Skip to main content

solverforge_core/
fast_hash.rs

1//! Deterministic fast hashing for engine-internal index keys.
2//!
3//! Index keys are minted by the engine itself (`RowHandle` slots, source
4//! indexes, descriptor ids, group coordinates); they are never adversarial
5//! input, so the DoS-resistant seeded default buys nothing on the event
6//! path and costs a full SipHash round per probe. The default also
7//! randomises bucket order per process, which an engine advertising a
8//! reproducible environment mode cannot want.
9//!
10//! Integer writes take a multiply-xor round; opaque keys such as `String`
11//! codes fall back to byte-wise FNV-1a.
12
13use std::collections::{HashMap, HashSet};
14use std::hash::{BuildHasherDefault, Hasher};
15
16/// A `HashMap` hashed with [`FastHasher`]: deterministic across runs, not DoS-resistant.
17pub type FastMap<K, V> = HashMap<K, V, BuildHasherDefault<FastHasher>>;
18/// A `HashSet` hashed with [`FastHasher`]: deterministic across runs, not DoS-resistant.
19pub type FastSet<T> = HashSet<T, BuildHasherDefault<FastHasher>>;
20
21/// Unseeded hasher for engine-minted keys: a multiply-xor round per integer
22/// write and FNV-1a over byte writes.
23///
24/// It is deterministic across processes and must not hash untrusted input.
25#[derive(Default)]
26pub struct FastHasher(u64);
27
28impl FastHasher {
29    #[inline]
30    fn mix(&mut self, value: u64) {
31        self.0 = (self.0 ^ value).wrapping_mul(0x9e37_79b9_7f4a_7c15);
32        self.0 ^= self.0 >> 29;
33    }
34}
35
36impl Hasher for FastHasher {
37    #[inline]
38    fn finish(&self) -> u64 {
39        self.0
40    }
41
42    #[inline]
43    fn write(&mut self, bytes: &[u8]) {
44        for &byte in bytes {
45            self.0 = (self.0 ^ u64::from(byte)).wrapping_mul(0x0000_0100_0000_01b3);
46        }
47    }
48
49    #[inline]
50    fn write_u8(&mut self, value: u8) {
51        self.mix(u64::from(value));
52    }
53
54    #[inline]
55    fn write_u16(&mut self, value: u16) {
56        self.mix(u64::from(value));
57    }
58
59    #[inline]
60    fn write_u32(&mut self, value: u32) {
61        self.mix(u64::from(value));
62    }
63
64    #[inline]
65    fn write_u64(&mut self, value: u64) {
66        self.mix(value);
67    }
68
69    #[inline]
70    fn write_usize(&mut self, value: usize) {
71        self.mix(value as u64);
72    }
73}
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78    use std::hash::Hash;
79
80    fn hash_of<T: Hash>(value: T) -> u64 {
81        let mut hasher = FastHasher::default();
82        value.hash(&mut hasher);
83        hasher.finish()
84    }
85
86    #[test]
87    fn hashes_integers_deterministically() {
88        assert_eq!(hash_of(7usize), hash_of(7usize));
89        assert_ne!(hash_of(7usize), hash_of(8usize));
90    }
91
92    #[test]
93    fn hashes_tuples_and_byte_keys() {
94        assert_ne!(hash_of((1usize, 2usize)), hash_of((2usize, 1usize)));
95        assert_ne!(hash_of("alpha"), hash_of("beta"));
96    }
97
98    #[test]
99    fn fast_maps_use_the_fast_hasher() {
100        let mut map = FastMap::<usize, usize>::default();
101        map.insert(1, 2);
102        assert_eq!(map.get(&1), Some(&2));
103        let mut set = FastSet::<usize>::default();
104        set.insert(3);
105        assert!(set.contains(&3));
106    }
107}