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

#include "shapes.h"

typedef struct shape SHAPE;

struct shape {
  SHAPE *link;
  int x;
  int y;
  char *map;
  int size;
  int serial;
  } ;
#define MAP(sh,ix,iy) ((sh)->map[((iy)*(sh)->x)+(ix)])

static SHAPE *cur;
static SHAPE *next;
static SHAPE *all;
static int serial;

static SHAPE *newshape(int x, int y)
{
 SHAPE *p;

 p = malloc(sizeof(SHAPE)+(x*y));
 p->map = (void *) (p+1);
 p->x = x;
 p->y = y;
 return(p);
}

static void copymap(SHAPE *f, SHAPE *t, int x1, int x2, int y1, int y2, int xo, int yo)
{
 int x;
 int y;

 for (y=y1;y<y2;y++) for (x=x1;x<x2;x++) MAP(t,x+xo,y+yo) = MAP(f,x,y);
}

static int mapmatch(SHAPE *n, SHAPE *p, int o, int xi, int yi)
{
 int x;
 int y;
 int no;

 no = 0;
 for (y=n->y;y>0;y--)
  { for (x=n->x;x>0;x--)
     { if (n->map[no] != p->map[o]) return(0);
       no ++;
       o += xi;
     }
    o += yi;
  }
 return(1);
}

static void save_or_free(SHAPE *n)
{
 SHAPE *p;

 do <"free">
  { for (p=next;p;p=p->link)
     { if ( ( (p->x == n->x) && (p->y == n->y) &&
	      ( mapmatch(n,p,0,1,0) ||
		mapmatch(n,p,p->x-1,-1,p->x*2) ||
		mapmatch(n,p,(p->y-1)*p->x,1,-p->x*2) ||
		mapmatch(n,p,(p->x*p->y)-1,-1,0) ) ) ||
	    ( (p->x == n->y) && (p->y == n->x) &&
	      ( mapmatch(n,p,0,p->x,1-(p->x*p->y)) ||
		mapmatch(n,p,p->x-1,p->x,-(p->x*p->y)-1) ||
		mapmatch(n,p,(p->y-1)*p->x,-p->x,(p->x*p->y)+1) ||
		mapmatch(n,p,(p->y*p->x)-1,-p->x,(p->x*p->y)-1) ) ) )
	{ break <"free">;
	}
     }
    n->link = next;
    next = n;
    n->serial = serial++;
    return;
  } while (0);
 free(n);
}

static void add1square(SHAPE *p)
{
 SHAPE *n;
 int i;
 int j;

 for (i=p->y-1;i>=0;i--)
  { if (MAP(p,0,i))
     { n = newshape(p->x+1,p->y);
       copymap(p,n,0,p->x,0,p->y,1,0);
       for (j=n->y-1;j>=0;j--) MAP(n,0,j) = (i==j);
       n->size = p->size + 1;
       save_or_free(n);
     }
    if (MAP(p,p->x-1,i))
     { n = newshape(p->x+1,p->y);
       copymap(p,n,0,p->x,0,p->y,0,0);
       for (j=n->y-1;j>=0;j--) MAP(n,p->x,j) = (i==j);
       n->size = p->size + 1;
       save_or_free(n);
     }
  }
 for (i=p->x-1;i>=0;i--)
  { if (MAP(p,i,0))
     { n = newshape(p->x,p->y+1);
       copymap(p,n,0,p->x,0,p->y,0,1);
       for (j=n->x-1;j>=0;j--) MAP(n,j,0) = (i==j);
       n->size = p->size + 1;
       save_or_free(n);
     }
    if (MAP(p,i,p->y-1))
     { n = newshape(p->x,p->y+1);
       copymap(p,n,0,p->x,0,p->y,0,0);
       for (j=n->x-1;j>=0;j--) MAP(n,j,p->y) = (i==j);
       n->size = p->size + 1;
       save_or_free(n);
     }
  }
 for (i=p->y-1;i>=0;i--)
  { for (j=p->x-1;j>=0;j--)
     { if (! MAP(p,j,i))
	{ if ( ((j > 0) && MAP(p,j-1,i)) ||
	       ((i > 0) && MAP(p,j,i-1)) ||
	       ((j < p->x-1) && MAP(p,j+1,i)) ||
	       ((i < p->y-1) && MAP(p,j,i+1)) )
	   { n = newshape(p->x,p->y);
	     copymap(p,n,0,p->x,0,p->y,0,0);
	     MAP(n,j,i) = 1;
	     n->size = p->size + 1;
	     save_or_free(n);
	   }
	}
     }
  }
}

static int isqrt(int v)
{
 int i;
 int j;

 i = (v >> 1) | 1;
 j = v / i;
 while ((i != j) && (i+1 != j))
  { i = j;
    j = (i + (v/i)) / 2;
  }
 return(i);
}

static SHAPE *sort_list(SHAPE *l)
{
 SHAPE *a;
 SHAPE *b;
 SHAPE *t;
 SHAPE **lp;

 if (!l || !l->link) return(l);
 a = 0;
 b = 0;
 while (l)
  { t = a;
    a = l;
    l = l->link;
    a->link = b;
    b = t;
  }
 a = sort_list(a);
 b = sort_list(b);
 lp = &l;
 while (a || b)
  { if ( a &&
	 ( !b ||
	   (a->size < b->size) ||
	   ( (a->size == b->size) &&
	     (a->serial < b->serial) ) ) )
     { t = a;
       a = a->link;
     }
    else
     { t = b;
       b = b->link;
     }
    *lp = t;
    lp = &t->link;
  }
 *lp = 0;
 return(l);
}

static void gen_shapes(void)
{
 SHAPE *s;
 int curn;

#if MAXSIZE < 1
#error "MAXSIZE must be > 0"
#endif
 serial = 1;
 all = 0;
 next = 0;
 s = newshape(1,1);
 s->link = 0;
 s->map[0] = 1;
 s->size = 1;
 save_or_free(s);
 for (curn=1;curn<MAXSIZE;curn++)
  { cur = next;
    next = 0;
    while (cur)
     { s = cur;
       cur = s->link;
       add1square(s);
       s->link = all;
       all = s;
     }
  }
 while (next)
  { s = next;
    next = s->link;
    s->link = all;
    all = s;
  }
 all = sort_list(all);
}

static void dump_output(void)
{
 int totalsquares[MAXSIZE];
 int lastx[MAXSIZE];
 int i;
 SHAPE *s;
 unsigned char buf;
 int nbuf;
 int x;
 int y;
 int sq;
 int c;
 int inx;

 printf("#include \"shapes.h\"\n");
 printf("const unsigned char * const pcinit[] = {\n"/*}*/);
 for (i=MAXSIZE-1;i>=0;i--)
  { totalsquares[i] = 0;
    lastx[i] = -1;
  }
 c = 0;
 inx = 0;
 for (s=all;s;s=s->link)
  { i = (((s->x * s->y) + 7) >> 3) + 2;
    if (c+(i*4)+3 > 78)
     { printf("\n");
       c = 0;
     }
    c += printf("\"\\x%02x\\x%02x",s->x,s->y);
    nbuf = 0;
    buf = 0;
    sq = 0;
    for (y=0;y<s->y;y++) for (x=0;x<s->x;x++)
     { buf <<= 1;
       if (MAP(s,x,y))
	{ buf |= 1;
	  sq ++;
	}
       nbuf ++;
       if (nbuf > 7)
	{ c += printf("\\x%02x",buf);
	  nbuf = 0;
	  buf = 0;
	}
     }
    if (nbuf > 0) c += printf("\\x%02x",buf<<(8-nbuf));
    if ((sq < 1) || (sq > MAXSIZE)) abort();
    lastx[sq-1] = inx;
    for (i=sq-1;i<MAXSIZE;i++) totalsquares[i] += sq;
    c += printf("\",");
    inx ++;
  }
 printf(/*{*/"\n};\n");
 printf("const int numpc[%d] = {"/*}*/,MAXSIZE);
 for (i=1;i<=MAXSIZE;i++) printf("%d,",lastx[i-1]+1);
 printf(/*{*/"};\n");
 printf("const int boardsizes[%d] = {"/*}*/,MAXSIZE);
 for (i=1;i<=MAXSIZE;i++)
  { sq = isqrt((totalsquares[i-1]*4)-1);
    printf("%d,",sq+2);
  }
 printf(/*{*/"};\n");
}

int main(void);
int main(void)
{
 gen_shapes();
 dump_output();
 return(0);
}