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

[Yegor Timoshenko]

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 | 155 ++++++++++++++++++++++++++++---------------------------
 1 file changed, 79 insertions(+), 76 deletions(-)

diff --git a/src/posix/rand.c b/src/posix/rand.c
index 338f4675da..d1f7b174b7 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,101 @@
  *****************************************************************************/
 
 #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 <stdbool.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;
 
-static uint8_t okey[BLOCK_SIZE], ikey[BLOCK_SIZE];
+  xsh = ((rng->state >> 18u) ^ rng->state) >> 27u;
+  rot = rng->state >> 59u;
 
-static void vlc_rand_init (void)
+  rng->state *= 6364136223846793005ULL;
+  rng->state += rng->inc | 1;
+
+  return (xsh >> rot) | (xsh << ((-rot) & 31));
+}
+
+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;
+  int ret = 0;
+
+  pthread_once(&pcg32_rng_once, pcg32_rng_key_create);
+
+  if ((rng = pthread_getspecific(pcg32_rng)) == NULL) {
+    rng = malloc(sizeof(pcg32_random_t));
+
+    if (rng == NULL)
+      return;
+
+    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);
+    ret = pthread_setspecific(pcg32_rng, rng);
+  }
+
+  pcg32_random_b(rng, buf, len);
+  if (ret) free(rng);
 }
-- 
2.14.2