/* 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"
* 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;
}
}
+/*
+ * 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;
+}
OSDN Git Service
