Merge branch 'sebastianotronto:master' into master

12 files changed, 205 insertions, 37 deletions

diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h
index 13ce68b..0f96da9 100644
--- a/src/solvers/h48/gendata_cocsep.h
+++ b/src/solvers/h48/gendata_cocsep.h
@@ -18,13 +18,13 @@ typedef struct {
         uint8_t *visited;
         uint64_t *selfsim;
         cube_t *rep;
-} dfsarg_cocsep_t;
+} cocsep_dfs_arg_t;
 
 _static_inline bool get_visited(const uint8_t *, int64_t);
 _static_inline void set_visited(uint8_t *, int64_t);
 
 _static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
-_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
+_static uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *);
 
 _static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
 
@@ -45,7 +45,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep)
         uint32_t *buf32, *info, cc;
         uint16_t n;
         uint8_t i, j, visited[COCSEP_VISITEDSIZE];
-        dfsarg_cocsep_t arg;
+        cocsep_dfs_arg_t arg;
 
         if (buf == NULL)
                 goto gendata_cocsep_return_size;
@@ -56,7 +56,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep)
         if (selfsim != NULL)
                 memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
 
-        arg = (dfsarg_cocsep_t) {
+        arg = (cocsep_dfs_arg_t) {
                 .cube = solved,
                 .n = &n,
                 .buf32 = buf32,
@@ -92,14 +92,14 @@ gendata_cocsep_return_size:
 }
 
 _static uint32_t
-gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
+gendata_cocsep_dfs(cocsep_dfs_arg_t *arg)
 {
         uint8_t m;
         uint32_t cc, class, ttrep, depth, olddepth, tinv;
         uint64_t t;
         int64_t i, j;
         cube_t d;
-        dfsarg_cocsep_t nextarg;
+        cocsep_dfs_arg_t nextarg;
 
         i = coord_cocsep(arg->cube);
         olddepth = (uint8_t)(arg->buf32[i] & 0xFF);
@@ -135,7 +135,7 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
                 return cc;
         }
 
-        memcpy(&nextarg, arg, sizeof(dfsarg_cocsep_t));
+        memcpy(&nextarg, arg, sizeof(cocsep_dfs_arg_t));
         nextarg.depth++;
         for (m = 0, cc = 0; m < 18; m++) {
                 nextarg.cube = move(arg->cube, m);
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 2b1347f..2d222c9 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -1,6 +1,6 @@
-#define H48_COORDMAX_NOEO    (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4)
-#define H48_COORDMAX(h)      (H48_COORDMAX_NOEO << (size_t)(h))
-#define H48_TABLESIZE(h, k)  (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k)))
+#define H48_COORDMAX_NOEO    ((int64_t)(COCSEP_CLASSES * _12c4 * _8c4))
+#define H48_COORDMAX(h)      ((int64_t)(H48_COORDMAX_NOEO << (int64_t)(h)))
+#define H48_TABLESIZE(h, k)  ((size_t)H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k)))
 
 #define H48_COEFF(k)         (UINT32_C(32) / (uint32_t)(k))
 #define H48_INDEX(i, k)      ((uint32_t)(i) / H48_COEFF(k))
@@ -55,7 +55,23 @@ typedef struct {
         uint64_t *selfsim;
         int64_t done;
         cube_t *crep;
-} bfsarg_esep_t;
+} h48h0k4_bfs_arg_t;
+
+typedef struct {
+        cube_t cube;
+        uint8_t moves[4];
+        uint8_t h;
+        uint8_t k;
+        uint8_t base;
+        uint8_t depth;
+        uint8_t shortdepth;
+        uint8_t maxdepth;
+        uint32_t *cocsepdata;
+        uint32_t *h48data;
+        uint64_t *selfsim;
+        cube_t *crep;
+        h48map_t *shortcubes;
+} h48k2_dfs_arg_t;
 
 _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t);
 _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t);
@@ -63,10 +79,11 @@ _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t);
 _static uint64_t gen_h48short(gendata_h48short_arg_t *);
 _static size_t gendata_h48(gendata_h48_arg_t *);
 _static size_t gendata_h48h0k4(gendata_h48_arg_t *);
-_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
-_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
-_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
+_static int64_t gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *);
+_static int64_t gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *);
+_static int64_t gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *);
 _static size_t gendata_h48k2(gendata_h48_arg_t *);
+_static void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg);
 
 _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *);
 
@@ -150,31 +167,17 @@ _static size_t
 gendata_h48h0k4(gendata_h48_arg_t *arg)
 {
         uint32_t j;
-        bfsarg_esep_t bfsarg;
+        h48h0k4_bfs_arg_t bfsarg;
         int64_t sc, cc, esep_max;
-/*
-        uint64_t selfsim[COCSEP_CLASSES];
-        cube_t crep[COCSEP_CLASSES];
-        size_t cocsepsize, infosize;
-*/
 
         if (arg->buf == NULL)
                 goto gendata_h48h0k4_return_size;
-/*
-        cocsepsize = gendata_cocsep(buf, selfsim, crep);
-        infosize = 88;
-
-        cocsepdata = (uint32_t *)buf;
-        buf32 = cocsepdata + cocsepsize / 4;
-        info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t));
-        memset(buf32, 0xFF, H48_TABLESIZE(0, 4));
-*/
 
         esep_max = (int64_t)H48_COORDMAX(0);
         sc = coord_h48(solved, arg->cocsepdata, 0);
         set_esep_pval(arg->h48data, sc, 4, 0);
         arg->info[1] = 1;
-        bfsarg = (bfsarg_esep_t) {
+        bfsarg = (h48h0k4_bfs_arg_t) {
                 .cocsepdata = arg->cocsepdata,
                 .buf32 = arg->h48data,
                 .selfsim = arg->selfsim,
@@ -205,7 +208,7 @@ gendata_h48h0k4_return_size:
 }
 
 _static int64_t
-gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
+gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *arg)
 {
         const uint8_t breakpoint = 10; /* Hand-picked optimal */
 
@@ -216,7 +219,7 @@ gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
 }
 
 _static int64_t
-gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
+gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *arg)
 {
         uint8_t c, m, x;
         uint32_t cc;
@@ -246,7 +249,7 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
 }
 
 _static int64_t
-gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg)
+gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *arg)
 {
         uint8_t c, m, x;
         uint32_t cc;
@@ -298,9 +301,13 @@ gendata_h48k2(gendata_h48_arg_t *arg)
                 [11] = 10
         };
 
-        uint64_t nshort;
+        uint8_t t;
+        int64_t j;
+        uint64_t nshort, i;
         h48map_t shortcubes;
+        kvpair_t kv;
         gendata_h48short_arg_t shortarg;
+        h48k2_dfs_arg_t dfsarg;
 
         DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n");
 
@@ -317,17 +324,84 @@ gendata_h48k2(gendata_h48_arg_t *arg)
                 .map = &shortcubes
         };
         nshort = gen_h48short(&shortarg);
-        LOG("Found %" PRIu64 "\n", nshort);
+        LOG("Cubes in <= %" PRIu8 " moves: %" PRIu64 "\n", shortdepth, nshort);
+
+        dfsarg = (h48k2_dfs_arg_t){
+                .h = arg->h,
+                .k = arg->k,
+                .base = base[arg->h],
+                .depth = shortdepth,
+                .shortdepth = shortdepth,
+                .maxdepth = arg->maxdepth,
+                .cocsepdata = arg->cocsepdata,
+                .h48data = arg->h48data,
+                .selfsim = arg->selfsim,
+                .crep = arg->crep,
+                .shortcubes = &shortcubes
+        };
 
-        /* TODO: loop over map, set all found to 0, do 2 moves each */
-        LOG("The rest is not implemented yet\n");
+        i = 0;
+        for (kv = h48map_nextkvpair(&shortcubes, &i);
+             i != shortcubes.capacity;
+             kv = h48map_nextkvpair(&shortcubes, &i)
+        ) {
+                /* TODO maybe over all sim? */
+                dfsarg.cube = invcoord_h48(kv.key, arg->crep, 11);
+                gendata_h48k2_dfs(&dfsarg);
+        }
 
         h48map_destroy(&shortcubes);
 
+        /* TODO: move info update to dfs? */
+        memset(arg->info, 0, 5 * sizeof(arg->info[0]));
+        arg->info[0] = base[arg->k];
+        for (j = 0; j < H48_COORDMAX(arg->h); j++) {
+                t = get_esep_pval(arg->h48data, j, 2);
+                arg->info[1 + t]++;
+        }
+
 gendata_h48k2_return_size:
         return H48_TABLESIZE(arg->h, 2);
 }
 
+_static void
+gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
+{
+        uint8_t nmoves;
+        uint64_t val;
+        int64_t coord, fullcoord;
+        h48k2_dfs_arg_t nextarg;
+        uint8_t m;
+
+        fullcoord = coord_h48(arg->cube, arg->cocsepdata, 11);
+        coord = fullcoord >> (int64_t)(11 - arg->h);
+
+        val = h48map_value(arg->shortcubes, fullcoord);
+
+        if (arg->depth >= arg->base && arg->depth <= arg->base + 2)
+                set_esep_pval(
+                    arg->h48data, coord, arg->k, arg->depth - arg->base);
+
+        if ((val < arg->shortdepth) ||
+            (arg->depth > arg->shortdepth && val != MAP_UNSET) ||
+            (arg->depth >= arg->maxdepth || arg->depth >= arg->base + 2))
+                return;
+
+        /* TODO: avoid copy, change arg and undo changes after recursion */
+        nextarg = *arg;
+        nextarg.depth = arg->depth + 1;
+        nmoves = nextarg.depth - arg->shortdepth;
+        for (m = 0; m < 18; m++) {
+                nextarg.moves[nmoves - 1] = m;
+                if (!allowednextmove(nextarg.moves, nmoves)) {
+                        m += 2;
+                        continue;
+                }
+                nextarg.cube = move(arg->cube, m);
+                gendata_h48k2_dfs(&nextarg);
+        }
+}
+
 _static_inline uint8_t
 get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k)
 {
diff --git a/test/113_gen_h48short/00_depth_1.in b/test/112_gen_h48short/00_depth_1.in
index c86f15b..c86f15b 100644
--- a/test/113_gen_h48short/00_depth_1.in
+++ b/test/112_gen_h48short/00_depth_1.in
diff --git a/test/113_gen_h48short/00_depth_1.out b/test/112_gen_h48short/00_depth_1.out
index b0dba31..b0dba31 100644
--- a/test/113_gen_h48short/00_depth_1.out
+++ b/test/112_gen_h48short/00_depth_1.out
diff --git a/test/113_gen_h48short/01_depth_3.in b/test/112_gen_h48short/01_depth_3.in
index 920e70a..920e70a 100644
--- a/test/113_gen_h48short/01_depth_3.in
+++ b/test/112_gen_h48short/01_depth_3.in
diff --git a/test/113_gen_h48short/01_depth_3.out b/test/112_gen_h48short/01_depth_3.out
index dbce376..dbce376 100644
--- a/test/113_gen_h48short/01_depth_3.out
+++ b/test/112_gen_h48short/01_depth_3.out
diff --git a/test/113_gen_h48short/gen_h48short.c b/test/112_gen_h48short/gen_h48short.c
index 335821a..335821a 100644
--- a/test/113_gen_h48short/gen_h48short.c
+++ b/test/112_gen_h48short/gen_h48short.c
diff --git a/test/112_gendata_h48/00_h_0.in b/test/120_gendata_h48h0k4/00_h_0.in
index cb6e5ed..cb6e5ed 100644
--- a/test/112_gendata_h48/00_h_0.in
+++ b/test/120_gendata_h48h0k4/00_h_0.in
diff --git a/test/112_gendata_h48/00_h_0.out b/test/120_gendata_h48h0k4/00_h_0.out
index 04e8bf6..04e8bf6 100644
--- a/test/112_gendata_h48/00_h_0.out
+++ b/test/120_gendata_h48h0k4/00_h_0.out
diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c
index d6c6cb2..d6c6cb2 100644
--- a/test/112_gendata_h48/gendata_h48_tests.c
+++ b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c
diff --git a/tools/001_gendata_h48/gendata_h48.c b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c
index a73f818..a73f818 100644
--- a/tools/001_gendata_h48/gendata_h48.c
+++ b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c
diff --git a/tools/003_solve_small/solve_small.c b/tools/003_solve_small/solve_small.c
new file mode 100644
index 0000000..406e255
--- /dev/null
+++ b/tools/003_solve_small/solve_small.c
@@ -0,0 +1,94 @@
+#include <pthread.h>
+#include <time.h>
+#include "../timerun.h"
+#include "../../src/nissy.h"
+
+#define OPTIONS "0;4;20"
+
+const char *filename = "tables/h48h0k4";
+char *buf;
+char *scrambles[] = {
+        "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */
+        "RLUD RLUD RLUD", /* 12 optimal */
+        NULL
+};
+
+void run(void) {
+        int i;
+        int64_t n;
+        char sol[100], cube[22];
+
+        printf("Solved the following scrambles:\n\n");
+        for (i = 0; scrambles[i] != NULL; i++) {
+                printf("%s\n", scrambles[i]);
+                fprintf(stderr, "Solving scramble %s\n", scrambles[i]);
+                if (nissy_frommoves(scrambles[i], cube) == -1) {
+                        fprintf(stderr, "Invalid scramble, "
+                            "continuing with next scramble\n");
+                        continue;
+                }
+                n = nissy_solve(
+                    cube, "h48", OPTIONS, "", 0, 20, 1, -1, buf, sol);
+                if (n == 0)
+                        fprintf(stderr, "No solution found, "
+                            "continuing with next scramble\n");
+        }
+        printf("\n");
+}
+
+int getdata(int64_t size) {
+        int64_t s;
+        FILE *f;
+
+        buf = malloc(size);
+
+        if ((f = fopen(filename, "rb")) == NULL) {
+                fprintf(stderr, "Table file not found, generating them."
+                    " This can take a while.\n");
+                s = nissy_gendata("h48", OPTIONS, buf);
+                if (s != size) {
+                        fprintf(stderr, "Error generating table");
+                        if (s != -1)
+                                fprintf(stderr, " (got %" PRId64 " bytes)", s);
+                        fprintf(stderr, "\n");
+                        return 1;
+                }
+                if ((f = fopen(filename, "wb")) == NULL) {
+                        fprintf(stderr, "Could not write tables to file %s"
+                            ", will be regenerated next time.\n", filename);
+                } else {
+                        fwrite(buf, size, 1, f);
+                        fclose(f);
+                }
+        } else {
+                fprintf(stderr, "Reading tables from file %s\n", filename);
+                fread(buf, size, 1, f);
+                fclose(f);
+        }
+
+        return 0;
+}
+
+int main(void) {
+        int64_t size;
+
+        srand(time(NULL));
+
+        nissy_setlogger(log_stderr);
+        size = nissy_datasize("h48", OPTIONS);
+        if (size == -1) {
+                printf("h48 stats: error in datasize\n");
+                return 1;
+        }
+
+        if (getdata(size) != 0) {
+                printf("Error getting table, stopping\n");
+                free(buf);
+                return 1;
+        }
+
+        timerun(run, "small solver benchmark");
+
+        free(buf);
+        return 0;
+}