Date: Tue, 8 Oct 1996 13:05:59 +0400 (MSD) From: "=?KOI8-R?Q?=E1=CE=C4=D2=C5=CA_=FE=C5=D2=CE=CF=D7?=" (Andrey A. Chernov) <ache@nagual.ru> To: current@freebsd.org (FreeBSD-current) Subject: Round #2 random() fix for review Message-ID: <199610080906.NAA00842@nagual.ru>
next in thread | raw e-mail | index | archive | help
*** random.c.orig Sat Oct 5 20:41:57 1996
--- random.c Tue Oct 8 12:08:24 1996
***************
*** 122,128 ****
/*
* Initially, everything is set up as if from:
*
! * initstate(1, &randtbl, 128);
*
* Note that this initialization takes advantage of the fact that srandom()
* advances the front and rear pointers 10*rand_deg times, and hence the
--- 122,128 ----
/*
* Initially, everything is set up as if from:
*
! * initstate(1, randtbl, 128);
*
* Note that this initialization takes advantage of the fact that srandom()
* advances the front and rear pointers 10*rand_deg times, and hence the
***************
*** 135,146 ****
static long randtbl[DEG_3 + 1] = {
TYPE_3,
0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd,
0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88,
0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc,
0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
! 0x27fb47b9,
};
/*
--- 135,157 ----
static long randtbl[DEG_3 + 1] = {
TYPE_3,
+ #ifndef USE_WEAK_SEEDING
+ 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05,
+ 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454,
+ 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471,
+ 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1,
+ 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41,
+ 0xf3bec5da
+ #else /* USE_WEAK_SEEDING */
+ /* Historic implementation compatibility */
+ /* The random sequences do not vary much with the seed */
0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5,
0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd,
0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88,
0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc,
0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b,
! 0x27fb47b9
! #endif /* USE_WEAK_SEEDING */
};
/*
***************
*** 176,181 ****
--- 187,221 ----
static int rand_sep = SEP_3;
static long *end_ptr = &randtbl[DEG_3 + 1];
+ static inline long good_rand __P((long));
+
+ static inline long good_rand (x)
+ register long x;
+ {
+ #ifndef USE_WEAK_SEEDING
+ /*
+ * Compute x = (7^5 * x) mod (2^31 - 1)
+ * wihout overflowing 31 bits:
+ * (2^31 - 1) = 127773 * (7^5) + 2836
+ * From "Random number generators: good ones are hard to find",
+ * Park and Miller, Communications of the ACM, vol. 31, no. 10,
+ * October 1988, p. 1195.
+ */
+ register long hi, lo;
+
+ hi = x / 127773;
+ lo = x % 127773;
+ x = 16807 * lo - 2836 * hi;
+ if (x <= 0)
+ x += 0x7fffffff;
+ return (x);
+ #else /* USE_WEAK_SEEDING */
+ /* Historic implementation compatibility */
+ /* The random sequences do not vary much with the seed */
+ return (1103515245 * x + 12345);
+ #endif /* USE_WEAK_SEEDING */
+ }
+
/*
* srandom:
*
***************
*** 192,206 ****
srandom(x)
unsigned int x;
{
! register int i, j;
if (rand_type == TYPE_0)
state[0] = x;
else {
- j = 1;
state[0] = x;
for (i = 1; i < rand_deg; i++)
! state[i] = 1103515245 * state[i - 1] + 12345;
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; i++)
--- 232,245 ----
srandom(x)
unsigned int x;
{
! register int i;
if (rand_type == TYPE_0)
state[0] = x;
else {
state[0] = x;
for (i = 1; i < rand_deg; i++)
! state[i] = good_rand(state[i - 1]);
fptr = &state[rand_sep];
rptr = &state[0];
for (i = 0; i < 10 * rand_deg; i++)
***************
*** 349,355 ****
long i;
if (rand_type == TYPE_0)
! i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff;
else {
*fptr += *rptr;
i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */
--- 388,394 ----
long i;
if (rand_type == TYPE_0)
! i = state[0] = good_rand(state[0]) & 0x7fffffff;
else {
*fptr += *rptr;
i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */
*** random.3.orig Tue Oct 8 12:49:59 1996
--- random.3 Tue Oct 8 12:58:48 1996
***************
*** 82,96 ****
will produce a random binary
value.
.Pp
! Unlike
! .Xr srand ,
! .Fn srandom
! does not return the old seed; the reason for this is that the amount of
! state information used is much more than a single word. (Two other
! routines are provided to deal with restarting/changing random
! number generators). Like
.Xr rand 3 ,
- however,
.Fn random
will by default produce a sequence of numbers that can be duplicated
by calling
--- 82,89 ----
will produce a random binary
value.
.Pp
! Like
.Xr rand 3 ,
.Fn random
will by default produce a sequence of numbers that can be duplicated
by calling
***************
*** 161,171 ****
detects that the state information has been garbled, error
messages are printed on the standard error output.
.Sh SEE ALSO
! .Xr rand 3
.Sh HISTORY
These
functions appeared in
.Bx 4.2 .
.Sh BUGS
About 2/3 the speed of
.Xr rand 3 .
--- 154,171 ----
detects that the state information has been garbled, error
messages are printed on the standard error output.
.Sh SEE ALSO
! .Xr rand 3 ,
! .Xr srand 3
.Sh HISTORY
These
functions appeared in
.Bx 4.2 .
.Sh BUGS
+ .Pp
About 2/3 the speed of
.Xr rand 3 .
+ .Pp
+ Original implementation changed to fix seeding weakness problem:
+ the random sequences do not vary much with the seed. Now
+ better pseudo-random number generator used for initial state
+ calculation.
--
Andrey A. Chernov
<ache@nagual.ru>
http://www.nagual.ru/~ache/
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199610080906.NAA00842>