-/* File: z-rand.c */
+/* 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- */
+#if defined(WINDOWS)
+#include <Windows.h>
+#endif
+
#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_seed(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];
+}
+static const u32b Rand_Xorshift_max = 0xFFFFFFFF;
/*
- * Initialize the "complex" RNG using a new seed
+ * Initialize the RNG using a new seed
*/
-void Rand_state_init(u32b seed)
+void Rand_state_set(u32b seed)
{
- int i, j;
+ Rand_Xorshift_seed(seed, Rand_state);
+}
- /* Seed the table */
- Rand_state[0] = seed;
+void Rand_state_init(void)
+{
+#ifdef RNG_DEVICE
- /* Propagate the seed */
- for (i = 1; i < RAND_DEG; i++) Rand_state[i] = LCRNG(Rand_state[i-1]);
+ FILE *fp = fopen(RNG_DEVICE, "r");
+
+ do {
+ fread(Rand_state, sizeof(Rand_state[0]), 4, fp);
+ } while ((Rand_state[0] | Rand_state[1] | Rand_state[2] | Rand_state[3]) == 0);
+
+ fclose(fp);
- /* 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;
+#elif defined(WINDOWS)
- /* Update the table, extract an entry */
- Rand_state[j] += Rand_state[Rand_place];
+ HCRYPTPROV hProvider;
- /* Advance the index */
- Rand_place = j;
- }
-}
+ CryptAcquireContext(&hProvider, NULL, NULL, PROV_RSA_FULL, 0);
+ do {
+ CryptGenRandom(hProvider, sizeof(Rand_state[0]) * 4, (BYTE*)Rand_state);
+ } while ((Rand_state[0] | Rand_state[1] | Rand_state[2] | Rand_state[3]) == 0);
-/*
- * Extract a "random" number from 0 to m-1, via "modulus"
- *
- * Note that "m" should probably be less than 500000, or the
- * results may be rather biased towards low values.
- */
-s32b Rand_mod(s32b m)
-{
- int j;
- u32b r;
+ CryptReleaseContext(hProvider, 0);
- /* Hack -- simple case */
- if (m <= 1) return (0);
+#else
- /* Use the "simple" RNG */
- if (Rand_quick)
- {
- /* Cycle the generator */
- r = (Rand_value = LCRNG(Rand_value));
+ /* Basic seed */
+ u32b seed = (time(NULL));
+#ifdef SET_UID
+ /* Mutate the seed on Unix machines */
+ seed = ((seed >> 3) * (getpid() << 1));
+#endif
+ /* Seed the RNG */
+ Rand_state_set(seed);
- /* Mutate a 28-bit "random" number */
- r = ((r >> 4) % m);
- }
+#endif
+}
- /* Use the "complex" RNG */
- else
- {
- /* Acquire the next index */
- j = Rand_place + 1;
- if (j == RAND_DEG) j = 0;
+/*
+ * Backup the RNG state
+ */
+void Rand_state_backup(u32b* backup_state)
+{
+ int i;
- /* Update the table, extract an entry */
- r = (Rand_state[j] += Rand_state[Rand_place]);
+ for (i = 0; i < 4; ++ i) {
+ backup_state[i] = Rand_state[i];
+ }
+}
- /* Advance the index */
- Rand_place = j;
+/*
+ * Restore the RNG state
+ */
+void Rand_state_restore(u32b* backup_state)
+{
+ int i;
- /* Extract a "random" number */
- r = ((r >> 4) % m);
+ for (i = 0; i < 4; ++ i) {
+ Rand_state[i] = backup_state[i];
}
-
- /* Use the value */
- return (r);
}
/*
* 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)
+static s32b Rand_div_impl(s32b m, u32b* state)
{
- u32b r, n;
+ u32b scaling;
+ u32b past;
+ u32b ret;
/* 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]);
+ scaling = Rand_Xorshift_max / m;
+ past = scaling * m;
- /* Hack -- extract a 28-bit "random" number */
- r = (r >> 4) / n;
+ do {
+ ret = Rand_Xorshift(state);
+ } while (ret >= past);
- /* Advance the index */
- Rand_place = j;
-
- /* Done */
- if (r < m) break;
- }
- }
+ return ret / scaling;
+}
- /* Use the value */
- return (r);
+s32b Rand_div(s32b m)
+{
+ return Rand_div_impl(m, Rand_state);
}
}
+/*
+ * 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
+ */
+s32b Rand_external(s32b m)
+{
+ static bool initialized = FALSE;
+ static u32b Rand_state_external[4];
+
+ if (!initialized)
+ {
+ /* Initialize with new seed */
+ u32b seed = time(NULL);
+ Rand_Xorshift_seed(seed, Rand_state_external);
+ initialized = TRUE;
+ }
+
+ return Rand_div_impl(m, Rand_state_external);
+}