Sam Trenholme's webpage
Support this website or listen to my music

Pitfall redux

 

June 8 2013

In this blog, I discuss Pitfall's random number generator by looking at 8-bit linear feedback shift registers (LFSRs) in general. This continues a series started in the last blog posted.

==Pitfall uses a LFSR==

In previous blog entry, I mentioned that Pitfall uses a LFSR. LFSR exist for every single power of two four or higher; since the Atari 2600’s CPU is an 8-bit CPU, Pitfall ended up using an 8-bit LFSR that looks like this in C:

uint8_t pitfall_lfsr(uint8_t random) {
        uint8_t t; // temp
        t = (random >> 7) ^ (random >> 5) ^ (random >> 4) ^ (random >> 3);
        random <<= 1;
        random |= t & 1;
        return random;
}

The values 3, 4, 5, and 7 chosen for the shifts were not chosen at random; while there are 128 possible 8-bit LFSRs (128 because tap 7 is always set in an 8-bit LFSR), only 16 of them have a period of 255. In other words, only 16 different 8-bit LFSRs, when run repeatedly, generate all 255 non-0 8-bit numbers.

Of those 16 possible LFSRs, 12 of them have four “taps”; the other four have six taps. This detail is important when representing a LFSR in compact 6502 code—each tap takes two bytes of code to represent. For example, the above LFSR, which Pitfall uses, has the following four taps: (3, 4, 5, 7). This particular tap configuration, in lists of LFSRs, has the hexadecimal number “b8”, which looks like this in binary:

7 6 5 4 3 2 1 0
1 0 1 1 1 0 0 0

In the number “b8” (184 when represented in decimal—the numbers normally used by humans), the bits (3, 4, 5, 7) are set, which correspond to the taps seen above.

The 12 4-tap 8-bit LFSRs are, in hexadecimal: 8e, 95, 96, a6, b1, b2, b4, b8, c3, c6, d4, and e1.

Here is the number “b1”, in binary:

7 6 5 4 3 2 1 0
1 0 1 1 0 0 0 1

And the function to implement the LFSR:

uint8_t b1_lfsr(uint8_t random) {
        uint8_t t; // temp
        t = (random >> 7) ^ (random >> 5) ^ (random >> 4) ^ random;
        random <<= 1;
        random |= t & 1;
        return random;
}

==The inverse LFSR==

To calculate the inverse LFSR, do the following:

  • Convert the shift after the taps from a left shift in to a right shift
  • Have the or (“|=”) operation affect the top, not bottom bit of the number
  • Convert the “7” tap in to a “0” tap; add 1 to all of the other taps

In a previous blog entry, I showed both the forward and inverse LFSRs for Pitfall’s random number generator. Above is the forward LFSR for the “b1” tap configuration; the inverse is:

uint8_t inverse_b1_lfsr(uint8_t random) {
        uint8_t t; // temp
        t = (random >> 6) ^ (random >> 5) ^ (random >> 1) ^ random;
        random >>= 1;
        random |= t << 7;
        return random;
}

Instead of the taps (0,4,5,7), the taps here are (1,5,6,0)—each tap (except the “7” tap) is increased by 1; the “7” tap is converted in to a “0” tap.

==A final note==

If any LFSR is given a zero input, it will always output a zero; a full period 8-bit LFSR cycles through all 255 other 8-bit values.

==More to come==

Now that I have looked at the various 8-bit LFSRs that exist, I will next look at how a LFSR is implemented in 6502 assembly language, which will explain why David Crane chose the “b8” LFSR. All of this is in a future blog entry.

To post a comment about an entry, send me an email and I may or may not post your comment (with or without editing)

Previous entry Next entry Blog index