2 * Copyright (c) 2009, 2012, 2014 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);
39 set_bit128(ovs_u128 array[16], int bit)
41 assert(bit >= 0 && bit <= 2048);
42 memset(array, 0, sizeof(ovs_u128) * 16);
47 array[bit / 128].u64.lo = UINT64_C(1) << (b % 64);
49 array[bit / 128].u64.hi = UINT64_C(1) << (b % 64);
55 hash_words_cb(uint32_t input)
57 return hash_words(&input, 1, 0);
61 jhash_words_cb(uint32_t input)
63 return jhash_words(&input, 1, 0);
67 hash_int_cb(uint32_t input)
69 return hash_int(input, 0);
73 hash_bytes128_cb(uint32_t input)
77 hash_bytes128(&input, sizeof input, 0, &hash);
82 check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
87 for (i = 0; i <= 32; i++) {
88 uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
89 for (j = i + 1; j <= 32; j++) {
90 uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
91 uint32_t out1 = hash(in1);
92 uint32_t out2 = hash(in2);
93 const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
95 for (ofs = 0; ofs < 32 - min_unique; ofs++) {
96 uint32_t bits1 = (out1 >> ofs) & unique_mask;
97 uint32_t bits2 = (out2 >> ofs) & unique_mask;
99 printf("Partial collision for '%s':\n", name);
100 printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
101 printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
102 printf("%d bits of output starting at bit %d "
103 "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
112 check_3word_hash(uint32_t (*hash)(const uint32_t[], size_t, uint32_t),
117 for (i = 0; i <= 96; i++) {
118 for (j = i + 1; j <= 96; j++) {
119 uint32_t in0[3], in1[3], in2[3];
120 uint32_t out0,out1, out2;
121 const int min_unique = 12;
122 const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
127 out0 = hash(in0, 3, 0);
128 out1 = hash(in1, 3, 0);
129 out2 = hash(in2, 3, 0);
132 printf("%s hash not the same for non-64 aligned data "
133 "%08"PRIx32" != %08"PRIx32"\n", name, out0, out1);
135 if ((out1 & unique_mask) == (out2 & unique_mask)) {
136 printf("%s has a partial collision:\n", name);
137 printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
138 printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
139 printf("The low-order %d bits of output are both "
140 "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
147 check_256byte_hash(void (*hash)(const void *, size_t, uint32_t, ovs_u128 *),
148 const char *name, const int min_unique)
150 const uint64_t unique_mask = (UINT64_C(1) << min_unique) - 1;
151 const int n_bits = 256 * 8;
154 for (i = 0; i < n_bits; i++) {
155 for (j = i + 1; j < n_bits; j++) {
156 OVS_PACKED(struct offset_ovs_u128 {
160 ovs_u128 *in0, in1[16], in2[16];
161 ovs_u128 out0, out1, out2;
167 hash(in0, sizeof(ovs_u128) * 16, 0, &out0);
168 hash(in1, sizeof(ovs_u128) * 16, 0, &out1);
169 hash(in2, sizeof(ovs_u128) * 16, 0, &out2);
170 if (!ovs_u128_equal(&out0, &out1)) {
171 printf("%s hash not the same for non-64 aligned data "
172 "%016"PRIx64"%016"PRIx64" != %016"PRIx64"%016"PRIx64"\n",
173 name, out0.u64.lo, out0.u64.hi, out1.u64.lo, out1.u64.hi);
175 if ((out1.u64.lo & unique_mask) == (out2.u64.lo & unique_mask)) {
176 printf("%s has a partial collision:\n", name);
177 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", i,
178 out1.u64.hi, out1.u64.lo);
179 printf("hash(1 << %4d) == %016"PRIx64"%016"PRIx64"\n", j,
180 out2.u64.hi, out2.u64.lo);
181 printf("The low-order %d bits of output are both "
182 "0x%"PRIx64"\n", min_unique, out1.u64.lo & unique_mask);
189 test_hash_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
191 /* Check that all hashes computed with hash_words with one 1-bit (or no
192 * 1-bits) set within a single 32-bit word have different values in all
193 * 11-bit consecutive runs.
195 * Given a random distribution, the probability of at least one collision
196 * in any set of 11 bits is approximately
198 * 1 - (proportion of same_bits)
199 * **(binomial_coefficient(n_bits_in_data + 1, 2))
200 * == 1 - ((2**11 - 1)/2**11)**C(33,2)
201 * == 1 - (2047/2048)**528
204 * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
205 * assumed independence then the chance of having no collisions in any of
206 * those 11-bit runs would be (1-0.22)**21 =~ .0044. Obviously
207 * independence must be a bad assumption :-)
209 check_word_hash(hash_words_cb, "hash_words", 11);
210 check_word_hash(jhash_words_cb, "jhash_words", 11);
212 /* Check that all hash functions of with one 1-bit (or no 1-bits) set
213 * within three 32-bit words have different values in their lowest 12
216 * Given a random distribution, the probability of at least one collision
217 * in 12 bits is approximately
219 * 1 - ((2**12 - 1)/2**12)**C(97,2)
220 * == 1 - (4095/4096)**4656
223 * so we are doing pretty well to not have any collisions in 12 bits.
225 check_3word_hash(hash_words, "hash_words");
226 check_3word_hash(jhash_words, "jhash_words");
228 /* Check that all hashes computed with hash_int with one 1-bit (or no
229 * 1-bits) set within a single 32-bit word have different values in all
230 * 12-bit consecutive runs.
232 * Given a random distribution, the probability of at least one collision
233 * in any set of 12 bits is approximately
235 * 1 - ((2**12 - 1)/2**12)**C(33,2)
236 * == 1 - (4,095/4,096)**528
239 * There are 20 ways to pick 12 consecutive bits in a 32-bit word, so if we
240 * assumed independence then the chance of having no collisions in any of
241 * those 12-bit runs would be (1-0.12)**20 =~ 0.078. This refutes our
242 * assumption of independence, which makes it seem like a good hash
245 check_word_hash(hash_int_cb, "hash_int", 12);
246 check_word_hash(hash_bytes128_cb, "hash_bytes128", 12);
248 /* Check that all hashes computed with hash_bytes128 with 1-bit (or no
249 * 1-bits) set within 16 128-bit words have different values in their
252 * Given a random distribution, the probability of at least one collision
253 * in any set of 23 bits is approximately
255 * 1 - ((2**23 - 1)/2**23)**C(2049,2)
256 * == 1 - (8,388,607/8,388,608)**2,098,176
259 * so we are doing pretty well to not have any collisions in 23 bits.
261 check_256byte_hash(hash_bytes128, "hash_bytes128", 23);
264 OVSTEST_REGISTER("test-hash", test_hash_main);