Faster and nice pruning table generation. Can still be improved with multithreading.

5 files changed, 110 insertions, 38 deletions

diff --git a/nissy b/nissy
index f559b2e..4970885 100755
--- a/nissy
+++ b/nissy
diff --git a/src/coord.c b/src/coord.c
index 3d5e785..c9a28c4 100644
--- a/src/coord.c
+++ b/src/coord.c
@@ -49,7 +49,6 @@ coord_eofb = {
         .index  = index_eofb,
         .cube   = antindex_eofb,
         .max    = POW2TO11,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -57,7 +56,6 @@ coord_eofbepos = {
         .index  = index_eofbepos,
         .cube   = antindex_eofbepos,
         .max    = POW2TO11 * BINOM12ON4,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -65,7 +63,6 @@ coord_coud = {
         .index  = index_coud,
         .cube   = antindex_coud,
         .max    = POW3TO7,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -73,7 +70,6 @@ coord_corners = {
         .index  = index_corners,
         .cube   = antindex_corners,
         .max    = POW3TO7 * FACTORIAL8,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -81,7 +77,6 @@ coord_cp = {
         .index  = index_cp,
         .cube   = antindex_cp,
         .max    = FACTORIAL8,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -89,7 +84,6 @@ coord_cphtr = {
         .index  = index_cphtr,
         .cube   = antindex_cphtr,
         .max    = BINOM8ON4 * 6,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -97,7 +91,6 @@ coord_cornershtr = {
         .index  = index_cornershtr,
         .cube   = antindex_cornershtr,
         .max    = POW3TO7 * BINOM8ON4 * 6,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -105,7 +98,6 @@ coord_cornershtrfin = {
         .index  = index_cornershtrfin,
         .cube   = antindex_cornershtrfin,
         .max    = 24*24/6,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -113,7 +105,6 @@ coord_epud = {
         .index  = index_epud,
         .cube   = antindex_epud,
         .max    = FACTORIAL8,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -121,7 +112,6 @@ coord_drud = {
         .index  = index_drud,
         .cube   = antindex_drud,
         .max    = POW2TO11 * POW3TO7 * BINOM12ON4,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -129,7 +119,6 @@ coord_htr_drud = {
         .index  = index_htr_drud,
         .cube   = antindex_htr_drud,
         .max    = BINOM8ON4 * 6 * BINOM8ON4,
-        .ntrans = 1,
 };
 
 Coordinate
@@ -137,7 +126,6 @@ coord_htrfin = {
         .index  = index_htrfin,
         .cube   = antindex_htrfin,
         .max    = 24 * 24 * 24 *24 * 24 / 6, /* should be /12 but it's ok */
-        .ntrans = 1,
 };
 
 Coordinate
@@ -145,7 +133,6 @@ coord_drud_eofb = {
         .index  = index_drud_eofb,
         .cube   = antindex_drud_eofb,
         .max    = POW3TO7 * BINOM12ON4,
-        .ntrans = 1,
 };
 
 /* Antindexers ***************************************************************/
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 3f350af..27666be 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -100,6 +100,7 @@ typedef uint64_t             (*Indexer)          (Cube);
 typedef bool                 (*Moveset)          (Move);
 typedef CommandArgs *        (*ArgParser)        (int, char **);
 typedef Trans                (*TransDetector)    (Cube);
+typedef int                  (*TransFinder)      (uint64_t ind, Trans *);
 
 
 /* Structs *******************************************************************/
@@ -162,8 +163,7 @@ coordinate
         Indexer           index;
         AntiIndexer       cube;
         uint64_t          max;
-        int               ntrans;
-        Trans *           trans;
+        TransFinder       trans;
 };
 
 struct
diff --git a/src/pruning.c b/src/pruning.c
index 716379e..6ea77e3 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -144,20 +144,20 @@ genptable(PruneData *pd)
 static void
 genptable_bfs(PruneData *pd, int d, Move *ms)
 {
-        int j;
+        int j, n;
         uint64_t i;
         Cube c, cc;
+        Trans t[NTRANS];
 
         for (i = 0; i < pd->coord->max; i++) {
-                /*
-                 * TODO: only do this if the position is "nasty",
-                 * i.e. self-symmetrical with respect to the base
-                 * coordinate but not overall.
-                 */
                  if (ptableval_index(pd, i) == d) {
+                        n = pd->coord->trans(i, t);
+                        if (n == 1)
+                                continue;
+
                         c = pd->coord->cube(i);
-                        for (j = 0; j < pd->coord->ntrans; j++) {
-                                cc = apply_trans(pd->coord->trans[j], c);
+                        for (j = 0; j < n; j++) {
+                                cc = apply_trans(t[j], c);
                                 if (ptableval(pd, cc) > d)
                                         ptable_update(pd, cc, d);
                         }
diff --git a/src/symcoord.c b/src/symcoord.c
index 798a946..038449a 100644
--- a/src/symcoord.c
+++ b/src/symcoord.c
@@ -1,5 +1,9 @@
 #include "symcoord.h"
 
+/* These constants have been computed generating the respective SymData */
+#define CLASSES_CP_16        2768
+#define CLASSES_EOFBEPOS_16  64430
+
 static Cube        antindex_coud_sym16(uint64_t ind);
 static Cube        antindex_cp_sym16(uint64_t ind);
 static Cube        antindex_eofbepos_sym16(uint64_t ind);
@@ -14,8 +18,13 @@ static uint64_t    index_drud_sym16(Cube cube);
 static uint64_t    index_drudfin_noE_sym16(Cube cube);
 static uint64_t    index_khuge(Cube cube);
 
+static int         transfinder_drud_sym16(uint64_t ind, Trans *ret);
+static int         transfinder_drudfin_noE_sym16(uint64_t ind, Trans *ret);
+static int         transfinder_khuge(uint64_t ind, Trans *ret);
+
 static void        gensym(SymData *sd);
 static bool        read_symdata_file(SymData *sd);
+static int         selfsims(SymData *sd, uint64_t ind, Trans *ret);
 static bool        write_symdata_file(SymData *sd);
 
 /* Transformation groups and symmetry data ***********************************/
@@ -69,51 +78,42 @@ Coordinate
 coord_eofbepos_sym16 = {
         .index  = index_eofbepos_sym16,
         .cube   = antindex_eofbepos_sym16,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
 };
 
 Coordinate
 coord_coud_sym16 = {
         .index  = index_coud_sym16,
         .cube   = antindex_coud_sym16,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
 };
 
 Coordinate
 coord_cp_sym16 = {
         .index  = index_cp_sym16,
         .cube   = antindex_cp_sym16,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
 };
 
 Coordinate
 coord_drud_sym16 = {
         .index  = index_drud_sym16,
         .cube   = antindex_drud_sym16,
-        .max    = POW3TO7 * 64430,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
+        .max    = POW3TO7 * CLASSES_EOFBEPOS_16,
+        .trans  = transfinder_drud_sym16,
 };
 
 Coordinate
 coord_drudfin_noE_sym16 = {
         .index  = index_drudfin_noE_sym16,
         .cube   = antindex_drudfin_noE_sym16,
-        .max    = FACTORIAL8 * 2768,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
+        .max    = FACTORIAL8 * CLASSES_CP_16,
+        .trans  = transfinder_drudfin_noE_sym16,
 };
 
 Coordinate
 coord_khuge = {
         .index  = index_khuge,
         .cube   = antindex_khuge,
-        .max    = POW3TO7 * FACTORIAL4 * 64430,
-        .ntrans = 16,
-        .trans  = trans_group_udfix,
+        .max    = POW3TO7 * FACTORIAL4 * CLASSES_EOFBEPOS_16,
+        .trans  = transfinder_khuge,
 };
 
 /* Functions *****************************************************************/
@@ -229,6 +229,72 @@ index_khuge(Cube cube)
         return a * POW3TO7 + c.coud;
 }
 
+static int
+transfinder_drud_sym16(uint64_t ind, Trans *ret)
+{
+        uint64_t i, trueind;
+        int j;
+        static bool initialized = false;
+        static int naux[CLASSES_EOFBEPOS_16];
+        static Trans retaux[CLASSES_EOFBEPOS_16][NTRANS];
+
+        if (!initialized) {
+                for (i = 0; i < CLASSES_EOFBEPOS_16; i++)
+                        naux[i] = selfsims(&sd_eofbepos_16, i, retaux[i]);
+
+                initialized = true;
+        }
+
+        trueind = ind/POW3TO7;
+        for (j = 0; j < naux[trueind]; j++)
+                ret[j] = retaux[trueind][j];
+        return naux[trueind];
+}
+
+static int
+transfinder_drudfin_noE_sym16(uint64_t ind, Trans *ret)
+{
+        uint64_t i, trueind;
+        int j;
+        static bool initialized = false;
+        static int naux[CLASSES_CP_16];
+        static Trans retaux[CLASSES_CP_16][NTRANS];
+
+        if (!initialized) {
+                for (i = 0; i < CLASSES_CP_16; i++)
+                        naux[i] = selfsims(&sd_cp_16, i, retaux[i]);
+
+                initialized = true;
+        }
+
+        trueind = ind/FACTORIAL8;
+        for (j = 0; j < naux[trueind]; j++)
+                ret[j] = retaux[trueind][j];
+        return naux[trueind];
+}
+
+static int
+transfinder_khuge(uint64_t ind, Trans *ret)
+{
+        uint64_t i, trueind;
+        int j;
+        static bool initialized = false;
+        static int naux[CLASSES_EOFBEPOS_16];
+        static Trans retaux[CLASSES_EOFBEPOS_16][NTRANS];
+
+        if (!initialized) {
+                for (i = 0; i < CLASSES_EOFBEPOS_16; i++)
+                        naux[i] = selfsims(&sd_eofbepos_16, i, retaux[i]);
+
+                initialized = true;
+        }
+
+        trueind = ind/(FACTORIAL4*POW3TO7);
+        for (j = 0; j < naux[trueind]; j++)
+                ret[j] = retaux[trueind][j];
+        return naux[trueind];
+}
+
 /* Other functions ***********************************************************/
 
 static void
@@ -320,6 +386,25 @@ read_symdata_file(SymData *sd)
         return r;
 }
 
+static int
+selfsims(SymData *sd, uint64_t ind, Trans *ret)
+{
+        Cube cube, tcube;
+        int i, n;
+        uint64_t indnosym;
+
+        cube = sd->sym_coord->cube(ind);
+        indnosym = sd->coord->index(cube);
+        n = 0;
+        for (i = 0; i < sd->ntrans; i++) {
+                tcube = apply_trans(sd->trans[i], cube);
+                if (sd->coord->index(tcube) == indnosym)
+                        ret[n++] = sd->trans[i];
+        }
+
+        return n;
+}
+
 static bool
 write_symdata_file(SymData *sd)
 {