1/* 2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright --- 18 unchanged lines hidden (view full) --- 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34#if defined(LIBC_SCCS) && !defined(lint) |
35static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; |
36#endif /* LIBC_SCCS and not lint */ 37 38#ifdef COMPAT_WEAK_SEEDING 39#define USE_WEAK_SEEDING 40#define random orandom 41#define srandom osrandom 42#define initstate oinitstate 43#define setstate osetstate --- 35 unchanged lines hidden (view full) --- 79 * higher order bits will have longer periods, since their values are also 80 * influenced by pseudo-random carries out of the lower bits. The total 81 * period of the generator is approximately deg*(2**deg - 1); thus doubling 82 * the amount of state information has a vast influence on the period of the 83 * generator. Note: the deg*(2**deg - 1) is an approximation only good for 84 * large deg, when the period of the shift register is the dominant factor. 85 * With deg equal to seven, the period is actually much longer than the 86 * 7*(2**7 - 1) predicted by this formula. |
87 * 88 * Modified 28 December 1994 by Jacob S. Rosenberg. 89 * The following changes have been made: 90 * All references to the type u_int have been changed to unsigned long. 91 * All references to type int have been changed to type long. Other 92 * cleanups have been made as well. A warning for both initstate and 93 * setstate has been inserted to the effect that on Sparc platforms 94 * the 'arg_state' variable must be forced to begin on word boundaries. 95 * This can be easily done by casting a long integer array to char *. 96 * The overall logic has been left STRICTLY alone. This software was 97 * tested on both a VAX and Sun SpacsStation with exactly the same 98 * results. The new version and the original give IDENTICAL results. 99 * The new version is somewhat faster than the original. As the 100 * documentation says: "By default, the package runs with 128 bytes of 101 * state information and generates far better random numbers than a linear 102 * congruential generator. If the amount of state information is less than 103 * 32 bytes, a simple linear congruential R.N.G. is used." For a buffer of 104 * 128 bytes, this new version runs about 19 percent faster and for a 16 105 * byte buffer it is about 5 percent faster. |
106 */ 107 108/* 109 * For each of the currently supported random number generators, we have a 110 * break value on the amount of state information (you need at least this 111 * many bytes of state info to support this random number generator), a degree 112 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and 113 * the separation between the two lower order coefficients of the trinomial. --- 24 unchanged lines hidden (view full) --- 138#define SEP_4 1 139 140/* 141 * Array versions of the above information to make code run faster -- 142 * relies on fact that TYPE_i == i. 143 */ 144#define MAX_TYPES 5 /* max number of types above */ 145 |
146static long degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 147static long seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; |
148 149/* 150 * Initially, everything is set up as if from: 151 * 152 * initstate(1, randtbl, 128); 153 * 154 * Note that this initialization takes advantage of the fact that srandom() 155 * advances the front and rear pointers 10*rand_deg times, and hence the --- 48 unchanged lines hidden (view full) --- 204 * used, and the separation between the two pointers. Note that for efficiency 205 * of random(), we remember the first location of the state information, not 206 * the zeroeth. Hence it is valid to access state[-1], which is used to 207 * store the type of the R.N.G. Also, we remember the last location, since 208 * this is more efficient than indexing every time to find the address of 209 * the last element to see if the front and rear pointers have wrapped. 210 */ 211static long *state = &randtbl[1]; |
212static long rand_type = TYPE_3; 213static long rand_deg = DEG_3; 214static long rand_sep = SEP_3; |
215static long *end_ptr = &randtbl[DEG_3 + 1]; 216 217static inline long good_rand __P((long)); 218 219static inline long good_rand (x) 220 register long x; 221{ 222#ifdef USE_WEAK_SEEDING --- 32 unchanged lines hidden (view full) --- 255 * congruential generator. Then, the pointers are set to known locations 256 * that are exactly rand_sep places apart. Lastly, it cycles the state 257 * information a given number of times to get rid of any initial dependencies 258 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 259 * for default usage relies on values produced by this routine. 260 */ 261void 262srandom(x) |
263 unsigned long x; |
264{ |
265 register long i; |
266 267 if (rand_type == TYPE_0) 268 state[0] = x; 269 else { 270 state[0] = x; 271 for (i = 1; i < rand_deg; i++) 272 state[i] = good_rand(state[i - 1]); 273 fptr = &state[rand_sep]; --- 16 unchanged lines hidden (view full) --- 290 * multiplexed with the current value of the rear pointer; this is so 291 * successive calls to initstate() won't lose this information and will be 292 * able to restart with setstate(). 293 * 294 * Note: the first thing we do is save the current state, if any, just like 295 * setstate() so that it doesn't matter when initstate is called. 296 * 297 * Returns a pointer to the old state. |
298 * 299 * Note: The Sparc platform requires that arg_state begin on a long 300 * word boundary; otherwise a bus error will occur. Even so, lint will 301 * complain about mis-alignment, but you should disregard these messages. |
302 */ 303char * 304initstate(seed, arg_state, n) |
305 unsigned long seed; /* seed for R.N.G. */ |
306 char *arg_state; /* pointer to state array */ |
307 long n; /* # bytes of state info */ |
308{ 309 register char *ostate = (char *)(&state[-1]); |
310 register long *long_arg_state = (long *) arg_state; |
311 312 if (rand_type == TYPE_0) 313 state[-1] = rand_type; 314 else 315 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 316 if (n < BREAK_0) { 317 (void)fprintf(stderr, |
318 "random: not enough state (%ld bytes); ignored.\n", n); |
319 return(0); 320 } 321 if (n < BREAK_1) { 322 rand_type = TYPE_0; 323 rand_deg = DEG_0; 324 rand_sep = SEP_0; 325 } else if (n < BREAK_2) { 326 rand_type = TYPE_1; --- 7 unchanged lines hidden (view full) --- 334 rand_type = TYPE_3; 335 rand_deg = DEG_3; 336 rand_sep = SEP_3; 337 } else { 338 rand_type = TYPE_4; 339 rand_deg = DEG_4; 340 rand_sep = SEP_4; 341 } |
342 state = (long *) (long_arg_state + 1); /* first location */ |
343 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ 344 srandom(seed); 345 if (rand_type == TYPE_0) |
346 long_arg_state[0] = rand_type; |
347 else |
348 long_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type; |
349 return(ostate); 350} 351 352/* 353 * setstate: 354 * 355 * Restore the state from the given state array. 356 * 357 * Note: it is important that we also remember the locations of the pointers 358 * in the current state information, and restore the locations of the pointers 359 * from the old state information. This is done by multiplexing the pointer 360 * location into the zeroeth word of the state information. 361 * 362 * Note that due to the order in which things are done, it is OK to call 363 * setstate() with the same state as the current state. 364 * 365 * Returns a pointer to the old state information. |
366 * 367 * Note: The Sparc platform requires that arg_state begin on a long 368 * word boundary; otherwise a bus error will occur. Even so, lint will 369 * complain about mis-alignment, but you should disregard these messages. |
370 */ 371char * 372setstate(arg_state) |
373 char *arg_state; /* pointer to state array */ |
374{ |
375 register long *new_state = (long *) arg_state; 376 register long type = new_state[0] % MAX_TYPES; 377 register long rear = new_state[0] / MAX_TYPES; |
378 char *ostate = (char *)(&state[-1]); 379 380 if (rand_type == TYPE_0) 381 state[-1] = rand_type; 382 else 383 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 384 switch(type) { 385 case TYPE_0: --- 4 unchanged lines hidden (view full) --- 390 rand_type = type; 391 rand_deg = degrees[type]; 392 rand_sep = seps[type]; 393 break; 394 default: 395 (void)fprintf(stderr, 396 "random: state info corrupted; not changed.\n"); 397 } |
398 state = (long *) (new_state + 1); |
399 if (rand_type != TYPE_0) { 400 rptr = &state[rear]; 401 fptr = &state[(rear + rand_sep) % rand_deg]; 402 } 403 end_ptr = &state[rand_deg]; /* set end_ptr too */ 404 return(ostate); 405} 406 --- 12 unchanged lines hidden (view full) --- 419 * rear pointers can't wrap on the same call by not testing the rear 420 * pointer if the front one has wrapped. 421 * 422 * Returns a 31-bit random number. 423 */ 424long 425random() 426{ |
427 register long i; 428 register long *f, *r; |
429 |
430 if (rand_type == TYPE_0) { 431 i = state[0]; 432 state[0] = i = (good_rand(i)) & 0x7fffffff; 433 } else { 434 /* 435 * Use local variables rather than static variables for speed. 436 */ 437 f = fptr; r = rptr; 438 *f += *r; 439 i = (*f >> 1) & 0x7fffffff; /* chucking least random bit */ 440 if (++f >= end_ptr) { 441 f = state; 442 ++r; 443 } 444 else if (++r >= end_ptr) { 445 r = state; 446 } 447 448 fptr = f; rptr = r; |
449 } 450 return(i); 451} |