]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
468cdd91 | 2 | * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc. |
064af421 | 3 | * |
a14bc59f BP |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
064af421 | 7 | * |
a14bc59f BP |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
064af421 BP |
15 | */ |
16 | #include <config.h> | |
17 | #include "hash.h" | |
18 | #include <string.h> | |
7376da64 | 19 | #include "unaligned.h" |
064af421 | 20 | |
1f26e796 | 21 | /* Returns the hash of 'a', 'b', and 'c'. */ |
cce1d8bd | 22 | uint32_t |
1f26e796 | 23 | hash_3words(uint32_t a, uint32_t b, uint32_t c) |
cce1d8bd | 24 | { |
33c6a1b9 | 25 | return hash_finish(hash_add(hash_add(hash_add(a, 0), b), c), 12); |
1f26e796 BP |
26 | } |
27 | ||
064af421 BP |
28 | /* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */ |
29 | uint32_t | |
30 | hash_bytes(const void *p_, size_t n, uint32_t basis) | |
31 | { | |
db5a1019 | 32 | const uint32_t *p = p_; |
c49d1dd1 BP |
33 | size_t orig_n = n; |
34 | uint32_t hash; | |
064af421 | 35 | |
c49d1dd1 BP |
36 | hash = basis; |
37 | while (n >= 4) { | |
33c6a1b9 | 38 | hash = hash_add(hash, get_unaligned_u32(p)); |
c49d1dd1 | 39 | n -= 4; |
db5a1019 | 40 | p += 1; |
064af421 BP |
41 | } |
42 | ||
43 | if (n) { | |
c49d1dd1 | 44 | uint32_t tmp = 0; |
7376da64 | 45 | |
c49d1dd1 | 46 | memcpy(&tmp, p, n); |
33c6a1b9 | 47 | hash = hash_add(hash, tmp); |
064af421 BP |
48 | } |
49 | ||
33c6a1b9 | 50 | return hash_finish(hash, orig_n); |
064af421 | 51 | } |
9879b94f | 52 | |
c49d1dd1 BP |
53 | uint32_t |
54 | hash_double(double x, uint32_t basis) | |
55 | { | |
56 | uint32_t value[2]; | |
57 | BUILD_ASSERT_DECL(sizeof x == sizeof value); | |
58 | ||
59 | memcpy(value, &x, sizeof value); | |
60 | return hash_3words(value[0], value[1], basis); | |
61 | } | |
ff8eeabd JR |
62 | |
63 | uint32_t | |
64 | hash_words__(const uint32_t p[], size_t n_words, uint32_t basis) | |
65 | { | |
66 | return hash_words_inline(p, n_words, basis); | |
67 | } | |
68 | ||
69 | uint32_t | |
4ad07ad7 | 70 | hash_words64__(const uint64_t p[], size_t n_words, uint32_t basis) |
ff8eeabd JR |
71 | { |
72 | return hash_words64_inline(p, n_words, basis); | |
73 | } | |
468cdd91 | 74 | |
d74c9202 | 75 | #if !(defined(__x86_64__)) && !(defined(__aarch64__)) |
468cdd91 JS |
76 | void |
77 | hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out) | |
78 | { | |
79 | const uint32_t c1 = 0x239b961b; | |
80 | const uint32_t c2 = 0xab0e9789; | |
81 | const uint32_t c3 = 0x38b34ae5; | |
82 | const uint32_t c4 = 0xa1e38b93; | |
83 | const uint8_t *tail, *data = (const uint8_t *)p_; | |
84 | const uint32_t *blocks = (const uint32_t *)p_; | |
85 | const int nblocks = len / 16; | |
86 | uint32_t h1 = basis; | |
87 | uint32_t h2 = basis; | |
88 | uint32_t h3 = basis; | |
89 | uint32_t h4 = basis; | |
468cdd91 JS |
90 | |
91 | /* Body */ | |
92 | for (int i = 0; i < nblocks; i++) { | |
93 | uint32_t k1 = get_unaligned_u32(&blocks[i * 4 + 0]); | |
94 | uint32_t k2 = get_unaligned_u32(&blocks[i * 4 + 1]); | |
95 | uint32_t k3 = get_unaligned_u32(&blocks[i * 4 + 2]); | |
96 | uint32_t k4 = get_unaligned_u32(&blocks[i * 4 + 3]); | |
97 | ||
98 | k1 *= c1; | |
99 | k1 = hash_rot(k1, 15); | |
100 | k1 *= c2; | |
101 | h1 ^= k1; | |
102 | ||
103 | h1 = hash_rot(h1, 19); | |
104 | h1 += h2; | |
105 | h1 = h1 * 5 + 0x561ccd1b; | |
106 | ||
107 | k2 *= c2; | |
108 | k2 = hash_rot(k2, 16); | |
109 | k2 *= c3; | |
110 | h2 ^= k2; | |
111 | ||
112 | h2 = hash_rot(h2, 17); | |
113 | h2 += h3; | |
114 | h2 = h2 * 5 + 0x0bcaa747; | |
115 | ||
116 | k3 *= c3; | |
117 | k3 = hash_rot(k3, 17); | |
118 | k3 *= c4; | |
119 | h3 ^= k3; | |
120 | ||
121 | h3 = hash_rot(h3, 15); | |
122 | h3 += h4; | |
123 | h3 = h3 * 5 + 0x96cd1c35; | |
124 | ||
125 | k4 *= c4; | |
126 | k4 = hash_rot(k4, 18); | |
127 | k4 *= c1; | |
128 | h4 ^= k4; | |
129 | ||
130 | h4 = hash_rot(h4, 13); | |
131 | h4 += h1; | |
132 | h4 = h4 * 5 + 0x32ac3b17; | |
133 | } | |
134 | ||
135 | /* Tail */ | |
71f21279 | 136 | uint32_t k1, k2, k3, k4; |
468cdd91 JS |
137 | k1 = k2 = k3 = k4 = 0; |
138 | tail = data + nblocks * 16; | |
139 | switch (len & 15) { | |
140 | case 15: | |
141 | k4 ^= tail[14] << 16; | |
f3eb7691 | 142 | /* fall through */ |
468cdd91 JS |
143 | case 14: |
144 | k4 ^= tail[13] << 8; | |
f3eb7691 | 145 | /* fall through */ |
468cdd91 JS |
146 | case 13: |
147 | k4 ^= tail[12] << 0; | |
148 | k4 *= c4; | |
149 | k4 = hash_rot(k4, 18); | |
150 | k4 *= c1; | |
151 | h4 ^= k4; | |
f3eb7691 | 152 | /* fall through */ |
468cdd91 JS |
153 | |
154 | case 12: | |
155 | k3 ^= tail[11] << 24; | |
f3eb7691 | 156 | /* fall through */ |
468cdd91 JS |
157 | case 11: |
158 | k3 ^= tail[10] << 16; | |
f3eb7691 | 159 | /* fall through */ |
468cdd91 JS |
160 | case 10: |
161 | k3 ^= tail[9] << 8; | |
f3eb7691 | 162 | /* fall through */ |
468cdd91 JS |
163 | case 9: |
164 | k3 ^= tail[8] << 0; | |
165 | k3 *= c3; | |
166 | k3 = hash_rot(k3, 17); | |
167 | k3 *= c4; | |
168 | h3 ^= k3; | |
f3eb7691 | 169 | /* fall through */ |
468cdd91 JS |
170 | |
171 | case 8: | |
172 | k2 ^= tail[7] << 24; | |
f3eb7691 | 173 | /* fall through */ |
468cdd91 JS |
174 | case 7: |
175 | k2 ^= tail[6] << 16; | |
f3eb7691 | 176 | /* fall through */ |
468cdd91 JS |
177 | case 6: |
178 | k2 ^= tail[5] << 8; | |
f3eb7691 | 179 | /* fall through */ |
468cdd91 JS |
180 | case 5: |
181 | k2 ^= tail[4] << 0; | |
182 | k2 *= c2; | |
183 | k2 = hash_rot(k2, 16); | |
184 | k2 *= c3; | |
185 | h2 ^= k2; | |
f3eb7691 | 186 | /* fall through */ |
468cdd91 JS |
187 | |
188 | case 4: | |
189 | k1 ^= tail[3] << 24; | |
f3eb7691 | 190 | /* fall through */ |
468cdd91 JS |
191 | case 3: |
192 | k1 ^= tail[2] << 16; | |
f3eb7691 | 193 | /* fall through */ |
468cdd91 JS |
194 | case 2: |
195 | k1 ^= tail[1] << 8; | |
f3eb7691 | 196 | /* fall through */ |
468cdd91 JS |
197 | case 1: |
198 | k1 ^= tail[0] << 0; | |
199 | k1 *= c1; | |
200 | k1 = hash_rot(k1, 15); | |
201 | k1 *= c2; | |
202 | h1 ^= k1; | |
203 | }; | |
204 | ||
205 | /* Finalization */ | |
206 | h1 ^= len; | |
207 | h2 ^= len; | |
208 | h3 ^= len; | |
209 | h4 ^= len; | |
210 | ||
211 | h1 += h2; | |
212 | h1 += h3; | |
213 | h1 += h4; | |
214 | h2 += h1; | |
215 | h3 += h1; | |
216 | h4 += h1; | |
217 | ||
218 | h1 = mhash_finish(h1); | |
219 | h2 = mhash_finish(h2); | |
220 | h3 = mhash_finish(h3); | |
221 | h4 = mhash_finish(h4); | |
222 | ||
223 | h1 += h2; | |
224 | h1 += h3; | |
225 | h1 += h4; | |
226 | h2 += h1; | |
227 | h3 += h1; | |
228 | h4 += h1; | |
229 | ||
230 | out->u32[0] = h1; | |
231 | out->u32[1] = h2; | |
232 | out->u32[2] = h3; | |
233 | out->u32[3] = h4; | |
234 | } | |
235 | ||
d74c9202 | 236 | #else /* __x86_64__ or __aarch64__*/ |
468cdd91 JS |
237 | |
238 | static inline uint64_t | |
239 | hash_rot64(uint64_t x, int8_t r) | |
240 | { | |
241 | return (x << r) | (x >> (64 - r)); | |
242 | } | |
243 | ||
244 | static inline uint64_t | |
245 | fmix64(uint64_t k) | |
246 | { | |
247 | k ^= k >> 33; | |
248 | k *= 0xff51afd7ed558ccdULL; | |
249 | k ^= k >> 33; | |
250 | k *= 0xc4ceb9fe1a85ec53ULL; | |
251 | k ^= k >> 33; | |
252 | ||
253 | return k; | |
254 | } | |
255 | ||
256 | void | |
257 | hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out) | |
258 | { | |
259 | const uint64_t c1 = 0x87c37b91114253d5ULL; | |
260 | const uint64_t c2 = 0x4cf5ad432745937fULL; | |
261 | const uint8_t *tail, *data = (const uint8_t *)p_; | |
262 | const uint64_t *blocks = (const uint64_t *)p_; | |
263 | const int nblocks = len / 16; | |
264 | uint64_t h1 = basis; | |
265 | uint64_t h2 = basis; | |
266 | uint64_t k1, k2; | |
267 | ||
268 | /* Body */ | |
269 | for (int i = 0; i < nblocks; i++) { | |
270 | k1 = get_unaligned_u64(&blocks[i * 2 + 0]); | |
271 | k2 = get_unaligned_u64(&blocks[i * 2 + 1]); | |
272 | ||
273 | k1 *= c1; | |
274 | k1 = hash_rot64(k1, 31); | |
275 | k1 *= c2; | |
276 | h1 ^= k1; | |
277 | ||
278 | h1 = hash_rot64(h1, 27); | |
279 | h1 += h2; | |
280 | h1 = h1 * 5 + 0x52dce729; | |
281 | ||
282 | k2 *= c2; | |
283 | k2 = hash_rot64(k2, 33); | |
284 | k2 *= c1; | |
285 | h2 ^= k2; | |
286 | ||
287 | h2 = hash_rot64(h2, 31); | |
288 | h2 += h1; | |
289 | h2 = h2 * 5 + 0x38495ab5; | |
290 | } | |
291 | ||
292 | /* Tail */ | |
293 | k1 = 0; | |
294 | k2 = 0; | |
295 | tail = data + nblocks * 16; | |
296 | switch (len & 15) { | |
297 | case 15: | |
298 | k2 ^= ((uint64_t) tail[14]) << 48; | |
73c7216a | 299 | /* fall through */ |
468cdd91 JS |
300 | case 14: |
301 | k2 ^= ((uint64_t) tail[13]) << 40; | |
73c7216a | 302 | /* fall through */ |
468cdd91 JS |
303 | case 13: |
304 | k2 ^= ((uint64_t) tail[12]) << 32; | |
73c7216a | 305 | /* fall through */ |
468cdd91 JS |
306 | case 12: |
307 | k2 ^= ((uint64_t) tail[11]) << 24; | |
73c7216a | 308 | /* fall through */ |
468cdd91 JS |
309 | case 11: |
310 | k2 ^= ((uint64_t) tail[10]) << 16; | |
73c7216a | 311 | /* fall through */ |
468cdd91 JS |
312 | case 10: |
313 | k2 ^= ((uint64_t) tail[9]) << 8; | |
73c7216a | 314 | /* fall through */ |
468cdd91 JS |
315 | case 9: |
316 | k2 ^= ((uint64_t) tail[8]) << 0; | |
317 | k2 *= c2; | |
318 | k2 = hash_rot64(k2, 33); | |
319 | k2 *= c1; | |
320 | h2 ^= k2; | |
73c7216a | 321 | /* fall through */ |
468cdd91 JS |
322 | case 8: |
323 | k1 ^= ((uint64_t) tail[7]) << 56; | |
73c7216a | 324 | /* fall through */ |
468cdd91 JS |
325 | case 7: |
326 | k1 ^= ((uint64_t) tail[6]) << 48; | |
73c7216a | 327 | /* fall through */ |
468cdd91 JS |
328 | case 6: |
329 | k1 ^= ((uint64_t) tail[5]) << 40; | |
73c7216a | 330 | /* fall through */ |
468cdd91 JS |
331 | case 5: |
332 | k1 ^= ((uint64_t) tail[4]) << 32; | |
73c7216a | 333 | /* fall through */ |
468cdd91 JS |
334 | case 4: |
335 | k1 ^= ((uint64_t) tail[3]) << 24; | |
73c7216a | 336 | /* fall through */ |
468cdd91 JS |
337 | case 3: |
338 | k1 ^= ((uint64_t) tail[2]) << 16; | |
73c7216a | 339 | /* fall through */ |
468cdd91 JS |
340 | case 2: |
341 | k1 ^= ((uint64_t) tail[1]) << 8; | |
73c7216a | 342 | /* fall through */ |
468cdd91 JS |
343 | case 1: |
344 | k1 ^= ((uint64_t) tail[0]) << 0; | |
345 | k1 *= c1; | |
346 | k1 = hash_rot64(k1, 31); | |
347 | k1 *= c2; | |
348 | h1 ^= k1; | |
349 | }; | |
350 | ||
351 | /* Finalization */ | |
352 | h1 ^= len; | |
353 | h2 ^= len; | |
354 | h1 += h2; | |
355 | h2 += h1; | |
356 | h1 = fmix64(h1); | |
357 | h2 = fmix64(h2); | |
358 | h1 += h2; | |
359 | h2 += h1; | |
360 | ||
361 | out->u64.lo = h1; | |
362 | out->u64.hi = h2; | |
363 | } | |
d74c9202 | 364 | #endif /* __x86_64__ or __aarch64__*/ |