Test Drive’s pixelized transition effect

Today I want to talk about the transition effect in the game Test Drive from 1987. The effect will switch from one image to the next by replacing it pixel for pixel in a somewhat randomized pattern:

I discussed this effect with Trixter, as I was thinking of ‘borrowing’ the idea for a future demo. I described how I thought the effect worked, roughly, and that I might want to reverse-engineer it to make sure.
He beat me to it however, and sent me this snippet as the core of the effect (comments are his):

lodsb           ; load packed pixels from source
and al, ah      ; mask some pixels out
not ah          ; invert mask
mov dl, es:[di] ; dl = existing byte onscreen
and dl, ah      ; mask some screen pixels out
or al, dl       ; combine source and screen pixels
mov es:[di], al ; store combination on screen
stosb           ; someone doesn't understand what stosb does!
not ah          ; invert mask
ror ah, 1       ; rotate mask by single bit

It was more or less what I expected, although it was simpler in nature, more linear. This code is run for an entire scanline. The order of the scanlines is randomized, but as you can see, it merely rotates the mask linearly along each scanline. But since this is done per-byte, and there are multiple pixels in a byte, it doesn’t appear to be as linear as it is. Apparently the mask is a byte value with 1 bit set, which is then rotated to the right one bit at a time. The most likely starting value for the mask would be 80h.

As you can also see from Trixter’s comments, even at first glance, the code does already look suboptimal. The mov es:[di], al is completely redundant, since stosb writes al to es:[di] as well, before increasing di.
Which is interesting in a way. Such an old game, which is not carefully hand-optimized. Not what I would have expected. It is even possible that this code was actually generated by a compiler.

Looking at it some more, I started spotting other optimizations. Firstly, if you were to take a second register for the inverted mask, you only need one extra rotate, and you can remove the two not-instructions:

lodsb           ; load packed pixels from source
and al, ah      ; mask some pixels out
mov dl, es:[di] ; dl = existing byte onscreen
and dl, dh      ; mask some screen pixels out
or al, dl       ; combine source and screen pixels
stosb           ; store combination on screen
ror ah, 1       ; rotate mask by single bit
ror dh, 1       ; rotate inverted mask by single bit

And once you’ve come this far, it becomes apparent that by choosing your registers wisely, you can combine the two 8-bit ands into a single 16-bit and:

lodsb           ; load packed pixels from source
mov ah, es:[di] ; ah = existing byte onscreen
and ax, dx      ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
ror dl, 1       ; rotate mask by single bit
ror dh, 1       ; rotate inverted mask by single bit

This reinforces my belief that it is not hand-coded. Because if you write this code in a language like C, you would do it ‘by the book’. And the above optimizations are not trivial to see from C code. From assembly however, they just leap out at you.

We could take the idea of going 16-bit even further:

lodsw           ; load packed pixels from source
and ax, dx      ; mask some pixels out
not dx          ; invert mask
mov bx, es:[di] ; dl = existing byte onscreen
and bx, dx      ; mask some screen pixels out
or ax, bx       ; combine source and screen pixels
stosw           ; store combination on screen
not dx          ; invert mask
ror dl, 1       ; rotate mask by single bit
ror dh, 1       ; rotate mask by single bit

Note however that for this version I chose to go back to using the not-instructions. The reason for this is that the rotates have to be done per byte. This would mean 4 rotate-instructions. The nots however can be done per word, so I still only need 2 of them in this 16-bit version.

These rotates however, they are quite a limiting factor on the overall optimization. So I wanted to try and get rid of them. I had the following idea: since you rotate a byte one bit at a time, you only have 8 unique values for the masks, a sequence which keeps repeating.
So if you unroll the code 8 times, you can hardcode all the masks as immediate operands, and remove the rotate-instructions altogether.

There is a catch however: The code has to be able to start with any given mask. The simplest way around that is to determine which mask you get, and then use a jumptable to jump to the right routine:

tdTable dw td0, td1, td2, td3, td4, td5, td6, td7

; Determine position of bit
xor bx, bx

@@bitLoop:
inc bx
add ah, ah
jnz @@bitLoop

add bx, bx
jmp cs:[tdTtable][bx][-2]

I first implemented it with byte-oriented routines.
I will just show the first and the second, so you can see how they are the same, except for the immediate operands being pre-rotated differently. The other 6 routines work the same way:

td0 PROC
mov cx, 100

@@loopHeight:
push cx
mov cx, 80/8

@@loopScanline:
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 7F80h   ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0BF40h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0DF20h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0EF10h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0F708h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FB04h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FD02h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FE01h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
loop @@loopScanLine

pop cx
loop @@loopHeight

ret
td0 ENDP

td1 PROC
mov cx, 100

@@loopHeight:
push cx
mov cx, 80/8

@@loopScanline:
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0BF40h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0DF20h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0EF10h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0F708h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FB04h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FD02h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 0FE01h  ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
lodsb           ; load packed pixels from source
mov ah, es:[di] ; dl = existing byte onscreen
and ax, 7F80h   ; mask some pixels out
or al, ah       ; combine source and screen pixels
stosb           ; store combination on screen
loop @@loopScanLine

pop cx
loop @@loopHeight

ret
td1 ENDP

Quite a lot of code… However, we can ‘re-roll’ it somewhat, by using 16-bit instructions instead. That way you process 2 bytes at a time, so the unrolled code only has to do 4 iterations:

td0 PROC
mov cx, 100

@@loopHeight:
push cx
mov cx, 80/8

@@loopScanline:
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 4080h   ; mask some pixels out
and dx, 0BF7Fh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 1020h   ; mask some pixels out
and dx, 0EFDFh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 0408h   ; mask some pixels out
and dx, 0FBF7h  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 0102h   ; mask some pixels out
and dx, 0FEFDh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
loop @@loopScanLine

pop cx
loop @@loopHeight

ret
td0 ENDP

td1 PROC
mov cx, 100

@@loopHeight:
push cx
mov cx, 80/8

@@loopScanline:
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 2040h   ; mask some pixels out
and dx, 0DFBFh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 0810h   ; mask some pixels out
and dx, 0F7EFh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 0204h   ; mask some pixels out
and dx, 0FDFBh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
lodsw           ; load packed pixels from source
mov dx, es:[di] ; dl = existing byte onscreen
and ax, 8001h   ; mask some pixels out
and dx, 07FFEh  ; mask some pixels out
or ax, dx       ; combine source and screen pixels
stosw           ; store combination on screen
loop @@loopScanLine

pop cx
loop @@loopHeight

ret
td1 ENDP

So, and what was the point of all this? Well, nothing really! Namely, the transition only does a few scanlines per frame, and is tuned to perform a transition in 3 seconds. So, even though we now have a faster routine, it only means that we have more idle time, if we want to stick to the 3 second transition speed. Going faster could ruin the effect. But hey, at least it was fun, and we got to flex our creative muscle, so it’s all good!