diff options
author | Franklin Wei <franklin@rockbox.org> | 2024-07-22 21:43:25 -0400 |
---|---|---|
committer | Franklin Wei <franklin@rockbox.org> | 2024-07-22 21:44:08 -0400 |
commit | 09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c (patch) | |
tree | 182bd4efb2dc8ca4fcb369d8cccab0c0f290d054 /apps/plugins/puzzles/src/grid.c | |
parent | c72030f98c953a82ed6f5c7132ad000c3d5f4a16 (diff) | |
download | rockbox-09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c.tar.gz rockbox-09aa8de52cb962f1ceebfb1fd44f2c54a924fc5c.zip |
puzzles: resync with upstream
This brings the puzzles source in sync with Simon's branch, commit fd304c5
(from March 2024), with some added Rockbox-specific compatibility changes:
https://www.franklinwei.com/git/puzzles/commit/?h=rockbox-devel&id=516830d9d76bdfe64fe5ccf2a9b59c33f5c7c078
There are quite a lot of backend changes, including a new "Mosaic" puzzle.
In addition, some new frontend changes were necessary:
- New "Preferences" menu to access the user preferences system.
- Enabled spacebar input for several games.
Change-Id: I94c7df674089c92f32d5f07025f6a1059068af1e
Diffstat (limited to 'apps/plugins/puzzles/src/grid.c')
-rw-r--r-- | apps/plugins/puzzles/src/grid.c | 1357 |
1 files changed, 1029 insertions, 328 deletions
diff --git a/apps/plugins/puzzles/src/grid.c b/apps/plugins/puzzles/src/grid.c index 5ea37439d4..04bb8a36cd 100644 --- a/apps/plugins/puzzles/src/grid.c +++ b/apps/plugins/puzzles/src/grid.c | |||
@@ -11,13 +11,21 @@ | |||
11 | #include <string.h> | 11 | #include <string.h> |
12 | #include <assert.h> | 12 | #include <assert.h> |
13 | #include <ctype.h> | 13 | #include <ctype.h> |
14 | #include <math.h> | ||
15 | #include <float.h> | 14 | #include <float.h> |
15 | #include <limits.h> | ||
16 | #ifdef NO_TGMATH_H | ||
17 | # include <math.h> | ||
18 | #else | ||
19 | # include <tgmath.h> | ||
20 | #endif | ||
16 | 21 | ||
17 | #include "puzzles.h" | 22 | #include "puzzles.h" |
18 | #include "tree234.h" | 23 | #include "tree234.h" |
19 | #include "grid.h" | 24 | #include "grid.h" |
25 | #include "penrose-legacy.h" | ||
20 | #include "penrose.h" | 26 | #include "penrose.h" |
27 | #include "hat.h" | ||
28 | #include "spectre.h" | ||
21 | 29 | ||
22 | /* Debugging options */ | 30 | /* Debugging options */ |
23 | 31 | ||
@@ -36,12 +44,17 @@ void grid_free(grid *g) | |||
36 | if (g->refcount == 0) { | 44 | if (g->refcount == 0) { |
37 | int i; | 45 | int i; |
38 | for (i = 0; i < g->num_faces; i++) { | 46 | for (i = 0; i < g->num_faces; i++) { |
39 | sfree(g->faces[i].dots); | 47 | sfree(g->faces[i]->dots); |
40 | sfree(g->faces[i].edges); | 48 | sfree(g->faces[i]->edges); |
49 | sfree(g->faces[i]); | ||
41 | } | 50 | } |
42 | for (i = 0; i < g->num_dots; i++) { | 51 | for (i = 0; i < g->num_dots; i++) { |
43 | sfree(g->dots[i].faces); | 52 | sfree(g->dots[i]->faces); |
44 | sfree(g->dots[i].edges); | 53 | sfree(g->dots[i]->edges); |
54 | sfree(g->dots[i]); | ||
55 | } | ||
56 | for (i = 0; i < g->num_edges; i++) { | ||
57 | sfree(g->edges[i]); | ||
45 | } | 58 | } |
46 | sfree(g->faces); | 59 | sfree(g->faces); |
47 | sfree(g->edges); | 60 | sfree(g->edges); |
@@ -59,6 +72,7 @@ static grid *grid_empty(void) | |||
59 | g->edges = NULL; | 72 | g->edges = NULL; |
60 | g->dots = NULL; | 73 | g->dots = NULL; |
61 | g->num_faces = g->num_edges = g->num_dots = 0; | 74 | g->num_faces = g->num_edges = g->num_dots = 0; |
75 | g->size_faces = g->size_edges = g->size_dots = 0; | ||
62 | g->refcount = 1; | 76 | g->refcount = 1; |
63 | g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0; | 77 | g->lowest_x = g->lowest_y = g->highest_x = g->highest_y = 0; |
64 | return g; | 78 | return g; |
@@ -116,7 +130,7 @@ grid_edge *grid_nearest_edge(grid *g, int x, int y) | |||
116 | best_edge = NULL; | 130 | best_edge = NULL; |
117 | 131 | ||
118 | for (i = 0; i < g->num_edges; i++) { | 132 | for (i = 0; i < g->num_edges; i++) { |
119 | grid_edge *e = &g->edges[i]; | 133 | grid_edge *e = g->edges[i]; |
120 | long e2; /* squared length of edge */ | 134 | long e2; /* squared length of edge */ |
121 | long a2, b2; /* squared lengths of other sides */ | 135 | long a2, b2; /* squared lengths of other sides */ |
122 | double dist; | 136 | double dist; |
@@ -185,7 +199,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); | |||
185 | if (which & SVG_FACES) { | 199 | if (which & SVG_FACES) { |
186 | fprintf(fp, "<g>\n"); | 200 | fprintf(fp, "<g>\n"); |
187 | for (i = 0; i < g->num_faces; i++) { | 201 | for (i = 0; i < g->num_faces; i++) { |
188 | grid_face *f = g->faces + i; | 202 | grid_face *f = g->faces[i]; |
189 | fprintf(fp, "<polygon points=\""); | 203 | fprintf(fp, "<polygon points=\""); |
190 | for (j = 0; j < f->order; j++) { | 204 | for (j = 0; j < f->order; j++) { |
191 | grid_dot *d = f->dots[j]; | 205 | grid_dot *d = f->dots[j]; |
@@ -200,7 +214,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); | |||
200 | if (which & SVG_EDGES) { | 214 | if (which & SVG_EDGES) { |
201 | fprintf(fp, "<g>\n"); | 215 | fprintf(fp, "<g>\n"); |
202 | for (i = 0; i < g->num_edges; i++) { | 216 | for (i = 0; i < g->num_edges; i++) { |
203 | grid_edge *e = g->edges + i; | 217 | grid_edge *e = g->edges[i]; |
204 | grid_dot *d1 = e->dot1, *d2 = e->dot2; | 218 | grid_dot *d1 = e->dot1, *d2 = e->dot2; |
205 | 219 | ||
206 | fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" " | 220 | fprintf(fp, "<line x1=\"%d\" y1=\"%d\" x2=\"%d\" y2=\"%d\" " |
@@ -213,7 +227,7 @@ xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n"); | |||
213 | if (which & SVG_DOTS) { | 227 | if (which & SVG_DOTS) { |
214 | fprintf(fp, "<g>\n"); | 228 | fprintf(fp, "<g>\n"); |
215 | for (i = 0; i < g->num_dots; i++) { | 229 | for (i = 0; i < g->num_dots; i++) { |
216 | grid_dot *d = g->dots + i; | 230 | grid_dot *d = g->dots[i]; |
217 | fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />", | 231 | fprintf(fp, "<ellipse cx=\"%d\" cy=\"%d\" rx=\"%d\" ry=\"%d\" fill=\"%s\" />", |
218 | d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR); | 232 | d->x, d->y, g->tilesize/20, g->tilesize/20, DOT_COLOUR); |
219 | } | 233 | } |
@@ -251,13 +265,17 @@ static void grid_debug_basic(grid *g) | |||
251 | #ifdef DEBUG_GRID | 265 | #ifdef DEBUG_GRID |
252 | int i; | 266 | int i; |
253 | printf("--- Basic Grid Data ---\n"); | 267 | printf("--- Basic Grid Data ---\n"); |
268 | for (i = 0; i < g->num_dots; i++) { | ||
269 | grid_dot *d = g->dots[i]; | ||
270 | printf("Dot %d at (%d,%d)\n", i, d->x, d->y); | ||
271 | } | ||
254 | for (i = 0; i < g->num_faces; i++) { | 272 | for (i = 0; i < g->num_faces; i++) { |
255 | grid_face *f = g->faces + i; | 273 | grid_face *f = g->faces[i]; |
256 | printf("Face %d: dots[", i); | 274 | printf("Face %d: dots[", i); |
257 | int j; | 275 | int j; |
258 | for (j = 0; j < f->order; j++) { | 276 | for (j = 0; j < f->order; j++) { |
259 | grid_dot *d = f->dots[j]; | 277 | grid_dot *d = f->dots[j]; |
260 | printf("%s%d", j ? "," : "", (int)(d - g->dots)); | 278 | printf("%s%d", j ? "," : "", (int)(d->index)); |
261 | } | 279 | } |
262 | printf("]\n"); | 280 | printf("]\n"); |
263 | } | 281 | } |
@@ -275,38 +293,38 @@ static void grid_debug_derived(grid *g) | |||
275 | int i; | 293 | int i; |
276 | printf("--- Derived Grid Data ---\n"); | 294 | printf("--- Derived Grid Data ---\n"); |
277 | for (i = 0; i < g->num_edges; i++) { | 295 | for (i = 0; i < g->num_edges; i++) { |
278 | grid_edge *e = g->edges + i; | 296 | grid_edge *e = g->edges[i]; |
279 | printf("Edge %d: dots[%d,%d] faces[%d,%d]\n", | 297 | printf("Edge %d: dots[%d,%d] faces[%d,%d]\n", |
280 | i, (int)(e->dot1 - g->dots), (int)(e->dot2 - g->dots), | 298 | i, (int)(e->dot1->index), (int)(e->dot2->index), |
281 | e->face1 ? (int)(e->face1 - g->faces) : -1, | 299 | e->face1 ? (int)(e->face1->index) : -1, |
282 | e->face2 ? (int)(e->face2 - g->faces) : -1); | 300 | e->face2 ? (int)(e->face2->index) : -1); |
283 | } | 301 | } |
284 | /* faces */ | 302 | /* faces */ |
285 | for (i = 0; i < g->num_faces; i++) { | 303 | for (i = 0; i < g->num_faces; i++) { |
286 | grid_face *f = g->faces + i; | 304 | grid_face *f = g->faces[i]; |
287 | int j; | 305 | int j; |
288 | printf("Face %d: faces[", i); | 306 | printf("Face %d: faces[", i); |
289 | for (j = 0; j < f->order; j++) { | 307 | for (j = 0; j < f->order; j++) { |
290 | grid_edge *e = f->edges[j]; | 308 | grid_edge *e = f->edges[j]; |
291 | grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1; | 309 | grid_face *f2 = (e->face1 == f) ? e->face2 : e->face1; |
292 | printf("%s%d", j ? "," : "", f2 ? (int)(f2 - g->faces) : -1); | 310 | printf("%s%d", j ? "," : "", f2 ? f2->index : -1); |
293 | } | 311 | } |
294 | printf("]\n"); | 312 | printf("]\n"); |
295 | } | 313 | } |
296 | /* dots */ | 314 | /* dots */ |
297 | for (i = 0; i < g->num_dots; i++) { | 315 | for (i = 0; i < g->num_dots; i++) { |
298 | grid_dot *d = g->dots + i; | 316 | grid_dot *d = g->dots[i]; |
299 | int j; | 317 | int j; |
300 | printf("Dot %d: dots[", i); | 318 | printf("Dot %d: dots[", i); |
301 | for (j = 0; j < d->order; j++) { | 319 | for (j = 0; j < d->order; j++) { |
302 | grid_edge *e = d->edges[j]; | 320 | grid_edge *e = d->edges[j]; |
303 | grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1; | 321 | grid_dot *d2 = (e->dot1 == d) ? e->dot2 : e->dot1; |
304 | printf("%s%d", j ? "," : "", (int)(d2 - g->dots)); | 322 | printf("%s%d", j ? "," : "", d2->index); |
305 | } | 323 | } |
306 | printf("] faces["); | 324 | printf("] faces["); |
307 | for (j = 0; j < d->order; j++) { | 325 | for (j = 0; j < d->order; j++) { |
308 | grid_face *f = d->faces[j]; | 326 | grid_face *f = d->faces[j]; |
309 | printf("%s%d", j ? "," : "", f ? (int)(f - g->faces) : -1); | 327 | printf("%s%d", j ? "," : "", f ? f->index : -1); |
310 | } | 328 | } |
311 | printf("]\n"); | 329 | printf("]\n"); |
312 | } | 330 | } |
@@ -324,21 +342,23 @@ static int grid_edge_bydots_cmpfn(void *v1, void *v2) | |||
324 | grid_edge *b = v2; | 342 | grid_edge *b = v2; |
325 | grid_dot *da, *db; | 343 | grid_dot *da, *db; |
326 | 344 | ||
327 | /* Pointer subtraction is valid here, because all dots point into the | 345 | /* Edges are not "normalised" - the 2 dots could be stored in any order, |
328 | * same dot-list (g->dots). | ||
329 | * Edges are not "normalised" - the 2 dots could be stored in any order, | ||
330 | * so we need to take this into account when comparing edges. */ | 346 | * so we need to take this into account when comparing edges. */ |
331 | 347 | ||
332 | /* Compare first dots */ | 348 | /* Compare first dots */ |
333 | da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2; | 349 | da = (a->dot1 < a->dot2) ? a->dot1 : a->dot2; |
334 | db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2; | 350 | db = (b->dot1 < b->dot2) ? b->dot1 : b->dot2; |
335 | if (da != db) | 351 | if (da->index < db->index) |
336 | return db - da; | 352 | return -1; |
353 | if (da->index > db->index) | ||
354 | return +1; | ||
337 | /* Compare last dots */ | 355 | /* Compare last dots */ |
338 | da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1; | 356 | da = (a->dot1 < a->dot2) ? a->dot2 : a->dot1; |
339 | db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1; | 357 | db = (b->dot1 < b->dot2) ? b->dot2 : b->dot1; |
340 | if (da != db) | 358 | if (da->index < db->index) |
341 | return db - da; | 359 | return -1; |
360 | if (da->index > db->index) | ||
361 | return +1; | ||
342 | 362 | ||
343 | return 0; | 363 | return 0; |
344 | } | 364 | } |
@@ -358,7 +378,7 @@ static int grid_edge_bydots_cmpfn(void *v1, void *v2) | |||
358 | static void grid_trim_vigorously(grid *g) | 378 | static void grid_trim_vigorously(grid *g) |
359 | { | 379 | { |
360 | int *dotpairs, *faces, *dots; | 380 | int *dotpairs, *faces, *dots; |
361 | int *dsf; | 381 | DSF *dsf; |
362 | int i, j, k, size, newfaces, newdots; | 382 | int i, j, k, size, newfaces, newdots; |
363 | 383 | ||
364 | /* | 384 | /* |
@@ -371,10 +391,10 @@ static void grid_trim_vigorously(grid *g) | |||
371 | for (j = 0; j < g->num_dots; j++) | 391 | for (j = 0; j < g->num_dots; j++) |
372 | dotpairs[i*g->num_dots+j] = -1; | 392 | dotpairs[i*g->num_dots+j] = -1; |
373 | for (i = 0; i < g->num_faces; i++) { | 393 | for (i = 0; i < g->num_faces; i++) { |
374 | grid_face *f = g->faces + i; | 394 | grid_face *f = g->faces[i]; |
375 | int dot0 = f->dots[f->order-1] - g->dots; | 395 | int dot0 = f->dots[f->order-1]->index; |
376 | for (j = 0; j < f->order; j++) { | 396 | for (j = 0; j < f->order; j++) { |
377 | int dot1 = f->dots[j] - g->dots; | 397 | int dot1 = f->dots[j]->index; |
378 | dotpairs[dot0 * g->num_dots + dot1] = i; | 398 | dotpairs[dot0 * g->num_dots + dot1] = i; |
379 | dot0 = dot1; | 399 | dot0 = dot1; |
380 | } | 400 | } |
@@ -398,7 +418,7 @@ static void grid_trim_vigorously(grid *g) | |||
398 | * Now identify connected pairs of landlocked dots, and form a dsf | 418 | * Now identify connected pairs of landlocked dots, and form a dsf |
399 | * unifying them. | 419 | * unifying them. |
400 | */ | 420 | */ |
401 | dsf = snew_dsf(g->num_dots); | 421 | dsf = dsf_new(g->num_dots); |
402 | for (i = 0; i < g->num_dots; i++) | 422 | for (i = 0; i < g->num_dots; i++) |
403 | for (j = 0; j < i; j++) | 423 | for (j = 0; j < i; j++) |
404 | if (dots[i] && dots[j] && | 424 | if (dots[i] && dots[j] && |
@@ -434,60 +454,52 @@ static void grid_trim_vigorously(grid *g) | |||
434 | for (i = 0; i < g->num_dots; i++) | 454 | for (i = 0; i < g->num_dots; i++) |
435 | dots[i] = 0; | 455 | dots[i] = 0; |
436 | for (i = 0; i < g->num_faces; i++) { | 456 | for (i = 0; i < g->num_faces; i++) { |
437 | grid_face *f = g->faces + i; | 457 | grid_face *f = g->faces[i]; |
438 | bool keep = false; | 458 | bool keep = false; |
439 | for (k = 0; k < f->order; k++) | 459 | for (k = 0; k < f->order; k++) |
440 | if (dsf_canonify(dsf, f->dots[k] - g->dots) == j) | 460 | if (dsf_canonify(dsf, f->dots[k]->index) == j) |
441 | keep = true; | 461 | keep = true; |
442 | if (keep) { | 462 | if (keep) { |
443 | faces[i] = 1; | 463 | faces[i] = 1; |
444 | for (k = 0; k < f->order; k++) | 464 | for (k = 0; k < f->order; k++) |
445 | dots[f->dots[k]-g->dots] = 1; | 465 | dots[f->dots[k]->index] = 1; |
446 | } | 466 | } |
447 | } | 467 | } |
448 | 468 | ||
449 | /* | 469 | /* |
450 | * Work out the new indices of those faces and dots, when we | 470 | * Compact the faces array, rewriting the faces' indices and |
451 | * compact the arrays containing them. | 471 | * freeing the unwanted ones. |
452 | */ | ||
453 | for (i = newfaces = 0; i < g->num_faces; i++) | ||
454 | faces[i] = (faces[i] ? newfaces++ : -1); | ||
455 | for (i = newdots = 0; i < g->num_dots; i++) | ||
456 | dots[i] = (dots[i] ? newdots++ : -1); | ||
457 | |||
458 | /* | ||
459 | * Free the dynamically allocated 'dots' pointer lists in faces | ||
460 | * we're going to discard. | ||
461 | */ | 472 | */ |
462 | for (i = 0; i < g->num_faces; i++) | 473 | for (i = newfaces = 0; i < g->num_faces; i++) { |
463 | if (faces[i] < 0) | 474 | grid_face *f = g->faces[i]; |
464 | sfree(g->faces[i].dots); | 475 | if (faces[i]) { |
476 | f->index = newfaces++; | ||
477 | g->faces[f->index] = f; | ||
478 | } else { | ||
479 | sfree(f->dots); | ||
480 | sfree(f); | ||
481 | } | ||
482 | } | ||
483 | g->num_faces = newfaces; | ||
465 | 484 | ||
466 | /* | 485 | /* |
467 | * Go through and compact the arrays. | 486 | * Compact the dots array, similarly. |
468 | */ | 487 | */ |
469 | for (i = 0; i < g->num_dots; i++) | 488 | for (i = newdots = 0; i < g->num_dots; i++) { |
470 | if (dots[i] >= 0) { | 489 | grid_dot *d = g->dots[i]; |
471 | grid_dot *dnew = g->dots + dots[i], *dold = g->dots + i; | 490 | if (dots[i]) { |
472 | *dnew = *dold; /* structure copy */ | 491 | d->index = newdots++; |
473 | } | 492 | g->dots[d->index] = d; |
474 | for (i = 0; i < g->num_faces; i++) | 493 | } else { |
475 | if (faces[i] >= 0) { | 494 | sfree(d->edges); |
476 | grid_face *fnew = g->faces + faces[i], *fold = g->faces + i; | 495 | sfree(d->faces); |
477 | *fnew = *fold; /* structure copy */ | 496 | sfree(d); |
478 | for (j = 0; j < fnew->order; j++) { | ||
479 | /* | ||
480 | * Reindex the dots in this face. | ||
481 | */ | ||
482 | k = fnew->dots[j] - g->dots; | ||
483 | fnew->dots[j] = g->dots + dots[k]; | ||
484 | } | ||
485 | } | 497 | } |
486 | g->num_faces = newfaces; | 498 | } |
487 | g->num_dots = newdots; | 499 | g->num_dots = newdots; |
488 | 500 | ||
489 | sfree(dotpairs); | 501 | sfree(dotpairs); |
490 | sfree(dsf); | 502 | dsf_free(dsf); |
491 | sfree(dots); | 503 | sfree(dots); |
492 | sfree(faces); | 504 | sfree(faces); |
493 | } | 505 | } |
@@ -505,7 +517,6 @@ static void grid_make_consistent(grid *g) | |||
505 | { | 517 | { |
506 | int i; | 518 | int i; |
507 | tree234 *incomplete_edges; | 519 | tree234 *incomplete_edges; |
508 | grid_edge *next_new_edge; /* Where new edge will go into g->edges */ | ||
509 | 520 | ||
510 | grid_debug_basic(g); | 521 | grid_debug_basic(g); |
511 | 522 | ||
@@ -513,14 +524,6 @@ static void grid_make_consistent(grid *g) | |||
513 | * Generate edges | 524 | * Generate edges |
514 | */ | 525 | */ |
515 | 526 | ||
516 | /* We know how many dots and faces there are, so we can find the exact | ||
517 | * number of edges from Euler's polyhedral formula: F + V = E + 2 . | ||
518 | * We use "-1", not "-2" here, because Euler's formula includes the | ||
519 | * infinite face, which we don't count. */ | ||
520 | g->num_edges = g->num_faces + g->num_dots - 1; | ||
521 | g->edges = snewn(g->num_edges, grid_edge); | ||
522 | next_new_edge = g->edges; | ||
523 | |||
524 | /* Iterate over faces, and over each face's dots, generating edges as we | 527 | /* Iterate over faces, and over each face's dots, generating edges as we |
525 | * go. As we find each new edge, we can immediately fill in the edge's | 528 | * go. As we find each new edge, we can immediately fill in the edge's |
526 | * dots, but only one of the edge's faces. Later on in the iteration, we | 529 | * dots, but only one of the edge's faces. Later on in the iteration, we |
@@ -530,7 +533,7 @@ static void grid_make_consistent(grid *g) | |||
530 | * their dots. */ | 533 | * their dots. */ |
531 | incomplete_edges = newtree234(grid_edge_bydots_cmpfn); | 534 | incomplete_edges = newtree234(grid_edge_bydots_cmpfn); |
532 | for (i = 0; i < g->num_faces; i++) { | 535 | for (i = 0; i < g->num_faces; i++) { |
533 | grid_face *f = g->faces + i; | 536 | grid_face *f = g->faces[i]; |
534 | int j; | 537 | int j; |
535 | for (j = 0; j < f->order; j++) { | 538 | for (j = 0; j < f->order; j++) { |
536 | grid_edge e; /* fake edge for searching */ | 539 | grid_edge e; /* fake edge for searching */ |
@@ -548,18 +551,28 @@ static void grid_make_consistent(grid *g) | |||
548 | * Edge is already removed from incomplete_edges. */ | 551 | * Edge is already removed from incomplete_edges. */ |
549 | edge_found->face2 = f; | 552 | edge_found->face2 = f; |
550 | } else { | 553 | } else { |
551 | assert(next_new_edge - g->edges < g->num_edges); | 554 | grid_edge *new_edge = snew(grid_edge); |
552 | next_new_edge->dot1 = e.dot1; | 555 | new_edge->dot1 = e.dot1; |
553 | next_new_edge->dot2 = e.dot2; | 556 | new_edge->dot2 = e.dot2; |
554 | next_new_edge->face1 = f; | 557 | new_edge->face1 = f; |
555 | next_new_edge->face2 = NULL; /* potentially infinite face */ | 558 | new_edge->face2 = NULL; /* potentially infinite face */ |
556 | add234(incomplete_edges, next_new_edge); | 559 | add234(incomplete_edges, new_edge); |
557 | ++next_new_edge; | 560 | |
561 | /* And add it to g->edges. */ | ||
562 | if (g->num_edges >= g->size_edges) { | ||
563 | int increment = g->num_edges / 4 + 128; | ||
564 | g->size_edges = (increment < INT_MAX - g->num_edges ? | ||
565 | g->num_edges + increment : INT_MAX); | ||
566 | g->edges = sresize(g->edges, g->size_edges, grid_edge *); | ||
567 | } | ||
568 | assert(g->num_edges < INT_MAX); | ||
569 | new_edge->index = g->num_edges++; | ||
570 | g->edges[new_edge->index] = new_edge; | ||
558 | } | 571 | } |
559 | } | 572 | } |
560 | } | 573 | } |
561 | freetree234(incomplete_edges); | 574 | freetree234(incomplete_edges); |
562 | 575 | ||
563 | /* ====== Stage 2 ====== | 576 | /* ====== Stage 2 ====== |
564 | * For each face, build its edge list. | 577 | * For each face, build its edge list. |
565 | */ | 578 | */ |
@@ -567,7 +580,7 @@ static void grid_make_consistent(grid *g) | |||
567 | /* Allocate space for each edge list. Can do this, because each face's | 580 | /* Allocate space for each edge list. Can do this, because each face's |
568 | * edge-list is the same size as its dot-list. */ | 581 | * edge-list is the same size as its dot-list. */ |
569 | for (i = 0; i < g->num_faces; i++) { | 582 | for (i = 0; i < g->num_faces; i++) { |
570 | grid_face *f = g->faces + i; | 583 | grid_face *f = g->faces[i]; |
571 | int j; | 584 | int j; |
572 | f->edges = snewn(f->order, grid_edge*); | 585 | f->edges = snewn(f->order, grid_edge*); |
573 | /* Preload with NULLs, to help detect potential bugs. */ | 586 | /* Preload with NULLs, to help detect potential bugs. */ |
@@ -579,7 +592,7 @@ static void grid_make_consistent(grid *g) | |||
579 | * the face's edge-list, after finding where it should go in the | 592 | * the face's edge-list, after finding where it should go in the |
580 | * sequence. */ | 593 | * sequence. */ |
581 | for (i = 0; i < g->num_edges; i++) { | 594 | for (i = 0; i < g->num_edges; i++) { |
582 | grid_edge *e = g->edges + i; | 595 | grid_edge *e = g->edges[i]; |
583 | int j; | 596 | int j; |
584 | for (j = 0; j < 2; j++) { | 597 | for (j = 0; j < 2; j++) { |
585 | grid_face *f = j ? e->face2 : e->face1; | 598 | grid_face *f = j ? e->face2 : e->face1; |
@@ -641,16 +654,16 @@ static void grid_make_consistent(grid *g) | |||
641 | * allocate the right space for these lists. Pre-compute the sizes by | 654 | * allocate the right space for these lists. Pre-compute the sizes by |
642 | * iterating over each edge and recording a tally against each dot. */ | 655 | * iterating over each edge and recording a tally against each dot. */ |
643 | for (i = 0; i < g->num_dots; i++) { | 656 | for (i = 0; i < g->num_dots; i++) { |
644 | g->dots[i].order = 0; | 657 | g->dots[i]->order = 0; |
645 | } | 658 | } |
646 | for (i = 0; i < g->num_edges; i++) { | 659 | for (i = 0; i < g->num_edges; i++) { |
647 | grid_edge *e = g->edges + i; | 660 | grid_edge *e = g->edges[i]; |
648 | ++(e->dot1->order); | 661 | ++(e->dot1->order); |
649 | ++(e->dot2->order); | 662 | ++(e->dot2->order); |
650 | } | 663 | } |
651 | /* Now we have the sizes, pre-allocate the edge and face lists. */ | 664 | /* Now we have the sizes, pre-allocate the edge and face lists. */ |
652 | for (i = 0; i < g->num_dots; i++) { | 665 | for (i = 0; i < g->num_dots; i++) { |
653 | grid_dot *d = g->dots + i; | 666 | grid_dot *d = g->dots[i]; |
654 | int j; | 667 | int j; |
655 | assert(d->order >= 2); /* sanity check */ | 668 | assert(d->order >= 2); /* sanity check */ |
656 | d->edges = snewn(d->order, grid_edge*); | 669 | d->edges = snewn(d->order, grid_edge*); |
@@ -663,7 +676,7 @@ static void grid_make_consistent(grid *g) | |||
663 | /* For each dot, need to find a face that touches it, so we can seed | 676 | /* For each dot, need to find a face that touches it, so we can seed |
664 | * the edge-face-edge-face process around each dot. */ | 677 | * the edge-face-edge-face process around each dot. */ |
665 | for (i = 0; i < g->num_faces; i++) { | 678 | for (i = 0; i < g->num_faces; i++) { |
666 | grid_face *f = g->faces + i; | 679 | grid_face *f = g->faces[i]; |
667 | int j; | 680 | int j; |
668 | for (j = 0; j < f->order; j++) { | 681 | for (j = 0; j < f->order; j++) { |
669 | grid_dot *d = f->dots[j]; | 682 | grid_dot *d = f->dots[j]; |
@@ -677,7 +690,7 @@ static void grid_make_consistent(grid *g) | |||
677 | * blocks progress. But there's only one such face, so we will | 690 | * blocks progress. But there's only one such face, so we will |
678 | * succeed in finding every edge and face this way. */ | 691 | * succeed in finding every edge and face this way. */ |
679 | for (i = 0; i < g->num_dots; i++) { | 692 | for (i = 0; i < g->num_dots; i++) { |
680 | grid_dot *d = g->dots + i; | 693 | grid_dot *d = g->dots[i]; |
681 | int current_face1 = 0; /* ascends clockwise */ | 694 | int current_face1 = 0; /* ascends clockwise */ |
682 | int current_face2 = 0; /* descends anticlockwise */ | 695 | int current_face2 = 0; /* descends anticlockwise */ |
683 | 696 | ||
@@ -774,7 +787,7 @@ static void grid_make_consistent(grid *g) | |||
774 | 787 | ||
775 | /* Bounding rectangle */ | 788 | /* Bounding rectangle */ |
776 | for (i = 0; i < g->num_dots; i++) { | 789 | for (i = 0; i < g->num_dots; i++) { |
777 | grid_dot *d = g->dots + i; | 790 | grid_dot *d = g->dots[i]; |
778 | if (i == 0) { | 791 | if (i == 0) { |
779 | g->lowest_x = g->highest_x = d->x; | 792 | g->lowest_x = g->highest_x = d->x; |
780 | g->lowest_y = g->highest_y = d->y; | 793 | g->lowest_y = g->highest_y = d->y; |
@@ -802,36 +815,52 @@ static int grid_point_cmp_fn(void *v1, void *v2) | |||
802 | else | 815 | else |
803 | return p2->x - p1->x; | 816 | return p2->x - p1->x; |
804 | } | 817 | } |
805 | /* Add a new face to the grid, with its dot list allocated. | 818 | /* Add a new face to the grid, with its dot list allocated. */ |
806 | * Assumes there's enough space allocated for the new face in grid->faces */ | ||
807 | static void grid_face_add_new(grid *g, int face_size) | 819 | static void grid_face_add_new(grid *g, int face_size) |
808 | { | 820 | { |
809 | int i; | 821 | int i; |
810 | grid_face *new_face = g->faces + g->num_faces; | 822 | grid_face *new_face = snew(grid_face); |
823 | assert(g->num_faces < INT_MAX); | ||
824 | if (g->num_faces >= g->size_faces) { | ||
825 | int increment = g->num_faces / 4 + 128; | ||
826 | g->size_faces = (increment < INT_MAX - g->num_faces ? | ||
827 | g->num_faces + increment : INT_MAX); | ||
828 | g->faces = sresize(g->faces, g->size_faces, grid_face *); | ||
829 | } | ||
830 | new_face->index = g->num_faces++; | ||
831 | g->faces[new_face->index] = new_face; | ||
832 | |||
811 | new_face->order = face_size; | 833 | new_face->order = face_size; |
812 | new_face->dots = snewn(face_size, grid_dot*); | 834 | new_face->dots = snewn(face_size, grid_dot*); |
813 | for (i = 0; i < face_size; i++) | 835 | for (i = 0; i < face_size; i++) |
814 | new_face->dots[i] = NULL; | 836 | new_face->dots[i] = NULL; |
815 | new_face->edges = NULL; | 837 | new_face->edges = NULL; |
816 | new_face->has_incentre = false; | 838 | new_face->has_incentre = false; |
817 | g->num_faces++; | ||
818 | } | 839 | } |
819 | /* Assumes dot list has enough space */ | ||
820 | static grid_dot *grid_dot_add_new(grid *g, int x, int y) | 840 | static grid_dot *grid_dot_add_new(grid *g, int x, int y) |
821 | { | 841 | { |
822 | grid_dot *new_dot = g->dots + g->num_dots; | 842 | grid_dot *new_dot = snew(grid_dot); |
843 | if (g->num_dots >= g->size_dots) { | ||
844 | int increment = g->num_dots / 4 + 128; | ||
845 | g->size_dots = (increment < INT_MAX - g->num_dots ? | ||
846 | g->num_dots + increment : INT_MAX); | ||
847 | g->dots = sresize(g->dots, g->size_dots, grid_dot *); | ||
848 | } | ||
849 | assert(g->num_dots < INT_MAX); | ||
850 | new_dot->index = g->num_dots++; | ||
851 | g->dots[new_dot->index] = new_dot; | ||
852 | |||
823 | new_dot->order = 0; | 853 | new_dot->order = 0; |
824 | new_dot->edges = NULL; | 854 | new_dot->edges = NULL; |
825 | new_dot->faces = NULL; | 855 | new_dot->faces = NULL; |
826 | new_dot->x = x; | 856 | new_dot->x = x; |
827 | new_dot->y = y; | 857 | new_dot->y = y; |
828 | g->num_dots++; | 858 | |
829 | return new_dot; | 859 | return new_dot; |
830 | } | 860 | } |
831 | /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot | 861 | /* Retrieve a dot with these (x,y) coordinates. Either return an existing dot |
832 | * in the dot_list, or add a new dot to the grid (and the dot_list) and | 862 | * in the dot_list, or add a new dot to the grid (and the dot_list) and |
833 | * return that. | 863 | * return that. */ |
834 | * Assumes g->dots has enough capacity allocated */ | ||
835 | static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) | 864 | static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) |
836 | { | 865 | { |
837 | grid_dot test, *ret; | 866 | grid_dot test, *ret; |
@@ -855,7 +884,7 @@ static grid_dot *grid_get_dot(grid *g, tree234 *dot_list, int x, int y) | |||
855 | * previously been added, with the required number of dots allocated) */ | 884 | * previously been added, with the required number of dots allocated) */ |
856 | static void grid_face_set_dot(grid *g, grid_dot *d, int position) | 885 | static void grid_face_set_dot(grid *g, grid_dot *d, int position) |
857 | { | 886 | { |
858 | grid_face *last_face = g->faces + g->num_faces - 1; | 887 | grid_face *last_face = g->faces[g->num_faces - 1]; |
859 | last_face->dots[position] = d; | 888 | last_face->dots[position] = d; |
860 | } | 889 | } |
861 | 890 | ||
@@ -1388,6 +1417,15 @@ void grid_find_incentre(grid_face *f) | |||
1388 | 1417 | ||
1389 | #define SQUARE_TILESIZE 20 | 1418 | #define SQUARE_TILESIZE 20 |
1390 | 1419 | ||
1420 | static const char *grid_validate_params_square(int width, int height) | ||
1421 | { | ||
1422 | if (width > INT_MAX / SQUARE_TILESIZE || /* xextent */ | ||
1423 | height > INT_MAX / SQUARE_TILESIZE || /* yextent */ | ||
1424 | width + 1 > INT_MAX / (height + 1)) /* max_dots */ | ||
1425 | return "Grid size must not be unreasonably large"; | ||
1426 | return NULL; | ||
1427 | } | ||
1428 | |||
1391 | static void grid_size_square(int width, int height, | 1429 | static void grid_size_square(int width, int height, |
1392 | int *tilesize, int *xextent, int *yextent) | 1430 | int *tilesize, int *xextent, int *yextent) |
1393 | { | 1431 | { |
@@ -1404,16 +1442,10 @@ static grid *grid_new_square(int width, int height, const char *desc) | |||
1404 | /* Side length */ | 1442 | /* Side length */ |
1405 | int a = SQUARE_TILESIZE; | 1443 | int a = SQUARE_TILESIZE; |
1406 | 1444 | ||
1407 | /* Upper bounds - don't have to be exact */ | ||
1408 | int max_faces = width * height; | ||
1409 | int max_dots = (width + 1) * (height + 1); | ||
1410 | |||
1411 | tree234 *points; | 1445 | tree234 *points; |
1412 | 1446 | ||
1413 | grid *g = grid_empty(); | 1447 | grid *g = grid_empty(); |
1414 | g->tilesize = a; | 1448 | g->tilesize = a; |
1415 | g->faces = snewn(max_faces, grid_face); | ||
1416 | g->dots = snewn(max_dots, grid_dot); | ||
1417 | 1449 | ||
1418 | points = newtree234(grid_point_cmp_fn); | 1450 | points = newtree234(grid_point_cmp_fn); |
1419 | 1451 | ||
@@ -1438,8 +1470,6 @@ static grid *grid_new_square(int width, int height, const char *desc) | |||
1438 | } | 1470 | } |
1439 | 1471 | ||
1440 | freetree234(points); | 1472 | freetree234(points); |
1441 | assert(g->num_faces <= max_faces); | ||
1442 | assert(g->num_dots <= max_dots); | ||
1443 | 1473 | ||
1444 | grid_make_consistent(g); | 1474 | grid_make_consistent(g); |
1445 | return g; | 1475 | return g; |
@@ -1450,6 +1480,18 @@ static grid *grid_new_square(int width, int height, const char *desc) | |||
1450 | #define HONEY_A 15 | 1480 | #define HONEY_A 15 |
1451 | #define HONEY_B 26 | 1481 | #define HONEY_B 26 |
1452 | 1482 | ||
1483 | static const char *grid_validate_params_honeycomb(int width, int height) | ||
1484 | { | ||
1485 | int a = HONEY_A; | ||
1486 | int b = HONEY_B; | ||
1487 | |||
1488 | if (width - 1 > (INT_MAX - 4*a) / (3 * a) || /* xextent */ | ||
1489 | height - 1 > (INT_MAX - 3*b) / (2 * b) || /* yextent */ | ||
1490 | width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */ | ||
1491 | return "Grid size must not be unreasonably large"; | ||
1492 | return NULL; | ||
1493 | } | ||
1494 | |||
1453 | static void grid_size_honeycomb(int width, int height, | 1495 | static void grid_size_honeycomb(int width, int height, |
1454 | int *tilesize, int *xextent, int *yextent) | 1496 | int *tilesize, int *xextent, int *yextent) |
1455 | { | 1497 | { |
@@ -1467,16 +1509,10 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc) | |||
1467 | int a = HONEY_A; | 1509 | int a = HONEY_A; |
1468 | int b = HONEY_B; | 1510 | int b = HONEY_B; |
1469 | 1511 | ||
1470 | /* Upper bounds - don't have to be exact */ | ||
1471 | int max_faces = width * height; | ||
1472 | int max_dots = 2 * (width + 1) * (height + 1); | ||
1473 | |||
1474 | tree234 *points; | 1512 | tree234 *points; |
1475 | 1513 | ||
1476 | grid *g = grid_empty(); | 1514 | grid *g = grid_empty(); |
1477 | g->tilesize = HONEY_TILESIZE; | 1515 | g->tilesize = HONEY_TILESIZE; |
1478 | g->faces = snewn(max_faces, grid_face); | ||
1479 | g->dots = snewn(max_dots, grid_dot); | ||
1480 | 1516 | ||
1481 | points = newtree234(grid_point_cmp_fn); | 1517 | points = newtree234(grid_point_cmp_fn); |
1482 | 1518 | ||
@@ -1507,8 +1543,6 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc) | |||
1507 | } | 1543 | } |
1508 | 1544 | ||
1509 | freetree234(points); | 1545 | freetree234(points); |
1510 | assert(g->num_faces <= max_faces); | ||
1511 | assert(g->num_dots <= max_dots); | ||
1512 | 1546 | ||
1513 | grid_make_consistent(g); | 1547 | grid_make_consistent(g); |
1514 | return g; | 1548 | return g; |
@@ -1519,6 +1553,18 @@ static grid *grid_new_honeycomb(int width, int height, const char *desc) | |||
1519 | #define TRIANGLE_VEC_X 15 | 1553 | #define TRIANGLE_VEC_X 15 |
1520 | #define TRIANGLE_VEC_Y 26 | 1554 | #define TRIANGLE_VEC_Y 26 |
1521 | 1555 | ||
1556 | static const char *grid_validate_params_triangular(int width, int height) | ||
1557 | { | ||
1558 | int vec_x = TRIANGLE_VEC_X; | ||
1559 | int vec_y = TRIANGLE_VEC_Y; | ||
1560 | |||
1561 | if (width > INT_MAX / (2 * vec_x) - 1 || /* xextent */ | ||
1562 | height > INT_MAX / vec_y || /* yextent */ | ||
1563 | width + 1 > INT_MAX / 4 / (height + 1)) /* max_dots */ | ||
1564 | return "Grid size must not be unreasonably large"; | ||
1565 | return NULL; | ||
1566 | } | ||
1567 | |||
1522 | static void grid_size_triangular(int width, int height, | 1568 | static void grid_size_triangular(int width, int height, |
1523 | int *tilesize, int *xextent, int *yextent) | 1569 | int *tilesize, int *xextent, int *yextent) |
1524 | { | 1570 | { |
@@ -1582,16 +1628,18 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1582 | * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e | 1628 | * 5x6t1:a022a212h1a1d1a12c2b11a012b1a20d1a0a12e |
1583 | */ | 1629 | */ |
1584 | 1630 | ||
1585 | g->num_faces = width * height * 2; | 1631 | g->num_faces = g->size_faces = width * height * 2; |
1586 | g->num_dots = (width + 1) * (height + 1); | 1632 | g->num_dots = g->size_dots = (width + 1) * (height + 1); |
1587 | g->faces = snewn(g->num_faces, grid_face); | 1633 | g->faces = snewn(g->size_faces, grid_face *); |
1588 | g->dots = snewn(g->num_dots, grid_dot); | 1634 | g->dots = snewn(g->size_dots, grid_dot *); |
1589 | 1635 | ||
1590 | /* generate dots */ | 1636 | /* generate dots */ |
1591 | index = 0; | 1637 | index = 0; |
1592 | for (y = 0; y <= height; y++) { | 1638 | for (y = 0; y <= height; y++) { |
1593 | for (x = 0; x <= width; x++) { | 1639 | for (x = 0; x <= width; x++) { |
1594 | grid_dot *d = g->dots + index; | 1640 | grid_dot *d = snew(grid_dot); |
1641 | d->index = index; | ||
1642 | g->dots[d->index] = d; | ||
1595 | /* odd rows are offset to the right */ | 1643 | /* odd rows are offset to the right */ |
1596 | d->order = 0; | 1644 | d->order = 0; |
1597 | d->edges = NULL; | 1645 | d->edges = NULL; |
@@ -1607,8 +1655,11 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1607 | for (y = 0; y < height; y++) { | 1655 | for (y = 0; y < height; y++) { |
1608 | for (x = 0; x < width; x++) { | 1656 | for (x = 0; x < width; x++) { |
1609 | /* initialise two faces for this (x,y) */ | 1657 | /* initialise two faces for this (x,y) */ |
1610 | grid_face *f1 = g->faces + index; | 1658 | grid_face *f1 = snew(grid_face), *f2 = snew(grid_face); |
1611 | grid_face *f2 = f1 + 1; | 1659 | f1->index = index; |
1660 | f2->index = index + 1; | ||
1661 | g->faces[f1->index] = f1; | ||
1662 | g->faces[f2->index] = f2; | ||
1612 | f1->edges = NULL; | 1663 | f1->edges = NULL; |
1613 | f1->order = 3; | 1664 | f1->order = 3; |
1614 | f1->dots = snewn(f1->order, grid_dot*); | 1665 | f1->dots = snewn(f1->order, grid_dot*); |
@@ -1621,19 +1672,19 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1621 | /* face descriptions depend on whether the row-number is | 1672 | /* face descriptions depend on whether the row-number is |
1622 | * odd or even */ | 1673 | * odd or even */ |
1623 | if (y % 2) { | 1674 | if (y % 2) { |
1624 | f1->dots[0] = g->dots + y * w + x; | 1675 | f1->dots[0] = g->dots[y * w + x]; |
1625 | f1->dots[1] = g->dots + (y + 1) * w + x + 1; | 1676 | f1->dots[1] = g->dots[(y + 1) * w + x + 1]; |
1626 | f1->dots[2] = g->dots + (y + 1) * w + x; | 1677 | f1->dots[2] = g->dots[(y + 1) * w + x]; |
1627 | f2->dots[0] = g->dots + y * w + x; | 1678 | f2->dots[0] = g->dots[y * w + x]; |
1628 | f2->dots[1] = g->dots + y * w + x + 1; | 1679 | f2->dots[1] = g->dots[y * w + x + 1]; |
1629 | f2->dots[2] = g->dots + (y + 1) * w + x + 1; | 1680 | f2->dots[2] = g->dots[(y + 1) * w + x + 1]; |
1630 | } else { | 1681 | } else { |
1631 | f1->dots[0] = g->dots + y * w + x; | 1682 | f1->dots[0] = g->dots[y * w + x]; |
1632 | f1->dots[1] = g->dots + y * w + x + 1; | 1683 | f1->dots[1] = g->dots[y * w + x + 1]; |
1633 | f1->dots[2] = g->dots + (y + 1) * w + x; | 1684 | f1->dots[2] = g->dots[(y + 1) * w + x]; |
1634 | f2->dots[0] = g->dots + y * w + x + 1; | 1685 | f2->dots[0] = g->dots[y * w + x + 1]; |
1635 | f2->dots[1] = g->dots + (y + 1) * w + x + 1; | 1686 | f2->dots[1] = g->dots[(y + 1) * w + x + 1]; |
1636 | f2->dots[2] = g->dots + (y + 1) * w + x; | 1687 | f2->dots[2] = g->dots[(y + 1) * w + x]; |
1637 | } | 1688 | } |
1638 | index += 2; | 1689 | index += 2; |
1639 | } | 1690 | } |
@@ -1650,12 +1701,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1650 | * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1 | 1701 | * 5x6t1:0_a1212c22c2a02a2f22a0c12a110d0e1c0c0a101121a1 |
1651 | */ | 1702 | */ |
1652 | tree234 *points = newtree234(grid_point_cmp_fn); | 1703 | tree234 *points = newtree234(grid_point_cmp_fn); |
1653 | /* Upper bounds - don't have to be exact */ | ||
1654 | int max_faces = height * (2*width+1); | ||
1655 | int max_dots = (height+1) * (width+1) * 4; | ||
1656 | |||
1657 | g->faces = snewn(max_faces, grid_face); | ||
1658 | g->dots = snewn(max_dots, grid_dot); | ||
1659 | 1704 | ||
1660 | for (y = 0; y < height; y++) { | 1705 | for (y = 0; y < height; y++) { |
1661 | /* | 1706 | /* |
@@ -1703,8 +1748,6 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1703 | } | 1748 | } |
1704 | 1749 | ||
1705 | freetree234(points); | 1750 | freetree234(points); |
1706 | assert(g->num_faces <= max_faces); | ||
1707 | assert(g->num_dots <= max_dots); | ||
1708 | } | 1751 | } |
1709 | 1752 | ||
1710 | grid_make_consistent(g); | 1753 | grid_make_consistent(g); |
@@ -1716,6 +1759,19 @@ static grid *grid_new_triangular(int width, int height, const char *desc) | |||
1716 | #define SNUBSQUARE_A 15 | 1759 | #define SNUBSQUARE_A 15 |
1717 | #define SNUBSQUARE_B 26 | 1760 | #define SNUBSQUARE_B 26 |
1718 | 1761 | ||
1762 | static const char *grid_validate_params_snubsquare(int width, int height) | ||
1763 | { | ||
1764 | int a = SNUBSQUARE_A; | ||
1765 | int b = SNUBSQUARE_B; | ||
1766 | |||
1767 | if (width-1 > (INT_MAX - (a + b)) / (a+b) || /* xextent */ | ||
1768 | height > (INT_MAX - (a + b)) / (a+b) || /* yextent */ | ||
1769 | width > INT_MAX / 3 / height || /* max_faces */ | ||
1770 | width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */ | ||
1771 | return "Grid size must not be unreasonably large"; | ||
1772 | return NULL; | ||
1773 | } | ||
1774 | |||
1719 | static void grid_size_snubsquare(int width, int height, | 1775 | static void grid_size_snubsquare(int width, int height, |
1720 | int *tilesize, int *xextent, int *yextent) | 1776 | int *tilesize, int *xextent, int *yextent) |
1721 | { | 1777 | { |
@@ -1733,16 +1789,10 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc) | |||
1733 | int a = SNUBSQUARE_A; | 1789 | int a = SNUBSQUARE_A; |
1734 | int b = SNUBSQUARE_B; | 1790 | int b = SNUBSQUARE_B; |
1735 | 1791 | ||
1736 | /* Upper bounds - don't have to be exact */ | ||
1737 | int max_faces = 3 * width * height; | ||
1738 | int max_dots = 2 * (width + 1) * (height + 1); | ||
1739 | |||
1740 | tree234 *points; | 1792 | tree234 *points; |
1741 | 1793 | ||
1742 | grid *g = grid_empty(); | 1794 | grid *g = grid_empty(); |
1743 | g->tilesize = SNUBSQUARE_TILESIZE; | 1795 | g->tilesize = SNUBSQUARE_TILESIZE; |
1744 | g->faces = snewn(max_faces, grid_face); | ||
1745 | g->dots = snewn(max_dots, grid_dot); | ||
1746 | 1796 | ||
1747 | points = newtree234(grid_point_cmp_fn); | 1797 | points = newtree234(grid_point_cmp_fn); |
1748 | 1798 | ||
@@ -1818,8 +1868,6 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc) | |||
1818 | } | 1868 | } |
1819 | 1869 | ||
1820 | freetree234(points); | 1870 | freetree234(points); |
1821 | assert(g->num_faces <= max_faces); | ||
1822 | assert(g->num_dots <= max_dots); | ||
1823 | 1871 | ||
1824 | grid_make_consistent(g); | 1872 | grid_make_consistent(g); |
1825 | return g; | 1873 | return g; |
@@ -1830,6 +1878,18 @@ static grid *grid_new_snubsquare(int width, int height, const char *desc) | |||
1830 | #define CAIRO_A 14 | 1878 | #define CAIRO_A 14 |
1831 | #define CAIRO_B 31 | 1879 | #define CAIRO_B 31 |
1832 | 1880 | ||
1881 | static const char *grid_validate_params_cairo(int width, int height) | ||
1882 | { | ||
1883 | int b = CAIRO_B; /* a unused in determining grid size. */ | ||
1884 | |||
1885 | if (width - 1 > (INT_MAX - 2*b) / (2*b) || /* xextent */ | ||
1886 | height - 1 > (INT_MAX - 2*b) / (2*b) || /* yextent */ | ||
1887 | width > INT_MAX / 2 / height || /* max_faces */ | ||
1888 | width + 1 > INT_MAX / 3 / (height + 1)) /* max_dots */ | ||
1889 | return "Grid size must not be unreasonably large"; | ||
1890 | return NULL; | ||
1891 | } | ||
1892 | |||
1833 | static void grid_size_cairo(int width, int height, | 1893 | static void grid_size_cairo(int width, int height, |
1834 | int *tilesize, int *xextent, int *yextent) | 1894 | int *tilesize, int *xextent, int *yextent) |
1835 | { | 1895 | { |
@@ -1846,16 +1906,10 @@ static grid *grid_new_cairo(int width, int height, const char *desc) | |||
1846 | int a = CAIRO_A; | 1906 | int a = CAIRO_A; |
1847 | int b = CAIRO_B; | 1907 | int b = CAIRO_B; |
1848 | 1908 | ||
1849 | /* Upper bounds - don't have to be exact */ | ||
1850 | int max_faces = 2 * width * height; | ||
1851 | int max_dots = 3 * (width + 1) * (height + 1); | ||
1852 | |||
1853 | tree234 *points; | 1909 | tree234 *points; |
1854 | 1910 | ||
1855 | grid *g = grid_empty(); | 1911 | grid *g = grid_empty(); |
1856 | g->tilesize = CAIRO_TILESIZE; | 1912 | g->tilesize = CAIRO_TILESIZE; |
1857 | g->faces = snewn(max_faces, grid_face); | ||
1858 | g->dots = snewn(max_dots, grid_dot); | ||
1859 | 1913 | ||
1860 | points = newtree234(grid_point_cmp_fn); | 1914 | points = newtree234(grid_point_cmp_fn); |
1861 | 1915 | ||
@@ -1924,8 +1978,6 @@ static grid *grid_new_cairo(int width, int height, const char *desc) | |||
1924 | } | 1978 | } |
1925 | 1979 | ||
1926 | freetree234(points); | 1980 | freetree234(points); |
1927 | assert(g->num_faces <= max_faces); | ||
1928 | assert(g->num_dots <= max_dots); | ||
1929 | 1981 | ||
1930 | grid_make_consistent(g); | 1982 | grid_make_consistent(g); |
1931 | return g; | 1983 | return g; |
@@ -1936,6 +1988,18 @@ static grid *grid_new_cairo(int width, int height, const char *desc) | |||
1936 | #define GREATHEX_A 15 | 1988 | #define GREATHEX_A 15 |
1937 | #define GREATHEX_B 26 | 1989 | #define GREATHEX_B 26 |
1938 | 1990 | ||
1991 | static const char *grid_validate_params_greathexagonal(int width, int height) | ||
1992 | { | ||
1993 | int a = GREATHEX_A; | ||
1994 | int b = GREATHEX_B; | ||
1995 | |||
1996 | if (width-1 > (INT_MAX - 4*a) / (3*a + b) || /* xextent */ | ||
1997 | height-1 > (INT_MAX - (3*b + a)) / (2*a + 2*b) || /* yextent */ | ||
1998 | width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */ | ||
1999 | return "Grid size must not be unreasonably large"; | ||
2000 | return NULL; | ||
2001 | } | ||
2002 | |||
1939 | static void grid_size_greathexagonal(int width, int height, | 2003 | static void grid_size_greathexagonal(int width, int height, |
1940 | int *tilesize, int *xextent, int *yextent) | 2004 | int *tilesize, int *xextent, int *yextent) |
1941 | { | 2005 | { |
@@ -1953,16 +2017,10 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc) | |||
1953 | int a = GREATHEX_A; | 2017 | int a = GREATHEX_A; |
1954 | int b = GREATHEX_B; | 2018 | int b = GREATHEX_B; |
1955 | 2019 | ||
1956 | /* Upper bounds - don't have to be exact */ | ||
1957 | int max_faces = 6 * (width + 1) * (height + 1); | ||
1958 | int max_dots = 6 * width * height; | ||
1959 | |||
1960 | tree234 *points; | 2020 | tree234 *points; |
1961 | 2021 | ||
1962 | grid *g = grid_empty(); | 2022 | grid *g = grid_empty(); |
1963 | g->tilesize = GREATHEX_TILESIZE; | 2023 | g->tilesize = GREATHEX_TILESIZE; |
1964 | g->faces = snewn(max_faces, grid_face); | ||
1965 | g->dots = snewn(max_dots, grid_dot); | ||
1966 | 2024 | ||
1967 | points = newtree234(grid_point_cmp_fn); | 2025 | points = newtree234(grid_point_cmp_fn); |
1968 | 2026 | ||
@@ -2054,8 +2112,6 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc) | |||
2054 | } | 2112 | } |
2055 | 2113 | ||
2056 | freetree234(points); | 2114 | freetree234(points); |
2057 | assert(g->num_faces <= max_faces); | ||
2058 | assert(g->num_dots <= max_dots); | ||
2059 | 2115 | ||
2060 | grid_make_consistent(g); | 2116 | grid_make_consistent(g); |
2061 | return g; | 2117 | return g; |
@@ -2066,6 +2122,18 @@ static grid *grid_new_greathexagonal(int width, int height, const char *desc) | |||
2066 | #define KAGOME_A 15 | 2122 | #define KAGOME_A 15 |
2067 | #define KAGOME_B 26 | 2123 | #define KAGOME_B 26 |
2068 | 2124 | ||
2125 | static const char *grid_validate_params_kagome(int width, int height) | ||
2126 | { | ||
2127 | int a = KAGOME_A; | ||
2128 | int b = KAGOME_B; | ||
2129 | |||
2130 | if (width-1 > (INT_MAX - 6*a) / (4*a) || /* xextent */ | ||
2131 | height-1 > (INT_MAX - 2*b) / (2*b) || /* yextent */ | ||
2132 | width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */ | ||
2133 | return "Grid size must not be unreasonably large"; | ||
2134 | return NULL; | ||
2135 | } | ||
2136 | |||
2069 | static void grid_size_kagome(int width, int height, | 2137 | static void grid_size_kagome(int width, int height, |
2070 | int *tilesize, int *xextent, int *yextent) | 2138 | int *tilesize, int *xextent, int *yextent) |
2071 | { | 2139 | { |
@@ -2083,16 +2151,10 @@ static grid *grid_new_kagome(int width, int height, const char *desc) | |||
2083 | int a = KAGOME_A; | 2151 | int a = KAGOME_A; |
2084 | int b = KAGOME_B; | 2152 | int b = KAGOME_B; |
2085 | 2153 | ||
2086 | /* Upper bounds - don't have to be exact */ | ||
2087 | int max_faces = 6 * (width + 1) * (height + 1); | ||
2088 | int max_dots = 6 * width * height; | ||
2089 | |||
2090 | tree234 *points; | 2154 | tree234 *points; |
2091 | 2155 | ||
2092 | grid *g = grid_empty(); | 2156 | grid *g = grid_empty(); |
2093 | g->tilesize = KAGOME_TILESIZE; | 2157 | g->tilesize = KAGOME_TILESIZE; |
2094 | g->faces = snewn(max_faces, grid_face); | ||
2095 | g->dots = snewn(max_dots, grid_dot); | ||
2096 | 2158 | ||
2097 | points = newtree234(grid_point_cmp_fn); | 2159 | points = newtree234(grid_point_cmp_fn); |
2098 | 2160 | ||
@@ -2150,8 +2212,6 @@ static grid *grid_new_kagome(int width, int height, const char *desc) | |||
2150 | } | 2212 | } |
2151 | 2213 | ||
2152 | freetree234(points); | 2214 | freetree234(points); |
2153 | assert(g->num_faces <= max_faces); | ||
2154 | assert(g->num_dots <= max_dots); | ||
2155 | 2215 | ||
2156 | grid_make_consistent(g); | 2216 | grid_make_consistent(g); |
2157 | return g; | 2217 | return g; |
@@ -2162,6 +2222,18 @@ static grid *grid_new_kagome(int width, int height, const char *desc) | |||
2162 | #define OCTAGONAL_A 29 | 2222 | #define OCTAGONAL_A 29 |
2163 | #define OCTAGONAL_B 41 | 2223 | #define OCTAGONAL_B 41 |
2164 | 2224 | ||
2225 | static const char *grid_validate_params_octagonal(int width, int height) | ||
2226 | { | ||
2227 | int a = OCTAGONAL_A; | ||
2228 | int b = OCTAGONAL_B; | ||
2229 | |||
2230 | if (width > INT_MAX / (2*a + b) || /* xextent */ | ||
2231 | height > INT_MAX / (2*a + b) || /* yextent */ | ||
2232 | height + 1 > INT_MAX / 4 / (width + 1)) /* max_dots */ | ||
2233 | return "Grid size must not be unreasonably large"; | ||
2234 | return NULL; | ||
2235 | } | ||
2236 | |||
2165 | static void grid_size_octagonal(int width, int height, | 2237 | static void grid_size_octagonal(int width, int height, |
2166 | int *tilesize, int *xextent, int *yextent) | 2238 | int *tilesize, int *xextent, int *yextent) |
2167 | { | 2239 | { |
@@ -2179,16 +2251,10 @@ static grid *grid_new_octagonal(int width, int height, const char *desc) | |||
2179 | int a = OCTAGONAL_A; | 2251 | int a = OCTAGONAL_A; |
2180 | int b = OCTAGONAL_B; | 2252 | int b = OCTAGONAL_B; |
2181 | 2253 | ||
2182 | /* Upper bounds - don't have to be exact */ | ||
2183 | int max_faces = 2 * width * height; | ||
2184 | int max_dots = 4 * (width + 1) * (height + 1); | ||
2185 | |||
2186 | tree234 *points; | 2254 | tree234 *points; |
2187 | 2255 | ||
2188 | grid *g = grid_empty(); | 2256 | grid *g = grid_empty(); |
2189 | g->tilesize = OCTAGONAL_TILESIZE; | 2257 | g->tilesize = OCTAGONAL_TILESIZE; |
2190 | g->faces = snewn(max_faces, grid_face); | ||
2191 | g->dots = snewn(max_dots, grid_dot); | ||
2192 | 2258 | ||
2193 | points = newtree234(grid_point_cmp_fn); | 2259 | points = newtree234(grid_point_cmp_fn); |
2194 | 2260 | ||
@@ -2233,8 +2299,6 @@ static grid *grid_new_octagonal(int width, int height, const char *desc) | |||
2233 | } | 2299 | } |
2234 | 2300 | ||
2235 | freetree234(points); | 2301 | freetree234(points); |
2236 | assert(g->num_faces <= max_faces); | ||
2237 | assert(g->num_dots <= max_dots); | ||
2238 | 2302 | ||
2239 | grid_make_consistent(g); | 2303 | grid_make_consistent(g); |
2240 | return g; | 2304 | return g; |
@@ -2245,6 +2309,18 @@ static grid *grid_new_octagonal(int width, int height, const char *desc) | |||
2245 | #define KITE_A 15 | 2309 | #define KITE_A 15 |
2246 | #define KITE_B 26 | 2310 | #define KITE_B 26 |
2247 | 2311 | ||
2312 | static const char *grid_validate_params_kites(int width, int height) | ||
2313 | { | ||
2314 | int a = KITE_A; | ||
2315 | int b = KITE_B; | ||
2316 | |||
2317 | if (width > (INT_MAX - 2*b) / (4*b) || /* xextent */ | ||
2318 | height - 1 > (INT_MAX - 8*a) / (6*a) || /* yextent */ | ||
2319 | width + 1 > INT_MAX / 6 / (height + 1)) /* max_dots */ | ||
2320 | return "Grid size must not be unreasonably large"; | ||
2321 | return NULL; | ||
2322 | } | ||
2323 | |||
2248 | static void grid_size_kites(int width, int height, | 2324 | static void grid_size_kites(int width, int height, |
2249 | int *tilesize, int *xextent, int *yextent) | 2325 | int *tilesize, int *xextent, int *yextent) |
2250 | { | 2326 | { |
@@ -2262,16 +2338,10 @@ static grid *grid_new_kites(int width, int height, const char *desc) | |||
2262 | int a = KITE_A; | 2338 | int a = KITE_A; |
2263 | int b = KITE_B; | 2339 | int b = KITE_B; |
2264 | 2340 | ||
2265 | /* Upper bounds - don't have to be exact */ | ||
2266 | int max_faces = 6 * width * height; | ||
2267 | int max_dots = 6 * (width + 1) * (height + 1); | ||
2268 | |||
2269 | tree234 *points; | 2341 | tree234 *points; |
2270 | 2342 | ||
2271 | grid *g = grid_empty(); | 2343 | grid *g = grid_empty(); |
2272 | g->tilesize = KITE_TILESIZE; | 2344 | g->tilesize = KITE_TILESIZE; |
2273 | g->faces = snewn(max_faces, grid_face); | ||
2274 | g->dots = snewn(max_dots, grid_dot); | ||
2275 | 2345 | ||
2276 | points = newtree234(grid_point_cmp_fn); | 2346 | points = newtree234(grid_point_cmp_fn); |
2277 | 2347 | ||
@@ -2353,8 +2423,6 @@ static grid *grid_new_kites(int width, int height, const char *desc) | |||
2353 | } | 2423 | } |
2354 | 2424 | ||
2355 | freetree234(points); | 2425 | freetree234(points); |
2356 | assert(g->num_faces <= max_faces); | ||
2357 | assert(g->num_dots <= max_dots); | ||
2358 | 2426 | ||
2359 | grid_make_consistent(g); | 2427 | grid_make_consistent(g); |
2360 | return g; | 2428 | return g; |
@@ -2367,6 +2435,20 @@ static grid *grid_new_kites(int width, int height, const char *desc) | |||
2367 | #define FLORET_PX 75 | 2435 | #define FLORET_PX 75 |
2368 | #define FLORET_PY -26 | 2436 | #define FLORET_PY -26 |
2369 | 2437 | ||
2438 | static const char *grid_validate_params_floret(int width, int height) | ||
2439 | { | ||
2440 | int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */ | ||
2441 | int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ | ||
2442 | int ry = qy-py; | ||
2443 | /* rx unused in determining grid size. */ | ||
2444 | |||
2445 | if (width - 1 > (INT_MAX - (4*qx + 2*px)) / ((6*px+3*qx)/2) ||/* xextent */ | ||
2446 | height - 1 > (INT_MAX - (4*qy + 2*ry)) / (5*qy-4*py) || /* yextent */ | ||
2447 | width + 1 > INT_MAX / 9 / (height + 1)) /* max_dots */ | ||
2448 | return "Grid size must not be unreasonably large"; | ||
2449 | return NULL; | ||
2450 | } | ||
2451 | |||
2370 | static void grid_size_floret(int width, int height, | 2452 | static void grid_size_floret(int width, int height, |
2371 | int *tilesize, int *xextent, int *yextent) | 2453 | int *tilesize, int *xextent, int *yextent) |
2372 | { | 2454 | { |
@@ -2393,16 +2475,10 @@ static grid *grid_new_floret(int width, int height, const char *desc) | |||
2393 | int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ | 2475 | int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */ |
2394 | int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */ | 2476 | int rx = qx-px, ry = qy-py; /* |(-15, 78)| = 79.38 */ |
2395 | 2477 | ||
2396 | /* Upper bounds - don't have to be exact */ | ||
2397 | int max_faces = 6 * width * height; | ||
2398 | int max_dots = 9 * (width + 1) * (height + 1); | ||
2399 | |||
2400 | tree234 *points; | 2478 | tree234 *points; |
2401 | 2479 | ||
2402 | grid *g = grid_empty(); | 2480 | grid *g = grid_empty(); |
2403 | g->tilesize = FLORET_TILESIZE; | 2481 | g->tilesize = FLORET_TILESIZE; |
2404 | g->faces = snewn(max_faces, grid_face); | ||
2405 | g->dots = snewn(max_dots, grid_dot); | ||
2406 | 2482 | ||
2407 | points = newtree234(grid_point_cmp_fn); | 2483 | points = newtree234(grid_point_cmp_fn); |
2408 | 2484 | ||
@@ -2463,8 +2539,6 @@ static grid *grid_new_floret(int width, int height, const char *desc) | |||
2463 | } | 2539 | } |
2464 | 2540 | ||
2465 | freetree234(points); | 2541 | freetree234(points); |
2466 | assert(g->num_faces <= max_faces); | ||
2467 | assert(g->num_dots <= max_dots); | ||
2468 | 2542 | ||
2469 | grid_make_consistent(g); | 2543 | grid_make_consistent(g); |
2470 | return g; | 2544 | return g; |
@@ -2476,6 +2550,18 @@ static grid *grid_new_floret(int width, int height, const char *desc) | |||
2476 | #define DODEC_A 15 | 2550 | #define DODEC_A 15 |
2477 | #define DODEC_B 26 | 2551 | #define DODEC_B 26 |
2478 | 2552 | ||
2553 | static const char *grid_validate_params_dodecagonal(int width, int height) | ||
2554 | { | ||
2555 | int a = DODEC_A; | ||
2556 | int b = DODEC_B; | ||
2557 | |||
2558 | if (width - 1 > (INT_MAX - 3*(2*a + b)) / (4*a + 2*b) || /* xextent */ | ||
2559 | height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 2*b) || /* yextent */ | ||
2560 | width > INT_MAX / 14 / height) /* max_dots */ | ||
2561 | return "Grid size must not be unreasonably large"; | ||
2562 | return NULL; | ||
2563 | } | ||
2564 | |||
2479 | static void grid_size_dodecagonal(int width, int height, | 2565 | static void grid_size_dodecagonal(int width, int height, |
2480 | int *tilesize, int *xextent, int *yextent) | 2566 | int *tilesize, int *xextent, int *yextent) |
2481 | { | 2567 | { |
@@ -2493,16 +2579,10 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc) | |||
2493 | int a = DODEC_A; | 2579 | int a = DODEC_A; |
2494 | int b = DODEC_B; | 2580 | int b = DODEC_B; |
2495 | 2581 | ||
2496 | /* Upper bounds - don't have to be exact */ | ||
2497 | int max_faces = 3 * width * height; | ||
2498 | int max_dots = 14 * width * height; | ||
2499 | |||
2500 | tree234 *points; | 2582 | tree234 *points; |
2501 | 2583 | ||
2502 | grid *g = grid_empty(); | 2584 | grid *g = grid_empty(); |
2503 | g->tilesize = DODEC_TILESIZE; | 2585 | g->tilesize = DODEC_TILESIZE; |
2504 | g->faces = snewn(max_faces, grid_face); | ||
2505 | g->dots = snewn(max_dots, grid_dot); | ||
2506 | 2586 | ||
2507 | points = newtree234(grid_point_cmp_fn); | 2587 | points = newtree234(grid_point_cmp_fn); |
2508 | 2588 | ||
@@ -2549,13 +2629,23 @@ static grid *grid_new_dodecagonal(int width, int height, const char *desc) | |||
2549 | } | 2629 | } |
2550 | 2630 | ||
2551 | freetree234(points); | 2631 | freetree234(points); |
2552 | assert(g->num_faces <= max_faces); | ||
2553 | assert(g->num_dots <= max_dots); | ||
2554 | 2632 | ||
2555 | grid_make_consistent(g); | 2633 | grid_make_consistent(g); |
2556 | return g; | 2634 | return g; |
2557 | } | 2635 | } |
2558 | 2636 | ||
2637 | static const char *grid_validate_params_greatdodecagonal(int width, int height) | ||
2638 | { | ||
2639 | int a = DODEC_A; | ||
2640 | int b = DODEC_B; | ||
2641 | |||
2642 | if (width - 1 > (INT_MAX - (2*(2*a + b) + 3*a + b)) / (6*a + 2*b) || | ||
2643 | height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 3*b) || /* yextent */ | ||
2644 | width > INT_MAX / 200 / height) /* max_dots */ | ||
2645 | return "Grid size must not be unreasonably large"; | ||
2646 | return NULL; | ||
2647 | } | ||
2648 | |||
2559 | static void grid_size_greatdodecagonal(int width, int height, | 2649 | static void grid_size_greatdodecagonal(int width, int height, |
2560 | int *tilesize, int *xextent, int *yextent) | 2650 | int *tilesize, int *xextent, int *yextent) |
2561 | { | 2651 | { |
@@ -2574,16 +2664,10 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) | |||
2574 | int a = DODEC_A; | 2664 | int a = DODEC_A; |
2575 | int b = DODEC_B; | 2665 | int b = DODEC_B; |
2576 | 2666 | ||
2577 | /* Upper bounds - don't have to be exact */ | ||
2578 | int max_faces = 30 * width * height; | ||
2579 | int max_dots = 200 * width * height; | ||
2580 | |||
2581 | tree234 *points; | 2667 | tree234 *points; |
2582 | 2668 | ||
2583 | grid *g = grid_empty(); | 2669 | grid *g = grid_empty(); |
2584 | g->tilesize = DODEC_TILESIZE; | 2670 | g->tilesize = DODEC_TILESIZE; |
2585 | g->faces = snewn(max_faces, grid_face); | ||
2586 | g->dots = snewn(max_dots, grid_dot); | ||
2587 | 2671 | ||
2588 | points = newtree234(grid_point_cmp_fn); | 2672 | points = newtree234(grid_point_cmp_fn); |
2589 | 2673 | ||
@@ -2663,13 +2747,24 @@ static grid *grid_new_greatdodecagonal(int width, int height, const char *desc) | |||
2663 | } | 2747 | } |
2664 | 2748 | ||
2665 | freetree234(points); | 2749 | freetree234(points); |
2666 | assert(g->num_faces <= max_faces); | ||
2667 | assert(g->num_dots <= max_dots); | ||
2668 | 2750 | ||
2669 | grid_make_consistent(g); | 2751 | grid_make_consistent(g); |
2670 | return g; | 2752 | return g; |
2671 | } | 2753 | } |
2672 | 2754 | ||
2755 | static const char *grid_validate_params_greatgreatdodecagonal( | ||
2756 | int width, int height) | ||
2757 | { | ||
2758 | int a = DODEC_A; | ||
2759 | int b = DODEC_B; | ||
2760 | |||
2761 | if (width-1 > (INT_MAX - (2*(2*a + b) + 2*a + 2*b)) / (4*a + 4*b) || | ||
2762 | height-1 > (INT_MAX - 2*(2*a + b)) / (6*a + 2*b) || /* yextent */ | ||
2763 | width > INT_MAX / 300 / height) /* max_dots */ | ||
2764 | return "Grid size must not be unreasonably large"; | ||
2765 | return NULL; | ||
2766 | } | ||
2767 | |||
2673 | static void grid_size_greatgreatdodecagonal(int width, int height, | 2768 | static void grid_size_greatgreatdodecagonal(int width, int height, |
2674 | int *tilesize, int *xextent, int *yextent) | 2769 | int *tilesize, int *xextent, int *yextent) |
2675 | { | 2770 | { |
@@ -2688,16 +2783,10 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d | |||
2688 | int a = DODEC_A; | 2783 | int a = DODEC_A; |
2689 | int b = DODEC_B; | 2784 | int b = DODEC_B; |
2690 | 2785 | ||
2691 | /* Upper bounds - don't have to be exact */ | ||
2692 | int max_faces = 50 * width * height; | ||
2693 | int max_dots = 300 * width * height; | ||
2694 | |||
2695 | tree234 *points; | 2786 | tree234 *points; |
2696 | 2787 | ||
2697 | grid *g = grid_empty(); | 2788 | grid *g = grid_empty(); |
2698 | g->tilesize = DODEC_TILESIZE; | 2789 | g->tilesize = DODEC_TILESIZE; |
2699 | g->faces = snewn(max_faces, grid_face); | ||
2700 | g->dots = snewn(max_dots, grid_dot); | ||
2701 | 2790 | ||
2702 | points = newtree234(grid_point_cmp_fn); | 2791 | points = newtree234(grid_point_cmp_fn); |
2703 | 2792 | ||
@@ -2747,7 +2836,7 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d | |||
2747 | d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5); | 2836 | d = grid_get_dot(g, points, px + (2*a + 2*b), py - 2*a); grid_face_set_dot(g, d, 5); |
2748 | } | 2837 | } |
2749 | 2838 | ||
2750 | /* hexagon on bottom right of dodecagon */ | 2839 | /* hexagon on bottom right of dodecagon */ |
2751 | if ((y < height - 1) && (x < width - 1 || !(y % 2))) { | 2840 | if ((y < height - 1) && (x < width - 1 || !(y % 2))) { |
2752 | grid_face_add_new(g, 6); | 2841 | grid_face_add_new(g, 6); |
2753 | d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); | 2842 | d = grid_get_dot(g, points, px + (a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); |
@@ -2832,29 +2921,165 @@ static grid *grid_new_greatgreatdodecagonal(int width, int height, const char *d | |||
2832 | } | 2921 | } |
2833 | 2922 | ||
2834 | freetree234(points); | 2923 | freetree234(points); |
2835 | assert(g->num_faces <= max_faces); | ||
2836 | assert(g->num_dots <= max_dots); | ||
2837 | 2924 | ||
2838 | grid_make_consistent(g); | 2925 | grid_make_consistent(g); |
2839 | return g; | 2926 | return g; |
2840 | } | 2927 | } |
2841 | 2928 | ||
2842 | typedef struct setface_ctx | 2929 | static const char *grid_validate_params_compassdodecagonal( |
2930 | int width, int height) | ||
2931 | { | ||
2932 | int a = DODEC_A; | ||
2933 | int b = DODEC_B; | ||
2934 | |||
2935 | if (width > INT_MAX / (4*a + 2*b) || /* xextent */ | ||
2936 | height > INT_MAX / (4*a + 2*b) || /* yextent */ | ||
2937 | width > INT_MAX / 18 / height) /* max_dots */ | ||
2938 | return "Grid must not be unreasonably large"; | ||
2939 | return NULL; | ||
2940 | } | ||
2941 | |||
2942 | static void grid_size_compassdodecagonal(int width, int height, | ||
2943 | int *tilesize, int *xextent, int *yextent) | ||
2944 | { | ||
2945 | int a = DODEC_A; | ||
2946 | int b = DODEC_B; | ||
2947 | |||
2948 | *tilesize = DODEC_TILESIZE; | ||
2949 | *xextent = (4*a + 2*b) * width; | ||
2950 | *yextent = (4*a + 2*b) * height; | ||
2951 | } | ||
2952 | |||
2953 | static grid *grid_new_compassdodecagonal(int width, int height, const char *desc) | ||
2843 | { | 2954 | { |
2955 | int x, y; | ||
2956 | /* Vector for side of triangle - ratio is close to sqrt(3) */ | ||
2957 | int a = DODEC_A; | ||
2958 | int b = DODEC_B; | ||
2959 | |||
2960 | tree234 *points; | ||
2961 | |||
2962 | grid *g = grid_empty(); | ||
2963 | g->tilesize = DODEC_TILESIZE; | ||
2964 | |||
2965 | points = newtree234(grid_point_cmp_fn); | ||
2966 | |||
2967 | for (y = 0; y < height; y++) { | ||
2968 | for (x = 0; x < width; x++) { | ||
2969 | grid_dot *d; | ||
2970 | /* centre of dodecagon */ | ||
2971 | int px = (4*a + 2*b) * x; | ||
2972 | int py = (4*a + 2*b) * y; | ||
2973 | |||
2974 | /* dodecagon */ | ||
2975 | grid_face_add_new(g, 12); | ||
2976 | d = grid_get_dot(g, points, px + ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 0); | ||
2977 | d = grid_get_dot(g, points, px + ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 1); | ||
2978 | d = grid_get_dot(g, points, px + (2*a + b), py - ( a )); grid_face_set_dot(g, d, 2); | ||
2979 | d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 3); | ||
2980 | d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 4); | ||
2981 | d = grid_get_dot(g, points, px + ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 5); | ||
2982 | d = grid_get_dot(g, points, px - ( a ), py + (2*a + b)); grid_face_set_dot(g, d, 6); | ||
2983 | d = grid_get_dot(g, points, px - ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 7); | ||
2984 | d = grid_get_dot(g, points, px - (2*a + b), py + ( a )); grid_face_set_dot(g, d, 8); | ||
2985 | d = grid_get_dot(g, points, px - (2*a + b), py - ( a )); grid_face_set_dot(g, d, 9); | ||
2986 | d = grid_get_dot(g, points, px - ( a + b), py - ( a + b)); grid_face_set_dot(g, d, 10); | ||
2987 | d = grid_get_dot(g, points, px - ( a ), py - (2*a + b)); grid_face_set_dot(g, d, 11); | ||
2988 | |||
2989 | if (x < width - 1 && y < height - 1) { | ||
2990 | /* north triangle */ | ||
2991 | grid_face_add_new(g, 3); | ||
2992 | d = grid_get_dot(g, points, px + (2*a + b), py + ( a )); grid_face_set_dot(g, d, 0); | ||
2993 | d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 1); | ||
2994 | d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 2); | ||
2995 | |||
2996 | /* east triangle */ | ||
2997 | grid_face_add_new(g, 3); | ||
2998 | d = grid_get_dot(g, points, px + (3*a + 2*b), py + (2*a + b)); grid_face_set_dot(g, d, 0); | ||
2999 | d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1); | ||
3000 | d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 2); | ||
3001 | |||
3002 | /* south triangle */ | ||
3003 | grid_face_add_new(g, 3); | ||
3004 | d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 0); | ||
3005 | d = grid_get_dot(g, points, px + (2*a + b), py + (3*a + 2*b)); grid_face_set_dot(g, d, 1); | ||
3006 | d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2); | ||
3007 | |||
3008 | /* west triangle */ | ||
3009 | grid_face_add_new(g, 3); | ||
3010 | d = grid_get_dot(g, points, px + (a + b), py + ( a + b)); grid_face_set_dot(g, d, 0); | ||
3011 | d = grid_get_dot(g, points, px + (a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1); | ||
3012 | d = grid_get_dot(g, points, px + (a ), py + (2*a + b)); grid_face_set_dot(g, d, 2); | ||
3013 | |||
3014 | /* square in center */ | ||
3015 | grid_face_add_new(g, 4); | ||
3016 | d = grid_get_dot(g, points, px + (3*a + b), py + ( a + b)); grid_face_set_dot(g, d, 0); | ||
3017 | d = grid_get_dot(g, points, px + (3*a + b), py + (3*a + b)); grid_face_set_dot(g, d, 1); | ||
3018 | d = grid_get_dot(g, points, px + ( a + b), py + (3*a + b)); grid_face_set_dot(g, d, 2); | ||
3019 | d = grid_get_dot(g, points, px + ( a + b), py + ( a + b)); grid_face_set_dot(g, d, 3); | ||
3020 | } | ||
3021 | } | ||
3022 | } | ||
3023 | |||
3024 | freetree234(points); | ||
3025 | |||
3026 | grid_make_consistent(g); | ||
3027 | return g; | ||
3028 | } | ||
3029 | |||
3030 | /* | ||
3031 | * Penrose tilings. For historical reasons, we support two totally | ||
3032 | * different generation algorithms: the legacy one is only supported | ||
3033 | * by grid_new_penrose, for backwards compatibility with game | ||
3034 | * descriptions generated before we switched. New grid generation uses | ||
3035 | * only the new system. | ||
3036 | */ | ||
3037 | |||
3038 | #define PENROSE_TILESIZE 100 | ||
3039 | |||
3040 | static const char *grid_validate_params_penrose(int width, int height) | ||
3041 | { | ||
3042 | int l = PENROSE_TILESIZE; | ||
3043 | |||
3044 | if (width > INT_MAX / l || /* xextent */ | ||
3045 | height > INT_MAX / l || /* yextent */ | ||
3046 | width > INT_MAX / (3 * 3 * 4 * height)) /* max_dots */ | ||
3047 | return "Grid must not be unreasonably large"; | ||
3048 | return NULL; | ||
3049 | } | ||
3050 | |||
3051 | static void grid_size_penrose(int width, int height, | ||
3052 | int *tilesize, int *xextent, int *yextent) | ||
3053 | { | ||
3054 | int l = PENROSE_TILESIZE; | ||
3055 | |||
3056 | *tilesize = l; | ||
3057 | *xextent = l * width; | ||
3058 | *yextent = l * height; | ||
3059 | } | ||
3060 | |||
3061 | /* | ||
3062 | * Legacy generation by selecting a patch of tiling from the expansion | ||
3063 | * of a big triangle. | ||
3064 | */ | ||
3065 | |||
3066 | typedef struct penrose_legacy_set_faces_ctx { | ||
2844 | int xmin, xmax, ymin, ymax; | 3067 | int xmin, xmax, ymin, ymax; |
2845 | 3068 | ||
2846 | grid *g; | 3069 | grid *g; |
2847 | tree234 *points; | 3070 | tree234 *points; |
2848 | } setface_ctx; | 3071 | } penrose_legacy_set_faces_ctx; |
2849 | 3072 | ||
2850 | static double round_int_nearest_away(double r) | 3073 | static double round_int_nearest_away(double r) |
2851 | { | 3074 | { |
2852 | return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); | 3075 | return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5); |
2853 | } | 3076 | } |
2854 | 3077 | ||
2855 | static int set_faces(penrose_state *state, vector *vs, int n, int depth) | 3078 | static int penrose_legacy_set_faces(penrose_legacy_state *state, vector *vs, |
3079 | int n, int depth) | ||
2856 | { | 3080 | { |
2857 | setface_ctx *sf_ctx = (setface_ctx *)state->ctx; | 3081 | penrose_legacy_set_faces_ctx *sf_ctx = |
3082 | (penrose_legacy_set_faces_ctx *)state->ctx; | ||
2858 | int i; | 3083 | int i; |
2859 | int xs[4], ys[4]; | 3084 | int xs[4], ys[4]; |
2860 | 3085 | ||
@@ -2864,7 +3089,7 @@ static int set_faces(penrose_state *state, vector *vs, int n, int depth) | |||
2864 | #endif | 3089 | #endif |
2865 | 3090 | ||
2866 | for (i = 0; i < n; i++) { | 3091 | for (i = 0; i < n; i++) { |
2867 | double tx = v_x(vs, i), ty = v_y(vs, i); | 3092 | double tx = penrose_legacy_vx(vs, i), ty = penrose_legacy_vy(vs, i); |
2868 | 3093 | ||
2869 | xs[i] = (int)round_int_nearest_away(tx); | 3094 | xs[i] = (int)round_int_nearest_away(tx); |
2870 | ys[i] = (int)round_int_nearest_away(ty); | 3095 | ys[i] = (int)round_int_nearest_away(ty); |
@@ -2875,88 +3100,24 @@ static int set_faces(penrose_state *state, vector *vs, int n, int depth) | |||
2875 | 3100 | ||
2876 | grid_face_add_new(sf_ctx->g, n); | 3101 | grid_face_add_new(sf_ctx->g, n); |
2877 | debug(("penrose: new face l=%f gen=%d...", | 3102 | debug(("penrose: new face l=%f gen=%d...", |
2878 | penrose_side_length(state->start_size, depth), depth)); | 3103 | penrose_legacy_side_length(state->start_size, depth), depth)); |
2879 | for (i = 0; i < n; i++) { | 3104 | for (i = 0; i < n; i++) { |
2880 | grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points, | 3105 | grid_dot *d = grid_get_dot(sf_ctx->g, sf_ctx->points, |
2881 | xs[i], ys[i]); | 3106 | xs[i], ys[i]); |
2882 | grid_face_set_dot(sf_ctx->g, d, i); | 3107 | grid_face_set_dot(sf_ctx->g, d, i); |
2883 | debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)", | 3108 | debug((" ... dot 0x%x (%d,%d) (was %2.2f,%2.2f)", |
2884 | d, d->x, d->y, v_x(vs, i), v_y(vs, i))); | 3109 | d, d->x, d->y, penrose_legacy_vx(vs, i), |
3110 | penrose_legacy_vy(vs, i))); | ||
2885 | } | 3111 | } |
2886 | 3112 | ||
2887 | return 0; | 3113 | return 0; |
2888 | } | 3114 | } |
2889 | 3115 | ||
2890 | #define PENROSE_TILESIZE 100 | 3116 | static grid *grid_new_penrose_legacy(int width, int height, int which, |
2891 | 3117 | const char *desc); | |
2892 | static void grid_size_penrose(int width, int height, | ||
2893 | int *tilesize, int *xextent, int *yextent) | ||
2894 | { | ||
2895 | int l = PENROSE_TILESIZE; | ||
2896 | |||
2897 | *tilesize = l; | ||
2898 | *xextent = l * width; | ||
2899 | *yextent = l * height; | ||
2900 | } | ||
2901 | |||
2902 | static grid *grid_new_penrose(int width, int height, int which, const char *desc); /* forward reference */ | ||
2903 | |||
2904 | static char *grid_new_desc_penrose(grid_type type, int width, int height, random_state *rs) | ||
2905 | { | ||
2906 | int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff; | ||
2907 | double outer_radius; | ||
2908 | int inner_radius; | ||
2909 | char gd[255]; | ||
2910 | int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); | ||
2911 | grid *g; | ||
2912 | |||
2913 | while (1) { | ||
2914 | /* We want to produce a random bit of penrose tiling, so we | ||
2915 | * calculate a random offset (within the patch that penrose.c | ||
2916 | * calculates for us) and an angle (multiple of 36) to rotate | ||
2917 | * the patch. */ | ||
2918 | |||
2919 | penrose_calculate_size(which, tilesize, width, height, | ||
2920 | &outer_radius, &startsz, &depth); | ||
2921 | |||
2922 | /* Calculate radius of (circumcircle of) patch, subtract from | ||
2923 | * radius calculated. */ | ||
2924 | inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); | ||
2925 | |||
2926 | /* Pick a random offset (the easy way: choose within outer | ||
2927 | * square, discarding while it's outside the circle) */ | ||
2928 | do { | ||
2929 | xoff = random_upto(rs, 2*inner_radius) - inner_radius; | ||
2930 | yoff = random_upto(rs, 2*inner_radius) - inner_radius; | ||
2931 | } while (sqrt(xoff*xoff+yoff*yoff) > inner_radius); | ||
2932 | |||
2933 | aoff = random_upto(rs, 360/36) * 36; | ||
2934 | |||
2935 | debug(("grid_desc: ts %d, %dx%d patch, orad %2.2f irad %d", | ||
2936 | tilesize, width, height, outer_radius, inner_radius)); | ||
2937 | debug((" -> xoff %d yoff %d aoff %d", xoff, yoff, aoff)); | ||
2938 | |||
2939 | sprintf(gd, "G%d,%d,%d", xoff, yoff, aoff); | ||
2940 | |||
2941 | /* | ||
2942 | * Now test-generate our grid, to make sure it actually | ||
2943 | * produces something. | ||
2944 | */ | ||
2945 | g = grid_new_penrose(width, height, which, gd); | ||
2946 | if (g) { | ||
2947 | grid_free(g); | ||
2948 | break; | ||
2949 | } | ||
2950 | /* If not, go back to the top of this while loop and try again | ||
2951 | * with a different random offset. */ | ||
2952 | } | ||
2953 | |||
2954 | return dupstr(gd); | ||
2955 | } | ||
2956 | 3118 | ||
2957 | static const char *grid_validate_desc_penrose(grid_type type, | 3119 | static const char *grid_validate_desc_penrose_legacy( |
2958 | int width, int height, | 3120 | grid_type type, int width, int height, const char *desc) |
2959 | const char *desc) | ||
2960 | { | 3121 | { |
2961 | int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius; | 3122 | int tilesize = PENROSE_TILESIZE, startsz, depth, xoff, yoff, aoff, inner_radius; |
2962 | double outer_radius; | 3123 | double outer_radius; |
@@ -2966,8 +3127,8 @@ static const char *grid_validate_desc_penrose(grid_type type, | |||
2966 | if (!desc) | 3127 | if (!desc) |
2967 | return "Missing grid description string."; | 3128 | return "Missing grid description string."; |
2968 | 3129 | ||
2969 | penrose_calculate_size(which, tilesize, width, height, | 3130 | penrose_legacy_calculate_size(which, tilesize, width, height, |
2970 | &outer_radius, &startsz, &depth); | 3131 | &outer_radius, &startsz, &depth); |
2971 | inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); | 3132 | inner_radius = (int)(outer_radius - sqrt(width*width + height*height)); |
2972 | 3133 | ||
2973 | if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) | 3134 | if (sscanf(desc, "G%d,%d,%d", &xoff, &yoff, &aoff) != 3) |
@@ -2982,7 +3143,7 @@ static const char *grid_validate_desc_penrose(grid_type type, | |||
2982 | * Test-generate to ensure these parameters don't end us up with | 3143 | * Test-generate to ensure these parameters don't end us up with |
2983 | * no grid at all. | 3144 | * no grid at all. |
2984 | */ | 3145 | */ |
2985 | g = grid_new_penrose(width, height, which, desc); | 3146 | g = grid_new_penrose_legacy(width, height, which, desc); |
2986 | if (!g) | 3147 | if (!g) |
2987 | return "Patch coordinates do not identify a usable grid fragment"; | 3148 | return "Patch coordinates do not identify a usable grid fragment"; |
2988 | grid_free(g); | 3149 | grid_free(g); |
@@ -2990,40 +3151,30 @@ static const char *grid_validate_desc_penrose(grid_type type, | |||
2990 | return NULL; | 3151 | return NULL; |
2991 | } | 3152 | } |
2992 | 3153 | ||
2993 | /* | 3154 | static grid *grid_new_penrose_legacy(int width, int height, int which, |
2994 | * We're asked for a grid of a particular size, and we generate enough | 3155 | const char *desc) |
2995 | * of the tiling so we can be sure to have enough random grid from which | ||
2996 | * to pick. | ||
2997 | */ | ||
2998 | |||
2999 | static grid *grid_new_penrose(int width, int height, int which, const char *desc) | ||
3000 | { | 3156 | { |
3001 | int max_faces, max_dots, tilesize = PENROSE_TILESIZE; | 3157 | int tilesize = PENROSE_TILESIZE; |
3002 | int xsz, ysz, xoff, yoff, aoff; | 3158 | int xsz, ysz, xoff, yoff, aoff; |
3003 | double rradius; | 3159 | double rradius; |
3004 | 3160 | ||
3005 | tree234 *points; | 3161 | tree234 *points; |
3006 | grid *g; | 3162 | grid *g; |
3007 | 3163 | ||
3008 | penrose_state ps; | 3164 | penrose_legacy_state ps; |
3009 | setface_ctx sf_ctx; | 3165 | penrose_legacy_set_faces_ctx sf_ctx; |
3010 | 3166 | ||
3011 | penrose_calculate_size(which, tilesize, width, height, | 3167 | penrose_legacy_calculate_size(which, tilesize, width, height, |
3012 | &rradius, &ps.start_size, &ps.max_depth); | 3168 | &rradius, &ps.start_size, &ps.max_depth); |
3013 | 3169 | ||
3014 | debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d", | 3170 | debug(("penrose: w%d h%d, tile size %d, start size %d, depth %d", |
3015 | width, height, tilesize, ps.start_size, ps.max_depth)); | 3171 | width, height, tilesize, ps.start_size, ps.max_depth)); |
3016 | 3172 | ||
3017 | ps.new_tile = set_faces; | 3173 | ps.new_tile = penrose_legacy_set_faces; |
3018 | ps.ctx = &sf_ctx; | 3174 | ps.ctx = &sf_ctx; |
3019 | 3175 | ||
3020 | max_faces = (width*3) * (height*3); /* somewhat paranoid... */ | ||
3021 | max_dots = max_faces * 4; /* ditto... */ | ||
3022 | |||
3023 | g = grid_empty(); | 3176 | g = grid_empty(); |
3024 | g->tilesize = tilesize; | 3177 | g->tilesize = tilesize; |
3025 | g->faces = snewn(max_faces, grid_face); | ||
3026 | g->dots = snewn(max_dots, grid_dot); | ||
3027 | 3178 | ||
3028 | points = newtree234(grid_point_cmp_fn); | 3179 | points = newtree234(grid_point_cmp_fn); |
3029 | 3180 | ||
@@ -3051,11 +3202,9 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc | |||
3051 | debug(("penrose: x range (%f --> %f), y range (%f --> %f)", | 3202 | debug(("penrose: x range (%f --> %f), y range (%f --> %f)", |
3052 | sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax)); | 3203 | sf_ctx.xmin, sf_ctx.xmax, sf_ctx.ymin, sf_ctx.ymax)); |
3053 | 3204 | ||
3054 | penrose(&ps, which, aoff); | 3205 | penrose_legacy(&ps, which, aoff); |
3055 | 3206 | ||
3056 | freetree234(points); | 3207 | freetree234(points); |
3057 | assert(g->num_faces <= max_faces); | ||
3058 | assert(g->num_dots <= max_dots); | ||
3059 | 3208 | ||
3060 | debug(("penrose: %d faces total (equivalent to %d wide by %d high)", | 3209 | debug(("penrose: %d faces total (equivalent to %d wide by %d high)", |
3061 | g->num_faces, g->num_faces/height, g->num_faces/width)); | 3210 | g->num_faces, g->num_faces/height, g->num_faces/width)); |
@@ -3091,6 +3240,223 @@ static grid *grid_new_penrose(int width, int height, int which, const char *desc | |||
3091 | return g; | 3240 | return g; |
3092 | } | 3241 | } |
3093 | 3242 | ||
3243 | /* | ||
3244 | * Combinatorial-coordinate generation. | ||
3245 | * | ||
3246 | * We receive coordinates from the generator in the form of x,y pairs | ||
3247 | * each of which is an integer combination of 1 and sqrt(5), but those | ||
3248 | * pairs have different scale units in the x and y directions. The | ||
3249 | * scale units are 1/4 for x and sin(pi/5)/2 for y, which makes their | ||
3250 | * ratio equal to 2 sin(pi/5) ~= 1.1756. We fudge that irrational | ||
3251 | * aspect ratio into a rational approximation, by simply taking a pair | ||
3252 | * of integer scale factors for the x and y dimensions; this distorts | ||
3253 | * the output tiling slightly, but the distortion is consistent, and | ||
3254 | * doesn't accumulate over a large patch of tiling, so it won't make | ||
3255 | * anything end up totally out of place. | ||
3256 | * | ||
3257 | * (However, we compute the subsequent combination of 1 and sqrt(5) | ||
3258 | * exactly, because using an approximation to sqrt(5) _could_ mean | ||
3259 | * that in a sufficiently large patch of tiling two such combinations | ||
3260 | * ended up misordered.) | ||
3261 | * | ||
3262 | * Adding to the confusion, we also flip round the x and y | ||
3263 | * coordinates, because it's slightly nicer to have vertical edges in | ||
3264 | * the tiling rather than horizontal ones. (Both for aesthetics, and | ||
3265 | * also because if two P3 thin rhombs are separated by a horizontal | ||
3266 | * line and both contain numeric clues then the clue numbers look a | ||
3267 | * bit crowded, due to digits being taller than they are wide.) | ||
3268 | * | ||
3269 | * Finally, we have different base unit sizes for the two tiling | ||
3270 | * types, because sensible sizes for the two are actually different. | ||
3271 | * Each of P2 and P3 can be subdivided into the other, via dividing | ||
3272 | * the larger triangle type in two, so that L large and S small become | ||
3273 | * L+S large and L small. In the limit, this means that you expect the | ||
3274 | * number of triangles (hence tiles) to grow by a factor of phi in | ||
3275 | * each of those subdivisions (and hence by a factor of phi^2 in a | ||
3276 | * full subdivision of P2 to a finer P2). So a sensible size ratio | ||
3277 | * between the two tilings is one that makes them fit about the same | ||
3278 | * number of tiles into the same area - and since tile area is | ||
3279 | * proportional to _square_ of length, it follows that the P2 and P3 | ||
3280 | * length unit should differ by a factor of sqrt(phi). | ||
3281 | */ | ||
3282 | #define PENROSE_XUNIT_P2 37 | ||
3283 | #define PENROSE_YUNIT_P2 44 | ||
3284 | #define PENROSE_XUNIT_P3 30 | ||
3285 | #define PENROSE_YUNIT_P3 35 | ||
3286 | |||
3287 | struct size { int w, h; }; | ||
3288 | static struct size api_size_penrose(int width, int height, int which) | ||
3289 | { | ||
3290 | int xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3); | ||
3291 | int yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3); | ||
3292 | struct size size = { | ||
3293 | width * PENROSE_TILESIZE / yunit, | ||
3294 | height * PENROSE_TILESIZE / xunit, | ||
3295 | }; | ||
3296 | return size; | ||
3297 | } | ||
3298 | |||
3299 | static grid *grid_new_penrose(int width, int height, int which, | ||
3300 | const char *desc); /* forward reference */ | ||
3301 | |||
3302 | static char *grid_new_desc_penrose(grid_type type, int width, int height, | ||
3303 | random_state *rs) | ||
3304 | { | ||
3305 | char *buf; | ||
3306 | struct PenrosePatchParams params; | ||
3307 | int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); | ||
3308 | struct size size = api_size_penrose(width, height, which); | ||
3309 | |||
3310 | penrose_tiling_randomise(¶ms, which, size.h, size.w, rs); | ||
3311 | |||
3312 | buf = snewn(params.ncoords + 3, char); | ||
3313 | buf[0] = '0' + params.orientation; | ||
3314 | buf[1] = '0' + params.start_vertex; | ||
3315 | memcpy(buf + 2, params.coords, params.ncoords); | ||
3316 | buf[2 + params.ncoords] = '\0'; | ||
3317 | |||
3318 | sfree(params.coords); | ||
3319 | return buf; | ||
3320 | } | ||
3321 | |||
3322 | /* Shared code between validating and reading grid descs. | ||
3323 | * Always allocates params->coords, whether or not it returns an error. */ | ||
3324 | static const char *grid_desc_to_penrose_params( | ||
3325 | const char *desc, int which, struct PenrosePatchParams *params) | ||
3326 | { | ||
3327 | int i; | ||
3328 | |||
3329 | if (!*desc) | ||
3330 | return "empty grid description"; | ||
3331 | |||
3332 | params->ncoords = strlen(desc) - 2; | ||
3333 | params->coords = snewn(params->ncoords, char); | ||
3334 | |||
3335 | { | ||
3336 | char c = desc[0]; | ||
3337 | if (isdigit((unsigned char)c)) | ||
3338 | params->orientation = c - '0'; | ||
3339 | else | ||
3340 | return "expected digit at start of grid description"; | ||
3341 | |||
3342 | c = desc[1]; | ||
3343 | if (c >= '0' && c < '3') | ||
3344 | params->start_vertex = c - '0'; | ||
3345 | else | ||
3346 | return "expected digit as second char of grid description"; | ||
3347 | } | ||
3348 | |||
3349 | for (i = 0; i < params->ncoords; i++) { | ||
3350 | char c = desc[i+2]; | ||
3351 | if (!penrose_valid_letter(c, which)) | ||
3352 | return "expected tile letter in grid description"; | ||
3353 | params->coords[i] = c; | ||
3354 | } | ||
3355 | |||
3356 | return NULL; | ||
3357 | } | ||
3358 | |||
3359 | static const char *grid_validate_desc_penrose(grid_type type, | ||
3360 | int width, int height, | ||
3361 | const char *desc) | ||
3362 | { | ||
3363 | struct PenrosePatchParams params; | ||
3364 | const char *error = NULL; | ||
3365 | int which = (type == GRID_PENROSE_P2 ? PENROSE_P2 : PENROSE_P3); | ||
3366 | |||
3367 | if (!desc) | ||
3368 | return "Missing grid description string."; | ||
3369 | |||
3370 | if (*desc == 'G') | ||
3371 | return grid_validate_desc_penrose_legacy(type, width, height, desc); | ||
3372 | |||
3373 | error = grid_desc_to_penrose_params(desc, which, ¶ms); | ||
3374 | if (!error) | ||
3375 | error = penrose_tiling_params_invalid(¶ms, which); | ||
3376 | |||
3377 | sfree(params.coords); | ||
3378 | return error; | ||
3379 | } | ||
3380 | |||
3381 | struct penrosecontext { | ||
3382 | grid *g; | ||
3383 | tree234 *points; | ||
3384 | int xunit, yunit; | ||
3385 | }; | ||
3386 | |||
3387 | static void grid_penrose_callback(void *vctx, const int *coords) | ||
3388 | { | ||
3389 | struct penrosecontext *ctx = (struct penrosecontext *)vctx; | ||
3390 | size_t i; | ||
3391 | |||
3392 | grid_face_add_new(ctx->g, 4); | ||
3393 | for (i = 0; i < 4; i++) { | ||
3394 | grid_dot *d = grid_get_dot( | ||
3395 | ctx->g, ctx->points, | ||
3396 | coords[4*i+2] * ctx->yunit + n_times_root_k( | ||
3397 | coords[4*i+3] * ctx->yunit, 5), | ||
3398 | coords[4*i+0] * ctx->xunit + n_times_root_k( | ||
3399 | coords[4*i+1] * ctx->xunit, 5)); | ||
3400 | grid_face_set_dot(ctx->g, d, i); | ||
3401 | } | ||
3402 | } | ||
3403 | |||
3404 | static grid *grid_new_penrose(int width, int height, int which, | ||
3405 | const char *desc) | ||
3406 | { | ||
3407 | struct PenrosePatchParams params; | ||
3408 | const char *error = NULL; | ||
3409 | struct penrosecontext ctx[1]; | ||
3410 | struct size size; | ||
3411 | |||
3412 | if (*desc == 'G') | ||
3413 | return grid_new_penrose_legacy(width, height, which, desc); | ||
3414 | |||
3415 | error = grid_desc_to_penrose_params(desc, which, ¶ms); | ||
3416 | assert(error == NULL && "grid_validate_desc_penrose should have failed"); | ||
3417 | |||
3418 | ctx->g = grid_empty(); | ||
3419 | ctx->g->tilesize = PENROSE_TILESIZE; | ||
3420 | |||
3421 | ctx->points = newtree234(grid_point_cmp_fn); | ||
3422 | |||
3423 | ctx->xunit = (which == PENROSE_P2 ? PENROSE_XUNIT_P2 : PENROSE_XUNIT_P3); | ||
3424 | ctx->yunit = (which == PENROSE_P2 ? PENROSE_YUNIT_P2 : PENROSE_YUNIT_P3); | ||
3425 | |||
3426 | size = api_size_penrose(width, height, which); | ||
3427 | penrose_tiling_generate(¶ms, size.h, size.w, | ||
3428 | grid_penrose_callback, ctx); | ||
3429 | |||
3430 | freetree234(ctx->points); | ||
3431 | sfree(params.coords); | ||
3432 | |||
3433 | grid_trim_vigorously(ctx->g); | ||
3434 | grid_make_consistent(ctx->g); | ||
3435 | |||
3436 | /* | ||
3437 | * Centre the grid in its originally promised rectangle. | ||
3438 | */ | ||
3439 | { | ||
3440 | int w = width * PENROSE_TILESIZE, h = height * PENROSE_TILESIZE; | ||
3441 | ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2; | ||
3442 | ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2; | ||
3443 | ctx->g->highest_x = ctx->g->lowest_x + w; | ||
3444 | ctx->g->highest_y = ctx->g->lowest_y + h; | ||
3445 | } | ||
3446 | |||
3447 | return ctx->g; | ||
3448 | } | ||
3449 | |||
3450 | static const char *grid_validate_params_penrose_p2_kite(int width, int height) | ||
3451 | { | ||
3452 | return grid_validate_params_penrose(width, height); | ||
3453 | } | ||
3454 | |||
3455 | static const char *grid_validate_params_penrose_p3_thick(int width, int height) | ||
3456 | { | ||
3457 | return grid_validate_params_penrose(width, height); | ||
3458 | } | ||
3459 | |||
3094 | static void grid_size_penrose_p2_kite(int width, int height, | 3460 | static void grid_size_penrose_p2_kite(int width, int height, |
3095 | int *tilesize, int *xextent, int *yextent) | 3461 | int *tilesize, int *xextent, int *yextent) |
3096 | { | 3462 | { |
@@ -3113,18 +3479,349 @@ static grid *grid_new_penrose_p3_thick(int width, int height, const char *desc) | |||
3113 | return grid_new_penrose(width, height, PENROSE_P3, desc); | 3479 | return grid_new_penrose(width, height, PENROSE_P3, desc); |
3114 | } | 3480 | } |
3115 | 3481 | ||
3482 | #define HATS_TILESIZE 32 | ||
3483 | #define HATS_XSQUARELEN 4 | ||
3484 | #define HATS_YSQUARELEN 6 | ||
3485 | #define HATS_XUNIT 14 | ||
3486 | #define HATS_YUNIT 8 | ||
3487 | |||
3488 | static const char *grid_validate_params_hats( | ||
3489 | int width, int height) | ||
3490 | { | ||
3491 | int l = HATS_TILESIZE; | ||
3492 | |||
3493 | if (width > INT_MAX / l || /* xextent */ | ||
3494 | height > INT_MAX / l || /* yextent */ | ||
3495 | width > INT_MAX / (6 * height)) /* max_dots */ | ||
3496 | return "Grid must not be unreasonably large"; | ||
3497 | return NULL; | ||
3498 | } | ||
3499 | |||
3500 | static void grid_size_hats(int width, int height, | ||
3501 | int *tilesize, int *xextent, int *yextent) | ||
3502 | { | ||
3503 | *tilesize = HATS_TILESIZE; | ||
3504 | *xextent = width * HATS_XUNIT * HATS_XSQUARELEN; | ||
3505 | *yextent = height * HATS_YUNIT * HATS_YSQUARELEN; | ||
3506 | } | ||
3507 | |||
3508 | static char *grid_new_desc_hats( | ||
3509 | grid_type type, int width, int height, random_state *rs) | ||
3510 | { | ||
3511 | char *buf, *p; | ||
3512 | size_t bufmax, i; | ||
3513 | struct HatPatchParams hp; | ||
3514 | |||
3515 | hat_tiling_randomise(&hp, width, height, rs); | ||
3516 | |||
3517 | bufmax = 3 * hp.ncoords + 2; | ||
3518 | buf = snewn(bufmax, char); | ||
3519 | p = buf; | ||
3520 | for (i = 0; i < hp.ncoords; i++) { | ||
3521 | assert(hp.coords[i] < 100); /* at most 2 digits */ | ||
3522 | assert(p - buf <= bufmax-4); /* room for 2 digits, comma and NUL */ | ||
3523 | p += sprintf(p, "%d,", (int)hp.coords[i]); | ||
3524 | } | ||
3525 | assert(p - buf <= bufmax-2); /* room for final letter and NUL */ | ||
3526 | p[0] = hp.final_metatile; | ||
3527 | p[1] = '\0'; | ||
3528 | |||
3529 | sfree(hp.coords); | ||
3530 | return buf; | ||
3531 | } | ||
3532 | |||
3533 | /* Shared code between validating and reading grid descs. | ||
3534 | * Always allocates hp->coords, whether or not it returns an error. */ | ||
3535 | static const char *grid_desc_to_hat_params( | ||
3536 | const char *desc, struct HatPatchParams *hp) | ||
3537 | { | ||
3538 | size_t maxcoords; | ||
3539 | const char *p = desc; | ||
3540 | |||
3541 | maxcoords = (strlen(desc) + 1) / 2; | ||
3542 | hp->coords = snewn(maxcoords, unsigned char); | ||
3543 | hp->ncoords = 0; | ||
3544 | |||
3545 | while (isdigit((unsigned char)*p)) { | ||
3546 | const char *p_orig = p; | ||
3547 | int n = atoi(p); | ||
3548 | while (*p && isdigit((unsigned char)*p)) p++; | ||
3549 | if (*p != ',') | ||
3550 | return "expected ',' in grid description"; | ||
3551 | if (p - p_orig > 2 || n > 0xFF) | ||
3552 | return "too-large coordinate in grid description"; | ||
3553 | p++; /* eat the comma */ | ||
3554 | |||
3555 | /* This assert should be guaranteed by the way we calculated | ||
3556 | * maxcoords, so a failure of this check is a bug in this | ||
3557 | * function, not an indication of an invalid input string */ | ||
3558 | assert(hp->ncoords < maxcoords); | ||
3559 | hp->coords[hp->ncoords++] = n; | ||
3560 | } | ||
3561 | |||
3562 | if (*p == 'H' || *p == 'T' || *p == 'P' || *p == 'F') | ||
3563 | hp->final_metatile = *p; | ||
3564 | else | ||
3565 | return "invalid character in grid description"; | ||
3566 | |||
3567 | return NULL; | ||
3568 | } | ||
3569 | |||
3570 | static const char *grid_validate_desc_hats( | ||
3571 | grid_type type, int width, int height, const char *desc) | ||
3572 | { | ||
3573 | struct HatPatchParams hp; | ||
3574 | const char *error = NULL; | ||
3575 | |||
3576 | if (!desc) | ||
3577 | return "Missing grid description string."; | ||
3578 | |||
3579 | error = grid_desc_to_hat_params(desc, &hp); | ||
3580 | if (!error) | ||
3581 | error = hat_tiling_params_invalid(&hp); | ||
3582 | |||
3583 | sfree(hp.coords); | ||
3584 | return error; | ||
3585 | } | ||
3586 | |||
3587 | struct hatcontext { | ||
3588 | grid *g; | ||
3589 | tree234 *points; | ||
3590 | }; | ||
3591 | |||
3592 | static void grid_hats_callback(void *vctx, size_t nvertices, int *coords) | ||
3593 | { | ||
3594 | struct hatcontext *ctx = (struct hatcontext *)vctx; | ||
3595 | size_t i; | ||
3596 | |||
3597 | grid_face_add_new(ctx->g, nvertices); | ||
3598 | for (i = 0; i < nvertices; i++) { | ||
3599 | grid_dot *d = grid_get_dot( | ||
3600 | ctx->g, ctx->points, | ||
3601 | coords[2*i] * HATS_XUNIT, | ||
3602 | coords[2*i+1] * HATS_YUNIT); | ||
3603 | grid_face_set_dot(ctx->g, d, i); | ||
3604 | } | ||
3605 | } | ||
3606 | |||
3607 | static grid *grid_new_hats(int width, int height, const char *desc) | ||
3608 | { | ||
3609 | struct HatPatchParams hp; | ||
3610 | const char *error = NULL; | ||
3611 | |||
3612 | error = grid_desc_to_hat_params(desc, &hp); | ||
3613 | assert(error == NULL && "grid_validate_desc_hats should have failed"); | ||
3614 | |||
3615 | struct hatcontext ctx[1]; | ||
3616 | |||
3617 | ctx->g = grid_empty(); | ||
3618 | ctx->g->tilesize = HATS_TILESIZE; | ||
3619 | |||
3620 | ctx->points = newtree234(grid_point_cmp_fn); | ||
3621 | |||
3622 | hat_tiling_generate(&hp, width, height, grid_hats_callback, ctx); | ||
3623 | |||
3624 | freetree234(ctx->points); | ||
3625 | sfree(hp.coords); | ||
3626 | |||
3627 | grid_trim_vigorously(ctx->g); | ||
3628 | grid_make_consistent(ctx->g); | ||
3629 | return ctx->g; | ||
3630 | } | ||
3631 | |||
3632 | #define SPECTRE_TILESIZE 32 | ||
3633 | #define SPECTRE_SQUARELEN 7 | ||
3634 | #define SPECTRE_UNIT 8 | ||
3635 | |||
3636 | static const char *grid_validate_params_spectres( | ||
3637 | int width, int height) | ||
3638 | { | ||
3639 | int l = SPECTRE_UNIT * SPECTRE_SQUARELEN; | ||
3640 | |||
3641 | if (width > INT_MAX / l || /* xextent */ | ||
3642 | height > INT_MAX / l || /* yextent */ | ||
3643 | width > (INT_MAX / SPECTRE_SQUARELEN / | ||
3644 | SPECTRE_SQUARELEN / height)) /* max_faces */ | ||
3645 | return "Grid must not be unreasonably large"; | ||
3646 | return NULL; | ||
3647 | } | ||
3648 | |||
3649 | static void grid_size_spectres(int width, int height, | ||
3650 | int *tilesize, int *xextent, int *yextent) | ||
3651 | { | ||
3652 | *tilesize = SPECTRE_TILESIZE; | ||
3653 | *xextent = width * SPECTRE_UNIT * SPECTRE_SQUARELEN; | ||
3654 | *yextent = height * SPECTRE_UNIT * SPECTRE_SQUARELEN; | ||
3655 | } | ||
3656 | |||
3657 | static char *grid_new_desc_spectres( | ||
3658 | grid_type type, int width, int height, random_state *rs) | ||
3659 | { | ||
3660 | char *buf; | ||
3661 | size_t i; | ||
3662 | struct SpectrePatchParams sp; | ||
3663 | |||
3664 | spectre_tiling_randomise(&sp, width * SPECTRE_SQUARELEN, | ||
3665 | height * SPECTRE_SQUARELEN, rs); | ||
3666 | |||
3667 | buf = snewn(sp.ncoords + 3, char); | ||
3668 | buf[0] = (sp.orientation < 10 ? '0' + sp.orientation : | ||
3669 | 'A' + sp.orientation - 10); | ||
3670 | for (i = 0; i < sp.ncoords; i++) { | ||
3671 | assert(sp.coords[i] < 10); /* all indices are 1 digit */ | ||
3672 | buf[i+1] = '0' + sp.coords[i]; | ||
3673 | } | ||
3674 | buf[sp.ncoords+1] = sp.final_hex; | ||
3675 | buf[sp.ncoords+2] = '\0'; | ||
3676 | |||
3677 | sfree(sp.coords); | ||
3678 | return buf; | ||
3679 | } | ||
3680 | |||
3681 | /* Shared code between validating and reading grid descs. | ||
3682 | * Always allocates sp->coords, whether or not it returns an error. */ | ||
3683 | static const char *grid_desc_to_spectre_params( | ||
3684 | const char *desc, struct SpectrePatchParams *sp) | ||
3685 | { | ||
3686 | size_t i; | ||
3687 | |||
3688 | if (!*desc) | ||
3689 | return "empty grid description"; | ||
3690 | |||
3691 | sp->ncoords = strlen(desc) - 2; | ||
3692 | sp->coords = snewn(sp->ncoords, unsigned char); | ||
3693 | |||
3694 | { | ||
3695 | char c = desc[0]; | ||
3696 | if (isdigit((unsigned char)c)) | ||
3697 | sp->orientation = c - '0'; | ||
3698 | else if (c == 'A' || c == 'B') | ||
3699 | sp->orientation = 10 + c - 'A'; | ||
3700 | else | ||
3701 | return "expected digit or A,B at start of grid description"; | ||
3702 | } | ||
3703 | |||
3704 | for (i = 0; i < sp->ncoords; i++) { | ||
3705 | char c = desc[i+1]; | ||
3706 | if (!isdigit((unsigned char)c)) | ||
3707 | return "expected digit in grid description"; | ||
3708 | sp->coords[i] = c - '0'; | ||
3709 | } | ||
3710 | |||
3711 | sp->final_hex = desc[sp->ncoords+1]; | ||
3712 | |||
3713 | return NULL; | ||
3714 | } | ||
3715 | |||
3716 | static const char *grid_validate_desc_spectres( | ||
3717 | grid_type type, int width, int height, const char *desc) | ||
3718 | { | ||
3719 | struct SpectrePatchParams sp; | ||
3720 | const char *error = NULL; | ||
3721 | |||
3722 | if (!desc) | ||
3723 | return "Missing grid description string."; | ||
3724 | |||
3725 | error = grid_desc_to_spectre_params(desc, &sp); | ||
3726 | if (!error) | ||
3727 | error = spectre_tiling_params_invalid(&sp); | ||
3728 | |||
3729 | sfree(sp.coords); | ||
3730 | return error; | ||
3731 | } | ||
3732 | |||
3733 | struct spectrecontext { | ||
3734 | grid *g; | ||
3735 | tree234 *points; | ||
3736 | }; | ||
3737 | |||
3738 | static void grid_spectres_callback(void *vctx, const int *coords) | ||
3739 | { | ||
3740 | struct spectrecontext *ctx = (struct spectrecontext *)vctx; | ||
3741 | size_t i; | ||
3742 | |||
3743 | grid_face_add_new(ctx->g, SPECTRE_NVERTICES); | ||
3744 | for (i = 0; i < SPECTRE_NVERTICES; i++) { | ||
3745 | grid_dot *d = grid_get_dot( | ||
3746 | ctx->g, ctx->points, | ||
3747 | (coords[4*i+0] * SPECTRE_UNIT + | ||
3748 | n_times_root_k(coords[4*i+1] * SPECTRE_UNIT, 3)), | ||
3749 | (coords[4*i+2] * SPECTRE_UNIT + | ||
3750 | n_times_root_k(coords[4*i+3] * SPECTRE_UNIT, 3))); | ||
3751 | grid_face_set_dot(ctx->g, d, i); | ||
3752 | } | ||
3753 | } | ||
3754 | |||
3755 | static grid *grid_new_spectres(int width, int height, const char *desc) | ||
3756 | { | ||
3757 | struct SpectrePatchParams sp; | ||
3758 | const char *error = NULL; | ||
3759 | int width2 = width * SPECTRE_SQUARELEN; | ||
3760 | int height2 = height * SPECTRE_SQUARELEN; | ||
3761 | |||
3762 | error = grid_desc_to_spectre_params(desc, &sp); | ||
3763 | assert(error == NULL && "grid_validate_desc_spectres should have failed"); | ||
3764 | |||
3765 | struct spectrecontext ctx[1]; | ||
3766 | |||
3767 | ctx->g = grid_empty(); | ||
3768 | ctx->g->tilesize = SPECTRE_TILESIZE; | ||
3769 | |||
3770 | ctx->points = newtree234(grid_point_cmp_fn); | ||
3771 | |||
3772 | spectre_tiling_generate(&sp, width2, height2, grid_spectres_callback, ctx); | ||
3773 | |||
3774 | freetree234(ctx->points); | ||
3775 | sfree(sp.coords); | ||
3776 | |||
3777 | grid_trim_vigorously(ctx->g); | ||
3778 | grid_make_consistent(ctx->g); | ||
3779 | |||
3780 | /* | ||
3781 | * As with the Penrose tiling, we're likely to have different | ||
3782 | * sized margins due to the lack of a neat grid that this tiling | ||
3783 | * fits on. So now we know what tiles we're left with, recentre | ||
3784 | * them. | ||
3785 | */ | ||
3786 | { | ||
3787 | int w = width2 * SPECTRE_UNIT, h = height2 * SPECTRE_UNIT; | ||
3788 | ctx->g->lowest_x -= (w - (ctx->g->highest_x - ctx->g->lowest_x))/2; | ||
3789 | ctx->g->lowest_y -= (h - (ctx->g->highest_y - ctx->g->lowest_y))/2; | ||
3790 | ctx->g->highest_x = ctx->g->lowest_x + w; | ||
3791 | ctx->g->highest_y = ctx->g->lowest_y + h; | ||
3792 | } | ||
3793 | |||
3794 | return ctx->g; | ||
3795 | } | ||
3796 | |||
3116 | /* ----------- End of grid generators ------------- */ | 3797 | /* ----------- End of grid generators ------------- */ |
3117 | 3798 | ||
3799 | #define FNVAL(upper,lower) &grid_validate_params_ ## lower, | ||
3118 | #define FNNEW(upper,lower) &grid_new_ ## lower, | 3800 | #define FNNEW(upper,lower) &grid_new_ ## lower, |
3119 | #define FNSZ(upper,lower) &grid_size_ ## lower, | 3801 | #define FNSZ(upper,lower) &grid_size_ ## lower, |
3120 | 3802 | ||
3803 | static const char *(*(grid_validate_paramses[]))(int, int) = | ||
3804 | { GRIDGEN_LIST(FNVAL) }; | ||
3121 | static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) }; | 3805 | static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) }; |
3122 | static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) }; | 3806 | static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) }; |
3123 | 3807 | ||
3808 | /* Work out if a grid can be made, and complain if not. */ | ||
3809 | |||
3810 | const char *grid_validate_params(grid_type type, int width, int height) | ||
3811 | { | ||
3812 | if (width <= 0 || height <= 0) | ||
3813 | return "Width and height must both be positive"; | ||
3814 | return grid_validate_paramses[type](width, height); | ||
3815 | } | ||
3816 | |||
3124 | char *grid_new_desc(grid_type type, int width, int height, random_state *rs) | 3817 | char *grid_new_desc(grid_type type, int width, int height, random_state *rs) |
3125 | { | 3818 | { |
3126 | if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { | 3819 | if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { |
3127 | return grid_new_desc_penrose(type, width, height, rs); | 3820 | return grid_new_desc_penrose(type, width, height, rs); |
3821 | } else if (type == GRID_HATS) { | ||
3822 | return grid_new_desc_hats(type, width, height, rs); | ||
3823 | } else if (type == GRID_SPECTRES) { | ||
3824 | return grid_new_desc_spectres(type, width, height, rs); | ||
3128 | } else if (type == GRID_TRIANGULAR) { | 3825 | } else if (type == GRID_TRIANGULAR) { |
3129 | return dupstr("0"); /* up-to-date version of triangular grid */ | 3826 | return dupstr("0"); /* up-to-date version of triangular grid */ |
3130 | } else { | 3827 | } else { |
@@ -3137,6 +3834,10 @@ const char *grid_validate_desc(grid_type type, int width, int height, | |||
3137 | { | 3834 | { |
3138 | if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { | 3835 | if (type == GRID_PENROSE_P2 || type == GRID_PENROSE_P3) { |
3139 | return grid_validate_desc_penrose(type, width, height, desc); | 3836 | return grid_validate_desc_penrose(type, width, height, desc); |
3837 | } else if (type == GRID_HATS) { | ||
3838 | return grid_validate_desc_hats(type, width, height, desc); | ||
3839 | } else if (type == GRID_SPECTRES) { | ||
3840 | return grid_validate_desc_spectres(type, width, height, desc); | ||
3140 | } else if (type == GRID_TRIANGULAR) { | 3841 | } else if (type == GRID_TRIANGULAR) { |
3141 | return grid_validate_desc_triangular(type, width, height, desc); | 3842 | return grid_validate_desc_triangular(type, width, height, desc); |
3142 | } else { | 3843 | } else { |