*********************** ******* yapRNG.h ****** *********************** yapRNG - yet another pseudo Random Number Generator yapRNG is a simple pseudo-random number generator. It uses a mechanism based on an interrupt raised by the WatchDog Timer of the microcontroller to collect entropy and a Fibonacci 32 bit LFSR (Linear Feedback Shift Register) to distribute it into a pool. The latest version of this library can be found at: https://github.com/Iniesta8/yapRNG/ Written by Andi Schnebinger. *********************** VERSION HISTORY v. 1.0.0: first release *********************** HOW TO USE THE LIBRARY - INSTALLATION AND METHODS Unpack the library and copy it into your /libraries folder, that usually is in your sketchs' folder (under \Documents\Arduino on Windows OS, under ~/sketchbook on Linux boxes), then include the library and create a new instance of it by adding the following code at the top of your sketch: #include "yapRNG.h" yapRNG prng; Now you can get a random number from the pool: byte value = prng.nextByte(); unsigned int = prng.nextInt(); unsigned long = prng.nextLong(); nextByte() will return a random byte (8 bits) in the range 0..255; nextInt() will return a random unsigned int (16 bits) in the range 0..65535; nextLong() will return a random unsigned long (32 bits) in the range 0..4294967295; *********************** HOW IT WORKS The mechanism of the library is very simple. It uses an interrupt raised by the WatchDog Timer to read the lower byte of the register that keeps the current value of the counter of Timer 1 (in case the microcontroller doesn't have Timer 1, Timer 0 will be used instead). Then, the less significant bit is taken and XORed with the less significant bit of a Fibonacci 32-bits LFSR, Linear Feedback Shift Register, and at the end the result is stored into a bit of a ring pool. The pool is by default 8 bytes in size but it can be resized if you need a bigger one. When the last bit is filled, the algorithm rolls back and starts again from the first one. The WatchDog Timer is set to its lowest interval, ~16 ms. Every 16 ms a bit is stored into the pool. To get a byte from the pool, it must contain at least 8 bits. If these bits aren't available yet, the code will wait for the pool to be filled up. Why this? Because entropy must be generated by the algorithm. How does the code do that? Whe WatchDog Timer is clocked by a separated 128 kHz clock. Due to the tolerance of the electronics components, the WatchDog Timer will not run perfectly synchronized with the other microcontroller's peripherals that instead get their signal clocks by a common clock source (on Arduino, that is the external ceramic resonator). The little differences of the electronic components lead to little timing differences. These differences are used to get random sequences that are different every time the microcontroller starts running. The Fibonacci 32-bits LFSR helps to diffuse these differences and get a sequence with a pseudo-randomness. The bitwise XOR increases the randomness of the bits that will populate the random pool. Let's see the start of the library. Initially, the pool contains only '0' bits: 00000000 00000000 .... 00000000 The size of the pool is related to the amount of SRAM of the microcontroller: - for MCUs with less than 512 bytes of SRAM, the pool size will be set to 8 byte; - for MCUs with an amount of SRAM between 512 and 1024 bytes, the pool size will be set to 12 bytes; - for MCUs with more than 1024 bytes of SRAM, the pool size will be set to 16 bytes. Now the entropy collector will start running: every time the WDT will overflow, it will collect a single bit of entropy and will put it into the pool starting from the less significant bit (LSB) to the most significant bit (MSB). Every bit will be added using a specific variable that points to a specific spot. 0 --> 00000000 00000000 .... 00000000 --> 00000000 00000000 .... 00000000 ^ ^ 1 --> 00000000 00000000 .... 00000000 --> 01000000 00000000 .... 00000000 ^ ^ 1 --> 01000000 00000000 .... 00000000 --> 01100000 00000000 .... 00000000 ^ ^ 0 --> 01100000 00000000 .... 00000000 --> 01100000 00000000 .... 00000000 ^ ^ 1 --> 01100000 00000000 .... 00000000 --> 01101000 00000000 .... 00000000 ^ ^ etc... When the pointer has reached the end of the pool, it is reset again to 0, overwriting the bits that are already into the pool. *********************** SUPPORTED MICROCONTROLLERS AND CLOCK FREQUENCIES yapRNG can work on almost every Atmel microcontroller that is supported by the GNU gcc Avr compiler and the Arduino IDE (through specific cores). At the moment, the only MCU supported by the Arduino IDE but NOT supported by yapRNG is the Atmega8/A due to the fact that the WDT of this chip isn't able to generate an interrupt signal but it can only raise a reset signal. *********************** WARNING - IMPORTANT ADVICE FOR ARDUINO MEGA/MEGA2560 OWNERS: the original bootloader flashed into the first models of the Arduino MEGA and MEGA2560 boards didn't deactivate the watchdog at the microcontroller’s startup leading to a board that will freeze itself in a neverending loop caused by eternal resets. To solve this problem, users of such boards that want to use yapRNG have to change the bootloader with one that it isn’t affected by this issue. The fixed bootloader is bundled with any of the newer releases of the Arduino software at this folder: /hardware/arduino/avr/bootloades/stk500v2 or, in case you are using an older release of the IDE, can be downloaded by this page: https://github.com/arduino/Arduino-stk500v2-bootloader/tree/master/goodHexFiles *********************** WARNING - IMPORTANT ADVICE FOR ALL THE USERS yapRNG is NOT intended to be used in critical applications where a REAL random number generator is required because the mechanism used by this library does NOT guarantee that the sequence won't contain repeating patterns. If you need a more secure algorithm, try looking for something else. *********************** LICENSE This library is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3.0 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. *********************** Document revision 1st revision: 2017/03/25