Fades in older games. Need some help figuring out how the algorithm was derived

Question

Sorry, this question is a bit esoteric, but I just can't get it out of my head!

I'm looking at the fade algorithm used in the arcade game DoDonPachi (as well as many other older games):

I wrote a python script to pick out a few pixels and track them for the duration of the fade. Here's a representative sample of the results. The first row of each group is the starting color value, while each subsequent row is the difference between the the color value of the current frame and the color value of the previous frame.

Starting Value: (132, 66, 189)
Frame 1:    [9, 9, 8]
Frame 2:    [8, 8, 8]
Frame 3:    [8, 8, 8]
Frame 4:    [8, 8, 9]
Frame 5:    [9, 9, 8]
Frame 6:    [8, 8, 8]
Frame 7:    [8, 8, 8]
Frame 8:    [8, 8, 9]
Frame 9:    [9, 0, 8]
Frame 10:   [8, 0, 8]
Frame 11:   [8, 0, 8]
Frame 12:   [8, 0, 9]
Frame 13:   [9, 0, 8]
Frame 14:   [8, 0, 8]
Frame 15:   [8, 0, 8]
Frame 16:   [8, 0, 9]
Frame 17:   [0, 0, 8]
Frame 18:   [0, 0, 8]
Frame 19:   [0, 0, 8]
Frame 20:   [0, 0, 9]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 8]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 0]
Frame 25:   [0, 0, 0]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (132, 0, 0)
Frame 1:    [9, 0, 0]
Frame 2:    [8, 0, 0]
Frame 3:    [8, 0, 0]
Frame 4:    [8, 0, 0]
Frame 5:    [9, 0, 0]
Frame 6:    [8, 0, 0]
Frame 7:    [8, 0, 0]
Frame 8:    [8, 0, 0]
Frame 9:    [9, 0, 0]
Frame 10:   [8, 0, 0]
Frame 11:   [8, 0, 0]
Frame 12:   [8, 0, 0]
Frame 13:   [9, 0, 0]
Frame 14:   [8, 0, 0]
Frame 15:   [8, 0, 0]
Frame 16:   [8, 0, 0]
Frame 17:   [0, 0, 0]
Frame 18:   [0, 0, 0]
Frame 19:   [0, 0, 0]
Frame 20:   [0, 0, 0]
Frame 21:   [0, 0, 0]
Frame 22:   [0, 0, 0]
Frame 23:   [0, 0, 0]
Frame 24:   [0, 0, 0]
Frame 25:   [0, 0, 0]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (165, 156, 222)
Frame 1:    [9, 8, 8]
Frame 2:    [8, 8, 8]
Frame 3:    [8, 8, 8]
Frame 4:    [8, 9, 9]
Frame 5:    [9, 8, 8]
Frame 6:    [8, 8, 8]
Frame 7:    [8, 8, 8]
Frame 8:    [8, 9, 9]
Frame 9:    [9, 8, 8]
Frame 10:   [8, 8, 8]
Frame 11:   [8, 8, 8]
Frame 12:   [8, 9, 9]
Frame 13:   [9, 8, 8]
Frame 14:   [8, 8, 8]
Frame 15:   [8, 8, 8]
Frame 16:   [8, 9, 9]
Frame 17:   [9, 8, 8]
Frame 18:   [8, 8, 8]
Frame 19:   [8, 8, 8]
Frame 20:   [8, 0, 9]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 8]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 9]
Frame 25:   [0, 0, 8]
Frame 26:   [0, 0, 8]
Frame 27:   [0, 0, 8]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

Starting Value: (156, 90, 206)
Frame 1:    [8, 8, 8]
Frame 2:    [8, 8, 9]
Frame 3:    [8, 8, 8]
Frame 4:    [9, 9, 8]
Frame 5:    [8, 8, 8]
Frame 6:    [8, 8, 9]
Frame 7:    [8, 8, 8]
Frame 8:    [9, 9, 8]
Frame 9:    [8, 8, 8]
Frame 10:   [8, 8, 9]
Frame 11:   [8, 8, 8]
Frame 12:   [9, 0, 8]
Frame 13:   [8, 0, 8]
Frame 14:   [8, 0, 9]
Frame 15:   [8, 0, 8]
Frame 16:   [9, 0, 8]
Frame 17:   [8, 0, 8]
Frame 18:   [8, 0, 9]
Frame 19:   [8, 0, 8]
Frame 20:   [0, 0, 8]
Frame 21:   [0, 0, 8]
Frame 22:   [0, 0, 9]
Frame 23:   [0, 0, 8]
Frame 24:   [0, 0, 8]
Frame 25:   [0, 0, 8]
Frame 26:   [0, 0, 0]
Frame 27:   [0, 0, 0]
Frame 28:   [0, 0, 0]
Frame 29:   [0, 0, 0]

As you can see, either an 8 or a 9 is subtracted from each color component in each frame. Furthermore, a 9 always appears three frames after an 8, even though the starting subtracted value is different for each color component. Note also that each color component reaches 0 (that is, black) with a difference of either 8 or 9, not some arbitrary remainder. This means that the subtracted value cycle of 8,8,8,9 is never broken! (This algorithm was probably written to ensure that the last frame of the fade was as smooth as the others.)

Now, this puzzles me. According to my calculations, if you reverse the process -- that is, take the 8,8,8,9 cycle and sum it up to find all the possible combinations in 29 frames -- you only get 52 unique numbers. But as it so happens, each color component is a member of this set! This means that either the colors were picked specifically for this fade algorithm (unlikely), or that the fade algorithm was designed around the color palette of the game. But how on earth could somebody have figured out that if you take 8,8,8,9, shift the cycle appropriately, and keep subtracting the numbers from each color component in your palette, you'll eventually reach 0 for every single color?! There's gotta be some mathematical trick that I'm missing. What is it?

Answer 1

Actually, there's a simple logic behind the 8-8-8-9 pattern. It arises naturally if you use only 32 intensity levels (5 bits per component), but want to render that on an 8-bit-per-component display.

Consider if you have a 5-bit intensity level and want to extend it to 8 bits. The simplest thing to do would be to just shift-left and leave the low three bits zero. The trouble is, then it doesn't go all the way to pure white. The highest intensity level you can reach is 11111000, or 248. So you're not using the full intensity range of the 8-bit display.

Really, what you'd want to do is a calculation like intensity8 = round(intensity5 * 255.0 / 31.0), to rescale the [0, 31] range to [0, 255]. However, there's a neat trick to accomplish this without any floating-point math or divides: set the low three bits equal to the high three bits. That is, to convert intensity from 5-bit to 8-bit you'd do

intensity8 = (intensity5 << 3) | (intensity5 >> 2);

Then an intensity of 11111 will map to 11111111 (31 maps to 255), and intermediate results will do something sane as well, e.g. 10000 -> 10000100 (16 -> 132).

This set of numbers is exactly what you have. Taking the red component of your first example, you have:

132    10000100
123    01111011
115    01110011
107    01101011
 99    01100011
 90    01011010
 82    01010010
 74    01001010

Note how the low three bits are always equal to the top three bits. The difference of 9 occurs when both bit 0 and bit 3 flip at the same time.

I'm uncertain why 5-bit intensity levels would have been used in this situation; perhaps that was the limit of the hardware of the arcade machine? It's notable that a 5-bit RGB value is 15 bits, which fits nicely into a 16-bit word. In any case, that explains the odd 8-8-8-9 pattern.

Answer 2

You should look into mode 13h, or 256 color palette fading. Back then, you had that many colors and what you did, was messing around with the whole palette, since you couldn't calculate new colors that weren't in it.