summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLeo Izen <leo.izen@gmail.com>2022-08-14 21:28:54 -0400
committerLeo Izen <leo.izen@gmail.com>2022-08-17 10:21:55 -0400
commit52e7269ea633b7ac3d83d7b5cba9b15c5fbcbef9 (patch)
tree89b68afb896b8b50a304b5bc79625775d4ba3252
parent813164cc07124aabfbc4aa3b8f9fe33fe222c77c (diff)
downloadmpv-52e7269ea633b7ac3d83d7b5cba9b15c5fbcbef9.tar.bz2
mpv-52e7269ea633b7ac3d83d7b5cba9b15c5fbcbef9.tar.xz
misc/random: add xoshiro random number implementation
Add xoshiro as a PRNG implementation instead of relying on srand() and rand() from the C standard library. This, in particular, lets us avoid platform-defined behavior with respect to threading.
-rw-r--r--common/playlist.c3
-rw-r--r--libmpv/client.h2
-rw-r--r--meson.build1
-rw-r--r--misc/random.c75
-rw-r--r--misc/random.h41
-rw-r--r--osdep/io.c3
-rw-r--r--osdep/timer.c3
-rw-r--r--wscript_build.py1
8 files changed, 124 insertions, 5 deletions
diff --git a/common/playlist.c b/common/playlist.c
index b7398dd936..21e5f63097 100644
--- a/common/playlist.c
+++ b/common/playlist.c
@@ -21,6 +21,7 @@
#include "common/common.h"
#include "common/global.h"
#include "common/msg.h"
+#include "misc/random.h"
#include "mpv_talloc.h"
#include "options/path.h"
@@ -147,7 +148,7 @@ void playlist_shuffle(struct playlist *pl)
for (int n = 0; n < pl->num_entries; n++)
pl->entries[n]->original_index = n;
for (int n = 0; n < pl->num_entries - 1; n++) {
- int j = (int)((double)(pl->num_entries - n) * rand() / (RAND_MAX + 1.0));
+ size_t j = (size_t)((pl->num_entries - n) * mp_rand_next_double());
MPSWAP(struct playlist_entry *, pl->entries[n], pl->entries[n + j]);
}
playlist_update_indexes(pl, 0, -1);
diff --git a/libmpv/client.h b/libmpv/client.h
index 07ab7d44bc..fb10e5e01d 100644
--- a/libmpv/client.h
+++ b/libmpv/client.h
@@ -152,8 +152,6 @@ extern "C" {
* - Using UNIX IPC (off by default) will override the SIGPIPE signal handler,
* and set it to SIG_IGN. Some invocations of the "subprocess" command will
* also do that.
- * - mpv will reseed the legacy C random number generator by calling srand() at
- * some random point once.
* - mpv may start sub processes, so overriding SIGCHLD, or waiting on all PIDs
* (such as calling wait()) by the parent process or any other library within
* the process must be avoided. libmpv itself only waits for its own PIDs.
diff --git a/meson.build b/meson.build
index 3a1fe0b471..3d78eec5dd 100644
--- a/meson.build
+++ b/meson.build
@@ -134,6 +134,7 @@ sources = files(
'misc/json.c',
'misc/natural_sort.c',
'misc/node.c',
+ 'misc/random.c',
'misc/rendezvous.c',
'misc/thread_pool.c',
'misc/thread_tools.c',
diff --git a/misc/random.c b/misc/random.c
new file mode 100644
index 0000000000..780c67ec10
--- /dev/null
+++ b/misc/random.c
@@ -0,0 +1,75 @@
+/*
+ * Implementation of non-cryptographic pseudo-random number
+ * generator algorithm known as xoshiro.
+ *
+ * This file is part of mpv.
+ *
+ * mpv 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.
+ *
+ * mpv 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 mpv. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdint.h>
+#include <pthread.h>
+
+#include "random.h"
+
+static uint64_t state[4];
+static pthread_mutex_t state_mutex = PTHREAD_MUTEX_INITIALIZER;
+
+static inline uint64_t rotl_u64(const uint64_t x, const int k)
+{
+ return (x << k) | (x >> (64 - k));
+}
+
+static inline uint64_t splitmix64(uint64_t *const 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);
+}
+
+void mp_rand_seed(uint64_t seed)
+{
+ pthread_mutex_lock(&state_mutex);
+ state[0] = seed;
+ for (int i = 1; i < 4; i++)
+ state[i] = splitmix64(&seed);
+ pthread_mutex_unlock(&state_mutex);
+}
+
+uint64_t mp_rand_next(void)
+{
+ uint64_t result, t;
+
+ pthread_mutex_lock(&state_mutex);
+
+ result = rotl_u64(state[1] * 5, 7) * 9;
+ t = state[1] << 17;
+
+ state[2] ^= state[0];
+ state[3] ^= state[1];
+ state[1] ^= state[2];
+ state[0] ^= state[3];
+ state[2] ^= t;
+ state[3] = rotl_u64(state[3], 45);
+
+ pthread_mutex_unlock(&state_mutex);
+
+ return result;
+}
+
+double mp_rand_next_double(void)
+{
+ return (mp_rand_next() >> 11) * 0x1.0p-53;
+}
diff --git a/misc/random.h b/misc/random.h
new file mode 100644
index 0000000000..9a3bef2fbc
--- /dev/null
+++ b/misc/random.h
@@ -0,0 +1,41 @@
+/*
+ * Implementation of non-cryptographic pseudo-random number
+ * generator algorithm known as xoshiro.
+ *
+ * This file is part of mpv.
+ *
+ * mpv 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.
+ *
+ * mpv 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 mpv. If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#pragma once
+
+#include <stdint.h>
+
+/*
+ * Initialize the pseudo-random number generator's state with
+ * the given 64-bit seed.
+ */
+void mp_rand_seed(uint64_t seed);
+
+/*
+ * Return the next 64-bit psuedo-random integer, and update the state
+ * accordingly.
+ */
+uint64_t mp_rand_next(void);
+
+/*
+ * Return a double value in the range of [0.0, 1.0) with uniform
+ * distribution, and update the state accordingly.
+ */
+double mp_rand_next_double(void);
diff --git a/osdep/io.c b/osdep/io.c
index d4dcfc6fba..ec55aa2647 100644
--- a/osdep/io.c
+++ b/osdep/io.c
@@ -32,6 +32,7 @@
#include "mpv_talloc.h"
#include "config.h"
+#include "misc/random.h"
#include "osdep/io.h"
#include "osdep/terminal.h"
@@ -804,7 +805,7 @@ int mp_mkostemps(char *template, int suffixlen, int flags)
for (size_t fuckshit = 0; fuckshit < UINT32_MAX; fuckshit++) {
// Using a random value may make it require fewer iterations (even if
// not truly random; just a counter would be sufficient).
- size_t fuckmess = rand();
+ size_t fuckmess = mp_rand_next();
char crap[7] = "";
snprintf(crap, sizeof(crap), "%06zx", fuckmess);
memcpy(t, crap, 6);
diff --git a/osdep/timer.c b/osdep/timer.c
index c624b66e70..8a52823b0f 100644
--- a/osdep/timer.c
+++ b/osdep/timer.c
@@ -25,6 +25,7 @@
#include "common/common.h"
#include "common/msg.h"
+#include "misc/random.h"
#include "timer.h"
static uint64_t raw_time_offset;
@@ -33,7 +34,7 @@ static pthread_once_t timer_init_once = PTHREAD_ONCE_INIT;
static void do_timer_init(void)
{
mp_raw_time_init();
- srand(mp_raw_time_us());
+ mp_rand_seed(mp_raw_time_us());
raw_time_offset = mp_raw_time_us();
// Arbitrary additional offset to avoid confusing relative/absolute times.
// Also,we rule that the timer never returns 0 (so default-initialized
diff --git a/wscript_build.py b/wscript_build.py
index 1b3ffd8e7b..b389284317 100644
--- a/wscript_build.py
+++ b/wscript_build.py
@@ -335,6 +335,7 @@ def build(ctx):
( "misc/natural_sort.c" ),
( "misc/node.c" ),
( "misc/rendezvous.c" ),
+ ( "misc/random.c" ),
( "misc/thread_pool.c" ),
( "misc/thread_tools.c" ),