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

`}`

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.

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.

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)*