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
15 use alloc::vec::Vec;
16
17 use core::convert::TryInto;
18 use core::hash::Hasher;
19 use core::mem;
20 use core::ops::{Deref, DerefMut};
21 use core::slice;
22
23 #[cfg(target_arch = "x86")]
24 use core::arch::x86::*;
25 #[cfg(target_arch = "x86_64")]
26 use core::arch::x86_64::*;
27
28 use cfg_if::cfg_if;
29 use static_assertions::{const_assert, const_assert_eq};
30
31 #[cfg(feature = "serialize")]
32 use serde::{Deserialize, Serialize};
33
34 use 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 };
38 use crate::thirty_two::{PRIME_1 as PRIME32_1, PRIME_2 as PRIME32_2, PRIME_3 as PRIME32_3};
39
40 #[cfg(feature = "std")]
41 pub use crate::std_support::xxh3::{RandomHashBuilder128, RandomHashBuilder64};
42
43 #[inline(always)]
hash64(data: &[u8]) -> u6444 pub fn hash64(data: &[u8]) -> u64 {
45 hash64_with_seed(data, 0)
46 }
47
48 #[inline(always)]
hash64_with_seed(data: &[u8], seed: u64) -> u6449 pub fn hash64_with_seed(data: &[u8], seed: u64) -> u64 {
50 let len = 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)]
hash64_with_secret(data: &[u8], secret: &[u8]) -> u6464 pub fn hash64_with_secret(data: &[u8], secret: &[u8]) -> u64 {
65 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
66
67 let len = data.len();
68
69 if len <= 16 {
70 hash_len_0to16_64bits(data, len, secret, 0)
71 } else if len <= 128 {
72 hash_len_17to128_64bits(data, len, secret, 0)
73 } else if len <= MIDSIZE_MAX {
74 hash_len_129to240_64bits(data, len, secret, 0)
75 } else {
76 hash_long_64bits_with_secret(data, len, secret)
77 }
78 }
79
80 #[inline(always)]
hash128(data: &[u8]) -> u12881 pub fn hash128(data: &[u8]) -> u128 {
82 hash128_with_seed(data, 0)
83 }
84
85 #[inline(always)]
hash128_with_seed(data: &[u8], seed: u64) -> u12886 pub fn hash128_with_seed(data: &[u8], seed: u64) -> u128 {
87 let len = 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)]
hash128_with_secret(data: &[u8], secret: &[u8]) -> u128101 pub fn hash128_with_secret(data: &[u8], secret: &[u8]) -> u128 {
102 debug_assert!(secret.len() >= SECRET_SIZE_MIN);
103
104 let len = data.len();
105
106 if len <= 16 {
107 hash_len_0to16_128bits(data, len, secret, 0)
108 } else if len <= 128 {
109 hash_len_17to128_128bits(data, len, secret, 0)
110 } else if len <= MIDSIZE_MAX {
111 hash_len_129to240_128bits(data, len, secret, 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)]
120 pub struct Hash64(State);
121
122 impl Hash64 {
with_seed(seed: u64) -> Self123 pub fn with_seed(seed: u64) -> Self {
124 Self(State::with_seed(seed))
125 }
126
with_secret<S: Into<Vec<u8>>>(secret: S) -> Self127 pub fn with_secret<S: Into<Vec<u8>>>(secret: S) -> Self {
128 Self(State::with_secret(secret))
129 }
130 }
131
132 impl Hasher for Hash64 {
133 #[inline(always)]
finish(&self) -> u64134 fn finish(&self) -> u64 {
135 self.0.digest64()
136 }
137
138 #[inline(always)]
write(&mut self, bytes: &[u8])139 fn write(&mut self, bytes: &[u8]) {
140 self.0.update(bytes, AccWidth::Acc64Bits)
141 }
142 }
143
144 /// Calculates the 128-bit hash.
145 #[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
146 #[derive(Clone, Default)]
147 pub struct Hash128(State);
148
149 impl Hash128 {
with_seed(seed: u64) -> Self150 pub fn with_seed(seed: u64) -> Self {
151 Self(State::with_seed(seed))
152 }
153
with_secret<S: Into<Vec<u8>>>(secret: S) -> Self154 pub fn with_secret<S: Into<Vec<u8>>>(secret: S) -> Self {
155 Self(State::with_secret(secret))
156 }
157 }
158
159 impl Hasher for Hash128 {
160 #[inline(always)]
finish(&self) -> u64161 fn finish(&self) -> u64 {
162 self.0.digest128() as u64
163 }
164
165 #[inline(always)]
write(&mut self, bytes: &[u8])166 fn write(&mut self, bytes: &[u8]) {
167 self.0.update(bytes, AccWidth::Acc128Bits)
168 }
169 }
170
171 pub trait HasherExt: Hasher {
finish_ext(&self) -> u128172 fn finish_ext(&self) -> u128;
173 }
174
175 impl HasherExt for Hash128 {
176 #[inline(always)]
finish_ext(&self) -> u128177 fn finish_ext(&self) -> u128 {
178 self.0.digest128()
179 }
180 }
181
182 /* ==========================================
183 * XXH3 default settings
184 * ========================================== */
185
186 const SECRET_DEFAULT_SIZE: usize = 192;
187 const SECRET_SIZE_MIN: usize = 136;
188
189 const 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)]
206 struct Secret([u8; SECRET_DEFAULT_SIZE]);
207
208 const_assert_eq!(mem::size_of::<Secret>() % 16, 0);
209
210 impl Default for Secret {
211 #[inline(always)]
default() -> Self212 fn default() -> Self {
213 SECRET
214 }
215 }
216
217 impl Deref for Secret {
218 type Target = [u8];
219
220 #[inline(always)]
deref(&self) -> &Self::Target221 fn deref(&self) -> &Self::Target {
222 &self.0[..]
223 }
224 }
225
226 cfg_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
273 impl Secret {
274 #[inline(always)]
with_seed(seed: u64) -> Self275 pub fn with_seed(seed: u64) -> Self {
276 let mut secret = [0; SECRET_DEFAULT_SIZE];
277
278 for off in (0..SECRET_DEFAULT_SIZE).step_by(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
287 cfg_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
306 const ACC_SIZE: usize = mem::size_of::<Acc>();
307
308 const_assert_eq!(ACC_SIZE, 64);
309
310 impl Default for Acc {
311 #[inline(always)]
default() -> Self312 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
326 impl Deref for Acc {
327 type Target = [u64];
328
329 #[inline(always)]
deref(&self) -> &Self::Target330 fn deref(&self) -> &Self::Target {
331 &self.0
332 }
333 }
334
335 impl DerefMut for Acc {
336 #[inline(always)]
deref_mut(&mut self) -> &mut Self::Target337 fn deref_mut(&mut self) -> &mut Self::Target {
338 &mut self.0
339 }
340 }
341
342 trait Buf {
read_u32_le(&self) -> u32343 fn read_u32_le(&self) -> u32;
344
read_u64_le(&self) -> u64345 fn read_u64_le(&self) -> u64;
346 }
347
348 trait BufMut {
write_u32_le(&mut self, n: u32)349 fn write_u32_le(&mut self, n: u32);
350
write_u64_le(&mut self, n: u64)351 fn write_u64_le(&mut self, n: u64);
352 }
353
354 impl Buf for [u8] {
355 #[inline(always)]
read_u32_le(&self) -> u32356 fn read_u32_le(&self) -> u32 {
357 let buf = &self[..mem::size_of::<u32>()];
358 u32::from_le_bytes(buf.try_into().unwrap())
359 }
360
361 #[inline(always)]
read_u64_le(&self) -> u64362 fn read_u64_le(&self) -> u64 {
363 let buf = &self[..mem::size_of::<u64>()];
364 u64::from_le_bytes(buf.try_into().unwrap())
365 }
366 }
367
368 impl BufMut for [u8] {
369 #[inline(always)]
write_u32_le(&mut self, n: u32)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)]
write_u64_le(&mut self, n: u64)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)]
hash_len_0to16_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64385 fn 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)]
hash_len_9to16_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64400 fn hash_len_9to16_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64 {
401 debug_assert!((9..=16).contains(&len));
402
403 let ll1 = data.read_u64_le() ^ key.read_u64_le().wrapping_add(seed);
404 let ll2 = data[len - 8..].read_u64_le() ^ key[8..].read_u64_le().wrapping_sub(seed);
405 let acc = (len as u64)
406 .wrapping_add(ll1)
407 .wrapping_add(ll2)
408 .wrapping_add(mul128_fold64(ll1, ll2));
409
410 avalanche(acc)
411 }
412
413 #[inline(always)]
hash_len_4to8_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64414 fn 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::from(data.read_u32_le());
418 let in2 = u64::from(data[len - 4..].read_u32_le());
419 let in64 = in1.wrapping_add(in2 << 32);
420 let keyed = in64 ^ key.read_u64_le().wrapping_add(seed);
421 let mix64 =
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)]
hash_len_1to3_64bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u64428 fn 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::from(data[0]);
432 let c2 = u32::from(data[len >> 1]);
433 let c3 = u32::from(data[len - 1]);
434 let combined = c1 + (c2 << 8) + (c3 << 16) + ((len as u32) << 24);
435 let keyed = u64::from(combined) ^ u64::from(key.read_u32_le()).wrapping_add(seed);
436 let mixed = keyed.wrapping_mul(PRIME64_1);
437
438 avalanche(mixed)
439 }
440
441 #[inline(always)]
hash_len_17to128_64bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u64442 fn 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
472 const MIDSIZE_MAX: usize = 240;
473 const MIDSIZE_STARTOFFSET: usize = 3;
474 const MIDSIZE_LASTOFFSET: usize = 17;
475
476 #[inline(always)]
hash_len_129to240_64bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u64477 fn 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
509 const STRIPE_LEN: usize = 64;
510 const SECRET_CONSUME_RATE: usize = 8; // nb of secret bytes consumed at each accumulation
511 const SECRET_MERGEACCS_START: usize = 11; // do not align on 8, so that secret is different from accumulator
512 const SECRET_LASTACC_START: usize = 7; // do not align on 8, so that secret is different from scrambler
513 const ACC_NB: usize = STRIPE_LEN / mem::size_of::<u64>();
514
515 #[derive(Debug, Clone, Copy, PartialEq)]
516 pub(crate) enum AccWidth {
517 Acc64Bits,
518 Acc128Bits,
519 }
520
521 #[inline(always)]
hash_long_64bits_with_default_secret(data: &[u8], len: usize) -> u64522 fn hash_long_64bits_with_default_secret(data: &[u8], len: usize) -> u64 {
523 hash_long_internal(data, len, &SECRET)
524 }
525
526 #[inline(always)]
hash_long_64bits_with_secret(data: &[u8], len: usize, secret: &[u8]) -> u64527 fn 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)]
hash_long_64bits_with_seed(data: &[u8], len: usize, seed: u64) -> u64537 fn 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::with_seed(seed);
542
543 hash_long_internal(data, len, &secret)
544 }
545 }
546
547 #[inline(always)]
hash_long_internal(data: &[u8], len: usize, secret: &[u8]) -> u64548 fn hash_long_internal(data: &[u8], len: usize, secret: &[u8]) -> u64 {
549 let mut 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)]
hash_long_internal_loop( acc: &mut [u64], data: &[u8], len: usize, secret: &[u8], acc_width: AccWidth, )561 fn 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)]
accumulate(acc: &mut [u64], data: &[u8], secret: &[u8], nb_stripes: usize, acc_width: AccWidth)606 fn accumulate(acc: &mut [u64], data: &[u8], secret: &[u8], nb_stripes: usize, acc_width: AccWidth) {
607 for n 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)]
_mm_shuffle(z: u32, y: u32, x: u32, w: u32) -> i32620 const 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")]
625 mod avx2 {
626 use super::*;
627
628 #[target_feature(enable = "avx2")]
accumulate512( acc: &mut [u64], data: &[u8], keys: &[u8], acc_width: AccWidth, )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")]
scramble_acc(acc: &mut [u64], key: &[u8])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")))]
681 mod sse2 {
682 use super::*;
683
684 #[target_feature(enable = "sse2")]
685 #[allow(clippy::cast_ptr_alignment)]
accumulate512( acc: &mut [u64], data: &[u8], keys: &[u8], acc_width: AccWidth, )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)]
scramble_acc(acc: &mut [u64], key: &[u8])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")))]
739 mod generic {
740 use super::*;
741
742 #[inline(always)]
accumulate512( acc: &mut [u64], data: &[u8], key: &[u8], acc_width: AccWidth, )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)]
mul32_to64(a: u64, b: u64) -> u64770 fn mul32_to64(a: u64, b: u64) -> u64 {
771 (a & 0xFFFFFFFF).wrapping_mul(b & 0xFFFFFFFF)
772 }
773
774 #[inline(always)]
scramble_acc(acc: &mut [u64], key: &[u8])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
787 cfg_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)]
merge_accs(acc: &[u64], secret: &[u8], start: u64) -> u64798 fn merge_accs(acc: &[u64], secret: &[u8], start: u64) -> u64 {
799 avalanche(
800 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)]
mix2accs(acc: &[u64], secret: &[u8]) -> u64809 fn mix2accs(acc: &[u64], secret: &[u8]) -> u64 {
810 mul128_fold64(
811 acc[0] ^ secret.read_u64_le(),
812 acc[1] ^ secret[8..].read_u64_le(),
813 )
814 }
815
816 #[inline(always)]
mix_16bytes(data: &[u8], key: &[u8], seed: u64) -> u64817 fn mix_16bytes(data: &[u8], key: &[u8], seed: u64) -> u64 {
818 let ll1 = data.read_u64_le();
819 let ll2 = data[8..].read_u64_le();
820
821 mul128_fold64(
822 ll1 ^ key.read_u64_le().wrapping_add(seed),
823 ll2 ^ key[8..].read_u64_le().wrapping_sub(seed),
824 )
825 }
826
827 #[inline(always)]
mul128_fold64(ll1: u64, ll2: u64) -> u64828 fn mul128_fold64(ll1: u64, ll2: u64) -> u64 {
829 let lll = u128::from(ll1).wrapping_mul(u128::from(ll2));
830
831 (lll as u64) ^ ((lll >> 64) as u64)
832 }
833
834 #[inline(always)]
avalanche(mut h64: u64) -> u64835 fn 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
843 const INTERNAL_BUFFER_SIZE: usize = 256;
844 const INTERNAL_BUFFER_STRIPES: usize = INTERNAL_BUFFER_SIZE / STRIPE_LEN;
845
846 const_assert!(INTERNAL_BUFFER_SIZE >= MIDSIZE_MAX);
847 const_assert_eq!(INTERNAL_BUFFER_SIZE % STRIPE_LEN, 0);
848
849 #[repr(align(64))]
850 #[cfg_attr(feature = "serialize", derive(Deserialize, Serialize))]
851 #[derive(Clone)]
852 struct 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)]
863 enum With {
864 Default(Secret),
865 Custom(Secret),
866 Ref(Vec<u8>),
867 }
868
869 impl Deref for With {
870 type Target = [u8];
871
deref(&self) -> &Self::Target872 fn deref(&self) -> &Self::Target {
873 match self {
874 With::Default(secret) | With::Custom(secret) => &secret.0[..],
875 With::Ref(secret) => secret,
876 }
877 }
878 }
879
880 impl Default for State {
default() -> Self881 fn default() -> Self {
882 Self::new(0, With::Default(Secret::default()))
883 }
884 }
885
886 impl State {
new(seed: u64, secret: With) -> Self887 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
with_seed(seed: u64) -> Self898 fn with_seed(seed: u64) -> Self {
899 Self::new(seed, With::Custom(Secret::with_seed(seed)))
900 }
901
with_secret<S: Into<Vec<u8>>>(secret: S) -> State902 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)]
secret_limit(&self) -> usize911 fn secret_limit(&self) -> usize {
912 self.secret.len() - STRIPE_LEN
913 }
914
915 #[inline(always)]
nb_stripes_per_block(&self) -> usize916 fn nb_stripes_per_block(&self) -> usize {
917 self.secret_limit() / SECRET_CONSUME_RATE
918 }
919
920 #[inline(always)]
update(&mut self, mut input: &[u8], acc_width: AccWidth)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)]
digest_long(&self, acc_width: AccWidth) -> Acc977 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)]
digest64(&self) -> u641031 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)]
digest128(&self) -> u1281048 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)]
consume_stripes( acc: &mut [u64], nb_stripes_so_far: usize, nb_stripes_per_block: usize, data: &[u8], total_stripes: usize, secret: &[u8], secret_limit: usize, acc_width: AccWidth, ) -> usize1080 fn 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)]
hash_len_0to16_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u1281132 fn 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, secret, seed)
1137 } else if len >= 4 {
1138 hash_len_4to8_128bits(data, len, secret, seed)
1139 } else if len > 0 {
1140 hash_len_1to3_128bits(data, len, secret, seed)
1141 } else {
1142 0
1143 }
1144 }
1145
1146 #[inline(always)]
hash_len_1to3_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u1281147 fn 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::from(data[0]);
1151 let c2 = u32::from(data[len >> 1]);
1152 let c3 = u32::from(data[len - 1]);
1153 let combinedl = c1 + (c2 << 8) + (c3 << 16) + ((len as u32) << 24);
1154 let combinedh = combinedl.swap_bytes();
1155 let keyedl = u64::from(combinedl) ^ u64::from(key.read_u32_le()).wrapping_add(seed);
1156 let keyedh = u64::from(combinedh) ^ u64::from(key[4..].read_u32_le()).wrapping_sub(seed);
1157 let mixedl = keyedl.wrapping_mul(PRIME64_1);
1158 let mixedh = keyedh.wrapping_mul(PRIME64_2);
1159
1160 u128::from(avalanche(mixedl)) + (u128::from(avalanche(mixedh)) << 64)
1161 }
1162
1163 #[inline(always)]
hash_len_4to8_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u1281164 fn 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::from(data.read_u32_le());
1168 let in2 = u64::from(data[len - 4..].read_u32_le());
1169 let in64l = in1.wrapping_add(in2 << 32);
1170 let in64h = in64l.swap_bytes();
1171 let keyedl = in64l ^ key.read_u64_le().wrapping_add(seed);
1172 let keyedh = in64h ^ key[8..].read_u64_le().wrapping_sub(seed);
1173 let mix64l1 =
1174 (len as u64).wrapping_add((keyedl ^ (keyedl >> 51)).wrapping_mul(u64::from(PRIME32_1)));
1175 let mix64l2 = (mix64l1 ^ (mix64l1 >> 47)).wrapping_mul(PRIME64_2);
1176 let mix64h1 = (keyedh ^ (keyedh >> 47))
1177 .wrapping_mul(PRIME64_1)
1178 .wrapping_sub(len as u64);
1179 let mix64h2 = (mix64h1 ^ (mix64h1 >> 43)).wrapping_mul(PRIME64_4);
1180
1181 u128::from(avalanche(mix64l2)) + (u128::from(avalanche(mix64h2)) << 64)
1182 }
1183
1184 #[inline(always)]
hash_len_9to16_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u1281185 fn hash_len_9to16_128bits(data: &[u8], len: usize, key: &[u8], seed: u64) -> u128 {
1186 debug_assert!((9..=16).contains(&len));
1187
1188 let ll1 = data.read_u64_le() ^ key.read_u64_le().wrapping_add(seed);
1189 let ll2 = data[len - 8..].read_u64_le() ^ key[8..].read_u64_le().wrapping_sub(seed);
1190 let inlow = ll1 ^ ll2;
1191
1192 let m128 = u128::from(inlow).wrapping_mul(u128::from(PRIME64_1));
1193 let high64 = ((m128 >> 64) as u64).wrapping_add(ll2.wrapping_mul(PRIME64_1));
1194 let low64 = (m128 as u64) ^ (high64 >> 32);
1195
1196 let h128 = u128::from(low64).wrapping_mul(u128::from(PRIME64_2));
1197 let high64 = ((h128 >> 64) as u64).wrapping_add(high64.wrapping_mul(PRIME64_2));
1198 let low64 = h128 as u64;
1199
1200 u128::from(avalanche(low64)) + (u128::from(avalanche(high64)) << 64)
1201 }
1202
1203 #[inline(always)]
hash_len_17to128_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u1281204 fn 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)]
hash_len_129to240_128bits(data: &[u8], len: usize, secret: &[u8], seed: u64) -> u1281238 fn 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]
hash_long_128bits_with_default_secret(data: &[u8], len: usize) -> u1281298 fn hash_long_128bits_with_default_secret(data: &[u8], len: usize) -> u128 {
1299 hash_long_128bits_internal(data, len, &SECRET)
1300 }
1301
1302 #[inline]
hash_long_128bits_with_secret(data: &[u8], len: usize, secret: &[u8]) -> u1281303 fn hash_long_128bits_with_secret(data: &[u8], len: usize, secret: &[u8]) -> u128 {
1304 hash_long_128bits_internal(data, len, secret)
1305 }
1306
1307 #[inline]
hash_long_128bits_with_seed(data: &[u8], len: usize, seed: u64) -> u1281308 fn 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::with_seed(seed);
1313
1314 hash_long_128bits_internal(data, len, &secret)
1315 }
1316 }
1317
1318 #[inline(always)]
hash_long_128bits_internal(data: &[u8], len: usize, secret: &[u8]) -> u1281319 fn hash_long_128bits_internal(data: &[u8], len: usize, secret: &[u8]) -> u128 {
1320 let mut 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 = merge_accs(
1327 &acc,
1328 &secret[SECRET_MERGEACCS_START..],
1329 (len as u64).wrapping_mul(PRIME64_1),
1330 );
1331 let high64 = 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,
1343 just the reset one is different (different initial acc values for 0,5,6,7),
1344 and near the end of the digest function */
1345
1346 #[cfg(test)]
1347 mod 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
sanity_buffer() -> [u8; SANITY_BUFFER_SIZE]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]
hash_64bits_sanity_check()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]
hash_64bits_with_secret_sanity_check()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]
hash_128bits_sanity_check()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