@; This file is a template.  It is not directly usable on its own.
@; gensolve.c takes this and massages it, interpreting the at signs as
@; indicating directives, generating C source for a solver.
#include <stdio.h>
#include <stdlib.h>
#include <strings.h>

@C

#define HTSIZE 1048576

typedef unsigned char CELL;
#define CELL_MARBLE 0x07
#define CELL_MARBLE_S 0
#define CELL_MARBLE_M 7
#define CELL_FIXED  0x38
#define CELL_F_EMPTY 0x00
#define CELL_F_WALL  0x08
#define CELL_F_BREAK 0x10
#define CELL_F_TPORT 0x18
#define CELL_F_DIODE 0x20
#define CELL_F_DBARS 0x28
#define CELL_F_AUX   0xc0
#define CELL_F_AUX_S 6
#define CELL_F_AUX_M 3
#define CELL_F_LF    0x00
#define CELL_F_UP    0x40
#define CELL_F_RT    0x80
#define CELL_F_DN    0xc0

typedef struct marble MARBLE;

struct marble {
  unsigned char colour;
  unsigned char x;
  unsigned char y;
  } ;

typedef struct board BOARD;

struct board {
  CELL b[SIZEX][SIZEY];
  MARBLE m[NMARBLES];
  unsigned char depth;
  unsigned int hash;
  BOARD *link;
  BOARD *hlink;
  const BOARD *parent;
  } ;

@B

static unsigned int crctbl[256];
static BOARD *htable[HTSIZE];
static BOARD *dlist;

@G

static void build_crctbl(void)
{
 unsigned int h;
 int i;
 int j;

 for (i=256-1;i>=0;i--)
  { h = i;
    for (j=8;j>0;j--) h = (h >> 1) ^ ((h & 1) ? 0xedb88320 : 0);
    crctbl[i] = h;
  }
}

static void init_hash(void)
{
 int i;

 for (i=HTSIZE-1;i>=0;i--) htable[i] = 0;
}

static void hashboard(BOARD *b)
{
 unsigned int h;
 int x;
 int y;

 h = 0x12345678;
 for (x=SIZEX-1;x>=0;x--) for (y=SIZEY-1;y>=0;y--) h = (h >> 8) ^ crctbl[(h^b->b[x][y])&0xff];
 b->hash = h;
}

static void hash_insert(BOARD *b)
{
 b->hlink = htable[b->hash%HTSIZE];
 htable[b->hash%HTSIZE] = b;
}

static BOARD *hash_find(BOARD *b)
{
 BOARD *t;

 for (t=htable[b->hash%HTSIZE];t;t=t->link)
  { if ((t->hash == b->hash) && !bcmp(&t->b[0][0],&b->b[0][0],SIZEX*SIZEY)) return(t);
  }
 return(0);
}

static void dumpboard(const BOARD *b)
{
 int x;
 int y;
 char c;

 for (y=0;y<SIZEY;y++)
  { for (x=0;x<SIZEX;x++)
     { if (b->b[x][y] & CELL_MARBLE)
	{ c = 'A' + (b->b[x][y] & CELL_MARBLE) - 1;
	}
       else
	{ switch (b->b[x][y] & CELL_FIXED)
	   { case CELL_F_EMPTY:
		c = '.';
		break;
	     case CELL_F_WALL:
		c = 'X';
		break;
	     default:
		c = '?';
		break;
	   }
	}
       if (x) putchar(' ');
       putchar(c);
     }
    if (y == 0) printf("   %d",b->depth);
    printf("\n");
  }
}

static void allmoves(const BOARD *b)
{
 int m;
 BOARD *n;
 BOARD *hf;
 int x;
 int y;
 int d;
 int dx;
 int dy;
 int xx;
 int yy;
 CELL c;
 static const int deltas[4][2]
  = { { 1, 0 },
      { 0, 1 },
      { -1, 0 },
      { 0, -1 } };

 n = 0;
// printf("testing moves from %p\n",(const void *)b);
// dumpboard(b);
 for (m=NMARBLES-1;m>=0;m--)
  { x = b->m[m].x;
    y = b->m[m].y;
    for (d=4-1;d>=0;d--)
     { if (! n) n = malloc(sizeof(BOARD));
       *n = *b;
       dx = deltas[d][0];
       dy = deltas[d][1];
       xx = x;
       yy = y;
//       printf("moving (%d,%d)=%d (%d,%d)\n",x,y,(b->b[x][y]>>CELL_MARBLE_S)&CELL_MARBLE_M,dx,dy);
       while <"move"> (1)
	{ c = n->b[xx+dx][yy+dy];
	  if (c & CELL_MARBLE) break <"move">;
	  switch (c & CELL_FIXED)
	   { case CELL_F_EMPTY:
		break;
	     case CELL_F_WALL:
		break <"move">;
	     case CELL_F_BREAK:
	     case CELL_F_TPORT:
	     case CELL_F_DIODE:
	     case CELL_F_DBARS:
		abort();
		break;
	   }
	  xx += dx;
	  yy += dy;
	}
       if ((xx == x) && (yy == y)) continue;
       n->depth = b->depth + 1;
       n->parent = b;
       n->m[m].x = xx;
       n->m[m].y = yy;
       n->b[x][y] &= ~CELL_MARBLE;
       n->b[xx][yy] |= b->b[x][y] & CELL_MARBLE;
       if (goal(n))
	{ printf("goal reached %p\n",(const void *)n);
	  dumpboard(n);
	  for (;b;b=b->parent)
	   { printf("---from\n");
	     dumpboard(b);
	   }
	  exit(0);
	}
       hashboard(n);
       hf = hash_find(n);
       if (hf)
	{ //printf("already present %p\n",(void *)hf);
	}
       else
	{ hash_insert(n);
	  n->link = dlist;
	  dlist = n;
//	  printf("saving new %p\n",(void *)n);
//	  dumpboard(n);
	  n = 0;
	}
     }
  }
 if (n) free(n);
}

static void deepen(void)
{
 BOARD *b;

 b = dlist;
 dlist = 0;
 for (;b;b=b->link) allmoves(b);
}

int main(void);
int main(void)
{
 build_crctbl();
 init_hash();
 initboard.link = 0;
 initboard.depth = 0;
 initboard.parent = 0;
 hashboard(&initboard);
 hash_insert(&initboard);
 dlist = &initboard;
 while (1)
  { deepen();
  }
}