Debian Codegraph @

vendor/ls-qpack/deps/xxhash/xxhash.c

raw
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>
87 static void *XXH_malloc(size_t s) { return malloc(s); }
88 static void XXH_free(void *p) { free(p); }
89 // for memcpy()
90 #include <string.h>
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 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
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
164 # define XXH_swap32 __builtin_bswap32
165 # define XXH_swap64 __builtin_bswap64
166 #else
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 }
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
224 FORCE_INLINE U32 XXH_readLE32_align(const void *ptr, XXH_endianess endian,
225 XXH_alignment align)
226 {
227 if (align == XXH_unaligned)
228 return endian == XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
229 else
230 return endian == XXH_littleEndian ? *(U32 *)ptr : XXH_swap32(*(U32 *)ptr);
231 }
232
233 FORCE_INLINE U32 XXH_readLE32(const void *ptr, XXH_endianess endian)
234 {
235 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
236 }
237
238 FORCE_INLINE U64 XXH_readLE64_align(const void *ptr, XXH_endianess endian,
239 XXH_alignment align)
240 {
241 if (align == XXH_unaligned)
242 return endian == XXH_littleEndian ? A64(ptr) : XXH_swap64(A64(ptr));
243 else
244 return endian == XXH_littleEndian ? *(U64 *)ptr : XXH_swap64(*(U64 *)ptr);
245 }
246
247 FORCE_INLINE U64 XXH_readLE64(const void *ptr, XXH_endianess endian)
248 {
249 return XXH_readLE64_align(ptr, endian, XXH_unaligned);
250 }
251
252
253 //****************************
254 // Simple Hash Functions
255 //****************************
256 FORCE_INLINE U32 XXH32_endian_align(const void *input, size_t len,
257 U32 seed, XXH_endianess endian, XXH_alignment align)
258 {
259 const BYTE *p = (const BYTE *)input;
260 const BYTE *bEnd = p + len;
261 U32 h32;
262 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
263
264 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
265 if (p == NULL)
266 {
267 len = 0;
268 bEnd = p = (const BYTE *)(size_t)16;
269 }
270 #endif
271
272 if (len >= 16)
273 {
274 const BYTE *const limit = bEnd - 16;
275 U32 v1 = seed + PRIME32_1 + PRIME32_2;
276 U32 v2 = seed + PRIME32_2;
277 U32 v3 = seed + 0;
278 U32 v4 = seed - PRIME32_1;
279
280 do
281 {
282 v1 += XXH_get32bits(p) * PRIME32_2;
283 v1 = XXH_rotl32(v1, 13);
284 v1 *= PRIME32_1;
285 p += 4;
286 v2 += XXH_get32bits(p) * PRIME32_2;
287 v2 = XXH_rotl32(v2, 13);
288 v2 *= PRIME32_1;
289 p += 4;
290 v3 += XXH_get32bits(p) * PRIME32_2;
291 v3 = XXH_rotl32(v3, 13);
292 v3 *= PRIME32_1;
293 p += 4;
294 v4 += XXH_get32bits(p) * PRIME32_2;
295 v4 = XXH_rotl32(v4, 13);
296 v4 *= PRIME32_1;
297 p += 4;
298 }
299 while (p <= limit);
300
301 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3,
302 12) + XXH_rotl32(v4, 18);
303 }
304 else
305 h32 = seed + PRIME32_5;
306
307 h32 += (U32) len;
308
309 while (p + 4 <= bEnd)
310 {
311 h32 += XXH_get32bits(p) * PRIME32_3;
312 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
313 p += 4;
314 }
315
316 while (p < bEnd)
317 {
318 h32 += (*p) * PRIME32_5;
319 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
320 p++;
321 }
322
323 h32 ^= h32 >> 15;
324 h32 *= PRIME32_2;
325 h32 ^= h32 >> 13;
326 h32 *= PRIME32_3;
327 h32 ^= h32 >> 16;
328
329 return h32;
330 }
331
332
333 unsigned int XXH32(const void *input, size_t len, unsigned seed)
334 {
335 #if 0
336 // Simple version, good for code maintenance, but unfortunately slow for small inputs
337 XXH32_state_t state;
338 XXH32_reset(&state, seed);
339 XXH32_update(&state, input, len);
340 return XXH32_digest(&state);
341 #else
342 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
343
344 # if !defined(XXH_USE_UNALIGNED_ACCESS)
345 if ((((size_t)input) & 3) ==
346 0) // Input is aligned, let's leverage the speed advantage
347 {
348 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
349 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
350 else
351 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
352 }
353 # endif
354
355 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
356 return XXH32_endian_align(input, len, seed, XXH_littleEndian,
357 XXH_unaligned);
358 else
359 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
360 #endif
361 }
362
363 FORCE_INLINE U64 XXH64_endian_align(const void *input, size_t len,
364 U64 seed, XXH_endianess endian, XXH_alignment align)
365 {
366 const BYTE *p = (const BYTE *)input;
367 const BYTE *bEnd = p + len;
368 U64 h64;
369 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
370
371 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
372 if (p == NULL)
373 {
374 len = 0;
375 bEnd = p = (const BYTE *)(size_t)32;
376 }
377 #endif
378
379 if (len >= 32)
380 {
381 const BYTE *const limit = bEnd - 32;
382 U64 v1 = seed + PRIME64_1 + PRIME64_2;
383 U64 v2 = seed + PRIME64_2;
384 U64 v3 = seed + 0;
385 U64 v4 = seed - PRIME64_1;
386
387 do
388 {
389 v1 += XXH_get64bits(p) * PRIME64_2;
390 p += 8;
391 v1 = XXH_rotl64(v1, 31);
392 v1 *= PRIME64_1;
393 v2 += XXH_get64bits(p) * PRIME64_2;
394 p += 8;
395 v2 = XXH_rotl64(v2, 31);
396 v2 *= PRIME64_1;
397 v3 += XXH_get64bits(p) * PRIME64_2;
398 p += 8;
399 v3 = XXH_rotl64(v3, 31);
400 v3 *= PRIME64_1;
401 v4 += XXH_get64bits(p) * PRIME64_2;
402 p += 8;
403 v4 = XXH_rotl64(v4, 31);
404 v4 *= PRIME64_1;
405 }
406 while (p <= limit);
407
408 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3,
409 12) + XXH_rotl64(v4, 18);
410
411 v1 *= PRIME64_2;
412 v1 = XXH_rotl64(v1, 31);
413 v1 *= PRIME64_1;
414 h64 ^= v1;
415 h64 = h64 * PRIME64_1 + PRIME64_4;
416
417 v2 *= PRIME64_2;
418 v2 = XXH_rotl64(v2, 31);
419 v2 *= PRIME64_1;
420 h64 ^= v2;
421 h64 = h64 * PRIME64_1 + PRIME64_4;
422
423 v3 *= PRIME64_2;
424 v3 = XXH_rotl64(v3, 31);
425 v3 *= PRIME64_1;
426 h64 ^= v3;
427 h64 = h64 * PRIME64_1 + PRIME64_4;
428
429 v4 *= PRIME64_2;
430 v4 = XXH_rotl64(v4, 31);
431 v4 *= PRIME64_1;
432 h64 ^= v4;
433 h64 = h64 * PRIME64_1 + PRIME64_4;
434 }
435 else
436 h64 = seed + PRIME64_5;
437
438 h64 += (U64) len;
439
440 while (p + 8 <= bEnd)
441 {
442 U64 k1 = XXH_get64bits(p);
443 k1 *= PRIME64_2;
444 k1 = XXH_rotl64(k1, 31);
445 k1 *= PRIME64_1;
446 h64 ^= k1;
447 h64 = XXH_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
448 p += 8;
449 }
450
451 if (p + 4 <= bEnd)
452 {
453 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
454 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
455 p += 4;
456 }
457
458 while (p < bEnd)
459 {
460 h64 ^= (*p) * PRIME64_5;
461 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
462 p++;
463 }
464
465 h64 ^= h64 >> 33;
466 h64 *= PRIME64_2;
467 h64 ^= h64 >> 29;
468 h64 *= PRIME64_3;
469 h64 ^= h64 >> 32;
470
471 return h64;
472 }
473
474
475 unsigned long long XXH64(const void *input, size_t len,
476 unsigned long long seed)
477 {
478 #if 0
479 // Simple version, good for code maintenance, but unfortunately slow for small inputs
480 XXH64_state_t state;
481 XXH64_reset(&state, seed);
482 XXH64_update(&state, input, len);
483 return XXH64_digest(&state);
484 #else
485 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
486
487 # if !defined(XXH_USE_UNALIGNED_ACCESS)
488 if ((((size_t)input) & 7) ==
489 0) // Input is aligned, let's leverage the speed advantage
490 {
491 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
492 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
493 else
494 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
495 }
496 # endif
497
498 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
499 return XXH64_endian_align(input, len, seed, XXH_littleEndian,
500 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
536 XXH32_state_t *XXH32_createState(void)
537 {
538 XXH_STATIC_ASSERT(sizeof(XXH32_state_t) >= sizeof(
539 XXH_istate32_t)); // A compilation error here means XXH32_state_t is not large enough
540 return (XXH32_state_t *)XXH_malloc(sizeof(XXH32_state_t));
541 }
542 XXH_errorcode XXH32_freeState(XXH32_state_t *statePtr)
543 {
544 XXH_free(statePtr);
545 return XXH_OK;
546 };
547
548 XXH64_state_t *XXH64_createState(void)
549 {
550 XXH_STATIC_ASSERT(sizeof(XXH64_state_t) >= sizeof(
551 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 }
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
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
576 XXH_errorcode XXH64_reset(XXH64_state_t *state_in, unsigned long long 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
590 FORCE_INLINE XXH_errorcode XXH32_update_endian(XXH32_state_t *state_in,
591 const void *input, size_t len, XXH_endianess endian)
592 {
593 XXH_istate32_t *state = (XXH_istate32_t *) state_in;
594 const BYTE *p = (const BYTE *)input;
595 const BYTE *const bEnd = p + len;
596
597 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
598 if (input == NULL) return XXH_ERROR;
599 #endif
600
601 state->total_len += len;
602
603 if (state->memsize + len < 16) // fill in tmp buffer
604 {
605 XXH_memcpy((BYTE *)(state->mem32) + state->memsize, input, len);
606 state->memsize += (U32)len;
607 return XXH_OK;
608 }
609
610 if (state->memsize) // some data left from previous update
611 {
612 XXH_memcpy((BYTE *)(state->mem32) + state->memsize, input,
613 16 - state->memsize);
614 {
615 const U32 *p32 = state->mem32;
616 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2;
617 state->v1 = XXH_rotl32(state->v1, 13);
618 state->v1 *= PRIME32_1;
619 p32++;
620 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2;
621 state->v2 = XXH_rotl32(state->v2, 13);
622 state->v2 *= PRIME32_1;
623 p32++;
624 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2;
625 state->v3 = XXH_rotl32(state->v3, 13);
626 state->v3 *= PRIME32_1;
627 p32++;
628 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2;
629 state->v4 = XXH_rotl32(state->v4, 13);
630 state->v4 *= PRIME32_1;
631 p32++;
632 }
633 p += 16 - state->memsize;
634 state->memsize = 0;
635 }
636
637 if (p <= bEnd - 16)
638 {
639 const BYTE *const limit = bEnd - 16;
640 U32 v1 = state->v1;
641 U32 v2 = state->v2;
642 U32 v3 = state->v3;
643 U32 v4 = state->v4;
644
645 do
646 {
647 v1 += XXH_readLE32(p, endian) * PRIME32_2;
648 v1 = XXH_rotl32(v1, 13);
649 v1 *= PRIME32_1;
650 p += 4;
651 v2 += XXH_readLE32(p, endian) * PRIME32_2;
652 v2 = XXH_rotl32(v2, 13);
653 v2 *= PRIME32_1;
654 p += 4;
655 v3 += XXH_readLE32(p, endian) * PRIME32_2;
656 v3 = XXH_rotl32(v3, 13);
657 v3 *= PRIME32_1;
658 p += 4;
659 v4 += XXH_readLE32(p, endian) * PRIME32_2;
660 v4 = XXH_rotl32(v4, 13);
661 v4 *= PRIME32_1;
662 p += 4;
663 }
664 while (p <= limit);
665
666 state->v1 = v1;
667 state->v2 = v2;
668 state->v3 = v3;
669 state->v4 = v4;
670 }
671
672 if (p < bEnd)
673 {
674 XXH_memcpy(state->mem32, p, bEnd - p);
675 state->memsize = (int)(bEnd - p);
676 }
677
678 return XXH_OK;
679 }
680
681 XXH_errorcode XXH32_update(XXH32_state_t *state_in, const void *input,
682 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
694 FORCE_INLINE U32 XXH32_digest_endian(const XXH32_state_t *state_in,
695 XXH_endianess endian)
696 {
697 XXH_istate32_t *state = (XXH_istate32_t *) state_in;
698 const BYTE *p = (const BYTE *)state->mem32;
699 BYTE *bEnd = (BYTE *)(state->mem32) + state->memsize;
700 U32 h32;
701
702 if (state->total_len >= 16)
703 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2,
704 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
705 else
706 h32 = state->seed + PRIME32_5;
707
708 h32 += (U32) state->total_len;
709
710 while (p + 4 <= bEnd)
711 {
712 h32 += XXH_readLE32(p, endian) * PRIME32_3;
713 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
714 p += 4;
715 }
716
717 while (p < bEnd)
718 {
719 h32 += (*p) * PRIME32_5;
720 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
721 p++;
722 }
723
724 h32 ^= h32 >> 15;
725 h32 *= PRIME32_2;
726 h32 ^= h32 >> 13;
727 h32 *= PRIME32_3;
728 h32 ^= h32 >> 16;
729
730 return h32;
731 }
732
733
734 U32 XXH32_digest(const XXH32_state_t *state_in)
735 {
736 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
737
738 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
739 return XXH32_digest_endian(state_in, XXH_littleEndian);
740 else
741 return XXH32_digest_endian(state_in, XXH_bigEndian);
742 }
743
744
745 FORCE_INLINE XXH_errorcode XXH64_update_endian(XXH64_state_t *state_in,
746 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,
768 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
836 XXH_errorcode XXH64_update(XXH64_state_t *state_in, const void *input,
837 size_t len)
838 {
839 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
840
841 if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
842 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
843 else
844 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
845 }
846
847
848
849 FORCE_INLINE U64 XXH64_digest_endian(const XXH64_state_t *state_in,
850 XXH_endianess endian)
851 {
852 XXH_istate64_t *state = (XXH_istate64_t *) state_in;
853 const BYTE *p = (const BYTE *)state->mem64;
854 BYTE *bEnd = (BYTE *)state->mem64 + state->memsize;
855 U64 h64;
856
857 if (state->total_len >= 32)
858 {
859 U64 v1 = state->v1;
860 U64 v2 = state->v2;
861 U64 v3 = state->v3;
862 U64 v4 = state->v4;
863
864 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3,
865 12) + XXH_rotl64(v4, 18);
866
867 v1 *= PRIME64_2;
868 v1 = XXH_rotl64(v1, 31);
869 v1 *= PRIME64_1;
870 h64 ^= v1;
871 h64 = h64 * PRIME64_1 + PRIME64_4;
872
873 v2 *= PRIME64_2;
874 v2 = XXH_rotl64(v2, 31);
875 v2 *= PRIME64_1;
876 h64 ^= v2;
877 h64 = h64 * PRIME64_1 + PRIME64_4;
878
879 v3 *= PRIME64_2;
880 v3 = XXH_rotl64(v3, 31);
881 v3 *= PRIME64_1;
882 h64 ^= v3;
883 h64 = h64 * PRIME64_1 + PRIME64_4;
884
885 v4 *= PRIME64_2;
886 v4 = XXH_rotl64(v4, 31);
887 v4 *= PRIME64_1;
888 h64 ^= v4;
889 h64 = h64 * PRIME64_1 + PRIME64_4;
890 }
891 else
892 h64 = state->seed + PRIME64_5;
893
894 h64 += (U64) state->total_len;
895
896 while (p + 8 <= bEnd)
897 {
898 U64 k1 = XXH_readLE64(p, endian);
899 k1 *= PRIME64_2;
900 k1 = XXH_rotl64(k1, 31);
901 k1 *= PRIME64_1;
902 h64 ^= k1;
903 h64 = XXH_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
904 p += 8;
905 }
906
907 if (p + 4 <= bEnd)
908 {
909 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
910 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
911 p += 4;
912 }
913
914 while (p < bEnd)
915 {
916 h64 ^= (*p) * PRIME64_5;
917 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
918 p++;
919 }
920
921 h64 ^= h64 >> 33;
922 h64 *= PRIME64_2;
923 h64 ^= h64 >> 29;
924 h64 *= PRIME64_3;
925 h64 ^= h64 >> 32;
926
927 return h64;
928 }
929
930
931 unsigned long long 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