1 // Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
6 /* BEGIN RocksDB customizations */
7 #ifndef XXH_STATIC_LINKING_ONLY
8 // Using compiled xxhash.cc
9 #define XXH_STATIC_LINKING_ONLY 1
10 #endif // !defined(XXH_STATIC_LINKING_ONLY)
12 #define XXH_NAMESPACE ROCKSDB_
13 #endif // !defined(XXH_NAMESPACE)
15 // for FALLTHROUGH_INTENDED, inserted as appropriate
16 #include "port/lang.h"
17 /* END RocksDB customizations */
21 * xxHash - Extremely Fast Hash algorithm
23 * Copyright (C) 2012-2020 Yann Collet
25 * BSD 2-Clause License (https://www.opensource.org/licenses/bsd-license.php)
27 * Redistribution and use in source and binary forms, with or without
28 * modification, are permitted provided that the following conditions are
31 * * Redistributions of source code must retain the above copyright
32 * notice, this list of conditions and the following disclaimer.
33 * * Redistributions in binary form must reproduce the above
34 * copyright notice, this list of conditions and the following disclaimer
35 * in the documentation and/or other materials provided with the
38 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
39 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
40 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
41 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
42 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
44 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
46 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
47 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
48 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
50 * You can contact the author at:
51 * - xxHash homepage: https://www.xxhash.com
52 * - xxHash source repository: https://github.com/Cyan4973/xxHash
58 * xxHash prototypes and implementation
61 /* Notice extracted from xxHash homepage:
63 xxHash is an extremely fast hash algorithm, running at RAM speed limits.
64 It also successfully passes all tests from the SMHasher suite.
66 Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz)
68 Name Speed Q.Score Author
70 CrapWow 3.2 GB/s 2 Andrew
71 MurmurHash 3a 2.7 GB/s 10 Austin Appleby
72 SpookyHash 2.0 GB/s 10 Bob Jenkins
73 SBox 1.4 GB/s 9 Bret Mulvey
74 Lookup3 1.2 GB/s 9 Bob Jenkins
75 SuperFastHash 1.2 GB/s 1 Paul Hsieh
76 CityHash64 1.05 GB/s 10 Pike & Alakuijala
77 FNV 0.55 GB/s 5 Fowler, Noll, Vo
79 MD5-32 0.33 GB/s 10 Ronald L. Rivest
82 Q.Score is a measure of quality of the hash function.
83 It depends on successfully passing SMHasher test set.
84 10 is a perfect score.
86 Note: SMHasher's CRC32 implementation is not the fastest one.
87 Other speed-oriented implementations can be faster,
88 especially in combination with PCLMUL instruction:
89 https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html?showComment=1552696407071#c3490092340461170735
91 A 64-bit version, named XXH64, is available since r35.
92 It offers much better speed, but for 64-bit applications only.
93 Name Speed on 64 bits Speed on 32 bits
94 XXH64 13.8 GB/s 1.9 GB/s
95 XXH32 6.8 GB/s 6.0 GB/s
98 #if defined (__cplusplus)
102 /* ****************************
104 ******************************/
106 * XXH_INLINE_ALL (and XXH_PRIVATE_API)
107 * Use these build macros to inline xxhash into the target unit.
108 * Inlining improves performance on small inputs, especially when the length is
109 * expressed as a compile-time constant:
111 * https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html
113 * It also keeps xxHash symbols private to the unit, so they are not exported.
116 * #define XXH_INLINE_ALL
117 * #include "xxhash.h"
119 * Do not compile and link xxhash.o as a separate object, as it is not useful.
121 #if (defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)) \
122 && !defined(XXH_INLINE_ALL_31684351384)
123 /* this section should be traversed only once */
124 # define XXH_INLINE_ALL_31684351384
125 /* give access to the advanced API, required to compile implementations */
126 # undef XXH_STATIC_LINKING_ONLY /* avoid macro redef */
127 # define XXH_STATIC_LINKING_ONLY
128 /* make all functions private */
129 # undef XXH_PUBLIC_API
130 # if defined(__GNUC__)
131 # define XXH_PUBLIC_API static __inline __attribute__((unused))
132 # elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
133 # define XXH_PUBLIC_API static inline
134 # elif defined(_MSC_VER)
135 # define XXH_PUBLIC_API static __inline
137 /* note: this version may generate warnings for unused static functions */
138 # define XXH_PUBLIC_API static
142 * This part deals with the special case where a unit wants to inline xxHash,
143 * but "xxhash.h" has previously been included without XXH_INLINE_ALL, such
144 * as part of some previously included *.h header file.
145 * Without further action, the new include would just be ignored,
146 * and functions would effectively _not_ be inlined (silent failure).
147 * The following macros solve this situation by prefixing all inlined names,
148 * avoiding naming collision with previous inclusions.
150 # ifdef XXH_NAMESPACE
151 # error "XXH_INLINE_ALL with XXH_NAMESPACE is not supported"
153 * Note: Alternative: #undef all symbols (it's a pretty large list).
154 * Without #error: it compiles, but functions are actually not inlined.
157 # define XXH_NAMESPACE XXH_INLINE_
159 * Some identifiers (enums, type names) are not symbols, but they must
160 * still be renamed to avoid redeclaration.
161 * Alternative solution: do not redeclare them.
162 * However, this requires some #ifdefs, and is a more dispersed action.
163 * Meanwhile, renaming can be achieved in a single block
165 # define XXH_IPREF(Id) XXH_INLINE_ ## Id
166 # define XXH_OK XXH_IPREF(XXH_OK)
167 # define XXH_ERROR XXH_IPREF(XXH_ERROR)
168 # define XXH_errorcode XXH_IPREF(XXH_errorcode)
169 # define XXH32_canonical_t XXH_IPREF(XXH32_canonical_t)
170 # define XXH64_canonical_t XXH_IPREF(XXH64_canonical_t)
171 # define XXH128_canonical_t XXH_IPREF(XXH128_canonical_t)
172 # define XXH32_state_s XXH_IPREF(XXH32_state_s)
173 # define XXH32_state_t XXH_IPREF(XXH32_state_t)
174 # define XXH64_state_s XXH_IPREF(XXH64_state_s)
175 # define XXH64_state_t XXH_IPREF(XXH64_state_t)
176 # define XXH3_state_s XXH_IPREF(XXH3_state_s)
177 # define XXH3_state_t XXH_IPREF(XXH3_state_t)
178 # define XXH128_hash_t XXH_IPREF(XXH128_hash_t)
179 /* Ensure the header is parsed again, even if it was previously included */
180 # undef XXHASH_H_5627135585666179
181 # undef XXHASH_H_STATIC_13879238742
182 #endif /* XXH_INLINE_ALL || XXH_PRIVATE_API */
186 /* ****************************************************************
188 *****************************************************************/
189 #ifndef XXHASH_H_5627135585666179
190 #define XXHASH_H_5627135585666179 1
194 * @defgroup public Public API
195 * Contains details on the public xxHash functions.
198 /* specific declaration modes for Windows */
199 #if !defined(XXH_INLINE_ALL) && !defined(XXH_PRIVATE_API)
200 # if defined(WIN32) && defined(_MSC_VER) && (defined(XXH_IMPORT) || defined(XXH_EXPORT))
202 # define XXH_PUBLIC_API __declspec(dllexport)
204 # define XXH_PUBLIC_API __declspec(dllimport)
207 # define XXH_PUBLIC_API /* do nothing */
213 * @brief Emulate a namespace by transparently prefixing all symbols.
215 * If you want to include _and expose_ xxHash functions from within your own
216 * library, but also want to avoid symbol collisions with other libraries which
217 * may also include xxHash, you can use XXH_NAMESPACE to automatically prefix
218 * any public symbol from xxhash library with the value of XXH_NAMESPACE
219 * (therefore, avoid empty or numeric values).
221 * Note that no change is required within the calling program as long as it
222 * includes `xxhash.h`: Regular symbol names will be automatically translated
225 # define XXH_NAMESPACE /* YOUR NAME HERE */
226 # undef XXH_NAMESPACE
230 # define XXH_CAT(A,B) A##B
231 # define XXH_NAME2(A,B) XXH_CAT(A,B)
232 # define XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, XXH_versionNumber)
234 # define XXH32 XXH_NAME2(XXH_NAMESPACE, XXH32)
235 # define XXH32_createState XXH_NAME2(XXH_NAMESPACE, XXH32_createState)
236 # define XXH32_freeState XXH_NAME2(XXH_NAMESPACE, XXH32_freeState)
237 # define XXH32_reset XXH_NAME2(XXH_NAMESPACE, XXH32_reset)
238 # define XXH32_update XXH_NAME2(XXH_NAMESPACE, XXH32_update)
239 # define XXH32_digest XXH_NAME2(XXH_NAMESPACE, XXH32_digest)
240 # define XXH32_copyState XXH_NAME2(XXH_NAMESPACE, XXH32_copyState)
241 # define XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH32_canonicalFromHash)
242 # define XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH32_hashFromCanonical)
244 # define XXH64 XXH_NAME2(XXH_NAMESPACE, XXH64)
245 # define XXH64_createState XXH_NAME2(XXH_NAMESPACE, XXH64_createState)
246 # define XXH64_freeState XXH_NAME2(XXH_NAMESPACE, XXH64_freeState)
247 # define XXH64_reset XXH_NAME2(XXH_NAMESPACE, XXH64_reset)
248 # define XXH64_update XXH_NAME2(XXH_NAMESPACE, XXH64_update)
249 # define XXH64_digest XXH_NAME2(XXH_NAMESPACE, XXH64_digest)
250 # define XXH64_copyState XXH_NAME2(XXH_NAMESPACE, XXH64_copyState)
251 # define XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH64_canonicalFromHash)
252 # define XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH64_hashFromCanonical)
254 # define XXH3_64bits XXH_NAME2(XXH_NAMESPACE, XXH3_64bits)
255 # define XXH3_64bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSecret)
256 # define XXH3_64bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSeed)
257 # define XXH3_createState XXH_NAME2(XXH_NAMESPACE, XXH3_createState)
258 # define XXH3_freeState XXH_NAME2(XXH_NAMESPACE, XXH3_freeState)
259 # define XXH3_copyState XXH_NAME2(XXH_NAMESPACE, XXH3_copyState)
260 # define XXH3_64bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset)
261 # define XXH3_64bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSeed)
262 # define XXH3_64bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSecret)
263 # define XXH3_64bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_update)
264 # define XXH3_64bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_digest)
265 # define XXH3_generateSecret XXH_NAME2(XXH_NAMESPACE, XXH3_generateSecret)
267 # define XXH128 XXH_NAME2(XXH_NAMESPACE, XXH128)
268 # define XXH3_128bits XXH_NAME2(XXH_NAMESPACE, XXH3_128bits)
269 # define XXH3_128bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSeed)
270 # define XXH3_128bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSecret)
271 # define XXH3_128bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset)
272 # define XXH3_128bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSeed)
273 # define XXH3_128bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSecret)
274 # define XXH3_128bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_update)
275 # define XXH3_128bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_digest)
276 # define XXH128_isEqual XXH_NAME2(XXH_NAMESPACE, XXH128_isEqual)
277 # define XXH128_cmp XXH_NAME2(XXH_NAMESPACE, XXH128_cmp)
278 # define XXH128_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH128_canonicalFromHash)
279 # define XXH128_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH128_hashFromCanonical)
283 /* *************************************
285 ***************************************/
286 #define XXH_VERSION_MAJOR 0
287 #define XXH_VERSION_MINOR 8
288 #define XXH_VERSION_RELEASE 1
289 #define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE)
292 * @brief Obtains the xxHash version.
294 * This is only useful when xxHash is compiled as a shared library, as it is
295 * independent of the version defined in the header.
297 * @return `XXH_VERSION_NUMBER` as of when the libray was compiled.
299 XXH_PUBLIC_API
unsigned XXH_versionNumber (void);
302 /* ****************************
304 ******************************/
305 #include <stddef.h> /* size_t */
306 typedef enum { XXH_OK
=0, XXH_ERROR
} XXH_errorcode
;
309 /*-**********************************************************************
311 ************************************************************************/
312 #if defined(XXH_DOXYGEN) /* Don't show <stdint.h> include */
314 * @brief An unsigned 32-bit integer.
316 * Not necessarily defined to `uint32_t` but functionally equivalent.
318 typedef uint32_t XXH32_hash_t
;
319 #elif !defined (__VMS) \
320 && (defined (__cplusplus) \
321 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
323 typedef uint32_t XXH32_hash_t
;
326 # if UINT_MAX == 0xFFFFFFFFUL
327 typedef unsigned int XXH32_hash_t
;
329 # if ULONG_MAX == 0xFFFFFFFFUL
330 typedef unsigned long XXH32_hash_t
;
332 # error "unsupported platform: need a 32-bit type"
340 * @defgroup xxh32_family XXH32 family
342 * Contains functions used in the classic 32-bit xxHash algorithm.
345 * XXH32 is considered rather weak by today's standards.
346 * The @ref xxh3_family provides competitive speed for both 32-bit and 64-bit
347 * systems, and offers true 64/128 bit hash results. It provides a superior
348 * level of dispersion, and greatly reduces the risks of collisions.
350 * @see @ref xxh64_family, @ref xxh3_family : Other xxHash families
351 * @see @ref xxh32_impl for implementation details
356 * @brief Calculates the 32-bit hash of @p input using xxHash32.
358 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark): 5.4 GB/s
360 * @param input The block of data to be hashed, at least @p length bytes in size.
361 * @param length The length of @p input, in bytes.
362 * @param seed The 32-bit seed to alter the hash's output predictably.
365 * The memory between @p input and @p input + @p length must be valid,
366 * readable, contiguous memory. However, if @p length is `0`, @p input may be
367 * `NULL`. In C++, this also must be *TriviallyCopyable*.
369 * @return The calculated 32-bit hash value.
372 * XXH64(), XXH3_64bits_withSeed(), XXH3_128bits_withSeed(), XXH128():
373 * Direct equivalents for the other variants of xxHash.
375 * XXH32_createState(), XXH32_update(), XXH32_digest(): Streaming version.
377 XXH_PUBLIC_API XXH32_hash_t
XXH32 (const void* input
, size_t length
, XXH32_hash_t seed
);
380 * Streaming functions generate the xxHash value from an incremental input.
381 * This method is slower than single-call functions, due to state management.
382 * For small inputs, prefer `XXH32()` and `XXH64()`, which are better optimized.
384 * An XXH state must first be allocated using `XXH*_createState()`.
386 * Start a new hash by initializing the state with a seed using `XXH*_reset()`.
388 * Then, feed the hash state by calling `XXH*_update()` as many times as necessary.
390 * The function returns an error code, with 0 meaning OK, and any other value
391 * meaning there is an error.
393 * Finally, a hash value can be produced anytime, by using `XXH*_digest()`.
394 * This function returns the nn-bits hash as an int or long long.
396 * It's still possible to continue inserting input into the hash state after a
397 * digest, and generate new hash values later on by invoking `XXH*_digest()`.
399 * When done, release the state using `XXH*_freeState()`.
401 * Example code for incrementally hashing a file:
404 * #include <xxhash.h>
405 * #define BUFFER_SIZE 256
407 * // Note: XXH64 and XXH3 use the same interface.
409 * hashFile(FILE* stream)
411 * XXH32_state_t* state;
412 * unsigned char buf[BUFFER_SIZE];
416 * state = XXH32_createState(); // Create a state
417 * assert(state != NULL); // Error check here
418 * XXH32_reset(state, 0xbaad5eed); // Reset state with our seed
419 * while ((amt = fread(buf, 1, sizeof(buf), stream)) != 0) {
420 * XXH32_update(state, buf, amt); // Hash the file in chunks
422 * hash = XXH32_digest(state); // Finalize the hash
423 * XXH32_freeState(state); // Clean up
430 * @typedef struct XXH32_state_s XXH32_state_t
431 * @brief The opaque state struct for the XXH32 streaming API.
433 * @see XXH32_state_s for details.
435 typedef struct XXH32_state_s XXH32_state_t
;
438 * @brief Allocates an @ref XXH32_state_t.
440 * Must be freed with XXH32_freeState().
441 * @return An allocated XXH32_state_t on success, `NULL` on failure.
443 XXH_PUBLIC_API XXH32_state_t
* XXH32_createState(void);
445 * @brief Frees an @ref XXH32_state_t.
447 * Must be allocated with XXH32_createState().
448 * @param statePtr A pointer to an @ref XXH32_state_t allocated with @ref XXH32_createState().
451 XXH_PUBLIC_API XXH_errorcode
XXH32_freeState(XXH32_state_t
* statePtr
);
453 * @brief Copies one @ref XXH32_state_t to another.
455 * @param dst_state The state to copy to.
456 * @param src_state The state to copy from.
458 * @p dst_state and @p src_state must not be `NULL` and must not overlap.
460 XXH_PUBLIC_API
void XXH32_copyState(XXH32_state_t
* dst_state
, const XXH32_state_t
* src_state
);
463 * @brief Resets an @ref XXH32_state_t to begin a new hash.
465 * This function resets and seeds a state. Call it before @ref XXH32_update().
467 * @param statePtr The state struct to reset.
468 * @param seed The 32-bit seed to alter the hash result predictably.
471 * @p statePtr must not be `NULL`.
473 * @return @ref XXH_OK on success, @ref XXH_ERROR on failure.
475 XXH_PUBLIC_API XXH_errorcode
XXH32_reset (XXH32_state_t
* statePtr
, XXH32_hash_t seed
);
478 * @brief Consumes a block of @p input to an @ref XXH32_state_t.
480 * Call this to incrementally consume blocks of data.
482 * @param statePtr The state struct to update.
483 * @param input The block of data to be hashed, at least @p length bytes in size.
484 * @param length The length of @p input, in bytes.
487 * @p statePtr must not be `NULL`.
489 * The memory between @p input and @p input + @p length must be valid,
490 * readable, contiguous memory. However, if @p length is `0`, @p input may be
491 * `NULL`. In C++, this also must be *TriviallyCopyable*.
493 * @return @ref XXH_OK on success, @ref XXH_ERROR on failure.
495 XXH_PUBLIC_API XXH_errorcode
XXH32_update (XXH32_state_t
* statePtr
, const void* input
, size_t length
);
498 * @brief Returns the calculated hash value from an @ref XXH32_state_t.
501 * Calling XXH32_digest() will not affect @p statePtr, so you can update,
502 * digest, and update again.
504 * @param statePtr The state struct to calculate the hash from.
507 * @p statePtr must not be `NULL`.
509 * @return The calculated xxHash32 value from that state.
511 XXH_PUBLIC_API XXH32_hash_t
XXH32_digest (const XXH32_state_t
* statePtr
);
513 /******* Canonical representation *******/
516 * The default return values from XXH functions are unsigned 32 and 64 bit
518 * This the simplest and fastest format for further post-processing.
520 * However, this leaves open the question of what is the order on the byte level,
521 * since little and big endian conventions will store the same number differently.
523 * The canonical representation settles this issue by mandating big-endian
524 * convention, the same convention as human-readable numbers (large digits first).
526 * When writing hash values to storage, sending them over a network, or printing
527 * them, it's highly recommended to use the canonical representation to ensure
528 * portability across a wider range of systems, present and future.
530 * The following functions allow transformation of hash values to and from
535 * @brief Canonical (big endian) representation of @ref XXH32_hash_t.
538 unsigned char digest
[4]; /*!< Hash bytes, big endian */
542 * @brief Converts an @ref XXH32_hash_t to a big endian @ref XXH32_canonical_t.
544 * @param dst The @ref XXH32_canonical_t pointer to be stored to.
545 * @param hash The @ref XXH32_hash_t to be converted.
548 * @p dst must not be `NULL`.
550 XXH_PUBLIC_API
void XXH32_canonicalFromHash(XXH32_canonical_t
* dst
, XXH32_hash_t hash
);
553 * @brief Converts an @ref XXH32_canonical_t to a native @ref XXH32_hash_t.
555 * @param src The @ref XXH32_canonical_t to convert.
558 * @p src must not be `NULL`.
560 * @return The converted hash.
562 XXH_PUBLIC_API XXH32_hash_t
XXH32_hashFromCanonical(const XXH32_canonical_t
* src
);
571 #ifndef XXH_NO_LONG_LONG
572 /*-**********************************************************************
574 ************************************************************************/
575 #if defined(XXH_DOXYGEN) /* don't include <stdint.h> */
577 * @brief An unsigned 64-bit integer.
579 * Not necessarily defined to `uint64_t` but functionally equivalent.
581 typedef uint64_t XXH64_hash_t
;
582 #elif !defined (__VMS) \
583 && (defined (__cplusplus) \
584 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
586 typedef uint64_t XXH64_hash_t
;
589 # if defined(__LP64__) && ULONG_MAX == 0xFFFFFFFFFFFFFFFFULL
590 /* LP64 ABI says uint64_t is unsigned long */
591 typedef unsigned long XXH64_hash_t
;
593 /* the following type must have a width of 64-bit */
594 typedef unsigned long long XXH64_hash_t
;
601 * @defgroup xxh64_family XXH64 family
604 * Contains functions used in the classic 64-bit xxHash algorithm.
607 * XXH3 provides competitive speed for both 32-bit and 64-bit systems,
608 * and offers true 64/128 bit hash results. It provides a superior level of
609 * dispersion, and greatly reduces the risks of collisions.
614 * @brief Calculates the 64-bit hash of @p input using xxHash64.
616 * This function usually runs faster on 64-bit systems, but slower on 32-bit
617 * systems (see benchmark).
619 * @param input The block of data to be hashed, at least @p length bytes in size.
620 * @param length The length of @p input, in bytes.
621 * @param seed The 64-bit seed to alter the hash's output predictably.
624 * The memory between @p input and @p input + @p length must be valid,
625 * readable, contiguous memory. However, if @p length is `0`, @p input may be
626 * `NULL`. In C++, this also must be *TriviallyCopyable*.
628 * @return The calculated 64-bit hash.
631 * XXH32(), XXH3_64bits_withSeed(), XXH3_128bits_withSeed(), XXH128():
632 * Direct equivalents for the other variants of xxHash.
634 * XXH64_createState(), XXH64_update(), XXH64_digest(): Streaming version.
636 XXH_PUBLIC_API XXH64_hash_t
XXH64(const void* input
, size_t length
, XXH64_hash_t seed
);
638 /******* Streaming *******/
640 * @brief The opaque state struct for the XXH64 streaming API.
642 * @see XXH64_state_s for details.
644 typedef struct XXH64_state_s XXH64_state_t
; /* incomplete type */
645 XXH_PUBLIC_API XXH64_state_t
* XXH64_createState(void);
646 XXH_PUBLIC_API XXH_errorcode
XXH64_freeState(XXH64_state_t
* statePtr
);
647 XXH_PUBLIC_API
void XXH64_copyState(XXH64_state_t
* dst_state
, const XXH64_state_t
* src_state
);
649 XXH_PUBLIC_API XXH_errorcode
XXH64_reset (XXH64_state_t
* statePtr
, XXH64_hash_t seed
);
650 XXH_PUBLIC_API XXH_errorcode
XXH64_update (XXH64_state_t
* statePtr
, const void* input
, size_t length
);
651 XXH_PUBLIC_API XXH64_hash_t
XXH64_digest (const XXH64_state_t
* statePtr
);
653 /******* Canonical representation *******/
654 typedef struct { unsigned char digest
[sizeof(XXH64_hash_t
)]; } XXH64_canonical_t
;
655 XXH_PUBLIC_API
void XXH64_canonicalFromHash(XXH64_canonical_t
* dst
, XXH64_hash_t hash
);
656 XXH_PUBLIC_API XXH64_hash_t
XXH64_hashFromCanonical(const XXH64_canonical_t
* src
);
660 * ************************************************************************
661 * @defgroup xxh3_family XXH3 family
665 * XXH3 is a more recent hash algorithm featuring:
666 * - Improved speed for both small and large inputs
667 * - True 64-bit and 128-bit outputs
668 * - SIMD acceleration
669 * - Improved 32-bit viability
671 * Speed analysis methodology is explained here:
673 * https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html
675 * Compared to XXH64, expect XXH3 to run approximately
676 * ~2x faster on large inputs and >3x faster on small ones,
677 * exact differences vary depending on platform.
679 * XXH3's speed benefits greatly from SIMD and 64-bit arithmetic,
680 * but does not require it.
681 * Any 32-bit and 64-bit targets that can run XXH32 smoothly
682 * can run XXH3 at competitive speeds, even without vector support.
683 * Further details are explained in the implementation.
685 * Optimized implementations are provided for AVX512, AVX2, SSE2, NEON, POWER8,
686 * ZVector and scalar targets. This can be controlled via the XXH_VECTOR macro.
688 * XXH3 implementation is portable:
689 * it has a generic C90 formulation that can be compiled on any platform,
690 * all implementations generage exactly the same hash value on all platforms.
691 * Starting from v0.8.0, it's also labelled "stable", meaning that
692 * any future version will also generate the same hash value.
694 * XXH3 offers 2 variants, _64bits and _128bits.
696 * When only 64 bits are needed, prefer invoking the _64bits variant, as it
697 * reduces the amount of mixing, resulting in faster speed on small inputs.
698 * It's also generally simpler to manipulate a scalar return type than a struct.
700 * The API supports one-shot hashing, streaming mode, and custom secrets.
703 /*-**********************************************************************
704 * XXH3 64-bit variant
705 ************************************************************************/
708 * default 64-bit variant, using default secret and default seed of 0.
709 * It's the fastest variant. */
710 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits(const void* data
, size_t len
);
713 * XXH3_64bits_withSeed():
714 * This variant generates a custom secret on the fly
715 * based on default secret altered using the `seed` value.
716 * While this operation is decently fast, note that it's not completely free.
717 * Note: seed==0 produces the same results as XXH3_64bits().
719 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits_withSeed(const void* data
, size_t len
, XXH64_hash_t seed
);
722 * The bare minimum size for a custom secret.
725 * XXH3_64bits_withSecret(), XXH3_64bits_reset_withSecret(),
726 * XXH3_128bits_withSecret(), XXH3_128bits_reset_withSecret().
728 #define XXH3_SECRET_SIZE_MIN 136
731 * XXH3_64bits_withSecret():
732 * It's possible to provide any blob of bytes as a "secret" to generate the hash.
733 * This makes it more difficult for an external actor to prepare an intentional collision.
734 * The main condition is that secretSize *must* be large enough (>= XXH3_SECRET_SIZE_MIN).
735 * However, the quality of produced hash values depends on secret's entropy.
736 * Technically, the secret must look like a bunch of random bytes.
737 * Avoid "trivial" or structured data such as repeated sequences or a text document.
738 * Whenever unsure about the "randomness" of the blob of bytes,
739 * consider relabelling it as a "custom seed" instead,
740 * and employ "XXH3_generateSecret()" (see below)
741 * to generate a high entropy secret derived from the custom seed.
743 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits_withSecret(const void* data
, size_t len
, const void* secret
, size_t secretSize
);
746 /******* Streaming *******/
748 * Streaming requires state maintenance.
749 * This operation costs memory and CPU.
750 * As a consequence, streaming is slower than one-shot hashing.
751 * For better performance, prefer one-shot functions whenever applicable.
755 * @brief The state struct for the XXH3 streaming API.
757 * @see XXH3_state_s for details.
759 typedef struct XXH3_state_s XXH3_state_t
;
760 XXH_PUBLIC_API XXH3_state_t
* XXH3_createState(void);
761 XXH_PUBLIC_API XXH_errorcode
XXH3_freeState(XXH3_state_t
* statePtr
);
762 XXH_PUBLIC_API
void XXH3_copyState(XXH3_state_t
* dst_state
, const XXH3_state_t
* src_state
);
765 * XXH3_64bits_reset():
766 * Initialize with default parameters.
767 * digest will be equivalent to `XXH3_64bits()`.
769 XXH_PUBLIC_API XXH_errorcode
XXH3_64bits_reset(XXH3_state_t
* statePtr
);
771 * XXH3_64bits_reset_withSeed():
772 * Generate a custom secret from `seed`, and store it into `statePtr`.
773 * digest will be equivalent to `XXH3_64bits_withSeed()`.
775 XXH_PUBLIC_API XXH_errorcode
XXH3_64bits_reset_withSeed(XXH3_state_t
* statePtr
, XXH64_hash_t seed
);
777 * XXH3_64bits_reset_withSecret():
778 * `secret` is referenced, it _must outlive_ the hash streaming session.
779 * Similar to one-shot API, `secretSize` must be >= `XXH3_SECRET_SIZE_MIN`,
780 * and the quality of produced hash values depends on secret's entropy
781 * (secret's content should look like a bunch of random bytes).
782 * When in doubt about the randomness of a candidate `secret`,
783 * consider employing `XXH3_generateSecret()` instead (see below).
785 XXH_PUBLIC_API XXH_errorcode
XXH3_64bits_reset_withSecret(XXH3_state_t
* statePtr
, const void* secret
, size_t secretSize
);
787 XXH_PUBLIC_API XXH_errorcode
XXH3_64bits_update (XXH3_state_t
* statePtr
, const void* input
, size_t length
);
788 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits_digest (const XXH3_state_t
* statePtr
);
790 /* note : canonical representation of XXH3 is the same as XXH64
791 * since they both produce XXH64_hash_t values */
794 /*-**********************************************************************
795 * XXH3 128-bit variant
796 ************************************************************************/
799 * @brief The return value from 128-bit hashes.
801 * Stored in little endian order, although the fields themselves are in native
805 XXH64_hash_t low64
; /*!< `value & 0xFFFFFFFFFFFFFFFF` */
806 XXH64_hash_t high64
; /*!< `value >> 64` */
809 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits(const void* data
, size_t len
);
810 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits_withSeed(const void* data
, size_t len
, XXH64_hash_t seed
);
811 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits_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.
820 * XXH3_128bits uses the same XXH3_state_t as XXH3_64bits().
821 * Use already declared XXH3_createState() and XXH3_freeState().
823 * All reset and streaming functions have same meaning as their 64-bit counterpart.
826 XXH_PUBLIC_API XXH_errorcode
XXH3_128bits_reset(XXH3_state_t
* statePtr
);
827 XXH_PUBLIC_API XXH_errorcode
XXH3_128bits_reset_withSeed(XXH3_state_t
* statePtr
, XXH64_hash_t seed
);
828 XXH_PUBLIC_API XXH_errorcode
XXH3_128bits_reset_withSecret(XXH3_state_t
* statePtr
, const void* secret
, size_t secretSize
);
830 XXH_PUBLIC_API XXH_errorcode
XXH3_128bits_update (XXH3_state_t
* statePtr
, const void* input
, size_t length
);
831 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits_digest (const XXH3_state_t
* statePtr
);
833 /* Following helper functions make it possible to compare XXH128_hast_t values.
834 * Since XXH128_hash_t is a structure, this capability is not offered by the language.
835 * Note: For better performance, these functions can be inlined using XXH_INLINE_ALL */
839 * Return: 1 if `h1` and `h2` are equal, 0 if they are not.
841 XXH_PUBLIC_API
int XXH128_isEqual(XXH128_hash_t h1
, XXH128_hash_t h2
);
846 * This comparator is compatible with stdlib's `qsort()`/`bsearch()`.
848 * return: >0 if *h128_1 > *h128_2
849 * =0 if *h128_1 == *h128_2
850 * <0 if *h128_1 < *h128_2
852 XXH_PUBLIC_API
int XXH128_cmp(const void* h128_1
, const void* h128_2
);
855 /******* Canonical representation *******/
856 typedef struct { unsigned char digest
[sizeof(XXH128_hash_t
)]; } XXH128_canonical_t
;
857 XXH_PUBLIC_API
void XXH128_canonicalFromHash(XXH128_canonical_t
* dst
, XXH128_hash_t hash
);
858 XXH_PUBLIC_API XXH128_hash_t
XXH128_hashFromCanonical(const XXH128_canonical_t
* src
);
861 #endif /* XXH_NO_LONG_LONG */
866 #endif /* XXHASH_H_5627135585666179 */
870 #if defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742)
871 #define XXHASH_H_STATIC_13879238742
872 /* ****************************************************************************
873 * This section contains declarations which are not guaranteed to remain stable.
874 * They may change in future versions, becoming incompatible with a different
875 * version of the library.
876 * These declarations should only be used with static linking.
877 * Never use them in association with dynamic linking!
878 ***************************************************************************** */
881 * These definitions are only present to allow static allocation
882 * of XXH states, on stack or in a struct, for example.
883 * Never **ever** access their members directly.
888 * @brief Structure for XXH32 streaming API.
890 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
891 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined. Otherwise it is
892 * an opaque type. This allows fields to safely be changed.
894 * Typedef'd to @ref XXH32_state_t.
895 * Do not access the members of this struct directly.
896 * @see XXH64_state_s, XXH3_state_s
898 struct XXH32_state_s
{
899 XXH32_hash_t total_len_32
; /*!< Total length hashed, modulo 2^32 */
900 XXH32_hash_t large_len
; /*!< Whether the hash is >= 16 (handles @ref total_len_32 overflow) */
901 XXH32_hash_t v1
; /*!< First accumulator lane */
902 XXH32_hash_t v2
; /*!< Second accumulator lane */
903 XXH32_hash_t v3
; /*!< Third accumulator lane */
904 XXH32_hash_t v4
; /*!< Fourth accumulator lane */
905 XXH32_hash_t mem32
[4]; /*!< Internal buffer for partial reads. Treated as unsigned char[16]. */
906 XXH32_hash_t memsize
; /*!< Amount of data in @ref mem32 */
907 XXH32_hash_t reserved
; /*!< Reserved field. Do not read or write to it, it may be removed. */
908 }; /* typedef'd to XXH32_state_t */
911 #ifndef XXH_NO_LONG_LONG /* defined when there is no 64-bit support */
915 * @brief Structure for XXH64 streaming API.
917 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
918 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined. Otherwise it is
919 * an opaque type. This allows fields to safely be changed.
921 * Typedef'd to @ref XXH64_state_t.
922 * Do not access the members of this struct directly.
923 * @see XXH32_state_s, XXH3_state_s
925 struct XXH64_state_s
{
926 XXH64_hash_t total_len
; /*!< Total length hashed. This is always 64-bit. */
927 XXH64_hash_t v1
; /*!< First accumulator lane */
928 XXH64_hash_t v2
; /*!< Second accumulator lane */
929 XXH64_hash_t v3
; /*!< Third accumulator lane */
930 XXH64_hash_t v4
; /*!< Fourth accumulator lane */
931 XXH64_hash_t mem64
[4]; /*!< Internal buffer for partial reads. Treated as unsigned char[32]. */
932 XXH32_hash_t memsize
; /*!< Amount of data in @ref mem64 */
933 XXH32_hash_t reserved32
; /*!< Reserved field, needed for padding anyways*/
934 XXH64_hash_t reserved64
; /*!< Reserved field. Do not read or write to it, it may be removed. */
935 }; /* typedef'd to XXH64_state_t */
937 #if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) /* C11+ */
938 # include <stdalign.h>
939 # define XXH_ALIGN(n) alignas(n)
940 #elif defined(__GNUC__)
941 # define XXH_ALIGN(n) __attribute__ ((aligned(n)))
942 #elif defined(_MSC_VER)
943 # define XXH_ALIGN(n) __declspec(align(n))
945 # define XXH_ALIGN(n) /* disabled */
948 /* Old GCC versions only accept the attribute after the type in structures. */
949 #if !(defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L)) /* C11+ */ \
951 # define XXH_ALIGN_MEMBER(align, type) type XXH_ALIGN(align)
953 # define XXH_ALIGN_MEMBER(align, type) XXH_ALIGN(align) type
957 * @brief The size of the internal XXH3 buffer.
959 * This is the optimal update size for incremental hashing.
961 * @see XXH3_64b_update(), XXH3_128b_update().
963 #define XXH3_INTERNALBUFFER_SIZE 256
966 * @brief Default size of the secret buffer (and @ref XXH3_kSecret).
968 * This is the size used in @ref XXH3_kSecret and the seeded functions.
970 * Not to be confused with @ref XXH3_SECRET_SIZE_MIN.
972 #define XXH3_SECRET_DEFAULT_SIZE 192
976 * @brief Structure for XXH3 streaming API.
978 * @note This is only defined when @ref XXH_STATIC_LINKING_ONLY,
979 * @ref XXH_INLINE_ALL, or @ref XXH_IMPLEMENTATION is defined. Otherwise it is
980 * an opaque type. This allows fields to safely be changed.
982 * @note **This structure has a strict alignment requirement of 64 bytes.** Do
983 * not allocate this with `malloc()` or `new`, it will not be sufficiently
984 * aligned. Use @ref XXH3_createState() and @ref XXH3_freeState(), or stack
987 * Typedef'd to @ref XXH3_state_t.
988 * Do not access the members of this struct directly.
990 * @see XXH3_INITSTATE() for stack initialization.
991 * @see XXH3_createState(), XXH3_freeState().
992 * @see XXH32_state_s, XXH64_state_s
994 struct XXH3_state_s
{
995 XXH_ALIGN_MEMBER(64, XXH64_hash_t acc
[8]);
996 /*!< The 8 accumulators. Similar to `vN` in @ref XXH32_state_s::v1 and @ref XXH64_state_s */
997 XXH_ALIGN_MEMBER(64, unsigned char customSecret
[XXH3_SECRET_DEFAULT_SIZE
]);
998 /*!< Used to store a custom secret generated from a seed. */
999 XXH_ALIGN_MEMBER(64, unsigned char buffer
[XXH3_INTERNALBUFFER_SIZE
]);
1000 /*!< The internal buffer. @see XXH32_state_s::mem32 */
1001 XXH32_hash_t bufferedSize
;
1002 /*!< The amount of memory in @ref buffer, @see XXH32_state_s::memsize */
1003 XXH32_hash_t reserved32
;
1004 /*!< Reserved field. Needed for padding on 64-bit. */
1005 size_t nbStripesSoFar
;
1006 /*!< Number or stripes processed. */
1007 XXH64_hash_t totalLen
;
1008 /*!< Total length hashed. 64-bit even on 32-bit targets. */
1009 size_t nbStripesPerBlock
;
1010 /*!< Number of stripes per block. */
1012 /*!< Size of @ref customSecret or @ref extSecret */
1014 /*!< Seed for _withSeed variants. Must be zero otherwise, @see XXH3_INITSTATE() */
1015 XXH64_hash_t reserved64
;
1016 /*!< Reserved field. */
1017 const unsigned char* extSecret
;
1018 /*!< Reference to an external secret for the _withSecret variants, NULL
1019 * for other variants. */
1020 /* note: there may be some padding at the end due to alignment on 64 bytes */
1021 }; /* typedef'd to XXH3_state_t */
1023 #undef XXH_ALIGN_MEMBER
1026 * @brief Initializes a stack-allocated `XXH3_state_s`.
1028 * When the @ref XXH3_state_t structure is merely emplaced on stack,
1029 * it should be initialized with XXH3_INITSTATE() or a memset()
1030 * in case its first reset uses XXH3_NNbits_reset_withSeed().
1031 * This init can be omitted if the first reset uses default or _withSecret mode.
1032 * This operation isn't necessary when the state is created with XXH3_createState().
1033 * Note that this doesn't prepare the state for a streaming operation,
1034 * it's still necessary to use XXH3_NNbits_reset*() afterwards.
1036 #define XXH3_INITSTATE(XXH3_state_ptr) { (XXH3_state_ptr)->seed = 0; }
1039 /* === Experimental API === */
1040 /* Symbols defined below must be considered tied to a specific library version. */
1043 * XXH3_generateSecret():
1045 * Derive a high-entropy secret from any user-defined content, named customSeed.
1046 * The generated secret can be used in combination with `*_withSecret()` functions.
1047 * The `_withSecret()` variants are useful to provide a higher level of protection than 64-bit seed,
1048 * as it becomes much more difficult for an external actor to guess how to impact the calculation logic.
1050 * The function accepts as input a custom seed of any length and any content,
1051 * and derives from it a high-entropy secret of length XXH3_SECRET_DEFAULT_SIZE
1052 * into an already allocated buffer secretBuffer.
1053 * The generated secret is _always_ XXH_SECRET_DEFAULT_SIZE bytes long.
1055 * The generated secret can then be used with any `*_withSecret()` variant.
1056 * Functions `XXH3_128bits_withSecret()`, `XXH3_64bits_withSecret()`,
1057 * `XXH3_128bits_reset_withSecret()` and `XXH3_64bits_reset_withSecret()`
1058 * are part of this list. They all accept a `secret` parameter
1059 * which must be very long for implementation reasons (>= XXH3_SECRET_SIZE_MIN)
1060 * _and_ feature very high entropy (consist of random-looking bytes).
1061 * These conditions can be a high bar to meet, so
1062 * this function can be used to generate a secret of proper quality.
1064 * customSeed can be anything. It can have any size, even small ones,
1065 * and its content can be anything, even stupidly "low entropy" source such as a bunch of zeroes.
1066 * The resulting `secret` will nonetheless provide all expected qualities.
1068 * Supplying NULL as the customSeed copies the default secret into `secretBuffer`.
1069 * When customSeedSize > 0, supplying NULL as customSeed is undefined behavior.
1071 XXH_PUBLIC_API
void XXH3_generateSecret(void* secretBuffer
, const void* customSeed
, size_t customSeedSize
);
1074 /* simple short-cut to pre-selected XXH3_128bits variant */
1075 XXH_PUBLIC_API XXH128_hash_t
XXH128(const void* data
, size_t len
, XXH64_hash_t seed
);
1078 #endif /* XXH_NO_LONG_LONG */
1079 #if defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)
1080 # define XXH_IMPLEMENTATION
1083 #endif /* defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742) */
1086 /* ======================================================================== */
1087 /* ======================================================================== */
1088 /* ======================================================================== */
1091 /*-**********************************************************************
1092 * xxHash implementation
1093 *-**********************************************************************
1094 * xxHash's implementation used to be hosted inside xxhash.c.
1096 * However, inlining requires implementation to be visible to the compiler,
1097 * hence be included alongside the header.
1098 * Previously, implementation was hosted inside xxhash.c,
1099 * which was then #included when inlining was activated.
1100 * This construction created issues with a few build and install systems,
1101 * as it required xxhash.c to be stored in /include directory.
1103 * xxHash implementation is now directly integrated within xxhash.h.
1104 * As a consequence, xxhash.c is no longer needed in /include.
1106 * xxhash.c is still available and is still useful.
1107 * In a "normal" setup, when xxhash is not inlined,
1108 * xxhash.h only exposes the prototypes and public symbols,
1109 * while xxhash.c can be built into an object file xxhash.o
1110 * which can then be linked into the final binary.
1111 ************************************************************************/
1113 #if ( defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API) \
1114 || defined(XXH_IMPLEMENTATION) ) && !defined(XXH_IMPLEM_13a8737387)
1115 # define XXH_IMPLEM_13a8737387
1117 /* *************************************
1119 ***************************************/
1122 * @defgroup tuning Tuning parameters
1125 * Various macros to control xxHash's behavior.
1129 * @brief Define this to disable 64-bit code.
1131 * Useful if only using the @ref xxh32_family and you have a strict C90 compiler.
1133 # define XXH_NO_LONG_LONG
1134 # undef XXH_NO_LONG_LONG /* don't actually */
1136 * @brief Controls how unaligned memory is accessed.
1138 * By default, access to unaligned memory is controlled by `memcpy()`, which is
1139 * safe and portable.
1141 * Unfortunately, on some target/compiler combinations, the generated assembly
1144 * The below switch allow selection of a different access method
1145 * in the search for improved performance.
1147 * @par Possible options:
1149 * - `XXH_FORCE_MEMORY_ACCESS=0` (default): `memcpy`
1151 * Use `memcpy()`. Safe and portable. Note that most modern compilers will
1152 * eliminate the function call and treat it as an unaligned access.
1154 * - `XXH_FORCE_MEMORY_ACCESS=1`: `__attribute__((packed))`
1156 * Depends on compiler extensions and is therefore not portable.
1157 * This method is safe _if_ your compiler supports it,
1158 * and *generally* as fast or faster than `memcpy`.
1160 * - `XXH_FORCE_MEMORY_ACCESS=2`: Direct cast
1162 * Casts directly and dereferences. This method doesn't depend on the
1163 * compiler, but it violates the C standard as it directly dereferences an
1164 * unaligned pointer. It can generate buggy code on targets which do not
1165 * support unaligned memory accesses, but in some circumstances, it's the
1166 * only known way to get the most performance.
1168 * - `XXH_FORCE_MEMORY_ACCESS=3`: Byteshift
1170 * Also portable. This can generate the best code on old compilers which don't
1171 * inline small `memcpy()` calls, and it might also be faster on big-endian
1172 * systems which lack a native byteswap instruction. However, some compilers
1173 * will emit literal byteshifts even if the target supports unaligned access.
1177 * Methods 1 and 2 rely on implementation-defined behavior. Use these with
1178 * care, as what works on one compiler/platform/optimization level may cause
1179 * another to read garbage data or even crash.
1181 * See https://stackoverflow.com/a/32095106/646947 for details.
1183 * Prefer these methods in priority order (0 > 3 > 1 > 2)
1185 # define XXH_FORCE_MEMORY_ACCESS 0
1187 * @def XXH_ACCEPT_NULL_INPUT_POINTER
1188 * @brief Whether to add explicit `NULL` checks.
1190 * If the input pointer is `NULL` and the length is non-zero, xxHash's default
1191 * behavior is to dereference it, triggering a segfault.
1193 * When this macro is enabled, xxHash actively checks the input for a null pointer.
1194 * If it is, the result for null input pointers is the same as a zero-length input.
1196 # define XXH_ACCEPT_NULL_INPUT_POINTER 0
1198 * @def XXH_FORCE_ALIGN_CHECK
1199 * @brief If defined to non-zero, adds a special path for aligned inputs (XXH32()
1200 * and XXH64() only).
1202 * This is an important performance trick for architectures without decent
1203 * unaligned memory access performance.
1205 * It checks for input alignment, and when conditions are met, uses a "fast
1206 * path" employing direct 32-bit/64-bit reads, resulting in _dramatically
1207 * faster_ read speed.
1209 * The check costs one initial branch per hash, which is generally negligible,
1212 * Moreover, it's not useful to generate an additional code path if memory
1213 * access uses the same instruction for both aligned and unaligned
1214 * addresses (e.g. x86 and aarch64).
1216 * In these cases, the alignment check can be removed by setting this macro to 0.
1217 * Then the code will always use unaligned memory access.
1218 * Align check is automatically disabled on x86, x64 & arm64,
1219 * which are platforms known to offer good unaligned memory accesses performance.
1221 * This option does not affect XXH3 (only XXH32 and XXH64).
1223 # define XXH_FORCE_ALIGN_CHECK 0
1226 * @def XXH_NO_INLINE_HINTS
1227 * @brief When non-zero, sets all functions to `static`.
1229 * By default, xxHash tries to force the compiler to inline almost all internal
1232 * This can usually improve performance due to reduced jumping and improved
1233 * constant folding, but significantly increases the size of the binary which
1234 * might not be favorable.
1236 * Additionally, sometimes the forced inlining can be detrimental to performance,
1237 * depending on the architecture.
1239 * XXH_NO_INLINE_HINTS marks all internal functions as static, giving the
1240 * compiler full control on whether to inline or not.
1242 * When not optimizing (-O0), optimizing for size (-Os, -Oz), or using
1243 * -fno-inline with GCC or Clang, this will automatically be defined.
1245 # define XXH_NO_INLINE_HINTS 0
1249 * @brief Whether to reroll `XXH32_finalize` and `XXH64_finalize`.
1251 * For performance, `XXH32_finalize` and `XXH64_finalize` use an unrolled loop
1252 * in the form of a switch statement.
1254 * This is not always desirable, as it generates larger code, and depending on
1255 * the architecture, may even be slower
1257 * This is automatically defined with `-Os`/`-Oz` on GCC and Clang.
1259 # define XXH_REROLL 0
1263 * @brief Redefines old internal names.
1265 * For compatibility with code that uses xxHash's internals before the names
1266 * were changed to improve namespacing. There is no other reason to use this.
1268 # define XXH_OLD_NAMES
1269 # undef XXH_OLD_NAMES /* don't actually use, it is ugly. */
1270 #endif /* XXH_DOXYGEN */
1275 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
1276 /* prefer __packed__ structures (method 1) for gcc on armv7 and armv8 */
1277 # if !defined(__clang__) && ( \
1278 (defined(__INTEL_COMPILER) && !defined(_WIN32)) || \
1279 (defined(__GNUC__) && (defined(__ARM_ARCH) && __ARM_ARCH >= 7)) )
1280 # define XXH_FORCE_MEMORY_ACCESS 1
1284 #ifndef XXH_ACCEPT_NULL_INPUT_POINTER /* can be defined externally */
1285 # define XXH_ACCEPT_NULL_INPUT_POINTER 0
1288 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
1289 # if defined(__i386) || defined(__x86_64__) || defined(__aarch64__) \
1290 || defined(_M_IX86) || defined(_M_X64) || defined(_M_ARM64) /* visual */
1291 # define XXH_FORCE_ALIGN_CHECK 0
1293 # define XXH_FORCE_ALIGN_CHECK 1
1297 #ifndef XXH_NO_INLINE_HINTS
1298 # if defined(__OPTIMIZE_SIZE__) /* -Os, -Oz */ \
1299 || defined(__NO_INLINE__) /* -O0, -fno-inline */
1300 # define XXH_NO_INLINE_HINTS 1
1302 # define XXH_NO_INLINE_HINTS 0
1307 # if defined(__OPTIMIZE_SIZE__)
1308 # define XXH_REROLL 1
1310 # define XXH_REROLL 0
1315 * @defgroup impl Implementation
1320 /* *************************************
1321 * Includes & Memory related functions
1322 ***************************************/
1324 * Modify the local functions below should you wish to use
1325 * different memory routines for malloc() and free()
1331 * @brief Modify this function to use a different routine than malloc().
1333 static void* XXH_malloc(size_t s
) { return malloc(s
); }
1337 * @brief Modify this function to use a different routine than free().
1339 static void XXH_free(void* p
) { free(p
); }
1345 * @brief Modify this function to use a different routine than memcpy().
1347 static void* XXH_memcpy(void* dest
, const void* src
, size_t size
)
1349 return memcpy(dest
,src
,size
);
1352 #include <limits.h> /* ULLONG_MAX */
1355 /* *************************************
1356 * Compiler Specific Options
1357 ***************************************/
1358 #ifdef _MSC_VER /* Visual Studio warning fix */
1359 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
1362 #if XXH_NO_INLINE_HINTS /* disable inlining hints */
1363 # if defined(__GNUC__)
1364 # define XXH_FORCE_INLINE static __attribute__((unused))
1366 # define XXH_FORCE_INLINE static
1368 # define XXH_NO_INLINE static
1369 /* enable inlining hints */
1370 #elif defined(_MSC_VER) /* Visual Studio */
1371 # define XXH_FORCE_INLINE static __forceinline
1372 # define XXH_NO_INLINE static __declspec(noinline)
1373 #elif defined(__GNUC__)
1374 # define XXH_FORCE_INLINE static __inline__ __attribute__((always_inline, unused))
1375 # define XXH_NO_INLINE static __attribute__((noinline))
1376 #elif defined (__cplusplus) \
1377 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) /* C99 */
1378 # define XXH_FORCE_INLINE static inline
1379 # define XXH_NO_INLINE static
1381 # define XXH_FORCE_INLINE static
1382 # define XXH_NO_INLINE static
1387 /* *************************************
1389 ***************************************/
1392 * @def XXH_DEBUGLEVEL
1393 * @brief Sets the debugging level.
1395 * XXH_DEBUGLEVEL is expected to be defined externally, typically via the
1396 * compiler's command line options. The value must be a number.
1398 #ifndef XXH_DEBUGLEVEL
1399 # ifdef DEBUGLEVEL /* backwards compat */
1400 # define XXH_DEBUGLEVEL DEBUGLEVEL
1402 # define XXH_DEBUGLEVEL 0
1406 #if (XXH_DEBUGLEVEL>=1)
1407 # include <assert.h> /* note: can still be disabled with NDEBUG */
1408 # define XXH_ASSERT(c) assert(c)
1410 # define XXH_ASSERT(c) ((void)0)
1413 /* note: use after variable declarations */
1414 #define XXH_STATIC_ASSERT(c) do { enum { XXH_sa = 1/(int)(!!(c)) }; } while (0)
1418 * @def XXH_COMPILER_GUARD(var)
1419 * @brief Used to prevent unwanted optimizations for @p var.
1421 * It uses an empty GCC inline assembly statement with a register constraint
1422 * which forces @p var into a general purpose register (eg eax, ebx, ecx
1423 * on x86) and marks it as modified.
1425 * This is used in a few places to avoid unwanted autovectorization (e.g.
1426 * XXH32_round()). All vectorization we want is explicit via intrinsics,
1427 * and _usually_ isn't wanted elsewhere.
1429 * We also use it to prevent unwanted constant folding for AArch64 in
1430 * XXH3_initCustomSecret_scalar().
1433 # define XXH_COMPILER_GUARD(var) __asm__ __volatile__("" : "+r" (var))
1435 # define XXH_COMPILER_GUARD(var) ((void)0)
1438 /* *************************************
1440 ***************************************/
1441 #if !defined (__VMS) \
1442 && (defined (__cplusplus) \
1443 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
1444 # include <stdint.h>
1445 typedef uint8_t xxh_u8
;
1447 typedef unsigned char xxh_u8
;
1449 typedef XXH32_hash_t xxh_u32
;
1451 #ifdef XXH_OLD_NAMES
1452 # define BYTE xxh_u8
1454 # define U32 xxh_u32
1457 /* *** Memory access *** */
1461 * @fn xxh_u32 XXH_read32(const void* ptr)
1462 * @brief Reads an unaligned 32-bit integer from @p ptr in native endianness.
1464 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1466 * @param ptr The pointer to read from.
1467 * @return The 32-bit native endian integer from the bytes at @p ptr.
1472 * @fn xxh_u32 XXH_readLE32(const void* ptr)
1473 * @brief Reads an unaligned 32-bit little endian integer from @p ptr.
1475 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1477 * @param ptr The pointer to read from.
1478 * @return The 32-bit little endian integer from the bytes at @p ptr.
1483 * @fn xxh_u32 XXH_readBE32(const void* ptr)
1484 * @brief Reads an unaligned 32-bit big endian integer from @p ptr.
1486 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1488 * @param ptr The pointer to read from.
1489 * @return The 32-bit big endian integer from the bytes at @p ptr.
1494 * @fn xxh_u32 XXH_readLE32_align(const void* ptr, XXH_alignment align)
1495 * @brief Like @ref XXH_readLE32(), but has an option for aligned reads.
1497 * Affected by @ref XXH_FORCE_MEMORY_ACCESS.
1498 * Note that when @ref XXH_FORCE_ALIGN_CHECK == 0, the @p align parameter is
1499 * always @ref XXH_alignment::XXH_unaligned.
1501 * @param ptr The pointer to read from.
1502 * @param align Whether @p ptr is aligned.
1504 * If @p align == @ref XXH_alignment::XXH_aligned, @p ptr must be 4 byte
1506 * @return The 32-bit little endian integer from the bytes at @p ptr.
1509 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
1511 * Manual byteshift. Best for old compilers which don't inline memcpy.
1512 * We actually directly use XXH_readLE32 and XXH_readBE32.
1514 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
1517 * Force direct memory access. Only works on CPU which support unaligned memory
1518 * access in hardware.
1520 static xxh_u32
XXH_read32(const void* memPtr
) { return *(const xxh_u32
*) memPtr
; }
1522 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
1525 * __pack instructions are safer but compiler specific, hence potentially
1526 * problematic for some compilers.
1528 * Currently only defined for GCC and ICC.
1530 #ifdef XXH_OLD_NAMES
1531 typedef union { xxh_u32 u32
; } __attribute__((packed
)) unalign
;
1533 static xxh_u32
XXH_read32(const void* ptr
)
1535 typedef union { xxh_u32 u32
; } __attribute__((packed
)) xxh_unalign
;
1536 return ((const xxh_unalign
*)ptr
)->u32
;
1542 * Portable and safe solution. Generally efficient.
1543 * see: https://stackoverflow.com/a/32095106/646947
1545 static xxh_u32
XXH_read32(const void* memPtr
)
1548 memcpy(&val
, memPtr
, sizeof(val
));
1552 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
1555 /* *** Endianness *** */
1558 * @def XXH_CPU_LITTLE_ENDIAN
1559 * @brief Whether the target is little endian.
1561 * Defined to 1 if the target is little endian, or 0 if it is big endian.
1562 * It can be defined externally, for example on the compiler command line.
1564 * If it is not defined, a runtime check (which is usually constant folded)
1568 * This is not necessarily defined to an integer constant.
1570 * @see XXH_isLittleEndian() for the runtime check.
1572 #ifndef XXH_CPU_LITTLE_ENDIAN
1574 * Try to detect endianness automatically, to avoid the nonstandard behavior
1575 * in `XXH_isLittleEndian()`
1577 # if defined(_WIN32) /* Windows is always little endian */ \
1578 || defined(__LITTLE_ENDIAN__) \
1579 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
1580 # define XXH_CPU_LITTLE_ENDIAN 1
1581 # elif defined(__BIG_ENDIAN__) \
1582 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
1583 # define XXH_CPU_LITTLE_ENDIAN 0
1587 * @brief Runtime check for @ref XXH_CPU_LITTLE_ENDIAN.
1589 * Most compilers will constant fold this.
1591 static int XXH_isLittleEndian(void)
1594 * Portable and well-defined behavior.
1595 * Don't use static: it is detrimental to performance.
1597 const union { xxh_u32 u
; xxh_u8 c
[4]; } one
= { 1 };
1600 # define XXH_CPU_LITTLE_ENDIAN XXH_isLittleEndian()
1607 /* ****************************************
1608 * Compiler-specific Functions and Macros
1609 ******************************************/
1610 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
1612 #ifdef __has_builtin
1613 # define XXH_HAS_BUILTIN(x) __has_builtin(x)
1615 # define XXH_HAS_BUILTIN(x) 0
1620 * @def XXH_rotl32(x,r)
1621 * @brief 32-bit rotate left.
1623 * @param x The 32-bit integer to be rotated.
1624 * @param r The number of bits to rotate.
1626 * @p r > 0 && @p r < 32
1628 * @p x and @p r may be evaluated multiple times.
1629 * @return The rotated result.
1631 #if !defined(NO_CLANG_BUILTIN) && XXH_HAS_BUILTIN(__builtin_rotateleft32) \
1632 && XXH_HAS_BUILTIN(__builtin_rotateleft64)
1633 # define XXH_rotl32 __builtin_rotateleft32
1634 # define XXH_rotl64 __builtin_rotateleft64
1635 /* Note: although _rotl exists for minGW (GCC under windows), performance seems poor */
1636 #elif defined(_MSC_VER)
1637 # define XXH_rotl32(x,r) _rotl(x,r)
1638 # define XXH_rotl64(x,r) _rotl64(x,r)
1640 # define XXH_rotl32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
1641 # define XXH_rotl64(x,r) (((x) << (r)) | ((x) >> (64 - (r))))
1646 * @fn xxh_u32 XXH_swap32(xxh_u32 x)
1647 * @brief A 32-bit byteswap.
1649 * @param x The 32-bit integer to byteswap.
1650 * @return @p x, byteswapped.
1652 #if defined(_MSC_VER) /* Visual Studio */
1653 # define XXH_swap32 _byteswap_ulong
1654 #elif XXH_GCC_VERSION >= 403
1655 # define XXH_swap32 __builtin_bswap32
1657 static xxh_u32
XXH_swap32 (xxh_u32 x
)
1659 return ((x
<< 24) & 0xff000000 ) |
1660 ((x
<< 8) & 0x00ff0000 ) |
1661 ((x
>> 8) & 0x0000ff00 ) |
1662 ((x
>> 24) & 0x000000ff );
1667 /* ***************************
1669 *****************************/
1673 * @brief Enum to indicate whether a pointer is aligned.
1676 XXH_aligned
, /*!< Aligned */
1677 XXH_unaligned
/*!< Possibly unaligned */
1681 * XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load.
1683 * This is ideal for older compilers which don't inline memcpy.
1685 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
1687 XXH_FORCE_INLINE xxh_u32
XXH_readLE32(const void* memPtr
)
1689 const xxh_u8
* bytePtr
= (const xxh_u8
*)memPtr
;
1691 | ((xxh_u32
)bytePtr
[1] << 8)
1692 | ((xxh_u32
)bytePtr
[2] << 16)
1693 | ((xxh_u32
)bytePtr
[3] << 24);
1696 XXH_FORCE_INLINE xxh_u32
XXH_readBE32(const void* memPtr
)
1698 const xxh_u8
* bytePtr
= (const xxh_u8
*)memPtr
;
1700 | ((xxh_u32
)bytePtr
[2] << 8)
1701 | ((xxh_u32
)bytePtr
[1] << 16)
1702 | ((xxh_u32
)bytePtr
[0] << 24);
1706 XXH_FORCE_INLINE xxh_u32
XXH_readLE32(const void* ptr
)
1708 return XXH_CPU_LITTLE_ENDIAN
? XXH_read32(ptr
) : XXH_swap32(XXH_read32(ptr
));
1711 static xxh_u32
XXH_readBE32(const void* ptr
)
1713 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap32(XXH_read32(ptr
)) : XXH_read32(ptr
);
1717 XXH_FORCE_INLINE xxh_u32
1718 XXH_readLE32_align(const void* ptr
, XXH_alignment align
)
1720 if (align
==XXH_unaligned
) {
1721 return XXH_readLE32(ptr
);
1723 return XXH_CPU_LITTLE_ENDIAN
? *(const xxh_u32
*)ptr
: XXH_swap32(*(const xxh_u32
*)ptr
);
1728 /* *************************************
1730 ***************************************/
1731 /*! @ingroup public */
1732 XXH_PUBLIC_API
unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER
; }
1735 /* *******************************************************************
1736 * 32-bit hash functions
1737 *********************************************************************/
1740 * @defgroup xxh32_impl XXH32 implementation
1744 /* #define instead of static const, to be used as initializers */
1745 #define XXH_PRIME32_1 0x9E3779B1U /*!< 0b10011110001101110111100110110001 */
1746 #define XXH_PRIME32_2 0x85EBCA77U /*!< 0b10000101111010111100101001110111 */
1747 #define XXH_PRIME32_3 0xC2B2AE3DU /*!< 0b11000010101100101010111000111101 */
1748 #define XXH_PRIME32_4 0x27D4EB2FU /*!< 0b00100111110101001110101100101111 */
1749 #define XXH_PRIME32_5 0x165667B1U /*!< 0b00010110010101100110011110110001 */
1751 #ifdef XXH_OLD_NAMES
1752 # define PRIME32_1 XXH_PRIME32_1
1753 # define PRIME32_2 XXH_PRIME32_2
1754 # define PRIME32_3 XXH_PRIME32_3
1755 # define PRIME32_4 XXH_PRIME32_4
1756 # define PRIME32_5 XXH_PRIME32_5
1761 * @brief Normal stripe processing routine.
1763 * This shuffles the bits so that any bit from @p input impacts several bits in
1766 * @param acc The accumulator lane.
1767 * @param input The stripe of input to mix.
1768 * @return The mixed accumulator lane.
1770 static xxh_u32
XXH32_round(xxh_u32 acc
, xxh_u32 input
)
1772 acc
+= input
* XXH_PRIME32_2
;
1773 acc
= XXH_rotl32(acc
, 13);
1774 acc
*= XXH_PRIME32_1
;
1775 #if (defined(__SSE4_1__) || defined(__aarch64__)) && !defined(XXH_ENABLE_AUTOVECTORIZE)
1778 * A compiler fence is the only thing that prevents GCC and Clang from
1779 * autovectorizing the XXH32 loop (pragmas and attributes don't work for some
1780 * reason) without globally disabling SSE4.1.
1782 * The reason we want to avoid vectorization is because despite working on
1783 * 4 integers at a time, there are multiple factors slowing XXH32 down on
1785 * - There's a ridiculous amount of lag from pmulld (10 cycles of latency on
1786 * newer chips!) making it slightly slower to multiply four integers at
1787 * once compared to four integers independently. Even when pmulld was
1788 * fastest, Sandy/Ivy Bridge, it is still not worth it to go into SSE
1789 * just to multiply unless doing a long operation.
1791 * - Four instructions are required to rotate,
1792 * movqda tmp, v // not required with VEX encoding
1793 * pslld tmp, 13 // tmp <<= 13
1794 * psrld v, 19 // x >>= 19
1795 * por v, tmp // x |= tmp
1796 * compared to one for scalar:
1797 * roll v, 13 // reliably fast across the board
1798 * shldl v, v, 13 // Sandy Bridge and later prefer this for some reason
1800 * - Instruction level parallelism is actually more beneficial here because
1801 * the SIMD actually serializes this operation: While v1 is rotating, v2
1802 * can load data, while v3 can multiply. SSE forces them to operate
1805 * This is also enabled on AArch64, as Clang autovectorizes it incorrectly
1806 * and it is pointless writing a NEON implementation that is basically the
1807 * same speed as scalar for XXH32.
1809 XXH_COMPILER_GUARD(acc
);
1816 * @brief Mixes all bits to finalize the hash.
1818 * The final mix ensures that all input bits have a chance to impact any bit in
1819 * the output digest, resulting in an unbiased distribution.
1821 * @param h32 The hash to avalanche.
1822 * @return The avalanched hash.
1824 static xxh_u32
XXH32_avalanche(xxh_u32 h32
)
1827 h32
*= XXH_PRIME32_2
;
1829 h32
*= XXH_PRIME32_3
;
1834 #define XXH_get32bits(p) XXH_readLE32_align(p, align)
1838 * @brief Processes the last 0-15 bytes of @p ptr.
1840 * There may be up to 15 bytes remaining to consume from the input.
1841 * This final stage will digest them to ensure that all input bytes are present
1844 * @param h32 The hash to finalize.
1845 * @param ptr The pointer to the remaining input.
1846 * @param len The remaining length, modulo 16.
1847 * @param align Whether @p ptr is aligned.
1848 * @return The finalized hash.
1851 XXH32_finalize(xxh_u32 h32
, const xxh_u8
* ptr
, size_t len
, XXH_alignment align
)
1853 #define XXH_PROCESS1 do { \
1854 h32 += (*ptr++) * XXH_PRIME32_5; \
1855 h32 = XXH_rotl32(h32, 11) * XXH_PRIME32_1; \
1858 #define XXH_PROCESS4 do { \
1859 h32 += XXH_get32bits(ptr) * XXH_PRIME32_3; \
1861 h32 = XXH_rotl32(h32, 17) * XXH_PRIME32_4; \
1864 /* Compact rerolled version */
1875 return XXH32_avalanche(h32
);
1877 switch(len
&15) /* or switch(bEnd - p) */ {
1878 case 12: XXH_PROCESS4
;
1879 FALLTHROUGH_INTENDED
;
1880 case 8: XXH_PROCESS4
;
1881 FALLTHROUGH_INTENDED
;
1882 case 4: XXH_PROCESS4
;
1883 return XXH32_avalanche(h32
);
1885 case 13: XXH_PROCESS4
;
1886 FALLTHROUGH_INTENDED
;
1887 case 9: XXH_PROCESS4
;
1888 FALLTHROUGH_INTENDED
;
1889 case 5: XXH_PROCESS4
;
1891 return XXH32_avalanche(h32
);
1893 case 14: XXH_PROCESS4
;
1894 FALLTHROUGH_INTENDED
;
1895 case 10: XXH_PROCESS4
;
1896 FALLTHROUGH_INTENDED
;
1897 case 6: XXH_PROCESS4
;
1900 return XXH32_avalanche(h32
);
1902 case 15: XXH_PROCESS4
;
1903 FALLTHROUGH_INTENDED
;
1904 case 11: XXH_PROCESS4
;
1905 FALLTHROUGH_INTENDED
;
1906 case 7: XXH_PROCESS4
;
1907 FALLTHROUGH_INTENDED
;
1908 case 3: XXH_PROCESS1
;
1909 FALLTHROUGH_INTENDED
;
1910 case 2: XXH_PROCESS1
;
1911 FALLTHROUGH_INTENDED
;
1912 case 1: XXH_PROCESS1
;
1913 FALLTHROUGH_INTENDED
;
1914 case 0: return XXH32_avalanche(h32
);
1917 return h32
; /* reaching this point is deemed impossible */
1921 #ifdef XXH_OLD_NAMES
1922 # define PROCESS1 XXH_PROCESS1
1923 # define PROCESS4 XXH_PROCESS4
1925 # undef XXH_PROCESS1
1926 # undef XXH_PROCESS4
1931 * @brief The implementation for @ref XXH32().
1933 * @param input, len, seed Directly passed from @ref XXH32().
1934 * @param align Whether @p input is aligned.
1935 * @return The calculated hash.
1937 XXH_FORCE_INLINE xxh_u32
1938 XXH32_endian_align(const xxh_u8
* input
, size_t len
, xxh_u32 seed
, XXH_alignment align
)
1940 const xxh_u8
* bEnd
= input
? input
+ len
: NULL
;
1943 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
1946 bEnd
=input
=(const xxh_u8
*)(size_t)16;
1951 const xxh_u8
* const limit
= bEnd
- 15;
1952 xxh_u32 v1
= seed
+ XXH_PRIME32_1
+ XXH_PRIME32_2
;
1953 xxh_u32 v2
= seed
+ XXH_PRIME32_2
;
1954 xxh_u32 v3
= seed
+ 0;
1955 xxh_u32 v4
= seed
- XXH_PRIME32_1
;
1958 v1
= XXH32_round(v1
, XXH_get32bits(input
)); input
+= 4;
1959 v2
= XXH32_round(v2
, XXH_get32bits(input
)); input
+= 4;
1960 v3
= XXH32_round(v3
, XXH_get32bits(input
)); input
+= 4;
1961 v4
= XXH32_round(v4
, XXH_get32bits(input
)); input
+= 4;
1962 } while (input
< limit
);
1964 h32
= XXH_rotl32(v1
, 1) + XXH_rotl32(v2
, 7)
1965 + XXH_rotl32(v3
, 12) + XXH_rotl32(v4
, 18);
1967 h32
= seed
+ XXH_PRIME32_5
;
1970 h32
+= (xxh_u32
)len
;
1972 return XXH32_finalize(h32
, input
, len
&15, align
);
1975 /*! @ingroup xxh32_family */
1976 XXH_PUBLIC_API XXH32_hash_t
XXH32 (const void* input
, size_t len
, XXH32_hash_t seed
)
1979 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
1980 XXH32_state_t state
;
1981 XXH32_reset(&state
, seed
);
1982 XXH32_update(&state
, (const xxh_u8
*)input
, len
);
1983 return XXH32_digest(&state
);
1985 if (XXH_FORCE_ALIGN_CHECK
) {
1986 if ((((size_t)input
) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
1987 return XXH32_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_aligned
);
1990 return XXH32_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_unaligned
);
1996 /******* Hash streaming *******/
1998 * @ingroup xxh32_family
2000 XXH_PUBLIC_API XXH32_state_t
* XXH32_createState(void)
2002 return (XXH32_state_t
*)XXH_malloc(sizeof(XXH32_state_t
));
2004 /*! @ingroup xxh32_family */
2005 XXH_PUBLIC_API XXH_errorcode
XXH32_freeState(XXH32_state_t
* statePtr
)
2011 /*! @ingroup xxh32_family */
2012 XXH_PUBLIC_API
void XXH32_copyState(XXH32_state_t
* dstState
, const XXH32_state_t
* srcState
)
2014 memcpy(dstState
, srcState
, sizeof(*dstState
));
2017 /*! @ingroup xxh32_family */
2018 XXH_PUBLIC_API XXH_errorcode
XXH32_reset(XXH32_state_t
* statePtr
, XXH32_hash_t seed
)
2020 XXH32_state_t state
; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
2021 memset(&state
, 0, sizeof(state
));
2022 state
.v1
= seed
+ XXH_PRIME32_1
+ XXH_PRIME32_2
;
2023 state
.v2
= seed
+ XXH_PRIME32_2
;
2024 state
.v3
= seed
+ 0;
2025 state
.v4
= seed
- XXH_PRIME32_1
;
2026 /* do not write into reserved, planned to be removed in a future version */
2027 memcpy(statePtr
, &state
, sizeof(state
) - sizeof(state
.reserved
));
2032 /*! @ingroup xxh32_family */
2033 XXH_PUBLIC_API XXH_errorcode
2034 XXH32_update(XXH32_state_t
* state
, const void* input
, size_t len
)
2037 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
2043 { const xxh_u8
* p
= (const xxh_u8
*)input
;
2044 const xxh_u8
* const bEnd
= p
+ len
;
2046 state
->total_len_32
+= (XXH32_hash_t
)len
;
2047 state
->large_len
|= (XXH32_hash_t
)((len
>=16) | (state
->total_len_32
>=16));
2049 if (state
->memsize
+ len
< 16) { /* fill in tmp buffer */
2050 XXH_memcpy((xxh_u8
*)(state
->mem32
) + state
->memsize
, input
, len
);
2051 state
->memsize
+= (XXH32_hash_t
)len
;
2055 if (state
->memsize
) { /* some data left from previous update */
2056 XXH_memcpy((xxh_u8
*)(state
->mem32
) + state
->memsize
, input
, 16-state
->memsize
);
2057 { const xxh_u32
* p32
= state
->mem32
;
2058 state
->v1
= XXH32_round(state
->v1
, XXH_readLE32(p32
)); p32
++;
2059 state
->v2
= XXH32_round(state
->v2
, XXH_readLE32(p32
)); p32
++;
2060 state
->v3
= XXH32_round(state
->v3
, XXH_readLE32(p32
)); p32
++;
2061 state
->v4
= XXH32_round(state
->v4
, XXH_readLE32(p32
));
2063 p
+= 16-state
->memsize
;
2067 /* uintptr_t casts avoid UB or compiler warning on out-of-bounds
2068 * pointer arithmetic */
2069 if ((uintptr_t)p
<= (uintptr_t)bEnd
- 16) {
2070 const uintptr_t limit
= (uintptr_t)bEnd
- 16;
2071 xxh_u32 v1
= state
->v1
;
2072 xxh_u32 v2
= state
->v2
;
2073 xxh_u32 v3
= state
->v3
;
2074 xxh_u32 v4
= state
->v4
;
2077 v1
= XXH32_round(v1
, XXH_readLE32(p
)); p
+=4;
2078 v2
= XXH32_round(v2
, XXH_readLE32(p
)); p
+=4;
2079 v3
= XXH32_round(v3
, XXH_readLE32(p
)); p
+=4;
2080 v4
= XXH32_round(v4
, XXH_readLE32(p
)); p
+=4;
2081 } while ((uintptr_t)p
<=limit
);
2090 XXH_memcpy(state
->mem32
, p
, (size_t)(bEnd
-p
));
2091 state
->memsize
= (unsigned)(bEnd
-p
);
2099 /*! @ingroup xxh32_family */
2100 XXH_PUBLIC_API XXH32_hash_t
XXH32_digest(const XXH32_state_t
* state
)
2104 if (state
->large_len
) {
2105 h32
= XXH_rotl32(state
->v1
, 1)
2106 + XXH_rotl32(state
->v2
, 7)
2107 + XXH_rotl32(state
->v3
, 12)
2108 + XXH_rotl32(state
->v4
, 18);
2110 h32
= state
->v3
/* == seed */ + XXH_PRIME32_5
;
2113 h32
+= state
->total_len_32
;
2115 return XXH32_finalize(h32
, (const xxh_u8
*)state
->mem32
, state
->memsize
, XXH_aligned
);
2119 /******* Canonical representation *******/
2122 * @ingroup xxh32_family
2123 * The default return values from XXH functions are unsigned 32 and 64 bit
2126 * The canonical representation uses big endian convention, the same convention
2127 * as human-readable numbers (large digits first).
2129 * This way, hash values can be written into a file or buffer, remaining
2130 * comparable across different systems.
2132 * The following functions allow transformation of hash values to and from their
2135 XXH_PUBLIC_API
void XXH32_canonicalFromHash(XXH32_canonical_t
* dst
, XXH32_hash_t hash
)
2137 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t
) == sizeof(XXH32_hash_t
));
2138 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap32(hash
);
2139 memcpy(dst
, &hash
, sizeof(*dst
));
2141 /*! @ingroup xxh32_family */
2142 XXH_PUBLIC_API XXH32_hash_t
XXH32_hashFromCanonical(const XXH32_canonical_t
* src
)
2144 return XXH_readBE32(src
);
2148 #ifndef XXH_NO_LONG_LONG
2150 /* *******************************************************************
2151 * 64-bit hash functions
2152 *********************************************************************/
2158 /******* Memory access *******/
2160 typedef XXH64_hash_t xxh_u64
;
2162 #ifdef XXH_OLD_NAMES
2163 # define U64 xxh_u64
2166 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
2168 * Manual byteshift. Best for old compilers which don't inline memcpy.
2169 * We actually directly use XXH_readLE64 and XXH_readBE64.
2171 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
2173 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
2174 static xxh_u64
XXH_read64(const void* memPtr
)
2176 return *(const xxh_u64
*) memPtr
;
2179 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
2182 * __pack instructions are safer, but compiler specific, hence potentially
2183 * problematic for some compilers.
2185 * Currently only defined for GCC and ICC.
2187 #ifdef XXH_OLD_NAMES
2188 typedef union { xxh_u32 u32
; xxh_u64 u64
; } __attribute__((packed
)) unalign64
;
2190 static xxh_u64
XXH_read64(const void* ptr
)
2192 typedef union { xxh_u32 u32
; xxh_u64 u64
; } __attribute__((packed
)) xxh_unalign64
;
2193 return ((const xxh_unalign64
*)ptr
)->u64
;
2199 * Portable and safe solution. Generally efficient.
2200 * see: https://stackoverflow.com/a/32095106/646947
2202 static xxh_u64
XXH_read64(const void* memPtr
)
2205 memcpy(&val
, memPtr
, sizeof(val
));
2209 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
2211 #if defined(_MSC_VER) /* Visual Studio */
2212 # define XXH_swap64 _byteswap_uint64
2213 #elif XXH_GCC_VERSION >= 403
2214 # define XXH_swap64 __builtin_bswap64
2216 static xxh_u64
XXH_swap64(xxh_u64 x
)
2218 return ((x
<< 56) & 0xff00000000000000ULL
) |
2219 ((x
<< 40) & 0x00ff000000000000ULL
) |
2220 ((x
<< 24) & 0x0000ff0000000000ULL
) |
2221 ((x
<< 8) & 0x000000ff00000000ULL
) |
2222 ((x
>> 8) & 0x00000000ff000000ULL
) |
2223 ((x
>> 24) & 0x0000000000ff0000ULL
) |
2224 ((x
>> 40) & 0x000000000000ff00ULL
) |
2225 ((x
>> 56) & 0x00000000000000ffULL
);
2230 /* XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load. */
2231 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3))
2233 XXH_FORCE_INLINE xxh_u64
XXH_readLE64(const void* memPtr
)
2235 const xxh_u8
* bytePtr
= (const xxh_u8
*)memPtr
;
2237 | ((xxh_u64
)bytePtr
[1] << 8)
2238 | ((xxh_u64
)bytePtr
[2] << 16)
2239 | ((xxh_u64
)bytePtr
[3] << 24)
2240 | ((xxh_u64
)bytePtr
[4] << 32)
2241 | ((xxh_u64
)bytePtr
[5] << 40)
2242 | ((xxh_u64
)bytePtr
[6] << 48)
2243 | ((xxh_u64
)bytePtr
[7] << 56);
2246 XXH_FORCE_INLINE xxh_u64
XXH_readBE64(const void* memPtr
)
2248 const xxh_u8
* bytePtr
= (const xxh_u8
*)memPtr
;
2250 | ((xxh_u64
)bytePtr
[6] << 8)
2251 | ((xxh_u64
)bytePtr
[5] << 16)
2252 | ((xxh_u64
)bytePtr
[4] << 24)
2253 | ((xxh_u64
)bytePtr
[3] << 32)
2254 | ((xxh_u64
)bytePtr
[2] << 40)
2255 | ((xxh_u64
)bytePtr
[1] << 48)
2256 | ((xxh_u64
)bytePtr
[0] << 56);
2260 XXH_FORCE_INLINE xxh_u64
XXH_readLE64(const void* ptr
)
2262 return XXH_CPU_LITTLE_ENDIAN
? XXH_read64(ptr
) : XXH_swap64(XXH_read64(ptr
));
2265 static xxh_u64
XXH_readBE64(const void* ptr
)
2267 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap64(XXH_read64(ptr
)) : XXH_read64(ptr
);
2271 XXH_FORCE_INLINE xxh_u64
2272 XXH_readLE64_align(const void* ptr
, XXH_alignment align
)
2274 if (align
==XXH_unaligned
)
2275 return XXH_readLE64(ptr
);
2277 return XXH_CPU_LITTLE_ENDIAN
? *(const xxh_u64
*)ptr
: XXH_swap64(*(const xxh_u64
*)ptr
);
2281 /******* xxh64 *******/
2284 * @defgroup xxh64_impl XXH64 implementation
2288 /* #define rather that static const, to be used as initializers */
2289 #define XXH_PRIME64_1 0x9E3779B185EBCA87ULL /*!< 0b1001111000110111011110011011000110000101111010111100101010000111 */
2290 #define XXH_PRIME64_2 0xC2B2AE3D27D4EB4FULL /*!< 0b1100001010110010101011100011110100100111110101001110101101001111 */
2291 #define XXH_PRIME64_3 0x165667B19E3779F9ULL /*!< 0b0001011001010110011001111011000110011110001101110111100111111001 */
2292 #define XXH_PRIME64_4 0x85EBCA77C2B2AE63ULL /*!< 0b1000010111101011110010100111011111000010101100101010111001100011 */
2293 #define XXH_PRIME64_5 0x27D4EB2F165667C5ULL /*!< 0b0010011111010100111010110010111100010110010101100110011111000101 */
2295 #ifdef XXH_OLD_NAMES
2296 # define PRIME64_1 XXH_PRIME64_1
2297 # define PRIME64_2 XXH_PRIME64_2
2298 # define PRIME64_3 XXH_PRIME64_3
2299 # define PRIME64_4 XXH_PRIME64_4
2300 # define PRIME64_5 XXH_PRIME64_5
2303 static xxh_u64
XXH64_round(xxh_u64 acc
, xxh_u64 input
)
2305 acc
+= input
* XXH_PRIME64_2
;
2306 acc
= XXH_rotl64(acc
, 31);
2307 acc
*= XXH_PRIME64_1
;
2311 static xxh_u64
XXH64_mergeRound(xxh_u64 acc
, xxh_u64 val
)
2313 val
= XXH64_round(0, val
);
2315 acc
= acc
* XXH_PRIME64_1
+ XXH_PRIME64_4
;
2319 static xxh_u64
XXH64_avalanche(xxh_u64 h64
)
2322 h64
*= XXH_PRIME64_2
;
2324 h64
*= XXH_PRIME64_3
;
2330 #define XXH_get64bits(p) XXH_readLE64_align(p, align)
2333 XXH64_finalize(xxh_u64 h64
, const xxh_u8
* ptr
, size_t len
, XXH_alignment align
)
2337 xxh_u64
const k1
= XXH64_round(0, XXH_get64bits(ptr
));
2340 h64
= XXH_rotl64(h64
,27) * XXH_PRIME64_1
+ XXH_PRIME64_4
;
2344 h64
^= (xxh_u64
)(XXH_get32bits(ptr
)) * XXH_PRIME64_1
;
2346 h64
= XXH_rotl64(h64
, 23) * XXH_PRIME64_2
+ XXH_PRIME64_3
;
2350 h64
^= (*ptr
++) * XXH_PRIME64_5
;
2351 h64
= XXH_rotl64(h64
, 11) * XXH_PRIME64_1
;
2354 return XXH64_avalanche(h64
);
2357 #ifdef XXH_OLD_NAMES
2358 # define PROCESS1_64 XXH_PROCESS1_64
2359 # define PROCESS4_64 XXH_PROCESS4_64
2360 # define PROCESS8_64 XXH_PROCESS8_64
2362 # undef XXH_PROCESS1_64
2363 # undef XXH_PROCESS4_64
2364 # undef XXH_PROCESS8_64
2367 XXH_FORCE_INLINE xxh_u64
2368 XXH64_endian_align(const xxh_u8
* input
, size_t len
, xxh_u64 seed
, XXH_alignment align
)
2370 const xxh_u8
* bEnd
= input
? input
+ len
: NULL
;
2373 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
2376 bEnd
=input
=(const xxh_u8
*)(size_t)32;
2381 const xxh_u8
* const limit
= bEnd
- 32;
2382 xxh_u64 v1
= seed
+ XXH_PRIME64_1
+ XXH_PRIME64_2
;
2383 xxh_u64 v2
= seed
+ XXH_PRIME64_2
;
2384 xxh_u64 v3
= seed
+ 0;
2385 xxh_u64 v4
= seed
- XXH_PRIME64_1
;
2388 v1
= XXH64_round(v1
, XXH_get64bits(input
)); input
+=8;
2389 v2
= XXH64_round(v2
, XXH_get64bits(input
)); input
+=8;
2390 v3
= XXH64_round(v3
, XXH_get64bits(input
)); input
+=8;
2391 v4
= XXH64_round(v4
, XXH_get64bits(input
)); input
+=8;
2392 } while (input
<=limit
);
2394 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
2395 h64
= XXH64_mergeRound(h64
, v1
);
2396 h64
= XXH64_mergeRound(h64
, v2
);
2397 h64
= XXH64_mergeRound(h64
, v3
);
2398 h64
= XXH64_mergeRound(h64
, v4
);
2401 h64
= seed
+ XXH_PRIME64_5
;
2404 h64
+= (xxh_u64
) len
;
2406 return XXH64_finalize(h64
, input
, len
, align
);
2410 /*! @ingroup xxh64_family */
2411 XXH_PUBLIC_API XXH64_hash_t
XXH64 (const void* input
, size_t len
, XXH64_hash_t seed
)
2414 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
2415 XXH64_state_t state
;
2416 XXH64_reset(&state
, seed
);
2417 XXH64_update(&state
, (const xxh_u8
*)input
, len
);
2418 return XXH64_digest(&state
);
2420 if (XXH_FORCE_ALIGN_CHECK
) {
2421 if ((((size_t)input
) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
2422 return XXH64_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_aligned
);
2425 return XXH64_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_unaligned
);
2430 /******* Hash Streaming *******/
2432 /*! @ingroup xxh64_family*/
2433 XXH_PUBLIC_API XXH64_state_t
* XXH64_createState(void)
2435 return (XXH64_state_t
*)XXH_malloc(sizeof(XXH64_state_t
));
2437 /*! @ingroup xxh64_family */
2438 XXH_PUBLIC_API XXH_errorcode
XXH64_freeState(XXH64_state_t
* statePtr
)
2444 /*! @ingroup xxh64_family */
2445 XXH_PUBLIC_API
void XXH64_copyState(XXH64_state_t
* dstState
, const XXH64_state_t
* srcState
)
2447 memcpy(dstState
, srcState
, sizeof(*dstState
));
2450 /*! @ingroup xxh64_family */
2451 XXH_PUBLIC_API XXH_errorcode
XXH64_reset(XXH64_state_t
* statePtr
, XXH64_hash_t seed
)
2453 XXH64_state_t state
; /* use a local state to memcpy() in order to avoid strict-aliasing warnings */
2454 memset(&state
, 0, sizeof(state
));
2455 state
.v1
= seed
+ XXH_PRIME64_1
+ XXH_PRIME64_2
;
2456 state
.v2
= seed
+ XXH_PRIME64_2
;
2457 state
.v3
= seed
+ 0;
2458 state
.v4
= seed
- XXH_PRIME64_1
;
2459 /* do not write into reserved64, might be removed in a future version */
2460 memcpy(statePtr
, &state
, sizeof(state
) - sizeof(state
.reserved64
));
2464 /*! @ingroup xxh64_family */
2465 XXH_PUBLIC_API XXH_errorcode
2466 XXH64_update (XXH64_state_t
* state
, const void* input
, size_t len
)
2469 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
2475 { const xxh_u8
* p
= (const xxh_u8
*)input
;
2476 const xxh_u8
* const bEnd
= p
+ len
;
2478 state
->total_len
+= len
;
2480 if (state
->memsize
+ len
< 32) { /* fill in tmp buffer */
2481 XXH_memcpy(((xxh_u8
*)state
->mem64
) + state
->memsize
, input
, len
);
2482 state
->memsize
+= (xxh_u32
)len
;
2486 if (state
->memsize
) { /* tmp buffer is full */
2487 XXH_memcpy(((xxh_u8
*)state
->mem64
) + state
->memsize
, input
, 32-state
->memsize
);
2488 state
->v1
= XXH64_round(state
->v1
, XXH_readLE64(state
->mem64
+0));
2489 state
->v2
= XXH64_round(state
->v2
, XXH_readLE64(state
->mem64
+1));
2490 state
->v3
= XXH64_round(state
->v3
, XXH_readLE64(state
->mem64
+2));
2491 state
->v4
= XXH64_round(state
->v4
, XXH_readLE64(state
->mem64
+3));
2492 p
+= 32 - state
->memsize
;
2496 /* uintptr_t casts avoid UB or compiler warning on out-of-bounds
2497 * pointer arithmetic */
2498 if ((uintptr_t)p
+ 32 <= (uintptr_t)bEnd
) {
2499 const uintptr_t limit
= (uintptr_t)bEnd
- 32;
2500 xxh_u64 v1
= state
->v1
;
2501 xxh_u64 v2
= state
->v2
;
2502 xxh_u64 v3
= state
->v3
;
2503 xxh_u64 v4
= state
->v4
;
2506 v1
= XXH64_round(v1
, XXH_readLE64(p
)); p
+=8;
2507 v2
= XXH64_round(v2
, XXH_readLE64(p
)); p
+=8;
2508 v3
= XXH64_round(v3
, XXH_readLE64(p
)); p
+=8;
2509 v4
= XXH64_round(v4
, XXH_readLE64(p
)); p
+=8;
2510 } while ((uintptr_t)p
<=limit
);
2519 XXH_memcpy(state
->mem64
, p
, (size_t)(bEnd
-p
));
2520 state
->memsize
= (unsigned)(bEnd
-p
);
2528 /*! @ingroup xxh64_family */
2529 XXH_PUBLIC_API XXH64_hash_t
XXH64_digest(const XXH64_state_t
* state
)
2533 if (state
->total_len
>= 32) {
2534 xxh_u64
const v1
= state
->v1
;
2535 xxh_u64
const v2
= state
->v2
;
2536 xxh_u64
const v3
= state
->v3
;
2537 xxh_u64
const v4
= state
->v4
;
2539 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
2540 h64
= XXH64_mergeRound(h64
, v1
);
2541 h64
= XXH64_mergeRound(h64
, v2
);
2542 h64
= XXH64_mergeRound(h64
, v3
);
2543 h64
= XXH64_mergeRound(h64
, v4
);
2545 h64
= state
->v3
/*seed*/ + XXH_PRIME64_5
;
2548 h64
+= (xxh_u64
) state
->total_len
;
2550 return XXH64_finalize(h64
, (const xxh_u8
*)state
->mem64
, (size_t)state
->total_len
, XXH_aligned
);
2554 /******* Canonical representation *******/
2556 /*! @ingroup xxh64_family */
2557 XXH_PUBLIC_API
void XXH64_canonicalFromHash(XXH64_canonical_t
* dst
, XXH64_hash_t hash
)
2559 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t
) == sizeof(XXH64_hash_t
));
2560 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap64(hash
);
2561 memcpy(dst
, &hash
, sizeof(*dst
));
2564 /*! @ingroup xxh64_family */
2565 XXH_PUBLIC_API XXH64_hash_t
XXH64_hashFromCanonical(const XXH64_canonical_t
* src
)
2567 return XXH_readBE64(src
);
2572 /* *********************************************************************
2574 * New generation hash designed for speed on small keys and vectorization
2575 ************************************************************************ */
2578 * @defgroup xxh3_impl XXH3 implementation
2583 /* === Compiler specifics === */
2585 #if ((defined(sun) || defined(__sun)) && __cplusplus) /* Solaris includes __STDC_VERSION__ with C++. Tested with GCC 5.5 */
2586 # define XXH_RESTRICT /* disable */
2587 #elif defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* >= C99 */
2588 # define XXH_RESTRICT restrict
2590 /* Note: it might be useful to define __restrict or __restrict__ for some C++ compilers */
2591 # define XXH_RESTRICT /* disable */
2594 #if (defined(__GNUC__) && (__GNUC__ >= 3)) \
2595 || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) \
2596 || defined(__clang__)
2597 # define XXH_likely(x) __builtin_expect(x, 1)
2598 # define XXH_unlikely(x) __builtin_expect(x, 0)
2600 # define XXH_likely(x) (x)
2601 # define XXH_unlikely(x) (x)
2604 #if defined(__GNUC__)
2605 # if defined(__AVX2__)
2606 # include <immintrin.h>
2607 # elif defined(__SSE2__)
2608 # include <emmintrin.h>
2609 # elif defined(__ARM_NEON__) || defined(__ARM_NEON)
2610 # define inline __inline__ /* circumvent a clang bug */
2611 # include <arm_neon.h>
2614 #elif defined(_MSC_VER)
2615 # include <intrin.h>
2619 * One goal of XXH3 is to make it fast on both 32-bit and 64-bit, while
2620 * remaining a true 64-bit/128-bit hash function.
2622 * This is done by prioritizing a subset of 64-bit operations that can be
2623 * emulated without too many steps on the average 32-bit machine.
2625 * For example, these two lines seem similar, and run equally fast on 64-bit:
2628 * x ^= (x >> 47); // good
2629 * x ^= (x >> 13); // bad
2631 * However, to a 32-bit machine, there is a major difference.
2633 * x ^= (x >> 47) looks like this:
2635 * x.lo ^= (x.hi >> (47 - 32));
2637 * while x ^= (x >> 13) looks like this:
2639 * // note: funnel shifts are not usually cheap.
2640 * x.lo ^= (x.lo >> 13) | (x.hi << (32 - 13));
2641 * x.hi ^= (x.hi >> 13);
2643 * The first one is significantly faster than the second, simply because the
2644 * shift is larger than 32. This means:
2645 * - All the bits we need are in the upper 32 bits, so we can ignore the lower
2646 * 32 bits in the shift.
2647 * - The shift result will always fit in the lower 32 bits, and therefore,
2648 * we can ignore the upper 32 bits in the xor.
2650 * Thanks to this optimization, XXH3 only requires these features to be efficient:
2652 * - Usable unaligned access
2653 * - A 32-bit or 64-bit ALU
2654 * - If 32-bit, a decent ADC instruction
2655 * - A 32 or 64-bit multiply with a 64-bit result
2656 * - For the 128-bit variant, a decent byteswap helps short inputs.
2658 * The first two are already required by XXH32, and almost all 32-bit and 64-bit
2659 * platforms which can run XXH32 can run XXH3 efficiently.
2661 * Thumb-1, the classic 16-bit only subset of ARM's instruction set, is one
2662 * notable exception.
2664 * First of all, Thumb-1 lacks support for the UMULL instruction which
2665 * performs the important long multiply. This means numerous __aeabi_lmul
2668 * Second of all, the 8 functional registers are just not enough.
2669 * Setup for __aeabi_lmul, byteshift loads, pointers, and all arithmetic need
2670 * Lo registers, and this shuffling results in thousands more MOVs than A32.
2672 * A32 and T32 don't have this limitation. They can access all 14 registers,
2673 * do a 32->64 multiply with UMULL, and the flexible operand allowing free
2674 * shifts is helpful, too.
2676 * Therefore, we do a quick sanity check.
2678 * If compiling Thumb-1 for a target which supports ARM instructions, we will
2679 * emit a warning, as it is not a "sane" platform to compile for.
2681 * Usually, if this happens, it is because of an accident and you probably need
2682 * to specify -march, as you likely meant to compile for a newer architecture.
2684 * Credit: large sections of the vectorial and asm source code paths
2685 * have been contributed by @easyaspi314
2687 #if defined(__thumb__) && !defined(__thumb2__) && defined(__ARM_ARCH_ISA_ARM)
2688 # warning "XXH3 is highly inefficient without ARM or Thumb-2."
2691 /* ==========================================
2692 * Vectorization detection
2693 * ========================================== */
2698 * @brief Overrides the vectorization implementation chosen for XXH3.
2700 * Can be defined to 0 to disable SIMD or any of the values mentioned in
2701 * @ref XXH_VECTOR_TYPE.
2703 * If this is not defined, it uses predefined macros to determine the best
2706 # define XXH_VECTOR XXH_SCALAR
2709 * @brief Possible values for @ref XXH_VECTOR.
2711 * Note that these are actually implemented as macros.
2713 * If this is not defined, it is detected automatically.
2714 * @ref XXH_X86DISPATCH overrides this.
2716 enum XXH_VECTOR_TYPE
/* fake enum */ {
2717 XXH_SCALAR
= 0, /*!< Portable scalar version */
2719 * SSE2 for Pentium 4, Opteron, all x86_64.
2721 * @note SSE2 is also guaranteed on Windows 10, macOS, and
2724 XXH_AVX2
= 2, /*!< AVX2 for Haswell and Bulldozer */
2725 XXH_AVX512
= 3, /*!< AVX512 for Skylake and Icelake */
2726 XXH_NEON
= 4, /*!< NEON for most ARMv7-A and all AArch64 */
2727 XXH_VSX
= 5, /*!< VSX and ZVector for POWER8/z13 (64-bit) */
2731 * @brief Selects the minimum alignment for XXH3's accumulators.
2733 * When using SIMD, this should match the alignment reqired for said vector
2734 * type, so, for example, 32 for AVX2.
2736 * Default: Auto detected.
2738 # define XXH_ACC_ALIGN 8
2741 /* Actual definition */
2743 # define XXH_SCALAR 0
2746 # define XXH_AVX512 3
2751 #ifndef XXH_VECTOR /* can be defined on command line */
2752 # if defined(__AVX512F__)
2753 # define XXH_VECTOR XXH_AVX512
2754 # elif defined(__AVX2__)
2755 # define XXH_VECTOR XXH_AVX2
2756 # elif defined(__SSE2__) || defined(_M_AMD64) || defined(_M_X64) || (defined(_M_IX86_FP) && (_M_IX86_FP == 2))
2757 # define XXH_VECTOR XXH_SSE2
2758 # elif defined(__GNUC__) /* msvc support maybe later */ \
2759 && (defined(__ARM_NEON__) || defined(__ARM_NEON)) \
2760 && (defined(__LITTLE_ENDIAN__) /* We only support little endian NEON */ \
2761 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__))
2762 # define XXH_VECTOR XXH_NEON
2763 # elif (defined(__PPC64__) && defined(__POWER8_VECTOR__)) \
2764 || (defined(__s390x__) && defined(__VEC__)) \
2765 && defined(__GNUC__) /* TODO: IBM XL */
2766 # define XXH_VECTOR XXH_VSX
2768 # define XXH_VECTOR XXH_SCALAR
2773 * Controls the alignment of the accumulator,
2774 * for compatibility with aligned vector loads, which are usually faster.
2776 #ifndef XXH_ACC_ALIGN
2777 # if defined(XXH_X86DISPATCH)
2778 # define XXH_ACC_ALIGN 64 /* for compatibility with avx512 */
2779 # elif XXH_VECTOR == XXH_SCALAR /* scalar */
2780 # define XXH_ACC_ALIGN 8
2781 # elif XXH_VECTOR == XXH_SSE2 /* sse2 */
2782 # define XXH_ACC_ALIGN 16
2783 # elif XXH_VECTOR == XXH_AVX2 /* avx2 */
2784 # define XXH_ACC_ALIGN 32
2785 # elif XXH_VECTOR == XXH_NEON /* neon */
2786 # define XXH_ACC_ALIGN 16
2787 # elif XXH_VECTOR == XXH_VSX /* vsx */
2788 # define XXH_ACC_ALIGN 16
2789 # elif XXH_VECTOR == XXH_AVX512 /* avx512 */
2790 # define XXH_ACC_ALIGN 64
2794 #if defined(XXH_X86DISPATCH) || XXH_VECTOR == XXH_SSE2 \
2795 || XXH_VECTOR == XXH_AVX2 || XXH_VECTOR == XXH_AVX512
2796 # define XXH_SEC_ALIGN XXH_ACC_ALIGN
2798 # define XXH_SEC_ALIGN 8
2803 * GCC usually generates the best code with -O3 for xxHash.
2805 * However, when targeting AVX2, it is overzealous in its unrolling resulting
2806 * in code roughly 3/4 the speed of Clang.
2808 * There are other issues, such as GCC splitting _mm256_loadu_si256 into
2809 * _mm_loadu_si128 + _mm256_inserti128_si256. This is an optimization which
2810 * only applies to Sandy and Ivy Bridge... which don't even support AVX2.
2812 * That is why when compiling the AVX2 version, it is recommended to use either
2813 * -O2 -mavx2 -march=haswell
2815 * -O2 -mavx2 -mno-avx256-split-unaligned-load
2816 * for decent performance, or to use Clang instead.
2818 * Fortunately, we can control the first one with a pragma that forces GCC into
2819 * -O2, but the other one we can't control without "failed to inline always
2820 * inline function due to target mismatch" warnings.
2822 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
2823 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
2824 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
2825 # pragma GCC push_options
2826 # pragma GCC optimize("-O2")
2830 #if XXH_VECTOR == XXH_NEON
2832 * NEON's setup for vmlal_u32 is a little more complicated than it is on
2833 * SSE2, AVX2, and VSX.
2835 * While PMULUDQ and VMULEUW both perform a mask, VMLAL.U32 performs an upcast.
2837 * To do the same operation, the 128-bit 'Q' register needs to be split into
2838 * two 64-bit 'D' registers, performing this operation::
2841 * | '---------. .--------' |
2843 * | .---------' '--------. |
2844 * [ a & 0xFFFFFFFF | b & 0xFFFFFFFF ],[ a >> 32 | b >> 32 ]
2846 * Due to significant changes in aarch64, the fastest method for aarch64 is
2847 * completely different than the fastest method for ARMv7-A.
2849 * ARMv7-A treats D registers as unions overlaying Q registers, so modifying
2850 * D11 will modify the high half of Q5. This is similar to how modifying AH
2851 * will only affect bits 8-15 of AX on x86.
2853 * VZIP takes two registers, and puts even lanes in one register and odd lanes
2856 * On ARMv7-A, this strangely modifies both parameters in place instead of
2857 * taking the usual 3-operand form.
2859 * Therefore, if we want to do this, we can simply use a D-form VZIP.32 on the
2860 * lower and upper halves of the Q register to end up with the high and low
2861 * halves where we want - all in one instruction.
2863 * vzip.32 d10, d11 @ d10 = { d10[0], d11[0] }; d11 = { d10[1], d11[1] }
2865 * Unfortunately we need inline assembly for this: Instructions modifying two
2866 * registers at once is not possible in GCC or Clang's IR, and they have to
2869 * aarch64 requires a different approach.
2871 * In order to make it easier to write a decent compiler for aarch64, many
2872 * quirks were removed, such as conditional execution.
2874 * NEON was also affected by this.
2876 * aarch64 cannot access the high bits of a Q-form register, and writes to a
2877 * D-form register zero the high bits, similar to how writes to W-form scalar
2878 * registers (or DWORD registers on x86_64) work.
2880 * The formerly free vget_high intrinsics now require a vext (with a few
2883 * Additionally, VZIP was replaced by ZIP1 and ZIP2, which are the equivalent
2884 * of PUNPCKL* and PUNPCKH* in SSE, respectively, in order to only modify one
2887 * The equivalent of the VZIP.32 on the lower and upper halves would be this
2890 * ext v2.4s, v0.4s, v0.4s, #2 // v2 = { v0[2], v0[3], v0[0], v0[1] }
2891 * zip1 v1.2s, v0.2s, v2.2s // v1 = { v0[0], v2[0] }
2892 * zip2 v0.2s, v0.2s, v1.2s // v0 = { v0[1], v2[1] }
2894 * Instead, we use a literal downcast, vmovn_u64 (XTN), and vshrn_n_u64 (SHRN):
2896 * shrn v1.2s, v0.2d, #32 // v1 = (uint32x2_t)(v0 >> 32);
2897 * xtn v0.2s, v0.2d // v0 = (uint32x2_t)(v0 & 0xFFFFFFFF);
2899 * This is available on ARMv7-A, but is less efficient than a single VZIP.32.
2903 * Function-like macro:
2904 * void XXH_SPLIT_IN_PLACE(uint64x2_t &in, uint32x2_t &outLo, uint32x2_t &outHi)
2906 * outLo = (uint32x2_t)(in & 0xFFFFFFFF);
2907 * outHi = (uint32x2_t)(in >> 32);
2911 # if !defined(XXH_NO_VZIP_HACK) /* define to disable */ \
2912 && defined(__GNUC__) \
2913 && !defined(__aarch64__) && !defined(__arm64__)
2914 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \
2916 /* Undocumented GCC/Clang operand modifier: %e0 = lower D half, %f0 = upper D half */ \
2917 /* https://github.com/gcc-mirror/gcc/blob/38cf91e5/gcc/config/arm/arm.c#L22486 */ \
2918 /* https://github.com/llvm-mirror/llvm/blob/2c4ca683/lib/Target/ARM/ARMAsmPrinter.cpp#L399 */ \
2919 __asm__("vzip.32 %e0, %f0" : "+w" (in)); \
2920 (outLo) = vget_low_u32 (vreinterpretq_u32_u64(in)); \
2921 (outHi) = vget_high_u32(vreinterpretq_u32_u64(in)); \
2924 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \
2926 (outLo) = vmovn_u64 (in); \
2927 (outHi) = vshrn_n_u64 ((in), 32); \
2930 #endif /* XXH_VECTOR == XXH_NEON */
2933 * VSX and Z Vector helpers.
2935 * This is very messy, and any pull requests to clean this up are welcome.
2937 * There are a lot of problems with supporting VSX and s390x, due to
2938 * inconsistent intrinsics, spotty coverage, and multiple endiannesses.
2940 #if XXH_VECTOR == XXH_VSX
2941 # if defined(__s390x__)
2942 # include <s390intrin.h>
2944 /* gcc's altivec.h can have the unwanted consequence to unconditionally
2945 * #define bool, vector, and pixel keywords,
2946 * with bad consequences for programs already using these keywords for other purposes.
2947 * The paragraph defining these macros is skipped when __APPLE_ALTIVEC__ is defined.
2948 * __APPLE_ALTIVEC__ is _generally_ defined automatically by the compiler,
2949 * but it seems that, in some cases, it isn't.
2950 * Force the build macro to be defined, so that keywords are not altered.
2952 # if defined(__GNUC__) && !defined(__APPLE_ALTIVEC__)
2953 # define __APPLE_ALTIVEC__
2955 # include <altivec.h>
2958 typedef __vector
unsigned long long xxh_u64x2
;
2959 typedef __vector
unsigned char xxh_u8x16
;
2960 typedef __vector
unsigned xxh_u32x4
;
2963 # if defined(__BIG_ENDIAN__) \
2964 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
2965 # define XXH_VSX_BE 1
2966 # elif defined(__VEC_ELEMENT_REG_ORDER__) && __VEC_ELEMENT_REG_ORDER__ == __ORDER_BIG_ENDIAN__
2967 # warning "-maltivec=be is not recommended. Please use native endianness."
2968 # define XXH_VSX_BE 1
2970 # define XXH_VSX_BE 0
2972 # endif /* !defined(XXH_VSX_BE) */
2975 # if defined(__POWER9_VECTOR__) || (defined(__clang__) && defined(__s390x__))
2976 # define XXH_vec_revb vec_revb
2979 * A polyfill for POWER9's vec_revb().
2981 XXH_FORCE_INLINE xxh_u64x2
XXH_vec_revb(xxh_u64x2 val
)
2983 xxh_u8x16
const vByteSwap
= { 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
2984 0x0F, 0x0E, 0x0D, 0x0C, 0x0B, 0x0A, 0x09, 0x08 };
2985 return vec_perm(val
, val
, vByteSwap
);
2988 # endif /* XXH_VSX_BE */
2991 * Performs an unaligned vector load and byte swaps it on big endian.
2993 XXH_FORCE_INLINE xxh_u64x2
XXH_vec_loadu(const void *ptr
)
2996 memcpy(&ret
, ptr
, sizeof(xxh_u64x2
));
2998 ret
= XXH_vec_revb(ret
);
3004 * vec_mulo and vec_mule are very problematic intrinsics on PowerPC
3006 * These intrinsics weren't added until GCC 8, despite existing for a while,
3007 * and they are endian dependent. Also, their meaning swap depending on version.
3009 # if defined(__s390x__)
3010 /* s390x is always big endian, no issue on this platform */
3011 # define XXH_vec_mulo vec_mulo
3012 # define XXH_vec_mule vec_mule
3013 # elif defined(__clang__) && XXH_HAS_BUILTIN(__builtin_altivec_vmuleuw)
3014 /* Clang has a better way to control this, we can just use the builtin which doesn't swap. */
3015 # define XXH_vec_mulo __builtin_altivec_vmulouw
3016 # define XXH_vec_mule __builtin_altivec_vmuleuw
3018 /* gcc needs inline assembly */
3019 /* Adapted from https://github.com/google/highwayhash/blob/master/highwayhash/hh_vsx.h. */
3020 XXH_FORCE_INLINE xxh_u64x2
XXH_vec_mulo(xxh_u32x4 a
, xxh_u32x4 b
)
3023 __asm__("vmulouw %0, %1, %2" : "=v" (result
) : "v" (a
), "v" (b
));
3026 XXH_FORCE_INLINE xxh_u64x2
XXH_vec_mule(xxh_u32x4 a
, xxh_u32x4 b
)
3029 __asm__("vmuleuw %0, %1, %2" : "=v" (result
) : "v" (a
), "v" (b
));
3032 # endif /* XXH_vec_mulo, XXH_vec_mule */
3033 #endif /* XXH_VECTOR == XXH_VSX */
3037 * can be disabled, by declaring XXH_NO_PREFETCH build macro */
3038 #if defined(XXH_NO_PREFETCH)
3039 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */
3041 # if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_IX86)) /* _mm_prefetch() not defined outside of x86/x64 */
3042 # include <mmintrin.h> /* https://msdn.microsoft.com/fr-fr/library/84szxsww(v=vs.90).aspx */
3043 # define XXH_PREFETCH(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T0)
3044 # elif defined(__GNUC__) && ( (__GNUC__ >= 4) || ( (__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) ) )
3045 # define XXH_PREFETCH(ptr) __builtin_prefetch((ptr), 0 /* rw==read */, 3 /* locality */)
3047 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */
3049 #endif /* XXH_NO_PREFETCH */
3052 /* ==========================================
3053 * XXH3 default settings
3054 * ========================================== */
3056 #define XXH_SECRET_DEFAULT_SIZE 192 /* minimum XXH3_SECRET_SIZE_MIN */
3058 #if (XXH_SECRET_DEFAULT_SIZE < XXH3_SECRET_SIZE_MIN)
3059 # error "default keyset is not large enough"
3062 /*! Pseudorandom secret taken directly from FARSH. */
3063 XXH_ALIGN(64) static const xxh_u8 XXH3_kSecret
[XXH_SECRET_DEFAULT_SIZE
] = {
3064 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c,
3065 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f,
3066 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21,
3067 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c,
3068 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3,
3069 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8,
3070 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d,
3071 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64,
3072 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb,
3073 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e,
3074 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce,
3075 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e,
3079 #ifdef XXH_OLD_NAMES
3080 # define kSecret XXH3_kSecret
3085 * @brief Calculates a 32-bit to 64-bit long multiply.
3087 * Implemented as a macro.
3089 * Wraps `__emulu` on MSVC x86 because it tends to call `__allmul` when it doesn't
3090 * need to (but it shouldn't need to anyways, it is about 7 instructions to do
3091 * a 64x64 multiply...). Since we know that this will _always_ emit `MULL`, we
3092 * use that instead of the normal method.
3094 * If you are compiling for platforms like Thumb-1 and don't have a better option,
3095 * you may also want to write your own long multiply routine here.
3097 * @param x, y Numbers to be multiplied
3098 * @return 64-bit product of the low 32 bits of @p x and @p y.
3100 XXH_FORCE_INLINE xxh_u64
3101 XXH_mult32to64(xxh_u64 x
, xxh_u64 y
)
3103 return (x
& 0xFFFFFFFF) * (y
& 0xFFFFFFFF);
3105 #elif defined(_MSC_VER) && defined(_M_IX86)
3106 # include <intrin.h>
3107 # define XXH_mult32to64(x, y) __emulu((unsigned)(x), (unsigned)(y))
3110 * Downcast + upcast is usually better than masking on older compilers like
3111 * GCC 4.2 (especially 32-bit ones), all without affecting newer compilers.
3113 * The other method, (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF), will AND both operands
3114 * and perform a full 64x64 multiply -- entirely redundant on 32-bit.
3116 # define XXH_mult32to64(x, y) ((xxh_u64)(xxh_u32)(x) * (xxh_u64)(xxh_u32)(y))
3120 * @brief Calculates a 64->128-bit long multiply.
3122 * Uses `__uint128_t` and `_umul128` if available, otherwise uses a scalar
3125 * @param lhs, rhs The 64-bit integers to be multiplied
3126 * @return The 128-bit result represented in an @ref XXH128_hash_t.
3128 static XXH128_hash_t
3129 XXH_mult64to128(xxh_u64 lhs
, xxh_u64 rhs
)
3132 * GCC/Clang __uint128_t method.
3134 * On most 64-bit targets, GCC and Clang define a __uint128_t type.
3135 * This is usually the best way as it usually uses a native long 64-bit
3136 * multiply, such as MULQ on x86_64 or MUL + UMULH on aarch64.
3140 * Despite being a 32-bit platform, Clang (and emscripten) define this type
3141 * despite not having the arithmetic for it. This results in a laggy
3142 * compiler builtin call which calculates a full 128-bit multiply.
3143 * In that case it is best to use the portable one.
3144 * https://github.com/Cyan4973/xxHash/issues/211#issuecomment-515575677
3146 #if defined(__GNUC__) && !defined(__wasm__) \
3147 && defined(__SIZEOF_INT128__) \
3148 || (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128)
3150 __uint128_t
const product
= (__uint128_t
)lhs
* (__uint128_t
)rhs
;
3152 r128
.low64
= (xxh_u64
)(product
);
3153 r128
.high64
= (xxh_u64
)(product
>> 64);
3157 * MSVC for x64's _umul128 method.
3159 * xxh_u64 _umul128(xxh_u64 Multiplier, xxh_u64 Multiplicand, xxh_u64 *HighProduct);
3161 * This compiles to single operand MUL on x64.
3163 #elif defined(_M_X64) || defined(_M_IA64)
3166 # pragma intrinsic(_umul128)
3168 xxh_u64 product_high
;
3169 xxh_u64
const product_low
= _umul128(lhs
, rhs
, &product_high
);
3171 r128
.low64
= product_low
;
3172 r128
.high64
= product_high
;
3177 * Portable scalar method. Optimized for 32-bit and 64-bit ALUs.
3179 * This is a fast and simple grade school multiply, which is shown below
3180 * with base 10 arithmetic instead of base 0x100000000.
3182 * 9 3 // D2 lhs = 93
3183 * x 7 5 // D2 rhs = 75
3185 * 1 5 // D2 lo_lo = (93 % 10) * (75 % 10) = 15
3186 * 4 5 | // D2 hi_lo = (93 / 10) * (75 % 10) = 45
3187 * 2 1 | // D2 lo_hi = (93 % 10) * (75 / 10) = 21
3188 * + 6 3 | | // D2 hi_hi = (93 / 10) * (75 / 10) = 63
3190 * 2 7 | // D2 cross = (15 / 10) + (45 % 10) + 21 = 27
3191 * + 6 7 | | // D2 upper = (27 / 10) + (45 / 10) + 63 = 67
3193 * 6 9 7 5 // D4 res = (27 * 10) + (15 % 10) + (67 * 100) = 6975
3195 * The reasons for adding the products like this are:
3196 * 1. It avoids manual carry tracking. Just like how
3197 * (9 * 9) + 9 + 9 = 99, the same applies with this for UINT64_MAX.
3198 * This avoids a lot of complexity.
3200 * 2. It hints for, and on Clang, compiles to, the powerful UMAAL
3201 * instruction available in ARM's Digital Signal Processing extension
3202 * in 32-bit ARMv6 and later, which is shown below:
3204 * void UMAAL(xxh_u32 *RdLo, xxh_u32 *RdHi, xxh_u32 Rn, xxh_u32 Rm)
3206 * xxh_u64 product = (xxh_u64)*RdLo * (xxh_u64)*RdHi + Rn + Rm;
3207 * *RdLo = (xxh_u32)(product & 0xFFFFFFFF);
3208 * *RdHi = (xxh_u32)(product >> 32);
3211 * This instruction was designed for efficient long multiplication, and
3212 * allows this to be calculated in only 4 instructions at speeds
3213 * comparable to some 64-bit ALUs.
3215 * 3. It isn't terrible on other platforms. Usually this will be a couple
3216 * of 32-bit ADD/ADCs.
3219 /* First calculate all of the cross products. */
3220 xxh_u64
const lo_lo
= XXH_mult32to64(lhs
& 0xFFFFFFFF, rhs
& 0xFFFFFFFF);
3221 xxh_u64
const hi_lo
= XXH_mult32to64(lhs
>> 32, rhs
& 0xFFFFFFFF);
3222 xxh_u64
const lo_hi
= XXH_mult32to64(lhs
& 0xFFFFFFFF, rhs
>> 32);
3223 xxh_u64
const hi_hi
= XXH_mult32to64(lhs
>> 32, rhs
>> 32);
3225 /* Now add the products together. These will never overflow. */
3226 xxh_u64
const cross
= (lo_lo
>> 32) + (hi_lo
& 0xFFFFFFFF) + lo_hi
;
3227 xxh_u64
const upper
= (hi_lo
>> 32) + (cross
>> 32) + hi_hi
;
3228 xxh_u64
const lower
= (cross
<< 32) | (lo_lo
& 0xFFFFFFFF);
3232 r128
.high64
= upper
;
3238 * @brief Calculates a 64-bit to 128-bit multiply, then XOR folds it.
3240 * The reason for the separate function is to prevent passing too many structs
3241 * around by value. This will hopefully inline the multiply, but we don't force it.
3243 * @param lhs, rhs The 64-bit integers to multiply
3244 * @return The low 64 bits of the product XOR'd by the high 64 bits.
3245 * @see XXH_mult64to128()
3248 XXH3_mul128_fold64(xxh_u64 lhs
, xxh_u64 rhs
)
3250 XXH128_hash_t product
= XXH_mult64to128(lhs
, rhs
);
3251 return product
.low64
^ product
.high64
;
3254 /*! Seems to produce slightly better code on GCC for some reason. */
3255 XXH_FORCE_INLINE xxh_u64
XXH_xorshift64(xxh_u64 v64
, int shift
)
3257 XXH_ASSERT(0 <= shift
&& shift
< 64);
3258 return v64
^ (v64
>> shift
);
3262 * This is a fast avalanche stage,
3263 * suitable when input bits are already partially mixed
3265 static XXH64_hash_t
XXH3_avalanche(xxh_u64 h64
)
3267 h64
= XXH_xorshift64(h64
, 37);
3268 h64
*= 0x165667919E3779F9ULL
;
3269 h64
= XXH_xorshift64(h64
, 32);
3274 * This is a stronger avalanche,
3275 * inspired by Pelle Evensen's rrmxmx
3276 * preferable when input has not been previously mixed
3278 static XXH64_hash_t
XXH3_rrmxmx(xxh_u64 h64
, xxh_u64 len
)
3280 /* this mix is inspired by Pelle Evensen's rrmxmx */
3281 h64
^= XXH_rotl64(h64
, 49) ^ XXH_rotl64(h64
, 24);
3282 h64
*= 0x9FB21C651E98DF25ULL
;
3283 h64
^= (h64
>> 35) + len
;
3284 h64
*= 0x9FB21C651E98DF25ULL
;
3285 return XXH_xorshift64(h64
, 28);
3289 /* ==========================================
3291 * ==========================================
3292 * One of the shortcomings of XXH32 and XXH64 was that their performance was
3293 * sub-optimal on short lengths. It used an iterative algorithm which strongly
3294 * favored lengths that were a multiple of 4 or 8.
3296 * Instead of iterating over individual inputs, we use a set of single shot
3297 * functions which piece together a range of lengths and operate in constant time.
3299 * Additionally, the number of multiplies has been significantly reduced. This
3300 * reduces latency, especially when emulating 64-bit multiplies on 32-bit.
3302 * Depending on the platform, this may or may not be faster than XXH32, but it
3303 * is almost guaranteed to be faster than XXH64.
3307 * At very short lengths, there isn't enough input to fully hide secrets, or use
3308 * the entire secret.
3310 * There is also only a limited amount of mixing we can do before significantly
3311 * impacting performance.
3313 * Therefore, we use different sections of the secret and always mix two secret
3314 * samples with an XOR. This should have no effect on performance on the
3315 * seedless or withSeed variants because everything _should_ be constant folded
3316 * by modern compilers.
3318 * The XOR mixing hides individual parts of the secret and increases entropy.
3320 * This adds an extra layer of strength for custom secrets.
3322 XXH_FORCE_INLINE XXH64_hash_t
3323 XXH3_len_1to3_64b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
3325 XXH_ASSERT(input
!= NULL
);
3326 XXH_ASSERT(1 <= len
&& len
<= 3);
3327 XXH_ASSERT(secret
!= NULL
);
3329 * len = 1: combined = { input[0], 0x01, input[0], input[0] }
3330 * len = 2: combined = { input[1], 0x02, input[0], input[1] }
3331 * len = 3: combined = { input[2], 0x03, input[0], input[1] }
3333 { xxh_u8
const c1
= input
[0];
3334 xxh_u8
const c2
= input
[len
>> 1];
3335 xxh_u8
const c3
= input
[len
- 1];
3336 xxh_u32
const combined
= ((xxh_u32
)c1
<< 16) | ((xxh_u32
)c2
<< 24)
3337 | ((xxh_u32
)c3
<< 0) | ((xxh_u32
)len
<< 8);
3338 xxh_u64
const bitflip
= (XXH_readLE32(secret
) ^ XXH_readLE32(secret
+4)) + seed
;
3339 xxh_u64
const keyed
= (xxh_u64
)combined
^ bitflip
;
3340 return XXH64_avalanche(keyed
);
3344 XXH_FORCE_INLINE XXH64_hash_t
3345 XXH3_len_4to8_64b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
3347 XXH_ASSERT(input
!= NULL
);
3348 XXH_ASSERT(secret
!= NULL
);
3349 XXH_ASSERT(4 <= len
&& len
<= 8);
3350 seed
^= (xxh_u64
)XXH_swap32((xxh_u32
)seed
) << 32;
3351 { xxh_u32
const input1
= XXH_readLE32(input
);
3352 xxh_u32
const input2
= XXH_readLE32(input
+ len
- 4);
3353 xxh_u64
const bitflip
= (XXH_readLE64(secret
+8) ^ XXH_readLE64(secret
+16)) - seed
;
3354 xxh_u64
const input64
= input2
+ (((xxh_u64
)input1
) << 32);
3355 xxh_u64
const keyed
= input64
^ bitflip
;
3356 return XXH3_rrmxmx(keyed
, len
);
3360 XXH_FORCE_INLINE XXH64_hash_t
3361 XXH3_len_9to16_64b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
3363 XXH_ASSERT(input
!= NULL
);
3364 XXH_ASSERT(secret
!= NULL
);
3365 XXH_ASSERT(9 <= len
&& len
<= 16);
3366 { xxh_u64
const bitflip1
= (XXH_readLE64(secret
+24) ^ XXH_readLE64(secret
+32)) + seed
;
3367 xxh_u64
const bitflip2
= (XXH_readLE64(secret
+40) ^ XXH_readLE64(secret
+48)) - seed
;
3368 xxh_u64
const input_lo
= XXH_readLE64(input
) ^ bitflip1
;
3369 xxh_u64
const input_hi
= XXH_readLE64(input
+ len
- 8) ^ bitflip2
;
3370 xxh_u64
const acc
= len
3371 + XXH_swap64(input_lo
) + input_hi
3372 + XXH3_mul128_fold64(input_lo
, input_hi
);
3373 return XXH3_avalanche(acc
);
3377 XXH_FORCE_INLINE XXH64_hash_t
3378 XXH3_len_0to16_64b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
3380 XXH_ASSERT(len
<= 16);
3381 { if (XXH_likely(len
> 8)) return XXH3_len_9to16_64b(input
, len
, secret
, seed
);
3382 if (XXH_likely(len
>= 4)) return XXH3_len_4to8_64b(input
, len
, secret
, seed
);
3383 if (len
) return XXH3_len_1to3_64b(input
, len
, secret
, seed
);
3384 return XXH64_avalanche(seed
^ (XXH_readLE64(secret
+56) ^ XXH_readLE64(secret
+64)));
3389 * DISCLAIMER: There are known *seed-dependent* multicollisions here due to
3390 * multiplication by zero, affecting hashes of lengths 17 to 240.
3392 * However, they are very unlikely.
3394 * Keep this in mind when using the unseeded XXH3_64bits() variant: As with all
3395 * unseeded non-cryptographic hashes, it does not attempt to defend itself
3396 * against specially crafted inputs, only random inputs.
3398 * Compared to classic UMAC where a 1 in 2^31 chance of 4 consecutive bytes
3399 * cancelling out the secret is taken an arbitrary number of times (addressed
3400 * in XXH3_accumulate_512), this collision is very unlikely with random inputs
3401 * and/or proper seeding:
3403 * This only has a 1 in 2^63 chance of 8 consecutive bytes cancelling out, in a
3404 * function that is only called up to 16 times per hash with up to 240 bytes of
3407 * This is not too bad for a non-cryptographic hash function, especially with
3408 * only 64 bit outputs.
3410 * The 128-bit variant (which trades some speed for strength) is NOT affected
3411 * by this, although it is always a good idea to use a proper seed if you care
3414 XXH_FORCE_INLINE xxh_u64
XXH3_mix16B(const xxh_u8
* XXH_RESTRICT input
,
3415 const xxh_u8
* XXH_RESTRICT secret
, xxh_u64 seed64
)
3417 #if defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
3418 && defined(__i386__) && defined(__SSE2__) /* x86 + SSE2 */ \
3419 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable like XXH32 hack */
3422 * GCC for x86 tends to autovectorize the 128-bit multiply, resulting in
3425 * By forcing seed64 into a register, we disrupt the cost model and
3426 * cause it to scalarize. See `XXH32_round()`
3428 * FIXME: Clang's output is still _much_ faster -- On an AMD Ryzen 3600,
3429 * XXH3_64bits @ len=240 runs at 4.6 GB/s with Clang 9, but 3.3 GB/s on
3430 * GCC 9.2, despite both emitting scalar code.
3432 * GCC generates much better scalar code than Clang for the rest of XXH3,
3433 * which is why finding a more optimal codepath is an interest.
3435 XXH_COMPILER_GUARD(seed64
);
3437 { xxh_u64
const input_lo
= XXH_readLE64(input
);
3438 xxh_u64
const input_hi
= XXH_readLE64(input
+8);
3439 return XXH3_mul128_fold64(
3440 input_lo
^ (XXH_readLE64(secret
) + seed64
),
3441 input_hi
^ (XXH_readLE64(secret
+8) - seed64
)
3446 /* For mid range keys, XXH3 uses a Mum-hash variant. */
3447 XXH_FORCE_INLINE XXH64_hash_t
3448 XXH3_len_17to128_64b(const xxh_u8
* XXH_RESTRICT input
, size_t len
,
3449 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
3452 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
); (void)secretSize
;
3453 XXH_ASSERT(16 < len
&& len
<= 128);
3455 { xxh_u64 acc
= len
* XXH_PRIME64_1
;
3459 acc
+= XXH3_mix16B(input
+48, secret
+96, seed
);
3460 acc
+= XXH3_mix16B(input
+len
-64, secret
+112, seed
);
3462 acc
+= XXH3_mix16B(input
+32, secret
+64, seed
);
3463 acc
+= XXH3_mix16B(input
+len
-48, secret
+80, seed
);
3465 acc
+= XXH3_mix16B(input
+16, secret
+32, seed
);
3466 acc
+= XXH3_mix16B(input
+len
-32, secret
+48, seed
);
3468 acc
+= XXH3_mix16B(input
+0, secret
+0, seed
);
3469 acc
+= XXH3_mix16B(input
+len
-16, secret
+16, seed
);
3471 return XXH3_avalanche(acc
);
3475 #define XXH3_MIDSIZE_MAX 240
3477 XXH_NO_INLINE XXH64_hash_t
3478 XXH3_len_129to240_64b(const xxh_u8
* XXH_RESTRICT input
, size_t len
,
3479 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
3482 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
); (void)secretSize
;
3483 XXH_ASSERT(128 < len
&& len
<= XXH3_MIDSIZE_MAX
);
3485 #define XXH3_MIDSIZE_STARTOFFSET 3
3486 #define XXH3_MIDSIZE_LASTOFFSET 17
3488 { xxh_u64 acc
= len
* XXH_PRIME64_1
;
3489 int const nbRounds
= (int)len
/ 16;
3491 for (i
=0; i
<8; i
++) {
3492 acc
+= XXH3_mix16B(input
+(16*i
), secret
+(16*i
), seed
);
3494 acc
= XXH3_avalanche(acc
);
3495 XXH_ASSERT(nbRounds
>= 8);
3496 #if defined(__clang__) /* Clang */ \
3497 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \
3498 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */
3501 * Clang for ARMv7-A tries to vectorize this loop, similar to GCC x86.
3502 * In everywhere else, it uses scalar code.
3504 * For 64->128-bit multiplies, even if the NEON was 100% optimal, it
3505 * would still be slower than UMAAL (see XXH_mult64to128).
3507 * Unfortunately, Clang doesn't handle the long multiplies properly and
3508 * converts them to the nonexistent "vmulq_u64" intrinsic, which is then
3509 * scalarized into an ugly mess of VMOV.32 instructions.
3511 * This mess is difficult to avoid without turning autovectorization
3512 * off completely, but they are usually relatively minor and/or not
3515 * This loop is the easiest to fix, as unlike XXH32, this pragma
3516 * _actually works_ because it is a loop vectorization instead of an
3517 * SLP vectorization.
3519 #pragma clang loop vectorize(disable)
3521 for (i
=8 ; i
< nbRounds
; i
++) {
3522 acc
+= XXH3_mix16B(input
+(16*i
), secret
+(16*(i
-8)) + XXH3_MIDSIZE_STARTOFFSET
, seed
);
3525 acc
+= XXH3_mix16B(input
+ len
- 16, secret
+ XXH3_SECRET_SIZE_MIN
- XXH3_MIDSIZE_LASTOFFSET
, seed
);
3526 return XXH3_avalanche(acc
);
3531 /* ======= Long Keys ======= */
3533 #define XXH_STRIPE_LEN 64
3534 #define XXH_SECRET_CONSUME_RATE 8 /* nb of secret bytes consumed at each accumulation */
3535 #define XXH_ACC_NB (XXH_STRIPE_LEN / sizeof(xxh_u64))
3537 #ifdef XXH_OLD_NAMES
3538 # define STRIPE_LEN XXH_STRIPE_LEN
3539 # define ACC_NB XXH_ACC_NB
3542 XXH_FORCE_INLINE
void XXH_writeLE64(void* dst
, xxh_u64 v64
)
3544 if (!XXH_CPU_LITTLE_ENDIAN
) v64
= XXH_swap64(v64
);
3545 memcpy(dst
, &v64
, sizeof(v64
));
3548 /* Several intrinsic functions below are supposed to accept __int64 as argument,
3549 * as documented in https://software.intel.com/sites/landingpage/IntrinsicsGuide/ .
3550 * However, several environments do not define __int64 type,
3551 * requiring a workaround.
3553 #if !defined (__VMS) \
3554 && (defined (__cplusplus) \
3555 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
3556 typedef int64_t xxh_i64
;
3558 /* the following type must have a width of 64-bit */
3559 typedef long long xxh_i64
;
3563 * XXH3_accumulate_512 is the tightest loop for long inputs, and it is the most optimized.
3565 * It is a hardened version of UMAC, based off of FARSH's implementation.
3567 * This was chosen because it adapts quite well to 32-bit, 64-bit, and SIMD
3568 * implementations, and it is ridiculously fast.
3570 * We harden it by mixing the original input to the accumulators as well as the product.
3572 * This means that in the (relatively likely) case of a multiply by zero, the
3573 * original input is preserved.
3575 * On 128-bit inputs, we swap 64-bit pairs when we add the input to improve
3576 * cross-pollination, as otherwise the upper and lower halves would be
3577 * essentially independent.
3579 * This doesn't matter on 64-bit hashes since they all get merged together in
3580 * the end, so we skip the extra step.
3582 * Both XXH3_64bits and XXH3_128bits use this subroutine.
3585 #if (XXH_VECTOR == XXH_AVX512) \
3586 || (defined(XXH_DISPATCH_AVX512) && XXH_DISPATCH_AVX512 != 0)
3588 #ifndef XXH_TARGET_AVX512
3589 # define XXH_TARGET_AVX512 /* disable attribute target */
3592 XXH_FORCE_INLINE XXH_TARGET_AVX512
void
3593 XXH3_accumulate_512_avx512(void* XXH_RESTRICT acc
,
3594 const void* XXH_RESTRICT input
,
3595 const void* XXH_RESTRICT secret
)
3597 XXH_ALIGN(64) __m512i
* const xacc
= (__m512i
*) acc
;
3598 XXH_ASSERT((((size_t)acc
) & 63) == 0);
3599 XXH_STATIC_ASSERT(XXH_STRIPE_LEN
== sizeof(__m512i
));
3602 /* data_vec = input[0]; */
3603 __m512i
const data_vec
= _mm512_loadu_si512 (input
);
3604 /* key_vec = secret[0]; */
3605 __m512i
const key_vec
= _mm512_loadu_si512 (secret
);
3606 /* data_key = data_vec ^ key_vec; */
3607 __m512i
const data_key
= _mm512_xor_si512 (data_vec
, key_vec
);
3608 /* data_key_lo = data_key >> 32; */
3609 __m512i
const data_key_lo
= _mm512_shuffle_epi32 (data_key
, (_MM_PERM_ENUM
)_MM_SHUFFLE(0, 3, 0, 1));
3610 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3611 __m512i
const product
= _mm512_mul_epu32 (data_key
, data_key_lo
);
3612 /* xacc[0] += swap(data_vec); */
3613 __m512i
const data_swap
= _mm512_shuffle_epi32(data_vec
, (_MM_PERM_ENUM
)_MM_SHUFFLE(1, 0, 3, 2));
3614 __m512i
const sum
= _mm512_add_epi64(*xacc
, data_swap
);
3615 /* xacc[0] += product; */
3616 *xacc
= _mm512_add_epi64(product
, sum
);
3621 * XXH3_scrambleAcc: Scrambles the accumulators to improve mixing.
3623 * Multiplication isn't perfect, as explained by Google in HighwayHash:
3625 * // Multiplication mixes/scrambles bytes 0-7 of the 64-bit result to
3626 * // varying degrees. In descending order of goodness, bytes
3627 * // 3 4 2 5 1 6 0 7 have quality 228 224 164 160 100 96 36 32.
3628 * // As expected, the upper and lower bytes are much worse.
3630 * Source: https://github.com/google/highwayhash/blob/0aaf66b/highwayhash/hh_avx2.h#L291
3632 * Since our algorithm uses a pseudorandom secret to add some variance into the
3633 * mix, we don't need to (or want to) mix as often or as much as HighwayHash does.
3635 * This isn't as tight as XXH3_accumulate, but still written in SIMD to avoid
3638 * Both XXH3_64bits and XXH3_128bits use this subroutine.
3641 XXH_FORCE_INLINE XXH_TARGET_AVX512
void
3642 XXH3_scrambleAcc_avx512(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
3644 XXH_ASSERT((((size_t)acc
) & 63) == 0);
3645 XXH_STATIC_ASSERT(XXH_STRIPE_LEN
== sizeof(__m512i
));
3646 { XXH_ALIGN(64) __m512i
* const xacc
= (__m512i
*) acc
;
3647 const __m512i prime32
= _mm512_set1_epi32((int)XXH_PRIME32_1
);
3649 /* xacc[0] ^= (xacc[0] >> 47) */
3650 __m512i
const acc_vec
= *xacc
;
3651 __m512i
const shifted
= _mm512_srli_epi64 (acc_vec
, 47);
3652 __m512i
const data_vec
= _mm512_xor_si512 (acc_vec
, shifted
);
3653 /* xacc[0] ^= secret; */
3654 __m512i
const key_vec
= _mm512_loadu_si512 (secret
);
3655 __m512i
const data_key
= _mm512_xor_si512 (data_vec
, key_vec
);
3657 /* xacc[0] *= XXH_PRIME32_1; */
3658 __m512i
const data_key_hi
= _mm512_shuffle_epi32 (data_key
, (_MM_PERM_ENUM
)_MM_SHUFFLE(0, 3, 0, 1));
3659 __m512i
const prod_lo
= _mm512_mul_epu32 (data_key
, prime32
);
3660 __m512i
const prod_hi
= _mm512_mul_epu32 (data_key_hi
, prime32
);
3661 *xacc
= _mm512_add_epi64(prod_lo
, _mm512_slli_epi64(prod_hi
, 32));
3665 XXH_FORCE_INLINE XXH_TARGET_AVX512
void
3666 XXH3_initCustomSecret_avx512(void* XXH_RESTRICT customSecret
, xxh_u64 seed64
)
3668 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE
& 63) == 0);
3669 XXH_STATIC_ASSERT(XXH_SEC_ALIGN
== 64);
3670 XXH_ASSERT(((size_t)customSecret
& 63) == 0);
3671 (void)(&XXH_writeLE64
);
3672 { int const nbRounds
= XXH_SECRET_DEFAULT_SIZE
/ sizeof(__m512i
);
3673 __m512i
const seed
= _mm512_mask_set1_epi64(_mm512_set1_epi64((xxh_i64
)seed64
), 0xAA, (xxh_i64
)(0U - seed64
));
3675 XXH_ALIGN(64) const __m512i
* const src
= (const __m512i
*) XXH3_kSecret
;
3676 XXH_ALIGN(64) __m512i
* const dest
= ( __m512i
*) customSecret
;
3678 for (i
=0; i
< nbRounds
; ++i
) {
3679 /* GCC has a bug, _mm512_stream_load_si512 accepts 'void*', not 'void const*',
3680 * this will warn "discards 'const' qualifier". */
3682 XXH_ALIGN(64) const __m512i
* cp
;
3683 XXH_ALIGN(64) void* p
;
3684 } remote_const_void
;
3685 remote_const_void
.cp
= src
+ i
;
3686 dest
[i
] = _mm512_add_epi64(_mm512_stream_load_si512(remote_const_void
.p
), seed
);
3692 #if (XXH_VECTOR == XXH_AVX2) \
3693 || (defined(XXH_DISPATCH_AVX2) && XXH_DISPATCH_AVX2 != 0)
3695 #ifndef XXH_TARGET_AVX2
3696 # define XXH_TARGET_AVX2 /* disable attribute target */
3699 XXH_FORCE_INLINE XXH_TARGET_AVX2
void
3700 XXH3_accumulate_512_avx2( void* XXH_RESTRICT acc
,
3701 const void* XXH_RESTRICT input
,
3702 const void* XXH_RESTRICT secret
)
3704 XXH_ASSERT((((size_t)acc
) & 31) == 0);
3705 { XXH_ALIGN(32) __m256i
* const xacc
= (__m256i
*) acc
;
3706 /* Unaligned. This is mainly for pointer arithmetic, and because
3707 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3708 const __m256i
* const xinput
= (const __m256i
*) input
;
3709 /* Unaligned. This is mainly for pointer arithmetic, and because
3710 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3711 const __m256i
* const xsecret
= (const __m256i
*) secret
;
3714 for (i
=0; i
< XXH_STRIPE_LEN
/sizeof(__m256i
); i
++) {
3715 /* data_vec = xinput[i]; */
3716 __m256i
const data_vec
= _mm256_loadu_si256 (xinput
+i
);
3717 /* key_vec = xsecret[i]; */
3718 __m256i
const key_vec
= _mm256_loadu_si256 (xsecret
+i
);
3719 /* data_key = data_vec ^ key_vec; */
3720 __m256i
const data_key
= _mm256_xor_si256 (data_vec
, key_vec
);
3721 /* data_key_lo = data_key >> 32; */
3722 __m256i
const data_key_lo
= _mm256_shuffle_epi32 (data_key
, _MM_SHUFFLE(0, 3, 0, 1));
3723 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3724 __m256i
const product
= _mm256_mul_epu32 (data_key
, data_key_lo
);
3725 /* xacc[i] += swap(data_vec); */
3726 __m256i
const data_swap
= _mm256_shuffle_epi32(data_vec
, _MM_SHUFFLE(1, 0, 3, 2));
3727 __m256i
const sum
= _mm256_add_epi64(xacc
[i
], data_swap
);
3728 /* xacc[i] += product; */
3729 xacc
[i
] = _mm256_add_epi64(product
, sum
);
3733 XXH_FORCE_INLINE XXH_TARGET_AVX2
void
3734 XXH3_scrambleAcc_avx2(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
3736 XXH_ASSERT((((size_t)acc
) & 31) == 0);
3737 { XXH_ALIGN(32) __m256i
* const xacc
= (__m256i
*) acc
;
3738 /* Unaligned. This is mainly for pointer arithmetic, and because
3739 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */
3740 const __m256i
* const xsecret
= (const __m256i
*) secret
;
3741 const __m256i prime32
= _mm256_set1_epi32((int)XXH_PRIME32_1
);
3744 for (i
=0; i
< XXH_STRIPE_LEN
/sizeof(__m256i
); i
++) {
3745 /* xacc[i] ^= (xacc[i] >> 47) */
3746 __m256i
const acc_vec
= xacc
[i
];
3747 __m256i
const shifted
= _mm256_srli_epi64 (acc_vec
, 47);
3748 __m256i
const data_vec
= _mm256_xor_si256 (acc_vec
, shifted
);
3749 /* xacc[i] ^= xsecret; */
3750 __m256i
const key_vec
= _mm256_loadu_si256 (xsecret
+i
);
3751 __m256i
const data_key
= _mm256_xor_si256 (data_vec
, key_vec
);
3753 /* xacc[i] *= XXH_PRIME32_1; */
3754 __m256i
const data_key_hi
= _mm256_shuffle_epi32 (data_key
, _MM_SHUFFLE(0, 3, 0, 1));
3755 __m256i
const prod_lo
= _mm256_mul_epu32 (data_key
, prime32
);
3756 __m256i
const prod_hi
= _mm256_mul_epu32 (data_key_hi
, prime32
);
3757 xacc
[i
] = _mm256_add_epi64(prod_lo
, _mm256_slli_epi64(prod_hi
, 32));
3762 XXH_FORCE_INLINE XXH_TARGET_AVX2
void XXH3_initCustomSecret_avx2(void* XXH_RESTRICT customSecret
, xxh_u64 seed64
)
3764 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE
& 31) == 0);
3765 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE
/ sizeof(__m256i
)) == 6);
3766 XXH_STATIC_ASSERT(XXH_SEC_ALIGN
<= 64);
3767 (void)(&XXH_writeLE64
);
3768 XXH_PREFETCH(customSecret
);
3769 { __m256i
const seed
= _mm256_set_epi64x((xxh_i64
)(0U - seed64
), (xxh_i64
)seed64
, (xxh_i64
)(0U - seed64
), (xxh_i64
)seed64
);
3771 XXH_ALIGN(64) const __m256i
* const src
= (const __m256i
*) XXH3_kSecret
;
3772 XXH_ALIGN(64) __m256i
* dest
= ( __m256i
*) customSecret
;
3774 # if defined(__GNUC__) || defined(__clang__)
3776 * On GCC & Clang, marking 'dest' as modified will cause the compiler:
3777 * - do not extract the secret from sse registers in the internal loop
3778 * - use less common registers, and avoid pushing these reg into stack
3780 XXH_COMPILER_GUARD(dest
);
3783 /* GCC -O2 need unroll loop manually */
3784 dest
[0] = _mm256_add_epi64(_mm256_stream_load_si256(src
+0), seed
);
3785 dest
[1] = _mm256_add_epi64(_mm256_stream_load_si256(src
+1), seed
);
3786 dest
[2] = _mm256_add_epi64(_mm256_stream_load_si256(src
+2), seed
);
3787 dest
[3] = _mm256_add_epi64(_mm256_stream_load_si256(src
+3), seed
);
3788 dest
[4] = _mm256_add_epi64(_mm256_stream_load_si256(src
+4), seed
);
3789 dest
[5] = _mm256_add_epi64(_mm256_stream_load_si256(src
+5), seed
);
3795 /* x86dispatch always generates SSE2 */
3796 #if (XXH_VECTOR == XXH_SSE2) || defined(XXH_X86DISPATCH)
3798 #ifndef XXH_TARGET_SSE2
3799 # define XXH_TARGET_SSE2 /* disable attribute target */
3802 XXH_FORCE_INLINE XXH_TARGET_SSE2
void
3803 XXH3_accumulate_512_sse2( void* XXH_RESTRICT acc
,
3804 const void* XXH_RESTRICT input
,
3805 const void* XXH_RESTRICT secret
)
3807 /* SSE2 is just a half-scale version of the AVX2 version. */
3808 XXH_ASSERT((((size_t)acc
) & 15) == 0);
3809 { XXH_ALIGN(16) __m128i
* const xacc
= (__m128i
*) acc
;
3810 /* Unaligned. This is mainly for pointer arithmetic, and because
3811 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3812 const __m128i
* const xinput
= (const __m128i
*) input
;
3813 /* Unaligned. This is mainly for pointer arithmetic, and because
3814 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3815 const __m128i
* const xsecret
= (const __m128i
*) secret
;
3818 for (i
=0; i
< XXH_STRIPE_LEN
/sizeof(__m128i
); i
++) {
3819 /* data_vec = xinput[i]; */
3820 __m128i
const data_vec
= _mm_loadu_si128 (xinput
+i
);
3821 /* key_vec = xsecret[i]; */
3822 __m128i
const key_vec
= _mm_loadu_si128 (xsecret
+i
);
3823 /* data_key = data_vec ^ key_vec; */
3824 __m128i
const data_key
= _mm_xor_si128 (data_vec
, key_vec
);
3825 /* data_key_lo = data_key >> 32; */
3826 __m128i
const data_key_lo
= _mm_shuffle_epi32 (data_key
, _MM_SHUFFLE(0, 3, 0, 1));
3827 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */
3828 __m128i
const product
= _mm_mul_epu32 (data_key
, data_key_lo
);
3829 /* xacc[i] += swap(data_vec); */
3830 __m128i
const data_swap
= _mm_shuffle_epi32(data_vec
, _MM_SHUFFLE(1,0,3,2));
3831 __m128i
const sum
= _mm_add_epi64(xacc
[i
], data_swap
);
3832 /* xacc[i] += product; */
3833 xacc
[i
] = _mm_add_epi64(product
, sum
);
3837 XXH_FORCE_INLINE XXH_TARGET_SSE2
void
3838 XXH3_scrambleAcc_sse2(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
3840 XXH_ASSERT((((size_t)acc
) & 15) == 0);
3841 { XXH_ALIGN(16) __m128i
* const xacc
= (__m128i
*) acc
;
3842 /* Unaligned. This is mainly for pointer arithmetic, and because
3843 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */
3844 const __m128i
* const xsecret
= (const __m128i
*) secret
;
3845 const __m128i prime32
= _mm_set1_epi32((int)XXH_PRIME32_1
);
3848 for (i
=0; i
< XXH_STRIPE_LEN
/sizeof(__m128i
); i
++) {
3849 /* xacc[i] ^= (xacc[i] >> 47) */
3850 __m128i
const acc_vec
= xacc
[i
];
3851 __m128i
const shifted
= _mm_srli_epi64 (acc_vec
, 47);
3852 __m128i
const data_vec
= _mm_xor_si128 (acc_vec
, shifted
);
3853 /* xacc[i] ^= xsecret[i]; */
3854 __m128i
const key_vec
= _mm_loadu_si128 (xsecret
+i
);
3855 __m128i
const data_key
= _mm_xor_si128 (data_vec
, key_vec
);
3857 /* xacc[i] *= XXH_PRIME32_1; */
3858 __m128i
const data_key_hi
= _mm_shuffle_epi32 (data_key
, _MM_SHUFFLE(0, 3, 0, 1));
3859 __m128i
const prod_lo
= _mm_mul_epu32 (data_key
, prime32
);
3860 __m128i
const prod_hi
= _mm_mul_epu32 (data_key_hi
, prime32
);
3861 xacc
[i
] = _mm_add_epi64(prod_lo
, _mm_slli_epi64(prod_hi
, 32));
3866 XXH_FORCE_INLINE XXH_TARGET_SSE2
void XXH3_initCustomSecret_sse2(void* XXH_RESTRICT customSecret
, xxh_u64 seed64
)
3868 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE
& 15) == 0);
3869 (void)(&XXH_writeLE64
);
3870 { int const nbRounds
= XXH_SECRET_DEFAULT_SIZE
/ sizeof(__m128i
);
3872 # if defined(_MSC_VER) && defined(_M_IX86) && _MSC_VER < 1900
3873 // MSVC 32bit mode does not support _mm_set_epi64x before 2015
3874 XXH_ALIGN(16) const xxh_i64 seed64x2
[2] = { (xxh_i64
)seed64
, (xxh_i64
)(0U - seed64
) };
3875 __m128i
const seed
= _mm_load_si128((__m128i
const*)seed64x2
);
3877 __m128i
const seed
= _mm_set_epi64x((xxh_i64
)(0U - seed64
), (xxh_i64
)seed64
);
3881 XXH_ALIGN(64) const float* const src
= (float const*) XXH3_kSecret
;
3882 XXH_ALIGN(XXH_SEC_ALIGN
) __m128i
* dest
= (__m128i
*) customSecret
;
3883 # if defined(__GNUC__) || defined(__clang__)
3885 * On GCC & Clang, marking 'dest' as modified will cause the compiler:
3886 * - do not extract the secret from sse registers in the internal loop
3887 * - use less common registers, and avoid pushing these reg into stack
3889 XXH_COMPILER_GUARD(dest
);
3892 for (i
=0; i
< nbRounds
; ++i
) {
3893 dest
[i
] = _mm_add_epi64(_mm_castps_si128(_mm_load_ps(src
+i
*4)), seed
);
3899 #if (XXH_VECTOR == XXH_NEON)
3901 XXH_FORCE_INLINE
void
3902 XXH3_accumulate_512_neon( void* XXH_RESTRICT acc
,
3903 const void* XXH_RESTRICT input
,
3904 const void* XXH_RESTRICT secret
)
3906 XXH_ASSERT((((size_t)acc
) & 15) == 0);
3908 XXH_ALIGN(16) uint64x2_t
* const xacc
= (uint64x2_t
*) acc
;
3909 /* We don't use a uint32x4_t pointer because it causes bus errors on ARMv7. */
3910 uint8_t const* const xinput
= (const uint8_t *) input
;
3911 uint8_t const* const xsecret
= (const uint8_t *) secret
;
3914 for (i
=0; i
< XXH_STRIPE_LEN
/ sizeof(uint64x2_t
); i
++) {
3915 /* data_vec = xinput[i]; */
3916 uint8x16_t data_vec
= vld1q_u8(xinput
+ (i
* 16));
3917 /* key_vec = xsecret[i]; */
3918 uint8x16_t key_vec
= vld1q_u8(xsecret
+ (i
* 16));
3919 uint64x2_t data_key
;
3920 uint32x2_t data_key_lo
, data_key_hi
;
3921 /* xacc[i] += swap(data_vec); */
3922 uint64x2_t
const data64
= vreinterpretq_u64_u8(data_vec
);
3923 uint64x2_t
const swapped
= vextq_u64(data64
, data64
, 1);
3924 xacc
[i
] = vaddq_u64 (xacc
[i
], swapped
);
3925 /* data_key = data_vec ^ key_vec; */
3926 data_key
= vreinterpretq_u64_u8(veorq_u8(data_vec
, key_vec
));
3927 /* data_key_lo = (uint32x2_t) (data_key & 0xFFFFFFFF);
3928 * data_key_hi = (uint32x2_t) (data_key >> 32);
3929 * data_key = UNDEFINED; */
3930 XXH_SPLIT_IN_PLACE(data_key
, data_key_lo
, data_key_hi
);
3931 /* xacc[i] += (uint64x2_t) data_key_lo * (uint64x2_t) data_key_hi; */
3932 xacc
[i
] = vmlal_u32 (xacc
[i
], data_key_lo
, data_key_hi
);
3938 XXH_FORCE_INLINE
void
3939 XXH3_scrambleAcc_neon(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
3941 XXH_ASSERT((((size_t)acc
) & 15) == 0);
3943 { uint64x2_t
* xacc
= (uint64x2_t
*) acc
;
3944 uint8_t const* xsecret
= (uint8_t const*) secret
;
3945 uint32x2_t prime
= vdup_n_u32 (XXH_PRIME32_1
);
3948 for (i
=0; i
< XXH_STRIPE_LEN
/sizeof(uint64x2_t
); i
++) {
3949 /* xacc[i] ^= (xacc[i] >> 47); */
3950 uint64x2_t acc_vec
= xacc
[i
];
3951 uint64x2_t shifted
= vshrq_n_u64 (acc_vec
, 47);
3952 uint64x2_t data_vec
= veorq_u64 (acc_vec
, shifted
);
3954 /* xacc[i] ^= xsecret[i]; */
3955 uint8x16_t key_vec
= vld1q_u8(xsecret
+ (i
* 16));
3956 uint64x2_t data_key
= veorq_u64(data_vec
, vreinterpretq_u64_u8(key_vec
));
3958 /* xacc[i] *= XXH_PRIME32_1 */
3959 uint32x2_t data_key_lo
, data_key_hi
;
3960 /* data_key_lo = (uint32x2_t) (xacc[i] & 0xFFFFFFFF);
3961 * data_key_hi = (uint32x2_t) (xacc[i] >> 32);
3962 * xacc[i] = UNDEFINED; */
3963 XXH_SPLIT_IN_PLACE(data_key
, data_key_lo
, data_key_hi
);
3965 * prod_hi = (data_key >> 32) * XXH_PRIME32_1;
3967 * Avoid vmul_u32 + vshll_n_u32 since Clang 6 and 7 will
3968 * incorrectly "optimize" this:
3969 * tmp = vmul_u32(vmovn_u64(a), vmovn_u64(b));
3970 * shifted = vshll_n_u32(tmp, 32);
3972 * tmp = "vmulq_u64"(a, b); // no such thing!
3973 * shifted = vshlq_n_u64(tmp, 32);
3975 * However, unlike SSE, Clang lacks a 64-bit multiply routine
3976 * for NEON, and it scalarizes two 64-bit multiplies instead.
3978 * vmull_u32 has the same timing as vmul_u32, and it avoids
3979 * this bug completely.
3980 * See https://bugs.llvm.org/show_bug.cgi?id=39967
3982 uint64x2_t prod_hi
= vmull_u32 (data_key_hi
, prime
);
3983 /* xacc[i] = prod_hi << 32; */
3984 xacc
[i
] = vshlq_n_u64(prod_hi
, 32);
3985 /* xacc[i] += (prod_hi & 0xFFFFFFFF) * XXH_PRIME32_1; */
3986 xacc
[i
] = vmlal_u32(xacc
[i
], data_key_lo
, prime
);
3993 #if (XXH_VECTOR == XXH_VSX)
3995 XXH_FORCE_INLINE
void
3996 XXH3_accumulate_512_vsx( void* XXH_RESTRICT acc
,
3997 const void* XXH_RESTRICT input
,
3998 const void* XXH_RESTRICT secret
)
4000 xxh_u64x2
* const xacc
= (xxh_u64x2
*) acc
; /* presumed aligned */
4001 xxh_u64x2
const* const xinput
= (xxh_u64x2
const*) input
; /* no alignment restriction */
4002 xxh_u64x2
const* const xsecret
= (xxh_u64x2
const*) secret
; /* no alignment restriction */
4003 xxh_u64x2
const v32
= { 32, 32 };
4005 for (i
= 0; i
< XXH_STRIPE_LEN
/ sizeof(xxh_u64x2
); i
++) {
4006 /* data_vec = xinput[i]; */
4007 xxh_u64x2
const data_vec
= XXH_vec_loadu(xinput
+ i
);
4008 /* key_vec = xsecret[i]; */
4009 xxh_u64x2
const key_vec
= XXH_vec_loadu(xsecret
+ i
);
4010 xxh_u64x2
const data_key
= data_vec
^ key_vec
;
4011 /* shuffled = (data_key << 32) | (data_key >> 32); */
4012 xxh_u32x4
const shuffled
= (xxh_u32x4
)vec_rl(data_key
, v32
);
4013 /* product = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)shuffled & 0xFFFFFFFF); */
4014 xxh_u64x2
const product
= XXH_vec_mulo((xxh_u32x4
)data_key
, shuffled
);
4017 /* swap high and low halves */
4019 xacc
[i
] += vec_permi(data_vec
, data_vec
, 2);
4021 xacc
[i
] += vec_xxpermdi(data_vec
, data_vec
, 2);
4026 XXH_FORCE_INLINE
void
4027 XXH3_scrambleAcc_vsx(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
4029 XXH_ASSERT((((size_t)acc
) & 15) == 0);
4031 { xxh_u64x2
* const xacc
= (xxh_u64x2
*) acc
;
4032 const xxh_u64x2
* const xsecret
= (const xxh_u64x2
*) secret
;
4034 xxh_u64x2
const v32
= { 32, 32 };
4035 xxh_u64x2
const v47
= { 47, 47 };
4036 xxh_u32x4
const prime
= { XXH_PRIME32_1
, XXH_PRIME32_1
, XXH_PRIME32_1
, XXH_PRIME32_1
};
4038 for (i
= 0; i
< XXH_STRIPE_LEN
/ sizeof(xxh_u64x2
); i
++) {
4039 /* xacc[i] ^= (xacc[i] >> 47); */
4040 xxh_u64x2
const acc_vec
= xacc
[i
];
4041 xxh_u64x2
const data_vec
= acc_vec
^ (acc_vec
>> v47
);
4043 /* xacc[i] ^= xsecret[i]; */
4044 xxh_u64x2
const key_vec
= XXH_vec_loadu(xsecret
+ i
);
4045 xxh_u64x2
const data_key
= data_vec
^ key_vec
;
4047 /* xacc[i] *= XXH_PRIME32_1 */
4048 /* prod_lo = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)prime & 0xFFFFFFFF); */
4049 xxh_u64x2
const prod_even
= XXH_vec_mule((xxh_u32x4
)data_key
, prime
);
4050 /* prod_hi = ((xxh_u64x2)data_key >> 32) * ((xxh_u64x2)prime >> 32); */
4051 xxh_u64x2
const prod_odd
= XXH_vec_mulo((xxh_u32x4
)data_key
, prime
);
4052 xacc
[i
] = prod_odd
+ (prod_even
<< v32
);
4058 /* scalar variants - universal */
4060 XXH_FORCE_INLINE
void
4061 XXH3_accumulate_512_scalar(void* XXH_RESTRICT acc
,
4062 const void* XXH_RESTRICT input
,
4063 const void* XXH_RESTRICT secret
)
4065 XXH_ALIGN(XXH_ACC_ALIGN
) xxh_u64
* const xacc
= (xxh_u64
*) acc
; /* presumed aligned */
4066 const xxh_u8
* const xinput
= (const xxh_u8
*) input
; /* no alignment restriction */
4067 const xxh_u8
* const xsecret
= (const xxh_u8
*) secret
; /* no alignment restriction */
4069 XXH_ASSERT(((size_t)acc
& (XXH_ACC_ALIGN
-1)) == 0);
4070 for (i
=0; i
< XXH_ACC_NB
; i
++) {
4071 xxh_u64
const data_val
= XXH_readLE64(xinput
+ 8*i
);
4072 xxh_u64
const data_key
= data_val
^ XXH_readLE64(xsecret
+ i
*8);
4073 xacc
[i
^ 1] += data_val
; /* swap adjacent lanes */
4074 xacc
[i
] += XXH_mult32to64(data_key
& 0xFFFFFFFF, data_key
>> 32);
4078 XXH_FORCE_INLINE
void
4079 XXH3_scrambleAcc_scalar(void* XXH_RESTRICT acc
, const void* XXH_RESTRICT secret
)
4081 XXH_ALIGN(XXH_ACC_ALIGN
) xxh_u64
* const xacc
= (xxh_u64
*) acc
; /* presumed aligned */
4082 const xxh_u8
* const xsecret
= (const xxh_u8
*) secret
; /* no alignment restriction */
4084 XXH_ASSERT((((size_t)acc
) & (XXH_ACC_ALIGN
-1)) == 0);
4085 for (i
=0; i
< XXH_ACC_NB
; i
++) {
4086 xxh_u64
const key64
= XXH_readLE64(xsecret
+ 8*i
);
4087 xxh_u64 acc64
= xacc
[i
];
4088 acc64
= XXH_xorshift64(acc64
, 47);
4090 acc64
*= XXH_PRIME32_1
;
4095 XXH_FORCE_INLINE
void
4096 XXH3_initCustomSecret_scalar(void* XXH_RESTRICT customSecret
, xxh_u64 seed64
)
4099 * We need a separate pointer for the hack below,
4100 * which requires a non-const pointer.
4101 * Any decent compiler will optimize this out otherwise.
4103 const xxh_u8
* kSecretPtr
= XXH3_kSecret
;
4104 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE
& 15) == 0);
4106 #if defined(__clang__) && defined(__aarch64__)
4109 * Clang generates a bunch of MOV/MOVK pairs for aarch64, and they are
4110 * placed sequentially, in order, at the top of the unrolled loop.
4112 * While MOVK is great for generating constants (2 cycles for a 64-bit
4113 * constant compared to 4 cycles for LDR), long MOVK chains stall the
4114 * integer pipelines:
4123 * By forcing loads from memory (as the asm line causes Clang to assume
4124 * that XXH3_kSecretPtr has been changed), the pipelines are used more
4131 * XXH3_64bits_withSeed, len == 256, Snapdragon 835
4132 * without hack: 2654.4 MB/s
4133 * with hack: 3202.9 MB/s
4135 XXH_COMPILER_GUARD(kSecretPtr
);
4138 * Note: in debug mode, this overrides the asm optimization
4139 * and Clang will emit MOVK chains again.
4141 XXH_ASSERT(kSecretPtr
== XXH3_kSecret
);
4143 { int const nbRounds
= XXH_SECRET_DEFAULT_SIZE
/ 16;
4145 for (i
=0; i
< nbRounds
; i
++) {
4147 * The asm hack causes Clang to assume that kSecretPtr aliases with
4148 * customSecret, and on aarch64, this prevented LDP from merging two
4149 * loads together for free. Putting the loads together before the stores
4150 * properly generates LDP.
4152 xxh_u64 lo
= XXH_readLE64(kSecretPtr
+ 16*i
) + seed64
;
4153 xxh_u64 hi
= XXH_readLE64(kSecretPtr
+ 16*i
+ 8) - seed64
;
4154 XXH_writeLE64((xxh_u8
*)customSecret
+ 16*i
, lo
);
4155 XXH_writeLE64((xxh_u8
*)customSecret
+ 16*i
+ 8, hi
);
4160 typedef void (*XXH3_f_accumulate_512
)(void* XXH_RESTRICT
, const void*, const void*);
4161 typedef void (*XXH3_f_scrambleAcc
)(void* XXH_RESTRICT
, const void*);
4162 typedef void (*XXH3_f_initCustomSecret
)(void* XXH_RESTRICT
, xxh_u64
);
4165 #if (XXH_VECTOR == XXH_AVX512)
4167 #define XXH3_accumulate_512 XXH3_accumulate_512_avx512
4168 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx512
4169 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx512
4171 #elif (XXH_VECTOR == XXH_AVX2)
4173 #define XXH3_accumulate_512 XXH3_accumulate_512_avx2
4174 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx2
4175 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx2
4177 #elif (XXH_VECTOR == XXH_SSE2)
4179 #define XXH3_accumulate_512 XXH3_accumulate_512_sse2
4180 #define XXH3_scrambleAcc XXH3_scrambleAcc_sse2
4181 #define XXH3_initCustomSecret XXH3_initCustomSecret_sse2
4183 #elif (XXH_VECTOR == XXH_NEON)
4185 #define XXH3_accumulate_512 XXH3_accumulate_512_neon
4186 #define XXH3_scrambleAcc XXH3_scrambleAcc_neon
4187 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4189 #elif (XXH_VECTOR == XXH_VSX)
4191 #define XXH3_accumulate_512 XXH3_accumulate_512_vsx
4192 #define XXH3_scrambleAcc XXH3_scrambleAcc_vsx
4193 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4197 #define XXH3_accumulate_512 XXH3_accumulate_512_scalar
4198 #define XXH3_scrambleAcc XXH3_scrambleAcc_scalar
4199 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar
4205 #ifndef XXH_PREFETCH_DIST
4207 # define XXH_PREFETCH_DIST 320
4209 # if (XXH_VECTOR == XXH_AVX512)
4210 # define XXH_PREFETCH_DIST 512
4212 # define XXH_PREFETCH_DIST 384
4214 # endif /* __clang__ */
4215 #endif /* XXH_PREFETCH_DIST */
4219 * Loops over XXH3_accumulate_512().
4220 * Assumption: nbStripes will not overflow the secret size
4222 XXH_FORCE_INLINE
void
4223 XXH3_accumulate( xxh_u64
* XXH_RESTRICT acc
,
4224 const xxh_u8
* XXH_RESTRICT input
,
4225 const xxh_u8
* XXH_RESTRICT secret
,
4227 XXH3_f_accumulate_512 f_acc512
)
4230 for (n
= 0; n
< nbStripes
; n
++ ) {
4231 const xxh_u8
* const in
= input
+ n
*XXH_STRIPE_LEN
;
4232 XXH_PREFETCH(in
+ XXH_PREFETCH_DIST
);
4235 secret
+ n
*XXH_SECRET_CONSUME_RATE
);
4239 XXH_FORCE_INLINE
void
4240 XXH3_hashLong_internal_loop(xxh_u64
* XXH_RESTRICT acc
,
4241 const xxh_u8
* XXH_RESTRICT input
, size_t len
,
4242 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
4243 XXH3_f_accumulate_512 f_acc512
,
4244 XXH3_f_scrambleAcc f_scramble
)
4246 size_t const nbStripesPerBlock
= (secretSize
- XXH_STRIPE_LEN
) / XXH_SECRET_CONSUME_RATE
;
4247 size_t const block_len
= XXH_STRIPE_LEN
* nbStripesPerBlock
;
4248 size_t const nb_blocks
= (len
- 1) / block_len
;
4252 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
);
4254 for (n
= 0; n
< nb_blocks
; n
++) {
4255 XXH3_accumulate(acc
, input
+ n
*block_len
, secret
, nbStripesPerBlock
, f_acc512
);
4256 f_scramble(acc
, secret
+ secretSize
- XXH_STRIPE_LEN
);
4259 /* last partial block */
4260 XXH_ASSERT(len
> XXH_STRIPE_LEN
);
4261 { size_t const nbStripes
= ((len
- 1) - (block_len
* nb_blocks
)) / XXH_STRIPE_LEN
;
4262 XXH_ASSERT(nbStripes
<= (secretSize
/ XXH_SECRET_CONSUME_RATE
));
4263 XXH3_accumulate(acc
, input
+ nb_blocks
*block_len
, secret
, nbStripes
, f_acc512
);
4266 { const xxh_u8
* const p
= input
+ len
- XXH_STRIPE_LEN
;
4267 #define XXH_SECRET_LASTACC_START 7 /* not aligned on 8, last secret is different from acc & scrambler */
4268 f_acc512(acc
, p
, secret
+ secretSize
- XXH_STRIPE_LEN
- XXH_SECRET_LASTACC_START
);
4272 XXH_FORCE_INLINE xxh_u64
4273 XXH3_mix2Accs(const xxh_u64
* XXH_RESTRICT acc
, const xxh_u8
* XXH_RESTRICT secret
)
4275 return XXH3_mul128_fold64(
4276 acc
[0] ^ XXH_readLE64(secret
),
4277 acc
[1] ^ XXH_readLE64(secret
+8) );
4281 XXH3_mergeAccs(const xxh_u64
* XXH_RESTRICT acc
, const xxh_u8
* XXH_RESTRICT secret
, xxh_u64 start
)
4283 xxh_u64 result64
= start
;
4286 for (i
= 0; i
< 4; i
++) {
4287 result64
+= XXH3_mix2Accs(acc
+2*i
, secret
+ 16*i
);
4288 #if defined(__clang__) /* Clang */ \
4289 && (defined(__arm__) || defined(__thumb__)) /* ARMv7 */ \
4290 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \
4291 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */
4294 * Prevent autovectorization on Clang ARMv7-a. Exact same problem as
4295 * the one in XXH3_len_129to240_64b. Speeds up shorter keys > 240b.
4296 * XXH3_64bits, len == 256, Snapdragon 835:
4297 * without hack: 2063.7 MB/s
4298 * with hack: 2560.7 MB/s
4300 XXH_COMPILER_GUARD(result64
);
4304 return XXH3_avalanche(result64
);
4307 #define XXH3_INIT_ACC { XXH_PRIME32_3, XXH_PRIME64_1, XXH_PRIME64_2, XXH_PRIME64_3, \
4308 XXH_PRIME64_4, XXH_PRIME32_2, XXH_PRIME64_5, XXH_PRIME32_1 }
4310 XXH_FORCE_INLINE XXH64_hash_t
4311 XXH3_hashLong_64b_internal(const void* XXH_RESTRICT input
, size_t len
,
4312 const void* XXH_RESTRICT secret
, size_t secretSize
,
4313 XXH3_f_accumulate_512 f_acc512
,
4314 XXH3_f_scrambleAcc f_scramble
)
4316 XXH_ALIGN(XXH_ACC_ALIGN
) xxh_u64 acc
[XXH_ACC_NB
] = XXH3_INIT_ACC
;
4318 XXH3_hashLong_internal_loop(acc
, (const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, secretSize
, f_acc512
, f_scramble
);
4320 /* converge into final hash */
4321 XXH_STATIC_ASSERT(sizeof(acc
) == 64);
4322 /* do not align on 8, so that the secret is different from the accumulator */
4323 #define XXH_SECRET_MERGEACCS_START 11
4324 XXH_ASSERT(secretSize
>= sizeof(acc
) + XXH_SECRET_MERGEACCS_START
);
4325 return XXH3_mergeAccs(acc
, (const xxh_u8
*)secret
+ XXH_SECRET_MERGEACCS_START
, (xxh_u64
)len
* XXH_PRIME64_1
);
4329 * It's important for performance that XXH3_hashLong is not inlined.
4331 XXH_NO_INLINE XXH64_hash_t
4332 XXH3_hashLong_64b_withSecret(const void* XXH_RESTRICT input
, size_t len
,
4333 XXH64_hash_t seed64
, const xxh_u8
* XXH_RESTRICT secret
, size_t secretLen
)
4336 return XXH3_hashLong_64b_internal(input
, len
, secret
, secretLen
, XXH3_accumulate_512
, XXH3_scrambleAcc
);
4340 * It's important for performance that XXH3_hashLong is not inlined.
4341 * Since the function is not inlined, the compiler may not be able to understand that,
4342 * in some scenarios, its `secret` argument is actually a compile time constant.
4343 * This variant enforces that the compiler can detect that,
4344 * and uses this opportunity to streamline the generated code for better performance.
4346 XXH_NO_INLINE XXH64_hash_t
4347 XXH3_hashLong_64b_default(const void* XXH_RESTRICT input
, size_t len
,
4348 XXH64_hash_t seed64
, const xxh_u8
* XXH_RESTRICT secret
, size_t secretLen
)
4350 (void)seed64
; (void)secret
; (void)secretLen
;
4351 return XXH3_hashLong_64b_internal(input
, len
, XXH3_kSecret
, sizeof(XXH3_kSecret
), XXH3_accumulate_512
, XXH3_scrambleAcc
);
4355 * XXH3_hashLong_64b_withSeed():
4356 * Generate a custom key based on alteration of default XXH3_kSecret with the seed,
4357 * and then use this key for long mode hashing.
4359 * This operation is decently fast but nonetheless costs a little bit of time.
4360 * Try to avoid it whenever possible (typically when seed==0).
4362 * It's important for performance that XXH3_hashLong is not inlined. Not sure
4363 * why (uop cache maybe?), but the difference is large and easily measurable.
4365 XXH_FORCE_INLINE XXH64_hash_t
4366 XXH3_hashLong_64b_withSeed_internal(const void* input
, size_t len
,
4368 XXH3_f_accumulate_512 f_acc512
,
4369 XXH3_f_scrambleAcc f_scramble
,
4370 XXH3_f_initCustomSecret f_initSec
)
4373 return XXH3_hashLong_64b_internal(input
, len
,
4374 XXH3_kSecret
, sizeof(XXH3_kSecret
),
4375 f_acc512
, f_scramble
);
4376 { XXH_ALIGN(XXH_SEC_ALIGN
) xxh_u8 secret
[XXH_SECRET_DEFAULT_SIZE
];
4377 f_initSec(secret
, seed
);
4378 return XXH3_hashLong_64b_internal(input
, len
, secret
, sizeof(secret
),
4379 f_acc512
, f_scramble
);
4384 * It's important for performance that XXH3_hashLong is not inlined.
4386 XXH_NO_INLINE XXH64_hash_t
4387 XXH3_hashLong_64b_withSeed(const void* input
, size_t len
,
4388 XXH64_hash_t seed
, const xxh_u8
* secret
, size_t secretLen
)
4390 (void)secret
; (void)secretLen
;
4391 return XXH3_hashLong_64b_withSeed_internal(input
, len
, seed
,
4392 XXH3_accumulate_512
, XXH3_scrambleAcc
, XXH3_initCustomSecret
);
4396 typedef XXH64_hash_t (*XXH3_hashLong64_f
)(const void* XXH_RESTRICT
, size_t,
4397 XXH64_hash_t
, const xxh_u8
* XXH_RESTRICT
, size_t);
4399 XXH_FORCE_INLINE XXH64_hash_t
4400 XXH3_64bits_internal(const void* XXH_RESTRICT input
, size_t len
,
4401 XXH64_hash_t seed64
, const void* XXH_RESTRICT secret
, size_t secretLen
,
4402 XXH3_hashLong64_f f_hashLong
)
4404 XXH_ASSERT(secretLen
>= XXH3_SECRET_SIZE_MIN
);
4406 * If an action is to be taken if `secretLen` condition is not respected,
4407 * it should be done here.
4408 * For now, it's a contract pre-condition.
4409 * Adding a check and a branch here would cost performance at every hash.
4410 * Also, note that function signature doesn't offer room to return an error.
4413 return XXH3_len_0to16_64b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, seed64
);
4415 return XXH3_len_17to128_64b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, secretLen
, seed64
);
4416 if (len
<= XXH3_MIDSIZE_MAX
)
4417 return XXH3_len_129to240_64b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, secretLen
, seed64
);
4418 return f_hashLong(input
, len
, seed64
, (const xxh_u8
*)secret
, secretLen
);
4422 /* === Public entry point === */
4424 /*! @ingroup xxh3_family */
4425 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits(const void* input
, size_t len
)
4427 return XXH3_64bits_internal(input
, len
, 0, XXH3_kSecret
, sizeof(XXH3_kSecret
), XXH3_hashLong_64b_default
);
4430 /*! @ingroup xxh3_family */
4431 XXH_PUBLIC_API XXH64_hash_t
4432 XXH3_64bits_withSecret(const void* input
, size_t len
, const void* secret
, size_t secretSize
)
4434 return XXH3_64bits_internal(input
, len
, 0, secret
, secretSize
, XXH3_hashLong_64b_withSecret
);
4437 /*! @ingroup xxh3_family */
4438 XXH_PUBLIC_API XXH64_hash_t
4439 XXH3_64bits_withSeed(const void* input
, size_t len
, XXH64_hash_t seed
)
4441 return XXH3_64bits_internal(input
, len
, seed
, XXH3_kSecret
, sizeof(XXH3_kSecret
), XXH3_hashLong_64b_withSeed
);
4445 /* === XXH3 streaming === */
4448 * Malloc's a pointer that is always aligned to align.
4450 * This must be freed with `XXH_alignedFree()`.
4452 * malloc typically guarantees 16 byte alignment on 64-bit systems and 8 byte
4453 * alignment on 32-bit. This isn't enough for the 32 byte aligned loads in AVX2
4454 * or on 32-bit, the 16 byte aligned loads in SSE2 and NEON.
4456 * This underalignment previously caused a rather obvious crash which went
4457 * completely unnoticed due to XXH3_createState() not actually being tested.
4458 * Credit to RedSpah for noticing this bug.
4460 * The alignment is done manually: Functions like posix_memalign or _mm_malloc
4461 * are avoided: To maintain portability, we would have to write a fallback
4462 * like this anyways, and besides, testing for the existence of library
4463 * functions without relying on external build tools is impossible.
4465 * The method is simple: Overallocate, manually align, and store the offset
4466 * to the original behind the returned pointer.
4468 * Align must be a power of 2 and 8 <= align <= 128.
4470 static void* XXH_alignedMalloc(size_t s
, size_t align
)
4472 XXH_ASSERT(align
<= 128 && align
>= 8); /* range check */
4473 XXH_ASSERT((align
& (align
-1)) == 0); /* power of 2 */
4474 XXH_ASSERT(s
!= 0 && s
< (s
+ align
)); /* empty/overflow */
4475 { /* Overallocate to make room for manual realignment and an offset byte */
4476 xxh_u8
* base
= (xxh_u8
*)XXH_malloc(s
+ align
);
4479 * Get the offset needed to align this pointer.
4481 * Even if the returned pointer is aligned, there will always be
4482 * at least one byte to store the offset to the original pointer.
4484 size_t offset
= align
- ((size_t)base
& (align
- 1)); /* base % align */
4485 /* Add the offset for the now-aligned pointer */
4486 xxh_u8
* ptr
= base
+ offset
;
4488 XXH_ASSERT((size_t)ptr
% align
== 0);
4490 /* Store the offset immediately before the returned pointer. */
4491 ptr
[-1] = (xxh_u8
)offset
;
4498 * Frees an aligned pointer allocated by XXH_alignedMalloc(). Don't pass
4499 * normal malloc'd pointers, XXH_alignedMalloc has a specific data layout.
4501 static void XXH_alignedFree(void* p
)
4504 xxh_u8
* ptr
= (xxh_u8
*)p
;
4505 /* Get the offset byte we added in XXH_malloc. */
4506 xxh_u8 offset
= ptr
[-1];
4507 /* Free the original malloc'd pointer */
4508 xxh_u8
* base
= ptr
- offset
;
4512 /*! @ingroup xxh3_family */
4513 XXH_PUBLIC_API XXH3_state_t
* XXH3_createState(void)
4515 XXH3_state_t
* const state
= (XXH3_state_t
*)XXH_alignedMalloc(sizeof(XXH3_state_t
), 64);
4516 if (state
==NULL
) return NULL
;
4517 XXH3_INITSTATE(state
);
4521 /*! @ingroup xxh3_family */
4522 XXH_PUBLIC_API XXH_errorcode
XXH3_freeState(XXH3_state_t
* statePtr
)
4524 XXH_alignedFree(statePtr
);
4528 /*! @ingroup xxh3_family */
4530 XXH3_copyState(XXH3_state_t
* dst_state
, const XXH3_state_t
* src_state
)
4532 memcpy(dst_state
, src_state
, sizeof(*dst_state
));
4536 XXH3_reset_internal(XXH3_state_t
* statePtr
,
4538 const void* secret
, size_t secretSize
)
4540 size_t const initStart
= offsetof(XXH3_state_t
, bufferedSize
);
4541 size_t const initLength
= offsetof(XXH3_state_t
, nbStripesPerBlock
) - initStart
;
4542 XXH_ASSERT(offsetof(XXH3_state_t
, nbStripesPerBlock
) > initStart
);
4543 XXH_ASSERT(statePtr
!= NULL
);
4544 /* set members from bufferedSize to nbStripesPerBlock (excluded) to 0 */
4545 memset((char*)statePtr
+ initStart
, 0, initLength
);
4546 statePtr
->acc
[0] = XXH_PRIME32_3
;
4547 statePtr
->acc
[1] = XXH_PRIME64_1
;
4548 statePtr
->acc
[2] = XXH_PRIME64_2
;
4549 statePtr
->acc
[3] = XXH_PRIME64_3
;
4550 statePtr
->acc
[4] = XXH_PRIME64_4
;
4551 statePtr
->acc
[5] = XXH_PRIME32_2
;
4552 statePtr
->acc
[6] = XXH_PRIME64_5
;
4553 statePtr
->acc
[7] = XXH_PRIME32_1
;
4554 statePtr
->seed
= seed
;
4555 statePtr
->extSecret
= (const unsigned char*)secret
;
4556 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
);
4557 statePtr
->secretLimit
= secretSize
- XXH_STRIPE_LEN
;
4558 statePtr
->nbStripesPerBlock
= statePtr
->secretLimit
/ XXH_SECRET_CONSUME_RATE
;
4561 /*! @ingroup xxh3_family */
4562 XXH_PUBLIC_API XXH_errorcode
4563 XXH3_64bits_reset(XXH3_state_t
* statePtr
)
4565 if (statePtr
== NULL
) return XXH_ERROR
;
4566 XXH3_reset_internal(statePtr
, 0, XXH3_kSecret
, XXH_SECRET_DEFAULT_SIZE
);
4570 /*! @ingroup xxh3_family */
4571 XXH_PUBLIC_API XXH_errorcode
4572 XXH3_64bits_reset_withSecret(XXH3_state_t
* statePtr
, const void* secret
, size_t secretSize
)
4574 if (statePtr
== NULL
) return XXH_ERROR
;
4575 XXH3_reset_internal(statePtr
, 0, secret
, secretSize
);
4576 if (secret
== NULL
) return XXH_ERROR
;
4577 if (secretSize
< XXH3_SECRET_SIZE_MIN
) return XXH_ERROR
;
4581 /*! @ingroup xxh3_family */
4582 XXH_PUBLIC_API XXH_errorcode
4583 XXH3_64bits_reset_withSeed(XXH3_state_t
* statePtr
, XXH64_hash_t seed
)
4585 if (statePtr
== NULL
) return XXH_ERROR
;
4586 if (seed
==0) return XXH3_64bits_reset(statePtr
);
4587 if (seed
!= statePtr
->seed
) XXH3_initCustomSecret(statePtr
->customSecret
, seed
);
4588 XXH3_reset_internal(statePtr
, seed
, NULL
, XXH_SECRET_DEFAULT_SIZE
);
4592 /* Note : when XXH3_consumeStripes() is invoked,
4593 * there must be a guarantee that at least one more byte must be consumed from input
4594 * so that the function can blindly consume all stripes using the "normal" secret segment */
4595 XXH_FORCE_INLINE
void
4596 XXH3_consumeStripes(xxh_u64
* XXH_RESTRICT acc
,
4597 size_t* XXH_RESTRICT nbStripesSoFarPtr
, size_t nbStripesPerBlock
,
4598 const xxh_u8
* XXH_RESTRICT input
, size_t nbStripes
,
4599 const xxh_u8
* XXH_RESTRICT secret
, size_t secretLimit
,
4600 XXH3_f_accumulate_512 f_acc512
,
4601 XXH3_f_scrambleAcc f_scramble
)
4603 XXH_ASSERT(nbStripes
<= nbStripesPerBlock
); /* can handle max 1 scramble per invocation */
4604 XXH_ASSERT(*nbStripesSoFarPtr
< nbStripesPerBlock
);
4605 if (nbStripesPerBlock
- *nbStripesSoFarPtr
<= nbStripes
) {
4606 /* need a scrambling operation */
4607 size_t const nbStripesToEndofBlock
= nbStripesPerBlock
- *nbStripesSoFarPtr
;
4608 size_t const nbStripesAfterBlock
= nbStripes
- nbStripesToEndofBlock
;
4609 XXH3_accumulate(acc
, input
, secret
+ nbStripesSoFarPtr
[0] * XXH_SECRET_CONSUME_RATE
, nbStripesToEndofBlock
, f_acc512
);
4610 f_scramble(acc
, secret
+ secretLimit
);
4611 XXH3_accumulate(acc
, input
+ nbStripesToEndofBlock
* XXH_STRIPE_LEN
, secret
, nbStripesAfterBlock
, f_acc512
);
4612 *nbStripesSoFarPtr
= nbStripesAfterBlock
;
4614 XXH3_accumulate(acc
, input
, secret
+ nbStripesSoFarPtr
[0] * XXH_SECRET_CONSUME_RATE
, nbStripes
, f_acc512
);
4615 *nbStripesSoFarPtr
+= nbStripes
;
4620 * Both XXH3_64bits_update and XXH3_128bits_update use this routine.
4622 XXH_FORCE_INLINE XXH_errorcode
4623 XXH3_update(XXH3_state_t
* state
,
4624 const xxh_u8
* input
, size_t len
,
4625 XXH3_f_accumulate_512 f_acc512
,
4626 XXH3_f_scrambleAcc f_scramble
)
4629 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
4635 { const xxh_u8
* const bEnd
= input
+ len
;
4636 const unsigned char* const secret
= (state
->extSecret
== NULL
) ? state
->customSecret
: state
->extSecret
;
4638 state
->totalLen
+= len
;
4639 XXH_ASSERT(state
->bufferedSize
<= XXH3_INTERNALBUFFER_SIZE
);
4641 if (state
->bufferedSize
+ len
<= XXH3_INTERNALBUFFER_SIZE
) { /* fill in tmp buffer */
4642 XXH_memcpy(state
->buffer
+ state
->bufferedSize
, input
, len
);
4643 state
->bufferedSize
+= (XXH32_hash_t
)len
;
4646 /* total input is now > XXH3_INTERNALBUFFER_SIZE */
4648 #define XXH3_INTERNALBUFFER_STRIPES (XXH3_INTERNALBUFFER_SIZE / XXH_STRIPE_LEN)
4649 XXH_STATIC_ASSERT(XXH3_INTERNALBUFFER_SIZE
% XXH_STRIPE_LEN
== 0); /* clean multiple */
4652 * Internal buffer is partially filled (always, except at beginning)
4653 * Complete it, then consume it.
4655 if (state
->bufferedSize
) {
4656 size_t const loadSize
= XXH3_INTERNALBUFFER_SIZE
- state
->bufferedSize
;
4657 XXH_memcpy(state
->buffer
+ state
->bufferedSize
, input
, loadSize
);
4659 XXH3_consumeStripes(state
->acc
,
4660 &state
->nbStripesSoFar
, state
->nbStripesPerBlock
,
4661 state
->buffer
, XXH3_INTERNALBUFFER_STRIPES
,
4662 secret
, state
->secretLimit
,
4663 f_acc512
, f_scramble
);
4664 state
->bufferedSize
= 0;
4666 XXH_ASSERT(input
< bEnd
);
4668 /* Consume input by a multiple of internal buffer size */
4669 if (input
+XXH3_INTERNALBUFFER_SIZE
< bEnd
) {
4670 const xxh_u8
* const limit
= bEnd
- XXH3_INTERNALBUFFER_SIZE
;
4672 XXH3_consumeStripes(state
->acc
,
4673 &state
->nbStripesSoFar
, state
->nbStripesPerBlock
,
4674 input
, XXH3_INTERNALBUFFER_STRIPES
,
4675 secret
, state
->secretLimit
,
4676 f_acc512
, f_scramble
);
4677 input
+= XXH3_INTERNALBUFFER_SIZE
;
4678 } while (input
<limit
);
4679 /* for last partial stripe */
4680 memcpy(state
->buffer
+ sizeof(state
->buffer
) - XXH_STRIPE_LEN
, input
- XXH_STRIPE_LEN
, XXH_STRIPE_LEN
);
4682 XXH_ASSERT(input
< bEnd
);
4684 /* Some remaining input (always) : buffer it */
4685 XXH_memcpy(state
->buffer
, input
, (size_t)(bEnd
-input
));
4686 state
->bufferedSize
= (XXH32_hash_t
)(bEnd
-input
);
4692 /*! @ingroup xxh3_family */
4693 XXH_PUBLIC_API XXH_errorcode
4694 XXH3_64bits_update(XXH3_state_t
* state
, const void* input
, size_t len
)
4696 return XXH3_update(state
, (const xxh_u8
*)input
, len
,
4697 XXH3_accumulate_512
, XXH3_scrambleAcc
);
4701 XXH_FORCE_INLINE
void
4702 XXH3_digest_long (XXH64_hash_t
* acc
,
4703 const XXH3_state_t
* state
,
4704 const unsigned char* secret
)
4707 * Digest on a local copy. This way, the state remains unaltered, and it can
4708 * continue ingesting more input afterwards.
4710 memcpy(acc
, state
->acc
, sizeof(state
->acc
));
4711 if (state
->bufferedSize
>= XXH_STRIPE_LEN
) {
4712 size_t const nbStripes
= (state
->bufferedSize
- 1) / XXH_STRIPE_LEN
;
4713 size_t nbStripesSoFar
= state
->nbStripesSoFar
;
4714 XXH3_consumeStripes(acc
,
4715 &nbStripesSoFar
, state
->nbStripesPerBlock
,
4716 state
->buffer
, nbStripes
,
4717 secret
, state
->secretLimit
,
4718 XXH3_accumulate_512
, XXH3_scrambleAcc
);
4720 XXH3_accumulate_512(acc
,
4721 state
->buffer
+ state
->bufferedSize
- XXH_STRIPE_LEN
,
4722 secret
+ state
->secretLimit
- XXH_SECRET_LASTACC_START
);
4723 } else { /* bufferedSize < XXH_STRIPE_LEN */
4724 xxh_u8 lastStripe
[XXH_STRIPE_LEN
];
4725 size_t const catchupSize
= XXH_STRIPE_LEN
- state
->bufferedSize
;
4726 XXH_ASSERT(state
->bufferedSize
> 0); /* there is always some input buffered */
4727 memcpy(lastStripe
, state
->buffer
+ sizeof(state
->buffer
) - catchupSize
, catchupSize
);
4728 memcpy(lastStripe
+ catchupSize
, state
->buffer
, state
->bufferedSize
);
4729 XXH3_accumulate_512(acc
,
4731 secret
+ state
->secretLimit
- XXH_SECRET_LASTACC_START
);
4735 /*! @ingroup xxh3_family */
4736 XXH_PUBLIC_API XXH64_hash_t
XXH3_64bits_digest (const XXH3_state_t
* state
)
4738 const unsigned char* const secret
= (state
->extSecret
== NULL
) ? state
->customSecret
: state
->extSecret
;
4739 if (state
->totalLen
> XXH3_MIDSIZE_MAX
) {
4740 XXH_ALIGN(XXH_ACC_ALIGN
) XXH64_hash_t acc
[XXH_ACC_NB
];
4741 XXH3_digest_long(acc
, state
, secret
);
4742 return XXH3_mergeAccs(acc
,
4743 secret
+ XXH_SECRET_MERGEACCS_START
,
4744 (xxh_u64
)state
->totalLen
* XXH_PRIME64_1
);
4746 /* totalLen <= XXH3_MIDSIZE_MAX: digesting a short input */
4748 return XXH3_64bits_withSeed(state
->buffer
, (size_t)state
->totalLen
, state
->seed
);
4749 return XXH3_64bits_withSecret(state
->buffer
, (size_t)(state
->totalLen
),
4750 secret
, state
->secretLimit
+ XXH_STRIPE_LEN
);
4754 #define XXH_MIN(x, y) (((x) > (y)) ? (y) : (x))
4756 /*! @ingroup xxh3_family */
4758 XXH3_generateSecret(void* secretBuffer
, const void* customSeed
, size_t customSeedSize
)
4760 XXH_ASSERT(secretBuffer
!= NULL
);
4761 if (customSeedSize
== 0) {
4762 memcpy(secretBuffer
, XXH3_kSecret
, XXH_SECRET_DEFAULT_SIZE
);
4765 XXH_ASSERT(customSeed
!= NULL
);
4767 { size_t const segmentSize
= sizeof(XXH128_hash_t
);
4768 size_t const nbSegments
= XXH_SECRET_DEFAULT_SIZE
/ segmentSize
;
4769 XXH128_canonical_t scrambler
;
4770 XXH64_hash_t seeds
[12];
4772 XXH_ASSERT(nbSegments
== 12);
4773 XXH_ASSERT(segmentSize
* nbSegments
== XXH_SECRET_DEFAULT_SIZE
); /* exact multiple */
4774 XXH128_canonicalFromHash(&scrambler
, XXH128(customSeed
, customSeedSize
, 0));
4777 * Copy customSeed to seeds[], truncating or repeating as necessary.
4779 { size_t toFill
= XXH_MIN(customSeedSize
, sizeof(seeds
));
4780 size_t filled
= toFill
;
4781 memcpy(seeds
, customSeed
, toFill
);
4782 while (filled
< sizeof(seeds
)) {
4783 toFill
= XXH_MIN(filled
, sizeof(seeds
) - filled
);
4784 memcpy((char*)seeds
+ filled
, seeds
, toFill
);
4788 /* generate secret */
4789 memcpy(secretBuffer
, &scrambler
, sizeof(scrambler
));
4790 for (segnb
=1; segnb
< nbSegments
; segnb
++) {
4791 size_t const segmentStart
= segnb
* segmentSize
;
4792 XXH128_canonical_t segment
;
4793 XXH128_canonicalFromHash(&segment
,
4794 XXH128(&scrambler
, sizeof(scrambler
), XXH_readLE64(seeds
+ segnb
) + segnb
) );
4795 memcpy((char*)secretBuffer
+ segmentStart
, &segment
, sizeof(segment
));
4800 /* ==========================================
4801 * XXH3 128 bits (a.k.a XXH128)
4802 * ==========================================
4803 * XXH3's 128-bit variant has better mixing and strength than the 64-bit variant,
4804 * even without counting the significantly larger output size.
4806 * For example, extra steps are taken to avoid the seed-dependent collisions
4807 * in 17-240 byte inputs (See XXH3_mix16B and XXH128_mix32B).
4809 * This strength naturally comes at the cost of some speed, especially on short
4810 * lengths. Note that longer hashes are about as fast as the 64-bit version
4811 * due to it using only a slight modification of the 64-bit loop.
4813 * XXH128 is also more oriented towards 64-bit machines. It is still extremely
4814 * fast for a _128-bit_ hash on 32-bit (it usually clears XXH64).
4817 XXH_FORCE_INLINE XXH128_hash_t
4818 XXH3_len_1to3_128b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
4820 /* A doubled version of 1to3_64b with different constants. */
4821 XXH_ASSERT(input
!= NULL
);
4822 XXH_ASSERT(1 <= len
&& len
<= 3);
4823 XXH_ASSERT(secret
!= NULL
);
4825 * len = 1: combinedl = { input[0], 0x01, input[0], input[0] }
4826 * len = 2: combinedl = { input[1], 0x02, input[0], input[1] }
4827 * len = 3: combinedl = { input[2], 0x03, input[0], input[1] }
4829 { xxh_u8
const c1
= input
[0];
4830 xxh_u8
const c2
= input
[len
>> 1];
4831 xxh_u8
const c3
= input
[len
- 1];
4832 xxh_u32
const combinedl
= ((xxh_u32
)c1
<<16) | ((xxh_u32
)c2
<< 24)
4833 | ((xxh_u32
)c3
<< 0) | ((xxh_u32
)len
<< 8);
4834 xxh_u32
const combinedh
= XXH_rotl32(XXH_swap32(combinedl
), 13);
4835 xxh_u64
const bitflipl
= (XXH_readLE32(secret
) ^ XXH_readLE32(secret
+4)) + seed
;
4836 xxh_u64
const bitfliph
= (XXH_readLE32(secret
+8) ^ XXH_readLE32(secret
+12)) - seed
;
4837 xxh_u64
const keyed_lo
= (xxh_u64
)combinedl
^ bitflipl
;
4838 xxh_u64
const keyed_hi
= (xxh_u64
)combinedh
^ bitfliph
;
4840 h128
.low64
= XXH64_avalanche(keyed_lo
);
4841 h128
.high64
= XXH64_avalanche(keyed_hi
);
4846 XXH_FORCE_INLINE XXH128_hash_t
4847 XXH3_len_4to8_128b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
4849 XXH_ASSERT(input
!= NULL
);
4850 XXH_ASSERT(secret
!= NULL
);
4851 XXH_ASSERT(4 <= len
&& len
<= 8);
4852 seed
^= (xxh_u64
)XXH_swap32((xxh_u32
)seed
) << 32;
4853 { xxh_u32
const input_lo
= XXH_readLE32(input
);
4854 xxh_u32
const input_hi
= XXH_readLE32(input
+ len
- 4);
4855 xxh_u64
const input_64
= input_lo
+ ((xxh_u64
)input_hi
<< 32);
4856 xxh_u64
const bitflip
= (XXH_readLE64(secret
+16) ^ XXH_readLE64(secret
+24)) + seed
;
4857 xxh_u64
const keyed
= input_64
^ bitflip
;
4859 /* Shift len to the left to ensure it is even, this avoids even multiplies. */
4860 XXH128_hash_t m128
= XXH_mult64to128(keyed
, XXH_PRIME64_1
+ (len
<< 2));
4862 m128
.high64
+= (m128
.low64
<< 1);
4863 m128
.low64
^= (m128
.high64
>> 3);
4865 m128
.low64
= XXH_xorshift64(m128
.low64
, 35);
4866 m128
.low64
*= 0x9FB21C651E98DF25ULL
;
4867 m128
.low64
= XXH_xorshift64(m128
.low64
, 28);
4868 m128
.high64
= XXH3_avalanche(m128
.high64
);
4873 XXH_FORCE_INLINE XXH128_hash_t
4874 XXH3_len_9to16_128b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
4876 XXH_ASSERT(input
!= NULL
);
4877 XXH_ASSERT(secret
!= NULL
);
4878 XXH_ASSERT(9 <= len
&& len
<= 16);
4879 { xxh_u64
const bitflipl
= (XXH_readLE64(secret
+32) ^ XXH_readLE64(secret
+40)) - seed
;
4880 xxh_u64
const bitfliph
= (XXH_readLE64(secret
+48) ^ XXH_readLE64(secret
+56)) + seed
;
4881 xxh_u64
const input_lo
= XXH_readLE64(input
);
4882 xxh_u64 input_hi
= XXH_readLE64(input
+ len
- 8);
4883 XXH128_hash_t m128
= XXH_mult64to128(input_lo
^ input_hi
^ bitflipl
, XXH_PRIME64_1
);
4885 * Put len in the middle of m128 to ensure that the length gets mixed to
4886 * both the low and high bits in the 128x64 multiply below.
4888 m128
.low64
+= (xxh_u64
)(len
- 1) << 54;
4889 input_hi
^= bitfliph
;
4891 * Add the high 32 bits of input_hi to the high 32 bits of m128, then
4892 * add the long product of the low 32 bits of input_hi and XXH_PRIME32_2 to
4893 * the high 64 bits of m128.
4895 * The best approach to this operation is different on 32-bit and 64-bit.
4897 if (sizeof(void *) < sizeof(xxh_u64
)) { /* 32-bit */
4899 * 32-bit optimized version, which is more readable.
4901 * On 32-bit, it removes an ADC and delays a dependency between the two
4902 * halves of m128.high64, but it generates an extra mask on 64-bit.
4904 m128
.high64
+= (input_hi
& 0xFFFFFFFF00000000ULL
) + XXH_mult32to64((xxh_u32
)input_hi
, XXH_PRIME32_2
);
4907 * 64-bit optimized (albeit more confusing) version.
4909 * Uses some properties of addition and multiplication to remove the mask:
4912 * a = input_hi.lo = (input_hi & 0x00000000FFFFFFFF)
4913 * b = input_hi.hi = (input_hi & 0xFFFFFFFF00000000)
4917 * Inverse Property: x + y - x == y
4918 * a + (b * (1 + c - 1))
4919 * Distributive Property: x * (y + z) == (x * y) + (x * z)
4920 * a + (b * 1) + (b * (c - 1))
4921 * Identity Property: x * 1 == x
4922 * a + b + (b * (c - 1))
4924 * Substitute a, b, and c:
4925 * input_hi.hi + input_hi.lo + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1))
4927 * Since input_hi.hi + input_hi.lo == input_hi, we get this:
4928 * input_hi + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1))
4930 m128
.high64
+= input_hi
+ XXH_mult32to64((xxh_u32
)input_hi
, XXH_PRIME32_2
- 1);
4932 /* m128 ^= XXH_swap64(m128 >> 64); */
4933 m128
.low64
^= XXH_swap64(m128
.high64
);
4935 { /* 128x64 multiply: h128 = m128 * XXH_PRIME64_2; */
4936 XXH128_hash_t h128
= XXH_mult64to128(m128
.low64
, XXH_PRIME64_2
);
4937 h128
.high64
+= m128
.high64
* XXH_PRIME64_2
;
4939 h128
.low64
= XXH3_avalanche(h128
.low64
);
4940 h128
.high64
= XXH3_avalanche(h128
.high64
);
4946 * Assumption: `secret` size is >= XXH3_SECRET_SIZE_MIN
4948 XXH_FORCE_INLINE XXH128_hash_t
4949 XXH3_len_0to16_128b(const xxh_u8
* input
, size_t len
, const xxh_u8
* secret
, XXH64_hash_t seed
)
4951 XXH_ASSERT(len
<= 16);
4952 { if (len
> 8) return XXH3_len_9to16_128b(input
, len
, secret
, seed
);
4953 if (len
>= 4) return XXH3_len_4to8_128b(input
, len
, secret
, seed
);
4954 if (len
) return XXH3_len_1to3_128b(input
, len
, secret
, seed
);
4955 { XXH128_hash_t h128
;
4956 xxh_u64
const bitflipl
= XXH_readLE64(secret
+64) ^ XXH_readLE64(secret
+72);
4957 xxh_u64
const bitfliph
= XXH_readLE64(secret
+80) ^ XXH_readLE64(secret
+88);
4958 h128
.low64
= XXH64_avalanche(seed
^ bitflipl
);
4959 h128
.high64
= XXH64_avalanche( seed
^ bitfliph
);
4965 * A bit slower than XXH3_mix16B, but handles multiply by zero better.
4967 XXH_FORCE_INLINE XXH128_hash_t
4968 XXH128_mix32B(XXH128_hash_t acc
, const xxh_u8
* input_1
, const xxh_u8
* input_2
,
4969 const xxh_u8
* secret
, XXH64_hash_t seed
)
4971 acc
.low64
+= XXH3_mix16B (input_1
, secret
+0, seed
);
4972 acc
.low64
^= XXH_readLE64(input_2
) + XXH_readLE64(input_2
+ 8);
4973 acc
.high64
+= XXH3_mix16B (input_2
, secret
+16, seed
);
4974 acc
.high64
^= XXH_readLE64(input_1
) + XXH_readLE64(input_1
+ 8);
4979 XXH_FORCE_INLINE XXH128_hash_t
4980 XXH3_len_17to128_128b(const xxh_u8
* XXH_RESTRICT input
, size_t len
,
4981 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
4984 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
); (void)secretSize
;
4985 XXH_ASSERT(16 < len
&& len
<= 128);
4987 { XXH128_hash_t acc
;
4988 acc
.low64
= len
* XXH_PRIME64_1
;
4993 acc
= XXH128_mix32B(acc
, input
+48, input
+len
-64, secret
+96, seed
);
4995 acc
= XXH128_mix32B(acc
, input
+32, input
+len
-48, secret
+64, seed
);
4997 acc
= XXH128_mix32B(acc
, input
+16, input
+len
-32, secret
+32, seed
);
4999 acc
= XXH128_mix32B(acc
, input
, input
+len
-16, secret
, seed
);
5000 { XXH128_hash_t h128
;
5001 h128
.low64
= acc
.low64
+ acc
.high64
;
5002 h128
.high64
= (acc
.low64
* XXH_PRIME64_1
)
5003 + (acc
.high64
* XXH_PRIME64_4
)
5004 + ((len
- seed
) * XXH_PRIME64_2
);
5005 h128
.low64
= XXH3_avalanche(h128
.low64
);
5006 h128
.high64
= (XXH64_hash_t
)0 - XXH3_avalanche(h128
.high64
);
5012 XXH_NO_INLINE XXH128_hash_t
5013 XXH3_len_129to240_128b(const xxh_u8
* XXH_RESTRICT input
, size_t len
,
5014 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
5017 XXH_ASSERT(secretSize
>= XXH3_SECRET_SIZE_MIN
); (void)secretSize
;
5018 XXH_ASSERT(128 < len
&& len
<= XXH3_MIDSIZE_MAX
);
5020 { XXH128_hash_t acc
;
5021 int const nbRounds
= (int)len
/ 32;
5023 acc
.low64
= len
* XXH_PRIME64_1
;
5025 for (i
=0; i
<4; i
++) {
5026 acc
= XXH128_mix32B(acc
,
5028 input
+ (32 * i
) + 16,
5032 acc
.low64
= XXH3_avalanche(acc
.low64
);
5033 acc
.high64
= XXH3_avalanche(acc
.high64
);
5034 XXH_ASSERT(nbRounds
>= 4);
5035 for (i
=4 ; i
< nbRounds
; i
++) {
5036 acc
= XXH128_mix32B(acc
,
5038 input
+ (32 * i
) + 16,
5039 secret
+ XXH3_MIDSIZE_STARTOFFSET
+ (32 * (i
- 4)),
5043 acc
= XXH128_mix32B(acc
,
5046 secret
+ XXH3_SECRET_SIZE_MIN
- XXH3_MIDSIZE_LASTOFFSET
- 16,
5049 { XXH128_hash_t h128
;
5050 h128
.low64
= acc
.low64
+ acc
.high64
;
5051 h128
.high64
= (acc
.low64
* XXH_PRIME64_1
)
5052 + (acc
.high64
* XXH_PRIME64_4
)
5053 + ((len
- seed
) * XXH_PRIME64_2
);
5054 h128
.low64
= XXH3_avalanche(h128
.low64
);
5055 h128
.high64
= (XXH64_hash_t
)0 - XXH3_avalanche(h128
.high64
);
5061 XXH_FORCE_INLINE XXH128_hash_t
5062 XXH3_hashLong_128b_internal(const void* XXH_RESTRICT input
, size_t len
,
5063 const xxh_u8
* XXH_RESTRICT secret
, size_t secretSize
,
5064 XXH3_f_accumulate_512 f_acc512
,
5065 XXH3_f_scrambleAcc f_scramble
)
5067 XXH_ALIGN(XXH_ACC_ALIGN
) xxh_u64 acc
[XXH_ACC_NB
] = XXH3_INIT_ACC
;
5069 XXH3_hashLong_internal_loop(acc
, (const xxh_u8
*)input
, len
, secret
, secretSize
, f_acc512
, f_scramble
);
5071 /* converge into final hash */
5072 XXH_STATIC_ASSERT(sizeof(acc
) == 64);
5073 XXH_ASSERT(secretSize
>= sizeof(acc
) + XXH_SECRET_MERGEACCS_START
);
5074 { XXH128_hash_t h128
;
5075 h128
.low64
= XXH3_mergeAccs(acc
,
5076 secret
+ XXH_SECRET_MERGEACCS_START
,
5077 (xxh_u64
)len
* XXH_PRIME64_1
);
5078 h128
.high64
= XXH3_mergeAccs(acc
,
5080 - sizeof(acc
) - XXH_SECRET_MERGEACCS_START
,
5081 ~((xxh_u64
)len
* XXH_PRIME64_2
));
5087 * It's important for performance that XXH3_hashLong is not inlined.
5089 XXH_NO_INLINE XXH128_hash_t
5090 XXH3_hashLong_128b_default(const void* XXH_RESTRICT input
, size_t len
,
5091 XXH64_hash_t seed64
,
5092 const void* XXH_RESTRICT secret
, size_t secretLen
)
5094 (void)seed64
; (void)secret
; (void)secretLen
;
5095 return XXH3_hashLong_128b_internal(input
, len
, XXH3_kSecret
, sizeof(XXH3_kSecret
),
5096 XXH3_accumulate_512
, XXH3_scrambleAcc
);
5100 * It's important for performance that XXH3_hashLong is not inlined.
5102 XXH_NO_INLINE XXH128_hash_t
5103 XXH3_hashLong_128b_withSecret(const void* XXH_RESTRICT input
, size_t len
,
5104 XXH64_hash_t seed64
,
5105 const void* XXH_RESTRICT secret
, size_t secretLen
)
5108 return XXH3_hashLong_128b_internal(input
, len
, (const xxh_u8
*)secret
, secretLen
,
5109 XXH3_accumulate_512
, XXH3_scrambleAcc
);
5112 XXH_FORCE_INLINE XXH128_hash_t
5113 XXH3_hashLong_128b_withSeed_internal(const void* XXH_RESTRICT input
, size_t len
,
5114 XXH64_hash_t seed64
,
5115 XXH3_f_accumulate_512 f_acc512
,
5116 XXH3_f_scrambleAcc f_scramble
,
5117 XXH3_f_initCustomSecret f_initSec
)
5120 return XXH3_hashLong_128b_internal(input
, len
,
5121 XXH3_kSecret
, sizeof(XXH3_kSecret
),
5122 f_acc512
, f_scramble
);
5123 { XXH_ALIGN(XXH_SEC_ALIGN
) xxh_u8 secret
[XXH_SECRET_DEFAULT_SIZE
];
5124 f_initSec(secret
, seed64
);
5125 return XXH3_hashLong_128b_internal(input
, len
, (const xxh_u8
*)secret
, sizeof(secret
),
5126 f_acc512
, f_scramble
);
5131 * It's important for performance that XXH3_hashLong is not inlined.
5133 XXH_NO_INLINE XXH128_hash_t
5134 XXH3_hashLong_128b_withSeed(const void* input
, size_t len
,
5135 XXH64_hash_t seed64
, const void* XXH_RESTRICT secret
, size_t secretLen
)
5137 (void)secret
; (void)secretLen
;
5138 return XXH3_hashLong_128b_withSeed_internal(input
, len
, seed64
,
5139 XXH3_accumulate_512
, XXH3_scrambleAcc
, XXH3_initCustomSecret
);
5142 typedef XXH128_hash_t (*XXH3_hashLong128_f
)(const void* XXH_RESTRICT
, size_t,
5143 XXH64_hash_t
, const void* XXH_RESTRICT
, size_t);
5145 XXH_FORCE_INLINE XXH128_hash_t
5146 XXH3_128bits_internal(const void* input
, size_t len
,
5147 XXH64_hash_t seed64
, const void* XXH_RESTRICT secret
, size_t secretLen
,
5148 XXH3_hashLong128_f f_hl128
)
5150 XXH_ASSERT(secretLen
>= XXH3_SECRET_SIZE_MIN
);
5152 * If an action is to be taken if `secret` conditions are not respected,
5153 * it should be done here.
5154 * For now, it's a contract pre-condition.
5155 * Adding a check and a branch here would cost performance at every hash.
5158 return XXH3_len_0to16_128b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, seed64
);
5160 return XXH3_len_17to128_128b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, secretLen
, seed64
);
5161 if (len
<= XXH3_MIDSIZE_MAX
)
5162 return XXH3_len_129to240_128b((const xxh_u8
*)input
, len
, (const xxh_u8
*)secret
, secretLen
, seed64
);
5163 return f_hl128(input
, len
, seed64
, secret
, secretLen
);
5167 /* === Public XXH128 API === */
5169 /*! @ingroup xxh3_family */
5170 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits(const void* input
, size_t len
)
5172 return XXH3_128bits_internal(input
, len
, 0,
5173 XXH3_kSecret
, sizeof(XXH3_kSecret
),
5174 XXH3_hashLong_128b_default
);
5177 /*! @ingroup xxh3_family */
5178 XXH_PUBLIC_API XXH128_hash_t
5179 XXH3_128bits_withSecret(const void* input
, size_t len
, const void* secret
, size_t secretSize
)
5181 return XXH3_128bits_internal(input
, len
, 0,
5182 (const xxh_u8
*)secret
, secretSize
,
5183 XXH3_hashLong_128b_withSecret
);
5186 /*! @ingroup xxh3_family */
5187 XXH_PUBLIC_API XXH128_hash_t
5188 XXH3_128bits_withSeed(const void* input
, size_t len
, XXH64_hash_t seed
)
5190 return XXH3_128bits_internal(input
, len
, seed
,
5191 XXH3_kSecret
, sizeof(XXH3_kSecret
),
5192 XXH3_hashLong_128b_withSeed
);
5195 /*! @ingroup xxh3_family */
5196 XXH_PUBLIC_API XXH128_hash_t
5197 XXH128(const void* input
, size_t len
, XXH64_hash_t seed
)
5199 return XXH3_128bits_withSeed(input
, len
, seed
);
5203 /* === XXH3 128-bit streaming === */
5206 * All the functions are actually the same as for 64-bit streaming variant.
5207 * The only difference is the finalization routine.
5210 /*! @ingroup xxh3_family */
5211 XXH_PUBLIC_API XXH_errorcode
5212 XXH3_128bits_reset(XXH3_state_t
* statePtr
)
5214 if (statePtr
== NULL
) return XXH_ERROR
;
5215 XXH3_reset_internal(statePtr
, 0, XXH3_kSecret
, XXH_SECRET_DEFAULT_SIZE
);
5219 /*! @ingroup xxh3_family */
5220 XXH_PUBLIC_API XXH_errorcode
5221 XXH3_128bits_reset_withSecret(XXH3_state_t
* statePtr
, const void* secret
, size_t secretSize
)
5223 if (statePtr
== NULL
) return XXH_ERROR
;
5224 XXH3_reset_internal(statePtr
, 0, secret
, secretSize
);
5225 if (secret
== NULL
) return XXH_ERROR
;
5226 if (secretSize
< XXH3_SECRET_SIZE_MIN
) return XXH_ERROR
;
5230 /*! @ingroup xxh3_family */
5231 XXH_PUBLIC_API XXH_errorcode
5232 XXH3_128bits_reset_withSeed(XXH3_state_t
* statePtr
, XXH64_hash_t seed
)
5234 if (statePtr
== NULL
) return XXH_ERROR
;
5235 if (seed
==0) return XXH3_128bits_reset(statePtr
);
5236 if (seed
!= statePtr
->seed
) XXH3_initCustomSecret(statePtr
->customSecret
, seed
);
5237 XXH3_reset_internal(statePtr
, seed
, NULL
, XXH_SECRET_DEFAULT_SIZE
);
5241 /*! @ingroup xxh3_family */
5242 XXH_PUBLIC_API XXH_errorcode
5243 XXH3_128bits_update(XXH3_state_t
* state
, const void* input
, size_t len
)
5245 return XXH3_update(state
, (const xxh_u8
*)input
, len
,
5246 XXH3_accumulate_512
, XXH3_scrambleAcc
);
5249 /*! @ingroup xxh3_family */
5250 XXH_PUBLIC_API XXH128_hash_t
XXH3_128bits_digest (const XXH3_state_t
* state
)
5252 const unsigned char* const secret
= (state
->extSecret
== NULL
) ? state
->customSecret
: state
->extSecret
;
5253 if (state
->totalLen
> XXH3_MIDSIZE_MAX
) {
5254 XXH_ALIGN(XXH_ACC_ALIGN
) XXH64_hash_t acc
[XXH_ACC_NB
];
5255 XXH3_digest_long(acc
, state
, secret
);
5256 XXH_ASSERT(state
->secretLimit
+ XXH_STRIPE_LEN
>= sizeof(acc
) + XXH_SECRET_MERGEACCS_START
);
5257 { XXH128_hash_t h128
;
5258 h128
.low64
= XXH3_mergeAccs(acc
,
5259 secret
+ XXH_SECRET_MERGEACCS_START
,
5260 (xxh_u64
)state
->totalLen
* XXH_PRIME64_1
);
5261 h128
.high64
= XXH3_mergeAccs(acc
,
5262 secret
+ state
->secretLimit
+ XXH_STRIPE_LEN
5263 - sizeof(acc
) - XXH_SECRET_MERGEACCS_START
,
5264 ~((xxh_u64
)state
->totalLen
* XXH_PRIME64_2
));
5268 /* len <= XXH3_MIDSIZE_MAX : short code */
5270 return XXH3_128bits_withSeed(state
->buffer
, (size_t)state
->totalLen
, state
->seed
);
5271 return XXH3_128bits_withSecret(state
->buffer
, (size_t)(state
->totalLen
),
5272 secret
, state
->secretLimit
+ XXH_STRIPE_LEN
);
5275 /* 128-bit utility functions */
5277 #include <string.h> /* memcmp, memcpy */
5279 /* return : 1 is equal, 0 if different */
5280 /*! @ingroup xxh3_family */
5281 XXH_PUBLIC_API
int XXH128_isEqual(XXH128_hash_t h1
, XXH128_hash_t h2
)
5283 /* note : XXH128_hash_t is compact, it has no padding byte */
5284 return !(memcmp(&h1
, &h2
, sizeof(h1
)));
5287 /* This prototype is compatible with stdlib's qsort().
5288 * return : >0 if *h128_1 > *h128_2
5289 * <0 if *h128_1 < *h128_2
5290 * =0 if *h128_1 == *h128_2 */
5291 /*! @ingroup xxh3_family */
5292 XXH_PUBLIC_API
int XXH128_cmp(const void* h128_1
, const void* h128_2
)
5294 XXH128_hash_t
const h1
= *(const XXH128_hash_t
*)h128_1
;
5295 XXH128_hash_t
const h2
= *(const XXH128_hash_t
*)h128_2
;
5296 int const hcmp
= (h1
.high64
> h2
.high64
) - (h2
.high64
> h1
.high64
);
5297 /* note : bets that, in most cases, hash values are different */
5298 if (hcmp
) return hcmp
;
5299 return (h1
.low64
> h2
.low64
) - (h2
.low64
> h1
.low64
);
5303 /*====== Canonical representation ======*/
5304 /*! @ingroup xxh3_family */
5306 XXH128_canonicalFromHash(XXH128_canonical_t
* dst
, XXH128_hash_t hash
)
5308 XXH_STATIC_ASSERT(sizeof(XXH128_canonical_t
) == sizeof(XXH128_hash_t
));
5309 if (XXH_CPU_LITTLE_ENDIAN
) {
5310 hash
.high64
= XXH_swap64(hash
.high64
);
5311 hash
.low64
= XXH_swap64(hash
.low64
);
5313 memcpy(dst
, &hash
.high64
, sizeof(hash
.high64
));
5314 memcpy((char*)dst
+ sizeof(hash
.high64
), &hash
.low64
, sizeof(hash
.low64
));
5317 /*! @ingroup xxh3_family */
5318 XXH_PUBLIC_API XXH128_hash_t
5319 XXH128_hashFromCanonical(const XXH128_canonical_t
* src
)
5322 h
.high64
= XXH_readBE64(src
);
5323 h
.low64
= XXH_readBE64(src
->digest
+ 8);
5327 /* Pop our optimization override from above */
5328 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \
5329 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \
5330 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */
5331 # pragma GCC pop_options
5334 #endif /* XXH_NO_LONG_LONG */
5336 #endif /* XXH_NO_XXH3 */
5341 #endif /* XXH_IMPLEMENTATION */
5344 #if defined (__cplusplus)