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 Reviewed-by: Michael Niedermayer <mich...@niedermayer.cc> Signed-off-by: Ganesh Ajjanagadde <gajja...@gmail.com> --- libavutil/Makefile | 2 ++ libavutil/rand.c | 38 +++++++++++++++++++++++++++++++++++++ libavutil/rand.h | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 95 insertions(+) create mode 100644 libavutil/rand.c create mode 100644 libavutil/rand.h diff --git a/libavutil/Makefile b/libavutil/Makefile index 58df75a..fb20c8a 100644 --- a/libavutil/Makefile +++ b/libavutil/Makefile @@ -52,6 +52,7 @@ HEADERS = adler32.h \ pixdesc.h \ pixelutils.h \ pixfmt.h \ + rand.h \ random_seed.h \ rc4.h \ replaygain.h \ @@ -129,6 +130,7 @@ OBJS = adler32.o \ parseutils.o \ pixdesc.o \ pixelutils.o \ + rand.o \ random_seed.o \ rational.o \ reverse.o \ diff --git a/libavutil/rand.c b/libavutil/rand.c new file mode 100644 index 0000000..7f569a2 --- /dev/null +++ b/libavutil/rand.c @@ -0,0 +1,38 @@ +/* + * 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. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#include "attributes.h" +#include "rand.h" + +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); +} diff --git a/libavutil/rand.h b/libavutil/rand.h new file mode 100644 index 0000000..574c2a0 --- /dev/null +++ b/libavutil/rand.h @@ -0,0 +1,55 @@ +/* + * 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. + * + * FFmpeg is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * FFmpeg is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with FFmpeg; if not, write to the Free Software + * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + */ + +#ifndef AVUTIL_RAND_H +#define AVUTIL_RAND_H +#include <stdint.h> + +typedef struct AVRAND64 { + uint64_t state[2]; +} AVRAND64; + +/** + * 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 64 bit random number from the rng. + * + * @param rng AVRAND64 structure holding the state of the rng + * @return 64 bit random number + */ +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; +} + +#endif /* AVUTIL_RAND_H */ -- 2.7.3 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
