rapidhash/inner/
rapid_hasher.rs

1use core::hash::Hasher;
2use super::DEFAULT_RAPID_SECRETS;
3use super::mix_np::rapid_mix_np;
4use super::rapid_const::rapidhash_core;
5use super::seed::rapidhash_seed;
6use crate::util::hints::likely;
7
8/// This function needs to be as small as possible to have as high a chance of being inlined as
9/// possible.
10///
11/// We try to generate the least amount of LLVM-IR code to reduce the inlining cost. Rust should
12/// remove the const statements before generating the LLVM-IR.
13macro_rules! write_num {
14    ($write_num:ident, $int:ident, $unsigned:ident) => {
15
16        /// Write an integer to the hasher, marked as `#[inline(always)]`.
17        #[inline(always)]
18        fn $write_num(&mut self, i: $int) {
19            const N: u8 = core::mem::size_of::<$int>() as u8 * 8;
20            if SPONGE {
21                // This early u128 conversion seems to be important on x86, as if it impacts the
22                // LLVM inlining cost too much to have it inside the if statement...
23                // The compiler also converts an i32 -> i128 -> u128 unless we coerce it into its
24                // unsigned type first.
25                let bytes = (i as $unsigned) as u128;
26                if likely(self.sponge_len + N <= 128) {
27                    // HOT: add the bytes into the sponge
28                    self.sponge |= bytes << self.sponge_len;
29                    self.sponge_len += N;
30                } else {
31                    // COLD: sponge is full, so we need to flush it
32                    let a = self.sponge as u64;
33                    let b = (self.sponge >> 64) as u64;
34                    self.seed = rapid_mix_np::<PROTECTED>(a ^ self.seed, b ^ self.secrets[0]);
35                    self.sponge = bytes;
36                    self.sponge_len = N;
37                }
38            } else {
39                // slower but high-quality rapidhash
40                let bytes = (i as $unsigned) as u64;
41                self.seed = rapid_mix_np::<PROTECTED>(bytes ^ self.secrets[0], bytes ^ self.seed);
42            }
43        }
44    };
45}
46
47/// A [Hasher] trait compatible hasher that uses the [rapidhash](https://github.com/Nicoshev/rapidhash)
48/// algorithm, and uses `#[inline(always)]` for all methods.
49///
50/// Using `#[inline(always)]` can deliver a large performance improvement when hashing complex
51/// objects, but should be benchmarked for your specific use case. If you have HashMaps for many
52/// different types this may come at the cost of some binary size increase.
53///
54/// See [crate::fast::RandomState] for usage with [std::collections::HashMap].
55///
56/// # Example
57/// ```
58/// use std::hash::Hasher;
59///
60/// use rapidhash::quality::RapidHasher;
61///
62/// let mut hasher = RapidHasher::default();
63/// hasher.write(b"hello world");
64/// let hash = hasher.finish();
65/// ```
66#[derive(Copy, Clone)]
67pub struct RapidHasher<'s, const AVALANCHE: bool, const SPONGE: bool, const COMPACT: bool = false, const PROTECTED: bool = false> {
68    seed: u64,
69    secrets: &'s [u64; 7],
70    sponge: u128,
71    sponge_len: u8,
72}
73
74impl<'s, const AVALANCHE: bool, const SPONGE: bool, const COMPACT: bool, const PROTECTED: bool> RapidHasher<'s, AVALANCHE, SPONGE, COMPACT, PROTECTED> {
75    /// Default `RapidHasher` seed.
76    pub const DEFAULT_SEED: u64 = super::seed::DEFAULT_SEED;
77
78    /// Create a new [RapidHasher] with a custom seed.
79    ///
80    /// See instead [crate::quality::RandomState::new] or [crate::fast::RandomState::new] for a random
81    /// seed and random secret initialization, for minimal DoS resistance.
82    #[inline(always)]
83    #[must_use]
84    pub const fn new(mut seed: u64) -> Self {
85        // do most of the rapidhash_seed initialization here to avoid doing it on each int
86        seed = rapidhash_seed(seed);
87        Self::new_precomputed_seed(seed, &DEFAULT_RAPID_SECRETS.secrets)
88    }
89
90    #[inline(always)]
91    #[must_use]
92    pub(super) const fn new_precomputed_seed(seed: u64, secrets: &'s [u64; 7]) -> Self {
93        Self {
94            seed,
95            secrets,
96            sponge: 0,
97            sponge_len: 0,
98        }
99    }
100
101    /// Create a new [RapidHasher] using the default seed and secrets.
102    #[inline(always)]
103    #[must_use]
104    pub const fn default_const() -> Self {
105        Self::new(Self::DEFAULT_SEED)
106    }
107}
108
109impl<const AVALANCHE: bool, const SPONGE: bool, const COMPACT: bool, const PROTECTED: bool> Default for RapidHasher<'_, AVALANCHE, SPONGE, COMPACT, PROTECTED> {
110    /// Create a new [RapidHasher] with the default seed.
111    ///
112    /// See [crate::inner::RandomState] for a [std::hash::BuildHasher] that initializes with a random
113    /// seed.
114    #[inline(always)]
115    fn default() -> Self {
116        Self::new(super::seed::DEFAULT_SEED)
117    }
118}
119
120/// This implementation implements methods for all integer types as the compiler will (hopefully...)
121/// inline and heavily optimize the rapidhash_core for each. Where the bytes length is known the
122/// compiler can make significant optimisations and saves us writing them out by hand.
123impl<const AVALANCHE: bool, const SPONGE: bool, const COMPACT: bool, const PROTECTED: bool> Hasher for RapidHasher<'_, AVALANCHE, SPONGE, COMPACT, PROTECTED> {
124    /// Produce the final hash value, marked as `#[inline(always)]`.
125    #[inline(always)]
126    fn finish(&self) -> u64 {
127        // written to minimise the LLVM-IR lines, as rust should remove the const if statements
128        #[allow(clippy::collapsible_else_if)]
129        if SPONGE {
130            if !AVALANCHE {
131                if self.sponge_len > 0 {
132                    let a = self.sponge as u64;
133                    let b = (self.sponge >> 64) as u64;
134                    rapid_mix_np::<PROTECTED>(a ^ self.seed, b ^ self.secrets[0])
135                } else {
136                    self.seed
137                }
138            } else {
139                let mut seed = self.seed;
140                if self.sponge_len > 0 {
141                    let a = self.sponge as u64;
142                    let b = (self.sponge >> 64) as u64;
143                    seed = rapid_mix_np::<PROTECTED>(a ^ self.seed, b ^ self.secrets[0]);
144                }
145                // FUTURE: revisit when write_str is stable, as we'd want to move this into the
146                // above if statement
147                rapid_mix_np::<PROTECTED>(seed, DEFAULT_RAPID_SECRETS.secrets[1])
148            }
149        } else {
150            if !AVALANCHE {
151                self.seed
152            } else {
153                rapid_mix_np::<PROTECTED>(self.seed, DEFAULT_RAPID_SECRETS.secrets[1])
154            }
155        }
156    }
157
158    /// Write a byte slice to the hasher, marked as `#[inline(always)]`.
159    #[inline(always)]
160    fn write(&mut self, bytes: &[u8]) {
161        self.seed = rapidhash_core::<AVALANCHE, COMPACT, PROTECTED>(self.seed, self.secrets, bytes);
162    }
163
164    write_num!(write_u8, u8, u8);
165    write_num!(write_u16, u16, u16);
166    write_num!(write_u32, u32, u32);
167    write_num!(write_u64, u64, u64);
168    write_num!(write_usize, usize, usize);
169    write_num!(write_i8, i8, u8);
170    write_num!(write_i16, i16, u16);
171    write_num!(write_i32, i32, u32);
172    write_num!(write_i64, i64, u64);
173    write_num!(write_isize, isize, usize);
174
175    /// Write an int to the hasher, marked as `#[inline(always)]`.
176    #[inline(always)]
177    fn write_u128(&mut self, i: u128) {
178        let a = i as u64;
179        let b = (i >> 64) as u64;
180        self.seed = rapid_mix_np::<PROTECTED>(a ^ self.seed, b ^ self.secrets[0]);
181    }
182
183    /// Write an int to the hasher, marked as `#[inline(always)]`.
184    #[inline(always)]
185    fn write_i128(&mut self, i: i128) {
186        let a = (i as u128) as u64;
187        let b = (i as u128 >> 64) as u64;
188        self.seed = rapid_mix_np::<PROTECTED>(a ^ self.seed, b ^ self.secrets[0]);
189    }
190
191    /// Write a length prefix to the hasher, marked as `#[inline(always)]`.
192    #[cfg(feature = "nightly")]
193    #[inline(always)]
194    fn write_length_prefix(&mut self, len: usize) {
195        self.write_usize(len);
196    }
197
198    /// Write a string to the hasher, without adding a length prefix as rapidhash already mixes in
199    /// the byte length to prevent length extension attacks, marked as `#[inline(always)]`.
200    #[cfg(feature = "nightly")]
201    #[inline(always)]
202    fn write_str(&mut self, s: &str) {
203        self.write(s.as_bytes());
204    }
205}
206
207#[cfg(test)]
208mod tests {
209    extern crate std;
210
211    use std::hash::BuildHasher;
212    use crate::fast::SeedableState;
213    use super::*;
214
215    #[test]
216    fn test_hasher_size() {
217        assert_eq!(core::mem::size_of::<RapidHasher::<true, true, false, false>>(), 48);
218    }
219
220    /// Test that writing a single u64 outputs the same as writing the equivalent bytes.
221    ///
222    /// Does not apply if the algorithm is using a sponge.
223    #[ignore]
224    #[test]
225    fn test_hasher_write_u64() {
226        assert_eq!((8 & 24) >> (8 >> 3), 4);
227
228        let ints = [1234u64, 0, 1, u64::MAX, u64::MAX - 2385962040453523];
229
230        for int in ints {
231            let mut hasher = RapidHasher::<true, false>::default();
232            hasher.write(int.to_le_bytes().as_slice());
233            let a = hasher.finish();
234
235            assert_eq!(int.to_le_bytes().as_slice().len(), 8);
236
237            let mut hasher = RapidHasher::<true, false>::default();
238            hasher.write_u64(int);
239            let b = hasher.finish();
240
241            assert_eq!(a, b, "Mismatching hash for u64 with input {int}");
242        }
243    }
244
245    /// Check the number of collisions when writing numbers.
246    #[test]
247    #[ignore]
248    #[cfg(feature = "std")]
249    fn test_num_collisions() {
250        let builder = SeedableState::default();
251        let mut collisions = 0;
252        let mut set = std::collections::HashSet::new();
253        for i in 0..=u16::MAX {
254            let hash_u16 = builder.hash_one(i) & 0xFFFFFF;
255            if set.contains(&hash_u16) {
256                collisions += 1;
257            } else {
258                set.insert(hash_u16);
259            }
260
261            // if i < 256 {
262            //     let hash_u8 = builder.hash_one(i as u8) & 0xFFFF;
263            //     if set.contains(&hash_u8) {
264            //         collisions += 1;
265            //     } else {
266            //         set.insert(hash_u8);
267            //     }
268            // }
269        }
270        assert_eq!(collisions, 0, "Collisions found when hashing numbers with seed {builder:?}");
271    }
272}
rapidhash/inner/rapid_hasher.rs

rapidhash/inner/
rapid_hasher.rs
