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