1 use core::slice;
2
3 use crate::{IntoU128 as _, IntoU32 as _};
4
5 pub mod large;
6
7 pub(crate) use large::dispatch;
8 pub use large::{Algorithm, Vector};
9
10 pub mod secret;
11
12 pub use secret::{Secret, SECRET_MINIMUM_LENGTH};
13
14 mod streaming;
15
16 pub use streaming::{
17 Finalize, FixedBuffer, FixedMutBuffer, RawHasherCore, SecretBuffer, SecretTooShortError,
18 SecretWithSeedError,
19 };
20
21 #[cfg(feature = "alloc")]
22 pub use streaming::AllocRawHasher;
23
24 pub 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
37 pub const CUTOFF: usize = 240;
38
39 pub const DEFAULT_SEED: u64 = 0;
40
41 /// The length of the default secret.
42 pub const DEFAULT_SECRET_LENGTH: usize = 192;
43
44 pub type DefaultSecret = [u8; DEFAULT_SECRET_LENGTH];
45
46 pub 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
62 pub 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]
derive_secret(seed: u64, secret: &mut DefaultSecret)69 pub 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)]
92 pub struct OneshotWithSecretError(pub(crate) secret::Error);
93
94 impl core::error::Error for OneshotWithSecretError {}
95
96 impl core::fmt::Display for OneshotWithSecretError {
fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result97 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
98 self.0.fmt(f)
99 }
100 }
101
102 macro_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 }
111 pub(crate) use assert_input_range;
112
113 #[inline(always)]
impl_1_to_3_bytes_combined(input: &[u8]) -> u32114 pub 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]
impl_17_to_128_bytes_iter( secret: &Secret, input: &[u8], mut f: impl FnMut(&[u8; 16], &[u8; 16], &[[u8; 16]; 2]), )125 pub 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]
mix_step(data: &[u8; 16], secret: &[u8; 16], seed: u64) -> u64153 pub 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]
to_u64s(bytes: &[u8; 16]) -> [u64; 2]168 pub 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")]
pairs_of_u64_bytes(bytes: &[u8]) -> &[[[u8; 16]; 2]]175 pub 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]
avalanche(mut x: u64) -> u64182 pub 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]
avalanche_xxh64(mut x: u64) -> u64190 pub 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]
stripes_with_tail(block: &[u8]) -> (&[[u8; 64]], &[u8])200 pub 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)]
211 pub(crate) struct X128 {
212 pub low: u64,
213 pub high: u64,
214 }
215
216 impl From<X128> for u128 {
from(value: X128) -> Self217 fn from(value: X128) -> Self {
218 value.high.into_u128() << 64 | value.low.into_u128()
219 }
220 }
221
222 impl crate::IntoU128 for X128 {
into_u128(self) -> u128223 fn into_u128(self) -> u128 {
224 self.into()
225 }
226 }
227
228 pub trait Halves {
229 type Output;
230
upper_half(self) -> Self::Output231 fn upper_half(self) -> Self::Output;
lower_half(self) -> Self::Output232 fn lower_half(self) -> Self::Output;
233 }
234
235 impl Halves for u64 {
236 type Output = u32;
237
238 #[inline]
upper_half(self) -> Self::Output239 fn upper_half(self) -> Self::Output {
240 (self >> 32) as _
241 }
242
243 #[inline]
lower_half(self) -> Self::Output244 fn lower_half(self) -> Self::Output {
245 self as _
246 }
247 }
248
249 impl Halves for u128 {
250 type Output = u64;
251
252 #[inline]
upper_half(self) -> Self::Output253 fn upper_half(self) -> Self::Output {
254 (self >> 64) as _
255 }
256
257 #[inline]
lower_half(self) -> Self::Output258 fn lower_half(self) -> Self::Output {
259 self as _
260 }
261 }
262
263 pub trait U8SliceExt {
first_u32(&self) -> Option<u32>264 fn first_u32(&self) -> Option<u32>;
265
last_u32(&self) -> Option<u32>266 fn last_u32(&self) -> Option<u32>;
267
first_u64(&self) -> Option<u64>268 fn first_u64(&self) -> Option<u64>;
269
last_u64(&self) -> Option<u64>270 fn last_u64(&self) -> Option<u64>;
271 }
272
273 impl U8SliceExt for [u8] {
274 #[inline]
first_u32(&self) -> Option<u32>275 fn first_u32(&self) -> Option<u32> {
276 self.first_chunk().copied().map(u32::from_le_bytes)
277 }
278
279 #[inline]
last_u32(&self) -> Option<u32>280 fn last_u32(&self) -> Option<u32> {
281 self.last_chunk().copied().map(u32::from_le_bytes)
282 }
283
284 #[inline]
first_u64(&self) -> Option<u64>285 fn first_u64(&self) -> Option<u64> {
286 self.first_chunk().copied().map(u64::from_le_bytes)
287 }
288
289 #[inline]
last_u64(&self) -> Option<u64>290 fn last_u64(&self) -> Option<u64> {
291 self.last_chunk().copied().map(u64::from_le_bytes)
292 }
293 }
294
295 pub trait SliceBackport<T> {
bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T])296 fn bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]);
297
bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T])298 fn bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]);
299
bp_as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]])300 fn bp_as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]);
301 }
302
303 impl<T> SliceBackport<T> for [T] {
bp_as_chunks<const N: usize>(&self) -> (&[[T; N]], &[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
bp_as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T])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
bp_as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]])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)]
345 pub 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
gen_bytes<const N: usize>() -> [u8; N]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]
default_secret_is_valid()364 fn default_secret_is_valid() {
365 assert!(DEFAULT_SECRET.is_valid())
366 }
367
368 #[test]
backported_as_chunks()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]
backported_as_rchunks()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 }
426