brepkit_math/
det_hash.rs

1//! Deterministic hashing primitives.
2//!
3//! The standard-library `HashMap`/`HashSet` seed their hasher from a
4//! process-global source, so iteration order — and therefore any algorithm
5//! whose output depends on the order it visits map entries — varies between
6//! runs (and even between successive map instances within one process, since
7//! the seed counter advances per instance). For geometry kernels this surfaces
8//! as nondeterministic mesh welding and triangulation: the same input can
9//! produce different vertex merges and face counts run-to-run.
10//!
11//! [`DetHashMap`] / [`DetHashSet`] use a fixed-seed FNV-1a hasher so iteration
12//! order is fully reproducible for a given set of keys. Use them anywhere map
13//! iteration order feeds geometry construction (vertex welds, triangulation,
14//! shell assembly).
15//!
16//! # Security
17//!
18//! This is a deterministic, fixed-seed FNV-1a hasher. It is **not**
19//! DoS-resistant: an adversary who controls the keys can trivially force
20//! collisions. Use it only for internal geometry processing where keys are
21//! derived from trusted topology, never for attacker-controlled input.
22
23use std::hash::{BuildHasher, Hasher};
24
25const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
26const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
27
28/// Fixed-seed FNV-1a hasher. Deterministic across processes and instances.
29///
30/// Not DoS-resistant — see the [module docs](self#security). For internal
31/// geometry processing only.
32#[derive(Clone)]
33pub struct DetHasher(u64);
34
35impl DetHasher {
36    /// Create a hasher seeded with the FNV-1a offset basis.
37    #[must_use]
38    pub const fn new() -> Self {
39        Self(FNV_OFFSET)
40    }
41}
42
43impl Default for DetHasher {
44    fn default() -> Self {
45        Self::new()
46    }
47}
48
49impl Hasher for DetHasher {
50    fn finish(&self) -> u64 {
51        self.0
52    }
53
54    fn write(&mut self, bytes: &[u8]) {
55        let mut h = self.0;
56        for &b in bytes {
57            h ^= u64::from(b);
58            h = h.wrapping_mul(FNV_PRIME);
59        }
60        self.0 = h;
61    }
62}
63
64/// `BuildHasher` for [`DetHasher`], seeding each hasher at the FNV-1a offset.
65#[derive(Default, Clone)]
66pub struct DetState;
67
68impl BuildHasher for DetState {
69    type Hasher = DetHasher;
70
71    fn build_hasher(&self) -> Self::Hasher {
72        DetHasher::new()
73    }
74}
75
76/// A `HashMap` with deterministic, reproducible iteration order.
77pub type DetHashMap<K, V> = std::collections::HashMap<K, V, DetState>;
78
79/// A `HashSet` with deterministic, reproducible iteration order.
80pub type DetHashSet<K> = std::collections::HashSet<K, DetState>;
81
82#[cfg(test)]
83mod tests {
84    #![allow(clippy::unwrap_used, clippy::expect_used)]
85    use super::*;
86
87    fn hash_writes(writes: &[&[u8]]) -> u64 {
88        let mut h = DetHasher::new();
89        for w in writes {
90            h.write(w);
91        }
92        h.finish()
93    }
94
95    #[test]
96    fn empty_hash_is_offset_basis() {
97        assert_eq!(DetHasher::new().finish(), FNV_OFFSET);
98    }
99
100    #[test]
101    fn distinct_sequences_differ() {
102        assert_ne!(hash_writes(&[b"abc"]), hash_writes(&[b"abd"]));
103    }
104
105    #[test]
106    fn write_is_order_sensitive() {
107        assert_ne!(hash_writes(&[b"ab", b"cd"]), hash_writes(&[b"cd", b"ab"]),);
108    }
109
110    #[test]
111    fn zero_state_does_not_restart() {
112        // A running state that reaches exactly zero must keep folding in
113        // subsequent bytes rather than silently reverting to the offset
114        // basis. Find a single byte that drives the state to 0, then verify
115        // that appending more bytes keeps the two distinct streams distinct.
116        let target = (0u16..=u16::from(u8::MAX)).map(|b| b as u8).find(|&b| {
117            let mut h = DetHasher::new();
118            h.write(&[b]);
119            h.finish() == 0
120        });
121        if let Some(zeroing) = target {
122            let mut a = DetHasher::new();
123            a.write(&[zeroing]);
124            a.write(&[0x01]);
125
126            // A hasher that began life at zero would, under the old buggy
127            // logic, hash [0x01] identically. Build that comparison stream.
128            let mut b = DetHasher::new();
129            b.write(&[0x01]);
130            assert_ne!(a.finish(), b.finish());
131        }
132
133        // Regardless of whether a zeroing byte exists for this FNV constant,
134        // assert the invariant that distinct streams stay distinct even when
135        // one of them is the empty (offset-basis) stream.
136        assert_ne!(hash_writes(&[]), hash_writes(&[b"x"]));
137    }
138}
brepkit_math/det_hash.rs

brepkit_math/
det_hash.rs
