| random.c (18832) | random.c (23662) |
|---|---|
| 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) | 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.1 (Berkeley) 6/4/93"; | 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. | 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. |
|
| 87 */ 88 89/* 90 * For each of the currently supported random number generators, we have a 91 * break value on the amount of state information (you need at least this 92 * many bytes of state info to support this random number generator), a degree 93 * for the polynomial (actually a trinomial) that the R.N.G. is based on, and 94 * the separation between the two lower order coefficients of the trinomial. --- 24 unchanged lines hidden (view full) --- 119#define SEP_4 1 120 121/* 122 * Array versions of the above information to make code run faster -- 123 * relies on fact that TYPE_i == i. 124 */ 125#define MAX_TYPES 5 /* max number of types above */ 126 | 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 |
| 127static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 128static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; | 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 }; |
| 129 130/* 131 * Initially, everything is set up as if from: 132 * 133 * initstate(1, randtbl, 128); 134 * 135 * Note that this initialization takes advantage of the fact that srandom() 136 * advances the front and rear pointers 10*rand_deg times, and hence the --- 48 unchanged lines hidden (view full) --- 185 * used, and the separation between the two pointers. Note that for efficiency 186 * of random(), we remember the first location of the state information, not 187 * the zeroeth. Hence it is valid to access state[-1], which is used to 188 * store the type of the R.N.G. Also, we remember the last location, since 189 * this is more efficient than indexing every time to find the address of 190 * the last element to see if the front and rear pointers have wrapped. 191 */ 192static long *state = &randtbl[1]; | 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]; |
| 193static int rand_type = TYPE_3; 194static int rand_deg = DEG_3; 195static int rand_sep = SEP_3; | 212static long rand_type = TYPE_3; 213static long rand_deg = DEG_3; 214static long rand_sep = SEP_3; |
| 196static long *end_ptr = &randtbl[DEG_3 + 1]; 197 198static inline long good_rand __P((long)); 199 200static inline long good_rand (x) 201 register long x; 202{ 203#ifdef USE_WEAK_SEEDING --- 32 unchanged lines hidden (view full) --- 236 * congruential generator. Then, the pointers are set to known locations 237 * that are exactly rand_sep places apart. Lastly, it cycles the state 238 * information a given number of times to get rid of any initial dependencies 239 * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] 240 * for default usage relies on values produced by this routine. 241 */ 242void 243srandom(x) | 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) |
| 244 unsigned int x; | 263 unsigned long x; |
| 245{ | 264{ |
| 246 register int i; | 265 register long i; |
| 247 248 if (rand_type == TYPE_0) 249 state[0] = x; 250 else { 251 state[0] = x; 252 for (i = 1; i < rand_deg; i++) 253 state[i] = good_rand(state[i - 1]); 254 fptr = &state[rand_sep]; --- 16 unchanged lines hidden (view full) --- 271 * multiplexed with the current value of the rear pointer; this is so 272 * successive calls to initstate() won't lose this information and will be 273 * able to restart with setstate(). 274 * 275 * Note: the first thing we do is save the current state, if any, just like 276 * setstate() so that it doesn't matter when initstate is called. 277 * 278 * Returns a pointer to the old state. | 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. |
|
| 279 */ 280char * 281initstate(seed, arg_state, n) | 302 */ 303char * 304initstate(seed, arg_state, n) |
| 282 unsigned int seed; /* seed for R.N.G. */ | 305 unsigned long seed; /* seed for R.N.G. */ |
| 283 char *arg_state; /* pointer to state array */ | 306 char *arg_state; /* pointer to state array */ |
| 284 int n; /* # bytes of state info */ | 307 long n; /* # bytes of state info */ |
| 285{ 286 register char *ostate = (char *)(&state[-1]); | 308{ 309 register char *ostate = (char *)(&state[-1]); |
| 310 register long *long_arg_state = (long *) arg_state; |
|
| 287 288 if (rand_type == TYPE_0) 289 state[-1] = rand_type; 290 else 291 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 292 if (n < BREAK_0) { 293 (void)fprintf(stderr, | 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, |
| 294 "random: not enough state (%d bytes); ignored.\n", n); | 318 "random: not enough state (%ld bytes); ignored.\n", n); |
| 295 return(0); 296 } 297 if (n < BREAK_1) { 298 rand_type = TYPE_0; 299 rand_deg = DEG_0; 300 rand_sep = SEP_0; 301 } else if (n < BREAK_2) { 302 rand_type = TYPE_1; --- 7 unchanged lines hidden (view full) --- 310 rand_type = TYPE_3; 311 rand_deg = DEG_3; 312 rand_sep = SEP_3; 313 } else { 314 rand_type = TYPE_4; 315 rand_deg = DEG_4; 316 rand_sep = SEP_4; 317 } | 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 } |
| 318 state = &(((long *)arg_state)[1]); /* first location */ | 342 state = (long *) (long_arg_state + 1); /* first location */ |
| 319 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ 320 srandom(seed); 321 if (rand_type == TYPE_0) | 343 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ 344 srandom(seed); 345 if (rand_type == TYPE_0) |
| 322 state[-1] = rand_type; | 346 long_arg_state[0] = rand_type; |
| 323 else | 347 else |
| 324 state[-1] = MAX_TYPES*(rptr - state) + rand_type; | 348 long_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type; |
| 325 return(ostate); 326} 327 328/* 329 * setstate: 330 * 331 * Restore the state from the given state array. 332 * 333 * Note: it is important that we also remember the locations of the pointers 334 * in the current state information, and restore the locations of the pointers 335 * from the old state information. This is done by multiplexing the pointer 336 * location into the zeroeth word of the state information. 337 * 338 * Note that due to the order in which things are done, it is OK to call 339 * setstate() with the same state as the current state. 340 * 341 * Returns a pointer to the old state information. | 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. |
|
| 342 */ 343char * 344setstate(arg_state) | 370 */ 371char * 372setstate(arg_state) |
| 345 char *arg_state; | 373 char *arg_state; /* pointer to state array */ |
| 346{ | 374{ |
| 347 register long *new_state = (long *)arg_state; 348 register int type = new_state[0] % MAX_TYPES; 349 register int rear = new_state[0] / MAX_TYPES; | 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; |
| 350 char *ostate = (char *)(&state[-1]); 351 352 if (rand_type == TYPE_0) 353 state[-1] = rand_type; 354 else 355 state[-1] = MAX_TYPES * (rptr - state) + rand_type; 356 switch(type) { 357 case TYPE_0: --- 4 unchanged lines hidden (view full) --- 362 rand_type = type; 363 rand_deg = degrees[type]; 364 rand_sep = seps[type]; 365 break; 366 default: 367 (void)fprintf(stderr, 368 "random: state info corrupted; not changed.\n"); 369 } | 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 } |
| 370 state = &new_state[1]; | 398 state = (long *) (new_state + 1); |
| 371 if (rand_type != TYPE_0) { 372 rptr = &state[rear]; 373 fptr = &state[(rear + rand_sep) % rand_deg]; 374 } 375 end_ptr = &state[rand_deg]; /* set end_ptr too */ 376 return(ostate); 377} 378 --- 12 unchanged lines hidden (view full) --- 391 * rear pointers can't wrap on the same call by not testing the rear 392 * pointer if the front one has wrapped. 393 * 394 * Returns a 31-bit random number. 395 */ 396long 397random() 398{ | 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{ |
| 399 long i; | 427 register long i; 428 register long *f, *r; |
| 400 | 429 |
| 401 if (rand_type == TYPE_0) 402 i = state[0] = good_rand(state[0]) & 0x7fffffff; 403 else { 404 *fptr += *rptr; 405 i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ 406 if (++fptr >= end_ptr) { 407 fptr = state; 408 ++rptr; 409 } else if (++rptr >= end_ptr) 410 rptr = state; | 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; |
| 411 } 412 return(i); 413} | 449 } 450 return(i); 451} |