FizzleFade (opens in new tab)

This is a good post, kudos on writing it up so quickly! In fact, the first thing I thought of when I read this post on HN was, "Well why not use a pseudorandom permutation instead of a pseudorandom function, this way we efficiently fill all pixels without first checking if they're red?"

Being that a feistel network is a pseudorandom permutation, this fulfills the need (and in my opinion, even more elegantly than a LFSR). For even better performance you could use AES as the PRF, especially if users have AES-NI instructions available for acceleration. Then use a basic Feistel network for the PRP.

> A good tool to have in a programmer mental box.

Relates well to Shannon's problem solving process' [1] "Step 2: Fill your 'mental matrix' with solutions to similar problems."

[1] http://www.businessinsider.com/engineer-claude-shannon-probl...

Always love seeing applications of Feistel cipher. Used it with AES as the PRF for implementing FPE in legacy systems.

Just want to note that this approach (regardless of PRF) probably wouldn't have worked in 1991. Recomputing the cipher state at every pixel is probably ~10x slower than the single shift + xor in the iterative LFSR approach.

You state that a Feistel network has the property that each input value is mapped to a different output value, but how do you ensure that there isn't some cycle whose length is shorter than that of the size of the set of possible inputs? That is to say, what guarantees that every pixel is reached at least once?

How do you pick and test the parameters in the F() transformation to guarantee that "Every input 16 bit input will generate a different 16 bit output?" your comment says they were picked at random... was that after some iterations? how did you know when you had a proper transformation?

Thank you.

If you'd like to see it in action, I made a CodePen to demonstrate antirez's pixel dissolve over a Castle Wolfenstein 3D scene: https://codepen.io/jones1618/pen/YxRVpo

"just scramble the address" was the solution that immediately came to mind. feistelNet looks a little heavy though, is it really necessary? would you not get the same effect from straight xor on the x and y coords?

Couldn't that algorithm equally be used to circumvent the problem of slowing down a file systems the more the available space fills up? I imagine this would be beneficial when storing but detrimental when reading data.

I remember seeing it in a variety of mid-80's Commodore 64 games, where it ran at full speed and looked fantastic. I always wondered how it worked.

I'm 95% sure I've seen this effect on a Spectrum which would likely predate even Space Rogue - I'd guess that would be an LSFR fade because "arbitrary PRNG and bump" would be hella clunky given the Spectrum's screen layout.

For more technical details on the exact LFSR used, there's this: http://belogic.com/gba/channel4.shtml

Ditto with the NES. It actually had two possible tap configurations with different sequence lengths, so that they have slightly different sounds to them.

My approach would be something like this, but with a very "poor" generator with the parameters a=81007, c=0 and m=2^17. This approximates a low discrepancy sequence (additive recurrence with alpha=1/golden ratio). Then I would calculate x and y values using the hilbert curve and the calculated pseudorandom number as the index (more precisely two Hilbert curves next to each other, so it covers a 512x256 rectangle). On today's CPUs it can be calculated quite fast (shameless selfplug: https://github.com/leni536/fast_hilbert_curve). I suspect that the resulting pattern on the screen would be less random looking, but more uniform without any obvious pattern.

Indeed; and careful selection of parameters for the LCG can truncate the ring to most arbitrary powers of two. And if you're willing to live with slight inefficiency (no more than twice as much work), an arbitrary modulo ring (shuffled sequence) can be produced by creating slightly larger range and skipping values that are outside the range.

This is a question I asked on SO some years ago relating to this problem - producing a shuffled range of numbers without allocating an array:

https://stackoverflow.com/questions/464476/generating-shuffl...

I thought of this too, but it might be a bit more taxing on an old CPU to do excess multiplication than a simple XOR and test.

Looks like the author fixed the C translation following your comments:

  y =  rndval & 0x000FF;  /* Y = low 8 bits */
  x = (rndval & 0x1FF00) >> 8;  /* X = High 9 bits */

However, given that the assembly is verbatim from id-software's git, I guess those extra instructions are part of history now.

except the pixels are in a linear framebuffer, the fizzlePixel(x, y) function has a multiplication by 320 in it to calculate the address in the buffer.

so you could skip both the modulo and the mul if you go straight for obtaining a random shuffled framebuffer index.

unless maybe fizzlePixel does additional bookkeeping for some purpose.

Yeah this wasn't covered well in the article.

Go back to the article and look at the section just below the first mention of Maximum-Length LFSR.

Take a look at that list of numbers and notice something; every number from 1-15 is output once and only once.

That's a property of Maximum-Length LFSRs; they output each number in their range once and only once.

So, for example, a 17-bit Maximum-Length LFSR will output every number from 1-131071, just in random order.

The Wolfenstein code separates the output of the LFSR into X and Y coordinates. Since the LFSR will visit every possible number exactly once, it will visit every possible combination of X and Y coordinates exactly once.

You can look at the 4-bit Maximum-Length LFSR again. Split each number it outputs into 2-bit X and Y:

   0001 | 0,1
   1000 | 2,0
   0100 | 1,0
   0010 | 0,2
   1001 | 2,1
   1100 | 2,0
   0110 | 1,2
   1011 | 2,3
   0101 | 1,1
   1010 | 2,2
   1101 | 3,1
   1110 | 3,2
   1111 | 3,3
   0111 | 1,3
   0011 | 0,3

You'll see that it hits every point on a 4x4 screen exactly once, in random order.

The caveat is that it doesn't seem to hit 0,0. This is because an LFSR can't go to 0, otherwise it gets stuck there. However, I believe the ASM code was incorrectly translated by the article author. For example the author seemed to forget to translate the "dec bl" instruction into the C equivalent, which would subtract 1 from the y coordinate and allow visiting 0,0.

The cycle length is 2^17-1 = 131071. The number of pixels is 320*200 = 64000. Therefore each pixel is hit at least once.

The authors likely used 17 bits instead of 16 because then the x and y coordinates can be obtained via masking rather than modulo (8 bits -> 256 values < 320 pixels).

I was wondering the same thing myself. I'm guessing they tested it and found that it hit every coordinate at least once and said "good enough". Meaning, I don't think it's guaranteed, they just picked one that did.

The interesting thing is that you're guaranteed to always have a different number because otherwise the cycle would restart. So you just need to find a sequence that's long enough.

Why? I mean if you look at the majority of work that programmers do today - frontend/backend web development and apps, there is no need to have knowledge about bits.

In fact, if I see someone using binary operators in languages such as Java,JS,Ruby etc... I'll immediately consider it bad code, regardless of context - it's just not the right tool for the level of abstraction in these languages.

The fact is that in these products (frontend/backend web development and apps) the performance profile is dominated by bad algorithms, wrong data structures, slow libraries, missing db indexes etc... which knowledge about bits help absolutely zero with.

Large binaries are also not dominated by code you write but rather by using too broad libraries or simply from huge assets.

The only thing I'd consider knowledge of bits to be of any help to a run of the mill developer these days is the knowledge that floating point numbers don't multiply/divide well - but that kind of knowledge can be imparted without really diving into how bits work.

I agree. Unfortunately, it feels like there is so many people out there lacking the fundamental engineering background to write software.

I once spent an hour "optimizing" a piece of code that ran in 15 minutes, which tested an embedded system. The resulting code ran in 4 seconds. The root cause was a complete misunderstanding of how microprocessor interrupts work.

I spent a week re-writing a 4000 line C-function, which ended up to be around 50 lines of code, doing the same thing. The root cause was a complete misunderstanding of how state machines should be constructed.

These types of rookie mistakes by itself don't worry me. But the "trend" seems to be that young coders graduate with less knowledge about the underlying hardware on which their software will run.

I feel like just like Mathematics and Physics, low level programming / microprocessors / computer architecture classes should be part of many university curriculum. (Oh and I think they should teach about version control systems in college as well, but that's the topic of another story!)

You should have said "thinking outside of the abstraction" instead. Bits are implementation details. The very knowledge of linear-feedback shift register is essential in this particular example.

> 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.

Not really. No one would do the fade transition---or more accurately, the regional alpha blending with a fixed color---in CPU nowadays exactly because GPUs are much more capable in that job, and such a job is actually fairly easy in most abstractions used because it is an integral part of UX and whatever. The ability of leveraging all resources and determining their efficient utilization is a key.

    > 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

From a management perspective, I wonder if people find older developers miss obvious solutions that involve throwing small amounts of money and/or hardware at business problems, and instead turn to "clever" solutions that are costly in terms of extra developer time needed for developer and maintenance.

Certainly when running technology in an SME I found my gut feelings about many cost/benefit questions were often invalidated by the ever-decreasing cost of computing power, both in terms of physical hardware and cloud resources.

Anecdotal evidence - I cut my teeth on C and a dabble of asm as a kid (even writing z80 opcodes directly for fun!). I vaguely remember wrangling bits to drive logic. I also wrote webpages as Apache C modules with binary logic to parse requests :D

That was a long time ago in tech terms (~15 years). In the intervening gap I spent most of my time in scripted languages (as3, c#, etc.).

Result? I don't know how to wrangle bits anymore. The added speed increase I'd add almost definitely isn't worth it (for example, flash and unity games, web services, etc.). That doesn't mean it isn't worth it for the end product - I rely on Unity, Adobe, Google, etc. to worry about those optimizations so I can stand on their shoulders and benefit.

But in terms of cost/benefit, getting into that stuff myself (again) just didn't make sense for most of my professional needs.

Recently, I started helping out data engineering teams improve performance of their big data processing pipelines.

Man, was I shocked. Very smart, highly educated, mid-level and even senior software engineers seem to know very little about bits these days. When they'd run into a memory issue, their natural response was to just spin up a few more servers and throw another terabyte of memory at the problem. Makes sense, I guess - until their CFO saw their pretty exponential curve in infrastructure costs.

there's still the whole other world of coders doing "embedded" software. They are still happily bit fiddling in blissful ignorance of web development fads. I only do a little bit these days, but one of the micros I program only has 20bytes of RAM to work with and requires bit magic. :)

I think that working with bits is still a standard part of a Computer Science program. I took a class last year dealing with logic gates and bits. I also have a couple of friends that went to other schools that also took the same kind of class.

While the information is nice to know and helps every once in a while (like understanding these articles better), I just don't think it's nearly as necessary to know as it used to be.

I find it incredibly hard to believe that any young code with a freshman level Computer Science education would now know bits inside and out. Then again, I went to college 10 years ago and I went to one of the better schools so maybe they don't teach that anymore?

I also acknowledge that with the invention of "code bootcamps" a lot more coders have never been to college than before. Effectively, I think, creating two types of programer that has nothing to do with age. Both types have their applications they are good at.

> 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.

I don't think this is true. I used to code in assembly and knowledge of bits is largely irrelevant the vast majority of the time now outside of graphics algorithms and low-level number crunching. Algorithmic growth and memory usage are always going to be important though.

I'm a low-level programmer and it's the first time I come across the linear-feedback shift register. I would say it's rather a part of digital circuits design.

Now, when FPGAs become more and more popular, people will be forced to learn VHDL languages and then different lesser-known techniques will surface. (It's a naive prediction, I know.)

Agreed. There's plenty of applications even today where this kind of mentality is helpful (embedded or real-time systems, for example).

It's not even necessarily about squeezing cpu or memory performance, but finding a solution that is "native" to how computers work: binary bits.

> I have the feeling that knowledge about bits is lacking by a lot of younger coders.

I optimize for what they pay me for now. I also optimize for what I think they will pay me in future.

The super efficient C solution might be an salary dead-end when management also accepts a huge Hadoop solution :)

Agreed. I like this list of somewhat common bit hacks (the popular Bit Twiddling Guide): graphics.stanford.edu/~seander/bithacks.html

I dont particularly care for your generalisation about younger coders, as a younger coder. There are many of us who do care about the low level details of our code, and take extra care to write good performant code. To make a generalisation about "older" programmers - I have the feelings that older coders are stuck in their ways and aren't willing to change their behaviours, and when a younger coder tries to suggest improvements, they're hand waved away because we have less experience.

CSS[1] was the defacto 'DRM' back in the day, which used two LFSRs for 40-bit encryption. Apart from being able to brute force it today, there are many other ways to break it[2].

Now the DRM on DVDs/BluRays is AACS[3], which uses AES. You might also recognise it from the 'copyrighted numbers' fiasco[4]

[1]: https://en.wikipedia.org/wiki/Content_Scramble_System

[2]: https://en.wikipedia.org/wiki/Content_Scramble_System#Crypta...

[3]: https://en.wikipedia.org/wiki/Advanced_Access_Content_System

[4]: https://en.wikipedia.org/wiki/AACS_encryption_key_controvers...

Similar concepts are used for raid 6 parity (LSFR + Galois Fields). A pdf I found describing raid 6 parity describes the field and LSFR use and some background. https://www.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf

(I took at stab at implementing them awhile back as an experiment. https://github.com/jimktrains/r6parity)

I'm not sure I'd call Wolfenstein 3D "old-school".

But then I did start with computers in 1980.

I did something like this in Go: https://godoc.org/github.com/lukechampine/randmap/perm

Galois generators of the sort in the article can be described naturally using the finite field Z_2[x]/p(x), that is, polynomials with coefficients taken mod two, where we consider polynomial p(x) is equivalent to zero. If p has degree n, this field has 2^n elements - the 2^n polynomials with degree less than n are distinct, but x^n is equivalent to x^n-p(x), which has degree less than n, so everything with higher degree is already accounted for. This is, however, only actually a field if p is irreducible.

Now we can describe the generator as multiplication by x, where the leftmost bit is the lowest power, since every bit moves right except for the rightmost, which corresponds to turning x^n into x^n-p(x) as above. The cycle length is the smallest k such that x^k is equivalent to 1. Now, an interesting property of finite fields is that there is always a "primitive" element, the powers of which generate every other element (you can prove this inductively by counting elements z such that z^d = 1 for different d, and noting that z^d-1, as a degree d polynomial, has at most d roots in the field). If x is primitive, it will cycle through all other values before reaching 1. In the specific case of n=17, however every element of the field is primitive (this is easy group theory, the nonzero elements form a group under multiplication, and that group has a prime number of elements).

This means any degree-17 polynomial which is irreducible in Z_2[x] will give rise to a full-cycle-length generator. Luckily, finding an irreducible polynomial isn't too hard - of the 2^16 options (ignoring the ones without a constant term, which are obviously divisible by x), 7710 are irreducible by my quick Mathematica computation.

A pdf I found describing raid 6 parity describes it. https://www.kernel.org/pub/linux/kernel/people/hpa/raid6.pdf That PDF + the sibling comment should help in understanding.

(I took a stab at implementing it in C a few years back. https://github.com/jimktrains/r6parity)

There's a complete theory based on primitive polynomials on Z/2Z. Check any article on linear PRNGs for references.

"Experimentally" will work only with ridiculously small state spaces.

I think some number theory should give you the answer. Look for something about cyclic groups and their generators..

It's very simple. Basically you need to cycle through all n-bit integers (except zero) in a random-looking way, and it turns out there's an arcane-ish bit twiddling operation that will do it when applied repeatedly. The reason it works can be explained with some undergrad math. You don't need to know these things for business programming but they are fun to read about.

Another idea in a similar vein is https://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dither... It converts an image with many shades of gray to an image with only black and white pixels. The algorithm is dead simple, but the results are surprisingly convincing.

Don't worry, it's rare to see manual bit level optimization these days as compilers are quite smart in optimization. It's kind of lost art. I work with embedded systems and even there bit manipulation is mostly used for controlling MCU registers, not writing optimized code. If you still want to understand such manipulations, it's mostly boolean algebra of which there's plenty of literature to choose from.

The article skipped most of the description of what LSFR's actually do, and the linked Wikipedia article is surprisingly unhelpful. After you read the value of the registers, they all get shifted one bit to the right. The last value simply falls off and is discarded. To generate the value for the new leftmost bit, which is now "empty", you XOR some of the other bits together. Then you read the new value and start over. Eventually the values will repeat, and the goal is to find a configuration that will give you the longest cycle before repeating.

Because with ideal packing it would take 150 kB (320·240·log2(320·240)/8). Wolf3d needed 640 kB of RAM and using quarter of it just to display death animation wouldn't be a good idea.

because this would take a huge amount of memory. something like xy(sizeof x + sizeof y). not only memory wasn't available cheaply at the time. it would be slow to generate, write to memory, then fetch back to draw.

This was written in assembly and to do that you'd have to make a new register of all the references while randomizing. Your approach works great in modern, high level languages where there's no issue copying an array in memory and calling array_shuffle or something, and doubling the memory requirement for the effect is no problem. This approach however seems to only require 17 bits of additional memory.

1) That's a lot of memory

2) Accessing memory is the slowest thing you can possibly do on a computer, other than IO

Given you are a seasoned programmer, most of the code written in familiar language should be obvious just by skimming it. But when it comes to a short and "smart" algorithms, especially including bit manipulations, I still find pen&paper the best tool to find out what's really happening.