Implement a simple xorshift 32bit random number generator

Avoid relying on the system random number generator for our random
shuffle, so that the same seed gives the same results on all systems.
This generator doesn't need to be amazing, just pretty good, so don't
bother with xorshift* or xorshift+, etc.

* src/makeint.h: Declare make_seed() and make_rand().
* src/misc.c (make_seed): Set the seed value for the RNG.
(make_rand): Return the next random number.  If the seed was not set
initialize it first.
* src/shuffle.c (shuffle_set_mode): If we don't get a seed from the
user just leave it unset (0).
(shuffle_deps_recursive): Use make_seed() not srand().
(random_shuffle_array): Use make_rand() not rand().

1 files changed, 29 insertions, 0 deletions

diff --git a/src/misc.c b/src/misc.c
index 8f9be328..48e4cb5e 100644
--- a/src/misc.c
+++ b/src/misc.c
@@ -78,6 +78,35 @@ make_ulltoa (unsigned long long val, char *buf)
   return buf;
 }
 
+/* Simple random number generator, for use with shuffle.
+   This doesn't need to be truly random, just pretty random.  Use our own
+   implementation rather than relying on the C runtime's rand() so we always
+   get the same results for a given seed, regardless of OS.  */
+
+static unsigned int mk_state = 0;
+
+void
+make_seed(unsigned int seed)
+{
+  mk_state = seed;
+}
+
+unsigned int
+make_rand()
+{
+  /* mk_state must never be 0.  */
+  if (mk_state == 0) {
+    mk_state = (unsigned int)(time (NULL) ^ make_pid ()) + 1;
+  }
+
+  /* A simple xorshift RNG.  */
+  mk_state ^= mk_state << 13;
+  mk_state ^= mk_state >> 17;
+  mk_state ^= mk_state << 5;
+
+  return mk_state;
+}
+
 /* Compare strings *S1 and *S2.
    Return negative if the first is less, positive if it is greater,
    zero if they are equal.  */