// APOHLIFE : Annotated Partially Obfuscated 64-bit Hash Life program.
// This program assumes sizeof(long)==8 (64 bits) and little endianess.
// Also unaligned (mod 8) long loads support.
// Xlib is evidently used . Should be runnable almost everywhere
// with gcc command such as:
// gcc -O3 -std=c99 apholife.c -lX11 -lm
//
// If you want to understand Hashlife The clearest description with diagrams of the recursion I found was in:
// https://jennyhasahat.github.io/hashlife.html
// You can also read Tom Rokicki article appearing in DrDobbs
// http://www.drdobbs.com/jvm/an-algorithm-for-compressing-space-and-t/184406478
// And of course look it up in wikipedia, etc ...
//
#include
#include
#include
#include
#include
#include
#include
#define MAXLEV 1024 // Maximal level supported by our universe.
#define W (32*40l) // Display window size
#define H (32*40l)
#define HBITS 29 // This wil determine our memory usage (hash + cells)
#define HSIZE (1ll<>i & m4;
o+= in*2>>i & m4;
o+= in/2>>i & m4;
o+=(o << 8)+(o >> 8); // And now we have in 'o' nibbles 16 sums each of a 3*3 neighborhood.
// This line, implementing Conways GOL rule, is left as an exercise for the reader. Muhahaha...
res |= (((o+m4 & m4*6 ^ 3*m4)+m4 >> 3) & (in >> i | o) & m4) << i;
}
in=res;
}
return in>>18 & mh ; // this just returns the middle quarter-leaf as the result.
}
//
// We have the following tricky but efficient way to encode node and leaf data in the same array of longs in
// an econmoical and aligned manner. We use 32bit indices into the array in lieu of pointers which occupy 64bit
// nowdays. This results in almost factor of 2 compression of memory usage.
//
// A node at ptr i will be encoded using three longs as follows:
// g_lmem[i] : Two upper quads ptrs (each 32 bits of course).
// g_lmem[i+1]: Upper 32bit word : Result ptr. Lower 13 bits: the log2 of step used for calculating result. 14th bit : 1.
// g_lmem[i+2]: Two lower quads ptrs.
//
// A leaf at ptr i will be encoded using two longs as:
// g_lmem[i] : 64 bits of the 8*8 leaf.
// g_lmem[i+1]: Upper 32bit word: Result 4*4 encoded in lower nibble of each byte. Lower 13 bits same as above. 14th bit: 0.
//
// Notice this encoding can support upto 2^32 pointers which would
// mean g_lmem would be 32 Gbytes and together with a hash of a reasonable load factor we would probably
// need more than 48 GBytes of RAM in order to run out of usable encoding space.
//
ulong *g_lmem;
unsigned *g_hash;
//
// The following functions/Macros are heavily used in the hashlife algorithm which is essentialy all about
// splitting cells into four quadrants, and then creating new cells by joining four quadrants.
// We use the term cell to denote *both* leafs and nodes which are stored of course in the same hash.
// Quads are always stored in an array conviently called q, with an implicit assumption
// that q is 2D with stride *Four*. I.e. to move vertically in q we need to add/sub 4 ...
// This way we naturally have a 4*4 array structure on a q[16] vector needed for hashlife recursion.
// We call the quads of each quad subquads. So we can say in q there are four quads and sixteen subquads.
// This QUADLOOP macro is used to shorten many loops in the code that work on 4 quads/subquads.
#define QUADLOOP(x) {int j; for(int i=0;i<4;i++) {j=i+(i&2); x;} } // j is quad index in q.
// Get a quad (indexed by i) from a cell pointer.
// The main complication here is the case of leaves that gets splitted to quarters-leaves differenty.
// Notice that here is the single place we actualy assume little endianity, as it affects the expression
// to get two 32bit words out of each long.
unsigned getquad(unsigned cell,int i){
return g_lmem[cell+1]&8192 ? g_lmem[cell+(i&2)] >> i%2*32 : g_lmem[cell] >> i%2*4+16*(i&2)&mh ;
}
// This mq function does the splitting of a cell into four quads and stores them in the q array.
void mq(unsigned cell,unsigned *q) {
QUADLOOP (q[j]=getquad(cell,i));
}
// This GQ macro is using the q array and generates the union of four cells there using the main
// hget hash lookup/update recursive function. All our recursions are done using this macro.
#define GQ(i,level,flags) hget(q+(i),(level)*4+flags)
unsigned calc_result(unsigned cell,ulong leaf,ulong lh,unsigned *q,int level,int res_step);
// This single hget routine will do most of the work for us.
// It will get (or create a new) node or leaf from the hash, looking it up from its four quarters.
// The four quarters are passed in the qi array, as usual in places 0,1, 4 and 5.
// In the level argument's 2 low bits we have flags described below.
// level>>2 is the level of the joined node made from the quarters, where 0 is for a leaf.
// Remember that quarter leaf encoding is always an unsigned with low nibbles only containing the 4*4 data.
// level&2: If on, we just return the joined node. If 0 we return the joined node's *Result*.
// level&1: Signals "half" recursion mode, Where we join four middle *quarters* of the 4 inputs, to produce a middle quad,
// In that case we return this middle cell's node (and not the middles result).
unsigned hget(unsigned* qi, int level)
{
ulong leaf,lh,ll;
int lv=level>>2;
unsigned hind=0; // Wil be used to calculate hash function
unsigned cell;
ulong *data=(ulong *)qi; // Here we seem to use little endianity but in fact we dont. as we store
// and compare the q unsigned array contents to the g_lmem long array.
// What we do use is tha fact longs can be loaded and stored from *unaligned*
// addresses. So we break pointer punning.
if(lv>0) {
if(level&1) {
unsigned q[6];
QUADLOOP(q[j]=getquad(qi[j],i^3)); // That ^3 will neatly give us the 4 middle subquads to be joined into middle quad.
return GQ(0,lv-1,2);
}
QUADLOOP(hind=917*hind+qi[j]); // Our node hash function ...
leaf=data[0]; // Misleading but used for the hash lookup
lh=data[2];
}
else {
// Inputs in qi are quarter leaves.
hind= (ll=qi[0]|qi[1]<<4) + 719*(lh=qi[4]|qi[5]<<4); // Hash calculation and create two longs...
// A bit tricky but that will be the quarter leaf mid of the joined leaf.
if(level&1) return (ll>>18)&0xf0f | (lh&0x3c3c)<<14;
leaf= ll | lh <<32;
}
// Do linear hash probing, nice and simple ...
for(; cell=g_hash[hind&=HMASK]; hind++)
if (leaf==g_lmem[cell] && (!lv || g_lmem[cell+2]==lh) && !!lv == (g_lmem[cell+1]>>13&1)) break;
// The last condition above is to avoid a very rare and subtle bug that can happen, for example
// when searching a leaf, we might find a node instead whose lower data is identical to the leaf's bits
// *and* its hash is also similar/close. This is possible but the probablity is very low indeed.
// The probablity of encountering this bug is so low that the actual obfuscated entry has not got
// the fix above but the bug does not seem to happen on the supplied patterns.
int res_step= lv+1; // res_step is the maximal timestep we can get result for.
if(res_step > g_step) res_step=g_step; // Notice that if g_step is small, res_step will not be maximal.
// This will mean we will do half recursion later.
if (!cell || g_lmem[cell+1]&8191^res_step) {
// We enter here whenever we need to (re) calculate result, either because g_step changed or
// if its a new cell. In principle result needs to be recalculated whenever g_step was increased
// compared to earlier calculation but also upon decrease. Though notice that when g_step is high
// and the cell is lower level, g_step changing will not affect res_step.
cell=g_hash[hind]=calc_result(cell,leaf,lh,qi,lv,res_step);
}
// Remember the result is always in cell+1 high part ...
return (level&2) ? cell: g_lmem[cell+1]>>32;
}
// This g_ptr variable is the pointer to the g_lmem nodes/leaf array where we will allocate the next cell.
unsigned g_ptr=2; // skip the 0 which is null ptr in the hash. Start from 2 in order to leave space
// at zero used by the getin leaf reading code.
//
// Finaly we reached the most intersting part of result calculation / hashlife recursion.
// After all the ground work we've layed before, it becomes surprsingly short, heck the
// comments are longer than the code !
//
unsigned calc_result(unsigned cell,ulong leaf,ulong lh,unsigned *qi,int level,int res_step)
{
if(!cell) { // Create a new one ...
g_lmem[cell=g_ptr]=leaf;
g_lmem[g_ptr+=2]=lh; // This will write some junk in case of leaf but we dont care
g_ptr+= level>0;
}
if(!level) {
g_lmem[cell+1]=res_step|(q8x8(leaf)<<32);
}
else {
int j;
unsigned q[16];
// Finaly we have reached Hashlifes glorious recusion: make new node from four quadrants and calculate its result.
// A neat obfuscation/compression trick here is that q can be updated in-place shrinking from 4*4 to 3*3 to 2*2,
// all during the sub-steps in the hashlife recursion calculation. Its recommended looking at the link above for
// some diagrams describing this recursion.
// 'hr' flag will indicates half recursion. All it does is, that in the second sub-step the 4 recursive calls just join
// cells to calculate middle cell, rather then calculate result forward in time.
//
// This QUADLOOP wil create the 16 subquads data in q.
// Notice that rather conveniently 2*j here is just 0,2,8,10 which are indices of the quads we want inside the 4*4 q.
QUADLOOP(mq(qi[j],q+2*j));
unsigned hr = level>g_step-1;
// The whole recursion stuff just becomes the two innocently looking loops below, and hopefuly gcc is decent
// enough to unroll them under -O3 so its also rather efficient as well...
for(int i=0;i<11;i++) if((i+1)&3) q[i]=GQ(i,level-1,0); // Neatly do the first step. 9 recursive calls.
QUADLOOP(q[j]=GQ(j, level-1, hr)); //Second step. four recursive calls, and QUADLOOP can be used....
// We get our final result from q by a simple quads join...
ulong result= GQ(0,level-1,2);
g_lmem[cell+1]=res_step|8192|(result<<32);
}
return cell;
}
// Create the empty space cells/empty universe. Must happen before getin.
void init_empty_space(int maxlev)
{
unsigned q[16];
unsigned cell=0;
for(unsigned i=0;i= MAXLEV) {
g_freeze=1;
return cell;
}
if(target>32; // Thats the expanded cell's result which does the actual timestep!
//
// Now we need to see if the result can be shrunk (i.e. is at a too high level).
//
while(--level > 0) {
mq(cell,q+10); // Split cell into 4 quads at index 10 (the bottom right quad)
QUADLOOP(mq(q[10+j],q+2*j)); // after this we are back with 16 subquads of original cell.
// Thats rather condensed but if the loop below finds one of the external 12 quads
// is nonempty it just returns with the current cell value.
for(int i=0;i<16;i++) if((i^i/2)&5^5 && q[i] != 3*level-4) {*ilevel=level; return cell;}
cell=GQ(5,level-1,2); // Shrink by one level to the middle quad.
}
}
#define MAXMOVES 500000
unsigned g_cells[MAXMOVES]; // Will be use to hold input cells and then later to hold moves history
double g_gens[MAXMOVES]; // Will be use to hold gens history
// We even have some minimal error handling here :)
void error(char *s) {printf("%s\n",s);exit(1);}
//
// This is our input routine, reading marocell (.mc) golly format.
// Its quite pedantic but hopefuly does not dump cores on bad input :)
//
int getin(FILE *f,int *lv)
{
char c,line[100];
static int lev,skip; // Skip is needed to skip Gollys header line.
unsigned cell,q[16];
unsigned iptr=1; // Start input counter from 1 as defined by .mc format.
while(fgets(line,100,f)) {
if(skip++ && line[0]!='#') {
if(sscanf(line,"%d%d%d%d%d",&lev,q,q+1,q+4,q+5)==5){
lev-=3;
// Put the Referenced nodes into q array. Notice that 0 uses the formula for the empty cell...
QUADLOOP(if(q[j]>=iptr)error("Bad node input data"));
QUADLOOP(q[j]=q[j]?g_cells[q[j]]:lev*3-1);
}
else {
// Put 64 bits leaf pattern into g_lmem[0].
lev=g_lmem[0]=0;
int l=0,j=0,i=0;
while(c=line[i++]){
if(c=='*') {
if(l*8+j>64) error("Bad leaf input data");
g_lmem[0]|=1l< 6) return;
double width2=ldexp(W,g_pscale-5);
double height2=ldexp(H,g_pscale-5);
if(sx >= g_mx+width2 || sx+sz<=g_mx-width2) return;
if(sy >= g_my+height2 || sy+sz<=g_my-height2) return;
double ox=(sx-g_mx+width2);
double oy=(sy-g_my+height2);
unsigned *pout=g_out+lround(ldexp(oy,4-g_pscale))*g_stride + lround(ldexp(ox,4-g_pscale));
if(level <= g_pscale-7) { // Our cell is smaller than a single pixel, its non empty though, so we set it.
*pout=-1; //Yes Virginia, -1 is needed here to get white color ....
return;
}
if(level) {
level--; sz*=0.5;
// Notice QUADLOOP macro is also usefull for this quadrants draw loop recursion.
unsigned q[6];
mq(cell,q);
QUADLOOP(draw(q[j],level,sx+i%2*sz,sy+i/2*sz,cx*2+i%2,cy*2+i/2));
}
else {
int z0=0,z=4-g_pscale;
if(z<0) {
z0=-z;
z=0;
}
// Generate color background pattern, another nice? coding riddle..
cx^=cy; unsigned background=0x22<<(cx&8?8:cx&64?16:24);
// Leaf drawing here supports both positive zoom of upto 4 and negative ofcourse.
ulong in=g_lmem[cell];
for(int i=0;i<8<>z0)*g_stride+(j>>z0)] |=
(!i|!j && g_pscale<4) ? 0x80 : // This is the condition to draw leaf borders
(in>>((i>>z)*8+(j>>z)))&1 ? -1 : background;
}
}
}
}
int g_adv=0, g_dir=0, g_sstep=0;
void processEvent(Display *d, Window win, XImage *xi)
{
XEvent ev;
if(XCheckWindowEvent(d,win,1,&ev)&&ev.type==KeyPress) {
int N=XLookupKeysym(&ev.xkey,0)&255;
// The keys ui is documented in the IOCCC entry remarks...
if (N==27) { exit(0);} // Use escape key to exit ...
if (N==83) { g_mx+=5l<= MAXMEM-g_ptr || curr>=MAXMOVES-3) {
g_freeze=curr;
}
}
else if(curr2) {
lev=g_cells[curr-=2]; cell=g_cells[curr-1]; gen=g_gens[curr/2];
}
}
if(curr>2) {
printf("G: %g M: %d L%d S%d%s\n",gen,g_ptr,lev,g_pscale,g_freeze?" (Frozen)":"");
}
}
if(g_sstep)g_adv=0;
}
}