From aa9a8e8c7eecc2de77690b872931e88951622813 Mon Sep 17 00:00:00 2001
From: Simon Tatham <anakin@pobox.com>
Date: Mon, 3 May 2004 09:10:52 +0000
Subject: [PATCH] The Windows RNG turns out to only give about 16 bits at a
 time. This is (a) pretty feeble, and (b) means that although Net seeds
 transfer between platforms and still generate the same game, there's a
 suspicious discrepancy in the typical seed _generated_ by each platform. I
 have a better RNG kicking around in this code base already, so I'll just use
 it. Each midend has its own random_state, which it passes to new_game_seed()
 as required. A handy consequence of this is that initial seed data is now
 passed to midend_new(), which means that new platform implementors are
 unlikely to forget to seed the RNG because failure to do so causes a compile
 error!

[originally from svn r4187]
---
 Recipe     |  4 ++--
 cube.c     |  6 +++---
 fifteen.c  |  6 +++---
 gtk.c      |  6 +++---
 midend.c   | 11 +++++++----
 misc.c     | 17 -----------------
 net.c      |  4 ++--
 nullgame.c |  2 +-
 puzzles.h  |  6 +++---
 random.c   | 10 ++++++++--
 sixteen.c  |  4 ++--
 windows.c  |  8 +++++---
 12 files changed, 39 insertions(+), 45 deletions(-)

diff --git a/Recipe b/Recipe
index a2a5bfc..9d7c1e9 100644
--- a/Recipe
+++ b/Recipe
@@ -13,8 +13,8 @@
 !makefile cygwin Makefile.cyg
 
 WINDOWS  = windows user32.lib gdi32.lib comctl32.lib
-COMMON   = midend misc malloc
-NET      = net random tree234
+COMMON   = midend misc malloc random
+NET      = net tree234
 
 net      : [X] gtk COMMON NET
 cube     : [X] gtk COMMON cube
diff --git a/cube.c b/cube.c
index 6c2658f..ccc8689 100644
--- a/cube.c
+++ b/cube.c
@@ -560,7 +560,7 @@ static void classify_grid_square_callback(void *ctx, struct grid_square *sq)
 	data->squareindex++;
 }
 
-char *new_game_seed(game_params *params)
+char *new_game_seed(game_params *params, random_state *rs)
 {
     struct grid_data data;
     int i, j, k, m, area, facesperclass;
@@ -605,7 +605,7 @@ char *new_game_seed(game_params *params)
 
     for (i = 0; i < data.nclasses; i++) {
 	for (j = 0; j < facesperclass; j++) {
-            int n = rand_upto(data.nsquares[i]);
+            int n = random_upto(rs, data.nsquares[i]);
 
 	    assert(!flags[data.gridptrs[i][n]]);
 	    flags[data.gridptrs[i][n]] = TRUE;
@@ -653,7 +653,7 @@ char *new_game_seed(game_params *params)
     /*
      * Choose a non-blue square for the polyhedron.
      */
-    sprintf(p, ":%d", data.gridptrs[0][rand_upto(m)]);
+    sprintf(p, ":%d", data.gridptrs[0][random_upto(rs, m)]);
 
     sfree(data.gridptrs[0]);
     sfree(flags);
diff --git a/fifteen.c b/fifteen.c
index 74fd4fc..3965844 100644
--- a/fifteen.c
+++ b/fifteen.c
@@ -131,7 +131,7 @@ int perm_parity(int *perm, int n)
     return ret;
 }
 
-char *new_game_seed(game_params *params)
+char *new_game_seed(game_params *params, random_state *rs)
 {
     int gap, n, i, x;
     int x1, x2, p1, p2, parity;
@@ -149,7 +149,7 @@ char *new_game_seed(game_params *params)
         used[i] = FALSE;
     }
 
-    gap = rand_upto(n);
+    gap = random_upto(rs, n);
     tiles[gap] = 0;
     used[0] = TRUE;
 
@@ -157,7 +157,7 @@ char *new_game_seed(game_params *params)
      * Place everything else except the last two tiles.
      */
     for (x = 0, i = n-1; i > 2; i--) {
-        int k = rand_upto(i);
+        int k = random_upto(rs, i);
         int j;
 
         for (j = 0; j < n; j++)
diff --git a/gtk.c b/gtk.c
index 6906f6c..5cbdbe4 100644
--- a/gtk.c
+++ b/gtk.c
@@ -688,10 +688,12 @@ static frontend *new_window(void)
     GtkBox *vbox;
     GtkWidget *menubar, *menu, *menuitem;
     int x, y, n;
+    time_t t;
 
     fe = snew(frontend);
 
-    fe->me = midend_new(fe);
+    time(&t);
+    fe->me = midend_new(fe, &t, sizeof(t));
     midend_new_game(fe->me);
 
     fe->window = gtk_window_new(GTK_WINDOW_TOPLEVEL);
@@ -855,8 +857,6 @@ static frontend *new_window(void)
 
 int main(int argc, char **argv)
 {
-    srand(time(NULL));
-
     gtk_init(&argc, &argv);
     (void) new_window();
     gtk_main();
diff --git a/midend.c b/midend.c
index 818b278..cacd66e 100644
--- a/midend.c
+++ b/midend.c
@@ -13,6 +13,8 @@
 
 struct midend_data {
     frontend *frontend;
+    random_state *random;
+
     char *seed;
     int fresh_seed;
     int nstates, statesize, statepos;
@@ -36,11 +38,12 @@ struct midend_data {
     } \
 } while (0)
 
-midend_data *midend_new(frontend *frontend)
+midend_data *midend_new(frontend *fe, void *randseed, int randseedsize)
 {
     midend_data *me = snew(midend_data);
 
-    me->frontend = frontend;
+    me->frontend = fe;
+    me->random = random_init(randseed, randseedsize);
     me->nstates = me->statesize = me->statepos = 0;
     me->states = NULL;
     me->params = default_params();
@@ -88,7 +91,7 @@ void midend_new_game(midend_data *me)
 
     if (!me->fresh_seed) {
 	sfree(me->seed);
-	me->seed = new_game_seed(me->params);
+	me->seed = new_game_seed(me->params, me->random);
     } else
 	me->fresh_seed = FALSE;
 
@@ -252,7 +255,7 @@ float *midend_colours(midend_data *me, int *ncolours)
     float *ret;
 
     if (me->nstates == 0) {
-        char *seed = new_game_seed(me->params);
+        char *seed = new_game_seed(me->params, me->random);
         state = new_game(me->params, seed);
         sfree(seed);
     } else
diff --git a/misc.c b/misc.c
index 48088da..73b9a7b 100644
--- a/misc.c
+++ b/misc.c
@@ -7,23 +7,6 @@
 
 #include "puzzles.h"
 
-int rand_upto(int limit)
-{
-    unsigned long divisor = RAND_MAX / (unsigned)limit;
-    unsigned long max = divisor * (unsigned)limit;
-    unsigned long n;
-
-    assert(limit > 0);
-
-    do {
-        n = rand();
-    } while (n >= max);
-
-    n /= divisor;
-
-    return (int)n;
-}
-
 void free_cfg(config_item *cfg)
 {
     config_item *i;
diff --git a/net.c b/net.c
index cf3fe3d..8b74e7b 100644
--- a/net.c
+++ b/net.c
@@ -254,7 +254,7 @@ char *validate_params(game_params *params)
  * Randomly select a new game seed.
  */
 
-char *new_game_seed(game_params *params)
+char *new_game_seed(game_params *params, random_state *rs)
 {
     /*
      * The full description of a Net game is far too large to
@@ -268,7 +268,7 @@ char *new_game_seed(game_params *params)
      * understand it and do something completely different.)
      */
     char buf[40];
-    sprintf(buf, "%d", rand());
+    sprintf(buf, "%lu", random_bits(rs, 32));
     return dupstr(buf);
 }
 
diff --git a/nullgame.c b/nullgame.c
index bc0c386..8df09e9 100644
--- a/nullgame.c
+++ b/nullgame.c
@@ -76,7 +76,7 @@ char *validate_params(game_params *params)
     return NULL;
 }
 
-char *new_game_seed(game_params *params)
+char *new_game_seed(game_params *params, random_state *rs)
 {
     return dupstr("FIXME");
 }
diff --git a/puzzles.h b/puzzles.h
index 10250a0..035ff24 100644
--- a/puzzles.h
+++ b/puzzles.h
@@ -103,7 +103,7 @@ void status_bar(frontend *fe, char *text);
 /*
  * midend.c
  */
-midend_data *midend_new(frontend *fe);
+midend_data *midend_new(frontend *fe, void *randseed, int randseedsize);
 void midend_free(midend_data *me);
 void midend_set_params(midend_data *me, game_params *params);
 void midend_size(midend_data *me, int *x, int *y);
@@ -138,13 +138,13 @@ char *dupstr(char *s);
 /*
  * misc.c
  */
-int rand_upto(int limit);
 void free_cfg(config_item *cfg);
 
 /*
  * random.c
  */
 random_state *random_init(char *seed, int len);
+unsigned long random_bits(random_state *state, int bits);
 unsigned long random_upto(random_state *state, unsigned long limit);
 void random_free(random_state *state);
 
@@ -160,7 +160,7 @@ game_params *dup_params(game_params *params);
 config_item *game_configure(game_params *params);
 game_params *custom_params(config_item *cfg);
 char *validate_params(game_params *params);
-char *new_game_seed(game_params *params);
+char *new_game_seed(game_params *params, random_state *rs);
 char *validate_seed(game_params *params, char *seed);
 game_state *new_game(game_params *params, char *seed);
 game_state *dup_game(game_state *state);
diff --git a/random.c b/random.c
index e0a179e..664b11c 100644
--- a/random.c
+++ b/random.c
@@ -231,7 +231,7 @@ random_state *random_init(char *seed, int len)
 
 unsigned long random_bits(random_state *state, int bits)
 {
-    int ret = 0;
+    unsigned long ret = 0;
     int n;
 
     for (n = 0; n < bits; n += 8) {
@@ -251,7 +251,13 @@ unsigned long random_bits(random_state *state, int bits)
 	ret = (ret << 8) | state->databuf[state->pos++];
     }
 
-    ret &= (1 << bits) - 1;
+    /*
+     * `(1 << bits) - 1' is not good enough, since if bits==32 on a
+     * 32-bit machine, behaviour is undefined and Intel has a nasty
+     * habit of shifting left by zero instead. We'll shift by
+     * bits-1 and then separately shift by one.
+     */
+    ret &= (1 << (bits-1)) * 2 - 1;
     return ret;
 }
 
diff --git a/sixteen.c b/sixteen.c
index 78bd851..f0acff5 100644
--- a/sixteen.c
+++ b/sixteen.c
@@ -151,7 +151,7 @@ int perm_parity(int *perm, int n)
     return ret;
 }
 
-char *new_game_seed(game_params *params)
+char *new_game_seed(game_params *params, random_state *rs)
 {
     int stop, n, i, x;
     int x1, x2, p1, p2;
@@ -181,7 +181,7 @@ char *new_game_seed(game_params *params)
      * Place everything except (possibly) the last two tiles.
      */
     for (x = 0, i = n; i > stop; i--) {
-        int k = i > 1 ? rand_upto(i) : 0;
+        int k = i > 1 ? random_upto(rs, i) : 0;
         int j;
 
         for (j = 0; j < n; j++)
diff --git a/windows.c b/windows.c
index 8fbcf8e..87f4284 100644
--- a/windows.c
+++ b/windows.c
@@ -311,9 +311,13 @@ static frontend *new_window(HINSTANCE inst)
     int x, y;
     RECT r, sr;
     HDC hdc;
+    time_t t;
 
     fe = snew(frontend);
-    fe->me = midend_new(fe);
+
+    time(&t);
+    fe->me = midend_new(fe, &t, sizeof(t));
+
     fe->inst = inst;
     midend_new_game(fe->me);
     midend_size(fe->me, &x, &y);
@@ -950,8 +954,6 @@ int WINAPI WinMain(HINSTANCE inst, HINSTANCE prev, LPSTR cmdline, int show)
 {
     MSG msg;
 
-    srand(time(NULL));
-
     InitCommonControls();
 
     if (!prev) {
-- 
2.30.2