rapidhash/inner/
mod.rs

1//! In-memory hashing: RapidHasher with full configurability via compile-time arguments.
2//!
3//! This module contains the Hasher, BuildHasher, HashMap, HashSet, and RandomState
4//! implementations. It is recommended to use [crate::fast] or [crate::quality], but for the
5//! advanced user, [crate::inner] can be used directly to customise the compile time options to
6//! modify the hash function.
7//!
8//! Each structure may have the compile time const generics:
9//! - `AVALANCHE`: Whether to use a final avalanche mix step, required to pass SMHasher3. This
10//!   option changes the hash output. Enabled on [crate::quality], disabled on [crate::fast].
11//! - `SPONGE`: Allow RapidHasher to cache integers into a 128-bit buffer to perform a single
12//!   folded multiply step on the entire buffer. If disabled, a mix step is performed on each
13//!   individual integer. This changes the hash output when hashing integers. Enabled on both
14//!   [crate::quality] and [crate::fast].
15//! - `COMPACT`: Reduce the code size of the hasher by preventing manually unrolled loops. This does
16//!   _not_ affect the hash output. Disabled on both [crate::quality] and [crate::fast].
17//! - `PROTECTED`: When performing the folded multiply mix step, XOR the a and b back into their
18//!   original values to make it harder for an attacker to generate collisions. This changes the
19//!   hash ouput. Disabled on both [crate::quality] and [crate::fast].
20//!
21//! The `RapidHasher` struct is _inspired by_ rapidhash, but is not a direct port and will output
22//! different hash values. It keeps the same hasher quality but uses various optimisations to
23//! improve performance when used in the Rust Hasher trait.
24//!
25//! The output values of functions in the `inner` module are not guaranteed to be stable between
26//! versions. Please use the `v1`, `v2`, or `v3` modules for stable output values between rapidhash
27//! crate versions.
28
29
30mod rapid_const;
31mod rapid_hasher;
32mod state;
33pub(crate) mod seeding;
34mod mix_np;
35mod seed;
36mod read_np;
37
38#[doc(inline)]
39pub use rapid_hasher::*;
40#[doc(inline)]
41pub use state::*;
42#[doc(inline)]
43use seed::*;
44
45#[cfg(test)]
46mod tests {
47    extern crate std;
48
49    use std::hash::{BuildHasher, Hash, Hasher};
50    use std::collections::BTreeSet;
51    use rand::Rng;
52    use crate::inner::mix_np::rapid_mix_np;
53    use super::seed::{DEFAULT_RAPID_SECRETS, DEFAULT_SEED};
54    use super::rapid_const::{rapidhash_rs, rapidhash_rs_seeded};
55
56    type RapidHasher = super::RapidHasher<'static, true, true, true, false>;
57    type SeedableState = super::SeedableState<'static, true, true, true, false>;
58
59    #[derive(Hash)]
60    struct Object {
61        string: &'static str,
62    }
63
64    /// `#[derive(Hash)]` writes a length prefix first, check understanding.
65    #[cfg(target_endian = "little")]
66    #[test]
67    fn derive_hash_works() {
68        #[cfg(not(feature = "nightly"))]
69        const EXPECTED: u64 = 7608958509739739138;
70
71        #[cfg(feature = "nightly")]
72        const EXPECTED: u64 = 8977256838778740407;
73
74        let object = Object { string: "hello world" };
75        let mut hasher = RapidHasher::default();
76        object.hash(&mut hasher);
77        assert_eq!(hasher.finish(), EXPECTED);
78
79        let mut hasher = RapidHasher::default();
80        hasher.write(object.string.as_bytes());
81        #[cfg(not(feature = "nightly"))] {
82            hasher.write_u8(0xFF);
83        }
84        assert_eq!(hasher.finish(), EXPECTED);
85    }
86
87    /// Check RapidHasher is equivalent to the raw rapidhash for a single byte stream.
88    ///
89    /// Also check that the hash is unique for different byte streams.
90    #[test]
91    fn all_sizes() {
92        let mut hashes = BTreeSet::new();
93
94        for size in 0..=1024 {
95            let mut data = std::vec![0; size];
96            rand::rng().fill(data.as_mut_slice());
97
98            let hash1 = rapidhash_rs(&data);
99            let mut hasher = RapidHasher::default();
100            hasher.write(&data);
101            let hash2 = hasher.finish();
102
103            assert_eq!(hash1, hash2, "Failed on size {}", size);
104            assert!(!hashes.contains(&hash1), "Duplicate for size {}", size);
105
106            hashes.insert(hash1);
107        }
108    }
109
110    /// Ensure that changing a single bit flips at least 10 bits in the resulting hash, and on
111    /// average flips half of the bits.
112    ///
113    /// These tests are not deterministic, but should fail with a very low probability.
114    #[test]
115    fn flip_bit_trial() {
116        use rand::Rng;
117
118        let mut flips = std::vec![];
119
120        for len in 1..=512 {
121            let mut data = std::vec![0; len];
122            rand::rng().fill(&mut data[..]);
123
124            let hash = rapidhash_rs(&data);
125            for byte in 0..len {
126                for bit in 0..8 {
127                    let mut data = data.clone();
128                    data[byte] ^= 1 << bit;
129                    let new_hash = rapidhash_rs(&data);
130                    assert_ne!(hash, new_hash, "Flipping byte {} bit {} did not change hash for input len {}", byte, bit, len);
131                    let xor = hash ^ new_hash;
132                    let flipped = xor.count_ones() as u64;
133                    assert!(xor.count_ones() >= 8, "Flipping bit {byte}:{bit} changed only {flipped} bits");
134
135                    flips.push(flipped);
136                }
137            }
138        }
139
140        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
141        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {average}, expected: 32.0");
142    }
143
144    /// Helper method for [flip_bit_trial_streaming]. Hashes a byte stream in u8 chunks.
145    fn streaming_hash(data: &[u8]) -> u64 {
146        let mut hasher = RapidHasher::default();
147        for byte in data {
148            hasher.write_u8(*byte);
149        }
150        hasher.finish()
151    }
152
153    /// Ensure various subsequent `write_u8` calls produce a stable result.
154    ///
155    /// Used to help diagnose an issue using rapidhash for PHF.
156    #[test]
157    fn sponge_buffer_stability() {
158        use std::collections::HashSet;
159
160        /// Simulate the UniCase Ascii/Unicode string hashing
161        fn manual_string_hash(data: &[u8]) -> u64 {
162            // ensure avalanche is disabled, sponge enabled to match PHF
163            let mut hasher = crate::inner::SeedableState::<'static, false, true, false, false>::fixed().build_hasher();
164            for byte in data {
165                hasher.write_u8(*byte);
166            }
167            hasher.write_u8(0xFF); // prefix freedom
168            hasher.finish()
169        }
170
171        let mut hashes = HashSet::new();
172
173        for len in 1..=64 {
174            for byte in 0u8..=255 {
175                // don't randomized the data, simply extend an extra byte each time
176                let data = std::vec![byte; len];
177
178                let hash1 = manual_string_hash(&data);
179                let hash2 = manual_string_hash(&data);
180                assert_eq!(hash1, hash2, "Mismatch for length {}", len);
181
182                assert!(!hashes.contains(&hash1), "Duplicate hash at length {}", len);
183                hashes.insert(hash1);
184            }
185        }
186    }
187
188    /// The same as [flip_bit_trial], but against our streaming implementation, to ensure that
189    /// reusing the `a`, `b`, and `seed` state is not causing glaringly obvious issues.
190    ///
191    /// This test is not a substitute for SMHasher or similar.
192    ///
193    /// These tests are not deterministic, but should fail with a very low probability.
194    #[test]
195    fn flip_bit_trial_streaming() {
196        use rand::Rng;
197
198        let mut flips = std::vec![];
199
200        for len in 1..=300 {
201            let mut data = std::vec![0; len];
202            rand::rng().fill(&mut data[..]);
203
204            let hash = streaming_hash(&data);
205            for byte in 0..len {
206                for bit in 0..8 {
207                    let mut data = data.clone();
208                    data[byte] ^= 1 << bit;
209
210                    // check that the hash changed
211                    let new_hash = streaming_hash(&data);
212                    assert_ne!(hash, new_hash, "Flipping bit {byte}:{bit} for input len {len} did not change hash");
213
214                    // track how many bits were flipped
215                    let xor = hash ^ new_hash;
216                    let flipped = xor.count_ones() as u64;
217                    assert!(xor.count_ones() >= 8, "Flipping bit {byte}:{bit} for input len {len} changed only {flipped} bits");
218                    flips.push(flipped);
219                }
220            }
221        }
222
223        // check that on average half of the bits were flipped
224        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
225        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {average}, expected: 32.0");
226    }
227
228    /// Compare to the C rapidhash implementation to ensure we match perfectly.
229    #[cfg(target_endian = "little")]
230    #[test]
231    fn compare_to_c() {
232        use rand::Rng;
233        use rapidhash_c::rapidhashcc_rs;
234
235        for len in 0..=512 {
236            let mut data = std::vec![0; len];
237            rand::rng().fill(&mut data[..]);
238
239            for byte in 0..len {
240                for bit in 0..8 {
241                    let mut data = data.clone();
242                    data[byte] ^= 1 << bit;
243
244                    let rust_hash = rapidhash_rs_seeded(&data, &DEFAULT_RAPID_SECRETS);
245                    let mut c_hash = rapidhashcc_rs(&data, DEFAULT_SEED);
246                    // TODO: remove this hack; it's to make it work with how the Hasher avalanches
247                    c_hash = rapid_mix_np::<false>(c_hash, DEFAULT_RAPID_SECRETS.secrets[1]);
248                    assert_eq!(rust_hash, c_hash, "Mismatch with input {} byte {} bit {}", len, byte, bit);
249
250                    let mut rust_hasher = SeedableState::fixed().build_hasher();
251                    rust_hasher.write(&data);
252                    let rust_hasher_hash = rust_hasher.finish();
253                    assert_eq!(rust_hash, rust_hasher_hash, "Hasher mismatch with input {} byte {} bit {}", len, byte, bit);
254                }
255            }
256        }
257    }
258
259    #[test]
260    fn disambiguation_check() {
261        use std::vec::Vec;
262
263        let hasher = SeedableState::default();
264
265        let a = [std::vec![1], std::vec![2, 3]];
266        let b = [std::vec![1, 2], std::vec![3]];
267        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
268
269        let a = [std::vec![], std::vec![1]];
270        let b = [std::vec![1],  std::vec![]];
271        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
272
273        let a: [Vec<Vec<u64>>; 2] = [std::vec![], std::vec![std::vec![]]];
274        let b: [Vec<Vec<u64>>; 2] = [std::vec![std::vec![]], std::vec![]];
275        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
276
277        let a = ["abc", "def"];
278        let b = ["fed", "abc"];
279        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
280
281        let a = ["abc", "def"];
282        let b = ["abcd", "ef"];
283        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
284
285        let a = [1u8, 2];
286        let b = [2u8, 1];
287        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
288
289        let a = [1u16, 2];
290        let b = [2u16, 1];
291        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
292
293        let a = [1u32, 2];
294        let b = [2u32, 1];
295        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
296
297        let a = [1u64, 2];
298        let b = [2u64, 1];
299        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
300
301        let a = [1u128, 2];
302        let b = [2u128, 1];
303        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
304    }
305}
rapidhash/inner/mod.rs

rapidhash/inner/
mod.rs
