2 * Copyright (c) 2009 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.
28 set_bit(uint32_t array[3], int bit)
30 assert(bit >= 0 && bit <= 96);
31 memset(array, 0, sizeof(uint32_t) * 3);
33 array[bit / 32] = UINT32_C(1) << (bit % 32);
38 hash_words_cb(uint32_t input)
40 return hash_words(&input, 1, 0);
44 hash_int_cb(uint32_t input)
46 return hash_int(input, 0);
50 check_word_hash(uint32_t (*hash)(uint32_t), const char *name,
55 for (i = 0; i <= 32; i++) {
56 uint32_t in1 = i < 32 ? UINT32_C(1) << i : 0;
57 for (j = i + 1; j <= 32; j++) {
58 uint32_t in2 = j < 32 ? UINT32_C(1) << j : 0;
59 uint32_t out1 = hash(in1);
60 uint32_t out2 = hash(in2);
61 const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
63 for (ofs = 0; ofs < 32 - min_unique; ofs++) {
64 uint32_t bits1 = (out1 >> ofs) & unique_mask;
65 uint32_t bits2 = (out2 >> ofs) & unique_mask;
67 printf("Partial collision for '%s':\n", name);
68 printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in1, out1);
69 printf("%s(%08"PRIx32") = %08"PRIx32"\n", name, in2, out2);
70 printf("%d bits of output starting at bit %d "
71 "are both 0x%"PRIx32"\n", min_unique, ofs, bits1);
84 /* Check that all hashes computed with hash_words with one 1-bit (or no
85 * 1-bits) set within a single 32-bit word have different values in all
86 * 11-bit consecutive runs.
88 * Given a random distribution, the probability of at least one collision
89 * in any set of 11 bits is approximately
91 * 1 - ((2**11 - 1)/2**11)**C(33,2)
92 * == 1 - (2047/2048)**528
95 * There are 21 ways to pick 11 consecutive bits in a 32-bit word, so if we
96 * assumed independence then the chance of having no collisions in any of
97 * those 11-bit runs would be (1-0.22)**21 =~ .0044. Obviously
98 * independence must be a bad assumption :-)
100 check_word_hash(hash_words_cb, "hash_words", 11);
102 /* Check that all hash functions of with one 1-bit (or no 1-bits) set
103 * within three 32-bit words have different values in their lowest 12
106 * Given a random distribution, the probability of at least one collision
107 * in 12 bits is approximately
109 * 1 - ((2**12 - 1)/2**12)**C(97,2)
110 * == 1 - (4095/4096)**4656
113 * so we are doing pretty well to not have any collisions in 12 bits.
115 for (i = 0; i <= 96; i++) {
116 for (j = i + 1; j <= 96; j++) {
117 uint32_t in1[3], in2[3];
119 const int min_unique = 12;
120 const uint32_t unique_mask = (UINT32_C(1) << min_unique) - 1;
124 out1 = hash_words(in1, 3, 0);
125 out2 = hash_words(in2, 3, 0);
126 if ((out1 & unique_mask) == (out2 & unique_mask)) {
127 printf("Partial collision:\n");
128 printf("hash(1 << %d) == %08"PRIx32"\n", i, out1);
129 printf("hash(1 << %d) == %08"PRIx32"\n", j, out2);
130 printf("The low-order %d bits of output are both "
131 "0x%"PRIx32"\n", min_unique, out1 & unique_mask);
137 /* Check that all hashes computed with hash_int with one 1-bit (or no
138 * 1-bits) set within a single 32-bit word have different values in all
139 * 14-bit consecutive runs.
141 * Given a random distribution, the probability of at least one collision
142 * in any set of 14 bits is approximately
144 * 1 - ((2**14 - 1)/2**14)**C(33,2)
145 * == 1 - (16,383/16,834)**528
148 * There are 18 ways to pick 14 consecutive bits in a 32-bit word, so if we
149 * assumed independence then the chance of having no collisions in any of
150 * those 14-bit runs would be (1-0.03)**18 =~ 0.56. This seems reasonable.
152 check_word_hash(hash_int_cb, "hash_int", 14);