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

[Tristan Matthews]

Hi,

On Fri, Oct 20, 2017 at 6:30 PM, Yegor Timoshenko
<yegortimoshenko at gmail.com> wrote:
> 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));

You need to check if malloc returned NULL here.

>> +    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);

You should check the return value of pthread_setspecific, and clean up
if it failed.

Best,
Tristan

>> +  }
>> +
>> +  pcg32_random_b(rng, buf, len);
>>  }
>> --
>> 2.14.2
>>
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel