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