#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef signed int Int;
typedef unsigned int UInt;
typedef unsigned long long int Addr64;
typedef unsigned char UChar;
typedef unsigned long int UWord;
static inline UInt ROL32 ( UInt x, UInt n ) {
assert(n != 0);
n &= 31;
x = (x << n) | (x >> (32-n));
return x;
}
//////////////////////////////////////////////////////////
typedef
struct {
Addr64 ga;
Int nbytes;
UChar* bytes;
UChar* actual;
}
GuestBytes;
GuestBytes* read_one ( FILE* f )
{
Int r;
UInt i;
UInt esum, csum;
GuestBytes* gb = malloc(sizeof(GuestBytes));
assert(gb);
if (feof(f)) return NULL;
assert(!ferror(f));
r= fscanf(f, "GuestBytes %llx %d ", &gb->ga, &gb->nbytes);
if (0) printf("r = %d\n", r);
assert(r == 2);
assert(gb->ga != 0);
assert(gb->nbytes > 0);
assert(gb->nbytes < 5000); // let's say
Int nToAlloc = gb->nbytes + (gb->ga & 3);
gb->bytes = malloc( gb->nbytes + nToAlloc);
gb->actual = gb->bytes + (gb->ga & 3);
assert(gb->bytes);
csum = 0;
for (i = 0; i < gb->nbytes; i++) {
UInt b;
r= fscanf(f, "%02x ", &b);
assert(r == 1);
gb->actual[i] = b;
csum = (csum << 1) ^ b;
}
r= fscanf(f, " %08x\n", &esum);
assert(r == 1);
assert(esum == csum);
return gb;
}
//////////////////////////////////////////////////////////
void apply_to_all ( FILE* f,
void(*fn)( GuestBytes*, void* ),
void* opaque )
{
while (!feof(f)) {
GuestBytes* gb = read_one(f);
if (0) printf("got %llu %d\n", gb->ga, gb->nbytes);
fn( gb, opaque );
free(gb->bytes);
free(gb);
}
}
//////////////////////////////////////////////////////////
UInt hash_const_zero ( GuestBytes* gb ) {
return 0;
}
UInt hash_sum ( GuestBytes* gb ) {
UInt i, sum = 0;
for (i = 0; i < gb->nbytes; i++)
sum += (UInt)gb->actual[i];
return sum;
}
UInt hash_rol ( GuestBytes* gb ) {
UInt i, sum = 0;
for (i = 0; i < gb->nbytes; i++) {
sum ^= (UInt)gb->actual[i];
sum = ROL32(sum,7);
}
return sum;
}
static UInt cand0 ( GuestBytes* gb )
{
UWord addr = (UWord)gb->actual;
UWord len = gb->nbytes;
UInt sum = 0;
/* pull up to 4-alignment */
while ((addr & 3) != 0 && len >= 1) {
UChar* p = (UChar*)addr;
sum = (sum << 8) | (UInt)p[0];
addr++;
len--;
}
/* vectorised + unrolled */
while (len >= 16) {
UInt* p = (UInt*)addr;
sum = ROL32(sum ^ p[0], 13);
sum = ROL32(sum ^ p[1], 13);
sum = ROL32(sum ^ p[2], 13);
sum = ROL32(sum ^ p[3], 13);
addr += 16;
len -= 16;
}
/* vectorised fixup */
while (len >= 4) {
UInt* p = (UInt*)addr;
sum = ROL32(sum ^ p[0], 13);
addr += 4;
len -= 4;
}
/* scalar fixup */
while (len >= 1) {
UChar* p = (UChar*)addr;
sum = ROL32(sum ^ (UInt)p[0], 19);
addr++;
len--;
}
return sum;
}
static UInt cand1 ( GuestBytes* gb )
{
UWord addr = (UWord)gb->actual;
UWord len = gb->nbytes;
UInt sum1 = 0, sum2 = 0;
/* pull up to 4-alignment */
while ((addr & 3) != 0 && len >= 1) {
UChar* p = (UChar*)addr;
sum1 = (sum1 << 8) | (UInt)p[0];
addr++;
len--;
}
/* vectorised + unrolled */
while (len >= 16) {
UInt* p = (UInt*)addr;
UInt w;
w = p[0]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
w = p[1]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
w = p[2]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
w = p[3]; sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
addr += 16;
len -= 16;
sum1 ^= sum2;
}
/* vectorised fixup */
while (len >= 4) {
UInt* p = (UInt*)addr;
UInt w = p[0];
sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
addr += 4;
len -= 4;
sum1 ^= sum2;
}
/* scalar fixup */
while (len >= 1) {
UChar* p = (UChar*)addr;
UInt w = (UInt)p[0];
sum1 = ROL32(sum1 ^ w, 31); sum2 += w;
addr++;
len--;
}
return sum1 + sum2;
}
static UInt adler32 ( GuestBytes* gb )
{
UWord addr = (UWord)gb->actual;
UWord len = gb->nbytes;
UInt s1 = 1;
UInt s2 = 0;
UChar* buf = (UChar*)addr;
while (len >= 4) {
s1 += buf[0];
s2 += s1;
s1 += buf[1];
s2 += s1;
s1 += buf[2];
s2 += s1;
s1 += buf[3];
s2 += s1;
buf += 4;
len -= 4;
}
while (len > 0) {
s1 += buf[0];
s2 += s1;
len--;
buf++;
}
return (s2 << 16) + s1;
}
//////////////////////////////////////////////////////////
UInt (*theFn)(GuestBytes*) =
//hash_const_zero;
//hash_sum;
//hash_rol;
//cand0;
cand1;
//adler32;
Int cmp_UInt_ps ( UInt* p1, UInt* p2 ) {
if (*p1 < *p2) return -1;
if (*p1 > *p2) return 1;
return 0;
}
Int nSetBits ( UInt w )
{
Int i, j;
j = 0;
for (i = 0; i < 32; i++)
if (w & (1<<i))
j++;
return j;
}
Int toc_nblocks = 0;
Int toc_nblocks_with_zero = 0;
double toc_sum_of_avgs = 0.0;
void invertBit ( UChar* b, UInt ix, UInt bix ) {
b[ix] ^= (1 << bix);
}
void try_onebit_changes( GuestBytes* gb, void* opaque )
{
toc_nblocks++;
/* collect up the hash values for all one bit changes of the key,
and also that for the unmodified key. Then compute the number
of changed bits for all of them. */
UInt hashIx = 0;
UInt nHashes = 8 * gb->nbytes;
UInt* hashes = malloc( nHashes * sizeof(UInt) );
UInt byteIx, bitIx;
UInt hInit, hFinal, hRunning;
Int dist, totDist = 0, nNoDist = 0;
assert(hashes);
hInit = theFn( gb );
for (byteIx = 0; byteIx < gb->nbytes; byteIx++) {
for (bitIx = 0; bitIx < 8; bitIx++) {
invertBit(gb->actual, byteIx, bitIx);
//invertBit(gb->actual, byteIx, bitIx ^ 4);
hRunning = theFn( gb );
dist = nSetBits(hRunning ^ hInit);
totDist += dist;
if (dist == 0) nNoDist++;
hashes[hashIx++] = hRunning;
invertBit(gb->actual, byteIx, bitIx);
//invertBit(gb->actual, byteIx, bitIx ^ 4);
if (0) printf(" %02d.%d %08x %d\n",
byteIx, bitIx, hRunning ^ hInit, dist);
}
}
hFinal = theFn( gb );
assert(hFinal == hInit);
assert(hashIx == nHashes);
if (nNoDist > 0)
printf("%4d measurements, %5.2f avg dist, %2d zeroes\n",
(Int)nHashes, (double)totDist / (double)nHashes, nNoDist);
else
printf("%4d measurements, %5.2f avg dist\n",
(Int)nHashes, (double)totDist / (double)nHashes);
if (nNoDist > 0)
toc_nblocks_with_zero++;
toc_sum_of_avgs += (double)totDist / (double)nHashes;
free(hashes);
}
//////////////////////////////////////////////////////////
int main ( void )
{
FILE* f = stdin;
apply_to_all(f, try_onebit_changes, NULL);
printf("\n%d blocks, %d with a zero, %5.2f avg avg\n\n",
toc_nblocks, toc_nblocks_with_zero, toc_sum_of_avgs / (double)toc_nblocks );
return 0;
}
//////////////////////////////////////////////////////////