Speccy, Vol 3: Sprites

November 30th, 2015

There's no way around it, sprites are pretty necessary when doing just about anything, so I tackled this problem. First, here's the sprite I'm using:

Uh, let's zoom a bit. Too bad there's no standard way to disable the bilinear filtering. Maybe in a future browser:

So yeah, I'm not a graphics designer. Anyway. The colors are black, white, and anything else. Everything that's black or white becomes the "sprite data" or "or mask" and everything that's anything else becomes "sprite mask" or "and mask".

Why do we need the two masks? Since the screen is a bitmap with every byte representing 8 pixels, we'll want to preserve any pixels that our sprite is not covering. We'll have to do a read-modify-write operation, where we first take the current pixels off the screen, then AND our sprite mask to cause all pixels that are on the sprite to become zero, and then OR our sprite data on top of this to turn the pixels back on where we want.

For any kind of speed, the 16x16 sprite has to be stored as eight 24x16 sprites, one copy for each sideways shifting. Remember, the z80 doesn't have a barrel shifter, so doing the shifting on the fly would be rather slow. If the sprite is animated (say, a walking animation), those animation frames can sometimes be written to these shifted copies, saving space, and you get the animation playing for free to boot.

Iteration 1, in pure C, managed to render one sprite in a frame.

Iteration 2, where I massaged the sprite data to be more streamlined - every two bytes of data contains one byte of mask and one byte of pixel data - managed three sprites in a frame. Still way too slow, so I went down to assembly.

/* shift 3*/
0b11111111, 0b00000000, 0b00000011, 0b11111100, 0b11111111, 0b00000000, 
0b11111100, 0b00000011, 0b00000000, 0b00000011, 0b11111111, 0b00000000, 
0b11111000, 0b00000100, 0b00000000, 0b00000000, 0b01111111, 0b10000000, 
0b11110000, 0b00001000, 0b00000000, 0b10000000, 0b00111111, 0b01000000, 
0b11110000, 0b00001001, 0b00000000, 0b01000000, 0b00111111, 0b01000000, 
0b11100000, 0b00010000, 0b00000000, 0b10000000, 0b00011111, 0b00100000, 
0b11100000, 0b00010000, 0b00000000, 0b00000000, 0b00011111, 0b00100000, 
0b11100000, 0b00010000, 0b00000000, 0b00000000, 0b00011111, 0b00100000, 
0b11100000, 0b00010000, 0b00000000, 0b00000000, 0b00011111, 0b00100000, 
0b11100000, 0b00010000, 0b00000000, 0b00000000, 0b00011111, 0b10100000, 
0b11100000, 0b00010000, 0b00000000, 0b00000000, 0b00011111, 0b00100000, 
0b11110000, 0b00001000, 0b00000000, 0b00000000, 0b00111111, 0b01000000, 
0b11110000, 0b00001000, 0b00000000, 0b00000001, 0b00111111, 0b01000000, 
0b11111000, 0b00000100, 0b00000000, 0b00001000, 0b01111111, 0b10000000, 
0b11111100, 0b00000011, 0b00000000, 0b00000011, 0b11111111, 0b00000000, 
0b11111111, 0b00000000, 0b00000011, 0b11111100, 0b11111111, 0b00000000, 

Oh yeah, the SDCC compiler (like most small device compilers) supports the 0b00000000 literals. My PNG to sprite data converter could easily be changed to outputting hex constants. Or to draw ascii art. Or to do political commentary on twitter. But I digress.

Iteration 3, with inner loop (which renders one span of the sprite) in assembly got up to 6 sprites in a frame.

Iteration 4 unrolled the whole drawing routine, and had it completely in assembler, managed 18 sprites in a frame. Here's code for one span (repeats 16 times):

        ld e, 2 (iy) ; fetch screen y offset from table
        ld d, 3 (iy)
        ex de,hl
        add hl, bc   ; add x offset
        ex de,hl

        ld a, (de)   ; load pixel from screen
        and (hl)     ; and the mask
        inc hl       ; increment data ptr
        or (hl)      ; or the pixel data
        ld (de),a    ; put modified pixels to screen
        inc hl       ; increment data ptr
        inc de       ; increment screen ptr
                        
        ld a, (de)   ; rinse
        and (hl)    
        inc hl      
        or (hl)     
        ld (de),a   
        inc hl      
        inc de      
                        
        ld a, (de)   ; repeat
        and (hl)    
        inc hl      
        or (hl)     
        ld (de),a   
        inc hl

At this point I stepped back and pondered if there was some other approach I could take. Any further optimizations on the current approach would be very incremental. So I wrote a code generator that takes in the sprite data, and outputs assembler functions that have the sprite data baked in. Armed with the knowledge of what exactly is in the sprite data, the code generator could take some shortcuts, and for all writes where all of the pixels get overwritten it can skip the whole read-modify-write operation and just write out the sprite data.

The result was 26 sprites in a frame. On average. Since the sprite data is different for every shifted version, the shortcuts also vary - some shifted versions are faster than others.

    ld l, 2 (iy) ; fetch screen y offset
    ld h, 3 (iy)
    add hl, bc   ; add x offset

    ld a, (hl)   ; load pixel from screen
    and #252     ; and with hardcoded value
    or #3        ; or with hardcoded value
    ld (hl), a   ; plot pixel to screen
    inc hl       ; increment screen ptr

    ld (hl), #3  ; write hardcoded value (mask was 0)

    ; skip third byte completely since it doesn't change screen

There are two other drawbacks to this approach. First, it takes a lot of space. The data-based approach took 546 bytes for the rendering routine and 768 bytes for the sprite, and if I wanted to render several different kinds of sprites (gasp!), each of these would take 768 bytes more.

The "compiled sprite" took 3645 bytes. And it can handle only this one specific 16x16 sprite. I did consider the possibility of doing some kind of crazy self-modifying-code hack where you first prime the function with the sprite data and then render several times, which should still be faster... but that would mean removing all of the shortcuts, which would make the routine slower and bigger.

Iteration 5 of the data based approach abused the stack mechanism of the z80 and got up to 20 sprites per frame. Also swapped a couple of registers to get rid of some instructions. Code size dropped to 470 bytes.

        ld l, 0 (iy) ; fetch y offset from table
        ld h, 1 (iy)
        add hl, bc   ; add x offset

        pop de       ; get mask and pixel data using stack
        ld a, (hl)   ; load pixel from screen
        and e        ; and the mask
        or d         ; or the pixel data
        ld (hl),a    ; put modified pixels to screen
        inc hl      
                    
        pop de       ; rinse
        ld a, (hl)  
        and e       
        or d        
        ld (hl),a   
        inc hl      
                    
        pop de       ; repeat
        ld a, (hl)  
        and e       
        or d        
        ld (hl),a   

The sprites per frame values are from a non-accurate emulator that doesn't handle the ULA contention timings (where ULA monopolizes memory and causes z80 to delay), so the actual sprite counts are lower. The relative speedups are still real. The drawing routines also simply draw the sprites, and there's no clearing covered here, so the routines as is are not too useful, but they are a foundation.

All of the code is available on github.