5 ms·
Demystifying the LFSR
- codewritinfool 4y agoThis is awesome. Schneier has an excellent chapter on LFSRs for generating pseudorandom sequences with varying lengths.
- Kosirich 4y agoThe content seems great but there is something about that background that made me dizzy when I started scrolling. Anyone else?
- djmips 4y agoPossible solutions: Shrink to fit? Simplified mode?
- wernsey 4y agoLFSR 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 https://fabiensanglard.net/fizzlefade/index.php [1]: https://evoniuk.github.io/posts/pitfall.html https://evoniuk.github.io/posts/pitfall.html edit: formatting
- ElevenLathe 4y agoCame here to say this about Pitfall. Very interesting imagining the author of Pitfall David Crane picking a seed/configuration that would give him the full 255 screens while also providing a gentle enough learning curve on the first few screens! Another fun fact: a very young Jack Black appeared in the Pitfall television commercial: https://www.youtube.com/watch?v=wfLgSdAAHMA https://www.youtube.com/watch?v=wfLgSdAAHMA
- djmips 4y agoThe use in fades goes back at least to early Apple II games where I probably learned about it by reverse engineering a game or reading about it in Nibble Magazine.
- pestatije 4y agoLFSR - linear feedback shift registers
- justinlloyd 4y agoLFSRs 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.
- djmips 4y agoAlso good for those full screen fizzle fade-ins.