1 files changed, 298 insertions, 0 deletions

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;
+}