1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 /*
5 * hlife 0.99 by Radical Eye Software.
6 *
7 * All good ideas here were originated by Gosper or Bell or others, I'm
8 * sure, and all bad ones by yours truly.
9 *
10 * The main reason I wrote this program was to attempt to push out the
11 * evaluation of metacatacryst as far as I could. So this program
12 * really does very little other than compute life as far into the
13 * future as possible, using as little memory as possible (and reusing
14 * it if necessary). No UI, few options.
15 */
16 #include "hlifealgo.h"
17 #include "util.h"
18 #include <stdlib.h>
19 #include <string.h>
20 #include <iostream>
21 using namespace std ;
22 /*
23 * Power of two hash sizes work fine.
24 */
25 #ifdef PRIMEMOD
26 #define HASHMOD(a) ((a)%hashprime)
nexthashsize(g_uintptr_t i)27 static g_uintptr_t nexthashsize(g_uintptr_t i) {
28 g_uintptr_t j ;
29 i |= 1 ;
30 for (;; i+=2) {
31 for (j=3; j*j<=i; j+=2)
32 if (i % j == 0)
33 break ;
34 if (j*j > i)
35 return i ;
36 }
37 }
38 #else
39 #define HASHMOD(a) ((a)&(hashmask))
nexthashsize(g_uintptr_t i)40 static g_uintptr_t nexthashsize(g_uintptr_t i) {
41 while ((i & (i - 1)))
42 i += (i & (1 + ~i)) ; // i & - i is more idiomatic but generates warning
43 return i ;
44 }
45 #endif
46 /*
47 * Note that all the places we represent 4-squares by short, we use
48 * unsigned shorts; this is so we can directly index into these arrays.
49 */
50 static unsigned char shortpop[65536] ;
51 /*
52 * The cached result of an 8-square is a new 4-square representing
53 * two generations into the future. This subroutine calculates that
54 * future, assuming ruletable is calculated (see below). The code
55 * that it uses is similar to code you'll see again, so we explain
56 * what's going on in some detail.
57 *
58 * Each time we build a leaf node, we compute the result, because it
59 * is reasonably quick.
60 *
61 * The first generation result of an 8-square is a 6-square, which
62 * we represent as nine 2-squares. The nine 2-squares are called
63 * t00 through t22, and are arranged in a matrix:
64 *
65 * t00 t01 t02
66 * t10 t11 t12
67 * t20 t21 t22
68 *
69 * To compute each of these, we need to extract the relevant bits
70 * from the four 4-square values n->nw, n->ne, n->sw, and n->ne.
71 * We can use these values to directly index into the ruletable
72 * array.
73 *
74 * Then, given the nine values, we can compute a resulting 4-square
75 * by computing four 2-square results, and combining these into a
76 * single 4-square.
77 *
78 * It's a bit intricate, but it's not really overwhelming.
79 */
80 #define combine9(t00,t01,t02,t10,t11,t12,t20,t21,t22) \
81 ((t00) << 15) | ((t01) << 13) | (((t02) << 11) & 0x1000) | \
82 (((t10) << 7) & 0x880) | ((t11) << 5) | (((t12) << 3) & 0x110) | \
83 (((t20) >> 1) & 0x8) | ((t21) >> 3) | ((t22) >> 5)
leafres(leaf * n)84 void hlifealgo::leafres(leaf *n) {
85 unsigned short
86 t00 = ruletable[n->nw],
87 t01 = ruletable[((n->nw << 2) & 0xcccc) | ((n->ne >> 2) & 0x3333)],
88 t02 = ruletable[n->ne],
89 t10 = ruletable[((n->nw << 8) & 0xff00) | ((n->sw >> 8) & 0x00ff)],
90 t11 = ruletable[((n->nw << 10) & 0xcc00) | ((n->ne << 6) & 0x3300) |
91 ((n->sw >> 6) & 0x00cc) | ((n->se >> 10) & 0x0033)],
92 t12 = ruletable[((n->ne << 8) & 0xff00) | ((n->se >> 8) & 0x00ff)],
93 t20 = ruletable[n->sw],
94 t21 = ruletable[((n->sw << 2) & 0xcccc) | ((n->se >> 2) & 0x3333)],
95 t22 = ruletable[n->se] ;
96 n->res1 = combine9(t00,t01,t02,t10,t11,t12,t20,t21,t22) ;
97 n->res2 =
98 (ruletable[(t00 << 10) | (t01 << 8) | (t10 << 2) | t11] << 10) |
99 (ruletable[(t01 << 10) | (t02 << 8) | (t11 << 2) | t12] << 8) |
100 (ruletable[(t10 << 10) | (t11 << 8) | (t20 << 2) | t21] << 2) |
101 ruletable[(t11 << 10) | (t12 << 8) | (t21 << 2) | t22] ;
102 n->leafpop = bigint((short)(shortpop[n->nw] + shortpop[n->ne] +
103 shortpop[n->sw] + shortpop[n->se])) ;
104 }
105 /*
106 * We do now support garbage collection, but there are some routines we
107 * call frequently to help us.
108 */
109 #ifdef PRIMEMOD
110 #define node_hash(a,b,c,d) (65537*(g_uintptr_t)(d)+257*(g_uintptr_t)(c)+17*(g_uintptr_t)(b)+5*(g_uintptr_t)(a))
111 #else
node_hash(void * a,void * b,void * c,void * d)112 g_uintptr_t node_hash(void *a, void *b, void *c, void *d) {
113 g_uintptr_t r = (65537*(g_uintptr_t)(d)+257*(g_uintptr_t)(c)+17*(g_uintptr_t)(b)+5*(g_uintptr_t)(a)) ;
114 r += (r >> 11) ;
115 return r ;
116 }
117 #endif
118 #define leaf_hash(a,b,c,d) (65537*(d)+257*(c)+17*(b)+5*(a))
119 /*
120 * Resize the hash. The max load factor defined here does not actually
121 * yield the maximum load factor the hash will see, because when we
122 * do the last resize before exhausting memory, we may find we are
123 * not permitted (while keeping total memory consumption below the
124 * limit) to do the resize, so the actual max load factor may be
125 * somewhat higher. Conversely, because we double the hash size
126 * each time, the actual final max load factor may be less than this.
127 * Additional code can be added to manage this, but after some
128 * experimentation, it has been found that the impact is tiny, so
129 * we are keeping the code simple. Nonetheless, this factor can be
130 * tweaked in the case where you absolutely want as many nodes as
131 * possible in memory, and are willing to use a large load factor to
132 * permit this; with the move-to-front heuristic, the code actually
133 * handles a large load factor fairly well.
134 */
135 double hlifealgo::maxloadfactor = 0.7 ;
resize()136 void hlifealgo::resize() {
137 #ifndef NOGCBEFORERESIZE
138 if (okaytogc) {
139 do_gc(0) ; // faster resizes if we do a gc first
140 }
141 #endif
142 g_uintptr_t i, nhashprime = nexthashsize(2 * hashprime) ;
143 node *p, **nhashtab ;
144 if (hashprime > (totalthings >> 2)) {
145 if (alloced > maxmem ||
146 nhashprime * sizeof(node *) > (maxmem - alloced)) {
147 hashlimit = G_MAX ;
148 return ;
149 }
150 }
151 if (verbose) {
152 sprintf(statusline, "Resizing hash to %" PRIuPTR "...", nhashprime) ;
153 lifestatus(statusline) ;
154 }
155 nhashtab = (node **)calloc(nhashprime, sizeof(node *)) ;
156 if (nhashtab == 0) {
157 lifewarning("Out of memory; running in a somewhat slower mode; "
158 "try reducing the hash memory limit after restarting.") ;
159 hashlimit = G_MAX ;
160 return ;
161 }
162 alloced += sizeof(node *) * (nhashprime - hashprime) ;
163 g_uintptr_t ohashprime = hashprime ;
164 hashprime = nhashprime ;
165 #ifndef PRIMEMOD
166 hashmask = hashprime - 1 ;
167 #endif
168 for (i=0; i<ohashprime; i++) {
169 for (p=hashtab[i]; p;) {
170 node *np = p->next ;
171 g_uintptr_t h ;
172 if (is_node(p)) {
173 h = node_hash(p->nw, p->ne, p->sw, p->se) ;
174 } else {
175 leaf *l = (leaf *)p ;
176 h = leaf_hash(l->nw, l->ne, l->sw, l->se) ;
177 }
178 h = HASHMOD(h) ;
179 p->next = nhashtab[h] ;
180 nhashtab[h] = p ;
181 p = np ;
182 }
183 }
184 free(hashtab) ;
185 hashtab = nhashtab ;
186 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
187 if (verbose) {
188 strcpy(statusline+strlen(statusline), " done.") ;
189 lifestatus(statusline) ;
190 }
191 }
192 /*
193 * These next two routines are (nearly) our only hash table access
194 * routines; we simply look up the passed in information. If we
195 * find it in the hash table, we return it; otherwise, we build a
196 * new node and store it in the hash table, and return that.
197 */
find_node(node * nw,node * ne,node * sw,node * se)198 node *hlifealgo::find_node(node *nw, node *ne, node *sw, node *se) {
199 node *p ;
200 g_uintptr_t h = node_hash(nw,ne,sw,se) ;
201 node *pred = 0 ;
202 h = HASHMOD(h) ;
203 for (p=hashtab[h]; p; p = p->next) { /* make sure to compare nw *first* */
204 if (nw == p->nw && ne == p->ne && sw == p->sw && se == p->se) {
205 if (pred) { /* move this one to the front */
206 pred->next = p->next ;
207 p->next = hashtab[h] ;
208 hashtab[h] = p ;
209 }
210 return save(p) ;
211 }
212 pred = p ;
213 }
214 p = newnode() ;
215 p->nw = nw ;
216 p->ne = ne ;
217 p->sw = sw ;
218 p->se = se ;
219 p->res = 0 ;
220 p->next = hashtab[h] ;
221 hashtab[h] = p ;
222 hashpop++ ;
223 save(p) ;
224 if (hashpop > hashlimit)
225 resize() ;
226 return p ;
227 }
find_leaf(unsigned short nw,unsigned short ne,unsigned short sw,unsigned short se)228 leaf *hlifealgo::find_leaf(unsigned short nw, unsigned short ne,
229 unsigned short sw, unsigned short se) {
230 leaf *p ;
231 leaf *pred = 0 ;
232 g_uintptr_t h = leaf_hash(nw, ne, sw, se) ;
233 h = HASHMOD(h) ;
234 for (p=(leaf *)hashtab[h]; p; p = (leaf *)p->next) {
235 if (nw == p->nw && ne == p->ne && sw == p->sw && se == p->se &&
236 !is_node(p)) {
237 if (pred) {
238 pred->next = p->next ;
239 p->next = hashtab[h] ;
240 hashtab[h] = (node *)p ;
241 }
242 return (leaf *)save((node *)p) ;
243 }
244 pred = p ;
245 }
246 p = newleaf() ;
247 p->nw = nw ;
248 p->ne = ne ;
249 p->sw = sw ;
250 p->se = se ;
251 leafres(p) ;
252 p->isnode = 0 ;
253 p->next = hashtab[h] ;
254 hashtab[h] = (node *)p ;
255 hashpop++ ;
256 save((node *)p) ;
257 if (hashpop > hashlimit)
258 resize() ;
259 return p ;
260 }
261 /*
262 * The following routine does the same, but first it checks to see if
263 * the cached result is any good. If it is, it directly returns that.
264 * Otherwise, it figures out whether to call the leaf routine or the
265 * non-leaf routine by whether two nodes down is a leaf node or not.
266 * (We'll understand why this is a bit later.) All the sp stuff is
267 * stack pointer and garbage collection stuff.
268 */
getres(node * n,int depth)269 node *hlifealgo::getres(node *n, int depth) {
270 if (n->res)
271 return n->res ;
272 node *res = 0 ;
273 /**
274 * This routine be the only place we assign to res. We use
275 * the fact that the poll routine is *sticky* to allow us to
276 * manage unwinding the stack without munging our data
277 * structures. Note that there may be many find_nodes
278 * and getres called before we finally actually exit from
279 * here, because the stack is deep and we don't want to
280 * put checks throughout the code. Instead we need two
281 * calls here, one to prevent us going deeper, and another
282 * to prevent us from destroying the cache field.
283 */
284 if (poller->poll() || softinterrupt)
285 return zeronode(depth-1) ;
286 int sp = gsp ;
287 if (running_hperf.fastinc(depth, ngens < depth))
288 running_hperf.report(inc_hperf, verbose) ;
289 depth-- ;
290 if (ngens >= depth) {
291 if (is_node(n->nw)) {
292 res = dorecurs(n->nw, n->ne, n->sw, n->se, depth) ;
293 } else {
294 res = (node *)dorecurs_leaf((leaf *)n->nw, (leaf *)n->ne,
295 (leaf *)n->sw, (leaf *)n->se) ;
296 }
297 } else {
298 if (is_node(n->nw)) {
299 res = dorecurs_half(n->nw, n->ne, n->sw, n->se, depth) ;
300 } else if (ngens == 0) {
301 res = (node *)dorecurs_leaf_quarter((leaf *)n->nw, (leaf *)n->ne,
302 (leaf *)n->sw, (leaf *)n->se) ;
303 } else {
304 res = (node *)dorecurs_leaf_half((leaf *)n->nw, (leaf *)n->ne,
305 (leaf *)n->sw, (leaf *)n->se) ;
306 }
307 }
308 pop(sp) ;
309 if (softinterrupt ||
310 poller->isInterrupted()) // don't assign this to the cache field!
311 res = zeronode(depth) ;
312 else {
313 if (ngens < depth && halvesdone < 1000)
314 halvesdone++ ;
315 n->res = res ;
316 }
317 return res ;
318 }
319 #ifdef USEPREFETCH
setupprefetch(setup_t & su,node * nw,node * ne,node * sw,node * se)320 void hlifealgo::setupprefetch(setup_t &su, node *nw, node *ne, node *sw, node *se) {
321 su.h = node_hash(nw,ne,sw,se) ;
322 su.nw = nw ;
323 su.ne = ne ;
324 su.sw = sw ;
325 su.se = se ;
326 su.prefetch(hashtab + HASHMOD(su.h)) ;
327 }
find_node(setup_t & su)328 node *hlifealgo::find_node(setup_t &su) {
329 node *p ;
330 node *pred = 0 ;
331 g_uintptr_t h = HASHMOD(su.h) ;
332 for (p=hashtab[h]; p; p = p->next) { /* make sure to compare nw *first* */
333 if (su.nw == p->nw && su.ne == p->ne && su.sw == p->sw && su.se == p->se) {
334 if (pred) { /* move this one to the front */
335 pred->next = p->next ;
336 p->next = hashtab[h] ;
337 hashtab[h] = p ;
338 }
339 return save(p) ;
340 }
341 pred = p ;
342 }
343 p = newnode() ;
344 p->nw = su.nw ;
345 p->ne = su.ne ;
346 p->sw = su.sw ;
347 p->se = su.se ;
348 p->res = 0 ;
349 p->next = hashtab[h] ;
350 hashtab[h] = p ;
351 hashpop++ ;
352 save(p) ;
353 if (hashpop > hashlimit)
354 resize() ;
355 return p ;
356 }
dorecurs(node * n,node * ne,node * t,node * e,int depth)357 node *hlifealgo::dorecurs(node *n, node *ne, node *t, node *e, int depth) {
358 int sp = gsp ;
359 setup_t su[5] ;
360 setupprefetch(su[2], n->se, ne->sw, t->ne, e->nw) ;
361 setupprefetch(su[0], n->ne, ne->nw, n->se, ne->sw) ;
362 setupprefetch(su[1], ne->sw, ne->se, e->nw, e->ne) ;
363 setupprefetch(su[3], n->sw, n->se, t->nw, t->ne) ;
364 setupprefetch(su[4], t->ne, e->nw, t->se, e->sw) ;
365 node
366 *t00 = getres(n, depth),
367 *t01 = getres(find_node(su[0]), depth),
368 *t02 = getres(ne, depth),
369 *t12 = getres(find_node(su[1]), depth),
370 *t11 = getres(find_node(su[2]), depth),
371 *t10 = getres(find_node(su[3]), depth),
372 *t20 = getres(t, depth),
373 *t21 = getres(find_node(su[4]), depth),
374 *t22 = getres(e, depth) ;
375 setupprefetch(su[0], t11, t12, t21, t22) ;
376 setupprefetch(su[1], t10, t11, t20, t21) ;
377 setupprefetch(su[2], t00, t01, t10, t11) ;
378 setupprefetch(su[3], t01, t02, t11, t12) ;
379 node
380 *t44 = getres(find_node(su[0]), depth),
381 *t43 = getres(find_node(su[1]), depth),
382 *t33 = getres(find_node(su[2]), depth),
383 *t34 = getres(find_node(su[3]), depth) ;
384 n = find_node(t33, t34, t43, t44) ;
385 pop(sp) ;
386 return save(n) ;
387 }
388 #else
389 /*
390 * So let's say the cached way failed. How do we do it the slow way?
391 * Recursively, of course. For an n-square (composed of the four
392 * n/2-squares passed in, compute the n/2-square that is n/4
393 * generations ahead.
394 *
395 * This routine works exactly the same as the leafres() routine, only
396 * instead of working on an 8-square, we're working on an n-square,
397 * returning an n/2-square, and we build that n/2-square by first building
398 * 9 n/4-squares, use those to calculate 4 more n/4-squares, and
399 * then put these together into a new n/2-square. Simple, eh?
400 */
dorecurs(node * n,node * ne,node * t,node * e,int depth)401 node *hlifealgo::dorecurs(node *n, node *ne, node *t, node *e, int depth) {
402 int sp = gsp ;
403 node
404 *t11 = getres(find_node(n->se, ne->sw, t->ne, e->nw), depth),
405 *t00 = getres(n, depth),
406 *t01 = getres(find_node(n->ne, ne->nw, n->se, ne->sw), depth),
407 *t02 = getres(ne, depth),
408 *t12 = getres(find_node(ne->sw, ne->se, e->nw, e->ne), depth),
409 *t10 = getres(find_node(n->sw, n->se, t->nw, t->ne), depth),
410 *t20 = getres(t, depth),
411 *t21 = getres(find_node(t->ne, e->nw, t->se, e->sw), depth),
412 *t22 = getres(e, depth),
413 *t44 = getres(find_node(t11, t12, t21, t22), depth),
414 *t43 = getres(find_node(t10, t11, t20, t21), depth),
415 *t33 = getres(find_node(t00, t01, t10, t11), depth),
416 *t34 = getres(find_node(t01, t02, t11, t12), depth) ;
417 n = find_node(t33, t34, t43, t44) ;
418 pop(sp) ;
419 return save(n) ;
420 }
421 #endif
422 /*
423 * Same as above, but we only do one step instead of 2.
424 */
dorecurs_half(node * n,node * ne,node * t,node * e,int depth)425 node *hlifealgo::dorecurs_half(node *n, node *ne, node *t,
426 node *e, int depth) {
427 int sp = gsp ;
428 node
429 *t00 = getres(n, depth),
430 *t01 = getres(find_node(n->ne, ne->nw, n->se, ne->sw), depth),
431 *t10 = getres(find_node(n->sw, n->se, t->nw, t->ne), depth),
432 *t11 = getres(find_node(n->se, ne->sw, t->ne, e->nw), depth),
433 *t02 = getres(ne, depth),
434 *t12 = getres(find_node(ne->sw, ne->se, e->nw, e->ne), depth),
435 *t20 = getres(t, depth),
436 *t21 = getres(find_node(t->ne, e->nw, t->se, e->sw), depth),
437 *t22 = getres(e, depth) ;
438 if (depth > 3) {
439 n = find_node(find_node(t00->se, t01->sw, t10->ne, t11->nw),
440 find_node(t01->se, t02->sw, t11->ne, t12->nw),
441 find_node(t10->se, t11->sw, t20->ne, t21->nw),
442 find_node(t11->se, t12->sw, t21->ne, t22->nw)) ;
443 } else {
444 n = find_node((node *)find_leaf(((leaf *)t00)->se,
445 ((leaf *)t01)->sw,
446 ((leaf *)t10)->ne,
447 ((leaf *)t11)->nw),
448 (node *)find_leaf(((leaf *)t01)->se,
449 ((leaf *)t02)->sw,
450 ((leaf *)t11)->ne,
451 ((leaf *)t12)->nw),
452 (node *)find_leaf(((leaf *)t10)->se,
453 ((leaf *)t11)->sw,
454 ((leaf *)t20)->ne,
455 ((leaf *)t21)->nw),
456 (node *)find_leaf(((leaf *)t11)->se,
457 ((leaf *)t12)->sw,
458 ((leaf *)t21)->ne,
459 ((leaf *)t22)->nw)) ;
460 }
461 pop(sp) ;
462 return save(n) ;
463 }
464 /*
465 * If the node is a 16-node, then the constituents are leaves, so we
466 * need a very similar but still somewhat different subroutine. Since
467 * we do not (yet) garbage collect leaves, we don't need all that
468 * save/pop mumbo-jumbo.
469 */
dorecurs_leaf(leaf * n,leaf * ne,leaf * t,leaf * e)470 leaf *hlifealgo::dorecurs_leaf(leaf *n, leaf *ne, leaf *t, leaf *e) {
471 unsigned short
472 t00 = n->res2,
473 t01 = find_leaf(n->ne, ne->nw, n->se, ne->sw)->res2,
474 t02 = ne->res2,
475 t10 = find_leaf(n->sw, n->se, t->nw, t->ne)->res2,
476 t11 = find_leaf(n->se, ne->sw, t->ne, e->nw)->res2,
477 t12 = find_leaf(ne->sw, ne->se, e->nw, e->ne)->res2,
478 t20 = t->res2,
479 t21 = find_leaf(t->ne, e->nw, t->se, e->sw)->res2,
480 t22 = e->res2 ;
481 return find_leaf(find_leaf(t00, t01, t10, t11)->res2,
482 find_leaf(t01, t02, t11, t12)->res2,
483 find_leaf(t10, t11, t20, t21)->res2,
484 find_leaf(t11, t12, t21, t22)->res2) ;
485 }
486 /*
487 * Same as above but we only do two generations.
488 */
489 #define combine4(t00,t01,t10,t11) (unsigned short)\
490 ((((t00)<<10)&0xcc00)|(((t01)<<6)&0x3300)|(((t10)>>6)&0xcc)|(((t11)>>10)&0x33))
dorecurs_leaf_half(leaf * n,leaf * ne,leaf * t,leaf * e)491 leaf *hlifealgo::dorecurs_leaf_half(leaf *n, leaf *ne, leaf *t, leaf *e) {
492 unsigned short
493 t00 = n->res2,
494 t01 = find_leaf(n->ne, ne->nw, n->se, ne->sw)->res2,
495 t02 = ne->res2,
496 t10 = find_leaf(n->sw, n->se, t->nw, t->ne)->res2,
497 t11 = find_leaf(n->se, ne->sw, t->ne, e->nw)->res2,
498 t12 = find_leaf(ne->sw, ne->se, e->nw, e->ne)->res2,
499 t20 = t->res2,
500 t21 = find_leaf(t->ne, e->nw, t->se, e->sw)->res2,
501 t22 = e->res2 ;
502 return find_leaf(combine4(t00, t01, t10, t11),
503 combine4(t01, t02, t11, t12),
504 combine4(t10, t11, t20, t21),
505 combine4(t11, t12, t21, t22)) ;
506 }
507 /*
508 * Same as above but we only do one generation.
509 */
dorecurs_leaf_quarter(leaf * n,leaf * ne,leaf * t,leaf * e)510 leaf *hlifealgo::dorecurs_leaf_quarter(leaf *n, leaf *ne,
511 leaf *t, leaf *e) {
512 unsigned short
513 t00 = n->res1,
514 t01 = find_leaf(n->ne, ne->nw, n->se, ne->sw)->res1,
515 t02 = ne->res1,
516 t10 = find_leaf(n->sw, n->se, t->nw, t->ne)->res1,
517 t11 = find_leaf(n->se, ne->sw, t->ne, e->nw)->res1,
518 t12 = find_leaf(ne->sw, ne->se, e->nw, e->ne)->res1,
519 t20 = t->res1,
520 t21 = find_leaf(t->ne, e->nw, t->se, e->sw)->res1,
521 t22 = e->res1 ;
522 return find_leaf(combine4(t00, t01, t10, t11),
523 combine4(t01, t02, t11, t12),
524 combine4(t10, t11, t20, t21),
525 combine4(t11, t12, t21, t22)) ;
526 }
527 /*
528 * We keep free nodes in a linked list for allocation, and we allocate
529 * them 1000 at a time.
530 */
newnode()531 node *hlifealgo::newnode() {
532 node *r ;
533 if (freenodes == 0) {
534 int i ;
535 freenodes = (node *)calloc(1001, sizeof(node)) ;
536 if (freenodes == 0)
537 lifefatal("Out of memory; try reducing the hash memory limit.") ;
538 alloced += 1001 * sizeof(node) ;
539 freenodes->next = nodeblocks ;
540 nodeblocks = freenodes++ ;
541 for (i=0; i<999; i++) {
542 freenodes[1].next = freenodes ;
543 freenodes++ ;
544 }
545 totalthings += 1000 ;
546 }
547 if (freenodes->next == 0 && alloced + 1000 * sizeof(node) > maxmem &&
548 okaytogc) {
549 do_gc(0) ;
550 }
551 r = freenodes ;
552 freenodes = freenodes->next ;
553 return r ;
554 }
555 /*
556 * Leaves are the same.
557 */
newleaf()558 leaf *hlifealgo::newleaf() {
559 leaf *r = (leaf *)newnode() ;
560 new(&(r->leafpop))bigint ;
561 return r ;
562 }
563 /*
564 * Sometimes we want the new node or leaf to be automatically cleared
565 * for us.
566 */
newclearednode()567 node *hlifealgo::newclearednode() {
568 return (node *)memset(newnode(), 0, sizeof(node)) ;
569 }
newclearedleaf()570 leaf *hlifealgo::newclearedleaf() {
571 leaf *r = (leaf *)newclearednode() ;
572 new(&(r->leafpop))bigint ;
573 return r ;
574 }
hlifealgo()575 hlifealgo::hlifealgo() {
576 int i ;
577 /*
578 * The population of one-bits in an integer is one more than the
579 * population of one-bits in the integer with one fewer bit set,
580 * and we can turn off a bit by anding an integer with the next
581 * lower integer.
582 */
583 if (shortpop[1] == 0)
584 for (i=1; i<65536; i++)
585 shortpop[i] = shortpop[i & (i - 1)] + 1 ;
586 hashprime = nexthashsize(1000) ;
587 #ifndef PRIMEMOD
588 hashmask = hashprime - 1 ;
589 #endif
590 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
591 hashpop = 0 ;
592 hashtab = (node **)calloc(hashprime, sizeof(node *)) ;
593 if (hashtab == 0)
594 lifefatal("Out of memory (1).") ;
595 alloced = hashprime * sizeof(node *) ;
596 ngens = 0 ;
597 stacksize = 0 ;
598 halvesdone = 0 ;
599 nzeros = 0 ;
600 stack = 0 ;
601 gsp = 0 ;
602 maxmem = 256 * 1024 * 1024 ;
603 freenodes = 0 ;
604 okaytogc = 0 ;
605 totalthings = 0 ;
606 nodeblocks = 0 ;
607 zeronodea = 0 ;
608 ruletable = hliferules.rule0 ;
609 /*
610 * We initialize our universe to be a 16-square. We are in drawing
611 * mode at this point.
612 */
613 root = (node *)newclearednode() ;
614 population = 0 ;
615 generation = 0 ;
616 increment = 1 ;
617 setincrement = 1 ;
618 nonpow2 = 1 ;
619 pow2step = 1 ;
620 llsize = 0 ;
621 depth = 3 ;
622 hashed = 0 ;
623 popValid = 0 ;
624 needPop = 0 ;
625 inGC = 0 ;
626 cacheinvalid = 0 ;
627 gccount = 0 ;
628 gcstep = 0 ;
629 running_hperf.clear() ;
630 inc_hperf = running_hperf ;
631 step_hperf = running_hperf ;
632 softinterrupt = 0 ;
633 }
634 /**
635 * Destructor frees memory.
636 */
~hlifealgo()637 hlifealgo::~hlifealgo() {
638 free(hashtab) ;
639 while (nodeblocks) {
640 node *r = nodeblocks ;
641 nodeblocks = nodeblocks->next ;
642 free(r) ;
643 }
644 if (zeronodea)
645 free(zeronodea) ;
646 if (stack)
647 free(stack) ;
648 if (llsize) {
649 delete [] llxb ;
650 delete [] llyb ;
651 }
652 }
653 /**
654 * Set increment.
655 */
setIncrement(bigint inc)656 void hlifealgo::setIncrement(bigint inc) {
657 if (inc < increment)
658 softinterrupt = 1 ;
659 increment = inc ;
660 }
661 /**
662 * Do a step.
663 */
step()664 void hlifealgo::step() {
665 poller->bailIfCalculating() ;
666 // we use while here because the increment may be changed while we are
667 // doing the hashtable sweep; if that happens, we may need to sweep
668 // again.
669 while (1) {
670 int cleareddownto = 1000000000 ;
671 softinterrupt = 0 ;
672 while (increment != setincrement) {
673 bigint pendingincrement = increment ;
674 int newpow2 = 0 ;
675 bigint t = pendingincrement ;
676 while (t > 0 && t.even()) {
677 newpow2++ ;
678 t.div2() ;
679 }
680 nonpow2 = t.low31() ;
681 if (t != nonpow2)
682 lifefatal("bad increment") ;
683 int downto = newpow2 ;
684 if (ngens < newpow2)
685 downto = ngens ;
686 if (newpow2 != ngens && cleareddownto > downto) {
687 new_ngens(newpow2) ;
688 cleareddownto = downto ;
689 } else {
690 ngens = newpow2 ;
691 }
692 setincrement = pendingincrement ;
693 pow2step = 1 ;
694 while (newpow2--)
695 pow2step += pow2step ;
696 }
697 gcstep = 0 ;
698 running_hperf.genval = generation.todouble() ;
699 for (int i=0; i<nonpow2; i++) {
700 node *newroot = runpattern() ;
701 if (newroot == 0 || softinterrupt || poller->isInterrupted()) // we *were* interrupted
702 break ;
703 popValid = 0 ;
704 root = newroot ;
705 depth = node_depth(root) ;
706 }
707 running_hperf.reportStep(step_hperf, inc_hperf, generation.todouble(), verbose) ;
708 if (poller->isInterrupted() || !softinterrupt)
709 break ;
710 }
711 }
setcurrentstate(void * n)712 void hlifealgo::setcurrentstate(void *n) {
713 if (root != (node *)n) {
714 root = (node *)n ;
715 depth = node_depth(root) ;
716 popValid = 0 ;
717 }
718 }
719 /*
720 * Set the max memory
721 */
setMaxMemory(int newmemlimit)722 void hlifealgo::setMaxMemory(int newmemlimit) {
723 if (newmemlimit < 10)
724 newmemlimit = 10 ;
725 #ifndef GOLLY64BIT
726 else if (newmemlimit > 4000)
727 newmemlimit = 4000 ;
728 #endif
729 g_uintptr_t newlimit = ((g_uintptr_t)newmemlimit) << 20 ;
730 if (alloced > newlimit) {
731 lifewarning("Sorry, more memory currently used than allowed.") ;
732 return ;
733 }
734 maxmem = newlimit ;
735 hashlimit = (g_uintptr_t)(maxloadfactor * hashprime) ;
736 }
737 /**
738 * Clear everything.
739 */
clearall()740 void hlifealgo::clearall() {
741 lifefatal("clearall not implemented yet") ;
742 }
743 /*
744 * This routine expands our universe by a factor of two, maintaining
745 * centering. We use four new nodes, and *reuse* the root so this cannot
746 * be called after we've started hashing.
747 */
pushroot_1()748 void hlifealgo::pushroot_1() {
749 node *t ;
750 t = newclearednode() ;
751 t->se = root->nw ;
752 root->nw = t ;
753 t = newclearednode() ;
754 t->sw = root->ne ;
755 root->ne = t ;
756 t = newclearednode() ;
757 t->ne = root->sw ;
758 root->sw = t ;
759 t = newclearednode() ;
760 t->nw = root->se ;
761 root->se = t ;
762 depth++ ;
763 }
764 /*
765 * Return the depth of this node (2 is 8x8).
766 */
node_depth(node * n)767 int hlifealgo::node_depth(node *n) {
768 int depth = 2 ;
769 while (is_node(n)) {
770 depth++ ;
771 n = n->nw ;
772 }
773 return depth ;
774 }
775 /*
776 * This routine returns the canonical clear space node at a particular
777 * depth.
778 */
zeronode(int depth)779 node *hlifealgo::zeronode(int depth) {
780 while (depth >= nzeros) {
781 int nnzeros = 2 * nzeros + 10 ;
782 zeronodea = (node **)realloc(zeronodea,
783 nnzeros * sizeof(node *)) ;
784 if (zeronodea == 0)
785 lifefatal("Out of memory (2).") ;
786 alloced += (nnzeros - nzeros) * sizeof(node *) ;
787 while (nzeros < nnzeros)
788 zeronodea[nzeros++] = 0 ;
789 }
790 if (zeronodea[depth] == 0) {
791 if (depth == 2) {
792 zeronodea[depth] = (node *)find_leaf(0, 0, 0, 0) ;
793 } else {
794 node *z = zeronode(depth-1) ;
795 zeronodea[depth] = find_node(z, z, z, z) ;
796 }
797 }
798 return zeronodea[depth] ;
799 }
800 /*
801 * Same, but with hashed nodes.
802 */
pushroot(node * n)803 node *hlifealgo::pushroot(node *n) {
804 int depth = node_depth(n) ;
805 zeronode(depth+1) ; // ensure enough zero nodes for rendering
806 node *z = zeronode(depth-1) ;
807 return find_node(find_node(z, z, z, n->nw),
808 find_node(z, z, n->ne, z),
809 find_node(z, n->sw, z, z),
810 find_node(n->se, z, z, z)) ;
811 }
812 /*
813 * Here is our recursive routine to set a bit in our universe. We
814 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
815 * but really not all that complicated. We allocate new nodes and
816 * leaves on our way down.
817 *
818 * Note that at this point our universe lives outside the hash table
819 * and has not been canonicalized, and that many of the pointers in
820 * the nodes can be null. We'll patch this up in due course.
821 */
gsetbit(node * n,int x,int y,int newstate,int depth)822 node *hlifealgo::gsetbit(node *n, int x, int y, int newstate, int depth) {
823 if (depth == 2) {
824 leaf *l = (leaf *)n ;
825 if (hashed) {
826 unsigned short nw = l->nw ;
827 unsigned short sw = l->sw ;
828 unsigned short ne = l->ne ;
829 unsigned short se = l->se ;
830 if (newstate) {
831 if (x < 0)
832 if (y < 0)
833 sw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
834 else
835 nw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
836 else
837 if (y < 0)
838 se |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
839 else
840 ne |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
841 } else {
842 if (x < 0)
843 if (y < 0)
844 sw &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
845 else
846 nw &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
847 else
848 if (y < 0)
849 se &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
850 else
851 ne &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
852 }
853 return save((node *)find_leaf(nw, ne, sw, se)) ;
854 }
855 if (newstate) {
856 if (x < 0)
857 if (y < 0)
858 l->sw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
859 else
860 l->nw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
861 else
862 if (y < 0)
863 l->se |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
864 else
865 l->ne |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
866 } else {
867 if (x < 0)
868 if (y < 0)
869 l->sw &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
870 else
871 l->nw &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
872 else
873 if (y < 0)
874 l->se &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
875 else
876 l->ne &= ~(1 << (3 - (x & 3) + 4 * (y & 3))) ;
877 }
878 return (node *)l ;
879 } else {
880 unsigned int w = 0, wh = 0 ;
881 if (depth >= 32) {
882 if (depth == 32)
883 wh = 0x80000000 ;
884 } else {
885 w = 1 << depth ;
886 wh = 1 << (depth - 1) ;
887 }
888 depth-- ;
889 node **nptr ;
890 if (depth+1 == this->depth || depth < 31) {
891 if (x < 0) {
892 if (y < 0)
893 nptr = &(n->sw) ;
894 else
895 nptr = &(n->nw) ;
896 } else {
897 if (y < 0)
898 nptr = &(n->se) ;
899 else
900 nptr = &(n->ne) ;
901 }
902 } else {
903 if (x >= 0) {
904 if (y >= 0)
905 nptr = &(n->sw) ;
906 else
907 nptr = &(n->nw) ;
908 } else {
909 if (y >= 0)
910 nptr = &(n->se) ;
911 else
912 nptr = &(n->ne) ;
913 }
914 }
915 if (*nptr == 0) {
916 if (depth == 2)
917 *nptr = (node *)newclearedleaf() ;
918 else
919 *nptr = newclearednode() ;
920 }
921 node *s = gsetbit(*nptr, (x & (w - 1)) - wh,
922 (y & (w - 1)) - wh, newstate, depth) ;
923 if (hashed) {
924 node *nw = (nptr == &(n->nw) ? s : n->nw) ;
925 node *sw = (nptr == &(n->sw) ? s : n->sw) ;
926 node *ne = (nptr == &(n->ne) ? s : n->ne) ;
927 node *se = (nptr == &(n->se) ? s : n->se) ;
928 n = save(find_node(nw, ne, sw, se)) ;
929 } else {
930 *nptr = s ;
931 }
932 return n ;
933 }
934 }
935 /*
936 * Here is our recursive routine to get a bit in our universe. We
937 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
938 * but really not all that complicated.
939 */
getbit(node * n,int x,int y,int depth)940 int hlifealgo::getbit(node *n, int x, int y, int depth) {
941 struct node tnode ;
942 while (depth >= 32) {
943 tnode.nw = n->nw->se ;
944 tnode.ne = n->ne->sw ;
945 tnode.sw = n->sw->ne ;
946 tnode.se = n->se->nw ;
947 n = &tnode ;
948 depth-- ;
949 }
950 if (depth == 2) {
951 leaf *l = (leaf *)n ;
952 int test = 0 ;
953 if (x < 0)
954 if (y < 0)
955 test = (l->sw & (1 << (3 - (x & 3) + 4 * (y & 3)))) ;
956 else
957 test = (l->nw & (1 << (3 - (x & 3) + 4 * (y & 3)))) ;
958 else
959 if (y < 0)
960 test = (l->se & (1 << (3 - (x & 3) + 4 * (y & 3)))) ;
961 else
962 test = (l->ne & (1 << (3 - (x & 3) + 4 * (y & 3)))) ;
963 if (test)
964 return 1 ;
965 return 0 ;
966 } else {
967 unsigned int w = 0, wh = 0 ;
968 if (depth >= 32) {
969 if (depth == 32)
970 wh = 0x80000000 ;
971 } else {
972 w = 1 << depth ;
973 wh = 1 << (depth - 1) ;
974 }
975 depth-- ;
976 node *nptr ;
977 if (x < 0) {
978 if (y < 0)
979 nptr = n->sw ;
980 else
981 nptr = n->nw ;
982 } else {
983 if (y < 0)
984 nptr = n->se ;
985 else
986 nptr = n->ne ;
987 }
988 if (nptr == 0 || nptr == zeronode(depth))
989 return 0 ;
990 return getbit(nptr, (x & (w - 1)) - wh, (y & (w - 1)) - wh, depth) ;
991 }
992 }
993 /*
994 * Here is our recursive routine to get the next bit in our universe. We
995 * pass in a depth, and walk the space. Again, a lot of bit twiddling,
996 * but really not all that complicated.
997 */
nextbit(node * n,int x,int y,int depth)998 int hlifealgo::nextbit(node *n, int x, int y, int depth) {
999 if (n == 0 || n == zeronode(depth))
1000 return -1 ;
1001 if (depth == 2) {
1002 leaf *l = (leaf *)n ;
1003 int test = 0 ;
1004 if (y < 0)
1005 test = (((l->sw >> (4 * (y & 3))) & 15) << 4) |
1006 ((l->se >> (4 * (y & 3))) & 15) ;
1007 else
1008 test = (((l->nw >> (4 * (y & 3))) & 15) << 4) |
1009 ((l->ne >> (4 * (y & 3))) & 15) ;
1010 test &= (1 << (4 - x)) - 1 ;
1011 if (test) {
1012 int r = 0 ;
1013 int b = 1 << (3 - x) ;
1014 while ((test & b) == 0) {
1015 r++ ;
1016 b >>= 1 ;
1017 }
1018 return r ;
1019 }
1020 return -1 ; // none found
1021 } else {
1022 unsigned int w = 0, wh = 0 ;
1023 w = 1 << depth ;
1024 wh = 1 << (depth - 1) ;
1025 node *lft, *rght ;
1026 depth-- ;
1027 if (y < 0) {
1028 lft = n->sw ;
1029 rght = n->se ;
1030 } else {
1031 lft = n->nw ;
1032 rght = n->ne ;
1033 }
1034 int r = 0 ;
1035 if (x < 0) {
1036 int t = nextbit(lft, (x & (w-1)) - wh,
1037 (y & (w - 1)) - wh, depth) ;
1038 if (t >= 0)
1039 return t ;
1040 r = -x ;
1041 x = 0 ;
1042 }
1043 int t = nextbit(rght, (x & (w-1)) - wh,
1044 (y & (w - 1)) - wh, depth) ;
1045 if (t >= 0)
1046 return r + t ;
1047 return -1 ;
1048 }
1049 }
1050 /*
1051 * Our nonrecurse top-level bit setting routine simply expands the
1052 * universe as necessary to encompass the passed-in coordinates, and
1053 * then invokes the recursive setbit. Right now it works hashed or
1054 * unhashed (but it's faster when unhashed). We also turn on the inGC
1055 * flag to inhibit popcount.
1056 */
setcell(int x,int y,int newstate)1057 int hlifealgo::setcell(int x, int y, int newstate) {
1058 if (newstate & ~1)
1059 return -1 ;
1060 if (hashed) {
1061 clearstack() ;
1062 save(root) ;
1063 okaytogc = 1 ;
1064 }
1065 inGC = 1 ;
1066 y = - y ;
1067 int sx = x ;
1068 int sy = y ;
1069 if (depth <= 31) {
1070 sx >>= depth ;
1071 sy >>= depth ;
1072 } else {
1073 sx >>= 31 ;
1074 sy >>= 31 ;
1075 }
1076 while (sx > 0 || sx < -1 || sy > 0 || sy < -1) {
1077 if (hashed) {
1078 root = save(pushroot(root)) ;
1079 depth++ ;
1080 } else {
1081 pushroot_1() ;
1082 }
1083 sx >>= 1 ;
1084 sy >>= 1 ;
1085 }
1086 root = gsetbit(root, x, y, newstate, depth) ;
1087 if (hashed) {
1088 okaytogc = 0 ;
1089 }
1090 return 0 ;
1091 }
1092 /*
1093 * Our nonrecurse top-level bit getting routine.
1094 */
getcell(int x,int y)1095 int hlifealgo::getcell(int x, int y) {
1096 y = - y ;
1097 int sx = x ;
1098 int sy = y ;
1099 if (depth <= 31) {
1100 sx >>= depth ;
1101 sy >>= depth ;
1102 } else {
1103 sx >>= 31 ;
1104 sy >>= 31 ;
1105 }
1106 if (sx > 0 || sx < -1 || sy > 0 || sy < -1)
1107 return 0 ;
1108 return getbit(root, x, y, depth) ;
1109 }
1110 /*
1111 * A recursive bit getting routine, but this one returns the
1112 * number of pixels to the right to the next set cell in the
1113 * current universe, or -1 if none set to the right, or if
1114 * the next set pixel is out of range.
1115 */
nextcell(int x,int y,int & v)1116 int hlifealgo::nextcell(int x, int y, int &v) {
1117 v = 1 ;
1118 y = - y ;
1119 int sx = x ;
1120 int sy = y ;
1121 if (depth <= 31) {
1122 sx >>= depth ;
1123 sy >>= depth ;
1124 } else {
1125 sx >>= 31 ;
1126 sy >>= 31 ;
1127 }
1128 while (sx > 0 || sx < -1 || sy > 0 || sy < -1) {
1129 if (hashed) {
1130 root = save(pushroot(root)) ;
1131 depth++ ;
1132 } else {
1133 pushroot_1() ;
1134 }
1135 sx >>= 1 ;
1136 sy >>= 1 ;
1137 }
1138 if (depth > 30) {
1139 struct node tnode = *root ;
1140 int mdepth = depth ;
1141 while (mdepth > 30) {
1142 tnode.nw = tnode.nw->se ;
1143 tnode.ne = tnode.ne->sw ;
1144 tnode.sw = tnode.sw->ne ;
1145 tnode.se = tnode.se->nw ;
1146 mdepth-- ;
1147 }
1148 return nextbit(&tnode, x, y, mdepth) ;
1149 }
1150 return nextbit(root, x, y, depth) ;
1151 }
1152 /*
1153 * Canonicalize a universe by filling in the null pointers and then
1154 * invoking find_node on each node. Drops the original universe on
1155 * the floor [big deal, it's probably small anyway].
1156 */
hashpattern(node * root,int depth)1157 node *hlifealgo::hashpattern(node *root, int depth) {
1158 node *r ;
1159 if (root == 0) {
1160 r = zeronode(depth) ;
1161 } else if (depth == 2) {
1162 leaf *n = (leaf *)root ;
1163 r = (node *)find_leaf(n->nw, n->ne, n->sw, n->se) ;
1164 n->next = freenodes ;
1165 freenodes = root ;
1166 } else {
1167 depth-- ;
1168 r = find_node(hashpattern(root->nw, depth),
1169 hashpattern(root->ne, depth),
1170 hashpattern(root->sw, depth),
1171 hashpattern(root->se, depth)) ;
1172 root->next = freenodes ;
1173 freenodes = root ;
1174 }
1175 return r ;
1176 }
endofpattern()1177 void hlifealgo::endofpattern() {
1178 poller->bailIfCalculating() ;
1179 if (!hashed) {
1180 root = hashpattern(root, depth) ;
1181 zeronode(depth) ;
1182 hashed = 1 ;
1183 }
1184 popValid = 0 ;
1185 needPop = 0 ;
1186 inGC = 0 ;
1187 }
ensure_hashed()1188 void hlifealgo::ensure_hashed() {
1189 if (!hashed)
1190 endofpattern() ;
1191 }
1192 /*
1193 * Pop off any levels we don't need.
1194 */
popzeros(node * n)1195 node *hlifealgo::popzeros(node *n) {
1196 int depth = node_depth(n) ;
1197 while (depth > 3) {
1198 node *z = zeronode(depth-2) ;
1199 if (n->nw->nw == z && n->nw->ne == z && n->nw->sw == z &&
1200 n->ne->nw == z && n->ne->ne == z && n->ne->se == z &&
1201 n->sw->nw == z && n->sw->sw == z && n->sw->se == z &&
1202 n->se->ne == z && n->se->sw == z && n->se->se == z) {
1203 depth-- ;
1204 n = find_node(n->nw->se, n->ne->sw, n->sw->ne, n->se->nw) ;
1205 } else {
1206 break ;
1207 }
1208 }
1209 return n ;
1210 }
1211 /*
1212 * A lot of the routines from here on down traverse the universe, hanging
1213 * information off the nodes. The way they generally do so is by using
1214 * (or abusing) the cache (res) field, and the least significant bit of
1215 * the hash next field (as a visited bit).
1216 */
1217 #define marked(n) (1 & (g_uintptr_t)(n)->next)
1218 #define mark(n) ((n)->next = (node *)(1 | (g_uintptr_t)(n)->next))
1219 #define clearmark(n) ((n)->next = (node *)(~1 & (g_uintptr_t)(n)->next))
1220 #define clearmarkbit(p) ((node *)(~1 & (g_uintptr_t)(p)))
1221 /*
1222 * Sometimes we want to use *res* instead of next to mark. You cannot
1223 * do this to leaves, though.
1224 */
1225 #define marked2(n) (3 & (g_uintptr_t)(n)->res)
1226 #define mark2(n) ((n)->res = (node *)(1 | (g_uintptr_t)(n)->res))
1227 #define mark2v(n,v) ((n)->res = (node *)(v | (g_uintptr_t)(n)->res))
1228 #define clearmark2(n) ((n)->res = (node *)(~3 & (g_uintptr_t)(n)->res))
unhash_node(node * n)1229 void hlifealgo::unhash_node(node *n) {
1230 node *p ;
1231 g_uintptr_t h = node_hash(n->nw,n->ne,n->sw,n->se) ;
1232 node *pred = 0 ;
1233 h = HASHMOD(h) ;
1234 for (p=hashtab[h]; (!is_node(p) || !marked2(p)) && p; p = p->next) {
1235 if (p == n) {
1236 if (pred)
1237 pred->next = p->next ;
1238 else
1239 hashtab[h] = p->next ;
1240 return ;
1241 }
1242 pred = p ;
1243 }
1244 lifefatal("Didn't find node to unhash") ;
1245 }
unhash_node2(node * n)1246 void hlifealgo::unhash_node2(node *n) {
1247 node *p ;
1248 g_uintptr_t h = node_hash(n->nw,n->ne,n->sw,n->se) ;
1249 node *pred = 0 ;
1250 h = HASHMOD(h) ;
1251 for (p=hashtab[h]; p; p = p->next) {
1252 if (p == n) {
1253 if (pred)
1254 pred->next = p->next ;
1255 else
1256 hashtab[h] = p->next ;
1257 return ;
1258 }
1259 pred = p ;
1260 }
1261 lifefatal("Didn't find node to unhash 2") ;
1262 }
rehash_node(node * n)1263 void hlifealgo::rehash_node(node *n) {
1264 g_uintptr_t h = node_hash(n->nw,n->ne,n->sw,n->se) ;
1265 h = HASHMOD(h) ;
1266 n->next = hashtab[h] ;
1267 hashtab[h] = n ;
1268 }
1269 /*
1270 * This recursive routine calculates the population by hanging the
1271 * population on marked nodes.
1272 */
calcpop(node * root,int depth)1273 const bigint &hlifealgo::calcpop(node *root, int depth) {
1274 if (root == zeronode(depth))
1275 return bigint::zero ;
1276 if (depth == 2)
1277 return ((leaf *)root)->leafpop ;
1278 if (marked2(root))
1279 return *(bigint*)&(root->next) ;
1280 depth-- ;
1281 if (root->next == 0)
1282 mark2v(root, 3) ;
1283 else {
1284 unhash_node(root) ;
1285 mark2(root) ;
1286 }
1287 /**
1288 * We use allocate-in-place bigint constructor here to initialize the
1289 * node. This should compile to a single instruction.
1290 */
1291 new(&(root->next))bigint(
1292 calcpop(root->nw, depth), calcpop(root->ne, depth),
1293 calcpop(root->sw, depth), calcpop(root->se, depth)) ;
1294 return *(bigint *)&(root->next) ;
1295 }
1296 /*
1297 * Call this after doing something that unhashes nodes in order to
1298 * use the next field as a temp pointer.
1299 */
aftercalcpop2(node * root,int depth)1300 void hlifealgo::aftercalcpop2(node *root, int depth) {
1301 if (depth == 2 || root == zeronode(depth))
1302 return ;
1303 int v = marked2(root) ;
1304 if (v) {
1305 clearmark2(root) ;
1306 depth-- ;
1307 if (depth > 2) {
1308 aftercalcpop2(root->nw, depth) ;
1309 aftercalcpop2(root->ne, depth) ;
1310 aftercalcpop2(root->sw, depth) ;
1311 aftercalcpop2(root->se, depth) ;
1312 }
1313 ((bigint *)&(root->next))->~bigint() ;
1314 if (v == 3)
1315 root->next = 0 ;
1316 else
1317 rehash_node(root) ;
1318 }
1319 }
1320 /*
1321 * Call this after writing macrocell.
1322 */
afterwritemc(node * root,int depth)1323 void hlifealgo::afterwritemc(node *root, int depth) {
1324 if (root == zeronode(depth))
1325 return ;
1326 if (depth == 2) {
1327 root->nw = 0 ;
1328 return ;
1329 }
1330 if (marked2(root)) {
1331 clearmark2(root) ;
1332 depth-- ;
1333 afterwritemc(root->nw, depth) ;
1334 afterwritemc(root->ne, depth) ;
1335 afterwritemc(root->sw, depth) ;
1336 afterwritemc(root->se, depth) ;
1337 rehash_node(root) ;
1338 }
1339 }
1340 /*
1341 * This top level routine calculates the population of a universe.
1342 */
calcPopulation()1343 void hlifealgo::calcPopulation() {
1344 int depth ;
1345 ensure_hashed() ;
1346 depth = node_depth(root) ;
1347 population = calcpop(root, depth) ;
1348 aftercalcpop2(root, depth) ;
1349 }
1350 /*
1351 * Is the universe empty?
1352 */
isEmpty()1353 int hlifealgo::isEmpty() {
1354 ensure_hashed() ;
1355 return root == zeronode(depth) ;
1356 }
1357 /*
1358 * This routine marks a node as needed to be saved.
1359 */
save(node * n)1360 node *hlifealgo::save(node *n) {
1361 if (gsp >= stacksize) {
1362 int nstacksize = stacksize * 2 + 100 ;
1363 alloced += sizeof(node *)*(nstacksize-stacksize) ;
1364 stack = (node **)realloc(stack, nstacksize * sizeof(node *)) ;
1365 if (stack == 0)
1366 lifefatal("Out of memory (3).") ;
1367 stacksize = nstacksize ;
1368 }
1369 stack[gsp++] = n ;
1370 return n ;
1371 }
1372 /*
1373 * This routine pops the stack back to a previous depth.
1374 */
pop(int n)1375 void hlifealgo::pop(int n) {
1376 gsp = n ;
1377 }
1378 /*
1379 * This routine clears the stack altogether.
1380 */
clearstack()1381 void hlifealgo::clearstack() {
1382 gsp = 0 ;
1383 }
1384 /*
1385 * Do a gc. Walk down from all nodes reachable on the stack, saveing
1386 * them by setting the odd bit on the next link. Then, walk the hash,
1387 * eliminating the res from everything that's not saveed, and moving
1388 * the nodes from the hash to the freelist as appropriate. Finally,
1389 * walk the hash again, clearing the low order bits in the next pointers.
1390 */
gc_mark(node * root,int invalidate)1391 void hlifealgo::gc_mark(node *root, int invalidate) {
1392 if (!marked(root)) {
1393 mark(root) ;
1394 if (is_node(root)) {
1395 gc_mark(root->nw, invalidate) ;
1396 gc_mark(root->ne, invalidate) ;
1397 gc_mark(root->sw, invalidate) ;
1398 gc_mark(root->se, invalidate) ;
1399 if (root->res) {
1400 if (invalidate)
1401 root->res = 0 ;
1402 else
1403 gc_mark(root->res, invalidate) ;
1404 }
1405 }
1406 }
1407 }
1408 /**
1409 * If the invalidate flag is set, we want to kill *all* cache entries
1410 * and recalculate all leaves.
1411 */
do_gc(int invalidate)1412 void hlifealgo::do_gc(int invalidate) {
1413 int i ;
1414 g_uintptr_t freed_nodes=0 ;
1415 node *p, *pp ;
1416 inGC = 1 ;
1417 gccount++ ;
1418 gcstep++ ;
1419 if (verbose) {
1420 if (gcstep > 1)
1421 sprintf(statusline, "GC #%d(%d)", gccount, gcstep) ;
1422 else
1423 sprintf(statusline, "GC #%d", gccount) ;
1424 lifestatus(statusline) ;
1425 }
1426 for (i=nzeros-1; i>=0; i--)
1427 if (zeronodea[i] != 0)
1428 break ;
1429 if (i >= 0)
1430 gc_mark(zeronodea[i], 0) ; // never invalidate zeronode
1431 if (root != 0)
1432 gc_mark(root, invalidate) ; // pick up the root
1433 for (i=0; i<gsp; i++) {
1434 poller->poll() ;
1435 gc_mark(stack[i], invalidate) ;
1436 }
1437 for (i=0; i<timeline.framecount; i++)
1438 gc_mark((node *)timeline.frames[i], invalidate) ;
1439 hashpop = 0 ;
1440 memset(hashtab, 0, sizeof(node *) * hashprime) ;
1441 freenodes = 0 ;
1442 for (p=nodeblocks; p; p=p->next) {
1443 poller->poll() ;
1444 for (pp=p+1, i=1; i<1001; i++, pp++) {
1445 if (marked(pp)) {
1446 g_uintptr_t h = 0 ;
1447 if (pp->nw) { /* yes, it's a node */
1448 h = HASHMOD(node_hash(pp->nw, pp->ne, pp->sw, pp->se)) ;
1449 } else {
1450 leaf *lp = (leaf *)pp ;
1451 if (invalidate)
1452 leafres(lp) ;
1453 h = HASHMOD(leaf_hash(lp->nw, lp->ne, lp->sw, lp->se)) ;
1454 }
1455 pp->next = hashtab[h] ;
1456 hashtab[h] = pp ;
1457 hashpop++ ;
1458 } else {
1459 pp->next = freenodes ;
1460 freenodes = pp ;
1461 freed_nodes++ ;
1462 }
1463 }
1464 }
1465 inGC = 0 ;
1466 if (verbose) {
1467 double perc = (double)freed_nodes / (double)totalthings * 100.0 ;
1468 sprintf(statusline+strlen(statusline), " freed %g percent (%" PRIuPTR ").",
1469 perc, freed_nodes) ;
1470 lifestatus(statusline) ;
1471 }
1472 if (needPop) {
1473 calcPopulation() ;
1474 popValid = 1 ;
1475 needPop = 0 ;
1476 poller->updatePop() ;
1477 }
1478 }
1479 /*
1480 * Clear the cache bits down to the appropriate level, marking the
1481 * nodes we've handled.
1482 */
clearcache(node * n,int depth,int clearto)1483 void hlifealgo::clearcache(node *n, int depth, int clearto) {
1484 if (!marked(n)) {
1485 mark(n) ;
1486 if (depth > 3) {
1487 depth-- ;
1488 poller->poll() ;
1489 clearcache(n->nw, depth, clearto) ;
1490 clearcache(n->ne, depth, clearto) ;
1491 clearcache(n->sw, depth, clearto) ;
1492 clearcache(n->se, depth, clearto) ;
1493 if (n->res)
1494 clearcache(n->res, depth, clearto) ;
1495 }
1496 if (depth >= clearto)
1497 n->res = 0 ;
1498 }
1499 }
1500 /*
1501 * Clear the entire cache of everything, and recalculate all leaves.
1502 * This can be very expensive.
1503 */
clearcache()1504 void hlifealgo::clearcache() {
1505 cacheinvalid = 1 ;
1506 }
1507 /*
1508 * Change the ngens value. Requires us to walk the hash, clearing
1509 * the cache fields of any nodes that do not have the appropriate
1510 * values.
1511 */
new_ngens(int newval)1512 void hlifealgo::new_ngens(int newval) {
1513 g_uintptr_t i ;
1514 node *p, *pp ;
1515 int clearto = ngens ;
1516 if (newval > ngens && halvesdone == 0) {
1517 ngens = newval ;
1518 return ;
1519 }
1520 #ifndef NOGCBEFOREINC
1521 do_gc(0) ;
1522 #endif
1523 if (verbose) {
1524 strcpy(statusline, "Changing increment...") ;
1525 lifestatus(statusline) ;
1526 }
1527 if (newval < clearto)
1528 clearto = newval ;
1529 clearto++ ; /* clear this depth and above */
1530 if (clearto < 3)
1531 clearto = 3 ;
1532 ngens = newval ;
1533 inGC = 1 ;
1534 for (i=0; i<hashprime; i++)
1535 for (p=hashtab[i]; p; p=clearmarkbit(p->next))
1536 if (is_node(p) && !marked(p))
1537 clearcache(p, node_depth(p), clearto) ;
1538 for (p=nodeblocks; p; p=p->next) {
1539 poller->poll() ;
1540 for (pp=p+1, i=1; i<1001; i++, pp++)
1541 clearmark(pp) ;
1542 }
1543 halvesdone = 0 ;
1544 inGC = 0 ;
1545 if (needPop) {
1546 calcPopulation() ;
1547 popValid = 1 ;
1548 needPop = 0 ;
1549 poller->updatePop() ;
1550 }
1551 if (verbose) {
1552 strcpy(statusline+strlen(statusline), " done.") ;
1553 lifestatus(statusline) ;
1554 }
1555 }
1556 /*
1557 * Return log2.
1558 */
log2(unsigned int n)1559 int hlifealgo::log2(unsigned int n) {
1560 int r = 0 ;
1561 while ((n & 1) == 0) {
1562 n >>= 1 ;
1563 r++ ;
1564 }
1565 if (n != 1) {
1566 lifefatal("Expected power of two!") ;
1567 }
1568 return r ;
1569 }
1570 static bigint negone = -1 ;
getPopulation()1571 const bigint &hlifealgo::getPopulation() {
1572 // note: if called during gc, then we cannot call calcPopulation
1573 // since that will mess up the gc.
1574 if (!popValid) {
1575 if (inGC) {
1576 needPop = 1 ;
1577 return negone ;
1578 } else if (poller->isCalculating()) {
1579 // AKT: avoid calling poller->bailIfCalculating
1580 return negone ;
1581 } else {
1582 calcPopulation() ;
1583 popValid = 1 ;
1584 needPop = 0 ;
1585 }
1586 }
1587 return population ;
1588 }
1589 /*
1590 * Finally, we get to run the pattern. We first ensure that all
1591 * clearspace nodes and the input pattern is never garbage
1592 * collected; we turn on garbage collection, and then we invoke our
1593 * magic top-level routine passing in clearspace borders that are
1594 * guaranteed large enough.
1595 */
runpattern()1596 node *hlifealgo::runpattern() {
1597 node *n = root ;
1598 save(root) ; // do this in case we interrupt generation
1599 ensure_hashed() ;
1600 okaytogc = 1 ;
1601 if (cacheinvalid) {
1602 do_gc(1) ; // invalidate the entire cache and recalc leaves
1603 cacheinvalid = 0 ;
1604 }
1605 int depth = node_depth(n) ;
1606 node *n2 ;
1607 n = pushroot(n) ;
1608 depth++ ;
1609 n = pushroot(n) ;
1610 depth++ ;
1611 while (ngens + 2 > depth) {
1612 n = pushroot(n) ;
1613 depth++ ;
1614 }
1615 save(zeronode(nzeros-1)) ;
1616 save(n) ;
1617 n2 = getres(n, depth) ;
1618 okaytogc = 0 ;
1619 clearstack() ;
1620 if (halvesdone == 1 && n->res != 0) {
1621 n->res = 0 ;
1622 halvesdone = 0 ;
1623 }
1624 if (poller->isInterrupted() || softinterrupt)
1625 return 0 ; // indicate it was interrupted
1626 n = popzeros(n2) ;
1627 generation += pow2step ;
1628 return n ;
1629 }
readmacrocell(char * line)1630 const char *hlifealgo::readmacrocell(char *line) {
1631 int n=0 ;
1632 g_uintptr_t i=1, nw=0, ne=0, sw=0, se=0, indlen=0 ;
1633 int r, d ;
1634 node **ind = 0 ;
1635 root = 0 ;
1636 while (getline(line, 10000)) {
1637 if (i >= indlen) {
1638 g_uintptr_t nlen = i + indlen + 10 ;
1639 ind = (node **)realloc(ind, sizeof(node*) * nlen) ;
1640 if (ind == 0)
1641 lifefatal("Out of memory (4).") ;
1642 while (indlen < nlen)
1643 ind[indlen++] = 0 ;
1644 }
1645 if (line[0] == '.' || line[0] == '*' || line[0] == '$') {
1646 int x=0, y=7 ;
1647 unsigned short lnw=0, lne=0, lsw=0, lse=0 ;
1648 char *p = 0 ;
1649 for (p=line; *p > ' '; p++) {
1650 switch(*p) {
1651 case '*': if (x > 7 || y < 0)
1652 return "Illegal coordinates in readmacrocell." ;
1653 if (x < 4)
1654 if (y < 4)
1655 lsw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
1656 else
1657 lnw |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
1658 else
1659 if (y < 4)
1660 lse |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
1661 else
1662 lne |= 1 << (3 - (x & 3) + 4 * (y & 3)) ;
1663 /* note: fall through here */
1664 case '.': x++ ;
1665 break ;
1666 case '$': x = 0 ;
1667 y-- ;
1668 break ;
1669 default: return "Illegal character in readmacrocell." ;
1670 }
1671 }
1672 clearstack() ;
1673 ind[i++] = (node *)find_leaf(lnw, lne, lsw, lse) ;
1674 } else if (line[0] == '#') {
1675 char *p, *pp ;
1676 const char *err ;
1677 switch (line[1]) {
1678 case 'R':
1679 p = line + 2 ;
1680 while (*p && *p <= ' ') p++ ;
1681 pp = p ;
1682 while (*pp > ' ') pp++ ;
1683 *pp = 0 ;
1684
1685 // AKT: need to check for B0-not-Smax rule
1686 err = hliferules.setrule(p, this);
1687 if (err)
1688 return err;
1689 if (hliferules.alternate_rules)
1690 return "B0-not-Smax rules are not allowed in HashLife.";
1691
1692 break ;
1693 case 'G':
1694 p = line + 2 ;
1695 while (*p && *p <= ' ') p++ ;
1696 pp = p ;
1697 while (*pp >= '0' && *pp <= '9') pp++ ;
1698 *pp = 0 ;
1699 generation = bigint(p) ;
1700 break ;
1701 // either:
1702 // #FRAMES count base inc
1703 // or
1704 // #FRAME index node
1705 case 'F':
1706 if (strncmp(line, "#FRAMES ", 8) == 0) {
1707 p = line + 8 ;
1708 while (*p && *p <= ' ')
1709 p++ ;
1710 long cnt = atol(p) ;
1711 if (cnt < 0 || cnt > MAX_FRAME_COUNT)
1712 return "Bad FRAMES line" ;
1713 destroytimeline() ;
1714 while ('0' <= *p && *p <= '9')
1715 p++ ;
1716 while (*p && *p <= ' ')
1717 p++ ;
1718 pp = p ;
1719 while ((*pp >= '0' && *pp <= '9') || *pp == ',') pp++ ;
1720 if (*pp == 0)
1721 return "Bad FRAMES line" ;
1722 *pp = 0 ;
1723 timeline.start = bigint(p) ;
1724 timeline.end = timeline.start ;
1725 timeline.next = timeline.start ;
1726 p = pp + 1 ;
1727 while (*p && *p <= ' ')
1728 p++ ;
1729 pp = p ;
1730 while (*pp > ' ')
1731 pp++ ;
1732 *pp = 0 ;
1733 if (strchr(p, '^')) {
1734 int tbase=0, texpo=0 ;
1735 if (sscanf(p, "%d^%d", &tbase, &texpo) != 2 ||
1736 tbase < 2 || texpo < 0)
1737 return "Bad FRAMES line" ;
1738 timeline.base = tbase ;
1739 timeline.expo = texpo ;
1740 timeline.inc = 1 ;
1741 while (texpo--)
1742 timeline.inc.mul_smallint(tbase) ;
1743 } else {
1744 timeline.inc = bigint(p) ;
1745 // if it's a power of two, we're good
1746 int texpo = timeline.inc.lowbitset() ;
1747 int tbase = 2 ;
1748 bigint test = 1 ;
1749 for (int i=0; i<texpo; i++)
1750 test += test ;
1751 if (test != timeline.inc)
1752 return "Bad increment (missing ^) in FRAMES" ;
1753 timeline.base = tbase ;
1754 timeline.expo = texpo ;
1755 }
1756 } else if (strncmp(line, "#FRAME ", 7) == 0) {
1757 int frameind = 0 ;
1758 g_uintptr_t nodeind = 0 ;
1759 n = sscanf(line+7, "%d %" PRIuPTR, &frameind, &nodeind) ;
1760 if (n != 2 || frameind > MAX_FRAME_COUNT || frameind < 0 ||
1761 nodeind > i || timeline.framecount != frameind)
1762 return "Bad FRAME line" ;
1763 timeline.frames.push_back(ind[nodeind]) ;
1764 timeline.framecount++ ;
1765 timeline.end = timeline.next ;
1766 timeline.next += timeline.inc ;
1767 }
1768 break ;
1769 }
1770 } else {
1771 n = sscanf(line, "%d %" PRIuPTR " %" PRIuPTR " %" PRIuPTR " %" PRIuPTR " %d", &d, &nw, &ne, &sw, &se, &r) ;
1772 if (n < 0) // blank line; permit
1773 continue ;
1774 if (n == 0) {
1775 // conversion error in first argument; we allow only if the only
1776 // content on the line is whitespace.
1777 char *ws = line ;
1778 while (*ws && *ws <= ' ')
1779 ws++ ;
1780 if (*ws > 0)
1781 return "Parse error in macrocell format." ;
1782 continue ;
1783 }
1784 if (n < 5)
1785 // AKT: best not to use lifefatal here because user won't see any
1786 // error message when reading clipboard data starting with "[..."
1787 return "Parse error in readmacrocell." ;
1788 if (d < 4)
1789 return "Oops; bad depth in readmacrocell." ;
1790 ind[0] = zeronode(d-2) ; /* allow zeros to work right */
1791 if (nw >= i || ind[nw] == 0 || ne >= i || ind[ne] == 0 ||
1792 sw >= i || ind[sw] == 0 || se >= i || ind[se] == 0) {
1793 return "Node out of range in readmacrocell." ;
1794 }
1795 clearstack() ;
1796 root = ind[i++] = find_node(ind[nw], ind[ne], ind[sw], ind[se]) ;
1797 depth = d - 1 ;
1798 }
1799 }
1800 if (ind)
1801 free(ind) ;
1802 if (root == 0) {
1803 // AKT: allow empty macrocell pattern; note that endofpattern()
1804 // will be called soon so don't set hashed here
1805 // return "Invalid macrocell file: no nodes." ;
1806 return 0 ;
1807 }
1808 hashed = 1 ;
1809 return 0 ;
1810 }
1811
1812 // Flip bits in given rule table.
fliprule(char * rptr)1813 static void fliprule(char *rptr) {
1814 for (int i=0; i<65536; i++) {
1815 int j = ((i & 0xf) << 12) +
1816 ((i & 0xf0) << 4) + ((i & 0xf00) >> 4) + ((i & 0xf000) >> 12) ;
1817 if (i <= j) {
1818 char fi = rptr[i] ;
1819 char fj = rptr[j] ;
1820 fi = ((fi & 0x30) >> 4) + ((fi & 0x3) << 4) ;
1821 fj = ((fj & 0x30) >> 4) + ((fj & 0x3) << 4) ;
1822 rptr[i] = fj ;
1823 rptr[j] = fi ;
1824 }
1825 }
1826 }
1827
setrule(const char * s)1828 const char *hlifealgo::setrule(const char *s) {
1829 poller->bailIfCalculating() ;
1830 const char* err = hliferules.setrule(s, this);
1831 if (err) return err;
1832
1833 // invert orientation if not hex or Wolfram
1834 if (!(hliferules.isHexagonal() || hliferules.isWolfram())) {
1835 fliprule(hliferules.rule0);
1836 }
1837
1838 clearcache() ;
1839
1840 if (hliferules.alternate_rules)
1841 return "B0-not-Smax rules are not allowed in HashLife.";
1842
1843 if (hliferules.isHexagonal())
1844 grid_type = HEX_GRID;
1845 else if (hliferules.isVonNeumann())
1846 grid_type = VN_GRID;
1847 else
1848 grid_type = SQUARE_GRID;
1849
1850 return 0 ;
1851 }
unpack8x8(unsigned short nw,unsigned short ne,unsigned short sw,unsigned short se,unsigned int * top,unsigned int * bot)1852 void hlifealgo::unpack8x8(unsigned short nw, unsigned short ne,
1853 unsigned short sw, unsigned short se,
1854 unsigned int *top, unsigned int *bot) {
1855 *top = ((nw & 0xf000) << 16) | (((ne & 0xf000) | (nw & 0xf00)) << 12) |
1856 (((ne & 0xf00) | (nw & 0xf0)) << 8) |
1857 (((ne & 0xf0) | (nw & 0xf)) << 4) | (ne & 0xf) ;
1858 *bot = ((sw & 0xf000) << 16) | (((se & 0xf000) | (sw & 0xf00)) << 12) |
1859 (((se & 0xf00) | (sw & 0xf0)) << 8) |
1860 (((se & 0xf0) | (sw & 0xf)) << 4) | (se & 0xf) ;
1861 }
1862 /**
1863 * Write out the native macrocell format. This is the one we use when
1864 * we're not interactive and displaying a progress dialog.
1865 */
writecell(std::ostream & os,node * root,int depth)1866 g_uintptr_t hlifealgo::writecell(std::ostream &os, node *root, int depth) {
1867 g_uintptr_t thiscell = 0 ;
1868 if (root == zeronode(depth))
1869 return 0 ;
1870 if (depth == 2) {
1871 if (root->nw != 0)
1872 return (g_uintptr_t)(root->nw) ;
1873 } else {
1874 if (marked2(root))
1875 return (g_uintptr_t)(root->next) ;
1876 unhash_node2(root) ;
1877 mark2(root) ;
1878 }
1879 if (depth == 2) {
1880 int i, j ;
1881 unsigned int top, bot ;
1882 leaf *n = (leaf *)root ;
1883 thiscell = ++cellcounter ;
1884 root->nw = (node *)thiscell ;
1885 unpack8x8(n->nw, n->ne, n->sw, n->se, &top, &bot) ;
1886 for (j=7; (top | bot) && j>=0; j--) {
1887 int bits = (top >> 24) ;
1888 top = (top << 8) | (bot >> 24) ;
1889 bot = (bot << 8) ;
1890 for (i=0; bits && i<8; i++, bits = (bits << 1) & 255)
1891 if (bits & 128)
1892 os << '*' ;
1893 else
1894 os << '.' ;
1895 os << '$' ;
1896 }
1897 os << '\n' ;
1898 } else {
1899 g_uintptr_t nw = writecell(os, root->nw, depth-1) ;
1900 g_uintptr_t ne = writecell(os, root->ne, depth-1) ;
1901 g_uintptr_t sw = writecell(os, root->sw, depth-1) ;
1902 g_uintptr_t se = writecell(os, root->se, depth-1) ;
1903 thiscell = ++cellcounter ;
1904 root->next = (node *)thiscell ;
1905 os << depth+1 << ' ' << nw << ' ' << ne << ' ' << sw << ' ' << se << '\n';
1906 }
1907 return thiscell ;
1908 }
1909 /**
1910 * This new two-pass method works by doing a prepass that numbers the
1911 * nodes and counts the number of nodes that should be sent, so we can
1912 * display an accurate progress dialog.
1913 */
writecell_2p1(node * root,int depth)1914 g_uintptr_t hlifealgo::writecell_2p1(node *root, int depth) {
1915 g_uintptr_t thiscell = 0 ;
1916 if (root == zeronode(depth))
1917 return 0 ;
1918 if (depth == 2) {
1919 if (root->nw != 0)
1920 return (g_uintptr_t)(root->nw) ;
1921 } else {
1922 if (marked2(root))
1923 return (g_uintptr_t)(root->next) ;
1924 unhash_node2(root) ;
1925 mark2(root) ;
1926 }
1927 if (depth == 2) {
1928 thiscell = ++cellcounter ;
1929 // note: we *must* not abort this prescan
1930 if ((cellcounter & 4095) == 0)
1931 lifeabortprogress(0, "Scanning tree") ;
1932 root->nw = (node *)thiscell ;
1933 } else {
1934 writecell_2p1(root->nw, depth-1) ;
1935 writecell_2p1(root->ne, depth-1) ;
1936 writecell_2p1(root->sw, depth-1) ;
1937 writecell_2p1(root->se, depth-1) ;
1938 thiscell = ++cellcounter ;
1939 // note: we *must* not abort this prescan
1940 if ((cellcounter & 4095) == 0)
1941 lifeabortprogress(0, "Scanning tree") ;
1942 root->next = (node *)thiscell ;
1943 }
1944 return thiscell ;
1945 }
1946 /**
1947 * This one writes the cells, but assuming they've already been
1948 * numbered, and displaying a progress dialog.
1949 */
1950 static char progressmsg[80] ;
writecell_2p2(std::ostream & os,node * root,int depth)1951 g_uintptr_t hlifealgo::writecell_2p2(std::ostream &os, node *root, int depth) {
1952 g_uintptr_t thiscell = 0 ;
1953 if (root == zeronode(depth))
1954 return 0 ;
1955 if (depth == 2) {
1956 if (cellcounter + 1 != (g_uintptr_t)(root->nw))
1957 return (g_uintptr_t)(root->nw) ;
1958 thiscell = ++cellcounter ;
1959 if ((cellcounter & 4095) == 0) {
1960 std::streampos siz = os.tellp();
1961 sprintf(progressmsg, "File size: %.2f MB", double(siz) / 1048576.0) ;
1962 lifeabortprogress(thiscell/(double)writecells, progressmsg) ;
1963 }
1964 int i, j ;
1965 unsigned int top, bot ;
1966 leaf *n = (leaf *)root ;
1967 root->nw = (node *)thiscell ;
1968 unpack8x8(n->nw, n->ne, n->sw, n->se, &top, &bot) ;
1969 for (j=7; (top | bot) && j>=0; j--) {
1970 int bits = (top >> 24) ;
1971 top = (top << 8) | (bot >> 24) ;
1972 bot = (bot << 8) ;
1973 for (i=0; bits && i<8; i++, bits = (bits << 1) & 255)
1974 if (bits & 128)
1975 os << '*' ;
1976 else
1977 os << '.' ;
1978 os << '$' ;
1979 }
1980 os << '\n' ;
1981 } else {
1982 if (cellcounter + 1 > (g_uintptr_t)(root->next) || isaborted())
1983 return (g_uintptr_t)(root->next) ;
1984 g_uintptr_t nw = writecell_2p2(os, root->nw, depth-1) ;
1985 g_uintptr_t ne = writecell_2p2(os, root->ne, depth-1) ;
1986 g_uintptr_t sw = writecell_2p2(os, root->sw, depth-1) ;
1987 g_uintptr_t se = writecell_2p2(os, root->se, depth-1) ;
1988 if (!isaborted() &&
1989 cellcounter + 1 != (g_uintptr_t)(root->next)) { // this should never happen
1990 lifefatal("Internal in writecell_2p2") ;
1991 return (g_uintptr_t)(root->next) ;
1992 }
1993 thiscell = ++cellcounter ;
1994 if ((cellcounter & 4095) == 0) {
1995 std::streampos siz = os.tellp();
1996 sprintf(progressmsg, "File size: %.2f MB", double(siz) / 1048576.0) ;
1997 lifeabortprogress(thiscell/(double)writecells, progressmsg) ;
1998 }
1999 root->next = (node *)thiscell ;
2000 os << depth+1 << ' ' << nw << ' ' << ne << ' ' << sw << ' ' << se << '\n';
2001 }
2002 return thiscell ;
2003 }
2004 #define STRINGIFY(arg) STR2(arg)
2005 #define STR2(arg) #arg
writeNativeFormat(std::ostream & os,char * comments)2006 const char *hlifealgo::writeNativeFormat(std::ostream &os, char *comments) {
2007 int depth = node_depth(root) ;
2008 os << "[M2] (golly " STRINGIFY(VERSION) ")\n" ;
2009
2010 // AKT: always write out explicit rule
2011 os << "#R " << hliferules.getrule() << '\n' ;
2012
2013 if (generation > bigint::zero) {
2014 // write non-zero gen count
2015 os << "#G " << generation.tostring('\0') << '\n' ;
2016 }
2017
2018 if (comments) {
2019 // write given comment line(s), but we can't just do "os << comments" because the
2020 // lines might not start with #C (eg. if they came from the end of a .rle file),
2021 // so we must ensure that each comment line in the .mc file starts with #C
2022 char *p = comments;
2023 while (*p != '\0') {
2024 char *line = p;
2025 // note that readcomments() in readpattern.cpp ensures each line ends with \n
2026 while (*p != '\n') p++;
2027 if (line[0] != '#' || line[1] != 'C') {
2028 os << "#C ";
2029 }
2030 if (line != p) {
2031 *p = '\0';
2032 os << line;
2033 *p = '\n';
2034 }
2035 os << '\n';
2036 p++;
2037 }
2038 }
2039
2040 inGC = 1 ;
2041 /* this is the old way:
2042 cellcounter = 0 ;
2043 writecell(f, root, depth) ;
2044 */
2045 /* this is the new two-pass way */
2046 cellcounter = 0 ;
2047 vector<int> depths(timeline.framecount) ;
2048 int framestosave = timeline.framecount ;
2049 if (timeline.savetimeline == 0)
2050 framestosave = 0 ;
2051 if (framestosave) {
2052 for (int i=0; i<timeline.framecount; i++) {
2053 node *frame = (node*)timeline.frames[i] ;
2054 depths[i] = node_depth(frame) ;
2055 }
2056 for (int i=0; i<timeline.framecount; i++) {
2057 node *frame = (node*)timeline.frames[i] ;
2058 writecell_2p1(frame, depths[i]) ;
2059 }
2060 }
2061 writecell_2p1(root, depth) ;
2062 writecells = cellcounter ;
2063 cellcounter = 0 ;
2064 if (framestosave) {
2065 os << "#FRAMES"
2066 << ' ' << timeline.framecount
2067 << ' ' << timeline.start.tostring()
2068 << ' ' << timeline.base << '^' << timeline.expo << '\n' ;
2069 for (int i=0; i<timeline.framecount; i++) {
2070 node *frame = (node*)timeline.frames[i] ;
2071 writecell_2p2(os, frame, depths[i]) ;
2072 os << "#FRAME " << i << ' ' << (g_uintptr_t)frame->next << '\n' ;
2073 }
2074 }
2075 writecell_2p2(os, root, depth) ;
2076 /* end new two-pass way */
2077 if (framestosave) {
2078 for (int i=0; i<timeline.framecount; i++) {
2079 node *frame = (node*)timeline.frames[i] ;
2080 afterwritemc(frame, depths[i]) ;
2081 }
2082 }
2083 afterwritemc(root, depth) ;
2084 inGC = 0 ;
2085 return 0 ;
2086 }
2087 char hlifealgo::statusline[200] ;
creator()2088 static lifealgo *creator() { return new hlifealgo() ; }
doInitializeAlgoInfo(staticAlgoInfo & ai)2089 void hlifealgo::doInitializeAlgoInfo(staticAlgoInfo &ai) {
2090 ai.setAlgorithmName("HashLife") ;
2091 ai.setAlgorithmCreator(&creator) ;
2092 ai.setDefaultBaseStep(8) ;
2093 ai.setDefaultMaxMem(500) ; // MB
2094 ai.minstates = 2 ;
2095 ai.maxstates = 2 ;
2096 // init default color scheme
2097 ai.defgradient = false;
2098 ai.defr1 = ai.defg1 = ai.defb1 = 255; // start color = white
2099 ai.defr2 = ai.defg2 = ai.defb2 = 255; // end color = white
2100 ai.defr[0] = ai.defg[0] = ai.defb[0] = 48; // 0 state = dark gray
2101 ai.defr[1] = ai.defg[1] = ai.defb[1] = 255; // 1 state = white
2102 }
2103