FizzleFade

An alternative approach that works for every resolution: <a href="http:&#x2F;&#x2F;antirez.com&#x2F;news&#x2F;113" rel="nofollow">http:&#x2F;&#x2F;antirez.com&#x2F;news&#x2F;113</a>

FizzleFade is also found in Microprose games from the era (e.g. Railroad Tycoon, Civilization), sometimes in full-screen transitions and other times to fade in single sprites. But more relevantly to &quot;id software history&quot;, you can find it in Origin&#x27;s Space Rogue, which John Romero contributed to. A likely possibility is that he picked up the trick on this or a previous project while at Origin.<p>It&#x27;s also possible to use a slower &quot;arbitrary PRNG and bump&quot; scheme that tests the VRAM for the desired values(e.g. if it were a sprite, by running the blit at that pixel address and testing) and walks forwards or backwards until an unset value is found. If the walk can be done fast enough, it&#x27;ll execute at the same framerate as an LFSR cycle-length fade. It can be further supplemented with an estimation heuristic or a low-resolution map to generate unique patterns. It&#x27;s just less speedy and mathematically interesting to do that.

If want to know more about cool things you can do with shift registers and you&#x27;ve never heard of Solomon W. Golomb, check out Shift Register Sequences (intro at [0]). Most of our fundamental telecommunications is possible because he solved the mathematics involved.<p>0. <a href="http:&#x2F;&#x2F;jm.planetarydefenses.net&#x2F;sense&#x2F;refs&#x2F;ref14_golomb.pdf" rel="nofollow">http:&#x2F;&#x2F;jm.planetarydefenses.net&#x2F;sense&#x2F;refs&#x2F;ref14_golomb.pdf</a>

The original GameBoy had a hardware LFSR that could be used to generate white-noise-like sounds. It was often used for &quot;whooshing&quot; effects and also cymbal sounds, such as in the famous Super Mario Land theme: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=Gb33Qnbw520" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=Gb33Qnbw520</a>

Related: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear_congruential_generator" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear_congruential_generator</a><p>A pseudo-RNG that cycles through a all elements of a modulo-ring.<p>Example for a 2^32 bit cycle:<p>X(n+1) = (a * X(n) + c) mod m<p>a = 134775813<p>c = 1<p>m = 2^32

&gt; asm mov ax ,[ WORD PTR rndval ]<p>&gt; asm mov dx ,[ WORD PTR rndval +2]<p>&gt; asm mov bx , ax<p>&gt; asm dec bl<p>&gt; asm mov [ BYTE PTR y ], bl &#x2F;&#x2F; low 8 bits - 1 = y<p>&gt; <i>asm mov bx , ax</i><p>&gt; asm mov cx , dx<p>&gt; asm mov [ BYTE PTR x ], ah &#x2F;&#x2F; next 9 bits = x<p>&gt; asm mov [ BYTE PTR x +1] , dl<p>I don&#x27;t understand the need for the second <i>asm mov bx , ax</i> : BX is not used afterwards. Same for CX, it is never used.<p>&gt; uint32_t rndval = 1;<p>&gt; uint16_t x,y;<p>&gt; do<p>&gt; {<p>&gt; y = rndval &amp; 0x00F; &#x2F;&#x2F; Y = low 8 bits<p>&gt; x = rndval &amp; 0x1F0; &#x2F;&#x2F; X = High 9 bits<p>Er... no, if you do that, you only get the lowest <i>4</i> bits in <i>y</i>, and then you only get <i>5</i> bits in <i>x</i> (and not the right ones, of course).<p>It should be:<p><pre><code> y = rndval &amp; 0x000000FF; &#x2F;&#x2F; Y = low 8 bits </code></pre> And then you have a &#x27;problem&#x27; for x, because you must shift it right, otherwise it doesn&#x27;t fit in a 16-bit variable:<p><pre><code> x = rndval &amp; 0x0001FF00; &#x2F;&#x2F; X = bits 8 to... 16 &gt; 15, irk </code></pre> So you should just do :<p><pre><code> x = rndval &gt;&gt; 8; &#x2F;&#x2F; X = bits 8 to 17, in their right place</code></pre>

I used LFSR to render the red grading in this little experiment: <a href="https:&#x2F;&#x2F;youtu.be&#x2F;fUpUrpHLUxo" rel="nofollow">https:&#x2F;&#x2F;youtu.be&#x2F;fUpUrpHLUxo</a> .<p>I have a feeling the Octane rendering engine uses it too.<p>It&#x27;s a good fit for most cases where you want random sampling of a set without replacement.

&gt; Since 320x200=64000, it could have been implemented with a 16 bits Maximum-length register.<p>But then you have to calculate modulus for 200 or 320.

It never ceases to amaze me how many of the older games were implemented as circuits first, and then translated to code. Makes you really appreciate how far we&#x27;ve come, and what sort of background that generation of developers had.

I didn&#x27;t quite understand why this is guaranteed to reach every pixel coordinate? Is there something inherent about LFSR that generates complete sequences within the cycle? So elements are never repeated or omitted?

I have the feeling that knowledge about bits is lacking by a lot of younger coders. And I also think this is what causes bloatware.<p>CPUs are powerful enough to use a naive fade transition. But coders who are aware of the internal workings can make it even faster on todays hardware.<p>Great article and imho still relevant on todays much more powerful computers.

Cool, I knew that LFSRs were used in ciphers. I was not aware that they were also useful for implementing old-school graphical effects.<p><a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear-feedback_shift_register#Uses_in_cryptography" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear-feedback_shift_register...</a>

As interesting as this article is, I would also love to know where and how the author of the code learned about LFSRs!<p>I wonder if they rediscovered the algorithm, knew they were implementing a LFSR or even just solved a particular instance of the problem without ever realizing they were writing a LFSR.<p>I learned about LFSRs a while ago and wrote a small implementation for ruby as an exercise [1] using a Wikipedia page as reference [2]. But Wolfenstein 3D was released in 1992, I&#x27;m sure back then information was a lot harder to find online!<p>1: <a href="https:&#x2F;&#x2F;github.com&#x2F;EmmanuelOga&#x2F;lfsr" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;EmmanuelOga&#x2F;lfsr</a> 2: <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear-feedback_shift_register" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Linear-feedback_shift_register</a>

Related: <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;10054732" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;10054732</a><p>Fundamentally you want to make a random permutation, but not spend linear memory on it, as you would if you did it by shuffling.

What properties are required in an LFSR that it covers the whole range (2^n-1 numbers) before returning? Or are such configurations found experimentally?

Note that you can (quite obviously) use this to fade from one image to an other by writing the color of the next image instead of just &quot;red&quot;.

For a Javascript implementation, check out <a href="https:&#x2F;&#x2F;github.com&#x2F;fisch0920&#x2F;dissolve-generator" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;fisch0920&#x2F;dissolve-generator</a><p>This version is based off of the article A Digital Dissolve Effect by Mike Morton &quot;Graphics Gems&quot;, Academic Press, 1990 (<a href="http:&#x2F;&#x2F;dl.acm.org&#x2F;citation.cfm?id=90821" rel="nofollow">http:&#x2F;&#x2F;dl.acm.org&#x2F;citation.cfm?id=90821</a>)

as a &quot;senior&quot; business programmer with non-engineering studies (I have a deegree in byology), I&#x27;m feeling an impostor reading this and admitting that I&#x27;m unable to understand basically everything... even <a href="https:&#x2F;&#x2F;bigmachine.io&#x2F;products&#x2F;the-imposters-handbook&#x2F;" rel="nofollow">https:&#x2F;&#x2F;bigmachine.io&#x2F;products&#x2F;the-imposters-handbook&#x2F;</a> not helped too much

Fascinating. Who wrote the original ASM? Carmack?

<i>My assumption is that LFSR literature was hard to come across in 1991&#x2F;1992 and finding the correct tap for a 16 bit maximum length register was not worth the effort.</i><p>I guess it might be more due to the lack of overlap between the problem domains --- LFSRs were known since the late 60s in relation to CRCs and other error-correcting codes. <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Gold_code" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Gold_code</a>

Still a good trick today. <a href="https:&#x2F;&#x2F;github.com&#x2F;silentbicycle&#x2F;greatest" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;silentbicycle&#x2F;greatest</a> just added a feature of shuffling test executions into random order, after I suggested the general idea in a Twitter convo. (I think it uses LCGs instead of an LFSR.)

Stupid question: Why can&#x27;t you just take an array of all the pixels, randomize it and then iterate it to draw?

The Atari 2600 video hardware used these all over the place instead of traditional counters. It saved them a lot of gates that counters would require.

i am interested to know the particulars of any routines people have for reading and reviewing a codebase, as the author talks about doing in his spare time. do you take notes? add comments? step through with a debugger?