Faster optimal solver.

This is a pretty big one, but unfortunately performance only improved by about 5%.
I implemented one of the main ideas of nxopt, that is switching to the
inverse scramble on the fly if it gives a lower branching factor.
On the one hand it makes sense that it does not have such a huge impact, since
it only rarely happens that we do have a lower branching factor on inverse, but
on the other hand I am quite sad that the improvement is barely noticeable :-(
Maybe the problem is that I have introduced a lot of new overhead and I can improve
that in the future. Or maybe I am just overlooking something stupid.

8 files changed, 616 insertions, 287 deletions

diff --git a/src/alg.c b/src/alg.c
index 4e96925..1158eba 100644
--- a/src/alg.c
+++ b/src/alg.c
@@ -373,3 +373,35 @@ realloc_alg(Alg *alg, int n)
         alg->allocated = n;
 }
 
+void
+swapmove(Move *m1, Move *m2)
+{
+        Move aux;
+
+        aux = *m1;
+        *m1 = *m2;
+        *m2 = aux;
+}
+
+void
+unniss(Alg *alg)
+{
+        int i;
+        Alg *aux;
+
+        aux = new_alg("");
+
+        for (i = 0; i < alg->len; i++)
+                if (!alg->inv[i])
+                        append_move(aux, alg->move[i], false);
+        
+        for (i = alg->len-1; i >= 0; i--)
+                if (alg->inv[i])
+                        append_move(aux, inverse_move(alg->move[i]), false);
+        
+        for (i = 0; i < alg->len; i++) {
+                alg->move[i] = aux->move[i];
+                alg->inv[i]  = false;
+        }
+        free(aux);
+}
diff --git a/src/alg.h b/src/alg.h
index 98900b4..f45b682 100644
--- a/src/alg.h
+++ b/src/alg.h
@@ -30,6 +30,8 @@ AlgList *   new_alglist();
 Alg *       on_inverse(Alg *alg);
 void        print_alg(Alg *alg, bool l);
 void        print_alglist(AlgList *al, bool l);
+void        swapmove(Move *m1, Move *m2);
+void        unniss(Alg *alg);
 
 #endif
 
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 9ec8620..3ad960b 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -81,9 +81,8 @@ typedef struct commandargs        CommandArgs;
 typedef struct coordinate         Coordinate;
 typedef struct cube               Cube;
 typedef struct cubearray          CubeArray;
-typedef struct dfsdata            DfsData;
+typedef struct dfsarg             DfsArg;
 typedef struct estimatedata       EstimateData;
-typedef struct localinfo          LocalInfo;
 typedef struct piecefilter        PieceFilter;
 typedef struct prunedata          PruneData;
 typedef struct solveoptions       SolveOptions;
@@ -94,7 +93,7 @@ typedef struct threaddatagenpt    ThreadDataGenpt;
 
 typedef Cube                 (*AntiIndexer)      (uint64_t);
 typedef bool                 (*Checker)          (Cube);
-typedef int                  (*Estimator)        (EstimateData *);
+typedef int                  (*Estimator)        (DfsArg *);
 typedef bool                 (*Validator)        (Alg *);
 typedef void                 (*Exec)             (CommandArgs *);
 typedef uint64_t             (*Indexer)          (Cube);
@@ -198,36 +197,31 @@ cubearray
 };
 
 struct
-dfsdata
+dfsarg
 {
+        Step *                    step;
+        SolveOptions *            opts;
+        Cube                      cube;
+        Cube                      inverse;
         int                       d;
-        int                       m;
-        int                       lb;
+        uint64_t                  badmoves;
+        uint64_t                  badmovesinv;
         bool                      niss;
         Move                      last1;
         Move                      last2;
+        Move                      last1inv;
+        Move                      last2inv;
         EstimateData *            ed;
         AlgList *                 sols;
         pthread_mutex_t *         sols_mutex;
         Alg *                     current_alg;
         Move *                    sorted_moves;
         int *                     move_position;
-        uint8_t *                 visited;
 };
 
 struct
 estimatedata
 {
-        Cube                      cube;
-        int                       target;
-        Move                      lastmove;
-        uint64_t                  movebitmask;
-        LocalInfo *               li;
-};
-
-struct
-localinfo
-{
         int                       corners;
         int                       normal_ud;
         int                       normal_fb;
@@ -235,7 +229,7 @@ localinfo
         int                       inverse_ud;
         int                       inverse_fb;
         int                       inverse_rl;
-        int                       prev_ret;
+        int                       oldret;
 };
 
 struct
@@ -284,6 +278,8 @@ step
 {
         char *                    shortname;
         char *                    name;
+        bool                      final;
+        Checker                   is_done;
         Estimator                 estimate;
         Checker                   ready;
         char *                    ready_msg;
diff --git a/src/solve.c b/src/solve.c
index ec16935..ea3b7ae 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -2,155 +2,208 @@
 
 /* Local functions ***********************************************************/
 
-static bool        allowed_next(Move move, DfsData *dd, uint64_t mm);
-static void        dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
-static void        dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd);
-static bool        dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd);
-static void        dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
-static bool        dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd);
+static bool        allowed_next(Move move, DfsArg *arg);
+static bool        cancel_niss(DfsArg *arg);
+static void        copy_dfsarg(DfsArg *src, DfsArg *dst);
+static void        dfs(DfsArg *arg);
+static void        dfs_branch(DfsArg *arg);
+static bool        dfs_check_solved(DfsArg *arg);
+static bool        dfs_switch_final(DfsArg *arg);
+static void        dfs_niss(DfsArg *arg);
+static bool        dfs_stop(DfsArg *arg);
 static void *      instance_thread(void *arg);
+static void        invert_branch(DfsArg *arg);
 static void        multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d);
+static bool        niss_makes_sense(DfsArg *arg);
 
 /* Local functions ***********************************************************/
 
 static bool
-allowed_next(Move move, DfsData *dd, uint64_t mm)
+allowed_next(Move m, DfsArg *arg)
 {
-        if ((1 << move) & mm)
+        if ((1 << m) & arg->badmoves)
                 return false;
 
-        if (!possible_next(dd->last2, dd->last1, move))
+        if (!possible_next(arg->last2, arg->last1, m))
                 return false;
 
-        if (commute(dd->last1, move))
-                return dd->move_position[dd->last1] < dd->move_position[move];
+        if (commute(arg->last1, m))
+                return arg->move_position[arg->last1] < arg->move_position[m];
 
         return true;
 }
 
+static bool
+cancel_niss(DfsArg *arg)
+{
+        return !possible_next(arg->last2, arg->last1, arg->last1inv) &&
+               !(commute(arg->last1inv, arg->last2inv) &&
+                 arg->last2inv != NULLMOVE &&
+                 possible_next(arg->last2, arg->last1, arg->last2inv));
+}
+
 static void
-dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+copy_dfsarg(DfsArg *src, DfsArg *dst)
 {
-        if (dfs_stop(c, s, opts, dd))
+        dst->step          = src->step;
+        dst->opts          = src->opts;
+        dst->cube          = src->cube;
+        dst->inverse       = src->inverse;
+        dst->d             = src->d;
+        dst->badmoves      = src->badmoves;
+        dst->badmovesinv   = src->badmovesinv;
+        dst->niss          = src->niss;
+        dst->last1         = src->last1;
+        dst->last2         = src->last2;
+        dst->last1inv      = src->last1inv;
+        dst->last2inv      = src->last2inv;
+        dst->sols          = src->sols;
+        dst->sols_mutex    = src->sols_mutex;
+        dst->current_alg   = src->current_alg;
+        dst->sorted_moves  = src->sorted_moves;
+        dst->move_position = src->move_position;
+
+        copy_estimatedata(src->ed, dst->ed);
+}
+
+static void
+dfs(DfsArg *arg)
+{
+        bool sw = false;
+
+        if (dfs_stop(arg))
                 return;
 
-        if (dfs_check_solved(s, opts, dd))
+        if (dfs_check_solved(arg))
                 return;
 
-        dfs_branch(c, s, opts, dd);
+        if (arg->step->final && (sw = dfs_switch_final(arg)))
+                invert_branch(arg);
+        dfs_branch(arg);
+
+        if (arg->opts->can_niss && !arg->niss && niss_makes_sense(arg))
+                dfs_niss(arg);
 
-        if (opts->can_niss && !dd->niss)
-                dfs_niss(c, s, opts, dd);
+        if (sw)
+                invert_branch(arg);
 }
 
 static void
-dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+dfs_branch(DfsArg *arg)
 {
-        bool b = false;
         int i;
-        uint64_t mm;
-        Move m, l1, l2;
-        LocalInfo li;
+        Move m;
+        DfsArg *newarg;
 
-        l1 = dd->last1;
-        l2 = dd->last2;
-        li = *(dd->ed->li);
-        mm = dd->ed->movebitmask;
+        newarg = malloc(sizeof(DfsArg));
+        newarg->ed = malloc(sizeof(EstimateData));
 
-        for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) {
-                if (b)
-                        break;
-                        
-                m = dd->sorted_moves[i];
-                if (allowed_next(m, dd, mm)) {
-                        dd->last2 = dd->last1;
-                        dd->last1 = m;
-                        append_move(dd->current_alg, m, dd->niss);
+        for (i = 0; arg->sorted_moves[i] != NULLMOVE; i++) {
+                m = arg->sorted_moves[i];
+                if (allowed_next(m, arg)) {
+                        copy_dfsarg(arg, newarg);
+                        newarg->last2 = arg->last1;
+                        newarg->last1 = m;
+                        newarg->cube  = apply_move(m, arg->cube);
+                        append_move(arg->current_alg, m, newarg->niss);
 
-                        dfs(apply_move(m, c), s, opts, dd);
+                        dfs(newarg);
 
-                        dd->current_alg->len--;
-                        dd->last2     = l2;
-                        dd->last1     = l1;
-                        *(dd->ed->li) = li;
+                        arg->current_alg->len--;
                 }
         }
+
+        free(newarg->ed);
+        free(newarg);
 }
 
 static bool
-dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
+dfs_check_solved(DfsArg *arg)
 {
-        if (dd->lb != 0)
+        if (!arg->step->is_done(arg->cube))
                 return false;
 
-        if (dd->current_alg->len == dd->d) {
-                if (s->is_valid(dd->current_alg) || opts->all) {
-                        pthread_mutex_lock(dd->sols_mutex);
-                        if (dd->sols->len < opts->max_solutions)
-                                append_alg(dd->sols, dd->current_alg);
-                        pthread_mutex_unlock(dd->sols_mutex);
+        if (arg->current_alg->len == arg->d) {
+                if ((arg->step->is_valid(arg->current_alg) || arg->opts->all)
+                    && (!arg->step->final || !cancel_niss(arg))) {
+                        pthread_mutex_lock(arg->sols_mutex);
+                        if (arg->sols->len < arg->opts->max_solutions)
+                                append_alg(arg->sols, arg->current_alg);
+                        pthread_mutex_unlock(arg->sols_mutex);
                 }
 
-                if (opts->verbose)
-                        print_alg(dd->current_alg, false);
+                if (arg->opts->verbose)
+                        print_alg(arg->current_alg, false);
         }
 
         return true;
 }
 
 static void
-dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+dfs_niss(DfsArg *arg)
 {
-        Move l1, l2;
-        EstimateData *ed;
-
-        l1 = dd->last1;
-        l2 = dd->last2;
+        DfsArg *newarg;
 
-        ed = malloc(sizeof(EstimateData));
-        ed->cube = apply_move(inverse_move(l1), (Cube){0});
-        ed->target = 1;
+        newarg = malloc(sizeof(DfsArg));
+        newarg->ed = malloc(sizeof(EstimateData));
 
-        if (dd->current_alg->len == 0 || s->estimate(ed)) {
-                dd->niss  = true;
-                dd->last1 = NULLMOVE;
-                dd->last2 = NULLMOVE;
+        copy_dfsarg(arg, newarg);
+        swapmove(&(newarg->last1), &(newarg->last1inv));
+        swapmove(&(newarg->last2), &(newarg->last2inv));
+        newarg->niss = !(arg->niss);
+        newarg->cube = inverse_cube(arg->cube);
 
-                dfs(inverse_cube(c), s, opts, dd);
+        dfs(newarg);
 
-                dd->last1 = l1;
-                dd->last2 = l2;
-                dd->niss  = false;
-        }
-
-        free(ed);
+        free(newarg->ed);
+        free(newarg);
 }
 
 static bool
-dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
+dfs_stop(DfsArg *arg)
 {
+        int lowerbound;
         bool b;
 
-        dd->ed->cube        = c;
-        dd->ed->target      = dd->d - dd->current_alg->len;
-        dd->ed->lastmove    = dd->last1;
-        dd->ed->movebitmask = 0;
-
-        dd->lb = s->estimate(dd->ed);
-        if (opts->can_niss && !dd->niss)
-                dd->lb = MIN(1, dd->lb);
+        lowerbound = arg->step->estimate(arg);
+        if (arg->opts->can_niss && !arg->niss)
+                lowerbound = MIN(1, lowerbound);
 
-        if (dd->current_alg->len + dd->lb > dd->d) {
+        if (arg->current_alg->len + lowerbound > arg->d) {
                  b = true;
         } else {
-                pthread_mutex_lock(dd->sols_mutex);
-                b = dd->sols->len >= opts->max_solutions;
-                pthread_mutex_unlock(dd->sols_mutex);
+                pthread_mutex_lock(arg->sols_mutex);
+                b = arg->sols->len >= arg->opts->max_solutions;
+                pthread_mutex_unlock(arg->sols_mutex);
         }
 
         return b;
 }
 
+static bool
+dfs_switch_final(DfsArg *arg)
+{
+        int i, bn, bi;
+
+        for (bn = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
+                if (allowed_next(arg->sorted_moves[i], arg))
+                        bn++;
+        
+        swapmove(&(arg->last1), &(arg->last1inv));
+        swapmove(&(arg->last2), &(arg->last2inv));
+        swapu64(&(arg->badmoves), &(arg->badmovesinv));
+
+        for (bi = 0, i = 0; arg->sorted_moves[i] != NULLMOVE; i++)
+                if (allowed_next(arg->sorted_moves[i], arg))
+                        bi++;
+        
+        swapmove(&(arg->last1), &(arg->last1inv));
+        swapmove(&(arg->last2), &(arg->last2inv));
+        swapu64(&(arg->badmoves), &(arg->badmovesinv));
+
+        return bi < bn;
+}
+
 static void *
 instance_thread(void *arg)
 {
@@ -158,7 +211,7 @@ instance_thread(void *arg)
         Cube c;
         ThreadDataSolve *td;
         AlgListNode *node;
-        DfsData dd;
+        DfsArg darg;
 
         td = (ThreadDataSolve *)arg;
 
@@ -179,34 +232,53 @@ instance_thread(void *arg)
                     apply_move(node->alg->move[0], inverse_cube(td->cube)) :
                     apply_move(node->alg->move[0], td->cube);
 
-                dd.d               = td->depth;
-                dd.m               = 1;
-                dd.niss            = node->alg->inv[0];
-                dd.lb              = -1;
-                dd.last1           = node->alg->move[0];
-                dd.last2           = NULLMOVE;
-                dd.sols            = td->sols;
-                dd.sols_mutex      = td->sols_mutex;
-                dd.current_alg     = new_alg("");
-                append_move(dd.current_alg, node->alg->move[0],
+                darg.step            = td->step;
+                darg.opts            = td->opts;
+                darg.cube            = c;
+                darg.d               = td->depth;
+                darg.niss            = node->alg->inv[0];
+                darg.last1           = node->alg->move[0];
+                darg.last2           = NULLMOVE;
+                darg.last1inv        = NULLMOVE;
+                darg.last2inv        = NULLMOVE;
+                darg.sols            = td->sols;
+                darg.sols_mutex      = td->sols_mutex;
+                darg.current_alg     = new_alg("");
+                append_move(darg.current_alg, node->alg->move[0],
                             node->alg->inv[0]);
-                dd.sorted_moves    = td->sorted_moves;
-                dd.move_position   = td->move_position;
-                dd.ed              = malloc(sizeof(EstimateData));
-                dd.ed->movebitmask = 0;
-                dd.ed->li          = new_localinfo();
+                darg.sorted_moves    = td->sorted_moves;
+                darg.move_position   = td->move_position;
+                darg.ed              = new_estimatedata();
+                darg.badmoves        = 0;
+                darg.badmovesinv     = 0;
 
-                dfs(c, td->step, td->opts, &dd);
+                dfs(&darg);
 
-                free_alg(dd.current_alg);
-                free_localinfo(dd.ed->li);
-                free(dd.ed);
+                free_alg(darg.current_alg);
+                free_estimatedata(darg.ed);
         }
 
         return NULL;
 }
 
 static void
+invert_branch(DfsArg *arg)
+{
+        Cube aux;
+
+        aux = arg->cube;
+        arg->cube = is_solved(arg->inverse) ?
+                    inverse_cube(arg->cube) : arg->inverse;
+        arg->inverse = aux;
+
+        swapu64(&(arg->badmoves), &(arg->badmovesinv));
+        arg->niss = !(arg->niss);
+        swapmove(&(arg->last1), &(arg->last1inv));
+        swapmove(&(arg->last2), &(arg->last2inv));
+        invert_estimatedata(arg->ed);
+}
+
+static void
 multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
 {
         int i, *move_position;
@@ -233,6 +305,8 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
 
         for (i = 0; sorted_moves[i] != NULLMOVE; i++) {
                 alg = new_alg("");
+                /* TODO: start on inverse also in case of final step
+                   and ed->sw true */
                 append_move(alg, sorted_moves[i], false);
                 append_alg(start, alg);
                 if (opts->can_niss) {
@@ -270,6 +344,15 @@ multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
         free(sorted_moves);
 }
 
+static bool
+niss_makes_sense(DfsArg *arg)
+{
+        Cube testcube;
+
+        testcube = apply_move(inverse_move(arg->last1), (Cube){0});
+        return arg->current_alg->len == 0 || arg->step->is_done(testcube);
+}
+
 /* Public functions **********************************************************/
 
 AlgList *
@@ -279,10 +362,8 @@ solve(Cube cube, Step *step, SolveOptions *opts)
         AlgList *sols;
         AlgListNode *node;
         Cube c;
-        EstimateData *ed;
-        bool b;
 
-        prepare_step(step, opts->nthreads);
+        prepare_step(step, opts);
 
         if (step->detect != NULL)
                 step->pre_trans = step->detect(cube);
@@ -296,19 +377,9 @@ solve(Cube cube, Step *step, SolveOptions *opts)
                 return sols;
         }
 
-        if (opts->min_moves == 0) {
-                ed = malloc(sizeof(EstimateData));
-                ed->cube = cube;
-                ed->target = 0;
-                ed->li = new_localinfo();
-                b = step->estimate(ed) == 0;
-                free_localinfo(ed->li);
-                free(ed);
-
-                if (b) {
-                        append_alg(sols, new_alg(""));
-                        return sols;
-                }
+        if (opts->min_moves == 0 && step->is_done(cube)) {
+                append_alg(sols, new_alg(""));
+                return sols;
         }
 
         for (d = opts->min_moves;
@@ -323,8 +394,11 @@ solve(Cube cube, Step *step, SolveOptions *opts)
                 multidfs(c, step, opts, sols, d);
         }
 
-        for (node = sols->first; node != NULL; node = node->next)
+        for (node = sols->first; node != NULL; node = node->next) {
                 transform_alg(inverse_trans(step->pre_trans), node->alg);
+                if (step->final)
+                        unniss(node->alg);
+        }
 
         return sols;
 }
diff --git a/src/steps.c b/src/steps.c
index abb2918..ccf33df 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -5,28 +5,37 @@
 /* Checkers, estimators and validators ***************************************/
 
 static bool             check_centers(Cube cube);
+static bool             check_coany_HTM(Cube cube);
+static bool             check_coud_HTM(Cube cube);
+static bool             check_coany_URF(Cube cube);
+static bool             check_coud_URF(Cube cube);
+static bool             check_corners_HTM(Cube cube);
+static bool             check_corners_URF(Cube cube);
+static bool             check_cornershtr(Cube cube);
+static bool             check_eoany(Cube cube);
 static bool             check_eofb(Cube cube);
+static bool             check_drany(Cube cube);
 static bool             check_drud(Cube cube);
 static bool             check_htr(Cube cube);
 
-static int              estimate_eoany_HTM(EstimateData *ed);
-static int              estimate_eofb_HTM(EstimateData *ed);
-static int              estimate_coany_HTM(EstimateData *ed);
-static int              estimate_coud_HTM(EstimateData *ed);
-static int              estimate_coany_URF(EstimateData *ed);
-static int              estimate_coud_URF(EstimateData *ed);
-static int              estimate_corners_HTM(EstimateData *ed);
-static int              estimate_cornershtr_HTM(EstimateData *ed);
-static int              estimate_corners_URF(EstimateData *ed);
-static int              estimate_cornershtr_URF(EstimateData *ed);
-static int              estimate_drany_HTM(EstimateData *ed);
-static int              estimate_drud_HTM(EstimateData *ed);
-static int              estimate_drud_eofb(EstimateData *ed);
-static int              estimate_dr_eofb(EstimateData *ed);
-static int              estimate_drudfin_drud(EstimateData *ed);
-static int              estimate_htr_drud(EstimateData *ed);
-static int              estimate_htrfin_htr(EstimateData *ed);
-static int              estimate_optimal_HTM(EstimateData *ed);
+static int              estimate_eoany_HTM(DfsArg *arg);
+static int              estimate_eofb_HTM(DfsArg *arg);
+static int              estimate_coany_HTM(DfsArg *arg);
+static int              estimate_coud_HTM(DfsArg *arg);
+static int              estimate_coany_URF(DfsArg *arg);
+static int              estimate_coud_URF(DfsArg *arg);
+static int              estimate_corners_HTM(DfsArg *arg);
+static int              estimate_cornershtr_HTM(DfsArg *arg);
+static int              estimate_corners_URF(DfsArg *arg);
+static int              estimate_cornershtr_URF(DfsArg *arg);
+static int              estimate_drany_HTM(DfsArg *arg);
+static int              estimate_drud_HTM(DfsArg *arg);
+static int              estimate_drud_eofb(DfsArg *arg);
+static int              estimate_dr_eofb(DfsArg *arg);
+static int              estimate_drudfin_drud(DfsArg *arg);
+static int              estimate_htr_drud(DfsArg *arg);
+static int              estimate_htrfin_htr(DfsArg *arg);
+static int              estimate_optimal_HTM(DfsArg *arg);
 
 static bool             always_valid(Alg *alg);
 static bool             validate_singlecw_ending(Alg *alg);
@@ -51,6 +60,8 @@ optimal_HTM = {
         .shortname = "optimal",
         .name      = "Optimal solve (in HTM)",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_optimal_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -69,6 +80,8 @@ eoany_HTM = {
         .shortname = "eo",
         .name      = "EO on any axis",
 
+        .final     = false,
+        .is_done   = check_eoany,
         .estimate  = estimate_eoany_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -86,6 +99,8 @@ eofb_HTM = {
         .shortname = "eofb",
         .name      = "EO on F/B",
 
+        .final     = false,
+        .is_done   = check_eofb,
         .estimate  = estimate_eofb_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -103,6 +118,8 @@ eorl_HTM = {
         .shortname = "eorl",
         .name      = "EO on R/L",
 
+        .final     = false,
+        .is_done   = check_eofb,
         .estimate  = estimate_eofb_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -120,6 +137,8 @@ eoud_HTM = {
         .shortname = "eoud",
         .name      = "EO on U/D",
 
+        .final     = false,
+        .is_done   = check_eofb,
         .estimate  = estimate_eofb_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -138,6 +157,8 @@ coany_HTM = {
         .shortname = "co",
         .name      = "CO on any axis",
 
+        .final     = false,
+        .is_done   = check_coany_HTM,
         .estimate  = estimate_coany_HTM,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -154,6 +175,8 @@ coud_HTM = {
         .shortname = "coud",
         .name      = "CO on U/D",
 
+        .final     = false,
+        .is_done   = check_coud_HTM,
         .estimate  = estimate_coud_HTM,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -170,6 +193,8 @@ corl_HTM = {
         .shortname = "corl",
         .name      = "CO on R/L",
 
+        .final     = false,
+        .is_done   = check_coud_HTM,
         .estimate  = estimate_coud_HTM,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -186,6 +211,8 @@ cofb_HTM = {
         .shortname = "cofb",
         .name      = "CO on F/B",
 
+        .final     = false,
+        .is_done   = check_coud_HTM,
         .estimate  = estimate_coud_HTM,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -202,6 +229,8 @@ coany_URF = {
         .shortname = "co-URF",
         .name      = "CO any axis (URF moveset)",
 
+        .final     = false,
+        .is_done   = check_coany_URF,
         .estimate  = estimate_coany_URF,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -218,6 +247,8 @@ coud_URF = {
         .shortname = "coud-URF",
         .name      = "CO on U/D (URF moveset)",
 
+        .final     = false,
+        .is_done   = check_coud_URF,
         .estimate  = estimate_coud_URF,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -234,6 +265,8 @@ corl_URF = {
         .shortname = "corl-URF",
         .name      = "CO on R/L (URF moveset)",
 
+        .final     = false,
+        .is_done   = check_coud_URF,
         .estimate  = estimate_coud_URF,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -250,6 +283,8 @@ cofb_URF = {
         .shortname = "cofb-URF",
         .name      = "CO on F/B (URF moveset)",
 
+        .final     = false,
+        .is_done   = check_coud_URF,
         .estimate  = estimate_coud_URF,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -267,6 +302,8 @@ cornershtr_HTM = {
         .shortname = "chtr",
         .name      = "Solve corners to HTR state",
 
+        .final     = false,
+        .is_done   = check_cornershtr,
         .estimate  = estimate_cornershtr_HTM,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -283,6 +320,8 @@ cornershtr_URF = {
         .shortname = "chtr-URF",
         .name      = "Solve corners to HTR state (URF moveset)",
 
+        .final     = false,
+        .is_done   = check_cornershtr,
         .estimate  = estimate_cornershtr_URF,
         .ready     = NULL,
         .is_valid  = validate_singlecw_ending,
@@ -299,6 +338,8 @@ corners_HTM = {
         .shortname = "corners",
         .name      = "Solve corners",
 
+        .final     = true,
+        .is_done   = check_corners_HTM,
         .estimate  = estimate_corners_HTM,
         .ready     = NULL,
         .is_valid  = always_valid,
@@ -315,6 +356,8 @@ corners_URF = {
         .shortname = "corners-URF",
         .name      = "Solve corners (URF moveset)",
 
+        .final     = true, /* TODO: check if this works with reorient */
+        .is_done   = check_corners_URF,
         .estimate  = estimate_corners_URF,
         .ready     = NULL,
         .is_valid  = always_valid,
@@ -332,6 +375,8 @@ drany_HTM = {
         .shortname = "dr",
         .name      = "DR on any axis",
 
+        .final     = false,
+        .is_done   = check_drany,
         .estimate  = estimate_drany_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -349,6 +394,8 @@ drud_HTM = {
         .shortname = "drud",
         .name      = "DR on U/D",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -366,6 +413,8 @@ drrl_HTM = {
         .shortname = "drrl",
         .name      = "DR on R/L",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -383,6 +432,8 @@ drfb_HTM = {
         .shortname = "drfb",
         .name      = "DR on F/B",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_HTM,
         .ready     = check_centers,
         .ready_msg = check_centers_msg,
@@ -401,6 +452,8 @@ dr_eo = {
         .shortname = "dr-eo",
         .name      = "DR without breaking EO (automatically detected)",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_dr_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -418,6 +471,8 @@ dr_eofb = {
         .shortname = "dr-eofb",
         .name      = "DR on U/D or R/L without breaking EO on F/B",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_dr_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -435,6 +490,8 @@ dr_eorl = {
         .shortname = "dr-eorl",
         .name      = "DR on U/D or F/B without breaking EO on R/L",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_dr_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -452,6 +509,8 @@ dr_eoud = {
         .shortname = "dr-eoud",
         .name      = "DR on R/L or F/B without breaking EO on U/D",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_dr_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -469,6 +528,8 @@ drud_eofb = {
         .shortname = "drud-eofb",
         .name      = "DR on U/D without breaking EO on F/B",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -486,6 +547,8 @@ drrl_eofb = {
         .shortname = "drrl-eofb",
         .name      = "DR on R/L without breaking EO on F/B",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -503,6 +566,8 @@ drud_eorl = {
         .shortname = "drud-eorl",
         .name      = "DR on U/D without breaking EO on R/L",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -520,6 +585,8 @@ drfb_eorl = {
         .shortname = "drfb-eorl",
         .name      = "DR on F/B without breaking EO on R/L",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -537,6 +604,8 @@ drfb_eoud = {
         .shortname = "drfb-eoud",
         .name      = "DR on F/B without breaking EO on U/D",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -554,6 +623,8 @@ drrl_eoud = {
         .shortname = "drrl-eoud",
         .name      = "DR on R/L without breaking EO on U/D",
 
+        .final     = false,
+        .is_done   = check_drud,
         .estimate  = estimate_drud_eofb,
         .ready     = check_eofb,
         .ready_msg = check_eo_msg,
@@ -572,6 +643,8 @@ dranyfin_DR = {
         .shortname = "drfin",
         .name      = "DR finish on any axis without breaking DR",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_drudfin_drud,
         .ready     = check_drud,
         .ready_msg = check_drany_msg,
@@ -589,6 +662,8 @@ drudfin_drud = {
         .shortname = "drudfin",
         .name      = "DR finish on U/D without breaking DR",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_drudfin_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -606,6 +681,8 @@ drrlfin_drrl = {
         .shortname = "drrlfin",
         .name      = "DR finish on R/L without breaking DR",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_drudfin_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -623,6 +700,8 @@ drfbfin_drfb = {
         .shortname = "drfbfin",
         .name      = "DR finish on F/B without breaking DR",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_drudfin_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -641,6 +720,8 @@ htr_any = {
         .shortname = "htr",
         .name      = "HTR from DR",
 
+        .final     = false,
+        .is_done   = check_htr,
         .estimate  = estimate_htr_drud,
         .ready     = check_drud,
         .ready_msg = check_drany_msg,
@@ -658,6 +739,8 @@ htr_drud = {
         .shortname = "htr-drud",
         .name      = "HTR from DR on U/D",
 
+        .final     = false,
+        .is_done   = check_htr,
         .estimate  = estimate_htr_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -675,6 +758,8 @@ htr_drrl = {
         .shortname = "htr-drrl",
         .name      = "HTR from DR on R/L",
 
+        .final     = false,
+        .is_done   = check_htr,
         .estimate  = estimate_htr_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -692,6 +777,8 @@ htr_drfb = {
         .shortname = "htr-drfb",
         .name      = "HTR from DR on F/B",
 
+        .final     = false,
+        .is_done   = check_htr,
         .estimate  = estimate_htr_drud,
         .ready     = check_drud,
         .ready_msg = check_dr_msg,
@@ -710,6 +797,8 @@ htrfin_htr = {
         .shortname = "htrfin",
         .name      = "HTR finish without breaking HTR",
 
+        .final     = true,
+        .is_done   = is_solved,
         .estimate  = estimate_htrfin_htr,
         .ready     = check_htr,
         .ready_msg = check_htr_msg,
@@ -783,12 +872,89 @@ check_centers(Cube cube)
 }
 
 static bool
+check_coany_HTM(Cube cube)
+{
+        return cube.cofb == 0 || cube.corl == 0 || cube.coud == 0;
+}
+
+static bool
+check_coud_HTM(Cube cube)
+{
+        return cube.coud == 0;
+}
+
+static bool
+check_coany_URF(Cube cube)
+{
+        Cube c2, c3;
+
+        c2 = apply_move(y, apply_move(z, cube));
+        c3 = apply_move(y, apply_move(x, cube));
+
+        return check_coany_HTM(cube) ||
+               check_coany_HTM(c2)   ||
+               check_coany_HTM(c3);
+}
+
+static bool
+check_coud_URF(Cube cube)
+{
+        Cube c2, c3;
+
+        c2 = apply_move(z, cube);
+        c3 = apply_move(x, cube);
+
+        return cube.coud == 0 || c2.coud == 0 || c3.coud == 0;
+}
+
+static bool
+check_corners_URF(Cube cube)
+{
+        Cube c;
+        Trans i;
+
+        for (i = 0; i < NROTATIONS; i++) {
+                c = apply_alg(rotation_alg(i), cube);
+                if (c.cp && c.coud)
+                        return true;
+        }
+
+        return false;
+}
+
+static bool
+check_corners_HTM(Cube cube)
+{
+        return cube.cp == 0 && cube.coud == 0;
+}
+
+static bool
+check_cornershtr(Cube cube)
+{
+        return coord_cornershtr.index(cube) == 0;
+}
+
+static bool
+check_eoany(Cube cube)
+{
+        return cube.eofb == 0 || cube.eorl == 0 || cube.eoud == 0;
+}
+
+static bool
 check_eofb(Cube cube)
 {
         return cube.eofb == 0;
 }
 
 static bool
+check_drany(Cube cube)
+{
+        return (cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0) ||
+               (cube.eorl == 0 && cube.eoud == 0 && cube.cofb == 0) ||
+               (cube.eoud == 0 && cube.eofb == 0 && cube.corl == 0);
+}
+
+static bool
 check_drud(Cube cube)
 {
         return cube.eofb == 0 && cube.eorl == 0 && cube.coud == 0;
@@ -801,265 +967,283 @@ check_htr(Cube cube)
 }
 
 static int
-estimate_eoany_HTM(EstimateData *ed)
+estimate_eoany_HTM(DfsArg *arg)
 {
         int r1, r2, r3;
 
-        r1 = ptableval(&pd_eofb_HTM, ed->cube);
-        r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, ed->cube));
-        r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, ed->cube));
+        r1 = ptableval(&pd_eofb_HTM, arg->cube);
+        r2 = ptableval(&pd_eofb_HTM, apply_trans(ur, arg->cube));
+        r3 = ptableval(&pd_eofb_HTM, apply_trans(fd, arg->cube));
 
         return MIN(r1, MIN(r2, r3));
 }
 
 static int
-estimate_eofb_HTM(EstimateData *ed)
+estimate_eofb_HTM(DfsArg *arg)
 {
-        return ptableval(&pd_eofb_HTM, ed->cube);
+        return ptableval(&pd_eofb_HTM, arg->cube);
 }
 
 static int
-estimate_coany_HTM(EstimateData *ed)
+estimate_coany_HTM(DfsArg *arg)
 {
         int r1, r2, r3;
 
-        r1 = ptableval(&pd_coud_HTM, ed->cube);
-        r2 = ptableval(&pd_coud_HTM, apply_trans(rf, ed->cube));
-        r3 = ptableval(&pd_coud_HTM, apply_trans(fd, ed->cube));
+        r1 = ptableval(&pd_coud_HTM, arg->cube);
+        r2 = ptableval(&pd_coud_HTM, apply_trans(rf, arg->cube));
+        r3 = ptableval(&pd_coud_HTM, apply_trans(fd, arg->cube));
 
         return MIN(r1, MIN(r2, r3));
 }
 
 static int
-estimate_coud_HTM(EstimateData *ed)
+estimate_coud_HTM(DfsArg *arg)
 {
-        return ptableval(&pd_coud_HTM, ed->cube);
+        return ptableval(&pd_coud_HTM, arg->cube);
 }
 
 static int
-estimate_coany_URF(EstimateData *ed)
+estimate_coany_URF(DfsArg *arg)
 {
         int r1, r2, r3;
-        EstimateData *ed2, *ed3;
+        Cube c;
 
-        ed2 = malloc(sizeof(EstimateData));
-        ed3 = malloc(sizeof(EstimateData));
+        c = arg->cube;
 
-        ed2->cube = apply_trans(rf, ed->cube);
-        ed2->target = ed->target;
+        r1 = estimate_coud_URF(arg);
+        arg->cube = apply_trans(rf, c);
+        r2 = estimate_coud_URF(arg);
+        arg->cube = apply_trans(fd, c);
+        r3 = estimate_coud_URF(arg);
 
-        ed3->cube = apply_trans(fd, ed->cube);
-        ed3->target = ed->target;
-
-        r1 = estimate_coud_URF(ed);
-        r2 = estimate_coud_URF(ed2);
-        r3 = estimate_coud_URF(ed3);
-
-        free(ed2);
-        free(ed3);
+        arg->cube = c;
 
         return MIN(r1, MIN(r2, r3));
 }
 
 static int
-estimate_coud_URF(EstimateData *ed)
+estimate_coud_URF(DfsArg *arg)
 {
         /* TODO: I can improve this by checking first the orientation of
          * the corner in DBL and use that as a reference */
 
-        EstimateData *ed2, *ed3;
-
-        ed2 = malloc(sizeof(EstimateData));
-        ed2->cube = apply_move(z, ed->cube);
-        ed2->target = ed->target;
+        Cube c;
 
-        ed3 = malloc(sizeof(EstimateData));
-        ed3->cube = apply_move(x, ed->cube);
-        ed3->target = ed->target;
+        c = arg->cube;
 
-        int ud = estimate_coud_HTM(ed);
-        int rl = estimate_coud_HTM(ed2);
-        int fb = estimate_coud_HTM(ed3);
+        int ud = estimate_coud_HTM(arg);
+        arg->cube = apply_move(z, c);
+        int rl = estimate_coud_HTM(arg);
+        arg->cube = apply_move(x, c);
+        int fb = estimate_coud_HTM(arg);
 
-        free(ed2);
-        free(ed3);
+        arg->cube = c;
 
         return MIN(ud, MIN(rl, fb));
 }
 
 static int
-estimate_corners_HTM(EstimateData *ed)
+estimate_corners_HTM(DfsArg *arg)
 {
-        return ptableval(&pd_corners_HTM, ed->cube);
+        return ptableval(&pd_corners_HTM, arg->cube);
 }
 
 static int
-estimate_cornershtr_HTM(EstimateData *ed)
+estimate_cornershtr_HTM(DfsArg *arg)
 {
-        return ptableval(&pd_cornershtr_HTM, ed->cube);
+        return ptableval(&pd_cornershtr_HTM, arg->cube);
 }
 
 static int
-estimate_cornershtr_URF(EstimateData *ed)
+estimate_cornershtr_URF(DfsArg *arg)
 {
         /* TODO: I can improve this by checking first the corner in DBL
          * and use that as a reference */
 
-        int c, ret = 15;
+        int ret;
+        Cube c;
         Trans i;
 
+        c = arg->cube;
+        ret = 15;
+
         for (i = 0; i < NROTATIONS; i++) {
-                ed->cube = apply_alg(rotation_alg(i), ed->cube);
-                c = estimate_cornershtr_HTM(ed);
-                ret = MIN(ret, c);
+                arg->cube = apply_alg(rotation_alg(i), c);
+                ret = MIN(ret, estimate_cornershtr_HTM(arg));
         }
 
+        arg->cube = c;
+
         return ret;
 }
 
 static int
-estimate_corners_URF(EstimateData *ed)
+estimate_corners_URF(DfsArg *arg)
 {
         /* TODO: I can improve this by checking first the corner in DBL
          * and use that as a reference */
 
-        int c, ret = 15;
+        int ret;
+        Cube c;
         Trans i;
 
+        c = arg->cube;
+        ret = 15;
+
         for (i = 0; i < NROTATIONS; i++) {
-                ed->cube = apply_alg(rotation_alg(i), ed->cube);
-                c = estimate_corners_HTM(ed);
-                ret = MIN(ret, c);
+                arg->cube = apply_alg(rotation_alg(i), c);
+                ret = MIN(ret, estimate_corners_HTM(arg));
         }
 
+        arg->cube = c;
+
         return ret;
 }
 
 static int
-estimate_drany_HTM(EstimateData *ed)
+estimate_drany_HTM(DfsArg *arg)
 {
         int r1, r2, r3;
 
-        r1 = ptableval(&pd_drud_sym16_HTM, ed->cube);
-        r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, ed->cube));
-        r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, ed->cube));
+        r1 = ptableval(&pd_drud_sym16_HTM, arg->cube);
+        r2 = ptableval(&pd_drud_sym16_HTM, apply_trans(rf, arg->cube));
+        r3 = ptableval(&pd_drud_sym16_HTM, apply_trans(fd, arg->cube));
 
         return MIN(r1, MIN(r2, r3));
 }
 
 static int
-estimate_drud_HTM(EstimateData *ed)
+estimate_drud_HTM(DfsArg *arg)
 {
-        return ptableval(&pd_drud_sym16_HTM, ed->cube);
+        return ptableval(&pd_drud_sym16_HTM, arg->cube);
 }
 
 static int
-estimate_drud_eofb(EstimateData *ed)
+estimate_drud_eofb(DfsArg *arg)
 {
-        return ptableval(&pd_drud_eofb, ed->cube);
+        return ptableval(&pd_drud_eofb, arg->cube);
 }
 
 static int
-estimate_dr_eofb(EstimateData *ed)
+estimate_dr_eofb(DfsArg *arg)
 {
         int r1, r2;
 
-        r1 = ptableval(&pd_drud_eofb, ed->cube);
-        r2 = ptableval(&pd_drud_eofb, apply_trans(rf, ed->cube));
+        r1 = ptableval(&pd_drud_eofb, arg->cube);
+        r2 = ptableval(&pd_drud_eofb, apply_trans(rf, arg->cube));
 
         return MIN(r1, r2);
 }
 
 static int
-estimate_drudfin_drud(EstimateData *ed)
+estimate_drudfin_drud(DfsArg *arg)
 {
-        int val = ptableval(&pd_drudfin_noE_sym16_drud, ed->cube);
+        int val = ptableval(&pd_drudfin_noE_sym16_drud, arg->cube);
 
         if (val != 0)
                 return val;
 
-        return ed->cube.epose % 24 == 0 ? 0 : 1;
+        return arg->cube.epose % 24 == 0 ? 0 : 1;
 }
 
 static int
-estimate_htr_drud(EstimateData *ed)
+estimate_htr_drud(DfsArg *arg)
 {
-        return ptableval(&pd_htr_drud, ed->cube);
+        return ptableval(&pd_htr_drud, arg->cube);
 }
 
 static int
-estimate_htrfin_htr(EstimateData *ed)
+estimate_htrfin_htr(DfsArg *arg)
 {
-        return ptableval(&pd_htrfin_htr, ed->cube);
+        return ptableval(&pd_htrfin_htr, arg->cube);
 }
 
 static int
-estimate_optimal_HTM(EstimateData *ed)
+estimate_optimal_HTM(DfsArg *arg)
 {
-        int ret = -1;
+        int target, ret;
         Move lbase;
-        Cube cubeaux, inv;
+        Cube aux;
 
-        ed->li->corners = ptableval(&pd_corners_HTM, ed->cube);
-        UPDATECHECKSTOP(ret, ed->li->corners, ed->target);
+        target = arg->d - arg->current_alg->len;
+        ret = -1;
+        arg->inverse = (Cube){0};
+        arg->badmovesinv = 0;
+        arg->badmoves = 0;
 
-        ed->li->normal_ud = ptableval(&pd_khuge_HTM, ed->cube);
-        UPDATECHECKSTOP(ret, ed->li->normal_ud, ed->target);
+        arg->ed->corners = ptableval(&pd_corners_HTM, arg->cube);
+        UPDATECHECKSTOP(ret, arg->ed->corners, target);
 
-        cubeaux = apply_trans(fd, ed->cube);
-        ed->li->normal_fb = ptableval(&pd_khuge_HTM, cubeaux);
-        UPDATECHECKSTOP(ret, ed->li->normal_fb, ed->target);
+        arg->ed->normal_ud = ptableval(&pd_khuge_HTM, arg->cube);
+        UPDATECHECKSTOP(ret, arg->ed->normal_ud, target);
+        if (arg->ed->normal_ud == target) {
+                arg->badmovesinv |= (1<<U) | (1<<U2) | (1<<U3) |
+                                    (1<<D) | (1<<D2) | (1<<D3);
+        }
 
-        cubeaux = apply_trans(rf, ed->cube);
-        ed->li->normal_rl = ptableval(&pd_khuge_HTM, cubeaux);
-        UPDATECHECKSTOP(ret, ed->li->normal_rl, ed->target);
+        aux = apply_trans(fd, arg->cube);
+        arg->ed->normal_fb = ptableval(&pd_khuge_HTM, aux);
+        UPDATECHECKSTOP(ret, arg->ed->normal_fb, target);
+        if (arg->ed->normal_fb == target) {
+                arg->badmovesinv |= (1<<F) | (1<<F2) | (1<<F3) |
+                                    (1<<B) | (1<<B2) | (1<<B3);
+        }
+
+        aux = apply_trans(rf, arg->cube);
+        arg->ed->normal_rl = ptableval(&pd_khuge_HTM, aux);
+        UPDATECHECKSTOP(ret, arg->ed->normal_rl, target);
+        if (arg->ed->normal_rl == target) {
+                arg->badmovesinv |= (1<<R) | (1<<R2) | (1<<R3) |
+                                    (1<<L) | (1<<L2) | (1<<L3);
+        }
 
         if (ret == 0)
                 return ret;
 
-        if (ed->li->normal_ud == ed->li->normal_fb &&
-            ed->li->normal_fb == ed->li->normal_rl)
-                UPDATECHECKSTOP(ret, ed->li->normal_ud + 1, ed->target);
+        if (arg->ed->normal_ud == arg->ed->normal_fb &&
+            arg->ed->normal_fb == arg->ed->normal_rl)
+                UPDATECHECKSTOP(ret, arg->ed->normal_ud + 1, target);
 
         /* TODO: avoid computation of inverse if unnecessary */
-        lbase = base_move(ed->lastmove);
-        inv = inverse_cube(ed->cube);
+        lbase = base_move(arg->last1);
+        arg->inverse = inverse_cube(arg->cube);
 
-        if ((lbase != U && lbase != D) ||
-            (ed->li->inverse_ud == -1)) {
-                ed->li->inverse_ud = ptableval(&pd_khuge_HTM, inv);
+        if ((lbase != U && lbase != D) || (arg->ed->inverse_ud == -1)) {
+                arg->ed->inverse_ud = ptableval(&pd_khuge_HTM, arg->inverse);
         }
-        UPDATECHECKSTOP(ret, ed->li->inverse_ud, ed->target);
+        UPDATECHECKSTOP(ret, arg->ed->inverse_ud, target);
 
-        if ((lbase != F && lbase != B) ||
-            (ed->li->inverse_fb == -1)) {
-                cubeaux = apply_trans(fd, inv);
-                ed->li->inverse_fb = ptableval(&pd_khuge_HTM, cubeaux);
+        if ((lbase != F && lbase != B) || (arg->ed->inverse_fb == -1)) {
+                aux = apply_trans(fd, arg->inverse);
+                arg->ed->inverse_fb = ptableval(&pd_khuge_HTM, aux);
         }
-        UPDATECHECKSTOP(ret, ed->li->inverse_fb, ed->target);
+        UPDATECHECKSTOP(ret, arg->ed->inverse_fb, target);
 
-        if ((lbase != R && lbase != L) ||
-            (ed->li->inverse_rl == -1)) {
-                cubeaux = apply_trans(rf, inv);
-                ed->li->inverse_rl = ptableval(&pd_khuge_HTM, cubeaux);
+        if ((lbase != R && lbase != L) || (arg->ed->inverse_rl == -1)) {
+                aux = apply_trans(rf, arg->inverse);
+                arg->ed->inverse_rl = ptableval(&pd_khuge_HTM, aux);
         }
-        UPDATECHECKSTOP(ret, ed->li->inverse_rl, ed->target);
+        UPDATECHECKSTOP(ret, arg->ed->inverse_rl, target);
 
-        if (ed->li->inverse_ud == ed->li->inverse_fb &&
-            ed->li->inverse_fb == ed->li->inverse_rl)
-                UPDATECHECKSTOP(ret, ed->li->inverse_ud + 1, ed->target);
+        if (arg->ed->inverse_ud == arg->ed->inverse_fb &&
+            arg->ed->inverse_fb == arg->ed->inverse_rl) {
+                UPDATECHECKSTOP(ret, arg->ed->inverse_ud + 1, target);
+        }
 
-        if (ed->li->inverse_ud == ed->target)
-                ed->movebitmask |= (1<<U) | (1<<U2) | (1<<U3) |
-                                   (1<<D) | (1<<D2) | (1<<D3);
-        if (ed->li->inverse_fb == ed->target)
-                ed->movebitmask |= (1<<F) | (1<<F2) | (1<<F3) |
-                                   (1<<B) | (1<<B2) | (1<<B3);
-        if (ed->li->inverse_rl == ed->target)
-                ed->movebitmask |= (1<<R) | (1<<R2) | (1<<R3) |
-                                   (1<<L) | (1<<L2) | (1<<L3);
+        if (arg->ed->inverse_ud == target) {
+                arg->badmoves |= (1<<U) | (1<<U2) | (1<<U3) |
+                                 (1<<D) | (1<<D2) | (1<<D3);
+        }
+        if (arg->ed->inverse_fb == target) {
+                arg->badmoves |= (1<<F) | (1<<F2) | (1<<F3) |
+                                 (1<<B) | (1<<B2) | (1<<B3);
+        }
+        if (arg->ed->inverse_rl == target) {
+                arg->badmoves |= (1<<R) | (1<<R2) | (1<<R3) |
+                                 (1<<L) | (1<<L2) | (1<<L3);
+        }
 
-        return ret;
+        return arg->ed->oldret = ret;
 }
 
 static bool
@@ -1120,15 +1304,36 @@ detect_pretrans_drud(Cube cube)
 /* Public functions **********************************************************/
 
 void
-free_localinfo(LocalInfo *li)
+copy_estimatedata(EstimateData *src, EstimateData *dst)
 {
-        free(li);
+        dst->corners    = src->corners;
+        dst->normal_ud  = src->normal_ud;
+        dst->normal_fb  = src->normal_fb;
+        dst->normal_rl  = src->normal_rl;
+        dst->inverse_ud = src->inverse_ud;
+        dst->inverse_fb = src->inverse_fb;
+        dst->inverse_rl = src->inverse_rl;
+        dst->oldret     = src->oldret;
 }
 
-LocalInfo *
-new_localinfo()
+void
+free_estimatedata(EstimateData *ed)
 {
-        LocalInfo *ret = malloc(sizeof(LocalInfo));
+        free(ed);
+}
+
+void
+invert_estimatedata(EstimateData *ed)
+{
+        swap(&(ed->normal_ud), &(ed->inverse_ud));
+        swap(&(ed->normal_fb), &(ed->inverse_fb));
+        swap(&(ed->normal_rl), &(ed->inverse_rl));
+}
+
+EstimateData *
+new_estimatedata()
+{
+        EstimateData *ret = malloc(sizeof(EstimateData));
 
         ret->corners    = -1;
         ret->normal_ud  = -1;
@@ -1137,16 +1342,22 @@ new_localinfo()
         ret->inverse_ud = -1;
         ret->inverse_fb = -1;
         ret->inverse_rl = -1;
-        ret->prev_ret   = -1;
+        ret->oldret     = -1;
 
         return ret;
 }
 
 void
-prepare_step(Step *step, int nthreads)
+prepare_step(Step *step, SolveOptions *opts)
 {
         int i;
 
+        if (step->final && opts->can_niss) {
+                opts->can_niss = false;
+                fprintf(stderr, "Step if final, niss not used"
+                                "(-n ignored)\n");
+        }
+
         for (i = 0; i < step->ntables; i++)
-                genptable(step->tables[i], nthreads);
+                genptable(step->tables[i], opts->nthreads);
 }
diff --git a/src/steps.h b/src/steps.h
index e145c64..a55a101 100644
--- a/src/steps.h
+++ b/src/steps.h
@@ -7,8 +7,10 @@
 
 extern Step *           steps[NSTEPS];
 
-void                    free_localinfo(LocalInfo *li);
-LocalInfo *             new_localinfo();
-void                    prepare_step(Step *step, int nthreads);
+void                    copy_estimatedata(EstimateData *s, EstimateData *d);
+void                    free_estimatedata(EstimateData *ed);
+void                    invert_estimatedata(EstimateData *ed);
+EstimateData *          new_estimatedata();
+void                    prepare_step(Step *step, SolveOptions *opts);
 
 #endif
diff --git a/src/utils.c b/src/utils.c
index 1c829c4..e0d3268 100644
--- a/src/utils.c
+++ b/src/utils.c
@@ -272,7 +272,17 @@ swap(int *a, int *b)
         int aux;
 
         aux = *a;
-        *a = *b;
-        *b = aux;
+        *a  = *b;
+        *b  = aux;
+}
+
+void
+swapu64(uint64_t *a, uint64_t *b)
+{
+        uint64_t aux;
+
+        aux = *a;
+        *a  = *b;
+        *b  = aux;
 }
 
diff --git a/src/utils.h b/src/utils.h
index 80c33ae..9ba228d 100644
--- a/src/utils.h
+++ b/src/utils.h
@@ -2,6 +2,7 @@
 #define UTILS_H
 
 #include <stdbool.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -37,5 +38,6 @@ int         powint(int a, int b);
 int         subset_to_index(int *a, int n, int k);
 void        sum_arrays_mod(int *src, int *dst, int n, int m);
 void        swap(int *a, int *b);
+void        swapu64(uint64_t *a, uint64_t *b);
 
 #endif