commit cee9856b2cb151f705acf6d27454ec08ef2b9a4e parent 0b32395de2500ad87e15fbb0ff4a852e313037e9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri, 27 Sep 2024 08:22:55 +0200 Merge branch 'master' of tronto.net:h48 Diffstat:
28 files changed, 279 insertions(+), 295 deletions(-)
diff --git a/.gitignore b/.gitignore @@ -10,6 +10,7 @@ test/*/runtest test/run test/run.DSYM run.DSYM +run.core test/last.* tools/results .vscode diff --git a/README.md b/README.md @@ -61,7 +61,7 @@ The results of the last test case run is saved in test/last.out (standard output, the results compared with the .out files) and test/last.err (standard error). -Tests are always run in "debug mode": this means that optimizations are +Tests are always run in debug mode: this means that optimizations are disabled and some extra logging is enabled. See the test folder and test/test.sh for details. @@ -70,7 +70,7 @@ See the test folder and test/test.sh for details. In the tools folder there are some small programs that test various functionality of the H48 library. They work similarly to test, but they -are not run in debug mode. +are not run in debug mode by default. To run a tool you must select it with the environment variable `TOOL`. For example the command: @@ -79,14 +79,26 @@ For example the command: TOOL=stats make tool ``` -Will run the stats_tables_h48 tool. Like for tests, the value of the -`TOOL` variable can be any regular expression matching the name of the -tool. Unlike tests, one and only one tool will be selected for each run. +Will run the stats_tables_h48 tool. + +To pass some arguments to a tool, use the `TOOLARGS` variable: + +``` +TOOL=gendata TOOLARGS="h48 0;2;20" make tool +``` + +Like for tests, the value of the `TOOL` variable can be any regular +expression matching the name of the tool. Unlike tests, one and +only one tool will be selected for each run. The content of the +`TOOLARGS` variable is used directly as command line arguments for +the chosen tool. Each tool run is automatically timed, so these tools can be used as benchmark. The output as well as the time of the run are saved to a file in the tools/results folder. +To build and run a tool in debug mode, use `make debugtool`. + ## Running commands manually This project also includes a rudimentary shell that can be used to run diff --git a/src/nissy.c b/src/nissy.c @@ -11,8 +11,11 @@ #include "nissy.h" -STATIC int parse_h48_options(const char *, uint8_t *, uint8_t *, uint8_t *); +int parse_h48_options(const char *, uint8_t *, uint8_t *, uint8_t *); STATIC int64_t write_result(cube_t, char [static 22]); +STATIC bool distribution_equal( + const uint64_t [static 21], const uint64_t [static 21], uint8_t); +STATIC bool checkdata(const void *, const tableinfo_t *); /* TODO: add option to get DR, maybe C-only, E-only, eo... */ #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } @@ -24,7 +27,7 @@ struct { GETCUBE_OPTIONS(NULL, NULL) }; -STATIC int +int parse_h48_options(const char *buf, uint8_t *h, uint8_t *k, uint8_t *maxdepth) { bool h_valid, k_valid, maxdepth_valid; @@ -62,6 +65,52 @@ parse_h48_options_error: return -1; } +STATIC bool +checkdata(const void *buf, const tableinfo_t *info) +{ + uint64_t distr[21]; + + if (!strncmp(info->solver, "cocsep", 6)) { + getdistribution_cocsep( + (uint32_t *)((char *)buf + INFOSIZE), distr); + } else if (!strncmp(info->solver, "h48", 3)) { + getdistribution_h48((uint8_t *)buf + INFOSIZE, distr, + info->h48h, info->bits); + } else { + LOG("checkdata: unknown solver %s\n", info->solver); + return false; + } + + return distribution_equal(info->distribution, distr, info->maxvalue); +} + +STATIC bool +distribution_equal( + const uint64_t expected[static 21], + const uint64_t actual[static 21], + uint8_t maxvalue +) +{ + int wrong; + uint8_t i; + + for (i = 0, wrong = 0; i <= MAX(maxvalue, 20); i++) { + if (expected[i] != actual[i]) { + wrong++; + LOG("Value %" PRIu8 ": expected %" PRIu64 ", found %" + PRIu64 "\n", i, expected[i], actual[i]); + } + } + + if (wrong > 0) { + LOG("checkdata: %d wrong values\n", wrong); + } else { + LOG("checkdata: table is consistent with info\n"); + } + + return wrong > 0; +} + STATIC int64_t write_result(cube_t cube, char result[static 22]) { @@ -275,6 +324,23 @@ nissy_gendata( } int64_t +nissy_checkdata( + const char *solver, + const char *options, + const void *data +) +{ + char *buf; + tableinfo_t info; + + for (buf = (char *)data; readtableinfo(buf, &info); buf += info.next) + if (!checkdata(buf, &info)) + return 1; + + return 0; +} + +int64_t nissy_solve( const char cube[static 22], const char *solver, diff --git a/src/nissy.h b/src/nissy.h @@ -93,6 +93,12 @@ int64_t nissy_derivedata( void *generated_data ); +int64_t nissy_checkdata( + const char *solver, + const char *options, + const void *data +); + /* Print information on a data table via the provided callback writer */ int64_t nissy_datainfo( const void *table, diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h @@ -25,6 +25,7 @@ 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(cocsep_dfs_arg_t *); +STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]); STATIC_INLINE int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); @@ -157,6 +158,17 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg) return cc; } +STATIC void +getdistribution_cocsep(const uint32_t *table, uint64_t distr[static 21]) +{ + size_t i; + + memset(distr, 0, 21 * sizeof(uint64_t)); + + for (i = 0; i < COCSEP_TABLESIZE; i++) + distr[CBOUND(table[i])]++; +} + STATIC_INLINE bool get_visited(const uint8_t *a, int64_t i) { diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h @@ -104,13 +104,16 @@ STATIC size_t gendata_h48k2_realcoord(gendata_h48_arg_t *); STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg); STATIC void * gendata_h48k2_runthread(void *); STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t *); +STATIC void getdistribution_h48( + const uint8_t *, uint64_t [static 21], uint8_t, uint8_t); STATIC uint32_t *get_cocsepdata_ptr(const void *); STATIC uint8_t *get_h48data_ptr(const void *); STATIC_INLINE uint8_t get_h48_pval(const uint8_t *, int64_t, uint8_t); STATIC_INLINE void set_h48_pval(uint8_t *, int64_t, uint8_t, uint8_t); -STATIC_INLINE uint8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint8_t *); +STATIC_INLINE uint8_t get_h48_bound( + cube_t, uint32_t, uint8_t, uint8_t, uint8_t *); size_t gendata_h48_derive(uint8_t, const void *, void *); @@ -665,6 +668,25 @@ makeinfo_h48k2(gendata_h48_arg_t *arg) return info; } +STATIC void +getdistribution_h48( + const uint8_t *table, + uint64_t distr[static 21], + uint8_t h, + uint8_t k +) { + uint8_t val; + int64_t i, h48max; + + memset(distr, 0, 21 * sizeof(uint64_t)); + + h48max = H48_COORDMAX(h); + for (i = 0; i < h48max; i++) { + val = get_h48_pval(table, i, k); + distr[val]++; + } +} + STATIC uint32_t * get_cocsepdata_ptr(const void *data) { diff --git a/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c @@ -24,6 +24,7 @@ typedef struct { typedef struct { uint8_t h; uint8_t k; + uint8_t base; uint8_t maxdepth; tableinfo_t info; void *buf; diff --git a/tools/0002_gendata_h48h0k2/gendata_h48h0k2.c b/tools/0002_gendata_h48h0k2/gendata_h48h0k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 5473562, - [1] = 34776317, - [2] = 68566704, - [3] = 8750867, -}; - -void run(void) { - gendata_run("h48", "0;2;20", "tables/h48h0k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 0, k = 2"); - - return 0; -} diff --git a/tools/0004_gendata_h48h0k4/gendata_h48h0k4.c b/tools/0004_gendata_h48h0k4/gendata_h48h0k4.c @@ -1,29 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - [0] = 1, - [1] = 1, - [2] = 4, - [3] = 34, - [4] = 331, - [5] = 3612, - [6] = 41605, - [7] = 474128, - [8] = 4953846, - [9] = 34776317, - [10] = 68566704, - [11] = 8749194, - [12] = 1673, -}; - -void run(void) { - gendata_run("h48", "0;4;20", "tables/h48h0k4", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 0, k = 4"); - - return 0; -} diff --git a/tools/000_gendata/gendata.c b/tools/000_gendata/gendata.c @@ -0,0 +1,55 @@ +#include "../tool.h" +#include "../expected_distributions.h" + +char *solver, *options; +uint64_t *expected; + +static void +run(void) { + int64_t size; + char *buf, filename[1024]; + + getfilename(solver, options, filename); + size = generatetable(solver, options, &buf); + switch (size) { + case -1: + return; + case -2: + goto gendata_run_finish; + default: + nissy_datainfo(buf, write_stdout); + printf("\n"); + printf("Succesfully generated %" PRId64 " bytes. " + "See above for details on the tables.\n", size); + + writetable(buf, size, filename); + break; + } + +gendata_run_finish: + free(buf); +} + +int main(int argc, char **argv) { + uint8_t h, k; + char description[256]; + + if (argc < 3) { + fprintf(stderr, "Error: not enough arguments. " + "A solver and its options must be given.\n"); + return 1; + } + + solver = argv[1]; + options = argv[2]; + parse_h48_options(options, &h, &k, NULL); + expected = expected_h48[h][k]; + sprintf(description, "benchmark gendata_h48 h = %" PRIu8 + ", k = %" PRIu8 "", h, k); + + nissy_setlogger(log_stderr); + + timerun(run, description); + + return 0; +} diff --git a/tools/0012_gendata_h48h1k2/gendata_h48h1k2.c b/tools/0012_gendata_h48h1k2/gendata_h48h1k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "1;2;20", "tables/h48h1k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 1, k = 2"); - - return 0; -} diff --git a/tools/0022_gendata_h48h2k2/gendata_h48h2k2.c b/tools/0022_gendata_h48h2k2/gendata_h48h2k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "2;2;20", "tables/h48h2k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 2, k = 2"); - - return 0; -} diff --git a/tools/0032_gendata_h48h3k2/gendata_h48h3k2.c b/tools/0032_gendata_h48h3k2/gendata_h48h3k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "3;2;20", "tables/h48h3k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 3, k = 2"); - - return 0; -} diff --git a/tools/0042_gendata_h48h4k2/gendata_h48h4k2.c b/tools/0042_gendata_h48h4k2/gendata_h48h4k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "4;2;20", "tables/h48h4k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 4, k = 2"); - - return 0; -} diff --git a/tools/0052_gendata_h48h5k2/gendata_h48h5k2.c b/tools/0052_gendata_h48h5k2/gendata_h48h5k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "5;2;20", "tables/h48h5k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 5, k = 2"); - - return 0; -} diff --git a/tools/0062_gendata_h48h6k2/gendata_h48h6k2.c b/tools/0062_gendata_h48h6k2/gendata_h48h6k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "6;2;20", "tables/h48h6k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 6, k = 2"); - - return 0; -} diff --git a/tools/0072_gendata_h48h7k2/gendata_h48h7k2.c b/tools/0072_gendata_h48h7k2/gendata_h48h7k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "7;2;20", "tables/h48h7k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 7, k = 2"); - - return 0; -} diff --git a/tools/0082_gendata_h48h8k2/gendata_h48h8k2.c b/tools/0082_gendata_h48h8k2/gendata_h48h8k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "8;2;20", "tables/h48h8k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 8, k = 2"); - - return 0; -} diff --git a/tools/0092_gendata_h48h9k2/gendata_h48h9k2.c b/tools/0092_gendata_h48h9k2/gendata_h48h9k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "9;2;20", "tables/h48h9k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 9, k = 2"); - - return 0; -} diff --git a/tools/0102_gendata_h48h10k2/gendata_h48h10k2.c b/tools/0102_gendata_h48h10k2/gendata_h48h10k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "10;2;20", "tables/h48h10k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 10, k = 2"); - - return 0; -} diff --git a/tools/0112_gendata_h48h11k2/gendata_h48h11k2.c b/tools/0112_gendata_h48h11k2/gendata_h48h11k2.c @@ -1,21 +0,0 @@ -#include "../tool.h" - -uint64_t expected[21] = { - /* Base value is 8 */ - [0] = 0, /* Unknown */ - [1] = 0, /* Unknown */ - [2] = 0, /* Unknown */ - [3] = 0, /* Unknown */ -}; - -void run(void) { - gendata_run("h48", "11;2;20", "tables/h48h11k2", expected); -} - -int main(void) { - nissy_setlogger(log_stderr); - - timerun(run, "benchmark gendata_h48 h = 11, k = 2"); - - return 0; -} diff --git a/tools/100_checkdata/checkdata.c b/tools/100_checkdata/checkdata.c @@ -0,0 +1,52 @@ +#include "../tool.h" +#include "../expected_distributions.h" + +char *solver, *options, *filename; + +static void +run(void) { + int64_t size; + char *buf; + FILE *f; + + size = nissy_datasize(solver, options); + + if (size <= 0) { + fprintf(stderr, "Error in datasize\n"); + return; + } + + if ((f = fopen(filename, "rb")) == NULL) { + fprintf(stderr, "Error reading file %s\n", filename); + return; + } + + buf = malloc(size); + fread(buf, size, 1, f); + fclose(f); + nissy_checkdata(solver, options, buf); + free(buf); + + /* TODO: cross-check with expected distributions? */ +} + +int main(int argc, char **argv) { + char description[256]; + + if (argc < 4) { + fprintf(stderr, "Error: not enough arguments. " + "A solver, its options and a file name must be given.\n"); + return 1; + } + + solver = argv[1]; + options = argv[2]; + filename = argv[3]; + sprintf(description, "checking data for solver %s" + "with options %s from file %s", solver, options, filename); + nissy_setlogger(log_stderr); + + timerun(run, description); + + return 0; +} diff --git a/tools/100_stats_tables_h48/stats_tables_h48.c b/tools/200_stats_tables_h48/stats_tables_h48.c diff --git a/tools/200_solve_small/solve_small.c b/tools/300_solve_small/solve_small.c diff --git a/tools/expected_distributions.h b/tools/expected_distributions.h @@ -0,0 +1,25 @@ +uint64_t expected_h48[12][9][21] = { + [0] = { + [2] = { + [0] = 5473562, + [1] = 34776317, + [2] = 68566704, + [3] = 8750867, + }, + [4] = { + [0] = 1, + [1] = 1, + [2] = 4, + [3] = 34, + [4] = 331, + [5] = 3612, + [6] = 41605, + [7] = 474128, + [8] = 4953846, + [9] = 34776317, + [10] = 68566704, + [11] = 8749194, + [12] = 1673, + }, + }, +}; diff --git a/tools/nissy_extra.h b/tools/nissy_extra.h @@ -4,3 +4,4 @@ for testing purposes only. */ size_t gendata_h48_derive(uint8_t, const void *, void *); +int parse_h48_options(const char *, uint8_t *, uint8_t *, uint8_t *); diff --git a/tools/run_tool.sh b/tools/run_tool.sh @@ -5,7 +5,7 @@ if [ -z "$TOOL" ]; then exit 1 fi -CC="$CC -D_POSIX_C_SOURCE=199309L" +CC="$CC -D_POSIX_C_SOURCE=199309L" # For timer BIN="tools/run" d="$(date +'%Y-%m-%d-%H-%M-%S')" @@ -16,7 +16,8 @@ for t in tools/*; do fi toolname="$(basename "$t" .c)" $CC -o $BIN "$t"/*.c "$CUBEOBJ" || exit 1; - $BIN | tee "tools/results/$toolname-$d.txt" "tools/results/last.out" + $BIN $TOOLARGS \ + | tee "tools/results/$toolname-$d.txt" "tools/results/last.out" break done diff --git a/tools/tool.h b/tools/tool.h @@ -11,11 +11,12 @@ static void log_stderr(const char *, ...); static void log_stdout(const char *, ...); static double timerun(void (*)(void), const char *); +static void getfilename(const char *, const char *, char *); static void writetable(const char *, int64_t, const char *); static int64_t generatetable(const char *, const char *, char **); static int64_t derivetable(uint8_t, char **); static int getdata(const char *, const char *, char **, const char *); -static void gendata_run(const char *, const char *, const char *, uint64_t[static 21]); +static void gendata_run(const char *, const char *, uint64_t[static 21]); static void derivedata_run(uint8_t, const char *, uint64_t[static 21]); static void @@ -73,6 +74,17 @@ timerun(void (*run)(void), const char *name) } static void +getfilename(const char *solver, const char *options, char *filename) +{ + uint8_t h, k; + + /* Only h48 supported for now */ + parse_h48_options(options, &h, &k, NULL); + + sprintf(filename, "tables/%sh%dk%d", solver, h, k); +} + +static void writetable(const char *buf, int64_t size, const char *filename) { FILE *f; @@ -193,13 +205,12 @@ static void gendata_run( const char *solver, const char *options, - const char *filename, /* TODO: remove filename, use solver name */ uint64_t expected[static 21] ) { int64_t size; - char *buf; + char *buf, filename[1024]; - + getfilename(solver, options, filename); size = generatetable(solver, options, &buf); switch (size) { case -1: