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