From 8b94d135429a9f3253cc7f25a1453b412065c4a0 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 18 May 2025 08:48:13 +0200 Subject: Refactor solver dispatch and checkdata --- src/solvers/coord/gendata.h | 35 ++++---------- src/solvers/coord/solve.h | 35 +++++++------- src/solvers/coord/utils.h | 12 +++-- src/solvers/dispatch.h | 49 +++++++++++++++++++ src/solvers/distribution.h | 77 ++++++++++++++++++++++++++++++ src/solvers/h48/gendata_cocsep.h | 16 ------- src/solvers/h48/gendata_h48.h | 86 ++++++++++------------------------ src/solvers/h48/gendata_types_macros.h | 8 ---- src/solvers/h48/h48.h | 1 + src/solvers/h48/solve.h | 34 ++++++++++++++ src/solvers/h48/utils.h | 66 ++++++++++++++++++++++++++ src/solvers/solvers.h | 2 + 12 files changed, 287 insertions(+), 134 deletions(-) create mode 100644 src/solvers/dispatch.h create mode 100644 src/solvers/distribution.h create mode 100644 src/solvers/h48/utils.h (limited to 'src/solvers') diff --git a/src/solvers/coord/gendata.h b/src/solvers/coord/gendata.h index 7a974f8..1b65f49 100644 --- a/src/solvers/coord/gendata.h +++ b/src/solvers/coord/gendata.h @@ -1,5 +1,6 @@ STATIC size_t gendata_coord(const coord_t [static 1], unsigned char *); -STATIC int64_t gendata_coord_dispatch(const char *, unsigned char *); +STATIC long long gendata_coord_dispatch(const char *, unsigned long long, + unsigned char *); STATIC tableinfo_t genptable_coord( const coord_t [static 1], const unsigned char *, unsigned char *); STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t); @@ -7,15 +8,17 @@ STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1], const unsigned char *, uint64_t, uint8_t, unsigned char *); STATIC uint64_t genptable_coord_fillfromnew(const coord_t [static 1], const unsigned char *, uint64_t, uint8_t, unsigned char *); -STATIC void getdistribution_coord(const unsigned char *, const char *, - uint64_t [static INFO_DISTRIBUTION_LEN]); STATIC uint8_t get_coord_pval( const coord_t [static 1], const unsigned char *, uint64_t); STATIC void set_coord_pval( const coord_t [static 1], unsigned char *, uint64_t, uint8_t); -STATIC int64_t -gendata_coord_dispatch(const char *coordstr, unsigned char *buf) +STATIC long long +gendata_coord_dispatch( + const char *coordstr, + unsigned long long bufsize, + unsigned char *buf +) { coord_t *coord; @@ -249,28 +252,6 @@ genptable_coord_fillfromnew( return tot; } -STATIC void -getdistribution_coord( - const unsigned char *table, - const char *coord, - uint64_t distr[static INFO_DISTRIBUTION_LEN] -) -{ - uint8_t v; - uint64_t i; - coord_t *c; - - memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); - - if((c = parse_coord(strlen(coord), coord)) == NULL) - return; - - for (i = 0; i < c->max; i++) { - v = get_coord_pval(c, table, i); - distr[v]++; - } -} - STATIC uint8_t get_coord_pval( const coord_t coord[static 1], diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h index 8eb3e9d..df0f6ff 100644 --- a/src/solvers/coord/solve.h +++ b/src/solvers/coord/solve.h @@ -13,11 +13,13 @@ typedef struct { } dfsarg_solve_coord_t; STATIC int64_t solve_coord(oriented_cube_t, coord_t [static 1], uint8_t, - uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, - const unsigned char *, size_t n, char [n], int (*)(void *), void *); -STATIC int64_t solve_coord_dispatch(oriented_cube_t, const char *, uint8_t, - uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t, - const unsigned char *, size_t n, char [n], int (*)(void *), void *); + uint8_t, uint8_t, uint8_t, uint64_t, uint8_t, uint8_t, uint64_t n, + const unsigned char [n], size_t m, char [m], int (*)(void *), void *); +STATIC long long solve_coord_dispatch(oriented_cube_t, const char *, unsigned, + unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long n, + const unsigned char [n], unsigned m, char [m], + long long [static NISSY_SIZE_SOLVE_STATS], + int (*)(void *), void *); STATIC bool coord_solution_admissible(const dfsarg_solve_coord_t [static 1]); STATIC bool solve_coord_dfs_stop(const dfsarg_solve_coord_t [static 1]); STATIC bool coord_continue_onnormal(const dfsarg_solve_coord_t [static 1]); @@ -198,20 +200,21 @@ solve_coord_dfs(dfsarg_solve_coord_t arg[static 1]) return ret; } -STATIC int64_t +STATIC long long solve_coord_dispatch( oriented_cube_t oc, const char *coord_and_axis, - uint8_t nissflag, - uint8_t minmoves, - uint8_t maxmoves, - uint64_t maxsolutions, - uint8_t optimal, - uint8_t threads, - uint64_t data_size, - const unsigned char *data, - size_t solutions_size, + unsigned nissflag, + unsigned minmoves, + unsigned maxmoves, + unsigned maxsolutions, + unsigned optimal, + unsigned threads, + unsigned long long data_size, + const unsigned char data[data_size], + unsigned solutions_size, char sols[solutions_size], + long long stats[static NISSY_SIZE_SOLVE_STATS], int (*poll_status)(void *), void *poll_status_data ) @@ -250,7 +253,7 @@ solve_coord( uint8_t optimal, uint8_t threads, uint64_t data_size, - const unsigned char *data, + const unsigned char data[data_size], size_t solutions_size, char sols[solutions_size], int (*poll_status)(void *), diff --git a/src/solvers/coord/utils.h b/src/solvers/coord/utils.h index ef3f817..aa4d74c 100644 --- a/src/solvers/coord/utils.h +++ b/src/solvers/coord/utils.h @@ -2,7 +2,7 @@ STATIC coord_t *parse_coord(size_t n, const char [n]); STATIC uint8_t parse_axis(size_t n, const char [n]); STATIC void parse_coord_and_axis( size_t n, const char [n], coord_t **, uint8_t *); -STATIC int64_t dataid_coord(const char *, char [static NISSY_SIZE_DATAID]); +STATIC long long dataid_coord(const char *, char [static NISSY_SIZE_DATAID]); STATIC coord_t * parse_coord(size_t n, const char coord[n]) @@ -38,20 +38,22 @@ parse_coord_and_axis( uint8_t *axis ) { + const char *s; size_t i; + s = str + 6; for (i = 0; i < n; i++) - if (str[i] == '_') + if (s[i] == '_') break; if (coord != NULL) - *coord = parse_coord(i, str); + *coord = parse_coord(i, s); if (axis != NULL) - *axis = i == n ? UINT8_ERROR : parse_axis(n-i-1, str+i+1); + *axis = i == n ? UINT8_ERROR : parse_axis(n-i-1, s+i+1); } -STATIC int64_t +STATIC long long dataid_coord(const char *ca, char dataid[static NISSY_SIZE_DATAID]) { coord_t *c; diff --git a/src/solvers/dispatch.h b/src/solvers/dispatch.h new file mode 100644 index 0000000..0cfbc3b --- /dev/null +++ b/src/solvers/dispatch.h @@ -0,0 +1,49 @@ +typedef struct { + const char *prefix; + long long (*dataid)(const char *, char [static NISSY_SIZE_DATAID]); + long long (*gendata)( + const char *, unsigned long long, unsigned char *); + long long (*solve)(oriented_cube_t, const char *, unsigned, unsigned, + unsigned, unsigned, unsigned, unsigned, unsigned long long, + const unsigned char *, unsigned, char *, + long long [static NISSY_SIZE_SOLVE_STATS], + int (*)(void *), void *); +} solver_dispatch_t; + +STATIC solver_dispatch_t *match_solver(const char *); + +solver_dispatch_t solver_dispatchers[] = { +{ + .prefix = "h48", + .dataid = dataid_h48, + .gendata = gendata_h48_dispatch, + .solve = solve_h48_dispatch, +}, +{ + .prefix = "coord_", + .dataid = dataid_coord, + .gendata = gendata_coord_dispatch, + .solve = solve_coord_dispatch, +}, +{ + .prefix = NULL +} +}; + +STATIC solver_dispatch_t * +match_solver(const char *name) +{ + const char *prefix; + int i; + + if (name == NULL) + return NULL; + + for (i = 0; solver_dispatchers[i].prefix != NULL; i++) { + prefix = solver_dispatchers[i].prefix; + if (!strncmp(name, prefix, strlen(prefix))) + return &solver_dispatchers[i]; + } + + return NULL; +} diff --git a/src/solvers/distribution.h b/src/solvers/distribution.h new file mode 100644 index 0000000..1a3719c --- /dev/null +++ b/src/solvers/distribution.h @@ -0,0 +1,77 @@ +#define ENTRIES_PER_BYTE(k) (UINT64_C(8) / (uint64_t)(k)) +#define TABLE_SHIFT(i, k) ((uint8_t)(k) * (uint8_t)((i) % ENTRIES_PER_BYTE(k))) +#define TABLE_MASK(i, k) ((UINT8_BIT(k) - UINT8_C(1)) << TABLE_SHIFT(i, k)) + +typedef struct { + uint64_t min; + uint64_t max; + uint8_t bits; + uint64_t *distr; + const unsigned char *table; +} getdistribution_data_t; + +STATIC void *getdistribution_runthread(void *); +STATIC void getdistribution(const unsigned char *, + uint64_t [static INFO_DISTRIBUTION_LEN], const tableinfo_t [static 1]); + +STATIC void * +getdistribution_runthread(void *arg) +{ + getdistribution_data_t *data = (getdistribution_data_t *)arg; + const unsigned char *table; + uint8_t j, k, m; + uint64_t i; + + memset(data->distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); + + k = data->bits; + table = data->table; + m = TABLE_MASK(0, k); + for (i = data->min; i < data->max; i++) + for (j = 0; j < ENTRIES_PER_BYTE(k); j++) + data->distr[(table[i] & (m << (j*k))) >> (j*k)]++; + + return NULL; +} + +STATIC void +getdistribution( + const unsigned char *table, + uint64_t distr[static INFO_DISTRIBUTION_LEN], + const tableinfo_t info[static 1] +) { + getdistribution_data_t targ[THREADS]; + pthread_t thread[THREADS]; + uint8_t pval, k; + uint64_t local_distr[THREADS][INFO_DISTRIBUTION_LEN]; + uint64_t i, j, nbytes, sz, epb; + + k = info->bits; + epb = ENTRIES_PER_BYTE(k); + nbytes = info->entries / epb; + sz = nbytes / THREADS; + for (i = 0; i < THREADS; i++) { + targ[i] = (getdistribution_data_t) { + .min = i * sz, + .max = i == THREADS - 1 ? nbytes : (i+1) * sz, + .bits = k, + .distr = local_distr[i], + .table = table, + }; + pthread_create(&thread[i], NULL, + getdistribution_runthread, &targ[i]); + } + + for (i = 0; i < THREADS; i++) + pthread_join(thread[i], NULL); + + memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); + for (i = 0; i < THREADS; i++) + for (j = 0; j < INFO_DISTRIBUTION_LEN; j++) + distr[j] += local_distr[i][j]; + + for (i = nbytes * epb; i < info->entries; i++) { + pval = (table[i/epb] & TABLE_MASK(i, k)) >> TABLE_SHIFT(i, k); + distr[pval]++; + } +} diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h index 2eac383..3117a8e 100644 --- a/src/solvers/h48/gendata_cocsep.h +++ b/src/solvers/h48/gendata_cocsep.h @@ -1,7 +1,5 @@ STATIC size_t gendata_cocsep(unsigned char *, uint64_t *, cube_t *); STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t [static 1]); -STATIC void getdistribution_cocsep( - const uint32_t [static COCSEP_TABLESIZE], uint64_t [static 21]); STATIC_INLINE bool gendata_cocsep_get_visited( const uint8_t [static COCSEP_VISITEDSIZE], int64_t); @@ -136,20 +134,6 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t arg[static 1]) return cc; } -STATIC void -getdistribution_cocsep( - const uint32_t table[static COCSEP_TABLESIZE], - 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 gendata_cocsep_get_visited( const uint8_t a[static COCSEP_VISITEDSIZE], diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index c1a9ced..644ddc2 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h @@ -1,3 +1,5 @@ +STATIC long long gendata_h48_dispatch( + const char *, unsigned long long, unsigned char *); STATIC uint64_t gendata_h48short(gendata_h48short_arg_t [static 1]); STATIC int64_t gendata_h48(gendata_h48_arg_t [static 1]); STATIC void gendata_h48h0k4(gendata_h48_arg_t [static 1]); @@ -12,9 +14,6 @@ STATIC_INLINE bool gendata_h48k2_dfs_stop( cube_t, int8_t, h48k2_dfs_arg_t [static 1]); STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t [static 1]); STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t [static 1]); -STATIC void *getdistribution_h48_runthread(void *); -STATIC void getdistribution_h48(const unsigned char *, - uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t, uint8_t); STATIC const uint32_t *get_cocsepdata_constptr(const unsigned char *); STATIC const unsigned char *get_h48data_constptr(const unsigned char *); @@ -28,6 +27,27 @@ STATIC_INLINE void set_h48_pval_atomic( size_t gendata_h48_derive(uint8_t, const unsigned char *, unsigned char *); +STATIC long long +gendata_h48_dispatch( + const char *solver, + unsigned long long data_size, + unsigned char *data +) +{ + long long err; + gendata_h48_arg_t arg; + + err = parse_h48_hk(solver, &arg.h, &arg.k); + if (err != NISSY_OK) + return err; + + arg.buf_size = data_size; + arg.buf = data; + arg.maxdepth = 20; + + return gendata_h48(&arg); +} + STATIC uint64_t gendata_h48short(gendata_h48short_arg_t arg[static 1]) { @@ -649,64 +669,6 @@ makeinfo_h48k2(gendata_h48_arg_t arg[static 1]) return info; } -STATIC void * -getdistribution_h48_runthread(void *arg) -{ - getdistribution_h48_data_t *data = (getdistribution_h48_data_t *)arg; - const unsigned char *table; - uint8_t j, k, m; - int64_t i; - - memset(data->distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); - - k = data->k; - table = data->table; - m = H48_MASK(0, k); - for (i = data->min; i < data->max; i++) - for (j = 0; j < H48_DIV(k); j++) - data->distr[(table[i] & (m << (j*k))) >> (j*k)]++; - - return NULL; -} - -STATIC void -getdistribution_h48( - const unsigned char *table, - uint64_t distr[static INFO_DISTRIBUTION_LEN], - uint8_t h, - uint8_t k -) { - getdistribution_h48_data_t targ[THREADS]; - pthread_t thread[THREADS]; - uint64_t local_distr[THREADS][INFO_DISTRIBUTION_LEN]; - int64_t i, j, nbytes, sz; - - nbytes = H48_COORDMAX(h) / H48_DIV(k); - sz = nbytes / THREADS; - for (i = 0; i < THREADS; i++) { - targ[i] = (getdistribution_h48_data_t) { - .min = i * sz, - .max = i == THREADS - 1 ? nbytes : (i+1) * sz, - .k = k, - .distr = local_distr[i], - .table = table, - }; - pthread_create(&thread[i], NULL, - getdistribution_h48_runthread, &targ[i]); - } - - for (i = 0; i < THREADS; i++) - pthread_join(thread[i], NULL); - - memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); - for (i = 0; i < THREADS; i++) - for (j = 0; j < INFO_DISTRIBUTION_LEN; j++) - distr[j] += local_distr[i][j]; - - for (i = nbytes * H48_DIV(k); i < H48_COORDMAX(h); i++) - distr[get_h48_pval(table, i, k)]++; -} - STATIC const uint32_t * get_cocsepdata_constptr(const unsigned char *data) { @@ -821,7 +783,7 @@ gendata_h48_derive(uint8_t h, const unsigned char *fulltable, unsigned char *buf h48derive, j, arg.k, MIN(val_full, val_derive)); } - getdistribution_h48(h48derive, arg.info.distribution, h, arg.k); + getdistribution(h48derive, arg.info.distribution, &arg.info); bufsize = arg.buf_size - COCSEP_FULLSIZE - INFOSIZE; if (writetableinfo(&arg.info, bufsize, (unsigned char *)arg.h48buf) diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h index c4b1b5a..b0592c2 100644 --- a/src/solvers/h48/gendata_types_macros.h +++ b/src/solvers/h48/gendata_types_macros.h @@ -121,11 +121,3 @@ typedef struct { _Atomic unsigned char *table_atomic; pthread_mutex_t **table_mutex; } gendata_h48_mark_t; - -typedef struct { - int64_t min; - int64_t max; - uint8_t k; - uint64_t *distr; - const unsigned char *table; -} getdistribution_h48_data_t; diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index 0cfa773..79d2583 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h @@ -1,3 +1,4 @@ +#include "utils.h" #include "coordinate_types_macros.h" #include "map_types_macros.h" #include "gendata_types_macros.h" diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index f2967ed..2818c09 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -50,6 +50,10 @@ typedef struct { int8_t *shortest_sol; } dfsarg_solve_h48_maketasks_t; +STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, + unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long n, + const unsigned char [n], unsigned m, char [m], + long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t [static 1]); STATIC int64_t solve_h48_maketasks( dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], @@ -61,6 +65,36 @@ STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, uint64_t, const unsigned char *, size_t n, char [n], long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); +STATIC long long solve_h48_dispatch( + oriented_cube_t oc, + const char *solver, + unsigned nissflag, + unsigned minmoves, + unsigned maxmoves, + unsigned maxsols, + unsigned optimal, + unsigned threads, + unsigned long long data_size, + const unsigned char data[data_size], + unsigned sols_size, + char sols[sols_size], + long long stats[static NISSY_SIZE_SOLVE_STATS], + int (*poll_status)(void *), + void *poll_status_data +) +{ + uint8_t h, k; + long long err; + + err = parse_h48_hk(solver, &h, &k); + if (err != NISSY_OK) + return err; + + return solve_h48(oc, minmoves, maxmoves, maxsols, optimal, threads, + data_size, data, sols_size, sols, stats, + poll_status, poll_status_data); +} + STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) { diff --git a/src/solvers/h48/utils.h b/src/solvers/h48/utils.h new file mode 100644 index 0000000..b266c66 --- /dev/null +++ b/src/solvers/h48/utils.h @@ -0,0 +1,66 @@ +long long parse_h48_hk( + const char *, uint8_t [static 1], uint8_t [static 1]); +STATIC long long dataid_h48(const char *, char [static NISSY_SIZE_DATAID]); + +long long +parse_h48_hk(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) +{ + char format_error_msg[100]; + sprintf(format_error_msg, "[H48] Error parsing H48 solver: must be in " + "'h48h*k*' format, but got '%s'\n", buf); + + buf += 3; + + if (*buf != 'h') { + LOG(format_error_msg); + goto parse_h48_hk_error; + } + buf++; + + *h = atoi(buf); + if (*h > 11) { + LOG("[H48] Invalid value %" PRIu8 " for parameter h\n", *h); + goto parse_h48_hk_error; + } + + for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++) { + if (*buf == 0) { + LOG(format_error_msg); + goto parse_h48_hk_error; + } + } + + if (*buf != 'k') { + LOG(format_error_msg); + goto parse_h48_hk_error; + } + buf++; + + *k = atoi(buf); + if (!(*k == 2 || (*k == 4 && *h == 0))) { + LOG("[H48] Invalid combinations of values h=%" PRIu8 " and k=%" + PRIu8 " for parameters h and k\n", *h, *k); + goto parse_h48_hk_error; + } + + return NISSY_OK; + +parse_h48_hk_error: + *h = 0; + *k = 0; + return NISSY_ERROR_INVALID_SOLVER; +} + +STATIC long long +dataid_h48(const char *hk, char buf[static NISSY_SIZE_DATAID]) +{ + uint8_t h, k; + long long err; + + err = parse_h48_hk(hk, &h, &k); + if (err < 0) + return err; + + sprintf(buf, "h48h%" PRIu8 "k%" PRIu8, h, k); + return NISSY_OK; +} diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h index 4d6bbca..27ae627 100644 --- a/src/solvers/solvers.h +++ b/src/solvers/solvers.h @@ -2,5 +2,7 @@ #include "solutions.h" #include "tables_types_macros.h" #include "tables.h" +#include "distribution.h" #include "h48/h48.h" #include "coord/coord.h" +#include "dispatch.h" -- cgit v1.3