d805ac3942e795a856d761539acdd181eb4bdea6
[gnuk/neug.git] / src / random.c
1 /*
2  * random.c - random number generation
3  *
4  * Copyright (C) 2011 Free Software Initiative of Japan
5  * Author: NIIBE Yutaka <gniibe@fsij.org>
6  *
7  * This file is a part of NeuG, a Random Number Generator
8  * implementation (for STM32F103).
9  *
10  * NeuG is free software: you can redistribute it and/or modify it
11  * under the terms of the GNU General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * Gnuk is distributed in the hope that it will be useful, but WITHOUT
16  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU General Public License
21  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
22  *
23  */
24
25 #include "config.h"
26
27 #include "ch.h"
28 #include "hal.h"
29
30 static Thread *rng_thread;
31 #define ADC_DATA_AVAILABLE ((eventmask_t)1)
32
33 /* Total number of channels to be sampled by a single ADC operation.*/
34 #define ADC_GRP1_NUM_CHANNELS   2
35  
36 /* Depth of the conversion buffer, channels are sampled one time each.*/
37 #define ADC_GRP1_BUF_DEPTH      4
38  
39 /*
40  * ADC samples buffer.
41  */
42 static adcsample_t samp[ADC_GRP1_NUM_CHANNELS * ADC_GRP1_BUF_DEPTH];
43  
44 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n);
45 static void adccb_err (ADCDriver *adcp, adcerror_t err);
46
47 /*
48  * ADC conversion group.
49  * Mode:        Linear buffer, 4 samples of 2 channels, SW triggered.
50  * Channels:    Vref   (1.5 cycles sample time, violating the spec.)
51  *              Sensor (1.5 cycles sample time, violating the spec.)
52  */
53 static const ADCConversionGroup adcgrpcfg = {
54   FALSE,
55   ADC_GRP1_NUM_CHANNELS,
56   adccb,
57   adccb_err,
58   0,
59   ADC_CR2_TSVREFE,
60   ADC_SMPR1_SMP_SENSOR(ADC_SAMPLE_1P5) | ADC_SMPR1_SMP_VREF(ADC_SAMPLE_1P5),
61   0,
62   ADC_SQR1_NUM_CH(ADC_GRP1_NUM_CHANNELS),
63   0,
64   ADC_SQR3_SQ2_N(ADC_CHANNEL_SENSOR) | ADC_SQR3_SQ1_N(ADC_CHANNEL_VREFINT)
65 };
66
67 /*
68  * ADC end conversion callback.
69  */
70 static void adccb (ADCDriver *adcp, adcsample_t *buffer, size_t n)
71 {
72   (void) buffer; (void) n;
73
74   chSysLockFromIsr();
75   if (adcp->state == ADC_COMPLETE)
76     chEvtSignalFlagsI (rng_thread, ADC_DATA_AVAILABLE);
77   chSysUnlockFromIsr();
78 }
79
80 static void adccb_err (ADCDriver *adcp, adcerror_t err)
81 {
82   (void)adcp;  (void)err;
83 }
84
85 \f
86 /*
87  * TinyMT routines.
88  *
89  * See
90  * "Tiny Mersenne Twister (TinyMT): A small-sized variant of Mersenne Twister"
91  * by Mutsuo Saito and Makoto Matsumoto
92  *     http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/
93  */
94
95 /* Use the first example of TinyMT */
96 #define TMT_MAT1 0x8f7011ee
97 #define TMT_MAT2 0xfc78ff1f
98 #define TMT_TMAT 0x3793fdff
99
100 static uint32_t tmt[4];
101
102 static void tmt_one_step (void);
103
104 #define TMT_INIT_MIN_LOOP 8
105 #define TMT_INIT_PRE_LOOP 8
106
107 /**
108  * @brief  TinyMT initialize function.
109  */
110 static void tmt_init (uint32_t seed)
111 {
112   int i;
113
114   tmt[0] = seed;
115   tmt[1] = TMT_MAT1;
116   tmt[2] = TMT_MAT2;
117   tmt[3] = TMT_TMAT;
118
119   for (i = 1; i < TMT_INIT_MIN_LOOP; i++)
120     tmt[i & 3] ^= i + UINT32_C(1812433253) * (tmt[(i - 1) & 3]
121                                               ^ (tmt[(i - 1) & 3] >> 30));
122
123   if ((tmt[0] & 0x7fffffff) == 0 && tmt[1] == 0 && tmt[2] == 0 && tmt[3] == 0)
124     {                           /* Prevent all zero */
125       tmt[0] = 'T';
126       tmt[1] = 'I';
127       tmt[2] = 'N';
128       tmt[3] = 'Y';
129     }
130
131   for (i = 0; i < TMT_INIT_PRE_LOOP; i++)
132     tmt_one_step ();
133 }
134
135 /**
136  * @brief  TinyMT one step function, call this every time before tmt_value.
137  */
138 static void tmt_one_step (void)
139 {
140   uint32_t x, y;
141
142   y = tmt[3];
143   x = (tmt[0] & 0x7fffffff) ^ tmt[1] ^ tmt[2];
144   x ^= (x << 1);
145   y ^= (y >> 1) ^ x;
146   tmt[0] = tmt[1];
147   tmt[1] = tmt[2];
148   tmt[2] = x ^ (y << 10);
149   tmt[3] = y;
150   if ((y & 1))
151     {
152       tmt[1] ^= TMT_MAT1;
153       tmt[2] ^= TMT_MAT2;
154     }
155 }
156
157 /**
158  * @brief  Get a random word (32-bit).
159  */
160 static uint32_t tmt_value (void)
161 {
162   uint32_t t0, t1;
163
164   t0 = tmt[3];
165   t1 = tmt[0] + (tmt[2] >> 8);
166   t0 ^= t1;
167   if ((t1 & 1))
168     t0 ^= TMT_TMAT;
169   return t0;
170 }
171
172 /* 8 parallel CRC-16 shift registers, with randomly rotated feedback */
173 #define EPOOL_SIZE 16
174 static uint8_t epool[EPOOL_SIZE];       /* Big-endian */
175 static uint8_t ep_count;
176
177 /*
178  * Magic number seven.
179  *
180  * We did an experiment of measuring entropy of ADC output with MUST.
181  * The entropy of a byte by raw sampling of LSBs has more than 6.0 bit/byte.
182  * So, it is considered OK to get 4-byte from 7-byte (6x7 = 42 > 32).
183  */
184 #define NUM_NOISE_INPUTS 7
185
186 #define SHIFT_RIGHT(f) ((f)>>1)
187
188 static void ep_add (uint8_t entropy_bits, uint8_t another_random_bit)
189 {
190   uint8_t v = epool[ep_count];
191
192   /* CRC-16-CCITT's Polynomial is: x^16 + x^12 + x^5 + 1 */
193   epool[(ep_count - 12)& 0x0f] ^= v;
194   epool[(ep_count - 5)& 0x0f] ^= v;
195   epool[ep_count] = SHIFT_RIGHT (v) ^ entropy_bits;
196
197   if ((v&1) || another_random_bit)
198     epool[ep_count] ^= 0xff;
199
200   ep_count = (ep_count + 1) & 0x0f;
201 }
202
203 #define FNV_INIT        2166136261U
204 #define FNV_PRIME       16777619
205
206 static uint32_t fnv32_hash (const uint8_t *buf, int len)
207 {
208   uint32_t v = FNV_INIT;
209   int i;
210
211   for (i = 0; i < len; i++)
212     {
213       v ^= buf[i];
214       v *= FNV_PRIME;
215     }
216
217   return v;
218 }
219
220 #define PROBABILITY_50_BY_TICK() ((SysTick->VAL & 0x02) != 0)
221
222 static uint32_t ep_output (void)
223 {
224   int i;
225   uint8_t buf[NUM_NOISE_INPUTS];
226   uint8_t *p = buf;
227
228   /*
229    * NUM_NOISE_INPUTS is seven.
230    *
231    * There are sixteen bytes in the CRC-16 buffer.  We use seven
232    * outputs of CRC-16 buffer for final output.  There are two parts;
233    * former 4 outputs which will be used directly, and latter 3
234    * outputs which will be used with feedback loop.
235    */
236
237   /* At some probability, use latter 3 outputs of CRC-16 buffer */
238   for (i = NUM_NOISE_INPUTS - 1; i >= 4; i--)
239     if (PROBABILITY_50_BY_TICK ())
240       *p++ = epool[(ep_count+i) & 0x0f] ^ epool[(ep_count+i-4) & 0x0f];
241
242   /* Use former 4 outputs of CRC-16 buffer */
243   for (i = 3; i >= 0; i--)
244     *p++ = epool[(ep_count+i) & 0x0f];
245
246   return fnv32_hash (buf, p - buf);
247 }
248
249
250 /*
251  * Ring buffer, filled by generator, consumed by neug_get routine.
252  */
253 struct rng_rb {
254   uint32_t *buf;
255   Mutex m;
256   CondVar data_available;
257   CondVar space_available;
258   uint8_t head, tail;
259   uint8_t size;
260   unsigned int full :1;
261   unsigned int empty :1;
262 };
263
264 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
265 {
266   rb->buf = p;
267   rb->size = size;
268   chMtxInit (&rb->m);
269   chCondInit (&rb->data_available);
270   chCondInit (&rb->space_available);
271   rb->head = rb->tail = 0;
272   rb->full = 0;
273   rb->empty = 1;
274 }
275
276 static void rb_add (struct rng_rb *rb, uint32_t v)
277 {
278   rb->buf[rb->tail++] = v;
279   if (rb->tail == rb->size)
280     rb->tail = 0;
281   if (rb->tail == rb->head)
282     rb->full = 1;
283   rb->empty = 0;
284 }
285
286 static uint32_t rb_del (struct rng_rb *rb)
287 {
288   uint32_t v = rb->buf[rb->head++];
289
290   if (rb->head == rb->size)
291     rb->head = 0;
292   if (rb->head == rb->tail)
293     rb->empty = 1;
294   rb->full = 0;
295
296   return v;
297 }
298
299 /**
300  * @brief  Random number generation from ADC sampling.
301  * @param  RB: Pointer to ring buffer structure
302  * @return -1 when failure, 0 otherwise.
303  * @note   Called holding the mutex, with RB->full == 0.
304  *         Keep generating until RB->full == 1.
305  */
306 static int rng_gen (struct rng_rb *rb)
307 {
308   static uint8_t round = 0;
309   uint8_t b;
310
311   while (1)
312     {
313       chEvtWaitOne (ADC_DATA_AVAILABLE);
314
315       /* Got, ADC sampling data */
316       round++;
317       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
318            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
319            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
320            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
321
322       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
323
324       /*
325        * Put a random byte to entropy pool.
326        */
327       ep_add (b, PROBABILITY_50_BY_TICK ());
328
329       if ((round % NUM_NOISE_INPUTS) == 0)
330         {                           /* We have enough entropy in the pool.  */
331           uint32_t v = ep_output (); /* Get the random bits from the pool.  */
332
333           /* Mix the random bits from the pool with the output of PRNG.  */
334           tmt_one_step ();
335           v ^= tmt_value ();
336
337           /* We got the final random bits, add it to the ring buffer.  */
338           rb_add (rb, v);
339           round = 0;
340           if (rb->full)
341             /* fully generated */
342             break;
343         }
344     }
345
346   return 0;                     /* success */
347 }
348
349 /**
350  * @brief Random number generation thread.
351  */
352 static msg_t rng (void *arg)
353 {
354   struct rng_rb *rb = (struct rng_rb *)arg;
355
356   rng_thread = chThdSelf ();
357
358   adcStart (&ADCD1, NULL);
359   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
360
361   while (1)
362     {
363       chMtxLock (&rb->m);
364       while (rb->full)
365         chCondWait (&rb->space_available);
366       rng_gen (rb);
367       chCondSignal (&rb->data_available);
368       chMtxUnlock ();
369     }
370
371   return 0;
372 }
373
374 static struct rng_rb the_ring_buffer;
375 static WORKING_AREA(wa_rng, 128);
376
377 /**
378  * @brief Initialize NeuG.
379  */
380 void
381 neug_init (uint32_t *buf, uint8_t size)
382 {
383   struct rng_rb *rb = &the_ring_buffer;
384
385   tmt_init (0);
386   rb_init (rb, buf, size);
387   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
388 }
389
390 /**
391  * @breif Flush random bytes.
392  */
393 void
394 neug_flush (void)
395 {
396   struct rng_rb *rb = &the_ring_buffer;
397
398   chMtxLock (&rb->m);
399   while (!rb->empty)
400     (void)rb_del (rb);
401   chCondSignal (&rb->space_available);
402   chMtxUnlock ();
403 }
404
405 /**
406  * @breif Set seed to PRNG
407  */
408 void
409 neug_prng_reseed (void)
410 {
411   uint32_t seed = ep_output ();
412
413   tmt_init (seed);
414   neug_flush ();
415 }
416
417 /**
418  * @brief  Wakes up RNG thread to generate random numbers.
419  */
420 void
421 neug_kick_filling (void)
422 {
423   struct rng_rb *rb = &the_ring_buffer;
424
425   chMtxLock (&rb->m);
426   if (!rb->full)
427     chCondSignal (&rb->space_available);
428   chMtxUnlock ();
429 }
430
431 /**
432  * @brief  Get random word (32-bit) from NeuG.
433  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
434  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
435  *         it is needed to call neug_kick_filling later.
436  */
437 uint32_t
438 neug_get (int kick)
439 {
440   struct rng_rb *rb = &the_ring_buffer;
441   uint32_t v;
442
443   chMtxLock (&rb->m);
444   while (rb->empty)
445     chCondWait (&rb->data_available);
446   v = rb_del (rb);
447   if (kick)
448     chCondSignal (&rb->space_available);
449   chMtxUnlock ();
450
451   return v;
452 }
453
454 void
455 neug_wait_full (void)
456 {
457   struct rng_rb *rb = &the_ring_buffer;
458
459   chMtxLock (&rb->m);
460   while (!rb->full)
461     chCondWait (&rb->data_available);
462   chMtxUnlock ();
463 }