1/* $OpenBSD: random.c,v 1.31 2017/11/28 06:55:49 tb 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 <fcntl.h> 32#include <stdio.h> 33#include <stdlib.h> 34#include <unistd.h> 35 36#include "thread_private.h" 37 38/* 39 * random.c: 40 * 41 * An improved random number generation package. In addition to the standard 42 * rand()/srand() like interface, this package also has a special state info 43 * interface. The initstate() routine is called with a seed, an array of 44 * bytes, and a count of how many bytes are being passed in; this array is 45 * then initialized to contain information for random number generation with 46 * that much state information. Good sizes for the amount of state 47 * information are 32, 64, 128, and 256 bytes. The state can be switched by 48 * calling the setstate() routine with the same array as was initiallized 49 * with initstate(). By default, the package runs with 128 bytes of state 50 * information and generates far better random numbers than a linear 51 * congruential generator. If the amount of state information is less than 52 * 32 bytes, a simple linear congruential R.N.G. is used. 53 * 54 * Internally, the state information is treated as an array of int32_t; the 55 * zeroeth element of the array is the type of R.N.G. being used (small 56 * integer); the remainder of the array is the state information for the 57 * R.N.G. Thus, 32 bytes of state information will give 7 int32_ts worth of 58 * state information, which will allow a degree seven polynomial. (Note: 59 * the zeroeth word of state information also has some other information 60 * stored in it -- see setstate() for details). 61 * 62 * The random number generation technique is a linear feedback shift register 63 * approach, employing trinomials (since there are fewer terms to sum up that 64 * way). In this approach, the least significant bit of all the numbers in 65 * the state table will act as a linear feedback shift register, and will 66 * have period 2^deg - 1 (where deg is the degree of the polynomial being 67 * used, assuming that the polynomial is irreducible and primitive). The 68 * higher order bits will have longer periods, since their values are also 69 * influenced by pseudo-random carries out of the lower bits. The total 70 * period of the generator is approximately deg*(2**deg - 1); thus doubling 71 * the amount of state information has a vast influence on the period of the 72 * generator. Note: the deg*(2**deg - 1) is an approximation only good for 73 * large deg, when the period of the shift register is the dominant factor. 74 * With deg equal to seven, the period is actually much longer than the 75 * 7*(2**7 - 1) predicted by this formula. 76 */ 77 78/* 79 * For each of the currently supported random number generators, we have a 80 * break value on the amount of state information (you need at least this 81 * many bytes of state info to support this random number generator), a degree 82 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and 83 * the separation between the two lower order coefficients of the trinomial. 84 */ 85#define TYPE_0 0 /* linear congruential */ 86#define BREAK_0 8 87#define DEG_0 0 88#define SEP_0 0 89 90#define TYPE_1 1 /* x**7 + x**3 + 1 */ 91#define BREAK_1 32 92#define DEG_1 7 93#define SEP_1 3 94 95#define TYPE_2 2 /* x**15 + x + 1 */ 96#define BREAK_2 64 97#define DEG_2 15 98#define SEP_2 1 99 100#define TYPE_3 3 /* x**31 + x**3 + 1 */ 101#define BREAK_3 128 102#define DEG_3 31 103#define SEP_3 3 104 105#define TYPE_4 4 /* x**63 + x + 1 */ 106#define BREAK_4 256 107#define DEG_4 63 108#define SEP_4 1 109 110/* 111 * Array versions of the above information to make code run faster -- 112 * relies on fact that TYPE_i == i. 113 */ 114#define MAX_TYPES 5 /* max number of types above */ 115 116static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 117static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; 118 119/* 120 * Initially, everything is set up as if from: 121 * 122 * initstate(1, &randtbl, 128); 123 * 124 * Note that this initialization takes advantage of the fact that srandom() 125 * advances the front and rear pointers 10*rand_deg times, and hence the 126 * rear pointer which starts at 0 will also end up at zero; thus the zeroeth 127 * element of the state information, which contains info about the current 128 * position of the rear pointer is just 129 * 130 * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3. 131 */ 132 133static int32_t randtbl[DEG_3 + 1] = { 134 TYPE_3, 135 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, 136 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, 137 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, 138 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, 139 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, 140 0xf3bec5da, 141}; 142 143/* 144 * fptr and rptr are two pointers into the state info, a front and a rear 145 * pointer. These two pointers are always rand_sep places aparts, as they 146 * cycle cyclically through the state information. (Yes, this does mean we 147 * could get away with just one pointer, but the code for random() is more 148 * efficient this way). The pointers are left positioned as they would be 149 * from the call 150 * 151 * initstate(1, randtbl, 128); 152 * 153 * (The position of the rear pointer, rptr, is really 0 (as explained above 154 * in the initialization of randtbl) because the state table pointer is set 155 * to point to randtbl[1] (as explained below). 156 */ 157static int32_t *fptr = &randtbl[SEP_3 + 1]; 158static int32_t *rptr = &randtbl[1]; 159 160/* 161 * The following things are the pointer to the state information table, the 162 * type of the current generator, the degree of the current polynomial being 163 * used, and the separation between the two pointers. Note that for efficiency 164 * of random(), we remember the first location of the state information, not 165 * the zeroeth. Hence it is valid to access state[-1], which is used to 166 * store the type of the R.N.G. Also, we remember the last location, since 167 * this is more efficient than indexing every time to find the address of 168 * the last element to see if the front and rear pointers have wrapped. 169 */ 170static int32_t *state = &randtbl[1]; 171static int32_t *end_ptr = &randtbl[DEG_3 + 1]; 172static int rand_type = TYPE_3; 173static int rand_deg = DEG_3; 174static int rand_sep = SEP_3; 175 176static int random_deterministic; 177 178static void *random_mutex; 179static long random_l(void); 180 181#define LOCK() _MUTEX_LOCK(&random_mutex) 182#define UNLOCK() _MUTEX_UNLOCK(&random_mutex) 183 184/* 185 * srandom: 186 * 187 * Initialize the random number generator based on the given seed. If the 188 * type is the trivial no-state-information type, just remember the seed. 189 * Otherwise, initializes state[] based on the given "seed" via a linear 190 * congruential generator. Then, the pointers are set to known locations 191 * that are exactly rand_sep places apart. Lastly, it cycles the state 192 * information a given number of times to get rid of any initial dependencies 193 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 194 * for default usage relies on values produced by this routine. 195 */ 196static void 197srandom_l(unsigned int x) 198{ 199 int i; 200 int32_t test; 201 div_t val; 202 203 random_deterministic = 1; 204 if (rand_type == TYPE_0) 205 state[0] = x; 206 else { 207 /* A seed of 0 would result in state[] always being zero. */ 208 state[0] = x ? x : 1; 209 for (i = 1; i < rand_deg; i++) { 210 /* 211 * Implement the following, without overflowing 31 bits: 212 * 213 * state[i] = (16807 * state[i - 1]) % 2147483647; 214 * 215 * 2^31-1 (prime) = 2147483647 = 127773*16807+2836 216 */ 217 val = div(state[i-1], 127773); 218 test = 16807 * val.rem - 2836 * val.quot; 219 state[i] = test + (test < 0 ? 2147483647 : 0); 220 } 221 fptr = &state[rand_sep]; 222 rptr = &state[0]; 223 for (i = 0; i < 10 * rand_deg; i++) 224 (void)random_l(); 225 } 226} 227 228void 229srandom(unsigned int x) 230{ 231 random_deterministic = 0; 232} 233 234void 235srandomdev(void) 236{ 237 random_deterministic = 0; /* back to the default */ 238} 239 240void 241srandom_deterministic(unsigned int x) 242{ 243 LOCK(); 244 srandom_l(x); 245 UNLOCK(); 246} 247 248/* 249 * initstate: 250 * 251 * Initialize the state information in the given array of n bytes for future 252 * random number generation. Based on the number of bytes we are given, and 253 * the break values for the different R.N.G.'s, we choose the best (largest) 254 * one we can and set things up for it. srandom() is then called to 255 * initialize the state information. 256 * 257 * Note that on return from srandom(), we set state[-1] to be the type 258 * multiplexed with the current value of the rear pointer; this is so 259 * successive calls to initstate() won't lose this information and will be 260 * able to restart with setstate(). 261 * 262 * Note: the first thing we do is save the current state, if any, just like 263 * setstate() so that it doesn't matter when initstate is called. 264 * 265 * Returns a pointer to the old state. 266 */ 267char * 268initstate(u_int seed, char *arg_state, size_t n) 269{ 270 char *ostate = (char *)(&state[-1]); 271 272 LOCK(); 273 random_deterministic = 1; 274 if (rand_type == TYPE_0) 275 state[-1] = rand_type; 276 else 277 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 278 if (n < BREAK_0) { 279 UNLOCK(); 280 return(NULL); 281 } 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_l(seed); 306 if (rand_type == TYPE_0) 307 state[-1] = rand_type; 308 else 309 state[-1] = MAX_TYPES*(rptr - state) + rand_type; 310 UNLOCK(); 311 return(ostate); 312} 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 */ 329char * 330setstate(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 LOCK(); 338 random_deterministic = 1; 339 if (rand_type == TYPE_0) 340 state[-1] = rand_type; 341 else 342 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 343 switch(type) { 344 case TYPE_0: 345 case TYPE_1: 346 case TYPE_2: 347 case TYPE_3: 348 case TYPE_4: 349 rand_type = type; 350 rand_deg = degrees[type]; 351 rand_sep = seps[type]; 352 break; 353 default: 354 UNLOCK(); 355 return(NULL); 356 } 357 state = &new_state[1]; 358 if (rand_type != TYPE_0) { 359 rptr = &state[rear]; 360 fptr = &state[(rear + rand_sep) % rand_deg]; 361 } 362 end_ptr = &state[rand_deg]; /* set end_ptr too */ 363 UNLOCK(); 364 return(ostate); 365} 366 367/* 368 * random: 369 * 370 * If we are using the trivial TYPE_0 R.N.G., just do the old linear 371 * congruential bit. Otherwise, we do our fancy trinomial stuff, which is 372 * the same in all the other cases due to all the global variables that have 373 * been set up. The basic operation is to add the number at the rear pointer 374 * into the one at the front pointer. Then both pointers are advanced to 375 * the next location cyclically in the table. The value returned is the sum 376 * generated, reduced to 31 bits by throwing away the "least random" low bit. 377 * 378 * Note: the code takes advantage of the fact that both the front and 379 * rear pointers can't wrap on the same call by not testing the rear 380 * pointer if the front one has wrapped. 381 * 382 * Returns a 31-bit random number. 383 */ 384static long 385random_l(void) 386{ 387 int32_t i; 388 389 if (random_deterministic == 0) 390 return arc4random() & 0x7fffffff; 391 392 if (rand_type == TYPE_0) 393 i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff; 394 else { 395 *fptr += *rptr; 396 i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ 397 if (++fptr >= end_ptr) { 398 fptr = state; 399 ++rptr; 400 } else if (++rptr >= end_ptr) 401 rptr = state; 402 } 403 return((long)i); 404} 405 406long 407random(void) 408{ 409 long r; 410 LOCK(); 411 r = random_l(); 412 UNLOCK(); 413 return r; 414} 415 416#if defined(APIWARN) 417__warn_references(random, 418 "random() may return deterministic values, is that what you want?"); 419#endif 420