Micrornd

Robbert Haarman

2019-05-27

Pseudorandom numbers for 8-bit microcomputers

Introduction

Micrornd is a pseudorandom number generator (PRNG) specifically designed for 8-bit microcomputers. It aims to strike a reasonable balance between code size, speed, and quality of the generated numbers. Implementations in 6502 assembly and C are provided.

Feel free to use and modify the code for your own projects. Attributing the code to me and sharing any improvements you make are appreciated.

6502 Assembly

The code below shows an implementation of Micrornd in 6502 assembly. It uses 4 bytes of state and returns the generated number in the A register. If the state is located in the zero page, this code takes 29 bytes and 44 clock cycles. If the state is not in the zero page, the code takes 41 bytes and 56 clock cycles.

The first 4 instructions can be omitted to produce the XS variant, which uses only 3 bytes of state, 21 bytes of code, and 30 clock cycles if the state is in the zero page. If not in the zero page, the code takes 29 bytes and 38 cycles.


lda micrornd_state + 1
eor micrornd_state + 3
sta micrornd_state + 1
inc micrornd_state + 3

lda micrornd_state + 1
asl
eor #$d5
adc micrornd_state + 2
sta micrornd_state + 1
lda micrornd_state + 2
adc #1
sta micrornd_state + 2
lda micrornd_state
adc micrornd_state + 1
sta micrornd_state

C Code

An implementation in C is shown below. The corresponding 6502 code is included in the comments.


uint8_t micrornd_state[4];

uint8_t micrornd() {
    uint16_t a;
    // lda s3; eor s1; sta s1
    micrornd_state[1] ^= micrornd_state[3];
    // inc s3
    ++micrornd_state[3];

    // lda s1; asl
    a = (uint16_t) micrornd_state[1] << 1;
    // eor #$d5                                
    a ^= 0xd5;
    // adc s2
    a = (a & 0xff) + micrornd_state[2] + (a >> 8);
    // sta s1
    micrornd_state[1] = a;
    // lda s2; adc #1
    a = micrornd_state[2] + 1 + (a >> 8);
    // sta s2
    micrornd_state[2] = a;
    // lda s0; adc s1; sta s0
    micrornd_state[0] += micrornd_state[1] + (a >> 8);
    return micrornd_state[0];
}

Explanation of the Algorithm

The byte in micrornd_state[1] is used as a mixer. On every invocation, it is shifted left and xored with 0xd5. This operation has two interesting properties. First, it makes the new value of micrornd_state[1] not look like the old value. Secondly, it sets the carry flag to a known state, independent of what it was on function entry. After this, we add micrornd_state[2] to micrornd_state[1], which uses the carry flag we just computed and computes a new carry flag.

The byte in micrornd_state[2] is used as a stepper. On every invocation, it is increased by either 1 or 2, depending on the carry flag that was just computed. Since it wraps around once it reaches 256, it causes the value we add to micrornd_state[1] to be different from one invocation to the next.

Together, the mixer and the stepper produce a sequence that might at first glance look random, but is not very good. Some values are significantly more likely to be generated than others, and the sequence compresses very well.

The last step is to add the mixer value to the most recently generated pseudorandom number (stored in micrornd_state[0]). We also add in the carry from incrementing the stepper, which makes the sequence less repetitive. The result is a sequence where each possible byte value is generated close to equally often and which does not compress well.

For the Micrond XS variant, this is everything. The regular variant adds one more step that runs before the others. It changes micrornd_state[1] by xoring it with micrornd_state[3], and then increments micrornd_state[3] by one. This effectively adds another stepper that is out of sync with micrornd_state[2], increasing the period of the generator.

How Good is It?

Here are the results of a few tests I ran to get an idea of the quality of the generated numbers. I created a file with 16,777,216 bytes generated by Micrornd with a seed of all NUL bytes. Then I used that file as input to a few tests.

First, rngtest.

rngtest 5
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.
There is NO warranty; not even for MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 134217728
rngtest: FIPS 140-2 successes: 6708
rngtest: FIPS 140-2 failures: 2
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 1
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=615.274; avg=27689.981; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=39.165; avg=171.943; max=185.179)Mibits/s
rngtest: Program run time: 749610 microseconds

Not too shabby. For comparison, 16MB from /dev/random also failed Long run once, but passed Runs every time.

Let's count how often each byte value occurs. We expect these to be roughly equal. Command: od -An -t x1 -v -w1 micrornd.out | sort | uniq -c | sort -k 1

The least frequent 10 are:

And the most frequent 10:

Pretty evenly distributed.

Next, let's see how well the file with the random numbers compresses. If it compresses well, that means there are patterns in there that the compressor can detect (generally, repeated runs).

Input	16,777,216
gzip -9	16,779,794
xz -6 -F raw	16,778,042

Neither compressor managed to reduce the size of the file, which, for our purposes, is good.

Related Work

muhash describes a few simple hash functions designed for the 6502, as well as a pseudorandom number generator. They make use of a 256-byte lookup table to speed up operations. The PRNG generates 32-bit numbers and consists of an extra 63 bytes of code (in addition to the lookup table) that take 93 cycles to execute, assuming the state lives in the zero page and the lookup table doesn't.

http://codebase64.org/doku.php?id=base:small_fast_8-bit_prng describes a small PRNG in just 14 bytes of code (assuming the state is in the zero page) and 1 byte of state. It repeats after at most 256 numbers, but it is very small.

The Deadbeef Random Number Generator is another PRNG I designed, with C code that is simple enough to memorize. As far as I can tell, it performs fairly well, but its multiple-bit shifts and 32-bit numbers are not a great fit for 8-bit micros.