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.

2 files changed, 116 insertions, 0 deletions

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);