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 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 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 ////////////////////////////////////////////////////////// 325
