shithub: puzzles

Download patch

ref: 83244294f56cbf4c6ac03564489d1775054bbcfc
parent: 71e1776094aa9240e9772b7fbc99dd5e2f4e1acb
author: Simon Tatham <[email protected]>
date: Sun Apr 2 06:42:42 EDT 2023 

Move other test main()s out of library source files.

Having stated the principle in the previous commit, I should apply it
consistently. A source file linked into the Puzzles library of common
support code should not also define a main() under ifdef.

This commit only goes as far as the _library_ support modules. It
would be a much bigger job to do the same for all the actual _puzzles_
that have test main()s or standalone-solver main()s. And it's not
necessary, because modifying one of those source files only triggers a
rebuild of _one_ puzzle, not absolutely everything. (Not to mention
that it's quite likely the puzzle and the test main() will need to be
modified in conjunction anyway.)

As in the previous commit, this has required exposing a few internal
API functions as global, and maybe editing them a bit. In particular,
the one-shot internal function that divvy_rectangle() loops on until
it succeeds is now exposed as divvy_rectangle_attempt(), which means
the test program doesn't have to condition a failure counter into the
real function.

I've thrown away penrose-vector-test completely, because that didn't
look like a test program with any ongoing use at all - it was surely
vestigial, while James was getting the vector representation up and
running in the first place.


--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -266,16 +266,6 @@
 add_subdirectory(unfinished)
 add_subdirectory(auxiliary)
 
-cliprogram(obfusc obfusc.c)
-cliprogram(latincheck latin.c COMPILE_DEFINITIONS STANDALONE_LATIN_TEST)
-cliprogram(matching matching.c COMPILE_DEFINITIONS STANDALONE_MATCHING_TEST)
-cliprogram(combi combi.c COMPILE_DEFINITIONS STANDALONE_COMBI_TEST)
-cliprogram(divvy divvy.c COMPILE_DEFINITIONS TESTMODE)
-cliprogram(penrose-test penrose.c COMPILE_DEFINITIONS TEST_PENROSE)
-cliprogram(penrose-vector-test penrose.c COMPILE_DEFINITIONS TEST_VECTORS)
-cliprogram(sort-test sort.c COMPILE_DEFINITIONS SORT_TEST)
-cliprogram(tree234-test tree234.c COMPILE_DEFINITIONS TEST)
-
 if(build_cli_programs)
   write_generated_games_header()
   include(CheckFunctionExists)
--- a/auxiliary/CMakeLists.txt
+++ b/auxiliary/CMakeLists.txt
@@ -1,2 +1,10 @@
+cliprogram(combi-test combi-test.c)
+cliprogram(divvy-test divvy-test.c)
 cliprogram(hatgen hatgen.c COMPILE_DEFINITIONS TEST_HAT)
 cliprogram(hat-test hat-test.c)
+cliprogram(latin-test latin-test.c)
+cliprogram(matching matching.c)
+cliprogram(obfusc obfusc.c)
+cliprogram(penrose-test penrose-test.c)
+cliprogram(sort-test sort-test.c)
+cliprogram(tree234-test tree234-test.c)
--- /dev/null
+++ b/auxiliary/combi-test.c
@@ -1,0 +1,25 @@
+#include <stdio.h>
+#include "puzzles.h"
+
+int main(int argc, char *argv[])
+{
+    combi_ctx *c;
+    int i, r, n;
+
+    if (argc < 3) {
+        fprintf(stderr, "Usage: combi R N\n");
+        exit(1);
+    }
+
+    r = atoi(argv[1]); n = atoi(argv[2]);
+    c = new_combi(r, n);
+    printf("combi %d of %d, %d elements.\n", c->r, c->n, c->total);
+
+    while (next_combi(c)) {
+        for (i = 0; i < c->r; i++) {
+            printf("%d ", c->a[i]);
+        }
+        printf("\n");
+    }
+    free_combi(c);
+}
--- /dev/null
+++ b/auxiliary/divvy-test.c
@@ -1,0 +1,103 @@
+#include <assert.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stddef.h>
+
+#include "puzzles.h"
+
+int main(int argc, char **argv)
+{
+    int *dsf;
+    int i;
+    int w = 9, h = 4, k = 6, tries = 100;
+    random_state *rs;
+    int fail_counter = 0;
+
+    rs = random_new("123456", 6);
+
+    if (argc > 1)
+	w = atoi(argv[1]);
+    if (argc > 2)
+	h = atoi(argv[2]);
+    if (argc > 3)
+	k = atoi(argv[3]);
+    if (argc > 4)
+	tries = atoi(argv[4]);
+
+    for (i = 0; i < tries; i++) {
+	int x, y;
+
+        while ((dsf = divvy_rectangle_attempt(w, h, k, rs)) == NULL)
+            fail_counter++;
+
+	for (y = 0; y <= 2*h; y++) {
+	    for (x = 0; x <= 2*w; x++) {
+		int miny = y/2 - 1 /*, maxy = y/2 */;
+		int minx = x/2 - 1 /*, maxx = x/2 */;
+		int classes[4], tx, ty;
+		for (ty = 0; ty < 2; ty++)
+		    for (tx = 0; tx < 2; tx++) {
+			int cx = minx+tx, cy = miny+ty;
+			if (cx < 0 || cx >= w || cy < 0 || cy >= h)
+			    classes[ty*2+tx] = -1;
+			else
+			    classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
+		    }
+		switch (y%2 * 2 + x%2) {
+		  case 0:	       /* corner */
+		    /*
+		     * Cases for the corner:
+		     *
+		     * 	- if all four surrounding squares belong
+		     * 	  to the same omino, we print a space.
+		     *
+		     * 	- if the top two are the same and the
+		     * 	  bottom two are the same, we print a
+		     * 	  horizontal line.
+		     *
+		     * 	- if the left two are the same and the
+		     * 	  right two are the same, we print a
+		     * 	  vertical line.
+		     *
+		     *  - otherwise, we print a cross.
+		     */
+		    if (classes[0] == classes[1] &&
+			classes[1] == classes[2] &&
+			classes[2] == classes[3])
+			printf(" ");
+		    else if (classes[0] == classes[1] &&
+			     classes[2] == classes[3])
+			printf("-");
+		    else if (classes[0] == classes[2] &&
+			     classes[1] == classes[3])
+			printf("|");
+		    else
+			printf("+");
+		    break;
+		  case 1:	       /* horiz edge */
+		    if (classes[1] == classes[3])
+			printf("  ");
+		    else
+			printf("--");
+		    break;
+		  case 2:	       /* vert edge */
+		    if (classes[2] == classes[3])
+			printf(" ");
+		    else
+			printf("|");
+		    break;
+		  case 3:	       /* square centre */
+		    printf("  ");
+		    break;
+		}
+	    }
+	    printf("\n");
+	}
+	printf("\n");
+	sfree(dsf);
+    }
+
+    printf("%d retries needed for %d successes\n", fail_counter, tries);
+
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/latin-test.c
@@ -1,0 +1,110 @@
+#include <stdio.h>
+#include <string.h>
+#include <time.h>
+
+#include "puzzles.h"
+#include "latin.h"
+
+static const char *quis;
+
+#define ELT(sq,x,y) (sq[((y)*order)+(x)])
+
+static void latin_print(digit *sq, int order)
+{
+    int x, y;
+
+    for (y = 0; y < order; y++) {
+	for (x = 0; x < order; x++) {
+	    printf("%2u ", ELT(sq, x, y));
+	}
+	printf("\n");
+    }
+    printf("\n");
+}
+
+static void gen(int order, random_state *rs, int debug)
+{
+    digit *sq;
+
+    sq = latin_generate(order, rs);
+    latin_print(sq, order);
+    if (latin_check(sq, order)) {
+	fprintf(stderr, "Square is not a latin square!");
+	exit(1);
+    }
+
+    sfree(sq);
+}
+
+static void test_soak(int order, random_state *rs)
+{
+    digit *sq;
+    int n = 0;
+    time_t tt_start, tt_now, tt_last;
+
+    tt_now = tt_start = time(NULL);
+
+    while(1) {
+        sq = latin_generate(order, rs);
+        sfree(sq);
+        n++;
+
+        tt_last = time(NULL);
+        if (tt_last > tt_now) {
+            tt_now = tt_last;
+            printf("%d total, %3.1f/s\n", n,
+                   (double)n / (double)(tt_now - tt_start));
+        }
+    }
+}
+
+static void usage_exit(const char *msg)
+{
+    if (msg)
+        fprintf(stderr, "%s: %s\n", quis, msg);
+    fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
+    exit(1);
+}
+
+int main(int argc, char *argv[])
+{
+    int i, soak = 0;
+    random_state *rs;
+    time_t seed = time(NULL);
+
+    quis = argv[0];
+    while (--argc > 0) {
+	const char *p = *++argv;
+	if (!strcmp(p, "--soak"))
+	    soak = 1;
+	else if (!strcmp(p, "--seed")) {
+	    if (argc == 0)
+		usage_exit("--seed needs an argument");
+	    seed = (time_t)atoi(*++argv);
+	    argc--;
+	} else if (*p == '-')
+		usage_exit("unrecognised option");
+	else
+	    break; /* finished options */
+    }
+
+    rs = random_new((void*)&seed, sizeof(time_t));
+
+    if (soak == 1) {
+	if (argc != 1) usage_exit("only one argument for --soak");
+	test_soak(atoi(*argv), rs);
+    } else {
+	if (argc > 0) {
+	    for (i = 0; i < argc; i++) {
+		gen(atoi(*argv++), rs, 1);
+	    }
+	} else {
+	    while (1) {
+		i = random_upto(rs, 20) + 1;
+		gen(i, rs, 0);
+	    }
+	}
+    }
+    random_free(rs);
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/matching.c
@@ -1,0 +1,397 @@
+/*
+ * Standalone tool to run the matching algorithm.
+ */
+
+#include <assert.h>
+#include <ctype.h>
+#include <string.h>
+#include <time.h>
+
+#include "puzzles.h"
+#include "matching.h"
+#include "tree234.h"
+
+static int nl, nr, count;
+static int **adjlists, *adjsizes;
+static int *adjdata, *outl, *outr, *witness;
+static void *scratch;
+static random_state *rs;
+
+static void allocate(int nl_, int nr_, int maxedges)
+{
+    nl = nl_;
+    nr = nr_;
+    adjdata = snewn(maxedges, int);
+    adjlists = snewn(nl, int *);
+    adjsizes = snewn(nl, int);
+    outl = snewn(nl, int);
+    outr = snewn(nr, int);
+    witness = snewn(nl+nr, int);
+    scratch = smalloc(matching_scratch_size(nl, nr));
+}
+
+static void deallocate(void)
+{
+    sfree(adjlists);
+    sfree(adjsizes);
+    sfree(adjdata);
+    sfree(outl);
+    sfree(outr);
+    sfree(witness);
+    sfree(scratch);
+}
+
+static void find_and_check_matching(void)
+{
+    int i, j, k;
+
+    count = matching_with_scratch(scratch, nl, nr, adjlists, adjsizes,
+                                  rs, outl, outr);
+    matching_witness(scratch, nl, nr, witness);
+
+    for (i = j = 0; i < nl; i++) {
+        if (outl[i] != -1) {
+            assert(0 <= outl[i] && outl[i] < nr);
+            assert(outr[outl[i]] == i);
+            j++;
+
+            for (k = 0; k < adjsizes[i]; k++)
+                if (adjlists[i][k] == outl[i])
+                    break;
+            assert(k < adjsizes[i]);
+        }
+    }
+    assert(j == count);
+
+    for (i = j = 0; i < nr; i++) {
+        if (outr[i] != -1) {
+            assert(0 <= outr[i] && outr[i] < nl);
+            assert(outl[outr[i]] == i);
+            j++;
+        }
+    }
+    assert(j == count);
+
+    for (i = 0; i < nl; i++) {
+        if (outl[i] == -1)
+            assert(witness[i] == 0);
+    }
+    for (i = 0; i < nr; i++) {
+        if (outr[i] == -1)
+            assert(witness[nl+i] == 1);
+    }
+    for (i = 0; i < nl; i++) {
+        for (j = 0; j < adjsizes[i]; j++) {
+            k = adjlists[i][j];
+
+            if (outl[i] == k)
+                assert(!(witness[i] == 1 && witness[nl+k] == 0));
+            else
+                assert(!(witness[i] == 0 && witness[nl+k] == 1));
+        }
+    }
+}
+
+struct nodename {
+    const char *name;
+    int index;
+};
+
+static int compare_nodes(void *av, void *bv)
+{
+    const struct nodename *a = (const struct nodename *)av;
+    const struct nodename *b = (const struct nodename *)bv;
+    return strcmp(a->name, b->name);
+}
+
+static int node_index(tree234 *n2i, tree234 *i2n, const char *name)
+{
+    struct nodename *nn, *nn_prev;
+    char *namedup = dupstr(name);
+
+    nn = snew(struct nodename);
+    nn->name = namedup;
+    nn->index = count234(n2i);
+
+    nn_prev = add234(n2i, nn);
+    if (nn_prev != nn) {
+        sfree(nn);
+        sfree(namedup);
+    } else {
+        addpos234(i2n, nn, nn->index);
+    }
+
+    return nn_prev->index;
+}
+
+struct edge {
+    int L, R;
+};
+
+static int compare_edges(void *av, void *bv)
+{
+    const struct edge *a = (const struct edge *)av;
+    const struct edge *b = (const struct edge *)bv;
+    if (a->L < b->L) return -1;
+    if (a->L > b->L) return +1;
+    if (a->R < b->R) return -1;
+    if (a->R > b->R) return +1;
+    return 0;
+}
+
+static void matching_from_user_input(FILE *fp, const char *filename)
+{
+    tree234 *Ln2i, *Li2n, *Rn2i, *Ri2n, *edges;
+    char *line = NULL;
+    struct edge *e;
+    int i, lineno = 0;
+    int *adjptr;
+
+    Ln2i = newtree234(compare_nodes);
+    Rn2i = newtree234(compare_nodes);
+    Li2n = newtree234(NULL);
+    Ri2n = newtree234(NULL);
+    edges = newtree234(compare_edges);
+
+    while (sfree(line), lineno++, (line = fgetline(fp)) != NULL) {
+        char *p, *Lname, *Rname;
+
+        p = line;
+        while (*p && isspace((unsigned char)*p)) p++;
+        if (!*p)
+            continue;
+
+        Lname = p;
+        while (*p && !isspace((unsigned char)*p)) p++;
+        if (*p)
+            *p++ = '\0';
+        while (*p && isspace((unsigned char)*p)) p++;
+
+        if (!*p) {
+            fprintf(stderr, "%s:%d: expected 2 words, found 1\n",
+                    filename, lineno);
+            exit(1);
+        }
+
+        Rname = p;
+        while (*p && !isspace((unsigned char)*p)) p++;
+        if (*p)
+            *p++ = '\0';
+        while (*p && isspace((unsigned char)*p)) p++;
+
+        if (*p) {
+            fprintf(stderr, "%s:%d: expected 2 words, found more\n",
+                    filename, lineno);
+            exit(1);
+        }
+
+        e = snew(struct edge);
+        e->L = node_index(Ln2i, Li2n, Lname);
+        e->R = node_index(Rn2i, Ri2n, Rname);
+        if (add234(edges, e) != e) {
+            fprintf(stderr, "%s:%d: duplicate edge\n",
+                    filename, lineno);
+            exit(1);
+        }
+    }
+
+    allocate(count234(Ln2i), count234(Rn2i), count234(edges));
+
+    adjptr = adjdata;
+    for (i = 0; i < nl; i++)
+        adjlists[i] = NULL;
+    for (i = 0; (e = index234(edges, i)) != NULL; i++) {
+        if (!adjlists[e->L])
+            adjlists[e->L] = adjptr;
+        *adjptr++ = e->R;
+        adjsizes[e->L] = adjptr - adjlists[e->L];
+    }
+
+    find_and_check_matching();
+
+    for (i = 0; i < nl; i++) {
+        if (outl[i] != -1) {
+            struct nodename *Lnn = index234(Li2n, i);
+            struct nodename *Rnn = index234(Ri2n, outl[i]);
+            printf("%s %s\n", Lnn->name, Rnn->name);
+        }
+    }
+    deallocate();
+}
+
+static void test_subsets(void)
+{
+    int b = 8;
+    int n = 1 << b;
+    int i, j, nruns, expected_size;
+    int *adjptr;
+    int *edgecounts;
+    struct stats {
+        int min, max;
+        double n, sx, sxx;
+    } *stats;
+    static const char seed[] = "fixed random seed for repeatability";
+
+    /*
+     * Generate a graph in which every subset of [b] = {1,...,b}
+     * (represented as a b-bit integer 0 <= i < n) has an edge going
+     * to every subset obtained by removing exactly one element.
+     *
+     * This graph is the disjoint union of the corresponding graph for
+     * each layer (collection of same-sized subset) of the power set
+     * of [b]. Each of those graphs has a matching of size equal to
+     * the smaller of its vertex sets. So we expect the overall size
+     * of the output matching to be less than n by the size of the
+     * largest layer, that is, to be n - binomial(n, floor(n/2)).
+     *
+     * We run the generation repeatedly, randomising it every time,
+     * and we expect to see every possible edge appear sooner or
+     * later.
+     */
+
+    rs = random_new(seed, strlen(seed));
+
+    allocate(n, n, n*b);
+    adjptr = adjdata;
+    expected_size = 0;
+    for (i = 0; i < n; i++) {
+        adjlists[i] = adjptr;
+        for (j = 0; j < b; j++) {
+            if (i & (1 << j))
+                *adjptr++ = i & ~(1 << j);
+        }
+        adjsizes[i] = adjptr - adjlists[i];
+        if (adjsizes[i] != b/2)
+            expected_size++;
+    }
+
+    edgecounts = snewn(n*b, int);
+    for (i = 0; i < n*b; i++)
+        edgecounts[i] = 0;
+
+    stats = snewn(b, struct stats);
+
+    nruns = 0;
+    while (nruns < 10000) {
+        nruns++;
+        find_and_check_matching();
+        assert(count == expected_size);
+
+        for (i = 0; i < n; i++)
+            for (j = 0; j < b; j++)
+                if ((i ^ outl[i]) == (1 << j))
+                    edgecounts[b*i+j]++;
+
+        if (nruns % 1000 == 0) {
+            for (i = 0; i < b; i++) {
+                struct stats *st = &stats[i];
+                st->min = st->max = -1;
+                st->n = st->sx = st->sxx = 0;
+            }
+
+            for (i = 0; i < n; i++) {
+                int pop = 0;
+                for (j = 0; j < b; j++)
+                    if (i & (1 << j))
+                        pop++;
+                pop--;
+
+                for (j = 0; j < b; j++) {
+                    if (i & (1 << j)) {
+                        struct stats *st = &stats[pop];
+                        int x = edgecounts[b*i+j];
+                        if (st->max == -1 || st->max < x)
+                            st->max = x;
+                        if (st->min == -1 || st->min > x)
+                            st->min = x;
+                        st->n++;
+                        st->sx += x;
+                        st->sxx += (double)x*x;
+                    } else {
+                        assert(edgecounts[b*i+j] == 0);
+                    }
+                }
+            }
+        }
+    }
+
+    printf("after %d runs:\n", nruns);
+    for (j = 0; j < b; j++) {
+        struct stats *st = &stats[j];
+        printf("edges between layers %d,%d:"
+               " min=%d max=%d mean=%f variance=%f\n",
+               j, j+1, st->min, st->max, st->sx/st->n,
+               (st->sxx - st->sx*st->sx/st->n) / st->n);
+    }
+    sfree(edgecounts);
+    deallocate();
+}
+
+int main(int argc, char **argv)
+{
+    static const char stdin_identifier[] = "<standard input>";
+    const char *infile = NULL;
+    bool doing_opts = true;
+    enum { USER_INPUT, AUTOTEST } mode = USER_INPUT;
+
+    while (--argc > 0) {
+        const char *arg = *++argv;
+
+        if (doing_opts && arg[0] == '-' && arg[1]) {
+            if (!strcmp(arg, "--")) {
+                doing_opts = false;
+            } else if (!strcmp(arg, "--random")) {
+                char buf[64];
+                int len = sprintf(buf, "%lu", (unsigned long)time(NULL));
+                rs = random_new(buf, len);
+            } else if (!strcmp(arg, "--autotest")) {
+                mode = AUTOTEST;
+            } else {
+                fprintf(stderr, "matching: unrecognised option '%s'\n", arg);
+                return 1;
+            }
+        } else {
+            if (!infile) {
+                infile = (!strcmp(arg, "-") ? stdin_identifier : arg);
+            } else {
+                fprintf(stderr, "matching: too many arguments\n");
+                return 1;
+            }
+        }
+    }
+
+    if (mode == USER_INPUT) {
+        FILE *fp;
+
+        if (!infile)
+            infile = stdin_identifier;
+
+        if (infile != stdin_identifier) {
+            fp = fopen(infile, "r");
+            if (!fp) {
+                fprintf(stderr, "matching: could not open input file '%s'\n",
+                        infile);
+                return 1;
+            }
+        } else {
+            fp = stdin;
+        }
+
+        matching_from_user_input(fp, infile);
+
+        if (infile != stdin_identifier)
+            fclose(fp);
+    }
+
+    if (mode == AUTOTEST) {
+        if (infile) {
+            fprintf(stderr, "matching: expected no filename argument "
+                    "with --autotest\n");
+            return 1;
+        }
+
+        test_subsets();
+    }
+
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/obfusc.c
@@ -1,0 +1,130 @@
+/*
+ * Stand-alone tool to access the Puzzles obfuscation algorithm.
+ * 
+ * To deobfuscate, use "obfusc -d":
+ * 
+ *   obfusc -d                 reads binary data from stdin, writes to stdout
+ *   obfusc -d <hex string>    works on the given hex string instead of stdin
+ *   obfusc -d -h              writes a hex string instead of binary to stdout
+ *
+ * To obfuscate, "obfusc -e":
+ * 
+ *   obfusc -e                 reads binary from stdin, writes hex to stdout
+ *   obfusc -e <hex string>    works on the given hex string instead of stdin
+ *   obfusc -e -b              writes binary instead of text to stdout
+ *
+ * The default output format is hex for -e and binary for -d
+ * because that's the way obfuscation is generally used in
+ * Puzzles. Either of -b and -h can always be specified to set it
+ * explicitly.
+ *
+ * Data read from standard input is assumed always to be binary;
+ * data provided on the command line is taken to be hex.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdarg.h>
+#include <string.h>
+#include <errno.h>
+
+#include "puzzles.h"
+
+int main(int argc, char **argv)
+{
+    enum { BINARY, DEFAULT, HEX } outputmode = DEFAULT;
+    char *inhex = NULL;
+    unsigned char *data;
+    int datalen;
+    enum { UNKNOWN, DECODE, ENCODE } mode = UNKNOWN;
+    bool doing_opts = true;
+
+    while (--argc > 0) {
+	char *p = *++argv;
+
+	if (doing_opts && *p == '-') {
+	    if (!strcmp(p, "--")) {
+		doing_opts = 0;
+		continue;
+	    }
+	    p++;
+	    while (*p) {
+		switch (*p) {
+		  case 'e':
+		    mode = ENCODE;
+		    break;
+		  case 'd':
+		    mode = DECODE;
+		    break;
+		  case 'b':
+		    outputmode = BINARY;
+		    break;
+		  case 'h':
+		    outputmode = HEX;
+		    break;
+		  default:
+		    fprintf(stderr, "obfusc: unrecognised option '-%c'\n",
+			    *p);
+		    return 1;
+		}
+		p++;
+	    }
+	} else {
+	    if (!inhex) {
+		inhex = p;
+	    } else {
+		fprintf(stderr, "obfusc: expected at most one argument\n");
+		return 1;
+	    }
+	}
+    }
+
+    if (mode == UNKNOWN) {
+	fprintf(stderr, "usage: obfusc < -e | -d > [ -b | -h ] [hex data]\n");
+	return 0;
+    }
+
+    if (outputmode == DEFAULT)
+	outputmode = (mode == DECODE ? BINARY : HEX);
+
+    if (inhex) {
+	datalen = strlen(inhex) / 2;
+	data = hex2bin(inhex, datalen);
+    } else {
+	int datasize = 4096;
+	datalen = 0;
+	data = snewn(datasize, unsigned char);
+	while (1) {
+	    int ret = fread(data + datalen, 1, datasize - datalen, stdin);
+	    if (ret < 0) {
+		fprintf(stderr, "obfusc: read: %s\n", strerror(errno));
+		return 1;
+	    } else if (ret == 0) {
+		break;
+	    } else {
+		datalen += ret;
+		if (datasize - datalen < 4096) {
+		    datasize = datalen * 5 / 4 + 4096;
+		    data = sresize(data, datasize, unsigned char);
+		}
+	    }
+	}
+    }
+
+    obfuscate_bitmap(data, datalen * 8, mode == DECODE);
+
+    if (outputmode == BINARY) {
+	int ret = fwrite(data, 1, datalen, stdout);
+        if (ret < 0) {
+            fprintf(stderr, "obfusc: write: %s\n", strerror(errno));
+            return 1;
+        }
+    } else {
+	int i;
+	for (i = 0; i < datalen; i++)
+	    printf("%02x", data[i]);
+	printf("\n");
+    }
+
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/penrose-test.c
@@ -1,0 +1,95 @@
+#include <stdio.h>
+#include <string.h>
+
+#include "puzzles.h"
+#include "penrose.h"
+
+static int show_recursion = 0;
+static int ntiles, nfinal;
+
+static int test_cb(penrose_state *state, vector *vs, int n, int depth)
+{
+    int i, xoff = 0, yoff = 0;
+    double l = penrose_side_length(state->start_size, depth);
+    double rball = l / 10.0;
+    const char *col;
+
+    ntiles++;
+    if (state->max_depth == depth) {
+        col = n == 4 ? "black" : "green";
+        nfinal++;
+    } else {
+        if (!show_recursion)
+            return 0;
+        col = n == 4 ? "red" : "blue";
+    }
+    if (n != 4) yoff = state->start_size;
+
+    printf("<polygon points=\"");
+    for (i = 0; i < n; i++) {
+        printf("%s%f,%f", (i == 0) ? "" : " ",
+               v_x(vs, i) + xoff, v_y(vs, i) + yoff);
+    }
+    printf("\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n", col, col);
+    printf("<ellipse cx=\"%f\" cy=\"%f\" rx=\"%f\" ry=\"%f\" fill=\"%s\" />",
+           v_x(vs, 0) + xoff, v_y(vs, 0) + yoff, rball, rball, col);
+
+    return 0;
+}
+
+static void usage_exit(void)
+{
+    fprintf(stderr, "Usage: penrose-test [--recursion] P2|P3 SIZE DEPTH\n");
+    exit(1);
+}
+
+int main(int argc, char *argv[])
+{
+    penrose_state ps;
+    int which = 0;
+
+    while (--argc > 0) {
+        char *p = *++argv;
+        if (!strcmp(p, "-h") || !strcmp(p, "--help")) {
+            usage_exit();
+        } else if (!strcmp(p, "--recursion")) {
+            show_recursion = 1;
+        } else if (*p == '-') {
+            fprintf(stderr, "Unrecognised option '%s'\n", p);
+            exit(1);
+        } else {
+            break;
+        }
+    }
+
+    if (argc < 3) usage_exit();
+
+    if (strcmp(argv[0], "P2") == 0) which = PENROSE_P2;
+    else if (strcmp(argv[0], "P3") == 0) which = PENROSE_P3;
+    else usage_exit();
+
+    ps.start_size = atoi(argv[1]);
+    ps.max_depth = atoi(argv[2]);
+    ps.new_tile = test_cb;
+
+    ntiles = nfinal = 0;
+
+    printf("\
+<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\
+<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n\
+\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n\
+\n\
+<svg xmlns=\"http://www.w3.org/2000/svg\"\n\
+xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
+
+    printf("<g>\n");
+    penrose(&ps, which, 0);
+    printf("</g>\n");
+
+    printf("<!-- %d tiles and %d leaf tiles total -->\n",
+           ntiles, nfinal);
+
+    printf("</svg>");
+
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/sort-test.c
@@ -1,0 +1,70 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+#include "puzzles.h"
+
+static int testcmp(const void *av, const void *bv, void *ctx)
+{
+    int a = *(const int *)av, b = *(const int *)bv;
+    const int *keys = (const int *)ctx;
+    return keys[a] < keys[b] ? -1 : keys[a] > keys[b] ? +1 : 0;
+}
+
+static int resetcmp(const void *av, const void *bv)
+{
+    int a = *(const int *)av, b = *(const int *)bv;
+    return a < b ? -1 : a > b ? +1 : 0;
+}
+
+int main(int argc, char **argv)
+{
+    typedef int Array[3723];
+    Array data, keys;
+    int iteration;
+    unsigned seed;
+
+    seed = (argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL));
+    printf("Random seed = %u\n", seed);
+    srand(seed);
+
+    for (iteration = 0; iteration < 10000; iteration++) {
+        int j;
+        const char *fail = NULL;
+
+        for (j = 0; j < lenof(data); j++) {
+            data[j] = j;
+            keys[j] = rand();
+        }
+
+        arraysort(data, lenof(data), testcmp, keys);
+
+        for (j = 1; j < lenof(data); j++) {
+            if (keys[data[j]] < keys[data[j-1]])
+                fail = "output misordered";
+        }
+        if (!fail) {
+            Array reset;
+            memcpy(reset, data, sizeof(data));
+            qsort(reset, lenof(reset), sizeof(*reset), resetcmp);
+            for (j = 0; j < lenof(reset); j++)
+                if (reset[j] != j)
+                    fail = "output not permuted";
+        }
+
+        if (fail) {
+            printf("Failed at iteration %d: %s\n", iteration, fail);
+            printf("Key values:\n");
+            for (j = 0; j < lenof(keys); j++)
+                printf("  [%2d] %10d\n", j, keys[j]);
+            printf("Output sorted order:\n");
+            for (j = 0; j < lenof(data); j++)
+                printf("  [%2d] %10d\n", data[j], keys[data[j]]);
+            return 1;
+        }
+    }
+
+    printf("OK\n");
+    return 0;
+}
--- /dev/null
+++ b/auxiliary/tree234-test.c
@@ -1,0 +1,746 @@
+/*
+ * Test code for the 2-3-4 tree. This code maintains an alternative
+ * representation of the data in the tree, in an array (using the
+ * obvious and slow insert and delete functions). After each tree
+ * operation, the verify() function is called, which ensures all
+ * the tree properties are preserved:
+ *  - node->child->parent always equals node
+ *  - tree->root->parent always equals NULL
+ *  - number of kids == 0 or number of elements + 1;
+ *  - tree has the same depth everywhere
+ *  - every node has at least one element
+ *  - subtree element counts are accurate
+ *  - any NULL kid pointer is accompanied by a zero count
+ *  - in a sorted tree: ordering property between elements of a
+ *    node and elements of its children is preserved
+ * and also ensures the list represented by the tree is the same
+ * list it should be. (This last check also doubly verifies the
+ * ordering properties, because the `same list it should be' is by
+ * definition correctly ordered. It also ensures all nodes are
+ * distinct, because the enum functions would get caught in a loop
+ * if not.)
+ */
+
+#include <assert.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "puzzles.h"
+
+#define TREE234_INTERNALS
+#include "tree234.h"
+
+/*
+ * Error reporting function.
+ */
+static void error(const char *fmt, ...) {
+    va_list ap;
+    printf("ERROR: ");
+    va_start(ap, fmt);
+    vfprintf(stdout, fmt, ap);
+    va_end(ap);
+    printf("\n");
+}
+
+/* The array representation of the data. */
+static void **array;
+static int arraylen, arraysize;
+static cmpfn234 cmp;
+
+/* The tree representation of the same data. */
+static tree234 *tree;
+
+/*
+ * Routines to provide a diagnostic printout of a tree. Currently
+ * relies on every element in the tree being a one-character string
+ * :-)
+ */
+typedef struct {
+    char **levels;
+} dispctx;
+
+static int dispnode(node234 *n, int level, dispctx *ctx) {
+    if (level == 0) {
+	int xpos = strlen(ctx->levels[0]);
+	int len;
+
+	if (n->elems[2])
+	    len = sprintf(ctx->levels[0]+xpos, " %s%s%s",
+			  (char *)n->elems[0], (char *)n->elems[1],
+                          (char *)n->elems[2]);
+	else if (n->elems[1])
+	    len = sprintf(ctx->levels[0]+xpos, " %s%s",
+			  (char *)n->elems[0], (char *)n->elems[1]);
+	else
+	    len = sprintf(ctx->levels[0]+xpos, " %s",
+			  (char *)n->elems[0]);
+	return xpos + 1 + (len-1) / 2;
+    } else {
+	int xpos[4], nkids;
+	int nodelen, mypos, myleft, x, i;
+
+	xpos[0] = dispnode(n->kids[0], level-3, ctx);
+	xpos[1] = dispnode(n->kids[1], level-3, ctx);
+	nkids = 2;
+	if (n->kids[2]) {
+	    xpos[2] = dispnode(n->kids[2], level-3, ctx);
+	    nkids = 3;
+	}
+	if (n->kids[3]) {
+	    xpos[3] = dispnode(n->kids[3], level-3, ctx);
+	    nkids = 4;
+	}
+
+	if (nkids == 4)
+	    mypos = (xpos[1] + xpos[2]) / 2;
+	else if (nkids == 3)
+	    mypos = xpos[1];
+	else
+	    mypos = (xpos[0] + xpos[1]) / 2;
+	nodelen = nkids * 2 - 1;
+	myleft = mypos - ((nodelen-1)/2);
+	assert(myleft >= xpos[0]);
+	assert(myleft + nodelen-1 <= xpos[nkids-1]);
+
+	x = strlen(ctx->levels[level]);
+	while (x <= xpos[0] && x < myleft)
+	    ctx->levels[level][x++] = ' ';
+	while (x < myleft)
+	    ctx->levels[level][x++] = '_';
+	if (nkids==4)
+	    x += sprintf(ctx->levels[level]+x, ".%s.%s.%s.",
+			 (char *)n->elems[0], (char *)n->elems[1],
+                         (char *)n->elems[2]);
+	else if (nkids==3)
+	    x += sprintf(ctx->levels[level]+x, ".%s.%s.",
+			 (char *)n->elems[0], (char *)n->elems[1]);
+	else
+	    x += sprintf(ctx->levels[level]+x, ".%s.",
+			 (char *)n->elems[0]);
+	while (x < xpos[nkids-1])
+	    ctx->levels[level][x++] = '_';
+	ctx->levels[level][x] = '\0';
+
+	x = strlen(ctx->levels[level-1]);
+	for (i = 0; i < nkids; i++) {
+	    int rpos, pos;
+	    rpos = xpos[i];
+	    if (i > 0 && i < nkids-1)
+		pos = myleft + 2*i;
+	    else
+		pos = rpos;
+	    if (rpos < pos)
+		rpos++;
+	    while (x < pos && x < rpos)
+		ctx->levels[level-1][x++] = ' ';
+	    if (x == pos)
+		ctx->levels[level-1][x++] = '|';
+	    while (x < pos || x < rpos)
+		ctx->levels[level-1][x++] = '_';
+	    if (x == pos)
+		ctx->levels[level-1][x++] = '|';
+	}
+	ctx->levels[level-1][x] = '\0';
+
+	x = strlen(ctx->levels[level-2]);
+	for (i = 0; i < nkids; i++) {
+	    int rpos = xpos[i];
+
+	    while (x < rpos)
+		ctx->levels[level-2][x++] = ' ';
+	    ctx->levels[level-2][x++] = '|';
+	}
+	ctx->levels[level-2][x] = '\0';
+
+	return mypos;
+    }
+}
+
+static void disptree(tree234 *t) {
+    dispctx ctx;
+    char *leveldata;
+    int width = count234(t);
+    int ht = height234(t) * 3 - 2;
+    int i;
+
+    if (!t->root) {
+	printf("[empty tree]\n");
+    }
+
+    leveldata = smalloc(ht * (width+2));
+    ctx.levels = smalloc(ht * sizeof(char *));
+    for (i = 0; i < ht; i++) {
+	ctx.levels[i] = leveldata + i * (width+2);
+	ctx.levels[i][0] = '\0';
+    }
+
+    (void) dispnode(t->root, ht-1, &ctx);
+
+    for (i = ht; i-- ;)
+	printf("%s\n", ctx.levels[i]);
+
+    sfree(ctx.levels);
+    sfree(leveldata);
+}
+
+typedef struct {
+    int treedepth;
+    int elemcount;
+} chkctx;
+
+static int chknode(chkctx *ctx, int level, node234 *node,
+                   void *lowbound, void *highbound) {
+    int nkids, nelems;
+    int i;
+    int count;
+
+    /* Count the non-NULL kids. */
+    for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
+    /* Ensure no kids beyond the first NULL are non-NULL. */
+    for (i = nkids; i < 4; i++)
+        if (node->kids[i]) {
+            error("node %p: nkids=%d but kids[%d] non-NULL",
+                   node, nkids, i);
+        } else if (node->counts[i]) {
+            error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
+                   node, i, i, node->counts[i]);
+	}
+
+    /* Count the non-NULL elements. */
+    for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
+    /* Ensure no elements beyond the first NULL are non-NULL. */
+    for (i = nelems; i < 3; i++)
+        if (node->elems[i]) {
+            error("node %p: nelems=%d but elems[%d] non-NULL",
+                   node, nelems, i);
+        }
+
+    if (nkids == 0) {
+        /*
+         * If nkids==0, this is a leaf node; verify that the tree
+         * depth is the same everywhere.
+         */
+        if (ctx->treedepth < 0)
+            ctx->treedepth = level;    /* we didn't know the depth yet */
+        else if (ctx->treedepth != level)
+            error("node %p: leaf at depth %d, previously seen depth %d",
+                   node, level, ctx->treedepth);
+    } else {
+        /*
+         * If nkids != 0, then it should be nelems+1, unless nelems
+         * is 0 in which case nkids should also be 0 (and so we
+         * shouldn't be in this condition at all).
+         */
+        int shouldkids = (nelems ? nelems+1 : 0);
+        if (nkids != shouldkids) {
+            error("node %p: %d elems should mean %d kids but has %d",
+                   node, nelems, shouldkids, nkids);
+        }
+    }
+
+    /*
+     * nelems should be at least 1.
+     */
+    if (nelems == 0) {
+        error("node %p: no elems", node, nkids);
+    }
+
+    /*
+     * Add nelems to the running element count of the whole tree.
+     */
+    ctx->elemcount += nelems;
+
+    /*
+     * Check ordering property: all elements should be strictly >
+     * lowbound, strictly < highbound, and strictly < each other in
+     * sequence. (lowbound and highbound are NULL at edges of tree
+     * - both NULL at root node - and NULL is considered to be <
+     * everything and > everything. IYSWIM.)
+     */
+    if (cmp) {
+	for (i = -1; i < nelems; i++) {
+	    void *lower = (i == -1 ? lowbound : node->elems[i]);
+	    void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
+	    if (lower && higher && cmp(lower, higher) >= 0) {
+		error("node %p: kid comparison [%d=%s,%d=%s] failed",
+		      node, i, lower, i+1, higher);
+	    }
+	}
+    }
+
+    /*
+     * Check parent pointers: all non-NULL kids should have a
+     * parent pointer coming back to this node.
+     */
+    for (i = 0; i < nkids; i++)
+        if (node->kids[i]->parent != node) {
+            error("node %p kid %d: parent ptr is %p not %p",
+                   node, i, node->kids[i]->parent, node);
+        }
+
+
+    /*
+     * Now (finally!) recurse into subtrees.
+     */
+    count = nelems;
+
+    for (i = 0; i < nkids; i++) {
+        void *lower = (i == 0 ? lowbound : node->elems[i-1]);
+        void *higher = (i >= nelems ? highbound : node->elems[i]);
+	int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
+	if (node->counts[i] != subcount) {
+	    error("node %p kid %d: count says %d, subtree really has %d",
+		  node, i, node->counts[i], subcount);
+	}
+        count += subcount;
+    }
+
+    return count;
+}
+
+static void verifytree(tree234 *tree, void **array, int arraylen) {
+    chkctx ctx;
+    int i;
+    void *p;
+
+    ctx.treedepth = -1;                /* depth unknown yet */
+    ctx.elemcount = 0;                 /* no elements seen yet */
+    /*
+     * Verify validity of tree properties.
+     */
+    if (tree->root) {
+	if (tree->root->parent != NULL)
+	    error("root->parent is %p should be null", tree->root->parent);
+        chknode(&ctx, 0, tree->root, NULL, NULL);
+    }
+    printf("tree depth: %d\n", ctx.treedepth);
+    /*
+     * Enumerate the tree and ensure it matches up to the array.
+     */
+    for (i = 0; NULL != (p = index234(tree, i)); i++) {
+        if (i >= arraylen)
+            error("tree contains more than %d elements", arraylen);
+        if (array[i] != p)
+            error("enum at position %d: array says %s, tree says %s",
+                   i, array[i], p);
+    }
+    if (ctx.elemcount != i) {
+        error("tree really contains %d elements, enum gave %d",
+               ctx.elemcount, i);
+    }
+    if (i < arraylen) {
+        error("enum gave only %d elements, array has %d", i, arraylen);
+    }
+    i = count234(tree);
+    if (ctx.elemcount != i) {
+        error("tree really contains %d elements, count234 gave %d",
+	      ctx.elemcount, i);
+    }
+}
+static void verify(void) { verifytree(tree, array, arraylen); }
+
+static void internal_addtest(void *elem, int index, void *realret) {
+    int i, j;
+    void *retval;
+
+    if (arraysize < arraylen+1) {
+        arraysize = arraylen+1+256;
+        array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
+                 srealloc(array, arraysize*sizeof(*array)));
+    }
+
+    i = index;
+    /* now i points to the first element >= elem */
+    retval = elem;                  /* expect elem returned (success) */
+    for (j = arraylen; j > i; j--)
+	array[j] = array[j-1];
+    array[i] = elem;                /* add elem to array */
+    arraylen++;
+
+    if (realret != retval) {
+        error("add: retval was %p expected %p", realret, retval);
+    }
+
+    verify();
+}
+
+static void addtest(void *elem) {
+    int i;
+    void *realret;
+
+    realret = add234(tree, elem);
+
+    i = 0;
+    while (i < arraylen && cmp(elem, array[i]) > 0)
+        i++;
+    if (i < arraylen && !cmp(elem, array[i])) {
+        void *retval = array[i];       /* expect that returned not elem */
+	if (realret != retval) {
+	    error("add: retval was %p expected %p", realret, retval);
+	}
+    } else
+	internal_addtest(elem, i, realret);
+}
+
+static void addpostest(void *elem, int i) {
+    void *realret;
+
+    realret = addpos234(tree, elem, i);
+
+    internal_addtest(elem, i, realret);
+}
+
+static void delpostest(int i) {
+    int index = i;
+    void *elem = array[i], *ret;
+
+    /* i points to the right element */
+    while (i < arraylen-1) {
+	array[i] = array[i+1];
+	i++;
+    }
+    arraylen--;			       /* delete elem from array */
+
+    if (tree->cmp)
+	ret = del234(tree, elem);
+    else
+	ret = delpos234(tree, index);
+
+    if (ret != elem) {
+	error("del returned %p, expected %p", ret, elem);
+    }
+
+    verify();
+}
+
+static void deltest(void *elem) {
+    int i;
+
+    i = 0;
+    while (i < arraylen && cmp(elem, array[i]) > 0)
+        i++;
+    if (i >= arraylen || cmp(elem, array[i]) != 0)
+        return;                        /* don't do it! */
+    delpostest(i);
+}
+
+/* A sample data set and test utility. Designed for pseudo-randomness,
+ * and yet repeatability. */
+
+/*
+ * This random number generator uses the `portable implementation'
+ * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
+ * change it if not.
+ */
+static int randomnumber(unsigned *seed) {
+    *seed *= 1103515245;
+    *seed += 12345;
+    return ((*seed) / 65536) % 32768;
+}
+
+static int mycmp(void *av, void *bv) {
+    char const *a = (char const *)av;
+    char const *b = (char const *)bv;
+    return strcmp(a, b);
+}
+
+static const char *const strings_init[] = {
+    "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
+    "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
+    "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
+    "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
+    "m", "s", "l", "4",
+#if 0
+    "a", "ab", "absque", "coram", "de",
+    "palam", "clam", "cum", "ex", "e",
+    "sine", "tenus", "pro", "prae",
+    "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
+    "penguin", "blancmange", "pangolin", "whale", "hedgehog",
+    "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
+    "murfl", "spoo", "breen", "flarn", "octothorpe",
+    "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
+    "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
+    "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
+    "wand", "ring", "amulet"
+#endif
+};
+
+#define NSTR lenof(strings_init)
+static char *strings[NSTR];
+
+static void findtest(void) {
+    static const int rels[] = {
+	REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
+    };
+    static const char *const relnames[] = {
+	"EQ", "GE", "LE", "LT", "GT"
+    };
+    int i, j, rel, index;
+    char *p, *ret, *realret, *realret2;
+    int lo, hi, mid, c;
+
+    for (i = 0; i < (int)NSTR; i++) {
+	p = strings[i];
+	for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) {
+	    rel = rels[j];
+
+	    lo = 0; hi = arraylen-1;
+	    while (lo <= hi) {
+		mid = (lo + hi) / 2;
+		c = strcmp(p, array[mid]);
+		if (c < 0)
+		    hi = mid-1;
+		else if (c > 0)
+		    lo = mid+1;
+		else
+		    break;
+	    }
+
+	    if (c == 0) {
+		if (rel == REL234_LT)
+		    ret = (mid > 0 ? array[--mid] : NULL);
+		else if (rel == REL234_GT)
+		    ret = (mid < arraylen-1 ? array[++mid] : NULL);
+		else
+		    ret = array[mid];
+	    } else {
+		assert(lo == hi+1);
+		if (rel == REL234_LT || rel == REL234_LE) {
+		    mid = hi;
+		    ret = (hi >= 0 ? array[hi] : NULL);
+		} else if (rel == REL234_GT || rel == REL234_GE) {
+		    mid = lo;
+		    ret = (lo < arraylen ? array[lo] : NULL);
+		} else
+		    ret = NULL;
+	    }
+
+	    realret = findrelpos234(tree, p, NULL, rel, &index);
+	    if (realret != ret) {
+		error("find(\"%s\",%s) gave %s should be %s",
+		      p, relnames[j], realret, ret);
+	    }
+	    if (realret && index != mid) {
+		error("find(\"%s\",%s) gave %d should be %d",
+		      p, relnames[j], index, mid);
+	    }
+	    if (realret && rel == REL234_EQ) {
+		realret2 = index234(tree, index);
+		if (realret2 != realret) {
+		    error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
+			  p, relnames[j], realret, index, index, realret2);
+		}
+	    }
+#if 0
+	    printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
+		   realret, index);
+#endif
+	}
+    }
+
+    realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
+    if (arraylen && (realret != array[0] || index != 0)) {
+	error("find(NULL,GT) gave %s(%d) should be %s(0)",
+	      realret, index, array[0]);
+    } else if (!arraylen && (realret != NULL)) {
+	error("find(NULL,GT) gave %s(%d) should be NULL",
+	      realret, index);
+    }
+
+    realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
+    if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
+	error("find(NULL,LT) gave %s(%d) should be %s(0)",
+	      realret, index, array[arraylen-1]);
+    } else if (!arraylen && (realret != NULL)) {
+	error("find(NULL,LT) gave %s(%d) should be NULL",
+	      realret, index);
+    }
+}
+
+static void splittest(tree234 *tree, void **array, int arraylen) {
+    int i;
+    tree234 *tree3, *tree4;
+    for (i = 0; i <= arraylen; i++) {
+	tree3 = copytree234(tree, NULL, NULL);
+	tree4 = splitpos234(tree3, i, false);
+	verifytree(tree3, array, i);
+	verifytree(tree4, array+i, arraylen-i);
+	join234(tree3, tree4);
+	freetree234(tree4);	       /* left empty by join */
+	verifytree(tree3, array, arraylen);
+	freetree234(tree3);
+    }
+}
+
+int main(void) {
+    int in[NSTR];
+    int i, j, k;
+    int tworoot, tmplen;
+    unsigned seed = 0;
+    tree234 *tree2, *tree3, *tree4;
+
+    setvbuf(stdout, NULL, _IOLBF, 0);
+
+    for (i = 0; i < (int)NSTR; i++)
+        strings[i] = dupstr(strings_init[i]);
+
+    for (i = 0; i < (int)NSTR; i++) in[i] = 0;
+    array = NULL;
+    arraylen = arraysize = 0;
+    tree = newtree234(mycmp);
+    cmp = mycmp;
+
+    verify();
+    for (i = 0; i < 10000; i++) {
+        j = randomnumber(&seed);
+        j %= NSTR;
+        printf("trial: %d\n", i);
+        if (in[j]) {
+            printf("deleting %s (%d)\n", strings[j], j);
+            deltest(strings[j]);
+            in[j] = 0;
+        } else {
+            printf("adding %s (%d)\n", strings[j], j);
+            addtest(strings[j]);
+            in[j] = 1;
+        }
+	disptree(tree);
+	findtest();
+    }
+
+    while (arraylen > 0) {
+        j = randomnumber(&seed);
+        j %= arraylen;
+        deltest(array[j]);
+    }
+
+    freetree234(tree);
+
+    /*
+     * Now try an unsorted tree. We don't really need to test
+     * delpos234 because we know del234 is based on it, so it's
+     * already been tested in the above sorted-tree code; but for
+     * completeness we'll use it to tear down our unsorted tree
+     * once we've built it.
+     */
+    tree = newtree234(NULL);
+    cmp = NULL;
+    verify();
+    for (i = 0; i < 1000; i++) {
+	printf("trial: %d\n", i);
+	j = randomnumber(&seed);
+	j %= NSTR;
+	k = randomnumber(&seed);
+	k %= count234(tree)+1;
+	printf("adding string %s at index %d\n", strings[j], k);
+	addpostest(strings[j], k);
+    }
+
+    /*
+     * While we have this tree in its full form, we'll take a copy
+     * of it to use in split and join testing.
+     */
+    tree2 = copytree234(tree, NULL, NULL);
+    verifytree(tree2, array, arraylen);/* check the copy is accurate */
+    /*
+     * Split tests. Split the tree at every possible point and
+     * check the resulting subtrees.
+     */
+    tworoot = (!tree2->root->elems[1]);/* see if it has a 2-root */
+    splittest(tree2, array, arraylen);
+    /*
+     * Now do the split test again, but on a tree that has a 2-root
+     * (if the previous one didn't) or doesn't (if the previous one
+     * did).
+     */
+    tmplen = arraylen;
+    while ((!tree2->root->elems[1]) == tworoot) {
+	delpos234(tree2, --tmplen);
+    }
+    printf("now trying splits on second tree\n");
+    splittest(tree2, array, tmplen);
+    freetree234(tree2);
+
+    /*
+     * Back to the main testing of uncounted trees.
+     */
+    while (count234(tree) > 0) {
+	printf("cleanup: tree size %d\n", count234(tree));
+	j = randomnumber(&seed);
+	j %= count234(tree);
+	printf("deleting string %s from index %d\n", (char *)array[j], j);
+	delpostest(j);
+    }
+    freetree234(tree);
+
+    /*
+     * Finally, do some testing on split/join on _sorted_ trees. At
+     * the same time, we'll be testing split on very small trees.
+     */
+    tree = newtree234(mycmp);
+    cmp = mycmp;
+    arraylen = 0;
+    for (i = 0; i < 17; i++) {
+	tree2 = copytree234(tree, NULL, NULL);
+	splittest(tree2, array, arraylen);
+	freetree234(tree2);
+	if (i < 16)
+	    addtest(strings[i]);
+    }
+    freetree234(tree);
+
+    /*
+     * Test silly cases of join: join(emptytree, emptytree), and
+     * also ensure join correctly spots when sorted trees fail the
+     * ordering constraint.
+     */
+    tree = newtree234(mycmp);
+    tree2 = newtree234(mycmp);
+    tree3 = newtree234(mycmp);
+    tree4 = newtree234(mycmp);
+    assert(mycmp(strings[0], strings[1]) < 0);   /* just in case :-) */
+    add234(tree2, strings[1]);
+    add234(tree4, strings[0]);
+    array[0] = strings[0];
+    array[1] = strings[1];
+    verifytree(tree, array, 0);
+    verifytree(tree2, array+1, 1);
+    verifytree(tree3, array, 0);
+    verifytree(tree4, array, 1);
+
+    /*
+     * So:
+     *  - join(tree,tree3) should leave both tree and tree3 unchanged.
+     *  - joinr(tree,tree2) should leave both tree and tree2 unchanged.
+     *  - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
+     *  - join(tree, tree2) should move the element from tree2 to tree.
+     *  - joinr(tree4, tree3) should move the element from tree4 to tree3.
+     *  - join(tree,tree3) should return NULL and leave both unchanged.
+     *  - join(tree3,tree) should work and create a bigger tree in tree3.
+     */
+    assert(tree == join234(tree, tree3));
+    verifytree(tree, array, 0);
+    verifytree(tree3, array, 0);
+    assert(tree2 == join234r(tree, tree2));
+    verifytree(tree, array, 0);
+    verifytree(tree2, array+1, 1);
+    assert(tree4 == join234(tree4, tree3));
+    verifytree(tree3, array, 0);
+    verifytree(tree4, array, 1);
+    assert(tree == join234(tree, tree2));
+    verifytree(tree, array+1, 1);
+    verifytree(tree2, array, 0);
+    assert(tree3 == join234r(tree4, tree3));
+    verifytree(tree3, array, 1);
+    verifytree(tree4, array, 0);
+    assert(NULL == join234(tree, tree3));
+    verifytree(tree, array+1, 1);
+    verifytree(tree3, array, 1);
+    assert(tree3 == join234(tree3, tree));
+    verifytree(tree3, array, 2);
+    verifytree(tree, array, 0);
+
+    return 0;
+}
--- a/combi.c
+++ b/combi.c
@@ -71,35 +71,3 @@
     sfree(combi->a);
     sfree(combi);
 }
-
-/* compile this with:
- *   gcc -o combi.exe -DSTANDALONE_COMBI_TEST combi.c malloc.c
- */
-#ifdef STANDALONE_COMBI_TEST
-
-#include <stdio.h>
-
-int main(int argc, char *argv[])
-{
-    combi_ctx *c;
-    int i, r, n;
-
-    if (argc < 3) {
-        fprintf(stderr, "Usage: combi R N\n");
-        exit(1);
-    }
-
-    r = atoi(argv[1]); n = atoi(argv[2]);
-    c = new_combi(r, n);
-    printf("combi %d of %d, %d elements.\n", c->r, c->n, c->total);
-
-    while (next_combi(c)) {
-        for (i = 0; i < c->r; i++) {
-            printf("%d ", c->a[i]);
-        }
-        printf("\n");
-    }
-    free_combi(c);
-}
-
-#endif
--- a/divvy.c
+++ b/divvy.c
@@ -260,7 +260,7 @@
  * In both of the above suggested use cases, the user would
  * probably want w==h==k, but that isn't a requirement.
  */
-static int *divvy_internal(int w, int h, int k, random_state *rs)
+int *divvy_rectangle_attempt(int w, int h, int k, random_state *rs)
 {
     int *order, *queue, *tmp, *own, *sizes, *addable, *retdsf;
     bool *removable;
@@ -652,131 +652,13 @@
     return retdsf;
 }
 
-#ifdef TESTMODE
-static int fail_counter = 0;
-#endif
-
 int *divvy_rectangle(int w, int h, int k, random_state *rs)
 {
     int *ret;
 
     do {
-	ret = divvy_internal(w, h, k, rs);
-
-#ifdef TESTMODE
-	if (!ret)
-	    fail_counter++;
-#endif
-
+	ret = divvy_rectangle_attempt(w, h, k, rs);
     } while (!ret);
 
     return ret;
 }
-
-#ifdef TESTMODE
-
-/*
- * gcc -g -O0 -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
- * 
- * or to debug
- * 
- * gcc -g -O0 -DDIVVY_DIAGNOSTICS -DTESTMODE -I.. -o divvy divvy.c ../random.c ../malloc.c ../dsf.c ../misc.c ../nullfe.c
- */
-
-int main(int argc, char **argv)
-{
-    int *dsf;
-    int i;
-    int w = 9, h = 4, k = 6, tries = 100;
-    random_state *rs;
-
-    rs = random_new("123456", 6);
-
-    if (argc > 1)
-	w = atoi(argv[1]);
-    if (argc > 2)
-	h = atoi(argv[2]);
-    if (argc > 3)
-	k = atoi(argv[3]);
-    if (argc > 4)
-	tries = atoi(argv[4]);
-
-    for (i = 0; i < tries; i++) {
-	int x, y;
-
-	dsf = divvy_rectangle(w, h, k, rs);
-	assert(dsf);
-
-	for (y = 0; y <= 2*h; y++) {
-	    for (x = 0; x <= 2*w; x++) {
-		int miny = y/2 - 1 /*, maxy = y/2 */;
-		int minx = x/2 - 1 /*, maxx = x/2 */;
-		int classes[4], tx, ty;
-		for (ty = 0; ty < 2; ty++)
-		    for (tx = 0; tx < 2; tx++) {
-			int cx = minx+tx, cy = miny+ty;
-			if (cx < 0 || cx >= w || cy < 0 || cy >= h)
-			    classes[ty*2+tx] = -1;
-			else
-			    classes[ty*2+tx] = dsf_canonify(dsf, cy*w+cx);
-		    }
-		switch (y%2 * 2 + x%2) {
-		  case 0:	       /* corner */
-		    /*
-		     * Cases for the corner:
-		     *
-		     * 	- if all four surrounding squares belong
-		     * 	  to the same omino, we print a space.
-		     *
-		     * 	- if the top two are the same and the
-		     * 	  bottom two are the same, we print a
-		     * 	  horizontal line.
-		     *
-		     * 	- if the left two are the same and the
-		     * 	  right two are the same, we print a
-		     * 	  vertical line.
-		     *
-		     *  - otherwise, we print a cross.
-		     */
-		    if (classes[0] == classes[1] &&
-			classes[1] == classes[2] &&
-			classes[2] == classes[3])
-			printf(" ");
-		    else if (classes[0] == classes[1] &&
-			     classes[2] == classes[3])
-			printf("-");
-		    else if (classes[0] == classes[2] &&
-			     classes[1] == classes[3])
-			printf("|");
-		    else
-			printf("+");
-		    break;
-		  case 1:	       /* horiz edge */
-		    if (classes[1] == classes[3])
-			printf("  ");
-		    else
-			printf("--");
-		    break;
-		  case 2:	       /* vert edge */
-		    if (classes[2] == classes[3])
-			printf(" ");
-		    else
-			printf("|");
-		    break;
-		  case 3:	       /* square centre */
-		    printf("  ");
-		    break;
-		}
-	    }
-	    printf("\n");
-	}
-	printf("\n");
-	sfree(dsf);
-    }
-
-    printf("%d retries needed for %d successes\n", fail_counter, tries);
-
-    return 0;
-}
-
-#endif
--- a/latin.c
+++ b/latin.c
@@ -1311,121 +1311,4 @@
     return ret;
 }
 
-
-/* --------------------------------------------------------
- * Testing (and printing).
- */
-
-#ifdef STANDALONE_LATIN_TEST
-
-#include <stdio.h>
-#include <time.h>
-
-static const char *quis;
-
-static void latin_print(digit *sq, int order)
-{
-    int x, y;
-
-    for (y = 0; y < order; y++) {
-	for (x = 0; x < order; x++) {
-	    printf("%2u ", ELT(sq, x, y));
-	}
-	printf("\n");
-    }
-    printf("\n");
-}
-
-static void gen(int order, random_state *rs, int debug)
-{
-    digit *sq;
-
-    solver_show_working = debug;
-
-    sq = latin_generate(order, rs);
-    latin_print(sq, order);
-    if (latin_check(sq, order)) {
-	fprintf(stderr, "Square is not a latin square!");
-	exit(1);
-    }
-
-    sfree(sq);
-}
-
-static void test_soak(int order, random_state *rs)
-{
-    digit *sq;
-    int n = 0;
-    time_t tt_start, tt_now, tt_last;
-
-    solver_show_working = 0;
-    tt_now = tt_start = time(NULL);
-
-    while(1) {
-        sq = latin_generate(order, rs);
-        sfree(sq);
-        n++;
-
-        tt_last = time(NULL);
-        if (tt_last > tt_now) {
-            tt_now = tt_last;
-            printf("%d total, %3.1f/s\n", n,
-                   (double)n / (double)(tt_now - tt_start));
-        }
-    }
-}
-
-static void usage_exit(const char *msg)
-{
-    if (msg)
-        fprintf(stderr, "%s: %s\n", quis, msg);
-    fprintf(stderr, "Usage: %s [--seed SEED] --soak <params> | [game_id [game_id ...]]\n", quis);
-    exit(1);
-}
-
-int main(int argc, char *argv[])
-{
-    int i, soak = 0;
-    random_state *rs;
-    time_t seed = time(NULL);
-
-    quis = argv[0];
-    while (--argc > 0) {
-	const char *p = *++argv;
-	if (!strcmp(p, "--soak"))
-	    soak = 1;
-	else if (!strcmp(p, "--seed")) {
-	    if (argc == 0)
-		usage_exit("--seed needs an argument");
-	    seed = (time_t)atoi(*++argv);
-	    argc--;
-	} else if (*p == '-')
-		usage_exit("unrecognised option");
-	else
-	    break; /* finished options */
-    }
-
-    rs = random_new((void*)&seed, sizeof(time_t));
-
-    if (soak == 1) {
-	if (argc != 1) usage_exit("only one argument for --soak");
-	test_soak(atoi(*argv), rs);
-    } else {
-	if (argc > 0) {
-	    for (i = 0; i < argc; i++) {
-		gen(atoi(*argv++), rs, 1);
-	    }
-	} else {
-	    while (1) {
-		i = random_upto(rs, 20) + 1;
-		gen(i, rs, 0);
-	    }
-	}
-    }
-    random_free(rs);
-    return 0;
-}
-
-#endif
-
 /* vim: set shiftwidth=4 tabstop=8: */
--- a/matching.c
+++ b/matching.c
@@ -319,35 +319,7 @@
     return ret;
 }
 
-#ifdef STANDALONE_MATCHING_TEST
-
-/*
- * Diagnostic routine used in testing this algorithm. It is passed a
- * pointer to a piece of scratch space that's just been used by
- * matching_with_scratch, and extracts from it a labelling of the
- * input graph that acts as a 'witness' to the maximality of the
- * returned matching.
- *
- * The output parameter 'witness' should be an array of (nl+nr)
- * integers, indexed such that witness[L] corresponds to an L-vertex (for
- * L=0,1,...,nl-1) and witness[nl+R] corresponds to an R-vertex (for
- * R=0,1,...,nr-1). On return, this array will assign each vertex a
- * label which is either 0 or 1, and the following properties will
- * hold:
- *
- *  + all vertices not paired up by the matching are type L0 or R1
- *  + every L0->R1 edge is used by the matching
- *  + no L1->R0 edge is used by the matching.
- *
- * The mere existence of such a labelling is enough to prove the
- * maximality of the matching, because if there is any larger matching
- * then its symmetric difference with this one must include at least
- * one 'augmenting path', which starts at a free L-vertex and ends at
- * a free R-vertex, traversing only unused L->R edges and only used
- * R->L edges. But that would mean it starts at an L0, ends at an R1,
- * and never follows an edge that can get from an 0 to a 1.
- */
-static void matching_witness(void *scratchv, int nl, int nr, int *witness)
+void matching_witness(void *scratchv, int nl, int nr, int *witness)
 {
     struct scratch *s = (struct scratch *)scratchv;
     int i, j;
@@ -357,400 +329,3 @@
     for (j = 0; j < nr; j++)
         witness[nl + j] = s->Rlayer[j] == -1;
 }
-
-/*
- * Standalone tool to run the matching algorithm.
- */
-
-#include <string.h>
-#include <ctype.h>
-#include <time.h>
-
-#include "tree234.h"
-
-static int nl, nr, count;
-static int **adjlists, *adjsizes;
-static int *adjdata, *outl, *outr, *witness;
-static void *scratch;
-static random_state *rs;
-
-static void allocate(int nl_, int nr_, int maxedges)
-{
-    nl = nl_;
-    nr = nr_;
-    adjdata = snewn(maxedges, int);
-    adjlists = snewn(nl, int *);
-    adjsizes = snewn(nl, int);
-    outl = snewn(nl, int);
-    outr = snewn(nr, int);
-    witness = snewn(nl+nr, int);
-    scratch = smalloc(matching_scratch_size(nl, nr));
-}
-
-static void deallocate(void)
-{
-    sfree(adjlists);
-    sfree(adjsizes);
-    sfree(adjdata);
-    sfree(outl);
-    sfree(outr);
-    sfree(witness);
-    sfree(scratch);
-}
-
-static void find_and_check_matching(void)
-{
-    int i, j, k;
-
-    count = matching_with_scratch(scratch, nl, nr, adjlists, adjsizes,
-                                  rs, outl, outr);
-    matching_witness(scratch, nl, nr, witness);
-
-    for (i = j = 0; i < nl; i++) {
-        if (outl[i] != -1) {
-            assert(0 <= outl[i] && outl[i] < nr);
-            assert(outr[outl[i]] == i);
-            j++;
-
-            for (k = 0; k < adjsizes[i]; k++)
-                if (adjlists[i][k] == outl[i])
-                    break;
-            assert(k < adjsizes[i]);
-        }
-    }
-    assert(j == count);
-
-    for (i = j = 0; i < nr; i++) {
-        if (outr[i] != -1) {
-            assert(0 <= outr[i] && outr[i] < nl);
-            assert(outl[outr[i]] == i);
-            j++;
-        }
-    }
-    assert(j == count);
-
-    for (i = 0; i < nl; i++) {
-        if (outl[i] == -1)
-            assert(witness[i] == 0);
-    }
-    for (i = 0; i < nr; i++) {
-        if (outr[i] == -1)
-            assert(witness[nl+i] == 1);
-    }
-    for (i = 0; i < nl; i++) {
-        for (j = 0; j < adjsizes[i]; j++) {
-            k = adjlists[i][j];
-
-            if (outl[i] == k)
-                assert(!(witness[i] == 1 && witness[nl+k] == 0));
-            else
-                assert(!(witness[i] == 0 && witness[nl+k] == 1));
-        }
-    }
-}
-
-struct nodename {
-    const char *name;
-    int index;
-};
-
-static int compare_nodes(void *av, void *bv)
-{
-    const struct nodename *a = (const struct nodename *)av;
-    const struct nodename *b = (const struct nodename *)bv;
-    return strcmp(a->name, b->name);
-}
-
-static int node_index(tree234 *n2i, tree234 *i2n, const char *name)
-{
-    struct nodename *nn, *nn_prev;
-    char *namedup = dupstr(name);
-
-    nn = snew(struct nodename);
-    nn->name = namedup;
-    nn->index = count234(n2i);
-
-    nn_prev = add234(n2i, nn);
-    if (nn_prev != nn) {
-        sfree(nn);
-        sfree(namedup);
-    } else {
-        addpos234(i2n, nn, nn->index);
-    }
-
-    return nn_prev->index;
-}
-
-struct edge {
-    int L, R;
-};
-
-static int compare_edges(void *av, void *bv)
-{
-    const struct edge *a = (const struct edge *)av;
-    const struct edge *b = (const struct edge *)bv;
-    if (a->L < b->L) return -1;
-    if (a->L > b->L) return +1;
-    if (a->R < b->R) return -1;
-    if (a->R > b->R) return +1;
-    return 0;
-}
-
-static void matching_from_user_input(FILE *fp, const char *filename)
-{
-    tree234 *Ln2i, *Li2n, *Rn2i, *Ri2n, *edges;
-    char *line = NULL;
-    struct edge *e;
-    int i, lineno = 0;
-    int *adjptr;
-
-    Ln2i = newtree234(compare_nodes);
-    Rn2i = newtree234(compare_nodes);
-    Li2n = newtree234(NULL);
-    Ri2n = newtree234(NULL);
-    edges = newtree234(compare_edges);
-
-    while (sfree(line), lineno++, (line = fgetline(fp)) != NULL) {
-        char *p, *Lname, *Rname;
-
-        p = line;
-        while (*p && isspace((unsigned char)*p)) p++;
-        if (!*p)
-            continue;
-
-        Lname = p;
-        while (*p && !isspace((unsigned char)*p)) p++;
-        if (*p)
-            *p++ = '\0';
-        while (*p && isspace((unsigned char)*p)) p++;
-
-        if (!*p) {
-            fprintf(stderr, "%s:%d: expected 2 words, found 1\n",
-                    filename, lineno);
-            exit(1);
-        }
-
-        Rname = p;
-        while (*p && !isspace((unsigned char)*p)) p++;
-        if (*p)
-            *p++ = '\0';
-        while (*p && isspace((unsigned char)*p)) p++;
-
-        if (*p) {
-            fprintf(stderr, "%s:%d: expected 2 words, found more\n",
-                    filename, lineno);
-            exit(1);
-        }
-
-        e = snew(struct edge);
-        e->L = node_index(Ln2i, Li2n, Lname);
-        e->R = node_index(Rn2i, Ri2n, Rname);
-        if (add234(edges, e) != e) {
-            fprintf(stderr, "%s:%d: duplicate edge\n",
-                    filename, lineno);
-            exit(1);
-        }
-    }
-
-    allocate(count234(Ln2i), count234(Rn2i), count234(edges));
-
-    adjptr = adjdata;
-    for (i = 0; i < nl; i++)
-        adjlists[i] = NULL;
-    for (i = 0; (e = index234(edges, i)) != NULL; i++) {
-        if (!adjlists[e->L])
-            adjlists[e->L] = adjptr;
-        *adjptr++ = e->R;
-        adjsizes[e->L] = adjptr - adjlists[e->L];
-    }
-
-    find_and_check_matching();
-
-    for (i = 0; i < nl; i++) {
-        if (outl[i] != -1) {
-            struct nodename *Lnn = index234(Li2n, i);
-            struct nodename *Rnn = index234(Ri2n, outl[i]);
-            printf("%s %s\n", Lnn->name, Rnn->name);
-        }
-    }
-    deallocate();
-}
-
-static void test_subsets(void)
-{
-    int b = 8;
-    int n = 1 << b;
-    int i, j, nruns, expected_size;
-    int *adjptr;
-    int *edgecounts;
-    struct stats {
-        int min, max;
-        double n, sx, sxx;
-    } *stats;
-    static const char seed[] = "fixed random seed for repeatability";
-
-    /*
-     * Generate a graph in which every subset of [b] = {1,...,b}
-     * (represented as a b-bit integer 0 <= i < n) has an edge going
-     * to every subset obtained by removing exactly one element.
-     *
-     * This graph is the disjoint union of the corresponding graph for
-     * each layer (collection of same-sized subset) of the power set
-     * of [b]. Each of those graphs has a matching of size equal to
-     * the smaller of its vertex sets. So we expect the overall size
-     * of the output matching to be less than n by the size of the
-     * largest layer, that is, to be n - binomial(n, floor(n/2)).
-     *
-     * We run the generation repeatedly, randomising it every time,
-     * and we expect to see every possible edge appear sooner or
-     * later.
-     */
-
-    rs = random_new(seed, strlen(seed));
-
-    allocate(n, n, n*b);
-    adjptr = adjdata;
-    expected_size = 0;
-    for (i = 0; i < n; i++) {
-        adjlists[i] = adjptr;
-        for (j = 0; j < b; j++) {
-            if (i & (1 << j))
-                *adjptr++ = i & ~(1 << j);
-        }
-        adjsizes[i] = adjptr - adjlists[i];
-        if (adjsizes[i] != b/2)
-            expected_size++;
-    }
-
-    edgecounts = snewn(n*b, int);
-    for (i = 0; i < n*b; i++)
-        edgecounts[i] = 0;
-
-    stats = snewn(b, struct stats);
-
-    nruns = 0;
-    while (nruns < 10000) {
-        nruns++;
-        find_and_check_matching();
-        assert(count == expected_size);
-
-        for (i = 0; i < n; i++)
-            for (j = 0; j < b; j++)
-                if ((i ^ outl[i]) == (1 << j))
-                    edgecounts[b*i+j]++;
-
-        if (nruns % 1000 == 0) {
-            for (i = 0; i < b; i++) {
-                struct stats *st = &stats[i];
-                st->min = st->max = -1;
-                st->n = st->sx = st->sxx = 0;
-            }
-
-            for (i = 0; i < n; i++) {
-                int pop = 0;
-                for (j = 0; j < b; j++)
-                    if (i & (1 << j))
-                        pop++;
-                pop--;
-
-                for (j = 0; j < b; j++) {
-                    if (i & (1 << j)) {
-                        struct stats *st = &stats[pop];
-                        int x = edgecounts[b*i+j];
-                        if (st->max == -1 || st->max < x)
-                            st->max = x;
-                        if (st->min == -1 || st->min > x)
-                            st->min = x;
-                        st->n++;
-                        st->sx += x;
-                        st->sxx += (double)x*x;
-                    } else {
-                        assert(edgecounts[b*i+j] == 0);
-                    }
-                }
-            }
-        }
-    }
-
-    printf("after %d runs:\n", nruns);
-    for (j = 0; j < b; j++) {
-        struct stats *st = &stats[j];
-        printf("edges between layers %d,%d:"
-               " min=%d max=%d mean=%f variance=%f\n",
-               j, j+1, st->min, st->max, st->sx/st->n,
-               (st->sxx - st->sx*st->sx/st->n) / st->n);
-    }
-    sfree(edgecounts);
-    deallocate();
-}
-
-int main(int argc, char **argv)
-{
-    static const char stdin_identifier[] = "<standard input>";
-    const char *infile = NULL;
-    bool doing_opts = true;
-    enum { USER_INPUT, AUTOTEST } mode = USER_INPUT;
-
-    while (--argc > 0) {
-        const char *arg = *++argv;
-
-        if (doing_opts && arg[0] == '-' && arg[1]) {
-            if (!strcmp(arg, "--")) {
-                doing_opts = false;
-            } else if (!strcmp(arg, "--random")) {
-                char buf[64];
-                int len = sprintf(buf, "%lu", (unsigned long)time(NULL));
-                rs = random_new(buf, len);
-            } else if (!strcmp(arg, "--autotest")) {
-                mode = AUTOTEST;
-            } else {
-                fprintf(stderr, "matching: unrecognised option '%s'\n", arg);
-                return 1;
-            }
-        } else {
-            if (!infile) {
-                infile = (!strcmp(arg, "-") ? stdin_identifier : arg);
-            } else {
-                fprintf(stderr, "matching: too many arguments\n");
-                return 1;
-            }
-        }
-    }
-
-    if (mode == USER_INPUT) {
-        FILE *fp;
-
-        if (!infile)
-            infile = stdin_identifier;
-
-        if (infile != stdin_identifier) {
-            fp = fopen(infile, "r");
-            if (!fp) {
-                fprintf(stderr, "matching: could not open input file '%s'\n",
-                        infile);
-                return 1;
-            }
-        } else {
-            fp = stdin;
-        }
-
-        matching_from_user_input(fp, infile);
-
-        if (infile != stdin_identifier)
-            fclose(fp);
-    }
-
-    if (mode == AUTOTEST) {
-        if (infile) {
-            fprintf(stderr, "matching: expected no filename argument "
-                    "with --autotest\n");
-            return 1;
-        }
-
-        test_subsets();
-    }
-
-    return 0;
-}
-
-#endif /* STANDALONE_MATCHING_TEST */
--- a/matching.h
+++ b/matching.h
@@ -77,4 +77,32 @@
 int matching(int nl, int nr, int **adjlists, int *adjsizes,
              random_state *rs, int *outl, int *outr);
 
+/*
+ * Diagnostic routine used in testing this algorithm. It is passed a
+ * pointer to a piece of scratch space that's just been used by
+ * matching_with_scratch, and extracts from it a labelling of the
+ * input graph that acts as a 'witness' to the maximality of the
+ * returned matching.
+ *
+ * The output parameter 'witness' should be an array of (nl+nr)
+ * integers, indexed such that witness[L] corresponds to an L-vertex (for
+ * L=0,1,...,nl-1) and witness[nl+R] corresponds to an R-vertex (for
+ * R=0,1,...,nr-1). On return, this array will assign each vertex a
+ * label which is either 0 or 1, and the following properties will
+ * hold:
+ *
+ *  + all vertices not paired up by the matching are type L0 or R1
+ *  + every L0->R1 edge is used by the matching
+ *  + no L1->R0 edge is used by the matching.
+ *
+ * The mere existence of such a labelling is enough to prove the
+ * maximality of the matching, because if there is any larger matching
+ * then its symmetric difference with this one must include at least
+ * one 'augmenting path', which starts at a free L-vertex and ends at
+ * a free R-vertex, traversing only unused L->R edges and only used
+ * R->L edges. But that would mean it starts at an L0, ends at an R1,
+ * and never follows an edge that can get from an 0 to a 1.
+ */
+void matching_witness(void *scratch, int nl, int nr, int *witness);
+
 #endif /* MATCHING_MATCHING_H */
--- a/obfusc.c
+++ /dev/null
@@ -1,130 +1,0 @@
-/*
- * Stand-alone tool to access the Puzzles obfuscation algorithm.
- * 
- * To deobfuscate, use "obfusc -d":
- * 
- *   obfusc -d                 reads binary data from stdin, writes to stdout
- *   obfusc -d <hex string>    works on the given hex string instead of stdin
- *   obfusc -d -h              writes a hex string instead of binary to stdout
- *
- * To obfuscate, "obfusc -e":
- * 
- *   obfusc -e                 reads binary from stdin, writes hex to stdout
- *   obfusc -e <hex string>    works on the given hex string instead of stdin
- *   obfusc -e -b              writes binary instead of text to stdout
- *
- * The default output format is hex for -e and binary for -d
- * because that's the way obfuscation is generally used in
- * Puzzles. Either of -b and -h can always be specified to set it
- * explicitly.
- *
- * Data read from standard input is assumed always to be binary;
- * data provided on the command line is taken to be hex.
- */
-
-#include <stdio.h>
-#include <stdlib.h>
-#include <stdarg.h>
-#include <string.h>
-#include <errno.h>
-
-#include "puzzles.h"
-
-int main(int argc, char **argv)
-{
-    enum { BINARY, DEFAULT, HEX } outputmode = DEFAULT;
-    char *inhex = NULL;
-    unsigned char *data;
-    int datalen;
-    enum { UNKNOWN, DECODE, ENCODE } mode = UNKNOWN;
-    bool doing_opts = true;
-
-    while (--argc > 0) {
-	char *p = *++argv;
-
-	if (doing_opts && *p == '-') {
-	    if (!strcmp(p, "--")) {
-		doing_opts = 0;
-		continue;
-	    }
-	    p++;
-	    while (*p) {
-		switch (*p) {
-		  case 'e':
-		    mode = ENCODE;
-		    break;
-		  case 'd':
-		    mode = DECODE;
-		    break;
-		  case 'b':
-		    outputmode = BINARY;
-		    break;
-		  case 'h':
-		    outputmode = HEX;
-		    break;
-		  default:
-		    fprintf(stderr, "obfusc: unrecognised option '-%c'\n",
-			    *p);
-		    return 1;
-		}
-		p++;
-	    }
-	} else {
-	    if (!inhex) {
-		inhex = p;
-	    } else {
-		fprintf(stderr, "obfusc: expected at most one argument\n");
-		return 1;
-	    }
-	}
-    }
-
-    if (mode == UNKNOWN) {
-	fprintf(stderr, "usage: obfusc < -e | -d > [ -b | -h ] [hex data]\n");
-	return 0;
-    }
-
-    if (outputmode == DEFAULT)
-	outputmode = (mode == DECODE ? BINARY : HEX);
-
-    if (inhex) {
-	datalen = strlen(inhex) / 2;
-	data = hex2bin(inhex, datalen);
-    } else {
-	int datasize = 4096;
-	datalen = 0;
-	data = snewn(datasize, unsigned char);
-	while (1) {
-	    int ret = fread(data + datalen, 1, datasize - datalen, stdin);
-	    if (ret < 0) {
-		fprintf(stderr, "obfusc: read: %s\n", strerror(errno));
-		return 1;
-	    } else if (ret == 0) {
-		break;
-	    } else {
-		datalen += ret;
-		if (datasize - datalen < 4096) {
-		    datasize = datalen * 5 / 4 + 4096;
-		    data = sresize(data, datasize, unsigned char);
-		}
-	    }
-	}
-    }
-
-    obfuscate_bitmap(data, datalen * 8, mode == DECODE);
-
-    if (outputmode == BINARY) {
-	int ret = fwrite(data, 1, datalen, stdout);
-        if (ret < 0) {
-            fprintf(stderr, "obfusc: write: %s\n", strerror(errno));
-            return 1;
-        }
-    } else {
-	int i;
-	for (i = 0; i < datalen; i++)
-	    printf("%02x", data[i]);
-	printf("\n");
-    }
-
-    return 0;
-}
--- a/penrose.c
+++ b/penrose.c
@@ -499,131 +499,3 @@
     *depth = n;
     *required_radius = rradius;
 }
-
-/* -------------------------------------------------------
- * Test code.
- */
-
-#ifdef TEST_PENROSE
-
-#include <stdio.h>
-#include <string.h>
-
-static int show_recursion = 0;
-static int ntiles, nfinal;
-
-static int test_cb(penrose_state *state, vector *vs, int n, int depth)
-{
-    int i, xoff = 0, yoff = 0;
-    double l = penrose_side_length(state->start_size, depth);
-    double rball = l / 10.0;
-    const char *col;
-
-    ntiles++;
-    if (state->max_depth == depth) {
-        col = n == 4 ? "black" : "green";
-        nfinal++;
-    } else {
-        if (!show_recursion)
-            return 0;
-        col = n == 4 ? "red" : "blue";
-    }
-    if (n != 4) yoff = state->start_size;
-
-    printf("<polygon points=\"");
-    for (i = 0; i < n; i++) {
-        printf("%s%f,%f", (i == 0) ? "" : " ",
-               v_x(vs, i) + xoff, v_y(vs, i) + yoff);
-    }
-    printf("\" style=\"fill: %s; fill-opacity: 0.2; stroke: %s\" />\n", col, col);
-    printf("<ellipse cx=\"%f\" cy=\"%f\" rx=\"%f\" ry=\"%f\" fill=\"%s\" />",
-           v_x(vs, 0) + xoff, v_y(vs, 0) + yoff, rball, rball, col);
-
-    return 0;
-}
-
-static void usage_exit(void)
-{
-    fprintf(stderr, "Usage: penrose-test [--recursion] P2|P3 SIZE DEPTH\n");
-    exit(1);
-}
-
-int main(int argc, char *argv[])
-{
-    penrose_state ps;
-    int which = 0;
-
-    while (--argc > 0) {
-        char *p = *++argv;
-        if (!strcmp(p, "-h") || !strcmp(p, "--help")) {
-            usage_exit();
-        } else if (!strcmp(p, "--recursion")) {
-            show_recursion = 1;
-        } else if (*p == '-') {
-            fprintf(stderr, "Unrecognised option '%s'\n", p);
-            exit(1);
-        } else {
-            break;
-        }
-    }
-
-    if (argc < 3) usage_exit();
-
-    if (strcmp(argv[0], "P2") == 0) which = PENROSE_P2;
-    else if (strcmp(argv[0], "P3") == 0) which = PENROSE_P3;
-    else usage_exit();
-
-    ps.start_size = atoi(argv[1]);
-    ps.max_depth = atoi(argv[2]);
-    ps.new_tile = test_cb;
-
-    ntiles = nfinal = 0;
-
-    printf("\
-<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n\
-<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n\
-\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n\
-\n\
-<svg xmlns=\"http://www.w3.org/2000/svg\"\n\
-xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n\n");
-
-    printf("<g>\n");
-    penrose(&ps, which, 0);
-    printf("</g>\n");
-
-    printf("<!-- %d tiles and %d leaf tiles total -->\n",
-           ntiles, nfinal);
-
-    printf("</svg>");
-
-    return 0;
-}
-
-#endif
-
-#ifdef TEST_VECTORS
-
-static void dbgv(const char *msg, vector v)
-{
-    printf("%s: %s\n", msg, v_debug(v));
-}
-
-int main(int argc, const char *argv[])
-{
-   vector v = v_unit();
-
-   dbgv("unit vector", v);
-   v = v_rotate(v, 36);
-   dbgv("rotated 36", v);
-   v = v_scale(v, 2);
-   dbgv("scaled x2", v);
-   v = v_shrinkphi(v);
-   dbgv("shrunk phi", v);
-   v = v_rotate(v, -36);
-   dbgv("rotated -36", v);
-
-   return 0;
-}
-
-#endif
-/* vim: set shiftwidth=4 tabstop=8: */
--- a/puzzles.h
+++ b/puzzles.h
@@ -563,6 +563,8 @@
  */
 /* divides w*h rectangle into pieces of size k. Returns w*h dsf. */
 int *divvy_rectangle(int w, int h, int k, random_state *rs);
+/* Same, but only tries once, and may fail. (Exposed for test program.) */
+int *divvy_rectangle_attempt(int w, int h, int k, random_state *rs);
 
 /*
  * findloop.c
--- a/sort.c
+++ b/sort.c
@@ -87,74 +87,3 @@
         downheap(array, i, size, cmp, ctx, 0);
     }
 }
-
-#ifdef SORT_TEST
-
-#include <stdlib.h>
-#include <time.h>
-
-static int testcmp(const void *av, const void *bv, void *ctx)
-{
-    int a = *(const int *)av, b = *(const int *)bv;
-    const int *keys = (const int *)ctx;
-    return keys[a] < keys[b] ? -1 : keys[a] > keys[b] ? +1 : 0;
-}
-
-static int resetcmp(const void *av, const void *bv)
-{
-    int a = *(const int *)av, b = *(const int *)bv;
-    return a < b ? -1 : a > b ? +1 : 0;
-}
-
-int main(int argc, char **argv)
-{
-    typedef int Array[3723];
-    Array data, keys;
-    int iteration;
-    unsigned seed;
-
-    seed = (argc > 1 ? strtoul(argv[1], NULL, 0) : time(NULL));
-    printf("Random seed = %u\n", seed);
-    srand(seed);
-
-    for (iteration = 0; iteration < 10000; iteration++) {
-        int j;
-        const char *fail = NULL;
-
-        for (j = 0; j < lenof(data); j++) {
-            data[j] = j;
-            keys[j] = rand();
-        }
-
-        arraysort(data, lenof(data), testcmp, keys);
-
-        for (j = 1; j < lenof(data); j++) {
-            if (keys[data[j]] < keys[data[j-1]])
-                fail = "output misordered";
-        }
-        if (!fail) {
-            Array reset;
-            memcpy(reset, data, sizeof(data));
-            qsort(reset, lenof(reset), sizeof(*reset), resetcmp);
-            for (j = 0; j < lenof(reset); j++)
-                if (reset[j] != j)
-                    fail = "output not permuted";
-        }
-
-        if (fail) {
-            printf("Failed at iteration %d: %s\n", iteration, fail);
-            printf("Key values:\n");
-            for (j = 0; j < lenof(keys); j++)
-                printf("  [%2d] %10d\n", j, keys[j]);
-            printf("Output sorted order:\n");
-            for (j = 0; j < lenof(data); j++)
-                printf("  [%2d] %10d\n", data[j], keys[data[j]]);
-            return 1;
-        }
-    }
-
-    printf("OK\n");
-    return 0;
-}
-
-#endif /* SORT_TEST */
--- a/tree234.c
+++ b/tree234.c
@@ -29,11 +29,12 @@
 #include <stdlib.h>
 #include <assert.h>
 
+#define TREE234_INTERNALS
 #include "tree234.h"
 
 #include "puzzles.h"		       /* for smalloc/sfree */
 
-#ifdef TEST
+#ifdef DEBUG_TREE234
 #include <stdarg.h>
 static void logprintf(const char *fmt, ...)
 {
@@ -47,20 +48,6 @@
 #define LOG(x)
 #endif
 
-typedef struct node234_Tag node234;
-
-struct tree234_Tag {
-    node234 *root;
-    cmpfn234 cmp;
-};
-
-struct node234_Tag {
-    node234 *parent;
-    node234 *kids[4];
-    int counts[4];
-    void *elems[3];
-};
-
 /*
  * Create a 2-3-4 tree.
  */
@@ -1109,7 +1096,7 @@
 
     return root;
 }
-static int height234(tree234 *t) {
+int height234(tree234 *t) {
     int level = 0;
     node234 *n = t->root;
     while (n) {
@@ -1457,754 +1444,3 @@
 
     return t2;
 }
-
-#ifdef TEST
-
-/*
- * Test code for the 2-3-4 tree. This code maintains an alternative
- * representation of the data in the tree, in an array (using the
- * obvious and slow insert and delete functions). After each tree
- * operation, the verify() function is called, which ensures all
- * the tree properties are preserved:
- *  - node->child->parent always equals node
- *  - tree->root->parent always equals NULL
- *  - number of kids == 0 or number of elements + 1;
- *  - tree has the same depth everywhere
- *  - every node has at least one element
- *  - subtree element counts are accurate
- *  - any NULL kid pointer is accompanied by a zero count
- *  - in a sorted tree: ordering property between elements of a
- *    node and elements of its children is preserved
- * and also ensures the list represented by the tree is the same
- * list it should be. (This last check also doubly verifies the
- * ordering properties, because the `same list it should be' is by
- * definition correctly ordered. It also ensures all nodes are
- * distinct, because the enum functions would get caught in a loop
- * if not.)
- */
-
-#include <string.h>
-#include <stdarg.h>
-
-#define srealloc realloc
-
-/*
- * Error reporting function.
- */
-static void error(const char *fmt, ...) {
-    va_list ap;
-    printf("ERROR: ");
-    va_start(ap, fmt);
-    vfprintf(stdout, fmt, ap);
-    va_end(ap);
-    printf("\n");
-}
-
-/* The array representation of the data. */
-static void **array;
-static int arraylen, arraysize;
-static cmpfn234 cmp;
-
-/* The tree representation of the same data. */
-static tree234 *tree;
-
-/*
- * Routines to provide a diagnostic printout of a tree. Currently
- * relies on every element in the tree being a one-character string
- * :-)
- */
-typedef struct {
-    char **levels;
-} dispctx;
-
-static int dispnode(node234 *n, int level, dispctx *ctx) {
-    if (level == 0) {
-	int xpos = strlen(ctx->levels[0]);
-	int len;
-
-	if (n->elems[2])
-	    len = sprintf(ctx->levels[0]+xpos, " %s%s%s",
-			  (char *)n->elems[0], (char *)n->elems[1],
-                          (char *)n->elems[2]);
-	else if (n->elems[1])
-	    len = sprintf(ctx->levels[0]+xpos, " %s%s",
-			  (char *)n->elems[0], (char *)n->elems[1]);
-	else
-	    len = sprintf(ctx->levels[0]+xpos, " %s",
-			  (char *)n->elems[0]);
-	return xpos + 1 + (len-1) / 2;
-    } else {
-	int xpos[4], nkids;
-	int nodelen, mypos, myleft, x, i;
-
-	xpos[0] = dispnode(n->kids[0], level-3, ctx);
-	xpos[1] = dispnode(n->kids[1], level-3, ctx);
-	nkids = 2;
-	if (n->kids[2]) {
-	    xpos[2] = dispnode(n->kids[2], level-3, ctx);
-	    nkids = 3;
-	}
-	if (n->kids[3]) {
-	    xpos[3] = dispnode(n->kids[3], level-3, ctx);
-	    nkids = 4;
-	}
-
-	if (nkids == 4)
-	    mypos = (xpos[1] + xpos[2]) / 2;
-	else if (nkids == 3)
-	    mypos = xpos[1];
-	else
-	    mypos = (xpos[0] + xpos[1]) / 2;
-	nodelen = nkids * 2 - 1;
-	myleft = mypos - ((nodelen-1)/2);
-	assert(myleft >= xpos[0]);
-	assert(myleft + nodelen-1 <= xpos[nkids-1]);
-
-	x = strlen(ctx->levels[level]);
-	while (x <= xpos[0] && x < myleft)
-	    ctx->levels[level][x++] = ' ';
-	while (x < myleft)
-	    ctx->levels[level][x++] = '_';
-	if (nkids==4)
-	    x += sprintf(ctx->levels[level]+x, ".%s.%s.%s.",
-			 (char *)n->elems[0], (char *)n->elems[1],
-                         (char *)n->elems[2]);
-	else if (nkids==3)
-	    x += sprintf(ctx->levels[level]+x, ".%s.%s.",
-			 (char *)n->elems[0], (char *)n->elems[1]);
-	else
-	    x += sprintf(ctx->levels[level]+x, ".%s.",
-			 (char *)n->elems[0]);
-	while (x < xpos[nkids-1])
-	    ctx->levels[level][x++] = '_';
-	ctx->levels[level][x] = '\0';
-
-	x = strlen(ctx->levels[level-1]);
-	for (i = 0; i < nkids; i++) {
-	    int rpos, pos;
-	    rpos = xpos[i];
-	    if (i > 0 && i < nkids-1)
-		pos = myleft + 2*i;
-	    else
-		pos = rpos;
-	    if (rpos < pos)
-		rpos++;
-	    while (x < pos && x < rpos)
-		ctx->levels[level-1][x++] = ' ';
-	    if (x == pos)
-		ctx->levels[level-1][x++] = '|';
-	    while (x < pos || x < rpos)
-		ctx->levels[level-1][x++] = '_';
-	    if (x == pos)
-		ctx->levels[level-1][x++] = '|';
-	}
-	ctx->levels[level-1][x] = '\0';
-
-	x = strlen(ctx->levels[level-2]);
-	for (i = 0; i < nkids; i++) {
-	    int rpos = xpos[i];
-
-	    while (x < rpos)
-		ctx->levels[level-2][x++] = ' ';
-	    ctx->levels[level-2][x++] = '|';
-	}
-	ctx->levels[level-2][x] = '\0';
-
-	return mypos;
-    }
-}
-
-static void disptree(tree234 *t) {
-    dispctx ctx;
-    char *leveldata;
-    int width = count234(t);
-    int ht = height234(t) * 3 - 2;
-    int i;
-
-    if (!t->root) {
-	printf("[empty tree]\n");
-    }
-
-    leveldata = smalloc(ht * (width+2));
-    ctx.levels = smalloc(ht * sizeof(char *));
-    for (i = 0; i < ht; i++) {
-	ctx.levels[i] = leveldata + i * (width+2);
-	ctx.levels[i][0] = '\0';
-    }
-
-    (void) dispnode(t->root, ht-1, &ctx);
-
-    for (i = ht; i-- ;)
-	printf("%s\n", ctx.levels[i]);
-
-    sfree(ctx.levels);
-    sfree(leveldata);
-}
-
-typedef struct {
-    int treedepth;
-    int elemcount;
-} chkctx;
-
-static int chknode(chkctx *ctx, int level, node234 *node,
-                   void *lowbound, void *highbound) {
-    int nkids, nelems;
-    int i;
-    int count;
-
-    /* Count the non-NULL kids. */
-    for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
-    /* Ensure no kids beyond the first NULL are non-NULL. */
-    for (i = nkids; i < 4; i++)
-        if (node->kids[i]) {
-            error("node %p: nkids=%d but kids[%d] non-NULL",
-                   node, nkids, i);
-        } else if (node->counts[i]) {
-            error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
-                   node, i, i, node->counts[i]);
-	}
-
-    /* Count the non-NULL elements. */
-    for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
-    /* Ensure no elements beyond the first NULL are non-NULL. */
-    for (i = nelems; i < 3; i++)
-        if (node->elems[i]) {
-            error("node %p: nelems=%d but elems[%d] non-NULL",
-                   node, nelems, i);
-        }
-
-    if (nkids == 0) {
-        /*
-         * If nkids==0, this is a leaf node; verify that the tree
-         * depth is the same everywhere.
-         */
-        if (ctx->treedepth < 0)
-            ctx->treedepth = level;    /* we didn't know the depth yet */
-        else if (ctx->treedepth != level)
-            error("node %p: leaf at depth %d, previously seen depth %d",
-                   node, level, ctx->treedepth);
-    } else {
-        /*
-         * If nkids != 0, then it should be nelems+1, unless nelems
-         * is 0 in which case nkids should also be 0 (and so we
-         * shouldn't be in this condition at all).
-         */
-        int shouldkids = (nelems ? nelems+1 : 0);
-        if (nkids != shouldkids) {
-            error("node %p: %d elems should mean %d kids but has %d",
-                   node, nelems, shouldkids, nkids);
-        }
-    }
-
-    /*
-     * nelems should be at least 1.
-     */
-    if (nelems == 0) {
-        error("node %p: no elems", node, nkids);
-    }
-
-    /*
-     * Add nelems to the running element count of the whole tree.
-     */
-    ctx->elemcount += nelems;
-
-    /*
-     * Check ordering property: all elements should be strictly >
-     * lowbound, strictly < highbound, and strictly < each other in
-     * sequence. (lowbound and highbound are NULL at edges of tree
-     * - both NULL at root node - and NULL is considered to be <
-     * everything and > everything. IYSWIM.)
-     */
-    if (cmp) {
-	for (i = -1; i < nelems; i++) {
-	    void *lower = (i == -1 ? lowbound : node->elems[i]);
-	    void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
-	    if (lower && higher && cmp(lower, higher) >= 0) {
-		error("node %p: kid comparison [%d=%s,%d=%s] failed",
-		      node, i, lower, i+1, higher);
-	    }
-	}
-    }
-
-    /*
-     * Check parent pointers: all non-NULL kids should have a
-     * parent pointer coming back to this node.
-     */
-    for (i = 0; i < nkids; i++)
-        if (node->kids[i]->parent != node) {
-            error("node %p kid %d: parent ptr is %p not %p",
-                   node, i, node->kids[i]->parent, node);
-        }
-
-
-    /*
-     * Now (finally!) recurse into subtrees.
-     */
-    count = nelems;
-
-    for (i = 0; i < nkids; i++) {
-        void *lower = (i == 0 ? lowbound : node->elems[i-1]);
-        void *higher = (i >= nelems ? highbound : node->elems[i]);
-	int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
-	if (node->counts[i] != subcount) {
-	    error("node %p kid %d: count says %d, subtree really has %d",
-		  node, i, node->counts[i], subcount);
-	}
-        count += subcount;
-    }
-
-    return count;
-}
-
-static void verifytree(tree234 *tree, void **array, int arraylen) {
-    chkctx ctx;
-    int i;
-    void *p;
-
-    ctx.treedepth = -1;                /* depth unknown yet */
-    ctx.elemcount = 0;                 /* no elements seen yet */
-    /*
-     * Verify validity of tree properties.
-     */
-    if (tree->root) {
-	if (tree->root->parent != NULL)
-	    error("root->parent is %p should be null", tree->root->parent);
-        chknode(&ctx, 0, tree->root, NULL, NULL);
-    }
-    printf("tree depth: %d\n", ctx.treedepth);
-    /*
-     * Enumerate the tree and ensure it matches up to the array.
-     */
-    for (i = 0; NULL != (p = index234(tree, i)); i++) {
-        if (i >= arraylen)
-            error("tree contains more than %d elements", arraylen);
-        if (array[i] != p)
-            error("enum at position %d: array says %s, tree says %s",
-                   i, array[i], p);
-    }
-    if (ctx.elemcount != i) {
-        error("tree really contains %d elements, enum gave %d",
-               ctx.elemcount, i);
-    }
-    if (i < arraylen) {
-        error("enum gave only %d elements, array has %d", i, arraylen);
-    }
-    i = count234(tree);
-    if (ctx.elemcount != i) {
-        error("tree really contains %d elements, count234 gave %d",
-	      ctx.elemcount, i);
-    }
-}
-static void verify(void) { verifytree(tree, array, arraylen); }
-
-static void internal_addtest(void *elem, int index, void *realret) {
-    int i, j;
-    void *retval;
-
-    if (arraysize < arraylen+1) {
-        arraysize = arraylen+1+256;
-        array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
-                 srealloc(array, arraysize*sizeof(*array)));
-    }
-
-    i = index;
-    /* now i points to the first element >= elem */
-    retval = elem;                  /* expect elem returned (success) */
-    for (j = arraylen; j > i; j--)
-	array[j] = array[j-1];
-    array[i] = elem;                /* add elem to array */
-    arraylen++;
-
-    if (realret != retval) {
-        error("add: retval was %p expected %p", realret, retval);
-    }
-
-    verify();
-}
-
-static void addtest(void *elem) {
-    int i;
-    void *realret;
-
-    realret = add234(tree, elem);
-
-    i = 0;
-    while (i < arraylen && cmp(elem, array[i]) > 0)
-        i++;
-    if (i < arraylen && !cmp(elem, array[i])) {
-        void *retval = array[i];       /* expect that returned not elem */
-	if (realret != retval) {
-	    error("add: retval was %p expected %p", realret, retval);
-	}
-    } else
-	internal_addtest(elem, i, realret);
-}
-
-static void addpostest(void *elem, int i) {
-    void *realret;
-
-    realret = addpos234(tree, elem, i);
-
-    internal_addtest(elem, i, realret);
-}
-
-static void delpostest(int i) {
-    int index = i;
-    void *elem = array[i], *ret;
-
-    /* i points to the right element */
-    while (i < arraylen-1) {
-	array[i] = array[i+1];
-	i++;
-    }
-    arraylen--;			       /* delete elem from array */
-
-    if (tree->cmp)
-	ret = del234(tree, elem);
-    else
-	ret = delpos234(tree, index);
-
-    if (ret != elem) {
-	error("del returned %p, expected %p", ret, elem);
-    }
-
-    verify();
-}
-
-static void deltest(void *elem) {
-    int i;
-
-    i = 0;
-    while (i < arraylen && cmp(elem, array[i]) > 0)
-        i++;
-    if (i >= arraylen || cmp(elem, array[i]) != 0)
-        return;                        /* don't do it! */
-    delpostest(i);
-}
-
-/* A sample data set and test utility. Designed for pseudo-randomness,
- * and yet repeatability. */
-
-/*
- * This random number generator uses the `portable implementation'
- * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
- * change it if not.
- */
-static int randomnumber(unsigned *seed) {
-    *seed *= 1103515245;
-    *seed += 12345;
-    return ((*seed) / 65536) % 32768;
-}
-
-static int mycmp(void *av, void *bv) {
-    char const *a = (char const *)av;
-    char const *b = (char const *)bv;
-    return strcmp(a, b);
-}
-
-static const char *const strings_init[] = {
-    "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
-    "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
-    "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
-    "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
-    "m", "s", "l", "4",
-#if 0
-    "a", "ab", "absque", "coram", "de",
-    "palam", "clam", "cum", "ex", "e",
-    "sine", "tenus", "pro", "prae",
-    "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
-    "penguin", "blancmange", "pangolin", "whale", "hedgehog",
-    "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
-    "murfl", "spoo", "breen", "flarn", "octothorpe",
-    "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
-    "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
-    "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
-    "wand", "ring", "amulet"
-#endif
-};
-
-#define NSTR lenof(strings_init)
-static char *strings[NSTR];
-
-static void findtest(void) {
-    static const int rels[] = {
-	REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
-    };
-    static const char *const relnames[] = {
-	"EQ", "GE", "LE", "LT", "GT"
-    };
-    int i, j, rel, index;
-    char *p, *ret, *realret, *realret2;
-    int lo, hi, mid, c;
-
-    for (i = 0; i < (int)NSTR; i++) {
-	p = strings[i];
-	for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) {
-	    rel = rels[j];
-
-	    lo = 0; hi = arraylen-1;
-	    while (lo <= hi) {
-		mid = (lo + hi) / 2;
-		c = strcmp(p, array[mid]);
-		if (c < 0)
-		    hi = mid-1;
-		else if (c > 0)
-		    lo = mid+1;
-		else
-		    break;
-	    }
-
-	    if (c == 0) {
-		if (rel == REL234_LT)
-		    ret = (mid > 0 ? array[--mid] : NULL);
-		else if (rel == REL234_GT)
-		    ret = (mid < arraylen-1 ? array[++mid] : NULL);
-		else
-		    ret = array[mid];
-	    } else {
-		assert(lo == hi+1);
-		if (rel == REL234_LT || rel == REL234_LE) {
-		    mid = hi;
-		    ret = (hi >= 0 ? array[hi] : NULL);
-		} else if (rel == REL234_GT || rel == REL234_GE) {
-		    mid = lo;
-		    ret = (lo < arraylen ? array[lo] : NULL);
-		} else
-		    ret = NULL;
-	    }
-
-	    realret = findrelpos234(tree, p, NULL, rel, &index);
-	    if (realret != ret) {
-		error("find(\"%s\",%s) gave %s should be %s",
-		      p, relnames[j], realret, ret);
-	    }
-	    if (realret && index != mid) {
-		error("find(\"%s\",%s) gave %d should be %d",
-		      p, relnames[j], index, mid);
-	    }
-	    if (realret && rel == REL234_EQ) {
-		realret2 = index234(tree, index);
-		if (realret2 != realret) {
-		    error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
-			  p, relnames[j], realret, index, index, realret2);
-		}
-	    }
-#if 0
-	    printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
-		   realret, index);
-#endif
-	}
-    }
-
-    realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
-    if (arraylen && (realret != array[0] || index != 0)) {
-	error("find(NULL,GT) gave %s(%d) should be %s(0)",
-	      realret, index, array[0]);
-    } else if (!arraylen && (realret != NULL)) {
-	error("find(NULL,GT) gave %s(%d) should be NULL",
-	      realret, index);
-    }
-
-    realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
-    if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
-	error("find(NULL,LT) gave %s(%d) should be %s(0)",
-	      realret, index, array[arraylen-1]);
-    } else if (!arraylen && (realret != NULL)) {
-	error("find(NULL,LT) gave %s(%d) should be NULL",
-	      realret, index);
-    }
-}
-
-static void splittest(tree234 *tree, void **array, int arraylen) {
-    int i;
-    tree234 *tree3, *tree4;
-    for (i = 0; i <= arraylen; i++) {
-	tree3 = copytree234(tree, NULL, NULL);
-	tree4 = splitpos234(tree3, i, false);
-	verifytree(tree3, array, i);
-	verifytree(tree4, array+i, arraylen-i);
-	join234(tree3, tree4);
-	freetree234(tree4);	       /* left empty by join */
-	verifytree(tree3, array, arraylen);
-	freetree234(tree3);
-    }
-}
-
-int main(void) {
-    int in[NSTR];
-    int i, j, k;
-    int tworoot, tmplen;
-    unsigned seed = 0;
-    tree234 *tree2, *tree3, *tree4;
-
-    setvbuf(stdout, NULL, _IOLBF, 0);
-
-    for (i = 0; i < (int)NSTR; i++)
-        strings[i] = dupstr(strings_init[i]);
-
-    for (i = 0; i < (int)NSTR; i++) in[i] = 0;
-    array = NULL;
-    arraylen = arraysize = 0;
-    tree = newtree234(mycmp);
-    cmp = mycmp;
-
-    verify();
-    for (i = 0; i < 10000; i++) {
-        j = randomnumber(&seed);
-        j %= NSTR;
-        printf("trial: %d\n", i);
-        if (in[j]) {
-            printf("deleting %s (%d)\n", strings[j], j);
-            deltest(strings[j]);
-            in[j] = 0;
-        } else {
-            printf("adding %s (%d)\n", strings[j], j);
-            addtest(strings[j]);
-            in[j] = 1;
-        }
-	disptree(tree);
-	findtest();
-    }
-
-    while (arraylen > 0) {
-        j = randomnumber(&seed);
-        j %= arraylen;
-        deltest(array[j]);
-    }
-
-    freetree234(tree);
-
-    /*
-     * Now try an unsorted tree. We don't really need to test
-     * delpos234 because we know del234 is based on it, so it's
-     * already been tested in the above sorted-tree code; but for
-     * completeness we'll use it to tear down our unsorted tree
-     * once we've built it.
-     */
-    tree = newtree234(NULL);
-    cmp = NULL;
-    verify();
-    for (i = 0; i < 1000; i++) {
-	printf("trial: %d\n", i);
-	j = randomnumber(&seed);
-	j %= NSTR;
-	k = randomnumber(&seed);
-	k %= count234(tree)+1;
-	printf("adding string %s at index %d\n", strings[j], k);
-	addpostest(strings[j], k);
-    }
-
-    /*
-     * While we have this tree in its full form, we'll take a copy
-     * of it to use in split and join testing.
-     */
-    tree2 = copytree234(tree, NULL, NULL);
-    verifytree(tree2, array, arraylen);/* check the copy is accurate */
-    /*
-     * Split tests. Split the tree at every possible point and
-     * check the resulting subtrees.
-     */
-    tworoot = (!tree2->root->elems[1]);/* see if it has a 2-root */
-    splittest(tree2, array, arraylen);
-    /*
-     * Now do the split test again, but on a tree that has a 2-root
-     * (if the previous one didn't) or doesn't (if the previous one
-     * did).
-     */
-    tmplen = arraylen;
-    while ((!tree2->root->elems[1]) == tworoot) {
-	delpos234(tree2, --tmplen);
-    }
-    printf("now trying splits on second tree\n");
-    splittest(tree2, array, tmplen);
-    freetree234(tree2);
-
-    /*
-     * Back to the main testing of uncounted trees.
-     */
-    while (count234(tree) > 0) {
-	printf("cleanup: tree size %d\n", count234(tree));
-	j = randomnumber(&seed);
-	j %= count234(tree);
-	printf("deleting string %s from index %d\n", (char *)array[j], j);
-	delpostest(j);
-    }
-    freetree234(tree);
-
-    /*
-     * Finally, do some testing on split/join on _sorted_ trees. At
-     * the same time, we'll be testing split on very small trees.
-     */
-    tree = newtree234(mycmp);
-    cmp = mycmp;
-    arraylen = 0;
-    for (i = 0; i < 17; i++) {
-	tree2 = copytree234(tree, NULL, NULL);
-	splittest(tree2, array, arraylen);
-	freetree234(tree2);
-	if (i < 16)
-	    addtest(strings[i]);
-    }
-    freetree234(tree);
-
-    /*
-     * Test silly cases of join: join(emptytree, emptytree), and
-     * also ensure join correctly spots when sorted trees fail the
-     * ordering constraint.
-     */
-    tree = newtree234(mycmp);
-    tree2 = newtree234(mycmp);
-    tree3 = newtree234(mycmp);
-    tree4 = newtree234(mycmp);
-    assert(mycmp(strings[0], strings[1]) < 0);   /* just in case :-) */
-    add234(tree2, strings[1]);
-    add234(tree4, strings[0]);
-    array[0] = strings[0];
-    array[1] = strings[1];
-    verifytree(tree, array, 0);
-    verifytree(tree2, array+1, 1);
-    verifytree(tree3, array, 0);
-    verifytree(tree4, array, 1);
-
-    /*
-     * So:
-     *  - join(tree,tree3) should leave both tree and tree3 unchanged.
-     *  - joinr(tree,tree2) should leave both tree and tree2 unchanged.
-     *  - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
-     *  - join(tree, tree2) should move the element from tree2 to tree.
-     *  - joinr(tree4, tree3) should move the element from tree4 to tree3.
-     *  - join(tree,tree3) should return NULL and leave both unchanged.
-     *  - join(tree3,tree) should work and create a bigger tree in tree3.
-     */
-    assert(tree == join234(tree, tree3));
-    verifytree(tree, array, 0);
-    verifytree(tree3, array, 0);
-    assert(tree2 == join234r(tree, tree2));
-    verifytree(tree, array, 0);
-    verifytree(tree2, array+1, 1);
-    assert(tree4 == join234(tree4, tree3));
-    verifytree(tree3, array, 0);
-    verifytree(tree4, array, 1);
-    assert(tree == join234(tree, tree2));
-    verifytree(tree, array+1, 1);
-    verifytree(tree2, array, 0);
-    assert(tree3 == join234r(tree4, tree3));
-    verifytree(tree3, array, 1);
-    verifytree(tree4, array, 0);
-    assert(NULL == join234(tree, tree3));
-    verifytree(tree, array+1, 1);
-    verifytree(tree3, array, 1);
-    assert(tree3 == join234(tree3, tree));
-    verifytree(tree3, array, 2);
-    verifytree(tree, array, 0);
-
-    return 0;
-}
-
-#endif
-
-#if 0 /* sorted list of strings might be useful */
-{
-    "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
-}
-#endif
--- a/tree234.h
+++ b/tree234.h
@@ -31,7 +31,11 @@
 #include <stdbool.h>
 
 /*
- * This typedef is opaque outside tree234.c itself.
+ * This typedef is typically opaque outside tree234.c itself. But you
+ * can define TREE234_INTERNALS to get a definition of it and its
+ * subsidiary node structure, as long as you're prepared to commit to
+ * responding to changes in the internals (which probably means you're
+ * tree234.c itself or tree234-test.c).
  */
 typedef struct tree234_Tag tree234;
 
@@ -38,6 +42,24 @@
 typedef int (*cmpfn234)(void *, void *);
 
 typedef void *(*copyfn234)(void *state, void *element);
+
+#ifdef TREE234_INTERNALS
+typedef struct node234_Tag node234;
+
+struct tree234_Tag {
+    node234 *root;
+    cmpfn234 cmp;
+};
+
+struct node234_Tag {
+    node234 *parent;
+    node234 *kids[4];
+    int counts[4];
+    void *elems[3];
+};
+
+int height234(tree234 *t);
+#endif
 
 /*
  * Create a 2-3-4 tree. If `cmp' is NULL, the tree is unsorted, and