From a99378ebe46f5245ef1307c6a9834d19d57882d0 Mon Sep 17 00:00:00 2001 From: Paul Smith Date: Mon, 26 Sep 2022 14:38:27 -0400 Subject: 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(). --- src/misc.c | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) (limited to 'src/misc.c') 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. */ -- cgit v1.2.1