Earlier quoted context omitted.
Why not `x / 16`?
Integer division will give a rounded result instead of floor
I think they're going for the ceiling here, not the floor. Truncation of positive values should be the same as a floor function.
FizzleFade
111–120 of 182 posts
Re: FizzleFade
#112I didn'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?
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).
Re: FizzleFade
#113I didn'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?
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
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.
Re: FizzleFade
#114Earlier quoted context omitted.
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, wh…
> lacking the fundamental engineering background to write software.... young coders graduate with less knowledge about the underlying hardware on which their software will run. There's a lot of software being written in Excel macros and Wordpress web development. These tools actually get work done - they automate things that were not automated before, they publish things that were not published before, and they gener…
I agree with you for the most part. Writing poor code is fine if the code will only be run for a limited use case. But much of the power of software comes from its potential to be easily reusable and extendable. This potential is thrown away when people write poor code. At some point, it becomes detrimental to keep reusing poor code and there is no choice but to rewrite it. So writing poor code is productive work in some sense, but it is useless(almost always, in my experience) in constructing higher levels of abstraction.
The complete disregard for good design I have seen troubles me as a software engineer. When I've had to rewrite code, usually its not because I disagree with its design, but because there is no design to disagree with! IMO code design should be taught better (or at least taught at all...). Only then can someone make the judgement call of what parts can be poorly written and which parts require more care.
This next claim is anecdotal: the people which don't bother to learn even the basics of how actual machines work tend to be the same people which don't bother to properly design their code. Good design necessitates some understanding of how the machine works, it can not be accomplished through brute force pattern matching. I understand that code is becoming increasingly common and that some people have no choice but to interact with it. But if a significant portion of your income is generated through work in software, then I don't really think a valid excuse exists; you should do your job correctly. I'm not saying everyone needs to be an expert. The culture of apathy for the most basic computing principles is what troubles me, and it should trouble anyone who has to read code written by others.
Re: FizzleFade
#115as a "senior" business programmer with non-engineering studies (I have a deegree in byology), I'm feeling an impostor reading this and admitting that I'm unable to understand basically everything... even https://bigmachine.io/products/the-imposters-handbook/ not helped too much
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.
Re: FizzleFade
#116An alternative approach that works for every resolution: http://antirez.com/news/113
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.
Re: FizzleFade
#117An alternative approach that works for every resolution: http://antirez.com/news/113
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 LF…
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.
Re: FizzleFade
#118An alternative approach that works for every resolution: http://antirez.com/news/113
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.
Re: FizzleFade
#119Earlier quoted context omitted.
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 LF…
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.
Absolutely. One of my recent research interests in cryptography has been identifying ways to make pseudorandom permutations faster and using them outside of typical cryptographic contexts. I'm happy to see that you use them in Rax. They map very well to a lot of data structure problems in networking, not just encyption (i.e. assigning IDs to users).
Re: FizzleFade
#120An alternative approach that works for every resolution: http://antirez.com/news/113
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.
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.