1 /* 2 * xxHash - Extremely Fast Hash algorithm 3 * Copyright (C) 2012-2016, Yann Collet. 4 * 5 * BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php) 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions are 9 * met: 10 * 11 * * Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * * Redistributions in binary form must reproduce the above 14 * copyright notice, this list of conditions and the following disclaimer 15 * in the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 * 30 * This program is free software; you can redistribute it and/or modify it under 31 * the terms of the GNU General Public License version 2 as published by the 32 * Free Software Foundation. This program is dual-licensed; you may select 33 * either version 2 of the GNU General Public License ("GPL") or BSD license 34 * ("BSD"). 35 * 36 * You can contact the author at: 37 * - xxHash homepage: https://cyan4973.github.io/xxHash/ 38 * - xxHash source repository: https://github.com/Cyan4973/xxHash 39 */ 40 41 /* 42 * Notice extracted from xxHash homepage: 43 * 44 * xxHash is an extremely fast Hash algorithm, running at RAM speed limits. 45 * It also successfully passes all tests from the SMHasher suite. 46 * 47 * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2 48 * Duo @3GHz) 49 * 50 * Name Speed Q.Score Author 51 * xxHash 5.4 GB/s 10 52 * CrapWow 3.2 GB/s 2 Andrew 53 * MumurHash 3a 2.7 GB/s 10 Austin Appleby 54 * SpookyHash 2.0 GB/s 10 Bob Jenkins 55 * SBox 1.4 GB/s 9 Bret Mulvey 56 * Lookup3 1.2 GB/s 9 Bob Jenkins 57 * SuperFastHash 1.2 GB/s 1 Paul Hsieh 58 * CityHash64 1.05 GB/s 10 Pike & Alakuijala 59 * FNV 0.55 GB/s 5 Fowler, Noll, Vo 60 * CRC32 0.43 GB/s 9 61 * MD5-32 0.33 GB/s 10 Ronald L. Rivest 62 * SHA1-32 0.28 GB/s 10 63 * 64 * Q.Score is a measure of quality of the hash function. 65 * It depends on successfully passing SMHasher test set. 66 * 10 is a perfect score. 67 * 68 * A 64-bits version, named xxh64 offers much better speed, 69 * but for 64-bits applications only. 70 * Name Speed on 64 bits Speed on 32 bits 71 * xxh64 13.8 GB/s 1.9 GB/s 72 * xxh32 6.8 GB/s 6.0 GB/s 73 */ 74 75 #ifndef XXHASH_H 76 #define XXHASH_H 77 78 #include <linux/types.h> 79 80 #define XXH_API static inline __attribute__((unused)) 81 /*-**************************** 82 * Simple Hash Functions 83 *****************************/ 84 85 /** 86 * xxh32() - calculate the 32-bit hash of the input with a given seed. 87 * 88 * @input: The data to hash. 89 * @length: The length of the data to hash. 90 * @seed: The seed can be used to alter the result predictably. 91 * 92 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s 93 * 94 * Return: The 32-bit hash of the data. 95 */ 96 XXH_API uint32_t xxh32(const void *input, size_t length, uint32_t seed); 97 98 /** 99 * xxh64() - calculate the 64-bit hash of the input with a given seed. 100 * 101 * @input: The data to hash. 102 * @length: The length of the data to hash. 103 * @seed: The seed can be used to alter the result predictably. 104 * 105 * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems. 106 * 107 * Return: The 64-bit hash of the data. 108 */ 109 XXH_API uint64_t xxh64(const void *input, size_t length, uint64_t seed); 110 111 /** 112 * xxhash() - calculate wordsize hash of the input with a given seed 113 * @input: The data to hash. 114 * @length: The length of the data to hash. 115 * @seed: The seed can be used to alter the result predictably. 116 * 117 * If the hash does not need to be comparable between machines with 118 * different word sizes, this function will call whichever of xxh32() 119 * or xxh64() is faster. 120 * 121 * Return: wordsize hash of the data. 122 */ 123 124 static inline unsigned long xxhash(const void *input, size_t length, 125 uint64_t seed) 126 { 127 if (sizeof(size_t) == 8) 128 return xxh64(input, length, seed); 129 else 130 return xxh32(input, length, seed); 131 } 132 133 /*-**************************** 134 * Streaming Hash Functions 135 *****************************/ 136 137 /* 138 * These definitions are only meant to allow allocation of XXH state 139 * statically, on stack, or in a struct for example. 140 * Do not use members directly. 141 */ 142 143 /** 144 * struct xxh32_state - private xxh32 state, do not use members directly 145 */ 146 struct xxh32_state { 147 uint32_t total_len_32; 148 uint32_t large_len; 149 uint32_t v1; 150 uint32_t v2; 151 uint32_t v3; 152 uint32_t v4; 153 uint32_t mem32[4]; 154 uint32_t memsize; 155 }; 156 157 /** 158 * struct xxh32_state - private xxh64 state, do not use members directly 159 */ 160 struct xxh64_state { 161 uint64_t total_len; 162 uint64_t v1; 163 uint64_t v2; 164 uint64_t v3; 165 uint64_t v4; 166 uint64_t mem64[4]; 167 uint32_t memsize; 168 }; 169 170 /** 171 * xxh32_reset() - reset the xxh32 state to start a new hashing operation 172 * 173 * @state: The xxh32 state to reset. 174 * @seed: Initialize the hash state with this seed. 175 * 176 * Call this function on any xxh32_state to prepare for a new hashing operation. 177 */ 178 XXH_API void xxh32_reset(struct xxh32_state *state, uint32_t seed); 179 180 /** 181 * xxh32_update() - hash the data given and update the xxh32 state 182 * 183 * @state: The xxh32 state to update. 184 * @input: The data to hash. 185 * @length: The length of the data to hash. 186 * 187 * After calling xxh32_reset() call xxh32_update() as many times as necessary. 188 * 189 * Return: Zero on success, otherwise an error code. 190 */ 191 XXH_API int xxh32_update(struct xxh32_state *state, const void *input, size_t length); 192 193 /** 194 * xxh32_digest() - produce the current xxh32 hash 195 * 196 * @state: Produce the current xxh32 hash of this state. 197 * 198 * A hash value can be produced at any time. It is still possible to continue 199 * inserting input into the hash state after a call to xxh32_digest(), and 200 * generate new hashes later on, by calling xxh32_digest() again. 201 * 202 * Return: The xxh32 hash stored in the state. 203 */ 204 XXH_API uint32_t xxh32_digest(const struct xxh32_state *state); 205 206 /** 207 * xxh64_reset() - reset the xxh64 state to start a new hashing operation 208 * 209 * @state: The xxh64 state to reset. 210 * @seed: Initialize the hash state with this seed. 211 */ 212 XXH_API void xxh64_reset(struct xxh64_state *state, uint64_t seed); 213 214 /** 215 * xxh64_update() - hash the data given and update the xxh64 state 216 * @state: The xxh64 state to update. 217 * @input: The data to hash. 218 * @length: The length of the data to hash. 219 * 220 * After calling xxh64_reset() call xxh64_update() as many times as necessary. 221 * 222 * Return: Zero on success, otherwise an error code. 223 */ 224 XXH_API int xxh64_update(struct xxh64_state *state, const void *input, size_t length); 225 226 /** 227 * xxh64_digest() - produce the current xxh64 hash 228 * 229 * @state: Produce the current xxh64 hash of this state. 230 * 231 * A hash value can be produced at any time. It is still possible to continue 232 * inserting input into the hash state after a call to xxh64_digest(), and 233 * generate new hashes later on, by calling xxh64_digest() again. 234 * 235 * Return: The xxh64 hash stored in the state. 236 */ 237 XXH_API uint64_t xxh64_digest(const struct xxh64_state *state); 238 239 /*-************************** 240 * Utils 241 ***************************/ 242 243 /** 244 * xxh32_copy_state() - copy the source state into the destination state 245 * 246 * @src: The source xxh32 state. 247 * @dst: The destination xxh32 state. 248 */ 249 XXH_API void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src); 250 251 /** 252 * xxh64_copy_state() - copy the source state into the destination state 253 * 254 * @src: The source xxh64 state. 255 * @dst: The destination xxh64 state. 256 */ 257 XXH_API void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src); 258 259 /* 260 * xxHash - Extremely Fast Hash algorithm 261 * Copyright (C) 2012-2016, Yann Collet. 262 * 263 * BSD 2-Clause License (https://opensource.org/licenses/bsd-license.php) 264 * 265 * Redistribution and use in source and binary forms, with or without 266 * modification, are permitted provided that the following conditions are 267 * met: 268 * 269 * * Redistributions of source code must retain the above copyright 270 * notice, this list of conditions and the following disclaimer. 271 * * Redistributions in binary form must reproduce the above 272 * copyright notice, this list of conditions and the following disclaimer 273 * in the documentation and/or other materials provided with the 274 * distribution. 275 * 276 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 277 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 278 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 279 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 280 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 281 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 282 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 283 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 284 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 285 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 286 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 287 * 288 * This program is free software; you can redistribute it and/or modify it under 289 * the terms of the GNU General Public License version 2 as published by the 290 * Free Software Foundation. This program is dual-licensed; you may select 291 * either version 2 of the GNU General Public License ("GPL") or BSD license 292 * ("BSD"). 293 * 294 * You can contact the author at: 295 * - xxHash homepage: https://cyan4973.github.io/xxHash/ 296 * - xxHash source repository: https://github.com/Cyan4973/xxHash 297 */ 298 299 #include <asm/unaligned.h> 300 #include <linux/errno.h> 301 #include <linux/kernel.h> 302 #include <linux/module.h> 303 #include <linux/xxhash.h> 304 305 /*-************************************* 306 * Macros 307 **************************************/ 308 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r))) 309 #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r))) 310 311 #ifdef __LITTLE_ENDIAN 312 # define XXH_CPU_LITTLE_ENDIAN 1 313 #else 314 # define XXH_CPU_LITTLE_ENDIAN 0 315 #endif 316 317 /*-************************************* 318 * Constants 319 **************************************/ 320 static const uint32_t PRIME32_1 = 2654435761U; 321 static const uint32_t PRIME32_2 = 2246822519U; 322 static const uint32_t PRIME32_3 = 3266489917U; 323 static const uint32_t PRIME32_4 = 668265263U; 324 static const uint32_t PRIME32_5 = 374761393U; 325 326 static const uint64_t PRIME64_1 = 11400714785074694791ULL; 327 static const uint64_t PRIME64_2 = 14029467366897019727ULL; 328 static const uint64_t PRIME64_3 = 1609587929392839161ULL; 329 static const uint64_t PRIME64_4 = 9650029242287828579ULL; 330 static const uint64_t PRIME64_5 = 2870177450012600261ULL; 331 332 /*-************************** 333 * Utils 334 ***************************/ 335 XXH_API void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src) 336 { 337 __builtin_memcpy(dst, src, sizeof(*dst)); 338 } 339 340 XXH_API void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src) 341 { 342 __builtin_memcpy(dst, src, sizeof(*dst)); 343 } 344 345 /*-*************************** 346 * Simple Hash Functions 347 ****************************/ 348 static uint32_t xxh32_round(uint32_t seed, const uint32_t input) 349 { 350 seed += input * PRIME32_2; 351 seed = xxh_rotl32(seed, 13); 352 seed *= PRIME32_1; 353 return seed; 354 } 355 356 XXH_API uint32_t xxh32(const void *input, const size_t len, const uint32_t seed) 357 { 358 const uint8_t *p = (const uint8_t *)input; 359 const uint8_t *b_end = p + len; 360 uint32_t h32; 361 362 if (len >= 16) { 363 const uint8_t *const limit = b_end - 16; 364 uint32_t v1 = seed + PRIME32_1 + PRIME32_2; 365 uint32_t v2 = seed + PRIME32_2; 366 uint32_t v3 = seed + 0; 367 uint32_t v4 = seed - PRIME32_1; 368 369 do { 370 v1 = xxh32_round(v1, get_unaligned_le32(p)); 371 p += 4; 372 v2 = xxh32_round(v2, get_unaligned_le32(p)); 373 p += 4; 374 v3 = xxh32_round(v3, get_unaligned_le32(p)); 375 p += 4; 376 v4 = xxh32_round(v4, get_unaligned_le32(p)); 377 p += 4; 378 } while (p <= limit); 379 380 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) + 381 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18); 382 } else { 383 h32 = seed + PRIME32_5; 384 } 385 386 h32 += (uint32_t)len; 387 388 while (p + 4 <= b_end) { 389 h32 += get_unaligned_le32(p) * PRIME32_3; 390 h32 = xxh_rotl32(h32, 17) * PRIME32_4; 391 p += 4; 392 } 393 394 while (p < b_end) { 395 h32 += (*p) * PRIME32_5; 396 h32 = xxh_rotl32(h32, 11) * PRIME32_1; 397 p++; 398 } 399 400 h32 ^= h32 >> 15; 401 h32 *= PRIME32_2; 402 h32 ^= h32 >> 13; 403 h32 *= PRIME32_3; 404 h32 ^= h32 >> 16; 405 406 return h32; 407 } 408 409 static uint64_t xxh64_round(uint64_t acc, const uint64_t input) 410 { 411 acc += input * PRIME64_2; 412 acc = xxh_rotl64(acc, 31); 413 acc *= PRIME64_1; 414 return acc; 415 } 416 417 static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val) 418 { 419 val = xxh64_round(0, val); 420 acc ^= val; 421 acc = acc * PRIME64_1 + PRIME64_4; 422 return acc; 423 } 424 425 XXH_API uint64_t xxh64(const void *input, const size_t len, const uint64_t seed) 426 { 427 const uint8_t *p = (const uint8_t *)input; 428 const uint8_t *const b_end = p + len; 429 uint64_t h64; 430 431 if (len >= 32) { 432 const uint8_t *const limit = b_end - 32; 433 uint64_t v1 = seed + PRIME64_1 + PRIME64_2; 434 uint64_t v2 = seed + PRIME64_2; 435 uint64_t v3 = seed + 0; 436 uint64_t v4 = seed - PRIME64_1; 437 438 do { 439 v1 = xxh64_round(v1, get_unaligned_le64(p)); 440 p += 8; 441 v2 = xxh64_round(v2, get_unaligned_le64(p)); 442 p += 8; 443 v3 = xxh64_round(v3, get_unaligned_le64(p)); 444 p += 8; 445 v4 = xxh64_round(v4, get_unaligned_le64(p)); 446 p += 8; 447 } while (p <= limit); 448 449 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) + 450 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18); 451 h64 = xxh64_merge_round(h64, v1); 452 h64 = xxh64_merge_round(h64, v2); 453 h64 = xxh64_merge_round(h64, v3); 454 h64 = xxh64_merge_round(h64, v4); 455 456 } else { 457 h64 = seed + PRIME64_5; 458 } 459 460 h64 += (uint64_t)len; 461 462 while (p + 8 <= b_end) { 463 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p)); 464 465 h64 ^= k1; 466 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4; 467 p += 8; 468 } 469 470 if (p + 4 <= b_end) { 471 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1; 472 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 473 p += 4; 474 } 475 476 while (p < b_end) { 477 h64 ^= (*p) * PRIME64_5; 478 h64 = xxh_rotl64(h64, 11) * PRIME64_1; 479 p++; 480 } 481 482 h64 ^= h64 >> 33; 483 h64 *= PRIME64_2; 484 h64 ^= h64 >> 29; 485 h64 *= PRIME64_3; 486 h64 ^= h64 >> 32; 487 488 return h64; 489 } 490 491 /*-************************************************** 492 * Advanced Hash Functions 493 ***************************************************/ 494 XXH_API void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed) 495 { 496 /* use a local state for memcpy() to avoid strict-aliasing warnings */ 497 struct xxh32_state state; 498 499 __builtin_memset(&state, 0, sizeof(state)); 500 state.v1 = seed + PRIME32_1 + PRIME32_2; 501 state.v2 = seed + PRIME32_2; 502 state.v3 = seed + 0; 503 state.v4 = seed - PRIME32_1; 504 __builtin_memcpy(statePtr, &state, sizeof(state)); 505 } 506 507 XXH_API void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed) 508 { 509 /* use a local state for memcpy() to avoid strict-aliasing warnings */ 510 struct xxh64_state state; 511 512 __builtin_memset(&state, 0, sizeof(state)); 513 state.v1 = seed + PRIME64_1 + PRIME64_2; 514 state.v2 = seed + PRIME64_2; 515 state.v3 = seed + 0; 516 state.v4 = seed - PRIME64_1; 517 __builtin_memcpy(statePtr, &state, sizeof(state)); 518 } 519 520 XXH_API int xxh32_update(struct xxh32_state *state, const void *input, const size_t len) 521 { 522 const uint8_t *p = (const uint8_t *)input; 523 const uint8_t *const b_end = p + len; 524 525 if (input == NULL) 526 return -EINVAL; 527 528 state->total_len_32 += (uint32_t)len; 529 state->large_len |= (len >= 16) | (state->total_len_32 >= 16); 530 531 if (state->memsize + len < 16) { /* fill in tmp buffer */ 532 __builtin_memcpy((uint8_t *)(state->mem32) + state->memsize, input, len); 533 state->memsize += (uint32_t)len; 534 return 0; 535 } 536 537 if (state->memsize) { /* some data left from previous update */ 538 const uint32_t *p32 = state->mem32; 539 540 __builtin_memcpy((uint8_t *)(state->mem32) + state->memsize, input, 541 16 - state->memsize); 542 543 state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32)); 544 p32++; 545 state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32)); 546 p32++; 547 state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32)); 548 p32++; 549 state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32)); 550 p32++; 551 552 p += 16-state->memsize; 553 state->memsize = 0; 554 } 555 556 if (p <= b_end - 16) { 557 const uint8_t *const limit = b_end - 16; 558 uint32_t v1 = state->v1; 559 uint32_t v2 = state->v2; 560 uint32_t v3 = state->v3; 561 uint32_t v4 = state->v4; 562 563 do { 564 v1 = xxh32_round(v1, get_unaligned_le32(p)); 565 p += 4; 566 v2 = xxh32_round(v2, get_unaligned_le32(p)); 567 p += 4; 568 v3 = xxh32_round(v3, get_unaligned_le32(p)); 569 p += 4; 570 v4 = xxh32_round(v4, get_unaligned_le32(p)); 571 p += 4; 572 } while (p <= limit); 573 574 state->v1 = v1; 575 state->v2 = v2; 576 state->v3 = v3; 577 state->v4 = v4; 578 } 579 580 if (p < b_end) { 581 __builtin_memcpy(state->mem32, p, (size_t)(b_end-p)); 582 state->memsize = (uint32_t)(b_end-p); 583 } 584 585 return 0; 586 } 587 588 XXH_API uint32_t xxh32_digest(const struct xxh32_state *state) 589 { 590 const uint8_t *p = (const uint8_t *)state->mem32; 591 const uint8_t *const b_end = (const uint8_t *)(state->mem32) + 592 state->memsize; 593 uint32_t h32; 594 595 if (state->large_len) { 596 h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) + 597 xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18); 598 } else { 599 h32 = state->v3 /* == seed */ + PRIME32_5; 600 } 601 602 h32 += state->total_len_32; 603 604 while (p + 4 <= b_end) { 605 h32 += get_unaligned_le32(p) * PRIME32_3; 606 h32 = xxh_rotl32(h32, 17) * PRIME32_4; 607 p += 4; 608 } 609 610 while (p < b_end) { 611 h32 += (*p) * PRIME32_5; 612 h32 = xxh_rotl32(h32, 11) * PRIME32_1; 613 p++; 614 } 615 616 h32 ^= h32 >> 15; 617 h32 *= PRIME32_2; 618 h32 ^= h32 >> 13; 619 h32 *= PRIME32_3; 620 h32 ^= h32 >> 16; 621 622 return h32; 623 } 624 625 XXH_API int xxh64_update(struct xxh64_state *state, const void *input, const size_t len) 626 { 627 const uint8_t *p = (const uint8_t *)input; 628 const uint8_t *const b_end = p + len; 629 630 if (input == NULL) 631 return -EINVAL; 632 633 state->total_len += len; 634 635 if (state->memsize + len < 32) { /* fill in tmp buffer */ 636 __builtin_memcpy(((uint8_t *)state->mem64) + state->memsize, input, len); 637 state->memsize += (uint32_t)len; 638 return 0; 639 } 640 641 if (state->memsize) { /* tmp buffer is full */ 642 uint64_t *p64 = state->mem64; 643 644 __builtin_memcpy(((uint8_t *)p64) + state->memsize, input, 645 32 - state->memsize); 646 647 state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64)); 648 p64++; 649 state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64)); 650 p64++; 651 state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64)); 652 p64++; 653 state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64)); 654 655 p += 32 - state->memsize; 656 state->memsize = 0; 657 } 658 659 if (p + 32 <= b_end) { 660 const uint8_t *const limit = b_end - 32; 661 uint64_t v1 = state->v1; 662 uint64_t v2 = state->v2; 663 uint64_t v3 = state->v3; 664 uint64_t v4 = state->v4; 665 666 do { 667 v1 = xxh64_round(v1, get_unaligned_le64(p)); 668 p += 8; 669 v2 = xxh64_round(v2, get_unaligned_le64(p)); 670 p += 8; 671 v3 = xxh64_round(v3, get_unaligned_le64(p)); 672 p += 8; 673 v4 = xxh64_round(v4, get_unaligned_le64(p)); 674 p += 8; 675 } while (p <= limit); 676 677 state->v1 = v1; 678 state->v2 = v2; 679 state->v3 = v3; 680 state->v4 = v4; 681 } 682 683 if (p < b_end) { 684 __builtin_memcpy(state->mem64, p, (size_t)(b_end-p)); 685 state->memsize = (uint32_t)(b_end - p); 686 } 687 688 return 0; 689 } 690 691 XXH_API uint64_t xxh64_digest(const struct xxh64_state *state) 692 { 693 const uint8_t *p = (const uint8_t *)state->mem64; 694 const uint8_t *const b_end = (const uint8_t *)state->mem64 + 695 state->memsize; 696 uint64_t h64; 697 698 if (state->total_len >= 32) { 699 const uint64_t v1 = state->v1; 700 const uint64_t v2 = state->v2; 701 const uint64_t v3 = state->v3; 702 const uint64_t v4 = state->v4; 703 704 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) + 705 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18); 706 h64 = xxh64_merge_round(h64, v1); 707 h64 = xxh64_merge_round(h64, v2); 708 h64 = xxh64_merge_round(h64, v3); 709 h64 = xxh64_merge_round(h64, v4); 710 } else { 711 h64 = state->v3 + PRIME64_5; 712 } 713 714 h64 += (uint64_t)state->total_len; 715 716 while (p + 8 <= b_end) { 717 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p)); 718 719 h64 ^= k1; 720 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4; 721 p += 8; 722 } 723 724 if (p + 4 <= b_end) { 725 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1; 726 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 727 p += 4; 728 } 729 730 while (p < b_end) { 731 h64 ^= (*p) * PRIME64_5; 732 h64 = xxh_rotl64(h64, 11) * PRIME64_1; 733 p++; 734 } 735 736 h64 ^= h64 >> 33; 737 h64 *= PRIME64_2; 738 h64 ^= h64 >> 29; 739 h64 *= PRIME64_3; 740 h64 ^= h64 >> 32; 741 742 return h64; 743 } 744 745 #endif /* XXHASH_H */ 746
Indexes created Tue Feb 24 01:34:59 UTC 2026