1 files changed, 289 insertions, 0 deletions

diff --git a/apps/plugins/puzzles/src/penrose-internal.h b/apps/plugins/puzzles/src/penrose-internal.h
new file mode 100644
index 0000000000..984cd35711
--- /dev/null
+++ b/apps/plugins/puzzles/src/penrose-internal.h
@@ -0,0 +1,289 @@
+#include "penrose.h"
+
+static inline unsigned num_subtriangles(char t)
+{
+    return (t == 'A' || t == 'B' || t == 'X' || t == 'Y') ? 3 : 2;
+}
+
+static inline unsigned sibling_edge(char t)
+{
+    switch (t) {
+      case 'A': case 'U': return 2;
+      case 'B': case 'V': return 1;
+      default: return 0;
+    }
+}
+
+/*
+ * Coordinate system for tracking Penrose-tile half-triangles.
+ * PenroseCoords simply stores an array of triangle types.
+ */
+typedef struct PenroseCoords {
+    char *c;
+    size_t nc, csize;
+} PenroseCoords;
+
+PenroseCoords *penrose_coords_new(void);
+void penrose_coords_free(PenroseCoords *pc);
+void penrose_coords_make_space(PenroseCoords *pc, size_t size);
+PenroseCoords *penrose_coords_copy(PenroseCoords *pc_in);
+
+/*
+ * Coordinate system for locating Penrose tiles in the plane.
+ *
+ * The 'Point' structure represents a single point by means of an
+ * integer linear combination of {1, t, t^2, t^3}, where t is the
+ * complex number exp(i pi/5) representing 1/10 of a turn about the
+ * origin.
+ *
+ * The 'PenroseTriangle' structure represents a half-tile triangle,
+ * giving both the locations of its vertices and its combinatorial
+ * coordinates. It also contains a linked-list pointer and a boolean
+ * flag, used during breadth-first search to generate all the tiles in
+ * an area and report them exactly once.
+ */
+typedef struct Point {
+    int coeffs[4];
+} Point;
+typedef struct PenroseTriangle PenroseTriangle;
+struct PenroseTriangle {
+    Point vertices[3];
+    PenroseCoords *pc;
+    PenroseTriangle *next; /* used in breadth-first search */
+    bool reported;
+};
+
+/* Fill in all the coordinates of a triangle starting from any single edge.
+ * Requires tri->pc to have been filled in, so that we know which shape of
+ * triangle we're placing. */
+void penrose_place(PenroseTriangle *tri, Point u, Point v, int index_of_u);
+
+/* Free a PenroseHalf and its contained coordinates, or a whole PenroseTile */
+void penrose_free(PenroseTriangle *tri);
+
+/*
+ * A Point is really a complex number, so we can add, subtract and
+ * multiply them.
+ */
+static inline Point point_add(Point a, Point b)
+{
+    Point r;
+    size_t i;
+    for (i = 0; i < 4; i++)
+        r.coeffs[i] = a.coeffs[i] + b.coeffs[i];
+    return r;
+}
+static inline Point point_sub(Point a, Point b)
+{
+    Point r;
+    size_t i;
+    for (i = 0; i < 4; i++)
+        r.coeffs[i] = a.coeffs[i] - b.coeffs[i];
+    return r;
+}
+static inline Point point_mul_by_t(Point x)
+{
+    Point r;
+    /* Multiply by t by using the identity t^4 - t^3 + t^2 - t + 1 = 0,
+     * so t^4 = t^3 - t^2 + t - 1 */
+    r.coeffs[0] = -x.coeffs[3];
+    r.coeffs[1] = x.coeffs[0] + x.coeffs[3];
+    r.coeffs[2] = x.coeffs[1] - x.coeffs[3];
+    r.coeffs[3] = x.coeffs[2] + x.coeffs[3];
+    return r;
+}
+static inline Point point_mul(Point a, Point b)
+{
+    size_t i, j;
+    Point r;
+
+    /* Initialise r to be a, scaled by b's t^3 term */
+    for (j = 0; j < 4; j++)
+        r.coeffs[j] = a.coeffs[j] * b.coeffs[3];
+
+    /* Now iterate r = t*r + (next coefficient down), by Horner's rule */
+    for (i = 3; i-- > 0 ;) {
+        r = point_mul_by_t(r);
+        for (j = 0; j < 4; j++)
+            r.coeffs[j] += a.coeffs[j] * b.coeffs[i];
+    }
+
+    return r;
+}
+static inline bool point_equal(Point a, Point b)
+{
+    size_t i;
+    for (i = 0; i < 4; i++)
+        if (a.coeffs[i] != b.coeffs[i])
+            return false;
+    return true;
+}
+
+/*
+ * Return the Point corresponding to a rotation of s steps around the
+ * origin, i.e. a rotation by 36*s degrees or s*pi/5 radians.
+ */
+static inline Point point_rot(int s)
+{
+    Point r = {{ 1, 0, 0, 0 }};
+    Point tpower = {{ 0, 1, 0, 0 }};
+
+    /* Reduce to a sensible range */
+    s = s % 10;
+    if (s < 0)
+        s += 10;
+
+    while (true) {
+        if (s & 1)
+            r = point_mul(r, tpower);
+        s >>= 1;
+        if (!s)
+            break;
+        tpower = point_mul(tpower, tpower);
+    }
+
+    return r;
+}
+
+/*
+ * PenroseContext is the shared context of a whole run of the
+ * algorithm. Its 'prototype' PenroseCoords object represents the
+ * coordinates of the starting triangle, and is extended as necessary;
+ * any other PenroseCoord that needs extending will copy the
+ * higher-order values from ctx->prototype as needed, so that once
+ * each choice has been made, it remains consistent.
+ *
+ * When we're inventing a random piece of tiling in the first place,
+ * we append to ctx->prototype by choosing a random (but legal)
+ * higher-level metatile for the current topmost one to turn out to be
+ * part of. When we're replaying a generation whose parameters are
+ * already stored, we don't have a random_state, and we make fixed
+ * decisions if not enough coordinates were provided, as in the
+ * corresponding hat.c system.
+ *
+ * For a normal (non-testing) caller, penrosectx_generate() is the
+ * main useful function. It breadth-first searches a whole area to
+ * generate all the triangles in it, starting from a (typically
+ * central) one with the coordinates of ctx->prototype. It takes two
+ * callback function: one that checks whether a triangle is within the
+ * bounds of the target area (and therefore the search should continue
+ * exploring its neighbours), and another that reports a full Penrose
+ * tile once both of its halves have been found and determined to be
+ * in bounds.
+ */
+typedef struct PenroseContext {
+    random_state *rs;
+    bool must_free_rs;
+    unsigned start_vertex; /* which vertex of 'prototype' is at the origin? */
+    int orientation;    /* orientation to put in PenrosePatchParams */
+    PenroseCoords *prototype;
+} PenroseContext;
+
+void penrosectx_init_random(PenroseContext *ctx, random_state *rs, int which);
+void penrosectx_init_from_params(
+    PenroseContext *ctx, const struct PenrosePatchParams *ps);
+void penrosectx_cleanup(PenroseContext *ctx);
+PenroseCoords *penrosectx_initial_coords(PenroseContext *ctx);
+void penrosectx_extend_coords(PenroseContext *ctx, PenroseCoords *pc,
+                              size_t n);
+void penrosectx_step(PenroseContext *ctx, PenroseCoords *pc,
+                     unsigned edge, unsigned *outedge);
+void penrosectx_generate(
+    PenroseContext *ctx,
+    bool (*inbounds)(void *inboundsctx,
+                     const PenroseTriangle *tri), void *inboundsctx,
+    void (*tile)(void *tilectx, const Point *vertices), void *tilectx);
+
+/* Subroutines that step around the tiling specified by a PenroseCtx,
+ * delivering both plane and combinatorial coordinates as they go */
+PenroseTriangle *penrose_initial(PenroseContext *ctx);
+PenroseTriangle *penrose_adjacent(PenroseContext *ctx,
+                                  const PenroseTriangle *src_spec,
+                                  unsigned src_edge, unsigned *dst_edge);
+
+/* For extracting the point coordinates */
+typedef struct Coord {
+    int c1, cr5;      /* coefficients of 1 and sqrt(5) respectively */
+} Coord;
+
+static inline Coord point_x(Point p)
+{
+    Coord x = {
+        4 * p.coeffs[0] + p.coeffs[1] - p.coeffs[2] + p.coeffs[3],
+        p.coeffs[1] + p.coeffs[2] - p.coeffs[3],
+    };
+    return x;
+}
+
+static inline Coord point_y(Point p)
+{
+    Coord y = {
+        2 * p.coeffs[1] + p.coeffs[2] + p.coeffs[3],
+        p.coeffs[2] + p.coeffs[3],
+    };
+    return y;
+}
+
+static inline int coord_sign(Coord x)
+{
+    if (x.c1 == 0 && x.cr5 == 0)
+        return 0;
+    if (x.c1 >= 0 && x.cr5 >= 0)
+        return +1;
+    if (x.c1 <= 0 && x.cr5 <= 0)
+        return -1;
+
+    if (x.c1 * x.c1 > 5 * x.cr5 * x.cr5)
+        return x.c1 < 0 ? -1 : +1;
+    else
+        return x.cr5 < 0 ? -1 : +1;
+}
+
+static inline Coord coord_construct(int c1, int cr5)
+{
+    Coord c = { c1, cr5 };
+    return c;
+}
+
+static inline Coord coord_integer(int c1)
+{
+    return coord_construct(c1, 0);
+}
+
+static inline Coord coord_add(Coord a, Coord b)
+{
+    Coord sum;
+    sum.c1 = a.c1 + b.c1;
+    sum.cr5 = a.cr5 + b.cr5;
+    return sum;
+}
+
+static inline Coord coord_sub(Coord a, Coord b)
+{
+    Coord diff;
+    diff.c1 = a.c1 - b.c1;
+    diff.cr5 = a.cr5 - b.cr5;
+    return diff;
+}
+
+static inline Coord coord_mul(Coord a, Coord b)
+{
+    Coord prod;
+    prod.c1 = a.c1 * b.c1 + 5 * a.cr5 * b.cr5;
+    prod.cr5 = a.c1 * b.cr5 + a.cr5 * b.c1;
+    return prod;
+}
+
+static inline Coord coord_abs(Coord a)
+{
+    int sign = coord_sign(a);
+    Coord abs;
+    abs.c1 = a.c1 * sign;
+    abs.cr5 = a.cr5 * sign;
+    return abs;
+}
+
+static inline int coord_cmp(Coord a, Coord b)
+{
+    return coord_sign(coord_sub(a, b));
+}