Change evutil_weakrand_() to avoid platform random()

This change allows us to avoid perturbing the platform's random(), and
to avoid hitting locks on random() in the platform's libc.

evutil_weakrand_() is, well, weak, so we choose here an algorithm that
favors speed over a number of other possibly desirable properties.
We're using a linear congruential generator, and taking our parameters
from those shared by the OpenBSD random() implementation, and
Glibc's fastest random() implementation.

The low bits of a LCG of modulus 2^32 are (notoriously) less random
than the higher bits.  So to generate a random value in a range, using
the % operator is no good; we ought to divide.  We add an
evutil_weakrand_range_() function to do that.

This code also changes the interface of evutil_weakrand_() so that it
now manipulates an explicit seed, rather than having the seed in a
static variable.  This change enables us to use existing locks to
achieve thread-safety, rather than having to rely on an additional lock.

(Patch by Nicholas Marriott; commit message by Nick Mathewson.)

1 files changed, 16 insertions, 7 deletions

diff --git a/evutil.c b/evutil.c
index abe15604..a87b5246 100644
--- a/evutil.c
+++ b/evutil.c
@@ -2273,14 +2273,23 @@ evutil_getenv_(const char *varname)
 	return getenv(varname);
 }
 
-long
-evutil_weakrand_(void)
+ev_uint32_t
+evutil_weakrand_(ev_uint32_t* seed)
 {
-#ifdef _WIN32
-	return rand();
-#else
-	return random();
-#endif
+	*seed = ((*seed) * 1103515245 + 12345) & 0x7fffffff;
+	return (*seed);
+}
+
+ev_uint32_t
+evutil_weakrand_range_(ev_uint32_t* seed, ev_uint32_t top)
+{
+	ev_uint32_t divisor, result;
+
+	divisor = EV_INT32_MAX / top;
+	do
+		result = evutil_weakrand_(seed) / divisor;
+	while (result > top);
+	return result;
 }
 
 int