twox_hash/
xxhash3.rs

1use core::slice;
2
3use crate::{IntoU128 as _, IntoU32 as _};
4
5pub mod large;
6
7pub(crate) use large::dispatch;
8pub use large::{Algorithm, Vector};
9
10pub mod secret;
11
12pub use secret::{Secret, SECRET_MINIMUM_LENGTH};
13
14mod streaming;
15
16pub use streaming::{
17    Finalize, FixedBuffer, FixedMutBuffer, RawHasherCore, SecretBuffer, SecretTooShortError,
18    SecretWithSeedError,
19};
20
21#[cfg(feature = "alloc")]
22pub use streaming::AllocRawHasher;
23
24pub mod primes {
25    pub const PRIME32_1: u64 = 0x9E3779B1;
26    pub const PRIME32_2: u64 = 0x85EBCA77;
27    pub const PRIME32_3: u64 = 0xC2B2AE3D;
28    pub const PRIME64_1: u64 = 0x9E3779B185EBCA87;
29    pub const PRIME64_2: u64 = 0xC2B2AE3D27D4EB4F;
30    pub const PRIME64_3: u64 = 0x165667B19E3779F9;
31    pub const PRIME64_4: u64 = 0x85EBCA77C2B2AE63;
32    pub const PRIME64_5: u64 = 0x27D4EB2F165667C5;
33    pub const PRIME_MX1: u64 = 0x165667919E3779F9;
34    pub const PRIME_MX2: u64 = 0x9FB21C651E98DF25;
35}
36
37pub const CUTOFF: usize = 240;
38
39pub const DEFAULT_SEED: u64 = 0;
40
41/// The length of the default secret.
42pub const DEFAULT_SECRET_LENGTH: usize = 192;
43
44pub type DefaultSecret = [u8; DEFAULT_SECRET_LENGTH];
45
46pub const DEFAULT_SECRET_RAW: DefaultSecret = [
47    0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
48    0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
49    0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
50    0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
51    0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
52    0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
53    0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
54    0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
55    0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
56    0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
57    0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
58    0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
59];
60
61// Safety: The default secret is long enough
62pub const DEFAULT_SECRET: &Secret = unsafe { Secret::new_unchecked(&DEFAULT_SECRET_RAW) };
63
64// This is a bit of magic... Without the `black_box`, the compiler can
65// and has constant-folded the `DEFAULT_SECRET` and then manifests it
66// as a bunch of immediate loads. Those immediate loads appear to make
67// some functions 1.5x the size (e.g. 800 to 1200 bytes).
68//
69// However, while I'm writing this comment, that no longer happens,
70// but the `black_box` *still* makes the code faster! I can't explain
71// why the current state is faster, but the code now clearly beats the
72// C performance.
73macro_rules! opaque_default_secret {
74    () => {
75        hint::black_box(DEFAULT_SECRET)
76    };
77}
78pub(crate) use opaque_default_secret;
79
80/// # Correctness
81///
82/// This function assumes that the incoming buffer has been populated
83/// with the default secret.
84#[inline]
85pub fn derive_secret(seed: u64, secret: &mut DefaultSecret) {
86    if seed == DEFAULT_SEED {
87        return;
88    }
89
90    let (words, _) = secret.bp_as_chunks_mut();
91    let (pairs, _) = words.bp_as_chunks_mut();
92
93    for [a_p, b_p] in pairs {
94        let a = u64::from_le_bytes(*a_p);
95        let b = u64::from_le_bytes(*b_p);
96
97        let a = a.wrapping_add(seed);
98        let b = b.wrapping_sub(seed);
99
100        *a_p = a.to_le_bytes();
101        *b_p = b.to_le_bytes();
102    }
103}
104
105/// The provided secret was not at least [`SECRET_MINIMUM_LENGTH`][]
106/// bytes.
107#[derive(Debug)]
108pub struct OneshotWithSecretError(pub(crate) secret::Error);
109
110impl core::error::Error for OneshotWithSecretError {}
111
112impl core::fmt::Display for OneshotWithSecretError {
113    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
114        self.0.fmt(f)
115    }
116}
117
118macro_rules! assert_input_range {
119    ($min:literal.., $len:expr) => {
120        assert!($min <= $len);
121    };
122    ($min:literal..=$max:literal, $len:expr) => {
123        assert!($min <= $len);
124        assert!($len <= $max);
125    };
126}
127pub(crate) use assert_input_range;
128
129#[inline(always)]
130pub fn impl_1_to_3_bytes_combined(input: &[u8]) -> u32 {
131    assert_input_range!(1..=3, input.len());
132    let input_length = input.len() as u8; // OK as we checked that the length fits
133
134    input[input.len() - 1].into_u32()
135        | input_length.into_u32() << 8
136        | input[0].into_u32() << 16
137        | input[input.len() >> 1].into_u32() << 24
138}
139
140#[inline]
141pub fn impl_17_to_128_bytes_iter(
142    secret: &Secret,
143    input: &[u8],
144    mut f: impl FnMut(&[u8; 16], &[u8; 16], &[[u8; 16]; 2]),
145) {
146    let secret = secret.words_for_17_to_128();
147    let (secret, _) = secret.bp_as_chunks();
148    let (fwd, _) = input.bp_as_chunks();
149
150    // The `n`th 16-byte chunk of `input`, counting backwards from the
151    // end.
152    //
153    // Using `slice::as_rchunks` yields the same chunks, but the
154    // generated assembly on x86_64 is worse. This form appears to
155    // allow the compiler to reuse some registers.
156    let bwd_chunk = |n: usize| input[input.len() - 16 * (n + 1)..].first_chunk().unwrap();
157
158    if input.len() > 32 {
159        if input.len() > 64 {
160            if input.len() > 96 {
161                f(&fwd[3], bwd_chunk(3), &secret[3]);
162            }
163
164            f(&fwd[2], bwd_chunk(2), &secret[2]);
165        }
166
167        f(&fwd[1], bwd_chunk(1), &secret[1]);
168    }
169
170    f(&fwd[0], bwd_chunk(0), &secret[0]);
171}
172
173#[inline]
174pub fn mix_step(data: &[u8; 16], secret: &[u8; 16], seed: u64) -> u64 {
175    let data_words = to_u64s(data);
176    let secret_words = to_u64s(secret);
177
178    let mul_result = {
179        let a = (data_words[0] ^ secret_words[0].wrapping_add(seed)).into_u128();
180        let b = (data_words[1] ^ secret_words[1].wrapping_sub(seed)).into_u128();
181
182        a.wrapping_mul(b)
183    };
184
185    mul_result.lower_half() ^ mul_result.upper_half()
186}
187
188#[inline]
189pub fn to_u64s(bytes: &[u8; 16]) -> [u64; 2] {
190    let (pair, _) = bytes.bp_as_chunks();
191    [pair[0], pair[1]].map(u64::from_le_bytes)
192}
193
194#[inline]
195#[cfg(feature = "xxhash3_128")]
196pub fn pairs_of_u64_bytes(bytes: &[u8]) -> &[[[u8; 16]; 2]] {
197    let (u64_bytes, _) = bytes.bp_as_chunks();
198    let (pairs, _) = u64_bytes.bp_as_chunks();
199    pairs
200}
201
202#[inline]
203pub fn avalanche(mut x: u64) -> u64 {
204    x ^= x >> 37;
205    x = x.wrapping_mul(primes::PRIME_MX1);
206    x ^= x >> 32;
207    x
208}
209
210#[inline]
211pub fn avalanche_xxh64(mut x: u64) -> u64 {
212    x ^= x >> 33;
213    x = x.wrapping_mul(primes::PRIME64_2);
214    x ^= x >> 29;
215    x = x.wrapping_mul(primes::PRIME64_3);
216    x ^= x >> 32;
217    x
218}
219
220#[inline]
221pub fn stripes_with_tail(block: &[u8]) -> (&[[u8; 64]], &[u8]) {
222    match block.bp_as_chunks() {
223        ([stripes @ .., last], []) => (stripes, last),
224        (stripes, last) => (stripes, last),
225    }
226}
227
228/// This exists just to easily map the XXH3 algorithm to Rust as the
229/// algorithm describes 128-bit results as a pair of high and low u64
230/// values.
231#[derive(Copy, Clone)]
232pub(crate) struct X128 {
233    pub low: u64,
234    pub high: u64,
235}
236
237impl From<X128> for u128 {
238    fn from(value: X128) -> Self {
239        value.high.into_u128() << 64 | value.low.into_u128()
240    }
241}
242
243impl crate::IntoU128 for X128 {
244    fn into_u128(self) -> u128 {
245        self.into()
246    }
247}
248
249pub trait Halves {
250    type Output;
251
252    fn upper_half(self) -> Self::Output;
253    fn lower_half(self) -> Self::Output;
254}
255
256impl Halves for u64 {
257    type Output = u32;
258
259    #[inline]
260    fn upper_half(self) -> Self::Output {
261        (self >> 32) as _
262    }
263
264    #[inline]
265    fn lower_half(self) -> Self::Output {
266        self as _
267    }
268}
269
270impl Halves for u128 {
271    type Output = u64;
272
273    #[inline]
274    fn upper_half(self) -> Self::Output {
275        (self >> 64) as _
276    }
277
278    #[inline]
279    fn lower_half(self) -> Self::Output {
280        self as _
281    }
282}
283
284pub trait U8SliceExt {
285    fn first_u32(&self) -> Option<u32>;
286
287    fn last_u32(&self) -> Option<u32>;
288
289    fn first_u64(&self) -> Option<u64>;
290
291    fn last_u64(&self) -> Option<u64>;
292}
293
294impl U8SliceExt for [u8] {
295    #[inline]
296    fn first_u32(&self) -> Option<u32> {
297        self.first_chunk().copied().map(u32::from_le_bytes)
298    }
299
300    #[inline]
301    fn last_u32(&self) -> Option<u32> {
302        self.last_chunk().copied().map(u32::from_le_bytes)
303    }
304
305    #[inline]
306    fn first_u64(&self) -> Option<u64> {
307        self.first_chunk().copied().map(u64::from_le_bytes)
308    }
309
310    #[inline]
311    fn last_u64(&self) -> Option<u64> {
312        self.last_chunk().copied().map(u64::from_le_bytes)
313    }
314}
315
316pub trait SliceBackport<T> {
317    fn bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]);
318
319    fn bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]);
320}
321
322impl<T> SliceBackport<T> for [T] {
323    fn bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
324        assert_ne!(N, 0);
325        let len = self.len() / N;
326        // Safety: `(len / N) * N` has to be less-than-or-equal to `len`
327        let (head, tail) = unsafe { self.split_at_unchecked(len * N) };
328        // Safety: (1) `head` points to valid data, (2) the alignment
329        // of an array and the individual type are the same, (3) the
330        // valid elements are less-than-or-equal to the original
331        // slice.
332        let head = unsafe { slice::from_raw_parts(head.as_ptr().cast(), len) };
333        (head, tail)
334    }
335
336    fn bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
337        assert_ne!(N, 0);
338        let len = self.len() / N;
339        // Safety: `(len / N) * N` has to be less than or equal to `len`
340        let (head, tail) = unsafe { self.split_at_mut_unchecked(len * N) };
341        // Safety: (1) `head` points to valid data, (2) the alignment
342        // of an array and the individual type are the same, (3) the
343        // valid elements are less-than-or-equal to the original
344        // slice.
345        let head = unsafe { slice::from_raw_parts_mut(head.as_mut_ptr().cast(), len) };
346        (head, tail)
347    }
348}
349
350#[cfg(test)]
351pub mod test {
352    use std::array;
353
354    use super::*;
355
356    macro_rules! bytes {
357        ($($n: literal),* $(,)?) => {
358            &[$(&crate::xxhash3::test::gen_bytes::<$n>() as &[u8],)*] as &[&[u8]]
359        };
360    }
361    pub(crate) use bytes;
362
363    pub fn gen_bytes<const N: usize>() -> [u8; N] {
364        // Picking 251 as it's a prime number, which will hopefully
365        // help avoid incidental power-of-two alignment.
366        array::from_fn(|i| (i % 251) as u8)
367    }
368
369    #[test]
370    fn default_secret_is_valid() {
371        assert!(DEFAULT_SECRET.is_valid());
372    }
373
374    #[test]
375    fn backported_as_chunks() {
376        let x = [1, 2, 3, 4, 5];
377
378        let (a, b) = x.bp_as_chunks::<1>();
379        assert_eq!(a, &[[1], [2], [3], [4], [5]]);
380        assert_eq!(b, &[] as &[i32]);
381
382        let (a, b) = x.bp_as_chunks::<2>();
383        assert_eq!(a, &[[1, 2], [3, 4]]);
384        assert_eq!(b, &[5]);
385
386        let (a, b) = x.bp_as_chunks::<3>();
387        assert_eq!(a, &[[1, 2, 3]]);
388        assert_eq!(b, &[4, 5]);
389
390        let (a, b) = x.bp_as_chunks::<4>();
391        assert_eq!(a, &[[1, 2, 3, 4]]);
392        assert_eq!(b, &[5]);
393
394        let (a, b) = x.bp_as_chunks::<5>();
395        assert_eq!(a, &[[1, 2, 3, 4, 5]]);
396        assert_eq!(b, &[] as &[i32]);
397
398        let (a, b) = x.bp_as_chunks::<6>();
399        assert_eq!(a, &[] as &[[i32; 6]]);
400        assert_eq!(b, &[1, 2, 3, 4, 5]);
401    }
402}
twox_hash/xxhash3.rs

twox_hash/
xxhash3.rs
