6 files changed, 155 insertions, 26 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..d9168a4
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1 @@
+nissy.o
diff --git a/README.md b/README.md
index fc71f2d..de56f9d 100644
--- a/README.md
+++ b/README.md
@@ -109,8 +109,9 @@ table to solving EO with HTM moveset and this coordinate would have values 0 (fo
 There is one caveat: each coordinates also needs an inverse function that takes a
 coordinate value and returns a cube which has that coordinate. This is in general
 more complicated, but luckily the cube does not need to be fully built or consistent.
-This inverse-coordinate is used only in one specific step when building pruning tables
-to avoid using up hundreds of Gb of memory.
+This inverse-coordinate is used only in one specific step when generating symmetry
+data, and I don't know if it is possible to avoid it (maybe it is). It is also used
+when building pruning tables, but in that case it is avoidable.
 
 Note: this part is different from what Cube Explorer does. Overall I think it is
 conceptually easier, although in practice it was still hard to implement.
diff --git a/src/coord.c b/src/coord.c
index 7e691ef..059a7a2 100644
--- a/src/coord.c
+++ b/src/coord.c
@@ -171,7 +171,7 @@ antindex_eofbepos(uint64_t ind)
 
         /* We need eorl for sym16 coordinate */
         static int initialized = false;
-        static uint64_t eorl_aux[POW2TO11][BINOM12ON4];
+        static uint64_t eorl_a[POW2TO11][BINOM12ON4];
         static int eo_aux[12], ep_aux[12];
         unsigned int i, j, k;
 
@@ -181,8 +181,10 @@ antindex_eofbepos(uint64_t ind)
                                 int_to_sum_zero_array(i, 2, 12, eo_aux);
                                 index_to_subset(j, 12, 4, ep_aux);
                                 for (k = 0; k < 12; k++)
-                                        if (ep_aux[k])
+                                        if ((ep_aux[k] && k <  FR) ||
+                                           (!ep_aux[k] && k >= FR))
                                                 eo_aux[k] = 1 - eo_aux[k];
+                                eorl_a[i][j] = digit_array_to_int(eo_aux,11,2);
                         }
                 }
 
@@ -191,7 +193,7 @@ antindex_eofbepos(uint64_t ind)
 
         ret.eofb = ind % POW2TO11;
         ret.epose = (ind / POW2TO11) * 24;
-        ret.eorl = eorl_aux[ret.eofb][ret.epose/24];
+        ret.eorl = eorl_a[ret.eofb][ret.epose/24];
 
         return ret;
 }
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 6602a68..da8ab6b 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -213,6 +213,7 @@ dfsdata
         Alg *           current_alg;
         Move            sorted_moves[NMOVES];
         int             move_position[NMOVES];
+        uint8_t *       visited;
 };
 
 struct
diff --git a/src/pruning.c b/src/pruning.c
index b7fedd4..ca6f57a 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -1,7 +1,20 @@
 #include "pruning.h"
 
+/*
+ * The commented functions are a way to generate a pruning table
+ * without using anti-indexes. It does not matter too much because
+ * we still need anti-indexes in gensym.
+ */
+/*
+static bool        dfs_get_visited(PruneData *pd, DfsData *dd, Cube c);
+static bool        dfs_get_visited_index(DfsData *dd, uint64_t ind);
+static void        dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b);
+static void        dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b);
+static void        genptable_dfs(Cube c, PruneData *pd, DfsData *dd);
+*/
+
 static void        genptable_bfs(PruneData *pd, int d, Move *ms);
-static void        genptable_branch(PruneData *pd, uint64_t i, int d, Move *m);
+static void        genptable_branch(PruneData *pd,uint64_t ind,int d,Move *ms);
 static void        ptable_update(PruneData *pd, Cube cube, int m);
 static void        ptable_update_index(PruneData *pd, uint64_t ind, int m);
 static int         ptableval_index(PruneData *pd, uint64_t ind);
@@ -78,6 +91,54 @@ pd_khuge_HTM = {
         .moveset  = moveset_HTM,
 };
 
+/*
+void
+genptable(PruneData *pd)
+{
+        Move ms[NMOVES];
+        uint64_t j, oldn;
+        DfsData dd;
+
+        if (pd->generated)
+                return;
+
+        pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
+
+        if (read_ptable_file(pd)) {
+                pd->generated = true;
+                return;
+        }
+        pd->generated = true;
+
+        fprintf(stderr, "Cannot load %s, generating it\n", pd->filename); 
+
+        moveset_to_list(pd->moveset, ms);
+
+        for (j = 0; j < pd->coord->max; j++)
+                ptable_update_index(pd, j, 15);
+
+        dd = (DfsData) { .m = 0 };
+        dd.visited = malloc((ptablesize(pd)/4 + 1) * sizeof(uint8_t));
+        moveset_to_list(pd->moveset, dd.sorted_moves);
+        oldn = 0;
+        pd->n = 0;
+
+        for (dd.d = 0; dd.d < 15 && pd->n < pd->coord->max; dd.d++) {
+                for (j = 0; j < pd->coord->max; j++)
+                        dfs_set_visited_index(&dd, j, false);
+                genptable_dfs((Cube){0}, pd, &dd);
+                fprintf(stderr, "Depth %d done, generated %lu\t(%lu/%lu)\n",
+                        dd.d+1, pd->n - oldn, pd->n, pd->coord->max);
+                oldn = pd->n;
+        }
+
+        if (!write_ptable_file(pd))
+                fprintf(stderr, "Error writing ptable file\n");
+
+        free(dd.visited);
+}
+*/
+
 void
 genptable(PruneData *pd)
 {
@@ -105,13 +166,6 @@ genptable(PruneData *pd)
         for (j = 0; j < pd->coord->max; j++)
                 ptable_update_index(pd, j, 15);
 
-        for (j = 0; j < pd->coord->max; j++)
-                if (ptableval_index(pd, j) != 15) {
-                        printf("Error, non-max value at index %lu!\n", j);
-                        break;
-                }
-        printf("Table set, ready to start\n");
-
         ptable_update(pd, (Cube){0}, 0);
         pd->n = 1;
         oldn = 0;
@@ -127,7 +181,81 @@ genptable(PruneData *pd)
 
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
+
+}
+
+/*
+static void
+genptable_dfs(Cube c, PruneData *pd, DfsData *dd)
+{
+        int i, j, pv;
+        Move mm;
+        Cube cc;
+
+        if (pd->coord->index(c) > 2*ptablesize(pd)) {
+                printf("error! %lu > %lu\n", pd->coord->index(c), 2*ptablesize(pd));
+                print_cube(c);
+                exit(1);
+        }
+        pv = ptableval(pd, c);
+
+        if (pv < dd->m || dd->m > dd->d)
+                return;
+
+        if (dfs_get_visited(pd, dd, c))
+                return;
+        dfs_set_visited(pd, dd, c, true);
+
+        if (pv != dd->m)
+                ptable_update(pd, c, dd->m);
+
+        for (i = 0; i < pd->coord->ntrans; i++) {
+                cc = i == 0 ? c :
+                              apply_trans(pd->coord->trans[i], c);
+                for (j = 0; dd->sorted_moves[j] != NULLMOVE; j++) {
+                        mm = dd->sorted_moves[j];
+                        dd->m++;
+                        genptable_dfs(apply_move(mm, cc), pd, dd);
+                        dd->m--;
+                }
+        }
+}
+*/
+
+/*
+static bool
+dfs_get_visited(PruneData *pd, DfsData *dd, Cube c)
+{
+        return dfs_get_visited_index(dd, pd->coord->index(c));
+}
+*/
+
+/*
+static bool
+dfs_get_visited_index(DfsData *dd, uint64_t ind)
+{
+        return dd->visited[ind/8] & ((uint8_t)1 << (ind % 8));
+}
+*/
+
+/*
+static void
+dfs_set_visited(PruneData *pd, DfsData *dd, Cube c, bool b)
+{
+        dfs_set_visited_index(dd, pd->coord->index(c), b);
+}
+*/
+
+/*
+static void
+dfs_set_visited_index(DfsData *dd, uint64_t ind, bool b)
+{
+        if (b)
+                dd->visited[ind/8] |= ((uint8_t)1 << (ind % 8));
+        else
+                dd->visited[ind/8] &= ~((uint8_t)1 << (ind % 8));
 }
+*/
 
 static void
 genptable_bfs(PruneData *pd, int d, Move *ms)
@@ -145,22 +273,9 @@ genptable_branch(PruneData *pd, uint64_t ind, int d, Move *ms)
         int i, j;
         Cube ci, cc, c;
 
-        /*
-         * This is the only line of the whole program where we REALLY need an
-         * anti-indexer function. We could get rid of it if only we could save
-         * a cube object for each index value as we go, but then we would need
-         * an incredible amount of memory to generate each ptable: assuming
-         * fields in struct cube are 32 bit ints that would take 88 times the
-         * memory of the table to be generated, more than 120Gb for
-         * ptable_khuge for example!
-         *
-         * TODO: it would be nice to get rid of this...
-         *
-         */
         ci = pd->coord->cube(ind);
 
         for (i = 0; i < pd->coord->ntrans; i++) {
-                /* For simplicity trans[] is NULL when ntrans = 1 */
                 c = i == 0 ? ci :
                              apply_trans(pd->coord->trans[i], ci);
                 for (j = 0; ms[j] != NULLMOVE; j++) {
diff --git a/src/symcoord.c b/src/symcoord.c
index 97a8d9a..e9374d7 100644
--- a/src/symcoord.c
+++ b/src/symcoord.c
@@ -257,7 +257,16 @@ gensym(SymData *sd)
 
         for (i = 0; i < sd->coord->max; i++) {
                 if (sd->class[i] == sd->coord->max + 1) {
+                
+                        /*
+                         * TODO: this is the only unavoidable use of
+                         * antindexes. I also use them in genptable() (see
+                         * pruning.c), but there I can do without (see
+                         * commented functions in that file.
+                         * Removing this would allow for a great simplification
+                         */
                         c = sd->coord->cube(i);
+
                         sd->rep[nreps] = c;
                         for (j = 0; j < sd->ntrans; j++) {
                                 d = apply_trans(sd->trans[j], c);