1 /*
2  * XLife Copyright 1989 Jon Bennett jb7m+@andrew.cmu.edu, jcrb@cs.cmu.edu
3  *
4  * Permission to use, copy, modify, distribute, and sell this software and its
5  * documentation for any purpose is hereby granted without fee, provided that
6  * the above copyright notice appear in all copies and that both that
7  * copyright notice and this permission notice appear in supporting
8  * documentation, and that the name of the copyright holders not be used in
9  * advertising or publicity pertaining to distribution of the software without
10  * specific, written prior permission.  The copyright holders make no
11  * representations about the suitability of this software for any purpose.  It
12  * is provided "as is" without express or implied warranty.
13  *
14  * THE COPYRIGHT HOLDERS DISCLAIM ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
15  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
16  * EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY SPECIAL, INDIRECT OR
17  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
18  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
19  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
20  * PERFORMANCE OF THIS SOFTWARE.
21  */
22 
23 /*
24  * A lot of modifications were added at 2001, 2011-14 by Vladimir Lidovski vol.litwr@gmail.com
25  * (C) This version of XLife may be used under the same conditions as mentioned above
26  * $Id: tile.c 279 2014-01-14 08:09:57Z litwr $
27  */
28 
29 /*
30  * This module encapsulates cell-box handling. Everything else in the program
31  * except possibly the evolution function should go through these functions
32  * to change the board state. Entry points are:
33  *
34  * void initcells(context)        -- initialize active pattern
35  *
36  * int lookcell(context, x, y)    -- get state of cell
37  *
38  * void chgcell(context, x, y, c) -- set cell to state c
39  *
40  * void changesize(n)             -- change the cellbox allocation size
41  *
42  * void center()                  -- center viewport on barycenter of pattern
43  *
44  * void clear_all()               -- clear the universe, freeing all storage
45  *
46  * void redisplay(int mode)        -- update visible display of active board
47  *
48  * void drawboundedgrid(void)
49  *
50  * void saveall()                 -- save entire board state to file
51  *
52  * This code knows that cells are packed in 8x8 tiles on a hash list, but
53  * it doesn't know anything about the internals of cell representation within
54  * cell boxes.  The function changesize() changes the size of cellboxes.
55  *
56  * This code relies on the existence of a triad of functions:
57  *
58  * getcell(ptr, dx, dy)      -- get state of cell at x, y in box *ptr
59  * setcell(ptr, dx, dy, val) -- set cell at x, y in box *ptr to state val
60  *
61  * to access cell state. It also relies on the existence of these functions:
62  *
63  * displaybox(x, y, ptr)     -- post box state to Xrect arrays
64  * fetchtile(context, x, y)  -- get tile containing cell (x, y), NULL if none
65  * maketile(context, x, y)   -- get tile holding cell (x, y), creating if none
66  */
67 
68 #include <stddef.h>	/* we need offsetof() */
69 #include <stdlib.h>
70 #include "defs.h"
71 #include "patchlevel.h"
72 #include "colors.h"
73 #include "tile.h"
74 #include "file.h"
75 #include "framebuffer.h"
76 #include "history.h"
77 #include "topology.h"
78 
79 #define MARK		'*'
80 #define SPACE		'.'
81 #define	USL_MAX		4294967295U	/* max decimal value of "unsigned" */
82 
83 /* public variables */
84 pattern active, tentative, oscillator_check;
85 static tile *freep, *curtile;
86 static XTextProperty windowName;
87 static char window_name_pattern[61], *window_name = window_name_pattern;
88 
hashstat(pattern * p)89 void hashstat(pattern *p) {
90    unsigned hashsum = 0, hashcount = 0, i;
91    tile *ptr;
92    for (i = 0; i < HASHSIZE; i++)
93       if (ptr = p->hashlist[i]) {
94          do hashsum++; while (ptr = ptr->hnext);
95          hashcount++;
96       }
97    sprintf(inpbuf, "Hash %s: X=%u Y=%u [%u] filled=%.4f badness=%.3f tiles=%ld",
98                                              p == &active? "active": "tentative",
99          HASHBITS - 3 - p->hxs, 3 + p->hxs, HASHBITS, (double)hashcount/HASHSIZE,
100                         hashcount ? (double)hashsum/hashcount : 0, p->tilecount);
101 }
102 
fixhash(pattern * p)103 static void fixhash(pattern *p) {
104    tile *ptr;
105    memset(p->hashlist, 0, HASHSIZE*sizeof(tile*));
106    for (ptr = p->tiles; ptr; ptr = ptr->next) {
107       unsigned hv = HASH(ptr->x, ptr->y, p->hxm, p->hxs, p->hym);
108       if (ptr->hnext = p->hashlist[hv])
109          ptr->hnext->hfore = ptr;
110       p->hashlist[hv] = ptr;
111    }
112 }
113 
inithash(pattern * p)114 static void inithash(pattern *p) {
115    if (HASHBITS/2 - 3 != p->hxs) {
116       p->hxs = HASHBITS/2 - 3;
117       p->hxm = ((1 << HASHBITS - HASHBITS/2) - 1) << 3,
118       p->hym = (1 << HASHBITS/2) - 1;
119       fixhash(p);
120    }
121 }
122 
adjhash(pattern * p)123 void adjhash(pattern *p) {
124    if (p->tilecount < 16 << HASHBITS/2)
125       inithash(p);
126    else {
127       unsigned xc = 0, yc = 0;
128       bounding_box(p);
129       while (p->xmax - p->xmin >> 3 + xc++);
130       while (p->ymax - p->ymin >> 3 + yc++);
131       xc = HASHBITS/(1 + (double)yc/xc);
132       if (xc < 4)
133          xc = 4;
134       else if (xc > HASHBITS - 4)
135          xc = HASHBITS - 4;
136       yc = HASHBITS - xc;
137       if (p->hxs != yc - 3) {
138          p->hxs = yc - 3;
139          p->hxm = ((1 << xc) - 1) << 3,
140          p->hym = (1 << yc) - 1;
141          fixhash(p);
142       }
143    }
144    if (truehistory)
145       fixhistoryhash();
146 }
147 
setscale(const int sc)148 void setscale(const int sc) { /* preset scale for X rectangles describing active board */
149     int min = 1, max = 1;
150     if (sc > 0) {
151 	int	i, j, size = (1 << sc) - (sc > 1);
152 	for (i = 0; i < MAXCOLORS; i++)
153 	    for (j = 0; j < MAXCHANGE; j++) {
154 		rects[i][j].height = size;
155 		rects[i][j].width = size;
156 	    }
157     }
158     if (sc < 0)
159        min = 1 << -sc;
160     else
161        max = 1 << sc;
162     sprintf(window_name_pattern, "XLife v%d.%d.%d: a cellular-automaton laboratory [%d:%d]",
163        majorversion, minorversion, patchlevel, min, max);
164     if (XStringListToTextProperty(&window_name, 1, &windowName) == 0) {
165        fprintf(stderr, "structure allocation for WindowName failed.\n");
166        exit(5);
167     }
168     XSetWMName(disp, mainw, &windowName);
169 }
170 
initcells(pattern * context)171 void initcells(pattern *context) {
172    memset(context, '\0', sizeof(pattern));
173    inithash(context);
174 }
175 
chgcell(pattern * context,coord_t x,coord_t y,cell_t c)176 int chgcell(pattern *context, coord_t x, coord_t y, cell_t c) {
177 /* turn a cell to state ON, return cell change status */
178    tile *ptr = maketile(context, x, y);
179    unsigned ydx = y - ptr->y, xdx = x - ptr->x;
180    cell_t oldstate;
181    if (c) ptr->dead = 0;
182    oldstate = getcell(&ptr->cells, xdx, ydx);
183    if (truehistory && c && context == &active) add2history(ptr);
184    if (c != oldstate) {
185       if (c)
186          context->cellcount[c]++;
187       setcell(&ptr->cells, xdx, ydx, c);
188       context->cellcount[oldstate]--;
189       return 1;
190    }
191    return 0;
192 }
193 
changesize(int newsize)194 void changesize(int newsize) { /* change the tile allocation size */
195     if (tilesize != offsetof(tile, cells) + newsize) {
196 	tile	*ptr, *nptr;
197         clear_pattern(&active); /* clear all patterns */
198 	for (ptr = freep; ptr; ptr = nptr) {
199 	    nptr = ptr->next;
200 	    free(ptr);
201 	}
202 	freep = 0;
203 	tilesize = offsetof(tile, cells) + newsize;
204         redraw_lifew();
205     }
206 }
207 
killtile(pattern * context,tile * ptr)208 void killtile(pattern *context, tile *ptr) {
209 /* nuke a tile, reclaiming all associated storage and fixing neighbor links */
210     unsigned hv = HASH(ptr->x, ptr->y, context->hxm, context->hxs, context->hym);
211     if (ptr != context->tiles)
212 	ptr->fore->next = ptr->next;
213     else
214 	context->tiles = ptr->next;
215     if (ptr == context->hashlist[hv])
216 	context->hashlist[hv] = ptr->hnext;
217     else
218 	ptr->hfore->hnext = ptr->hnext;
219     if (ptr->next) ptr->next->fore = ptr->fore;
220     if (ptr->hnext) ptr->hnext->hfore = ptr->hfore;
221     if (ptr->rt) ptr->rt->lf = 0;
222     if (ptr->lf) ptr->lf->rt = 0;
223     if (ptr->up) ptr->up->dn = 0;
224     if (ptr->dn) ptr->dn->up = 0;
225     ptr->next = freep;
226     freep = ptr;
227     context->tilecount--;
228 }
229 
createtile(pattern * context,coord_t x,coord_t y,unsigned hv)230 static tile *createtile(pattern *context, coord_t x, coord_t y, unsigned hv) {
231 /* create a tile to hold cells near life-world coordinates x, y */
232 /* universe it belongs in */
233 /* associated life-world coordinates */
234 /* tile-retrieval hash value */
235     tile *ptr;
236 
237     if (freep == 0) {
238 	if ((ptr = (tile*)malloc(tilesize)) == 0)
239 	    fatal("create: malloc error: ");
240     }
241     else {
242 	ptr = freep;
243 	freep = freep->next;
244     }
245     memset(ptr, '\0', tilesize);
246     ptr->next = context->tiles;
247     context->tiles = ptr;
248 
249     if (ptr->next)
250 	ptr->next->fore = ptr;
251     ptr->hnext = context->hashlist[hv];
252     context->hashlist[hv] = ptr;
253     if (ptr->hnext)
254 	ptr->hnext->hfore = ptr;
255     ptr->x = x;
256     ptr->y = y;
257     context->tilecount++;
258     return ptr;
259 }
260 
findtile(pattern * context,coord_t x,coord_t y,unsigned hv)261 static tile *findtile(pattern *context, coord_t x, coord_t y, unsigned hv) {
262    tile *ptr = context->hashlist[hv];
263    while (ptr) {
264       if (ptr->x == x && ptr->y == y)
265          return ptr;
266          ptr = ptr->hnext;
267    }
268    return 0;
269 }
270 
lookcell(pattern * context,coord_t x,coord_t y)271 int lookcell(pattern *context, coord_t x, coord_t y) {
272 /* get the state of a cell from its world coordinates */
273    tile *ptr;
274    coord_t hx = x & XMASK, hy = y & YMASK;
275    unsigned hv = HASH(hx, hy, context->hxm, context->hxs, context->hym);
276    if (ptr = findtile(context, hx, hy, hv))
277       return getcell(&ptr->cells, x - hx, y - hy);
278    else
279       return 0;
280 }
281 
282 #define checktore() if (topology == 'T' && context == &active) {\
283          if (x >= x_max_limit)\
284             x = x - x_max_limit + x_min_limit;\
285          else if (x < x_min_limit)\
286             x = x - x_min_limit + x_max_limit;\
287          if (y >= y_max_limit)\
288             y = y - y_max_limit + y_min_limit;\
289          else if (y < y_min_limit)\
290             y = y - y_min_limit + y_max_limit;\
291     }
292 
fetchtile(pattern * context,coord_t x,coord_t y)293 tile *fetchtile(pattern *context, coord_t x, coord_t y) {
294     checktore();
295     return findtile(context, x, y, HASH(x, y, context->hxm, context->hxs, context->hym));
296 }
297 
maketile(pattern * context,coord_t x,coord_t y)298 tile *maketile(pattern *context, coord_t x, coord_t y) {
299     tile *ptr;
300     unsigned hv;
301     checktore();
302     x &= XMASK;
303     y &= YMASK;
304     hv = HASH(x, y, context->hxm, context->hxs, context->hym);
305     if (ptr = findtile(context, x, y, hv))
306        return ptr;
307     else
308        return createtile(context, x, y, hv);
309 }
310 
center(void)311 void center(void) {
312 /* center the display on the `center of mass' of the live boxes */
313    double x = 0, y = 0;
314    int ctr = 0;
315    tile *ptr;
316    for (ptr = active.tiles; ptr; ptr = ptr->next)
317       if (!ptr->dead) {
318          x += ptr->x;
319          y += ptr->y;
320          ctr++;
321       }
322    if (ctr > 0) {
323       x /= ctr;
324       y /= ctr;
325    }
326    else
327       x = xorigin, y = yorigin;
328    xpos = x - SCALE(width/2);
329    ypos = y - SCALE(height/2);
330 }
331 
display_move(int force,int dx,int dy)332 void display_move(int force, int dx, int dy) {
333 #if VFREQ != 0
334    prev_vsync.tv_sec--;
335 #endif
336    if ((tentative.tiles || force) && wireframe && scale == 1)
337       redraw_lifew();
338    else if ((tentative.tiles || force) && wireframe && scale > 1 && !dispmesh) {
339       griddisplay(0);
340       redisplay(MESH);
341    }
342    else if (topology != 'Q' && (dx || dy)) {
343       adjust_topology(dx, dy, 0);
344       if (tentative.tiles && wireframe)
345          redisplay(MESH);
346       else
347          redisplay(0);
348       adjust_topology(dx, dy, 1);
349       if (!tentative.tiles || !wireframe) {
350          if (dispmesh && scale > 1) {
351             griddisplay(1);
352             if (tentative.tiles && !wireframe)
353                boxpattern(CYAN_EVER);
354          }
355       }
356    }
357    else
358       redisplay(tentative.tiles || force);
359 }
360 
cmpnum(const void * e1,const void * e2)361 static int cmpnum(const void *e1, const void *e2) {
362    if (*(coord_t*)e1 < *(coord_t*)e2)
363       return -1;
364    return *(coord_t*)e1 > *(coord_t*)e2;
365 }
366 
median(void)367 void median(void) {
368 /* return the median coordinates of the live cells in the context */
369    coord_t *coordxlist, *coordylist;
370    int ctr = 0, x = xorigin, y = yorigin;
371    tile *ptr;
372    if (!(coordxlist = (coord_t*)malloc(sizeof(coord_t)*active.tilecount)))
373       return;
374    if (!(coordylist = (coord_t*)malloc(sizeof(coord_t)*active.tilecount))) {
375       free(coordxlist);
376       return;
377    }
378    for (ptr = active.tiles; ptr; ptr = ptr->next) {
379       if (!ptr->dead) {
380          coordxlist[ctr] = ptr->x;
381          coordylist[ctr++] = ptr->y;
382       }
383    }
384    if (ctr > 0) {
385       qsort(coordxlist, ctr, sizeof(coord_t), cmpnum);
386       qsort(coordylist, ctr, sizeof(coord_t), cmpnum);
387       x = coordxlist[ctr/2];
388       y = coordylist[ctr/2];
389    }
390    free(coordylist);
391    free(coordxlist);
392    xpos = x - SCALE(width/2);
393    ypos = y - SCALE(height/2);
394 }
395 
current_tile(void)396 void current_tile(void) {
397    if (curtile == 0)
398       curtile = active.tiles;
399    if (curtile) {
400       coord_t xnew, ynew;
401       int lflag = 0;
402       xnew = curtile->x - SCALE(width/2);
403       ynew = curtile->y - SCALE(height/2);
404       while (curtile->dead || labs((long)xnew - (long)xpos) < 10 << 6 - scale
405                           && labs((long)ynew - (long)ypos) < 10 << 6 - scale) {
406          curtile = curtile->next;
407          if (curtile == 0) {
408             if (lflag) return;
409             curtile = active.tiles;
410             lflag++;
411          }
412          xnew = curtile->x - SCALE(width/2);
413          ynew = curtile->y - SCALE(height/2);
414       }
415       xpos = xnew;
416       ypos = ynew;
417       curtile = curtile->next;
418    }
419 }
420 
cellcnt(pattern * pp)421 cellcount_t cellcnt(pattern *pp) {
422    int i;
423    cellcount_t sum = 0;
424    for (i = 1; i < maxstates; i++)
425       sum += pp->cellcount[i];
426    return sum;
427 }
428 
displaystats(void)429 void displaystats(void) {
430    sprintf(inpbuf, "Generations: %lu", active.generations);
431    if (active.cellmass) strcat(inpbuf, "*");
432    if (dispboxes)
433       sprintf(inpbuf + strlen(inpbuf), ", Cells: %u", cellcnt(&active));
434    else
435       sprintf(inpbuf + strlen(inpbuf), ", Tiles: %u", active.tilecount);
436    if (dispchanges)
437       sprintf(inpbuf + strlen(inpbuf), ", Changes: %u", active.chgcount);
438    if (dispspeed)
439       sprintf(inpbuf + strlen(inpbuf), ", Speed: %u", speed);
440    DoExpose(inputw);
441 }
442 
clear_pattern(pattern * pp)443 void clear_pattern(pattern *pp) {
444 /* free given pattern */
445    tile *ptr = pp->tiles, *nptr;
446    while (ptr) {
447       nptr = ptr->next;
448       killtile(pp, ptr);
449       ptr = nptr;
450    }
451    initcells(pp);
452 }
453 
clear_all(void)454 void clear_all(void) {
455 /* clear the board or tentative pattern, freeing all storage */
456    if (tentative.tiles)
457       clear_pattern(&tentative);
458    clear_pattern(&active);
459    redraw_lifew();
460 }
461 
fb_sync()462 static int fb_sync() {
463 #if VFREQ == 0
464    return 1;
465 #else
466    struct timeval cur;
467    gettimeofday(&cur, 0);
468    if ((cur.tv_sec - prev_vsync.tv_sec)*1000000 + cur.tv_usec
469                                         - prev_vsync.tv_usec > 1000000/VFREQ) {
470       prev_vsync = cur;
471       return 1;
472    }
473    else if (cur.tv_sec < prev_vsync.tv_sec)
474       prev_vsync = cur;
475    return state == STOP;
476 #endif
477 }
478 
ascale()479 static int ascale() {
480    if (scale >= 0)
481       return 8;
482    else if (scale <= -3)
483       return 1;
484    else if (scale == -1)
485       return 7;
486    return 5;
487 }
488 
onscreen(coord_t x,coord_t y)489 int onscreen(coord_t x, coord_t y) {
490    /*this is a bit complicated due to the big torus calculations */
491    int px_min = x > xpos - ascale(), py_min = y > ypos - ascale(),
492       px_max = x < xpos + SCALE(width), py_max = y < ypos + SCALE(height);
493    return (px_min && px_max
494       || (px_min || px_max) && (xpos - ascale() > xpos + SCALE(width)))
495       && (py_min && py_max
496       || (py_min || py_max) && (ypos - ascale() > ypos + SCALE(height)));
497 }
498 
griddisplay(int f)499 void griddisplay(int f) {
500    coord_t cx = width >> scale, cy = height >> scale;
501    int small = 1 << scale, x, y;
502    for (x = 0; x <= cx; x++)
503       if (x%5 == 0)
504          XDrawLine(disp, lifew, cellgc[GRID_ECOLOR*f], x*small - 1, 0, x*small - 1, height);
505       else
506          XDrawLine(disp, lifew, cellgc[GRID_COLOR*f], x*small - 1, 0, x*small - 1, height);
507    for (y = 0; y <= cy; y++) {
508       if (y%5 == 0)
509          XDrawLine(disp, lifew, cellgc[GRID_ECOLOR*f], 0, y*small - 1, width, y*small - 1);
510       else
511          XDrawLine(disp, lifew, cellgc[GRID_COLOR*f], 0, y*small - 1, width, y*small - 1);
512    }
513 }
514 
tile_fb_update(void)515 void tile_fb_update(void) {
516    tile *ptr;
517    coord_t x, y, tentx, tenty;
518    int curstate, q = 0;
519    if (truehistory) {
520       historytile *ptr;
521       for (curstate = 1; curstate >= 0; curstate--) {
522          for (ptr = history[curstate].tiles; ptr; ptr = ptr->next) {
523             x = ptr->x;
524             y = ptr->y;
525             if (onscreen(x, y)) {
526                if (scale < -3) {
527                   tentx = (x >> -scale) << -scale;
528                   tenty = (y >> -scale) << -scale;
529                   if (x != tentx || y != tenty) {
530                      if (!fetchhistorytile(history + curstate, tentx, tenty)) {
531                         makehistorytile(history + curstate, tentx, tenty);
532                         q++;
533                      }
534                      continue;
535                   }
536                }
537                displayhistorybox(x, y, ptr, curstate);
538             }
539          }
540          if (q)
541             for (ptr = history[curstate].tiles; q--; ptr = ptr->next)
542                displayhistorybox(ptr->x, ptr->y, ptr, curstate);
543             q = 0;
544       }
545    }
546    for (ptr = active.tiles; ptr; ptr = ptr->next) {
547       x = ptr->x;
548       y = ptr->y;
549       if (onscreen(x, y)) {
550          if (scale < -3 && topology != 'T') {
551             tentx = (x >> -scale) << -scale;
552             tenty = (y >> -scale) << -scale;
553             if (x != tentx || y != tenty) {
554                if (!fetchtile(&active, tentx, tenty)) {
555                   maketile(&active, tentx, tenty);
556                   q++;
557                }
558                continue;
559             }
560          }
561          displaybox(x, y, &ptr->cells);
562       }
563    }
564    if (q)
565       for (ptr = active.tiles; q--; ptr = ptr->next)
566          displaybox(ptr->x, ptr->y, &ptr->cells);
567    q = 0;
568    if (tentative.tiles && (!wireframe || scale < 1)) {
569       /* draw tentative points with appropriate transformation */
570       for (ptr = tentative.tiles; ptr; ptr = ptr->next) {
571          tile *nptr;
572          tentx = ptr->x - STARTX;
573          tenty = ptr->y - STARTY;
574          if (onscreen(Tx(tentx,tenty), Ty(tentx,tenty))) {
575             if (scale < -3) {
576                tentx = (tentx >> -scale) << -scale;
577                tenty = (tenty >> -scale) << -scale;
578                x = (ptr->x >> -scale) << -scale;
579                y = (ptr->y >> -scale) << -scale;
580                if (ptr->x != x || ptr->y != y) {
581                   if (!fetchtile(&tentative, x, y)) {
582                      maketile(&tentative, x, y);
583                      q++;
584                   }
585                   continue;
586                }
587             }
588             trdisplaybox(tentx, tenty, &ptr->cells);
589          }
590       }
591       if (q)
592          for (ptr = tentative.tiles; q--; ptr = ptr->next)
593             trdisplaybox(ptr->x - STARTX, ptr->y - STARTY, &ptr->cells);
594          q = 0;
595    }
596 }
597 
redisplay(int mode)598 void redisplay(int mode) {
599 /* re-display the visible part of the board*/
600    tile *ptr;
601    coord_t x, y, tentx, tenty;
602    int curstate, q = 0;
603    if (state == HIDE) return;
604    if (dispmesh && scale > 1 && (mode & MESH)) griddisplay(1);
605    if (!fb_sync()) return;
606    if (tentative.tiles && pivot) { /* remove pivot of tentative points */
607       if (!wireframe) boxpattern(CYAN_EVER);
608       drawpivot();
609    }
610    if (mode & EXPOSE)
611       fb_flush_rep();
612    else {
613       tile_fb_update();
614       fb_flush();
615    }
616    if (tentative.tiles && wireframe && scale >= 1)
617       /* draw tentative points with appropriate transformation */
618       for (ptr = tentative.tiles; ptr; ptr = ptr->next) {
619          tile *nptr;
620          tentx = ptr->x - STARTX;
621          tenty = ptr->y - STARTY;
622          if (onscreen(tx(tentx,tenty,txx,txy) + loadx,
623                                             ty(tentx,tenty,tyx,tyy) + loady)) {
624             if (scale < -3) {
625                tentx = (tentx >> -scale) << -scale;
626                tenty = (tenty >> -scale) << -scale;
627                x = (ptr->x >> -scale) << -scale;
628                y = (ptr->y >> -scale) << -scale;
629                if (ptr->x != x || ptr->y != y) {
630                   if (!fetchtile(&tentative, x, y)) {
631                      maketile(&tentative, x, y);
632                      q++;
633                   }
634                   continue;
635                }
636             }
637             trdisplaybox_nofb(tentx, tenty, &ptr->cells);
638             if (q)
639                for (nptr = tentative.tiles; q--; nptr = nptr->next)
640                   trdisplaybox_nofb(nptr->x - STARTX, nptr->y - STARTY,
641                                                                  &nptr->cells);
642             q = 0;
643             if (scale > 0)
644                for (curstate = 1; curstate < maxstates; curstate++)
645                   if (chgrects[curstate]) {
646                      if (scale > 1)
647                         for (q = 0; q < chgrects[curstate]; q++) {
648                            rects[curstate][q].x--;
649                            rects[curstate][q].y--;
650                            rects[curstate][q].height++;
651                            rects[curstate][q].width++;
652                         }
653                      XDrawRectangles(disp, lifew, cellgc[LOAD_BOX],
654                                           rects[curstate], chgrects[curstate]);
655                      if (scale > 1)
656                         for (q = 0; q < chgrects[curstate]; q++) {
657                            rects[curstate][q].height--;
658                            rects[curstate][q].width--;
659                         }
660                      q = chgrects[curstate] = 0;
661                   }
662          }
663       }
664    /* removedraw pivot of tentative points and box them */
665    if (tentative.tiles) {
666       if (!wireframe) boxpattern(CYAN_EVER); /* outline box */
667       drawpivot();
668    }
669    XFlush(disp);
670 }
671 
bounding_box(pattern * context)672 cellcount_t bounding_box(pattern *context) {
673 /* get the bounding box of a pattern */
674    int dx, dy, state;
675    tile *ptr;
676    context->ymin = context->xmin = USL_MAX;
677    context->ymax = context->xmax = 0;
678    if (context->tiles == 0)
679       return context->ymin = context->xmin = 0;
680    for (state = 1; state < maxstates; state++)
681       context->cellcount[state] = 0;
682    FOR_CELLS(context, ptr, dx, dy) {
683       if (state = getcell(&ptr->cells, dx, dy)) {
684          context->cellcount[state]++;
685          if (ptr->x + dx < context->xmin)
686             context->xmin = ptr->x + dx;
687          if (ptr->y + dy < context->ymin)
688             context->ymin = ptr->y + dy;
689          if (ptr->x + dx > context->xmax)
690             context->xmax = ptr->x + dx;
691          if (ptr->y + dy > context->ymax)
692             context->ymax = ptr->y + dy;
693       }
694    }
695    return cellcnt(context);
696 }
697 
flood_fill(pattern * from,coord_t x,coord_t y,pattern * to)698 static void flood_fill(pattern *from, coord_t x, coord_t y, pattern *to) {
699 /* transplant all points in a blob touching (x,y) between contexts */
700     static offsets neighbors[] =
701     {
702 	{-1, -1},
703 	{-1,  0},
704 	{-1,  1},
705 	{ 0, -1},
706 	{ 0,  1},
707 	{ 1, -1},
708 	{ 1,  0},
709 	{ 1,  1},
710 #ifdef DEPTH2
711 	{-2, -2},
712 	{-2, -1},
713 	{-2,  0},
714 	{-2,  1},
715 	{-2,  2},
716 	{-1,  2},
717 	{ 0,  2},
718 	{ 1,  2},
719 	{ 2,  2},
720 	{ 2,  1},
721 	{ 2,  0},
722 	{ 2, -1},
723 	{ 2, -2},
724 	{ 1, -2},
725 	{ 0, -2},
726 	{-1, -2},
727 #endif /* DEPTH2 */
728     };
729     int i;
730 
731     /* skip empty cells */
732     if (!lookcell(from, x, y))
733 	return;
734 
735     /* skip cells that are already colored */
736     if (lookcell(to, x, y))
737 	return;
738 
739     /* transfer this cell from the copy to the new context */
740     chgcell(to,   x, y, lookcell(from, x, y));
741     chgcell(from, x, y, 0);
742 
743     for (i = 0; i < sizeof(neighbors)/sizeof(neighbors[0]); i++) {
744 	int nx = x + neighbors[i].xi;
745 	int ny = y + neighbors[i].yi;
746 
747 	/* recursively transfer all its neighbors */
748 	flood_fill(from, nx, ny, to);
749     }
750 }
751 
refcmp(const void * r1,const void * r2)752 static int refcmp(const void *r1, const void *r2) {
753 /* sort blobs first by least Y coordinate, then by least X coordinate */
754     int	cmp = (((pattern*)r1)->ymin - ((pattern*)r2)->ymin);
755 
756     if (!cmp)
757 	cmp = (((pattern*)r1)->xmin - ((pattern*)r2)->xmin);
758     return cmp;
759 }
760 
analyze(pattern * context)761 pattern *analyze(pattern *context) {
762 /* analyze a pattern into an allocated list of blobs */
763     cell_t	state;
764     tile	*ptr;
765     int		dx, dy, color = 0;
766     pattern	*parts, *pp;
767     static pattern analysand; /* too big to be automatic */
768 
769     initcells(&analysand);
770 
771     /* copy the pattern */
772     FOR_CELLS(context, ptr, dx, dy)
773 	if ((state = getcell(&ptr->cells, dx, dy)))
774 	    chgcell(&analysand, ptr->x + dx, ptr->y + dy, state);
775     /*
776      * This loop is deceptively simple-looking.  It relies on flood_fill()
777      * not returning until it has transpanted the largest blob it can find
778      * connected to a cell.
779      */
780     parts = (pattern*)calloc(sizeof(pattern), 1);
781     FOR_CELLS(&analysand, ptr, dx, dy)
782 	if (getcell(&ptr->cells, dx, dy)) {
783 	    parts = (pattern *)realloc(parts, sizeof(pattern) * (color + 1));
784 	    initcells(&parts[color]);
785 	    flood_fill(&analysand, ptr->x + dx, ptr->y + dy, &parts[color]);
786 	    color++;
787 	}
788 
789     /* create an extra, blank pattern entry as a fencepost */
790     parts = (pattern *)realloc(parts, sizeof(pattern) * (color + 1));
791     initcells(&parts[color]);
792 
793     /* this cleans up the blob order -- strictly cosmetic */
794     for (pp = parts; pp->tiles; pp++)
795 	bounding_box(pp);
796     qsort(parts, color, sizeof(pattern), refcmp);
797 
798     /* return the analyzed parts */
799     return parts;
800 }
801 
saveformatsign(char f,int xoff,int yoff,FILE * ofp)802 void saveformatsign(char f, int xoff, int yoff, FILE* ofp) {
803    fprintf(ofp, "#%c", f);
804    if (xoff || yoff)
805       fprintf(ofp, " %d %d", xoff, yoff);
806    fputs("\n", ofp);
807 }
808 
savesimple(pattern * pp,int xoff,int yoff,FILE * ofp)809 void savesimple(pattern *pp, int xoff, int yoff, FILE *ofp) {
810 /* save a pattern as a simple picture block */
811     coord_t x, y;
812     cellcount_t cellcount = bounding_box(pp);
813     if (cellcount == 0)
814 	return;
815     saveformatsign('P', xoff, yoff, ofp);
816     for (y = pp->ymin; y <= pp->ymax; y++) {
817 	for (x = pp->xmin; x <= pp->xmax; x++) {
818 	    int val;
819 	    if (val = lookcell(pp, x, y)) {
820 		if (maxstates > 2)
821 		    fputc(itos(val), ofp);
822 		else
823 		    fputc(MARK, ofp);
824 	    }
825 	    else
826 		fputc(SPACE, ofp);
827 	}
828 	fputc('\n', ofp);
829     }
830 }
831 
savecomplex(pattern * context,FILE * ofp)832 static void savecomplex(pattern *context, FILE *ofp) {
833 /* do a pattern analysis and save the pattern as a blob sequence */
834     pattern	*pp, *parts = analyze(context);
835     int		xcenter, ycenter, blobcount = 0;
836     if (parts == NULL) {
837 	perror("Pattern analysis failed; too many blobs in picture.\n");
838 	return;
839     }
840     for (pp = parts; pp->tiles; pp++)
841 	blobcount++;
842     if (blobcount > 1)
843 	fprintf(ofp, "#C %d blobs\n", blobcount);
844     for (pp = parts; pp->tiles; pp++)
845 	savesimple(pp, pp->xmin - STARTX, pp->ymin - STARTY, ofp);
846 }
847 
rlestr(int c)848 char* rlestr(int c) {
849    static char s[3];
850    if (c < 25) {
851       s[1] = 0;
852       if (c == 0)
853         s[0] = 'b';
854       else if (c == 1)
855         s[0] = 'o';
856       else
857         s[0] = c + '@';
858    }
859    else {
860       s[0] = 'o' + (c - 1)/24;
861       s[1] = (c - 1)%24 + 'A';
862       s[2] = 0;
863    }
864    return s;
865 }
866 
867 #define rleflush(n) if (strlen(buf) > n) {\
868        t = *p;\
869        *p = '\0';\
870        fprintf(ofp, "%s\n", buf);\
871        *p = t;\
872        strcpy(buf, p);\
873    }\
874    p = buf + strlen(buf);
875 
876 
saveall(FILE * ofp,char mode)877 void saveall(FILE *ofp, char mode) {
878 /* save the entire board contents (or the tentative pattern if there is one) */
879     tile *ptr;
880     char buf[100], *p = buf, t;
881     int dx, dy, val;
882     coord_t x = 0, y;
883     cellcount_t cellcount;
884     pattern *pp = tentative.tiles ? &tentative : &active;
885 /*
886  * Determine the bounding box of the live cells.
887  */
888     cellcount = bounding_box(pp);
889     if (mode == '4') { /* 8-bit format */
890           if (ev_mode != VALENCE_DRIVEN || (born&1) || pp->xmax - pp->xmin >= 192
891                 || pp->ymax - pp->ymin >= 192
892                 || pp->xmax - pp->xmin >= 160 && pp->ymax - pp->ymin >= 160) {
893              fprintf(stderr, "can't convert this pattern\n");
894              return;
895           }
896           fprintf(ofp, "%c%c", pp->xmax - pp->xmin + 1, pp->ymax - pp->ymin + 1);
897           fwrite(&live, 2, 1, ofp);
898           fwrite(&born, 2, 1, ofp);
899 	  FOR_CELLS(pp, ptr, dx, dy)
900 		if (val = getcell(&ptr->cells, dx, dy))
901 		    fprintf(ofp, "%c%c",
902 			       ptr->x + dx - pp->xmin, ptr->y + dy - pp->ymin);
903 	  return;
904     }
905     fprintf(ofp, "##XLife\n");
906     if (fname[0])
907         fprintf(ofp, "#N %s\n", fname);
908     else if (stashed[0]) {
909         char *p = strrchr(stashed, '/');
910         if (p)
911              p++;
912         else
913              p = stashed;
914         if (strchr(p, ':'))
915            fprintf(ofp, "#N %s\n", p);
916     }
917     stamp("#0", ofp);
918     if (outcome[0])
919         fprintf(ofp, "#K %s\n", outcome);
920     while (x < numcomments)
921 	fprintf(ofp, "#C %s\n", comments[x++]);
922     if (fname[0])
923 	fprintf(ofp, "#N %s\n", fname);
924     strcpy(buf, active_rules);
925     if (!strcmp(buf, "life"))
926         strcpy(buf, "23/3");
927     t = 'U';
928     if (strchr(buf, '$') || !strcmp(buf, "wireworld") || !strcmp(buf, "brian's brain")
929              || strchr(buf, '/') || !strcmp(buf, "life+") || !strcmp(buf, "lifehistory"))
930         t = 'T';
931     fprintf(ofp, "#%c %s", t, buf);
932     if (topology != 'Q')
933         fprintf(ofp, ":%c%d,%d", topology, x_max_limit - x_min_limit, y_max_limit - y_min_limit);
934     fprintf(ofp, "\n");
935     if (*colorfile)
936        fprintf(ofp, "#X %s\n", strrchr(colorfile, '/') + 1);
937     buf[0] = 0;
938 /* caller may want save to shortest format */
939     if (mode == '\0')
940 	if ((pp->ymax - pp->ymin + 1)*(pp->xmax - pp->xmin + 1) > cellcount * 8)
941 	    mode = 'R';
942 	else
943 	    mode = 'P';
944 
945 /* now that we have the bounding box, we can gen the other formats */
946     switch (mode) {
947 	case 'A': /* save in absolute mode */
948 	  fputs("#A\n", ofp);
949 	  FOR_CELLS(pp, ptr, dx, dy)
950 			if (val = getcell(&ptr->cells, dx, dy))
951 			    if (maxstates > 2)
952 				fprintf(ofp, "%d %d %d\n",
953 					       ptr->x + dx - xorigin,
954                                                ptr->y + dy - yorigin, val);
955 			    else
956 				fprintf(ofp, "%d %d\n",
957                                                ptr->x + dx - xorigin,
958                                                ptr->y + dy - yorigin);
959 	return;
960 
961 	case 'R':
962           saveformatsign('R', pp->xmin - STARTX, pp->ymin - STARTY, ofp);
963 	  FOR_CELLS(pp, ptr, dx, dy)
964 		if (val = getcell(&ptr->cells, dx, dy))
965 		    if (maxstates > 2)
966 			  fprintf(ofp, "%d %d %d\n",
967 				       ptr->x + dx - pp->xmin, ptr->y + dy - pp->ymin,
968 				       val);
969 		    else
970 		          fprintf(ofp, "%d %d\n",
971 				       ptr->x + dx - pp->xmin, ptr->y + dy - pp->ymin);
972 	  return;
973 
974 	case 'P':
975 	  savesimple(pp, pp->xmin - STARTX, pp->ymin - STARTY, ofp);
976 	  return;
977 
978 	case 'D':
979           saveformatsign('D', pp->xmin - STARTX, pp->ymin - STARTY, ofp);
980 	  x = pp->xmin;
981 	  y = pp->ymin;
982 	  FOR_CELLS(pp, ptr, dx, dy)
983 			if (val = getcell(&ptr->cells, dx, dy)) {
984 			    if (maxstates > 2)
985 				fprintf(ofp, "%d %d %d\n",
986 					       ptr->x + dx - x, ptr->y + dy - y,
987 					       val);
988 			    else
989 				fprintf(ofp, "%d %d\n",
990 					       ptr->x + dx - x, ptr->y + dy - y);
991 			    x = ptr->x + dx;
992 			    y = ptr->y + dy;
993 			}
994 	  return;
995 
996 	case 'M':
997           saveformatsign('M', pp->xmin - STARTX, pp->ymin - STARTY, ofp);
998 	  dy = 0;
999 	  for (y = pp->ymin; y <= pp->ymax; y++) {
1000 	    for (x = pp->xmin; x <= pp->xmax; x = dx) {
1001 		val = lookcell(pp, x, y);
1002 		for (dx = x + 1; dx <= pp->xmax && lookcell(pp, dx, y) == val; dx++);
1003 		if (val) {
1004 		    if (dy > 1)
1005 			sprintf(p, "%d$", dy);
1006 		    else if (dy > 0)
1007 			strcpy(p, "$");
1008                     rleflush(70);
1009 		    dy = 0;
1010 		    if (maxstates > 2)
1011 			if (dx - x > 1)
1012 			    sprintf(p, "%d%s", dx - x, rlestr(val));
1013 			else
1014 			    sprintf(p, "%s", rlestr(val));
1015 		    else
1016 			if (dx - x > 1)
1017 			    sprintf(p, "%do", dx - x);
1018 			else
1019 			    strcpy(p, "o");
1020 		}
1021 		else if (dx <= pp->xmax) {
1022 		    if (dy > 1)
1023 			sprintf(p, "%d$", dy);
1024 		    else if (dy > 0)
1025 			strcpy(p, "$");
1026                     rleflush(70);
1027 		    dy = 0;
1028 		    if (dx - x > 1)
1029 		        sprintf(p, "%db", dx - x);
1030 		    else
1031 		        strcpy(p, "b");
1032 		}
1033                 rleflush(70);
1034 	    }
1035 	    dy++;
1036 	  }
1037 	  if (buf[0])
1038 	    fprintf(ofp, "%s", buf);
1039 	  fprintf(ofp, "!\n");
1040 	  return;
1041 
1042 	case 'I':
1043 	  savestructured(pp, ofp);
1044 	  return;
1045 
1046 	case 'S':
1047 	  savecomplex(pp, ofp);
1048 	  return;
1049     }
1050 }
1051 /* tile.c ends here */
1052