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