1 /*
2 xxHash - Fast Hash algorithm
3 Copyright (C) 2012-2015, 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 source repository : http://code.google.com/p/xxhash/
32 - xxHash source mirror : https://github.com/Cyan4973/xxHash
33 - public discussion board : https://groups.google.com/forum/#!forum/lz4c
34 */
35
36
37 /**************************************
38 * Tuning parameters
39 ***************************************/
40 /* Unaligned memory access is automatically enabled for "common" CPU, such as x86.
41 * For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
42 * If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
43 * You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
44 */
45 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
46 # define XXH_USE_UNALIGNED_ACCESS 1
47 #endif
48
49 /* XXH_ACCEPT_NULL_INPUT_POINTER :
50 * If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
51 * When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
52 * By default, this option is disabled. To enable it, uncomment below define :
53 */
54 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */
55
56 /* XXH_FORCE_NATIVE_FORMAT :
57 * By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
58 * Results are therefore identical for little-endian and big-endian CPU.
59 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
60 * Should endian-independance be of no importance for your application, you may set the #define below to 1.
61 * It will improve speed for Big-endian CPU.
62 * This option has no impact on Little_Endian CPU.
63 */
64 #define XXH_FORCE_NATIVE_FORMAT 0
65
66
67 /**************************************
68 * Compiler Specific Options
69 ***************************************/
70 #ifdef _MSC_VER /* Visual Studio */
71 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
72 # define FORCE_INLINE static __forceinline
73 #else
74 # if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
75 # ifdef __GNUC__
76 # define FORCE_INLINE static inline __attribute__((always_inline))
77 # else
78 # define FORCE_INLINE static inline
79 # endif
80 # else
81 # define FORCE_INLINE static
82 # endif /* __STDC_VERSION__ */
83 #endif
84
85
86 /**************************************
87 * Includes & Memory related functions
88 ***************************************/
89 #include "xxhash.h"
90 /* Modify the local functions below should you wish to use some other memory routines */
91 /* for malloc(), free() */
92 #include <stdlib.h>
XXH_malloc(size_t s)93 static void* XXH_malloc(size_t s) { return malloc(s); }
XXH_free(void * p)94 static void XXH_free (void* p) { free(p); }
95 /* for memcpy() */
96 #include <string.h>
XXH_memcpy(void * dest,const void * src,size_t size)97 static void* XXH_memcpy(void* dest, const void* src, size_t size)
98 {
99 return memcpy(dest,src,size);
100 }
101
102
103 /**************************************
104 * Basic Types
105 ***************************************/
106 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
107 # include <stdint.h>
108 typedef uint8_t BYTE;
109 typedef uint16_t U16;
110 typedef uint32_t U32;
111 typedef int32_t S32;
112 typedef uint64_t U64;
113 #else
114 typedef unsigned char BYTE;
115 typedef unsigned short U16;
116 typedef unsigned int U32;
117 typedef signed int S32;
118 typedef unsigned long long U64;
119 #endif
120
121 #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
122 # define _PACKED __attribute__ ((packed))
123 #else
124 # define _PACKED
125 #endif
126
127 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
128 # ifdef __IBMC__
129 # pragma pack(1)
130 # else
131 # pragma pack(push, 1)
132 # endif
133 #endif
134
135 typedef struct _U32_S
136 {
137 U32 v;
138 } _PACKED U32_S;
139 typedef struct _U64_S
140 {
141 U64 v;
142 } _PACKED U64_S;
143
144 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
145 # pragma pack(pop)
146 #endif
147
148 #define A32(x) (((U32_S *)(x))->v)
149 #define A64(x) (((U64_S *)(x))->v)
150
151
152 /*****************************************
153 * Compiler-specific Functions and Macros
154 ******************************************/
155 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
156
157 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
158 #if defined(_MSC_VER)
159 # define XXH_rotl32(x,r) _rotl(x,r)
160 # define XXH_rotl64(x,r) _rotl64(x,r)
161 #else
162 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
163 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
164 #endif
165
166 #if defined(_MSC_VER) /* Visual Studio */
167 # define XXH_swap32 _byteswap_ulong
168 # define XXH_swap64 _byteswap_uint64
169 #elif GCC_VERSION >= 403
170 # define XXH_swap32 __builtin_bswap32
171 # define XXH_swap64 __builtin_bswap64
172 #else
XXH_swap32(U32 x)173 static U32 XXH_swap32 (U32 x)
174 {
175 return ((x << 24) & 0xff000000 ) |
176 ((x << 8) & 0x00ff0000 ) |
177 ((x >> 8) & 0x0000ff00 ) |
178 ((x >> 24) & 0x000000ff );
179 }
XXH_swap64(U64 x)180 static U64 XXH_swap64 (U64 x)
181 {
182 return ((x << 56) & 0xff00000000000000ULL) |
183 ((x << 40) & 0x00ff000000000000ULL) |
184 ((x << 24) & 0x0000ff0000000000ULL) |
185 ((x << 8) & 0x000000ff00000000ULL) |
186 ((x >> 8) & 0x00000000ff000000ULL) |
187 ((x >> 24) & 0x0000000000ff0000ULL) |
188 ((x >> 40) & 0x000000000000ff00ULL) |
189 ((x >> 56) & 0x00000000000000ffULL);
190 }
191 #endif
192
193
194 /**************************************
195 * Constants
196 ***************************************/
197 #define PRIME32_1 2654435761U
198 #define PRIME32_2 2246822519U
199 #define PRIME32_3 3266489917U
200 #define PRIME32_4 668265263U
201 #define PRIME32_5 374761393U
202
203 #define PRIME64_1 11400714785074694791ULL
204 #define PRIME64_2 14029467366897019727ULL
205 #define PRIME64_3 1609587929392839161ULL
206 #define PRIME64_4 9650029242287828579ULL
207 #define PRIME64_5 2870177450012600261ULL
208
209
210 /***************************************
211 * Architecture Macros
212 ****************************************/
213 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
214 #ifndef XXH_CPU_LITTLE_ENDIAN /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example using a compiler switch */
215 static const int one = 1;
216 # define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one))
217 #endif
218
219
220 /**************************************
221 * Macros
222 ***************************************/
223 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */
224
225
226 /****************************
227 * Memory reads
228 *****************************/
229 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
230
XXH_readLE32_align(const void * ptr,XXH_endianess endian,XXH_alignment align)231 FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
232 {
233 if (align==XXH_unaligned)
234 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
235 else
236 return endian==XXH_littleEndian ? *(U32*)ptr : XXH_swap32(*(U32*)ptr);
237 }
238
XXH_readLE32(const void * ptr,XXH_endianess endian)239 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
240 {
241 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
242 }
243
XXH_readLE64_align(const void * ptr,XXH_endianess endian,XXH_alignment align)244 FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
245 {
246 if (align==XXH_unaligned)
247 return endian==XXH_littleEndian ? A64(ptr) : XXH_swap64(A64(ptr));
248 else
249 return endian==XXH_littleEndian ? *(U64*)ptr : XXH_swap64(*(U64*)ptr);
250 }
251
XXH_readLE64(const void * ptr,XXH_endianess endian)252 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
253 {
254 return XXH_readLE64_align(ptr, endian, XXH_unaligned);
255 }
256
257
258 /****************************
259 * Simple Hash Functions
260 *****************************/
XXH32_endian_align(const void * input,size_t len,U32 seed,XXH_endianess endian,XXH_alignment align)261 FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
262 {
263 const BYTE* p = (const BYTE*)input;
264 const BYTE* bEnd = p + len;
265 U32 h32;
266 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
267
268 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
269 if (p==NULL)
270 {
271 len=0;
272 bEnd=p=(const BYTE*)(size_t)16;
273 }
274 #endif
275
276 if (len>=16)
277 {
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 {
286 v1 += XXH_get32bits(p) * PRIME32_2;
287 v1 = XXH_rotl32(v1, 13);
288 v1 *= PRIME32_1;
289 p+=4;
290 v2 += XXH_get32bits(p) * PRIME32_2;
291 v2 = XXH_rotl32(v2, 13);
292 v2 *= PRIME32_1;
293 p+=4;
294 v3 += XXH_get32bits(p) * PRIME32_2;
295 v3 = XXH_rotl32(v3, 13);
296 v3 *= PRIME32_1;
297 p+=4;
298 v4 += XXH_get32bits(p) * PRIME32_2;
299 v4 = XXH_rotl32(v4, 13);
300 v4 *= PRIME32_1;
301 p+=4;
302 }
303 while (p<=limit);
304
305 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
306 }
307 else
308 {
309 h32 = seed + PRIME32_5;
310 }
311
312 h32 += (U32) len;
313
314 while (p+4<=bEnd)
315 {
316 h32 += XXH_get32bits(p) * PRIME32_3;
317 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
318 p+=4;
319 }
320
321 while (p<bEnd)
322 {
323 h32 += (*p) * PRIME32_5;
324 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
325 p++;
326 }
327
328 h32 ^= h32 >> 15;
329 h32 *= PRIME32_2;
330 h32 ^= h32 >> 13;
331 h32 *= PRIME32_3;
332 h32 ^= h32 >> 16;
333
334 return h32;
335 }
336
337
XXH32(const void * input,size_t len,unsigned seed)338 unsigned int XXH32 (const void* input, size_t len, unsigned seed)
339 {
340 #if 0
341 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
342 XXH32_state_t state;
343 XXH32_reset(&state, seed);
344 XXH32_update(&state, input, len);
345 return XXH32_digest(&state);
346 #else
347 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
348
349 # if !defined(XXH_USE_UNALIGNED_ACCESS)
350 if ((((size_t)input) & 3) == 0) /* Input is aligned, let's leverage the speed advantage */
351 {
352 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
353 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
354 else
355 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
356 }
357 # endif
358
359 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
360 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
361 else
362 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
363 #endif
364 }
365
XXH64_endian_align(const void * input,size_t len,U64 seed,XXH_endianess endian,XXH_alignment align)366 FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
367 {
368 const BYTE* p = (const BYTE*)input;
369 const BYTE* bEnd = p + len;
370 U64 h64;
371 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
372
373 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
374 if (p==NULL)
375 {
376 len=0;
377 bEnd=p=(const BYTE*)(size_t)32;
378 }
379 #endif
380
381 if (len>=32)
382 {
383 const BYTE* const limit = bEnd - 32;
384 U64 v1 = seed + PRIME64_1 + PRIME64_2;
385 U64 v2 = seed + PRIME64_2;
386 U64 v3 = seed + 0;
387 U64 v4 = seed - PRIME64_1;
388
389 do
390 {
391 v1 += XXH_get64bits(p) * PRIME64_2;
392 p+=8;
393 v1 = XXH_rotl64(v1, 31);
394 v1 *= PRIME64_1;
395 v2 += XXH_get64bits(p) * PRIME64_2;
396 p+=8;
397 v2 = XXH_rotl64(v2, 31);
398 v2 *= PRIME64_1;
399 v3 += XXH_get64bits(p) * PRIME64_2;
400 p+=8;
401 v3 = XXH_rotl64(v3, 31);
402 v3 *= PRIME64_1;
403 v4 += XXH_get64bits(p) * PRIME64_2;
404 p+=8;
405 v4 = XXH_rotl64(v4, 31);
406 v4 *= PRIME64_1;
407 }
408 while (p<=limit);
409
410 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
411
412 v1 *= PRIME64_2;
413 v1 = XXH_rotl64(v1, 31);
414 v1 *= PRIME64_1;
415 h64 ^= v1;
416 h64 = h64 * PRIME64_1 + PRIME64_4;
417
418 v2 *= PRIME64_2;
419 v2 = XXH_rotl64(v2, 31);
420 v2 *= PRIME64_1;
421 h64 ^= v2;
422 h64 = h64 * PRIME64_1 + PRIME64_4;
423
424 v3 *= PRIME64_2;
425 v3 = XXH_rotl64(v3, 31);
426 v3 *= PRIME64_1;
427 h64 ^= v3;
428 h64 = h64 * PRIME64_1 + PRIME64_4;
429
430 v4 *= PRIME64_2;
431 v4 = XXH_rotl64(v4, 31);
432 v4 *= PRIME64_1;
433 h64 ^= v4;
434 h64 = h64 * PRIME64_1 + PRIME64_4;
435 }
436 else
437 {
438 h64 = seed + PRIME64_5;
439 }
440
441 h64 += (U64) len;
442
443 while (p+8<=bEnd)
444 {
445 U64 k1 = XXH_get64bits(p);
446 k1 *= PRIME64_2;
447 k1 = XXH_rotl64(k1,31);
448 k1 *= PRIME64_1;
449 h64 ^= k1;
450 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
451 p+=8;
452 }
453
454 if (p+4<=bEnd)
455 {
456 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
457 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
458 p+=4;
459 }
460
461 while (p<bEnd)
462 {
463 h64 ^= (*p) * PRIME64_5;
464 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
465 p++;
466 }
467
468 h64 ^= h64 >> 33;
469 h64 *= PRIME64_2;
470 h64 ^= h64 >> 29;
471 h64 *= PRIME64_3;
472 h64 ^= h64 >> 32;
473
474 return h64;
475 }
476
477
XXH64(const void * input,size_t len,unsigned long long seed)478 unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed)
479 {
480 #if 0
481 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
482 XXH64_state_t state;
483 XXH64_reset(&state, seed);
484 XXH64_update(&state, input, len);
485 return XXH64_digest(&state);
486 #else
487 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
488
489 # if !defined(XXH_USE_UNALIGNED_ACCESS)
490 if ((((size_t)input) & 7)==0) /* Input is aligned, let's leverage the speed advantage */
491 {
492 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
493 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
494 else
495 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
496 }
497 # endif
498
499 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
500 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
501 else
502 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
503 #endif
504 }
505
506 /****************************************************
507 * Advanced Hash Functions
508 ****************************************************/
509
510 /*** Allocation ***/
511 typedef struct
512 {
513 U64 total_len;
514 U32 seed;
515 U32 v1;
516 U32 v2;
517 U32 v3;
518 U32 v4;
519 U32 mem32[4]; /* defined as U32 for alignment */
520 U32 memsize;
521 } XXH_istate32_t;
522
523 typedef struct
524 {
525 U64 total_len;
526 U64 seed;
527 U64 v1;
528 U64 v2;
529 U64 v3;
530 U64 v4;
531 U64 mem64[4]; /* defined as U64 for alignment */
532 U32 memsize;
533 } XXH_istate64_t;
534
535
XXH32_createState(void)536 XXH32_state_t* XXH32_createState(void)
537 {
538 XXH_STATIC_ASSERT(sizeof(XXH32_state_t) >= sizeof(XXH_istate32_t)); /* A compilation error here means XXH32_state_t is not large enough */
539 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
540 }
XXH32_freeState(XXH32_state_t * statePtr)541 XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
542 {
543 XXH_free(statePtr);
544 return XXH_OK;
545 }
546
XXH64_createState(void)547 XXH64_state_t* XXH64_createState(void)
548 {
549 XXH_STATIC_ASSERT(sizeof(XXH64_state_t) >= sizeof(XXH_istate64_t)); /* A compilation error here means XXH64_state_t is not large enough */
550 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
551 }
XXH64_freeState(XXH64_state_t * statePtr)552 XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
553 {
554 XXH_free(statePtr);
555 return XXH_OK;
556 }
557
558
559 /*** Hash feed ***/
560
XXH32_reset(XXH32_state_t * state_in,U32 seed)561 XXH_errorcode XXH32_reset(XXH32_state_t* state_in, U32 seed)
562 {
563 XXH_istate32_t* state = (XXH_istate32_t*) state_in;
564 state->seed = seed;
565 state->v1 = seed + PRIME32_1 + PRIME32_2;
566 state->v2 = seed + PRIME32_2;
567 state->v3 = seed + 0;
568 state->v4 = seed - PRIME32_1;
569 state->total_len = 0;
570 state->memsize = 0;
571 return XXH_OK;
572 }
573
XXH64_reset(XXH64_state_t * state_in,unsigned long long seed)574 XXH_errorcode XXH64_reset(XXH64_state_t* state_in, unsigned long long seed)
575 {
576 XXH_istate64_t* state = (XXH_istate64_t*) state_in;
577 state->seed = seed;
578 state->v1 = seed + PRIME64_1 + PRIME64_2;
579 state->v2 = seed + PRIME64_2;
580 state->v3 = seed + 0;
581 state->v4 = seed - PRIME64_1;
582 state->total_len = 0;
583 state->memsize = 0;
584 return XXH_OK;
585 }
586
587
XXH32_update_endian(XXH32_state_t * state_in,const void * input,size_t len,XXH_endianess endian)588 FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
589 {
590 XXH_istate32_t* state = (XXH_istate32_t *) state_in;
591 const BYTE* p = (const BYTE*)input;
592 const BYTE* const bEnd = p + len;
593
594 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
595 if (input==NULL) return XXH_ERROR;
596 #endif
597
598 state->total_len += len;
599
600 if (state->memsize + len < 16) /* fill in tmp buffer */
601 {
602 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
603 state->memsize += (U32)len;
604 return XXH_OK;
605 }
606
607 if (state->memsize) /* some data left from previous update */
608 {
609 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
610 {
611 const U32* p32 = state->mem32;
612 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2;
613 state->v1 = XXH_rotl32(state->v1, 13);
614 state->v1 *= PRIME32_1;
615 p32++;
616 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2;
617 state->v2 = XXH_rotl32(state->v2, 13);
618 state->v2 *= PRIME32_1;
619 p32++;
620 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2;
621 state->v3 = XXH_rotl32(state->v3, 13);
622 state->v3 *= PRIME32_1;
623 p32++;
624 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2;
625 state->v4 = XXH_rotl32(state->v4, 13);
626 state->v4 *= PRIME32_1;
627 p32++;
628 }
629 p += 16-state->memsize;
630 state->memsize = 0;
631 }
632
633 if (p <= bEnd-16)
634 {
635 const BYTE* const limit = bEnd - 16;
636 U32 v1 = state->v1;
637 U32 v2 = state->v2;
638 U32 v3 = state->v3;
639 U32 v4 = state->v4;
640
641 do
642 {
643 v1 += XXH_readLE32(p, endian) * PRIME32_2;
644 v1 = XXH_rotl32(v1, 13);
645 v1 *= PRIME32_1;
646 p+=4;
647 v2 += XXH_readLE32(p, endian) * PRIME32_2;
648 v2 = XXH_rotl32(v2, 13);
649 v2 *= PRIME32_1;
650 p+=4;
651 v3 += XXH_readLE32(p, endian) * PRIME32_2;
652 v3 = XXH_rotl32(v3, 13);
653 v3 *= PRIME32_1;
654 p+=4;
655 v4 += XXH_readLE32(p, endian) * PRIME32_2;
656 v4 = XXH_rotl32(v4, 13);
657 v4 *= PRIME32_1;
658 p+=4;
659 }
660 while (p<=limit);
661
662 state->v1 = v1;
663 state->v2 = v2;
664 state->v3 = v3;
665 state->v4 = v4;
666 }
667
668 if (p < bEnd)
669 {
670 XXH_memcpy(state->mem32, p, bEnd-p);
671 state->memsize = (int)(bEnd-p);
672 }
673
674 return XXH_OK;
675 }
676
XXH32_update(XXH32_state_t * state_in,const void * input,size_t len)677 XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
678 {
679 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
680
681 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
682 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
683 else
684 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
685 }
686
687
688
XXH32_digest_endian(const XXH32_state_t * state_in,XXH_endianess endian)689 FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state_in, XXH_endianess endian)
690 {
691 XXH_istate32_t* state = (XXH_istate32_t*) state_in;
692 const BYTE * p = (const BYTE*)state->mem32;
693 BYTE* bEnd = (BYTE*)(state->mem32) + state->memsize;
694 U32 h32;
695
696 if (state->total_len >= 16)
697 {
698 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
699 }
700 else
701 {
702 h32 = state->seed + PRIME32_5;
703 }
704
705 h32 += (U32) state->total_len;
706
707 while (p+4<=bEnd)
708 {
709 h32 += XXH_readLE32(p, endian) * PRIME32_3;
710 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
711 p+=4;
712 }
713
714 while (p<bEnd)
715 {
716 h32 += (*p) * PRIME32_5;
717 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
718 p++;
719 }
720
721 h32 ^= h32 >> 15;
722 h32 *= PRIME32_2;
723 h32 ^= h32 >> 13;
724 h32 *= PRIME32_3;
725 h32 ^= h32 >> 16;
726
727 return h32;
728 }
729
730
XXH32_digest(const XXH32_state_t * state_in)731 U32 XXH32_digest (const XXH32_state_t* state_in)
732 {
733 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
734
735 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
736 return XXH32_digest_endian(state_in, XXH_littleEndian);
737 else
738 return XXH32_digest_endian(state_in, XXH_bigEndian);
739 }
740
741
XXH64_update_endian(XXH64_state_t * state_in,const void * input,size_t len,XXH_endianess endian)742 FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
743 {
744 XXH_istate64_t * state = (XXH_istate64_t *) state_in;
745 const BYTE* p = (const BYTE*)input;
746 const BYTE* const bEnd = p + len;
747
748 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
749 if (input==NULL) return XXH_ERROR;
750 #endif
751
752 state->total_len += len;
753
754 if (state->memsize + len < 32) /* fill in tmp buffer */
755 {
756 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
757 state->memsize += (U32)len;
758 return XXH_OK;
759 }
760
761 if (state->memsize) /* some data left from previous update */
762 {
763 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
764 {
765 const U64* p64 = state->mem64;
766 state->v1 += XXH_readLE64(p64, endian) * PRIME64_2;
767 state->v1 = XXH_rotl64(state->v1, 31);
768 state->v1 *= PRIME64_1;
769 p64++;
770 state->v2 += XXH_readLE64(p64, endian) * PRIME64_2;
771 state->v2 = XXH_rotl64(state->v2, 31);
772 state->v2 *= PRIME64_1;
773 p64++;
774 state->v3 += XXH_readLE64(p64, endian) * PRIME64_2;
775 state->v3 = XXH_rotl64(state->v3, 31);
776 state->v3 *= PRIME64_1;
777 p64++;
778 state->v4 += XXH_readLE64(p64, endian) * PRIME64_2;
779 state->v4 = XXH_rotl64(state->v4, 31);
780 state->v4 *= PRIME64_1;
781 p64++;
782 }
783 p += 32-state->memsize;
784 state->memsize = 0;
785 }
786
787 if (p+32 <= bEnd)
788 {
789 const BYTE* const limit = bEnd - 32;
790 U64 v1 = state->v1;
791 U64 v2 = state->v2;
792 U64 v3 = state->v3;
793 U64 v4 = state->v4;
794
795 do
796 {
797 v1 += XXH_readLE64(p, endian) * PRIME64_2;
798 v1 = XXH_rotl64(v1, 31);
799 v1 *= PRIME64_1;
800 p+=8;
801 v2 += XXH_readLE64(p, endian) * PRIME64_2;
802 v2 = XXH_rotl64(v2, 31);
803 v2 *= PRIME64_1;
804 p+=8;
805 v3 += XXH_readLE64(p, endian) * PRIME64_2;
806 v3 = XXH_rotl64(v3, 31);
807 v3 *= PRIME64_1;
808 p+=8;
809 v4 += XXH_readLE64(p, endian) * PRIME64_2;
810 v4 = XXH_rotl64(v4, 31);
811 v4 *= PRIME64_1;
812 p+=8;
813 }
814 while (p<=limit);
815
816 state->v1 = v1;
817 state->v2 = v2;
818 state->v3 = v3;
819 state->v4 = v4;
820 }
821
822 if (p < bEnd)
823 {
824 XXH_memcpy(state->mem64, p, bEnd-p);
825 state->memsize = (int)(bEnd-p);
826 }
827
828 return XXH_OK;
829 }
830
XXH64_update(XXH64_state_t * state_in,const void * input,size_t len)831 XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
832 {
833 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
834
835 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
836 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
837 else
838 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
839 }
840
841
842
XXH64_digest_endian(const XXH64_state_t * state_in,XXH_endianess endian)843 FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state_in, XXH_endianess endian)
844 {
845 XXH_istate64_t * state = (XXH_istate64_t *) state_in;
846 const BYTE * p = (const BYTE*)state->mem64;
847 BYTE* bEnd = (BYTE*)state->mem64 + state->memsize;
848 U64 h64;
849
850 if (state->total_len >= 32)
851 {
852 U64 v1 = state->v1;
853 U64 v2 = state->v2;
854 U64 v3 = state->v3;
855 U64 v4 = state->v4;
856
857 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
858
859 v1 *= PRIME64_2;
860 v1 = XXH_rotl64(v1, 31);
861 v1 *= PRIME64_1;
862 h64 ^= v1;
863 h64 = h64*PRIME64_1 + PRIME64_4;
864
865 v2 *= PRIME64_2;
866 v2 = XXH_rotl64(v2, 31);
867 v2 *= PRIME64_1;
868 h64 ^= v2;
869 h64 = h64*PRIME64_1 + PRIME64_4;
870
871 v3 *= PRIME64_2;
872 v3 = XXH_rotl64(v3, 31);
873 v3 *= PRIME64_1;
874 h64 ^= v3;
875 h64 = h64*PRIME64_1 + PRIME64_4;
876
877 v4 *= PRIME64_2;
878 v4 = XXH_rotl64(v4, 31);
879 v4 *= PRIME64_1;
880 h64 ^= v4;
881 h64 = h64*PRIME64_1 + PRIME64_4;
882 }
883 else
884 {
885 h64 = state->seed + PRIME64_5;
886 }
887
888 h64 += (U64) state->total_len;
889
890 while (p+8<=bEnd)
891 {
892 U64 k1 = XXH_readLE64(p, endian);
893 k1 *= PRIME64_2;
894 k1 = XXH_rotl64(k1,31);
895 k1 *= PRIME64_1;
896 h64 ^= k1;
897 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
898 p+=8;
899 }
900
901 if (p+4<=bEnd)
902 {
903 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
904 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
905 p+=4;
906 }
907
908 while (p<bEnd)
909 {
910 h64 ^= (*p) * PRIME64_5;
911 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
912 p++;
913 }
914
915 h64 ^= h64 >> 33;
916 h64 *= PRIME64_2;
917 h64 ^= h64 >> 29;
918 h64 *= PRIME64_3;
919 h64 ^= h64 >> 32;
920
921 return h64;
922 }
923
924
XXH64_digest(const XXH64_state_t * state_in)925 unsigned long long XXH64_digest (const XXH64_state_t* state_in)
926 {
927 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
928
929 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
930 return XXH64_digest_endian(state_in, XXH_littleEndian);
931 else
932 return XXH64_digest_endian(state_in, XXH_bigEndian);
933 }
934
935
936