-/* File: z-rand.c */
+/* File: z-rand.c */
/*
* Copyright (c) 1997 Ben Harrison, and others
/* 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,
+};
+
+
+typedef struct {
+ u32b dw[2];
+} u64b;
+
+static u64b u64b_xor(u64b a, u64b b)
+{
+ u64b result;
+
+ result.dw[0] = a.dw[0] ^ b.dw[0];
+ result.dw[1] = a.dw[1] ^ b.dw[1];
+
+ return result;
+}
+static u64b u64b_shiftl(u64b x, int k)
+{
+ u64b result;
+
+ if (k < 32) {
+ result.dw[1] = (x.dw[1] << k) | (x.dw[0] >> (32 - k));
+ result.dw[0] = (x.dw[0] << k);
+ }
+ else {
+ result.dw[1] = (x.dw[0] << (k - 32));
+ result.dw[0] = 0;
+ }
+
+ return result;
+}
+
+static u64b u64b_rotl(u64b x, int k)
+{
+ u64b result;
+
+ if (k < 32) {
+ result.dw[0] = (x.dw[0] << k) | (x.dw[1] >> (32 - k));
+ result.dw[1] = (x.dw[1] << k) | (x.dw[0] >> (32 - k));
+ }
+ else {
+ result.dw[0] = (x.dw[0] >> (64 - k)) | (x.dw[1] << (k - 32));
+ result.dw[1] = (x.dw[1] >> (64 - k)) | (x.dw[0] << (k - 32));
+ }
+
+ return result;
+}
+
+static u64b u64b_add(u64b a, u64b b)
+{
+ u64b result;
+
+ result.dw[0] = a.dw[0] + b.dw[0];
+ result.dw[1] = a.dw[1] + b.dw[1];
+
+ if (result.dw[0] < a.dw[0])
+ result.dw[1] ++;
+
+ return result;
+}
/*
- * 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;
+ }
+}
+#if 0
/*
- * Current "index" for the "complex" RNG
+ * Xorshift Algorithm
*/
-u16b Rand_place;
+static u32b Rand_Xorshift(u32b* state)
+{
+ u32b t = state[0] ^ (state[0] << 11);
+
+ 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];
+}
+#endif
/*
- * Current "state" table for the "complex" RNG
+ * Xoroshiro128+ Algorithm
*/
-u32b Rand_state[RAND_DEG];
+static u32b Rand_Xoroshiro128plus(u32b* state)
+{
+ const u64b s0 = *((u64b*)state);
+ u64b s1 = *((u64b*)state + 1);
+ const u64b result = u64b_add(s0, s1);
+ s1 = u64b_xor(s0, s1);
+ *((u64b*)state) = u64b_xor(u64b_xor(u64b_rotl(s0, 55), s1), u64b_shiftl(s1, 14));
+ *((u64b*)state + 1) = u64b_rotl(s1, 36);
+
+ return result.dw[0];
+}
+
+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");
+ int n;
+
+ do {
+ n = fread(Rand_state, sizeof(Rand_state[0]), 4, fp);
+ } while (n != 4 || (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);
+
+ CryptReleaseContext(hProvider, 0);
+#else
+
+ /* 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);
+
+#endif
+}
/*
- * 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.
+ * Backup the RNG state
*/
-s32b Rand_div(u32b m)
+void Rand_state_backup(u32b* backup_state)
{
- u32b r, n;
+ int i;
- /* 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));
+ for (i = 0; i < 4; ++ i) {
+ backup_state[i] = Rand_state[i];
+ }
+}
- /* Mutate a 28-bit "random" number */
- r = (r >> 4) / n;
+/*
+ * Restore the RNG state
+ */
+void Rand_state_restore(u32b* backup_state)
+{
+ int i;
- /* Done */
- if (r < m) break;
- }
+ for (i = 0; i < 4; ++ i) {
+ Rand_state[i] = backup_state[i];
}
+}
- /* 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;
+/*
+ * Extract a "random" number from 0 to m-1, via "division"
+ */
+static s32b Rand_div_impl(s32b m, u32b* state)
+{
+ u32b scaling;
+ u32b past;
+ u32b ret;
- /* Update the table, extract an entry */
- r = (Rand_state[j] += Rand_state[Rand_place]);
+ /* Hack -- simple case */
+ if (m <= 1) return (0);
- /* Hack -- extract a 28-bit "random" number */
- r = (r >> 4) / n;
+ scaling = Rand_Xorshift_max / m;
+ past = scaling * m;
- /* Advance the index */
- Rand_place = j;
+ do {
+ ret = Rand_Xoroshiro128plus(state);
+ } while (ret >= past);
- /* 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);
}
s16b high = RANDNOR_NUM;
/* Paranoia */
- if (stand < 1) return (mean);
+ if (stand < 1) return (s16b)(mean);
/* Roll for probability */
tmp = (s16b)randint0(32768);
/* Move left otherwise */
else
{
- high = mid;
+ high = (s16b)mid;
}
}
{
int i, sum = 0;
for (i = 0; i < num; i++) sum += randint1(sides);
- return (sum);
+ return (s16b)(sum);
}
}
+/*
+ * 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 = (u32b)time(NULL);
+ Rand_Xorshift_seed(seed, Rand_state_external);
+ initialized = TRUE;
+ }
+
+ return Rand_div_impl(m, Rand_state_external);
+}
OSDN Git Service
