7 files changed, 310 insertions, 24 deletions

diff --git a/src/cube.c b/src/cube.c
index 0ccffa4..c2a457c 100644
--- a/src/cube.c
+++ b/src/cube.c
@@ -2,6 +2,8 @@
 
 #include "cube.h"
 
+static int where_is_piece(int piece, int *arr, int n);
+
 void
 compose(Cube *c2, Cube *c1)
 {
@@ -154,3 +156,33 @@ print_cube(Cube *cube)
                 printf("  %s ", center_string[cube->xp[i]]);
         printf("\n");
 }
+
+int
+where_is_center(Center x, Cube *c)
+{
+        return where_is_piece(x, c->xp, 6);
+}
+
+int
+where_is_corner(Corner k, Cube *c)
+{
+        return where_is_piece(k, c->cp, 8);
+}
+
+int
+where_is_edge(Edge e, Cube *c)
+{
+        return where_is_piece(e, c->ep, 12);
+}
+
+static int
+where_is_piece(int piece, int *arr, int n)
+{
+        int i;
+
+        for (i = 0; i < n; i++)
+                if (arr[i] == piece)
+                        return i;
+
+        return -1;
+}
diff --git a/src/cube.h b/src/cube.h
index 9f8b23d..789bb2e 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -15,6 +15,9 @@ bool        is_admissible(Cube *cube);
 bool        is_solved(Cube *cube);
 void        make_solved(Cube *cube);
 void        print_cube(Cube *cube);
+int         where_is_center(Center x, Cube *c);
+int         where_is_corner(Corner k, Cube *c);
+int         where_is_edge(Edge e, Cube *c);
 
 #endif
 
diff --git a/src/cubetypes.h b/src/cubetypes.h
index bb1ad10..d4fa241 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -108,6 +108,7 @@ typedef void                 (*DfsExtraCopier)   (void *, void *);
 typedef bool                 (*Validator)        (Alg *);
 typedef void                 (*Exec)             (CommandArgs *);
 typedef CommandArgs *        (*ArgParser)        (int, char **);
+typedef bool                 (*Tester)           (void);
 typedef int                  (*TransFinder)      (uint64_t, Trans *);
 
 
@@ -239,7 +240,7 @@ fstcube
         uint16_t                  rd_eofb;
         uint16_t                  rd_eposepe;
         uint16_t                  rd_coud;
-}
+};
 
 struct
 indexer
diff --git a/src/fst.c b/src/fst.c
index 91c022a..ebd3333 100644
--- a/src/fst.c
+++ b/src/fst.c
@@ -2,7 +2,30 @@
 
 #include "fst.h"
 
-static void             fst_to_ep(FstCube fst, int *ep);
+static FstCube          ep_to_fst_epos(int *ep);
+static int              fst_where_is_edge(int e, FstCube fst);
+static void             transform_ep_only(Trans t, int *ep, Cube *dst);
+static void             init_fst_corner_invtables();
+static void             init_fst_eo_invtables();
+static void             init_fst_eo_update(uint64_t, uint64_t, int, Cube *);
+static void             init_fst_transalg();
+static void             init_fst_where_is_edge();
+
+static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0,
+                             [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1,
+                             [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2};
+
+static uint16_t         inv_coud[FACTORIAL8][POW3TO7];
+static uint16_t         inv_cp[FACTORIAL8];
+static uint16_t         uf_cp_to_fr_cp[FACTORIAL8];
+static uint16_t         uf_cp_to_rd_cp[FACTORIAL8];
+
+static int16_t          eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4];
+
+static int              trans_ep_alg[NROTATIONS][12];
+static int              trans_ep_inv[NROTATIONS][12];
+
+static uint16_t         fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4];
 
 FstCube
 cube_to_fst(Cube *cube)
@@ -11,19 +34,39 @@ cube_to_fst(Cube *cube)
         FstCube ret;
 
         copy_cube(cube, &c);
-        ret.uf_eofb    = index_eofb(&c);
-        ret.uf_eposepe = index_eposepe(&c);
-        ret.uf_coud    = index_coud(&c);
-        ret.uf_cp      = index_cp(&c);
+        ret.uf_eofb    = coord_eofb.i[0]->index(&c);
+        ret.uf_eposepe = coord_eposepe.i[0]->index(&c);
+        ret.uf_coud    = coord_coud.i[0]->index(&c);
+        ret.uf_cp      = coord_cp.i[0]->index(&c);
         copy_cube(cube, &c);
-        transform_cube(fr, &c);
-        ret.fr_eofb    = index_eofb(&c);
-        ret.fr_eposepe = index_eposepe(&c);
-        ret.fr_coud    = index_coud(&c);
-        transform_cube(rd, &c);
-        ret.rd_eofb    = index_eofb(&c);
-        ret.rd_eposepe = index_eposepe(&c);
-        ret.rd_coud    = index_coud(&c);
+        apply_trans(fr, &c);
+        ret.fr_eofb    = coord_eofb.i[0]->index(&c);
+        ret.fr_eposepe = coord_eposepe.i[0]->index(&c);
+        ret.fr_coud    = coord_coud.i[0]->index(&c);
+        apply_trans(rd, &c);
+        ret.rd_eofb    = coord_eofb.i[0]->index(&c);
+        ret.rd_eposepe = coord_eposepe.i[0]->index(&c);
+        ret.rd_coud    = coord_coud.i[0]->index(&c);
+
+        return ret;
+}
+
+static FstCube
+ep_to_fst_epos(int *ep)
+{
+        /* TODO: maybe optimize? */
+
+        FstCube ret;
+        Cube c;
+
+        memcpy(c.ep, ep, 12 * sizeof(int));
+        ret.uf_eposepe = coord_eposepe.i[0]->index(&c);
+
+        transform_ep_only(fr, ep, &c);
+        ret.fr_eposepe = coord_eposepe.i[0]->index(&c);
+
+        transform_ep_only(rd, ep, &c);
+        ret.rd_eposepe = coord_eposepe.i[0]->index(&c);
 
         return ret;
 }
@@ -31,28 +74,232 @@ cube_to_fst(Cube *cube)
 FstCube
 fst_inverse(FstCube fst)
 {
-        /* TODO */
+        FstCube ret;
+        int i, ep_inv[12];
+
+        for (i = 0; i < 12; i++)
+                ep_inv[i] = fst_where_is_edge(i, fst);
+        ret = ep_to_fst_epos(ep_inv);
+
+        ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) |
+                      ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) |
+                      ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]);
+        ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) |
+                      ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) |
+                      ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]);
+        ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) |
+                      ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) |
+                      ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]);
+
+        ret.uf_cp = inv_cp[fst.uf_cp];
+
+        ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud];
+        ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud];
+        ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud];
+
+        return ret;
 }
 
 FstCube
 fst_move(Move m, FstCube fst)
 {
-        /* TODO */
+        FstCube ret;
+        Move m_fr, m_rd;
+
+        m_fr = transform_move(fr, m);
+        m_rd = transform_move(rd, m);
+
+        ret.uf_eofb    = coord_eofb.mtable[m][fst.uf_eofb];
+        ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe];
+        ret.uf_coud    = coord_coud.mtable[m][fst.uf_coud];
+        ret.uf_cp      = coord_cp.mtable[m][fst.uf_cp];
+
+        ret.fr_eofb    = coord_eofb.mtable[m_fr][fst.fr_eofb];
+        ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe];
+        ret.fr_coud    = coord_coud.mtable[m_fr][fst.fr_coud];
+
+        ret.rd_eofb    = coord_eofb.mtable[m_rd][fst.rd_eofb];
+        ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe];
+        ret.rd_coud    = coord_coud.mtable[m_rd][fst.rd_coud];
+
+        return ret;
 }
 
 void
 fst_to_cube(FstCube fst, Cube *cube)
 {
-        invindex_eofb((uint64_t)fst.uf_eofb, cube);
-        fst_to_ep(fst, cube->ep);
-        invindex_coud((uint64_t)fst.uf_coud, cube);
-        invindex_cp((uint64_t)fst.uf_cp, cube);
+        Cube e, s, m;
+        int i;
+
+        coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e);
+        coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s);
+        apply_trans(inverse_trans(fr), &s);
+        coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m);
+        apply_trans(inverse_trans(rd), &m);
+
+        for (i = 0; i < 12; i++) {
+                if (edge_slice[e.ep[i]] == 0)
+                        cube->ep[i] = e.ep[i];
+                if (edge_slice[s.ep[i]] == 1)
+                        cube->ep[i] = s.ep[i];
+                if (edge_slice[m.ep[i]] == 2)
+                        cube->ep[i] = m.ep[i];
+        }
+
+        coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube);
+        coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube);
+        coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube);
+}
+
+static int
+fst_where_is_edge(int e, FstCube fst)
+{
+        switch (edge_slice[e]) {
+        case 0:
+                return fst_where_is_edge_arr[0][e][fst.uf_eposepe];
+        case 1:
+                return fst_where_is_edge_arr[1][e][fst.fr_eposepe];
+        default:
+                return fst_where_is_edge_arr[2][e][fst.rd_eposepe];
+        }
+
+        return -1;
+}
+
+static void
+transform_ep_only(Trans t, int *ep, Cube *dst)
+{
+        int i;
+
+        for (i = 0; i < 12; i++)
+                dst->ep[i] = trans_ep_alg[t][ep[trans_ep_inv[t][i]]];
+}
+
+void
+init_fst()
+{
+        init_fst_corner_invtables();
+        init_fst_eo_invtables();
+        init_fst_transalg();
+        init_fst_where_is_edge();
+}
+
+static void
+init_fst_corner_invtables()
+{
+/* TODO: this can be optimized by transforming and copying only corners */
+/* A factor of about 4 would be saved in the innermost loop */
+
+        Cube c, d;
+        uint64_t cp, coud;
+
+        for (cp = 0; cp < FACTORIAL8; cp++) {
+                make_solved(&c);
+                coord_cp.i[0]->to_cube(cp, &c);
+
+                copy_cube(&c, &d);
+                invert_cube(&d);
+                inv_cp[cp] = coord_coud.i[0]->index(&d);
+
+                for (coud = 0; coud < POW3TO7; coud++) {
+                        copy_cube(&c, &d);
+                        coord_coud.i[0]->to_cube(coud, &d);
+                        invert_cube(&d);
+                        inv_coud[cp][coud] = coord_coud.i[0]->index(&d);
+                }
+
+                copy_cube(&c, &d);
+                apply_trans(fr, &d);
+                uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d);
+
+                copy_cube(&c, &d);
+                apply_trans(rd, &d);
+                uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d);
+        }
+}
+
+static void
+init_fst_eo_invtables()
+{
+        uint64_t ep, eo;
+        Cube c, d;
+
+        for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) {
+                make_solved(&c);
+                coord_eposepe.i[0]->to_cube(ep, &c);
+                for (eo = 0; eo < POW2TO11; eo++) {
+                        coord_eofb.i[0]->to_cube(eo, &c);
+                        copy_cube(&c, &d);
+                        init_fst_eo_update(eo, ep, 0, &d);
+                        apply_trans(inverse_trans(fr), &d);
+                        init_fst_eo_update(eo, ep, 1, &d);
+                        copy_cube(&c, &d);
+                        apply_trans(inverse_trans(rd), &d);
+                        init_fst_eo_update(eo, ep, 2, &d);
+                }
+        }
 }
 
 static void
-fst_to_ep(FstCube fst, int *ep)
+init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d)
 {
-        /* TODO */
+        int i;
+
+        for (i = 0; i < 12; i++)
+                if (d->eo[i])
+                        eo_invtable[s][eo][ep] |= ((uint16_t)1) << d->ep[i];
 }
 
-#endif
+static void
+init_fst_transalg()
+{
+        Trans t;
+        Alg *alg;
+        Cube c;
+        int i;
+
+        for (t = uf; t < NROTATIONS; t++) {
+                make_solved(&c);
+                alg = rotation_alg(t);
+                apply_alg(alg, &c);
+                for (i = 0; i < 12; i++)
+                        trans_ep_alg[t][i] = c.ep[i];
+                invert_cube(&c);
+                for (i = 0; i < 12; i++)
+                        trans_ep_inv[t][i] = c.ep[i];
+        }
+}
+
+static void
+init_fst_where_is_edge()
+{
+        Cube c, d;
+        uint64_t e;
+
+        init_trans();
+
+        make_solved(&c);
+        for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) {
+                coord_eposepe.i[0]->to_cube(e, &c);
+
+                copy_cube(&c, &d);
+                fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d);
+                fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d);
+                fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d);
+                fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d);
+
+                copy_cube(&c, &d);
+                apply_trans(inverse_trans(fr), &d);
+                fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d);
+                fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d);
+                fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d);
+                fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d);
+
+                copy_cube(&c, &d);
+                apply_trans(inverse_trans(rd), &d);
+                fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d);
+                fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d);
+                fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d);
+                fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &d);
+        }
+}
diff --git a/src/fst.h b/src/fst.h
index 94f6c30..c3b226c 100644
--- a/src/fst.h
+++ b/src/fst.h
@@ -7,6 +7,7 @@ FstCube     cube_to_fst(Cube *cube);
 FstCube     fst_inverse(FstCube fst);
 FstCube     fst_move(Move m, FstCube fst);
 void        fst_to_cube(FstCube fst, Cube *cube);
+void        init_fst();
 
 #endif
 
diff --git a/src/shell.c b/src/shell.c
index 44665a8..c25b399 100644
--- a/src/shell.c
+++ b/src/shell.c
@@ -142,6 +142,7 @@ launch(bool batchmode)
         free(shell_argv);
 }
 
+#ifndef TEST
 int
 main(int argc, char *argv[])
 {
@@ -187,3 +188,4 @@ main(int argc, char *argv[])
 
         return 0;
 }
+#endif
diff --git a/src/trans.c b/src/trans.c
index da2dca3..898c2be 100644
--- a/src/trans.c
+++ b/src/trans.c
@@ -26,7 +26,7 @@ static char rotation_alg_string[100][NROTATIONS] = {
         [bu] = "x3",   [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3",
 };
 
-static Alg *rotation_alg_arr[NROTATIONS];
+Alg  *rotation_alg_arr[NROTATIONS];
 Move  moves_ttable[NTRANS][NMOVES];
 Trans trans_ttable[NTRANS][NTRANS];
 Trans trans_itable[NTRANS];