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