Reverted to 2.0.3

1 files changed, 252 insertions, 119 deletions

diff --git a/src/pruning.c b/src/pruning.c
index 3cc9152..1dba949 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -1,5 +1,3 @@
-#define PRUNING_C
-
 #include "pruning.h"
 
 #define ENTRIES_PER_GROUP              (2*sizeof(entry_group_t))
@@ -7,14 +5,106 @@
 
 static int         findchunk(PruneData *pd, int nchunks, uint64_t i);
 static void        genptable_bfs(PruneData *pd, int d, int nt, int nc);
+static void        genptable_compress(PruneData *pd);
 static void        genptable_fixnasty(PruneData *pd, int d, int nthreads);
+static void        genptable_setbase(PruneData *pd);
 static void *      instance_bfs(void *arg);
 static void *      instance_fixnasty(void *arg);
-static void        ptable_update(PruneData *pd, uint64_t ind, int m);
+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);
 static bool        read_ptable_file(PruneData *pd);
 static bool        write_ptable_file(PruneData *pd);
 
-PruneData *active_pd[256];
+PruneData
+pd_eofb_HTM = {
+        .filename = "pt_eofb_HTM",
+        .coord    = &coord_eofb,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_coud_HTM = {
+        .filename = "pt_coud_HTM",
+        .coord    = &coord_coud,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_cornershtr_HTM = {
+        .filename = "pt_cornershtr_HTM",
+        .coord    = &coord_cornershtr,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_corners_HTM = {
+        .filename = "pt_corners_HTM",
+        .coord    = &coord_corners,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_drud_sym16_HTM = {
+        .filename = "pt_drud_sym16_HTM",
+        .coord    = &coord_drud_sym16,
+        .moveset  = &moveset_HTM,
+};
+
+PruneData
+pd_drud_eofb = {
+        .filename = "pt_drud_eofb",
+        .coord    = &coord_drud_eofb,
+        .moveset  = &moveset_eofb,
+};
+
+PruneData
+pd_drudfin_noE_sym16_drud = {
+        .filename = "pt_drudfin_noE_sym16_drud",
+        .coord    = &coord_drudfin_noE_sym16,
+        .moveset  = &moveset_drud,
+};
+
+PruneData
+pd_htr_drud = {
+        .filename = "pt_htr_drud",
+        .coord    = &coord_htr_drud,
+        .moveset  = &moveset_drud,
+};
+
+PruneData
+pd_htrfin_htr = {
+        .filename = "pt_htrfin_htr",
+        .coord    = &coord_htrfin,
+        .moveset  = &moveset_htr,
+};
+
+PruneData
+pd_nxopt31_HTM = {
+        .filename = "pt_nxopt31_HTM",
+        .coord    = &coord_nxopt31,
+        .moveset  = &moveset_HTM,
+
+        .compact  = true,
+        .fallback = &pd_drud_sym16_HTM,
+        .fbmod    = BINOM8ON4,
+};
+
+PruneData * all_pd[] = {
+        &pd_eofb_HTM,
+        &pd_coud_HTM,
+        &pd_cornershtr_HTM,
+        &pd_corners_HTM,
+        &pd_drud_sym16_HTM,
+        &pd_drud_eofb,
+        &pd_drudfin_noE_sym16_drud,
+        &pd_htr_drud,
+        &pd_htrfin_htr,
+        &pd_nxopt31_HTM,
+        NULL
+};
+
+/* Functions *****************************************************************/
 
 int
 findchunk(PruneData *pd, int nchunks, uint64_t i)
@@ -27,47 +117,59 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
         return MIN(nchunks-1, (int)(i / chunksize));
 }
 
-PruneData *
-genptable(PruneData *pd, int nthreads)
+void
+free_pd(PruneData *pd)
 {
-        int d, nchunks, i, maxv;
-        uint64_t oldn;
+        if (pd->generated)
+                free(pd->ptable);
 
-        for (i = 0; active_pd[i] != NULL; i++) {
-                if (active_pd[i]->coord == pd->coord &&
-                    active_pd[i]->moveset == pd->moveset &&
-                    active_pd[i]->compact == pd->compact)
-                        return active_pd[i];
-        }
+        pd->generated = false;
+}
+
+void
+genptable(PruneData *pd, int nthreads)
+{
+        bool compact;
+        int d, nchunks;
+        uint64_t oldn, sz;
 
-        init_moveset(pd->moveset);
-        gen_coord(pd->coord);
+        if (pd->generated)
+                return;
 
-        pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
+        /* TODO: check if memory is enough, otherwise maybe exit gracefully? */
+        sz = ptablesize(pd) * (pd->compact ? 2 : 1);
+        pd->ptable = malloc(sz * sizeof(entry_group_t));
 
-        if (read_ptable_file(pd))
-                goto genptable_done;
+        if (read_ptable_file(pd)) {
+                pd->generated = true;
+                return;
+        }
 
         if (nthreads < 4) {
                 fprintf(stderr,
                         "--- Warning ---\n"
                         "You are using only %d threads to generate the pruning"
-                        "tables. This can take a while.\n"
+                        "tables. This can take a while."
                         "Unless you did this intentionally, you should re-run"
                         "this command with `-t 4' or more.\n"
                         "---------------\n\n", nthreads
                 );
         }
 
+
+        /* For the first steps we proceed the same way for compact and not */
+        compact = pd->compact;
+        pd->compact = false;
+        pd->generated = true;
+
         nchunks = MIN(ptablesize(pd), 100000);
-        fprintf(stderr, "Generating pt_%s_%s with %d threads\n",
-                        pd->coord->name, pd->moveset->name, nthreads); 
+        fprintf(stderr, "Cannot load %s, generating it with %d threads\n",
+                        pd->filename, nthreads); 
+
 
         memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t));
-        for (i = 0; i < 16; i++)
-                pd->count[i] = 0;
 
-        ptable_update(pd, 0, 0);
+        ptable_update(pd, (Cube){0}, 0);
         pd->n = 1;
         oldn = 0;
         genptable_fixnasty(pd, 0, nthreads);
@@ -76,9 +178,7 @@ genptable(PruneData *pd, int nthreads)
                 0, pd->n - oldn, pd->n, pd->coord->max);
         oldn = pd->n;
         pd->count[0] = pd->n;
-
-        maxv = pd->compact ? MIN(15, pd->base + 4) : 15;
-        for (d = 0; d < maxv && pd->n < pd->coord->max; d++) {
+        for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
                 genptable_bfs(pd, d, nthreads, nchunks);
                 genptable_fixnasty(pd, d+1, nthreads);
                 fprintf(stderr, "Depth %d done, generated %"
@@ -87,17 +187,14 @@ genptable(PruneData *pd, int nthreads)
                 pd->count[d+1] = pd->n - oldn;
                 oldn = pd->n;
         }
-        if (pd->compact)
-                fprintf(stderr, "Compact table, values above "
-                                "%d are inaccurate.\n", maxv-1);
         fprintf(stderr, "Pruning table generated!\n");
-
+        
+        genptable_setbase(pd);
+        if (compact)
+                genptable_compress(pd);
+        
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
-
-genptable_done:
-        for (i = 0; active_pd[i] != NULL; i++);
-        return active_pd[i] = pd;
 }
 
 static void
@@ -135,6 +232,31 @@ genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
 }
 
 static void
+genptable_compress(PruneData *pd)
+{
+        int val;
+        uint64_t i, j;
+        entry_group_t mask, v;
+
+        fprintf(stderr, "Compressing table to 2 bits per entry\n");
+
+        for (i = 0; i < pd->coord->max; i += ENTRIES_PER_GROUP_COMPACT) {
+                mask = (entry_group_t)0;
+                for (j = 0; j < ENTRIES_PER_GROUP_COMPACT; j++) {
+                        if (i+j >= pd->coord->max)
+                                break;
+                        val = ptableval_index(pd, i+j) - pd->base;
+                        v = (entry_group_t)MIN(3, MAX(0, val));
+                        mask |= v << (2*j);
+                }
+                pd->ptable[i/ENTRIES_PER_GROUP_COMPACT] = mask;
+        }
+
+        pd->compact = true;
+        pd->ptable = realloc(pd->ptable, sizeof(entry_group_t)*ptablesize(pd));
+}
+
+static void
 genptable_fixnasty(PruneData *pd, int d, int nthreads)
 {
         int i;
@@ -142,7 +264,7 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads)
         ThreadDataGenpt td[nthreads];
         pthread_mutex_t *upmtx;
 
-        if (pd->coord->type != SYMCOMP_COORD)
+        if (pd->coord->tfind == NULL)
                 return;
 
         upmtx = malloc(sizeof(pthread_mutex_t));
@@ -162,12 +284,28 @@ genptable_fixnasty(PruneData *pd, int d, int nthreads)
         free(upmtx);
 }
 
+static void
+genptable_setbase(PruneData *pd)
+{
+        int i;
+        uint64_t sum, newsum;
+
+        pd->base = 0;
+        sum = pd->count[0] + pd->count[1] + pd->count[2];
+        for (i = 3; i < 16; i++) {
+                newsum = sum + pd->count[i] - pd->count[i-3];
+                if (newsum > sum)
+                        pd->base = i-3;
+                sum = newsum;
+        }
+}
+
 static void *
 instance_bfs(void *arg)
 {
         ThreadDataGenpt *td;
         uint64_t i, ii, blocksize, rmin, rmax, updated;
-        int j, pval, ichunk, oldc, newc;
+        int j, pval, ichunk;
         Move *ms;
 
         td = (ThreadDataGenpt *)arg;
@@ -178,43 +316,25 @@ instance_bfs(void *arg)
                td->pd->coord->max :
                ((uint64_t)td->thid + 1) * blocksize;
 
-        if (td->pd->compact) {
-                if (td->d <= td->pd->base) {
-                        oldc = 1;
-                        newc = 1;
-                } else {
-                        oldc = td->d - td->pd->base;
-                        newc = td->d - td->pd->base;
-                }
-        } else {
-                oldc = td->d;
-                newc = td->d + 1;
-        }
-
         updated = 0;
         for (i = rmin; i < rmax; i++) {
                 ichunk = findchunk(td->pd, td->nchunks, i);
                 pthread_mutex_lock(td->mutex[ichunk]);
-                pval = ptableval(td->pd, i);
+                pval = ptableval_index(td->pd, i);
                 pthread_mutex_unlock(td->mutex[ichunk]);
-                if (pval == oldc) {
+                if (pval == td->d) {
                         for (j = 0; ms[j] != NULLMOVE; j++) {
-                                ii = move_coord(td->pd->coord, ms[j], i, NULL);
+                                ii = td->pd->coord->move(ms[j], i);
                                 ichunk = findchunk(td->pd, td->nchunks, ii);
                                 pthread_mutex_lock(td->mutex[ichunk]);
-                                pval = ptableval(td->pd, ii);
-                                if (pval > newc) {
-                                        ptable_update(td->pd, ii, newc);
+                                pval = ptableval_index(td->pd, ii);
+                                if (pval > td->d+1) {
+                                        ptable_update_index(td->pd,
+                                            ii, td->d+1);
                                         updated++;
                                 }
                                 pthread_mutex_unlock(td->mutex[ichunk]);
                         }
-                        if (td->pd->compact && td->d <= td->pd->base) {
-                                ichunk = findchunk(td->pd, td->nchunks, i);
-                                pthread_mutex_lock(td->mutex[ichunk]);
-                                ptable_update(td->pd, i, 0);
-                                pthread_mutex_unlock(td->mutex[ichunk]);
-                        }
                 }
         }
 
@@ -229,40 +349,30 @@ static void *
 instance_fixnasty(void *arg)
 {
         ThreadDataGenpt *td;
-        uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M;
-        int j, oldc;
-        Trans t;
+        uint64_t i, ii, nb, blocksize, rmin, rmax, updated;
+        int j, n;
+        Trans t, aux[NTRANS];
 
         td = (ThreadDataGenpt *)arg;
-
-        /* We know type = SYMCOMP_COORD */
-        M = td->pd->coord->base[1]->max;
-        blocksize = (td->pd->coord->base[0]->max / td->nthreads) * M;
+        nb = td->pd->coord->max / td->pd->coord->base->max;
+        blocksize = (td->pd->coord->base->max / td->nthreads) * nb;
         rmin = ((uint64_t)td->thid) * blocksize;
         rmax = td->thid == td->nthreads - 1 ?
                td->pd->coord->max :
                ((uint64_t)td->thid + 1) * blocksize;
 
-        if (td->pd->compact) {
-                if (td->d <= td->pd->base)
-                        oldc = 1;
-                else
-                        oldc = td->d - td->pd->base;
-        } else {
-                oldc = td->d;
-        }
-
         updated = 0;
         for (i = rmin; i < rmax; i++) {
-                if (ptableval(td->pd, i) == oldc) {
-                        ss = td->pd->coord->base[0]->selfsim[i/M];
-                        for (j = 0; j < td->pd->coord->base[0]->tgrp->n; j++) {
-                                t = td->pd->coord->base[0]->tgrp->t[j];
-                                if (t == uf || !(ss & ((uint64_t)1<<t)))
+                if (ptableval_index(td->pd, i) == td->d) {
+                        if ((n = td->pd->coord->tfind(i, aux)) == 1)
+                                continue;
+
+                        for (j = 0; j < n; j++) {
+                                if ((t = aux[j]) == uf)
                                         continue;
-                                ii = trans_coord(td->pd->coord, t, i);
-                                if (ptableval(td->pd, ii) > oldc) {
-                                        ptable_update(td->pd, ii, oldc);
+                                ii = td->pd->coord->transform(t, i);
+                                if (ptableval_index(td->pd, ii) > td->d) {
+                                        ptable_update_index(td->pd, ii, td->d);
                                         updated++;
                                 }
                         }
@@ -281,13 +391,11 @@ print_ptable(PruneData *pd)
 {
         uint64_t i;
 
-        printf("Table %s_%s\n", pd->coord->name, pd->moveset->name);
-
-        if (pd->compact) {
-                printf("Compract table with base value: %d\n", pd->base);
-                printf("Values above %d are inaccurate.\n", pd->base + 3);
-        }
-
+        if (!pd->generated)
+                genptable(pd, 1); /* TODO: set default nthreads somewhere */
+                
+        printf("Table %s\n", pd->filename);
+        printf("Base value: %d\n", pd->base);
         for (i = 0; i < 16; i++)
                 printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
 }
@@ -303,31 +411,48 @@ ptablesize(PruneData *pd)
 }
 
 static void
-ptable_update(PruneData *pd, uint64_t ind, int n)
+ptable_update(PruneData *pd, Cube cube, int n)
 {
-        int sh;
-        entry_group_t f, mask;
-        uint64_t i, e, b;
+        ptable_update_index(pd, pd->coord->index(cube), n);
+}
 
-        e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
-        b = pd->compact ? 2 : 4;
-        f = pd->compact ? 3 : 15;
+static void
+ptable_update_index(PruneData *pd, uint64_t ind, int n)
+{
+        int sh;
+        entry_group_t mask;
+        uint64_t i;
 
-        sh = b * (ind % e);
-        mask = f << sh;
-        i = ind / e;
+        sh = 4 * (ind % ENTRIES_PER_GROUP);
+        mask = ((entry_group_t)15) << sh;
+        i = ind/ENTRIES_PER_GROUP;
 
         pd->ptable[i] &= ~mask;
-        pd->ptable[i] |= (((entry_group_t)n) & f) << sh;
+        pd->ptable[i] |= (((entry_group_t)n)&15) << sh;
 }
 
 int
-ptableval(PruneData *pd, uint64_t ind)
+ptableval(PruneData *pd, Cube cube)
 {
-        int sh;
-        uint64_t e;
+        return ptableval_index(pd, pd->coord->index(cube));
+}
+
+static int
+ptableval_index(PruneData *pd, uint64_t ind)
+{
+        int sh, ret;
+        entry_group_t mask;
+        uint64_t i, e;
         entry_group_t m;
 
+        if (!pd->generated) {
+                fprintf(stderr, "Warning: request pruning table value"
+                        " for uninitialized table %s.\n It's fine, but it"
+                        " should not happen. Please report bug.\n",
+                        pd->filename);
+                genptable(pd, 1); /* TODO: set default or remove this case */
+        }
+
         if (pd->compact) {
                 e  = ENTRIES_PER_GROUP_COMPACT;
                 m  = 3;
@@ -338,7 +463,19 @@ ptableval(PruneData *pd, uint64_t ind)
                 sh = (ind % e) * 4;
         }
 
-        return (pd->ptable[ind/e] & (m << sh)) >> sh;
+        mask = m << sh;
+        i = ind/e;
+
+        ret = (pd->ptable[i] & mask) >> sh;
+
+        if (pd->compact) {
+                if (ret)
+                        ret += pd->base;
+                else
+                        ret = ptableval_index(pd->fallback, ind / pd->fbmod);
+        }
+
+        return ret;
 }
 
 static bool
@@ -347,15 +484,13 @@ read_ptable_file(PruneData *pd)
         init_env();
 
         FILE *f;
-        char fname[strlen(tabledir)+256];
+        char fname[strlen(tabledir)+100];
         int i;
         uint64_t r;
 
         strcpy(fname, tabledir);
-        strcat(fname, "/pt_");
-        strcat(fname, pd->coord->name);
-        strcat(fname, "_");
-        strcat(fname, pd->moveset->name);
+        strcat(fname, "/");
+        strcat(fname, pd->filename);
 
         if ((f = fopen(fname, "rb")) == NULL)
                 return false;
@@ -376,15 +511,13 @@ write_ptable_file(PruneData *pd)
         init_env();
 
         FILE *f;
-        char fname[strlen(tabledir)+256];
+        char fname[strlen(tabledir)+100];
         int i;
         uint64_t w;
 
         strcpy(fname, tabledir);
-        strcat(fname, "/pt_");
-        strcat(fname, pd->coord->name);
-        strcat(fname, "_");
-        strcat(fname, pd->moveset->name);
+        strcat(fname, "/");
+        strcat(fname, pd->filename);
 
         if ((f = fopen(fname, "wb")) == NULL)
                 return false;