typedef struct macrocell {
	macrocell *next, *result;
	macrocell *tl, *tr, *bl, *br;
} macrocell;

size_t hashcount, hashlimit, hashsize;
macrocell **hashtab, *freelist;

#define HASH(TL,TR,BL,BR) (BMP(TL)+3*(BMP(TR)+3*(BMP(BL)+3*(BMP(BR)+3))))

void
freemore(void) {
	size_t i;
	freelist = malloc(sizeof(*freelist) * hashcount);
	if(freelist == NULL)
		err(1, "malloc");
	for(i = 1; i < hashcount; i++)
		freelist[i-1].next = freelist+i;
}

void
hashmore(void) {
	unsigned long hash;
	macrocell *mc, **newtab;
	size_t newsize, i;

	newsize = hashsize * 2 + 1;
	newtab = calloc(sizeof(*newtab), newsize);
	for(i = 0; i < hashsize; i++)
		for(mc = hashtab[i]; mc; mc = mc->next) {
			hash = HASH(mc->tl,mc->tr,mc->bl,mc->br);
			newtab[hash & newsize] = mc;
		}
	free(hashtab);
	hashtab = newtab;
	hashsize = newsize;
	hashlimit = hashsize;
}

macrocell *
findmacrocell(macrocell *tl, macrocell *tr, macrocell *bl, macrocell *br) {
	unsigned long hash = HASH(tl,tr,bl,br);
	macrocell *mc;

	for(mc = hashtab[hash & hashzize]; mc; mc = mc->next)
		if(mc->tl==tl && mc->tr==tr && mc->bl==bl && mc->br==br)
			return(mc);
	if(freelist == NULL)
		freemore();
	if(++hashcount > hashlimit)
		hashmore();
	mc = freelist;
	freelist = mc->next;
	mc->next = hashtab[hash & hashsize];
	hashtab[hash & hashsize] = mc;
	mc->tl = tl;
	mc->tr = tr;
	mc->bl = bl;
	mc->br = br;
	if(ISBMP(tl))
		/* compute eagerly instead of lazily
		   since no extra memory is required */
		mc->result = result8(mc);
	else
		mc->result = NULL;
	return(mc);
}

/*
 * We represent 4*4 macrocells as unboxed bitmaps stored in what would
 * normally be the 8*8 macrocells' pointers, which means we make
 * certain assumptions as embodied in the macros below.
 */
#define BMPMAX (1 << 4*4)
#define BMP(MC) ((unsigned long)(MC))
#define ISBMP(MC) (BMP(MC) < BMPMAX)

/*
 * The quadrants of a 4*4 macrocell. Note that we represent a 2*2
 * macrocell as the centre of a 4*4 macrocell in order to make certain
 * things easier.
 */
#define BMPTL(MC) (BMP(MC) & 0xCC00 >> 5)
#define BMPTR(MC) (BMP(MC) & 0x3300 >> 3)
#define BMPBL(MC) (BMP(MC) & 0x00CC << 3)
#define BMPBR(MC) (BMP(MC) & 0x0033 << 5)

#define MAKEBMP(TL,TR,BL,BR) ((macrocell*)(TL<<5 | TR<<3 | BL>>3 | BR>>5))

/*
 * One generation of a 4*4 pattern gives a 2*2 result.
 */
static unsigned char bmpresult[BMPMAX];
#define BMPRESULT(MC) BMPBR(bmpresult[BMP(MC)])

void
initrules(void) {
	unsigned char tbl[1<<9];
	unsigned bmp;
	int bit, count, x, y;

	for(bmp = 0; bmp < 1<<9; bmp++) {
		count = 0;
		for(bit = 0; bit < 9; bit++)
			if(bmp & 1<<bit)
				count++;
		if(count == 3 || count == 4 && bmp & 020)
			tbl[bmp] = 1;
		else
			tbl[bmp] = 0;
	}
	for(bmp = 0; bmp < BMPMAX; bmp++) {
		bmpresult[bmp] = 0;
		for(x = 0; x < 2; x++)
			for(y = 0; y < 2; y++) {
				bit = y*4 + x;
				if(tbl[(bmp & 0x0007 << bit) >> bit+0 |
				       (bmp & 0x0070 << bit) >> bit+1 |
				       (bmp & 0x0700 << bit) >> bit+2])
					bmpresult[bmp] |= 1 << bit;
			}
	}
}

macrocell *
result8(macrocell *mc) {
/*
 * Two generations of an 8*8 pattern gives a 4*4 result.
 */
	unsigned
	    tlr = BMPRESULT(mc->tl),
	    tcr = BMPRESULT(MAKEBMP(BMPTR(mc->tl), BMPTL(mc->tr),
				    BMPBR(mc->tl), BMPBL(mc->tr))),
	    trr = BMPRESULT(mc->tr),
	    mlr = BMPRESULT(MAKEBMP(BMPBL(mc->tl), BMPBR(mc->tl),
				    BMPTL(mc->bl), BMPTR(mc->bl))),
	    mcr = BMPRESULT(MAKEBMP(BMPBR(mc->tl), BMPBL(mc->tr),
				    BMPTR(mc->bl), BMPTL(mc->br))),
	    mrr = BMPRESULT(MAKEBMP(BMPBL(mc->tr), BMPBR(mc->tr),
				    BMPTL(mc->br), BMPTR(mc->br))),
	    blr = BMPRESULT(mc->bl),
	    bcr = BMPRESULT(MAKEBMP(BMPTR(mc->bl), BMPTL(mc->br),
				    BMPBR(mc->bl), BMPBL(mc->br))),
	    brr = BMPRESULT(mc->br),
	    tlrr = BMPRESULT(MAKEBMP(tlr, tcr, mlr, mcr)),
	    trrr = BMPRESULT(MAKEBMP(tcr, trr, mcr, mrr)),
	    blrr = BMPRESULT(MAKEBMP(mlr, mcr, blr, bcr)),
	    brrr = BMPRESULT(MAKEBMP(mcr, mrr, bcr, brr));
	return(MAKEBMP(tlrr, trrr, blrr, brrr));
}

macrocell *
result(macrocell *mc) {
	if(mc->result || ISBMP(mc->tl))
		return(mc->result);
	else {
/*
 * 2^(n-2) generations of a 2^n * 2^n pattern gives a 2^(n-1) * 2^(n-1) result.
 */
		macrocell *
		    tlr = result(mc->tl),
		    tcr = result(findmacrocell(mc->tl->tr, mc->tr->tl,
					       mc->tl->br, mc->tr->bl)),
		    trr = result(mc->tr),
		    mlr = result(findmacrocell(mc->tl->bl, mc->tl->br,
					       mc->bl->tl, mc->bl->tr)),
		    mcr = result(findmacrocell(mc->tl->br, mc->tr->bl,
					       mc->bl->tr, mc->br->tl)),
		    mrr = result(findmacrocell(mc->tr->bl, mc->tr->br,
					       mc->br->tl, mc->br->tr)),
		    blr = result(mc->bl),
		    bcr = result(findmacrocell(mc->bl->tr, mc->br->tl,
					       mc->bl->br, mc->br->bl)),
		    brr = result(mc->br),
		    tlrr = result(findmacrocell(tlr, tcr, mlr, mcr)),
		    trrr = result(findmacrocell(tcr, trr, mcr, mrr)),
		    blrr = result(findmacrocell(mlr, mcr, blr, bcr)),
		    brrr = result(findmacrocell(mcr, mrr, bcr, brr));
		return(mc->result = findmacrocell(tlrr, trrr, blrr, brrr));
	}
}

int
depth(macrocell *mc) {
	int d;
	for(d = 2; !ISBMP(mc); mc = mc->next)
		d++;
	return(d);
}

/*
 * This macrocell is 2^depth cells across. Its quadrants are
 * 2^(depth-1) cells across. Its result is 2^(depth-1) cells across
 * and 2^(depth-2) generations in the future. We need to compute a
 * universe which is gen cells wider at this point in time than at gen
 * generations in the future.
 */
void
show(macrocell *mc, int depth, int cx, int cy, int gen) {
	int d1 = 1 << depth-1, d2 = 1 << depth-2;


	bool left   = disp.minx-gen < cx    || cx-d1 < disp.maxx+gen;
	bool centre = disp.minx-gen < cx+d2 || cx-d2 < disp.maxx+gen;
	bool right  = disp.minx-gen < cx+d1 || cx    < disp.maxx+gen;
	bool top    = disp.miny-gen < cy+d1 || cy    < disp.maxy+gen;
	bool middle = disp.miny-gen < cy+d2 || cy-d2 < disp.maxy+gen;
	bool bottom = disp.miny-gen < cy    || cy-d1 < disp.maxy+gen;
	if(depth == 1)
		showbmp(BMP(mc), cx, cy);
	else if(gen >= d2)
		show(result(mc), depth-1, cx, cy, gen-d2);
	else if(depth == 3) {
	} else {
		if(top) {
			if(left)
				show(mc->tl, depth-1, cx-d2, cy+d2, gen);
			if(centre && gen != 0)
				show(findmacrocell(mc->tl->tr, mc->tr->tl,
						   mc->tl->br, mc->tr->bl),
				    depth-1, cx, cy+d2, gen);
			if(right)
				show(mc->tr, depth-1, cx+d2, cy+d2, gen);
		}
		if(middle && gen != 0) {
			if(left)
				show(findmacrocell(mc->tl->bl, mc->tl->br,
						   mc->bl->tl, mc->bl->tr),
				    depth-1, cx-d2, cy, gen);
			if(centre)
				show(findmacrocell(mc->tl->br, mc->tr->bl,
						   mc->bl->tr, mc->br->tl),
				    depth-1, cx, cy, gen);
			if(right)
				show(findmacrocell(mc->tr->bl, mc->tr->br,
						   mc->br->tl, mc->br->tr),
				    depth-1, cx+d2, cy, gen);
		}
		if(bottom) {
			if(left)
				show(mc->bl, depth-1, cx-d2, cy-d2, gen);
			if(centre && gen != 0)
				show(findmacrocell(mc->bl->tr, mc->br->tl,
						   mc->bl->br, mc->br->bl),
				    depth-1, cx, cy-d2, gen);
			if(right)
				show(mc->br, depth-1, cx+d2, cy-d2, gen);
		}
	}
}