Ogni tanto mi risveglio dal letargo e divento pericoloso perché mi metto a produrre software ]
Questa volta è il turno della pRNG da pretty Random Number Generator, una libreria che serve, come si capisce dal nome, a produrre numeri pseudo casuali.
Dove sta l'inghippo?
L'inghippo sta nel fatto che questa libreria cerca di generare numeri pseudo casuali discretamente casuali. Come saprete la funzione random() di Arduino è tutto fuorché random perché ogni volta che si avvia la scheda, la sequenza riparte. Con pRNG ho cercato un modo alternativo per generare una sequenza non ripetibile, evitando i pastrocchi della lettura dei pin analogici che di casuale hanno ben poco
La libreria utilizza un interrupt sollevato dal WatchDog Timer per collezionare entropia usando un timer dell’Arduino (o del microcontrollore) ed un registro a scorrimento a retroazione lineare (in inglese LFSR, da Linear Feedback Shift Register) di Galois a 32 bit. I dati casuali sono prelevabili come singoli byte da un pool costantemente aggiornato. Il meccanismo permette di avere sequenze sempre diverse e mai ripetute (per lo meno non nel breve periodo).
Ormai il WatchDog lo conoscerete senz'altro perché ve l'ho menata non so quanto a riguardo visto che l'ho usato nel mio leOS2. Sfruttando la possibilità che offre di generare anche un interrupt, si può creare una ISR (Internet Service Routine) che periodicamente fa scorrere il registro: il registro restituisce in output un bit, bit che viene poi combinato tramite XOR con il bit meno significativo del contatore di un timer del microcontrollore ed il risultato che si ottiene viene inserito in un pool. Grazie a questo meccanismo la sequenza di bit generata appare semi casuale, ripetendosi solo dopo un elevato numero di estrazioni, e più è grande il registro maggiore è questo valore. L’uso del registro a scorrimento è il meccanismo usato che consente di avere sequenze molto complesse. Resta il problema della ripetibilità all’avvio. Ad esempio, la funzione random predefinita dell’Arduino in realtà di random non ha nulla dato che ad ogni avvio essa restituisce sempre la stessa sequenza numerica: pRNG, invece, ogni volta che viene avviato restituisce una sequenza diversa. Ciò è possibile perché il registro a scorrimento è usato in combinazione con un seme casuale sempre diverso per cui anche la sequenza che esso restituisce varia ogni volta.
Vediamo come viene estratto questo seme. Il WatchDog Timer riceve il clock da un oscillatore a 128 kHz mentre tutte le altre periferiche del microcontrollore, compresi i timer, ricevono il clock di lavoro da un'altra fonte, che per le schede Arduino è il risuonatore ceramico esterno. Grazie alle tolleranze produttive, ogni componente viene realizzato diverso dagli altri con specifiche di funzionamento grosso modo uguali ma mai perfettamente identiche. Queste tolleranze sono responsabili della non perfetta precisione del segnale generato, che può subire delle oscillazioni rallentando oppure accelerando rispetto alla frequenza nominale. Sfruttando questo fatto, accade che quando viene chiamata la routine di interrupt del WatchDog ed andiamo a leggere il contatore del timer, può accadere che l’oscillatore del primo abbia avuto una leggera accelerazione rispetto al secondo o viceversa. Questa differenza permette ad ogni intervallo di leggere nel contatore del timer un valore leggermente differente. Questo è il meccanismo alla base della pRNG grazie al quale essa non genera mai la stessa sequenza di numeri casuali.
L’uso della libreria è molto semplice. Basta scaricare l’archivio e scompattarlo nella cartella /libraries contenuta nella propria cartella degli sketch. A questo punto basta includerla nel proprio sketch ed istanziarne una copia:
#include "pRNG.h"
pRNG prng;
Nel setup() va inizializzata prima dell’uso con il metodo begin():
void setup() {
prng.begin();
La libreria fornisce 2 soli metodi, getRndByte() per estrarre dal pool un byte casuale (0..255), e getRndInt() per estrarre un intero senza segno (0..65535):
byte valByte = prng.getRndByte();
unsigned int valInt = prng.getRndInt();
Una nota a riguardo del pool di numeri casuali. Esso ha una dimensione predefinita di 10 byte (modificabile nel file pRNG.cpp) e viene popolato bit per bit a partire da quello meno significativo del primo byte fino al bit più significativo dell’ultimo byte. Una volta raggiunta l’estremità del pool, l’algoritmo riparte dall’inizio. Quando si estrae un byte, viene prelevato il primo byte dal pool e tutti quelli successivi vengono spostati indietro di una posizione per occupare lo spazio vuoto che si è creato. Se nel pool non sono disponibili almeno 8 bit, verrà atteso finché non sarà pronto 1 byte di entropia. Questa cosa è da tenere a mente perché richieste continuative di numeri casuali saranno evase solo quando i dati saranno disponibili. Il WatchDog Timer è impostato con il minimo prescaler possibile, che genera un interrupt circa ogni 16 millisecondi, per cui per ottenere 1 byte di entropia sono necessari circa 8*16=96 ms.
La libreria è compatibile con tutti i microcontrollori Atmel ad accezione dell’ATmega8 perché il suo WatchDog Timer non è capace di sollevare un interrupt.
IMPORTANTE:
la libreria NON deve essere utilizzata nel caso si richieda un VERO generatore di numeri casuali perché non è garantito che la pRNG non fornisca ad un certo punto una sequenza ripetibile di numeri. Nel caso si necessiti di più sicurezza, è bene rivolgersi a sistemi di generazione di numeri casuali diversi.
AVVISO PER GLI UTENTI DELLA ARDUINO MEGA/MEGA2560:
il bootloader originale delle schede Arduino MEGA e MEGA2560 non disattiva il watchdog al riavvio del microcontrollore per cui si incorre in un reset infinito che blocca il chip. Per evitare questo problema bisogna sostituire il bootloader con uno aggiornato che è esente da questo problema. Il bootloader è prelevabile da questa pagina.
La libreria è scaricabile da questa pagina.