1
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <assert.h>
5
6 typedef signed int Int;
7 typedef unsigned int UInt;
8 typedef unsigned long long int Addr64;
9 typedef unsigned char UChar;
10 typedef unsigned long int UWord;
11
ROL32(UInt x,UInt n)12 static inline UInt ROL32 ( UInt x, UInt n ) {
13 assert(n != 0);
14 n &= 31;
15 x = (x << n) | (x >> (32-n));
16 return x;
17 }
18
19 //////////////////////////////////////////////////////////
20
21 typedef
22 struct {
23 Addr64 ga;
24 Int nbytes;
25 UChar* bytes;
26 UChar* actual;
27 }
28 GuestBytes;
29
read_one(FILE * f)30 GuestBytes* read_one ( FILE* f )
31 {
32 Int r;
33 UInt i;
34 UInt esum, csum;
35
36 GuestBytes* gb = malloc(sizeof(GuestBytes));
37 assert(gb);
38
39 if (feof(f)) return NULL;
40 assert(!ferror(f));
41
42 r= fscanf(f, "GuestBytes %llx %d ", &gb->ga, &gb->nbytes);
43 if (0) printf("r = %d\n", r);
44 assert(r == 2);
45
46 assert(gb->ga != 0);
47 assert(gb->nbytes > 0);
48 assert(gb->nbytes < 5000); // let's say
49
50 Int nToAlloc = gb->nbytes + (gb->ga & 3);
51
52 gb->bytes = malloc( gb->nbytes + nToAlloc);
53 gb->actual = gb->bytes + (gb->ga & 3);
54 assert(gb->bytes);
55
56 csum = 0;
57 for (i = 0; i < gb->nbytes; i++) {
58 UInt b;
59 r= fscanf(f, "%02x ", &b);
60 assert(r == 1);
61 gb->actual[i] = b;
62 csum = (csum << 1) ^ b;
63 }
64
65 r= fscanf(f, " %08x\n", &esum);
66 assert(r == 1);
67
68 assert(esum == csum);
69
70 return gb;
71 }
72
73 //////////////////////////////////////////////////////////
74
apply_to_all(FILE * f,void (* fn)(GuestBytes *,void *),void * opaque)75 void apply_to_all ( FILE* f,
76 void(*fn)( GuestBytes*, void* ),
77 void* opaque )
78 {
79 while (!feof(f)) {
80 GuestBytes* gb = read_one(f);
81 if (0) printf("got %llu %d\n", gb->ga, gb->nbytes);
82 fn( gb, opaque );
83 free(gb->bytes);
84 free(gb);
85 }
86 }
87
88 //////////////////////////////////////////////////////////
89
hash_const_zero(GuestBytes * gb)90 UInt hash_const_zero ( GuestBytes* gb ) {
91 return 0;
92 }
93
hash_sum(GuestBytes * gb)94 UInt hash_sum ( GuestBytes* gb ) {
95 UInt i, sum = 0;
96 for (i = 0; i < gb->nbytes; i++)
97 sum += (UInt)gb->actual[i];
98 return sum;
99 }
100
hash_rol(GuestBytes * gb)101 UInt hash_rol ( GuestBytes* gb ) {
102 UInt i, sum = 0;
103 for (i = 0; i < gb->nbytes; i++) {
104 sum ^= (UInt)gb->actual[i];
105 sum = ROL32(sum,7);
106 }
107 return sum;
108 }
109
cand0(GuestBytes * gb)110 static UInt cand0 ( GuestBytes* gb )
111 {
112 UWord addr = (UWord)gb->actual;
113 UWord len = gb->nbytes;
114 UInt sum = 0;
115 /* pull up to 4-alignment */
116 while ((addr & 3) != 0 && len >= 1) {
117 UChar* p = (UChar*)addr;
118 sum = (sum << 8) | (UInt)p[0];
119 addr++;
120 len--;
121 }
122 /* vectorised + unrolled */
123 while (len >= 16) {
124 UInt* p = (UInt*)addr;
125 sum = ROL32(sum ^ p[0], 13);
126 sum = ROL32(sum ^ p[1], 13);
127 sum = ROL32(sum ^ p[2], 13);
128 sum = ROL32(sum ^ p[3], 13);
129 addr += 16;
130 len -= 16;
131 }
132 /* vectorised fixup */
133 while (len >= 4) {
134 UInt* p = (UInt*)addr;
135 sum = ROL32(sum ^ p[0], 13);
136 addr += 4;
137 len -= 4;
138 }
139 /* scalar fixup */
140 while (len >= 1) {
141 UChar* p = (UChar*)addr;
142 sum = ROL32(sum ^ (UInt)p[0], 19);
143 addr++;
144 len--;
145 }
146 return sum;
147 }
148
cand1(GuestBytes * gb)149 static UInt cand1 ( GuestBytes* gb )
150 {
151 UWord addr = (UWord)gb->actual;
152 UWord len = gb->nbytes;
153 UInt sum1 = 0, sum2 = 0;
154 /* pull up to 4-alignment */
155 while ((addr & 3) != 0 && len >= 1) {
156 UChar* p = (UChar*)addr;
157 sum1 = (sum1 << 8) | (UInt)p[0];
158 addr++;
159 len--;
160 }
161 /* vectorised + unrolled */
162 while (len >= 16) {
163 UInt* p = (UInt*)addr;
164 UInt w;
165 w = p[0]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
166 w = p[1]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
167 w = p[2]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
168 w = p[3]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
169 addr += 16;
170 len -= 16;
171 sum1 ^= sum2;
172 }
173 /* vectorised fixup */
174 while (len >= 4) {
175 UInt* p = (UInt*)addr;
176 UInt w = p[0];
177 sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
178 addr += 4;
179 len -= 4;
180 sum1 ^= sum2;
181 }
182 /* scalar fixup */
183 while (len >= 1) {
184 UChar* p = (UChar*)addr;
185 UInt w = (UInt)p[0];
186 sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
187 addr++;
188 len--;
189 }
190 return sum1 + sum2;
191 }
192
adler32(GuestBytes * gb)193 static UInt adler32 ( GuestBytes* gb )
194 {
195 UWord addr = (UWord)gb->actual;
196 UWord len = gb->nbytes;
197 UInt s1 = 1;
198 UInt s2 = 0;
199 UChar* buf = (UChar*)addr;
200 while (len >= 4) {
201 s1 += buf[0];
202 s2 += s1;
203 s1 += buf[1];
204 s2 += s1;
205 s1 += buf[2];
206 s2 += s1;
207 s1 += buf[3];
208 s2 += s1;
209 buf += 4;
210 len -= 4;
211 }
212 while (len > 0) {
213 s1 += buf[0];
214 s2 += s1;
215 len--;
216 buf++;
217 }
218 return (s2 << 16) + s1;
219 }
220
221
222
223
224 //////////////////////////////////////////////////////////
225
226 UInt (*theFn)(GuestBytes*) =
227 //hash_const_zero;
228 //hash_sum;
229 //hash_rol;
230 //cand0;
231 cand1;
232 //adler32;
233
cmp_UInt_ps(UInt * p1,UInt * p2)234 Int cmp_UInt_ps ( UInt* p1, UInt* p2 ) {
235 if (*p1 < *p2) return -1;
236 if (*p1 > *p2) return 1;
237 return 0;
238 }
239
nSetBits(UInt w)240 Int nSetBits ( UInt w )
241 {
242 Int i, j;
243 j = 0;
244 for (i = 0; i < 32; i++)
245 if (w & (1<<i))
246 j++;
247 return j;
248 }
249
250 Int toc_nblocks = 0;
251 Int toc_nblocks_with_zero = 0;
252 double toc_sum_of_avgs = 0.0;
253
invertBit(UChar * b,UInt ix,UInt bix)254 void invertBit ( UChar* b, UInt ix, UInt bix ) {
255 b[ix] ^= (1 << bix);
256 }
257
try_onebit_changes(GuestBytes * gb,void * opaque)258 void try_onebit_changes( GuestBytes* gb, void* opaque )
259 {
260 toc_nblocks++;
261 /* collect up the hash values for all one bit changes of the key,
262 and also that for the unmodified key. Then compute the number
263 of changed bits for all of them. */
264 UInt hashIx = 0;
265 UInt nHashes = 8 * gb->nbytes;
266 UInt* hashes = malloc( nHashes * sizeof(UInt) );
267
268 UInt byteIx, bitIx;
269 UInt hInit, hFinal, hRunning;
270 Int dist, totDist = 0, nNoDist = 0;
271 assert(hashes);
272 hInit = theFn( gb );
273 for (byteIx = 0; byteIx < gb->nbytes; byteIx++) {
274 for (bitIx = 0; bitIx < 8; bitIx++) {
275
276 invertBit(gb->actual, byteIx, bitIx);
277 //invertBit(gb->actual, byteIx, bitIx ^ 4);
278
279 hRunning = theFn( gb );
280
281 dist = nSetBits(hRunning ^ hInit);
282 totDist += dist;
283 if (dist == 0) nNoDist++;
284
285 hashes[hashIx++] = hRunning;
286
287 invertBit(gb->actual, byteIx, bitIx);
288 //invertBit(gb->actual, byteIx, bitIx ^ 4);
289
290 if (0) printf(" %02d.%d %08x %d\n",
291 byteIx, bitIx, hRunning ^ hInit, dist);
292 }
293 }
294 hFinal = theFn( gb );
295 assert(hFinal == hInit);
296 assert(hashIx == nHashes);
297
298 if (nNoDist > 0)
299 printf("%4d measurements, %5.2f avg dist, %2d zeroes\n",
300 (Int)nHashes, (double)totDist / (double)nHashes, nNoDist);
301 else
302 printf("%4d measurements, %5.2f avg dist\n",
303 (Int)nHashes, (double)totDist / (double)nHashes);
304
305 if (nNoDist > 0)
306 toc_nblocks_with_zero++;
307
308 toc_sum_of_avgs += (double)totDist / (double)nHashes;
309
310 free(hashes);
311 }
312
313 //////////////////////////////////////////////////////////
314
main(void)315 int main ( void )
316 {
317 FILE* f = stdin;
318 apply_to_all(f, try_onebit_changes, NULL);
319 printf("\n%d blocks, %d with a zero, %5.2f avg avg\n\n",
320 toc_nblocks, toc_nblocks_with_zero, toc_sum_of_avgs / (double)toc_nblocks );
321 return 0;
322 }
323
324 //////////////////////////////////////////////////////////
325