1 files changed, 93 insertions, 0 deletions
diff --git a/src/seed.rs b/src/seed.rs
new file mode 100644
index 0000000..b7491e7
--- /dev/null
+++ b/src/seed.rs
@@ -0,0 +1,93 @@
+//! Stable, hierarchical seeds.
+//!
+//! The universe is a pure function of one `u64`. Each thing derives its seed
+//! from its parent's plus a label and an index:
+//!
+//! ```text
+//! let system = seed::derive(universe, "system", 42);
+//! let wreck  = seed::derive(system, "derelict", 3);
+//! ```
+//!
+//! so any one thing can be regenerated without generating everything before
+//! it, and a save file only needs the root seed plus what the player changed.
+//!
+//! Everything here must give the same answer forever: a change silently
+//! reshuffles every universe. That's why this doesn't use std's
+//! `DefaultHasher` (allowed to change between Rust releases) or rand's
+//! `seed_from_u64` (allowed to change between rand releases), and why the
+//! tests pin exact outputs.
+
+use rand::SeedableRng;
+use rand_chacha::ChaCha8Rng;
+
+/// The RNG for all procedural generation. ChaCha's output is specified and
+/// rand_chacha promises not to change it, unlike rand's `StdRng`.
+pub type Rng = ChaCha8Rng;
+
+/// SplitMix64's finalizer: scrambles every input bit into every output bit.
+const fn mix(mut z: u64) -> u64 {
+    z = (z ^ (z >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
+    z = (z ^ (z >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
+    z ^ (z >> 31)
+}
+
+/// FNV-1a: a tiny hash for turning labels into numbers.
+const fn fnv1a(bytes: &[u8]) -> u64 {
+    let mut hash: u64 = 0xcbf2_9ce4_8422_2325;
+    let mut i = 0;
+    while i < bytes.len() {
+        hash ^= bytes[i] as u64;
+        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
+        i += 1;
+    }
+    hash
+}
+
+/// The seed of the `index`th `label` inside `parent`.
+pub const fn derive(parent: u64, label: &str, index: u64) -> u64 {
+    mix(mix(parent ^ fnv1a(label.as_bytes())).wrapping_add(mix(index ^ 0x9e37_79b9_7f4a_7c15)))
+}
+
+/// An RNG for generating whatever `seed` identifies.
+pub fn rng(seed: u64) -> Rng {
+    let mut bytes = [0u8; 32];
+    let mut state = seed;
+    for chunk in bytes.as_chunks_mut::<8>().0 {
+        state = state.wrapping_add(0x9e37_79b9_7f4a_7c15);
+        *chunk = mix(state).to_le_bytes();
+    }
+    Rng::from_seed(bytes)
+}
+
+/// A fresh universe seed for when the player doesn't pick one.
+pub fn from_clock() -> u64 {
+    let nanos = std::time::SystemTime::now()
+        .duration_since(std::time::UNIX_EPOCH)
+        .map_or(0, |d| d.as_nanos() as u64);
+    // Keep seeds short enough to read aloud and retype.
+    mix(nanos ^ u64::from(std::process::id())) % 1_000_000_000
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+    use rand::Rng as _;
+
+    /// If this fails, every existing universe just changed. Only update the
+    /// numbers if you mean to break old seeds and saves.
+    #[test]
+    fn outputs_never_change() {
+        assert_eq!(derive(0, "system", 0), PINNED_DERIVE);
+        assert_eq!(rng(0).next_u64(), PINNED_RNG);
+    }
+    const PINNED_DERIVE: u64 = 11_894_545_496_673_509_984;
+    const PINNED_RNG: u64 = 13_804_888_775_535_289_832;
+
+    #[test]
+    fn labels_and_indices_give_different_seeds() {
+        let a = derive(7, "system", 0);
+        assert_ne!(a, derive(7, "system", 1));
+        assert_ne!(a, derive(7, "derelict", 0));
+        assert_ne!(a, derive(8, "system", 0));
+    }
+}