#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void * memcpy ( void * destination, const void * source, size_t num );

#ifdef NOPRINT
#define printf(...) ;
#endif

#define UNDEF -1
//#define PRESENT
#ifndef PRESENT
#define DESL
#endif

#ifdef DESL
#define KIN 6
#define KOUT 4
#define NUMIN 64
#define NUMOUT 16
#define MAXDIFFTAB maxdifftabDESL
#define MAXLINTAB  maxlintabDESL
#endif
#ifdef PRESENT
#define KIN 4
#define KOUT 4
#define NUMIN 16
#define NUMOUT 16
#define MAXDIFFTAB maxdifftabPRESENT
#define MAXLINTAB  maxlintabPRESENT
#endif

#ifdef NUMIN
#else
#error
#endif

// Type for an s-box
typedef int sbox[NUMIN];

// Type for a table (differential or linear)
typedef int tab[NUMIN][NUMOUT];

struct poswithpenalty {
  int pos;
  double penalty;
};

#if NUMIN==64 
   sbox dess5 = {2,14,12,11,4,2,1,12,7,4,10,7,11,13,6,1,8,5,5,0,3,15,15,10,13,3,0,9,14,8,9,6,4,11,2,8,1,12,11,7,10,1,13,14,7,2,8,13,15,6,9,15,12,0,5,9,6,10,3,4,0,5,14,3};
   sbox desl = {14, 5, 5, 0, 7, 8, 2, 15, 11, 14, 8, 3, 1, 2, 15, 12, 0, 11, 10, 7, 9, 6, 4, 9, 6, 13, 13, 4, 12, 1, 3, 10, 4, 9, 9, 6, 2, 15, 14, 5, 8, 3, 7, 8, 13, 4, 0, 11, 10, 7, 12, 1, 15, 12, 1, 2, 5, 0, 11, 14, 3, 10, 6, 13};
#endif
#if NUMIN==16
  sbox present = { 12, 5, 6, 11, 9, 0, 10, 13, 3, 14, 15, 8, 4, 7, 1, 2 };
#endif

/* General helpers */
// Computes the hamming weight of val
// Better: http://en.wikipedia.org/wiki/Hamming_weight
int hamming(int val) {
  int akt;
  int res;

  akt = val;
  res = 0;
  while(akt != 0) {
    res = res + (akt&1);
    akt >>= 1;
  }

  return(res);
}

// Computes the scalar product of v1 and v2
int sprod(int v1, int v2) {
  return(hamming(v1&v2));
}

/* S-BOX HELPER FUNCTIONS */
// Initializes an s-box as everywhere undefined
void initsbox(sbox s) {
  int i;

  for(i = 0; i < NUMIN; i++) {
    s[i] = UNDEF;
  }
}

// Prints an s-box
void printsbox(sbox s) {
  int i;

  for(i = 0; i < NUMIN; i++) {
    if(s[i] == UNDEF) {
      printf("-");
    } else {
      printf("%1X", s[i]);
    }
    if(i%16==15) {
      printf(" ");
    } 
  }
  printf("\n");
}

// Copies s1 into s2
void Xsboxcopy(sbox s1, sbox s2) {
  int i;

  for(i = 0; i < NUMIN; i++) {
    s2[i] = s1[i];
  }
}

#define sboxcopy(s1,s2) memcpy( (void*)s2, (void*)s1, (size_t)sizeof(sbox) );

// Counts the number of undefined places in an s-box
inline int countUNDEF(sbox s) {
  int x;
  int res;

  res = 0;
  for(x = 0; x < NUMIN; x++) {
    if(s[x] == UNDEF) {
      res++;
    }
  }

  return(res);
}

/**************************/
/* TABLE HELPER FUNCTIONS */
/**************************/

// Initializes t componentwise with initval
void inittab(tab t, int initval) {
  int i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      t[i][j] = initval;
    }
  }
}

// Prints t
void printtab(tab t) {
  int i, j;

  printf("     ");
  for(j = 0; j < NUMOUT; j++) {
    printf(" %02X ", j);
  }
  printf("\n");
  for(i = 0; i < NUMIN; i++) {
    printf("%02X | ", i);
    for(j = 0; j < NUMOUT; j++) {
      printf("%+03d ", t[i][j]);
    }
    printf("\n");
  }  
}

// Checks if t1 is componentwise equal to t2
int tabeq(tab t1, tab t2) {
  int i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(t1[i][j] != t2[i][j]) {
	return(0);
      }
    }
  }

  return(1);
}

// Copies t1 into t2
void Xtabcopy(tab t1, tab t2) {
  int i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      t2[i][j] = t1[i][j];
    }
  }
}

// using tabcopy instead of Xtabcopy makes it 3 times faster!!!
#define tabcopy(t1,t2) memcpy( (void*)t2, (void*)t1, (size_t)sizeof(tab) )

// Checks if t1 is componentwise lower or equal to t2
int tableq(tab t1, tab t2) {
  int i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(t1[i][j] > t2[i][j]) {
	return(0);
      }
    }
  }
  return(1);
}
int tababsleq(tab t1, tab t2) {
  int i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(abs(t1[i][j]) > t2[i][j]) {
	return(0);
      }
    }
  }
  return(1);
}
int tababsmaxovershoot(tab t1, tab t2) {
  int m, c, i, j;

  m=-NUMOUT;
  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      c = abs(t1[i][j]) - t2[i][j];
      if(c>m) m=c;
    }
  }
  return(m);
}
int istababsmaxovershoot(tab t1, tab t2, int lmt) {
  int  c, i, j;

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if( abs(t1[i][j]) - t2[i][j] > lmt ) return(1);
    }
  }
  return(0);
}


/* DIFFERENTIAL STUFF */
// DUMBEST METHOD EVER = DEFINITION
void difftabDUMB(sbox s, tab res) {
  int dx, dy, x;

  for(dx = 0; dx < NUMIN; dx++) {
    for(dy = 0; dy < NUMOUT; dy++) {
      res[dx][dy] = 0;
      for(x = 0; x < NUMIN; x++) {
        if(s[x] != UNDEF && s[x^dx] != UNDEF) {
          if((s[x]^s[x^dx]) == dy) {
	    res[dx][dy]++;
	  }
	}
      }
    }
  }
}

// Computes the differential table for s-box s and stores the result in res
void difftab(sbox s, tab res) {
  int dx, dy, x;

  inittab(res,0);
  for(x = 0; x < NUMIN; x++) {
    for(dx = 0; dx < NUMIN; dx++) {
      if(s[x] != UNDEF && s[x^dx] != UNDEF) {
        res[dx][s[x]^s[x^dx]]++;
      }
    }
  }
}

// Computes the differential table for s-box s with additional value s[x0] = y0 
// given the differential table res for the s-box s and stores the result in res
void difftabAcc(sbox s, int x0, int y0, tab dtab) {
  int dx,dy;

  dtab[0][0]++;
  for(dx = 1; dx < NUMIN; dx++) {
    dy=s[x0^dx];
    if(dy != UNDEF)
      dtab[dx][y0^dy] += 2;
  }
}

// Incorrect procedure that should undo the changes of difftabAccum
void difftabUnacc(sbox s, int x0, int y0, tab dtab) {
  int dx,dy;

  for(dx = 0; dx < NUMIN; dx++) {
    dy=s[x0^dx];
    if(dy != UNDEF)
      dtab[dx][y0^dy] -= 2;
  }
}

// Stores the maximal admissible differential table in res
void maxdifftabPRESENT(tab res) {
  int i,j;

  // diff_S(dx,dy) <= 4
  inittab(res, 4);

  // Trivial
  res[0][0] = NUMIN;
  for(j = 1; j < NUMOUT; j++) {
    res[0][j] = 0;
  }
  // Force injective
  for(i = 1; i < NUMIN; i++) {
    res[i][0] = 0;
  }

  // diff_S(dx,dy) = 0 for wt(dx) = wt(dy) = 1.
  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(hamming(j) == 1) {
	if(hamming(i) == 1) {
	  res[i][j] = 0;
	}
      }
    }
  }
}

// Stores the maximal admissible differential table in res
void maxdifftabDESL(tab res) {
  int i,j;

  /* S-7 */
  inittab(res, 16);

  /* Trivial */
  res[0][0] = 64;
  for(j = 1; j < NUMOUT; j++) {
    res[0][j] = 0;
  }

  /* S-3 */
  for(i = 1; i < 16; i++) {
    res[2*i][0] = 0;
  }

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(hamming(j) <= 1) {
	/* S-4 */
	if(hamming(i) == 1) {
	  res[i][j] = 0;
	}
	/* S-5 */
	if(i == 12) {
	  res[i][j] = 0;
	}
      }
    }
  }

  /* C1 */
  for(i = 0; i < 8; i++) {
    res[32+4*i][0] = 0;
  }
}

// Test whether adding x0->y0 to s still fits with t1<t2
inline int nextdifftableq( tab t1, tab t2, sbox s, int x0, int y0 ){
  int dx, dy;
  for(dx = 0; dx < NUMIN; dx++) {
    dy=s[x0^dx];
    if(dy != UNDEF) {
      dy^=y0;
      if (t1[dx][dy]+2 > t2[dx][dy]) return(0);
    }
  }
  return(1);
}
// Computes the list and number of admissible options 
inline void OLDcomputeoptions(
			   sbox s,
			   tab maxdtab,
			   tab dtab,
			   int x0,
			   int* res,
			   int* num) {
  int c,y0;
  tab dtabbak;

  c= 0;
  for(y0 = 0; y0 < NUMOUT; y0++) {
    tabcopy(dtab, dtabbak);
    difftabAcc(s, x0, y0, dtabbak);
    if(tableq(dtabbak, maxdtab)) {
      res[c++] = y0; }
    /*
      printf("x0=%d, y0=%d, leq=%d, next=%d\n",
	   x0, y0,
	   tableq(dtabbak,maxdtab),
	   nextdifftableq(dtab,maxdtab,s,x0,y0)
	   );//*/
  }
  *num = c;
}
inline void computeoptions(
			   sbox s,
			   tab maxdtab,
			   tab dtab,
			   int x0,
			   int* res,
			   int* num) {
  int c,y0;

  c= 0;
  for(y0 = 0; y0 < NUMOUT; y0++) {
    if (nextdifftableq(dtab,maxdtab,s,x0,y0))
      res[c++] = y0;
  }
  *num = c;
}

/* LINEAR STUFF */
// Computes the linear table for s-box s and stores the result in res
void lintab(sbox s, tab res) {
  int alpha, beta, x;
 
  for(alpha = 0; alpha < NUMIN; alpha++) {
    for(beta = 0; beta < NUMOUT; beta++) {
      res[alpha][beta] = 0;
      for(x = 0; x < NUMIN; x++) {
        if(s[x] != UNDEF) {
	  if((sprod(beta,s[x])&1) == ((sprod(alpha,x))&1)) {
	    res[alpha][beta]++;
	  } else {
	    res[alpha][beta]--;
	  }
	}
      }
    }
  }
}

// Computes the linear table for s-box s with additional value s[x0] = y0 
// given the linear table res for the s-box s and stores the result in res
void XlintabAcc(sbox s, int x0, int y0, tab ltab) {
  int alpha, beta, x;
 
  for(alpha = 0; alpha < NUMIN; alpha++) {
    for(beta = 0; beta < NUMOUT; beta++) {
      if((sprod(y0,beta)&1) == ((sprod(x0,alpha))&1)) {
	ltab[alpha][beta]++;
      } else {
	ltab[alpha][beta]--;
      }
    }
  }
}
void lintabAcc(sbox s, int x0, int y0, tab ltab) {
  int alpha, beta, a, x;
  int A[NUMIN];
  int B[NUMOUT];
 
  for(alpha = 0; alpha < NUMIN; alpha++) A[alpha] = sprod(x0,alpha)&1;
  for(beta = 0; beta < NUMOUT; beta++) B[beta] = sprod(y0,beta)&1;
  for(alpha = 0; alpha < NUMIN; alpha++) {
    a = A[alpha];
    for(beta = 0; beta < NUMOUT; beta++) {
      if(B[beta] == a) {
	ltab[alpha][beta]++;
      } else {
	ltab[alpha][beta]--;
      }
    }
  }
}
void YlintabAcc(sbox s, int x0, int y0, tab ltab) {
  int alpha, beta, a, x;
  int A[NUMIN], *pA;
  int B[NUMOUT], *pB;
 
  for(alpha = 0; alpha < NUMIN; alpha++) A[alpha] = sprod(x0,alpha)&1;
  for(beta = 0; beta < NUMOUT; beta++) B[beta] = sprod(y0,beta)&1;
  for(alpha = 0, pA=(int*)A; alpha < NUMIN; alpha++, pA++) {
    a = *pA;
    for(beta = 0, pB=(int*)B; beta < NUMOUT; beta++, pB++) {
      if(*pB == a) {
	ltab[alpha][beta]++;
      } else {
	ltab[alpha][beta]--;
      }
    }
  }
}

// Undo the computations in the linear table for s-box s with additional value s[x0] = y0 
// given the linear table res for the s-box s. Stores the result in res.
void lintabUnacc(sbox s, int x0, int y0, tab ltab) {
  int alpha, beta, x;
 
  for(alpha = 0; alpha < NUMIN; alpha++) {
    for(beta = 0; beta < NUMOUT; beta++) {
      if((sprod(y0,beta)&1) == ((sprod(x0,alpha))&1)) {
	ltab[alpha][beta]--;
      } else {
	ltab[alpha][beta]++;
      }
    }
  }
}

// Stores the maximal admissible bias table in res
void maxlintabPRESENT(tab res) {
  int i,j;

  /* C2 */
  inittab(res, 8);

  /* bias_S(a,b) <= 1/4 for wt(a) = wt(b) = 1. */
  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      if(hamming(i) == 1 && hamming(j) == 1) {
	res[i][j] = 4;
      }
    }
  }

  /* trivial */
  res[0][0] = NUMIN;
  for(i = 1; i < NUMIN; i++) {
    res[i][0] = 0;
  }
}

/* Stores the maximal admissible bias table in res */
void maxlintabDESL(tab res) {
  int i,j;

  /* C2 */
  inittab(res, 28);

  for(i = 0; i < NUMIN; i++) {
    for(j = 0; j < NUMOUT; j++) {
      /* C4 */
      if(hamming(i) <= 2 && hamming(j) <= 2) {
	res[i][j] = 16;
      }

      /* C3 */
      if(hamming(i) == 1 && hamming(j) == 1) {
	res[i][j] = 4;
      }
    }
  }

  /* C6 */
  for(j = 0; j < NUMOUT; j++) {
    if(hamming(j) == 1) {
      res[2][j] = 0;
      res[16][j] = 0;
    }
  }

  /* C8 */
  res[4][4] = 0;

  /* trivial */
  res[0][0] = 64;

  for(i = 1; i < NUMIN; i++) {
    res[i][0] = 0;
  }

  for(j = 1; j < NUMOUT; j++) {
    res[0][j] = 0;
    res[1][j] = 0;
    res[32][j] = 0;
    res[33][j] = 0;
  }
}

int additional_linear_conditions( tab ltab ) {
  int i,a,b1,j,b2;
  /* C5 */
  for(i = 0; i < KIN; i++ ) {
    a = 1<<i;
    for(b1 = 0; b1 < NUMOUT; b1++ ) {
      for(j = 0; j < KOUT; j++ ) {
	b2 = b1 ^ (1<<j);
	if (abs( ltab[a][b1] * ltab[a][b2] ) > 240) {
          return(0);
	}
      }
    }
  }
  /* C7 */
  a = 2;
  for(b1 = 0; b1 < NUMOUT; b1++ ) {
    for(j = 0; j < KOUT; j++ ) {
      b2 = b1 ^ (1<<j);
      if (ltab[a][b1]!=0 && ltab[a][b2]!=0) {
	return(0);
      }
    }
  }
  return(1);
}

// Computes a heuristical value that describes the quality of a linear table ltab
// with respect to a maximal one 
double computepenalty(tab ltab, tab maxltab) {
  int alpha, beta;
  int tmp;

  double res;
 
  res = 0;
  for(alpha = 0; alpha < NUMIN; alpha++) {
    for(beta = 0; beta < NUMOUT; beta++) {
      tmp = abs(ltab[alpha][beta])-maxltab[alpha][beta];
      //tmp += tmp;
      res += ldexp( 1.0, tmp );
      res--;
    }
  }
  // add small random value to make all penalties different
  res += (rand()&0x3FF) * 0.0000009765625;
 
  return(res);
}

/* Array helper */

// Comparison function of two poswithpenalty elements wrt. the double stored in there
int comparePoswithpenalty(const void *p1, const void *p2) {
  struct poswithpenalty* s1;
  struct poswithpenalty* s2;
  double d;

  s1 = (struct poswithpenalty*) p1;
  s2 = (struct poswithpenalty*) p2;
  d = s1->penalty - s2->penalty;
  return((d>0) - (d<0));
}


// Prints nicely a poswithpenalty struct
void printPoswithpenalty(struct poswithpenalty p1) {
  printf("(%d, %f)", p1.pos, p1.penalty);
}

// backtracking procedure. Gets an s-box s and a new assignment s[x0] = y0 as well as all
// necessary tables to find an s-box that fulfills the requirements stated by maxdtab and 
// maxltab. 

double nodefrac = 1.0;
double treefrac = 0.0;
int backtrackcnt = 0;
int ends = 0;
int bottoms1 =0;
int bottoms2 =0;
int bottoms3 =0;
int backtrack(int x0, int y0, tab maxdtab, tab maxltab, tab actdtab, tab actltab, sbox s) {
  int numUNDEF;
  int x1, y1;
  int i;
  
  int j;
  
  int numoptions;
  int options[NUMOUT];
  struct poswithpenalty penalties[NUMOUT];

  double minpenalty;

  int alloptions[NUMIN][NUMOUT];
  int numoptionslist[NUMIN];

  int bestnumoptions;
  int numbestx;
  int listbestx[NUMIN];

  int randpos;

  sbox sbak;
  tab dtabbak, ltabbak;

  int backtrackok;

  double treefracprev, nodefracprev;

  backtrackcnt++;

  if(y0 != UNDEF) {
    //printf("Setting S[%02X] = %X\n", x0, y0);
    lintabAcc(s, x0, y0, actltab);
    difftabAcc(s, x0, y0, actdtab);
    s[x0] = y0;
  }

  numUNDEF = countUNDEF(s);

#ifdef DEBUGTM
  if(backtrackcnt>9999) {
    printf("%8d L%3d: Abort %.3e at %.12f of tree..\n",
	   backtrackcnt, numUNDEF, nodefrac, treefrac );
    return(1);
  }
#endif

  //printf("Number of undefined places is %d\n", numUNDEF);

  if(numUNDEF == 0) {
    printf("%8d L%3d: Complete %.3e at %.12f of tree..\n",
	   backtrackcnt, numUNDEF, nodefrac, treefrac );
    if(!tababsleq(actltab, maxltab)) {
      bottoms1++;
      /*
      printf("BAD1: ");
      printsbox(s); //*/
      return(0);
    } 
#ifdef DESL
    else if (!additional_linear_conditions(actltab)) {
      bottoms2++;
      printf("BAD2: ");
      printsbox(s);
      return(0);
    }
#endif
    else {
      bottoms3++;
      printf("GOOD: ");
      printsbox(s);
#ifdef WHOLETREE
      return(0);
#else
      return(1);
#endif
    }
  }

#ifndef NOPURGE
  // Purge branches that cannot fulfill linear conditions any more.
  if(tababsmaxovershoot(actltab,maxltab)>numUNDEF) {
    printf("%8d L%3d: Purge %.3e at %.12f of tree.\n",
	   backtrackcnt, numUNDEF, nodefrac, treefrac );
    ends++;
    /*
    printf("BAD : ");
    printsbox(s);
    //*/
    fflush(stdout);
    return(0);
  }
#endif

  bestnumoptions = NUMIN+1;
      
  for(x1 = 0; x1 < NUMIN; x1++) {
    if(s[x1] == UNDEF) {
      computeoptions(s, maxdtab, actdtab, x1, options, &numoptions);

      numoptionslist[x1] = numoptions;
      for(j = 0; j < numoptions; j++) {
	alloptions[x1][j] = options[j];
      }

      if(numoptions == 0) {
	//printf("FAIL: No options left for S[%02X]. Backtracking.\n", x1);
	return(0);
      }

      /*
      printf("Can pick S[%02X] in {", x1);
      for(i = 0; i < numoptions; i++) {
	y1 = options[i];
	printf("%d", y1);
	if(i < numoptions-1) {
	  printf(", ");
	} else {
	  printf("}\n");
	}
      }
      //*/

      if(numoptions < bestnumoptions) {
	numbestx = 0;
	bestnumoptions = numoptions;
      }
      
      if(numoptions == bestnumoptions) {
	listbestx[numbestx++] = x1;
      }
    }
  }

#ifdef DETERMINEXS
  randpos = 0;
#else
  randpos = ((int) rand())%numbestx;
#endif
  x1 = listbestx[randpos];
  //printf("Selected x0 = %X, sorting options by penalty...\n", x1);

  for(i = 0; i < bestnumoptions; i++) {
    y1 = alloptions[x1][i];
    tabcopy(actltab, ltabbak);
    lintabAcc(s, x1, y1, ltabbak);
    
    penalties[i].pos = y1;
    penalties[i].penalty = computepenalty(ltabbak, maxltab);

    //lintabUnacc(s, x1, y1, actltab);
    //tabcopy(ltabbak, actltab);
  }
  
  qsort(penalties, bestnumoptions, (size_t) sizeof(struct poswithpenalty), comparePoswithpenalty);
  
  if (numUNDEF>NUMIN-16 || numUNDEF<8) {
    printf("%8d L%3d: Try S[%02X] in{ ", backtrackcnt, numUNDEF, x1 );
    for(i = 0; i < bestnumoptions; i++)
      printf("%1X (%+.3f), ", penalties[i].pos, penalties[i].penalty );
    printf("\b\b }...\n");
    fflush(stdout);
  }

  treefracprev = treefrac;
  nodefracprev = nodefrac;
  nodefrac = nodefrac / bestnumoptions;
  for(i = 0; i < bestnumoptions; i++) {
    y1 = penalties[i].pos;

    //printf("Trying S[%02X] = %X...\n", x1, y1);
    sboxcopy(s,sbak);
    tabcopy(actdtab, dtabbak);
    tabcopy(actltab, ltabbak);

    backtrackok = backtrack(x1, y1, maxdtab, maxltab, actdtab, actltab, s);
    treefrac += nodefrac;

    if(backtrackok) {
      return(1);
    } else {
      sboxcopy(sbak,s);
      tabcopy(dtabbak, actdtab);
      tabcopy(ltabbak, actltab);      
    }
  }
  nodefrac = nodefracprev;
  treefrac = treefracprev + nodefracprev;

  //printf("SEARCH FAILED\n");
  return(0);
}


void find_sbox() {
  tab maxdtab, maxltab, actltab,actdtab;
  sbox s;
  int x0, y0;

  printf("**********************************************\n");
  printf("*** Hello! Starting search for an s-box... ***\n");
  printf("**********************************************\n\n");

  printf("Computing the Coppersmith/Poschmann bounds...\n");
  MAXDIFFTAB(maxdtab);
  MAXLINTAB(maxltab);
  printf("Done.\n");

  printf("Generating a partially empty s-box...\n");
  initsbox(s);

  inittab(actltab, 0);
  inittab(actdtab, 0);

#ifdef TESTDESL
  //*// use partial values from desl S-box
  for(x0 = TESTDESL; x0 < NUMIN; x0++) {
    y0 = desl[x0];
    difftabAcc(s, x0, y0, actdtab);
    lintabAcc(s, x0, y0, actltab);
    s[x0] = y0;
  }
  //*/
#endif

  printf("**********************************************\n");
  printf("STARTING SEARCH...\n");
  backtrack(0, UNDEF, maxdtab, maxltab, actdtab, actltab, s);
  printf("**********************************************\n");

  difftab(s, actdtab);
  lintab(s, actltab);

  if(tableq(actdtab, maxdtab)) {
    printf("Differential properties OK!\n");
  } else {
    printf("Violation of the differential properties :(\n");
  }
  if(tababsleq(actltab, maxltab)) {
    printf("Linear properties OK!\n");
  } else {
    printf("Violation of the linear properties :(\n");
  }
  if(additional_linear_conditions(actltab)) {
    printf("Additional linear properties OK!\n");
  } else {
    printf("Violation of the additional linear properties :(\n");
  }
  printf("Ciao (after %d backtrack calls, %d ends, %d,%d,%d bottoms).\n",
	 backtrackcnt, ends, bottoms1, bottoms2, bottoms3);
}

int main(int argc, char *argv[]) {
  int seed;
  
  if(argc>1) {
    if (sscanf(argv[1],"%d",&seed)==1)
      seed;
    else
      seed = time(NULL);
    srand(seed);
    printf("Setting random seed = %d.\n", seed );
  } else
    printf("No valid input found. Using default random init...\n");
  find_sbox();
}