deps/libchdr/deps/zstd-1.5.5/contrib/linux-kernel/test/include/linux/xxhash.h

   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 */