cranpose_ui_graphics/
fx_hash.rs

1use std::hash::{BuildHasherDefault, Hasher};
2
3/// Multiplier from the FxHash family: odd, so every `wrapping_mul` step is a
4/// bijection on `u64` and folding a word can never lose accumulator state.
5const FOLD: u64 = 0x517c_c1b7_2722_0a95;
6
7/// Rotation applied before each fold so that a word's bits reach every lane of
8/// the accumulator across successive words.
9const FOLD_ROTATE: u32 = 5;
10
11/// The bytes a write needs before [`FxHasher::write`] folds it in four lanes.
12/// Each fold waits on the multiply before it, so one chain takes a multiply's
13/// latency per word; four chains overlap their multiplies, and a recording's
14/// columns hash in about a quarter of the time. Below this, the lanes' own
15/// folds into the hash cost what they save.
16const LANE_BYTES: usize = 64;
17
18/// Starting offsets that set the lanes apart, so the same word in two lanes
19/// folds differently.
20const LANE_SEEDS: [u64; 3] = [
21    0x9e37_79b9_7f4a_7c15,
22    0xc2b2_ae3d_27d4_eb4f,
23    0x1656_67b1_9e37_79f9,
24];
25
26const FINALIZE_A: u64 = 0xbf58_476d_1ce4_e5b9;
27const FINALIZE_B: u64 = 0x94d0_49bb_1331_11eb;
28
29/// Non-cryptographic hasher for in-memory frame-to-frame change detection.
30///
31/// Every step of the fold — rotate, xor with the next word, multiply by an odd
32/// constant — is a bijection on `u64`, so equal-length inputs never collide
33/// structurally; only the unavoidable 64-bit pigeonhole remains. [`finish`]
34/// applies the SplitMix64 finalizer, itself a bijection, which adds no
35/// collisions and gives full avalanche so the result is safe to use directly as
36/// a `HashMap` key hash.
37///
38/// [`finish`]: Hasher::finish
39#[derive(Clone, Copy, Default)]
40pub struct FxHasher {
41    hash: u64,
42}
43
44/// [`std::hash::BuildHasher`] for [`FxHasher`], for `HashMap`/`HashSet` on the
45/// per-frame path.
46pub type FxBuildHasher = BuildHasherDefault<FxHasher>;
47
48impl FxHasher {
49    #[inline]
50    fn fold(&mut self, word: u64) {
51        self.hash = fold(self.hash, word);
52    }
53
54    /// Folds `blocks` into four lanes, word `i` of each block into lane `i`,
55    /// then the lanes into the hash in order. Every lane fold is a bijection,
56    /// so a change to any one word still changes the hash.
57    fn fold_blocks(&mut self, blocks: &[[u8; 32]]) {
58        let mut lanes = [
59            self.hash,
60            self.hash ^ LANE_SEEDS[0],
61            self.hash ^ LANE_SEEDS[1],
62            self.hash ^ LANE_SEEDS[2],
63        ];
64        for block in blocks {
65            for (lane, word) in lanes.iter_mut().zip(block.as_chunks::<8>().0) {
66                *lane = fold(*lane, u64::from_le_bytes(*word));
67            }
68        }
69        for lane in lanes {
70            self.fold(lane);
71        }
72    }
73}
74
75#[inline]
76fn fold(hash: u64, word: u64) -> u64 {
77    (hash.rotate_left(FOLD_ROTATE) ^ word).wrapping_mul(FOLD)
78}
79
80impl Hasher for FxHasher {
81    #[inline]
82    fn write(&mut self, bytes: &[u8]) {
83        let bytes = if bytes.len() >= LANE_BYTES {
84            let (blocks, rest) = bytes.as_chunks::<32>();
85            self.fold_blocks(blocks);
86            rest
87        } else {
88            bytes
89        };
90        let (chunks, tail) = bytes.as_chunks::<8>();
91        for chunk in chunks {
92            self.fold(u64::from_le_bytes(*chunk));
93        }
94        if !tail.is_empty() {
95            let mut word = [0u8; 8];
96            word[..tail.len()].copy_from_slice(tail);
97            self.fold(u64::from_le_bytes(word) ^ ((tail.len() as u64) << 56));
98        }
99    }
100
101    #[inline]
102    fn write_u8(&mut self, value: u8) {
103        self.fold(u64::from(value));
104    }
105
106    #[inline]
107    fn write_u16(&mut self, value: u16) {
108        self.fold(u64::from(value));
109    }
110
111    #[inline]
112    fn write_u32(&mut self, value: u32) {
113        self.fold(u64::from(value));
114    }
115
116    #[inline]
117    fn write_u64(&mut self, value: u64) {
118        self.fold(value);
119    }
120
121    #[inline]
122    fn write_u128(&mut self, value: u128) {
123        self.fold(value as u64);
124        self.fold((value >> 64) as u64);
125    }
126
127    #[inline]
128    fn write_usize(&mut self, value: usize) {
129        self.fold(value as u64);
130    }
131
132    #[inline]
133    fn finish(&self) -> u64 {
134        let mut hash = self.hash;
135        hash ^= hash >> 30;
136        hash = hash.wrapping_mul(FINALIZE_A);
137        hash ^= hash >> 27;
138        hash = hash.wrapping_mul(FINALIZE_B);
139        hash ^ (hash >> 31)
140    }
141}
142
143#[cfg(test)]
144#[path = "tests/fx_hash_tests.rs"]
145mod tests;
cranpose_ui_graphics/fx_hash.rs

cranpose_ui_graphics/
fx_hash.rs
