1/* 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 "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, 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 233FORCE_INLINE U32 XXH_readLE32(const void *ptr, XXH_endianess endian) 234{ 235 return XXH_readLE32_align(ptr, endian, XXH_unaligned); 236} 237 238FORCE_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 247FORCE_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//**************************** 256FORCE_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 333unsigned 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 363FORCE_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 475unsigned 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 ***/ 511typedef 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 523typedef 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 536XXH32_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} 542XXH_errorcode XXH32_freeState(XXH32_state_t *statePtr) 543{ 544 XXH_free(statePtr); 545 return XXH_OK; 546}; 547 548XXH64_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} 554XXH_errorcode XXH64_freeState(XXH64_state_t *statePtr) 555{ 556 XXH_free(statePtr); 557 return XXH_OK; 558}; 559 560 561/*** Hash feed ***/ 562 563XXH_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 576XXH_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 590FORCE_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 681XXH_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 694FORCE_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 734U32 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 745FORCE_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 836XXH_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 849FORCE_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 931unsigned 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 942