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