2 xxHash - Extremely Fast Hash algorithm
4 Copyright (C) 2012-2016, Yann Collet.
6 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are
12 * Redistributions of source code must retain the above copyright
13 notice, this list of conditions and the following disclaimer.
14 * Redistributions in binary form must reproduce the above
15 copyright notice, this list of conditions and the following disclaimer
16 in the documentation and/or other materials provided with the
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 You can contact the author at :
32 - xxHash source repository : https://github.com/Cyan4973/xxHash
35 /* Notice extracted from xxHash homepage :
37 xxHash is an extremely fast Hash algorithm, running at RAM speed limits.
38 It also successfully passes all tests from the SMHasher suite.
40 Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz)
42 Name Speed Q.Score Author
44 CrapWow 3.2 GB/s 2 Andrew
45 MumurHash 3a 2.7 GB/s 10 Austin Appleby
46 SpookyHash 2.0 GB/s 10 Bob Jenkins
47 SBox 1.4 GB/s 9 Bret Mulvey
48 Lookup3 1.2 GB/s 9 Bob Jenkins
49 SuperFastHash 1.2 GB/s 1 Paul Hsieh
50 CityHash64 1.05 GB/s 10 Pike & Alakuijala
51 FNV 0.55 GB/s 5 Fowler, Noll, Vo
53 MD5-32 0.33 GB/s 10 Ronald L. Rivest
56 Q.Score is a measure of quality of the hash function.
57 It depends on successfully passing SMHasher test set.
58 10 is a perfect score.
60 Note : SMHasher's CRC32 implementation is not the fastest one.
61 Other speed-oriented implementations can be faster,
62 especially in combination with PCLMUL instruction :
63 http://fastcompression.blogspot.com/2019/03/presenting-xxh3.html?showComment=1552696407071#c3490092340461170735
65 A 64-bit version, named XXH64, is available since r35.
66 It offers much better speed, but for 64-bit applications only.
67 Name Speed on 64 bits Speed on 32 bits
68 XXH64 13.8 GB/s 1.9 GB/s
69 XXH32 6.8 GB/s 6.0 GB/s
72 #if defined (__cplusplus)
77 #ifndef XXHASH_H_5627135585666179
78 #define XXHASH_H_5627135585666179 1
80 /* ****************************
82 ******************************/
83 /** XXH_INLINE_ALL (and XXH_PRIVATE_API)
84 * This build macro includes xxhash functions in `static` mode
85 * in order to inline them, and remove their symbol from the public list.
86 * Inlining offers great performance improvement on small keys,
87 * and dramatic ones when length is expressed as a compile-time constant.
88 * See https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html .
90 * #define XXH_INLINE_ALL
92 * `xxhash.c` is automatically included.
93 * It's not useful to compile and link it as a separate object.
95 #if defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)
96 # ifndef XXH_STATIC_LINKING_ONLY
97 # define XXH_STATIC_LINKING_ONLY
99 # if defined(__GNUC__)
100 # define XXH_PUBLIC_API static __inline __attribute__((unused))
101 # elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */)
102 # define XXH_PUBLIC_API static inline
103 # elif defined(_MSC_VER)
104 # define XXH_PUBLIC_API static __inline
106 /* this version may generate warnings for unused static functions */
107 # define XXH_PUBLIC_API static
110 # if defined(WIN32) && defined(_MSC_VER) && (defined(XXH_IMPORT) || defined(XXH_EXPORT))
112 # define XXH_PUBLIC_API __declspec(dllexport)
114 # define XXH_PUBLIC_API __declspec(dllimport)
117 # define XXH_PUBLIC_API /* do nothing */
119 #endif /* XXH_INLINE_ALL || XXH_PRIVATE_API */
121 /*! XXH_NAMESPACE, aka Namespace Emulation :
123 * If you want to include _and expose_ xxHash functions from within your own library,
124 * but also want to avoid symbol collisions with other libraries which may also include xxHash,
126 * you can use XXH_NAMESPACE, to automatically prefix any public symbol from xxhash library
127 * with the value of XXH_NAMESPACE (therefore, avoid NULL and numeric values).
129 * Note that no change is required within the calling program as long as it includes `xxhash.h` :
130 * regular symbol name will be automatically translated by this header.
133 # define XXH_CAT(A,B) A##B
134 # define XXH_NAME2(A,B) XXH_CAT(A,B)
135 # define XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, XXH_versionNumber)
136 # define XXH32 XXH_NAME2(XXH_NAMESPACE, XXH32)
137 # define XXH32_createState XXH_NAME2(XXH_NAMESPACE, XXH32_createState)
138 # define XXH32_freeState XXH_NAME2(XXH_NAMESPACE, XXH32_freeState)
139 # define XXH32_reset XXH_NAME2(XXH_NAMESPACE, XXH32_reset)
140 # define XXH32_update XXH_NAME2(XXH_NAMESPACE, XXH32_update)
141 # define XXH32_digest XXH_NAME2(XXH_NAMESPACE, XXH32_digest)
142 # define XXH32_copyState XXH_NAME2(XXH_NAMESPACE, XXH32_copyState)
143 # define XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH32_canonicalFromHash)
144 # define XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH32_hashFromCanonical)
145 # define XXH64 XXH_NAME2(XXH_NAMESPACE, XXH64)
146 # define XXH64_createState XXH_NAME2(XXH_NAMESPACE, XXH64_createState)
147 # define XXH64_freeState XXH_NAME2(XXH_NAMESPACE, XXH64_freeState)
148 # define XXH64_reset XXH_NAME2(XXH_NAMESPACE, XXH64_reset)
149 # define XXH64_update XXH_NAME2(XXH_NAMESPACE, XXH64_update)
150 # define XXH64_digest XXH_NAME2(XXH_NAMESPACE, XXH64_digest)
151 # define XXH64_copyState XXH_NAME2(XXH_NAMESPACE, XXH64_copyState)
152 # define XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH64_canonicalFromHash)
153 # define XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH64_hashFromCanonical)
157 /* *************************************
159 ***************************************/
160 #define XXH_VERSION_MAJOR 0
161 #define XXH_VERSION_MINOR 7
162 #define XXH_VERSION_RELEASE 2
163 #define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE)
164 XXH_PUBLIC_API
unsigned XXH_versionNumber (void);
167 /* ****************************
169 ******************************/
170 #include <stddef.h> /* size_t */
171 typedef enum { XXH_OK
=0, XXH_ERROR
} XXH_errorcode
;
174 /*-**********************************************************************
176 ************************************************************************/
177 #if !defined (__VMS) \
178 && (defined (__cplusplus) \
179 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
181 typedef uint32_t XXH32_hash_t
;
184 # if UINT_MAX == 0xFFFFFFFFUL
185 typedef unsigned int XXH32_hash_t
;
187 # if ULONG_MAX == 0xFFFFFFFFUL
188 typedef unsigned long XXH32_hash_t
;
190 # error "unsupported platform : need a 32-bit type"
196 Calculate the 32-bit hash of sequence "length" bytes stored at memory address "input".
197 The memory between input & input+length must be valid (allocated and read-accessible).
198 "seed" can be used to alter the result predictably.
199 Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s */
200 XXH_PUBLIC_API XXH32_hash_t
XXH32 (const void* input
, size_t length
, XXH32_hash_t seed
);
202 /******* Streaming *******/
205 * Streaming functions generate the xxHash value from an incrememtal input.
206 * This method is slower than single-call functions, due to state management.
207 * For small inputs, prefer `XXH32()` and `XXH64()`, which are better optimized.
209 * XXH state must first be allocated, using XXH*_createState() .
211 * Start a new hash by initializing state with a seed, using XXH*_reset().
213 * Then, feed the hash state by calling XXH*_update() as many times as necessary.
214 * The function returns an error code, with 0 meaning OK, and any other value meaning there is an error.
216 * Finally, a hash value can be produced anytime, by using XXH*_digest().
217 * This function returns the nn-bits hash as an int or long long.
219 * It's still possible to continue inserting input into the hash state after a digest,
220 * and generate some new hash values later on, by invoking again XXH*_digest().
222 * When done, release the state, using XXH*_freeState().
225 typedef struct XXH32_state_s XXH32_state_t
; /* incomplete type */
226 XXH_PUBLIC_API XXH32_state_t
* XXH32_createState(void);
227 XXH_PUBLIC_API XXH_errorcode
XXH32_freeState(XXH32_state_t
* statePtr
);
228 XXH_PUBLIC_API
void XXH32_copyState(XXH32_state_t
* dst_state
, const XXH32_state_t
* src_state
);
230 XXH_PUBLIC_API XXH_errorcode
XXH32_reset (XXH32_state_t
* statePtr
, XXH32_hash_t seed
);
231 XXH_PUBLIC_API XXH_errorcode
XXH32_update (XXH32_state_t
* statePtr
, const void* input
, size_t length
);
232 XXH_PUBLIC_API XXH32_hash_t
XXH32_digest (const XXH32_state_t
* statePtr
);
234 /******* Canonical representation *******/
236 /* Default return values from XXH functions are basic unsigned 32 and 64 bits.
237 * This the simplest and fastest format for further post-processing.
238 * However, this leaves open the question of what is the order of bytes,
239 * since little and big endian conventions will write the same number differently.
241 * The canonical representation settles this issue,
242 * by mandating big-endian convention,
243 * aka, the same convention as human-readable numbers (large digits first).
244 * When writing hash values to storage, sending them over a network, or printing them,
245 * it's highly recommended to use the canonical representation,
246 * to ensure portability across a wider range of systems, present and future.
248 * The following functions allow transformation of hash values into and from canonical format.
251 typedef struct { unsigned char digest
[4]; } XXH32_canonical_t
;
252 XXH_PUBLIC_API
void XXH32_canonicalFromHash(XXH32_canonical_t
* dst
, XXH32_hash_t hash
);
253 XXH_PUBLIC_API XXH32_hash_t
XXH32_hashFromCanonical(const XXH32_canonical_t
* src
);
256 #ifndef XXH_NO_LONG_LONG
257 /*-**********************************************************************
259 ************************************************************************/
260 #if !defined (__VMS) \
261 && (defined (__cplusplus) \
262 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
264 typedef uint64_t XXH64_hash_t
;
266 /* the following type must have a width of 64-bit */
267 typedef unsigned long long XXH64_hash_t
;
271 * Returns the 64-bit hash of sequence of length @length stored at memory address @input.
272 * @seed can be used to alter the result predictably.
273 * This function runs faster on 64-bit systems, but slower on 32-bit systems (see benchmark).
275 XXH_PUBLIC_API XXH64_hash_t
XXH64 (const void* input
, size_t length
, XXH64_hash_t seed
);
277 /******* Streaming *******/
278 typedef struct XXH64_state_s XXH64_state_t
; /* incomplete type */
279 XXH_PUBLIC_API XXH64_state_t
* XXH64_createState(void);
280 XXH_PUBLIC_API XXH_errorcode
XXH64_freeState(XXH64_state_t
* statePtr
);
281 XXH_PUBLIC_API
void XXH64_copyState(XXH64_state_t
* dst_state
, const XXH64_state_t
* src_state
);
283 XXH_PUBLIC_API XXH_errorcode
XXH64_reset (XXH64_state_t
* statePtr
, XXH64_hash_t seed
);
284 XXH_PUBLIC_API XXH_errorcode
XXH64_update (XXH64_state_t
* statePtr
, const void* input
, size_t length
);
285 XXH_PUBLIC_API XXH64_hash_t
XXH64_digest (const XXH64_state_t
* statePtr
);
287 /******* Canonical representation *******/
288 typedef struct { unsigned char digest
[8]; } XXH64_canonical_t
;
289 XXH_PUBLIC_API
void XXH64_canonicalFromHash(XXH64_canonical_t
* dst
, XXH64_hash_t hash
);
290 XXH_PUBLIC_API XXH64_hash_t
XXH64_hashFromCanonical(const XXH64_canonical_t
* src
);
293 #endif /* XXH_NO_LONG_LONG */
295 #endif /* XXHASH_H_5627135585666179 */
299 #if defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742)
300 #define XXHASH_H_STATIC_13879238742
301 /* ************************************************************************************************
302 This section contains declarations which are not guaranteed to remain stable.
303 They may change in future versions, becoming incompatible with a different version of the library.
304 These declarations should only be used with static linking.
305 Never use them in association with dynamic linking !
306 *************************************************************************************************** */
308 /* These definitions are only present to allow
309 * static allocation of XXH state, on stack or in a struct for example.
310 * Never **ever** use members directly. */
312 struct XXH32_state_s
{
313 XXH32_hash_t total_len_32
;
314 XXH32_hash_t large_len
;
319 XXH32_hash_t mem32
[4];
320 XXH32_hash_t memsize
;
321 XXH32_hash_t reserved
; /* never read nor write, might be removed in a future version */
322 }; /* typedef'd to XXH32_state_t */
325 #ifndef XXH_NO_LONG_LONG /* defined when there is no 64-bit support */
327 struct XXH64_state_s
{
328 XXH64_hash_t total_len
;
333 XXH64_hash_t mem64
[4];
334 XXH32_hash_t memsize
;
335 XXH32_hash_t reserved32
; /* required for padding anyway */
336 XXH64_hash_t reserved64
; /* never read nor write, might be removed in a future version */
337 }; /* typedef'd to XXH64_state_t */
339 #endif /* XXH_NO_LONG_LONG */
341 #if defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)
342 # define XXH_IMPLEMENTATION
345 #endif /* defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742) */
349 /*-**********************************************************************
350 * xxHash implementation
351 * Functions implementation used to be hosted within xxhash.c .
352 * However, code inlining requires to place implementation in the header file.
353 * As a consequence, xxhash.c used to be included within xxhash.h .
354 * But some build systems don't like *.c inclusions.
355 * So the implementation is now directly integrated within xxhash.h .
356 * Another small advantage is that xxhash.c is no longer required in /includes .
357 ************************************************************************/
359 #if ( defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API) \
360 || defined(XXH_IMPLEMENTATION) ) && !defined(XXH_IMPLEM_13a8737387)
361 # define XXH_IMPLEM_13a8737387
363 /* *************************************
365 ***************************************/
366 /*!XXH_FORCE_MEMORY_ACCESS :
367 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
368 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
369 * The below switch allow to select different access method for improved performance.
370 * Method 0 (default) : use `memcpy()`. Safe and portable.
371 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
372 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
373 * Method 2 : direct access. This method doesn't depend on compiler but violate C standard.
374 * It can generate buggy code on targets which do not support unaligned memory accesses.
375 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
376 * See http://stackoverflow.com/a/32095106/646947 for details.
377 * Prefer these methods in priority order (0 > 1 > 2)
379 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
380 # if !defined(__clang__) && defined(__GNUC__) && defined(__ARM_FEATURE_UNALIGNED) && defined(__ARM_ARCH) && (__ARM_ARCH == 6)
381 # define XXH_FORCE_MEMORY_ACCESS 2
382 # elif !defined(__clang__) && ((defined(__INTEL_COMPILER) && !defined(_WIN32)) || \
383 (defined(__GNUC__) && (defined(__ARM_ARCH) && __ARM_ARCH >= 7)))
384 # define XXH_FORCE_MEMORY_ACCESS 1
388 /*!XXH_ACCEPT_NULL_INPUT_POINTER :
389 * If input pointer is NULL, xxHash default behavior is to dereference it, triggering a segfault.
390 * When this macro is enabled, xxHash actively checks input for null pointer.
391 * It it is, result for null input pointers is the same as a null-length input.
393 #ifndef XXH_ACCEPT_NULL_INPUT_POINTER /* can be defined externally */
394 # define XXH_ACCEPT_NULL_INPUT_POINTER 0
397 /*!XXH_FORCE_ALIGN_CHECK :
398 * This is a minor performance trick, only useful with lots of very small keys.
399 * It means : check for aligned/unaligned input.
400 * The check costs one initial branch per hash;
401 * set it to 0 when the input is guaranteed to be aligned,
402 * or when alignment doesn't matter for performance.
404 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
405 # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
406 # define XXH_FORCE_ALIGN_CHECK 0
408 # define XXH_FORCE_ALIGN_CHECK 1
413 * Whether to reroll XXH32_finalize, and XXH64_finalize,
414 * instead of using an unrolled jump table/if statement loop.
416 * This is automatically defined on -Os/-Oz on GCC and Clang. */
418 # if defined(__OPTIMIZE_SIZE__)
419 # define XXH_REROLL 1
421 # define XXH_REROLL 0
426 /* *************************************
427 * Includes & Memory related functions
428 ***************************************/
429 /*! Modify the local functions below should you wish to use some other memory routines
430 * for malloc(), free() */
432 static void* XXH_malloc(size_t s
) { return malloc(s
); }
433 static void XXH_free (void* p
) { free(p
); }
434 /*! and for memcpy() */
436 static void* XXH_memcpy(void* dest
, const void* src
, size_t size
) { return memcpy(dest
,src
,size
); }
438 #include <limits.h> /* ULLONG_MAX */
441 /* *************************************
442 * Compiler Specific Options
443 ***************************************/
444 #ifdef _MSC_VER /* Visual Studio */
445 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
446 # define XXH_FORCE_INLINE static __forceinline
447 # define XXH_NO_INLINE static __declspec(noinline)
449 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
451 # define XXH_FORCE_INLINE static inline __attribute__((always_inline))
452 # define XXH_NO_INLINE static __attribute__((noinline))
454 # define XXH_FORCE_INLINE static inline
455 # define XXH_NO_INLINE static
458 # define XXH_FORCE_INLINE static
459 # define XXH_NO_INLINE static
460 # endif /* __STDC_VERSION__ */
465 /* *************************************
467 ***************************************/
468 /* DEBUGLEVEL is expected to be defined externally,
469 * typically through compiler command line.
470 * Value must be a number. */
472 # define DEBUGLEVEL 0
476 # include <assert.h> /* note : can still be disabled with NDEBUG */
477 # define XXH_ASSERT(c) assert(c)
479 # define XXH_ASSERT(c) ((void)0)
482 /* note : use after variable declarations */
483 #define XXH_STATIC_ASSERT(c) { enum { XXH_sa = 1/(int)(!!(c)) }; }
486 /* *************************************
488 ***************************************/
489 #if !defined (__VMS) \
490 && (defined (__cplusplus) \
491 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
493 typedef uint8_t xxh_u8
;
495 typedef unsigned char xxh_u8
;
497 typedef XXH32_hash_t xxh_u32
;
500 /* *** Memory access *** */
502 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
504 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
505 static xxh_u32
XXH_read32(const void* memPtr
) { return *(const xxh_u32
*) memPtr
; }
507 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
509 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
510 /* currently only defined for gcc and icc */
511 typedef union { xxh_u32 u32
; } __attribute__((packed
)) unalign
;
512 static xxh_u32
XXH_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
516 /* portable and safe solution. Generally efficient.
517 * see : http://stackoverflow.com/a/32095106/646947
519 static xxh_u32
XXH_read32(const void* memPtr
)
522 memcpy(&val
, memPtr
, sizeof(val
));
526 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
529 /* *** Endianess *** */
530 typedef enum { XXH_bigEndian
=0, XXH_littleEndian
=1 } XXH_endianess
;
532 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
533 #ifndef XXH_CPU_LITTLE_ENDIAN
534 # if defined(_WIN32) /* Windows is always little endian */ \
535 || defined(__LITTLE_ENDIAN__) \
536 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
537 # define XXH_CPU_LITTLE_ENDIAN 1
538 # elif defined(__BIG_ENDIAN__) \
539 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
540 # define XXH_CPU_LITTLE_ENDIAN 0
542 static int XXH_isLittleEndian(void)
544 const union { xxh_u32 u
; xxh_u8 c
[4]; } one
= { 1 }; /* don't use static : performance detrimental */
547 # define XXH_CPU_LITTLE_ENDIAN XXH_isLittleEndian()
554 /* ****************************************
555 * Compiler-specific Functions and Macros
556 ******************************************/
557 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
559 #ifndef __has_builtin
560 # define __has_builtin(x) 0
563 #if !defined(NO_CLANG_BUILTIN) && __has_builtin(__builtin_rotateleft32) && __has_builtin(__builtin_rotateleft64)
564 # define XXH_rotl32 __builtin_rotateleft32
565 # define XXH_rotl64 __builtin_rotateleft64
566 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
567 #elif defined(_MSC_VER)
568 # define XXH_rotl32(x,r) _rotl(x,r)
569 # define XXH_rotl64(x,r) _rotl64(x,r)
571 # define XXH_rotl32(x,r) (((x) << (r)) | ((x) >> (32 - (r))))
572 # define XXH_rotl64(x,r) (((x) << (r)) | ((x) >> (64 - (r))))
575 #if defined(_MSC_VER) /* Visual Studio */
576 # define XXH_swap32 _byteswap_ulong
577 #elif XXH_GCC_VERSION >= 403
578 # define XXH_swap32 __builtin_bswap32
580 static xxh_u32
XXH_swap32 (xxh_u32 x
)
582 return ((x
<< 24) & 0xff000000 ) |
583 ((x
<< 8) & 0x00ff0000 ) |
584 ((x
>> 8) & 0x0000ff00 ) |
585 ((x
>> 24) & 0x000000ff );
590 /* ***************************
592 *****************************/
593 typedef enum { XXH_aligned
, XXH_unaligned
} XXH_alignment
;
595 XXH_FORCE_INLINE xxh_u32
XXH_readLE32(const void* ptr
)
597 return XXH_CPU_LITTLE_ENDIAN
? XXH_read32(ptr
) : XXH_swap32(XXH_read32(ptr
));
600 static xxh_u32
XXH_readBE32(const void* ptr
)
602 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap32(XXH_read32(ptr
)) : XXH_read32(ptr
);
605 XXH_FORCE_INLINE xxh_u32
606 XXH_readLE32_align(const void* ptr
, XXH_alignment align
)
608 if (align
==XXH_unaligned
) {
609 return XXH_readLE32(ptr
);
611 return XXH_CPU_LITTLE_ENDIAN
? *(const xxh_u32
*)ptr
: XXH_swap32(*(const xxh_u32
*)ptr
);
616 /* *************************************
618 ***************************************/
619 XXH_PUBLIC_API
unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER
; }
622 /* *******************************************************************
623 * 32-bit hash functions
624 *********************************************************************/
625 static const xxh_u32 PRIME32_1
= 0x9E3779B1U
; /* 0b10011110001101110111100110110001 */
626 static const xxh_u32 PRIME32_2
= 0x85EBCA77U
; /* 0b10000101111010111100101001110111 */
627 static const xxh_u32 PRIME32_3
= 0xC2B2AE3DU
; /* 0b11000010101100101010111000111101 */
628 static const xxh_u32 PRIME32_4
= 0x27D4EB2FU
; /* 0b00100111110101001110101100101111 */
629 static const xxh_u32 PRIME32_5
= 0x165667B1U
; /* 0b00010110010101100110011110110001 */
631 static xxh_u32
XXH32_round(xxh_u32 acc
, xxh_u32 input
)
633 acc
+= input
* PRIME32_2
;
634 acc
= XXH_rotl32(acc
, 13);
636 #if defined(__GNUC__) && defined(__SSE4_1__) && !defined(XXH_ENABLE_AUTOVECTORIZE)
638 * This inline assembly hack forces acc into a normal register. This is the
639 * only thing that prevents GCC and Clang from autovectorizing the XXH32 loop
640 * (pragmas and attributes don't work for some resason) without globally
643 * The reason we want to avoid vectorization is because despite working on
644 * 4 integers at a time, there are multiple factors slowing XXH32 down on
646 * - There's a ridiculous amount of lag from pmulld (10 cycles of latency on newer chips!)
647 * making it slightly slower to multiply four integers at once compared to four
648 * integers independently. Even when pmulld was fastest, Sandy/Ivy Bridge, it is
649 * still not worth it to go into SSE just to multiply unless doing a long operation.
651 * - Four instructions are required to rotate,
652 * movqda tmp, v // not required with VEX encoding
653 * pslld tmp, 13 // tmp <<= 13
654 * psrld v, 19 // x >>= 19
655 * por v, tmp // x |= tmp
656 * compared to one for scalar:
657 * roll v, 13 // reliably fast across the board
658 * shldl v, v, 13 // Sandy Bridge and later prefer this for some reason
660 * - Instruction level parallelism is actually more beneficial here because the
661 * SIMD actually serializes this operation: While v1 is rotating, v2 can load data,
662 * while v3 can multiply. SSE forces them to operate together.
664 * How this hack works:
665 * __asm__("" // Declare an assembly block but don't declare any instructions
666 * : // However, as an Input/Output Operand,
667 * "+r" // constrain a read/write operand (+) as a general purpose register (r).
668 * (acc) // and set acc as the operand
671 * Because of the 'r', the compiler has promised that seed will be in a
672 * general purpose register and the '+' says that it will be 'read/write',
673 * so it has to assume it has changed. It is like volatile without all the
676 * Since the argument has to be in a normal register (not an SSE register),
677 * each time XXH32_round is called, it is impossible to vectorize. */
678 __asm__("" : "+r" (acc
));
684 static xxh_u32
XXH32_avalanche(xxh_u32 h32
)
694 #define XXH_get32bits(p) XXH_readLE32_align(p, align)
697 XXH32_finalize(xxh_u32 h32
, const xxh_u8
* ptr
, size_t len
, XXH_alignment align
)
700 h32 += (*ptr++) * PRIME32_5; \
701 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
704 h32 += XXH_get32bits(ptr) * PRIME32_3; \
706 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
708 /* Compact rerolled version */
719 return XXH32_avalanche(h32
);
721 switch(len
&15) /* or switch(bEnd - p) */ {
727 return XXH32_avalanche(h32
);
735 return XXH32_avalanche(h32
);
744 return XXH32_avalanche(h32
);
758 case 0: return XXH32_avalanche(h32
);
761 return h32
; /* reaching this point is deemed impossible */
765 XXH_FORCE_INLINE xxh_u32
766 XXH32_endian_align(const xxh_u8
* input
, size_t len
, xxh_u32 seed
, XXH_alignment align
)
768 const xxh_u8
* bEnd
= input
+ len
;
771 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
774 bEnd
=input
=(const xxh_u8
*)(size_t)16;
779 const xxh_u8
* const limit
= bEnd
- 15;
780 xxh_u32 v1
= seed
+ PRIME32_1
+ PRIME32_2
;
781 xxh_u32 v2
= seed
+ PRIME32_2
;
782 xxh_u32 v3
= seed
+ 0;
783 xxh_u32 v4
= seed
- PRIME32_1
;
786 v1
= XXH32_round(v1
, XXH_get32bits(input
)); input
+= 4;
787 v2
= XXH32_round(v2
, XXH_get32bits(input
)); input
+= 4;
788 v3
= XXH32_round(v3
, XXH_get32bits(input
)); input
+= 4;
789 v4
= XXH32_round(v4
, XXH_get32bits(input
)); input
+= 4;
790 } while (input
< limit
);
792 h32
= XXH_rotl32(v1
, 1) + XXH_rotl32(v2
, 7)
793 + XXH_rotl32(v3
, 12) + XXH_rotl32(v4
, 18);
795 h32
= seed
+ PRIME32_5
;
800 return XXH32_finalize(h32
, input
, len
&15, align
);
804 XXH_PUBLIC_API XXH32_hash_t
XXH32 (const void* input
, size_t len
, XXH32_hash_t seed
)
807 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
809 XXH32_reset(&state
, seed
);
810 XXH32_update(&state
, (const xxh_u8
*)input
, len
);
811 return XXH32_digest(&state
);
815 if (XXH_FORCE_ALIGN_CHECK
) {
816 if ((((size_t)input
) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
817 return XXH32_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_aligned
);
820 return XXH32_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_unaligned
);
826 /******* Hash streaming *******/
828 XXH_PUBLIC_API XXH32_state_t
* XXH32_createState(void)
830 return (XXH32_state_t
*)XXH_malloc(sizeof(XXH32_state_t
));
832 XXH_PUBLIC_API XXH_errorcode
XXH32_freeState(XXH32_state_t
* statePtr
)
838 XXH_PUBLIC_API
void XXH32_copyState(XXH32_state_t
* dstState
, const XXH32_state_t
* srcState
)
840 memcpy(dstState
, srcState
, sizeof(*dstState
));
843 XXH_PUBLIC_API XXH_errorcode
XXH32_reset(XXH32_state_t
* statePtr
, XXH32_hash_t seed
)
845 XXH32_state_t state
; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
846 memset(&state
, 0, sizeof(state
));
847 state
.v1
= seed
+ PRIME32_1
+ PRIME32_2
;
848 state
.v2
= seed
+ PRIME32_2
;
850 state
.v4
= seed
- PRIME32_1
;
851 /* do not write into reserved, planned to be removed in a future version */
852 memcpy(statePtr
, &state
, sizeof(state
) - sizeof(state
.reserved
));
857 XXH_PUBLIC_API XXH_errorcode
858 XXH32_update(XXH32_state_t
* state
, const void* input
, size_t len
)
861 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
867 { const xxh_u8
* p
= (const xxh_u8
*)input
;
868 const xxh_u8
* const bEnd
= p
+ len
;
870 state
->total_len_32
+= (XXH32_hash_t
)len
;
871 state
->large_len
|= (XXH32_hash_t
)((len
>=16) | (state
->total_len_32
>=16));
873 if (state
->memsize
+ len
< 16) { /* fill in tmp buffer */
874 XXH_memcpy((xxh_u8
*)(state
->mem32
) + state
->memsize
, input
, len
);
875 state
->memsize
+= (XXH32_hash_t
)len
;
879 if (state
->memsize
) { /* some data left from previous update */
880 XXH_memcpy((xxh_u8
*)(state
->mem32
) + state
->memsize
, input
, 16-state
->memsize
);
881 { const xxh_u32
* p32
= state
->mem32
;
882 state
->v1
= XXH32_round(state
->v1
, XXH_readLE32(p32
)); p32
++;
883 state
->v2
= XXH32_round(state
->v2
, XXH_readLE32(p32
)); p32
++;
884 state
->v3
= XXH32_round(state
->v3
, XXH_readLE32(p32
)); p32
++;
885 state
->v4
= XXH32_round(state
->v4
, XXH_readLE32(p32
));
887 p
+= 16-state
->memsize
;
892 const xxh_u8
* const limit
= bEnd
- 16;
893 xxh_u32 v1
= state
->v1
;
894 xxh_u32 v2
= state
->v2
;
895 xxh_u32 v3
= state
->v3
;
896 xxh_u32 v4
= state
->v4
;
899 v1
= XXH32_round(v1
, XXH_readLE32(p
)); p
+=4;
900 v2
= XXH32_round(v2
, XXH_readLE32(p
)); p
+=4;
901 v3
= XXH32_round(v3
, XXH_readLE32(p
)); p
+=4;
902 v4
= XXH32_round(v4
, XXH_readLE32(p
)); p
+=4;
912 XXH_memcpy(state
->mem32
, p
, (size_t)(bEnd
-p
));
913 state
->memsize
= (unsigned)(bEnd
-p
);
921 XXH_PUBLIC_API XXH32_hash_t
XXH32_digest (const XXH32_state_t
* state
)
925 if (state
->large_len
) {
926 h32
= XXH_rotl32(state
->v1
, 1)
927 + XXH_rotl32(state
->v2
, 7)
928 + XXH_rotl32(state
->v3
, 12)
929 + XXH_rotl32(state
->v4
, 18);
931 h32
= state
->v3
/* == seed */ + PRIME32_5
;
934 h32
+= state
->total_len_32
;
936 return XXH32_finalize(h32
, (const xxh_u8
*)state
->mem32
, state
->memsize
, XXH_aligned
);
940 /******* Canonical representation *******/
942 /*! Default XXH result types are basic unsigned 32 and 64 bits.
943 * The canonical representation follows human-readable write convention, aka big-endian (large digits first).
944 * These functions allow transformation of hash result into and from its canonical format.
945 * This way, hash values can be written into a file or buffer, remaining comparable across different systems.
948 XXH_PUBLIC_API
void XXH32_canonicalFromHash(XXH32_canonical_t
* dst
, XXH32_hash_t hash
)
950 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t
) == sizeof(XXH32_hash_t
));
951 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap32(hash
);
952 memcpy(dst
, &hash
, sizeof(*dst
));
955 XXH_PUBLIC_API XXH32_hash_t
XXH32_hashFromCanonical(const XXH32_canonical_t
* src
)
957 return XXH_readBE32(src
);
961 #ifndef XXH_NO_LONG_LONG
963 /* *******************************************************************
964 * 64-bit hash functions
965 *********************************************************************/
967 /******* Memory access *******/
969 typedef XXH64_hash_t xxh_u64
;
972 /*! XXH_REROLL_XXH64:
973 * Whether to reroll the XXH64_finalize() loop.
975 * Just like XXH32, we can unroll the XXH64_finalize() loop. This can be a performance gain
976 * on 64-bit hosts, as only one jump is required.
978 * However, on 32-bit hosts, because arithmetic needs to be done with two 32-bit registers,
979 * and 64-bit arithmetic needs to be simulated, it isn't beneficial to unroll. The code becomes
980 * ridiculously large (the largest function in the binary on i386!), and rerolling it saves
981 * anywhere from 3kB to 20kB. It is also slightly faster because it fits into cache better
982 * and is more likely to be inlined by the compiler.
984 * If XXH_REROLL is defined, this is ignored and the loop is always rerolled. */
985 #ifndef XXH_REROLL_XXH64
986 # if (defined(__ILP32__) || defined(_ILP32)) /* ILP32 is often defined on 32-bit GCC family */ \
987 || !(defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) /* x86-64 */ \
988 || defined(_M_ARM64) || defined(__aarch64__) || defined(__arm64__) /* aarch64 */ \
989 || defined(__PPC64__) || defined(__PPC64LE__) || defined(__ppc64__) || defined(__powerpc64__) /* ppc64 */ \
990 || defined(__mips64__) || defined(__mips64)) /* mips64 */ \
991 || (!defined(SIZE_MAX) || SIZE_MAX < ULLONG_MAX) /* check limits */
992 # define XXH_REROLL_XXH64 1
994 # define XXH_REROLL_XXH64 0
996 #endif /* !defined(XXH_REROLL_XXH64) */
998 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
1000 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
1001 static xxh_u64
XXH_read64(const void* memPtr
) { return *(const xxh_u64
*) memPtr
; }
1003 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
1005 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
1006 /* currently only defined for gcc and icc */
1007 typedef union { xxh_u32 u32
; xxh_u64 u64
; } __attribute__((packed
)) unalign64
;
1008 static xxh_u64
XXH_read64(const void* ptr
) { return ((const unalign64
*)ptr
)->u64
; }
1012 /* portable and safe solution. Generally efficient.
1013 * see : http://stackoverflow.com/a/32095106/646947
1016 static xxh_u64
XXH_read64(const void* memPtr
)
1019 memcpy(&val
, memPtr
, sizeof(val
));
1023 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
1025 #if defined(_MSC_VER) /* Visual Studio */
1026 # define XXH_swap64 _byteswap_uint64
1027 #elif XXH_GCC_VERSION >= 403
1028 # define XXH_swap64 __builtin_bswap64
1030 static xxh_u64
XXH_swap64 (xxh_u64 x
)
1032 return ((x
<< 56) & 0xff00000000000000ULL
) |
1033 ((x
<< 40) & 0x00ff000000000000ULL
) |
1034 ((x
<< 24) & 0x0000ff0000000000ULL
) |
1035 ((x
<< 8) & 0x000000ff00000000ULL
) |
1036 ((x
>> 8) & 0x00000000ff000000ULL
) |
1037 ((x
>> 24) & 0x0000000000ff0000ULL
) |
1038 ((x
>> 40) & 0x000000000000ff00ULL
) |
1039 ((x
>> 56) & 0x00000000000000ffULL
);
1043 XXH_FORCE_INLINE xxh_u64
XXH_readLE64(const void* ptr
)
1045 return XXH_CPU_LITTLE_ENDIAN
? XXH_read64(ptr
) : XXH_swap64(XXH_read64(ptr
));
1048 static xxh_u64
XXH_readBE64(const void* ptr
)
1050 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap64(XXH_read64(ptr
)) : XXH_read64(ptr
);
1053 XXH_FORCE_INLINE xxh_u64
1054 XXH_readLE64_align(const void* ptr
, XXH_alignment align
)
1056 if (align
==XXH_unaligned
)
1057 return XXH_readLE64(ptr
);
1059 return XXH_CPU_LITTLE_ENDIAN
? *(const xxh_u64
*)ptr
: XXH_swap64(*(const xxh_u64
*)ptr
);
1063 /******* xxh64 *******/
1065 static const xxh_u64 PRIME64_1
= 0x9E3779B185EBCA87ULL
; /* 0b1001111000110111011110011011000110000101111010111100101010000111 */
1066 static const xxh_u64 PRIME64_2
= 0xC2B2AE3D27D4EB4FULL
; /* 0b1100001010110010101011100011110100100111110101001110101101001111 */
1067 static const xxh_u64 PRIME64_3
= 0x165667B19E3779F9ULL
; /* 0b0001011001010110011001111011000110011110001101110111100111111001 */
1068 static const xxh_u64 PRIME64_4
= 0x85EBCA77C2B2AE63ULL
; /* 0b1000010111101011110010100111011111000010101100101010111001100011 */
1069 static const xxh_u64 PRIME64_5
= 0x27D4EB2F165667C5ULL
; /* 0b0010011111010100111010110010111100010110010101100110011111000101 */
1071 static xxh_u64
XXH64_round(xxh_u64 acc
, xxh_u64 input
)
1073 acc
+= input
* PRIME64_2
;
1074 acc
= XXH_rotl64(acc
, 31);
1079 static xxh_u64
XXH64_mergeRound(xxh_u64 acc
, xxh_u64 val
)
1081 val
= XXH64_round(0, val
);
1083 acc
= acc
* PRIME64_1
+ PRIME64_4
;
1087 static xxh_u64
XXH64_avalanche(xxh_u64 h64
)
1098 #define XXH_get64bits(p) XXH_readLE64_align(p, align)
1101 XXH64_finalize(xxh_u64 h64
, const xxh_u8
* ptr
, size_t len
, XXH_alignment align
)
1103 #define PROCESS1_64 \
1104 h64 ^= (*ptr++) * PRIME64_5; \
1105 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
1107 #define PROCESS4_64 \
1108 h64 ^= (xxh_u64)(XXH_get32bits(ptr)) * PRIME64_1; \
1110 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
1112 #define PROCESS8_64 { \
1113 xxh_u64 const k1 = XXH64_round(0, XXH_get64bits(ptr)); \
1116 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; \
1119 /* Rerolled version for 32-bit targets is faster and much smaller. */
1120 if (XXH_REROLL
|| XXH_REROLL_XXH64
) {
1134 return XXH64_avalanche(h64
);
1137 case 24: PROCESS8_64
;
1139 case 16: PROCESS8_64
;
1141 case 8: PROCESS8_64
;
1142 return XXH64_avalanche(h64
);
1144 case 28: PROCESS8_64
;
1146 case 20: PROCESS8_64
;
1148 case 12: PROCESS8_64
;
1150 case 4: PROCESS4_64
;
1151 return XXH64_avalanche(h64
);
1153 case 25: PROCESS8_64
;
1155 case 17: PROCESS8_64
;
1157 case 9: PROCESS8_64
;
1159 return XXH64_avalanche(h64
);
1161 case 29: PROCESS8_64
;
1163 case 21: PROCESS8_64
;
1165 case 13: PROCESS8_64
;
1167 case 5: PROCESS4_64
;
1169 return XXH64_avalanche(h64
);
1171 case 26: PROCESS8_64
;
1173 case 18: PROCESS8_64
;
1175 case 10: PROCESS8_64
;
1178 return XXH64_avalanche(h64
);
1180 case 30: PROCESS8_64
;
1182 case 22: PROCESS8_64
;
1184 case 14: PROCESS8_64
;
1186 case 6: PROCESS4_64
;
1189 return XXH64_avalanche(h64
);
1191 case 27: PROCESS8_64
;
1193 case 19: PROCESS8_64
;
1195 case 11: PROCESS8_64
;
1199 return XXH64_avalanche(h64
);
1201 case 31: PROCESS8_64
;
1203 case 23: PROCESS8_64
;
1205 case 15: PROCESS8_64
;
1207 case 7: PROCESS4_64
;
1209 case 3: PROCESS1_64
;
1211 case 2: PROCESS1_64
;
1213 case 1: PROCESS1_64
;
1215 case 0: return XXH64_avalanche(h64
);
1218 /* impossible to reach */
1220 return 0; /* unreachable, but some compilers complain without it */
1223 XXH_FORCE_INLINE xxh_u64
1224 XXH64_endian_align(const xxh_u8
* input
, size_t len
, xxh_u64 seed
, XXH_alignment align
)
1226 const xxh_u8
* bEnd
= input
+ len
;
1229 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
1232 bEnd
=input
=(const xxh_u8
*)(size_t)32;
1237 const xxh_u8
* const limit
= bEnd
- 32;
1238 xxh_u64 v1
= seed
+ PRIME64_1
+ PRIME64_2
;
1239 xxh_u64 v2
= seed
+ PRIME64_2
;
1240 xxh_u64 v3
= seed
+ 0;
1241 xxh_u64 v4
= seed
- PRIME64_1
;
1244 v1
= XXH64_round(v1
, XXH_get64bits(input
)); input
+=8;
1245 v2
= XXH64_round(v2
, XXH_get64bits(input
)); input
+=8;
1246 v3
= XXH64_round(v3
, XXH_get64bits(input
)); input
+=8;
1247 v4
= XXH64_round(v4
, XXH_get64bits(input
)); input
+=8;
1248 } while (input
<=limit
);
1250 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
1251 h64
= XXH64_mergeRound(h64
, v1
);
1252 h64
= XXH64_mergeRound(h64
, v2
);
1253 h64
= XXH64_mergeRound(h64
, v3
);
1254 h64
= XXH64_mergeRound(h64
, v4
);
1257 h64
= seed
+ PRIME64_5
;
1260 h64
+= (xxh_u64
) len
;
1262 return XXH64_finalize(h64
, input
, len
, align
);
1266 XXH_PUBLIC_API XXH64_hash_t
XXH64 (const void* input
, size_t len
, XXH64_hash_t seed
)
1269 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
1270 XXH64_state_t state
;
1271 XXH64_reset(&state
, seed
);
1272 XXH64_update(&state
, (const xxh_u8
*)input
, len
);
1273 return XXH64_digest(&state
);
1277 if (XXH_FORCE_ALIGN_CHECK
) {
1278 if ((((size_t)input
) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
1279 return XXH64_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_aligned
);
1282 return XXH64_endian_align((const xxh_u8
*)input
, len
, seed
, XXH_unaligned
);
1287 /******* Hash Streaming *******/
1289 XXH_PUBLIC_API XXH64_state_t
* XXH64_createState(void)
1291 return (XXH64_state_t
*)XXH_malloc(sizeof(XXH64_state_t
));
1293 XXH_PUBLIC_API XXH_errorcode
XXH64_freeState(XXH64_state_t
* statePtr
)
1299 XXH_PUBLIC_API
void XXH64_copyState(XXH64_state_t
* dstState
, const XXH64_state_t
* srcState
)
1301 memcpy(dstState
, srcState
, sizeof(*dstState
));
1304 XXH_PUBLIC_API XXH_errorcode
XXH64_reset(XXH64_state_t
* statePtr
, XXH64_hash_t seed
)
1306 XXH64_state_t state
; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
1307 memset(&state
, 0, sizeof(state
));
1308 state
.v1
= seed
+ PRIME64_1
+ PRIME64_2
;
1309 state
.v2
= seed
+ PRIME64_2
;
1310 state
.v3
= seed
+ 0;
1311 state
.v4
= seed
- PRIME64_1
;
1312 /* do not write into reserved64, might be removed in a future version */
1313 memcpy(statePtr
, &state
, sizeof(state
) - sizeof(state
.reserved64
));
1317 XXH_PUBLIC_API XXH_errorcode
1318 XXH64_update (XXH64_state_t
* state
, const void* input
, size_t len
)
1321 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1)
1327 { const xxh_u8
* p
= (const xxh_u8
*)input
;
1328 const xxh_u8
* const bEnd
= p
+ len
;
1330 state
->total_len
+= len
;
1332 if (state
->memsize
+ len
< 32) { /* fill in tmp buffer */
1333 XXH_memcpy(((xxh_u8
*)state
->mem64
) + state
->memsize
, input
, len
);
1334 state
->memsize
+= (xxh_u32
)len
;
1338 if (state
->memsize
) { /* tmp buffer is full */
1339 XXH_memcpy(((xxh_u8
*)state
->mem64
) + state
->memsize
, input
, 32-state
->memsize
);
1340 state
->v1
= XXH64_round(state
->v1
, XXH_readLE64(state
->mem64
+0));
1341 state
->v2
= XXH64_round(state
->v2
, XXH_readLE64(state
->mem64
+1));
1342 state
->v3
= XXH64_round(state
->v3
, XXH_readLE64(state
->mem64
+2));
1343 state
->v4
= XXH64_round(state
->v4
, XXH_readLE64(state
->mem64
+3));
1344 p
+= 32-state
->memsize
;
1349 const xxh_u8
* const limit
= bEnd
- 32;
1350 xxh_u64 v1
= state
->v1
;
1351 xxh_u64 v2
= state
->v2
;
1352 xxh_u64 v3
= state
->v3
;
1353 xxh_u64 v4
= state
->v4
;
1356 v1
= XXH64_round(v1
, XXH_readLE64(p
)); p
+=8;
1357 v2
= XXH64_round(v2
, XXH_readLE64(p
)); p
+=8;
1358 v3
= XXH64_round(v3
, XXH_readLE64(p
)); p
+=8;
1359 v4
= XXH64_round(v4
, XXH_readLE64(p
)); p
+=8;
1369 XXH_memcpy(state
->mem64
, p
, (size_t)(bEnd
-p
));
1370 state
->memsize
= (unsigned)(bEnd
-p
);
1378 XXH_PUBLIC_API XXH64_hash_t
XXH64_digest (const XXH64_state_t
* state
)
1382 if (state
->total_len
>= 32) {
1383 xxh_u64
const v1
= state
->v1
;
1384 xxh_u64
const v2
= state
->v2
;
1385 xxh_u64
const v3
= state
->v3
;
1386 xxh_u64
const v4
= state
->v4
;
1388 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
1389 h64
= XXH64_mergeRound(h64
, v1
);
1390 h64
= XXH64_mergeRound(h64
, v2
);
1391 h64
= XXH64_mergeRound(h64
, v3
);
1392 h64
= XXH64_mergeRound(h64
, v4
);
1394 h64
= state
->v3
/*seed*/ + PRIME64_5
;
1397 h64
+= (xxh_u64
) state
->total_len
;
1399 return XXH64_finalize(h64
, (const xxh_u8
*)state
->mem64
, (size_t)state
->total_len
, XXH_aligned
);
1403 /******* Canonical representation *******/
1405 XXH_PUBLIC_API
void XXH64_canonicalFromHash(XXH64_canonical_t
* dst
, XXH64_hash_t hash
)
1407 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t
) == sizeof(XXH64_hash_t
));
1408 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap64(hash
);
1409 memcpy(dst
, &hash
, sizeof(*dst
));
1412 XXH_PUBLIC_API XXH64_hash_t
XXH64_hashFromCanonical(const XXH64_canonical_t
* src
)
1414 return XXH_readBE64(src
);
1419 /* *********************************************************************
1421 * New generation hash designed for speed on small keys and vectorization
1422 ************************************************************************ */
1424 /* #include "xxh3.h" */
1427 #endif /* XXH_NO_LONG_LONG */
1430 #endif /* XXH_IMPLEMENTATION */
1433 #if defined (__cplusplus)