VEX/useful/smchash.c

   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
  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
  30 GuestBytes* read_one ( FILE* f )
  31 {
  32   Int r;
  33   UInt i;
  34   UInt esum, csum;
  35
  36   if (feof(f)) return NULL;
  37   assert(!ferror(f));
  38
  39   GuestBytes* gb = malloc(sizeof(GuestBytes));
  40   assert(gb);
  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
  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
  90 UInt hash_const_zero ( GuestBytes* gb ) {
  91   return 0;
  92 }
  93
  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
 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
 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
 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
 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
 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
 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
 254 void invertBit ( UChar* b, UInt ix, UInt bix ) {
 255    b[ix] ^= (1 << bix);
 256 }
 257
 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
 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 //////////////////////////////////////////////////////////