Merge pull request #5963 from Yawning/feature/chacha8rand

runtime: Use chacha8rand as the default RNG (BREAKING)

3 files changed, 272 insertions, 3 deletions

diff --git a/core/math/rand/rand.odin b/core/math/rand/rand.odin
index a9870b9f7..4ffcc595e 100644
--- a/core/math/rand/rand.odin
+++ b/core/math/rand/rand.odin
@@ -11,15 +11,50 @@ Generator :: runtime.Random_Generator
 Generator_Query_Info :: runtime.Random_Generator_Query_Info
 
 Default_Random_State :: runtime.Default_Random_State
+
+/*
+Returns an instance of the runtime pseudorandom generator.  If no
+initial state is provided, the PRNG will be lazily initialized with
+entropy from the system entropy source on first-use.
+
+The cryptographic security of the returned random number generator
+is directly dependent on the quality of the initialization entropy.
+Calling `reset`/`create` SHOULD be done with no seed/state, or
+32-bytes of high-quality entropy.
+
+WARNING:
+- The lazy initialization will panic if there is no system entropy
+  source available.
+- While the generator is cryptographically secure, developers SHOULD
+  prefer `crypto.random_generator()` for cryptographic use cases such
+  as key generation.
+
+Inputs:
+- state: Optional initial PRNG state.
+
+Returns:
+- A `Generator` instance.
+*/
 default_random_generator :: runtime.default_random_generator
 
 @(require_results)
-create :: proc(seed: u64) -> (state: Default_Random_State) {
+create_u64 :: proc(seed: u64) -> (state: Default_Random_State) {
 	seed := seed
 	runtime.default_random_generator_proc(&state, .Reset, ([^]byte)(&seed)[:size_of(seed)])
 	return
 }
 
+@(require_results)
+create_bytes :: proc(seed: []byte) -> (state: Default_Random_State) {
+	runtime.default_random_generator_proc(&state, .Reset, seed)
+	return
+}
+
+create :: proc {
+	create_u64,
+	create_bytes,
+}
+
 /*
 Reset the seed used by the context.random_generator.
 
@@ -39,10 +74,14 @@ Possible Output:
 
 	10
 */
-reset :: proc(seed: u64, gen := context.random_generator) {
-	runtime.random_generator_reset_u64(gen, seed)
+reset :: proc {
+	reset_u64,
+	reset_bytes,
 }
 
+reset_u64 :: proc(seed: u64, gen := context.random_generator) {
+	runtime.random_generator_reset_u64(gen, seed)
+}
 
 reset_bytes :: proc(bytes: []byte, gen := context.random_generator) {
 	runtime.random_generator_reset_bytes(gen, bytes)
diff --git a/core/math/rand/rand_pcg.odin b/core/math/rand/rand_pcg.odin
new file mode 100644
index 000000000..009e139be
--- /dev/null
+++ b/core/math/rand/rand_pcg.odin
@@ -0,0 +1,107 @@
+package rand
+
+import "base:intrinsics"
+import "base:runtime"
+
+/*
+The state for a PCG64 RXS-M-XS pseudorandom generator.
+*/
+PCG_Random_State :: struct {
+	state: u64,
+	inc:   u64,
+}
+
+pcg_random_generator_proc :: proc(data: rawptr, mode: runtime.Random_Generator_Mode, p: []byte) {
+	@(require_results)
+	read_u64 :: proc "contextless" (r: ^PCG_Random_State) -> u64 {
+		old_state := r.state
+		r.state = old_state * 6364136223846793005 + (r.inc|1)
+		xor_shifted := (((old_state >> 59) + 5) ~ old_state) * 12605985483714917081
+		rot := (old_state >> 59)
+		return (xor_shifted >> rot) | (xor_shifted << ((-rot) & 63))
+	}
+
+	@(thread_local)
+	global_rand_seed: PCG_Random_State
+
+	init :: proc "contextless" (r: ^PCG_Random_State, seed: u64) {
+		seed := seed
+		if seed == 0 {
+			seed = u64(intrinsics.read_cycle_counter())
+		}
+		r.state = 0
+		r.inc = (seed << 1) | 1
+		_ = read_u64(r)
+		r.state += seed
+		_ = read_u64(r)
+	}
+
+	r: ^PCG_Random_State = ---
+	if data == nil {
+		r = &global_rand_seed
+	} else {
+		r = cast(^PCG_Random_State)data
+	}
+
+	switch mode {
+	case .Read:
+		if r.state == 0 && r.inc == 0 {
+			init(r, 0)
+		}
+
+		switch len(p) {
+		case size_of(u64):
+			// Fast path for a 64-bit destination.
+			intrinsics.unaligned_store((^u64)(raw_data(p)), read_u64(r))
+		case:
+			// All other cases.
+			pos := i8(0)
+			val := u64(0)
+			for &v in p {
+				if pos == 0 {
+					val = read_u64(r)
+					pos = 8
+				}
+				v = byte(val)
+				val >>= 8
+				pos -= 1
+			}
+		}
+
+	case .Reset:
+		seed: u64
+		runtime.mem_copy_non_overlapping(&seed, raw_data(p), min(size_of(seed), len(p)))
+		init(r, seed)
+
+	case .Query_Info:
+		if len(p) != size_of(Generator_Query_Info) {
+			return
+		}
+		info := (^Generator_Query_Info)(raw_data(p))
+		info^ += {.Uniform, .Resettable}
+	}
+}
+
+/*
+Returns an instance of the PGC64 RXS-M-XS pseudorandom generator.  If no
+initial state is provided, the PRNG will be lazily initialized with the
+system timestamp counter on first-use.
+
+WARNING: This random number generator is NOT cryptographically secure,
+and is additionally known to be flawed.  It is only included for
+backward compatibility with historical releases of Odin.
+See: https://github.com/odin-lang/Odin/issues/5881
+
+Inputs:
+- state: Optional initial PRNG state.
+
+Returns:
+- A `Generator` instance.
+*/
+@(require_results)
+pcg_random_generator :: proc "contextless" (state: ^PCG_Random_State = nil) -> Generator {
+	return {
+		procedure = pcg_random_generator_proc,
+		data = state,
+	}
+}
diff --git a/core/math/rand/rand_xoshiro256.odin b/core/math/rand/rand_xoshiro256.odin
new file mode 100644
index 000000000..54dd02130
--- /dev/null
+++ b/core/math/rand/rand_xoshiro256.odin
@@ -0,0 +1,123 @@
+package rand
+
+import "base:intrinsics"
+import "base:runtime"
+
+import "core:math/bits"
+
+/*
+The state for a xoshiro256** pseudorandom generator.
+*/
+Xoshiro256_Random_State :: struct {
+	s: [4]u64,
+}
+
+xoshiro256_random_generator_proc :: proc(data: rawptr, mode: runtime.Random_Generator_Mode, p: []byte) {
+	@(require_results)
+	read_u64 :: proc "contextless" (r: ^Xoshiro256_Random_State) -> u64 {
+		// xoshiro256** output function and state transition
+
+		result := bits.rotate_left64(r.s[1] * 5, 7) * 9
+		t := r.s[1] << 17
+
+		r.s[2] = r.s[2] ~ r.s[0]
+		r.s[3] = r.s[3] ~ r.s[1]
+		r.s[1] = r.s[1] ~ r.s[2]
+		r.s[0] = r.s[0] ~ r.s[3]
+		r.s[2] = r.s[2] ~ t
+		r.s[3] = bits.rotate_left64(r.s[3], 45)
+
+		return result
+	}
+
+	@(thread_local)
+	global_rand_seed: Xoshiro256_Random_State
+
+	init :: proc "contextless" (r: ^Xoshiro256_Random_State, seed: u64) {
+		// splitmix64 to expand a 64-bit seed into 256 bits of state
+		sm64_next :: proc "contextless" (s: ^u64) -> u64 {
+			s^ += 0x9E3779B97F4A7C15
+			z := s^
+			z = (z ~ (z >> 30)) * 0xBF58476D1CE4E5B9
+			z = (z ~ (z >> 27)) * 0x94D049BB133111EB
+			return z ~ (z >> 31)
+		}
+
+		local_seed := seed
+		r.s[0] = sm64_next(&local_seed)
+		r.s[1] = sm64_next(&local_seed)
+		r.s[2] = sm64_next(&local_seed)
+		r.s[3] = sm64_next(&local_seed)
+		// Extremely unlikely all zero; ensure non-zero state
+		if (r.s[0] | r.s[1] | r.s[2] | r.s[3]) == 0 {
+			// force a minimal non-zero tweak
+			r.s[0] = 1
+		}
+	}
+
+	r: ^Xoshiro256_Random_State = ---
+	if data == nil {
+		r = &global_rand_seed
+	} else {
+		r = cast(^Xoshiro256_Random_State)data
+	}
+
+	switch mode {
+	case .Read:
+		if (r.s[0] | r.s[1] | r.s[2] | r.s[3]) == 0 {
+			init(r, u64(intrinsics.read_cycle_counter()))
+		}
+
+		switch len(p) {
+		case size_of(u64):
+			// Fast path for a 64-bit destination.
+			intrinsics.unaligned_store((^u64)(raw_data(p)), read_u64(r))
+		case:
+			// All other cases.
+			pos := i8(0)
+			val := u64(0)
+			for &v in p {
+				if pos == 0 {
+					val = read_u64(r)
+					pos = 8
+				}
+				v = byte(val)
+				val >>= 8
+				pos -= 1
+			}
+		}
+
+	case .Reset:
+		seed: u64 = 0
+		runtime.mem_copy_non_overlapping(&seed, raw_data(p), min(size_of(seed), len(p)))
+		init(r, seed)
+
+	case .Query_Info:
+		if len(p) != size_of(Generator_Query_Info) {
+			return
+		}
+		info := (^Generator_Query_Info)(raw_data(p))
+		info^ += {.Uniform, .Resettable}
+	}
+}
+
+/*
+Returns an instance of the xoshiro256** pseudorandom generator.  If no
+initial state is provided, the PRNG will be lazily initialized with the
+system timestamp counter on first-use.
+
+WARNING: This random number generator is NOT cryptographically secure.
+
+Inputs:
+- state: Optional initial PRNG state.
+
+Returns:
+- A `Generator` instance.
+*/
+@(require_results)
+xoshiro256_random_generator :: proc "contextless" (state: ^Xoshiro256_Random_State = nil) -> Generator {
+	return {
+		procedure = xoshiro256_random_generator_proc,
+		data = state,
+	}
+}