[PATCH 1/4] lib: random: implement Xorshift* RNG

[Ahmad Fatoum]

Xorshift is simpler, faster and better than the LCG we are currently
using. Add it in preparation alongside the LCG until consumers are
migrated.

Signed-off-by: Ahmad Fatoum <a.fatoum at pengutronix.de>
---
 include/stdlib.h | 15 ++++++++
 lib/random.c     | 92 ++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 107 insertions(+)

diff --git a/include/stdlib.h b/include/stdlib.h
index 20bdc0491e3c..12a81cfc31a3 100644
--- a/include/stdlib.h
+++ b/include/stdlib.h
@@ -18,10 +18,25 @@ struct hwrng;
 
 /* fill a buffer with pseudo-random data */
 #if IN_PROPER
+void randbuf_r(u64 *x, void *buf, size_t len);
+void srand_xor(u64 entropy);
+void get_noncrypto_bytes(void *buf, size_t len);
 void get_random_bytes(void *buf, int len);
 int get_crypto_bytes(void *buf, int len);
 int hwrng_get_crypto_bytes(struct hwrng *rng, void *buf, int len);
 #else
+static inline void randbuf_r(u64 *x, void *buf, size_t len)
+{
+	BUG();
+}
+static inline void srand_xor(u64 entropy)
+{
+	BUG();
+}
+static inline void get_noncrypto_bytes(void *buf, size_t len)
+{
+	BUG();
+}
 static inline void get_random_bytes(void *buf, int len)
 {
 	BUG();
diff --git a/lib/random.c b/lib/random.c
index e83935d0e17c..fc4ecdfd3a1d 100644
--- a/lib/random.c
+++ b/lib/random.c
@@ -1,4 +1,15 @@
 // SPDX-License-Identifier: GPL-2.0-only
+/*
+ * The barebox random number generator provides mainly two APIs:
+ *
+ *   - get_noncrypto_bytes: Xorshift*
+ *     - https://en.wikipedia.org/wiki/Xorshift#xorshift*)
+ *     - https://forum.pjrc.com/index.php?threads/teensy-4-1-random-number-generator.61125/#post-243895
+ *
+ *   - get_crypto_bytes: Randomness directly from a HWRNG.
+ *     PRNG fallback only possible with debugging option
+ *     CONFIG_ALLOW_PRNG_FALLBACK set, which will emit a warning at runtime.
+ */
 
 #include <common.h>
 #include <stdlib.h>
@@ -21,6 +32,87 @@ void srand(unsigned int seed)
 	random_seed = seed;
 }
 
+static u64 prng_state = 1;
+
+/**
+ * rand_r - return next pseudo-random number depending only on input
+ *
+ * @x: RNG state
+ *
+ * This function runs the Xorshift* algorithm on the state input,
+ * updates the state and returns the next number in the PRNG
+ * sequence.
+ *
+ * Return: a 32 bit pseudo-random number
+ */
+static u32 rand_r(u64 *x)
+{
+	*x ^= *x >> 12;
+	*x ^= *x << 25;
+	*x ^= *x >> 27;
+
+	/*
+	 * Xorshift* fails only the MatrixRank test of BigCrush, however if the
+	 * generator is modified to return only the high 32 bits, then it passes
+	 * BigCrush with zero failures
+	 */
+	return (*x * 0x2545F4914F6CDD1DULL) >> 32;
+}
+
+/**
+ * randbuf_r - fills pseudo-random numbers into buffer depending only on input
+ *
+ * @x:   RNG state
+ * @buf: buffer to fill
+ * @len: size of buffer
+ *
+ * This function runs the Xorshift* algorithm on the state input,
+ * updates the state and fills the buffer with pseudo-random numbers.
+ *
+ * Only use this when you are using a fixed seed and the sequence
+ * should be reproducible (e.g. for NAND test).
+ */
+void randbuf_r(u64 *x, void *buf, size_t len)
+{
+	for (size_t i = 0; i < len; i += 4) {
+		u32 val = rand_r(x);
+		memcpy(buf + i, &val, min_t(size_t, 4, len - i));
+	}
+}
+
+/**
+ * srand_xor - Xor a 64-bit into the existing RNG state
+ *
+ * @entropy: additional 64-bit of entropy
+ *
+ * This function mixes 64-bit of entropy into the exising
+ * state by means of an Xor operation.
+ *
+ * Only use for independent entropy sources.
+ */
+void srand_xor(u64 entropy)
+{
+	prng_state ^= entropy;
+	/* Ensure prng_state is never zero */
+	prng_state += !prng_state;
+	rand_r(&prng_state);
+}
+
+/**
+ * get_noncrypto_bytes - get pseudo random numbers.
+ *
+ * @buf: buffer to fill
+ * @len: length of buffer
+ *
+ * This interface can be good enough to generate MAC address
+ * or use for NAND test. Use get_crypto_bytes for cryptographic
+ * applications.
+ */
+void get_noncrypto_bytes(void *buf, size_t len)
+{
+	randbuf_r(&prng_state, buf, len);
+}
+
 /**
  * get_random_bytes - get pseudo random numbers.
  * This interface can be good enough to generate MAC address
-- 
2.39.5