# 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**.

`Code: 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.

`Code `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.

`Initialization using LFINTOSC `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`.