/*
-----------------------------------------------------------------
Software implementation of a 1024-bit hash.  A candidate for being
a candidate for the NIST SHA-3 cryptographic hash competition.

Bits are arranged in an 8x8 grid of 16-bit chunks.  A round (perm())
consists of applying a 16-bit permutation to each chunk, then 
rotating each of the 16 bit positions by different amounts through 
the 64 chunks.  The rotates are chosen so 2 bits each are shifted 
up by 0..7 and left by 0..7.

The nonlinear mix of 16-bit chunks is actually an 8-bit permutation 
applied to the even bits and again to the odd bits, with the 16 bits 
shuffled at the end.  This is 5 NAND-gates deep.  6 of the 16 bits
implement a^b^c^d, and can be inverted and still be implemented 5 
NAND-gates deep.  Symmetry is broken by inverting different subsets
of these 6 bits in each of the 64 chunks.  Symmetry breaking is done
in software by XORing constants.  The 16-bit permutation has avalanche
of 0.375 when applied to itself three times.

The 64 16-bit permutations are actually 128 8-bit permutations.  All
128 8-bit permutations are done at once with SSE instructions.  It 
takes 8 rounds forward or 7 rounds backwards for all bits to be 
affected by all one-bit deltas for nearly-zero states (avalanche 
0.27 forward, 0.23 backward).  (7 rounds forward (avalanche 0.378) 
or 6 backwards (avalanche 0.19) for random states.)  

I'm making an ungrounded assumption that twice forward + backward
avalanche, 30 rounds that is, is enough to thwart cryptanalysis.
Further, I'm assuming it doesn't matter if these are consecutive rounds.
This is done by combining a block every 3 rounds.  Each block is combined 
four times, at offsets i (plus two rounds), i+15-6(i%4), i+26-6(i%4), 
and i+37.  The offset by two rounds for the first use guarantees at least 
one round of differentials is required per blocks.  Brute-force search 
said that all sets of 9 variables or less require at least 30 rounds of 
differentials that way.

(by Bob Jenkins, August 14 2008, public domain)
-----------------------------------------------------------------
*/

#include <stdio.h>
#include <stddef.h>
#include <windows.h>
#include <emmintrin.h>

typedef unsigned long  u4;
typedef unsigned long long u8;

#define LEN 16     /* number of 8-byte values per block */

#define ROWS 8
#define COLS 8

#define ROUNDS 20000

#define xor(a,b) (a ^ b)
#define or(a,b) (a | b)
#define and(a,b) (a & b)
#define ant(a,b) (~a & b)
#define not(a) ~a
#define read(x,i) x[i*2]
#define write(y,i,a) y[i*2] = a

/* apply the 8-bit permutation to the even bits */
static void eight( u8 *x, u8 *y)
{
  u8 q,r;
  u8 a0 = read(x,0);
  u8 a1 = read(x,1);
  u8 a2 = read(x,2);
  u8 a3 = read(x,3);
  u8 a4 = read(x,4);
  u8 a5 = read(x,5);
  u8 a6 = read(x,6);
  u8 a7 = read(x,7);

  q = xor(a4,a5);
  r = xor(a7,a0);
  write(y,0,xor(q,r));

  q = xor(a5,a1);
  r = xor(a3,a2);
  write(y,1,xor(q,r));

  q = xor(a3,a4);
  r = xor(a5,a1);
  write(y,2,xor(q,r));

  q = ant(xor(a0,a3),xor(a6,a4));
  r = ant(xor(a4,a6),or(and(a0,a1),ant(a0,a3)));
  write(y,3,or(q,r));

  q = ant(xor(a6,a7),xor(a5,a2));
  r = and(or(not(or(a2,a5)),and(a4,a5)),xor(a7,a6));
  write(y,4,or(q,r));

  q = and(xor(a5,a0),xor(a4,a2));
  r = ant(xor(a2,a4),or(and(a0,a5),ant(a0,a1)));
  write(y,5,or(q,r));

  q = and(xor(a4,a2),xor(a7,a6));
  r = ant(xor(a2,a4),or(ant(a7,a0),and(a6,a7)));
  write(y,6,or(q,r));

  q = and(or(not(or(a6,a7)),ant(and(a6,a7),a0)),xor(a4,a2));
  r = ant(xor(a2,a4),or(ant(and(a0,a2),a6),ant(a0,a7)));
  write(y,7,or(q,r));

}

#undef xor
#undef or
#undef and
#undef ant
#undef not
#undef read
#undef write

#define xor(a,b) _mm_xor_si128(a, b)
#define or(a,b) _mm_or_si128(a, b)
#define and(a,b) _mm_and_si128(a, b)
#define ant(a,b) _mm_andnot_si128(a, b)
#define not(a) _mm_xor_si128(a, _mm_set_epi32(0xffffffff, 0xffffffff, 0xffffffff, 0xffffffff))
#define read(x,i) _mm_load_si128((void *)&x[i])
#define write(y,i,a) _mm_storeu_si128((void *)&y[i], a)

static void eightSSE(__m128i *x, __m128i *y)
{
  __m128i q,r;
  __m128i a0 = read(x,0);
  __m128i a1 = read(x,1);
  __m128i a2 = read(x,2);
  __m128i a3 = read(x,3);
  __m128i a4 = read(x,4);
  __m128i a5 = read(x,5);
  __m128i a6 = read(x,6);
  __m128i a7 = read(x,7);

  q = xor(a4,a5);
  r = xor(a7,a0);
  write(y,0,xor(q,r));

  q = xor(a5,a1);
  r = xor(a3,a2);
  write(y,1,xor(q,r));

  q = xor(a3,a4);
  r = xor(a5,a1);
  write(y,2,xor(q,r));

  q = ant(xor(a0,a3),xor(a6,a4));
  r = ant(xor(a4,a6),or(and(a0,a1),ant(a0,a3)));
  write(y,3,or(q,r));

  q = ant(xor(a6,a7),xor(a5,a2));
  r = and(or(not(or(a2,a5)),and(a4,a5)),xor(a7,a6));
  write(y,4,or(q,r));

  q = and(xor(a5,a0),xor(a4,a2));
  r = ant(xor(a2,a4),or(and(a0,a5),ant(a0,a1)));
  write(y,5,or(q,r));

  q = and(xor(a4,a2),xor(a7,a6));
  r = ant(xor(a2,a4),or(ant(a7,a0),and(a6,a7)));
  write(y,6,or(q,r));

  q = and(or(not(or(a6,a7)),ant(and(a6,a7),a0)),xor(a4,a2));
  r = ant(xor(a2,a4),or(ant(and(a0,a2),a6),ant(a0,a7)));
  write(y,7,or(q,r));

}


static int shift[LEN] = {40,60,26,4,0,3,11,15,13,13,1,41,14,7,18,14};
static int map[LEN] = {12,13,4,9,1,14,5,2,10,8,6,7,3,15,0,11};

/* one permutation of the internal state */
static void perm(u8 *x)
{
  int i;
  __m128i y2[LEN/2];
  u8 *y = (u8 *)y2;

  /* do 128 8-bit permutations */
  eightSSE((__m128i *)x, (__m128i *)y);

  /* break symmetry among the 64 16-bit permutations */
  y[0] ^= 0x18f8aa72369b75c2LL;
  y[1] ^= 0x337b824aab77201fLL;
  y[2] ^= 0x60bd51315e37b49cLL;
  y[3] ^= 0x82ed31eb138e02efLL;
  y[4] ^= 0x5fe101ed66fc3130LL;
  y[5] ^= 0x1019906dca58dffbLL;

  /* shuffle and rotate the 16 output bits among the 64 chunks */
  x[12] = (y[0] << 40) | (y[0] >> (64-40));
  x[13] = (y[1] << 60) | (y[1] >> (64-60));
  x[ 4] = (y[2] << 26) | (y[2] >> (64-26));
  x[ 9] = (y[3] <<  4) | (y[3] >> (64- 4));
  x[ 1] =  y[4];
  x[14] = (y[5] <<  3) | (y[5] >> (64- 3));
  x[ 5] = (y[6] << 11) | (y[6] >> (64-11));
  x[ 2] = (y[7] << 15) | (y[7] >> (64-15));
  x[10] = (y[8] << 13) | (y[8] >> (64-13));
  x[ 8] = (y[9] << 13) | (y[9] >> (64-13));
  x[ 6] = (y[10]<<  1) | (y[10]>> (64- 1));
  x[ 7] = (y[11]<< 41) | (y[11]>> (64-41));
  x[ 3] = (y[12]<< 14) | (y[12]>> (64-14));
  x[15] = (y[13]<<  7) | (y[13]>> (64- 7));
  x[ 0] = (y[14]<< 18) | (y[14]>> (64-18));
  x[11] = (y[15]<< 14) | (y[15]>> (64-14));
}

static int unperm[256];

/* the inverse of eight(x,y) */
static void uneight(u8 *y, u8 *x)
{
  int i, j;
  for (i=0; i<LEN/2; ++i) {
    x[2*i] = 0;
  }
  for (i=0; i<64; ++i) {
    int z = 0;
    for (j=0; j<LEN/2; ++j) {
      if (y[2*j] & (((u8)1)<<i)) {
	z ^= (1<<j);
      }
    }
    z = unperm[z];
    for (j=0; j<LEN/2; ++j) {
      if (z & (1<<j)) {
	x[2*j] ^= (((u8)1)<<i);
      }
    }
  }
}

/* do the inverse of one permutation of the internal state */
static void iperm(u8 x[LEN])
{
  int i;
  u8 y[LEN];

  /* unshuffle the output bits */
  for (i=0; i<LEN; ++i) {
    y[i] = x[map[i]];
  }
 
  /* unrotate the output bits */
  for (i=0; i<LEN; ++i) {
    y[i] = (y[i] >> shift[i]) | (y[i] << (64-shift[i]));
  }

  /* break symmetry among the 64 16-bit permutations */
  y[0] ^= 0x18f8aa72369b75c2LL;
  y[1] ^= 0x337b824aab77201fLL;
  y[2] ^= 0x60bd51315e37b49cLL;
  y[3] ^= 0x82ed31eb138e02efLL;
  y[4] ^= 0x5fe101ed66fc3130LL;
  y[5] ^= 0x1019906dca58dffbLL;
    
  /* revert the two 8-bit permutations */
  uneight(&y[1], &x[1]);
  uneight(y, x);
}


/* a random number generator, for testing, not part of the hash */
typedef struct ranctx { u4 a; u4 b; u4 c; u4 d; } ranctx;

#define rot(x,k) ((x<<k)|(x>>(32-k)))
u4 ranval( ranctx *x ) {
  u4 e = x->a - rot(x->b, 27);
  x->a = x->b ^ rot(x->c, 17);
  x->b = x->c + x->d;
  x->c = x->d + e;
  x->d = e + x->a;
  return e;
}

void show(u8 x[LEN])
{
  int i,j,k;
  for (i=0; i<ROWS; ++i) {
    for (j=0; j<COLS; ++j) {
      for (k=0; k<4; ++k) {
	printf(" %s", (x[k] & (((u8)1)<<(COLS*i+j))) ? "1" : "0");
      }
    }
    printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=8; --k>=4; ) {
	printf(" %s", (x[k] & (((u8)1)<<(COLS*i+j))) ? "1" : "0");
      }
    }
    printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=8; k<12; ++k) {
	printf(" %s", (x[k] & (((u8)1)<<(COLS*i+j))) ? "1" : "0");
      }
    }
    printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=16; --k>=12; ) {
	printf(" %s", (x[k] & (((u8)1)<<(COLS*i+j))) ? "1" : "0");
      }
    }
    printf("\n");
  }
  printf("\n");
}

void showx(float x, float *worst, int verbose)
{
  x = x/ROUNDS;
  if (x < *worst) *worst = x;
  if (verbose) printf("%3d", (int)(100*x + 0.5));
  if (1.0-x < *worst) *worst = 1.0-x;
}

float showc(float c[ROWS][COLS][LEN], int verbose)
{
  int i,j,k;
  float worst = 1.0;
  for (i=0; i<ROWS; ++i) {
    for (j=0; j<COLS; ++j) {
      for (k=0; k<4; ++k) {
	showx(c[i][j][k], &worst, verbose);
      }
      if (verbose) printf(" ");
    }
    if (verbose) printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=8; --k>=4; ) {
	showx(c[i][j][k], &worst, verbose);
      }
      if (verbose) printf(" ");
    }
    if (verbose) printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=8; k<12; ++k) {
	showx(c[i][j][k], &worst, verbose);
      }
      if (verbose) printf(" ");
    }
    if (verbose) printf("\n");
    for (j=0; j<COLS; ++j) {
      for (k=16; --k>=12; ) {
	showx(c[i][j][k], &worst, verbose);
      }
      if (verbose) printf(" ");
    }
    if (verbose) printf("\n\n");
  }
  /* printf("  worst = %f\n", worst); */
  return worst;
}

#define TESTONERUNS 100
void testone(ranctx *rctx)
{
  u4 count[LEN];
  __m128i x2[LEN/2];
  __m128i y2[LEN/2];
  u8 *x = (u8 *)x2;
  u8 *y = (u8 *)y2;
  u4 i;

  for (i=0; i<(1<<LEN); ++i) {
    u4 j;
    for (j=0; j<LEN; ++j) {
      count[j] = 0;
    }
    for (j=0; j<TESTONERUNS; ++j) {
      u4 k, r;
      r = ranval(rctx);
      for (k=0; k<LEN; ++k) {
	y[k] = x[k] = (r & (1<<k)) ? 1 : 0;
      }
      for (k=0; k<LEN; ++k) {
	if (i & (1<<k)) y[k] ^= 1;
      }
      perm(x);
      perm(y);
      for (k=0; k<LEN; ++k) {
	if ((x[k]^y[k]) & 1) ++count[k];
      }
    }
    for (j=0; j<LEN; ++j) {
      if (count[j] > .15*TESTONERUNS && count[j] < .85*TESTONERUNS) break;
    }
    if (j == LEN) {
      printf("%.4x  ", i);
      for (j=0; j<LEN; ++j) {
	printf("%3d ", count[j]);
      }
      printf("\n");
    }
  }
}

void test(ranctx *rctx)
{
  u4 m,n,o,p,count,i,j,k;
  float val, worst = 1.0;
  float zcount = 0.0;
  __m128i x2[LEN/2];
  __m128i y2[LEN/2];
  u8 *x = (u8 *)x2;
  u8 *y = (u8 *)y2;

  /* check that eight() is the reverse of uneight() */
  for (i=0; i<LEN; ++i) {
    x[i] =  0xdeadbeefdeadbeefLL;
  }
  eight(x, y);
  uneight(y, x);
  for (i=0; i<LEN; ++i) {
    if (x[i] != 0xdeadbeefdeadbeefLL) {
      printf("eight and uneight are not inverses!\n");
      return;
    }
  }

  /* check that perm() is reversible and iperm() is its reverse */
  for (i=0; i<LEN; ++i) {
    x[i] = y[i] = 0xdeadbeefdeadbeefLL;
  }
  for (i=0; i<LEN; ++i) {
    perm(x);
  }
  for (i=0; i<LEN; ++i) {
    iperm(x);
  }
  for (i=0; i<LEN; ++i) {
    if (x[i] != y[i]) {
      printf("perm(x) and iperm(x) are not inverses!\n");
      /* return; */
    }
  }

  /* see how thoroughly bit "tab[m][n] & (1<<o)" propogates */
  for (m=0; m<ROWS; ++m) {
    for (n=0; n<COLS; ++n) {
      for (o=0; o<LEN; ++o) {
	for (p=0; p<2*LEN; p++) {
	  float c[ROWS][COLS][LEN];  /* count of how many times bit flipped */
	  u4 r;  /* count # of rounds */

	  if (m != 5 || n != 7 || o != 12 || p != 0) continue;
	  /* if (m != 0) continue; */

	  /* initialize c */
	  for (i=0; i<ROWS; ++i) {
	    for (j=0; j<COLS; ++j) {
	      for (k=0; k<LEN; ++k) {
		c[i][j][k] = 0;
	      }
	    }
	  }

	  /* try r keys */
	  for (r=0; r<ROUNDS; ++r) {

	    /* initialize to a random key */
	    for (i=0; i<LEN; ++i) {
	      x[i] = y[i] = ((u8)ranval(rctx)) | (((u8)ranval(rctx))<<32);
	      /* x[i] = y[i] = (p/LEN ? ~((u8)0) : ((u8)0)); */
	    }
	    x[p%LEN] ^= ((u8)r)<<0;
	    y[p%LEN] = x[p%LEN];

	    /* start with bit [m][n][o] different */
	    y[o] ^= (((u8)1) << (COLS*m+n));

	    /* apply several rounds of the hash to both keys */
	    perm(x); perm(y);
	    perm(x); perm(y);
	    perm(x); perm(y);

	    perm(x); perm(y);
	    perm(x); perm(y);
	    perm(x); perm(y);

	    perm(x); perm(y);

	    /* measure which bits were affected */
	    for (k=0; k<LEN; ++k) {
	      u8 diff = x[k] ^ y[k];
	      for (i=0; i<ROWS; ++i) {
		for (j=0; j<COLS; ++j) {
		  if (diff & (((u8)1) << (COLS*i+j))) {
		    ++c[i][j][k];
		  }
		}
	      }
	    }
	  }

	  /* report which bits were affected */
	  val = showc(c, 1);
	  if (val == 0) {
	    ++zcount;
	  }
	  if (val < worst) {
	    worst = val;
	    printf("new worst: %f  %d %d %d %d\n", worst, m,n,o,p);
	  }
	}
      }
    }
  }
}

void set_unperm()
{
  u8 x[LEN];
  u8 y[LEN];
  int perm[256];
  int i, j;
  for (i=0; i<256; ++i) {
    for (j=0; j<8; ++j) {
      x[2*j] = (i & (1<<j)) ? 1 : 0;
    }
    eight(x, y);
    perm[i] = 0;

    for (j=0; j<8; ++j) {
      if (y[2*j] & 1) {
	perm[i] ^= (1<<j);
      }
    }
  }
  for (i=0; i<256; ++i) {
    unperm[perm[i]] = i;
  }
}

#define BYTES_PER_BLOCK (sizeof(u8)*LEN)
#define BLOCKS 64  /* cached accumulators */

#define DO_ADD(i) \
  { \
    __m128i  val1 = _mm_load_si128((void *)&((const __m128i *)next)[i]); \
    __m128i *where = &fourth[(i+6) % (LEN/2)];		\
    __m128i  val2;                                      \
    _mm_storeu_si128(where, val1);			\
    where = &third[(i+3) % (LEN/2)];			\
    val2 = _mm_load_si128(where);			\
    val2 = _mm_xor_si128(val2, val1);			\
    _mm_storeu_si128(where, val2);			\
    where = &second[(i+1) % (LEN/2)];			\
    val2 = _mm_load_si128(where);			\
    val2 = _mm_xor_si128(val2, val1);			\
    _mm_storeu_si128(where, val2);			\
  }

#define DO(x) \
  x(0); x(1); x(2); x(3); x(4); x(5); x(6); x(7)

/* add the next block to the accumulators */
#define SECOND  26
#define THIRD   28
#define FOURTH  38

#define COMBINE(i) \
  {						        \
    __m128i  val1 = _mm_load_si128((void *)&accum[i]);	\
    __m128i *where = &state[i];				\
    __m128i  val2 = _mm_load_si128(where);		\
    val2 = _mm_xor_si128(val2, val1);			\
    _mm_storeu_si128(where, val2);			\
  }

static void do_combine(const __m128i *accum, __m128i *state)
{
  DO(COMBINE);
}

/* one combine */
static void one_combine(
  __m128i **a, 
  int      *index, 
  __m128i  *state, 
  const void *next)
{
  int x = *index;
  __m128i *first = a[x & (BLOCKS-1)];

  /* add second, third, fourth uses of older blocks */
  do_combine(first, state);

  perm((u8 *)state);

  /* add the first use of current block */
  do_combine(next, state);

  /* accumulate second, third, fourth use of current block */
  {
    int offset = 6*(x&3);
    __m128i *second = a[(x + SECOND - offset) & (BLOCKS-1)];
    __m128i *third  = a[(x + THIRD - offset) & (BLOCKS-1)];
    __m128i *fourth = a[(x + FOURTH) & (BLOCKS-1)] = first;
    
    DO(DO_ADD);
  }

  perm((u8 *)state);
  perm((u8 *)state);

  /* remember that we've done another combine */
  ++*index;
}


/* finish it off when there are no more inputs */
void end_combine(
  __m128i **a, 
  int      *index, 
  __m128i  *state) 
{
  __m128i *accum = a[*index & (BLOCKS-1)];

  /* add the current accumulator (accum) to the internal state */
  DO(COMBINE);

  /* apply three rounds to the internal state */
  perm((u8 *)state);
  perm((u8 *)state);
  perm((u8 *)state);

  /* remember that we've done another combine */
  ++*index;
}


void hash(
  void  *data,    /* array of bytes to hash, align to 8-byte boundary! */
  size_t length,  /* original length of the data, in bytes */
  const __m128i *key,   /* 128-byte key aligned to 16-byte boundary */
  __m128i *state)   /* 1024-bit hash value */
{
  int i;
  __m128i buf[LEN/2];   /* for last data block*/
  __m128i *a[BLOCKS];   /* accumulators, to be added to the state */
  __m128i abuf[FOURTH][LEN/2]; /* buffers for a */
  int offset = 0;       /* offset into the accumulators */
  size_t dataoff;       /* offset into the data */
  size_t stop = (length/BYTES_PER_BLOCK)*BYTES_PER_BLOCK;
  __m128i *accum;

  /* use the key to set up the state and the accumulators */
  memset((char *)state, 0, BYTES_PER_BLOCK);
  for (i=0; i<FOURTH; ++i) {
    a[i] = abuf[i];
  }
  for (i=0; i<FOURTH; ++i) {
    memset(a[(i+offset) & (BLOCKS-1)], 0, BYTES_PER_BLOCK);
  }
  one_combine(a, &offset, state, key);

  /* loop: handle 16 8-byte quantities at a time */
  for (dataoff = 0; dataoff < stop; dataoff += BYTES_PER_BLOCK) {
    one_combine(a, &offset, state, &((char *)data)[dataoff]);
  }
  if (dataoff != stop) printf("bob you have a bug\n");

  /* handle the last block */
  if (stop < length) {
    memcpy(buf, &((char *)data)[stop], length-stop);
    memset(((char *)buf)+length-stop, 0, BYTES_PER_BLOCK-(length-stop));
    one_combine(a, &offset, state, buf);
  }

  /* Use the key again, and the length */
  memcpy(buf, key, BYTES_PER_BLOCK);
  ((u8 *)buf)[0] ^= ((u8)length)<<3;
  ((u8 *)buf)[1] ^= ((u8)length)>>(64-3);
  one_combine(a, &offset, state, buf);

  /* apply the remaining uses of the last few blocks */
  for (i=0; i<FOURTH-1; ++i) {
    end_combine(a, &offset, state);
  }

  /* the last combine of the key: no mixing needed after this */
  accum = a[offset & (BLOCKS-1)];
  DO(COMBINE);
}

int main()
{
  int i;
  ranctx rctx = {1,1,1,1};
  char message[] = "";
  __m128i key[LEN/2];
  __m128i val[LEN/2];
  __m128i buf[1<<12];
  u8 starttime;
  u8 endtime;

  for (i=0; i<20; ++i) ranval(&rctx);
  set_unperm();
  memset((char *)key, 0, sizeof(key));

  printf("usual chances of one bit affecting other bits after 7 rounds:\n");
  test(&rctx);
  printf("\n");

  hash(message, strlen(message), (const __m128i *)key, (__m128i *)val);
  printf("length: %d, data: %s\n", strlen(message), message);
  printf("hash:\n");
  for (i=0; i<LEN; ++i) {
    printf("%.16llx\n", ((u8 *)val)[i]);
  }
  printf("\n");

  for (i=0; i<sizeof(buf)/sizeof(u8); ++i) {
    ((u8 *)buf)[i] = ranval(&rctx) + ((u8)ranval(&rctx))<<32;
  }
  printf("time for 1 billion bytes:\n");
  starttime = GetTickCount();
  for (i=0; i<(1<<14); ++i) {
    hash(buf, sizeof(buf), (__m128i *)key, (__m128i *)val);
  }
  endtime = GetTickCount();
  printf("   %d millisecond\n", endtime-starttime);
  for (i=0; i<LEN; ++i) {
    printf("%.16llx\n", ((u8 *)val)[i]);
  }
  printf("\n");

  printf("time for empty string 512K times:\n");
  starttime = GetTickCount();
  for (i=0; i<(1<<19); ++i) {
    hash(buf, 0, (__m128i *)key, (__m128i *)val);
  }
  endtime = GetTickCount();
  printf("   %d millisecond\n", endtime-starttime);
  for (i=0; i<LEN; ++i) {
    printf("%.16llx\n", ((u8 *)val)[i]);
  }
  printf("\n");
}