Demystifying the LFSR (opens in new tab)

LFSR is in my vocabulary because of these two articles:

* Fizzlefade by Fabien Sanglard [0] that explains the fade to red effect in Wolfenstein 3D

* How Pitfall Builds its World [1] that explains how the original Pitfall on the Atari 2600 managed to have 255 unique screens despite severe constraints on the storage space available (it used a maximal length 8-bit LFSR that was also invertible so that you can go back to previous screens).

[0]: https://fabiensanglard.net/fizzlefade/index.php

[1]: https://evoniuk.github.io/posts/pitfall.html

edit: formatting

LFSRs were used in game development for many years as "random" number generators that were guaranteed to always produce a series of "random" numbers that returned every value within a range precisely once. It was a way to save memory when you didn't have enough RAM to store the entire list of randomized numbers. It was also used in level generation, e.g. Pitfall, and other games. I used an LFSR in a couple of games for word generation and level layout, which was especially important when you only had 6KB of storage total.

This is awesome. Schneier has an excellent chapter on LFSRs for generating pseudorandom sequences with varying lengths.

The content seems great but there is something about that background that made me dizzy when I started scrolling. Anyone else?

LFSR - linear feedback shift registers