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