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; set to 0 when the input data
84 * is guaranteed to be aligned.
85 */
86#ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
87# if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
88# define XXH_FORCE_ALIGN_CHECK 0
89# else
90# define XXH_FORCE_ALIGN_CHECK 1
91# endif
92#endif
93
94
95/* *************************************
96* Includes & Memory related functions
97***************************************/
98/*! Modify the local functions below should you wish to use some other memory routines
99* for malloc(), free() */
100#include <stdlib.h>
101static void* XXH_malloc(size_t s) { return malloc(s); }
102static void XXH_free (void* p) { free(p); }
103/*! and for memcpy() */
104#include <string.h>
105static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
106
107#define XXH_STATIC_LINKING_ONLY
108#include "xxhash.h"
109
110
111/* *************************************
112* Compiler Specific Options
113***************************************/
114#ifdef _MSC_VER /* Visual Studio */
115# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
116# define FORCE_INLINE static __forceinline
117#else
118# if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
119# ifdef __GNUC__
120# define FORCE_INLINE static inline __attribute__((always_inline))
121# else
122# define FORCE_INLINE static inline
123# endif
124# else
125# define FORCE_INLINE static
126# endif /* __STDC_VERSION__ */
127#endif
128
129
130/* *************************************
131* Basic Types
132***************************************/
133#ifndef MEM_MODULE
134# if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
135# include <stdint.h>
136 typedef uint8_t BYTE;
137 typedef uint16_t U16;
138 typedef uint32_t U32;
139 typedef int32_t S32;
140# else
141 typedef unsigned char BYTE;
142 typedef unsigned short U16;
143 typedef unsigned int U32;
144 typedef signed int S32;
145# endif
146#endif
147
148#if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
149
150/* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
151static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; }
152
153#elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
154
155/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
156/* currently only defined for gcc and icc */
157typedef union { U32 u32; } __attribute__((packed)) unalign;
158static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
159
160#else
161
162/* portable and safe solution. Generally efficient.
163 * see : http://stackoverflow.com/a/32095106/646947
164 */
165static U32 XXH_read32(const void* memPtr)
166{
167 U32 val;
168 memcpy(&val, memPtr, sizeof(val));
169 return val;
170}
171
172#endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
173
174
175/* ****************************************
176* Compiler-specific Functions and Macros
177******************************************/
178#define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
179
180/* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
181#if defined(_MSC_VER)
182# define XXH_rotl32(x,r) _rotl(x,r)
183# define XXH_rotl64(x,r) _rotl64(x,r)
184#else
185# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
186# define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
187#endif
188
189#if defined(_MSC_VER) /* Visual Studio */
190# define XXH_swap32 _byteswap_ulong
191#elif XXH_GCC_VERSION >= 403
192# define XXH_swap32 __builtin_bswap32
193#else
194static U32 XXH_swap32 (U32 x)
195{
196 return ((x << 24) & 0xff000000 ) |
197 ((x << 8) & 0x00ff0000 ) |
198 ((x >> 8) & 0x0000ff00 ) |
199 ((x >> 24) & 0x000000ff );
200}
201#endif
202
203
204/* *************************************
205* Architecture Macros
206***************************************/
207typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
208
209/* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
210#ifndef XXH_CPU_LITTLE_ENDIAN
211 static const int g_one = 1;
212# define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one))
213#endif
214
215
216/* ***************************
217* Memory reads
218*****************************/
219typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
220
221FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
222{
223 if (align==XXH_unaligned)
224 return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr));
225 else
226 return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr);
227}
228
229FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
230{
231 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
232}
233
234static U32 XXH_readBE32(const void* ptr)
235{
236 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr);
237}
238
239
240/* *************************************
241* Macros
242***************************************/
243#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
244XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; }
245
246
247/* *******************************************************************
248* 32-bits hash functions
249*********************************************************************/
250static const U32 PRIME32_1 = 2654435761U;
251static const U32 PRIME32_2 = 2246822519U;
252static const U32 PRIME32_3 = 3266489917U;
253static const U32 PRIME32_4 = 668265263U;
254static const U32 PRIME32_5 = 374761393U;
255
256static U32 XXH32_round(U32 seed, U32 input)
257{
258 seed += input * PRIME32_2;
259 seed = XXH_rotl32(seed, 13);
260 seed *= PRIME32_1;
261 return seed;
262}
263
264FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
265{
266 const BYTE* p = (const BYTE*)input;
267 const BYTE* bEnd = p + len;
268 U32 h32;
269#define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
270
271#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
272 if (p==NULL) {
273 len=0;
274 bEnd=p=(const BYTE*)(size_t)16;
275 }
276#endif
277
278 if (len>=16) {
279 const BYTE* const limit = bEnd - 16;
280 U32 v1 = seed + PRIME32_1 + PRIME32_2;
281 U32 v2 = seed + PRIME32_2;
282 U32 v3 = seed + 0;
283 U32 v4 = seed - PRIME32_1;
284
285 do {
286 v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4;
287 v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4;
288 v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4;
289 v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4;
290 } while (p<=limit);
291
292 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
293 } else {
294 h32 = seed + PRIME32_5;
295 }
296
297 h32 += (U32) len;
298
299 while (p+4<=bEnd) {
300 h32 += XXH_get32bits(p) * PRIME32_3;
301 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
302 p+=4;
303 }
304
305 while (p<bEnd) {
306 h32 += (*p) * PRIME32_5;
307 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
308 p++;
309 }
310
311 h32 ^= h32 >> 15;
312 h32 *= PRIME32_2;
313 h32 ^= h32 >> 13;
314 h32 *= PRIME32_3;
315 h32 ^= h32 >> 16;
316
317 return h32;
318}
319
320
321XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed)
322{
323#if 0
324 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
325 XXH32_state_t state;
326 XXH32_reset(&state, seed);
327 XXH32_update(&state, input, len);
328 return XXH32_digest(&state);
329#else
330 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
331
332 if (XXH_FORCE_ALIGN_CHECK) {
333 if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
334 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
335 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
336 else
337 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
338 } }
339
340 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
341 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
342 else
343 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
344#endif
345}
346
347
348
349/*====== Hash streaming ======*/
350
351XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void)
352{
353 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
354}
355XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
356{
357 XXH_free(statePtr);
358 return XXH_OK;
359}
360
361XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState)
362{
363 memcpy(dstState, srcState, sizeof(*dstState));
364}
365
366XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed)
367{
368 XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
369 memset(&state, 0, sizeof(state)-4); /* do not write into reserved, for future removal */
370 state.v1 = seed + PRIME32_1 + PRIME32_2;
371 state.v2 = seed + PRIME32_2;
372 state.v3 = seed + 0;
373 state.v4 = seed - PRIME32_1;
374 memcpy(statePtr, &state, sizeof(state));
375 return XXH_OK;
376}
377
378
379FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian)
380{
381 const BYTE* p = (const BYTE*)input;
382 const BYTE* const bEnd = p + len;
383
384#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
385 if (input==NULL) return XXH_ERROR;
386#endif
387
388 state->total_len_32 += (unsigned)len;
389 state->large_len |= (len>=16) | (state->total_len_32>=16);
390
391 if (state->memsize + len < 16) { /* fill in tmp buffer */
392 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
393 state->memsize += (unsigned)len;
394 return XXH_OK;
395 }
396
397 if (state->memsize) { /* some data left from previous update */
398 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
399 { const U32* p32 = state->mem32;
400 state->v1 = XXH32_round(state->v1, XXH_readLE32(p32, endian)); p32++;
401 state->v2 = XXH32_round(state->v2, XXH_readLE32(p32, endian)); p32++;
402 state->v3 = XXH32_round(state->v3, XXH_readLE32(p32, endian)); p32++;
403 state->v4 = XXH32_round(state->v4, XXH_readLE32(p32, endian)); p32++;
404 }
405 p += 16-state->memsize;
406 state->memsize = 0;
407 }
408
409 if (p <= bEnd-16) {
410 const BYTE* const limit = bEnd - 16;
411 U32 v1 = state->v1;
412 U32 v2 = state->v2;
413 U32 v3 = state->v3;
414 U32 v4 = state->v4;
415
416 do {
417 v1 = XXH32_round(v1, XXH_readLE32(p, endian)); p+=4;
418 v2 = XXH32_round(v2, XXH_readLE32(p, endian)); p+=4;
419 v3 = XXH32_round(v3, XXH_readLE32(p, endian)); p+=4;
420 v4 = XXH32_round(v4, XXH_readLE32(p, endian)); p+=4;
421 } while (p<=limit);
422
423 state->v1 = v1;
424 state->v2 = v2;
425 state->v3 = v3;
426 state->v4 = v4;
427 }
428
429 if (p < bEnd) {
430 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p));
431 state->memsize = (unsigned)(bEnd-p);
432 }
433
434 return XXH_OK;
435}
436
437XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
438{
439 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
440
441 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
442 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
443 else
444 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
445}
446
447
448
449FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian)
450{
451 const BYTE * p = (const BYTE*)state->mem32;
452 const BYTE* const bEnd = (const BYTE*)(state->mem32) + state->memsize;
453 U32 h32;
454
455 if (state->large_len) {
456 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
457 } else {
458 h32 = state->v3 /* == seed */ + PRIME32_5;
459 }
460
461 h32 += state->total_len_32;
462
463 while (p+4<=bEnd) {
464 h32 += XXH_readLE32(p, endian) * PRIME32_3;
465 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
466 p+=4;
467 }
468
469 while (p<bEnd) {
470 h32 += (*p) * PRIME32_5;
471 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
472 p++;
473 }
474
475 h32 ^= h32 >> 15;
476 h32 *= PRIME32_2;
477 h32 ^= h32 >> 13;
478 h32 *= PRIME32_3;
479 h32 ^= h32 >> 16;
480
481 return h32;
482}
483
484
485XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in)
486{
487 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
488
489 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
490 return XXH32_digest_endian(state_in, XXH_littleEndian);
491 else
492 return XXH32_digest_endian(state_in, XXH_bigEndian);
493}
494
495
496/*====== Canonical representation ======*/
497
498/*! Default XXH result types are basic unsigned 32 and 64 bits.
499* The canonical representation follows human-readable write convention, aka big-endian (large digits first).
500* These functions allow transformation of hash result into and from its canonical format.
501* This way, hash values can be written into a file or buffer, and remain comparable across different systems and programs.
502*/
503
504XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash)
505{
506 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t));
507 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash);
508 memcpy(dst, &hash, sizeof(*dst));
509}
510
511XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src)
512{
513 return XXH_readBE32(src);
514}
515
516
517#ifndef XXH_NO_LONG_LONG
518
519/* *******************************************************************
520* 64-bits hash functions
521*********************************************************************/
522
523/*====== Memory access ======*/
524
525#ifndef MEM_MODULE
526# define MEM_MODULE
527# if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
528# include <stdint.h>
529 typedef uint64_t U64;
530# else
531 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. */
532# endif
533#endif
534
535
536#if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
537
538/* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
539static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; }
540
541#elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
542
543/* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
544/* currently only defined for gcc and icc */
545typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign64;
546static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; }
547
548#else
549
550/* portable and safe solution. Generally efficient.
551 * see : http://stackoverflow.com/a/32095106/646947
552 */
553
554static U64 XXH_read64(const void* memPtr)
555{
556 U64 val;
557 memcpy(&val, memPtr, sizeof(val));
558 return val;
559}
560
561#endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
562
563#if defined(_MSC_VER) /* Visual Studio */
564# define XXH_swap64 _byteswap_uint64
565#elif XXH_GCC_VERSION >= 403
566# define XXH_swap64 __builtin_bswap64
567#else
568static U64 XXH_swap64 (U64 x)
569{
570 return ((x << 56) & 0xff00000000000000ULL) |
571 ((x << 40) & 0x00ff000000000000ULL) |
572 ((x << 24) & 0x0000ff0000000000ULL) |
573 ((x << 8) & 0x000000ff00000000ULL) |
574 ((x >> 8) & 0x00000000ff000000ULL) |
575 ((x >> 24) & 0x0000000000ff0000ULL) |
576 ((x >> 40) & 0x000000000000ff00ULL) |
577 ((x >> 56) & 0x00000000000000ffULL);
578}
579#endif
580
581FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
582{
583 if (align==XXH_unaligned)
584 return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr));
585 else
586 return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr);
587}
588
589FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
590{
591 return XXH_readLE64_align(ptr, endian, XXH_unaligned);
592}
593
594static U64 XXH_readBE64(const void* ptr)
595{
596 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr);
597}
598
599
600/*====== xxh64 ======*/
601
602static const U64 PRIME64_1 = 11400714785074694791ULL;
603static const U64 PRIME64_2 = 14029467366897019727ULL;
604static const U64 PRIME64_3 = 1609587929392839161ULL;
605static const U64 PRIME64_4 = 9650029242287828579ULL;
606static const U64 PRIME64_5 = 2870177450012600261ULL;
607
608static U64 XXH64_round(U64 acc, U64 input)
609{
610 acc += input * PRIME64_2;
611 acc = XXH_rotl64(acc, 31);
612 acc *= PRIME64_1;
613 return acc;
614}
615
616static U64 XXH64_mergeRound(U64 acc, U64 val)
617{
618 val = XXH64_round(0, val);
619 acc ^= val;
620 acc = acc * PRIME64_1 + PRIME64_4;
621 return acc;
622}
623
624FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
625{
626 const BYTE* p = (const BYTE*)input;
627 const BYTE* bEnd = p + len;
628 U64 h64;
629#define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
630
631#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
632 if (p==NULL) {
633 len=0;
634 bEnd=p=(const BYTE*)(size_t)32;
635 }
636#endif
637
638 if (len>=32) {
639 const BYTE* const limit = bEnd - 32;
640 U64 v1 = seed + PRIME64_1 + PRIME64_2;
641 U64 v2 = seed + PRIME64_2;
642 U64 v3 = seed + 0;
643 U64 v4 = seed - PRIME64_1;
644
645 do {
646 v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8;
647 v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8;
648 v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8;
649 v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8;
650 } while (p<=limit);
651
652 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
653 h64 = XXH64_mergeRound(h64, v1);
654 h64 = XXH64_mergeRound(h64, v2);
655 h64 = XXH64_mergeRound(h64, v3);
656 h64 = XXH64_mergeRound(h64, v4);
657
658 } else {
659 h64 = seed + PRIME64_5;
660 }
661
662 h64 += (U64) len;
663
664 while (p+8<=bEnd) {
665 U64 const k1 = XXH64_round(0, XXH_get64bits(p));
666 h64 ^= k1;
667 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
668 p+=8;
669 }
670
671 if (p+4<=bEnd) {
672 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
673 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
674 p+=4;
675 }
676
677 while (p<bEnd) {
678 h64 ^= (*p) * PRIME64_5;
679 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
680 p++;
681 }
682
683 h64 ^= h64 >> 33;
684 h64 *= PRIME64_2;
685 h64 ^= h64 >> 29;
686 h64 *= PRIME64_3;
687 h64 ^= h64 >> 32;
688
689 return h64;
690}
691
692
693XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed)
694{
695#if 0
696 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
697 XXH64_state_t state;
698 XXH64_reset(&state, seed);
699 XXH64_update(&state, input, len);
700 return XXH64_digest(&state);
701#else
702 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
703
704 if (XXH_FORCE_ALIGN_CHECK) {
705 if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
706 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
707 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
708 else
709 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
710 } }
711
712 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
713 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
714 else
715 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
716#endif
717}
718
719/*====== Hash Streaming ======*/
720
721XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void)
722{
723 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
724}
725XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
726{
727 XXH_free(statePtr);
728 return XXH_OK;
729}
730
731XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState)
732{
733 memcpy(dstState, srcState, sizeof(*dstState));
734}
735
736XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed)
737{
738 XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
739 memset(&state, 0, sizeof(state)-8); /* do not write into reserved, for future removal */
740 state.v1 = seed + PRIME64_1 + PRIME64_2;
741 state.v2 = seed + PRIME64_2;
742 state.v3 = seed + 0;
743 state.v4 = seed - PRIME64_1;
744 memcpy(statePtr, &state, sizeof(state));
745 return XXH_OK;
746}
747
748FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian)
749{
750 const BYTE* p = (const BYTE*)input;
751 const BYTE* const bEnd = p + len;
752
753#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
754 if (input==NULL) return XXH_ERROR;
755#endif
756
757 state->total_len += len;
758
759 if (state->memsize + len < 32) { /* fill in tmp buffer */
760 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
761 state->memsize += (U32)len;
762 return XXH_OK;
763 }
764
765 if (state->memsize) { /* tmp buffer is full */
766 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
767 state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0, endian));
768 state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1, endian));
769 state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2, endian));
770 state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3, endian));
771 p += 32-state->memsize;
772 state->memsize = 0;
773 }
774
775 if (p+32 <= bEnd) {
776 const BYTE* const limit = bEnd - 32;
777 U64 v1 = state->v1;
778 U64 v2 = state->v2;
779 U64 v3 = state->v3;
780 U64 v4 = state->v4;
781
782 do {
783 v1 = XXH64_round(v1, XXH_readLE64(p, endian)); p+=8;
784 v2 = XXH64_round(v2, XXH_readLE64(p, endian)); p+=8;
785 v3 = XXH64_round(v3, XXH_readLE64(p, endian)); p+=8;
786 v4 = XXH64_round(v4, XXH_readLE64(p, endian)); p+=8;
787 } while (p<=limit);
788
789 state->v1 = v1;
790 state->v2 = v2;
791 state->v3 = v3;
792 state->v4 = v4;
793 }
794
795 if (p < bEnd) {
796 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p));
797 state->memsize = (unsigned)(bEnd-p);
798 }
799
800 return XXH_OK;
801}
802
803XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
804{
805 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
806
807 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
808 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
809 else
810 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
811}
812
813FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian)
814{
815 const BYTE * p = (const BYTE*)state->mem64;
816 const BYTE* const bEnd = (const BYTE*)state->mem64 + state->memsize;
817 U64 h64;
818
819 if (state->total_len >= 32) {
820 U64 const v1 = state->v1;
821 U64 const v2 = state->v2;
822 U64 const v3 = state->v3;
823 U64 const v4 = state->v4;
824
825 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
826 h64 = XXH64_mergeRound(h64, v1);
827 h64 = XXH64_mergeRound(h64, v2);
828 h64 = XXH64_mergeRound(h64, v3);
829 h64 = XXH64_mergeRound(h64, v4);
830 } else {
831 h64 = state->v3 + PRIME64_5;
832 }
833
834 h64 += (U64) state->total_len;
835
836 while (p+8<=bEnd) {
837 U64 const k1 = XXH64_round(0, XXH_readLE64(p, endian));
838 h64 ^= k1;
839 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
840 p+=8;
841 }
842
843 if (p+4<=bEnd) {
844 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
845 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
846 p+=4;
847 }
848
849 while (p<bEnd) {
850 h64 ^= (*p) * PRIME64_5;
851 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
852 p++;
853 }
854
855 h64 ^= h64 >> 33;
856 h64 *= PRIME64_2;
857 h64 ^= h64 >> 29;
858 h64 *= PRIME64_3;
859 h64 ^= h64 >> 32;
860
861 return h64;
862}
863
864XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in)
865{
866 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
867
868 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
869 return XXH64_digest_endian(state_in, XXH_littleEndian);
870 else
871 return XXH64_digest_endian(state_in, XXH_bigEndian);
872}
873
874
875/*====== Canonical representation ======*/
876
877XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash)
878{
879 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t));
880 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash);
881 memcpy(dst, &hash, sizeof(*dst));
882}
883
884XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src)
885{
886 return XXH_readBE64(src);
887}
888
889#endif /* XXH_NO_LONG_LONG */
890