change ep_add for feedback shift
[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_EXTSEL_SWSTART | ADC_CR2_TSVREFE | ADC_CR2_CONT,
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 ROTATE(f) (((f)>>1)|(((f)&1)?0x80000000UL:0))
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   if (another_random_bit)
188     {
189       v ^= entropy_bits;
190       epool[ep_count] = ROTATE (v);
191     }
192   else
193     epool[ep_count] = ROTATE (v) ^ entropy_bits;
194
195   ep_count = (ep_count + 1) & 0x0f;
196 }
197
198 #define FNV_INIT        2166136261U
199 #define FNV_PRIME       16777619
200
201 static uint32_t fnv32_hash (const uint8_t *buf, int len)
202 {
203   uint32_t v = FNV_INIT;
204   int i;
205
206   for (i = 0; i < len; i++)
207     {
208       v ^= buf[i];
209       v *= FNV_PRIME;
210     }
211
212   return v;
213 }
214
215 #define PROBABILITY_50_BY_TICK() ((SysTick->VAL & 0x02) != 0)
216
217 static uint32_t ep_output (void)
218 {
219   int i;
220   uint8_t buf[NUM_NOISE_INPUTS];
221   uint8_t *p = buf;
222
223   /*
224    * NUM_NOISE_INPUTS is seven.
225    *
226    * There are sixteen bytes in the CRC-16 buffer.  We use seven
227    * outputs of CRC-16 buffer for final output.  There are two parts;
228    * former 4 outputs which will be used directly, and latter 3
229    * outputs which will be used with feedback loop.
230    */
231
232   /* At some probability, use latter 3 outputs of CRC-16 buffer */
233   for (i = NUM_NOISE_INPUTS - 1; i >= 4; i--)
234     if (PROBABILITY_50_BY_TICK ())
235       *p++ = epool[(ep_count+i) & 0x0f] ^ epool[(ep_count+i-4) & 0x0f];
236
237   /* Use former 4 outputs of CRC-16 buffer */
238   for (i = 3; i >= 0; i--)
239     *p++ = epool[(ep_count+i) & 0x0f];
240
241   return fnv32_hash (buf, p - buf);
242 }
243
244
245 /*
246  * Ring buffer, filled by generator, consumed by neug_get routine.
247  */
248 struct rng_rb {
249   uint32_t *buf;
250   Mutex m;
251   CondVar data_available;
252   CondVar space_available;
253   uint8_t head, tail;
254   uint8_t size;
255   unsigned int full :1;
256   unsigned int empty :1;
257 };
258
259 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
260 {
261   rb->buf = p;
262   rb->size = size;
263   chMtxInit (&rb->m);
264   chCondInit (&rb->data_available);
265   chCondInit (&rb->space_available);
266   rb->head = rb->tail = 0;
267   rb->full = 0;
268   rb->empty = 1;
269 }
270
271 static void rb_add (struct rng_rb *rb, uint32_t v)
272 {
273   rb->buf[rb->tail++] = v;
274   if (rb->tail == rb->size)
275     rb->tail = 0;
276   if (rb->tail == rb->head)
277     rb->full = 1;
278   rb->empty = 0;
279 }
280
281 static uint32_t rb_del (struct rng_rb *rb)
282 {
283   uint32_t v = rb->buf[rb->head++];
284
285   if (rb->head == rb->size)
286     rb->head = 0;
287   if (rb->head == rb->tail)
288     rb->empty = 1;
289   rb->full = 0;
290
291   return v;
292 }
293
294 /**
295  * @brief  Random number generation from ADC sampling.
296  * @param  RB: Pointer to ring buffer structure
297  * @return -1 when failure, 0 otherwise.
298  * @note   Called holding the mutex, with RB->full == 0.
299  *         Keep generating until RB->full == 1.
300  */
301 static int rng_gen (struct rng_rb *rb)
302 {
303   static uint8_t round = 0;
304   uint8_t b;
305
306   while (1)
307     {
308       chEvtWaitOne (ADC_DATA_AVAILABLE);
309
310       /* Got, ADC sampling data */
311       round++;
312       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
313            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
314            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
315            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
316
317       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
318
319       /*
320        * Put a random byte to entropy pool.
321        */
322       ep_add (b, PROBABILITY_50_BY_TICK ());
323
324       if ((round % NUM_NOISE_INPUTS) == 0)
325         {                           /* We have enough entropy in the pool.  */
326           uint32_t v = ep_output (); /* Get the random bits from the pool.  */
327
328           /* Mix the random bits from the pool with the output of PRNG.  */
329           tmt_one_step ();
330           v ^= tmt_value ();
331
332           /* We got the final random bits, add it to the ring buffer.  */
333           rb_add (rb, v);
334           round = 0;
335           if (rb->full)
336             /* fully generated */
337             break;
338         }
339     }
340
341   return 0;                     /* success */
342 }
343
344 /**
345  * @brief Random number generation thread.
346  */
347 static msg_t rng (void *arg)
348 {
349   struct rng_rb *rb = (struct rng_rb *)arg;
350
351   rng_thread = chThdSelf ();
352
353   adcStart (&ADCD1, NULL);
354   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
355
356   while (1)
357     {
358       chMtxLock (&rb->m);
359       while (rb->full)
360         chCondWait (&rb->space_available);
361       rng_gen (rb);
362       chCondSignal (&rb->data_available);
363       chMtxUnlock ();
364     }
365
366   return 0;
367 }
368
369 static struct rng_rb the_ring_buffer;
370 static WORKING_AREA(wa_rng, 128);
371
372 /**
373  * @brief Initialize NeuG.
374  */
375 void
376 neug_init (uint32_t *buf, uint8_t size)
377 {
378   struct rng_rb *rb = &the_ring_buffer;
379
380   tmt_init (0);
381   rb_init (rb, buf, size);
382   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
383 }
384
385 /**
386  * @breif Set seed to PRNG
387  */
388 void
389 neug_prng_reseed (void)
390 {
391   uint32_t seed = ep_output ();
392
393   tmt_init (seed);
394 }
395
396 /**
397  * @brief  Wakes up RNG thread to generate random numbers.
398  */
399 void
400 neug_kick_filling (void)
401 {
402   struct rng_rb *rb = &the_ring_buffer;
403
404   chMtxLock (&rb->m);
405   if (!rb->full)
406     chCondSignal (&rb->space_available);
407   chMtxUnlock ();
408 }
409
410 /**
411  * @brief  Get random word (32-bit) from NeuG.
412  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
413  *         With NEUG_NO_KICK, it doesn't wake up automatically,
414  *         it is needed to call neug_kick_filling later.
415  */
416 uint32_t
417 neug_get (int kick)
418 {
419   struct rng_rb *rb = &the_ring_buffer;
420   uint32_t v;
421
422   chMtxLock (&rb->m);
423   while (rb->empty)
424     chCondWait (&rb->data_available);
425   v = rb_del (rb);
426   if (kick)
427     chCondSignal (&rb->space_available);
428   chMtxUnlock ();
429
430   return v;
431 }