1 #include "AppHdr.h"
2
3 #include "random.h"
4
5 #include <cinttypes>
6 #include <cmath>
7 #if defined(UNIX) || defined(TARGET_COMPILER_MINGW)
8 # include <unistd.h>
9 #else
10 # include <process.h>
11 #endif
12
13 #include "pcg.h"
14 #include "syscalls.h"
15 #include "branch-type.h"
16 #include "state.h"
17 #include "store.h"
18 #include "options.h"
19
20 namespace rng
21 {
22 // global/persistent rng state that will be saved
23 static FixedVector<PcgRNG, rng::NUM_RNGS> _global_state;
24
25 // temporary rng state
26 static rng_type _generator = rng::GAMEPLAY;
27 // TODO: once we have c++17, convert to type optional<PcgRNG>
28 static PcgRNG * _sub_generator = nullptr;
29
generators_to_vector()30 CrawlVector generators_to_vector()
31 {
32 CrawlVector store;
33 for (PcgRNG& rng : _global_state)
34 store.push_back(rng.to_vector()); // TODO is this ok memory-wise?
35 return store;
36 }
37
get_states()38 vector<uint64_t> get_states()
39 {
40 // this doesn't return the internal state per se, but it returns the count
41 // of 32 bit integers that have been drawn, which amounts to the same thing.
42 // This isn't saved, though, so it's mainly useful for debugging within a
43 // session.
44 vector<uint64_t> result;
45 for (PcgRNG& rng : _global_state)
46 result.push_back(rng.get_count());
47 return result;
48 }
49
load_generators(const CrawlVector & v)50 void load_generators(const CrawlVector &v)
51 {
52 // as-is, decreasing the number of rngs (e.g. by removing a branch) will
53 // break save compatibility.
54 ASSERT(v.size() <= _global_state.size());
55 for (int i = 0; i < v.size(); i++)
56 {
57 CrawlVector state = v[i].get_vector();
58 _global_state[i] = PcgRNG(state);
59 }
60 }
61
generator(rng_type g)62 generator::generator(rng_type g) : previous(_generator)
63 {
64 ASSERT(g != rng::SUB_GENERATOR);
65 _generator = g;
66 }
67
get_branch_generator(const branch_type b)68 rng_type get_branch_generator(const branch_type b)
69 {
70 return static_cast<rng_type>(rng::LEVELGEN + static_cast<int>(b));
71 }
72
generator(branch_type b)73 generator::generator(branch_type b) : previous(_generator)
74 {
75 _generator = get_branch_generator(b);
76 }
77
~generator()78 generator::~generator()
79 {
80 _generator = previous;
81 }
82
subgenerator(uint64_t seed,uint64_t sequence)83 subgenerator::subgenerator(uint64_t seed, uint64_t sequence)
84 : current(seed, sequence),
85 previous(_sub_generator),
86 previous_main(_generator)
87 {
88 _generator = rng::SUB_GENERATOR;
89 _sub_generator = ¤t;
90 }
91
~subgenerator()92 subgenerator::~subgenerator()
93 {
94 _generator = previous_main;
95 _sub_generator = previous;
96 }
97
subgenerator(uint64_t seed)98 subgenerator::subgenerator(uint64_t seed)
99 : subgenerator(seed, get_uint64())
100 { }
101
102 // call the 1-arg constructor so as to ensure a sequence point between the
103 // two get_uint64 calls.
subgenerator()104 subgenerator::subgenerator()
105 : subgenerator(get_uint64())
106 { }
107
get_generator(rng_type r)108 PcgRNG *get_generator(rng_type r)
109 {
110 UNUSED(r);
111 ASSERT(_generator != ASSERT_NO_RNG);
112 if (_generator == SUB_GENERATOR)
113 return _sub_generator;
114 else
115 return &_global_state[_generator];
116 }
117
current_generator()118 PcgRNG ¤t_generator()
119 {
120 PcgRNG *ret = get_generator(_generator);
121 ASSERT(ret);
122 return *ret;
123 }
124
get_uint32()125 uint32_t get_uint32()
126 {
127 return current_generator().get_uint32();
128 }
129
peek_uint32()130 uint32_t peek_uint32()
131 {
132 PcgRNG tmp = current_generator(); // make a copy
133 return tmp.get_uint32();
134 }
135
get_uint64()136 uint64_t get_uint64()
137 {
138 return current_generator().get_uint64();
139 }
140
peek_uint64()141 uint64_t peek_uint64()
142 {
143 PcgRNG tmp = current_generator(); // make a copy
144 return tmp.get_uint64();
145 }
146
_do_seeding(PcgRNG & master)147 static void _do_seeding(PcgRNG &master)
148 {
149 // TODO: don't initialize gameplay/ui rng?
150 // Use the just seeded RNG to initialize the rest.
151 for (PcgRNG& rng : _global_state)
152 {
153 uint64_t init_state = master.get_uint64();
154 uint64_t seq = master.get_uint64();
155 rng = PcgRNG(init_state, seq);
156 }
157 }
158
seed(uint64_t seed)159 void seed(uint64_t seed)
160 {
161 // use the default stream
162 PcgRNG master = PcgRNG(seed);
163 _do_seeding(master);
164 }
165
seed()166 void seed()
167 {
168 // seed both state and sequence from system randomness.
169 uint64_t seed_key[2];
170 bool seeded = read_urandom((char*)(&seed_key), sizeof(seed_key));
171 ASSERT(seeded);
172 PcgRNG master = PcgRNG(seed_key[0], seed_key[1]);
173 _do_seeding(master);
174 }
175
176 /**
177 * Reset RNG to Options seed, and if that seed is 0, generate a new one.
178 */
reset()179 void reset()
180 {
181 crawl_state.seed = Options.seed;
182 while (!crawl_state.seed) // 0 = random seed
183 {
184 rng::seed(); // reset entirely via read_urandom
185 crawl_state.seed = get_uint64();
186 }
187 dprf("Setting game seed to %" PRIu64, crawl_state.seed);
188 you.game_seed = crawl_state.seed;
189 rng::seed(crawl_state.seed);
190 }
191 }
192
193 // TODO: probably this could all be in the rng namespace
194
195 // [low, high]
random_range(int low,int high)196 int random_range(int low, int high)
197 {
198 ASSERT(low <= high);
199 return low + random2(high - low + 1);
200 }
201
202 // [low, high]
random_range(int low,int high,int nrolls)203 int random_range(int low, int high, int nrolls)
204 {
205 ASSERT(nrolls > 0);
206 const int roll = random2avg(high - low + 1, nrolls);
207 return low + roll;
208 }
209
210 // [0, max)
random2(int max)211 int random2(int max)
212 {
213 if (max <= 1)
214 return 0;
215
216 return rng::current_generator().get_bounded_uint32(max);
217 }
218
219 // [0, max), separate RNG state
ui_random(int max)220 int ui_random(int max)
221 {
222 rng::generator ui(rng::UI);
223
224 return random2(max);
225 }
226
227 // [0, 1]
coinflip()228 bool coinflip()
229 {
230 return static_cast<bool>(random2(2));
231 }
232
233 // Returns random2(x) if random_factor is true, otherwise the mean.
234 // [0, x)
maybe_random2(int x,bool random_factor)235 int maybe_random2(int x, bool random_factor)
236 {
237 if (x <= 1)
238 return 0;
239 if (random_factor)
240 return random2(x);
241 else
242 return x / 2;
243 }
244
245 // [0, ceil(nom/denom)]
maybe_random_div(int nom,int denom,bool random_factor)246 int maybe_random_div(int nom, int denom, bool random_factor)
247 {
248 if (nom <= 0)
249 return 0;
250 if (random_factor)
251 return random2(nom + denom) / denom;
252 else
253 return nom / 2 / denom;
254 }
255
256 // [num, num*size]
maybe_roll_dice(int num,int size,bool random)257 int maybe_roll_dice(int num, int size, bool random)
258 {
259 if (random)
260 return roll_dice(num, size);
261 else
262 return (num + num * size) / 2;
263 }
264
265 // [num, num*size]
roll_dice(int num,int size)266 int roll_dice(int num, int size)
267 {
268 int ret = 0;
269
270 // If num <= 0 or size <= 0, then we'll just return the default
271 // value of zero. This is good behaviour in that it will be
272 // appropriate for calculated values that might be passed in.
273 if (num > 0 && size > 0)
274 {
275 ret += num; // since random2() is zero based
276
277 for (int i = 0; i < num; i++)
278 ret += random2(size);
279 }
280
281 return ret;
282 }
283
roll() const284 int dice_def::roll() const
285 {
286 return roll_dice(num, size);
287 }
288
calc_dice(int num_dice,int max_damage,bool random)289 dice_def calc_dice(int num_dice, int max_damage, bool random)
290 {
291 dice_def ret(num_dice, 0);
292
293 if (num_dice <= 1)
294 {
295 ret.num = 1;
296 ret.size = max_damage;
297 }
298 else if (max_damage <= num_dice)
299 {
300 ret.num = max_damage;
301 ret.size = 1;
302 }
303 else if (random)
304 ret.size = div_rand_round(max_damage, num_dice);
305 else
306 ret.size = max_damage / num_dice; // round down
307
308 return ret;
309 }
310
311 // Calculates num/den and randomly adds one based on the remainder.
312 // [floor(num/den), ceil(num/den)]
div_rand_round(int num,int den)313 int div_rand_round(int num, int den)
314 {
315 int rem = num % den;
316 if (rem)
317 return num / den + (random2(den) < rem);
318 else
319 return num / den;
320 }
321
322 // Converts a double to an integer by randomly rounding.
323 // Currently does not handle negative inputs.
rand_round(double x)324 int rand_round(double x)
325 {
326 ASSERT(x >= 0);
327 return int(x) + decimal_chance(fmod(x, 1.0));
328 }
329
div_round_up(int num,int den)330 int div_round_up(int num, int den)
331 {
332 return num / den + (num % den != 0);
333 }
334
335 // random2avg() returns same mean value as random2() but with a lower variance
336 // never use with rolls < 2 as that would be silly - use random2() instead {dlb}
337 // [0, max)
random2avg(int max,int rolls)338 int random2avg(int max, int rolls)
339 {
340 int sum = random2(max);
341
342 for (int i = 0; i < (rolls - 1); i++)
343 sum += random2(max + 1);
344
345 return sum / rolls;
346 }
347
348 // biased_random2() takes values in the same range [0, max) as random2() but
349 // with mean value (max - 1)/(n + 1) biased towards the bottom end.
350 // This can be thought of as the smallest of n _distinct_ random integers
351 // chosen in [0, max + n - 1).
352 // Never use with n < 2.
biased_random2(int max,int n)353 int biased_random2(int max, int n)
354 {
355 for (int i = 0; i < max; i++)
356 if (x_chance_in_y(n, n + max - 1 - i))
357 return i;
358 return 0;
359 }
360
361 // originally designed to randomise evasion -
362 // values are slightly lowered near (max) and
363 // approach an upper limit somewhere near (limit/2)
364 // [0, max]
random2limit(int max,int limit)365 int random2limit(int max, int limit)
366 {
367 int sum = 0;
368
369 if (max < 1)
370 return 0;
371
372 for (int i = 0; i < max; i++)
373 if (random2(limit) >= i)
374 sum++;
375
376 return sum;
377 }
378
379 /** Sample from a binomial distribution.
380 *
381 * This is the number of successes in a sequence of independent trials with
382 * fixed probability.
383 *
384 * @param n_trials The number of trials.
385 * @param trial_prob The numerator of the probability of success of each trial.
386 * If greater than scale, the probability is 1.0.
387 * @param scale The denominator of trial_prob, default 100.
388 * @return the number of successes, range [0, n_trials]
389 */
binomial(unsigned n_trials,unsigned trial_prob,unsigned scale)390 int binomial(unsigned n_trials, unsigned trial_prob, unsigned scale)
391 {
392 int count = 0;
393 for (unsigned i = 0; i < n_trials; ++i)
394 if (::x_chance_in_y(trial_prob, scale))
395 count++;
396
397 return count;
398 }
399
400 // range [0, 1.0)
401 // This uses a technique described by Saito and Matsumoto at
402 // MCQMC'08. Given that the IEEE floating point numbers are
403 // uniformly distributed over [1,2), we generate a number in
404 // this range and then offset it onto the range [0,1). The
405 // choice of bits (masking v. shifting) is arbitrary and
406 // should be immaterial for high quality generators.
random_real()407 double random_real()
408 {
409 static const uint64_t UPPER_BITS = 0x3FF0000000000000ULL;
410 static const uint64_t LOWER_MASK = 0x000FFFFFFFFFFFFFULL;
411 const uint64_t value = UPPER_BITS | (rng::get_uint64() & LOWER_MASK);
412 double result;
413 // Portable memory transmutation. The union trick almost always
414 // works, but this is safer.
415 memcpy(&result, &value, sizeof(value));
416 return result - 1.0;
417 }
418
419 // Roll n_trials, return true if at least one succeeded. n_trials might be
420 // not integer.
421 // [0, 1]
bernoulli(double n_trials,double trial_prob)422 bool bernoulli(double n_trials, double trial_prob)
423 {
424 if (n_trials <= 0 || trial_prob <= 0)
425 return false;
426 return !decimal_chance(pow(1 - trial_prob, n_trials));
427 }
428
one_chance_in(int a_million)429 bool one_chance_in(int a_million)
430 {
431 return random2(a_million) == 0;
432 }
433
x_chance_in_y(int x,int y)434 bool x_chance_in_y(int x, int y)
435 {
436 if (x <= 0)
437 return false;
438
439 if (x >= y)
440 return true;
441
442 return random2(y) < x;
443 }
444
445 // [val - lowfuzz, val + highfuzz]
fuzz_value(int val,int lowfuzz,int highfuzz,int naverage)446 int fuzz_value(int val, int lowfuzz, int highfuzz, int naverage)
447 {
448 const int lfuzz = lowfuzz * val / 100,
449 hfuzz = highfuzz * val / 100;
450 return val + random2avg(lfuzz + hfuzz + 1, naverage) - lfuzz;
451 }
452
decimal_chance(double chance)453 bool decimal_chance(double chance)
454 {
455 return random_real() < chance;
456 }
457
458 // This is used when the front-end randomness is inconclusive. There are
459 // never more than two possibilities, which simplifies things.
x_chance_in_y_contd(int x,int y,int index)460 bool defer_rand::x_chance_in_y_contd(int x, int y, int index)
461 {
462 if (x <= 0)
463 return false;
464
465 if (x >= y)
466 return true;
467
468 do
469 {
470 if (index == int(bits.size()))
471 bits.push_back(rng::get_uint32());
472
473 uint64_t expn_rand_1 = uint64_t(bits[index++]) * y;
474 uint64_t expn_rand_2 = expn_rand_1 + y;
475 uint64_t expn_minimum_fail = uint64_t(x) << 32;
476
477 if (expn_minimum_fail <= expn_rand_1)
478 return false;
479
480 if (expn_rand_2 <= expn_minimum_fail)
481 return true;
482
483 // y = expn_rand_2 - expn_rand_1; no-op
484 x = expn_minimum_fail - expn_rand_1;
485 } while (1);
486 }
487
random2(int maxp1)488 int defer_rand::random2(int maxp1)
489 {
490 if (maxp1 <= 1)
491 return 0;
492
493 if (bits.empty())
494 bits.push_back(rng::get_uint32());
495
496 uint64_t expn_rand_1 = uint64_t(bits[0]) * maxp1;
497 uint64_t expn_rand_2 = expn_rand_1 + maxp1;
498
499 int val1 = int(expn_rand_1 >> 32);
500 int val2 = int(expn_rand_2 >> 32);
501
502 if (val2 == val1)
503 return val1;
504
505 // val2 == val1 + 1
506 uint64_t expn_thresh = uint64_t(val2) << 32;
507
508 return x_chance_in_y_contd(int(expn_thresh - expn_rand_1),
509 maxp1, 1)
510 ? val1 : val2;
511 }
512
operator [](int i)513 defer_rand& defer_rand::operator[](int i)
514 {
515 return children[i];
516 }
517
random_range(int low,int high)518 int defer_rand::random_range(int low, int high)
519 {
520 ASSERT(low <= high);
521 return low + random2(high - low + 1);
522 }
523
random2avg(int max,int rolls)524 int defer_rand::random2avg(int max, int rolls)
525 {
526 int sum = (*this)[0].random2(max);
527
528 for (int i = 0; i < (rolls - 1); i++)
529 sum += (*this)[i+1].random2(max + 1);
530
531 return sum / rolls;
532 }
533