Skip to main content

clairlune_scene/
hash.rs

1//! Stable hashing.
2//!
3//! RNG streams, noise lattices and recipe hashes depend on these functions, so
4//! their output is part of the on-disk format and must never change. Never use
5//! `std::hash::DefaultHasher` for anything that affects output: its algorithm is
6//! unspecified and may change between Rust releases.
7
8const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
9const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
10
11/// SplitMix64 finaliser. A bijective, well-mixed 64-bit permutation.
12#[inline]
13pub const fn splitmix64(x: u64) -> u64 {
14    let mut z = x.wrapping_add(0x9E37_79B9_7F4A_7C15);
15    z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
16    z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
17    z ^ (z >> 31)
18}
19
20/// FNV-1a over bytes, finished with SplitMix64 for avalanche.
21#[derive(Clone, Debug)]
22pub struct StableHasher {
23    state: u64,
24}
25
26impl Default for StableHasher {
27    fn default() -> Self {
28        Self::new()
29    }
30}
31
32impl StableHasher {
33    pub const fn new() -> Self {
34        Self { state: FNV_OFFSET }
35    }
36
37    pub fn write_bytes(&mut self, bytes: &[u8]) {
38        for &b in bytes {
39            self.state ^= u64::from(b);
40            self.state = self.state.wrapping_mul(FNV_PRIME);
41        }
42    }
43
44    pub fn write_u64(&mut self, v: u64) {
45        self.write_bytes(&v.to_le_bytes());
46    }
47
48    /// Length-prefixed, so `("ab", "c")` and `("a", "bc")` hash differently.
49    pub fn write_str(&mut self, s: &str) {
50        self.write_u64(s.len() as u64);
51        self.write_bytes(s.as_bytes());
52    }
53
54    pub fn finish(&self) -> u64 {
55        splitmix64(self.state)
56    }
57}
58
59/// `hash(seed, label)`: derives a sub-seed, e.g. one RNG stream per subsystem.
60pub fn hash_label(seed: u64, label: &str) -> u64 {
61    let mut h = StableHasher::new();
62    h.write_u64(seed);
63    h.write_str(label);
64    h.finish()
65}
66
67/// Hash of a byte string.
68pub fn hash_bytes(bytes: &[u8]) -> u64 {
69    let mut h = StableHasher::new();
70    h.write_bytes(bytes);
71    h.finish()
72}
73
74/// Fast lattice hash for noise and per-cell jitter.
75#[inline]
76pub fn hash3(seed: u64, a: i64, b: i64) -> u64 {
77    let ka = (a as u64).wrapping_mul(0x9E37_79B9_7F4A_7C15);
78    let kb = (b as u64)
79        .wrapping_mul(0xC2B2_AE3D_27D4_EB4F)
80        .rotate_left(31);
81    splitmix64(seed ^ splitmix64(ka ^ kb))
82}
83
84/// Maps a hash to a float in `[0, 1)` using its top 53 bits. Exact on every platform.
85#[inline]
86pub fn unit_from_hash(h: u64) -> f64 {
87    (h >> 11) as f64 * (1.0 / 9_007_199_254_740_992.0)
88}
89
90#[cfg(test)]
91mod tests {
92    use super::*;
93
94    #[test]
95    fn known_values_never_change() {
96        // Pinned outputs. If one of these fails, every recipe and image changes.
97        assert_eq!(splitmix64(0), 0xE220_A839_7B1D_CDAF);
98        assert_eq!(hash_label(7, "terrain"), hash_label(7, "terrain"));
99        assert_ne!(hash_label(7, "terrain"), hash_label(7, "props"));
100        let mut a = StableHasher::new();
101        a.write_str("ab");
102        a.write_str("c");
103        let mut b = StableHasher::new();
104        b.write_str("a");
105        b.write_str("bc");
106        assert_ne!(a.finish(), b.finish());
107    }
108
109    #[test]
110    fn unit_range() {
111        assert_eq!(unit_from_hash(0), 0.0);
112        assert!(unit_from_hash(u64::MAX) < 1.0);
113    }
114}