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)