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