OSDev.org

I'm trying to implement a non-repeating PRNG, and it seems that the best way to do that is with a block cipher on an increasing value. Are there any 64 bit block ciphers that would be easy to implement in x86_64 assembly?

There is no such thing as a non-repeating PRNG. Any PRNG has a finite amount of state, and therefore a finite number of states it can be in, and therefore has to repeat its sequence at some point.

But anyway, a block cipher that should be easy to implement in x86_64, if you're willing to use architecture extensions, would be Rijndael, since the introduction of AES-NI means that it can be implemented in only a few instructions. Otherwise they are all very long instruction lists. May I ask why assembler and not C or any other high-level language?

Another approach may be to use the SHA counter algorithm. You fill a hash buffer with entropy (e.g. from a simpler LCG), and then, when more entropy is requested, you hash that buffer (with something like SHA-3) and return the data from that hash. Once that data is used up, you increment the buffer and return the hash of the increment. Highly unlikely to repeat until the hash buffer has completely wrapped around.

By non-repeating, I mean that it will not repeat before every possible value has been returned. I specifically need 64 bit output, which excludes AES and SHA as they both would require truncation, and would not guarantee a period of 2^64 after that.

nullplan wrote: ↑Tue Sep 29, 2026 11:13 am May I ask why assembler and not C or any other high-level language?

The entirety of the codebase that this is going to be integrated into is written in assembly.

That wouldn't stop you writing this particular function in C. It would be much easier.

I neither have a stack or a compiler. That's a fairly big roadblock for writing it in c.

I will also note that I am fine with a C implementation that I can manually translate into assembly.

avalyn0x45 wrote: ↑Tue Sep 29, 2026 2:55 pmI neither have a stack or a compiler.

Why don't you have a stack?

Octocontrabass wrote: ↑Tue Sep 29, 2026 4:23 pm

avalyn0x45 wrote: ↑Tue Sep 29, 2026 2:55 pmI neither have a stack or a compiler.

Why don't you have a stack?

Because I don't need one.

Why don't you need a stack? How are you able to do things like call functions and handle interrupts without one?

Octocontrabass wrote: ↑Tue Sep 29, 2026 4:32 pm Why don't you need a stack? How are you able to do things like call functions and handle interrupts without one?

The logic is small enough to not require function calls, and interrupts are handled by setting rsp0 to a tiny 64 byte region of memory only used for interrupts.