Begin work for coordinate solver

12 files changed, 263 insertions, 0 deletions

diff --git a/TODO_COORDINATES b/TODO_COORDINATES
new file mode 100644
index 0000000..7e5628b
--- /dev/null
+++ b/TODO_COORDINATES
@@ -0,0 +1,7 @@
+- solver
+  - include NISS
+- test solver for EO
+- make solve parallelized
+- other coordinates
+  - gendata must handle symmetry
+- make gendata parallelized
diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h
new file mode 100644
index 0000000..b54e5e2
--- /dev/null
+++ b/src/solvers/coord/common.h
@@ -0,0 +1,20 @@
+#include "eo.h"
+
+coord_t *all_coordinates[] = {
+        &coordinate_eo,
+        NULL
+};
+
+STATIC void append_coord_name(const coord_t *, char *);
+
+STATIC void
+append_coord_name(const coord_t *coord, char *str)
+{
+        int i, j;
+
+        i = 0;
+        j = strlen(str);
+        while (coord->name[i]) str[j++] = coord->name[i++];
+
+        str[j] = '\0';
+}
diff --git a/src/solvers/coord/coord_solve.h b/src/solvers/coord/coord_solve.h
new file mode 100644
index 0000000..1d7c036
--- /dev/null
+++ b/src/solvers/coord/coord_solve.h
@@ -0,0 +1,3 @@
+#include "coord_types_macros.h"
+#include "common.h"
+#include "gendata_coord.h"
diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h
new file mode 100644
index 0000000..4f2877c
--- /dev/null
+++ b/src/solvers/coord/coord_types_macros.h
@@ -0,0 +1,13 @@
+#define COORD_INDEX(i) ((i)/2)
+#define COORD_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2))
+#define COORD_MASK(i)  (UINT8_C(0xF) << COORD_SHIFT(i))
+
+typedef struct {
+        char name[255];
+        uint64_t (*coord)(cube_t, const void *);
+        cube_t (*cube)(uint64_t, const void *);
+        size_t (*gendata)(void *);
+        uint64_t max;
+        uint32_t moves_mask;
+        uint64_t trans_mask;
+} coord_t;
diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h
new file mode 100644
index 0000000..d6604d9
--- /dev/null
+++ b/src/solvers/coord/eo.h
@@ -0,0 +1,33 @@
+STATIC uint64_t coordinate_eo_coord(cube_t, const void *);
+STATIC cube_t coordinate_eo_cube(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,
+        .gendata = coordinate_eo_gendata,
+        .max = POW_2_11,
+        .trans_mask = TM_ALLTRANS,
+        .moves_mask = MM_ALLMOVES,
+};
+
+STATIC uint64_t
+coordinate_eo_coord(cube_t c, const void *data)
+{
+        return (uint64_t)coord_eo(c);
+}
+
+STATIC cube_t
+coordinate_eo_cube(uint64_t c, const void *data)
+{
+        cube_t cube = SOLVED_CUBE;
+        set_eo(&cube, (int64_t)c);
+        return cube;
+}
+
+STATIC size_t
+coordinate_eo_gendata(void *data)
+{
+        return 0;
+}
diff --git a/src/solvers/coord/gendata_coord.h b/src/solvers/coord/gendata_coord.h
new file mode 100644
index 0000000..b3932cd
--- /dev/null
+++ b/src/solvers/coord/gendata_coord.h
@@ -0,0 +1,134 @@
+STATIC size_t gendata_coordinate(const coord_t *, void *);
+STATIC size_t gendata_coordinate_name(const char *, void *);
+STATIC tableinfo_t genptable_coordinate(const coord_t *, const void *, uint8_t *);
+STATIC uint8_t get_coord_pval(const coord_t *, const uint8_t *, uint64_t);
+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;
+
+        for (i = 0; all_coordinates[i] != NULL; i++)
+                if (strcmp(all_coordinates[i]->name, name) == 0)
+                        return gendata_coordinate(all_coordinates[i], buf);
+
+        LOG("Cannot generate data for coordinate '%s': not found\n", name);
+        return 0;
+}
+
+STATIC size_t
+gendata_coordinate(const coord_t *coord, void *buf)
+{
+        uint64_t coord_dsize, tablesize, ninfo;
+        void *pruningbuf, *coord_data;
+        uint8_t *table;
+        tableinfo_t coord_data_info, pruning_info;
+
+        coord_data = buf == NULL ? NULL : ((uint8_t *)buf) + INFOSIZE;
+        coord_dsize = coord->gendata(coord_data);
+        ninfo = coord_dsize == 0 ? 1 : 2;
+        tablesize = DIV_ROUND_UP(coord->max, 2);
+
+        if (buf == NULL)
+                goto gendata_coordinate_return_size;
+
+        if (ninfo == 2) {
+                coord_data_info = (tableinfo_t) {
+                        .solver = "coord helper table for ",
+                        .type = TABLETYPE_SPECIAL,
+                        .infosize = INFOSIZE,
+                        .fullsize = INFOSIZE + coord_dsize,
+                        .hash = 0, /* TODO */
+                        .next = INFOSIZE + coord_dsize,
+
+                        /* Unknown / non-applicable values */
+                        .entries = 0,
+                        .classes = 0,
+                        .bits = 0,
+                        .base = 0,
+                        .maxvalue = 0,
+                };
+
+                append_coord_name(coord, coord_data_info.solver);
+
+                writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf);
+
+                pruningbuf = ((uint8_t *)buf) + INFOSIZE + coord_dsize;
+        } else {
+                pruningbuf = buf;
+        }
+
+        table = ((uint8_t *)pruningbuf) + INFOSIZE;
+        pruning_info = genptable_coordinate(coord, coord_data, table);
+        writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf);
+
+gendata_coordinate_return_size:
+        return ninfo * INFOSIZE + coord_dsize + tablesize;
+}
+
+STATIC tableinfo_t
+genptable_coordinate(const coord_t *coord, const void *data, uint8_t *table)
+{
+        uint64_t tablesize, i, j, d, tot;
+        tableinfo_t info;
+        uint8_t m;
+        cube_t c, cc;
+
+        tablesize = DIV_ROUND_UP(coord->max, 2);
+
+        memset(table, 0xFF, tablesize);
+
+        info = (tableinfo_t) {
+                .solver = "coordinate solver for ",
+                .type = TABLETYPE_PRUNING,
+                .infosize = INFOSIZE,
+                .fullsize = INFOSIZE + tablesize,
+                .hash = 0, /* TODO */
+                .entries = coord->max,
+                .classes = 0,
+                .bits = 4,
+                .base = 0,
+                .maxvalue = 0,
+                .next = 0
+        };
+
+        memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+        append_coord_name(coord, info.solver);
+
+        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++) {
+                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]++;
+                                        }
+                                }
+                        }
+                }
+        }
+        info.maxvalue = d-1;
+
+        return info;
+}
+
+STATIC uint8_t
+get_coord_pval(const coord_t *coord, const uint8_t *table, uint64_t i)
+{
+        return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i);
+}
+
+STATIC void
+set_coord_pval(const coord_t *coord, uint8_t *table, uint64_t i, uint8_t val)
+{
+        table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i)))
+            | (val << COORD_SHIFT(i));
+}
diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h
index 7b7f355..154f8cc 100644
--- a/src/solvers/solvers.h
+++ b/src/solvers/solvers.h
@@ -1,2 +1,3 @@
 #include "tables.h"
 #include "h48/h48.h"
+#include "coord/coord_solve.h"
diff --git a/src/utils/constants.h b/src/utils/constants.h
index 1e4a630..3d8bf5e 100644
--- a/src/utils/constants.h
+++ b/src/utils/constants.h
@@ -99,6 +99,8 @@ STATIC int64_t binomial[12][12] = {
 #define MM_ALLMOVES    UINT32_C(0x3FFFF)
 #define MM_NOHALFTURNS UINT32_C(0x2DB6D)
 
+#define TM_ALLTRANS    UINT64_C(0xFFFFFFFFFFFF)
+
 #define CORNER_UFR      UINT8_C(0)
 #define CORNER_UBL      UINT8_C(1)
 #define CORNER_DFL      UINT8_C(2)
diff --git a/test/120_gendata_eo/00_all.in b/test/120_gendata_eo/00_all.in
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/120_gendata_eo/00_all.in
diff --git a/test/120_gendata_eo/00_all.out b/test/120_gendata_eo/00_all.out
new file mode 100644
index 0000000..42e8c66
--- /dev/null
+++ b/test/120_gendata_eo/00_all.out
@@ -0,0 +1,12 @@
+1536
+0: 1
+1: 2
+2: 25
+3: 202
+4: 620
+5: 900
+6: 285
+7: 13
+8: 0
+9: 0
+10: 0
diff --git a/test/120_gendata_eo/gendata_eo_tests.c b/test/120_gendata_eo/gendata_eo_tests.c
new file mode 100644
index 0000000..3a6ac07
--- /dev/null
+++ b/test/120_gendata_eo/gendata_eo_tests.c
@@ -0,0 +1,37 @@
+/*
+Pruning table values (from nissy):
+0: 1
+1: 2
+2: 25
+3: 202
+4: 620
+5: 900
+6: 285
+7: 13
+*/
+
+#include "../test.h"
+
+#define ISIZE 512
+#define FULLSIZE (ISIZE + 1024)
+
+char buf[FULLSIZE];
+
+size_t gendata_coordinate_name(const char *, void *);
+bool readtableinfo(uint64_t, const char *, tableinfo_t *);
+
+void run(void) {
+        uint32_t i;
+        size_t result;
+        tableinfo_t info;
+
+        result = gendata_coordinate_name("EO", buf);
+        if (readtableinfo(FULLSIZE, buf, &info) != NISSY_OK) {
+                printf("Error reading info from table\n");
+                return;
+        }
+
+        printf("%zu\n", result);
+        for (i = 0; i <= 10; i++)
+                printf("%" PRIu32 ": %" PRIu64 "\n", i, info.distribution[i]);
+}
diff --git a/test/test.h b/test/test.h
index fe362c7..e144527 100644
--- a/test/test.h
+++ b/test/test.h
@@ -14,6 +14,7 @@
 #include "../src/solvers/h48/coordinate_macros.h"
 #include "../src/solvers/h48/map_types_macros.h"
 #include "../src/solvers/h48/gendata_types_macros.h"
+#include "../src/solvers/coord/coord_types_macros.h"
 
 #define STRLENMAX 10000