1 /*
2 * XLife Copyright 1998 Eric S. Raymond <esr@thyrsus.com>
3 *
4 */
5
6 /*
7 Several modifications were added at 2011 by Vladimir Lidovski <vol.litwr@gmail.com>
8 $Id: isave.c 271 2014-01-11 15:33:25Z litwr $
9 */
10
11 /* it saves pattern in I-format.
12 */
13
14 #include <stdlib.h>
15 #include <ctype.h>
16 #include "defs.h"
17 #include "file.h"
18 #include "tile.h"
19
20 #define NO_MATCH -1 /* not 0..16 */
21
22 char matchlibfile[64] = "named-patterns";
23
24 typedef struct {
25 int xtrans, ytrans; /* translation point */
26 int flip; /* 1 or -1 */
27 int rotation; /* 0..3, 90-degree increments clockwise */
28 } dihedral;
29
30 typedef struct blobref_t {
31 int xsize, ysize, number;
32 dihedral where;
33 pattern *pattern;
34 pattern *blob;
35 struct blobref_t *ref;
36 #ifdef COALESCE
37 int refcount;
38 #endif /* COALESCE */
39 } blobref;
40
transform(int flip,int rotation,coord_t j,coord_t i,coord_t xsize,coord_t ysize,coord_t * newx,coord_t * newy)41 static void transform(int flip, int rotation,
42 coord_t j, coord_t i,
43 coord_t xsize, coord_t ysize,
44 coord_t *newx, coord_t *newy) {
45 switch (rotation + 4 * flip) {
46 case 0: /* no rotation, no flip */
47 *newx = j;
48 *newy = i;
49 break;
50
51 case 1: /* one rotation, no flip */
52 *newx = i;
53 *newy = ysize - j;
54 break;
55
56 case 2: /* two rotations, no flip */
57 *newx = xsize - j;
58 *newy = ysize - i;
59 break;
60
61 case 3: /* three rotations, no flip */
62 *newx = xsize - i;
63 *newy = j;
64 break;
65
66 case 4: /* no rotation, one flip */
67 *newx = j;
68 *newy = ysize - i;
69 break;
70
71 case 5: /* one rotation, one flip */
72 *newx = i;
73 *newy = j;
74 break;
75
76 case 6: /* two rotations, one flip */
77 *newx = xsize - j;
78 *newy = i;
79 break;
80
81 case 7: /* three rotations, one flip */
82 *newx = xsize - i;
83 *newy = ysize - j;
84 }
85 }
86
blob_equal(pattern * within,const blobref * tp,const blobref * sp,dihedral * where)87 static int blob_equal(pattern *within,
88 const blobref *tp, const blobref *sp,
89 dihedral *where) {
90 /* check blob tp for equality with blob sp */
91 static offsets xoffmagic[] =
92 {{0, 0}, {0, 1}, {1, 0}, {0, 0}, {0, 0}, {0, 0}, {1, 0}, {0, 1}};
93 static offsets yoffmagic[] =
94 {{0, 0}, {0, 0}, {0, 1}, {1, 0}, {0, 1}, {0, 0}, {0, 0}, {1, 0}};
95 int i, j, rotation, flip;
96
97 /* check for identical population */
98 if (cellcnt(tp->blob) != cellcnt(sp->blob))
99 return NO_MATCH;
100
101 /* bounding rectangles must be compatible */
102 if (!(tp->xsize == sp->xsize && tp->ysize == sp->ysize
103 || tp->xsize == sp->ysize && tp->ysize == sp->xsize))
104 return NO_MATCH;
105
106 for (rotation = 0; rotation < 4; rotation++)
107 for (flip = 0; flip < 2; flip++) {
108 int trans = rotation + 4*flip;
109 coord_t newx, newy, xbcorner, ybcorner;
110
111 #ifdef BLOBDEBUG
112 fprintf(stderr, "Flip %d, rotation %d\n", flip ? -1 : 1, rotation);
113 #endif /* BLOBDEBUG */
114
115 for (i = 0; i < sp->ysize; i++)
116 for (j = 0; j < sp->xsize; j++) {
117 transform(flip, rotation, j, i, tp->xsize-1, tp->ysize-1,
118 &newx, &newy);
119 if (lookcell(sp->blob, sp->blob->xmin + j, sp->blob->ymin + i)
120 != lookcell(tp->blob, tp->blob->xmin + newx, tp->blob->ymin + newy))
121 goto nomatch;
122 }
123
124 /* OK, now we have the corner of the matching blob pinned down */
125 xbcorner = sp->where.xtrans
126 + xoffmagic[trans].xi * (tp->xsize-1)
127 + xoffmagic[trans].yi * (tp->ysize-1);
128 ybcorner = sp->where.ytrans
129 + yoffmagic[trans].xi * (tp->xsize-1)
130 + yoffmagic[trans].yi * (tp->ysize-1);
131
132 flip = flip ? -1 : 1;
133
134 #ifdef BLOBDEBUG
135 /*
136 * OK, the blobs matched. What if there is a larger composite
137 * pattern associated with tp? Does it match the rest of the
138 * context?
139 */
140 if (tp->pattern != tp->blob) {
141 coord_t xsize = tp->pattern->xmax - tp->pattern->xmin;
142 coord_t ysize = tp->pattern->ymax - tp->pattern->ymin;
143 coord_t xinner, yinner, xouter, youter, xloc, yloc;
144
145 printf("# Possible %s with flip %2d rotation %d based on blob at (%d,%d)\n",
146 tp->pattern->pattern_name,
147 flip, rotation,
148 sp->where.xtrans, sp->where.ytrans);
149 continue;
150 }
151 #endif
152
153 if (where) {
154 where->flip = flip;
155 where->rotation = rotation;
156 where->xtrans = xbcorner;
157 where->ytrans = ybcorner;
158 }
159 return trans;
160 nomatch:;
161 }
162
163 return NO_MATCH;
164 }
165
savestructured(pattern * context,FILE * ofp)166 void savestructured(pattern *context, FILE *ofp) {
167 /* save with full scene analysis in structured (#I) format */
168 pattern *pp, *parts;
169 blobref *scene, *sp, *tp;
170 int blobcount, i, nonrefcount;
171 FILE *fp;
172 LoadReq *loadqueue;
173 static int matchcount = 0;
174 static blobref *matchlib;
175
176 if ((parts = analyze(context)) == 0) {
177 perror("Pattern analysis failed; too many blobs in picture.\n");
178 return;
179 }
180 /* if there is only one blob, save in #P format */
181 if (!parts[1].tiles) {
182 bounding_box(context);
183 savesimple(context, context->xmin - STARTX, context->ymin - STARTY, ofp);
184 free(parts);
185 return;
186 }
187 /*
188 * Otherwise it's time to do a full scene analysis.
189 */
190 blobcount = 0;
191 for (pp = parts; pp->tiles; pp++)
192 blobcount++;
193 scene = (blobref*)calloc(sizeof(blobref), blobcount);
194
195 /* assemble a list of blob references */
196 for (i = 0; i < blobcount; i++) {
197 pattern *pp = parts + i;
198 sp = scene + i;
199
200 sp->xsize = pp->xmax - pp->xmin + 1;
201 sp->ysize = pp->ymax - pp->ymin + 1;
202
203 sp->pattern = sp->blob = &parts[i];
204
205 sp->ref = 0; /* defensive programming */
206 sp->where.rotation = 0; /* defensive programming */
207 sp->where.flip = 1;
208 sp->where.xtrans = sp->pattern->xmin;
209 sp->where.ytrans = sp->pattern->ymin;
210 #ifdef COALESCE
211 sp->refcount = 1;
212 #endif /* COALESCE */
213 }
214
215 /* search for duplicate blobs */
216 for (sp = scene; sp < scene + blobcount; sp++)
217 for (tp = scene; tp < sp; tp++) {
218 if (tp->ref)
219 continue;
220 if (blob_equal(context, tp, sp, &sp->where) != NO_MATCH) {
221 sp->ref = tp;
222 #ifdef COALESCE
223 tp->refcount++;
224 #endif /* COALESCE */
225 #ifdef BLOBDEBUG
226 fprintf(stderr, "Matched, flip %d and rotation %d\n",
227 sp->where.flip, sp->where.rotation);
228 #endif /* BLOBDEBUG */
229 break;
230 }
231 }
232 /* initialize the list of named blobs */
233 if (!matchcount) {
234 if (!strcmp(active_rules, "life") && !find_file(matchlibfile, dirs) && (fp = fopen(rfullpath, "r"))) {
235 char buf[BUFSIZ], name[BUFSIZ], request[BUFSIZ];
236 int gens, gen;
237 cell_t state;
238 matchcount = 0;
239 matchlib = (blobref*)calloc(sizeof(blobref), 1);
240 while (fgets(buf, sizeof(buf) - 1, fp)) {
241 char *cp;
242 static pattern matcher; /* must be initially zeroed */
243 if (buf[0] == '#') /* allow comments */
244 continue;
245 initcells(&matcher);
246 if (cp = strchr(buf, '#'))
247 while (isspace(*cp) || *cp == '#')
248 *cp-- = '\0';
249 name[0] = request[0] = '\0';
250 gens = 0;
251 sscanf(buf, "%s %s %d", name, request, &gens);
252 if (name[0] == '\0')
253 continue;
254 else if (request[0] == '\0')
255 strcpy(request, name);
256 buf[strlen(buf) - 1] = '\0';
257 loadqueue = 0;
258 loadx = xpos;
259 loady = ypos;
260 txx = tyy = 1;
261 txy = tyx = 0;
262 add_loadreq(&loadqueue, 0, request, 0,
263 STARTX, STARTY, 1, 0, 0, 1);
264 if (!do_loadreq(loadqueue, &matcher)) return;
265 gen = 0;
266 do {
267 tile *ptr;
268 int dx, dy;
269 if (gen == 0)
270 strcpy(request, name);
271 else
272 sprintf(request, "%s%d", name, gen + 1);
273 matchlib = (blobref*)realloc(matchlib, sizeof(blobref)*(matchcount + 1));
274 tp = matchlib + matchcount;
275 tp->pattern = (pattern*)malloc(sizeof(pattern));
276 initcells(tp->pattern);
277 FOR_CELLS(&matcher, ptr, dx, dy)
278 if ((state = getcell(&ptr->cells, dx, dy)))
279 chgcell(tp->pattern, ptr->x + dx, ptr->y + dy, state);
280 bounding_box(tp->pattern);
281 tp->blob = 0;
282 tp->pattern->pattern_name = strdup(request);
283 matchcount++;
284 generate(&matcher);
285 } while
286 (++gen < gens);
287 }
288 fclose(fp);
289 }
290 /* now go through looking for composites */
291 for (tp = matchlib; tp < matchlib + matchcount; tp++) {
292 pattern *pp, *parts = analyze(tp->pattern);
293 if (!parts[1].tiles)
294 tp->blob = tp->pattern;
295 else
296 {
297 int merit = 0;
298 pattern *best;
299 for (pp = parts; pp->tiles; pp++) {
300 int m = cellcnt(pp)*(pp->xmax - pp->xmin)*(pp->ymax - pp->ymin);
301 if (m > merit) {
302 best = pp;
303 merit = m;
304 }
305 }
306 tp->blob = (pattern*)malloc(sizeof(pattern));
307 memcpy(tp->blob, best, sizeof(pattern));
308 initcells(best);
309 }
310 for (pp = parts; pp->tiles; pp++)
311 clear_pattern(pp);
312 free(parts);
313 bounding_box(tp->blob);
314 tp->xsize = (tp->blob->xmax - tp->blob->xmin + 1);
315 tp->ysize = (tp->blob->ymax - tp->blob->ymin + 1);
316 }
317 }
318 /* check for named blocks in the pattern */
319 if (matchcount) {
320 int point;
321 for (sp = scene; sp < scene + blobcount; sp++)
322 for (tp = matchlib; tp < matchlib + matchcount; tp++)
323 if ((point = blob_equal(context, tp, sp, (dihedral *)NULL)) != NO_MATCH) {
324 char *cp;
325
326 if (sp->ref)
327 continue;
328 if ((cp = strchr(tp->pattern->pattern_name, ':')))
329 cp++;
330 else
331 cp = tp->pattern->pattern_name;
332 if (sp->pattern->pattern_name)
333 free(sp->pattern->pattern_name);
334 sp->pattern->pattern_name = strdup(cp);
335 }
336 fputs("\n", ofp);
337 }
338
339 #ifdef COALESCE
340 /*
341 * Coalesce unnamed blobs with bounding rectangles that nearly touch.
342 * This way we get an output report with fewer tiny "junk" blobs.
343 */
344 #define NEAR 2
345 #define LAP(s1, e1, s2, e2) ((((s2)+NEAR <= (e1)-NEAR) && ((e2)+NEAR >= (s1)-NEAR)) \
346 || (((s1)+NEAR <= (e2)-NEAR) && ((e1)+NEAR >= (s2)-NEAR)))
347 do {
348 i = 0;
349 for (sp = scene; sp < scene + blobcount; sp++)
350 if (sp->refcount > 0 && !sp->pattern->pattern_name)
351 for (tp = scene; tp < sp; tp++)
352 if (tp->refcount > 0 && !tp->pattern->pattern_name)
353 if (LAP(sp->pattern->box.min.x,
354 sp->pattern->box.max.x,
355 tp->pattern->box.min.x,
356 tp->pattern->box.max.x)
357 && LAP(sp->pattern->box.min.y,
358 sp->pattern->box.max.y,
359 tp->pattern->box.min.y,
360 tp->pattern->box.max.y)) {
361 int state, dx, dy;
362 tile *ptr;
363
364 FOR_CELLS(sp->pattern, ptr, dx, dy)
365 if ((state=getcell(&ptr->cells, dx, dy))) {
366 chgcell(tp->pattern, ptr->x+dx, ptr->y+dy, state);
367 chgcell(sp->pattern, ptr->x+dx, ptr->y+dy, 0);
368 }
369 sp->refcount--;
370 i++;
371 }
372 } while
373 (i);
374 #undef LAP
375 #endif /* COALESCE */
376
377 /* name the unnamed blobs */
378 nonrefcount = 0;
379 for (sp = scene; sp < scene + blobcount; sp++)
380 if (!sp->ref && !sp->pattern->pattern_name) {
381 char namebuf[10];
382
383 sprintf(namebuf, "part%d", ++nonrefcount);
384 sp->pattern->pattern_name = strdup(namebuf);
385 }
386
387 /* emit the blob list */
388 for (sp = scene; sp < scene + blobcount; sp++) {
389 #ifdef COALESCE
390 if (!sp->refcount)
391 continue;
392 #endif /* COALESCE */
393 if (!sp->ref) {
394 fprintf(ofp, "#B %s\n", sp->pattern->pattern_name);
395 savesimple(sp->pattern, 0, 0, ofp);
396 fputs("#E\n\n", ofp);
397 }
398 }
399 /* issue the inclusion list */
400 fprintf(ofp, "#C %d blobs\n", blobcount);
401 for (sp = scene; sp < scene + blobcount; sp++) {
402 #ifdef COALESCE
403 if (!sp->refcount)
404 continue;
405 #endif /* COALESCE */
406 if (sp->ref)
407 tp = sp->ref;
408 else
409 tp = sp;
410 fprintf(ofp, "#I :%s\t%4d %4d %d %2d 0\n",
411 tp->pattern->pattern_name,
412 sp->where.xtrans - STARTX,
413 sp->where.ytrans - STARTY,
414 sp->where.rotation,
415 sp->where.flip);
416 }
417 free(parts);
418 }
419