barrym95838 wrote:
gfoot wrote:
The sprite width being a power of two will make Bresenham very easy to do in hardware I think.
Bresenham was exactly the first thing that popped into my head, but I lack the hardware and/or software chops to actually implement it.
For this aspect I would start by thinking of what state it needs to store and how that state is updated on each step. What state do we have? The residue needs storing somewhere (e.g. in an 8-bit D flipflop register). We also need source and destination address counters, or shift registers, or similar things.
Regarding the state updates, we need to be able to add a constant to the residue, so need maybe a 4-bit adder to do that. Being able to reset it is also useful at the start, so use a DFF with a reset pin. For 8-pixel wide sprite, the bottom three bits from the adder feed back th the register's inputs, so it does the modulo automatically. So those two together can count up in fives modulo 8 for my example, based on an input clock.
The next bit up on the adder is then effectively a carry bit, indicating whether the residue is about to overflow. If this is set then on the next clock we want to increment the destination pixel. So this could feed into a clock enable pin on a counter, perhaps. Then the counter and residue will work in tandem based on the input clock, and another counter can also be counting up the source pixel index on every tick.
This is simpler because the divisor is a power of two, meaning that the remainder "carries" when a certain number of bits overflows (3 bits in my case) and taking the modulus is just discarding that top bit.
For other divisors you need to do some sort of magnitude comparison, and then subtract the divisor if it overflowed. One observation there is that we might as well go ahead with the subtraction, then if the result of that is not negative, then we did overflow. So the magnitude comparison is built in. Now we just need to tick the destination address counter if that happened, and arrange for the residue register to load from the subtraction output rather than the adder output. So a multiplexer would do that nicely.
I might see about putting this together in logisim or a schematic if anyone is interested to see it all together (and test if it works!)
I just realised that the original question talked about stretching sprites but my example was the opposite. In this case the divisor is going to be the target width, not the source width, and so it indeed won't necessarily be a power of two.