]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
afb50572 | 2 | * Copyright (c) 2009, 2012, 2014, 2015 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 | ||
17 | #include <config.h> | |
3f636c7e JR |
18 | #undef NDEBUG |
19 | #include "hash.h" | |
20 | #include <assert.h> | |
064af421 BP |
21 | #include <inttypes.h> |
22 | #include <stdio.h> | |
23 | #include <stdlib.h> | |
24 | #include <string.h> | |
c49d1dd1 | 25 | #include "jhash.h" |
eadd1644 | 26 | #include "ovstest.h" |
064af421 | 27 | |
064af421 BP |
28 | static void |
29 | set_bit(uint32_t array[3], int bit) | |
30 | { | |
31 | assert(bit >= 0 && bit <= 96); | |
32 | memset(array, 0, sizeof(uint32_t) * 3); | |
33 | if (bit < 96) { | |
34 | array[bit / 32] = UINT32_C(1) << (bit % 32); | |
35 | } | |
36 | } | |
37 | ||
afb50572 | 38 | /* When bit == n_bits, the function just 0 sets the 'values'. */ |
468cdd91 | 39 | static void |
afb50572 | 40 | set_bit128(ovs_u128 *values, int bit, int n_bits) |
468cdd91 JS |
41 | { |
42 | assert(bit >= 0 && bit <= 2048); | |
afb50572 AW |
43 | memset(values, 0, n_bits/8); |
44 | if (bit < n_bits) { | |
468cdd91 JS |
45 | int b = bit % 128; |
46 | ||
47 | if (b < 64) { | |
afb50572 | 48 | values[bit / 128].u64.lo = UINT64_C(1) << (b % 64); |
468cdd91 | 49 | } else { |
afb50572 | 50 | values[bit / 128].u64.hi = UINT64_C(1) << (b % 64); |
468cdd91 JS |
51 | } |
52 | } | |
53 | } | |
54 | ||
afb50572 AW |
55 | static uint64_t |
56 | get_range128(ovs_u128 *value, int ofs, uint64_t mask) | |
57 | { | |
58 | return ((ofs < 64 ? (value->u64.lo >> ofs) : 0) & mask) | |
59 | | ((ofs <= 64 ? (value->u64.hi << (64 - ofs)) : (value->u64.hi >> (ofs - 64)) & mask)); | |
60 | } | |
61 | ||
064af421 BP |
62 | static uint32_t |
63 | hash_words_cb(uint32_t input) | |
64 | { | |
65 | return hash_words(&input, 1, 0); | |
66 | } | |
67 | ||
9879b94f | 68 | static uint32_t |
c49d1dd1 | 69 | jhash_words_cb(uint32_t input) |
9879b94f | 70 | { |
c49d1dd1 | 71 | return jhash_words(&input, 1, 0); |
9879b94f BP |
72 | } |
73 | ||
064af421 BP |
74 | static uint32_t |
75 | hash_int_cb(uint32_t input) | |
76 | { | |
77 | return hash_int(input, 0); | |
78 | } | |
79 | ||
80 | static void | |
81 | check_word_hash(uint32_t (*hash)(uint32_t), const char *name, | |
82 | int min_unique) | |
83 | { | |
84 | int i, j; | |
85 | ||
86 | for (i = 0; i <= 32; i++) { | |
87 | uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0; | |
88 | for (j = i + 1; j <= 32; j++) { | |
89 | uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0; | |
90 | uint32_t out1 = hash(in1); | |
91 | uint32_t out2 = hash(in2); | |
92 | const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1; | |
93 | int ofs; | |
94 | for (ofs = 0; ofs < 32 - min_unique; ofs++) { | |
95 | uint32_t bits1 = (out1 >> ofs) & unique_mask; | |
96 | uint32_t bits2 = (out2 >> ofs) & unique_mask; | |
97 | if (bits1 == bits2) { | |
98 | printf("Partial collision for '%s':\n", name); | |
99 | printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1); | |
100 | printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2); | |
101 | printf("%d bits of output starting at bit %d " | |
102 | "are both 0x%"PRIx32"\n", min_unique, ofs, bits1); | |
064af421 BP |
103 | } |
104 | } | |
105 | } | |
106 | } | |
107 | } | |
108 | ||
9879b94f BP |
109 | static void |
110 | check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t), | |
111 | const char *name) | |
064af421 BP |
112 | { |
113 | int i, j; | |
114 | ||
9879b94f BP |
115 | for (i = 0; i <= 96; i++) { |
116 | for (j = i + 1; j <= 96; j++) { | |
ff8eeabd JR |
117 | uint32_t in0[3], in1[3], in2[3]; |
118 | uint32_t out0,out1, out2; | |
9879b94f BP |
119 | const int min_unique = 12; |
120 | const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1; | |
121 | ||
ff8eeabd | 122 | set_bit(in0, i); |
9879b94f BP |
123 | set_bit(in1, i); |
124 | set_bit(in2, j); | |
ff8eeabd | 125 | out0 = hash(in0, 3, 0); |
9879b94f BP |
126 | out1 = hash(in1, 3, 0); |
127 | out2 = hash(in2, 3, 0); | |
ff8eeabd JR |
128 | |
129 | if (out0 != out1) { | |
130 | printf("%s hash not the same for non-64 aligned data " | |
131 | "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1); | |
132 | } | |
9879b94f BP |
133 | if ((out1 & unique_mask) == (out2 & unique_mask)) { |
134 | printf("%s has a partial collision:\n", name); | |
135 | printf("hash(1 << %d) == %08"PRIx32"\n", i, out1); | |
136 | printf("hash(1 << %d) == %08"PRIx32"\n", j, out2); | |
137 | printf("The low-order %d bits of output are both " | |
138 | "0x%"PRIx32"\n", min_unique, out1 & unique_mask); | |
139 | } | |
140 | } | |
141 | } | |
142 | } | |
143 | ||
afb50572 AW |
144 | static void |
145 | check_hash_bytes128(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *), | |
146 | const char *name, const int min_unique) | |
147 | { | |
148 | const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1; | |
149 | const int n_bits = sizeof(ovs_u128) * 8; | |
150 | int i, j; | |
151 | ||
152 | for (i = 0; i <= n_bits; i++) { | |
153 | OVS_PACKED(struct offset_ovs_u128 { | |
154 | uint32_t a; | |
155 | ovs_u128 b; | |
11d9ad2d JS |
156 | }) in0; |
157 | ovs_u128 in1; | |
afb50572 AW |
158 | ovs_u128 out0, out1; |
159 | ||
afb50572 | 160 | set_bit128(&in1, i, n_bits); |
11d9ad2d JS |
161 | in0.b = in1; |
162 | hash(&in0.b, sizeof(ovs_u128), 0, &out0); | |
afb50572 | 163 | hash(&in1, sizeof(ovs_u128), 0, &out1); |
2ff8484b | 164 | if (!ovs_u128_equals(out0, out1)) { |
afb50572 AW |
165 | printf("%s hash not the same for non-64 aligned data " |
166 | "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n", | |
167 | name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi); | |
168 | } | |
169 | ||
170 | for (j = i + 1; j <= n_bits; j++) { | |
171 | ovs_u128 in2; | |
172 | ovs_u128 out2; | |
173 | int ofs; | |
174 | ||
175 | set_bit128(&in2, j, n_bits); | |
176 | hash(&in2, sizeof(ovs_u128), 0, &out2); | |
177 | for (ofs = 0; ofs < 128 - min_unique; ofs++) { | |
178 | uint64_t bits1 = get_range128(&out1, ofs, unique_mask); | |
179 | uint64_t bits2 = get_range128(&out2, ofs, unique_mask); | |
180 | ||
181 | if (bits1 == bits2) { | |
182 | printf("%s has a partial collision:\n", name); | |
183 | printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n", | |
184 | i, out1.u64.hi, out1.u64.lo); | |
185 | printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n", | |
186 | j, out2.u64.hi, out2.u64.lo); | |
187 | printf("%d bits of output starting at bit %d " | |
188 | "are both 0x%016"PRIx64"\n", min_unique, ofs, bits1); | |
189 | } | |
190 | } | |
191 | } | |
192 | } | |
193 | } | |
194 | ||
468cdd91 JS |
195 | static void |
196 | check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *), | |
197 | const char *name, const int min_unique) | |
198 | { | |
199 | const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1; | |
afb50572 | 200 | const int n_bits = sizeof(ovs_u128) * 8 * 16; |
468cdd91 JS |
201 | int i, j; |
202 | ||
59f280f1 | 203 | for (i = 0; i <= n_bits; i++) { |
135fec59 AW |
204 | OVS_PACKED(struct offset_ovs_u128 { |
205 | uint32_t a; | |
206 | ovs_u128 b[16]; | |
11d9ad2d JS |
207 | }) in0; |
208 | ovs_u128 in1[16]; | |
135fec59 AW |
209 | ovs_u128 out0, out1; |
210 | ||
afb50572 | 211 | set_bit128(in1, i, n_bits); |
11d9ad2d JS |
212 | for (j = 0; j < 16; j++) { |
213 | in0.b[j] = in1[j]; | |
214 | } | |
215 | hash(&in0.b, sizeof(ovs_u128) * 16, 0, &out0); | |
135fec59 | 216 | hash(in1, sizeof(ovs_u128) * 16, 0, &out1); |
2ff8484b | 217 | if (!ovs_u128_equals(out0, out1)) { |
135fec59 AW |
218 | printf("%s hash not the same for non-64 aligned data " |
219 | "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n", | |
220 | name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi); | |
221 | } | |
222 | ||
59f280f1 | 223 | for (j = i + 1; j <= n_bits; j++) { |
135fec59 AW |
224 | ovs_u128 in2[16]; |
225 | ovs_u128 out2; | |
226 | ||
afb50572 | 227 | set_bit128(in2, j, n_bits); |
468cdd91 | 228 | hash(in2, sizeof(ovs_u128) * 16, 0, &out2); |
468cdd91 JS |
229 | if ((out1.u64.lo & unique_mask) == (out2.u64.lo & unique_mask)) { |
230 | printf("%s has a partial collision:\n", name); | |
231 | printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", i, | |
232 | out1.u64.hi, out1.u64.lo); | |
233 | printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", j, | |
234 | out2.u64.hi, out2.u64.lo); | |
235 | printf("The low-order %d bits of output are both " | |
236 | "0x%"PRIx64"\n", min_unique, out1.u64.lo & unique_mask); | |
237 | } | |
238 | } | |
239 | } | |
240 | } | |
241 | ||
eadd1644 AZ |
242 | static void |
243 | test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED) | |
9879b94f | 244 | { |
6cc59853 AW |
245 | /* |
246 | * The following tests check that all hashes computed with hash_function | |
247 | * with one 1-bit (or no 1-bits) set within a X-bit word have different | |
248 | * values in all N-bit consecutive comparisons. | |
249 | * | |
250 | * test_function(hash_function, test_name, N) | |
064af421 BP |
251 | * |
252 | * Given a random distribution, the probability of at least one collision | |
6cc59853 | 253 | * in any set of N bits is approximately |
064af421 | 254 | * |
6cc59853 AW |
255 | * 1 - (prob of no collisions) |
256 | * **(combination of all possible comparisons) | |
257 | * == 1 - ((2**N - 1)/2**N)**C(X+1,2) | |
258 | * == p | |
064af421 | 259 | * |
6cc59853 | 260 | * There are (X-N) ways to pick N consecutive bits in a X-bit word, so if we |
064af421 | 261 | * assumed independence then the chance of having no collisions in any of |
6cc59853 AW |
262 | * those X-bit runs would be (1-p)**(X-N) == q. If this q is very small |
263 | * and we can also find a relatively small 'magic number' N such that there | |
264 | * is no collision in any comparison, then it means we have a pretty good | |
265 | * hash function. | |
064af421 | 266 | * |
6cc59853 AW |
267 | * The values of each parameters mentioned above for the tested hash |
268 | * functions are summarized as follow: | |
064af421 | 269 | * |
6cc59853 AW |
270 | * hash_function X N p q |
271 | * ------------- --- --- ------- ------- | |
064af421 | 272 | * |
6cc59853 AW |
273 | * hash_words_cb 32 11 0.22 0.0044 |
274 | * jhash_words_cb 32 11 0.22 0.0044 | |
275 | * hash_int_cb 32 12 0.12 0.0078 | |
276 | * hash_bytes128 128 19 0.0156 0.174 | |
064af421 | 277 | * |
064af421 | 278 | */ |
6cc59853 AW |
279 | check_word_hash(hash_words_cb, "hash_words", 11); |
280 | check_word_hash(jhash_words_cb, "jhash_words", 11); | |
c49d1dd1 | 281 | check_word_hash(hash_int_cb, "hash_int", 12); |
6cc59853 | 282 | check_hash_bytes128(hash_bytes128, "hash_bytes128", 19); |
468cdd91 | 283 | |
6cc59853 AW |
284 | /* |
285 | * The following tests check that all hashes computed with hash_function | |
286 | * with one 1-bit (or no 1-bits) set within Y X-bit word have different | |
287 | * values in their lowest N bits. | |
288 | * | |
289 | * test_function(hash_function, test_name, N) | |
afb50572 AW |
290 | * |
291 | * Given a random distribution, the probability of at least one collision | |
6cc59853 | 292 | * in any set of N bits is approximately |
afb50572 | 293 | * |
6cc59853 AW |
294 | * 1 - (prob of no collisions) |
295 | * **(combination of all possible comparisons) | |
296 | * == 1 - ((2**N - 1)/2**N)**C(Y*X+1,2) | |
297 | * == p | |
afb50572 | 298 | * |
6cc59853 AW |
299 | * If this p is not very small and we can also find a relatively small |
300 | * 'magic number' N such that there is no collision in any comparison, | |
301 | * then it means we have a pretty good hash function. | |
468cdd91 | 302 | * |
6cc59853 AW |
303 | * The values of each parameters mentioned above for the tested hash |
304 | * functions are summarized as follow: | |
468cdd91 | 305 | * |
6cc59853 AW |
306 | * hash_function Y X N p |
307 | * ------------- --- --- --- ------- | |
308 | * | |
309 | * hash_words 3 32 12 0.68 | |
310 | * jhash_words 3 32 12 0.68 | |
311 | * hash_bytes128 16 128 23 0.22 | |
468cdd91 | 312 | * |
468cdd91 | 313 | */ |
6cc59853 AW |
314 | check_3word_hash(hash_words, "hash_words"); |
315 | check_3word_hash(jhash_words, "jhash_words"); | |
468cdd91 | 316 | check_256byte_hash(hash_bytes128, "hash_bytes128", 23); |
064af421 | 317 | } |
eadd1644 AZ |
318 | |
319 | OVSTEST_REGISTER("test-hash", test_hash_main); |