{"id":779,"date":"2013-04-14T21:47:05","date_gmt":"2013-04-14T20:47:05","guid":{"rendered":"http:\/\/www.leonardomiliani.com\/?p=779"},"modified":"2013-07-06T20:05:24","modified_gmt":"2013-07-06T19:05:24","slug":"nuova-libreria-prng","status":"publish","type":"post","link":"https:\/\/leonardomiliani.com\/?p=779","title":{"rendered":"Nuova libreria pRNG"},"content":{"rendered":"

In un ritaglio di tempo ho scritto una nuova libreria che ho chiamato pRNG<\/strong>, acronimo di pretty Randon Number Generator<\/em>, ossia Generatore di Numeri Casuali Carino.<\/p>\n

La libreria fondamentalmente \u00e8 un generatore di numeri pseudo casuali. 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).<\/p>\n

<\/p>\n

Entriamo un p\u00f2 nel dettaglio. Il WatchDog Timer \u00e8 un circuito interno ai microcontrollori Atmel che principalmente viene usato (se attivato) per resettare il microcontrollore se questo si blocca nell’esecuzione di un codice senza uscita. Esso pu\u00f2 per\u00f2 essere impostato anche per sollevare un interrupt, non solo per eseguire un reset (caratteristica che uso nella mia libreria leOS2). Sfruttando questa possibilit\u00e0 si pu\u00f2 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. Qui sotto potete vedere un registro a scorrimento a retroazione lineare: ingrandendo l’immagine verr\u00e0 mostrata l’animazione in cui la retroazione \u00e8 data da alcuni bit che sono reintrodotti nel registro quando un bit viene prelevato da esso.\"Lfsr\"<\/a><\/p>\n

Grazie a questo meccanismo la sequenza di bit generata appare semi casuale, ripetendosi solo dopo un elevato numero di estrazioni, e pi\u00f9 \u00e8 grande il registro maggiore \u00e8 questo valore. L’uso del registro a scorrimento \u00e8 il meccanismo usato che consente di avere sequenze molto complesse. Resta il problema della ripetibilit\u00e0 all’avvio. Ad esempio, la funzione random predefinita dell’Arduino in realt\u00e0 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\u00f2 \u00e8 possibile perch\u00e9 il registro a scorrimento \u00e8 usato in combinazione con un seme casuale sempre diverso per cui anche la sequenza che esso restituisce varia ogni volta.<\/p>\n

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 dalla stessa fonte, che per le schede Arduino \u00e8 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\u00f2 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\u00f2 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 \u00e8 il meccanismo alla base della pRNG grazie al quale essa non genera mai la stessa sequenza di numeri casuali.<\/p>\n

L’uso della libreria \u00e8 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:<\/p>\n

#include \"pRNG.h\"
\npRNG prng;<\/code><\/p>\n

Nel setup() va inizializzata prima dell’uso con il metodo begin()<\/em>:<\/p>\n

void setup() {
\nprng.begin();
\n....
\n<\/code><\/p>\n

La libreria fornisce 3 metodi, getRndByte()<\/em> per estrarre dal pool un byte casuale (0..255), \u00a0getRndInt()<\/em> per estrarre un intero senza segno (0..65535), e getRndLong() per estrarre un intero lungo senza segno (0..4294967295):<\/p>\n

byte valByte = prng.getRndByte();
\nunsigned int valInt = prng.getRndInt();
\nunsigned long valLong = prng.getRndLong();
\n<\/code><\/p>\n

Una nota a riguardo del pool di numeri. Esso ha una dimensione che varia in base al quantitativo di SRAM del microcontrollore: si parte da 8 byte per le MCU con meno di 512 byte fino ad arrivare ai 16 byte delle MCU con pi\u00f9 di 1024 byte. Esso viene popolato bit per bit a partire da quello meno significativo del primo byte fino al bit pi\u00f9 significativo dell’ultimo byte. Una volta raggiunta l’estremit\u00e0 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 \u00e8 creato. Se nel pool non sono disponibili almeno 8 bit, verr\u00e0 atteso finch\u00e9 non sar\u00e0 pronto 1 byte di entropia. Questa cosa \u00e8 da tenere a mente perch\u00e9 richieste continuative di numeri casuali saranno evase solo quando i dati saranno disponibili. Il WatchDog Timer \u00e8 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 16 x 16 = 256 ms su un Atmega328.<\/p>\n

La libreria \u00e8 compatibile con tutti i microcontrollori Atmel ad accezione dell’ATmega8 perch\u00e9 il suo WatchDog Timer non \u00e8 capace di sollevare un interrupt.<\/p>\n

IMPORTANTE<\/strong><\/p>\n

la libreria NON deve essere utilizzata nel caso si richieda un VERO generatore di numeri casuali perch\u00e9 non \u00e8 garantito che la pRNG non fornisca ad un certo punto una sequenza ripetibile di numeri. Nel caso si necessiti di pi\u00f9 sicurezza, \u00e8 bene rivolgersi a sistemi di generazione di numeri casuali diversi.<\/p>\n

IMPORTANTE PER GLI UTENTI DELLA ARDUINO MEGA\/MEGA2560<\/strong>
\nIl 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, se si vuole usare la pRNG bisogna sostituire il bootloader con uno aggiornato che \u00e8 esente da questo problema. Il bootloader \u00e8 prelevabile da questa pagina<\/a>.<\/p>","protected":false},"excerpt":{"rendered":"

In un ritaglio di tempo ho scritto una nuova libreria che ho chiamato pRNG, acronimo di pretty Randon Number Generator,...<\/p>\n","protected":false},"author":193,"featured_media":781,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[14],"tags":[],"class_list":["post-779","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-arduino"],"_links":{"self":[{"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/posts\/779","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/users\/193"}],"replies":[{"embeddable":true,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=779"}],"version-history":[{"count":10,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/posts\/779\/revisions"}],"predecessor-version":[{"id":789,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/posts\/779\/revisions\/789"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=\/wp\/v2\/media\/781"}],"wp:attachment":[{"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=779"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=779"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/leonardomiliani.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=779"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}