1 files changed, 74 insertions, 163 deletions

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");