[vlc-devel] [PATCH] rand: implement a per-thread PCG random number generator for POSIX

[Yegor Timoshenko]

And done! Tristan, thanks for pointing this out.

On Fri, Oct 20, 2017 at 10:19 PM, Yegor Timoshenko
<yegortimoshenko at gmail.com> wrote:
> PCG RNG has a lot of useful qualities that make it the best fit as of
> yet for VLC. It generates numbers of very high statistical quality,
> very fast, with very little code, and is not easily predictable. See:
>
> http://www.pcg-random.org
> http://www.pcg-random.org/other-rngs.html
>
> Now there's one RNG for each thread, instead of locking.
>
> The next logical step would be to decouple platform-specific entropy
> sources (used for seeding) and RNG implementations, currently these
> two are intermingled in vlc_rand_bytes() function. Then it would be
> possible to use this RNG algorithm on other platforms.
> ---
>  src/posix/rand.c | 148 +++++++++++++++++++++++++++----------------------------
>  1 file changed, 72 insertions(+), 76 deletions(-)
>
> diff --git a/src/posix/rand.c b/src/posix/rand.c
> index 338f4675da..48b179b120 100644
> --- a/src/posix/rand.c
> +++ b/src/posix/rand.c
> @@ -1,8 +1,8 @@
>  /*****************************************************************************
> - * rand.c : non-predictible random bytes generator
> + * rand.c : per-thread PCG RNG (see http://www.pcg-random.org)
>   *****************************************************************************
> - * Copyright © 2007 Rémi Denis-Courmont
> - * $Id$
> + * Copyright (C) 2007 Rémi Denis-Courmont
> + * Copyright (C) 2017 Yegor Timoshenko <yegortimoshenko at gmail.com>
>   *
>   * This program is free software; you can redistribute it and/or modify it
>   * under the terms of the GNU Lesser General Public License as published by
> @@ -20,98 +20,94 @@
>   *****************************************************************************/
>
>  #ifdef HAVE_CONFIG_H
> -# include "config.h"
> +#include "config.h"
>  #endif
>
>  #include <vlc_common.h>
> +#include <vlc_fs.h>
>  #include <vlc_rand.h>
>
> +#include <fcntl.h>
> +#include <pthread.h>
>  #include <stdint.h>
>  #include <string.h>
>  #include <stdlib.h>
> -
> -#include <sys/types.h>
> -#include <fcntl.h>
>  #include <unistd.h>
> -#include <pthread.h>
> -#include <vlc_fs.h>
>
> -#include <vlc_md5.h>
> +typedef struct { uint64_t state;  uint64_t inc; } pcg32_random_t;
>
> -/*
> - * Pseudo-random number generator using a HMAC-MD5 in counter mode.
> - * Probably not very secure (expert patches welcome) but definitely
> - * better than rand() which is defined to be reproducible...
> - */
> -#define BLOCK_SIZE 64
> +static uint32_t pcg32_random_r(pcg32_random_t *rng)
> +{
> +  uint64_t xsh, rot;
> +
> +  xsh = ((rng->state >> 18u) ^ rng->state) >> 27u;
> +  rot = rng->state >> 59u;
>
> -static uint8_t okey[BLOCK_SIZE], ikey[BLOCK_SIZE];
> +  rng->state *= 6364136223846793005ULL;
> +  rng->state += rng->inc | 1;
> +
> +  return (xsh >> rot) | (xsh << ((-rot) & 31));
> +}
>
> -static void vlc_rand_init (void)
> +static void pcg32_random_b(pcg32_random_t *rng, uint8_t *buf, size_t len)
>  {
> -    uint8_t key[BLOCK_SIZE];
> -
> -    /* Get non-predictible value as key for HMAC */
> -    int fd = vlc_open ("/dev/urandom", O_RDONLY);
> -    if (fd == -1)
> -        return; /* Uho! */
> -
> -    for (size_t i = 0; i < sizeof (key);)
> -    {
> -         ssize_t val = read (fd, key + i, sizeof (key) - i);
> -         if (val > 0)
> -             i += val;
> -    }
> +  size_t i, j;
> +  uint32_t n;
>
> -    /* Precompute outer and inner keys for HMAC */
> -    for (size_t i = 0; i < sizeof (key); i++)
> -    {
> -        okey[i] = key[i] ^ 0x5c;
> -        ikey[i] = key[i] ^ 0x36;
> -    }
> +  for (i = 0; i < len; i += sizeof(n)) {
> +    j = len - i;
> +    n = pcg32_random_r(rng);
>
> -    vlc_close (fd);
> +    memcpy(buf + i, &n, j < sizeof(n) ? j : sizeof(n));
> +  }
>  }
>
> +static void pcg32_srandom_r(pcg32_random_t* rng, uint64_t state, uint64_t inc)
> +{
> +  rng->state = 0U;
> +  rng->inc = (inc << 1u) | 1u;
> +  pcg32_random_r(rng);
>
> -void vlc_rand_bytes (void *buf, size_t len)
> +  rng->state += state;
> +  pcg32_random_r(rng);
> +}
> +
> +static pthread_key_t pcg32_rng;
> +static pthread_once_t pcg32_rng_once = PTHREAD_ONCE_INIT;
> +
> +static void pcg32_rng_key_create()
>  {
> -    static pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
> -    static uint64_t counter = 0;
> -
> -    uint64_t stamp = NTPtime64 ();
> -
> -    while (len > 0)
> -    {
> -        uint64_t val;
> -        struct md5_s mdi, mdo;
> -
> -        InitMD5 (&mdi);
> -        InitMD5 (&mdo);
> -
> -        pthread_mutex_lock (&lock);
> -        if (counter == 0)
> -            vlc_rand_init ();
> -        val = counter++;
> -
> -        AddMD5 (&mdi, ikey, sizeof (ikey));
> -        AddMD5 (&mdo, okey, sizeof (okey));
> -        pthread_mutex_unlock (&lock);
> -
> -        AddMD5 (&mdi, &stamp, sizeof (stamp));
> -        AddMD5 (&mdi, &val, sizeof (val));
> -        EndMD5 (&mdi);
> -        AddMD5 (&mdo, mdi.buf, 16);
> -        EndMD5 (&mdo);
> -
> -        if (len < 16)
> -        {
> -            memcpy (buf, mdo.buf, len);
> -            break;
> -        }
> -
> -        memcpy (buf, mdo.buf, 16);
> -        len -= 16;
> -        buf = ((uint8_t *)buf) + 16;
> +  pthread_key_create(&pcg32_rng, NULL);
> +}
> +
> +void vlc_rand_bytes(void *buf, size_t len)
> +{
> +  pcg32_random_t *rng;
> +  uint64_t state, inc;
> +  int fd;
> +
> +  pthread_once(&pcg32_rng_once, pcg32_rng_key_create);
> +
> +  if ((rng = pthread_getspecific(pcg32_rng)) == NULL) {
> +    rng = malloc(sizeof(pcg32_random_t));
> +    fd = vlc_open("/dev/urandom", O_RDONLY);
> +
> +    if (fd == -1) {
> +      free(rng);
> +      return;
> +    }
> +
> +    if (read(fd, &state, sizeof(state)) == -1 ||
> +       read(fd, &inc, sizeof(inc)) == -1) {
> +      vlc_close(fd);
> +      free(rng);
> +      return;
>      }
> +
> +    vlc_close(fd);
> +    pcg32_srandom_r(rng, state, inc);
> +    pthread_setspecific(pcg32_rng, rng);
> +  }
> +
> +  pcg32_random_b(rng, buf, len);
>  }
> --
> 2.14.2
>