[vlc-devel] [PATCH] rand: implement a per-thread PCG random number generator for POSIX
Tristan Matthews
tmatth at videolan.org
Sat Oct 21 00:44:03 CEST 2017
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
More information about the vlc-devel
mailing list