From d45e1595ec1cffeab83ac6602b748250b66bea03 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 24 Mar 2025 23:09:26 +0100 Subject: 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 --- src/solvers/h48/solve.h | 237 +++++++++++++++--------------------------------- 1 file changed, 74 insertions(+), 163 deletions(-) (limited to 'src/solvers/h48/solve.h') diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index f7565d5..dbd15bb 100644 --- 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"); -- cgit v1.3