Modified pruning table generation (new compressed) + website update

7 files changed, 110 insertions, 70 deletions

diff --git a/TODO.md b/TODO.md
index fb57dd1..30803fb 100644
--- a/TODO.md
+++ b/TODO.md
@@ -8,13 +8,9 @@ It's more of a personal reminder than anything else.
 * add Void * extradata to DfsArg and a custom move function
 * add optional custom pre-process for generating special table (nx)
 * copy_dfsdata should copy extra too!
-* Pruning: remove base value?
 ### nx.c
 * implement nxopt with all tables and all tricks
   (maybe compile time variable for maximum memory to use?)
-* custom pruning table, copy some code from pruning.h
-* generate compressed: hard-code the base value, doable!
-* special type of pruning table with fallback and whatnot
 * is_valid should also unniss / cleanup the alg
 ### fst_cube
 * slightly different from cube in v2.0.2: each "side" coordinate
diff --git a/src/cubetypes.h b/src/cubetypes.h
index fa19f6c..f9b4011 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -93,7 +93,6 @@ typedef struct dfsarg             DfsArg;
 typedef struct indexer            Indexer;
 typedef struct movable            Movable;
 typedef struct moveset            Moveset;
-typedef struct pdgendata          PDGenData;
 typedef struct prunedata          PruneData;
 typedef struct solveoptions       SolveOptions;
 typedef struct step               Step;
@@ -245,14 +244,6 @@ moveset
 };
 
 struct
-pdgendata
-{
-        Coordinate *              coord;
-        Moveset *                 moveset;
-        PruneData *               pd;
-};
-
-struct
 prunedata
 {
         entry_group_t *           ptable;
@@ -260,6 +251,8 @@ prunedata
         Coordinate *              coord;
         Moveset *                 moveset;
         uint64_t                  count[16];
+        bool                      compact;
+        int                       base;
 };
 
 struct
@@ -287,6 +280,7 @@ step
         Coordinate *              coord[MAX_N_COORD];
         Trans                     coord_trans[MAX_N_COORD];
         PruneData *               pd[MAX_N_COORD];
+        bool                      pd_compact[MAX_N_COORD];
         Validator                 is_valid;
         DfsMover                  custom_move_checkstop;
         DfsExtraCopier            copy_extra;
diff --git a/src/pruning.c b/src/pruning.c
index 2e30351..3cc9152 100644
--- a/src/pruning.c
+++ b/src/pruning.c
@@ -3,6 +3,7 @@
 #include "pruning.h"
 
 #define ENTRIES_PER_GROUP              (2*sizeof(entry_group_t))
+#define ENTRIES_PER_GROUP_COMPACT      (4*sizeof(entry_group_t))
 
 static int         findchunk(PruneData *pd, int nchunks, uint64_t i);
 static void        genptable_bfs(PruneData *pd, int d, int nt, int nc);
@@ -13,7 +14,7 @@ static void        ptable_update(PruneData *pd, uint64_t ind, int m);
 static bool        read_ptable_file(PruneData *pd);
 static bool        write_ptable_file(PruneData *pd);
 
-PDGenData *active_pdg[256];
+PruneData *active_pd[256];
 
 int
 findchunk(PruneData *pd, int nchunks, uint64_t i)
@@ -27,26 +28,23 @@ findchunk(PruneData *pd, int nchunks, uint64_t i)
 }
 
 PruneData *
-genptable(PDGenData *pdg, int nthreads)
+genptable(PruneData *pd, int nthreads)
 {
-        int d, nchunks, i;
+        int d, nchunks, i, maxv;
         uint64_t oldn;
-        PruneData *pd;
 
-        for (i = 0; active_pdg[i] != NULL; i++) {
-                pd = active_pdg[i]->pd;
-                if (pd->coord == pdg->coord && pd->moveset == pdg->moveset)
-                        return pd;
+        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 = malloc(sizeof(PruneData));
-        pdg->pd = pd;
-        pd->coord   = pdg->coord;
-        pd->moveset = pdg->moveset;
-        pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
-
+        init_moveset(pd->moveset);
         gen_coord(pd->coord);
 
+        pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
+
         if (read_ptable_file(pd))
                 goto genptable_done;
 
@@ -78,7 +76,9 @@ genptable(PDGenData *pdg, int nthreads)
                 0, pd->n - oldn, pd->n, pd->coord->max);
         oldn = pd->n;
         pd->count[0] = pd->n;
-        for (d = 0; d < 15 && pd->n < pd->coord->max; d++) {
+
+        maxv = pd->compact ? MIN(15, pd->base + 4) : 15;
+        for (d = 0; d < maxv && 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,19 +87,17 @@ genptable(PDGenData *pdg, 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");
 
         if (!write_ptable_file(pd))
                 fprintf(stderr, "Error writing ptable file\n");
 
 genptable_done:
-        for (i = 0; active_pdg[i] != NULL; i++);
-        active_pdg[i] = malloc(sizeof(PDGenData));
-        active_pdg[i]->coord   = pdg->coord;
-        active_pdg[i]->moveset = pdg->moveset;
-        active_pdg[i]->pd      = pd;
-
-        return pd;
+        for (i = 0; active_pd[i] != NULL; i++);
+        return active_pd[i] = pd;
 }
 
 static void
@@ -169,7 +167,7 @@ instance_bfs(void *arg)
 {
         ThreadDataGenpt *td;
         uint64_t i, ii, blocksize, rmin, rmax, updated;
-        int j, pval, ichunk;
+        int j, pval, ichunk, oldc, newc;
         Move *ms;
 
         td = (ThreadDataGenpt *)arg;
@@ -180,25 +178,43 @@ 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);
                 pthread_mutex_unlock(td->mutex[ichunk]);
-                if (pval == td->d) {
+                if (pval == oldc) {
                         for (j = 0; ms[j] != NULLMOVE; j++) {
-                                /* ii = td->pd->coord->move(ms[j], i); */
                                 ii = move_coord(td->pd->coord, ms[j], i, NULL);
                                 ichunk = findchunk(td->pd, td->nchunks, ii);
                                 pthread_mutex_lock(td->mutex[ichunk]);
                                 pval = ptableval(td->pd, ii);
-                                if (pval > td->d+1) {
-                                        ptable_update(td->pd, ii, td->d+1);
+                                if (pval > newc) {
+                                        ptable_update(td->pd, ii, newc);
                                         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]);
+                        }
                 }
         }
 
@@ -214,7 +230,7 @@ instance_fixnasty(void *arg)
 {
         ThreadDataGenpt *td;
         uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M;
-        int j;
+        int j, oldc;
         Trans t;
 
         td = (ThreadDataGenpt *)arg;
@@ -227,17 +243,26 @@ instance_fixnasty(void *arg)
                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) == td->d) {
+                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)))
                                         continue;
                                 ii = trans_coord(td->pd->coord, t, i);
-                                if (ptableval(td->pd, ii) > td->d) {
-                                        ptable_update(td->pd, ii, td->d);
+                                if (ptableval(td->pd, ii) > oldc) {
+                                        ptable_update(td->pd, ii, oldc);
                                         updated++;
                                 }
                         }
@@ -257,6 +282,12 @@ 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);
+        }
+
         for (i = 0; i < 16; i++)
                 printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
 }
@@ -264,32 +295,50 @@ print_ptable(PruneData *pd)
 uint64_t
 ptablesize(PruneData *pd)
 {
-        return (pd->coord->max + ENTRIES_PER_GROUP - 1) / ENTRIES_PER_GROUP;
+        uint64_t e;
+
+        e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
+
+        return (pd->coord->max + e - 1) / e;
 }
 
 static void
 ptable_update(PruneData *pd, uint64_t ind, int n)
 {
         int sh;
-        entry_group_t mask;
-        uint64_t i;
+        entry_group_t f, mask;
+        uint64_t i, e, b;
+
+        e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
+        b = pd->compact ? 2 : 4;
+        f = pd->compact ? 3 : 15;
 
-        sh = 4 * (ind % ENTRIES_PER_GROUP);
-        mask = ((entry_group_t)15) << sh;
-        i = ind/ENTRIES_PER_GROUP;
+        sh = b * (ind % e);
+        mask = f << sh;
+        i = ind / e;
 
         pd->ptable[i] &= ~mask;
-        pd->ptable[i] |= (((entry_group_t)n)&15) << sh;
+        pd->ptable[i] |= (((entry_group_t)n) & f) << sh;
 }
 
 int
 ptableval(PruneData *pd, uint64_t ind)
 {
         int sh;
+        uint64_t e;
+        entry_group_t m;
 
-        sh = (ind % ENTRIES_PER_GROUP) * 4;
+        if (pd->compact) {
+                e  = ENTRIES_PER_GROUP_COMPACT;
+                m  = 3;
+                sh = (ind % e) * 2;
+        } else {
+                e  = ENTRIES_PER_GROUP;
+                m  = 15;
+                sh = (ind % e) * 4;
+        }
 
-        return (pd->ptable[ind/ENTRIES_PER_GROUP] & (15 << sh)) >> sh;
+        return (pd->ptable[ind/e] & (m << sh)) >> sh;
 }
 
 static bool
@@ -299,7 +348,7 @@ read_ptable_file(PruneData *pd)
 
         FILE *f;
         char fname[strlen(tabledir)+256];
-        int i, phony;
+        int i;
         uint64_t r;
 
         strcpy(fname, tabledir);
@@ -311,7 +360,7 @@ read_ptable_file(PruneData *pd)
         if ((f = fopen(fname, "rb")) == NULL)
                 return false;
 
-        r = fread(&phony, sizeof(int), 1, f);
+        r = fread(&(pd->base), sizeof(int), 1, f);
         for (i = 0; i < 16; i++)
                 r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f);
         r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
@@ -328,7 +377,7 @@ write_ptable_file(PruneData *pd)
 
         FILE *f;
         char fname[strlen(tabledir)+256];
-        int i, phony = 0;
+        int i;
         uint64_t w;
 
         strcpy(fname, tabledir);
@@ -340,7 +389,7 @@ write_ptable_file(PruneData *pd)
         if ((f = fopen(fname, "wb")) == NULL)
                 return false;
 
-        w = fwrite(&phony, sizeof(int), 1, f); /* phony replace base */
+        w = fwrite(&(pd->base), sizeof(int), 1, f);
         for (i = 0; i < 16; i++)
                 w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f);
         w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
diff --git a/src/pruning.h b/src/pruning.h
index 6965910..86691c1 100644
--- a/src/pruning.h
+++ b/src/pruning.h
@@ -4,12 +4,12 @@
 #include "coord.h"
 
 void        free_pd(PruneData *pd);
-PruneData * genptable(PDGenData *data, int nthreads);
+PruneData * genptable(PruneData *data, int nthreads);
 void        print_ptable(PruneData *pd);
 uint64_t    ptablesize(PruneData *pd);
 int         ptableval(PruneData *pd, uint64_t ind);
 
-extern PDGenData *active_pdg[256];
+extern PruneData *active_pd[256];
 
 #endif
 
diff --git a/src/steps.c b/src/steps.c
index a04d5e2..2f5fd2c 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -152,20 +152,16 @@ void
 prepare_cs(ChoiceStep *cs, SolveOptions *opts)
 {
         int i, j;
-        PDGenData pdg;
         Step *s;
 
         for (i = 0; cs->step[i] != NULL; i++) {
                 s = cs->step[i];
-                init_moveset(s->moveset);
-                pdg.moveset = s->moveset;
                 for (j = 0; j < s->n_coord; j++) {
-                        gen_coord(s->coord[j]);
-
-                        pdg.coord   = s->coord[j];
-                        pdg.pd      = NULL;
-
-                        s->pd[j] = genptable(&pdg, opts->nthreads);
+                        s->pd[j] = malloc(sizeof(PruneData));
+                        s->pd[j]->moveset = s->moveset;
+                        s->pd[j]->coord   = s->coord[j];
+                        s->pd[j]->compact = s->pd_compact[j];
+                        s->pd[j] = genptable(s->pd[j], opts->nthreads);
                 }
         }
 }
diff --git a/www/download/index.html b/www/download/index.html
index 01c4895..8e4cccd 100644
--- a/www/download/index.html
+++ b/www/download/index.html
@@ -34,8 +34,8 @@
 </tr>
 <tr>
         <td><strong>Latest version</strong></td>
-        <td><a href="/nissy-2.0.2.tar.gz">nissy-2.0.2.tar.gz (67Kb)</a></td>
-        <td><a href="/nissy-2.0.2.exe">nissy-2.0.2.exe (780Kb)</a></td>
+        <td><a href="/nissy-2.0.3.tar.gz">nissy-2.0.3.tar.gz (67Kb)</a></td>
+        <td><a href="/nissy-2.0.3.exe">nissy-2.0.3.exe (780Kb)</a></td>
 </tr>
 </table>
 
@@ -167,6 +167,11 @@ may be not used anymore. Nissy will deal with this automatically.
         <td><strong>Comment</strong></td>
 </tr>
 <tr>
+        <td><a href="/nissy-2.0.3.tar.gz">2.0.3</a></td>
+        <td>2022-09-10</td>
+        <td>Fixed bug in scramble dr</td>
+</tr>
+<tr>
         <td><a href="/nissy-2.0.2.tar.gz">2.0.2</a></td>
         <td>2022-06-01</td>
         <td>Improved table generation speed</td>
diff --git a/www/style-2.css b/www/style-3.css
index ec70635..ec70635 100644
--- a/www/style-2.css
+++ b/www/style-3.css