commit ec669b3179ea8150b15777d66c4365fc2ea7870f
parent 5d536a65d75f7ee452a2164858342937e2332c6d
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 17 Apr 2023 22:41:49 +0200
merged coord and pruning, separated steps
Diffstat:
| M | src/coord.c | | | 551 | ++++++++++++++++++++++++++++++++++++++----------------------------------------- |
| M | src/coord.h | | | 197 | +++++++------------------------------------------------------------------------ |
| D | src/pruning.c | | | 323 | ------------------------------------------------------------------------------- |
| D | src/pruning.h | | | 42 | ------------------------------------------ |
| M | src/solve.c | | | 104 | ++++++++----------------------------------------------------------------------- |
| A | src/steps.c | | | 485 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/steps.h | | | 36 | ++++++++++++++++++++++++++++++++++++ |
7 files changed, 811 insertions(+), 927 deletions(-)
diff --git a/src/coord.c b/src/coord.c
@@ -2,6 +2,9 @@
#include "coord.h"
+#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
+#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t))
+
static uint64_t indexers_getind(Indexer **is, Cube *c);
static uint64_t indexers_getmax(Indexer **is);
static void indexers_makecube(Indexer **is, uint64_t ind, Cube *c);
@@ -14,293 +17,15 @@ static bool write_coord_mtable(Coordinate *coord);
static bool write_coord_sd(Coordinate *coord);
static bool write_coord_ttable(Coordinate *coord);
-/* Utility functions *********************************************************/
-
-int
-factorial(int n)
-{
- int i, ret = 1;
-
- if (n < 0)
- return 0;
-
- for (i = 1; i <= n; i++)
- ret *= i;
-
- return ret;
-}
-
-int
-perm_to_index(int *a, int n)
-{
- int i, j, c, ret = 0;
-
- for (i = 0; i < n; i++) {
- c = 0;
- for (j = i+1; j < n; j++)
- c += (a[i] > a[j]) ? 1 : 0;
- ret += factorial(n-i-1) * c;
- }
-
- return ret;
-}
-
-void
-index_to_perm(int p, int n, int *r)
-{
- int *a = malloc(n * sizeof(int));
- int i, j, c;
-
- for (i = 0; i < n; i++)
- a[i] = 0;
-
- if (p < 0 || p >= factorial(n))
- for (i = 0; i < n; i++)
- r[i] = -1;
-
- for (i = 0; i < n; i++) {
- c = 0;
- j = 0;
- while (c <= p / factorial(n-i-1))
- c += a[j++] ? 0 : 1;
- r[i] = j-1;
- a[j-1] = 1;
- p %= factorial(n-i-1);
- }
-
- free(a);
-}
-
-int
-binomial(int n, int k)
-{
- if (n < 0 || k < 0 || k > n)
- return 0;
-
- return factorial(n) / (factorial(k) * factorial(n-k));
-}
-
-int
-subset_to_index(int *a, int n, int k)
-{
- int i, ret = 0;
-
- for (i = 0; i < n; i++) {
- if (k == n-i)
- return ret;
- if (a[i]) {
- ret += binomial(n-i-1, k);
- k--;
- }
- }
-
- return ret;
-}
-
-void
-index_to_subset(int s, int n, int k, int *r)
-{
- int i, j, v;
-
- for (i = 0; i < n; i++) {
- if (k == n-i) {
- for (j = i; j < n; j++)
- r[j] = 1;
- return;
- }
-
- if (k == 0) {
- for (j = i; j < n; j++)
- r[j] = 0;
- return;
- }
-
- v = binomial(n-i-1, k);
- if (s >= v) {
- r[i] = 1;
- k--;
- s -= v;
- } else {
- r[i] = 0;
- }
- }
-}
-
-int
-digit_array_to_int(int *a, int n, int b)
-{
- int i, ret = 0, p = 1;
-
- for (i = 0; i < n; i++, p *= b)
- ret += a[i] * p;
-
- return ret;
-}
-
-void
-int_to_digit_array(int a, int b, int n, int *r)
-{
- int i;
-
- for (i = 0; i < n; i++, a /= b)
- r[i] = a % b;
-}
-
-void
-int_to_sum_zero_array(int x, int b, int n, int *a)
-{
- int i, s = 0;
-
- int_to_digit_array(x, b, n-1, a);
- for (i = 0; i < n - 1; i++)
- s = (s + a[i]) % b;
- a[n-1] = (b - s) % b;
-}
-
-int
-perm_sign(int *a, int n)
-{
- int i, j, ret = 0;
-
- for (i = 0; i < n; i++)
- for (j = i+1; j < n; j++)
- ret += (a[i] > a[j]) ? 1 : 0;
-
- return ret % 2;
-}
-
-/* Indexers ******************************************************************/
-
-uint64_t
-index_eofb(Cube *cube)
-{
- return (uint64_t)digit_array_to_int(cube->eo, 11, 2);
-}
-
-uint64_t
-index_coud(Cube *cube)
-{
- return (uint64_t)digit_array_to_int(cube->co, 7, 3);
-}
-
-uint64_t
-index_cp(Cube *cube)
-{
- return (uint64_t)perm_to_index(cube->cp, 8);
-}
-
-uint64_t
-index_epe(Cube *cube)
-{
- int i, e[4];
-
- for (i = 0; i < 4; i++)
- e[i] = cube->ep[i+8] - 8;
-
- return (uint64_t)perm_to_index(e, 4);
-}
-
-uint64_t
-index_epud(Cube *cube)
-{
- return (uint64_t)perm_to_index(cube->ep, 8);
-}
-
-uint64_t
-index_epos(Cube *cube)
-{
- int i, a[12];
-
- for (i = 0; i < 12; i++)
- a[i] = (cube->ep[i] < 8) ? 0 : 1;
-
- return (uint64_t)subset_to_index(a, 12, 4);
-}
-
-uint64_t
-index_eposepe(Cube *cube)
-{
- int i, j, e[4];
- uint64_t epos, epe;
-
- epos = (uint64_t)index_epos(cube);
- for (i = 0, j = 0; i < 12; i++)
- if (cube->ep[i] >= 8)
- e[j++] = cube->ep[i] - 8;
- epe = (uint64_t)perm_to_index(e, 4);
-
- return epos * FACTORIAL4 + epe;
-}
-
-/* Inverse indexers **********************************************************/
-
-void
-invindex_eofb(uint64_t ind, Cube *cube)
-{
- int_to_sum_zero_array(ind, 2, 12, cube->eo);
-}
-
-void
-invindex_coud(uint64_t ind, Cube *cube)
-{
- int_to_sum_zero_array(ind, 3, 8, cube->co);
-}
-
-void
-invindex_cp(uint64_t ind, Cube *cube)
-{
- index_to_perm(ind, 8, cube->cp);
-}
-
-void
-invindex_epe(uint64_t ind, Cube *cube)
-{
- int i;
-
- index_to_perm(ind, 4, &cube->ep[8]);
- for (i = 0; i < 4; i++)
- cube->ep[i+8] += 8;
-}
-
-void
-invindex_epud(uint64_t ind, Cube *cube)
-{
- index_to_perm(ind, 8, cube->ep);
-}
-
-void
-invindex_epos(uint64_t ind, Cube *cube)
-{
- int i, j, k;
-
- index_to_subset(ind, 12, 4, cube->ep);
- for (i = 0, j = 0, k = 8; i < 12; i++)
- if (cube->ep[i] == 0)
- cube->ep[i] = j++;
- else
- cube->ep[i] = k++;
-}
-
-void
-invindex_eposepe(uint64_t ind, Cube *cube)
-{
- int i, j, k, e[4];
- uint64_t epos, epe;
-
- epos = ind / FACTORIAL4;
- epe = ind % FACTORIAL4;
-
- index_to_subset(epos, 12, 4, cube->ep);
- index_to_perm(epe, 4, e);
-
- for (i = 0, j = 0, k = 0; i < 12; i++)
- if (cube->ep[i] == 0)
- cube->ep[i] = j++;
- else
- cube->ep[i] = e[k++] + 8;
-}
-
-/* Other local functions *****************************************************/
+static void genptable(Coordinate *coord);
+static void genptable_bfs(Coordinate *coord, int d);
+static void fixnasty(Coordinate *coord, uint64_t i, int d);
+static void genptable_compress(Coordinate *coord);
+static void genptable_setbase(Coordinate *coord);
+static uint64_t ptablesize(Coordinate *coord);
+static void ptable_update(Coordinate *coord, uint64_t ind, int m);
+static bool read_ptable_file(Coordinate *coord);
+static bool write_ptable_file(Coordinate *coord);
static uint64_t
indexers_getmax(Indexer **is)
@@ -667,6 +392,8 @@ gen_coord(Coordinate *coord)
}
coord->generated = true;
+ genptable(coord);
+
return;
error_gc:
@@ -808,3 +535,253 @@ trans_coord(Coordinate *coord, Trans t, uint64_t ind)
return coord->max; /* Only reached in case of error */
}
+
+static void
+genptable(Coordinate *coord)
+{
+ bool compact;
+ int d, i;
+ uint64_t oldn, sz;
+
+ compact = coord->base[1] != NULL;
+ sz = ptablesize(coord) * (compact ? 2 : 1);
+ coord->ptable = malloc(sz * sizeof(entry_group_t));
+
+ if (read_ptable_file(coord))
+ return;
+
+ /* For the first steps we proceed the same way for compact and not */
+ coord->compact = false;
+
+ fprintf(stderr, "Generating pt_%s\n", coord->name);
+
+ /* TODO: replace with loop */
+ memset(coord->ptable, ~(uint8_t)0,
+ ptablesize(coord)*sizeof(entry_group_t));
+ for (i = 0; i < 16; i++)
+ coord->count[i] = 0;
+
+ coord->updated = 0;
+ oldn = 0;
+ ptable_update(coord, 0, 0);
+ fixnasty(coord, 0, 0);
+ fprintf(stderr, "Depth %d done, generated %"
+ PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
+ 0, coord->updated - oldn, coord->updated, coord->max);
+ oldn = coord->updated;
+ coord->count[0] = coord->updated;
+ for (d = 0; d < 15 && coord->updated < coord->max; d++) {
+ genptable_bfs(coord, d);
+ fprintf(stderr, "Depth %d done, generated %"
+ PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
+ d+1, coord->updated-oldn, coord->updated, coord->max);
+ coord->count[d+1] = coord->updated - oldn;
+ oldn = coord->updated;
+ }
+ fprintf(stderr, "Pruning table generated!\n");
+
+ genptable_setbase(coord);
+ if (compact)
+ genptable_compress(coord);
+
+ if (!write_ptable_file(coord))
+ fprintf(stderr, "Error writing ptable file\n");
+}
+
+static void
+genptable_bfs(Coordinate *coord, int d)
+{
+ uint64_t i, ii;
+ int pval;
+ Move m;
+
+ for (i = 0; i < coord->max; i++) {
+ pval = ptableval(coord, i);
+ if (pval != d)
+ continue;
+ for (m = U; m <= B3; m++) {
+ if (!coord->moveset(m))
+ continue;
+ ii = move_coord(coord, m, i, NULL);
+ ptable_update(coord, ii, d+1);
+ fixnasty(coord, ii, d+1);
+ }
+ }
+}
+
+static void
+fixnasty(Coordinate *coord, uint64_t i, int d)
+{
+ uint64_t ii, ss, M;
+ int j;
+ Trans t;
+
+ if (coord->type != SYMCOMP_COORD)
+ return;
+
+ M = coord->base[1]->max;
+ ss = coord->base[0]->selfsim[i/M];
+ for (j = 0; j < coord->base[0]->tgrp->n; j++) {
+ t = coord->base[0]->tgrp->t[j];
+ if (t == uf || !(ss & ((uint64_t)1<<t)))
+ continue;
+ ii = trans_coord(coord, t, i);
+ ptable_update(coord, ii, d);
+ }
+}
+
+static void
+genptable_compress(Coordinate *coord)
+{
+ 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 < coord->max; i += ENTRIES_PER_GROUP_COMPACT) {
+ mask = (entry_group_t)0;
+ for (j = 0; j < ENTRIES_PER_GROUP_COMPACT; j++) {
+ if (i+j >= coord->max)
+ break;
+ val = ptableval(coord, i+j) - coord->ptablebase;
+ v = (entry_group_t)MIN(3, MAX(0, val));
+ mask |= v << (2*j);
+ }
+ coord->ptable[i/ENTRIES_PER_GROUP_COMPACT] = mask;
+ }
+
+ coord->compact = true;
+ coord->ptable = realloc(coord->ptable,
+ sizeof(entry_group_t)*ptablesize(coord));
+}
+
+static void
+genptable_setbase(Coordinate *coord)
+{
+ int i;
+ uint64_t sum, newsum;
+
+ coord->ptablebase = 0;
+ sum = coord->count[0] + coord->count[1] + coord->count[2];
+ for (i = 3; i < 16; i++) {
+ newsum = sum + coord->count[i] - coord->count[i-3];
+ if (newsum > sum)
+ coord->ptablebase = i-3;
+ sum = newsum;
+ }
+}
+
+void
+print_ptable(Coordinate *coord)
+{
+ uint64_t i;
+
+ printf("Table %s\n", coord->name);
+ printf("Base value: %d\n", coord->ptablebase);
+ for (i = 0; i < 16; i++)
+ printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, coord->count[i]);
+}
+
+static uint64_t
+ptablesize(Coordinate *coord)
+{
+ uint64_t e;
+
+ e = coord->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
+
+ return (coord->max + e - 1) / e;
+}
+
+static void
+ptable_update(Coordinate *coord, uint64_t ind, int n)
+{
+ int sh;
+ entry_group_t mask;
+ uint64_t i;
+
+ if (ptableval(coord, ind) <= n)
+ return;
+
+ sh = 4 * (ind % ENTRIES_PER_GROUP);
+ mask = ((entry_group_t)15) << sh;
+ i = ind/ENTRIES_PER_GROUP;
+ coord->ptable[i] &= ~mask;
+ coord->ptable[i] |= (((entry_group_t)n)&15) << sh;
+
+ coord->updated++;
+}
+
+int
+ptableval(Coordinate *coord, uint64_t ind)
+{
+ int ret, j, sh;
+ uint64_t e, ii;
+
+ if (coord->compact) {
+ e = ENTRIES_PER_GROUP_COMPACT;
+ sh = (ind % e) * 2;
+ ret = (coord->ptable[ind/e] & (3 << sh)) >> sh;
+ if (ret != coord->ptablebase)
+ return ret;
+ for (j = 0; coord->base[j] != NULL; j++) ;
+ for ( ; j >= 0; j--) {
+ ii = ind % coord->base[j]->max;
+ ret = MAX(ret, ptableval(coord->base[j], ii));
+ ind /= coord->base[j]->max;
+ }
+ return ret;
+ }
+
+ e = ENTRIES_PER_GROUP;
+ sh = (ind % e) * 4;
+ return (coord->ptable[ind/e] & (15 << sh)) >> sh;
+}
+
+static bool
+read_ptable_file(Coordinate *coord)
+{
+ FILE *f;
+ char fname[256];
+ int i;
+ uint64_t r;
+
+ strcpy(fname, "tables/pt_");
+ strcat(fname, coord->name);
+
+ if ((f = fopen(fname, "rb")) == NULL)
+ return false;
+
+ r = fread(&(coord->ptablebase), sizeof(int), 1, f);
+ for (i = 0; i < 16; i++)
+ r += fread(&(coord->count[i]), sizeof(uint64_t), 1, f);
+ r += fread(coord->ptable, sizeof(entry_group_t), ptablesize(coord), f);
+
+ fclose(f);
+
+ return r == 17 + ptablesize(coord);
+}
+
+static bool
+write_ptable_file(Coordinate *coord)
+{
+ FILE *f;
+ char fname[256];
+ int i;
+ uint64_t w;
+
+ strcpy(fname, "tables/pt_");
+ strcat(fname, coord->name);
+
+ if ((f = fopen(fname, "wb")) == NULL)
+ return false;
+
+ w = fwrite(&(coord->ptablebase), sizeof(int), 1, f);
+ for (i = 0; i < 16; i++)
+ w += fwrite(&(coord->count[i]), sizeof(uint64_t), 1, f);
+ w += fwrite(coord->ptable, sizeof(entry_group_t), ptablesize(coord), f);
+ fclose(f);
+
+ return w == 17 + ptablesize(coord);
+}
+
diff --git a/src/coord.h b/src/coord.h
@@ -8,6 +8,9 @@
#include "cube.h"
+#define entry_group_t uint8_t
+
+typedef bool (Moveset)(Move);
typedef enum { COMP_COORD, SYM_COORD, SYMCOMP_COORD } CoordType;
typedef struct {
int n;
@@ -17,8 +20,6 @@ typedef struct {
typedef struct coordinate {
char * name;
CoordType type;
- bool generated;
- Indexer * i[99];
uint64_t max;
uint64_t * mtable[NMOVES];
uint64_t * ttable[NTRANS];
@@ -28,7 +29,17 @@ typedef struct coordinate {
uint64_t * symrep;
Trans * transtorep;
Trans * ttrep_move[NMOVES];
- uint64_t * selfsim;
+
+ bool generated;
+ Indexer * i[99];
+ uint64_t * selfsim; /* used only in fixnasty */
+
+ Moveset * moveset; /* for pruning, mt and compressing */
+ uint64_t updated;
+ entry_group_t * ptable;
+ int ptablebase; /* Renamed */
+ bool compact; /* Only needed for generation, maybe keep */
+ uint64_t count[16]; /* Only needed for generation and print */
} Coordinate;
void gen_coord(Coordinate *coord);
@@ -39,183 +50,7 @@ uint64_t move_coord(Coordinate *coord, Move m,
bool test_coord(Coordinate *coord);
uint64_t trans_coord(Coordinate *coord, Trans t, uint64_t ind);
-/* Base coordinates and their index functions ********************************/
-
-#ifndef COORD_C
-
-extern Coordinate coord_eofb;
-extern Coordinate coord_coud;
-extern Coordinate coord_cp;
-extern Coordinate coord_epos;
-extern Coordinate coord_epe;
-extern Coordinate coord_eposepe;
-extern Coordinate coord_epud;
-extern Coordinate coord_eofbepos;
-extern Coordinate coord_eofbepos_sym16;
-extern Coordinate coord_drud_sym16;
-extern Coordinate coord_cp_sym16;
-extern Coordinate coord_drudfin_noE_sym16;
-
-#else
-
-/* Indexers ******************************************************************/
-
-uint64_t index_eofb(Cube *cube);
-void invindex_eofb(uint64_t ind, Cube *ret);
-Indexer
-i_eofb = {
- .n = POW2TO11,
- .index = index_eofb,
- .to_cube = invindex_eofb,
-};
-
-uint64_t index_coud(Cube *cube);
-void invindex_coud(uint64_t ind, Cube *ret);
-Indexer
-i_coud = {
- .n = POW3TO7,
- .index = index_coud,
- .to_cube = invindex_coud,
-};
-
-uint64_t index_cp(Cube *cube);
-void invindex_cp(uint64_t ind, Cube *ret);
-Indexer
-i_cp = {
- .n = FACTORIAL8,
- .index = index_cp,
- .to_cube = invindex_cp,
-};
-
-uint64_t index_epos(Cube *cube);
-void invindex_epos(uint64_t ind, Cube *ret);
-Indexer
-i_epos = {
- .n = BINOM12ON4,
- .index = index_epos,
- .to_cube = invindex_epos,
-};
-
-uint64_t index_epe(Cube *cube);
-void invindex_epe(uint64_t ind, Cube *ret);
-Indexer
-i_epe = {
- .n = FACTORIAL4,
- .index = index_epe,
- .to_cube = invindex_epe,
-};
-
-uint64_t index_eposepe(Cube *cube);
-void invindex_eposepe(uint64_t ind, Cube *ret);
-Indexer
-i_eposepe = {
- .n = BINOM12ON4 * FACTORIAL4,
- .index = index_eposepe,
- .to_cube = invindex_eposepe,
-};
-
-uint64_t index_epud(Cube *cube);
-void invindex_epud(uint64_t ind, Cube *ret);
-Indexer
-i_epud = {
- .n = FACTORIAL8,
- .index = index_epud,
- .to_cube = invindex_epud,
-};
-
-/* Composite coordinates *****************************************************/
-
-Coordinate
-coord_eofb = {
- .name = "eofb",
- .type = COMP_COORD,
- .i = {&i_eofb, NULL},
-};
-
-Coordinate
-coord_coud = {
- .name = "coud",
- .type = COMP_COORD,
- .i = {&i_coud, NULL},
-};
-
-Coordinate
-coord_cp = {
- .name = "cp",
- .type = COMP_COORD,
- .i = {&i_cp, NULL},
-};
-
-Coordinate
-coord_epos = {
- .name = "epos",
- .type = COMP_COORD,
- .i = {&i_epos, NULL},
-};
-
-Coordinate
-coord_epe = {
- .name = "epe",
- .type = COMP_COORD,
- .i = {&i_epe, NULL},
-};
-
-Coordinate
-coord_eposepe = {
- .name = "eposepe",
- .type = COMP_COORD,
- .i = {&i_eposepe, NULL},
-};
-
-Coordinate
-coord_epud = {
- .name = "epud",
- .type = COMP_COORD,
- .i = {&i_epud, NULL},
-};
-
-Coordinate
-coord_eofbepos = {
- .name = "eofbepos",
- .type = COMP_COORD,
- .i = {&i_epos, &i_eofb, NULL},
-};
-
-/* Symcoordinates ************************************************************/
-
-Coordinate
-coord_eofbepos_sym16 = {
- .name = "eofbepos_sym16",
- .type = SYM_COORD,
- .base = {&coord_eofbepos, NULL},
- .tgrp = &tgrp_udfix,
-};
-
-Coordinate
-coord_cp_sym16 = {
- .name = "cp_sym16",
- .type = SYM_COORD,
- .base = {&coord_cp, NULL},
- .tgrp = &tgrp_udfix,
-};
-
-/* "Symcomp" coordinates *****************************************************/
-
-Coordinate
-coord_drud_sym16 = {
- .name = "drud_sym16",
- .type = SYMCOMP_COORD,
- .base = {&coord_eofbepos_sym16, &coord_coud},
-};
-
-Coordinate
-coord_drudfin_noE_sym16 = {
- .name = "drudfin_noE_sym16",
- .type = SYMCOMP_COORD,
- .base = {&coord_cp_sym16, &coord_epud},
-};
-
-#endif
+void print_ptable(Coordinate *coord);
+int ptableval(Coordinate *coord, uint64_t ind);
#endif
-
diff --git a/src/pruning.c b/src/pruning.c
@@ -1,323 +0,0 @@
-#define PRUNING_C
-
-#include "pruning.h"
-
-#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
-#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t))
-
-static void genptable_bfs(PruneData *pd, int d);
-static void fixnasty(PruneData *pd, uint64_t i, int d);
-static void genptable_compress(PruneData *pd);
-static void genptable_setbase(PruneData *pd);
-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];
-
-bool
-allowed_HTM(Move m)
-{
- return m >= U && m <= B3;
-}
-
-bool
-allowed_URF(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == R || b == F;
-}
-
-bool
-allowed_eofb(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == D || b == R || b == L ||
- ((b == F || b == B) && m == b+1);
-}
-
-bool
-allowed_drud(Move m)
-{
- Move b = base_move(m);
-
- return b == U || b == D ||
- ((b == R || b == L || b == F || b == B) && m == b + 1);
-}
-
-bool
-allowed_htr(Move m)
-{
- return allowed_HTM(m) && m == base_move(m) + 1;
-}
-
-PruneData *
-genptable(PDGenData *pdg)
-{
- bool compact;
- int d, i;
- uint64_t oldn, sz;
- PruneData *pd;
-
- for (i = 0; active_pdg[i] != NULL; i++) {
- pd = active_pdg[i]->pd;
- if (pd->coord == pdg->coord &&
- pd->moveset == pdg->moveset &&
- pd->compact == pdg->compact)
- return pd;
- }
-
- pd = malloc(sizeof(PruneData));
- pdg->pd = pd;
- pd->coord = pdg->coord;
- pd->moveset = pdg->moveset;
- pd->compact = pdg->compact;
-
- sz = ptablesize(pd) * (pd->compact ? 2 : 1);
- pd->ptable = malloc(sz * sizeof(entry_group_t));
-
- gen_coord(pd->coord);
-
- if (read_ptable_file(pd))
- goto genptable_done;
-
- /* For the first steps we proceed the same way for compact and not */
- compact = pd->compact;
- pd->compact = false;
-
- fprintf(stderr, "Generating pt_%s\n", pd->coord->name);
-
- 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);
- pd->n = 1;
- oldn = 0;
- fixnasty(pd, 0, 0);
- fprintf(stderr, "Depth %d done, generated %"
- PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
- 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++) {
- genptable_bfs(pd, d);
- fprintf(stderr, "Depth %d done, generated %"
- PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
- d+1, pd->n - oldn, pd->n, pd->coord->max);
- pd->count[d+1] = pd->n - oldn;
- oldn = pd->n;
- }
- 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_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]->compact = pdg->compact;
- active_pdg[i]->pd = pd;
-
- return pd;
-}
-
-static void
-genptable_bfs(PruneData *pd, int d)
-{
- uint64_t i, ii;
- int pval;
- Move m;
-
- for (i = 0; i < pd->coord->max; i++) {
- pval = ptableval(pd, i);
- if (pval != d)
- continue;
- for (m = U; m <= B3; m++) {
- if (!pd->moveset(m))
- continue;
- ii = move_coord(pd->coord, m, i, NULL);
- ptable_update(pd, ii, d+1);
- fixnasty(pd, ii, d+1);
- }
- }
-}
-
-static void
-fixnasty(PruneData *pd, uint64_t i, int d)
-{
- uint64_t ii, ss, M;
- int j;
- Trans t;
-
- if (pd->coord->type != SYMCOMP_COORD)
- return;
-
- M = pd->coord->base[1]->max;
- ss = pd->coord->base[0]->selfsim[i/M];
- for (j = 0; j < pd->coord->base[0]->tgrp->n; j++) {
- t = pd->coord->base[0]->tgrp->t[j];
- if (t == uf || !(ss & ((uint64_t)1<<t)))
- continue;
- ii = trans_coord(pd->coord, t, i);
- ptable_update(pd, ii, d);
- }
-}
-
-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(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_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;
- }
-}
-
-void
-print_ptable(PruneData *pd)
-{
- uint64_t i;
-
- printf("Table %s\n", pd->coord->name);
- printf("Base value: %d\n", pd->base);
- for (i = 0; i < 16; i++)
- printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
-}
-
-uint64_t
-ptablesize(PruneData *pd)
-{
- 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;
-
- if (ptableval(pd, ind) <= n)
- return;
-
- 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)&15) << sh;
- pd->n++;
-}
-
-int
-ptableval(PruneData *pd, uint64_t ind)
-{
- int sh, ret;
- 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;
- }
-
- ret = (pd->ptable[ind/e] & (m << sh)) >> sh;
-
- return pd->compact ? ret + pd->base : ret;
-}
-
-static bool
-read_ptable_file(PruneData *pd)
-{
- FILE *f;
- char fname[256];
- int i;
- uint64_t r;
-
- strcpy(fname, "tables/pt_");
- strcat(fname, pd->coord->name);
-
- if ((f = fopen(fname, "rb")) == NULL)
- return false;
-
- 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);
-
- fclose(f);
-
- return r == 17 + ptablesize(pd);
-}
-
-static bool
-write_ptable_file(PruneData *pd)
-{
- FILE *f;
- char fname[256];
- int i;
- uint64_t w;
-
- strcpy(fname, "tables/pt_");
- strcat(fname, pd->coord->name);
-
- if ((f = fopen(fname, "wb")) == NULL)
- return false;
-
- 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);
- fclose(f);
-
- return w == 17 + ptablesize(pd);
-}
-
diff --git a/src/pruning.h b/src/pruning.h
@@ -1,42 +0,0 @@
-#ifndef PRUNING_H
-#define PRUNING_H
-
-#include "coord.h"
-
-#define entry_group_t uint8_t
-
-typedef bool (Moveset)(Move);
-typedef struct {
- entry_group_t * ptable;
- uint64_t n;
- Coordinate * coord;
- Moveset * moveset;
- bool compact;
- int base;
- uint64_t count[16];
- uint64_t fbmod;
-} PruneData;
-typedef struct {
- Coordinate * coord;
- Moveset * moveset;
- bool compact;
- PruneData * pd;
-} PDGenData;
-
-bool allowed_all(Move m);
-bool allowed_HTM(Move m);
-bool allowed_URF(Move m);
-bool allowed_eofb(Move m);
-bool allowed_drud(Move m);
-bool allowed_htr(Move m);
-
-void free_pd(PruneData *pd);
-PruneData * genptable(PDGenData *data);
-void print_ptable(PruneData *pd);
-uint64_t ptablesize(PruneData *pd);
-int ptableval(PruneData *pd, uint64_t ind);
-
-extern PDGenData *active_pdg[256];
-
-#endif
-
diff --git a/src/solve.c b/src/solve.c
@@ -1,25 +1,12 @@
#define SOLVE_C
+#include "coord.h"
+#include "steps.h"
#include "solve.h"
-#include "pruning.h"
-
-#define MAX_N_COORD 3
typedef enum { NORMAL, INVERSE, NISS } SolutionType;
typedef struct { uint64_t val; Trans t; } Movable;
typedef struct {
- char * shortname;
- bool filter;
- Moveset * moveset;
- Coordinate * coord[MAX_N_COORD];
- PruneData * pd[MAX_N_COORD];
- bool compact_pd[MAX_N_COORD];
- Coordinate * fallback_coord[MAX_N_COORD];
- PruneData * fallback_pd[MAX_N_COORD];
- uint64_t fbmod[MAX_N_COORD];
-
-} Step;
-typedef struct {
Cube * cube;
Movable ind[MAX_N_COORD];
Step * s;
@@ -44,33 +31,6 @@ static void dfs(DfsArg *arg);
static void dfs_niss(DfsArg *arg);
static bool dfs_move_checkstop(DfsArg *arg);
static bool niss_makes_sense(DfsArg *arg);
-static bool singlecwend(Alg *alg);
-
-Step eofb_HTM = {
- .shortname = "eofb",
- .filter = true,
- .moveset = allowed_HTM,
- .coord = {&coord_eofb, NULL},
- .compact_pd = {false},
-};
-
-Step drud_HTM = {
- .shortname = "drud",
- .filter = true,
- .moveset = allowed_HTM,
- .coord = {&coord_drud_sym16, NULL},
- .compact_pd = {false}, /* TODO: compactify! */
-};
-
-Step drfin_drud = {
- .shortname = "drudfin",
- .filter = false,
- .moveset = allowed_drud,
- .coord = {&coord_drudfin_noE_sym16, &coord_epe, NULL},
- .compact_pd = {false}, /* TODO: compactify! */
-};
-
-Step *steps[] = { &eofb_HTM, &drud_HTM, &drfin_drud, NULL };
static void
append_sol(DfsArg *arg)
@@ -144,17 +104,11 @@ copy_dfsarg(DfsArg *src, DfsArg *dst)
static int
estimate_step(Step *step, Movable *ind)
{
- int i, v, ret = -1;
-
- for (i = 0; step->coord[i] != NULL; i++) {
- v = ptableval(step->pd[i], ind[i].val);
- if (v == step->pd[i]->base && step->compact_pd[i])
- v = ptableval(step->fallback_pd[i],
- ind[i].val / step->fbmod[i]);
- if (v == 0 && ind[i].val != 0)
- v = 1;
- ret = MAX(ret, v);
- }
+ int i, ret;
+
+ ret = -1;
+ for (i = 0; step->coord[i] != NULL; i++)
+ ret = MAX(ret, ptableval(step->coord[i], ind[i].val));
return ret;
}
@@ -164,16 +118,15 @@ dfs(DfsArg *arg)
{
Move m;
DfsArg newarg;
- bool len, singlecw, niss;
+ bool len, niss;
if (dfs_move_checkstop(arg))
return;
if (arg->bound == 0) {
len = arg->current_alg->len == arg->d;
- singlecw = singlecwend(arg->current_alg);
niss = !(arg->st == NISS) || arg->has_nissed;
- if (len && singlecw && niss)
+ if (len && niss)
append_sol(arg);
return;
}
@@ -276,29 +229,6 @@ niss_makes_sense(DfsArg *arg)
return estimate_step(aux.s, aux.ind) > 0;
}
-bool
-singlecwend(Alg *alg)
-{
- int i;
- bool nor, inv;
- Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
-
- for (i = 0; i < alg->len; i++) {
- if (alg->inv[i]) {
- l2i = l1i;
- l1i = alg->move[i];
- } else {
- l2 = l1;
- l1 = alg->move[i];
- }
- }
-
- nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2));
- inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i));
-
- return nor && inv;
-}
-
/* Public functions **********************************************************/
static bool
@@ -378,22 +308,8 @@ solve(char *step, char *trans, int d, char *type, char *scramble, char *sol)
if (!set_step(step, &arg.s)) return 1;
/* Prepare step TODO: remove all initialization! */
- PDGenData pdg;
- pdg.moveset = arg.s->moveset;
- for (i = 0; arg.s->coord[i] != NULL; i++) {
+ for (i = 0; arg.s->coord[i] != NULL; i++)
gen_coord(arg.s->coord[i]);
- pdg.coord = arg.s->coord[i];
- pdg.compact = arg.s->compact_pd[i];
- pdg.pd = NULL;
- arg.s->pd[i] = genptable(&pdg);
- if (arg.s->compact_pd[i]) {
- gen_coord(arg.s->fallback_coord[i]);
- pdg.coord = arg.s->fallback_coord[i];
- pdg.compact = false;
- pdg.pd = NULL;
- arg.s->fallback_pd[i] = genptable(&pdg);
- }
- }
if (!set_trans(trans, &arg.t)) return 2;
diff --git a/src/steps.c b/src/steps.c
@@ -0,0 +1,485 @@
+#include "steps.h"
+
+static bool moveset_HTM(Move m);
+static bool moveset_eofb(Move m);
+static bool moveset_drud(Move m);
+static bool moveset_htr(Move m);
+
+static uint64_t index_eofb(Cube *cube);
+static void invindex_eofb(uint64_t ind, Cube *ret);
+Indexer i_eofb = {
+ .n = POW2TO11,
+ .index = index_eofb,
+ .to_cube = invindex_eofb,
+};
+
+static uint64_t index_coud(Cube *cube);
+static void invindex_coud(uint64_t ind, Cube *ret);
+Indexer i_coud = {
+ .n = POW3TO7,
+ .index = index_coud,
+ .to_cube = invindex_coud,
+};
+
+static uint64_t index_cp(Cube *cube);
+static void invindex_cp(uint64_t ind, Cube *ret);
+Indexer i_cp = {
+ .n = FACTORIAL8,
+ .index = index_cp,
+ .to_cube = invindex_cp,
+};
+
+static uint64_t index_epos(Cube *cube);
+static void invindex_epos(uint64_t ind, Cube *ret);
+Indexer i_epos = {
+ .n = BINOM12ON4,
+ .index = index_epos,
+ .to_cube = invindex_epos,
+};
+
+static uint64_t index_epe(Cube *cube);
+static void invindex_epe(uint64_t ind, Cube *ret);
+Indexer i_epe = {
+ .n = FACTORIAL4,
+ .index = index_epe,
+ .to_cube = invindex_epe,
+};
+
+static uint64_t index_eposepe(Cube *cube);
+static void invindex_eposepe(uint64_t ind, Cube *ret);
+Indexer i_eposepe = {
+ .n = BINOM12ON4 * FACTORIAL4,
+ .index = index_eposepe,
+ .to_cube = invindex_eposepe,
+};
+
+static uint64_t index_epud(Cube *cube);
+static void invindex_epud(uint64_t ind, Cube *ret);
+Indexer i_epud = {
+ .n = FACTORIAL8,
+ .index = index_epud,
+ .to_cube = invindex_epud,
+};
+
+Coordinate coord_eofb = {
+ .name = "eofb",
+ .type = COMP_COORD,
+ .i = {&i_eofb, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_coud = {
+ .name = "coud",
+ .type = COMP_COORD,
+ .i = {&i_coud, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_cp = {
+ .name = "cp",
+ .type = COMP_COORD,
+ .i = {&i_cp, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_epos = {
+ .name = "epos",
+ .type = COMP_COORD,
+ .i = {&i_epos, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_epe = {
+ .name = "epe",
+ .type = COMP_COORD,
+ .i = {&i_epe, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_eposepe = {
+ .name = "eposepe",
+ .type = COMP_COORD,
+ .i = {&i_eposepe, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_epud = {
+ .name = "epud",
+ .type = COMP_COORD,
+ .i = {&i_epud, NULL},
+ .moveset = moveset_drud,
+};
+
+Coordinate coord_eofbepos = {
+ .name = "eofbepos",
+ .type = COMP_COORD,
+ .i = {&i_epos, &i_eofb, NULL},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_eofbepos_sym16 = {
+ .name = "eofbepos_sym16",
+ .type = SYM_COORD,
+ .base = {&coord_eofbepos, NULL},
+ .tgrp = &tgrp_udfix,
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_cp_sym16 = {
+ .name = "cp_sym16",
+ .type = SYM_COORD,
+ .base = {&coord_cp, NULL},
+ .tgrp = &tgrp_udfix,
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_drud_sym16 = {
+ .name = "drud_sym16",
+ .type = SYMCOMP_COORD,
+ .base = {&coord_eofbepos_sym16, &coord_coud},
+ .moveset = moveset_HTM,
+};
+
+Coordinate coord_drudfin_noE_sym16 = {
+ .name = "drudfin_noE_sym16",
+ .type = SYMCOMP_COORD,
+ .base = {&coord_cp_sym16, &coord_epud},
+ .moveset = moveset_drud,
+};
+
+Coordinate *coordinates[] = {
+ &coord_eofb, &coord_coud, &coord_cp, &coord_epos, &coord_epe,
+ &coord_eposepe, &coord_epud, &coord_eofbepos, &coord_eofbepos_sym16,
+ &coord_drud_sym16, &coord_cp_sym16, &coord_drudfin_noE_sym16,
+ NULL
+};
+
+Step eofb_HTM = {
+ .shortname = "eofb",
+ .moveset = moveset_HTM,
+ .coord = {&coord_eofb, NULL},
+};
+
+Step drud_HTM = {
+ .shortname = "drud",
+ .moveset = moveset_HTM,
+ .coord = {&coord_drud_sym16, NULL},
+};
+
+Step drfin_drud = {
+ .shortname = "drudfin",
+ .moveset = moveset_drud,
+ .coord = {&coord_drudfin_noE_sym16, &coord_epe, NULL},
+};
+
+Step *steps[] = {&eofb_HTM, &drud_HTM, &drfin_drud, NULL};
+
+static bool
+moveset_HTM(Move m)
+{
+ return m >= U && m <= B3;
+}
+
+static bool
+moveset_eofb(Move m)
+{
+ Move b = base_move(m);
+
+ return b == U || b == D || b == R || b == L ||
+ ((b == F || b == B) && m == b+1);
+}
+
+static bool
+moveset_drud(Move m)
+{
+ Move b = base_move(m);
+
+ return b == U || b == D ||
+ ((b == R || b == L || b == F || b == B) && m == b + 1);
+}
+
+static bool
+moveset_htr(Move m)
+{
+ return moveset_HTM(m) && m == base_move(m) + 1;
+}
+
+static int
+factorial(int n)
+{
+ int i, ret = 1;
+
+ if (n < 0)
+ return 0;
+
+ for (i = 1; i <= n; i++)
+ ret *= i;
+
+ return ret;
+}
+
+static int
+perm_to_index(int *a, int n)
+{
+ int i, j, c, ret = 0;
+
+ for (i = 0; i < n; i++) {
+ c = 0;
+ for (j = i+1; j < n; j++)
+ c += (a[i] > a[j]) ? 1 : 0;
+ ret += factorial(n-i-1) * c;
+ }
+
+ return ret;
+}
+
+static void
+index_to_perm(int p, int n, int *r)
+{
+ int *a = malloc(n * sizeof(int));
+ int i, j, c;
+
+ for (i = 0; i < n; i++)
+ a[i] = 0;
+
+ if (p < 0 || p >= factorial(n))
+ for (i = 0; i < n; i++)
+ r[i] = -1;
+
+ for (i = 0; i < n; i++) {
+ c = 0;
+ j = 0;
+ while (c <= p / factorial(n-i-1))
+ c += a[j++] ? 0 : 1;
+ r[i] = j-1;
+ a[j-1] = 1;
+ p %= factorial(n-i-1);
+ }
+
+ free(a);
+}
+
+static int
+binomial(int n, int k)
+{
+ if (n < 0 || k < 0 || k > n)
+ return 0;
+
+ return factorial(n) / (factorial(k) * factorial(n-k));
+}
+
+static int
+subset_to_index(int *a, int n, int k)
+{
+ int i, ret = 0;
+
+ for (i = 0; i < n; i++) {
+ if (k == n-i)
+ return ret;
+ if (a[i]) {
+ ret += binomial(n-i-1, k);
+ k--;
+ }
+ }
+
+ return ret;
+}
+
+static void
+index_to_subset(int s, int n, int k, int *r)
+{
+ int i, j, v;
+
+ for (i = 0; i < n; i++) {
+ if (k == n-i) {
+ for (j = i; j < n; j++)
+ r[j] = 1;
+ return;
+ }
+
+ if (k == 0) {
+ for (j = i; j < n; j++)
+ r[j] = 0;
+ return;
+ }
+
+ v = binomial(n-i-1, k);
+ if (s >= v) {
+ r[i] = 1;
+ k--;
+ s -= v;
+ } else {
+ r[i] = 0;
+ }
+ }
+}
+
+static int
+digit_array_to_int(int *a, int n, int b)
+{
+ int i, ret = 0, p = 1;
+
+ for (i = 0; i < n; i++, p *= b)
+ ret += a[i] * p;
+
+ return ret;
+}
+
+static void
+int_to_digit_array(int a, int b, int n, int *r)
+{
+ int i;
+
+ for (i = 0; i < n; i++, a /= b)
+ r[i] = a % b;
+}
+
+static void
+int_to_sum_zero_array(int x, int b, int n, int *a)
+{
+ int i, s = 0;
+
+ int_to_digit_array(x, b, n-1, a);
+ for (i = 0; i < n - 1; i++)
+ s = (s + a[i]) % b;
+ a[n-1] = (b - s) % b;
+}
+
+static int
+perm_sign(int *a, int n)
+{
+ int i, j, ret = 0;
+
+ for (i = 0; i < n; i++)
+ for (j = i+1; j < n; j++)
+ ret += (a[i] > a[j]) ? 1 : 0;
+
+ return ret % 2;
+}
+
+static uint64_t
+index_eofb(Cube *cube)
+{
+ return (uint64_t)digit_array_to_int(cube->eo, 11, 2);
+}
+
+static uint64_t
+index_coud(Cube *cube)
+{
+ return (uint64_t)digit_array_to_int(cube->co, 7, 3);
+}
+
+static uint64_t
+index_cp(Cube *cube)
+{
+ return (uint64_t)perm_to_index(cube->cp, 8);
+}
+
+static uint64_t
+index_epe(Cube *cube)
+{
+ int i, e[4];
+
+ for (i = 0; i < 4; i++)
+ e[i] = cube->ep[i+8] - 8;
+
+ return (uint64_t)perm_to_index(e, 4);
+}
+
+static uint64_t
+index_epud(Cube *cube)
+{
+ return (uint64_t)perm_to_index(cube->ep, 8);
+}
+
+static uint64_t
+index_epos(Cube *cube)
+{
+ int i, a[12];
+
+ for (i = 0; i < 12; i++)
+ a[i] = (cube->ep[i] < 8) ? 0 : 1;
+
+ return (uint64_t)subset_to_index(a, 12, 4);
+}
+
+static uint64_t
+index_eposepe(Cube *cube)
+{
+ int i, j, e[4];
+ uint64_t epos, epe;
+
+ epos = (uint64_t)index_epos(cube);
+ for (i = 0, j = 0; i < 12; i++)
+ if (cube->ep[i] >= 8)
+ e[j++] = cube->ep[i] - 8;
+ epe = (uint64_t)perm_to_index(e, 4);
+
+ return epos * FACTORIAL4 + epe;
+}
+
+static void
+invindex_eofb(uint64_t ind, Cube *cube)
+{
+ int_to_sum_zero_array(ind, 2, 12, cube->eo);
+}
+
+static void
+invindex_coud(uint64_t ind, Cube *cube)
+{
+ int_to_sum_zero_array(ind, 3, 8, cube->co);
+}
+
+static void
+invindex_cp(uint64_t ind, Cube *cube)
+{
+ index_to_perm(ind, 8, cube->cp);
+}
+
+static void
+invindex_epe(uint64_t ind, Cube *cube)
+{
+ int i;
+
+ index_to_perm(ind, 4, &cube->ep[8]);
+ for (i = 0; i < 4; i++)
+ cube->ep[i+8] += 8;
+}
+
+static void
+invindex_epud(uint64_t ind, Cube *cube)
+{
+ index_to_perm(ind, 8, cube->ep);
+}
+
+static void
+invindex_epos(uint64_t ind, Cube *cube)
+{
+ int i, j, k;
+
+ index_to_subset(ind, 12, 4, cube->ep);
+ for (i = 0, j = 0, k = 8; i < 12; i++)
+ if (cube->ep[i] == 0)
+ cube->ep[i] = j++;
+ else
+ cube->ep[i] = k++;
+}
+
+static void
+invindex_eposepe(uint64_t ind, Cube *cube)
+{
+ int i, j, k, e[4];
+ uint64_t epos, epe;
+
+ epos = ind / FACTORIAL4;
+ epe = ind % FACTORIAL4;
+
+ index_to_subset(epos, 12, 4, cube->ep);
+ index_to_perm(epe, 4, e);
+
+ for (i = 0, j = 0, k = 0; i < 12; i++)
+ if (cube->ep[i] == 0)
+ cube->ep[i] = j++;
+ else
+ cube->ep[i] = e[k++] + 8;
+}
diff --git a/src/steps.h b/src/steps.h
@@ -0,0 +1,36 @@
+#ifndef STEPS_H
+#define STEPS_H
+
+#include "coord.h"
+#include "cube.h"
+
+#define MAX_N_COORD 3
+
+typedef struct {
+ char * shortname;
+ Moveset * moveset;
+ Coordinate * coord[MAX_N_COORD];
+} Step;
+
+extern Coordinate coord_eofb;
+extern Coordinate coord_coud;
+extern Coordinate coord_cp;
+extern Coordinate coord_epos;
+extern Coordinate coord_epe;
+extern Coordinate coord_eposepe;
+extern Coordinate coord_epud;
+extern Coordinate coord_eofbepos;
+extern Coordinate coord_eofbepos_sym16;
+extern Coordinate coord_drud_sym16;
+extern Coordinate coord_cp_sym16;
+extern Coordinate coord_drudfin_noE_sym16;
+
+extern Coordinate *coordinates[];
+
+extern Step eofb_HTM;
+extern Step drud_HTM;
+extern Step drfin_drud;
+
+extern Step *steps[];
+
+#endif
