/*
-----------------------------------------------------------------------
Given a list of balanced functions, try to build VARS-bit permutations
out of them.  This does hillclimbing: it replaces one variable at a 
time, always trying to build a bigger list of variables that work 
together.  Eventually it has VARS variables that all work together, and
every replacement forms a new complete permutation.
-----------------------------------------------------------------------
*/

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

typedef unsigned long int  u4;
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;
}

/* set a bit in a bitarray */
static void bits(char *x, int off)
{
  x[off/8] |= (1 << (off & 7));
}

/* clear a bit in a bitarray */
static void bitc(char *x, int off)
{
  x[off/8] &= (~(unsigned char)(1 << (off & 7)));
}

/* read a bit in a bitarray */
static int bit(char *x, int off)
{
  return ((x[off/8] & (1 << (off & 7))) != 0);
}

static bitclear(char *x, int length)
{
  int i;
  for (i=0; i<length/8; ++i) {
    x[i] = 0;
  }
}

/* count how many bits are set in a 32-bit integer, returns 0..32 */
static int count(int x)
{
  unsigned long c = (unsigned long)x;

  c = (c & 0x55555555) + ((c>>1 ) & 0x55555555);
  c = (c & 0x33333333) + ((c>>2 ) & 0x33333333);
  c = (c & 0x0f0f0f0f) + ((c>>4 ) & 0x0f0f0f0f);
  c = (c & 0x00ff00ff) + ((c>>8 ) & 0x00ff00ff);
  c = (c & 0x0000ffff) + ((c>>16) & 0x0000ffff);
  return (int)c;
}

/* one of all possible balanced functions */
typedef struct balance {
  int loglen;  /* loglen of truth table, number of variables in function */
  char *truth;  /* truth table for this function */
} balance;

#define VARS 8
#define VALUES (1<<VARS)

/* a 1-bit slice of some VARS-bit permutation */
typedef struct slice {
  struct slice *next;  /* next bit in the permutation */
  char truth[VALUES/8];  /* truth table for this bit */
  balance *source;      /* source balanced function */
  int offset[VARS];  /* mapping of source bits to slice bits */
} slice;

/* show how to build a complete permutation */
void showperm(slice *map[VARS])
{
  int i;
  for (i=0; i<VARS; ++i) {
    int j;
    printf("%d  ", map[i]->source->loglen); /* number of inputs */
    for (j=0; j<map[i]->source->loglen; ++j) {
      if (j != 0) printf(",");
      printf("%2d", map[i]->offset[j]);
    }
    printf("   %.*s", (1 << map[i]->source->loglen), map[i]->source->truth);
    printf("\n");
  }
  printf("\n");
}


/*
 * Given a source balanced function and a mapping of source bits to
 * slice bits, fill in the fields of a slice.
 */
void fillslice(slice *s, int mapping)
{
  char *x = s->source->truth;
  int loglen = s->source->loglen;
  int i, j;

  /* fill in the offsets */
  for (i=0, j=0; i<VARS; ++i) {
    if (mapping & (1<<i)) {
      s->offset[j++] = i;
    }
  }

  /* fill in the truth table */
  bitclear(s->truth, VALUES);
  for (i=0; i < VALUES; ++i) {
    int k;
    for (j=0, k=0; j<loglen; ++j) {
      if (i & (1<<s->offset[j])) {
	k |= (1<<j);
      }
    }
    if (s->source->truth[k] == '1') {
      bits(s->truth, i);
    }
  }
}


/*
 * Return 1 if the map so far is balanced, 0 otherwise 
 */
int testslice(slice *map[VARS], int slices)
{
  int count[VALUES];
  int len = VALUES;
  int values = (1 << slices);
  int limit = len / values;
  int i;
  for (i=0; i<values; ++i) {
    count[i] = 0;
  }
  for (i=0; i<len; ++i) {
    int j, q;
    for (j=0, q=0; j<slices; ++j) {
      if (bit(map[j]->truth, i)) {
	q |= (1<<j);
      }
    }
    if (++count[q] > limit) {
      return 0;
    }
  }
  return 1;
}


/*
 * Generate permutations from balanced functions
 */
int driver(
  balance **array, 
  size_t arraylen, 
  slice *map[VARS], 
  int *count,
  ranctx *rctx) 
{
  int offset = ranval(rctx)%arraylen;
  int i;
  
  /* set up a new trial slice */
  map[*count]->source = array[offset];
  i=((1<<array[offset]->loglen)-1);

  /* iterate over all ways of using this truth table */
  while (i < VALUES) {
    int replace = ranval(rctx) % *count;  /* old slice to replace */
    slice *tempslice;
    int j, k;
    
    fillslice(map[*count], i);  /* fill in the slice */

    /* use the new slice */
    tempslice = map[replace];
    map[replace] = map[*count];
    map[*count] = tempslice;
  
    /* test if the map is still balanced */
    if (testslice(map, *count)) {
      if (*count < VARS && testslice(map, *count+1)) {
	++*count;
	printf("count is now %d\n", *count);
      }

      if (*count == VARS) {
	/* we found a permutation, print it out */
	showperm(map);
      }

      /* This slice is at least as good as the old one, keep it */
      return;
    }
    
    /* restore the old slice */
    tempslice = map[replace];
    map[replace] = map[*count];
    map[*count] = tempslice;

    /* increment i */
    for (j=0; j<VALUES && !(i & (1<<j)); ++j) 
      ;
    for (k=j+1; k<VALUES && (i & (1<<k)); ++k)
      ;
    if (k >= VALUES) {
      return;
    }
    i += (1<<j) + (1<<(k-j-1)) - 1;
  }
}

#define MAXVARS 5
int main()
{
  char buf[2000];
  slice *map[VARS+1];
  balance **array; /* array of balanced functions */
  size_t arraylen;  /* length of list */
  int  i, len, count;
  FILE *f;
  char *filename = "high.boo";
  ranctx rctx = {1,1,1,2};

  for (i=0; i<20; ++i) (void)ranval(&rctx);

  /* allocate the mapping representation */
  for (i=0; i<VARS+1; ++i) {
    map[i] = (slice *)malloc(sizeof(slice));
  }

  /* how many balanced functions do we have? */
  f = fopen(filename, "r");
  if (!f) {
    fprintf(stderr, "no such file, %s\n", filename);
    exit(1);
  }
  arraylen = 0;
  while (fgets(buf, 2000, f)) {
    sscanf(buf, "%d", &len);
    if (len <= (1<<MAXVARS)) {
      ++arraylen;
    }
  }
  array = (balance **)malloc(sizeof(balance *)*arraylen);
  if (!array) {
    fprintf(stderr, "could not allocate array\n");
    exit(1);
  }
  fclose(f);

  /* read them all in */
  f = fopen(filename, "r");
  if (!f) {
    fprintf(stderr, "no such file second pass, %s\n", filename);
    exit(1);
  }
  i = 0;
  while (fgets(buf, 2000, f) && i<arraylen) {
    sscanf(buf, "%d", &len);
    if (len <= (1<<MAXVARS)) {
      int loglen = 0;
      while ((1<<loglen) < len) ++loglen;
      array[i] = (balance *)malloc(sizeof(balance));
      array[i]->loglen = loglen;
      array[i]->truth = (char *)malloc(len);
      memcpy(array[i]->truth, &buf[5], len);
      ++i;
    }
  }
  fclose(f);
  f = (FILE *)0;
  printf("read everything in\n");

  /* recursively build all permutations */
  count = 1;
  map[0]->source = array[0];
  fillslice(map[0], (1<<map[0]->source->loglen)-1);
  for (;;) {
    driver(array, arraylen, map, &count, &rctx);
  }
}