////
////  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
////  derived from the code in the following post by Tom Rokicki.
////  http://groups.google.com/group/comp.arch.embedded/msg/d835361b253897b5
////  See also http://fanf.livejournal.com/93032.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/liar2.c,v 1.4 2008/09/04 19:10:41 fanf2 Exp $";

#include <stdint.h>

// adder-like 3-to-2 reduction - see find-adder.lua
#define REDUCE(g,f,a,b,c) do {	\
		uint64_t d, e;	\
		d = a ^ b;	\
		e = b ^ c;	\
		f = c ^ d;	\
		g = d | e;	\
	} while(0)

uint64_t
liar(uint64_t bmp) {
	uint64_t tmp, left, right;
	uint64_t upper1, side1, mid1, lower1;
	uint64_t upper2, side2, mid2, lower2;
	uint64_t sum12, sum13, sum24, sum26;
	// this wraps around the left and right edges
	// but incorrect results for the border are ok
	left = bmp << 1;
	right = bmp >> 1;
	// half adder count of cells to either side
	side1 = left ^ right;
	side2 = left & right;
	// full adder count of cells in middle row
	mid1 = side1 ^ bmp;
	mid2 = side1 & bmp;
	mid2 = side2 | mid2;
	// shift middle row count to get upper and lower row counts
	upper1 = mid1 << 8;
	lower1 = mid1 >> 8;
	upper2 = mid2 << 8;
	lower2 = mid2 >> 8;
	// compress vertically
	REDUCE(sum12, sum13, upper1, side1, lower1);
	REDUCE(sum24, sum26, upper2, side2, lower2);
	// calculate result
	tmp = sum12 ^ sum13;
	bmp = (bmp | sum13) & (tmp ^ sum24) & (tmp ^ sum26);
	// mask out incorrect border cells
	return(bmp & 0x007E7E7E7E7E7E00);
	// total 19 + 7 = 26 operations
}

// eof