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::RngExt;
52    use rapidrand::RapidRng;
53    use crate::inner::mix_np::rapid_mix_np;
54    use super::seed::{DEFAULT_RAPID_SECRETS, DEFAULT_SEED};
55    use super::rapid_const::{rapidhash_rs, rapidhash_rs_seeded};
56
57    type RapidHasher = super::RapidHasher<'static, true, true, true, false>;
58    type SeedableState = super::SeedableState<'static, true, true, true, false>;
59
60    #[derive(Hash)]
61    struct Object {
62        string: &'static str,
63    }
64
65    /// `#[derive(Hash)]` writes a length prefix first, check understanding.
66    ///
67    /// Cfg gated as this test's expected values are set correctly for platforms that:
68    /// - Use the 128-bit multiply path
69    /// - Are little endian
70    #[cfg(any(
71        all(
72            target_pointer_width = "64",
73            not(any(target_arch = "sparc64", target_arch = "wasm64")),
74        ),
75        target_arch = "aarch64",
76        target_arch = "x86_64",
77        all(target_family = "wasm", target_feature = "wide-arithmetic"),
78    ))]
79    #[cfg(target_endian = "little")]
80    #[test]
81    fn derive_hash_works() {
82        #[cfg(not(feature = "nightly"))]
83        const EXPECTED: u64 = 7608958509739739138;
84
85        #[cfg(feature = "nightly")]
86        const EXPECTED: u64 = 8977256838778740407;
87
88        let object = Object { string: "hello world" };
89        let mut hasher = RapidHasher::default();
90        object.hash(&mut hasher);
91        assert_eq!(hasher.finish(), EXPECTED);
92
93        let mut hasher = RapidHasher::default();
94        hasher.write(object.string.as_bytes());
95        #[cfg(not(feature = "nightly"))] {
96            hasher.write_u8(0xFF);
97        }
98        assert_eq!(hasher.finish(), EXPECTED);
99    }
100
101    /// Check RapidHasher is equivalent to the raw rapidhash for a single byte stream.
102    ///
103    /// Also check that the hash is unique for different byte streams.
104    #[test]
105    fn all_sizes() {
106        let mut rng: RapidRng = rand::make_rng();
107        let mut hashes = BTreeSet::new();
108
109        for size in 0..=1024 {
110            let mut data = std::vec![0; size];
111            rng.fill(data.as_mut_slice());
112
113            let hash1 = rapidhash_rs(&data);
114            let mut hasher = RapidHasher::default();
115            hasher.write(&data);
116            let hash2 = hasher.finish();
117
118            assert_eq!(hash1, hash2, "Failed on size {}", size);
119            assert!(!hashes.contains(&hash1), "Duplicate for size {}", size);
120
121            hashes.insert(hash1);
122        }
123    }
124
125    /// Ensure that changing a single bit flips at least 10 bits in the resulting hash, and on
126    /// average flips half of the bits.
127    ///
128    /// These tests are not deterministic, but should fail with a very low probability.
129    #[test]
130    fn flip_bit_trial() {
131        let mut rng: RapidRng = rand::make_rng();
132        let mut flips = std::vec![];
133
134        for len in 1..=512 {
135            let mut data = std::vec![0; len];
136            rng.fill(&mut data[..]);
137
138            let hash = rapidhash_rs(&data);
139            for byte in 0..len {
140                for bit in 0..8 {
141                    let mut data = data.clone();
142                    data[byte] ^= 1 << bit;
143                    let new_hash = rapidhash_rs(&data);
144                    assert_ne!(hash, new_hash, "Flipping byte {} bit {} did not change hash for input len {}", byte, bit, len);
145                    let xor = hash ^ new_hash;
146                    let flipped = xor.count_ones() as u64;
147                    assert!(xor.count_ones() >= 8, "Flipping bit {byte}:{bit} changed only {flipped} bits");
148
149                    flips.push(flipped);
150                }
151            }
152        }
153
154        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
155        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {average}, expected: 32.0");
156    }
157
158    /// Helper method for [flip_bit_trial_streaming]. Hashes a byte stream in u8 chunks.
159    fn streaming_hash(data: &[u8]) -> u64 {
160        let mut hasher = RapidHasher::default();
161        for byte in data {
162            hasher.write_u8(*byte);
163        }
164        hasher.finish()
165    }
166
167    /// Ensure various subsequent `write_u8` calls produce a stable result.
168    ///
169    /// Used to help diagnose an issue using rapidhash for PHF.
170    #[test]
171    fn sponge_buffer_stability() {
172        use std::collections::HashSet;
173
174        /// Simulate the UniCase Ascii/Unicode string hashing
175        fn manual_string_hash(data: &[u8]) -> u64 {
176            // ensure avalanche is disabled, sponge enabled to match PHF
177            let mut hasher = crate::inner::SeedableState::<'static, false, true, false, false>::fixed().build_hasher();
178            for byte in data {
179                hasher.write_u8(*byte);
180            }
181            hasher.write_u8(0xFF); // prefix freedom
182            hasher.finish()
183        }
184
185        let mut hashes = HashSet::new();
186
187        for len in 1..=64 {
188            for byte in 0u8..=255 {
189                // don't randomized the data, simply extend an extra byte each time
190                let data = std::vec![byte; len];
191
192                let hash1 = manual_string_hash(&data);
193                let hash2 = manual_string_hash(&data);
194                assert_eq!(hash1, hash2, "Mismatch for length {}", len);
195
196                assert!(!hashes.contains(&hash1), "Duplicate hash at length {}", len);
197                hashes.insert(hash1);
198            }
199        }
200    }
201
202    /// The same as [flip_bit_trial], but against our streaming implementation, to ensure that
203    /// reusing the `a`, `b`, and `seed` state is not causing glaringly obvious issues.
204    ///
205    /// This test is not a substitute for SMHasher or similar.
206    ///
207    /// These tests are not deterministic, but should fail with a very low probability.
208    #[test]
209    fn flip_bit_trial_streaming() {
210        let mut rng: RapidRng = rand::make_rng();
211        let mut flips = std::vec![];
212
213        for len in 1..=300 {
214            let mut data = std::vec![0; len];
215            rng.fill(&mut data[..]);
216
217            let hash = streaming_hash(&data);
218            for byte in 0..len {
219                for bit in 0..8 {
220                    let mut data = data.clone();
221                    data[byte] ^= 1 << bit;
222
223                    // check that the hash changed
224                    let new_hash = streaming_hash(&data);
225                    assert_ne!(hash, new_hash, "Flipping bit {byte}:{bit} for input len {len} did not change hash");
226
227                    // track how many bits were flipped
228                    let xor = hash ^ new_hash;
229                    let flipped = xor.count_ones() as u64;
230                    assert!(xor.count_ones() >= 8, "Flipping bit {byte}:{bit} for input len {len} changed only {flipped} bits");
231                    flips.push(flipped);
232                }
233            }
234        }
235
236        // check that on average half of the bits were flipped
237        let average = flips.iter().sum::<u64>() as f64 / flips.len() as f64;
238        assert!(average > 31.95 && average < 32.05, "Did not flip an average of half the bits. average: {average}, expected: 32.0");
239    }
240
241    /// Compare to the C rapidhash implementation to ensure we match perfectly.
242    ///
243    /// Only where the Rust code doesn't go through 32-bit fast paths, or on little-endian platforms
244    /// as we're not looking at a portable/stable hasher here.
245    #[cfg(any(
246        all(
247            target_pointer_width = "64",
248            not(any(target_arch = "sparc64", target_arch = "wasm64")),
249        ),
250        target_arch = "aarch64",
251        target_arch = "x86_64",
252        all(target_family = "wasm", target_feature = "wide-arithmetic"),
253    ))]
254    #[cfg(target_endian = "little")]
255    #[test]
256    fn compare_to_c() {
257        use rapidhash_c::rapidhashcc_rs;
258        let mut rng: RapidRng = rand::make_rng();
259
260        for len in 0..=512 {
261            let mut data = std::vec![0; len];
262            rng.fill(&mut data[..]);
263
264            for byte in 0..len {
265                for bit in 0..8 {
266                    let mut data = data.clone();
267                    data[byte] ^= 1 << bit;
268
269                    let rust_hash = rapidhash_rs_seeded(&data, &DEFAULT_RAPID_SECRETS);
270                    let mut c_hash = rapidhashcc_rs(&data, DEFAULT_SEED);
271                    // TODO: remove this hack; it's to make it work with how the Hasher avalanches
272                    c_hash = rapid_mix_np::<false>(c_hash, DEFAULT_RAPID_SECRETS.secrets[1]);
273                    assert_eq!(rust_hash, c_hash, "Mismatch with input {} byte {} bit {}", len, byte, bit);
274
275                    let mut rust_hasher = SeedableState::fixed().build_hasher();
276                    rust_hasher.write(&data);
277                    let rust_hasher_hash = rust_hasher.finish();
278                    assert_eq!(rust_hash, rust_hasher_hash, "Hasher mismatch with input {} byte {} bit {}", len, byte, bit);
279                }
280            }
281        }
282    }
283
284    #[test]
285    fn disambiguation_check() {
286        use std::vec::Vec;
287
288        let hasher = SeedableState::default();
289
290        let a = [std::vec![1], std::vec![2, 3]];
291        let b = [std::vec![1, 2], std::vec![3]];
292        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
293
294        let a = [std::vec![], std::vec![1]];
295        let b = [std::vec![1],  std::vec![]];
296        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
297
298        let a: [Vec<Vec<u64>>; 2] = [std::vec![], std::vec![std::vec![]]];
299        let b: [Vec<Vec<u64>>; 2] = [std::vec![std::vec![]], std::vec![]];
300        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
301
302        let a = ["abc", "def"];
303        let b = ["fed", "abc"];
304        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
305
306        let a = ["abc", "def"];
307        let b = ["abcd", "ef"];
308        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
309
310        let a = [1u8, 2];
311        let b = [2u8, 1];
312        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
313
314        let a = [1u16, 2];
315        let b = [2u16, 1];
316        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
317
318        let a = [1u32, 2];
319        let b = [2u32, 1];
320        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
321
322        let a = [1u64, 2];
323        let b = [2u64, 1];
324        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
325
326        let a = [1u128, 2];
327        let b = [2u128, 1];
328        assert_ne!(hasher.hash_one(a), hasher.hash_one(b));
329    }
330}
rapidhash/inner/mod.rs

rapidhash/inner/
mod.rs
