More progress on coordinate solver

8 files changed, 274 insertions, 9 deletions

diff --git a/TODO_COORDINATES b/TODO_COORDINATES
index 7e5628b..0202f49 100644
--- a/TODO_COORDINATES
+++ b/TODO_COORDINATES
@@ -1,6 +1,6 @@
-- solver
-  - include NISS
+- solver (from TODOs in appending solution)
 - test solver for EO
+- add NISS (and add tests for NISS EO)
 - make solve parallelized
 - other coordinates
   - gendata must handle symmetry
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
index b54e5e2..1d6e622 100644
--- a/src/solvers/coord/common.h
+++ b/src/solvers/coord/common.h
@@ -6,6 +6,8 @@ coord_t *all_coordinates[] = {
 };
 
 STATIC void append_coord_name(const coord_t *, char *);
+STATIC coord_t *parse_coord(const char *, int);
+STATIC uint8_t parse_axis(const char *, int);
 
 STATIC void
 append_coord_name(const coord_t *coord, char *str)
@@ -18,3 +20,29 @@ append_coord_name(const coord_t *coord, char *str)
 
         str[j] = '\0';
 }
+
+STATIC coord_t *
+parse_coord(const char *coord, int n)
+{
+        int i;
+
+        for (i = 0; all_coordinates[i] != NULL; i++)
+                if (!strncmp(all_coordinates[i]->name, coord, n))
+                        return all_coordinates[i];
+
+        return NULL;
+}
+
+STATIC uint8_t
+parse_axis(const char *axis, int n)
+{
+        if (!strncmp(axis, "UD", n) || !strncmp(axis, "DU", n)) {
+                return AXIS_UD;
+        } else if (!strncmp(axis, "RL", n) || !strncmp(axis, "LR", n)) {
+                return AXIS_RL;
+        } else if (!strncmp(axis, "FB", n) || !strncmp(axis, "BF", n)) {
+                return AXIS_FB;
+        }
+
+        return UINT8_ERROR;
+}
diff --git a/src/solvers/coord/coord_solve.h b/src/solvers/coord/coord_solve.h
index 1d7c036..317cb33 100644
--- a/src/solvers/coord/coord_solve.h
+++ b/src/solvers/coord/coord_solve.h
@@ -1,3 +1,228 @@
 #include "coord_types_macros.h"
 #include "common.h"
 #include "gendata_coord.h"
+
+#define MAXLEN_COORDSOL 20
+
+typedef struct {
+        cube_t cube;
+        uint8_t depth;
+        uint8_t nmoves;
+        uint8_t moves[MAXLEN_COORDSOL];
+        coord_t *coord;
+        const void *coord_data;
+        const uint8_t *ptable;
+        uint8_t trans;
+        int64_t *nsols;
+        int64_t maxsolutions;
+        int optimal;
+        uint8_t *shortest_sol;
+        uint64_t solutions_size;
+        uint64_t *solutions_used;
+        char **solutions;
+} dfsarg_solve_coord_t;
+
+STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t,
+    uint8_t, uint64_t, int, int, uint64_t, const void, uint64_t, char);
+STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t,
+    uint8_t, uint64_t, int, int, uint64_t, const void, uint64_t, char);
+STATIC bool solve_coord_appendchar(char *, uint64_t, uint64_t *, char);
+STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *);
+STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *);
+
+STATIC int64_t
+solve_coord_appendsolution(dfsarg_solve_coord_t *arg)
+{
+        uint8_t i, t, tmoves[MAXLEN_COORDSOL];
+
+        if (*arg->nsols >= arg->maxsolutions ||
+            arg->nmoves > *arg->shortest_sol + arg->optimal)
+                return 0;
+
+        sortparallel(arg->moves, arg->nmoves);
+
+        t = inverse_trans(arg->trans);
+        for (i = 0; i < arg->nmoves; i++)
+                tmoves[i] = transform_move(arg->moves[i], t);
+
+        /* TODO append tmoves[] */
+
+        return 1;
+}
+
+STATIC bool
+solve_coord_appendchar(char *s, uint64_t s_size, uint64_t *s_used, char c)
+{
+        if (s_size == *s_used)
+                return false;
+
+        s[*s_used] = c;
+        (*s_used)++;
+
+        return true;
+}
+
+STATIC int64_t
+solve_coord_dfs(dfsarg_solve_coord_t *arg)
+{
+        uint64_t coord;
+        uint8_t pval;
+
+        coord = arg->coord->coord(arg->cube, arg->coord_data);
+
+        if (coord == 0) {
+                if (arg->nmoves != arg->depth)
+                        return 0;
+                return solve_coord_appendsolution(arg);
+        }
+
+        pval = get_coord_pval(arg->coord, arg->ptable, coord);
+        if (arg->nmoves + pval > arg->depth)
+                return 0;
+
+        /* TODO recursive call */
+        /* Is allowednextmove available here? */
+
+        return 0;
+}
+
+STATIC int64_t
+solve_coord_dispatch(
+        cube_t cube,
+        const char *coord_axis,
+        uint8_t nissflag,
+        uint8_t minmoves,
+        uint8_t maxmoves,
+        uint64_t maxsolutions,
+        int optimal,
+        int threads,
+        uint64_t data_size,
+        const void *data,
+        uint64_t sols_size,
+        char *sols
+)
+{
+        int i, n;
+        coord_t *coord;
+        uint8_t axis;
+
+        n = strlen(coord_axis);
+        for (i = 0; coord_axis[i] != ' ' && coord_axis[i] != '\0'; i++) ;
+
+        coord = parse_coord(coord_axis, i);
+        axis = parse_axis(coord_axis + i + 1, n - i - 1);
+
+        if (coord == NULL) {
+                LOG("Could not parse coordinate '%s'\n", coord_axis);
+                return NISSY_ERROR_INVALID_SOLVER;
+        }
+
+        if (axis == UINT8_ERROR) {
+                LOG("Could not parse axis from '%s'\n", coord_axis);
+                return NISSY_ERROR_INVALID_SOLVER;
+        }
+
+        return solve_coord(cube, coord, axis, nissflag, minmoves, maxmoves,
+            maxsolutions, optimal, threads, data_size, data, sols_size, sols);
+}
+
+STATIC int64_t
+solve_coord(
+        cube_t cube,
+        coord_t *coord,
+        uint8_t axis,
+        uint8_t nissflag,
+        uint8_t minmoves,
+        uint8_t maxmoves,
+        uint64_t maxsolutions,
+        int optimal,
+        int threads,
+        uint64_t data_size,
+        const void data,
+        uint64_t sols_size,
+        char *sols
+)
+{
+        int8_t d;
+        uint8_t t, shortest_sol;
+        int64_t nsols;
+        uint64_t sols_used;
+        cube_t c;
+        const void *coord_data;
+        const uint8_t *ptable;
+        dfsarg_solve_coord_t arg;
+        tableinfo_t info;
+
+        if (readtableinfo(data_size, data, &info) != NISSY_OK)
+                goto solve_coord_error_data;
+
+        if (info.type == TABLETYPE_PRUNING) {
+                /* Only the pruning table */
+                coord_data = NULL;
+                ptable = (uint8_t *)data + INFOSIZE;
+        } else {
+                /* Coordinate has extra data */
+                coord_data = data + INFOSIZE;
+                ptable = (uint8_t *)data + info.next + INFOSIZE;
+        }
+
+        nsols = 0;
+        sols_used = 0;
+        shortest_sol = MAXLEN_COORDSOL + 1;
+        c = transform(cube, t);
+        t = coord->axistrans[axis];
+
+        arg = (dfsarg_solve_coord_t) {
+                .cube = c,
+                .coord = coord,
+                .coord_data = coord_data,
+                .ptable = ptable,
+                .trans = t,
+                .nsols = &nsols,
+                .maxsolutions = (int64_t)maxsolutions,
+                .optimal = optimal,
+                .shortest_sol = &shortest_sol,
+                .solutions_size = sols_size,
+                .solutions_used = &sols_used,
+                .solutions = &sols,
+        };
+
+        if (coord->coord(c, coord_data) == 0) {
+                if (minmoves == 0) {
+                        nsols = 1;
+                        if (!solve_coord_appendchar(
+                            sols, sols_size, &sols_used, '\n'))
+                                goto solve_coord_error_buffer;
+                }
+                goto solve_coord_done;
+        }
+
+        for (
+            d = MAX(minmoves, 1);
+            d <= maxmoves && nsols < (int64_t)maxsolutions
+                && !(nsols != 0 && d > shortest_sol + optimal);
+            d++
+        ) {
+                if (d >= 10)
+                        LOG("Found %" PRId64 " solutions, searching at depth %"
+                            PRId8 "\n", nsols, d);
+
+                arg.depth = d;
+                arg.nmoves = 0;
+                nsols += solve_coord_dfs(&arg);
+        }
+
+solve_coord_done:
+        if (!solve_coord_appendchar(sols, sols_size, &sols_used, '\0'))
+                goto solve_coord_error_buffer;
+
+        return nsols;
+
+solve_coord_error_data:
+        LOG("solve_coord: error reading table\n");
+        return NISSY_ERROR_DATA;
+
+solve_coord_error_buffer:
+        LOG("Could not append solution to buffer: size too small\n");
+        return NISSY_ERROR_BUFFER_SIZE;
+}
diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h
index 4f2877c..594f594 100644
--- a/src/solvers/coord/coord_types_macros.h
+++ b/src/solvers/coord/coord_types_macros.h
@@ -10,4 +10,5 @@ typedef struct {
         uint64_t max;
         uint32_t moves_mask;
         uint64_t trans_mask;
+        uint8_t axistrans[3];
 } coord_t;
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
index d6604d9..449397f 100644
--- a/src/solvers/coord/eo.h
+++ b/src/solvers/coord/eo.h
@@ -10,6 +10,11 @@ STATIC coord_t coordinate_eo = {
         .max = POW_2_11,
         .trans_mask = TM_ALLTRANS,
         .moves_mask = MM_ALLMOVES,
+        .axistrans = {
+                [AXIS_UD] = TRANS_FDr,
+                [AXIS_RL] = TRANS_URr,
+                [AXIS_FB] = TRANS_UFr,
+        },
 };
 
 STATIC uint64_t
diff --git a/src/solvers/coord/gendata_coord.h b/src/solvers/coord/gendata_coord.h
index b3932cd..3d385e9 100644
--- a/src/solvers/coord/gendata_coord.h
+++ b/src/solvers/coord/gendata_coord.h
@@ -7,14 +7,16 @@ STATIC void set_coord_pval(const coord_t *, uint8_t *, uint64_t, uint8_t);
 STATIC size_t
 gendata_coordinate_name(const char *name, void *buf)
 {
-        int i;
+        coord_t *coord;
 
-        for (i = 0; all_coordinates[i] != NULL; i++)
-                if (strcmp(all_coordinates[i]->name, name) == 0)
-                        return gendata_coordinate(all_coordinates[i], buf);
+        coord = parse_coord(name, strlen(name));
+        if (coord == NULL) {
+                LOG("Cannot generate data for coordinate '%s': not found\n",
+                    name);
+                return 0;
+        }
 
-        LOG("Cannot generate data for coordinate '%s': not found\n", name);
-        return 0;
+        return gendata_coordinate(coord, buf);
 }
 
 STATIC size_t
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 6277082..44f6a89 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -457,7 +457,7 @@ solve_h48(
         pthread_t thread[THREADS];
         pthread_mutex_t solutions_mutex;
 
-        if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
+        if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
                 goto solve_h48_error_data;
 
         cocsepdata = (uint32_t *)((char *)data + INFOSIZE);
diff --git a/src/utils/constants.h b/src/utils/constants.h
index 3d8bf5e..1db1940 100644
--- a/src/utils/constants.h
+++ b/src/utils/constants.h
@@ -93,6 +93,10 @@ STATIC int64_t binomial[12][12] = {
 #define TRANS_BDm UINT8_C(46)
 #define TRANS_BLm UINT8_C(47)
 
+#define AXIS_UD   UINT8_C(0)
+#define AXIS_RL   UINT8_C(1)
+#define AXIS_FB   UINT8_C(2)
+
 #define NMOVES  (1+MOVE_B3)
 #define NTRANS  (1+TRANS_BLm)