Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2009, 2012, 2014, 2015 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 : :
17 : : #include <config.h>
18 : : #undef NDEBUG
19 : : #include "hash.h"
20 : : #include <assert.h>
21 : : #include <inttypes.h>
22 : : #include <stdio.h>
23 : : #include <stdlib.h>
24 : : #include <string.h>
25 : : #include "jhash.h"
26 : : #include "ovstest.h"
27 : :
28 : : static void
29 : 27936 : set_bit(uint32_t array[3], int bit)
30 : : {
31 [ + - ][ - + ]: 27936 : assert(bit >= 0 && bit <= 96);
32 : 27936 : memset(array, 0, sizeof(uint32_t) * 3);
33 [ + + ]: 27936 : if (bit < 96) {
34 : 27744 : array[bit / 32] = UINT32_C(1) << (bit % 32);
35 : : }
36 : 27936 : }
37 : :
38 : : /* When bit == n_bits, the function just 0 sets the 'values'. */
39 : : static void
40 : 2110788 : set_bit128(ovs_u128 *values, int bit, int n_bits)
41 : : {
42 [ + - ][ - + ]: 2110788 : assert(bit >= 0 && bit <= 2048);
43 : 2110788 : memset(values, 0, n_bits/8);
44 [ + + ]: 2110788 : if (bit < n_bits) {
45 : 2108608 : int b = bit % 128;
46 : :
47 [ + + ]: 2108608 : if (b < 64) {
48 : 1019488 : values[bit / 128].u64.lo = UINT64_C(1) << (b % 64);
49 : : } else {
50 : 1089120 : values[bit / 128].u64.hi = UINT64_C(1) << (b % 64);
51 : : }
52 : : }
53 : 2110788 : }
54 : :
55 : : static uint64_t
56 : 1799808 : get_range128(ovs_u128 *value, int ofs, uint64_t mask)
57 : : {
58 [ + + ]: 3599616 : return ((ofs < 64 ? (value->u64.lo >> ofs) : 0) & mask)
59 [ + + ]: 1799808 : | ((ofs <= 64 ? (value->u64.hi << (64 - ofs)) : (value->u64.hi >> (ofs - 64)) & mask));
60 : : }
61 : :
62 : : static uint32_t
63 : 1056 : hash_words_cb(uint32_t input)
64 : : {
65 : 1056 : return hash_words(&input, 1, 0);
66 : : }
67 : :
68 : : static uint32_t
69 : 1056 : jhash_words_cb(uint32_t input)
70 : : {
71 : 1056 : return jhash_words(&input, 1, 0);
72 : : }
73 : :
74 : : static uint32_t
75 : 1056 : hash_int_cb(uint32_t input)
76 : : {
77 : 1056 : return hash_int(input, 0);
78 : : }
79 : :
80 : : static void
81 : 3 : check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
82 : : int min_unique)
83 : : {
84 : : int i, j;
85 : :
86 [ + + ]: 102 : for (i = 0; i <= 32; i++) {
87 [ + + ]: 99 : uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
88 [ + + ]: 1683 : for (j = i + 1; j <= 32; j++) {
89 [ + + ]: 1584 : uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
90 : 1584 : uint32_t out1 = hash(in1);
91 : 1584 : uint32_t out2 = hash(in2);
92 : 1584 : const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
93 : : int ofs;
94 [ + + ]: 34320 : for (ofs = 0; ofs < 32 - min_unique; ofs++) {
95 : 32736 : uint32_t bits1 = (out1 >> ofs) & unique_mask;
96 : 32736 : uint32_t bits2 = (out2 >> ofs) & unique_mask;
97 [ - + ]: 32736 : if (bits1 == bits2) {
98 : 0 : printf("Partial collision for '%s':\n", name);
99 : 0 : printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
100 : 0 : printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
101 : 0 : printf("%d bits of output starting at bit %d "
102 : : "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
103 : : }
104 : : }
105 : : }
106 : : }
107 : 3 : }
108 : :
109 : : static void
110 : 2 : check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
111 : : const char *name)
112 : : {
113 : : int i, j;
114 : :
115 [ + + ]: 196 : for (i = 0; i <= 96; i++) {
116 [ + + ]: 9506 : for (j = i + 1; j <= 96; j++) {
117 : : uint32_t in0[3], in1[3], in2[3];
118 : : uint32_t out0,out1, out2;
119 : 9312 : const int min_unique = 12;
120 : 9312 : const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
121 : :
122 : 9312 : set_bit(in0, i);
123 : 9312 : set_bit(in1, i);
124 : 9312 : set_bit(in2, j);
125 : 9312 : out0 = hash(in0, 3, 0);
126 : 9312 : out1 = hash(in1, 3, 0);
127 : 9312 : out2 = hash(in2, 3, 0);
128 : :
129 [ - + ]: 9312 : if (out0 != out1) {
130 : 0 : printf("%s hash not the same for non-64 aligned data "
131 : : "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1);
132 : : }
133 [ - + ]: 9312 : if ((out1 & unique_mask) == (out2 & unique_mask)) {
134 : 0 : printf("%s has a partial collision:\n", name);
135 : 0 : printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
136 : 0 : printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
137 : 0 : printf("The low-order %d bits of output are both "
138 : : "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
139 : : }
140 : : }
141 : : }
142 : 2 : }
143 : :
144 : : static void
145 : 1 : check_hash_bytes128(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
146 : : const char *name, const int min_unique)
147 : : {
148 : 1 : const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
149 : 1 : const int n_bits = sizeof(ovs_u128) * 8;
150 : : int i, j;
151 : :
152 [ + + ]: 130 : for (i = 0; i <= n_bits; i++) {
153 : : OVS_PACKED(struct offset_ovs_u128 {
154 : : uint32_t a;
155 : : ovs_u128 b;
156 : : }) in0_data;
157 : : ovs_u128 *in0, in1;
158 : : ovs_u128 out0, out1;
159 : :
160 : 129 : in0 = &in0_data.b;
161 : 129 : set_bit128(in0, i, n_bits);
162 : 129 : set_bit128(&in1, i, n_bits);
163 : 129 : hash(in0, sizeof(ovs_u128), 0, &out0);
164 : 129 : hash(&in1, sizeof(ovs_u128), 0, &out1);
165 [ - + ]: 129 : if (!ovs_u128_equals(out0, out1)) {
166 : 0 : printf("%s hash not the same for non-64 aligned data "
167 : : "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
168 : : name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
169 : : }
170 : :
171 [ + + ]: 8385 : for (j = i + 1; j <= n_bits; j++) {
172 : : ovs_u128 in2;
173 : : ovs_u128 out2;
174 : : int ofs;
175 : :
176 : 8256 : set_bit128(&in2, j, n_bits);
177 : 8256 : hash(&in2, sizeof(ovs_u128), 0, &out2);
178 [ + + ]: 908160 : for (ofs = 0; ofs < 128 - min_unique; ofs++) {
179 : 899904 : uint64_t bits1 = get_range128(&out1, ofs, unique_mask);
180 : 899904 : uint64_t bits2 = get_range128(&out2, ofs, unique_mask);
181 : :
182 [ - + ]: 899904 : if (bits1 == bits2) {
183 : 0 : printf("%s has a partial collision:\n", name);
184 : 0 : printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
185 : : i, out1.u64.hi, out1.u64.lo);
186 : 0 : printf("hash(1 << %d) == %016"PRIx64"%016"PRIx64"\n",
187 : : j, out2.u64.hi, out2.u64.lo);
188 : 0 : printf("%d bits of output starting at bit %d "
189 : : "are both 0x%016"PRIx64"\n", min_unique, ofs, bits1);
190 : : }
191 : : }
192 : : }
193 : : }
194 : 1 : }
195 : :
196 : : static void
197 : 1 : check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
198 : : const char *name, const int min_unique)
199 : : {
200 : 1 : const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
201 : 1 : const int n_bits = sizeof(ovs_u128) * 8 * 16;
202 : : int i, j;
203 : :
204 [ + + ]: 2050 : for (i = 0; i <= n_bits; i++) {
205 : : OVS_PACKED(struct offset_ovs_u128 {
206 : : uint32_t a;
207 : : ovs_u128 b[16];
208 : : }) in0_data;
209 : : ovs_u128 *in0, in1[16];
210 : : ovs_u128 out0, out1;
211 : :
212 : 2049 : in0 = in0_data.b;
213 : 2049 : set_bit128(in0, i, n_bits);
214 : 2049 : set_bit128(in1, i, n_bits);
215 : 2049 : hash(in0, sizeof(ovs_u128) * 16, 0, &out0);
216 : 2049 : hash(in1, sizeof(ovs_u128) * 16, 0, &out1);
217 [ - + ]: 2049 : if (!ovs_u128_equals(out0, out1)) {
218 : 0 : 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 : :
223 [ + + ]: 2100225 : for (j = i + 1; j <= n_bits; j++) {
224 : : ovs_u128 in2[16];
225 : : ovs_u128 out2;
226 : :
227 : 2098176 : set_bit128(in2, j, n_bits);
228 : 2098176 : hash(in2, sizeof(ovs_u128) * 16, 0, &out2);
229 [ - + ]: 2098176 : if ((out1.u64.lo & unique_mask) == (out2.u64.lo & unique_mask)) {
230 : 0 : printf("%s has a partial collision:\n", name);
231 : 0 : printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", i,
232 : : out1.u64.hi, out1.u64.lo);
233 : 0 : printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", j,
234 : : out2.u64.hi, out2.u64.lo);
235 : 0 : printf("The low-order %d bits of output are both "
236 : 0 : "0x%"PRIx64"\n", min_unique, out1.u64.lo & unique_mask);
237 : : }
238 : : }
239 : : }
240 : 1 : }
241 : :
242 : : static void
243 : 1 : test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
244 : : {
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)
251 : : *
252 : : * Given a random distribution, the probability of at least one collision
253 : : * in any set of N bits is approximately
254 : : *
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
259 : : *
260 : : * There are (X-N) ways to pick N consecutive bits in a X-bit word, so if we
261 : : * assumed independence then the chance of having no collisions in any of
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.
266 : : *
267 : : * The values of each parameters mentioned above for the tested hash
268 : : * functions are summarized as follow:
269 : : *
270 : : * hash_function X N p q
271 : : * ------------- --- --- ------- -------
272 : : *
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
277 : : *
278 : : */
279 : 1 : check_word_hash(hash_words_cb, "hash_words", 11);
280 : 1 : check_word_hash(jhash_words_cb, "jhash_words", 11);
281 : 1 : check_word_hash(hash_int_cb, "hash_int", 12);
282 : 1 : check_hash_bytes128(hash_bytes128, "hash_bytes128", 19);
283 : :
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)
290 : : *
291 : : * Given a random distribution, the probability of at least one collision
292 : : * in any set of N bits is approximately
293 : : *
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
298 : : *
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.
302 : : *
303 : : * The values of each parameters mentioned above for the tested hash
304 : : * functions are summarized as follow:
305 : : *
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
312 : : *
313 : : */
314 : 1 : check_3word_hash(hash_words, "hash_words");
315 : 1 : check_3word_hash(jhash_words, "jhash_words");
316 : 1 : check_256byte_hash(hash_bytes128, "hash_bytes128", 23);
317 : 1 : }
318 : :
319 : 1176 : OVSTEST_REGISTER("test-hash", test_hash_main);
|
