[Pixman] [PATCH 1/4] Fix lcg_rand_u32() to return 32 random bits.

[Andrea Canciani]

On Thu, Aug 4, 2011 at 4:21 AM, Søren Sandmann <sandmann at cs.au.dk> wrote:
> From: Søren Sandmann Pedersen <ssp at redhat.com>
>
> The lcg_rand() function only returns 15 random bits, so lcg_rand_u32()
> would always have 0 in bit 31 and bit 15. Fix that by calling
> lcg_rand() three times, to generate 15, 15, and 2 random bits
> respectively.
> ---
>  test/utils.h |    5 +++--
>  1 files changed, 3 insertions(+), 2 deletions(-)
>
> diff --git a/test/utils.h b/test/utils.h
> index 615ad78..a249627 100644
> --- a/test/utils.h
> +++ b/test/utils.h
> @@ -45,9 +45,10 @@ static inline uint32_t
>  lcg_rand_u32 (void)
>  {
>     uint32_t lo = lcg_rand();
> -    uint32_t hi = lcg_rand();
> +    uint32_t mid = lcg_rand() << 15;
> +    uint32_t hi = lcg_rand() << 30;
>
> -    return (hi << 16) | lo;
> +    return (hi | mid | lo);

lcg has more randomness in the high bits, so we might want
to keep them (hi discards everything but the last two bits).
We could probably get slightly better randomness by doing
something like:

-    uint32_t lo = lcg_rand();
-    uint32_t hi = lcg_rand();
+    uint32_t lo = lcg_rand() >> -(32 - 15 - 11*2);
+    uint32_t mid = lcg_rand() << (32 - 15 - 11*1);
+    uint32_t hi = lcg_rand() << (32 - 15 - 11*0);

-    return (hi << 16) | lo;
+    return hi ^ mid ^ lo;

This uses the 10/11 most significant bits from the 3 lcg results
(and mixes them with the low from the adjacent one... instead
of mixing we could just discard the low ones, but it just makes
the code more complicated).

I'm not sure if this is worth the effort, because lcg is not a great
RNG anyway, but maybe the change is simple enough to make
it reasonable.

Andrea

>  }
>
>  /* CRC 32 computation
> --
> 1.7.4
>
> _______________________________________________
> Pixman mailing list
> Pixman at lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/pixman
>