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