1 /* 2 * Copyright (c) 1986 Regents of the University of California. 3 * All rights reserved. The Berkeley software License Agreement 4 * specifies the terms and conditions for redistribution. 5 */ 6 7 #ifndef lint 8 static char sccsid[] = "@(#)rnd.c 5.1 (Berkeley) 12/09/86"; 9 #endif not lint 10 11 /* 12 * code for when the good (berkeley) random number generator is around 13 */ 14 15 rnd(num) 16 { 17 return (random() % num); 18 } 19 20 srnd(num) 21 { 22 srandom(num); 23 } 24 25 #ifdef NO_RANDOM 26 27 #ifndef lint 28 static char sccsid[] = "@(#)random.c 4.2 (Berkeley) 83/01/02"; 29 #endif 30 31 #include <stdio.h> 32 33 /* 34 * random.c: 35 * An improved random number generation package. In addition to the standard 36 * rand()/srand() like interface, this package also has a special state info 37 * interface. The initstate() routine is called with a seed, an array of 38 * bytes, and a count of how many bytes are being passed in; this array is then 39 * initialized to contain information for random number generation with that 40 * much state information. Good sizes for the amount of state information are 41 * 32, 64, 128, and 256 bytes. The state can be switched by calling the 42 * setstate() routine with the same array as was initiallized with initstate(). 43 * By default, the package runs with 128 bytes of state information and 44 * generates far better random numbers than a linear congruential generator. 45 * If the amount of state information is less than 32 bytes, a simple linear 46 * congruential R.N.G. is used. 47 * Internally, the state information is treated as an array of longs; the 48 * zeroeth element of the array is the type of R.N.G. being used (small 49 * integer); the remainder of the array is the state information for the 50 * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of 51 * state information, which will allow a degree seven polynomial. (Note: the 52 * zeroeth word of state information also has some other information stored 53 * in it -- see setstate() for details). 54 * The random number generation technique is a linear feedback shift register 55 * approach, employing trinomials (since there are fewer terms to sum up that 56 * way). In this approach, the least significant bit of all the numbers in 57 * the state table will act as a linear feedback shift register, and will have 58 * period 2^deg - 1 (where deg is the degree of the polynomial being used, 59 * assuming that the polynomial is irreducible and primitive). The higher 60 * order bits will have longer periods, since their values are also influenced 61 * by pseudo-random carries out of the lower bits. The total period of the 62 * generator is approximately deg*(2**deg - 1); thus doubling the amount of 63 * state information has a vast influence on the period of the generator. 64 * Note: the deg*(2**deg - 1) is an approximation only good for large deg, 65 * when the period of the shift register is the dominant factor. With deg 66 * equal to seven, the period is actually much longer than the 7*(2**7 - 1) 67 * predicted by this formula. 68 */ 69 70 71 72 /* 73 * For each of the currently supported random number generators, we have a 74 * break value on the amount of state information (you need at least this 75 * many bytes of state info to support this random number generator), a degree 76 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and 77 * the separation between the two lower order coefficients of the trinomial. 78 */ 79 80 #define TYPE_0 0 /* linear congruential */ 81 #define BREAK_0 8 82 #define DEG_0 0 83 #define SEP_0 0 84 85 #define TYPE_1 1 /* x**7 + x**3 + 1 */ 86 #define BREAK_1 32 87 #define DEG_1 7 88 #define SEP_1 3 89 90 #define TYPE_2 2 /* x**15 + x + 1 */ 91 #define BREAK_2 64 92 #define DEG_2 15 93 #define SEP_2 1 94 95 #define TYPE_3 3 /* x**31 + x**3 + 1 */ 96 #define BREAK_3 128 97 #define DEG_3 31 98 #define SEP_3 3 99 100 #define TYPE_4 4 /* x**63 + x + 1 */ 101 #define BREAK_4 256 102 #define DEG_4 63 103 #define SEP_4 1 104 105 106 /* 107 * Array versions of the above information to make code run faster -- relies 108 * on fact that TYPE_i == i. 109 */ 110 111 #define MAX_TYPES 5 /* max number of types above */ 112 113 static int degrees[ MAX_TYPES ] = { DEG_0, DEG_1, DEG_2, 114 DEG_3, DEG_4 }; 115 116 static int seps[ MAX_TYPES ] = { SEP_0, SEP_1, SEP_2, 117 SEP_3, SEP_4 }; 118 119 120 121 /* 122 * Initially, everything is set up as if from : 123 * initstate( 1, &randtbl, 128 ); 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 * MAX_TYPES*(rptr - state) + TYPE_3 == TYPE_3. 130 */ 131 132 static long randtbl[ DEG_3 + 1 ] = { TYPE_3, 133 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 134 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, 135 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, 136 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 137 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, 138 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, 139 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 140 0xf5ad9d0e, 0x8999220b, 0x27fb47b9 }; 141 142 /* 143 * fptr and rptr are two pointers into the state info, a front and a rear 144 * pointer. These two pointers are always rand_sep places aparts, as they cycle 145 * cyclically through the state information. (Yes, this does mean we could get 146 * away with just one pointer, but the code for random() is more efficient this 147 * way). The pointers are left positioned as they would be from the call 148 * initstate( 1, randtbl, 128 ) 149 * (The position of the rear pointer, rptr, is really 0 (as explained above 150 * in the initialization of randtbl) because the state table pointer is set 151 * to point to randtbl[1] (as explained below). 152 */ 153 154 static long *fptr = &randtbl[ SEP_3 + 1 ]; 155 static long *rptr = &randtbl[ 1 ]; 156 157 158 159 /* 160 * The following things are the pointer to the state information table, 161 * the type of the current generator, the degree of the current polynomial 162 * being used, and the separation between the two pointers. 163 * Note that for efficiency of random(), we remember the first location of 164 * the state information, not the zeroeth. Hence it is valid to access 165 * state[-1], which is used to store the type of the R.N.G. 166 * Also, we remember the last location, since this is more efficient than 167 * indexing every time to find the address of the last element to see if 168 * the front and rear pointers have wrapped. 169 */ 170 171 static long *state = &randtbl[ 1 ]; 172 173 static int rand_type = TYPE_3; 174 static int rand_deg = DEG_3; 175 static int rand_sep = SEP_3; 176 177 static long *end_ptr = &randtbl[ DEG_3 + 1 ]; 178 179 180 181 /* 182 * srandom: 183 * Initialize the random number generator based on the given seed. If the 184 * type is the trivial no-state-information type, just remember the seed. 185 * Otherwise, initializes state[] based on the given "seed" via a linear 186 * congruential generator. Then, the pointers are set to known locations 187 * that are exactly rand_sep places apart. Lastly, it cycles the state 188 * information a given number of times to get rid of any initial dependencies 189 * introduced by the L.C.R.N.G. 190 * Note that the initialization of randtbl[] for default usage relies on 191 * values produced by this routine. 192 */ 193 194 srandom( x ) 195 196 unsigned x; 197 { 198 register int i, j; 199 200 if( rand_type == TYPE_0 ) { 201 state[ 0 ] = x; 202 } 203 else { 204 j = 1; 205 state[ 0 ] = x; 206 for( i = 1; i < rand_deg; i++ ) { 207 state[i] = 1103515245*state[i - 1] + 12345; 208 } 209 fptr = &state[ rand_sep ]; 210 rptr = &state[ 0 ]; 211 for( i = 0; i < 10*rand_deg; i++ ) random(); 212 } 213 } 214 215 216 217 /* 218 * initstate: 219 * Initialize the state information in the given array of n bytes for 220 * future random number generation. Based on the number of bytes we 221 * are given, and the break values for the different R.N.G.'s, we choose 222 * the best (largest) one we can and set things up for it. srandom() is 223 * then called to initialize the state information. 224 * Note that on return from srandom(), we set state[-1] to be the type 225 * multiplexed with the current value of the rear pointer; this is so 226 * successive calls to initstate() won't lose this information and will 227 * be able to restart with setstate(). 228 * Note: the first thing we do is save the current state, if any, just like 229 * setstate() so that it doesn't matter when initstate is called. 230 * Returns a pointer to the old state. 231 */ 232 233 char * 234 initstate( seed, arg_state, n ) 235 236 unsigned seed; /* seed for R. N. G. */ 237 char *arg_state; /* pointer to state array */ 238 int n; /* # bytes of state info */ 239 { 240 register char *ostate = (char *)( &state[ -1 ] ); 241 242 if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; 243 else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; 244 if( n < BREAK_1 ) { 245 if( n < BREAK_0 ) { 246 fprintf( stderr, "initstate: not enough state (%d bytes) with which to do jack; ignored.\n" ); 247 return; 248 } 249 rand_type = TYPE_0; 250 rand_deg = DEG_0; 251 rand_sep = SEP_0; 252 } 253 else { 254 if( n < BREAK_2 ) { 255 rand_type = TYPE_1; 256 rand_deg = DEG_1; 257 rand_sep = SEP_1; 258 } 259 else { 260 if( n < BREAK_3 ) { 261 rand_type = TYPE_2; 262 rand_deg = DEG_2; 263 rand_sep = SEP_2; 264 } 265 else { 266 if( n < BREAK_4 ) { 267 rand_type = TYPE_3; 268 rand_deg = DEG_3; 269 rand_sep = SEP_3; 270 } 271 else { 272 rand_type = TYPE_4; 273 rand_deg = DEG_4; 274 rand_sep = SEP_4; 275 } 276 } 277 } 278 } 279 state = &( ( (long *)arg_state )[1] ); /* first location */ 280 end_ptr = &state[ rand_deg ]; /* must set end_ptr before srandom */ 281 srandom( seed ); 282 if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; 283 else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; 284 return( ostate ); 285 } 286 287 288 289 /* 290 * setstate: 291 * Restore the state from the given state array. 292 * Note: it is important that we also remember the locations of the pointers 293 * in the current state information, and restore the locations of the pointers 294 * from the old state information. This is done by multiplexing the pointer 295 * location into the zeroeth word of the state information. 296 * Note that due to the order in which things are done, it is OK to call 297 * setstate() with the same state as the current state. 298 * Returns a pointer to the old state information. 299 */ 300 301 char * 302 setstate( arg_state ) 303 304 char *arg_state; 305 { 306 register long *new_state = (long *)arg_state; 307 register int type = new_state[0]%MAX_TYPES; 308 register int rear = new_state[0]/MAX_TYPES; 309 char *ostate = (char *)( &state[ -1 ] ); 310 311 if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; 312 else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; 313 switch( type ) { 314 case TYPE_0: 315 case TYPE_1: 316 case TYPE_2: 317 case TYPE_3: 318 case TYPE_4: 319 rand_type = type; 320 rand_deg = degrees[ type ]; 321 rand_sep = seps[ type ]; 322 break; 323 324 default: 325 fprintf( stderr, "setstate: state info has been munged; not changed.\n" ); 326 } 327 state = &new_state[ 1 ]; 328 if( rand_type != TYPE_0 ) { 329 rptr = &state[ rear ]; 330 fptr = &state[ (rear + rand_sep)%rand_deg ]; 331 } 332 end_ptr = &state[ rand_deg ]; /* set end_ptr too */ 333 return( ostate ); 334 } 335 336 337 338 /* 339 * random: 340 * If we are using the trivial TYPE_0 R.N.G., just do the old linear 341 * congruential bit. Otherwise, we do our fancy trinomial stuff, which is the 342 * same in all ther other cases due to all the global variables that have been 343 * set up. The basic operation is to add the number at the rear pointer into 344 * the one at the front pointer. Then both pointers are advanced to the next 345 * location cyclically in the table. The value returned is the sum generated, 346 * reduced to 31 bits by throwing away the "least random" low bit. 347 * Note: the code takes advantage of the fact that both the front and 348 * rear pointers can't wrap on the same call by not testing the rear 349 * pointer if the front one has wrapped. 350 * Returns a 31-bit random number. 351 */ 352 353 long 354 random() 355 { 356 long i; 357 358 if( rand_type == TYPE_0 ) { 359 i = state[0] = ( state[0]*1103515245 + 12345 )&0x7fffffff; 360 } 361 else { 362 *fptr += *rptr; 363 i = (*fptr >> 1)&0x7fffffff; /* chucking least random bit */ 364 if( ++fptr >= end_ptr ) { 365 fptr = state; 366 ++rptr; 367 } 368 else { 369 if( ++rptr >= end_ptr ) rptr = state; 370 } 371 } 372 return( i ); 373 } 374 375 #endif NO_RANDOM 376