Hardware Linear Feedback Shift Registers in the NES
This is going to be a bit of a tangent, but djc and jauricchio both nerd sniped me and I had to look into some things.
Picking up from where we left off, NES Tetris uses a Linear Feedback Shift Register as its Pseudo Random Number Generator. This particular LFSR, as the cool kids call it, will generate the exact same stream of 32,767 16-bit numbers every time the game is turned on. That’s just under half of all of the possible 16-bit numbers. We’ll see that this isn’t a problem for Tetris, but it could be in other situations.
An XOR-based LFSR will get stuck forever if it’s set to 0 because it will never generate a 1 bit to shift in.
It’s possible to create 16-bit LFSRs that will generate every number except 0 but you’ll need 4 taps instead of 2. Taps at bits 0, 2, 3, and 5 will do it. There’s a neat reference list for setting up these kinds of maximal length LFSRs, but note that it numbers bits from the left instead of the right.
LFSRs are great because they’re fast and require very little storage. And while the Tetris PRNG is written in software, they’re also very easy to implement in hardware. The NES has two hardware LFSRs that I’m aware of.
The first one lives in the 2A03/7 audio processing unit (APU). The noise channel uses a 15-bit LFSR seeded to
0x0001 on startup with taps at bits 0 and 1 by default. This configuration will cycle through every 15-bit number except
Why in the world would you want to feed random data into a sound mixer? The sound usually comes out as a sort of static, and with some careful management of pitch and volume you can turn that into some pretty decent percussion sounds. Though the NES APU could play samples through the delta modulation channel, waveforms take up a lot of cartridge space and playback requires a lot of work (filling the one byte DMC sample buffer can stall the CPU for up to four cycles). Using the non-sample channels is a lot more efficient.
That is to say “Korobeiniki” is the official Tetris theme song, as the Tetris Company requires that every officially licensed Tetris game include it.
In any case, here’s an example of how it sounds. This is NES Tetris’s “Music A”. Even though “Korobeiniki” is more or less the official Tetris theme song, it doesn’t appear in the NES version. Tchaikovsky’s “Dance of the Sugar Plum Fairy” was the default song instead.
Here’s the same song but with only the noise channel enabled and normalized. It’s a bit sparse in isolation, but it adds a lot to the final composition.
Here’s another example. I know that Rad Racer is more or less the iconic NES racing game, but I’ve always preferred the style of Al Unser Jr.’s Turbo Racing. Nothing feels quite the same as taking hairpin turns as the sun sets above Österreichring and the sky turns beautiful colors. But check out BGM “C”:
It sounds like there’s a whole damn drum set in there!
There’s also a second noise channel mode that will tap bits 0 and 6 instead of 0 and 1. Depending on the value of the register when this Mode flag is turned on, the register will generate either a 31 or 93 value cycle. The effect is more like a metallic buzz than static, and I can’t think of a better example than Mega Man 2’s Quick Man stage.
There’s another hardware LFSR in the 10NES lockout chip. Yes, even consoles in the 80s had lockout hardware. Nintendo’s public motivation was to prevent third parties from manufacturing game cartridges without Nintendo’s approval. When the NES was released in 1985, the videogame crash of 1983 was fresh on everyone’s minds. From 1981 to 1983 video game revenue dropped a terrifying 97%, and entire divisions and companies were devastated.
Believing that bad third party software was a primary factor in the crash, Nintendo wanted final approval on every title shipped for their hardware. Atari had previously tried to prevent Activision from developing third party software for their consoles through legal channels but weren’t successful. Nintendo took another approach by adding a lockout chip to the console that would reset the CPU if a similar chip in the cartridge didn’t produce exactly the correct data stream for the entire duration the unit was powered.
It also doesn’t explain how Hook was released. “Nintendo Seal of Quality” my foot.
I think a major motivation for the lockout chip really was about enforcing third party title quality. Nintendo also limited licensees to five titles per year for ostensibly the same reason. But I’m sure the license fees Nintendo collected on every third party title didn’t hurt, and the restrictions also ensured first party titles wouldn’t be lost in a flooded market. In any case, the lockout chip exists, and probably not for the same reasons that current consoles include DRM systems to reduce piracy.
XNOR is like XOR but backwards; it outputs 1 if and only if the two inputs are the same. A nibble is four bits, or half a byte.
The 10NES uses an LFSR as its program counter. The 10-bit register has taps at bits 0 and 1 and shifts in the XNOR of the taps each cycle. At first I thought this was done to obscure the inner workings of the chip to make it harder to reverse engineer, but now I think the reason is more pragmatic. An LFSR uses far fewer transistors than a normal counter. Given the size of the chip (a 4-bit microprocessor with 32 nibbles of RAM and only 512 bytes of ROM), this would be a priority. The chip would be included in every cartridge, so keeping it physically small and cheap to manufacture would be important.
In the end, the lockout chip didn’t stop third party development. Color Dreams, AVE, and other third party manufacturers included a chip that would send a voltage spike to the lockout ship, effectively “stunning” it. I guess there’s some truth to the warning that unlicensed hardware could damage the system.
Tengen’s approach was something else entirely, though. After failing to reverse engineer the chip to produce their own, the Atari subsidiary acquired a copy of the code from the U.S. Copyright Office claiming it was needed to prepare defenses for a legal case! Their “Rabbit” chip appeared in cartridges soon after, and although they ultimately used different microprocessors and code they generated a compatible data stream that would be accepted by the 10NES.
This was not the only legal conflict Nintendo and Tengen had. Tengen also developed, marketed, and sold a Tetris game for the NES—for about four weeks. But that’s another story for another time.
Let’s get back to Tetris randomizers.
- "APU Noise". (wiki.nesdev.com)
- "APU DMC". (wiki.nesdev.com)
- Segher. "The weird and wonderful CIC". (hackmii.com)
- Sheff, David. Game Over: How Nintendo Conquered The World. Vintage, 1994. ISBN 978-0679736226.
Many thanks to djc for providing a lot of the insight and motivation for this post.