This week I came across an excellent post by Fabien Sanglard analyzing the ‘Fizzlefade’ algorithm in the classic game Wolfeinstein 3D. It’s a great read and his blog is excellent - he analyzes interesting algorithms and techniques in games and graphics development.
Now despite what Google and Facebook’s interview questions might think it’s pretty rare that you come across algorithms like these in software engineering, so I wanted to spend some time analyzing and understanding the algorithm. Cause it’s fun!
Wolfeinstein 3D has an interesting death animation where the screen ‘fizzles’ - the entire screen turns to red one pixel at a time, seemingly at random. Instead of implementing this by randomly turning pixels red - which would either be non-deterministic or use up extra memory - the game designers use a technique called a Linear-feedback shift register. The original code was written in assembly but Fabien translated it into C.
Fabien’s post does a great job of explaining how the Linear-feedback shift register works, so I’m not going to cover that. However, I still had a few questions about how this code:
- Why do we use the low 8 bits and the high 9 bits? What’s magic about 8 and 9 in this context?
- Why are variables in C named so obscurely? Why
random_value, for example? Could this code be refactored to be - gasp - readable? Could we test it?
The first question is the easiest to answer - Wolfenstein 3D was programmed for a 320 * 200 display. That means the x-coordinate can be represented with 9 bits (2^9 = 512) and the y-coordinate can be represented with 8 bits (2^8 = 256). The fact that details like these are embedded into the code probably explains why it has never been ported to a higher resolution - all of the online emulators that I’ve seen are still in 320 * 200.
The second question is a bigger challenge.
Is it possible to refactor this code to be readable? If code comments are considered harmful, can we write a readable version of this code that doesn’t use comments? I haven’t written C code in at least 10 years, but I thought it would be an interesting exercise to see if it’s actually possible to apply some modern techniques to this problem.
The first problem I tackled was how to actually write tests for this algorithm. I didn’t even check to see if there’s any testing libraries for C - I’m happy with just writing regular functions that
printf their results - but I needed some way to check the results of the algorithm in isolation. Right now the
fizzlefade function depends on a
fizzle_pixel function, which is actually the only result of the function. (It does actually have a boolean return value, although that is pretty meaningless) Can I inject the
fizzle_pixel function, allowing me to swap out a test function?
To test this I created a simple function that simply prints the coordinate.
Here’s the output.
Now we’re talking! Next up I wanted to add some ‘tests’ - basically just have some checks to ensure the algorithm is working as expected. I’m completely fine with just writing to the console when a test fails, the minimum amount of effort here is definitely enough. I came up with 4 different tests:
- Every x coordinate returned must be between 0 and 320 (0 <= x < 320)
- Every y coordinate returned must be between 0 and 200 (0 <= y < 200)
- Every position returned must be unique - the same pixel can’t be ‘fizzled’ twice
- Every position must be returned - all pixels must be ‘fizzled’
Here is my very amateur C code to make this happen:
Now when I run this code I would expect to see no output.
What’s going on here? Turns out the algorithm never iterates over the position
0,0 (which I believe is the top left position). Turns out this is just a bug in C version of this code - the original assembler version of code subtracts 1 from the y coordinate after grabbing the lower 8 bits. So the correct C version of this code would actually do this:
When I made this change all the ‘tests’ pass, neat! Now let’s see if we can make this code a bit more readable.
Turns out cleaning up C code is really difficult! My only real contribution here was to use constants and better variable names. I also changed it to a void function since the return value was unused - the original assembler code checked for a system interrupt (I’m guessing this allowed the user to skip the death animation). Some of the code is just really difficult to encapsulate since it’s just very magicky - for example, knowing that we only need to apply the XOR when the least significant bit is set. If you take that out the Linear-feedback shift register never returns to 1, but I couldn’t think of a way to make this obvious.
If you want to look at the code it’s available on Github. If you have suggestions for how you would clean up code like this leave a comment below.