Fallback tables

6 files changed, 103 insertions, 31 deletions

diff --git a/.gitignore b/.gitignore
index 0a26988..451da56 100644
--- a/.gitignore
+++ b/.gitignore
@@ -11,6 +11,7 @@ run
 shell/lasttest.out
 shell/lasttest.err
 tables/*
+tables-old/*
 test/*/runtest
 test/.DS_Store
 test/run
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 2a4469f..4400011 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -67,17 +67,20 @@ gendata_h48short(gendata_h48short_arg_t *arg)
 STATIC int64_t
 gendata_h48(gendata_h48_arg_t *arg)
 {
-        uint64_t size;
+        uint64_t size, cocsepsize, h48size, fallbacksize;
         void *cocsepdata_offset;
-        size_t cocsepsize;
-        tableinfo_t cocsepinfo;
+        tableinfo_t cocsepinfo, h48info;
+        gendata_h48_arg_t arg_h0k4;
 
         if (arg == NULL) {
                 LOG("Error computing H48 data: arg is NULL.\n");
                 return NISSY_ERROR_UNKNOWN;
         }
 
-        size = 2*INFOSIZE + COCSEP_FULLSIZE + H48_TABLESIZE(arg->h, arg->k);
+        cocsepsize = COCSEP_FULLSIZE;
+        h48size = INFOSIZE + H48_TABLESIZE(arg->h, arg->k);
+        fallbacksize = arg->k == 2 ? INFOSIZE + H48_TABLESIZE(0, 4) : 0;
+        size = cocsepsize + h48size + fallbacksize;
 
         if (arg->buf == NULL)
                 return size; /* Dry-run */
@@ -89,7 +92,7 @@ gendata_h48(gendata_h48_arg_t *arg)
                 return NISSY_ERROR_BUFFER_SIZE;
         }
 
-        cocsepsize = gendata_cocsep(arg->buf, arg->selfsim, arg->crep);
+        gendata_cocsep(arg->buf, arg->selfsim, arg->crep);
 
         cocsepdata_offset = (char *)arg->buf + INFOSIZE;
         arg->cocsepdata = (uint32_t *)cocsepdata_offset;
@@ -121,6 +124,32 @@ gendata_h48(gendata_h48_arg_t *arg)
                 return NISSY_ERROR_UNKNOWN;
         }
 
+        if (arg->k == 2) {
+                arg_h0k4 = *arg;
+                arg_h0k4.h = 0;
+                arg_h0k4.k = 4;
+                arg_h0k4.base = 0;
+                arg_h0k4.maxdepth = 20;
+                arg_h0k4.buf_size = arg->buf_size - h48size;
+                arg_h0k4.buf = (char *)arg->buf + cocsepsize + h48size;
+                arg_h0k4.h48buf = (char *)arg->h48buf + h48size;
+
+                gendata_h48h0k4(&arg_h0k4);
+
+                if (readtableinfo_n(arg->buf_size, arg->buf, 2, &h48info)
+                    != NISSY_OK) {
+                        LOG("gendata_h48: could not read info for h48 table\n");
+                        return NISSY_ERROR_UNKNOWN;
+                }
+
+                h48info.next = h48size;
+                if (writetableinfo(&h48info, arg->buf_size - cocsepsize,
+                    (char *)arg->buf + cocsepsize) != NISSY_OK) {
+                        LOG("gendata_h48: could not write info for h48 table\n");
+                        return NISSY_ERROR_UNKNOWN;
+                }
+        }
+
         return size;
 }
 
@@ -198,7 +227,7 @@ gendata_h48h0k4(gendata_h48_arg_t *arg)
         }
 
         arg->info.maxvalue = d - 1;
-        bufsize = arg->buf_size - COCSEP_FULLSIZE - INFOSIZE;
+        bufsize = arg->buf_size - COCSEP_FULLSIZE;
         writetableinfo(&arg->info, bufsize, arg->h48buf);
 }
 
@@ -377,7 +406,7 @@ gendata_h48k2(gendata_h48_arg_t *arg)
                 arg->info.distribution[t]++;
         }
 
-        bufsize = arg->buf_size - COCSEP_FULLSIZE - INFOSIZE;
+        bufsize = arg->buf_size - COCSEP_FULLSIZE;
         writetableinfo(&arg->info, bufsize, arg->h48buf);
 }
 
@@ -619,7 +648,6 @@ getdistribution_h48(
                 distr[val]++;
         }
 }
-
 STATIC const uint32_t *
 get_cocsepdata_constptr(const void *data)
 {
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 2a5e341..8f55501 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -11,6 +11,7 @@ typedef struct {
         uint8_t base;
         const uint32_t *cocsepdata;
         const uint8_t *h48data;
+        const uint8_t *h48data_fallback;
         uint64_t solutions_size;
         char **nextsol;
         uint8_t nissbranch;
@@ -112,16 +113,31 @@ solve_h48_stop(dfsarg_solveh48_t *arg)
 
         h48bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
 
-        /* If the h48 bound is > 0, we add the base value.        */
-        /* Otherwise, we use the cbound value instead (fallback). */
-        h48bound += h48bound == 0 ? cbound : arg->base;
+        /* If the h48 bound is > 0, we add the base value.    */
+        /* Otherwise, we use the fallback h0k4 value instead. */
+
+        if (arg->k == 2) {
+                if (h48bound == 0) {
+                        h48bound = get_h48_bound(
+                            arg->cube, data, 0, 4, arg->h48data_fallback);
+                } else {
+                        h48bound += arg->base;
+                }
+        }
         if (h48bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
         if (h48bound + arg->nmoves + arg->npremoves == arg->depth)
                 arg->nissbranch = MM_INVERSEBRANCH;
 
         h48bound_inv = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
-        h48bound_inv += h48bound_inv == 0 ? cbound_inv : arg->base;
+        if (arg->k == 2) {
+                if (h48bound_inv == 0) {
+                        h48bound_inv = get_h48_bound(
+                            arg->inverse, data_inv, 0, 4, arg->h48data_fallback);
+                } else {
+                        h48bound_inv += arg->base;
+                }
+        }
         if (h48bound_inv + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
         if (h48bound_inv + arg->nmoves + arg->npremoves == arg->depth)
@@ -194,12 +210,10 @@ solve_h48(
 {
         _Atomic int64_t nsols;
         dfsarg_solveh48_t arg;
-        tableinfo_t info;
+        tableinfo_t info, fbinfo;
 
-        if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) {
-                LOG("solve_h48: error reading table\n");
-                return NISSY_ERROR_DATA;
-        }
+        if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
+                goto solve_h48_error_data;
 
         arg = (dfsarg_solveh48_t) {
                 .cube = cube,
@@ -209,12 +223,23 @@ solve_h48(
                 .h = info.h48h,
                 .k = info.bits,
                 .base = info.base,
-                .cocsepdata = get_cocsepdata_constptr(data),
-                .h48data = get_h48data_constptr(data),
+                .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
+                .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
                 .solutions_size = solutions_size,
                 .nextsol = &solutions
         };
 
+        if (info.bits == 2) {
+                if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
+                        goto solve_h48_error_data;
+                /* We only support h0k4 as fallback table */
+                if (fbinfo.h48h != 0 || fbinfo.bits != 4)
+                        goto solve_h48_error_data;
+                arg.h48data_fallback = arg.h48data + info.next;
+        } else {
+                arg.h48data_fallback = NULL;
+        }
+
         nsols = 0;
         for (arg.depth = minmoves;
              arg.depth <= maxmoves && nsols < maxsolutions;
@@ -229,4 +254,8 @@ solve_h48(
         **arg.nextsol = '\0';
         (*arg.nextsol)++;
         return nsols;
+
+solve_h48_error_data:
+        LOG("solve_h48: error reading table\n");
+        return NISSY_ERROR_DATA;
 }
diff --git a/src/solvers/h48/solve_multithread.h b/src/solvers/h48/solve_multithread.h
index 2e3a1e9..2755372 100644
--- a/src/solvers/h48/solve_multithread.h
+++ b/src/solvers/h48/solve_multithread.h
@@ -261,13 +261,11 @@ solve_h48_multithread(
         _Atomic int64_t nsols = 0;
         int p_depth = 0;
         dfsarg_solveh48_t arg;
-        tableinfo_t info;
+        tableinfo_t info, fbinfo;
         pthread_t threads[THREADS];
 
-        if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) {
-                LOG("solve_h48: error reading table\n");
-                return NISSY_ERROR_DATA;
-        }
+        if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
+                goto solve_h48_multithread_error_data;
 
         arg = (dfsarg_solveh48_t){
                 .cube = cube,
@@ -278,12 +276,23 @@ solve_h48_multithread(
                 .h = info.h48h,
                 .k = info.bits,
                 .base = info.base,
-                .cocsepdata = get_cocsepdata_constptr(data),
-                .h48data = get_h48data_constptr(data),
+                .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
+                .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
                 .solutions_size = solutions_size,
                 .nextsol = &solutions
         };
 
+        if (info.bits == 2) {
+                if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
+                        goto solve_h48_multithread_error_data;
+                /* We only support h0k4 as fallback table */
+                if (fbinfo.h48h != 0 || fbinfo.bits != 4)
+                        goto solve_h48_multithread_error_data;
+                arg.h48data_fallback = arg.h48data + info.next;
+        } else {
+                arg.h48data_fallback = NULL;
+        }
+
         task_queue_t q;
         init_queue(&q);
         if (solve_h48_bfs(&arg, &q, maxmoves))
@@ -301,7 +310,8 @@ solve_h48_multithread(
                  p_depth <= maxmoves && nsols < maxsolutions;
                  p_depth++)
         {
-                LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth);
+                LOG("Found %" PRId64 " solutions, "
+                    "searching at depth %" PRId8 "\n", nsols, p_depth);
                 copy_queue(&q, &nq, p_depth, &nsols);
                 
                 pthread_mutex_lock(&nq.mutex);
@@ -319,4 +329,8 @@ solve_h48_multithread(
         **arg.nextsol = '\0';
         (*arg.nextsol)++;
         return nsols;
+
+solve_h48_multithread_error_data:
+        LOG("solve_h48: error reading table\n");
+        return NISSY_ERROR_DATA;
 }
diff --git a/src/solvers/h48/stats.h b/src/solvers/h48/stats.h
index ca4b72e..cc51bd9 100644
--- a/src/solvers/h48/stats.h
+++ b/src/solvers/h48/stats.h
@@ -80,8 +80,8 @@ solve_h48stats(
 
         arg = (dfsarg_solveh48stats_t) {
                 .cube = cube,
-                .cocsepdata = get_cocsepdata_constptr(data),
-                .h48data = get_h48data_constptr(data),
+                .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
+                .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
                 .s = solutions
         };
 
diff --git a/tools/300_solve_small/solve_small.c b/tools/300_solve_small/solve_small.c
index 374d11a..60d1bd8 100644
--- a/tools/300_solve_small/solve_small.c
+++ b/tools/300_solve_small/solve_small.c
@@ -7,8 +7,8 @@ int64_t size = 0;
 char *buf;
 
 char *scrambles[] = {
-        //"R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */
-        //"RLUD RLUD RLUD", /* 12 optimal */
+        "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */
+        "RLUD RLUD RLUD", /* 12 optimal */
         "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F", /* FMC2019 A1 - 16 optimal */
         // "R' U' F D R F2 D L F D2 F2 L' U R' L2 D' R2 F2 R2 D L2 U2 R' U' F", /* FMC2024 A1 - 19 optimal */
         NULL