]>
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 JS |
74 | |
75 | #if !(defined(__x86_64__)) | |
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; | |
90 | uint32_t k1, k2, k3, k4; | |
91 | ||
92 | /* Body */ | |
93 | for (int i = 0; i < nblocks; i++) { | |
94 | uint32_t k1 = get_unaligned_u32(&blocks[i * 4 + 0]); | |
95 | uint32_t k2 = get_unaligned_u32(&blocks[i * 4 + 1]); | |
96 | uint32_t k3 = get_unaligned_u32(&blocks[i * 4 + 2]); | |
97 | uint32_t k4 = get_unaligned_u32(&blocks[i * 4 + 3]); | |
98 | ||
99 | k1 *= c1; | |
100 | k1 = hash_rot(k1, 15); | |
101 | k1 *= c2; | |
102 | h1 ^= k1; | |
103 | ||
104 | h1 = hash_rot(h1, 19); | |
105 | h1 += h2; | |
106 | h1 = h1 * 5 + 0x561ccd1b; | |
107 | ||
108 | k2 *= c2; | |
109 | k2 = hash_rot(k2, 16); | |
110 | k2 *= c3; | |
111 | h2 ^= k2; | |
112 | ||
113 | h2 = hash_rot(h2, 17); | |
114 | h2 += h3; | |
115 | h2 = h2 * 5 + 0x0bcaa747; | |
116 | ||
117 | k3 *= c3; | |
118 | k3 = hash_rot(k3, 17); | |
119 | k3 *= c4; | |
120 | h3 ^= k3; | |
121 | ||
122 | h3 = hash_rot(h3, 15); | |
123 | h3 += h4; | |
124 | h3 = h3 * 5 + 0x96cd1c35; | |
125 | ||
126 | k4 *= c4; | |
127 | k4 = hash_rot(k4, 18); | |
128 | k4 *= c1; | |
129 | h4 ^= k4; | |
130 | ||
131 | h4 = hash_rot(h4, 13); | |
132 | h4 += h1; | |
133 | h4 = h4 * 5 + 0x32ac3b17; | |
134 | } | |
135 | ||
136 | /* Tail */ | |
137 | k1 = k2 = k3 = k4 = 0; | |
138 | tail = data + nblocks * 16; | |
139 | switch (len & 15) { | |
140 | case 15: | |
141 | k4 ^= tail[14] << 16; | |
142 | case 14: | |
143 | k4 ^= tail[13] << 8; | |
144 | case 13: | |
145 | k4 ^= tail[12] << 0; | |
146 | k4 *= c4; | |
147 | k4 = hash_rot(k4, 18); | |
148 | k4 *= c1; | |
149 | h4 ^= k4; | |
150 | ||
151 | case 12: | |
152 | k3 ^= tail[11] << 24; | |
153 | case 11: | |
154 | k3 ^= tail[10] << 16; | |
155 | case 10: | |
156 | k3 ^= tail[9] << 8; | |
157 | case 9: | |
158 | k3 ^= tail[8] << 0; | |
159 | k3 *= c3; | |
160 | k3 = hash_rot(k3, 17); | |
161 | k3 *= c4; | |
162 | h3 ^= k3; | |
163 | ||
164 | case 8: | |
165 | k2 ^= tail[7] << 24; | |
166 | case 7: | |
167 | k2 ^= tail[6] << 16; | |
168 | case 6: | |
169 | k2 ^= tail[5] << 8; | |
170 | case 5: | |
171 | k2 ^= tail[4] << 0; | |
172 | k2 *= c2; | |
173 | k2 = hash_rot(k2, 16); | |
174 | k2 *= c3; | |
175 | h2 ^= k2; | |
176 | ||
177 | case 4: | |
178 | k1 ^= tail[3] << 24; | |
179 | case 3: | |
180 | k1 ^= tail[2] << 16; | |
181 | case 2: | |
182 | k1 ^= tail[1] << 8; | |
183 | case 1: | |
184 | k1 ^= tail[0] << 0; | |
185 | k1 *= c1; | |
186 | k1 = hash_rot(k1, 15); | |
187 | k1 *= c2; | |
188 | h1 ^= k1; | |
189 | }; | |
190 | ||
191 | /* Finalization */ | |
192 | h1 ^= len; | |
193 | h2 ^= len; | |
194 | h3 ^= len; | |
195 | h4 ^= len; | |
196 | ||
197 | h1 += h2; | |
198 | h1 += h3; | |
199 | h1 += h4; | |
200 | h2 += h1; | |
201 | h3 += h1; | |
202 | h4 += h1; | |
203 | ||
204 | h1 = mhash_finish(h1); | |
205 | h2 = mhash_finish(h2); | |
206 | h3 = mhash_finish(h3); | |
207 | h4 = mhash_finish(h4); | |
208 | ||
209 | h1 += h2; | |
210 | h1 += h3; | |
211 | h1 += h4; | |
212 | h2 += h1; | |
213 | h3 += h1; | |
214 | h4 += h1; | |
215 | ||
216 | out->u32[0] = h1; | |
217 | out->u32[1] = h2; | |
218 | out->u32[2] = h3; | |
219 | out->u32[3] = h4; | |
220 | } | |
221 | ||
222 | #else /* __x86_64__ */ | |
223 | ||
224 | static inline uint64_t | |
225 | hash_rot64(uint64_t x, int8_t r) | |
226 | { | |
227 | return (x << r) | (x >> (64 - r)); | |
228 | } | |
229 | ||
230 | static inline uint64_t | |
231 | fmix64(uint64_t k) | |
232 | { | |
233 | k ^= k >> 33; | |
234 | k *= 0xff51afd7ed558ccdULL; | |
235 | k ^= k >> 33; | |
236 | k *= 0xc4ceb9fe1a85ec53ULL; | |
237 | k ^= k >> 33; | |
238 | ||
239 | return k; | |
240 | } | |
241 | ||
242 | void | |
243 | hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out) | |
244 | { | |
245 | const uint64_t c1 = 0x87c37b91114253d5ULL; | |
246 | const uint64_t c2 = 0x4cf5ad432745937fULL; | |
247 | const uint8_t *tail, *data = (const uint8_t *)p_; | |
248 | const uint64_t *blocks = (const uint64_t *)p_; | |
249 | const int nblocks = len / 16; | |
250 | uint64_t h1 = basis; | |
251 | uint64_t h2 = basis; | |
252 | uint64_t k1, k2; | |
253 | ||
254 | /* Body */ | |
255 | for (int i = 0; i < nblocks; i++) { | |
256 | k1 = get_unaligned_u64(&blocks[i * 2 + 0]); | |
257 | k2 = get_unaligned_u64(&blocks[i * 2 + 1]); | |
258 | ||
259 | k1 *= c1; | |
260 | k1 = hash_rot64(k1, 31); | |
261 | k1 *= c2; | |
262 | h1 ^= k1; | |
263 | ||
264 | h1 = hash_rot64(h1, 27); | |
265 | h1 += h2; | |
266 | h1 = h1 * 5 + 0x52dce729; | |
267 | ||
268 | k2 *= c2; | |
269 | k2 = hash_rot64(k2, 33); | |
270 | k2 *= c1; | |
271 | h2 ^= k2; | |
272 | ||
273 | h2 = hash_rot64(h2, 31); | |
274 | h2 += h1; | |
275 | h2 = h2 * 5 + 0x38495ab5; | |
276 | } | |
277 | ||
278 | /* Tail */ | |
279 | k1 = 0; | |
280 | k2 = 0; | |
281 | tail = data + nblocks * 16; | |
282 | switch (len & 15) { | |
283 | case 15: | |
284 | k2 ^= ((uint64_t) tail[14]) << 48; | |
285 | case 14: | |
286 | k2 ^= ((uint64_t) tail[13]) << 40; | |
287 | case 13: | |
288 | k2 ^= ((uint64_t) tail[12]) << 32; | |
289 | case 12: | |
290 | k2 ^= ((uint64_t) tail[11]) << 24; | |
291 | case 11: | |
292 | k2 ^= ((uint64_t) tail[10]) << 16; | |
293 | case 10: | |
294 | k2 ^= ((uint64_t) tail[9]) << 8; | |
295 | case 9: | |
296 | k2 ^= ((uint64_t) tail[8]) << 0; | |
297 | k2 *= c2; | |
298 | k2 = hash_rot64(k2, 33); | |
299 | k2 *= c1; | |
300 | h2 ^= k2; | |
301 | ||
302 | case 8: | |
303 | k1 ^= ((uint64_t) tail[7]) << 56; | |
304 | case 7: | |
305 | k1 ^= ((uint64_t) tail[6]) << 48; | |
306 | case 6: | |
307 | k1 ^= ((uint64_t) tail[5]) << 40; | |
308 | case 5: | |
309 | k1 ^= ((uint64_t) tail[4]) << 32; | |
310 | case 4: | |
311 | k1 ^= ((uint64_t) tail[3]) << 24; | |
312 | case 3: | |
313 | k1 ^= ((uint64_t) tail[2]) << 16; | |
314 | case 2: | |
315 | k1 ^= ((uint64_t) tail[1]) << 8; | |
316 | case 1: | |
317 | k1 ^= ((uint64_t) tail[0]) << 0; | |
318 | k1 *= c1; | |
319 | k1 = hash_rot64(k1, 31); | |
320 | k1 *= c2; | |
321 | h1 ^= k1; | |
322 | }; | |
323 | ||
324 | /* Finalization */ | |
325 | h1 ^= len; | |
326 | h2 ^= len; | |
327 | h1 += h2; | |
328 | h2 += h1; | |
329 | h1 = fmix64(h1); | |
330 | h2 = fmix64(h2); | |
331 | h1 += h2; | |
332 | h2 += h1; | |
333 | ||
334 | out->u64.lo = h1; | |
335 | out->u64.hi = h2; | |
336 | } | |
337 | #endif /* __x86_64__ */ |