summaryrefslogtreecommitdiff
path: root/src/librandom
diff options
context:
space:
mode:
authorLaurent Bercot <ska-skaware@skarnet.org>2016-10-19 01:44:27 +0000
committerLaurent Bercot <ska-skaware@skarnet.org>2016-10-19 01:44:27 +0000
commit58b993dd48fe140047c326a82dea9ec3055cf334 (patch)
tree036bffea357ef6d1fc2b0136ac7e6afb2db94aa5 /src/librandom
parent67a454f72e4194dae9764fcc85aa426db0fa9334 (diff)
downloadskalibs-58b993dd48fe140047c326a82dea9ec3055cf334.tar.xz
Better random_uint32 uniformity algorithm
Diffstat (limited to 'src/librandom')
-rw-r--r--src/librandom/random_uint32.c39
1 files changed, 9 insertions, 30 deletions
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