6 files changed, 333 insertions, 150 deletions

diff --git a/src/commands.c b/src/commands.c
index 10e4eb8..b089a1c 100644
--- a/src/commands.c
+++ b/src/commands.c
@@ -28,7 +28,7 @@ Command
 solve_cmd = {
         .name        = "solve",
         .usage       = "solve STEP [OPTIONS] SCRAMBLE",
-        .description = "Solve a step",
+        .description = "Solve a step; see command steps for a list of steps",
         .parse_args  = solve_parse_args,
         .exec        = solve_exec
 };
@@ -116,6 +116,7 @@ solve_parse_args(int c, char **v)
         a->opts->min_moves     = 0;
         a->opts->max_moves     = 20;
         a->opts->max_solutions = 1;
+        a->opts->nthreads      = 1;
         a->opts->optimal_only  = false;
         a->opts->can_niss      = false;
         a->opts->verbose       = false;
@@ -127,7 +128,8 @@ solve_parse_args(int c, char **v)
                         val = strtol(v[++i], NULL, 10);
                         if (val < 0 || val > 100) {
                                 fprintf(stderr,
-                                        "Invalid min number of moves.\n");
+                                        "Invalid min number of moves"
+                                        "(0 <= m <= 100).\n");
                                 return a;
                         }
                         a->opts->min_moves = val;
@@ -135,10 +137,20 @@ solve_parse_args(int c, char **v)
                         val = strtol(v[++i], NULL, 10);
                         if (val < 0 || val > 100) {
                                 fprintf(stderr,
-                                        "Invalid max number of moves.\n");
+                                        "Invalid max number of moves"
+                                        "(0 <= M <= 100).\n");
                                 return a;
                         }
                         a->opts->max_moves = val;
+                } else if (!strcmp(v[i], "-t")) {
+                        val = strtol(v[++i], NULL, 10);
+                        if (val < 1 || val > 64) {
+                                fprintf(stderr,
+                                        "Invalid number of threads."
+                                        "1 <= t <= 64\n");
+                                return a;
+                        }
+                        a->opts->nthreads = val;
                 } else if (!strcmp(v[i], "-s")) {
                         val = strtol(v[++i], NULL, 10);
                         if (val < 1 || val > 1000000) {
@@ -255,11 +267,19 @@ print_exec(CommandArgs *args)
 static void
 help_exec(CommandArgs *args)
 {
-        /* TODO: print full nissy manpage */
         if (args->command == NULL) {
-                printf("Type help COMMAND for information on a ");
-                printf("specific command.\n");
-                printf("A more complete manual page is work in progress.\n");
+                printf(
+                       "Use the nissy command \"help COMMAND\" for a short "
+                       "description of a specific command.\n"
+                       "Use the nissy command \"commands\" for a list of "
+                       "available commands.\n"
+                       "See the manual page for more details. The manual"
+                       " page is available with \"man nissy\" on a UNIX"
+                       " system (such a Linux or MacOS) or in pdf and html"
+                       " format in the docs folder.\n"
+                       "Nissy is available for free at "
+                       "https://github.com/sebastianotronto/nissy"
+                      );
         } else {
                 printf("Command %s: %s\nusage: %s\n", args->command->name,
                        args->command->description, args->command->usage);
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 334662c..7eb803e 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -3,6 +3,7 @@
 
 #include <stdbool.h>
 #include <inttypes.h>
+#include <pthread.h>
 
 #define NMOVES               55 /* Actually 55, but one is NULLMOVE */
 #define NTRANS               48
@@ -87,6 +88,7 @@ typedef struct prunedata     PruneData;
 typedef struct solveoptions  SolveOptions;
 typedef struct step          Step;
 typedef struct symdata       SymData;
+typedef struct threaddata    ThreadData;
 
 typedef Cube                 (*AntiIndexer)      (uint64_t);
 typedef bool                 (*Checker)          (Cube);
@@ -104,186 +106,205 @@ typedef Trans                (*TransDetector)    (Cube);
 struct
 alg
 {
-        Move *          move;
-        bool *          inv;
-        int             len;
-        int             allocated;
+        Move *            move;
+        bool *            inv;
+        int               len;
+        int               allocated;
 };
 
 struct
 alglist
 {
-        AlgListNode *   first;
-        AlgListNode *   last;
-        int             len;
+        AlgListNode *     first;
+        AlgListNode *     last;
+        int               len;
 };
 
 struct
 alglistnode
 {
-        Alg *           alg;
-        AlgListNode *   next;
+        Alg *             alg;
+        AlgListNode *     next;
 };
 
 struct
 block
 {
-        bool            edge[12];
-        bool            corner[8];
-        bool            center[6];
+        bool              edge[12];
+        bool              corner[8];
+        bool              center[6];
 };
 
 struct
 command
 {
-        char *          name;
-        char *          usage;
-        char *          description;
-        ArgParser       parse_args;
-        Exec            exec;
+        char *            name;
+        char *            usage;
+        char *            description;
+        ArgParser         parse_args;
+        Exec              exec;
 };
 
 struct
 commandargs
 {
-        bool            success;
-        Alg *           scramble;
-        SolveOptions *  opts;
-        Step *          step;
-        Command *       command; /* For help */
+        bool              success;
+        Alg *             scramble;
+        SolveOptions *    opts;
+        Step *            step;
+        Command *         command; /* For help */
 };
 
 struct
 coordinate
 {
-        Indexer         index;
-        AntiIndexer     cube;
-        uint64_t        max;
-        int             ntrans;
-        Trans *         trans;
+        Indexer           index;
+        AntiIndexer       cube;
+        uint64_t          max;
+        int               ntrans;
+        Trans *           trans;
 };
 
 struct
 cube
 {
-        int             epose;
-        int             eposs;
-        int             eposm;
-        int             eofb;
-        int             eorl;
-        int             eoud;
-        int             cp;
-        int             coud;
-        int             cofb;
-        int             corl;
-        int             cpos;
+        int               epose;
+        int               eposs;
+        int               eposm;
+        int               eofb;
+        int               eorl;
+        int               eoud;
+        int               cp;
+        int               coud;
+        int               cofb;
+        int               corl;
+        int               cpos;
 };
 
 struct
 cubearray
 {
-        int *           ep;
-        int *           eofb;
-        int *           eorl;
-        int *           eoud;
-        int *           cp;
-        int *           coud;
-        int *           corl;
-        int *           cofb;
-        int *           cpos;
+        int *             ep;
+        int *             eofb;
+        int *             eorl;
+        int *             eoud;
+        int *             cp;
+        int *             coud;
+        int *             corl;
+        int *             cofb;
+        int *             cpos;
 };
 
 struct
 cubetarget
 {
-        Cube            cube;
-        int             target;
+        Cube              cube;
+        int               target;
 };
 
 struct
 dfsdata
 {
-        int             d;
-        int             m;
-        int             lb;
-        bool            niss;
-        Move            last1;
-        Move            last2;
-        AlgList *       sols;
-        Alg *           current_alg;
-        Move            sorted_moves[NMOVES];
-        int             move_position[NMOVES];
-        uint8_t *       visited;
+        int               d;
+        int               m;
+        int               lb;
+        bool              niss;
+        Move              last1;
+        Move              last2;
+        AlgList *         sols;
+        pthread_mutex_t * sols_mutex;
+        Alg *             current_alg;
+        Move *            sorted_moves;
+        int *             move_position;
+        uint8_t *         visited;
 };
 
 struct
 piecefilter
 {
-        bool            epose;
-        bool            eposs;
-        bool            eposm;
-        bool            eofb;
-        bool            eorl;
-        bool            eoud;
-        bool            cp;
-        bool            coud;
-        bool            cofb;
-        bool            corl;
-        bool            cpos;
+        bool              epose;
+        bool              eposs;
+        bool              eposm;
+        bool              eofb;
+        bool              eorl;
+        bool              eoud;
+        bool              cp;
+        bool              coud;
+        bool              cofb;
+        bool              corl;
+        bool              cpos;
 };
 
 struct
 prunedata
 {
-        char *          filename;
-        uint8_t *       ptable;
-        bool            generated;
-        uint64_t        n;
-        Coordinate *    coord;
-        Moveset         moveset;
+        char *            filename;
+        uint8_t *         ptable;
+        bool              generated;
+        uint64_t          n;
+        Coordinate *      coord;
+        Moveset           moveset;
 };
 
 struct
 solveoptions
 {
-        int             min_moves;
-        int             max_moves;
-        int             max_solutions;
-        bool            optimal_only;
-        bool            can_niss;
-        bool            verbose;
-        bool            all;
-        bool            print_number;
+        int               min_moves;
+        int               max_moves;
+        int               max_solutions;
+        int               nthreads;
+        bool              optimal_only;
+        bool              can_niss;
+        bool              verbose;
+        bool              all;
+        bool              print_number;
 };
 
 struct
 step
 {
-        char *          shortname;
-        char *          name;
-        Estimator       estimate;
-        Checker         ready;
-        char *          ready_msg;
-        Validator       is_valid;
-        Moveset         moveset;
-        Trans           pre_trans;
-        TransDetector   detect;
-        int             ntables;
-        PruneData *     tables[10];
+        char *            shortname;
+        char *            name;
+        Estimator         estimate;
+        Checker           ready;
+        char *            ready_msg;
+        Validator         is_valid;
+        Moveset           moveset;
+        Trans             pre_trans;
+        TransDetector     detect;
+        int               ntables;
+        PruneData *       tables[10];
 };
 
 struct
 symdata
 {
-        char *          filename;
-        bool            generated;
-        Coordinate *    coord;
-        Coordinate *    sym_coord;
-        int             ntrans;
-        Trans *         trans;
-        uint64_t *      class;
-        Cube *          rep;
-        Trans *         transtorep;
+        char *            filename;
+        bool              generated;
+        Coordinate *      coord;
+        Coordinate *      sym_coord;
+        int               ntrans;
+        Trans *           trans;
+        uint64_t *        class;
+        Cube *            rep;
+        Trans *           transtorep;
+};
+
+struct
+threaddata
+{
+        int               thid;
+        Cube              cube;
+        Step *            step;
+        int               depth;
+        Move *            sorted_moves;
+        int *             move_position;
+        SolveOptions *    opts;
+        AlgList *         start;
+        AlgListNode **    node;
+        AlgList *         sols;
+        pthread_mutex_t * start_mutex;
+        pthread_mutex_t * sols_mutex;
 };
 
 #endif
diff --git a/src/pruning.c b/src/pruning.c
index 1369892..2c6f348 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -95,7 +95,7 @@ pd_khuge_HTM = {
 void
 genptable(PruneData *pd)
 {
-        Move ms[NMOVES];
+        Move *ms;
         uint64_t j, oldn;
         DfsData dd;
 
@@ -112,6 +112,7 @@ genptable(PruneData *pd)
 
         fprintf(stderr, "Cannot load %s, generating it\n", pd->filename); 
 
+        ms = malloc(NMOVES * sizeof(Move));
         moveset_to_list(pd->moveset, ms);
 
         for (j = 0; j < pd->coord->max; j++)
@@ -119,6 +120,7 @@ genptable(PruneData *pd)
 
         dd = (DfsData) { .m = 0 };
         dd.visited = malloc((ptablesize(pd)/4 + 1) * sizeof(uint8_t));
+        dd.sorted_moves = malloc(NMOVES * sizeof(Move));
         moveset_to_list(pd->moveset, dd.sorted_moves);
         oldn = 0;
         pd->n = 0;
@@ -136,14 +138,16 @@ genptable(PruneData *pd)
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
 
+        free(ms);
         free(dd.visited);
+        free(dd.sorted_moves);
 }
 */
 
 void
 genptable(PruneData *pd)
 {
-        Move ms[NMOVES];
+        Move *ms;
         int d;
         uint64_t j, oldn;
 
@@ -161,6 +165,7 @@ genptable(PruneData *pd)
 
         fprintf(stderr, "Cannot load %s, generating it\n", pd->filename); 
 
+        ms = malloc(NMOVES * sizeof(Move));
         moveset_to_list(pd->moveset, ms);
 
         /* We use 4 bits per value, so any distance >= 15 is set to 15 */
@@ -186,6 +191,7 @@ genptable(PruneData *pd)
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
 
+        free(ms);
 }
 
 /*
diff --git a/src/solve.c b/src/solve.c
index 29f614b..a35a837 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -8,6 +8,8 @@ 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 void *      instance_thread(void *arg);
+static void        multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d);
 
 /* Local functions ***********************************************************/
 
@@ -41,12 +43,24 @@ dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 static void
 dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 {
-        Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves;
+        bool b = false;
+        int i;
+        Move m, l1, l2;
 
-        int i, maxnsol = opts->max_solutions;
+        l1 = dd->last1;
+        l2 = dd->last2;
 
-        for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) {
-                m = moves[i];
+        for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) {
+        /*
+                pthread_mutex_lock(dd->sols_mutex);
+                b = dd->sols->len >= opts->max_solutions;
+                pthread_mutex_unlock(dd->sols_mutex);
+        */
+
+                if (b)
+                        break;
+                        
+                m = dd->sorted_moves[i];
                 if (allowed_next(m, dd)) {
                         dd->last2 = dd->last1;
                         dd->last1 = m;
@@ -68,8 +82,12 @@ dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd)
                 return false;
 
         if (dd->current_alg->len == dd->d) {
-                if (s->is_valid(dd->current_alg) || opts->all)
-                        append_alg(dd->sols, dd->current_alg);
+                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 (opts->verbose)
                         print_alg(dd->current_alg, false);
@@ -103,14 +121,13 @@ dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 static bool
 dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 {
+        bool b = false;
+
         CubeTarget ct = {
                 .cube   = c,
                 .target = dd->d - dd->current_alg->len
         };
 
-        if (dd->sols->len >= opts->max_solutions)
-                return true;
-
         dd->lb = s->estimate(ct);
         if (opts->can_niss && !dd->niss)
                 dd->lb = MIN(1, dd->lb);
@@ -118,7 +135,131 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
         if (dd->current_alg->len + dd->lb > dd->d)
                 return true;
 
-        return false;
+        pthread_mutex_lock(dd->sols_mutex);
+        b = dd->sols->len >= opts->max_solutions;
+        pthread_mutex_unlock(dd->sols_mutex);
+
+        return b;
+}
+
+static void *
+instance_thread(void *arg)
+{
+        bool b;
+        Cube c;
+        ThreadData *td;
+        AlgListNode *node;
+        DfsData dd;
+
+        td = (ThreadData *)arg;
+
+        while (1) {
+                b = false;
+
+                pthread_mutex_lock(td->start_mutex);
+                if ((node = *(td->node)) == NULL)
+                        b = true;
+                else
+                        *(td->node) = (*(td->node))->next;
+                pthread_mutex_unlock(td->start_mutex);
+
+                if (b)
+                        break;
+
+                c = node->alg->inv[0] ?
+                    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],
+                            node->alg->inv[0]);
+                dd.sorted_moves  = td->sorted_moves;
+                dd.move_position = td->move_position;
+
+/*
+                pthread_mutex_lock(td->sols_mutex);
+                printf("Starting thread %d with move: ", td->thid);
+                print_alg(dd.current_alg, false);
+                pthread_mutex_unlock(td->sols_mutex);
+*/
+
+                dfs(c, td->step, td->opts, &dd);
+
+                free_alg(dd.current_alg);
+        }
+
+        return NULL;
+}
+
+static void
+multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d)
+{
+        int i, *move_position;
+        Move *sorted_moves;
+        Alg *alg;
+        AlgList *start;
+        AlgListNode **node;
+        pthread_t t[opts->nthreads];
+        ThreadData td[opts->nthreads];
+        pthread_mutex_t *start_mutex, *sols_mutex;
+
+        move_position = malloc(NMOVES * sizeof(int));
+        sorted_moves  = malloc(NMOVES * sizeof(Move));
+        node  = malloc(sizeof(AlgListNode *));
+        start_mutex = malloc(sizeof(pthread_mutex_t));
+        sols_mutex  = malloc(sizeof(pthread_mutex_t));
+
+        start = new_alglist();
+        pthread_mutex_init(start_mutex, NULL);
+        pthread_mutex_init(sols_mutex,  NULL);
+
+        moveset_to_list(s->moveset, sorted_moves);
+        movelist_to_position(sorted_moves, move_position);
+        for (i = 0; sorted_moves[i] != NULLMOVE; i++) {
+                alg = new_alg("");
+                append_move(alg, sorted_moves[i], false);
+                append_alg(start, alg);
+                if (opts->can_niss) {
+                        alg->inv[0] = true;
+                        append_alg(start, alg);
+                }
+                free_alg(alg);
+        }
+        *node = start->first;
+
+        for (i = 0; i < opts->nthreads; i++) {
+                td[i].thid          = i;
+                td[i].cube          = c;
+                td[i].step          = s;
+                td[i].depth         = d;
+                td[i].sorted_moves  = sorted_moves;
+                td[i].move_position = move_position;
+                td[i].opts          = opts;
+                td[i].start         = start;
+                td[i].node          = node;
+                td[i].sols          = sols;
+                td[i].start_mutex   = start_mutex;
+                td[i].sols_mutex    = sols_mutex;
+                pthread_create(&t[i], NULL, instance_thread, &td[i]);
+        }
+
+        for (i = 0; i < opts->nthreads; i++)
+                pthread_join(t[i], NULL);
+
+        free_alglist(start);
+        free(node);
+        free(start_mutex);
+        free(sols_mutex);
+        free(move_position);
+        free(sorted_moves);
 }
 
 /* Public functions **********************************************************/
@@ -126,11 +267,12 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd)
 AlgList *
 solve(Cube cube, Step *step, SolveOptions *opts)
 {
+        int d;
+        AlgList *sols = new_alglist();
         AlgListNode *node;
-        DfsData dd;
         Cube c;
 
-        prepare_step(step, &dd);
+        prepare_step(step);
 
         if (step->detect != NULL)
                 step->pre_trans = step->detect(cube);
@@ -139,24 +281,29 @@ solve(Cube cube, Step *step, SolveOptions *opts)
         if (step->ready != NULL && !step->ready(c)) {
                 fprintf(stderr, "Cube not ready for solving step: ");
                 fprintf(stderr, "%s\n", step->ready_msg);
-                return dd.sols;
+                return sols;
+        }
+
+        if (step->estimate((CubeTarget){.cube = c, .target = 0}) == 0 &&
+            opts->min_moves == 0) {
+                append_alg(sols, new_alg(""));
+                return sols;
         }
 
-        for (dd.d = opts->min_moves;
-             dd.d <= opts->max_moves &&
-                 !(dd.sols->len && opts->optimal_only) &&
-                 dd.sols->len < opts->max_solutions;
-             dd.d++) {
+        for (d = MAX(1, opts->min_moves);
+             d <= opts->max_moves &&
+                 !(sols->len && opts->optimal_only) &&
+                 sols->len < opts->max_solutions;
+             d++) {
                 if (opts->verbose)
                         fprintf(stderr,
                                 "Found %d solutions, searching depth %d...\n",
-                                dd.sols->len, dd.d);
-                dfs(c, step, opts, &dd);
+                                sols->len, d);
+                multidfs(c, step, opts, sols, d);
         }
 
-        for (node = dd.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);
 
-        free_alg(dd.current_alg);
-        return dd.sols;
+        return sols;
 }
diff --git a/src/steps.c b/src/steps.c
index 012e4cd..34ddcc2 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -1063,21 +1063,10 @@ detect_pretrans_drud(Cube cube)
 /* Public functions **********************************************************/
 
 void
-prepare_step(Step *step, DfsData *dd)
+prepare_step(Step *step)
 {
         int i;
 
-        dd->m           = 0;
-        dd->niss        = false;
-        dd->lb          = -1;
-        dd->last1       = NULLMOVE;
-        dd->last2       = NULLMOVE;
-        dd->sols        = new_alglist();
-        dd->current_alg = new_alg("");
-
-        moveset_to_list(step->moveset, dd->sorted_moves);
-        movelist_to_position(dd->sorted_moves, dd->move_position);
-
         for (i = 0; i < step->ntables; i++)
                 genptable(step->tables[i]);
 }
diff --git a/src/steps.h b/src/steps.h
index 89ab168..4aedcee 100644
--- a/src/steps.h
+++ b/src/steps.h
@@ -7,6 +7,6 @@
 
 extern Step *           steps[NSTEPS];
 
-void                    prepare_step(Step *step, DfsData *dd);
+void                    prepare_step(Step *step);
 
 #endif