From 58b993dd48fe140047c326a82dea9ec3055cf334 Mon Sep 17 00:00:00 2001
From: Laurent Bercot <ska-skaware@skarnet.org>
Date: Wed, 19 Oct 2016 01:44:27 +0000
Subject:  Better random_uint32 uniformity algorithm

---
 package/deps.mak              |  2 +-
 src/librandom/random_uint32.c | 39 +++++++++------------------------------
 2 files changed, 10 insertions(+), 31 deletions(-)

diff --git a/package/deps.mak b/package/deps.mak
index bc6dbf2..58fd526 100644
--- a/package/deps.mak
+++ b/package/deps.mak
@@ -135,7 +135,7 @@ src/librandom/random_makeseed.o src/librandom/random_makeseed.lo: src/librandom/
 src/librandom/random_name.o src/librandom/random_name.lo: src/librandom/random_name.c src/include/skalibs/random.h
 src/librandom/random_sauniquename.o src/librandom/random_sauniquename.lo: src/librandom/random_sauniquename.c src/include/skalibs/random.h src/include/skalibs/skamisc.h src/include/skalibs/stralloc.h
 src/librandom/random_string.o src/librandom/random_string.lo: src/librandom/random_string.c src/include/skalibs/allreadwrite.h src/include/skalibs/nonposix.h src/librandom/random-internal.h src/include/skalibs/random.h src/include/skalibs/sysdeps.h
-src/librandom/random_uint32.o src/librandom/random_uint32.lo: src/librandom/random_uint32.c src/include/skalibs/bytestr.h src/include/skalibs/nonposix.h src/include/skalibs/random.h src/include/skalibs/sysdeps.h src/include/skalibs/uint32.h
+src/librandom/random_uint32.o src/librandom/random_uint32.lo: src/librandom/random_uint32.c src/include/skalibs/nonposix.h src/include/skalibs/random.h src/include/skalibs/sysdeps.h src/include/skalibs/uint32.h
 src/librandom/random_unsort.o src/librandom/random_unsort.lo: src/librandom/random_unsort.c src/include/skalibs/bytestr.h src/include/skalibs/random.h src/include/skalibs/uint32.h
 src/librandom/surf.o src/librandom/surf.lo: src/librandom/surf.c src/include/skalibs/bytestr.h src/include/skalibs/surf.h src/include/skalibs/uint32.h
 src/librandom/surf_init.o src/librandom/surf_init.lo: src/librandom/surf_init.c src/include/skalibs/surf.h src/include/skalibs/uint32.h
diff --git a/src/librandom/random_uint32.c b/src/librandom/random_uint32.c
index 5fda0d3..9009a59 100644
--- a/src/librandom/random_uint32.c
+++ b/src/librandom/random_uint32.c
@@ -6,6 +6,7 @@
 
 #include <skalibs/nonposix.h>
 #include <stdlib.h>
+#include <skalibs/uint32.h>
 #include <skalibs/random.h>
 
 uint32 random_uint32 (uint32 n)
@@ -16,43 +17,21 @@ uint32 random_uint32 (uint32 n)
 #else
 
 #include <skalibs/uint32.h>
-#include <skalibs/bytestr.h>
 #include <skalibs/random.h>
 
-static inline uint32 random_mask2 (register uint32 n)
-{
-  for (;;)
-  {
-    register uint32 m = n | (n >> 1) ;
-    if (m == n) return n ;
-    n = m ;
-  }
-}
-
-static inline unsigned int random_nchars (register uint32 n)
-{
-  return n <= 0xff ? 1 :
-         n <= 0xffff ? 2 :
-         n <= 0xffffffUL ? 3 : 4 ;
-}
-
 uint32 random_uint32 (uint32 n)
 {
-  if (!n) return 0 ;
-  else
+  uint32 min, x ;
+  if (n < 2) return 0 ;
+  min = -n % n ;
+  for (;;)
   {
-    uint32 i = n, m = random_mask2(n-1) ;
-    unsigned int nchars = random_nchars(n) ;
     char tmp[4] ;
-    while (i >= n)
-    {
-      random_string(tmp, nchars) ;
-      byte_zero(tmp + nchars, 4 - nchars) ;
-      uint32_unpack(tmp, &i) ;
-      i &= m ;
-    }
-    return i ;
+    random_string(tmp, 4) ;
+    uint32_unpack(tmp, &x) ;
+    if (x >= min) break ;
   }
+  return x % n ;
 }
 
 #endif
-- 
cgit v1.2.3