Added DRFIN solver

14 files changed, 543 insertions, 75 deletions

diff --git a/src/solvers/coord/checkdata.h b/src/solvers/coord/checkdata.h
index e448e8f..51265a8 100644
--- a/src/solvers/coord/checkdata.h
+++ b/src/solvers/coord/checkdata.h
@@ -1,14 +1,39 @@
-STATIC long long checkdata_coord(
+STATIC long long checkdata_coord_dispatch(
     const char *, unsigned long long, const unsigned char *);
+STATIC long long checkdata_coord(
+    const coord_t *, unsigned long long, const unsigned char *);
+STATIC long long checkdata_multicoord(
+    const multicoord_t *, unsigned long long, const unsigned char *);
 
 STATIC long long
-checkdata_coord(
+checkdata_coord_dispatch(
         const char *solver,
         unsigned long long data_size,
         const unsigned char *data
 )
 {
-        coord_t *coord;
+        coord_t *c;
+        multicoord_t *mc;
+
+        parse_coord_and_trans(solver, &c, &mc, NULL);
+
+        if (c != NULL)
+                return checkdata_coord(c, data_size, data);
+
+        if (mc != NULL)
+                return checkdata_multicoord(mc, data_size, data);
+
+        LOG("[cehckdata] Unknown coordinate solver '%s'\n", solver);
+        return NISSY_ERROR_DATA;
+}
+
+STATIC long long
+checkdata_coord(
+        const coord_t *coord,
+        unsigned long long data_size,
+        const unsigned char *data
+)
+{
         const unsigned char *table;
         tableinfo_t info;
         int64_t err;
@@ -19,12 +44,6 @@ checkdata_coord(
                 return NISSY_ERROR_DATA;
         }
 
-        parse_coord_and_trans(solver, &coord, NULL);
-        if (coord == NULL) {
-                LOG("[cehckdata] Unknown coordinate solver '%s'\n", solver);
-                return NISSY_ERROR_DATA;
-        }
-
         table = data + INFOSIZE;
         err = readtableinfo(data_size, data, &info);
         if (err != NISSY_OK) {
@@ -63,3 +82,41 @@ checkdata_coord(
 
         return NISSY_OK;
 }
+
+STATIC long long
+checkdata_multicoord(
+        const multicoord_t *mcoord,
+        unsigned long long data_size,
+        const unsigned char *data
+)
+{
+        long long r;
+        size_t i, of, s;
+
+        for (of = INFOSIZE, i = 0; mcoord->coordinates[i] != NULL; i++) {
+                LOG("[checkdata] %s: checking data for %s\n", mcoord->name,
+                    mcoord->coordinates[i]->name);
+                s = gendata_coord(mcoord->coordinates[i], NULL);
+                if (s > data_size-of)
+                        return NISSY_ERROR_DATA;
+
+                r = checkdata_coord(mcoord->coordinates[i], s, data + of);
+                if (r != NISSY_OK)
+                        return r;
+
+                LOG("[checkdata] Ok\n");
+
+                of += s;
+
+                /* Skip padding */
+                while (of % 8 != 0) {
+                        if (data[of] != 0)
+                                LOG("[checkdata] Warning: some unused bytes "
+                                    "are not set to zero. Please report this "
+                                    "bug.\n");
+                        of++;
+                }
+        }
+
+        return NISSY_OK;
+}
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
index 901b8bd..5b5f57b 100644
--- a/src/solvers/coord/common.h
+++ b/src/solvers/coord/common.h
@@ -6,7 +6,6 @@ STATIC bool coord_isnasty_generic(
     const coord_t [static 1], uint64_t, const unsigned char *);
 STATIC size_t coord_gendata_generic(const coord_t [static 1], unsigned char *);
 
-STATIC void append_coord_name(const coord_t [static 1], char *);
 STATIC bool solution_lastqt_cw(const solution_moves_t [static 1]);
 STATIC bool coord_can_switch(const coord_t [static 1], const unsigned char *,
     size_t, const uint8_t *);
@@ -106,7 +105,7 @@ coord_gendata_generic(
                 .maxvalue = 0,
                 .next = 0
         };
-        append_coord_name(coord, info.solver);
+        append_name(&info, coord->name);
 
         for (i = 0, n = 0; i < coord->sym.max; i++) {
                 if (classttrep[i] != 0xFFFFFFFF)
@@ -142,18 +141,6 @@ coord_gendata_generic(
         return coord_datasize;
 }
 
-STATIC void
-append_coord_name(const coord_t coord[static 1], char *str)
-{
-        int i, j;
-
-        i = 0;
-        j = strlen(str);
-        while (coord->name[i]) str[j++] = coord->name[i++];
-
-        str[j] = '\0';
-}
-
 STATIC bool
 solution_lastqt_cw(const solution_moves_t s[static 1])
 {
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
index 3b42e31..beb1b6a 100644
--- a/src/solvers/coord/coord.h
+++ b/src/solvers/coord/coord.h
@@ -5,8 +5,11 @@
 #include "dreo.h"
 #include "drfinnoe.h"
 #include "drslice.h"
+#include "cpepe.h"
+#include "drfin.h"
 #include "list.h"
 #include "utils.h"
 #include "gendata.h"
 #include "checkdata.h"
 #include "solve.h"
+#include "multisolve.h"
diff --git a/src/solvers/coord/cpepe.h b/src/solvers/coord/cpepe.h
index 37ec014..9c9bffc 100644
--- a/src/solvers/coord/cpepe.h
+++ b/src/solvers/coord/cpepe.h
@@ -15,29 +15,27 @@ STATIC coord_t coordinate_cpepe = {
         .moves_mask_gendata = MM18_DR,
         .moves_mask_solve = MM18_DR,
         .is_admissible = &solution_always_valid,
-        .is_solvable = &is_drfin_solvable,
+        .is_solvable = &is_drfinnoe_solvable,
         .is_solved = NULL,
         .allow_niss = false,
         .pruning_distribution = {
-                /* TODO */
-                [0] = 0,
-                [1] = 0,
-                [2] = 0,
-                [3] = 0,
-                [4] = 0,
-                [5] = 0,
-                [6] = 0,
-                [7] = 0,
-                [8] = 0,
-                [9] = 0,
-                [10] = 0,
-                [11] = 0,
-                [12] = 0,
-                [13] = 0,
-                [14] = 0,
-                [15] = 0,
+                [0] = 1,
+                [1] = 3,
+                [2] = 10,
+                [3] = 44,
+                [4] = 214,
+                [5] = 846,
+                [6] = 2413,
+                [7] = 5122,
+                [8] = 8639,
+                [9] = 12128,
+                [10] = 12571,
+                [11] = 12985,
+                [12] = 7754,
+                [13] = 3366,
+                [14] = 336,
         },
-        .pruning_max = 15, /* TODO */
+        .pruning_max = 14,
         .sym = {
                 .classes = CLASSES_CP_16,
                 .max = FACT_8,
diff --git a/src/solvers/coord/drfin.h b/src/solvers/coord/drfin.h
new file mode 100644
index 0000000..569419b
--- /dev/null
+++ b/src/solvers/coord/drfin.h
@@ -0,0 +1,17 @@
+STATIC bool is_drfin_solvable(cube_t);
+
+STATIC multicoord_t multicoordinate_drfin = {
+        .name = "DRFIN",
+        .coordinates = { &coordinate_cpepe, &coordinate_drfinnoe, NULL },
+        .moves_mask = MM18_DR,
+        .is_solvable = is_drfin_solvable,
+};
+
+STATIC bool
+is_drfin_solvable(cube_t cube)
+{
+        return coord_eo(cube) == 0 &&
+               coord_eo(transform_edges(cube, TRANS_URr)) == 0 &&
+               coord_co(cube) == 0 &&
+               issolvable((oriented_cube_t){.cube = cube, .orientation = 0});
+}
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
index 0b108cd..cbc8774 100644
--- a/src/solvers/coord/gendata.h
+++ b/src/solvers/coord/gendata.h
@@ -1,4 +1,6 @@
 STATIC size_t gendata_coord(const coord_t [static 1], unsigned char *);
+STATIC size_t gendata_multicoord(
+    const multicoord_t [static 1], unsigned char *);
 STATIC long long gendata_coord_dispatch(const char *, unsigned long long,
     unsigned char *);
 STATIC tableinfo_t genptable_coord(
@@ -23,15 +25,18 @@ gendata_coord_dispatch(
 )
 {
         coord_t *coord;
+        multicoord_t *mcoord;
 
-        parse_coord_and_trans(coordstr, &coord, NULL);
+        parse_coord_and_trans(coordstr, &coord, &mcoord, NULL);
 
-        if (coord == NULL) {
-                LOG("Error: could not parse coordinate '%s'\n", coordstr);
-                return NISSY_ERROR_INVALID_SOLVER;
-        }
+        if (coord != NULL)
+                return gendata_coord(coord, buf);
+
+        if (mcoord != NULL)
+                return gendata_multicoord(mcoord, buf);
 
-        return gendata_coord(coord, buf);
+        LOG("Error: could not parse coordinate '%s'\n", coordstr);
+        return NISSY_ERROR_INVALID_SOLVER;
 }
 
 STATIC size_t
@@ -70,8 +75,7 @@ gendata_coord(const coord_t coord[static 1], unsigned char *buf)
                         .maxvalue = 0,
                 };
 
-                append_coord_name(coord, coord_data_info.solver);
-
+                append_name(&coord_data_info, coord->name);
                 writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf);
 
                 pruningbuf = buf + INFOSIZE + coord_dsize;
@@ -91,6 +95,50 @@ gendata_coord_error:
         return 0;
 }
 
+STATIC size_t
+gendata_multicoord(const multicoord_t mcoord[static 1], unsigned char *buf)
+{
+        unsigned char *b;
+        size_t i, s, ret;
+        tableinfo_t info;
+
+        info = (tableinfo_t) {
+                .solver = "multicoordinate table for ",
+                .type = TABLETYPE_MULTI,
+                .infosize = INFOSIZE,
+                .fullsize = INFOSIZE,
+                .hash = 0,
+                .next = INFOSIZE,
+
+                /* Unknown / non-applicable values */
+                .entries = 0,
+                .classes = 0,
+                .bits = 0,
+                .base = 0,
+                .maxvalue = 0,
+        };
+
+        append_name(&info, mcoord->name);
+        if (buf != NULL)
+                writetableinfo(&info, INFOSIZE, buf);
+        ret = INFOSIZE;
+
+        for (i = 0; mcoord->coordinates[i] != NULL; i++) {
+                b = buf == NULL ? NULL : buf + ret;
+                s = gendata_coord(mcoord->coordinates[i], b);
+                if (s == 0)
+                        return 0;
+
+                ret += s;
+
+                /* Pad so that each coordinate's table is 8-byte aligned */
+                while (ret % 8 != 0)
+                        buf[ret++] = 0;
+        }
+
+        return ret;
+}
+
 STATIC tableinfo_t
 genptable_coord(
         const coord_t coord[static 1],
@@ -118,7 +166,7 @@ genptable_coord(
 
         memset(table, 0xFF, tablesize);
         memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
-        append_coord_name(coord, info.solver);
+        append_name(&info, coord->name);
 
         tot = info.distribution[0] =
             genptable_coord_init_solved(coord, data, table);
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
index 929e0fd..7bc8041 100644
--- a/src/solvers/coord/list.h
+++ b/src/solvers/coord/list.h
@@ -4,5 +4,11 @@ coord_t *all_coordinates[] = {
         &coordinate_dreo,
         &coordinate_drfinnoe,
         &coordinate_drslice,
+        &coordinate_cpepe,
+        NULL
+};
+
+multicoord_t *all_multicoordinates[] = {
+        &multicoordinate_drfin,
         NULL
 };
diff --git a/src/solvers/coord/multisolve.h b/src/solvers/coord/multisolve.h
new file mode 100644
index 0000000..f3589e8
--- /dev/null
+++ b/src/solvers/coord/multisolve.h
@@ -0,0 +1,298 @@
+/*
+For now the only multicoordinate is DRFIN, and this solver reflects this.
+For example, NISS is not available.
+*/
+
+typedef struct {
+        cube_t cube;
+        cube_t inverse;
+        uint8_t target_depth;
+        solution_moves_t *solution_moves;
+        solution_settings_t *solution_settings;
+        solution_list_t *solution_list;
+        multicoord_t *mcoord;
+        const unsigned char *coord_data[MAX_MULTICOORD_NCOORDS];
+        const unsigned char *ptable[MAX_MULTICOORD_NCOORDS];
+} dfsarg_solve_multicoord_t;
+
+STATIC int64_t solve_multicoord(oriented_cube_t, multicoord_t [static 1],
+    uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t,
+    const unsigned char *, size_t, char *, int (*)(void *), void *);
+STATIC long long solve_multicoord_dispatch(oriented_cube_t, const char *,
+    unsigned, unsigned, unsigned, unsigned, unsigned, unsigned,
+    unsigned long long, const unsigned char *, unsigned, char *,
+    long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *);
+STATIC bool multicoord_solution_admissible(
+    const dfsarg_solve_multicoord_t [static 1]);
+STATIC bool multicoord_dfs_stop(const dfsarg_solve_multicoord_t [static 1]);
+STATIC int64_t solve_multicoord_dfs(dfsarg_solve_multicoord_t [static 1]);
+
+STATIC bool
+multicoord_solution_admissible(const dfsarg_solve_multicoord_t arg[static 1])
+{
+        uint8_t n, i;
+        const coord_t *c;
+
+        n = arg->solution_moves->nmoves + arg->solution_moves->npremoves;
+        if (arg->target_depth != n)
+                return false;
+
+        for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) {
+                c = arg->mcoord->coordinates[i];
+                if (c->is_admissible != NULL &&
+                    !c->is_admissible(arg->solution_moves))
+                        return false;
+        }
+
+        return true;
+}
+
+STATIC bool
+multicoord_dfs_stop(const dfsarg_solve_multicoord_t arg[static 1])
+{
+        uint8_t pval, i;
+        uint64_t cval;
+        const coord_t *c;
+
+        for (i = 0, pval = 0; arg->mcoord->coordinates[i] != NULL; i++) {
+                c = arg->mcoord->coordinates[i];
+
+                cval = c->coord(arg->cube, arg->coord_data[i]);
+                pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval));
+
+                cval = c->coord(arg->inverse, arg->coord_data[i]);
+                pval = MAX(pval, get_coord_pval(c, arg->ptable[i], cval));
+        }
+
+        return arg->solution_moves->nmoves + pval > arg->target_depth;
+}
+
+STATIC int64_t
+solve_multicoord_dfs(dfsarg_solve_multicoord_t arg[static 1])
+{
+        uint8_t m, l, i;
+        uint32_t mm;
+        uint64_t coord;
+        int64_t n, ret;
+        const coord_t *c;
+        cube_t backup_cube, backup_inverse;
+
+        for (i = 0; arg->mcoord->coordinates[i] != NULL; i++) {
+                c = arg->mcoord->coordinates[i];
+                coord = c->coord(arg->cube, arg->coord_data[i]);
+                if (!coord_is_solved(c, coord, arg->coord_data[i]))
+                        goto solve_multicoord_dfs_notsolved;
+        }
+
+        /* All coordinates are solved */
+        if (!multicoord_solution_admissible(arg))
+                return 0;
+        return appendsolution(arg->solution_moves,
+            arg->solution_settings, arg->solution_list);
+
+solve_multicoord_dfs_notsolved:
+        if (multicoord_dfs_stop(arg))
+                return 0;
+
+        backup_cube = arg->cube;
+        backup_inverse = arg->inverse;
+        ret = 0;
+
+        l = arg->solution_moves->nmoves;
+        mm = arg->mcoord->moves_mask;
+        if (l != 0) {
+                m = arg->solution_moves->moves[l-1];
+                mm &= allowedmask[movebase(m)];
+        }
+        arg->solution_moves->nmoves++;
+
+        for (m = 0; m < NMOVES; m++) {
+                if (!(mm & (UINT32_C(1) << (uint32_t)m)))
+                        continue;
+
+                arg->solution_moves->moves[l] = m;
+                arg->cube = move(backup_cube, m);
+                arg->inverse = premove(backup_inverse, m);
+                n = solve_multicoord_dfs(arg);
+                if (n < 0)
+                        return n;
+                ret += n;
+        }
+
+        arg->solution_moves->nmoves--;
+        arg->cube = backup_cube;
+        arg->inverse = backup_inverse;
+
+        return ret;
+}
+
+STATIC long long
+solve_multicoord_dispatch(
+        oriented_cube_t oc,
+        const char *coord_and_trans,
+        unsigned nissflag,
+        unsigned minmoves,
+        unsigned maxmoves,
+        unsigned maxsolutions,
+        unsigned optimal,
+        unsigned threads,
+        unsigned long long data_size,
+        const unsigned char *data,
+        unsigned solutions_size,
+        char *sols,
+        long long stats[static NISSY_SIZE_SOLVE_STATS],
+        int (*poll_status)(void *),
+        void *poll_status_data
+)
+{
+        multicoord_t *mcoord;
+        uint8_t trans;
+
+        parse_coord_and_trans(coord_and_trans, NULL, &mcoord, &trans);
+
+        if (mcoord == NULL) {
+                LOG("Error: could not parse coordinate from '%s'\n",
+                    coord_and_trans);
+                return NISSY_ERROR_INVALID_SOLVER;
+        }
+
+        if (trans == UINT8_ERROR) {
+                LOG("Error: could not parse transformation from '%s'\n",
+                    coord_and_trans);
+                return NISSY_ERROR_INVALID_SOLVER;
+        }
+
+        return solve_multicoord(oc, mcoord, trans, minmoves,
+            maxmoves, maxsolutions, optimal, threads, data_size, data,
+            solutions_size, sols, poll_status, poll_status_data);
+}
+
+STATIC int64_t
+solve_multicoord(
+        oriented_cube_t oc,
+        multicoord_t mcoord [static 1],
+        uint8_t trans,
+        uint8_t minmoves,
+        uint8_t maxmoves,
+        uint64_t maxsolutions,
+        uint8_t optimal,
+        uint8_t threads,
+        uint64_t data_size,
+        const unsigned char *data,
+        size_t solutions_size,
+        char *sols,
+        int (*poll_status)(void *),
+        void *poll_status_data
+)
+{
+        int8_t d;
+        size_t j, of;
+        uint64_t i;
+        int64_t err;
+        cube_t c;
+        const coord_t *coord;
+        dfsarg_solve_multicoord_t arg;
+        tableinfo_t info;
+        solution_moves_t solution_moves;
+        solution_settings_t solution_settings;
+        solution_list_t solution_list;
+
+        c = transform(oc.cube, trans);
+
+        if (!mcoord->is_solvable(c))
+                goto solve_multicoord_error_unsolvable;
+
+        if (!solution_list_init(&solution_list, solutions_size, sols))
+                goto solve_multicoord_error_buffer;
+
+        solution_moves_reset(&solution_moves);
+
+        solution_settings = (solution_settings_t) {
+                .tmask = TM_SINGLE(inverse_trans(trans)),
+                .unniss = false,
+                .maxmoves = maxmoves,
+                .maxsolutions = maxsolutions,
+                .optimal = optimal,
+                .orientation = oc.orientation,
+        };
+
+        arg = (dfsarg_solve_multicoord_t) {
+                .cube = c,
+                .inverse = inverse(c),
+                .mcoord = mcoord,
+                .solution_moves = &solution_moves,
+                .solution_settings = &solution_settings,
+                .solution_list = &solution_list,
+        };
+
+        for (j = 0, of = INFOSIZE; mcoord->coordinates[j] != NULL; j++) {
+                if (readtableinfo(data_size-of, data+of, &info) != NISSY_OK)
+                        goto solve_multicoord_error_data;
+
+                if (info.type == TABLETYPE_PRUNING) {
+                        /* Only the pruning table */
+                        arg.coord_data[j] = NULL;
+                        arg.ptable[j] = data + of + INFOSIZE;
+                        of += info.fullsize;
+                } else {
+                        /* Coordinate has extra data */
+                        arg.coord_data[j] = data + of + INFOSIZE;
+                        arg.ptable[j] = data + of + info.next + INFOSIZE;
+                        of += info.fullsize;
+                        if (readtableinfo(data_size-of, data+of, &info)
+                            != NISSY_OK)
+                                goto solve_multicoord_error_data;
+                        of += info.fullsize;
+                }
+
+                /* Skip padding */
+                while (of % 8 != 0)
+                        of++;
+        }
+
+        for (j = 0; mcoord->coordinates[j] != NULL; j++) {
+                coord = mcoord->coordinates[j];
+                i = coord->coord(c, arg.coord_data[j]);
+                if (!coord_is_solved(coord, i, arg.coord_data[j]))
+                        goto solve_multicoord_notsolved;
+        }
+
+        /* All coordinates are solved */
+        if (minmoves == 0 && !appendsolution(&solution_moves,
+            &solution_settings, &solution_list))
+                goto solve_multicoord_error_buffer;
+        goto solve_multicoord_done;
+
+solve_multicoord_notsolved:
+        for (
+            d = MAX(minmoves, 1);
+            !solutions_done(&solution_list, &solution_settings, d);
+            d++
+        ) {
+                if (d >= 12)
+                        LOG("[%s solve] Found %" PRIu64 " solutions, "
+                            "searching at depth %" PRId8 "\n",
+                            mcoord->name, solution_list.nsols, d);
+
+                arg.target_depth = d;
+                solution_moves_reset(arg.solution_moves);
+                if ((err = solve_multicoord_dfs(&arg)) < 0)
+                        return err;
+        }
+
+solve_multicoord_done:
+        return (int64_t)solution_list.nsols;
+
+solve_multicoord_error_data:
+        LOG("[%s solve] Error reading table\n", mcoord->name);
+        return NISSY_ERROR_DATA;
+
+solve_multicoord_error_buffer:
+        LOG("[%s solve] Error appending solution to buffer: size too small\n",
+            mcoord->name);
+        return NISSY_ERROR_BUFFER_SIZE;
+
+solve_multicoord_error_unsolvable:
+        LOG("[%s solve] Error: cube not ready\n", mcoord->name);
+        return NISSY_ERROR_UNSOLVABLE_CUBE;
+}
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
index f9ee06e..72bc064 100644
--- a/src/solvers/coord/solve.h
+++ b/src/solvers/coord/solve.h
@@ -52,10 +52,6 @@ coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
         /* If only inverse moves are allowed */
         if (flag == NISSY_NISSFLAG_INVERSE)
                 return false;
-        
-        /* It's the first move */
-        if (nn + ni == 0)
-                return true;
 
         /* Pruning table check */
         if (!(flag & NISSY_NISSFLAG_MIXED) || ni != 0) {
@@ -64,6 +60,10 @@ coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
                 if (nn + ni + pval > arg->target_depth)
                         return false;
         }
+        
+        /* It's the first move */
+        if (nn + ni == 0)
+                return true;
 
         if (arg->lastisnormal) {
                 /* Can continue if we have already switched */
@@ -106,10 +106,6 @@ coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
         /* If only normal moves are allowed */
         if (flag == NISSY_NISSFLAG_NORMAL)
                 return false;
-        
-        /* It's the first move */
-        if (nn + ni == 0)
-                return true;
 
         /* Pruning table check */
         if (!(flag & NISSY_NISSFLAG_MIXED) || nn != 0) {
@@ -118,6 +114,10 @@ coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
                 if (nn + ni + pval > arg->target_depth)
                         return false;
         }
+        
+        /* It's the first move */
+        if (nn + ni == 0)
+                return true;
 
         if (!arg->lastisnormal) {
                 /* Can continue if we have already switched */
@@ -261,7 +261,7 @@ solve_coord_dispatch(
         coord_t *coord;
         uint8_t trans;
 
-        parse_coord_and_trans(coord_and_trans, &coord, &trans);
+        parse_coord_and_trans(coord_and_trans, &coord, NULL, &trans);
 
         if (coord == NULL) {
                 LOG("Error: could not parse coordinate from '%s'\n",
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
index f36ecaf..73484ba 100644
--- a/src/solvers/coord/types_macros.h
+++ b/src/solvers/coord/types_macros.h
@@ -14,6 +14,8 @@
 #define COORD_ISNASTY_MASK  (UINT32_C(0xFF) << COORD_ISNASTY_SHIFT)
 #define COORD_ISNASTY(d)    (((d) & COORD_ISNASTY_MASK) >> COORD_ISNASTY_SHIFT)
 
+#define MAX_MULTICOORD_NCOORDS 4
+
 typedef struct {
         const char name[255];
         uint64_t (*coord)(cube_t, const unsigned char *);
@@ -42,3 +44,10 @@ typedef struct {
                 cube_t (*merge)(cube_t, cube_t);
         } sym;
 } coord_t;
+
+typedef struct {
+        const char name[255];
+        coord_t *coordinates[MAX_MULTICOORD_NCOORDS];
+        uint64_t moves_mask;
+        bool (*is_solvable)(cube_t);
+} multicoord_t;
diff --git a/src/solvers/coord/utils.h b/src/solvers/coord/utils.h
index 93704cc..c8a9338 100644
--- a/src/solvers/coord/utils.h
+++ b/src/solvers/coord/utils.h
@@ -1,19 +1,35 @@
 STATIC coord_t *parse_coord(size_t, const char *);
-STATIC void parse_coord_and_trans(const char *, coord_t **, uint8_t *);
+STATIC multicoord_t *parse_multicoord(size_t, const char *);
+STATIC void parse_coord_and_trans(
+    const char *, coord_t **, multicoord_t **, uint8_t *);
 STATIC long long dataid_coord(const char *, char [static NISSY_SIZE_DATAID]);
 
 STATIC coord_t *
 parse_coord(size_t n, const char *coord)
 {
         int i;
+        const char *name;
 
-        /*
-        TODO Some coordinates are parsed incorrectly, e.g. DRFINNOE
-        TODO is matched by DRFIN. Check that strncmp is used correctly.
-        */
-        for (i = 0; all_coordinates[i] != NULL; i++)
-                if (!strncmp(all_coordinates[i]->name, coord, n))
+        for (i = 0; all_coordinates[i] != NULL; i++) {
+                name = all_coordinates[i]->name;
+                if (n == strlen(name) && !strncmp(name, coord, n))
                         return all_coordinates[i];
+        }
+
+        return NULL;
+}
+
+STATIC multicoord_t *
+parse_multicoord(size_t n, const char *coord)
+{
+        int i;
+        const char *name;
+
+        for (i = 0; all_multicoordinates[i] != NULL; i++) {
+                name = all_multicoordinates[i]->name;
+                if (n == strlen(name) && !strncmp(name, coord, n))
+                        return all_multicoordinates[i];
+        }
 
         return NULL;
 }
@@ -22,18 +38,22 @@ STATIC void
 parse_coord_and_trans(
         const char *str,
         coord_t **coord,
+        multicoord_t **mcoord,
         uint8_t *trans
 )
 {
         size_t i;
 
-        for (i = 6; i < strlen(str); i++)
+        for (i = 7; i < strlen(str); i++)
                 if (str[i] == '_')
                         break;
 
         if (coord != NULL)
                 *coord = parse_coord(i-6, str+6);
 
+        if (mcoord != NULL)
+                *mcoord = parse_multicoord(i-7, str+7);
+
         if (trans != NULL)
                 *trans = i == strlen(str) ?
                     UINT8_ERROR : readrotation(str+i+1);
@@ -43,15 +63,20 @@ STATIC long long
 dataid_coord(const char *ca, char dataid[static NISSY_SIZE_DATAID])
 {
         coord_t *c;
+        multicoord_t *mc;
 
-        parse_coord_and_trans(ca, &c, NULL);
+        parse_coord_and_trans(ca, &c, &mc, NULL);
 
-        if (c == NULL) {
-                LOG("Error: cannot parse coordinate from '%s'\n", ca);
-                return NISSY_ERROR_INVALID_SOLVER;
+        if (c != NULL) {
+                strcpy(dataid, c->name);
+                return NISSY_OK;
         }
 
-        strcpy(dataid, c->name);
+        if (mc != NULL) {
+                strcpy(dataid, mc->name);
+                return NISSY_OK;
+        }
 
-        return NISSY_OK;
+        LOG("Error: cannot parse coordinate from '%s'\n", ca);
+        return NISSY_ERROR_INVALID_SOLVER;
 }
diff --git a/src/solvers/dispatch.h b/src/solvers/dispatch.h
index 484983e..013468c 100644
--- a/src/solvers/dispatch.h
+++ b/src/solvers/dispatch.h
@@ -26,10 +26,17 @@ solver_dispatch_t solver_dispatchers[] = {
         .prefix = "coord_",
         .dataid = dataid_coord,
         .gendata = gendata_coord_dispatch,
-        .checkdata = checkdata_coord,
+        .checkdata = checkdata_coord_dispatch,
         .solve = solve_coord_dispatch,
 },
 {
+        .prefix = "mcoord_",
+        .dataid = dataid_coord,
+        .gendata = gendata_coord_dispatch,
+        .checkdata = checkdata_coord_dispatch,
+        .solve = solve_multicoord_dispatch,
+},
+{
         .prefix = NULL
 }
 };
diff --git a/src/solvers/tables.h b/src/solvers/tables.h
index 1e76fc1..b7a1079 100644
--- a/src/solvers/tables.h
+++ b/src/solvers/tables.h
@@ -8,6 +8,7 @@ STATIC int64_t readtableinfo_n(
     size_t, const unsigned char *, uint8_t, tableinfo_t [static 1]);
 STATIC int64_t writetableinfo(
     const tableinfo_t [static 1], size_t, unsigned char *);
+STATIC void append_name(tableinfo_t [static 1], const char *);
 
 STATIC uint64_t
 read_unaligned_u64(const unsigned char buf[static sizeof(uint64_t)])
@@ -135,3 +136,14 @@ writetableinfo(
 
         return NISSY_OK;
 }
+
+STATIC void
+append_name(tableinfo_t info[static 1], const char *str)
+{
+        int i, j;
+
+        for (i = 0, j = strlen(info->solver); str[i] != '\0'; i++, j++)
+                info->solver[j] = str[i];
+
+        info->solver[j] = '\0';
+}
diff --git a/src/solvers/tables_types_macros.h b/src/solvers/tables_types_macros.h
index 16e1346..b2809b7 100644
--- a/src/solvers/tables_types_macros.h
+++ b/src/solvers/tables_types_macros.h
@@ -6,6 +6,7 @@
 
 #define TABLETYPE_PRUNING        UINT64_C(0)
 #define TABLETYPE_SPECIAL        UINT64_C(1)
+#define TABLETYPE_MULTI          UINT64_C(2)
 
 #define INFO_OFFSET_DISTRIBUTION 0
 #define INFO_OFFSET_TYPE         (INFO_DISTRIBUTION_LEN * sizeof(uint64_t))