pptxboss_core/
hash.rs

1//! A fast, non-cryptographic hasher for the short keys the reader hashes in
2//! bulk: ZIP item names, part names, relationship ids and XML names. The
3//! standard library's SipHash is DoS-resistant and far slower than needed
4//! for in-process maps over already-parsed input.
5//!
6//! The construction is FxHash: fold each machine word of the key into an
7//! accumulator with a rotate, an xor and a multiply by a fixed odd
8//! constant. It is unseeded, so iteration order is stable across runs.
9
10use std::hash::{BuildHasherDefault, Hasher};
11
12/// A [`std::collections::HashMap`] using [`FxHasher`].
13pub type FastMap<K, V> = std::collections::HashMap<K, V, BuildHasherDefault<FxHasher>>;
14
15/// A [`std::collections::HashSet`] using [`FxHasher`].
16pub type FastSet<K> = std::collections::HashSet<K, BuildHasherDefault<FxHasher>>;
17
18const SEED: u64 = 0x51_7c_c1_b7_27_22_0a_95;
19const ROTATE: u32 = 5;
20
21#[derive(Default)]
22pub struct FxHasher {
23    hash: u64,
24}
25
26impl FxHasher {
27    #[inline]
28    fn add(&mut self, word: u64) {
29        self.hash = (self.hash.rotate_left(ROTATE) ^ word).wrapping_mul(SEED);
30    }
31}
32
33impl Hasher for FxHasher {
34    #[inline]
35    fn write(&mut self, mut bytes: &[u8]) {
36        while bytes.len() >= 8 {
37            let mut chunk = [0u8; 8];
38            chunk.copy_from_slice(&bytes[..8]);
39            self.add(u64::from_le_bytes(chunk));
40            bytes = &bytes[8..];
41        }
42        if bytes.len() >= 4 {
43            let mut chunk = [0u8; 4];
44            chunk.copy_from_slice(&bytes[..4]);
45            self.add(u64::from(u32::from_le_bytes(chunk)));
46            bytes = &bytes[4..];
47        }
48        for &byte in bytes {
49            self.add(u64::from(byte));
50        }
51    }
52
53    #[inline]
54    fn write_u8(&mut self, value: u8) {
55        self.add(u64::from(value));
56    }
57
58    #[inline]
59    fn write_u16(&mut self, value: u16) {
60        self.add(u64::from(value));
61    }
62
63    #[inline]
64    fn write_u32(&mut self, value: u32) {
65        self.add(u64::from(value));
66    }
67
68    #[inline]
69    fn write_u64(&mut self, value: u64) {
70        self.add(value);
71    }
72
73    #[inline]
74    fn write_usize(&mut self, value: usize) {
75        self.add(value as u64);
76    }
77
78    #[inline]
79    fn finish(&self) -> u64 {
80        self.hash
81    }
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn equal_keys_hash_equal_and_differ_from_neighbours() {
90        let hash = |key: &str| {
91            let mut hasher = FxHasher::default();
92            hasher.write(key.as_bytes());
93            hasher.finish()
94        };
95        assert_eq!(hash("ppt/slides/slide1.xml"), hash("ppt/slides/slide1.xml"));
96        assert_ne!(hash("ppt/slides/slide1.xml"), hash("ppt/slides/slide2.xml"));
97        assert_ne!(hash("rId1"), hash("rId2"));
98    }
99
100    #[test]
101    fn fast_map_round_trips() {
102        let mut map: FastMap<&str, u32> = FastMap::default();
103        map.insert("a", 1);
104        map.insert("b", 2);
105        assert_eq!(map.get("a"), Some(&1));
106        assert_eq!(map.get("c"), None);
107    }
108}
pptxboss_core/hash.rs

pptxboss_core/
hash.rs
