1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 // Implementation code for the "Larger than Life" family of rules.
5 // See Help/Algorithms/Larger_than_Life.html for more info.
6
7 #include "ltlalgo.h"
8 #include "liferules.h"
9 #include "util.h"
10 #include <stdlib.h> // for malloc, free, etc
11 #include <limits.h> // for INT_MIN and INT_MAX
12 #include <string.h> // for memset and strchr
13
14 // -----------------------------------------------------------------------------
15
16 // set default rule to match Life
17 static const char *DEFAULTRULE = "R1,C0,M0,S2..3,B3..3,NM";
18
19 #define MAXRANGE 500
20 #define DEFAULTSIZE 400 // must be >= 2
21
22 // maximum number of columns in a cell's neighborhood (used in fast_Moore)
23 static const int MAXNCOLS = 2 * MAXRANGE + 1;
24
25 // maximum number of cells in grid must be < 2^31 so population can't overflow
26 #define MAXCELLS 100000000.0
27
28 // faster_Neumann_* calls are much slower than fast_Neumann when the
29 // range is 1 or 2, similar when 5, but much faster when 10 or above
30 #define SMALL_NN_RANGE 4
31
32 // -----------------------------------------------------------------------------
33
34 // Create a new empty universe.
35
ltlalgo()36 ltlalgo::ltlalgo()
37 {
38 shape = NULL ;
39 // create a bounded universe with the default grid size, range and neighborhood
40 unbounded = false;
41 range = 1;
42 ntype = 'M';
43 colcounts = NULL;
44 create_grids(DEFAULTSIZE, DEFAULTSIZE);
45 generation = 0;
46 increment = 1;
47 show_warning = true;
48 }
49
50 // -----------------------------------------------------------------------------
51
52 // Destroy the universe.
53
~ltlalgo()54 ltlalgo::~ltlalgo()
55 {
56 free(outergrid1);
57 if (outergrid2) free(outergrid2);
58 if (colcounts) free(colcounts);
59 if (shape) free(shape) ;
60 }
61
62 // -----------------------------------------------------------------------------
63
allocate_colcounts()64 void ltlalgo::allocate_colcounts()
65 {
66 // allocate the array used for cumulative column counts of state-1 cells
67 if (colcounts) free(colcounts);
68 if (ntype == 'M') {
69 colcounts = (int*) malloc(outerbytes * sizeof(int));
70 // if NULL then use fast_Moore, otherwise faster_Moore_*
71 } else if (ntype == 'N') {
72 if (range <= SMALL_NN_RANGE) {
73 // use fast_Neumann (faster than faster_Neumann_* for small ranges)
74 colcounts = NULL;
75 } else {
76 // additional rows are needed to calculate counts in faster_Neumann_*
77 colcounts = (int*) malloc(outerwd * (outerht + (outerwd-1)/2) * sizeof(int));
78 // if NULL then use fast_Neumann
79 }
80 } else if (ntype == 'C') {
81 colcounts = NULL ;
82 // use fast_Shaped
83 } else {
84 lifefatal("Unexpected ntype!");
85 }
86 }
87
88 // -----------------------------------------------------------------------------
89
create_grids(int wd,int ht)90 void ltlalgo::create_grids(int wd, int ht)
91 {
92 // create a bounded universe of given width and height
93 gwd = wd;
94 ght = ht;
95 border = range + 1; // the extra 1 is needed by faster_Moore_*
96 outerwd = gwd + border * 2; // add left and right border
97 outerht = ght + border * 2; // add top and bottom border
98 outerbytes = outerwd * outerht;
99
100 allocate_colcounts();
101
102 // allocate memory for grid
103 int offset = border * outerwd + border;
104 outergrid1 = (unsigned char*) calloc(outerbytes, sizeof(unsigned char));
105 if (outergrid1 == NULL) lifefatal("Not enough memory for LtL grid!");
106 // point currgrid to top left non-border cells within outergrid1
107 currgrid = outergrid1 + offset;
108
109 // if using fast_Moore or fast_Neumann we need to allocate outergrid2
110 if (colcounts == NULL) {
111 outergrid2 = (unsigned char*) calloc(outerbytes, sizeof(unsigned char));
112 if (outergrid2 == NULL) lifefatal("Not enough memory for LtL grids!");
113 // point nextgrid to top left non-border cells within outergrid2
114 nextgrid = outergrid2 + offset;
115 } else {
116 // faster_* calls don't use outergrid2
117 outergrid2 = NULL;
118 nextgrid = NULL;
119 }
120
121 // set grid coordinates of cell at bottom right corner of inner grid
122 gwdm1 = gwd - 1;
123 ghtm1 = ght - 1;
124
125 // set cell coordinates of inner grid edges (middle of grid is 0,0)
126 gtop = -int(ght / 2);
127 gleft = -int(gwd / 2);
128 gbottom = gtop + ghtm1;
129 gright = gleft + gwdm1;
130
131 // set bigint versions of inner grid edges (used by GUI code)
132 gridtop = gtop;
133 gridleft = gleft;
134 gridbottom = gbottom;
135 gridright = gright;
136
137 // the universe is empty
138 population = 0;
139
140 // init boundaries so next birth will change them
141 empty_boundaries();
142 }
143
144 // -----------------------------------------------------------------------------
145
empty_boundaries()146 void ltlalgo::empty_boundaries()
147 {
148 minx = INT_MAX;
149 miny = INT_MAX;
150 maxx = INT_MIN;
151 maxy = INT_MIN;
152 }
153
154 // -----------------------------------------------------------------------------
155
clearall()156 void ltlalgo::clearall()
157 {
158 lifefatal("clearall is not implemented");
159 }
160
161 // -----------------------------------------------------------------------------
162
NumCellStates()163 int ltlalgo::NumCellStates()
164 {
165 return maxCellStates;
166 }
167
168 // -----------------------------------------------------------------------------
169
endofpattern()170 void ltlalgo::endofpattern()
171 {
172 show_warning = true;
173 }
174
175 // -----------------------------------------------------------------------------
176
resize_grids(int up,int down,int left,int right)177 const char* ltlalgo::resize_grids(int up, int down, int left, int right)
178 {
179 // try to resize an unbounded universe by given amounts (possibly -ve)
180 int newwd = gwd + left + right;
181 int newht = ght + up + down;
182 if ((float)newwd * (float)newht > MAXCELLS) {
183 return "Sorry, but the universe can't be expanded that far.";
184 }
185
186 // check if new grid edges would be outside editing limits
187 int newtop = gtop - up;
188 int newleft = gleft - left;
189 int newbottom = newtop + newht - 1;
190 int newright = newleft + newwd - 1;
191 if (newtop < -1000000000 || newleft < -1000000000 ||
192 newbottom > 1000000000 || newright > 1000000000) {
193 return "Sorry, but the grid edges can't be outside the editing limits.";
194 }
195
196 int newbytes = newwd * newht;
197 unsigned char* newcurr = (unsigned char*) calloc(newbytes, sizeof(unsigned char));
198 unsigned char* newnext = (unsigned char*) calloc(newbytes, sizeof(unsigned char));
199 if (newcurr == NULL || newnext == NULL) {
200 if (newcurr) free(newcurr);
201 if (newnext) free(newnext);
202 return "Not enough memory to resize universe!";
203 }
204
205 // resize succeeded so copy pattern from currgrid into newcurr
206 if (population > 0) {
207 unsigned char* src = currgrid + miny * outerwd + minx;
208 unsigned char* dest = newcurr + (miny + up) * newwd + minx + left;
209 int xbytes = maxx - minx + 1;
210 for (int row = miny; row <= maxy; row++) {
211 memcpy(dest, src, xbytes);
212 src += outerwd;
213 dest += newwd;
214 }
215 // shift pattern boundaries
216 minx += left;
217 maxx += left;
218 miny += up;
219 maxy += up;
220 }
221
222 free(outergrid1);
223 if (outergrid2) free(outergrid2);
224 outergrid1 = currgrid = newcurr;
225 outergrid2 = nextgrid = newnext;
226
227 outerwd = gwd = newwd;
228 outerht = ght = newht;
229 outerbytes = newbytes;
230
231 // set grid coordinates of cell at bottom right corner of grid
232 gwdm1 = gwd - 1;
233 ghtm1 = ght - 1;
234
235 // adjust cell coordinates of grid edges
236 gtop -= up;
237 gleft -= left;
238 gbottom = gtop + ghtm1;
239 gright = gleft + gwdm1;
240
241 // set bigint versions of grid edges (used by GUI code)
242 gridtop = gtop;
243 gridleft = gleft;
244 gridbottom = gbottom;
245 gridright = gright;
246
247 allocate_colcounts();
248
249 if (colcounts) {
250 // faster_* calls don't use outergrid2
251 free(outergrid2);
252 outergrid2 = NULL;
253 nextgrid = NULL;
254 }
255
256 return NULL; // success
257 }
258
259 // -----------------------------------------------------------------------------
260
261 // Set the cell at the given location to the given state.
262
setcell(int x,int y,int newstate)263 int ltlalgo::setcell(int x, int y, int newstate)
264 {
265 if (newstate < 0 || newstate >= maxCellStates) return -1;
266
267 if (unbounded) {
268 // check if universe needs to be expanded
269 if (x < gleft || x > gright || y < gtop || y > gbottom) {
270 if (population == 0) {
271 // no need to resize empty grids;
272 // just adjust grid edges so that x,y is in middle of grid
273 gtop = y - int(ght / 2);
274 gleft = x - int(gwd / 2);
275 gbottom = gtop + ghtm1;
276 gright = gleft + gwdm1;
277 // set bigint versions of grid edges (used by GUI code)
278 gridtop = gtop;
279 gridleft = gleft;
280 gridbottom = gbottom;
281 gridright = gright;
282 } else {
283 int up = y < gtop ? gtop - y : 0;
284 int down = y > gbottom ? y - gbottom : 0;
285 int left = x < gleft ? gleft - x : 0;
286 int right = x > gright ? x - gright : 0;
287
288 // if the down or right amount is 1 then it's likely a pattern file
289 // is being loaded, so increase the amount to reduce the number of
290 // resize_grids calls and speed up the loading time
291 if (down == 1) down = 10;
292 if (right == 1) right = 10;
293
294 const char* errmsg = resize_grids(up, down, left, right);
295 if (errmsg) {
296 if (show_warning) lifewarning(errmsg);
297 // prevent further warning messages until endofpattern is called
298 // (this avoids user having to close thousands of dialog boxes
299 // if they attempted to paste a large pattern)
300 show_warning = false;
301 return -1;
302 }
303 }
304 }
305 } else {
306 // check if x,y is outside bounded universe
307 if (x < gleft || x > gright) return -1;
308 if (y < gtop || y > gbottom) return -1;
309 }
310
311 // set x,y cell in currgrid
312 int gx = x - gleft;
313 int gy = y - gtop;
314 unsigned char* cellptr = currgrid + gy * outerwd + gx;
315 int oldstate = *cellptr;
316 if (newstate != oldstate) {
317 *cellptr = (unsigned char)newstate;
318 // population might change
319 if (oldstate == 0 && newstate > 0) {
320 population++;
321 if (gx < minx) minx = gx;
322 if (gx > maxx) maxx = gx;
323 if (gy < miny) miny = gy;
324 if (gy > maxy) maxy = gy;
325 } else if (oldstate > 0 && newstate == 0) {
326 population--;
327 if (population == 0) empty_boundaries();
328 }
329 }
330
331 return 0;
332 }
333
334 // -----------------------------------------------------------------------------
335
336 // Get the state of the cell at the given location.
337
getcell(int x,int y)338 int ltlalgo::getcell(int x, int y)
339 {
340 if (unbounded) {
341 // cell outside grid is dead
342 if (x < gleft || x > gright) return 0;
343 if (y < gtop || y > gbottom) return 0;
344 } else {
345 // error if x,y is outside bounded universe
346 if (x < gleft || x > gright) return -1;
347 if (y < gtop || y > gbottom) return -1;
348 }
349
350 // get x,y cell in currgrid
351 unsigned char* cellptr = currgrid + (y - gtop) * outerwd + (x - gleft);
352 return *cellptr;
353 }
354
355 // -----------------------------------------------------------------------------
356
357 // Return the distance to the next non-zero cell in the given row,
358 // or -1 if there is none.
359
nextcell(int x,int y,int & v)360 int ltlalgo::nextcell(int x, int y, int& v)
361 {
362 if (population == 0) return -1;
363
364 // check if y is outside grid
365 if (y < gtop || y > gbottom) return -1;
366
367 // check if x is outside right edge
368 if (x > gright) return -1;
369
370 // init distance
371 int d = 0;
372
373 // if x is outside left edge then set it to gleft and increase d
374 // (this is necessary in case the user makes a selection outside
375 // gleft when the universe is unbounded)
376 if (x < gleft) {
377 d = gleft - x;
378 x = gleft;
379 }
380
381 // get x,y cell in currgrid
382 unsigned char* cellptr = currgrid + (y - gtop) * outerwd + (x - gleft);
383
384 do {
385 v = *cellptr;
386 if (v > 0) return d; // found a non-zero cell
387 d++;
388 cellptr++;
389 x++;
390 } while (x <= gright);
391
392 return -1;
393 }
394
395 // -----------------------------------------------------------------------------
396
397 static bigint bigpop;
398
getPopulation()399 const bigint& ltlalgo::getPopulation()
400 {
401 bigpop = population;
402 return bigpop;
403 }
404
405 // -----------------------------------------------------------------------------
406
isEmpty()407 int ltlalgo::isEmpty()
408 {
409 return population == 0 ? 1 : 0;
410 }
411
412 // -----------------------------------------------------------------------------
413
update_current_grid(unsigned char & state,int ncount)414 void ltlalgo::update_current_grid(unsigned char &state, int ncount)
415 {
416 // return the state of the cell based on the neighbor count
417 if (state == 0) {
418 // this cell is dead
419 if (ncount >= minB && ncount <= maxB) {
420 // new cell is born
421 state = 1;
422 population++;
423 }
424 } else if (state == 1) {
425 // this cell is alive
426 if (ncount < minS || ncount > maxS) {
427 // this cell doesn't survive
428 if (maxCellStates > 2) {
429 // cell decays to state 2
430 state = 2;
431 } else {
432 // cell dies
433 state = 0;
434 population--;
435 if (population == 0) empty_boundaries();
436 }
437 }
438 } else {
439 // state is > 1 so this cell will eventually die
440 if (state + 1 < maxCellStates) {
441 state++;
442 } else {
443 // cell dies
444 state = 0;
445 population--;
446 if (population == 0) empty_boundaries();
447 }
448 }
449 }
450
451 // -----------------------------------------------------------------------------
452
update_next_grid(int x,int y,int xyoffset,int ncount)453 void ltlalgo::update_next_grid(int x, int y, int xyoffset, int ncount)
454 {
455 // x,y cell in nextgrid might change based on the given neighborhood count
456 unsigned char state = *(currgrid + xyoffset);
457 if (state == 0) {
458 // this cell is dead
459 if (ncount >= minB && ncount <= maxB) {
460 // new cell is born in nextgrid
461 unsigned char* nextcell = nextgrid + xyoffset;
462 *nextcell = 1;
463 population++;
464 if (x < minx) minx = x;
465 if (x > maxx) maxx = x;
466 if (y < miny) miny = y;
467 if (y > maxy) maxy = y;
468 }
469 } else if (state == 1) {
470 // this cell is alive
471 if (ncount >= minS && ncount <= maxS) {
472 // cell survives so copy into nextgrid
473 unsigned char* nextcell = nextgrid + xyoffset;
474 *nextcell = 1;
475 // population doesn't change but pattern limits in nextgrid might
476 if (x < minx) minx = x;
477 if (x > maxx) maxx = x;
478 if (y < miny) miny = y;
479 if (y > maxy) maxy = y;
480 } else if (maxCellStates > 2) {
481 // cell decays to state 2
482 unsigned char* nextcell = nextgrid + xyoffset;
483 *nextcell = 2;
484 // population doesn't change but pattern limits in nextgrid might
485 if (x < minx) minx = x;
486 if (x > maxx) maxx = x;
487 if (y < miny) miny = y;
488 if (y > maxy) maxy = y;
489 } else {
490 // cell dies
491 population--;
492 if (population == 0) empty_boundaries();
493 }
494 } else {
495 // state is > 1 so this cell will eventually die
496 if (state + 1 < maxCellStates) {
497 unsigned char* nextcell = nextgrid + xyoffset;
498 *nextcell = state + 1;
499 // population doesn't change but pattern limits in nextgrid might
500 if (x < minx) minx = x;
501 if (x > maxx) maxx = x;
502 if (y < miny) miny = y;
503 if (y > maxy) maxy = y;
504 } else {
505 // cell dies
506 population--;
507 if (population == 0) empty_boundaries();
508 }
509 }
510 }
511
512 // -----------------------------------------------------------------------------
513
faster_Moore_bounded(int mincol,int minrow,int maxcol,int maxrow)514 void ltlalgo::faster_Moore_bounded(int mincol, int minrow, int maxcol, int maxrow)
515 {
516 // use Adam P. Goucher's algorithm to calculate Moore neighborhood counts
517 // in a bounded universe; note that currgrid is surrounded by a border that
518 // might contain live cells (the border is range+1 cells thick and the
519 // outermost cells are always dead)
520
521 // the given limits are relative to currgrid so we need to add border
522 // so they are relative to outergrid1, and then expand them by range
523 int bmr = border - range;
524 int bpr = border + range;
525 minrow += bmr;
526 mincol += bmr;
527 maxrow += bpr;
528 maxcol += bpr;
529
530 // calculate cumulative counts for each column and store in colcounts
531
532 unsigned char* cellptr = outergrid1 + minrow * outerwd + mincol;
533 int* ccptr = colcounts + minrow * outerwd + mincol;
534 int *prevptr = NULL;
535 int width = (maxcol - mincol + 1);
536 int nextrow = outerwd - width;
537 int rowcount = 0;
538
539 for (int j = mincol; j <= maxcol; j++) {
540 if (*cellptr == 1) rowcount++;
541 *ccptr = rowcount;
542 cellptr++;
543 ccptr++;
544 }
545 cellptr += nextrow;
546 ccptr += nextrow;
547 prevptr = ccptr - outerwd;
548 for (int i = minrow + 1; i <= maxrow; i++) {
549 rowcount = 0;
550 for (int j = mincol; j <= maxcol; j++) {
551 if (*cellptr == 1) rowcount++;
552 *ccptr = *prevptr + rowcount;
553 cellptr++;
554 ccptr++;
555 prevptr++;
556 }
557 cellptr += nextrow;
558 ccptr += nextrow;
559 prevptr += nextrow;
560 }
561
562 // restore given limits (necessary for update_current_grid calls)
563 minrow -= bmr;
564 mincol -= bmr;
565 maxrow -= bpr;
566 maxcol -= bpr;
567
568 // calculate final neighborhood counts using values in colcounts
569 // and update the corresponding cells in current grid
570
571 int* colptr = colcounts + (minrow + bpr) * outerwd;
572 ccptr = colptr + mincol + bpr;
573 unsigned char* stateptr = currgrid + minrow*outerwd+mincol;
574 unsigned char state = *stateptr;
575 update_current_grid(state, *ccptr);
576 *stateptr = state;
577 if (state) {
578 if (mincol < minx) minx = mincol;
579 if (mincol > maxx) maxx = mincol;
580 if (minrow < miny) miny = minrow;
581 if (minrow > maxy) maxy = minrow;
582 }
583
584 bool rowchanged = false;
585 int bmrm1 = border - range - 1;
586 stateptr = currgrid + minrow*outerwd + mincol+1;
587 for (int j = mincol+1; j <= maxcol; j++) {
588 // do i == minrow
589 int* ccptr1 = colptr + (j + bpr);
590 int* ccptr2 = colptr + (j + bmrm1);
591 state = *stateptr;
592 update_current_grid(state, *ccptr1 - *ccptr2);
593 *stateptr++ = state;
594 if (state) {
595 if (j < minx) minx = j;
596 if (j > maxx) maxx = j;
597 rowchanged = true;
598 }
599 }
600 if (rowchanged) {
601 if (minrow < miny) miny = minrow;
602 if (minrow > maxy) maxy = minrow;
603 }
604
605 bool colchanged = false;
606 colptr = colcounts + mincol + bpr;
607 stateptr = currgrid + (minrow+1)*outerwd + mincol;
608 for (int i = minrow+1; i <= maxrow; i++) {
609 // do j == mincol
610 int* ccptr1 = colptr + (i + bpr) * outerwd;
611 int* ccptr2 = colptr + (i + bmrm1) * outerwd;
612 state = *stateptr;
613 update_current_grid(state, *ccptr1 - *ccptr2);
614 *stateptr = state;
615 stateptr += outerwd;
616 if (state) {
617 if (i < miny) miny = i;
618 if (i > maxy) maxy = i;
619 colchanged = true;
620 }
621 }
622 if (colchanged) {
623 if (mincol < minx) minx = mincol;
624 if (mincol > maxx) maxx = mincol;
625 }
626
627 rowchanged = false;
628 for (int i = minrow+1; i <= maxrow; i++) {
629 int* ipr = colcounts + (i + bpr) * outerwd;
630 int* imrm1 = colcounts + (i + bmrm1) * outerwd;
631 stateptr = currgrid + i*outerwd + mincol+1;
632 for (int j = mincol+1; j <= maxcol; j++) {
633 int jpr = j + bpr;
634 int jmrm1 = j + bmrm1;
635 int* ccptr1 = ipr + jpr;
636 int* ccptr2 = imrm1 + jmrm1;
637 int* ccptr3 = ipr + jmrm1;
638 int* ccptr4 = imrm1 + jpr;
639 state = *stateptr;
640 update_current_grid(state, *ccptr1 + *ccptr2 - *ccptr3 - *ccptr4);
641 *stateptr++ = state;
642 if (state) {
643 if (j < minx) minx = j;
644 if (j > maxx) maxx = j;
645 rowchanged = true;
646 }
647 }
648 if (rowchanged) {
649 if (i < miny) miny = i;
650 if (i > maxy) maxy = i;
651 rowchanged = false;
652 }
653 }
654 }
655
656 // -----------------------------------------------------------------------------
657
faster_Moore_bounded2(int mincol,int minrow,int maxcol,int maxrow)658 void ltlalgo::faster_Moore_bounded2(int mincol, int minrow, int maxcol, int maxrow)
659 {
660 // use Adam P. Goucher's algorithm to calculate Moore neighborhood counts
661 // in a bounded universe; note that currgrid is surrounded by a border that
662 // might contain live cells (the border is range+1 cells thick and the
663 // outermost cells are always dead)
664
665 // the given limits are relative to currgrid so we need to add border
666 // so they are relative to outergrid1, and then expand them by range
667 int bmr = border - range;
668 int bpr = border + range;
669 minrow += bmr;
670 mincol += bmr;
671 maxrow += bpr;
672 maxcol += bpr;
673
674 // calculate cumulative counts for each column and store in colcounts
675
676 unsigned char* cellptr = outergrid1 + minrow * outerwd + mincol;
677 int* ccptr = colcounts + minrow * outerwd + mincol;
678 int *prevptr = NULL;
679 int width = (maxcol - mincol + 1);
680 int nextrow = outerwd - width;
681 int rowcount = 0;
682
683 // compute 4 cell offset
684 int offset = (4 - ((g_uintptr_t)cellptr & 3)) & 3;
685 if (offset > width) offset = width;
686
687 // process in 4 cell chunks
688 int chunks = (width - offset) >> 2;
689 int remainder = (width - offset) - (chunks << 2);
690 int j = 0;
691
692 // process cells in the first row
693
694 // process cells up to the first 4 cell chunk
695 for (j = 0; j < offset; j++) {
696 rowcount += *cellptr++;
697 *ccptr++ = rowcount;
698 }
699
700 // process any 4 cell chunks
701 unsigned int *lcellptr = (unsigned int*)cellptr;
702 for (j = 0; j < chunks; j++) {
703 if (*lcellptr++) {
704 rowcount += *cellptr++;
705 *ccptr++ = rowcount;
706 rowcount += *cellptr++;
707 *ccptr++ = rowcount;
708 rowcount += *cellptr++;
709 *ccptr++ = rowcount;
710 rowcount += *cellptr++;
711 *ccptr++ = rowcount;
712 } else {
713 *ccptr++ = rowcount;
714 *ccptr++ = rowcount;
715 *ccptr++ = rowcount;
716 *ccptr++ = rowcount;
717 cellptr += 4;
718 }
719 }
720
721 // process any remaining cells
722 for (j = 0; j < remainder; j++) {
723 rowcount += *cellptr++;
724 *ccptr++ = rowcount;
725 }
726 cellptr += nextrow;
727 ccptr += nextrow;
728 prevptr = ccptr - outerwd;
729
730 // process the remaining rows of cells
731
732 for (int i = minrow + 1; i <= maxrow; i++) {
733 rowcount = 0;
734
735 // compute 4 cell offset
736 offset = (4 - ((g_uintptr_t)cellptr & 3)) & 3;
737 if (offset > width) offset = width;
738
739 // process in 4 cell chunks
740 chunks = (width - offset) >> 2;
741 remainder = (width - offset) - (chunks << 2);
742
743 // process cells up to the first 4 cell chunk
744 for (j = 0; j < offset; j++) {
745 rowcount += *cellptr++;
746 *ccptr++ = *prevptr++ + rowcount;
747 }
748 lcellptr = (unsigned int*)cellptr;
749
750 // process any 4 cell chunks
751 for (j = 0; j < chunks; j++) {
752 // check if any of the cells are alive
753 if (*lcellptr++) {
754 rowcount += *cellptr++;
755 *ccptr++ = *prevptr++ + rowcount;
756 rowcount += *cellptr++;
757 *ccptr++ = *prevptr++ + rowcount;
758 rowcount += *cellptr++;
759 *ccptr++ = *prevptr++ + rowcount;
760 rowcount += *cellptr++;
761 *ccptr++ = *prevptr++ + rowcount;
762 } else {
763 *ccptr++ = *prevptr++ + rowcount;
764 *ccptr++ = *prevptr++ + rowcount;
765 *ccptr++ = *prevptr++ + rowcount;
766 *ccptr++ = *prevptr++ + rowcount;
767 cellptr += 4;
768 }
769 }
770
771 // process any remaining cells
772 for (j = 0; j < remainder; j++) {
773 rowcount += *cellptr++;
774 *ccptr++ = *prevptr++ + rowcount;
775 }
776 // next row
777 cellptr += nextrow;
778 ccptr += nextrow;
779 prevptr += nextrow;
780 }
781
782 // restore given limits (necessary for update_current_grid calls)
783 minrow -= bmr;
784 mincol -= bmr;
785 maxrow -= bpr;
786 maxcol -= bpr;
787
788 // calculate final neighborhood counts using values in colcounts
789 // and update the corresponding cells in current grid
790
791 int* colptr = colcounts + (minrow + bpr) * outerwd;
792 ccptr = colptr + mincol + bpr;
793 unsigned char* stateptr = currgrid + minrow*outerwd+mincol;
794 int ncount = *ccptr;
795 if (*stateptr == 0) {
796 if (ncount >= minB && ncount <= maxB) {
797 *stateptr = 1;
798 population++;
799 minx = mincol;
800 maxx = mincol;
801 miny = minrow;
802 maxy = minrow;
803 }
804 } else {
805 if (ncount < minS || ncount > maxS) {
806 *stateptr = 0;
807 population--;
808 }
809 else {
810 minx = mincol;
811 maxx = maxcol;
812 miny = minrow;
813 maxy = maxrow;
814 }
815 }
816
817 bool rowchanged = false;
818 int bmrm1 = border - range - 1;
819 stateptr = currgrid + minrow*outerwd + mincol+1;
820 int* ccptr1 = colptr + (mincol+1 + bpr);
821 int* ccptr2 = colptr + (mincol+1 + bmrm1);
822 for (j = mincol+1; j <= maxcol; j++) {
823 // do i == minrow
824 ncount = *ccptr1++ - *ccptr2++;
825 if (*stateptr == 0) {
826 if (ncount >= minB && ncount <= maxB) {
827 *stateptr = 1;
828 population++;
829 if (j < minx) minx = j;
830 if (j > maxx) maxx = j;
831 rowchanged = true;
832 }
833 } else {
834 if (ncount < minS || ncount > maxS) {
835 *stateptr = 0;
836 population--;
837 }
838 else {
839 if (j < minx) minx = j;
840 if (j > maxx) maxx = j;
841 rowchanged = true;
842 }
843 }
844 stateptr++;
845 }
846 if (rowchanged) {
847 if (minrow < miny) miny = minrow;
848 if (minrow > maxy) maxy = minrow;
849 }
850
851 bool colchanged = false;
852 colptr = colcounts + mincol + bpr;
853 stateptr = currgrid + (minrow+1)*outerwd + mincol;
854 ccptr1 = colptr + (minrow+1 + bpr) * outerwd;
855 ccptr2 = colptr + (minrow+1 + bmrm1) * outerwd;
856 for (int i = minrow+1; i <= maxrow; i++) {
857 // do j == mincol
858 ncount = *ccptr1 - *ccptr2;
859 if (*stateptr == 0) {
860 if (ncount >= minB && ncount <= maxB) {
861 *stateptr = 1;
862 population++;
863 if (i < miny) miny = i;
864 if (i > maxy) maxy = i;
865 colchanged = true;
866 }
867 } else {
868 if (ncount < minS || ncount > maxS) {
869 *stateptr = 0;
870 population--;
871 }
872 else {
873 if (i < miny) miny = i;
874 if (i > maxy) maxy = i;
875 colchanged = true;
876 }
877 }
878 stateptr += outerwd;
879 ccptr1 += outerwd;
880 ccptr2 += outerwd;
881 }
882 if (colchanged) {
883 if (mincol < minx) minx = mincol;
884 if (mincol > maxx) maxx = mincol;
885 }
886
887 rowchanged = false;
888 for (int i = minrow+1; i <= maxrow; i++) {
889 int* ipr = colcounts + (i + bpr) * outerwd;
890 int* imrm1 = colcounts + (i + bmrm1) * outerwd;
891 int jpr = mincol+1 + bpr;
892 int jmrm1 = mincol+1 + bmrm1;
893 ccptr1 = ipr + jpr;
894 ccptr2 = imrm1 + jmrm1;
895 int* ccptr3 = ipr + jmrm1;
896 int* ccptr4 = imrm1 + jpr;
897 stateptr = currgrid + i*outerwd + mincol+1;
898 for (j = mincol+1; j <= maxcol; j++) {
899 ncount = *ccptr1++ + *ccptr2++ - *ccptr3++ - *ccptr4++;
900 if (*stateptr == 0) {
901 if (ncount >= minB && ncount <= maxB) {
902 *stateptr = 1;
903 population++;
904 if (j < minx) minx = j;
905 if (j > maxx) maxx = j;
906 rowchanged = true;
907 }
908 } else {
909 if (ncount < minS || ncount > maxS) {
910 *stateptr = 0;
911 population--;
912 }
913 else {
914 if (j < minx) minx = j;
915 if (j > maxx) maxx = j;
916 rowchanged = true;
917 }
918 }
919 stateptr++;
920 }
921 if (rowchanged) {
922 if (i < miny) miny = i;
923 if (i > maxy) maxy = i;
924 rowchanged = false;
925 }
926 }
927 if (population == 0) empty_boundaries();
928 }
929
930 // -----------------------------------------------------------------------------
931
faster_Moore_unbounded(int mincol,int minrow,int maxcol,int maxrow)932 void ltlalgo::faster_Moore_unbounded(int mincol, int minrow, int maxcol, int maxrow)
933 {
934 // use Adam P. Goucher's algorithm to calculate Moore neighborhood counts
935 // in an unbounded universe; note that we can safely assume there is at least
936 // a 2*range border of dead cells surrounding the pattern
937
938 // temporarily expand the given limits
939 minrow -= range;
940 mincol -= range;
941 maxrow += range;
942 maxcol += range;
943
944 int r2 = range * 2;
945 int minrowpr2 = minrow+r2;
946 int mincolpr2 = mincol+r2;
947
948 // put zeros in top 2*range rows of colcounts
949 for (int i = minrow; i < minrowpr2; i++) {
950 int* ccptr = colcounts + i * outerwd + mincol;
951 for (int j = mincol; j <= maxcol; j++) {
952 *ccptr++ = 0;
953 }
954 }
955
956 // put zeros in left 2*range columns of colcounts
957 for (int j = mincol; j < mincolpr2; j++) {
958 int* ccptr = colcounts + minrowpr2 * outerwd + j;
959 for (int i = minrowpr2; i <= maxrow; i++) {
960 *ccptr = 0;
961 ccptr += outerwd;
962 }
963 }
964
965 unsigned char* cellptr = currgrid + minrowpr2 * outerwd + mincolpr2;
966 int* ccptr = colcounts + minrowpr2 * outerwd + mincolpr2;
967 int* prevptr = ccptr - outerwd;
968 int width = (maxcol - mincolpr2 + 1);
969 int nextrow = outerwd - width;
970 int rowcount = 0;
971 int j = 0;
972
973 for (int i = minrowpr2; i <= maxrow; i++) {
974 rowcount = 0;
975 for (j = mincolpr2; j <= maxcol; j++) {
976 if (*cellptr == 1) rowcount++;
977 *ccptr = *prevptr + rowcount;
978 cellptr++;
979 ccptr++;
980 prevptr++;
981 }
982 cellptr += nextrow;
983 ccptr += nextrow;
984 prevptr += nextrow;
985 }
986
987 // restore given limits
988 minrow += range;
989 mincol += range;
990 maxrow -= range;
991 maxcol -= range;
992
993 // calculate final neighborhood counts using values in colcounts
994 // and update the corresponding cells in current grid
995
996 int* colptr = colcounts + (minrow + range) * outerwd;
997 ccptr = colptr + mincol + range;
998 unsigned char* stateptr = currgrid + minrow*outerwd+mincol;
999 unsigned char state = *stateptr;
1000 update_current_grid(state, *ccptr);
1001 *stateptr = state;
1002 if (state) {
1003 if (mincol < minx) minx = mincol;
1004 if (mincol > maxx) maxx = mincol;
1005 if (minrow < miny) miny = minrow;
1006 if (minrow > maxy) maxy = minrow;
1007 }
1008
1009 bool rowchanged = false;
1010 int rangep1 = range + 1;
1011 stateptr = currgrid + minrow*outerwd + mincol+1;
1012 for (j = mincol+1; j <= maxcol; j++) {
1013 // do i == minrow
1014 int* ccptr1 = colptr + (j+range);
1015 int* ccptr2 = colptr + (j-rangep1);
1016 state = *stateptr;
1017 update_current_grid(state, *ccptr1 - *ccptr2);
1018 *stateptr++ = state;
1019 if (state) {
1020 if (j < minx) minx = j;
1021 if (j > maxx) maxx = j;
1022 rowchanged = true;
1023 }
1024 }
1025 if (rowchanged) {
1026 if (minrow < miny) miny = minrow;
1027 if (minrow > maxy) maxy = minrow;
1028 }
1029
1030 bool colchanged = false;
1031 colptr = colcounts + mincol + range;
1032 stateptr = currgrid + (minrow+1)*outerwd + mincol;
1033 for (int i = minrow+1; i <= maxrow; i++) {
1034 // do j == mincol
1035 int* ccptr1 = colptr + (i+range) * outerwd;
1036 int* ccptr2 = colptr + (i-rangep1) * outerwd;
1037 state = *stateptr;
1038 update_current_grid(state, *ccptr1 - *ccptr2);
1039 *stateptr = state;
1040 stateptr += outerwd;
1041 if (state) {
1042 if (i < miny) miny = i;
1043 if (i > maxy) maxy = i;
1044 colchanged = true;
1045 }
1046 }
1047 if (colchanged) {
1048 if (mincol < minx) minx = mincol;
1049 if (mincol > maxx) maxx = mincol;
1050 }
1051
1052 rowchanged = false;
1053 for (int i = minrow+1; i <= maxrow; i++) {
1054 int* ipr = colcounts + (i+range) * outerwd;
1055 int* imrm1 = colcounts + (i-rangep1) * outerwd;
1056 stateptr = currgrid + i*outerwd + mincol+1;
1057 for (j = mincol+1; j <= maxcol; j++) {
1058 int jpr = j+range;
1059 int jmrm1 = j-rangep1;
1060 int* ccptr1 = ipr + jpr;
1061 int* ccptr2 = imrm1 + jmrm1;
1062 int* ccptr3 = ipr + jmrm1;
1063 int* ccptr4 = imrm1 + jpr;
1064 state = *stateptr;
1065 update_current_grid(state, *ccptr1 + *ccptr2 - *ccptr3 - *ccptr4);
1066 *stateptr++ = state;
1067 if (state) {
1068 if (j < minx) minx = j;
1069 if (j > maxx) maxx = j;
1070 rowchanged = true;
1071 }
1072 }
1073 if (rowchanged) {
1074 if (i < miny) miny = i;
1075 if (i > maxy) maxy = i;
1076 rowchanged = false;
1077 }
1078 }
1079 }
1080
1081 // -----------------------------------------------------------------------------
1082
faster_Moore_unbounded2(int mincol,int minrow,int maxcol,int maxrow)1083 void ltlalgo::faster_Moore_unbounded2(int mincol, int minrow, int maxcol, int maxrow)
1084 {
1085 // use Adam P. Goucher's algorithm to calculate Moore neighborhood counts
1086 // in an unbounded universe; note that we can safely assume there is at least
1087 // a 2*range border of dead cells surrounding the pattern
1088
1089 // temporarily expand the given limits
1090 minrow -= range;
1091 mincol -= range;
1092 maxrow += range;
1093 maxcol += range;
1094
1095 int r2 = range * 2;
1096 int minrowpr2 = minrow+r2;
1097 int mincolpr2 = mincol+r2;
1098
1099 // put zeros in top 2*range rows of colcounts
1100 for (int i = minrow; i < minrowpr2; i++) {
1101 int* ccptr = colcounts + i * outerwd + mincol;
1102 for (int j = mincol; j <= maxcol; j++) {
1103 *ccptr++ = 0;
1104 }
1105 }
1106
1107 // put zeros in left 2*range columns of colcounts
1108 for (int j = mincol; j < mincolpr2; j++) {
1109 int* ccptr = colcounts + minrowpr2 * outerwd + j;
1110 for (int i = minrowpr2; i <= maxrow; i++) {
1111 *ccptr = 0;
1112 ccptr += outerwd;
1113 }
1114 }
1115
1116 // calculate cumulative counts for each column and store in colcounts
1117
1118 unsigned char* cellptr = currgrid + minrowpr2 * outerwd + mincolpr2;
1119 int* ccptr = colcounts + minrowpr2 * outerwd + mincolpr2;
1120 int* prevptr = ccptr - outerwd;
1121 int width = (maxcol - mincolpr2 + 1);
1122 int nextrow = outerwd - width;
1123 int rowcount = 0;
1124
1125 // compute 4 cell offset
1126 int offset = (4 - ((g_uintptr_t)cellptr & 3)) & 3;
1127 if (offset > width) offset = width;
1128
1129 // process in 4 cell chunks
1130 int chunks = (width - offset) >> 2;
1131 int remainder = (width - offset) - (chunks << 2);
1132 int j = 0;
1133
1134 // process cells in the first row
1135
1136 // process cells up to the first 4 cell chunk
1137 for (j = 0; j < offset; j++) {
1138 rowcount += *cellptr++;
1139 *ccptr++ = rowcount;
1140 }
1141
1142 // process any 4 cell chunks
1143 unsigned int *lcellptr = (unsigned int*)cellptr;
1144 for (j = 0; j < chunks; j++) {
1145 if (*lcellptr++) {
1146 rowcount += *cellptr++;
1147 *ccptr++ = rowcount;
1148 rowcount += *cellptr++;
1149 *ccptr++ = rowcount;
1150 rowcount += *cellptr++;
1151 *ccptr++ = rowcount;
1152 rowcount += *cellptr++;
1153 *ccptr++ = rowcount;
1154 } else {
1155 *ccptr++ = rowcount;
1156 *ccptr++ = rowcount;
1157 *ccptr++ = rowcount;
1158 *ccptr++ = rowcount;
1159 cellptr += 4;
1160 }
1161 }
1162
1163 // process any remaining cells
1164 for (j = 0; j < remainder; j++) {
1165 rowcount += *cellptr++;
1166 *ccptr++ = rowcount;
1167 }
1168 cellptr += nextrow;
1169 ccptr += nextrow;
1170 prevptr = ccptr - outerwd;
1171
1172 // process the remaining rows of cells
1173
1174 for (int i = minrowpr2 + 1; i <= maxrow; i++) {
1175 rowcount = 0;
1176
1177 // compute 4 cell offset
1178 offset = (4 - ((g_uintptr_t)cellptr & 3)) & 3;
1179 if (offset > width) offset = width;
1180
1181 // process in 4 cell chunks
1182 chunks = (width - offset) >> 2;
1183 remainder = (width - offset) - (chunks << 2);
1184
1185 // process cells up to the first 4 cell chunk
1186 for (j = 0; j < offset; j++) {
1187 rowcount += *cellptr++;
1188 *ccptr++ = *prevptr++ + rowcount;
1189 }
1190 lcellptr = (unsigned int*)cellptr;
1191
1192 // process any 4 cell chunks
1193 for (j = 0; j < chunks; j++) {
1194 // check if any of the cells are alive
1195 if (*lcellptr++) {
1196 rowcount += *cellptr++;
1197 *ccptr++ = *prevptr++ + rowcount;
1198 rowcount += *cellptr++;
1199 *ccptr++ = *prevptr++ + rowcount;
1200 rowcount += *cellptr++;
1201 *ccptr++ = *prevptr++ + rowcount;
1202 rowcount += *cellptr++;
1203 *ccptr++ = *prevptr++ + rowcount;
1204 } else {
1205 *ccptr++ = *prevptr++ + rowcount;
1206 *ccptr++ = *prevptr++ + rowcount;
1207 *ccptr++ = *prevptr++ + rowcount;
1208 *ccptr++ = *prevptr++ + rowcount;
1209 cellptr += 4;
1210 }
1211 }
1212
1213 // process any remaining cells
1214 for (j = 0; j < remainder; j++) {
1215 rowcount += *cellptr++;
1216 *ccptr++ = *prevptr++ + rowcount;
1217 }
1218 // next row
1219 cellptr += nextrow;
1220 ccptr += nextrow;
1221 prevptr += nextrow;
1222 }
1223
1224 // restore given limits
1225 minrow += range;
1226 mincol += range;
1227 maxrow -= range;
1228 maxcol -= range;
1229
1230 // calculate final neighborhood counts using values in colcounts
1231 // and update the corresponding cells in current grid
1232
1233 int* colptr = colcounts + (minrow + range) * outerwd;
1234 ccptr = colptr + mincol + range;
1235 unsigned char* stateptr = currgrid + minrow*outerwd+mincol;
1236 int ncount = *ccptr;
1237 if (*stateptr == 0) {
1238 if (ncount >= minB && ncount <= maxB) {
1239 *stateptr = 1;
1240 population++;
1241 minx = mincol;
1242 maxx = mincol;
1243 miny = minrow;
1244 maxy = minrow;
1245 }
1246 } else {
1247 if (ncount < minS || ncount > maxS) {
1248 *stateptr = 0;
1249 population--;
1250 }
1251 else {
1252 minx = mincol;
1253 maxx = maxcol;
1254 miny = minrow;
1255 maxy = maxrow;
1256 }
1257 }
1258
1259 bool rowchanged = false;
1260 int rangep1 = range + 1;
1261 stateptr = currgrid + minrow*outerwd + mincol+1;
1262 int* ccptr1 = colptr + (mincol+1 + range);
1263 int* ccptr2 = colptr + (mincol+1 - rangep1);
1264 for (j = mincol+1; j <= maxcol; j++) {
1265 // do i == minrow
1266 ncount = *ccptr1++ - *ccptr2++;
1267 if (*stateptr == 0) {
1268 if (ncount >= minB && ncount <= maxB) {
1269 *stateptr = 1;
1270 population++;
1271 if (j < minx) minx = j;
1272 if (j > maxx) maxx = j;
1273 rowchanged = true;
1274 }
1275 } else {
1276 if (ncount < minS || ncount > maxS) {
1277 *stateptr = 0;
1278 population--;
1279 }
1280 else {
1281 if (j < minx) minx = j;
1282 if (j > maxx) maxx = j;
1283 rowchanged = true;
1284 }
1285 }
1286 stateptr++;
1287 }
1288 if (rowchanged) {
1289 if (minrow < miny) miny = minrow;
1290 if (minrow > maxy) maxy = minrow;
1291 }
1292
1293 bool colchanged = false;
1294 colptr = colcounts + mincol + range;
1295 stateptr = currgrid + (minrow+1)*outerwd + mincol;
1296 ccptr1 = colptr + (minrow+1+range) * outerwd;
1297 ccptr2 = colptr + (minrow+1-rangep1) * outerwd;
1298 for (int i = minrow+1; i <= maxrow; i++) {
1299 // do j == mincol
1300 ncount = *ccptr1 - *ccptr2;
1301 if (*stateptr == 0) {
1302 if (ncount >= minB && ncount <= maxB) {
1303 *stateptr = 1;
1304 population++;
1305 if (i < miny) miny = i;
1306 if (i > maxy) maxy = i;
1307 colchanged = true;
1308 }
1309 } else {
1310 if (ncount < minS || ncount > maxS) {
1311 *stateptr = 0;
1312 population--;
1313 }
1314 else {
1315 if (i < miny) miny = i;
1316 if (i > maxy) maxy = i;
1317 colchanged = true;
1318 }
1319 }
1320 stateptr += outerwd;
1321 ccptr1 += outerwd;
1322 ccptr2 += outerwd;
1323 }
1324 if (colchanged) {
1325 if (mincol < minx) minx = mincol;
1326 if (mincol > maxx) maxx = mincol;
1327 }
1328
1329 rowchanged = false;
1330 for (int i = minrow+1; i <= maxrow; i++) {
1331 int* ipr = colcounts + (i+range) * outerwd;
1332 int* imrm1 = colcounts + (i-rangep1) * outerwd;
1333 int jpr = mincol+1+range;
1334 int jmrm1 = mincol+1-rangep1;
1335 ccptr1 = ipr + jpr;
1336 ccptr2 = imrm1 + jmrm1;
1337 int* ccptr3 = ipr + jmrm1;
1338 int* ccptr4 = imrm1 + jpr;
1339 stateptr = currgrid + i*outerwd + mincol+1;
1340 for (j = mincol+1; j <= maxcol; j++) {
1341 ncount = *ccptr1++ + *ccptr2++ - *ccptr3++ - *ccptr4++;
1342 if (*stateptr == 0) {
1343 if (ncount >= minB && ncount <= maxB) {
1344 *stateptr = 1;
1345 population++;
1346 if (j < minx) minx = j;
1347 if (j > maxx) maxx = j;
1348 rowchanged = true;
1349 }
1350 } else {
1351 if (ncount < minS || ncount > maxS) {
1352 *stateptr = 0;
1353 population--;
1354 }
1355 else {
1356 if (j < minx) minx = j;
1357 if (j > maxx) maxx = j;
1358 rowchanged = true;
1359 }
1360 }
1361 stateptr++;
1362 }
1363 if (rowchanged) {
1364 if (i < miny) miny = i;
1365 if (i > maxy) maxy = i;
1366 rowchanged = false;
1367 }
1368 }
1369 if (population == 0) empty_boundaries();
1370 }
1371
1372 // -----------------------------------------------------------------------------
1373
fast_Moore(int mincol,int minrow,int maxcol,int maxrow)1374 void ltlalgo::fast_Moore(int mincol, int minrow, int maxcol, int maxrow)
1375 {
1376 if (range == 1) {
1377 for (int y = minrow; y <= maxrow; y++) {
1378 int yoffset = y * outerwd;
1379 unsigned char* topy = currgrid + (y - 1) * outerwd;
1380 for (int x = mincol; x <= maxcol; x++) {
1381 // count the state-1 neighbors within the current range
1382 // using the extended Moore neighborhood with no edge checks
1383 int ncount = 0;
1384 unsigned char* cellptr = topy + (x - 1);
1385 if (*cellptr++ == 1) ncount++;
1386 if (*cellptr++ == 1) ncount++;
1387 if (*cellptr == 1) ncount++;
1388 cellptr += outerwd;
1389 if (*cellptr == 1) ncount++;
1390 if (*--cellptr == 1) ncount++;
1391 if (*--cellptr == 1) ncount++;
1392 cellptr += outerwd;
1393 if (*cellptr++ == 1) ncount++;
1394 if (*cellptr++ == 1) ncount++;
1395 if (*cellptr == 1) ncount++;
1396 update_next_grid(x, y, yoffset+x, ncount);
1397 }
1398 }
1399 } else {
1400 // range > 1
1401 int rightcol = 2 * range;
1402 for (int y = minrow; y <= maxrow; y++) {
1403 int yoffset = y * outerwd;
1404 int ymrange = y - range;
1405 int yprange = y + range;
1406 unsigned char* topy = currgrid + ymrange * outerwd;
1407
1408 // for the 1st cell in this row we count the state-1 cells in the
1409 // extended Moore neighborhood and remember the column counts
1410 int colcount[MAXNCOLS];
1411 int xmrange = mincol - range;
1412 int xprange = mincol + range;
1413 int ncount = 0;
1414 for (int i = xmrange; i <= xprange; i++) {
1415 unsigned char* cellptr = topy + i;
1416 int col = i - xmrange;
1417 colcount[col] = 0;
1418 for (int j = ymrange; j <= yprange; j++) {
1419 if (*cellptr == 1) colcount[col]++;
1420 cellptr += outerwd;
1421 }
1422 ncount += colcount[col];
1423 }
1424
1425 // we now have the neighborhood counts in each column;
1426 // eg. 7 columns if range == 3:
1427 // ---------------
1428 // | | | | | | | |
1429 // | | | | | | | |
1430 // |0|1|2|3|4|5|6|
1431 // | | | | | | | |
1432 // | | | | | | | |
1433 // ---------------
1434
1435 update_next_grid(mincol, y, yoffset+mincol, ncount);
1436
1437 // for the remaining cells in this row we only need to update
1438 // the count in the right column of the new neighborhood
1439 // and shift the other column counts to the left
1440 topy += range;
1441 for (int x = mincol+1; x <= maxcol; x++) {
1442 // get count in right column
1443 int rcount = 0;
1444 unsigned char* cellptr = topy + x;
1445 for (int j = ymrange; j <= yprange; j++) {
1446 if (*cellptr == 1) rcount++;
1447 cellptr += outerwd;
1448 }
1449
1450 ncount = rcount;
1451 for (int i = 1; i <= rightcol; i++) {
1452 ncount += colcount[i];
1453 colcount[i-1] = colcount[i];
1454 }
1455 colcount[rightcol] = rcount;
1456
1457 update_next_grid(x, y, yoffset+x, ncount);
1458 }
1459 }
1460
1461 }
1462 }
1463
1464 // -----------------------------------------------------------------------------
1465
fast_Shaped(int mincol,int minrow,int maxcol,int maxrow)1466 void ltlalgo::fast_Shaped(int mincol, int minrow, int maxcol, int maxrow)
1467 {
1468 for (int y = minrow; y <= maxrow; y++) {
1469 int yoffset = y * outerwd;
1470 int ymrange = y - range;
1471 int yprange = y + range;
1472
1473 // for the 1st cell in this row we count the state-1 cells in the
1474 // shaped neighborhood and remember the column counts
1475 int ncount = 0;
1476 unsigned char* cellptr = currgrid + ymrange * outerwd ;
1477 for (int j = ymrange; j <= yprange; j++, cellptr += outerwd) {
1478 int xmrange = mincol - shape[j-ymrange] ;
1479 int xprange = mincol + shape[j-ymrange] ;
1480 for (int i = xmrange; i <= xprange; i++)
1481 if (cellptr[i] == 1) ncount++ ;
1482 }
1483
1484 update_next_grid(mincol, y, yoffset+mincol, ncount);
1485
1486 // for the remaining cells in this row we only need subtract
1487 // points in relevant rows and add points in other relevant
1488 // rows according to the shape.
1489 cellptr = currgrid + ymrange * outerwd ;
1490 for (int x = mincol+1; x <= maxcol; x++) {
1491 unsigned char* cp = cellptr ;
1492 for (int j = ymrange; j <= yprange; j++, cp += outerwd) {
1493 int xmrange = x - shape[j-ymrange] ;
1494 int xprange = x + shape[j-ymrange] ;
1495 if (cp[xmrange-1] == 1)
1496 ncount-- ;
1497 if (cp[xprange] == 1)
1498 ncount++ ;
1499 }
1500 update_next_grid(x, y, yoffset+x, ncount);
1501 }
1502 }
1503 }
1504
1505 // -----------------------------------------------------------------------------
1506
getcount(int i,int j)1507 int ltlalgo::getcount(int i, int j)
1508 {
1509 // From Dean Hickerson:
1510 // C[i][j] is the sum of G[i'][j'] for all cells between northwest and northeast from
1511 // (i,j) with i'+j' == i+j (mod 2). I.e. the sum of these:
1512 //
1513 // ... ... ...
1514 // G[i-3][j-3] G[i-3][j-1] G[i-3][j+1] G[i-3][j+3]
1515 // G[i-2][j-2] G[i-2][j] G[i-2][j+2]
1516 // G[i-1][j-1] G[i-1][j+1]
1517 // G[i][j]
1518 //
1519 // We only need to compute and store C[i][j] for 0 <= i < ncols, 0 <= j < nrows + floor((ncols-1)/2);
1520 // other values that we need are equal to one of these, as given by this function.
1521 //
1522 if (i < 0 || i+j < 0 || j-i >= ncols) {
1523 return 0;
1524 }
1525 if (j < 0 && i+j < ccht) {
1526 // return C[i+j][0]
1527 return *(colcounts + (i+j) * outerwd);
1528 }
1529 if (j >= ncols && j-i >= ncols-ccht) {
1530 // return C[i+ncols-1-j][ncols-1]
1531 return *(colcounts + (i+ncols-1-j) * outerwd + (ncols-1));
1532 }
1533 if (i < ccht) {
1534 // return C[i][j]
1535 return *(colcounts + i * outerwd + j);
1536 }
1537 if ((i-ccht+1)+j <= halfccwd) {
1538 // return C[ccht-1][i-ccht+1+j]
1539 return *(colcounts + (ccht-1) * outerwd + (i-ccht+1+j));
1540 }
1541 if (j-(i-ccht+1) >= halfccwd) {
1542 // return C[ccht-1][j-(i-ccht+1)]
1543 return *(colcounts + (ccht-1) * outerwd + (j-(i-ccht+1)));
1544 }
1545 // return C[ccht-1][halfccwd + ((i+j+ccht+halfccwd+1) % 2)]
1546 return *(colcounts + (ccht-1) * outerwd + (halfccwd + ((i+j+ccht+halfccwd+1) % 2)));
1547 }
1548
1549 // -----------------------------------------------------------------------------
1550
faster_Neumann_bounded(int mincol,int minrow,int maxcol,int maxrow)1551 void ltlalgo::faster_Neumann_bounded(int mincol, int minrow, int maxcol, int maxrow)
1552 {
1553 // use Dean Hickerson's algorithm (based on Adam P. Goucher's algorithm for the
1554 // Moore neighborhood) to calculate extended von Neumann neighborhood counts
1555 // in a bounded universe; note that currgrid is surrounded by a border that
1556 // might contain live cells (the border is range+1 cells thick and the
1557 // outermost cells are always dead)
1558
1559 // the given limits are relative to currgrid so we need to add border
1560 // so they are relative to outergrid1, and then expand them by range
1561 int bmr = border - range;
1562 int bpr = border + range;
1563 minrow += bmr;
1564 mincol += bmr;
1565 maxrow += bpr;
1566 maxcol += bpr;
1567
1568 // set variables used below and in getcount
1569 nrows = maxrow - minrow + 1;
1570 ncols = maxcol - mincol + 1;
1571 ccht = nrows + (ncols-1)/2;
1572 halfccwd = ncols/2;
1573
1574 // calculate cumulative counts in top left corner of colcounts
1575 for (int i = 0; i < ccht; i++) {
1576 int* Coffset = colcounts + i * outerwd;
1577 unsigned char* Goffset = outergrid1 + (i + minrow) * outerwd;
1578 int im1 = i - 1;
1579 int im2 = im1 - 1;
1580 for (int j = 0; j < ncols; j++) {
1581 int* Cij = Coffset + j;
1582 *Cij = getcount(im1,j-1) + getcount(im1,j+1) - getcount(im2,j);
1583 if (i < nrows) {
1584 unsigned char* Gij = Goffset + j + mincol;
1585 if (*Gij == 1) *Cij += *Gij;
1586 }
1587 }
1588 }
1589
1590 // set minrow and mincol for update_current_grid calls
1591 minrow -= border;
1592 mincol -= border;
1593
1594 // calculate final neighborhood counts and update the corresponding cells in the grid
1595 bool rowchanged = false;
1596 for (int i = range; i < nrows-range; i++) {
1597 int im1 = i - 1;
1598 int ipr = i + range;
1599 int iprm1 = ipr - 1;
1600 int imrm1 = i - range - 1;
1601 int imrm2 = imrm1 - 1;
1602 int ipminrow = i + minrow;
1603 unsigned char* stateptr = currgrid + ipminrow*outerwd + range + mincol;
1604 for (int j = range; j < ncols-range; j++) {
1605 int jpr = j + range;
1606 int jmr = j - range;
1607 int n = getcount(ipr,j) - getcount(im1,jpr+1) - getcount(im1,jmr-1) + getcount(imrm2,j) +
1608 getcount(iprm1,j) - getcount(im1,jpr) - getcount(im1,jmr) + getcount(imrm1,j);
1609 unsigned char state = *stateptr;
1610 update_current_grid(state, n);
1611 *stateptr++ = state;
1612 if (state) {
1613 int jpmincol = j + mincol;
1614 if (jpmincol < minx) minx = jpmincol;
1615 if (jpmincol > maxx) maxx = jpmincol;
1616 rowchanged = true;
1617 }
1618 }
1619 if (rowchanged) {
1620 if (ipminrow < miny) miny = ipminrow;
1621 if (ipminrow > maxy) maxy = ipminrow;
1622 rowchanged = false;
1623 }
1624 }
1625 }
1626
1627 // -----------------------------------------------------------------------------
1628
faster_Neumann_unbounded(int mincol,int minrow,int maxcol,int maxrow)1629 void ltlalgo::faster_Neumann_unbounded(int mincol, int minrow, int maxcol, int maxrow)
1630 {
1631 // use Dean Hickerson's algorithm (based on Adam P. Goucher's algorithm for the
1632 // Moore neighborhood) to calculate extended von Neumann neighborhood counts
1633 // in an unbounded universe; note that we can safely assume there is at least
1634 // a 2*range border of dead cells surrounding the pattern
1635
1636 // set variables used below and in getcount
1637 nrows = maxrow - minrow + 1;
1638 ncols = maxcol - mincol + 1;
1639 ccht = nrows + (ncols-1)/2;
1640 halfccwd = ncols/2;
1641
1642 // calculate cumulative counts in top left corner of colcounts
1643 for (int i = 0; i < ccht; i++) {
1644 int* Coffset = colcounts + i * outerwd;
1645 unsigned char* Goffset = outergrid1 + (i + minrow) * outerwd;
1646 int im1 = i - 1;
1647 int im2 = im1 - 1;
1648 for (int j = 0; j < ncols; j++) {
1649 int* Cij = Coffset + j;
1650 *Cij = getcount(im1,j-1) + getcount(im1,j+1) - getcount(im2,j);
1651 if (i < nrows) {
1652 unsigned char* Gij = Goffset + j + mincol;
1653 if (*Gij == 1) *Cij += *Gij;
1654 }
1655 }
1656 }
1657
1658 // calculate final neighborhood counts and update the corresponding cells in the grid
1659 bool rowchanged = false;
1660 for (int i = 0; i < nrows; i++) {
1661 int im1 = i - 1;
1662 int ipr = i + range;
1663 int iprm1 = ipr - 1;
1664 int imrm1 = i - range - 1;
1665 int imrm2 = imrm1 - 1;
1666 int ipminrow = i + minrow;
1667 unsigned char* stateptr = currgrid + ipminrow*outerwd + mincol;
1668 for (int j = 0; j < ncols; j++) {
1669 int jpr = j + range;
1670 int jmr = j - range;
1671 int n = getcount(ipr,j) - getcount(im1,jpr+1) - getcount(im1,jmr-1) + getcount(imrm2,j) +
1672 getcount(iprm1,j) - getcount(im1,jpr) - getcount(im1,jmr) + getcount(imrm1,j);
1673 unsigned char state = *stateptr;
1674 update_current_grid(state, n);
1675 *stateptr++ = state;
1676 if (state) {
1677 int jpmincol = j + mincol;
1678 if (jpmincol < minx) minx = jpmincol;
1679 if (jpmincol > maxx) maxx = jpmincol;
1680 rowchanged = true;
1681 }
1682 }
1683 if (rowchanged) {
1684 if (ipminrow < miny) miny = ipminrow;
1685 if (ipminrow > maxy) maxy = ipminrow;
1686 rowchanged = false;
1687 }
1688 }
1689 }
1690
1691 // -----------------------------------------------------------------------------
1692
fast_Neumann(int mincol,int minrow,int maxcol,int maxrow)1693 void ltlalgo::fast_Neumann(int mincol, int minrow, int maxcol, int maxrow)
1694 {
1695 if (range == 1) {
1696 int outerwd2 = outerwd * 2;
1697 for (int y = minrow; y <= maxrow; y++) {
1698 int yoffset = y * outerwd;
1699 unsigned char* topy = currgrid + yoffset;
1700 for (int x = mincol; x <= maxcol; x++) {
1701 // count the state-1 neighbors within the current range
1702 // using the extended von Neumann neighborhood with no edge checks
1703 // (at range 1 a diamond is a cross: +)
1704 int ncount = 0;
1705 unsigned char* cellptr = topy + (x - 1);
1706 if (*cellptr++ == 1) ncount++;
1707 if (*cellptr++ == 1) ncount++;
1708 if (*cellptr == 1) ncount++;
1709 cellptr -= outerwd;
1710 if (*--cellptr == 1) ncount++;
1711 cellptr += outerwd2;
1712 if (*cellptr == 1) ncount++;
1713 update_next_grid(x, y, yoffset+x, ncount);
1714 }
1715 }
1716 } else {
1717 // range > 1
1718 for (int y = minrow; y <= maxrow; y++) {
1719 int yoffset = y * outerwd;
1720 int ymrange = y - range;
1721 int yprange = y + range;
1722 unsigned char* topy = currgrid + ymrange * outerwd;
1723 for (int x = mincol; x <= maxcol; x++) {
1724 // count the state-1 neighbors within the current range
1725 // using the extended von Neumann neighborhood (diamond) with no edge checks
1726 int ncount = 0;
1727 int xoffset = 0;
1728 unsigned char* rowptr = topy;
1729 for (int j = ymrange; j < y; j++) {
1730 unsigned char* cellptr = rowptr + (x - xoffset);
1731 int len = 2 * xoffset + 1;
1732 for (int i = 0; i < len; i++) {
1733 if (*cellptr++ == 1) ncount++;
1734 }
1735 xoffset++; // 0, 1, 2, ..., range
1736 rowptr += outerwd;
1737 }
1738 // xoffset == range
1739 for (int j = y; j <= yprange; j++) {
1740 unsigned char* cellptr = rowptr + (x - xoffset);
1741 int len = 2 * xoffset + 1;
1742 for (int i = 0; i < len; i++) {
1743 if (*cellptr++ == 1) ncount++;
1744 }
1745 xoffset--; // range-1, ..., 2, 1, 0
1746 rowptr += outerwd;
1747 }
1748 update_next_grid(x, y, yoffset+x, ncount);
1749 }
1750 }
1751 }
1752 }
1753
1754 // -----------------------------------------------------------------------------
1755
do_bounded_gen()1756 void ltlalgo::do_bounded_gen()
1757 {
1758 // limit processing to rectangle where births/deaths can occur
1759 int mincol, minrow, maxcol, maxrow;
1760 bool torus = topology == 'T';
1761 if (minB == 0) {
1762 // birth in every dead cell so process entire grid
1763 mincol = 0;
1764 minrow = 0;
1765 maxcol = gwdm1;
1766 maxrow = ghtm1;
1767 } else {
1768 mincol = minx - range;
1769 minrow = miny - range;
1770 maxcol = maxx + range;
1771 maxrow = maxy + range;
1772
1773 // check if the limits are outside the grid edges
1774 if (mincol < 0) {
1775 mincol = 0;
1776 if (torus) maxcol = gwdm1;
1777 }
1778 if (maxcol > gwdm1) {
1779 maxcol = gwdm1;
1780 if (torus) mincol = 0;
1781 }
1782 if (minrow < 0) {
1783 minrow = 0;
1784 if (torus) maxrow = ghtm1;
1785 }
1786 if (maxrow > ghtm1) {
1787 maxrow = ghtm1;
1788 if (torus) minrow = 0;
1789 }
1790 }
1791
1792 // save pattern limits for clearing border cells at end
1793 int sminx = minx;
1794 int smaxx = maxx;
1795 int sminy = miny;
1796 int smaxy = maxy;
1797
1798 if (torus) {
1799 // If a pattern edge is within range of a grid edge then copy cells
1800 // into appropriate border cells next to the opposite grid edge,
1801 // as illustrated in this example of a grid with range 1 (so border = 2).
1802 // The live cells at "a" will be copied to the "A" locations and the
1803 // live cell at corner "b" will be copied to the three "B" locations:
1804 //
1805 // <-------------- outerwd -------------->
1806 // o-------------------------------------- ^ o = outergrid1
1807 // | | |
1808 // | <------------- gwd -------------> | |
1809 // | c-------------------------------- | | c = currgrid
1810 // | B| aa ^ b| | |
1811 // | | | | | |
1812 // | | ght | |outerht
1813 // | | | | | |
1814 // | | v | | |
1815 // | --------------------------------- | |
1816 // | B AA B | |
1817 // | | |
1818 // --------------------------------------- v
1819 //
1820 if (miny < range) {
1821 // copy cells near top edge of currgrid to bottom border
1822 int numrows = range - miny;
1823 int numcols = maxx - minx + 1;
1824 unsigned char* src = currgrid + miny * outerwd + minx;
1825 unsigned char* dest = src + ght * outerwd;
1826 for (int row = 0; row < numrows; row++) {
1827 memcpy(dest, src, numcols);
1828 src += outerwd;
1829 dest += outerwd;
1830 }
1831 if (minx < range) {
1832 // copy cells near top left corner of currgrid to bottom right border
1833 numcols = range - minx;
1834 src = currgrid + miny * outerwd + minx;
1835 dest = src + ght * outerwd + gwd;
1836 for (int row = 0; row < numrows; row++) {
1837 memcpy(dest, src, numcols);
1838 src += outerwd;
1839 dest += outerwd;
1840 }
1841 }
1842 }
1843 if (maxy + range > ghtm1) {
1844 // copy cells near bottom edge of currgrid to top border
1845 int numrows = maxy + range - ghtm1;
1846 int numcols = maxx - minx + 1;
1847 unsigned char* src = currgrid + (ght - range) * outerwd + minx;
1848 unsigned char* dest = src - ght * outerwd;
1849 for (int row = 0; row < numrows; row++) {
1850 memcpy(dest, src, numcols);
1851 src += outerwd;
1852 dest += outerwd;
1853 }
1854 if (maxx + range > gwdm1) {
1855 // copy cells near bottom right corner of currgrid to top left border
1856 numcols = maxx + range - gwdm1;
1857 src = currgrid + (ght - range) * outerwd + gwd - range;
1858 dest = src - ght * outerwd - gwd;
1859 for (int row = 0; row < numrows; row++) {
1860 memcpy(dest, src, numcols);
1861 src += outerwd;
1862 dest += outerwd;
1863 }
1864 }
1865 }
1866 if (minx < range) {
1867 // copy cells near left edge of currgrid to right border
1868 int numrows = maxy - miny + 1;
1869 int numcols = range - minx;
1870 unsigned char* src = currgrid + miny * outerwd + minx;
1871 unsigned char* dest = src + gwd;
1872 for (int row = 0; row < numrows; row++) {
1873 memcpy(dest, src, numcols);
1874 src += outerwd;
1875 dest += outerwd;
1876 }
1877 if (maxy + range > ghtm1) {
1878 // copy cells near bottom left corner of currgrid to top right border
1879 numrows = maxy + range - ghtm1;
1880 src = currgrid + (ght - range) * outerwd + minx;
1881 dest = src - ght * outerwd + gwd;
1882 for (int row = 0; row < numrows; row++) {
1883 memcpy(dest, src, numcols);
1884 src += outerwd;
1885 dest += outerwd;
1886 }
1887 }
1888 }
1889 if (maxx + range > gwdm1) {
1890 // copy cells near right edge of currgrid to left border
1891 int numrows = maxy - miny + 1;
1892 int numcols = maxx + range - gwdm1;
1893 unsigned char* src = currgrid + miny * outerwd + gwd - range;
1894 unsigned char* dest = src - gwd;
1895 for (int row = 0; row < numrows; row++) {
1896 memcpy(dest, src, numcols);
1897 src += outerwd;
1898 dest += outerwd;
1899 }
1900 if (miny < range) {
1901 // copy cells near top right corner of currgrid to bottom left border
1902 numrows = range - miny;
1903 src = currgrid + miny * outerwd + gwd - range;
1904 dest = src + ght * outerwd - gwd;
1905 for (int row = 0; row < numrows; row++) {
1906 memcpy(dest, src, numcols);
1907 src += outerwd;
1908 dest += outerwd;
1909 }
1910 }
1911 }
1912 }
1913
1914 // reset minx,miny,maxx,maxy for first birth or survivor in nextgrid
1915 empty_boundaries();
1916
1917 // create next generation
1918 if (ntype == 'M') {
1919 if (colcounts) {
1920 if (maxCellStates == 2) {
1921 faster_Moore_bounded2(mincol, minrow, maxcol, maxrow);
1922 } else {
1923 faster_Moore_bounded(mincol, minrow, maxcol, maxrow);
1924 }
1925 } else {
1926 fast_Moore(mincol, minrow, maxcol, maxrow);
1927 }
1928 } else if (ntype == 'N') {
1929 if (colcounts) {
1930 faster_Neumann_bounded(mincol, minrow, maxcol, maxrow);
1931 } else {
1932 fast_Neumann(mincol, minrow, maxcol, maxrow);
1933 }
1934 } else {
1935 fast_Shaped(mincol, minrow, maxcol, maxrow);
1936 }
1937
1938 // if using one grid with a torus then clear border cells copied above
1939 if (colcounts && torus) {
1940 if (sminy < range) {
1941 // clear cells in bottom border
1942 int numrows = range - sminy;
1943 int numcols = smaxx - sminx + 1;
1944 unsigned char* src = currgrid + sminy * outerwd + sminx;
1945 unsigned char* dest = src + ght * outerwd;
1946 for (int row = 0; row < numrows; row++) {
1947 memset(dest, 0, numcols);
1948 dest += outerwd;
1949 }
1950 if (sminx < range) {
1951 // clear cells in bottom right border
1952 numcols = range - sminx;
1953 src = currgrid + sminy * outerwd + sminx;
1954 dest = src + ght * outerwd + gwd;
1955 for (int row = 0; row < numrows; row++) {
1956 memset(dest, 0, numcols);
1957 dest += outerwd;
1958 }
1959 }
1960 }
1961 if (smaxy + range > ghtm1) {
1962 // clear cells in top border
1963 int numrows = smaxy + range - ghtm1;
1964 int numcols = smaxx - sminx + 1;
1965 unsigned char* src = currgrid + (ght - range) * outerwd + sminx;
1966 unsigned char* dest = src - ght * outerwd;
1967 for (int row = 0; row < numrows; row++) {
1968 memset(dest, 0, numcols);
1969 dest += outerwd;
1970 }
1971 if (smaxx + range > gwdm1) {
1972 // clear cells in top left border
1973 numcols = smaxx + range - gwdm1;
1974 src = currgrid + (ght - range) * outerwd + gwd - range;
1975 dest = src - ght * outerwd - gwd;
1976 for (int row = 0; row < numrows; row++) {
1977 memset(dest, 0, numcols);
1978 dest += outerwd;
1979 }
1980 }
1981 }
1982 if (sminx < range) {
1983 // clear cells in right border
1984 int numrows = smaxy - sminy + 1;
1985 int numcols = range - sminx;
1986 unsigned char* src = currgrid + sminy * outerwd + sminx;
1987 unsigned char* dest = src + gwd;
1988 for (int row = 0; row < numrows; row++) {
1989 memset(dest, 0, numcols);
1990 dest += outerwd;
1991 }
1992 if (smaxy + range > ghtm1) {
1993 // clear cells in top right border
1994 numrows = smaxy + range - ghtm1;
1995 src = currgrid + (ght - range) * outerwd + sminx;
1996 dest = src - ght * outerwd + gwd;
1997 for (int row = 0; row < numrows; row++) {
1998 memset(dest, 0, numcols);
1999 dest += outerwd;
2000 }
2001 }
2002 }
2003 if (smaxx + range > gwdm1) {
2004 // clear cells in left border
2005 int numrows = smaxy - sminy + 1;
2006 int numcols = smaxx + range - gwdm1;
2007 unsigned char* src = currgrid + sminy * outerwd + gwd - range;
2008 unsigned char* dest = src - gwd;
2009 for (int row = 0; row < numrows; row++) {
2010 memset(dest, 0, numcols);
2011 dest += outerwd;
2012 }
2013 if (sminy < range) {
2014 // clear cells in bottom left border
2015 numrows = range - sminy;
2016 src = currgrid + sminy * outerwd + gwd - range;
2017 dest = src + ght * outerwd - gwd;
2018 for (int row = 0; row < numrows; row++) {
2019 memset(dest, 0, numcols);
2020 dest += outerwd;
2021 }
2022 }
2023 }
2024 }
2025 }
2026
2027 // -----------------------------------------------------------------------------
2028
do_unbounded_gen()2029 bool ltlalgo::do_unbounded_gen()
2030 {
2031 int mincol = minx - range;
2032 int minrow = miny - range;
2033 int maxcol = maxx + range;
2034 int maxrow = maxy + range;
2035
2036 if (mincol < range || maxcol > gwdm1-range || minrow < range || maxrow > ghtm1-range) {
2037 // pattern boundary is too close to a grid edge so expand the universe in that
2038 // direction, and possibly shrink the universe in the opposite direction
2039 int inc = MAXRANGE * 2;
2040 int up = minrow < range ? inc : 0;
2041 int down = maxrow > ghtm1-range ? inc : 0;
2042 int left = mincol < range ? inc : 0;
2043 int right = maxcol > gwdm1-range ? inc : 0;
2044
2045 // check for possible shrinkage (pattern might be a spaceship)
2046 if (up > 0 && down == 0 && maxrow < ghtm1-range) down = -(ghtm1-maxrow-range);
2047 if (down > 0 && up == 0 && minrow > range) up = -(minrow-range);
2048 if (left > 0 && right == 0 && maxcol < gwdm1-range) right = -(gwdm1-maxcol-range);
2049 if (right > 0 && left == 0 && mincol > range) left = -(mincol-range);
2050
2051 const char* errmsg = resize_grids(up, down, left, right);
2052 if (errmsg) {
2053 lifewarning(errmsg); // no need to check show_warning here
2054 return false; // stop generating
2055 }
2056
2057 mincol = minx - range;
2058 minrow = miny - range;
2059 maxcol = maxx + range;
2060 maxrow = maxy + range;
2061 }
2062
2063 // reset minx,miny,maxx,maxy for first birth or survivor in nextgrid
2064 empty_boundaries();
2065
2066 if (ntype == 'M') {
2067 if (colcounts) {
2068 if (maxCellStates == 2) {
2069 faster_Moore_unbounded2(mincol, minrow, maxcol, maxrow);
2070 } else {
2071 faster_Moore_unbounded(mincol, minrow, maxcol, maxrow);
2072 }
2073 } else {
2074 fast_Moore(mincol, minrow, maxcol, maxrow);
2075 }
2076 } else if (ntype == 'N') {
2077 if (colcounts) {
2078 faster_Neumann_unbounded(mincol, minrow, maxcol, maxrow);
2079 } else {
2080 fast_Neumann(mincol, minrow, maxcol, maxrow);
2081 }
2082 } else {
2083 fast_Shaped(mincol, minrow, maxcol, maxrow);
2084 }
2085 return true;
2086 }
2087
2088 // -----------------------------------------------------------------------------
2089
2090 // Do increment generations.
2091
step()2092 void ltlalgo::step()
2093 {
2094 bigint t = increment;
2095 while (t != 0) {
2096 if (population > 0 || minB == 0) {
2097 int prevpop = population;
2098
2099 // calculate the next generation in nextgrid
2100 if (unbounded) {
2101 if (!do_unbounded_gen()) {
2102 // failed to resize universe so stop generating
2103 poller->setInterrupted();
2104 return;
2105 }
2106 } else {
2107 do_bounded_gen();
2108 }
2109
2110 // swap outergrid1 and outergrid2 if using fast_* algo
2111 if (outergrid2) {
2112 unsigned char* temp = outergrid1;
2113 outergrid1 = outergrid2;
2114 outergrid2 = temp;
2115
2116 // swap currgrid and nextgrid
2117 temp = currgrid;
2118 currgrid = nextgrid;
2119 nextgrid = temp;
2120
2121 // kill all cells in outergrid2
2122 if (prevpop > 0) memset(outergrid2, 0, outerbytes);
2123 }
2124 }
2125
2126 generation += bigint::one;
2127
2128 // this is a safe place to check for user events
2129 if (poller->inner_poll()) return;
2130
2131 t -= 1;
2132 // user might have changed increment
2133 if (t > increment) t = increment;
2134 }
2135 }
2136
2137 // -----------------------------------------------------------------------------
2138
save_cells()2139 void ltlalgo::save_cells()
2140 {
2141 for (int y = miny; y <= maxy; y++) {
2142 int yoffset = y * outerwd;
2143 for (int x = minx; x <= maxx; x++) {
2144 unsigned char* currcell = currgrid + yoffset + x;
2145 if (*currcell) {
2146 cell_list.push_back(x + gleft);
2147 cell_list.push_back(y + gtop);
2148 cell_list.push_back(*currcell);
2149 }
2150 }
2151 }
2152 }
2153
2154 // -----------------------------------------------------------------------------
2155
restore_cells()2156 void ltlalgo::restore_cells()
2157 {
2158 clipped_cells.clear();
2159 for (size_t i = 0; i < cell_list.size(); i += 3) {
2160 int x = cell_list[i];
2161 int y = cell_list[i+1];
2162 int s = cell_list[i+2];
2163 // check if x,y is outside grid
2164 if (x < gleft || x > gright || y < gtop || y > gbottom) {
2165 // store clipped cells so that GUI code (eg. ClearOutsideGrid)
2166 // can remember them in case this rule change is undone
2167 clipped_cells.push_back(x);
2168 clipped_cells.push_back(y);
2169 clipped_cells.push_back(s);
2170 } else {
2171 setcell(x, y, s);
2172 }
2173 }
2174 cell_list.clear();
2175 }
2176
2177 // -----------------------------------------------------------------------------
2178
2179 // Switch to the given rule if it is valid.
2180
setrule(const char * s)2181 const char *ltlalgo::setrule(const char *s)
2182 {
2183 int r, c, m, s1, s2, b1, b2, endpos;
2184 char n;
2185 if (sscanf(s, "R%d,C%d,M%d,S%d..%d,B%d..%d,N%c%n",
2186 &r, &c, &m, &s1, &s2, &b1, &b2, &n, &endpos) != 8) {
2187 // try alternate LtL syntax as defined by Kellie Evans;
2188 // eg: 5,34,45,34,58 is equivalent to R5,C0,M1,S34..58,B34..45,NM
2189 if (sscanf(s, "%d,%d,%d,%d,%d%n",
2190 &r, &b1, &b2, &s1, &s2, &endpos) == 5) {
2191 c = 0;
2192 m = 1;
2193 n = 'M';
2194 } else {
2195 return "bad syntax in Larger than Life rule";
2196 }
2197 }
2198
2199 if (r < 1) return "R value is too small";
2200 int r2 = r*r+r ;
2201 if (r > MAXRANGE) return "R value is too big";
2202 if (c < 0 || c > 256) return "C value must be from 0 to 256";
2203 if (m < 0 || m > 1) return "M value must be 0 or 1";
2204 if (s1 > s2) return "S minimum must be <= S maximum";
2205 if (b1 > b2) return "B minimum must be <= B maximum";
2206 if (n != 'M' && n != 'N' && n != 'C') return "N must be followed by M or N or C";
2207 int maxn = n == 'M' ? (2*r+1)*(2*r+1) : 2*r*(r+1)+1;
2208 int tshape[2*MAXRANGE+1] ;
2209 if (n == 'C') {
2210 int cnt = 0 ;
2211 for (int i=-r; i<=r; i++) {
2212 int w = 0 ;
2213 while ((w + 1) * (w + 1) + (i * i) <= r2)
2214 w++ ;
2215 tshape[i+r] = w ;
2216 cnt += 2 * w + 1 ;
2217 }
2218 maxn = cnt ;
2219 }
2220 maxn -= (1 - m); // adjust max neighbors by middle cell setting
2221 if (s1 < 0 || s1 > maxn || s2 < 0 || s2 > maxn) return "S value must be from 0 to max neighbors";
2222 if (b1 < 0 || b1 > maxn || b2 < 0 || b2 > maxn) return "B value must be from 0 to max neighbors";
2223 if (s[endpos] != 0 && s[endpos] != ':') return "bad suffix";
2224
2225 char t = 'T';
2226 int newwd = DEFAULTSIZE;
2227 int newht = DEFAULTSIZE;
2228
2229 // check for explicit suffix like ":T200,100"
2230 const char *suffix = strchr(s, ':');
2231 if (suffix && suffix[1] != 0) {
2232 if (suffix[1] == 'T' || suffix[1] == 't') {
2233 t = 'T';
2234 } else if (suffix[1] == 'P' || suffix[1] == 'p') {
2235 t = 'P';
2236 } else {
2237 return "bad topology in suffix (must be torus or plane)";
2238 }
2239 if (suffix[2] != 0) {
2240 bool oneval = false;
2241 if (sscanf(suffix+2, "%d,%d%n", &newwd, &newht, &endpos) != 2) {
2242 if (sscanf(suffix+2, "%d%n", &newwd, &endpos) != 1) {
2243 return "bad grid size";
2244 } else {
2245 newht = newwd;
2246 oneval = true;
2247 if (suffix[endpos+2] != 0) {
2248 if (suffix[endpos+2] == ',' && suffix[endpos+3] == 0) {
2249 // allow dangling comma after width to be consistent with lifealgo::setgridsize
2250 } else {
2251 return "unexpected character in suffix";
2252 }
2253 }
2254 }
2255 }
2256 if (!oneval && suffix[endpos+2] != 0) return "unexpected character in suffix";
2257 }
2258 if ((float)newwd * (float)newht > MAXCELLS) return "grid size is too big";
2259 }
2260
2261 if (!suffix) {
2262 // no suffix given so universe is unbounded
2263 if (b1 == 0) return "B0 is not allowed if universe is unbounded";
2264 }
2265
2266 // the given rule is valid
2267 int oldrange = range;
2268 char oldtype = ntype;
2269 int scount = c;
2270 range = r;
2271 rangec = r2;
2272 totalistic = m;
2273 minS = s1;
2274 maxS = s2;
2275 minB = b1;
2276 maxB = b2;
2277 ntype = n;
2278 topology = t;
2279
2280 if (shape)
2281 free(shape) ;
2282 shape = (int *)calloc(sizeof(int), 2*r+1) ;
2283 for (int i=0; i<2*r+1; i++) {
2284 shape[i] = tshape[i] ;
2285 }
2286 // set the grid_type so the GUI code can display circles or diamonds in icon mode
2287 // (no circular grid, so adopt a square grid for now)
2288 #define CIRC_GRID SQUARE_GRID
2289 grid_type = ntype == 'M' ? SQUARE_GRID : (ntype == 'N' ? VN_GRID : CIRC_GRID) ;
2290
2291 if (suffix) {
2292 // use a bounded universe
2293 int minsize = 2 * range;
2294 if (newwd < minsize) newwd = minsize;
2295 if (newht < minsize) newht = minsize;
2296
2297 // if the new size is different or range has changed or ntype has changed
2298 // or the old universe is unbounded then we need to create new grids
2299 if (gwd != newwd || ght != newht || range != oldrange || ntype != oldtype || unbounded) {
2300 if (population > 0) {
2301 save_cells(); // store the current pattern in cell_list
2302 }
2303 // free the current grids and allocate new ones
2304 free(outergrid1);
2305 if (outergrid2) {
2306 free(outergrid2);
2307 outergrid2 = NULL;
2308 }
2309 create_grids(newwd, newht);
2310 if (cell_list.size() > 0) {
2311 // restore the pattern (if the new grid is smaller then any live cells
2312 // outside the grid will be saved in clipped_cells)
2313 restore_cells();
2314 }
2315 }
2316
2317 // tell GUI code not to call CreateBorderCells and DeleteBorderCells
2318 unbounded = false;
2319
2320 // set bounded grid dimensions used by GUI code
2321 gridwd = gwd;
2322 gridht = ght;
2323
2324 } else {
2325 // no suffix given so use an unbounded universe
2326 unbounded = true;
2327
2328 // set unbounded grid dimensions used by GUI code
2329 gridwd = 0;
2330 gridht = 0;
2331
2332 // check if previous universe was bounded
2333 if (gwd < outerwd) {
2334 // we could call resize_grids(-border,-border,-border,-border)
2335 // to remove the outer border but there's a (slight) danger
2336 // the call will fail due to lack of memory, so safer to use
2337 // the current grids and just shift the pattern position
2338 if (population > 0) {
2339 // shift pattern boundaries
2340 minx += border;
2341 maxx += border;
2342 miny += border;
2343 maxy += border;
2344 }
2345 currgrid = outergrid1;
2346 nextgrid = outergrid2;
2347 gwd = outerwd;
2348 ght = outerht;
2349 // set grid coordinates of cell at bottom right corner of grid
2350 gwdm1 = gwd - 1;
2351 ghtm1 = ght - 1;
2352 // adjust cell coordinates of grid edges
2353 gtop -= border;
2354 gleft -= border;
2355 gbottom = gtop + ghtm1;
2356 gright = gleft + gwdm1;
2357 // set bigint versions of grid edges (used by GUI code)
2358 gridtop = gtop;
2359 gridleft = gleft;
2360 gridbottom = gbottom;
2361 gridright = gright;
2362 }
2363
2364 // reallocate colcounts if ntype has changed
2365 if (ntype != oldtype) {
2366 allocate_colcounts();
2367 }
2368
2369 if (colcounts == NULL && outergrid2 == NULL) {
2370 // this can happen if previous rule used NM and was unbounded,
2371 // and new rule uses NN and is unbounded and range <= SMALL_NN_RANGE
2372 outergrid2 = (unsigned char*) calloc(outerbytes, sizeof(unsigned char));
2373 if (outergrid2 == NULL) lifefatal("Not enough memory for nextgrid!");
2374 nextgrid = outergrid2;
2375 }
2376
2377 if (colcounts && outergrid2) {
2378 // faster_* calls don't use outergrid2, so we deallocate it and
2379 // reset it to NULL (also necessary for test in step() loop)
2380 free(outergrid2);
2381 outergrid2 = NULL;
2382 nextgrid = NULL;
2383 }
2384 }
2385
2386 // set the number of cell states
2387 if (scount > 2) {
2388 // show history
2389 maxCellStates = scount;
2390 } else {
2391 maxCellStates = 2;
2392 scount = 0; // show C0 in canonical rule
2393 }
2394
2395 // set the canonical rule
2396 if (unbounded) {
2397 sprintf(canonrule, "R%d,C%d,M%d,S%d..%d,B%d..%d,N%c",
2398 range, scount, totalistic, minS, maxS, minB, maxB, ntype);
2399 } else {
2400 sprintf(canonrule, "R%d,C%d,M%d,S%d..%d,B%d..%d,N%c:%c%d,%d",
2401 range, scount, totalistic, minS, maxS, minB, maxB, ntype,
2402 topology, gwd, ght);
2403 }
2404
2405 // adjust the survival range if the center cell is not included
2406 if (totalistic == 0) {
2407 minS++;
2408 maxS++;
2409 }
2410
2411 return 0;
2412 }
2413
2414 // -----------------------------------------------------------------------------
2415
getrule()2416 const char* ltlalgo::getrule()
2417 {
2418 return canonrule;
2419 }
2420
2421 // -----------------------------------------------------------------------------
2422
DefaultRule()2423 const char* ltlalgo::DefaultRule()
2424 {
2425 return DEFAULTRULE;
2426 }
2427
2428 // -----------------------------------------------------------------------------
2429
creator()2430 static lifealgo *creator() { return new ltlalgo(); }
2431
doInitializeAlgoInfo(staticAlgoInfo & ai)2432 void ltlalgo::doInitializeAlgoInfo(staticAlgoInfo& ai)
2433 {
2434 ai.setAlgorithmName("Larger than Life");
2435 ai.setAlgorithmCreator(&creator);
2436 ai.setDefaultBaseStep(10);
2437 ai.setDefaultMaxMem(0);
2438 ai.minstates = 2;
2439 ai.maxstates = 256;
2440 // init default color scheme
2441 ai.defgradient = true; // use gradient
2442 ai.defr1 = 255; // start color = yellow
2443 ai.defg1 = 255;
2444 ai.defb1 = 0;
2445 ai.defr2 = 255; // end color = red
2446 ai.defg2 = 0;
2447 ai.defb2 = 0;
2448 // if not using gradient then set all states to white
2449 for (int i=0; i<256; i++) {
2450 ai.defr[i] = ai.defg[i] = ai.defb[i] = 255;
2451 }
2452 }
2453