commit d45e1595ec1cffeab83ac6602b748250b66bea03 parent ce3f1cc0ef9f46d70ab5387b1458e9098b40711d Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon, 24 Mar 2025 23:09:26 +0100 Big cleanup for appendsolution() With this PR the appendsolution routine is extracted from the h48 solver and the new coordinate solver and made generic. This has many advantages: - less repetition (even if the two versions are different enough that *for now* it was not a big deal) - smaller h48/solve.h file, which is already a big beast - easier to test the appendsolution() routine separately Diffstat:
36 files changed, 562 insertions(+), 349 deletions(-)
diff --git a/src/core/io_moves.h b/src/core/io_moves.h @@ -1,6 +1,26 @@ STATIC uint8_t readmove(char); +STATIC int64_t readmoves(const char *, size_t n, uint8_t [n]); STATIC uint8_t readmodifier(char); -STATIC int64_t writemoves(size_t n, uint8_t [n], size_t m, char [m]); +STATIC int64_t writemoves(size_t n, const uint8_t [n], size_t m, char [m]); + +#define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \ + RET_ERROR, ARG_ACTION) \ + const char *VAR_B; \ + uint8_t VAR_MOVE_NOMOD, VAR_MOD; \ + for (VAR_B = ARG_BUF, ARG_C = 0; *VAR_B != '\0'; VAR_B++, ARG_C++) { \ + while (*VAR_B == ' ' || *VAR_B == '\t' || *VAR_B == '\n') \ + VAR_B++; \ + if (*VAR_B == '\0' || ARG_C == ARG_MAX) \ + break; \ + if ((VAR_MOVE_NOMOD = readmove(*VAR_B)) == UINT8_ERROR) { \ + LOG("Error: unknown move '%c'\n", *VAR_B); \ + return RET_ERROR; \ + } \ + if ((VAR_MOD = readmodifier(*(VAR_B+1))) != 0) \ + VAR_B++; \ + ARG_MOVE = VAR_MOVE_NOMOD + VAR_MOD; \ + ARG_ACTION \ + } STATIC uint8_t readmove(char c) @@ -39,9 +59,22 @@ readmodifier(char c) } STATIC int64_t +readmoves(const char *buf, size_t n, uint8_t ret[n]) +{ + uint8_t m; + uint64_t c; + + FOREACH_READMOVE(buf, m, c, n, NISSY_ERROR_INVALID_MOVES, + ret[c] = m; + ) + + return (int64_t)c; +} + +STATIC int64_t writemoves( size_t nmoves, - uint8_t m[nmoves], + const uint8_t m[nmoves], size_t buf_size, char buf[buf_size] ) @@ -69,7 +102,9 @@ writemoves( *b = ' '; } - if (b != buf) + if (b == buf) + written = 1; /* Nothing written, only NULL-terminator */ + else b--; /* Remove last space */ *b = '\0'; diff --git a/src/core/moves.h b/src/core/moves.h @@ -3,6 +3,7 @@ STATIC_INLINE bool allowednextmove(size_t n, const uint8_t [n]); STATIC_INLINE uint32_t allowednextmove_mask(size_t n, const uint8_t [n]); +STATIC bool allowedmoves(size_t n, const uint8_t [n]); STATIC_INLINE uint8_t movebase(uint8_t); STATIC_INLINE uint8_t moveaxis(uint8_t); @@ -13,11 +14,9 @@ STATIC_INLINE uint32_t disable_moves(uint32_t, uint8_t); STATIC cube_t move(cube_t, uint8_t); STATIC cube_t premove(cube_t, uint8_t); STATIC uint8_t inverse_move(uint8_t); -STATIC void invertmoves(size_t n, const uint8_t [n], uint8_t [n]); -STATIC void sortparallel(size_t n, uint8_t [n]); +STATIC void sortparallel_moves(size_t n, uint8_t [n]); STATIC bool are_lastmoves_singlecw(size_t n, uint8_t [n]); -STATIC int readmoves(const char *, int, uint8_t *); STATIC cube_t applymoves(cube_t, const char *); #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \ @@ -75,6 +74,18 @@ allowednextmove_mask(size_t n, const uint8_t moves[n]) return result; } +STATIC bool +allowedmoves(size_t n, const uint8_t moves[n]) +{ + uint8_t j; + + for (j = 2; j < n; j++) + if (!allowednextmove(j, moves)) + return false; + + return true; +} + STATIC_INLINE uint32_t disable_moves(uint32_t current_result, uint8_t base_index) { @@ -210,44 +221,13 @@ inverse_move(uint8_t m) return m - 2 * (m % 3) + 2; } -/* -GCC has issues when -Wstringop-overflow is used together with O3. It produces -warnings like the following: - -In function 'invertmoves', - inlined from 'solve_h48_appendsolution' at src/solvers/h48/solve.h:81:3, - inlined from 'solve_h48_dfs.isra' at src/solvers/h48/solve.h:139:3: -warning: writing 32 bytes into a region of size 0 [-Wstringop-overflow=] - 197 | ret[i] = inverse_move(moves[nmoves - i - 1]); - | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -In function 'solve_h48_dfs.isra': -note: at offset 192 into destination object 'invertedpremoves' of size 20 - 71 | uint8_t invertedpremoves[MAXLEN]; - -Clang does not give any warning. -Someone else complained here: https://access.redhat.com/solutions/6755371 - -To solve this issue temporarily, we use a lower optimization setting for -this function only. - -TODO check if the issue is resolved -*/ -#pragma GCC push_options -#pragma GCC optimize ("O2") STATIC void -invertmoves(size_t n, const uint8_t moves[n], uint8_t ret[n]) +sortparallel_moves(size_t n, uint8_t moves[n]) { uint8_t i; - for (i = 0; i < n; i++) - ret[i] = inverse_move(moves[n - i - 1]); -} -#pragma GCC pop_options - -STATIC void -sortparallel(size_t n, uint8_t moves[n]) -{ - uint8_t i; + if (n < 2) + return; for (i = 0; i < n-1; i++) if (moveaxis(moves[i]) == moveaxis(moves[i+1]) && @@ -268,20 +248,6 @@ are_lastmoves_singlecw(size_t n, uint8_t moves[n]) return isbase(moves[n-1]) && (!two || isbase(moves[n-2])); } -STATIC int -readmoves(const char *buf, int max, uint8_t *ret) -{ - uint8_t m; - int c; - - FOREACH_READMOVE(buf, m, c, max, NISSY_ERROR_INVALID_MOVES, - if (ret != NULL) - ret[c] = m; - ) - - return c; -} - STATIC cube_t applymoves(cube_t cube, const char *buf) { diff --git a/src/solvers/coord/solve.h b/src/solvers/coord/solve.h @@ -1,71 +1,21 @@ typedef struct { cube_t cube; - uint8_t depth; - uint8_t nmoves; - uint8_t moves[MAXLEN]; + uint8_t target_depth; + solution_moves_t *solution_moves; + solution_settings_t *solution_settings; coord_t *coord; const void *coord_data; const uint8_t *ptable; - uint8_t trans; - int64_t *nsols; - int64_t maxsolutions; - int optimal; - uint8_t *shortest_sol; - size_t solutions_size; - size_t *solutions_used; - char **solutions; + solution_list_t *solution_list; } dfsarg_solve_coord_t; STATIC int64_t solve_coord(cube_t, coord_t *, uint8_t, uint8_t, uint8_t, - uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); + uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *); STATIC int64_t solve_coord_dispatch(cube_t, const char *, uint8_t, uint8_t, - uint8_t, uint64_t, int, int, uint64_t, const void *, size_t, char *); -STATIC int64_t solve_coord_appendsolution(dfsarg_solve_coord_t *); + uint8_t, uint64_t, int8_t, int, uint64_t, const void *, size_t, char *); STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *); STATIC int64_t -solve_coord_appendsolution(dfsarg_solve_coord_t *arg) -{ - uint8_t i, t, tmoves[MAXLEN]; - int64_t strl; - uint64_t l; - char *m; - - if (*arg->nsols >= arg->maxsolutions || - arg->nmoves > *arg->shortest_sol + arg->optimal || - (arg->coord->is_admissible != NULL && - !arg->coord->is_admissible(arg->nmoves, arg->moves))) - return 0; - - t = inverse_trans(arg->trans); - for (i = 0; i < arg->nmoves; i++) - tmoves[i] = transform_move(arg->moves[i], t); - - sortparallel(arg->nmoves, tmoves); - - l = arg->solutions_size - *arg->solutions_used; - m = *arg->solutions + *arg->solutions_used; - strl = writemoves(arg->nmoves, tmoves, l, m); - if (strl < 0) - goto solve_coord_appendsolution_error; - - *arg->solutions_used += MAX(0, strl-1); - - if (!appendchar( - arg->solutions_size, *arg->solutions, arg->solutions_used, '\n')) - goto solve_coord_appendsolution_error; - - (*arg->nsols)++; - *arg->shortest_sol = MIN(*arg->shortest_sol, arg->nmoves); - - return 1; - -solve_coord_appendsolution_error: - LOG("Could not append solution to buffer: size too small\n"); - return NISSY_ERROR_BUFFER_SIZE; -} - -STATIC int64_t solve_coord_dfs(dfsarg_solve_coord_t *arg) { uint8_t m, pval; @@ -77,25 +27,30 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg) coord = arg->coord->coord(arg->cube, arg->coord_data); if (coord == 0) { - if (arg->nmoves != arg->depth) + if (arg->solution_moves->nmoves != arg->target_depth || + (arg->coord->is_admissible != NULL && + !arg->coord->is_admissible(arg->solution_moves->nmoves, + arg->solution_moves->moves))) return 0; - return solve_coord_appendsolution(arg); + return appendsolution(arg->solution_moves, + arg->solution_settings, arg->solution_list); } pval = get_coord_pval(arg->coord, arg->ptable, coord); - if (arg->nmoves + pval > arg->depth) + if (arg->solution_moves->nmoves + pval > arg->target_depth) return 0; backup_cube = arg->cube; ret = 0; - mm = allowednextmove_mask(arg->nmoves, arg->moves); - arg->nmoves++; - for (m = 0; m < 18; m++) { + mm = allowednextmove_mask( + arg->solution_moves->nmoves, arg->solution_moves->moves); + arg->solution_moves->nmoves++; + for (m = 0; m < NMOVES; m++) { if (!(mm & (1 << m))) continue; - arg->moves[arg->nmoves-1] = m; + arg->solution_moves->moves[arg->solution_moves->nmoves-1] = m; arg->cube = move(backup_cube, m); n = solve_coord_dfs(arg); if (n < 0) @@ -103,7 +58,7 @@ solve_coord_dfs(dfsarg_solve_coord_t *arg) ret += n; } arg->cube = backup_cube; - arg->nmoves--; + arg->solution_moves->nmoves--; return 0; } @@ -116,7 +71,7 @@ solve_coord_dispatch( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int optimal, + int8_t optimal, int threads, uint64_t data_size, const void *data, @@ -154,7 +109,7 @@ solve_coord( uint8_t minmoves, uint8_t maxmoves, uint64_t maxsolutions, - int optimal, + int8_t optimal, int threads, uint64_t data_size, const void *data, @@ -163,14 +118,19 @@ solve_coord( ) { int8_t d; - uint8_t t, shortest_sol; - int64_t nsols, ndepth; - size_t solutions_used; + uint8_t t; + int64_t ndepth; cube_t c; const void *coord_data; const uint8_t *ptable; dfsarg_solve_coord_t arg; tableinfo_t info; + solution_moves_t solution_moves; + solution_settings_t solution_settings; + solution_list_t solution_list; + + if (!solution_list_init(&solution_list, solutions_size, sols)) + goto solve_coord_error_buffer; if (readtableinfo(data_size, data, &info) != NISSY_OK) goto solve_coord_error_data; @@ -185,64 +145,59 @@ solve_coord( ptable = (uint8_t *)data + info.next + INFOSIZE; } - nsols = 0; - solutions_used = 0; - shortest_sol = MAXLEN + 1; t = coord->axistrans[axis]; c = transform(cube, t); + solution_moves_reset(&solution_moves); + + solution_settings = (solution_settings_t) { + .tmask = TM_SINGLE(inverse_trans(t)), + .unniss = false, + .maxmoves = maxmoves, + .maxsolutions = maxsolutions, + .optimal = optimal, + }; + arg = (dfsarg_solve_coord_t) { .cube = c, .coord = coord, .coord_data = coord_data, .ptable = ptable, - .trans = t, - .nsols = &nsols, - .maxsolutions = (int64_t)maxsolutions, - .optimal = optimal, - .shortest_sol = &shortest_sol, - .solutions_size = solutions_size, - .solutions_used = &solutions_used, - .solutions = &sols, + .solution_moves = &solution_moves, + .solution_settings = &solution_settings, + .solution_list = &solution_list, }; if (coord->coord(c, coord_data) == 0) { - if (minmoves == 0) { - nsols = 1; - if (!appendchar(solutions_size, sols, &solutions_used, '\n')) + if (minmoves == 0 && !appendsolution( + &solution_moves, &solution_settings, &solution_list)) goto solve_coord_error_buffer; - } goto solve_coord_done; } for ( d = MAX(minmoves, 1); - d <= maxmoves && nsols < (int64_t)maxsolutions - && !(nsols != 0 && d > shortest_sol + optimal); + !solutions_done(&solution_list, &solution_settings, d); d++ ) { if (d >= 10) - LOG("Found %" PRId64 " solutions, searching at depth %" - PRId8 "\n", nsols, d); + LOG("Found %" PRIu64 " solutions, searching at depth %" + PRId8 "\n", solution_list.nsols, d); - arg.depth = d; - arg.nmoves = 0; + arg.target_depth = d; + solution_moves_reset(arg.solution_moves); ndepth = solve_coord_dfs(&arg); - /* TODO: improve error handling? */ if (ndepth < 0) { LOG("Error %" PRId64 "\n", ndepth); return ndepth; } - nsols += ndepth; + solution_list.nsols += (uint64_t)ndepth; } solve_coord_done: - if (!appendchar(solutions_size, sols, &solutions_used, '\0')) - goto solve_coord_error_buffer; - - return nsols; + return (int64_t)solution_list.nsols; solve_coord_error_data: LOG("solve_coord: error reading table\n"); diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h @@ -4,27 +4,20 @@ typedef struct { cube_t cube; uint8_t moves[STARTING_MOVES]; - uint64_t symmask0; } solve_h48_task_t; typedef struct { cube_t start_cube; - uint64_t symmask0; cube_t cube; cube_t inverse; - int8_t depth; - int8_t nmoves; - uint8_t moves[MAXLEN]; - int8_t npremoves; - uint8_t premoves[MAXLEN]; + int8_t target_depth; + solution_moves_t *solution_moves; + solution_settings_t *solution_settings; + solution_list_t *solution_list; int8_t lb_normal; int8_t lb_inverse; bool use_lb_normal; bool use_lb_inverse; - _Atomic int64_t *nsols; - int64_t maxsolutions; - int8_t *shortest_sol; - int8_t optimal; uint8_t h; uint8_t k; uint8_t base; @@ -32,9 +25,6 @@ typedef struct { const uint8_t *h48data; const uint8_t *h48data_fallback_h0k4; const void *h48data_fallback_eoesep; - size_t solutions_size; - size_t *solutions_used; - char **solutions; uint32_t movemask_normal; uint32_t movemask_inverse; int64_t nodes_visited; @@ -56,8 +46,6 @@ typedef struct { int8_t *shortest_sol; } dfsarg_solve_h48_maketasks_t; -STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *); -STATIC int64_t solve_h48_appendallsym(dfsarg_solve_h48_t *); STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *); STATIC int64_t solve_h48_maketasks( dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *, @@ -65,107 +53,21 @@ STATIC int64_t solve_h48_maketasks( STATIC void *solve_h48_runthread(void *); STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *); STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, int8_t, int8_t, - uint64_t, const void *, size_t, char *, + uint64_t, const void *, size_t n, char [n], long long [static NISSY_SIZE_SOLVE_STATS]); -STATIC int64_t -solve_h48_appendsolution(dfsarg_solve_h48_t *arg) -{ - if (*arg->nsols >= arg->maxsolutions || - arg->nmoves + arg->npremoves > *arg->shortest_sol + arg->optimal) - return 0; - - invertmoves(arg->npremoves, arg->premoves, arg->moves + arg->nmoves); - - /* Sort parallel moves for consistency */ - sortparallel(arg->nmoves + arg->npremoves, arg->moves); - - /* Do not append the solution in case premoves cancel with normal */ - if (arg->npremoves > 0 && !allowednextmove(arg->nmoves+1, arg->moves)) - return 0; - if (arg->npremoves > 1 && !allowednextmove(arg->nmoves+2, arg->moves)) - return 0; - - return solve_h48_appendallsym(arg); -} - -STATIC int64_t -solve_h48_appendallsym(dfsarg_solve_h48_t *arg) -{ - bool eq; - uint8_t t, i, j, k, n; - int64_t ret, strl, l; - char *m; - uint8_t all[NTRANS][MAXLEN]; - - n = arg->nmoves + arg->npremoves; - - for (t = 0, j = 0; t < NTRANS; t++) { - if (!(arg->symmask0 & (UINT64_C(1) << (uint64_t)t))) - continue; - - for (i = 0; i < n; i++) - all[j][i] = transform_move(arg->moves[i], t); - - /* Sort parallel moves for consistency */ - sortparallel(n, all[j]); - - /* Check for duplicate solutions */ - for (k = 0; k < j; k++) { - eq = true; - for (i = 0; i < n; i++) - if (all[k][i] != all[j][i]) - eq = false; - - /* If a solution was already found, we skip it */ - if (eq) { - j--; - break; - } - } - - j++; - } - - /* The solutions are appended */ - ret = 0; - for (k = 0; k < j && *arg->nsols < arg->maxsolutions; k++) { - l = arg->solutions_size - *arg->solutions_used; - m = *arg->solutions + *arg->solutions_used; - strl = writemoves(n, all[k], l, m); - if (strl < 0) - goto solve_h48_appendallsym_error; - - LOG("Solution found: %s\n", m); - - *arg->solutions_used += MAX(0, strl-1); - - if (!appendchar(arg->solutions_size, - *arg->solutions, arg->solutions_used, '\n')) - goto solve_h48_appendallsym_error; - - (*arg->nsols)++; - *arg->shortest_sol = MIN(*arg->shortest_sol, n); - ret++; - } - - return ret; - -solve_h48_appendallsym_error: - LOG("Could not append solution to buffer: size too small\n"); - return NISSY_ERROR_BUFFER_SIZE; -} - STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *arg) { uint32_t data, data_inv; int64_t coord; - int8_t target, nh; + int8_t target, nh, n; uint8_t pval_cocsep, pval_eoesep; - target = arg->depth - arg->nmoves - arg->npremoves; - if (target <= 0 || *arg->nsols == arg->maxsolutions) + n = arg->solution_moves->nmoves + arg->solution_moves->npremoves; + target = arg->target_depth - n; + if (target <= 0 || + arg->solution_list->nsols == arg->solution_settings->maxsolutions) return true; arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES; @@ -246,16 +148,19 @@ STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *arg) { int64_t ret, n; - uint8_t m, lbn, lbi; + uint8_t m, nm, lbn, lbi; uint32_t mm_normal, mm_inverse; bool ulbi, ulbn; cube_t backup_cube, backup_inverse; if (issolved(arg->cube)) { - if (arg->nmoves + arg->npremoves != arg->depth) + nm = arg->solution_moves->nmoves + + arg->solution_moves->npremoves; + if (arg->target_depth != nm) return 0; pthread_mutex_lock(arg->solutions_mutex); - ret = solve_h48_appendsolution(arg); + ret = appendsolution(arg->solution_moves, + arg->solution_settings, arg->solution_list); pthread_mutex_unlock(arg->solutions_mutex); return ret; } @@ -271,16 +176,17 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg) ulbi = arg->use_lb_inverse; ret = 0; - mm_normal = allowednextmove_mask(arg->nmoves, arg->moves) & - arg->movemask_normal; - mm_inverse = allowednextmove_mask(arg->npremoves, arg->premoves) & - arg->movemask_inverse; + mm_normal = allowednextmove_mask(arg->solution_moves->nmoves, + arg->solution_moves->moves) & arg->movemask_normal; + mm_inverse = allowednextmove_mask(arg->solution_moves->npremoves, + arg->solution_moves->premoves) & arg->movemask_inverse; if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { - arg->nmoves++; + arg->solution_moves->nmoves++; for (m = 0; m < 18; m++) { if (!(mm_normal & (UINT32_C(1) << (uint32_t)m))) continue; - arg->moves[arg->nmoves-1] = m; + arg->solution_moves->moves[ + arg->solution_moves->nmoves-1] = m; arg->cube = move(backup_cube, m); arg->inverse = premove(backup_inverse, m); arg->lb_inverse = lbi; @@ -291,13 +197,14 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg) return n; ret += n; } - arg->nmoves--; + arg->solution_moves->nmoves--; } else { - arg->npremoves++; + arg->solution_moves->npremoves++; for (m = 0; m < 18; m++) { if(!(mm_inverse & (UINT32_C(1) << (uint32_t)m))) continue; - arg->premoves[arg->npremoves-1] = m; + arg->solution_moves->premoves[ + arg->solution_moves->npremoves-1] = m; arg->inverse = move(backup_inverse, m); arg->cube = premove(backup_cube, m); arg->lb_normal = lbn; @@ -308,7 +215,7 @@ solve_h48_dfs(dfsarg_solve_h48_t *arg) return n; ret += n; } - arg->npremoves--; + arg->solution_moves->npremoves--; } arg->cube = backup_cube; @@ -322,22 +229,23 @@ solve_h48_runthread(void *arg) { int i, j; solve_h48_task_t task; - dfsarg_solve_h48_t * dfsarg; - cube_t cube; + dfsarg_solve_h48_t *dfsarg; dfsarg = (dfsarg_solve_h48_t *)arg; - cube = dfsarg->start_cube; for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) { task = dfsarg->tasks[i]; - memcpy(dfsarg->moves, task.moves, STARTING_MOVES); - dfsarg->cube = cube; + + solution_moves_reset(dfsarg->solution_moves); + memcpy( + dfsarg->solution_moves->moves, task.moves, STARTING_MOVES); + dfsarg->solution_moves->nmoves = STARTING_MOVES; + + dfsarg->cube = dfsarg->start_cube; for (j = 0; j < STARTING_MOVES; j++) - dfsarg->cube = move( - dfsarg->cube, dfsarg->moves[j]); + dfsarg->cube = move(dfsarg->cube, task.moves[j]); dfsarg->inverse = inverse(dfsarg->cube); - dfsarg->nmoves = STARTING_MOVES; - dfsarg->npremoves = 0; + dfsarg->lb_normal = 0; dfsarg->lb_inverse = 0; dfsarg->use_lb_normal = false; @@ -364,16 +272,22 @@ solve_h48_maketasks( uint8_t m, t; uint32_t mm; cube_t backup_cube; + solution_moves_t moves; if (issolved(maketasks_arg->cube)) { if (maketasks_arg->nmoves > maketasks_arg->maxmoves || maketasks_arg->nmoves < maketasks_arg->minmoves || - *solve_arg->nsols >= solve_arg->maxsolutions) + solve_arg->solution_list->nsols >= + solve_arg->solution_settings->maxsolutions) return NISSY_OK; - memcpy(solve_arg->moves, + + solution_moves_reset(&moves); + moves.nmoves = maketasks_arg->nmoves; + memcpy(moves.moves, maketasks_arg->moves, maketasks_arg->nmoves); - solve_arg->nmoves = maketasks_arg->nmoves; - appret = solve_h48_appendsolution(solve_arg); + + appret = appendsolution(&moves, + solve_arg->solution_settings, solve_arg->solution_list); return appret < 0 ? appret : NISSY_OK; } @@ -402,7 +316,7 @@ solve_h48_maketasks( /* Avoid symmetry-equivalent moves from the starting cube */ if (maketasks_arg->nmoves == 1) for (t = 0; t < NTRANS; t++) - if (solve_arg->symmask0 & + if (solve_arg->solution_settings->tmask & (UINT64_C(1) << (uint64_t)t)) mm &= ~(UINT32_C(1) << (uint32_t)transform_move(m, t)); @@ -424,27 +338,31 @@ solve_h48( uint64_t data_size, const void *data, size_t solutions_size, - char *solutions, + char solutions[solutions_size], long long stats[static NISSY_SIZE_SOLVE_STATS] ) { int i, ntasks, eoesep_table_index; - int8_t d, shortest_sol; - _Atomic int64_t nsols; + int8_t d; dfsarg_solve_h48_t arg[THREADS]; solve_h48_task_t tasks[STARTING_CUBES]; dfsarg_solve_h48_maketasks_t maketasks_arg; long double fallback_rate, lookups_per_node; - uint64_t symmask, offset; - size_t solutions_used; + uint64_t offset; int64_t nodes_visited, table_lookups, table_fallbacks; tableinfo_t info, fbinfo, fbinfo2; const uint32_t *cocsepdata; const uint8_t *fallback, *h48data; const void *fallback2; + solution_moves_t solution_moves[THREADS]; + solution_settings_t settings; + solution_list_t sollist; pthread_t thread[THREADS]; pthread_mutex_t solutions_mutex; + if (!solution_list_init(&sollist, solutions_size, solutions)) + goto solve_h48_error_solutions_buffer; + if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) goto solve_h48_error_data; @@ -475,17 +393,18 @@ solve_h48( goto solve_h48_error_data; fallback2 = h48data + offset; - symmask = symmetry_mask(cube); - shortest_sol = MAXLEN+1; + settings = (solution_settings_t) { + .tmask = symmetry_mask(cube), + .unniss = true, + .maxmoves = maxmoves, + .maxsolutions = maxsolutions, + .optimal = optimal, + }; + for (i = 0; i < threads; i++) { arg[i] = (dfsarg_solve_h48_t) { .start_cube = cube, .cube = cube, - .symmask0 = symmask, - .nsols = &nsols, - .shortest_sol = &shortest_sol, - .optimal = optimal, - .maxsolutions = maxsolutions, .h = info.h48h, .k = info.bits, .base = info.base, @@ -493,9 +412,9 @@ solve_h48( .h48data = h48data, .h48data_fallback_h0k4 = fallback, .h48data_fallback_eoesep = fallback2, - .solutions_size = solutions_size, - .solutions_used = &solutions_used, - .solutions = &solutions, + .solution_moves = &solution_moves[i], + .solution_settings = &settings, + .solution_list = &sollist, .nodes_visited = 0, .table_fallbacks = 0, .table_lookups = 0, @@ -506,9 +425,6 @@ solve_h48( } - nsols = 0; - solutions_used = 0; - pthread_mutex_init(&solutions_mutex, NULL); maketasks_arg = (dfsarg_solve_h48_maketasks_t) { @@ -521,7 +437,7 @@ solve_h48( solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks); if (ntasks < 0) goto solve_h48_error_solutions_buffer; - if (*arg[0].nsols >= (int64_t)maxsolutions) + if (sollist.nsols >= maxsolutions) goto solve_h48_done; for (i = 0; i < threads; i++) { @@ -533,15 +449,14 @@ solve_h48( for ( d = MAX(minmoves, STARTING_MOVES + 1); - d <= maxmoves && nsols < (int64_t)maxsolutions - && !(nsols != 0 && d > shortest_sol + optimal); + !solutions_done(&sollist, &settings, d); d++ ) { if (d >= 10) LOG("Found %" PRId64 " solutions, searching at depth %" - PRId8 "\n", nsols, d); + PRId8 "\n", sollist.nsols, d); for (i = 0; i < threads; i++) { - arg[i].depth = d; + arg[i].target_depth = d; pthread_create( &thread[i], NULL, solve_h48_runthread, &arg[i]); } @@ -550,10 +465,6 @@ solve_h48( } solve_h48_done: - if (!appendchar(arg[0].solutions_size, *arg[0].solutions, - arg[0].solutions_used, '\0')) - goto solve_h48_error_solutions_buffer; - nodes_visited = table_lookups = table_fallbacks = 0; for (i = 0; i < threads; i++) { nodes_visited += arg[i].nodes_visited; @@ -573,7 +484,7 @@ solve_h48_done: LOG("Table fallbacks: %" PRId64 " (%.3Lf%%)\n", table_fallbacks, fallback_rate); - return nsols; + return sollist.nsols; solve_h48_error_data: LOG("solve_h48: error reading table\n"); diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h @@ -1,14 +1,217 @@ -#define MAXLEN 20 +STATIC void solution_moves_reset(solution_moves_t [static 1]); +STATIC void solution_moves_transform(solution_moves_t [static 1], uint8_t t); +STATIC bool solution_list_init( + solution_list_t [static 1], size_t n, char [n]); +STATIC bool solution_moves_equal( + const solution_moves_t [static 1], const solution_moves_t [static 1]); +STATIC bool solution_moves_is_duplicate(size_t n, const solution_moves_t[n]); +STATIC bool appendchar(solution_list_t [static 1], char); +STATIC int64_t appendsolution(const solution_moves_t [static 1], + const solution_settings_t [static 1], solution_list_t [static 1]); +STATIC bool solutions_done(const solution_list_t [static 1], + const solution_settings_t [static 1], int8_t depth); -STATIC bool appendchar(size_t n, char [n], size_t *, char); +STATIC void +solution_moves_reset(solution_moves_t sol[static 1]) +{ + sol->nmoves = 0; + sol->npremoves = 0; +} + +STATIC void +solution_moves_transform(solution_moves_t moves[static 1], uint8_t t) +{ + uint8_t i; + + for (i = 0; i < moves->nmoves; i++) + moves->moves[i] = transform_move(moves->moves[i], t); + + for (i = 0; i < moves->npremoves; i++) + moves->premoves[i] = transform_move(moves->premoves[i], t); +} STATIC bool -appendchar(size_t n, char s[n], size_t *used, char c) +solution_list_init(solution_list_t sols[static 1], size_t n, char buf[n]) { - if (n <= *used) + if (n == 0) { + LOG("Cannot use solution buffer with size 0\n"); return false; + } + + sols->nsols = 0; + sols->shortest_sol = MAXLEN + 1; + sols->size = n; + sols->used = 0; + sols->buf = buf; - s[(*used)++] = c; + /* Ensure string buffer is NULL-terminated */ + sols->buf[0] = '\0'; return true; } + +STATIC bool +solution_moves_equal( + const solution_moves_t a[static 1], + const solution_moves_t b[static 1] +) +{ + uint8_t i; + + if (a->nmoves != b->nmoves || a->npremoves != b->npremoves) + return false; + + for (i = 0; i < a->nmoves; i++) + if (a->moves[i] != b->moves[i]) + return false; + + for (i = 0; i < a->npremoves; i++) + if (a->premoves[i] != b->premoves[i]) + return false; + + return true; +} + +STATIC bool +solution_moves_is_duplicate(size_t r, const solution_moves_t s[r]) +{ + size_t i; + + for (i = 0; i < r; i++) + if (solution_moves_equal(&s[i], &s[r])) + return true; + + return false; +} + +STATIC bool +appendchar(solution_list_t solutions[static 1], char c) +{ + if (solutions->size <= solutions->used) + return false; + + solutions->buf[solutions->used++] = c; + + return true; +} + +STATIC int64_t +appendsolution( + const solution_moves_t moves[static 1], + const solution_settings_t settings[static 1], + solution_list_t list[static 1] +) +{ + int64_t r, strl; + int i; + uint8_t t; + solution_moves_t tsol[NTRANS]; + + if (moves->nmoves + moves->npremoves > MAXLEN) + goto appendsolution_error_solution_length; + + for ( + t = 0, r = 0; + t < NTRANS && list->nsols < settings->maxsolutions; + t++ + ) { + if (!(settings->tmask & TM_SINGLE(t))) + continue; + + tsol[r] = *moves; + if (settings->unniss) { + tsol[r].nmoves += moves->npremoves; + tsol[r].npremoves = 0; + for (i = moves->npremoves-1; i >= 0; i--) + tsol[r].moves[tsol[r].nmoves - i - 1] = + inverse_move(moves->premoves[i]); + + /* + This is a bit ugly: we have to sort now and then again + later, because the allowednext check would fail with + improperly sorted parallel moves, but then transforming + could swap the pairs the wrong way around. + TODO: maybe fix this + */ + sortparallel_moves(tsol[r].nmoves, tsol[r].moves); + + /* Check if unnissed premoves cancel with normal. */ + if (!allowedmoves(tsol[r].nmoves, tsol[r].moves)) + continue; + } + solution_moves_transform(&tsol[r], t); + sortparallel_moves(tsol[r].nmoves, tsol[r].moves); + sortparallel_moves(tsol[r].npremoves, tsol[r].premoves); + + /* Skip duplicates that may appear after transforming */ + if (solution_moves_is_duplicate(r, tsol)) + continue; + + /* Write moves on normal */ + strl = writemoves(tsol[r].nmoves, tsol[r].moves, + list->size - list->used, list->buf + list->used); + if (strl < 0) + goto appendsolution_error_buffer; + list->used += (size_t)(strl-1); + + /* Write moves on inverse with NISS notation */ + if (tsol[r].npremoves > 0) { + if (!appendchar(list, ' ')) + goto appendsolution_error_buffer; + if (!appendchar(list, '(')) + goto appendsolution_error_buffer; + + strl = writemoves(tsol[r].npremoves, tsol[r].premoves, + list->size - list->used, list->buf + list->used); + if (strl < 0) + goto appendsolution_error_buffer; + list->used += (size_t)(strl-1); + + if (!appendchar(list, ')')) + goto appendsolution_error_buffer; + } + + if (!appendchar(list, '\n')) + goto appendsolution_error_buffer; + + ++list->nsols; + list->shortest_sol = MIN( + list->shortest_sol, tsol[r].nmoves + tsol[r].npremoves); + r++; + } + + list->buf[list->used] = '\0'; + return r; + +appendsolution_error_buffer: + LOG("Could not append solution to buffer: size too small\n"); + list->buf[0] = '\0'; + return NISSY_ERROR_BUFFER_SIZE; + +appendsolution_error_solution_length: + LOG("Error: solution is too long (%" PRIu8 ").\n" + "This is a bug, please report it.\n", + moves->nmoves + moves->npremoves); + list->buf[0] = '\0'; + return NISSY_ERROR_UNKNOWN; +} + +STATIC bool +solutions_done( + const solution_list_t list[static 1], + const solution_settings_t settings[static 1], + int8_t depth +) +{ + if (list->nsols >= settings->maxsolutions) + return true; + + if (depth > settings->maxmoves) + return true; + + if (list->nsols > 0 && settings->optimal >= 0 && + depth > list->shortest_sol + settings->optimal) + return true; + + return false; +} diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h @@ -0,0 +1,24 @@ +#define MAXLEN 20 + +typedef struct { + uint8_t nmoves; + uint8_t moves[MAXLEN]; + uint8_t npremoves; + uint8_t premoves[MAXLEN]; +} solution_moves_t; + +typedef struct { + uint64_t tmask; + bool unniss; + uint8_t maxmoves; + uint64_t maxsolutions; + int8_t optimal; +} solution_settings_t; + +typedef struct { + _Atomic uint64_t nsols; + uint8_t shortest_sol; + size_t size; + size_t used; + char *buf; +} solution_list_t; diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h @@ -1,4 +1,6 @@ +#include "solutions_types_macros.h" #include "solutions.h" +#include "tables_types_macros.h" #include "tables.h" #include "h48/h48.h" #include "coord/coord.h" diff --git a/src/solvers/tables.h b/src/solvers/tables.h @@ -1,6 +1,3 @@ -/* Type definitions and macros are in a separate file for easier testing */ -#include "tables_types_macros.h" - STATIC uint64_t read_unaligned_u64(const char *); STATIC void write_unaligned_u64(char *, uint64_t); STATIC int64_t readtableinfo(uint64_t, const char *, tableinfo_t *); diff --git a/src/utils/constants.h b/src/utils/constants.h @@ -105,7 +105,7 @@ STATIC int64_t binomial[12][12] = { #define MM_SIDE(m) (UINT32_C(7) << (uint32_t)(m)) #define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF) -#define TM_SINGLE_UFr UINT64_C(1) +#define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t)) #define CORNER_UFR UINT8_C(0) #define CORNER_UBL UINT8_C(1) @@ -142,7 +142,7 @@ STATIC int64_t binomial[12][12] = { #define CTWIST_CW UINT8_C(0x20) #define CTWIST_CCW UINT8_C(0x40) #define EFLIP UINT8_C(0x10) -#define UINT8_ERROR UINT8_C(0xFF) +#define UINT8_ERROR UINT8_MAX STATIC const char *cornerstr[] = { [CORNER_UFR] = "UFR", diff --git a/test/032_invertmoves/001_onemove.in b/test/032_invertmoves/001_onemove.in @@ -1 +0,0 @@ -F diff --git a/test/032_invertmoves/001_onemove.out b/test/032_invertmoves/001_onemove.out @@ -1 +0,0 @@ -F' diff --git a/test/032_invertmoves/002_20moves.in b/test/032_invertmoves/002_20moves.in @@ -1 +0,0 @@ -B2 R D2 B2 R D2 F2 L2 F2 R' F2 D' L D2 L U2 L B2 F2 U diff --git a/test/032_invertmoves/002_20moves.out b/test/032_invertmoves/002_20moves.out @@ -1 +0,0 @@ -U' F2 B2 L' U2 L' D2 L' D F2 R F2 L2 F2 D2 R' B2 D2 R' B2 diff --git a/test/032_invertmoves/invertmoves_tests.c b/test/032_invertmoves/invertmoves_tests.c @@ -1,21 +0,0 @@ -#include "../test.h" - -#define MAXMOVES 20 - -int64_t readmoves(const char *, int, uint8_t *); -void writemoves(size_t n, uint8_t [n], size_t m, char [m]); -void invertmoves(size_t n, const uint8_t [n], uint8_t [n]); - -void run(void) { - char movestr[STRLENMAX], outstr[STRLENMAX]; - uint8_t moves[MAXMOVES], ret[MAXMOVES]; - int c; - - fgets(movestr, STRLENMAX, stdin); - c = readmoves(movestr, MAXMOVES, moves); - - invertmoves(c, moves, ret); - writemoves(c, ret, STRLENMAX, outstr); - - printf("%s\n", outstr); -} diff --git a/test/062_transform_move/transform_move_tests.c b/test/062_transform_move/transform_move_tests.c @@ -4,7 +4,7 @@ cube_t applytrans(cube_t, const char *); uint8_t transform_move(uint8_t, uint8_t); -int readmoves(const char *, int, uint8_t *); +int64_t readmoves(const char *, size_t n, uint8_t [n]); cube_t move(cube_t, uint8_t); cube_t applymoves(cube_t, const char *); uint8_t readtrans(const char[static NISSY_SIZE_TRANSFORMATION]); diff --git a/test/130_appendsolution/00_empty.in b/test/130_appendsolution/00_empty.in @@ -0,0 +1,5 @@ + + +0 +1 +rotation UF diff --git a/test/130_appendsolution/00_empty.out b/test/130_appendsolution/00_empty.out @@ -0,0 +1,4 @@ + +Number of solutions: 1 +Shortest solution length: 0 +Used bytes: 1 diff --git a/test/130_appendsolution/01_simple_onlynormal_nounniss.in b/test/130_appendsolution/01_simple_onlynormal_nounniss.in @@ -0,0 +1,5 @@ +U F R D2 B' + +0 +1 +rotation UF diff --git a/test/130_appendsolution/01_simple_onlynormal_nounniss.out b/test/130_appendsolution/01_simple_onlynormal_nounniss.out @@ -0,0 +1,4 @@ +U F R D2 B' +Number of solutions: 1 +Shortest solution length: 5 +Used bytes: 12 diff --git a/test/130_appendsolution/02_simple_onlynormal_nounnis_multitrans.in b/test/130_appendsolution/02_simple_onlynormal_nounnis_multitrans.in @@ -0,0 +1,8 @@ +U F R + +0 +4 +rotation UF +mirrored UR +rotation BD +mirrored LB diff --git a/test/130_appendsolution/02_simple_onlynormal_nounnis_multitrans.out b/test/130_appendsolution/02_simple_onlynormal_nounnis_multitrans.out @@ -0,0 +1,7 @@ +U F R +B D L +U' L' B' +R' B' D' +Number of solutions: 4 +Shortest solution length: 3 +Used bytes: 30 diff --git a/test/130_appendsolution/03_simple_unniss.in b/test/130_appendsolution/03_simple_unniss.in @@ -0,0 +1,5 @@ +U F B2 +R' F D +1 +1 +rotation UF diff --git a/test/130_appendsolution/03_simple_unniss.out b/test/130_appendsolution/03_simple_unniss.out @@ -0,0 +1,4 @@ +U F B2 D' F' R +Number of solutions: 1 +Shortest solution length: 6 +Used bytes: 15 diff --git a/test/130_appendsolution/04_niss_nounniss.in b/test/130_appendsolution/04_niss_nounniss.in @@ -0,0 +1,5 @@ +U F B2 +R' F D +0 +1 +rotation UF diff --git a/test/130_appendsolution/04_niss_nounniss.out b/test/130_appendsolution/04_niss_nounniss.out @@ -0,0 +1,4 @@ +U F B2 (R' F D) +Number of solutions: 1 +Shortest solution length: 6 +Used bytes: 16 diff --git a/test/130_appendsolution/05_sort_parallel.in b/test/130_appendsolution/05_sort_parallel.in @@ -0,0 +1,5 @@ +L R' B2 F + +0 +1 +rotation UF diff --git a/test/130_appendsolution/05_sort_parallel.out b/test/130_appendsolution/05_sort_parallel.out @@ -0,0 +1,4 @@ +R' L F B2 +Number of solutions: 1 +Shortest solution length: 4 +Used bytes: 10 diff --git a/test/130_appendsolution/06_unniss_trans_sort.in b/test/130_appendsolution/06_unniss_trans_sort.in @@ -0,0 +1,5 @@ +B +R2 F2 +1 +1 +rotation UR diff --git a/test/130_appendsolution/06_unniss_trans_sort.out b/test/130_appendsolution/06_unniss_trans_sort.out @@ -0,0 +1,4 @@ +R2 L B2 +Number of solutions: 1 +Shortest solution length: 3 +Used bytes: 8 diff --git a/test/130_appendsolution/07_unniss_cancel_nosol.in b/test/130_appendsolution/07_unniss_cancel_nosol.in @@ -0,0 +1,5 @@ +B' F +R2 B2 +1 +1 +rotation UF diff --git a/test/130_appendsolution/07_unniss_cancel_nosol.out b/test/130_appendsolution/07_unniss_cancel_nosol.out @@ -0,0 +1,3 @@ +Number of solutions: 0 +Shortest solution length: 21 +Used bytes: 0 diff --git a/test/130_appendsolution/08_unniss_cancel_nosol_v2.in b/test/130_appendsolution/08_unniss_cancel_nosol_v2.in @@ -0,0 +1,5 @@ +F' B +R2 F2 +1 +1 +rotation UF diff --git a/test/130_appendsolution/08_unniss_cancel_nosol_v2.out b/test/130_appendsolution/08_unniss_cancel_nosol_v2.out @@ -0,0 +1,3 @@ +Number of solutions: 0 +Shortest solution length: 21 +Used bytes: 0 diff --git a/test/130_appendsolution/appendsolution_tests.c b/test/130_appendsolution/appendsolution_tests.c @@ -0,0 +1,58 @@ +/* +Input format for appendsolution tests: + +moves on normal +moves on inverse (without parentheses) +unniss flag (0=false, 1=true) +number of transformations +transformations, one per line + +See below for the output format. +*/ + +#include "../test.h" + +uint8_t readtrans(const char [NISSY_SIZE_TRANSFORMATION]); +int64_t readmoves(const char *, size_t n, uint8_t [n]); +void solution_moves_reset(solution_moves_t [static 1]); +bool solution_list_init(solution_list_t [static 1], size_t n, char [n]); +int64_t appendsolution(const solution_moves_t [static 1], + const solution_settings_t [static 1], solution_list_t [static 1]); + +void run(void) { + int i, ntrans; + char str[STRLENMAX], buf[STRLENMAX]; + solution_moves_t moves; + solution_settings_t settings; + solution_list_t list; + + solution_moves_reset(&moves); + solution_list_init(&list, STRLENMAX, buf); + settings = (solution_settings_t) { + .tmask = UINT64_C(0), + .unniss = false, + .maxmoves = 20, + .maxsolutions = 100, + .optimal = -1, + }; + + fgets(str, STRLENMAX, stdin); + moves.nmoves = (uint8_t)readmoves(str, 20, moves.moves); + fgets(str, STRLENMAX, stdin); + moves.npremoves = (uint8_t)readmoves(str, 20, moves.premoves); + fgets(str, STRLENMAX, stdin); + settings.unniss = (bool)atoi(str); + fgets(str, STRLENMAX, stdin); + ntrans = atoi(str); + for (i = 0; i < ntrans; i++) { + fgets(str, STRLENMAX, stdin); + settings.tmask |= UINT64_C(1) << (uint64_t)readtrans(str); + } + + appendsolution(&moves, &settings, &list); + + printf("%s", list.buf); + printf("Number of solutions: %" PRIu64 "\n", list.nsols); + printf("Shortest solution length: %" PRIu8 "\n", list.shortest_sol); + printf("Used bytes: %zu\n", list.used); +} diff --git a/test/test.h b/test/test.h @@ -10,6 +10,7 @@ #include "../src/nissy.h" #include "../src/arch/arch.h" +#include "../src/solvers/solutions_types_macros.h" #include "../src/solvers/tables_types_macros.h" #include "../src/solvers/h48/coordinate_macros.h" #include "../src/solvers/h48/map_types_macros.h" diff --git a/tools/nissy_extra.h b/tools/nissy_extra.h @@ -6,6 +6,7 @@ for testing purposes only. #define STATIC static #define LOG printf +#include "../src/solvers/tables_types_macros.h" #include "../src/solvers/tables.h" size_t gendata_h48_derive(uint8_t, const void *, void *);