diff options
| author | Laurent Bercot <ska-skaware@skarnet.org> | 2016-10-19 01:44:27 +0000 |
|---|---|---|
| committer | Laurent Bercot <ska-skaware@skarnet.org> | 2016-10-19 01:44:27 +0000 |
| commit | 58b993dd48fe140047c326a82dea9ec3055cf334 (patch) | |
| tree | 036bffea357ef6d1fc2b0136ac7e6afb2db94aa5 | |
| parent | 67a454f72e4194dae9764fcc85aa426db0fa9334 (diff) | |
| download | skalibs-58b993dd48fe140047c326a82dea9ec3055cf334.tar.xz | |
Better random_uint32 uniformity algorithm
| -rw-r--r-- | package/deps.mak | 2 | ||||
| -rw-r--r-- | 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 |