/*
 * Copyright (c) 2008 Sebastiaan Indesteege
 *                              <sebastiaan.indesteege@esat.kuleuven.be>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

/*
 * Program used to determine the starting state for the LFSR used to
 * generate the constants in the Lane hash function. For every possible
 * starting state, the constants are generated, and it is verified that
 * no two bytes in the same position in different lanes are equal. As this
 * gives many solutions, it is also counted how many times a byte is the
 * one's complement of a byte in the same position in a different lane. This
 * number is minimized. Note that the program was not written with
 * efficiency in mind.
 *
 * Relevant output of the program:
 *   [... values with higher count ...]
 *   001  0x07fc703d
 *   001  0x0ff8e07a
 *   001  0x1ff1c0f4
 *   001  0x3fe381e8
 *   001  0x5cff8e07
 *   001  0x7f3fe381
 *   001  0xb9ff1c0e
 *   001  0xd3fe381f
 *   001  0xef9ff1c1
 *
 * The first starting point with count 1, i.e., 0x07fc703d is used in Lane.
 */

#include <limits.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define KMAX ((6*7+2*3)*16)
uint32_t constant[KMAX];

inline int countequalbytes (const uint32_t a, const uint32_t b)
{
  int c = 0;
  if (((a      )&0xff) == ((b      )&0xff)) ++c;
  if (((a >>  8)&0xff) == ((b >>  8)&0xff)) ++c;
  if (((a >> 16)&0xff) == ((b >> 16)&0xff)) ++c;
  if (((a >> 24)&0xff) == ((b >> 24)&0xff)) ++c;
  return c;
}

int main(int argc, char **argv)
{
  int i,j,k,l;
  uint64_t start, stop;
  int best = INT_MAX;
  int count;

  if (arcc == 1) {
    /* search whole space */
    start = 0x00000000;
    stop = 0xffffffff;
  } else if (argc == 3) {
    /* use arguments to select which points to search */
    start = strtoul(argv[1], NULL, 0);
    stop = strtoul(argv[2], NULL, 0);
  } else {
    printf("Usage: %s [<start> <stop>]\n", argv[0]);
    return 1;
  }

  do {
    /* generate constants */
    count = 0;
    constant[0] = (uint32_t) start;
    for (i=1; i!=KMAX; ++i) {
      constant[i] = constant[i-1] & 1 ? (constant[i-1] >> 1)^0xd0000001 : constant[i-1] >> 1;
    }

    /* test P-layer for Lane-256 */
    for (i=0; i!=6; ++i) /* round i */
      for (j=0; j!=8; ++j) /* column j */
        for (k=0; k!=5; ++k) /* first lane k */
          for (l=k+1; l!=6; ++l) { /* second lane l */
            if (countequalbytes(constant[8*(5*k+i)+j], constant[8*(5*l+i)+j]))
              goto next; /* we want no bytes to be equal */
            count += (countequalbytes(~constant[8*(5*k+i)+j], constant[8*(5*l+i)+j])); /* count inverted bytes */
          }

    /* test Q-layer for Lane-256 */
    for (i=0; i!=3; ++i) /* round i */
      for (j=0; j!=8; ++j) /* column j */
        for (k=0; k!=1; ++k) /* first lane k */
          for (l=k+1; l!=2; ++l) { /* second lane l */
            if (countequalbytes(constant[8*(30+2*k+i)+j], constant[8*(30+2*l+i)+j]))
              goto next; /* we want no bytes to be equal */
            count += (countequalbytes(~constant[8*(30+2*k+i)+j], constant[8*(30+2*l+i)+j])); /* count inverted bytes */
          }

    /* test P-layer for Lane-512 */
    for (i=0; i!=8; ++i) /* round i */
      for (j=0; j!=16; ++j) /* column j */
        for (k=0; k!=5; ++k) /* first lane k */
          for (l=k+1; l!=6; ++l) { /* second lane l */
            if (countequalbytes(constant[16*(7*k+i)+j], constant[16*(7*l+i)+j]))
              goto next; /* we want no bytes to be equal */
            count += (countequalbytes(~constant[16*(7*k+i)+j], constant[16*(7*l+i)+j])); /* count inverted bytes */
          }

    /* test Q-layer for Lane-512 */
    for (i=0; i!=3; ++i) /* round i */
      for (j=0; j!=16; ++j) /* column j */
        for (k=0; k!=1; ++k) /* first lane k */
          for (l=k+1; l!=2; ++l) { /* second lane l */
            if (countequalbytes(constant[16*(42+3*k+i)+j], constant[16*(42+3*l+i)+j]))
              goto next; /* we want no bytes to be equal */
            count += (countequalbytes(~constant[16*(42+3*k+i)+j], constant[16*(42+3*l+i)+j])); /* count inverted bytes */
          }

    /* success */
    if (count < best) {
      printf("%03d  0x%08x\n", count, start);
      best = count;
    }

    /* next iteration */
next:
    ++start;

  } while (start <= stop);

  return 0;
}