solana_hash/
hasher.rs

1use {
2    crate::HASH_BYTES,
3    core::{
4        cell::Cell,
5        hash::{BuildHasher, Hasher},
6        mem,
7    },
8    rand::{rng, Rng},
9};
10
11/// A faster, but less collision resistant hasher for hashes.
12///
13/// Specialized hasher that uses a random 8 bytes subslice of the
14/// hash as the hash value. Should not be used when collisions
15/// might be used to mount DOS attacks.
16///
17/// Using this results in about 4x faster lookups in a typical hashmap.
18#[derive(Default)]
19pub struct HashHasher {
20    offset: usize,
21    state: u64,
22}
23
24impl Hasher for HashHasher {
25    #[inline]
26    fn finish(&self) -> u64 {
27        self.state
28    }
29    #[inline]
30    fn write(&mut self, bytes: &[u8]) {
31        debug_assert_eq!(
32            bytes.len(),
33            HASH_BYTES,
34            "This hasher is intended to be used with hashes and nothing else"
35        );
36        // This slice/unwrap can never panic since offset is < HASH_BYTES - mem::size_of::<u64>()
37        let chunk: &[u8; mem::size_of::<u64>()] = bytes
38            [self.offset..self.offset + mem::size_of::<u64>()]
39            .try_into()
40            .unwrap();
41        self.state = u64::from_ne_bytes(*chunk);
42    }
43}
44
45/// A builder for faster, but less collision resistant hasher for hashes.
46///
47/// Initializes `HashHasher` instances that use an 8-byte
48/// slice of the hash as the hash value. Should not be used when
49/// collisions might be used to mount DOS attacks.
50///
51/// Using this results in about 4x faster lookups in a typical hashmap.
52#[derive(Clone)]
53pub struct HashHasherBuilder {
54    offset: usize,
55}
56
57impl HashHasherBuilder {
58    /// Constructs a builder with a specific offset.
59    ///
60    /// Prefer `HashHasherBuilder::default()` unless deterministic results are required.
61    pub fn with_offset(offset: usize) -> Self {
62        HashHasherBuilder { offset }
63    }
64
65    /// Returns the offset used to construct this builder.
66    pub fn offset(&self) -> usize {
67        self.offset
68    }
69}
70
71impl Default for HashHasherBuilder {
72    /// Default construct the HashHasherBuilder.
73    ///
74    /// The position of the slice is determined initially
75    /// through random draw and then by incrementing a thread-local
76    /// This way each hashmap can be expected to use a slightly different
77    /// slice. This is essentially the same mechanism as what is used by
78    /// `RandomState`
79    fn default() -> Self {
80        std::thread_local!(static OFFSET: Cell<usize>  = {
81            let mut rng = rng();
82            Cell::new(rng.random_range(0..HASH_BYTES - mem::size_of::<u64>()))
83        });
84
85        let offset = OFFSET.with(|offset| {
86            let mut next_offset = offset.get() + 1;
87            if next_offset > HASH_BYTES - mem::size_of::<u64>() {
88                next_offset = 0;
89            }
90            offset.set(next_offset);
91            next_offset
92        });
93        HashHasherBuilder { offset }
94    }
95}
96
97impl BuildHasher for HashHasherBuilder {
98    type Hasher = HashHasher;
99    #[inline]
100    fn build_hasher(&self) -> Self::Hasher {
101        HashHasher {
102            offset: self.offset,
103            state: 0,
104        }
105    }
106}
107
108#[cfg(test)]
109mod tests {
110    use {
111        super::HashHasherBuilder,
112        crate::{Hash, HASH_BYTES},
113        core::hash::{BuildHasher, Hasher},
114    };
115
116    fn hash_with_bytes(bytes: u8) -> Hash {
117        Hash::new_from_array([bytes; HASH_BYTES])
118    }
119
120    fn hash_with_distinct_windows() -> Hash {
121        Hash::new_from_array([
122            0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23,
123            24, 25, 26, 27, 28, 29, 30, 31,
124        ])
125    }
126
127    #[test]
128    fn test_hash_hasher_builder() {
129        let key = hash_with_distinct_windows();
130        let builder = HashHasherBuilder::default();
131        let mut hasher1 = builder.build_hasher();
132        let mut hasher2 = builder.build_hasher();
133        hasher1.write(key.as_bytes());
134        hasher2.write(key.as_bytes());
135        assert_eq!(
136            hasher1.finish(),
137            hasher2.finish(),
138            "Hashers made with same builder should be identical"
139        );
140        // Make sure that when we make new builders we get different slices
141        // chosen for hashing
142        let builder2 = HashHasherBuilder::default();
143        assert_ne!(builder.offset(), builder2.offset());
144        let mut hasher3 = builder2.build_hasher();
145        hasher3.write(key.as_bytes());
146        assert_ne!(
147            hasher1.finish(),
148            hasher3.finish(),
149            "Hashers built with different builder should use different offsets"
150        );
151    }
152
153    #[test]
154    fn test_hash_hasher() {
155        let key1 = hash_with_bytes(1);
156        let key2 = hash_with_bytes(2);
157        let builder = HashHasherBuilder::default();
158        let mut hasher1 = builder.build_hasher();
159        let mut hasher2 = builder.build_hasher();
160        hasher1.write(key1.as_bytes());
161        hasher2.write(key2.as_bytes());
162        assert_ne!(hasher1.finish(), hasher2.finish());
163    }
164
165    #[test]
166    fn test_builder_with_offset() {
167        let builder1 = HashHasherBuilder::default();
168        let offset1 = builder1.offset();
169        let builder2 = HashHasherBuilder::with_offset(offset1);
170        let offset2 = builder2.offset();
171        assert_eq!(offset1, offset2);
172        let key = hash_with_distinct_windows();
173        assert_eq!(builder1.hash_one(key), builder2.hash_one(key));
174    }
175}
solana_hash/hasher.rs

solana_hash/
hasher.rs
