blob: 5702e64f5ca168299d6049afaa870ea8a4644343 [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).
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 <import/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>
87static void* XXH_malloc(size_t s) { return malloc(s); }
88static void XXH_free (void* p) { free(p); }
89// for memcpy()
90#include <string.h>
91static 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>
102typedef uint8_t BYTE;
103typedef uint16_t U16;
104typedef uint32_t U32;
105typedef int32_t S32;
106typedef uint64_t U64;
107#else
108typedef unsigned char BYTE;
109typedef unsigned short U16;
110typedef unsigned int U32;
111typedef signed int S32;
112typedef unsigned long long 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
129typedef struct _U32_S
130{
131 U32 v;
132} _PACKED U32_S;
133typedef 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
164# define XXH_swap32 __builtin_bswap32
165# define XXH_swap64 __builtin_bswap64
166#else
167static 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}
174static 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//**************************************
206typedef 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
208static 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//****************************
222typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
223
224FORCE_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
232FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
233{
234 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
235}
236
237FORCE_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
245FORCE_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//****************************
254FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
255{
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200256 const BYTE* p = input;
Willy Tarreaub5684e02015-04-27 11:59:40 +0200257 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
331unsigned 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
359FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
360{
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200361 const BYTE* p = input;
Willy Tarreaub5684e02015-04-27 11:59:40 +0200362 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
471unsigned long long XXH64 (const void* input, size_t len, unsigned long long 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 ***/
504typedef 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
516typedef 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
529XXH32_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}
534XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
535{
536 XXH_free(statePtr);
537 return XXH_OK;
538};
539
540XXH64_state_t* XXH64_createState(void)
541{
542 XXH_STATIC_ASSERT(sizeof(XXH64_state_t) >= sizeof(XXH_istate64_t)); // A compilation error here means XXH64_state_t is not large enough
543 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
544}
545XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
546{
547 XXH_free(statePtr);
548 return XXH_OK;
549};
550
551
552/*** Hash feed ***/
553
554XXH_errorcode XXH32_reset(XXH32_state_t* state_in, U32 seed)
555{
556 XXH_istate32_t* state = (XXH_istate32_t*) state_in;
557 state->seed = seed;
558 state->v1 = seed + PRIME32_1 + PRIME32_2;
559 state->v2 = seed + PRIME32_2;
560 state->v3 = seed + 0;
561 state->v4 = seed - PRIME32_1;
562 state->total_len = 0;
563 state->memsize = 0;
564 return XXH_OK;
565}
566
567XXH_errorcode XXH64_reset(XXH64_state_t* state_in, unsigned long long seed)
568{
569 XXH_istate64_t* state = (XXH_istate64_t*) state_in;
570 state->seed = seed;
571 state->v1 = seed + PRIME64_1 + PRIME64_2;
572 state->v2 = seed + PRIME64_2;
573 state->v3 = seed + 0;
574 state->v4 = seed - PRIME64_1;
575 state->total_len = 0;
576 state->memsize = 0;
577 return XXH_OK;
578}
579
580
581FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
582{
583 XXH_istate32_t* state = (XXH_istate32_t *) state_in;
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200584 const BYTE* p = input;
Willy Tarreaub5684e02015-04-27 11:59:40 +0200585 const BYTE* const bEnd = p + len;
586
587#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
588 if (input==NULL) return XXH_ERROR;
589#endif
590
591 state->total_len += len;
592
593 if (state->memsize + len < 16) // fill in tmp buffer
594 {
595 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
596 state->memsize += (U32)len;
597 return XXH_OK;
598 }
599
600 if (state->memsize) // some data left from previous update
601 {
602 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
603 {
604 const U32* p32 = state->mem32;
605 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2;
606 state->v1 = XXH_rotl32(state->v1, 13);
607 state->v1 *= PRIME32_1;
608 p32++;
609 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2;
610 state->v2 = XXH_rotl32(state->v2, 13);
611 state->v2 *= PRIME32_1;
612 p32++;
613 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2;
614 state->v3 = XXH_rotl32(state->v3, 13);
615 state->v3 *= PRIME32_1;
616 p32++;
617 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2;
618 state->v4 = XXH_rotl32(state->v4, 13);
619 state->v4 *= PRIME32_1;
620 p32++;
621 }
622 p += 16-state->memsize;
623 state->memsize = 0;
624 }
625
626 if (p <= bEnd-16)
627 {
628 const BYTE* const limit = bEnd - 16;
629 U32 v1 = state->v1;
630 U32 v2 = state->v2;
631 U32 v3 = state->v3;
632 U32 v4 = state->v4;
633
634 do
635 {
636 v1 += XXH_readLE32(p, endian) * PRIME32_2;
637 v1 = XXH_rotl32(v1, 13);
638 v1 *= PRIME32_1;
639 p+=4;
640 v2 += XXH_readLE32(p, endian) * PRIME32_2;
641 v2 = XXH_rotl32(v2, 13);
642 v2 *= PRIME32_1;
643 p+=4;
644 v3 += XXH_readLE32(p, endian) * PRIME32_2;
645 v3 = XXH_rotl32(v3, 13);
646 v3 *= PRIME32_1;
647 p+=4;
648 v4 += XXH_readLE32(p, endian) * PRIME32_2;
649 v4 = XXH_rotl32(v4, 13);
650 v4 *= PRIME32_1;
651 p+=4;
652 }
653 while (p<=limit);
654
655 state->v1 = v1;
656 state->v2 = v2;
657 state->v3 = v3;
658 state->v4 = v4;
659 }
660
661 if (p < bEnd)
662 {
663 XXH_memcpy(state->mem32, p, bEnd-p);
664 state->memsize = (int)(bEnd-p);
665 }
666
667 return XXH_OK;
668}
669
670XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
671{
672 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
673
674 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
675 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
676 else
677 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
678}
679
680
681
682FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state_in, XXH_endianess endian)
683{
684 XXH_istate32_t* state = (XXH_istate32_t*) state_in;
685 const BYTE * p = (const BYTE*)state->mem32;
686 BYTE* bEnd = (BYTE*)(state->mem32) + state->memsize;
687 U32 h32;
688
689 if (state->total_len >= 16)
690 {
691 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
692 }
693 else
694 {
695 h32 = state->seed + PRIME32_5;
696 }
697
698 h32 += (U32) state->total_len;
699
700 while (p+4<=bEnd)
701 {
702 h32 += XXH_readLE32(p, endian) * PRIME32_3;
703 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
704 p+=4;
705 }
706
707 while (p<bEnd)
708 {
709 h32 += (*p) * PRIME32_5;
710 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
711 p++;
712 }
713
714 h32 ^= h32 >> 15;
715 h32 *= PRIME32_2;
716 h32 ^= h32 >> 13;
717 h32 *= PRIME32_3;
718 h32 ^= h32 >> 16;
719
720 return h32;
721}
722
723
724U32 XXH32_digest (const XXH32_state_t* state_in)
725{
726 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
727
728 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
729 return XXH32_digest_endian(state_in, XXH_littleEndian);
730 else
731 return XXH32_digest_endian(state_in, XXH_bigEndian);
732}
733
734
735FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
736{
737 XXH_istate64_t * state = (XXH_istate64_t *) state_in;
Vincent Bernat3c2f2f22016-04-03 13:48:42 +0200738 const BYTE* p = input;
Willy Tarreaub5684e02015-04-27 11:59:40 +0200739 const BYTE* const bEnd = p + len;
740
741#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
742 if (input==NULL) return XXH_ERROR;
743#endif
744
745 state->total_len += len;
746
747 if (state->memsize + len < 32) // fill in tmp buffer
748 {
749 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
750 state->memsize += (U32)len;
751 return XXH_OK;
752 }
753
754 if (state->memsize) // some data left from previous update
755 {
756 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
757 {
758 const U64* p64 = state->mem64;
759 state->v1 += XXH_readLE64(p64, endian) * PRIME64_2;
760 state->v1 = XXH_rotl64(state->v1, 31);
761 state->v1 *= PRIME64_1;
762 p64++;
763 state->v2 += XXH_readLE64(p64, endian) * PRIME64_2;
764 state->v2 = XXH_rotl64(state->v2, 31);
765 state->v2 *= PRIME64_1;
766 p64++;
767 state->v3 += XXH_readLE64(p64, endian) * PRIME64_2;
768 state->v3 = XXH_rotl64(state->v3, 31);
769 state->v3 *= PRIME64_1;
770 p64++;
771 state->v4 += XXH_readLE64(p64, endian) * PRIME64_2;
772 state->v4 = XXH_rotl64(state->v4, 31);
773 state->v4 *= PRIME64_1;
774 p64++;
775 }
776 p += 32-state->memsize;
777 state->memsize = 0;
778 }
779
780 if (p+32 <= bEnd)
781 {
782 const BYTE* const limit = bEnd - 32;
783 U64 v1 = state->v1;
784 U64 v2 = state->v2;
785 U64 v3 = state->v3;
786 U64 v4 = state->v4;
787
788 do
789 {
790 v1 += XXH_readLE64(p, endian) * PRIME64_2;
791 v1 = XXH_rotl64(v1, 31);
792 v1 *= PRIME64_1;
793 p+=8;
794 v2 += XXH_readLE64(p, endian) * PRIME64_2;
795 v2 = XXH_rotl64(v2, 31);
796 v2 *= PRIME64_1;
797 p+=8;
798 v3 += XXH_readLE64(p, endian) * PRIME64_2;
799 v3 = XXH_rotl64(v3, 31);
800 v3 *= PRIME64_1;
801 p+=8;
802 v4 += XXH_readLE64(p, endian) * PRIME64_2;
803 v4 = XXH_rotl64(v4, 31);
804 v4 *= PRIME64_1;
805 p+=8;
806 }
807 while (p<=limit);
808
809 state->v1 = v1;
810 state->v2 = v2;
811 state->v3 = v3;
812 state->v4 = v4;
813 }
814
815 if (p < bEnd)
816 {
817 XXH_memcpy(state->mem64, p, bEnd-p);
818 state->memsize = (int)(bEnd-p);
819 }
820
821 return XXH_OK;
822}
823
824XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
825{
826 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
827
828 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
829 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
830 else
831 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
832}
833
834
835
836FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state_in, XXH_endianess endian)
837{
838 XXH_istate64_t * state = (XXH_istate64_t *) state_in;
839 const BYTE * p = (const BYTE*)state->mem64;
840 BYTE* bEnd = (BYTE*)state->mem64 + state->memsize;
841 U64 h64;
842
843 if (state->total_len >= 32)
844 {
845 U64 v1 = state->v1;
846 U64 v2 = state->v2;
847 U64 v3 = state->v3;
848 U64 v4 = state->v4;
849
850 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
851
852 v1 *= PRIME64_2;
853 v1 = XXH_rotl64(v1, 31);
854 v1 *= PRIME64_1;
855 h64 ^= v1;
856 h64 = h64*PRIME64_1 + PRIME64_4;
857
858 v2 *= PRIME64_2;
859 v2 = XXH_rotl64(v2, 31);
860 v2 *= PRIME64_1;
861 h64 ^= v2;
862 h64 = h64*PRIME64_1 + PRIME64_4;
863
864 v3 *= PRIME64_2;
865 v3 = XXH_rotl64(v3, 31);
866 v3 *= PRIME64_1;
867 h64 ^= v3;
868 h64 = h64*PRIME64_1 + PRIME64_4;
869
870 v4 *= PRIME64_2;
871 v4 = XXH_rotl64(v4, 31);
872 v4 *= PRIME64_1;
873 h64 ^= v4;
874 h64 = h64*PRIME64_1 + PRIME64_4;
875 }
876 else
877 {
878 h64 = state->seed + PRIME64_5;
879 }
880
881 h64 += (U64) state->total_len;
882
883 while (p+8<=bEnd)
884 {
885 U64 k1 = XXH_readLE64(p, endian);
886 k1 *= PRIME64_2;
887 k1 = XXH_rotl64(k1,31);
888 k1 *= PRIME64_1;
889 h64 ^= k1;
890 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
891 p+=8;
892 }
893
894 if (p+4<=bEnd)
895 {
896 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
897 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
898 p+=4;
899 }
900
901 while (p<bEnd)
902 {
903 h64 ^= (*p) * PRIME64_5;
904 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
905 p++;
906 }
907
908 h64 ^= h64 >> 33;
909 h64 *= PRIME64_2;
910 h64 ^= h64 >> 29;
911 h64 *= PRIME64_3;
912 h64 ^= h64 >> 32;
913
914 return h64;
915}
916
917
918unsigned long long XXH64_digest (const XXH64_state_t* state_in)
919{
920 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
921
922 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
923 return XXH64_digest_endian(state_in, XXH_littleEndian);
924 else
925 return XXH64_digest_endian(state_in, XXH_bigEndian);
926}
927
928