2 * xxHash - Fast Hash algorithm
3 * Copyright (c) Meta Platforms, Inc. and affiliates.
5 * You can contact the author at :
6 * - xxHash homepage: https://cyan4973.github.io/xxHash/
7 * - xxHash source repository : https://github.com/Cyan4973/xxHash
9 * This source code is licensed under both the BSD-style license (found in the
10 * LICENSE file in the root directory of this source tree) and the GPLv2 (found
11 * in the COPYING file in the root directory of this source tree).
12 * You may select, at your option, one of the above-listed licenses.
21 # define XXH_NAMESPACE ZSTD_
28 * xxHash prototypes and implementation
31 /* Notice extracted from xxHash homepage:
33 xxHash is an extremely fast hash algorithm, running at RAM speed limits.
34 It also successfully passes all tests from the SMHasher suite.
36 Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz)
38 Name Speed Q.Score Author
40 CrapWow 3.2 GB/s 2 Andrew
41 MurmurHash 3a 2.7 GB/s 10 Austin Appleby
42 SpookyHash 2.0 GB/s 10 Bob Jenkins
43 SBox 1.4 GB/s 9 Bret Mulvey
44 Lookup3 1.2 GB/s 9 Bob Jenkins
45 SuperFastHash 1.2 GB/s 1 Paul Hsieh
46 CityHash64 1.05 GB/s 10 Pike & Alakuijala
47 FNV 0.55 GB/s 5 Fowler, Noll, Vo
49 MD5-32 0.33 GB/s 10 Ronald L. Rivest
52 Q.Score is a measure of quality of the hash function.
53 It depends on successfully passing SMHasher test set.
54 10 is a perfect score.
56 Note: SMHasher's CRC32 implementation is not the fastest one.
57 Other speed-oriented implementations can be faster,
58 especially in combination with PCLMUL instruction:
59 https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html?showComment=1552696407071#c3490092340461170735
61 A 64-bit version, named XXH64, is available since r35.
62 It offers much better speed, but for 64-bit applications only.
63 Name Speed on 64 bits Speed on 32 bits
64 XXH64 13.8 GB/s 1.9 GB/s
65 XXH32 6.8 GB/s 6.0 GB/s
68 #if defined (__cplusplus)
72 /* ****************************
74 ******************************/
76 * XXH_INLINE_ALL (and XXH_PRIVATE_API)
77 * Use these build macros to inline xxhash into the target unit.
78 * Inlining improves performance on small inputs, especially when the length is
79 * expressed as a compile-time constant:
81 * https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html
83 * It also keeps xxHash symbols private to the unit, so they are not exported.
86 * #define XXH_INLINE_ALL
89 * Do not compile and link xxhash.o as a separate object, as it is not useful.
91 #if (defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)) \
92 && !defined(XXH_INLINE_ALL_31684351384)
93 /* this section should be traversed only once */
94 # define XXH_INLINE_ALL_31684351384
95 /* give access to the advanced API, required to compile implementations */
96 # undef XXH_STATIC_LINKING_ONLY /* avoid macro redef */
97 # define XXH_STATIC_LINKING_ONLY
98 /* make all functions private */
99 # undef XXH_PUBLIC_API
100 # if defined(__GNUC__)
101 # define XXH_PUBLIC_API static __inline __attribute__((unused))
102 # elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
103 # define XXH_PUBLIC_API static inline
104 # elif defined(_MSC_VER)
105 # define XXH_PUBLIC_API static __inline
107 /* note: this version may generate warnings for unused static functions */
108 # define XXH_PUBLIC_API static
112 * This part deals with the special case where a unit wants to inline xxHash,
113 * but "xxhash.h" has previously been included without XXH_INLINE_ALL,
114 * such as part of some previously included *.h header file.
115 * Without further action, the new include would just be ignored,
116 * and functions would effectively _not_ be inlined (silent failure).
117 * The following macros solve this situation by prefixing all inlined names,
118 * avoiding naming collision with previous inclusions.
120 /* Before that, we unconditionally #undef all symbols,
121 * in case they were already defined with XXH_NAMESPACE.
122 * They will then be redefined for XXH_INLINE_ALL
124 # undef XXH_versionNumber
127 # undef XXH32_createState
128 # undef XXH32_freeState
132 # undef XXH32_copyState
133 # undef XXH32_canonicalFromHash
134 # undef XXH32_hashFromCanonical
137 # undef XXH64_createState
138 # undef XXH64_freeState
142 # undef XXH64_copyState
143 # undef XXH64_canonicalFromHash
144 # undef XXH64_hashFromCanonical
147 # undef XXH3_64bits_withSecret
148 # undef XXH3_64bits_withSeed
149 # undef XXH3_64bits_withSecretandSeed
150 # undef XXH3_createState
151 # undef XXH3_freeState
152 # undef XXH3_copyState
153 # undef XXH3_64bits_reset
154 # undef XXH3_64bits_reset_withSeed
155 # undef XXH3_64bits_reset_withSecret
156 # undef XXH3_64bits_update
157 # undef XXH3_64bits_digest
158 # undef XXH3_generateSecret
162 # undef XXH3_128bits_withSeed
163 # undef XXH3_128bits_withSecret
164 # undef XXH3_128bits_reset
165 # undef XXH3_128bits_reset_withSeed
166 # undef XXH3_128bits_reset_withSecret
167 # undef XXH3_128bits_reset_withSecretandSeed
168 # undef XXH3_128bits_update
169 # undef XXH3_128bits_digest
170 # undef XXH128_isEqual
172 # undef XXH128_canonicalFromHash
173 # undef XXH128_hashFromCanonical
174 /* Finally, free the namespace itself */
175 # undef XXH_NAMESPACE
177 /* employ the namespace for XXH_INLINE_ALL */
178 # define XXH_NAMESPACE XXH_INLINE_
180 * Some identifiers (enums, type names) are not symbols,
181 * but they must nonetheless be renamed to avoid redeclaration.
182 * Alternative solution: do not redeclare them.
183 * However, this requires some #ifdefs, and has a more dispersed impact.
184 * Meanwhile, renaming can be achieved in a single place.
186 # define XXH_IPREF(Id) XXH_NAMESPACE ## Id
187 # define XXH_OK XXH_IPREF(XXH_OK)
188 # define XXH_ERROR XXH_IPREF(XXH_ERROR)
189 # define XXH_errorcode XXH_IPREF(XXH_errorcode)
190 # define XXH32_canonical_t XXH_IPREF(XXH32_canonical_t)
191 # define XXH64_canonical_t XXH_IPREF(XXH64_canonical_t)
192 # define XXH128_canonical_t XXH_IPREF(XXH128_canonical_t)
193 # define XXH32_state_s XXH_IPREF(XXH32_state_s)
194 # define XXH32_state_t XXH_IPREF(XXH32_state_t)
195 # define XXH64_state_s XXH_IPREF(XXH64_state_s)
196 # define XXH64_state_t XXH_IPREF(XXH64_state_t)
197 # define XXH3_state_s XXH_IPREF(XXH3_state_s)
198 # define XXH3_state_t XXH_IPREF(XXH3_state_t)
199 # define XXH128_hash_t XXH_IPREF(XXH128_hash_t)
200 /* Ensure the header is parsed again, even if it was previously included */
201 # undef XXHASH_H_5627135585666179
202 # undef XXHASH_H_STATIC_13879238742
203 #endif /* XXH_INLINE_ALL || XXH_PRIVATE_API */
207 /* ****************************************************************
209 *****************************************************************/
210 #ifndef XXHASH_H_5627135585666179
211 #define XXHASH_H_5627135585666179 1
215 * @defgroup public Public API
216 * Contains details on the public xxHash functions.
219 /* specific declaration modes for Windows */
220 #if !defined(XXH_INLINE_ALL) && !defined(XXH_PRIVATE_API)
221 # if defined(WIN32) && defined(_MSC_VER) && (defined(XXH_IMPORT) || defined(XXH_EXPORT))
223 # define XXH_PUBLIC_API __declspec(dllexport)
225 # define XXH_PUBLIC_API __declspec(dllimport)
228 # define XXH_PUBLIC_API /* do nothing */
234 * @brief Emulate a namespace by transparently prefixing all symbols.
236 * If you want to include _and expose_ xxHash functions from within your own
237 * library, but also want to avoid symbol collisions with other libraries which
238 * may also include xxHash, you can use XXH_NAMESPACE to automatically prefix
239 * any public symbol from xxhash library with the value of XXH_NAMESPACE
240 * (therefore, avoid empty or numeric values).
242 * Note that no change is required within the calling program as long as it
243 * includes `xxhash.h`: Regular symbol names will be automatically translated
246 # define XXH_NAMESPACE /* YOUR NAME HERE */
247 # undef XXH_NAMESPACE
251 # define XXH_CAT(A,B) A##B
252 # define XXH_NAME2(A,B) XXH_CAT(A,B)
253 # define XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, XXH_versionNumber)
255 # define XXH32 XXH_NAME2(XXH_NAMESPACE, XXH32)
256 # define XXH32_createState XXH_NAME2(XXH_NAMESPACE, XXH32_createState)
257 # define XXH32_freeState XXH_NAME2(XXH_NAMESPACE, XXH32_freeState)
258 # define XXH32_reset XXH_NAME2(XXH_NAMESPACE, XXH32_reset)
259 # define XXH32_update XXH_NAME2(XXH_NAMESPACE, XXH32_update)
260 # define XXH32_digest XXH_NAME2(XXH_NAMESPACE, XXH32_digest)
261 # define XXH32_copyState XXH_NAME2(XXH_NAMESPACE, XXH32_copyState)
262 # define XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH32_canonicalFromHash)
263 # define XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH32_hashFromCanonical)
265 # define XXH64 XXH_NAME2(XXH_NAMESPACE, XXH64)
266 # define XXH64_createState XXH_NAME2(XXH_NAMESPACE, XXH64_createState)
267 # define XXH64_freeState XXH_NAME2(XXH_NAMESPACE, XXH64_freeState)
268 # define XXH64_reset XXH_NAME2(XXH_NAMESPACE, XXH64_reset)
269 # define XXH64_update XXH_NAME2(XXH_NAMESPACE, XXH64_update)
270 # define XXH64_digest XXH_NAME2(XXH_NAMESPACE, XXH64_digest)
271 # define XXH64_copyState XXH_NAME2(XXH_NAMESPACE, XXH64_copyState)
272 # define XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH64_canonicalFromHash)
273 # define XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH64_hashFromCanonical)
275 # define XXH3_64bits XXH_NAME2(XXH_NAMESPACE, XXH3_64bits)
276 # define XXH3_64bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSecret)
277 # define XXH3_64bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSeed)
278 # define XXH3_64bits_withSecretandSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSecretandSeed)
279 # define XXH3_createState XXH_NAME2(XXH_NAMESPACE, XXH3_createState)
280 # define XXH3_freeState XXH_NAME2(XXH_NAMESPACE, XXH3_freeState)
281 # define XXH3_copyState XXH_NAME2(XXH_NAMESPACE, XXH3_copyState)
282 # define XXH3_64bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset)
283 # define XXH3_64bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSeed)
284 # define XXH3_64bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSecret)
285 # define XXH3_64bits_reset_withSecretandSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSecretandSeed)
286 # define XXH3_64bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_update)
287 # define XXH3_64bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_digest)
288 # define XXH3_generateSecret XXH_NAME2(XXH_NAMESPACE, XXH3_generateSecret)
289 # define XXH3_generateSecret_fromSeed XXH_NAME2(XXH_NAMESPACE, XXH3_generateSecret_fromSeed)
291 # define XXH128 XXH_NAME2(XXH_NAMESPACE, XXH128)
292 # define XXH3_128bits XXH_NAME2(XXH_NAMESPACE, XXH3_128bits)
293 # define XXH3_128bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSeed)
294 # define XXH3_128bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSecret)
295 # define XXH3_128bits_withSecretandSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSecretandSeed)
296 # define XXH3_128bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset)
297 # define XXH3_128bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSeed)
298 # define XXH3_128bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSecret)
299 # define XXH3_128bits_reset_withSecretandSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSecretandSeed)
300 # define XXH3_128bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_update)
301 # define XXH3_128bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_digest)
302 # define XXH128_isEqual XXH_NAME2(XXH_NAMESPACE, XXH128_isEqual)
303 # define XXH128_cmp XXH_NAME2(XXH_NAMESPACE, XXH128_cmp)
304 # define XXH128_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH128_canonicalFromHash)
305 # define XXH128_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH128_hashFromCanonical)
309 /* *************************************
311 ***************************************/
312 #define XXH_VERSION_MAJOR 0
313 #define XXH_VERSION_MINOR 8
314 #define XXH_VERSION_RELEASE 1
315 #define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE)
318 * @brief Obtains the xxHash version.
320 * This is mostly useful when xxHash is compiled as a shared library,
321 * since the returned value comes from the library, as opposed to header file.
323 * @return `XXH_VERSION_NUMBER` of the invoked library.
325 XXH_PUBLIC_API unsigned XXH_versionNumber (void);
328 /* ****************************
330 ******************************/
331 #include <stddef.h> /* size_t */
332 typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode;
335 /*-**********************************************************************
337 ************************************************************************/
338 #if defined(XXH_DOXYGEN) /* Don't show <stdint.h> include */
340 * @brief An unsigned 32-bit integer.
342 * Not necessarily defined to `uint32_t` but functionally equivalent.
344 typedef uint32_t XXH32_hash_t;
346 #elif !defined (__VMS) \
347 && (defined (__cplusplus) \
348 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
350 typedef uint32_t XXH32_hash_t;
354 # if UINT_MAX == 0xFFFFFFFFUL
355 typedef unsigned int XXH32_hash_t;
357 # if ULONG_MAX == 0xFFFFFFFFUL
358 typedef unsigned long XXH32_hash_t;
360 # error "unsupported platform: need a 32-bit type"
368 * @defgroup xxh32_family XXH32 family
370 * Contains functions used in the classic 32-bit xxHash algorithm.
373 * XXH32 is useful for older platforms, with no or poor 64-bit performance.
374 * Note that @ref xxh3_family provides competitive speed
375 * for both 32-bit and 64-bit systems, and offers true 64/128 bit hash results.
377 * @see @ref xxh64_family, @ref xxh3_family : Other xxHash families
378 * @see @ref xxh32_impl for implementation details
383 * @brief Calculates the 32-bit hash of @p input using xxHash32.
385 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark): 5.4 GB/s
387 * @param input The block of data to be hashed, at least @p length bytes in size.
388 * @param length The length of @p input, in bytes.
389 * @param seed The 32-bit seed to alter the hash's output predictably.
392 * The memory between @p input and @p input + @p length must be valid,
393 * readable, contiguous memory. However, if @p length is `0`, @p input may be
394 * `NULL`. In C++, this also must be *TriviallyCopyable*.
396 * @return The calculated 32-bit hash value.
399 * XXH64(), XXH3_64bits_withSeed(), XXH3_128bits_withSeed(), XXH128():
400 * Direct equivalents for the other variants of xxHash.
402 * XXH32_createState(), XXH32_update(), XXH32_digest(): Streaming version.
404 XXH_PUBLIC_API XXH32_hash_t XXH32 (const void* input, size_t length, XXH32_hash_t seed);
407 * Streaming functions generate the xxHash value from an incremental input.
408 * This method is slower than single-call functions, due to state management.
409 * For small inputs, prefer `XXH32()` and `XXH64()`, which are better optimized.
411 * An XXH state must first be allocated using `XXH*_createState()`.
413 * Start a new hash by initializing the state with a seed using `XXH*_reset()`.
415 * Then, feed the hash state by calling `XXH*_update()` as many times as necessary.
417 * The function returns an error code, with 0 meaning OK, and any other value
418 * meaning there is an error.
420 * Finally, a hash value can be produced anytime, by using `XXH*_digest()`.
421 * This function returns the nn-bits hash as an int or long long.
423 * It's still possible to continue inserting input into the hash state after a
424 * digest, and generate new hash values later on by invoking `XXH*_digest()`.
426 * When done, release the state using `XXH*_freeState()`.
428 * Example code for incrementally hashing a file:
431 * #include <xxhash.h>
432 * #define BUFFER_SIZE 256
434 * // Note: XXH64 and XXH3 use the same interface.
436 * hashFile(FILE* stream)
438 * XXH32_state_t* state;
439 * unsigned char buf[BUFFER_SIZE];
443 * state = XXH32_createState(); // Create a state
444 * assert(state != NULL); // Error check here
445 * XXH32_reset(state, 0xbaad5eed); // Reset state with our seed
446 * while ((amt = fread(buf, 1, sizeof(buf), stream)) != 0) {
447 * XXH32_update(state, buf, amt); // Hash the file in chunks
449 * hash = XXH32_digest(state); // Finalize the hash
450 * XXH32_freeState(state); // Clean up
457 * @typedef struct XXH32_state_s XXH32_state_t
458 * @brief The opaque state struct for the XXH32 streaming API.
460 * @see XXH32_state_s for details.
462 typedef struct XXH32_state_s XXH32_state_t;
465 * @brief Allocates an @ref XXH32_state_t.
467 * Must be freed with XXH32_freeState().
468 * @return An allocated XXH32_state_t on success, `NULL` on failure.
470 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void);
472 * @brief Frees an @ref XXH32_state_t.
474 * Must be allocated with XXH32_createState().
475 * @param statePtr A pointer to an @ref XXH32_state_t allocated with @ref XXH32_createState().
478 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr);
480 * @brief Copies one @ref XXH32_state_t to another.
482 * @param dst_state The state to copy to.
483 * @param src_state The state to copy from.
485 * @p dst_state and @p src_state must not be `NULL` and must not overlap.
487 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dst_state, const XXH32_state_t* src_state);
490 * @brief Resets an @ref XXH32_state_t to begin a new hash.
492 * This function resets and seeds a state. Call it before @ref XXH32_update().
494 * @param statePtr The state struct to reset.
495 * @param seed The 32-bit seed to alter the hash result predictably.
498 * @p statePtr must not be `NULL`.
500 * @return @ref XXH_OK on success, @ref XXH_ERROR on failure.
502 XXH_PUBLIC_API XXH_errorcode XXH32_reset (XXH32_state_t* statePtr, XXH32_hash_t seed);
505 * @brief Consumes a block of @p input to an @ref XXH32_state_t.
507 * Call this to incrementally consume blocks of data.
509 * @param statePtr The state struct to update.
510 * @param input The block of data to be hashed, at least @p length bytes in size.
511 * @param length The length of @p input, in bytes.
514 * @p statePtr must not be `NULL`.
516 * The memory between @p input and @p input + @p length must be valid,
517 * readable, contiguous memory. However, if @p length is `0`, @p input may be
518 * `NULL`. In C++, this also must be *TriviallyCopyable*.
520 * @return @ref XXH_OK on success, @ref XXH_ERROR on failure.
522 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* statePtr, const void* input, size_t length);
525 * @brief Returns the calculated hash value from an @ref XXH32_state_t.
528 * Calling XXH32_digest() will not affect @p statePtr, so you can update,
529 * digest, and update again.
531 * @param statePtr The state struct to calculate the hash from.
534 * @p statePtr must not be `NULL`.
536 * @return The calculated xxHash32 value from that state.
538 XXH_PUBLIC_API XXH32_hash_t XXH32_digest (const XXH32_state_t* statePtr);
540 /******* Canonical representation *******/
543 * The default return values from XXH functions are unsigned 32 and 64 bit
545 * This the simplest and fastest format for further post-processing.
547 * However, this leaves open the question of what is the order on the byte level,
548 * since little and big endian conventions will store the same number differently.
550 * The canonical representation settles this issue by mandating big-endian
551 * convention, the same convention as human-readable numbers (large digits first).
553 * When writing hash values to storage, sending them over a network, or printing
554 * them, it's highly recommended to use the canonical representation to ensure
555 * portability across a wider range of systems, present and future.
557 * The following functions allow transformation of hash values to and from
562 * @brief Canonical (big endian) representation of @ref XXH32_hash_t.
565 unsigned char digest[4]; /*!< Hash bytes, big endian */
569 * @brief Converts an @ref XXH32_hash_t to a big endian @ref XXH32_canonical_t.
571 * @param dst The @ref XXH32_canonical_t pointer to be stored to.
572 * @param hash The @ref XXH32_hash_t to be converted.
575 * @p dst must not be `NULL`.
577 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash);
580 * @brief Converts an @ref XXH32_canonical_t to a native @ref XXH32_hash_t.
582 * @param src The @ref XXH32_canonical_t to convert.
585 * @p src must not be `NULL`.
587 * @return The converted hash.
589 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src);
592 #ifdef __has_attribute
593 # define XXH_HAS_ATTRIBUTE(x) __has_attribute(x)
595 # define XXH_HAS_ATTRIBUTE(x) 0
598 /* C-language Attributes are added in C23. */
599 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ > 201710L) && defined(__has_c_attribute)
600 # define XXH_HAS_C_ATTRIBUTE(x) __has_c_attribute(x)
602 # define XXH_HAS_C_ATTRIBUTE(x) 0
605 #if defined(__cplusplus) && defined(__has_cpp_attribute)
606 # define XXH_HAS_CPP_ATTRIBUTE(x) __has_cpp_attribute(x)
608 # define XXH_HAS_CPP_ATTRIBUTE(x) 0
612 Define XXH_FALLTHROUGH macro for annotating switch case with the 'fallthrough' attribute
613 introduced in CPP17 and C23.
614 CPP17 : https://en.cppreference.com/w/cpp/language/attributes/fallthrough
615 C23 : https://en.cppreference.com/w/c/language/attributes/fallthrough
617 #if XXH_HAS_C_ATTRIBUTE(x)
618 # define XXH_FALLTHROUGH [[fallthrough]]
619 #elif XXH_HAS_CPP_ATTRIBUTE(x)
620 # define XXH_FALLTHROUGH [[fallthrough]]
621 #elif XXH_HAS_ATTRIBUTE(__fallthrough__)
622 # define XXH_FALLTHROUGH __attribute__ ((fallthrough))
624 # define XXH_FALLTHROUGH
633 #ifndef XXH_NO_LONG_LONG
634 /*-**********************************************************************
636 ************************************************************************/
637 #if defined(XXH_DOXYGEN) /* don't include <stdint.h> */
639 * @brief An unsigned 64-bit integer.
641 * Not necessarily defined to `uint64_t` but functionally equivalent.
643 typedef uint64_t XXH64_hash_t;
644 #elif !defined (__VMS) \
645 && (defined (__cplusplus) \
646 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
648 typedef uint64_t XXH64_hash_t;
651 # if defined(__LP64__) && ULONG_MAX == 0xFFFFFFFFFFFFFFFFULL
652 /* LP64 ABI says uint64_t is unsigned long */
653 typedef unsigned long XXH64_hash_t;
655 /* the following type must have a width of 64-bit */
656 typedef unsigned long long XXH64_hash_t;
663 * @defgroup xxh64_family XXH64 family
666 * Contains functions used in the classic 64-bit xxHash algorithm.
669 * XXH3 provides competitive speed for both 32-bit and 64-bit systems,
670 * and offers true 64/128 bit hash results.
671 * It provides better speed for systems with vector processing capabilities.
676 * @brief Calculates the 64-bit hash of @p input using xxHash64.
678 * This function usually runs faster on 64-bit systems, but slower on 32-bit
679 * systems (see benchmark).
681 * @param input The block of data to be hashed, at least @p length bytes in size.
682 * @param length The length of @p input, in bytes.
683 * @param seed The 64-bit seed to alter the hash's output predictably.
686 * The memory between @p input and @p input + @p length must be valid,
687 * readable, contiguous memory. However, if @p length is `0`, @p input may be
688 * `NULL`. In C++, this also must be *TriviallyCopyable*.
690 * @return The calculated 64-bit hash.
693 * XXH32(), XXH3_64bits_withSeed(), XXH3_128bits_withSeed(), XXH128():
694 * Direct equivalents for the other variants of xxHash.
696 * XXH64_createState(), XXH64_update(), XXH64_digest(): Streaming version.
698 XXH_PUBLIC_API XXH64_hash_t XXH64(const void* input, size_t length, XXH64_hash_t seed);
700 /******* Streaming *******/
702 * @brief The opaque state struct for the XXH64 streaming API.
704 * @see XXH64_state_s for details.
706 typedef struct XXH64_state_s XXH64_state_t; /* incomplete type */
707 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void);
708 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr);
709 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dst_state, const XXH64_state_t* src_state);
711 XXH_PUBLIC_API XXH_errorcode XXH64_reset (XXH64_state_t* statePtr, XXH64_hash_t seed);
712 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* statePtr, const void* input, size_t length);
713 XXH_PUBLIC_API XXH64_hash_t XXH64_digest (const XXH64_state_t* statePtr);
715 /******* Canonical representation *******/
716 typedef struct { unsigned char digest[sizeof(XXH64_hash_t)]; } XXH64_canonical_t;
717 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash);
718 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src);
723 * ************************************************************************
724 * @defgroup xxh3_family XXH3 family
728 * XXH3 is a more recent hash algorithm featuring:
729 * - Improved speed for both small and large inputs
730 * - True 64-bit and 128-bit outputs
731 * - SIMD acceleration
732 * - Improved 32-bit viability
734 * Speed analysis methodology is explained here:
736 * https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html
738 * Compared to XXH64, expect XXH3 to run approximately
739 * ~2x faster on large inputs and >3x faster on small ones,
740 * exact differences vary depending on platform.
742 * XXH3's speed benefits greatly from SIMD and 64-bit arithmetic,
743 * but does not require it.
744 * Any 32-bit and 64-bit targets that can run XXH32 smoothly
745 * can run XXH3 at competitive speeds, even without vector support.
746 * Further details are explained in the implementation.
748 * Optimized implementations are provided for AVX512, AVX2, SSE2, NEON, POWER8,
749 * ZVector and scalar targets. This can be controlled via the XXH_VECTOR macro.
751 * XXH3 implementation is portable:
752 * it has a generic C90 formulation that can be compiled on any platform,
753 * all implementations generage exactly the same hash value on all platforms.
754 * Starting from v0.8.0, it's also labelled "stable", meaning that
755 * any future version will also generate the same hash value.
757 * XXH3 offers 2 variants, _64bits and _128bits.
759 * When only 64 bits are needed, prefer invoking the _64bits variant, as it
760 * reduces the amount of mixing, resulting in faster speed on small inputs.
761 * It's also generally simpler to manipulate a scalar return type than a struct.
763 * The API supports one-shot hashing, streaming mode, and custom secrets.
766 /*-**********************************************************************
767 * XXH3 64-bit variant
768 ************************************************************************/
771 * default 64-bit variant, using default secret and default seed of 0.
772 * It's the fastest variant. */
773 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits(const void* data, size_t len);
776 * XXH3_64bits_withSeed():
777 * This variant generates a custom secret on the fly
778 * based on default secret altered using the `seed` value.
779 * While this operation is decently fast, note that it's not completely free.
780 * Note: seed==0 produces the same results as XXH3_64bits().
782 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_withSeed(const void* data, size_t len, XXH64_hash_t seed);
785 * The bare minimum size for a custom secret.
788 * XXH3_64bits_withSecret(), XXH3_64bits_reset_withSecret(),
789 * XXH3_128bits_withSecret(), XXH3_128bits_reset_withSecret().
791 #define XXH3_SECRET_SIZE_MIN 136
794 * XXH3_64bits_withSecret():
795 * It's possible to provide any blob of bytes as a "secret" to generate the hash.
796 * This makes it more difficult for an external actor to prepare an intentional collision.
797 * The main condition is that secretSize *must* be large enough (>= XXH3_SECRET_SIZE_MIN).
798 * However, the quality of the secret impacts the dispersion of the hash algorithm.
799 * Therefore, the secret _must_ look like a bunch of random bytes.
800 * Avoid "trivial" or structured data such as repeated sequences or a text document.
801 * Whenever in doubt about the "randomness" of the blob of bytes,
802 * consider employing "XXH3_generateSecret()" instead (see below).
803 * It will generate a proper high entropy secret derived from the blob of bytes.
804 * Another advantage of using XXH3_generateSecret() is that
805 * it guarantees that all bits within the initial blob of bytes
806 * will impact every bit of the output.
807 * This is not necessarily the case when using the blob of bytes directly
808 * because, when hashing _small_ inputs, only a portion of the secret is employed.
810 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_withSecret(const void* data, size_t len, const void* secret, size_t secretSize);
813 /******* Streaming *******/
815 * Streaming requires state maintenance.
816 * This operation costs memory and CPU.
817 * As a consequence, streaming is slower than one-shot hashing.
818 * For better performance, prefer one-shot functions whenever applicable.
822 * @brief The state struct for the XXH3 streaming API.
824 * @see XXH3_state_s for details.
826 typedef struct XXH3_state_s XXH3_state_t;
827 XXH_PUBLIC_API XXH3_state_t* XXH3_createState(void);
828 XXH_PUBLIC_API XXH_errorcode XXH3_freeState(XXH3_state_t* statePtr);
829 XXH_PUBLIC_API void XXH3_copyState(XXH3_state_t* dst_state, const XXH3_state_t* src_state);
832 * XXH3_64bits_reset():
833 * Initialize with default parameters.
834 * digest will be equivalent to `XXH3_64bits()`.
836 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset(XXH3_state_t* statePtr);
838 * XXH3_64bits_reset_withSeed():
839 * Generate a custom secret from `seed`, and store it into `statePtr`.
840 * digest will be equivalent to `XXH3_64bits_withSeed()`.
842 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed);
844 * XXH3_64bits_reset_withSecret():
845 * `secret` is referenced, it _must outlive_ the hash streaming session.
846 * Similar to one-shot API, `secretSize` must be >= `XXH3_SECRET_SIZE_MIN`,
847 * and the quality of produced hash values depends on secret's entropy
848 * (secret's content should look like a bunch of random bytes).
849 * When in doubt about the randomness of a candidate `secret`,
850 * consider employing `XXH3_generateSecret()` instead (see below).
852 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize);
854 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_update (XXH3_state_t* statePtr, const void* input, size_t length);
855 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_digest (const XXH3_state_t* statePtr);
857 /* note : canonical representation of XXH3 is the same as XXH64
858 * since they both produce XXH64_hash_t values */
861 /*-**********************************************************************
862 * XXH3 128-bit variant
863 ************************************************************************/
866 * @brief The return value from 128-bit hashes.
868 * Stored in little endian order, although the fields themselves are in native
872 XXH64_hash_t low64; /*!< `value & 0xFFFFFFFFFFFFFFFF` */
873 XXH64_hash_t high64; /*!< `value >> 64` */
876 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits(const void* data, size_t len);
877 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_withSeed(const void* data, size_t len, XXH64_hash_t seed);
878 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_withSecret(const void* data, size_t len, const void* secret, size_t secretSize);
880 /******* Streaming *******/
882 * Streaming requires state maintenance.
883 * This operation costs memory and CPU.
884 * As a consequence, streaming is slower than one-shot hashing.
885 * For better performance, prefer one-shot functions whenever applicable.
887 * XXH3_128bits uses the same XXH3_state_t as XXH3_64bits().
888 * Use already declared XXH3_createState() and XXH3_freeState().
890 * All reset and streaming functions have same meaning as their 64-bit counterpart.
893 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset(XXH3_state_t* statePtr);
894 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed);
895 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize);
897 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_update (XXH3_state_t* statePtr, const void* input, size_t length);
898 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_digest (const XXH3_state_t* statePtr);
900 /* Following helper functions make it possible to compare XXH128_hast_t values.
901 * Since XXH128_hash_t is a structure, this capability is not offered by the language.
902 * Note: For better performance, these functions can be inlined using XXH_INLINE_ALL */
906 * Return: 1 if `h1` and `h2` are equal, 0 if they are not.
908 XXH_PUBLIC_API int XXH128_isEqual(XXH128_hash_t h1, XXH128_hash_t h2);
913 * This comparator is compatible with stdlib's `qsort()`/`bsearch()`.
915 * return: >0 if *h128_1 > *h128_2
916 * =0 if *h128_1 == *h128_2
917 * <0 if *h128_1 < *h128_2
919 XXH_PUBLIC_API int XXH128_cmp(const void* h128_1, const void* h128_2);
922 /******* Canonical representation *******/
923 typedef struct { unsigned char digest[sizeof(XXH128_hash_t)]; } XXH128_canonical_t;
924 XXH_PUBLIC_API void XXH128_canonicalFromHash(XXH128_canonical_t* dst, XXH128_hash_t hash);
925 XXH_PUBLIC_API XXH128_hash_t XXH128_hashFromCanonical(const XXH128_canonical_t* src);
928 #endif /* !XXH_NO_XXH3 */
929 #endif /* XXH_NO_LONG_LONG */
934 #endif /* XXHASH_H_5627135585666179 */
938 #if defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742)
939 #define XXHASH_H_STATIC_13879238742
940 /* ****************************************************************************
941 * This section contains declarations which are not guaranteed to remain stable.
942 * They may change in future versions, becoming incompatible with a different
943 * version of the library.
944 * These declarations should only be used with static linking.
945 * Never use them in association with dynamic linking!
946 ***************************************************************************** */
949 * These definitions are only present to allow static allocation
950 * of XXH states, on stack or in a struct, for example.
951 * Never **ever** access their members directly.
956 * @brief Structure for XXH32 streaming API.
958 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
959 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined. Otherwise it is
960 * an opaque type. This allows fields to safely be changed.
962 * Typedef'd to @ref XXH32_state_t.
963 * Do not access the members of this struct directly.
964 * @see XXH64_state_s, XXH3_state_s
966 struct XXH32_state_s {
967 XXH32_hash_t total_len_32; /*!< Total length hashed, modulo 2^32 */
968 XXH32_hash_t large_len; /*!< Whether the hash is >= 16 (handles @ref total_len_32 overflow) */
969 XXH32_hash_t v[4]; /*!< Accumulator lanes */
970 XXH32_hash_t mem32[4]; /*!< Internal buffer for partial reads. Treated as unsigned char[16]. */
971 XXH32_hash_t memsize; /*!< Amount of data in @ref mem32 */
972 XXH32_hash_t reserved; /*!< Reserved field. Do not read nor write to it. */
973 }; /* typedef'd to XXH32_state_t */
976 #ifndef XXH_NO_LONG_LONG /* defined when there is no 64-bit support */
980 * @brief Structure for XXH64 streaming API.
982 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
983 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined. Otherwise it is
984 * an opaque type. This allows fields to safely be changed.
986 * Typedef'd to @ref XXH64_state_t.
987 * Do not access the members of this struct directly.
988 * @see XXH32_state_s, XXH3_state_s
990 struct XXH64_state_s {
991 XXH64_hash_t total_len; /*!< Total length hashed. This is always 64-bit. */
992 XXH64_hash_t v[4]; /*!< Accumulator lanes */
993 XXH64_hash_t mem64[4]; /*!< Internal buffer for partial reads. Treated as unsigned char[32]. */
994 XXH32_hash_t memsize; /*!< Amount of data in @ref mem64 */
995 XXH32_hash_t reserved32; /*!< Reserved field, needed for padding anyways*/
996 XXH64_hash_t reserved64; /*!< Reserved field. Do not read or write to it. */
997 }; /* typedef'd to XXH64_state_t */
1002 #if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) /* >= C11 */
1003 # include <stdalign.h>
1004 # define XXH_ALIGN(n) alignas(n)
1005 #elif defined(__cplusplus) && (__cplusplus >= 201103L) /* >= C++11 */
1006 /* In C++ alignas() is a keyword */
1007 # define XXH_ALIGN(n) alignas(n)
1008 #elif defined(__GNUC__)
1009 # define XXH_ALIGN(n) __attribute__ ((aligned(n)))
1010 #elif defined(_MSC_VER)
1011 # define XXH_ALIGN(n) __declspec(align(n))
1013 # define XXH_ALIGN(n) /* disabled */
1016 /* Old GCC versions only accept the attribute after the type in structures. */
1017 #if !(defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L)) /* C11+ */ \
1018 && ! (defined(__cplusplus) && (__cplusplus >= 201103L)) /* >= C++11 */ \
1019 && defined(__GNUC__)
1020 # define XXH_ALIGN_MEMBER(align, type) type XXH_ALIGN(align)
1022 # define XXH_ALIGN_MEMBER(align, type) XXH_ALIGN(align) type
1026 * @brief The size of the internal XXH3 buffer.
1028 * This is the optimal update size for incremental hashing.
1030 * @see XXH3_64b_update(), XXH3_128b_update().
1032 #define XXH3_INTERNALBUFFER_SIZE 256
1035 * @brief Default size of the secret buffer (and @ref XXH3_kSecret).
1037 * This is the size used in @ref XXH3_kSecret and the seeded functions.
1039 * Not to be confused with @ref XXH3_SECRET_SIZE_MIN.
1041 #define XXH3_SECRET_DEFAULT_SIZE 192
1045 * @brief Structure for XXH3 streaming API.
1047 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
1048 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined.
1049 * Otherwise it is an opaque type.
1050 * Never use this definition in combination with dynamic library.
1051 * This allows fields to safely be changed in the future.
1053 * @note ** This structure has a strict alignment requirement of 64 bytes!! **
1054 * Do not allocate this with `malloc()` or `new`,
1055 * it will not be sufficiently aligned.
1056 * Use @ref XXH3_createState() and @ref XXH3_freeState(), or stack allocation.
1058 * Typedef'd to @ref XXH3_state_t.
1059 * Do never access the members of this struct directly.
1061 * @see XXH3_INITSTATE() for stack initialization.
1062 * @see XXH3_createState(), XXH3_freeState().
1063 * @see XXH32_state_s, XXH64_state_s
1065 struct XXH3_state_s {
1066 XXH_ALIGN_MEMBER(64, XXH64_hash_t acc[8]);
1067 /*!< The 8 accumulators. Similar to `vN` in @ref XXH32_state_s::v1 and @ref XXH64_state_s */
1068 XXH_ALIGN_MEMBER(64, unsigned char customSecret[XXH3_SECRET_DEFAULT_SIZE]);
1069 /*!< Used to store a custom secret generated from a seed. */
1070 XXH_ALIGN_MEMBER(64, unsigned char buffer[XXH3_INTERNALBUFFER_SIZE]);
1071 /*!< The internal buffer. @see XXH32_state_s::mem32 */
1072 XXH32_hash_t bufferedSize;
1073 /*!< The amount of memory in @ref buffer, @see XXH32_state_s::memsize */
1074 XXH32_hash_t useSeed;
1075 /*!< Reserved field. Needed for padding on 64-bit. */
1076 size_t nbStripesSoFar;
1077 /*!< Number or stripes processed. */
1078 XXH64_hash_t totalLen;
1079 /*!< Total length hashed. 64-bit even on 32-bit targets. */
1080 size_t nbStripesPerBlock;
1081 /*!< Number of stripes per block. */
1083 /*!< Size of @ref customSecret or @ref extSecret */
1085 /*!< Seed for _withSeed variants. Must be zero otherwise, @see XXH3_INITSTATE() */
1086 XXH64_hash_t reserved64;
1087 /*!< Reserved field. */
1088 const unsigned char* extSecret;
1089 /*!< Reference to an external secret for the _withSecret variants, NULL
1090 * for other variants. */
1091 /* note: there may be some padding at the end due to alignment on 64 bytes */
1092 }; /* typedef'd to XXH3_state_t */
1094 #undef XXH_ALIGN_MEMBER
1097 * @brief Initializes a stack-allocated `XXH3_state_s`.
1099 * When the @ref XXH3_state_t structure is merely emplaced on stack,
1100 * it should be initialized with XXH3_INITSTATE() or a memset()
1101 * in case its first reset uses XXH3_NNbits_reset_withSeed().
1102 * This init can be omitted if the first reset uses default or _withSecret mode.
1103 * This operation isn't necessary when the state is created with XXH3_createState().
1104 * Note that this doesn't prepare the state for a streaming operation,
1105 * it's still necessary to use XXH3_NNbits_reset*() afterwards.
1107 #define XXH3_INITSTATE(XXH3_state_ptr) { (XXH3_state_ptr)->seed = 0; }
1111 * simple alias to pre-selected XXH3_128bits variant
1113 XXH_PUBLIC_API XXH128_hash_t XXH128(const void* data, size_t len, XXH64_hash_t seed);
1116 /* === Experimental API === */
1117 /* Symbols defined below must be considered tied to a specific library version. */
1120 * XXH3_generateSecret():
1122 * Derive a high-entropy secret from any user-defined content, named customSeed.
1123 * The generated secret can be used in combination with `*_withSecret()` functions.
1124 * The `_withSecret()` variants are useful to provide a higher level of protection than 64-bit seed,
1125 * as it becomes much more difficult for an external actor to guess how to impact the calculation logic.
1127 * The function accepts as input a custom seed of any length and any content,
1128 * and derives from it a high-entropy secret of length @secretSize
1129 * into an already allocated buffer @secretBuffer.
1130 * @secretSize must be >= XXH3_SECRET_SIZE_MIN
1132 * The generated secret can then be used with any `*_withSecret()` variant.
1133 * Functions `XXH3_128bits_withSecret()`, `XXH3_64bits_withSecret()`,
1134 * `XXH3_128bits_reset_withSecret()` and `XXH3_64bits_reset_withSecret()`
1135 * are part of this list. They all accept a `secret` parameter
1136 * which must be large enough for implementation reasons (>= XXH3_SECRET_SIZE_MIN)
1137 * _and_ feature very high entropy (consist of random-looking bytes).
1138 * These conditions can be a high bar to meet, so
1139 * XXH3_generateSecret() can be employed to ensure proper quality.
1141 * customSeed can be anything. It can have any size, even small ones,
1142 * and its content can be anything, even "poor entropy" sources such as a bunch of zeroes.
1143 * The resulting `secret` will nonetheless provide all required qualities.
1145 * When customSeedSize > 0, supplying NULL as customSeed is undefined behavior.
1147 XXH_PUBLIC_API XXH_errorcode XXH3_generateSecret(void* secretBuffer, size_t secretSize, const void* customSeed, size_t customSeedSize);
1151 * XXH3_generateSecret_fromSeed():
1153 * Generate the same secret as the _withSeed() variants.
1155 * The resulting secret has a length of XXH3_SECRET_DEFAULT_SIZE (necessarily).
1156 * @secretBuffer must be already allocated, of size at least XXH3_SECRET_DEFAULT_SIZE bytes.
1158 * The generated secret can be used in combination with
1159 *`*_withSecret()` and `_withSecretandSeed()` variants.
1160 * This generator is notably useful in combination with `_withSecretandSeed()`,
1161 * as a way to emulate a faster `_withSeed()` variant.
1163 XXH_PUBLIC_API void XXH3_generateSecret_fromSeed(void* secretBuffer, XXH64_hash_t seed);
1166 * *_withSecretandSeed() :
1167 * These variants generate hash values using either
1168 * @seed for "short" keys (< XXH3_MIDSIZE_MAX = 240 bytes)
1169 * or @secret for "large" keys (>= XXH3_MIDSIZE_MAX).
1171 * This generally benefits speed, compared to `_withSeed()` or `_withSecret()`.
1172 * `_withSeed()` has to generate the secret on the fly for "large" keys.
1173 * It's fast, but can be perceptible for "not so large" keys (< 1 KB).
1174 * `_withSecret()` has to generate the masks on the fly for "small" keys,
1175 * which requires more instructions than _withSeed() variants.
1176 * Therefore, _withSecretandSeed variant combines the best of both worlds.
1178 * When @secret has been generated by XXH3_generateSecret_fromSeed(),
1179 * this variant produces *exactly* the same results as `_withSeed()` variant,
1180 * hence offering only a pure speed benefit on "large" input,
1181 * by skipping the need to regenerate the secret for every large input.
1183 * Another usage scenario is to hash the secret to a 64-bit hash value,
1184 * for example with XXH3_64bits(), which then becomes the seed,
1185 * and then employ both the seed and the secret in _withSecretandSeed().
1186 * On top of speed, an added benefit is that each bit in the secret
1187 * has a 50% chance to swap each bit in the output,
1188 * via its impact to the seed.
1189 * This is not guaranteed when using the secret directly in "small data" scenarios,
1190 * because only portions of the secret are employed for small data.
1192 XXH_PUBLIC_API XXH64_hash_t
1193 XXH3_64bits_withSecretandSeed(const void* data, size_t len,
1194 const void* secret, size_t secretSize,
1197 XXH_PUBLIC_API XXH128_hash_t
1198 XXH3_128bits_withSecretandSeed(const void* data, size_t len,
1199 const void* secret, size_t secretSize,
1200 XXH64_hash_t seed64);
1202 XXH_PUBLIC_API XXH_errorcode
1203 XXH3_64bits_reset_withSecretandSeed(XXH3_state_t* statePtr,
1204 const void* secret, size_t secretSize,
1205 XXH64_hash_t seed64);
1207 XXH_PUBLIC_API XXH_errorcode
1208 XXH3_128bits_reset_withSecretandSeed(XXH3_state_t* statePtr,
1209 const void* secret, size_t secretSize,
1210 XXH64_hash_t seed64);
1213 #endif /* XXH_NO_XXH3 */
1214 #endif /* XXH_NO_LONG_LONG */
1215 #if defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)
1216 # define XXH_IMPLEMENTATION
1219 #endif /* defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742) */
1222 /* ======================================================================== */
1223 /* ======================================================================== */
1224 /* ======================================================================== */
1227 /*-**********************************************************************
1228 * xxHash implementation
1229 *-**********************************************************************
1230 * xxHash's implementation used to be hosted inside xxhash.c.
1232 * However, inlining requires implementation to be visible to the compiler,
1233 * hence be included alongside the header.
1234 * Previously, implementation was hosted inside xxhash.c,
1235 * which was then #included when inlining was activated.
1236 * This construction created issues with a few build and install systems,
1237 * as it required xxhash.c to be stored in /include directory.
1239 * xxHash implementation is now directly integrated within xxhash.h.
1240 * As a consequence, xxhash.c is no longer needed in /include.
1242 * xxhash.c is still available and is still useful.
1243 * In a "normal" setup, when xxhash is not inlined,
1244 * xxhash.h only exposes the prototypes and public symbols,
1245 * while xxhash.c can be built into an object file xxhash.o
1246 * which can then be linked into the final binary.
1247 ************************************************************************/
1249 #if ( defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API) \
1250 || defined(XXH_IMPLEMENTATION) ) && !defined(XXH_IMPLEM_13a8737387)
1251 # define XXH_IMPLEM_13a8737387
1253 /* *************************************
1255 ***************************************/
1258 * @defgroup tuning Tuning parameters
1261 * Various macros to control xxHash's behavior.
1265 * @brief Define this to disable 64-bit code.
1267 * Useful if only using the @ref xxh32_family and you have a strict C90 compiler.
1269 # define XXH_NO_LONG_LONG
1270 # undef XXH_NO_LONG_LONG /* don't actually */
1272 * @brief Controls how unaligned memory is accessed.
1274 * By default, access to unaligned memory is controlled by `memcpy()`, which is
1275 * safe and portable.
1277 * Unfortunately, on some target/compiler combinations, the generated assembly
1280 * The below switch allow selection of a different access method
1281 * in the search for improved performance.
1283 * @par Possible options:
1285 * - `XXH_FORCE_MEMORY_ACCESS=0` (default): `memcpy`
1287 * Use `memcpy()`. Safe and portable. Note that most modern compilers will
1288 * eliminate the function call and treat it as an unaligned access.
1290 * - `XXH_FORCE_MEMORY_ACCESS=1`: `__attribute__((packed))`
1292 * Depends on compiler extensions and is therefore not portable.
1293 * This method is safe _if_ your compiler supports it,
1294 * and *generally* as fast or faster than `memcpy`.
1296 * - `XXH_FORCE_MEMORY_ACCESS=2`: Direct cast
1298 * Casts directly and dereferences. This method doesn't depend on the
1299 * compiler, but it violates the C standard as it directly dereferences an
1300 * unaligned pointer. It can generate buggy code on targets which do not
1301 * support unaligned memory accesses, but in some circumstances, it's the
1302 * only known way to get the most performance.
1304 * - `XXH_FORCE_MEMORY_ACCESS=3`: Byteshift
1306 * Also portable. This can generate the best code on old compilers which don't
1307 * inline small `memcpy()` calls, and it might also be faster on big-endian
1308 * systems which lack a native byteswap instruction. However, some compilers
1309 * will emit literal byteshifts even if the target supports unaligned access.
1313 * Methods 1 and 2 rely on implementation-defined behavior. Use these with
1314 * care, as what works on one compiler/platform/optimization level may cause
1315 * another to read garbage data or even crash.
1317 * See https://fastcompression.blogspot.com/2015/08/accessing-unaligned-memory.html for details.
1319 * Prefer these methods in priority order (0 > 3 > 1 > 2)
1321 # define XXH_FORCE_MEMORY_ACCESS 0
1324 * @def XXH_FORCE_ALIGN_CHECK
1325 * @brief If defined to non-zero, adds a special path for aligned inputs (XXH32()
1326 * and XXH64() only).
1328 * This is an important performance trick for architectures without decent
1329 * unaligned memory access performance.
1331 * It checks for input alignment, and when conditions are met, uses a "fast
1332 * path" employing direct 32-bit/64-bit reads, resulting in _dramatically
1333 * faster_ read speed.
1335 * The check costs one initial branch per hash, which is generally negligible,
1338 * Moreover, it's not useful to generate an additional code path if memory
1339 * access uses the same instruction for both aligned and unaligned
1340 * addresses (e.g. x86 and aarch64).
1342 * In these cases, the alignment check can be removed by setting this macro to 0.
1343 * Then the code will always use unaligned memory access.
1344 * Align check is automatically disabled on x86, x64 & arm64,
1345 * which are platforms known to offer good unaligned memory accesses performance.
1347 * This option does not affect XXH3 (only XXH32 and XXH64).
1349 # define XXH_FORCE_ALIGN_CHECK 0
1352 * @def XXH_NO_INLINE_HINTS
1353 * @brief When non-zero, sets all functions to `static`.
1355 * By default, xxHash tries to force the compiler to inline almost all internal
1358 * This can usually improve performance due to reduced jumping and improved
1359 * constant folding, but significantly increases the size of the binary which
1360 * might not be favorable.
1362 * Additionally, sometimes the forced inlining can be detrimental to performance,
1363 * depending on the architecture.
1365 * XXH_NO_INLINE_HINTS marks all internal functions as static, giving the
1366 * compiler full control on whether to inline or not.
1368 * When not optimizing (-O0), optimizing for size (-Os, -Oz), or using
1369 * -fno-inline with GCC or Clang, this will automatically be defined.
1371 # define XXH_NO_INLINE_HINTS 0
1375 * @brief Whether to use a jump for `XXH32_finalize`.
1377 * For performance, `XXH32_finalize` uses multiple branches in the finalizer.
1378 * This is generally preferable for performance,
1379 * but depending on exact architecture, a jmp may be preferable.
1381 * This setting is only possibly making a difference for very small inputs.
1383 # define XXH32_ENDJMP 0
1387 * @brief Redefines old internal names.
1389 * For compatibility with code that uses xxHash's internals before the names
1390 * were changed to improve namespacing. There is no other reason to use this.
1392 # define XXH_OLD_NAMES
1393 # undef XXH_OLD_NAMES /* don't actually use, it is ugly. */
1394 #endif /* XXH_DOXYGEN */
1399 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
1400 /* prefer __packed__ structures (method 1) for gcc on armv7+ and mips */
1401 # if !defined(__clang__) && \
1403 (defined(__INTEL_COMPILER) && !defined(_WIN32)) || \
1405 defined(__GNUC__) && ( \
1406 (defined(__ARM_ARCH) && __ARM_ARCH >= 7) || \
1408 defined(__mips__) && \
1409 (__mips <= 5 || __mips_isa_rev < 6) && \
1410 (!defined(__mips16) || defined(__mips_mips16e2)) \
1415 # define XXH_FORCE_MEMORY_ACCESS 1
1419 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
1420 # if defined(__i386) || defined(__x86_64__) || defined(__aarch64__) \
1421 || defined(_M_IX86) || defined(_M_X64) || defined(_M_ARM64) /* visual */
1422 # define XXH_FORCE_ALIGN_CHECK 0
1424 # define XXH_FORCE_ALIGN_CHECK 1
1428 #ifndef XXH_NO_INLINE_HINTS
1429 # if defined(__OPTIMIZE_SIZE__) /* -Os, -Oz */ \
1430 || defined(__NO_INLINE__) /* -O0, -fno-inline */
1431 # define XXH_NO_INLINE_HINTS 1
1433 # define XXH_NO_INLINE_HINTS 0
1437 #ifndef XXH32_ENDJMP
1438 /* generally preferable for performance */
1439 # define XXH32_ENDJMP 0
1443 * @defgroup impl Implementation
1448 /* *************************************
1449 * Includes & Memory related functions
1450 ***************************************/
1451 /* Modify the local functions below should you wish to use some other memory routines */
1452 /* for ZSTD_malloc(), ZSTD_free() */
1453 #define ZSTD_DEPS_NEED_MALLOC
1454 #include "zstd_deps.h" /* size_t, ZSTD_malloc, ZSTD_free, ZSTD_memcpy */
1455 static void* XXH_malloc(size_t s) { return ZSTD_malloc(s); }
1456 static void XXH_free (void* p) { ZSTD_free(p); }
1457 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return ZSTD_memcpy(dest,src,size); }
1460 /* *************************************
1461 * Compiler Specific Options
1462 ***************************************/
1463 #ifdef _MSC_VER /* Visual Studio warning fix */
1464 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1467 #if XXH_NO_INLINE_HINTS /* disable inlining hints */
1468 # if defined(__GNUC__) || defined(__clang__)
1469 # define XXH_FORCE_INLINE static __attribute__((unused))
1471 # define XXH_FORCE_INLINE static
1473 # define XXH_NO_INLINE static
1474 /* enable inlining hints */
1475 #elif defined(__GNUC__) || defined(__clang__)
1476 # define XXH_FORCE_INLINE static __inline__ __attribute__((always_inline, unused))
1477 # define XXH_NO_INLINE static __attribute__((noinline))
1478 #elif defined(_MSC_VER) /* Visual Studio */
1479 # define XXH_FORCE_INLINE static __forceinline
1480 # define XXH_NO_INLINE static __declspec(noinline)
1481 #elif defined (__cplusplus) \
1482 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) /* C99 */
1483 # define XXH_FORCE_INLINE static inline
1484 # define XXH_NO_INLINE static
1486 # define XXH_FORCE_INLINE static
1487 # define XXH_NO_INLINE static
1492 /* *************************************
1494 ***************************************/
1497 * @def XXH_DEBUGLEVEL
1498 * @brief Sets the debugging level.
1500 * XXH_DEBUGLEVEL is expected to be defined externally, typically via the
1501 * compiler's command line options. The value must be a number.
1503 #ifndef XXH_DEBUGLEVEL
1504 # ifdef DEBUGLEVEL /* backwards compat */
1505 # define XXH_DEBUGLEVEL DEBUGLEVEL
1507 # define XXH_DEBUGLEVEL 0
1511 #if (XXH_DEBUGLEVEL>=1)
1512 # include <assert.h> /* note: can still be disabled with NDEBUG */
1513 # define XXH_ASSERT(c) assert(c)
1515 # define XXH_ASSERT(c) ((void)0)
1518 /* note: use after variable declarations */
1519 #ifndef XXH_STATIC_ASSERT
1520 # if defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) /* C11 */
1521 # include <assert.h>
1522 # define XXH_STATIC_ASSERT_WITH_MESSAGE(c,m) do { static_assert((c),m); } while(0)
1523 # elif defined(__cplusplus) && (__cplusplus >= 201103L) /* C++11 */
1524 # define XXH_STATIC_ASSERT_WITH_MESSAGE(c,m) do { static_assert((c),m); } while(0)
1526 # define XXH_STATIC_ASSERT_WITH_MESSAGE(c,m) do { struct xxh_sa { char x[(c) ? 1 : -1]; }; } while(0)
1528 # define XXH_STATIC_ASSERT(c) XXH_STATIC_ASSERT_WITH_MESSAGE((c),#c)
1533 * @def XXH_COMPILER_GUARD(var)
1534 * @brief Used to prevent unwanted optimizations for @p var.
1536 * It uses an empty GCC inline assembly statement with a register constraint
1537 * which forces @p var into a general purpose register (e.g. eax, ebx, ecx
1538 * on x86) and marks it as modified.
1540 * This is used in a few places to avoid unwanted autovectorization (e.g.
1541 * XXH32_round()). All vectorization we want is explicit via intrinsics,
1542 * and _usually_ isn't wanted elsewhere.
1544 * We also use it to prevent unwanted constant folding for AArch64 in
1545 * XXH3_initCustomSecret_scalar().
1547 #if defined(__GNUC__) || defined(__clang__)
1548 # define XXH_COMPILER_GUARD(var) __asm__ __volatile__("" : "+r" (var))
1550 # define XXH_COMPILER_GUARD(var) ((void)0)
1553 /* *************************************
1555 ***************************************/
1556 #if !defined (__VMS) \
1557 && (defined (__cplusplus) \
1558 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
1559 # include <stdint.h>
1560 typedef uint8_t xxh_u8;
1562 typedef unsigned char xxh_u8;
1564 typedef XXH32_hash_t xxh_u32;
1566 #ifdef XXH_OLD_NAMES
1567 # define BYTE xxh_u8
1569 # define U32 xxh_u32
1572 /* *** Memory access *** */
1576 * @fn xxh_u32 XXH_read32(const void* ptr)
1577 * @brief Reads an unaligned 32-bit integer from @p ptr in native endianness.
1579 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1581 * @param ptr The pointer to read from.
1582 * @return The 32-bit native endian integer from the bytes at @p ptr.
1587 * @fn xxh_u32 XXH_readLE32(const void* ptr)
1588 * @brief Reads an unaligned 32-bit little endian integer from @p ptr.
1590 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1592 * @param ptr The pointer to read from.
1593 * @return The 32-bit little endian integer from the bytes at @p ptr.
1598 * @fn xxh_u32 XXH_readBE32(const void* ptr)
1599 * @brief Reads an unaligned 32-bit big endian integer from @p ptr.
1601 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1603 * @param ptr The pointer to read from.
1604 * @return The 32-bit big endian integer from the bytes at @p ptr.
1609 * @fn xxh_u32 XXH_readLE32_align(const void* ptr, XXH_alignment align)
1610 * @brief Like @ref XXH_readLE32(), but has an option for aligned reads.
1612 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1613 * Note that when @ref XXH_FORCE_ALIGN_CHECK == 0, the @p align parameter is
1614 * always @ref XXH_alignment::XXH_unaligned.
1616 * @param ptr The pointer to read from.
1617 * @param align Whether @p ptr is aligned.
1619 * If @p align == @ref XXH_alignment::XXH_aligned, @p ptr must be 4 byte
1621 * @return The 32-bit little endian integer from the bytes at @p ptr.
1624 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
1626 * Manual byteshift. Best for old compilers which don't inline memcpy.
1627 * We actually directly use XXH_readLE32 and XXH_readBE32.
1629 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
1632 * Force direct memory access. Only works on CPU which support unaligned memory
1633 * access in hardware.
1635 static xxh_u32 XXH_read32(const void* memPtr) { return *(const xxh_u32*) memPtr; }
1637 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
1640 * __pack instructions are safer but compiler specific, hence potentially
1641 * problematic for some compilers.
1643 * Currently only defined for GCC and ICC.
1645 #ifdef XXH_OLD_NAMES
1646 typedef union { xxh_u32 u32; } __attribute__((packed)) unalign;
1648 static xxh_u32 XXH_read32(const void* ptr)
1650 typedef union { xxh_u32 u32; } __attribute__((packed)) xxh_unalign;
1651 return ((const xxh_unalign*)ptr)->u32;
1657 * Portable and safe solution. Generally efficient.
1658 * see: https://fastcompression.blogspot.com/2015/08/accessing-unaligned-memory.html
1660 static xxh_u32 XXH_read32(const void* memPtr)
1663 XXH_memcpy(&val, memPtr, sizeof(val));
1667 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
1670 /* *** Endianness *** */
1674 * @def XXH_CPU_LITTLE_ENDIAN
1675 * @brief Whether the target is little endian.
1677 * Defined to 1 if the target is little endian, or 0 if it is big endian.
1678 * It can be defined externally, for example on the compiler command line.
1680 * If it is not defined,
1681 * a runtime check (which is usually constant folded) is used instead.
1684 * This is not necessarily defined to an integer constant.
1686 * @see XXH_isLittleEndian() for the runtime check.
1688 #ifndef XXH_CPU_LITTLE_ENDIAN
1690 * Try to detect endianness automatically, to avoid the nonstandard behavior
1691 * in `XXH_isLittleEndian()`
1693 # if defined(_WIN32) /* Windows is always little endian */ \
1694 || defined(__LITTLE_ENDIAN__) \
1695 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1696 # define XXH_CPU_LITTLE_ENDIAN 1
1697 # elif defined(__BIG_ENDIAN__) \
1698 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
1699 # define XXH_CPU_LITTLE_ENDIAN 0
1703 * @brief Runtime check for @ref XXH_CPU_LITTLE_ENDIAN.
1705 * Most compilers will constant fold this.
1707 static int XXH_isLittleEndian(void)
1710 * Portable and well-defined behavior.
1711 * Don't use static: it is detrimental to performance.
1713 const union { xxh_u32 u; xxh_u8 c[4]; } one = { 1 };
1716 # define XXH_CPU_LITTLE_ENDIAN XXH_isLittleEndian()
1723 /* ****************************************
1724 * Compiler-specific Functions and Macros
1725 ******************************************/
1726 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
1728 #ifdef __has_builtin
1729 # define XXH_HAS_BUILTIN(x) __has_builtin(x)
1731 # define XXH_HAS_BUILTIN(x) 0
1736 * @def XXH_rotl32(x,r)
1737 * @brief 32-bit rotate left.
1739 * @param x The 32-bit integer to be rotated.
1740 * @param r The number of bits to rotate.
1742 * @p r > 0 && @p r < 32
1744 * @p x and @p r may be evaluated multiple times.
1745 * @return The rotated result.
1747 #if !defined(NO_CLANG_BUILTIN) && XXH_HAS_BUILTIN(__builtin_rotateleft32) \
1748 && XXH_HAS_BUILTIN(__builtin_rotateleft64)
1749 # define XXH_rotl32 __builtin_rotateleft32
1750 # define XXH_rotl64 __builtin_rotateleft64
1751 /* Note: although _rotl exists for minGW (GCC under windows), performance seems poor */
1752 #elif defined(_MSC_VER)
1753 # define XXH_rotl32(x,r) _rotl(x,r)
1754 # define XXH_rotl64(x,r) _rotl64(x,r)
1756 # define XXH_rotl32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
1757 # define XXH_rotl64(x,r) (((x) << (r)) | ((x) >> (64 - (r))))
1762 * @fn xxh_u32 XXH_swap32(xxh_u32 x)
1763 * @brief A 32-bit byteswap.
1765 * @param x The 32-bit integer to byteswap.
1766 * @return @p x, byteswapped.
1768 #if defined(_MSC_VER) /* Visual Studio */
1769 # define XXH_swap32 _byteswap_ulong
1770 #elif XXH_GCC_VERSION >= 403
1771 # define XXH_swap32 __builtin_bswap32
1773 static xxh_u32 XXH_swap32 (xxh_u32 x)
1775 return ((x << 24) & 0xff000000 ) |
1776 ((x << 8) & 0x00ff0000 ) |
1777 ((x >> 8) & 0x0000ff00 ) |
1778 ((x >> 24) & 0x000000ff );
1783 /* ***************************
1785 *****************************/
1789 * @brief Enum to indicate whether a pointer is aligned.
1792 XXH_aligned, /*!< Aligned */
1793 XXH_unaligned /*!< Possibly unaligned */
1797 * XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load.
1799 * This is ideal for older compilers which don't inline memcpy.
1801 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
1803 XXH_FORCE_INLINE xxh_u32 XXH_readLE32(const void* memPtr)
1805 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr;
1807 | ((xxh_u32)bytePtr[1] << 8)
1808 | ((xxh_u32)bytePtr[2] << 16)
1809 | ((xxh_u32)bytePtr[3] << 24);
1812 XXH_FORCE_INLINE xxh_u32 XXH_readBE32(const void* memPtr)
1814 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr;
1816 | ((xxh_u32)bytePtr[2] << 8)
1817 | ((xxh_u32)bytePtr[1] << 16)
1818 | ((xxh_u32)bytePtr[0] << 24);
1822 XXH_FORCE_INLINE xxh_u32 XXH_readLE32(const void* ptr)
1824 return XXH_CPU_LITTLE_ENDIAN ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr));
1827 static xxh_u32 XXH_readBE32(const void* ptr)
1829 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr);
1833 XXH_FORCE_INLINE xxh_u32
1834 XXH_readLE32_align(const void* ptr, XXH_alignment align)
1836 if (align==XXH_unaligned) {
1837 return XXH_readLE32(ptr);
1839 return XXH_CPU_LITTLE_ENDIAN ? *(const xxh_u32*)ptr : XXH_swap32(*(const xxh_u32*)ptr);
1844 /* *************************************
1846 ***************************************/
1847 /*! @ingroup public */
1848 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; }
1851 /* *******************************************************************
1852 * 32-bit hash functions
1853 *********************************************************************/
1856 * @defgroup xxh32_impl XXH32 implementation
1860 /* #define instead of static const, to be used as initializers */
1861 #define XXH_PRIME32_1 0x9E3779B1U /*!< 0b10011110001101110111100110110001 */
1862 #define XXH_PRIME32_2 0x85EBCA77U /*!< 0b10000101111010111100101001110111 */
1863 #define XXH_PRIME32_3 0xC2B2AE3DU /*!< 0b11000010101100101010111000111101 */
1864 #define XXH_PRIME32_4 0x27D4EB2FU /*!< 0b00100111110101001110101100101111 */
1865 #define XXH_PRIME32_5 0x165667B1U /*!< 0b00010110010101100110011110110001 */
1867 #ifdef XXH_OLD_NAMES
1868 # define PRIME32_1 XXH_PRIME32_1
1869 # define PRIME32_2 XXH_PRIME32_2
1870 # define PRIME32_3 XXH_PRIME32_3
1871 # define PRIME32_4 XXH_PRIME32_4
1872 # define PRIME32_5 XXH_PRIME32_5
1877 * @brief Normal stripe processing routine.
1879 * This shuffles the bits so that any bit from @p input impacts several bits in
1882 * @param acc The accumulator lane.
1883 * @param input The stripe of input to mix.
1884 * @return The mixed accumulator lane.
1886 static xxh_u32 XXH32_round(xxh_u32 acc, xxh_u32 input)
1888 acc += input * XXH_PRIME32_2;
1889 acc = XXH_rotl32(acc, 13);
1890 acc *= XXH_PRIME32_1;
1891 #if (defined(__SSE4_1__) || defined(__aarch64__)) && !defined(XXH_ENABLE_AUTOVECTORIZE)
1894 * A compiler fence is the only thing that prevents GCC and Clang from
1895 * autovectorizing the XXH32 loop (pragmas and attributes don't work for some
1896 * reason) without globally disabling SSE4.1.
1898 * The reason we want to avoid vectorization is because despite working on
1899 * 4 integers at a time, there are multiple factors slowing XXH32 down on
1901 * - There's a ridiculous amount of lag from pmulld (10 cycles of latency on
1902 * newer chips!) making it slightly slower to multiply four integers at
1903 * once compared to four integers independently. Even when pmulld was
1904 * fastest, Sandy/Ivy Bridge, it is still not worth it to go into SSE
1905 * just to multiply unless doing a long operation.
1907 * - Four instructions are required to rotate,
1908 * movqda tmp, v // not required with VEX encoding
1909 * pslld tmp, 13 // tmp <<= 13
1910 * psrld v, 19 // x >>= 19
1911 * por v, tmp // x |= tmp
1912 * compared to one for scalar:
1913 * roll v, 13 // reliably fast across the board
1914 * shldl v, v, 13 // Sandy Bridge and later prefer this for some reason
1916 * - Instruction level parallelism is actually more beneficial here because
1917 * the SIMD actually serializes this operation: While v1 is rotating, v2
1918 * can load data, while v3 can multiply. SSE forces them to operate
1921 * This is also enabled on AArch64, as Clang autovectorizes it incorrectly
1922 * and it is pointless writing a NEON implementation that is basically the
1923 * same speed as scalar for XXH32.
1925 XXH_COMPILER_GUARD(acc);
1932 * @brief Mixes all bits to finalize the hash.
1934 * The final mix ensures that all input bits have a chance to impact any bit in
1935 * the output digest, resulting in an unbiased distribution.
1937 * @param h32 The hash to avalanche.
1938 * @return The avalanched hash.
1940 static xxh_u32 XXH32_avalanche(xxh_u32 h32)
1943 h32 *= XXH_PRIME32_2;
1945 h32 *= XXH_PRIME32_3;
1950 #define XXH_get32bits(p) XXH_readLE32_align(p, align)
1954 * @brief Processes the last 0-15 bytes of @p ptr.
1956 * There may be up to 15 bytes remaining to consume from the input.
1957 * This final stage will digest them to ensure that all input bytes are present
1960 * @param h32 The hash to finalize.
1961 * @param ptr The pointer to the remaining input.
1962 * @param len The remaining length, modulo 16.
1963 * @param align Whether @p ptr is aligned.
1964 * @return The finalized hash.
1967 XXH32_finalize(xxh_u32 h32, const xxh_u8* ptr, size_t len, XXH_alignment align)
1969 #define XXH_PROCESS1 do { \
1970 h32 += (*ptr++) * XXH_PRIME32_5; \
1971 h32 = XXH_rotl32(h32, 11) * XXH_PRIME32_1; \
1974 #define XXH_PROCESS4 do { \
1975 h32 += XXH_get32bits(ptr) * XXH_PRIME32_3; \
1977 h32 = XXH_rotl32(h32, 17) * XXH_PRIME32_4; \
1980 if (ptr==NULL) XXH_ASSERT(len == 0);
1982 /* Compact rerolled version; generally faster */
1983 if (!XXH32_ENDJMP) {
1993 return XXH32_avalanche(h32);
1995 switch(len&15) /* or switch(bEnd - p) */ {
1996 case 12: XXH_PROCESS4;
1998 case 8: XXH_PROCESS4;
2000 case 4: XXH_PROCESS4;
2001 return XXH32_avalanche(h32);
2003 case 13: XXH_PROCESS4;
2005 case 9: XXH_PROCESS4;
2007 case 5: XXH_PROCESS4;
2009 return XXH32_avalanche(h32);
2011 case 14: XXH_PROCESS4;
2013 case 10: XXH_PROCESS4;
2015 case 6: XXH_PROCESS4;
2018 return XXH32_avalanche(h32);
2020 case 15: XXH_PROCESS4;
2022 case 11: XXH_PROCESS4;
2024 case 7: XXH_PROCESS4;
2026 case 3: XXH_PROCESS1;
2028 case 2: XXH_PROCESS1;
2030 case 1: XXH_PROCESS1;
2032 case 0: return XXH32_avalanche(h32);
2035 return h32; /* reaching this point is deemed impossible */
2039 #ifdef XXH_OLD_NAMES
2040 # define PROCESS1 XXH_PROCESS1
2041 # define PROCESS4 XXH_PROCESS4
2043 # undef XXH_PROCESS1
2044 # undef XXH_PROCESS4
2049 * @brief The implementation for @ref XXH32().
2051 * @param input , len , seed Directly passed from @ref XXH32().
2052 * @param align Whether @p input is aligned.
2053 * @return The calculated hash.
2055 XXH_FORCE_INLINE xxh_u32
2056 XXH32_endian_align(const xxh_u8* input, size_t len, xxh_u32 seed, XXH_alignment align)
2060 if (input==NULL) XXH_ASSERT(len == 0);
2063 const xxh_u8* const bEnd = input + len;
2064 const xxh_u8* const limit = bEnd - 15;
2065 xxh_u32 v1 = seed + XXH_PRIME32_1 + XXH_PRIME32_2;
2066 xxh_u32 v2 = seed + XXH_PRIME32_2;
2067 xxh_u32 v3 = seed + 0;
2068 xxh_u32 v4 = seed - XXH_PRIME32_1;
2071 v1 = XXH32_round(v1, XXH_get32bits(input)); input += 4;
2072 v2 = XXH32_round(v2, XXH_get32bits(input)); input += 4;
2073 v3 = XXH32_round(v3, XXH_get32bits(input)); input += 4;
2074 v4 = XXH32_round(v4, XXH_get32bits(input)); input += 4;
2075 } while (input < limit);
2077 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7)
2078 + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
2080 h32 = seed + XXH_PRIME32_5;
2083 h32 += (xxh_u32)len;
2085 return XXH32_finalize(h32, input, len&15, align);
2088 /*! @ingroup xxh32_family */
2089 XXH_PUBLIC_API XXH32_hash_t XXH32 (const void* input, size_t len, XXH32_hash_t seed)
2092 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
2093 XXH32_state_t state;
2094 XXH32_reset(&state, seed);
2095 XXH32_update(&state, (const xxh_u8*)input, len);
2096 return XXH32_digest(&state);
2098 if (XXH_FORCE_ALIGN_CHECK) {
2099 if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
2100 return XXH32_endian_align((const xxh_u8*)input, len, seed, XXH_aligned);
2103 return XXH32_endian_align((const xxh_u8*)input, len, seed, XXH_unaligned);
2109 /******* Hash streaming *******/
2111 * @ingroup xxh32_family
2113 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void)
2115 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
2117 /*! @ingroup xxh32_family */
2118 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
2124 /*! @ingroup xxh32_family */
2125 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState)
2127 XXH_memcpy(dstState, srcState, sizeof(*dstState));
2130 /*! @ingroup xxh32_family */
2131 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, XXH32_hash_t seed)
2133 XXH_ASSERT(statePtr != NULL);
2134 memset(statePtr, 0, sizeof(*statePtr));
2135 statePtr->v[0] = seed + XXH_PRIME32_1 + XXH_PRIME32_2;
2136 statePtr->v[1] = seed + XXH_PRIME32_2;
2137 statePtr->v[2] = seed + 0;
2138 statePtr->v[3] = seed - XXH_PRIME32_1;
2143 /*! @ingroup xxh32_family */
2144 XXH_PUBLIC_API XXH_errorcode
2145 XXH32_update(XXH32_state_t* state, const void* input, size_t len)
2148 XXH_ASSERT(len == 0);
2152 { const xxh_u8* p = (const xxh_u8*)input;
2153 const xxh_u8* const bEnd = p + len;
2155 state->total_len_32 += (XXH32_hash_t)len;
2156 state->large_len |= (XXH32_hash_t)((len>=16) | (state->total_len_32>=16));
2158 if (state->memsize + len < 16) { /* fill in tmp buffer */
2159 XXH_memcpy((xxh_u8*)(state->mem32) + state->memsize, input, len);
2160 state->memsize += (XXH32_hash_t)len;
2164 if (state->memsize) { /* some data left from previous update */
2165 XXH_memcpy((xxh_u8*)(state->mem32) + state->memsize, input, 16-state->memsize);
2166 { const xxh_u32* p32 = state->mem32;
2167 state->v[0] = XXH32_round(state->v[0], XXH_readLE32(p32)); p32++;
2168 state->v[1] = XXH32_round(state->v[1], XXH_readLE32(p32)); p32++;
2169 state->v[2] = XXH32_round(state->v[2], XXH_readLE32(p32)); p32++;
2170 state->v[3] = XXH32_round(state->v[3], XXH_readLE32(p32));
2172 p += 16-state->memsize;
2177 const xxh_u8* const limit = bEnd - 16;
2180 state->v[0] = XXH32_round(state->v[0], XXH_readLE32(p)); p+=4;
2181 state->v[1] = XXH32_round(state->v[1], XXH_readLE32(p)); p+=4;
2182 state->v[2] = XXH32_round(state->v[2], XXH_readLE32(p)); p+=4;
2183 state->v[3] = XXH32_round(state->v[3], XXH_readLE32(p)); p+=4;
2189 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p));
2190 state->memsize = (unsigned)(bEnd-p);
2198 /*! @ingroup xxh32_family */
2199 XXH_PUBLIC_API XXH32_hash_t XXH32_digest(const XXH32_state_t* state)
2203 if (state->large_len) {
2204 h32 = XXH_rotl32(state->v[0], 1)
2205 + XXH_rotl32(state->v[1], 7)
2206 + XXH_rotl32(state->v[2], 12)
2207 + XXH_rotl32(state->v[3], 18);
2209 h32 = state->v[2] /* == seed */ + XXH_PRIME32_5;
2212 h32 += state->total_len_32;
2214 return XXH32_finalize(h32, (const xxh_u8*)state->mem32, state->memsize, XXH_aligned);
2218 /******* Canonical representation *******/
2221 * @ingroup xxh32_family
2222 * The default return values from XXH functions are unsigned 32 and 64 bit
2225 * The canonical representation uses big endian convention, the same convention
2226 * as human-readable numbers (large digits first).
2228 * This way, hash values can be written into a file or buffer, remaining
2229 * comparable across different systems.
2231 * The following functions allow transformation of hash values to and from their
2234 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash)
2236 /* XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t)); */
2237 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash);
2238 XXH_memcpy(dst, &hash, sizeof(*dst));
2240 /*! @ingroup xxh32_family */
2241 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src)
2243 return XXH_readBE32(src);
2247 #ifndef XXH_NO_LONG_LONG
2249 /* *******************************************************************
2250 * 64-bit hash functions
2251 *********************************************************************/
2257 /******* Memory access *******/
2259 typedef XXH64_hash_t xxh_u64;
2261 #ifdef XXH_OLD_NAMES
2262 # define U64 xxh_u64
2265 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
2267 * Manual byteshift. Best for old compilers which don't inline memcpy.
2268 * We actually directly use XXH_readLE64 and XXH_readBE64.
2270 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
2272 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
2273 static xxh_u64 XXH_read64(const void* memPtr)
2275 return *(const xxh_u64*) memPtr;
2278 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
2281 * __pack instructions are safer, but compiler specific, hence potentially
2282 * problematic for some compilers.
2284 * Currently only defined for GCC and ICC.
2286 #ifdef XXH_OLD_NAMES
2287 typedef union { xxh_u32 u32; xxh_u64 u64; } __attribute__((packed)) unalign64;
2289 static xxh_u64 XXH_read64(const void* ptr)
2291 typedef union { xxh_u32 u32; xxh_u64 u64; } __attribute__((packed)) xxh_unalign64;
2292 return ((const xxh_unalign64*)ptr)->u64;
2298 * Portable and safe solution. Generally efficient.
2299 * see: https://fastcompression.blogspot.com/2015/08/accessing-unaligned-memory.html
2301 static xxh_u64 XXH_read64(const void* memPtr)
2304 XXH_memcpy(&val, memPtr, sizeof(val));
2308 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
2310 #if defined(_MSC_VER) /* Visual Studio */
2311 # define XXH_swap64 _byteswap_uint64
2312 #elif XXH_GCC_VERSION >= 403
2313 # define XXH_swap64 __builtin_bswap64
2315 static xxh_u64 XXH_swap64(xxh_u64 x)
2317 return ((x << 56) & 0xff00000000000000ULL) |
2318 ((x << 40) & 0x00ff000000000000ULL) |
2319 ((x << 24) & 0x0000ff0000000000ULL) |
2320 ((x << 8) & 0x000000ff00000000ULL) |
2321 ((x >> 8) & 0x00000000ff000000ULL) |
2322 ((x >> 24) & 0x0000000000ff0000ULL) |
2323 ((x >> 40) & 0x000000000000ff00ULL) |
2324 ((x >> 56) & 0x00000000000000ffULL);
2329 /* XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load. */
2330 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
2332 XXH_FORCE_INLINE xxh_u64 XXH_readLE64(const void* memPtr)
2334 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr;
2336 | ((xxh_u64)bytePtr[1] << 8)
2337 | ((xxh_u64)bytePtr[2] << 16)
2338 | ((xxh_u64)bytePtr[3] << 24)
2339 | ((xxh_u64)bytePtr[4] << 32)
2340 | ((xxh_u64)bytePtr[5] << 40)
2341 | ((xxh_u64)bytePtr[6] << 48)
2342 | ((xxh_u64)bytePtr[7] << 56);
2345 XXH_FORCE_INLINE xxh_u64 XXH_readBE64(const void* memPtr)
2347 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr;
2349 | ((xxh_u64)bytePtr[6] << 8)
2350 | ((xxh_u64)bytePtr[5] << 16)
2351 | ((xxh_u64)bytePtr[4] << 24)
2352 | ((xxh_u64)bytePtr[3] << 32)
2353 | ((xxh_u64)bytePtr[2] << 40)
2354 | ((xxh_u64)bytePtr[1] << 48)
2355 | ((xxh_u64)bytePtr[0] << 56);
2359 XXH_FORCE_INLINE xxh_u64 XXH_readLE64(const void* ptr)
2361 return XXH_CPU_LITTLE_ENDIAN ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr));
2364 static xxh_u64 XXH_readBE64(const void* ptr)
2366 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr);
2370 XXH_FORCE_INLINE xxh_u64
2371 XXH_readLE64_align(const void* ptr, XXH_alignment align)
2373 if (align==XXH_unaligned)
2374 return XXH_readLE64(ptr);
2376 return XXH_CPU_LITTLE_ENDIAN ? *(const xxh_u64*)ptr : XXH_swap64(*(const xxh_u64*)ptr);
2380 /******* xxh64 *******/
2383 * @defgroup xxh64_impl XXH64 implementation
2387 /* #define rather that static const, to be used as initializers */
2388 #define XXH_PRIME64_1 0x9E3779B185EBCA87ULL /*!< 0b1001111000110111011110011011000110000101111010111100101010000111 */
2389 #define XXH_PRIME64_2 0xC2B2AE3D27D4EB4FULL /*!< 0b1100001010110010101011100011110100100111110101001110101101001111 */
2390 #define XXH_PRIME64_3 0x165667B19E3779F9ULL /*!< 0b0001011001010110011001111011000110011110001101110111100111111001 */
2391 #define XXH_PRIME64_4 0x85EBCA77C2B2AE63ULL /*!< 0b1000010111101011110010100111011111000010101100101010111001100011 */
2392 #define XXH_PRIME64_5 0x27D4EB2F165667C5ULL /*!< 0b0010011111010100111010110010111100010110010101100110011111000101 */
2394 #ifdef XXH_OLD_NAMES
2395 # define PRIME64_1 XXH_PRIME64_1
2396 # define PRIME64_2 XXH_PRIME64_2
2397 # define PRIME64_3 XXH_PRIME64_3
2398 # define PRIME64_4 XXH_PRIME64_4
2399 # define PRIME64_5 XXH_PRIME64_5
2402 static xxh_u64 XXH64_round(xxh_u64 acc, xxh_u64 input)
2404 acc += input * XXH_PRIME64_2;
2405 acc = XXH_rotl64(acc, 31);
2406 acc *= XXH_PRIME64_1;
2410 static xxh_u64 XXH64_mergeRound(xxh_u64 acc, xxh_u64 val)
2412 val = XXH64_round(0, val);
2414 acc = acc * XXH_PRIME64_1 + XXH_PRIME64_4;
2418 static xxh_u64 XXH64_avalanche(xxh_u64 h64)
2421 h64 *= XXH_PRIME64_2;
2423 h64 *= XXH_PRIME64_3;
2429 #define XXH_get64bits(p) XXH_readLE64_align(p, align)
2432 XXH64_finalize(xxh_u64 h64, const xxh_u8* ptr, size_t len, XXH_alignment align)
2434 if (ptr==NULL) XXH_ASSERT(len == 0);
2437 xxh_u64 const k1 = XXH64_round(0, XXH_get64bits(ptr));
2440 h64 = XXH_rotl64(h64,27) * XXH_PRIME64_1 + XXH_PRIME64_4;
2444 h64 ^= (xxh_u64)(XXH_get32bits(ptr)) * XXH_PRIME64_1;
2446 h64 = XXH_rotl64(h64, 23) * XXH_PRIME64_2 + XXH_PRIME64_3;
2450 h64 ^= (*ptr++) * XXH_PRIME64_5;
2451 h64 = XXH_rotl64(h64, 11) * XXH_PRIME64_1;
2454 return XXH64_avalanche(h64);
2457 #ifdef XXH_OLD_NAMES
2458 # define PROCESS1_64 XXH_PROCESS1_64
2459 # define PROCESS4_64 XXH_PROCESS4_64
2460 # define PROCESS8_64 XXH_PROCESS8_64
2462 # undef XXH_PROCESS1_64
2463 # undef XXH_PROCESS4_64
2464 # undef XXH_PROCESS8_64
2467 XXH_FORCE_INLINE xxh_u64
2468 XXH64_endian_align(const xxh_u8* input, size_t len, xxh_u64 seed, XXH_alignment align)
2471 if (input==NULL) XXH_ASSERT(len == 0);
2474 const xxh_u8* const bEnd = input + len;
2475 const xxh_u8* const limit = bEnd - 31;
2476 xxh_u64 v1 = seed + XXH_PRIME64_1 + XXH_PRIME64_2;
2477 xxh_u64 v2 = seed + XXH_PRIME64_2;
2478 xxh_u64 v3 = seed + 0;
2479 xxh_u64 v4 = seed - XXH_PRIME64_1;
2482 v1 = XXH64_round(v1, XXH_get64bits(input)); input+=8;
2483 v2 = XXH64_round(v2, XXH_get64bits(input)); input+=8;
2484 v3 = XXH64_round(v3, XXH_get64bits(input)); input+=8;
2485 v4 = XXH64_round(v4, XXH_get64bits(input)); input+=8;
2486 } while (input<limit);
2488 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
2489 h64 = XXH64_mergeRound(h64, v1);
2490 h64 = XXH64_mergeRound(h64, v2);
2491 h64 = XXH64_mergeRound(h64, v3);
2492 h64 = XXH64_mergeRound(h64, v4);
2495 h64 = seed + XXH_PRIME64_5;
2498 h64 += (xxh_u64) len;
2500 return XXH64_finalize(h64, input, len, align);
2504 /*! @ingroup xxh64_family */
2505 XXH_PUBLIC_API XXH64_hash_t XXH64 (const void* input, size_t len, XXH64_hash_t seed)
2508 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
2509 XXH64_state_t state;
2510 XXH64_reset(&state, seed);
2511 XXH64_update(&state, (const xxh_u8*)input, len);
2512 return XXH64_digest(&state);
2514 if (XXH_FORCE_ALIGN_CHECK) {
2515 if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
2516 return XXH64_endian_align((const xxh_u8*)input, len, seed, XXH_aligned);
2519 return XXH64_endian_align((const xxh_u8*)input, len, seed, XXH_unaligned);
2524 /******* Hash Streaming *******/
2526 /*! @ingroup xxh64_family*/
2527 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void)
2529 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
2531 /*! @ingroup xxh64_family */
2532 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
2538 /*! @ingroup xxh64_family */
2539 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState)
2541 XXH_memcpy(dstState, srcState, sizeof(*dstState));
2544 /*! @ingroup xxh64_family */
2545 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, XXH64_hash_t seed)
2547 XXH_ASSERT(statePtr != NULL);
2548 memset(statePtr, 0, sizeof(*statePtr));
2549 statePtr->v[0] = seed + XXH_PRIME64_1 + XXH_PRIME64_2;
2550 statePtr->v[1] = seed + XXH_PRIME64_2;
2551 statePtr->v[2] = seed + 0;
2552 statePtr->v[3] = seed - XXH_PRIME64_1;
2556 /*! @ingroup xxh64_family */
2557 XXH_PUBLIC_API XXH_errorcode
2558 XXH64_update (XXH64_state_t* state, const void* input, size_t len)
2561 XXH_ASSERT(len == 0);
2565 { const xxh_u8* p = (const xxh_u8*)input;
2566 const xxh_u8* const bEnd = p + len;
2568 state->total_len += len;
2570 if (state->memsize + len < 32) { /* fill in tmp buffer */
2571 XXH_memcpy(((xxh_u8*)state->mem64) + state->memsize, input, len);
2572 state->memsize += (xxh_u32)len;
2576 if (state->memsize) { /* tmp buffer is full */
2577 XXH_memcpy(((xxh_u8*)state->mem64) + state->memsize, input, 32-state->memsize);
2578 state->v[0] = XXH64_round(state->v[0], XXH_readLE64(state->mem64+0));
2579 state->v[1] = XXH64_round(state->v[1], XXH_readLE64(state->mem64+1));
2580 state->v[2] = XXH64_round(state->v[2], XXH_readLE64(state->mem64+2));
2581 state->v[3] = XXH64_round(state->v[3], XXH_readLE64(state->mem64+3));
2582 p += 32 - state->memsize;
2587 const xxh_u8* const limit = bEnd - 32;
2590 state->v[0] = XXH64_round(state->v[0], XXH_readLE64(p)); p+=8;
2591 state->v[1] = XXH64_round(state->v[1], XXH_readLE64(p)); p+=8;
2592 state->v[2] = XXH64_round(state->v[2], XXH_readLE64(p)); p+=8;
2593 state->v[3] = XXH64_round(state->v[3], XXH_readLE64(p)); p+=8;
2599 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p));
2600 state->memsize = (unsigned)(bEnd-p);
2608 /*! @ingroup xxh64_family */
2609 XXH_PUBLIC_API XXH64_hash_t XXH64_digest(const XXH64_state_t* state)
2613 if (state->total_len >= 32) {
2614 h64 = XXH_rotl64(state->v[0], 1) + XXH_rotl64(state->v[1], 7) + XXH_rotl64(state->v[2], 12) + XXH_rotl64(state->v[3], 18);
2615 h64 = XXH64_mergeRound(h64, state->v[0]);
2616 h64 = XXH64_mergeRound(h64, state->v[1]);
2617 h64 = XXH64_mergeRound(h64, state->v[2]);
2618 h64 = XXH64_mergeRound(h64, state->v[3]);
2620 h64 = state->v[2] /*seed*/ + XXH_PRIME64_5;
2623 h64 += (xxh_u64) state->total_len;
2625 return XXH64_finalize(h64, (const xxh_u8*)state->mem64, (size_t)state->total_len, XXH_aligned);
2629 /******* Canonical representation *******/
2631 /*! @ingroup xxh64_family */
2632 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash)
2634 /* XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t)); */
2635 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash);
2636 XXH_memcpy(dst, &hash, sizeof(*dst));
2639 /*! @ingroup xxh64_family */
2640 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src)
2642 return XXH_readBE64(src);
2647 /* *********************************************************************
2649 * New generation hash designed for speed on small keys and vectorization
2650 ************************************************************************ */
2653 * @defgroup xxh3_impl XXH3 implementation
2658 /* === Compiler specifics === */
2660 #if ((defined(sun) || defined(__sun)) && __cplusplus) /* Solaris includes __STDC_VERSION__ with C++. Tested with GCC 5.5 */
2661 # define XXH_RESTRICT /* disable */
2662 #elif defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* >= C99 */
2663 # define XXH_RESTRICT restrict
2665 /* Note: it might be useful to define __restrict or __restrict__ for some C++ compilers */
2666 # define XXH_RESTRICT /* disable */
2669 #if (defined(__GNUC__) && (__GNUC__ >= 3)) \
2670 || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) \
2671 || defined(__clang__)
2672 # define XXH_likely(x) __builtin_expect(x, 1)
2673 # define XXH_unlikely(x) __builtin_expect(x, 0)
2675 # define XXH_likely(x) (x)
2676 # define XXH_unlikely(x) (x)
2679 #if defined(__GNUC__) || defined(__clang__)
2680 # if defined(__ARM_NEON__) || defined(__ARM_NEON) \
2681 || defined(__aarch64__) || defined(_M_ARM) \
2682 || defined(_M_ARM64) || defined(_M_ARM64EC)
2683 # define inline __inline__ /* circumvent a clang bug */
2684 # include <arm_neon.h>
2686 # elif defined(__AVX2__)
2687 # include <immintrin.h>
2688 # elif defined(__SSE2__)
2689 # include <emmintrin.h>
2693 #if defined(_MSC_VER)
2694 # include <intrin.h>
2698 * One goal of XXH3 is to make it fast on both 32-bit and 64-bit, while
2699 * remaining a true 64-bit/128-bit hash function.
2701 * This is done by prioritizing a subset of 64-bit operations that can be
2702 * emulated without too many steps on the average 32-bit machine.
2704 * For example, these two lines seem similar, and run equally fast on 64-bit:
2707 * x ^= (x >> 47); // good
2708 * x ^= (x >> 13); // bad
2710 * However, to a 32-bit machine, there is a major difference.
2712 * x ^= (x >> 47) looks like this:
2714 * x.lo ^= (x.hi >> (47 - 32));
2716 * while x ^= (x >> 13) looks like this:
2718 * // note: funnel shifts are not usually cheap.
2719 * x.lo ^= (x.lo >> 13) | (x.hi << (32 - 13));
2720 * x.hi ^= (x.hi >> 13);
2722 * The first one is significantly faster than the second, simply because the
2723 * shift is larger than 32. This means:
2724 * - All the bits we need are in the upper 32 bits, so we can ignore the lower
2725 * 32 bits in the shift.
2726 * - The shift result will always fit in the lower 32 bits, and therefore,
2727 * we can ignore the upper 32 bits in the xor.
2729 * Thanks to this optimization, XXH3 only requires these features to be efficient:
2731 * - Usable unaligned access
2732 * - A 32-bit or 64-bit ALU
2733 * - If 32-bit, a decent ADC instruction
2734 * - A 32 or 64-bit multiply with a 64-bit result
2735 * - For the 128-bit variant, a decent byteswap helps short inputs.
2737 * The first two are already required by XXH32, and almost all 32-bit and 64-bit
2738 * platforms which can run XXH32 can run XXH3 efficiently.
2740 * Thumb-1, the classic 16-bit only subset of ARM's instruction set, is one
2741 * notable exception.
2743 * First of all, Thumb-1 lacks support for the UMULL instruction which
2744 * performs the important long multiply. This means numerous __aeabi_lmul
2747 * Second of all, the 8 functional registers are just not enough.
2748 * Setup for __aeabi_lmul, byteshift loads, pointers, and all arithmetic need
2749 * Lo registers, and this shuffling results in thousands more MOVs than A32.
2751 * A32 and T32 don't have this limitation. They can access all 14 registers,
2752 * do a 32->64 multiply with UMULL, and the flexible operand allowing free
2753 * shifts is helpful, too.
2755 * Therefore, we do a quick sanity check.
2757 * If compiling Thumb-1 for a target which supports ARM instructions, we will
2758 * emit a warning, as it is not a "sane" platform to compile for.
2760 * Usually, if this happens, it is because of an accident and you probably need
2761 * to specify -march, as you likely meant to compile for a newer architecture.
2763 * Credit: large sections of the vectorial and asm source code paths
2764 * have been contributed by @easyaspi314
2766 #if defined(__thumb__) && !defined(__thumb2__) && defined(__ARM_ARCH_ISA_ARM)
2767 # warning "XXH3 is highly inefficient without ARM or Thumb-2."
2770 /* ==========================================
2771 * Vectorization detection
2772 * ========================================== */
2777 * @brief Overrides the vectorization implementation chosen for XXH3.
2779 * Can be defined to 0 to disable SIMD or any of the values mentioned in
2780 * @ref XXH_VECTOR_TYPE.
2782 * If this is not defined, it uses predefined macros to determine the best
2785 # define XXH_VECTOR XXH_SCALAR
2788 * @brief Possible values for @ref XXH_VECTOR.
2790 * Note that these are actually implemented as macros.
2792 * If this is not defined, it is detected automatically.
2793 * @ref XXH_X86DISPATCH overrides this.
2795 enum XXH_VECTOR_TYPE /* fake enum */ {
2796 XXH_SCALAR = 0, /*!< Portable scalar version */
2798 * SSE2 for Pentium 4, Opteron, all x86_64.
2800 * @note SSE2 is also guaranteed on Windows 10, macOS, and
2803 XXH_AVX2 = 2, /*!< AVX2 for Haswell and Bulldozer */
2804 XXH_AVX512 = 3, /*!< AVX512 for Skylake and Icelake */
2805 XXH_NEON = 4, /*!< NEON for most ARMv7-A and all AArch64 */
2806 XXH_VSX = 5, /*!< VSX and ZVector for POWER8/z13 (64-bit) */
2810 * @brief Selects the minimum alignment for XXH3's accumulators.
2812 * When using SIMD, this should match the alignment required for said vector
2813 * type, so, for example, 32 for AVX2.
2815 * Default: Auto detected.
2817 # define XXH_ACC_ALIGN 8
2820 /* Actual definition */
2822 # define XXH_SCALAR 0
2825 # define XXH_AVX512 3
2830 #ifndef XXH_VECTOR /* can be defined on command line */
2832 defined(__ARM_NEON__) || defined(__ARM_NEON) /* gcc */ \
2833 || defined(_M_ARM) || defined(_M_ARM64) || defined(_M_ARM64EC) /* msvc */ \
2835 defined(_WIN32) || defined(__LITTLE_ENDIAN__) /* little endian only */ \
2836 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) \
2838 # define XXH_VECTOR XXH_NEON
2839 # elif defined(__AVX512F__)
2840 # define XXH_VECTOR XXH_AVX512
2841 # elif defined(__AVX2__)
2842 # define XXH_VECTOR XXH_AVX2
2843 # elif defined(__SSE2__) || defined(_M_AMD64) || defined(_M_X64) || (defined(_M_IX86_FP) && (_M_IX86_FP == 2))
2844 # define XXH_VECTOR XXH_SSE2
2845 # elif (defined(__PPC64__) && defined(__POWER8_VECTOR__)) \
2846 || (defined(__s390x__) && defined(__VEC__)) \
2847 && defined(__GNUC__) /* TODO: IBM XL */
2848 # define XXH_VECTOR XXH_VSX
2850 # define XXH_VECTOR XXH_SCALAR
2855 * Controls the alignment of the accumulator,
2856 * for compatibility with aligned vector loads, which are usually faster.
2858 #ifndef XXH_ACC_ALIGN
2859 # if defined(XXH_X86DISPATCH)
2860 # define XXH_ACC_ALIGN 64 /* for compatibility with avx512 */
2861 # elif XXH_VECTOR == XXH_SCALAR /* scalar */
2862 # define XXH_ACC_ALIGN 8
2863 # elif XXH_VECTOR == XXH_SSE2 /* sse2 */
2864 # define XXH_ACC_ALIGN 16
2865 # elif XXH_VECTOR == XXH_AVX2 /* avx2 */
2866 # define XXH_ACC_ALIGN 32
2867 # elif XXH_VECTOR == XXH_NEON /* neon */
2868 # define XXH_ACC_ALIGN 16
2869 # elif XXH_VECTOR == XXH_VSX /* vsx */
2870 # define XXH_ACC_ALIGN 16
2871 # elif XXH_VECTOR == XXH_AVX512 /* avx512 */
2872 # define XXH_ACC_ALIGN 64
2876 #if defined(XXH_X86DISPATCH) || XXH_VECTOR == XXH_SSE2 \
2877 || XXH_VECTOR == XXH_AVX2 || XXH_VECTOR == XXH_AVX512
2878 # define XXH_SEC_ALIGN XXH_ACC_ALIGN
2880 # define XXH_SEC_ALIGN 8
2885 * GCC usually generates the best code with -O3 for xxHash.
2887 * However, when targeting AVX2, it is overzealous in its unrolling resulting
2888 * in code roughly 3/4 the speed of Clang.
2890 * There are other issues, such as GCC splitting _mm256_loadu_si256 into
2891 * _mm_loadu_si128 + _mm256_inserti128_si256. This is an optimization which
2892 * only applies to Sandy and Ivy Bridge... which don't even support AVX2.
2894 * That is why when compiling the AVX2 version, it is recommended to use either
2895 * -O2 -mavx2 -march=haswell
2897 * -O2 -mavx2 -mno-avx256-split-unaligned-load
2898 * for decent performance, or to use Clang instead.
2900 * Fortunately, we can control the first one with a pragma that forces GCC into
2901 * -O2, but the other one we can't control without "failed to inline always
2902 * inline function due to target mismatch" warnings.
2904 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
2905 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
2906 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
2907 # pragma GCC push_options
2908 # pragma GCC optimize("-O2")
2912 #if XXH_VECTOR == XXH_NEON
2914 * NEON's setup for vmlal_u32 is a little more complicated than it is on
2915 * SSE2, AVX2, and VSX.
2917 * While PMULUDQ and VMULEUW both perform a mask, VMLAL.U32 performs an upcast.
2919 * To do the same operation, the 128-bit 'Q' register needs to be split into
2920 * two 64-bit 'D' registers, performing this operation::
2923 * | '---------. .--------' |
2925 * | .---------' '--------. |
2926 * [ a & 0xFFFFFFFF | b & 0xFFFFFFFF ],[ a >> 32 | b >> 32 ]
2928 * Due to significant changes in aarch64, the fastest method for aarch64 is
2929 * completely different than the fastest method for ARMv7-A.
2931 * ARMv7-A treats D registers as unions overlaying Q registers, so modifying
2932 * D11 will modify the high half of Q5. This is similar to how modifying AH
2933 * will only affect bits 8-15 of AX on x86.
2935 * VZIP takes two registers, and puts even lanes in one register and odd lanes
2938 * On ARMv7-A, this strangely modifies both parameters in place instead of
2939 * taking the usual 3-operand form.
2941 * Therefore, if we want to do this, we can simply use a D-form VZIP.32 on the
2942 * lower and upper halves of the Q register to end up with the high and low
2943 * halves where we want - all in one instruction.
2945 * vzip.32 d10, d11 @ d10 = { d10[0], d11[0] }; d11 = { d10[1], d11[1] }
2947 * Unfortunately we need inline assembly for this: Instructions modifying two
2948 * registers at once is not possible in GCC or Clang's IR, and they have to
2951 * aarch64 requires a different approach.
2953 * In order to make it easier to write a decent compiler for aarch64, many
2954 * quirks were removed, such as conditional execution.
2956 * NEON was also affected by this.
2958 * aarch64 cannot access the high bits of a Q-form register, and writes to a
2959 * D-form register zero the high bits, similar to how writes to W-form scalar
2960 * registers (or DWORD registers on x86_64) work.
2962 * The formerly free vget_high intrinsics now require a vext (with a few
2965 * Additionally, VZIP was replaced by ZIP1 and ZIP2, which are the equivalent
2966 * of PUNPCKL* and PUNPCKH* in SSE, respectively, in order to only modify one
2969 * The equivalent of the VZIP.32 on the lower and upper halves would be this
2972 * ext v2.4s, v0.4s, v0.4s, #2 // v2 = { v0[2], v0[3], v0[0], v0[1] }
2973 * zip1 v1.2s, v0.2s, v2.2s // v1 = { v0[0], v2[0] }
2974 * zip2 v0.2s, v0.2s, v1.2s // v0 = { v0[1], v2[1] }
2976 * Instead, we use a literal downcast, vmovn_u64 (XTN), and vshrn_n_u64 (SHRN):
2978 * shrn v1.2s, v0.2d, #32 // v1 = (uint32x2_t)(v0 >> 32);
2979 * xtn v0.2s, v0.2d // v0 = (uint32x2_t)(v0 & 0xFFFFFFFF);
2981 * This is available on ARMv7-A, but is less efficient than a single VZIP.32.
2985 * Function-like macro:
2986 * void XXH_SPLIT_IN_PLACE(uint64x2_t &in, uint32x2_t &outLo, uint32x2_t &outHi)
2988 * outLo = (uint32x2_t)(in & 0xFFFFFFFF);
2989 * outHi = (uint32x2_t)(in >> 32);
2993 # if !defined(XXH_NO_VZIP_HACK) /* define to disable */ \
2994 && (defined(__GNUC__) || defined(__clang__)) \
2995 && (defined(__arm__) || defined(__thumb__) || defined(_M_ARM))
2996 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \
2998 /* Undocumented GCC/Clang operand modifier: %e0 = lower D half, %f0 = upper D half */ \
2999 /* https://github.com/gcc-mirror/gcc/blob/38cf91e5/gcc/config/arm/arm.c#L22486 */ \
3000 /* https://github.com/llvm-mirror/llvm/blob/2c4ca683/lib/Target/ARM/ARMAsmPrinter.cpp#L399 */ \
3001 __asm__("vzip.32 %e0, %f0" : "+w" (in)); \
3002 (outLo) = vget_low_u32 (vreinterpretq_u32_u64(in)); \
3003 (outHi) = vget_high_u32(vreinterpretq_u32_u64(in)); \
3006 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \
3008 (outLo) = vmovn_u64 (in); \
3009 (outHi) = vshrn_n_u64 ((in), 32); \
3015 * @brief Controls the NEON to scalar ratio for XXH3
3017 * On AArch64 when not optimizing for size, XXH3 will run 6 lanes using NEON and
3018 * 2 lanes on scalar by default.
3020 * This can be set to 2, 4, 6, or 8. ARMv7 will default to all 8 NEON lanes, as the
3021 * emulated 64-bit arithmetic is too slow.
3023 * Modern ARM CPUs are _very_ sensitive to how their pipelines are used.
3025 * For example, the Cortex-A73 can dispatch 3 micro-ops per cycle, but it can't
3026 * have more than 2 NEON (F0/F1) micro-ops. If you are only using NEON instructions,
3027 * you are only using 2/3 of the CPU bandwidth.
3029 * This is even more noticeable on the more advanced cores like the A76 which
3030 * can dispatch 8 micro-ops per cycle, but still only 2 NEON micro-ops at once.
3032 * Therefore, @ref XXH3_NEON_LANES lanes will be processed using NEON, and the
3033 * remaining lanes will use scalar instructions. This improves the bandwidth
3034 * and also gives the integer pipelines something to do besides twiddling loop
3035 * counters and pointers.
3037 * This change benefits CPUs with large micro-op buffers without negatively affecting
3040 * | Chipset | Dispatch type | NEON only | 6:2 hybrid | Diff. |
3041 * |:----------------------|:--------------------|----------:|-----------:|------:|
3042 * | Snapdragon 730 (A76) | 2 NEON/8 micro-ops | 8.8 GB/s | 10.1 GB/s | ~16% |
3043 * | Snapdragon 835 (A73) | 2 NEON/3 micro-ops | 5.1 GB/s | 5.3 GB/s | ~5% |
3044 * | Marvell PXA1928 (A53) | In-order dual-issue | 1.9 GB/s | 1.9 GB/s | 0% |
3046 * It also seems to fix some bad codegen on GCC, making it almost as fast as clang.
3048 * @see XXH3_accumulate_512_neon()
3050 # ifndef XXH3_NEON_LANES
3051 # if (defined(__aarch64__) || defined(__arm64__) || defined(_M_ARM64) || defined(_M_ARM64EC)) \
3052 && !defined(__OPTIMIZE_SIZE__)
3053 # define XXH3_NEON_LANES 6
3055 # define XXH3_NEON_LANES XXH_ACC_NB
3058 #endif /* XXH_VECTOR == XXH_NEON */
3061 * VSX and Z Vector helpers.
3063 * This is very messy, and any pull requests to clean this up are welcome.
3065 * There are a lot of problems with supporting VSX and s390x, due to
3066 * inconsistent intrinsics, spotty coverage, and multiple endiannesses.
3068 #if XXH_VECTOR == XXH_VSX
3069 # if defined(__s390x__)
3070 # include <s390intrin.h>
3072 /* gcc's altivec.h can have the unwanted consequence to unconditionally
3073 * #define bool, vector, and pixel keywords,
3074 * with bad consequences for programs already using these keywords for other purposes.
3075 * The paragraph defining these macros is skipped when __APPLE_ALTIVEC__ is defined.
3076 * __APPLE_ALTIVEC__ is _generally_ defined automatically by the compiler,
3077 * but it seems that, in some cases, it isn't.
3078 * Force the build macro to be defined, so that keywords are not altered.
3080 # if defined(__GNUC__) && !defined(__APPLE_ALTIVEC__)
3081 # define __APPLE_ALTIVEC__
3083 # include <altivec.h>
3086 typedef __vector unsigned long long xxh_u64x2;
3087 typedef __vector unsigned char xxh_u8x16;
3088 typedef __vector unsigned xxh_u32x4;
3091 # if defined(__BIG_ENDIAN__) \
3092 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
3093 # define XXH_VSX_BE 1
3094 # elif defined(__VEC_ELEMENT_REG_ORDER__) && __VEC_ELEMENT_REG_ORDER__ == __ORDER_BIG_ENDIAN__
3095 # warning "-maltivec=be is not recommended. Please use native endianness."
3096 # define XXH_VSX_BE 1
3098 # define XXH_VSX_BE 0
3100 # endif /* !defined(XXH_VSX_BE) */
3103 # if defined(__POWER9_VECTOR__) || (defined(__clang__) && defined(__s390x__))
3104 # define XXH_vec_revb vec_revb
3107 * A polyfill for POWER9's vec_revb().
3109 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_revb(xxh_u64x2 val)
3111 xxh_u8x16 const vByteSwap = { 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
3112 0x0F, 0x0E, 0x0D, 0x0C, 0x0B, 0x0A, 0x09, 0x08 };
3113 return vec_perm(val, val, vByteSwap);
3116 # endif /* XXH_VSX_BE */
3119 * Performs an unaligned vector load and byte swaps it on big endian.
3121 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_loadu(const void *ptr)
3124 XXH_memcpy(&ret, ptr, sizeof(xxh_u64x2));
3126 ret = XXH_vec_revb(ret);
3132 * vec_mulo and vec_mule are very problematic intrinsics on PowerPC
3134 * These intrinsics weren't added until GCC 8, despite existing for a while,
3135 * and they are endian dependent. Also, their meaning swap depending on version.
3137 # if defined(__s390x__)
3138 /* s390x is always big endian, no issue on this platform */
3139 # define XXH_vec_mulo vec_mulo
3140 # define XXH_vec_mule vec_mule
3141 # elif defined(__clang__) && XXH_HAS_BUILTIN(__builtin_altivec_vmuleuw)
3142 /* Clang has a better way to control this, we can just use the builtin which doesn't swap. */
3143 # define XXH_vec_mulo __builtin_altivec_vmulouw
3144 # define XXH_vec_mule __builtin_altivec_vmuleuw
3146 /* gcc needs inline assembly */
3147 /* Adapted from https://github.com/google/highwayhash/blob/master/highwayhash/hh_vsx.h. */
3148 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_mulo(xxh_u32x4 a, xxh_u32x4 b)
3151 __asm__("vmulouw %0, %1, %2" : "=v" (result) : "v" (a), "v" (b));
3154 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_mule(xxh_u32x4 a, xxh_u32x4 b)
3157 __asm__("vmuleuw %0, %1, %2" : "=v" (result) : "v" (a), "v" (b));
3160 # endif /* XXH_vec_mulo, XXH_vec_mule */
3161 #endif /* XXH_VECTOR == XXH_VSX */
3165 * can be disabled, by declaring XXH_NO_PREFETCH build macro */
3166 #if defined(XXH_NO_PREFETCH)
3167 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */
3169 # if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) /* _mm_prefetch() not defined outside of x86/x64 */
3170 # include <mmintrin.h> /* https://msdn.microsoft.com/fr-fr/library/84szxsww(v=vs.90).aspx */
3171 # define XXH_PREFETCH(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T0)
3172 # elif defined(__GNUC__) && ( (__GNUC__ >= 4) || ( (__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) ) )
3173 # define XXH_PREFETCH(ptr) __builtin_prefetch((ptr), 0 /* rw==read */, 3 /* locality */)
3175 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */
3177 #endif /* XXH_NO_PREFETCH */
3180 /* ==========================================
3181 * XXH3 default settings
3182 * ========================================== */
3184 #define XXH_SECRET_DEFAULT_SIZE 192 /* minimum XXH3_SECRET_SIZE_MIN */
3186 #if (XXH_SECRET_DEFAULT_SIZE < XXH3_SECRET_SIZE_MIN)
3187 # error "default keyset is not large enough"
3190 /*! Pseudorandom secret taken directly from FARSH. */
3191 XXH_ALIGN(64) static const xxh_u8 XXH3_kSecret[XXH_SECRET_DEFAULT_SIZE] = {
3192 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
3193 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
3194 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
3195 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
3196 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
3197 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
3198 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
3199 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
3200 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
3201 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
3202 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
3203 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
3207 #ifdef XXH_OLD_NAMES
3208 # define kSecret XXH3_kSecret
3213 * @brief Calculates a 32-bit to 64-bit long multiply.
3215 * Implemented as a macro.
3217 * Wraps `__emulu` on MSVC x86 because it tends to call `__allmul` when it doesn't
3218 * need to (but it shouldn't need to anyways, it is about 7 instructions to do
3219 * a 64x64 multiply...). Since we know that this will _always_ emit `MULL`, we
3220 * use that instead of the normal method.
3222 * If you are compiling for platforms like Thumb-1 and don't have a better option,
3223 * you may also want to write your own long multiply routine here.
3225 * @param x, y Numbers to be multiplied
3226 * @return 64-bit product of the low 32 bits of @p x and @p y.
3228 XXH_FORCE_INLINE xxh_u64
3229 XXH_mult32to64(xxh_u64 x, xxh_u64 y)
3231 return (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF);
3233 #elif defined(_MSC_VER) && defined(_M_IX86)
3234 # define XXH_mult32to64(x, y) __emulu((unsigned)(x), (unsigned)(y))
3237 * Downcast + upcast is usually better than masking on older compilers like
3238 * GCC 4.2 (especially 32-bit ones), all without affecting newer compilers.
3240 * The other method, (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF), will AND both operands
3241 * and perform a full 64x64 multiply -- entirely redundant on 32-bit.
3243 # define XXH_mult32to64(x, y) ((xxh_u64)(xxh_u32)(x) * (xxh_u64)(xxh_u32)(y))
3247 * @brief Calculates a 64->128-bit long multiply.
3249 * Uses `__uint128_t` and `_umul128` if available, otherwise uses a scalar
3252 * @param lhs , rhs The 64-bit integers to be multiplied
3253 * @return The 128-bit result represented in an @ref XXH128_hash_t.
3255 static XXH128_hash_t
3256 XXH_mult64to128(xxh_u64 lhs, xxh_u64 rhs)
3259 * GCC/Clang __uint128_t method.
3261 * On most 64-bit targets, GCC and Clang define a __uint128_t type.
3262 * This is usually the best way as it usually uses a native long 64-bit
3263 * multiply, such as MULQ on x86_64 or MUL + UMULH on aarch64.
3267 * Despite being a 32-bit platform, Clang (and emscripten) define this type
3268 * despite not having the arithmetic for it. This results in a laggy
3269 * compiler builtin call which calculates a full 128-bit multiply.
3270 * In that case it is best to use the portable one.
3271 * https://github.com/Cyan4973/xxHash/issues/211#issuecomment-515575677
3273 #if (defined(__GNUC__) || defined(__clang__)) && !defined(__wasm__) \
3274 && defined(__SIZEOF_INT128__) \
3275 || (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128)
3277 __uint128_t const product = (__uint128_t)lhs * (__uint128_t)rhs;
3279 r128.low64 = (xxh_u64)(product);
3280 r128.high64 = (xxh_u64)(product >> 64);
3284 * MSVC for x64's _umul128 method.
3286 * xxh_u64 _umul128(xxh_u64 Multiplier, xxh_u64 Multiplicand, xxh_u64 *HighProduct);
3288 * This compiles to single operand MUL on x64.
3290 #elif (defined(_M_X64) || defined(_M_IA64)) && !defined(_M_ARM64EC)
3293 # pragma intrinsic(_umul128)
3295 xxh_u64 product_high;
3296 xxh_u64 const product_low = _umul128(lhs, rhs, &product_high);
3298 r128.low64 = product_low;
3299 r128.high64 = product_high;
3303 * MSVC for ARM64's __umulh method.
3305 * This compiles to the same MUL + UMULH as GCC/Clang's __uint128_t method.
3307 #elif defined(_M_ARM64) || defined(_M_ARM64EC)
3310 # pragma intrinsic(__umulh)
3313 r128.low64 = lhs * rhs;
3314 r128.high64 = __umulh(lhs, rhs);
3319 * Portable scalar method. Optimized for 32-bit and 64-bit ALUs.
3321 * This is a fast and simple grade school multiply, which is shown below
3322 * with base 10 arithmetic instead of base 0x100000000.
3324 * 9 3 // D2 lhs = 93
3325 * x 7 5 // D2 rhs = 75
3327 * 1 5 // D2 lo_lo = (93 % 10) * (75 % 10) = 15
3328 * 4 5 | // D2 hi_lo = (93 / 10) * (75 % 10) = 45
3329 * 2 1 | // D2 lo_hi = (93 % 10) * (75 / 10) = 21
3330 * + 6 3 | | // D2 hi_hi = (93 / 10) * (75 / 10) = 63
3332 * 2 7 | // D2 cross = (15 / 10) + (45 % 10) + 21 = 27
3333 * + 6 7 | | // D2 upper = (27 / 10) + (45 / 10) + 63 = 67
3335 * 6 9 7 5 // D4 res = (27 * 10) + (15 % 10) + (67 * 100) = 6975
3337 * The reasons for adding the products like this are:
3338 * 1. It avoids manual carry tracking. Just like how
3339 * (9 * 9) + 9 + 9 = 99, the same applies with this for UINT64_MAX.
3340 * This avoids a lot of complexity.
3342 * 2. It hints for, and on Clang, compiles to, the powerful UMAAL
3343 * instruction available in ARM's Digital Signal Processing extension
3344 * in 32-bit ARMv6 and later, which is shown below:
3346 * void UMAAL(xxh_u32 *RdLo, xxh_u32 *RdHi, xxh_u32 Rn, xxh_u32 Rm)
3348 * xxh_u64 product = (xxh_u64)*RdLo * (xxh_u64)*RdHi + Rn + Rm;
3349 * *RdLo = (xxh_u32)(product & 0xFFFFFFFF);
3350 * *RdHi = (xxh_u32)(product >> 32);
3353 * This instruction was designed for efficient long multiplication, and
3354 * allows this to be calculated in only 4 instructions at speeds
3355 * comparable to some 64-bit ALUs.
3357 * 3. It isn't terrible on other platforms. Usually this will be a couple
3358 * of 32-bit ADD/ADCs.
3361 /* First calculate all of the cross products. */
3362 xxh_u64 const lo_lo = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs & 0xFFFFFFFF);
3363 xxh_u64 const hi_lo = XXH_mult32to64(lhs >> 32, rhs & 0xFFFFFFFF);
3364 xxh_u64 const lo_hi = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs >> 32);
3365 xxh_u64 const hi_hi = XXH_mult32to64(lhs >> 32, rhs >> 32);
3367 /* Now add the products together. These will never overflow. */
3368 xxh_u64 const cross = (lo_lo >> 32) + (hi_lo & 0xFFFFFFFF) + lo_hi;
3369 xxh_u64 const upper = (hi_lo >> 32) + (cross >> 32) + hi_hi;
3370 xxh_u64 const lower = (cross << 32) | (lo_lo & 0xFFFFFFFF);
3374 r128.high64 = upper;
3380 * @brief Calculates a 64-bit to 128-bit multiply, then XOR folds it.
3382 * The reason for the separate function is to prevent passing too many structs
3383 * around by value. This will hopefully inline the multiply, but we don't force it.
3385 * @param lhs , rhs The 64-bit integers to multiply
3386 * @return The low 64 bits of the product XOR'd by the high 64 bits.
3387 * @see XXH_mult64to128()
3390 XXH3_mul128_fold64(xxh_u64 lhs, xxh_u64 rhs)
3392 XXH128_hash_t product = XXH_mult64to128(lhs, rhs);
3393 return product.low64 ^ product.high64;
3396 /*! Seems to produce slightly better code on GCC for some reason. */
3397 XXH_FORCE_INLINE xxh_u64 XXH_xorshift64(xxh_u64 v64, int shift)
3399 XXH_ASSERT(0 <= shift && shift < 64);
3400 return v64 ^ (v64 >> shift);
3404 * This is a fast avalanche stage,
3405 * suitable when input bits are already partially mixed
3407 static XXH64_hash_t XXH3_avalanche(xxh_u64 h64)
3409 h64 = XXH_xorshift64(h64, 37);
3410 h64 *= 0x165667919E3779F9ULL;
3411 h64 = XXH_xorshift64(h64, 32);
3416 * This is a stronger avalanche,
3417 * inspired by Pelle Evensen's rrmxmx
3418 * preferable when input has not been previously mixed
3420 static XXH64_hash_t XXH3_rrmxmx(xxh_u64 h64, xxh_u64 len)
3422 /* this mix is inspired by Pelle Evensen's rrmxmx */
3423 h64 ^= XXH_rotl64(h64, 49) ^ XXH_rotl64(h64, 24);
3424 h64 *= 0x9FB21C651E98DF25ULL;
3425 h64 ^= (h64 >> 35) + len ;
3426 h64 *= 0x9FB21C651E98DF25ULL;
3427 return XXH_xorshift64(h64, 28);
3431 /* ==========================================
3433 * ==========================================
3434 * One of the shortcomings of XXH32 and XXH64 was that their performance was
3435 * sub-optimal on short lengths. It used an iterative algorithm which strongly
3436 * favored lengths that were a multiple of 4 or 8.
3438 * Instead of iterating over individual inputs, we use a set of single shot
3439 * functions which piece together a range of lengths and operate in constant time.
3441 * Additionally, the number of multiplies has been significantly reduced. This
3442 * reduces latency, especially when emulating 64-bit multiplies on 32-bit.
3444 * Depending on the platform, this may or may not be faster than XXH32, but it
3445 * is almost guaranteed to be faster than XXH64.
3449 * At very short lengths, there isn't enough input to fully hide secrets, or use
3450 * the entire secret.
3452 * There is also only a limited amount of mixing we can do before significantly
3453 * impacting performance.
3455 * Therefore, we use different sections of the secret and always mix two secret
3456 * samples with an XOR. This should have no effect on performance on the
3457 * seedless or withSeed variants because everything _should_ be constant folded
3458 * by modern compilers.
3460 * The XOR mixing hides individual parts of the secret and increases entropy.
3462 * This adds an extra layer of strength for custom secrets.
3464 XXH_FORCE_INLINE XXH64_hash_t
3465 XXH3_len_1to3_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
3467 XXH_ASSERT(input != NULL);
3468 XXH_ASSERT(1 <= len && len <= 3);
3469 XXH_ASSERT(secret != NULL);
3471 * len = 1: combined = { input[0], 0x01, input[0], input[0] }
3472 * len = 2: combined = { input[1], 0x02, input[0], input[1] }
3473 * len = 3: combined = { input[2], 0x03, input[0], input[1] }
3475 { xxh_u8 const c1 = input[0];
3476 xxh_u8 const c2 = input[len >> 1];
3477 xxh_u8 const c3 = input[len - 1];
3478 xxh_u32 const combined = ((xxh_u32)c1 << 16) | ((xxh_u32)c2 << 24)
3479 | ((xxh_u32)c3 << 0) | ((xxh_u32)len << 8);
3480 xxh_u64 const bitflip = (XXH_readLE32(secret) ^ XXH_readLE32(secret+4)) + seed;
3481 xxh_u64 const keyed = (xxh_u64)combined ^ bitflip;
3482 return XXH64_avalanche(keyed);
3486 XXH_FORCE_INLINE XXH64_hash_t
3487 XXH3_len_4to8_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
3489 XXH_ASSERT(input != NULL);
3490 XXH_ASSERT(secret != NULL);
3491 XXH_ASSERT(4 <= len && len <= 8);
3492 seed ^= (xxh_u64)XXH_swap32((xxh_u32)seed) << 32;
3493 { xxh_u32 const input1 = XXH_readLE32(input);
3494 xxh_u32 const input2 = XXH_readLE32(input + len - 4);
3495 xxh_u64 const bitflip = (XXH_readLE64(secret+8) ^ XXH_readLE64(secret+16)) - seed;
3496 xxh_u64 const input64 = input2 + (((xxh_u64)input1) << 32);
3497 xxh_u64 const keyed = input64 ^ bitflip;
3498 return XXH3_rrmxmx(keyed, len);
3502 XXH_FORCE_INLINE XXH64_hash_t
3503 XXH3_len_9to16_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
3505 XXH_ASSERT(input != NULL);
3506 XXH_ASSERT(secret != NULL);
3507 XXH_ASSERT(9 <= len && len <= 16);
3508 { xxh_u64 const bitflip1 = (XXH_readLE64(secret+24) ^ XXH_readLE64(secret+32)) + seed;
3509 xxh_u64 const bitflip2 = (XXH_readLE64(secret+40) ^ XXH_readLE64(secret+48)) - seed;
3510 xxh_u64 const input_lo = XXH_readLE64(input) ^ bitflip1;
3511 xxh_u64 const input_hi = XXH_readLE64(input + len - 8) ^ bitflip2;
3512 xxh_u64 const acc = len
3513 + XXH_swap64(input_lo) + input_hi
3514 + XXH3_mul128_fold64(input_lo, input_hi);
3515 return XXH3_avalanche(acc);
3519 XXH_FORCE_INLINE XXH64_hash_t
3520 XXH3_len_0to16_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
3522 XXH_ASSERT(len <= 16);
3523 { if (XXH_likely(len > 8)) return XXH3_len_9to16_64b(input, len, secret, seed);
3524 if (XXH_likely(len >= 4)) return XXH3_len_4to8_64b(input, len, secret, seed);
3525 if (len) return XXH3_len_1to3_64b(input, len, secret, seed);
3526 return XXH64_avalanche(seed ^ (XXH_readLE64(secret+56) ^ XXH_readLE64(secret+64)));
3531 * DISCLAIMER: There are known *seed-dependent* multicollisions here due to
3532 * multiplication by zero, affecting hashes of lengths 17 to 240.
3534 * However, they are very unlikely.
3536 * Keep this in mind when using the unseeded XXH3_64bits() variant: As with all
3537 * unseeded non-cryptographic hashes, it does not attempt to defend itself
3538 * against specially crafted inputs, only random inputs.
3540 * Compared to classic UMAC where a 1 in 2^31 chance of 4 consecutive bytes
3541 * cancelling out the secret is taken an arbitrary number of times (addressed
3542 * in XXH3_accumulate_512), this collision is very unlikely with random inputs
3543 * and/or proper seeding:
3545 * This only has a 1 in 2^63 chance of 8 consecutive bytes cancelling out, in a
3546 * function that is only called up to 16 times per hash with up to 240 bytes of
3549 * This is not too bad for a non-cryptographic hash function, especially with
3550 * only 64 bit outputs.
3552 * The 128-bit variant (which trades some speed for strength) is NOT affected
3553 * by this, although it is always a good idea to use a proper seed if you care
3556 XXH_FORCE_INLINE xxh_u64 XXH3_mix16B(const xxh_u8* XXH_RESTRICT input,
3557 const xxh_u8* XXH_RESTRICT secret, xxh_u64 seed64)
3559 #if defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
3560 && defined(__i386__) && defined(__SSE2__) /* x86 + SSE2 */ \
3561 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable like XXH32 hack */
3564 * GCC for x86 tends to autovectorize the 128-bit multiply, resulting in
3567 * By forcing seed64 into a register, we disrupt the cost model and
3568 * cause it to scalarize. See `XXH32_round()`
3570 * FIXME: Clang's output is still _much_ faster -- On an AMD Ryzen 3600,
3571 * XXH3_64bits @ len=240 runs at 4.6 GB/s with Clang 9, but 3.3 GB/s on
3572 * GCC 9.2, despite both emitting scalar code.
3574 * GCC generates much better scalar code than Clang for the rest of XXH3,
3575 * which is why finding a more optimal codepath is an interest.
3577 XXH_COMPILER_GUARD(seed64);
3579 { xxh_u64 const input_lo = XXH_readLE64(input);
3580 xxh_u64 const input_hi = XXH_readLE64(input+8);
3581 return XXH3_mul128_fold64(
3582 input_lo ^ (XXH_readLE64(secret) + seed64),
3583 input_hi ^ (XXH_readLE64(secret+8) - seed64)
3588 /* For mid range keys, XXH3 uses a Mum-hash variant. */
3589 XXH_FORCE_INLINE XXH64_hash_t
3590 XXH3_len_17to128_64b(const xxh_u8* XXH_RESTRICT input, size_t len,
3591 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
3594 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize;
3595 XXH_ASSERT(16 < len && len <= 128);
3597 { xxh_u64 acc = len * XXH_PRIME64_1;
3601 acc += XXH3_mix16B(input+48, secret+96, seed);
3602 acc += XXH3_mix16B(input+len-64, secret+112, seed);
3604 acc += XXH3_mix16B(input+32, secret+64, seed);
3605 acc += XXH3_mix16B(input+len-48, secret+80, seed);
3607 acc += XXH3_mix16B(input+16, secret+32, seed);
3608 acc += XXH3_mix16B(input+len-32, secret+48, seed);
3610 acc += XXH3_mix16B(input+0, secret+0, seed);
3611 acc += XXH3_mix16B(input+len-16, secret+16, seed);
3613 return XXH3_avalanche(acc);
3617 #define XXH3_MIDSIZE_MAX 240
3619 XXH_NO_INLINE XXH64_hash_t
3620 XXH3_len_129to240_64b(const xxh_u8* XXH_RESTRICT input, size_t len,
3621 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
3624 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize;
3625 XXH_ASSERT(128 < len && len <= XXH3_MIDSIZE_MAX);
3627 #define XXH3_MIDSIZE_STARTOFFSET 3
3628 #define XXH3_MIDSIZE_LASTOFFSET 17
3630 { xxh_u64 acc = len * XXH_PRIME64_1;
3631 int const nbRounds = (int)len / 16;
3633 for (i=0; i<8; i++) {
3634 acc += XXH3_mix16B(input+(16*i), secret+(16*i), seed);
3636 acc = XXH3_avalanche(acc);
3637 XXH_ASSERT(nbRounds >= 8);
3638 #if defined(__clang__) /* Clang */ \
3639 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \
3640 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */
3643 * Clang for ARMv7-A tries to vectorize this loop, similar to GCC x86.
3644 * In everywhere else, it uses scalar code.
3646 * For 64->128-bit multiplies, even if the NEON was 100% optimal, it
3647 * would still be slower than UMAAL (see XXH_mult64to128).
3649 * Unfortunately, Clang doesn't handle the long multiplies properly and
3650 * converts them to the nonexistent "vmulq_u64" intrinsic, which is then
3651 * scalarized into an ugly mess of VMOV.32 instructions.
3653 * This mess is difficult to avoid without turning autovectorization
3654 * off completely, but they are usually relatively minor and/or not
3657 * This loop is the easiest to fix, as unlike XXH32, this pragma
3658 * _actually works_ because it is a loop vectorization instead of an
3659 * SLP vectorization.
3661 #pragma clang loop vectorize(disable)
3663 for (i=8 ; i < nbRounds; i++) {
3664 acc += XXH3_mix16B(input+(16*i), secret+(16*(i-8)) + XXH3_MIDSIZE_STARTOFFSET, seed);
3667 acc += XXH3_mix16B(input + len - 16, secret + XXH3_SECRET_SIZE_MIN - XXH3_MIDSIZE_LASTOFFSET, seed);
3668 return XXH3_avalanche(acc);
3673 /* ======= Long Keys ======= */
3675 #define XXH_STRIPE_LEN 64
3676 #define XXH_SECRET_CONSUME_RATE 8 /* nb of secret bytes consumed at each accumulation */
3677 #define XXH_ACC_NB (XXH_STRIPE_LEN / sizeof(xxh_u64))
3679 #ifdef XXH_OLD_NAMES
3680 # define STRIPE_LEN XXH_STRIPE_LEN
3681 # define ACC_NB XXH_ACC_NB
3684 XXH_FORCE_INLINE void XXH_writeLE64(void* dst, xxh_u64 v64)
3686 if (!XXH_CPU_LITTLE_ENDIAN) v64 = XXH_swap64(v64);
3687 XXH_memcpy(dst, &v64, sizeof(v64));
3690 /* Several intrinsic functions below are supposed to accept __int64 as argument,
3691 * as documented in https://software.intel.com/sites/landingpage/IntrinsicsGuide/ .
3692 * However, several environments do not define __int64 type,
3693 * requiring a workaround.
3695 #if !defined (__VMS) \
3696 && (defined (__cplusplus) \
3697 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
3698 typedef int64_t xxh_i64;
3700 /* the following type must have a width of 64-bit */
3701 typedef long long xxh_i64;
3706 * XXH3_accumulate_512 is the tightest loop for long inputs, and it is the most optimized.
3708 * It is a hardened version of UMAC, based off of FARSH's implementation.
3710 * This was chosen because it adapts quite well to 32-bit, 64-bit, and SIMD
3711 * implementations, and it is ridiculously fast.
3713 * We harden it by mixing the original input to the accumulators as well as the product.
3715 * This means that in the (relatively likely) case of a multiply by zero, the
3716 * original input is preserved.
3718 * On 128-bit inputs, we swap 64-bit pairs when we add the input to improve
3719 * cross-pollination, as otherwise the upper and lower halves would be
3720 * essentially independent.
3722 * This doesn't matter on 64-bit hashes since they all get merged together in
3723 * the end, so we skip the extra step.
3725 * Both XXH3_64bits and XXH3_128bits use this subroutine.
3728 #if (XXH_VECTOR == XXH_AVX512) \
3729 || (defined(XXH_DISPATCH_AVX512) && XXH_DISPATCH_AVX512 != 0)
3731 #ifndef XXH_TARGET_AVX512
3732 # define XXH_TARGET_AVX512 /* disable attribute target */
3735 XXH_FORCE_INLINE XXH_TARGET_AVX512 void
3736 XXH3_accumulate_512_avx512(void* XXH_RESTRICT acc,
3737 const void* XXH_RESTRICT input,
3738 const void* XXH_RESTRICT secret)
3740 __m512i* const xacc = (__m512i *) acc;
3741 XXH_ASSERT((((size_t)acc) & 63) == 0);
3742 XXH_STATIC_ASSERT(XXH_STRIPE_LEN == sizeof(__m512i));
3745 /* data_vec = input[0]; */
3746 __m512i const data_vec = _mm512_loadu_si512 (input);
3747 /* key_vec = secret[0]; */
3748 __m512i const key_vec = _mm512_loadu_si512 (secret);
3749 /* data_key = data_vec ^ key_vec; */
3750 __m512i const data_key = _mm512_xor_si512 (data_vec, key_vec);
3751 /* data_key_lo = data_key >> 32; */
3752 __m512i const data_key_lo = _mm512_shuffle_epi32 (data_key, (_MM_PERM_ENUM)_MM_SHUFFLE(0, 3, 0, 1));
3753 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3754 __m512i const product = _mm512_mul_epu32 (data_key, data_key_lo);
3755 /* xacc[0] += swap(data_vec); */
3756 __m512i const data_swap = _mm512_shuffle_epi32(data_vec, (_MM_PERM_ENUM)_MM_SHUFFLE(1, 0, 3, 2));
3757 __m512i const sum = _mm512_add_epi64(*xacc, data_swap);
3758 /* xacc[0] += product; */
3759 *xacc = _mm512_add_epi64(product, sum);
3764 * XXH3_scrambleAcc: Scrambles the accumulators to improve mixing.
3766 * Multiplication isn't perfect, as explained by Google in HighwayHash:
3768 * // Multiplication mixes/scrambles bytes 0-7 of the 64-bit result to
3769 * // varying degrees. In descending order of goodness, bytes
3770 * // 3 4 2 5 1 6 0 7 have quality 228 224 164 160 100 96 36 32.
3771 * // As expected, the upper and lower bytes are much worse.
3773 * Source: https://github.com/google/highwayhash/blob/0aaf66b/highwayhash/hh_avx2.h#L291
3775 * Since our algorithm uses a pseudorandom secret to add some variance into the
3776 * mix, we don't need to (or want to) mix as often or as much as HighwayHash does.
3778 * This isn't as tight as XXH3_accumulate, but still written in SIMD to avoid
3781 * Both XXH3_64bits and XXH3_128bits use this subroutine.
3784 XXH_FORCE_INLINE XXH_TARGET_AVX512 void
3785 XXH3_scrambleAcc_avx512(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
3787 XXH_ASSERT((((size_t)acc) & 63) == 0);
3788 XXH_STATIC_ASSERT(XXH_STRIPE_LEN == sizeof(__m512i));
3789 { __m512i* const xacc = (__m512i*) acc;
3790 const __m512i prime32 = _mm512_set1_epi32((int)XXH_PRIME32_1);
3792 /* xacc[0] ^= (xacc[0] >> 47) */
3793 __m512i const acc_vec = *xacc;
3794 __m512i const shifted = _mm512_srli_epi64 (acc_vec, 47);
3795 __m512i const data_vec = _mm512_xor_si512 (acc_vec, shifted);
3796 /* xacc[0] ^= secret; */
3797 __m512i const key_vec = _mm512_loadu_si512 (secret);
3798 __m512i const data_key = _mm512_xor_si512 (data_vec, key_vec);
3800 /* xacc[0] *= XXH_PRIME32_1; */
3801 __m512i const data_key_hi = _mm512_shuffle_epi32 (data_key, (_MM_PERM_ENUM)_MM_SHUFFLE(0, 3, 0, 1));
3802 __m512i const prod_lo = _mm512_mul_epu32 (data_key, prime32);
3803 __m512i const prod_hi = _mm512_mul_epu32 (data_key_hi, prime32);
3804 *xacc = _mm512_add_epi64(prod_lo, _mm512_slli_epi64(prod_hi, 32));
3808 XXH_FORCE_INLINE XXH_TARGET_AVX512 void
3809 XXH3_initCustomSecret_avx512(void* XXH_RESTRICT customSecret, xxh_u64 seed64)
3811 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 63) == 0);
3812 XXH_STATIC_ASSERT(XXH_SEC_ALIGN == 64);
3813 XXH_ASSERT(((size_t)customSecret & 63) == 0);
3814 (void)(&XXH_writeLE64);
3815 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / sizeof(__m512i);
3816 __m512i const seed = _mm512_mask_set1_epi64(_mm512_set1_epi64((xxh_i64)seed64), 0xAA, (xxh_i64)(0U - seed64));
3818 const __m512i* const src = (const __m512i*) ((const void*) XXH3_kSecret);
3819 __m512i* const dest = ( __m512i*) customSecret;
3821 XXH_ASSERT(((size_t)src & 63) == 0); /* control alignment */
3822 XXH_ASSERT(((size_t)dest & 63) == 0);
3823 for (i=0; i < nbRounds; ++i) {
3824 /* GCC has a bug, _mm512_stream_load_si512 accepts 'void*', not 'void const*',
3825 * this will warn "discards 'const' qualifier". */
3829 } remote_const_void;
3830 remote_const_void.cp = src + i;
3831 dest[i] = _mm512_add_epi64(_mm512_stream_load_si512(remote_const_void.p), seed);
3837 #if (XXH_VECTOR == XXH_AVX2) \
3838 || (defined(XXH_DISPATCH_AVX2) && XXH_DISPATCH_AVX2 != 0)
3840 #ifndef XXH_TARGET_AVX2
3841 # define XXH_TARGET_AVX2 /* disable attribute target */
3844 XXH_FORCE_INLINE XXH_TARGET_AVX2 void
3845 XXH3_accumulate_512_avx2( void* XXH_RESTRICT acc,
3846 const void* XXH_RESTRICT input,
3847 const void* XXH_RESTRICT secret)
3849 XXH_ASSERT((((size_t)acc) & 31) == 0);
3850 { __m256i* const xacc = (__m256i *) acc;
3851 /* Unaligned. This is mainly for pointer arithmetic, and because
3852 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3853 const __m256i* const xinput = (const __m256i *) input;
3854 /* Unaligned. This is mainly for pointer arithmetic, and because
3855 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3856 const __m256i* const xsecret = (const __m256i *) secret;
3859 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m256i); i++) {
3860 /* data_vec = xinput[i]; */
3861 __m256i const data_vec = _mm256_loadu_si256 (xinput+i);
3862 /* key_vec = xsecret[i]; */
3863 __m256i const key_vec = _mm256_loadu_si256 (xsecret+i);
3864 /* data_key = data_vec ^ key_vec; */
3865 __m256i const data_key = _mm256_xor_si256 (data_vec, key_vec);
3866 /* data_key_lo = data_key >> 32; */
3867 __m256i const data_key_lo = _mm256_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1));
3868 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3869 __m256i const product = _mm256_mul_epu32 (data_key, data_key_lo);
3870 /* xacc[i] += swap(data_vec); */
3871 __m256i const data_swap = _mm256_shuffle_epi32(data_vec, _MM_SHUFFLE(1, 0, 3, 2));
3872 __m256i const sum = _mm256_add_epi64(xacc[i], data_swap);
3873 /* xacc[i] += product; */
3874 xacc[i] = _mm256_add_epi64(product, sum);
3878 XXH_FORCE_INLINE XXH_TARGET_AVX2 void
3879 XXH3_scrambleAcc_avx2(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
3881 XXH_ASSERT((((size_t)acc) & 31) == 0);
3882 { __m256i* const xacc = (__m256i*) acc;
3883 /* Unaligned. This is mainly for pointer arithmetic, and because
3884 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3885 const __m256i* const xsecret = (const __m256i *) secret;
3886 const __m256i prime32 = _mm256_set1_epi32((int)XXH_PRIME32_1);
3889 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m256i); i++) {
3890 /* xacc[i] ^= (xacc[i] >> 47) */
3891 __m256i const acc_vec = xacc[i];
3892 __m256i const shifted = _mm256_srli_epi64 (acc_vec, 47);
3893 __m256i const data_vec = _mm256_xor_si256 (acc_vec, shifted);
3894 /* xacc[i] ^= xsecret; */
3895 __m256i const key_vec = _mm256_loadu_si256 (xsecret+i);
3896 __m256i const data_key = _mm256_xor_si256 (data_vec, key_vec);
3898 /* xacc[i] *= XXH_PRIME32_1; */
3899 __m256i const data_key_hi = _mm256_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1));
3900 __m256i const prod_lo = _mm256_mul_epu32 (data_key, prime32);
3901 __m256i const prod_hi = _mm256_mul_epu32 (data_key_hi, prime32);
3902 xacc[i] = _mm256_add_epi64(prod_lo, _mm256_slli_epi64(prod_hi, 32));
3907 XXH_FORCE_INLINE XXH_TARGET_AVX2 void XXH3_initCustomSecret_avx2(void* XXH_RESTRICT customSecret, xxh_u64 seed64)
3909 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 31) == 0);
3910 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE / sizeof(__m256i)) == 6);
3911 XXH_STATIC_ASSERT(XXH_SEC_ALIGN <= 64);
3912 (void)(&XXH_writeLE64);
3913 XXH_PREFETCH(customSecret);
3914 { __m256i const seed = _mm256_set_epi64x((xxh_i64)(0U - seed64), (xxh_i64)seed64, (xxh_i64)(0U - seed64), (xxh_i64)seed64);
3916 const __m256i* const src = (const __m256i*) ((const void*) XXH3_kSecret);
3917 __m256i* dest = ( __m256i*) customSecret;
3919 # if defined(__GNUC__) || defined(__clang__)
3921 * On GCC & Clang, marking 'dest' as modified will cause the compiler:
3922 * - do not extract the secret from sse registers in the internal loop
3923 * - use less common registers, and avoid pushing these reg into stack
3925 XXH_COMPILER_GUARD(dest);
3927 XXH_ASSERT(((size_t)src & 31) == 0); /* control alignment */
3928 XXH_ASSERT(((size_t)dest & 31) == 0);
3930 /* GCC -O2 need unroll loop manually */
3931 dest[0] = _mm256_add_epi64(_mm256_stream_load_si256(src+0), seed);
3932 dest[1] = _mm256_add_epi64(_mm256_stream_load_si256(src+1), seed);
3933 dest[2] = _mm256_add_epi64(_mm256_stream_load_si256(src+2), seed);
3934 dest[3] = _mm256_add_epi64(_mm256_stream_load_si256(src+3), seed);
3935 dest[4] = _mm256_add_epi64(_mm256_stream_load_si256(src+4), seed);
3936 dest[5] = _mm256_add_epi64(_mm256_stream_load_si256(src+5), seed);
3942 /* x86dispatch always generates SSE2 */
3943 #if (XXH_VECTOR == XXH_SSE2) || defined(XXH_X86DISPATCH)
3945 #ifndef XXH_TARGET_SSE2
3946 # define XXH_TARGET_SSE2 /* disable attribute target */
3949 XXH_FORCE_INLINE XXH_TARGET_SSE2 void
3950 XXH3_accumulate_512_sse2( void* XXH_RESTRICT acc,
3951 const void* XXH_RESTRICT input,
3952 const void* XXH_RESTRICT secret)
3954 /* SSE2 is just a half-scale version of the AVX2 version. */
3955 XXH_ASSERT((((size_t)acc) & 15) == 0);
3956 { __m128i* const xacc = (__m128i *) acc;
3957 /* Unaligned. This is mainly for pointer arithmetic, and because
3958 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3959 const __m128i* const xinput = (const __m128i *) input;
3960 /* Unaligned. This is mainly for pointer arithmetic, and because
3961 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3962 const __m128i* const xsecret = (const __m128i *) secret;
3965 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m128i); i++) {
3966 /* data_vec = xinput[i]; */
3967 __m128i const data_vec = _mm_loadu_si128 (xinput+i);
3968 /* key_vec = xsecret[i]; */
3969 __m128i const key_vec = _mm_loadu_si128 (xsecret+i);
3970 /* data_key = data_vec ^ key_vec; */
3971 __m128i const data_key = _mm_xor_si128 (data_vec, key_vec);
3972 /* data_key_lo = data_key >> 32; */
3973 __m128i const data_key_lo = _mm_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1));
3974 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3975 __m128i const product = _mm_mul_epu32 (data_key, data_key_lo);
3976 /* xacc[i] += swap(data_vec); */
3977 __m128i const data_swap = _mm_shuffle_epi32(data_vec, _MM_SHUFFLE(1,0,3,2));
3978 __m128i const sum = _mm_add_epi64(xacc[i], data_swap);
3979 /* xacc[i] += product; */
3980 xacc[i] = _mm_add_epi64(product, sum);
3984 XXH_FORCE_INLINE XXH_TARGET_SSE2 void
3985 XXH3_scrambleAcc_sse2(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
3987 XXH_ASSERT((((size_t)acc) & 15) == 0);
3988 { __m128i* const xacc = (__m128i*) acc;
3989 /* Unaligned. This is mainly for pointer arithmetic, and because
3990 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3991 const __m128i* const xsecret = (const __m128i *) secret;
3992 const __m128i prime32 = _mm_set1_epi32((int)XXH_PRIME32_1);
3995 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m128i); i++) {
3996 /* xacc[i] ^= (xacc[i] >> 47) */
3997 __m128i const acc_vec = xacc[i];
3998 __m128i const shifted = _mm_srli_epi64 (acc_vec, 47);
3999 __m128i const data_vec = _mm_xor_si128 (acc_vec, shifted);
4000 /* xacc[i] ^= xsecret[i]; */
4001 __m128i const key_vec = _mm_loadu_si128 (xsecret+i);
4002 __m128i const data_key = _mm_xor_si128 (data_vec, key_vec);
4004 /* xacc[i] *= XXH_PRIME32_1; */
4005 __m128i const data_key_hi = _mm_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1));
4006 __m128i const prod_lo = _mm_mul_epu32 (data_key, prime32);
4007 __m128i const prod_hi = _mm_mul_epu32 (data_key_hi, prime32);
4008 xacc[i] = _mm_add_epi64(prod_lo, _mm_slli_epi64(prod_hi, 32));
4013 XXH_FORCE_INLINE XXH_TARGET_SSE2 void XXH3_initCustomSecret_sse2(void* XXH_RESTRICT customSecret, xxh_u64 seed64)
4015 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 15) == 0);
4016 (void)(&XXH_writeLE64);
4017 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / sizeof(__m128i);
4019 # if defined(_MSC_VER) && defined(_M_IX86) && _MSC_VER < 1900
4020 /* MSVC 32bit mode does not support _mm_set_epi64x before 2015 */
4021 XXH_ALIGN(16) const xxh_i64 seed64x2[2] = { (xxh_i64)seed64, (xxh_i64)(0U - seed64) };
4022 __m128i const seed = _mm_load_si128((__m128i const*)seed64x2);
4024 __m128i const seed = _mm_set_epi64x((xxh_i64)(0U - seed64), (xxh_i64)seed64);
4028 const void* const src16 = XXH3_kSecret;
4029 __m128i* dst16 = (__m128i*) customSecret;
4030 # if defined(__GNUC__) || defined(__clang__)
4032 * On GCC & Clang, marking 'dest' as modified will cause the compiler:
4033 * - do not extract the secret from sse registers in the internal loop
4034 * - use less common registers, and avoid pushing these reg into stack
4036 XXH_COMPILER_GUARD(dst16);
4038 XXH_ASSERT(((size_t)src16 & 15) == 0); /* control alignment */
4039 XXH_ASSERT(((size_t)dst16 & 15) == 0);
4041 for (i=0; i < nbRounds; ++i) {
4042 dst16[i] = _mm_add_epi64(_mm_load_si128((const __m128i *)src16+i), seed);
4048 #if (XXH_VECTOR == XXH_NEON)
4050 /* forward declarations for the scalar routines */
4051 XXH_FORCE_INLINE void
4052 XXH3_scalarRound(void* XXH_RESTRICT acc, void const* XXH_RESTRICT input,
4053 void const* XXH_RESTRICT secret, size_t lane);
4055 XXH_FORCE_INLINE void
4056 XXH3_scalarScrambleRound(void* XXH_RESTRICT acc,
4057 void const* XXH_RESTRICT secret, size_t lane);
4061 * @brief The bulk processing loop for NEON.
4063 * The NEON code path is actually partially scalar when running on AArch64. This
4064 * is to optimize the pipelining and can have up to 15% speedup depending on the
4065 * CPU, and it also mitigates some GCC codegen issues.
4067 * @see XXH3_NEON_LANES for configuring this and details about this optimization.
4069 XXH_FORCE_INLINE void
4070 XXH3_accumulate_512_neon( void* XXH_RESTRICT acc,
4071 const void* XXH_RESTRICT input,
4072 const void* XXH_RESTRICT secret)
4074 XXH_ASSERT((((size_t)acc) & 15) == 0);
4075 XXH_STATIC_ASSERT(XXH3_NEON_LANES > 0 && XXH3_NEON_LANES <= XXH_ACC_NB && XXH3_NEON_LANES % 2 == 0);
4077 uint64x2_t* const xacc = (uint64x2_t *) acc;
4078 /* We don't use a uint32x4_t pointer because it causes bus errors on ARMv7. */
4079 uint8_t const* const xinput = (const uint8_t *) input;
4080 uint8_t const* const xsecret = (const uint8_t *) secret;
4083 /* NEON for the first few lanes (these loops are normally interleaved) */
4084 for (i=0; i < XXH3_NEON_LANES / 2; i++) {
4085 /* data_vec = xinput[i]; */
4086 uint8x16_t data_vec = vld1q_u8(xinput + (i * 16));
4087 /* key_vec = xsecret[i]; */
4088 uint8x16_t key_vec = vld1q_u8(xsecret + (i * 16));
4089 uint64x2_t data_key;
4090 uint32x2_t data_key_lo, data_key_hi;
4091 /* xacc[i] += swap(data_vec); */
4092 uint64x2_t const data64 = vreinterpretq_u64_u8(data_vec);
4093 uint64x2_t const swapped = vextq_u64(data64, data64, 1);
4094 xacc[i] = vaddq_u64 (xacc[i], swapped);
4095 /* data_key = data_vec ^ key_vec; */
4096 data_key = vreinterpretq_u64_u8(veorq_u8(data_vec, key_vec));
4097 /* data_key_lo = (uint32x2_t) (data_key & 0xFFFFFFFF);
4098 * data_key_hi = (uint32x2_t) (data_key >> 32);
4099 * data_key = UNDEFINED; */
4100 XXH_SPLIT_IN_PLACE(data_key, data_key_lo, data_key_hi);
4101 /* xacc[i] += (uint64x2_t) data_key_lo * (uint64x2_t) data_key_hi; */
4102 xacc[i] = vmlal_u32 (xacc[i], data_key_lo, data_key_hi);
4105 /* Scalar for the remainder. This may be a zero iteration loop. */
4106 for (i = XXH3_NEON_LANES; i < XXH_ACC_NB; i++) {
4107 XXH3_scalarRound(acc, input, secret, i);
4112 XXH_FORCE_INLINE void
4113 XXH3_scrambleAcc_neon(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
4115 XXH_ASSERT((((size_t)acc) & 15) == 0);
4117 { uint64x2_t* xacc = (uint64x2_t*) acc;
4118 uint8_t const* xsecret = (uint8_t const*) secret;
4119 uint32x2_t prime = vdup_n_u32 (XXH_PRIME32_1);
4122 /* NEON for the first few lanes (these loops are normally interleaved) */
4123 for (i=0; i < XXH3_NEON_LANES / 2; i++) {
4124 /* xacc[i] ^= (xacc[i] >> 47); */
4125 uint64x2_t acc_vec = xacc[i];
4126 uint64x2_t shifted = vshrq_n_u64 (acc_vec, 47);
4127 uint64x2_t data_vec = veorq_u64 (acc_vec, shifted);
4129 /* xacc[i] ^= xsecret[i]; */
4130 uint8x16_t key_vec = vld1q_u8 (xsecret + (i * 16));
4131 uint64x2_t data_key = veorq_u64 (data_vec, vreinterpretq_u64_u8(key_vec));
4133 /* xacc[i] *= XXH_PRIME32_1 */
4134 uint32x2_t data_key_lo, data_key_hi;
4135 /* data_key_lo = (uint32x2_t) (xacc[i] & 0xFFFFFFFF);
4136 * data_key_hi = (uint32x2_t) (xacc[i] >> 32);
4137 * xacc[i] = UNDEFINED; */
4138 XXH_SPLIT_IN_PLACE(data_key, data_key_lo, data_key_hi);
4140 * prod_hi = (data_key >> 32) * XXH_PRIME32_1;
4142 * Avoid vmul_u32 + vshll_n_u32 since Clang 6 and 7 will
4143 * incorrectly "optimize" this:
4144 * tmp = vmul_u32(vmovn_u64(a), vmovn_u64(b));
4145 * shifted = vshll_n_u32(tmp, 32);
4147 * tmp = "vmulq_u64"(a, b); // no such thing!
4148 * shifted = vshlq_n_u64(tmp, 32);
4150 * However, unlike SSE, Clang lacks a 64-bit multiply routine
4151 * for NEON, and it scalarizes two 64-bit multiplies instead.
4153 * vmull_u32 has the same timing as vmul_u32, and it avoids
4154 * this bug completely.
4155 * See https://bugs.llvm.org/show_bug.cgi?id=39967
4157 uint64x2_t prod_hi = vmull_u32 (data_key_hi, prime);
4158 /* xacc[i] = prod_hi << 32; */
4159 xacc[i] = vshlq_n_u64(prod_hi, 32);
4160 /* xacc[i] += (prod_hi & 0xFFFFFFFF) * XXH_PRIME32_1; */
4161 xacc[i] = vmlal_u32(xacc[i], data_key_lo, prime);
4164 /* Scalar for the remainder. This may be a zero iteration loop. */
4165 for (i = XXH3_NEON_LANES; i < XXH_ACC_NB; i++) {
4166 XXH3_scalarScrambleRound(acc, secret, i);
4173 #if (XXH_VECTOR == XXH_VSX)
4175 XXH_FORCE_INLINE void
4176 XXH3_accumulate_512_vsx( void* XXH_RESTRICT acc,
4177 const void* XXH_RESTRICT input,
4178 const void* XXH_RESTRICT secret)
4180 /* presumed aligned */
4181 unsigned int* const xacc = (unsigned int*) acc;
4182 xxh_u64x2 const* const xinput = (xxh_u64x2 const*) input; /* no alignment restriction */
4183 xxh_u64x2 const* const xsecret = (xxh_u64x2 const*) secret; /* no alignment restriction */
4184 xxh_u64x2 const v32 = { 32, 32 };
4186 for (i = 0; i < XXH_STRIPE_LEN / sizeof(xxh_u64x2); i++) {
4187 /* data_vec = xinput[i]; */
4188 xxh_u64x2 const data_vec = XXH_vec_loadu(xinput + i);
4189 /* key_vec = xsecret[i]; */
4190 xxh_u64x2 const key_vec = XXH_vec_loadu(xsecret + i);
4191 xxh_u64x2 const data_key = data_vec ^ key_vec;
4192 /* shuffled = (data_key << 32) | (data_key >> 32); */
4193 xxh_u32x4 const shuffled = (xxh_u32x4)vec_rl(data_key, v32);
4194 /* product = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)shuffled & 0xFFFFFFFF); */
4195 xxh_u64x2 const product = XXH_vec_mulo((xxh_u32x4)data_key, shuffled);
4196 /* acc_vec = xacc[i]; */
4197 xxh_u64x2 acc_vec = (xxh_u64x2)vec_xl(0, xacc + 4 * i);
4200 /* swap high and low halves */
4202 acc_vec += vec_permi(data_vec, data_vec, 2);
4204 acc_vec += vec_xxpermdi(data_vec, data_vec, 2);
4206 /* xacc[i] = acc_vec; */
4207 vec_xst((xxh_u32x4)acc_vec, 0, xacc + 4 * i);
4211 XXH_FORCE_INLINE void
4212 XXH3_scrambleAcc_vsx(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
4214 XXH_ASSERT((((size_t)acc) & 15) == 0);
4216 { xxh_u64x2* const xacc = (xxh_u64x2*) acc;
4217 const xxh_u64x2* const xsecret = (const xxh_u64x2*) secret;
4219 xxh_u64x2 const v32 = { 32, 32 };
4220 xxh_u64x2 const v47 = { 47, 47 };
4221 xxh_u32x4 const prime = { XXH_PRIME32_1, XXH_PRIME32_1, XXH_PRIME32_1, XXH_PRIME32_1 };
4223 for (i = 0; i < XXH_STRIPE_LEN / sizeof(xxh_u64x2); i++) {
4224 /* xacc[i] ^= (xacc[i] >> 47); */
4225 xxh_u64x2 const acc_vec = xacc[i];
4226 xxh_u64x2 const data_vec = acc_vec ^ (acc_vec >> v47);
4228 /* xacc[i] ^= xsecret[i]; */
4229 xxh_u64x2 const key_vec = XXH_vec_loadu(xsecret + i);
4230 xxh_u64x2 const data_key = data_vec ^ key_vec;
4232 /* xacc[i] *= XXH_PRIME32_1 */
4233 /* prod_lo = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)prime & 0xFFFFFFFF); */
4234 xxh_u64x2 const prod_even = XXH_vec_mule((xxh_u32x4)data_key, prime);
4235 /* prod_hi = ((xxh_u64x2)data_key >> 32) * ((xxh_u64x2)prime >> 32); */
4236 xxh_u64x2 const prod_odd = XXH_vec_mulo((xxh_u32x4)data_key, prime);
4237 xacc[i] = prod_odd + (prod_even << v32);
4243 /* scalar variants - universal */
4247 * @brief Scalar round for @ref XXH3_accumulate_512_scalar().
4249 * This is extracted to its own function because the NEON path uses a combination
4250 * of NEON and scalar.
4252 XXH_FORCE_INLINE void
4253 XXH3_scalarRound(void* XXH_RESTRICT acc,
4254 void const* XXH_RESTRICT input,
4255 void const* XXH_RESTRICT secret,
4258 xxh_u64* xacc = (xxh_u64*) acc;
4259 xxh_u8 const* xinput = (xxh_u8 const*) input;
4260 xxh_u8 const* xsecret = (xxh_u8 const*) secret;
4261 XXH_ASSERT(lane < XXH_ACC_NB);
4262 XXH_ASSERT(((size_t)acc & (XXH_ACC_ALIGN-1)) == 0);
4264 xxh_u64 const data_val = XXH_readLE64(xinput + lane * 8);
4265 xxh_u64 const data_key = data_val ^ XXH_readLE64(xsecret + lane * 8);
4266 xacc[lane ^ 1] += data_val; /* swap adjacent lanes */
4267 xacc[lane] += XXH_mult32to64(data_key & 0xFFFFFFFF, data_key >> 32);
4273 * @brief Processes a 64 byte block of data using the scalar path.
4275 XXH_FORCE_INLINE void
4276 XXH3_accumulate_512_scalar(void* XXH_RESTRICT acc,
4277 const void* XXH_RESTRICT input,
4278 const void* XXH_RESTRICT secret)
4281 for (i=0; i < XXH_ACC_NB; i++) {
4282 XXH3_scalarRound(acc, input, secret, i);
4288 * @brief Scalar scramble step for @ref XXH3_scrambleAcc_scalar().
4290 * This is extracted to its own function because the NEON path uses a combination
4291 * of NEON and scalar.
4293 XXH_FORCE_INLINE void
4294 XXH3_scalarScrambleRound(void* XXH_RESTRICT acc,
4295 void const* XXH_RESTRICT secret,
4298 xxh_u64* const xacc = (xxh_u64*) acc; /* presumed aligned */
4299 const xxh_u8* const xsecret = (const xxh_u8*) secret; /* no alignment restriction */
4300 XXH_ASSERT((((size_t)acc) & (XXH_ACC_ALIGN-1)) == 0);
4301 XXH_ASSERT(lane < XXH_ACC_NB);
4303 xxh_u64 const key64 = XXH_readLE64(xsecret + lane * 8);
4304 xxh_u64 acc64 = xacc[lane];
4305 acc64 = XXH_xorshift64(acc64, 47);
4307 acc64 *= XXH_PRIME32_1;
4314 * @brief Scrambles the accumulators after a large chunk has been read
4316 XXH_FORCE_INLINE void
4317 XXH3_scrambleAcc_scalar(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret)
4320 for (i=0; i < XXH_ACC_NB; i++) {
4321 XXH3_scalarScrambleRound(acc, secret, i);
4325 XXH_FORCE_INLINE void
4326 XXH3_initCustomSecret_scalar(void* XXH_RESTRICT customSecret, xxh_u64 seed64)
4329 * We need a separate pointer for the hack below,
4330 * which requires a non-const pointer.
4331 * Any decent compiler will optimize this out otherwise.
4333 const xxh_u8* kSecretPtr = XXH3_kSecret;
4334 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 15) == 0);
4336 #if defined(__clang__) && defined(__aarch64__)
4339 * Clang generates a bunch of MOV/MOVK pairs for aarch64, and they are
4340 * placed sequentially, in order, at the top of the unrolled loop.
4342 * While MOVK is great for generating constants (2 cycles for a 64-bit
4343 * constant compared to 4 cycles for LDR), it fights for bandwidth with
4344 * the arithmetic instructions.
4354 * By forcing loads from memory (as the asm line causes Clang to assume
4355 * that XXH3_kSecretPtr has been changed), the pipelines are used more
4363 * See XXH3_NEON_LANES for details on the pipsline.
4365 * XXH3_64bits_withSeed, len == 256, Snapdragon 835
4366 * without hack: 2654.4 MB/s
4367 * with hack: 3202.9 MB/s
4369 XXH_COMPILER_GUARD(kSecretPtr);
4372 * Note: in debug mode, this overrides the asm optimization
4373 * and Clang will emit MOVK chains again.
4375 XXH_ASSERT(kSecretPtr == XXH3_kSecret);
4377 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / 16;
4379 for (i=0; i < nbRounds; i++) {
4381 * The asm hack causes Clang to assume that kSecretPtr aliases with
4382 * customSecret, and on aarch64, this prevented LDP from merging two
4383 * loads together for free. Putting the loads together before the stores
4384 * properly generates LDP.
4386 xxh_u64 lo = XXH_readLE64(kSecretPtr + 16*i) + seed64;
4387 xxh_u64 hi = XXH_readLE64(kSecretPtr + 16*i + 8) - seed64;
4388 XXH_writeLE64((xxh_u8*)customSecret + 16*i, lo);
4389 XXH_writeLE64((xxh_u8*)customSecret + 16*i + 8, hi);
4394 typedef void (*XXH3_f_accumulate_512)(void* XXH_RESTRICT, const void*, const void*);
4395 typedef void (*XXH3_f_scrambleAcc)(void* XXH_RESTRICT, const void*);
4396 typedef void (*XXH3_f_initCustomSecret)(void* XXH_RESTRICT, xxh_u64);
4399 #if (XXH_VECTOR == XXH_AVX512)
4401 #define XXH3_accumulate_512 XXH3_accumulate_512_avx512
4402 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx512
4403 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx512
4405 #elif (XXH_VECTOR == XXH_AVX2)
4407 #define XXH3_accumulate_512 XXH3_accumulate_512_avx2
4408 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx2
4409 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx2
4411 #elif (XXH_VECTOR == XXH_SSE2)
4413 #define XXH3_accumulate_512 XXH3_accumulate_512_sse2
4414 #define XXH3_scrambleAcc XXH3_scrambleAcc_sse2
4415 #define XXH3_initCustomSecret XXH3_initCustomSecret_sse2
4417 #elif (XXH_VECTOR == XXH_NEON)
4419 #define XXH3_accumulate_512 XXH3_accumulate_512_neon
4420 #define XXH3_scrambleAcc XXH3_scrambleAcc_neon
4421 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4423 #elif (XXH_VECTOR == XXH_VSX)
4425 #define XXH3_accumulate_512 XXH3_accumulate_512_vsx
4426 #define XXH3_scrambleAcc XXH3_scrambleAcc_vsx
4427 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4431 #define XXH3_accumulate_512 XXH3_accumulate_512_scalar
4432 #define XXH3_scrambleAcc XXH3_scrambleAcc_scalar
4433 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4439 #ifndef XXH_PREFETCH_DIST
4441 # define XXH_PREFETCH_DIST 320
4443 # if (XXH_VECTOR == XXH_AVX512)
4444 # define XXH_PREFETCH_DIST 512
4446 # define XXH_PREFETCH_DIST 384
4448 # endif /* __clang__ */
4449 #endif /* XXH_PREFETCH_DIST */
4453 * Loops over XXH3_accumulate_512().
4454 * Assumption: nbStripes will not overflow the secret size
4456 XXH_FORCE_INLINE void
4457 XXH3_accumulate( xxh_u64* XXH_RESTRICT acc,
4458 const xxh_u8* XXH_RESTRICT input,
4459 const xxh_u8* XXH_RESTRICT secret,
4461 XXH3_f_accumulate_512 f_acc512)
4464 for (n = 0; n < nbStripes; n++ ) {
4465 const xxh_u8* const in = input + n*XXH_STRIPE_LEN;
4466 XXH_PREFETCH(in + XXH_PREFETCH_DIST);
4469 secret + n*XXH_SECRET_CONSUME_RATE);
4473 XXH_FORCE_INLINE void
4474 XXH3_hashLong_internal_loop(xxh_u64* XXH_RESTRICT acc,
4475 const xxh_u8* XXH_RESTRICT input, size_t len,
4476 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
4477 XXH3_f_accumulate_512 f_acc512,
4478 XXH3_f_scrambleAcc f_scramble)
4480 size_t const nbStripesPerBlock = (secretSize - XXH_STRIPE_LEN) / XXH_SECRET_CONSUME_RATE;
4481 size_t const block_len = XXH_STRIPE_LEN * nbStripesPerBlock;
4482 size_t const nb_blocks = (len - 1) / block_len;
4486 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN);
4488 for (n = 0; n < nb_blocks; n++) {
4489 XXH3_accumulate(acc, input + n*block_len, secret, nbStripesPerBlock, f_acc512);
4490 f_scramble(acc, secret + secretSize - XXH_STRIPE_LEN);
4493 /* last partial block */
4494 XXH_ASSERT(len > XXH_STRIPE_LEN);
4495 { size_t const nbStripes = ((len - 1) - (block_len * nb_blocks)) / XXH_STRIPE_LEN;
4496 XXH_ASSERT(nbStripes <= (secretSize / XXH_SECRET_CONSUME_RATE));
4497 XXH3_accumulate(acc, input + nb_blocks*block_len, secret, nbStripes, f_acc512);
4500 { const xxh_u8* const p = input + len - XXH_STRIPE_LEN;
4501 #define XXH_SECRET_LASTACC_START 7 /* not aligned on 8, last secret is different from acc & scrambler */
4502 f_acc512(acc, p, secret + secretSize - XXH_STRIPE_LEN - XXH_SECRET_LASTACC_START);
4506 XXH_FORCE_INLINE xxh_u64
4507 XXH3_mix2Accs(const xxh_u64* XXH_RESTRICT acc, const xxh_u8* XXH_RESTRICT secret)
4509 return XXH3_mul128_fold64(
4510 acc[0] ^ XXH_readLE64(secret),
4511 acc[1] ^ XXH_readLE64(secret+8) );
4515 XXH3_mergeAccs(const xxh_u64* XXH_RESTRICT acc, const xxh_u8* XXH_RESTRICT secret, xxh_u64 start)
4517 xxh_u64 result64 = start;
4520 for (i = 0; i < 4; i++) {
4521 result64 += XXH3_mix2Accs(acc+2*i, secret + 16*i);
4522 #if defined(__clang__) /* Clang */ \
4523 && (defined(__arm__) || defined(__thumb__)) /* ARMv7 */ \
4524 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \
4525 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */
4528 * Prevent autovectorization on Clang ARMv7-a. Exact same problem as
4529 * the one in XXH3_len_129to240_64b. Speeds up shorter keys > 240b.
4530 * XXH3_64bits, len == 256, Snapdragon 835:
4531 * without hack: 2063.7 MB/s
4532 * with hack: 2560.7 MB/s
4534 XXH_COMPILER_GUARD(result64);
4538 return XXH3_avalanche(result64);
4541 #define XXH3_INIT_ACC { XXH_PRIME32_3, XXH_PRIME64_1, XXH_PRIME64_2, XXH_PRIME64_3, \
4542 XXH_PRIME64_4, XXH_PRIME32_2, XXH_PRIME64_5, XXH_PRIME32_1 }
4544 XXH_FORCE_INLINE XXH64_hash_t
4545 XXH3_hashLong_64b_internal(const void* XXH_RESTRICT input, size_t len,
4546 const void* XXH_RESTRICT secret, size_t secretSize,
4547 XXH3_f_accumulate_512 f_acc512,
4548 XXH3_f_scrambleAcc f_scramble)
4550 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64 acc[XXH_ACC_NB] = XXH3_INIT_ACC;
4552 XXH3_hashLong_internal_loop(acc, (const xxh_u8*)input, len, (const xxh_u8*)secret, secretSize, f_acc512, f_scramble);
4554 /* converge into final hash */
4555 XXH_STATIC_ASSERT(sizeof(acc) == 64);
4556 /* do not align on 8, so that the secret is different from the accumulator */
4557 #define XXH_SECRET_MERGEACCS_START 11
4558 XXH_ASSERT(secretSize >= sizeof(acc) + XXH_SECRET_MERGEACCS_START);
4559 return XXH3_mergeAccs(acc, (const xxh_u8*)secret + XXH_SECRET_MERGEACCS_START, (xxh_u64)len * XXH_PRIME64_1);
4563 * It's important for performance to transmit secret's size (when it's static)
4564 * so that the compiler can properly optimize the vectorized loop.
4565 * This makes a big performance difference for "medium" keys (<1 KB) when using AVX instruction set.
4567 XXH_FORCE_INLINE XXH64_hash_t
4568 XXH3_hashLong_64b_withSecret(const void* XXH_RESTRICT input, size_t len,
4569 XXH64_hash_t seed64, const xxh_u8* XXH_RESTRICT secret, size_t secretLen)
4572 return XXH3_hashLong_64b_internal(input, len, secret, secretLen, XXH3_accumulate_512, XXH3_scrambleAcc);
4576 * It's preferable for performance that XXH3_hashLong is not inlined,
4577 * as it results in a smaller function for small data, easier to the instruction cache.
4578 * Note that inside this no_inline function, we do inline the internal loop,
4579 * and provide a statically defined secret size to allow optimization of vector loop.
4581 XXH_NO_INLINE XXH64_hash_t
4582 XXH3_hashLong_64b_default(const void* XXH_RESTRICT input, size_t len,
4583 XXH64_hash_t seed64, const xxh_u8* XXH_RESTRICT secret, size_t secretLen)
4585 (void)seed64; (void)secret; (void)secretLen;
4586 return XXH3_hashLong_64b_internal(input, len, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_accumulate_512, XXH3_scrambleAcc);
4590 * XXH3_hashLong_64b_withSeed():
4591 * Generate a custom key based on alteration of default XXH3_kSecret with the seed,
4592 * and then use this key for long mode hashing.
4594 * This operation is decently fast but nonetheless costs a little bit of time.
4595 * Try to avoid it whenever possible (typically when seed==0).
4597 * It's important for performance that XXH3_hashLong is not inlined. Not sure
4598 * why (uop cache maybe?), but the difference is large and easily measurable.
4600 XXH_FORCE_INLINE XXH64_hash_t
4601 XXH3_hashLong_64b_withSeed_internal(const void* input, size_t len,
4603 XXH3_f_accumulate_512 f_acc512,
4604 XXH3_f_scrambleAcc f_scramble,
4605 XXH3_f_initCustomSecret f_initSec)
4608 return XXH3_hashLong_64b_internal(input, len,
4609 XXH3_kSecret, sizeof(XXH3_kSecret),
4610 f_acc512, f_scramble);
4611 { XXH_ALIGN(XXH_SEC_ALIGN) xxh_u8 secret[XXH_SECRET_DEFAULT_SIZE];
4612 f_initSec(secret, seed);
4613 return XXH3_hashLong_64b_internal(input, len, secret, sizeof(secret),
4614 f_acc512, f_scramble);
4619 * It's important for performance that XXH3_hashLong is not inlined.
4621 XXH_NO_INLINE XXH64_hash_t
4622 XXH3_hashLong_64b_withSeed(const void* input, size_t len,
4623 XXH64_hash_t seed, const xxh_u8* secret, size_t secretLen)
4625 (void)secret; (void)secretLen;
4626 return XXH3_hashLong_64b_withSeed_internal(input, len, seed,
4627 XXH3_accumulate_512, XXH3_scrambleAcc, XXH3_initCustomSecret);
4631 typedef XXH64_hash_t (*XXH3_hashLong64_f)(const void* XXH_RESTRICT, size_t,
4632 XXH64_hash_t, const xxh_u8* XXH_RESTRICT, size_t);
4634 XXH_FORCE_INLINE XXH64_hash_t
4635 XXH3_64bits_internal(const void* XXH_RESTRICT input, size_t len,
4636 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen,
4637 XXH3_hashLong64_f f_hashLong)
4639 XXH_ASSERT(secretLen >= XXH3_SECRET_SIZE_MIN);
4641 * If an action is to be taken if `secretLen` condition is not respected,
4642 * it should be done here.
4643 * For now, it's a contract pre-condition.
4644 * Adding a check and a branch here would cost performance at every hash.
4645 * Also, note that function signature doesn't offer room to return an error.
4648 return XXH3_len_0to16_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, seed64);
4650 return XXH3_len_17to128_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64);
4651 if (len <= XXH3_MIDSIZE_MAX)
4652 return XXH3_len_129to240_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64);
4653 return f_hashLong(input, len, seed64, (const xxh_u8*)secret, secretLen);
4657 /* === Public entry point === */
4659 /*! @ingroup xxh3_family */
4660 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits(const void* input, size_t len)
4662 return XXH3_64bits_internal(input, len, 0, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_hashLong_64b_default);
4665 /*! @ingroup xxh3_family */
4666 XXH_PUBLIC_API XXH64_hash_t
4667 XXH3_64bits_withSecret(const void* input, size_t len, const void* secret, size_t secretSize)
4669 return XXH3_64bits_internal(input, len, 0, secret, secretSize, XXH3_hashLong_64b_withSecret);
4672 /*! @ingroup xxh3_family */
4673 XXH_PUBLIC_API XXH64_hash_t
4674 XXH3_64bits_withSeed(const void* input, size_t len, XXH64_hash_t seed)
4676 return XXH3_64bits_internal(input, len, seed, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_hashLong_64b_withSeed);
4679 XXH_PUBLIC_API XXH64_hash_t
4680 XXH3_64bits_withSecretandSeed(const void* input, size_t len, const void* secret, size_t secretSize, XXH64_hash_t seed)
4682 if (len <= XXH3_MIDSIZE_MAX)
4683 return XXH3_64bits_internal(input, len, seed, XXH3_kSecret, sizeof(XXH3_kSecret), NULL);
4684 return XXH3_hashLong_64b_withSecret(input, len, seed, (const xxh_u8*)secret, secretSize);
4688 /* === XXH3 streaming === */
4691 * Malloc's a pointer that is always aligned to align.
4693 * This must be freed with `XXH_alignedFree()`.
4695 * malloc typically guarantees 16 byte alignment on 64-bit systems and 8 byte
4696 * alignment on 32-bit. This isn't enough for the 32 byte aligned loads in AVX2
4697 * or on 32-bit, the 16 byte aligned loads in SSE2 and NEON.
4699 * This underalignment previously caused a rather obvious crash which went
4700 * completely unnoticed due to XXH3_createState() not actually being tested.
4701 * Credit to RedSpah for noticing this bug.
4703 * The alignment is done manually: Functions like posix_memalign or _mm_malloc
4704 * are avoided: To maintain portability, we would have to write a fallback
4705 * like this anyways, and besides, testing for the existence of library
4706 * functions without relying on external build tools is impossible.
4708 * The method is simple: Overallocate, manually align, and store the offset
4709 * to the original behind the returned pointer.
4711 * Align must be a power of 2 and 8 <= align <= 128.
4713 static void* XXH_alignedMalloc(size_t s, size_t align)
4715 XXH_ASSERT(align <= 128 && align >= 8); /* range check */
4716 XXH_ASSERT((align & (align-1)) == 0); /* power of 2 */
4717 XXH_ASSERT(s != 0 && s < (s + align)); /* empty/overflow */
4718 { /* Overallocate to make room for manual realignment and an offset byte */
4719 xxh_u8* base = (xxh_u8*)XXH_malloc(s + align);
4722 * Get the offset needed to align this pointer.
4724 * Even if the returned pointer is aligned, there will always be
4725 * at least one byte to store the offset to the original pointer.
4727 size_t offset = align - ((size_t)base & (align - 1)); /* base % align */
4728 /* Add the offset for the now-aligned pointer */
4729 xxh_u8* ptr = base + offset;
4731 XXH_ASSERT((size_t)ptr % align == 0);
4733 /* Store the offset immediately before the returned pointer. */
4734 ptr[-1] = (xxh_u8)offset;
4741 * Frees an aligned pointer allocated by XXH_alignedMalloc(). Don't pass
4742 * normal malloc'd pointers, XXH_alignedMalloc has a specific data layout.
4744 static void XXH_alignedFree(void* p)
4747 xxh_u8* ptr = (xxh_u8*)p;
4748 /* Get the offset byte we added in XXH_malloc. */
4749 xxh_u8 offset = ptr[-1];
4750 /* Free the original malloc'd pointer */
4751 xxh_u8* base = ptr - offset;
4755 /*! @ingroup xxh3_family */
4756 XXH_PUBLIC_API XXH3_state_t* XXH3_createState(void)
4758 XXH3_state_t* const state = (XXH3_state_t*)XXH_alignedMalloc(sizeof(XXH3_state_t), 64);
4759 if (state==NULL) return NULL;
4760 XXH3_INITSTATE(state);
4764 /*! @ingroup xxh3_family */
4765 XXH_PUBLIC_API XXH_errorcode XXH3_freeState(XXH3_state_t* statePtr)
4767 XXH_alignedFree(statePtr);
4771 /*! @ingroup xxh3_family */
4773 XXH3_copyState(XXH3_state_t* dst_state, const XXH3_state_t* src_state)
4775 XXH_memcpy(dst_state, src_state, sizeof(*dst_state));
4779 XXH3_reset_internal(XXH3_state_t* statePtr,
4781 const void* secret, size_t secretSize)
4783 size_t const initStart = offsetof(XXH3_state_t, bufferedSize);
4784 size_t const initLength = offsetof(XXH3_state_t, nbStripesPerBlock) - initStart;
4785 XXH_ASSERT(offsetof(XXH3_state_t, nbStripesPerBlock) > initStart);
4786 XXH_ASSERT(statePtr != NULL);
4787 /* set members from bufferedSize to nbStripesPerBlock (excluded) to 0 */
4788 memset((char*)statePtr + initStart, 0, initLength);
4789 statePtr->acc[0] = XXH_PRIME32_3;
4790 statePtr->acc[1] = XXH_PRIME64_1;
4791 statePtr->acc[2] = XXH_PRIME64_2;
4792 statePtr->acc[3] = XXH_PRIME64_3;
4793 statePtr->acc[4] = XXH_PRIME64_4;
4794 statePtr->acc[5] = XXH_PRIME32_2;
4795 statePtr->acc[6] = XXH_PRIME64_5;
4796 statePtr->acc[7] = XXH_PRIME32_1;
4797 statePtr->seed = seed;
4798 statePtr->useSeed = (seed != 0);
4799 statePtr->extSecret = (const unsigned char*)secret;
4800 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN);
4801 statePtr->secretLimit = secretSize - XXH_STRIPE_LEN;
4802 statePtr->nbStripesPerBlock = statePtr->secretLimit / XXH_SECRET_CONSUME_RATE;
4805 /*! @ingroup xxh3_family */
4806 XXH_PUBLIC_API XXH_errorcode
4807 XXH3_64bits_reset(XXH3_state_t* statePtr)
4809 if (statePtr == NULL) return XXH_ERROR;
4810 XXH3_reset_internal(statePtr, 0, XXH3_kSecret, XXH_SECRET_DEFAULT_SIZE);
4814 /*! @ingroup xxh3_family */
4815 XXH_PUBLIC_API XXH_errorcode
4816 XXH3_64bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize)
4818 if (statePtr == NULL) return XXH_ERROR;
4819 XXH3_reset_internal(statePtr, 0, secret, secretSize);
4820 if (secret == NULL) return XXH_ERROR;
4821 if (secretSize < XXH3_SECRET_SIZE_MIN) return XXH_ERROR;
4825 /*! @ingroup xxh3_family */
4826 XXH_PUBLIC_API XXH_errorcode
4827 XXH3_64bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed)
4829 if (statePtr == NULL) return XXH_ERROR;
4830 if (seed==0) return XXH3_64bits_reset(statePtr);
4831 if ((seed != statePtr->seed) || (statePtr->extSecret != NULL))
4832 XXH3_initCustomSecret(statePtr->customSecret, seed);
4833 XXH3_reset_internal(statePtr, seed, NULL, XXH_SECRET_DEFAULT_SIZE);
4837 /*! @ingroup xxh3_family */
4838 XXH_PUBLIC_API XXH_errorcode
4839 XXH3_64bits_reset_withSecretandSeed(XXH3_state_t* statePtr, const void* secret, size_t secretSize, XXH64_hash_t seed64)
4841 if (statePtr == NULL) return XXH_ERROR;
4842 if (secret == NULL) return XXH_ERROR;
4843 if (secretSize < XXH3_SECRET_SIZE_MIN) return XXH_ERROR;
4844 XXH3_reset_internal(statePtr, seed64, secret, secretSize);
4845 statePtr->useSeed = 1; /* always, even if seed64==0 */
4849 /* Note : when XXH3_consumeStripes() is invoked,
4850 * there must be a guarantee that at least one more byte must be consumed from input
4851 * so that the function can blindly consume all stripes using the "normal" secret segment */
4852 XXH_FORCE_INLINE void
4853 XXH3_consumeStripes(xxh_u64* XXH_RESTRICT acc,
4854 size_t* XXH_RESTRICT nbStripesSoFarPtr, size_t nbStripesPerBlock,
4855 const xxh_u8* XXH_RESTRICT input, size_t nbStripes,
4856 const xxh_u8* XXH_RESTRICT secret, size_t secretLimit,
4857 XXH3_f_accumulate_512 f_acc512,
4858 XXH3_f_scrambleAcc f_scramble)
4860 XXH_ASSERT(nbStripes <= nbStripesPerBlock); /* can handle max 1 scramble per invocation */
4861 XXH_ASSERT(*nbStripesSoFarPtr < nbStripesPerBlock);
4862 if (nbStripesPerBlock - *nbStripesSoFarPtr <= nbStripes) {
4863 /* need a scrambling operation */
4864 size_t const nbStripesToEndofBlock = nbStripesPerBlock - *nbStripesSoFarPtr;
4865 size_t const nbStripesAfterBlock = nbStripes - nbStripesToEndofBlock;
4866 XXH3_accumulate(acc, input, secret + nbStripesSoFarPtr[0] * XXH_SECRET_CONSUME_RATE, nbStripesToEndofBlock, f_acc512);
4867 f_scramble(acc, secret + secretLimit);
4868 XXH3_accumulate(acc, input + nbStripesToEndofBlock * XXH_STRIPE_LEN, secret, nbStripesAfterBlock, f_acc512);
4869 *nbStripesSoFarPtr = nbStripesAfterBlock;
4871 XXH3_accumulate(acc, input, secret + nbStripesSoFarPtr[0] * XXH_SECRET_CONSUME_RATE, nbStripes, f_acc512);
4872 *nbStripesSoFarPtr += nbStripes;
4876 #ifndef XXH3_STREAM_USE_STACK
4877 # ifndef __clang__ /* clang doesn't need additional stack space */
4878 # define XXH3_STREAM_USE_STACK 1
4882 * Both XXH3_64bits_update and XXH3_128bits_update use this routine.
4884 XXH_FORCE_INLINE XXH_errorcode
4885 XXH3_update(XXH3_state_t* XXH_RESTRICT const state,
4886 const xxh_u8* XXH_RESTRICT input, size_t len,
4887 XXH3_f_accumulate_512 f_acc512,
4888 XXH3_f_scrambleAcc f_scramble)
4891 XXH_ASSERT(len == 0);
4895 XXH_ASSERT(state != NULL);
4896 { const xxh_u8* const bEnd = input + len;
4897 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret;
4898 #if defined(XXH3_STREAM_USE_STACK) && XXH3_STREAM_USE_STACK >= 1
4899 /* For some reason, gcc and MSVC seem to suffer greatly
4900 * when operating accumulators directly into state.
4901 * Operating into stack space seems to enable proper optimization.
4902 * clang, on the other hand, doesn't seem to need this trick */
4903 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64 acc[8]; memcpy(acc, state->acc, sizeof(acc));
4905 xxh_u64* XXH_RESTRICT const acc = state->acc;
4907 state->totalLen += len;
4908 XXH_ASSERT(state->bufferedSize <= XXH3_INTERNALBUFFER_SIZE);
4910 /* small input : just fill in tmp buffer */
4911 if (state->bufferedSize + len <= XXH3_INTERNALBUFFER_SIZE) {
4912 XXH_memcpy(state->buffer + state->bufferedSize, input, len);
4913 state->bufferedSize += (XXH32_hash_t)len;
4917 /* total input is now > XXH3_INTERNALBUFFER_SIZE */
4918 #define XXH3_INTERNALBUFFER_STRIPES (XXH3_INTERNALBUFFER_SIZE / XXH_STRIPE_LEN)
4919 XXH_STATIC_ASSERT(XXH3_INTERNALBUFFER_SIZE % XXH_STRIPE_LEN == 0); /* clean multiple */
4922 * Internal buffer is partially filled (always, except at beginning)
4923 * Complete it, then consume it.
4925 if (state->bufferedSize) {
4926 size_t const loadSize = XXH3_INTERNALBUFFER_SIZE - state->bufferedSize;
4927 XXH_memcpy(state->buffer + state->bufferedSize, input, loadSize);
4929 XXH3_consumeStripes(acc,
4930 &state->nbStripesSoFar, state->nbStripesPerBlock,
4931 state->buffer, XXH3_INTERNALBUFFER_STRIPES,
4932 secret, state->secretLimit,
4933 f_acc512, f_scramble);
4934 state->bufferedSize = 0;
4936 XXH_ASSERT(input < bEnd);
4938 /* large input to consume : ingest per full block */
4939 if ((size_t)(bEnd - input) > state->nbStripesPerBlock * XXH_STRIPE_LEN) {
4940 size_t nbStripes = (size_t)(bEnd - 1 - input) / XXH_STRIPE_LEN;
4941 XXH_ASSERT(state->nbStripesPerBlock >= state->nbStripesSoFar);
4942 /* join to current block's end */
4943 { size_t const nbStripesToEnd = state->nbStripesPerBlock - state->nbStripesSoFar;
4944 XXH_ASSERT(nbStripesToEnd <= nbStripes);
4945 XXH3_accumulate(acc, input, secret + state->nbStripesSoFar * XXH_SECRET_CONSUME_RATE, nbStripesToEnd, f_acc512);
4946 f_scramble(acc, secret + state->secretLimit);
4947 state->nbStripesSoFar = 0;
4948 input += nbStripesToEnd * XXH_STRIPE_LEN;
4949 nbStripes -= nbStripesToEnd;
4951 /* consume per entire blocks */
4952 while(nbStripes >= state->nbStripesPerBlock) {
4953 XXH3_accumulate(acc, input, secret, state->nbStripesPerBlock, f_acc512);
4954 f_scramble(acc, secret + state->secretLimit);
4955 input += state->nbStripesPerBlock * XXH_STRIPE_LEN;
4956 nbStripes -= state->nbStripesPerBlock;
4958 /* consume last partial block */
4959 XXH3_accumulate(acc, input, secret, nbStripes, f_acc512);
4960 input += nbStripes * XXH_STRIPE_LEN;
4961 XXH_ASSERT(input < bEnd); /* at least some bytes left */
4962 state->nbStripesSoFar = nbStripes;
4963 /* buffer predecessor of last partial stripe */
4964 XXH_memcpy(state->buffer + sizeof(state->buffer) - XXH_STRIPE_LEN, input - XXH_STRIPE_LEN, XXH_STRIPE_LEN);
4965 XXH_ASSERT(bEnd - input <= XXH_STRIPE_LEN);
4967 /* content to consume <= block size */
4968 /* Consume input by a multiple of internal buffer size */
4969 if (bEnd - input > XXH3_INTERNALBUFFER_SIZE) {
4970 const xxh_u8* const limit = bEnd - XXH3_INTERNALBUFFER_SIZE;
4972 XXH3_consumeStripes(acc,
4973 &state->nbStripesSoFar, state->nbStripesPerBlock,
4974 input, XXH3_INTERNALBUFFER_STRIPES,
4975 secret, state->secretLimit,
4976 f_acc512, f_scramble);
4977 input += XXH3_INTERNALBUFFER_SIZE;
4978 } while (input<limit);
4979 /* buffer predecessor of last partial stripe */
4980 XXH_memcpy(state->buffer + sizeof(state->buffer) - XXH_STRIPE_LEN, input - XXH_STRIPE_LEN, XXH_STRIPE_LEN);
4984 /* Some remaining input (always) : buffer it */
4985 XXH_ASSERT(input < bEnd);
4986 XXH_ASSERT(bEnd - input <= XXH3_INTERNALBUFFER_SIZE);
4987 XXH_ASSERT(state->bufferedSize == 0);
4988 XXH_memcpy(state->buffer, input, (size_t)(bEnd-input));
4989 state->bufferedSize = (XXH32_hash_t)(bEnd-input);
4990 #if defined(XXH3_STREAM_USE_STACK) && XXH3_STREAM_USE_STACK >= 1
4991 /* save stack accumulators into state */
4992 memcpy(state->acc, acc, sizeof(acc));
4999 /*! @ingroup xxh3_family */
5000 XXH_PUBLIC_API XXH_errorcode
5001 XXH3_64bits_update(XXH3_state_t* state, const void* input, size_t len)
5003 return XXH3_update(state, (const xxh_u8*)input, len,
5004 XXH3_accumulate_512, XXH3_scrambleAcc);
5008 XXH_FORCE_INLINE void
5009 XXH3_digest_long (XXH64_hash_t* acc,
5010 const XXH3_state_t* state,
5011 const unsigned char* secret)
5014 * Digest on a local copy. This way, the state remains unaltered, and it can
5015 * continue ingesting more input afterwards.
5017 XXH_memcpy(acc, state->acc, sizeof(state->acc));
5018 if (state->bufferedSize >= XXH_STRIPE_LEN) {
5019 size_t const nbStripes = (state->bufferedSize - 1) / XXH_STRIPE_LEN;
5020 size_t nbStripesSoFar = state->nbStripesSoFar;
5021 XXH3_consumeStripes(acc,
5022 &nbStripesSoFar, state->nbStripesPerBlock,
5023 state->buffer, nbStripes,
5024 secret, state->secretLimit,
5025 XXH3_accumulate_512, XXH3_scrambleAcc);
5027 XXH3_accumulate_512(acc,
5028 state->buffer + state->bufferedSize - XXH_STRIPE_LEN,
5029 secret + state->secretLimit - XXH_SECRET_LASTACC_START);
5030 } else { /* bufferedSize < XXH_STRIPE_LEN */
5031 xxh_u8 lastStripe[XXH_STRIPE_LEN];
5032 size_t const catchupSize = XXH_STRIPE_LEN - state->bufferedSize;
5033 XXH_ASSERT(state->bufferedSize > 0); /* there is always some input buffered */
5034 XXH_memcpy(lastStripe, state->buffer + sizeof(state->buffer) - catchupSize, catchupSize);
5035 XXH_memcpy(lastStripe + catchupSize, state->buffer, state->bufferedSize);
5036 XXH3_accumulate_512(acc,
5038 secret + state->secretLimit - XXH_SECRET_LASTACC_START);
5042 /*! @ingroup xxh3_family */
5043 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_digest (const XXH3_state_t* state)
5045 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret;
5046 if (state->totalLen > XXH3_MIDSIZE_MAX) {
5047 XXH_ALIGN(XXH_ACC_ALIGN) XXH64_hash_t acc[XXH_ACC_NB];
5048 XXH3_digest_long(acc, state, secret);
5049 return XXH3_mergeAccs(acc,
5050 secret + XXH_SECRET_MERGEACCS_START,
5051 (xxh_u64)state->totalLen * XXH_PRIME64_1);
5053 /* totalLen <= XXH3_MIDSIZE_MAX: digesting a short input */
5055 return XXH3_64bits_withSeed(state->buffer, (size_t)state->totalLen, state->seed);
5056 return XXH3_64bits_withSecret(state->buffer, (size_t)(state->totalLen),
5057 secret, state->secretLimit + XXH_STRIPE_LEN);
5062 /* ==========================================
5063 * XXH3 128 bits (a.k.a XXH128)
5064 * ==========================================
5065 * XXH3's 128-bit variant has better mixing and strength than the 64-bit variant,
5066 * even without counting the significantly larger output size.
5068 * For example, extra steps are taken to avoid the seed-dependent collisions
5069 * in 17-240 byte inputs (See XXH3_mix16B and XXH128_mix32B).
5071 * This strength naturally comes at the cost of some speed, especially on short
5072 * lengths. Note that longer hashes are about as fast as the 64-bit version
5073 * due to it using only a slight modification of the 64-bit loop.
5075 * XXH128 is also more oriented towards 64-bit machines. It is still extremely
5076 * fast for a _128-bit_ hash on 32-bit (it usually clears XXH64).
5079 XXH_FORCE_INLINE XXH128_hash_t
5080 XXH3_len_1to3_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
5082 /* A doubled version of 1to3_64b with different constants. */
5083 XXH_ASSERT(input != NULL);
5084 XXH_ASSERT(1 <= len && len <= 3);
5085 XXH_ASSERT(secret != NULL);
5087 * len = 1: combinedl = { input[0], 0x01, input[0], input[0] }
5088 * len = 2: combinedl = { input[1], 0x02, input[0], input[1] }
5089 * len = 3: combinedl = { input[2], 0x03, input[0], input[1] }
5091 { xxh_u8 const c1 = input[0];
5092 xxh_u8 const c2 = input[len >> 1];
5093 xxh_u8 const c3 = input[len - 1];
5094 xxh_u32 const combinedl = ((xxh_u32)c1 <<16) | ((xxh_u32)c2 << 24)
5095 | ((xxh_u32)c3 << 0) | ((xxh_u32)len << 8);
5096 xxh_u32 const combinedh = XXH_rotl32(XXH_swap32(combinedl), 13);
5097 xxh_u64 const bitflipl = (XXH_readLE32(secret) ^ XXH_readLE32(secret+4)) + seed;
5098 xxh_u64 const bitfliph = (XXH_readLE32(secret+8) ^ XXH_readLE32(secret+12)) - seed;
5099 xxh_u64 const keyed_lo = (xxh_u64)combinedl ^ bitflipl;
5100 xxh_u64 const keyed_hi = (xxh_u64)combinedh ^ bitfliph;
5102 h128.low64 = XXH64_avalanche(keyed_lo);
5103 h128.high64 = XXH64_avalanche(keyed_hi);
5108 XXH_FORCE_INLINE XXH128_hash_t
5109 XXH3_len_4to8_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
5111 XXH_ASSERT(input != NULL);
5112 XXH_ASSERT(secret != NULL);
5113 XXH_ASSERT(4 <= len && len <= 8);
5114 seed ^= (xxh_u64)XXH_swap32((xxh_u32)seed) << 32;
5115 { xxh_u32 const input_lo = XXH_readLE32(input);
5116 xxh_u32 const input_hi = XXH_readLE32(input + len - 4);
5117 xxh_u64 const input_64 = input_lo + ((xxh_u64)input_hi << 32);
5118 xxh_u64 const bitflip = (XXH_readLE64(secret+16) ^ XXH_readLE64(secret+24)) + seed;
5119 xxh_u64 const keyed = input_64 ^ bitflip;
5121 /* Shift len to the left to ensure it is even, this avoids even multiplies. */
5122 XXH128_hash_t m128 = XXH_mult64to128(keyed, XXH_PRIME64_1 + (len << 2));
5124 m128.high64 += (m128.low64 << 1);
5125 m128.low64 ^= (m128.high64 >> 3);
5127 m128.low64 = XXH_xorshift64(m128.low64, 35);
5128 m128.low64 *= 0x9FB21C651E98DF25ULL;
5129 m128.low64 = XXH_xorshift64(m128.low64, 28);
5130 m128.high64 = XXH3_avalanche(m128.high64);
5135 XXH_FORCE_INLINE XXH128_hash_t
5136 XXH3_len_9to16_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
5138 XXH_ASSERT(input != NULL);
5139 XXH_ASSERT(secret != NULL);
5140 XXH_ASSERT(9 <= len && len <= 16);
5141 { xxh_u64 const bitflipl = (XXH_readLE64(secret+32) ^ XXH_readLE64(secret+40)) - seed;
5142 xxh_u64 const bitfliph = (XXH_readLE64(secret+48) ^ XXH_readLE64(secret+56)) + seed;
5143 xxh_u64 const input_lo = XXH_readLE64(input);
5144 xxh_u64 input_hi = XXH_readLE64(input + len - 8);
5145 XXH128_hash_t m128 = XXH_mult64to128(input_lo ^ input_hi ^ bitflipl, XXH_PRIME64_1);
5147 * Put len in the middle of m128 to ensure that the length gets mixed to
5148 * both the low and high bits in the 128x64 multiply below.
5150 m128.low64 += (xxh_u64)(len - 1) << 54;
5151 input_hi ^= bitfliph;
5153 * Add the high 32 bits of input_hi to the high 32 bits of m128, then
5154 * add the long product of the low 32 bits of input_hi and XXH_PRIME32_2 to
5155 * the high 64 bits of m128.
5157 * The best approach to this operation is different on 32-bit and 64-bit.
5159 if (sizeof(void *) < sizeof(xxh_u64)) { /* 32-bit */
5161 * 32-bit optimized version, which is more readable.
5163 * On 32-bit, it removes an ADC and delays a dependency between the two
5164 * halves of m128.high64, but it generates an extra mask on 64-bit.
5166 m128.high64 += (input_hi & 0xFFFFFFFF00000000ULL) + XXH_mult32to64((xxh_u32)input_hi, XXH_PRIME32_2);
5169 * 64-bit optimized (albeit more confusing) version.
5171 * Uses some properties of addition and multiplication to remove the mask:
5174 * a = input_hi.lo = (input_hi & 0x00000000FFFFFFFF)
5175 * b = input_hi.hi = (input_hi & 0xFFFFFFFF00000000)
5179 * Inverse Property: x + y - x == y
5180 * a + (b * (1 + c - 1))
5181 * Distributive Property: x * (y + z) == (x * y) + (x * z)
5182 * a + (b * 1) + (b * (c - 1))
5183 * Identity Property: x * 1 == x
5184 * a + b + (b * (c - 1))
5186 * Substitute a, b, and c:
5187 * input_hi.hi + input_hi.lo + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1))
5189 * Since input_hi.hi + input_hi.lo == input_hi, we get this:
5190 * input_hi + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1))
5192 m128.high64 += input_hi + XXH_mult32to64((xxh_u32)input_hi, XXH_PRIME32_2 - 1);
5194 /* m128 ^= XXH_swap64(m128 >> 64); */
5195 m128.low64 ^= XXH_swap64(m128.high64);
5197 { /* 128x64 multiply: h128 = m128 * XXH_PRIME64_2; */
5198 XXH128_hash_t h128 = XXH_mult64to128(m128.low64, XXH_PRIME64_2);
5199 h128.high64 += m128.high64 * XXH_PRIME64_2;
5201 h128.low64 = XXH3_avalanche(h128.low64);
5202 h128.high64 = XXH3_avalanche(h128.high64);
5208 * Assumption: `secret` size is >= XXH3_SECRET_SIZE_MIN
5210 XXH_FORCE_INLINE XXH128_hash_t
5211 XXH3_len_0to16_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed)
5213 XXH_ASSERT(len <= 16);
5214 { if (len > 8) return XXH3_len_9to16_128b(input, len, secret, seed);
5215 if (len >= 4) return XXH3_len_4to8_128b(input, len, secret, seed);
5216 if (len) return XXH3_len_1to3_128b(input, len, secret, seed);
5217 { XXH128_hash_t h128;
5218 xxh_u64 const bitflipl = XXH_readLE64(secret+64) ^ XXH_readLE64(secret+72);
5219 xxh_u64 const bitfliph = XXH_readLE64(secret+80) ^ XXH_readLE64(secret+88);
5220 h128.low64 = XXH64_avalanche(seed ^ bitflipl);
5221 h128.high64 = XXH64_avalanche( seed ^ bitfliph);
5227 * A bit slower than XXH3_mix16B, but handles multiply by zero better.
5229 XXH_FORCE_INLINE XXH128_hash_t
5230 XXH128_mix32B(XXH128_hash_t acc, const xxh_u8* input_1, const xxh_u8* input_2,
5231 const xxh_u8* secret, XXH64_hash_t seed)
5233 acc.low64 += XXH3_mix16B (input_1, secret+0, seed);
5234 acc.low64 ^= XXH_readLE64(input_2) + XXH_readLE64(input_2 + 8);
5235 acc.high64 += XXH3_mix16B (input_2, secret+16, seed);
5236 acc.high64 ^= XXH_readLE64(input_1) + XXH_readLE64(input_1 + 8);
5241 XXH_FORCE_INLINE XXH128_hash_t
5242 XXH3_len_17to128_128b(const xxh_u8* XXH_RESTRICT input, size_t len,
5243 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
5246 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize;
5247 XXH_ASSERT(16 < len && len <= 128);
5249 { XXH128_hash_t acc;
5250 acc.low64 = len * XXH_PRIME64_1;
5255 acc = XXH128_mix32B(acc, input+48, input+len-64, secret+96, seed);
5257 acc = XXH128_mix32B(acc, input+32, input+len-48, secret+64, seed);
5259 acc = XXH128_mix32B(acc, input+16, input+len-32, secret+32, seed);
5261 acc = XXH128_mix32B(acc, input, input+len-16, secret, seed);
5262 { XXH128_hash_t h128;
5263 h128.low64 = acc.low64 + acc.high64;
5264 h128.high64 = (acc.low64 * XXH_PRIME64_1)
5265 + (acc.high64 * XXH_PRIME64_4)
5266 + ((len - seed) * XXH_PRIME64_2);
5267 h128.low64 = XXH3_avalanche(h128.low64);
5268 h128.high64 = (XXH64_hash_t)0 - XXH3_avalanche(h128.high64);
5274 XXH_NO_INLINE XXH128_hash_t
5275 XXH3_len_129to240_128b(const xxh_u8* XXH_RESTRICT input, size_t len,
5276 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
5279 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize;
5280 XXH_ASSERT(128 < len && len <= XXH3_MIDSIZE_MAX);
5282 { XXH128_hash_t acc;
5283 int const nbRounds = (int)len / 32;
5285 acc.low64 = len * XXH_PRIME64_1;
5287 for (i=0; i<4; i++) {
5288 acc = XXH128_mix32B(acc,
5290 input + (32 * i) + 16,
5294 acc.low64 = XXH3_avalanche(acc.low64);
5295 acc.high64 = XXH3_avalanche(acc.high64);
5296 XXH_ASSERT(nbRounds >= 4);
5297 for (i=4 ; i < nbRounds; i++) {
5298 acc = XXH128_mix32B(acc,
5300 input + (32 * i) + 16,
5301 secret + XXH3_MIDSIZE_STARTOFFSET + (32 * (i - 4)),
5305 acc = XXH128_mix32B(acc,
5308 secret + XXH3_SECRET_SIZE_MIN - XXH3_MIDSIZE_LASTOFFSET - 16,
5311 { XXH128_hash_t h128;
5312 h128.low64 = acc.low64 + acc.high64;
5313 h128.high64 = (acc.low64 * XXH_PRIME64_1)
5314 + (acc.high64 * XXH_PRIME64_4)
5315 + ((len - seed) * XXH_PRIME64_2);
5316 h128.low64 = XXH3_avalanche(h128.low64);
5317 h128.high64 = (XXH64_hash_t)0 - XXH3_avalanche(h128.high64);
5323 XXH_FORCE_INLINE XXH128_hash_t
5324 XXH3_hashLong_128b_internal(const void* XXH_RESTRICT input, size_t len,
5325 const xxh_u8* XXH_RESTRICT secret, size_t secretSize,
5326 XXH3_f_accumulate_512 f_acc512,
5327 XXH3_f_scrambleAcc f_scramble)
5329 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64 acc[XXH_ACC_NB] = XXH3_INIT_ACC;
5331 XXH3_hashLong_internal_loop(acc, (const xxh_u8*)input, len, secret, secretSize, f_acc512, f_scramble);
5333 /* converge into final hash */
5334 XXH_STATIC_ASSERT(sizeof(acc) == 64);
5335 XXH_ASSERT(secretSize >= sizeof(acc) + XXH_SECRET_MERGEACCS_START);
5336 { XXH128_hash_t h128;
5337 h128.low64 = XXH3_mergeAccs(acc,
5338 secret + XXH_SECRET_MERGEACCS_START,
5339 (xxh_u64)len * XXH_PRIME64_1);
5340 h128.high64 = XXH3_mergeAccs(acc,
5342 - sizeof(acc) - XXH_SECRET_MERGEACCS_START,
5343 ~((xxh_u64)len * XXH_PRIME64_2));
5349 * It's important for performance that XXH3_hashLong is not inlined.
5351 XXH_NO_INLINE XXH128_hash_t
5352 XXH3_hashLong_128b_default(const void* XXH_RESTRICT input, size_t len,
5353 XXH64_hash_t seed64,
5354 const void* XXH_RESTRICT secret, size_t secretLen)
5356 (void)seed64; (void)secret; (void)secretLen;
5357 return XXH3_hashLong_128b_internal(input, len, XXH3_kSecret, sizeof(XXH3_kSecret),
5358 XXH3_accumulate_512, XXH3_scrambleAcc);
5362 * It's important for performance to pass @secretLen (when it's static)
5363 * to the compiler, so that it can properly optimize the vectorized loop.
5365 XXH_FORCE_INLINE XXH128_hash_t
5366 XXH3_hashLong_128b_withSecret(const void* XXH_RESTRICT input, size_t len,
5367 XXH64_hash_t seed64,
5368 const void* XXH_RESTRICT secret, size_t secretLen)
5371 return XXH3_hashLong_128b_internal(input, len, (const xxh_u8*)secret, secretLen,
5372 XXH3_accumulate_512, XXH3_scrambleAcc);
5375 XXH_FORCE_INLINE XXH128_hash_t
5376 XXH3_hashLong_128b_withSeed_internal(const void* XXH_RESTRICT input, size_t len,
5377 XXH64_hash_t seed64,
5378 XXH3_f_accumulate_512 f_acc512,
5379 XXH3_f_scrambleAcc f_scramble,
5380 XXH3_f_initCustomSecret f_initSec)
5383 return XXH3_hashLong_128b_internal(input, len,
5384 XXH3_kSecret, sizeof(XXH3_kSecret),
5385 f_acc512, f_scramble);
5386 { XXH_ALIGN(XXH_SEC_ALIGN) xxh_u8 secret[XXH_SECRET_DEFAULT_SIZE];
5387 f_initSec(secret, seed64);
5388 return XXH3_hashLong_128b_internal(input, len, (const xxh_u8*)secret, sizeof(secret),
5389 f_acc512, f_scramble);
5394 * It's important for performance that XXH3_hashLong is not inlined.
5396 XXH_NO_INLINE XXH128_hash_t
5397 XXH3_hashLong_128b_withSeed(const void* input, size_t len,
5398 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen)
5400 (void)secret; (void)secretLen;
5401 return XXH3_hashLong_128b_withSeed_internal(input, len, seed64,
5402 XXH3_accumulate_512, XXH3_scrambleAcc, XXH3_initCustomSecret);
5405 typedef XXH128_hash_t (*XXH3_hashLong128_f)(const void* XXH_RESTRICT, size_t,
5406 XXH64_hash_t, const void* XXH_RESTRICT, size_t);
5408 XXH_FORCE_INLINE XXH128_hash_t
5409 XXH3_128bits_internal(const void* input, size_t len,
5410 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen,
5411 XXH3_hashLong128_f f_hl128)
5413 XXH_ASSERT(secretLen >= XXH3_SECRET_SIZE_MIN);
5415 * If an action is to be taken if `secret` conditions are not respected,
5416 * it should be done here.
5417 * For now, it's a contract pre-condition.
5418 * Adding a check and a branch here would cost performance at every hash.
5421 return XXH3_len_0to16_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, seed64);
5423 return XXH3_len_17to128_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64);
5424 if (len <= XXH3_MIDSIZE_MAX)
5425 return XXH3_len_129to240_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64);
5426 return f_hl128(input, len, seed64, secret, secretLen);
5430 /* === Public XXH128 API === */
5432 /*! @ingroup xxh3_family */
5433 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits(const void* input, size_t len)
5435 return XXH3_128bits_internal(input, len, 0,
5436 XXH3_kSecret, sizeof(XXH3_kSecret),
5437 XXH3_hashLong_128b_default);
5440 /*! @ingroup xxh3_family */
5441 XXH_PUBLIC_API XXH128_hash_t
5442 XXH3_128bits_withSecret(const void* input, size_t len, const void* secret, size_t secretSize)
5444 return XXH3_128bits_internal(input, len, 0,
5445 (const xxh_u8*)secret, secretSize,
5446 XXH3_hashLong_128b_withSecret);
5449 /*! @ingroup xxh3_family */
5450 XXH_PUBLIC_API XXH128_hash_t
5451 XXH3_128bits_withSeed(const void* input, size_t len, XXH64_hash_t seed)
5453 return XXH3_128bits_internal(input, len, seed,
5454 XXH3_kSecret, sizeof(XXH3_kSecret),
5455 XXH3_hashLong_128b_withSeed);
5458 /*! @ingroup xxh3_family */
5459 XXH_PUBLIC_API XXH128_hash_t
5460 XXH3_128bits_withSecretandSeed(const void* input, size_t len, const void* secret, size_t secretSize, XXH64_hash_t seed)
5462 if (len <= XXH3_MIDSIZE_MAX)
5463 return XXH3_128bits_internal(input, len, seed, XXH3_kSecret, sizeof(XXH3_kSecret), NULL);
5464 return XXH3_hashLong_128b_withSecret(input, len, seed, secret, secretSize);
5467 /*! @ingroup xxh3_family */
5468 XXH_PUBLIC_API XXH128_hash_t
5469 XXH128(const void* input, size_t len, XXH64_hash_t seed)
5471 return XXH3_128bits_withSeed(input, len, seed);
5475 /* === XXH3 128-bit streaming === */
5478 * All initialization and update functions are identical to 64-bit streaming variant.
5479 * The only difference is the finalization routine.
5482 /*! @ingroup xxh3_family */
5483 XXH_PUBLIC_API XXH_errorcode
5484 XXH3_128bits_reset(XXH3_state_t* statePtr)
5486 return XXH3_64bits_reset(statePtr);
5489 /*! @ingroup xxh3_family */
5490 XXH_PUBLIC_API XXH_errorcode
5491 XXH3_128bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize)
5493 return XXH3_64bits_reset_withSecret(statePtr, secret, secretSize);
5496 /*! @ingroup xxh3_family */
5497 XXH_PUBLIC_API XXH_errorcode
5498 XXH3_128bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed)
5500 return XXH3_64bits_reset_withSeed(statePtr, seed);
5503 /*! @ingroup xxh3_family */
5504 XXH_PUBLIC_API XXH_errorcode
5505 XXH3_128bits_reset_withSecretandSeed(XXH3_state_t* statePtr, const void* secret, size_t secretSize, XXH64_hash_t seed)
5507 return XXH3_64bits_reset_withSecretandSeed(statePtr, secret, secretSize, seed);
5510 /*! @ingroup xxh3_family */
5511 XXH_PUBLIC_API XXH_errorcode
5512 XXH3_128bits_update(XXH3_state_t* state, const void* input, size_t len)
5514 return XXH3_update(state, (const xxh_u8*)input, len,
5515 XXH3_accumulate_512, XXH3_scrambleAcc);
5518 /*! @ingroup xxh3_family */
5519 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_digest (const XXH3_state_t* state)
5521 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret;
5522 if (state->totalLen > XXH3_MIDSIZE_MAX) {
5523 XXH_ALIGN(XXH_ACC_ALIGN) XXH64_hash_t acc[XXH_ACC_NB];
5524 XXH3_digest_long(acc, state, secret);
5525 XXH_ASSERT(state->secretLimit + XXH_STRIPE_LEN >= sizeof(acc) + XXH_SECRET_MERGEACCS_START);
5526 { XXH128_hash_t h128;
5527 h128.low64 = XXH3_mergeAccs(acc,
5528 secret + XXH_SECRET_MERGEACCS_START,
5529 (xxh_u64)state->totalLen * XXH_PRIME64_1);
5530 h128.high64 = XXH3_mergeAccs(acc,
5531 secret + state->secretLimit + XXH_STRIPE_LEN
5532 - sizeof(acc) - XXH_SECRET_MERGEACCS_START,
5533 ~((xxh_u64)state->totalLen * XXH_PRIME64_2));
5537 /* len <= XXH3_MIDSIZE_MAX : short code */
5539 return XXH3_128bits_withSeed(state->buffer, (size_t)state->totalLen, state->seed);
5540 return XXH3_128bits_withSecret(state->buffer, (size_t)(state->totalLen),
5541 secret, state->secretLimit + XXH_STRIPE_LEN);
5544 /* 128-bit utility functions */
5546 #include <string.h> /* memcmp, memcpy */
5548 /* return : 1 is equal, 0 if different */
5549 /*! @ingroup xxh3_family */
5550 XXH_PUBLIC_API int XXH128_isEqual(XXH128_hash_t h1, XXH128_hash_t h2)
5552 /* note : XXH128_hash_t is compact, it has no padding byte */
5553 return !(memcmp(&h1, &h2, sizeof(h1)));
5556 /* This prototype is compatible with stdlib's qsort().
5557 * return : >0 if *h128_1 > *h128_2
5558 * <0 if *h128_1 < *h128_2
5559 * =0 if *h128_1 == *h128_2 */
5560 /*! @ingroup xxh3_family */
5561 XXH_PUBLIC_API int XXH128_cmp(const void* h128_1, const void* h128_2)
5563 XXH128_hash_t const h1 = *(const XXH128_hash_t*)h128_1;
5564 XXH128_hash_t const h2 = *(const XXH128_hash_t*)h128_2;
5565 int const hcmp = (h1.high64 > h2.high64) - (h2.high64 > h1.high64);
5566 /* note : bets that, in most cases, hash values are different */
5567 if (hcmp) return hcmp;
5568 return (h1.low64 > h2.low64) - (h2.low64 > h1.low64);
5572 /*====== Canonical representation ======*/
5573 /*! @ingroup xxh3_family */
5575 XXH128_canonicalFromHash(XXH128_canonical_t* dst, XXH128_hash_t hash)
5577 XXH_STATIC_ASSERT(sizeof(XXH128_canonical_t) == sizeof(XXH128_hash_t));
5578 if (XXH_CPU_LITTLE_ENDIAN) {
5579 hash.high64 = XXH_swap64(hash.high64);
5580 hash.low64 = XXH_swap64(hash.low64);
5582 XXH_memcpy(dst, &hash.high64, sizeof(hash.high64));
5583 XXH_memcpy((char*)dst + sizeof(hash.high64), &hash.low64, sizeof(hash.low64));
5586 /*! @ingroup xxh3_family */
5587 XXH_PUBLIC_API XXH128_hash_t
5588 XXH128_hashFromCanonical(const XXH128_canonical_t* src)
5591 h.high64 = XXH_readBE64(src);
5592 h.low64 = XXH_readBE64(src->digest + 8);
5598 /* ==========================================
5600 * ==========================================
5602 #define XXH_MIN(x, y) (((x) > (y)) ? (y) : (x))
5604 XXH_FORCE_INLINE void XXH3_combine16(void* dst, XXH128_hash_t h128)
5606 XXH_writeLE64( dst, XXH_readLE64(dst) ^ h128.low64 );
5607 XXH_writeLE64( (char*)dst+8, XXH_readLE64((char*)dst+8) ^ h128.high64 );
5610 /*! @ingroup xxh3_family */
5611 XXH_PUBLIC_API XXH_errorcode
5612 XXH3_generateSecret(void* secretBuffer, size_t secretSize, const void* customSeed, size_t customSeedSize)
5614 #if (XXH_DEBUGLEVEL >= 1)
5615 XXH_ASSERT(secretBuffer != NULL);
5616 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN);
5618 /* production mode, assert() are disabled */
5619 if (secretBuffer == NULL) return XXH_ERROR;
5620 if (secretSize < XXH3_SECRET_SIZE_MIN) return XXH_ERROR;
5623 if (customSeedSize == 0) {
5624 customSeed = XXH3_kSecret;
5625 customSeedSize = XXH_SECRET_DEFAULT_SIZE;
5627 #if (XXH_DEBUGLEVEL >= 1)
5628 XXH_ASSERT(customSeed != NULL);
5630 if (customSeed == NULL) return XXH_ERROR;
5633 /* Fill secretBuffer with a copy of customSeed - repeat as needed */
5635 while (pos < secretSize) {
5636 size_t const toCopy = XXH_MIN((secretSize - pos), customSeedSize);
5637 memcpy((char*)secretBuffer + pos, customSeed, toCopy);
5641 { size_t const nbSeg16 = secretSize / 16;
5643 XXH128_canonical_t scrambler;
5644 XXH128_canonicalFromHash(&scrambler, XXH128(customSeed, customSeedSize, 0));
5645 for (n=0; n<nbSeg16; n++) {
5646 XXH128_hash_t const h128 = XXH128(&scrambler, sizeof(scrambler), n);
5647 XXH3_combine16((char*)secretBuffer + n*16, h128);
5650 XXH3_combine16((char*)secretBuffer + secretSize - 16, XXH128_hashFromCanonical(&scrambler));
5655 /*! @ingroup xxh3_family */
5657 XXH3_generateSecret_fromSeed(void* secretBuffer, XXH64_hash_t seed)
5659 XXH_ALIGN(XXH_SEC_ALIGN) xxh_u8 secret[XXH_SECRET_DEFAULT_SIZE];
5660 XXH3_initCustomSecret(secret, seed);
5661 XXH_ASSERT(secretBuffer != NULL);
5662 memcpy(secretBuffer, secret, XXH_SECRET_DEFAULT_SIZE);
5667 /* Pop our optimization override from above */
5668 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
5669 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
5670 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
5671 # pragma GCC pop_options
5674 #endif /* XXH_NO_LONG_LONG */
5676 #endif /* XXH_NO_XXH3 */
5681 #endif /* XXH_IMPLEMENTATION */
5684 #if defined (__cplusplus)