1//! The in-progress XXH3 algorithm.
2//!
3//! Please read [the notes in original implementation][warning] to
4//! learn about when to use these algorithms. Specifically, the
5//! version of code this crate reproduces says:
6//!
7//! > The algorithm is currently in development, meaning its return
8//! values might still change in future versions. However, the API
9//! is stable, and can be used in production, typically for
10//! generation of ephemeral hashes (produced and consumed in same
11//! session).
12//!
13//! [warning]: https://github.com/Cyan4973/xxHash#new-hash-algorithms
14
15use alloc::vec::Vec;
16
17use core::convert::TryInto;
18use core::hash::Hasher;
19use core::mem;
20use core::ops::{Deref, DerefMut};
21use core::slice;
22
23#[cfg(target_arch = "x86")]
24use core::arch::x86::*;
25#[cfg(target_arch = "x86_64")]
26use core::arch::x86_64::*;
27
28use cfg_if::cfg_if;
29use static_assertions::{const_assert, const_assert_eq};
30
31#[cfg(feature = "serialize")]
32use serde::{Deserialize, Serialize};
33
34use crate::sixty_four::{
35 PRIME_1 as PRIME64_1, PRIME_2 as PRIME64_2, PRIME_3 as PRIME64_3, PRIME_4 as PRIME64_4,
36 PRIME_5 as PRIME64_5,
37};
38use crate::thirty_two::{PRIME_1 as PRIME32_1, PRIME_2 as PRIME32_2, PRIME_3 as PRIME32_3};
39
40#[cfg(feature = "std")]
41pub use crate::std_support::xxh3::{RandomHashBuilder128, RandomHashBuilder64};
42
43#[inline(always)]
44pub fn hash64(data: &[u8]) -> u64 {
45 hash64_with_seed(data, seed:0)
46}
47
48#[inline(always)]
49pub fn hash64_with_seed(data: &[u8], seed: u64) -> u64 {
50 let len: usize = data.len();
51
52 if len <= 16 {
53 hash_len_0to16_64bits(data, len, &SECRET, seed)
54 } else if len <= 128 {
55 hash_len_17to128_64bits(data, len, &SECRET, seed)
56 } else if len <= MIDSIZE_MAX {
57 hash_len_129to240_64bits(data, len, &SECRET, seed)
58 } else {
59 hash_long_64bits_with_seed(data, len, seed)
60 }
61}
62
63#[inline(always)]
64pub fn hash64_with_secret(data: &[u8], secret: &[u8]) -> u64 {
65 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
66
67 let len: usize = data.len();
68
69 if len <= 16 {
70 hash_len_0to16_64bits(data, len, key:secret, seed:0)
71 } else if len <= 128 {
72 hash_len_17to128_64bits(data, len, secret, seed:0)
73 } else if len <= MIDSIZE_MAX {
74 hash_len_129to240_64bits(data, len, secret, seed:0)
75 } else {
76 hash_long_64bits_with_secret(data, len, secret)
77 }
78}
79
80#[inline(always)]
81pub fn hash128(data: &[u8]) -> u128 {
82 hash128_with_seed(data, seed:0)
83}
84
85#[inline(always)]
86pub fn hash128_with_seed(data: &[u8], seed: u64) -> u128 {
87 let len: usize = data.len();
88
89 if len <= 16 {
90 hash_len_0to16_128bits(data, len, &SECRET, seed)
91 } else if len <= 128 {
92 hash_len_17to128_128bits(data, len, &SECRET, seed)
93 } else if len <= MIDSIZE_MAX {
94 hash_len_129to240_128bits(data, len, &SECRET, seed)
95 } else {
96 hash_long_128bits_with_seed(data, len, seed)
97 }
98}
99
100#[inline(always)]
101pub fn hash128_with_secret(data: &[u8], secret: &[u8]) -> u128 {
102 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
103
104 let len: usize = data.len();
105
106 if len <= 16 {
107 hash_len_0to16_128bits(data, len, secret, seed:0)
108 } else if len <= 128 {
109 hash_len_17to128_128bits(data, len, secret, seed:0)
110 } else if len <= MIDSIZE_MAX {
111 hash_len_129to240_128bits(data, len, secret, seed:0)
112 } else {
113 hash_long_128bits_with_secret(data, len, secret)
114 }
115}
116
117/// Calculates the 64-bit hash.
118#[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
119#[derive(Clone, Default)]
120pub struct Hash64(State);
121
122impl Hash64 {
123 pub fn with_seed(seed: u64) -> Self {
124 Self(State::with_seed(seed))
125 }
126
127 pub fn with_secret<S: Into<Vec<u8>>>(secret: S) -> Self {
128 Self(State::with_secret(secret))
129 }
130}
131
132impl Hasher for Hash64 {
133 #[inline(always)]
134 fn finish(&self) -> u64 {
135 self.0.digest64()
136 }
137
138 #[inline(always)]
139 fn write(&mut self, bytes: &[u8]) {
140 self.0.update(input:bytes, AccWidth::Acc64Bits)
141 }
142}
143
144/// Calculates the 128-bit hash.
145#[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
146#[derive(Clone, Default)]
147pub struct Hash128(State);
148
149impl Hash128 {
150 pub fn with_seed(seed: u64) -> Self {
151 Self(State::with_seed(seed))
152 }
153
154 pub fn with_secret<S: Into<Vec<u8>>>(secret: S) -> Self {
155 Self(State::with_secret(secret))
156 }
157}
158
159impl Hasher for Hash128 {
160 #[inline(always)]
161 fn finish(&self) -> u64 {
162 self.0.digest128() as u64
163 }
164
165 #[inline(always)]
166 fn write(&mut self, bytes: &[u8]) {
167 self.0.update(input:bytes, AccWidth::Acc128Bits)
168 }
169}
170
171pub trait HasherExt: Hasher {
172 fn finish_ext(&self) -> u128;
173}
174
175impl HasherExt for Hash128 {
176 #[inline(always)]
177 fn finish_ext(&self) -> u128 {
178 self.0.digest128()
179 }
180}
181
182/* ==========================================
183 * XXH3 default settings
184 * ========================================== */
185
186const SECRET_DEFAULT_SIZE: usize = 192;
187const SECRET_SIZE_MIN: usize = 136;
188
189const SECRET: Secret = Secret([
190 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
191 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
192 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
193 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
194 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
195 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
196 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
197 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
198 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
199 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
200 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
201 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
202]);
203
204#[repr(align(64))]
205#[derive(Clone)]
206struct Secret([u8; SECRET_DEFAULT_SIZE]);
207
208const_assert_eq!(mem::size_of::<Secret>() % 16, 0);
209
210impl Default for Secret {
211 #[inline(always)]
212 fn default() -> Self {
213 SECRET
214 }
215}
216
217impl Deref for Secret {
218 type Target = [u8];
219
220 #[inline(always)]
221 fn deref(&self) -> &Self::Target {
222 &self.0[..]
223 }
224}
225
226cfg_if! {
227 if #[cfg(feature = "serialize")] {
228 impl Serialize for Secret {
229 fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
230 where
231 S: serde::Serializer,
232 {
233 serializer.serialize_bytes(self)
234 }
235 }
236
237 impl<'de> Deserialize<'de> for Secret {
238 fn deserialize<D>(deserializer: D) -> Result<Secret, D::Error>
239 where
240 D: serde::Deserializer<'de>,
241 {
242 deserializer.deserialize_bytes(SecretVisitor)
243 }
244 }
245
246 struct SecretVisitor;
247
248 impl<'de> serde::de::Visitor<'de> for SecretVisitor {
249 type Value = Secret;
250
251 fn expecting(&self, formatter: &mut core::fmt::Formatter) -> core::fmt::Result {
252 formatter.write_str("secret with a bytes array")
253 }
254
255 fn visit_bytes<E>(self, v: &[u8]) -> Result<Self::Value, E>
256 where
257 E: serde::de::Error,
258 {
259 if v.len() == SECRET_DEFAULT_SIZE {
260 let mut secret = [0; SECRET_DEFAULT_SIZE];
261
262 secret.copy_from_slice(v);
263
264 Ok(Secret(secret))
265 } else {
266 Err(E::custom("incomplete secret data"))
267 }
268 }
269 }
270 }
271}
272
273impl Secret {
274 #[inline(always)]
275 pub fn with_seed(seed: u64) -> Self {
276 let mut secret: [u8; 192] = [0; SECRET_DEFAULT_SIZE];
277
278 for off: usize in (0..SECRET_DEFAULT_SIZE).step_by(step:16) {
279 secret[off..].write_u64_le(SECRET[off..].read_u64_le().wrapping_add(seed));
280 secret[off + 8..].write_u64_le(SECRET[off + 8..].read_u64_le().wrapping_sub(seed));
281 }
282
283 Secret(secret)
284 }
285}
286
287cfg_if! {
288 if #[cfg(target_feature = "avx2")] {
289 #[repr(align(32))]
290 #[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
291 #[derive(Clone)]
292 struct Acc([u64; ACC_NB]);
293 } else if #[cfg(target_feature = "sse2")] {
294 #[repr(align(16))]
295 #[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
296 #[derive(Clone)]
297 struct Acc([u64; ACC_NB]);
298 } else {
299 #[repr(align(8))]
300 #[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
301 #[derive(Clone)]
302 struct Acc([u64; ACC_NB]);
303 }
304}
305
306const ACC_SIZE: usize = mem::size_of::<Acc>();
307
308const_assert_eq!(ACC_SIZE, 64);
309
310impl Default for Acc {
311 #[inline(always)]
312 fn default() -> Self {
313 Acc([
314 u64::from(PRIME32_3),
315 PRIME64_1,
316 PRIME64_2,
317 PRIME64_3,
318 PRIME64_4,
319 u64::from(PRIME32_2),
320 PRIME64_5,
321 u64::from(PRIME32_1),
322 ])
323 }
324}
325
326impl Deref for Acc {
327 type Target = [u64];
328
329 #[inline(always)]
330 fn deref(&self) -> &Self::Target {
331 &self.0
332 }
333}
334
335impl DerefMut for Acc {
336 #[inline(always)]
337 fn deref_mut(&mut self) -> &mut Self::Target {
338 &mut self.0
339 }
340}
341
342trait Buf {
343 fn read_u32_le(&self) -> u32;
344
345 fn read_u64_le(&self) -> u64;
346}
347
348trait BufMut {
349 fn write_u32_le(&mut self, n: u32);
350
351 fn write_u64_le(&mut self, n: u64);
352}
353
354impl Buf for [u8] {
355 #[inline(always)]
356 fn read_u32_le(&self) -> u32 {
357 let buf: &[u8] = &self[..mem::size_of::<u32>()];
358 u32::from_le_bytes(buf.try_into().unwrap())
359 }
360
361 #[inline(always)]
362 fn read_u64_le(&self) -> u64 {
363 let buf: &[u8] = &self[..mem::size_of::<u64>()];
364 u64::from_le_bytes(buf.try_into().unwrap())
365 }
366}
367
368impl BufMut for [u8] {
369 #[inline(always)]
370 fn write_u32_le(&mut self, n: u32) {
371 self[..mem::size_of::<u32>()].copy_from_slice(&n.to_le_bytes()[..]);
372 }
373
374 #[inline(always)]
375 fn write_u64_le(&mut self, n: u64) {
376 self[..mem::size_of::<u64>()].copy_from_slice(&n.to_le_bytes()[..]);
377 }
378}
379
380/* ==========================================
381 * Short keys
382 * ========================================== */
383
384#[inline(always)]
385fn hash_len_0to16_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64 {
386 debug_assert!(len <= 16);
387
388 if len > 8 {
389 hash_len_9to16_64bits(data, len, key, seed)
390 } else if len >= 4 {
391 hash_len_4to8_64bits(data, len, key, seed)
392 } else if len > 0 {
393 hash_len_1to3_64bits(data, len, key, seed)
394 } else {
395 0
396 }
397}
398
399#[inline(always)]
400fn hash_len_9to16_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64 {
401 debug_assert!((9..=16).contains(&len));
402
403 let ll1: u64 = data.read_u64_le() ^ key.read_u64_le().wrapping_add(seed);
404 let ll2: u64 = data[len - 8..].read_u64_le() ^ key[8..].read_u64_le().wrapping_sub(seed);
405 let acc: u64 = (len as u64)
406 .wrapping_add(ll1)
407 .wrapping_add(ll2)
408 .wrapping_add(mul128_fold64(ll1, ll2));
409
410 avalanche(h64:acc)
411}
412
413#[inline(always)]
414fn hash_len_4to8_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64 {
415 debug_assert!((4..=8).contains(&len));
416
417 let in1: u64 = u64::from(data.read_u32_le());
418 let in2: u64 = u64::from(data[len - 4..].read_u32_le());
419 let in64: u64 = in1.wrapping_add(in2 << 32);
420 let keyed: u64 = in64 ^ key.read_u64_le().wrapping_add(seed);
421 let mix64: u64 =
422 (len as u64).wrapping_add((keyed ^ (keyed >> 51)).wrapping_mul(u64::from(PRIME32_1)));
423
424 avalanche((mix64 ^ (mix64 >> 47)).wrapping_mul(PRIME64_2))
425}
426
427#[inline(always)]
428fn hash_len_1to3_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64 {
429 debug_assert!((1..=3).contains(&len));
430
431 let c1: u32 = u32::from(data[0]);
432 let c2: u32 = u32::from(data[len >> 1]);
433 let c3: u32 = u32::from(data[len - 1]);
434 let combined: u32 = c1 + (c2 << 8) + (c3 << 16) + ((len as u32) << 24);
435 let keyed: u64 = u64::from(combined) ^ u64::from(key.read_u32_le()).wrapping_add(seed);
436 let mixed: u64 = keyed.wrapping_mul(PRIME64_1);
437
438 avalanche(h64:mixed)
439}
440
441#[inline(always)]
442fn hash_len_17to128_64bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u64 {
443 debug_assert!((17..=128).contains(&len));
444 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
445
446 let mut acc = PRIME64_1.wrapping_mul(len as u64);
447
448 if len > 32 {
449 if len > 64 {
450 if len > 96 {
451 acc = acc
452 .wrapping_add(mix_16bytes(&data[48..], &secret[96..], seed))
453 .wrapping_add(mix_16bytes(&data[len - 64..], &secret[112..], seed));
454 }
455 acc = acc
456 .wrapping_add(mix_16bytes(&data[32..], &secret[64..], seed))
457 .wrapping_add(mix_16bytes(&data[len - 48..], &secret[80..], seed));
458 }
459
460 acc = acc
461 .wrapping_add(mix_16bytes(&data[16..], &secret[32..], seed))
462 .wrapping_add(mix_16bytes(&data[len - 32..], &secret[48..], seed));
463 }
464
465 acc = acc
466 .wrapping_add(mix_16bytes(data, secret, seed))
467 .wrapping_add(mix_16bytes(&data[len - 16..], &secret[16..], seed));
468
469 avalanche(acc)
470}
471
472const MIDSIZE_MAX: usize = 240;
473const MIDSIZE_STARTOFFSET: usize = 3;
474const MIDSIZE_LASTOFFSET: usize = 17;
475
476#[inline(always)]
477fn hash_len_129to240_64bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u64 {
478 debug_assert!((129..=MIDSIZE_MAX).contains(&len));
479 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
480
481 let acc = (len as u64).wrapping_mul(PRIME64_1);
482 let acc = (0..8).fold(acc, |acc, i| {
483 acc.wrapping_add(mix_16bytes(&data[16 * i..], &secret[16 * i..], seed))
484 });
485 let acc = avalanche(acc);
486
487 let nb_rounds = len / 16;
488 debug_assert!(nb_rounds >= 8);
489
490 let acc = (8..nb_rounds).fold(acc, |acc, i| {
491 acc.wrapping_add(mix_16bytes(
492 &data[16 * i..],
493 &secret[16 * (i - 8) + MIDSIZE_STARTOFFSET..],
494 seed,
495 ))
496 });
497
498 avalanche(acc.wrapping_add(mix_16bytes(
499 &data[len - 16..],
500 &secret[SECRET_SIZE_MIN - MIDSIZE_LASTOFFSET..],
501 seed,
502 )))
503}
504
505/* ==========================================
506 * Long keys
507 * ========================================== */
508
509const STRIPE_LEN: usize = 64;
510const SECRET_CONSUME_RATE: usize = 8; // nb of secret bytes consumed at each accumulation
511const SECRET_MERGEACCS_START: usize = 11; // do not align on 8, so that secret is different from accumulator
512const SECRET_LASTACC_START: usize = 7; // do not align on 8, so that secret is different from scrambler
513const ACC_NB: usize = STRIPE_LEN / mem::size_of::<u64>();
514
515#[derive(Debug, Clone, Copy, PartialEq)]
516pub(crate) enum AccWidth {
517 Acc64Bits,
518 Acc128Bits,
519}
520
521#[inline(always)]
522fn hash_long_64bits_with_default_secret(data: &[u8], len: usize) -> u64 {
523 hash_long_internal(data, len, &SECRET)
524}
525
526#[inline(always)]
527fn hash_long_64bits_with_secret(data: &[u8], len: usize, secret: &[u8]) -> u64 {
528 hash_long_internal(data, len, secret)
529}
530
531/// Generate a custom key, based on alteration of default kSecret with the seed,
532/// and then use this key for long mode hashing.
533///
534/// This operation is decently fast but nonetheless costs a little bit of time.
535/// Try to avoid it whenever possible (typically when `seed.is_none()`).
536#[inline(always)]
537fn hash_long_64bits_with_seed(data: &[u8], len: usize, seed: u64) -> u64 {
538 if seed == 0 {
539 hash_long_64bits_with_default_secret(data, len)
540 } else {
541 let secret: Secret = Secret::with_seed(seed);
542
543 hash_long_internal(data, len, &secret)
544 }
545}
546
547#[inline(always)]
548fn hash_long_internal(data: &[u8], len: usize, secret: &[u8]) -> u64 {
549 let mut acc: Acc = Acc::default();
550
551 hash_long_internal_loop(&mut acc, data, len, secret, AccWidth::Acc64Bits);
552
553 merge_accs(
554 &acc,
555 &secret[SECRET_MERGEACCS_START..],
556 (len as u64).wrapping_mul(PRIME64_1),
557 )
558}
559
560#[inline(always)]
561fn hash_long_internal_loop(
562 acc: &mut [u64],
563 data: &[u8],
564 len: usize,
565 secret: &[u8],
566 acc_width: AccWidth,
567) {
568 let secret_len = secret.len();
569 let nb_rounds = (secret_len - STRIPE_LEN) / SECRET_CONSUME_RATE;
570 let block_len = STRIPE_LEN * nb_rounds;
571
572 debug_assert!(secret_len >= SECRET_SIZE_MIN);
573
574 let mut chunks = data.chunks_exact(block_len);
575
576 for chunk in &mut chunks {
577 accumulate(acc, chunk, secret, nb_rounds, acc_width);
578 unsafe {
579 scramble_acc(acc, &secret[secret_len - STRIPE_LEN..]);
580 }
581 }
582
583 /* last partial block */
584 debug_assert!(len > STRIPE_LEN);
585
586 let nb_stripes = (len % block_len) / STRIPE_LEN;
587
588 debug_assert!(nb_stripes < (secret_len / SECRET_CONSUME_RATE));
589
590 accumulate(acc, chunks.remainder(), secret, nb_stripes, acc_width);
591
592 /* last stripe */
593 if (len & (STRIPE_LEN - 1)) != 0 {
594 unsafe {
595 accumulate512(
596 acc,
597 &data[len - STRIPE_LEN..],
598 &secret[secret_len - STRIPE_LEN - SECRET_LASTACC_START..],
599 acc_width,
600 );
601 }
602 }
603}
604
605#[inline(always)]
606fn accumulate(acc: &mut [u64], data: &[u8], secret: &[u8], nb_stripes: usize, acc_width: AccWidth) {
607 for n: usize in 0..nb_stripes {
608 unsafe {
609 accumulate512(
610 acc,
611 &data[n * STRIPE_LEN..],
612 &secret[n * SECRET_CONSUME_RATE..],
613 acc_width,
614 );
615 }
616 }
617}
618
619#[inline(always)]
620const fn _mm_shuffle(z: u32, y: u32, x: u32, w: u32) -> i32 {
621 ((z << 6) | (y << 4) | (x << 2) | w) as i32
622}
623
624#[cfg(target_feature = "avx2")]
625mod avx2 {
626 use super::*;
627
628 #[target_feature(enable = "avx2")]
629 pub(crate) unsafe fn accumulate512(
630 acc: &mut [u64],
631 data: &[u8],
632 keys: &[u8],
633 acc_width: AccWidth,
634 ) {
635 let xacc = acc.as_mut_ptr() as *mut __m256i;
636 let xdata = data.as_ptr() as *const __m256i;
637 let xkey = keys.as_ptr() as *const __m256i;
638
639 for i in 0..STRIPE_LEN / mem::size_of::<__m256i>() {
640 let d = _mm256_loadu_si256(xdata.add(i));
641 let k = _mm256_loadu_si256(xkey.add(i));
642 let dk = _mm256_xor_si256(d, k); // uint32 dk[8] = {d0+k0, d1+k1, d2+k2, d3+k3, ...}
643 let mul = _mm256_mul_epu32(dk, _mm256_shuffle_epi32(dk, 0x31)); // uint64 res[4] = {dk0*dk1, dk2*dk3, ...}
644
645 xacc.add(i).write(if acc_width == AccWidth::Acc128Bits {
646 let dswap = _mm256_shuffle_epi32(d, _mm_shuffle(1, 0, 3, 2));
647 let add = _mm256_add_epi64(xacc.add(i).read(), dswap);
648 _mm256_add_epi64(mul, add)
649 } else {
650 let add = _mm256_add_epi64(xacc.add(i).read(), d);
651 _mm256_add_epi64(mul, add)
652 })
653 }
654 }
655
656 #[target_feature(enable = "avx2")]
657 pub unsafe fn scramble_acc(acc: &mut [u64], key: &[u8]) {
658 let xacc = acc.as_mut_ptr() as *mut __m256i;
659 let xkey = key.as_ptr() as *const __m256i;
660 let prime32 = _mm256_set1_epi32(PRIME32_1 as i32);
661
662 for i in 0..STRIPE_LEN / mem::size_of::<__m256i>() {
663 let data = xacc.add(i).read();
664 let shifted = _mm256_srli_epi64(data, 47);
665 let data = _mm256_xor_si256(data, shifted);
666
667 let k = _mm256_loadu_si256(xkey.add(i));
668 let dk = _mm256_xor_si256(data, k); /* U32 dk[4] = {d0+k0, d1+k1, d2+k2, d3+k3} */
669 let dk1 = _mm256_mul_epu32(dk, prime32);
670
671 let d2 = _mm256_shuffle_epi32(dk, 0x31);
672 let dk2 = _mm256_mul_epu32(d2, prime32);
673 let dk2h = _mm256_slli_epi64(dk2, 32);
674
675 xacc.add(i).write(_mm256_add_epi64(dk1, dk2h));
676 }
677 }
678}
679
680#[cfg(all(target_feature = "sse2", not(target_feature = "avx2")))]
681mod sse2 {
682 use super::*;
683
684 #[target_feature(enable = "sse2")]
685 #[allow(clippy::cast_ptr_alignment)]
686 pub(crate) unsafe fn accumulate512(
687 acc: &mut [u64],
688 data: &[u8],
689 keys: &[u8],
690 acc_width: AccWidth,
691 ) {
692 let xacc = acc.as_mut_ptr() as *mut __m128i;
693 let xdata = data.as_ptr() as *const __m128i;
694 let xkey = keys.as_ptr() as *const __m128i;
695
696 for i in 0..STRIPE_LEN / mem::size_of::<__m128i>() {
697 let d = _mm_loadu_si128(xdata.add(i));
698 let k = _mm_loadu_si128(xkey.add(i));
699 let dk = _mm_xor_si128(d, k); // uint32 dk[4] = {d0+k0, d1+k1, d2+k2, d3+k3} */
700 let mul = _mm_mul_epu32(dk, _mm_shuffle_epi32(dk, 0x31)); // uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */
701 xacc.add(i).write(if acc_width == AccWidth::Acc128Bits {
702 let dswap = _mm_shuffle_epi32(d, _mm_shuffle(1, 0, 3, 2));
703 let add = _mm_add_epi64(xacc.add(i).read(), dswap);
704 _mm_add_epi64(mul, add)
705 } else {
706 let add = _mm_add_epi64(xacc.add(i).read(), d);
707 _mm_add_epi64(mul, add)
708 })
709 }
710 }
711
712 #[target_feature(enable = "sse2")]
713 #[allow(clippy::cast_ptr_alignment)]
714 pub unsafe fn scramble_acc(acc: &mut [u64], key: &[u8]) {
715 let xacc = acc.as_mut_ptr() as *mut __m128i;
716 let xkey = key.as_ptr() as *const __m128i;
717 let prime32 = _mm_set1_epi32(PRIME32_1 as i32);
718
719 for i in 0..STRIPE_LEN / mem::size_of::<__m128i>() {
720 let data = xacc.add(i).read();
721 let shifted = _mm_srli_epi64(data, 47);
722 let data = _mm_xor_si128(data, shifted);
723
724 let k = _mm_loadu_si128(xkey.add(i));
725 let dk = _mm_xor_si128(data, k);
726
727 let dk1 = _mm_mul_epu32(dk, prime32);
728
729 let d2 = _mm_shuffle_epi32(dk, 0x31);
730 let dk2 = _mm_mul_epu32(d2, prime32);
731 let dk2h = _mm_slli_epi64(dk2, 32);
732
733 xacc.add(i).write(_mm_add_epi64(dk1, dk2h));
734 }
735 }
736}
737
738#[cfg(not(any(target_feature = "avx2", target_feature = "sse2")))]
739mod generic {
740 use super::*;
741
742 #[inline(always)]
743 pub(crate) unsafe fn accumulate512(
744 acc: &mut [u64],
745 data: &[u8],
746 key: &[u8],
747 acc_width: AccWidth,
748 ) {
749 for i in (0..ACC_NB).step_by(2) {
750 let in1 = data[8 * i..].read_u64_le();
751 let in2 = data[8 * (i + 1)..].read_u64_le();
752 let key1 = key[8 * i..].read_u64_le();
753 let key2 = key[8 * (i + 1)..].read_u64_le();
754 let data_key1 = key1 ^ in1;
755 let data_key2 = key2 ^ in2;
756 acc[i] = acc[i].wrapping_add(mul32_to64(data_key1, data_key1 >> 32));
757 acc[i + 1] = acc[i + 1].wrapping_add(mul32_to64(data_key2, data_key2 >> 32));
758
759 if acc_width == AccWidth::Acc128Bits {
760 acc[i] = acc[i].wrapping_add(in2);
761 acc[i + 1] = acc[i + 1].wrapping_add(in1);
762 } else {
763 acc[i] = acc[i].wrapping_add(in1);
764 acc[i + 1] = acc[i + 1].wrapping_add(in2);
765 }
766 }
767 }
768
769 #[inline(always)]
770 fn mul32_to64(a: u64, b: u64) -> u64 {
771 (a & 0xFFFFFFFF).wrapping_mul(b & 0xFFFFFFFF)
772 }
773
774 #[inline(always)]
775 pub unsafe fn scramble_acc(acc: &mut [u64], key: &[u8]) {
776 for i in 0..ACC_NB {
777 let key64 = key[8 * i..].read_u64_le();
778 let mut acc64 = acc[i];
779 acc64 ^= acc64 >> 47;
780 acc64 ^= key64;
781 acc64 = acc64.wrapping_mul(u64::from(PRIME32_1));
782 acc[i] = acc64;
783 }
784 }
785}
786
787cfg_if! {
788 if #[cfg(target_feature = "avx2")] {
789 use avx2::{accumulate512, scramble_acc};
790 } else if #[cfg(target_feature = "sse2")] {
791 use sse2::{accumulate512, scramble_acc};
792 } else {
793 use generic::{accumulate512, scramble_acc};
794 }
795}
796
797#[inline(always)]
798fn merge_accs(acc: &[u64], secret: &[u8], start: u64) -> u64 {
799 avalanche(
800 h64:start
801 .wrapping_add(mix2accs(acc, secret))
802 .wrapping_add(mix2accs(&acc[2..], &secret[16..]))
803 .wrapping_add(mix2accs(&acc[4..], &secret[32..]))
804 .wrapping_add(mix2accs(&acc[6..], &secret[48..])),
805 )
806}
807
808#[inline(always)]
809fn mix2accs(acc: &[u64], secret: &[u8]) -> u64 {
810 mul128_fold64(
811 ll1:acc[0] ^ secret.read_u64_le(),
812 ll2:acc[1] ^ secret[8..].read_u64_le(),
813 )
814}
815
816#[inline(always)]
817fn mix_16bytes(data: &[u8], key: &[u8], seed: u64) -> u64 {
818 let ll1: u64 = data.read_u64_le();
819 let ll2: u64 = data[8..].read_u64_le();
820
821 mul128_fold64(
822 ll1:ll1 ^ key.read_u64_le().wrapping_add(seed),
823 ll2:ll2 ^ key[8..].read_u64_le().wrapping_sub(seed),
824 )
825}
826
827#[inline(always)]
828fn mul128_fold64(ll1: u64, ll2: u64) -> u64 {
829 let lll: u128 = u128::from(ll1).wrapping_mul(u128::from(ll2));
830
831 (lll as u64) ^ ((lll >> 64) as u64)
832}
833
834#[inline(always)]
835fn avalanche(mut h64: u64) -> u64 {
836 h64 ^= h64 >> 37;
837 h64 = h64.wrapping_mul(PRIME64_3);
838 h64 ^ (h64 >> 32)
839}
840
841/* === XXH3 streaming === */
842
843const INTERNAL_BUFFER_SIZE: usize = 256;
844const INTERNAL_BUFFER_STRIPES: usize = INTERNAL_BUFFER_SIZE / STRIPE_LEN;
845
846const_assert!(INTERNAL_BUFFER_SIZE >= MIDSIZE_MAX);
847const_assert_eq!(INTERNAL_BUFFER_SIZE % STRIPE_LEN, 0);
848
849#[repr(align(64))]
850#[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
851#[derive(Clone)]
852struct State {
853 acc: Acc,
854 secret: With,
855 buf: Vec<u8>,
856 seed: u64,
857 total_len: usize,
858 nb_stripes_so_far: usize,
859}
860
861#[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
862#[derive(Clone)]
863enum With {
864 Default(Secret),
865 Custom(Secret),
866 Ref(Vec<u8>),
867}
868
869impl Deref for With {
870 type Target = [u8];
871
872 fn deref(&self) -> &Self::Target {
873 match self {
874 With::Default(secret: &Secret) | With::Custom(secret: &Secret) => &secret.0[..],
875 With::Ref(secret: &Vec) => secret,
876 }
877 }
878}
879
880impl Default for State {
881 fn default() -> Self {
882 Self::new(seed:0, secret:With::Default(Secret::default()))
883 }
884}
885
886impl State {
887 fn new(seed: u64, secret: With) -> Self {
888 State {
889 acc: Acc::default(),
890 secret,
891 buf: Vec::with_capacity(INTERNAL_BUFFER_SIZE),
892 seed,
893 total_len: 0,
894 nb_stripes_so_far: 0,
895 }
896 }
897
898 fn with_seed(seed: u64) -> Self {
899 Self::new(seed, With::Custom(Secret::with_seed(seed)))
900 }
901
902 fn with_secret<S: Into<Vec<u8>>>(secret: S) -> State {
903 let secret = secret.into();
904
905 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
906
907 Self::new(0, With::Ref(secret))
908 }
909
910 #[inline(always)]
911 fn secret_limit(&self) -> usize {
912 self.secret.len() - STRIPE_LEN
913 }
914
915 #[inline(always)]
916 fn nb_stripes_per_block(&self) -> usize {
917 self.secret_limit() / SECRET_CONSUME_RATE
918 }
919
920 #[inline(always)]
921 fn update(&mut self, mut input: &[u8], acc_width: AccWidth) {
922 let len = input.len();
923
924 if len == 0 {
925 return;
926 }
927
928 self.total_len += len;
929
930 if self.buf.len() + len <= self.buf.capacity() {
931 self.buf.extend_from_slice(input);
932 return;
933 }
934
935 let nb_stripes_per_block = self.nb_stripes_per_block();
936 let secret_limit = self.secret_limit();
937
938 if !self.buf.is_empty() {
939 // some data within internal buffer: fill then consume it
940 let (load, rest) = input.split_at(self.buf.capacity() - self.buf.len());
941 self.buf.extend_from_slice(load);
942 input = rest;
943 self.nb_stripes_so_far = consume_stripes(
944 &mut self.acc,
945 self.nb_stripes_so_far,
946 nb_stripes_per_block,
947 &self.buf,
948 INTERNAL_BUFFER_STRIPES,
949 &self.secret,
950 secret_limit,
951 acc_width,
952 );
953 self.buf.clear();
954 }
955
956 // consume input by full buffer quantities
957 let mut chunks = input.chunks_exact(INTERNAL_BUFFER_SIZE);
958
959 for chunk in &mut chunks {
960 self.nb_stripes_so_far = consume_stripes(
961 &mut self.acc,
962 self.nb_stripes_so_far,
963 nb_stripes_per_block,
964 chunk,
965 INTERNAL_BUFFER_STRIPES,
966 &self.secret,
967 secret_limit,
968 acc_width,
969 );
970 }
971
972 // some remaining input data : buffer it
973 self.buf.extend_from_slice(chunks.remainder())
974 }
975
976 #[inline(always)]
977 fn digest_long(&self, acc_width: AccWidth) -> Acc {
978 let mut acc = self.acc.clone();
979 let secret_limit = self.secret_limit();
980
981 if self.buf.len() >= STRIPE_LEN {
982 // digest locally, state remains unaltered, and can continue ingesting more data afterwards
983 let total_nb_stripes = self.buf.len() / STRIPE_LEN;
984 let _nb_stripes_so_far = consume_stripes(
985 &mut acc,
986 self.nb_stripes_so_far,
987 self.nb_stripes_per_block(),
988 &self.buf,
989 total_nb_stripes,
990 &self.secret,
991 secret_limit,
992 acc_width,
993 );
994 if (self.buf.len() % STRIPE_LEN) != 0 {
995 unsafe {
996 accumulate512(
997 &mut acc,
998 &self.buf[self.buf.len() - STRIPE_LEN..],
999 &self.secret[secret_limit - SECRET_LASTACC_START..],
1000 acc_width,
1001 );
1002 }
1003 }
1004 } else if !self.buf.is_empty() {
1005 // one last stripe
1006 let mut last_stripe = [0u8; STRIPE_LEN];
1007 let catchup_size = STRIPE_LEN - self.buf.len();
1008
1009 last_stripe[..catchup_size].copy_from_slice(unsafe {
1010 slice::from_raw_parts(
1011 self.buf.as_ptr().add(self.buf.capacity() - catchup_size),
1012 catchup_size,
1013 )
1014 });
1015 last_stripe[catchup_size..].copy_from_slice(&self.buf);
1016
1017 unsafe {
1018 accumulate512(
1019 &mut acc,
1020 &last_stripe[..],
1021 &self.secret[secret_limit - SECRET_LASTACC_START..],
1022 acc_width,
1023 );
1024 }
1025 }
1026
1027 acc
1028 }
1029
1030 #[inline(always)]
1031 fn digest64(&self) -> u64 {
1032 if self.total_len > MIDSIZE_MAX {
1033 let acc = self.digest_long(AccWidth::Acc64Bits);
1034
1035 merge_accs(
1036 &acc,
1037 &self.secret[SECRET_MERGEACCS_START..],
1038 (self.total_len as u64).wrapping_mul(PRIME64_1),
1039 )
1040 } else if self.seed != 0 {
1041 hash64_with_seed(&self.buf, self.seed)
1042 } else {
1043 hash64_with_secret(&self.buf, &self.secret[..self.secret_limit() + STRIPE_LEN])
1044 }
1045 }
1046
1047 #[inline(always)]
1048 fn digest128(&self) -> u128 {
1049 let secret_limit = self.secret_limit();
1050
1051 if self.total_len > MIDSIZE_MAX {
1052 let acc = self.digest_long(AccWidth::Acc128Bits);
1053
1054 debug_assert!(secret_limit + STRIPE_LEN >= ACC_SIZE + SECRET_MERGEACCS_START);
1055
1056 let total_len = self.total_len as u64;
1057
1058 let low64 = merge_accs(
1059 &acc,
1060 &self.secret[SECRET_MERGEACCS_START..],
1061 total_len.wrapping_mul(PRIME64_1),
1062 );
1063 let high64 = merge_accs(
1064 &acc,
1065 &self.secret[secret_limit + STRIPE_LEN - ACC_SIZE - SECRET_MERGEACCS_START..],
1066 !total_len.wrapping_mul(PRIME64_2),
1067 );
1068
1069 u128::from(low64) + (u128::from(high64) << 64)
1070 } else if self.seed != 0 {
1071 hash128_with_seed(&self.buf, self.seed)
1072 } else {
1073 hash128_with_secret(&self.buf, &self.secret[..secret_limit + STRIPE_LEN])
1074 }
1075 }
1076}
1077
1078#[inline(always)]
1079#[allow(clippy::too_many_arguments)]
1080fn consume_stripes(
1081 acc: &mut [u64],
1082 nb_stripes_so_far: usize,
1083 nb_stripes_per_block: usize,
1084 data: &[u8],
1085 total_stripes: usize,
1086 secret: &[u8],
1087 secret_limit: usize,
1088 acc_width: AccWidth,
1089) -> usize {
1090 debug_assert!(nb_stripes_so_far < nb_stripes_per_block);
1091
1092 if nb_stripes_per_block - nb_stripes_so_far <= total_stripes {
1093 let nb_stripes = nb_stripes_per_block - nb_stripes_so_far;
1094
1095 accumulate(
1096 acc,
1097 data,
1098 &secret[nb_stripes_so_far * SECRET_CONSUME_RATE..],
1099 nb_stripes,
1100 acc_width,
1101 );
1102 unsafe {
1103 scramble_acc(acc, &secret[secret_limit..]);
1104 }
1105 accumulate(
1106 acc,
1107 &data[nb_stripes * STRIPE_LEN..],
1108 secret,
1109 total_stripes - nb_stripes,
1110 acc_width,
1111 );
1112
1113 total_stripes - nb_stripes
1114 } else {
1115 accumulate(
1116 acc,
1117 data,
1118 &secret[nb_stripes_so_far * SECRET_CONSUME_RATE..],
1119 total_stripes,
1120 acc_width,
1121 );
1122
1123 nb_stripes_so_far + total_stripes
1124 }
1125}
1126
1127/* ==========================================
1128 * XXH3 128 bits (=> XXH128)
1129 * ========================================== */
1130
1131#[inline(always)]
1132fn hash_len_0to16_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u128 {
1133 debug_assert!(len <= 16);
1134
1135 if len > 8 {
1136 hash_len_9to16_128bits(data, len, key:secret, seed)
1137 } else if len >= 4 {
1138 hash_len_4to8_128bits(data, len, key:secret, seed)
1139 } else if len > 0 {
1140 hash_len_1to3_128bits(data, len, key:secret, seed)
1141 } else {
1142 0
1143 }
1144}
1145
1146#[inline(always)]
1147fn hash_len_1to3_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u128 {
1148 debug_assert!((1..=3).contains(&len));
1149
1150 let c1: u32 = u32::from(data[0]);
1151 let c2: u32 = u32::from(data[len >> 1]);
1152 let c3: u32 = u32::from(data[len - 1]);
1153 let combinedl: u32 = c1 + (c2 << 8) + (c3 << 16) + ((len as u32) << 24);
1154 let combinedh: u32 = combinedl.swap_bytes();
1155 let keyedl: u64 = u64::from(combinedl) ^ u64::from(key.read_u32_le()).wrapping_add(seed);
1156 let keyedh: u64 = u64::from(combinedh) ^ u64::from(key[4..].read_u32_le()).wrapping_sub(seed);
1157 let mixedl: u64 = keyedl.wrapping_mul(PRIME64_1);
1158 let mixedh: u64 = keyedh.wrapping_mul(PRIME64_2);
1159
1160 u128::from(avalanche(h64:mixedl)) + (u128::from(avalanche(h64:mixedh)) << 64)
1161}
1162
1163#[inline(always)]
1164fn hash_len_4to8_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u128 {
1165 debug_assert!((4..=8).contains(&len));
1166
1167 let in1: u64 = u64::from(data.read_u32_le());
1168 let in2: u64 = u64::from(data[len - 4..].read_u32_le());
1169 let in64l: u64 = in1.wrapping_add(in2 << 32);
1170 let in64h: u64 = in64l.swap_bytes();
1171 let keyedl: u64 = in64l ^ key.read_u64_le().wrapping_add(seed);
1172 let keyedh: u64 = in64h ^ key[8..].read_u64_le().wrapping_sub(seed);
1173 let mix64l1: u64 =
1174 (len as u64).wrapping_add((keyedl ^ (keyedl >> 51)).wrapping_mul(u64::from(PRIME32_1)));
1175 let mix64l2: u64 = (mix64l1 ^ (mix64l1 >> 47)).wrapping_mul(PRIME64_2);
1176 let mix64h1: u64 = (keyedh ^ (keyedh >> 47))
1177 .wrapping_mul(PRIME64_1)
1178 .wrapping_sub(len as u64);
1179 let mix64h2: u64 = (mix64h1 ^ (mix64h1 >> 43)).wrapping_mul(PRIME64_4);
1180
1181 u128::from(avalanche(h64:mix64l2)) + (u128::from(avalanche(h64:mix64h2)) << 64)
1182}
1183
1184#[inline(always)]
1185fn hash_len_9to16_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u128 {
1186 debug_assert!((9..=16).contains(&len));
1187
1188 let ll1: u64 = data.read_u64_le() ^ key.read_u64_le().wrapping_add(seed);
1189 let ll2: u64 = data[len - 8..].read_u64_le() ^ key[8..].read_u64_le().wrapping_sub(seed);
1190 let inlow: u64 = ll1 ^ ll2;
1191
1192 let m128: u128 = u128::from(inlow).wrapping_mul(u128::from(PRIME64_1));
1193 let high64: u64 = ((m128 >> 64) as u64).wrapping_add(ll2.wrapping_mul(PRIME64_1));
1194 let low64: u64 = (m128 as u64) ^ (high64 >> 32);
1195
1196 let h128: u128 = u128::from(low64).wrapping_mul(u128::from(PRIME64_2));
1197 let high64: u64 = ((h128 >> 64) as u64).wrapping_add(high64.wrapping_mul(PRIME64_2));
1198 let low64: u64 = h128 as u64;
1199
1200 u128::from(avalanche(h64:low64)) + (u128::from(avalanche(h64:high64)) << 64)
1201}
1202
1203#[inline(always)]
1204fn hash_len_17to128_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u128 {
1205 debug_assert!((17..=128).contains(&len));
1206 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
1207
1208 let mut acc1 = PRIME64_1.wrapping_mul(len as u64);
1209 let mut acc2 = 0u64;
1210
1211 if len > 32 {
1212 if len > 64 {
1213 if len > 96 {
1214 acc1 = acc1.wrapping_add(mix_16bytes(&data[48..], &secret[96..], seed));
1215 acc2 = acc2.wrapping_add(mix_16bytes(&data[len - 64..], &secret[112..], seed));
1216 }
1217 acc1 = acc1.wrapping_add(mix_16bytes(&data[32..], &secret[64..], seed));
1218 acc2 = acc2.wrapping_add(mix_16bytes(&data[len - 48..], &secret[80..], seed));
1219 }
1220
1221 acc1 = acc1.wrapping_add(mix_16bytes(&data[16..], &secret[32..], seed));
1222 acc2 = acc2.wrapping_add(mix_16bytes(&data[len - 32..], &secret[48..], seed));
1223 }
1224
1225 acc1 = acc1.wrapping_add(mix_16bytes(data, secret, seed));
1226 acc2 = acc2.wrapping_add(mix_16bytes(&data[len - 16..], &secret[16..], seed));
1227
1228 let low64 = acc1.wrapping_add(acc2);
1229 let high64 = acc1
1230 .wrapping_mul(PRIME64_1)
1231 .wrapping_add(acc2.wrapping_mul(PRIME64_4))
1232 .wrapping_add((len as u64).wrapping_sub(seed).wrapping_mul(PRIME64_2));
1233
1234 u128::from(avalanche(low64)) + (u128::from(0u64.wrapping_sub(avalanche(high64))) << 64)
1235}
1236
1237#[inline(always)]
1238fn hash_len_129to240_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u128 {
1239 debug_assert!((129..=MIDSIZE_MAX).contains(&len));
1240 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
1241
1242 let acc1 = (len as u64).wrapping_mul(PRIME64_1);
1243 let acc2 = 0u64;
1244
1245 let (acc1, acc2) = (0..4).fold((acc1, acc2), |(acc1, acc2), i| {
1246 (
1247 acc1.wrapping_add(mix_16bytes(&data[32 * i..], &secret[32 * i..], seed)),
1248 acc2.wrapping_add(mix_16bytes(
1249 &data[32 * i + 16..],
1250 &secret[32 * i + 16..],
1251 0u64.wrapping_sub(seed),
1252 )),
1253 )
1254 });
1255 let acc1 = avalanche(acc1);
1256 let acc2 = avalanche(acc2);
1257
1258 let nb_rounds = len / 32;
1259 debug_assert!(nb_rounds >= 4);
1260
1261 let (acc1, acc2) = (4..nb_rounds).fold((acc1, acc2), |(acc1, acc2), i| {
1262 (
1263 acc1.wrapping_add(mix_16bytes(
1264 &data[32 * i..],
1265 &secret[32 * (i - 4) + MIDSIZE_STARTOFFSET..],
1266 seed,
1267 )),
1268 acc2.wrapping_add(mix_16bytes(
1269 &data[32 * i + 16..],
1270 &secret[32 * (i - 4) + 16 + MIDSIZE_STARTOFFSET..],
1271 0u64.wrapping_sub(seed),
1272 )),
1273 )
1274 });
1275
1276 // last bytes
1277 let acc1 = acc1.wrapping_add(mix_16bytes(
1278 &data[len - 16..],
1279 &secret[SECRET_SIZE_MIN - MIDSIZE_LASTOFFSET..],
1280 seed,
1281 ));
1282 let acc2 = acc2.wrapping_add(mix_16bytes(
1283 &data[len - 32..],
1284 &secret[SECRET_SIZE_MIN - MIDSIZE_LASTOFFSET - 16..],
1285 0u64.wrapping_sub(seed),
1286 ));
1287
1288 let low64 = acc1.wrapping_add(acc2);
1289 let high64 = acc1
1290 .wrapping_mul(PRIME64_1)
1291 .wrapping_add(acc2.wrapping_mul(PRIME64_4))
1292 .wrapping_add((len as u64).wrapping_sub(seed).wrapping_mul(PRIME64_2));
1293
1294 u128::from(avalanche(low64)) + (u128::from(0u64.wrapping_sub(avalanche(high64))) << 64)
1295}
1296
1297#[inline]
1298fn hash_long_128bits_with_default_secret(data: &[u8], len: usize) -> u128 {
1299 hash_long_128bits_internal(data, len, &SECRET)
1300}
1301
1302#[inline]
1303fn hash_long_128bits_with_secret(data: &[u8], len: usize, secret: &[u8]) -> u128 {
1304 hash_long_128bits_internal(data, len, secret)
1305}
1306
1307#[inline]
1308fn hash_long_128bits_with_seed(data: &[u8], len: usize, seed: u64) -> u128 {
1309 if seed == 0 {
1310 hash_long_128bits_with_default_secret(data, len)
1311 } else {
1312 let secret: Secret = Secret::with_seed(seed);
1313
1314 hash_long_128bits_internal(data, len, &secret)
1315 }
1316}
1317
1318#[inline(always)]
1319fn hash_long_128bits_internal(data: &[u8], len: usize, secret: &[u8]) -> u128 {
1320 let mut acc: Acc = Acc::default();
1321
1322 hash_long_internal_loop(&mut acc, data, len, secret, AccWidth::Acc128Bits);
1323
1324 debug_assert!(secret.len() >= acc.len() + SECRET_MERGEACCS_START);
1325
1326 let low64: u64 = merge_accs(
1327 &acc,
1328 &secret[SECRET_MERGEACCS_START..],
1329 (len as u64).wrapping_mul(PRIME64_1),
1330 );
1331 let high64: u64 = merge_accs(
1332 &acc,
1333 &secret[secret.len() - ACC_SIZE - SECRET_MERGEACCS_START..],
1334 !(len as u64).wrapping_mul(PRIME64_2),
1335 );
1336
1337 u128::from(low64) + (u128::from(high64) << 64)
1338}
1339
1340/* === XXH3 128-bit streaming === */
1341
1342/* all the functions are actually the same as for 64-bit streaming variant,
1343just the reset one is different (different initial acc values for 0,5,6,7),
1344and near the end of the digest function */
1345
1346#[cfg(test)]
1347mod tests {
1348 use alloc::vec;
1349
1350 use super::*;
1351
1352 const PRIME: u64 = 2654435761;
1353 const PRIME64: u64 = 11400714785074694797;
1354 const SANITY_BUFFER_SIZE: usize = 2243;
1355
1356 fn sanity_buffer() -> [u8; SANITY_BUFFER_SIZE] {
1357 let mut buf = [0; SANITY_BUFFER_SIZE];
1358 let mut byte_gen: u64 = PRIME;
1359
1360 for b in buf.iter_mut() {
1361 *b = (byte_gen >> 56) as u8;
1362 byte_gen = byte_gen.wrapping_mul(PRIME64);
1363 }
1364
1365 buf
1366 }
1367
1368 #[test]
1369 fn hash_64bits_sanity_check() {
1370 let buf = sanity_buffer();
1371
1372 let test_cases = vec![
1373 (&[][..], 0, 0), /* zero-length hash is always 0 */
1374 (&[][..], PRIME64, 0),
1375 (&buf[..1], 0, 0x7198D737CFE7F386), /* 1 - 3 */
1376 (&buf[..1], PRIME64, 0xB70252DB7161C2BD), /* 1 - 3 */
1377 (&buf[..6], 0, 0x22CBF5F3E1F6257C), /* 4 - 8 */
1378 (&buf[..6], PRIME64, 0x6398631C12AB94CE), /* 4 - 8 */
1379 (&buf[..12], 0, 0xD5361CCEEBB5A0CC), /* 9 - 16 */
1380 (&buf[..12], PRIME64, 0xC4C125E75A808C3D), /* 9 - 16 */
1381 (&buf[..24], 0, 0x46796F3F78B20F6B), /* 17 - 32 */
1382 (&buf[..24], PRIME64, 0x60171A7CD0A44C10), /* 17 - 32 */
1383 (&buf[..48], 0, 0xD8D4D3590D136E11), /* 33 - 64 */
1384 (&buf[..48], PRIME64, 0x05441F2AEC2A1296), /* 33 - 64 */
1385 (&buf[..80], 0, 0xA1DC8ADB3145B86A), /* 65 - 96 */
1386 (&buf[..80], PRIME64, 0xC9D55256965B7093), /* 65 - 96 */
1387 (&buf[..112], 0, 0xE43E5717A61D3759), /* 97 -128 */
1388 (&buf[..112], PRIME64, 0x5A5F89A3FECE44A5), /* 97 -128 */
1389 (&buf[..195], 0, 0x6F747739CBAC22A5), /* 129-240 */
1390 (&buf[..195], PRIME64, 0x33368E23C7F95810), /* 129-240 */
1391 (&buf[..403], 0, 0x4834389B15D981E8), /* one block, last stripe is overlapping */
1392 (&buf[..403], PRIME64, 0x85CE5DFFC7B07C87), /* one block, last stripe is overlapping */
1393 (&buf[..512], 0, 0x6A1B982631F059A8), /* one block, finishing at stripe boundary */
1394 (&buf[..512], PRIME64, 0x10086868CF0ADC99), /* one block, finishing at stripe boundary */
1395 (&buf[..2048], 0, 0xEFEFD4449323CDD4), /* 2 blocks, finishing at block boundary */
1396 (&buf[..2048], PRIME64, 0x01C85E405ECA3F6E), /* 2 blocks, finishing at block boundary */
1397 (&buf[..2240], 0, 0x998C0437486672C7), /* 3 blocks, finishing at stripe boundary */
1398 (&buf[..2240], PRIME64, 0x4ED38056B87ABC7F), /* 3 blocks, finishing at stripe boundary */
1399 (&buf[..2243], 0, 0xA559D20581D742D3), /* 3 blocks, last stripe is overlapping */
1400 (&buf[..2243], PRIME64, 0x96E051AB57F21FC8), /* 3 blocks, last stripe is overlapping */
1401 ];
1402
1403 for (buf, seed, result) in test_cases {
1404 {
1405 let hash = hash64_with_seed(buf, seed);
1406
1407 assert_eq!(
1408 hash,
1409 result,
1410 "hash64_with_seed(&buf[..{}], seed={}) failed, got 0x{:X}, expected 0x{:X}",
1411 buf.len(),
1412 seed,
1413 hash,
1414 result
1415 );
1416 }
1417
1418 // streaming API test
1419
1420 // single ingestio
1421 {
1422 let mut hasher = Hash64::with_seed(seed);
1423 hasher.write(buf);
1424 let hash = hasher.finish();
1425
1426 assert_eq!(
1427 hash,
1428 result,
1429 "Hash64::update(&buf[..{}]) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1430 buf.len(),
1431 seed,
1432 hash,
1433 result
1434 );
1435 }
1436
1437 if buf.len() > 3 {
1438 // 2 ingestions
1439 let mut hasher = Hash64::with_seed(seed);
1440 hasher.write(&buf[..3]);
1441 hasher.write(&buf[3..]);
1442 let hash = hasher.finish();
1443
1444 assert_eq!(
1445 hash,
1446 result,
1447 "Hash64::update(&buf[..3], &buf[3..{}]) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1448 buf.len(),
1449 seed,
1450 hash,
1451 result
1452 );
1453 }
1454
1455 // byte by byte ingestion
1456 {
1457 let mut hasher = Hash64::with_seed(seed);
1458
1459 for chunk in buf.chunks(1) {
1460 hasher.write(chunk);
1461 }
1462
1463 let hash = hasher.finish();
1464
1465 assert_eq!(
1466 hash,
1467 result,
1468 "Hash64::update(&buf[..{}].chunks(1)) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1469 buf.len(),
1470 seed,
1471 hash,
1472 result
1473 );
1474 }
1475 }
1476 }
1477
1478 #[test]
1479 fn hash_64bits_with_secret_sanity_check() {
1480 let buf = sanity_buffer();
1481 let secret = &buf[7..7 + SECRET_SIZE_MIN + 11];
1482
1483 let test_cases = vec![
1484 (&[][..], secret, 0), /* zero-length hash is always 0 */
1485 (&buf[..1], secret, 0x7F69735D618DB3F0), /* 1 - 3 */
1486 (&buf[..6], secret, 0xBFCC7CB1B3554DCE), /* 6 - 8 */
1487 (&buf[..12], secret, 0x8C50DC90AC9206FC), /* 9 - 16 */
1488 (&buf[..24], secret, 0x1CD2C2EE9B9A0928), /* 17 - 32 */
1489 (&buf[..48], secret, 0xA785256D9D65D514), /* 33 - 64 */
1490 (&buf[..80], secret, 0x6F3053360D21BBB7), /* 65 - 96 */
1491 (&buf[..112], secret, 0x560E82D25684154C), /* 97 -128 */
1492 (&buf[..195], secret, 0xBA5BDDBC5A767B11), /* 129-240 */
1493 (&buf[..403], secret, 0xFC3911BBA656DB58), /* one block, last stripe is overlapping */
1494 (&buf[..512], secret, 0x306137DD875741F1), /* one block, finishing at stripe boundary */
1495 (&buf[..2048], secret, 0x2836B83880AD3C0C), /* > one block, at least one scrambling */
1496 (&buf[..2243], secret, 0x3446E248A00CB44A), /* > one block, at least one scrambling, last stripe unaligned */
1497 ];
1498
1499 for (buf, secret, result) in test_cases {
1500 {
1501 let hash = hash64_with_secret(buf, secret);
1502
1503 assert_eq!(
1504 hash,
1505 result,
1506 "hash64_with_secret(&buf[..{}], secret) failed, got 0x{:X}, expected 0x{:X}",
1507 buf.len(),
1508 hash,
1509 result
1510 );
1511 }
1512
1513 // streaming API test
1514
1515 // single ingestio
1516 {
1517 let mut hasher = Hash64::with_secret(secret);
1518 hasher.write(buf);
1519 let hash = hasher.finish();
1520
1521 assert_eq!(
1522 hash,
1523 result,
1524 "Hash64::update(&buf[..{}]) with secret failed, got 0x{:X}, expected 0x{:X}",
1525 buf.len(),
1526 hash,
1527 result
1528 );
1529 }
1530
1531 // byte by byte ingestion
1532 {
1533 let mut hasher = Hash64::with_secret(secret);
1534
1535 for chunk in buf.chunks(1) {
1536 hasher.write(chunk);
1537 }
1538
1539 let hash = hasher.finish();
1540
1541 assert_eq!(
1542 hash,
1543 result,
1544 "Hash64::update(&buf[..{}].chunks(1)) with secret failed, got 0x{:X}, expected 0x{:X}",
1545 buf.len(),
1546 hash,
1547 result
1548 );
1549 }
1550 }
1551 }
1552
1553 #[test]
1554 fn hash_128bits_sanity_check() {
1555 let buf = sanity_buffer();
1556
1557 let test_cases = vec![
1558 (&[][..], 0, 0u64, 0u64), /* zero-length hash is { seed, -seed } by default */
1559 (&[][..], PRIME, 0, 0),
1560 (&buf[..1], 0, 0x7198D737CFE7F386, 0x3EE70EA338F3F1E8), /* 1-3 */
1561 (&buf[..1], PRIME, 0x8E05996EC27C0F46, 0x90DFC659A8BDCC0C), /* 1-3 */
1562 (&buf[..6], 0, 0x22CBF5F3E1F6257C, 0xD4E6C2B94FFC3BFA), /* 4-8 */
1563 (&buf[..6], PRIME, 0x97B28D3079F8541F, 0xEFC0B954298E6555), /* 4-8 */
1564 (&buf[..12], 0, 0x0E0CD01F05AC2F0D, 0x2B55C95951070D4B), /* 9-16 */
1565 (&buf[..12], PRIME, 0xA9DE561CA04CDF37, 0x609E31FDC00A43C9), /* 9-16 */
1566 (&buf[..24], 0, 0x46796F3F78B20F6B, 0x58FF55C3926C13FA), /* 17-32 */
1567 (&buf[..24], PRIME, 0x30D5C4E9EB415C55, 0x8868344B3A4645D0), /* 17-32 */
1568 (&buf[..48], 0, 0xD8D4D3590D136E11, 0x5527A42843020A62), /* 33-64 */
1569 (&buf[..48], PRIME, 0x1D8834E1A5407A1C, 0x44375B9FB060F541), /* 33-64 */
1570 (&buf[..81], 0, 0x4B9B448ED8DFD3DD, 0xE805A6D1A43D70E5), /* 65-96 */
1571 (&buf[..81], PRIME, 0xD2D6B075945617BA, 0xE58BE5736F6E7550), /* 65-96 */
1572 (&buf[..103], 0, 0xC5A9F97B29EFA44E, 0x254DB7BE881E125C), /* 97-128 */
1573 (&buf[..103], PRIME, 0xFA2086367CDB177F, 0x0AEDEA68C988B0C0), /* 97-128 */
1574 (&buf[..192], 0, 0xC3142FDDD9102A3F, 0x06F1747E77185F97), /* 129-240 */
1575 (&buf[..192], PRIME, 0xA89F07B35987540F, 0xCF1B35FB2C557F54), /* 129-240 */
1576 (&buf[..222], 0, 0xA61AC4EB3295F86B, 0x33FA7B7598C28A07), /* 129-240 */
1577 (&buf[..222], PRIME, 0x54135EB88AD8B75E, 0xBC45CE6AE50BCF53), /* 129-240 */
1578 (&buf[..403], 0, 0xB0C48E6D18E9D084, 0xB16FC17E992FF45D), /* one block, last stripe is overlapping */
1579 (&buf[..403], PRIME64, 0x0A1D320C9520871D, 0xCE11CB376EC93252), /* one block, last stripe is overlapping */
1580 (&buf[..512], 0, 0xA03428558AC97327, 0x4ECF51281BA406F7), /* one block, finishing at stripe boundary */
1581 (&buf[..512], PRIME64, 0xAF67A482D6C893F2, 0x1382D92F25B84D90), /* one block, finishing at stripe boundary */
1582 (&buf[..2048], 0, 0x21901B416B3B9863, 0x212AF8E6326F01E0), /* two blocks, finishing at block boundary */
1583 (&buf[..2048], PRIME, 0xBDBB2282577DADEC, 0xF78CDDC2C9A9A692), /* two blocks, finishing at block boundary */
1584 (&buf[..2240], 0, 0x00AD52FA9385B6FE, 0xC705BAD3356CE302), /* two blocks, ends at stripe boundary */
1585 (&buf[..2240], PRIME, 0x10FD0072EC68BFAA, 0xE1312F3458817F15), /* two blocks, ends at stripe boundary */
1586 (&buf[..2237], 0, 0x970C91411533862C, 0x4BBD06FF7BFF0AB1), /* two blocks, ends at stripe boundary */
1587 (&buf[..2237], PRIME, 0xD80282846D814431, 0x14EBB157B84D9785), /* two blocks, ends at stripe boundary */
1588 ];
1589
1590 for (buf, seed, lo, hi) in test_cases {
1591 let result = u128::from(lo) + (u128::from(hi) << 64);
1592
1593 {
1594 let hash = hash128_with_seed(buf, seed);
1595
1596 assert_eq!(
1597 hash,
1598 result,
1599 "hash128_with_seed(&buf[..{}], seed={}) failed, got 0x{:X}, expected 0x{:X}",
1600 buf.len(),
1601 seed,
1602 hash,
1603 result
1604 );
1605 }
1606
1607 // streaming API test
1608
1609 // single ingestio
1610 {
1611 let mut hasher = Hash128::with_seed(seed);
1612 hasher.write(buf);
1613 let hash = hasher.finish_ext();
1614
1615 assert_eq!(
1616 hash,
1617 result,
1618 "Hash128::update(&buf[..{}]) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1619 buf.len(),
1620 seed,
1621 hash,
1622 result
1623 );
1624 }
1625
1626 if buf.len() > 3 {
1627 // 2 ingestions
1628 let mut hasher = Hash128::with_seed(seed);
1629 hasher.write(&buf[..3]);
1630 hasher.write(&buf[3..]);
1631 let hash = hasher.finish_ext();
1632
1633 assert_eq!(
1634 hash,
1635 result,
1636 "Hash64::update(&buf[..3], &buf[3..{}]) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1637 buf.len(),
1638 seed,
1639 hash,
1640 result
1641 );
1642 }
1643
1644 // byte by byte ingestion
1645 {
1646 let mut hasher = Hash128::with_seed(seed);
1647
1648 for chunk in buf.chunks(1) {
1649 hasher.write(chunk);
1650 }
1651
1652 let hash = hasher.finish_ext();
1653
1654 assert_eq!(
1655 hash,
1656 result,
1657 "Hash64::update(&buf[..{}].chunks(1)) with seed={} failed, got 0x{:X}, expected 0x{:X}",
1658 buf.len(),
1659 seed,
1660 hash,
1661 result
1662 );
1663 }
1664 }
1665 }
1666}
1667