]>
Commit | Line | Data |
---|---|---|
dc8b295d EC |
1 | /* |
2 | * xxHash - Fast Hash algorithm | |
3 | * 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 without | |
8 | * modification, are permitted provided that the following conditions are | |
9 | * met: | |
10 | * | |
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 | |
16 | * distribution. | |
17 | * | |
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. | |
29 | * | |
30 | * You can contact the author at : | |
31 | * - xxHash source repository : https://github.com/Cyan4973/xxHash | |
32 | */ | |
2a6a4076 | 33 | |
fe656e31 EC |
34 | #ifndef QEMU_XXHASH_H |
35 | #define QEMU_XXHASH_H | |
dc8b295d | 36 | |
a9c94277 | 37 | #include "qemu/bitops.h" |
dc8b295d EC |
38 | |
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 | |
44 | ||
c971d8fa | 45 | #define QEMU_XXHASH_SEED 1 |
dc8b295d EC |
46 | |
47 | /* | |
48 | * xxhash32, customized for input variables that are not guaranteed to be | |
49 | * contiguous in memory. | |
50 | */ | |
367189ef AB |
51 | static inline uint32_t qemu_xxhash8(uint64_t ab, uint64_t cd, uint64_t ef, |
52 | uint32_t g, uint32_t h) | |
dc8b295d | 53 | { |
c971d8fa EC |
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; | |
b7c2cd08 EC |
58 | uint32_t a = ab; |
59 | uint32_t b = ab >> 32; | |
60 | uint32_t c = cd; | |
61 | uint32_t d = cd >> 32; | |
367189ef AB |
62 | uint32_t e = ef; |
63 | uint32_t f = ef >> 32; | |
dc8b295d EC |
64 | uint32_t h32; |
65 | ||
66 | v1 += a * PRIME32_2; | |
67 | v1 = rol32(v1, 13); | |
68 | v1 *= PRIME32_1; | |
69 | ||
70 | v2 += b * PRIME32_2; | |
71 | v2 = rol32(v2, 13); | |
72 | v2 *= PRIME32_1; | |
73 | ||
74 | v3 += c * PRIME32_2; | |
75 | v3 = rol32(v3, 13); | |
76 | v3 *= PRIME32_1; | |
77 | ||
78 | v4 += d * PRIME32_2; | |
79 | v4 = rol32(v4, 13); | |
80 | v4 *= PRIME32_1; | |
81 | ||
82 | h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); | |
4e2ca83e | 83 | h32 += 28; |
dc8b295d EC |
84 | |
85 | h32 += e * PRIME32_3; | |
86 | h32 = rol32(h32, 17) * PRIME32_4; | |
87 | ||
61a67f71 LV |
88 | h32 += f * PRIME32_3; |
89 | h32 = rol32(h32, 17) * PRIME32_4; | |
90 | ||
4e2ca83e EC |
91 | h32 += g * PRIME32_3; |
92 | h32 = rol32(h32, 17) * PRIME32_4; | |
93 | ||
367189ef AB |
94 | h32 += h * PRIME32_3; |
95 | h32 = rol32(h32, 17) * PRIME32_4; | |
96 | ||
dc8b295d EC |
97 | h32 ^= h32 >> 15; |
98 | h32 *= PRIME32_2; | |
99 | h32 ^= h32 >> 13; | |
100 | h32 *= PRIME32_3; | |
101 | h32 ^= h32 >> 16; | |
102 | ||
103 | return h32; | |
104 | } | |
105 | ||
c971d8fa EC |
106 | static inline uint32_t qemu_xxhash2(uint64_t ab) |
107 | { | |
367189ef | 108 | return qemu_xxhash8(ab, 0, 0, 0, 0); |
c971d8fa EC |
109 | } |
110 | ||
111 | static inline uint32_t qemu_xxhash4(uint64_t ab, uint64_t cd) | |
112 | { | |
367189ef | 113 | return qemu_xxhash8(ab, cd, 0, 0, 0); |
c971d8fa EC |
114 | } |
115 | ||
116 | static inline uint32_t qemu_xxhash5(uint64_t ab, uint64_t cd, uint32_t e) | |
117 | { | |
367189ef | 118 | return qemu_xxhash8(ab, cd, 0, e, 0); |
c971d8fa EC |
119 | } |
120 | ||
121 | static inline uint32_t qemu_xxhash6(uint64_t ab, uint64_t cd, uint32_t e, | |
122 | uint32_t f) | |
123 | { | |
367189ef AB |
124 | return qemu_xxhash8(ab, cd, 0, e, f); |
125 | } | |
126 | ||
127 | static inline uint32_t qemu_xxhash7(uint64_t ab, uint64_t cd, uint64_t ef, | |
128 | uint32_t g) | |
129 | { | |
130 | return qemu_xxhash8(ab, cd, ef, g, 0); | |
c971d8fa EC |
131 | } |
132 | ||
283fc52a RH |
133 | /* |
134 | * Component parts of the XXH64 algorithm from | |
135 | * https://github.com/Cyan4973/xxHash/blob/v0.8.0/xxhash.h | |
136 | * | |
137 | * The complete algorithm looks like | |
138 | * | |
139 | * i = 0; | |
140 | * if (len >= 32) { | |
141 | * v1 = seed + XXH_PRIME64_1 + XXH_PRIME64_2; | |
142 | * v2 = seed + XXH_PRIME64_2; | |
143 | * v3 = seed + 0; | |
144 | * v4 = seed - XXH_PRIME64_1; | |
145 | * do { | |
146 | * v1 = XXH64_round(v1, get64bits(input + i)); | |
147 | * v2 = XXH64_round(v2, get64bits(input + i + 8)); | |
148 | * v3 = XXH64_round(v3, get64bits(input + i + 16)); | |
149 | * v4 = XXH64_round(v4, get64bits(input + i + 24)); | |
150 | * } while ((i += 32) <= len); | |
151 | * h64 = XXH64_mergerounds(v1, v2, v3, v4); | |
152 | * } else { | |
153 | * h64 = seed + XXH_PRIME64_5; | |
154 | * } | |
155 | * h64 += len; | |
156 | * | |
157 | * for (; i + 8 <= len; i += 8) { | |
158 | * h64 ^= XXH64_round(0, get64bits(input + i)); | |
159 | * h64 = rol64(h64, 27) * XXH_PRIME64_1 + XXH_PRIME64_4; | |
160 | * } | |
161 | * for (; i + 4 <= len; i += 4) { | |
162 | * h64 ^= get32bits(input + i) * PRIME64_1; | |
163 | * h64 = rol64(h64, 23) * XXH_PRIME64_2 + XXH_PRIME64_3; | |
164 | * } | |
165 | * for (; i < len; i += 1) { | |
166 | * h64 ^= get8bits(input + i) * XXH_PRIME64_5; | |
167 | * h64 = rol64(h64, 11) * XXH_PRIME64_1; | |
168 | * } | |
169 | * | |
170 | * return XXH64_avalanche(h64) | |
171 | * | |
172 | * Exposing the pieces instead allows for simplified usage when | |
173 | * the length is a known constant and the inputs are in registers. | |
174 | */ | |
175 | #define XXH_PRIME64_1 0x9E3779B185EBCA87ULL | |
176 | #define XXH_PRIME64_2 0xC2B2AE3D27D4EB4FULL | |
177 | #define XXH_PRIME64_3 0x165667B19E3779F9ULL | |
178 | #define XXH_PRIME64_4 0x85EBCA77C2B2AE63ULL | |
179 | #define XXH_PRIME64_5 0x27D4EB2F165667C5ULL | |
180 | ||
181 | static inline uint64_t XXH64_round(uint64_t acc, uint64_t input) | |
182 | { | |
183 | return rol64(acc + input * XXH_PRIME64_2, 31) * XXH_PRIME64_1; | |
184 | } | |
185 | ||
186 | static inline uint64_t XXH64_mergeround(uint64_t acc, uint64_t val) | |
187 | { | |
188 | return (acc ^ XXH64_round(0, val)) * XXH_PRIME64_1 + XXH_PRIME64_4; | |
189 | } | |
190 | ||
191 | static inline uint64_t XXH64_mergerounds(uint64_t v1, uint64_t v2, | |
192 | uint64_t v3, uint64_t v4) | |
193 | { | |
194 | uint64_t h64; | |
195 | ||
196 | h64 = rol64(v1, 1) + rol64(v2, 7) + rol64(v3, 12) + rol64(v4, 18); | |
197 | h64 = XXH64_mergeround(h64, v1); | |
198 | h64 = XXH64_mergeround(h64, v2); | |
199 | h64 = XXH64_mergeround(h64, v3); | |
200 | h64 = XXH64_mergeround(h64, v4); | |
201 | ||
202 | return h64; | |
203 | } | |
204 | ||
205 | static inline uint64_t XXH64_avalanche(uint64_t h64) | |
206 | { | |
207 | h64 ^= h64 >> 33; | |
208 | h64 *= XXH_PRIME64_2; | |
209 | h64 ^= h64 >> 29; | |
210 | h64 *= XXH_PRIME64_3; | |
211 | h64 ^= h64 >> 32; | |
212 | return h64; | |
213 | } | |
214 | ||
215 | static inline uint64_t qemu_xxhash64_4(uint64_t a, uint64_t b, | |
216 | uint64_t c, uint64_t d) | |
217 | { | |
218 | uint64_t v1 = QEMU_XXHASH_SEED + XXH_PRIME64_1 + XXH_PRIME64_2; | |
219 | uint64_t v2 = QEMU_XXHASH_SEED + XXH_PRIME64_2; | |
220 | uint64_t v3 = QEMU_XXHASH_SEED + 0; | |
221 | uint64_t v4 = QEMU_XXHASH_SEED - XXH_PRIME64_1; | |
222 | ||
223 | v1 = XXH64_round(v1, a); | |
224 | v2 = XXH64_round(v2, b); | |
225 | v3 = XXH64_round(v3, c); | |
226 | v4 = XXH64_round(v4, d); | |
227 | ||
228 | return XXH64_avalanche(XXH64_mergerounds(v1, v2, v3, v4)); | |
229 | } | |
230 | ||
fe656e31 | 231 | #endif /* QEMU_XXHASH_H */ |