rapidhash/
rapid_const.rs

1/// The rapidhash default seed.
2pub const RAPID_SEED: u64 = 0xbdd89aa982704029;
3pub(crate) const RAPID_SECRET: [u64; 3] = [0x2d358dccaa6c78a5, 0x8bb84b93962eacc9, 0x4b33a62ed433d4a3];
4
5/// Rapidhash a single byte stream, matching the C++ implementation.
6#[inline]
7pub const fn rapidhash(data: &[u8]) -> u64 {
8    rapidhash_inline(data, RAPID_SEED)
9}
10
11/// Rapidhash a single byte stream, matching the C++ implementation, with a custom seed.
12#[inline]
13pub const fn rapidhash_seeded(data: &[u8], seed: u64) -> u64 {
14    rapidhash_inline(data, seed)
15}
16
17/// Rapidhash a single byte stream, matching the C++ implementation.
18///
19/// Is marked with `#[inline(always)]` to force the compiler to inline and optimise the method.
20/// Can provide large performance uplifts for inputs where the length is known at compile time.
21#[inline(always)]
22pub const fn rapidhash_inline(data: &[u8], mut seed: u64) -> u64 {
23    seed = rapidhash_seed(seed, data.len() as u64);
24    let (a, b, _) = rapidhash_core(0, 0, seed, data);
25    rapidhash_finish(a, b, data.len() as u64)
26}
27
28#[inline(always)]
29pub const fn rapid_mum(a: u64, b: u64) -> (u64, u64) {
30    let r = a as u128 * b as u128;
31    (r as u64, (r >> 64) as u64)
32}
33
34#[inline(always)]
35pub const fn rapid_mix(a: u64, b: u64) -> u64 {
36    let (a, b) = rapid_mum(a, b);
37    a ^ b
38}
39
40#[inline(always)]
41pub(crate) const fn rapidhash_seed(seed: u64, len: u64) -> u64 {
42    seed ^ rapid_mix(seed ^ RAPID_SECRET[0], RAPID_SECRET[1]) ^ len
43}
44
45#[inline(always)]
46pub(crate) const fn rapidhash_core(mut a: u64, mut b: u64, mut seed: u64, data: &[u8]) -> (u64, u64, u64) {
47    if data.len() <= 16 {
48        // deviation from the C++ impl computes delta as follows
49        // let delta = (data.len() & 24) >> (data.len() >> 3);
50        // this is equivalent to "match {..8=>0, 8..=>4}"
51        // and so using the extra if-else statement is equivalent and allows the compiler to skip
52        // some unnecessary bounds checks while still being safe rust.
53        if data.len() >= 8 {
54            // len is 4..=16
55            let plast = data.len() - 4;
56            let delta = 4;
57            a ^= read_u32_combined(data, 0, plast);
58            b ^= read_u32_combined(data, delta, plast - delta);
59        } else if data.len() >= 4 {
60            let plast = data.len() - 4;
61            let delta = 0;
62            a ^= read_u32_combined(data, 0, plast);
63            b ^= read_u32_combined(data, delta, plast - delta);
64        } else if data.len() > 0 {
65            // len is 1..=3
66            let len = data.len();
67            a ^= ((data[0] as u64) << 56) | ((data[len >> 1] as u64) << 32) | data[len - 1] as u64;
68            // b = 0;
69        }
70    } else {
71        let mut slice = data;
72
73        // most CPUs appear to benefit from this unrolled loop
74        let mut see1 = seed;
75        let mut see2 = seed;
76        while slice.len() >= 96 {
77            seed = rapid_mix(read_u64(slice, 0) ^ RAPID_SECRET[0], read_u64(slice, 8) ^ seed);
78            see1 = rapid_mix(read_u64(slice, 16) ^ RAPID_SECRET[1], read_u64(slice, 24) ^ see1);
79            see2 = rapid_mix(read_u64(slice, 32) ^ RAPID_SECRET[2], read_u64(slice, 40) ^ see2);
80            seed = rapid_mix(read_u64(slice , 48) ^ RAPID_SECRET[0], read_u64(slice, 56) ^ seed);
81            see1 = rapid_mix(read_u64(slice, 64) ^ RAPID_SECRET[1], read_u64(slice, 72) ^ see1);
82            see2 = rapid_mix(read_u64(slice, 80) ^ RAPID_SECRET[2], read_u64(slice, 88) ^ see2);
83            let (_, split) = slice.split_at(96);
84            slice = split;
85        }
86        if slice.len() >= 48 {
87            seed = rapid_mix(read_u64(slice, 0) ^ RAPID_SECRET[0], read_u64(slice, 8) ^ seed);
88            see1 = rapid_mix(read_u64(slice, 16) ^ RAPID_SECRET[1], read_u64(slice, 24) ^ see1);
89            see2 = rapid_mix(read_u64(slice, 32) ^ RAPID_SECRET[2], read_u64(slice, 40) ^ see2);
90            let (_, split) = slice.split_at(48);
91            slice = split;
92        }
93        seed ^= see1 ^ see2;
94
95        if slice.len() > 16 {
96            seed = rapid_mix(read_u64(slice, 0) ^ RAPID_SECRET[2], read_u64(slice, 8) ^ seed ^ RAPID_SECRET[1]);
97            if slice.len() > 32 {
98                seed = rapid_mix(read_u64(slice, 16) ^ RAPID_SECRET[2], read_u64(slice, 24) ^ seed);
99            }
100        }
101
102        a ^= read_u64(data, data.len() - 16);
103        b ^= read_u64(data, data.len() - 8);
104    }
105
106    a ^= RAPID_SECRET[1];
107    b ^= seed;
108
109    let (a2, b2) = rapid_mum(a, b);
110    a = a2;
111    b = b2;
112    (a, b, seed)
113}
114
115#[inline(always)]
116pub(crate) const fn rapidhash_finish(a: u64, b: u64, len: u64) -> u64 {
117    rapid_mix(a ^ RAPID_SECRET[0] ^ len, b ^ RAPID_SECRET[1])
118}
119
120/// Hacky const-friendly memory-safe unaligned bytes to u64. Compiler can't seem to remove the
121/// bounds check, and so we have an unsafe version behind the `unsafe` feature flag.
122#[cfg(not(feature = "unsafe"))]
123#[inline(always)]
124pub(crate) const fn read_u64(slice: &[u8], offset: usize) -> u64 {
125    // equivalent to slice[offset..offset+8].try_into().unwrap(), but const-friendly
126    let maybe_buf = slice.split_at(offset).1.first_chunk::<8>();
127    let buf = match maybe_buf {
128        Some(buf) => *buf,
129        None => panic!("read_u64: slice too short"),
130    };
131    u64::from_le_bytes(buf)
132}
133
134/// Hacky const-friendly memory-safe unaligned bytes to u64. Compiler can't seem to remove the
135/// bounds check, and so we have an unsafe version behind the `unsafe` feature flag.
136#[cfg(not(feature = "unsafe"))]
137#[inline(always)]
138const fn read_u32(slice: &[u8], offset: usize) -> u32 {
139    // equivalent to slice[offset..offset+4].try_into().unwrap(), but const-friendly
140    let maybe_buf = slice.split_at(offset).1.first_chunk::<4>();
141    let buf = match maybe_buf {
142        Some(buf) => *buf,
143        None => panic!("read_u32: slice too short"),
144    };
145    u32::from_le_bytes(buf)
146}
147
148/// Unsafe but const-friendly unaligned bytes to u64. The compiler can't seem to remove the bounds
149/// checks for small integers because we do some funky bit shifting in the indexing.
150///
151/// SAFETY: `slice` must be at least `offset+8` bytes long, which we guarantee in this rapidhash
152/// implementation.
153#[cfg(feature = "unsafe")]
154#[inline(always)]
155pub(crate) const fn read_u64(slice: &[u8], offset: usize) -> u64 {
156    debug_assert!(offset as isize >= 0);
157    debug_assert!(slice.len() >= 8 + offset);
158    let val = unsafe { core::ptr::read_unaligned(slice.as_ptr().offset(offset as isize) as *const u64) };
159    val.to_le()  // swap bytes on big-endian systems to get the same u64 value
160}
161
162/// Unsafe but const-friendly unaligned bytes to u32. The compiler can't seem to remove the bounds
163/// checks for small integers because we do some funky bit shifting in the indexing.
164///
165/// SAFETY: `slice` must be at least `offset+8` bytes long, which we guarantee in this rapidhash
166/// implementation.
167#[cfg(feature = "unsafe")]
168#[inline(always)]
169const fn read_u32(slice: &[u8], offset: usize) -> u32 {
170    debug_assert!(offset as isize >= 0);
171    debug_assert!(slice.len() >= 4 + offset);
172    let val = unsafe { core::ptr::read_unaligned(slice.as_ptr().offset(offset as isize) as *const u32) };
173    val.to_le()  // swap bytes on big-endian systems to get the same u64 value
174}
175
176#[inline(always)]
177pub(crate) const fn read_u32_combined(slice: &[u8], offset_top: usize, offset_bot: usize) -> u64 {
178    debug_assert!(slice.len() >= 4 + offset_top && slice.len() >= 4 + offset_bot);
179    let top = read_u32(slice, offset_top) as u64;
180    let bot = read_u32(slice, offset_bot) as u64;
181    (top << 32) | bot
182}
183
184#[cfg(test)]
185mod tests {
186    use super::*;
187
188    #[test]
189    fn test_read_u32() {
190        let bytes = &[23, 145, 3, 34];
191
192        let split_result = bytes.split_at(0).1;
193        assert_eq!(split_result.len(), 4);
194        let maybe_buf = split_result.first_chunk::<4>();
195        assert_eq!(maybe_buf, Some(&[23, 145, 3, 34]));
196
197        assert_eq!(read_u32(bytes, 0), 570659095);
198
199        let bytes = &[24, 54, 3, 23, 145, 3, 34];
200        assert_eq!(read_u32(bytes, 3), 570659095);
201
202        assert_eq!(read_u32(&[0, 0, 0, 0], 0), 0);
203        assert_eq!(read_u32(&[1, 0, 0, 0], 0), 1);
204        assert_eq!(read_u32(&[12, 0, 0, 0], 0), 12);
205        assert_eq!(read_u32(&[0, 10, 0, 0], 0), 2560);
206    }
207
208    #[test]
209    fn test_read_u64() {
210        let bytes = [23, 145, 3, 34, 0, 0, 0, 0, 0, 0, 0].as_slice();
211        assert_eq!(read_u64(bytes, 0), 570659095);
212
213        let bytes = [1, 2, 3, 23, 145, 3, 34, 0, 0, 0, 0, 0, 0, 0].as_slice();
214        assert_eq!(read_u64(bytes, 3), 570659095);
215
216        let bytes = [0, 0, 0, 0, 0, 0, 0, 0].as_slice();
217        assert_eq!(read_u64(bytes, 0), 0);
218    }
219
220    #[cfg(feature = "std")]
221    #[test]
222    fn test_u32_to_u128_delta() {
223        fn formula(len: u64) -> u64 {
224            (len & 24) >> (len >> 3)
225        }
226
227        fn formula2(len: u64) -> u64 {
228            match len {
229                8.. => 4,
230                _ => 0,
231            }
232        }
233
234        let inputs: std::vec::Vec<u64> = (4..=16).collect();
235        let outputs: std::vec::Vec<u64> = inputs.iter().map(|&x| formula(x)).collect();
236        let expected = std::vec![0, 0, 0, 0, 4, 4, 4, 4, 4, 4, 4, 4, 4];
237        assert_eq!(outputs, expected);
238        assert_eq!(outputs, inputs.iter().map(|&x| formula2(x)).collect::<Vec<u64>>());
239    }
240
241    #[test]
242    #[should_panic]
243    #[cfg(any(test, not(feature = "unsafe")))]
244    fn test_read_u32_to_short_panics() {
245        let bytes = [23, 145, 0].as_slice();
246        assert_eq!(read_u32(bytes, 0), 0);
247    }
248
249    #[test]
250    #[should_panic]
251    #[cfg(any(test, not(feature = "unsafe")))]
252    fn test_read_u64_to_short_panics() {
253        let bytes = [23, 145, 0].as_slice();
254        assert_eq!(read_u64(bytes, 0), 0);
255    }
256
257    #[test]
258    fn test_rapid_mum() {
259        let (a, b) = rapid_mum(0, 0);
260        assert_eq!(a, 0);
261        assert_eq!(b, 0);
262
263        let (a, b) = rapid_mum(100, 100);
264        assert_eq!(a, 10000);
265        assert_eq!(b, 0);
266
267        let (a, b) = rapid_mum(u64::MAX, 2);
268        assert_eq!(a, u64::MAX - 1);
269        assert_eq!(b, 1);
270    }
271}
rapidhash/rapid_const.rs

rapidhash/
rapid_const.rs
