ref: d71bba1a17d6b228e7dd8b437dccbd3f6bc4698c
parent: fcda12f4b73e69841fd8957b8e33930c584093e5
author: Ben Harris <bjh21@bjh21.me.uk>
date: Wed Jan 11 18:11:46 EST 2023
Limit maximum grid size in Loopy Every grid shape has its own limit, so this involved adding a new interface between loopy.c and grid.c. The limits are based on ensuring that the co-ordinate system of the grid doesn't overflow INT_MAX and neither do the lengths of the face and dot arrays. Though now I come to look at it I think the actual limits of grid.c are much lower. Hmm.
--- a/grid.c
+++ b/grid.c
@@ -11,8 +11,9 @@
#include <string.h>
#include <assert.h>
#include <ctype.h>
-#include <math.h>
#include <float.h>
+#include <limits.h>
+#include <math.h>
#include "puzzles.h"
#include "tree234.h"
@@ -1388,6 +1389,15 @@
#define SQUARE_TILESIZE 20
+static const char *grid_validate_params_square(int width, int height)
+{+ if (width > INT_MAX / SQUARE_TILESIZE || /* xextent */
+ height > INT_MAX / SQUARE_TILESIZE || /* yextent */
+ width + 1 > INT_MAX / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_square(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -1450,6 +1460,18 @@
#define HONEY_A 15
#define HONEY_B 26
+static const char *grid_validate_params_honeycomb(int width, int height)
+{+ int a = HONEY_A;
+ int b = HONEY_B;
+
+ if (width - 1 > (INT_MAX - 4*a) / (3 * a) || /* xextent */
+ height - 1 > (INT_MAX - 3*b) / (2 * b) || /* yextent */
+ width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_honeycomb(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -1519,6 +1541,18 @@
#define TRIANGLE_VEC_X 15
#define TRIANGLE_VEC_Y 26
+static const char *grid_validate_params_triangular(int width, int height)
+{+ int vec_x = TRIANGLE_VEC_X;
+ int vec_y = TRIANGLE_VEC_Y;
+
+ if (width > INT_MAX / (2 * vec_x) - 1 || /* xextent */
+ height > INT_MAX / vec_y || /* yextent */
+ width + 1 > INT_MAX / 4 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_triangular(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -1716,6 +1750,19 @@
#define SNUBSQUARE_A 15
#define SNUBSQUARE_B 26
+static const char *grid_validate_params_snubsquare(int width, int height)
+{+ int a = SNUBSQUARE_A;
+ int b = SNUBSQUARE_B;
+
+ if (width-1 > (INT_MAX - (a + b)) / (a+b) || /* xextent */
+ height > (INT_MAX - (a + b)) / (a+b) || /* yextent */
+ width > INT_MAX / 3 / height || /* max_faces */
+ width + 1 > INT_MAX / 2 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_snubsquare(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -1830,6 +1877,18 @@
#define CAIRO_A 14
#define CAIRO_B 31
+static const char *grid_validate_params_cairo(int width, int height)
+{+ int b = CAIRO_B; /* a unused in determining grid size. */
+
+ if (width - 1 > (INT_MAX - 2*b) / (2*b) || /* xextent */
+ height - 1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
+ width > INT_MAX / 2 / height || /* max_faces */
+ width + 1 > INT_MAX / 3 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_cairo(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -1936,6 +1995,18 @@
#define GREATHEX_A 15
#define GREATHEX_B 26
+static const char *grid_validate_params_greathexagonal(int width, int height)
+{+ int a = GREATHEX_A;
+ int b = GREATHEX_B;
+
+ if (width-1 > (INT_MAX - 4*a) / (3*a + b) || /* xextent */
+ height-1 > (INT_MAX - (3*b + a)) / (2*a + 2*b) || /* yextent */
+ width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_greathexagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2066,6 +2137,18 @@
#define KAGOME_A 15
#define KAGOME_B 26
+static const char *grid_validate_params_kagome(int width, int height)
+{+ int a = KAGOME_A;
+ int b = KAGOME_B;
+
+ if (width-1 > (INT_MAX - 6*a) / (4*a) || /* xextent */
+ height-1 > (INT_MAX - 2*b) / (2*b) || /* yextent */
+ width + 1 > INT_MAX / 6 / (height + 1)) /* max_faces */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_kagome(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2162,6 +2245,18 @@
#define OCTAGONAL_A 29
#define OCTAGONAL_B 41
+static const char *grid_validate_params_octagonal(int width, int height)
+{+ int a = OCTAGONAL_A;
+ int b = OCTAGONAL_B;
+
+ if (width > INT_MAX / (2*a + b) || /* xextent */
+ height > INT_MAX / (2*a + b) || /* yextent */
+ height + 1 > INT_MAX / 4 / (width + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_octagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2245,6 +2340,18 @@
#define KITE_A 15
#define KITE_B 26
+static const char *grid_validate_params_kites(int width, int height)
+{+ int a = KITE_A;
+ int b = KITE_B;
+
+ if (width > (INT_MAX - 2*b) / (4*b) || /* xextent */
+ height - 1 > (INT_MAX - 8*a) / (6*a) || /* yextent */
+ width + 1 > INT_MAX / 6 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_kites(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2367,6 +2474,20 @@
#define FLORET_PX 75
#define FLORET_PY -26
+static const char *grid_validate_params_floret(int width, int height)
+{+ int px = FLORET_PX, py = FLORET_PY; /* |( 75, -26)| = 79.43 */
+ int qx = 4*px/5, qy = -py*2; /* |( 60, 52)| = 79.40 */
+ int ry = qy-py;
+ /* rx unused in determining grid size. */
+
+ if (width - 1 > (INT_MAX - (4*qx + 2*px)) / ((6*px+3*qx)/2) ||/* xextent */
+ height - 1 > (INT_MAX - (4*qy + 2*ry)) / (5*qy-4*py) || /* yextent */
+ width + 1 > INT_MAX / 9 / (height + 1)) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_floret(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2476,6 +2597,18 @@
#define DODEC_A 15
#define DODEC_B 26
+static const char *grid_validate_params_dodecagonal(int width, int height)
+{+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ if (width - 1 > (INT_MAX - 3*(2*a + b)) / (4*a + 2*b) || /* xextent */
+ height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 2*b) || /* yextent */
+ width > INT_MAX / 14 / height) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_dodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2556,6 +2689,18 @@
return g;
}
+static const char *grid_validate_params_greatdodecagonal(int width, int height)
+{+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ if (width - 1 > (INT_MAX - (2*(2*a + b) + 3*a + b)) / (6*a + 2*b) ||
+ height - 1 > (INT_MAX - 2*(2*a + b)) / (3*a + 3*b) || /* yextent */
+ width > INT_MAX / 200 / height) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_greatdodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2670,6 +2815,19 @@
return g;
}
+static const char *grid_validate_params_greatgreatdodecagonal(
+ int width, int height)
+{+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ if (width-1 > (INT_MAX - (2*(2*a + b) + 2*a + 2*b)) / (4*a + 4*b) ||
+ height-1 > (INT_MAX - 2*(2*a + b)) / (6*a + 2*b) || /* yextent */
+ width > INT_MAX / 300 / height) /* max_dots */
+ return "Grid size must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_greatgreatdodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2839,6 +2997,19 @@
return g;
}
+static const char *grid_validate_params_compassdodecagonal(
+ int width, int height)
+{+ int a = DODEC_A;
+ int b = DODEC_B;
+
+ if (width > INT_MAX / (4*a + 2*b) || /* xextent */
+ height > INT_MAX / (4*a + 2*b) || /* yextent */
+ width > INT_MAX / 18 / height) /* max_dots */
+ return "Grid must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_compassdodecagonal(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -2985,6 +3156,17 @@
#define PENROSE_TILESIZE 100
+static const char *grid_validate_params_penrose(int width, int height)
+{+ int l = PENROSE_TILESIZE;
+
+ if (width > INT_MAX / l || /* xextent */
+ height > INT_MAX / l || /* yextent */
+ width > INT_MAX / (3 * 3 * 4 * height)) /* max_dots */
+ return "Grid must not be unreasonably large";
+ return NULL;
+}
+
static void grid_size_penrose(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -3187,6 +3369,16 @@
return g;
}
+static const char *grid_validate_params_penrose_p2_kite(int width, int height)
+{+ return grid_validate_params_penrose(width, height);
+}
+
+static const char *grid_validate_params_penrose_p3_thick(int width, int height)
+{+ return grid_validate_params_penrose(width, height);
+}
+
static void grid_size_penrose_p2_kite(int width, int height,
int *tilesize, int *xextent, int *yextent)
{@@ -3211,11 +3403,23 @@
/* ----------- End of grid generators ------------- */
+#define FNVAL(upper,lower) &grid_validate_params_ ## lower,
#define FNNEW(upper,lower) &grid_new_ ## lower,
#define FNSZ(upper,lower) &grid_size_ ## lower,
+static const char *(*(grid_validate_paramses[]))(int, int) =
+ { GRIDGEN_LIST(FNVAL) }; static grid *(*(grid_news[]))(int, int, const char*) = { GRIDGEN_LIST(FNNEW) }; static void(*(grid_sizes[]))(int, int, int*, int*, int*) = { GRIDGEN_LIST(FNSZ) };+
+/* Work out if a grid can be made, and complain if not. */
+
+const char *grid_validate_params(grid_type type, int width, int height)
+{+ if (width <= 0 || height <= 0)
+ return "Width and height must both be positive";
+ return grid_validate_paramses[type](width, height);
+}
char *grid_new_desc(grid_type type, int width, int height, random_state *rs)
{--- a/grid.h
+++ b/grid.h
@@ -115,6 +115,8 @@
typedef enum grid_type { GRIDGEN_LIST(ENUM) GRID_TYPE_MAX } grid_type;#undef ENUM
+const char *grid_validate_params(grid_type type, int width, int height);
+
/* Free directly after use if non-NULL. Will never contain an underscore
* (so clients can safely use that as a separator). */
char *grid_new_desc(grid_type type, int width, int height, random_state *rs);
--- a/loopy.c
+++ b/loopy.c
@@ -684,6 +684,7 @@
static const char *validate_params(const game_params *params, bool full)
{+ const char *err;
if (params->type < 0 || params->type >= NUM_GRID_TYPES)
return "Illegal grid type";
if (params->w < grid_size_limits[params->type].amin ||
@@ -692,6 +693,8 @@
if (params->w < grid_size_limits[params->type].omin &&
params->h < grid_size_limits[params->type].omin)
return grid_size_limits[params->type].oerr;
+ err = grid_validate_params(grid_types[params->type], params->w, params->h);
+ if (err != NULL) return err;
/*
* This shouldn't be able to happen at all, since decode_params