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!

Fizzlefade

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.

boolean fizzlefade(void)
{
  uint32_t rndval = 1;
  uint16_t x,y; 
  do
  {
     y =  rndval & 0x000FF;  /* Y = low 8 bits */
     x = (rndval & 0x1FF00) >> 8;  /* X = High 9 bits */
     unsigned lsb = rndval & 1;   /* Get the output bit. */
     rndval >>= 1;                /* Shift register */
     if (lsb) {                 /* If the output is 0, the xor can be skipped. */
          rndval ^= 0x00012000;
      }
      if (x < 320 && y < 200)
        fizzle_pixel(x , y) ;
  } while (rndval != 1);

  return 0;
}

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:

1. Why do we use the low 8 bits and the high 9 bits? What’s magic about 8 and 9 in this context?
2. Why are variables in C named so obscurely? Why rndval instead of 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.

Modernizing Fizzlefade

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?

typedef void (*PIXEL_FUNC_PTR)(uint16_t, uint16_t);

boolean fizzlefade(PIXEL_FUNC_PTR fizzle_pixel) {
  // exact same implementation
}

To test this I created a simple function that simply prints the coordinate.

void print_pixel(uint16_t x, uint16_t y) {
  printf("%d, %d\n", x, y);
}

int main(int argc, const char * argv[]) {
  fizzlefade(&print_pixel);
  return 0;
}

Here’s the output.

0, 1
288, 0
144, 0
72, 0
36, 0
18, 0
9, 0
4, 128
2, 64
1, 32
0, 144
0, 72
0, 36
0, 18
... Quite a few pages of this

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:

static bool test_screen[320][200];

void reset_test_screen() {
  int x,y;
  for(x=0;x<320;x++) {
    for(y=0;y<200;y++) {
      test_screen[x][y] = false;
    }
  }
}

void test_every_x_position_is_between_0_and_320(uint16_t x, uint16_t y) {
  if (x < 0 || x >= 320) {
    printf("test_every_x_position_is_between_0_and_320: %d was outside of the expected range\n", x);
  }
}

void test_every_y_position_is_between_0_and_200(uint16_t x, uint16_t y) {
  if (y < 0 || y >= 200) {
    printf("test_every_y_position_is_between_0_and_200: %d was outside of the expected range\n", x);
  }
}

void test_every_position_is_unique(uint16_t x, uint16_t y) {
  if (test_screen[x][y]) {
    printf("test_every_position_is_unique: %d, %d was returned multiple times\n", x, y);
  } else {
    test_screen[x][y] = true;
  }
}

void test_every_possible_position_is_returned(uint16_t x, uint16_t y) {
  test_screen[x][y] = true;
}


void run_all_tests() {
  printf("Running tests.\n");

  fizzlefade(&test_every_x_position_is_between_0_and_320);
  fizzlefade(&test_every_y_position_is_between_0_and_200);

  reset_test_screen();
  fizzlefade(&test_every_position_is_unique);

  reset_test_screen();
  fizzlefade(&test_every_possible_position_is_returned);
  int x,y;
  for(x=0;x<320;x++) {
    for(y=0;y<200;y++) {
      if (!test_screen[x][y]) {
        printf("test_every_possible_position_is_returned: %d, %d was never returned\n", x, y);
      }
    }
  }

  printf("All done.\n");
}

int main(int argc, const char * argv[]) {
  run_all_tests();
  return 0;
}

Now when I run this code I would expect to see no output.

Running tests.
test_every_possible_position_is_returned: 0, 0 was never returned
All done.

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:

y =  (rndval & 0x000FF) - 1;  /* Y = low 8 bits - 1 */

When I made this change all the ‘tests’ pass, neat! Now let’s see if we can make this code a bit more readable.

#define FIRST_BIT        (uint32_t)(0x00001)
#define FIRST_EIGHT_BITS (uint32_t)(0x000FF)
#define NEXT_NINE_BITS   (uint32_t)(0x1FF00)
#define LINEAR_FEEDBACK_SHIFT_REGISTER_TAPS (uint32_t)(0x00012000)

void fizzlefade(PIXEL_FUNC_PTR fizzle_pixel) {
  uint32_t random_value = 1;
  uint16_t x,y;
  unsigned least_significant_bit;
  do
  {
    y = (random_value & FIRST_EIGHT_BITS) - 1;
    x = (random_value & NEXT_NINE_BITS) >> 8;

    least_significant_bit = random_value & FIRST_BIT;
    random_value >>= 1;
    if (least_significant_bit) {
      random_value ^= LINEAR_FEEDBACK_SHIFT_REGISTER_TAPS;
    }

    if (x < 320 && y < 200) {
      fizzle_pixel(x , y);
    }
  } while (random_value != 1);
}

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.

Share on: Twitter, Facebook, Google+ or use the Permalink