/*
-----------------------------------------------------------------
Software implementation of Maraca, a submission for the NIST SHA-3 
cryptographic hash competition.  Reference version.

Bits are split into 64 16-bit chunks.  A 1024-bit 
permutation (a call to perm()) consists of applying a 16-bit 
mix to each chunk, then rotating each of the 16 bit 
positions by different amounts through the 64 chunks.  The rotates 
are of the form i+8j, where all i in 0..7 and j in 0..7 are used twice.

The nonlinear reversible mix of 16-bit chunks is actually a 
nonlinear reversible 8-bit mix applied to the even bits and again 
to the odd bits, with the 16 bits shuffled at the end.  
Symmetry is broken by inverting different subsets of the first 6 bits 
in each of the 64 chunks, by XORing constants.  This reference version
uses 64-bit values, and uses table lookup to compute the 8-bit mix.  The
optimized version uses 128-bit values, and uses logic to compute all 128
8-bit mixes simultaneously.

It takes 8 perm() calls forward or 7 backwards for all bits 
to be affected by all one-bit deltas for nearly-zero states (the minimum
avalanche effect on output bits is 0.12 forward, 0.41 backward).  For 
random base  states, 7 perm() forward has effect 0.37, 6 backwards has 
avalanche 0.38. 

Maraca claims that twice forward + backward avalanche, 30 perm() calls 
that is, is enough to thwart cryptanalysis.
Further, it claims it doesn't matter if these are consecutive 
permutations or how many blocks are involved.  This is done by 
combining a new block every 3 perm()s.
The ith block is XORed to the internal state four times, before 
perm()s 3i, 3(i+21-6(i%4))+1, 3(i+41-6((i+2)%4))+1, and 3(i+46)+1.
The first use the only block XORed at that point, but the other three 
uses have two other blocks XORed to the internal state at the same time.
The j=1..4th use is left rotated by 128*j(j-1)/2 bits.  Brute-force 
search found no pattern of blocks allowed a delta to pass through less 
than 30 perm()s, but the search was too big to complete.

(by Bob Jenkins, October 21 2008, public domain)
-----------------------------------------------------------------
*/

#include <stdio.h>
#include <stddef.h>
#include <windows.h>
#include "reference.h"

#define BYTES_PER_BLOCK (sizeof(u8)*MARACA_LEN)
#define BITS_PER_BLOCK  (8*BYTES_PER_BLOCK)
#define bytes(x)        (((x)+7)/8)

/* #define TRACE_INTERMEDIATE_VALUES */

#ifdef TRACE_INTERMEDIATE_VALUES
static int display_count;
#endif




/* the nonlinear reversible 8-bit mix */
static int eight_tab[256] = 
{
    0, 65, 38, 79,146,179,148,189, 14, 71, 40, 73,156,181,154,187,
  141,164,139,162, 31, 86, 57, 80,131,170,133,172, 17, 88, 55, 94,
   23,118, 49,120,165,132,163,138, 25,112, 63,126,171,130,173,140,
  186,147,188,149,  8, 97, 46,103,180,157,178,155,  6,111, 32,105,
  152,209,190,215, 74,227, 76,229,150,223,176,217, 68,237, 66,235,
   85,244, 83,250,135, 70,161, 72, 91,242, 93,252,137, 64,175, 78,
  143,230,169,224,109,196,107,194,129,232,167,238, 99,202,101,204,
  114,211,116,221,144,113,182,127,124,213,122,219,158,119,184,121,
  145, 16,183, 30, 67,226, 69,236,159, 22,185, 24, 77,228, 75,234,
   92,245, 90,243,142,  7,168,  1, 82,251, 84,253,128,  9,166, 15,
  134, 39,160, 41,100,197, 98,203,136, 33,174, 47,106,195,108,205,
  123,210,125,212,153, 48,191, 54,117,220,115,218,151, 62,177, 56,
  201,192,239,198, 27, 50, 29, 52,199,206,225,200, 21, 60, 19, 58,
    4, 37,  2, 43,214, 87,240, 89, 10, 35, 12, 45,216, 81,254, 95,
  222,247,248,241, 44,  5, 42,  3,208,249,246,255, 34, 11, 36, 13,
   51, 18, 53, 28,193, 96,231,110, 61, 20, 59, 26,207,102,233,104
};

/* eight: apply the 8-bit mix to the even bits */
void eight( u8 *x, u8 *y)
{
  int i, j;

  for (i=0; i<MARACA_LEN/2; ++i)
  {
    y[2*i] = 0;
  }
  /* apply the 8-bit mix to the even bits */
  for (i=0; i<64; ++i)
  {
    /* apply the 8-bit mix to the eight even bits */
    int val = 0;
    for (j=0; j<MARACA_LEN/2; ++j)
    {
      if (x[2*j] & (((u8)1)<<i))
      {
	val ^= (1<<j);
      }
    }
    val = eight_tab[val];
    for (j=0; j<MARACA_LEN/2; ++j)
    {
      if (val & (1<<j))
      {
	y[2*j] ^= (((u8)1)<<i);
      }
    }
  }
}

/* perm: one 1024-bit permutation */

static int shift[MARACA_LEN] = {14,55,61,35,30,60,32,49,16,4,42,5,26,11,47,17};
static int map[MARACA_LEN] = {2,12,8,3,1,15,11,0,14,5,13,7,9,4,10,6};

static void perm(u8 *x)
{
  int i;
  u8 y[MARACA_LEN];

#ifdef TRACE_INTERMEDIATE_VALUES
  printf("Before permutation %d\n", display_count);
  for (i=0; i<MARACA_LEN; ++i)
  {
    printf("%.16llx ", x[i]);
    if ((i%4) == 3) printf("\n");
  }
  printf("\n");
#endif /* TRACE_INTERMEDIATE_VALUES */

  /* do 128 8-bit mixes */
  eight( x, y);          /* mix the even bits of all 64 chunks */
  eight( &x[1], &y[1]);  /* mix the odd bits of all 64 chunks */

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

  /* rotate the output bits among the 64 chunks */
  for (i=0; i<MARACA_LEN; ++i) 
  {
    y[i] = (y[i] << shift[i]) | (y[i] >> (64-shift[i]));
  }

  /* shuffle the 16 output bits within each chunk */
  for (i=0; i<MARACA_LEN; ++i) 
  {
    x[map[i]] = y[i];
  }

#ifdef TRACE_INTERMEDIATE_VALUES
  printf("After permutation %d\n", display_count++);
  for (i=0; i<MARACA_LEN; ++i)
  {
    printf("%.16llx ", x[i]);
    if ((i%4) == 3) printf("\n");
  }
  printf("\n");
#endif /* TRACE_INTERMEDIATE_VALUES */
}



/* The full hash */


/* do_combine: XOR something to the internal state */
static void do_combine( const u8 *thing, u8 *hash)
{
  int k;

#ifdef TRACE_INTERMEDIATE_VALUES
  printf("Combining data block\n");
  for (k=0; k<MARACA_LEN; ++k)
  {
    printf("%.16llx ", ((u8 *)thing)[k]);
    if ((k%4) == 3) printf("\n");
  }
  printf("\n");
#endif /* TRACE_INTERMEDIATE_VALUES */

  for (k=0; k<MARACA_LEN; ++k) 
  {
    hash[k] ^= thing[k];
  }
}


/* accumulate: add a block to its second, third, fourth accumulators */
#define SECOND 21
#define THIRD  41
#define FOURTH 46
void accumulate( u8 a[MARACA_ACCUM][MARACA_LEN],
                 const u8 *block,
                 int i)
{
  u8 *fourth = a[(i + FOURTH) % MARACA_ACCUM];
  u8 *third  = a[(i + THIRD - 6*((i+2)%4)) % MARACA_ACCUM];
  u8 *second = a[(i + SECOND - 6*(i%4)) % MARACA_ACCUM];
  int k;
  
  for (k=0; k<MARACA_LEN; ++k) 
  {
    u8 val = block[k];
    fourth[(k+12) % MARACA_LEN]  = val;
    third [(k+ 6) % MARACA_LEN] ^= val;
    second[(k+ 2) % MARACA_LEN] ^= val;
  }
}



/* one combine: add a data block, perm, and an accumulator, perm perm */
static void one_combine( u8 a[MARACA_ACCUM][MARACA_LEN],
                         int *i,
                         u8 *hash,
                         const u8 *block)
{
  accumulate( a, block, *i);
  do_combine( block, hash);
  perm( hash);
  do_combine( a[(*i) % MARACA_ACCUM], hash);
  perm( hash);
  perm( hash);
  *i += 1;
  if (*i == 4*MARACA_ACCUM) 
  {
    /* both i%4 and i%47 are used */
    *i = 0;
  }
}



/* Init: initialize the hash */
HashReturn Init( hashState *state,
		 int hashbitlen) 
{
  int i;

#ifdef TRACE_INTERMEDIATE_VALUES
  display_count = 0;
#endif

  if (hashbitlen > BITS_PER_BLOCK || (hashbitlen % 8) != 0) 
  {
    return BAD_HASHBITLEN;
  }

  state->hashbitlen = hashbitlen;
  state->keybitlen = 0;
  state->offset = 0;
  state->length = 0;
  memset( state->hash, 0, BYTES_PER_BLOCK);
  memset( state->key, 0, BYTES_PER_BLOCK);
  memset( state->a, 0, sizeof(state->a));
  state->running = 1;
  return SUCCESS;
}




/* Update: update the hash with a bit array */
/* Update must follow an Init or another Update */
HashReturn Update( hashState *state, 
		   const BitSequence *data, 
		   DataLength databitlen)
{
  unsigned int start = state->length % BITS_PER_BLOCK;
  size_t stop;
  size_t dataoff = 0;

  if (!state->running) 
  {
    return BAD_STATE;
  }

  if ((start % 8) != 0)
  {
    return BAD_PREVIOUS_DATABITLEN;
  }

  /* get started */
  state->length += databitlen;
  if (start != 0) 
  {
    if (databitlen + start < BITS_PER_BLOCK) 
    {
      memcpy( &((char *)state->buf)[bytes(start)], data, bytes(databitlen));
      return SUCCESS;
    }
    else
    {
      unsigned int piece = (BITS_PER_BLOCK-start)/8;
      memcpy( &((char *)state->buf)[bytes(start)], data, piece);
      one_combine( state->a, &state->offset, state->hash, state->buf);
      data = &data[piece];
      databitlen -= piece;
    }
  }

  /* loop: handle a whole block at a time */
  stop = (databitlen / BITS_PER_BLOCK) * BYTES_PER_BLOCK;
  for (dataoff = 0; dataoff < stop; dataoff += BYTES_PER_BLOCK)
  {
    memcpy( state->buf, &((char *)data)[dataoff], BYTES_PER_BLOCK);
    one_combine( state->a, &state->offset, state->hash, state->buf);
  }

  /* remember the last partial block */
  memcpy( state->buf, &((char *)data)[stop], bytes(databitlen) - stop);

  return SUCCESS;
}




/* InitWithKey: initialize the hash with a key */
HashReturn InitWithKey( hashState *state,
			int hashbitlen, 
			const BitSequence *key,
			int keybitlen)
{
  if (keybitlen > BITS_PER_BLOCK || (keybitlen % 128) != 0)
  {
    return BAD_KEYBITLEN;
  }
  if (Init( state, hashbitlen)) return FAIL;
  state->keybitlen = keybitlen;
  memcpy(state->key, key, bytes(keybitlen));
  if (Update( state, (const BitSequence *)state->key, keybitlen)) return FAIL;
  return SUCCESS;
}



/* Final: hash the last piece, the key and length, then report the result */
HashReturn Final( hashState *state, 
		  BitSequence *hashval)
{
  int i;
  int fraction = state->length % 8;
  u8  zero[MARACA_LEN];
  int pad = 0;
  unsigned short int lengths;  /* a 2-byte unsigned integer */

  if (!state->running) 
  {
    return BAD_STATE;
  }

  /* pad the last partial block to a 1-byte boundary */
  if (fraction != 0)
  {
    int last = (state->length % BITS_PER_BLOCK)/8;
    fraction = 8-fraction;

    /* clear the unused bits of the last used byte */
    ((char *)state->buf)[last] &= ~(char)((1 << fraction) - 1);
    state->length += fraction;

    if (last == BYTES_PER_BLOCK-1)
    {
      one_combine( state->a, &state->offset, state->hash, state->buf);
    }
  }

  /* Update with the key again */
  if (state->keybitlen != 0)
  {
    Update( state, (BitSequence *)state->key, state->keybitlen);
  }

  /* Update with the keybitlen and zero-padded fraction length, and a 1 */
  lengths = 16*state->keybitlen + 2*fraction + 1;     
  Update( state, (BitSequence *)&lengths, 16);

  /* finish padding the last partial block */
  pad = (state->length % BITS_PER_BLOCK)/8;
  if (pad != 0)
  {
    pad = BYTES_PER_BLOCK-pad;
    memset( &((char *)state->buf)[BYTES_PER_BLOCK-pad], 0, pad);
    one_combine( state->a, &state->offset, state->hash, state->buf);
  }

  /* use up the accumulators */
  /* XOR an all-zero block for blocks beyond the end of the message */
  memset( zero, 0, BYTES_PER_BLOCK);
  for (i=1; i<=FOURTH; ++i)
  {
    one_combine( state->a, &state->offset, state->hash, zero);
  }

  /* do 30 strengthening permutations after the last real block use */
  for (i=2; i<30; ++i) 
  {
    perm( state->hash);
  }

  /* report the final state */
  memcpy( hashval, state->hash, bytes(state->hashbitlen));

  state->running = 0;
  return SUCCESS;
}




HashReturn Hash( int hashbitlen,          /* length of hashval, in bits */
		 const BitSequence *data, /* array of bytes to hash */
		 DataLength databitlen,   /* length of the data, in bits */
		 BitSequence *hashval)    /* 128-byte hash value */
{
  hashState state;

  if (Init( &state, hashbitlen)) return FAIL;
  if (Update( &state, data, databitlen)) return FAIL;
  if (Final( &state, hashval)) return FAIL;
  return SUCCESS;
}



#ifdef SELF_TEST

int main()
{
  int hashbitlen = 1024;
  hashState   state;
  u8 hashbuf[MARACA_LEN];
  BitSequence *hashval = (BitSequence *)hashbuf;
  BitSequence buf[1<<16];
  int i;
  u8 starttime;
  u8 endtime;

  u8 key[MARACA_LEN];
  memset( key, 0, BYTES_PER_BLOCK);
  memset( buf, 42, sizeof(buf));

  /* hash the empty string once */
  if (1)
  {
    DataLength databitlen = 0;
    printf( "Hash the empty string once:\n");
    Hash( hashbitlen, buf, databitlen, hashval);
    printf( "Message digest for the empty string:\n");
    for (i=0; i<MARACA_LEN; ++i)
    {
      printf( "%.16llx ", ((u8 *)hashbuf)[i]);
      if ((i%4) == 3) printf("\n");
    }
    printf( "\n");
  }

  /* hash one block */
  if (1)
  {
    DataLength databitlen = 8*(1<<7);
    printf( "Hash one block:\n");
    Hash( hashbitlen, buf, databitlen, hashval);
    printf( "Message digest for one block:\n");
    for (i=0; i<MARACA_LEN; ++i)
    {
      printf( "%.16llx ", ((u8 *)hashbuf)[i]);
      if ((i%4) == 3) printf("\n");
    }
    printf( "\n");
  }

  /* hash two blocks */
  if (1)
  {
    DataLength databitlen = 2*8*(1<<7);
    printf( "Hash two blocks:\n");
    Hash( hashbitlen, buf, databitlen, hashval);
    printf( "Message digest for two blocks:\n");
    for (i=0; i<MARACA_LEN; ++i)
    {
      printf( "%.16llx ", ((u8 *)hashbuf)[i]);
      if ((i%4) == 3) printf("\n");
    }
    printf( "\n");
  }

  /* hash the empty string 2^^16 times */
  if (1)
  {
    DataLength databitlen = 0;
    printf( "time for empty string 2^^16 times:\n");
    starttime = GetTickCount();
    for (i=0; i<(1<<16); ++i)
    {
      Hash( hashbitlen, buf, databitlen, hashval);
    }
    endtime = GetTickCount();
    printf( "   %d millisecond\n", endtime-starttime);
    for (i=0; i<MARACA_LEN; ++i)
    {
      printf( "%.16llx ", ((u8 *)hashbuf)[i]);
      if ((i%4) == 3) printf("\n");
    }
    printf( "\n");
  }


  /* Do a single hash of 2^^30 bytes */
  /* Update the hash with a single 1<<16 byte buffer 1<<14 times */
  if (1)
  {
    DataLength databitlen = 8*(1<<16);  /* length in bits */
    printf( "time for 2^^30 bytes:\n");
    starttime = GetTickCount();
    InitWithKey( &state, hashbitlen, (BitSequence *)key, 1024);
    for (i=0; i < (1<<30)/bytes(databitlen); ++i)
    {
      Update( &state, buf, databitlen);
    }
    Final( &state, hashval);
    endtime = GetTickCount();
    printf( "   %d millisecond\n", (unsigned int)(endtime-starttime));
    for (i=0; i<MARACA_LEN; ++i)
    {
      printf( "%.16llx ", ((u8 *)hashbuf)[i]);
      if ((i%4) == 3) printf("\n");
    }
    printf( "\n");
  }
    
  printf( "size of state: %d\n", sizeof(hashState));
}

#endif /* SELF_TEST */