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__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) ) 54 # define XXH_FORCE_MEMORY_ACCESS 2 55 # elif (defined(__INTEL_COMPILER) && !defined(WIN32)) || \ 56 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) )) 57 # define XXH_FORCE_MEMORY_ACCESS 1 58 # endif 59 #endif 60 61 /*!XXH_ACCEPT_NULL_INPUT_POINTER : 62 * If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. 63 * When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. 64 * By default, this option is disabled. To enable it, uncomment below define : 65 */ 66 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */ 67 68 /*!XXH_FORCE_NATIVE_FORMAT : 69 * By default, xxHash library provides endian-independent Hash values, based on little-endian convention. 70 * Results are therefore identical for little-endian and big-endian CPU. 71 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. 72 * Should endian-independence be of no importance for your application, you may set the #define below to 1, 73 * to improve speed for Big-endian CPU. 74 * This option has no impact on Little_Endian CPU. 75 */ 76 #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */ 77 # define XXH_FORCE_NATIVE_FORMAT 0 78 #endif 79 80 /*!XXH_FORCE_ALIGN_CHECK : 81 * This is a minor performance trick, only useful with lots of very small keys. 82 * It means : check for aligned/unaligned input. 83 * The check costs one initial branch per hash; set to 0 when the input data 84 * is guaranteed to be aligned. 85 */ 86 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */ 87 # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) 88 # define XXH_FORCE_ALIGN_CHECK 0 89 # else 90 # define XXH_FORCE_ALIGN_CHECK 1 91 # endif 92 #endif 93 94 95 /* ************************************* 96 * Includes & Memory related functions 97 ***************************************/ 98 /* Modify the local functions below should you wish to use some other memory routines */ 99 /* for malloc(), free() */ 100 #include <stdlib.h> 101 #include <stddef.h> /* size_t */ 102 static void* XXH_malloc(size_t s) { return malloc(s); } 103 static void XXH_free (void* p) { free(p); } 104 /* for memcpy() */ 105 #include <string.h> 106 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); } 107 108 #ifndef XXH_STATIC_LINKING_ONLY 109 # define XXH_STATIC_LINKING_ONLY 110 #endif 111 #include "xxhash.h" 112 113 114 /* ************************************* 115 * Compiler Specific Options 116 ***************************************/ 117 #if defined (__GNUC__) || defined(__cplusplus) || defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 118 # define INLINE_KEYWORD inline 119 #else 120 # define INLINE_KEYWORD 121 #endif 122 123 #if defined(__GNUC__) 124 # define FORCE_INLINE_ATTR __attribute__((always_inline)) 125 #elif defined(_MSC_VER) 126 # define FORCE_INLINE_ATTR __forceinline 127 #else 128 # define FORCE_INLINE_ATTR 129 #endif 130 131 #define FORCE_INLINE_TEMPLATE static INLINE_KEYWORD FORCE_INLINE_ATTR 132 133 134 #ifdef _MSC_VER 135 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 136 #endif 137 138 139 /* ************************************* 140 * Basic Types 141 ***************************************/ 142 #ifndef MEM_MODULE 143 # define MEM_MODULE 144 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 145 # include <stdint.h> 146 typedef uint8_t BYTE; 147 typedef uint16_t U16; 148 typedef uint32_t U32; 149 typedef int32_t S32; 150 typedef uint64_t U64; 151 # else 152 typedef unsigned char BYTE; 153 typedef unsigned short U16; 154 typedef unsigned int U32; 155 typedef signed int S32; 156 typedef unsigned long long U64; /* if your compiler doesn't support unsigned long long, replace by another 64-bit type here. Note that xxhash.h will also need to be updated. */ 157 # endif 158 #endif 159 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 static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; } 166 167 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) 168 169 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */ 170 /* currently only defined for gcc and icc */ 171 typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign; 172 173 static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; } 174 static U64 XXH_read64(const void* ptr) { return ((const unalign*)ptr)->u64; } 175 176 #else 177 178 /* portable and safe solution. Generally efficient. 179 * see : http://stackoverflow.com/a/32095106/646947 180 */ 181 182 static U32 XXH_read32(const void* memPtr) 183 { 184 U32 val; 185 memcpy(&val, memPtr, sizeof(val)); 186 return val; 187 } 188 189 static U64 XXH_read64(const void* memPtr) 190 { 191 U64 val; 192 memcpy(&val, memPtr, sizeof(val)); 193 return val; 194 } 195 196 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ 197 198 199 /* **************************************** 200 * Compiler-specific Functions and Macros 201 ******************************************/ 202 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 203 204 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */ 205 #if defined(_MSC_VER) 206 # define XXH_rotl32(x,r) _rotl(x,r) 207 # define XXH_rotl64(x,r) _rotl64(x,r) 208 #else 209 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) 210 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r))) 211 #endif 212 213 #if defined(_MSC_VER) /* Visual Studio */ 214 # define XXH_swap32 _byteswap_ulong 215 # define XXH_swap64 _byteswap_uint64 216 #elif GCC_VERSION >= 403 217 # define XXH_swap32 __builtin_bswap32 218 # define XXH_swap64 __builtin_bswap64 219 #else 220 static U32 XXH_swap32 (U32 x) 221 { 222 return ((x << 24) & 0xff000000 ) | 223 ((x << 8) & 0x00ff0000 ) | 224 ((x >> 8) & 0x0000ff00 ) | 225 ((x >> 24) & 0x000000ff ); 226 } 227 static U64 XXH_swap64 (U64 x) 228 { 229 return ((x << 56) & 0xff00000000000000ULL) | 230 ((x << 40) & 0x00ff000000000000ULL) | 231 ((x << 24) & 0x0000ff0000000000ULL) | 232 ((x << 8) & 0x000000ff00000000ULL) | 233 ((x >> 8) & 0x00000000ff000000ULL) | 234 ((x >> 24) & 0x0000000000ff0000ULL) | 235 ((x >> 40) & 0x000000000000ff00ULL) | 236 ((x >> 56) & 0x00000000000000ffULL); 237 } 238 #endif 239 240 241 /* ************************************* 242 * Architecture Macros 243 ***************************************/ 244 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; 245 246 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */ 247 #ifndef XXH_CPU_LITTLE_ENDIAN 248 static const int g_one = 1; 249 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one)) 250 #endif 251 252 253 /* *************************** 254 * Memory reads 255 *****************************/ 256 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; 257 258 FORCE_INLINE_TEMPLATE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align) 259 { 260 if (align==XXH_unaligned) 261 return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr)); 262 else 263 return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr); 264 } 265 266 FORCE_INLINE_TEMPLATE U32 XXH_readLE32(const void* ptr, XXH_endianess endian) 267 { 268 return XXH_readLE32_align(ptr, endian, XXH_unaligned); 269 } 270 271 static U32 XXH_readBE32(const void* ptr) 272 { 273 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr); 274 } 275 276 FORCE_INLINE_TEMPLATE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align) 277 { 278 if (align==XXH_unaligned) 279 return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr)); 280 else 281 return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr); 282 } 283 284 FORCE_INLINE_TEMPLATE U64 XXH_readLE64(const void* ptr, XXH_endianess endian) 285 { 286 return XXH_readLE64_align(ptr, endian, XXH_unaligned); 287 } 288 289 static U64 XXH_readBE64(const void* ptr) 290 { 291 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr); 292 } 293 294 295 /* ************************************* 296 * Macros 297 ***************************************/ 298 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */ 299 300 301 /* ************************************* 302 * Constants 303 ***************************************/ 304 static const U32 PRIME32_1 = 2654435761U; 305 static const U32 PRIME32_2 = 2246822519U; 306 static const U32 PRIME32_3 = 3266489917U; 307 static const U32 PRIME32_4 = 668265263U; 308 static const U32 PRIME32_5 = 374761393U; 309 310 static const U64 PRIME64_1 = 11400714785074694791ULL; 311 static const U64 PRIME64_2 = 14029467366897019727ULL; 312 static const U64 PRIME64_3 = 1609587929392839161ULL; 313 static const U64 PRIME64_4 = 9650029242287828579ULL; 314 static const U64 PRIME64_5 = 2870177450012600261ULL; 315 316 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; } 317 318 319 /* ************************** 320 * Utils 321 ****************************/ 322 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* restrict dstState, const XXH32_state_t* restrict srcState) 323 { 324 memcpy(dstState, srcState, sizeof(*dstState)); 325 } 326 327 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* restrict dstState, const XXH64_state_t* restrict srcState) 328 { 329 memcpy(dstState, srcState, sizeof(*dstState)); 330 } 331 332 333 /* *************************** 334 * Simple Hash Functions 335 *****************************/ 336 337 static U32 XXH32_round(U32 seed, U32 input) 338 { 339 seed += input * PRIME32_2; 340 seed = XXH_rotl32(seed, 13); 341 seed *= PRIME32_1; 342 return seed; 343 } 344 345 FORCE_INLINE_TEMPLATE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align) 346 { 347 const BYTE* p = (const BYTE*)input; 348 const BYTE* bEnd = p + len; 349 U32 h32; 350 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align) 351 352 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER 353 if (p==NULL) { 354 len=0; 355 bEnd=p=(const BYTE*)(size_t)16; 356 } 357 #endif 358 359 if (len>=16) { 360 const BYTE* const limit = bEnd - 16; 361 U32 v1 = seed + PRIME32_1 + PRIME32_2; 362 U32 v2 = seed + PRIME32_2; 363 U32 v3 = seed + 0; 364 U32 v4 = seed - PRIME32_1; 365 366 do { 367 v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4; 368 v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4; 369 v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4; 370 v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4; 371 } while (p<=limit); 372 373 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); 374 } else { 375 h32 = seed + PRIME32_5; 376 } 377 378 h32 += (U32) len; 379 380 while (p+4<=bEnd) { 381 h32 += XXH_get32bits(p) * PRIME32_3; 382 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; 383 p+=4; 384 } 385 386 while (p<bEnd) { 387 h32 += (*p) * PRIME32_5; 388 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; 389 p++; 390 } 391 392 h32 ^= h32 >> 15; 393 h32 *= PRIME32_2; 394 h32 ^= h32 >> 13; 395 h32 *= PRIME32_3; 396 h32 ^= h32 >> 16; 397 398 return h32; 399 } 400 401 402 XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed) 403 { 404 #if 0 405 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 406 XXH32_CREATESTATE_STATIC(state); 407 XXH32_reset(state, seed); 408 XXH32_update(state, input, len); 409 return XXH32_digest(state); 410 #else 411 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 412 413 if (XXH_FORCE_ALIGN_CHECK) { 414 if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */ 415 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 416 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 417 else 418 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 419 } } 420 421 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 422 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); 423 else 424 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 425 #endif 426 } 427 428 429 static U64 XXH64_round(U64 acc, U64 input) 430 { 431 acc += input * PRIME64_2; 432 acc = XXH_rotl64(acc, 31); 433 acc *= PRIME64_1; 434 return acc; 435 } 436 437 static U64 XXH64_mergeRound(U64 acc, U64 val) 438 { 439 val = XXH64_round(0, val); 440 acc ^= val; 441 acc = acc * PRIME64_1 + PRIME64_4; 442 return acc; 443 } 444 445 FORCE_INLINE_TEMPLATE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align) 446 { 447 const BYTE* p = (const BYTE*)input; 448 const BYTE* const bEnd = p + len; 449 U64 h64; 450 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align) 451 452 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER 453 if (p==NULL) { 454 len=0; 455 bEnd=p=(const BYTE*)(size_t)32; 456 } 457 #endif 458 459 if (len>=32) { 460 const BYTE* const limit = bEnd - 32; 461 U64 v1 = seed + PRIME64_1 + PRIME64_2; 462 U64 v2 = seed + PRIME64_2; 463 U64 v3 = seed + 0; 464 U64 v4 = seed - PRIME64_1; 465 466 do { 467 v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8; 468 v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8; 469 v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8; 470 v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8; 471 } while (p<=limit); 472 473 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 474 h64 = XXH64_mergeRound(h64, v1); 475 h64 = XXH64_mergeRound(h64, v2); 476 h64 = XXH64_mergeRound(h64, v3); 477 h64 = XXH64_mergeRound(h64, v4); 478 479 } else { 480 h64 = seed + PRIME64_5; 481 } 482 483 h64 += (U64) len; 484 485 while (p+8<=bEnd) { 486 U64 const k1 = XXH64_round(0, XXH_get64bits(p)); 487 h64 ^= k1; 488 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; 489 p+=8; 490 } 491 492 if (p+4<=bEnd) { 493 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1; 494 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 495 p+=4; 496 } 497 498 while (p<bEnd) { 499 h64 ^= (*p) * PRIME64_5; 500 h64 = XXH_rotl64(h64, 11) * PRIME64_1; 501 p++; 502 } 503 504 h64 ^= h64 >> 33; 505 h64 *= PRIME64_2; 506 h64 ^= h64 >> 29; 507 h64 *= PRIME64_3; 508 h64 ^= h64 >> 32; 509 510 return h64; 511 } 512 513 514 XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed) 515 { 516 #if 0 517 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 518 XXH64_CREATESTATE_STATIC(state); 519 XXH64_reset(state, seed); 520 XXH64_update(state, input, len); 521 return XXH64_digest(state); 522 #else 523 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 524 525 if (XXH_FORCE_ALIGN_CHECK) { 526 if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */ 527 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 528 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 529 else 530 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 531 } } 532 533 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 534 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); 535 else 536 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 537 #endif 538 } 539 540 541 /* ************************************************** 542 * Advanced Hash Functions 543 ****************************************************/ 544 545 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void) 546 { 547 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t)); 548 } 549 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr) 550 { 551 XXH_free(statePtr); 552 return XXH_OK; 553 } 554 555 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void) 556 { 557 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t)); 558 } 559 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr) 560 { 561 XXH_free(statePtr); 562 return XXH_OK; 563 } 564 565 566 /*** Hash feed ***/ 567 568 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed) 569 { 570 XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ 571 memset(&state, 0, sizeof(state)-4); /* do not write into reserved, for future removal */ 572 state.v1 = seed + PRIME32_1 + PRIME32_2; 573 state.v2 = seed + PRIME32_2; 574 state.v3 = seed + 0; 575 state.v4 = seed - PRIME32_1; 576 memcpy(statePtr, &state, sizeof(state)); 577 return XXH_OK; 578 } 579 580 581 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed) 582 { 583 XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ 584 memset(&state, 0, sizeof(state)-8); /* do not write into reserved, for future removal */ 585 state.v1 = seed + PRIME64_1 + PRIME64_2; 586 state.v2 = seed + PRIME64_2; 587 state.v3 = seed + 0; 588 state.v4 = seed - PRIME64_1; 589 memcpy(statePtr, &state, sizeof(state)); 590 return XXH_OK; 591 } 592 593 594 FORCE_INLINE_TEMPLATE XXH_errorcode XXH32_update_endian (XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian) 595 { 596 const BYTE* p = (const BYTE*)input; 597 const BYTE* const bEnd = p + len; 598 599 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER 600 if (input==NULL) return XXH_ERROR; 601 #endif 602 603 state->total_len_32 += (unsigned)len; 604 state->large_len |= (len>=16) | (state->total_len_32>=16); 605 606 if (state->memsize + len < 16) { /* fill in tmp buffer */ 607 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len); 608 state->memsize += (unsigned)len; 609 return XXH_OK; 610 } 611 612 if (state->memsize) { /* some data left from previous update */ 613 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize); 614 { const U32* p32 = state->mem32; 615 state->v1 = XXH32_round(state->v1, XXH_readLE32(p32, endian)); p32++; 616 state->v2 = XXH32_round(state->v2, XXH_readLE32(p32, endian)); p32++; 617 state->v3 = XXH32_round(state->v3, XXH_readLE32(p32, endian)); p32++; 618 state->v4 = XXH32_round(state->v4, XXH_readLE32(p32, endian)); p32++; 619 } 620 p += 16-state->memsize; 621 state->memsize = 0; 622 } 623 624 if (p <= bEnd-16) { 625 const BYTE* const limit = bEnd - 16; 626 U32 v1 = state->v1; 627 U32 v2 = state->v2; 628 U32 v3 = state->v3; 629 U32 v4 = state->v4; 630 631 do { 632 v1 = XXH32_round(v1, XXH_readLE32(p, endian)); p+=4; 633 v2 = XXH32_round(v2, XXH_readLE32(p, endian)); p+=4; 634 v3 = XXH32_round(v3, XXH_readLE32(p, endian)); p+=4; 635 v4 = XXH32_round(v4, XXH_readLE32(p, endian)); p+=4; 636 } while (p<=limit); 637 638 state->v1 = v1; 639 state->v2 = v2; 640 state->v3 = v3; 641 state->v4 = v4; 642 } 643 644 if (p < bEnd) { 645 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p)); 646 state->memsize = (unsigned)(bEnd-p); 647 } 648 649 return XXH_OK; 650 } 651 652 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len) 653 { 654 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 655 656 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 657 return XXH32_update_endian(state_in, input, len, XXH_littleEndian); 658 else 659 return XXH32_update_endian(state_in, input, len, XXH_bigEndian); 660 } 661 662 663 664 FORCE_INLINE_TEMPLATE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian) 665 { 666 const BYTE * p = (const BYTE*)state->mem32; 667 const BYTE* const bEnd = (const BYTE*)(state->mem32) + state->memsize; 668 U32 h32; 669 670 if (state->large_len) { 671 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); 672 } else { 673 h32 = state->v3 /* == seed */ + PRIME32_5; 674 } 675 676 h32 += state->total_len_32; 677 678 while (p+4<=bEnd) { 679 h32 += XXH_readLE32(p, endian) * PRIME32_3; 680 h32 = XXH_rotl32(h32, 17) * PRIME32_4; 681 p+=4; 682 } 683 684 while (p<bEnd) { 685 h32 += (*p) * PRIME32_5; 686 h32 = XXH_rotl32(h32, 11) * PRIME32_1; 687 p++; 688 } 689 690 h32 ^= h32 >> 15; 691 h32 *= PRIME32_2; 692 h32 ^= h32 >> 13; 693 h32 *= PRIME32_3; 694 h32 ^= h32 >> 16; 695 696 return h32; 697 } 698 699 700 XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in) 701 { 702 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 703 704 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 705 return XXH32_digest_endian(state_in, XXH_littleEndian); 706 else 707 return XXH32_digest_endian(state_in, XXH_bigEndian); 708 } 709 710 711 712 /* **** XXH64 **** */ 713 714 FORCE_INLINE_TEMPLATE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian) 715 { 716 const BYTE* p = (const BYTE*)input; 717 const BYTE* const bEnd = p + len; 718 719 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER 720 if (input==NULL) return XXH_ERROR; 721 #endif 722 723 state->total_len += len; 724 725 if (state->memsize + len < 32) { /* fill in tmp buffer */ 726 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len); 727 state->memsize += (U32)len; 728 return XXH_OK; 729 } 730 731 if (state->memsize) { /* tmp buffer is full */ 732 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize); 733 state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0, endian)); 734 state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1, endian)); 735 state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2, endian)); 736 state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3, endian)); 737 p += 32-state->memsize; 738 state->memsize = 0; 739 } 740 741 if (p+32 <= bEnd) { 742 const BYTE* const limit = bEnd - 32; 743 U64 v1 = state->v1; 744 U64 v2 = state->v2; 745 U64 v3 = state->v3; 746 U64 v4 = state->v4; 747 748 do { 749 v1 = XXH64_round(v1, XXH_readLE64(p, endian)); p+=8; 750 v2 = XXH64_round(v2, XXH_readLE64(p, endian)); p+=8; 751 v3 = XXH64_round(v3, XXH_readLE64(p, endian)); p+=8; 752 v4 = XXH64_round(v4, XXH_readLE64(p, endian)); p+=8; 753 } while (p<=limit); 754 755 state->v1 = v1; 756 state->v2 = v2; 757 state->v3 = v3; 758 state->v4 = v4; 759 } 760 761 if (p < bEnd) { 762 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p)); 763 state->memsize = (unsigned)(bEnd-p); 764 } 765 766 return XXH_OK; 767 } 768 769 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len) 770 { 771 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 772 773 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 774 return XXH64_update_endian(state_in, input, len, XXH_littleEndian); 775 else 776 return XXH64_update_endian(state_in, input, len, XXH_bigEndian); 777 } 778 779 780 781 FORCE_INLINE_TEMPLATE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian) 782 { 783 const BYTE * p = (const BYTE*)state->mem64; 784 const BYTE* const bEnd = (const BYTE*)state->mem64 + state->memsize; 785 U64 h64; 786 787 if (state->total_len >= 32) { 788 U64 const v1 = state->v1; 789 U64 const v2 = state->v2; 790 U64 const v3 = state->v3; 791 U64 const v4 = state->v4; 792 793 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 794 h64 = XXH64_mergeRound(h64, v1); 795 h64 = XXH64_mergeRound(h64, v2); 796 h64 = XXH64_mergeRound(h64, v3); 797 h64 = XXH64_mergeRound(h64, v4); 798 } else { 799 h64 = state->v3 + PRIME64_5; 800 } 801 802 h64 += (U64) state->total_len; 803 804 while (p+8<=bEnd) { 805 U64 const k1 = XXH64_round(0, XXH_readLE64(p, endian)); 806 h64 ^= k1; 807 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4; 808 p+=8; 809 } 810 811 if (p+4<=bEnd) { 812 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1; 813 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 814 p+=4; 815 } 816 817 while (p<bEnd) { 818 h64 ^= (*p) * PRIME64_5; 819 h64 = XXH_rotl64(h64, 11) * PRIME64_1; 820 p++; 821 } 822 823 h64 ^= h64 >> 33; 824 h64 *= PRIME64_2; 825 h64 ^= h64 >> 29; 826 h64 *= PRIME64_3; 827 h64 ^= h64 >> 32; 828 829 return h64; 830 } 831 832 833 XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in) 834 { 835 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 836 837 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 838 return XXH64_digest_endian(state_in, XXH_littleEndian); 839 else 840 return XXH64_digest_endian(state_in, XXH_bigEndian); 841 } 842 843 844 /* ************************** 845 * Canonical representation 846 ****************************/ 847 848 /*! Default XXH result types are basic unsigned 32 and 64 bits. 849 * The canonical representation follows human-readable write convention, aka big-endian (large digits first). 850 * These functions allow transformation of hash result into and from its canonical format. 851 * This way, hash values can be written into a file or buffer, and remain comparable across different systems and programs. 852 */ 853 854 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) 855 { 856 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t)); 857 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash); 858 memcpy(dst, &hash, sizeof(*dst)); 859 } 860 861 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) 862 { 863 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t)); 864 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash); 865 memcpy(dst, &hash, sizeof(*dst)); 866 } 867 868 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src) 869 { 870 return XXH_readBE32(src); 871 } 872 873 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src) 874 { 875 return XXH_readBE64(src); 876 } 877