Added a new pruning table (equivalent to nxopt31). I have not tested it yet, it takes a while to generate.

Plus I have done a whole lot of refactoring in random places because I cannot focus on
one thing at the time.

1 files changed, 52 insertions, 43 deletions

diff --git a/src/pruning.c b/src/pruning.c
index b305a89..0a6e305 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -1,11 +1,10 @@
 #include "pruning.h"
 
-/* Chunks for multithreading */
-/* TODO: try smaller */
-#define NCHUNKS    100000
+#define NCHUNKS               100000
+#define ENTRIES_PER_GROUP     (2*sizeof(entry_group_t))
 
 static int         findchunk(PruneData *pd, int nchunks, uint64_t i);
-static void        genptable_bfs(PruneData *pd,int d,Move *ms,int nt,int nc);
+static void        genptable_bfs(PruneData *pd, int d, int nt, int nc);
 static void        genptable_fixnasty(PruneData *pd, int d);
 static void *      instance_bfs(void *arg);
 static void        ptable_update(PruneData *pd, Cube cube, int m);
@@ -18,70 +17,77 @@ PruneData
 pd_eofb_HTM = {
         .filename = "pt_eofb_HTM",
         .coord    = &coord_eofb,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData
 pd_coud_HTM = {
         .filename = "pt_coud_HTM",
         .coord    = &coord_coud,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData
 pd_cornershtr_HTM = {
         .filename = "pt_cornershtr_HTM",
         .coord    = &coord_cornershtr,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData
 pd_corners_HTM = {
         .filename = "pt_corners_HTM",
         .coord    = &coord_corners,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData
 pd_drud_sym16_HTM = {
         .filename = "pt_drud_sym16_HTM",
         .coord    = &coord_drud_sym16,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData
 pd_drud_eofb = {
         .filename = "pt_drud_eofb",
         .coord    = &coord_drud_eofb,
-        .moveset  = moveset_eofb,
+        .moveset  = &moveset_eofb,
 };
 
 PruneData
 pd_drudfin_noE_sym16_drud = {
         .filename = "pt_drudfin_noE_sym16_drud",
         .coord    = &coord_drudfin_noE_sym16,
-        .moveset  = moveset_drud,
+        .moveset  = &moveset_drud,
 };
 
 PruneData
 pd_htr_drud = {
         .filename = "pt_htr_drud",
         .coord    = &coord_htr_drud,
-        .moveset  = moveset_drud,
+        .moveset  = &moveset_drud,
 };
 
 PruneData
 pd_htrfin_htr = {
         .filename = "pt_htrfin_htr",
         .coord    = &coord_htrfin,
-        .moveset  = moveset_htr,
+        .moveset  = &moveset_htr,
 };
 
 PruneData
 pd_khuge_HTM = {
         .filename = "pt_khuge_HTM",
         .coord    = &coord_khuge,
-        .moveset  = moveset_HTM,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_nxopt31_HTM = {
+        .filename = "pt_nxopt31_HTM",
+        .coord    = &coord_nxopt31,
+        .moveset  = &moveset_HTM,
 };
 
 PruneData * allpd[NPTABLES] = {
@@ -95,6 +101,7 @@ PruneData * allpd[NPTABLES] = {
         &pd_htr_drud,
         &pd_htrfin_htr,
         &pd_khuge_HTM,
+        &pd_nxopt31_HTM,
 };
 
 /* Functions *****************************************************************/
@@ -105,8 +112,7 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
         uint64_t chunksize;
 
         chunksize = pd->coord->max / (uint64_t)nchunks;
-        if (chunksize % 2 != 0)
-                chunksize++;
+        chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP);
 
         return MIN(nchunks-1, (int)(i / chunksize));
 }
@@ -114,15 +120,14 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
 void
 genptable(PruneData *pd, int nthreads)
 {
-        Move *ms;
         int d, nchunks;
-        uint64_t j, oldn;
+        uint64_t oldn;
 
         if (pd->generated)
                 return;
 
         /* TODO: check if memory is enough, otherwise maybe exit gracefully? */
-        pd->ptable = malloc(ptablesize(pd) * sizeof(uint8_t));
+        pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
 
         if (read_ptable_file(pd)) {
                 pd->generated = true;
@@ -130,17 +135,12 @@ genptable(PruneData *pd, int nthreads)
         }
         pd->generated = true;
 
-        nchunks = MIN(pd->coord->max/2, NCHUNKS);
+        nchunks = MIN(pd->coord->max/ENTRIES_PER_GROUP, NCHUNKS);
         fprintf(stderr, "Cannot load %s, generating it "
                         "with %d threads and %d chunks\n",
                         pd->filename, nthreads, nchunks); 
 
-        ms = malloc(NMOVES * sizeof(Move));
-        moveset_to_list(pd->moveset, ms);
-
-        /* We use 4 bits per value, so any distance >= 15 is set to 15 */
-        for (j = 0; j < pd->coord->max; j++)
-                ptable_update_index(pd, j, 15);
+        memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t));
 
         ptable_update(pd, (Cube){0}, 0);
         pd->n = 1;
@@ -151,7 +151,7 @@ genptable(PruneData *pd, int nthreads)
                 0, pd->n - oldn, pd->n, pd->coord->max);
         oldn = pd->n;
         for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
-                genptable_bfs(pd, d, ms, nthreads, nchunks);
+                genptable_bfs(pd, d, nthreads, nchunks);
                 genptable_fixnasty(pd, d+1);
                 fprintf(stderr, "Depth %d done, generated %"
                         PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
@@ -162,12 +162,10 @@ genptable(PruneData *pd, int nthreads)
 
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
-
-        free(ms);
 }
 
 static void
-genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks)
+genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
 {
         int i;
         pthread_t t[nthreads];
@@ -186,7 +184,6 @@ genptable_bfs(PruneData *pd, int d, Move *ms, int nthreads, int nchunks)
                 td[i].nthreads = nthreads;
                 td[i].pd       = pd;
                 td[i].d        = d;
-                td[i].ms       = ms;
                 td[i].nchunks  = nchunks;
                 td[i].mutex    = mtx;
                 td[i].upmutex  = upmtx;
@@ -237,8 +234,10 @@ instance_bfs(void *arg)
         uint64_t i, ii, blocksize, rmin, rmax, updated;
         int j, pval, ichunk;
         Cube c, cc;
+        Move *ms;
 
         td = (ThreadDataGenpt *)arg;
+        ms = td->pd->moveset->sorted_moves;
         blocksize = td->pd->coord->max / (uint64_t)td->nthreads;
         rmin = ((uint64_t)td->thid) * blocksize;
         rmax = td->thid == td->nthreads - 1 ?
@@ -253,8 +252,8 @@ instance_bfs(void *arg)
                 pthread_mutex_unlock(td->mutex[ichunk]);
                 if (pval == td->d) {
                         c = td->pd->coord->cube(i);
-                        for (j = 0; td->ms[j] != NULLMOVE; j++) {
-                                cc = apply_move(td->ms[j], c);
+                        for (j = 0; ms[j] != NULLMOVE; j++) {
+                                cc = apply_move(ms[j], c);
                                 ii = td->pd->coord->index(cc);
                                 ichunk = findchunk(td->pd, td->nchunks, ii);
                                 pthread_mutex_lock(td->mutex[ichunk]);
@@ -296,7 +295,7 @@ print_ptable(PruneData *pd)
 uint64_t
 ptablesize(PruneData *pd)
 {
-        return (pd->coord->max + 1) / 2;
+        return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP;
 }
 
 static void
@@ -308,14 +307,16 @@ ptable_update(PruneData *pd, Cube cube, int n)
 static void
 ptable_update_index(PruneData *pd, uint64_t ind, int n)
 {
-        uint8_t oldval2;
-        int other;
+        int sh;
+        entry_group_t mask;
+        uint64_t i;
 
-        oldval2 = pd->ptable[ind/2];
-        other = (ind % 2) ? oldval2 % 16 : oldval2 / 16;
+        sh = 4 * (ind % ENTRIES_PER_GROUP);
+        mask = ((entry_group_t)15) << sh;
+        i = ind/ENTRIES_PER_GROUP;
 
-        pd->ptable[ind/2] = (ind % 2) ? 16*n + other : 16*other + n;
-        /*pd->n++;*/
+        pd->ptable[i] &= ~mask;
+        pd->ptable[i] |= (((entry_group_t)n)&15) << sh;
 }
 
 int
@@ -327,6 +328,10 @@ ptableval(PruneData *pd, Cube cube)
 static int
 ptableval_index(PruneData *pd, uint64_t ind)
 {
+        int sh;
+        entry_group_t mask;
+        uint64_t i;
+
         if (!pd->generated) {
                 fprintf(stderr, "Warning: request pruning table value"
                         " for uninitialized table %s.\n It's fine, but it"
@@ -335,7 +340,11 @@ ptableval_index(PruneData *pd, uint64_t ind)
                 genptable(pd, 1); /* TODO: set default or remove this case */
         }
 
-        return (ind % 2) ? pd->ptable[ind/2] / 16 : pd->ptable[ind/2] % 16;
+        sh = 4 * (ind % ENTRIES_PER_GROUP);
+        mask = ((entry_group_t)15) << sh;
+        i = ind/ENTRIES_PER_GROUP;
+
+        return (pd->ptable[i] & mask) >> sh;
 }
 
 static bool
@@ -354,7 +363,7 @@ read_ptable_file(PruneData *pd)
         if ((f = fopen(fname, "rb")) == NULL)
                 return false;
 
-        r = fread(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
+        r = fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
         fclose(f);
 
         return r == ptablesize(pd);
@@ -376,7 +385,7 @@ write_ptable_file(PruneData *pd)
         if ((f = fopen(fname, "wb")) == NULL)
                 return false;
 
-        written = fwrite(pd->ptable, sizeof(uint8_t), ptablesize(pd), f);
+        written = fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
         fclose(f);
 
         return written == ptablesize(pd);