[hackers] [sbase][PATCH] libutil/random: rewrite whole algorithm

From: Elie Le Vaillant <eolien55_AT_disroot.org>
Date: Sun, 3 Mar 2024 16:07:49 +0100

libutil/random.c now includes a custom PRNG, which is the PCG family.
It also overhauls random_uniform(), making it way faster. Names were
changed (s/random/rng32/g), and reentrant versions added.
The PRNG is faster than libc's random().
It is way faster than the previous version, which used

---
 libutil/random.c | 90 ++++++++++++++++++++++++++++++++----------------
 util.h           |  9 +++--
 2 files changed, 67 insertions(+), 32 deletions(-)
diff --git a/libutil/random.c b/libutil/random.c
index 48eeb79..780ba29 100644
--- a/libutil/random.c
+++ b/libutil/random.c
_AT_@ -1,46 +1,76 @@
 #include <stdint.h>
-#include <stdlib.h>
 #include <time.h>
 
+static uint64_t globalstate;
+
 /*
- * Uniformity is achieved by generating new random numbers until the one
- * returned is outside the range [0, 2**32 % upper_bound).  This
- * guarantees the selected random number will be inside
- * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound)
- * after reduction modulo upper_bound.
- *
- * Copied off OpenBSD (original is arc4random_uniform)
+ * PCG construction
+ * seeding the RNG means merely setting the initial state.
+ * the increment could also be made part of the seed, just make sure it's odd.
  */
 uint32_t
-random_uniform(uint32_t upper_bound)
+rng32_r(uint64_t *state)
 {
-	uint32_t r, min;
-
-	if (upper_bound < 2)
-		return 0;
-
-	/* 2**32 % x == (2**32 - x) % x */
-	min = -upper_bound % upper_bound;
-
-	/*
-	 * This could theoretically loop forever but each retry has
-	 * p > 0.5 (worst case, usually far better) of selecting a
-	 * number inside the range we need, so it should rarely need
-	 * to re-roll.
-	 */
-	for (;;) {
-		r = random(); /* arc4random() is better, but we don't always have it */
-		if (r >= min)
-			break;
+	uint64_t oldstate = *state;
+	uint32_t r, v;
+
+	*state *= UINT64_C(0x9E3793492EEDC3F7);
+	*state += 0x1337;
+
+	r = oldstate >> (64 - 5);
+	v = (oldstate ^ (oldstate >> 18)) >> (32 - 5);
+	v = (v >> (-r & 31)) | (v << r);
+	return v;
+}
+
+uint32_t
+rng32(void)
+{
+	return rng32_r(&globalstate);
+}
+
+/*
+ * Based on optimized Lemire's method
+ * https://pcg-random.org/posts/bounded-rands.html
+ */
+uint32_t
+rng32_bounded_r(uint64_t *state, uint32_t range) {
+	uint32_t x = rng32_r(state);
+	uint64_t m = (uint64_t)x * (uint64_t)range;
+	uint32_t l = (uint32_t)m;
+	if (l < range) {
+		uint32_t t = -range;
+		if (t >= range) {
+			t -= range;
+			if (t >= range) 
+				t %= range;
+		}
+		while (l < t) {
+			x = rng32_r(state);
+			m = (uint64_t)x * (uint64_t)range;
+			l = (uint32_t)m;
+		}
 	}
+	return m >> 32;
+}
 
-	return r % upper_bound;
+uint64_t
+rng32_bounded(uint32_t range)
+{
+	return rng32_bounded_r(&globalstate, range);
 }
 
+/* Initialize state with somewhat random number */
 void
-random_seed(void)
+rng32_seed_r(uint64_t *state)
 {
 	struct timespec ts;
 	clock_gettime(CLOCK_REALTIME, &ts);
-	srandom(ts.tv_nsec); /* not a good source of randomness, but eh */
+	*state = ts.tv_nsec;
+}
+
+void
+rng32_seed(void)
+{
+	rng32_seed_r(&globalstate);
 }
diff --git a/util.h b/util.h
index 4c9b5b2..b613af4 100644
--- a/util.h
+++ b/util.h
_AT_@ -92,5 +92,10 @@ int mkdirp(const char *, mode_t, mode_t);
 #undef memmem
 #define memmem xmemmem
 void *memmem(const void *, size_t, const void *, size_t);
-void random_seed(void);
-uint32_t random_uniform(uint32_t);
+
+uint32_t rng32_r(uint64_t*);
+uint32_t rng32(void);
+uint32_t rng32_bounded_r(uint64_t*, uint32_t);
+uint32_t rng32_bounded(uint32_t);
+void rng32_seed_r(uint64_t*);
+void rng32_seed(void);
-- 
2.44.0

Received on Sun Mar 03 2024 - 16:07:49 CET