LLVM 19.0.0git
xxhash.cpp
Go to the documentation of this file.
1/*
2 * xxHash - Extremely Fast Hash algorithm
3 * Copyright (C) 2012-2023, Yann Collet
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * You can contact the author at :
31 * - xxHash homepage: http://www.xxhash.com
32 * - xxHash source repository : https://github.com/Cyan4973/xxHash
33 */
34
35// xxhash64 is based on commit d2df04efcbef7d7f6886d345861e5dfda4edacc1. Removed
36// everything but a simple interface for computing xxh64.
37
38// xxh3_64bits is based on commit d5891596637d21366b9b1dcf2c0007a3edb26a9e (July
39// 2023).
40
41// xxh3_128bits is based on commit b0adcc54188c3130b1793e7b19c62eb1e669f7df
42// (June 2024).
43
44#include "llvm/Support/xxhash.h"
46#include "llvm/Support/Endian.h"
47
48#include <stdlib.h>
49
50using namespace llvm;
51using namespace support;
52
53static uint64_t rotl64(uint64_t X, size_t R) {
54 return (X << R) | (X >> (64 - R));
55}
56
57constexpr uint32_t PRIME32_1 = 0x9E3779B1;
58constexpr uint32_t PRIME32_2 = 0x85EBCA77;
59constexpr uint32_t PRIME32_3 = 0xC2B2AE3D;
60
61static const uint64_t PRIME64_1 = 11400714785074694791ULL;
62static const uint64_t PRIME64_2 = 14029467366897019727ULL;
63static const uint64_t PRIME64_3 = 1609587929392839161ULL;
64static const uint64_t PRIME64_4 = 9650029242287828579ULL;
65static const uint64_t PRIME64_5 = 2870177450012600261ULL;
66
67static uint64_t round(uint64_t Acc, uint64_t Input) {
68 Acc += Input * PRIME64_2;
69 Acc = rotl64(Acc, 31);
70 Acc *= PRIME64_1;
71 return Acc;
72}
73
75 Val = round(0, Val);
76 Acc ^= Val;
77 Acc = Acc * PRIME64_1 + PRIME64_4;
78 return Acc;
79}
80
82 hash ^= hash >> 33;
83 hash *= PRIME64_2;
84 hash ^= hash >> 29;
85 hash *= PRIME64_3;
86 hash ^= hash >> 32;
87 return hash;
88}
89
91 size_t Len = Data.size();
92 uint64_t Seed = 0;
93 const unsigned char *P = Data.bytes_begin();
94 const unsigned char *const BEnd = Data.bytes_end();
95 uint64_t H64;
96
97 if (Len >= 32) {
98 const unsigned char *const Limit = BEnd - 32;
100 uint64_t V2 = Seed + PRIME64_2;
101 uint64_t V3 = Seed + 0;
102 uint64_t V4 = Seed - PRIME64_1;
103
104 do {
105 V1 = round(V1, endian::read64le(P));
106 P += 8;
107 V2 = round(V2, endian::read64le(P));
108 P += 8;
109 V3 = round(V3, endian::read64le(P));
110 P += 8;
111 V4 = round(V4, endian::read64le(P));
112 P += 8;
113 } while (P <= Limit);
114
115 H64 = rotl64(V1, 1) + rotl64(V2, 7) + rotl64(V3, 12) + rotl64(V4, 18);
116 H64 = mergeRound(H64, V1);
117 H64 = mergeRound(H64, V2);
118 H64 = mergeRound(H64, V3);
119 H64 = mergeRound(H64, V4);
120
121 } else {
122 H64 = Seed + PRIME64_5;
123 }
124
125 H64 += (uint64_t)Len;
126
127 while (reinterpret_cast<uintptr_t>(P) + 8 <=
128 reinterpret_cast<uintptr_t>(BEnd)) {
129 uint64_t const K1 = round(0, endian::read64le(P));
130 H64 ^= K1;
131 H64 = rotl64(H64, 27) * PRIME64_1 + PRIME64_4;
132 P += 8;
133 }
134
135 if (reinterpret_cast<uintptr_t>(P) + 4 <= reinterpret_cast<uintptr_t>(BEnd)) {
137 H64 = rotl64(H64, 23) * PRIME64_2 + PRIME64_3;
138 P += 4;
139 }
140
141 while (P < BEnd) {
142 H64 ^= (*P) * PRIME64_5;
143 H64 = rotl64(H64, 11) * PRIME64_1;
144 P++;
145 }
146
147 return XXH64_avalanche(H64);
148}
149
151 return xxHash64({(const char *)Data.data(), Data.size()});
152}
153
154constexpr size_t XXH3_SECRETSIZE_MIN = 136;
155constexpr size_t XXH_SECRET_DEFAULT_SIZE = 192;
156
157/* Pseudorandom data taken directly from FARSH */
158// clang-format off
159constexpr uint8_t kSecret[XXH_SECRET_DEFAULT_SIZE] = {
160 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
161 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
162 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
163 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
164 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
165 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
166 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
167 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
168 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
169 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
170 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
171 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
172};
173// clang-format on
174
175constexpr uint64_t PRIME_MX1 = 0x165667919E3779F9;
176constexpr uint64_t PRIME_MX2 = 0x9FB21C651E98DF25;
177
178// Calculates a 64-bit to 128-bit multiply, then XOR folds it.
180#if defined(__SIZEOF_INT128__) || \
181 (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128)
182 __uint128_t product = (__uint128_t)lhs * (__uint128_t)rhs;
183 return uint64_t(product) ^ uint64_t(product >> 64);
184
185#else
186 /* First calculate all of the cross products. */
187 const uint64_t lo_lo = (lhs & 0xFFFFFFFF) * (rhs & 0xFFFFFFFF);
188 const uint64_t hi_lo = (lhs >> 32) * (rhs & 0xFFFFFFFF);
189 const uint64_t lo_hi = (lhs & 0xFFFFFFFF) * (rhs >> 32);
190 const uint64_t hi_hi = (lhs >> 32) * (rhs >> 32);
191
192 /* Now add the products together. These will never overflow. */
193 const uint64_t cross = (lo_lo >> 32) + (hi_lo & 0xFFFFFFFF) + lo_hi;
194 const uint64_t upper = (hi_lo >> 32) + (cross >> 32) + hi_hi;
195 const uint64_t lower = (cross << 32) | (lo_lo & 0xFFFFFFFF);
196
197 return upper ^ lower;
198#endif
199}
200
201constexpr size_t XXH_STRIPE_LEN = 64;
202constexpr size_t XXH_SECRET_CONSUME_RATE = 8;
203constexpr size_t XXH_ACC_NB = XXH_STRIPE_LEN / sizeof(uint64_t);
204
206 hash ^= hash >> 37;
207 hash *= PRIME_MX1;
208 hash ^= hash >> 32;
209 return hash;
210}
211
212static uint64_t XXH3_len_1to3_64b(const uint8_t *input, size_t len,
213 const uint8_t *secret, uint64_t seed) {
214 const uint8_t c1 = input[0];
215 const uint8_t c2 = input[len >> 1];
216 const uint8_t c3 = input[len - 1];
217 uint32_t combined = ((uint32_t)c1 << 16) | ((uint32_t)c2 << 24) |
218 ((uint32_t)c3 << 0) | ((uint32_t)len << 8);
219 uint64_t bitflip =
220 (uint64_t)(endian::read32le(secret) ^ endian::read32le(secret + 4)) +
221 seed;
222 return XXH64_avalanche(uint64_t(combined) ^ bitflip);
223}
224
225static uint64_t XXH3_len_4to8_64b(const uint8_t *input, size_t len,
226 const uint8_t *secret, uint64_t seed) {
227 seed ^= (uint64_t)byteswap(uint32_t(seed)) << 32;
228 const uint32_t input1 = endian::read32le(input);
229 const uint32_t input2 = endian::read32le(input + len - 4);
230 uint64_t acc =
231 (endian::read64le(secret + 8) ^ endian::read64le(secret + 16)) - seed;
232 const uint64_t input64 = (uint64_t)input2 | ((uint64_t)input1 << 32);
233 acc ^= input64;
234 // XXH3_rrmxmx(acc, len)
235 acc ^= rotl64(acc, 49) ^ rotl64(acc, 24);
236 acc *= PRIME_MX2;
237 acc ^= (acc >> 35) + (uint64_t)len;
238 acc *= PRIME_MX2;
239 return acc ^ (acc >> 28);
240}
241
242static uint64_t XXH3_len_9to16_64b(const uint8_t *input, size_t len,
243 const uint8_t *secret, uint64_t const seed) {
244 uint64_t input_lo =
245 (endian::read64le(secret + 24) ^ endian::read64le(secret + 32)) + seed;
246 uint64_t input_hi =
247 (endian::read64le(secret + 40) ^ endian::read64le(secret + 48)) - seed;
248 input_lo ^= endian::read64le(input);
249 input_hi ^= endian::read64le(input + len - 8);
250 uint64_t acc = uint64_t(len) + byteswap(input_lo) + input_hi +
251 XXH3_mul128_fold64(input_lo, input_hi);
252 return XXH3_avalanche(acc);
253}
254
256static uint64_t XXH3_len_0to16_64b(const uint8_t *input, size_t len,
257 const uint8_t *secret, uint64_t const seed) {
258 if (LLVM_LIKELY(len > 8))
259 return XXH3_len_9to16_64b(input, len, secret, seed);
260 if (LLVM_LIKELY(len >= 4))
261 return XXH3_len_4to8_64b(input, len, secret, seed);
262 if (len != 0)
263 return XXH3_len_1to3_64b(input, len, secret, seed);
264 return XXH64_avalanche(seed ^ endian::read64le(secret + 56) ^
265 endian::read64le(secret + 64));
266}
267
268static uint64_t XXH3_mix16B(const uint8_t *input, uint8_t const *secret,
269 uint64_t seed) {
270 uint64_t lhs = seed;
271 uint64_t rhs = 0U - seed;
272 lhs += endian::read64le(secret);
273 rhs += endian::read64le(secret + 8);
274 lhs ^= endian::read64le(input);
275 rhs ^= endian::read64le(input + 8);
276 return XXH3_mul128_fold64(lhs, rhs);
277}
278
279/* For mid range keys, XXH3 uses a Mum-hash variant. */
281static uint64_t XXH3_len_17to128_64b(const uint8_t *input, size_t len,
282 const uint8_t *secret,
283 uint64_t const seed) {
284 uint64_t acc = len * PRIME64_1, acc_end;
285 acc += XXH3_mix16B(input + 0, secret + 0, seed);
286 acc_end = XXH3_mix16B(input + len - 16, secret + 16, seed);
287 if (len > 32) {
288 acc += XXH3_mix16B(input + 16, secret + 32, seed);
289 acc_end += XXH3_mix16B(input + len - 32, secret + 48, seed);
290 if (len > 64) {
291 acc += XXH3_mix16B(input + 32, secret + 64, seed);
292 acc_end += XXH3_mix16B(input + len - 48, secret + 80, seed);
293 if (len > 96) {
294 acc += XXH3_mix16B(input + 48, secret + 96, seed);
295 acc_end += XXH3_mix16B(input + len - 64, secret + 112, seed);
296 }
297 }
298 }
299 return XXH3_avalanche(acc + acc_end);
300}
301
302constexpr size_t XXH3_MIDSIZE_MAX = 240;
303constexpr size_t XXH3_MIDSIZE_STARTOFFSET = 3;
304constexpr size_t XXH3_MIDSIZE_LASTOFFSET = 17;
305
307static uint64_t XXH3_len_129to240_64b(const uint8_t *input, size_t len,
308 const uint8_t *secret, uint64_t seed) {
309 uint64_t acc = (uint64_t)len * PRIME64_1;
310 const unsigned nbRounds = len / 16;
311 for (unsigned i = 0; i < 8; ++i)
312 acc += XXH3_mix16B(input + 16 * i, secret + 16 * i, seed);
313 acc = XXH3_avalanche(acc);
314
315 for (unsigned i = 8; i < nbRounds; ++i) {
316 acc += XXH3_mix16B(input + 16 * i,
317 secret + 16 * (i - 8) + XXH3_MIDSIZE_STARTOFFSET, seed);
318 }
319 /* last bytes */
320 acc +=
321 XXH3_mix16B(input + len - 16,
323 return XXH3_avalanche(acc);
324}
325
327static void XXH3_accumulate_512_scalar(uint64_t *acc, const uint8_t *input,
328 const uint8_t *secret) {
329 for (size_t i = 0; i < XXH_ACC_NB; ++i) {
330 uint64_t data_val = endian::read64le(input + 8 * i);
331 uint64_t data_key = data_val ^ endian::read64le(secret + 8 * i);
332 acc[i ^ 1] += data_val;
333 acc[i] += uint32_t(data_key) * (data_key >> 32);
334 }
335}
336
338static void XXH3_accumulate_scalar(uint64_t *acc, const uint8_t *input,
339 const uint8_t *secret, size_t nbStripes) {
340 for (size_t n = 0; n < nbStripes; ++n)
342 secret + n * XXH_SECRET_CONSUME_RATE);
343}
344
345static void XXH3_scrambleAcc(uint64_t *acc, const uint8_t *secret) {
346 for (size_t i = 0; i < XXH_ACC_NB; ++i) {
347 acc[i] ^= acc[i] >> 47;
348 acc[i] ^= endian::read64le(secret + 8 * i);
349 acc[i] *= PRIME32_1;
350 }
351}
352
353static uint64_t XXH3_mix2Accs(const uint64_t *acc, const uint8_t *secret) {
354 return XXH3_mul128_fold64(acc[0] ^ endian::read64le(secret),
355 acc[1] ^ endian::read64le(secret + 8));
356}
357
358static uint64_t XXH3_mergeAccs(const uint64_t *acc, const uint8_t *key,
359 uint64_t start) {
360 uint64_t result64 = start;
361 for (size_t i = 0; i < 4; ++i)
362 result64 += XXH3_mix2Accs(acc + 2 * i, key + 16 * i);
363 return XXH3_avalanche(result64);
364}
365
367static uint64_t XXH3_hashLong_64b(const uint8_t *input, size_t len,
368 const uint8_t *secret, size_t secretSize) {
369 const size_t nbStripesPerBlock =
371 const size_t block_len = XXH_STRIPE_LEN * nbStripesPerBlock;
372 const size_t nb_blocks = (len - 1) / block_len;
373 alignas(16) uint64_t acc[XXH_ACC_NB] = {
376 };
377 for (size_t n = 0; n < nb_blocks; ++n) {
378 XXH3_accumulate_scalar(acc, input + n * block_len, secret,
379 nbStripesPerBlock);
380 XXH3_scrambleAcc(acc, secret + secretSize - XXH_STRIPE_LEN);
381 }
382
383 /* last partial block */
384 const size_t nbStripes = (len - 1 - (block_len * nb_blocks)) / XXH_STRIPE_LEN;
385 assert(nbStripes <= secretSize / XXH_SECRET_CONSUME_RATE);
386 XXH3_accumulate_scalar(acc, input + nb_blocks * block_len, secret, nbStripes);
387
388 /* last stripe */
389 constexpr size_t XXH_SECRET_LASTACC_START = 7;
391 secret + secretSize - XXH_STRIPE_LEN -
392 XXH_SECRET_LASTACC_START);
393
394 /* converge into final hash */
395 constexpr size_t XXH_SECRET_MERGEACCS_START = 11;
396 return XXH3_mergeAccs(acc, secret + XXH_SECRET_MERGEACCS_START,
397 (uint64_t)len * PRIME64_1);
398}
399
401 auto *in = data.data();
402 size_t len = data.size();
403 if (len <= 16)
404 return XXH3_len_0to16_64b(in, len, kSecret, 0);
405 if (len <= 128)
406 return XXH3_len_17to128_64b(in, len, kSecret, 0);
407 if (len <= XXH3_MIDSIZE_MAX)
408 return XXH3_len_129to240_64b(in, len, kSecret, 0);
409 return XXH3_hashLong_64b(in, len, kSecret, sizeof(kSecret));
410}
411
412/* ==========================================
413 * XXH3 128 bits (a.k.a XXH128)
414 * ==========================================
415 * XXH3's 128-bit variant has better mixing and strength than the 64-bit
416 * variant, even without counting the significantly larger output size.
417 *
418 * For example, extra steps are taken to avoid the seed-dependent collisions
419 * in 17-240 byte inputs (See XXH3_mix16B and XXH128_mix32B).
420 *
421 * This strength naturally comes at the cost of some speed, especially on short
422 * lengths. Note that longer hashes are about as fast as the 64-bit version
423 * due to it using only a slight modification of the 64-bit loop.
424 *
425 * XXH128 is also more oriented towards 64-bit machines. It is still extremely
426 * fast for a _128-bit_ hash on 32-bit (it usually clears XXH64).
427 */
428
429/*!
430 * @internal
431 * @def XXH_rotl32(x,r)
432 * @brief 32-bit rotate left.
433 *
434 * @param x The 32-bit integer to be rotated.
435 * @param r The number of bits to rotate.
436 * @pre
437 * @p r > 0 && @p r < 32
438 * @note
439 * @p x and @p r may be evaluated multiple times.
440 * @return The rotated result.
441 */
442#if __has_builtin(__builtin_rotateleft32) && \
443 __has_builtin(__builtin_rotateleft64)
444#define XXH_rotl32 __builtin_rotateleft32
445#define XXH_rotl64 __builtin_rotateleft64
446/* Note: although _rotl exists for minGW (GCC under windows), performance seems
447 * poor */
448#elif defined(_MSC_VER)
449#define XXH_rotl32(x, r) _rotl(x, r)
450#define XXH_rotl64(x, r) _rotl64(x, r)
451#else
452#define XXH_rotl32(x, r) (((x) << (r)) | ((x) >> (32 - (r))))
453#define XXH_rotl64(x, r) (((x) << (r)) | ((x) >> (64 - (r))))
454#endif
455
456#if defined(_MSC_VER) && defined(_M_IX86)
457#define XXH_mult32to64(x, y) __emulu((unsigned)(x), (unsigned)(y))
458#else
459/*
460 * Downcast + upcast is usually better than masking on older compilers like
461 * GCC 4.2 (especially 32-bit ones), all without affecting newer compilers.
462 *
463 * The other method, (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF), will AND both operands
464 * and perform a full 64x64 multiply -- entirely redundant on 32-bit.
465 */
466#define XXH_mult32to64(x, y) ((uint64_t)(uint32_t)(x) * (uint64_t)(uint32_t)(y))
467#endif
468
469/*!
470 * @brief Calculates a 64->128-bit long multiply.
471 *
472 * Uses `__uint128_t` and `_umul128` if available, otherwise uses a scalar
473 * version.
474 *
475 * @param lhs , rhs The 64-bit integers to be multiplied
476 * @return The 128-bit result represented in an @ref XXH128_hash_t.
477 */
479 /*
480 * GCC/Clang __uint128_t method.
481 *
482 * On most 64-bit targets, GCC and Clang define a __uint128_t type.
483 * This is usually the best way as it usually uses a native long 64-bit
484 * multiply, such as MULQ on x86_64 or MUL + UMULH on aarch64.
485 *
486 * Usually.
487 *
488 * Despite being a 32-bit platform, Clang (and emscripten) define this type
489 * despite not having the arithmetic for it. This results in a laggy
490 * compiler builtin call which calculates a full 128-bit multiply.
491 * In that case it is best to use the portable one.
492 * https://github.com/Cyan4973/xxHash/issues/211#issuecomment-515575677
493 */
494#if (defined(__GNUC__) || defined(__clang__)) && !defined(__wasm__) && \
495 defined(__SIZEOF_INT128__) || \
496 (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128)
497
498 __uint128_t const product = (__uint128_t)lhs * (__uint128_t)rhs;
499 XXH128_hash_t r128;
500 r128.low64 = (uint64_t)(product);
501 r128.high64 = (uint64_t)(product >> 64);
502 return r128;
503
504 /*
505 * MSVC for x64's _umul128 method.
506 *
507 * uint64_t _umul128(uint64_t Multiplier, uint64_t Multiplicand, uint64_t
508 * *HighProduct);
509 *
510 * This compiles to single operand MUL on x64.
511 */
512#elif (defined(_M_X64) || defined(_M_IA64)) && !defined(_M_ARM64EC)
513
514#ifndef _MSC_VER
515#pragma intrinsic(_umul128)
516#endif
517 uint64_t product_high;
518 uint64_t const product_low = _umul128(lhs, rhs, &product_high);
519 XXH128_hash_t r128;
520 r128.low64 = product_low;
521 r128.high64 = product_high;
522 return r128;
523
524 /*
525 * MSVC for ARM64's __umulh method.
526 *
527 * This compiles to the same MUL + UMULH as GCC/Clang's __uint128_t method.
528 */
529#elif defined(_M_ARM64) || defined(_M_ARM64EC)
530
531#ifndef _MSC_VER
532#pragma intrinsic(__umulh)
533#endif
534 XXH128_hash_t r128;
535 r128.low64 = lhs * rhs;
536 r128.high64 = __umulh(lhs, rhs);
537 return r128;
538
539#else
540 /*
541 * Portable scalar method. Optimized for 32-bit and 64-bit ALUs.
542 *
543 * This is a fast and simple grade school multiply, which is shown below
544 * with base 10 arithmetic instead of base 0x100000000.
545 *
546 * 9 3 // D2 lhs = 93
547 * x 7 5 // D2 rhs = 75
548 * ----------
549 * 1 5 // D2 lo_lo = (93 % 10) * (75 % 10) = 15
550 * 4 5 | // D2 hi_lo = (93 / 10) * (75 % 10) = 45
551 * 2 1 | // D2 lo_hi = (93 % 10) * (75 / 10) = 21
552 * + 6 3 | | // D2 hi_hi = (93 / 10) * (75 / 10) = 63
553 * ---------
554 * 2 7 | // D2 cross = (15 / 10) + (45 % 10) + 21 = 27
555 * + 6 7 | | // D2 upper = (27 / 10) + (45 / 10) + 63 = 67
556 * ---------
557 * 6 9 7 5 // D4 res = (27 * 10) + (15 % 10) + (67 * 100) = 6975
558 *
559 * The reasons for adding the products like this are:
560 * 1. It avoids manual carry tracking. Just like how
561 * (9 * 9) + 9 + 9 = 99, the same applies with this for UINT64_MAX.
562 * This avoids a lot of complexity.
563 *
564 * 2. It hints for, and on Clang, compiles to, the powerful UMAAL
565 * instruction available in ARM's Digital Signal Processing extension
566 * in 32-bit ARMv6 and later, which is shown below:
567 *
568 * void UMAAL(xxh_u32 *RdLo, xxh_u32 *RdHi, xxh_u32 Rn, xxh_u32 Rm)
569 * {
570 * uint64_t product = (uint64_t)*RdLo * (uint64_t)*RdHi + Rn + Rm;
571 * *RdLo = (xxh_u32)(product & 0xFFFFFFFF);
572 * *RdHi = (xxh_u32)(product >> 32);
573 * }
574 *
575 * This instruction was designed for efficient long multiplication, and
576 * allows this to be calculated in only 4 instructions at speeds
577 * comparable to some 64-bit ALUs.
578 *
579 * 3. It isn't terrible on other platforms. Usually this will be a couple
580 * of 32-bit ADD/ADCs.
581 */
582
583 /* First calculate all of the cross products. */
584 uint64_t const lo_lo = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs & 0xFFFFFFFF);
585 uint64_t const hi_lo = XXH_mult32to64(lhs >> 32, rhs & 0xFFFFFFFF);
586 uint64_t const lo_hi = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs >> 32);
587 uint64_t const hi_hi = XXH_mult32to64(lhs >> 32, rhs >> 32);
588
589 /* Now add the products together. These will never overflow. */
590 uint64_t const cross = (lo_lo >> 32) + (hi_lo & 0xFFFFFFFF) + lo_hi;
591 uint64_t const upper = (hi_lo >> 32) + (cross >> 32) + hi_hi;
592 uint64_t const lower = (cross << 32) | (lo_lo & 0xFFFFFFFF);
593
594 XXH128_hash_t r128;
595 r128.low64 = lower;
596 r128.high64 = upper;
597 return r128;
598#endif
599}
600
601/*! Seems to produce slightly better code on GCC for some reason. */
603 int shift) {
604 return v64 ^ (v64 >> shift);
605}
606
608XXH3_len_1to3_128b(const uint8_t *input, size_t len, const uint8_t *secret,
609 uint64_t seed) {
610 /* A doubled version of 1to3_64b with different constants. */
611 /*
612 * len = 1: combinedl = { input[0], 0x01, input[0], input[0] }
613 * len = 2: combinedl = { input[1], 0x02, input[0], input[1] }
614 * len = 3: combinedl = { input[2], 0x03, input[0], input[1] }
615 */
616 uint8_t const c1 = input[0];
617 uint8_t const c2 = input[len >> 1];
618 uint8_t const c3 = input[len - 1];
619 uint32_t const combinedl = ((uint32_t)c1 << 16) | ((uint32_t)c2 << 24) |
620 ((uint32_t)c3 << 0) | ((uint32_t)len << 8);
621 uint32_t const combinedh = XXH_rotl32(byteswap(combinedl), 13);
622 uint64_t const bitflipl =
623 (endian::read32le(secret) ^ endian::read32le(secret + 4)) + seed;
624 uint64_t const bitfliph =
625 (endian::read32le(secret + 8) ^ endian::read32le(secret + 12)) - seed;
626 uint64_t const keyed_lo = (uint64_t)combinedl ^ bitflipl;
627 uint64_t const keyed_hi = (uint64_t)combinedh ^ bitfliph;
628 XXH128_hash_t h128;
629 h128.low64 = XXH64_avalanche(keyed_lo);
630 h128.high64 = XXH64_avalanche(keyed_hi);
631 return h128;
632}
633
635XXH3_len_4to8_128b(const uint8_t *input, size_t len, const uint8_t *secret,
636 uint64_t seed) {
637 seed ^= (uint64_t)byteswap((uint32_t)seed) << 32;
638 uint32_t const input_lo = endian::read32le(input);
639 uint32_t const input_hi = endian::read32le(input + len - 4);
640 uint64_t const input_64 = input_lo + ((uint64_t)input_hi << 32);
641 uint64_t const bitflip =
642 (endian::read64le(secret + 16) ^ endian::read64le(secret + 24)) + seed;
643 uint64_t const keyed = input_64 ^ bitflip;
644
645 /* Shift len to the left to ensure it is even, this avoids even multiplies.
646 */
647 XXH128_hash_t m128 = XXH_mult64to128(keyed, PRIME64_1 + (len << 2));
648
649 m128.high64 += (m128.low64 << 1);
650 m128.low64 ^= (m128.high64 >> 3);
651
652 m128.low64 = XXH_xorshift64(m128.low64, 35);
653 m128.low64 *= PRIME_MX2;
654 m128.low64 = XXH_xorshift64(m128.low64, 28);
655 m128.high64 = XXH3_avalanche(m128.high64);
656 return m128;
657}
658
660XXH3_len_9to16_128b(const uint8_t *input, size_t len, const uint8_t *secret,
661 uint64_t seed) {
662 uint64_t const bitflipl =
663 (endian::read64le(secret + 32) ^ endian::read64le(secret + 40)) - seed;
664 uint64_t const bitfliph =
665 (endian::read64le(secret + 48) ^ endian::read64le(secret + 56)) + seed;
666 uint64_t const input_lo = endian::read64le(input);
667 uint64_t input_hi = endian::read64le(input + len - 8);
668 XXH128_hash_t m128 =
669 XXH_mult64to128(input_lo ^ input_hi ^ bitflipl, PRIME64_1);
670 /*
671 * Put len in the middle of m128 to ensure that the length gets mixed to
672 * both the low and high bits in the 128x64 multiply below.
673 */
674 m128.low64 += (uint64_t)(len - 1) << 54;
675 input_hi ^= bitfliph;
676 /*
677 * Add the high 32 bits of input_hi to the high 32 bits of m128, then
678 * add the long product of the low 32 bits of input_hi and PRIME32_2 to
679 * the high 64 bits of m128.
680 *
681 * The best approach to this operation is different on 32-bit and 64-bit.
682 */
683 if (sizeof(void *) < sizeof(uint64_t)) { /* 32-bit */
684 /*
685 * 32-bit optimized version, which is more readable.
686 *
687 * On 32-bit, it removes an ADC and delays a dependency between the two
688 * halves of m128.high64, but it generates an extra mask on 64-bit.
689 */
690 m128.high64 += (input_hi & 0xFFFFFFFF00000000ULL) +
692 } else {
693 /*
694 * 64-bit optimized (albeit more confusing) version.
695 *
696 * Uses some properties of addition and multiplication to remove the mask:
697 *
698 * Let:
699 * a = input_hi.lo = (input_hi & 0x00000000FFFFFFFF)
700 * b = input_hi.hi = (input_hi & 0xFFFFFFFF00000000)
701 * c = PRIME32_2
702 *
703 * a + (b * c)
704 * Inverse Property: x + y - x == y
705 * a + (b * (1 + c - 1))
706 * Distributive Property: x * (y + z) == (x * y) + (x * z)
707 * a + (b * 1) + (b * (c - 1))
708 * Identity Property: x * 1 == x
709 * a + b + (b * (c - 1))
710 *
711 * Substitute a, b, and c:
712 * input_hi.hi + input_hi.lo + ((uint64_t)input_hi.lo * (PRIME32_2
713 * - 1))
714 *
715 * Since input_hi.hi + input_hi.lo == input_hi, we get this:
716 * input_hi + ((uint64_t)input_hi.lo * (PRIME32_2 - 1))
717 */
718 m128.high64 += input_hi + XXH_mult32to64((uint32_t)input_hi, PRIME32_2 - 1);
719 }
720 /* m128 ^= XXH_swap64(m128 >> 64); */
721 m128.low64 ^= byteswap(m128.high64);
722
723 /* 128x64 multiply: h128 = m128 * PRIME64_2; */
725 h128.high64 += m128.high64 * PRIME64_2;
726
727 h128.low64 = XXH3_avalanche(h128.low64);
728 h128.high64 = XXH3_avalanche(h128.high64);
729 return h128;
730}
731
732/*
733 * Assumption: `secret` size is >= XXH3_SECRET_SIZE_MIN
734 */
736XXH3_len_0to16_128b(const uint8_t *input, size_t len, const uint8_t *secret,
737 uint64_t seed) {
738 if (len > 8)
739 return XXH3_len_9to16_128b(input, len, secret, seed);
740 if (len >= 4)
741 return XXH3_len_4to8_128b(input, len, secret, seed);
742 if (len)
743 return XXH3_len_1to3_128b(input, len, secret, seed);
744 XXH128_hash_t h128;
745 uint64_t const bitflipl =
746 endian::read64le(secret + 64) ^ endian::read64le(secret + 72);
747 uint64_t const bitfliph =
748 endian::read64le(secret + 80) ^ endian::read64le(secret + 88);
749 h128.low64 = XXH64_avalanche(seed ^ bitflipl);
750 h128.high64 = XXH64_avalanche(seed ^ bitfliph);
751 return h128;
752}
753
754/*
755 * A bit slower than XXH3_mix16B, but handles multiply by zero better.
756 */
758XXH128_mix32B(XXH128_hash_t acc, const uint8_t *input_1, const uint8_t *input_2,
759 const uint8_t *secret, uint64_t seed) {
760 acc.low64 += XXH3_mix16B(input_1, secret + 0, seed);
761 acc.low64 ^= endian::read64le(input_2) + endian::read64le(input_2 + 8);
762 acc.high64 += XXH3_mix16B(input_2, secret + 16, seed);
763 acc.high64 ^= endian::read64le(input_1) + endian::read64le(input_1 + 8);
764 return acc;
765}
766
768XXH3_len_17to128_128b(const uint8_t *input, size_t len, const uint8_t *secret,
769 size_t secretSize, uint64_t seed) {
770 (void)secretSize;
771
772 XXH128_hash_t acc;
773 acc.low64 = len * PRIME64_1;
774 acc.high64 = 0;
775
776 if (len > 32) {
777 if (len > 64) {
778 if (len > 96) {
779 acc =
780 XXH128_mix32B(acc, input + 48, input + len - 64, secret + 96, seed);
781 }
782 acc = XXH128_mix32B(acc, input + 32, input + len - 48, secret + 64, seed);
783 }
784 acc = XXH128_mix32B(acc, input + 16, input + len - 32, secret + 32, seed);
785 }
786 acc = XXH128_mix32B(acc, input, input + len - 16, secret, seed);
787 XXH128_hash_t h128;
788 h128.low64 = acc.low64 + acc.high64;
789 h128.high64 = (acc.low64 * PRIME64_1) + (acc.high64 * PRIME64_4) +
790 ((len - seed) * PRIME64_2);
791 h128.low64 = XXH3_avalanche(h128.low64);
792 h128.high64 = (uint64_t)0 - XXH3_avalanche(h128.high64);
793 return h128;
794}
795
797XXH3_len_129to240_128b(const uint8_t *input, size_t len, const uint8_t *secret,
798 size_t secretSize, uint64_t seed) {
799 (void)secretSize;
800
801 XXH128_hash_t acc;
802 unsigned i;
803 acc.low64 = len * PRIME64_1;
804 acc.high64 = 0;
805 /*
806 * We set as `i` as offset + 32. We do this so that unchanged
807 * `len` can be used as upper bound. This reaches a sweet spot
808 * where both x86 and aarch64 get simple agen and good codegen
809 * for the loop.
810 */
811 for (i = 32; i < 160; i += 32) {
812 acc = XXH128_mix32B(acc, input + i - 32, input + i - 16, secret + i - 32,
813 seed);
814 }
815 acc.low64 = XXH3_avalanche(acc.low64);
816 acc.high64 = XXH3_avalanche(acc.high64);
817 /*
818 * NB: `i <= len` will duplicate the last 32-bytes if
819 * len % 32 was zero. This is an unfortunate necessity to keep
820 * the hash result stable.
821 */
822 for (i = 160; i <= len; i += 32) {
823 acc = XXH128_mix32B(acc, input + i - 32, input + i - 16,
824 secret + XXH3_MIDSIZE_STARTOFFSET + i - 160, seed);
825 }
826 /* last bytes */
827 acc =
828 XXH128_mix32B(acc, input + len - 16, input + len - 32,
830 (uint64_t)0 - seed);
831
832 XXH128_hash_t h128;
833 h128.low64 = acc.low64 + acc.high64;
834 h128.high64 = (acc.low64 * PRIME64_1) + (acc.high64 * PRIME64_4) +
835 ((len - seed) * PRIME64_2);
836 h128.low64 = XXH3_avalanche(h128.low64);
837 h128.high64 = (uint64_t)0 - XXH3_avalanche(h128.high64);
838 return h128;
839}
840
842XXH3_hashLong_128b(const uint8_t *input, size_t len, const uint8_t *secret,
843 size_t secretSize) {
844 const size_t nbStripesPerBlock =
846 const size_t block_len = XXH_STRIPE_LEN * nbStripesPerBlock;
847 const size_t nb_blocks = (len - 1) / block_len;
848 alignas(16) uint64_t acc[XXH_ACC_NB] = {
851 };
852
853 for (size_t n = 0; n < nb_blocks; ++n) {
854 XXH3_accumulate_scalar(acc, input + n * block_len, secret,
855 nbStripesPerBlock);
856 XXH3_scrambleAcc(acc, secret + secretSize - XXH_STRIPE_LEN);
857 }
858
859 /* last partial block */
860 const size_t nbStripes = (len - 1 - (block_len * nb_blocks)) / XXH_STRIPE_LEN;
861 assert(nbStripes <= secretSize / XXH_SECRET_CONSUME_RATE);
862 XXH3_accumulate_scalar(acc, input + nb_blocks * block_len, secret, nbStripes);
863
864 /* last stripe */
865 constexpr size_t XXH_SECRET_LASTACC_START = 7;
867 secret + secretSize - XXH_STRIPE_LEN -
868 XXH_SECRET_LASTACC_START);
869
870 /* converge into final hash */
871 static_assert(sizeof(acc) == 64);
872 XXH128_hash_t h128;
873 constexpr size_t XXH_SECRET_MERGEACCS_START = 11;
874 h128.low64 = XXH3_mergeAccs(acc, secret + XXH_SECRET_MERGEACCS_START,
875 (uint64_t)len * PRIME64_1);
876 h128.high64 = XXH3_mergeAccs(
877 acc, secret + secretSize - sizeof(acc) - XXH_SECRET_MERGEACCS_START,
878 ~((uint64_t)len * PRIME64_2));
879 return h128;
880}
881
883 size_t len = data.size();
884 const uint8_t *input = data.data();
885
886 /*
887 * If an action is to be taken if `secret` conditions are not respected,
888 * it should be done here.
889 * For now, it's a contract pre-condition.
890 * Adding a check and a branch here would cost performance at every hash.
891 */
892 if (len <= 16)
893 return XXH3_len_0to16_128b(input, len, kSecret, /*seed64=*/0);
894 if (len <= 128)
895 return XXH3_len_17to128_128b(input, len, kSecret, sizeof(kSecret),
896 /*seed64=*/0);
897 if (len <= XXH3_MIDSIZE_MAX)
898 return XXH3_len_129to240_128b(input, len, kSecret, sizeof(kSecret),
899 /*seed64=*/0);
900 return XXH3_hashLong_128b(input, len, kSecret, sizeof(kSecret));
901}
#define LLVM_ATTRIBUTE_ALWAYS_INLINE
LLVM_ATTRIBUTE_ALWAYS_INLINE - On compilers where we have a directive to do so, mark a method "always...
Definition: Compiler.h:261
#define LLVM_ATTRIBUTE_NOINLINE
LLVM_ATTRIBUTE_NOINLINE - On compilers where we have a directive to do so, mark a method "not for inl...
Definition: Compiler.h:251
#define LLVM_LIKELY(EXPR)
Definition: Compiler.h:240
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
#define P(N)
static ManagedStatic< cl::opt< uint64_t >, CreateSeed > Seed
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
const T * data() const
Definition: ArrayRef.h:162
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
uint64_t read64le(const void *P)
Definition: Endian.h:428
uint32_t read32le(const void *P)
Definition: Endian.h:425
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
uint64_t xxh3_64bits(ArrayRef< uint8_t > data)
Definition: xxhash.cpp:400
constexpr T byteswap(T V) noexcept
Reverses the bytes in the given integer value V.
Definition: bit.h:101
XXH128_hash_t xxh3_128bits(ArrayRef< uint8_t > data)
XXH3's 128-bit variant.
Definition: xxhash.cpp:882
uint64_t xxHash64(llvm::StringRef Data)
Definition: xxhash.cpp:90
The return value from 128-bit hashes.
Definition: xxhash.h:64
uint64_t low64
value & 0xFFFFFFFFFFFFFFFF
Definition: xxhash.h:65
uint64_t high64
value >> 64
Definition: xxhash.h:66
static uint64_t XXH3_len_9to16_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t const seed)
Definition: xxhash.cpp:242
static uint64_t mergeRound(uint64_t Acc, uint64_t Val)
Definition: xxhash.cpp:74
#define XXH_mult32to64(x, y)
Definition: xxhash.cpp:466
static uint64_t XXH3_len_4to8_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:225
static LLVM_ATTRIBUTE_NOINLINE uint64_t XXH3_hashLong_64b(const uint8_t *input, size_t len, const uint8_t *secret, size_t secretSize)
Definition: xxhash.cpp:367
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_len_1to3_128b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:608
static uint64_t XXH3_len_1to3_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:212
static const uint64_t PRIME64_3
Definition: xxhash.cpp:63
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH128_mix32B(XXH128_hash_t acc, const uint8_t *input_1, const uint8_t *input_2, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:758
static uint64_t XXH3_mergeAccs(const uint64_t *acc, const uint8_t *key, uint64_t start)
Definition: xxhash.cpp:358
static uint64_t XXH3_mix16B(const uint8_t *input, uint8_t const *secret, uint64_t seed)
Definition: xxhash.cpp:268
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_len_17to128_128b(const uint8_t *input, size_t len, const uint8_t *secret, size_t secretSize, uint64_t seed)
Definition: xxhash.cpp:768
static const uint64_t PRIME64_1
Definition: xxhash.cpp:61
static XXH128_hash_t XXH_mult64to128(uint64_t lhs, uint64_t rhs)
Calculates a 64->128-bit long multiply.
Definition: xxhash.cpp:478
static uint64_t XXH3_avalanche(uint64_t hash)
Definition: xxhash.cpp:205
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_len_4to8_128b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:635
constexpr size_t XXH3_SECRETSIZE_MIN
Definition: xxhash.cpp:154
static LLVM_ATTRIBUTE_NOINLINE XXH128_hash_t XXH3_len_129to240_128b(const uint8_t *input, size_t len, const uint8_t *secret, size_t secretSize, uint64_t seed)
Definition: xxhash.cpp:797
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_len_9to16_128b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:660
constexpr uint32_t PRIME32_1
Definition: xxhash.cpp:57
constexpr uint32_t PRIME32_2
Definition: xxhash.cpp:58
static LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_len_0to16_128b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:736
#define XXH_rotl32(x, r)
Definition: xxhash.cpp:452
static const uint64_t PRIME64_2
Definition: xxhash.cpp:62
static void XXH3_scrambleAcc(uint64_t *acc, const uint8_t *secret)
Definition: xxhash.cpp:345
constexpr size_t XXH3_MIDSIZE_MAX
Definition: xxhash.cpp:302
constexpr uint8_t kSecret[XXH_SECRET_DEFAULT_SIZE]
Definition: xxhash.cpp:159
static LLVM_ATTRIBUTE_ALWAYS_INLINE uint64_t XXH3_len_17to128_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t const seed)
Definition: xxhash.cpp:281
static LLVM_ATTRIBUTE_NOINLINE uint64_t XXH3_len_129to240_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t seed)
Definition: xxhash.cpp:307
constexpr uint32_t PRIME32_3
Definition: xxhash.cpp:59
constexpr size_t XXH_STRIPE_LEN
Definition: xxhash.cpp:201
static const uint64_t PRIME64_4
Definition: xxhash.cpp:64
constexpr size_t XXH_ACC_NB
Definition: xxhash.cpp:203
static const uint64_t PRIME64_5
Definition: xxhash.cpp:65
LLVM_ATTRIBUTE_ALWAYS_INLINE constexpr uint64_t XXH_xorshift64(uint64_t v64, int shift)
Seems to produce slightly better code on GCC for some reason.
Definition: xxhash.cpp:602
LLVM_ATTRIBUTE_ALWAYS_INLINE XXH128_hash_t XXH3_hashLong_128b(const uint8_t *input, size_t len, const uint8_t *secret, size_t secretSize)
Definition: xxhash.cpp:842
static uint64_t rotl64(uint64_t X, size_t R)
Definition: xxhash.cpp:53
static uint64_t XXH64_avalanche(uint64_t hash)
Definition: xxhash.cpp:81
constexpr size_t XXH_SECRET_DEFAULT_SIZE
Definition: xxhash.cpp:155
constexpr uint64_t PRIME_MX1
Definition: xxhash.cpp:175
static LLVM_ATTRIBUTE_ALWAYS_INLINE void XXH3_accumulate_512_scalar(uint64_t *acc, const uint8_t *input, const uint8_t *secret)
Definition: xxhash.cpp:327
static uint64_t XXH3_mix2Accs(const uint64_t *acc, const uint8_t *secret)
Definition: xxhash.cpp:353
constexpr size_t XXH3_MIDSIZE_STARTOFFSET
Definition: xxhash.cpp:303
static LLVM_ATTRIBUTE_ALWAYS_INLINE uint64_t XXH3_len_0to16_64b(const uint8_t *input, size_t len, const uint8_t *secret, uint64_t const seed)
Definition: xxhash.cpp:256
static uint64_t XXH3_mul128_fold64(uint64_t lhs, uint64_t rhs)
Definition: xxhash.cpp:179
static uint64_t round(uint64_t Acc, uint64_t Input)
Definition: xxhash.cpp:67
constexpr size_t XXH_SECRET_CONSUME_RATE
Definition: xxhash.cpp:202
constexpr uint64_t PRIME_MX2
Definition: xxhash.cpp:176
static LLVM_ATTRIBUTE_ALWAYS_INLINE void XXH3_accumulate_scalar(uint64_t *acc, const uint8_t *input, const uint8_t *secret, size_t nbStripes)
Definition: xxhash.cpp:338
constexpr size_t XXH3_MIDSIZE_LASTOFFSET
Definition: xxhash.cpp:304