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/// # Correctness
65///
66/// This function assumes that the incoming buffer has been populated
67/// with the default secret.
68#[inline]
69pub fn derive_secret(seed: u64, secret: &mut DefaultSecret) {
70    if seed == DEFAULT_SEED {
71        return;
72    }
73
74    let (words, _) = secret.bp_as_chunks_mut();
75    let (pairs, _) = words.bp_as_chunks_mut();
76
77    for [a_p, b_p] in pairs {
78        let a = u64::from_le_bytes(*a_p);
79        let b = u64::from_le_bytes(*b_p);
80
81        let a = a.wrapping_add(seed);
82        let b = b.wrapping_sub(seed);
83
84        *a_p = a.to_le_bytes();
85        *b_p = b.to_le_bytes();
86    }
87}
88
89/// The provided secret was not at least [`SECRET_MINIMUM_LENGTH`][]
90/// bytes.
91#[derive(Debug)]
92pub struct OneshotWithSecretError(pub(crate) secret::Error);
93
94impl core::error::Error for OneshotWithSecretError {}
95
96impl core::fmt::Display for OneshotWithSecretError {
97    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
98        self.0.fmt(f)
99    }
100}
101
102macro_rules! assert_input_range {
103    ($min:literal.., $len:expr) => {
104        assert!($min <= $len);
105    };
106    ($min:literal..=$max:literal, $len:expr) => {
107        assert!($min <= $len);
108        assert!($len <= $max);
109    };
110}
111pub(crate) use assert_input_range;
112
113#[inline(always)]
114pub fn impl_1_to_3_bytes_combined(input: &[u8]) -> u32 {
115    assert_input_range!(1..=3, input.len());
116    let input_length = input.len() as u8; // OK as we checked that the length fits
117
118    input[input.len() - 1].into_u32()
119        | input_length.into_u32() << 8
120        | input[0].into_u32() << 16
121        | input[input.len() >> 1].into_u32() << 24
122}
123
124#[inline]
125pub fn impl_17_to_128_bytes_iter(
126    secret: &Secret,
127    input: &[u8],
128    mut f: impl FnMut(&[u8; 16], &[u8; 16], &[[u8; 16]; 2]),
129) {
130    let secret = secret.words_for_17_to_128();
131    let (secret, _) = secret.bp_as_chunks::<2>();
132    let (fwd, _) = input.bp_as_chunks();
133    let (_, bwd) = input.bp_as_rchunks();
134
135    let q = bwd.len();
136
137    if input.len() > 32 {
138        if input.len() > 64 {
139            if input.len() > 96 {
140                f(&fwd[3], &bwd[q - 4], &secret[3]);
141            }
142
143            f(&fwd[2], &bwd[q - 3], &secret[2]);
144        }
145
146        f(&fwd[1], &bwd[q - 2], &secret[1]);
147    }
148
149    f(&fwd[0], &bwd[q - 1], &secret[0]);
150}
151
152#[inline]
153pub fn mix_step(data: &[u8; 16], secret: &[u8; 16], seed: u64) -> u64 {
154    let data_words = to_u64s(data);
155    let secret_words = to_u64s(secret);
156
157    let mul_result = {
158        let a = (data_words[0] ^ secret_words[0].wrapping_add(seed)).into_u128();
159        let b = (data_words[1] ^ secret_words[1].wrapping_sub(seed)).into_u128();
160
161        a.wrapping_mul(b)
162    };
163
164    mul_result.lower_half() ^ mul_result.upper_half()
165}
166
167#[inline]
168pub fn to_u64s(bytes: &[u8; 16]) -> [u64; 2] {
169    let (pair, _) = bytes.bp_as_chunks::<8>();
170    [pair[0], pair[1]].map(u64::from_le_bytes)
171}
172
173#[inline]
174#[cfg(feature = "xxhash3_128")]
175pub fn pairs_of_u64_bytes(bytes: &[u8]) -> &[[[u8; 16]; 2]] {
176    let (u64_bytes, _) = bytes.bp_as_chunks::<16>();
177    let (pairs, _) = u64_bytes.bp_as_chunks::<2>();
178    pairs
179}
180
181#[inline]
182pub fn avalanche(mut x: u64) -> u64 {
183    x ^= x >> 37;
184    x = x.wrapping_mul(primes::PRIME_MX1);
185    x ^= x >> 32;
186    x
187}
188
189#[inline]
190pub fn avalanche_xxh64(mut x: u64) -> u64 {
191    x ^= x >> 33;
192    x = x.wrapping_mul(primes::PRIME64_2);
193    x ^= x >> 29;
194    x = x.wrapping_mul(primes::PRIME64_3);
195    x ^= x >> 32;
196    x
197}
198
199#[inline]
200pub fn stripes_with_tail(block: &[u8]) -> (&[[u8; 64]], &[u8]) {
201    match block.bp_as_chunks() {
202        ([stripes @ .., last], []) => (stripes, last),
203        (stripes, last) => (stripes, last),
204    }
205}
206
207/// This exists just to easily map the XXH3 algorithm to Rust as the
208/// algorithm describes 128-bit results as a pair of high and low u64
209/// values.
210#[derive(Copy, Clone)]
211pub(crate) struct X128 {
212    pub low: u64,
213    pub high: u64,
214}
215
216impl From<X128> for u128 {
217    fn from(value: X128) -> Self {
218        value.high.into_u128() << 64 | value.low.into_u128()
219    }
220}
221
222impl crate::IntoU128 for X128 {
223    fn into_u128(self) -> u128 {
224        self.into()
225    }
226}
227
228pub trait Halves {
229    type Output;
230
231    fn upper_half(self) -> Self::Output;
232    fn lower_half(self) -> Self::Output;
233}
234
235impl Halves for u64 {
236    type Output = u32;
237
238    #[inline]
239    fn upper_half(self) -> Self::Output {
240        (self >> 32) as _
241    }
242
243    #[inline]
244    fn lower_half(self) -> Self::Output {
245        self as _
246    }
247}
248
249impl Halves for u128 {
250    type Output = u64;
251
252    #[inline]
253    fn upper_half(self) -> Self::Output {
254        (self >> 64) as _
255    }
256
257    #[inline]
258    fn lower_half(self) -> Self::Output {
259        self as _
260    }
261}
262
263pub trait U8SliceExt {
264    fn first_u32(&self) -> Option<u32>;
265
266    fn last_u32(&self) -> Option<u32>;
267
268    fn first_u64(&self) -> Option<u64>;
269
270    fn last_u64(&self) -> Option<u64>;
271}
272
273impl U8SliceExt for [u8] {
274    #[inline]
275    fn first_u32(&self) -> Option<u32> {
276        self.first_chunk().copied().map(u32::from_le_bytes)
277    }
278
279    #[inline]
280    fn last_u32(&self) -> Option<u32> {
281        self.last_chunk().copied().map(u32::from_le_bytes)
282    }
283
284    #[inline]
285    fn first_u64(&self) -> Option<u64> {
286        self.first_chunk().copied().map(u64::from_le_bytes)
287    }
288
289    #[inline]
290    fn last_u64(&self) -> Option<u64> {
291        self.last_chunk().copied().map(u64::from_le_bytes)
292    }
293}
294
295pub trait SliceBackport<T> {
296    fn bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]);
297
298    fn bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]);
299
300    fn bp_as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]);
301}
302
303impl<T> SliceBackport<T> for [T] {
304    fn bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
305        assert_ne!(N, 0);
306        let len = self.len() / N;
307        // Safety: `(len / N) * N` has to be less-than-or-equal to `len`
308        let (head, tail) = unsafe { self.split_at_unchecked(len * N) };
309        // Safety: (1) `head` points to valid data, (2) the alignment
310        // of an array and the individual type are the same, (3) the
311        // valid elements are less-than-or-equal to the original
312        // slice.
313        let head = unsafe { slice::from_raw_parts(head.as_ptr().cast(), len) };
314        (head, tail)
315    }
316
317    fn bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
318        assert_ne!(N, 0);
319        let len = self.len() / N;
320        // Safety: `(len / N) * N` has to be less than or equal to `len`
321        let (head, tail) = unsafe { self.split_at_mut_unchecked(len * N) };
322        // Safety: (1) `head` points to valid data, (2) the alignment
323        // of an array and the individual type are the same, (3) the
324        // valid elements are less-than-or-equal to the original
325        // slice.
326        let head = unsafe { slice::from_raw_parts_mut(head.as_mut_ptr().cast(), len) };
327        (head, tail)
328    }
329
330    fn bp_as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) {
331        assert_ne!(N, 0);
332        let len = self.len() / N;
333        // Safety: `(len / N) * N` has to be less than or equal to `len`
334        let (head, tail) = unsafe { self.split_at_unchecked(self.len() - len * N) };
335        // Safety: (1) `tail` points to valid data, (2) the alignment
336        // of an array and the individual type are the same, (3) the
337        // valid elements are less-than-or-equal to the original
338        // slice.
339        let tail = unsafe { slice::from_raw_parts(tail.as_ptr().cast(), len) };
340        (head, tail)
341    }
342}
343
344#[cfg(test)]
345pub mod test {
346    use std::array;
347
348    use super::*;
349
350    macro_rules! bytes {
351        ($($n: literal),* $(,)?) => {
352            &[$(&crate::xxhash3::test::gen_bytes::<$n>() as &[u8],)*] as &[&[u8]]
353        };
354    }
355    pub(crate) use bytes;
356
357    pub fn gen_bytes<const N: usize>() -> [u8; N] {
358        // Picking 251 as it's a prime number, which will hopefully
359        // help avoid incidental power-of-two alignment.
360        array::from_fn(|i| (i % 251) as u8)
361    }
362
363    #[test]
364    fn default_secret_is_valid() {
365        assert!(DEFAULT_SECRET.is_valid());
366    }
367
368    #[test]
369    fn backported_as_chunks() {
370        let x = [1, 2, 3, 4, 5];
371
372        let (a, b) = x.bp_as_chunks::<1>();
373        assert_eq!(a, &[[1], [2], [3], [4], [5]]);
374        assert_eq!(b, &[] as &[i32]);
375
376        let (a, b) = x.bp_as_chunks::<2>();
377        assert_eq!(a, &[[1, 2], [3, 4]]);
378        assert_eq!(b, &[5]);
379
380        let (a, b) = x.bp_as_chunks::<3>();
381        assert_eq!(a, &[[1, 2, 3]]);
382        assert_eq!(b, &[4, 5]);
383
384        let (a, b) = x.bp_as_chunks::<4>();
385        assert_eq!(a, &[[1, 2, 3, 4]]);
386        assert_eq!(b, &[5]);
387
388        let (a, b) = x.bp_as_chunks::<5>();
389        assert_eq!(a, &[[1, 2, 3, 4, 5]]);
390        assert_eq!(b, &[] as &[i32]);
391
392        let (a, b) = x.bp_as_chunks::<6>();
393        assert_eq!(a, &[] as &[[i32; 6]]);
394        assert_eq!(b, &[1, 2, 3, 4, 5]);
395    }
396
397    #[test]
398    fn backported_as_rchunks() {
399        let x = [1, 2, 3, 4, 5];
400
401        let (a, b) = x.bp_as_rchunks::<1>();
402        assert_eq!(a, &[] as &[i32]);
403        assert_eq!(b, &[[1], [2], [3], [4], [5]]);
404
405        let (a, b) = x.bp_as_rchunks::<2>();
406        assert_eq!(a, &[1]);
407        assert_eq!(b, &[[2, 3], [4, 5]]);
408
409        let (a, b) = x.bp_as_rchunks::<3>();
410        assert_eq!(a, &[1, 2]);
411        assert_eq!(b, &[[3, 4, 5]]);
412
413        let (a, b) = x.bp_as_rchunks::<4>();
414        assert_eq!(a, &[1]);
415        assert_eq!(b, &[[2, 3, 4, 5]]);
416
417        let (a, b) = x.bp_as_rchunks::<5>();
418        assert_eq!(a, &[] as &[i32]);
419        assert_eq!(b, &[[1, 2, 3, 4, 5]]);
420
421        let (a, b) = x.bp_as_rchunks::<6>();
422        assert_eq!(a, &[1, 2, 3, 4, 5]);
423        assert_eq!(b, &[] as &[[i32; 6]]);
424    }
425}
twox_hash/xxhash3.rs

twox_hash/
xxhash3.rs
