DR coordinate solver

7 files changed, 238 insertions, 14 deletions

diff --git a/src/solvers/coord/coord.h b/src/solvers/coord/coord.h
index f42739d..11d41bc 100644
--- a/src/solvers/coord/coord.h
+++ b/src/solvers/coord/coord.h
@@ -1,6 +1,7 @@
 #include "types_macros.h"
 #include "common.h"
 #include "eo.h"
+#include "dr.h"
 #include "list.h"
 #include "utils.h"
 #include "gendata.h"
diff --git a/src/solvers/coord/dr.h b/src/solvers/coord/dr.h
new file mode 100644
index 0000000..5f3a99b
--- /dev/null
+++ b/src/solvers/coord/dr.h
@@ -0,0 +1,178 @@
+#define DREOESEP_CLASSES   UINT64_C(64430)
+#define DREOESEP_MAX       (POW_2_11 * COMB_12_4)
+
+#define DR_CLASS_TABLESIZE (sizeof(uint32_t) * (size_t)DREOESEP_MAX)
+#define DR_REP_TABLESIZE   (sizeof(uint32_t) * (size_t)DREOESEP_CLASSES)
+#define DR_COORD_DATASIZE  (INFOSIZE + DR_CLASS_TABLESIZE + DR_REP_TABLESIZE)
+
+#define DR_CLASS_SHIFT     UINT32_C(16)
+#define DR_CLASS_MASK      (UINT32_C(0xFFFF) << DR_CLASS_SHIFT)
+#define DR_CLASS(d)        (((d) & DR_CLASS_MASK) >> DR_CLASS_SHIFT)
+
+#define DR_TTREP_SHIFT     UINT32_C(0)
+#define DR_TTREP_MASK      (UINT32_C(0xFF) << DR_TTREP_SHIFT)
+#define DR_TTREP(d)        (((d) & DR_TTREP_MASK) >> DR_TTREP_SHIFT)
+
+#define DR_ISNASTY_SHIFT   UINT32_C(8)
+#define DR_ISNASTY_MASK    (UINT32_C(0xFF) << DR_ISNASTY_SHIFT)
+#define DR_ISNASTY(d)      (((d) & DR_ISNASTY_MASK) >> DR_ISNASTY_SHIFT)
+
+STATIC uint64_t coord_dreoesep_nosym(cube_t);
+STATIC cube_t invcoord_dreoesep_nosym(uint64_t);
+
+STATIC uint64_t coordinate_dr_coord(cube_t, const void *);
+STATIC cube_t coordinate_dr_cube(uint64_t, const void *);
+STATIC bool coordinate_dr_isnasty(uint64_t, const void *);
+STATIC uint64_t coordinate_dr_gendata(void *);
+
+STATIC coord_t coordinate_dr = {
+        .name = "DR",
+        .coord = &coordinate_dr_coord,
+        .cube = &coordinate_dr_cube,
+        .isnasty = &coordinate_dr_isnasty,
+        .gendata = coordinate_dr_gendata,
+        .max = DREOESEP_CLASSES * POW_3_7,
+        .trans_mask = TM_UDFIX,
+        .moves_mask = MM_ALLMOVES,
+        .axistrans = {
+                [AXIS_UD] = TRANS_UFr,
+                [AXIS_RL] = TRANS_RFr,
+                [AXIS_FB] = TRANS_FDr,
+        },
+        .is_admissible = &solution_lastqt_cw,
+};
+
+STATIC uint64_t
+coord_dreoesep_nosym(cube_t cube)
+{
+        uint64_t eo, esep;
+
+        esep = coord_esep(cube) / COMB_8_4;
+        eo = coord_eo(cube);
+
+        return esep * POW_2_11 + eo;
+}
+
+STATIC cube_t
+invcoord_dreoesep_nosym(uint64_t coord)
+{
+        uint64_t eo, esep;
+        cube_t cube;
+
+        eo = coord % POW_2_11;
+        esep = (coord / POW_2_11) * COMB_8_4; 
+        cube = invcoord_esep(esep);
+        set_eo(&cube, eo);
+
+        return cube;
+}
+
+STATIC uint64_t
+coordinate_dr_coord(cube_t cube, const void *data)
+{
+        const char *datanoinfo;
+        const uint32_t *data32;
+        uint32_t d;
+        cube_t transformed;
+
+        datanoinfo = (const char *)data + INFOSIZE;
+        data32 = (const uint32_t *)datanoinfo;
+        d = data32[coord_dreoesep_nosym(cube)];
+        transformed = transform(cube, DR_TTREP(d));
+        
+        return DR_CLASS(d) * POW_3_7 + coord_co(transformed);
+}
+
+STATIC cube_t
+coordinate_dr_cube(uint64_t coord, const void *data)
+{
+        const char *datanoinfo;
+        const uint32_t *rep32;
+        cube_t cube;
+
+        datanoinfo = (const char *)data + INFOSIZE;
+        rep32 = (const uint32_t *)(datanoinfo + DR_CLASS_TABLESIZE);
+        cube = invcoord_dreoesep_nosym(rep32[coord / POW_3_7]);
+        copy_corners(&cube, invcoord_co(coord % POW_3_7));
+
+        return cube;
+}
+
+STATIC bool
+coordinate_dr_isnasty(uint64_t coord, const void *data)
+{
+        const char *datanoinfo;
+        const uint32_t *classttrep;
+
+        datanoinfo = (const char *)data + INFOSIZE;
+        classttrep = (const uint32_t *)datanoinfo;
+
+        return DR_ISNASTY(classttrep[coord]);
+}
+
+STATIC size_t
+coordinate_dr_gendata(void *data)
+{
+        uint64_t i, ii, j, n, t, nasty;
+        char *datanoinfo;
+        uint32_t *classttrep, *rep;
+        cube_t c;
+        tableinfo_t info;
+
+        if (data == NULL)
+                goto coordinate_dr_gendata_returnsize;
+
+        datanoinfo = (char *)data + INFOSIZE;
+        classttrep = (uint32_t *)datanoinfo;
+        rep = classttrep + (DR_CLASS_TABLESIZE / sizeof(uint32_t));
+        memset(data, 0xFF, DR_COORD_DATASIZE);
+
+        info = (tableinfo_t) {
+                .solver = "coord data for DR",
+                .type = TABLETYPE_SPECIAL,
+                .infosize = INFOSIZE,
+                .fullsize = DR_COORD_DATASIZE,
+                .hash = 0,
+                .entries = DREOESEP_CLASSES + DREOESEP_MAX,
+                .classes = DREOESEP_CLASSES,
+                .bits = 32,
+                .base = 0,
+                .maxvalue = 0,
+                .next = 0
+        };
+
+        for (i = 0, n = 0; i < COMB_12_4 * POW_2_11; i++) {
+                if (classttrep[i] != 0xFFFFFFFF)
+                        continue;
+
+                c = invcoord_dreoesep_nosym(i);
+                ii = coord_dreoesep_nosym(c);
+                for (t = 0, nasty = 0; t < NTRANS && !nasty; t++) {
+                        if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
+                                continue;
+
+                        nasty = ii == coord_dreoesep_nosym(transform(c, t));
+                }
+
+                for (t = 0; t < NTRANS; t++) {
+                        if (!((UINT64_C(1) << t) & coordinate_dr.trans_mask))
+                                continue;
+
+                        j = coord_dreoesep_nosym(transform(c, t));
+                        classttrep[j] =
+                            (n << DR_CLASS_SHIFT) |
+                            (nasty << DR_ISNASTY_SHIFT) |
+                            (inverse_trans(t) << DR_TTREP_SHIFT);
+                }
+                rep[n++] = i;
+        }
+
+        writetableinfo(&info, DR_COORD_DATASIZE, data);
+
+        DBG_ASSERT(n == DREOESEP_CLASSES, 0,
+            "dr coordinate data: computed %" PRIu64 " classes, "
+            "expected %" PRIu64 "\n", n, DREOESEP_CLASSES);
+
+coordinate_dr_gendata_returnsize:
+        return DR_COORD_DATASIZE;
+}
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
index ef9b27a..3fabf9f 100644
--- a/src/solvers/coord/eo.h
+++ b/src/solvers/coord/eo.h
@@ -1,14 +1,16 @@
 STATIC uint64_t coordinate_eo_coord(cube_t, const void *);
 STATIC cube_t coordinate_eo_cube(uint64_t, const void *);
+STATIC bool coordinate_eo_isnasty(uint64_t, const void *);
 STATIC uint64_t coordinate_eo_gendata(void *);
 
 STATIC coord_t coordinate_eo = {
         .name = "EO",
         .coord = &coordinate_eo_coord,
         .cube = &coordinate_eo_cube,
+        .isnasty = &coordinate_eo_isnasty,
         .gendata = coordinate_eo_gendata,
         .max = POW_2_11,
-        .trans_mask = TM_ALLTRANS,
+        .trans_mask = TM_SINGLE(TRANS_UFr),
         .moves_mask = MM_ALLMOVES,
         .axistrans = {
                 [AXIS_UD] = TRANS_FDr,
@@ -32,6 +34,12 @@ coordinate_eo_cube(uint64_t c, const void *data)
         return cube;
 }
 
+STATIC bool
+coordinate_eo_isnasty(uint64_t c, const void *data)
+{
+        return false;
+}
+
 STATIC size_t
 coordinate_eo_gendata(void *data)
 {
diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h
index ca058b0..5e40575 100644
--- a/src/solvers/coord/gendata.h
+++ b/src/solvers/coord/gendata.h
@@ -2,6 +2,8 @@ STATIC size_t gendata_coord(const coord_t [static 1], void *);
 STATIC int64_t gendata_coord_dispatch(const char *, void *);
 STATIC tableinfo_t genptable_coord(
     const coord_t [static 1], const void *, uint8_t *);
+STATIC uint64_t genptable_coord_fillneighbors(
+    const coord_t [static 1], const void *, uint64_t, uint8_t, uint8_t *);
 STATIC void getdistribution_coord(
     const uint8_t *, const char *, uint64_t [static INFO_DISTRIBUTION_LEN]);
 STATIC uint8_t get_coord_pval(
@@ -81,10 +83,8 @@ genptable_coord(
         uint8_t *table
 )
 {
-        uint64_t tablesize, i, j, d, tot;
+        uint64_t tablesize, i, d, tot, t;
         tableinfo_t info;
-        uint8_t m;
-        cube_t c, cc;
 
         tablesize = DIV_ROUND_UP(coord->max, 2);
 
@@ -113,24 +113,52 @@ genptable_coord(
         for (d = 1, tot = 1; tot < coord->max; d++) {
                 for (i = 0; i < coord->max; i++) {
                         if (get_coord_pval(coord, table, i) == d-1) {
-                                c = coord->cube(i, data);
-                                for (m = 0; m < 18; m++) {
-                                        cc = move(c, m);
-                                        j = coord->coord(cc, data);
-                                        if (get_coord_pval(coord, table, j) > d) {
-                                                set_coord_pval(coord, table, j, d);
-                                                tot++;
-                                                info.distribution[d]++;
-                                        }
-                                }
+                                t = genptable_coord_fillneighbors(
+                                    coord, data, i, d, table);
+                                tot += t;
+                                info.distribution[d] += t;
                         }
                 }
+                LOG("Depth %" PRIu64 ": %" PRIu64 " of %" PRIu64 "\n",
+                    d, tot, coord->max);
         }
         info.maxvalue = d-1;
 
         return info;
 }
 
+STATIC uint64_t
+genptable_coord_fillneighbors(
+        const coord_t coord[static 1],
+        const void *data,
+        uint64_t i, 
+        uint8_t d,
+        uint8_t *table
+)
+{
+        uint8_t m;
+        uint64_t j, t, tot;
+        cube_t c, moved;
+
+        c = coord->cube(i, data);
+        tot = 0;
+        for (m = 0; m < NMOVES; m++) {
+                moved = move(c, m);
+                for (t = 0; t < NTRANS; t++) {
+                        if (!((UINT64_C(1) << t) & coord->trans_mask))
+                                continue;
+
+                        j = coord->coord(transform(moved, t), data);
+                        if (get_coord_pval(coord, table, j) > d) {
+                                set_coord_pval(coord, table, j, d);
+                                tot++;
+                        }
+                }
+        }
+
+        return tot;
+}
+
 STATIC void
 getdistribution_coord(
         const uint8_t *table,
diff --git a/src/solvers/coord/list.h b/src/solvers/coord/list.h
index 32c94a4..7d43d45 100644
--- a/src/solvers/coord/list.h
+++ b/src/solvers/coord/list.h
@@ -1,4 +1,5 @@
 coord_t *all_coordinates[] = {
         &coordinate_eo,
+        &coordinate_dr,
         NULL
 };
diff --git a/src/solvers/coord/types_macros.h b/src/solvers/coord/types_macros.h
index 9eaeca0..8741e27 100644
--- a/src/solvers/coord/types_macros.h
+++ b/src/solvers/coord/types_macros.h
@@ -6,6 +6,7 @@ typedef struct {
         const char name[255];
         uint64_t (*coord)(cube_t, const void *);
         cube_t (*cube)(uint64_t, const void *);
+        bool (*isnasty)(uint64_t, const void *);
         size_t (*gendata)(void *);
         uint64_t max;
         uint32_t moves_mask;
diff --git a/src/utils/constants.h b/src/utils/constants.h
index ef8c7e0..a6c6b7a 100644
--- a/src/utils/constants.h
+++ b/src/utils/constants.h
@@ -106,6 +106,13 @@ STATIC int64_t binomial[12][12] = {
 
 #define TM_ALLTRANS    UINT64_C(0xFFFFFFFFFFFF)
 #define TM_SINGLE(t)   (UINT64_C(1) << (uint64_t)(t))
+#define TM_UDFIX       (\
+    TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_URr) | \
+    TM_SINGLE(TRANS_ULr) | TM_SINGLE(TRANS_UFm) | TM_SINGLE(TRANS_UBm) | \
+    TM_SINGLE(TRANS_URm) | TM_SINGLE(TRANS_ULm) | TM_SINGLE(TRANS_DFr) | \
+    TM_SINGLE(TRANS_DBr) | TM_SINGLE(TRANS_DRr) | TM_SINGLE(TRANS_DLr) | \
+    TM_SINGLE(TRANS_DFm) | TM_SINGLE(TRANS_DBm) | TM_SINGLE(TRANS_DRm) | \
+    TM_SINGLE(TRANS_DLm))
 
 #define CORNER_UFR      UINT8_C(0)
 #define CORNER_UBL      UINT8_C(1)