7 files changed, 356 insertions, 15 deletions

diff --git a/src/core/constants.h b/src/core/constants.h
index 26f6916..d8f2471 100644
--- a/src/core/constants.h
+++ b/src/core/constants.h
@@ -845,3 +845,69 @@ STATIC equivalent_moves_t equivalent_moves_table[] = {
         [MOVE_z2]  = {{UINT8_MAX}, {2, 2, UINT8_MAX}},
         [MOVE_z3]  = {{UINT8_MAX}, {2, 2, 2, UINT8_MAX}},
 };
+
+STATIC uint8_t slice_to_basic[] = {
+        [MOVE_M]  = MOVE_L,
+        [MOVE_M2] = MOVE_L2,
+        [MOVE_M3] = MOVE_L3,
+        [MOVE_S]  = MOVE_F,
+        [MOVE_S2] = MOVE_F2,
+        [MOVE_S3] = MOVE_F3,
+        [MOVE_E]  = MOVE_D,
+        [MOVE_E2] = MOVE_D2,
+        [MOVE_E3] = MOVE_D3,
+};
+
+STATIC uint8_t basic_to_slice[] = {
+        [MOVE_U]  = MOVE_E3,
+        [MOVE_U2] = MOVE_E2,
+        [MOVE_U3] = MOVE_E,
+        [MOVE_D]  = MOVE_E,
+        [MOVE_D2] = MOVE_E2,
+        [MOVE_D3] = MOVE_E3,
+        [MOVE_R]  = MOVE_M3,
+        [MOVE_R2] = MOVE_M2,
+        [MOVE_R3] = MOVE_M,
+        [MOVE_L]  = MOVE_M,
+        [MOVE_L2] = MOVE_M2,
+        [MOVE_L3] = MOVE_M3,
+        [MOVE_F]  = MOVE_S,
+        [MOVE_F2] = MOVE_S2,
+        [MOVE_F3] = MOVE_S3,
+        [MOVE_B]  = MOVE_S3,
+        [MOVE_B2] = MOVE_S2,
+        [MOVE_B3] = MOVE_S,
+};
+
+STATIC uint8_t rotation_to_basic[] = {
+        [MOVE_x]  = MOVE_R,
+        [MOVE_x2] = MOVE_R2,
+        [MOVE_x3] = MOVE_R3,
+        [MOVE_y]  = MOVE_U,
+        [MOVE_y2] = MOVE_U2,
+        [MOVE_y3] = MOVE_U3,
+        [MOVE_z]  = MOVE_F,
+        [MOVE_z2] = MOVE_F2,
+        [MOVE_z3] = MOVE_F3,
+};
+
+STATIC uint8_t basic_to_rotation[] = {
+        [MOVE_U]  = MOVE_y,
+        [MOVE_U2] = MOVE_y2,
+        [MOVE_U3] = MOVE_y3,
+        [MOVE_D]  = MOVE_y3,
+        [MOVE_D2] = MOVE_y2,
+        [MOVE_D3] = MOVE_y,
+        [MOVE_R]  = MOVE_x,
+        [MOVE_R2] = MOVE_x2,
+        [MOVE_R3] = MOVE_x3,
+        [MOVE_L]  = MOVE_x3,
+        [MOVE_L2] = MOVE_x2,
+        [MOVE_L3] = MOVE_x,
+        [MOVE_F]  = MOVE_z,
+        [MOVE_F2] = MOVE_z2,
+        [MOVE_F3] = MOVE_z3,
+        [MOVE_B]  = MOVE_z3,
+        [MOVE_B2] = MOVE_z2,
+        [MOVE_B3] = MOVE_z,
+};
diff --git a/src/core/core_types.h b/src/core/core_types.h
index 19a9f42..53cc95e 100644
--- a/src/core/core_types.h
+++ b/src/core/core_types.h
@@ -1,5 +1,3 @@
-#define MOVES_STRUCT_MAXLEN 1000
-
 typedef struct {
         cube_t cube;
         uint8_t orientation;
@@ -8,6 +6,6 @@ typedef struct {
 typedef struct {
         size_t nnormal;
         size_t ninverse;
-        uint8_t normal[MOVES_STRUCT_MAXLEN];
-        uint8_t inverse[MOVES_STRUCT_MAXLEN];
+        uint8_t normal[NISSY_SIZE_MOVES];
+        uint8_t inverse[NISSY_SIZE_MOVES];
 } moves_struct_t;
diff --git a/src/core/moves.h b/src/core/moves.h
index 9c8cc90..6169c6e 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -11,6 +11,8 @@ STATIC bool moves_struct_equal(
 STATIC long long comparemoves(const char *, const char *);
 STATIC uint8_t readmodifier(char);
 STATIC int64_t writemoves(size_t, const uint8_t *, size_t, char *);
+STATIC int64_t writemoves_struct(
+    const moves_struct_t [static 1], size_t, char *);
 
 STATIC_INLINE bool allowednextmove(uint8_t, uint8_t);
 STATIC bool allowedmoves(size_t, const uint8_t *);
@@ -23,6 +25,7 @@ STATIC_INLINE uint8_t moveopposite(uint8_t);
 STATIC_INLINE uint8_t reorient_move(uint8_t, uint8_t);
 STATIC_INLINE uint8_t inverse_reorient_move(uint8_t, uint8_t);
 STATIC_INLINE uint8_t movefollow(uint8_t);
+STATIC uint8_t transform_move_basic(uint8_t, uint8_t);
 STATIC uint8_t transform_move(uint8_t, uint8_t);
 
 STATIC cube_t move(cube_t, uint8_t);
@@ -31,6 +34,12 @@ STATIC uint8_t inverse_move(uint8_t);
 STATIC void sortparallel_moves(size_t, uint8_t*);
 STATIC bool are_lastmoves_singlecw(size_t, const uint8_t*);
 
+STATIC int64_t move_variations(const char *, const char *, size_t, char *);
+STATIC int64_t move_variations_lastqt(
+    const moves_struct_t [static 1], size_t, char *);
+STATIC int64_t move_variations_unniss(
+    const moves_struct_t [static 1], size_t, char *);
+
 #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \
         RET_ERROR, ARG_ACTION) \
         const char *VAR_B; \
@@ -160,7 +169,7 @@ readmoves(
 STATIC int64_t
 readmoves_struct(const char *moves, moves_struct_t ret[static 1])
 {
-        return readmoves(moves, MOVES_STRUCT_MAXLEN, MOVES_STRUCT_MAXLEN,
+        return readmoves(moves, NISSY_SIZE_MOVES, NISSY_SIZE_MOVES,
             &ret->nnormal, &ret->ninverse, ret->normal, ret->inverse);
 }
 
@@ -270,6 +279,51 @@ writemoves_error:
         return NISSY_ERROR_BUFFER_SIZE;
 }
 
+STATIC int64_t
+writemoves_struct(
+        const moves_struct_t moves[static 1],
+        size_t buf_size,
+        char *buf
+)
+{
+        int64_t w, u;
+
+        w = 0;
+        if (moves->nnormal > 0) {
+                w = writemoves(moves->nnormal, moves->normal, buf_size, buf);
+                if (w < 0)
+                        goto writemoves_struct_error;
+        }
+
+        u = 0;
+        if (moves->ninverse > 0) {
+                if (moves->nnormal > 0) {
+                        if ((size_t)w >= buf_size)
+                                goto writemoves_struct_error;
+                        buf[w++] = ' ';
+                }
+                if ((size_t)w >= buf_size)
+                        goto writemoves_struct_error;
+                buf[w++] = '(';
+
+                u = writemoves(moves->ninverse, moves->inverse,
+                    buf_size-w, buf+w);
+                if (u < 0)
+                        goto writemoves_struct_error;
+
+                if ((size_t)w >= buf_size)
+                        goto writemoves_struct_error;
+                buf[w + (u++)] = ')';
+        }
+
+        buf[u+w] = '\0';
+        return u+w;
+
+writemoves_struct_error:
+        buf[w] = '\0';
+        return NISSY_ERROR_BUFFER_SIZE;
+}
+
 STATIC_INLINE bool
 allowednextmove(uint8_t m1, uint8_t m2)
 {
@@ -408,14 +462,12 @@ move(cube_t c, uint8_t m)
 }
 
 STATIC uint8_t
-transform_move(uint8_t m, uint8_t t)
+transform_move_basic(uint8_t m, uint8_t t)
 {
         uint8_t a, base, modifier;
 
-        if (m > MOVE_B3) {
-                LOG("transform_move: attempting to transform %s, but "
-                    "transofrmations are only supported for basic moves\n",
-                    movestr[m]);
+        if (t > 47) {
+                LOG("transform_move: invalid trans %" PRIu8 "\n", t);
                 return UINT8_ERROR;
         }
 
@@ -431,6 +483,27 @@ transform_move(uint8_t m, uint8_t t)
         return base + modifier;
 }
 
+STATIC uint8_t
+transform_move(uint8_t m, uint8_t t)
+{
+        if (m <= MOVE_B3)
+                return transform_move_basic(m, t);
+
+        if (m >= MOVE_Uw && m <= MOVE_Bw3)
+                return 18+transform_move_basic(m-18, t);
+
+        if (m >= MOVE_M && m <= MOVE_E3)
+                return basic_to_slice[
+                    transform_move_basic(slice_to_basic[m], t)];
+
+        if (m >= MOVE_x && m <= MOVE_z3)
+                return basic_to_rotation[
+                    transform_move_basic(rotation_to_basic[m], t)];
+
+        LOG("transform_move: invalid move %" PRIu8 "\n", m);
+        return UINT8_ERROR;
+}
+
 /* Applies the INVERSE of m BEFORE the scramble corresponding to c */
 STATIC cube_t
 premove(cube_t c, uint8_t m)
@@ -509,3 +582,140 @@ are_lastmoves_singlecw(size_t n, const uint8_t *moves)
 
         return isbase(moves[n-1]) && (!two || isbase(moves[n-2]));
 }
+
+STATIC int64_t
+move_variations(
+        const char *moves,
+        const char *variation,
+        size_t result_size,
+        char *result
+)
+{
+        moves_struct_t m;
+        int64_t err;
+
+        err = readmoves_struct(moves, &m);
+        if (err < 0) {
+                LOG("[variations] Error reading moves.\n");
+                return err;
+        }
+
+        if (!strcmp(variation, "lastqt")) {
+                return move_variations_lastqt(&m, result_size, result);
+        } else if (!strcmp(variation, "unniss")) {
+                return move_variations_unniss(&m, result_size, result);
+        } else {
+                LOG("[variations] Error: unknown variation '%s'\n", variation);
+                return NISSY_ERROR_INVALID_VARIATION;
+        }
+}
+
+STATIC int64_t
+move_variations_lastqt(
+        const moves_struct_t s[static 1],
+        size_t result_size,
+        char *result
+)
+{
+        uint8_t n1, n2, i1, i2, swapn1, swapn2, swapi1, swapi2, i, j, k, l;
+        int8_t in1, in2, ii1, ii2;
+        int64_t err, count;
+        size_t u;
+        moves_struct_t ss;
+
+        in1 = s->nnormal-1;
+        in2 = s->nnormal-2;
+        ii1 = s->ninverse-1;
+        ii2 = s->ninverse-2;
+
+        n1 = in1 >= 0 ? s->normal[in1] : UINT8_ERROR;
+        n2 = in2 >= 0 ? s->normal[in2] : UINT8_ERROR;
+        i1 = ii1 >= 0 ? s->inverse[ii1] : UINT8_ERROR;
+        i2 = ii2 >= 0 ? s->inverse[ii2] : UINT8_ERROR;
+
+        swapn1 = in1 >= 0 && n1 % 3 != 1 ? 1 : 0;
+        swapn2 = swapn1 && in2 >= 0 && n2 % 3 != 1 && parallel(n1, n2) ? 1 : 0;
+        swapi1 = ii1 >= 0 && i1 % 3 != 1 ? 1 : 0;
+        swapi2 = swapi1 && ii2 >= 0 && i2 % 3 != 1 && parallel(i1, i2) ? 1 : 0;
+
+        /* Reset ending qt to base so that they are sorted */
+        ss = *s;
+        if (swapn1 == 1) ss.normal[in1] = 3*movebase(n1);
+        if (swapn2 == 1) ss.normal[in2] = 3*movebase(n2);
+        if (swapi1 == 1) ss.inverse[ii1] = 3*movebase(i1);
+        if (swapi2 == 1) ss.inverse[ii2] = 3*movebase(i2);
+
+        u = 0;
+        count = 0;
+        for (i = 0; i <= swapn2; i++) {
+                if (i == 1) ss.normal[in2] += 2;
+                for (j = 0; j <= swapn1; j++) {
+                        if (j == 1) ss.normal[in1] += 2;
+                        for (k = 0; k <= swapi2; k++) {
+                                if (k == 1) ss.inverse[ii2] += 2;
+                                for (l = 0; l <= swapi1; l++) {
+                                        if (l == 1) ss.inverse[ii1] += 2;
+
+                                        err = writemoves_struct(
+                                            &ss, result_size-u, result+u);
+                                        if (err < 0)
+                                                goto lastqt_error;
+                                        u += err;
+                                        count++;
+
+                                        if (u >= result_size)
+                                                goto lastqt_error;
+                                        result[u++] = '\n';
+                                        result[u] = '\0';
+
+                                        if (l == 1) ss.inverse[ii1] -= 2;
+                                }
+                                if (k == 1) ss.inverse[ii2] -= 2;
+                        }
+                        if (j == 1) ss.normal[in1] -= 2;
+                }
+                if (i == 1) ss.normal[in2] -= 2;
+        }
+
+        return count;
+
+lastqt_error:
+        LOG("[variations] Error writing result.\n");
+        return NISSY_ERROR_BUFFER_SIZE;
+}
+
+STATIC int64_t
+move_variations_unniss(
+        const moves_struct_t s[static 1],
+        size_t result_size,
+        char *result
+)
+{
+        size_t i, tot;
+        uint8_t res[NISSY_SIZE_MOVES];
+        int64_t err;
+
+        tot = s->nnormal + s->ninverse;
+        if (tot > NISSY_SIZE_MOVES) {
+                LOG("[variations] Error: %zu total moves, more than maximum "
+                    "allowed %zu", tot, NISSY_SIZE_MOVES);
+                return NISSY_ERROR_BUFFER_SIZE;
+        }
+
+        for (i = 0; i < s->nnormal; i++)
+                res[i] = s->normal[i];
+        for (i = 0; i < s->ninverse; i++)
+                res[i+s->nnormal] = inverse_move(s->inverse[s->ninverse-i-1]);
+
+        err = writemoves(tot, res, result_size, result);
+        if (err < 0 || (size_t)err > result_size)
+                goto unniss_error;
+
+        result[err++] = '\n';
+        result[err] = '\0';
+        return 1;
+
+unniss_error:
+        LOG("[variations] Error writing result.\n");
+        return NISSY_ERROR_BUFFER_SIZE;
+}
diff --git a/src/nissy.c b/src/nissy.c
index 4b5d476..17ef960 100644
--- a/src/nissy.c
+++ b/src/nissy.c
@@ -149,6 +149,32 @@ nissy_applytrans_error:
 }
 
 long long
+nissy_variations(
+        const char *moves,
+        const char *variation,
+        unsigned long long result_size,
+        char *result
+)
+{
+        if (moves == NULL) {
+                LOG("[variations] Error: 'moves' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        if (variation == NULL) {
+                LOG("[variations] Error: 'variation' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        if (result == NULL) {
+                LOG("[variations] Error: 'result' argument is NULL\n");
+                return NISSY_ERROR_NULL_POINTER;
+        }
+
+        return move_variations(moves, variation, result_size, result);
+}
+
+long long
 nissy_getcube(
         long long ep,
         long long eo,
diff --git a/src/nissy.h b/src/nissy.h
index 38fe656..959b2d8 100644
--- a/src/nissy.h
+++ b/src/nissy.h
@@ -27,6 +27,7 @@ for example 'rotation UF' or 'mirrored BL'.
 #define NISSY_SIZE_TRANSFORMATION 12U
 #define NISSY_SIZE_SOLVE_STATS    10U
 #define NISSY_SIZE_DATAID         255U
+#define NISSY_SIZE_MOVES          1000U
 
 /* Flags for NISS options */
 #define NISSY_NISSFLAG_NORMAL  1U
@@ -99,6 +100,12 @@ not known.
 #define NISSY_ERROR_INVALID_SOLVER -50LL
 
 /*
+The value NISSY_ERROR_INVALID_VARIATION means that the given method of
+finding variations for a solution is not known.
+*/
+#define NISSY_ERROR_INVALID_VARIATION -51LL
+
+/*
 The value NISSY_ERROR_NULL_POINTER means that one of the provided pointer
 arguments is NULL. For example, it may be returned by solve when called
 with a solver that requires some pre-computed data, but the provided
@@ -205,6 +212,36 @@ nissy_applytrans(
 );
 
 /*
+Find variations of a given move sequence, for example by changing
+the direction of the last quarter turn(s), or linearizing a NISS move
+sequence. The result consists of one or more move sequences, one per line,
+and it always ends in a newline character.
+
+Parameters:
+   moves       - The moves of which to find the variation. Must be at most
+                 NISSY_SIZE_MOVES long.
+   variations  - Specify which kind of variations to find, e.g. "lastqt".
+   result_size - The size of the result buffer.
+   result      - The result buffer.
+
+Return values:
+   NISSY_ERROR_NULL_POINTER      - One of the provided pointers is NULL.
+   NISSY_ERROR_INVALID_MOVES     - The given moves are invalid.
+   NISSY_ERROR_INVALID_VARIATION - The given transformer is not known.
+   NISSY_ERROR_BUFFER_SIZE       - Either the result buffer is too small or the
+                                   given move sequence is longer than
+                                   NISSY_SIZE_MOVES.
+   Any value >= 0                - The number of variations found.
+*/
+long long
+nissy_variations(
+        const char *moves,
+        const char *variation,
+        unsigned long long result_size,
+        char *result
+);
+
+/*
 Get the cube with the given ep, eo, cp and co values. The values must be in the
 ranges specified below, but if the option "fix" is given any values outside its
 range will be adjusted before using it. The option "fix" also fixes parity and
@@ -365,6 +402,8 @@ nissy_solve(
 );
 
 /*
+Count the given moves.
+
 Parameters:
    moves  - The moves to be counted.
 
@@ -379,6 +418,8 @@ nissy_countmoves(
 );
 
 /*
+Compare the two moves sequences. Both must be at most NISSY_SIZE_MOVES long.
+
 Parameters:
    moves1 - The first sequence of moves to compare.
    moves2 - The second sequence of moves to compare.
diff --git a/src/solvers/solutions.h b/src/solvers/solutions.h
index 00ed84c..9f209d1 100644
--- a/src/solvers/solutions.h
+++ b/src/solvers/solutions.h
@@ -55,7 +55,7 @@ solution_list_init(solution_list_t sols[static 1], size_t n, char *buf)
                 return false;
 
         sols->nsols = 0;
-        sols->shortest_sol = MAXLEN + 1;
+        sols->shortest_sol = SOLUTION_MAXLEN + 1;
         sols->size = n;
         sols->used = 0;
         sols->buf = buf;
@@ -162,7 +162,7 @@ appendsolution(
         uint8_t t;
         solution_moves_t tsol[NTRANS];
 
-        if (moves->nmoves + moves->npremoves > MAXLEN)
+        if (moves->nmoves + moves->npremoves > SOLUTION_MAXLEN)
                 goto appendsolution_error_solution_length;
 
         for (
diff --git a/src/solvers/solutions_types_macros.h b/src/solvers/solutions_types_macros.h
index f1cb517..e57e039 100644
--- a/src/solvers/solutions_types_macros.h
+++ b/src/solvers/solutions_types_macros.h
@@ -1,10 +1,10 @@
-#define MAXLEN 20
+#define SOLUTION_MAXLEN 20
 
 typedef struct {
         uint8_t nmoves;
-        uint8_t moves[MAXLEN];
+        uint8_t moves[SOLUTION_MAXLEN];
         uint8_t npremoves;
-        uint8_t premoves[MAXLEN];
+        uint8_t premoves[SOLUTION_MAXLEN];
 } solution_moves_t;
 
 typedef struct {