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
24double maxBias(std::vector<int> & counts, int reps);
25
26typedef void (*pfHash)(const void * blob, const int len, const uint32_t seed, void * out);
27
28
29inline 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
42template <typename T>
43inline uint32_t getbit(T & blob, uint32_t bit)
44{
45 return getbit(&blob, sizeof(blob), bit);
46}
47
48inline 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
59template <typename T>
60inline void flipbit(T & blob, uint32_t bit)
61{
62 flipbit(&blob, sizeof(blob), bit);
63}
64
65//-----------------------------------------------------------------------------
66
67template <typename keytype, typename hashtype>
68void 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
109template <typename keytype, typename hashtype>
110bool 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
152template <typename keytype, typename hashtype>
153void 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