2 * xxHash - Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 * You can contact the author at :
31 * - xxHash homepage: http://www.xxhash.com
32 * - xxHash source repository : https://github.com/Cyan4973/xxHash
36 /* *************************************
38 ***************************************/
39 /*!XXH_FORCE_MEMORY_ACCESS :
40 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
41 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
42 * The below switch allow to select different access method for improved performance.
43 * Method 0 (default) : use `memcpy()`. Safe and portable.
44 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
45 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
46 * Method 2 : direct access. This method doesn't depend on compiler but violate C standard.
47 * It can generate buggy code on targets which do not support unaligned memory accesses.
48 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
49 * See http://stackoverflow.com/a/32095106/646947 for details.
50 * Prefer these methods in priority order (0 > 1 > 2)
52 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
53 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
54 # define XXH_FORCE_MEMORY_ACCESS 2
55 # elif defined(__INTEL_COMPILER) || \
56 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
57 # define XXH_FORCE_MEMORY_ACCESS 1
61 /*!XXH_ACCEPT_NULL_INPUT_POINTER :
62 * If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
63 * When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
64 * By default, this option is disabled. To enable it, uncomment below define :
66 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */
68 /*!XXH_FORCE_NATIVE_FORMAT :
69 * By default, xxHash library provides endian-independent Hash values, based on little-endian convention.
70 * Results are therefore identical for little-endian and big-endian CPU.
71 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
72 * Should endian-independence be of no importance for your application, you may set the #define below to 1,
73 * to improve speed for Big-endian CPU.
74 * This option has no impact on Little_Endian CPU.
76 #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */
77 # define XXH_FORCE_NATIVE_FORMAT 0
80 /*!XXH_FORCE_ALIGN_CHECK :
81 * This is a minor performance trick, only useful with lots of very small keys.
82 * It means : check for aligned/unaligned input.
83 * The check costs one initial branch per hash;
84 * set it to 0 when the input is guaranteed to be aligned,
85 * or when alignment doesn't matter for performance.
87 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
88 # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
89 # define XXH_FORCE_ALIGN_CHECK 0
91 # define XXH_FORCE_ALIGN_CHECK 1
96 /* *************************************
97 * Includes & Memory related functions
98 ***************************************/
99 /*! Modify the local functions below should you wish to use some other memory routines
100 * for malloc(), free() */
102 static void* XXH_malloc(size_t s
) { return malloc(s
); }
103 static void XXH_free (void* p
) { free(p
); }
104 /*! and for memcpy() */
106 static void* XXH_memcpy(void* dest
, const void* src
, size_t size
) { return memcpy(dest
,src
,size
); }
108 #define XXH_STATIC_LINKING_ONLY
112 /* *************************************
113 * Compiler Specific Options
114 ***************************************/
115 #ifdef _MSC_VER /* Visual Studio */
116 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
117 # define FORCE_INLINE static __forceinline
119 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
121 # define FORCE_INLINE static inline __attribute__((always_inline))
123 # define FORCE_INLINE static inline
126 # define FORCE_INLINE static
127 # endif /* __STDC_VERSION__ */
131 /* *************************************
133 ***************************************/
135 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
137 typedef uint8_t BYTE
;
138 typedef uint16_t U16
;
139 typedef uint32_t U32
;
141 typedef unsigned char BYTE
;
142 typedef unsigned short U16
;
143 typedef unsigned int U32
;
147 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
149 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
150 static U32
XXH_read32(const void* memPtr
) { return *(const U32
*) memPtr
; }
152 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
154 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
155 /* currently only defined for gcc and icc */
156 typedef union { U32 u32
; } __attribute__((packed
)) unalign
;
157 static U32
XXH_read32(const void* ptr
) { return ((const unalign
*)ptr
)->u32
; }
161 /* portable and safe solution. Generally efficient.
162 * see : http://stackoverflow.com/a/32095106/646947
164 static U32
XXH_read32(const void* memPtr
)
167 memcpy(&val
, memPtr
, sizeof(val
));
171 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
174 /* ****************************************
175 * Compiler-specific Functions and Macros
176 ******************************************/
177 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
179 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
180 #if defined(_MSC_VER)
181 # define XXH_rotl32(x,r) _rotl(x,r)
182 # define XXH_rotl64(x,r) _rotl64(x,r)
184 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
185 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
188 #if defined(_MSC_VER) /* Visual Studio */
189 # define XXH_swap32 _byteswap_ulong
190 #elif XXH_GCC_VERSION >= 403
191 # define XXH_swap32 __builtin_bswap32
193 static U32
XXH_swap32 (U32 x
)
195 return ((x
<< 24) & 0xff000000 ) |
196 ((x
<< 8) & 0x00ff0000 ) |
197 ((x
>> 8) & 0x0000ff00 ) |
198 ((x
>> 24) & 0x000000ff );
203 /* *************************************
204 * Architecture Macros
205 ***************************************/
206 typedef enum { XXH_bigEndian
=0, XXH_littleEndian
=1 } XXH_endianess
;
208 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
209 #ifndef XXH_CPU_LITTLE_ENDIAN
210 static const int g_one
= 1;
211 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one))
215 /* ***************************
217 *****************************/
218 typedef enum { XXH_aligned
, XXH_unaligned
} XXH_alignment
;
220 FORCE_INLINE U32
XXH_readLE32_align(const void* ptr
, XXH_endianess endian
, XXH_alignment align
)
222 if (align
==XXH_unaligned
)
223 return endian
==XXH_littleEndian
? XXH_read32(ptr
) : XXH_swap32(XXH_read32(ptr
));
225 return endian
==XXH_littleEndian
? *(const U32
*)ptr
: XXH_swap32(*(const U32
*)ptr
);
228 FORCE_INLINE U32
XXH_readLE32(const void* ptr
, XXH_endianess endian
)
230 return XXH_readLE32_align(ptr
, endian
, XXH_unaligned
);
233 static U32
XXH_readBE32(const void* ptr
)
235 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap32(XXH_read32(ptr
)) : XXH_read32(ptr
);
239 /* *************************************
241 ***************************************/
242 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
243 XXH_PUBLIC_API
unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER
; }
246 /* *******************************************************************
247 * 32-bits hash functions
248 *********************************************************************/
249 static const U32 PRIME32_1
= 2654435761U;
250 static const U32 PRIME32_2
= 2246822519U;
251 static const U32 PRIME32_3
= 3266489917U;
252 static const U32 PRIME32_4
= 668265263U;
253 static const U32 PRIME32_5
= 374761393U;
255 static U32
XXH32_round(U32 seed
, U32 input
)
257 seed
+= input
* PRIME32_2
;
258 seed
= XXH_rotl32(seed
, 13);
263 FORCE_INLINE U32
XXH32_endian_align(const void* input
, size_t len
, U32 seed
, XXH_endianess endian
, XXH_alignment align
)
265 const BYTE
* p
= (const BYTE
*)input
;
266 const BYTE
* bEnd
= p
+ len
;
268 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
270 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
273 bEnd
=p
=(const BYTE
*)(size_t)16;
278 const BYTE
* const limit
= bEnd
- 16;
279 U32 v1
= seed
+ PRIME32_1
+ PRIME32_2
;
280 U32 v2
= seed
+ PRIME32_2
;
282 U32 v4
= seed
- PRIME32_1
;
285 v1
= XXH32_round(v1
, XXH_get32bits(p
)); p
+=4;
286 v2
= XXH32_round(v2
, XXH_get32bits(p
)); p
+=4;
287 v3
= XXH32_round(v3
, XXH_get32bits(p
)); p
+=4;
288 v4
= XXH32_round(v4
, XXH_get32bits(p
)); p
+=4;
291 h32
= XXH_rotl32(v1
, 1) + XXH_rotl32(v2
, 7) + XXH_rotl32(v3
, 12) + XXH_rotl32(v4
, 18);
293 h32
= seed
+ PRIME32_5
;
299 h32
+= XXH_get32bits(p
) * PRIME32_3
;
300 h32
= XXH_rotl32(h32
, 17) * PRIME32_4
;
305 h32
+= (*p
) * PRIME32_5
;
306 h32
= XXH_rotl32(h32
, 11) * PRIME32_1
;
320 XXH_PUBLIC_API
unsigned int XXH32 (const void* input
, size_t len
, unsigned int seed
)
323 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
325 XXH32_reset(&state
, seed
);
326 XXH32_update(&state
, input
, len
);
327 return XXH32_digest(&state
);
329 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
331 if (XXH_FORCE_ALIGN_CHECK
) {
332 if ((((size_t)input
) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
333 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
334 return XXH32_endian_align(input
, len
, seed
, XXH_littleEndian
, XXH_aligned
);
336 return XXH32_endian_align(input
, len
, seed
, XXH_bigEndian
, XXH_aligned
);
339 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
340 return XXH32_endian_align(input
, len
, seed
, XXH_littleEndian
, XXH_unaligned
);
342 return XXH32_endian_align(input
, len
, seed
, XXH_bigEndian
, XXH_unaligned
);
348 /*====== Hash streaming ======*/
350 XXH_PUBLIC_API XXH32_state_t
* XXH32_createState(void)
352 return (XXH32_state_t
*)XXH_malloc(sizeof(XXH32_state_t
));
354 XXH_PUBLIC_API XXH_errorcode
XXH32_freeState(XXH32_state_t
* statePtr
)
360 XXH_PUBLIC_API
void XXH32_copyState(XXH32_state_t
* dstState
, const XXH32_state_t
* srcState
)
362 memcpy(dstState
, srcState
, sizeof(*dstState
));
365 XXH_PUBLIC_API XXH_errorcode
XXH32_reset(XXH32_state_t
* statePtr
, unsigned int seed
)
367 XXH32_state_t state
; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
368 memset(&state
, 0, sizeof(state
)-4); /* do not write into reserved, for future removal */
369 state
.v1
= seed
+ PRIME32_1
+ PRIME32_2
;
370 state
.v2
= seed
+ PRIME32_2
;
372 state
.v4
= seed
- PRIME32_1
;
373 memcpy(statePtr
, &state
, sizeof(state
));
378 FORCE_INLINE XXH_errorcode
XXH32_update_endian (XXH32_state_t
* state
, const void* input
, size_t len
, XXH_endianess endian
)
380 const BYTE
* p
= (const BYTE
*)input
;
381 const BYTE
* const bEnd
= p
+ len
;
383 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
384 if (input
==NULL
) return XXH_ERROR
;
387 state
->total_len_32
+= (unsigned)len
;
388 state
->large_len
|= (len
>=16) | (state
->total_len_32
>=16);
390 if (state
->memsize
+ len
< 16) { /* fill in tmp buffer */
391 XXH_memcpy((BYTE
*)(state
->mem32
) + state
->memsize
, input
, len
);
392 state
->memsize
+= (unsigned)len
;
396 if (state
->memsize
) { /* some data left from previous update */
397 XXH_memcpy((BYTE
*)(state
->mem32
) + state
->memsize
, input
, 16-state
->memsize
);
398 { const U32
* p32
= state
->mem32
;
399 state
->v1
= XXH32_round(state
->v1
, XXH_readLE32(p32
, endian
)); p32
++;
400 state
->v2
= XXH32_round(state
->v2
, XXH_readLE32(p32
, endian
)); p32
++;
401 state
->v3
= XXH32_round(state
->v3
, XXH_readLE32(p32
, endian
)); p32
++;
402 state
->v4
= XXH32_round(state
->v4
, XXH_readLE32(p32
, endian
));
404 p
+= 16-state
->memsize
;
409 const BYTE
* const limit
= bEnd
- 16;
416 v1
= XXH32_round(v1
, XXH_readLE32(p
, endian
)); p
+=4;
417 v2
= XXH32_round(v2
, XXH_readLE32(p
, endian
)); p
+=4;
418 v3
= XXH32_round(v3
, XXH_readLE32(p
, endian
)); p
+=4;
419 v4
= XXH32_round(v4
, XXH_readLE32(p
, endian
)); p
+=4;
429 XXH_memcpy(state
->mem32
, p
, (size_t)(bEnd
-p
));
430 state
->memsize
= (unsigned)(bEnd
-p
);
436 XXH_PUBLIC_API XXH_errorcode
XXH32_update (XXH32_state_t
* state_in
, const void* input
, size_t len
)
438 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
440 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
441 return XXH32_update_endian(state_in
, input
, len
, XXH_littleEndian
);
443 return XXH32_update_endian(state_in
, input
, len
, XXH_bigEndian
);
448 FORCE_INLINE U32
XXH32_digest_endian (const XXH32_state_t
* state
, XXH_endianess endian
)
450 const BYTE
* p
= (const BYTE
*)state
->mem32
;
451 const BYTE
* const bEnd
= (const BYTE
*)(state
->mem32
) + state
->memsize
;
454 if (state
->large_len
) {
455 h32
= XXH_rotl32(state
->v1
, 1) + XXH_rotl32(state
->v2
, 7) + XXH_rotl32(state
->v3
, 12) + XXH_rotl32(state
->v4
, 18);
457 h32
= state
->v3
/* == seed */ + PRIME32_5
;
460 h32
+= state
->total_len_32
;
463 h32
+= XXH_readLE32(p
, endian
) * PRIME32_3
;
464 h32
= XXH_rotl32(h32
, 17) * PRIME32_4
;
469 h32
+= (*p
) * PRIME32_5
;
470 h32
= XXH_rotl32(h32
, 11) * PRIME32_1
;
484 XXH_PUBLIC_API
unsigned int XXH32_digest (const XXH32_state_t
* state_in
)
486 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
488 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
489 return XXH32_digest_endian(state_in
, XXH_littleEndian
);
491 return XXH32_digest_endian(state_in
, XXH_bigEndian
);
495 /*====== Canonical representation ======*/
497 /*! Default XXH result types are basic unsigned 32 and 64 bits.
498 * The canonical representation follows human-readable write convention, aka big-endian (large digits first).
499 * These functions allow transformation of hash result into and from its canonical format.
500 * This way, hash values can be written into a file or buffer, and remain comparable across different systems and programs.
503 XXH_PUBLIC_API
void XXH32_canonicalFromHash(XXH32_canonical_t
* dst
, XXH32_hash_t hash
)
505 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t
) == sizeof(XXH32_hash_t
));
506 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap32(hash
);
507 memcpy(dst
, &hash
, sizeof(*dst
));
510 XXH_PUBLIC_API XXH32_hash_t
XXH32_hashFromCanonical(const XXH32_canonical_t
* src
)
512 return XXH_readBE32(src
);
516 #ifndef XXH_NO_LONG_LONG
518 /* *******************************************************************
519 * 64-bits hash functions
520 *********************************************************************/
522 /*====== Memory access ======*/
526 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
528 typedef uint64_t U64
;
530 typedef unsigned long long U64
; /* if your compiler doesn't support unsigned long long, replace by another 64-bit type here. Note that xxhash.h will also need to be updated. */
535 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
537 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
538 static U64
XXH_read64(const void* memPtr
) { return *(const U64
*) memPtr
; }
540 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
542 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
543 /* currently only defined for gcc and icc */
544 typedef union { U32 u32
; U64 u64
; } __attribute__((packed
)) unalign64
;
545 static U64
XXH_read64(const void* ptr
) { return ((const unalign64
*)ptr
)->u64
; }
549 /* portable and safe solution. Generally efficient.
550 * see : http://stackoverflow.com/a/32095106/646947
553 static U64
XXH_read64(const void* memPtr
)
556 memcpy(&val
, memPtr
, sizeof(val
));
560 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
562 #if defined(_MSC_VER) /* Visual Studio */
563 # define XXH_swap64 _byteswap_uint64
564 #elif XXH_GCC_VERSION >= 403
565 # define XXH_swap64 __builtin_bswap64
567 static U64
XXH_swap64 (U64 x
)
569 return ((x
<< 56) & 0xff00000000000000ULL
) |
570 ((x
<< 40) & 0x00ff000000000000ULL
) |
571 ((x
<< 24) & 0x0000ff0000000000ULL
) |
572 ((x
<< 8) & 0x000000ff00000000ULL
) |
573 ((x
>> 8) & 0x00000000ff000000ULL
) |
574 ((x
>> 24) & 0x0000000000ff0000ULL
) |
575 ((x
>> 40) & 0x000000000000ff00ULL
) |
576 ((x
>> 56) & 0x00000000000000ffULL
);
580 FORCE_INLINE U64
XXH_readLE64_align(const void* ptr
, XXH_endianess endian
, XXH_alignment align
)
582 if (align
==XXH_unaligned
)
583 return endian
==XXH_littleEndian
? XXH_read64(ptr
) : XXH_swap64(XXH_read64(ptr
));
585 return endian
==XXH_littleEndian
? *(const U64
*)ptr
: XXH_swap64(*(const U64
*)ptr
);
588 FORCE_INLINE U64
XXH_readLE64(const void* ptr
, XXH_endianess endian
)
590 return XXH_readLE64_align(ptr
, endian
, XXH_unaligned
);
593 static U64
XXH_readBE64(const void* ptr
)
595 return XXH_CPU_LITTLE_ENDIAN
? XXH_swap64(XXH_read64(ptr
)) : XXH_read64(ptr
);
599 /*====== xxh64 ======*/
601 static const U64 PRIME64_1
= 11400714785074694791ULL;
602 static const U64 PRIME64_2
= 14029467366897019727ULL;
603 static const U64 PRIME64_3
= 1609587929392839161ULL;
604 static const U64 PRIME64_4
= 9650029242287828579ULL;
605 static const U64 PRIME64_5
= 2870177450012600261ULL;
607 static U64
XXH64_round(U64 acc
, U64 input
)
609 acc
+= input
* PRIME64_2
;
610 acc
= XXH_rotl64(acc
, 31);
615 static U64
XXH64_mergeRound(U64 acc
, U64 val
)
617 val
= XXH64_round(0, val
);
619 acc
= acc
* PRIME64_1
+ PRIME64_4
;
623 FORCE_INLINE U64
XXH64_endian_align(const void* input
, size_t len
, U64 seed
, XXH_endianess endian
, XXH_alignment align
)
625 const BYTE
* p
= (const BYTE
*)input
;
626 const BYTE
* bEnd
= p
+ len
;
628 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
630 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
633 bEnd
=p
=(const BYTE
*)(size_t)32;
638 const BYTE
* const limit
= bEnd
- 32;
639 U64 v1
= seed
+ PRIME64_1
+ PRIME64_2
;
640 U64 v2
= seed
+ PRIME64_2
;
642 U64 v4
= seed
- PRIME64_1
;
645 v1
= XXH64_round(v1
, XXH_get64bits(p
)); p
+=8;
646 v2
= XXH64_round(v2
, XXH_get64bits(p
)); p
+=8;
647 v3
= XXH64_round(v3
, XXH_get64bits(p
)); p
+=8;
648 v4
= XXH64_round(v4
, XXH_get64bits(p
)); p
+=8;
651 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
652 h64
= XXH64_mergeRound(h64
, v1
);
653 h64
= XXH64_mergeRound(h64
, v2
);
654 h64
= XXH64_mergeRound(h64
, v3
);
655 h64
= XXH64_mergeRound(h64
, v4
);
658 h64
= seed
+ PRIME64_5
;
664 U64
const k1
= XXH64_round(0, XXH_get64bits(p
));
666 h64
= XXH_rotl64(h64
,27) * PRIME64_1
+ PRIME64_4
;
671 h64
^= (U64
)(XXH_get32bits(p
)) * PRIME64_1
;
672 h64
= XXH_rotl64(h64
, 23) * PRIME64_2
+ PRIME64_3
;
677 h64
^= (*p
) * PRIME64_5
;
678 h64
= XXH_rotl64(h64
, 11) * PRIME64_1
;
692 XXH_PUBLIC_API
unsigned long long XXH64 (const void* input
, size_t len
, unsigned long long seed
)
695 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
697 XXH64_reset(&state
, seed
);
698 XXH64_update(&state
, input
, len
);
699 return XXH64_digest(&state
);
701 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
703 if (XXH_FORCE_ALIGN_CHECK
) {
704 if ((((size_t)input
) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
705 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
706 return XXH64_endian_align(input
, len
, seed
, XXH_littleEndian
, XXH_aligned
);
708 return XXH64_endian_align(input
, len
, seed
, XXH_bigEndian
, XXH_aligned
);
711 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
712 return XXH64_endian_align(input
, len
, seed
, XXH_littleEndian
, XXH_unaligned
);
714 return XXH64_endian_align(input
, len
, seed
, XXH_bigEndian
, XXH_unaligned
);
718 /*====== Hash Streaming ======*/
720 XXH_PUBLIC_API XXH64_state_t
* XXH64_createState(void)
722 return (XXH64_state_t
*)XXH_malloc(sizeof(XXH64_state_t
));
724 XXH_PUBLIC_API XXH_errorcode
XXH64_freeState(XXH64_state_t
* statePtr
)
730 XXH_PUBLIC_API
void XXH64_copyState(XXH64_state_t
* dstState
, const XXH64_state_t
* srcState
)
732 memcpy(dstState
, srcState
, sizeof(*dstState
));
735 XXH_PUBLIC_API XXH_errorcode
XXH64_reset(XXH64_state_t
* statePtr
, unsigned long long seed
)
737 XXH64_state_t state
; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
738 memset(&state
, 0, sizeof(state
)-8); /* do not write into reserved, for future removal */
739 state
.v1
= seed
+ PRIME64_1
+ PRIME64_2
;
740 state
.v2
= seed
+ PRIME64_2
;
742 state
.v4
= seed
- PRIME64_1
;
743 memcpy(statePtr
, &state
, sizeof(state
));
747 FORCE_INLINE XXH_errorcode
XXH64_update_endian (XXH64_state_t
* state
, const void* input
, size_t len
, XXH_endianess endian
)
749 const BYTE
* p
= (const BYTE
*)input
;
750 const BYTE
* const bEnd
= p
+ len
;
752 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
753 if (input
==NULL
) return XXH_ERROR
;
756 state
->total_len
+= len
;
758 if (state
->memsize
+ len
< 32) { /* fill in tmp buffer */
759 XXH_memcpy(((BYTE
*)state
->mem64
) + state
->memsize
, input
, len
);
760 state
->memsize
+= (U32
)len
;
764 if (state
->memsize
) { /* tmp buffer is full */
765 XXH_memcpy(((BYTE
*)state
->mem64
) + state
->memsize
, input
, 32-state
->memsize
);
766 state
->v1
= XXH64_round(state
->v1
, XXH_readLE64(state
->mem64
+0, endian
));
767 state
->v2
= XXH64_round(state
->v2
, XXH_readLE64(state
->mem64
+1, endian
));
768 state
->v3
= XXH64_round(state
->v3
, XXH_readLE64(state
->mem64
+2, endian
));
769 state
->v4
= XXH64_round(state
->v4
, XXH_readLE64(state
->mem64
+3, endian
));
770 p
+= 32-state
->memsize
;
775 const BYTE
* const limit
= bEnd
- 32;
782 v1
= XXH64_round(v1
, XXH_readLE64(p
, endian
)); p
+=8;
783 v2
= XXH64_round(v2
, XXH_readLE64(p
, endian
)); p
+=8;
784 v3
= XXH64_round(v3
, XXH_readLE64(p
, endian
)); p
+=8;
785 v4
= XXH64_round(v4
, XXH_readLE64(p
, endian
)); p
+=8;
795 XXH_memcpy(state
->mem64
, p
, (size_t)(bEnd
-p
));
796 state
->memsize
= (unsigned)(bEnd
-p
);
802 XXH_PUBLIC_API XXH_errorcode
XXH64_update (XXH64_state_t
* state_in
, const void* input
, size_t len
)
804 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
806 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
807 return XXH64_update_endian(state_in
, input
, len
, XXH_littleEndian
);
809 return XXH64_update_endian(state_in
, input
, len
, XXH_bigEndian
);
812 FORCE_INLINE U64
XXH64_digest_endian (const XXH64_state_t
* state
, XXH_endianess endian
)
814 const BYTE
* p
= (const BYTE
*)state
->mem64
;
815 const BYTE
* const bEnd
= (const BYTE
*)state
->mem64
+ state
->memsize
;
818 if (state
->total_len
>= 32) {
819 U64
const v1
= state
->v1
;
820 U64
const v2
= state
->v2
;
821 U64
const v3
= state
->v3
;
822 U64
const v4
= state
->v4
;
824 h64
= XXH_rotl64(v1
, 1) + XXH_rotl64(v2
, 7) + XXH_rotl64(v3
, 12) + XXH_rotl64(v4
, 18);
825 h64
= XXH64_mergeRound(h64
, v1
);
826 h64
= XXH64_mergeRound(h64
, v2
);
827 h64
= XXH64_mergeRound(h64
, v3
);
828 h64
= XXH64_mergeRound(h64
, v4
);
830 h64
= state
->v3
+ PRIME64_5
;
833 h64
+= (U64
) state
->total_len
;
836 U64
const k1
= XXH64_round(0, XXH_readLE64(p
, endian
));
838 h64
= XXH_rotl64(h64
,27) * PRIME64_1
+ PRIME64_4
;
843 h64
^= (U64
)(XXH_readLE32(p
, endian
)) * PRIME64_1
;
844 h64
= XXH_rotl64(h64
, 23) * PRIME64_2
+ PRIME64_3
;
849 h64
^= (*p
) * PRIME64_5
;
850 h64
= XXH_rotl64(h64
, 11) * PRIME64_1
;
863 XXH_PUBLIC_API
unsigned long long XXH64_digest (const XXH64_state_t
* state_in
)
865 XXH_endianess endian_detected
= (XXH_endianess
)XXH_CPU_LITTLE_ENDIAN
;
867 if ((endian_detected
==XXH_littleEndian
) || XXH_FORCE_NATIVE_FORMAT
)
868 return XXH64_digest_endian(state_in
, XXH_littleEndian
);
870 return XXH64_digest_endian(state_in
, XXH_bigEndian
);
874 /*====== Canonical representation ======*/
876 XXH_PUBLIC_API
void XXH64_canonicalFromHash(XXH64_canonical_t
* dst
, XXH64_hash_t hash
)
878 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t
) == sizeof(XXH64_hash_t
));
879 if (XXH_CPU_LITTLE_ENDIAN
) hash
= XXH_swap64(hash
);
880 memcpy(dst
, &hash
, sizeof(*dst
));
883 XXH_PUBLIC_API XXH64_hash_t
XXH64_hashFromCanonical(const XXH64_canonical_t
* src
)
885 return XXH_readBE64(src
);
888 #endif /* XXH_NO_LONG_LONG */