2 * xxHash - Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
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
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.
30 * You can contact the author at :
31 * - xxHash source repository : https://github.com/Cyan4973/xxHash
37 #include "qemu/bitops.h"
39 #define PRIME32_1 2654435761U
40 #define PRIME32_2 2246822519U
41 #define PRIME32_3 3266489917U
42 #define PRIME32_4 668265263U
43 #define PRIME32_5 374761393U
45 #define QEMU_XXHASH_SEED 1
48 * xxhash32, customized for input variables that are not guaranteed to be
49 * contiguous in memory.
51 static inline uint32_t
52 qemu_xxhash7(uint64_t ab
, uint64_t cd
, uint32_t e
, uint32_t f
, uint32_t g
)
54 uint32_t v1
= QEMU_XXHASH_SEED
+ PRIME32_1
+ PRIME32_2
;
55 uint32_t v2
= QEMU_XXHASH_SEED
+ PRIME32_2
;
56 uint32_t v3
= QEMU_XXHASH_SEED
+ 0;
57 uint32_t v4
= QEMU_XXHASH_SEED
- PRIME32_1
;
59 uint32_t b
= ab
>> 32;
61 uint32_t d
= cd
>> 32;
80 h32
= rol32(v1
, 1) + rol32(v2
, 7) + rol32(v3
, 12) + rol32(v4
, 18);
84 h32
= rol32(h32
, 17) * PRIME32_4
;
87 h32
= rol32(h32
, 17) * PRIME32_4
;
90 h32
= rol32(h32
, 17) * PRIME32_4
;
101 static inline uint32_t qemu_xxhash2(uint64_t ab
)
103 return qemu_xxhash7(ab
, 0, 0, 0, 0);
106 static inline uint32_t qemu_xxhash4(uint64_t ab
, uint64_t cd
)
108 return qemu_xxhash7(ab
, cd
, 0, 0, 0);
111 static inline uint32_t qemu_xxhash5(uint64_t ab
, uint64_t cd
, uint32_t e
)
113 return qemu_xxhash7(ab
, cd
, e
, 0, 0);
116 static inline uint32_t qemu_xxhash6(uint64_t ab
, uint64_t cd
, uint32_t e
,
119 return qemu_xxhash7(ab
, cd
, e
, f
, 0);
123 * Component parts of the XXH64 algorithm from
124 * https://github.com/Cyan4973/xxHash/blob/v0.8.0/xxhash.h
126 * The complete algorithm looks like
130 * v1 = seed + XXH_PRIME64_1 + XXH_PRIME64_2;
131 * v2 = seed + XXH_PRIME64_2;
133 * v4 = seed - XXH_PRIME64_1;
135 * v1 = XXH64_round(v1, get64bits(input + i));
136 * v2 = XXH64_round(v2, get64bits(input + i + 8));
137 * v3 = XXH64_round(v3, get64bits(input + i + 16));
138 * v4 = XXH64_round(v4, get64bits(input + i + 24));
139 * } while ((i += 32) <= len);
140 * h64 = XXH64_mergerounds(v1, v2, v3, v4);
142 * h64 = seed + XXH_PRIME64_5;
146 * for (; i + 8 <= len; i += 8) {
147 * h64 ^= XXH64_round(0, get64bits(input + i));
148 * h64 = rol64(h64, 27) * XXH_PRIME64_1 + XXH_PRIME64_4;
150 * for (; i + 4 <= len; i += 4) {
151 * h64 ^= get32bits(input + i) * PRIME64_1;
152 * h64 = rol64(h64, 23) * XXH_PRIME64_2 + XXH_PRIME64_3;
154 * for (; i < len; i += 1) {
155 * h64 ^= get8bits(input + i) * XXH_PRIME64_5;
156 * h64 = rol64(h64, 11) * XXH_PRIME64_1;
159 * return XXH64_avalanche(h64)
161 * Exposing the pieces instead allows for simplified usage when
162 * the length is a known constant and the inputs are in registers.
164 #define XXH_PRIME64_1 0x9E3779B185EBCA87ULL
165 #define XXH_PRIME64_2 0xC2B2AE3D27D4EB4FULL
166 #define XXH_PRIME64_3 0x165667B19E3779F9ULL
167 #define XXH_PRIME64_4 0x85EBCA77C2B2AE63ULL
168 #define XXH_PRIME64_5 0x27D4EB2F165667C5ULL
170 static inline uint64_t XXH64_round(uint64_t acc
, uint64_t input
)
172 return rol64(acc
+ input
* XXH_PRIME64_2
, 31) * XXH_PRIME64_1
;
175 static inline uint64_t XXH64_mergeround(uint64_t acc
, uint64_t val
)
177 return (acc
^ XXH64_round(0, val
)) * XXH_PRIME64_1
+ XXH_PRIME64_4
;
180 static inline uint64_t XXH64_mergerounds(uint64_t v1
, uint64_t v2
,
181 uint64_t v3
, uint64_t v4
)
185 h64
= rol64(v1
, 1) + rol64(v2
, 7) + rol64(v3
, 12) + rol64(v4
, 18);
186 h64
= XXH64_mergeround(h64
, v1
);
187 h64
= XXH64_mergeround(h64
, v2
);
188 h64
= XXH64_mergeround(h64
, v3
);
189 h64
= XXH64_mergeround(h64
, v4
);
194 static inline uint64_t XXH64_avalanche(uint64_t h64
)
197 h64
*= XXH_PRIME64_2
;
199 h64
*= XXH_PRIME64_3
;
204 static inline uint64_t qemu_xxhash64_4(uint64_t a
, uint64_t b
,
205 uint64_t c
, uint64_t d
)
207 uint64_t v1
= QEMU_XXHASH_SEED
+ XXH_PRIME64_1
+ XXH_PRIME64_2
;
208 uint64_t v2
= QEMU_XXHASH_SEED
+ XXH_PRIME64_2
;
209 uint64_t v3
= QEMU_XXHASH_SEED
+ 0;
210 uint64_t v4
= QEMU_XXHASH_SEED
- XXH_PRIME64_1
;
212 v1
= XXH64_round(v1
, a
);
213 v2
= XXH64_round(v2
, b
);
214 v3
= XXH64_round(v3
, c
);
215 v4
= XXH64_round(v4
, d
);
217 return XXH64_avalanche(XXH64_mergerounds(v1
, v2
, v3
, v4
));
220 #endif /* QEMU_XXHASH_H */