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

utils/
hash.rs
