[ovs-dev] [PATCH] random: Implement a decent random number generator.

Ben Pfaff blp at nicira.com
Wed Aug 11 22:59:38 UTC 2010


Thanks, pushed.

On Wed, Aug 11, 2010 at 03:48:22PM -0700, Justin Pettit wrote:
> Looks good.
> 
> --Justin
> 
> 
> On Aug 5, 2010, at 10:23 AM, Ben Pfaff wrote:
> 
> > Until now this library has based its random number upon those returned
> > by libc's rand() function.  This has always bugged me--it is not a good
> > solution since rand() varies in quality so much.  This commit changes
> > the random library to use a simple but high-quality PRNG.
> > ---
> > lib/random.c |   77 ++++++++++++++++++++++++++++++++++++----------------------
> > 1 files changed, 48 insertions(+), 29 deletions(-)
> > 
> > diff --git a/lib/random.c b/lib/random.c
> > index 18bd444..78a5916 100644
> > --- a/lib/random.c
> > +++ b/lib/random.c
> > @@ -1,5 +1,5 @@
> > /*
> > - * Copyright (c) 2008, 2009 Nicira Networks.
> > + * Copyright (c) 2008, 2009, 2010 Nicira Networks.
> >  *
> >  * Licensed under the Apache License, Version 2.0 (the "License");
> >  * you may not use this file except in compliance with the License.
> > @@ -23,17 +23,35 @@
> > 
> > #include "util.h"
> > 
> > +/* This is the 32-bit PRNG recommended in G. Marsaglia, "Xorshift RNGs",
> > + * _Journal of Statistical Software_ 8:14 (July 2003).  According to the paper,
> > + * it has a period of 2**32 - 1 and passes almost all tests of randomness.
> > + *
> > + * We use this PRNG instead of libc's rand() because rand() varies in quality
> > + * and because its maximum value also varies between 32767 and INT_MAX, whereas
> > + * we often want random numbers in the full range of uint32_t.  */
> > +
> > +/* Current random state. */
> > +static uint32_t seed;
> > +
> > +static uint32_t random_next(void);
> > +
> > void
> > random_init(void)
> > {
> > -    static bool inited = false;
> > -    if (!inited) {
> > +    if (!seed) {
> >         struct timeval tv;
> > -        inited = true;
> > +
> >         if (gettimeofday(&tv, NULL) < 0) {
> >             ovs_fatal(errno, "gettimeofday");
> >         }
> > -        srand(tv.tv_sec ^ tv.tv_usec);
> > +
> > +        seed = tv.tv_sec ^ tv.tv_usec;
> > +        if (!seed) {
> > +            /* A 'seed' of 0 is fatal to randomness--the random value will
> > +             * always be 0--so use the initial seed mentioned by Marsaglia. */
> > +            seed = UINT32_C(2463534242);
> > +        }
> >     }
> > }
> > 
> > @@ -41,50 +59,51 @@ void
> > random_bytes(void *p_, size_t n)
> > {
> >     uint8_t *p = p_;
> > +
> >     random_init();
> > -    while (n--) {
> > -        *p++ = rand();
> > +
> > +    for (; n > 4; p += 4, n -= 4) {
> > +        uint32_t x = random_next();
> > +        memcpy(p, &x, 4);
> > +    }
> > +
> > +    if (n) {
> > +        uint32_t x = random_next();
> > +        memcpy(p, &x, n);
> >     }
> > }
> > 
> > uint8_t
> > random_uint8(void)
> > {
> > -    random_init();
> > -    return rand();
> > +    return random_uint32();
> > }
> > 
> > uint16_t
> > random_uint16(void)
> > {
> > -    if (RAND_MAX >= UINT16_MAX) {
> > -        random_init();
> > -        return rand();
> > -    } else {
> > -        uint16_t x;
> > -        random_bytes(&x, sizeof x);
> > -        return x;
> > -    }
> > +    return random_uint32();
> > }
> > 
> > uint32_t
> > random_uint32(void)
> > {
> > -    if (RAND_MAX >= UINT32_MAX) {
> > -        random_init();
> > -        return rand();
> > -    } else if (RAND_MAX == INT32_MAX) {
> > -        random_init();
> > -        return rand() | ((rand() & 1u) << 31);
> > -    } else {
> > -        uint32_t x;
> > -        random_bytes(&x, sizeof x);
> > -        return x;
> > -    }
> > +    random_init();
> > +    return random_next();
> > }
> > 
> > int
> > -random_range(int max) 
> > +random_range(int max)
> > {
> >     return random_uint32() % max;
> > }
> > +
> > +static uint32_t
> > +random_next(void)
> > +{
> > +    seed ^= seed << 13;
> > +    seed >>= 17;
> > +    seed ^= seed << 5;
> > +
> > +    return seed;
> > +}
> > -- 
> > 1.7.1
> > 
> > 
> > _______________________________________________
> > dev mailing list
> > dev at openvswitch.org
> > http://openvswitch.org/mailman/listinfo/dev_openvswitch.org
> 




More information about the dev mailing list