//// //// 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 . //// 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 // 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