]>
git.proxmox.com Git - ovs.git/blob - tests/test-hash.c
2 * Copyright (c) 2009, 2012, 2014, 2015 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
29 set_bit(uint32_t array
[3], int bit
)
31 assert(bit
>= 0 && bit
<= 96);
32 memset(array
, 0, sizeof(uint32_t) * 3);
34 array
[bit
/ 32] = UINT32_C(1) << (bit
% 32);
38 /* When bit == n_bits, the function just 0 sets the 'values'. */
40 set_bit128(ovs_u128
*values
, int bit
, int n_bits
)
42 assert(bit
>= 0 && bit
<= 2048);
43 memset(values
, 0, n_bits
/8);
48 values
[bit
/ 128].u64
.lo
= UINT64_C(1) << (b
% 64);
50 values
[bit
/ 128].u64
.hi
= UINT64_C(1) << (b
% 64);
56 get_range128(ovs_u128
*value
, int ofs
, uint64_t mask
)
58 return ((ofs
< 64 ? (value
->u64
.lo
>> ofs
) : 0) & mask
)
59 | ((ofs
<= 64 ? (value
->u64
.hi
<< (64 - ofs
)) : (value
->u64
.hi
>> (ofs
- 64)) & mask
));
63 hash_words_cb(uint32_t input
)
65 return hash_words(&input
, 1, 0);
69 jhash_words_cb(uint32_t input
)
71 return jhash_words(&input
, 1, 0);
75 hash_int_cb(uint32_t input
)
77 return hash_int(input
, 0);
81 check_word_hash(uint32_t (*hash
)(uint32_t), const char *name
,
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;
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
;
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
);
110 check_3word_hash(uint32_t (*hash
)(const uint32_t[], size_t, uint32_t),
115 for (i
= 0; i
<= 96; i
++) {
116 for (j
= i
+ 1; j
<= 96; j
++) {
117 uint32_t in0
[3], in1
[3], in2
[3];
118 uint32_t out0
,out1
, out2
;
119 const int min_unique
= 12;
120 const uint32_t unique_mask
= (UINT32_C(1) << min_unique
) - 1;
125 out0
= hash(in0
, 3, 0);
126 out1
= hash(in1
, 3, 0);
127 out2
= hash(in2
, 3, 0);
130 printf("%s hash not the same for non-64 aligned data "
131 "%08"PRIx32
" != %08"PRIx32
"\n", name
, out0
, out1
);
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
);
145 check_hash_bytes128(void (*hash
)(const void *, size_t, uint32_t, ovs_u128
*),
146 const char *name
, const int min_unique
)
148 const uint64_t unique_mask
= (UINT64_C(1) << min_unique
) - 1;
149 const int n_bits
= sizeof(ovs_u128
) * 8;
152 for (i
= 0; i
<= n_bits
; i
++) {
153 OVS_PACKED(struct offset_ovs_u128
{
161 set_bit128(in0
, i
, n_bits
);
162 set_bit128(&in1
, i
, n_bits
);
163 hash(in0
, sizeof(ovs_u128
), 0, &out0
);
164 hash(&in1
, sizeof(ovs_u128
), 0, &out1
);
165 if (!ovs_u128_equal(&out0
, &out1
)) {
166 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
);
171 for (j
= i
+ 1; j
<= n_bits
; j
++) {
176 set_bit128(&in2
, j
, n_bits
);
177 hash(&in2
, sizeof(ovs_u128
), 0, &out2
);
178 for (ofs
= 0; ofs
< 128 - min_unique
; ofs
++) {
179 uint64_t bits1
= get_range128(&out1
, ofs
, unique_mask
);
180 uint64_t bits2
= get_range128(&out2
, ofs
, unique_mask
);
182 if (bits1
== bits2
) {
183 printf("%s has a partial collision:\n", name
);
184 printf("hash(1 << %d) == %016"PRIx64
"%016"PRIx64
"\n",
185 i
, out1
.u64
.hi
, out1
.u64
.lo
);
186 printf("hash(1 << %d) == %016"PRIx64
"%016"PRIx64
"\n",
187 j
, out2
.u64
.hi
, out2
.u64
.lo
);
188 printf("%d bits of output starting at bit %d "
189 "are both 0x%016"PRIx64
"\n", min_unique
, ofs
, bits1
);
197 check_256byte_hash(void (*hash
)(const void *, size_t, uint32_t, ovs_u128
*),
198 const char *name
, const int min_unique
)
200 const uint64_t unique_mask
= (UINT64_C(1) << min_unique
) - 1;
201 const int n_bits
= sizeof(ovs_u128
) * 8 * 16;
204 for (i
= 0; i
<= n_bits
; i
++) {
205 OVS_PACKED(struct offset_ovs_u128
{
209 ovs_u128
*in0
, in1
[16];
213 set_bit128(in0
, i
, n_bits
);
214 set_bit128(in1
, i
, n_bits
);
215 hash(in0
, sizeof(ovs_u128
) * 16, 0, &out0
);
216 hash(in1
, sizeof(ovs_u128
) * 16, 0, &out1
);
217 if (!ovs_u128_equal(&out0
, &out1
)) {
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
);
223 for (j
= i
+ 1; j
<= n_bits
; j
++) {
227 set_bit128(in2
, j
, n_bits
);
228 hash(in2
, sizeof(ovs_u128
) * 16, 0, &out2
);
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
);
243 test_hash_main(int argc OVS_UNUSED
, char *argv
[] OVS_UNUSED
)
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.
250 * test_function(hash_function, test_name, N)
252 * Given a random distribution, the probability of at least one collision
253 * in any set of N bits is approximately
255 * 1 - (prob of no collisions)
256 * **(combination of all possible comparisons)
257 * == 1 - ((2**N - 1)/2**N)**C(X+1,2)
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
267 * The values of each parameters mentioned above for the tested hash
268 * functions are summarized as follow:
270 * hash_function X N p q
271 * ------------- --- --- ------- -------
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
279 check_word_hash(hash_words_cb
, "hash_words", 11);
280 check_word_hash(jhash_words_cb
, "jhash_words", 11);
281 check_word_hash(hash_int_cb
, "hash_int", 12);
282 check_hash_bytes128(hash_bytes128
, "hash_bytes128", 19);
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.
289 * test_function(hash_function, test_name, N)
291 * Given a random distribution, the probability of at least one collision
292 * in any set of N bits is approximately
294 * 1 - (prob of no collisions)
295 * **(combination of all possible comparisons)
296 * == 1 - ((2**N - 1)/2**N)**C(Y*X+1,2)
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.
303 * The values of each parameters mentioned above for the tested hash
304 * functions are summarized as follow:
306 * hash_function Y X N p
307 * ------------- --- --- --- -------
309 * hash_words 3 32 12 0.68
310 * jhash_words 3 32 12 0.68
311 * hash_bytes128 16 128 23 0.22
314 check_3word_hash(hash_words
, "hash_words");
315 check_3word_hash(jhash_words
, "jhash_words");
316 check_256byte_hash(hash_bytes128
, "hash_bytes128", 23);
319 OVSTEST_REGISTER("test-hash", test_hash_main
);