/*
-----------------------------------------------------------------
Software simulation of a 1024-bit hardware hash.  A work-in-progress
with the goal of entering the NIST cryptographic hash competition.

Bits are arranged in a 32 x 32 grid, well, an 8x8 grid of 
4x4-bit blocks.  The hash consists of horizontal and vertical
shuffling, followed by the a nonlinear mix applied to every 4x4-bit block.

The nonlinear mix of 4x4 blocks is actually an LFSR with usually 4 taps 
per bit for bits 0..7, another LFSR with usually 2 taps per bit for bits
8..15.  Also bits 8..15 are XORed with ((w&x)|(y&z)), where w,x,y,z are 
all in 0..7 and possibly complemented.

The hash is done in rounds.  Each round does the horizontal and 
vertical shuffling, then mixes the 4x4 blocks.  In hardware the shuffles
are free and the mixes are 6 NANDs deep.  Weak avalanche for one-bit diffs
and almost-all-zero or almost-all-one states requires 8 rounds of hash() 
or 6 rounds of ihash().

The internal state is represented by 16 64-bit integers, x[16],
where x[k] & (1<<(8*i+j)) is the kth bit of block [i][j].  This 
allows the nonlinear mixing to be done for all blocks simulateously,
and also allows horizontal and vertical wires to be handled in bulk.

Tests reveal there is some symmetry between the 8x8 blocks.  That almost
certainly makes this exact function unacceptable.  I expect the next
steps are to hillclimb the 16-bit mixing function standalone, then to
hillclimb the 16 shuffling shifts for a given mixing function.  Symmetry
would be broken if my shifts weren't so uniform.

(by Bob Jenkins, February 22 2008, public domain)
-----------------------------------------------------------------
*/

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

typedef unsigned long  u4;
typedef unsigned long long u8;

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;
}

#define LEN 16

#define ROWS 8
#define COLS 8

#define ROUNDS 200000

/* do one round of the hash */
void hash(u8 x[LEN])
{
  u8 i, j;
  u8 y[LEN];

  /* Horizontal shuffling */
  x[ 0] = (x[ 0]<<4)|(x[ 0]>>60);
  x[ 2] = (x[ 2]<<3)|(x[ 2]>>61);
  x[ 4] = (x[ 4]<<2)|(x[ 4]>>62);
  x[ 6] = (x[ 6]<<1)|(x[ 6]>>63);
  x[10] = (x[10]>>1)|(x[10]<<63);
  x[12] = (x[12]>>2)|(x[12]<<62);
  x[14] = (x[14]>>3)|(x[14]<<61);

  /* Vertical shuffling */
  x[ 3] = (x[ 3]<< 8)|(x[ 3]>>56);
  x[ 5] = (x[ 5]<<16)|(x[ 5]>>48);
  x[ 7] = (x[ 7]<<24)|(x[ 7]>>40);
  x[ 9] = (x[ 9]<<32)|(x[ 9]>>32);
  x[11] = (x[11]<<40)|(x[11]>>24);
  x[13] = (x[13]<<48)|(x[13]>>16);
  x[15] = (x[15]<<56)|(x[15]>> 8);

  for (i=0; i<LEN; ++i) y[i] = x[15-i];

  /* Do the nonlinear mixing of the bits in the 4x4 blocks */
  x[ 0] = y[2] ^ y[4] ^ y[7];
  x[ 1] = y[0] ^ y[1] ^ y[2] ^ y[3];
  x[ 2] = y[1] ^ y[2] ^ y[5] ^ y[7];
  x[ 3] = y[1] ^ y[2] ^ y[3] ^ y[6];
  x[ 4] = y[0] ^ y[2] ^ y[3] ^ y[7];
  x[ 5] = y[1] ^ y[3] ^ y[4] ^ y[5];
  x[ 6] = y[1] ^ y[2] ^ y[4] ^ y[6];
  x[ 7] = y[0] ^ y[4] ^ y[5] ^ y[6];
  x[ 8] = y[11]         ^ (( y[1] &  y[4]) | (~y[5] &  y[6]));
  x[ 9] = y[ 9] ^ y[12] ^ ((~y[6] & ~y[5]) | (~y[4] &  y[5]));
  x[10] = y[ 8] ^ y[12] ^ (( y[4] & ~y[0]) | ( y[7] & ~y[2]));
  x[11] = y[10] ^ y[15] ^ (( y[3] &  y[0]) | (~y[6] &  y[2]));
  x[12] = y[13] ^ y[14] ^ (( y[6] & ~y[1]) | ( y[4] & ~y[6]));
  x[13] = y[10] ^ y[14] ^ (( y[7] & ~y[5]) | ( y[1] & ~y[3]));
  x[14] = y[11] ^ y[15] ^ ((~y[5] & ~y[5]) | ( y[2] &  y[6]));
  x[15] = y[ 9] ^ y[11] ^ ((~y[4] & ~y[1]) | ( y[1] &  y[3]));
}

/* do the inverse of one round of the hash */
void ihash(u8 x[LEN])
{
  u8 i, j;
  u8 y[LEN];

  /* Do the nonlinear mixing of the bits in the 4x4 blocks */
  y[ 0] = x[0] ^ x[3] ^ x[4] ^ x[6];
  y[ 1] = x[0] ^ x[1] ^ x[2] ^ x[3] ^ x[7];
  y[ 2] = x[0] ^ x[4] ^ x[5] ^ x[6] ^ x[7];
  y[ 3] = x[0] ^ x[2] ^ x[5];
  y[ 4] = x[0] ^ x[2] ^ x[3] ^ x[5] ^ x[6];
  y[ 5] = x[0] ^ x[1] ^ x[2] ^ x[5] ^ x[6] ^ x[7];
  y[ 6] = x[0] ^ x[1] ^ x[4] ^ x[6];
  y[ 7] = x[0] ^ x[2] ^ x[3] ^ x[4] ^ x[7];
  x[ 8] ^= (( y[1] &  y[4]) | (~y[5] &  y[6]));
  x[ 9] ^= ((~y[6] & ~y[5]) | (~y[4] &  y[5]));
  x[10] ^= (( y[4] & ~y[0]) | ( y[7] & ~y[2]));
  x[11] ^= (( y[3] &  y[0]) | (~y[6] &  y[2]));
  x[12] ^= (( y[6] & ~y[1]) | ( y[4] & ~y[6]));
  x[13] ^= (( y[7] & ~y[5]) | ( y[1] & ~y[3]));
  x[14] ^= ((~y[5] & ~y[5]) | ( y[2] &  y[6]));
  x[15] ^= ((~y[4] & ~y[1]) | ( y[1] &  y[3]));
  y[ 8] = x[8] ^ x[9] ^ x[10] ^ x[15];
  y[ 9] = x[8] ^ x[15];
  y[10] = x[8] ^ x[11] ^ x[14];
  y[11] = x[8];
  y[12] = x[8] ^ x[9] ^ x[15];
  y[13] = x[8] ^ x[11] ^ x[12] ^ x[13] ^ x[14];
  y[14] = x[8] ^ x[11] ^ x[13] ^ x[14];
  y[15] = x[8] ^ x[14];

  for (i=0; i<LEN; ++i) x[15-i] = y[i];

  /* Mostly horizontal shuffling */
  x[ 0] = (x[ 0]>>4)|(x[ 0]<<60);
  x[ 2] = (x[ 2]>>3)|(x[ 2]<<61);
  x[ 4] = (x[ 4]>>2)|(x[ 4]<<62);
  x[ 6] = (x[ 6]>>1)|(x[ 6]<<63);
  x[10] = (x[10]<<1)|(x[10]>>63);
  x[12] = (x[12]<<2)|(x[12]>>62);
  x[14] = (x[14]<<3)|(x[14]>>61);

  /* Vertical shuffling */
  x[ 3] = (x[ 3]>> 8)|(x[ 3]<<56);
  x[ 5] = (x[ 5]>>16)|(x[ 5]<<48);
  x[ 7] = (x[ 7]>>24)|(x[ 7]<<40);
  x[ 9] = (x[ 9]>>32)|(x[ 9]<<32);
  x[11] = (x[11]>>40)|(x[11]<<24);
  x[13] = (x[13]>>48)|(x[13]<<16);
  x[15] = (x[15]>>56)|(x[15]<< 8);
}




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;
}

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

  /* 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 != 6 || 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 */
	    hash(x); hash(y);
	    hash(x); hash(y);
	    hash(x); hash(y);
	    hash(x); hash(y);
	    
	    hash(x); hash(y);
	    hash(x); hash(y);
	    hash(x); hash(y);
	    hash(x); hash(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);
	  }
	}
      }
    }
  }
}

int main()
{
  int i;
  ranctx rctx = {1,1,1,63};
  for (i=0; i<20; ++i) ranval(&rctx);
  driver(&rctx);
}