1 /* $OpenBSD: random.c,v 1.16 2012/03/21 12:36:49 millert Exp $ */
2 /*
3 * Copyright (c) 1983 Regents of the University of California.
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the University nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 * SUCH DAMAGE.
29 */
30
31 #include <sys/param.h>
32 #include <sys/time.h>
33 #include <fcntl.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <unistd.h>
37
38 __RCSID("$MirOS: src/lib/libc/stdlib/random.c,v 1.4 2014/02/19 23:01:19 tg Exp $");
39
40 /*
41 * random.c:
42 *
43 * An improved random number generation package. In addition to the standard
44 * rand()/srand() like interface, this package also has a special state info
45 * interface. The initstate() routine is called with a seed, an array of
46 * bytes, and a count of how many bytes are being passed in; this array is
47 * then initialized to contain information for random number generation with
48 * that much state information. Good sizes for the amount of state
49 * information are 32, 64, 128, and 256 bytes. The state can be switched by
50 * calling the setstate() routine with the same array as was initiallized
51 * with initstate(). By default, the package runs with 128 bytes of state
52 * information and generates far better random numbers than a linear
53 * congruential generator. If the amount of state information is less than
54 * 32 bytes, a simple linear congruential R.N.G. is used.
55 *
56 * Internally, the state information is treated as an array of int32_t; the
57 * zeroeth element of the array is the type of R.N.G. being used (small
58 * integer); the remainder of the array is the state information for the
59 * R.N.G. Thus, 32 bytes of state information will give 7 int32_ts worth of
60 * state information, which will allow a degree seven polynomial. (Note:
61 * the zeroeth word of state information also has some other information
62 * stored in it -- see setstate() for details).
63 *
64 * The random number generation technique is a linear feedback shift register
65 * approach, employing trinomials (since there are fewer terms to sum up that
66 * way). In this approach, the least significant bit of all the numbers in
67 * the state table will act as a linear feedback shift register, and will
68 * have period 2^deg - 1 (where deg is the degree of the polynomial being
69 * used, assuming that the polynomial is irreducible and primitive). The
70 * higher order bits will have longer periods, since their values are also
71 * influenced by pseudo-random carries out of the lower bits. The total
72 * period of the generator is approximately deg*(2**deg - 1); thus doubling
73 * the amount of state information has a vast influence on the period of the
74 * generator. Note: the deg*(2**deg - 1) is an approximation only good for
75 * large deg, when the period of the shift register is the dominant factor.
76 * With deg equal to seven, the period is actually much longer than the
77 * 7*(2**7 - 1) predicted by this formula.
78 */
79
80 /*
81 * For each of the currently supported random number generators, we have a
82 * break value on the amount of state information (you need at least this
83 * many bytes of state info to support this random number generator), a degree
84 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and
85 * the separation between the two lower order coefficients of the trinomial.
86 */
87 #define TYPE_0 0 /* linear congruential */
88 #define BREAK_0 8
89 #define DEG_0 0
90 #define SEP_0 0
91
92 #define TYPE_1 1 /* x**7 + x**3 + 1 */
93 #define BREAK_1 32
94 #define DEG_1 7
95 #define SEP_1 3
96
97 #define TYPE_2 2 /* x**15 + x + 1 */
98 #define BREAK_2 64
99 #define DEG_2 15
100 #define SEP_2 1
101
102 #define TYPE_3 3 /* x**31 + x**3 + 1 */
103 #define BREAK_3 128
104 #define DEG_3 31
105 #define SEP_3 3
106
107 #define TYPE_4 4 /* x**63 + x + 1 */
108 #define BREAK_4 256
109 #define DEG_4 63
110 #define SEP_4 1
111
112 /*
113 * Array versions of the above information to make code run faster --
114 * relies on fact that TYPE_i == i.
115 */
116 #define MAX_TYPES 5 /* max number of types above */
117
118 static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 };
119 static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
120
121 /*
122 * Initially, everything is set up as if from:
123 *
124 * initstate(1, &randtbl, 128);
125 *
126 * Note that this initialization takes advantage of the fact that srandom()
127 * advances the front and rear pointers 10*rand_deg times, and hence the
128 * rear pointer which starts at 0 will also end up at zero; thus the zeroeth
129 * element of the state information, which contains info about the current
130 * position of the rear pointer is just
131 *
132 * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3.
133 */
134
135 static int32_t randtbl[DEG_3 + 1] = {
136 TYPE_3,
137 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05,
138 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454,
139 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471,
140 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
141 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
142 0xf3bec5da,
143 };
144
145 /*
146 * fptr and rptr are two pointers into the state info, a front and a rear
147 * pointer. These two pointers are always rand_sep places aparts, as they
148 * cycle cyclically through the state information. (Yes, this does mean we
149 * could get away with just one pointer, but the code for random() is more
150 * efficient this way). The pointers are left positioned as they would be
151 * from the call
152 *
153 * initstate(1, randtbl, 128);
154 *
155 * (The position of the rear pointer, rptr, is really 0 (as explained above
156 * in the initialization of randtbl) because the state table pointer is set
157 * to point to randtbl[1] (as explained below).
158 */
159 static int32_t *fptr = &randtbl[SEP_3 + 1];
160 static int32_t *rptr = &randtbl[1];
161
162 /*
163 * The following things are the pointer to the state information table, the
164 * type of the current generator, the degree of the current polynomial being
165 * used, and the separation between the two pointers. Note that for efficiency
166 * of random(), we remember the first location of the state information, not
167 * the zeroeth. Hence it is valid to access state[-1], which is used to
168 * store the type of the R.N.G. Also, we remember the last location, since
169 * this is more efficient than indexing every time to find the address of
170 * the last element to see if the front and rear pointers have wrapped.
171 */
172 static int32_t *state = &randtbl[1];
173 static int32_t *end_ptr = &randtbl[DEG_3 + 1];
174 static int rand_type = TYPE_3;
175 static int rand_deg = DEG_3;
176 static int rand_sep = SEP_3;
177
178 /*
179 * srandom:
180 *
181 * Initialize the random number generator based on the given seed. If the
182 * type is the trivial no-state-information type, just remember the seed.
183 * Otherwise, initializes state[] based on the given "seed" via a linear
184 * congruential generator. Then, the pointers are set to known locations
185 * that are exactly rand_sep places apart. Lastly, it cycles the state
186 * information a given number of times to get rid of any initial dependencies
187 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[]
188 * for default usage relies on values produced by this routine.
189 */
190 void
srandom(unsigned int x)191 srandom(unsigned int x)
192 {
193 int i;
194 int32_t test;
195 div_t val;
196
197 if (rand_type == TYPE_0)
198 state[0] = x;
199 else {
200 /* A seed of 0 would result in state[] always being zero. */
201 state[0] = x ? x : 1;
202 for (i = 1; i < rand_deg; i++) {
203 /*
204 * Implement the following, without overflowing 31 bits:
205 *
206 * state[i] = (16807 * state[i - 1]) % 2147483647;
207 *
208 * 2^31-1 (prime) = 2147483647 = 127773*16807+2836
209 */
210 val = div(state[i-1], 127773);
211 test = 16807 * val.rem - 2836 * val.quot;
212 state[i] = test + (test < 0 ? 2147483647 : 0);
213 }
214 fptr = &state[rand_sep];
215 rptr = &state[0];
216 for (i = 0; i < 10 * rand_deg; i++)
217 (void)random();
218 }
219 }
220 __warn_references(srandom, "srandom is insecure; use the arc4random family API instead");
221
222 /*
223 * srandomdev:
224 *
225 * Many programs choose the seed value in a totally predictable manner.
226 * This often causes problems. We seed the generator using the much
227 * more secure arc4random_buf(3) interface.
228 * Note that this particular seeding procedure can generate states
229 * which are impossible to reproduce by calling srandom() with any
230 * value, since the succeeding terms in the state buffer are no longer
231 * derived from the LC algorithm applied to a fixed seed.
232 */
233 void
srandomdev(void)234 srandomdev(void)
235 {
236 size_t len;
237
238 if (rand_type == TYPE_0)
239 len = sizeof(state[0]);
240 else
241 len = rand_deg * sizeof(state[0]);
242
243 arc4random_buf((void *)state, len);
244
245 if (rand_type != TYPE_0) {
246 fptr = &state[rand_sep];
247 rptr = &state[0];
248 }
249 }
250 __warn_references(srandomdev, "srandomdev is insecure; use the arc4random family API instead");
251
252 /*
253 * initstate:
254 *
255 * Initialize the state information in the given array of n bytes for future
256 * random number generation. Based on the number of bytes we are given, and
257 * the break values for the different R.N.G.'s, we choose the best (largest)
258 * one we can and set things up for it. srandom() is then called to
259 * initialize the state information.
260 *
261 * Note that on return from srandom(), we set state[-1] to be the type
262 * multiplexed with the current value of the rear pointer; this is so
263 * successive calls to initstate() won't lose this information and will be
264 * able to restart with setstate().
265 *
266 * Note: the first thing we do is save the current state, if any, just like
267 * setstate() so that it doesn't matter when initstate is called.
268 *
269 * Returns a pointer to the old state.
270 */
271 char *
initstate(u_int seed,char * arg_state,size_t n)272 initstate(u_int seed, char *arg_state, size_t n)
273 {
274 char *ostate = (char *)(&state[-1]);
275
276 if (rand_type == TYPE_0)
277 state[-1] = rand_type;
278 else
279 state[-1] = MAX_TYPES * (rptr - state) + rand_type;
280 if (n < BREAK_0)
281 return(NULL);
282 if (n < BREAK_1) {
283 rand_type = TYPE_0;
284 rand_deg = DEG_0;
285 rand_sep = SEP_0;
286 } else if (n < BREAK_2) {
287 rand_type = TYPE_1;
288 rand_deg = DEG_1;
289 rand_sep = SEP_1;
290 } else if (n < BREAK_3) {
291 rand_type = TYPE_2;
292 rand_deg = DEG_2;
293 rand_sep = SEP_2;
294 } else if (n < BREAK_4) {
295 rand_type = TYPE_3;
296 rand_deg = DEG_3;
297 rand_sep = SEP_3;
298 } else {
299 rand_type = TYPE_4;
300 rand_deg = DEG_4;
301 rand_sep = SEP_4;
302 }
303 state = &(((int32_t *)arg_state)[1]); /* first location */
304 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */
305 srandom(seed);
306 if (rand_type == TYPE_0)
307 state[-1] = rand_type;
308 else
309 state[-1] = MAX_TYPES*(rptr - state) + rand_type;
310 return(ostate);
311 }
312 __warn_references(initstate, "initstate is insecure; use the arc4random family API instead");
313
314 /*
315 * setstate:
316 *
317 * Restore the state from the given state array.
318 *
319 * Note: it is important that we also remember the locations of the pointers
320 * in the current state information, and restore the locations of the pointers
321 * from the old state information. This is done by multiplexing the pointer
322 * location into the zeroeth word of the state information.
323 *
324 * Note that due to the order in which things are done, it is OK to call
325 * setstate() with the same state as the current state.
326 *
327 * Returns a pointer to the old state information.
328 */
329 char *
setstate(const char * arg_state)330 setstate(const char *arg_state)
331 {
332 int32_t *new_state = (int32_t *)arg_state;
333 int32_t type = new_state[0] % MAX_TYPES;
334 int32_t rear = new_state[0] / MAX_TYPES;
335 char *ostate = (char *)(&state[-1]);
336
337 if (rand_type == TYPE_0)
338 state[-1] = rand_type;
339 else
340 state[-1] = MAX_TYPES * (rptr - state) + rand_type;
341 switch(type) {
342 case TYPE_0:
343 case TYPE_1:
344 case TYPE_2:
345 case TYPE_3:
346 case TYPE_4:
347 rand_type = type;
348 rand_deg = degrees[type];
349 rand_sep = seps[type];
350 break;
351 default:
352 return(NULL);
353 }
354 state = &new_state[1];
355 if (rand_type != TYPE_0) {
356 rptr = &state[rear];
357 fptr = &state[(rear + rand_sep) % rand_deg];
358 }
359 end_ptr = &state[rand_deg]; /* set end_ptr too */
360 return(ostate);
361 }
362 __warn_references(setstate, "setstate is insecure; use the arc4random family API instead");
363
364 /*
365 * random:
366 *
367 * If we are using the trivial TYPE_0 R.N.G., just do the old linear
368 * congruential bit. Otherwise, we do our fancy trinomial stuff, which is
369 * the same in all the other cases due to all the global variables that have
370 * been set up. The basic operation is to add the number at the rear pointer
371 * into the one at the front pointer. Then both pointers are advanced to
372 * the next location cyclically in the table. The value returned is the sum
373 * generated, reduced to 31 bits by throwing away the "least random" low bit.
374 *
375 * Note: the code takes advantage of the fact that both the front and
376 * rear pointers can't wrap on the same call by not testing the rear
377 * pointer if the front one has wrapped.
378 *
379 * Returns a 31-bit random number.
380 */
381 long
random(void)382 random(void)
383 {
384 int32_t i;
385
386 if (rand_type == TYPE_0)
387 i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff;
388 else {
389 *fptr += *rptr;
390 i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */
391 if (++fptr >= end_ptr) {
392 fptr = state;
393 ++rptr;
394 } else if (++rptr >= end_ptr)
395 rptr = state;
396 }
397 return((long)i);
398 }
399 __warn_references(random, "random is insecure; use the arc4random family API instead");
400