I found some free time to spend on writing a new library that I called pRNG, for pretty Randon Number Generator.
Basically, the library is a pseudorandom number generator. It uses an interrupt raised by the WatchDog Timer (WDT) to collect entropy from a timer of the Arduino (or any microcontroller) and a 32-bits Galois linear feedback shift register (LFSR). Random data are stored in a pool that is constantly updated, from which the user can pick them up as single bytes. The mechanism gives patterns that are different every time the Arduino starts, and never replicated (at least in the short period).
Let’s esamine the library. The WDT is an built-in circuit that is present in almost every microcontroller (MCU) from Atmel: it’s mainly used (if activated) to reset the MCU if this freezes into a neverending loop of the user’s firmware. The WDT can be set up to raise an interrupt too, not only to reset the MCU (I used this feature in my leOS2). We can use this feature to write an Internet Service Routine (ISR) that periodically scrolls an LFSR: this one returns a bit that we XOR with the less significant bit of the register of a timer of the MCU, and then the result is stored into a pool. Here you can see a linear feedfack shift register: if you click on the image you’ll see the animation that shows you how some bits are used to feedback the register when a bit is picked up.
Thanks to this mechanism, the bits sequence appears to be mostly random, in fact it is repeated only after a huge number of iterations, and the bigger the size of the register is the longer this number is. The LFSR ensures that we have very complex patterns. We just have to solve the problem of repeatability at the power-up of the Arduino or MCU. For example, the Arduino random function is anything but a random number generator: in fact every time the Arduino is powered up, it will return the same numerical sequence: pRNG, instead, will return a sequence that will be every time different from the previous one. This is possible because the LFSR is seed using a starting value that ensures the randomness of the generated sequence.
Let’s see how this seed is provided. The WDT gets its clock from a built-in 128 kHz oscillator while the other modules of the MCU, like the timers, get their clock from the system clock: for the Arduino boards, this is given by an external ceramic oscillator. Due to the technical tolerances, electronics compontents differ each other: they are almost similar but not completely identical. This tolerances are responsable for the little difference between the nominal clock speed and the real frequency of any crystal or resonator. So the signal can suffer little variations like slowdowns or accelerations. We use this fact to be sure that every time the WDT interrupt is raised we go to read the register of the timer at a time that isn’t exactly the same of the previous due to the fact that the WDT and the timer use two different clocks, returning a value that is greater or smaller than the last one. This is the mechanism used by pRNG to ensure that it never gives the same random sequence.
The use of the library is quite simple. Just download the archive, uncompress it into your sketchbooks library and you’re ready to use it. First, include it into your sketch and instantiates a new copy of the library:
#include "pRNG.h"
pRNG prng;
Then call the begin() method from the setup():
void setup() {
prng.begin();
....
The library provides 3 methods to extract numbers from the pool: getRndByte(), to extract a random byte (0..255), getRndInt() to extract an unsigned integer (0..65535), and getRndLong() to extract an unsigned long integer (0..4294967295):
byte valByte = prng.getRndByte();
unsigned int valInt = prng.getRndInt();
unsigned long valLong = prng.getRndLong();
Just a note about the random pool. Its size is related to the amount of SRAM of the microcontroller: from 8 bytes for MCUs with less than 512 bytes of SRAM to 16 byte for MCUs with more than 1024 bytes. It is populated bit per bit from the less significant one of the first byte of the pool to the most significant one of the last byte of the pool. When the last bit is stored inside the pool, the algorithm restarts by the first one. When you ask for a byte, the library returns the first byte of the pool: the following bytes are moved back by 1 position to fill the empty space. If the pool doesn’t contain 8 bits, the library will wait until 1 byte of entropy is available. You have to keep in mind this because if you requires a lot of random bytes the library will return the data only when the pool will contain the need amount of entropy. The WDT is set up to raise an interrupt at the shortest interval, that is about 16 milliseconds, so to get 1 byte of entropy 16 x 16 = 256 ms are required (on an Atmega328).
The library runs on almost every Atmel MCU. The only MCU that is not supported is the ATmega8, due to the fact that the WDT of this chip isn’t able to raise interrupts.
IMPORTANT:
the library is NOT intended to be used in place of a REAL random number generator because it is not guaranteed that the sequence that it generates doesn’t contain repetitive patterns in the long period. If you need a higher level of security, please use specific random number generators.
IMPORTANT ADVICE FOR ARDUINO MEGA2560 USERS
the builti-in bootloader of the Arduino MEGA2560 boards doens’t deactivate the WDT after a reset so it is possible that you can have a freezed card that still continue to reset itself. To avoid this problem and if you want to use pRNG, you have to flash a newer bootloader, available at this page.
