Optimize arc4random_uniform() (by syncing with OpenBSD implementation)

1. In d4de062, in Feb 2010, libevent adopted OpenBSD implementation of
   arc4random_uniform.
2. In
   https://github.com/openbsd/src/commit/728918cba93e0418bea2a73c9784f6b80c2a9dbd,
   in Jun 2012, OpenBSD improved their implementation to be faster, by
   changing arc4random_uniform() to calculate ``2**32 % upper_bound'' as
   ``-upper_bound % upper_bound''.

Alternatively we can simply remove arc4random_uniform() since it is not
used by libevent anyway, but let's just sync the header for now.

diff --git a/arc4random.c b/arc4random.c
index b3ec765510d69a99acb4de83c86a6016268b3aa6..21a12755779d8e849e5ea193cd0d4299fcb86ac5 100644 (file)
--- a/arc4random.c
+++ b/arc4random.c
@@ -506,17 +506,8 @@ arc4random_uniform(unsigned int upper_bound)
        if (upper_bound < 2)
                return 0;
 
-#if (UINT_MAX > 0xffffffffUL)
-       min = 0x100000000UL % upper_bound;
-#else
-       /* Calculate (2**32 % upper_bound) avoiding 64-bit math */
-       if (upper_bound > 0x80000000)
-               min = 1 + ~upper_bound;         /* 2**32 - upper_bound */
-       else {
-               /* (2**32 - (x * 2)) % x == 2**32 % x when x <= 2**31 */
-               min = ((0xffffffff - (upper_bound * 2)) + 1) % upper_bound;
-       }
-#endif
+       /* 2**32 % x == (2**32 - x) % x */
+       min = -upper_bound % upper_bound;
 
        /*
         * This could theoretically loop forever but each retry has