From 86dd040a2d2f06e8355f5441fb1da5ed59ecc399 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 10 Sep 2022 17:52:57 +0200 Subject: Modified pruning table generation (new compressed) + website update --- TODO.md | 4 -- src/cubetypes.h | 12 ++--- src/pruning.c | 139 ++++++++++++++++++++++++++++++++---------------- src/pruning.h | 4 +- src/steps.c | 14 ++--- www/download/index.html | 9 +++- www/style-2.css | 105 ------------------------------------ www/style-3.css | 105 ++++++++++++++++++++++++++++++++++++ 8 files changed, 216 insertions(+), 176 deletions(-) delete mode 100644 www/style-2.css create mode 100644 www/style-3.css 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; @@ -244,14 +243,6 @@ moveset uint64_t mask[NMOVES][NMOVES]; }; -struct -pdgendata -{ - Coordinate * coord; - Moveset * moveset; - PruneData * pd; -}; - struct prunedata { @@ -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<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; + + 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; + } - sh = (ind % ENTRIES_PER_GROUP) * 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 @@ Latest version - nissy-2.0.2.tar.gz (67Kb) - nissy-2.0.2.exe (780Kb) + nissy-2.0.3.tar.gz (67Kb) + nissy-2.0.3.exe (780Kb) @@ -166,6 +166,11 @@ may be not used anymore. Nissy will deal with this automatically. Date Comment + + 2.0.3 + 2022-09-10 + Fixed bug in scramble dr + 2.0.2 2022-06-01 diff --git a/www/style-2.css b/www/style-2.css deleted file mode 100644 index ec70635..0000000 --- a/www/style-2.css +++ /dev/null @@ -1,105 +0,0 @@ -.menu { - width: 100%; -} - -.links { - text-align: right; - font-weight: bold; -} - -.logo img { - width: 50px; - height: 50px; -} - -.footer { - font-style: italic; - width: 100%; -} - -.hosted { - text-align: right; -} - -body { - margin: auto 8px 20px 8px; -} - -img { - display: block; - margin-left: auto; - margin-right: auto; - max-width: 100%; -} - -code { - background-color: #eeeeee; - padding: 2px; -} - -pre code { - padding: 0px; -} - -pre { - background-color: #eeeeee; - border: 2px solid; - padding: 6px; -} - -#blob { - background: #ffffff; - border: none; -} - -a { - color: #0f2899; - text-decoration: none; -} - -.links a { - font-weight: bold; - color: black; -} - -.hosted a, -.contact a { - font-weight: bold; -} - -a:hover { - text-decoration: underline; -} - -html { - margin: 1em auto; - max-width: 42em; -} - -h1 { - text-align: center; -} - -td h1 { - text-align: left; - font-size: 1.5em; -} - -table { - width: 100%; -} - -.url td { - font-family: monospace; -} - -.dltable th, .dltable td { - border: 1px solid black; - padding: 3px; -} - -.subtitle { - text-align: center; - font-weight: bold; - font-size: 1.1em; -} diff --git a/www/style-3.css b/www/style-3.css new file mode 100644 index 0000000..ec70635 --- /dev/null +++ b/www/style-3.css @@ -0,0 +1,105 @@ +.menu { + width: 100%; +} + +.links { + text-align: right; + font-weight: bold; +} + +.logo img { + width: 50px; + height: 50px; +} + +.footer { + font-style: italic; + width: 100%; +} + +.hosted { + text-align: right; +} + +body { + margin: auto 8px 20px 8px; +} + +img { + display: block; + margin-left: auto; + margin-right: auto; + max-width: 100%; +} + +code { + background-color: #eeeeee; + padding: 2px; +} + +pre code { + padding: 0px; +} + +pre { + background-color: #eeeeee; + border: 2px solid; + padding: 6px; +} + +#blob { + background: #ffffff; + border: none; +} + +a { + color: #0f2899; + text-decoration: none; +} + +.links a { + font-weight: bold; + color: black; +} + +.hosted a, +.contact a { + font-weight: bold; +} + +a:hover { + text-decoration: underline; +} + +html { + margin: 1em auto; + max-width: 42em; +} + +h1 { + text-align: center; +} + +td h1 { + text-align: left; + font-size: 1.5em; +} + +table { + width: 100%; +} + +.url td { + font-family: monospace; +} + +.dltable th, .dltable td { + border: 1px solid black; + padding: 3px; +} + +.subtitle { + text-align: center; + font-weight: bold; + font-size: 1.1em; +} -- cgit v1.3