Random Number Generation 1: Introducing the LFSR

True random number generation is, of course, impossible. However, it's quite possible to pseudo-randomly generate numbers that are good enough for console gaming purposes. One common algorithm for this is what's known as a linear-feedback shift register, or LFSR.

In short, what a proper LFSR does is to take a range of numbers and dole them out one by one in a pseudo-random order, without repeating any. Once it's output all the numbers, it starts over. As you can probably guess, for the best pseudo-randomness, we'll want an LFSR with a wide range of numbers, and which jumps around a lot as it churns through them. To achieve this, we'll use a few layers of misdirection while we set up our LFSR.

The concept of a shift register comes from digital circuitry. In essence, it refers to a series of stable circuits that are chained together from output to input, so that changing the value of one circuit causes the next one to change, and so on down the line.

That's a (massive) oversimplification, but for our purposes, what's important is this idea of cascading output to input. Basically, we can start with a value, mess with it somehow, and the result of that operation becomes the new starting value for the next step in the chain—and on and on.

You might be be starting to see how this could be useful for pseudo-RNG. If we can come up with an algorithm that cycles through 1.) a huge set of numbers, 2.) in an unpredictable way, 3.) without repeating any of them before it starts over, we could get a pretty good approximation of randomness. And that's what our linear-feedback shift register will do.

One last thought before we look at the code: since the output of each step is the input of the next step, that means an LFSR is deterministic. Given a certain input, we know exactly what the output must be.

In other words, if we always used the same "seed" for our pseudo-RNG algorithm, it would always produce the same "random" numbers in the same order. That's no good! We want the seed itself to be as random as possible, since our LFSR really isn't random at all: it's just a really big, complex—but predictable—shuffler.

All pseudo-RNG relies on what are called "seed values": starting values that the pseudo-RNG algorithm uses as a launchpad for generating its seemingly random output. Given the same seed, a pseudo-RNG algorithm will return the same output every time. Thus it's important that we make our seed as random as possible.

To begin, we'll reserve space for two sixteen-bit seeds in the zero page.

Now, how do we make these seeds the randomest they can be? We start by turning to the most unpredictable part of any game: the player. Pretty much any NES game will implement a timer as part of its basic code. We can use this timer to count some arbitrary player-based time—say, from when the title screen loads until the player starts the game—and use that value to seed our RNG.

It would be nice to add some extra (pseudo-)randomness to our timer seed, though. After all, our clock is only sixteen bits wide. So we'll use a quick, simple LFSR to scramble the timer value before we actually store it in the seed that intializes our true RNG algorithm.

Let's take a look at the entire sequence of events that initializes our RNG. This code could be placed anywhere you want to initialize the RNG seed, as long as the timer is running.

The first half is pretty straightforward: we load the contents of the timer into the two bytes of seed0 and run the scrambleSeed subroutine (which we'll look at momentarily—it operates on seed0).

But what about that SBC opcode? That's a Subtract With Carry, which subtracts the second byte of our timer value from the result of scrambleSeed, which is in the A register. It's just a way of adding a little more unpredictability to the proceedings. That result is is stored in the first byte of seed1, scrambleSeed is run again on seed0, we subtract the first byte of the timer because why not, and the final result is saved in the second byte of seed1.

All in all, then, seed0 winds up holding the contents of the timer having been run through scrambleSeed twice. While we were doing that, we stored an altered version of the output of the first run in the first byte of seed1, and an altered version of the second run's output in the second byte of seed1. Whew!

All right, the last thing we need to do in this step is look at the scrambleSeed subroutine. It is itself an LFSR algorithm, but it's not a very complex one—that is, it doesn't generate a whole lot of randomness. Remember, all we're doing right now is creating a nicely scrambled seed value for our real LFSR, which we'll see in a moment.

The best way to explain this code is to step through an example, which we'll do momentarily, but the short version is essentially: it takes the two bytes of seed0 and noodles around with them in a predictable way.

All right, on to the example! Remember that when the subroutine begins, seed0 and seed0+1 have been initialized with the bytes from timer and timer+1. As we step through, I'll call out each register or memory value when it changes.

We start by saying, for the sake of example, that seed0 is 01011101 and seed0+1 is 10100010.

Load 01011101 from seed0 into A.

This Logical Shift Right changes A to 00101110 and sets the Carry Flag to 1.

Rotate Left the contents of seed0+1. seed0+1 becomes 01000101 and the Carry Flag is set to 1.

BCC means Branch if Carry Clear—in other words, jump to the label @noeor if the Carry Flag is 0. In this case, the Carry Flag is set (it's equal to 1) so the branch does not occur.

What's this all about? Well, it's pseudo-random. Based on the results of the previous ROL operation (and thus the starting contents of seed0+1), this BCC will fire more or less half the time, meaning the next line of code will be skipped about half the time.

This line (which only runs about half the time thanks to the BCC above it) performs an Exclusive Or on the contents of A. If it runs, it'll shuffle up some, but not all, of the bits. Since it did occur in our example, A now equals 10011010.

The contents of A are stored back into seed0, making it, in our case, 10011010.

We scramble A one more time by Exclusive Or'ing it against seed0+1, changing A to 11011111. Note that within the context of the subroutine itself, this move is meaningless. It only makes sense when we remember that after we exit the subroutine, A is immediately used to set seed1. It's a good reminder that in the world of assembly, the registers are often used to return values in ways that aren't immediately obvious to those of us used to higher-level programming languages.

And we're out!