1
2#include <stdio.h>
3#include <stdlib.h>
4#include <assert.h>
5
6typedef  signed int              Int;
7typedef  unsigned int            UInt;
8typedef  unsigned long long int  Addr64;
9typedef  unsigned char           UChar;
10typedef  unsigned long int       UWord;
11
12static 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
21typedef
22   struct {
23      Addr64 ga;
24      Int    nbytes;
25      UChar* bytes;
26      UChar* actual;
27   }
28   GuestBytes;
29
30GuestBytes* 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
75void 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
90UInt hash_const_zero ( GuestBytes* gb ) {
91  return 0;
92}
93
94UInt 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
101UInt 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
110static 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
149static 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
193static 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
226UInt (*theFn)(GuestBytes*) =
227  //hash_const_zero;
228  //hash_sum;
229//hash_rol;
230//cand0;
231  cand1;
232  //adler32;
233
234Int cmp_UInt_ps ( UInt* p1, UInt* p2 ) {
235  if (*p1 < *p2) return -1;
236  if (*p1 > *p2) return 1;
237  return 0;
238}
239
240Int 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
250Int    toc_nblocks           = 0;
251Int    toc_nblocks_with_zero = 0;
252double toc_sum_of_avgs       = 0.0;
253
254void invertBit ( UChar* b, UInt ix, UInt bix ) {
255   b[ix] ^= (1 << bix);
256}
257
258void 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
315int 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