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.
Thanks! Exactly my thought indeed. Probably now that many people are aware of crypto primitives, permutation boxes and other related tools it is an immediate thought to have, but potentially back then when the game was written it was not so obvious.
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.
Hello, yes the approach is slower in my implementation, but I've the feeling that a suitable F (much simpler) and a low number of rounds could do the trick. However the highlight in the original post was that the ports were not able to reproduce the effect. Given that the ports are AFAIK successive and use higher resolutions, I bet that the CPU was not an issue in that case.
EDIT: I just randomly checked that 4 rounds of F = ((r * 31) ^ (r >> 3)) & 0xff provide more or less the same result. Multiplying for 31 is the same as shifting 5 bits on the left and subtracting the number again, so it's just 4 rounds of bit shifting and xor.
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?
Feistel is a permutation. That means it's a 1:1 mapping between a 16-bit # to another 16-bit #.
You run Feistel for each number 0->65535 (corresponding to the "stage" of the FizzleFade) and out comes the pixel to redden at that stage. Since it's a 16-bit number, some values will fall outside of 320x240 resolution, and you ignore those.
Hello, please check the chillingeffect comment replies, it is basically the same question. There are no cycles since it's not a generator where the previous number is the seed for the next. It's a transformation which is invertible and guaranteed to be unique by the Feistel network structure itself.
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?
So you're basically using what's known as the Luby-Rackoff construction on a provable pseudorandom function to create a pseudorandom permutation. A pseudorandom function generates output that appears random but which can repeat, which is why it cannot be invertible, and is thus unsuitable as a block cipher (you need to be able to decrypt a ciphertext to a specific plaintext).
A pseudorandom function is used as the round function in the feistel network (in the diagram, that's denoted by the F in the middle). You seed the pseudorandom function with a key K. Because the Feistel network successively transforms L and R in each round (L0, R0, L1, R1 and so on), it can be proven that even when the PRF F generates an output that has already been used, the Feistel structure will transform that output differently than the last time it was used.
In other words, the function F is not itself invertible. Invertibility is provided by the surrounding Feistel structure, because if F was already a permutation you wouldn't need anything else. F is only required to generate pseudorandom output, and the Feistel structure's additional logic is what grants invertibility to it. This is the "magic" of the Luby-Rackoff construction, which allows you to take any PRF and transform it into a PRP.
Hello, you don't have to pick an invertible F(), the way the L and R sides are combined together leads automatically to the network to be invertible. This is the magic of Feistel networks, that F() can be as complex as you want and can be not invertible at all.
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.
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 "id software history", you can find it in Origin'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.
It's also possible to use a slower "arbitrary PRNG and bump" 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'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's just less speedy and mathematically interesting to do that.
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.
If want to know more about cool things you can do with shift registers and you'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.
The original GameBoy had a hardware LFSR that could be used to generate white-noise-like sounds. It was often used for "whooshing" effects and also cymbal sounds, such as in the famous Super Mario Land theme: https://www.youtube.com/watch?v=Gb33Qnbw520
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:
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.
Readit News
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.
Wait... what? It took him 25 years! ;)
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...
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.
EDIT: I just randomly checked that 4 rounds of F = ((r * 31) ^ (r >> 3)) & 0xff provide more or less the same result. Multiplying for 31 is the same as shifting 5 bits on the left and subtracting the number again, so it's just 4 rounds of bit shifting and xor.
You run Feistel for each number 0->65535 (corresponding to the "stage" of the FizzleFade) and out comes the pixel to redden at that stage. Since it's a 16-bit number, some values will fall outside of 320x240 resolution, and you ignore those.
Thank you.
So you're basically using what's known as the Luby-Rackoff construction on a provable pseudorandom function to create a pseudorandom permutation. A pseudorandom function generates output that appears random but which can repeat, which is why it cannot be invertible, and is thus unsuitable as a block cipher (you need to be able to decrypt a ciphertext to a specific plaintext).
A pseudorandom function is used as the round function in the feistel network (in the diagram, that's denoted by the F in the middle). You seed the pseudorandom function with a key K. Because the Feistel network successively transforms L and R in each round (L0, R0, L1, R1 and so on), it can be proven that even when the PRF F generates an output that has already been used, the Feistel structure will transform that output differently than the last time it was used.
In other words, the function F is not itself invertible. Invertibility is provided by the surrounding Feistel structure, because if F was already a permutation you wouldn't need anything else. F is only required to generate pseudorandom output, and the Feistel structure's additional logic is what grants invertibility to it. This is the "magic" of the Luby-Rackoff construction, which allows you to take any PRF and transform it into a PRP.
It's also possible to use a slower "arbitrary PRNG and bump" 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'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's just less speedy and mathematically interesting to do that.
0. http://jm.planetarydefenses.net/sense/refs/ref14_golomb.pdf
A pseudo-RNG that cycles through a all elements of a modulo-ring.
Example for a 2^32 bit cycle:
X(n+1) = (a * X(n) + c) mod m
a = 134775813
c = 1
m = 2^32
(quick note: in your source the function is called hilebert instead of hilbert)
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...
> asm mov dx ,[ WORD PTR rndval +2]
> asm mov bx , ax
> asm dec bl
> asm mov [ BYTE PTR y ], bl // low 8 bits - 1 = y
> asm mov bx , ax
> asm mov cx , dx
> asm mov [ BYTE PTR x ], ah // next 9 bits = x
> asm mov [ BYTE PTR x +1] , dl
I don't understand the need for the second asm mov bx , ax : BX is not used afterwards. Same for CX, it is never used.
> uint32_t rndval = 1;
> uint16_t x,y;
> do
> {
> y = rndval & 0x00F; // Y = low 8 bits
> x = rndval & 0x1F0; // X = High 9 bits
Er... no, if you do that, you only get the lowest 4 bits in y, and then you only get 5 bits in x (and not the right ones, of course).
It should be:
And then you have a 'problem' for x, because you must shift it right, otherwise it doesn't fit in a 16-bit variable: So you should just do :I have a feeling the Octane rendering engine uses it too.
It's a good fit for most cases where you want random sampling of a set without replacement.
But then you have to calculate modulus for 200 or 320.
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.
Huh the original implementation seems to have a lookup table instead of that, interesting.
https://github.com/id-Software/wolf3d/blob/05167784ef009d0d0...