lfsr math in pitfall!

A few weeks ago I attended VCF West at the Computer History Museum in Mountain View. One of my favorite talks was Making Games in the 1980s by David Crane and Garry Kitchen about the unique constraints of programming for the Atari 2600. Crane mentioned one hack in particular from his game Pitfall! that inspired this blog post.

Pitfall! is a platform game in which you control a character named Harry through a jungle filled with crocodiles, logs, ladders, and, of course, pits. One of its main innovations is allowing movement back and forth between different screens, creating the illusion of an enormous world (at least by the standards of the time).

Each screen is unique, with different arrangements of obstacles and enemies. Even the patterns of the trees in the background aren’t static; you can see the difference if you look closely at the treelines of the two screenshots below:

Each screen is represented by a single byte, with different bits controlling the objects to spawn, the layout of the holes, and so on. With 8 bits, it was possible to represent 255 unique screens (0x0 isn’t used, for reasons we’ll come to shortly).¹

The challenge is that the Pitfall! cartridge had only 4KB of read-only memory, most of which was needed to store the game executable. There was simply no space to store an additional 255 bytes in ROM.

So David Crane invented an ingenious hack. Instead of storing every screen’s configuration individually, he wrote code to generate a sequence of each possible byte from an initial value (0xC4) representing the first screen. Then he devised a way to reverse the generation so Harry could return to the previous screen.

I left the talk super curious about the math behind this trick. How exactly does the procedural generation and reversal in Pitfall! work? Let’s explore!

Definitions

Linear Feedback Shift Register (LFSR)

Let $B$ represent a sequence of $n$ bits for some $n \geq 2$, and let $b_i \in \{ 0, 1 \}$ denote the $i$th bit in $B$, with $1 \le i \le n$. For the 8-bit sequence used in Pitfall!, this looks like:

Pitfall! generates new sequences using something called a linear feedback shift register (LFSR), which is a transformation of $B$ to another $n$-bit sequence by:

1. Shifting the bits of $B$ to the left by one.
2. Calculating a new value for the last bit by XOR’ing some of the bits chosen from $B$.

In other words, an LFSR is a function $F$ of the form

where $f(B)$ (the “feedback function”) is derived from the bits of $B$

with coefficients $c_i \in \{0, 1 \}$. (The $\bigoplus$ operator means summation using XOR ($\oplus$) instead of addition.)

Fixing the values of $c_i$ produces a specific LFSR, and applying such an LFSR repeatedly produces a sequence of states, $B_1, B_2, B_3, ...$ where $B_{t+1} = F(B_t)$.

Maximal-length LFSR

If the LFSR produces every possible $n$-bit sequence except all zeroes, then it’s called a maximal-length LFSR. That is, both the domain and range of the function $F$ are $\{ x \in \{0, 1\}^n : x \ne 0^n\}$. The zero bit sequence $0^n$ is excluded because $F(0^n) = 0^n$, preventing progression to any other state.

Not all LFSRs are maximal-length; for example, it’s possible to choose the coefficients such that the LFSR “loops” through a subset of possible states. Crane intentionally chose a maximal-length LFSR for Pitfall! in order to generate all 255 possible screens.

Invertibility

In Pitfall!, the player is allowed to return to the previous screen by walking left. This requires a mechanism for reversing an LFSR to recover the previous state. Let’s call an LFSR invertible if there exists some operation $F^{-1}$ such that:

A trivial implementation of $F^{-1}$ for a maximal-length LFSR $F$ would repeatedly apply $F$ until observing output $B$, then return the input that produced $B$. Since there are $2^n-1$ reachable states, this has exponential time complexity in $n$. Even for small values like $n=8$, this would execute far too slowly on an Atari. We therefore restrict ourselves to inverses that are at least as efficient as $F$. In particular, they should require $O(1)$ memory and $O(n)$ operations (since $F$ executes a left shift plus $O(1)$ bitwise operations for each non-zero coefficient, of which there are at most $n$).²

How rare are maximal-length LFSRs?

The LFSR used in Pitfall! operates on 8-bit sequences. The family of LFSRs with $n=8$ has $2^8 = 256$ members, one for each possible assignment of the 8 coefficients. How many of these are maximal-length LFSRs? In other words, if Crane had flipped a coin for each coefficient, what is the probability that he would have found a maximal-length LFSR?

Since there are only 256 possible LFSRs to consider, we can find the answer by brute force using a short Python program.

First, we iterate through all possible assignments of n coefficients to generate a specific LFSR function f:

from itertools import product

def iter_lfsr(n):
    mask = (1 << n) - 1

    for coefficients in product([0, 1], repeat=n):
        def f(x):
            last_bit = 0
            for i, c in enumerate(coefficients):
                last_bit ^= c & (x >> (n - 1 - i)) & 0x01
            return ((x << 1) | last_bit) & mask

        yield coefficients, f

Then, for each LFSR, we check if it is maximal-length by counting the number of states reached from a non-zero initial state:

def is_max_len_lfsr(f, n):
    x = 1 # always a valid non-zero starting state for any n >= 2
    visited = set()

    while x not in visited and x != 0:
        visited.add(x)
        x = f(x)

    return len(visited) == (1 << n) - 1

This yields exactly sixteen maximal-length LFSRs for $n=8$, including the one that Crane chose for Pitfall!. Their coefficients are:

(1, 0, 0, 0, 1, 1, 1, 0)
(1, 0, 0, 1, 0, 1, 0, 1)
(1, 0, 0, 1, 0, 1, 1, 0)
(1, 0, 1, 0, 0, 1, 1, 0)
(1, 0, 1, 0, 1, 1, 1, 1)
(1, 0, 1, 1, 0, 0, 0, 1)
(1, 0, 1, 1, 0, 0, 1, 0)
(1, 0, 1, 1, 0, 1, 0, 0)
(1, 0, 1, 1, 1, 0, 0, 0) <-- this is the one used in Pitfall!
(1, 1, 0, 0, 0, 0, 1, 1)
(1, 1, 0, 0, 0, 1, 1, 0)
(1, 1, 0, 1, 0, 1, 0, 0)
(1, 1, 1, 0, 0, 0, 0, 1)
(1, 1, 1, 0, 0, 1, 1, 1)
(1, 1, 1, 1, 0, 0, 1, 1)
(1, 1, 1, 1, 1, 0, 1, 0)

(Notice that the first coefficient is always one. This will become important later.)

With $n=8$, choosing coefficients at random produces a maximal-length LFSR with probability $16/256 = 6.25\%$. What happens as we vary $n$? Since the number of coefficient assignments grows exponentially with $n$, brute force search quickly becomes intractable, but we can at least explore up to $n=16$ in a reasonable amount of time.³

Given that the total number of LFSRs is exponential in $n$, I would have expected the number of maximum-length LFSRs to strictly increase, but this isn’t how it works out. For example, $n=11$ has 176 maximum-length LFSRs, but $n=12$ has only 144.

Are all maximal-length LFSRs invertible?

How did Crane discover an LFSR that was both maximal-length and invertible? It may seem like an incredible coincidence that the LFSR he chose for Pitfall! happened to have an inverse. However, as I’ll show below, it is possible to construct an inverse function for any maximal-length LFSR by following a simple procedure.⁴

Intuition

Before giving the proof, I want to build some intuition from an example. Let’s use the exact LFSR and inverse from Pitfall!:

Something magical happens when we combine these two functions:

All the bits are shifted left by $F$, then shifted right by $F^{-1}$, restoring every bit except the first. The first bit $b_1$ gets “smuggled” by the feedback function $f$ into the last bit of $F(B)$. By canceling out the other terms of $f(B)$, the inverse $F^{-1}(B)$ recovers $b_1$!

This seems pretty amazing, but it turns out that the same trick works for every maximal-length LFSR. To prove it, we first need two lemmas.

Lemma: unique predecessors

If $F$ is a maximal-length LFSR, then for every state $S' \in \operatorname{range}(F)$ (the “successor”), there exists exactly one state $S \in \operatorname{domain}(F)$ (the “predecessor”) such that $F(S) = S'$.

Proof: Suppose to the contrary that there exists a maximal-length LFSR $F$ and state $S'$ such that either (1) there is no state $S$ where $F(S) = S'$ or (2) there are at least two states $S_1$ and $S_2$ where $S_1 \ne S_2$ and $F(S_1) = F(S_2) = S'$. In case (1), $S$ would not be within the domain of $F$, contradicting the assumption that $F$ is maximal-length. And in case (2), repeated application of $F$ must eventually produce either $S_1$ or $S_2$ since $F$ is maximal-length. If $F$ outputs $S_1$, then the next application $F(S_1)$ produces $S$ without ever producing $S_2$ (by the assumption that $F(S_1) = S$). Likewise, if $F$ outputs $S_2$, then the next state becomes $F(S_2) = S$ without ever producing $S_1$. Therefore the range of $F$ will exclude either $S_1$ or $S_2$, contradicting the assumption that $F$ is maximal-length. $\blacksquare$

Lemma: first coefficient

If $F$ is a maximal-length LFSR, then the first coefficient of its feedback function must be non-zero; that is, $c_1=1$.

Proof: Assume by way of contradiction that there exists an $F$ that is a maximal-length LFSR with $c_1=0$. Let $S_1 = (0, x_1, \dots, x_{n-1})$ and $S_2 = (1, x_1, \dots, x_{n-1})$ for any $x_i \in \{0, 1\}$. $S_1$ and $S_2$ differ only by the first bit, and since $c_1=0$, it follows that $f(S_1) = f(S_2)$ and therefore $F(S_1) = F(S_2)$. But the unique predecessors lemma implies that no two such states can exist for a maximal-length LFSR, contradicting the original assumption. $\blacksquare$

Inverse construction

With these lemmas, we can now construct an inverse for any maximal-length LFSR. Let’s define the inverse as:

In other words, we shift the bits of $B$ to the right and calculate an inverse feedback function $f^{-1}$ for the first bit:

where

(Intuitively: always include the last bit to retrieve the original feedback function $f(B)$, then include other bits to cancel out the other terms of $f(B)$ and recover $b_1$.)

Now let’s prove that $F^{-1}$ is an inverse of the maximal-length LSRF $F$. First, the two efficiency requirements:

1. $F^{-1}$ has $O(1)$ space complexity, since it needs to copy only the last bit ($b_n$); the remaining bits can be shifted in-place.
2. $F^{-1}$ has $O(n)$ time complexity, since, like $F$, it executes a single bitwise shift plus $O(1)$ bitwise operations per non-zero coefficient, of which there are at most $n$.

All that remains is to show that $F^{-1}(F(B)) = B$.

$F$ shifts all the bits left by one, and $F^{-1}$ shifts them back right by one, restoring every bit except the first. So we just need to prove that the inverse feedback function restores the first bit; that is, $f^{-1}(F(B)) = b_1$.

For notational convenience, let $F(B) = (b_1', \ldots, b_n')$, then

Thus, $F^{-1}(F(B)) = (f^{-1}(F(B)), \ldots, b_n) = (b_1, \ldots, b_n) = B$ as required. $\blacksquare$

Conclusion

Learning the math behind the LFSR trick in Pitfall! leaves me with even greater admiration for the ingenuity of programmers from that era. There is something deeply satisfying about the way a maximal-length LFSR chooses just the right bits to generate all possible states and how this property guarantees that the last bit preserves enough information to recover the previous state. What an elegant hack!