commit a0b89016dc7ea42fe8af0aeb956fd383cd1b66f1
parent 131428b913a3d42f26714b8e5e873d8112db10c0
Author: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Wed, 8 Dec 2021 17:38:42 +0100
Faster and nice pruning table generation. Can still be improved with multithreading.
Diffstat:
5 files changed, 110 insertions(+), 38 deletions(-)
diff --git a/nissy b/nissy
Binary files differ.
diff --git 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
@@ -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
@@ -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
@@ -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)
{
