Fix biased output of randi_range

2 files changed, 11 insertions, 0 deletions

diff --git a/thirdparty/misc/pcg.cpp b/thirdparty/misc/pcg.cpp
index c421e16f89..5f4bf40460 100644
--- a/thirdparty/misc/pcg.cpp
+++ b/thirdparty/misc/pcg.cpp
@@ -23,3 +23,13 @@ void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq)
     rng->state += initstate;
     pcg32_random_r(rng);
 }
+
+// Source from https://github.com/imneme/pcg-c-basic/blob/master/pcg_basic.c
+uint32_t pcg32_boundedrand_r(pcg32_random_t *rng, uint32_t bound) {
+	uint32_t threshold = -bound % bound;
+	for (;;) {
+		uint32_t r = pcg32_random_r(rng);
+		if (r >= threshold)
+			return r % bound;
+	}
+}
diff --git a/thirdparty/misc/pcg.h b/thirdparty/misc/pcg.h
index 6f42b3b094..0faab73e64 100644
--- a/thirdparty/misc/pcg.h
+++ b/thirdparty/misc/pcg.h
@@ -11,5 +11,6 @@
 typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
 uint32_t pcg32_random_r(pcg32_random_t* rng);
 void pcg32_srandom_r(pcg32_random_t* rng, uint64_t initstate, uint64_t initseq);
+uint32_t pcg32_boundedrand_r(pcg32_random_t* rng, uint32_t bound);
 
 #endif // RANDOM_H