1/*
2 * rapidhash - Very fast, high quality, platform-independent hashing algorithm.
3 * Copyright (C) 2024 Nicolas De Carli
4 *
5 * Based on 'wyhash', by Wang Yi <godspeed_china@yeah.net>
6 *
7 * BSD 2-Clause License (https://www.opensource.org/licenses/bsd-license.php)
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions are
11 * met:
12 *
13 * * Redistributions of source code must retain the above copyright
14 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above
16 * copyright notice, this list of conditions and the following disclaimer
17 * in the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *
32 * You can contact the author at:
33 * - rapidhash source repository: https://github.com/Nicoshev/rapidhash
34 */
35
36/*
37 * Includes.
38 */
39#include <stdint.h>
40#include <string.h>
41#if defined(_MSC_VER)
42 #include <intrin.h>
43 #if defined(_M_X64) && !defined(_M_ARM64EC)
44 #pragma intrinsic(_umul128)
45 #endif
46#endif
47
48/*
49 * C++ macros.
50 *
51 * RAPIDHASH_INLINE can be overriden to be stronger than a hint, i.e. by adding __attribute__((always_inline)).
52 */
53#ifdef __cplusplus
54 #define RAPIDHASH_NOEXCEPT noexcept
55 #define RAPIDHASH_CONSTEXPR constexpr
56 #ifndef RAPIDHASH_INLINE
57 #define RAPIDHASH_INLINE inline
58 #endif
59#else
60 #define RAPIDHASH_NOEXCEPT
61 #define RAPIDHASH_CONSTEXPR static const
62 #ifndef RAPIDHASH_INLINE
63 #define RAPIDHASH_INLINE static inline
64 #endif
65#endif
66
67/*
68 * Protection macro, alters behaviour of rapid_mum multiplication function.
69 *
70 * RAPIDHASH_FAST: Normal behavior, max speed.
71 * RAPIDHASH_PROTECTED: Extra protection against entropy loss.
72 */
73#ifndef RAPIDHASH_PROTECTED
74 #define RAPIDHASH_FAST
75#elif defined(RAPIDHASH_FAST)
76 #error "cannot define RAPIDHASH_PROTECTED and RAPIDHASH_FAST simultaneously."
77#endif
78
79/*
80 * Unrolling macros, changes code definition for main hash function.
81 *
82 * RAPIDHASH_COMPACT: Legacy variant, each loop process 48 bytes.
83 * RAPIDHASH_UNROLLED: Unrolled variant, each loop process 96 bytes.
84 *
85 * Most modern CPUs should benefit from having RAPIDHASH_UNROLLED.
86 *
87 * These macros do not alter the output hash.
88 */
89#ifndef RAPIDHASH_COMPACT
90 #define RAPIDHASH_UNROLLED
91#elif defined(RAPIDHASH_UNROLLED)
92 #error "cannot define RAPIDHASH_COMPACT and RAPIDHASH_UNROLLED simultaneously."
93#endif
94
95/*
96 * Likely and unlikely macros.
97 */
98#if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
99 #define _likely_(x) __builtin_expect(x,1)
100 #define _unlikely_(x) __builtin_expect(x,0)
101#else
102 #define _likely_(x) (x)
103 #define _unlikely_(x) (x)
104#endif
105
106/*
107 * Endianness macros.
108 */
109#ifndef RAPIDHASH_LITTLE_ENDIAN
110 #if defined(_WIN32) || defined(__LITTLE_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__)
111 #define RAPIDHASH_LITTLE_ENDIAN
112 #elif defined(__BIG_ENDIAN__) || (defined(__BYTE_ORDER__) && __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__)
113 #define RAPIDHASH_BIG_ENDIAN
114 #else
115 #warning "could not determine endianness! Falling back to little endian."
116 #define RAPIDHASH_LITTLE_ENDIAN
117 #endif
118#endif
119
120/*
121 * Default seed.
122 */
123#define RAPID_SEED (0xbdd89aa982704029ull)
124
125/*
126 * Default secret parameters.
127 */
128#define RAPID_SECRET_0 0x2d358dccaa6c78a5ull
129#define RAPID_SECRET_1 0x8bb84b93962eacc9ull
130#define RAPID_SECRET_2 0x4b33a62ed433d4a3ull
131
132RAPIDHASH_CONSTEXPR uint64_t rapid_secret[3] = {RAPID_SECRET_0, RAPID_SECRET_1, RAPID_SECRET_2};
133
134/*
135 * 64*64 -> 128bit multiply function.
136 *
137 * @param A Address of 64-bit number.
138 * @param B Address of 64-bit number.
139 *
140 * Calculates 128-bit C = *A * *B.
141 *
142 * When RAPIDHASH_FAST is defined:
143 * Overwrites A contents with C's low 64 bits.
144 * Overwrites B contents with C's high 64 bits.
145 *
146 * When RAPIDHASH_PROTECTED is defined:
147 * Xors and overwrites A contents with C's low 64 bits.
148 * Xors and overwrites B contents with C's high 64 bits.
149 */
150RAPIDHASH_INLINE void rapid_mum(uint64_t *A, uint64_t *B) RAPIDHASH_NOEXCEPT {
151#if defined(__SIZEOF_INT128__)
152 __uint128_t r=*A; r*=*B;
153 #ifdef RAPIDHASH_PROTECTED
154 *A^=(uint64_t)r; *B^=(uint64_t)(r>>64);
155 #else
156 *A=(uint64_t)r; *B=(uint64_t)(r>>64);
157 #endif
158#elif defined(_MSC_VER) && (defined(_WIN64) || defined(_M_HYBRID_CHPE_ARM64))
159 #if defined(_M_X64)
160 #ifdef RAPIDHASH_PROTECTED
161 uint64_t a, b;
162 a=_umul128(*A,*B,&b);
163 *A^=a; *B^=b;
164 #else
165 *A=_umul128(*A,*B,B);
166 #endif
167 #else
168 #ifdef RAPIDHASH_PROTECTED
169 uint64_t a, b;
170 b = __umulh(*A, *B);
171 a = *A * *B;
172 *A^=a; *B^=b;
173 #else
174 uint64_t c = __umulh(*A, *B);
175 *A = *A * *B;
176 *B = c;
177 #endif
178 #endif
179#else
180 uint64_t ha=*A>>32, hb=*B>>32, la=(uint32_t)*A, lb=(uint32_t)*B, hi, lo;
181 uint64_t rh=ha*hb, rm0=ha*lb, rm1=hb*la, rl=la*lb, t=rl+(rm0<<32), c=t<rl;
182 lo=t+(rm1<<32); c+=lo<t; hi=rh+(rm0>>32)+(rm1>>32)+c;
183 #ifdef RAPIDHASH_PROTECTED
184 *A^=lo; *B^=hi;
185 #else
186 *A=lo; *B=hi;
187 #endif
188#endif
189}
190
191/*
192 * Multiply and xor mix function.
193 *
194 * @param A 64-bit number.
195 * @param B 64-bit number.
196 *
197 * Calculates 128-bit C = A * B.
198 * Returns 64-bit xor between high and low 64 bits of C.
199 */
200RAPIDHASH_INLINE uint64_t rapid_mix(uint64_t A, uint64_t B) RAPIDHASH_NOEXCEPT { rapid_mum(&A,&B); return A^B; }
201
202/*
203 * Read functions.
204 */
205#ifdef RAPIDHASH_LITTLE_ENDIAN
206RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return v;}
207RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return v;}
208#elif defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
209RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return __builtin_bswap64(v);}
210RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return __builtin_bswap32(v);}
211#elif defined(_MSC_VER)
212RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint64_t v; memcpy(&v, p, sizeof(uint64_t)); return _byteswap_uint64(v);}
213RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT { uint32_t v; memcpy(&v, p, sizeof(uint32_t)); return _byteswap_ulong(v);}
214#else
215RAPIDHASH_INLINE uint64_t rapid_read64(const uint8_t *p) RAPIDHASH_NOEXCEPT {
216 uint64_t v; memcpy(&v, p, 8);
217 return (((v >> 56) & 0xff)| ((v >> 40) & 0xff00)| ((v >> 24) & 0xff0000)| ((v >> 8) & 0xff000000)| ((v << 8) & 0xff00000000)| ((v << 24) & 0xff0000000000)| ((v << 40) & 0xff000000000000)| ((v << 56) & 0xff00000000000000));
218}
219RAPIDHASH_INLINE uint64_t rapid_read32(const uint8_t *p) RAPIDHASH_NOEXCEPT {
220 uint32_t v; memcpy(&v, p, 4);
221 return (((v >> 24) & 0xff)| ((v >> 8) & 0xff00)| ((v << 8) & 0xff0000)| ((v << 24) & 0xff000000));
222}
223#endif
224
225/*
226 * Reads and combines 3 bytes of input.
227 *
228 * @param p Buffer to read from.
229 * @param k Length of @p, in bytes.
230 *
231 * Always reads and combines 3 bytes from memory.
232 * Guarantees to read each buffer position at least once.
233 *
234 * Returns a 64-bit value containing all three bytes read.
235 */
236RAPIDHASH_INLINE uint64_t rapid_readSmall(const uint8_t *p, unsigned k) RAPIDHASH_NOEXCEPT { return (((uint64_t)p[0])<<56)|(((uint64_t)p[k>>1])<<32)|p[k-1];}
237
238/*
239 * rapidhash main function.
240 *
241 * @param key Buffer to be hashed.
242 * @param len @key length, in bytes.
243 * @param seed 64-bit seed used to alter the hash result predictably.
244 * @param secret Triplet of 64-bit secrets used to alter hash result predictably.
245 *
246 * Returns a 64-bit hash.
247 */
248RAPIDHASH_INLINE uint64_t rapidhash_internal(const void *key, unsigned len, uint64_t seed, const uint64_t* secret) RAPIDHASH_NOEXCEPT {
249 const uint8_t *p=(const uint8_t *)key; seed^=rapid_mix(seed^secret[0],secret[1])^len; uint64_t a, b;
250 if(_likely_(len<=16)){
251 if(_likely_(len>=4)){
252 const uint8_t * plast = p + len - 4;
253 a = (rapid_read32(p) << 32) | rapid_read32(plast);
254 const uint64_t delta = ((len&24)>>(len>>3));
255 b = ((rapid_read32(p + delta) << 32) | rapid_read32(plast - delta)); }
256 else if(_likely_(len>0)){ a=rapid_readSmall(p,len); b=0;}
257 else a=b=0;
258 }
259 else{
260 unsigned i=len;
261 if(_unlikely_(i>48)){
262 uint64_t see1=seed, see2=seed;
263#ifdef RAPIDHASH_UNROLLED
264 while(_likely_(i>=96)){
265 seed=rapid_mix(rapid_read64(p)^secret[0],rapid_read64(p+8)^seed);
266 see1=rapid_mix(rapid_read64(p+16)^secret[1],rapid_read64(p+24)^see1);
267 see2=rapid_mix(rapid_read64(p+32)^secret[2],rapid_read64(p+40)^see2);
268 seed=rapid_mix(rapid_read64(p+48)^secret[0],rapid_read64(p+56)^seed);
269 see1=rapid_mix(rapid_read64(p+64)^secret[1],rapid_read64(p+72)^see1);
270 see2=rapid_mix(rapid_read64(p+80)^secret[2],rapid_read64(p+88)^see2);
271 p+=96; i-=96;
272 }
273 if(_unlikely_(i>=48)){
274 seed=rapid_mix(rapid_read64(p)^secret[0],rapid_read64(p+8)^seed);
275 see1=rapid_mix(rapid_read64(p+16)^secret[1],rapid_read64(p+24)^see1);
276 see2=rapid_mix(rapid_read64(p+32)^secret[2],rapid_read64(p+40)^see2);
277 p+=48; i-=48;
278 }
279#else
280 do {
281 seed=rapid_mix(rapid_read64(p)^secret[0],rapid_read64(p+8)^seed);
282 see1=rapid_mix(rapid_read64(p+16)^secret[1],rapid_read64(p+24)^see1);
283 see2=rapid_mix(rapid_read64(p+32)^secret[2],rapid_read64(p+40)^see2);
284 p+=48; i-=48;
285 } while (_likely_(i>=48));
286#endif
287 seed^=see1^see2;
288 }
289 if(i>16){
290 seed=rapid_mix(rapid_read64(p)^secret[2],rapid_read64(p+8)^seed^secret[1]);
291 if(i>32)
292 seed=rapid_mix(rapid_read64(p+16)^secret[2],rapid_read64(p+24)^seed);
293 }
294 a=rapid_read64(p+i-16); b=rapid_read64(p+i-8);
295 }
296 a^=secret[1]; b^=seed; rapid_mum(&a,&b);
297 return rapid_mix(a^secret[0]^len,b^secret[1]);
298}
299
300/*
301 * rapidhash default seeded hash function.
302 *
303 * @param key Buffer to be hashed.
304 * @param len @key length, in bytes.
305 * @param seed 64-bit seed used to alter the hash result predictably.
306 *
307 * Calls rapidhash_internal using provided parameters and default secrets.
308 *
309 * Returns a 64-bit hash.
310 */
311RAPIDHASH_INLINE uint64_t rapidhash_withSeed(const void *key, unsigned len, uint64_t seed) RAPIDHASH_NOEXCEPT {
312 return rapidhash_internal(key, len, seed, rapid_secret);
313}
314
315/*
316 * rapidhash default hash function.
317 *
318 * @param key Buffer to be hashed.
319 * @param len @key length, in bytes.
320 *
321 * Calls rapidhash_withSeed using provided parameters and the default seed.
322 *
323 * Returns a 64-bit hash.
324 */
325RAPIDHASH_INLINE uint64_t rapidhash(const void *key, unsigned len) RAPIDHASH_NOEXCEPT {
326 return rapidhash_withSeed(key, len, RAPID_SEED);
327}