Randomness in 8-bit Microchip PIC

Generating pseudo-random (or even fully random) numbers on desktop computers is mostly a solved problem. However, what if we need to generate random numbers on much smaller devices? For example, on Microchip’s 8-bit PIC16F1454 microcontroller?

Good news first, mersenne twister is no longer the only player in town. These days we have a whole family of both faster and more random algorithms courtesy of Guy Steele and Sebastiano Vigna. Their xoshiro / xoroshiro generators cover essentially any combination of speed and memory needs. They are probably a pinnacle of randomness quality you can fit in such a minimal space.

Since I did need a minimal footprint, I first selected xoroshiro64**.

uint32_t rotl(const uint32_t x, int k) {
    return (x << k) | (x >> (32 - k));
}

uint32_t s[2];

uint32_t next(void) {
    uint32_t s0 = s[0];
    uint32_t s1 = s[1];
    uint32_t result = rotl(s0 * 0x9E3779BB, 5) * 5;

    s1 ^= s0;
    s[0] = rotl(s0, 26) ^ s1 ^ (s1 << 9);
    s[1] = rotl(s1, 13);

    return result;
}

This code will generate random numbers that pass vast majority of DieHarder randomness tests and all that just in 58 bytes of data memory and 365 words of program memory (freeware XC8 2.31, with optimizations).

While this is probably as small as a good random number generator can reasonably get on a microcontroller, Microchip PIC is an 8-bit device at heart and dealing with 32-bit values doesn’t come naturally. Fortunately, xoroshiro algorithm family scales reasonably well and one can “borrow” the setup.

Here is my stab at making xoroshiro a bit more 8-bit friendly.

uint8_t rotl(const uint8_t x, int k) {
    return (x << k) | (x >> (8 - k));
}

uint8_t s[2] = { 0, 0xA3 };

uint8_t next(void) {
    uint8_t s0 = s[0];
    uint8_t s1 = s[1];
    uint8_t result = s0 + s1;

    s1 ^= s0;
    s[0] = rotl(s0, 6) ^ s1 ^ (s1 << 1);
    s[1] = rotl(s1, 3);

    return result;
}

Now, this is a simplified version and definitely not as random as the full implementation. Obvious change is in a state variable size (16 instead of 64) and calculation is taken from xoroshiro128+ so that multiplication can be avoided. There are no multiplication circuits in 8-bit PIC microcontrollers and thus this makes code much smaller and faster.

Lastly, the half of initial state is fixed to 0xA3. When dealing with such a small state, not all combinations of initial state are valid nor they produce equally long period and this is essentially just a workaround to keep numbers coming.

This simplified version needs 10 bytes of data memory and takes only 65 words of program memory. A great improvement (more than 5x in both data and program memory) albeit at significant randomness cost. First of all, you essentially only get 256 seeds with large enough period (64897 bytes). Secondly, the whole space can be only 16-bits to start with. While this might barely pass a few DieHarder tests (e.g. birthdays, 2dsphere, dab_dct, and rgb_permutations), it won’t come even close to the full xoroshiro64** in terms of randomness quality. And let’s not even mention higher state size algorithms.

That said, if you just need random numbers for a game or something similar on a highly constrained device, I would say that quality trade-off is worth the speed and memory usage improvements.

PS: If you initialize random number generator with static values (which is perfectly valid), you will always get the same set of random values. Sometime that is a desired feature (e.g. during debugging) but we usually want something more unpredictable. Assuming you’re using the chip with a separate low-frequency oscillator (LFINTOSC), you can rely on a drift between it and a high-frequency oscillator to get a reasonably random seed.

void init(void) {
    // setup timer if not already in use
    T1CONbits.TMR1CS = 0b11;
    T1CONbits.T1OSCEN = 1;
    T1CONbits.TMR1ON = 1;

    _delay(4096);  // just to improve randomness of timer - can be omitted

    // initialize using timer values (ideally you would wait a bit after starting timer)
    s[0] = TMR1L;
    s[1] = 0x2A;  // important to get high periods and to avoid starting from 0x0000
}

PPS: No, xoshiro algorithms are not cryptographically secure. If you need to generate keys on microcontrollers, look into specialized hardware. These algorithms are intended for general-purpose randomness.

PPPS: Code is available for download. It will use 10 bytes of data memory and should fit into 82 words of program memory with initialization from LFINTOSC.