blob: fc5dd268cafad002a982063004bde16c178fc0b0 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/*
* Copyright (c) 2021, the SerenityOS developers.
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#include <AK/Random.h>
namespace AK {
u32 get_random_uniform(u32 max_bounds)
{
// If we try to divide all 2**32 numbers into groups of "max_bounds" numbers, we may end up
// with a group around 2**32-1 that is a bit too small. For this reason, the implementation
// `arc4random() % max_bounds` would be insufficient. Here we compute the last number of the
// last "full group". Note that if max_bounds is a divisor of UINT32_MAX,
// then we end up with UINT32_MAX:
const u32 max_usable = UINT32_MAX - (static_cast<u64>(UINT32_MAX) + 1) % max_bounds;
auto random_value = get_random<u32>();
for (int i = 0; i < 20 && random_value > max_usable; ++i) {
// By chance we picked a value from the incomplete group. Note that this group has size at
// most 2**31-1, so picking this group has a chance of less than 50%.
// In practice, this means that for the worst possible input, there is still only a
// once-in-a-million chance to get to iteration 20. In theory we should be able to loop
// forever. Here we prefer marginally imperfect random numbers over weird runtime behavior.
random_value = get_random<u32>();
}
return random_value % max_bounds;
}
}
|
