added drslice coordinate

11 files changed, 197 insertions, 52 deletions

diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
index d38b7d3..901b8bd 100644
--- a/src/solvers/coord/common.h
+++ b/src/solvers/coord/common.h
@@ -10,6 +10,8 @@ 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 *);
+STATIC bool coord_is_solved(
+    const coord_t [static 1], uint64_t, const unsigned char *);
 
 STATIC uint64_t
 coord_coord_generic(
@@ -182,8 +184,11 @@ coord_can_switch(
 
         uint64_t i;
 
-        if (n == 0)
-                return true;
+        DBG_ASSERT(n > 0, "Error: cannot check if coordinate solver "
+            "can use NISS after 0 moves");
+
+        if (!coord->allow_niss)
+                return false;
 
         i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
         if (i == 0)
@@ -195,3 +200,13 @@ coord_can_switch(
         i = coord->coord(move(SOLVED_CUBE, moves[n-1]), data);
         return i != 0;
 }
+
+STATIC bool
+coord_is_solved(
+        const coord_t coord[static 1],
+        uint64_t i,
+        const unsigned char *data
+)
+{
+        return coord->is_solved == NULL ? i == 0 : coord->is_solved(i, data);
+}
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
index e487964..3b42e31 100644
--- a/src/solvers/coord/coord.h
+++ b/src/solvers/coord/coord.h
@@ -4,6 +4,7 @@
 #include "dr.h"
 #include "dreo.h"
 #include "drfinnoe.h"
+#include "drslice.h"
 #include "list.h"
 #include "utils.h"
 #include "gendata.h"
diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h
index 7f7af4f..487e79c 100644
--- a/src/solvers/coord/dr.h
+++ b/src/solvers/coord/dr.h
@@ -20,7 +20,8 @@ STATIC coord_t coordinate_dr = {
         .gendata = coordinate_dr_gendata,
         .max = DREOESEP_CLASSES * POW_3_7,
         .trans_mask = TM_UDFIX,
-        .moves_mask = MM18_ALLMOVES,
+        .moves_mask_gendata = MM18_ALLMOVES,
+        .moves_mask_solve = MM18_ALLMOVES,
         .axistrans = {
                 [AXIS_UD] = TRANS_UFr,
                 [AXIS_RL] = TRANS_RFr,
@@ -28,6 +29,8 @@ STATIC coord_t coordinate_dr = {
         },
         .is_admissible = &solution_lastqt_cw,
         .is_solvable = &is_eoco_solvable,
+        .is_solved = NULL,
+        .allow_niss = true,
         .pruning_distribution = {
                 [0] = 1,
                 [1] = 1,
diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h
index 31f7008..8780807 100644
--- a/src/solvers/coord/dreo.h
+++ b/src/solvers/coord/dreo.h
@@ -19,7 +19,8 @@ STATIC coord_t coordinate_dreo = {
         .gendata = coordinate_dreo_gendata,
         .max = DRESEP_CLASSES * POW_3_7,
         .trans_mask = TM_UDRLFIX,
-        .moves_mask = MM18_EO,
+        .moves_mask_gendata = MM18_EO,
+        .moves_mask_solve = MM18_EO,
         .axistrans = {
                 [AXIS_UD] = TRANS_UFr,
                 [AXIS_RL] = TRANS_RFr,
@@ -27,6 +28,8 @@ STATIC coord_t coordinate_dreo = {
         },
         .is_admissible = &solution_lastqt_cw,
         .is_solvable = &is_dreo_solvable,
+        .is_solved = NULL,
+        .allow_niss = true,
         .pruning_distribution = {
                 [0] = 1,
                 [1] = 1,
diff --git a/src/solvers/coord/drfinnoe.h b/src/solvers/coord/drfinnoe.h
index 984b10a..c088ac4 100644
--- a/src/solvers/coord/drfinnoe.h
+++ b/src/solvers/coord/drfinnoe.h
@@ -13,12 +13,7 @@ In the worst case, it is a bug to be fixed, but I find it unlikely.
 
 #define CLASSES_CP_16 2768
 
-STATIC uint64_t coordinate_cp_coord(cube_t);
-STATIC cube_t coordinate_cp_cube(uint64_t);
-STATIC uint64_t coordinate_epud_coord(cube_t);
-STATIC cube_t coordinate_epud_cube(uint64_t);
 STATIC cube_t coordinate_drfinnoe_merge(cube_t, cube_t);
-
 STATIC uint64_t coordinate_drfinnoe_coord(cube_t, const unsigned char *);
 STATIC cube_t coordinate_drfinnoe_cube(uint64_t, const unsigned char *);
 STATIC bool coordinate_drfinnoe_isnasty(uint64_t, const unsigned char *);
@@ -34,7 +29,8 @@ STATIC coord_t coordinate_drfinnoe = {
         .gendata = coordinate_drfinnoe_gendata,
         .max = CLASSES_CP_16 * FACT_8,
         .trans_mask = TM_UDFIX,
-        .moves_mask = MM18_DR,
+        .moves_mask_gendata = MM18_DR,
+        .moves_mask_solve = MM18_DR,
         .axistrans = {
                 [AXIS_UD] = TRANS_UFr,
                 [AXIS_RL] = TRANS_RFr,
@@ -42,6 +38,8 @@ STATIC coord_t coordinate_drfinnoe = {
         },
         .is_admissible = &solution_always_valid,
         .is_solvable = &is_drfinnoe_solvable,
+        .is_solved = NULL,
+        .allow_niss = false,
         .pruning_distribution = {
                 [0] = 1,
                 [1] = 3,
@@ -64,39 +62,15 @@ STATIC coord_t coordinate_drfinnoe = {
         .sym = {
                 .classes = CLASSES_CP_16,
                 .max = FACT_8,
-                .coord = &coordinate_cp_coord,
-                .cube = &coordinate_cp_cube,
+                .coord = &coord_cp,
+                .cube = &invcoord_cp,
                 .max2 = FACT_8,
-                .coord2 = &coordinate_epud_coord,
-                .cube2 = &coordinate_epud_cube,
+                .coord2 = &coord_epud,
+                .cube2 = &invcoord_epud,
                 .merge = &coordinate_drfinnoe_merge,
         },
 };
 
-STATIC uint64_t
-coordinate_cp_coord(cube_t c)
-{
-        return coord_cp(c);
-}
-
-STATIC cube_t
-coordinate_cp_cube(uint64_t i)
-{
-        return invcoord_cp(i);
-}
-
-STATIC uint64_t
-coordinate_epud_coord(cube_t c)
-{
-        return coord_epud(c);
-}
-
-STATIC cube_t
-coordinate_epud_cube(uint64_t i)
-{
-        return invcoord_epud(i);
-}
-
 STATIC cube_t
 coordinate_drfinnoe_merge(cube_t c1, cube_t c2)
 {
diff --git a/src/solvers/coord/drslice.h b/src/solvers/coord/drslice.h
new file mode 100644
index 0000000..4299b30
--- /dev/null
+++ b/src/solvers/coord/drslice.h
@@ -0,0 +1,113 @@
+/*
+The DRSLICE coordinate is almost identical to DRFINNOE, but it allows for
+the centers of the E layer to be off by a rotation. For this reason we reuse
+much of the code of DRFINNOE. We could make the pruning table 4x smaller
+if we reduced the coordinate by rotations. TODO.
+*/
+
+STATIC cube_t coordinate_drslice_merge(cube_t, cube_t);
+STATIC uint64_t coordinate_drslice_coord(cube_t, const unsigned char *);
+STATIC cube_t coordinate_drslice_cube(uint64_t, const unsigned char *);
+STATIC bool coordinate_drslice_isnasty(uint64_t, const unsigned char *);
+STATIC size_t coordinate_drslice_gendata(unsigned char *);
+STATIC bool is_drslice_solvable(cube_t);
+STATIC bool is_drslice_solved(uint64_t, const unsigned char *);
+
+STATIC coord_t coordinate_drslice = {
+        .name = "DRSLICE",
+        .coord = &coordinate_drslice_coord,
+        .cube = &coordinate_drslice_cube,
+        .isnasty = &coordinate_drslice_isnasty,
+        .gendata = coordinate_drslice_gendata,
+        .max = CLASSES_CP_16 * FACT_8,
+        .trans_mask = TM_UDFIX,
+        .moves_mask_gendata = MM18_DR,
+        .moves_mask_solve = MM18_DR_NOD,
+        .axistrans = {
+                [AXIS_UD] = TRANS_UFr,
+                [AXIS_RL] = TRANS_RFr,
+                [AXIS_FB] = TRANS_FDr,
+        },
+        .is_admissible = &solution_always_valid,
+        .is_solvable = &is_drslice_solvable,
+        .is_solved = &is_drslice_solved,
+        .allow_niss = false,
+        .pruning_distribution = {
+                [0] = 3,
+                [1] = 7,
+                [2] = 18,
+                [3] = 111,
+                [4] = 433,
+                [5] = 1618,
+                [6] = 6718,
+                [7] = 29182,
+                [8] = 119873,
+                [9] = 476999,
+                [10] = 1858350,
+                [11] = 6531166,
+                [12] = 18338522,
+                [13] = 32839235,
+                [14] = 34118824,
+                [15] = 17284701
+        },
+        .pruning_max = 15,
+        .sym = {
+                .classes = CLASSES_CP_16,
+                .max = FACT_8,
+                .coord = &coord_cp,
+                .cube = &invcoord_cp,
+                .max2 = FACT_8,
+                .coord2 = &coord_epud,
+                .cube2 = &invcoord_epud,
+                .merge = &coordinate_drslice_merge,
+        },
+};
+
+STATIC cube_t
+coordinate_drslice_merge(cube_t c1, cube_t c2)
+{
+        cube_t merged;
+
+        merged = c1;
+        copy_edges(&merged, c2);
+
+        return merged;
+}
+
+STATIC uint64_t
+coordinate_drslice_coord(cube_t cube, const unsigned char *data)
+{
+        return coord_coord_generic(&coordinate_drslice, cube, data);
+}
+
+STATIC cube_t
+coordinate_drslice_cube(uint64_t i, const unsigned char *data)
+{
+        return coord_cube_generic(&coordinate_drslice, i, data);
+}
+
+STATIC size_t
+coordinate_drslice_gendata(unsigned char *data)
+{
+        return coord_gendata_generic(&coordinate_drslice, data);
+}
+
+STATIC bool
+coordinate_drslice_isnasty(uint64_t i, const unsigned char *data)
+{
+        return coord_isnasty_generic(&coordinate_drslice, i, data);
+}
+
+STATIC bool
+is_drslice_solvable(cube_t cube) {
+        return coord_eo(cube) == 0 &&
+               coord_eo(transform_edges(cube, TRANS_URr)) == 0 &&
+               coord_co(cube) == 0;
+}
+
+STATIC bool
+is_drslice_solved(uint64_t i, const unsigned char *data)
+{
+        /* Pre-computed coordinates of U D' (= U' D up to trans) and U2 D2 */
+        return i == 0 || i == 109779816 || i == 68468527;
+}
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
index b963832..86e09e9 100644
--- a/src/solvers/coord/eo.h
+++ b/src/solvers/coord/eo.h
@@ -12,7 +12,8 @@ STATIC coord_t coordinate_eo = {
         .gendata = coordinate_eo_gendata,
         .max = POW_2_11,
         .trans_mask = TM_SINGLE(TRANS_UFr),
-        .moves_mask = MM18_ALLMOVES,
+        .moves_mask_gendata = MM18_ALLMOVES,
+        .moves_mask_solve = MM18_ALLMOVES,
         .axistrans = {
                 [AXIS_UD] = TRANS_FDr,
                 [AXIS_RL] = TRANS_URr,
@@ -20,6 +21,8 @@ STATIC coord_t coordinate_eo = {
         },
         .is_admissible = &solution_lastqt_cw,
         .is_solvable = &is_eo_even,
+        .is_solved = NULL,
+        .allow_niss = true,
         .pruning_distribution = {
                 [0] = 1,
                 [1] = 2,
@@ -37,7 +40,7 @@ STATIC coord_t coordinate_eo = {
 STATIC uint64_t
 coordinate_eo_coord(cube_t c, const unsigned char *data)
 {
-        return (uint64_t)coord_eo(c);
+        return coord_eo(c);
 }
 
 STATIC cube_t
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
index 678bfd7..75c57e4 100644
--- a/src/solvers/coord/gendata.h
+++ b/src/solvers/coord/gendata.h
@@ -3,6 +3,8 @@ STATIC long long gendata_coord_dispatch(const char *, unsigned long long,
     unsigned char *);
 STATIC tableinfo_t genptable_coord(
     const coord_t [static 1], const unsigned char *, unsigned char *);
+STATIC uint64_t genptable_coord_init_solved(
+    const coord_t [static 1], const unsigned char *, unsigned char *);
 STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t);
 STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1],
     const unsigned char *, uint64_t, uint8_t, unsigned char *);
@@ -118,11 +120,10 @@ genptable_coord(
         memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
         append_coord_name(coord, info.solver);
 
-        nm = popcount_u32(coord->moves_mask);
-        i = coord->coord(SOLVED_CUBE, data);
-        set_coord_pval(coord, table, i, 0);
-        info.distribution[0] = 1;
-        for (d = 1, tot = 1; tot < coord->max && d < 15; d++) {
+        tot = info.distribution[0] =
+            genptable_coord_init_solved(coord, data, table);
+        nm = popcount_u32(coord->moves_mask_gendata);
+        for (d = 1; tot < coord->max && d < 15; d++) {
                 t = 0;
                 if (switch_to_fromnew(tot, coord->max, nm)) {
                         for (i = 0; i < coord->max; i++)
@@ -153,6 +154,27 @@ genptable_coord(
         return info;
 }
 
+STATIC uint64_t
+genptable_coord_init_solved(
+        const coord_t coord[static 1],
+        const unsigned char *coord_data,
+        unsigned char *table
+)
+{
+        uint64_t i, max_solved, ret;
+
+        max_solved = coord->is_solved == NULL ? 1 : coord->max;
+
+        for (i = 0, ret = 0; i < max_solved; i++) {
+                if (coord_is_solved(coord, i, coord_data)) {
+                        set_coord_pval(coord, table, i, 0);
+                        ret++;
+                }
+        }
+
+        return ret;
+}
+
 STATIC bool
 switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm)
 {
@@ -183,7 +205,8 @@ genptable_coord_fillneighbors(
         c = coord->cube(i, data);
         tot = 0;
         for (m = 0; m < NMOVES; m++) {
-                if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask))
+                if (!((UINT32_C(1) << (uint32_t)m) &
+                    coord->moves_mask_gendata))
                         continue;
                 moved = move(c, m);
                 ii = coord->coord(moved, data);
@@ -234,7 +257,8 @@ genptable_coord_fillfromnew(
         for (j = 0, found = false; j < nsim && !found; j++) {
                 c = coord->cube(sim[j], data);
                 for (m = 0; m < NMOVES; m++) {
-                        if (!((UINT32_C(1) << (uint32_t)m) & coord->moves_mask))
+                        if (!((UINT32_C(1) << (uint32_t)m) &
+                            coord->moves_mask_gendata))
                                 continue;
                         ii = coord->coord(move(c, m), data);
                         if (get_coord_pval(coord, table, ii) < d) {
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
index a3d3206..929e0fd 100644
--- a/src/solvers/coord/list.h
+++ b/src/solvers/coord/list.h
@@ -3,5 +3,6 @@ coord_t *all_coordinates[] = {
         &coordinate_dr,
         &coordinate_dreo,
         &coordinate_drfinnoe,
+        &coordinate_drslice,
         NULL
 };
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
index 75ec200..280ca36 100644
--- a/src/solvers/coord/solve.h
+++ b/src/solvers/coord/solve.h
@@ -76,6 +76,7 @@ coord_continue_onnormal(const dfsarg_solve_coord_t arg[static 1])
         if (nn + ni == 0)
                 return f & (NISSY_NISSFLAG_NORMAL | NISSY_NISSFLAG_MIXED);
 
+        /* TODO logic here can probably be simplified */
         if (arg->lastisnormal)
                 return (f & NISSY_NISSFLAG_NORMAL) ||
                     ((f & NISSY_NISSFLAG_MIXED) && (ni > 0 || nn <= th));
@@ -98,6 +99,7 @@ coord_continue_oninverse(const dfsarg_solve_coord_t arg[static 1])
         if (nn + ni == 0)
                 return f & (NISSY_NISSFLAG_INVERSE | NISSY_NISSFLAG_MIXED);
 
+        /* TODO logic here can probably be simplified */
         if (!arg->lastisnormal)
                 return (f & NISSY_NISSFLAG_INVERSE) ||
                     ((f & NISSY_NISSFLAG_MIXED) && (nn > 0 || ni < th));
@@ -118,7 +120,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
         cube_t backup_cube, backup_inverse;
 
         coord = arg->coord->coord(arg->cube, arg->coord_data);
-        if (coord == 0) {
+        if (coord_is_solved(arg->coord, coord, arg->coord_data)) {
                 if (!coord_solution_admissible(arg))
                         return 0;
                 return appendsolution(arg->solution_moves,
@@ -137,7 +139,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
         ret = 0;
         if (coord_continue_onnormal(arg)) {
                 l = arg->solution_moves->nmoves;
-                mm = arg->coord->moves_mask;
+                mm = arg->coord->moves_mask_solve;
                 if (l != 0) {
                         m = arg->solution_moves->moves[l-1];
                         mm &= allowedmask[movebase(m)];
@@ -166,7 +168,7 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
 
         if (coord_continue_oninverse(arg)) {
                 l = arg->solution_moves->npremoves;
-                mm = arg->coord->moves_mask;
+                mm = arg->coord->moves_mask_solve;
                 if (l != 0) {
                         m = arg->solution_moves->premoves[l-1];
                         mm &= allowedmask[movebase(m)];
@@ -260,6 +262,7 @@ solve_coord(
         int8_t d;
         uint8_t t;
         int64_t ndepth;
+        uint64_t i;
         cube_t c;
         const unsigned char *coord_data;
         const unsigned char *ptable;
@@ -314,7 +317,8 @@ solve_coord(
                 .nissflag = nissflag,
         };
 
-        if (coord->coord(c, coord_data) == 0) {
+        i = coord->coord(c, coord_data);
+        if (coord_is_solved(coord, i, coord_data)) {
                 if (minmoves == 0 && !appendsolution(&solution_moves,
                     &solution_settings, &solution_list))
                                 goto solve_coord_error_buffer;
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
index 0c7a3a2..2acf146 100644
--- a/src/solvers/coord/types_macros.h
+++ b/src/solvers/coord/types_macros.h
@@ -21,13 +21,17 @@ typedef struct {
         bool (*isnasty)(uint64_t, const unsigned char *);
         size_t (*gendata)(unsigned char *);
         uint64_t max;
-        uint64_t moves_mask;
+        /* moves_mask_gendata must be invariant under trans_mask */
+        uint64_t moves_mask_gendata;
+        uint64_t moves_mask_solve;
         uint64_t trans_mask;
         uint8_t axistrans[3];
         bool (*is_admissible)(const solution_moves_t[static 1]);
         bool (*is_solvable)(cube_t);
+        bool (*is_solved)(uint64_t, const unsigned char *);
         uint64_t pruning_distribution[INFO_DISTRIBUTION_LEN];
         uint8_t pruning_max;
+        bool allow_niss;
         struct {
                 size_t classes;
                 uint64_t max;