////
////  LIFE IN A REGISTER
////
////  This code computes a generation of Conway's Game of Life on
////  an 8x8 bitmap represented as a 64 bit unsigned integer. It is
////  described in detail at http://fanf.livejournal.com/81169.html
////
////  This was written by Tony Finch <dot@dotat.at>.
////  You may do anything with it, at your own risk.
////

static const char metadata[] =
"@(#) $dotat: life/liar.c,v 1.6 2008/09/03 19:44:34 fanf2 Exp $";

#include <stdint.h>

// Parallel half adder.
// s1 must not be the same as a0 or a1
#define ADD2(s0,s1,a0,a1) do {		\
		s1 = (a0) & (a1);	\
		s0 = (a0) ^ (a1);	\
	} while(0)

// Parallel full adder.
// s0 must not be the same as a2
#define ADD3(s0,s1,a0,a1,a2) do {	\
		uint64_t c0, c1;	\
		ADD2(s0,c0,a0,a1);	\
		ADD2(s0,c1,s0,a2);	\
		s1 = c0 | c1;		\
	} while(0)

uint64_t
liar(uint64_t bmp) {
	uint64_t left, right;
	uint64_t up1, mid1, down1;
	uint64_t up2, mid2, down2;
	uint64_t sum2a, sum2b;
	uint64_t sum4a, sum4b;
	uint64_t sum1, sum2, sum4;
	// count cells in middle row
	// this wraps around the left and right edges
	// but incorrect results for the border are ok
	left  = bmp << 1;
	right = bmp >> 1;
	ADD3(mid1, mid2, left, bmp, right);
	// count bottom bits of three rows
	up1   = mid1 << 8;
	down1 = mid1 >> 8;
	ADD3(sum1, sum2a, up1, mid1, down1);
	// and upper bits of three rows
	up2   = mid2 << 8;
	down2 = mid2 >> 8;
	ADD3(sum2b, sum4a, up2, mid2, down2);
	// propagate carries, ignoring last one
	// so counts 8 and 9 map on to 0 and 1
	ADD2(sum2, sum4b, sum2a, sum2b);
	sum4 = sum4a ^ sum4b;
	// it stays the same if the count is 4
	// and is live if the count is 3
	bmp = bmp & ~sum1 & ~sum2 &  sum4
	          |  sum1 &  sum2 & ~sum4;
	// mask out incorrect border cells
	return(bmp & 0x007E7E7E7E7E7E00);
	// total 27 + 7 = 34 operations
}

// eof