1 /*
2 * xxHash - Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * You can contact the author at :
31 * - xxHash homepage: http://www.xxhash.com
32 * - xxHash source repository : https://github.com/Cyan4973/xxHash
33 */
34
35
36 /* *************************************
37 * Tuning parameters
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)
51 */
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
58 # endif
59 #endif
60
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 :
65 */
66 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */
67
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.
75 */
76 #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */
77 # define XXH_FORCE_NATIVE_FORMAT 0
78 #endif
79
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.
86 */
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
90 # else
91 # define XXH_FORCE_ALIGN_CHECK 1
92 # endif
93 #endif
94
95
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() */
101 #include <stdlib.h>
XXH_malloc(size_t s)102 static void* XXH_malloc(size_t s) { return malloc(s); }
XXH_free(void * p)103 static void XXH_free (void* p) { free(p); }
104 /*! and for memcpy() */
105 #include <string.h>
XXH_memcpy(void * dest,const void * src,size_t size)106 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
107
108 #define XXH_STATIC_LINKING_ONLY
109 #include "xxhash.h"
110
111
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
118 #else
119 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
120 # ifdef __GNUC__
121 # define FORCE_INLINE static inline __attribute__((always_inline))
122 # else
123 # define FORCE_INLINE static inline
124 # endif
125 # else
126 # define FORCE_INLINE static
127 # endif /* __STDC_VERSION__ */
128 #endif
129
130
131 /* *************************************
132 * Basic Types
133 ***************************************/
134 #ifndef MEM_MODULE
135 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
136 # include <stdint.h>
137 typedef uint8_t BYTE;
138 typedef uint16_t U16;
139 typedef uint32_t U32;
140 # else
141 typedef unsigned char BYTE;
142 typedef unsigned short U16;
143 typedef unsigned int U32;
144 # endif
145 #endif
146
147 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
148
149 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
XXH_read32(const void * memPtr)150 static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; }
151
152 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
153
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;
XXH_read32(const void * ptr)157 static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
158
159 #else
160
161 /* portable and safe solution. Generally efficient.
162 * see : http://stackoverflow.com/a/32095106/646947
163 */
XXH_read32(const void * memPtr)164 static U32 XXH_read32(const void* memPtr)
165 {
166 U32 val;
167 memcpy(&val, memPtr, sizeof(val));
168 return val;
169 }
170
171 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
172
173
174 /* ****************************************
175 * Compiler-specific Functions and Macros
176 ******************************************/
177 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
178
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)
183 #else
184 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
185 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
186 #endif
187
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
192 #else
XXH_swap32(U32 x)193 static U32 XXH_swap32 (U32 x)
194 {
195 return ((x << 24) & 0xff000000 ) |
196 ((x << 8) & 0x00ff0000 ) |
197 ((x >> 8) & 0x0000ff00 ) |
198 ((x >> 24) & 0x000000ff );
199 }
200 #endif
201
202
203 /* *************************************
204 * Architecture Macros
205 ***************************************/
206 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
207
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))
212 #endif
213
214
215 /* ***************************
216 * Memory reads
217 *****************************/
218 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
219
XXH_readLE32_align(const void * ptr,XXH_endianess endian,XXH_alignment align)220 FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
221 {
222 if (align==XXH_unaligned)
223 return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr));
224 else
225 return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr);
226 }
227
XXH_readLE32(const void * ptr,XXH_endianess endian)228 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
229 {
230 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
231 }
232
XXH_readBE32(const void * ptr)233 static U32 XXH_readBE32(const void* ptr)
234 {
235 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr);
236 }
237
238
239 /* *************************************
240 * Macros
241 ***************************************/
242 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
XXH_versionNumber(void)243 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; }
244
245
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;
254
XXH32_round(U32 seed,U32 input)255 static U32 XXH32_round(U32 seed, U32 input)
256 {
257 seed += input * PRIME32_2;
258 seed = XXH_rotl32(seed, 13);
259 seed *= PRIME32_1;
260 return seed;
261 }
262
XXH32_endian_align(const void * input,size_t len,U32 seed,XXH_endianess endian,XXH_alignment align)263 FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
264 {
265 const BYTE* p = (const BYTE*)input;
266 const BYTE* bEnd = p + len;
267 U32 h32;
268 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
269
270 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
271 if (p==NULL) {
272 len=0;
273 bEnd=p=(const BYTE*)(size_t)16;
274 }
275 #endif
276
277 if (len>=16) {
278 const BYTE* const limit = bEnd - 16;
279 U32 v1 = seed + PRIME32_1 + PRIME32_2;
280 U32 v2 = seed + PRIME32_2;
281 U32 v3 = seed + 0;
282 U32 v4 = seed - PRIME32_1;
283
284 do {
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;
289 } while (p<=limit);
290
291 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
292 } else {
293 h32 = seed + PRIME32_5;
294 }
295
296 h32 += (U32) len;
297
298 while (p+4<=bEnd) {
299 h32 += XXH_get32bits(p) * PRIME32_3;
300 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
301 p+=4;
302 }
303
304 while (p<bEnd) {
305 h32 += (*p) * PRIME32_5;
306 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
307 p++;
308 }
309
310 h32 ^= h32 >> 15;
311 h32 *= PRIME32_2;
312 h32 ^= h32 >> 13;
313 h32 *= PRIME32_3;
314 h32 ^= h32 >> 16;
315
316 return h32;
317 }
318
319
XXH32(const void * input,size_t len,unsigned int seed)320 XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed)
321 {
322 #if 0
323 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
324 XXH32_state_t state;
325 XXH32_reset(&state, seed);
326 XXH32_update(&state, input, len);
327 return XXH32_digest(&state);
328 #else
329 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
330
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);
335 else
336 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
337 } }
338
339 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
340 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
341 else
342 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
343 #endif
344 }
345
346
347
348 /*====== Hash streaming ======*/
349
XXH32_createState(void)350 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void)
351 {
352 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
353 }
XXH32_freeState(XXH32_state_t * statePtr)354 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
355 {
356 XXH_free(statePtr);
357 return XXH_OK;
358 }
359
XXH32_copyState(XXH32_state_t * dstState,const XXH32_state_t * srcState)360 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState)
361 {
362 memcpy(dstState, srcState, sizeof(*dstState));
363 }
364
XXH32_reset(XXH32_state_t * statePtr,unsigned int seed)365 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed)
366 {
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;
371 state.v3 = seed + 0;
372 state.v4 = seed - PRIME32_1;
373 memcpy(statePtr, &state, sizeof(state));
374 return XXH_OK;
375 }
376
377
XXH32_update_endian(XXH32_state_t * state,const void * input,size_t len,XXH_endianess endian)378 FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian)
379 {
380 const BYTE* p = (const BYTE*)input;
381 const BYTE* const bEnd = p + len;
382
383 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
384 if (input==NULL) return XXH_ERROR;
385 #endif
386
387 state->total_len_32 += (unsigned)len;
388 state->large_len |= (len>=16) | (state->total_len_32>=16);
389
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;
393 return XXH_OK;
394 }
395
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));
403 }
404 p += 16-state->memsize;
405 state->memsize = 0;
406 }
407
408 if (p <= bEnd-16) {
409 const BYTE* const limit = bEnd - 16;
410 U32 v1 = state->v1;
411 U32 v2 = state->v2;
412 U32 v3 = state->v3;
413 U32 v4 = state->v4;
414
415 do {
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;
420 } while (p<=limit);
421
422 state->v1 = v1;
423 state->v2 = v2;
424 state->v3 = v3;
425 state->v4 = v4;
426 }
427
428 if (p < bEnd) {
429 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p));
430 state->memsize = (unsigned)(bEnd-p);
431 }
432
433 return XXH_OK;
434 }
435
XXH32_update(XXH32_state_t * state_in,const void * input,size_t len)436 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
437 {
438 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
439
440 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
441 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
442 else
443 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
444 }
445
446
447
XXH32_digest_endian(const XXH32_state_t * state,XXH_endianess endian)448 FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian)
449 {
450 const BYTE * p = (const BYTE*)state->mem32;
451 const BYTE* const bEnd = (const BYTE*)(state->mem32) + state->memsize;
452 U32 h32;
453
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);
456 } else {
457 h32 = state->v3 /* == seed */ + PRIME32_5;
458 }
459
460 h32 += state->total_len_32;
461
462 while (p+4<=bEnd) {
463 h32 += XXH_readLE32(p, endian) * PRIME32_3;
464 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
465 p+=4;
466 }
467
468 while (p<bEnd) {
469 h32 += (*p) * PRIME32_5;
470 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
471 p++;
472 }
473
474 h32 ^= h32 >> 15;
475 h32 *= PRIME32_2;
476 h32 ^= h32 >> 13;
477 h32 *= PRIME32_3;
478 h32 ^= h32 >> 16;
479
480 return h32;
481 }
482
483
XXH32_digest(const XXH32_state_t * state_in)484 XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in)
485 {
486 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
487
488 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
489 return XXH32_digest_endian(state_in, XXH_littleEndian);
490 else
491 return XXH32_digest_endian(state_in, XXH_bigEndian);
492 }
493
494
495 /*====== Canonical representation ======*/
496
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.
501 */
502
XXH32_canonicalFromHash(XXH32_canonical_t * dst,XXH32_hash_t hash)503 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash)
504 {
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));
508 }
509
XXH32_hashFromCanonical(const XXH32_canonical_t * src)510 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src)
511 {
512 return XXH_readBE32(src);
513 }
514
515
516 #ifndef XXH_NO_LONG_LONG
517
518 /* *******************************************************************
519 * 64-bits hash functions
520 *********************************************************************/
521
522 /*====== Memory access ======*/
523
524 #ifndef MEM_MODULE
525 # define MEM_MODULE
526 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
527 # include <stdint.h>
528 typedef uint64_t U64;
529 # else
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. */
531 # endif
532 #endif
533
534
535 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
536
537 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
XXH_read64(const void * memPtr)538 static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; }
539
540 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
541
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;
XXH_read64(const void * ptr)545 static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; }
546
547 #else
548
549 /* portable and safe solution. Generally efficient.
550 * see : http://stackoverflow.com/a/32095106/646947
551 */
552
XXH_read64(const void * memPtr)553 static U64 XXH_read64(const void* memPtr)
554 {
555 U64 val;
556 memcpy(&val, memPtr, sizeof(val));
557 return val;
558 }
559
560 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
561
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
566 #else
XXH_swap64(U64 x)567 static U64 XXH_swap64 (U64 x)
568 {
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);
577 }
578 #endif
579
XXH_readLE64_align(const void * ptr,XXH_endianess endian,XXH_alignment align)580 FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
581 {
582 if (align==XXH_unaligned)
583 return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr));
584 else
585 return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr);
586 }
587
XXH_readLE64(const void * ptr,XXH_endianess endian)588 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
589 {
590 return XXH_readLE64_align(ptr, endian, XXH_unaligned);
591 }
592
XXH_readBE64(const void * ptr)593 static U64 XXH_readBE64(const void* ptr)
594 {
595 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr);
596 }
597
598
599 /*====== xxh64 ======*/
600
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;
606
XXH64_round(U64 acc,U64 input)607 static U64 XXH64_round(U64 acc, U64 input)
608 {
609 acc += input * PRIME64_2;
610 acc = XXH_rotl64(acc, 31);
611 acc *= PRIME64_1;
612 return acc;
613 }
614
XXH64_mergeRound(U64 acc,U64 val)615 static U64 XXH64_mergeRound(U64 acc, U64 val)
616 {
617 val = XXH64_round(0, val);
618 acc ^= val;
619 acc = acc * PRIME64_1 + PRIME64_4;
620 return acc;
621 }
622
XXH64_endian_align(const void * input,size_t len,U64 seed,XXH_endianess endian,XXH_alignment align)623 FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
624 {
625 const BYTE* p = (const BYTE*)input;
626 const BYTE* bEnd = p + len;
627 U64 h64;
628 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
629
630 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
631 if (p==NULL) {
632 len=0;
633 bEnd=p=(const BYTE*)(size_t)32;
634 }
635 #endif
636
637 if (len>=32) {
638 const BYTE* const limit = bEnd - 32;
639 U64 v1 = seed + PRIME64_1 + PRIME64_2;
640 U64 v2 = seed + PRIME64_2;
641 U64 v3 = seed + 0;
642 U64 v4 = seed - PRIME64_1;
643
644 do {
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;
649 } while (p<=limit);
650
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);
656
657 } else {
658 h64 = seed + PRIME64_5;
659 }
660
661 h64 += (U64) len;
662
663 while (p+8<=bEnd) {
664 U64 const k1 = XXH64_round(0, XXH_get64bits(p));
665 h64 ^= k1;
666 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
667 p+=8;
668 }
669
670 if (p+4<=bEnd) {
671 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
672 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
673 p+=4;
674 }
675
676 while (p<bEnd) {
677 h64 ^= (*p) * PRIME64_5;
678 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
679 p++;
680 }
681
682 h64 ^= h64 >> 33;
683 h64 *= PRIME64_2;
684 h64 ^= h64 >> 29;
685 h64 *= PRIME64_3;
686 h64 ^= h64 >> 32;
687
688 return h64;
689 }
690
691
XXH64(const void * input,size_t len,unsigned long long seed)692 XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed)
693 {
694 #if 0
695 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
696 XXH64_state_t state;
697 XXH64_reset(&state, seed);
698 XXH64_update(&state, input, len);
699 return XXH64_digest(&state);
700 #else
701 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
702
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);
707 else
708 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
709 } }
710
711 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
712 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
713 else
714 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
715 #endif
716 }
717
718 /*====== Hash Streaming ======*/
719
XXH64_createState(void)720 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void)
721 {
722 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
723 }
XXH64_freeState(XXH64_state_t * statePtr)724 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
725 {
726 XXH_free(statePtr);
727 return XXH_OK;
728 }
729
XXH64_copyState(XXH64_state_t * dstState,const XXH64_state_t * srcState)730 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState)
731 {
732 memcpy(dstState, srcState, sizeof(*dstState));
733 }
734
XXH64_reset(XXH64_state_t * statePtr,unsigned long long seed)735 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed)
736 {
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;
741 state.v3 = seed + 0;
742 state.v4 = seed - PRIME64_1;
743 memcpy(statePtr, &state, sizeof(state));
744 return XXH_OK;
745 }
746
XXH64_update_endian(XXH64_state_t * state,const void * input,size_t len,XXH_endianess endian)747 FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian)
748 {
749 const BYTE* p = (const BYTE*)input;
750 const BYTE* const bEnd = p + len;
751
752 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
753 if (input==NULL) return XXH_ERROR;
754 #endif
755
756 state->total_len += len;
757
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;
761 return XXH_OK;
762 }
763
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;
771 state->memsize = 0;
772 }
773
774 if (p+32 <= bEnd) {
775 const BYTE* const limit = bEnd - 32;
776 U64 v1 = state->v1;
777 U64 v2 = state->v2;
778 U64 v3 = state->v3;
779 U64 v4 = state->v4;
780
781 do {
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;
786 } while (p<=limit);
787
788 state->v1 = v1;
789 state->v2 = v2;
790 state->v3 = v3;
791 state->v4 = v4;
792 }
793
794 if (p < bEnd) {
795 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p));
796 state->memsize = (unsigned)(bEnd-p);
797 }
798
799 return XXH_OK;
800 }
801
XXH64_update(XXH64_state_t * state_in,const void * input,size_t len)802 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
803 {
804 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
805
806 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
807 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
808 else
809 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
810 }
811
XXH64_digest_endian(const XXH64_state_t * state,XXH_endianess endian)812 FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian)
813 {
814 const BYTE * p = (const BYTE*)state->mem64;
815 const BYTE* const bEnd = (const BYTE*)state->mem64 + state->memsize;
816 U64 h64;
817
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;
823
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);
829 } else {
830 h64 = state->v3 + PRIME64_5;
831 }
832
833 h64 += (U64) state->total_len;
834
835 while (p+8<=bEnd) {
836 U64 const k1 = XXH64_round(0, XXH_readLE64(p, endian));
837 h64 ^= k1;
838 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
839 p+=8;
840 }
841
842 if (p+4<=bEnd) {
843 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
844 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
845 p+=4;
846 }
847
848 while (p<bEnd) {
849 h64 ^= (*p) * PRIME64_5;
850 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
851 p++;
852 }
853
854 h64 ^= h64 >> 33;
855 h64 *= PRIME64_2;
856 h64 ^= h64 >> 29;
857 h64 *= PRIME64_3;
858 h64 ^= h64 >> 32;
859
860 return h64;
861 }
862
XXH64_digest(const XXH64_state_t * state_in)863 XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in)
864 {
865 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
866
867 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
868 return XXH64_digest_endian(state_in, XXH_littleEndian);
869 else
870 return XXH64_digest_endian(state_in, XXH_bigEndian);
871 }
872
873
874 /*====== Canonical representation ======*/
875
XXH64_canonicalFromHash(XXH64_canonical_t * dst,XXH64_hash_t hash)876 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash)
877 {
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));
881 }
882
XXH64_hashFromCanonical(const XXH64_canonical_t * src)883 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src)
884 {
885 return XXH_readBE64(src);
886 }
887
888 #endif /* XXH_NO_LONG_LONG */
889