Improve seeding, the random sequence did not vary match

with the seed. Old variant will be available via libcompat soon.

2 files changed, 75 insertions, 14 deletions

diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3
index d1b8208..dd85711 100644
--- a/lib/libc/stdlib/random.3
+++ b/lib/libc/stdlib/random.3
@@ -82,15 +82,8 @@ are usable.  For example,
 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
+Like
 .Xr rand 3 ,
-however,
 .Fn random
 will by default produce a sequence of numbers that can be duplicated
 by calling
@@ -161,11 +154,29 @@ is called with less than 8 bytes of state information, or if
 detects that the state information has been garbled, error
 messages are printed on the standard error output.
 .Sh SEE ALSO
-.Xr rand 3
+.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
+The historical implementation used to have a very weak seeding; the
+random sequence did not vary much with the seed.  For compatibility
+reasons, this implementation has been made available until the
+next FreeBSD release
+via the
+functions
+.Fn orandom ,
+.Fn osrandom ,
+.Fn oinitstate
+and
+.Fn osetstate
+from the compatibility library,
+.Em libcompat .
+The current implementation employs a better pseudo-random number
+generator for the initial state calculation.
diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c
index fa89f82..d1ec971 100644
--- a/lib/libc/stdlib/random.c
+++ b/lib/libc/stdlib/random.c
@@ -35,6 +35,14 @@
 static char sccsid[] = "@(#)random.c	8.1 (Berkeley) 6/4/93";
 #endif /* LIBC_SCCS and not lint */
 
+#ifdef COMPAT_WEAK_SEEDING
+#define USE_WEAK_SEEDING
+#define random orandom
+#define srandom osrandom
+#define initstate oinitstate
+#define setstate osetstate
+#endif
+
 #include <stdio.h>
 #include <stdlib.h>
 
@@ -122,7 +130,7 @@ static int seps [MAX_TYPES] =	{ SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
 /*
  * Initially, everything is set up as if from:
  *
- *	initstate(1, &randtbl, 128);
+ *	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,12 +143,23 @@ static int seps [MAX_TYPES] =	{ SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 };
 
 static long randtbl[DEG_3 + 1] = {
 	TYPE_3,
+#ifdef  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,
+#else   /* !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
+#endif  /* !USE_WEAK_SEEDING */
 };
 
 /*
@@ -176,6 +195,38 @@ static int rand_deg = DEG_3;
 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;
+{
+#ifdef  USE_WEAK_SEEDING
+/*
+ * Historic implementation compatibility.
+ * The random sequences do not vary much with the seed,
+ * even with overflowing.
+ */
+	return (1103515245 * x + 12345);
+#else   /* !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);
+#endif  /* !USE_WEAK_SEEDING */
+}
+
 /*
  * srandom:
  *
@@ -192,15 +243,14 @@ void
 srandom(x)
 	unsigned int x;
 {
-	register int i, j;
+	register int i;
 
 	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;
+			state[i] = good_rand(state[i - 1]);
 		fptr = &state[rand_sep];
 		rptr = &state[0];
 		for (i = 0; i < 10 * rand_deg; i++)
@@ -349,7 +399,7 @@ random()
 	long i;
 
 	if (rand_type == TYPE_0)
-		i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff;
+		i = state[0] = good_rand(state[0]) & 0x7fffffff;
 	else {
 		*fptr += *rptr;
 		i = (*fptr >> 1) & 0x7fffffff;	/* chucking least random bit */