LibC: Implement uniform random sampling without modulo bias

1 files changed, 16 insertions, 3 deletions

diff --git a/Userland/Libraries/LibC/stdlib.cpp b/Userland/Libraries/LibC/stdlib.cpp
index cddf548c25..47dd242bb0 100644
--- a/Userland/Libraries/LibC/stdlib.cpp
+++ b/Userland/Libraries/LibC/stdlib.cpp
@@ -1039,9 +1039,22 @@ void arc4random_buf(void* buffer, size_t buffer_size)
 
 uint32_t arc4random_uniform(uint32_t max_bounds)
 {
-    // XXX: Should actually apply special rules for uniformity; avoid what is
-    // called "modulo bias".
-    return arc4random() % 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 uint32_t max_usable = UINT32_MAX - (static_cast<uint64_t>(UINT32_MAX) + 1) % max_bounds;
+    uint32_t random_value = arc4random();
+    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 = arc4random();
+    }
+    return random_value % max_bounds;
 }
 
 char* realpath(const char* pathname, char* buffer)