bacnet_types/
map_hash.rs

1//! A cheap hasher for small maps a program fills itself (#1713).
2//!
3//! SipHash, the standard map's hasher, guards a map an attacker can fill
4//! with colliding keys. Some of this stack's per-request maps can't be
5//! filled that way: the client's transaction table holds only the peers the
6//! client sent requests to, since an answer from the network only looks a
7//! key up, and the server's admission table holds at most one entry per
8//! request it is running, which its in-flight limit caps. Such a map can
9//! hash with the multiply-and-rotate scheme rustc's own maps use, at a
10//! fraction of SipHash's cost. Don't use it for a map remote input can grow.
11
12use core::hash::{BuildHasherDefault, Hasher};
13
14/// The odd multiplier rustc-hash 2 uses.
15const K: u64 = 0xf135_7aea_2e62_a9c5;
16
17/// Multiply-and-rotate hasher over 64-bit words. See the module
18/// documentation for the maps it suits.
19#[derive(Debug, Default, Clone, Copy)]
20pub struct MapHasher(u64);
21
22impl MapHasher {
23    #[inline]
24    fn add(&mut self, word: u64) {
25        self.0 = self.0.wrapping_add(word).wrapping_mul(K);
26    }
27}
28
29impl Hasher for MapHasher {
30    #[inline]
31    fn write(&mut self, bytes: &[u8]) {
32        let (words, rest) = bytes.as_chunks::<8>();
33        for word in words {
34            self.add(u64::from_le_bytes(*word));
35        }
36        if !rest.is_empty() {
37            let mut word = [0u8; 8];
38            word[..rest.len()].copy_from_slice(rest);
39            // The length keeps a short tail distinct from zero padding.
40            self.add(u64::from_le_bytes(word) ^ ((rest.len() as u64) << 56));
41        }
42    }
43
44    #[inline]
45    fn write_u8(&mut self, value: u8) {
46        self.add(u64::from(value));
47    }
48
49    #[inline]
50    fn write_u16(&mut self, value: u16) {
51        self.add(u64::from(value));
52    }
53
54    #[inline]
55    fn write_u32(&mut self, value: u32) {
56        self.add(u64::from(value));
57    }
58
59    #[inline]
60    fn write_u64(&mut self, value: u64) {
61        self.add(value);
62    }
63
64    #[inline]
65    fn write_usize(&mut self, value: usize) {
66        self.add(value as u64);
67    }
68
69    #[inline]
70    fn finish(&self) -> u64 {
71        // The map takes its control bits from the top of the hash, where a
72        // multiply mixes least; the rotation brings mixed bits up there.
73        self.0.rotate_left(26)
74    }
75}
76
77/// Builds a [`MapHasher`]: the `S` of a `HashMap<K, V, S>`.
78pub type BuildMapHasher = BuildHasherDefault<MapHasher>;
79
80// The keys are `MacAddr`, which needs `alloc`.
81#[cfg(all(test, feature = "alloc"))]
82mod tests {
83    use super::*;
84    use crate::MacAddr;
85    use core::hash::BuildHasher;
86    use std::collections::HashMap;
87
88    fn hash(key: &(MacAddr, u8)) -> u64 {
89        BuildMapHasher::default().hash_one(key)
90    }
91
92    #[test]
93    fn distinct_peers_and_invoke_ids_hash_apart() {
94        let macs: [&[u8]; 6] = [
95            &[1],
96            &[1, 0],
97            &[0, 1],
98            &[192, 168, 1, 10, 0xba, 0xc0],
99            &[192, 168, 1, 11, 0xba, 0xc0],
100            &[0xff, 0x52, 0, 5, 1, 3, 9],
101        ];
102        let mut seen = std::collections::HashSet::new();
103        for mac in macs {
104            for invoke in [0u8, 1, 255] {
105                assert!(seen.insert(hash(&(MacAddr::from_slice(mac), invoke))));
106            }
107        }
108    }
109
110    #[test]
111    fn a_map_finds_what_it_holds() {
112        let mut map: HashMap<_, _, BuildMapHasher> = HashMap::default();
113        for station in 0..=255u8 {
114            for invoke in 0..4u8 {
115                map.insert(
116                    (MacAddr::from_slice(&[station]), invoke),
117                    u16::from(station),
118                );
119            }
120        }
121        assert_eq!(map.len(), 1024);
122        assert_eq!(map.get(&(MacAddr::from_slice(&[77]), 3)), Some(&77));
123        assert!(!map.contains_key(&(MacAddr::from_slice(&[77, 0]), 3)));
124    }
125}
bacnet_types/map_hash.rs

bacnet_types/
map_hash.rs
