Fizzlefade

I enjoy reading a lot of source code and after 15 years in the field I feel like I have seen my fair share. Even with a full-time job, I still try to spare evenings here and there to read. I don't see myself ever stopping. It is always an opportunity to learn new things to follow somebody's mind process.

Every once in a while I come across a solution to a problem that is so elegant, and so creative that there is no other word but "beautiful" to describe it. Q_rsqrt, better known as "Inverse Square Root" and popularized by Quake 3, definitely belong to the family of breathtaking code. While I was working on the Game Engine Black Book: Wolfenstein 3D I came across an other one: Fizzlefade.

Fizzlefade is the name of the function in charge of fading from a scene to an other in Wolfenstein 3D. What it does is turn the pixels of the screen to a solid color, only one at a time, seemingly at random.

// What The Fizzle ?!

In Wolfenstein 3D, most screen transitions are done with a fade to black (by shifting the palette), there are two instances when the screen transitions via fizzling:

• When dying
• When killing a boss

Below are a series of screenshots to illustrate fizzling. During the transition, each pixel on the screen is turned to red (when dying) or blue (when dispatching a boss). Each pixel is written only once and seemingly at random.



To implement this effect, a naive approach would have been to use the pseudo random generator US_RndT and keep track of which pixels had been fizzled. However, this would make the fade non-deterministic with regard to duration and would also waste CPU cycles since the same pixel coordinates (X,Y) could come up several times. There is a much faster and more elegant way to implement a pseudo-random value generator. The code responsible for this effect can be found in id_vh.cpp, function FizzleFade. At first, it is not obvious how it works.

  boolean FizzleFade {
    long rndval = 1;
    int x , y ;
    do
    {
      // seperate random value into x/y pair
      asm mov ax ,[ WORD PTR rndval ]
      asm mov dx ,[ WORD PTR rndval +2]
      asm mov bx , ax
      asm dec bl
      asm mov [ BYTE PTR y ], bl // low 8 bits - 1 = y
      asm mov bx , ax
      asm mov cx , dx
      asm mov [ BYTE PTR x ], ah // next 9 bits = x
      asm mov [ BYTE PTR x +1] , dl
    
      // advance to next random element
      asm shr dx ,1
      asm rcr ax ,1
      asm jnc noxor
      asm xor dx ,0x0001
      asm xor ax ,0x2000
    
      noxor :
      asm mov [ WORD PTR rndval ] , ax
      asm mov [ WORD PTR rndval +2] , dx

      if (x > width || y > height ) continue ;
          
      fizzle_pixel (x , y ) ;
    
      if ( rndval == 1) return false ; // end sequence

    } while (1)
  }

If you can't read 16 bits TASM (I won't blame you), this is the C equivalent:

  
  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;
  }

Which can be read as:

• Initialize rndval to 1.
• Break it down in 9 + 8 bits: use 8 bits to generate a Y coordinate and 9 bits for a X coordinate. Turn this pixel to red.
• Subject rndval to a soup of XORing.
• When rndval value is somehow back to 1: Stop, the screen is solid red.

This feels like dark magic. How is rndval supposed to return to value 1? That technique is called Linear Feedback Shift Register. The idea is to use one register to store a state, generate the next state, and also generate a value. To get the next value, you do a right shift. Since the rightmost bit disappears, a new one to the left is needed. To generate this new bit, the register uses "taps" which are bit offsets used to XOR together values and generate the new bit value. A Fibonnaci representation shows a simple LFSR with two taps.



This register (with taps on bit 0 and 2) is able to generate 6 values before it cycles back to it original state. The following listing shows all of them (the stars indicate the taps location).

   * * | value
  ======================
  0001 | 1
  1000 | 8
  0100 | 4
  1010 | A
  0101 | 5
  0010 | 2
  0001 | 1 -> CYCLE

  Sequence of 6 numbers before cycling .

Various arrangements of taps will produce different series. In the case of this four bits register, the maximum number of values in a series is 16-1 = 15 (zero cannot be reached.) This can be achieved with taps on bits 0 and 1. This is called a "Maximum-Length" LFSR.

    ** | value
  ======================
  0001 | 1
  1000 | 8
  0100 | 4
  0010 | 2
  1001 | 9
  1100 | C
  0110 | 6
  1011 | B
  0101 | 5
  1010 | A
  1101 | D
  1110 | E
  1111 | F
  0111 | 7
  0011 | 3
  0001 | 1 -> CYCLE

  Sequence of 15 numbers before cycling .

Wolf uses a 17 bits Maximum-Length LFSR with two taps to generate a serie of pseudorandom values. Of these 17 bits, on each iteration, 8 are used to generate a Y coordinate and 9 for a X coordinate. The corresponding pixel on screen is turned red/blue.



The Fibonacci representation helps to understand the general idea. But it is not how a LFSR is usually implemented in software. The reason is that it scales linearly with the number of taps. With four taps, you need three sequential XOR operations:



There is an alternative way to represent a LFSR called "Galois" which requires only one XOR regardless of the number of taps and it is the way Wolfenstein 3D writes 320x200=64000 pixels exactly once with deterministic duration.



Note : Because the effect works by plotting pixels individually, it was hard to replicate when developers tried to port the game to hardware accelerated GPU. None of the ports managed to replicate the fizzlefade except Wolf4SDL, which found a LFSR taps configuration to reach resolution higher than 320x200.

Note : The tap configuration on 17 bits generates 131,072 values before cycling. Since 320x200=64000, it could have been implemented with a 16 bits Maximum-length register with taps on 16,15,13 and 4 (in "Galois" notation.). My assumption is that LFSR literature was hard to come across in 1991/1992 and finding the correct tap for a 16 bit maximum length register was not worth the effort.

Recommended reading

Game Engine Black Book: Wolfenstein 3D