Changeset 743
- Timestamp:
- Sep 29, 2003, 1:39:48 AM (22 years ago)
- Location:
- trunk/src/emx
- Files:
-
- 1 added
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/emx/bsd/libc/random.c
-
Property cvs2svn:cvs-rev
changed from
1.1
to1.2
r742 r743 1 1 /* 2 * Copyright (c) 1983 Regents of the University of California.3 * All rights reserved.2 * Copyright (c) 1983, 1993 3 * The Regents of the University of California. All rights reserved. 4 4 * 5 5 * Redistribution and use in source and binary forms, with or without … … 33 33 34 34 #if defined(LIBC_SCCS) && !defined(lint) 35 static char sccsid[] = "@(#)random.c 5.9 (Berkeley) 2/23/91";35 static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; 36 36 #endif /* LIBC_SCCS and not lint */ 37 37 #include <sys/cdefs.h> 38 __FBSDID("$FreeBSD: src/lib/libc/stdlib/random.c,v 1.23 2003/08/10 17:49:55 ache Exp $"); 39 40 #ifndef __EMX__ 41 #include "namespace.h" 42 #endif 43 #include <sys/time.h> /* for srandomdev() */ 44 #include <fcntl.h> /* for srandomdev() */ 38 45 #include <stdio.h> 39 46 #include <stdlib.h> 40 #if defined (__EMX__) 41 #include "emxbsd.h" 47 #include <unistd.h> /* for srandomdev() */ 48 #ifndef __EMX__ 49 #include "un-namespace.h" 42 50 #endif 43 51 … … 65 73 * the zeroeth word of state information also has some other information 66 74 * stored in it -- see setstate() for details). 67 * 75 * 68 76 * The random number generation technique is a linear feedback shift register 69 77 * approach, employing trinomials (since there are fewer terms to sum up that … … 77 85 * the amount of state information has a vast influence on the period of the 78 86 * generator. Note: the deg*(2**deg - 1) is an approximation only good for 79 * large deg, when the period of the shift registeris the dominant factor.87 * large deg, when the period of the shift is the dominant factor. 80 88 * With deg equal to seven, the period is actually much longer than the 81 89 * 7*(2**7 - 1) predicted by this formula. 90 * 91 * Modified 28 December 1994 by Jacob S. Rosenberg. 92 * The following changes have been made: 93 * All references to the type u_int have been changed to unsigned long. 94 * All references to type int have been changed to type long. Other 95 * cleanups have been made as well. A warning for both initstate and 96 * setstate has been inserted to the effect that on Sparc platforms 97 * the 'arg_state' variable must be forced to begin on word boundaries. 98 * This can be easily done by casting a long integer array to char *. 99 * The overall logic has been left STRICTLY alone. This software was 100 * tested on both a VAX and Sun SpacsStation with exactly the same 101 * results. The new version and the original give IDENTICAL results. 102 * The new version is somewhat faster than the original. As the 103 * documentation says: "By default, the package runs with 128 bytes of 104 * state information and generates far better random numbers than a linear 105 * congruential generator. If the amount of state information is less than 106 * 32 bytes, a simple linear congruential R.N.G. is used." For a buffer of 107 * 128 bytes, this new version runs about 19 percent faster and for a 16 108 * byte buffer it is about 5 percent faster. 82 109 */ 83 110 … … 120 147 #define MAX_TYPES 5 /* max number of types above */ 121 148 122 static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 123 static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; 149 #ifdef USE_WEAK_SEEDING 150 #define NSHUFF 0 151 #else /* !USE_WEAK_SEEDING */ 152 #define NSHUFF 50 /* to drop some "seed -> 1st value" linearity */ 153 #endif /* !USE_WEAK_SEEDING */ 154 155 static long degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; 156 static long seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; 124 157 125 158 /* 126 159 * Initially, everything is set up as if from: 127 160 * 128 * initstate(1, &randtbl, 128);161 * initstate(1, randtbl, 128); 129 162 * 130 163 * Note that this initialization takes advantage of the fact that srandom() … … 139 172 static long randtbl[DEG_3 + 1] = { 140 173 TYPE_3, 174 #ifdef USE_WEAK_SEEDING 175 /* Historic implementation compatibility */ 176 /* The random sequences do not vary much with the seed */ 141 177 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5, 142 178 0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, … … 145 181 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, 146 182 0x27fb47b9, 183 #else /* !USE_WEAK_SEEDING */ 184 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, 185 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, 186 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, 187 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, 188 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, 189 0xf3bec5da 190 #endif /* !USE_WEAK_SEEDING */ 147 191 }; 148 192 … … 175 219 */ 176 220 static long *state = &randtbl[1]; 177 static intrand_type = TYPE_3;178 static intrand_deg = DEG_3;179 static intrand_sep = SEP_3;221 static long rand_type = TYPE_3; 222 static long rand_deg = DEG_3; 223 static long rand_sep = SEP_3; 180 224 static long *end_ptr = &randtbl[DEG_3 + 1]; 225 226 static inline long good_rand(long); 227 228 static inline long good_rand (x) 229 long x; 230 { 231 #ifdef USE_WEAK_SEEDING 232 /* 233 * Historic implementation compatibility. 234 * The random sequences do not vary much with the seed, 235 * even with overflowing. 236 */ 237 return (1103515245 * x + 12345); 238 #else /* !USE_WEAK_SEEDING */ 239 /* 240 * Compute x = (7^5 * x) mod (2^31 - 1) 241 * wihout overflowing 31 bits: 242 * (2^31 - 1) = 127773 * (7^5) + 2836 243 * From "Random number generators: good ones are hard to find", 244 * Park and Miller, Communications of the ACM, vol. 31, no. 10, 245 * October 1988, p. 1195. 246 */ 247 long hi, lo; 248 249 /* Can't be initialized with 0, so use another value. */ 250 if (x == 0) 251 x = 123459876; 252 hi = x / 127773; 253 lo = x % 127773; 254 x = 16807 * lo - 2836 * hi; 255 if (x < 0) 256 x += 0x7fffffff; 257 return (x); 258 #endif /* !USE_WEAK_SEEDING */ 259 } 181 260 182 261 /* … … 194 273 void 195 274 srandom(x) 196 u _intx;275 unsigned long x; 197 276 { 198 register int i, j; 199 277 long i, lim; 278 279 state[0] = x; 200 280 if (rand_type == TYPE_0) 201 state[0] = x;281 lim = NSHUFF; 202 282 else { 203 j = 1;204 state[0] = x;205 283 for (i = 1; i < rand_deg; i++) 206 state[i] = 1103515245 * state[i - 1] + 12345;284 state[i] = good_rand(state[i - 1]); 207 285 fptr = &state[rand_sep]; 208 286 rptr = &state[0]; 209 for (i = 0; i < 10 * rand_deg; i++) 210 (void)random(); 287 lim = 10 * rand_deg; 288 } 289 for (i = 0; i < lim; i++) 290 (void)random(); 291 } 292 293 /* 294 * srandomdev: 295 * 296 * Many programs choose the seed value in a totally predictable manner. 297 * This often causes problems. We seed the generator using the much more 298 * secure random(4) interface. Note that this particular seeding 299 * procedure can generate states which are impossible to reproduce by 300 * calling srandom() with any value, since the succeeding terms in the 301 * state buffer are no longer derived from the LC algorithm applied to 302 * a fixed seed. 303 */ 304 void 305 srandomdev() 306 { 307 int fd, done; 308 size_t len; 309 310 if (rand_type == TYPE_0) 311 len = sizeof state[0]; 312 else 313 len = rand_deg * sizeof state[0]; 314 315 done = 0; 316 fd = _open("/dev/random", O_RDONLY, 0); 317 if (fd >= 0) { 318 if (_read(fd, (void *) state, len) == (ssize_t) len) 319 done = 1; 320 _close(fd); 321 } 322 323 if (!done) { 324 struct timeval tv; 325 unsigned long junk; 326 327 gettimeofday(&tv, NULL); 328 srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk); 329 return; 330 } 331 332 if (rand_type != TYPE_0) { 333 fptr = &state[rand_sep]; 334 rptr = &state[0]; 211 335 } 212 336 } … … 220 344 * one we can and set things up for it. srandom() is then called to 221 345 * initialize the state information. 222 * 346 * 223 347 * Note that on return from srandom(), we set state[-1] to be the type 224 348 * multiplexed with the current value of the rear pointer; this is so 225 349 * successive calls to initstate() won't lose this information and will be 226 350 * able to restart with setstate(). 227 * 351 * 228 352 * Note: the first thing we do is save the current state, if any, just like 229 353 * setstate() so that it doesn't matter when initstate is called. 230 354 * 231 355 * Returns a pointer to the old state. 356 * 357 * Note: The Sparc platform requires that arg_state begin on a long 358 * word boundary; otherwise a bus error will occur. Even so, lint will 359 * complain about mis-alignment, but you should disregard these messages. 232 360 */ 233 361 char * 234 362 initstate(seed, arg_state, n) 235 u _int seed;/* seed for R.N.G. */363 unsigned long seed; /* seed for R.N.G. */ 236 364 char *arg_state; /* pointer to state array */ 237 intn; /* # bytes of state info */365 long n; /* # bytes of state info */ 238 366 { 239 register char *ostate = (char *)(&state[-1]); 367 char *ostate = (char *)(&state[-1]); 368 long *long_arg_state = (long *) arg_state; 240 369 241 370 if (rand_type == TYPE_0) … … 245 374 if (n < BREAK_0) { 246 375 (void)fprintf(stderr, 247 "random: not enough state (% d bytes); ignored.\n", n);376 "random: not enough state (%ld bytes); ignored.\n", n); 248 377 return(0); 249 378 } … … 269 398 rand_sep = SEP_4; 270 399 } 271 state = &(((long *)arg_state)[1]);/* first location */400 state = (long *) (long_arg_state + 1); /* first location */ 272 401 end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ 273 402 srandom(seed); 274 403 if (rand_type == TYPE_0) 275 state[-1] = rand_type;404 long_arg_state[0] = rand_type; 276 405 else 277 state[-1] = MAX_TYPES*(rptr - state) + rand_type;406 long_arg_state[0] = MAX_TYPES * (rptr - state) + rand_type; 278 407 return(ostate); 279 408 } … … 293 422 * 294 423 * Returns a pointer to the old state information. 424 * 425 * Note: The Sparc platform requires that arg_state begin on a long 426 * word boundary; otherwise a bus error will occur. Even so, lint will 427 * complain about mis-alignment, but you should disregard these messages. 295 428 */ 296 429 char * 297 430 setstate(arg_state) 298 char *arg_state; 431 char *arg_state; /* pointer to state array */ 299 432 { 300 register long *new_state = (long *)arg_state;301 register inttype = new_state[0] % MAX_TYPES;302 register intrear = new_state[0] / MAX_TYPES;433 long *new_state = (long *) arg_state; 434 long type = new_state[0] % MAX_TYPES; 435 long rear = new_state[0] / MAX_TYPES; 303 436 char *ostate = (char *)(&state[-1]); 304 437 … … 321 454 "random: state info corrupted; not changed.\n"); 322 455 } 323 state = &new_state[1];456 state = (long *) (new_state + 1); 324 457 if (rand_type != TYPE_0) { 325 458 rptr = &state[rear]; … … 351 484 { 352 485 long i; 353 354 if (rand_type == TYPE_0) 355 i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff; 356 else { 357 *fptr += *rptr; 358 i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ 359 if (++fptr >= end_ptr) { 360 fptr = state; 361 ++rptr; 362 } else if (++rptr >= end_ptr) 363 rptr = state; 486 long *f, *r; 487 488 if (rand_type == TYPE_0) { 489 i = state[0]; 490 state[0] = i = (good_rand(i)) & 0x7fffffff; 491 } else { 492 /* 493 * Use local variables rather than static variables for speed. 494 */ 495 f = fptr; r = rptr; 496 *f += *r; 497 i = (*f >> 1) & 0x7fffffff; /* chucking least random bit */ 498 if (++f >= end_ptr) { 499 f = state; 500 ++r; 501 } 502 else if (++r >= end_ptr) { 503 r = state; 504 } 505 506 fptr = f; rptr = r; 364 507 } 365 508 return(i); -
Property cvs2svn:cvs-rev
changed from
-
trunk/src/emx/include/stdlib.h
-
Property cvs2svn:cvs-rev
changed from
1.9
to1.10
r742 r743 149 149 extern char **environ; 150 150 151 extern __const__ char * __const__ sys_errlist[]; 151 extern __const__ char * __const__ sys_errlist[]; 152 152 extern __const__ int sys_nerr; 153 153 … … 174 174 long ulimit (int, ...); 175 175 176 /* BSD - start */ 176 177 int heapsort (void *, size_t, size_t, 177 178 int (*)(__const__ void *, __const__ void *)); /* BSD */ 178 char *initstate (unsigned, char *, int); /* BSD */ 179 long random (void); /* BSD */ 180 char *setstate (char *); /* BSD */ 181 void srandom (unsigned); /* BSD */ 179 char *initstate(unsigned long /* XSI requires u_int */, char *, long); 180 char *setstate(/* const */ char *); 181 long random(void); 182 void srandom(unsigned long); 183 void srandomdev(void); 184 /* BSD - end */ 182 185 183 186 char *itoa (int, char *, int); … … 197 200 198 201 extern char **_environ; 199 extern __const__ char * __const__ _sys_errlist[]; 202 extern __const__ char * __const__ _sys_errlist[]; 200 203 extern __const__ int _sys_nerr; 201 204 -
Property cvs2svn:cvs-rev
changed from
Note:
See TracChangeset
for help on using the changeset viewer.