4 * Copyright (c) 1997 Ben Harrison, and others
6 * This software may be copied and distributed for educational, research,
7 * and not for profit purposes provided that this copyright and statement
8 * are included in all such copies. Other copyrights may also apply.
12 /* Purpose: a simple random number generator -BEN- */
24 * Angband 2.7.9 introduced a new (optimized) random number generator,
25 * based loosely on the old "random.c" from Berkeley but with some major
26 * optimizations and algorithm changes. See below for more details.
28 * Code by myself (benh@phial.com) and Randy (randy@stat.tamu.edu).
30 * This code provides (1) a "decent" RNG, based on the "BSD-degree-63-RNG"
31 * used in Angband 2.7.8, but rather optimized, and (2) a "simple" RNG,
32 * based on the simple "LCRNG" currently used in Angband, but "corrected"
33 * to give slightly better values. Both of these are available in two
34 * flavors, first, the simple "mod" flavor, which is fast, but slightly
35 * biased at high values, and second, the simple "div" flavor, which is
36 * less fast (and potentially non-terminating) but which is not biased
37 * and is much less subject to low-bit-non-randomness problems.
39 * You can select your favorite flavor by proper definition of the
40 * "randint0()" macro in the "defines.h" file.
42 * Note that, in Angband 2.8.0, the "state" table will be saved in the
43 * savefile, so a special "initialization" phase will be necessary.
45 * Note the use of the "simple" RNG, first you activate it via
46 * "Rand_quick = TRUE" and "Rand_value = seed" and then it is used
47 * automatically used instead of the "complex" RNG, and when you are
48 * done, you de-activate it via "Rand_quick = FALSE" or choose a new
49 * seed via "Rand_value = seed".
52 * RNG algorithm was fully rewritten. Upper comment is OLD.
62 * Current "state" table for the RNG
63 * Only index 0 to 3 are used
65 u32b Rand_state[RAND_DEG] = {
77 static u64b u64b_xor(u64b a, u64b b)
81 result.dw[0] = a.dw[0] ^ b.dw[0];
82 result.dw[1] = a.dw[1] ^ b.dw[1];
87 static u64b u64b_shiftl(u64b x, int k)
92 result.dw[1] = (x.dw[1] << k) | (x.dw[0] >> (32 - k));
93 result.dw[0] = (x.dw[0] << k);
96 result.dw[1] = (x.dw[0] << (k - 32));
103 static u64b u64b_rotl(u64b x, int k)
108 result.dw[0] = (x.dw[0] << k) | (x.dw[1] >> (32 - k));
109 result.dw[1] = (x.dw[1] << k) | (x.dw[0] >> (32 - k));
112 result.dw[0] = (x.dw[0] >> (64 - k)) | (x.dw[1] << (k - 32));
113 result.dw[1] = (x.dw[1] >> (64 - k)) | (x.dw[0] << (k - 32));
119 static u64b u64b_add(u64b a, u64b b)
123 result.dw[0] = a.dw[0] + b.dw[0];
124 result.dw[1] = a.dw[1] + b.dw[1];
126 if (result.dw[0] < a.dw[0])
133 * Initialize Xorshift Algorithm state
135 static void Rand_Xorshift_seed(u32b seed, u32b* state)
139 /* Initialize Xorshift Algorithm RNG */
140 for (i = 1; i <= 4; ++ i) {
141 seed = 1812433253UL * (seed ^ (seed >> 30)) + i;
150 static u32b Rand_Xorshift(u32b* state)
152 u32b t = state[0] ^ (state[0] << 11);
158 state[3] = (state[3] ^ (state[3] >> 19)) ^ (t ^ (t >> 8));
165 * Xoroshiro128+ Algorithm
167 static u32b Rand_Xoroshiro128plus(u32b* state)
169 const u64b s0 = *((u64b*)state);
170 u64b s1 = *((u64b*)state + 1);
171 const u64b result = u64b_add(s0, s1);
173 s1 = u64b_xor(s0, s1);
174 *((u64b*)state) = u64b_xor(u64b_xor(u64b_rotl(s0, 55), s1), u64b_shiftl(s1, 14));
175 *((u64b*)state + 1) = u64b_rotl(s1, 36);
180 static const u32b Rand_Xorshift_max = 0xFFFFFFFF;
183 * Initialize the RNG using a new seed
185 void Rand_state_set(u32b seed)
187 Rand_Xorshift_seed(seed, Rand_state);
190 void Rand_state_init(void)
194 FILE *fp = fopen(RNG_DEVICE, "r");
198 n = fread(Rand_state, sizeof(Rand_state[0]), 4, fp);
199 } while (n != 4 || (Rand_state[0] | Rand_state[1] | Rand_state[2] | Rand_state[3]) == 0);
203 #elif defined(WINDOWS)
205 HCRYPTPROV hProvider;
207 CryptAcquireContext(&hProvider, NULL, NULL, PROV_RSA_FULL, 0);
210 CryptGenRandom(hProvider, sizeof(Rand_state[0]) * 4, (BYTE*)Rand_state);
211 } while ((Rand_state[0] | Rand_state[1] | Rand_state[2] | Rand_state[3]) == 0);
213 CryptReleaseContext(hProvider, 0);
218 u32b seed = (time(NULL));
220 /* Mutate the seed on Unix machines */
221 seed = ((seed >> 3) * (getpid() << 1));
224 Rand_state_set(seed);
230 * Backup the RNG state
232 void Rand_state_backup(u32b* backup_state)
236 for (i = 0; i < 4; ++ i) {
237 backup_state[i] = Rand_state[i];
242 * Restore the RNG state
244 void Rand_state_restore(u32b* backup_state)
248 for (i = 0; i < 4; ++ i) {
249 Rand_state[i] = backup_state[i];
255 * Extract a "random" number from 0 to m-1, via "division"
257 static s32b Rand_div_impl(s32b m, u32b* state)
263 /* Hack -- simple case */
264 if (m <= 1) return (0);
266 scaling = Rand_Xorshift_max / m;
270 ret = Rand_Xoroshiro128plus(state);
271 } while (ret >= past);
273 return ret / scaling;
276 s32b Rand_div(s32b m)
278 return Rand_div_impl(m, Rand_state);
285 * The number of entries in the "randnor_table"
287 #define RANDNOR_NUM 256
290 * The standard deviation of the "randnor_table"
292 #define RANDNOR_STD 64
295 * The normal distribution table for the "randnor()" function (below)
297 static s16b randnor_table[RANDNOR_NUM] =
299 206, 613, 1022, 1430, 1838, 2245, 2652, 3058,
300 3463, 3867, 4271, 4673, 5075, 5475, 5874, 6271,
301 6667, 7061, 7454, 7845, 8234, 8621, 9006, 9389,
302 9770, 10148, 10524, 10898, 11269, 11638, 12004, 12367,
303 12727, 13085, 13440, 13792, 14140, 14486, 14828, 15168,
304 15504, 15836, 16166, 16492, 16814, 17133, 17449, 17761,
305 18069, 18374, 18675, 18972, 19266, 19556, 19842, 20124,
306 20403, 20678, 20949, 21216, 21479, 21738, 21994, 22245,
308 22493, 22737, 22977, 23213, 23446, 23674, 23899, 24120,
309 24336, 24550, 24759, 24965, 25166, 25365, 25559, 25750,
310 25937, 26120, 26300, 26476, 26649, 26818, 26983, 27146,
311 27304, 27460, 27612, 27760, 27906, 28048, 28187, 28323,
312 28455, 28585, 28711, 28835, 28955, 29073, 29188, 29299,
313 29409, 29515, 29619, 29720, 29818, 29914, 30007, 30098,
314 30186, 30272, 30356, 30437, 30516, 30593, 30668, 30740,
315 30810, 30879, 30945, 31010, 31072, 31133, 31192, 31249,
317 31304, 31358, 31410, 31460, 31509, 31556, 31601, 31646,
318 31688, 31730, 31770, 31808, 31846, 31882, 31917, 31950,
319 31983, 32014, 32044, 32074, 32102, 32129, 32155, 32180,
320 32205, 32228, 32251, 32273, 32294, 32314, 32333, 32352,
321 32370, 32387, 32404, 32420, 32435, 32450, 32464, 32477,
322 32490, 32503, 32515, 32526, 32537, 32548, 32558, 32568,
323 32577, 32586, 32595, 32603, 32611, 32618, 32625, 32632,
324 32639, 32645, 32651, 32657, 32662, 32667, 32672, 32677,
326 32682, 32686, 32690, 32694, 32698, 32702, 32705, 32708,
327 32711, 32714, 32717, 32720, 32722, 32725, 32727, 32729,
328 32731, 32733, 32735, 32737, 32739, 32740, 32742, 32743,
329 32745, 32746, 32747, 32748, 32749, 32750, 32751, 32752,
330 32753, 32754, 32755, 32756, 32757, 32757, 32758, 32758,
331 32759, 32760, 32760, 32761, 32761, 32761, 32762, 32762,
332 32763, 32763, 32763, 32764, 32764, 32764, 32764, 32765,
333 32765, 32765, 32765, 32766, 32766, 32766, 32766, 32767,
339 * Generate a random integer number of NORMAL distribution
341 * The table above is used to generate a pseudo-normal distribution,
342 * in a manner which is much faster than calling a transcendental
343 * function to calculate a true normal distribution.
345 * Basically, entry 64*N in the table above represents the number of
346 * times out of 32767 that a random variable with normal distribution
347 * will fall within N standard deviations of the mean. That is, about
348 * 68 percent of the time for N=1 and 95 percent of the time for N=2.
350 * The table above contains a "faked" final entry which allows us to
351 * pretend that all values in a normal distribution are strictly less
352 * than four standard deviations away from the mean. This results in
353 * "conservative" distribution of approximately 1/32768 values.
355 * Note that the binary search takes up to 16 quick iterations.
357 s16b randnor(int mean, int stand)
363 s16b high = RANDNOR_NUM;
366 if (stand < 1) return (s16b)(mean);
368 /* Roll for probability */
369 tmp = (s16b)randint0(32768);
374 int mid = (low + high) >> 1;
376 /* Move right if forced */
377 if (randnor_table[mid] < tmp)
382 /* Move left otherwise */
389 /* Convert the index into an offset */
390 offset = (long)stand * (long)low / RANDNOR_STD;
392 /* One half should be negative */
393 if (randint0(100) < 50) return (mean - offset);
395 /* One half should be positive */
396 return (mean + offset);
402 * Generates damage for "2d6" style dice rolls
404 s16b damroll(DICE_NUMBER num, DICE_SID sides)
407 for (i = 0; i < num; i++) sum += randint1(sides);
413 * Same as above, but always maximal
415 s16b maxroll(DICE_NUMBER num, DICE_SID sides)
417 return (num * sides);
422 * Given a numerator and a denominator, supply a properly rounded result,
423 * using the RNG to smooth out remainders. -LM-
425 s32b div_round(s32b n, s32b d)
429 /* Refuse to divide by zero */
436 if ((ABS(n) % ABS(d)) > randint0(ABS(d)))
438 /* Increase the absolute value */
439 if (n * d > 0L) tmp += 1L;
451 * Extract a "random" number from 0 to m-1, using the RNG.
453 * This function should be used when generating random numbers in
454 * "external" program parts like the main-*.c files. It preserves
455 * the current RNG state to prevent influences on game-play.
457 * Could also use rand() from <stdlib.h> directly.
459 s32b Rand_external(s32b m)
461 static bool initialized = FALSE;
462 static u32b Rand_state_external[4];
466 /* Initialize with new seed */
467 u32b seed = (u32b)time(NULL);
468 Rand_Xorshift_seed(seed, Rand_state_external);
472 return Rand_div_impl(m, Rand_state_external);