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.

>This is a good post, kudos on writing it up so quickly!

Wait... what? It took him 25 years! ;)

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.

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.

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

It might help if you look at a diagram such as this one to understand exactly what the code is doing: https://en.m.wikipedia.org/wiki/Feistel_cipher#/media/File%3...

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.

A permutation like that reduces biases in the output