1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 #include "qlifealgo.h"
5 #include <cstring>
6 #include <cstdlib>
7 #include "util.h"
8
9 const int logbmsize = 8 ; // *must* be 8 in this code
10 const int bmsize = (1<<logbmsize) ;
11 const int ibufsize = (bmsize*bmsize/32) ;
12 static unsigned int ibigbuf[ibufsize] ; // shared buffer for 256x256 pixels
13 static unsigned char *bigbuf = (unsigned char *)ibigbuf ;
14
15 // AKT: 256x256 pixmap where each pixel is 4 RGBA bytes
16 static unsigned char pixbuf[bmsize*bmsize*4];
17
18 // AKT: RGBA values for cell states (see getcolors call)
19 static unsigned char deadr, deadg, deadb, deada;
20 static unsigned char liver, liveg, liveb, livea;
21
22 // rowett: RGBA view of cell states
23 static unsigned int liveRGBA, deadRGBA;
24
renderbm(int x,int y)25 void qlifealgo::renderbm(int x, int y) {
26 renderbm(x, y, bmsize, bmsize) ;
27 }
28
renderbm(int x,int y,int xsize,int ysize)29 void qlifealgo::renderbm(int x, int y, int xsize, int ysize) {
30 // x,y is lower left corner
31 int rx = x ;
32 int ry = y ;
33 int rw = xsize ;
34 int rh = ysize ;
35 if (pmag > 1) {
36 rx *= pmag ;
37 ry *= pmag ;
38 rw *= pmag ;
39 rh *= pmag ;
40 }
41 ry = uviewh - ry - rh ;
42
43 unsigned char *bigptr = bigbuf;
44 if (renderer->justState() || pmag > 1) {
45 // convert each bigbuf byte into 8 bytes of state data
46 unsigned char *pixptr = pixbuf;
47
48 for (int i = 0; i < ibufsize * 4; i++) {
49 unsigned char byte = *bigptr++;
50 *pixptr++ = (byte & 128) ? 1 : 0;
51 *pixptr++ = (byte & 64) ? 1 : 0;
52 *pixptr++ = (byte & 32) ? 1 : 0;
53 *pixptr++ = (byte & 16) ? 1 : 0;
54 *pixptr++ = (byte & 8) ? 1 : 0;
55 *pixptr++ = (byte & 4) ? 1 : 0;
56 *pixptr++ = (byte & 2) ? 1 : 0;
57 *pixptr++ = (byte & 1); // no condition needed
58 }
59 } else {
60 // convert each bigbuf byte into 32 bytes of pixel data (8 * RGBA)
61 // get RGBA view of pixel buffer
62 unsigned int *pixptr = (unsigned int *)pixbuf;
63
64 for (int i = 0; i < ibufsize * 4; i++) {
65 unsigned char byte = *bigptr++;
66 *pixptr++ = (byte & 128) ? liveRGBA : deadRGBA;
67 *pixptr++ = (byte & 64) ? liveRGBA : deadRGBA;
68 *pixptr++ = (byte & 32) ? liveRGBA : deadRGBA;
69 *pixptr++ = (byte & 16) ? liveRGBA : deadRGBA;
70 *pixptr++ = (byte & 8) ? liveRGBA : deadRGBA;
71 *pixptr++ = (byte & 4) ? liveRGBA : deadRGBA;
72 *pixptr++ = (byte & 2) ? liveRGBA : deadRGBA;
73 *pixptr++ = (byte & 1) ? liveRGBA : deadRGBA;
74 }
75 }
76 if (renderer->justState())
77 renderer->stateblit(rx, ry, rw, rh, pixbuf) ;
78 else
79 renderer->pixblit(rx, ry, rw, rh, pixbuf, pmag);
80
81 memset(bigbuf, 0, sizeof(ibigbuf)) ;
82 }
83
84 static int minlevel;
85 /*
86 * We cheat for now; we assume we can use 32-bit ints. We can below
87 * a certain level; we'll deal with higher levels later.
88 */
BlitCells(supertile * p,int xoff,int yoff,int wd,int ht,int lev)89 void qlifealgo::BlitCells(supertile *p,
90 int xoff, int yoff, int wd, int ht, int lev) {
91 int i, xinc=0, yinc=0, ypos, x, yy;
92 int liveseen = 0 ;
93
94 if (xoff >= vieww || xoff + wd < 0 || yoff >= viewh || yoff + ht < 0)
95 // no part of this supertile is visible
96 return;
97
98 if (p == nullroots[lev]) {
99 return;
100 }
101
102 // do recursion until we get to level 2 (256x256 supertile)
103 if (lev > 2) {
104 if (lev & 1) {
105 // odd level -- 8 subtiles are stacked horizontally
106 xinc = wd = ht;
107 } else {
108 // even level -- 8 subtiles are stacked vertically
109 yinc = ht = (ht >> 3);
110 }
111 for (i=0; i<8; i++) {
112 BlitCells(p->d[i], xoff, yoff, wd, ht, lev-1);
113 xoff += xinc;
114 yoff += yinc;
115 }
116 return;
117 }
118
119 // walk a (probably) non-empty 256x256 supertile, finding all the 1 bits and
120 // setting corresponding bits in the bitmap (bigbuf)
121 liveseen = 0 ;
122 ypos = yoff;
123 // examine the 8 vertically stacked subtiles in this 256x256 supertile (at level 2)
124 for (yy=0; yy<8; yy++) {
125 if (p->d[yy] != nullroots[1] && ypos < viewh && ypos + 32 >= 0) {
126 supertile *psub = p->d[yy];
127 x = xoff;
128 // examine the 8 tiles in this 256x32 supertile (at level 1)
129 for (i=0; i<8; i++) {
130 if (psub->d[i] != nullroots[0] && x < vieww && x + 32 >= 0) {
131 tile *t = (tile *)psub->d[i];
132 int j, k, y = ypos;
133 // examine the 4 bricks in this 32x32 tile (at level 0)
134 for (j=0; j<4; j++) {
135 if (t->b[j] != emptybrick && y < viewh && y + 8 >= 0) {
136 brick *b = t->b[j];
137 // examine the 8 slices (2 at a time) in the appropriate half-brick
138 for (k=0; k<8; k+=2) {
139 unsigned int v1 = b->d[k+kadd];
140 unsigned int v2 = b->d[k+kadd+1];
141 if (v1|v2) {
142 // do an 8x8 set of bits (2 adjacent slices)
143 int xd = (i<<2)+(k>>1);
144 int yd = (7 - yy) << 10; // 1024 bytes in 256x32 supertile
145 unsigned char *p = bigbuf + yd + xd + ((3 - j) << 8);
146
147 unsigned int v3 = (((v1 & 0x0f0f0f0f) << 4) |
148 (v2 & 0x0f0f0f0f));
149 v2 = ((v1 & 0xf0f0f0f0) | ((v2 >> 4) & 0x0f0f0f0f));
150 *p = (unsigned char)v3;
151 p[32] = (unsigned char)v2;
152 p[64] = (unsigned char)(v3 >> 8);
153 p[96] = (unsigned char)(v2 >> 8);
154 p[128] = (unsigned char)(v3 >> 16);
155 p[160] = (unsigned char)(v2 >> 16);
156 p[192] = (unsigned char)(v3 >> 24);
157 p[224] = (unsigned char)(v2 >> 24);
158
159 liveseen |= (1 << yy) ;
160 }
161 }
162 }
163 y += 8; // down to next brick
164 }
165 }
166 x += 32; // across to next tile
167 }
168 }
169 ypos += 32; // down to next subtile
170 }
171
172 if (liveseen == 0) {
173 return; // no live cells seen
174 }
175
176 // performance: if we want, liveseen now contains eight bits
177 // corresponding to whether those respective 256x32 rectangles
178 // contain set pixels or not. We should trim the bitmap
179 // to only render those portions that need to be rendered
180 // (using this information). -tom
181 //
182 // draw the non-empty bitmap, scaling up if pmag > 1
183 renderbm(xoff, yoff) ;
184 }
185
186 // This pattern drawing routine is used when mag > 0.
187 // We go down to a level where what we're going to draw maps to one
188 // of 256x256, 128x128, or 64x64.
189 //
190 // We no longer rely on popcount having been called; instead we invoke
191 // the popcount child if needed.
192
ShrinkCells(supertile * p,int xoff,int yoff,int wd,int ht,int lev)193 void qlifealgo::ShrinkCells(supertile *p,
194 int xoff, int yoff, int wd, int ht, int lev) {
195 int i ;
196 if (lev >= bmlev) {
197 if (xoff >= vieww || xoff + wd < 0 || yoff >= viewh || yoff + ht < 0)
198 // no part of this supertile/tile is visible
199 return ;
200 if (p == nullroots[lev]) {
201 return ;
202 }
203 if (lev == bmlev) {
204 bmleft = xoff ;
205 bmtop = yoff ;
206 }
207 } else {
208 if (p == nullroots[lev])
209 return ;
210 }
211 int bminc = -1 << (logshbmsize-3) ;
212 unsigned char *bm = bigbuf + (((shbmsize-1)-yoff+bmtop) << (logshbmsize-3)) +
213 ((xoff-bmleft) >> 3) ;
214 int bit = 128 >> ((xoff-bmleft) & 7) ;
215 // do recursion until we get to minimum level (which depends on mag)
216 if (lev > minlevel) {
217 int xinc = 0, yinc = 0 ;
218 if (lev & 1) {
219 // odd level -- 8 subtiles are stacked horizontally
220 xinc = wd ;
221 wd = ht ;
222 } else {
223 // even level -- 8 subtiles are stacked vertically
224 yinc = ht ;
225 ht = (ht >> 3);
226 }
227 int xxinc = 0 ;
228 int yyinc = 0 ;
229 if (yinc <= 8 && xinc == 0) {
230 // This is a case where we need to traverse multiple nodes for a
231 // single pixel. This can be really slow, especially if we have
232 // to examine 4x4=16 nodes just for a single pixel! To help
233 // mitigate that, we special-case this and do the entire square,
234 // tracking which pixels are set and not traversing when we
235 // would set a pixel again.
236 xinc = yinc ;
237 int sh = 0 ;
238 if (xinc == 8)
239 sh = 0 ;
240 else if (xinc == 4)
241 sh = 1 ;
242 else if (xinc == 2)
243 sh = 2 ;
244 for (i=0; i<8; i++) {
245 if (p->d[i] != nullroots[lev-1]) {
246 supertile *pp = p->d[i] ;
247 int bbit = bit ;
248 for (int j=0; j<8; j++) {
249 if (pp->d[j] != nullroots[lev-2]) {
250 if (0 == (*bm & bbit)) {
251 supertile *ppp = pp->d[j] ;
252 if (lev > 2) {
253 if ( ppp->pop[oddgen] != 0 )
254 *bm |= bbit ;
255 } else {
256 tile *t = (tile *)ppp ;
257 if (t->flags & quickb)
258 *bm |= bbit ;
259 }
260 }
261 }
262 if ((j ^ (j + 1)) >> sh)
263 bbit >>= 1 ;
264 }
265 }
266 if ((i ^ (i + 1)) >> sh)
267 bm += bminc ;
268 }
269 return ;
270 } else {
271 for (i=0; i<8; i++) {
272 ShrinkCells(p->d[i], xoff + (xxinc >> 3), yoff + (yyinc >> 3),
273 wd, ht, lev-1);
274 xxinc += xinc ;
275 yyinc += yinc ;
276 }
277 if (lev == bmlev)
278 renderbm(bmleft, bmtop, shbmsize, shbmsize) ;
279 }
280 } else if (mag > 4) {
281 if (lev > 0) {
282 // mag >= 8
283 if ( p->pop[oddgen] != 0 )
284 *bm |= bit ;
285 } else {
286 // mag = 5..7
287 tile *t = (tile *)p;
288 if (t->flags & quickb)
289 *bm |= bit ;
290 }
291 } else {
292 switch (mag) {
293 case 4: {
294 // shrink 32x32 tile to 2x2 pixels
295 tile *t = (tile *)p;
296 if ((t->b[0] != emptybrick || t->b[1] != emptybrick) ) {
297 brick *bt = t->b[0];
298 brick *bb = t->b[1];
299 // examine the top left 16x16 cells
300 if ( bt->d[kadd+0] | bt->d[kadd+1] | bt->d[kadd+2] | bt->d[kadd+3] |
301 bb->d[kadd+0] | bb->d[kadd+1] | bb->d[kadd+2] | bb->d[kadd+3] )
302 // shrink 16x16 cells to 1 pixel
303 *bm |= bit ;
304 // examine the top right 16x16 cells
305 if ( bt->d[kadd+4] | bt->d[kadd+5] | bt->d[kadd+6] | bt->d[kadd+7] |
306 bb->d[kadd+4] | bb->d[kadd+5] | bb->d[kadd+6] | bb->d[kadd+7] )
307 // shrink 16x16 cells to 1 pixel
308 *bm |= bit >> 1 ;
309 }
310 bm += bminc ;
311 if (t->b[2] != emptybrick || t->b[3] != emptybrick) {
312 brick *bt = t->b[2];
313 brick *bb = t->b[3];
314 // examine the bottom left 16x16 cells
315 if ( bt->d[kadd+0] | bt->d[kadd+1] | bt->d[kadd+2] | bt->d[kadd+3] |
316 bb->d[kadd+0] | bb->d[kadd+1] | bb->d[kadd+2] | bb->d[kadd+3] )
317 // shrink 16x16 cells to 1 pixel
318 *bm |= bit ;
319 // examine the bottom right 16x16 cells
320 if ( bt->d[kadd+4] | bt->d[kadd+5] | bt->d[kadd+6] | bt->d[kadd+7] |
321 bb->d[kadd+4] | bb->d[kadd+5] | bb->d[kadd+6] | bb->d[kadd+7] )
322 // shrink 16x16 cells to 1 pixel
323 *bm |= bit >> 1 ;
324 }
325 }
326 break;
327
328 case 3: {
329 // mag = 3 so shrink 32x32 tile to 4x4 pixels
330 tile *t = (tile *)p;
331 int j ;
332 // examine the 4 bricks in this 32x32 tile
333 for (j=0; j<4; j++) {
334 if (t->b[j] != emptybrick) {
335 brick *b = t->b[j];
336 int k ;
337 // examine the 8 slices (2 at a time) in the appropriate half-brick
338 int bbit = bit;
339 for (k=0; k<8; k += 2) {
340 if ( (b->d[k+kadd] | b->d[k+kadd+1]) ) *bm |= bbit ;
341 bbit >>= 1 ;
342 }
343 }
344 bm += bminc ;
345 }
346 }
347 break;
348
349 case 2: {
350 // mag = 2 so shrink 32x32 tile to 8x8 pixels
351 tile *t = (tile *)p;
352 int j ;
353 // examine the 4 bricks in this 32x32 tile
354 for (j=0; j<4; j++) {
355 if (t->b[j] != emptybrick) {
356 brick *b = t->b[j];
357 int k ;
358 bit = 128 ;
359 // examine the 8 slices in the appropriate half-brick
360 for (k=0; k<8; k++) {
361 unsigned int s = b->d[k+kadd];
362 // s represents a 4x8 slice so examine top and bottom halves
363 if (s) {
364 if (s & 0xFFFF0000) *bm |= bit ;
365 if (s & 0x0000FFFF) bm[bminc] |= bit ;
366 }
367 bit >>= 1 ;
368 }
369 }
370 bm += 2 * bminc ;
371 }
372 }
373 break;
374
375 case 1: {
376 // mag = 1 so shrink 32x32 tile to 16x16 pixels
377 tile *t = (tile *)p;
378 int j ;
379 // examine the 4 bricks in this 32x32 tile
380 unsigned char *bmm = bm ;
381 for (j=0; j<4; j++) {
382 if (t->b[j] != emptybrick) {
383 brick *b = t->b[j];
384 int k ;
385 bit = 128 ;
386 // examine the 8 slices in the appropriate half-brick
387 for (k=0; k<8; k++) {
388 unsigned int s = b->d[k+kadd];
389 if (s) {
390 // s is a non-empty 4x8 slice so shrink each 2x2 section to 1 pixel
391 if (s & 0xCC000000) *bmm |= bit ;
392 if (s & 0x00CC0000) bmm[bminc] |= bit ;
393 if (s & 0x0000CC00) bmm[bminc+bminc] |= bit ;
394 if (s & 0x000000CC) bmm[bminc+bminc+bminc] |= bit ;
395 bit >>= 1 ;
396 if (s & 0x33000000) *bmm |= bit ;
397 if (s & 0x00330000) bmm[bminc] |= bit ;
398 if (s & 0x00003300) bmm[bminc+bminc] |= bit ;
399 if (s & 0x00000033) bmm[bminc+bminc+bminc] |= bit ;
400 bit >>= 1 ;
401 } else {
402 bit >>= 2 ;
403 }
404 if (bit < 1) {
405 bmm++ ;
406 bit = 128 ;
407 }
408 }
409 bmm -= 2 ;
410 }
411 bmm += 4 * bminc ;
412 }
413 }
414 break;
415 }
416 }
417 }
418 /*
419 * Fill in the llxb and llyb bits from the viewport information.
420 * Allocate if necessary. This arithmetic should be done carefully.
421 */
fill_ll(int d)422 void qlifealgo::fill_ll(int d) {
423 pair<bigint, bigint> coor = view->at(0, view->getymax()) ;
424 coor.second.mul_smallint(-1) ;
425 coor.first -= bmin ;
426 coor.second -= bmin ;
427 if (oddgen) {
428 coor.first -= 1 ;
429 coor.second -= 1 ;
430 }
431 int bitsreq = coor.first.bitsreq() ;
432 int bitsreq2 = coor.second.bitsreq() ;
433 if (bitsreq2 > bitsreq)
434 bitsreq = bitsreq2 ;
435 if (bitsreq <= d)
436 bitsreq = d + 1 ; // need to access llxyb[d]
437 if (bitsreq > llsize) {
438 if (llsize) {
439 delete [] llxb ;
440 delete [] llyb ;
441 }
442 llxb = new char[bitsreq] ;
443 llyb = new char[bitsreq] ;
444 llsize = bitsreq ;
445 }
446 llbits = bitsreq ;
447 coor.first.tochararr(llxb, llbits) ;
448 coor.second.tochararr(llyb, llbits) ;
449 }
draw(viewport & viewarg,liferender & renderarg)450 void qlifealgo::draw(viewport &viewarg, liferender &renderarg) {
451 memset(bigbuf, 0, sizeof(ibigbuf)) ;
452 renderer = &renderarg ;
453
454 if (!renderer->justState()) {
455 // AKT: get cell colors and alpha values for dead and live pixels
456 unsigned char *r, *g, *b;
457 renderer->getcolors(&r, &g, &b, &deada, &livea);
458 deadr = r[0];
459 deadg = g[0];
460 deadb = b[0];
461 liver = r[1];
462 liveg = g[1];
463 liveb = b[1];
464
465 // create RGBA live color
466 unsigned char *colptr = (unsigned char *)&liveRGBA;
467 *colptr++ = liver;
468 *colptr++ = liveg;
469 *colptr++ = liveb;
470 *colptr++ = livea;
471
472 // create RGBA dead color
473 colptr = (unsigned char *)&deadRGBA;
474 *colptr++ = deadr;
475 *colptr++ = deadg;
476 *colptr++ = deadb;
477 *colptr++ = deada;
478 }
479
480 view = &viewarg ;
481 uvieww = view->getwidth() ;
482 uviewh = view->getheight() ;
483 oddgen = getGeneration().odd() ;
484 kadd = oddgen ? 8 : 0 ;
485 int xoff, yoff ;
486 if (view->getmag() > 0) {
487 pmag = 1 << (view->getmag()) ;
488 mag = 0 ;
489 viewh = ((uviewh - 1) >> view->getmag()) + 1 ;
490 vieww = ((uvieww - 1) >> view->getmag()) + 1 ;
491 uviewh += (-uviewh) & (pmag-1) ;
492 } else {
493 mag = (-view->getmag()) ;
494 // cheat for now since unzoom is broken
495 pmag = 1 ;
496 viewh = uviewh ;
497 vieww = uvieww ;
498 }
499 if (root == nullroots[rootlev]) {
500 renderer = 0 ;
501 view = 0 ;
502 return ;
503 }
504 int d = 5 + (rootlev + 1) / 2 * 3 ;
505 fill_ll(d) ;
506 int maxd = vieww ;
507 supertile *sw = root, *nw = nullroots[rootlev], *ne = nullroots[rootlev],
508 *se = nullroots[rootlev] ;
509 if (viewh > maxd)
510 maxd = viewh ;
511 int llx=-llxb[llbits-1], lly=-llyb[llbits-1] ;
512 /* Skip down to top of tree. */
513 int i;
514 for (i=llbits-1; i>=d && i>=mag; i--) { /* go down to d, but not further than mag */
515 llx = (llx << 1) + llxb[i] ;
516 lly = (lly << 1) + llyb[i] ;
517 if (llx > 2*maxd || lly > 2*maxd || llx < -2*maxd || lly < -2*maxd) {
518 renderer = 0 ;
519 view = 0 ;
520 return ;
521 }
522 }
523 /* Find the lowest four we need to examine */
524 int curlev = rootlev ;
525 while (d > 8 && d - mag > 2 &&
526 (d - mag > 28 || (1 << (d - mag)) > 32 * maxd)) {
527 // d is 5 + 3 * i for some positive i
528 llx = (llx << 3) + (llxb[d-1] << 2) + (llxb[d-2] << 1) + llxb[d-3] ;
529 lly = (lly << 3) + (llyb[d-1] << 2) + (llyb[d-2] << 1) + llyb[d-3] ;
530 int xp = llx ;
531 if (xp < 0)
532 xp = 0 ;
533 else if (xp > 7)
534 xp = 7 ;
535 int yp = lly ;
536 if (yp < 0)
537 yp = 0 ;
538 else if (yp > 7)
539 yp = 7 ;
540 if (xp == 7) {
541 if (yp == 7) {
542 ne = ne->d[0]->d[0] ;
543 se = se->d[7]->d[0] ;
544 nw = nw->d[0]->d[7] ;
545 sw = sw->d[7]->d[7] ;
546 } else {
547 ne = se->d[yp+1]->d[0] ;
548 se = se->d[yp]->d[0] ;
549 nw = sw->d[yp+1]->d[7] ;
550 sw = sw->d[yp]->d[7] ;
551 }
552 } else {
553 if (yp == 7) {
554 ne = nw->d[0]->d[xp+1] ;
555 se = sw->d[7]->d[xp+1] ;
556 nw = nw->d[0]->d[xp] ;
557 sw = sw->d[7]->d[xp] ;
558 } else {
559 ne = sw->d[yp+1]->d[xp+1] ;
560 se = sw->d[yp]->d[xp+1] ;
561 nw = sw->d[yp+1]->d[xp] ;
562 sw = sw->d[yp]->d[xp] ;
563 }
564 }
565 llx -= xp ;
566 lly -= yp ;
567 if (llx > 2*maxd || lly > 2*maxd || llx < -2*maxd || lly < -2*maxd) {
568 renderer = 0 ;
569 view = 0 ;
570 return ;
571 }
572 d -= 3 ;
573 curlev -= 2 ;
574 }
575 find_set_bits(nw, curlev, oddgen) ;
576 find_set_bits(ne, curlev, oddgen) ;
577 find_set_bits(sw, curlev, oddgen) ;
578 find_set_bits(se, curlev, oddgen) ;
579 // getPopulation() ;
580 /* At this point we know we can use 32-bit arithmetic. */
581 for (i=d-1; i>=mag; i--) {
582 llx = (llx << 1) + llxb[i] ;
583 lly = (lly << 1) + llyb[i] ;
584 }
585 /* now, we have four nodes to draw. the ll point in
586 screen coordinates is given by llx/lly. the ur point
587 in screen coordinates is given by that plus 2 << (d-mag).
588 */
589 xoff = -llx ;
590 yoff = -lly ;
591 int wd = 2 ;
592 if (d >= mag)
593 wd = 2 << (d-mag) ;
594 int yoffuht = yoff + wd ;
595 int xoffuwd = xoff + wd ;
596 if (yoff >= viewh || xoff >= vieww || yoffuht < 0 || xoffuwd < 0) {
597 renderer = 0 ;
598 view = 0 ;
599 return ;
600 }
601 int levsize = wd / 2 ;
602 // do recursive drawing
603 quickb = 0xfff << (8 + oddgen * 12) ;
604 if (mag > 0) {
605 bmlev = (1 + mag / 3) * 2 ;
606 logshbmsize = 8 - (mag % 3) ;
607 shbmsize = 1 << logshbmsize ;
608 if (mag < 5) {
609 // recurse down to 32x32 tiles
610 minlevel = 0;
611 } else {
612 // if mag = 5..7 minlevel = 0 (32x32 tiles)
613 // if mag = 8..10 minlevel = 2 (256x256 supertiles)
614 // if mag = 11..13 minlevel = 4 (2048x2048 supertiles) etc...
615 minlevel = ((mag - 5) / 3) * 2;
616 }
617 bmleft = xoff ;
618 bmtop = yoff ;
619 ShrinkCells(sw, xoff, yoff, levsize, levsize, curlev);
620 ShrinkCells(se, xoff+levsize, yoff, levsize, levsize, curlev);
621 ShrinkCells(nw, xoff, yoff+levsize, levsize, levsize, curlev);
622 ShrinkCells(ne, xoff+levsize, yoff+levsize, levsize, levsize, curlev);
623 if (bmlev > curlev)
624 renderbm(bmleft, bmtop, shbmsize, shbmsize) ;
625 } else {
626 // recurse down to 256x256 supertiles and use bitmap blitting
627 BlitCells(sw, xoff, yoff, levsize, levsize, curlev);
628 BlitCells(se, xoff+levsize, yoff, levsize, levsize, curlev);
629 BlitCells(nw, xoff, yoff+levsize, levsize, levsize, curlev);
630 BlitCells(ne, xoff+levsize, yoff+levsize, levsize, levsize, curlev);
631 }
632 renderer = 0 ;
633 view = 0 ;
634 }
635 /**
636 * Find the subsupertiles with the smallest indices.
637 */
lowsub(vector<supertile * > & src,vector<supertile * > & dst,int lev)638 int qlifealgo::lowsub(vector<supertile*> &src, vector<supertile*> &dst,
639 int lev) {
640 int lowlev = 7 ;
641 dst.clear() ;
642 supertile *z = nullroots[lev-1] ;
643 if (lev > 1) {
644 for (int i=0; i<(int)src.size(); i++) {
645 supertile *p = src[i] ;
646 for (int j=0; j<lowlev; j++)
647 if (p->d[j] != z && (p->d[j]->pop[oddgen])) {
648 lowlev = j ;
649 dst.clear() ;
650 }
651 if (p->d[lowlev] != z && (p->d[lowlev]->pop[oddgen]))
652 dst.push_back(p->d[lowlev]) ;
653 }
654 } else {
655 for (int i=0; i<(int)src.size(); i++) {
656 supertile *p = src[i] ;
657 for (int j=0; j<lowlev; j++)
658 if (p->d[j] != z && (((tile *)(p->d[j]))->flags & quickb)) {
659 lowlev = j ;
660 dst.clear() ;
661 }
662 if (p->d[lowlev] != z && (((tile *)(p->d[lowlev]))->flags & quickb))
663 dst.push_back(p->d[lowlev]) ;
664 }
665 }
666 return lowlev ;
667 }
668 /**
669 * Find the subsupertiles with the highest indices.
670 */
highsub(vector<supertile * > & src,vector<supertile * > & dst,int lev)671 int qlifealgo::highsub(vector<supertile*> &src, vector<supertile*> &dst,
672 int lev) {
673 int highlev = 0 ;
674 dst.clear() ;
675 supertile *z = nullroots[lev-1] ;
676 if (lev > 1) {
677 for (int i=0; i<(int)src.size(); i++) {
678 supertile *p = src[i] ;
679 for (int j=7; j>highlev; j--)
680 if (p->d[j] != z && (p->d[j]->pop[oddgen])) {
681 highlev = j ;
682 dst.clear() ;
683 }
684 if (p->d[highlev] != z && (p->d[highlev]->pop[oddgen]))
685 dst.push_back(p->d[highlev]) ;
686 }
687 } else {
688 for (int i=0; i<(int)src.size(); i++) {
689 supertile *p = src[i] ;
690 for (int j=7; j>highlev; j--)
691 if (p->d[j] != z && (((tile *)(p->d[j]))->flags & quickb)) {
692 highlev = j ;
693 dst.clear() ;
694 }
695 if (p->d[highlev] != z && (((tile *)(p->d[highlev]))->flags & quickb))
696 dst.push_back(p->d[highlev]) ;
697 }
698 }
699 return highlev ;
700 }
701 /**
702 * Find all nonzero sub-supertiles.
703 */
allsub(vector<supertile * > & src,vector<supertile * > & dst,int lev)704 void qlifealgo::allsub(vector<supertile*> &src, vector<supertile*> &dst,
705 int lev) {
706 dst.clear() ;
707 supertile *z = nullroots[lev-1] ;
708 if (lev > 1) {
709 for (int i=0; i<(int)src.size(); i++) {
710 supertile *p = src[i] ;
711 for (int j=0; j<8; j++)
712 if (p->d[j] != z && (p->d[j]->pop[oddgen]))
713 dst.push_back(p->d[j]) ;
714 }
715 } else {
716 for (int i=0; i<(int)src.size(); i++) {
717 supertile *p = src[i] ;
718 for (int j=0; j<8; j++)
719 if (p->d[j] != z && (((tile *)(p->d[j]))->flags & quickb))
720 dst.push_back(p->d[j]) ;
721 }
722 }
723 }
gethbitsfromleaves(vector<supertile * > v)724 int qlifealgo::gethbitsfromleaves(vector<supertile *> v) {
725 int h[8] ;
726 int i;
727 for (i=0; i<8; i++)
728 h[i] = 0 ;
729 for (i=0; i<(int)v.size(); i++) {
730 tile *p = (tile *)v[i] ;
731 for (int j=0; j<4; j++)
732 if (p->b[j] != emptybrick)
733 for (int k=0; k<8; k++)
734 h[k] |= p->b[j]->d[k+kadd] ;
735 }
736 int r = 0 ;
737 for (i=0; i<8; i++) {
738 int v = h[i] ;
739 v |= (v >> 16) ;
740 v |= (v >> 8) ;
741 v |= (v >> 4) ;
742 r = (r << 4) | (v & 15) ;
743 }
744 return r ;
745 }
getvbitsfromleaves(vector<supertile * > vec)746 int qlifealgo::getvbitsfromleaves(vector<supertile *> vec) {
747 int v[4] ;
748 int i;
749 for (i=0; i<4; i++)
750 v[i] = 0 ;
751 for (i=0; i<(int)vec.size(); i++) {
752 tile *p = (tile *)vec[i] ;
753 for (int j=0; j<4; j++)
754 if (p->b[j] != emptybrick)
755 for (int k=0; k<8; k++)
756 v[j] |= p->b[j]->d[k+kadd] ;
757 }
758 int r = 0 ;
759 for (i=3; i>=0; i--) {
760 int vv = v[i] ;
761 for (int j=0; j<8; j++) {
762 r += r ;
763 if (vv & (0xf << (4 * j)))
764 r++ ;
765 }
766 }
767 return r ;
768 }
769
findedges(bigint * ptop,bigint * pleft,bigint * pbottom,bigint * pright)770 void qlifealgo::findedges(bigint *ptop, bigint *pleft, bigint *pbottom, bigint *pright) {
771 // AKT: following code is from fit() but all goal/size stuff
772 // has been removed so it finds the exact pattern edges
773 bigint xmin = 0 ;
774 bigint xmax = 1 ;
775 bigint ymin = 0 ;
776 bigint ymax = 1 ;
777 getPopulation() ; // make sure pop values are valid
778 oddgen = getGeneration().odd() ;
779 kadd = oddgen ? 8 : 0 ;
780 quickb = 0xfff << (8 + oddgen * 12) ;
781 int currdepth = rootlev ;
782 if (root == nullroots[currdepth] || root->pop[oddgen] == 0) {
783 // AKT: return impossible edges to indicate empty pattern;
784 // not really a problem because caller should check first
785 *ptop = 1 ;
786 *pleft = 1 ;
787 *pbottom = 0 ;
788 *pright = 0 ;
789 return ;
790 }
791 vector<supertile *> top, left, bottom, right ;
792 top.push_back(root) ;
793 left.push_back(root) ;
794 bottom.push_back(root) ;
795 right.push_back(root) ;
796 int topbm = 0, bottombm = 0, rightbm = 0, leftbm = 0 ;
797 int bitval = (currdepth + 1) / 2 * 3 + 5 ;
798 while (bitval > 0) {
799 if (bitval == 5) { // we have leaf nodes; turn them into bitmasks
800 topbm = getvbitsfromleaves(top) ;
801 bottombm = getvbitsfromleaves(bottom) ;
802 leftbm = gethbitsfromleaves(left) ;
803 rightbm = gethbitsfromleaves(right) ;
804 }
805 if (bitval <= 5) {
806 int sz = 1 << bitval ;
807 int masklo = (1 << (sz >> 1)) - 1 ;
808 int maskhi = ~masklo ;
809 ymax += ymax ;
810 xmax += xmax ;
811 ymin += ymin ;
812 xmin += xmin ;
813 if ((topbm & maskhi) == 0) {
814 ymax.add_smallint(-1) ;
815 } else {
816 topbm = (topbm >> (sz >> 1)) & masklo ;
817 }
818 if ((bottombm & masklo) == 0) {
819 ymin.add_smallint(1) ;
820 bottombm = (bottombm >> (sz >> 1)) & masklo ;
821 }
822 if ((rightbm & masklo) == 0) {
823 xmax.add_smallint(-1) ;
824 rightbm = (rightbm >> (sz >> 1)) & masklo ;
825 }
826 if ((leftbm & maskhi) == 0) {
827 xmin.add_smallint(1) ;
828 } else {
829 leftbm = (leftbm >> (sz >> 1)) & masklo ;
830 }
831 bitval-- ;
832 } else {
833 vector<supertile *> newv ;
834 int outer = highsub(top, newv, currdepth) ;
835 allsub(newv, top, currdepth-1) ;
836 ymax <<= 3 ;
837 ymax -= (7 - outer) ;
838 outer = lowsub(bottom, newv, currdepth) ;
839 allsub(newv, bottom, currdepth-1) ;
840 ymin <<= 3 ;
841 ymin += outer ;
842 allsub(left, newv, currdepth) ;
843 outer = lowsub(newv, left, currdepth-1) ;
844 xmin <<= 3 ;
845 xmin += outer ;
846 allsub(right, newv, currdepth) ;
847 outer = highsub(newv, right, currdepth-1) ;
848 xmax <<= 3 ;
849 xmax -= (7-outer) ;
850 currdepth -= 2 ;
851 bitval -= 3 ;
852 }
853 }
854 if (bitval > 0) {
855 xmin <<= bitval ;
856 ymin <<= bitval ;
857 xmax <<= bitval ;
858 ymax <<= bitval ;
859 }
860 if (oddgen) {
861 xmin += 1 ;
862 ymin += 1 ;
863 xmax += 1 ;
864 ymax += 1 ;
865 }
866 xmin += bmin ;
867 ymin += bmin ;
868 xmax += bmin ;
869 ymax += bmin ;
870 ymax -= 1 ;
871 xmax -= 1 ;
872 ymin.mul_smallint(-1) ;
873 ymax.mul_smallint(-1) ;
874 // set pattern edges
875 *ptop = ymax ; // due to y flip
876 *pbottom = ymin ; // due to y flip
877 *pleft = xmin ;
878 *pright = xmax ;
879 }
880
fit(viewport & view,int force)881 void qlifealgo::fit(viewport &view, int force) {
882 bigint xmin = 0 ;
883 bigint xmax = 1 ;
884 bigint ymin = 0 ;
885 bigint ymax = 1 ;
886 getPopulation() ; // make sure pop values are valid
887 oddgen = getGeneration().odd() ;
888 kadd = oddgen ? 8 : 0 ;
889 quickb = 0xfff << (8 + oddgen * 12) ;
890 int xgoal = view.getwidth() ;
891 int ygoal = view.getheight() ;
892 if (xgoal < 8)
893 xgoal = 8 ;
894 if (ygoal < 8)
895 ygoal = 8 ;
896 int xsize = 1 ;
897 int ysize = 1 ;
898 int currdepth = rootlev ;
899 if (root == nullroots[currdepth] || root->pop[oddgen] == 0) {
900 view.center() ;
901 view.setmag(MAX_MAG) ;
902 return ;
903 }
904 vector<supertile *> top, left, bottom, right ;
905 top.push_back(root) ;
906 left.push_back(root) ;
907 bottom.push_back(root) ;
908 right.push_back(root) ;
909 int topbm = 0, bottombm = 0, rightbm = 0, leftbm = 0 ;
910 int bitval = (currdepth + 1) / 2 * 3 + 5 ;
911 while (bitval > 0) {
912 if (bitval == 5) { // we have leaf nodes; turn them into bitmasks
913 topbm = getvbitsfromleaves(top) ;
914 bottombm = getvbitsfromleaves(bottom) ;
915 leftbm = gethbitsfromleaves(left) ;
916 rightbm = gethbitsfromleaves(right) ;
917 }
918 if (bitval <= 5) {
919 int sz = 1 << bitval ;
920 int masklo = (1 << (sz >> 1)) - 1 ;
921 int maskhi = ~masklo ;
922 ymax += ymax ;
923 xmax += xmax ;
924 ymin += ymin ;
925 xmin += xmin ;
926 xsize <<= 1 ;
927 ysize <<= 1 ;
928 if ((topbm & maskhi) == 0) {
929 ymax.add_smallint(-1) ;
930 ysize-- ;
931 } else {
932 topbm = (topbm >> (sz >> 1)) & masklo ;
933 }
934 if ((bottombm & masklo) == 0) {
935 ymin.add_smallint(1) ;
936 ysize-- ;
937 bottombm = (bottombm >> (sz >> 1)) & masklo ;
938 }
939 if ((rightbm & masklo) == 0) {
940 xmax.add_smallint(-1) ;
941 xsize-- ;
942 rightbm = (rightbm >> (sz >> 1)) & masklo ;
943 }
944 if ((leftbm & maskhi) == 0) {
945 xmin.add_smallint(1) ;
946 xsize-- ;
947 } else {
948 leftbm = (leftbm >> (sz >> 1)) & masklo ;
949 }
950 bitval-- ;
951 } else {
952 vector<supertile *> newv ;
953 ysize <<= 3 ;
954 int outer = highsub(top, newv, currdepth) ;
955 allsub(newv, top, currdepth-1) ;
956 ymax <<= 3 ;
957 ymax -= (7 - outer) ;
958 ysize -= (7 - outer) ;
959 outer = lowsub(bottom, newv, currdepth) ;
960 allsub(newv, bottom, currdepth-1) ;
961 ymin <<= 3 ;
962 ymin += outer ;
963 ysize -= outer ;
964 xsize <<= 3 ;
965 allsub(left, newv, currdepth) ;
966 outer = lowsub(newv, left, currdepth-1) ;
967 xmin <<= 3 ;
968 xmin += outer ;
969 xsize -= outer ;
970 allsub(right, newv, currdepth) ;
971 outer = highsub(newv, right, currdepth-1) ;
972 xmax <<= 3 ;
973 xmax -= (7-outer) ;
974 xsize -= (7-outer) ;
975 currdepth -= 2 ;
976 bitval -= 3 ;
977 }
978 if (xsize > xgoal || ysize > ygoal)
979 break ;
980 }
981 if (bitval > 0) {
982 xmin <<= bitval ;
983 ymin <<= bitval ;
984 xmax <<= bitval ;
985 ymax <<= bitval ;
986 }
987 if (oddgen) {
988 xmin += 1 ;
989 ymin += 1 ;
990 xmax += 1 ;
991 ymax += 1 ;
992 }
993 xmin += bmin ;
994 ymin += bmin ;
995 xmax += bmin ;
996 ymax += bmin ;
997 ymax -= 1 ;
998 xmax -= 1 ;
999 ymin.mul_smallint(-1) ;
1000 ymax.mul_smallint(-1) ;
1001 if (!force) {
1002 // if all four of the above dimensions are in the viewport, don't change
1003 if (view.contains(xmin, ymin) && view.contains(xmax, ymax))
1004 return ;
1005 }
1006 int mag = - bitval ;
1007 while (2 * xsize <= xgoal && 2 * ysize <= ygoal && mag < MAX_MAG) {
1008 mag++ ;
1009 xsize *= 2 ;
1010 ysize *= 2 ;
1011 }
1012 while (xsize > xgoal || ysize > ygoal) {
1013 mag-- ;
1014 xsize /= 2 ;
1015 ysize /= 2 ;
1016 }
1017 view.setpositionmag(xmin, xmax, ymin, ymax, mag) ;
1018 }
1019 /**
1020 * Fixed for qlife.
1021 */
lowerRightPixel(bigint & x,bigint & y,int mag)1022 void qlifealgo::lowerRightPixel(bigint &x, bigint &y, int mag) {
1023 if (mag >= 0)
1024 return ;
1025 x -= oddgen ;
1026 x -= bmin ;
1027 x >>= -mag ;
1028 x <<= -mag ;
1029 x += bmin ;
1030 x += oddgen ;
1031 y -= 1 ;
1032 y += bmin ;
1033 y += oddgen ;
1034 y >>= -mag ;
1035 y <<= -mag ;
1036 y -= bmin ;
1037 y += 1 ;
1038 y -= oddgen ;
1039 }
1040