Skip to main content

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::fmt::{Debug, Formatter};
7use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
8use std::ops::{Index, IndexMut};
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`](std::collections::HashMap) using [`FastHasher`].
177#[expect(clippy::disallowed_types)]
178pub type FastMap<K, V> = std::collections::HashMap<K, V, BuildFastHasher>;
179/// [`HashSet`](std::collections::HashSet) using [`FastHasher`].
180#[expect(clippy::disallowed_types)]
181pub type FastSet<T> = std::collections::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/// A simple hash map which assigns each key an index in insertion order.
219///
220/// Keys and values are stored in a [`Vec`] in insertion order. A separate hash table using linear
221/// probing and [`FastHasher`] maps keys to their indexes. Keys cannot be removed.
222///
223/// The table is kept at most 25% full for performance. This can be faster than [`FastMap`] for
224/// small maps with up to ~1000 entries.
225///
226/// # Examples
227///
228/// ```
229/// # use utils::hash::IndexedMap;
230/// let mut map = IndexedMap::<&str, u32>::new();
231/// let index = map.intern("x");
232/// map[index] += 2;
233/// assert_eq!(map.try_insert("x"), Err(0));
234/// assert_eq!(map.try_insert_with("y", || 5), Ok(1));
235/// assert_eq!(map.into_values().collect::<Vec<_>>(), [2, 5]);
236/// ```
237#[derive(Clone)]
238pub struct IndexedMap<K, V> {
239    entries: Vec<(K, V)>,
240    table: Vec<u32>,
241}
242
243/// Hash set using [`IndexedMap`].
244///
245/// Keys are assigned indexes in insertion order, which can be used to intern them.
246///
247/// # Examples
248///
249/// ```
250/// # use utils::hash::IndexedSet;
251/// let mut set = IndexedSet::new();
252/// assert!(set.insert("b"));
253/// assert!(!set.insert("b"));
254/// assert_eq!(set.intern("a"), 1);
255/// assert_eq!(set.index_of(&"a"), Some(1));
256/// assert_eq!(set.index_of(&"c"), None);
257/// ```
258pub type IndexedSet<K> = IndexedMap<K, ()>;
259
260const EMPTY: u32 = u32::MAX;
261
262impl<K: Hash + Eq, V> IndexedMap<K, V> {
263    /// Creates an empty map.
264    #[inline]
265    #[must_use]
266    pub fn new() -> Self {
267        Self::with_capacity(0)
268    }
269
270    /// Creates an empty map with at least the specified capacity.
271    #[inline]
272    #[must_use]
273    pub fn with_capacity(capacity: usize) -> Self {
274        Self {
275            entries: Vec::with_capacity(capacity),
276            table: vec![EMPTY; (capacity * 4).next_power_of_two().max(64)],
277        }
278    }
279
280    /// Inserts the key if it is not present, creating the value using `f`.
281    ///
282    /// Returns [`Ok`] containing the new index, or [`Err`] containing the existing index.
283    #[inline(always)]
284    #[expect(clippy::cast_possible_truncation)]
285    pub fn try_insert_with(&mut self, key: K, f: impl FnOnce() -> V) -> Result<usize, usize> {
286        if (self.entries.len() + 1) * 4 > self.table.len() {
287            self.grow();
288        }
289        match self.find(&key) {
290            Ok(index) => Err(index),
291            Err(slot) => {
292                let index = self.entries.len();
293                self.table[slot] = index as u32;
294                self.entries.push((key, f()));
295                Ok(index)
296            }
297        }
298    }
299
300    /// Inserts the key if it is not present, using the default value.
301    ///
302    /// See [`try_insert_with`](Self::try_insert_with).
303    #[inline(always)]
304    pub fn try_insert(&mut self, key: K) -> Result<usize, usize>
305    where
306        V: Default,
307    {
308        self.try_insert_with(key, V::default)
309    }
310
311    /// Inserts the key if it is not present, returning whether it was inserted.
312    #[inline]
313    pub fn insert(&mut self, key: K) -> bool
314    where
315        V: Default,
316    {
317        self.try_insert(key).is_ok()
318    }
319
320    /// Returns the index of the key, inserting the key first if it is not present.
321    #[inline]
322    pub fn intern(&mut self, key: K) -> usize
323    where
324        V: Default,
325    {
326        let (Ok(index) | Err(index)) = self.try_insert(key);
327        index
328    }
329
330    /// Returns the index of the provided key if it is present.
331    #[inline]
332    pub fn index_of(&self, key: &K) -> Option<usize> {
333        self.find(key).ok()
334    }
335
336    /// Returns an iterator over the values, ordered by index.
337    #[inline]
338    pub fn into_values(self) -> impl Iterator<Item = V> {
339        self.entries.into_iter().map(|(_, v)| v)
340    }
341
342    /// Returns the number of keys in the map.
343    #[inline]
344    #[must_use]
345    pub fn len(&self) -> usize {
346        self.entries.len()
347    }
348
349    /// Returns whether the map is empty.
350    #[inline]
351    #[must_use]
352    pub fn is_empty(&self) -> bool {
353        self.entries.is_empty()
354    }
355
356    /// Clears the map in place.
357    #[inline]
358    pub fn clear(&mut self) {
359        if !self.entries.is_empty() {
360            self.entries.clear();
361            self.table.fill(EMPTY);
362        }
363    }
364
365    #[inline]
366    #[expect(clippy::cast_possible_truncation)]
367    fn find(&self, key: &K) -> Result<usize, usize> {
368        let mask = self.table.len() - 1;
369        let mut slot = BuildFastHasher::default().hash_one(key) as usize & mask;
370        loop {
371            match self.table[slot] {
372                EMPTY => return Err(slot),
373                index if self.entries[index as usize].0 == *key => return Ok(index as usize),
374                _ => slot = (slot + 1) & mask,
375            }
376        }
377    }
378
379    #[cold]
380    #[inline(never)]
381    #[expect(clippy::cast_possible_truncation)]
382    fn grow(&mut self) {
383        let len = self.table.len() * 2;
384        assert!(len / 4 < EMPTY as usize, "too many keys");
385        self.table = vec![EMPTY; len];
386        for (index, (key, _)) in self.entries.iter().enumerate() {
387            let mut slot = BuildFastHasher::default().hash_one(key) as usize & (len - 1);
388            while self.table[slot] != EMPTY {
389                slot = (slot + 1) & (len - 1);
390            }
391            self.table[slot] = index as u32;
392        }
393    }
394}
395
396impl<K: Hash + Eq, V> Default for IndexedMap<K, V> {
397    #[inline]
398    fn default() -> Self {
399        Self::new()
400    }
401}
402
403impl<K, V> Index<usize> for IndexedMap<K, V> {
404    type Output = V;
405
406    #[inline]
407    fn index(&self, index: usize) -> &V {
408        &self.entries[index].1
409    }
410}
411
412impl<K, V> IndexMut<usize> for IndexedMap<K, V> {
413    #[inline]
414    fn index_mut(&mut self, index: usize) -> &mut V {
415        &mut self.entries[index].1
416    }
417}
418
419impl<K: Debug, V: Debug> Debug for IndexedMap<K, V> {
420    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
421        f.debug_map()
422            .entries(self.entries.iter().map(|(k, v)| (k, v)))
423            .finish()
424    }
425}
426
427#[cfg(test)]
428mod tests {
429    use super::*;
430
431    fn hash_of(f: impl FnOnce(&mut FastHasher)) -> u64 {
432        let mut hasher = FastHasher::default();
433        f(&mut hasher);
434        hasher.finish()
435    }
436
437    #[test]
438    fn packs_small_writes() {
439        let a = hash_of(|h| {
440            h.write_u16(0x1234);
441            h.write_u16(0x5678);
442            h.write_u32(0x9abc_def0);
443        });
444        let b = hash_of(|h| h.write_u64(0x1234_5678_9abc_def0));
445        assert_eq!(a, b);
446    }
447
448    #[test]
449    fn packs_partial_writes_with_length() {
450        let a = hash_of(|h| {
451            h.write_u16(0x1234);
452            h.write_u16(0x5678);
453            h.write_u8(0x9a);
454        });
455        let b = hash_of(|h| h.write_u64(0x2800_0012_3456_789a));
456        assert_eq!(a, b);
457    }
458
459    #[test]
460    fn field_order_matters() {
461        let a = hash_of(|h| {
462            h.write_u32(1);
463            h.write_u32(2);
464        });
465        let packed_a = hash_of(|h| h.write_u64(0x0000_0001_0000_0002));
466        assert_eq!(a, packed_a);
467
468        let b = hash_of(|h| {
469            h.write_u32(2);
470            h.write_u32(1);
471        });
472        let packed_b = hash_of(|h| h.write_u64(0x0000_0002_0000_0001));
473        assert_eq!(b, packed_b);
474
475        assert_ne!(a, b);
476    }
477
478    #[test]
479    fn packs_full_word_then_tags_tail() {
480        let a = hash_of(|h| {
481            h.write_u32(1);
482            h.write_u32(2);
483            h.write_u32(3);
484        });
485        let b = hash_of(|h| {
486            h.write_u64(0x0000_0001_0000_0002);
487            h.write_u64(0x2000_0000_0000_0003);
488        });
489        assert_eq!(a, b);
490    }
491
492    #[test]
493    fn u64_write_order_matters() {
494        let a = hash_of(|h| {
495            h.write_u64(1);
496            h.write_u64(2);
497            h.write_u64(3);
498        });
499        let b = hash_of(|h| {
500            h.write_u64(3);
501            h.write_u64(2);
502            h.write_u64(1);
503        });
504        assert_ne!(a, b);
505    }
506
507    #[test]
508    fn zero_bytes_are_significant() {
509        let inputs: &[&[u8]] = &[
510            b"a",
511            b"ab",
512            b"ab\0",
513            b"a\0\0\0",
514            b"\0a",
515            b"\0a\0",
516            b"\0\0\0a",
517            b"\0\0\0\0\0\0\0\0a",
518            b"a\0\0\0\0\0\0\0\0",
519            b"\0",
520            b"\0\0",
521            b"\0\0\0",
522            b"\0\0\0\0",
523            b"\0\0\0\0\0\0\0\0",
524            b"\0\0\0\0\0\0\0\0\0",
525            b"\0\0\0\0\0\0\0\0\0\0",
526        ];
527        for (i, a) in inputs.iter().enumerate() {
528            for b in &inputs[i + 1..] {
529                assert_ne!(
530                    hash_of(|h| h.write(a)),
531                    hash_of(|h| h.write(b)),
532                    "{a:?} and {b:?} hashed the same",
533                );
534            }
535        }
536    }
537
538    #[test]
539    fn indexed_map_resizes() {
540        let mut map = IndexedMap::new();
541        for i in 0..1000u32 {
542            assert_eq!(map.try_insert_with(i * 3, || i * 5), Ok(i as usize));
543        }
544        assert_eq!(map.len(), 1000);
545        for i in 0..1000u32 {
546            let index = map.index_of(&(i * 3)).unwrap();
547            assert_eq!((index, map[index]), (i as usize, i * 5));
548        }
549
550        map.clear();
551        assert!(map.is_empty());
552        assert_eq!(map.index_of(&3), None);
553        assert_eq!(map.try_insert(6), Ok(0));
554    }
555}