Added cocsep data generation, but it is very slow

9 files changed, 243 insertions, 23 deletions

diff --git a/TODO.txt b/TODO.txt
index b6f5faa..8f636aa 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,8 +1,11 @@
-## (find better name) H48 solver, ideas
-
-TODO implement lookup tables
+TODO optimize cocsep generation (very slow!)
+TODO cocsep data: fix
+TODO cocsep data: add hash checks?
+TODO implement big pruning table for H48 solver
 TODO alternative: ARM NEON part
 
+## H48 optimal solver
+
 First compute co + csep. Use csep as a binary number (2^7 instead of 70,
 loose a factor of 1.8 but still fits in a few megabytes or less). Use
 co + csep as an index in a table whose entries have: 6 bits for ttrep,
diff --git a/cube.c b/cube.c
index fd6b0cf..58c8e7c 100644
--- a/cube.c
+++ b/cube.c
@@ -28,7 +28,33 @@
 #endif
 
 /******************************************************************************
-Section: constants, strings and other stuff
+Section: mathematical constants
+******************************************************************************/
+
+#define _2p11  2048U
+#define _2p12  4096U
+#define _3p7   2187U
+#define _3p8   6561U
+#define _12c4  495U
+#define _8c4   70U
+
+_static int64_t binomial[12][12] = {
+        {1,  0,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
+        {1,  1,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
+        {1,  2,  1,   0,   0,   0,   0,   0,   0,  0,  0, 0},
+        {1,  3,  3,   1,   0,   0,   0,   0,   0,  0,  0, 0},
+        {1,  4,  6,   4,   1,   0,   0,   0,   0,  0,  0, 0},
+        {1,  5, 10,  10,   5,   1,   0,   0,   0,  0,  0, 0},
+        {1,  6, 15,  20,  15,   6,   1,   0,   0,  0,  0, 0},
+        {1,  7, 21,  35,  35,  21,   7,   1,   0,  0,  0, 0},
+        {1,  8, 28,  56,  70,  56,  28,   8,   1,  0,  0, 0},
+        {1,  9, 36,  84, 126, 126,  84,  36,   9,  1,  0, 0},
+        {1, 10, 45, 120, 210, 252, 210, 120,  45, 10,  1, 0},
+        {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
+};
+
+/******************************************************************************
+Section: moves definitions and tables
 ******************************************************************************/
 
 #define U  0U
@@ -378,7 +404,7 @@ _static cube_t solved = {
 #define _trans_cube_BLm_inverse fastcube( \
     38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
 
-static char *cornerstr[] = {
+_static char *cornerstr[] = {
         [_c_ufr] = "UFR",
         [_c_ubl] = "UBL",
         [_c_dfl] = "DFL",
@@ -389,7 +415,7 @@ static char *cornerstr[] = {
         [_c_dbl] = "DBL"
 };
 
-static char *cornerstralt[] = {
+_static char *cornerstralt[] = {
         [_c_ufr] = "URF",
         [_c_ubl] = "ULB",
         [_c_dfl] = "DLF",
@@ -400,7 +426,7 @@ static char *cornerstralt[] = {
         [_c_dbl] = "DLB"
 };
 
-static char *edgestr[] = {
+_static char *edgestr[] = {
         [_e_uf] = "UF",
         [_e_ub] = "UB",
         [_e_db] = "DB",
@@ -415,7 +441,7 @@ static char *edgestr[] = {
         [_e_br] = "BR"
 };
 
-static char *movestr[] = {
+_static char *movestr[] = {
         [U]  = "U",
         [U2] = "U2",
         [U3] = "U'",
@@ -436,7 +462,7 @@ static char *movestr[] = {
         [B3] = "B'",
 };
 
-static char *transstr[] = {
+_static char *transstr[] = {
         [UFr] = "rotation UF",
         [UFm] = "mirrored UF",
         [ULr] = "rotation UL",
@@ -487,19 +513,55 @@ static char *transstr[] = {
         [BLm] = "mirrored BL",
 };
 
-static int64_t binomial[12][12] = {
-        {1,  0,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
-        {1,  1,  0,   0,   0,   0,   0,   0,   0,  0,  0, 0},
-        {1,  2,  1,   0,   0,   0,   0,   0,   0,  0,  0, 0},
-        {1,  3,  3,   1,   0,   0,   0,   0,   0,  0,  0, 0},
-        {1,  4,  6,   4,   1,   0,   0,   0,   0,  0,  0, 0},
-        {1,  5, 10,  10,   5,   1,   0,   0,   0,  0,  0, 0},
-        {1,  6, 15,  20,  15,   6,   1,   0,   0,  0,  0, 0},
-        {1,  7, 21,  35,  35,  21,   7,   1,   0,  0,  0, 0},
-        {1,  8, 28,  56,  70,  56,  28,   8,   1,  0,  0, 0},
-        {1,  9, 36,  84, 126, 126,  84,  36,   9,  1,  0, 0},
-        {1, 10, 45, 120, 210, 252, 210, 120,  45, 10,  1, 0},
-        {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
+static uint8_t inverse_trans_table[48] = {
+        [UFr] = UFr,
+        [UFm] = UFm,
+        [ULr] = URr,
+        [ULm] = ULm,
+        [UBr] = UBr,
+        [UBm] = UBm,
+        [URr] = ULr,
+        [URm] = URm,
+        [DFr] = DFr,
+        [DFm] = DFm,
+        [DLr] = DLr,
+        [DLm] = DRm,
+        [DBr] = DBr,
+        [DBm] = DBm,
+        [DRr] = DRr,
+        [DRm] = DLm,
+        [RUr] = FRr,
+        [RUm] = FLm,
+        [RFr] = LFr,
+        [RFm] = RFm,
+        [RDr] = BLr,
+        [RDm] = BRm,
+        [RBr] = RBr,
+        [RBm] = LBm,
+        [LUr] = FLr,
+        [LUm] = FRm,
+        [LFr] = RFr,
+        [LFm] = LFm,
+        [LDr] = BRr,
+        [LDm] = BLm,
+        [LBr] = LBr,
+        [LBm] = RBm,
+        [FUr] = FUr,
+        [FUm] = FUm,
+        [FRr] = RUr,
+        [FRm] = LUm,
+        [FDr] = BUr,
+        [FDm] = BUm,
+        [FLr] = LUr,
+        [FLm] = RUm,
+        [BUr] = FDr,
+        [BUm] = FDm,
+        [BRr] = LDr,
+        [BRm] = RDm,
+        [BDr] = BDr,
+        [BDm] = BDm,
+        [BLr] = RDr,
+        [BLm] = LDm,
 };
 
 /******************************************************************************
@@ -536,6 +598,7 @@ _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
 
 _static_inline int64_t coord_fast_co(cube_fast_t);
 _static_inline int64_t coord_fast_csep(cube_fast_t);
+_static_inline int64_t coord_fast_cocsep(cube_fast_t);
 _static_inline int64_t coord_fast_eo(cube_fast_t);
 _static_inline int64_t coord_fast_esep(cube_fast_t);
 
@@ -694,6 +757,12 @@ coord_fast_csep(cube_fast_t c)
 }
 
 _static_inline int64_t
+coord_fast_cocsep(cube_fast_t c)
+{
+        return (coord_fast_co(c) << 7) + coord_fast_csep(c);
+}
+
+_static_inline int64_t
 coord_fast_eo(cube_fast_t c)
 {
         cube_fast_t eo, shifted;
@@ -779,6 +848,7 @@ _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
 
 _static_inline int64_t coord_fast_co(cube_fast_t);
 _static_inline int64_t coord_fast_csep(cube_fast_t);
+_static_inline int64_t coord_fast_cocsep(cube_fast_t);
 _static_inline int64_t coord_fast_eo(cube_fast_t);
 _static_inline int64_t coord_fast_esep(cube_fast_t);
 
@@ -934,6 +1004,12 @@ coord_fast_csep(cube_fast_t c)
 }
 
 _static_inline int64_t
+coord_fast_cocsep(cube_fast_t c)
+{
+        return (coord_fast_co(c) << 7) + coord_fast_csep(c);
+}
+
+_static_inline int64_t
 coord_fast_eo(cube_fast_t c)
 {
         int i, p;
@@ -1734,16 +1810,23 @@ transform(cube_fast_t c, uint8_t t)
 }
 
 /******************************************************************************
-Section: moves and move sequences
+Section: moves, move sequences and transformations
 
 This section contains methods to work with moves and arrays of moves. They
 do not rely on the cube structure.
 ******************************************************************************/
 
+_static_inline uint8_t inverse_trans(uint8_t);
 _static_inline uint8_t movebase(uint8_t);
 _static_inline uint8_t moveaxis(uint8_t);
 
 _static_inline uint8_t
+inverse_trans(uint8_t t)
+{
+        return inverse_trans_table[t];
+}
+
+_static_inline uint8_t
 movebase(uint8_t move)
 {
         return move / 3;
@@ -1759,7 +1842,87 @@ moveaxis(uint8_t move)
 Section: auxiliary procedures for H48 optimal solver (temporary)
 ******************************************************************************/
 
+_static size_t gendata_cocsep(void *);
+_static uint16_t dfs_cocsep(cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *);
+
+/*
+Each element of the cocsep table is a uint32_t used as follows:
+  - Lowest 8-bit block: pruning value
+  - Second-lower 8-bit block: "ttrep" (transformation to representative)
+  - Top 16-bit block: symcoord value
+*/
+_static size_t
+gendata_cocsep(void *buf)
+{
+        uint32_t *buf32;
+        uint16_t n, cc;
+        uint8_t i, j;
+        size_t tablesize;
+
+        tablesize = _3p7 << 7U;
+
+        buf32 = (uint32_t *)buf;
+        memset(buf32, 0xFFU, 4*tablesize);
+        memset(buf32 + tablesize, 0, 21*4);
+
+        for (i = 0, n = 0, cc = 0; cc != 0 || i == 0; i++) {
+                DBG_LOG("gendata_cocsep: generating depth %" PRIu8 "\n", i);
+                cc = dfs_cocsep(cubetofast(solvedcube()), 0, i, &n, buf32);
+                buf32[tablesize+i+1] = (uint32_t)cc;
+        }
+        buf32[tablesize] = (uint32_t)n;
+        i--;
 
+        DBG_LOG("cocsep data computed, %" PRIu16 " symmetry classes\n", n);
+        DBG_LOG("Pruning value distribution:\n");
+        for (j = 0; j < i; j++)
+                DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, buf32[tablesize+j+1]);
+
+        return 4*(tablesize + i + 1);
+}
+
+_static uint16_t
+dfs_cocsep(
+        cube_fast_t c,
+        uint8_t depth,
+        uint8_t maxdepth,
+        uint16_t *n,
+        uint32_t *buf32
+)
+{
+        uint8_t m, t, tinv, olddepth;
+        uint16_t cc;
+        uint32_t oldvalue;
+        uint64_t i;
+        cube_fast_t d;
+
+        oldvalue = buf32[coord_fast_cocsep(c)];
+        if (depth == maxdepth) {
+                if ((oldvalue & 0xFFU) != 0xFFU)
+                        return 0;
+
+                for (t = 0, cc = 0; t < 48; t++) {
+                        d = transform(c, t);
+                        i = coord_fast_cocsep(d);
+                        tinv = inverse_trans(t);
+                        if ((buf32[i] & 0xFFU) == 0xFFU)
+                                cc++;
+                        buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
+                }
+                (*n)++;
+
+                return cc;
+        }
+
+        olddepth = (uint8_t)(oldvalue & 0xFFU);
+        if (olddepth != depth)
+                return 0;
+
+        for (m = 0, cc = 0; m < 18; m++)
+                cc += dfs_cocsep(move(c, m), depth+1, maxdepth, n, buf32);
+
+        return cc;
+}
 
 /******************************************************************************
 Section: solvers
diff --git a/test/061_inverse_trans/00_all.in b/test/061_inverse_trans/00_all.in
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/061_inverse_trans/00_all.in
diff --git a/test/061_inverse_trans/00_all.out b/test/061_inverse_trans/00_all.out
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/061_inverse_trans/00_all.out
diff --git a/test/061_inverse_trans/inverse_trans_tests.c b/test/061_inverse_trans/inverse_trans_tests.c
new file mode 100644
index 0000000..77bd40b
--- /dev/null
+++ b/test/061_inverse_trans/inverse_trans_tests.c
@@ -0,0 +1,38 @@
+#include "../test.h"
+
+uint8_t readtrans(char *);
+uint8_t inverse_trans(uint8_t);
+cube_t applymoves(cube_t, char *);
+cube_t applytrans(cube_t, char *);
+extern char *transstr[];
+
+int main(void) {
+        uint8_t t, tinv;
+        cube_t cube;
+
+        for (t = 0; t < 48; t++) {
+                cube = solvedcube();
+                cube = applymoves(cube, "R");
+                cube = applymoves(cube, "U");
+                cube = applymoves(cube, "F");
+
+                cube = applytrans(cube, transstr[t]);
+                tinv = inverse_trans(t);
+                cube = applytrans(cube, transstr[tinv]);
+
+                if (iserror(cube)) {
+                        printf("Error transforming cube\n");
+                } else if (!issolvable(cube)) {
+                        printf("Transformed cube is not solvable\n");
+                } else {
+                        cube = applymoves(cube, "F'");
+                        cube = applymoves(cube, "U'");
+                        cube = applymoves(cube, "R'");
+                        if (!issolved(cube))
+                                printf("%s: Error! Got %" PRIu8 "\n",
+                                    transstr[t], tinv);
+                }
+        }
+
+        return 0;
+}
diff --git a/test/100_gendata_cocsep/00_all.in b/test/100_gendata_cocsep/00_all.in
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/100_gendata_cocsep/00_all.in
diff --git a/test/100_gendata_cocsep/00_all.out b/test/100_gendata_cocsep/00_all.out
new file mode 100644
index 0000000..37b8c1d
--- /dev/null
+++ b/test/100_gendata_cocsep/00_all.out
@@ -0,0 +1 @@
+1119788
diff --git a/test/100_gendata_cocsep/gendata_cocsep_tests.c b/test/100_gendata_cocsep/gendata_cocsep_tests.c
new file mode 100644
index 0000000..19dfa9f
--- /dev/null
+++ b/test/100_gendata_cocsep/gendata_cocsep_tests.c
@@ -0,0 +1,14 @@
+#include "../test.h"
+
+size_t gendata_cocsep(void *);
+
+int main(void) {
+        uint32_t buf[300000];
+        size_t result;
+
+        result = gendata_cocsep(buf);
+
+        printf("%zu\n", result);
+
+        return 0;
+}
diff --git a/test/test.h b/test/test.h
index 7c5400e..3cbfd10 100644
--- a/test/test.h
+++ b/test/test.h
@@ -22,5 +22,6 @@ typedef cube_t cube_fast_t;
 cube_t solvedcube(void);
 bool iserror(cube_t);
 bool issolvable(cube_t);
+bool issolved(cube_t);
 cube_t readcube(char *, char *);
 void writecube(char *, cube_t, char *);