501 lines · c
1/*2 * xxHash - Extremely Fast Hash algorithm3 * Copyright (C) 2012-2016, Yann Collet.4 *5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)6 *7 * Redistribution and use in source and binary forms, with or without8 * modification, are permitted provided that the following conditions are9 * met:10 *11 * * Redistributions of source code must retain the above copyright12 * notice, this list of conditions and the following disclaimer.13 * * Redistributions in binary form must reproduce the above14 * copyright notice, this list of conditions and the following disclaimer15 * in the documentation and/or other materials provided with the16 * distribution.17 *18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE28 * 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 under31 * the terms of the GNU General Public License version 2 as published by the32 * Free Software Foundation. This program is dual-licensed; you may select33 * either version 2 of the GNU General Public License ("GPL") or BSD license34 * ("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/xxHash39 */40 41#include <linux/unaligned.h>42#include <linux/errno.h>43#include <linux/compiler.h>44#include <linux/kernel.h>45#include <linux/module.h>46#include <linux/string.h>47#include <linux/xxhash.h>48 49/*-*************************************50 * Macros51 **************************************/52#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))53#define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))54 55#ifdef __LITTLE_ENDIAN56# define XXH_CPU_LITTLE_ENDIAN 157#else58# define XXH_CPU_LITTLE_ENDIAN 059#endif60 61/*-*************************************62 * Constants63 **************************************/64static const uint32_t PRIME32_1 = 2654435761U;65static const uint32_t PRIME32_2 = 2246822519U;66static const uint32_t PRIME32_3 = 3266489917U;67static const uint32_t PRIME32_4 = 668265263U;68static const uint32_t PRIME32_5 = 374761393U;69 70static const uint64_t PRIME64_1 = 11400714785074694791ULL;71static const uint64_t PRIME64_2 = 14029467366897019727ULL;72static const uint64_t PRIME64_3 = 1609587929392839161ULL;73static const uint64_t PRIME64_4 = 9650029242287828579ULL;74static const uint64_t PRIME64_5 = 2870177450012600261ULL;75 76/*-**************************77 * Utils78 ***************************/79void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)80{81 memcpy(dst, src, sizeof(*dst));82}83EXPORT_SYMBOL(xxh32_copy_state);84 85void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)86{87 memcpy(dst, src, sizeof(*dst));88}89EXPORT_SYMBOL(xxh64_copy_state);90 91/*-***************************92 * Simple Hash Functions93 ****************************/94static uint32_t xxh32_round(uint32_t seed, const uint32_t input)95{96 seed += input * PRIME32_2;97 seed = xxh_rotl32(seed, 13);98 seed *= PRIME32_1;99 return seed;100}101 102uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)103{104 const uint8_t *p = (const uint8_t *)input;105 const uint8_t *b_end = p + len;106 uint32_t h32;107 108 if (len >= 16) {109 const uint8_t *const limit = b_end - 16;110 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;111 uint32_t v2 = seed + PRIME32_2;112 uint32_t v3 = seed + 0;113 uint32_t v4 = seed - PRIME32_1;114 115 do {116 v1 = xxh32_round(v1, get_unaligned_le32(p));117 p += 4;118 v2 = xxh32_round(v2, get_unaligned_le32(p));119 p += 4;120 v3 = xxh32_round(v3, get_unaligned_le32(p));121 p += 4;122 v4 = xxh32_round(v4, get_unaligned_le32(p));123 p += 4;124 } while (p <= limit);125 126 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +127 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);128 } else {129 h32 = seed + PRIME32_5;130 }131 132 h32 += (uint32_t)len;133 134 while (p + 4 <= b_end) {135 h32 += get_unaligned_le32(p) * PRIME32_3;136 h32 = xxh_rotl32(h32, 17) * PRIME32_4;137 p += 4;138 }139 140 while (p < b_end) {141 h32 += (*p) * PRIME32_5;142 h32 = xxh_rotl32(h32, 11) * PRIME32_1;143 p++;144 }145 146 h32 ^= h32 >> 15;147 h32 *= PRIME32_2;148 h32 ^= h32 >> 13;149 h32 *= PRIME32_3;150 h32 ^= h32 >> 16;151 152 return h32;153}154EXPORT_SYMBOL(xxh32);155 156static uint64_t xxh64_round(uint64_t acc, const uint64_t input)157{158 acc += input * PRIME64_2;159 acc = xxh_rotl64(acc, 31);160 acc *= PRIME64_1;161 return acc;162}163 164static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)165{166 val = xxh64_round(0, val);167 acc ^= val;168 acc = acc * PRIME64_1 + PRIME64_4;169 return acc;170}171 172uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)173{174 const uint8_t *p = (const uint8_t *)input;175 const uint8_t *const b_end = p + len;176 uint64_t h64;177 178 if (len >= 32) {179 const uint8_t *const limit = b_end - 32;180 uint64_t v1 = seed + PRIME64_1 + PRIME64_2;181 uint64_t v2 = seed + PRIME64_2;182 uint64_t v3 = seed + 0;183 uint64_t v4 = seed - PRIME64_1;184 185 do {186 v1 = xxh64_round(v1, get_unaligned_le64(p));187 p += 8;188 v2 = xxh64_round(v2, get_unaligned_le64(p));189 p += 8;190 v3 = xxh64_round(v3, get_unaligned_le64(p));191 p += 8;192 v4 = xxh64_round(v4, get_unaligned_le64(p));193 p += 8;194 } while (p <= limit);195 196 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +197 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);198 h64 = xxh64_merge_round(h64, v1);199 h64 = xxh64_merge_round(h64, v2);200 h64 = xxh64_merge_round(h64, v3);201 h64 = xxh64_merge_round(h64, v4);202 203 } else {204 h64 = seed + PRIME64_5;205 }206 207 h64 += (uint64_t)len;208 209 while (p + 8 <= b_end) {210 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));211 212 h64 ^= k1;213 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;214 p += 8;215 }216 217 if (p + 4 <= b_end) {218 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;219 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;220 p += 4;221 }222 223 while (p < b_end) {224 h64 ^= (*p) * PRIME64_5;225 h64 = xxh_rotl64(h64, 11) * PRIME64_1;226 p++;227 }228 229 h64 ^= h64 >> 33;230 h64 *= PRIME64_2;231 h64 ^= h64 >> 29;232 h64 *= PRIME64_3;233 h64 ^= h64 >> 32;234 235 return h64;236}237EXPORT_SYMBOL(xxh64);238 239/*-**************************************************240 * Advanced Hash Functions241 ***************************************************/242void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)243{244 /* use a local state for memcpy() to avoid strict-aliasing warnings */245 struct xxh32_state state;246 247 memset(&state, 0, sizeof(state));248 state.v1 = seed + PRIME32_1 + PRIME32_2;249 state.v2 = seed + PRIME32_2;250 state.v3 = seed + 0;251 state.v4 = seed - PRIME32_1;252 memcpy(statePtr, &state, sizeof(state));253}254EXPORT_SYMBOL(xxh32_reset);255 256void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)257{258 /* use a local state for memcpy() to avoid strict-aliasing warnings */259 struct xxh64_state state;260 261 memset(&state, 0, sizeof(state));262 state.v1 = seed + PRIME64_1 + PRIME64_2;263 state.v2 = seed + PRIME64_2;264 state.v3 = seed + 0;265 state.v4 = seed - PRIME64_1;266 memcpy(statePtr, &state, sizeof(state));267}268EXPORT_SYMBOL(xxh64_reset);269 270int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)271{272 const uint8_t *p = (const uint8_t *)input;273 const uint8_t *const b_end = p + len;274 275 if (input == NULL)276 return -EINVAL;277 278 state->total_len_32 += (uint32_t)len;279 state->large_len |= (len >= 16) | (state->total_len_32 >= 16);280 281 if (state->memsize + len < 16) { /* fill in tmp buffer */282 memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);283 state->memsize += (uint32_t)len;284 return 0;285 }286 287 if (state->memsize) { /* some data left from previous update */288 const uint32_t *p32 = state->mem32;289 290 memcpy((uint8_t *)(state->mem32) + state->memsize, input,291 16 - state->memsize);292 293 state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));294 p32++;295 state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));296 p32++;297 state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));298 p32++;299 state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));300 p32++;301 302 p += 16-state->memsize;303 state->memsize = 0;304 }305 306 if (p <= b_end - 16) {307 const uint8_t *const limit = b_end - 16;308 uint32_t v1 = state->v1;309 uint32_t v2 = state->v2;310 uint32_t v3 = state->v3;311 uint32_t v4 = state->v4;312 313 do {314 v1 = xxh32_round(v1, get_unaligned_le32(p));315 p += 4;316 v2 = xxh32_round(v2, get_unaligned_le32(p));317 p += 4;318 v3 = xxh32_round(v3, get_unaligned_le32(p));319 p += 4;320 v4 = xxh32_round(v4, get_unaligned_le32(p));321 p += 4;322 } while (p <= limit);323 324 state->v1 = v1;325 state->v2 = v2;326 state->v3 = v3;327 state->v4 = v4;328 }329 330 if (p < b_end) {331 memcpy(state->mem32, p, (size_t)(b_end-p));332 state->memsize = (uint32_t)(b_end-p);333 }334 335 return 0;336}337EXPORT_SYMBOL(xxh32_update);338 339uint32_t xxh32_digest(const struct xxh32_state *state)340{341 const uint8_t *p = (const uint8_t *)state->mem32;342 const uint8_t *const b_end = (const uint8_t *)(state->mem32) +343 state->memsize;344 uint32_t h32;345 346 if (state->large_len) {347 h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +348 xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);349 } else {350 h32 = state->v3 /* == seed */ + PRIME32_5;351 }352 353 h32 += state->total_len_32;354 355 while (p + 4 <= b_end) {356 h32 += get_unaligned_le32(p) * PRIME32_3;357 h32 = xxh_rotl32(h32, 17) * PRIME32_4;358 p += 4;359 }360 361 while (p < b_end) {362 h32 += (*p) * PRIME32_5;363 h32 = xxh_rotl32(h32, 11) * PRIME32_1;364 p++;365 }366 367 h32 ^= h32 >> 15;368 h32 *= PRIME32_2;369 h32 ^= h32 >> 13;370 h32 *= PRIME32_3;371 h32 ^= h32 >> 16;372 373 return h32;374}375EXPORT_SYMBOL(xxh32_digest);376 377int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)378{379 const uint8_t *p = (const uint8_t *)input;380 const uint8_t *const b_end = p + len;381 382 if (input == NULL)383 return -EINVAL;384 385 state->total_len += len;386 387 if (state->memsize + len < 32) { /* fill in tmp buffer */388 memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);389 state->memsize += (uint32_t)len;390 return 0;391 }392 393 if (state->memsize) { /* tmp buffer is full */394 uint64_t *p64 = state->mem64;395 396 memcpy(((uint8_t *)p64) + state->memsize, input,397 32 - state->memsize);398 399 state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));400 p64++;401 state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));402 p64++;403 state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));404 p64++;405 state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));406 407 p += 32 - state->memsize;408 state->memsize = 0;409 }410 411 if (p + 32 <= b_end) {412 const uint8_t *const limit = b_end - 32;413 uint64_t v1 = state->v1;414 uint64_t v2 = state->v2;415 uint64_t v3 = state->v3;416 uint64_t v4 = state->v4;417 418 do {419 v1 = xxh64_round(v1, get_unaligned_le64(p));420 p += 8;421 v2 = xxh64_round(v2, get_unaligned_le64(p));422 p += 8;423 v3 = xxh64_round(v3, get_unaligned_le64(p));424 p += 8;425 v4 = xxh64_round(v4, get_unaligned_le64(p));426 p += 8;427 } while (p <= limit);428 429 state->v1 = v1;430 state->v2 = v2;431 state->v3 = v3;432 state->v4 = v4;433 }434 435 if (p < b_end) {436 memcpy(state->mem64, p, (size_t)(b_end-p));437 state->memsize = (uint32_t)(b_end - p);438 }439 440 return 0;441}442EXPORT_SYMBOL(xxh64_update);443 444uint64_t xxh64_digest(const struct xxh64_state *state)445{446 const uint8_t *p = (const uint8_t *)state->mem64;447 const uint8_t *const b_end = (const uint8_t *)state->mem64 +448 state->memsize;449 uint64_t h64;450 451 if (state->total_len >= 32) {452 const uint64_t v1 = state->v1;453 const uint64_t v2 = state->v2;454 const uint64_t v3 = state->v3;455 const uint64_t v4 = state->v4;456 457 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +458 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);459 h64 = xxh64_merge_round(h64, v1);460 h64 = xxh64_merge_round(h64, v2);461 h64 = xxh64_merge_round(h64, v3);462 h64 = xxh64_merge_round(h64, v4);463 } else {464 h64 = state->v3 + PRIME64_5;465 }466 467 h64 += (uint64_t)state->total_len;468 469 while (p + 8 <= b_end) {470 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));471 472 h64 ^= k1;473 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;474 p += 8;475 }476 477 if (p + 4 <= b_end) {478 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;479 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;480 p += 4;481 }482 483 while (p < b_end) {484 h64 ^= (*p) * PRIME64_5;485 h64 = xxh_rotl64(h64, 11) * PRIME64_1;486 p++;487 }488 489 h64 ^= h64 >> 33;490 h64 *= PRIME64_2;491 h64 ^= h64 >> 29;492 h64 *= PRIME64_3;493 h64 ^= h64 >> 32;494 495 return h64;496}497EXPORT_SYMBOL(xxh64_digest);498 499MODULE_LICENSE("Dual BSD/GPL");500MODULE_DESCRIPTION("xxHash");501