Medo's Home Page

When dealing with 8-bit microcontrollers one doesn’t always have all facilities taken for granted on a computer. One such example is a simple random number. While all computers can easily provide you with random number at will, unless you have a heavily specialized PIC, real random numbers are out of your reach. However, there is a way to get sufficiently close to make it work for most non-cryptographic purposes.

The answer is in linear-feedback shift registers. Assuming polynomials are carefully chosen, it is relatively easy to get non-repeating 255 byte sequences on 8-bit PIC. Yes, they are not random but for the most purposes they are random enough.

There are many types of LFSRs, Fibonacci’s being the most famous and probably the one implemented most often due to its simple hardware structure. However, for the PIC device, Galois has similar enough properties with a much simpler software structure.

General Galois function might looks like this:

#define GALOIS_POLYNOMIAL 0b11010100; //x^8+x^7+x^5+x^3+1
uint8_t randomState;

uint8_t getRandomByte() {
    unsigned bit = randomState & 0x01;
    randomState >>= 1;
    if (bit) { randomState ^= GALOIS_POLYNOMIAL; }
    return randomState;
}

This function essentially takes whatever data has in previous step and, using one of the maximum sequence length polynomials, calculates the next random byte. However, if you run it as such you might or might not get anything other than 0. Why? Well, pesky sequence has one blind spot – number 0. You can get any 255 byte sequence assuming it does not contain 0. If data becomes 0, it will stay 0.

Knowing this, one might be tempted to simply initialize data to some number and call it a day. Indeed, that would work for many applications that use 8-bit PIC. However, there are two things to have in mind: sequence will repeat every 255 bytes and random number sequence will be exactly the same on every startup.

To deal with the issue of repeating sequences, we need a counter that will simply reset the sequence after it “runs out of bytes”. As LFSR “circles” back to the original value after going thru all permutations (assuming polynomial is selected well), the easiest approach is to remember first value and reinitialize inner state once that value comes up again.

Second problem is a bit harder but not impossible. While the hardware random source would be nice, we can also do without it. My favorite approach is to have 8-bit timer running (e.g. TMR4) and then execute something that doesn’t have deterministic time – for example any user interaction (e.g. button press), writing to EEPROM (if PIC has one), or just waiting for PLL lock:

//setup unused timer that runs of the clock
T4CONbits.T4CKPS = 0; no prescale
T4CONbits.T4OUTPS = 0; //no postscale
T4CONbits.TMR4ON = 1; turn on timer 4 (or any other timer)

PLLEN = 1; //enable PLL
while (!OSCCONbits.OSTS); //wait for PLL lock

If function takes a slightly different amount of clock cycles every time, your timer will be in reasonably random state every time you check it and you can use it as a seed for generating random sequence – just don’t forget to ensure it is not zero.

Thus, our simple generator of random numbers could look something like this:

#define GALOIS_POLYNOMIAL 0b11010100; //x^8+x^7+x^5+x^3+1
uint8_t randomState = 0;
uint8_t randomStart = 0;

uint8_t getRandomByte() {
    if (randomState == randomStart) {
        randomState = (randomState ^ TMR4 ^ polynomial) | 0x80; //ensure non-zero at the cost of LSB
        randomStart = randomState;
    }

    unsigned bit = randomState & 0x01;
    randomState >>= 1;
    if (bit) { randomState ^= GALOIS_POLYNOMIAL; }
    return randomState;
}

If you run it for a while, you’ll notice something a bit disturbing. While start of the sequence is random, sequence is always the same. We need a way to make the sequence a bit more random. The cheap way to change this is to simply loop through all maximum length polynomial terms and thus extending our sequence from 255 to 4080 bytes.

Or, to break a pattern, you can even make switches in middle of sequence to make it a bit less obvious:

const uint8_t POLYNOMIALS[] = { 0x8E, 0x95, 0x96, 0xA6, 0xAF, 0xB1, 0xB2, 0xB4,
                                0xB8, 0xC3, 0xC6, 0xD4, 0xE1, 0xE7, 0xF3, 0xFA };
const uint8_t POLYNOMIALS_COUNT = 16;
uint8_t polynomial = 0xB8;

uint8_t randomState = 0;
uint8_t randomIndex = 0;

uint8_t getRandomByte() {
    if (randomIndex == 0) {
        randomIndex = (TMR4 >> 6) + 1; //generate number 1 to 4
        randomState = (randomState ^ TMR4 ^ polynomial) | 0x80; //ensure non-zero at the cost of LSB
        polynomial = POLYNOMIALS[TMR4 & 0x0F]; //select next polynomial
    }
    randomIndex--;

    unsigned bit = randomState & 0x01;
    randomState >>= 1;
    if (bit) { randomState ^= polynomial; }
    return randomState;
}

Realistically, there is only so much you can do without any random entropy while keeping function reasonably fast and I think this final function gives a reasonable result.

 
PS: Again, do not use this for anything security related – for that you need real random numbers, not pseudo-random sequences.

PPS: Jason Sachs has a nice article going a bit deeper in details about LFSRs.

PPPS: If you really want to expand random sequence, think about using 16-bit state and polynomial. Albeit the price of 16-bit computations on a 8-bit microprocessor is non-negligible (albeit not devastating), your use case might warrant such step.