***********************
******** pRNG.h *******
***********************

pRNG.h - <p>retty <R>andom <N>umber <G>enerator

pRNG 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
Galois 32 bit LFSR (Linear Feedback Shift Register) to
distribuite it into a 10-bytes pool.
    
For more infos, please read the README.txt file.

The latest version of this library can be found at:
http://www.leonardomiliani.com/
or at:
https://github.com/leomil72

Written by Leonardo Miliani <www.leonardomiliani.com>

***********************
VERSION HISTORY

v. 1.2.3:  use correct field separator in keywords.txt (per1234)
v. 1.2.2:  documentation revision; lowered down serial speed to comply with Tiny MCUs
v. 1.2.1:  added compatibility with Arduino IDE >= 1.6.7
v. 1.2.0:  now the pool size is sized according to the amount of SRAM
v. 1.1.0:  added the method getRndLong() to extract a random unsigned long
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 istance of it
by adding the following code at the top of your sketch:

#include "pRNG.h"
pRNG prng;

++IMPORTANT++
Since v. 1.2.0, the library doesn't need to be initialized anymore. If
you're using an older version, initialize the library in the setup() routine:

void setup() {
  prng.begin(); //only needed for versions < 1.2.0
  .....
}

Now you can get a random number from the pool:

byte value = prng.getRndByte();
unsigned int = prng.getRndInt();
unsigned long = prng.getRndLong();

getRndByte() will return a random byte (8 bits) in the range 0..255;
getRndInt() will return a random unsigned int (16 bits) in the range 0..65535;
getRndLong() 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 Galois 32-bits LFSR, Linear 
Feedback Shift Register, and at the end the result is stored into a bit of a
ring pool. The pools is by default 10 bytes in size but it can be resized
if you nees a bigger one. When the last bit is filled, the algorithm rolls back
and start 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 Galois 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

pRNG 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 pRNG 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 pRNG 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

pRNG 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

6th revision: 2016/04/24