==**How to make a LFSR more compact**==

In a previous blog entry, I looked at how to implement a LFSR in 6502. The code took 18 bytes of ROM. The actual code used in the Pitfall cartridge uses 15 bytes:

`uint8_t lfsr_3(uint8_t r) {`

` uint8_t a, c, t;`

` a = r; // LDA r a: r`

` c = a >> 7; a <<= 1; // ASL a: r << 1`

` a ^= r; // EOR r a: r << 1 ^ r`

` c = a >> 7; a <<= 1; // ASL a: r << 2 ^ r << 1`

` a ^= r; // EOR r a: r << 2 ^ r << 1 ^ r`

` c = a >> 7; a <<= 1; // ASL a: r << 3 ^ r << 2 ^ r << 1`

` c = a >> 7; a <<= 1; // ASL a: r << 4 ^ r << 3 ^ r << 2`

` a ^= r; // EOR r a: r << 4 ^ r << 3 ^ r << 2 ^ r`

The next command is a little tricky. It takes the left bit of a and puts it in the “carry” bit.

When grabbing the 7th (left) bit of a value which is a series of left shifts, we can convert the left shifts in to the corresponding right shifts by taking 7 and subtracting it from the right shift value.

When this is done, grabbing the left bit makes a left shift of 0 become a right shift of 7, a left shift of 1 be a right shift of 6 and so on:

`Before (<<) After(>>)`

`0 7`

`1 6`

`2 5`

`3 4`

`4 3`

`5 2`

`6 1`

`7 0`

This in mind, by taking the left bit of “r << 4 ^ r << 3 ^ r << 2 ^ r” (4,3,2,0), we get “r >> 3 ^ r >> 4 ^ r >> 5 ^ r >> 7” (3,4,5,7). Let’s continue the code in the actuall Pitfall cartridge:

` c = a >> 7; a <<= 1; // ASL`

` t = r >> 7; r <<= 1; r |= c; c = t; // ROL r`

` return r;`

`}`

The reason David Crane wrote the code this way was to save three bytes; while the code is harder to follow, it’s now 15 instead of 18 bytes long.

==**Why this particular tap sequence**==

There are 16 different possible tap sequences for this particular random number generator. The reason Pitfall uses this particular one is because it has the most compact representation in 6502; other sequences use more code.

If David Crane knew then when we know today about pseudo-random number generators, he would have used a different algorithm. The code we have been looking at is actually called a “Fibonacci LFSR”. There is a variant way of representing a LFSR called a “Galois LFSR” which is even smaller; we will look at that as well as another small possible variant random number generator for Pitfall 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)*