1 /*(lighttpd customization)*/ 2 #define XXH_NO_INLINE_HINTS 1 3 /*#define XXH_REROLL 1*/ 4 5 /* 6 * xxHash - Extremely Fast Hash algorithm 7 * Header File 8 * Copyright (C) 2012-2020 Yann Collet 9 * 10 * BSD 2-Clause License (https://www.opensource.org/licenses/bsd-license.php) 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions are 14 * met: 15 * 16 * * Redistributions of source code must retain the above copyright 17 * notice, this list of conditions and the following disclaimer. 18 * * Redistributions in binary form must reproduce the above 19 * copyright notice, this list of conditions and the following disclaimer 20 * in the documentation and/or other materials provided with the 21 * distribution. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 29 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 30 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 31 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 32 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 33 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 * 35 * You can contact the author at: 36 * - xxHash homepage: https://www.xxhash.com 37 * - xxHash source repository: https://github.com/Cyan4973/xxHash 38 */ 39 40 /* TODO: update */ 41 /* Notice extracted from xxHash homepage: 42 43 xxHash is an extremely fast hash algorithm, running at RAM speed limits. 44 It also successfully passes all tests from the SMHasher suite. 45 46 Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 Duo @3GHz) 47 48 Name Speed Q.Score Author 49 xxHash 5.4 GB/s 10 50 CrapWow 3.2 GB/s 2 Andrew 51 MumurHash 3a 2.7 GB/s 10 Austin Appleby 52 SpookyHash 2.0 GB/s 10 Bob Jenkins 53 SBox 1.4 GB/s 9 Bret Mulvey 54 Lookup3 1.2 GB/s 9 Bob Jenkins 55 SuperFastHash 1.2 GB/s 1 Paul Hsieh 56 CityHash64 1.05 GB/s 10 Pike & Alakuijala 57 FNV 0.55 GB/s 5 Fowler, Noll, Vo 58 CRC32 0.43 GB/s 9 59 MD5-32 0.33 GB/s 10 Ronald L. Rivest 60 SHA1-32 0.28 GB/s 10 61 62 Q.Score is a measure of quality of the hash function. 63 It depends on successfully passing SMHasher test set. 64 10 is a perfect score. 65 66 Note: SMHasher's CRC32 implementation is not the fastest one. 67 Other speed-oriented implementations can be faster, 68 especially in combination with PCLMUL instruction: 69 https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html?showComment=1552696407071#c3490092340461170735 70 71 A 64-bit version, named XXH64, is available since r35. 72 It offers much better speed, but for 64-bit applications only. 73 Name Speed on 64 bits Speed on 32 bits 74 XXH64 13.8 GB/s 1.9 GB/s 75 XXH32 6.8 GB/s 6.0 GB/s 76 */ 77 78 #if defined (__cplusplus) 79 extern "C" { 80 #endif 81 82 /* **************************** 83 * INLINE mode 84 ******************************/ 85 /*! 86 * XXH_INLINE_ALL (and XXH_PRIVATE_API) 87 * Use these build macros to inline xxhash into the target unit. 88 * Inlining improves performance on small inputs, especially when the length is 89 * expressed as a compile-time constant: 90 * 91 * https://fastcompression.blogspot.com/2018/03/xxhash-for-small-keys-impressive-power.html 92 * 93 * It also keeps xxHash symbols private to the unit, so they are not exported. 94 * 95 * Usage: 96 * #define XXH_INLINE_ALL 97 * #include "xxhash.h" 98 * 99 * Do not compile and link xxhash.o as a separate object, as it is not useful. 100 */ 101 #if (defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API)) \ 102 && !defined(XXH_INLINE_ALL_31684351384) 103 /* this section should be traversed only once */ 104 # define XXH_INLINE_ALL_31684351384 105 /* give access to the advanced API, required to compile implementations */ 106 # undef XXH_STATIC_LINKING_ONLY /* avoid macro redef */ 107 # define XXH_STATIC_LINKING_ONLY 108 /* make all functions private */ 109 # undef XXH_PUBLIC_API 110 # if defined(__GNUC__) 111 # define XXH_PUBLIC_API static __inline __attribute__((unused)) 112 # elif defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) 113 # define XXH_PUBLIC_API static inline 114 # elif defined(_MSC_VER) 115 # define XXH_PUBLIC_API static __inline 116 # else 117 /* note: this version may generate warnings for unused static functions */ 118 # define XXH_PUBLIC_API static 119 # endif 120 121 /* 122 * This part deals with the special case where a unit wants to inline xxHash, 123 * but "xxhash.h" has previously been included without XXH_INLINE_ALL, such 124 * as part of some previously included *.h header file. 125 * Without further action, the new include would just be ignored, 126 * and functions would effectively _not_ be inlined (silent failure). 127 * The following macros solve this situation by prefixing all inlined names, 128 * avoiding naming collision with previous inclusions. 129 */ 130 # ifdef XXH_NAMESPACE 131 # error "XXH_INLINE_ALL with XXH_NAMESPACE is not supported" 132 /* 133 * Note: Alternative: #undef all symbols (it's a pretty large list). 134 * Without #error: it compiles, but functions are actually not inlined. 135 */ 136 # endif 137 # define XXH_NAMESPACE XXH_INLINE_ 138 /* 139 * Some identifiers (enums, type names) are not symbols, but they must 140 * still be renamed to avoid redeclaration. 141 * Alternative solution: do not redeclare them. 142 * However, this requires some #ifdefs, and is a more dispersed action. 143 * Meanwhile, renaming can be achieved in a single block 144 */ 145 # define XXH_IPREF(Id) XXH_INLINE_ ## Id 146 # define XXH_OK XXH_IPREF(XXH_OK) 147 # define XXH_ERROR XXH_IPREF(XXH_ERROR) 148 # define XXH_errorcode XXH_IPREF(XXH_errorcode) 149 # define XXH32_canonical_t XXH_IPREF(XXH32_canonical_t) 150 # define XXH64_canonical_t XXH_IPREF(XXH64_canonical_t) 151 # define XXH128_canonical_t XXH_IPREF(XXH128_canonical_t) 152 # define XXH32_state_s XXH_IPREF(XXH32_state_s) 153 # define XXH32_state_t XXH_IPREF(XXH32_state_t) 154 # define XXH64_state_s XXH_IPREF(XXH64_state_s) 155 # define XXH64_state_t XXH_IPREF(XXH64_state_t) 156 # define XXH3_state_s XXH_IPREF(XXH3_state_s) 157 # define XXH3_state_t XXH_IPREF(XXH3_state_t) 158 # define XXH128_hash_t XXH_IPREF(XXH128_hash_t) 159 /* Ensure the header is parsed again, even if it was previously included */ 160 # undef XXHASH_H_5627135585666179 161 # undef XXHASH_H_STATIC_13879238742 162 #endif /* XXH_INLINE_ALL || XXH_PRIVATE_API */ 163 164 165 166 /* **************************************************************** 167 * Stable API 168 *****************************************************************/ 169 #ifndef XXHASH_H_5627135585666179 170 #define XXHASH_H_5627135585666179 1 171 172 /* specific declaration modes for Windows */ 173 #if !defined(XXH_INLINE_ALL) && !defined(XXH_PRIVATE_API) 174 # if defined(WIN32) && defined(_MSC_VER) && (defined(XXH_IMPORT) || defined(XXH_EXPORT)) 175 # ifdef XXH_EXPORT 176 # define XXH_PUBLIC_API __declspec(dllexport) 177 # elif XXH_IMPORT 178 # define XXH_PUBLIC_API __declspec(dllimport) 179 # endif 180 # else 181 # define XXH_PUBLIC_API /* do nothing */ 182 # endif 183 #endif 184 185 /*! 186 * XXH_NAMESPACE, aka Namespace Emulation: 187 * 188 * If you want to include _and expose_ xxHash functions from within your own 189 * library, but also want to avoid symbol collisions with other libraries which 190 * may also include xxHash, you can use XXH_NAMESPACE to automatically prefix 191 * any public symbol from xxhash library with the value of XXH_NAMESPACE 192 * (therefore, avoid empty or numeric values). 193 * 194 * Note that no change is required within the calling program as long as it 195 * includes `xxhash.h`: Regular symbol names will be automatically translated 196 * by this header. 197 */ 198 #ifdef XXH_NAMESPACE 199 # define XXH_CAT(A,B) A##B 200 # define XXH_NAME2(A,B) XXH_CAT(A,B) 201 # define XXH_versionNumber XXH_NAME2(XXH_NAMESPACE, XXH_versionNumber) 202 /* XXH32 */ 203 # define XXH32 XXH_NAME2(XXH_NAMESPACE, XXH32) 204 # define XXH32_createState XXH_NAME2(XXH_NAMESPACE, XXH32_createState) 205 # define XXH32_freeState XXH_NAME2(XXH_NAMESPACE, XXH32_freeState) 206 # define XXH32_reset XXH_NAME2(XXH_NAMESPACE, XXH32_reset) 207 # define XXH32_update XXH_NAME2(XXH_NAMESPACE, XXH32_update) 208 # define XXH32_digest XXH_NAME2(XXH_NAMESPACE, XXH32_digest) 209 # define XXH32_copyState XXH_NAME2(XXH_NAMESPACE, XXH32_copyState) 210 # define XXH32_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH32_canonicalFromHash) 211 # define XXH32_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH32_hashFromCanonical) 212 /* XXH64 */ 213 # define XXH64 XXH_NAME2(XXH_NAMESPACE, XXH64) 214 # define XXH64_createState XXH_NAME2(XXH_NAMESPACE, XXH64_createState) 215 # define XXH64_freeState XXH_NAME2(XXH_NAMESPACE, XXH64_freeState) 216 # define XXH64_reset XXH_NAME2(XXH_NAMESPACE, XXH64_reset) 217 # define XXH64_update XXH_NAME2(XXH_NAMESPACE, XXH64_update) 218 # define XXH64_digest XXH_NAME2(XXH_NAMESPACE, XXH64_digest) 219 # define XXH64_copyState XXH_NAME2(XXH_NAMESPACE, XXH64_copyState) 220 # define XXH64_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH64_canonicalFromHash) 221 # define XXH64_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH64_hashFromCanonical) 222 /* XXH3_64bits */ 223 # define XXH3_64bits XXH_NAME2(XXH_NAMESPACE, XXH3_64bits) 224 # define XXH3_64bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSecret) 225 # define XXH3_64bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_withSeed) 226 # define XXH3_createState XXH_NAME2(XXH_NAMESPACE, XXH3_createState) 227 # define XXH3_freeState XXH_NAME2(XXH_NAMESPACE, XXH3_freeState) 228 # define XXH3_copyState XXH_NAME2(XXH_NAMESPACE, XXH3_copyState) 229 # define XXH3_64bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset) 230 # define XXH3_64bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSeed) 231 # define XXH3_64bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_reset_withSecret) 232 # define XXH3_64bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_update) 233 # define XXH3_64bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_64bits_digest) 234 # define XXH3_generateSecret XXH_NAME2(XXH_NAMESPACE, XXH3_generateSecret) 235 /* XXH3_128bits */ 236 # define XXH128 XXH_NAME2(XXH_NAMESPACE, XXH128) 237 # define XXH3_128bits XXH_NAME2(XXH_NAMESPACE, XXH3_128bits) 238 # define XXH3_128bits_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSeed) 239 # define XXH3_128bits_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_withSecret) 240 # define XXH3_128bits_reset XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset) 241 # define XXH3_128bits_reset_withSeed XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSeed) 242 # define XXH3_128bits_reset_withSecret XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_reset_withSecret) 243 # define XXH3_128bits_update XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_update) 244 # define XXH3_128bits_digest XXH_NAME2(XXH_NAMESPACE, XXH3_128bits_digest) 245 # define XXH128_isEqual XXH_NAME2(XXH_NAMESPACE, XXH128_isEqual) 246 # define XXH128_cmp XXH_NAME2(XXH_NAMESPACE, XXH128_cmp) 247 # define XXH128_canonicalFromHash XXH_NAME2(XXH_NAMESPACE, XXH128_canonicalFromHash) 248 # define XXH128_hashFromCanonical XXH_NAME2(XXH_NAMESPACE, XXH128_hashFromCanonical) 249 #endif 250 251 252 /* ************************************* 253 * Version 254 ***************************************/ 255 #define XXH_VERSION_MAJOR 0 256 #define XXH_VERSION_MINOR 8 257 #define XXH_VERSION_RELEASE 0 258 #define XXH_VERSION_NUMBER (XXH_VERSION_MAJOR *100*100 + XXH_VERSION_MINOR *100 + XXH_VERSION_RELEASE) 259 XXH_PUBLIC_API unsigned XXH_versionNumber (void); 260 261 262 /* **************************** 263 * Definitions 264 ******************************/ 265 #include <stddef.h> /* size_t */ 266 typedef enum { XXH_OK=0, XXH_ERROR } XXH_errorcode; 267 268 269 /*-********************************************************************** 270 * 32-bit hash 271 ************************************************************************/ 272 #if !defined (__VMS) \ 273 && (defined (__cplusplus) \ 274 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 275 # include <stdint.h> 276 typedef uint32_t XXH32_hash_t; 277 #else 278 # include <limits.h> 279 # if UINT_MAX == 0xFFFFFFFFUL 280 typedef unsigned int XXH32_hash_t; 281 # else 282 # if ULONG_MAX == 0xFFFFFFFFUL 283 typedef unsigned long XXH32_hash_t; 284 # else 285 # error "unsupported platform: need a 32-bit type" 286 # endif 287 # endif 288 #endif 289 290 /*! 291 * XXH32(): 292 * Calculate the 32-bit hash of sequence "length" bytes stored at memory address "input". 293 * The memory between input & input+length must be valid (allocated and read-accessible). 294 * "seed" can be used to alter the result predictably. 295 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark): 5.4 GB/s 296 * 297 * Note: XXH3 provides competitive speed for both 32-bit and 64-bit systems, 298 * and offers true 64/128 bit hash results. It provides a superior level of 299 * dispersion, and greatly reduces the risks of collisions. 300 */ 301 XXH_PUBLIC_API XXH32_hash_t XXH32 (const void* input, size_t length, XXH32_hash_t seed); 302 303 /******* Streaming *******/ 304 305 /* 306 * Streaming functions generate the xxHash value from an incrememtal input. 307 * This method is slower than single-call functions, due to state management. 308 * For small inputs, prefer `XXH32()` and `XXH64()`, which are better optimized. 309 * 310 * An XXH state must first be allocated using `XXH*_createState()`. 311 * 312 * Start a new hash by initializing the state with a seed using `XXH*_reset()`. 313 * 314 * Then, feed the hash state by calling `XXH*_update()` as many times as necessary. 315 * 316 * The function returns an error code, with 0 meaning OK, and any other value 317 * meaning there is an error. 318 * 319 * Finally, a hash value can be produced anytime, by using `XXH*_digest()`. 320 * This function returns the nn-bits hash as an int or long long. 321 * 322 * It's still possible to continue inserting input into the hash state after a 323 * digest, and generate new hash values later on by invoking `XXH*_digest()`. 324 * 325 * When done, release the state using `XXH*_freeState()`. 326 */ 327 328 typedef struct XXH32_state_s XXH32_state_t; /* incomplete type */ 329 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void); 330 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr); 331 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dst_state, const XXH32_state_t* src_state); 332 333 XXH_PUBLIC_API XXH_errorcode XXH32_reset (XXH32_state_t* statePtr, XXH32_hash_t seed); 334 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* statePtr, const void* input, size_t length); 335 XXH_PUBLIC_API XXH32_hash_t XXH32_digest (const XXH32_state_t* statePtr); 336 337 /******* Canonical representation *******/ 338 339 /* 340 * The default return values from XXH functions are unsigned 32 and 64 bit 341 * integers. 342 * This the simplest and fastest format for further post-processing. 343 * 344 * However, this leaves open the question of what is the order on the byte level, 345 * since little and big endian conventions will store the same number differently. 346 * 347 * The canonical representation settles this issue by mandating big-endian 348 * convention, the same convention as human-readable numbers (large digits first). 349 * 350 * When writing hash values to storage, sending them over a network, or printing 351 * them, it's highly recommended to use the canonical representation to ensure 352 * portability across a wider range of systems, present and future. 353 * 354 * The following functions allow transformation of hash values to and from 355 * canonical format. 356 */ 357 358 typedef struct { unsigned char digest[4]; } XXH32_canonical_t; 359 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash); 360 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src); 361 362 363 #ifndef XXH_NO_LONG_LONG 364 /*-********************************************************************** 365 * 64-bit hash 366 ************************************************************************/ 367 #if !defined (__VMS) \ 368 && (defined (__cplusplus) \ 369 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 370 # include <stdint.h> 371 typedef uint64_t XXH64_hash_t; 372 #else 373 /* the following type must have a width of 64-bit */ 374 typedef unsigned long long XXH64_hash_t; 375 #endif 376 377 /*! 378 * XXH64(): 379 * Returns the 64-bit hash of sequence of length @length stored at memory 380 * address @input. 381 * @seed can be used to alter the result predictably. 382 * 383 * This function usually runs faster on 64-bit systems, but slower on 32-bit 384 * systems (see benchmark). 385 * 386 * Note: XXH3 provides competitive speed for both 32-bit and 64-bit systems, 387 * and offers true 64/128 bit hash results. It provides a superior level of 388 * dispersion, and greatly reduces the risks of collisions. 389 */ 390 XXH_PUBLIC_API XXH64_hash_t XXH64 (const void* input, size_t length, XXH64_hash_t seed); 391 392 /******* Streaming *******/ 393 typedef struct XXH64_state_s XXH64_state_t; /* incomplete type */ 394 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void); 395 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr); 396 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dst_state, const XXH64_state_t* src_state); 397 398 XXH_PUBLIC_API XXH_errorcode XXH64_reset (XXH64_state_t* statePtr, XXH64_hash_t seed); 399 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* statePtr, const void* input, size_t length); 400 XXH_PUBLIC_API XXH64_hash_t XXH64_digest (const XXH64_state_t* statePtr); 401 402 /******* Canonical representation *******/ 403 typedef struct { unsigned char digest[sizeof(XXH64_hash_t)]; } XXH64_canonical_t; 404 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash); 405 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src); 406 407 408 /*-********************************************************************** 409 * XXH3 64-bit variant 410 ************************************************************************/ 411 412 /* ************************************************************************ 413 * XXH3 is a new hash algorithm featuring: 414 * - Improved speed for both small and large inputs 415 * - True 64-bit and 128-bit outputs 416 * - SIMD acceleration 417 * - Improved 32-bit viability 418 * 419 * Speed analysis methodology is explained here: 420 * 421 * https://fastcompression.blogspot.com/2019/03/presenting-xxh3.html 422 * 423 * In general, expect XXH3 to run about ~2x faster on large inputs and >3x 424 * faster on small ones compared to XXH64, though exact differences depend on 425 * the platform. 426 * 427 * The algorithm is portable: Like XXH32 and XXH64, it generates the same hash 428 * on all platforms. 429 * 430 * It benefits greatly from SIMD and 64-bit arithmetic, but does not require it. 431 * 432 * Almost all 32-bit and 64-bit targets that can run XXH32 smoothly can run 433 * XXH3 at competitive speeds, even if XXH64 runs slowly. Further details are 434 * explained in the implementation. 435 * 436 * Optimized implementations are provided for AVX512, AVX2, SSE2, NEON, POWER8, 437 * ZVector and scalar targets. This can be controlled with the XXH_VECTOR macro. 438 * 439 * XXH3 offers 2 variants, _64bits and _128bits. 440 * When only 64 bits are needed, prefer calling the _64bits variant, as it 441 * reduces the amount of mixing, resulting in faster speed on small inputs. 442 * 443 * It's also generally simpler to manipulate a scalar return type than a struct. 444 * 445 * The 128-bit version adds additional strength, but it is slightly slower. 446 * 447 * The XXH3 algorithm is still in development. 448 * The results it produces may still change in future versions. 449 * 450 * Results produced by v0.7.x are not comparable with results from v0.7.y. 451 * However, the API is completely stable, and it can safely be used for 452 * ephemeral data (local sessions). 453 * 454 * Avoid storing values in long-term storage until the algorithm is finalized. 455 * XXH3's return values will be officially finalized upon reaching v0.8.0. 456 * 457 * After which, return values of XXH3 and XXH128 will no longer change in 458 * future versions. 459 * 460 * The API supports one-shot hashing, streaming mode, and custom secrets. 461 */ 462 463 /* XXH3_64bits(): 464 * default 64-bit variant, using default secret and default seed of 0. 465 * It's the fastest variant. */ 466 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits(const void* data, size_t len); 467 468 /* 469 * XXH3_64bits_withSeed(): 470 * This variant generates a custom secret on the fly 471 * based on default secret altered using the `seed` value. 472 * While this operation is decently fast, note that it's not completely free. 473 * Note: seed==0 produces the same results as XXH3_64bits(). 474 */ 475 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_withSeed(const void* data, size_t len, XXH64_hash_t seed); 476 477 /* 478 * XXH3_64bits_withSecret(): 479 * It's possible to provide any blob of bytes as a "secret" to generate the hash. 480 * This makes it more difficult for an external actor to prepare an intentional collision. 481 * The main condition is that secretSize *must* be large enough (>= XXH3_SECRET_SIZE_MIN). 482 * However, the quality of produced hash values depends on secret's entropy. 483 * Technically, the secret must look like a bunch of random bytes. 484 * Avoid "trivial" or structured data such as repeated sequences or a text document. 485 * Whenever unsure about the "randomness" of the blob of bytes, 486 * consider relabelling it as a "custom seed" instead, 487 * and employ "XXH3_generateSecret()" (see below) 488 * to generate a high entropy secret derived from the custom seed. 489 */ 490 #define XXH3_SECRET_SIZE_MIN 136 491 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_withSecret(const void* data, size_t len, const void* secret, size_t secretSize); 492 493 494 /******* Streaming *******/ 495 /* 496 * Streaming requires state maintenance. 497 * This operation costs memory and CPU. 498 * As a consequence, streaming is slower than one-shot hashing. 499 * For better performance, prefer one-shot functions whenever applicable. 500 */ 501 typedef struct XXH3_state_s XXH3_state_t; 502 XXH_PUBLIC_API XXH3_state_t* XXH3_createState(void); 503 XXH_PUBLIC_API XXH_errorcode XXH3_freeState(XXH3_state_t* statePtr); 504 XXH_PUBLIC_API void XXH3_copyState(XXH3_state_t* dst_state, const XXH3_state_t* src_state); 505 506 /* 507 * XXH3_64bits_reset(): 508 * Initialize with default parameters. 509 * digest will be equivalent to `XXH3_64bits()`. 510 */ 511 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset(XXH3_state_t* statePtr); 512 /* 513 * XXH3_64bits_reset_withSeed(): 514 * Generate a custom secret from `seed`, and store it into `statePtr`. 515 * digest will be equivalent to `XXH3_64bits_withSeed()`. 516 */ 517 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed); 518 /* 519 * XXH3_64bits_reset_withSecret(): 520 * `secret` is referenced, it _must outlive_ the hash streaming session. 521 * Similar to one-shot API, `secretSize` must be >= `XXH3_SECRET_SIZE_MIN`, 522 * and the quality of produced hash values depends on secret's entropy 523 * (secret's content should look like a bunch of random bytes). 524 * When in doubt about the randomness of a candidate `secret`, 525 * consider employing `XXH3_generateSecret()` instead (see below). 526 */ 527 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize); 528 529 XXH_PUBLIC_API XXH_errorcode XXH3_64bits_update (XXH3_state_t* statePtr, const void* input, size_t length); 530 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_digest (const XXH3_state_t* statePtr); 531 532 /* note : canonical representation of XXH3 is the same as XXH64 533 * since they both produce XXH64_hash_t values */ 534 535 536 /*-********************************************************************** 537 * XXH3 128-bit variant 538 ************************************************************************/ 539 540 typedef struct { 541 XXH64_hash_t low64; 542 XXH64_hash_t high64; 543 } XXH128_hash_t; 544 545 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits(const void* data, size_t len); 546 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_withSeed(const void* data, size_t len, XXH64_hash_t seed); 547 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_withSecret(const void* data, size_t len, const void* secret, size_t secretSize); 548 549 /******* Streaming *******/ 550 /* 551 * Streaming requires state maintenance. 552 * This operation costs memory and CPU. 553 * As a consequence, streaming is slower than one-shot hashing. 554 * For better performance, prefer one-shot functions whenever applicable. 555 * 556 * XXH3_128bits uses the same XXH3_state_t as XXH3_64bits(). 557 * Use already declared XXH3_createState() and XXH3_freeState(). 558 * 559 * All reset and streaming functions have same meaning as their 64-bit counterpart. 560 */ 561 562 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset(XXH3_state_t* statePtr); 563 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed); 564 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize); 565 566 XXH_PUBLIC_API XXH_errorcode XXH3_128bits_update (XXH3_state_t* statePtr, const void* input, size_t length); 567 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_digest (const XXH3_state_t* statePtr); 568 569 /* Following helper functions make it possible to compare XXH128_hast_t values. 570 * Since XXH128_hash_t is a structure, this capability is not offered by the language. 571 * Note: For better performance, these functions can be inlined using XXH_INLINE_ALL */ 572 573 /*! 574 * XXH128_isEqual(): 575 * Return: 1 if `h1` and `h2` are equal, 0 if they are not. 576 */ 577 XXH_PUBLIC_API int XXH128_isEqual(XXH128_hash_t h1, XXH128_hash_t h2); 578 579 /*! 580 * XXH128_cmp(): 581 * 582 * This comparator is compatible with stdlib's `qsort()`/`bsearch()`. 583 * 584 * return: >0 if *h128_1 > *h128_2 585 * =0 if *h128_1 == *h128_2 586 * <0 if *h128_1 < *h128_2 587 */ 588 XXH_PUBLIC_API int XXH128_cmp(const void* h128_1, const void* h128_2); 589 590 591 /******* Canonical representation *******/ 592 typedef struct { unsigned char digest[sizeof(XXH128_hash_t)]; } XXH128_canonical_t; 593 XXH_PUBLIC_API void XXH128_canonicalFromHash(XXH128_canonical_t* dst, XXH128_hash_t hash); 594 XXH_PUBLIC_API XXH128_hash_t XXH128_hashFromCanonical(const XXH128_canonical_t* src); 595 596 597 #endif /* XXH_NO_LONG_LONG */ 598 599 #endif /* XXHASH_H_5627135585666179 */ 600 601 602 603 #if defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742) 604 #define XXHASH_H_STATIC_13879238742 605 /* **************************************************************************** 606 * This section contains declarations which are not guaranteed to remain stable. 607 * They may change in future versions, becoming incompatible with a different 608 * version of the library. 609 * These declarations should only be used with static linking. 610 * Never use them in association with dynamic linking! 611 ***************************************************************************** */ 612 613 /* 614 * These definitions are only present to allow static allocation 615 * of XXH states, on stack or in a struct, for example. 616 * Never **ever** access their members directly. 617 */ 618 619 struct XXH32_state_s { 620 XXH32_hash_t total_len_32; 621 XXH32_hash_t large_len; 622 XXH32_hash_t v1; 623 XXH32_hash_t v2; 624 XXH32_hash_t v3; 625 XXH32_hash_t v4; 626 XXH32_hash_t mem32[4]; 627 XXH32_hash_t memsize; 628 XXH32_hash_t reserved; /* never read nor write, might be removed in a future version */ 629 }; /* typedef'd to XXH32_state_t */ 630 631 632 #ifndef XXH_NO_LONG_LONG /* defined when there is no 64-bit support */ 633 634 struct XXH64_state_s { 635 XXH64_hash_t total_len; 636 XXH64_hash_t v1; 637 XXH64_hash_t v2; 638 XXH64_hash_t v3; 639 XXH64_hash_t v4; 640 XXH64_hash_t mem64[4]; 641 XXH32_hash_t memsize; 642 XXH32_hash_t reserved32; /* required for padding anyway */ 643 XXH64_hash_t reserved64; /* never read nor write, might be removed in a future version */ 644 }; /* typedef'd to XXH64_state_t */ 645 646 #if defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L) /* C11+ */ 647 # include <stdalign.h> 648 # define XXH_ALIGN(n) alignas(n) 649 #elif defined(__GNUC__) 650 # define XXH_ALIGN(n) __attribute__ ((aligned(n))) 651 #elif defined(_MSC_VER) 652 # define XXH_ALIGN(n) __declspec(align(n)) 653 #else 654 # define XXH_ALIGN(n) /* disabled */ 655 #endif 656 657 /* Old GCC versions only accept the attribute after the type in structures. */ 658 #if !(defined(__STDC_VERSION__) && (__STDC_VERSION__ >= 201112L)) /* C11+ */ \ 659 && defined(__GNUC__) 660 # define XXH_ALIGN_MEMBER(align, type) type XXH_ALIGN(align) 661 #else 662 # define XXH_ALIGN_MEMBER(align, type) XXH_ALIGN(align) type 663 #endif 664 665 #define XXH3_INTERNALBUFFER_SIZE 256 666 #define XXH3_SECRET_DEFAULT_SIZE 192 667 struct XXH3_state_s { 668 XXH_ALIGN_MEMBER(64, XXH64_hash_t acc[8]); 669 /* used to store a custom secret generated from a seed */ 670 XXH_ALIGN_MEMBER(64, unsigned char customSecret[XXH3_SECRET_DEFAULT_SIZE]); 671 XXH_ALIGN_MEMBER(64, unsigned char buffer[XXH3_INTERNALBUFFER_SIZE]); 672 XXH32_hash_t bufferedSize; 673 XXH32_hash_t reserved32; 674 size_t nbStripesSoFar; 675 XXH64_hash_t totalLen; 676 size_t nbStripesPerBlock; 677 size_t secretLimit; 678 XXH64_hash_t seed; 679 XXH64_hash_t reserved64; 680 const unsigned char* extSecret; /* reference to external secret; 681 * if == NULL, use .customSecret instead */ 682 /* note: there may be some padding at the end due to alignment on 64 bytes */ 683 }; /* typedef'd to XXH3_state_t */ 684 685 #undef XXH_ALIGN_MEMBER 686 687 /* When the XXH3_state_t structure is merely emplaced on stack, 688 * it should be initialized with XXH3_INITSTATE() or a memset() 689 * in case its first reset uses XXH3_NNbits_reset_withSeed(). 690 * This init can be omitted if the first reset uses default or _withSecret mode. 691 * This operation isn't necessary when the state is created with XXH3_createState(). 692 * Note that this doesn't prepare the state for a streaming operation, 693 * it's still necessary to use XXH3_NNbits_reset*() afterwards. 694 */ 695 #define XXH3_INITSTATE(XXH3_state_ptr) { (XXH3_state_ptr)->seed = 0; } 696 697 698 /* === Experimental API === */ 699 /* Symbols defined below must be considered tied to a specific library version. */ 700 701 /* 702 * XXH3_generateSecret(): 703 * 704 * Derive a high-entropy secret from any user-defined content, named customSeed. 705 * The generated secret can be used in combination with `*_withSecret()` functions. 706 * The `_withSecret()` variants are useful to provide a higher level of protection than 64-bit seed, 707 * as it becomes much more difficult for an external actor to guess how to impact the calculation logic. 708 * 709 * The function accepts as input a custom seed of any length and any content, 710 * and derives from it a high-entropy secret of length XXH3_SECRET_DEFAULT_SIZE 711 * into an already allocated buffer secretBuffer. 712 * The generated secret is _always_ XXH_SECRET_DEFAULT_SIZE bytes long. 713 * 714 * The generated secret can then be used with any `*_withSecret()` variant. 715 * Functions `XXH3_128bits_withSecret()`, `XXH3_64bits_withSecret()`, 716 * `XXH3_128bits_reset_withSecret()` and `XXH3_64bits_reset_withSecret()` 717 * are part of this list. They all accept a `secret` parameter 718 * which must be very long for implementation reasons (>= XXH3_SECRET_SIZE_MIN) 719 * _and_ feature very high entropy (consist of random-looking bytes). 720 * These conditions can be a high bar to meet, so 721 * this function can be used to generate a secret of proper quality. 722 * 723 * customSeed can be anything. It can have any size, even small ones, 724 * and its content can be anything, even stupidly "low entropy" source such as a bunch of zeroes. 725 * The resulting `secret` will nonetheless provide all expected qualities. 726 * 727 * Supplying NULL as the customSeed copies the default secret into `secretBuffer`. 728 * When customSeedSize > 0, supplying NULL as customSeed is undefined behavior. 729 */ 730 XXH_PUBLIC_API void XXH3_generateSecret(void* secretBuffer, const void* customSeed, size_t customSeedSize); 731 732 733 /* simple short-cut to pre-selected XXH3_128bits variant */ 734 XXH_PUBLIC_API XXH128_hash_t XXH128(const void* data, size_t len, XXH64_hash_t seed); 735 736 737 #endif /* XXH_NO_LONG_LONG */ 738 739 740 #if defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API) 741 # define XXH_IMPLEMENTATION 742 #endif 743 744 #endif /* defined(XXH_STATIC_LINKING_ONLY) && !defined(XXHASH_H_STATIC_13879238742) */ 745 746 747 /* ======================================================================== */ 748 /* ======================================================================== */ 749 /* ======================================================================== */ 750 751 752 /*-********************************************************************** 753 * xxHash implementation 754 *-********************************************************************** 755 * xxHash's implementation used to be hosted inside xxhash.c. 756 * 757 * However, inlining requires implementation to be visible to the compiler, 758 * hence be included alongside the header. 759 * Previously, implementation was hosted inside xxhash.c, 760 * which was then #included when inlining was activated. 761 * This construction created issues with a few build and install systems, 762 * as it required xxhash.c to be stored in /include directory. 763 * 764 * xxHash implementation is now directly integrated within xxhash.h. 765 * As a consequence, xxhash.c is no longer needed in /include. 766 * 767 * xxhash.c is still available and is still useful. 768 * In a "normal" setup, when xxhash is not inlined, 769 * xxhash.h only exposes the prototypes and public symbols, 770 * while xxhash.c can be built into an object file xxhash.o 771 * which can then be linked into the final binary. 772 ************************************************************************/ 773 774 #if ( defined(XXH_INLINE_ALL) || defined(XXH_PRIVATE_API) \ 775 || defined(XXH_IMPLEMENTATION) ) && !defined(XXH_IMPLEM_13a8737387) 776 # define XXH_IMPLEM_13a8737387 777 778 /* ************************************* 779 * Tuning parameters 780 ***************************************/ 781 /*! 782 * XXH_FORCE_MEMORY_ACCESS: 783 * By default, access to unaligned memory is controlled by `memcpy()`, which is 784 * safe and portable. 785 * 786 * Unfortunately, on some target/compiler combinations, the generated assembly 787 * is sub-optimal. 788 * 789 * The below switch allow selection of a different access method 790 * in the search for improved performance. 791 * Method 0 (default): 792 * Use `memcpy()`. Safe and portable. Default. 793 * Method 1: 794 * `__attribute__((packed))` statement. It depends on compiler extensions 795 * and is therefore not portable. 796 * This method is safe if your compiler supports it, and *generally* as 797 * fast or faster than `memcpy`. 798 * Method 2: 799 * Direct access via cast. This method doesn't depend on the compiler but 800 * violates the C standard. 801 * It can generate buggy code on targets which do not support unaligned 802 * memory accesses. 803 * But in some circumstances, it's the only known way to get the most 804 * performance (example: GCC + ARMv6) 805 * Method 3: 806 * Byteshift. This can generate the best code on old compilers which don't 807 * inline small `memcpy()` calls, and it might also be faster on big-endian 808 * systems which lack a native byteswap instruction. 809 * See https://stackoverflow.com/a/32095106/646947 for details. 810 * Prefer these methods in priority order (0 > 1 > 2 > 3) 811 */ 812 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */ 813 # if !defined(__clang__) && defined(__GNUC__) && defined(__ARM_FEATURE_UNALIGNED) && defined(__ARM_ARCH) && (__ARM_ARCH == 6) 814 # define XXH_FORCE_MEMORY_ACCESS 2 815 # elif !defined(__clang__) && ((defined(__INTEL_COMPILER) && !defined(_WIN32)) || \ 816 (defined(__GNUC__) && (defined(__ARM_ARCH) && __ARM_ARCH >= 7))) 817 # define XXH_FORCE_MEMORY_ACCESS 1 818 # endif 819 #endif 820 821 /*! 822 * XXH_ACCEPT_NULL_INPUT_POINTER: 823 * If the input pointer is NULL, xxHash's default behavior is to dereference it, 824 * triggering a segfault. 825 * When this macro is enabled, xxHash actively checks the input for a null pointer. 826 * If it is, the result for null input pointers is the same as a zero-length input. 827 */ 828 #ifndef XXH_ACCEPT_NULL_INPUT_POINTER /* can be defined externally */ 829 # define XXH_ACCEPT_NULL_INPUT_POINTER 0 830 #endif 831 832 /*! 833 * XXH_FORCE_ALIGN_CHECK: 834 * This is an important performance trick 835 * for architectures without decent unaligned memory access performance. 836 * It checks for input alignment, and when conditions are met, 837 * uses a "fast path" employing direct 32-bit/64-bit read, 838 * resulting in _dramatically faster_ read speed. 839 * 840 * The check costs one initial branch per hash, which is generally negligible, but not zero. 841 * Moreover, it's not useful to generate binary for an additional code path 842 * if memory access uses same instruction for both aligned and unaligned adresses. 843 * 844 * In these cases, the alignment check can be removed by setting this macro to 0. 845 * Then the code will always use unaligned memory access. 846 * Align check is automatically disabled on x86, x64 & arm64, 847 * which are platforms known to offer good unaligned memory accesses performance. 848 * 849 * This option does not affect XXH3 (only XXH32 and XXH64). 850 */ 851 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */ 852 # if defined(__i386) || defined(__x86_64__) || defined(__aarch64__) \ 853 || defined(_M_IX86) || defined(_M_X64) || defined(_M_ARM64) /* visual */ 854 # define XXH_FORCE_ALIGN_CHECK 0 855 # else 856 # define XXH_FORCE_ALIGN_CHECK 1 857 # endif 858 #endif 859 860 /*! 861 * XXH_NO_INLINE_HINTS: 862 * 863 * By default, xxHash tries to force the compiler to inline almost all internal 864 * functions. 865 * 866 * This can usually improve performance due to reduced jumping and improved 867 * constant folding, but significantly increases the size of the binary which 868 * might not be favorable. 869 * 870 * Additionally, sometimes the forced inlining can be detrimental to performance, 871 * depending on the architecture. 872 * 873 * XXH_NO_INLINE_HINTS marks all internal functions as static, giving the 874 * compiler full control on whether to inline or not. 875 * 876 * When not optimizing (-O0), optimizing for size (-Os, -Oz), or using 877 * -fno-inline with GCC or Clang, this will automatically be defined. 878 */ 879 #ifndef XXH_NO_INLINE_HINTS 880 # if defined(__OPTIMIZE_SIZE__) /* -Os, -Oz */ \ 881 || defined(__NO_INLINE__) /* -O0, -fno-inline */ 882 # define XXH_NO_INLINE_HINTS 1 883 # else 884 # define XXH_NO_INLINE_HINTS 0 885 # endif 886 #endif 887 888 /*! 889 * XXH_REROLL: 890 * Whether to reroll XXH32_finalize, and XXH64_finalize, 891 * instead of using an unrolled jump table/if statement loop. 892 * 893 * This is automatically defined on -Os/-Oz on GCC and Clang. 894 */ 895 #ifndef XXH_REROLL 896 # if defined(__OPTIMIZE_SIZE__) 897 # define XXH_REROLL 1 898 # else 899 # define XXH_REROLL 0 900 # endif 901 #endif 902 903 904 /* ************************************* 905 * Includes & Memory related functions 906 ***************************************/ 907 /*! 908 * Modify the local functions below should you wish to use 909 * different memory routines for malloc() and free() 910 */ 911 #include <stdlib.h> 912 913 static void* XXH_malloc(size_t s) { return malloc(s); } 914 static void XXH_free(void* p) { free(p); } 915 916 /*! and for memcpy() */ 917 #include <string.h> 918 static void* XXH_memcpy(void* dest, const void* src, size_t size) 919 { 920 return memcpy(dest,src,size); 921 } 922 923 #include <limits.h> /* ULLONG_MAX */ 924 925 926 /* ************************************* 927 * Compiler Specific Options 928 ***************************************/ 929 #ifdef _MSC_VER /* Visual Studio warning fix */ 930 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 931 #endif 932 933 #if XXH_NO_INLINE_HINTS /* disable inlining hints */ 934 # if defined(__GNUC__) 935 # define XXH_FORCE_INLINE static __attribute__((unused)) 936 # else 937 # define XXH_FORCE_INLINE static 938 # endif 939 # define XXH_NO_INLINE static 940 /* enable inlining hints */ 941 #elif defined(_MSC_VER) /* Visual Studio */ 942 # define XXH_FORCE_INLINE static __forceinline 943 # define XXH_NO_INLINE static __declspec(noinline) 944 #elif defined(__GNUC__) 945 # define XXH_FORCE_INLINE static __inline__ __attribute__((always_inline, unused)) 946 # define XXH_NO_INLINE static __attribute__((noinline)) 947 #elif defined (__cplusplus) \ 948 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L)) /* C99 */ 949 # define XXH_FORCE_INLINE static inline 950 # define XXH_NO_INLINE static 951 #else 952 # define XXH_FORCE_INLINE static 953 # define XXH_NO_INLINE static 954 #endif 955 956 957 958 /* ************************************* 959 * Debug 960 ***************************************/ 961 /* 962 * XXH_DEBUGLEVEL is expected to be defined externally, typically via the 963 * compiler's command line options. The value must be a number. 964 */ 965 #ifndef XXH_DEBUGLEVEL 966 # ifdef DEBUGLEVEL /* backwards compat */ 967 # define XXH_DEBUGLEVEL DEBUGLEVEL 968 # else 969 # define XXH_DEBUGLEVEL 0 970 # endif 971 #endif 972 973 #if (XXH_DEBUGLEVEL>=1) 974 # include <assert.h> /* note: can still be disabled with NDEBUG */ 975 # define XXH_ASSERT(c) assert(c) 976 #else 977 # define XXH_ASSERT(c) ((void)0) 978 #endif 979 980 /* note: use after variable declarations */ 981 #define XXH_STATIC_ASSERT(c) do { enum { XXH_sa = 1/(int)(!!(c)) }; } while (0) 982 983 984 /* ************************************* 985 * Basic Types 986 ***************************************/ 987 #if !defined (__VMS) \ 988 && (defined (__cplusplus) \ 989 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 990 # include <stdint.h> 991 typedef uint8_t xxh_u8; 992 #else 993 typedef unsigned char xxh_u8; 994 #endif 995 typedef XXH32_hash_t xxh_u32; 996 997 #ifdef XXH_OLD_NAMES 998 # define BYTE xxh_u8 999 # define U8 xxh_u8 1000 # define U32 xxh_u32 1001 #endif 1002 1003 /* *** Memory access *** */ 1004 1005 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3)) 1006 /* 1007 * Manual byteshift. Best for old compilers which don't inline memcpy. 1008 * We actually directly use XXH_readLE32 and XXH_readBE32. 1009 */ 1010 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) 1011 1012 /* 1013 * Force direct memory access. Only works on CPU which support unaligned memory 1014 * access in hardware. 1015 */ 1016 static xxh_u32 XXH_read32(const void* memPtr) { return *(const xxh_u32*) memPtr; } 1017 1018 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) 1019 1020 /* 1021 * __pack instructions are safer but compiler specific, hence potentially 1022 * problematic for some compilers. 1023 * 1024 * Currently only defined for GCC and ICC. 1025 */ 1026 #ifdef XXH_OLD_NAMES 1027 typedef union { xxh_u32 u32; } __attribute__((packed)) unalign; 1028 #endif 1029 static xxh_u32 XXH_read32(const void* ptr) 1030 { 1031 typedef union { xxh_u32 u32; } __attribute__((packed)) xxh_unalign; 1032 return ((const xxh_unalign*)ptr)->u32; 1033 } 1034 1035 #else 1036 1037 /* 1038 * Portable and safe solution. Generally efficient. 1039 * see: https://stackoverflow.com/a/32095106/646947 1040 */ 1041 static xxh_u32 XXH_read32(const void* memPtr) 1042 { 1043 xxh_u32 val; 1044 memcpy(&val, memPtr, sizeof(val)); 1045 return val; 1046 } 1047 1048 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ 1049 1050 1051 /* *** Endianess *** */ 1052 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; 1053 1054 /*! 1055 * XXH_CPU_LITTLE_ENDIAN: 1056 * Defined to 1 if the target is little endian, or 0 if it is big endian. 1057 * It can be defined externally, for example on the compiler command line. 1058 * 1059 * If it is not defined, a runtime check (which is usually constant folded) 1060 * is used instead. 1061 */ 1062 #ifndef XXH_CPU_LITTLE_ENDIAN 1063 /* 1064 * Try to detect endianness automatically, to avoid the nonstandard behavior 1065 * in `XXH_isLittleEndian()` 1066 */ 1067 # if defined(_WIN32) /* Windows is always little endian */ \ 1068 || defined(__LITTLE_ENDIAN__) \ 1069 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__) 1070 # define XXH_CPU_LITTLE_ENDIAN 1 1071 # elif defined(__BIG_ENDIAN__) \ 1072 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) 1073 # define XXH_CPU_LITTLE_ENDIAN 0 1074 # else 1075 /* 1076 * runtime test, presumed to simplify to a constant by compiler 1077 */ 1078 static int XXH_isLittleEndian(void) 1079 { 1080 /* 1081 * Portable and well-defined behavior. 1082 * Don't use static: it is detrimental to performance. 1083 */ 1084 const union { xxh_u32 u; xxh_u8 c[4]; } one = { 1 }; 1085 return one.c[0]; 1086 } 1087 # define XXH_CPU_LITTLE_ENDIAN XXH_isLittleEndian() 1088 # endif 1089 #endif 1090 1091 1092 1093 1094 /* **************************************** 1095 * Compiler-specific Functions and Macros 1096 ******************************************/ 1097 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 1098 1099 #ifdef __has_builtin 1100 # define XXH_HAS_BUILTIN(x) __has_builtin(x) 1101 #else 1102 # define XXH_HAS_BUILTIN(x) 0 1103 #endif 1104 1105 #if !defined(NO_CLANG_BUILTIN) && XXH_HAS_BUILTIN(__builtin_rotateleft32) \ 1106 && XXH_HAS_BUILTIN(__builtin_rotateleft64) 1107 # define XXH_rotl32 __builtin_rotateleft32 1108 # define XXH_rotl64 __builtin_rotateleft64 1109 /* Note: although _rotl exists for minGW (GCC under windows), performance seems poor */ 1110 #elif defined(_MSC_VER) 1111 # define XXH_rotl32(x,r) _rotl(x,r) 1112 # define XXH_rotl64(x,r) _rotl64(x,r) 1113 #else 1114 # define XXH_rotl32(x,r) (((x) << (r)) | ((x) >> (32 - (r)))) 1115 # define XXH_rotl64(x,r) (((x) << (r)) | ((x) >> (64 - (r)))) 1116 #endif 1117 1118 #if defined(_MSC_VER) /* Visual Studio */ 1119 # define XXH_swap32 _byteswap_ulong 1120 #elif XXH_GCC_VERSION >= 403 1121 # define XXH_swap32 __builtin_bswap32 1122 #else 1123 static xxh_u32 XXH_swap32 (xxh_u32 x) 1124 { 1125 return ((x << 24) & 0xff000000 ) | 1126 ((x << 8) & 0x00ff0000 ) | 1127 ((x >> 8) & 0x0000ff00 ) | 1128 ((x >> 24) & 0x000000ff ); 1129 } 1130 #endif 1131 1132 1133 /* *************************** 1134 * Memory reads 1135 *****************************/ 1136 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; 1137 1138 /* 1139 * XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load. 1140 * 1141 * This is ideal for older compilers which don't inline memcpy. 1142 */ 1143 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3)) 1144 1145 XXH_FORCE_INLINE xxh_u32 XXH_readLE32(const void* memPtr) 1146 { 1147 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr; 1148 return bytePtr[0] 1149 | ((xxh_u32)bytePtr[1] << 8) 1150 | ((xxh_u32)bytePtr[2] << 16) 1151 | ((xxh_u32)bytePtr[3] << 24); 1152 } 1153 1154 XXH_FORCE_INLINE xxh_u32 XXH_readBE32(const void* memPtr) 1155 { 1156 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr; 1157 return bytePtr[3] 1158 | ((xxh_u32)bytePtr[2] << 8) 1159 | ((xxh_u32)bytePtr[1] << 16) 1160 | ((xxh_u32)bytePtr[0] << 24); 1161 } 1162 1163 #else 1164 XXH_FORCE_INLINE xxh_u32 XXH_readLE32(const void* ptr) 1165 { 1166 return XXH_CPU_LITTLE_ENDIAN ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr)); 1167 } 1168 1169 static xxh_u32 XXH_readBE32(const void* ptr) 1170 { 1171 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr); 1172 } 1173 #endif 1174 1175 XXH_FORCE_INLINE xxh_u32 1176 XXH_readLE32_align(const void* ptr, XXH_alignment align) 1177 { 1178 if (align==XXH_unaligned) { 1179 return XXH_readLE32(ptr); 1180 } else { 1181 return XXH_CPU_LITTLE_ENDIAN ? *(const xxh_u32*)ptr : XXH_swap32(*(const xxh_u32*)ptr); 1182 } 1183 } 1184 1185 1186 /* ************************************* 1187 * Misc 1188 ***************************************/ 1189 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; } 1190 1191 1192 /* ******************************************************************* 1193 * 32-bit hash functions 1194 *********************************************************************/ 1195 static const xxh_u32 XXH_PRIME32_1 = 0x9E3779B1U; /* 0b10011110001101110111100110110001 */ 1196 static const xxh_u32 XXH_PRIME32_2 = 0x85EBCA77U; /* 0b10000101111010111100101001110111 */ 1197 static const xxh_u32 XXH_PRIME32_3 = 0xC2B2AE3DU; /* 0b11000010101100101010111000111101 */ 1198 static const xxh_u32 XXH_PRIME32_4 = 0x27D4EB2FU; /* 0b00100111110101001110101100101111 */ 1199 static const xxh_u32 XXH_PRIME32_5 = 0x165667B1U; /* 0b00010110010101100110011110110001 */ 1200 1201 #ifdef XXH_OLD_NAMES 1202 # define PRIME32_1 XXH_PRIME32_1 1203 # define PRIME32_2 XXH_PRIME32_2 1204 # define PRIME32_3 XXH_PRIME32_3 1205 # define PRIME32_4 XXH_PRIME32_4 1206 # define PRIME32_5 XXH_PRIME32_5 1207 #endif 1208 1209 static xxh_u32 XXH32_round(xxh_u32 acc, xxh_u32 input) 1210 { 1211 acc += input * XXH_PRIME32_2; 1212 acc = XXH_rotl32(acc, 13); 1213 acc *= XXH_PRIME32_1; 1214 #if defined(__GNUC__) && defined(__SSE4_1__) && !defined(XXH_ENABLE_AUTOVECTORIZE) 1215 /* 1216 * UGLY HACK: 1217 * This inline assembly hack forces acc into a normal register. This is the 1218 * only thing that prevents GCC and Clang from autovectorizing the XXH32 1219 * loop (pragmas and attributes don't work for some resason) without globally 1220 * disabling SSE4.1. 1221 * 1222 * The reason we want to avoid vectorization is because despite working on 1223 * 4 integers at a time, there are multiple factors slowing XXH32 down on 1224 * SSE4: 1225 * - There's a ridiculous amount of lag from pmulld (10 cycles of latency on 1226 * newer chips!) making it slightly slower to multiply four integers at 1227 * once compared to four integers independently. Even when pmulld was 1228 * fastest, Sandy/Ivy Bridge, it is still not worth it to go into SSE 1229 * just to multiply unless doing a long operation. 1230 * 1231 * - Four instructions are required to rotate, 1232 * movqda tmp, v // not required with VEX encoding 1233 * pslld tmp, 13 // tmp <<= 13 1234 * psrld v, 19 // x >>= 19 1235 * por v, tmp // x |= tmp 1236 * compared to one for scalar: 1237 * roll v, 13 // reliably fast across the board 1238 * shldl v, v, 13 // Sandy Bridge and later prefer this for some reason 1239 * 1240 * - Instruction level parallelism is actually more beneficial here because 1241 * the SIMD actually serializes this operation: While v1 is rotating, v2 1242 * can load data, while v3 can multiply. SSE forces them to operate 1243 * together. 1244 * 1245 * How this hack works: 1246 * __asm__("" // Declare an assembly block but don't declare any instructions 1247 * : // However, as an Input/Output Operand, 1248 * "+r" // constrain a read/write operand (+) as a general purpose register (r). 1249 * (acc) // and set acc as the operand 1250 * ); 1251 * 1252 * Because of the 'r', the compiler has promised that seed will be in a 1253 * general purpose register and the '+' says that it will be 'read/write', 1254 * so it has to assume it has changed. It is like volatile without all the 1255 * loads and stores. 1256 * 1257 * Since the argument has to be in a normal register (not an SSE register), 1258 * each time XXH32_round is called, it is impossible to vectorize. 1259 */ 1260 __asm__("" : "+r" (acc)); 1261 #endif 1262 return acc; 1263 } 1264 1265 /* mix all bits */ 1266 static xxh_u32 XXH32_avalanche(xxh_u32 h32) 1267 { 1268 h32 ^= h32 >> 15; 1269 h32 *= XXH_PRIME32_2; 1270 h32 ^= h32 >> 13; 1271 h32 *= XXH_PRIME32_3; 1272 h32 ^= h32 >> 16; 1273 return(h32); 1274 } 1275 1276 #define XXH_get32bits(p) XXH_readLE32_align(p, align) 1277 1278 static xxh_u32 1279 XXH32_finalize(xxh_u32 h32, const xxh_u8* ptr, size_t len, XXH_alignment align) 1280 { 1281 #define XXH_PROCESS1 do { \ 1282 h32 += (*ptr++) * XXH_PRIME32_5; \ 1283 h32 = XXH_rotl32(h32, 11) * XXH_PRIME32_1; \ 1284 } while (0) 1285 1286 #define XXH_PROCESS4 do { \ 1287 h32 += XXH_get32bits(ptr) * XXH_PRIME32_3; \ 1288 ptr += 4; \ 1289 h32 = XXH_rotl32(h32, 17) * XXH_PRIME32_4; \ 1290 } while (0) 1291 1292 /* Compact rerolled version */ 1293 if (XXH_REROLL) { 1294 len &= 15; 1295 while (len >= 4) { 1296 XXH_PROCESS4; 1297 len -= 4; 1298 } 1299 while (len > 0) { 1300 XXH_PROCESS1; 1301 --len; 1302 } 1303 return XXH32_avalanche(h32); 1304 } else { 1305 switch(len&15) /* or switch(bEnd - p) */ { 1306 case 12: XXH_PROCESS4; 1307 /* fallthrough */ 1308 case 8: XXH_PROCESS4; 1309 /* fallthrough */ 1310 case 4: XXH_PROCESS4; 1311 return XXH32_avalanche(h32); 1312 1313 case 13: XXH_PROCESS4; 1314 /* fallthrough */ 1315 case 9: XXH_PROCESS4; 1316 /* fallthrough */ 1317 case 5: XXH_PROCESS4; 1318 XXH_PROCESS1; 1319 return XXH32_avalanche(h32); 1320 1321 case 14: XXH_PROCESS4; 1322 /* fallthrough */ 1323 case 10: XXH_PROCESS4; 1324 /* fallthrough */ 1325 case 6: XXH_PROCESS4; 1326 XXH_PROCESS1; 1327 XXH_PROCESS1; 1328 return XXH32_avalanche(h32); 1329 1330 case 15: XXH_PROCESS4; 1331 /* fallthrough */ 1332 case 11: XXH_PROCESS4; 1333 /* fallthrough */ 1334 case 7: XXH_PROCESS4; 1335 /* fallthrough */ 1336 case 3: XXH_PROCESS1; 1337 /* fallthrough */ 1338 case 2: XXH_PROCESS1; 1339 /* fallthrough */ 1340 case 1: XXH_PROCESS1; 1341 /* fallthrough */ 1342 case 0: return XXH32_avalanche(h32); 1343 } 1344 XXH_ASSERT(0); 1345 return h32; /* reaching this point is deemed impossible */ 1346 } 1347 } 1348 1349 #ifdef XXH_OLD_NAMES 1350 # define PROCESS1 XXH_PROCESS1 1351 # define PROCESS4 XXH_PROCESS4 1352 #else 1353 # undef XXH_PROCESS1 1354 # undef XXH_PROCESS4 1355 #endif 1356 1357 XXH_FORCE_INLINE xxh_u32 1358 XXH32_endian_align(const xxh_u8* input, size_t len, xxh_u32 seed, XXH_alignment align) 1359 { 1360 const xxh_u8* bEnd = input + len; 1361 xxh_u32 h32; 1362 1363 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 1364 if (input==NULL) { 1365 len=0; 1366 bEnd=input=(const xxh_u8*)(size_t)16; 1367 } 1368 #endif 1369 1370 if (len>=16) { 1371 const xxh_u8* const limit = bEnd - 15; 1372 xxh_u32 v1 = seed + XXH_PRIME32_1 + XXH_PRIME32_2; 1373 xxh_u32 v2 = seed + XXH_PRIME32_2; 1374 xxh_u32 v3 = seed + 0; 1375 xxh_u32 v4 = seed - XXH_PRIME32_1; 1376 1377 do { 1378 v1 = XXH32_round(v1, XXH_get32bits(input)); input += 4; 1379 v2 = XXH32_round(v2, XXH_get32bits(input)); input += 4; 1380 v3 = XXH32_round(v3, XXH_get32bits(input)); input += 4; 1381 v4 = XXH32_round(v4, XXH_get32bits(input)); input += 4; 1382 } while (input < limit); 1383 1384 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) 1385 + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); 1386 } else { 1387 h32 = seed + XXH_PRIME32_5; 1388 } 1389 1390 h32 += (xxh_u32)len; 1391 1392 return XXH32_finalize(h32, input, len&15, align); 1393 } 1394 1395 1396 XXH_PUBLIC_API XXH32_hash_t XXH32 (const void* input, size_t len, XXH32_hash_t seed) 1397 { 1398 #if 0 1399 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 1400 XXH32_state_t state; 1401 XXH32_reset(&state, seed); 1402 XXH32_update(&state, (const xxh_u8*)input, len); 1403 return XXH32_digest(&state); 1404 1405 #else 1406 1407 if (XXH_FORCE_ALIGN_CHECK) { 1408 if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */ 1409 return XXH32_endian_align((const xxh_u8*)input, len, seed, XXH_aligned); 1410 } } 1411 1412 return XXH32_endian_align((const xxh_u8*)input, len, seed, XXH_unaligned); 1413 #endif 1414 } 1415 1416 1417 1418 /******* Hash streaming *******/ 1419 1420 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void) 1421 { 1422 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t)); 1423 } 1424 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr) 1425 { 1426 XXH_free(statePtr); 1427 return XXH_OK; 1428 } 1429 1430 XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t* dstState, const XXH32_state_t* srcState) 1431 { 1432 memcpy(dstState, srcState, sizeof(*dstState)); 1433 } 1434 1435 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, XXH32_hash_t seed) 1436 { 1437 XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */ 1438 memset(&state, 0, sizeof(state)); 1439 state.v1 = seed + XXH_PRIME32_1 + XXH_PRIME32_2; 1440 state.v2 = seed + XXH_PRIME32_2; 1441 state.v3 = seed + 0; 1442 state.v4 = seed - XXH_PRIME32_1; 1443 /* do not write into reserved, planned to be removed in a future version */ 1444 memcpy(statePtr, &state, sizeof(state) - sizeof(state.reserved)); 1445 return XXH_OK; 1446 } 1447 1448 1449 XXH_PUBLIC_API XXH_errorcode 1450 XXH32_update(XXH32_state_t* state, const void* input, size_t len) 1451 { 1452 if (input==NULL) 1453 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 1454 return XXH_OK; 1455 #else 1456 return XXH_ERROR; 1457 #endif 1458 1459 { const xxh_u8* p = (const xxh_u8*)input; 1460 const xxh_u8* const bEnd = p + len; 1461 1462 state->total_len_32 += (XXH32_hash_t)len; 1463 state->large_len |= (XXH32_hash_t)((len>=16) | (state->total_len_32>=16)); 1464 1465 if (state->memsize + len < 16) { /* fill in tmp buffer */ 1466 XXH_memcpy((xxh_u8*)(state->mem32) + state->memsize, input, len); 1467 state->memsize += (XXH32_hash_t)len; 1468 return XXH_OK; 1469 } 1470 1471 if (state->memsize) { /* some data left from previous update */ 1472 XXH_memcpy((xxh_u8*)(state->mem32) + state->memsize, input, 16-state->memsize); 1473 { const xxh_u32* p32 = state->mem32; 1474 state->v1 = XXH32_round(state->v1, XXH_readLE32(p32)); p32++; 1475 state->v2 = XXH32_round(state->v2, XXH_readLE32(p32)); p32++; 1476 state->v3 = XXH32_round(state->v3, XXH_readLE32(p32)); p32++; 1477 state->v4 = XXH32_round(state->v4, XXH_readLE32(p32)); 1478 } 1479 p += 16-state->memsize; 1480 state->memsize = 0; 1481 } 1482 1483 if (p <= bEnd-16) { 1484 const xxh_u8* const limit = bEnd - 16; 1485 xxh_u32 v1 = state->v1; 1486 xxh_u32 v2 = state->v2; 1487 xxh_u32 v3 = state->v3; 1488 xxh_u32 v4 = state->v4; 1489 1490 do { 1491 v1 = XXH32_round(v1, XXH_readLE32(p)); p+=4; 1492 v2 = XXH32_round(v2, XXH_readLE32(p)); p+=4; 1493 v3 = XXH32_round(v3, XXH_readLE32(p)); p+=4; 1494 v4 = XXH32_round(v4, XXH_readLE32(p)); p+=4; 1495 } while (p<=limit); 1496 1497 state->v1 = v1; 1498 state->v2 = v2; 1499 state->v3 = v3; 1500 state->v4 = v4; 1501 } 1502 1503 if (p < bEnd) { 1504 XXH_memcpy(state->mem32, p, (size_t)(bEnd-p)); 1505 state->memsize = (unsigned)(bEnd-p); 1506 } 1507 } 1508 1509 return XXH_OK; 1510 } 1511 1512 1513 XXH_PUBLIC_API XXH32_hash_t XXH32_digest (const XXH32_state_t* state) 1514 { 1515 xxh_u32 h32; 1516 1517 if (state->large_len) { 1518 h32 = XXH_rotl32(state->v1, 1) 1519 + XXH_rotl32(state->v2, 7) 1520 + XXH_rotl32(state->v3, 12) 1521 + XXH_rotl32(state->v4, 18); 1522 } else { 1523 h32 = state->v3 /* == seed */ + XXH_PRIME32_5; 1524 } 1525 1526 h32 += state->total_len_32; 1527 1528 return XXH32_finalize(h32, (const xxh_u8*)state->mem32, state->memsize, XXH_aligned); 1529 } 1530 1531 1532 /******* Canonical representation *******/ 1533 1534 /* 1535 * The default return values from XXH functions are unsigned 32 and 64 bit 1536 * integers. 1537 * 1538 * The canonical representation uses big endian convention, the same convention 1539 * as human-readable numbers (large digits first). 1540 * 1541 * This way, hash values can be written into a file or buffer, remaining 1542 * comparable across different systems. 1543 * 1544 * The following functions allow transformation of hash values to and from their 1545 * canonical format. 1546 */ 1547 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash) 1548 { 1549 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t)); 1550 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash); 1551 memcpy(dst, &hash, sizeof(*dst)); 1552 } 1553 1554 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src) 1555 { 1556 return XXH_readBE32(src); 1557 } 1558 1559 1560 #ifndef XXH_NO_LONG_LONG 1561 1562 /* ******************************************************************* 1563 * 64-bit hash functions 1564 *********************************************************************/ 1565 1566 /******* Memory access *******/ 1567 1568 typedef XXH64_hash_t xxh_u64; 1569 1570 #ifdef XXH_OLD_NAMES 1571 # define U64 xxh_u64 1572 #endif 1573 1574 /*! 1575 * XXH_REROLL_XXH64: 1576 * Whether to reroll the XXH64_finalize() loop. 1577 * 1578 * Just like XXH32, we can unroll the XXH64_finalize() loop. This can be a 1579 * performance gain on 64-bit hosts, as only one jump is required. 1580 * 1581 * However, on 32-bit hosts, because arithmetic needs to be done with two 32-bit 1582 * registers, and 64-bit arithmetic needs to be simulated, it isn't beneficial 1583 * to unroll. The code becomes ridiculously large (the largest function in the 1584 * binary on i386!), and rerolling it saves anywhere from 3kB to 20kB. It is 1585 * also slightly faster because it fits into cache better and is more likely 1586 * to be inlined by the compiler. 1587 * 1588 * If XXH_REROLL is defined, this is ignored and the loop is always rerolled. 1589 */ 1590 #ifndef XXH_REROLL_XXH64 1591 # if (defined(__ILP32__) || defined(_ILP32)) /* ILP32 is often defined on 32-bit GCC family */ \ 1592 || !(defined(__x86_64__) || defined(_M_X64) || defined(_M_AMD64) /* x86-64 */ \ 1593 || defined(_M_ARM64) || defined(__aarch64__) || defined(__arm64__) /* aarch64 */ \ 1594 || defined(__PPC64__) || defined(__PPC64LE__) || defined(__ppc64__) || defined(__powerpc64__) /* ppc64 */ \ 1595 || defined(__mips64__) || defined(__mips64)) /* mips64 */ \ 1596 || (!defined(SIZE_MAX) || SIZE_MAX < ULLONG_MAX) /* check limits */ 1597 # define XXH_REROLL_XXH64 1 1598 # else 1599 # define XXH_REROLL_XXH64 0 1600 # endif 1601 #endif /* !defined(XXH_REROLL_XXH64) */ 1602 1603 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3)) 1604 /* 1605 * Manual byteshift. Best for old compilers which don't inline memcpy. 1606 * We actually directly use XXH_readLE64 and XXH_readBE64. 1607 */ 1608 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2)) 1609 1610 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */ 1611 static xxh_u64 XXH_read64(const void* memPtr) { return *(const xxh_u64*) memPtr; } 1612 1613 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1)) 1614 1615 /* 1616 * __pack instructions are safer, but compiler specific, hence potentially 1617 * problematic for some compilers. 1618 * 1619 * Currently only defined for GCC and ICC. 1620 */ 1621 #ifdef XXH_OLD_NAMES 1622 typedef union { xxh_u32 u32; xxh_u64 u64; } __attribute__((packed)) unalign64; 1623 #endif 1624 static xxh_u64 XXH_read64(const void* ptr) 1625 { 1626 typedef union { xxh_u32 u32; xxh_u64 u64; } __attribute__((packed)) xxh_unalign64; 1627 return ((const xxh_unalign64*)ptr)->u64; 1628 } 1629 1630 #else 1631 1632 /* 1633 * Portable and safe solution. Generally efficient. 1634 * see: https://stackoverflow.com/a/32095106/646947 1635 */ 1636 static xxh_u64 XXH_read64(const void* memPtr) 1637 { 1638 xxh_u64 val; 1639 memcpy(&val, memPtr, sizeof(val)); 1640 return val; 1641 } 1642 1643 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */ 1644 1645 #if defined(_MSC_VER) /* Visual Studio */ 1646 # define XXH_swap64 _byteswap_uint64 1647 #elif XXH_GCC_VERSION >= 403 1648 # define XXH_swap64 __builtin_bswap64 1649 #else 1650 static xxh_u64 XXH_swap64 (xxh_u64 x) 1651 { 1652 return ((x << 56) & 0xff00000000000000ULL) | 1653 ((x << 40) & 0x00ff000000000000ULL) | 1654 ((x << 24) & 0x0000ff0000000000ULL) | 1655 ((x << 8) & 0x000000ff00000000ULL) | 1656 ((x >> 8) & 0x00000000ff000000ULL) | 1657 ((x >> 24) & 0x0000000000ff0000ULL) | 1658 ((x >> 40) & 0x000000000000ff00ULL) | 1659 ((x >> 56) & 0x00000000000000ffULL); 1660 } 1661 #endif 1662 1663 1664 /* XXH_FORCE_MEMORY_ACCESS==3 is an endian-independent byteshift load. */ 1665 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==3)) 1666 1667 XXH_FORCE_INLINE xxh_u64 XXH_readLE64(const void* memPtr) 1668 { 1669 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr; 1670 return bytePtr[0] 1671 | ((xxh_u64)bytePtr[1] << 8) 1672 | ((xxh_u64)bytePtr[2] << 16) 1673 | ((xxh_u64)bytePtr[3] << 24) 1674 | ((xxh_u64)bytePtr[4] << 32) 1675 | ((xxh_u64)bytePtr[5] << 40) 1676 | ((xxh_u64)bytePtr[6] << 48) 1677 | ((xxh_u64)bytePtr[7] << 56); 1678 } 1679 1680 XXH_FORCE_INLINE xxh_u64 XXH_readBE64(const void* memPtr) 1681 { 1682 const xxh_u8* bytePtr = (const xxh_u8 *)memPtr; 1683 return bytePtr[7] 1684 | ((xxh_u64)bytePtr[6] << 8) 1685 | ((xxh_u64)bytePtr[5] << 16) 1686 | ((xxh_u64)bytePtr[4] << 24) 1687 | ((xxh_u64)bytePtr[3] << 32) 1688 | ((xxh_u64)bytePtr[2] << 40) 1689 | ((xxh_u64)bytePtr[1] << 48) 1690 | ((xxh_u64)bytePtr[0] << 56); 1691 } 1692 1693 #else 1694 XXH_FORCE_INLINE xxh_u64 XXH_readLE64(const void* ptr) 1695 { 1696 return XXH_CPU_LITTLE_ENDIAN ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr)); 1697 } 1698 1699 static xxh_u64 XXH_readBE64(const void* ptr) 1700 { 1701 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr); 1702 } 1703 #endif 1704 1705 XXH_FORCE_INLINE xxh_u64 1706 XXH_readLE64_align(const void* ptr, XXH_alignment align) 1707 { 1708 if (align==XXH_unaligned) 1709 return XXH_readLE64(ptr); 1710 else 1711 return XXH_CPU_LITTLE_ENDIAN ? *(const xxh_u64*)ptr : XXH_swap64(*(const xxh_u64*)ptr); 1712 } 1713 1714 1715 /******* xxh64 *******/ 1716 1717 static const xxh_u64 XXH_PRIME64_1 = 0x9E3779B185EBCA87ULL; /* 0b1001111000110111011110011011000110000101111010111100101010000111 */ 1718 static const xxh_u64 XXH_PRIME64_2 = 0xC2B2AE3D27D4EB4FULL; /* 0b1100001010110010101011100011110100100111110101001110101101001111 */ 1719 static const xxh_u64 XXH_PRIME64_3 = 0x165667B19E3779F9ULL; /* 0b0001011001010110011001111011000110011110001101110111100111111001 */ 1720 static const xxh_u64 XXH_PRIME64_4 = 0x85EBCA77C2B2AE63ULL; /* 0b1000010111101011110010100111011111000010101100101010111001100011 */ 1721 static const xxh_u64 XXH_PRIME64_5 = 0x27D4EB2F165667C5ULL; /* 0b0010011111010100111010110010111100010110010101100110011111000101 */ 1722 1723 #ifdef XXH_OLD_NAMES 1724 # define PRIME64_1 XXH_PRIME64_1 1725 # define PRIME64_2 XXH_PRIME64_2 1726 # define PRIME64_3 XXH_PRIME64_3 1727 # define PRIME64_4 XXH_PRIME64_4 1728 # define PRIME64_5 XXH_PRIME64_5 1729 #endif 1730 1731 static xxh_u64 XXH64_round(xxh_u64 acc, xxh_u64 input) 1732 { 1733 acc += input * XXH_PRIME64_2; 1734 acc = XXH_rotl64(acc, 31); 1735 acc *= XXH_PRIME64_1; 1736 return acc; 1737 } 1738 1739 static xxh_u64 XXH64_mergeRound(xxh_u64 acc, xxh_u64 val) 1740 { 1741 val = XXH64_round(0, val); 1742 acc ^= val; 1743 acc = acc * XXH_PRIME64_1 + XXH_PRIME64_4; 1744 return acc; 1745 } 1746 1747 static xxh_u64 XXH64_avalanche(xxh_u64 h64) 1748 { 1749 h64 ^= h64 >> 33; 1750 h64 *= XXH_PRIME64_2; 1751 h64 ^= h64 >> 29; 1752 h64 *= XXH_PRIME64_3; 1753 h64 ^= h64 >> 32; 1754 return h64; 1755 } 1756 1757 1758 #define XXH_get64bits(p) XXH_readLE64_align(p, align) 1759 1760 static xxh_u64 1761 XXH64_finalize(xxh_u64 h64, const xxh_u8* ptr, size_t len, XXH_alignment align) 1762 { 1763 #define XXH_PROCESS1_64 do { \ 1764 h64 ^= (*ptr++) * XXH_PRIME64_5; \ 1765 h64 = XXH_rotl64(h64, 11) * XXH_PRIME64_1; \ 1766 } while (0) 1767 1768 #define XXH_PROCESS4_64 do { \ 1769 h64 ^= (xxh_u64)(XXH_get32bits(ptr)) * XXH_PRIME64_1; \ 1770 ptr += 4; \ 1771 h64 = XXH_rotl64(h64, 23) * XXH_PRIME64_2 + XXH_PRIME64_3; \ 1772 } while (0) 1773 1774 #define XXH_PROCESS8_64 do { \ 1775 xxh_u64 const k1 = XXH64_round(0, XXH_get64bits(ptr)); \ 1776 ptr += 8; \ 1777 h64 ^= k1; \ 1778 h64 = XXH_rotl64(h64,27) * XXH_PRIME64_1 + XXH_PRIME64_4; \ 1779 } while (0) 1780 1781 /* Rerolled version for 32-bit targets is faster and much smaller. */ 1782 if (XXH_REROLL || XXH_REROLL_XXH64) { 1783 len &= 31; 1784 while (len >= 8) { 1785 XXH_PROCESS8_64; 1786 len -= 8; 1787 } 1788 if (len >= 4) { 1789 XXH_PROCESS4_64; 1790 len -= 4; 1791 } 1792 while (len > 0) { 1793 XXH_PROCESS1_64; 1794 --len; 1795 } 1796 return XXH64_avalanche(h64); 1797 } else { 1798 switch(len & 31) { 1799 case 24: XXH_PROCESS8_64; 1800 /* fallthrough */ 1801 case 16: XXH_PROCESS8_64; 1802 /* fallthrough */ 1803 case 8: XXH_PROCESS8_64; 1804 return XXH64_avalanche(h64); 1805 1806 case 28: XXH_PROCESS8_64; 1807 /* fallthrough */ 1808 case 20: XXH_PROCESS8_64; 1809 /* fallthrough */ 1810 case 12: XXH_PROCESS8_64; 1811 /* fallthrough */ 1812 case 4: XXH_PROCESS4_64; 1813 return XXH64_avalanche(h64); 1814 1815 case 25: XXH_PROCESS8_64; 1816 /* fallthrough */ 1817 case 17: XXH_PROCESS8_64; 1818 /* fallthrough */ 1819 case 9: XXH_PROCESS8_64; 1820 XXH_PROCESS1_64; 1821 return XXH64_avalanche(h64); 1822 1823 case 29: XXH_PROCESS8_64; 1824 /* fallthrough */ 1825 case 21: XXH_PROCESS8_64; 1826 /* fallthrough */ 1827 case 13: XXH_PROCESS8_64; 1828 /* fallthrough */ 1829 case 5: XXH_PROCESS4_64; 1830 XXH_PROCESS1_64; 1831 return XXH64_avalanche(h64); 1832 1833 case 26: XXH_PROCESS8_64; 1834 /* fallthrough */ 1835 case 18: XXH_PROCESS8_64; 1836 /* fallthrough */ 1837 case 10: XXH_PROCESS8_64; 1838 XXH_PROCESS1_64; 1839 XXH_PROCESS1_64; 1840 return XXH64_avalanche(h64); 1841 1842 case 30: XXH_PROCESS8_64; 1843 /* fallthrough */ 1844 case 22: XXH_PROCESS8_64; 1845 /* fallthrough */ 1846 case 14: XXH_PROCESS8_64; 1847 /* fallthrough */ 1848 case 6: XXH_PROCESS4_64; 1849 XXH_PROCESS1_64; 1850 XXH_PROCESS1_64; 1851 return XXH64_avalanche(h64); 1852 1853 case 27: XXH_PROCESS8_64; 1854 /* fallthrough */ 1855 case 19: XXH_PROCESS8_64; 1856 /* fallthrough */ 1857 case 11: XXH_PROCESS8_64; 1858 XXH_PROCESS1_64; 1859 XXH_PROCESS1_64; 1860 XXH_PROCESS1_64; 1861 return XXH64_avalanche(h64); 1862 1863 case 31: XXH_PROCESS8_64; 1864 /* fallthrough */ 1865 case 23: XXH_PROCESS8_64; 1866 /* fallthrough */ 1867 case 15: XXH_PROCESS8_64; 1868 /* fallthrough */ 1869 case 7: XXH_PROCESS4_64; 1870 /* fallthrough */ 1871 case 3: XXH_PROCESS1_64; 1872 /* fallthrough */ 1873 case 2: XXH_PROCESS1_64; 1874 /* fallthrough */ 1875 case 1: XXH_PROCESS1_64; 1876 /* fallthrough */ 1877 case 0: return XXH64_avalanche(h64); 1878 } 1879 } 1880 /* impossible to reach */ 1881 XXH_ASSERT(0); 1882 return 0; /* unreachable, but some compilers complain without it */ 1883 } 1884 1885 #ifdef XXH_OLD_NAMES 1886 # define PROCESS1_64 XXH_PROCESS1_64 1887 # define PROCESS4_64 XXH_PROCESS4_64 1888 # define PROCESS8_64 XXH_PROCESS8_64 1889 #else 1890 # undef XXH_PROCESS1_64 1891 # undef XXH_PROCESS4_64 1892 # undef XXH_PROCESS8_64 1893 #endif 1894 1895 XXH_FORCE_INLINE xxh_u64 1896 XXH64_endian_align(const xxh_u8* input, size_t len, xxh_u64 seed, XXH_alignment align) 1897 { 1898 const xxh_u8* bEnd = input + len; 1899 xxh_u64 h64; 1900 1901 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 1902 if (input==NULL) { 1903 len=0; 1904 bEnd=input=(const xxh_u8*)(size_t)32; 1905 } 1906 #endif 1907 1908 if (len>=32) { 1909 const xxh_u8* const limit = bEnd - 32; 1910 xxh_u64 v1 = seed + XXH_PRIME64_1 + XXH_PRIME64_2; 1911 xxh_u64 v2 = seed + XXH_PRIME64_2; 1912 xxh_u64 v3 = seed + 0; 1913 xxh_u64 v4 = seed - XXH_PRIME64_1; 1914 1915 do { 1916 v1 = XXH64_round(v1, XXH_get64bits(input)); input+=8; 1917 v2 = XXH64_round(v2, XXH_get64bits(input)); input+=8; 1918 v3 = XXH64_round(v3, XXH_get64bits(input)); input+=8; 1919 v4 = XXH64_round(v4, XXH_get64bits(input)); input+=8; 1920 } while (input<=limit); 1921 1922 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 1923 h64 = XXH64_mergeRound(h64, v1); 1924 h64 = XXH64_mergeRound(h64, v2); 1925 h64 = XXH64_mergeRound(h64, v3); 1926 h64 = XXH64_mergeRound(h64, v4); 1927 1928 } else { 1929 h64 = seed + XXH_PRIME64_5; 1930 } 1931 1932 h64 += (xxh_u64) len; 1933 1934 return XXH64_finalize(h64, input, len, align); 1935 } 1936 1937 1938 XXH_PUBLIC_API XXH64_hash_t XXH64 (const void* input, size_t len, XXH64_hash_t seed) 1939 { 1940 #if 0 1941 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */ 1942 XXH64_state_t state; 1943 XXH64_reset(&state, seed); 1944 XXH64_update(&state, (const xxh_u8*)input, len); 1945 return XXH64_digest(&state); 1946 1947 #else 1948 1949 if (XXH_FORCE_ALIGN_CHECK) { 1950 if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */ 1951 return XXH64_endian_align((const xxh_u8*)input, len, seed, XXH_aligned); 1952 } } 1953 1954 return XXH64_endian_align((const xxh_u8*)input, len, seed, XXH_unaligned); 1955 1956 #endif 1957 } 1958 1959 /******* Hash Streaming *******/ 1960 1961 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void) 1962 { 1963 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t)); 1964 } 1965 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr) 1966 { 1967 XXH_free(statePtr); 1968 return XXH_OK; 1969 } 1970 1971 XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t* dstState, const XXH64_state_t* srcState) 1972 { 1973 memcpy(dstState, srcState, sizeof(*dstState)); 1974 } 1975 1976 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, XXH64_hash_t seed) 1977 { 1978 XXH64_state_t state; /* use a local state to memcpy() in order to avoid strict-aliasing warnings */ 1979 memset(&state, 0, sizeof(state)); 1980 state.v1 = seed + XXH_PRIME64_1 + XXH_PRIME64_2; 1981 state.v2 = seed + XXH_PRIME64_2; 1982 state.v3 = seed + 0; 1983 state.v4 = seed - XXH_PRIME64_1; 1984 /* do not write into reserved64, might be removed in a future version */ 1985 memcpy(statePtr, &state, sizeof(state) - sizeof(state.reserved64)); 1986 return XXH_OK; 1987 } 1988 1989 XXH_PUBLIC_API XXH_errorcode 1990 XXH64_update (XXH64_state_t* state, const void* input, size_t len) 1991 { 1992 if (input==NULL) 1993 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 1994 return XXH_OK; 1995 #else 1996 return XXH_ERROR; 1997 #endif 1998 1999 { const xxh_u8* p = (const xxh_u8*)input; 2000 const xxh_u8* const bEnd = p + len; 2001 2002 state->total_len += len; 2003 2004 if (state->memsize + len < 32) { /* fill in tmp buffer */ 2005 XXH_memcpy(((xxh_u8*)state->mem64) + state->memsize, input, len); 2006 state->memsize += (xxh_u32)len; 2007 return XXH_OK; 2008 } 2009 2010 if (state->memsize) { /* tmp buffer is full */ 2011 XXH_memcpy(((xxh_u8*)state->mem64) + state->memsize, input, 32-state->memsize); 2012 state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0)); 2013 state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1)); 2014 state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2)); 2015 state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3)); 2016 p += 32-state->memsize; 2017 state->memsize = 0; 2018 } 2019 2020 if (p+32 <= bEnd) { 2021 const xxh_u8* const limit = bEnd - 32; 2022 xxh_u64 v1 = state->v1; 2023 xxh_u64 v2 = state->v2; 2024 xxh_u64 v3 = state->v3; 2025 xxh_u64 v4 = state->v4; 2026 2027 do { 2028 v1 = XXH64_round(v1, XXH_readLE64(p)); p+=8; 2029 v2 = XXH64_round(v2, XXH_readLE64(p)); p+=8; 2030 v3 = XXH64_round(v3, XXH_readLE64(p)); p+=8; 2031 v4 = XXH64_round(v4, XXH_readLE64(p)); p+=8; 2032 } while (p<=limit); 2033 2034 state->v1 = v1; 2035 state->v2 = v2; 2036 state->v3 = v3; 2037 state->v4 = v4; 2038 } 2039 2040 if (p < bEnd) { 2041 XXH_memcpy(state->mem64, p, (size_t)(bEnd-p)); 2042 state->memsize = (unsigned)(bEnd-p); 2043 } 2044 } 2045 2046 return XXH_OK; 2047 } 2048 2049 2050 XXH_PUBLIC_API XXH64_hash_t XXH64_digest (const XXH64_state_t* state) 2051 { 2052 xxh_u64 h64; 2053 2054 if (state->total_len >= 32) { 2055 xxh_u64 const v1 = state->v1; 2056 xxh_u64 const v2 = state->v2; 2057 xxh_u64 const v3 = state->v3; 2058 xxh_u64 const v4 = state->v4; 2059 2060 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18); 2061 h64 = XXH64_mergeRound(h64, v1); 2062 h64 = XXH64_mergeRound(h64, v2); 2063 h64 = XXH64_mergeRound(h64, v3); 2064 h64 = XXH64_mergeRound(h64, v4); 2065 } else { 2066 h64 = state->v3 /*seed*/ + XXH_PRIME64_5; 2067 } 2068 2069 h64 += (xxh_u64) state->total_len; 2070 2071 return XXH64_finalize(h64, (const xxh_u8*)state->mem64, (size_t)state->total_len, XXH_aligned); 2072 } 2073 2074 2075 /******* Canonical representation *******/ 2076 2077 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash) 2078 { 2079 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t)); 2080 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash); 2081 memcpy(dst, &hash, sizeof(*dst)); 2082 } 2083 2084 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src) 2085 { 2086 return XXH_readBE64(src); 2087 } 2088 2089 2090 2091 /* ********************************************************************* 2092 * XXH3 2093 * New generation hash designed for speed on small keys and vectorization 2094 ************************************************************************ */ 2095 2096 /* === Compiler specifics === */ 2097 2098 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* >= C99 */ 2099 # define XXH_RESTRICT restrict 2100 #else 2101 /* Note: it might be useful to define __restrict or __restrict__ for some C++ compilers */ 2102 # define XXH_RESTRICT /* disable */ 2103 #endif 2104 2105 #if (defined(__GNUC__) && (__GNUC__ >= 3)) \ 2106 || (defined(__INTEL_COMPILER) && (__INTEL_COMPILER >= 800)) \ 2107 || defined(__clang__) 2108 # define XXH_likely(x) __builtin_expect(x, 1) 2109 # define XXH_unlikely(x) __builtin_expect(x, 0) 2110 #else 2111 # define XXH_likely(x) (x) 2112 # define XXH_unlikely(x) (x) 2113 #endif 2114 2115 #if defined(__GNUC__) 2116 # if defined(__AVX2__) 2117 # include <immintrin.h> 2118 # elif defined(__SSE2__) 2119 # include <emmintrin.h> 2120 # elif defined(__ARM_NEON__) || defined(__ARM_NEON) 2121 # define inline __inline__ /* circumvent a clang bug */ 2122 # include <arm_neon.h> 2123 # undef inline 2124 # endif 2125 #elif defined(_MSC_VER) 2126 # include <intrin.h> 2127 #endif 2128 2129 /* 2130 * One goal of XXH3 is to make it fast on both 32-bit and 64-bit, while 2131 * remaining a true 64-bit/128-bit hash function. 2132 * 2133 * This is done by prioritizing a subset of 64-bit operations that can be 2134 * emulated without too many steps on the average 32-bit machine. 2135 * 2136 * For example, these two lines seem similar, and run equally fast on 64-bit: 2137 * 2138 * xxh_u64 x; 2139 * x ^= (x >> 47); // good 2140 * x ^= (x >> 13); // bad 2141 * 2142 * However, to a 32-bit machine, there is a major difference. 2143 * 2144 * x ^= (x >> 47) looks like this: 2145 * 2146 * x.lo ^= (x.hi >> (47 - 32)); 2147 * 2148 * while x ^= (x >> 13) looks like this: 2149 * 2150 * // note: funnel shifts are not usually cheap. 2151 * x.lo ^= (x.lo >> 13) | (x.hi << (32 - 13)); 2152 * x.hi ^= (x.hi >> 13); 2153 * 2154 * The first one is significantly faster than the second, simply because the 2155 * shift is larger than 32. This means: 2156 * - All the bits we need are in the upper 32 bits, so we can ignore the lower 2157 * 32 bits in the shift. 2158 * - The shift result will always fit in the lower 32 bits, and therefore, 2159 * we can ignore the upper 32 bits in the xor. 2160 * 2161 * Thanks to this optimization, XXH3 only requires these features to be efficient: 2162 * 2163 * - Usable unaligned access 2164 * - A 32-bit or 64-bit ALU 2165 * - If 32-bit, a decent ADC instruction 2166 * - A 32 or 64-bit multiply with a 64-bit result 2167 * - For the 128-bit variant, a decent byteswap helps short inputs. 2168 * 2169 * The first two are already required by XXH32, and almost all 32-bit and 64-bit 2170 * platforms which can run XXH32 can run XXH3 efficiently. 2171 * 2172 * Thumb-1, the classic 16-bit only subset of ARM's instruction set, is one 2173 * notable exception. 2174 * 2175 * First of all, Thumb-1 lacks support for the UMULL instruction which 2176 * performs the important long multiply. This means numerous __aeabi_lmul 2177 * calls. 2178 * 2179 * Second of all, the 8 functional registers are just not enough. 2180 * Setup for __aeabi_lmul, byteshift loads, pointers, and all arithmetic need 2181 * Lo registers, and this shuffling results in thousands more MOVs than A32. 2182 * 2183 * A32 and T32 don't have this limitation. They can access all 14 registers, 2184 * do a 32->64 multiply with UMULL, and the flexible operand allowing free 2185 * shifts is helpful, too. 2186 * 2187 * Therefore, we do a quick sanity check. 2188 * 2189 * If compiling Thumb-1 for a target which supports ARM instructions, we will 2190 * emit a warning, as it is not a "sane" platform to compile for. 2191 * 2192 * Usually, if this happens, it is because of an accident and you probably need 2193 * to specify -march, as you likely meant to compile for a newer architecture. 2194 * 2195 * Credit: large sections of the vectorial and asm source code paths 2196 * have been contributed by @easyaspi314 2197 */ 2198 #if defined(__thumb__) && !defined(__thumb2__) && defined(__ARM_ARCH_ISA_ARM) 2199 # warning "XXH3 is highly inefficient without ARM or Thumb-2." 2200 #endif 2201 2202 /* ========================================== 2203 * Vectorization detection 2204 * ========================================== */ 2205 #define XXH_SCALAR 0 /* Portable scalar version */ 2206 #define XXH_SSE2 1 /* SSE2 for Pentium 4 and all x86_64 */ 2207 #define XXH_AVX2 2 /* AVX2 for Haswell and Bulldozer */ 2208 #define XXH_AVX512 3 /* AVX512 for Skylake and Icelake */ 2209 #define XXH_NEON 4 /* NEON for most ARMv7-A and all AArch64 */ 2210 #define XXH_VSX 5 /* VSX and ZVector for POWER8/z13 */ 2211 2212 #ifndef XXH_VECTOR /* can be defined on command line */ 2213 # if defined(__AVX512F__) 2214 # define XXH_VECTOR XXH_AVX512 2215 # elif defined(__AVX2__) 2216 # define XXH_VECTOR XXH_AVX2 2217 # elif defined(__SSE2__) || defined(_M_AMD64) || defined(_M_X64) || (defined(_M_IX86_FP) && (_M_IX86_FP == 2)) 2218 # define XXH_VECTOR XXH_SSE2 2219 # elif defined(__GNUC__) /* msvc support maybe later */ \ 2220 && (defined(__ARM_NEON__) || defined(__ARM_NEON)) \ 2221 && (defined(__LITTLE_ENDIAN__) /* We only support little endian NEON */ \ 2222 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)) 2223 # define XXH_VECTOR XXH_NEON 2224 # elif (defined(__PPC64__) && defined(__POWER8_VECTOR__)) \ 2225 || (defined(__s390x__) && defined(__VEC__)) \ 2226 && defined(__GNUC__) /* TODO: IBM XL */ 2227 # define XXH_VECTOR XXH_VSX 2228 # else 2229 # define XXH_VECTOR XXH_SCALAR 2230 # endif 2231 #endif 2232 2233 /* 2234 * Controls the alignment of the accumulator, 2235 * for compatibility with aligned vector loads, which are usually faster. 2236 */ 2237 #ifndef XXH_ACC_ALIGN 2238 # if defined(XXH_X86DISPATCH) 2239 # define XXH_ACC_ALIGN 64 /* for compatibility with avx512 */ 2240 # elif XXH_VECTOR == XXH_SCALAR /* scalar */ 2241 # define XXH_ACC_ALIGN 8 2242 # elif XXH_VECTOR == XXH_SSE2 /* sse2 */ 2243 # define XXH_ACC_ALIGN 16 2244 # elif XXH_VECTOR == XXH_AVX2 /* avx2 */ 2245 # define XXH_ACC_ALIGN 32 2246 # elif XXH_VECTOR == XXH_NEON /* neon */ 2247 # define XXH_ACC_ALIGN 16 2248 # elif XXH_VECTOR == XXH_VSX /* vsx */ 2249 # define XXH_ACC_ALIGN 16 2250 # elif XXH_VECTOR == XXH_AVX512 /* avx512 */ 2251 # define XXH_ACC_ALIGN 64 2252 # endif 2253 #endif 2254 2255 #if defined(XXH_X86DISPATCH) || XXH_VECTOR == XXH_SSE2 \ 2256 || XXH_VECTOR == XXH_AVX2 || XXH_VECTOR == XXH_AVX512 2257 # define XXH_SEC_ALIGN XXH_ACC_ALIGN 2258 #else 2259 # define XXH_SEC_ALIGN 8 2260 #endif 2261 2262 /* 2263 * UGLY HACK: 2264 * GCC usually generates the best code with -O3 for xxHash. 2265 * 2266 * However, when targeting AVX2, it is overzealous in its unrolling resulting 2267 * in code roughly 3/4 the speed of Clang. 2268 * 2269 * There are other issues, such as GCC splitting _mm256_loadu_si256 into 2270 * _mm_loadu_si128 + _mm256_inserti128_si256. This is an optimization which 2271 * only applies to Sandy and Ivy Bridge... which don't even support AVX2. 2272 * 2273 * That is why when compiling the AVX2 version, it is recommended to use either 2274 * -O2 -mavx2 -march=haswell 2275 * or 2276 * -O2 -mavx2 -mno-avx256-split-unaligned-load 2277 * for decent performance, or to use Clang instead. 2278 * 2279 * Fortunately, we can control the first one with a pragma that forces GCC into 2280 * -O2, but the other one we can't control without "failed to inline always 2281 * inline function due to target mismatch" warnings. 2282 */ 2283 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \ 2284 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \ 2285 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */ 2286 # pragma GCC push_options 2287 # pragma GCC optimize("-O2") 2288 #endif 2289 2290 2291 #if XXH_VECTOR == XXH_NEON 2292 /* 2293 * NEON's setup for vmlal_u32 is a little more complicated than it is on 2294 * SSE2, AVX2, and VSX. 2295 * 2296 * While PMULUDQ and VMULEUW both perform a mask, VMLAL.U32 performs an upcast. 2297 * 2298 * To do the same operation, the 128-bit 'Q' register needs to be split into 2299 * two 64-bit 'D' registers, performing this operation:: 2300 * 2301 * [ a | b ] 2302 * | '---------. .--------' | 2303 * | x | 2304 * | .---------' '--------. | 2305 * [ a & 0xFFFFFFFF | b & 0xFFFFFFFF ],[ a >> 32 | b >> 32 ] 2306 * 2307 * Due to significant changes in aarch64, the fastest method for aarch64 is 2308 * completely different than the fastest method for ARMv7-A. 2309 * 2310 * ARMv7-A treats D registers as unions overlaying Q registers, so modifying 2311 * D11 will modify the high half of Q5. This is similar to how modifying AH 2312 * will only affect bits 8-15 of AX on x86. 2313 * 2314 * VZIP takes two registers, and puts even lanes in one register and odd lanes 2315 * in the other. 2316 * 2317 * On ARMv7-A, this strangely modifies both parameters in place instead of 2318 * taking the usual 3-operand form. 2319 * 2320 * Therefore, if we want to do this, we can simply use a D-form VZIP.32 on the 2321 * lower and upper halves of the Q register to end up with the high and low 2322 * halves where we want - all in one instruction. 2323 * 2324 * vzip.32 d10, d11 @ d10 = { d10[0], d11[0] }; d11 = { d10[1], d11[1] } 2325 * 2326 * Unfortunately we need inline assembly for this: Instructions modifying two 2327 * registers at once is not possible in GCC or Clang's IR, and they have to 2328 * create a copy. 2329 * 2330 * aarch64 requires a different approach. 2331 * 2332 * In order to make it easier to write a decent compiler for aarch64, many 2333 * quirks were removed, such as conditional execution. 2334 * 2335 * NEON was also affected by this. 2336 * 2337 * aarch64 cannot access the high bits of a Q-form register, and writes to a 2338 * D-form register zero the high bits, similar to how writes to W-form scalar 2339 * registers (or DWORD registers on x86_64) work. 2340 * 2341 * The formerly free vget_high intrinsics now require a vext (with a few 2342 * exceptions) 2343 * 2344 * Additionally, VZIP was replaced by ZIP1 and ZIP2, which are the equivalent 2345 * of PUNPCKL* and PUNPCKH* in SSE, respectively, in order to only modify one 2346 * operand. 2347 * 2348 * The equivalent of the VZIP.32 on the lower and upper halves would be this 2349 * mess: 2350 * 2351 * ext v2.4s, v0.4s, v0.4s, #2 // v2 = { v0[2], v0[3], v0[0], v0[1] } 2352 * zip1 v1.2s, v0.2s, v2.2s // v1 = { v0[0], v2[0] } 2353 * zip2 v0.2s, v0.2s, v1.2s // v0 = { v0[1], v2[1] } 2354 * 2355 * Instead, we use a literal downcast, vmovn_u64 (XTN), and vshrn_n_u64 (SHRN): 2356 * 2357 * shrn v1.2s, v0.2d, #32 // v1 = (uint32x2_t)(v0 >> 32); 2358 * xtn v0.2s, v0.2d // v0 = (uint32x2_t)(v0 & 0xFFFFFFFF); 2359 * 2360 * This is available on ARMv7-A, but is less efficient than a single VZIP.32. 2361 */ 2362 2363 /* 2364 * Function-like macro: 2365 * void XXH_SPLIT_IN_PLACE(uint64x2_t &in, uint32x2_t &outLo, uint32x2_t &outHi) 2366 * { 2367 * outLo = (uint32x2_t)(in & 0xFFFFFFFF); 2368 * outHi = (uint32x2_t)(in >> 32); 2369 * in = UNDEFINED; 2370 * } 2371 */ 2372 # if !defined(XXH_NO_VZIP_HACK) /* define to disable */ \ 2373 && defined(__GNUC__) \ 2374 && !defined(__aarch64__) && !defined(__arm64__) 2375 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \ 2376 do { \ 2377 /* Undocumented GCC/Clang operand modifier: %e0 = lower D half, %f0 = upper D half */ \ 2378 /* https://github.com/gcc-mirror/gcc/blob/38cf91e5/gcc/config/arm/arm.c#L22486 */ \ 2379 /* https://github.com/llvm-mirror/llvm/blob/2c4ca683/lib/Target/ARM/ARMAsmPrinter.cpp#L399 */ \ 2380 __asm__("vzip.32 %e0, %f0" : "+w" (in)); \ 2381 (outLo) = vget_low_u32 (vreinterpretq_u32_u64(in)); \ 2382 (outHi) = vget_high_u32(vreinterpretq_u32_u64(in)); \ 2383 } while (0) 2384 # else 2385 # define XXH_SPLIT_IN_PLACE(in, outLo, outHi) \ 2386 do { \ 2387 (outLo) = vmovn_u64 (in); \ 2388 (outHi) = vshrn_n_u64 ((in), 32); \ 2389 } while (0) 2390 # endif 2391 #endif /* XXH_VECTOR == XXH_NEON */ 2392 2393 /* 2394 * VSX and Z Vector helpers. 2395 * 2396 * This is very messy, and any pull requests to clean this up are welcome. 2397 * 2398 * There are a lot of problems with supporting VSX and s390x, due to 2399 * inconsistent intrinsics, spotty coverage, and multiple endiannesses. 2400 */ 2401 #if XXH_VECTOR == XXH_VSX 2402 # if defined(__s390x__) 2403 # include <s390intrin.h> 2404 # else 2405 /* gcc's altivec.h can have the unwanted consequence to unconditionally 2406 * #define bool, vector, and pixel keywords, 2407 * with bad consequences for programs already using these keywords for other purposes. 2408 * The paragraph defining these macros is skipped when __APPLE_ALTIVEC__ is defined. 2409 * __APPLE_ALTIVEC__ is _generally_ defined automatically by the compiler, 2410 * but it seems that, in some cases, it isn't. 2411 * Force the build macro to be defined, so that keywords are not altered. 2412 */ 2413 # if defined(__GNUC__) && !defined(__APPLE_ALTIVEC__) 2414 # define __APPLE_ALTIVEC__ 2415 # endif 2416 # include <altivec.h> 2417 # endif 2418 2419 typedef __vector unsigned long long xxh_u64x2; 2420 typedef __vector unsigned char xxh_u8x16; 2421 typedef __vector unsigned xxh_u32x4; 2422 2423 # ifndef XXH_VSX_BE 2424 # if defined(__BIG_ENDIAN__) \ 2425 || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__) 2426 # define XXH_VSX_BE 1 2427 # elif defined(__VEC_ELEMENT_REG_ORDER__) && __VEC_ELEMENT_REG_ORDER__ == __ORDER_BIG_ENDIAN__ 2428 # warning "-maltivec=be is not recommended. Please use native endianness." 2429 # define XXH_VSX_BE 1 2430 # else 2431 # define XXH_VSX_BE 0 2432 # endif 2433 # endif /* !defined(XXH_VSX_BE) */ 2434 2435 # if XXH_VSX_BE 2436 /* A wrapper for POWER9's vec_revb. */ 2437 # if defined(__POWER9_VECTOR__) || (defined(__clang__) && defined(__s390x__)) 2438 # define XXH_vec_revb vec_revb 2439 # else 2440 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_revb(xxh_u64x2 val) 2441 { 2442 xxh_u8x16 const vByteSwap = { 0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00, 2443 0x0F, 0x0E, 0x0D, 0x0C, 0x0B, 0x0A, 0x09, 0x08 }; 2444 return vec_perm(val, val, vByteSwap); 2445 } 2446 # endif 2447 # endif /* XXH_VSX_BE */ 2448 2449 /* 2450 * Performs an unaligned load and byte swaps it on big endian. 2451 */ 2452 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_loadu(const void *ptr) 2453 { 2454 xxh_u64x2 ret; 2455 memcpy(&ret, ptr, sizeof(xxh_u64x2)); 2456 # if XXH_VSX_BE 2457 ret = XXH_vec_revb(ret); 2458 # endif 2459 return ret; 2460 } 2461 2462 /* 2463 * vec_mulo and vec_mule are very problematic intrinsics on PowerPC 2464 * 2465 * These intrinsics weren't added until GCC 8, despite existing for a while, 2466 * and they are endian dependent. Also, their meaning swap depending on version. 2467 * */ 2468 # if defined(__s390x__) 2469 /* s390x is always big endian, no issue on this platform */ 2470 # define XXH_vec_mulo vec_mulo 2471 # define XXH_vec_mule vec_mule 2472 # elif defined(__clang__) && XXH_HAS_BUILTIN(__builtin_altivec_vmuleuw) 2473 /* Clang has a better way to control this, we can just use the builtin which doesn't swap. */ 2474 # define XXH_vec_mulo __builtin_altivec_vmulouw 2475 # define XXH_vec_mule __builtin_altivec_vmuleuw 2476 # else 2477 /* gcc needs inline assembly */ 2478 /* Adapted from https://github.com/google/highwayhash/blob/master/highwayhash/hh_vsx.h. */ 2479 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_mulo(xxh_u32x4 a, xxh_u32x4 b) 2480 { 2481 xxh_u64x2 result; 2482 __asm__("vmulouw %0, %1, %2" : "=v" (result) : "v" (a), "v" (b)); 2483 return result; 2484 } 2485 XXH_FORCE_INLINE xxh_u64x2 XXH_vec_mule(xxh_u32x4 a, xxh_u32x4 b) 2486 { 2487 xxh_u64x2 result; 2488 __asm__("vmuleuw %0, %1, %2" : "=v" (result) : "v" (a), "v" (b)); 2489 return result; 2490 } 2491 # endif /* XXH_vec_mulo, XXH_vec_mule */ 2492 #endif /* XXH_VECTOR == XXH_VSX */ 2493 2494 2495 /* prefetch 2496 * can be disabled, by declaring XXH_NO_PREFETCH build macro */ 2497 #if defined(XXH_NO_PREFETCH) 2498 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */ 2499 #else 2500 # if defined(_MSC_VER) && (defined(_M_X64) || defined(_M_I86)) /* _mm_prefetch() is not defined outside of x86/x64 */ 2501 # include <mmintrin.h> /* https://msdn.microsoft.com/fr-fr/library/84szxsww(v=vs.90).aspx */ 2502 # define XXH_PREFETCH(ptr) _mm_prefetch((const char*)(ptr), _MM_HINT_T0) 2503 # elif defined(__GNUC__) && ( (__GNUC__ >= 4) || ( (__GNUC__ == 3) && (__GNUC_MINOR__ >= 1) ) ) 2504 # define XXH_PREFETCH(ptr) __builtin_prefetch((ptr), 0 /* rw==read */, 3 /* locality */) 2505 # else 2506 # define XXH_PREFETCH(ptr) (void)(ptr) /* disabled */ 2507 # endif 2508 #endif /* XXH_NO_PREFETCH */ 2509 2510 2511 /* ========================================== 2512 * XXH3 default settings 2513 * ========================================== */ 2514 2515 #define XXH_SECRET_DEFAULT_SIZE 192 /* minimum XXH3_SECRET_SIZE_MIN */ 2516 2517 #if (XXH_SECRET_DEFAULT_SIZE < XXH3_SECRET_SIZE_MIN) 2518 # error "default keyset is not large enough" 2519 #endif 2520 2521 /* Pseudorandom secret taken directly from FARSH */ 2522 XXH_ALIGN(64) static const xxh_u8 XXH3_kSecret[XXH_SECRET_DEFAULT_SIZE] = { 2523 0xb8, 0xfe, 0x6c, 0x39, 0x23, 0xa4, 0x4b, 0xbe, 0x7c, 0x01, 0x81, 0x2c, 0xf7, 0x21, 0xad, 0x1c, 2524 0xde, 0xd4, 0x6d, 0xe9, 0x83, 0x90, 0x97, 0xdb, 0x72, 0x40, 0xa4, 0xa4, 0xb7, 0xb3, 0x67, 0x1f, 2525 0xcb, 0x79, 0xe6, 0x4e, 0xcc, 0xc0, 0xe5, 0x78, 0x82, 0x5a, 0xd0, 0x7d, 0xcc, 0xff, 0x72, 0x21, 2526 0xb8, 0x08, 0x46, 0x74, 0xf7, 0x43, 0x24, 0x8e, 0xe0, 0x35, 0x90, 0xe6, 0x81, 0x3a, 0x26, 0x4c, 2527 0x3c, 0x28, 0x52, 0xbb, 0x91, 0xc3, 0x00, 0xcb, 0x88, 0xd0, 0x65, 0x8b, 0x1b, 0x53, 0x2e, 0xa3, 2528 0x71, 0x64, 0x48, 0x97, 0xa2, 0x0d, 0xf9, 0x4e, 0x38, 0x19, 0xef, 0x46, 0xa9, 0xde, 0xac, 0xd8, 2529 0xa8, 0xfa, 0x76, 0x3f, 0xe3, 0x9c, 0x34, 0x3f, 0xf9, 0xdc, 0xbb, 0xc7, 0xc7, 0x0b, 0x4f, 0x1d, 2530 0x8a, 0x51, 0xe0, 0x4b, 0xcd, 0xb4, 0x59, 0x31, 0xc8, 0x9f, 0x7e, 0xc9, 0xd9, 0x78, 0x73, 0x64, 2531 0xea, 0xc5, 0xac, 0x83, 0x34, 0xd3, 0xeb, 0xc3, 0xc5, 0x81, 0xa0, 0xff, 0xfa, 0x13, 0x63, 0xeb, 2532 0x17, 0x0d, 0xdd, 0x51, 0xb7, 0xf0, 0xda, 0x49, 0xd3, 0x16, 0x55, 0x26, 0x29, 0xd4, 0x68, 0x9e, 2533 0x2b, 0x16, 0xbe, 0x58, 0x7d, 0x47, 0xa1, 0xfc, 0x8f, 0xf8, 0xb8, 0xd1, 0x7a, 0xd0, 0x31, 0xce, 2534 0x45, 0xcb, 0x3a, 0x8f, 0x95, 0x16, 0x04, 0x28, 0xaf, 0xd7, 0xfb, 0xca, 0xbb, 0x4b, 0x40, 0x7e, 2535 }; 2536 2537 2538 #ifdef XXH_OLD_NAMES 2539 # define kSecret XXH3_kSecret 2540 #endif 2541 2542 /* 2543 * Calculates a 32-bit to 64-bit long multiply. 2544 * 2545 * Wraps __emulu on MSVC x86 because it tends to call __allmul when it doesn't 2546 * need to (but it shouldn't need to anyways, it is about 7 instructions to do 2547 * a 64x64 multiply...). Since we know that this will _always_ emit MULL, we 2548 * use that instead of the normal method. 2549 * 2550 * If you are compiling for platforms like Thumb-1 and don't have a better option, 2551 * you may also want to write your own long multiply routine here. 2552 * 2553 * XXH_FORCE_INLINE xxh_u64 XXH_mult32to64(xxh_u64 x, xxh_u64 y) 2554 * { 2555 * return (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF); 2556 * } 2557 */ 2558 #if defined(_MSC_VER) && defined(_M_IX86) 2559 # include <intrin.h> 2560 # define XXH_mult32to64(x, y) __emulu((unsigned)(x), (unsigned)(y)) 2561 #else 2562 /* 2563 * Downcast + upcast is usually better than masking on older compilers like 2564 * GCC 4.2 (especially 32-bit ones), all without affecting newer compilers. 2565 * 2566 * The other method, (x & 0xFFFFFFFF) * (y & 0xFFFFFFFF), will AND both operands 2567 * and perform a full 64x64 multiply -- entirely redundant on 32-bit. 2568 */ 2569 # define XXH_mult32to64(x, y) ((xxh_u64)(xxh_u32)(x) * (xxh_u64)(xxh_u32)(y)) 2570 #endif 2571 2572 /* 2573 * Calculates a 64->128-bit long multiply. 2574 * 2575 * Uses __uint128_t and _umul128 if available, otherwise uses a scalar version. 2576 */ 2577 static XXH128_hash_t 2578 XXH_mult64to128(xxh_u64 lhs, xxh_u64 rhs) 2579 { 2580 /* 2581 * GCC/Clang __uint128_t method. 2582 * 2583 * On most 64-bit targets, GCC and Clang define a __uint128_t type. 2584 * This is usually the best way as it usually uses a native long 64-bit 2585 * multiply, such as MULQ on x86_64 or MUL + UMULH on aarch64. 2586 * 2587 * Usually. 2588 * 2589 * Despite being a 32-bit platform, Clang (and emscripten) define this type 2590 * despite not having the arithmetic for it. This results in a laggy 2591 * compiler builtin call which calculates a full 128-bit multiply. 2592 * In that case it is best to use the portable one. 2593 * https://github.com/Cyan4973/xxHash/issues/211#issuecomment-515575677 2594 */ 2595 #if defined(__GNUC__) && !defined(__wasm__) \ 2596 && defined(__SIZEOF_INT128__) \ 2597 || (defined(_INTEGRAL_MAX_BITS) && _INTEGRAL_MAX_BITS >= 128) 2598 2599 __uint128_t const product = (__uint128_t)lhs * (__uint128_t)rhs; 2600 XXH128_hash_t r128; 2601 r128.low64 = (xxh_u64)(product); 2602 r128.high64 = (xxh_u64)(product >> 64); 2603 return r128; 2604 2605 /* 2606 * MSVC for x64's _umul128 method. 2607 * 2608 * xxh_u64 _umul128(xxh_u64 Multiplier, xxh_u64 Multiplicand, xxh_u64 *HighProduct); 2609 * 2610 * This compiles to single operand MUL on x64. 2611 */ 2612 #elif defined(_M_X64) || defined(_M_IA64) 2613 2614 #ifndef _MSC_VER 2615 # pragma intrinsic(_umul128) 2616 #endif 2617 xxh_u64 product_high; 2618 xxh_u64 const product_low = _umul128(lhs, rhs, &product_high); 2619 XXH128_hash_t r128; 2620 r128.low64 = product_low; 2621 r128.high64 = product_high; 2622 return r128; 2623 2624 #else 2625 /* 2626 * Portable scalar method. Optimized for 32-bit and 64-bit ALUs. 2627 * 2628 * This is a fast and simple grade school multiply, which is shown below 2629 * with base 10 arithmetic instead of base 0x100000000. 2630 * 2631 * 9 3 // D2 lhs = 93 2632 * x 7 5 // D2 rhs = 75 2633 * ---------- 2634 * 1 5 // D2 lo_lo = (93 % 10) * (75 % 10) = 15 2635 * 4 5 | // D2 hi_lo = (93 / 10) * (75 % 10) = 45 2636 * 2 1 | // D2 lo_hi = (93 % 10) * (75 / 10) = 21 2637 * + 6 3 | | // D2 hi_hi = (93 / 10) * (75 / 10) = 63 2638 * --------- 2639 * 2 7 | // D2 cross = (15 / 10) + (45 % 10) + 21 = 27 2640 * + 6 7 | | // D2 upper = (27 / 10) + (45 / 10) + 63 = 67 2641 * --------- 2642 * 6 9 7 5 // D4 res = (27 * 10) + (15 % 10) + (67 * 100) = 6975 2643 * 2644 * The reasons for adding the products like this are: 2645 * 1. It avoids manual carry tracking. Just like how 2646 * (9 * 9) + 9 + 9 = 99, the same applies with this for UINT64_MAX. 2647 * This avoids a lot of complexity. 2648 * 2649 * 2. It hints for, and on Clang, compiles to, the powerful UMAAL 2650 * instruction available in ARM's Digital Signal Processing extension 2651 * in 32-bit ARMv6 and later, which is shown below: 2652 * 2653 * void UMAAL(xxh_u32 *RdLo, xxh_u32 *RdHi, xxh_u32 Rn, xxh_u32 Rm) 2654 * { 2655 * xxh_u64 product = (xxh_u64)*RdLo * (xxh_u64)*RdHi + Rn + Rm; 2656 * *RdLo = (xxh_u32)(product & 0xFFFFFFFF); 2657 * *RdHi = (xxh_u32)(product >> 32); 2658 * } 2659 * 2660 * This instruction was designed for efficient long multiplication, and 2661 * allows this to be calculated in only 4 instructions at speeds 2662 * comparable to some 64-bit ALUs. 2663 * 2664 * 3. It isn't terrible on other platforms. Usually this will be a couple 2665 * of 32-bit ADD/ADCs. 2666 */ 2667 2668 /* First calculate all of the cross products. */ 2669 xxh_u64 const lo_lo = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs & 0xFFFFFFFF); 2670 xxh_u64 const hi_lo = XXH_mult32to64(lhs >> 32, rhs & 0xFFFFFFFF); 2671 xxh_u64 const lo_hi = XXH_mult32to64(lhs & 0xFFFFFFFF, rhs >> 32); 2672 xxh_u64 const hi_hi = XXH_mult32to64(lhs >> 32, rhs >> 32); 2673 2674 /* Now add the products together. These will never overflow. */ 2675 xxh_u64 const cross = (lo_lo >> 32) + (hi_lo & 0xFFFFFFFF) + lo_hi; 2676 xxh_u64 const upper = (hi_lo >> 32) + (cross >> 32) + hi_hi; 2677 xxh_u64 const lower = (cross << 32) | (lo_lo & 0xFFFFFFFF); 2678 2679 XXH128_hash_t r128; 2680 r128.low64 = lower; 2681 r128.high64 = upper; 2682 return r128; 2683 #endif 2684 } 2685 2686 /* 2687 * Does a 64-bit to 128-bit multiply, then XOR folds it. 2688 * 2689 * The reason for the separate function is to prevent passing too many structs 2690 * around by value. This will hopefully inline the multiply, but we don't force it. 2691 */ 2692 static xxh_u64 2693 XXH3_mul128_fold64(xxh_u64 lhs, xxh_u64 rhs) 2694 { 2695 XXH128_hash_t product = XXH_mult64to128(lhs, rhs); 2696 return product.low64 ^ product.high64; 2697 } 2698 2699 /* Seems to produce slightly better code on GCC for some reason. */ 2700 XXH_FORCE_INLINE xxh_u64 XXH_xorshift64(xxh_u64 v64, int shift) 2701 { 2702 XXH_ASSERT(0 <= shift && shift < 64); 2703 return v64 ^ (v64 >> shift); 2704 } 2705 2706 /* 2707 * This is a fast avalanche stage, 2708 * suitable when input bits are already partially mixed 2709 */ 2710 static XXH64_hash_t XXH3_avalanche(xxh_u64 h64) 2711 { 2712 h64 = XXH_xorshift64(h64, 37); 2713 h64 *= 0x165667919E3779F9ULL; 2714 h64 = XXH_xorshift64(h64, 32); 2715 return h64; 2716 } 2717 2718 /* 2719 * This is a stronger avalanche, 2720 * inspired by Pelle Evensen's rrmxmx 2721 * preferable when input has not been previously mixed 2722 */ 2723 static XXH64_hash_t XXH3_rrmxmx(xxh_u64 h64, xxh_u64 len) 2724 { 2725 /* this mix is inspired by Pelle Evensen's rrmxmx */ 2726 h64 ^= XXH_rotl64(h64, 49) ^ XXH_rotl64(h64, 24); 2727 h64 *= 0x9FB21C651E98DF25ULL; 2728 h64 ^= (h64 >> 35) + len ; 2729 h64 *= 0x9FB21C651E98DF25ULL; 2730 return XXH_xorshift64(h64, 28); 2731 } 2732 2733 2734 /* ========================================== 2735 * Short keys 2736 * ========================================== 2737 * One of the shortcomings of XXH32 and XXH64 was that their performance was 2738 * sub-optimal on short lengths. It used an iterative algorithm which strongly 2739 * favored lengths that were a multiple of 4 or 8. 2740 * 2741 * Instead of iterating over individual inputs, we use a set of single shot 2742 * functions which piece together a range of lengths and operate in constant time. 2743 * 2744 * Additionally, the number of multiplies has been significantly reduced. This 2745 * reduces latency, especially when emulating 64-bit multiplies on 32-bit. 2746 * 2747 * Depending on the platform, this may or may not be faster than XXH32, but it 2748 * is almost guaranteed to be faster than XXH64. 2749 */ 2750 2751 /* 2752 * At very short lengths, there isn't enough input to fully hide secrets, or use 2753 * the entire secret. 2754 * 2755 * There is also only a limited amount of mixing we can do before significantly 2756 * impacting performance. 2757 * 2758 * Therefore, we use different sections of the secret and always mix two secret 2759 * samples with an XOR. This should have no effect on performance on the 2760 * seedless or withSeed variants because everything _should_ be constant folded 2761 * by modern compilers. 2762 * 2763 * The XOR mixing hides individual parts of the secret and increases entropy. 2764 * 2765 * This adds an extra layer of strength for custom secrets. 2766 */ 2767 XXH_FORCE_INLINE XXH64_hash_t 2768 XXH3_len_1to3_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 2769 { 2770 XXH_ASSERT(input != NULL); 2771 XXH_ASSERT(1 <= len && len <= 3); 2772 XXH_ASSERT(secret != NULL); 2773 /* 2774 * len = 1: combined = { input[0], 0x01, input[0], input[0] } 2775 * len = 2: combined = { input[1], 0x02, input[0], input[1] } 2776 * len = 3: combined = { input[2], 0x03, input[0], input[1] } 2777 */ 2778 { xxh_u8 const c1 = input[0]; 2779 xxh_u8 const c2 = input[len >> 1]; 2780 xxh_u8 const c3 = input[len - 1]; 2781 xxh_u32 const combined = ((xxh_u32)c1 << 16) | ((xxh_u32)c2 << 24) 2782 | ((xxh_u32)c3 << 0) | ((xxh_u32)len << 8); 2783 xxh_u64 const bitflip = (XXH_readLE32(secret) ^ XXH_readLE32(secret+4)) + seed; 2784 xxh_u64 const keyed = (xxh_u64)combined ^ bitflip; 2785 return XXH64_avalanche(keyed); 2786 } 2787 } 2788 2789 XXH_FORCE_INLINE XXH64_hash_t 2790 XXH3_len_4to8_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 2791 { 2792 XXH_ASSERT(input != NULL); 2793 XXH_ASSERT(secret != NULL); 2794 XXH_ASSERT(4 <= len && len < 8); 2795 seed ^= (xxh_u64)XXH_swap32((xxh_u32)seed) << 32; 2796 { xxh_u32 const input1 = XXH_readLE32(input); 2797 xxh_u32 const input2 = XXH_readLE32(input + len - 4); 2798 xxh_u64 const bitflip = (XXH_readLE64(secret+8) ^ XXH_readLE64(secret+16)) - seed; 2799 xxh_u64 const input64 = input2 + (((xxh_u64)input1) << 32); 2800 xxh_u64 const keyed = input64 ^ bitflip; 2801 return XXH3_rrmxmx(keyed, len); 2802 } 2803 } 2804 2805 XXH_FORCE_INLINE XXH64_hash_t 2806 XXH3_len_9to16_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 2807 { 2808 XXH_ASSERT(input != NULL); 2809 XXH_ASSERT(secret != NULL); 2810 XXH_ASSERT(8 <= len && len <= 16); 2811 { xxh_u64 const bitflip1 = (XXH_readLE64(secret+24) ^ XXH_readLE64(secret+32)) + seed; 2812 xxh_u64 const bitflip2 = (XXH_readLE64(secret+40) ^ XXH_readLE64(secret+48)) - seed; 2813 xxh_u64 const input_lo = XXH_readLE64(input) ^ bitflip1; 2814 xxh_u64 const input_hi = XXH_readLE64(input + len - 8) ^ bitflip2; 2815 xxh_u64 const acc = len 2816 + XXH_swap64(input_lo) + input_hi 2817 + XXH3_mul128_fold64(input_lo, input_hi); 2818 return XXH3_avalanche(acc); 2819 } 2820 } 2821 2822 XXH_FORCE_INLINE XXH64_hash_t 2823 XXH3_len_0to16_64b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 2824 { 2825 XXH_ASSERT(len <= 16); 2826 { if (XXH_likely(len > 8)) return XXH3_len_9to16_64b(input, len, secret, seed); 2827 if (XXH_likely(len >= 4)) return XXH3_len_4to8_64b(input, len, secret, seed); 2828 if (len) return XXH3_len_1to3_64b(input, len, secret, seed); 2829 return XXH64_avalanche(seed ^ (XXH_readLE64(secret+56) ^ XXH_readLE64(secret+64))); 2830 } 2831 } 2832 2833 /* 2834 * DISCLAIMER: There are known *seed-dependent* multicollisions here due to 2835 * multiplication by zero, affecting hashes of lengths 17 to 240. 2836 * 2837 * However, they are very unlikely. 2838 * 2839 * Keep this in mind when using the unseeded XXH3_64bits() variant: As with all 2840 * unseeded non-cryptographic hashes, it does not attempt to defend itself 2841 * against specially crafted inputs, only random inputs. 2842 * 2843 * Compared to classic UMAC where a 1 in 2^31 chance of 4 consecutive bytes 2844 * cancelling out the secret is taken an arbitrary number of times (addressed 2845 * in XXH3_accumulate_512), this collision is very unlikely with random inputs 2846 * and/or proper seeding: 2847 * 2848 * This only has a 1 in 2^63 chance of 8 consecutive bytes cancelling out, in a 2849 * function that is only called up to 16 times per hash with up to 240 bytes of 2850 * input. 2851 * 2852 * This is not too bad for a non-cryptographic hash function, especially with 2853 * only 64 bit outputs. 2854 * 2855 * The 128-bit variant (which trades some speed for strength) is NOT affected 2856 * by this, although it is always a good idea to use a proper seed if you care 2857 * about strength. 2858 */ 2859 XXH_FORCE_INLINE xxh_u64 XXH3_mix16B(const xxh_u8* XXH_RESTRICT input, 2860 const xxh_u8* XXH_RESTRICT secret, xxh_u64 seed64) 2861 { 2862 #if defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \ 2863 && defined(__i386__) && defined(__SSE2__) /* x86 + SSE2 */ \ 2864 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable like XXH32 hack */ 2865 /* 2866 * UGLY HACK: 2867 * GCC for x86 tends to autovectorize the 128-bit multiply, resulting in 2868 * slower code. 2869 * 2870 * By forcing seed64 into a register, we disrupt the cost model and 2871 * cause it to scalarize. See `XXH32_round()` 2872 * 2873 * FIXME: Clang's output is still _much_ faster -- On an AMD Ryzen 3600, 2874 * XXH3_64bits @ len=240 runs at 4.6 GB/s with Clang 9, but 3.3 GB/s on 2875 * GCC 9.2, despite both emitting scalar code. 2876 * 2877 * GCC generates much better scalar code than Clang for the rest of XXH3, 2878 * which is why finding a more optimal codepath is an interest. 2879 */ 2880 __asm__ ("" : "+r" (seed64)); 2881 #endif 2882 { xxh_u64 const input_lo = XXH_readLE64(input); 2883 xxh_u64 const input_hi = XXH_readLE64(input+8); 2884 return XXH3_mul128_fold64( 2885 input_lo ^ (XXH_readLE64(secret) + seed64), 2886 input_hi ^ (XXH_readLE64(secret+8) - seed64) 2887 ); 2888 } 2889 } 2890 2891 /* For mid range keys, XXH3 uses a Mum-hash variant. */ 2892 XXH_FORCE_INLINE XXH64_hash_t 2893 XXH3_len_17to128_64b(const xxh_u8* XXH_RESTRICT input, size_t len, 2894 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 2895 XXH64_hash_t seed) 2896 { 2897 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize; 2898 XXH_ASSERT(16 < len && len <= 128); 2899 2900 { xxh_u64 acc = len * XXH_PRIME64_1; 2901 if (len > 32) { 2902 if (len > 64) { 2903 if (len > 96) { 2904 acc += XXH3_mix16B(input+48, secret+96, seed); 2905 acc += XXH3_mix16B(input+len-64, secret+112, seed); 2906 } 2907 acc += XXH3_mix16B(input+32, secret+64, seed); 2908 acc += XXH3_mix16B(input+len-48, secret+80, seed); 2909 } 2910 acc += XXH3_mix16B(input+16, secret+32, seed); 2911 acc += XXH3_mix16B(input+len-32, secret+48, seed); 2912 } 2913 acc += XXH3_mix16B(input+0, secret+0, seed); 2914 acc += XXH3_mix16B(input+len-16, secret+16, seed); 2915 2916 return XXH3_avalanche(acc); 2917 } 2918 } 2919 2920 #define XXH3_MIDSIZE_MAX 240 2921 2922 XXH_NO_INLINE XXH64_hash_t 2923 XXH3_len_129to240_64b(const xxh_u8* XXH_RESTRICT input, size_t len, 2924 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 2925 XXH64_hash_t seed) 2926 { 2927 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize; 2928 XXH_ASSERT(128 < len && len <= XXH3_MIDSIZE_MAX); 2929 2930 #define XXH3_MIDSIZE_STARTOFFSET 3 2931 #define XXH3_MIDSIZE_LASTOFFSET 17 2932 2933 { xxh_u64 acc = len * XXH_PRIME64_1; 2934 int const nbRounds = (int)len / 16; 2935 int i; 2936 for (i=0; i<8; i++) { 2937 acc += XXH3_mix16B(input+(16*i), secret+(16*i), seed); 2938 } 2939 acc = XXH3_avalanche(acc); 2940 XXH_ASSERT(nbRounds >= 8); 2941 #if defined(__clang__) /* Clang */ \ 2942 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \ 2943 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */ 2944 /* 2945 * UGLY HACK: 2946 * Clang for ARMv7-A tries to vectorize this loop, similar to GCC x86. 2947 * In everywhere else, it uses scalar code. 2948 * 2949 * For 64->128-bit multiplies, even if the NEON was 100% optimal, it 2950 * would still be slower than UMAAL (see XXH_mult64to128). 2951 * 2952 * Unfortunately, Clang doesn't handle the long multiplies properly and 2953 * converts them to the nonexistent "vmulq_u64" intrinsic, which is then 2954 * scalarized into an ugly mess of VMOV.32 instructions. 2955 * 2956 * This mess is difficult to avoid without turning autovectorization 2957 * off completely, but they are usually relatively minor and/or not 2958 * worth it to fix. 2959 * 2960 * This loop is the easiest to fix, as unlike XXH32, this pragma 2961 * _actually works_ because it is a loop vectorization instead of an 2962 * SLP vectorization. 2963 */ 2964 #pragma clang loop vectorize(disable) 2965 #endif 2966 for (i=8 ; i < nbRounds; i++) { 2967 acc += XXH3_mix16B(input+(16*i), secret+(16*(i-8)) + XXH3_MIDSIZE_STARTOFFSET, seed); 2968 } 2969 /* last bytes */ 2970 acc += XXH3_mix16B(input + len - 16, secret + XXH3_SECRET_SIZE_MIN - XXH3_MIDSIZE_LASTOFFSET, seed); 2971 return XXH3_avalanche(acc); 2972 } 2973 } 2974 2975 2976 /* ======= Long Keys ======= */ 2977 2978 #define XXH_STRIPE_LEN 64 2979 #define XXH_SECRET_CONSUME_RATE 8 /* nb of secret bytes consumed at each accumulation */ 2980 #define XXH_ACC_NB (XXH_STRIPE_LEN / sizeof(xxh_u64)) 2981 2982 #ifdef XXH_OLD_NAMES 2983 # define STRIPE_LEN XXH_STRIPE_LEN 2984 # define ACC_NB XXH_ACC_NB 2985 #endif 2986 2987 XXH_FORCE_INLINE void XXH_writeLE64(void* dst, xxh_u64 v64) 2988 { 2989 if (!XXH_CPU_LITTLE_ENDIAN) v64 = XXH_swap64(v64); 2990 memcpy(dst, &v64, sizeof(v64)); 2991 } 2992 2993 /* Several intrinsic functions below are supposed to accept __int64 as argument, 2994 * as documented in https://software.intel.com/sites/landingpage/IntrinsicsGuide/ . 2995 * However, several environments do not define __int64 type, 2996 * requiring a workaround. 2997 */ 2998 #if !defined (__VMS) \ 2999 && (defined (__cplusplus) \ 3000 || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) ) 3001 typedef int64_t xxh_i64; 3002 #else 3003 /* the following type must have a width of 64-bit */ 3004 typedef long long xxh_i64; 3005 #endif 3006 3007 /* 3008 * XXH3_accumulate_512 is the tightest loop for long inputs, and it is the most optimized. 3009 * 3010 * It is a hardened version of UMAC, based off of FARSH's implementation. 3011 * 3012 * This was chosen because it adapts quite well to 32-bit, 64-bit, and SIMD 3013 * implementations, and it is ridiculously fast. 3014 * 3015 * We harden it by mixing the original input to the accumulators as well as the product. 3016 * 3017 * This means that in the (relatively likely) case of a multiply by zero, the 3018 * original input is preserved. 3019 * 3020 * On 128-bit inputs, we swap 64-bit pairs when we add the input to improve 3021 * cross-pollination, as otherwise the upper and lower halves would be 3022 * essentially independent. 3023 * 3024 * This doesn't matter on 64-bit hashes since they all get merged together in 3025 * the end, so we skip the extra step. 3026 * 3027 * Both XXH3_64bits and XXH3_128bits use this subroutine. 3028 */ 3029 3030 #if (XXH_VECTOR == XXH_AVX512) || defined(XXH_X86DISPATCH) 3031 3032 #ifndef XXH_TARGET_AVX512 3033 # define XXH_TARGET_AVX512 /* disable attribute target */ 3034 #endif 3035 3036 XXH_FORCE_INLINE XXH_TARGET_AVX512 void 3037 XXH3_accumulate_512_avx512(void* XXH_RESTRICT acc, 3038 const void* XXH_RESTRICT input, 3039 const void* XXH_RESTRICT secret) 3040 { 3041 XXH_ALIGN(64) __m512i* const xacc = (__m512i *) acc; 3042 XXH_ASSERT((((size_t)acc) & 63) == 0); 3043 XXH_STATIC_ASSERT(XXH_STRIPE_LEN == sizeof(__m512i)); 3044 3045 { 3046 /* data_vec = input[0]; */ 3047 __m512i const data_vec = _mm512_loadu_si512 (input); 3048 /* key_vec = secret[0]; */ 3049 __m512i const key_vec = _mm512_loadu_si512 (secret); 3050 /* data_key = data_vec ^ key_vec; */ 3051 __m512i const data_key = _mm512_xor_si512 (data_vec, key_vec); 3052 /* data_key_lo = data_key >> 32; */ 3053 __m512i const data_key_lo = _mm512_shuffle_epi32 (data_key, (_MM_PERM_ENUM)_MM_SHUFFLE(0, 3, 0, 1)); 3054 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */ 3055 __m512i const product = _mm512_mul_epu32 (data_key, data_key_lo); 3056 /* xacc[0] += swap(data_vec); */ 3057 __m512i const data_swap = _mm512_shuffle_epi32(data_vec, (_MM_PERM_ENUM)_MM_SHUFFLE(1, 0, 3, 2)); 3058 __m512i const sum = _mm512_add_epi64(*xacc, data_swap); 3059 /* xacc[0] += product; */ 3060 *xacc = _mm512_add_epi64(product, sum); 3061 } 3062 } 3063 3064 /* 3065 * XXH3_scrambleAcc: Scrambles the accumulators to improve mixing. 3066 * 3067 * Multiplication isn't perfect, as explained by Google in HighwayHash: 3068 * 3069 * // Multiplication mixes/scrambles bytes 0-7 of the 64-bit result to 3070 * // varying degrees. In descending order of goodness, bytes 3071 * // 3 4 2 5 1 6 0 7 have quality 228 224 164 160 100 96 36 32. 3072 * // As expected, the upper and lower bytes are much worse. 3073 * 3074 * Source: https://github.com/google/highwayhash/blob/0aaf66b/highwayhash/hh_avx2.h#L291 3075 * 3076 * Since our algorithm uses a pseudorandom secret to add some variance into the 3077 * mix, we don't need to (or want to) mix as often or as much as HighwayHash does. 3078 * 3079 * This isn't as tight as XXH3_accumulate, but still written in SIMD to avoid 3080 * extraction. 3081 * 3082 * Both XXH3_64bits and XXH3_128bits use this subroutine. 3083 */ 3084 3085 XXH_FORCE_INLINE XXH_TARGET_AVX512 void 3086 XXH3_scrambleAcc_avx512(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3087 { 3088 XXH_ASSERT((((size_t)acc) & 63) == 0); 3089 XXH_STATIC_ASSERT(XXH_STRIPE_LEN == sizeof(__m512i)); 3090 { XXH_ALIGN(64) __m512i* const xacc = (__m512i*) acc; 3091 const __m512i prime32 = _mm512_set1_epi32((int)XXH_PRIME32_1); 3092 3093 /* xacc[0] ^= (xacc[0] >> 47) */ 3094 __m512i const acc_vec = *xacc; 3095 __m512i const shifted = _mm512_srli_epi64 (acc_vec, 47); 3096 __m512i const data_vec = _mm512_xor_si512 (acc_vec, shifted); 3097 /* xacc[0] ^= secret; */ 3098 __m512i const key_vec = _mm512_loadu_si512 (secret); 3099 __m512i const data_key = _mm512_xor_si512 (data_vec, key_vec); 3100 3101 /* xacc[0] *= XXH_PRIME32_1; */ 3102 __m512i const data_key_hi = _mm512_shuffle_epi32 (data_key, (_MM_PERM_ENUM)_MM_SHUFFLE(0, 3, 0, 1)); 3103 __m512i const prod_lo = _mm512_mul_epu32 (data_key, prime32); 3104 __m512i const prod_hi = _mm512_mul_epu32 (data_key_hi, prime32); 3105 *xacc = _mm512_add_epi64(prod_lo, _mm512_slli_epi64(prod_hi, 32)); 3106 } 3107 } 3108 3109 XXH_FORCE_INLINE XXH_TARGET_AVX512 void 3110 XXH3_initCustomSecret_avx512(void* XXH_RESTRICT customSecret, xxh_u64 seed64) 3111 { 3112 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 63) == 0); 3113 XXH_STATIC_ASSERT(XXH_SEC_ALIGN == 64); 3114 XXH_ASSERT(((size_t)customSecret & 63) == 0); 3115 (void)(&XXH_writeLE64); 3116 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / sizeof(__m512i); 3117 __m512i const seed = _mm512_mask_set1_epi64(_mm512_set1_epi64((xxh_i64)seed64), 0xAA, -(xxh_i64)seed64); 3118 3119 XXH_ALIGN(64) const __m512i* const src = (const __m512i*) XXH3_kSecret; 3120 XXH_ALIGN(64) __m512i* const dest = ( __m512i*) customSecret; 3121 int i; 3122 for (i=0; i < nbRounds; ++i) { 3123 /* GCC has a bug, _mm512_stream_load_si512 accepts 'void*', not 'void const*', 3124 * this will warn "discards ‘const’ qualifier". */ 3125 union { 3126 XXH_ALIGN(64) const __m512i* cp; 3127 XXH_ALIGN(64) void* p; 3128 } remote_const_void; 3129 remote_const_void.cp = src + i; 3130 dest[i] = _mm512_add_epi64(_mm512_stream_load_si512(remote_const_void.p), seed); 3131 } } 3132 } 3133 3134 #endif 3135 3136 #if (XXH_VECTOR == XXH_AVX2) || defined(XXH_X86DISPATCH) 3137 3138 #ifndef XXH_TARGET_AVX2 3139 # define XXH_TARGET_AVX2 /* disable attribute target */ 3140 #endif 3141 3142 XXH_FORCE_INLINE XXH_TARGET_AVX2 void 3143 XXH3_accumulate_512_avx2( void* XXH_RESTRICT acc, 3144 const void* XXH_RESTRICT input, 3145 const void* XXH_RESTRICT secret) 3146 { 3147 XXH_ASSERT((((size_t)acc) & 31) == 0); 3148 { XXH_ALIGN(32) __m256i* const xacc = (__m256i *) acc; 3149 /* Unaligned. This is mainly for pointer arithmetic, and because 3150 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */ 3151 const __m256i* const xinput = (const __m256i *) input; 3152 /* Unaligned. This is mainly for pointer arithmetic, and because 3153 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */ 3154 const __m256i* const xsecret = (const __m256i *) secret; 3155 3156 size_t i; 3157 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m256i); i++) { 3158 /* data_vec = xinput[i]; */ 3159 __m256i const data_vec = _mm256_loadu_si256 (xinput+i); 3160 /* key_vec = xsecret[i]; */ 3161 __m256i const key_vec = _mm256_loadu_si256 (xsecret+i); 3162 /* data_key = data_vec ^ key_vec; */ 3163 __m256i const data_key = _mm256_xor_si256 (data_vec, key_vec); 3164 /* data_key_lo = data_key >> 32; */ 3165 __m256i const data_key_lo = _mm256_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1)); 3166 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */ 3167 __m256i const product = _mm256_mul_epu32 (data_key, data_key_lo); 3168 /* xacc[i] += swap(data_vec); */ 3169 __m256i const data_swap = _mm256_shuffle_epi32(data_vec, _MM_SHUFFLE(1, 0, 3, 2)); 3170 __m256i const sum = _mm256_add_epi64(xacc[i], data_swap); 3171 /* xacc[i] += product; */ 3172 xacc[i] = _mm256_add_epi64(product, sum); 3173 } } 3174 } 3175 3176 XXH_FORCE_INLINE XXH_TARGET_AVX2 void 3177 XXH3_scrambleAcc_avx2(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3178 { 3179 XXH_ASSERT((((size_t)acc) & 31) == 0); 3180 { XXH_ALIGN(32) __m256i* const xacc = (__m256i*) acc; 3181 /* Unaligned. This is mainly for pointer arithmetic, and because 3182 * _mm256_loadu_si256 requires a const __m256i * pointer for some reason. */ 3183 const __m256i* const xsecret = (const __m256i *) secret; 3184 const __m256i prime32 = _mm256_set1_epi32((int)XXH_PRIME32_1); 3185 3186 size_t i; 3187 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m256i); i++) { 3188 /* xacc[i] ^= (xacc[i] >> 47) */ 3189 __m256i const acc_vec = xacc[i]; 3190 __m256i const shifted = _mm256_srli_epi64 (acc_vec, 47); 3191 __m256i const data_vec = _mm256_xor_si256 (acc_vec, shifted); 3192 /* xacc[i] ^= xsecret; */ 3193 __m256i const key_vec = _mm256_loadu_si256 (xsecret+i); 3194 __m256i const data_key = _mm256_xor_si256 (data_vec, key_vec); 3195 3196 /* xacc[i] *= XXH_PRIME32_1; */ 3197 __m256i const data_key_hi = _mm256_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1)); 3198 __m256i const prod_lo = _mm256_mul_epu32 (data_key, prime32); 3199 __m256i const prod_hi = _mm256_mul_epu32 (data_key_hi, prime32); 3200 xacc[i] = _mm256_add_epi64(prod_lo, _mm256_slli_epi64(prod_hi, 32)); 3201 } 3202 } 3203 } 3204 3205 XXH_FORCE_INLINE XXH_TARGET_AVX2 void XXH3_initCustomSecret_avx2(void* XXH_RESTRICT customSecret, xxh_u64 seed64) 3206 { 3207 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 31) == 0); 3208 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE / sizeof(__m256i)) == 6); 3209 XXH_STATIC_ASSERT(XXH_SEC_ALIGN <= 64); 3210 (void)(&XXH_writeLE64); 3211 XXH_PREFETCH(customSecret); 3212 { __m256i const seed = _mm256_set_epi64x(-(xxh_i64)seed64, (xxh_i64)seed64, -(xxh_i64)seed64, (xxh_i64)seed64); 3213 3214 XXH_ALIGN(64) const __m256i* const src = (const __m256i*) XXH3_kSecret; 3215 XXH_ALIGN(64) __m256i* dest = ( __m256i*) customSecret; 3216 3217 # if defined(__GNUC__) || defined(__clang__) 3218 /* 3219 * On GCC & Clang, marking 'dest' as modified will cause the compiler: 3220 * - do not extract the secret from sse registers in the internal loop 3221 * - use less common registers, and avoid pushing these reg into stack 3222 * The asm hack causes Clang to assume that XXH3_kSecretPtr aliases with 3223 * customSecret, and on aarch64, this prevented LDP from merging two 3224 * loads together for free. Putting the loads together before the stores 3225 * properly generates LDP. 3226 */ 3227 __asm__("" : "+r" (dest)); 3228 # endif 3229 3230 /* GCC -O2 need unroll loop manually */ 3231 dest[0] = _mm256_add_epi64(_mm256_stream_load_si256(src+0), seed); 3232 dest[1] = _mm256_add_epi64(_mm256_stream_load_si256(src+1), seed); 3233 dest[2] = _mm256_add_epi64(_mm256_stream_load_si256(src+2), seed); 3234 dest[3] = _mm256_add_epi64(_mm256_stream_load_si256(src+3), seed); 3235 dest[4] = _mm256_add_epi64(_mm256_stream_load_si256(src+4), seed); 3236 dest[5] = _mm256_add_epi64(_mm256_stream_load_si256(src+5), seed); 3237 } 3238 } 3239 3240 #endif 3241 3242 #if (XXH_VECTOR == XXH_SSE2) || defined(XXH_X86DISPATCH) 3243 3244 #ifndef XXH_TARGET_SSE2 3245 # define XXH_TARGET_SSE2 /* disable attribute target */ 3246 #endif 3247 3248 XXH_FORCE_INLINE XXH_TARGET_SSE2 void 3249 XXH3_accumulate_512_sse2( void* XXH_RESTRICT acc, 3250 const void* XXH_RESTRICT input, 3251 const void* XXH_RESTRICT secret) 3252 { 3253 /* SSE2 is just a half-scale version of the AVX2 version. */ 3254 XXH_ASSERT((((size_t)acc) & 15) == 0); 3255 { XXH_ALIGN(16) __m128i* const xacc = (__m128i *) acc; 3256 /* Unaligned. This is mainly for pointer arithmetic, and because 3257 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */ 3258 const __m128i* const xinput = (const __m128i *) input; 3259 /* Unaligned. This is mainly for pointer arithmetic, and because 3260 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */ 3261 const __m128i* const xsecret = (const __m128i *) secret; 3262 3263 size_t i; 3264 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m128i); i++) { 3265 /* data_vec = xinput[i]; */ 3266 __m128i const data_vec = _mm_loadu_si128 (xinput+i); 3267 /* key_vec = xsecret[i]; */ 3268 __m128i const key_vec = _mm_loadu_si128 (xsecret+i); 3269 /* data_key = data_vec ^ key_vec; */ 3270 __m128i const data_key = _mm_xor_si128 (data_vec, key_vec); 3271 /* data_key_lo = data_key >> 32; */ 3272 __m128i const data_key_lo = _mm_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1)); 3273 /* product = (data_key & 0xffffffff) * (data_key_lo & 0xffffffff); */ 3274 __m128i const product = _mm_mul_epu32 (data_key, data_key_lo); 3275 /* xacc[i] += swap(data_vec); */ 3276 __m128i const data_swap = _mm_shuffle_epi32(data_vec, _MM_SHUFFLE(1,0,3,2)); 3277 __m128i const sum = _mm_add_epi64(xacc[i], data_swap); 3278 /* xacc[i] += product; */ 3279 xacc[i] = _mm_add_epi64(product, sum); 3280 } } 3281 } 3282 3283 XXH_FORCE_INLINE XXH_TARGET_SSE2 void 3284 XXH3_scrambleAcc_sse2(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3285 { 3286 XXH_ASSERT((((size_t)acc) & 15) == 0); 3287 { XXH_ALIGN(16) __m128i* const xacc = (__m128i*) acc; 3288 /* Unaligned. This is mainly for pointer arithmetic, and because 3289 * _mm_loadu_si128 requires a const __m128i * pointer for some reason. */ 3290 const __m128i* const xsecret = (const __m128i *) secret; 3291 const __m128i prime32 = _mm_set1_epi32((int)XXH_PRIME32_1); 3292 3293 size_t i; 3294 for (i=0; i < XXH_STRIPE_LEN/sizeof(__m128i); i++) { 3295 /* xacc[i] ^= (xacc[i] >> 47) */ 3296 __m128i const acc_vec = xacc[i]; 3297 __m128i const shifted = _mm_srli_epi64 (acc_vec, 47); 3298 __m128i const data_vec = _mm_xor_si128 (acc_vec, shifted); 3299 /* xacc[i] ^= xsecret[i]; */ 3300 __m128i const key_vec = _mm_loadu_si128 (xsecret+i); 3301 __m128i const data_key = _mm_xor_si128 (data_vec, key_vec); 3302 3303 /* xacc[i] *= XXH_PRIME32_1; */ 3304 __m128i const data_key_hi = _mm_shuffle_epi32 (data_key, _MM_SHUFFLE(0, 3, 0, 1)); 3305 __m128i const prod_lo = _mm_mul_epu32 (data_key, prime32); 3306 __m128i const prod_hi = _mm_mul_epu32 (data_key_hi, prime32); 3307 xacc[i] = _mm_add_epi64(prod_lo, _mm_slli_epi64(prod_hi, 32)); 3308 } 3309 } 3310 } 3311 3312 XXH_FORCE_INLINE XXH_TARGET_SSE2 void XXH3_initCustomSecret_sse2(void* XXH_RESTRICT customSecret, xxh_u64 seed64) 3313 { 3314 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 15) == 0); 3315 (void)(&XXH_writeLE64); 3316 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / sizeof(__m128i); 3317 3318 # if defined(_MSC_VER) && defined(_M_IX86) && _MSC_VER < 1900 3319 // MSVC 32bit mode does not support _mm_set_epi64x before 2015 3320 XXH_ALIGN(16) const xxh_i64 seed64x2[2] = { (xxh_i64)seed64, -(xxh_i64)seed64 }; 3321 __m128i const seed = _mm_load_si128((__m128i const*)seed64x2); 3322 # else 3323 __m128i const seed = _mm_set_epi64x(-(xxh_i64)seed64, (xxh_i64)seed64); 3324 # endif 3325 int i; 3326 3327 XXH_ALIGN(64) const float* const src = (float const*) XXH3_kSecret; 3328 XXH_ALIGN(XXH_SEC_ALIGN) __m128i* dest = (__m128i*) customSecret; 3329 # if defined(__GNUC__) || defined(__clang__) 3330 /* 3331 * On GCC & Clang, marking 'dest' as modified will cause the compiler: 3332 * - do not extract the secret from sse registers in the internal loop 3333 * - use less common registers, and avoid pushing these reg into stack 3334 */ 3335 __asm__("" : "+r" (dest)); 3336 # endif 3337 3338 for (i=0; i < nbRounds; ++i) { 3339 dest[i] = _mm_add_epi64(_mm_castps_si128(_mm_load_ps(src+i*4)), seed); 3340 } } 3341 } 3342 3343 #endif 3344 3345 #if (XXH_VECTOR == XXH_NEON) 3346 3347 XXH_FORCE_INLINE void 3348 XXH3_accumulate_512_neon( void* XXH_RESTRICT acc, 3349 const void* XXH_RESTRICT input, 3350 const void* XXH_RESTRICT secret) 3351 { 3352 XXH_ASSERT((((size_t)acc) & 15) == 0); 3353 { 3354 XXH_ALIGN(16) uint64x2_t* const xacc = (uint64x2_t *) acc; 3355 /* We don't use a uint32x4_t pointer because it causes bus errors on ARMv7. */ 3356 uint8_t const* const xinput = (const uint8_t *) input; 3357 uint8_t const* const xsecret = (const uint8_t *) secret; 3358 3359 size_t i; 3360 for (i=0; i < XXH_STRIPE_LEN / sizeof(uint64x2_t); i++) { 3361 /* data_vec = xinput[i]; */ 3362 uint8x16_t data_vec = vld1q_u8(xinput + (i * 16)); 3363 /* key_vec = xsecret[i]; */ 3364 uint8x16_t key_vec = vld1q_u8(xsecret + (i * 16)); 3365 uint64x2_t data_key; 3366 uint32x2_t data_key_lo, data_key_hi; 3367 /* xacc[i] += swap(data_vec); */ 3368 uint64x2_t const data64 = vreinterpretq_u64_u8(data_vec); 3369 uint64x2_t const swapped = vextq_u64(data64, data64, 1); 3370 xacc[i] = vaddq_u64 (xacc[i], swapped); 3371 /* data_key = data_vec ^ key_vec; */ 3372 data_key = vreinterpretq_u64_u8(veorq_u8(data_vec, key_vec)); 3373 /* data_key_lo = (uint32x2_t) (data_key & 0xFFFFFFFF); 3374 * data_key_hi = (uint32x2_t) (data_key >> 32); 3375 * data_key = UNDEFINED; */ 3376 XXH_SPLIT_IN_PLACE(data_key, data_key_lo, data_key_hi); 3377 /* xacc[i] += (uint64x2_t) data_key_lo * (uint64x2_t) data_key_hi; */ 3378 xacc[i] = vmlal_u32 (xacc[i], data_key_lo, data_key_hi); 3379 3380 } 3381 } 3382 } 3383 3384 XXH_FORCE_INLINE void 3385 XXH3_scrambleAcc_neon(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3386 { 3387 XXH_ASSERT((((size_t)acc) & 15) == 0); 3388 3389 { uint64x2_t* xacc = (uint64x2_t*) acc; 3390 uint8_t const* xsecret = (uint8_t const*) secret; 3391 uint32x2_t prime = vdup_n_u32 (XXH_PRIME32_1); 3392 3393 size_t i; 3394 for (i=0; i < XXH_STRIPE_LEN/sizeof(uint64x2_t); i++) { 3395 /* xacc[i] ^= (xacc[i] >> 47); */ 3396 uint64x2_t acc_vec = xacc[i]; 3397 uint64x2_t shifted = vshrq_n_u64 (acc_vec, 47); 3398 uint64x2_t data_vec = veorq_u64 (acc_vec, shifted); 3399 3400 /* xacc[i] ^= xsecret[i]; */ 3401 uint8x16_t key_vec = vld1q_u8(xsecret + (i * 16)); 3402 uint64x2_t data_key = veorq_u64(data_vec, vreinterpretq_u64_u8(key_vec)); 3403 3404 /* xacc[i] *= XXH_PRIME32_1 */ 3405 uint32x2_t data_key_lo, data_key_hi; 3406 /* data_key_lo = (uint32x2_t) (xacc[i] & 0xFFFFFFFF); 3407 * data_key_hi = (uint32x2_t) (xacc[i] >> 32); 3408 * xacc[i] = UNDEFINED; */ 3409 XXH_SPLIT_IN_PLACE(data_key, data_key_lo, data_key_hi); 3410 { /* 3411 * prod_hi = (data_key >> 32) * XXH_PRIME32_1; 3412 * 3413 * Avoid vmul_u32 + vshll_n_u32 since Clang 6 and 7 will 3414 * incorrectly "optimize" this: 3415 * tmp = vmul_u32(vmovn_u64(a), vmovn_u64(b)); 3416 * shifted = vshll_n_u32(tmp, 32); 3417 * to this: 3418 * tmp = "vmulq_u64"(a, b); // no such thing! 3419 * shifted = vshlq_n_u64(tmp, 32); 3420 * 3421 * However, unlike SSE, Clang lacks a 64-bit multiply routine 3422 * for NEON, and it scalarizes two 64-bit multiplies instead. 3423 * 3424 * vmull_u32 has the same timing as vmul_u32, and it avoids 3425 * this bug completely. 3426 * See https://bugs.llvm.org/show_bug.cgi?id=39967 3427 */ 3428 uint64x2_t prod_hi = vmull_u32 (data_key_hi, prime); 3429 /* xacc[i] = prod_hi << 32; */ 3430 xacc[i] = vshlq_n_u64(prod_hi, 32); 3431 /* xacc[i] += (prod_hi & 0xFFFFFFFF) * XXH_PRIME32_1; */ 3432 xacc[i] = vmlal_u32(xacc[i], data_key_lo, prime); 3433 } 3434 } } 3435 } 3436 3437 #endif 3438 3439 #if (XXH_VECTOR == XXH_VSX) 3440 3441 XXH_FORCE_INLINE void 3442 XXH3_accumulate_512_vsx( void* XXH_RESTRICT acc, 3443 const void* XXH_RESTRICT input, 3444 const void* XXH_RESTRICT secret) 3445 { 3446 xxh_u64x2* const xacc = (xxh_u64x2*) acc; /* presumed aligned */ 3447 xxh_u64x2 const* const xinput = (xxh_u64x2 const*) input; /* no alignment restriction */ 3448 xxh_u64x2 const* const xsecret = (xxh_u64x2 const*) secret; /* no alignment restriction */ 3449 xxh_u64x2 const v32 = { 32, 32 }; 3450 size_t i; 3451 for (i = 0; i < XXH_STRIPE_LEN / sizeof(xxh_u64x2); i++) { 3452 /* data_vec = xinput[i]; */ 3453 xxh_u64x2 const data_vec = XXH_vec_loadu(xinput + i); 3454 /* key_vec = xsecret[i]; */ 3455 xxh_u64x2 const key_vec = XXH_vec_loadu(xsecret + i); 3456 xxh_u64x2 const data_key = data_vec ^ key_vec; 3457 /* shuffled = (data_key << 32) | (data_key >> 32); */ 3458 xxh_u32x4 const shuffled = (xxh_u32x4)vec_rl(data_key, v32); 3459 /* product = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)shuffled & 0xFFFFFFFF); */ 3460 xxh_u64x2 const product = XXH_vec_mulo((xxh_u32x4)data_key, shuffled); 3461 xacc[i] += product; 3462 3463 /* swap high and low halves */ 3464 #ifdef __s390x__ 3465 xacc[i] += vec_permi(data_vec, data_vec, 2); 3466 #else 3467 xacc[i] += vec_xxpermdi(data_vec, data_vec, 2); 3468 #endif 3469 } 3470 } 3471 3472 XXH_FORCE_INLINE void 3473 XXH3_scrambleAcc_vsx(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3474 { 3475 XXH_ASSERT((((size_t)acc) & 15) == 0); 3476 3477 { xxh_u64x2* const xacc = (xxh_u64x2*) acc; 3478 const xxh_u64x2* const xsecret = (const xxh_u64x2*) secret; 3479 /* constants */ 3480 xxh_u64x2 const v32 = { 32, 32 }; 3481 xxh_u64x2 const v47 = { 47, 47 }; 3482 xxh_u32x4 const prime = { XXH_PRIME32_1, XXH_PRIME32_1, XXH_PRIME32_1, XXH_PRIME32_1 }; 3483 size_t i; 3484 for (i = 0; i < XXH_STRIPE_LEN / sizeof(xxh_u64x2); i++) { 3485 /* xacc[i] ^= (xacc[i] >> 47); */ 3486 xxh_u64x2 const acc_vec = xacc[i]; 3487 xxh_u64x2 const data_vec = acc_vec ^ (acc_vec >> v47); 3488 3489 /* xacc[i] ^= xsecret[i]; */ 3490 xxh_u64x2 const key_vec = XXH_vec_loadu(xsecret + i); 3491 xxh_u64x2 const data_key = data_vec ^ key_vec; 3492 3493 /* xacc[i] *= XXH_PRIME32_1 */ 3494 /* prod_lo = ((xxh_u64x2)data_key & 0xFFFFFFFF) * ((xxh_u64x2)prime & 0xFFFFFFFF); */ 3495 xxh_u64x2 const prod_even = XXH_vec_mule((xxh_u32x4)data_key, prime); 3496 /* prod_hi = ((xxh_u64x2)data_key >> 32) * ((xxh_u64x2)prime >> 32); */ 3497 xxh_u64x2 const prod_odd = XXH_vec_mulo((xxh_u32x4)data_key, prime); 3498 xacc[i] = prod_odd + (prod_even << v32); 3499 } } 3500 } 3501 3502 #endif 3503 3504 /* scalar variants - universal */ 3505 3506 XXH_FORCE_INLINE void 3507 XXH3_accumulate_512_scalar(void* XXH_RESTRICT acc, 3508 const void* XXH_RESTRICT input, 3509 const void* XXH_RESTRICT secret) 3510 { 3511 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64* const xacc = (xxh_u64*) acc; /* presumed aligned */ 3512 const xxh_u8* const xinput = (const xxh_u8*) input; /* no alignment restriction */ 3513 const xxh_u8* const xsecret = (const xxh_u8*) secret; /* no alignment restriction */ 3514 size_t i; 3515 XXH_ASSERT(((size_t)acc & (XXH_ACC_ALIGN-1)) == 0); 3516 for (i=0; i < XXH_ACC_NB; i++) { 3517 xxh_u64 const data_val = XXH_readLE64(xinput + 8*i); 3518 xxh_u64 const data_key = data_val ^ XXH_readLE64(xsecret + i*8); 3519 xacc[i ^ 1] += data_val; /* swap adjacent lanes */ 3520 xacc[i] += XXH_mult32to64(data_key & 0xFFFFFFFF, data_key >> 32); 3521 } 3522 } 3523 3524 XXH_FORCE_INLINE void 3525 XXH3_scrambleAcc_scalar(void* XXH_RESTRICT acc, const void* XXH_RESTRICT secret) 3526 { 3527 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64* const xacc = (xxh_u64*) acc; /* presumed aligned */ 3528 const xxh_u8* const xsecret = (const xxh_u8*) secret; /* no alignment restriction */ 3529 size_t i; 3530 XXH_ASSERT((((size_t)acc) & (XXH_ACC_ALIGN-1)) == 0); 3531 for (i=0; i < XXH_ACC_NB; i++) { 3532 xxh_u64 const key64 = XXH_readLE64(xsecret + 8*i); 3533 xxh_u64 acc64 = xacc[i]; 3534 acc64 = XXH_xorshift64(acc64, 47); 3535 acc64 ^= key64; 3536 acc64 *= XXH_PRIME32_1; 3537 xacc[i] = acc64; 3538 } 3539 } 3540 3541 XXH_FORCE_INLINE void 3542 XXH3_initCustomSecret_scalar(void* XXH_RESTRICT customSecret, xxh_u64 seed64) 3543 { 3544 /* 3545 * We need a separate pointer for the hack below, 3546 * which requires a non-const pointer. 3547 * Any decent compiler will optimize this out otherwise. 3548 */ 3549 const xxh_u8* kSecretPtr = XXH3_kSecret; 3550 XXH_STATIC_ASSERT((XXH_SECRET_DEFAULT_SIZE & 15) == 0); 3551 3552 #if defined(__clang__) && defined(__aarch64__) 3553 /* 3554 * UGLY HACK: 3555 * Clang generates a bunch of MOV/MOVK pairs for aarch64, and they are 3556 * placed sequentially, in order, at the top of the unrolled loop. 3557 * 3558 * While MOVK is great for generating constants (2 cycles for a 64-bit 3559 * constant compared to 4 cycles for LDR), long MOVK chains stall the 3560 * integer pipelines: 3561 * I L S 3562 * MOVK 3563 * MOVK 3564 * MOVK 3565 * MOVK 3566 * ADD 3567 * SUB STR 3568 * STR 3569 * By forcing loads from memory (as the asm line causes Clang to assume 3570 * that XXH3_kSecretPtr has been changed), the pipelines are used more 3571 * efficiently: 3572 * I L S 3573 * LDR 3574 * ADD LDR 3575 * SUB STR 3576 * STR 3577 * XXH3_64bits_withSeed, len == 256, Snapdragon 835 3578 * without hack: 2654.4 MB/s 3579 * with hack: 3202.9 MB/s 3580 */ 3581 __asm__("" : "+r" (kSecretPtr)); 3582 #endif 3583 /* 3584 * Note: in debug mode, this overrides the asm optimization 3585 * and Clang will emit MOVK chains again. 3586 */ 3587 XXH_ASSERT(kSecretPtr == XXH3_kSecret); 3588 3589 { int const nbRounds = XXH_SECRET_DEFAULT_SIZE / 16; 3590 int i; 3591 for (i=0; i < nbRounds; i++) { 3592 /* 3593 * The asm hack causes Clang to assume that kSecretPtr aliases with 3594 * customSecret, and on aarch64, this prevented LDP from merging two 3595 * loads together for free. Putting the loads together before the stores 3596 * properly generates LDP. 3597 */ 3598 xxh_u64 lo = XXH_readLE64(kSecretPtr + 16*i) + seed64; 3599 xxh_u64 hi = XXH_readLE64(kSecretPtr + 16*i + 8) - seed64; 3600 XXH_writeLE64((xxh_u8*)customSecret + 16*i, lo); 3601 XXH_writeLE64((xxh_u8*)customSecret + 16*i + 8, hi); 3602 } } 3603 } 3604 3605 3606 typedef void (*XXH3_f_accumulate_512)(void* XXH_RESTRICT, const void*, const void*); 3607 typedef void (*XXH3_f_scrambleAcc)(void* XXH_RESTRICT, const void*); 3608 typedef void (*XXH3_f_initCustomSecret)(void* XXH_RESTRICT, xxh_u64); 3609 3610 3611 #if (XXH_VECTOR == XXH_AVX512) 3612 3613 #define XXH3_accumulate_512 XXH3_accumulate_512_avx512 3614 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx512 3615 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx512 3616 3617 #elif (XXH_VECTOR == XXH_AVX2) 3618 3619 #define XXH3_accumulate_512 XXH3_accumulate_512_avx2 3620 #define XXH3_scrambleAcc XXH3_scrambleAcc_avx2 3621 #define XXH3_initCustomSecret XXH3_initCustomSecret_avx2 3622 3623 #elif (XXH_VECTOR == XXH_SSE2) 3624 3625 #define XXH3_accumulate_512 XXH3_accumulate_512_sse2 3626 #define XXH3_scrambleAcc XXH3_scrambleAcc_sse2 3627 #define XXH3_initCustomSecret XXH3_initCustomSecret_sse2 3628 3629 #elif (XXH_VECTOR == XXH_NEON) 3630 3631 #define XXH3_accumulate_512 XXH3_accumulate_512_neon 3632 #define XXH3_scrambleAcc XXH3_scrambleAcc_neon 3633 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar 3634 3635 #elif (XXH_VECTOR == XXH_VSX) 3636 3637 #define XXH3_accumulate_512 XXH3_accumulate_512_vsx 3638 #define XXH3_scrambleAcc XXH3_scrambleAcc_vsx 3639 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar 3640 3641 #else /* scalar */ 3642 3643 #define XXH3_accumulate_512 XXH3_accumulate_512_scalar 3644 #define XXH3_scrambleAcc XXH3_scrambleAcc_scalar 3645 #define XXH3_initCustomSecret XXH3_initCustomSecret_scalar 3646 3647 #endif 3648 3649 3650 3651 #ifndef XXH_PREFETCH_DIST 3652 # ifdef __clang__ 3653 # define XXH_PREFETCH_DIST 320 3654 # else 3655 # if (XXH_VECTOR == XXH_AVX512) 3656 # define XXH_PREFETCH_DIST 512 3657 # else 3658 # define XXH_PREFETCH_DIST 384 3659 # endif 3660 # endif /* __clang__ */ 3661 #endif /* XXH_PREFETCH_DIST */ 3662 3663 /* 3664 * XXH3_accumulate() 3665 * Loops over XXH3_accumulate_512(). 3666 * Assumption: nbStripes will not overflow the secret size 3667 */ 3668 XXH_FORCE_INLINE void 3669 XXH3_accumulate( xxh_u64* XXH_RESTRICT acc, 3670 const xxh_u8* XXH_RESTRICT input, 3671 const xxh_u8* XXH_RESTRICT secret, 3672 size_t nbStripes, 3673 XXH3_f_accumulate_512 f_acc512) 3674 { 3675 size_t n; 3676 for (n = 0; n < nbStripes; n++ ) { 3677 const xxh_u8* const in = input + n*XXH_STRIPE_LEN; 3678 XXH_PREFETCH(in + XXH_PREFETCH_DIST); 3679 f_acc512(acc, 3680 in, 3681 secret + n*XXH_SECRET_CONSUME_RATE); 3682 } 3683 } 3684 3685 XXH_FORCE_INLINE void 3686 XXH3_hashLong_internal_loop(xxh_u64* XXH_RESTRICT acc, 3687 const xxh_u8* XXH_RESTRICT input, size_t len, 3688 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 3689 XXH3_f_accumulate_512 f_acc512, 3690 XXH3_f_scrambleAcc f_scramble) 3691 { 3692 size_t const nbStripesPerBlock = (secretSize - XXH_STRIPE_LEN) / XXH_SECRET_CONSUME_RATE; 3693 size_t const block_len = XXH_STRIPE_LEN * nbStripesPerBlock; 3694 size_t const nb_blocks = (len - 1) / block_len; 3695 3696 size_t n; 3697 3698 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); 3699 3700 for (n = 0; n < nb_blocks; n++) { 3701 XXH3_accumulate(acc, input + n*block_len, secret, nbStripesPerBlock, f_acc512); 3702 f_scramble(acc, secret + secretSize - XXH_STRIPE_LEN); 3703 } 3704 3705 /* last partial block */ 3706 XXH_ASSERT(len > XXH_STRIPE_LEN); 3707 { size_t const nbStripes = ((len - 1) - (block_len * nb_blocks)) / XXH_STRIPE_LEN; 3708 XXH_ASSERT(nbStripes <= (secretSize / XXH_SECRET_CONSUME_RATE)); 3709 XXH3_accumulate(acc, input + nb_blocks*block_len, secret, nbStripes, f_acc512); 3710 3711 /* last stripe */ 3712 { const xxh_u8* const p = input + len - XXH_STRIPE_LEN; 3713 #define XXH_SECRET_LASTACC_START 7 /* not aligned on 8, last secret is different from acc & scrambler */ 3714 f_acc512(acc, p, secret + secretSize - XXH_STRIPE_LEN - XXH_SECRET_LASTACC_START); 3715 } } 3716 } 3717 3718 XXH_FORCE_INLINE xxh_u64 3719 XXH3_mix2Accs(const xxh_u64* XXH_RESTRICT acc, const xxh_u8* XXH_RESTRICT secret) 3720 { 3721 return XXH3_mul128_fold64( 3722 acc[0] ^ XXH_readLE64(secret), 3723 acc[1] ^ XXH_readLE64(secret+8) ); 3724 } 3725 3726 static XXH64_hash_t 3727 XXH3_mergeAccs(const xxh_u64* XXH_RESTRICT acc, const xxh_u8* XXH_RESTRICT secret, xxh_u64 start) 3728 { 3729 xxh_u64 result64 = start; 3730 size_t i = 0; 3731 3732 for (i = 0; i < 4; i++) { 3733 result64 += XXH3_mix2Accs(acc+2*i, secret + 16*i); 3734 #if defined(__clang__) /* Clang */ \ 3735 && (defined(__arm__) || defined(__thumb__)) /* ARMv7 */ \ 3736 && (defined(__ARM_NEON) || defined(__ARM_NEON__)) /* NEON */ \ 3737 && !defined(XXH_ENABLE_AUTOVECTORIZE) /* Define to disable */ 3738 /* 3739 * UGLY HACK: 3740 * Prevent autovectorization on Clang ARMv7-a. Exact same problem as 3741 * the one in XXH3_len_129to240_64b. Speeds up shorter keys > 240b. 3742 * XXH3_64bits, len == 256, Snapdragon 835: 3743 * without hack: 2063.7 MB/s 3744 * with hack: 2560.7 MB/s 3745 */ 3746 __asm__("" : "+r" (result64)); 3747 #endif 3748 } 3749 3750 return XXH3_avalanche(result64); 3751 } 3752 3753 #define XXH3_INIT_ACC { XXH_PRIME32_3, XXH_PRIME64_1, XXH_PRIME64_2, XXH_PRIME64_3, \ 3754 XXH_PRIME64_4, XXH_PRIME32_2, XXH_PRIME64_5, XXH_PRIME32_1 } 3755 3756 XXH_FORCE_INLINE XXH64_hash_t 3757 XXH3_hashLong_64b_internal(const void* XXH_RESTRICT input, size_t len, 3758 const void* XXH_RESTRICT secret, size_t secretSize, 3759 XXH3_f_accumulate_512 f_acc512, 3760 XXH3_f_scrambleAcc f_scramble) 3761 { 3762 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64 acc[XXH_ACC_NB] = XXH3_INIT_ACC; 3763 3764 XXH3_hashLong_internal_loop(acc, (const xxh_u8*)input, len, (const xxh_u8*)secret, secretSize, f_acc512, f_scramble); 3765 3766 /* converge into final hash */ 3767 XXH_STATIC_ASSERT(sizeof(acc) == 64); 3768 /* do not align on 8, so that the secret is different from the accumulator */ 3769 #define XXH_SECRET_MERGEACCS_START 11 3770 XXH_ASSERT(secretSize >= sizeof(acc) + XXH_SECRET_MERGEACCS_START); 3771 return XXH3_mergeAccs(acc, (const xxh_u8*)secret + XXH_SECRET_MERGEACCS_START, (xxh_u64)len * XXH_PRIME64_1); 3772 } 3773 3774 /* 3775 * It's important for performance that XXH3_hashLong is not inlined. 3776 */ 3777 XXH_NO_INLINE XXH64_hash_t 3778 XXH3_hashLong_64b_withSecret(const void* XXH_RESTRICT input, size_t len, 3779 XXH64_hash_t seed64, const xxh_u8* XXH_RESTRICT secret, size_t secretLen) 3780 { 3781 (void)seed64; 3782 return XXH3_hashLong_64b_internal(input, len, secret, secretLen, XXH3_accumulate_512, XXH3_scrambleAcc); 3783 } 3784 3785 /* 3786 * It's important for performance that XXH3_hashLong is not inlined. 3787 * Since the function is not inlined, the compiler may not be able to understand that, 3788 * in some scenarios, its `secret` argument is actually a compile time constant. 3789 * This variant enforces that the compiler can detect that, 3790 * and uses this opportunity to streamline the generated code for better performance. 3791 */ 3792 XXH_NO_INLINE XXH64_hash_t 3793 XXH3_hashLong_64b_default(const void* XXH_RESTRICT input, size_t len, 3794 XXH64_hash_t seed64, const xxh_u8* XXH_RESTRICT secret, size_t secretLen) 3795 { 3796 (void)seed64; (void)secret; (void)secretLen; 3797 return XXH3_hashLong_64b_internal(input, len, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_accumulate_512, XXH3_scrambleAcc); 3798 } 3799 3800 /* 3801 * XXH3_hashLong_64b_withSeed(): 3802 * Generate a custom key based on alteration of default XXH3_kSecret with the seed, 3803 * and then use this key for long mode hashing. 3804 * 3805 * This operation is decently fast but nonetheless costs a little bit of time. 3806 * Try to avoid it whenever possible (typically when seed==0). 3807 * 3808 * It's important for performance that XXH3_hashLong is not inlined. Not sure 3809 * why (uop cache maybe?), but the difference is large and easily measurable. 3810 */ 3811 XXH_FORCE_INLINE XXH64_hash_t 3812 XXH3_hashLong_64b_withSeed_internal(const void* input, size_t len, 3813 XXH64_hash_t seed, 3814 XXH3_f_accumulate_512 f_acc512, 3815 XXH3_f_scrambleAcc f_scramble, 3816 XXH3_f_initCustomSecret f_initSec) 3817 { 3818 if (seed == 0) 3819 return XXH3_hashLong_64b_internal(input, len, 3820 XXH3_kSecret, sizeof(XXH3_kSecret), 3821 f_acc512, f_scramble); 3822 { XXH_ALIGN(XXH_SEC_ALIGN) xxh_u8 secret[XXH_SECRET_DEFAULT_SIZE]; 3823 f_initSec(secret, seed); 3824 return XXH3_hashLong_64b_internal(input, len, secret, sizeof(secret), 3825 f_acc512, f_scramble); 3826 } 3827 } 3828 3829 /* 3830 * It's important for performance that XXH3_hashLong is not inlined. 3831 */ 3832 XXH_NO_INLINE XXH64_hash_t 3833 XXH3_hashLong_64b_withSeed(const void* input, size_t len, 3834 XXH64_hash_t seed, const xxh_u8* secret, size_t secretLen) 3835 { 3836 (void)secret; (void)secretLen; 3837 return XXH3_hashLong_64b_withSeed_internal(input, len, seed, 3838 XXH3_accumulate_512, XXH3_scrambleAcc, XXH3_initCustomSecret); 3839 } 3840 3841 3842 typedef XXH64_hash_t (*XXH3_hashLong64_f)(const void* XXH_RESTRICT, size_t, 3843 XXH64_hash_t, const xxh_u8* XXH_RESTRICT, size_t); 3844 3845 XXH_FORCE_INLINE XXH64_hash_t 3846 XXH3_64bits_internal(const void* XXH_RESTRICT input, size_t len, 3847 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen, 3848 XXH3_hashLong64_f f_hashLong) 3849 { 3850 XXH_ASSERT(secretLen >= XXH3_SECRET_SIZE_MIN); 3851 /* 3852 * If an action is to be taken if `secretLen` condition is not respected, 3853 * it should be done here. 3854 * For now, it's a contract pre-condition. 3855 * Adding a check and a branch here would cost performance at every hash. 3856 * Also, note that function signature doesn't offer room to return an error. 3857 */ 3858 if (len <= 16) 3859 return XXH3_len_0to16_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, seed64); 3860 if (len <= 128) 3861 return XXH3_len_17to128_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64); 3862 if (len <= XXH3_MIDSIZE_MAX) 3863 return XXH3_len_129to240_64b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64); 3864 return f_hashLong(input, len, seed64, (const xxh_u8*)secret, secretLen); 3865 } 3866 3867 3868 /* === Public entry point === */ 3869 3870 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits(const void* input, size_t len) 3871 { 3872 return XXH3_64bits_internal(input, len, 0, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_hashLong_64b_default); 3873 } 3874 3875 XXH_PUBLIC_API XXH64_hash_t 3876 XXH3_64bits_withSecret(const void* input, size_t len, const void* secret, size_t secretSize) 3877 { 3878 return XXH3_64bits_internal(input, len, 0, secret, secretSize, XXH3_hashLong_64b_withSecret); 3879 } 3880 3881 XXH_PUBLIC_API XXH64_hash_t 3882 XXH3_64bits_withSeed(const void* input, size_t len, XXH64_hash_t seed) 3883 { 3884 return XXH3_64bits_internal(input, len, seed, XXH3_kSecret, sizeof(XXH3_kSecret), XXH3_hashLong_64b_withSeed); 3885 } 3886 3887 3888 /* === XXH3 streaming === */ 3889 3890 /* 3891 * Malloc's a pointer that is always aligned to align. 3892 * 3893 * This must be freed with `XXH_alignedFree()`. 3894 * 3895 * malloc typically guarantees 16 byte alignment on 64-bit systems and 8 byte 3896 * alignment on 32-bit. This isn't enough for the 32 byte aligned loads in AVX2 3897 * or on 32-bit, the 16 byte aligned loads in SSE2 and NEON. 3898 * 3899 * This underalignment previously caused a rather obvious crash which went 3900 * completely unnoticed due to XXH3_createState() not actually being tested. 3901 * Credit to RedSpah for noticing this bug. 3902 * 3903 * The alignment is done manually: Functions like posix_memalign or _mm_malloc 3904 * are avoided: To maintain portability, we would have to write a fallback 3905 * like this anyways, and besides, testing for the existence of library 3906 * functions without relying on external build tools is impossible. 3907 * 3908 * The method is simple: Overallocate, manually align, and store the offset 3909 * to the original behind the returned pointer. 3910 * 3911 * Align must be a power of 2 and 8 <= align <= 128. 3912 */ 3913 static void* XXH_alignedMalloc(size_t s, size_t align) 3914 { 3915 XXH_ASSERT(align <= 128 && align >= 8); /* range check */ 3916 XXH_ASSERT((align & (align-1)) == 0); /* power of 2 */ 3917 XXH_ASSERT(s != 0 && s < (s + align)); /* empty/overflow */ 3918 { /* Overallocate to make room for manual realignment and an offset byte */ 3919 xxh_u8* base = (xxh_u8*)XXH_malloc(s + align); 3920 if (base != NULL) { 3921 /* 3922 * Get the offset needed to align this pointer. 3923 * 3924 * Even if the returned pointer is aligned, there will always be 3925 * at least one byte to store the offset to the original pointer. 3926 */ 3927 size_t offset = align - ((size_t)base & (align - 1)); /* base % align */ 3928 /* Add the offset for the now-aligned pointer */ 3929 xxh_u8* ptr = base + offset; 3930 3931 XXH_ASSERT((size_t)ptr % align == 0); 3932 3933 /* Store the offset immediately before the returned pointer. */ 3934 ptr[-1] = (xxh_u8)offset; 3935 return ptr; 3936 } 3937 return NULL; 3938 } 3939 } 3940 /* 3941 * Frees an aligned pointer allocated by XXH_alignedMalloc(). Don't pass 3942 * normal malloc'd pointers, XXH_alignedMalloc has a specific data layout. 3943 */ 3944 static void XXH_alignedFree(void* p) 3945 { 3946 if (p != NULL) { 3947 xxh_u8* ptr = (xxh_u8*)p; 3948 /* Get the offset byte we added in XXH_malloc. */ 3949 xxh_u8 offset = ptr[-1]; 3950 /* Free the original malloc'd pointer */ 3951 xxh_u8* base = ptr - offset; 3952 XXH_free(base); 3953 } 3954 } 3955 XXH_PUBLIC_API XXH3_state_t* XXH3_createState(void) 3956 { 3957 XXH3_state_t* const state = (XXH3_state_t*)XXH_alignedMalloc(sizeof(XXH3_state_t), 64); 3958 if (state==NULL) return NULL; 3959 XXH3_INITSTATE(state); 3960 return state; 3961 } 3962 3963 XXH_PUBLIC_API XXH_errorcode XXH3_freeState(XXH3_state_t* statePtr) 3964 { 3965 XXH_alignedFree(statePtr); 3966 return XXH_OK; 3967 } 3968 3969 XXH_PUBLIC_API void 3970 XXH3_copyState(XXH3_state_t* dst_state, const XXH3_state_t* src_state) 3971 { 3972 memcpy(dst_state, src_state, sizeof(*dst_state)); 3973 } 3974 3975 static void 3976 XXH3_64bits_reset_internal(XXH3_state_t* statePtr, 3977 XXH64_hash_t seed, 3978 const void* secret, size_t secretSize) 3979 { 3980 size_t const initStart = offsetof(XXH3_state_t, bufferedSize); 3981 size_t const initLength = offsetof(XXH3_state_t, nbStripesPerBlock) - initStart; 3982 XXH_ASSERT(offsetof(XXH3_state_t, nbStripesPerBlock) > initStart); 3983 XXH_ASSERT(statePtr != NULL); 3984 /* set members from bufferedSize to nbStripesPerBlock (excluded) to 0 */ 3985 memset((char*)statePtr + initStart, 0, initLength); 3986 statePtr->acc[0] = XXH_PRIME32_3; 3987 statePtr->acc[1] = XXH_PRIME64_1; 3988 statePtr->acc[2] = XXH_PRIME64_2; 3989 statePtr->acc[3] = XXH_PRIME64_3; 3990 statePtr->acc[4] = XXH_PRIME64_4; 3991 statePtr->acc[5] = XXH_PRIME32_2; 3992 statePtr->acc[6] = XXH_PRIME64_5; 3993 statePtr->acc[7] = XXH_PRIME32_1; 3994 statePtr->seed = seed; 3995 statePtr->extSecret = (const unsigned char*)secret; 3996 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); 3997 statePtr->secretLimit = secretSize - XXH_STRIPE_LEN; 3998 statePtr->nbStripesPerBlock = statePtr->secretLimit / XXH_SECRET_CONSUME_RATE; 3999 } 4000 4001 XXH_PUBLIC_API XXH_errorcode 4002 XXH3_64bits_reset(XXH3_state_t* statePtr) 4003 { 4004 if (statePtr == NULL) return XXH_ERROR; 4005 XXH3_64bits_reset_internal(statePtr, 0, XXH3_kSecret, XXH_SECRET_DEFAULT_SIZE); 4006 return XXH_OK; 4007 } 4008 4009 XXH_PUBLIC_API XXH_errorcode 4010 XXH3_64bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize) 4011 { 4012 if (statePtr == NULL) return XXH_ERROR; 4013 XXH3_64bits_reset_internal(statePtr, 0, secret, secretSize); 4014 if (secret == NULL) return XXH_ERROR; 4015 if (secretSize < XXH3_SECRET_SIZE_MIN) return XXH_ERROR; 4016 return XXH_OK; 4017 } 4018 4019 XXH_PUBLIC_API XXH_errorcode 4020 XXH3_64bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed) 4021 { 4022 if (statePtr == NULL) return XXH_ERROR; 4023 if (seed==0) return XXH3_64bits_reset(statePtr); 4024 if (seed != statePtr->seed) XXH3_initCustomSecret(statePtr->customSecret, seed); 4025 XXH3_64bits_reset_internal(statePtr, seed, NULL, XXH_SECRET_DEFAULT_SIZE); 4026 return XXH_OK; 4027 } 4028 4029 /* Note : when XXH3_consumeStripes() is invoked, 4030 * there must be a guarantee that at least one more byte must be consumed from input 4031 * so that the function can blindly consume all stripes using the "normal" secret segment */ 4032 XXH_FORCE_INLINE void 4033 XXH3_consumeStripes(xxh_u64* XXH_RESTRICT acc, 4034 size_t* XXH_RESTRICT nbStripesSoFarPtr, size_t nbStripesPerBlock, 4035 const xxh_u8* XXH_RESTRICT input, size_t nbStripes, 4036 const xxh_u8* XXH_RESTRICT secret, size_t secretLimit, 4037 XXH3_f_accumulate_512 f_acc512, 4038 XXH3_f_scrambleAcc f_scramble) 4039 { 4040 XXH_ASSERT(nbStripes <= nbStripesPerBlock); /* can handle max 1 scramble per invocation */ 4041 XXH_ASSERT(*nbStripesSoFarPtr < nbStripesPerBlock); 4042 if (nbStripesPerBlock - *nbStripesSoFarPtr <= nbStripes) { 4043 /* need a scrambling operation */ 4044 size_t const nbStripesToEndofBlock = nbStripesPerBlock - *nbStripesSoFarPtr; 4045 size_t const nbStripesAfterBlock = nbStripes - nbStripesToEndofBlock; 4046 XXH3_accumulate(acc, input, secret + nbStripesSoFarPtr[0] * XXH_SECRET_CONSUME_RATE, nbStripesToEndofBlock, f_acc512); 4047 f_scramble(acc, secret + secretLimit); 4048 XXH3_accumulate(acc, input + nbStripesToEndofBlock * XXH_STRIPE_LEN, secret, nbStripesAfterBlock, f_acc512); 4049 *nbStripesSoFarPtr = nbStripesAfterBlock; 4050 } else { 4051 XXH3_accumulate(acc, input, secret + nbStripesSoFarPtr[0] * XXH_SECRET_CONSUME_RATE, nbStripes, f_acc512); 4052 *nbStripesSoFarPtr += nbStripes; 4053 } 4054 } 4055 4056 /* 4057 * Both XXH3_64bits_update and XXH3_128bits_update use this routine. 4058 */ 4059 XXH_FORCE_INLINE XXH_errorcode 4060 XXH3_update(XXH3_state_t* state, 4061 const xxh_u8* input, size_t len, 4062 XXH3_f_accumulate_512 f_acc512, 4063 XXH3_f_scrambleAcc f_scramble) 4064 { 4065 if (input==NULL) 4066 #if defined(XXH_ACCEPT_NULL_INPUT_POINTER) && (XXH_ACCEPT_NULL_INPUT_POINTER>=1) 4067 return XXH_OK; 4068 #else 4069 return XXH_ERROR; 4070 #endif 4071 4072 { const xxh_u8* const bEnd = input + len; 4073 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret; 4074 4075 state->totalLen += len; 4076 4077 if (state->bufferedSize + len <= XXH3_INTERNALBUFFER_SIZE) { /* fill in tmp buffer */ 4078 XXH_memcpy(state->buffer + state->bufferedSize, input, len); 4079 state->bufferedSize += (XXH32_hash_t)len; 4080 return XXH_OK; 4081 } 4082 /* total input is now > XXH3_INTERNALBUFFER_SIZE */ 4083 4084 #define XXH3_INTERNALBUFFER_STRIPES (XXH3_INTERNALBUFFER_SIZE / XXH_STRIPE_LEN) 4085 XXH_STATIC_ASSERT(XXH3_INTERNALBUFFER_SIZE % XXH_STRIPE_LEN == 0); /* clean multiple */ 4086 4087 /* 4088 * Internal buffer is partially filled (always, except at beginning) 4089 * Complete it, then consume it. 4090 */ 4091 if (state->bufferedSize) { 4092 size_t const loadSize = XXH3_INTERNALBUFFER_SIZE - state->bufferedSize; 4093 XXH_memcpy(state->buffer + state->bufferedSize, input, loadSize); 4094 input += loadSize; 4095 XXH3_consumeStripes(state->acc, 4096 &state->nbStripesSoFar, state->nbStripesPerBlock, 4097 state->buffer, XXH3_INTERNALBUFFER_STRIPES, 4098 secret, state->secretLimit, 4099 f_acc512, f_scramble); 4100 state->bufferedSize = 0; 4101 } 4102 XXH_ASSERT(input < bEnd); 4103 4104 /* Consume input by a multiple of internal buffer size */ 4105 if (input+XXH3_INTERNALBUFFER_SIZE < bEnd) { 4106 const xxh_u8* const limit = bEnd - XXH3_INTERNALBUFFER_SIZE; 4107 do { 4108 XXH3_consumeStripes(state->acc, 4109 &state->nbStripesSoFar, state->nbStripesPerBlock, 4110 input, XXH3_INTERNALBUFFER_STRIPES, 4111 secret, state->secretLimit, 4112 f_acc512, f_scramble); 4113 input += XXH3_INTERNALBUFFER_SIZE; 4114 } while (input<limit); 4115 /* for last partial stripe */ 4116 memcpy(state->buffer + sizeof(state->buffer) - XXH_STRIPE_LEN, input - XXH_STRIPE_LEN, XXH_STRIPE_LEN); 4117 } 4118 XXH_ASSERT(input < bEnd); 4119 4120 /* Some remaining input (always) : buffer it */ 4121 XXH_memcpy(state->buffer, input, (size_t)(bEnd-input)); 4122 state->bufferedSize = (XXH32_hash_t)(bEnd-input); 4123 } 4124 4125 return XXH_OK; 4126 } 4127 4128 XXH_PUBLIC_API XXH_errorcode 4129 XXH3_64bits_update(XXH3_state_t* state, const void* input, size_t len) 4130 { 4131 return XXH3_update(state, (const xxh_u8*)input, len, 4132 XXH3_accumulate_512, XXH3_scrambleAcc); 4133 } 4134 4135 4136 XXH_FORCE_INLINE void 4137 XXH3_digest_long (XXH64_hash_t* acc, 4138 const XXH3_state_t* state, 4139 const unsigned char* secret) 4140 { 4141 /* 4142 * Digest on a local copy. This way, the state remains unaltered, and it can 4143 * continue ingesting more input afterwards. 4144 */ 4145 memcpy(acc, state->acc, sizeof(state->acc)); 4146 if (state->bufferedSize >= XXH_STRIPE_LEN) { 4147 size_t const nbStripes = (state->bufferedSize - 1) / XXH_STRIPE_LEN; 4148 size_t nbStripesSoFar = state->nbStripesSoFar; 4149 XXH3_consumeStripes(acc, 4150 &nbStripesSoFar, state->nbStripesPerBlock, 4151 state->buffer, nbStripes, 4152 secret, state->secretLimit, 4153 XXH3_accumulate_512, XXH3_scrambleAcc); 4154 /* last stripe */ 4155 XXH3_accumulate_512(acc, 4156 state->buffer + state->bufferedSize - XXH_STRIPE_LEN, 4157 secret + state->secretLimit - XXH_SECRET_LASTACC_START); 4158 } else { /* bufferedSize < XXH_STRIPE_LEN */ 4159 xxh_u8 lastStripe[XXH_STRIPE_LEN]; 4160 size_t const catchupSize = XXH_STRIPE_LEN - state->bufferedSize; 4161 XXH_ASSERT(state->bufferedSize > 0); /* there is always some input buffered */ 4162 memcpy(lastStripe, state->buffer + sizeof(state->buffer) - catchupSize, catchupSize); 4163 memcpy(lastStripe + catchupSize, state->buffer, state->bufferedSize); 4164 XXH3_accumulate_512(acc, 4165 lastStripe, 4166 secret + state->secretLimit - XXH_SECRET_LASTACC_START); 4167 } 4168 } 4169 4170 XXH_PUBLIC_API XXH64_hash_t XXH3_64bits_digest (const XXH3_state_t* state) 4171 { 4172 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret; 4173 if (state->totalLen > XXH3_MIDSIZE_MAX) { 4174 XXH_ALIGN(XXH_ACC_ALIGN) XXH64_hash_t acc[XXH_ACC_NB]; 4175 XXH3_digest_long(acc, state, secret); 4176 return XXH3_mergeAccs(acc, 4177 secret + XXH_SECRET_MERGEACCS_START, 4178 (xxh_u64)state->totalLen * XXH_PRIME64_1); 4179 } 4180 /* totalLen <= XXH3_MIDSIZE_MAX: digesting a short input */ 4181 if (state->seed) 4182 return XXH3_64bits_withSeed(state->buffer, (size_t)state->totalLen, state->seed); 4183 return XXH3_64bits_withSecret(state->buffer, (size_t)(state->totalLen), 4184 secret, state->secretLimit + XXH_STRIPE_LEN); 4185 } 4186 4187 4188 #define XXH_MIN(x, y) (((x) > (y)) ? (y) : (x)) 4189 4190 XXH_PUBLIC_API void 4191 XXH3_generateSecret(void* secretBuffer, const void* customSeed, size_t customSeedSize) 4192 { 4193 XXH_ASSERT(secretBuffer != NULL); 4194 if (customSeedSize == 0) { 4195 memcpy(secretBuffer, XXH3_kSecret, XXH_SECRET_DEFAULT_SIZE); 4196 return; 4197 } 4198 XXH_ASSERT(customSeed != NULL); 4199 4200 { size_t const segmentSize = sizeof(XXH128_hash_t); 4201 size_t const nbSegments = XXH_SECRET_DEFAULT_SIZE / segmentSize; 4202 XXH128_canonical_t scrambler; 4203 XXH64_hash_t seeds[12]; 4204 size_t segnb; 4205 XXH_ASSERT(nbSegments == 12); 4206 XXH_ASSERT(segmentSize * nbSegments == XXH_SECRET_DEFAULT_SIZE); /* exact multiple */ 4207 XXH128_canonicalFromHash(&scrambler, XXH128(customSeed, customSeedSize, 0)); 4208 4209 /* 4210 * Copy customSeed to seeds[], truncating or repeating as necessary. 4211 */ 4212 { size_t toFill = XXH_MIN(customSeedSize, sizeof(seeds)); 4213 size_t filled = toFill; 4214 memcpy(seeds, customSeed, toFill); 4215 while (filled < sizeof(seeds)) { 4216 toFill = XXH_MIN(filled, sizeof(seeds) - filled); 4217 memcpy((char*)seeds + filled, seeds, toFill); 4218 filled += toFill; 4219 } } 4220 4221 /* generate secret */ 4222 memcpy(secretBuffer, &scrambler, sizeof(scrambler)); 4223 for (segnb=1; segnb < nbSegments; segnb++) { 4224 size_t const segmentStart = segnb * segmentSize; 4225 XXH128_canonical_t segment; 4226 XXH128_canonicalFromHash(&segment, 4227 XXH128(&scrambler, sizeof(scrambler), XXH_readLE64(seeds + segnb) + segnb) ); 4228 memcpy((char*)secretBuffer + segmentStart, &segment, sizeof(segment)); 4229 } } 4230 } 4231 4232 4233 /* ========================================== 4234 * XXH3 128 bits (a.k.a XXH128) 4235 * ========================================== 4236 * XXH3's 128-bit variant has better mixing and strength than the 64-bit variant, 4237 * even without counting the significantly larger output size. 4238 * 4239 * For example, extra steps are taken to avoid the seed-dependent collisions 4240 * in 17-240 byte inputs (See XXH3_mix16B and XXH128_mix32B). 4241 * 4242 * This strength naturally comes at the cost of some speed, especially on short 4243 * lengths. Note that longer hashes are about as fast as the 64-bit version 4244 * due to it using only a slight modification of the 64-bit loop. 4245 * 4246 * XXH128 is also more oriented towards 64-bit machines. It is still extremely 4247 * fast for a _128-bit_ hash on 32-bit (it usually clears XXH64). 4248 */ 4249 4250 XXH_FORCE_INLINE XXH128_hash_t 4251 XXH3_len_1to3_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 4252 { 4253 /* A doubled version of 1to3_64b with different constants. */ 4254 XXH_ASSERT(input != NULL); 4255 XXH_ASSERT(1 <= len && len <= 3); 4256 XXH_ASSERT(secret != NULL); 4257 /* 4258 * len = 1: combinedl = { input[0], 0x01, input[0], input[0] } 4259 * len = 2: combinedl = { input[1], 0x02, input[0], input[1] } 4260 * len = 3: combinedl = { input[2], 0x03, input[0], input[1] } 4261 */ 4262 { xxh_u8 const c1 = input[0]; 4263 xxh_u8 const c2 = input[len >> 1]; 4264 xxh_u8 const c3 = input[len - 1]; 4265 xxh_u32 const combinedl = ((xxh_u32)c1 <<16) | ((xxh_u32)c2 << 24) 4266 | ((xxh_u32)c3 << 0) | ((xxh_u32)len << 8); 4267 xxh_u32 const combinedh = XXH_rotl32(XXH_swap32(combinedl), 13); 4268 xxh_u64 const bitflipl = (XXH_readLE32(secret) ^ XXH_readLE32(secret+4)) + seed; 4269 xxh_u64 const bitfliph = (XXH_readLE32(secret+8) ^ XXH_readLE32(secret+12)) - seed; 4270 xxh_u64 const keyed_lo = (xxh_u64)combinedl ^ bitflipl; 4271 xxh_u64 const keyed_hi = (xxh_u64)combinedh ^ bitfliph; 4272 XXH128_hash_t h128; 4273 h128.low64 = XXH64_avalanche(keyed_lo); 4274 h128.high64 = XXH64_avalanche(keyed_hi); 4275 return h128; 4276 } 4277 } 4278 4279 XXH_FORCE_INLINE XXH128_hash_t 4280 XXH3_len_4to8_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 4281 { 4282 XXH_ASSERT(input != NULL); 4283 XXH_ASSERT(secret != NULL); 4284 XXH_ASSERT(4 <= len && len <= 8); 4285 seed ^= (xxh_u64)XXH_swap32((xxh_u32)seed) << 32; 4286 { xxh_u32 const input_lo = XXH_readLE32(input); 4287 xxh_u32 const input_hi = XXH_readLE32(input + len - 4); 4288 xxh_u64 const input_64 = input_lo + ((xxh_u64)input_hi << 32); 4289 xxh_u64 const bitflip = (XXH_readLE64(secret+16) ^ XXH_readLE64(secret+24)) + seed; 4290 xxh_u64 const keyed = input_64 ^ bitflip; 4291 4292 /* Shift len to the left to ensure it is even, this avoids even multiplies. */ 4293 XXH128_hash_t m128 = XXH_mult64to128(keyed, XXH_PRIME64_1 + (len << 2)); 4294 4295 m128.high64 += (m128.low64 << 1); 4296 m128.low64 ^= (m128.high64 >> 3); 4297 4298 m128.low64 = XXH_xorshift64(m128.low64, 35); 4299 m128.low64 *= 0x9FB21C651E98DF25ULL; 4300 m128.low64 = XXH_xorshift64(m128.low64, 28); 4301 m128.high64 = XXH3_avalanche(m128.high64); 4302 return m128; 4303 } 4304 } 4305 4306 XXH_FORCE_INLINE XXH128_hash_t 4307 XXH3_len_9to16_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 4308 { 4309 XXH_ASSERT(input != NULL); 4310 XXH_ASSERT(secret != NULL); 4311 XXH_ASSERT(9 <= len && len <= 16); 4312 { xxh_u64 const bitflipl = (XXH_readLE64(secret+32) ^ XXH_readLE64(secret+40)) - seed; 4313 xxh_u64 const bitfliph = (XXH_readLE64(secret+48) ^ XXH_readLE64(secret+56)) + seed; 4314 xxh_u64 const input_lo = XXH_readLE64(input); 4315 xxh_u64 input_hi = XXH_readLE64(input + len - 8); 4316 XXH128_hash_t m128 = XXH_mult64to128(input_lo ^ input_hi ^ bitflipl, XXH_PRIME64_1); 4317 /* 4318 * Put len in the middle of m128 to ensure that the length gets mixed to 4319 * both the low and high bits in the 128x64 multiply below. 4320 */ 4321 m128.low64 += (xxh_u64)(len - 1) << 54; 4322 input_hi ^= bitfliph; 4323 /* 4324 * Add the high 32 bits of input_hi to the high 32 bits of m128, then 4325 * add the long product of the low 32 bits of input_hi and XXH_PRIME32_2 to 4326 * the high 64 bits of m128. 4327 * 4328 * The best approach to this operation is different on 32-bit and 64-bit. 4329 */ 4330 if (sizeof(void *) < sizeof(xxh_u64)) { /* 32-bit */ 4331 /* 4332 * 32-bit optimized version, which is more readable. 4333 * 4334 * On 32-bit, it removes an ADC and delays a dependency between the two 4335 * halves of m128.high64, but it generates an extra mask on 64-bit. 4336 */ 4337 m128.high64 += (input_hi & 0xFFFFFFFF00000000ULL) + XXH_mult32to64((xxh_u32)input_hi, XXH_PRIME32_2); 4338 } else { 4339 /* 4340 * 64-bit optimized (albeit more confusing) version. 4341 * 4342 * Uses some properties of addition and multiplication to remove the mask: 4343 * 4344 * Let: 4345 * a = input_hi.lo = (input_hi & 0x00000000FFFFFFFF) 4346 * b = input_hi.hi = (input_hi & 0xFFFFFFFF00000000) 4347 * c = XXH_PRIME32_2 4348 * 4349 * a + (b * c) 4350 * Inverse Property: x + y - x == y 4351 * a + (b * (1 + c - 1)) 4352 * Distributive Property: x * (y + z) == (x * y) + (x * z) 4353 * a + (b * 1) + (b * (c - 1)) 4354 * Identity Property: x * 1 == x 4355 * a + b + (b * (c - 1)) 4356 * 4357 * Substitute a, b, and c: 4358 * input_hi.hi + input_hi.lo + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1)) 4359 * 4360 * Since input_hi.hi + input_hi.lo == input_hi, we get this: 4361 * input_hi + ((xxh_u64)input_hi.lo * (XXH_PRIME32_2 - 1)) 4362 */ 4363 m128.high64 += input_hi + XXH_mult32to64((xxh_u32)input_hi, XXH_PRIME32_2 - 1); 4364 } 4365 /* m128 ^= XXH_swap64(m128 >> 64); */ 4366 m128.low64 ^= XXH_swap64(m128.high64); 4367 4368 { /* 128x64 multiply: h128 = m128 * XXH_PRIME64_2; */ 4369 XXH128_hash_t h128 = XXH_mult64to128(m128.low64, XXH_PRIME64_2); 4370 h128.high64 += m128.high64 * XXH_PRIME64_2; 4371 4372 h128.low64 = XXH3_avalanche(h128.low64); 4373 h128.high64 = XXH3_avalanche(h128.high64); 4374 return h128; 4375 } } 4376 } 4377 4378 /* 4379 * Assumption: `secret` size is >= XXH3_SECRET_SIZE_MIN 4380 */ 4381 XXH_FORCE_INLINE XXH128_hash_t 4382 XXH3_len_0to16_128b(const xxh_u8* input, size_t len, const xxh_u8* secret, XXH64_hash_t seed) 4383 { 4384 XXH_ASSERT(len <= 16); 4385 { if (len > 8) return XXH3_len_9to16_128b(input, len, secret, seed); 4386 if (len >= 4) return XXH3_len_4to8_128b(input, len, secret, seed); 4387 if (len) return XXH3_len_1to3_128b(input, len, secret, seed); 4388 { XXH128_hash_t h128; 4389 xxh_u64 const bitflipl = XXH_readLE64(secret+64) ^ XXH_readLE64(secret+72); 4390 xxh_u64 const bitfliph = XXH_readLE64(secret+80) ^ XXH_readLE64(secret+88); 4391 h128.low64 = XXH64_avalanche(seed ^ bitflipl); 4392 h128.high64 = XXH64_avalanche( seed ^ bitfliph); 4393 return h128; 4394 } } 4395 } 4396 4397 /* 4398 * A bit slower than XXH3_mix16B, but handles multiply by zero better. 4399 */ 4400 XXH_FORCE_INLINE XXH128_hash_t 4401 XXH128_mix32B(XXH128_hash_t acc, const xxh_u8* input_1, const xxh_u8* input_2, 4402 const xxh_u8* secret, XXH64_hash_t seed) 4403 { 4404 acc.low64 += XXH3_mix16B (input_1, secret+0, seed); 4405 acc.low64 ^= XXH_readLE64(input_2) + XXH_readLE64(input_2 + 8); 4406 acc.high64 += XXH3_mix16B (input_2, secret+16, seed); 4407 acc.high64 ^= XXH_readLE64(input_1) + XXH_readLE64(input_1 + 8); 4408 return acc; 4409 } 4410 4411 4412 XXH_FORCE_INLINE XXH128_hash_t 4413 XXH3_len_17to128_128b(const xxh_u8* XXH_RESTRICT input, size_t len, 4414 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 4415 XXH64_hash_t seed) 4416 { 4417 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize; 4418 XXH_ASSERT(16 < len && len <= 128); 4419 4420 { XXH128_hash_t acc; 4421 acc.low64 = len * XXH_PRIME64_1; 4422 acc.high64 = 0; 4423 if (len > 32) { 4424 if (len > 64) { 4425 if (len > 96) { 4426 acc = XXH128_mix32B(acc, input+48, input+len-64, secret+96, seed); 4427 } 4428 acc = XXH128_mix32B(acc, input+32, input+len-48, secret+64, seed); 4429 } 4430 acc = XXH128_mix32B(acc, input+16, input+len-32, secret+32, seed); 4431 } 4432 acc = XXH128_mix32B(acc, input, input+len-16, secret, seed); 4433 { XXH128_hash_t h128; 4434 h128.low64 = acc.low64 + acc.high64; 4435 h128.high64 = (acc.low64 * XXH_PRIME64_1) 4436 + (acc.high64 * XXH_PRIME64_4) 4437 + ((len - seed) * XXH_PRIME64_2); 4438 h128.low64 = XXH3_avalanche(h128.low64); 4439 h128.high64 = (XXH64_hash_t)0 - XXH3_avalanche(h128.high64); 4440 return h128; 4441 } 4442 } 4443 } 4444 4445 XXH_NO_INLINE XXH128_hash_t 4446 XXH3_len_129to240_128b(const xxh_u8* XXH_RESTRICT input, size_t len, 4447 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 4448 XXH64_hash_t seed) 4449 { 4450 XXH_ASSERT(secretSize >= XXH3_SECRET_SIZE_MIN); (void)secretSize; 4451 XXH_ASSERT(128 < len && len <= XXH3_MIDSIZE_MAX); 4452 4453 { XXH128_hash_t acc; 4454 int const nbRounds = (int)len / 32; 4455 int i; 4456 acc.low64 = len * XXH_PRIME64_1; 4457 acc.high64 = 0; 4458 for (i=0; i<4; i++) { 4459 acc = XXH128_mix32B(acc, 4460 input + (32 * i), 4461 input + (32 * i) + 16, 4462 secret + (32 * i), 4463 seed); 4464 } 4465 acc.low64 = XXH3_avalanche(acc.low64); 4466 acc.high64 = XXH3_avalanche(acc.high64); 4467 XXH_ASSERT(nbRounds >= 4); 4468 for (i=4 ; i < nbRounds; i++) { 4469 acc = XXH128_mix32B(acc, 4470 input + (32 * i), 4471 input + (32 * i) + 16, 4472 secret + XXH3_MIDSIZE_STARTOFFSET + (32 * (i - 4)), 4473 seed); 4474 } 4475 /* last bytes */ 4476 acc = XXH128_mix32B(acc, 4477 input + len - 16, 4478 input + len - 32, 4479 secret + XXH3_SECRET_SIZE_MIN - XXH3_MIDSIZE_LASTOFFSET - 16, 4480 0ULL - seed); 4481 4482 { XXH128_hash_t h128; 4483 h128.low64 = acc.low64 + acc.high64; 4484 h128.high64 = (acc.low64 * XXH_PRIME64_1) 4485 + (acc.high64 * XXH_PRIME64_4) 4486 + ((len - seed) * XXH_PRIME64_2); 4487 h128.low64 = XXH3_avalanche(h128.low64); 4488 h128.high64 = (XXH64_hash_t)0 - XXH3_avalanche(h128.high64); 4489 return h128; 4490 } 4491 } 4492 } 4493 4494 XXH_FORCE_INLINE XXH128_hash_t 4495 XXH3_hashLong_128b_internal(const void* XXH_RESTRICT input, size_t len, 4496 const xxh_u8* XXH_RESTRICT secret, size_t secretSize, 4497 XXH3_f_accumulate_512 f_acc512, 4498 XXH3_f_scrambleAcc f_scramble) 4499 { 4500 XXH_ALIGN(XXH_ACC_ALIGN) xxh_u64 acc[XXH_ACC_NB] = XXH3_INIT_ACC; 4501 4502 XXH3_hashLong_internal_loop(acc, (const xxh_u8*)input, len, secret, secretSize, f_acc512, f_scramble); 4503 4504 /* converge into final hash */ 4505 XXH_STATIC_ASSERT(sizeof(acc) == 64); 4506 XXH_ASSERT(secretSize >= sizeof(acc) + XXH_SECRET_MERGEACCS_START); 4507 { XXH128_hash_t h128; 4508 h128.low64 = XXH3_mergeAccs(acc, 4509 secret + XXH_SECRET_MERGEACCS_START, 4510 (xxh_u64)len * XXH_PRIME64_1); 4511 h128.high64 = XXH3_mergeAccs(acc, 4512 secret + secretSize 4513 - sizeof(acc) - XXH_SECRET_MERGEACCS_START, 4514 ~((xxh_u64)len * XXH_PRIME64_2)); 4515 return h128; 4516 } 4517 } 4518 4519 /* 4520 * It's important for performance that XXH3_hashLong is not inlined. 4521 */ 4522 XXH_NO_INLINE XXH128_hash_t 4523 XXH3_hashLong_128b_default(const void* XXH_RESTRICT input, size_t len, 4524 XXH64_hash_t seed64, 4525 const void* XXH_RESTRICT secret, size_t secretLen) 4526 { 4527 (void)seed64; (void)secret; (void)secretLen; 4528 return XXH3_hashLong_128b_internal(input, len, XXH3_kSecret, sizeof(XXH3_kSecret), 4529 XXH3_accumulate_512, XXH3_scrambleAcc); 4530 } 4531 4532 /* 4533 * It's important for performance that XXH3_hashLong is not inlined. 4534 */ 4535 XXH_NO_INLINE XXH128_hash_t 4536 XXH3_hashLong_128b_withSecret(const void* XXH_RESTRICT input, size_t len, 4537 XXH64_hash_t seed64, 4538 const void* XXH_RESTRICT secret, size_t secretLen) 4539 { 4540 (void)seed64; 4541 return XXH3_hashLong_128b_internal(input, len, (const xxh_u8*)secret, secretLen, 4542 XXH3_accumulate_512, XXH3_scrambleAcc); 4543 } 4544 4545 XXH_FORCE_INLINE XXH128_hash_t 4546 XXH3_hashLong_128b_withSeed_internal(const void* XXH_RESTRICT input, size_t len, 4547 XXH64_hash_t seed64, 4548 XXH3_f_accumulate_512 f_acc512, 4549 XXH3_f_scrambleAcc f_scramble, 4550 XXH3_f_initCustomSecret f_initSec) 4551 { 4552 if (seed64 == 0) 4553 return XXH3_hashLong_128b_internal(input, len, 4554 XXH3_kSecret, sizeof(XXH3_kSecret), 4555 f_acc512, f_scramble); 4556 { XXH_ALIGN(XXH_SEC_ALIGN) xxh_u8 secret[XXH_SECRET_DEFAULT_SIZE]; 4557 f_initSec(secret, seed64); 4558 return XXH3_hashLong_128b_internal(input, len, (const xxh_u8*)secret, sizeof(secret), 4559 f_acc512, f_scramble); 4560 } 4561 } 4562 4563 /* 4564 * It's important for performance that XXH3_hashLong is not inlined. 4565 */ 4566 XXH_NO_INLINE XXH128_hash_t 4567 XXH3_hashLong_128b_withSeed(const void* input, size_t len, 4568 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen) 4569 { 4570 (void)secret; (void)secretLen; 4571 return XXH3_hashLong_128b_withSeed_internal(input, len, seed64, 4572 XXH3_accumulate_512, XXH3_scrambleAcc, XXH3_initCustomSecret); 4573 } 4574 4575 typedef XXH128_hash_t (*XXH3_hashLong128_f)(const void* XXH_RESTRICT, size_t, 4576 XXH64_hash_t, const void* XXH_RESTRICT, size_t); 4577 4578 XXH_FORCE_INLINE XXH128_hash_t 4579 XXH3_128bits_internal(const void* input, size_t len, 4580 XXH64_hash_t seed64, const void* XXH_RESTRICT secret, size_t secretLen, 4581 XXH3_hashLong128_f f_hl128) 4582 { 4583 XXH_ASSERT(secretLen >= XXH3_SECRET_SIZE_MIN); 4584 /* 4585 * If an action is to be taken if `secret` conditions are not respected, 4586 * it should be done here. 4587 * For now, it's a contract pre-condition. 4588 * Adding a check and a branch here would cost performance at every hash. 4589 */ 4590 if (len <= 16) 4591 return XXH3_len_0to16_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, seed64); 4592 if (len <= 128) 4593 return XXH3_len_17to128_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64); 4594 if (len <= XXH3_MIDSIZE_MAX) 4595 return XXH3_len_129to240_128b((const xxh_u8*)input, len, (const xxh_u8*)secret, secretLen, seed64); 4596 return f_hl128(input, len, seed64, secret, secretLen); 4597 } 4598 4599 4600 /* === Public XXH128 API === */ 4601 4602 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits(const void* input, size_t len) 4603 { 4604 return XXH3_128bits_internal(input, len, 0, 4605 XXH3_kSecret, sizeof(XXH3_kSecret), 4606 XXH3_hashLong_128b_default); 4607 } 4608 4609 XXH_PUBLIC_API XXH128_hash_t 4610 XXH3_128bits_withSecret(const void* input, size_t len, const void* secret, size_t secretSize) 4611 { 4612 return XXH3_128bits_internal(input, len, 0, 4613 (const xxh_u8*)secret, secretSize, 4614 XXH3_hashLong_128b_withSecret); 4615 } 4616 4617 XXH_PUBLIC_API XXH128_hash_t 4618 XXH3_128bits_withSeed(const void* input, size_t len, XXH64_hash_t seed) 4619 { 4620 return XXH3_128bits_internal(input, len, seed, 4621 XXH3_kSecret, sizeof(XXH3_kSecret), 4622 XXH3_hashLong_128b_withSeed); 4623 } 4624 4625 XXH_PUBLIC_API XXH128_hash_t 4626 XXH128(const void* input, size_t len, XXH64_hash_t seed) 4627 { 4628 return XXH3_128bits_withSeed(input, len, seed); 4629 } 4630 4631 4632 /* === XXH3 128-bit streaming === */ 4633 4634 /* 4635 * All the functions are actually the same as for 64-bit streaming variant. 4636 * The only difference is the finalizatiom routine. 4637 */ 4638 4639 static void 4640 XXH3_128bits_reset_internal(XXH3_state_t* statePtr, 4641 XXH64_hash_t seed, 4642 const void* secret, size_t secretSize) 4643 { 4644 XXH3_64bits_reset_internal(statePtr, seed, secret, secretSize); 4645 } 4646 4647 XXH_PUBLIC_API XXH_errorcode 4648 XXH3_128bits_reset(XXH3_state_t* statePtr) 4649 { 4650 if (statePtr == NULL) return XXH_ERROR; 4651 XXH3_128bits_reset_internal(statePtr, 0, XXH3_kSecret, XXH_SECRET_DEFAULT_SIZE); 4652 return XXH_OK; 4653 } 4654 4655 XXH_PUBLIC_API XXH_errorcode 4656 XXH3_128bits_reset_withSecret(XXH3_state_t* statePtr, const void* secret, size_t secretSize) 4657 { 4658 if (statePtr == NULL) return XXH_ERROR; 4659 XXH3_128bits_reset_internal(statePtr, 0, secret, secretSize); 4660 if (secret == NULL) return XXH_ERROR; 4661 if (secretSize < XXH3_SECRET_SIZE_MIN) return XXH_ERROR; 4662 return XXH_OK; 4663 } 4664 4665 XXH_PUBLIC_API XXH_errorcode 4666 XXH3_128bits_reset_withSeed(XXH3_state_t* statePtr, XXH64_hash_t seed) 4667 { 4668 if (statePtr == NULL) return XXH_ERROR; 4669 if (seed==0) return XXH3_128bits_reset(statePtr); 4670 if (seed != statePtr->seed) XXH3_initCustomSecret(statePtr->customSecret, seed); 4671 XXH3_128bits_reset_internal(statePtr, seed, NULL, XXH_SECRET_DEFAULT_SIZE); 4672 return XXH_OK; 4673 } 4674 4675 XXH_PUBLIC_API XXH_errorcode 4676 XXH3_128bits_update(XXH3_state_t* state, const void* input, size_t len) 4677 { 4678 return XXH3_update(state, (const xxh_u8*)input, len, 4679 XXH3_accumulate_512, XXH3_scrambleAcc); 4680 } 4681 4682 XXH_PUBLIC_API XXH128_hash_t XXH3_128bits_digest (const XXH3_state_t* state) 4683 { 4684 const unsigned char* const secret = (state->extSecret == NULL) ? state->customSecret : state->extSecret; 4685 if (state->totalLen > XXH3_MIDSIZE_MAX) { 4686 XXH_ALIGN(XXH_ACC_ALIGN) XXH64_hash_t acc[XXH_ACC_NB]; 4687 XXH3_digest_long(acc, state, secret); 4688 XXH_ASSERT(state->secretLimit + XXH_STRIPE_LEN >= sizeof(acc) + XXH_SECRET_MERGEACCS_START); 4689 { XXH128_hash_t h128; 4690 h128.low64 = XXH3_mergeAccs(acc, 4691 secret + XXH_SECRET_MERGEACCS_START, 4692 (xxh_u64)state->totalLen * XXH_PRIME64_1); 4693 h128.high64 = XXH3_mergeAccs(acc, 4694 secret + state->secretLimit + XXH_STRIPE_LEN 4695 - sizeof(acc) - XXH_SECRET_MERGEACCS_START, 4696 ~((xxh_u64)state->totalLen * XXH_PRIME64_2)); 4697 return h128; 4698 } 4699 } 4700 /* len <= XXH3_MIDSIZE_MAX : short code */ 4701 if (state->seed) 4702 return XXH3_128bits_withSeed(state->buffer, (size_t)state->totalLen, state->seed); 4703 return XXH3_128bits_withSecret(state->buffer, (size_t)(state->totalLen), 4704 secret, state->secretLimit + XXH_STRIPE_LEN); 4705 } 4706 4707 /* 128-bit utility functions */ 4708 4709 #include <string.h> /* memcmp, memcpy */ 4710 4711 /* return : 1 is equal, 0 if different */ 4712 XXH_PUBLIC_API int XXH128_isEqual(XXH128_hash_t h1, XXH128_hash_t h2) 4713 { 4714 /* note : XXH128_hash_t is compact, it has no padding byte */ 4715 return !(memcmp(&h1, &h2, sizeof(h1))); 4716 } 4717 4718 /* This prototype is compatible with stdlib's qsort(). 4719 * return : >0 if *h128_1 > *h128_2 4720 * <0 if *h128_1 < *h128_2 4721 * =0 if *h128_1 == *h128_2 */ 4722 XXH_PUBLIC_API int XXH128_cmp(const void* h128_1, const void* h128_2) 4723 { 4724 XXH128_hash_t const h1 = *(const XXH128_hash_t*)h128_1; 4725 XXH128_hash_t const h2 = *(const XXH128_hash_t*)h128_2; 4726 int const hcmp = (h1.high64 > h2.high64) - (h2.high64 > h1.high64); 4727 /* note : bets that, in most cases, hash values are different */ 4728 if (hcmp) return hcmp; 4729 return (h1.low64 > h2.low64) - (h2.low64 > h1.low64); 4730 } 4731 4732 4733 /*====== Canonical representation ======*/ 4734 XXH_PUBLIC_API void 4735 XXH128_canonicalFromHash(XXH128_canonical_t* dst, XXH128_hash_t hash) 4736 { 4737 XXH_STATIC_ASSERT(sizeof(XXH128_canonical_t) == sizeof(XXH128_hash_t)); 4738 if (XXH_CPU_LITTLE_ENDIAN) { 4739 hash.high64 = XXH_swap64(hash.high64); 4740 hash.low64 = XXH_swap64(hash.low64); 4741 } 4742 memcpy(dst, &hash.high64, sizeof(hash.high64)); 4743 memcpy((char*)dst + sizeof(hash.high64), &hash.low64, sizeof(hash.low64)); 4744 } 4745 4746 XXH_PUBLIC_API XXH128_hash_t 4747 XXH128_hashFromCanonical(const XXH128_canonical_t* src) 4748 { 4749 XXH128_hash_t h; 4750 h.high64 = XXH_readBE64(src); 4751 h.low64 = XXH_readBE64(src->digest + 8); 4752 return h; 4753 } 4754 4755 /* Pop our optimization override from above */ 4756 #if XXH_VECTOR == XXH_AVX2 /* AVX2 */ \ 4757 && defined(__GNUC__) && !defined(__clang__) /* GCC, not Clang */ \ 4758 && defined(__OPTIMIZE__) && !defined(__OPTIMIZE_SIZE__) /* respect -O0 and -Os */ 4759 # pragma GCC pop_options 4760 #endif 4761 4762 #endif /* XXH_NO_LONG_LONG */ 4763 4764 4765 #endif /* XXH_IMPLEMENTATION */ 4766 4767 4768 #if defined (__cplusplus) 4769 } 4770 #endif 4771