/*
------------------------------------------------------------------------
I've got a bunch of 16-bit permutations (that are really two copies
of the same 8-bit permutation shuffled together) that look like this:

5   8, 9,10,12,14   00001111111000011111000100001110 101
5   0, 1, 2, 4, 6   00001111111000011111000100001110 101
5   0, 1, 3, 5, 7   01011101101001000110101010010101 1340
5   0, 1, 3, 5, 7   11000011001011100011100011001011 2962
5   8, 9,11,13,15   01100101100110101010111001011000 1443
5   8, 9,11,13,15   01001001011110010001011011010110 930
5   8, 9,11,13,15   00100111000110010101101010101101 345
5   9,10,12,13,15   11000011001111001100001101101001 2983
5   8, 9,10,12,14   01011010010010111010010110110100 1179
5   1, 2, 4, 5, 7   11000011001111001100001101101001 2983
5   0, 1, 3, 5, 7   01001001011110010001011011010110 930
5   0, 1, 3, 5, 7   00100111000110010101101010101101 345
5   8, 9,11,13,15   01011101101001000110101010010101 1340
5   0, 1, 2, 4, 6   01011010010010111010010110110100 1179
5   0, 1, 3, 5, 7   01100101100110101010111001011000 1443
5   8, 9,11,13,15   11000011001011100011100011001011 2962

and NAND trees for computing each of those truth tables, like

 32  00001111111000011111000100001110  3.125000 01f 01f\n
(((2 4) ((2 3) (3 4))) ((2 (2 4)) (3 (0 1))))  
(((0 1) ((2 3) (2 4))) ((2 (0 4)) (4 (3 3))))\n
\n

There are a little under a million distinct trees.  The truth tables
all use either 3 bits, 4 bits, or 5 bits.  No 6 bit truth tables had
enough avalanche to be considered when building the permutations.

I plan to compute 64 of these permutations at once.  Really 128, since
the 16-bit permutation itself is two copies of the same 8-bit permutation.
The best way to do that is with 128-bit wide SSE3 instructions, following
those NAND trees and being careful to combine common subexpressions.

This program reads in these 16 permutations, looks up the NAND trees, and 
generates C code to compute them.  It also estimates the cost of that
C code.  The cost in software varies from permutation to permutation,
even though the cost is a constant 5 gates deep in hardware for all the
permutations being considered.
------------------------------------------------------------------------
*/

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

typedef  unsigned long long  u8;
typedef  unsigned long int   u4;
typedef  unsigned short int  u2;
typedef  unsigned char       u1;

#define HALFVAR 8
#define FULLVAR (2*HALFVAR)

/* hash a 32-bit integer to a 32-bit integer, use at least 11 bottom bits */
u4 hashint( u4 a)
{
  a = (a^0xdeadbeef) + (a<<4);
  a = a ^ (a>>10);
  a = a + (a<<7);
  a = a ^ (a>>13);
  return a;
}

typedef struct tree {
  u4 treelen;
  struct tree *next;
  char t[0];
} tree;

/* one of all possible balanced functions */
typedef struct balance {
  u4 loglen;  /* loglen of truth table, number of variables in function */
  u4 truth;  /* truth table for this table (zero padded) */
  float avalanche;  /* how many bits does it affect on average */
  struct balance *next;
  tree *impl;
} balance;

typedef struct perm {
  balance source[FULLVAR];
  u4 mask[FULLVAR];
  float avalanche;
} perm;

/* hash table of distinct balanced functions */
typedef  struct hashtab {
  balance **tab;
  u4 length;
  u4 count;
} hashtab;

typedef enum op {
  VAL=1, NOT, AND, OR, XOR 
} op;

typedef  struct expr {
  op kind;
  u4 children;
  struct expr *child[2];
  u4 value;  /* 0..HALFVAR-1, not '0'..'0'+HALFVAR-1 */
  u8 hash;
  u4 pos;  /* position of this result in instruction array */
  struct expr *next;
} expr;

/* hash table of distinct expressions */
typedef  struct etab {
  expr **tab;
  u4 length;
  u4 count;
} etab;


/* fill in the hashes for all the expressions in a tree */
void exprhash1(expr *e) {
  u8 hash = 0xdeadbeefdeadbeefLL;
  u4 i;
  for (i=0; i<e->children; ++i) {
    /* the children commute for all our operations */
    hash += e->child[i]->hash;
  }
  hash += (hash<<10);
  hash ^= (hash>>6);
  hash += e->kind;
  hash += (hash<<10);
  hash ^= (hash>>6);
  if (e->kind == VAL) {
    hash += e->value;
    hash += (hash<<10);
    hash ^= (hash>>6);
  }
  hash += (hash<<10);
  hash ^= (hash>>6);
  hash += (hash<<10);
  hash ^= (hash>>6);
  hash += (hash<<10);
  hash ^= (hash>>6);
  hash += (hash<<10);
  hash ^= (hash>>6);
  e->hash = hash;
}

void exprhash(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    exprhash(e->child[i]);
  }
  exprhash1(e);
}

expr *exprfree(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    exprfree(e->child[i]);
  }
  free(e);
  return (expr *)0;
}

/* trees look like "(...)  (...)".  Find a point between the two groups. */
int midpoint(char *t, int treelen)
{
  u4 i;
  u4 paren = 0;
  for (i=0; i<treelen; ++i) {
    if (t[i] == '(') ++paren;
    else if (t[i] == ')') --paren;
    if (paren == 0) break;
  }
  return i;
}

void hinit(hashtab *thash, u4 length)
{
  u4 i;
  if (length & (length-1)) {
    fprintf(stderr, "length must be a power of two: %d\n", length);
    exit(1);
  }
  thash->length = length;
  thash->count = 0;
  thash->tab = (balance **)malloc(sizeof(balance *)*length);
  for (i=0; i<length; ++i) {
    thash->tab[i] = (balance *)0;
  }
}

balance *hfind(hashtab *thash, u4 key)
{
  u4 hash = hashint(key) & (thash->length-1);
  balance **walk;
  for (walk = &thash->tab[hash]; *walk; walk = &(*walk)->next) {
    if ((*walk)->truth == key) {
      return *walk;
    }
  }
  return (balance *)0;
}

void hgrow(hashtab *thash)
{
  u4 i;
  u4 len = thash->length;
  u4 mask = len-1;
  balance **oldtab = thash->tab;
  hinit(thash, len*2);
  for (i=0; i<len; ++i) {
    balance *walk;
    for (walk = oldtab[i]; walk;) {
      balance *next = walk->next;
      u4 hash = hashint(walk->truth) & mask;
      walk->next = thash->tab[hash];
      thash->tab[hash] = walk;
      walk = next;
    }
  }
  free(oldtab);
}

/* Add b to the hash tab.  Make a copy of it, don't point directly. */
void hadd(hashtab *thash, balance *b)
{
  u4 hash = hashint(b->truth) & (thash->length-1);
  balance **walk;
  balance *x;
  for (walk = &thash->tab[hash]; *walk; walk = &(*walk)->next) {
    if ((*walk)->truth == b->truth) {
      return;
    }
  }
  x = (balance *)malloc(sizeof(balance));
  x->loglen = b->loglen;
  x->truth = b->truth;
  x->impl = (tree *)0;
  x->next = thash->tab[hash];
  thash->tab[hash] = x;
  if (++thash->count > thash->length) { 
    hgrow(thash);
  }
}

void hfree(hashtab *thash)
{
  u4 i;
  for (i=0; i<thash->length; ++i) {
    while (thash->tab[i]) {
      balance *b = thash->tab[i];
      thash->tab[i] = b->next;
      while (b->impl) {
	tree *t = b->impl;
	b->impl = t->next;
	free(t);
      }
      free (b);
    }
  }
  free(thash->tab);
  thash->tab = (balance **)0;
}




void einit(etab *ehash, u4 length)
{
  u4 i;
  if (length & (length-1)) {
    fprintf(stderr, "length must be a power of two: %d\n", length);
    exit(1);
  }
  ehash->length = length;
  ehash->count = 0;
  ehash->tab = (expr **)malloc(sizeof(expr *)*length);
  for (i=0; i<length; ++i) {
    ehash->tab[i] = (expr *)0;
  }
}

expr *efind(etab *ehash, expr *e)
{
  u8 hash = e->hash & (ehash->length-1);
  expr **walk;
  for (walk = &ehash->tab[hash]; *walk; walk = &(*walk)->next) {
    if ((*walk)->hash == e->hash) {
      return *walk;
    }
  }
  return (expr *)0;
}

void egrow(etab *ehash)
{
  u4 i;
  u4 len = ehash->length;
  u4 mask = len-1;
  expr **oldtab = ehash->tab;
  einit(ehash, len*2);
  for (i=0; i<len; ++i) {
    expr *walk;
    for (walk = oldtab[i]; walk;) {
      expr *next = walk->next;
      u4 hash = walk->hash & mask;
      walk->next = ehash->tab[hash];
      ehash->tab[hash] = walk;
      walk = next;
    }
  }
  free(oldtab);
}

/* Add e to the hash tab, return 1 if it's already there */
int eadd(etab *ehash, expr *e)
{
  u4 hash = e->hash & (ehash->length-1);
  expr **walk;
  expr *x;
  for (walk = &ehash->tab[hash]; *walk; walk = &(*walk)->next) {
    if ((*walk)->hash == e->hash) {
      return 1;
    }
  }
  e->next = ehash->tab[hash];
  ehash->tab[hash] = e;
  if (++ehash->count > ehash->length) { 
    egrow(ehash);
  }
  return 0;
}

void efree(etab *ehash)
{
  free(ehash->tab);
  ehash->tab = (expr **)0;
}



/*
 * The input sometimes has 0..3 with 01e for half the tree meaning it
 * should be 1,2,3,4 instead of 0,1,2,3.  Adjust the numbers to be right.
 */
void polishtree(char *t, char *map, u4 treelen)
{
  u4 i,j,k;
  u4 x[4];
  j = map[2];
  j = (j > '9') ? 10 + j - 'a' : j - '0';
  if (map[1] == '1') j |= 16;
  for (i=0, k=0; i<5; ++i) {
    if (!(j&(1<<i))) continue;
    x[k++] = i;
  }
  for (i=0; i<treelen; ++i) {
    if (t[i] >= '0' && t[i] <= '9') {
      t[i] = x[t[i]-'0']+'0';
    }
  }
}

/*
   Trees are stored in goofive.txt and look like this:
 32  11001001101001111110001000001101  2.875000 01f 01f
(((1 3) ((1 1) (2 3))) (((0 0) (4 4)) ((2 2) (3 3))))  (((0 2) (4 (1 3))) ((1 (0 4)) (2 3)))

 */
void gettree(perm **perms, u4 count, hashtab *thash, char *filename)
{
  FILE *f;
  u4 i;
  u4 countline;
  char buf[2000];

  /* first, add all the balanced functions we care about */
  /* add their complements too */
  for (i=0; i<count; ++i) {
    u4 j;
    for (j=0; j<FULLVAR; ++j) {
      u4 k = perms[i]->source[j].truth;
      hadd(thash, &perms[i]->source[j]);
      perms[i]->source[j].truth = (~k) & ((1<<(1<<perms[i]->source[j].loglen))-1);
      hadd(thash, &perms[i]->source[j]);
      perms[i]->source[j].truth = k;
    }
  }

  /* then add all the trees implementing them */
  f = fopen(filename, "r");
  if (!f) {
    fprintf(stderr, "could not open %s\n", filename);
    exit(1);
  }

  countline = 0;
  while (fgets(buf, 2000, f)) {
    u4 len;
    char truth[128];
    char left[3];
    char right[3];
    char t[2000];
    char blank[2000];
    u4 j;
    u4 mask;
    u4 treelen;
    float avalanche;
    balance *b;
    tree *storedtree;

    /* read in one tree */
    ++countline;
    sscanf(buf, " %d", &len);
    memcpy(truth, buf+5, len);
    sscanf(buf+7+len, "%f", &avalanche);
    memcpy(left, buf+16+len, 3);
    memcpy(right, buf+20+len, 3);
    fgets(t, 2000, f); /* the tree */
    fgets(blank, 2000, f);  /* the blank line */

    /* check if we care about it */
    if (len > 32) continue;
    mask = 0;
    for (j=0; j<len; ++j) {
      if (truth[j] == '1') {
	mask |= (1<<j);
      }
    }
    b = hfind(thash, mask);
    if (!b) continue;

    /* adjust the numbers in the tree to be right */
    b->avalanche = avalanche;
    treelen = strlen(t);
    i = midpoint(t, treelen);
    polishtree(t, left, i);
    polishtree(t+i, right, treelen-i);

    /* I suppose I could just store the tree */
    storedtree = (tree *)malloc(sizeof(tree)+treelen-1);
    storedtree->next = b->impl;
    storedtree->treelen = treelen;
    memcpy(&(storedtree->t), t, treelen);
    b->impl = storedtree;
  }
}

tree *copytree(tree *t)
{
  /* copy the tree */
  tree *newtree = (tree *)malloc(sizeof(tree)+t->treelen-1);
  memcpy(&(newtree->t), t->t, t->treelen);
  newtree->treelen = t->treelen;
  return newtree;
}

/* adjust the positions in a tree according to a mask of used bits */
void adjustpos(tree *t, u4 mask)
{
  u4 map[HALFVAR];
  u4 i, j;
  for (i=0, j=0; i<HALFVAR; ++i) {
    if (mask & (1<<i)) {
      map[j++] = i;
    }
  }
  for (i=0; i<t->treelen; ++i) {
    if (t->t[i] >= '0' && t->t[i] < '0'+HALFVAR) {
      t->t[i] = '0' + map[t->t[i] - '0'];
    }
  }
}

expr *parsevar(char *t, u4 *i)
{
  expr *var = (expr *)malloc(sizeof(expr));
  var->kind = VAL;
  var->children = 0;
  var->value = t[(*i)++] - '0';
  return var;
}

expr *parsenand(char *t, u4 *i)
{
  expr *left;
  expr *right;
  expr *and;
  expr *not;
  expr *rsl;

  /* skip past the first parenthesis */
  while (t[*i] == ' ')
    ++*i;

  if (t[*i] == '(') {
    ++*i;
    left = parsenand(t, i);
    while (t[*i] == ' ')
      ++*i;
    if (t[(*i)++] != ')') printf("something's wrong\n");
  } else {
    left = parsevar(t, i);
  }

  while (t[*i] == ' ')
    ++*i;
  
  if (t[*i] == '(') {
    ++*i;
    right = parsenand(t, i);
    while (t[*i] == ' ')
      ++*i;
    if (t[(*i)++] != ')') printf("something's wrong\n");
  } else {
    right = parsevar(t, i);
  }

  and = (expr *)malloc(sizeof(expr));
  not = (expr *)malloc(sizeof(expr));
  and->kind = AND;
  and->children = 2;
  and->child[0] = left;
  and->child[1] = right;
  not->kind = NOT;
  not->children = 1;
  not->child[0] = and;
  return not;
}

expr *parsetree(tree *t)
{
  u4 i = 0;
  return parsenand(t->t, &i);
}

/* and(0 0) becomes 0 */
expr *opti1(expr *e)
{
  int i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti1(e->child[i]);
  }
  if (e->kind == AND && 
      e->child[0]->kind == VAL && 
      e->child[1]->kind == VAL &&
      e->child[0]->value == e->child[1]->value) {
    expr *var = e->child[0];
    free(e->child[1]);
    free(e);
    return var;
  }
  return e;
}

/* convert not(and(not(0) not(and(0 *)))) to 0 */
expr *opti2(expr *e)
{
  int i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti2(e->child[i]);
  }
  if (e->kind == NOT && 
      e->child[0]->kind == AND && 
      e->child[0]->child[0]->kind == NOT &&
      e->child[0]->child[1]->kind == NOT) {
    expr *left = e->child[0]->child[0]->child[0];
    expr *right = e->child[0]->child[1]->child[0];
    if (left->kind == VAL &&
	right->kind == AND &&
	((right->child[0]->kind == VAL &&
	  right->child[0]->value == left->value) ||
	 (right->child[1]->kind == VAL &&
	  right->child[1]->value == left->value))) {
      expr *rsl = left;
      exprfree(e->child[0]->child[1]);
      free(e->child[0]->child[0]);
      free(e->child[0]);
      free(e);
      return rsl;
    }
    if (right->kind == VAL &&
	left->kind == AND &&
	((left->child[0]->kind == VAL &&
	  left->child[0]->value == right->value) ||
	 (left->child[1]->kind == VAL &&
	  left->child[1]->value == right->value))) {
      expr *rsl = right;
      exprfree(e->child[0]->child[0]);
      free(e->child[0]->child[1]);
      free(e->child[0]);
      free(e);
      return rsl;
    }
  }
  return e;
}

/* convert and(0 not(and(0 1))) to and(0 not(1)) */
expr *opti3(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti3(e->child[i]);
  }
  if (e->kind == AND &&
      e->child[0]->kind == VAL &&
      e->child[1]->kind == NOT &&
      e->child[1]->child[0]->kind == AND) {
    if (e->child[1]->child[0]->child[0]->kind == VAL &&
	e->child[1]->child[0]->child[0]->value == e->child[0]->value) {
      expr *old = e->child[1]->child[0];
      e->child[1]->child[0] = old->child[1];
      free(old->child[0]);
      free(old);
      return e;
    }
    if (e->child[1]->child[0]->child[1]->kind == VAL &&
	e->child[1]->child[0]->child[1]->value == e->child[0]->value) {
      expr *old = e->child[1]->child[1];
      e->child[1]->child[0] = old->child[0];
      free(old->child[1]);
      free(old);
      return e;
    }
  }
  if (e->kind == AND &&
      e->child[1]->kind == VAL &&
      e->child[0]->kind == NOT &&
      e->child[0]->child[0]->kind == AND) {
    if (e->child[0]->child[0]->child[0]->kind == VAL &&
	e->child[0]->child[0]->child[0]->value == e->child[1]->value) {
      expr *old = e->child[1]->child[0];
      e->child[0]->child[0] = old->child[1];
      free(old->child[0]);
      free(old);
      return e;
    }
    if (e->child[0]->child[0]->child[1]->kind == VAL &&
	e->child[0]->child[0]->child[1]->value == e->child[1]->value) {
      expr *old = e->child[1]->child[1];
      e->child[0]->child[0] = old->child[0];
      free(old->child[1]);
      free(old);
      return e;
    }
  }
  return e;
}

/* convert not(not(a) and b) to (a or not(b)) */
expr *opti4(expr *e)
{
  u4 i;
  if (e->kind == NOT &&
      (e->child[0]->kind == AND ||
       e->child[0]->kind == OR) &&
      (e->child[0]->child[0]->kind == NOT ||
       e->child[0]->child[1]->kind == NOT)) {
    expr *left = e->child[0]->child[0];
    expr *right = e->child[0]->child[1];
    expr *not;
    if (left->kind == NOT) {
      not = left;
      left = left->child[0];
      if (right->kind == NOT) {
	free(not);
	not = right;
	right = right->child[0];
	free(not);
      } else {
	not->child[0] = right;
	right = not;
      }
    } else {
      not = right;
      right = right->child[0];
      not->child[0] = left;
      left = not;
    }
    not = e;
    e = e->child[0];
    e->kind = (e->kind == AND ? OR : AND);
    e->child[0] = left;
    e->child[1] = right;
    free(not);
  }
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti4(e->child[i]);
  }
  return e;
}

/* convert (not(a) and not(b)) to not(a or b) */
expr *opti4b(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti4b(e->child[i]);
  }
  if ((e->kind == AND || e->kind == OR) &&
      e->child[0]->kind == NOT &&
      e->child[1]->kind == NOT) {
    expr *not = e->child[0];
    e->child[0] = e->child[0]->child[0];
    free(not);
    not = e->child[1];
    e->child[1] = e->child[1]->child[0];
    e->kind = ((e->kind == AND) ? OR : AND);
    not->child[0] = e;
    return not;
  } else if (e->kind == NOT && 
	     e->child[0]->kind == NOT) {
    expr *base = e->child[0]->child[0];
    free(e->child[0]);
    free(e);
    return base;
  }
  return e;
}

void doopti5(expr *e, u4 left, u4 right)
{
  expr *common = e->child[0]->child[left];
  e->child[0]->child[left] = e->child[1]->child[!right];
  e->child[0]->kind = e->kind;
  e->kind = e->child[1]->kind;
  exprfree(e->child[1]->child[right]);
  free(e->child[1]);
  e->child[1] = common;
  exprhash1(e->child[0]);
  exprhash1(e);
}

/* convert (a and b) or (a and c) to (a or (b and c)) */
expr *opti5(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti5(e->child[i]);
  }
  if (e->children == 2 &&
      e->child[0]->kind == e->child[1]->kind &&
      (e->kind == AND || e->kind == OR) &&
      (e->child[0]->kind == AND || e->child[0]->kind == OR)) {
    if (e->child[0]->child[0]->hash == e->child[1]->child[0]->hash) {
      doopti5(e, 0, 0);
    } else if (e->child[0]->child[0]->hash == e->child[1]->child[1]->hash) {
      doopti5(e, 0, 1);
    } else if (e->child[0]->child[1]->hash == e->child[1]->child[0]->hash) {
      doopti5(e, 1, 0);
    } else if (e->child[0]->child[1]->hash == e->child[1]->child[1]->hash) {
      doopti5(e, 1, 1);
    }
  }
  return e;
}

/* (a | b) & !(a & b) -> (a ^ b) */
expr *doopti6a(expr *e)
{
  expr *pair = e->child[0];
  pair->kind = XOR;
  exprfree(e->child[1]);
  if (e->kind == AND) {
    free(e);
    exprhash1(pair);
    return pair;
  } else {
    e->kind = NOT;
    e->children = 1;
    exprhash1(pair);
    exprhash1(e);
    return e;
  }
}

/* (a | ~b) & (~a | b) -> (a ^ ~b) */
expr *doopti6b(expr *e)
{
  expr *pair = e->child[0];
  exprfree(e->child[1]);
  free(e);
  if (pair->kind == AND) {
    expr *not = pair->child[1];
    pair->child[1] = not->child[0];
    free(not);
  }
  pair->kind = XOR;
  exprhash1(pair);
  return pair;
}

/* convert (a and ~b) or (~a and b) to (a xor b) */
expr *opti6(expr *e)
{
  u4 i;
  for (i=0; i<e->children; ++i) {
    e->child[i] = opti6(e->child[i]);
  }
  /* make sure NOT comes second if it comes at all */
  if (e->kind == AND || e->kind == OR) {
    if (e->child[0]->kind == NOT) {
      expr *temp = e->child[0];
      e->child[0] = e->child[1];
      e->child[1] = temp;
    }
  }
  if (e->kind == AND) {
    if (e->child[0]->kind == OR &&
	e->child[1]->kind == NOT &&
	e->child[1]->child[0]->kind == AND) {
      expr *right = e->child[1]->child[0];
      if ((e->child[0]->child[0]->hash == right->child[0]->hash &&
	  e->child[0]->child[1]->hash == right->child[1]->hash) ||
	  (e->child[0]->child[0]->hash == right->child[1]->hash &&
	   e->child[0]->child[1]->hash == right->child[0]->hash)) {
	e = doopti6a(e);
      }
    } else if (e->child[0]->kind == OR &&
	       e->child[1]->kind == OR &&
	       e->child[0]->child[1]->kind == NOT &&
	       e->child[1]->child[1]->kind == NOT) {
      expr *leftnot = e->child[0]->child[1]->child[0];
      expr *rightnot = e->child[1]->child[1]->child[0];
      if (leftnot->hash == e->child[1]->child[0]->hash &&
	  e->child[0]->child[0]->hash == rightnot->hash) {
	e = doopti6b(e);
      }
    }
  } else if (e->kind == OR) {
    if (e->child[0]->kind == AND &&
	e->child[1]->kind == NOT &&
	e->child[1]->child[0]->kind == OR) {
      expr *right = e->child[1]->child[0];
      if ((e->child[0]->child[0]->hash == right->child[0]->hash &&
	   e->child[0]->child[1]->hash == right->child[1]->hash) ||
	  (e->child[0]->child[0]->hash == right->child[1]->hash &&
	   e->child[0]->child[1]->hash == right->child[0]->hash)) {
	e = doopti6a(e);
      }
    } else if (e->child[0]->kind == AND &&
	       e->child[1]->kind == AND &&
	       e->child[0]->child[1]->kind == NOT &&
	       e->child[1]->child[1]->kind == NOT) {
      expr *leftnot = e->child[0]->child[1]->child[0];
      expr *rightnot = e->child[1]->child[1]->child[0];
      if (leftnot->hash == e->child[1]->child[0]->hash &&
	  e->child[0]->child[0]->hash == rightnot->hash) {
	e = doopti6b(e);
      }
    }
  }

  return e;
}

/* compile a subexpression */
void subcompile(expr **code, etab *ehash, expr *e, u4 *pos)
{
  expr *e2 = efind(ehash, e);
  u4 i;
  if (e2) {
    e->pos = e2->pos;
  } else {
    for (i=0; i<e->children; ++i) {
      subcompile(code, ehash, e->child[i], pos);
    }
    code[*pos] = e;
    e->pos = *pos;
    eadd(ehash, e);
    ++*pos;
  }
}

/* print the code for a half-permutation */
void printc(expr **code, expr **zwei, u4 pos, u4 id, perm *p, u4 *match)
{
  u4 i;

  printf("u4 truth%d[] = {\n", id);
  for (i=0; i<8; ++i) {
    if (i==4) printf("\n");
    printf(" 0x%.8x,", p->source[match[i]].truth);
  }
  printf("};\n\n");
  printf("u4 mask%d[] = {\n", id);
  for (i=0; i<8; ++i) {
    if (i==4) printf("\n");
    printf(" 0x%.3x,", p->mask[match[i]]);
  }
  printf("};\n\n");

  printf("void x%d(u8 *v)\n", id);
  printf("{\n");
  for (i=0; i<pos; ++i) {
    expr *e = code[i];
    printf("  u8 a%d = ", i);
    if (e->kind == VAL) {
      printf("v[%d]", e->value);
    } else if (e->kind == NOT) {
      printf("~a%d", e->child[0]->pos);
    } else if (e->kind == XOR) {
      printf("a%d ^ a%d", e->child[0]->pos, e->child[1]->pos);
    } else if (e->kind == AND) {
      printf("a%d & a%d", e->child[0]->pos, e->child[1]->pos);
    } else if (e->kind == OR) {
      printf("a%d | a%d", e->child[0]->pos, e->child[1]->pos);
    } else {
      printf("bob you missed something %d\n", e->kind);
    }
    printf(";\n");
  }
  for (i=0; i<HALFVAR; ++i) {
    printf("  v[%d] = a%d;\n", i, zwei[i]->pos);
  }
  printf("}\n\n");
}

static routine_id = 0;

/* given trees of optimized expr structures, write C code */
void compile(expr **zwei, perm *p, u4 *match)
{
  expr *code[2000];
  etab ehash;
  u4 i, pos;
  
  einit(&ehash,128);

  /* fill in the base variables */
  for (i=0; i<HALFVAR; ++i) {
    char x[1];
    u4 k = 0;
    x[0] = '0'+i;
    code[i] = parsevar(x, &k);
    code[i]->pos = i;
    exprhash(code[i]);
    eadd(&ehash, code[i]);
  }

  /* populate the array with nonduplicated expressions */
  pos=HALFVAR;
  for (i=0; i<HALFVAR; ++i) {
    subcompile(code, &ehash, zwei[i], &pos);
  }

  /* write the code */
  if (p->avalanche < 0.41) return;
  if (pos > 80) return;
  if (routine_id > 100) return;

  printc(code, zwei, pos, routine_id++, p, match);
}

/* further processing on a permutation */
/* match[HALFVAR] are the indexes of distinct slices */
u4 driver3(perm *p, hashtab *thash, u4 *match)
{
  u4 i,j,k;
  tree *half[HALFVAR];
  expr *zwei[HALFVAR];
  etab  ehash;

  for (i=0; i<HALFVAR; ++i) {
    balance *c = &p->source[match[i]];
    balance *b = hfind(thash, c->truth);
    half[i] = (tree *)0;
    tree *t;

    /* copy the trees, but adjust the positions for this permutation */
    for (t=b->impl; t; t = t->next) {
      /* copy the tree */
      tree *newtree = copytree(t);
      newtree->next = half[i];
      half[i] = newtree;

      /* adjust the positions of this new tree for this permutation */
      adjustpos(newtree, p->mask[match[i]]);
    }

    /* parse expresssion, and make use of XOR */
    zwei[i] = parsetree(half[i]);

    /* convert and(0 0) to 0 */
    zwei[i] = opti1(zwei[i]);

    /* convert not(and(not(0) not(and(0 1)))) to 0 */
    zwei[i] = opti2(zwei[i]);

    /* convert and(0 not(and(0 1))) to and(0 not(1)) */
    zwei[i] = opti3(zwei[i]);

    /* convert (not(a) and not(b)) to not(a or b) */
    zwei[i] = opti4b(zwei[i]);

    /* convert not(not(a) and b) to (a or not(b)) */
    zwei[i] = opti4(zwei[i]);

    /* fill in hashes of all expressions in this tree */
    exprhash(zwei[i]);

    /* convert ((a and b) or (a and c)) to (a or (b and c)) */
    zwei[i] = opti5(zwei[i]);

    /* recognize XOR */
    zwei[i] = opti6(zwei[i]);

    if (b->avalanche == 4.0 && 
	!((zwei[i]->kind == XOR) ||
	  (zwei[i]->kind == NOT && zwei[i]->child[0]->kind == XOR))) {
      printf("hi bob\n");
    }
  }

  /* generate C code */
  compile(zwei, p, match);

  /* free the trees */
  for (i=0; i<HALFVAR; ++i) {
    tree *t;
    while (half[i]) {
      t = half[i]->next;
      free(half[i]);
      half[i] = t;
    }
    zwei[i] = exprfree(zwei[i]);
  }
}

/* handle a single permutation */
u4 driver2(perm *p, hashtab *thash)
{
  u4 i,j,k;
  u4 counter;
  u4 match[HALFVAR][2];

  /* figure out the top and bottom half of the permutation */
  for (k=0, i=0; i<FULLVAR; ++i) {
    if (p->mask[i] < (1<<HALFVAR)) {
      match[k][0] = i;
      match[k][1] = -1;
      for (j=0; j<FULLVAR; ++j) {
	if (p->source[i].truth == p->source[j].truth &&
	    p->mask[i] == (p->mask[j] >> HALFVAR)) {
	  match[k][1] = j;
	}
      }
      if (match[k][1] == -1) {
	fprintf(stderr, "half-permutation is not duplicated\n");
	exit(3);
      }
      ++k;
    }
  }
  if (k != HALFVAR) {
    fprintf(stderr, "wrong size half permutation\n");
    exit(4);
  }

  /* who has at least 4*2 bits that are invertible? */
  counter = 0;
  for (i=0; i<HALFVAR; ++i) {
    balance *b = &p->source[match[i][0]];
    balance *base;
    u4 truth = b->truth;
    u4 invtruth = (~truth) & ((1<<(1<<b->loglen))-1);
    base = hfind(thash, truth);
    b->avalanche = base->avalanche;
    if (!base || !base->impl) {
      fprintf(stderr, "how could there be no truth table?\n");
      exit(1);
    }
    base = hfind(thash, invtruth);
    if (base->impl) {
      counter += 2;
    }
  }

#ifdef NEVER
  if (counter >= 2 && p->avalanche > 0.4) {
    printf("found %d invertible bits %f\n", counter, p->avalanche);
    for (i=0; i<HALFVAR; ++i) {
      balance *b = &p->source[match[i][0]];
      printf("%d  ", i);
      for (j=0; j<1<<(b->loglen); ++j) {
	printf("%c", (b->truth & (1<<j)) ? '1' : '0');
      }
      printf("  %f\n", b->avalanche);
    }
    printf("\n");
  }
#endif

  if (counter >= 2) {
    /* this one looks OK, generate some C code */
    u4 halfmatch[HALFVAR];
    for (i=0; i<HALFVAR; ++i) {
      halfmatch[i] = match[i][0];
    }
    driver3(p, thash, halfmatch);
  }
}

void driver(perm **perms, u4 count)
{
  u4   i;
  hashtab thash;
  if (count == 0) return;

  /* initialize the hash table */
  hinit(&thash, (1<<11));

  /* build a hash table of balanced functions for perms currently loaded */
  gettree(perms, count, &thash, "glob.txt");

  printf("/* got the trees */\n");

  /* generate code for all the perms */
  for (i=0; i<count; ++i) {
    driver2(perms[i], &thash);
  }

  /* release the tree */
  hfree(&thash);
}

#define MAPS 1000

/* handle a whole file full of permutations */
int main()
{
  char     *permname = "essex.txt";
  FILE     *permfile;
  char      buf[2000];
  perm     *perms[MAPS];
  u4        i, j, lineno;
  float     avalanche;

  /* allocate space for a permutation */
  for (i=0; i<MAPS; ++i) {
    perms[i] = (perm *)malloc(sizeof(perm));
  }

  /* open the permutation file */
  permfile = fopen(permname, "r");
  if (!permfile) {
    fprintf(stderr, "no such file, %s\n", permname);
    exit(1);
  }

  printf("typedef  unsigned long  u4;\n");
  printf("typedef  unsigned long long u8;\n");

  /* read in all the permutations */
  i = 0;
  j = 0;
  lineno = 0;
  while (fgets(buf, 2000, permfile)) {
    u4 k;
    u4 mask;
    u4 len;
    ++lineno;

    /* start over any time you see a blank line */
    if (buf[0] == '\r') {
      i = 0;
      continue;
    }
    else if (memcmp(buf, "worst is ", 9) == 0) {
      i = 0;
      sscanf(buf+9, "%f", &perms[j]->avalanche);
      continue;
    } else if (i > FULLVAR) {
      fprintf(stderr, "saw more than %d nonblank lines in a row, %d\n", 
	      FULLVAR, lineno);
      exit(2);
    }

    /* fill in one line of the permutation */
    sscanf(buf, "%d", &len);
    perms[j]->source[i].loglen = len;
    mask = 0;
    for (k=0; k<len; ++k) {
      u4 offset;
      sscanf(&buf[3*(k+1)], "%d", &offset);
      mask |= (1<<offset);
    }
    perms[j]->mask[i] = mask;
    perms[j]->source[i].truth = 0;
    for (k=0; k < (1<<len); ++k) {
      if (buf[3*len+5+k] == '1') {
	perms[j]->source[i].truth |= (1<<k);
      }
    }
    ++i;

    if (i == FULLVAR) {
      ++j;
    }
    if (j == MAPS) {
      driver(perms, MAPS);
      j = 0;
    }
  }
  driver(perms, j);

  /* close up shop */
  close(permfile);
  for (i=0; i<FULLVAR; ++i) {
    free(perms[i]);
    perms[i] = (perm *)0;
  }
}