[FFmpeg-devel] [PATCH] lavu/lfg: add 64 bit random number generator

[Ganesh Ajjanagadde]

This is based on the relatively well known xorshift128+ of Sebastiano
Vigna (https://en.wikipedia.org/wiki/Xorshift) that performs very well on the
BigCrush suite, is very efficient, and is thus used by a number of
clients: http://xorshift.di.unimi.it/ (see Introduction).

Moreover, the implementation is in the public domain:
http://xorshift.di.unimi.it/xorshift128plus.c.

Concretely, it is nearly as fast as av_lfg_get (which only returns 32 bits),
and has a much smaller cache (128 bits). Thus, the timings should also
be more stable.

This is needed because av_lfg_get<<32 | av_lfg_get is far slower, and
likely less random as measured by BigCrush - most LFG's perform
quite poorly on the BigCrush suite:
http://www6.tw.freebsd.org/distfiles/testu01.pdf.
In particular, FFmpeg's seems to be Ran055 in the paper, see pg31.

Sample benchmark (Haswell, GCC + -march=native):
  23200 decicycles in 624 calls of av_lfg_get,       1 runs,      0 skips
  23040 decicycles in 624 calls of av_lfg_get,       2 runs,      0 skips
  22810 decicycles in 624 calls of av_lfg_get,       4 runs,      0 skips
[...]
  19884 decicycles in 624 calls of av_lfg_get,   65532 runs,      4 skips
  19880 decicycles in 624 calls of av_lfg_get,  131067 runs,      5 skips
  19884 decicycles in 624 calls of av_lfg_get,  262136 runs,      8 skips
  19877 decicycles in 624 calls of av_lfg_get,  524276 runs,     12 skips

  25380 decicycles in 624 calls of av_rand64_get,       1 runs,      0 skips
  28560 decicycles in 624 calls of av_rand64_get,       2 runs,      0 skips
  30112 decicycles in 624 calls of av_rand64_get,       4 runs,      0 skips
[...]
  22627 decicycles in 624 calls of av_rand64_get,   65536 runs,      0 skips
  22625 decicycles in 624 calls of av_rand64_get,  131072 runs,      0 skips
  22625 decicycles in 624 calls of av_rand64_get,  262143 runs,      1 skips
  22624 decicycles in 624 calls of av_rand64_get,  524286 runs,      2 skips

Signed-off-by: Ganesh Ajjanagadde <gajjanag at gmail.com>
---
 libavutil/lfg.c | 33 ++++++++++++++++++++++++++++++++-
 libavutil/lfg.h | 26 ++++++++++++++++++++++++++
 2 files changed, 58 insertions(+), 1 deletion(-)

diff --git a/libavutil/lfg.c b/libavutil/lfg.c
index 5ffd76f..e8e4adf 100644
--- a/libavutil/lfg.c
+++ b/libavutil/lfg.c
@@ -1,6 +1,11 @@
 /*
  * Lagged Fibonacci PRNG
  * Copyright (c) 2008 Michael Niedermayer
+ * 64 bit random number generator written by
+ * Written in 2015 by Sebastiano Vigna (vigna at acm.org)
+ * under public domain:
+ * https://creativecommons.org/publicdomain/zero/1.0/
+ *
  *
  * This file is part of FFmpeg.
  *
@@ -44,6 +49,19 @@ av_cold void av_lfg_init(AVLFG *c, unsigned int seed)
     c->index = 0;
 }
 
+static inline uint64_t next64(uint64_t x) {
+    uint64_t z = (x += UINT64_C(0x9E3779B97F4A7C15));
+    z = (z ^ (z >> 30)) * UINT64_C(0xBF58476D1CE4E5B9);
+    z = (z ^ (z >> 27)) * UINT64_C(0x94D049BB133111EB);
+    return z ^ (z >> 31);
+}
+
+av_cold void av_rand64_init(AVRAND64 *rng, uint64_t seed)
+{
+    rng->state[0] = seed;
+    rng->state[1] = next64(seed);
+}
+
 void av_bmg_get(AVLFG *lfg, double out[2])
 {
     double x1, x2, w;
@@ -66,11 +84,14 @@ void av_bmg_get(AVLFG *lfg, double out[2])
 int main(void)
 {
     int x = 0;
+    uint64_t y = 0;
     int i, j;
     AVLFG state;
+    AVRAND64 state64;
 
     av_lfg_init(&state, 0xdeadbeef);
-    for (j = 0; j < 10000; j++) {
+    av_rand64_init(&state64, UINT64_C(0xdeadbeefdeadbeef));
+    for (j = 0; j < 1000000; j++) {
         START_TIMER
         for (i = 0; i < 624; i++) {
             //av_log(NULL, AV_LOG_ERROR, "%X\n", av_lfg_get(&state));
@@ -80,6 +101,16 @@ int main(void)
     }
     av_log(NULL, AV_LOG_ERROR, "final value:%X\n", x);
 
+    for (j = 0; j < 1000000; j++) {
+        START_TIMER
+        for (i = 0; i < 624; i++) {
+            //av_log(NULL, AV_LOG_ERROR, "%X\n", av_lfg_get(&state));
+            y += av_rand64_get(&state64);
+            //y += ((uint64_t)av_lfg_get(&state) << 32) | av_lfg_get(&state);
+        }
+        STOP_TIMER("624 calls of av_rand64_get");
+    }
+
     /* BMG usage example */
     {
         double mean   = 1000;
diff --git a/libavutil/lfg.h b/libavutil/lfg.h
index ec90562..1f0f38d 100644
--- a/libavutil/lfg.h
+++ b/libavutil/lfg.h
@@ -1,6 +1,10 @@
 /*
  * Lagged Fibonacci PRNG
  * Copyright (c) 2008 Michael Niedermayer
+ * 64 bit random number generator written by
+ * Written in 2015 by Sebastiano Vigna (vigna at acm.org)
+ * under public domain:
+ * https://creativecommons.org/publicdomain/zero/1.0/
  *
  * This file is part of FFmpeg.
  *
@@ -21,15 +25,28 @@
 
 #ifndef AVUTIL_LFG_H
 #define AVUTIL_LFG_H
+#include <stdint.h>
 
 typedef struct AVLFG {
     unsigned int state[64];
     int index;
 } AVLFG;
 
+typedef struct AVRAND64 {
+    uint64_t state[2];
+} AVRAND64;
+
 void av_lfg_init(AVLFG *c, unsigned int seed);
 
 /**
+ * Initialize the 64 bit random number generator.
+ *
+ * @param rng AVRAND64 structure that is initialized
+ * @param seed 64 bit seed
+ */
+void av_rand64_init(AVRAND64 *rng, uint64_t seed);
+
+/**
  * Get the next random unsigned 32-bit number using an ALFG.
  *
  * Please also consider a simple LCG like state= state*1664525+1013904223,
@@ -40,6 +57,15 @@ static inline unsigned int av_lfg_get(AVLFG *c){
     return c->state[c->index++ & 63];
 }
 
+static inline uint64_t av_rand64_get(AVRAND64 *rng){
+    uint64_t x = rng->state[0];
+    uint64_t const y = rng->state[1];
+    rng->state[0] = y;
+    x ^= x << 23; // a
+    rng->state[1] = x ^ y ^ (x >> 17) ^ (y >> 26); // b, c
+    return rng->state[1] + y;
+}
+
 /**
  * Get the next random unsigned 32-bit number using a MLFG.
  *
-- 
2.7.3