1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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));
}
}
|
