commit a7444e9ab414e1eb73451a806289a3f7c4f02047
parent 1983bacfbb84e2a410ebe663ac1fa7c1b22eb096
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 30 Aug 2024 07:52:04 +0200
Merge branch 'master' of tronto.net:h48
Diffstat:
11 files changed, 347 insertions(+), 304 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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/002_stats_tables_h48/stats_tables_h48.c b/tools/002_stats_tables_h48/stats_tables_h48.c
@@ -1,143 +0,0 @@
-#include <pthread.h>
-#include <time.h>
-#include "../timerun.h"
-#include "../../src/nissy.h"
-
-#define MAXMOVES 20
-#define NTHREADS 32
-#define NCUBES_PER_THREAD 10000
-#define LOG_EVERY (NCUBES_PER_THREAD / 10)
-
-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;
-
- for (i = 0, ret = 0; i < 64; i++)
- ret |= (uint64_t)(rand() % 2) << i;
-
- return ret;
-}
-
-static void *
-run_thread(void *arg)
-{
- char sols[12], cube[22];
- int64_t ep, eo, cp, co;
- int i, j;
-
- thread_arg_t *a = (thread_arg_t *)arg;
-
- for (i = 0; i < a->n; i++) {
- ep = rand64();
- eo = rand64();
- cp = rand64();
- co = rand64();
- nissy_getcube(ep, eo, cp, co, "fix", cube);
- nissy_solve(cube, "h48stats", "", "",
- 0, MAXMOVES, 1, -1, buf, sols);
- for (j = 0; j < 12; j++)
- a->v[j][(int)sols[j]]++;
- if ((i+1) % LOG_EVERY == 0)
- fprintf(stderr, "[thread %d] %d cubes solved...\n",
- a->thread_id, i+1);
- }
-
- return NULL;
-}
-
-void run(void) {
- int64_t i, j, k, tot;
- double avg;
- pthread_t thread[NTHREADS];
- thread_arg_t arg[NTHREADS];
-
- for (i = 0; i < NTHREADS; i++) {
- arg[i] = (thread_arg_t) {
- .thread_id = i,
- .n = NCUBES_PER_THREAD,
- .v = {{0}}
- };
- pthread_create(&thread[i], NULL, run_thread, &arg[i]);
- }
-
- for (i = 0; i < NTHREADS; i++)
- pthread_join(thread[i], NULL);
-
- for (j = 0; j < 12; j++) {
- printf("Data for h=%" PRId64 "\n", j);
- for (k = 0, avg = 0.0; k <= 16; k++) {
- for (i = 0, tot = 0; i < NTHREADS; i++)
- tot += arg[i].v[j][k];
- printf("%" PRId64 "\t%" PRId64 "\n", k, tot);
- avg += tot * k;
- }
- avg /= (double)(NCUBES_PER_THREAD * NTHREADS);
- printf("Average: %.4lf\n", avg);
- 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("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);
- return 1;
- }
-
- timerun(run, "h48 table stats");
-
- free(buf);
- return 0;
-}
diff --git a/tools/003_solve_small/solve_small.c b/tools/003_solve_small/solve_small.c
@@ -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/010_stats_tables_h48/stats_tables_h48.c b/tools/010_stats_tables_h48/stats_tables_h48.c
@@ -0,0 +1,100 @@
+#include <pthread.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;
+
+uint64_t rand64(void) {
+ uint64_t i, ret;
+
+ for (i = 0, ret = 0; i < 64; i++)
+ ret |= (uint64_t)(rand() % 2) << i;
+
+ return ret;
+}
+
+static void *
+run_thread(void *arg)
+{
+ char sols[12], cube[22];
+ int64_t ep, eo, cp, co;
+ int i, j;
+
+ thread_arg_t *a = (thread_arg_t *)arg;
+
+ for (i = 0; i < a->n; i++) {
+ ep = rand64();
+ eo = rand64();
+ cp = rand64();
+ co = rand64();
+ nissy_getcube(ep, eo, cp, co, "fix", cube);
+ nissy_solve(cube, "h48stats", "", "",
+ 0, MAXMOVES, 1, -1, buf, sols);
+ for (j = 0; j < 12; j++)
+ a->v[j][(int)sols[j]]++;
+ if ((i+1) % LOG_EVERY == 0)
+ fprintf(stderr, "[thread %d] %d cubes solved...\n",
+ a->thread_id, i+1);
+ }
+
+ return NULL;
+}
+
+void run(void) {
+ int64_t i, j, k, tot;
+ double avg;
+ pthread_t thread[NTHREADS];
+ thread_arg_t arg[NTHREADS];
+
+ for (i = 0; i < NTHREADS; i++) {
+ arg[i] = (thread_arg_t) {
+ .thread_id = i,
+ .n = NCUBES_PER_THREAD,
+ .v = {{0}}
+ };
+ pthread_create(&thread[i], NULL, run_thread, &arg[i]);
+ }
+
+ for (i = 0; i < NTHREADS; i++)
+ pthread_join(thread[i], NULL);
+
+ for (j = 0; j < 12; j++) {
+ printf("Data for h=%" PRId64 "\n", j);
+ for (k = 0, avg = 0.0; k <= 16; k++) {
+ for (i = 0, tot = 0; i < NTHREADS; i++)
+ tot += arg[i].v[j][k];
+ printf("%" PRId64 "\t%" PRId64 "\n", k, tot);
+ avg += tot * k;
+ }
+ avg /= (double)(NCUBES_PER_THREAD * NTHREADS);
+ printf("Average: %.4lf\n", avg);
+ printf("\n");
+ }
+}
+
+int main(void) {
+ srand(time(NULL));
+ nissy_setlogger(log_stderr);
+
+ if (getdata(solver, options, &buf, filename) != 0)
+ return 1;
+
+ timerun(run, "h48 table stats");
+
+ free(buf);
+ return 0;
+}
diff --git a/tools/020_solve_small/solve_small.c 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
@@ -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
@@ -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;
+}
