WELL
[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 #define EPOOL_SIZE (64 / sizeof (uint32_t))
87 #define EP_INDEX(cnt, i)  ((cnt + i) & (EPOOL_SIZE - 1))
88 #define EP_INCREMENT(cnt) ((cnt + 15) & (EPOOL_SIZE - 1))
89
90 static uint8_t ep_count;
91 static uint32_t epool[EPOOL_SIZE];
92
93
94 /*
95  * We did an experiment of measuring entropy of ADC output with MUST.
96  * The entropy of a byte by raw sampling of LSBs has more than 6.0 bit/byte.
97  * So, it is considered OK to get 4-byte from 6-byte (6x6 = 36 > 32).
98  */
99 #define NUM_NOISE_INPUTS 6
100
101 static void well512a_step (void)
102 {
103   uint32_t v = epool[ep_count]; /* V0 */
104   uint32_t z1, z2;
105
106   z1  = (v ^ (v << 16));
107   v = epool[EP_INDEX (ep_count, 13)]; /* VM1 */
108   z1 ^= (v ^ (v << 15));
109   v = epool[EP_INDEX (ep_count, 9)]; /* VM2 */
110   z2 = v ^ (v >> 11);
111   v = z1 ^ z2;
112   
113   /* newV1 */
114   epool[ep_count] = v;
115
116   v = (v ^ ((v<<5) & 0xda442d24U));
117   z1 = (z1 ^ (z1 << 18));
118   z2 = (z2 << 28);
119   ep_count = EP_INCREMENT (ep_count);
120
121   /* newV0 */
122   epool[ep_count] ^= (epool[ep_count] << 2) ^ z1 ^ z2 ^ v;
123 }
124
125 #define FNV_INIT        2166136261U
126 #define FNV_PRIME       16777619
127
128 static void ep_add (uint8_t entropy_bits, uint8_t another_random_bit,
129                     uint8_t round)
130 {
131   uint32_t v = FNV_INIT;
132
133   v ^= (another_random_bit << 8) | round;
134   v *= FNV_PRIME;
135   v ^= entropy_bits;
136   v *= FNV_PRIME;
137   v ^= epool[ep_count] & 0xff;
138   v *= FNV_PRIME;
139
140   epool[ep_count] ^= v;
141 }
142
143 static uint32_t ep_output (void)
144 {
145   well512a_step ();
146   well512a_step ();
147   well512a_step ();
148   return epool[ep_count];
149 }
150
151
152 /*
153  * Ring buffer, filled by generator, consumed by neug_get routine.
154  */
155 struct rng_rb {
156   uint32_t *buf;
157   Mutex m;
158   CondVar data_available;
159   CondVar space_available;
160   uint8_t head, tail;
161   uint8_t size;
162   unsigned int full :1;
163   unsigned int empty :1;
164 };
165
166 static void rb_init (struct rng_rb *rb, uint32_t *p, uint8_t size)
167 {
168   rb->buf = p;
169   rb->size = size;
170   chMtxInit (&rb->m);
171   chCondInit (&rb->data_available);
172   chCondInit (&rb->space_available);
173   rb->head = rb->tail = 0;
174   rb->full = 0;
175   rb->empty = 1;
176 }
177
178 static void rb_add (struct rng_rb *rb, uint32_t v)
179 {
180   rb->buf[rb->tail++] = v;
181   if (rb->tail == rb->size)
182     rb->tail = 0;
183   if (rb->tail == rb->head)
184     rb->full = 1;
185   rb->empty = 0;
186 }
187
188 static uint32_t rb_del (struct rng_rb *rb)
189 {
190   uint32_t v = rb->buf[rb->head++];
191
192   if (rb->head == rb->size)
193     rb->head = 0;
194   if (rb->head == rb->tail)
195     rb->empty = 1;
196   rb->full = 0;
197
198   return v;
199 }
200
201 #define PROBABILITY_50_BY_TICK() ((SysTick->VAL & 0x02) != 0)
202
203 /**
204  * @brief  Random number generation from ADC sampling.
205  * @param  RB: Pointer to ring buffer structure
206  * @return -1 when failure, 0 otherwise.
207  * @note   Called holding the mutex, with RB->full == 0.
208  *         Keep generating until RB->full == 1.
209  */
210 static int rng_gen (struct rng_rb *rb)
211 {
212   static uint8_t round = 0;
213   uint8_t b;
214
215   while (1)
216     {
217       chEvtWaitOne (ADC_DATA_AVAILABLE);
218
219       /* Got, ADC sampling data */
220       b = (((samp[0] & 0x01) << 0) | ((samp[1] & 0x01) << 1)
221            | ((samp[2] & 0x01) << 2) | ((samp[3] & 0x01) << 3)
222            | ((samp[4] & 0x01) << 4) | ((samp[5] & 0x01) << 5)
223            | ((samp[6] & 0x01) << 6) | ((samp[7] & 0x01) << 7));
224
225       adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
226
227       /*
228        * Put a random byte to entropy pool.
229        */
230       ep_add (b, PROBABILITY_50_BY_TICK (), round);
231       round++;
232       if ((round % NUM_NOISE_INPUTS) == 0)
233         {                           /* We have enough entropy in the pool.  */
234           uint32_t v = ep_output (); /* Get the random bits from the pool.  */
235
236           /* We got the final random bits, add it to the ring buffer.  */
237           rb_add (rb, v);
238           if (rb->full)
239             /* fully generated */
240             break;
241         }
242     }
243
244   return 0;                     /* success */
245 }
246
247 /**
248  * @brief Random number generation thread.
249  */
250 static msg_t rng (void *arg)
251 {
252   struct rng_rb *rb = (struct rng_rb *)arg;
253
254   rng_thread = chThdSelf ();
255
256   adcStart (&ADCD1, NULL);
257   adcStartConversion (&ADCD1, &adcgrpcfg, samp, ADC_GRP1_BUF_DEPTH);
258
259   while (1)
260     {
261       chMtxLock (&rb->m);
262       while (rb->full)
263         chCondWait (&rb->space_available);
264       rng_gen (rb);
265       chCondSignal (&rb->data_available);
266       chMtxUnlock ();
267     }
268
269   return 0;
270 }
271
272 static struct rng_rb the_ring_buffer;
273 static WORKING_AREA(wa_rng, 128);
274
275 /**
276  * @brief Initialize NeuG.
277  */
278 void
279 neug_init (uint32_t *buf, uint8_t size)
280 {
281   struct rng_rb *rb = &the_ring_buffer;
282
283   rb_init (rb, buf, size);
284   chThdCreateStatic (wa_rng, sizeof (wa_rng), NORMALPRIO, rng, rb);
285 }
286
287 /**
288  * @breif Flush random bytes.
289  */
290 void
291 neug_flush (void)
292 {
293   struct rng_rb *rb = &the_ring_buffer;
294
295   chMtxLock (&rb->m);
296   while (!rb->empty)
297     (void)rb_del (rb);
298   chCondSignal (&rb->space_available);
299   chMtxUnlock ();
300 }
301
302
303 /**
304  * @brief  Wakes up RNG thread to generate random numbers.
305  */
306 void
307 neug_kick_filling (void)
308 {
309   struct rng_rb *rb = &the_ring_buffer;
310
311   chMtxLock (&rb->m);
312   if (!rb->full)
313     chCondSignal (&rb->space_available);
314   chMtxUnlock ();
315 }
316
317 /**
318  * @brief  Get random word (32-bit) from NeuG.
319  * @detail With NEUG_KICK_FILLING, it wakes up RNG thread.
320  *         With NEUG_NO_KICK, it doesn't wake up RNG thread automatically,
321  *         it is needed to call neug_kick_filling later.
322  */
323 uint32_t
324 neug_get (int kick)
325 {
326   struct rng_rb *rb = &the_ring_buffer;
327   uint32_t v;
328
329   chMtxLock (&rb->m);
330   while (rb->empty)
331     chCondWait (&rb->data_available);
332   v = rb_del (rb);
333   if (kick)
334     chCondSignal (&rb->space_available);
335   chMtxUnlock ();
336
337   return v;
338 }
339
340 void
341 neug_wait_full (void)
342 {
343   struct rng_rb *rb = &the_ring_buffer;
344
345   chMtxLock (&rb->m);
346   while (!rb->full)
347     chCondWait (&rb->data_available);
348   chMtxUnlock ();
349 }