X-Git-Url: http://git.osdn.net/view?a=blobdiff_plain;f=src%2Fz-rand.c;h=a41873492bde4950c7eea6a81895ef69504c7440;hb=cee5e8f2f28a7b602659f2de6aa1df5cdf7f8fbd;hp=f3c11dedb9dd92e4cd24768b183f7604642db35f;hpb=5e080b88c27bcb3fb59a5469c84528695c2174a9;p=hengband%2Fhengband.git

diff --git a/src/z-rand.c b/src/z-rand.c
index f3c11dedb..a41873492 100644
--- a/src/z-rand.c
+++ b/src/z-rand.c
@@ -1,5 +1,14 @@
 /* File: z-rand.c */
 
+/*
+ * Copyright (c) 1997 Ben Harrison, and others
+ *
+ * This software may be copied and distributed for educational, research,
+ * and not for profit purposes provided that this copyright and statement
+ * are included in all such copies.  Other copyrights may also apply.
+ */
+
+
 /* Purpose: a simple random number generator -BEN- */
 
 #include "z-rand.h"
@@ -34,134 +43,102 @@
  * automatically used instead of the "complex" RNG, and when you are
  * done, you de-activate it via "Rand_quick = FALSE" or choose a new
  * seed via "Rand_value = seed".
+ *
+ *
+ * RNG algorithm was fully rewritten. Upper comment is OLD.
  */
 
 
 /*
- * Random Number Generator -- Linear Congruent RNG
+ * Currently unused
  */
-#define LCRNG(X)        ((X) * 1103515245 + 12345)
-
-
+u16b Rand_place;
 
 /*
- * Use the "simple" LCRNG
+ * Current "state" table for the RNG
+ * Only index 0 to 3 are used
  */
-bool Rand_quick = TRUE;
+u32b Rand_state[RAND_DEG] = {
+	123456789,
+	362436069,
+	521288629,
+	88675123,
+};
 
 
 /*
- * Current "value" of the "simple" RNG
+ * Initialize Xorshift Algorithm state
  */
-u32b Rand_value;
+static void Rand_Xorshift_init(u32b seed, u32b* state)
+{
+	int i;
 
+	/* Initialize Xorshift Algorithm RNG */
+	for (i = 1; i <= 4; ++ i) {
+		seed = 1812433253UL * (seed ^ (seed >> 30)) + i;
+		state[i-1] = seed;
+	}
+}
 
 /*
- * Current "index" for the "complex" RNG
+ * Xorshift Algorithm
  */
-u16b Rand_place;
+static u32b Rand_Xorshift(u32b* state)
+{
+	u32b t = state[0] ^ (state[0] << 11);
 
-/*
- * Current "state" table for the "complex" RNG
- */
-u32b Rand_state[RAND_DEG];
+	state[0] = state[1];
+	state[1] = state[2];
+	state[2] = state[3];
 
+	state[3] = (state[3] ^ (state[3] >> 19)) ^ (t ^ (t >> 8));
+
+	return state[3];
+}
 
 /*
- * Initialize the "complex" RNG using a new seed
+ * Initialize the RNG using a new seed
  */
 void Rand_state_init(u32b seed)
 {
-	int i, j;
-
-	/* Seed the table */
-	Rand_state[0] = seed;
+	Rand_Xorshift_init(seed, Rand_state);
+}
 
-	/* Propagate the seed */
-	for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
+/*
+ * Backup the RNG state
+ */
+void Rand_state_backup(u32b* backup_state)
+{
+	int i;
 
-	/* Cycle the table ten times per degree */
-	for (i = 0; i < RAND_DEG * 10; i++)
-	{
-		/* Acquire the next index */
-		j = Rand_place + 1;
-		if (j == RAND_DEG) j = 0;
+	for (i = 0; i < 4; ++ i) {
+		backup_state[i] = Rand_state[i];
+	}
+}
 
-		/* Update the table, extract an entry */
-		Rand_state[j] += Rand_state[Rand_place];
+/*
+ * Restore the RNG state
+ */
+void Rand_state_restore(u32b* backup_state)
+{
+	int i;
 
-		/* Advance the index */
-		Rand_place = j;
+	for (i = 0; i < 4; ++ i) {
+		Rand_state[i] = backup_state[i];
 	}
 }
 
 
 /*
  * Extract a "random" number from 0 to m-1, via "division"
- *
- * This method selects "random" 28-bit numbers, and then uses
- * division to drop those numbers into "m" different partitions,
- * plus a small non-partition to reduce bias, taking as the final
- * value the first "good" partition that a number falls into.
- *
- * This method has no bias, and is much less affected by patterns
- * in the "low" bits of the underlying RNG's.
  */
 s32b Rand_div(u32b m)
 {
-	u32b r, n;
-
 	/* Hack -- simple case */
 	if (m <= 1) return (0);
 
-	/* Partition size */
-	n = (0x10000000 / m);
-
-	/* Use a simple RNG */
-	if (Rand_quick)
-	{
-		/* Wait for it */
-		while (1)
-		{
-			/* Cycle the generator */
-			r = (Rand_value = LCRNG(Rand_value));
-
-			/* Mutate a 28-bit "random" number */
-			r = (r >> 4) / n;
-
-			/* Done */
-			if (r < m) break;
-		}
-	}
-
-	/* Use a complex RNG */
-	else
-	{
-		/* Wait for it */
-		while (1)
-		{
-			int j;
-
-			/* Acquire the next index */
-			j = Rand_place + 1;
-			if (j == RAND_DEG) j = 0;
-
-			/* Update the table, extract an entry */
-			r = (Rand_state[j] += Rand_state[Rand_place]);
-
-			/* Hack -- extract a 28-bit "random" number */
-			r = (r >> 4) / n;
-
-			/* Advance the index */
-			Rand_place = j;
-
-			/* Done */
-			if (r < m) break;
-		}
-	}
-
 	/* Use the value */
-	return (r);
+	return Rand_Xorshift(Rand_state) % m;
 }
 
 
@@ -304,4 +281,56 @@ s16b maxroll(int num, int sides)
 }
 
 
+/*
+ * Given a numerator and a denominator, supply a properly rounded result,
+ * using the RNG to smooth out remainders.  -LM-
+ */
+s32b div_round(s32b n, s32b d)
+{
+        s32b tmp;
+
+        /* Refuse to divide by zero */
+        if (!d) return (n);
+
+        /* Division */
+        tmp = n / d;
+
+        /* Rounding */
+        if ((ABS(n) % ABS(d)) > randint0(ABS(d)))
+        {
+                /* Increase the absolute value */
+                if (n * d > 0L) tmp += 1L;
+                else            tmp -= 1L;
+        }
+
+        /* Return */
+        return (tmp);
+}
+
+
+
+
+/*
+ * Extract a "random" number from 0 to m-1, using the RNG.
+ *
+ * This function should be used when generating random numbers in
+ * "external" program parts like the main-*.c files.  It preserves
+ * the current RNG state to prevent influences on game-play.
+ *
+ * Could also use rand() from <stdlib.h> directly. XXX XXX XXX
+ */
+u32b Rand_external(u32b m)
+{
+	static bool initialized = FALSE;
+	static u32b Rand_state_external[4];
 
+	if (!initialized)
+	{
+		/* Initialize with new seed */
+		u32b seed = time(NULL);
+		Rand_Xorshift_init(seed, Rand_state_external);
+		initialized = TRUE;
+	}
+
+	return Rand_Xorshift(Rand_state_external) % m;
+}