[FFmpeg-devel] [PATCHv3 1/3] lavu/rand: add 64 bit random number generator
Ganesh Ajjanagadde
gajjanag at gmail.com
Tue Mar 15 05:46:59 CET 2016
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 <michael at niedermayer.cc>
Signed-off-by: Ganesh Ajjanagadde <gajjanag at 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 (vigna at 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 (vigna at 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
More information about the ffmpeg-devel
mailing list