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 <gajja...@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 (vi...@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 (vi...@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 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
