1 // SPDX-License-Identifier: BSD-2-Clause OR GPL-2.0-only
2 /*
3 * The xxhash is copied from the linux kernel at:
4 * https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/xxhash.c
5 *
6 * The original copyright is:
7 *
8 * xxHash - Extremely Fast Hash algorithm
9 * Copyright (C) 2012-2016, Yann Collet.
10 *
11 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions are
15 * met:
16 *
17 * * Redistributions of source code must retain the above copyright
18 * notice, this list of conditions and the following disclaimer.
19 * * Redistributions in binary form must reproduce the above
20 * copyright notice, this list of conditions and the following disclaimer
21 * in the documentation and/or other materials provided with the
22 * distribution.
23 *
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
27 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
28 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
29 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
30 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
31 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
32 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
33 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
34 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35 *
36 * This program is free software; you can redistribute it and/or modify it under
37 * the terms of the GNU General Public License version 2 as published by the
38 * Free Software Foundation. This program is dual-licensed; you may select
39 * either version 2 of the GNU General Public License ("GPL") or BSD license
40 * ("BSD").
41 *
42 * You can contact the author at:
43 * - xxHash homepage: https://cyan4973.github.io/xxHash/
44 * - xxHash source repository: https://github.com/Cyan4973/xxHash
45 */
46 #include "erofs/defs.h"
47 #include "xxhash.h"
48
49 /*-*************************************
50 * Macros
51 **************************************/
52 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
53 #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
54
55 /*-*************************************
56 * Constants
57 **************************************/
58 static const uint32_t PRIME32_1 = 2654435761U;
59 static const uint32_t PRIME32_2 = 2246822519U;
60 static const uint32_t PRIME32_3 = 3266489917U;
61 static const uint32_t PRIME32_4 = 668265263U;
62 static const uint32_t PRIME32_5 = 374761393U;
63
64 static const uint64_t PRIME64_1 = 11400714785074694791ULL;
65 static const uint64_t PRIME64_2 = 14029467366897019727ULL;
66 static const uint64_t PRIME64_3 = 1609587929392839161ULL;
67 static const uint64_t PRIME64_4 = 9650029242287828579ULL;
68 static const uint64_t PRIME64_5 = 2870177450012600261ULL;
69
70 /*-***************************
71 * Simple Hash Functions
72 ****************************/
xxh32_round(uint32_t seed,const uint32_t input)73 static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
74 {
75 seed += input * PRIME32_2;
76 seed = xxh_rotl32(seed, 13);
77 seed *= PRIME32_1;
78 return seed;
79 }
80
xxh32(const void * input,const size_t len,const uint32_t seed)81 uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
82 {
83 const uint8_t *p = (const uint8_t *)input;
84 const uint8_t *b_end = p + len;
85 uint32_t h32;
86
87 if (len >= 16) {
88 const uint8_t *const limit = b_end - 16;
89 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
90 uint32_t v2 = seed + PRIME32_2;
91 uint32_t v3 = seed + 0;
92 uint32_t v4 = seed - PRIME32_1;
93
94 do {
95 v1 = xxh32_round(v1, get_unaligned_le32(p));
96 p += 4;
97 v2 = xxh32_round(v2, get_unaligned_le32(p));
98 p += 4;
99 v3 = xxh32_round(v3, get_unaligned_le32(p));
100 p += 4;
101 v4 = xxh32_round(v4, get_unaligned_le32(p));
102 p += 4;
103 } while (p <= limit);
104
105 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
106 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
107 } else {
108 h32 = seed + PRIME32_5;
109 }
110
111 h32 += (uint32_t)len;
112
113 while (p + 4 <= b_end) {
114 h32 += get_unaligned_le32(p) * PRIME32_3;
115 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
116 p += 4;
117 }
118
119 while (p < b_end) {
120 h32 += (*p) * PRIME32_5;
121 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
122 p++;
123 }
124
125 h32 ^= h32 >> 15;
126 h32 *= PRIME32_2;
127 h32 ^= h32 >> 13;
128 h32 *= PRIME32_3;
129 h32 ^= h32 >> 16;
130
131 return h32;
132 }
133
xxh64_round(uint64_t acc,const uint64_t input)134 static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
135 {
136 acc += input * PRIME64_2;
137 acc = xxh_rotl64(acc, 31);
138 acc *= PRIME64_1;
139 return acc;
140 }
141
xxh64_merge_round(uint64_t acc,uint64_t val)142 static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
143 {
144 val = xxh64_round(0, val);
145 acc ^= val;
146 acc = acc * PRIME64_1 + PRIME64_4;
147 return acc;
148 }
149
xxh64(const void * input,const size_t len,const uint64_t seed)150 uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
151 {
152 const uint8_t *p = (const uint8_t *)input;
153 const uint8_t *const b_end = p + len;
154 uint64_t h64;
155
156 if (len >= 32) {
157 const uint8_t *const limit = b_end - 32;
158 uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
159 uint64_t v2 = seed + PRIME64_2;
160 uint64_t v3 = seed + 0;
161 uint64_t v4 = seed - PRIME64_1;
162
163 do {
164 v1 = xxh64_round(v1, get_unaligned_le64(p));
165 p += 8;
166 v2 = xxh64_round(v2, get_unaligned_le64(p));
167 p += 8;
168 v3 = xxh64_round(v3, get_unaligned_le64(p));
169 p += 8;
170 v4 = xxh64_round(v4, get_unaligned_le64(p));
171 p += 8;
172 } while (p <= limit);
173
174 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
175 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
176 h64 = xxh64_merge_round(h64, v1);
177 h64 = xxh64_merge_round(h64, v2);
178 h64 = xxh64_merge_round(h64, v3);
179 h64 = xxh64_merge_round(h64, v4);
180
181 } else {
182 h64 = seed + PRIME64_5;
183 }
184
185 h64 += (uint64_t)len;
186
187 while (p + 8 <= b_end) {
188 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
189
190 h64 ^= k1;
191 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
192 p += 8;
193 }
194
195 if (p + 4 <= b_end) {
196 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
197 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
198 p += 4;
199 }
200
201 while (p < b_end) {
202 h64 ^= (*p) * PRIME64_5;
203 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
204 p++;
205 }
206
207 h64 ^= h64 >> 33;
208 h64 *= PRIME64_2;
209 h64 ^= h64 >> 29;
210 h64 *= PRIME64_3;
211 h64 ^= h64 >> 32;
212
213 return h64;
214 }
215