1 | /// Taken from SMHasher. |
2 | |
3 | //----------------------------------------------------------------------------- |
4 | // Flipping a single bit of a key should cause an "avalanche" of changes in |
5 | // the hash function's output. Ideally, each output bits should flip 50% of |
6 | // the time - if the probability of an output bit flipping is not 50%, that bit |
7 | // is "biased". Too much bias means that patterns applied to the input will |
8 | // cause "echoes" of the patterns in the output, which in turn can cause the |
9 | // hash function to fail to create an even, random distribution of hash values. |
10 | |
11 | |
12 | #pragma once |
13 | |
14 | #include "Random.h" |
15 | |
16 | #include <vector> |
17 | #include <math.h> |
18 | #include <stdio.h> |
19 | |
20 | // Avalanche fails if a bit is biased by more than 1% |
21 | |
22 | #define AVALANCHE_FAIL 0.01 |
23 | |
24 | double maxBias(std::vector<int> & counts, int reps); |
25 | |
26 | typedef void (*pfHash)(const void * blob, const int len, const uint32_t seed, void * out); |
27 | |
28 | |
29 | inline uint32_t getbit(const void * block, int len, uint32_t bit) |
30 | { |
31 | uint8_t * b = reinterpret_cast<uint8_t *>(const_cast<void *>(block)); |
32 | |
33 | int byte = bit >> 3; |
34 | bit = bit & 0x7; |
35 | |
36 | if (byte < len) |
37 | return (b[byte] >> bit) & 1; |
38 | |
39 | return 0; |
40 | } |
41 | |
42 | template <typename T> |
43 | inline uint32_t getbit(T & blob, uint32_t bit) |
44 | { |
45 | return getbit(&blob, sizeof(blob), bit); |
46 | } |
47 | |
48 | inline void flipbit(void * block, int len, uint32_t bit) |
49 | { |
50 | uint8_t * b = reinterpret_cast<uint8_t *>(block); |
51 | |
52 | int byte = bit >> 3; |
53 | bit = bit & 0x7; |
54 | |
55 | if (byte < len) |
56 | b[byte] ^= (1 << bit); |
57 | } |
58 | |
59 | template <typename T> |
60 | inline void flipbit(T & blob, uint32_t bit) |
61 | { |
62 | flipbit(&blob, sizeof(blob), bit); |
63 | } |
64 | |
65 | //----------------------------------------------------------------------------- |
66 | |
67 | template <typename keytype, typename hashtype> |
68 | void calcBias(pfHash hash, std::vector<int> & counts, int reps, Rand & r) |
69 | { |
70 | const int keybytes = sizeof(keytype); |
71 | const int hashbytes = sizeof(hashtype); |
72 | |
73 | const int keybits = keybytes * 8; |
74 | const int hashbits = hashbytes * 8; |
75 | |
76 | keytype K; |
77 | hashtype A, B; |
78 | |
79 | for (int irep = 0; irep < reps; irep++) |
80 | { |
81 | if (irep % (reps / 10) == 0) |
82 | printf("." ); |
83 | |
84 | r.rand_p(&K, keybytes); |
85 | |
86 | hash(&K, keybytes, 0, &A); |
87 | |
88 | int * cursor = counts.data(); |
89 | |
90 | for (int iBit = 0; iBit < keybits; iBit++) |
91 | { |
92 | flipbit(&K, keybytes, iBit); |
93 | hash(&K, keybytes, 0, &B); |
94 | flipbit(&K, keybytes, iBit); |
95 | |
96 | for (int iOut = 0; iOut < hashbits; iOut++) |
97 | { |
98 | int bitA = getbit(&A, hashbytes, iOut); |
99 | int bitB = getbit(&B, hashbytes, iOut); |
100 | |
101 | (*cursor++) += (bitA ^ bitB); |
102 | } |
103 | } |
104 | } |
105 | } |
106 | |
107 | //----------------------------------------------------------------------------- |
108 | |
109 | template <typename keytype, typename hashtype> |
110 | bool AvalancheTest(pfHash hash, const int reps) |
111 | { |
112 | Rand r(48273); |
113 | |
114 | const int keybytes = sizeof(keytype); |
115 | const int hashbytes = sizeof(hashtype); |
116 | |
117 | const int keybits = keybytes * 8; |
118 | const int hashbits = hashbytes * 8; |
119 | |
120 | printf("Testing %3d-bit keys -> %3d-bit hashes, %8d reps" , keybits, hashbits, reps); |
121 | |
122 | //---------- |
123 | |
124 | std::vector<int> bins(keybits * hashbits, 0); |
125 | |
126 | calcBias<keytype, hashtype>(hash, bins, reps, r); |
127 | |
128 | //---------- |
129 | |
130 | bool result = true; |
131 | |
132 | double b = maxBias(bins, reps); |
133 | |
134 | printf(" worst bias is %f%%" , b * 100.0); |
135 | |
136 | if (b > AVALANCHE_FAIL) |
137 | { |
138 | printf(" !!!!! " ); |
139 | result = false; |
140 | } |
141 | |
142 | printf("\n" ); |
143 | |
144 | return result; |
145 | } |
146 | |
147 | |
148 | //----------------------------------------------------------------------------- |
149 | // BIC test variant - store all intermediate data in a table, draw diagram |
150 | // afterwards (much faster) |
151 | |
152 | template <typename keytype, typename hashtype> |
153 | void BicTest3(pfHash hash, const int reps, bool verbose = true) |
154 | { |
155 | const int keybytes = sizeof(keytype); |
156 | const int keybits = keybytes * 8; |
157 | const int hashbytes = sizeof(hashtype); |
158 | const int hashbits = hashbytes * 8; |
159 | const int pagesize = hashbits * hashbits * 4; |
160 | |
161 | Rand r(11938); |
162 | |
163 | double maxBias = 0; |
164 | int maxK = 0; |
165 | int maxA = 0; |
166 | int maxB = 0; |
167 | |
168 | keytype key; |
169 | hashtype h1, h2; |
170 | |
171 | std::vector<int> bins(keybits * pagesize, 0); |
172 | |
173 | for (int keybit = 0; keybit < keybits; keybit++) |
174 | { |
175 | if (keybit % (keybits / 10) == 0) |
176 | printf("." ); |
177 | |
178 | int * page = &bins[keybit * pagesize]; |
179 | |
180 | for (int irep = 0; irep < reps; irep++) |
181 | { |
182 | r.rand_p(&key, keybytes); |
183 | hash(&key, keybytes, 0, &h1); |
184 | flipbit(key, keybit); |
185 | hash(&key, keybytes, 0, &h2); |
186 | |
187 | hashtype d = h1 ^ h2; |
188 | |
189 | for (int out1 = 0; out1 < hashbits - 1; out1++) |
190 | for (int out2 = out1 + 1; out2 < hashbits; out2++) |
191 | { |
192 | int * b = &page[(out1 * hashbits + out2) * 4]; |
193 | |
194 | uint32_t x = getbit(d, out1) | (getbit(d, out2) << 1); |
195 | |
196 | b[x]++; |
197 | } |
198 | } |
199 | } |
200 | |
201 | printf("\n" ); |
202 | |
203 | for (int out1 = 0; out1 < hashbits - 1; out1++) |
204 | { |
205 | for (int out2 = out1 + 1; out2 < hashbits; out2++) |
206 | { |
207 | if (verbose) |
208 | printf("(%3d,%3d) - " , out1, out2); |
209 | |
210 | for (int keybit = 0; keybit < keybits; keybit++) |
211 | { |
212 | int * page = &bins[keybit * pagesize]; |
213 | int * bins_in_page = &page[(out1 * hashbits + out2) * 4]; |
214 | |
215 | double bias = 0; |
216 | |
217 | for (int b = 0; b < 4; b++) |
218 | { |
219 | double b2 = static_cast<double>(bins_in_page[b]) / static_cast<double>(reps / 2); |
220 | b2 = fabs(b2 * 2 - 1); |
221 | |
222 | if (b2 > bias) |
223 | bias = b2; |
224 | } |
225 | |
226 | if (bias > maxBias) |
227 | { |
228 | maxBias = bias; |
229 | maxK = keybit; |
230 | maxA = out1; |
231 | maxB = out2; |
232 | } |
233 | |
234 | if (verbose) |
235 | { |
236 | if (bias < 0.01) |
237 | printf("." ); |
238 | else if (bias < 0.05) |
239 | printf("o" ); |
240 | else if (bias < 0.33) |
241 | printf("O" ); |
242 | else |
243 | printf("X" ); |
244 | } |
245 | } |
246 | |
247 | // Finished keybit |
248 | |
249 | if (verbose) |
250 | printf("\n" ); |
251 | } |
252 | |
253 | if (verbose) |
254 | { |
255 | for (int i = 0; i < keybits + 12; i++) |
256 | printf("-" ); |
257 | printf("\n" ); |
258 | } |
259 | } |
260 | |
261 | printf("Max bias %f - (%3d : %3d,%3d)\n" , maxBias, maxK, maxA, maxB); |
262 | } |
263 | |
264 | //----------------------------------------------------------------------------- |
265 | |