Added HTR solver

12 files changed, 164 insertions, 68 deletions

diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
index 5b5f57b..5f2435d 100644
--- a/src/solvers/coord/common.h
+++ b/src/solvers/coord/common.h
@@ -12,6 +12,9 @@ STATIC bool coord_can_switch(const coord_t [static 1], const unsigned char *,
 STATIC bool coord_is_solved(
     const coord_t [static 1], uint64_t, const unsigned char *);
 
+STATIC cube_t coordinate_merge_ce(cube_t, cube_t);
+STATIC cube_t coordinate_merge_ec(cube_t, cube_t);
+
 STATIC uint64_t
 coord_coord_generic(
         const coord_t coord[static 1],
@@ -19,13 +22,11 @@ coord_coord_generic(
         const unsigned char *data
 )
 {
-        const unsigned char *datanoinfo;
         const uint32_t *data32;
         uint32_t d;
         cube_t tr;
 
-        datanoinfo = data + INFOSIZE;
-        data32 = (const uint32_t *)datanoinfo;
+        data32 = (const uint32_t *)(data + INFOSIZE);
         d = data32[coord->sym.coord(c)];
         tr = transform(c, COORD_TTREP(d));
 
@@ -197,3 +198,20 @@ coord_is_solved(
 {
         return coord->is_solved == NULL ? i == 0 : coord->is_solved(i, data);
 }
+
+STATIC cube_t
+coordinate_merge_ce(cube_t corners, cube_t edges)
+{
+        cube_t merged;
+
+        merged = corners;
+        copy_edges(&merged, edges);
+
+        return merged;
+}
+
+STATIC cube_t
+coordinate_merge_ec(cube_t edges, cube_t corners)
+{
+        return coordinate_merge_ce(corners, edges);
+}
diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
index beb1b6a..db40239 100644
--- a/src/solvers/coord/coord.h
+++ b/src/solvers/coord/coord.h
@@ -7,6 +7,7 @@
 #include "drslice.h"
 #include "cpepe.h"
 #include "drfin.h"
+#include "htr.h"
 #include "list.h"
 #include "utils.h"
 #include "gendata.h"
diff --git a/src/solvers/coord/cpepe.h b/src/solvers/coord/cpepe.h
index 9c9bffc..7035400 100644
--- a/src/solvers/coord/cpepe.h
+++ b/src/solvers/coord/cpepe.h
@@ -1,4 +1,3 @@
-STATIC cube_t coordinate_cpepe_merge(const cube_t, const cube_t);
 STATIC uint64_t coordinate_cpepe_coord(const cube_t, const unsigned char *);
 STATIC cube_t coordinate_cpepe_cube(uint64_t, const unsigned char *);
 STATIC bool coordinate_cpepe_isnasty(uint64_t, const unsigned char *);
@@ -15,6 +14,7 @@ STATIC coord_t coordinate_cpepe = {
         .moves_mask_gendata = MM18_DR,
         .moves_mask_solve = MM18_DR,
         .is_admissible = &solution_always_valid,
+        .solution_prune = NULL,
         .is_solvable = &is_drfinnoe_solvable,
         .is_solved = NULL,
         .allow_niss = false,
@@ -44,21 +44,10 @@ STATIC coord_t coordinate_cpepe = {
                 .max2 = FACT_4,
                 .coord2 = &coord_epe,
                 .cube2 = &invcoord_epe,
-                .merge = &coordinate_cpepe_merge,
+                .merge = &coordinate_merge_ce,
         },
 };
 
-STATIC cube_t
-coordinate_cpepe_merge(const cube_t c1, const cube_t c2)
-{
-        cube_t merged;
-
-        merged = c1;
-        copy_edges(&merged, c2);
-
-        return merged;
-}
-
 STATIC uint64_t
 coordinate_cpepe_coord(const cube_t cube, const unsigned char *data)
 {
diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h
index 03473df..8100910 100644
--- a/src/solvers/coord/dr.h
+++ b/src/solvers/coord/dr.h
@@ -3,7 +3,6 @@
 
 STATIC uint64_t coord_dreoesep_nosym(cube_t);
 STATIC cube_t invcoord_dreoesep_nosym(uint64_t);
-STATIC cube_t coordinate_dr_merge(cube_t, cube_t);
 
 STATIC uint64_t coordinate_dr_coord(cube_t, const unsigned char *);
 STATIC cube_t coordinate_dr_cube(uint64_t, const unsigned char *);
@@ -23,6 +22,7 @@ STATIC coord_t coordinate_dr = {
         .moves_mask_gendata = MM18_ALLMOVES,
         .moves_mask_solve = MM18_ALLMOVES,
         .is_admissible = &solution_lastqt_cw,
+        .solution_prune = NULL,
         .is_solvable = &is_eoco_solvable,
         .is_solved = NULL,
         .allow_niss = true,
@@ -50,7 +50,7 @@ STATIC coord_t coordinate_dr = {
                 .max2 = POW_3_7,
                 .coord2 = &coord_co,
                 .cube2 = &invcoord_co,
-                .merge = &coordinate_dr_merge,
+                .merge = &coordinate_merge_ec,
         },
 };
 
@@ -79,17 +79,6 @@ invcoord_dreoesep_nosym(uint64_t coord)
         return cube;
 }
 
-STATIC cube_t
-coordinate_dr_merge(cube_t c1, cube_t c2)
-{
-        cube_t merged;
-
-        merged = c1;
-        copy_corners(&merged, c2);
-
-        return merged;
-}
-
 STATIC uint64_t
 coordinate_dr_coord(cube_t cube, const unsigned char *data)
 {
diff --git a/src/solvers/coord/dreo.h b/src/solvers/coord/dreo.h
index f563129..c5cacac 100644
--- a/src/solvers/coord/dreo.h
+++ b/src/solvers/coord/dreo.h
@@ -2,7 +2,6 @@
 
 STATIC uint64_t coord_dresep_nosym(cube_t);
 STATIC cube_t invcoord_dresep_nosym(uint64_t);
-STATIC cube_t coordinate_dreo_merge(cube_t, cube_t);
 
 STATIC uint64_t coordinate_dreo_coord(cube_t, const unsigned char *);
 STATIC cube_t coordinate_dreo_cube(uint64_t, const unsigned char *);
@@ -22,6 +21,7 @@ STATIC coord_t coordinate_dreo = {
         .moves_mask_gendata = MM18_EO,
         .moves_mask_solve = MM18_EO,
         .is_admissible = &solution_lastqt_cw,
+        .solution_prune = NULL,
         .is_solvable = &is_dreo_solvable,
         .is_solved = NULL,
         .allow_niss = true,
@@ -47,7 +47,7 @@ STATIC coord_t coordinate_dreo = {
                 .max2 = POW_3_7,
                 .coord2 = &coord_co,
                 .cube2 = &invcoord_co,
-                .merge = &coordinate_dreo_merge,
+                .merge = &coordinate_merge_ec,
         },
 };
 
@@ -63,17 +63,6 @@ invcoord_dresep_nosym(uint64_t coord)
         return invcoord_esep(coord * COMB_8_4);
 }
 
-STATIC cube_t
-coordinate_dreo_merge(cube_t c1, cube_t c2)
-{
-        cube_t merged;
-
-        merged = c1;
-        copy_corners(&merged, c2);
-
-        return merged;
-}
-
 STATIC uint64_t
 coordinate_dreo_coord(cube_t cube, const unsigned char *data)
 {
diff --git a/src/solvers/coord/drfinnoe.h b/src/solvers/coord/drfinnoe.h
index 4370779..63f4edf 100644
--- a/src/solvers/coord/drfinnoe.h
+++ b/src/solvers/coord/drfinnoe.h
@@ -13,7 +13,6 @@ In the worst case, it is a bug to be fixed, but I find it unlikely.
 
 #define CLASSES_CP_16 2768
 
-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 *);
@@ -32,6 +31,7 @@ STATIC coord_t coordinate_drfinnoe = {
         .moves_mask_gendata = MM18_DR,
         .moves_mask_solve = MM18_DR,
         .is_admissible = &solution_always_valid,
+        .solution_prune = NULL,
         .is_solvable = &is_drfinnoe_solvable,
         .is_solved = NULL,
         .allow_niss = false,
@@ -62,21 +62,10 @@ STATIC coord_t coordinate_drfinnoe = {
                 .max2 = FACT_8,
                 .coord2 = &coord_epud,
                 .cube2 = &invcoord_epud,
-                .merge = &coordinate_drfinnoe_merge,
+                .merge = &coordinate_merge_ce,
         },
 };
 
-STATIC cube_t
-coordinate_drfinnoe_merge(cube_t c1, cube_t c2)
-{
-        cube_t merged;
-
-        merged = c1;
-        copy_edges(&merged, c2);
-
-        return merged;
-}
-
 STATIC uint64_t
 coordinate_drfinnoe_coord(cube_t cube, const unsigned char *data)
 {
diff --git a/src/solvers/coord/drslice.h b/src/solvers/coord/drslice.h
index c9403f8..42699f8 100644
--- a/src/solvers/coord/drslice.h
+++ b/src/solvers/coord/drslice.h
@@ -5,7 +5,6 @@ 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 *);
@@ -24,6 +23,7 @@ STATIC coord_t coordinate_drslice = {
         .moves_mask_gendata = MM18_DR,
         .moves_mask_solve = MM18_DR_NOD,
         .is_admissible = &solution_always_valid,
+        .solution_prune = NULL,
         .is_solvable = &is_drslice_solvable,
         .is_solved = &is_drslice_solved,
         .allow_niss = false,
@@ -54,21 +54,10 @@ STATIC coord_t coordinate_drslice = {
                 .max2 = FACT_8,
                 .coord2 = &coord_epud,
                 .cube2 = &invcoord_epud,
-                .merge = &coordinate_drslice_merge,
+                .merge = &coordinate_merge_ce,
         },
 };
 
-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)
 {
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
index 5c823a1..42196af 100644
--- a/src/solvers/coord/eo.h
+++ b/src/solvers/coord/eo.h
@@ -14,6 +14,7 @@ STATIC coord_t coordinate_eo = {
         .moves_mask_gendata = MM18_ALLMOVES,
         .moves_mask_solve = MM18_ALLMOVES,
         .is_admissible = &solution_lastqt_cw,
+        .solution_prune = NULL,
         .is_solvable = &is_eo_even,
         .is_solved = NULL,
         .allow_niss = true,
diff --git a/src/solvers/coord/htr.h b/src/solvers/coord/htr.h
new file mode 100644
index 0000000..cfd451b
--- /dev/null
+++ b/src/solvers/coord/htr.h
@@ -0,0 +1,125 @@
+STATIC uint64_t coordinate_htr_coord(cube_t, const unsigned char *);
+STATIC cube_t coordinate_htr_cube(uint64_t, const unsigned char *);
+STATIC bool coordinate_htr_isnasty(uint64_t, const unsigned char *);
+STATIC size_t coordinate_htr_gendata(unsigned char *);
+
+STATIC bool htr_checkmoves(bool *, uint8_t, const uint8_t *);
+STATIC bool htr_solution_prune(const solution_moves_t [static 1]);
+STATIC bool is_cp_htr(uint64_t, const unsigned char *);
+
+STATIC coord_t coordinate_htr = {
+        .name = "HTR",
+        .coord = &coordinate_htr_coord,
+        .cube = &coordinate_htr_cube,
+        .isnasty = &coordinate_htr_isnasty,
+        .gendata = coordinate_htr_gendata,
+        .max = CLASSES_CP_16 * COMB_8_4,
+        .trans_mask = TM_UDFIX,
+        .moves_mask_gendata = MM18_DR,
+        .moves_mask_solve = MM18_DRHTR,
+        .is_admissible = &solution_lastqt_cw,
+        .solution_prune = &htr_solution_prune,
+        .is_solvable = &is_drfinnoe_solvable,
+        .is_solved = &is_cp_htr,
+        .allow_niss = true,
+        .pruning_distribution = {
+                [0] = 22,
+                [1] = 18,
+                [2] = 86,
+                [3] = 268,
+                [4] = 920,
+                [5] = 4042,
+                [6] = 12716,
+                [7] = 24852,
+                [8] = 33116,
+                [9] = 45032,
+                [10] = 47144,
+                [11] = 21676,
+                [12] = 3692,
+                [13] = 176
+        },
+        .pruning_max = 13,
+        .sym = {
+                .classes = CLASSES_CP_16,
+                .max = FACT_8,
+                .coord = &coord_cp,
+                .cube = &invcoord_cp,
+                .max2 = COMB_8_4,
+                .coord2 = &coord_epudsep,
+                .cube2 = &invcoord_epudsep,
+                .merge = &coordinate_merge_ce,
+        },
+};
+
+STATIC uint64_t
+coordinate_htr_coord(cube_t cube, const unsigned char *data)
+{
+        return coord_coord_generic(&coordinate_htr, cube, data);
+}
+
+STATIC cube_t
+coordinate_htr_cube(uint64_t i, const unsigned char *data)
+{
+        return coord_cube_generic(&coordinate_htr, i, data);
+}
+
+STATIC bool
+coordinate_htr_isnasty(uint64_t i, const unsigned char *data)
+{
+        return coord_isnasty_generic(&coordinate_htr, i, data);
+}
+
+STATIC size_t
+coordinate_htr_gendata(unsigned char *data)
+{
+        return coord_gendata_generic(&coordinate_htr, data);
+}
+
+STATIC bool
+htr_checkmoves(bool *f, uint8_t n, const uint8_t *moves)
+{
+        uint8_t i;
+        bool is_d, is_u;
+
+        for (i = 0; i < n; i++) {
+                is_d = moves[i] == MOVE_D || moves[i] == MOVE_D3;
+                is_u = moves[i] == MOVE_U || moves[i] == MOVE_U3;
+                if (is_d && *f)
+                        return true;
+                *f = *f || is_d || is_u;
+
+                if (i < n-1 && moveaxis(moves[i]) == 0 &&
+                    parallel(moves[i], moves[i+1]))
+                        return true;
+        }
+
+        return false;
+}
+
+STATIC bool
+htr_solution_prune(const solution_moves_t s[static 1])
+{
+        bool f;
+
+        f = false;
+
+        return htr_checkmoves(&f, s->nmoves, s->moves) ||
+               htr_checkmoves(&f, s->npremoves, s->premoves);
+}
+
+STATIC bool
+is_cp_htr(uint64_t i, const unsigned char *data)
+{
+        static uint8_t is_cp16_htr_table[DIV_ROUND_UP(CLASSES_CP_16, 8)] = {
+                [0] = 81, [7] = 144, [8] = 16, [25] = 130, [26] = 34,
+                [37] = 64, [38] = 48, [39] = 8, [212] = 20, [226] = 32,
+                [227] = 2, [298] = 160, [300] = 128, [301] = 1
+        };
+
+        uint64_t e, c;
+
+        e = i % COMB_8_4;
+        c = i / COMB_8_4;
+
+        return e == 0 && is_cp16_htr_table[c / 8] & (UINT8_C(1) << (c % 8));
+}
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
index 7bc8041..9b59969 100644
--- a/src/solvers/coord/list.h
+++ b/src/solvers/coord/list.h
@@ -5,6 +5,7 @@ coord_t *all_coordinates[] = {
         &coordinate_drfinnoe,
         &coordinate_drslice,
         &coordinate_cpepe,
+        &coordinate_htr,
         NULL
 };
 
diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h
index 72bc064..54309b1 100644
--- a/src/solvers/coord/solve.h
+++ b/src/solvers/coord/solve.h
@@ -155,6 +155,10 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1])
         int64_t n, ret;
         cube_t backup_cube, backup_inverse;
 
+        if (arg->coord->solution_prune != NULL &&
+            arg->coord->solution_prune(arg->solution_moves))
+                return 0;
+
         coord = arg->coord->coord(arg->cube, arg->coord_data);
         if (coord_is_solved(arg->coord, coord, arg->coord_data)) {
                 if (!coord_solution_admissible(arg))
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
index 73484ba..98f9822 100644
--- a/src/solvers/coord/types_macros.h
+++ b/src/solvers/coord/types_macros.h
@@ -28,6 +28,7 @@ typedef struct {
         uint64_t moves_mask_solve;
         uint64_t trans_mask;
         bool (*is_admissible)(const solution_moves_t[static 1]);
+        bool (*solution_prune)(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];