A game about forced loneliness, made by TACStudios
tacstudios.tngl.sh
1using System.Runtime.CompilerServices;
2using Unity.Burst;
3using Unity.Burst.Intrinsics;
4using Unity.Collections.LowLevel.Unsafe;
5using Unity.Mathematics;
6using UnityEngine;
7#if UNITY_EDITOR
8using UnityEditor;
9#endif
10
11namespace Unity.Collections
12{
13 /// <summary>
14 /// A feature complete hashing API based on xxHash3 (https://github.com/Cyan4973/xxHash)
15 /// </summary>
16 /// <remarks>
17 /// Features:
18 /// - Compute 64bits or 128bits hash keys, based on a private key, with an optional given seed value.
19 /// - Hash on buffer (with or without a ulong based seed value)
20 /// - Hash on buffer while copying the data to a destination
21 /// - Use instances of <see cref="xxHash3.StreamingState"/> to accumulate data to hash in multiple calls, suited for small data, then retrieve the hash key at the end.
22 /// - xxHash3 has several implementation based on the size to hash to ensure best performances
23 /// - We currently have two implementations:
24 /// - A generic one based on Unity.Mathematics, that should always be executed compiled with Burst.
25 /// - An AVX2 based implementation for platforms supporting it, using Burst intrinsics.
26 /// - Whether or not the call site is compiled with burst, the hashing function will be executed by Burst(*) to ensure optimal performance.
27 /// (*) Only when the hashing size justifies such transition.
28 /// </remarks>
29 [BurstCompile]
30 [GenerateTestsForBurstCompatibility]
31 public static partial class xxHash3
32 {
33 #region Public API
34
35 /// <summary>
36 /// Compute a 64bits hash of a memory region
37 /// </summary>
38 /// <param name="input">The memory buffer, can't be null</param>
39 /// <param name="length">The length of the memory buffer, can be zero</param>
40 /// <returns>The hash result</returns>
41 public static unsafe uint2 Hash64(void* input, long length)
42 {
43 fixed (void* secret = xxHashDefaultKey.kSecret)
44 {
45 return ToUint2(Hash64Internal((byte*) input, null, length, (byte*) secret, 0));
46 }
47 }
48
49
50 /// <summary>
51 /// Compute a 64bits hash from the contents of the input struct
52 /// </summary>
53 /// <typeparam name="T">The input type.</typeparam>
54 /// <param name="input">The input struct that will be hashed</param>
55 /// <returns>The hash result</returns>
56 [GenerateTestsForBurstCompatibility(GenericTypeArguments = new [] { typeof(int) })]
57 public static unsafe uint2 Hash64<T>(in T input) where T : unmanaged
58 {
59 return Hash64(UnsafeUtilityExtensions.AddressOf(input), UnsafeUtility.SizeOf<T>());
60 }
61
62 /// <summary>
63 /// Compute a 64bits hash of a memory region using a given seed value
64 /// </summary>
65 /// <param name="input">The memory buffer, can't be null</param>
66 /// <param name="length">The length of the memory buffer, can be zero</param>
67 /// <param name="seed">The seed value to alter the hash computation from</param>
68 /// <returns>The hash result</returns>
69 public static unsafe uint2 Hash64(void* input, long length, ulong seed)
70 {
71 fixed (byte* secret = xxHashDefaultKey.kSecret)
72 {
73 return ToUint2(Hash64Internal((byte*) input, null, length, secret, seed));
74 }
75 }
76
77 /// <summary>
78 /// Compute a 128bits hash of a memory region
79 /// </summary>
80 /// <param name="input">The memory buffer, can't be null</param>
81 /// <param name="length">The length of the memory buffer, can be zero</param>
82 /// <returns>The hash result</returns>
83 public static unsafe uint4 Hash128(void* input, long length)
84 {
85 fixed (void* secret = xxHashDefaultKey.kSecret)
86 {
87 Hash128Internal((byte*) input, null, length, (byte*) secret, 0, out var result);
88 return result;
89 }
90 }
91
92 /// <summary>
93 /// Compute a 128bits hash from the contents of the input struct
94 /// </summary>
95 /// <typeparam name="T">The input type.</typeparam>
96 /// <param name="input">The input struct that will be hashed</param>
97 /// <returns>The hash result</returns>
98 [GenerateTestsForBurstCompatibility(GenericTypeArguments = new [] { typeof(int) })]
99 public static unsafe uint4 Hash128<T>(in T input) where T : unmanaged
100 {
101 return Hash128(UnsafeUtilityExtensions.AddressOf(input), UnsafeUtility.SizeOf<T>());
102 }
103
104 /// <summary>
105 /// Compute a 128bits hash while copying the data to a destination buffer
106 /// </summary>
107 /// <param name="input">The memory buffer to compute the hash and copy from, can't be null</param>
108 /// <param name="destination">The destination buffer, can't be null and must be at least big enough to match the input's length</param>
109 /// <param name="length">The length of the memory buffer, can be zero</param>
110 /// <returns>The hash result</returns>
111 /// <remarks>Use this API to avoid a double memory scan in situations where the hash as to be compute and the data copied at the same time. Performances improvements vary between 30-50% on
112 /// big data.</remarks>
113 public static unsafe uint4 Hash128(void* input, void* destination, long length)
114 {
115 fixed (byte* secret = xxHashDefaultKey.kSecret)
116 {
117 Hash128Internal((byte*) input, (byte*) destination, length, secret, 0, out var result);
118
119 return result;
120 }
121 }
122
123 /// <summary>
124 /// Compute a 128bits hash of a memory region using a given seed value
125 /// </summary>
126 /// <param name="input">The memory buffer, can't be null</param>
127 /// <param name="length">The length of the memory buffer, can be zero</param>
128 /// <param name="seed">The seed value to alter the hash computation from</param>
129 /// <returns>The hash result</returns>
130 public static unsafe uint4 Hash128(void* input, long length, ulong seed)
131 {
132 fixed (byte* secret = xxHashDefaultKey.kSecret)
133 {
134 Hash128Internal((byte*) input, null, length, secret, seed, out var result);
135
136 return result;
137 }
138 }
139
140 /// <summary>
141 /// Compute a 128bits hash while copying the data to a destination buffer using a given seed value
142 /// </summary>
143 /// <param name="input">The memory buffer to compute the hash and copy from, can't be null</param>
144 /// <param name="destination">The destination buffer, can't be null and must be at least big enough to match the input's length</param>
145 /// <param name="length">The length of the memory buffer, can be zero</param>
146 /// <param name="seed">The seed value to alter the hash computation from</param>
147 /// <returns>The hash result</returns>
148 public static unsafe uint4 Hash128(void* input, void* destination, long length, ulong seed)
149 {
150 fixed (byte* secret = xxHashDefaultKey.kSecret)
151 {
152 Hash128Internal((byte*) input, (byte*) destination, length, secret, seed, out var result);
153
154 return result;
155 }
156 }
157
158 #endregion
159
160 #region Constants
161
162 private const int STRIPE_LEN = 64;
163 private const int ACC_NB = STRIPE_LEN / 8; // Accumulators are ulong sized
164 private const int SECRET_CONSUME_RATE = 8;
165 private const int SECRET_KEY_SIZE = 192;
166 private const int SECRET_KEY_MIN_SIZE = 136;
167 private const int SECRET_LASTACC_START = 7;
168 private const int NB_ROUNDS = (SECRET_KEY_SIZE - STRIPE_LEN) / SECRET_CONSUME_RATE;
169 private const int BLOCK_LEN = STRIPE_LEN * NB_ROUNDS;
170
171 private const uint PRIME32_1 = 0x9E3779B1U;
172 private const uint PRIME32_2 = 0x85EBCA77U;
173
174 private const uint PRIME32_3 = 0xC2B2AE3DU;
175
176 // static readonly uint PRIME32_4 = 0x27D4EB2FU;
177 private const uint PRIME32_5 = 0x165667B1U;
178 private const ulong PRIME64_1 = 0x9E3779B185EBCA87UL;
179 private const ulong PRIME64_2 = 0xC2B2AE3D27D4EB4FUL;
180 private const ulong PRIME64_3 = 0x165667B19E3779F9UL;
181 private const ulong PRIME64_4 = 0x85EBCA77C2B2AE63UL;
182 private const ulong PRIME64_5 = 0x27D4EB2F165667C5UL;
183
184 private const int MIDSIZE_MAX = 240;
185 private const int MIDSIZE_STARTOFFSET = 3;
186 private const int MIDSIZE_LASTOFFSET = 17;
187
188 private const int SECRET_MERGEACCS_START = 11;
189
190 #endregion
191
192 private struct ulong2
193 {
194 public ulong x;
195 public ulong y;
196
197 public ulong2(ulong x, ulong y)
198 {
199 this.x = x;
200 this.y = y;
201 }
202 }
203
204 internal static unsafe ulong Hash64Internal(byte* input, byte* dest, long length, byte* secret, ulong seed)
205 {
206 if (length < 16)
207 {
208 return Hash64Len0To16(input, length, secret, seed);
209 }
210
211 if (length < 128)
212 {
213 return Hash64Len17To128(input, length, secret, seed);
214 }
215
216 if (length < MIDSIZE_MAX)
217 {
218 return Hash64Len129To240(input, length, secret, seed);
219 }
220
221 if (seed != 0)
222 {
223 var newSecret = (byte*) Memory.Unmanaged.Allocate(SECRET_KEY_SIZE, 64, Allocator.Temp);
224
225 EncodeSecretKey(newSecret, secret, seed);
226 var result = Hash64Long(input, dest, length, newSecret);
227
228 Memory.Unmanaged.Free(newSecret, Allocator.Temp);
229
230 return result;
231 }
232
233 else
234 {
235 return Hash64Long(input, dest, length, secret);
236 }
237 }
238
239 internal static unsafe void Hash128Internal(byte* input, byte* dest, long length, byte* secret, ulong seed,
240 out uint4 result)
241 {
242 if (dest != null && length < MIDSIZE_MAX)
243 {
244 UnsafeUtility.MemCpy(dest, input, length);
245 }
246
247 if (length < 16)
248 {
249 Hash128Len0To16(input, length, secret, seed, out result);
250 return;
251 }
252
253 if (length < 128)
254 {
255 Hash128Len17To128(input, length, secret, seed, out result);
256 return;
257 }
258
259 if (length < MIDSIZE_MAX)
260 {
261 Hash128Len129To240(input, length, secret, seed, out result);
262 return;
263 }
264
265 if (seed != 0)
266 {
267 var addr = stackalloc byte[SECRET_KEY_SIZE + 31];
268
269 // Aligned the allocated address on 32 bytes
270 var newSecret = (byte*) ((ulong) addr + 31 & 0xFFFFFFFFFFFFFFE0);
271
272 EncodeSecretKey(newSecret, secret, seed);
273 Hash128Long(input, dest, length, newSecret, out result);
274 }
275
276 else
277 {
278 Hash128Long(input, dest, length, secret, out result);
279 }
280 }
281
282 #region 64-bits hash, size dependent implementations
283
284 private static unsafe ulong Hash64Len1To3(byte* input, long len, byte* secret, ulong seed)
285 {
286 unchecked
287 {
288 var c1 = input[0];
289 var c2 = input[len >> 1];
290 var c3 = input[len - 1];
291 var combined = ((uint)c1 << 16) | ((uint)c2 << 24) | ((uint)c3 << 0) | ((uint)len << 8);
292 ulong bitflip = (Read32LE(secret) ^ Read32LE(secret+4)) + seed;
293 ulong keyed = (ulong)combined ^ bitflip;
294 return AvalancheH64(keyed);
295 }
296 }
297
298 private static unsafe ulong Hash64Len4To8(byte* input, long length, byte* secret, ulong seed)
299 {
300 unchecked
301 {
302 seed ^= (ulong)Swap32((uint)seed) << 32;
303 var input1 = Read32LE(input);
304 var input2 = Read32LE(input + length - 4);
305 var bitflip = (Read64LE(secret+8) ^ Read64LE(secret+16)) - seed;
306 var input64 = input2 + (((ulong)input1) << 32);
307 var keyed = input64 ^ bitflip;
308 return rrmxmx(keyed, (ulong)length);
309 }
310 }
311
312 private static unsafe ulong Hash64Len9To16(byte* input, long length, byte* secret, ulong seed)
313 {
314 unchecked
315 {
316 var bitflip1 = (Read64LE(secret+24) ^ Read64LE(secret+32)) + seed;
317 var bitflip2 = (Read64LE(secret+40) ^ Read64LE(secret+48)) - seed;
318 var input_lo = Read64LE(input) ^ bitflip1;
319 var input_hi = Read64LE(input + length - 8) ^ bitflip2;
320 var acc = (ulong)length + Swap64(input_lo) + input_hi + Mul128Fold64(input_lo, input_hi);
321 return Avalanche(acc);
322 }
323 }
324
325 private static unsafe ulong Hash64Len0To16(byte* input, long length, byte* secret, ulong seed)
326 {
327 if (length > 8)
328 {
329 return Hash64Len9To16(input, length, secret, seed);
330 }
331
332 if (length >= 4)
333 {
334 return Hash64Len4To8(input, length, secret, seed);
335 }
336
337 if (length > 0)
338 {
339 return Hash64Len1To3(input, length, secret, seed);
340 }
341
342 return AvalancheH64(seed ^ (Read64LE(secret+56) ^ Read64LE(secret+64)));
343 }
344
345 private static unsafe ulong Hash64Len17To128(byte* input, long length, byte* secret, ulong seed)
346 {
347 unchecked
348 {
349 var acc = (ulong) length * PRIME64_1;
350 if (length > 32)
351 {
352 if (length > 64)
353 {
354 if (length > 96)
355 {
356 acc += Mix16(input + 48, secret + 96, seed);
357 acc += Mix16(input + length - 64, secret + 112, seed);
358 }
359
360 acc += Mix16(input + 32, secret + 64, seed);
361 acc += Mix16(input + length - 48, secret + 80, seed);
362 }
363
364 acc += Mix16(input + 16, secret + 32, seed);
365 acc += Mix16(input + length - 32, secret + 48, seed);
366 }
367
368 acc += Mix16(input + 0, secret + 0, seed);
369 acc += Mix16(input + length - 16, secret + 16, seed);
370
371 return Avalanche(acc);
372 }
373 }
374
375 private static unsafe ulong Hash64Len129To240(byte* input, long length, byte* secret, ulong seed)
376 {
377 unchecked
378 {
379 var acc = (ulong) length * PRIME64_1;
380 var nbRounds = (int) length / 16;
381 for (var i = 0; i < 8; i++)
382 {
383 acc += Mix16(input + (16 * i), secret + (16 * i), seed);
384 }
385
386 acc = Avalanche(acc);
387
388 for (var i = 8; i < nbRounds; i++)
389 {
390 acc += Mix16(input + (16 * i), secret + (16 * (i - 8)) + MIDSIZE_STARTOFFSET, seed);
391 }
392
393 acc += Mix16(input + length - 16, secret + SECRET_KEY_MIN_SIZE - MIDSIZE_LASTOFFSET, seed);
394 return Avalanche(acc);
395 }
396 }
397
398 [BurstCompile]
399 private static unsafe ulong Hash64Long(byte* input, byte* dest, long length, byte* secret)
400 {
401 var addr = stackalloc byte[STRIPE_LEN + 31];
402 var acc = (ulong*) ((ulong) addr + 31 & 0xFFFFFFFFFFFFFFE0); // Aligned the allocated address on 32 bytes
403 acc[0] = PRIME32_3;
404 acc[1] = PRIME64_1;
405 acc[2] = PRIME64_2;
406 acc[3] = PRIME64_3;
407 acc[4] = PRIME64_4;
408 acc[5] = PRIME32_2;
409 acc[6] = PRIME64_5;
410 acc[7] = PRIME32_1;
411
412 unchecked
413 {
414 if (X86.Avx2.IsAvx2Supported)
415 {
416 Avx2HashLongInternalLoop(acc, input, dest, length, secret, 1);
417 }
418 else
419 {
420 DefaultHashLongInternalLoop(acc, input, dest, length, secret, 1);
421 }
422 return MergeAcc(acc, secret + SECRET_MERGEACCS_START, (ulong) length * PRIME64_1);
423 }
424 }
425
426 #endregion
427
428 #region 128-bits hash, size dependent implementations
429
430 private static unsafe void Hash128Len1To3(byte* input, long length, byte* secret, ulong seed,
431 out uint4 result)
432 {
433 unchecked
434 {
435 var c1 = input[0];
436 var c2 = input[length >> 1];
437 var c3 = input[length - 1];
438 var combinedl = ((uint) c1 << 16) + (((uint) c2) << 24) + (((uint) c3) << 0) + (((uint) length) << 8);
439 var combinedh = RotL32(Swap32(combinedl), 13);
440 var bitflipl = (Read32LE(secret) ^ Read32LE(secret+4)) + seed;
441 var bitfliph = (Read32LE(secret+8) ^ Read32LE(secret+12)) - seed;
442 var keyed_lo = combinedl ^ bitflipl;
443 var keyed_hi = combinedh ^ bitfliph;
444
445 result = ToUint4(AvalancheH64(keyed_lo), AvalancheH64(keyed_hi));
446 }
447 }
448
449 private static unsafe void Hash128Len4To8(byte* input, long len, byte* secret, ulong seed,
450 out uint4 result)
451 {
452 unchecked
453 {
454 seed ^= (ulong)Swap32((uint)seed) << 32;
455 var input_lo = Read32LE(input);
456 var input_hi = Read32LE(input + len - 4);
457 var input_64 = input_lo + ((ulong)input_hi << 32);
458 var bitflip = (Read64LE(secret+16) ^ Read64LE(secret+24)) + seed;
459 var keyed = input_64 ^ bitflip;
460
461 var low = Common.umul128(keyed, PRIME64_1 + (ulong)(len << 2), out var high);
462
463 high += (low << 1);
464 low ^= (high >> 3);
465
466 low = XorShift64(low, 35);
467 low*= 0x9FB21C651E98DF25UL;
468 low = XorShift64(low, 28);
469 high = Avalanche(high);
470 result = ToUint4(low, high);
471 }
472 }
473
474 private static unsafe void Hash128Len9To16(byte* input, long len, byte* secret, ulong seed,
475 out uint4 result)
476 {
477 unchecked
478 {
479 var bitflipl = (Read64LE(secret+32) ^ Read64LE(secret+40)) - seed;
480 var bitfliph = (Read64LE(secret+48) ^ Read64LE(secret+56)) + seed;
481 var input_lo = Read64LE(input);
482 var input_hi = Read64LE(input + len - 8);
483 var low = Common.umul128(input_lo ^ input_hi ^ bitflipl, PRIME64_1, out var high);
484
485 low += (ulong)(len - 1) << 54;
486 input_hi ^= bitfliph;
487 high += input_hi + Mul32To64((uint)input_hi, PRIME32_2 - 1);
488 low ^= Swap64(high);
489
490 var hlow = Common.umul128(low, PRIME64_2, out var hhigh);
491 hhigh += high * PRIME64_2;
492
493 result = ToUint4(Avalanche(hlow), Avalanche(hhigh));
494 }
495 }
496
497 private static unsafe void Hash128Len0To16(byte* input, long length, byte* secret, ulong seed,
498 out uint4 result)
499 {
500 if (length > 8)
501 {
502 Hash128Len9To16(input, length, secret, seed, out result);
503 return;
504 }
505
506 if (length >= 4)
507 {
508 Hash128Len4To8(input, length, secret, seed, out result);
509 return;
510 }
511
512 if (length > 0)
513 {
514 Hash128Len1To3(input, length, secret, seed, out result);
515 return;
516 }
517
518 var bitflipl = Read64LE(secret+64) ^ Read64LE(secret+72);
519 var bitfliph = Read64LE(secret+80) ^ Read64LE(secret+88);
520 var low = AvalancheH64(seed ^ bitflipl);
521 var hi = AvalancheH64( seed ^ bitfliph);
522 result = ToUint4(low, hi);
523 }
524
525 private static unsafe void Hash128Len17To128(byte* input, long length, byte* secret, ulong seed,
526 out uint4 result)
527 {
528 unchecked
529 {
530 var acc = new ulong2((ulong) length * PRIME64_1, 0);
531 if (length > 32)
532 {
533 if (length > 64)
534 {
535 if (length > 96)
536 {
537 acc = Mix32(acc, input + 48, input + length - 64, secret + 96, seed);
538 }
539
540 acc = Mix32(acc, input + 32, input + length - 48, secret + 64, seed);
541 }
542
543 acc = Mix32(acc, input + 16, input + length - 32, secret + 32, seed);
544 }
545
546 acc = Mix32(acc, input, input + length - 16, secret, seed);
547
548 var low64 = acc.x + acc.y;
549 var high64 = acc.x * PRIME64_1 + acc.y * PRIME64_4 + ((ulong) length - seed) * PRIME64_2;
550
551 result = ToUint4(Avalanche(low64), 0ul - Avalanche(high64));
552 }
553 }
554
555 private static unsafe void Hash128Len129To240(byte* input, long length, byte* secret, ulong seed,
556 out uint4 result)
557 {
558 unchecked
559 {
560 var acc = new ulong2((ulong) length * PRIME64_1, 0);
561 var nbRounds = length / 32;
562 int i;
563
564 for (i = 0; i < 4; i++)
565 {
566 acc = Mix32(acc, input + 32 * i, input + 32 * i + 16, secret + 32 * i, seed);
567 }
568
569 acc.x = Avalanche(acc.x);
570 acc.y = Avalanche(acc.y);
571
572 for (i = 4; i < nbRounds; i++)
573 {
574 acc = Mix32(acc, input + 32 * i, input + 32 * i + 16, secret + MIDSIZE_STARTOFFSET + 32 * (i - 4),
575 seed);
576 }
577
578 acc = Mix32(acc, input + length - 16, input + length - 32,
579 secret + SECRET_KEY_MIN_SIZE - MIDSIZE_LASTOFFSET - 16, 0UL - seed);
580
581 var low64 = acc.x + acc.y;
582 var high64 = acc.x * PRIME64_1 + acc.y * PRIME64_4 + ((ulong) length - seed) * PRIME64_2;
583
584 result = ToUint4(Avalanche(low64), 0ul - Avalanche(high64));
585 }
586 }
587
588 [BurstCompile]
589 private static unsafe void Hash128Long(byte* input, byte* dest, long length, byte* secret, out uint4 result)
590 {
591 // var acc = stackalloc ulong[ACC_NB];
592 var addr = stackalloc byte[STRIPE_LEN + 31];
593 var acc = (ulong*) ((ulong) addr + 31 & 0xFFFFFFFFFFFFFFE0); // Aligned the allocated address on 32 bytes
594 acc[0] = PRIME32_3;
595 acc[1] = PRIME64_1;
596 acc[2] = PRIME64_2;
597 acc[3] = PRIME64_3;
598 acc[4] = PRIME64_4;
599 acc[5] = PRIME32_2;
600 acc[6] = PRIME64_5;
601 acc[7] = PRIME32_1;
602
603 unchecked
604 {
605 if (X86.Avx2.IsAvx2Supported)
606 {
607 Avx2HashLongInternalLoop(acc, input, dest, length, secret, 0);
608 }
609 else
610 {
611 DefaultHashLongInternalLoop(acc, input, dest, length, secret, 0);
612 }
613
614 var low64 = MergeAcc(acc, secret + SECRET_MERGEACCS_START, (ulong) length * PRIME64_1);
615 var high64 = MergeAcc(acc, secret + SECRET_KEY_SIZE - 64 - SECRET_MERGEACCS_START,
616 ~((ulong) length * PRIME64_2));
617
618 result = ToUint4(low64, high64);
619 }
620 }
621
622 #endregion
623
624 #region Internal helpers
625
626 internal static uint2 ToUint2(ulong u)
627 {
628 return new uint2((uint)(u & 0xFFFFFFFF), (uint)(u >> 32));
629 }
630
631 internal static uint4 ToUint4(ulong ul0, ulong ul1)
632 {
633 return new uint4((uint)(ul0 & 0xFFFFFFFF), (uint)(ul0 >> 32), (uint)(ul1 & 0xFFFFFFFF), (uint)(ul1 >> 32));
634 }
635
636 internal static unsafe void EncodeSecretKey(byte* dst, byte* secret, ulong seed)
637 {
638 unchecked
639 {
640 var seedInitCount = SECRET_KEY_SIZE / (8 * 2);
641 for (var i = 0; i < seedInitCount; i++)
642 {
643 Write64LE(dst + 16 * i + 0, Read64LE(secret + 16 * i + 0) + seed);
644 Write64LE(dst + 16 * i + 8, Read64LE(secret + 16 * i + 8) - seed);
645 }
646 }
647 }
648
649 [MethodImpl(MethodImplOptions.AggressiveInlining)]
650 private static unsafe ulong Read64LE(void* addr) => *(ulong*) addr;
651 [MethodImpl(MethodImplOptions.AggressiveInlining)]
652 private static unsafe uint Read32LE(void* addr) => *(uint*) addr;
653
654 [MethodImpl(MethodImplOptions.AggressiveInlining)]
655 private static unsafe void Write64LE(void* addr, ulong value) => *(ulong*) addr = value;
656 [MethodImpl(MethodImplOptions.AggressiveInlining)]
657 private static unsafe void Read32LE(void* addr, uint value) => *(uint*) addr = value;
658
659 [MethodImpl(MethodImplOptions.AggressiveInlining)]
660 private static ulong Mul32To64(uint x, uint y) => (ulong) x * y;
661
662 [MethodImpl(MethodImplOptions.AggressiveInlining)]
663 private static ulong Swap64(ulong x)
664 {
665 return ((x << 56) & 0xff00000000000000UL) |
666 ((x << 40) & 0x00ff000000000000UL) |
667 ((x << 24) & 0x0000ff0000000000UL) |
668 ((x << 8) & 0x000000ff00000000UL) |
669 ((x >> 8) & 0x00000000ff000000UL) |
670 ((x >> 24) & 0x0000000000ff0000UL) |
671 ((x >> 40) & 0x000000000000ff00UL) |
672 ((x >> 56) & 0x00000000000000ffUL);
673 }
674
675 [MethodImpl(MethodImplOptions.AggressiveInlining)]
676 private static uint Swap32(uint x)
677 {
678 return ((x << 24) & 0xff000000) |
679 ((x << 8) & 0x00ff0000) |
680 ((x >> 8) & 0x0000ff00) |
681 ((x >> 24) & 0x000000ff);
682 }
683
684 [MethodImpl(MethodImplOptions.AggressiveInlining)]
685 private static uint RotL32(uint x, int r) => (((x) << (r)) | ((x) >> (32 - (r))));
686 [MethodImpl(MethodImplOptions.AggressiveInlining)]
687 private static ulong RotL64(ulong x, int r) => (((x) << (r)) | ((x) >> (64 - (r))));
688
689 [MethodImpl(MethodImplOptions.AggressiveInlining)]
690 private static ulong XorShift64(ulong v64, int shift)
691 {
692 return v64 ^ (v64 >> shift);
693 }
694
695 [MethodImpl(MethodImplOptions.AggressiveInlining)]
696 private static ulong Mul128Fold64(ulong lhs, ulong rhs)
697 {
698 var lo = Common.umul128(lhs, rhs, out var hi);
699 return lo ^ hi;
700 }
701
702 [MethodImpl(MethodImplOptions.AggressiveInlining)]
703 private static unsafe ulong Mix16(byte* input, byte* secret, ulong seed)
704 {
705 var input_lo = Read64LE(input);
706 var input_hi = Read64LE(input + 8);
707 return Mul128Fold64(
708 input_lo ^ (Read64LE(secret + 0) + seed),
709 input_hi ^ (Read64LE(secret + 8) - seed));
710 }
711
712 [MethodImpl(MethodImplOptions.AggressiveInlining)]
713 private static unsafe ulong2 Mix32(ulong2 acc, byte* input_1, byte* input_2, byte* secret, ulong seed)
714 {
715 unchecked
716 {
717 var l0 = acc.x + Mix16(input_1, secret + 0, seed);
718 l0 ^= Read64LE(input_2) + Read64LE(input_2 + 8);
719
720 var l1 = acc.y + Mix16(input_2, secret + 16, seed);
721 l1 ^= Read64LE(input_1) + Read64LE(input_1 + 8);
722
723 return new ulong2(l0, l1);
724 }
725 }
726
727 [MethodImpl(MethodImplOptions.AggressiveInlining)]
728 private static ulong Avalanche(ulong h64)
729 {
730 unchecked
731 {
732 h64 = XorShift64(h64, 37);
733 h64 *= 0x165667919E3779F9UL;
734 h64 = XorShift64(h64, 32);
735 return h64;
736 }
737 }
738
739 [MethodImpl(MethodImplOptions.AggressiveInlining)]
740 private static ulong AvalancheH64(ulong h64)
741 {
742 unchecked
743 {
744 h64 ^= h64 >> 33;
745 h64 *= PRIME64_2;
746 h64 ^= h64 >> 29;
747 h64 *= PRIME64_3;
748 h64 ^= h64 >> 32;
749 return h64;
750 }
751 }
752
753 [MethodImpl(MethodImplOptions.AggressiveInlining)]
754 private static ulong rrmxmx(ulong h64, ulong length)
755 {
756 h64 ^= RotL64(h64, 49) ^ RotL64(h64, 24);
757 h64 *= 0x9FB21C651E98DF25UL;
758 h64 ^= (h64 >> 35) + length ;
759 h64 *= 0x9FB21C651E98DF25UL;
760 return XorShift64(h64, 28);
761 }
762
763 [MethodImpl(MethodImplOptions.AggressiveInlining)]
764 private static unsafe ulong Mix2Acc(ulong acc0, ulong acc1, byte* secret)
765 {
766 return Mul128Fold64(acc0 ^ Read64LE(secret), acc1 ^ Read64LE(secret+8));
767 }
768
769 internal static unsafe ulong MergeAcc(ulong* acc, byte* secret, ulong start)
770 {
771 unchecked
772 {
773 var result64 = start;
774
775 result64 += Mix2Acc(acc[0], acc[1], secret + 0);
776 result64 += Mix2Acc(acc[2], acc[3], secret + 16);
777 result64 += Mix2Acc(acc[4], acc[5], secret + 32);
778 result64 += Mix2Acc(acc[6], acc[7], secret + 48);
779
780 return Avalanche(result64);
781 }
782 }
783
784 #endregion
785
786 #region Default Implementation
787
788 private static unsafe void DefaultHashLongInternalLoop(ulong* acc, byte* input, byte* dest, long length, byte* secret, int isHash64)
789 {
790 // Process packets of 512 bits
791 var nb_blocks = (length-1) / BLOCK_LEN;
792 for (int n = 0; n < nb_blocks; n++)
793 {
794 DefaultAccumulate(acc, input + n * BLOCK_LEN, dest == null ? null : dest + n * BLOCK_LEN, secret,
795 NB_ROUNDS, isHash64);
796 DefaultScrambleAcc(acc, secret + SECRET_KEY_SIZE - STRIPE_LEN);
797 }
798
799 var nbStripes = ((length-1) - (BLOCK_LEN * nb_blocks)) / STRIPE_LEN;
800 DefaultAccumulate(acc, input + nb_blocks * BLOCK_LEN, dest == null ? null : dest + nb_blocks * BLOCK_LEN,
801 secret, nbStripes, isHash64);
802
803 var p = input + length - STRIPE_LEN;
804 DefaultAccumulate512(acc, p, null, secret + SECRET_KEY_SIZE - STRIPE_LEN - SECRET_LASTACC_START,
805 isHash64);
806
807 if (dest != null)
808 {
809 var remaining = length % STRIPE_LEN;
810 if (remaining != 0)
811 {
812 UnsafeUtility.MemCpy(dest + length - remaining, input + length - remaining, remaining);
813 }
814 }
815 }
816
817 internal static unsafe void DefaultAccumulate(ulong* acc, byte* input, byte* dest, byte* secret, long nbStripes, int isHash64)
818 {
819 for (int n = 0; n < nbStripes; n++)
820 {
821 DefaultAccumulate512(acc, input + n * STRIPE_LEN, dest == null ? null : dest + n * STRIPE_LEN,
822 secret + n * SECRET_CONSUME_RATE, isHash64);
823 }
824 }
825
826 internal static unsafe void DefaultAccumulate512(ulong* acc, byte* input, byte* dest, byte* secret, int isHash64)
827 {
828 var count = ACC_NB;
829 for (var i = 0; i < count; i++)
830 {
831 var data_val = Read64LE(input + 8 * i);
832 var data_key = data_val ^ Read64LE(secret + i * 8);
833
834 if (dest != null)
835 {
836 Write64LE(dest + 8 * i, data_val);
837 }
838
839 acc[i ^ 1] += data_val;
840 acc[i] += Mul32To64((uint) (data_key & 0xFFFFFFFF), (uint) (data_key >> 32));
841 }
842 }
843
844 internal static unsafe void DefaultScrambleAcc(ulong* acc, byte* secret)
845 {
846 for (var i = 0; i < ACC_NB; i++)
847 {
848 var key64 = Read64LE(secret + 8 * i);
849 var acc64 = acc[i];
850 acc64 = XorShift64(acc64, 47);
851 acc64 ^= key64;
852 acc64 *= PRIME32_1;
853 acc[i] = acc64;
854 }
855 }
856
857 #endregion
858 }
859
860 static class xxHashDefaultKey
861 {
862 // The default xxHash3 encoding key, other implementations of this algorithm should use the same key to produce identical hashes
863 public static readonly byte[] kSecret =
864 {
865 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
866 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
867 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
868 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
869 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
870 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
871 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
872 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
873
874 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
875 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
876 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
877 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
878 };
879 }
880}