Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc.
3 : : *
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:
7 : : *
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.
15 : : */
16 : : #include <config.h>
17 : : #include "hash.h"
18 : : #include <string.h>
19 : : #include "unaligned.h"
20 : :
21 : : /* Returns the hash of 'a', 'b', and 'c'. */
22 : : uint32_t
23 : 45672 : hash_3words(uint32_t a, uint32_t b, uint32_t c)
24 : : {
25 : 45672 : return hash_finish(hash_add(hash_add(hash_add(a, 0), b), c), 12);
26 : : }
27 : :
28 : : /* Returns the hash of the 'n' bytes at 'p', starting from 'basis'. */
29 : : uint32_t
30 : 57931621 : hash_bytes(const void *p_, size_t n, uint32_t basis)
31 : : {
32 : 57931621 : const uint32_t *p = p_;
33 : 57931621 : size_t orig_n = n;
34 : : uint32_t hash;
35 : :
36 : 57931621 : hash = basis;
37 [ + + ]: 151334616 : while (n >= 4) {
38 : 93403075 : hash = hash_add(hash, get_unaligned_u32(p));
39 : 93402995 : n -= 4;
40 : 93402995 : p += 1;
41 : : }
42 : :
43 [ + + ]: 57931541 : if (n) {
44 : 41513158 : uint32_t tmp = 0;
45 : :
46 : 41513158 : memcpy(&tmp, p, n);
47 : 41513158 : hash = hash_add(hash, tmp);
48 : : }
49 : :
50 : 57931541 : return hash_finish(hash, orig_n);
51 : : }
52 : :
53 : : uint32_t
54 : 1439 : hash_double(double x, uint32_t basis)
55 : : {
56 : : uint32_t value[2];
57 : : BUILD_ASSERT_DECL(sizeof x == sizeof value);
58 : :
59 : 1439 : memcpy(value, &x, sizeof value);
60 : 1439 : return hash_3words(value[0], value[1], basis);
61 : : }
62 : :
63 : : uint32_t
64 : 6908994 : hash_words__(const uint32_t p[], size_t n_words, uint32_t basis)
65 : : {
66 : 6908994 : return hash_words_inline(p, n_words, basis);
67 : : }
68 : :
69 : : uint32_t
70 : 4372417 : hash_words64__(const uint64_t p[], size_t n_words, uint32_t basis)
71 : : {
72 : 4372417 : return hash_words64_inline(p, n_words, basis);
73 : : }
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 : 137463133 : hash_rot64(uint64_t x, int8_t r)
226 : : {
227 : 137463133 : return (x << r) | (x >> (64 - r));
228 : : }
229 : :
230 : : static inline uint64_t
231 : 4265246 : fmix64(uint64_t k)
232 : : {
233 : 4265246 : k ^= k >> 33;
234 : 4265246 : k *= 0xff51afd7ed558ccdULL;
235 : 4265246 : k ^= k >> 33;
236 : 4265246 : k *= 0xc4ceb9fe1a85ec53ULL;
237 : 4265246 : k ^= k >> 33;
238 : :
239 : 4265246 : return k;
240 : : }
241 : :
242 : : void
243 : 2132623 : hash_bytes128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
244 : : {
245 : 2132623 : const uint64_t c1 = 0x87c37b91114253d5ULL;
246 : 2132623 : const uint64_t c2 = 0x4cf5ad432745937fULL;
247 : 2132623 : const uint8_t *tail, *data = (const uint8_t *)p_;
248 : 2132623 : const uint64_t *blocks = (const uint64_t *)p_;
249 : 2132623 : const int nblocks = len / 16;
250 : 2132623 : uint64_t h1 = basis;
251 : 2132623 : uint64_t h2 = basis;
252 : : uint64_t k1, k2;
253 : :
254 : : /* Body */
255 [ + + ]: 36493094 : for (int i = 0; i < nblocks; i++) {
256 : 34360471 : k1 = get_unaligned_u64(&blocks[i * 2 + 0]);
257 : 34360471 : k2 = get_unaligned_u64(&blocks[i * 2 + 1]);
258 : :
259 : 34360471 : k1 *= c1;
260 : 34360471 : k1 = hash_rot64(k1, 31);
261 : 34360471 : k1 *= c2;
262 : 34360471 : h1 ^= k1;
263 : :
264 : 34360471 : h1 = hash_rot64(h1, 27);
265 : 34360471 : h1 += h2;
266 : 34360471 : h1 = h1 * 5 + 0x52dce729;
267 : :
268 : 34360471 : k2 *= c2;
269 : 34360471 : k2 = hash_rot64(k2, 33);
270 : 34360471 : k2 *= c1;
271 : 34360471 : h2 ^= k2;
272 : :
273 : 34360471 : h2 = hash_rot64(h2, 31);
274 : 34360471 : h2 += h1;
275 : 34360471 : h2 = h2 * 5 + 0x38495ab5;
276 : : }
277 : :
278 : : /* Tail */
279 : 2132623 : k1 = 0;
280 : 2132623 : k2 = 0;
281 : 2132623 : tail = data + nblocks * 16;
282 [ - - - + : 2132623 : switch (len & 15) {
- - - + -
- - + - -
- + ]
283 : : case 15:
284 : 0 : k2 ^= ((uint64_t) tail[14]) << 48;
285 : : case 14:
286 : 0 : k2 ^= ((uint64_t) tail[13]) << 40;
287 : : case 13:
288 : 0 : k2 ^= ((uint64_t) tail[12]) << 32;
289 : : case 12:
290 : 527 : k2 ^= ((uint64_t) tail[11]) << 24;
291 : : case 11:
292 : 527 : k2 ^= ((uint64_t) tail[10]) << 16;
293 : : case 10:
294 : 527 : k2 ^= ((uint64_t) tail[9]) << 8;
295 : : case 9:
296 : 527 : k2 ^= ((uint64_t) tail[8]) << 0;
297 : 527 : k2 *= c2;
298 : 527 : k2 = hash_rot64(k2, 33);
299 : 527 : k2 *= c1;
300 : 527 : h2 ^= k2;
301 : :
302 : : case 8:
303 : 20131 : k1 ^= ((uint64_t) tail[7]) << 56;
304 : : case 7:
305 : 20131 : k1 ^= ((uint64_t) tail[6]) << 48;
306 : : case 6:
307 : 20131 : k1 ^= ((uint64_t) tail[5]) << 40;
308 : : case 5:
309 : 20131 : k1 ^= ((uint64_t) tail[4]) << 32;
310 : : case 4:
311 : 20722 : k1 ^= ((uint64_t) tail[3]) << 24;
312 : : case 3:
313 : 20722 : k1 ^= ((uint64_t) tail[2]) << 16;
314 : : case 2:
315 : 20722 : k1 ^= ((uint64_t) tail[1]) << 8;
316 : : case 1:
317 : 20722 : k1 ^= ((uint64_t) tail[0]) << 0;
318 : 20722 : k1 *= c1;
319 : 20722 : k1 = hash_rot64(k1, 31);
320 : 20722 : k1 *= c2;
321 : 20722 : h1 ^= k1;
322 : : };
323 : :
324 : : /* Finalization */
325 : 2132623 : h1 ^= len;
326 : 2132623 : h2 ^= len;
327 : 2132623 : h1 += h2;
328 : 2132623 : h2 += h1;
329 : 2132623 : h1 = fmix64(h1);
330 : 2132623 : h2 = fmix64(h2);
331 : 2132623 : h1 += h2;
332 : 2132623 : h2 += h1;
333 : :
334 : 2132623 : out->u64.lo = h1;
335 : 2132623 : out->u64.hi = h2;
336 : 2132623 : }
337 : : #endif /* __x86_64__ */
|
