I tried to remove the dependence on antindex in order to get rid of them

once and for all. I successfully removed from the pruning table generation
part by using an alternative (slower) method, but then I realized that I also
use antindexes when generating symmetry data. So I reverted to the original
pruning table computation method, but I left the alternative way there, commented.

1 files changed, 136 insertions, 21 deletions

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++) {