Merge branch 'master' of tronto.net:h48

10 files changed, 255 insertions, 212 deletions

diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 2d222c9..fbb8b35 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -1,6 +1,7 @@
 #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_DIV(k)           ((size_t)8 / (size_t)(k))
+#define H48_TABLESIZE(h, k)  _div_round_up((size_t)H48_COORDMAX((h)), H48_DIV(k))
 
 #define H48_COEFF(k)         (UINT32_C(32) / (uint32_t)(k))
 #define H48_INDEX(i, k)      ((uint32_t)(i) / H48_COEFF(k))
@@ -140,7 +141,7 @@ gendata_h48(gendata_h48_arg_t *arg)
         cocsepsize = gendata_cocsep(
             (void *)arg->cocsepdata, arg->selfsim, arg->crep);
         arg->h48data = arg->cocsepdata + (cocsepsize / sizeof(uint32_t));
-        arg->info = arg->h48data +
+        arg->info = arg->h48data + 1 +
             (H48_TABLESIZE(arg->h, arg->k) / sizeof(uint32_t));
 
         if (arg->buf != NULL)
@@ -341,18 +342,27 @@ gendata_h48k2(gendata_h48_arg_t *arg)
         };
 
         i = 0;
+int jj = 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);
+
+#if 1
                 gendata_h48k2_dfs(&dfsarg);
+#else
+                /* It looks like this is not necessary, we get the same result */
+                _foreach_h48sim(
+                        dfsarg.cube, arg->cocsepdata, arg->selfsim, arg->h,
+                        gendata_h48k2_dfs(&dfsarg);
+                )
+#endif
+if ((++jj) % 1000 == 0) LOG("Done %d distance 8 cubes\n", jj);
         }
 
         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++) {
@@ -367,7 +377,7 @@ gendata_h48k2_return_size:
 _static void
 gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
 {
-        uint8_t nmoves;
+        uint8_t nmoves, oldval, newval;
         uint64_t val;
         int64_t coord, fullcoord;
         h48k2_dfs_arg_t nextarg;
@@ -378,12 +388,13 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t *arg)
 
         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 (arg->depth >= arg->base && arg->depth <= arg->base + 2) {
+                oldval = get_esep_pval(arg->h48data, coord, arg->k);
+                newval = _min(oldval, arg->depth - arg->base);
+                set_esep_pval(arg->h48data, coord, arg->k, newval);
+        }
 
-        if ((val < arg->shortdepth) ||
-            (arg->depth > arg->shortdepth && val != MAP_UNSET) ||
+        if ((arg->depth > arg->shortdepth && val != MAP_UNSET_VAL) ||
             (arg->depth >= arg->maxdepth || arg->depth >= arg->base + 2))
                 return;
 
diff --git a/src/solvers/h48/map.h b/src/solvers/h48/map.h
index 82e5a2c..0e9f926 100644
--- a/src/solvers/h48/map.h
+++ b/src/solvers/h48/map.h
@@ -1,6 +1,7 @@
 #define MAP_UNSET             UINT64_C(0xFFFFFFFFFFFFFFFF)
 #define MAP_KEYMASK           UINT64_C(0xFFFFFFFFFF)
 #define MAP_KEYSHIFT          UINT64_C(40)
+#define MAP_UNSET_VAL         (MAP_UNSET >> MAP_KEYSHIFT)
 
 typedef struct {
         uint64_t n;
@@ -84,8 +85,8 @@ h48map_nextkvpair(h48map_t *map, uint64_t *p)
         kvpair_t kv;
         uint64_t pair;
 
-        kv.key = MAP_UNSET;
-        kv.val = MAP_UNSET;
+        kv.key = MAP_KEYMASK;
+        kv.val = MAP_UNSET_VAL;
 
         DBG_ASSERT(*p < map->capacity, kv,
             "Error looping over map: given index %" PRIu64 " is out of "
diff --git a/src/utils/math.h b/src/utils/math.h
index 87402e6..a361808 100644
--- a/src/utils/math.h
+++ b/src/utils/math.h
@@ -1,6 +1,7 @@
 #define _swap(x, y) do { x ^= y; y ^= x; x ^= y; } while (0)
 #define _min(x, y) ((x) < (y) ? (x) : (y))
 #define _max(x, y) ((x) > (y) ? (x) : (y))
+#define _div_round_up(n, d) (((n) + (d) - 1) / (d))
 
 _static int64_t factorial(int64_t);
 _static bool isperm(uint8_t *, int64_t);
diff --git a/tools/001_gendata_h48h0k4/gendata_h48h0k4.c b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c
index a73f818..a2c57ca 100644
--- a/tools/001_gendata_h48h0k4/gendata_h48h0k4.c
+++ b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c
@@ -1,5 +1,4 @@
-#include "../timerun.h"
-#include "../../src/nissy.h"
+#include "../tool.h"
 
 #define MAXDEPTH 20
 #define HVALUE 0
@@ -38,12 +37,12 @@ void run(void) {
                 printf("Error generating table\n");
         } else {
                 printf("Succesfully generated %" PRId64 " bytes. Table:\n", s);
-                h48info = (uint32_t *)buf + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4;
+                h48info = (uint32_t *)buf + 1 + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4;
                 for (i = 0; i < MAXDEPTH+1 && h48info[i+1]; i++) {
                         x = h48info[i+1];
                         printf("%d:\t%" PRIu32, i, x);
                         if (x != expected[i])
-                                printf(" <--- Error! Expected: %" PRIu32 "\n",
+                                printf(" <--- Error! Expected: %" PRIu32,
                                     expected[i]);
                         printf("\n");
                 }
diff --git a/tools/002_gendata_h48h0k2/gendata_h48h0k2.c b/tools/002_gendata_h48h0k2/gendata_h48h0k2.c
new file mode 100644
index 0000000..2754f80
--- /dev/null
+++ b/tools/002_gendata_h48h0k2/gendata_h48h0k2.c
@@ -0,0 +1,62 @@
+#include "../tool.h"
+
+#define MAXDEPTH 20
+#define HVALUE 0
+#define OPTIONS "0;2;20"
+#define LONGOPTIONS "h = 0, k = 2, max depth = 20"
+
+#define COCSEPSIZE 1119792
+#define ETABLESIZE(h) (((3393 * 495 * 70) >> 2) << (size_t)(h))
+
+uint32_t expected[21] = {
+        /* Base value is 8 */
+        [0] = 5473562,
+        [1] = 34776317,
+        [2] = 68566704,
+        [3] = 8750867,
+};
+
+char *buf;
+
+void run(void) {
+        uint32_t *h48info, x;
+        int i;
+        int64_t s;
+
+        s = nissy_gendata("h48", OPTIONS, buf);
+
+        if (s == -1) {
+                printf("Error generating table\n");
+        } else {
+                printf("Succesfully generated %" PRId64 " bytes. Table:\n", s);
+                h48info = (uint32_t *)buf + 1 + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4;
+                for (i = 0; i < 4; i++) {
+                        x = h48info[i+1];
+                        printf("%d:\t%" PRIu32, i, x);
+                        if (x != expected[i])
+                                printf(" <--- Error! Expected: %" PRIu32,
+                                    expected[i]);
+                        printf("\n");
+                }
+        }
+}
+
+int main(void) {
+        int64_t size;
+
+        nissy_setlogger(log_stderr);
+
+        size = nissy_datasize("h48", OPTIONS);
+        if (size == -1) {
+                printf("gendata_h48 benchmark: error in datasize\n");
+                return 1;
+        }
+
+        buf = malloc(size);
+
+        timerun(run, "benchmark gendata_h48 " LONGOPTIONS);
+
+        free(buf);
+
+        return 0;
+}
diff --git a/tools/003_solve_small/solve_small.c b/tools/003_solve_small/solve_small.c
deleted file mode 100644
index 406e255..0000000
--- a/tools/003_solve_small/solve_small.c
+++ /dev/null
@@ -1,94 +0,0 @@
-#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;
-}
diff --git a/tools/002_stats_tables_h48/stats_tables_h48.c b/tools/010_stats_tables_h48/stats_tables_h48.c
index 2e48497..8b65862 100644
--- a/tools/002_stats_tables_h48/stats_tables_h48.c
+++ b/tools/010_stats_tables_h48/stats_tables_h48.c
@@ -1,22 +1,23 @@
 #include <pthread.h>
-#include <time.h>
-#include "../timerun.h"
-#include "../../src/nissy.h"
+
+#include "../tool.h"
 
 #define MAXMOVES 20
 #define NTHREADS 32
 #define NCUBES_PER_THREAD 10000
 #define LOG_EVERY (NCUBES_PER_THREAD / 10)
 
+const char *solver = "h48stats";
+const char *options = "";
+const char *filename = "tables/h48h0k4";
+char *buf;
+
 typedef struct {
         int n;
         int thread_id;
         int64_t v[12][100];
 } thread_arg_t;
 
-const char *filename = "tables/h48h0k4";
-char *buf;
-
 uint64_t rand64(void) {
         uint64_t i, ret;
 
@@ -85,56 +86,12 @@ void run(void) {
         }
 }
 
-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("h48stats", "", 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("h48stats", "");
-        if (size == -1) {
-                printf("h48 stats: error in datasize\n");
-                return 1;
-        }
 
-        if (getdata(size) != 0) {
-                printf("Error getting table, stopping\n");
-                free(buf);
+        if (getdata(solver, options, &buf, filename) != 0)
                 return 1;
-        }
 
         timerun(run, "h48 table stats");
 
diff --git a/tools/020_solve_small/solve_small.c b/tools/020_solve_small/solve_small.c
new file mode 100644
index 0000000..dee2b55
--- /dev/null
+++ b/tools/020_solve_small/solve_small.c
@@ -0,0 +1,51 @@
+#include <pthread.h>
+
+#include "../tool.h"
+
+const char *solver = "h48";
+const char *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 main(void) {
+
+        srand(time(NULL));
+        nissy_setlogger(log_stderr);
+
+        if (getdata(solver, options, &buf, filename) != 0)
+                return 1;
+
+        timerun(run, "small solver benchmark");
+
+        free(buf);
+        return 0;
+}
diff --git a/tools/timerun.h b/tools/timerun.h
deleted file mode 100644
index 58a8e7a..0000000
--- a/tools/timerun.h
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <stdarg.h>
-#include <stdbool.h>
-#include <inttypes.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-void
-log_stderr(const char *str, ...)
-{
-        va_list args;
-
-        va_start(args, str);
-        vfprintf(stderr, str, args);
-        va_end(args);
-}
-
-
-double
-timerun(void (*run)(void), char *name)
-{
-        struct timespec start, end;
-        double tdiff, tdsec, tdnano;
-
-        printf("\n");
-        fflush(stdout);
-
-        if (run == NULL) {
-                printf("> %s: nothing to run!\n", name);
-                fflush(stdout);
-                return -1.0;
-        }
-
-        printf("Running tool: %s\n", name);
-        printf("==========\n");
-        fflush(stdout);
-
-        clock_gettime(CLOCK_MONOTONIC, &start);
-        run();
-        clock_gettime(CLOCK_MONOTONIC, &end);
-
-        tdsec = end.tv_sec - start.tv_sec;
-        tdnano = end.tv_nsec - start.tv_nsec;
-        tdiff = tdsec + 1e-9 * tdnano;
-
-        printf("==========\n");
-        printf("\nTotal time: %.4fs\n", tdiff);
-        fflush(stdout);
-
-        return tdiff;
-}
diff --git a/tools/tool.h b/tools/tool.h
new file mode 100644
index 0000000..d75342d
--- /dev/null
+++ b/tools/tool.h
@@ -0,0 +1,106 @@
+#include <time.h>
+#include <stdarg.h>
+#include <stdbool.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+#include "../src/nissy.h"
+
+static void
+log_stderr(const char *str, ...)
+{
+        va_list args;
+
+        va_start(args, str);
+        vfprintf(stderr, str, args);
+        va_end(args);
+}
+
+static double
+timerun(void (*run)(void), char *name)
+{
+        struct timespec start, end;
+        double tdiff, tdsec, tdnano;
+
+        printf("\n");
+        fflush(stdout);
+
+        if (run == NULL) {
+                printf("> %s: nothing to run!\n", name);
+                fflush(stdout);
+                return -1.0;
+        }
+
+        printf("Running tool: %s\n", name);
+        printf("==========\n");
+        fflush(stdout);
+
+        clock_gettime(CLOCK_MONOTONIC, &start);
+        run();
+        clock_gettime(CLOCK_MONOTONIC, &end);
+
+        tdsec = end.tv_sec - start.tv_sec;
+        tdnano = end.tv_nsec - start.tv_nsec;
+        tdiff = tdsec + 1e-9 * tdnano;
+
+        printf("==========\n");
+        printf("\nTotal time: %.4fs\n", tdiff);
+        fflush(stdout);
+
+        return tdiff;
+}
+
+static int
+getdata(
+        const char *solver,
+        const char *options,
+        char **buf,
+        const char *filename
+) {
+        int64_t s, size, sizeread;
+        FILE *f;
+
+        if ((size = nissy_datasize(solver, options)) == -1) {
+                printf("Error in datasize\n");
+                goto getdata_error_nofree;
+        }
+
+        *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(solver, options, *buf);
+                if (s != size) {
+                        fprintf(stderr, "Error generating table");
+                        if (s != -1)
+                                fprintf(stderr, " (got %" PRId64 " bytes)", s);
+                        fprintf(stderr, "\n");
+                        goto getdata_error;
+                }
+                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);
+                sizeread = fread(*buf, size, 1, f);
+                fclose(f);
+                if (sizeread != 1) {
+                        fprintf(stderr, "Error reading table, stopping\n");
+                        goto getdata_error;
+                }
+        }
+
+        return 0;
+
+getdata_error:
+        free(*buf);
+getdata_error_nofree:
+        return 1;
+}