xxhash.c (34476B)
1 /* 2 * xxHash - Fast Hash algorithm 3 * Copyright (C) 2012-2016, Yann Collet 4 * 5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are 9 * met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above 14 * copyright notice, this list of conditions and the following disclaimer 15 * in the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * You can contact the author at : 31 * - xxHash homepage: http://www.xxhash.com 32 * - xxHash source repository : https://github.com/Cyan4973/xxHash 33 */ 34 35 36 /* ************************************* 37 * Tuning parameters 38 ***************************************/ 39 /*!XXH_FORCE_MEMORY_ACCESS : 40 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable. 41 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal. 42 * The below switch allow to select different access method for improved performance. 43 * Method 0 (default) : use `memcpy()`. Safe and portable. 44 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable). 45 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`. 46 * Method 2 : direct access. This method doesn't depend on compiler but violate C standard. 47 * It can generate buggy code on targets which do not support unaligned memory accesses. 48 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6) 49 * See http://stackoverflow.com/a/32095106/646947 for details. 50 * Prefer these methods in priority order (0 > 1 > 2) 51 */ 52 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 53 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) \ 54 || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) \ 55 || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 56 # define XXH_FORCE_MEMORY_ACCESS 2 57 # elif (defined(__INTEL_COMPILER) && !defined(_WIN32)) || \ 58 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) \ 59 || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) \ 60 || defined(__ARM_ARCH_7S__) )) 61 # define XXH_FORCE_MEMORY_ACCESS 1 62 # endif 63 #endif 64 65 /*!XXH_ACCEPT_NULL_INPUT_POINTER : 66 * If input pointer is NULL, xxHash default behavior is to dereference it, triggering a segfault. 67 * When this macro is enabled, xxHash actively checks input for null pointer. 68 * It it is, result for null input pointers is the same as a null-length input. 69 */ 70 #ifndef XXH_ACCEPT_NULL_INPUT_POINTER /* can be defined externally */ 71 # define XXH_ACCEPT_NULL_INPUT_POINTER 0 72 #endif 73 74 /*!XXH_FORCE_NATIVE_FORMAT : 75 * By default, xxHash library provides endian-independent Hash values, based on little-endian convention. 76 * Results are therefore identical for little-endian and big-endian CPU. 77 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. 78 * Should endian-independence be of no importance for your application, you may set the #define below to 1, 79 * to improve speed for Big-endian CPU. 80 * This option has no impact on Little_Endian CPU. 81 */ 82 #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */ 83 # define XXH_FORCE_NATIVE_FORMAT 0 84 #endif 85 86 /*!XXH_FORCE_ALIGN_CHECK : 87 * This is a minor performance trick, only useful with lots of very small keys. 88 * It means : check for aligned/unaligned input. 89 * The check costs one initial branch per hash; 90 * set it to 0 when the input is guaranteed to be aligned, 91 * or when alignment doesn't matter for performance. 92 */ 93 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */ 94 # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) 95 # define XXH_FORCE_ALIGN_CHECK 0 96 # else 97 # define XXH_FORCE_ALIGN_CHECK 1 98 # endif 99 #endif 100 101 102 /* ************************************* 103 * Includes & Memory related functions 104 ***************************************/ 105 /*! Modify the local functions below should you wish to use some other memory routines 106 * for malloc(), free() */ 107 /* kit local modification (diverges from pristine upstream): libkit builds 108 * -ffreestanding -nostdinc, so libc malloc/free are unavailable. These are only 109 * used by XXH32/64_createState/freeState, which the LZ4 frame codec never calls 110 * (it uses an inline XXH32_state_t + XXH32_reset). Stub them out as dead code 111 * rather than pull a libc heap into libkit. */ 112 static void* XXH_malloc(size_t s) { (void)s; return ((void*)0); } 113 static void XXH_free (void* p) { (void)p; } 114 /*! and for memcpy() */ 115 #include <string.h> 116 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); } 117 118 #include <assert.h> /* assert */ 119 120 #define XXH_STATIC_LINKING_ONLY 121 #include "xxhash.h" 122 123 124 /* ************************************* 125 * Compiler Specific Options 126 ***************************************/ 127 #if defined (_MSC_VER) && !defined (__clang__) /* MSVC */ 128 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 129 # define FORCE_INLINE static __forceinline 130 #else 131 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 132 # if defined (__GNUC__) || defined (__clang__) 133 # define FORCE_INLINE static inline __attribute__((always_inline)) 134 # else 135 # define FORCE_INLINE static inline 136 # endif 137 # else 138 # define FORCE_INLINE static 139 # endif /* __STDC_VERSION__ */ 140 #endif 141 142 143 /* ************************************* 144 * Basic Types 145 ***************************************/ 146 #ifndef MEM_MODULE 147 # if !defined (__VMS) \ 148 && (defined (__cplusplus) \ 149 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 150 # include <stdint.h> 151 typedef uint8_t BYTE; 152 typedef uint16_t U16; 153 typedef uint32_t U32; 154 # else 155 typedef unsigned char BYTE; 156 typedef unsigned short U16; 157 typedef unsigned int U32; 158 # endif 159 #endif 160 161 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) 162 163 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ 164 static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; } 165 166 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) 167 168 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 169 /* currently only defined for gcc and icc */ 170 typedef union { U32 u32; } __attribute__((packed)) unalign; 171 static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 172 173 #else 174 175 /* portable and safe solution. Generally efficient. 176 * see : http://stackoverflow.com/a/32095106/646947 177 */ 178 static U32 XXH_read32(const void* memPtr) 179 { 180 U32 val; 181 memcpy(&val, memPtr, sizeof(val)); 182 return val; 183 } 184 185 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ 186 187 188 /* **************************************** 189 * Compiler-specific Functions and Macros 190 ******************************************/ 191 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 192 193 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */ 194 #if defined(_MSC_VER) 195 # define XXH_rotl32(x,r) _rotl(x,r) 196 # define XXH_rotl64(x,r) _rotl64(x,r) 197 #else 198 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) 199 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r))) 200 #endif 201 202 #if defined(_MSC_VER) /* Visual Studio */ 203 # define XXH_swap32 _byteswap_ulong 204 #elif XXH_GCC_VERSION >= 403 205 # define XXH_swap32 __builtin_bswap32 206 #else 207 static U32 XXH_swap32 (U32 x) 208 { 209 return ((x << 24) & 0xff000000 ) | 210 ((x << 8) & 0x00ff0000 ) | 211 ((x >> 8) & 0x0000ff00 ) | 212 ((x >> 24) & 0x000000ff ); 213 } 214 #endif 215 216 217 /* ************************************* 218 * Architecture Macros 219 ***************************************/ 220 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianness; 221 222 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */ 223 #ifndef XXH_CPU_LITTLE_ENDIAN 224 static int XXH_isLittleEndian(void) 225 { 226 const union { U32 u; BYTE c[4]; } one = { 1 }; /* don't use static : performance detrimental */ 227 return one.c[0]; 228 } 229 # define XXH_CPU_LITTLE_ENDIAN XXH_isLittleEndian() 230 #endif 231 232 233 /* *************************** 234 * Memory reads 235 *****************************/ 236 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; 237 238 FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianness endian, XXH_alignment align) 239 { 240 if (align==XXH_unaligned) 241 return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr)); 242 else 243 return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr); 244 } 245 246 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianness endian) 247 { 248 return XXH_readLE32_align(ptr, endian, XXH_unaligned); 249 } 250 251 static U32 XXH_readBE32(const void* ptr) 252 { 253 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr); 254 } 255 256 257 /* ************************************* 258 * Macros 259 ***************************************/ 260 #define XXH_STATIC_ASSERT(c) { enum { XXH_sa = 1/(int)(!!(c)) }; } /* use after variable declarations */ 261 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; } 262 263 264 /* ******************************************************************* 265 * 32-bit hash functions 266 *********************************************************************/ 267 static const U32 PRIME32_1 = 2654435761U; 268 static const U32 PRIME32_2 = 2246822519U; 269 static const U32 PRIME32_3 = 3266489917U; 270 static const U32 PRIME32_4 = 668265263U; 271 static const U32 PRIME32_5 = 374761393U; 272 273 static U32 XXH32_round(U32 seed, U32 input) 274 { 275 seed += input * PRIME32_2; 276 seed = XXH_rotl32(seed, 13); 277 seed *= PRIME32_1; 278 return seed; 279 } 280 281 /* mix all bits */ 282 static U32 XXH32_avalanche(U32 h32) 283 { 284 h32 ^= h32 >> 15; 285 h32 *= PRIME32_2; 286 h32 ^= h32 >> 13; 287 h32 *= PRIME32_3; 288 h32 ^= h32 >> 16; 289 return(h32); 290 } 291 292 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align) 293 294 static U32 295 XXH32_finalize(U32 h32, const void* ptr, size_t len, 296 XXH_endianness endian, XXH_alignment align) 297 298 { 299 const BYTE* p = (const BYTE*)ptr; 300 301 #define PROCESS1 \ 302 h32 += (*p++) * PRIME32_5; \ 303 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; 304 305 #define PROCESS4 \ 306 h32 += XXH_get32bits(p) * PRIME32_3; \ 307 p+=4; \ 308 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; 309 310 switch(len&15) /* or switch(bEnd - p) */ 311 { 312 case 12: PROCESS4; 313 /* fallthrough */ 314 case 8: PROCESS4; 315 /* fallthrough */ 316 case 4: PROCESS4; 317 return XXH32_avalanche(h32); 318 319 case 13: PROCESS4; 320 /* fallthrough */ 321 case 9: PROCESS4; 322 /* fallthrough */ 323 case 5: PROCESS4; 324 PROCESS1; 325 return XXH32_avalanche(h32); 326 327 case 14: PROCESS4; 328 /* fallthrough */ 329 case 10: PROCESS4; 330 /* fallthrough */ 331 case 6: PROCESS4; 332 PROCESS1; 333 PROCESS1; 334 return XXH32_avalanche(h32); 335 336 case 15: PROCESS4; 337 /* fallthrough */ 338 case 11: PROCESS4; 339 /* fallthrough */ 340 case 7: PROCESS4; 341 /* fallthrough */ 342 case 3: PROCESS1; 343 /* fallthrough */ 344 case 2: PROCESS1; 345 /* fallthrough */ 346 case 1: PROCESS1; 347 /* fallthrough */ 348 case 0: return XXH32_avalanche(h32); 349 } 350 assert(0); 351 return h32; /* reaching this point is deemed impossible */ 352 } 353 354 355 FORCE_INLINE U32 356 XXH32_endian_align(const void* input, size_t len, U32 seed, 357 XXH_endianness endian, XXH_alignment align) 358 { 359 const BYTE* p = (const BYTE*)input; 360 const BYTE* bEnd = p + len; 361 U32 h32; 362 363 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 364 if (p==NULL) { 365 len=0; 366 bEnd=p=(const BYTE*)(size_t)16; 367 } 368 #endif 369 370 if (len>=16) { 371 const BYTE* const limit = bEnd - 15; 372 U32 v1 = seed + PRIME32_1 + PRIME32_2; 373 U32 v2 = seed + PRIME32_2; 374 U32 v3 = seed + 0; 375 U32 v4 = seed - PRIME32_1; 376 377 do { 378 v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4; 379 v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4; 380 v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4; 381 v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4; 382 } while (p < limit); 383 384 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) 385 + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); 386 } else { 387 h32 = seed + PRIME32_5; 388 } 389 390 h32 += (U32)len; 391 392 return XXH32_finalize(h32, p, len&15, endian, align); 393 } 394 395 396 XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed) 397 { 398 #if 0 399 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 400 XXH32_state_t state; 401 XXH32_reset(&state, seed); 402 XXH32_update(&state, input, len); 403 return XXH32_digest(&state); 404 #else 405 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 406 407 if (XXH_FORCE_ALIGN_CHECK) { 408 if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */ 409 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 410 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 411 else 412 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 413 } } 414 415 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 416 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); 417 else 418 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 419 #endif 420 } 421 422 423 424 /*====== Hash streaming ======*/ 425 426 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void) 427 { 428 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t)); 429 } 430 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr) 431 { 432 XXH_free(statePtr); 433 return XXH_OK; 434 } 435 436 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState) 437 { 438 memcpy(dstState, srcState, sizeof(*dstState)); 439 } 440 441 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed) 442 { 443 XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ 444 memset(&state, 0, sizeof(state)); 445 state.v1 = seed + PRIME32_1 + PRIME32_2; 446 state.v2 = seed + PRIME32_2; 447 state.v3 = seed + 0; 448 state.v4 = seed - PRIME32_1; 449 /* do not write into reserved, planned to be removed in a future version */ 450 memcpy(statePtr, &state, sizeof(state) - sizeof(state.reserved)); 451 return XXH_OK; 452 } 453 454 455 FORCE_INLINE XXH_errorcode 456 XXH32_update_endian(XXH32_state_t* state, const void* input, size_t len, XXH_endianness endian) 457 { 458 if (input==NULL) 459 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 460 return XXH_OK; 461 #else 462 return XXH_ERROR; 463 #endif 464 465 { const BYTE* p = (const BYTE*)input; 466 const BYTE* const bEnd = p + len; 467 468 state->total_len_32 += (unsigned)len; 469 state->large_len |= (len>=16) | (state->total_len_32>=16); 470 471 if (state->memsize + len < 16) { /* fill in tmp buffer */ 472 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len); 473 state->memsize += (unsigned)len; 474 return XXH_OK; 475 } 476 477 if (state->memsize) { /* some data left from previous update */ 478 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize); 479 { const U32* p32 = state->mem32; 480 state->v1 = XXH32_round(state->v1, XXH_readLE32(p32, endian)); p32++; 481 state->v2 = XXH32_round(state->v2, XXH_readLE32(p32, endian)); p32++; 482 state->v3 = XXH32_round(state->v3, XXH_readLE32(p32, endian)); p32++; 483 state->v4 = XXH32_round(state->v4, XXH_readLE32(p32, endian)); 484 } 485 p += 16-state->memsize; 486 state->memsize = 0; 487 } 488 489 if (p <= bEnd-16) { 490 const BYTE* const limit = bEnd - 16; 491 U32 v1 = state->v1; 492 U32 v2 = state->v2; 493 U32 v3 = state->v3; 494 U32 v4 = state->v4; 495 496 do { 497 v1 = XXH32_round(v1, XXH_readLE32(p, endian)); p+=4; 498 v2 = XXH32_round(v2, XXH_readLE32(p, endian)); p+=4; 499 v3 = XXH32_round(v3, XXH_readLE32(p, endian)); p+=4; 500 v4 = XXH32_round(v4, XXH_readLE32(p, endian)); p+=4; 501 } while (p<=limit); 502 503 state->v1 = v1; 504 state->v2 = v2; 505 state->v3 = v3; 506 state->v4 = v4; 507 } 508 509 if (p < bEnd) { 510 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p)); 511 state->memsize = (unsigned)(bEnd-p); 512 } 513 } 514 515 return XXH_OK; 516 } 517 518 519 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len) 520 { 521 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 522 523 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 524 return XXH32_update_endian(state_in, input, len, XXH_littleEndian); 525 else 526 return XXH32_update_endian(state_in, input, len, XXH_bigEndian); 527 } 528 529 530 FORCE_INLINE U32 531 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianness endian) 532 { 533 U32 h32; 534 535 if (state->large_len) { 536 h32 = XXH_rotl32(state->v1, 1) 537 + XXH_rotl32(state->v2, 7) 538 + XXH_rotl32(state->v3, 12) 539 + XXH_rotl32(state->v4, 18); 540 } else { 541 h32 = state->v3 /* == seed */ + PRIME32_5; 542 } 543 544 h32 += state->total_len_32; 545 546 return XXH32_finalize(h32, state->mem32, state->memsize, endian, XXH_aligned); 547 } 548 549 550 XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in) 551 { 552 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 553 554 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 555 return XXH32_digest_endian(state_in, XXH_littleEndian); 556 else 557 return XXH32_digest_endian(state_in, XXH_bigEndian); 558 } 559 560 561 /*====== Canonical representation ======*/ 562 563 /*! Default XXH result types are basic unsigned 32 and 64 bits. 564 * The canonical representation follows human-readable write convention, aka big-endian (large digits first). 565 * These functions allow transformation of hash result into and from its canonical format. 566 * This way, hash values can be written into a file or buffer, remaining comparable across different systems. 567 */ 568 569 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) 570 { 571 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t)); 572 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash); 573 memcpy(dst, &hash, sizeof(*dst)); 574 } 575 576 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src) 577 { 578 return XXH_readBE32(src); 579 } 580 581 582 #ifndef XXH_NO_LONG_LONG 583 584 /* ******************************************************************* 585 * 64-bit hash functions 586 *********************************************************************/ 587 588 /*====== Memory access ======*/ 589 590 #ifndef MEM_MODULE 591 # define MEM_MODULE 592 # if !defined (__VMS) \ 593 && (defined (__cplusplus) \ 594 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 595 # include <stdint.h> 596 typedef uint64_t U64; 597 # else 598 /* if compiler doesn't support unsigned long long, replace by another 64-bit type */ 599 typedef unsigned long long U64; 600 # endif 601 #endif 602 603 604 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) 605 606 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ 607 static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; } 608 609 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) 610 611 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 612 /* currently only defined for gcc and icc */ 613 typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign64; 614 static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; } 615 616 #else 617 618 /* portable and safe solution. Generally efficient. 619 * see : http://stackoverflow.com/a/32095106/646947 620 */ 621 622 static U64 XXH_read64(const void* memPtr) 623 { 624 U64 val; 625 memcpy(&val, memPtr, sizeof(val)); 626 return val; 627 } 628 629 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ 630 631 #if defined(_MSC_VER) /* Visual Studio */ 632 # define XXH_swap64 _byteswap_uint64 633 #elif XXH_GCC_VERSION >= 403 634 # define XXH_swap64 __builtin_bswap64 635 #else 636 static U64 XXH_swap64 (U64 x) 637 { 638 return ((x << 56) & 0xff00000000000000ULL) | 639 ((x << 40) & 0x00ff000000000000ULL) | 640 ((x << 24) & 0x0000ff0000000000ULL) | 641 ((x << 8) & 0x000000ff00000000ULL) | 642 ((x >> 8) & 0x00000000ff000000ULL) | 643 ((x >> 24) & 0x0000000000ff0000ULL) | 644 ((x >> 40) & 0x000000000000ff00ULL) | 645 ((x >> 56) & 0x00000000000000ffULL); 646 } 647 #endif 648 649 FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianness endian, XXH_alignment align) 650 { 651 if (align==XXH_unaligned) 652 return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr)); 653 else 654 return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr); 655 } 656 657 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianness endian) 658 { 659 return XXH_readLE64_align(ptr, endian, XXH_unaligned); 660 } 661 662 static U64 XXH_readBE64(const void* ptr) 663 { 664 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr); 665 } 666 667 668 /*====== xxh64 ======*/ 669 670 static const U64 PRIME64_1 = 11400714785074694791ULL; 671 static const U64 PRIME64_2 = 14029467366897019727ULL; 672 static const U64 PRIME64_3 = 1609587929392839161ULL; 673 static const U64 PRIME64_4 = 9650029242287828579ULL; 674 static const U64 PRIME64_5 = 2870177450012600261ULL; 675 676 static U64 XXH64_round(U64 acc, U64 input) 677 { 678 acc += input * PRIME64_2; 679 acc = XXH_rotl64(acc, 31); 680 acc *= PRIME64_1; 681 return acc; 682 } 683 684 static U64 XXH64_mergeRound(U64 acc, U64 val) 685 { 686 val = XXH64_round(0, val); 687 acc ^= val; 688 acc = acc * PRIME64_1 + PRIME64_4; 689 return acc; 690 } 691 692 static U64 XXH64_avalanche(U64 h64) 693 { 694 h64 ^= h64 >> 33; 695 h64 *= PRIME64_2; 696 h64 ^= h64 >> 29; 697 h64 *= PRIME64_3; 698 h64 ^= h64 >> 32; 699 return h64; 700 } 701 702 703 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align) 704 705 static U64 706 XXH64_finalize(U64 h64, const void* ptr, size_t len, 707 XXH_endianness endian, XXH_alignment align) 708 { 709 const BYTE* p = (const BYTE*)ptr; 710 711 #define PROCESS1_64 \ 712 h64 ^= (*p++) * PRIME64_5; \ 713 h64 = XXH_rotl64(h64, 11) * PRIME64_1; 714 715 #define PROCESS4_64 \ 716 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1; \ 717 p+=4; \ 718 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 719 720 #define PROCESS8_64 { \ 721 U64 const k1 = XXH64_round(0, XXH_get64bits(p)); \ 722 p+=8; \ 723 h64 ^= k1; \ 724 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; \ 725 } 726 727 switch(len&31) { 728 case 24: PROCESS8_64; 729 /* fallthrough */ 730 case 16: PROCESS8_64; 731 /* fallthrough */ 732 case 8: PROCESS8_64; 733 return XXH64_avalanche(h64); 734 735 case 28: PROCESS8_64; 736 /* fallthrough */ 737 case 20: PROCESS8_64; 738 /* fallthrough */ 739 case 12: PROCESS8_64; 740 /* fallthrough */ 741 case 4: PROCESS4_64; 742 return XXH64_avalanche(h64); 743 744 case 25: PROCESS8_64; 745 /* fallthrough */ 746 case 17: PROCESS8_64; 747 /* fallthrough */ 748 case 9: PROCESS8_64; 749 PROCESS1_64; 750 return XXH64_avalanche(h64); 751 752 case 29: PROCESS8_64; 753 /* fallthrough */ 754 case 21: PROCESS8_64; 755 /* fallthrough */ 756 case 13: PROCESS8_64; 757 /* fallthrough */ 758 case 5: PROCESS4_64; 759 PROCESS1_64; 760 return XXH64_avalanche(h64); 761 762 case 26: PROCESS8_64; 763 /* fallthrough */ 764 case 18: PROCESS8_64; 765 /* fallthrough */ 766 case 10: PROCESS8_64; 767 PROCESS1_64; 768 PROCESS1_64; 769 return XXH64_avalanche(h64); 770 771 case 30: PROCESS8_64; 772 /* fallthrough */ 773 case 22: PROCESS8_64; 774 /* fallthrough */ 775 case 14: PROCESS8_64; 776 /* fallthrough */ 777 case 6: PROCESS4_64; 778 PROCESS1_64; 779 PROCESS1_64; 780 return XXH64_avalanche(h64); 781 782 case 27: PROCESS8_64; 783 /* fallthrough */ 784 case 19: PROCESS8_64; 785 /* fallthrough */ 786 case 11: PROCESS8_64; 787 PROCESS1_64; 788 PROCESS1_64; 789 PROCESS1_64; 790 return XXH64_avalanche(h64); 791 792 case 31: PROCESS8_64; 793 /* fallthrough */ 794 case 23: PROCESS8_64; 795 /* fallthrough */ 796 case 15: PROCESS8_64; 797 /* fallthrough */ 798 case 7: PROCESS4_64; 799 /* fallthrough */ 800 case 3: PROCESS1_64; 801 /* fallthrough */ 802 case 2: PROCESS1_64; 803 /* fallthrough */ 804 case 1: PROCESS1_64; 805 /* fallthrough */ 806 case 0: return XXH64_avalanche(h64); 807 } 808 809 /* impossible to reach */ 810 assert(0); 811 return 0; /* unreachable, but some compilers complain without it */ 812 } 813 814 FORCE_INLINE U64 815 XXH64_endian_align(const void* input, size_t len, U64 seed, 816 XXH_endianness endian, XXH_alignment align) 817 { 818 const BYTE* p = (const BYTE*)input; 819 const BYTE* bEnd = p + len; 820 U64 h64; 821 822 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 823 if (p==NULL) { 824 len=0; 825 bEnd=p=(const BYTE*)(size_t)32; 826 } 827 #endif 828 829 if (len>=32) { 830 const BYTE* const limit = bEnd - 32; 831 U64 v1 = seed + PRIME64_1 + PRIME64_2; 832 U64 v2 = seed + PRIME64_2; 833 U64 v3 = seed + 0; 834 U64 v4 = seed - PRIME64_1; 835 836 do { 837 v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8; 838 v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8; 839 v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8; 840 v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8; 841 } while (p<=limit); 842 843 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 844 h64 = XXH64_mergeRound(h64, v1); 845 h64 = XXH64_mergeRound(h64, v2); 846 h64 = XXH64_mergeRound(h64, v3); 847 h64 = XXH64_mergeRound(h64, v4); 848 849 } else { 850 h64 = seed + PRIME64_5; 851 } 852 853 h64 += (U64) len; 854 855 return XXH64_finalize(h64, p, len, endian, align); 856 } 857 858 859 XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed) 860 { 861 #if 0 862 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 863 XXH64_state_t state; 864 XXH64_reset(&state, seed); 865 XXH64_update(&state, input, len); 866 return XXH64_digest(&state); 867 #else 868 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 869 870 if (XXH_FORCE_ALIGN_CHECK) { 871 if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */ 872 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 873 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 874 else 875 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 876 } } 877 878 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 879 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); 880 else 881 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 882 #endif 883 } 884 885 /*====== Hash Streaming ======*/ 886 887 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void) 888 { 889 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t)); 890 } 891 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr) 892 { 893 XXH_free(statePtr); 894 return XXH_OK; 895 } 896 897 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState) 898 { 899 memcpy(dstState, srcState, sizeof(*dstState)); 900 } 901 902 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed) 903 { 904 XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ 905 memset(&state, 0, sizeof(state)); 906 state.v1 = seed + PRIME64_1 + PRIME64_2; 907 state.v2 = seed + PRIME64_2; 908 state.v3 = seed + 0; 909 state.v4 = seed - PRIME64_1; 910 /* do not write into reserved, planned to be removed in a future version */ 911 memcpy(statePtr, &state, sizeof(state) - sizeof(state.reserved)); 912 return XXH_OK; 913 } 914 915 FORCE_INLINE XXH_errorcode 916 XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianness endian) 917 { 918 if (input==NULL) 919 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 920 return XXH_OK; 921 #else 922 return XXH_ERROR; 923 #endif 924 925 { const BYTE* p = (const BYTE*)input; 926 const BYTE* const bEnd = p + len; 927 928 state->total_len += len; 929 930 if (state->memsize + len < 32) { /* fill in tmp buffer */ 931 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len); 932 state->memsize += (U32)len; 933 return XXH_OK; 934 } 935 936 if (state->memsize) { /* tmp buffer is full */ 937 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize); 938 state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0, endian)); 939 state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1, endian)); 940 state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2, endian)); 941 state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3, endian)); 942 p += 32-state->memsize; 943 state->memsize = 0; 944 } 945 946 if (p+32 <= bEnd) { 947 const BYTE* const limit = bEnd - 32; 948 U64 v1 = state->v1; 949 U64 v2 = state->v2; 950 U64 v3 = state->v3; 951 U64 v4 = state->v4; 952 953 do { 954 v1 = XXH64_round(v1, XXH_readLE64(p, endian)); p+=8; 955 v2 = XXH64_round(v2, XXH_readLE64(p, endian)); p+=8; 956 v3 = XXH64_round(v3, XXH_readLE64(p, endian)); p+=8; 957 v4 = XXH64_round(v4, XXH_readLE64(p, endian)); p+=8; 958 } while (p<=limit); 959 960 state->v1 = v1; 961 state->v2 = v2; 962 state->v3 = v3; 963 state->v4 = v4; 964 } 965 966 if (p < bEnd) { 967 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p)); 968 state->memsize = (unsigned)(bEnd-p); 969 } 970 } 971 972 return XXH_OK; 973 } 974 975 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len) 976 { 977 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 978 979 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 980 return XXH64_update_endian(state_in, input, len, XXH_littleEndian); 981 else 982 return XXH64_update_endian(state_in, input, len, XXH_bigEndian); 983 } 984 985 FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianness endian) 986 { 987 U64 h64; 988 989 if (state->total_len >= 32) { 990 U64 const v1 = state->v1; 991 U64 const v2 = state->v2; 992 U64 const v3 = state->v3; 993 U64 const v4 = state->v4; 994 995 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 996 h64 = XXH64_mergeRound(h64, v1); 997 h64 = XXH64_mergeRound(h64, v2); 998 h64 = XXH64_mergeRound(h64, v3); 999 h64 = XXH64_mergeRound(h64, v4); 1000 } else { 1001 h64 = state->v3 /*seed*/ + PRIME64_5; 1002 } 1003 1004 h64 += (U64) state->total_len; 1005 1006 return XXH64_finalize(h64, state->mem64, (size_t)state->total_len, endian, XXH_aligned); 1007 } 1008 1009 XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in) 1010 { 1011 XXH_endianness endian_detected = (XXH_endianness)XXH_CPU_LITTLE_ENDIAN; 1012 1013 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 1014 return XXH64_digest_endian(state_in, XXH_littleEndian); 1015 else 1016 return XXH64_digest_endian(state_in, XXH_bigEndian); 1017 } 1018 1019 1020 /*====== Canonical representation ======*/ 1021 1022 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) 1023 { 1024 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t)); 1025 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash); 1026 memcpy(dst, &hash, sizeof(*dst)); 1027 } 1028 1029 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src) 1030 { 1031 return XXH_readBE64(src); 1032 } 1033 1034 #endif /* XXH_NO_LONG_LONG */