utils/
hash.rs

1//! Hashing helpers.
2
3// #[inline(always)] is required to ensure hashing is branchless for fixed-sized types.
4#![allow(clippy::inline_always)]
5
6#[expect(clippy::disallowed_types)]
7use std::collections::{HashMap, HashSet};
8use std::hash::{BuildHasherDefault, Hasher};
9
10// Reused wyhash secret, used as a non-zero initial state.
11const SEED: u64 = 0xa076_1d64_78bd_642f;
12// Reused wyhash secret, used for the fold multiply.
13const MUL: u64 = 0xe703_7ed1_a0b4_28db;
14
15/// Faster non-cryptographic hasher for small integer keys.
16///
17/// Intended to replace and outperform the default `SipHash` hasher for small keys used in puzzles.
18/// It should not be used in cryptographic or sensitive contexts and is vulnerable to `HashDoS`
19/// attacks.
20///
21/// Integer writes smaller than 64 bits are packed into a pending `u64`, so a key such as
22/// `(u32, u16, u16)` hashes like the manually packed value `(a << 32) | (b << 16) | c`.
23///
24/// The mixing step is inspired by [`wyhash`](https://github.com/wangyi-fudan/wyhash). It uses XOR
25/// to mix the current state and value, then does a 128bit multiplication with a large constant,
26/// before XOR-ing the high and low 64bit halves.
27///
28/// The branches should be optimized out for fixed-sized types in release builds.
29/// Example x86 assembly for [`u64`]:
30///
31/// ```text
32/// movabsq $SEED,%rax
33/// xorq    %rdi,%rax
34/// movabsq $MUL,%rcx
35/// mulq    %rcx
36/// xorq    %rdx,%rax
37/// retq
38/// ```
39///
40/// Example x86 assembly for `(u32, u16, u16)`, showing bit packing followed by the same fold:
41///
42/// ```text
43/// shlq    $32,%rdi
44/// shll    $16,%esi
45/// leaq    (%rsi,%rdi),%rax
46/// movzwl  %dx,%ecx
47/// orq     %rax,%rcx
48/// movabsq $SEED,%rax
49/// xorq    %rcx,%rax
50/// movabsq $MUL,%rcx
51/// mulq    %rcx
52/// xorq    %rdx,%rax
53/// retq
54/// ```
55#[derive(Clone, Debug)]
56pub struct FastHasher {
57    state: u64,
58    pending: u64,
59    bits: u32,
60}
61
62impl Default for FastHasher {
63    #[inline(always)]
64    fn default() -> Self {
65        FastHasher {
66            state: SEED,
67            pending: 0,
68            bits: 0,
69        }
70    }
71}
72
73impl FastHasher {
74    #[inline]
75    fn fold(state: u64, value: u64) -> u64 {
76        let (lo, hi) = (state ^ value).carrying_mul(MUL, 0);
77        lo ^ hi
78    }
79
80    #[inline(always)]
81    fn write_bits(&mut self, value: u64, bits: u32) {
82        if self.bits + bits > 64 {
83            self.state = Self::fold(self.state, self.pending);
84            self.pending = 0;
85            self.bits = 0;
86        }
87
88        self.pending = (self.pending << bits) | value;
89        self.bits += bits;
90    }
91}
92
93impl Hasher for FastHasher {
94    #[inline(always)]
95    fn finish(&self) -> u64 {
96        if self.bits > 0 {
97            // Include the pending bit count if less than 64 bits so leading zeros hash differently.
98            Self::fold(self.state, self.pending ^ (u64::from(self.bits & 63) << 56))
99        } else {
100            self.state
101        }
102    }
103
104    #[inline]
105    fn write(&mut self, mut bytes: &[u8]) {
106        while let Some((chunk, rest)) = bytes.split_first_chunk() {
107            self.write_u64(u64::from_ne_bytes(*chunk));
108            bytes = rest;
109        }
110
111        if let Some((chunk, rest)) = bytes.split_first_chunk() {
112            self.write_u32(u32::from_ne_bytes(*chunk));
113            bytes = rest;
114        }
115
116        if let Some((chunk, rest)) = bytes.split_first_chunk() {
117            self.write_u16(u16::from_ne_bytes(*chunk));
118            bytes = rest;
119        }
120
121        if let Some(&byte) = bytes.first() {
122            self.write_u8(byte);
123        }
124    }
125
126    #[inline(always)]
127    fn write_u8(&mut self, n: u8) {
128        self.write_bits(u64::from(n), 8);
129    }
130
131    #[inline(always)]
132    fn write_u16(&mut self, n: u16) {
133        self.write_bits(u64::from(n), 16);
134    }
135
136    #[inline(always)]
137    fn write_u32(&mut self, n: u32) {
138        self.write_bits(u64::from(n), 32);
139    }
140
141    #[inline(always)]
142    fn write_u64(&mut self, n: u64) {
143        self.state = Self::fold(self.state, n);
144    }
145
146    #[inline(always)]
147    #[expect(clippy::cast_possible_truncation)]
148    fn write_u128(&mut self, n: u128) {
149        self.write_u64(n as u64);
150        self.write_u64((n >> 64) as u64);
151    }
152
153    #[inline(always)]
154    #[cfg(target_pointer_width = "16")]
155    #[expect(clippy::cast_possible_truncation)]
156    fn write_usize(&mut self, n: usize) {
157        self.write_u16(n as u16);
158    }
159
160    #[inline(always)]
161    #[cfg(target_pointer_width = "32")]
162    #[expect(clippy::cast_possible_truncation)]
163    fn write_usize(&mut self, n: usize) {
164        self.write_u32(n as u32);
165    }
166
167    #[inline(always)]
168    #[cfg(target_pointer_width = "64")]
169    fn write_usize(&mut self, n: usize) {
170        self.write_u64(n as u64);
171    }
172}
173
174/// [`BuildHasherDefault`] using [`FastHasher`].
175pub type BuildFastHasher = BuildHasherDefault<FastHasher>;
176/// [`HashMap`] using [`FastHasher`].
177#[expect(clippy::disallowed_types)]
178pub type FastMap<K, V> = HashMap<K, V, BuildFastHasher>;
179/// [`HashSet`] using [`FastHasher`].
180#[expect(clippy::disallowed_types)]
181pub type FastSet<T> = HashSet<T, BuildFastHasher>;
182
183/// Helper trait providing `new` and `with_capacity` functions for [`FastMap`] and [`FastSet`].
184pub trait FastCollectionBuilder {
185    /// Creates an empty collection.
186    fn new() -> Self;
187
188    /// Creates an empty collection with at least the specified capacity.
189    fn with_capacity(capacity: usize) -> Self;
190}
191
192#[expect(clippy::implicit_hasher)]
193impl<K, V> FastCollectionBuilder for FastMap<K, V> {
194    #[inline]
195    fn new() -> Self {
196        Self::with_hasher(BuildFastHasher::default())
197    }
198
199    #[inline]
200    fn with_capacity(capacity: usize) -> Self {
201        Self::with_capacity_and_hasher(capacity, BuildFastHasher::default())
202    }
203}
204
205#[expect(clippy::implicit_hasher)]
206impl<T> FastCollectionBuilder for FastSet<T> {
207    #[inline]
208    fn new() -> Self {
209        Self::with_hasher(BuildFastHasher::default())
210    }
211
212    #[inline]
213    fn with_capacity(capacity: usize) -> Self {
214        Self::with_capacity_and_hasher(capacity, BuildFastHasher::default())
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    use super::*;
221
222    fn hash_of(f: impl FnOnce(&mut FastHasher)) -> u64 {
223        let mut hasher = FastHasher::default();
224        f(&mut hasher);
225        hasher.finish()
226    }
227
228    #[test]
229    fn packs_small_writes() {
230        let a = hash_of(|h| {
231            h.write_u16(0x1234);
232            h.write_u16(0x5678);
233            h.write_u32(0x9abc_def0);
234        });
235        let b = hash_of(|h| h.write_u64(0x1234_5678_9abc_def0));
236        assert_eq!(a, b);
237    }
238
239    #[test]
240    fn packs_partial_writes_with_length() {
241        let a = hash_of(|h| {
242            h.write_u16(0x1234);
243            h.write_u16(0x5678);
244            h.write_u8(0x9a);
245        });
246        let b = hash_of(|h| h.write_u64(0x2800_0012_3456_789a));
247        assert_eq!(a, b);
248    }
249
250    #[test]
251    fn field_order_matters() {
252        let a = hash_of(|h| {
253            h.write_u32(1);
254            h.write_u32(2);
255        });
256        let packed_a = hash_of(|h| h.write_u64(0x0000_0001_0000_0002));
257        assert_eq!(a, packed_a);
258
259        let b = hash_of(|h| {
260            h.write_u32(2);
261            h.write_u32(1);
262        });
263        let packed_b = hash_of(|h| h.write_u64(0x0000_0002_0000_0001));
264        assert_eq!(b, packed_b);
265
266        assert_ne!(a, b);
267    }
268
269    #[test]
270    fn packs_full_word_then_tags_tail() {
271        let a = hash_of(|h| {
272            h.write_u32(1);
273            h.write_u32(2);
274            h.write_u32(3);
275        });
276        let b = hash_of(|h| {
277            h.write_u64(0x0000_0001_0000_0002);
278            h.write_u64(0x2000_0000_0000_0003);
279        });
280        assert_eq!(a, b);
281    }
282
283    #[test]
284    fn u64_write_order_matters() {
285        let a = hash_of(|h| {
286            h.write_u64(1);
287            h.write_u64(2);
288            h.write_u64(3);
289        });
290        let b = hash_of(|h| {
291            h.write_u64(3);
292            h.write_u64(2);
293            h.write_u64(1);
294        });
295        assert_ne!(a, b);
296    }
297
298    #[test]
299    fn zero_bytes_are_significant() {
300        let inputs: &[&[u8]] = &[
301            b"a",
302            b"ab",
303            b"ab\0",
304            b"a\0\0\0",
305            b"\0a",
306            b"\0a\0",
307            b"\0\0\0a",
308            b"\0\0\0\0\0\0\0\0a",
309            b"a\0\0\0\0\0\0\0\0",
310            b"\0",
311            b"\0\0",
312            b"\0\0\0",
313            b"\0\0\0\0",
314            b"\0\0\0\0\0\0\0\0",
315            b"\0\0\0\0\0\0\0\0\0",
316            b"\0\0\0\0\0\0\0\0\0\0",
317        ];
318        for (i, a) in inputs.iter().enumerate() {
319            for b in &inputs[i + 1..] {
320                assert_ne!(
321                    hash_of(|h| h.write(a)),
322                    hash_of(|h| h.write(b)),
323                    "{a:?} and {b:?} hashed the same",
324                );
325            }
326        }
327    }
328}
utils/hash.rs

utils/
hash.rs
