From bf44088d4373a9520e860152c56a958332819c4b Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 1 May 2023 16:33:51 +0200 Subject: Split nissy in other repos, see README.md --- src/alg.c | 459 ----------------------------------- src/alg.h | 35 --- src/commands.c | 569 ------------------------------------------- src/commands.h | 211 ---------------- src/coord.c | 654 -------------------------------------------------- src/coord.h | 259 -------------------- src/cube.c | 270 --------------------- src/cube.h | 35 --- src/cubetypes.h | 360 --------------------------- src/env.c | 60 ----- src/env.h | 15 -- src/fst.c | 401 ------------------------------- src/fst.h | 13 - src/moves.c | 301 ----------------------- src/moves.h | 17 -- src/movesets.c | 194 --------------- src/movesets.h | 15 -- src/pruning.c | 400 ------------------------------ src/pruning.h | 16 -- src/shell.c | 177 -------------- src/shell.h | 14 -- src/solve.c | 122 ---------- src/solve.h | 54 ----- src/solver_step.c | 306 ----------------------- src/solver_step.h | 12 - src/steps.c | 177 -------------- src/steps.h | 244 ------------------- src/threader_eager.c | 163 ------------- src/threader_eager.h | 8 - src/threader_single.c | 35 --- src/threader_single.h | 8 - src/trans.c | 190 --------------- src/trans.h | 32 --- src/utils.c | 290 ---------------------- src/utils.h | 43 ---- 35 files changed, 6159 deletions(-) delete mode 100644 src/alg.c delete mode 100644 src/alg.h delete mode 100644 src/commands.c delete mode 100644 src/commands.h delete mode 100644 src/coord.c delete mode 100644 src/coord.h delete mode 100644 src/cube.c delete mode 100644 src/cube.h delete mode 100644 src/cubetypes.h delete mode 100644 src/env.c delete mode 100644 src/env.h delete mode 100644 src/fst.c delete mode 100644 src/fst.h delete mode 100644 src/moves.c delete mode 100644 src/moves.h delete mode 100644 src/movesets.c delete mode 100644 src/movesets.h delete mode 100644 src/pruning.c delete mode 100644 src/pruning.h delete mode 100644 src/shell.c delete mode 100644 src/shell.h delete mode 100644 src/solve.c delete mode 100644 src/solve.h delete mode 100644 src/solver_step.c delete mode 100644 src/solver_step.h delete mode 100644 src/steps.c delete mode 100644 src/steps.h delete mode 100644 src/threader_eager.c delete mode 100644 src/threader_eager.h delete mode 100644 src/threader_single.c delete mode 100644 src/threader_single.h delete mode 100644 src/trans.c delete mode 100644 src/trans.h delete mode 100644 src/utils.c delete mode 100644 src/utils.h (limited to 'src') diff --git a/src/alg.c b/src/alg.c deleted file mode 100644 index d806178..0000000 --- a/src/alg.c +++ /dev/null @@ -1,459 +0,0 @@ -#define ALG_C - -#include "alg.h" - -static int axis(Move m); -static void free_alglistnode(AlgListNode *aln); -static void realloc_alg(Alg *alg, int n); - -void -append_alg(AlgList *l, Alg *alg) -{ - AlgListNode *node = malloc(sizeof(AlgListNode)); - int i; - - node->alg = new_alg(""); - for (i = 0; i < alg->len; i++) - append_move(node->alg, alg->move[i], alg->inv[i]); - node->next = NULL; - - if (++l->len == 1) - l->first = node; - else - l->last->next = node; - l->last = node; -} - -void -append_move(Alg *alg, Move m, bool inverse) -{ - if (alg->len == alg->allocated) - realloc_alg(alg, 2*alg->len); - - alg->move[alg->len] = m; - alg->inv [alg->len] = inverse; - alg->len++; - - if (inverse) - alg->move_inverse[alg->len_inverse++] = m; - else - alg->move_normal[alg->len_normal++] = m; -} - -static int -axis(Move m) -{ - static int aux[] = { - [NULLMOVE] = 0, - - [U] = 1, [U2] = 1, [U3] = 1, - [D] = 1, [D2] = 1, [D3] = 1, - [Uw] = 1, [Uw2] = 1, [Uw3] = 1, - [Dw] = 1, [Dw2] = 1, [Dw3] = 1, - [E] = 1, [E2] = 1, [E3] = 1, - [y] = 1, [y2] = 1, [y3] = 1, - - [R] = 2, [R2] = 2, [R3] = 2, - [L] = 2, [L2] = 2, [L3] = 2, - [Rw] = 2, [Rw2] = 2, [Rw3] = 2, - [Lw] = 2, [Lw2] = 2, [Lw3] = 2, - [M] = 2, [M2] = 2, [M3] = 2, - [x] = 2, [x2] = 2, [x3] = 2, - - [F] = 3, [F2] = 3, [F3] = 3, - [B] = 3, [B2] = 3, [B3] = 3, - [Fw] = 3, [Fw2] = 3, [Fw3] = 3, - [Bw] = 3, [Bw2] = 3, [Bw3] = 3, - [S] = 3, [S2] = 3, [S3] = 3, - [z] = 3, [z2] = 3, [z3] = 3, - }; - - return aux[m]; -} - -Move -base_move(Move m) -{ - if (m == NULLMOVE) - return NULLMOVE; - else - return m - (m-1)%3; -} - -bool -commute(Move m1, Move m2) -{ - return axis(m1) == axis(m2); -} - -int -compare(Move m1, Move m2) -{ - if (!commute(m1, m2)) - return 0; - - return m1 < m2 ? 1 : -1; -} - -int -compare_last(Alg *alg, Move m, bool inverse) -{ - Move last; - int n; - - if (inverse) { - n = alg->len_inverse; - last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; - } else { - n = alg->len_normal; - last = n > 0 ? alg->move_normal[n-1] : NULLMOVE; - } - - return compare(last, m); -} - -void -compose_alg(Alg *alg1, Alg *alg2) -{ - int i; - - for (i = 0; i < alg2->len; i++) - append_move(alg1, alg2->move[i], alg2->inv[i]); -} - -void -copy_alg(Alg *src, Alg *dst) -{ - dst->len = dst->len_normal = dst->len_inverse = 0; - compose_alg(dst, src); -} - -void -free_alg(Alg *alg) -{ - free(alg->move); - free(alg->inv); - free(alg); -} - -void -free_alglist(AlgList *l) -{ - AlgListNode *aux, *i = l->first; - - while (i != NULL) { - aux = i->next; - free_alglistnode(i); - i = aux; - } - free(l); -} - -static void -free_alglistnode(AlgListNode *aln) -{ - free_alg(aln->alg); - free(aln); -} - -Alg * -inverse_alg(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = alg->len-1; i >= 0; i--) - append_move(ret, inverse_move(alg->move[i]), alg->inv[i]); - - return ret; -} - -Move -inverse_move(Move m) -{ - return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3); -} - -char * -move_string(Move m) -{ - static char move_string_aux[NMOVES][7] = { - [NULLMOVE] = "-", - [U] = "U", [U2] = "U2", [U3] = "U\'", - [D] = "D", [D2] = "D2", [D3] = "D\'", - [R] = "R", [R2] = "R2", [R3] = "R\'", - [L] = "L", [L2] = "L2", [L3] = "L\'", - [F] = "F", [F2] = "F2", [F3] = "F\'", - [B] = "B", [B2] = "B2", [B3] = "B\'", - [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'", - [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'", - [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'", - [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'", - [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'", - [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'", - [M] = "M", [M2] = "M2", [M3] = "M\'", - [E] = "E", [E2] = "E2", [E3] = "E\'", - [S] = "S", [S2] = "S2", [S3] = "S\'", - [x] = "x", [x2] = "x2", [x3] = "x\'", - [y] = "y", [y2] = "y2", [y3] = "y\'", - [z] = "z", [z2] = "z2", [z3] = "z\'", - }; - - return move_string_aux[m]; -} - -Alg * -new_alg(char *str) -{ - Alg *alg; - int i; - bool niss, move_read; - Move j, m; - - alg = malloc(sizeof(Alg)); - alg->allocated = 30; - alg->move = malloc(alg->allocated * sizeof(Move)); - alg->inv = malloc(alg->allocated * sizeof(bool)); - alg->move_normal = malloc(alg->allocated * sizeof(Move)); - alg->move_inverse = malloc(alg->allocated * sizeof(Move)); - alg->len = 0; - alg->len_normal = 0; - alg->len_inverse = 0; - - niss = false; - for (i = 0; str[i]; i++) { - if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n') - continue; - - if (str[i] == '(' && niss) { - fprintf(stderr, "Error reading moves: nested ( )\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - return alg; - } - - if (str[i] == ')' && !niss) { - fprintf(stderr, "Error reading moves: unmatched )\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - return alg; - } - - if (str[i] == '(' || str[i] == ')') { - niss = !niss; - continue; - } - - /* Single slash for comments */ - if (str[i] == '/') { - while (str[i] && str[i] != '\n') - i++; - - if (!str[i]) - i--; - - continue; - } - - move_read = false; - for (j = U; j < NMOVES; j++) { - if (str[i] == move_string(j)[0] || - (str[i] >= 'a' && str[i] <= 'z' && - str[i] == move_string(j)[0]-('A'-'a') && j<=B)) { - m = j; - if (str[i] >= 'a' && str[i] <= 'z' && j<=B) { - m += Uw - U; - } - if (m <= B && str[i+1]=='w') { - m += Uw - U; - i++; - } - if (str[i+1]=='2') { - m += 1; - i++; - } else if (str[i+1] == '\'' || - str[i+1] == '3' || - str[i+1] == '`' ) { - m += 2; - i++; - } else if ((int)str[i+1] == -62 && - (int)str[i+2] == -76) { - /* Weird apostrophe */ - m += 2; - i += 2; - } else if ((int)str[i+1] == -30 && - (int)str[i+2] == -128 && - (int)str[i+3] == -103) { - /* MacOS apostrophe */ - m += 2; - i += 3; - } - append_move(alg, m, niss); - move_read = true; - break; - } - } - - if (!move_read) { - free(alg); - return new_alg(""); - } - } - - if (niss) { - fprintf(stderr, "Error reading moves: unmatched (\n"); - alg->len = alg->len_normal = alg->len_inverse = 0; - } - - return alg; -} - -AlgList * -new_alglist() -{ - AlgList *ret = malloc(sizeof(AlgList)); - - ret->len = 0; - ret->first = NULL; - ret->last = NULL; - - return ret; -} - -Alg * -on_inverse(Alg *alg) -{ - Alg *ret = new_alg(""); - int i; - - for (i = 0; i < alg->len; i++) - append_move(ret, alg->move[i], !alg->inv[i]); - - return ret; -} - -void -print_alg(Alg *alg, bool l) -{ - char fill[4]; - int i; - bool niss = false; - - for (i = 0; i < alg->len; i++) { - if (!niss && alg->inv[i]) - strcpy(fill, i == 0 ? "(" : " ("); - if (niss && !alg->inv[i]) - strcpy(fill, ") "); - if (niss == alg->inv[i]) - strcpy(fill, i == 0 ? "" : " "); - - printf("%s%s", fill, move_string(alg->move[i])); - niss = alg->inv[i]; - } - - if (niss) - printf(")"); - if (l) - printf(" (%d)", alg->len); - - printf("\n"); -} - -void -print_alglist(AlgList *al, bool l) -{ - AlgListNode *i; - - for (i = al->first; i != NULL; i = i->next) - print_alg(i->alg, l); -} - -static void -realloc_alg(Alg *alg, int n) -{ - if (alg == NULL) { - fprintf(stderr, "Error: trying to reallocate NULL alg.\n"); - return; - } - - if (n < alg->len) { - fprintf(stderr, "Error: alg too long for reallocation "); - fprintf(stderr, "(%d vs %d)\n", alg->len, n); - return; - } - - if (n > 1000000) { - fprintf(stderr, "Warning: very long alg,"); - fprintf(stderr, "something might go wrong.\n"); - } - - alg->move = realloc(alg->move, n * sizeof(int)); - alg->inv = realloc(alg->inv, n * sizeof(int)); - alg->move_normal = realloc(alg->move_normal, n * sizeof(int)); - alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int)); - alg->allocated = n; -} - -void -remove_last_move(Alg *a) -{ - a->len--; - - if (a->inv[a->len]) - a->len_inverse--; - else - a->len_normal--; -} - -void -swapmove(Move *m1, Move *m2) -{ - Move aux; - - aux = *m1; - *m1 = *m2; - *m2 = aux; -} - -char * -trans_string(Trans t) -{ - static char trans_string_aux[NTRANS][20] = { - [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul", - [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl", - [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru", - [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu", - [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl", - [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl", - - [uf_mirror] = "uf*", [ur_mirror] = "ur*", - [ub_mirror] = "ub*", [ul_mirror] = "ul*", - [df_mirror] = "df*", [dr_mirror] = "dr*", - [db_mirror] = "db*", [dl_mirror] = "dl*", - [rf_mirror] = "rf*", [rd_mirror] = "rd*", - [rb_mirror] = "rb*", [ru_mirror] = "ru*", - [lf_mirror] = "lf*", [ld_mirror] = "ld*", - [lb_mirror] = "lb*", [lu_mirror] = "lu*", - [fu_mirror] = "fu*", [fr_mirror] = "fr*", - [fd_mirror] = "fd*", [fl_mirror] = "fl*", - [bu_mirror] = "bu*", [br_mirror] = "br*", - [bd_mirror] = "bd*", [bl_mirror] = "bl*", - }; - - return trans_string_aux[t]; -} - -Alg * -unniss(Alg *alg) -{ - int i; - Alg *ret; - - ret = new_alg(""); - - for (i = 0; i < alg->len_normal; i++) - append_move(ret, alg->move_normal[i], false); - - for (i = 0; i < alg->len_inverse; i++) - append_move(ret, inverse_move(alg->move_inverse[i]), false); - - return ret; -} diff --git a/src/alg.h b/src/alg.h deleted file mode 100644 index 967cd92..0000000 --- a/src/alg.h +++ /dev/null @@ -1,35 +0,0 @@ -#ifndef ALG_H -#define ALG_H - -#include -#include -#include - -#include "cubetypes.h" -#include "utils.h" - -void append_alg(AlgList *l, Alg *alg); -void append_move(Alg *alg, Move m, bool inverse); -Move base_move(Move m); -int compare(Move m1, Move m2); /* Return 1 (m1m2) */ -int compare_last(Alg *alg, Move m, bool inverse); -void compose_alg(Alg *alg1, Alg *alg2); -bool commute(Move m1, Move m2); -void copy_alg(Alg *src, Alg *dst); -void free_alg(Alg *alg); -void free_alglist(AlgList *l); -Alg * inverse_alg(Alg *alg); -Move inverse_move(Move m); -char * move_string(Move m); -Alg * new_alg(char *str); -AlgList * new_alglist(); -Alg * on_inverse(Alg *alg); -void print_alg(Alg *alg, bool l); -void print_alglist(AlgList *al, bool l); -void remove_last_move(Alg *alg); -void swapmove(Move *m1, Move *m2); -char * trans_string(Trans t); /* Here because similar to move_string, move? */ -Alg * unniss(Alg *alg); - -#endif - diff --git a/src/commands.c b/src/commands.c deleted file mode 100644 index a9e8fc9..0000000 --- a/src/commands.c +++ /dev/null @@ -1,569 +0,0 @@ -#define COMMANDS_C - -#include "commands.h" - -static bool read_cs(CommandArgs *args, char *str); -static bool read_scrtype(CommandArgs *args, char *str); -static bool read_scramble(int c, char **v, CommandArgs *args); - -/* Arg parsing functions implementation **************************************/ - -CommandArgs * -solve_parse_args(int c, char **v) -{ - int i; - bool infinitesols, fixedmsols; - long val; - - CommandArgs *a = new_args(); - - a->opts->min_moves = 0; - a->opts->max_moves = 20; - a->opts->max_solutions = 1; - a->opts->nthreads = 1; - a->opts->optimal = -1; - a->opts->can_niss = false; - a->opts->verbose = false; - a->opts->all = false; - a->opts->print_number = true; - a->opts->count_only = false; - - fixedmsols = false; - infinitesols = false; - - for (i = 0; i < c; i++) { - if (!strcmp(v[i], "-m") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid min number of moves" - "(0 <= N <= 100).\n"); - return a; - } - a->opts->min_moves = val; - } else if (!strcmp(v[i], "-M") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100) { - fprintf(stderr, - "Invalid max number of moves" - "(0 <= N <= 100).\n"); - return a; - } - a->opts->max_moves = val; - infinitesols = true; - } else if (!strcmp(v[i], "-t") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 64) { - fprintf(stderr, - "Invalid number of threads." - "1 <= t <= 64\n"); - return a; - } - a->opts->nthreads = val; - } else if (!strcmp(v[i], "-n") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 1000000) { - fprintf(stderr, - "Invalid number of solutions.\n"); - return a; - } - a->opts->max_solutions = val; - fixedmsols = true; - } else if (!strcmp(v[i], "-o")) { - a->opts->optimal = 0; - infinitesols = true; - } else if (!strcmp(v[i], "-O") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 0 || val > 100 || - (val == 0 && strcmp("0", v[i]))) { - fprintf(stderr, - "Invalid max number of moves" - " (0 <= N <= 100).\n"); - return a; - } - a->opts->optimal = val; - infinitesols = true; - } else if (!strcmp(v[i], "-N")) { - a->opts->can_niss = true; - } else if (!strcmp(v[i], "-i")) { - a->scrstdin = true; - } else if (!strcmp(v[i], "-v")) { - a->opts->verbose = true; - } else if (!strcmp(v[i], "-a")) { - a->opts->all = true; - } else if (!strcmp(v[i], "-p")) { - a->opts->print_number = false; - } else if (!strcmp(v[i], "-c")) { - a->opts->count_only = true; - } else if (!read_cs(a, v[i])) { - break; - } - } - - if (infinitesols && !fixedmsols) - a->opts->max_solutions = 1000000; /* 1M = +infty */ - - a->success = (a->scrstdin && i == c) || read_scramble(c-i, &v[i], a); - return a; -} - -CommandArgs * -scramble_parse_args(int c, char **v) -{ - int i; - long val; - - CommandArgs *a = new_args(); - - a->success = true; - a->n = 1; - - for (i = 0; i < c; i++) { - if (!strcmp(v[i], "-n") && i+1 < c) { - val = strtol(v[++i], NULL, 10); - if (val < 1 || val > 1000000) { - fprintf(stderr, - "Invalid number of scrambles.\n"); - a->success = false; - return a; - } - a->n = val; - } else if (!read_scrtype(a, v[i])) { - a->success = false; - return a; - } - } - - return a; -} - -CommandArgs * -gen_parse_args(int c, char **v) -{ - int val; - CommandArgs *a = new_args(); - - a->opts->nthreads = 64; - a->success = false; - - if (c == 0) { - a->success = true; - } else { - if (!strcmp(v[0], "-t") && c > 1) { - val = strtol(v[1], NULL, 10); - if (val < 1 || val > 64) { - fprintf(stderr, - "Invalid number of threads." - "1 <= t <= 64\n"); - return a; - } - a->opts->nthreads = val; - a->success = true; - } - } - - return a; -} - -CommandArgs * -help_parse_args(int c, char **v) -{ - int i; - CommandArgs *a = new_args(); - - if (c == 1) { - for (i = 0; commands[i] != NULL; i++) - if (!strcmp(v[0], commands[i]->name)) - a->command = commands[i]; - if (a->command == NULL) - fprintf(stderr, "%s: command not found\n", v[0]); - } - - a->success = c == 0 || (c == 1 && a->command != NULL); - return a; -} - -CommandArgs * -parse_only_scramble(int c, char **v) -{ - CommandArgs *a = new_args(); - - if (!strcmp(v[0], "-i")) { - a->scrstdin = true; - a->success = c == 1; - } else { - a->success = read_scramble(c, v, a); - } - - return a; -} - -CommandArgs * -parse_no_arg(int c, char **v) -{ - CommandArgs *a = new_args(); - - a->success = true; - - return a; -} - -/* Exec functions implementation *********************************************/ - -void -solve_exec(CommandArgs *args) -{ - Cube c; - AlgList *sols; - Solver *solver[99]; - Threader *threader; - - make_solved(&c); - apply_alg(args->scramble, &c); -/* TODO: adjust */ -/* threader = &threader_single;*/ - threader = &threader_eager; - -/* TODO: adjust */ - int i; - for (i = 0; args->cs->step[i] != NULL; i++) - solver[i] = new_stepsolver_lazy(args->cs->step[i]); - solver[i] = NULL; - sols = solve(&c, args->opts, solver, threader); - - if (args->opts->count_only) - printf("%d\n", sols->len); - else - print_alglist(sols, args->opts->print_number); - - free_alglist(sols); -} - -void -scramble_exec(CommandArgs *args) -{ - Cube cube; - Alg *scr, *ruf, *aux; - int i, j, eo, ep, co, cp; - uint64_t ui, uj, uk; - - srand(time(NULL)); - - for (i = 0; i < args->n; i++) { - - if (!strcmp(args->scrtype, "dr")) { - ui = rand() % FACTORIAL8; - uj = rand() % FACTORIAL8; - uk = rand() % FACTORIAL4; - - make_solved(&cube); - index_to_perm(ui, 8, cube.cp); - index_to_perm(uj, 8, cube.ep); - index_to_perm(uk, 4, cube.ep + 8); - for (j = 8; j < 12; j++) - cube.ep[j] += 8; - } else if (!strcmp(args->scrtype, "htr")) { - make_solved(&cube); - /* TODO */ - } else { - ep = rand() % FACTORIAL12; - cp = rand() % FACTORIAL8; - eo = rand() % POW2TO11; - co = rand() % POW3TO7; - - if (!strcmp(args->scrtype, "eo")) { - eo = 0; - } else if (!strcmp(args->scrtype, "corners")) { - eo = 0; - ep = 0; - } else if (!strcmp(args->scrtype, "edges")) { - co = 0; - cp = 0; - } - - make_solved(&cube); - index_to_perm(ep, 12, cube.ep); - index_to_perm(cp, 8, cube.cp); - int_to_sum_zero_array(eo, 2, 12, cube.eo); - int_to_sum_zero_array(co, 3, 8, cube.co); - } - - if (!is_admissible(&cube)) { - if (!strcmp(args->scrtype, "corners")) - swap(&cube.cp[UFR], &cube.cp[UFL]); - else - swap(&cube.ep[UF], &cube.ep[UB]); - } - - /* TODO: can be optimized for htr and dr using htrfin, drfin */ - /* - TODO: solve_2phase was removed - scr = solve_2phase(&cube, 1); - */ - - if (!strcmp(args->scrtype, "fmc")) { - aux = new_alg(""); - copy_alg(scr, aux); - /* Trick to rufify for free: rotate the scramble * - * so that it does not start with F or end with R */ - for (j = 0; j < NROTATIONS; j++) { - if (base_move(scr->move[0]) != F && - base_move(scr->move[0]) != B && - base_move(scr->move[scr->len-1]) != R && - base_move(scr->move[scr->len-1]) != L) - break; - copy_alg(aux, scr); - transform_alg(j, scr); - } - copy_alg(scr, aux); - ruf = new_alg("R' U' F"); - copy_alg(ruf, scr); - compose_alg(scr, aux); - compose_alg(scr, ruf); - free_alg(aux); - free_alg(ruf); - } - print_alg(scr, false); - free_alg(scr); - } -} - -void -gen_exec(CommandArgs *args) -{ -/* TODO: - int i; - - fprintf(stderr, "Generating coordinates...\n"); - fprintf(stderr, "Generating pruning tables...\n"); - for (i = 0; all_pd[i] != NULL; i++) - genptable(all_pd[i], args->opts->nthreads); -*/ - - fprintf(stderr, "Done!\n"); -} - -void -invert_exec(CommandArgs *args) -{ - Alg *inv; - - inv = inverse_alg(args->scramble); - print_alg(inv, false); - - free_alg(inv); -} - -void -steps_exec(CommandArgs *args) -{ - int i; - - for (i = 0; csteps[i] != NULL; i++) - printf("%-15s %s\n", csteps[i]->shortname, csteps[i]->name); -} - -void -commands_exec(CommandArgs *args) -{ - int i; - - for (i = 0; commands[i] != NULL; i++) - printf("%s\n", commands[i]->usage); - -} - -void -freemem_exec(CommandArgs *args) -{ -/* TODO: - int i; - - for (i = 0; all_pd[i] != NULL; i++) - free_pd(all_pd[i]); - - for (i = 0; all_sd[i] != NULL; i++) - free_sd(all_sd[i]); -*/ -} - -void -print_exec(CommandArgs *args) -{ - Cube c; - - make_solved(&c); - apply_alg(args->scramble, &c); - print_cube(&c); -} - -/* -void -twophase_exec(CommandArgs *args) -{ - Cube c; - Alg *sol; - - make_solved(&c); - apply_alg(args->scramble, &c); - sol = solve_2phase(&c, 1); - - print_alg(sol, false); - free_alg(sol); -} -*/ - -void -help_exec(CommandArgs *args) -{ - if (args->command == NULL) { - printf( - "Use the nissy command \"help COMMAND\" for a short " - "description of a specific command.\n" - "Use the nissy command \"commands\" for a list of " - "available commands.\n" - "See the manual page for more details. The manual" - " page is available with \"man nissy\" on a UNIX" - " system (such as Linux or MacOS) or in pdf and html" - " format in the docs folder.\n" - "Nissy is available for free at " - "https://nissy.tronto.net\n" - ); - } else { - printf("Command %s: %s\nusage: %s\n", args->command->name, - args->command->description, args->command->usage); - } -} - -void -quit_exec(CommandArgs *args) -{ - exit(0); -} - -void -cleanup_exec(CommandArgs *args) -{ - Alg *alg; - - alg = cleanup(args->scramble); - print_alg(alg, false); - - free_alg(alg); -} - -void -unniss_exec(CommandArgs *args) -{ - Alg *aux; - - aux = unniss(args->scramble); - print_alg(aux, false); - free(aux); -} - -void -version_exec(CommandArgs *args) -{ - printf(VERSION"\n"); -} - -/* Local functions implementation ********************************************/ - -static bool -read_scramble(int c, char **v, CommandArgs *args) -{ - int i, k, n; - unsigned int j; - char *algstr; - - if (c < 1) { - fprintf(stderr, "Error: no scramble given?\n"); - return false; - } - - for(n = 0, i = 0; i < c; i++) - n += strlen(v[i]); - - algstr = malloc((n + 1) * sizeof(char)); - k = 0; - for (i = 0; i < c; i++) - for (j = 0; j < strlen(v[i]); j++) - algstr[k++] = v[i][j]; - algstr[k] = 0; - - args->scramble = new_alg(algstr); - free(algstr); - - if (args->scramble->len == 0) - fprintf(stderr, "Error reading scramble\n"); - - return args->scramble->len > 0; -} - -static bool -read_scrtype(CommandArgs *args, char *str) -{ - int i; - static char *scrtypes[20] = - { "eo", "corners", "edges", "fmc", "dr", "htr", NULL }; - - for (i = 0; scrtypes[i] != NULL; i++) { - if (!strcmp(scrtypes[i], str)) { - strcpy(args->scrtype, scrtypes[i]); - return true; - } - } - - return false; -} - -static bool -read_cs(CommandArgs *args, char *str) -{ - int i; - - for (i = 0; csteps[i] != NULL; i++) { - if (!strcmp(csteps[i]->shortname, str)) { - args->cs = csteps[i]; - return true; - } - } - - return false; -} - -/* Public functions implementation *******************************************/ - -void -free_args(CommandArgs *args) -{ - if (args == NULL) - return; - - if (args->scramble != NULL) - free_alg(args->scramble); - if (args->opts != NULL) - free(args->opts); - - /* step and command must not be freed, they are static! */ - - free(args); -} - -CommandArgs * -new_args() -{ - CommandArgs *args = malloc(sizeof(CommandArgs)); - - args->success = false; - args->scrstdin = false; - args->scramble = NULL; /* initialized in read_scramble */ - args->opts = malloc(sizeof(SolveOptions)); - - /* step and command are static */ - args->cs = csteps[0]; /* default: first step in list */ - args->command = NULL; - - return args; -} diff --git a/src/commands.h b/src/commands.h deleted file mode 100644 index 65708e0..0000000 --- a/src/commands.h +++ /dev/null @@ -1,211 +0,0 @@ -#ifndef COMMANDS_H -#define COMMANDS_H - -#include - -#include "solve.h" -#include "steps.h" -#include "solver_step.h" -#include "threader_single.h" -#include "threader_eager.h" - -void free_args(CommandArgs *args); -CommandArgs * new_args(); - -/* Arg parsing functions *****************************************************/ - -CommandArgs * gen_parse_args(int c, char **v); -CommandArgs * help_parse_args(int c, char **v); -CommandArgs * parse_only_scramble(int c, char **v); -CommandArgs * parse_no_arg(int c, char **v); -CommandArgs * solve_parse_args(int c, char **v); -CommandArgs * scramble_parse_args(int c, char **v); - -/* Exec functions ************************************************************/ - -void gen_exec(CommandArgs *args); -void cleanup_exec(CommandArgs *args); -void invert_exec(CommandArgs *args); -void solve_exec(CommandArgs *args); -void scramble_exec(CommandArgs *args); -void steps_exec(CommandArgs *args); -void commands_exec(CommandArgs *args); -void freemem_exec(CommandArgs *args); -void print_exec(CommandArgs *args); -/*void twophase_exec(CommandArgs *args);*/ -void help_exec(CommandArgs *args); -void quit_exec(CommandArgs *args); -void unniss_exec(CommandArgs *args); -void version_exec(CommandArgs *args); - -/* Commands ******************************************************************/ - -#ifndef COMMANDS_C - -extern Command cleanup_cmd; -extern Command commands_cmd; -extern Command freemem_cmd; -extern Command gen_cmd; -extern Command help_cmd; -extern Command invert_cmd; -extern Command print_cmd; -extern Command quit_cmd; -extern Command scramble_cmd; -extern Command solve_cmd; -extern Command steps_cmd; -extern Command unniss_cmd; -extern Command version_cmd; - -extern Command *commands[]; - -#else - -Command -solve_cmd = { - .name = "solve", - .usage = "solve STEP [OPTIONS] SCRAMBLE", - .description = "Solve a step; see command steps for a list of steps", - .parse_args = solve_parse_args, - .exec = solve_exec -}; - -Command -scramble_cmd = { - .name = "scramble", - .usage = "scramble [TYPE] [-n N]", - .description = "Get a random-position scramble", - .parse_args = scramble_parse_args, - .exec = scramble_exec, -}; - -Command -gen_cmd = { - .name = "gen", - .usage = "gen [-t N]", - .description = "Generate all tables [using N threads]", - .parse_args = gen_parse_args, - .exec = gen_exec -}; - -Command -invert_cmd = { - .name = "invert", - .usage = "invert SCRAMBLE]", - .description = "Invert a scramble", - .parse_args = parse_only_scramble, - .exec = invert_exec, -}; - -Command -steps_cmd = { - .name = "steps", - .usage = "steps", - .description = "List available steps", - .parse_args = parse_no_arg, - .exec = steps_exec -}; - -Command -commands_cmd = { - .name = "commands", - .usage = "commands", - .description = "List available commands", - .parse_args = parse_no_arg, - .exec = commands_exec -}; - -Command -freemem_cmd = { - .name = "freemem", - .usage = "freemem", - .description = "free large tables from RAM", - .parse_args = parse_no_arg, - .exec = freemem_exec, -}; - -Command -print_cmd = { - .name = "print", - .usage = "print SCRAMBLE", - .description = "Print written description of the cube", - .parse_args = parse_only_scramble, - .exec = print_exec, -}; - -Command -help_cmd = { - .name = "help", - .usage = "help [COMMAND]", - .description = "Display nissy manual page or help on specific command", - .parse_args = help_parse_args, - .exec = help_exec, -}; - -/* -Command -twophase_cmd = { - .name = "twophase", - .usage = "twophase", - .description = "Find a solution quickly using a 2-phase method", - .parse_args = parse_only_scramble, - .exec = twophase_exec, -}; -*/ - -Command -quit_cmd = { - .name = "quit", - .usage = "quit", - .description = "Quit nissy", - .parse_args = parse_no_arg, - .exec = quit_exec, -}; - -Command -cleanup_cmd = { - .name = "cleanup", - .usage = "cleanup SCRAMBLE", - .description = "Rewrite a scramble using only standard moves (HTM)", - .parse_args = parse_only_scramble, - .exec = cleanup_exec, -}; - -Command -unniss_cmd = { - .name = "unniss", - .usage = "unniss SCRAMBLE", - .description = "Rewrite a scramble without NISS", - .parse_args = parse_only_scramble, - .exec = unniss_exec, -}; - -Command -version_cmd = { - .name = "version", - .usage = "version", - .description = "print nissy version", - .parse_args = parse_no_arg, - .exec = version_exec, -}; - -Command *commands[] = { - &commands_cmd, - &freemem_cmd, - &gen_cmd, - &help_cmd, - &invert_cmd, - &print_cmd, - &quit_cmd, - &solve_cmd, - &scramble_cmd, - &steps_cmd, -/* &twophase_cmd,*/ - &cleanup_cmd, - &unniss_cmd, - &version_cmd, - NULL -}; - -#endif - -#endif diff --git a/src/coord.c b/src/coord.c deleted file mode 100644 index 673434f..0000000 --- a/src/coord.c +++ /dev/null @@ -1,654 +0,0 @@ -#define COORD_C - -#include "coord.h" - -static void gen_coord_comp(Coordinate *coord); -static void gen_coord_sym(Coordinate *coord); -static bool read_coord_mtable(Coordinate *coord); -static bool read_coord_sd(Coordinate *coord); -static bool read_coord_ttable(Coordinate *coord); -static bool write_coord_mtable(Coordinate *coord); -static bool write_coord_sd(Coordinate *coord); -static bool write_coord_ttable(Coordinate *coord); - -/* 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_cpudsep(Cube *cube) -{ - int i, c[8]; - - for (i = 0; i < 8; i++) - c[i] = cube->cp[i] < 4 ? 0 : 1; - - return (uint64_t)subset_to_index(c, 8, 4); -} - -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_cpudsep(uint64_t ind, Cube *cube) -{ - int i, j, k, c[8]; - - index_to_subset(ind, 8, 4, c); - for (i = 0, j = 0, k = 4; i < 8; i++) - cube->cp[i] = c[i] == 0 ? j++ : k++; -} - - -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 *****************************************************/ - -uint64_t -indexers_getmax(Indexer **is) -{ - int i; - uint64_t max = 1; - - for (i = 0; is[i] != NULL; i++) - max *= is[i]->n; - - return max; -} - -uint64_t -indexers_getind(Indexer **is, Cube *c) -{ - int i; - uint64_t max = 0; - - for (i = 0; is[i] != NULL; i++) { - max *= is[i]->n; - max += is[i]->index(c); - } - - return max; -} - -void -indexers_makecube(Indexer **is, uint64_t ind, Cube *c) -{ - /* Warning: anti-indexers are applied in the same order as indexers. */ - /* We assume order does not matter, but it would make more sense to */ - /* apply them in reverse. */ - - int i; - uint64_t m; - - make_solved(c); - m = indexers_getmax(is); - for (i = 0; is[i] != NULL; i++) { - m /= is[i]->n; - is[i]->to_cube(ind / m, c); - ind %= m; - } -} - -static void -gen_coord_comp(Coordinate *coord) -{ - uint64_t ui; - Cube c, mvd; - Move m; - Trans t; - - coord->max = indexers_getmax(coord->i); - - for (m = 0; m < NMOVES; m++) - coord->mtable[m] = malloc(coord->max * sizeof(uint64_t)); - - for (t = 0; t < NTRANS; t++) - coord->ttable[t] = malloc(coord->max * sizeof(uint64_t)); - - if (!read_coord_mtable(coord)) { - fprintf(stderr, "%s: generating mtable\n", coord->name); - - for (ui = 0; ui < coord->max; ui++) { - indexers_makecube(coord->i, ui, &c); - for (m = 0; m < NMOVES; m++) { - copy_cube(&c, &mvd); - apply_move(m, &mvd); - coord->mtable[m][ui] = - indexers_getind(coord->i, &mvd); - } - } - if (!write_coord_mtable(coord)) - fprintf(stderr, "%s: error writing mtable\n", - coord->name); - - fprintf(stderr, "%s: mtable generated\n", coord->name); - } - - if (!read_coord_ttable(coord)) { - fprintf(stderr, "%s: generating ttable\n", coord->name); - - for (ui = 0; ui < coord->max; ui++) { - indexers_makecube(coord->i, ui, &c); - for (t = 0; t < NTRANS; t++) { - copy_cube(&c, &mvd); - apply_trans(t, &mvd); - coord->ttable[t][ui] = - indexers_getind(coord->i, &mvd); - } - } - if (!write_coord_ttable(coord)) - fprintf(stderr, "%s: error writing ttable\n", - coord->name); - } -} - -static void -gen_coord_sym(Coordinate *coord) -{ - uint64_t i, in, ui, uj, uu, M, nr; - int j; - Move m; - Trans t; - - M = coord->base[0]->max; - coord->selfsim = malloc(M * sizeof(uint64_t)); - coord->symclass = malloc(M * sizeof(uint64_t)); - coord->symrep = malloc(M * sizeof(uint64_t)); - coord->transtorep = malloc(M * sizeof(Trans)); - - if (!read_coord_sd(coord)) { - fprintf(stderr, "%s: generating syms\n", coord->name); - - for (i = 0; i < M; i++) - coord->symclass[i] = M+1; - - for (i = 0, nr = 0; i < M; i++) { - if (coord->symclass[i] != M+1) - continue; - - coord->symrep[nr] = i; - coord->transtorep[i] = uf; - coord->selfsim[nr] = (uint64_t)0; - for (j = 0; j < coord->tgrp->n; j++) { - t = coord->tgrp->t[j]; - in = trans_coord(coord->base[0], t, i); - coord->symclass[in] = nr; - if (in == i) - coord->selfsim[nr] |= ((uint64_t)1<transtorep[in] = - inverse_trans(t); - } - nr++; - } - - coord->max = nr; - - fprintf(stderr, "%s: found %" PRIu64 " classes\n", - coord->name, nr); - if (!write_coord_sd(coord)) - fprintf(stderr, "%s: error writing symdata\n", - coord->name); - } - - coord->symrep = realloc(coord->symrep, coord->max*sizeof(uint64_t)); - coord->selfsim = realloc(coord->selfsim, coord->max*sizeof(uint64_t)); - - for (m = 0; m < NMOVES; m++) { - coord->mtable[m] = malloc(coord->max*sizeof(uint64_t)); - coord->ttrep_move[m] = malloc(coord->max*sizeof(Trans)); - } - - if (!read_coord_mtable(coord)) { - for (ui = 0; ui < coord->max; ui++) { - uu = coord->symrep[ui]; - for (m = 0; m < NMOVES; m++) { - uj = move_coord(coord->base[0], m, uu, NULL); - coord->mtable[m][ui] = coord->symclass[uj]; - coord->ttrep_move[m][ui] = - coord->transtorep[uj]; - } - } - if (!write_coord_mtable(coord)) - fprintf(stderr, "%s: error writing mtable\n", - coord->name); - } -} - -static bool -read_coord_mtable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Move m; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/mt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - M = coord->max; - r = true; - for (m = 0; m < NMOVES; m++) - r = r && fread(coord->mtable[m], sizeof(uint64_t), M, f) == M; - - if (coord->type == SYM_COORD) - for (m = 0; m < NMOVES; m++) - r = r && fread(coord->ttrep_move[m], - sizeof(Trans), M, f) == M; - - fclose(f); - return r; -} - -static bool -read_coord_sd(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t M, N; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/sd_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = true; - r = r && fread(&coord->max, sizeof(uint64_t), 1, f) == 1; - M = coord->max; - N = coord->base[0]->max; - r = r && fread(coord->symrep, sizeof(uint64_t), M, f) == M; - r = r && fread(coord->selfsim, sizeof(uint64_t), M, f) == M; - r = r && fread(coord->symclass, sizeof(uint64_t), N, f) == N; - r = r && fread(coord->transtorep, sizeof(Trans), N, f) == N; - - fclose(f); - return r; -} - -static bool -read_coord_ttable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Trans t; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/tt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - M = coord->max; - r = true; - for (t = 0; t < NTRANS; t++) - r = r && fread(coord->ttable[t], sizeof(uint64_t), M, f) == M; - - fclose(f); - return r; -} - -static bool -write_coord_mtable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Move m; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/mt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - M = coord->max; - r = true; - for (m = 0; m < NMOVES; m++) - r = r && fwrite(coord->mtable[m], sizeof(uint64_t), M, f) == M; - - if (coord->type == SYM_COORD) - for (m = 0; m < NMOVES; m++) - r = r && fwrite(coord->ttrep_move[m], - sizeof(Trans), M, f) == M; - - fclose(f); - return r; -} - -static bool -write_coord_sd(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t M, N; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/sd_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - r = true; - M = coord->max; - N = coord->base[0]->max; - r = r && fwrite(&coord->max, sizeof(uint64_t), 1, f) == 1; - r = r && fwrite(coord->symrep, sizeof(uint64_t), M, f) == M; - r = r && fwrite(coord->selfsim, sizeof(uint64_t), M, f) == M; - r = r && fwrite(coord->symclass, sizeof(uint64_t), N, f) == N; - r = r && fwrite(coord->transtorep, sizeof(Trans), N, f) == N; - - fclose(f); - return r; -} - -static bool -write_coord_ttable(Coordinate *coord) -{ - FILE *f; - char fname[strlen(tabledir)+256]; - Trans t; - uint64_t M; - bool r; - - strcpy(fname, tabledir); - strcat(fname, "/tt_"); - strcat(fname, coord->name); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - M = coord->max; - r = true; - for (t = 0; t < NTRANS; t++) - r = r && fwrite(coord->ttable[t], sizeof(uint64_t), M, f) == M; - - fclose(f); - return r; -} - -/* Public functions **********************************************************/ - -void -gen_coord(Coordinate *coord) -{ - int i; - - if (coord == NULL || coord->generated) - return; - - for (i = 0; i < 2; i++) - gen_coord(coord->base[i]); - - switch (coord->type) { - case COMP_COORD: - if (coord->i[0] == NULL) - goto error_gc; - gen_coord_comp(coord); - break; - case SYM_COORD: - if (coord->base[0] == NULL || coord->tgrp == NULL) - goto error_gc; - gen_coord_sym(coord); - break; - case SYMCOMP_COORD: - if (coord->base[0] == NULL || coord->base[1] == NULL) - goto error_gc; - coord->max = coord->base[0]->max * coord->base[1]->max; - break; - default: - break; - } - - coord->generated = true; - return; - -error_gc: - fprintf(stderr, "Error generating coordinates.\n" - "This is a bug, pleae report.\n"); - exit(1); -} - -uint64_t -index_coord(Coordinate *coord, Cube *cube, Trans *offtrans) -{ - uint64_t c[2], cnosym; - Trans ttr; - - switch (coord->type) { - case COMP_COORD: - if (offtrans != NULL) - *offtrans = uf; - - return indexers_getind(coord->i, cube); - case SYM_COORD: - cnosym = index_coord(coord->base[0], cube, NULL); - ttr = coord->transtorep[cnosym]; - - if (offtrans != NULL) - *offtrans = ttr; - - return coord->symclass[cnosym]; - case SYMCOMP_COORD: - c[0] = index_coord(coord->base[0], cube, NULL); - cnosym = index_coord(coord->base[0]->base[0], cube, NULL); - ttr = coord->base[0]->transtorep[cnosym]; - c[1] = index_coord(coord->base[1], cube, NULL); - c[1] = trans_coord(coord->base[1], ttr, c[1]); - - if (offtrans != NULL) - *offtrans = ttr; - - return c[0] * coord->base[1]->max + c[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} - -uint64_t -move_coord(Coordinate *coord, Move m, uint64_t ind, Trans *offtrans) -{ - uint64_t i[2], M; - Trans ttr; - - /* Some safety checks should be done here, but for performance * - * reasons we'd rather do them before calling this function. * - * We should check if coord is generated. */ - - switch (coord->type) { - case COMP_COORD: - if (offtrans != NULL) - *offtrans = uf; - - return coord->mtable[m][ind]; - case SYM_COORD: - ttr = coord->ttrep_move[m][ind]; - - if (offtrans != NULL) - *offtrans = ttr; - - return coord->mtable[m][ind]; - case SYMCOMP_COORD: - M = coord->base[1]->max; - i[0] = ind / M; - i[1] = ind % M; - ttr = coord->base[0]->ttrep_move[m][i[0]]; - i[0] = coord->base[0]->mtable[m][i[0]]; - i[1] = coord->base[1]->mtable[m][i[1]]; - i[1] = coord->base[1]->ttable[ttr][i[1]]; - - if (offtrans != NULL) - *offtrans = ttr; - - return i[0] * M + i[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} - -uint64_t -trans_coord(Coordinate *coord, Trans t, uint64_t ind) -{ - uint64_t i[2], M; - - /* Some safety checks should be done here, but for performance * - * reasons we'd rather do them before calling this function. * - * We should check if coord is generated. */ - - switch (coord->type) { - case COMP_COORD: - return coord->ttable[t][ind]; - case SYM_COORD: - return ind; - case SYMCOMP_COORD: - M = coord->base[1]->max; - i[0] = ind / M; /* Always fixed */ - i[1] = ind % M; - i[1] = coord->base[1]->ttable[t][i[1]]; - return i[0] * M + i[1]; - default: - break; - } - - return coord->max; /* Only reached in case of error */ -} diff --git a/src/coord.h b/src/coord.h deleted file mode 100644 index 4cd7e47..0000000 --- a/src/coord.h +++ /dev/null @@ -1,259 +0,0 @@ -#ifndef COORD_H -#define COORD_H - -#include "trans.h" - -void gen_coord(Coordinate *coord); -uint64_t index_coord(Coordinate *coord, Cube *cube, - Trans *offtrans); -uint64_t indexers_getind(Indexer **is, Cube *c); -void indexers_makecube(Indexer **is, uint64_t ind, Cube *c); -uint64_t move_coord(Coordinate *coord, Move m, - uint64_t ind, Trans *offtrans); -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_cpudsep; -extern Coordinate coord_epos; -extern Coordinate coord_epe; -extern Coordinate coord_eposepe; -extern Coordinate coord_epud; -extern Coordinate coord_eofbepos; -extern Coordinate coord_coud_cpudsep; -extern Coordinate coord_eofbepos_sym16; -extern Coordinate coord_cp_sym16; -extern Coordinate coord_corners_sym16; -extern Coordinate coord_drud_sym16; -extern Coordinate coord_drudfin_noE_sym16; -extern Coordinate coord_nxopt31; - -extern Coordinate *all_coordinates[]; - -#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_cpudsep(Cube *cube); -void invindex_cpudsep(uint64_t ind, Cube *ret); -Indexer -i_cpudsep = { - .n = BINOM8ON4, - .index = index_cpudsep, - .to_cube = invindex_cpudsep, -}; - -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_cpudsep = { - .name = "cpudsep", - .type = COMP_COORD, - .i = {&i_cpudsep, 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 = { /* Has to be done by hand, hard compose epos + epe */ - .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}, -}; - -Coordinate -coord_coud_cpudsep = { - .name = "coud_cpudsep", - .type = COMP_COORD, - .i = {&i_coud, &i_cpudsep, 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_corners_sym16 = { - .name = "corners_sym16", - .type = SYMCOMP_COORD, - .base = {&coord_cp_sym16, &coord_coud}, -}; - -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}, -}; - -Coordinate -coord_nxopt31 = { - .name = "nxopt31", - .type = SYMCOMP_COORD, - .base = {&coord_eofbepos_sym16, &coord_coud_cpudsep}, -}; - -/* All coordinates ***********************************************************/ - -Coordinate *all_coordinates[] = { - &coord_eofb, - &coord_coud, - &coord_cp, - &coord_cpudsep, - &coord_epos, - &coord_epe, - &coord_eposepe, - &coord_epud, - &coord_eofbepos, - &coord_coud_cpudsep, - &coord_eofbepos_sym16, - &coord_cp_sym16, - &coord_corners_sym16, - &coord_drud_sym16, - &coord_drudfin_noE_sym16, - &coord_nxopt31, - NULL -}; - -#endif - -#endif - diff --git a/src/cube.c b/src/cube.c deleted file mode 100644 index 92c6713..0000000 --- a/src/cube.c +++ /dev/null @@ -1,270 +0,0 @@ -#define CUBE_C - -#include "cube.h" - -static int where_is_piece(int piece, int *arr, int n); - -void -compose_centers(Cube *c2, Cube *c1) -{ - apply_permutation(c2->xp, c1->xp, 6); -} - -void -compose_corners(Cube *c2, Cube *c1) -{ - apply_permutation(c2->cp, c1->cp, 8); - apply_permutation(c2->cp, c1->co, 8); - sum_arrays_mod(c2->co, c1->co, 8, 3); -} - -void -compose_edges(Cube *c2, Cube *c1) -{ - apply_permutation(c2->ep, c1->ep, 12); - apply_permutation(c2->ep, c1->eo, 12); - sum_arrays_mod(c2->eo, c1->eo, 12, 2); -} - -void -compose(Cube *c2, Cube *c1) -{ - compose_centers(c2, c1); - compose_corners(c2, c1); - compose_edges(c2, c1); -} - -void -copy_cube_centers(Cube *src, Cube *dst) -{ - memcpy(dst->xp, src->xp, 6 * sizeof(int)); -} - -void -copy_cube_corners(Cube *src, Cube *dst) -{ - memcpy(dst->cp, src->cp, 8 * sizeof(int)); - memcpy(dst->co, src->co, 8 * sizeof(int)); -} - -void -copy_cube_edges(Cube *src, Cube *dst) -{ - memcpy(dst->ep, src->ep, 12 * sizeof(int)); - memcpy(dst->eo, src->eo, 12 * sizeof(int)); -} - -void -copy_cube(Cube *src, Cube *dst) -{ - copy_cube_centers(src, dst); - copy_cube_corners(src, dst); - copy_cube_edges(src, dst); -} - -bool -equal(Cube *c1, Cube *c2) -{ - int i; - - for (i = 0; i < 12; i++) - if (c1->ep[i] != c2->ep[i] || c1->eo[i] != c2->eo[i]) - return false; - - for (i = 0; i < 8; i++) - if (c1->cp[i] != c2->cp[i] || c1->co[i] != c2->co[i]) - return false; - - for (i = 0; i < 6; i++) - if (c1->xp[i] != c2->xp[i]) - return false; - - return true; -} - -void -invert_cube_centers(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_centers(cube, &aux); - - for (i = 0; i < 6; i++) - cube->xp[aux.xp[i]] = i; -} - -void -invert_cube_corners(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_corners(cube, &aux); - - for (i = 0; i < 8; i++) { - cube->cp[aux.cp[i]] = i; - cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3; - } -} - -void -invert_cube_edges(Cube *cube) -{ - int i; - Cube aux; - - copy_cube_edges(cube, &aux); - - for (i = 0; i < 12; i++) { - cube->ep[aux.ep[i]] = i; - cube->eo[aux.ep[i]] = aux.eo[i]; - } -} - -void -invert_cube(Cube *cube) -{ - invert_cube_centers(cube); - invert_cube_corners(cube); - invert_cube_edges(cube); -} - -bool -is_admissible(Cube *c) { - bool perm; - int sign, i; - int sum_e, sum_c; - - perm = is_perm(c->ep, 12) && is_perm(c->cp, 8) && is_perm(c->xp, 6); - - sign = perm_sign(c->ep,12) + perm_sign(c->cp,8) + perm_sign(c->xp,6); - - for (i = 0, sum_e = 0; i < 12; i++) - if (c->eo[i] > 1) - return false; - else - sum_e += c->eo[i]; - - for (i = 0, sum_c = 0; i < 8; i++) - if (c->co[i] > 2) - return false; - else - sum_c += c->co[i]; - - return (perm && sign % 2 == 0 && sum_e % 2 == 0 && sum_c % 2 == 0); -} - -bool -is_solved(Cube *cube) -{ - Cube solved_cube; - make_solved(&solved_cube); - - return equal(cube, &solved_cube); -} - -void -make_solved_centers(Cube *cube) -{ - static int sorted[6] = {0, 1, 2, 3, 4, 5}; - - memcpy(cube->xp, sorted, 6 * sizeof(int)); -} - -void -make_solved_corners(Cube *cube) -{ - static int sorted[8] = {0, 1, 2, 3, 4, 5, 6, 7}; - - memcpy(cube->cp, sorted, 8 * sizeof(int)); - memset(cube->co, 0, 8 * sizeof(int)); -} - -void -make_solved_edges(Cube *cube) -{ - static int sorted[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}; - - memcpy(cube->ep, sorted, 12 * sizeof(int)); - memset(cube->eo, 0, 12 * sizeof(int)); -} - -void -make_solved(Cube *cube) -{ - make_solved_centers(cube); - make_solved_corners(cube); - make_solved_edges(cube); -} - -void -print_cube(Cube *cube) -{ - static char edge_string[12][7] = { - [UF] = "UF", [UL] = "UL", [UB] = "UB", [UR] = "UR", - [DF] = "DF", [DL] = "DL", [DB] = "DB", [DR] = "DR", - [FR] = "FR", [FL] = "FL", [BL] = "BL", [BR] = "BR" - }; - - static char corner_string[8][7] = { - [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR", - [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR" - }; - - static char center_string[6][7] = { - [U_center] = "U", [D_center] = "D", - [R_center] = "R", [L_center] = "L", - [F_center] = "F", [B_center] = "B" - }; - - for (int i = 0; i < 12; i++) - printf(" %s ", edge_string[cube->ep[i]]); - printf("\n"); - - for (int i = 0; i < 12; i++) - printf(" %" PRIu8 " ", cube->eo[i]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf("%s ", corner_string[cube->cp[i]]); - printf("\n"); - - for (int i = 0; i < 8; i++) - printf(" %" PRIu8 " ", cube->co[i]); - printf("\n"); - - for (int i = 0; i < 6; i++) - printf(" %s ", center_string[cube->xp[i]]); - printf("\n"); -} - -int -where_is_center(Center x, Cube *c) -{ - return where_is_piece(x, c->xp, 6); -} - -int -where_is_corner(Corner k, Cube *c) -{ - return where_is_piece(k, c->cp, 8); -} - -int -where_is_edge(Edge e, Cube *c) -{ - return where_is_piece(e, c->ep, 12); -} - -static int -where_is_piece(int piece, int *arr, int n) -{ - int i; - - for (i = 0; i < n; i++) - if (arr[i] == piece) - return i; - - return -1; -} diff --git a/src/cube.h b/src/cube.h deleted file mode 100644 index f182b27..0000000 --- a/src/cube.h +++ /dev/null @@ -1,35 +0,0 @@ -#ifndef CUBE_H -#define CUBE_H - -#include - -#include "cubetypes.h" -#include "env.h" -#include "utils.h" - -void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */ -void compose_centers(Cube *c2, Cube *c1); -void compose_corners(Cube *c2, Cube *c1); -void compose_edges(Cube *c2, Cube *c1); -void copy_cube(Cube *src, Cube *dst); -void copy_cube_centers(Cube *src, Cube *dst); -void copy_cube_corners(Cube *src, Cube *dst); -void copy_cube_edges(Cube *src, Cube *dst); -bool equal(Cube *c1, Cube *c2); -void invert_cube(Cube *cube); -void invert_cube_centers(Cube *cube); -void invert_cube_corners(Cube *cube); -void invert_cube_edges(Cube *cube); -bool is_admissible(Cube *cube); -bool is_solved(Cube *cube); -void make_solved(Cube *cube); -void make_solved_centers(Cube *cube); -void make_solved_corners(Cube *cube); -void make_solved_edges(Cube *cube); -void print_cube(Cube *cube); -int where_is_center(Center x, Cube *c); -int where_is_corner(Corner k, Cube *c); -int where_is_edge(Edge e, Cube *c); - -#endif - diff --git a/src/cubetypes.h b/src/cubetypes.h deleted file mode 100644 index 3752019..0000000 --- a/src/cubetypes.h +++ /dev/null @@ -1,360 +0,0 @@ -#ifndef CUBETYPES_H -#define CUBETYPES_H - -#include -#include -#include - -#define NMOVES 55 /* Actually 54, but one is NULLMOVE */ -#define NTRANS 48 -#define NROTATIONS 24 -#define entry_group_t uint8_t /* For pruning tables */ - -#define MAX_N_COORD 6 - -/* Enums *********************************************************************/ - -typedef enum -center -{ - U_center, D_center, - R_center, L_center, - F_center, B_center -} Center; - -typedef enum -corner -{ - UFR, UFL, UBL, UBR, - DFR, DFL, DBL, DBR -} Corner; - -typedef enum -coordtype -{ - COMP_COORD, SYM_COORD, SYMCOMP_COORD -} CoordType; - -typedef enum -edge -{ - UF, UL, UB, UR, - DF, DL, DB, DR, - FR, FL, BL, BR -} Edge; - -typedef enum -move -{ - NULLMOVE, - U, U2, U3, D, D2, D3, - R, R2, R3, L, L2, L3, - F, F2, F3, B, B2, B3, - Uw, Uw2, Uw3, Dw, Dw2, Dw3, - Rw, Rw2, Rw3, Lw, Lw2, Lw3, - Fw, Fw2, Fw3, Bw, Bw2, Bw3, - M, M2, M3, - S, S2, S3, - E, E2, E3, - x, x2, x3, - y, y2, y3, - z, z2, z3, -} Move; - -typedef enum -trans -{ - uf, ur, ub, ul, - df, dr, db, dl, - rf, rd, rb, ru, - lf, ld, lb, lu, - fu, fr, fd, fl, - bu, br, bd, bl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror, - rf_mirror, rd_mirror, rb_mirror, ru_mirror, - lf_mirror, ld_mirror, lb_mirror, lu_mirror, - fu_mirror, fr_mirror, fd_mirror, fl_mirror, - bu_mirror, br_mirror, bd_mirror, bl_mirror, -} Trans; - - -/* Typedefs ******************************************************************/ - -typedef struct alg Alg; -typedef struct alglist AlgList; -typedef struct alglistnode AlgListNode; -typedef struct choicestep ChoiceStep; -typedef struct command Command; -typedef struct commandargs CommandArgs; -typedef struct coordinate Coordinate; -typedef struct cube Cube; -/*typedef struct dfsarg DfsArg;*/ -typedef struct fstcube FstCube; -typedef struct indexer Indexer; -typedef struct movable Movable; -typedef struct moveset Moveset; -typedef struct prunedata PruneData; -typedef struct solveoptions SolveOptions; -typedef struct step Step; -typedef struct symdata SymData; -typedef struct threaddatasolve ThreadDataSolve; -typedef struct threaddatagenpt ThreadDataGenpt; -typedef struct transgroup TransGroup; - -typedef bool (*Checker) (Cube *); -typedef bool (*CubeTester) (Cube *, Alg *); -/*typedef bool (*DfsMover) (DfsArg *);*/ -typedef void (*DfsExtraCopier) (void *, void *); -typedef Alg * (*Validator) (Alg *); -typedef void (*Exec) (CommandArgs *); -typedef CommandArgs * (*ArgParser) (int, char **); -typedef bool (*Tester) (void); -typedef int (*TransFinder) (uint64_t, Trans *); - - -/* Structs *******************************************************************/ - -struct -alg -{ - Move * move; - bool * inv; - int len; - int allocated; - Move * move_normal; - int len_normal; - Move * move_inverse; - int len_inverse; -}; - -struct -alglist -{ - AlgListNode * first; - AlgListNode * last; - int len; -}; - -struct -alglistnode -{ - Alg * alg; - AlgListNode * next; -}; - -struct -choicestep -{ - char * shortname; - char * name; - Step * step[99]; - Trans t[99]; - char * ready_msg; -}; - -struct -command -{ - char * name; - char * usage; - char * description; - ArgParser parse_args; - Exec exec; -}; - -struct -commandargs -{ - bool success; - Alg * scramble; - SolveOptions * opts; - ChoiceStep * cs; - Command * command; /* For help */ - int n; - char scrtype[20]; - bool scrstdin; - bool header; -}; - -struct -coordinate -{ - char * name; - CoordType type; - bool generated; - Indexer * i[99]; - uint64_t max; - uint64_t * mtable[NMOVES]; - uint64_t * ttable[NTRANS]; - TransGroup * tgrp; - Coordinate * base[2]; - uint64_t * symclass; - uint64_t * symrep; - Trans * transtorep; - Trans * ttrep_move[NMOVES]; - uint64_t * selfsim; -}; - -struct -cube -{ - int ep[12]; - int eo[12]; - int cp[8]; - int co[8]; - int xp[6]; -}; - -/* -struct -movable -{ - uint64_t val; - Trans t; -}; -*/ - -/* -struct -dfsarg -{ - Cube * cube; - Movable ind[MAX_N_COORD]; - Trans t; - Step * s; - SolveOptions * opts; - int d; - int bound; - bool niss; - AlgList * sols; - pthread_mutex_t * sols_mutex; - Alg * current_alg; - void * extra; -}; -*/ - -/* -struct -dfsarg -{ - void * cube_data; - SolveOptions * opts; - int d; - int bound; - bool niss; - AlgList * sols; - Alg * current_alg; - Solver * solver; - Threader * threader; -}; -*/ - -struct -fstcube -{ - uint16_t uf_eofb; - uint16_t uf_eposepe; - uint16_t uf_coud; - uint16_t uf_cp; - uint16_t fr_eofb; - uint16_t fr_eposepe; - uint16_t fr_coud; - uint16_t rd_eofb; - uint16_t rd_eposepe; - uint16_t rd_coud; -}; - -struct -indexer -{ - int n; - uint64_t (*index)(Cube *); - void (*to_cube)(uint64_t, Cube *); -}; - -struct -moveset -{ - char * name; - bool (*allowed)(Move); - bool (*can_append)(Alg *, Move, bool); - bool (*cancel_niss)(Alg *); - Move sorted_moves[NMOVES+1]; -}; - -struct -prunedata -{ - entry_group_t * ptable; - uint64_t n; - Coordinate * coord; - Moveset * moveset; - uint64_t count[16]; - bool compact; - int base; -}; - -struct -solveoptions -{ - int min_moves; - int max_moves; - int max_solutions; - int nthreads; - int optimal; - bool can_niss; - bool verbose; - bool all; - bool print_number; - bool count_only; -}; - -struct -step -{ - Checker ready; - bool final; - Moveset * moveset; - int n_coord; - 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; -}; - -/* -struct -threaddatasolve -{ - DfsArg arg; - int thid; - AlgList * start; - AlgListNode ** node; - pthread_mutex_t * start_mutex; -}; -*/ - -struct -threaddatagenpt -{ - int thid; - int nthreads; - PruneData * pd; - int d; - int nchunks; - pthread_mutex_t ** mutex; - pthread_mutex_t * upmutex; -}; - -struct -transgroup -{ - int n; - Trans t[NTRANS]; -}; - -#endif diff --git a/src/env.c b/src/env.c deleted file mode 100644 index 375bfa8..0000000 --- a/src/env.c +++ /dev/null @@ -1,60 +0,0 @@ -#define ENV_C - -#include "env.h" - -bool initialized_env = false; -char *tabledir; - -void -mymkdir(char *d, int m) -{ -#ifdef _WIN32 - mkdir(d); -#else - mkdir(d, m); -#endif -} - -void -init_env() -{ - char *nissydata = getenv("NISSYDATA"); - char *localdata = getenv("XDG_DATA_HOME"); - char *home = getenv("HOME"); - bool read, write; - - if (initialized_env) - return; - - if (nissydata != NULL) { - tabledir = malloc((strlen(nissydata) + 20) * sizeof(char)); - strcpy(tabledir, nissydata); - } else if (localdata != NULL) { - tabledir = malloc((strlen(localdata) + 20) * sizeof(char)); - strcpy(tabledir, localdata); - strcat(tabledir, "/nissy"); - } else if (home != NULL) { - tabledir = malloc((strlen(home) + 20) * sizeof(char)); - strcpy(tabledir, home); - strcat(tabledir, "/.nissy"); - } else { - tabledir = malloc(20 * sizeof(char)); - strcpy(tabledir, "."); - } - - mymkdir(tabledir, 0777); - strcat(tabledir, "/tables"); - mymkdir(tabledir, 0777); - - read = !access(tabledir, R_OK); - write = !access(tabledir, W_OK); - - if (!read) { - fprintf(stderr, "Table files cannot be read.\n"); - } else if (!write) { - fprintf(stderr, "Data directory not writable: "); - fprintf(stderr, "tables can be loaded, but not saved.\n"); - } - - initialized_env = true; -} diff --git a/src/env.h b/src/env.h deleted file mode 100644 index a49d643..0000000 --- a/src/env.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef ENV_H -#define ENV_H - -#include -#include -#include -#include -#include -#include - -void init_env(); - -extern char *tabledir; - -#endif diff --git a/src/fst.c b/src/fst.c deleted file mode 100644 index b51e2d4..0000000 --- a/src/fst.c +++ /dev/null @@ -1,401 +0,0 @@ -#define FST_C - -#include "fst.h" - -static FstCube ep_to_fst_epos(int *ep); -static void init_fst_corner_invtables(); -static void init_fst_eo_invtables(); -static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *); -static void init_fst_where_is_edge(); -static bool read_fst_tables_file(); -static bool write_fst_tables_file(); - -static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0, - [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1, - [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2}; - -static uint16_t inv_coud[FACTORIAL8][POW3TO7]; -static uint16_t inv_cp[FACTORIAL8]; -static uint16_t uf_cp_to_fr_cp[FACTORIAL8]; -static uint16_t uf_cp_to_rd_cp[FACTORIAL8]; -static uint16_t eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4]; -static uint16_t fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4]; - -FstCube -cube_to_fst(Cube *cube) -{ - Cube c; - FstCube ret; - - copy_cube(cube, &c); - ret.uf_eofb = coord_eofb.i[0]->index(&c); - ret.uf_eposepe = coord_eposepe.i[0]->index(&c); - ret.uf_coud = coord_coud.i[0]->index(&c); - ret.uf_cp = coord_cp.i[0]->index(&c); - copy_cube(cube, &c); - apply_trans(fr, &c); - ret.fr_eofb = coord_eofb.i[0]->index(&c); - ret.fr_eposepe = coord_eposepe.i[0]->index(&c); - ret.fr_coud = coord_coud.i[0]->index(&c); - copy_cube(cube, &c); - apply_trans(rd, &c); - ret.rd_eofb = coord_eofb.i[0]->index(&c); - ret.rd_eposepe = coord_eposepe.i[0]->index(&c); - ret.rd_coud = coord_coud.i[0]->index(&c); - - return ret; -} - -static FstCube -ep_to_fst_epos(int *ep) -{ - static int eind[12] = { - [FR] = 0, [FL] = 1, [BL] = 2, [BR] = 3, - [UR] = 0, [DR] = 1, [DL] = 2, [UL] = 3, - [DB] = 0, [DF] = 1, [UF] = 2, [UB] = 3 - }; - static int eptrans_fr[12] = { - [FR] = UF, [DF] = UL, [FL] = UB, [UF] = UR, - [BR] = DF, [DB] = DL, [BL] = DB, [UB] = DR, - [UR] = FR, [DR] = FL, [DL] = BL, [UL] = BR - }; - static int eptrans_rd[12] = { - [DR] = UF, [FR] = UL, [UR] = UB, [BR] = UR, - [DL] = DF, [FL] = DL, [UL] = DB, [BL] = DR, - [DB] = FR, [DF] = FL, [UF] = BL, [UB] = BR - }; - - FstCube ret; - int i, ce, cs, cm; - int epe[4], eps[4], epm[4], epose[12], eposs[12], eposm[12]; - - memset(epose, 0, 12*sizeof(int)); - memset(eposs, 0, 12*sizeof(int)); - memset(eposm, 0, 12*sizeof(int)); - - for (i = 0, ce = 0; i < 12; i++) { - switch (edge_slice[ep[i]]) { - case 0: - epose[i] = 1; - epe[ce++] = eind[ep[i]]; - break; - case 1: - eposs[eptrans_fr[i]] = eind[ep[i]] + 1; - break; - default: - eposm[eptrans_rd[i]] = eind[ep[i]] + 1; - break; - } - } - - for (i = 0, cs = 0, cm = 0; i < 12; i++) { - if (eposs[i]) { - eps[cs++] = eposs[i] - 1; - eposs[i] = 1; - } - if (eposm[i]) { - epm[cm++] = eposm[i] - 1; - eposm[i] = 1; - } - } - - ret.uf_eposepe = subset_to_index(epose, 12, 4) * FACTORIAL4 + - perm_to_index(epe, 4); - ret.fr_eposepe = subset_to_index(eposs, 12, 4) * FACTORIAL4 + - perm_to_index(eps, 4); - ret.rd_eposepe = subset_to_index(eposm, 12, 4) * FACTORIAL4 + - perm_to_index(epm, 4); - - return ret; -} - -FstCube -fst_inverse(FstCube fst) -{ - FstCube ret; - int ep_inv[12]; - - ep_inv[FR] = fst_where_is_edge_arr[0][FR][fst.uf_eposepe]; - ep_inv[FL] = fst_where_is_edge_arr[0][FL][fst.uf_eposepe]; - ep_inv[BL] = fst_where_is_edge_arr[0][BL][fst.uf_eposepe]; - ep_inv[BR] = fst_where_is_edge_arr[0][BR][fst.uf_eposepe]; - - ep_inv[UR] = fst_where_is_edge_arr[1][UR][fst.fr_eposepe]; - ep_inv[UL] = fst_where_is_edge_arr[1][UL][fst.fr_eposepe]; - ep_inv[DR] = fst_where_is_edge_arr[1][DR][fst.fr_eposepe]; - ep_inv[DL] = fst_where_is_edge_arr[1][DL][fst.fr_eposepe]; - - ep_inv[UF] = fst_where_is_edge_arr[2][UF][fst.rd_eposepe]; - ep_inv[UB] = fst_where_is_edge_arr[2][UB][fst.rd_eposepe]; - ep_inv[DF] = fst_where_is_edge_arr[2][DF][fst.rd_eposepe]; - ep_inv[DB] = fst_where_is_edge_arr[2][DB][fst.rd_eposepe]; - - ret = ep_to_fst_epos(ep_inv); - - ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]); - ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]); - ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) | - ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) | - ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]); - - ret.uf_cp = inv_cp[fst.uf_cp]; - - ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud]; - ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud]; - ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud]; - - return ret; -} - -FstCube -fst_move(Move m, FstCube fst) -{ - FstCube ret; - Move m_fr, m_rd; - - m_fr = transform_move(fr, m); - m_rd = transform_move(rd, m); - - ret.uf_eofb = coord_eofb.mtable[m][fst.uf_eofb]; - ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe]; - ret.uf_coud = coord_coud.mtable[m][fst.uf_coud]; - ret.uf_cp = coord_cp.mtable[m][fst.uf_cp]; - - ret.fr_eofb = coord_eofb.mtable[m_fr][fst.fr_eofb]; - ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe]; - ret.fr_coud = coord_coud.mtable[m_fr][fst.fr_coud]; - - ret.rd_eofb = coord_eofb.mtable[m_rd][fst.rd_eofb]; - ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe]; - ret.rd_coud = coord_coud.mtable[m_rd][fst.rd_coud]; - - return ret; -} - -void -fst_to_cube(FstCube fst, Cube *cube) -{ - Cube e, s, m; - int i; - - coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e); - coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s); - apply_trans(inverse_trans(fr), &s); - coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m); - apply_trans(inverse_trans(rd), &m); - - for (i = 0; i < 12; i++) { - if (edge_slice[e.ep[i]] == 0) - cube->ep[i] = e.ep[i]; - if (edge_slice[s.ep[i]] == 1) - cube->ep[i] = s.ep[i]; - if (edge_slice[m.ep[i]] == 2) - cube->ep[i] = m.ep[i]; - } - - coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube); - coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube); - coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube); - - for (i = 0; i < 6; i++) - cube->xp[i] = i; -} - -void -init_fst() -{ - init_trans(); - gen_coord(&coord_eofb); - gen_coord(&coord_eposepe); - gen_coord(&coord_coud); - gen_coord(&coord_cp); - - if (!read_fst_tables_file()) { - fprintf(stderr, - "Could not load fst_tables, generating them\n"); - init_fst_corner_invtables(); - init_fst_eo_invtables(); - init_fst_where_is_edge(); - if (!write_fst_tables_file()) - fprintf(stderr, "fst_tables could not be written\b"); - } -} - -static void -init_fst_corner_invtables() -{ - Cube c, d; - uint64_t cp, coud; - - for (cp = 0; cp < FACTORIAL8; cp++) { - make_solved_corners(&c); - coord_cp.i[0]->to_cube(cp, &c); - - copy_cube_corners(&c, &d); - invert_cube_corners(&d); - inv_cp[cp] = coord_cp.i[0]->index(&d); - - for (coud = 0; coud < POW3TO7; coud++) { - copy_cube_corners(&c, &d); - coord_coud.i[0]->to_cube(coud, &d); - invert_cube_corners(&d); - inv_coud[cp][coud] = coord_coud.i[0]->index(&d); - } - - copy_cube_corners(&c, &d); - apply_trans(fr, &d); - uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d); - - copy_cube_corners(&c, &d); - apply_trans(rd, &d); - uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d); - } -} - -static void -init_fst_eo_invtables() -{ - uint64_t ep, eo; - Cube c, d; - - for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) { - make_solved(&c); - coord_eposepe.i[0]->to_cube(ep, &c); - for (eo = 0; eo < POW2TO11; eo++) { - copy_cube_edges(&c, &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 0, &d); - - apply_trans(inverse_trans(fr), &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 1, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(rd), &d); - coord_eofb.i[0]->to_cube(eo, &d); - init_fst_eo_update(eo, ep, 2, &d); - } - } -} - -static void -init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d) -{ - int i; - - for (i = 0; i < 12; i++) { - if (edge_slice[d->ep[i]] == s && d->eo[i] && d->ep[i] != 11) - eo_invtable[s][eo][ep] |= - ((uint16_t)1) << ((uint16_t)d->ep[i]); - } -} - -static void -init_fst_where_is_edge() -{ - Cube c, d; - uint64_t e; - - make_solved(&c); - for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) { - coord_eposepe.i[0]->to_cube(e, &c); - - copy_cube_edges(&c, &d); - fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d); - fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d); - fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d); - fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(fr), &d); - fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d); - fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d); - fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d); - fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d); - - copy_cube_edges(&c, &d); - apply_trans(inverse_trans(rd), &d); - fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d); - fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d); - fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d); - fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &d); - } -} - -static bool -read_fst_tables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t i, j, r, total; - - strcpy(fname, tabledir); - strcat(fname, "/fst_tables"); - - if ((f = fopen(fname, "rb")) == NULL) - return false; - - r = 0; - total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); - - for (i = 0; i < FACTORIAL8; i++) - r += fread(inv_coud[i], sizeof(uint16_t), POW3TO7, f); - r += fread(inv_cp, sizeof(uint16_t), FACTORIAL8, f); - r += fread(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); - r += fread(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); - for (i = 0; i < 3; i++) - for (j = 0; j < POW2TO11; j++) - r += fread(eo_invtable[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - for (i = 0; i < 3; i++) - for (j = 0; j < 12; j++) - r += fread(fst_where_is_edge_arr[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - - fclose(f); - - return r == total; -} - -static bool -write_fst_tables_file() -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - uint64_t i, j, w, total; - - strcpy(fname, tabledir); - strcat(fname, "/fst_tables"); - - if ((f = fopen(fname, "wb")) == NULL) - return false; - - w = 0; - total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); - - for (i = 0; i < FACTORIAL8; i++) - w += fwrite(inv_coud[i], sizeof(uint16_t), POW3TO7, f); - w += fwrite(inv_cp, sizeof(uint16_t), FACTORIAL8, f); - w += fwrite(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); - w += fwrite(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); - for (i = 0; i < 3; i++) - for (j = 0; j < POW2TO11; j++) - w += fwrite(eo_invtable[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - for (i = 0; i < 3; i++) - for (j = 0; j < 12; j++) - w += fwrite(fst_where_is_edge_arr[i][j], - sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); - - fclose(f); - - return w == total; -} diff --git a/src/fst.h b/src/fst.h deleted file mode 100644 index c3b226c..0000000 --- a/src/fst.h +++ /dev/null @@ -1,13 +0,0 @@ -#ifndef FST_H -#define FST_H - -#include "coord.h" - -FstCube cube_to_fst(Cube *cube); -FstCube fst_inverse(FstCube fst); -FstCube fst_move(Move m, FstCube fst); -void fst_to_cube(FstCube fst, Cube *cube); -void init_fst(); - -#endif - diff --git a/src/moves.c b/src/moves.c deleted file mode 100644 index a9dfdc0..0000000 --- a/src/moves.c +++ /dev/null @@ -1,301 +0,0 @@ -#define MOVES_C - -#include "moves.h" - -/* Local functions ***********************************************************/ - -static void cleanup_aux(Alg *alg, Alg *ret, bool inv); - -/* Tables and other data *****************************************************/ - -/* Moves are represented as cubes and applied using compose(). Every move is * - * translated to a an alg before filling the transition tables. * - * See init_moves(). */ - -static Cube move_array[NMOVES]; - -static char equiv_alg_string[100][NMOVES] = { - [NULLMOVE] = "", - - [U] = " U ", - [U2] = " UU ", - [U3] = " UUU ", - [D] = " xx U xx ", - [D2] = " xx UU xx ", - [D3] = " xx UUU xx ", - [R] = " yx U xxxyyy ", - [R2] = " yx UU xxxyyy ", - [R3] = " yx UUU xxxyyy ", - [L] = " yyyx U xxxy ", - [L2] = " yyyx UU xxxy ", - [L3] = " yyyx UUU xxxy ", - [F] = " x U xxx ", - [F2] = " x UU xxx ", - [F3] = " x UUU xxx ", - [B] = " xxx U x ", - [B2] = " xxx UU x ", - [B3] = " xxx UUU x ", - - [Uw] = " xx U xx y ", - [Uw2] = " xx UU xx yy ", - [Uw3] = " xx UUU xx yyy ", - [Dw] = " U yyy ", - [Dw2] = " UU yy ", - [Dw3] = " UUU y ", - [Rw] = " yyyx U xxxy x ", - [Rw2] = " yyyx UU xxxy xx ", - [Rw3] = " yyyx UUU xxxy xxx ", - [Lw] = " yx U xxxyyy xxx ", - [Lw2] = " yx UU xxxyyy xx ", - [Lw3] = " yx UUU xxxyyy x ", - [Fw] = " xxx U x yxxxyyy ", - [Fw2] = " xxx UU x yxxyyy ", - [Fw3] = " xxx UUU x yxyyy ", - [Bw] = " x U xxx yxyyy ", - [Bw2] = " x UU xxx yxxyyy ", - [Bw3] = " x UUU xxx yxxxyyy ", - - [M] = " yx U xx UUU yxyyy ", - [M2] = " yx UU xx UU xxxy ", - [M3] = " yx UUU xx U yxxxy ", - [S] = " x UUU xx U yyyx ", - [S2] = " x UU xx UU yyx ", - [S3] = " x U xx UUU yx ", - [E] = " U xx UUU xxyyy ", - [E2] = " UU xx UU xxyy ", - [E3] = " UUU xx U xxy ", - - [x] = " x ", - [x2] = " xx ", - [x3] = " xxx ", - [y] = " y ", - [y2] = " yy ", - [y3] = " yyy ", - [z] = " yyy x y ", - [z2] = " yy xx ", - [z3] = " y x yyy " -}; - - -/* Public functions **********************************************************/ - -void -apply_alg(Alg *alg, Cube *cube) -{ - Cube aux; - int i; - - copy_cube(cube, &aux); - make_solved(cube); - - for (i = 0; i < alg->len; i++) - if (alg->inv[i]) - apply_move(alg->move[i], cube); - - invert_cube(cube); - compose(&aux, cube); - - for (i = 0; i < alg->len; i++) - if (!alg->inv[i]) - apply_move(alg->move[i], cube); -} - -void -apply_move(Move m, Cube *cube) -{ - compose(&move_array[m], cube); -} - -void -apply_move_centers(Move m, Cube *cube) -{ - compose_centers(&move_array[m], cube); -} - -void -apply_move_corners(Move m, Cube *cube) -{ - compose_corners(&move_array[m], cube); -} - -void -apply_move_edges(Move m, Cube *cube) -{ - compose_edges(&move_array[m], cube); -} - -Alg * -cleanup(Alg *alg) -{ - int i, j, k, b[2], n, L; - Move bb, m; - Alg *ret; - - ret = new_alg(""); - cleanup_aux(alg, ret, false); - cleanup_aux(alg, ret, true); - - do { - for (i = 0, j = 0, n = 0; i < ret->len; i = j) { - if (ret->move[i] > B3) { - ret->move[n] = ret->move[i]; - ret->inv[n] = ret->inv[i]; - n++; - j++; - continue; - } - - bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6; - while (j < ret->len && - ret->move[j] <= B3 && - ret->inv[j] == ret->inv[i] && - 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb) - j++; - - for (k = i, b[0] = 0, b[1] = 0; k < j; k++) { - m = ret->move[k]; - if (base_move(m) == bb) - b[0] = (b[0]+1+m-base_move(m)) % 4; - else - b[1] = (b[1]+1+m-base_move(m)) % 4; - } - - for (k = 0; k < 2; k++) { - if (b[k] != 0) { - ret->move[n] = bb + b[k] - 1 + 3*k; - ret->inv[n] = ret->inv[i]; - n++; - } - } - } - - L = ret->len; - ret->len = n; - } while (L != n); - - return ret; -} - -static void -cleanup_aux(Alg *alg, Alg *ret, bool inv) -{ - int i, j; - Cube c, d; - Move m; - Alg *equiv_alg; - - make_solved(&c); - for (i = 0; i < alg->len; i++) { - if (alg->inv[i] != inv) - continue; - - equiv_alg = new_alg(equiv_alg_string[alg->move[i]]); - - for (j = 0; j < equiv_alg->len; j++) - if (equiv_alg->move[j] == U) - append_move(ret, 3 * c.xp[U_center] + 1, inv); - else - apply_move(equiv_alg->move[j], &c); - - free_alg(equiv_alg); - } - - m = NULLMOVE; - switch (c.xp[F_center]) { - case U_center: - m = x3; - break; - case D_center: - m = x; - break; - case R_center: - m = y; - break; - case L_center: - m = y3; - break; - case B_center: - if (c.xp[U_center] == U_center) - m = y2; - else - m = x2; - break; - default: - break; - } - - make_solved(&d); - apply_move(m, &d); - if (m != NULLMOVE) - append_move(ret, m, inv); - - m = NULLMOVE; - if (c.xp[U_center] == d.xp[D_center]) { - m = z2; - } else if (c.xp[U_center] == d.xp[R_center]) { - m = z3; - } else if (c.xp[U_center] == d.xp[L_center]) { - m = z; - } - if (m != NULLMOVE) - append_move(ret, m, inv); -} - -void -init_moves() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - Move m; - Alg *equiv_alg[NMOVES]; - - static const Cube mcu = { - .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR }, - .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR }, - }; - static const Cube mcx = { - .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR }, - .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 }, - .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR }, - .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2, - [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 }, - .xp = { F_center, B_center, R_center, - L_center, D_center, U_center }, - }; - static const Cube mcy = { - .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL }, - .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 }, - .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL }, - .xp = { U_center, D_center, B_center, - F_center, R_center, L_center }, - }; - - move_array[U] = mcu; - move_array[x] = mcx; - move_array[y] = mcy; - - for (m = 0; m < NMOVES; m++) - equiv_alg[m] = new_alg(equiv_alg_string[m]); - - for (m = 0; m < NMOVES; m++) { - switch (m) { - case NULLMOVE: - make_solved(&move_array[m]); - break; - case U: - case x: - case y: - break; - default: - make_solved(&move_array[m]); - apply_alg(equiv_alg[m], &move_array[m]); - break; - } - } - - for (m = 0; m < NMOVES; m++) - free_alg(equiv_alg[m]); -} - diff --git a/src/moves.h b/src/moves.h deleted file mode 100644 index 4e8be7f..0000000 --- a/src/moves.h +++ /dev/null @@ -1,17 +0,0 @@ -#ifndef MOVES_H -#define MOVES_H - -#include "alg.h" -#include "cube.h" -#include "env.h" - -void apply_alg(Alg *alg, Cube *cube); -void apply_move(Move m, Cube *cube); -void apply_move_centers(Move m, Cube *cube); -void apply_move_corners(Move m, Cube *cube); -void apply_move_edges(Move m, Cube *cube); -Alg * cleanup(Alg *alg); - -void init_moves(); - -#endif diff --git a/src/movesets.c b/src/movesets.c deleted file mode 100644 index d8f5bc1..0000000 --- a/src/movesets.c +++ /dev/null @@ -1,194 +0,0 @@ -#define MOVESETS_C - -#include "movesets.h" - -static bool allowed_HTM(Move m); -static bool allowed_URF(Move m); -static bool allowed_eofb(Move m); -static bool allowed_drud(Move m); -static bool allowed_htr(Move m); -static bool can_append_HTM(Move l2, Move l1, Move m); -static bool can_append_HTM_cached(Alg *alg, Move m, bool inverse); -static bool cancel_niss_HTM_cached(Alg *alg); -static void init_can_append_HTM(); - -Moveset -moveset_HTM = { - .name = "HTM", - .allowed = allowed_HTM, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_URF = { - .name = "URF", - .allowed = allowed_URF, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_eofb = { - .name = "eofb", - .allowed = allowed_eofb, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_drud = { - .name = "drud", - .allowed = allowed_drud, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset -moveset_htr = { - .name = "htr", - .allowed = allowed_htr, - .can_append = can_append_HTM_cached, - .cancel_niss = cancel_niss_HTM_cached, -}; - -Moveset * -all_movesets[] = { - &moveset_HTM, - &moveset_URF, - &moveset_eofb, - &moveset_drud, - &moveset_htr, - NULL -}; - -static uint64_t can_append_HTM_mask[NMOVES][NMOVES]; - -static bool -allowed_HTM(Move m) -{ - return m >= U && m <= B3; -} - -static bool -allowed_URF(Move m) -{ - Move b = base_move(m); - - return b == U || b == R || b == F; -} - -static 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); -} - -static 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); -} - -static bool -allowed_htr(Move m) -{ - Move b = base_move(m); - - return moveset_HTM.allowed(m) && m == b + 1; -} - -static bool -can_append_HTM(Move l2, Move l1, Move m) -{ - bool cancel, cancel_last, cancel_swap; - - cancel_last = l1 != NULLMOVE && base_move(l1) == base_move(m); - cancel_swap = l2 != NULLMOVE && base_move(l2) == base_move(m); - cancel = cancel_last || (commute(l1, l2) && cancel_swap); - - return !cancel; -} - -static bool -can_append_HTM_cached(Alg *alg, Move m, bool inverse) -{ - Move *moves, l1, l2; - uint64_t mbit; - int n; - - if (inverse) { - moves = alg->move_inverse; - n = alg->len_inverse; - } else { - moves = alg->move_normal; - n = alg->len_normal; - } - - l1 = n > 0 ? moves[n-1] : NULLMOVE; - l2 = n > 1 ? moves[n-2] : NULLMOVE; - - mbit = ((uint64_t)1) << m; - - return can_append_HTM_mask[l2][l1] & mbit; -} - -static bool -cancel_niss_HTM_cached(Alg *alg) -{ - Move i1, i2; - int n; - bool can_first, can_swap; - - n = alg->len_inverse; - i1 = n > 0 ? alg->move_inverse[n-1] : NULLMOVE; - i2 = n > 1 ? alg->move_inverse[n-2] : NULLMOVE; - - can_first = can_append_HTM_cached(alg, inverse_move(i1), false); - can_swap = can_append_HTM_cached(alg, inverse_move(i2), false); - - return can_first && (!commute(i1, i2) || can_swap); -} - -static void -init_can_append_HTM() -{ - Move l2, l1, m; - - for (l1 = 0; l1 < NMOVES; l1++) - for (l2 = 0; l2 < NMOVES; l2++) - for (m = 0; m < NMOVES; m++) - if (can_append_HTM(l2, l1, m)) - can_append_HTM_mask[l2][l1] - |= (((uint64_t)1) << m); -} - -void -init_moveset(Moveset *ms) -{ - int j; - Move m; - - for (j = 0, m = U; m < NMOVES; m++) - if (ms->allowed(m)) - ms->sorted_moves[j++] = m; - ms->sorted_moves[j] = NULLMOVE; - -/* TODO: should be here? maybe just init all movesets together anyway... */ - init_can_append_HTM(); -} - -void -init_movesets() -{ - int i; - - for (i = 0; all_movesets[i] != NULL; i++) - init_moveset(all_movesets[i]); -} diff --git a/src/movesets.h b/src/movesets.h deleted file mode 100644 index a02d171..0000000 --- a/src/movesets.h +++ /dev/null @@ -1,15 +0,0 @@ -#ifndef MOVESETS_H -#define MOVESETS_H - -#include "alg.h" - -void init_moveset(Moveset *); -void init_movesets(); - -extern Moveset moveset_HTM; -extern Moveset moveset_URF; -extern Moveset moveset_eofb; -extern Moveset moveset_drud; -extern Moveset moveset_htr; - -#endif diff --git a/src/pruning.c b/src/pruning.c deleted file mode 100644 index 3cc9152..0000000 --- a/src/pruning.c +++ /dev/null @@ -1,400 +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 int findchunk(PruneData *pd, int nchunks, uint64_t i); -static void genptable_bfs(PruneData *pd, int d, int nt, int nc); -static void genptable_fixnasty(PruneData *pd, int d, int nthreads); -static void * instance_bfs(void *arg); -static void * instance_fixnasty(void *arg); -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); - -PruneData *active_pd[256]; - -int -findchunk(PruneData *pd, int nchunks, uint64_t i) -{ - uint64_t chunksize; - - chunksize = pd->coord->max / (uint64_t)nchunks; - chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP); - - return MIN(nchunks-1, (int)(i / chunksize)); -} - -PruneData * -genptable(PruneData *pd, int nthreads) -{ - int d, nchunks, i, maxv; - uint64_t oldn; - - 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]; - } - - 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; - - if (nthreads < 4) { - fprintf(stderr, - "--- Warning ---\n" - "You are using only %d threads to generate the pruning" - "tables. This can take a while.\n" - "Unless you did this intentionally, you should re-run" - "this command with `-t 4' or more.\n" - "---------------\n\n", nthreads - ); - } - - nchunks = MIN(ptablesize(pd), 100000); - fprintf(stderr, "Generating pt_%s_%s with %d threads\n", - pd->coord->name, pd->moveset->name, 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); - pd->n = 1; - oldn = 0; - genptable_fixnasty(pd, 0, nthreads); - 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; - - 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 %" - 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; - } - 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_pd[i] != NULL; i++); - return active_pd[i] = pd; -} - -static void -genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks) -{ - int i; - pthread_t t[nthreads]; - ThreadDataGenpt td[nthreads]; - pthread_mutex_t *mtx[nchunks], *upmtx; - - upmtx = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(upmtx, NULL); - for (i = 0; i < nchunks; i++) { - mtx[i] = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(mtx[i], NULL); - } - - for (i = 0; i < nthreads; i++) { - td[i].thid = i; - td[i].nthreads = nthreads; - td[i].pd = pd; - td[i].d = d; - td[i].nchunks = nchunks; - td[i].mutex = mtx; - td[i].upmutex = upmtx; - pthread_create(&t[i], NULL, instance_bfs, &td[i]); - } - - for (i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(upmtx); - for (i = 0; i < nchunks; i++) - free(mtx[i]); -} - -static void -genptable_fixnasty(PruneData *pd, int d, int nthreads) -{ - int i; - pthread_t t[nthreads]; - ThreadDataGenpt td[nthreads]; - pthread_mutex_t *upmtx; - - if (pd->coord->type != SYMCOMP_COORD) - return; - - upmtx = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(upmtx, NULL); - for (i = 0; i < nthreads; i++) { - td[i].thid = i; - td[i].nthreads = nthreads; - td[i].pd = pd; - td[i].d = d; - td[i].upmutex = upmtx; - pthread_create(&t[i], NULL, instance_fixnasty, &td[i]); - } - - for (i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(upmtx); -} - -static void * -instance_bfs(void *arg) -{ - ThreadDataGenpt *td; - uint64_t i, ii, blocksize, rmin, rmax, updated; - int j, pval, ichunk, oldc, newc; - 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 ? - 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 == oldc) { - for (j = 0; ms[j] != NULLMOVE; j++) { - 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 > 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]); - } - } - } - - pthread_mutex_lock(td->upmutex); - td->pd->n += updated; - pthread_mutex_unlock(td->upmutex); - - return NULL; -} - -static void * -instance_fixnasty(void *arg) -{ - ThreadDataGenpt *td; - uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M; - int j, oldc; - Trans t; - - 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; - 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<pd->coord, t, i); - if (ptableval(td->pd, ii) > oldc) { - ptable_update(td->pd, ii, oldc); - updated++; - } - } - } - } - - pthread_mutex_lock(td->upmutex); - td->pd->n += updated; - pthread_mutex_unlock(td->upmutex); - - return NULL; -} - -void -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]); -} - -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 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 = b * (ind % e); - mask = f << sh; - i = ind / e; - - pd->ptable[i] &= ~mask; - 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; - } - - return (pd->ptable[ind/e] & (m << sh)) >> sh; -} - -static bool -read_ptable_file(PruneData *pd) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - int i; - uint64_t r; - - strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->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) -{ - init_env(); - - FILE *f; - char fname[strlen(tabledir)+256]; - int i; - uint64_t w; - - strcpy(fname, tabledir); - strcat(fname, "/pt_"); - strcat(fname, pd->coord->name); - strcat(fname, "_"); - strcat(fname, pd->moveset->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 deleted file mode 100644 index 93ae863..0000000 --- a/src/pruning.h +++ /dev/null @@ -1,16 +0,0 @@ -#ifndef PRUNING_H -#define PRUNING_H - -#include "coord.h" -#include "movesets.h" - -void free_pd(PruneData *pd); -PruneData * genptable(PruneData *data, int nthreads); -void print_ptable(PruneData *pd); -uint64_t ptablesize(PruneData *pd); -int ptableval(PruneData *pd, uint64_t ind); - -extern PruneData *active_pd[256]; - -#endif - diff --git a/src/shell.c b/src/shell.c deleted file mode 100644 index 4faa0a8..0000000 --- a/src/shell.c +++ /dev/null @@ -1,177 +0,0 @@ -#define SHELL_C - -#include "shell.h" - -static void cleanwhitespaces(char *line); -static int parseline(char *line, char **v); - -bool -checkfiles() -{ - /* TODO: add more checks (other files, use checksum...) */ - /* How to check for pruning tables with new method? */ - /* Solution: use list of steps */ - /* - char fname[strlen(tabledir)+100]; - int i; - - for (i = 0; all_pd[i] != NULL; i++) { - strcpy(fname, tabledir); - strcat(fname, "/"); - strcat(fname, all_pd[i]->filename); - if ((f = fopen(fname, "rb")) == NULL) - return false; - else - fclose(f); - } - */ - - return true; -} - -static void -cleanwhitespaces(char *line) -{ - char *i; - - for (i = line; *i != 0; i++) - if (*i == '\t' || *i == '\n') - *i = ' '; -} - -/* This function assumes that **v is large enough */ -static int -parseline(char *line, char **v) -{ - char *t; - int n = 0; - - cleanwhitespaces(line); - - for (t = strtok(line, " "); t != NULL; t = strtok(NULL, " ")) - strcpy(v[n++], t); - - return n; -} - -void -exec_args(int c, char **v) -{ - int i; - char line[MAXLINELEN]; - Command *cmd = NULL; - CommandArgs *args; - Alg *scramble; - - for (i = 0; commands[i] != NULL; i++) - if (!strcmp(v[0], commands[i]->name)) - cmd = commands[i]; - - if (cmd == NULL) { - fprintf(stderr, "%s: command not found\n", v[0]); - return; - } - - args = cmd->parse_args(c-1, &v[1]); - if (!args->success) { - fprintf(stderr, "usage: %s\n", cmd->usage); - return; - } - - if (args->scrstdin) { - while (true) { - if (fgets(line, MAXLINELEN, stdin) == NULL) { - clearerr(stdin); - break; - } - - scramble = new_alg(line); - - printf(">>> Line: %s", line); - - if (scramble != NULL && scramble->len > 0) { - args->scramble = scramble; - cmd->exec(args); - free_alg(scramble); - args->scramble = NULL; - } - } - } else { - cmd->exec(args); - } - free_args(args); -} - -void -launch(bool batchmode) -{ - int i, shell_argc; - char line[MAXLINELEN], **shell_argv; - - shell_argv = malloc(MAXNTOKENS * sizeof(char *)); - for (i = 0; i < MAXNTOKENS; i++) - shell_argv[i] = malloc((MAXTOKENLEN+1) * sizeof(char)); - - if (!batchmode) { - fprintf(stderr, "Welcome to Nissy "VERSION".\n" - "Type \"commands\" for a list of commands.\n"); - } - - while (true) { - if (!batchmode) { - fprintf(stdout, "nissy-# "); - } - - if (fgets(line, MAXLINELEN, stdin) == NULL) - break; - - if (batchmode) { - printf(">>>\n" - ">>> Executing command: %s" - ">>>\n", line); - } - - shell_argc = parseline(line, shell_argv); - - if (shell_argc > 0) - exec_args(shell_argc, shell_argv); - } - - for (i = 0; i < MAXNTOKENS; i++) - free(shell_argv[i]); - free(shell_argv); -} - -#ifndef TEST -int -main(int argc, char *argv[]) -{ - char *closing_cmd[1] = { "freemem" }; - - init_env(); - init_trans(); - - if (!checkfiles()) { - fprintf(stderr, - "--- Warning ---\n" - "Some pruning tables are missing or unreadable\n" - "You can generate them with `nissy gen'.\n" - "---------------\n\n" - ); - } - - if (argc > 1) { - if (!strcmp(argv[1], "-b")) { - launch(true); - } else { - exec_args(argc-1, &argv[1]); - } - } else { - launch(false); - } - - exec_args(1, closing_cmd); - - return 0; -} -#endif diff --git a/src/shell.h b/src/shell.h deleted file mode 100644 index 7e4f785..0000000 --- a/src/shell.h +++ /dev/null @@ -1,14 +0,0 @@ -#ifndef SHELL_H -#define SHELL_H - -#include "commands.h" - -#define MAXLINELEN 10000 -#define MAXTOKENLEN 255 -#define MAXNTOKENS 255 - -bool checkfiles(); -void exec_args(int c, char **v); -void launch(bool batchmode); - -#endif diff --git a/src/solve.c b/src/solve.c deleted file mode 100644 index 2d0c94d..0000000 --- a/src/solve.c +++ /dev/null @@ -1,122 +0,0 @@ -#define SOLVE_C - -#include "solve.h" - -void -dfs(DfsArg *arg, Solver *solver, Threader *threader) -{ - int i; - DfsArg newarg; - Alg *sol; - Move m; - - if (arg->current_alg->len > arg->d) - return; - - if (solver->is_solved(solver->param, arg->cubedata)) { -/* TODO: the "all" option should be re-implemented as setting -validate to null */ - -/* TODO: we also have to check if cancel with NISS; -we can't because we have no access to the s->final field -this should be done by the step's validator? */ - sol = solver->validate_solution(solver->param,arg->current_alg); - bool accepted = sol != NULL; - bool too_short = arg->current_alg->len != arg->d; - - if (accepted && !too_short) { -/* TODO: arg->t got lost in refactoring */ -/* transform_alg(inverse_trans(arg->t), sol);*/ - if (arg->opts->verbose) - print_alg(sol, false); - threader->append_sol(sol, arg->threaddata); - } - return; - } - - if (arg->current_alg->len == arg->d) - return; - -/* TODO: do not alloc */ - newarg.cubedata = solver->alloc_cubedata(solver->param); - for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { - m = solver->moveset->sorted_moves[i]; - if (solver->moveset->can_append(arg->current_alg, m, arg->niss) - && compare_last(arg->current_alg, m, arg->niss) >= 0) { - append_move(arg->current_alg, m, arg->niss); - - solver->copy_cubedata( - solver->param, arg->cubedata, newarg.cubedata); - newarg.threaddata = arg->threaddata; - newarg.opts = arg->opts; - newarg.d = arg->d; - newarg.niss = arg->niss; - newarg.current_alg = arg->current_alg; - if (!solver->move_check_stop( - solver->param, &newarg, threader)) - dfs(&newarg, solver, threader); - - remove_last_move(arg->current_alg); - } - } - solver->free_cubedata(solver->param, newarg.cubedata); - - if (arg->opts->can_niss && !arg->niss && - solver->niss_makes_sense( - solver->param, arg->cubedata, arg->current_alg)) { - solver->invert_cube(solver->param, arg->cubedata); - arg->niss = true; - dfs(arg, solver, threader); - } -} - -AlgList * -solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader) -{ - int i, d, optimal; - bool ready[MAX_SOLVERS], stop, one_ready; - DfsArg arg[MAX_SOLVERS]; - AlgList *sols; - - one_ready = false; - for (i = 0; solver[i] != NULL; i++) { - arg[i].cubedata = - solver[i]->prepare_cube(solver[i]->param, cube); - arg[i].opts = opts; - ready[i] = arg[i].cubedata != NULL; - one_ready = one_ready || ready[i]; - } - - sols = new_alglist(); - if (!one_ready) { - fprintf(stderr, "Cube not ready for solving\n"); - return sols; - } - - optimal = opts->max_moves; - stop = false; - for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) { - if (opts->verbose) - fprintf(stderr, "Searching depth %d\n", d); - - for (i = 0; solver[i] != NULL && !stop; i++) { - if (!ready[i]) - continue; - - arg[i].d = d; - threader->dispatch(&arg[i], sols, solver[i], threader); - - if (sols->len > 0) - optimal = MIN(optimal, d); - - stop = sols->len >= opts->max_solutions; - } - stop = stop || - (opts->optimal != -1 && d >= opts->optimal + optimal); - } - -/* TODO: some cleanup (free cubedata) */ -/* TODO: actually, preparation should be done somewhere else */ - - return sols; -} diff --git a/src/solve.h b/src/solve.h deleted file mode 100644 index 8182887..0000000 --- a/src/solve.h +++ /dev/null @@ -1,54 +0,0 @@ -#ifndef SOLVE_H -#define SOLVE_H - -#include "moves.h" - -#define MAX_SOLVERS 99 - -typedef struct dfsarg DfsArg; -typedef struct threader Threader; -typedef struct solver Solver; - -/* TODO: add solver and threader in DfsData, remove from dispatch args and similar */ - -struct dfsarg { - void * cubedata; - void * threaddata; - SolveOptions * opts; - int d; - bool niss; - Alg * current_alg; -}; - -struct threader { - void (*append_sol)(Alg *, void *); - void (*dispatch)(DfsArg *, AlgList *, Solver *, Threader *); - int (*get_nsol)(void *); -/* TODO: threader should have param, like solver? */ -}; - -struct solver { - Moveset * moveset; - bool (*move_check_stop)(void *, DfsArg *, Threader *); - Alg * (*validate_solution)(void *, Alg *); - bool (*niss_makes_sense)(void *, void *, Alg *); -/* TODO: move param to somewhere where it makes more sense */ - void * param; -/* TODO: the following should be part of a generic cube description */ -/* TODO: remove alloc? */ -/* TODO: revisit apply_move, maybe apply_alg? or both? */ - void * (*alloc_cubedata)(void *); - void (*copy_cubedata)(void *, void *, void *); - void (*free_cubedata)(void *, void *); - void (*invert_cube)(void *, void *); - bool (*is_solved)(void *, void *); - void (*apply_move)(void *, void *, Move); -/* TODO: remove dependence on Cube, preparation should be done before */ - void * (*prepare_cube)(void *, Cube *); -}; - -void dfs(DfsArg *, Solver *, Threader *); -/* TODO: remove dependence on Cube, preparation should be done before */ -AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *); - -#endif diff --git a/src/solver_step.c b/src/solver_step.c deleted file mode 100644 index 52fa347..0000000 --- a/src/solver_step.c +++ /dev/null @@ -1,306 +0,0 @@ -#include "solver_step.h" - -typedef struct { - Cube * cube; - uint64_t * val; - Trans * t; -} CubeData; - -static void apply_move_cubedata(void *, void *, Move); -static void init_indexes(Step *, CubeData *); -static void * prepare_cube(void *, Cube *); -static bool move_check_stop_eager(void *, DfsArg *, Threader *); -static bool move_check_stop_lazy(void *, DfsArg *, Threader *); -static bool move_check_stop_nonsol(void *, DfsArg *, Threader *); -static bool is_solved_step(void *, void *); -static Alg * validate_solution(void *, Alg *); -static void * alloc_cubedata(void *); -static void copy_cubedata(void *, void *, void *); -static void free_cubedata(void *, void *); -static void invert_cubedata(void *, void *); -static bool niss_makes_sense(void *, void *, Alg *); -static Solver * new_stepsolver_nocheckstop(Step *step); - -static void -apply_move_cubedata(void *param, void *cubedata, Move m) -{ - Step *s = (Step *)param; - CubeData *data = (CubeData *)cubedata; - - Trans tt; - for (int i = 0; i < s->n_coord; i++) { - Move mm = transform_move(data->t[i], m); - data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); - data->t[i] = transform_trans(tt, data->t[i]); - } -} - -static void -init_indexes(Step *step, CubeData *data) -{ - int i; - Cube moved; - Trans t, tt; - - for (i = 0; i < step->n_coord; i++) { - t = step->coord_trans[i]; - copy_cube(data->cube, &moved); - apply_trans(t, &moved); - data->val[i] = index_coord(step->coord[i], &moved, &tt); - data->t[i] = transform_trans(tt, t); - } -} - -static void * -prepare_cube(void *param, Cube *cube) -{ - int i; - Step *s; - CubeData *data; - - s = (Step *)param; - - for (i = 0; i < s->n_coord; i++) { - s->pd[i] = malloc(sizeof(PruneData)); - s->pd[i]->moveset = s->moveset; -/* TODO: check if moveset initialization works fine, - e.g. if there is a variable to save the initialized status - or if it gets initialized multiple times */ - init_moveset(s->moveset); - s->pd[i]->coord = s->coord[i]; - gen_coord(s->coord[i]); - s->pd[i]->compact = s->pd_compact[i]; - s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */ - } - - data = alloc_cubedata(param); - data->cube = malloc(sizeof(Cube)); - copy_cube(cube, data->cube); - init_indexes(s, data); - - return data; -} - -static bool -move_check_stop_eager(void *param, DfsArg *arg, Threader *threader) -{ - int nsol; - - if (move_check_stop_nonsol(param, arg, threader)) - return true; - - nsol = threader->get_nsol(arg->threaddata); - return nsol >= arg->opts->max_solutions; -} - -static bool -move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader) -{ - int nsol; - - nsol = threader->get_nsol(arg->threaddata); - if (nsol >= arg->opts->max_solutions) - return true; - - return move_check_stop_nonsol(param, arg, threader); -} - -/* TODO: split in 2 (nissable / non-nissable) and only move cube - when nissable */ -static bool -move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader) -{ - int i, goal, bound; - Move mm, lastmove; - Trans tt = uf; - CubeData *data; - Step *s; - - s = (Step *)param; - data = (CubeData *)arg->cubedata; - - - bound = 0; - goal = arg->d - arg->current_alg->len; -/* TODO: check if len is 0 */ - lastmove = arg->current_alg->move[arg->current_alg->len-1]; - for (i = 0; i < s->n_coord; i++) { - mm = transform_move(data->t[i], lastmove); - data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt); - data->t[i] = transform_trans(tt, data->t[i]); - - bound = MAX(bound, ptableval(s->pd[i], data->val[i])); - if (arg->opts->can_niss && !arg->niss) - bound = MIN(1, bound); - - if (bound > goal) { - return true; - } - } - if (arg->opts->can_niss && !arg->niss) - apply_move(lastmove, data->cube); - - return false; -} - -static bool -is_solved_step(void *param, void *cubedata) -{ - int i; - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - for (i = 0; i < s->n_coord; i++) - if (data->val[i] != 0) - return false; - - return true; -} - -static Alg * -validate_solution(void *param, Alg *alg) -{ - return ((Step *)param)->is_valid(alg); -} - -static void * -alloc_cubedata(void *param) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - - data = malloc(sizeof(CubeData)); - /* We do not need to allocate a cube */ - data->val = malloc(s->n_coord * sizeof(uint64_t)); - data->t = malloc(s->n_coord * sizeof(Trans)); - - return data; -} - -static void -copy_cubedata(void *param, void *src, void *dst) -{ - int i; - Step *s; - CubeData *newdata, *olddata; - - s = (Step *)param; - olddata = (CubeData *)src; - newdata = (CubeData *)dst; - -/* TODO: do not copy if not nissable */ - newdata->cube = malloc(sizeof(Cube)); - copy_cube(olddata->cube, newdata->cube); - for (i = 0; i < s->n_coord; i++) { - newdata->val[i] = olddata->val[i]; - newdata->t[i] = olddata->t[i]; - } -} - -static void -free_cubedata(void *param, void *cubedata) -{ - CubeData *data; - - data = (CubeData *)cubedata; - - free(data->t); - free(data->val); - free(data->cube); - free(data); -} - -static void -invert_cubedata(void *param, void *cubedata) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - invert_cube(data->cube); - init_indexes(s, data); -} - -static bool -niss_makes_sense(void *param, void *cubedata, Alg *alg) -{ - Step *s; - CubeData *data; - - s = (Step *)param; - data = (CubeData *)cubedata; - - if (s->final) - return false; - - if (alg->len_normal == 0) - return true; - - Move m = inverse_move(alg->move_normal[alg->len_normal-1]); - for (int i = 0; i < s->n_coord; i++) { - Move mm = transform_move(data->t[i], m); - uint64_t u = move_coord(s->coord[i], mm, 0, NULL); - if (ptableval(s->pd[i], u) > 0) - return true; - } - - return false; -} - -static Solver * -new_stepsolver_nocheckstop(Step *step) -{ - Solver *solver; - - solver = malloc(sizeof(Solver)); - - solver->moveset = step->moveset; - solver->param = step; - - solver->apply_move = apply_move_cubedata; - solver->prepare_cube = prepare_cube; - solver->is_solved = is_solved_step; - solver->validate_solution = validate_solution; - solver->alloc_cubedata = alloc_cubedata; - solver->copy_cubedata = copy_cubedata; - solver->free_cubedata = free_cubedata; - solver->invert_cube = invert_cubedata; - solver->niss_makes_sense = niss_makes_sense; - - return solver; -} - -Solver * -new_stepsolver_eager(Step *step) -{ - Solver *solver; - - solver = new_stepsolver_nocheckstop(step); - solver->move_check_stop = move_check_stop_eager; - - return solver; -} - -Solver * -new_stepsolver_lazy(Step *step) -{ - Solver *solver; - - solver = new_stepsolver_nocheckstop(step); - solver->move_check_stop = move_check_stop_lazy; - - return solver; -} - -void -free_stepsolver(Solver *solver) -{ - free(solver); -} diff --git a/src/solver_step.h b/src/solver_step.h deleted file mode 100644 index f68d077..0000000 --- a/src/solver_step.h +++ /dev/null @@ -1,12 +0,0 @@ -#ifndef SOLVER_STEP_H -#define SOLVER_STEP_H - -#include "cube.h" -#include "solve.h" -#include "steps.h" - -Solver *new_stepsolver_eager(Step *); -Solver *new_stepsolver_lazy(Step *); -void free_stepsolver(Solver *); - -#endif diff --git a/src/steps.c b/src/steps.c deleted file mode 100644 index cdba763..0000000 --- a/src/steps.c +++ /dev/null @@ -1,177 +0,0 @@ -#define STEPS_C - -#include "steps.h" - -/* TODO: change all checkers to use coordinates! */ - -bool -check_centers(Cube *cube) -{ - int i; - - for (i = 0; i < 6; i++) - if (cube->xp[i] != i) - return false; - - return true; -} - -bool -check_coud_HTM(Cube *cube) -{ - int i; - - for (i = 0; i < 8; i++) - if (cube->co[i] != 0) - return false; - - return true; -} - -bool -check_coud_URF(Cube *cube) -{ - Cube c2, c3; - - copy_cube(cube, &c2); - copy_cube(cube, &c3); - - apply_move(z, &c2); - apply_move(x, &c3); - - return check_coud_HTM(cube) || - check_coud_HTM(&c2) || - check_coud_HTM(&c3); -} - -bool -check_cp_HTM(Cube *cube) -{ - int i; - - for (i = 0; i < 8; i++) - if (cube->cp[i] != i) - return false; - - return true; -} - -bool -check_corners_HTM(Cube *cube) -{ - return check_coud_HTM(cube) && check_cp_HTM(cube); -} - -bool -check_corners_URF(Cube *cube) -{ - Cube c; - Trans i; - - for (i = 0; i < NROTATIONS; i++) { - copy_cube(cube, &c); - apply_alg(rotation_alg(i), &c); - if (check_corners_HTM(&c)) - return true; - } - - return false; -} - -bool -check_cornershtr(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_eofb(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_drud(Cube *cube) -{ - /* TODO (use coord) */ - return true; -} - -bool -check_htr(Cube *cube) -{ - /* TODO (check_drud(cube) and coord_htr_drud == 0) */ - return true; -} - -Alg * -validate_singlecw_ending(Alg *alg) -{ - int i; - bool nor, inv; - Alg *ret; - 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)); - - if (nor && inv) { - ret = new_alg(""); - copy_alg(alg, ret); - } else { - ret = NULL; - } - - return ret; -} - -/* Public functions **********************************************************/ - -/* -void -compute_ind(Step *s, Cube *cube, Movable *ind) -{ - int i; - Cube mvd; - Trans t, tt; - - for (i = 0; i < s->n_coord; i++) { - t = s->coord_trans[i]; - copy_cube(cube, &mvd); - apply_trans(t, &mvd); - - ind[i].val = index_coord(s->coord[i], &mvd, &tt); - ind[i].t = transform_trans(tt, t); - } -} -*/ - -void -prepare_cs(ChoiceStep *cs, SolveOptions *opts) -{ - int i, j; - Step *s; - - for (i = 0; cs->step[i] != NULL; i++) { - s = cs->step[i]; - for (j = 0; j < s->n_coord; j++) { - 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/src/steps.h b/src/steps.h deleted file mode 100644 index 206f8b4..0000000 --- a/src/steps.h +++ /dev/null @@ -1,244 +0,0 @@ -#ifndef STEPS_H -#define STEPS_H - -#include "pruning.h" -#include "movesets.h" - -bool check_centers(Cube *cube); -bool check_coud_HTM(Cube *cube); -bool check_coud_URF(Cube *cube); -bool check_cp_HTM(Cube *cube); -bool check_corners_HTM(Cube *cube); -bool check_corners_URF(Cube *cube); -bool check_cornershtr(Cube *cube); -bool check_eofb(Cube *cube); -bool check_drud(Cube *cube); -bool check_htr(Cube *cube); -/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/ -void prepare_cs(ChoiceStep *cs, SolveOptions *opts); -bool always_valid(Alg *alg); -Alg * validate_singlecw_ending(Alg *alg); - -#ifndef STEPS_C - -extern char check_centers_msg[100]; -extern char check_eo_msg[100]; -extern char check_dr_msg[100]; -extern char check_htr_msg[100]; -extern char check_drany_msg[100]; - -extern Step step_eofb_HTM; -extern Step step_drud_HTM; -extern Step step_drfin_drud; - -extern ChoiceStep optimal_HTM; -extern ChoiceStep eoany_HTM; -extern ChoiceStep eofb_HTM; -extern ChoiceStep eorl_HTM; -extern ChoiceStep eoud_HTM; -extern ChoiceStep drany_HTM; -extern ChoiceStep drud_HTM; -extern ChoiceStep drrl_HTM; -extern ChoiceStep drfb_HTM; -extern ChoiceStep dranyfin_DR; -extern ChoiceStep drudfin_drud; -extern ChoiceStep drrlfin_drrl; -extern ChoiceStep drfbfin_drfb; - -extern ChoiceStep *csteps[]; - -#else - -char check_centers_msg[100] = "cube must be oriented (centers solved)"; -char check_eo_msg[100] = "EO must be solved on given axis"; -char check_dr_msg[100] = "DR must be solved on given axis"; -char check_htr_msg[100] = "HTR must be solved"; -char check_drany_msg[100] = "DR must be solved on at least one axis"; - -/* Optimal after EO ******************/ -/* TODO: eofin_eo (generic), eofbfin_eofb, eorlfin_eorl, eoudfin_eoud */ - -/* EO steps **************************/ -/* TODO: eoany_HTM (generic), eofb_HTM, eorl_HTM, eoud_HTM */ - -Step -step_eofb_HTM = { - .ready = check_centers, - .final = false, - .moveset = &moveset_HTM, - .n_coord = 1, - .coord = {&coord_eofb}, - .coord_trans = {uf}, - .is_valid = validate_singlecw_ending, -}; -ChoiceStep -eoany_HTM = { - .shortname = "eo", - .name = "EO on any axis", - .step = {&step_eofb_HTM, &step_eofb_HTM, &step_eofb_HTM, NULL}, - .t = {uf, ur, fd}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eofb_HTM = { - .shortname = "eofb", - .name = "EO on F/B", - .step = {&step_eofb_HTM, NULL}, - .t = {uf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eorl_HTM = { - .shortname = "eorl", - .name = "EO on R/L", - .step = {&step_eofb_HTM, NULL}, - .t = {ur}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -eoud_HTM = { - .shortname = "eoud", - .name = "EO on U/D", - .step = {&step_eofb_HTM, NULL}, - .t = {fd}, - .ready_msg = check_centers_msg, -}; - -/* CO steps **************************/ -/* TODO: coany_HTM (generic), cofb_HTM, corl_HTM, coud_HTM */ -/* TODO: coany_URF (generic), cofb_URF, corl_URF, coud_URF */ - -/* Misc corner steps *****************/ -/* TODO: cornershtr_HTM, cornershtr_URF, corners_HTM, corners_URF */ -/* TODO (new): corners_drud */ - -/* DR steps **************************/ -/* TODO: dr_eo (generic) */ -/* TODO: dr_eofb (generic), dr_eorl (generic), dr_eoud (generic) */ -/* TODO: drud_eofb, drrl_eofb, drud_eorl, drfb_eorl, drrl_eoud, drfb_eoud */ - -Step -step_drud_HTM = { - .ready = check_centers, - .final = false, - .moveset = &moveset_HTM, - .n_coord = 1, - .coord = {&coord_drud_sym16}, - .coord_trans = {uf}, - .is_valid = validate_singlecw_ending, -}; -ChoiceStep -drany_HTM = { - .shortname = "dr", - .name = "DR on any axis", - .step = {&step_drud_HTM, &step_drud_HTM, &step_drud_HTM, NULL}, - .t = {uf, rf, fd}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drud_HTM = { - .shortname = "drud", - .name = "DR on U/D", - .step = {&step_drud_HTM, NULL}, - .t = {uf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drrl_HTM = { - .shortname = "drrl", - .name = "DR on R/L", - .step = {&step_drud_HTM, NULL}, - .t = {rf}, - .ready_msg = check_centers_msg, -}; -ChoiceStep -drfb_HTM = { - .shortname = "drfb", - .name = "DR on F/B", - .step = {&step_drud_HTM, NULL}, - .t = {fd}, - .ready_msg = check_centers_msg, -}; - -/* DR finish steps */ -Step -step_drfin_drud = { - .ready = check_drud, - .final = true, - .moveset = &moveset_drud, - .n_coord = 1, - .coord = {&coord_drudfin_noE_sym16}, /* TODO: maybe no noE */ - .coord_trans = {uf}, - .is_valid = NULL, -}; -ChoiceStep -dranyfin_DR = { - .shortname = "drfin", - .name = "DR finish on any axis without breaking DR", - .step = {&step_drfin_drud, &step_drfin_drud, - &step_drfin_drud, NULL}, - .t = {uf, rf, fd}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drudfin_drud = { - .shortname = "drudfin", - .name = "DR finis on U/D without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {uf}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drrlfin_drrl = { - .shortname = "drrlfin", - .name = "DR finish on R/L without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {rf}, - .ready_msg = check_dr_msg, -}; -ChoiceStep -drfbfin_drfb = { - .shortname = "drfbfin", - .name = "DR finish on F/B without breaking DR", - .step = {&step_drfin_drud, NULL}, - .t = {fd}, - .ready_msg = check_dr_msg, -}; - -/* HTR from DR */ -/* TODO: htr_any (generic), htr_drud, htr_drrl, htr_drfb */ - -/* HTR finish */ -/* TODO: htrfin_htr */ - -ChoiceStep *csteps[] = { -/* TODO: re-implement optimal - &optimal_HTM, -*/ - - &eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM, - &drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM, - &dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb, - -NULL -/* TODO: - &optimal_light_HTM, - - &eofin_eo, &eofbfin_eofb, &eorlfin_eorl, &eoudfin_eoud, - &coany_HTM, &coud_HTM, &corl_HTM, &cofb_HTM, - &coany_URF, &coud_URF, &corl_URF, &cofb_URF, - &dr_eo, &dr_eofb, &dr_eorl, &dr_eoud, - &drud_eofb, &drrl_eofb, - &drud_eorl, &drfb_eorl, - &drfb_eoud, &drrl_eoud, - &htr_any, &htr_drud, &htr_drrl, &htr_drfb, - &htrfin_htr, - &cornershtr_HTM, &cornershtr_URF, &corners_HTM, &corners_URF, - NULL -*/ - -}; - -#endif - -#endif diff --git a/src/threader_eager.c b/src/threader_eager.c deleted file mode 100644 index 261b995..0000000 --- a/src/threader_eager.c +++ /dev/null @@ -1,163 +0,0 @@ -#include -#include "threader_eager.h" - -typedef struct { - AlgList * sols; - pthread_mutex_t * sols_mutex; -} ThreadData; - -typedef struct { - DfsArg * arg; - Solver * solver; - Threader * threader; - AlgList * starts; - AlgListNode ** node; - pthread_mutex_t * start_mutex; -} ThreadInitData; - -static void append_sol(Alg *, void *); -static void * instance_thread(void *); -static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); -static AlgList * possible_starts(DfsArg *, Solver *); -static int get_nsol(void *); - -Threader threader_eager = { - .append_sol = append_sol, - .dispatch = dispatch, - .get_nsol = get_nsol, -}; - -static void -append_sol(Alg *alg, void *threaddata) -{ - ThreadData *td = (ThreadData *)threaddata; - - pthread_mutex_lock(td->sols_mutex); - append_alg(td->sols, alg); - pthread_mutex_unlock(td->sols_mutex); -} - -static AlgList * -possible_starts(DfsArg *arg, Solver *solver) -{ - AlgList *ret = new_alglist(); - - if (solver->is_solved(solver->param, arg->cubedata)) { - if (arg->opts->min_moves == 0 && arg->d == 0) - append_sol(new_alg(""), arg->threaddata); - return ret; - } - - for (int i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) { - Move m = solver->moveset->sorted_moves[i]; - Alg *alg = new_alg(""); - append_move(alg, m, false); - append_alg(ret, alg); - free_alg(alg); - -/* TODO: check if step not final */ - if (arg->opts->can_niss) { - alg = new_alg(""); - append_move(alg, m, true); - append_alg(ret, alg); - free_alg(alg); - } - } - - return ret; -} - -static void * -instance_thread(void *arg) -{ - ThreadInitData *tid = (ThreadInitData *)arg; - - while (true) { - pthread_mutex_lock(tid->start_mutex); - AlgListNode *node = *(tid->node); - if (node == NULL) { - pthread_mutex_unlock(tid->start_mutex); - break; - } - *(tid->node) = (*(tid->node))->next; - pthread_mutex_unlock(tid->start_mutex); - -/* TODO: adjust for longer (arbitrarily long?) starting sequences */ - void *data = tid->solver->alloc_cubedata(tid->solver->param); - tid->solver->copy_cubedata( - tid->solver->param, tid->arg->cubedata, data); - bool inv = node->alg->inv[node->alg->len-1]; - if (inv) - tid->solver->invert_cube( - tid->solver->param, data); - tid->solver->apply_move( - tid->solver->param, data, node->alg->move[0]); - - DfsArg newarg; - newarg.cubedata = data; - newarg.threaddata = tid->arg->threaddata; - newarg.opts = tid->arg->opts; - newarg.d = tid->arg->d; - newarg.niss = inv; - newarg.current_alg = new_alg(""); - copy_alg(node->alg, newarg.current_alg); - - dfs(&newarg, tid->solver, tid->threader); - - tid->solver->free_cubedata(tid->solver->param, data); - free_alg(newarg.current_alg); - } - - return NULL; -} - -static void -dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) -{ - int nthreads = arg->opts->nthreads; - ThreadInitData tid[nthreads]; - pthread_t t[nthreads]; - - pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(sols_mutex, NULL); - - arg->threaddata = malloc(sizeof(ThreadData)); - ThreadData *td = (ThreadData *)arg->threaddata; - td->sols = sols; - td->sols_mutex = sols_mutex; - - AlgList *starts = possible_starts(arg, solver); - AlgListNode *node = starts->first; - pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t)); - pthread_mutex_init(start_mutex, NULL); - for (int i = 0; i < nthreads; i++) { - tid[i].arg = arg; - tid[i].solver = solver; - tid[i].threader = threader; - tid[i].starts = starts; - tid[i].node = &node; - tid[i].start_mutex = start_mutex; - - pthread_create(&t[i], NULL, instance_thread, &tid[i]); - } - - for (int i = 0; i < nthreads; i++) - pthread_join(t[i], NULL); - - free(td); - free(sols_mutex); - free_alglist(starts); - free(start_mutex); -} - -static int -get_nsol(void *threaddata) -{ - ThreadData *td = (ThreadData *)threaddata; - - pthread_mutex_lock(td->sols_mutex); - int n = td->sols->len; - pthread_mutex_unlock(td->sols_mutex); - - return n; -} diff --git a/src/threader_eager.h b/src/threader_eager.h deleted file mode 100644 index e39b27f..0000000 --- a/src/threader_eager.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef THREADER_EAGER_H -#define THREADER_EAGER_H - -#include "solve.h" - -extern Threader threader_eager; - -#endif diff --git a/src/threader_single.c b/src/threader_single.c deleted file mode 100644 index 232835d..0000000 --- a/src/threader_single.c +++ /dev/null @@ -1,35 +0,0 @@ -#include "threader_single.h" - -static void append_sol(Alg *, void *); -static void dispatch(DfsArg *, AlgList *, Solver *, Threader *); -static int get_nsol(void *); - -Threader threader_single = { - .append_sol = append_sol, - .dispatch = dispatch, - .get_nsol = get_nsol, -}; - -static void -append_sol(Alg *alg, void *threaddata) -{ - append_alg((AlgList *)threaddata, alg); -} - -static void -dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader) -{ - arg->threaddata = sols; - arg->niss = false; - arg->current_alg = new_alg(""); - - dfs(arg, solver, threader); - - free_alg(arg->current_alg); -} - -static int -get_nsol(void *threaddata) -{ - return ((AlgList *)threaddata)->len; -} diff --git a/src/threader_single.h b/src/threader_single.h deleted file mode 100644 index 2c0bfab..0000000 --- a/src/threader_single.h +++ /dev/null @@ -1,8 +0,0 @@ -#ifndef THREADER_SINGLE_H -#define THREADER_SINGLE_H - -#include "solve.h" - -extern Threader threader_single; - -#endif diff --git a/src/trans.c b/src/trans.c deleted file mode 100644 index 898c2be..0000000 --- a/src/trans.c +++ /dev/null @@ -1,190 +0,0 @@ -#define TRANS_C - -#include "trans.h" - -/* Local functions ***********************************************************/ - -/* Tables and other data *****************************************************/ - -static Cube mirror_cube = { -.ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL, - [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL, - [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL }, -.cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL, - [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL }, -.xp = { [U_center] = U_center, [D_center] = D_center, - [R_center] = L_center, [L_center] = R_center, - [F_center] = F_center, [B_center] = B_center } -}; - -static char rotation_alg_string[100][NROTATIONS] = { - [uf] = "", [ur] = "y", [ub] = "y2", [ul] = "y3", - [df] = "z2", [dr] = "y z2", [db] = "x2", [dl] = "y3 z2", - [rf] = "z3", [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3", - [lf] = "z", [ld] = "z y3", [lb] = "z y2", [lu] = "z y", - [fu] = "x y2", [fr] = "x y", [fd] = "x", [fl] = "x y3", - [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3", -}; - -Alg *rotation_alg_arr[NROTATIONS]; -Move moves_ttable[NTRANS][NMOVES]; -Trans trans_ttable[NTRANS][NTRANS]; -Trans trans_itable[NTRANS]; - -/* Public functions **********************************************************/ - -void -apply_trans(Trans t, Cube *cube) -{ - Cube aux; - Alg *inv; - int i; - - inv = inverse_alg(rotation_alg(t % NROTATIONS)); - copy_cube(cube, &aux); - make_solved(cube); - - if (t >= NROTATIONS) - compose(&mirror_cube, cube); - apply_alg(inv, cube); - compose(&aux, cube); - apply_alg(rotation_alg(t % NROTATIONS), cube); - if (t >= NROTATIONS) { - compose(&mirror_cube, cube); - for (i = 0; i < 8; i++) - cube->co[i] = (3 - cube->co[i]) % 3; - } - - free_alg(inv); -} - -/* -Trans -inverse_trans(Trans t) -{ - static Trans inverse_trans_aux[NTRANS] = { - [uf] = uf, [ur] = ul, [ul] = ur, [ub] = ub, - [df] = df, [dr] = dr, [dl] = dl, [db] = db, - [rf] = lf, [rd] = bl, [rb] = rb, [ru] = fr, - [lf] = rf, [ld] = br, [lb] = lb, [lu] = fl, - [fu] = fu, [fr] = ru, [fd] = bu, [fl] = lu, - [bu] = fd, [br] = ld, [bd] = bd, [bl] = rd, - - [uf_mirror] = uf_mirror, [ur_mirror] = ur_mirror, - [ul_mirror] = ul_mirror, [ub_mirror] = ub_mirror, - [df_mirror] = df_mirror, [dr_mirror] = dl_mirror, - [dl_mirror] = dr_mirror, [db_mirror] = db_mirror, - [rf_mirror] = rf_mirror, [rd_mirror] = br_mirror, - [rb_mirror] = lb_mirror, [ru_mirror] = fl_mirror, - [lf_mirror] = lf_mirror, [ld_mirror] = bl_mirror, - [lb_mirror] = rb_mirror, [lu_mirror] = fr_mirror, - [fu_mirror] = fu_mirror, [fr_mirror] = lu_mirror, - [fd_mirror] = bu_mirror, [fl_mirror] = ru_mirror, - [bu_mirror] = fd_mirror, [br_mirror] = rd_mirror, - [bd_mirror] = bd_mirror, [bl_mirror] = ld_mirror - }; - - return inverse_trans_aux[t]; -} -*/ - -Trans -inverse_trans(Trans t) -{ - return trans_itable[t]; -} - -Alg * -rotation_alg(Trans i) -{ - return rotation_alg_arr[i % NROTATIONS]; -} - -void -transform_alg(Trans t, Alg *alg) -{ - int i; - - for (i = 0; i < alg->len; i++) - alg->move[i] = transform_move(t, alg->move[i]); -} - -Move -transform_move(Trans t, Move m) -{ - return moves_ttable[t][m]; -} - -Trans -transform_trans(Trans t, Trans m) -{ - return trans_ttable[t][m]; -} - -void -init_trans() { - static bool initialized = false; - if (initialized) - return; - initialized = true; - - int i; - Alg *nonsym_alg, *nonsym_inv; - Cube aux, cube; - Move mi, move; - Trans t, u, v; - - init_moves(); - - for (i = 0; i < NROTATIONS; i++) - rotation_alg_arr[i] = new_alg(rotation_alg_string[i]); - - for (t = 0; t < NTRANS; t++) { - for (mi = 0; mi < NMOVES; mi++) { - make_solved(&aux); - apply_move(mi, &aux); - apply_trans(t, &aux); - for (move = 0; move < NMOVES; move++) { - copy_cube(&aux, &cube); - apply_move(inverse_move(move), &cube); - if (is_solved(&cube)) { - moves_ttable[t][mi] = move; - break; - } - } - } - } - - nonsym_alg = new_alg("R' U' F"); - nonsym_inv = inverse_alg(nonsym_alg); - - for (t = 0; t < NTRANS; t++) { - for (u = 0; u < NTRANS; u++) { - make_solved(&aux); - apply_alg(nonsym_alg, &aux); - apply_trans(u, &aux); - apply_trans(t, &aux); - for (v = 0; v < NTRANS; v++) { - copy_cube(&aux, &cube); - apply_trans(v, &cube); - apply_alg(nonsym_inv, &cube); - if (is_solved(&cube)) { - /* This is the inverse of the correct - value, it will be inverted later */ - trans_ttable[t][u] = v; - if (v == uf) - trans_itable[t] = u; - break; - } - } - } - } - for (t = 0; t < NTRANS; t++) - for (u = 0; u < NTRANS; u++) - trans_ttable[t][u] = trans_itable[trans_ttable[t][u]]; - - - free_alg(nonsym_alg); - free_alg(nonsym_inv); -} - diff --git a/src/trans.h b/src/trans.h deleted file mode 100644 index 0cc8cef..0000000 --- a/src/trans.h +++ /dev/null @@ -1,32 +0,0 @@ -#ifndef TRANS_H -#define TRANS_H - -#include "moves.h" - -void apply_trans(Trans t, Cube *cube); -Trans inverse_trans(Trans t); -Alg * rotation_alg(Trans i); -void transform_alg(Trans t, Alg *alg); -Move transform_move(Trans t, Move m); -Trans transform_trans(Trans t, Trans m); - -void init_trans(); - -#ifndef TRANS_C - -extern TransGroup tgrp_udfix; - -#else - -TransGroup -tgrp_udfix = { - .n = 16, - .t = { uf, ur, ub, ul, - df, dr, db, dl, - uf_mirror, ur_mirror, ub_mirror, ul_mirror, - df_mirror, dr_mirror, db_mirror, dl_mirror }, -}; - -#endif - -#endif diff --git a/src/utils.c b/src/utils.c deleted file mode 100644 index cbf951e..0000000 --- a/src/utils.c +++ /dev/null @@ -1,290 +0,0 @@ -#define UTILS_C - -#include "utils.h" - -void -apply_permutation(int *perm, int *set, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - - if (!is_perm(perm, n)) - return; - - for (i = 0; i < n; i++) - aux[i] = set[perm[i]]; - - memcpy(set, aux, n * sizeof(int)); - free(aux); -} - -int -binomial(int n, int k) -{ - if (n < 0 || k < 0 || k > n) - return 0; - - return factorial(n) / (factorial(k) * factorial(n-k)); -} - -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; -} - -int -factorial(int n) -{ - int i, ret = 1; - - if (n < 0) - return 0; - - for (i = 1; i <= n; i++) - ret *= i; - - 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); -} - -void -index_to_subset(int s, int n, int k, int *r) -{ - int i, j, v; - - if (s < 0 || s >= binomial(n, k)) { - for (i = 0; i < n; i++) - r[i] = -1; - return; - } - - 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; - } - } -} - -void -int_to_digit_array(int a, int b, int n, int *r) -{ - int i; - - if (b <= 1) - for (i = 0; i < n; i++) - r[i] = 0; - else - 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; - - if (b <= 1) { - for (i = 0; i < n; i++) - a[i] = 0; - } else { - 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 -invert_digits(int a, int b, int n) -{ - int i, ret, *r = malloc(n * sizeof(int)); - - int_to_digit_array(a, b, n, r); - for (i = 0; i < n; i++) - r[i] = (b-r[i]) % b; - - ret = digit_array_to_int(r, n, b); - free(r); - return ret; -} - -bool -is_perm(int *a, int n) -{ - int *aux = malloc(n * sizeof(int)); - int i; - bool ret = true; - - for (i = 0; i < n; i++) - aux[i] = 0; - - for (i = 0; i < n; i++) { - if (a[i] < 0 || a[i] >= n) - ret = false; - else - aux[a[i]] = 1; - } - - for (i = 0; i < n; i++) - if (!aux[i]) - ret = false; - - free(aux); - return ret; -} - -bool -is_subset(int *a, int n, int k) -{ - int i, sum = 0; - - for (i = 0; i < n; i++) - sum += a[i] ? 1 : 0; - - return sum == k; -} - -int -perm_sign(int *a, int n) -{ - int i, j, ret = 0; - - if (!is_perm(a, n)) - return -1; - - for (i = 0; i < n; i++) - for (j = i+1; j < n; j++) - ret += (a[i] > a[j]) ? 1 : 0; - - return ret % 2; -} - -int -perm_to_index(int *a, int n) -{ - int i, j, c, ret = 0; - - if (!is_perm(a, n)) - return factorial(n); - - 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; -} - -int -powint(int a, int b) -{ - if (b < 0) - return 0; - if (b == 0) - return 1; - - if (b % 2) - return a * powint(a, b-1); - else - return powint(a*a, b/2); -} - -int -subset_to_index(int *a, int n, int k) -{ - int i, ret = 0; - - if (!is_subset(a, n, k)) - return binomial(n, k); - - 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 -sum_arrays_mod(int *src, int *dst, int n, int m) -{ - int i; - - for (i = 0; i < n; i++) - dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m; -} - -void -swap(int *a, int *b) -{ - int aux; - - aux = *a; - *a = *b; - *b = aux; -} - -void -swapu64(uint64_t *a, uint64_t *b) -{ - uint64_t aux; - - aux = *a; - *a = *b; - *b = aux; -} - diff --git a/src/utils.h b/src/utils.h deleted file mode 100644 index 9ba228d..0000000 --- a/src/utils.h +++ /dev/null @@ -1,43 +0,0 @@ -#ifndef UTILS_H -#define UTILS_H - -#include -#include -#include -#include - -#define POW2TO6 64ULL -#define POW2TO11 2048ULL -#define POW2TO12 4096ULL -#define POW3TO7 2187ULL -#define POW3TO8 6561ULL -#define FACTORIAL4 24ULL -#define FACTORIAL6 720ULL -#define FACTORIAL7 5040ULL -#define FACTORIAL8 40320ULL -#define FACTORIAL12 479001600ULL -#define BINOM12ON4 495ULL -#define BINOM8ON4 70ULL -#define MIN(a,b) (((a) < (b)) ? (a) : (b)) -#define MAX(a,b) (((a) > (b)) ? (a) : (b)) - -void apply_permutation(int *perm, int *set, int n); -int binomial(int n, int k); -int digit_array_to_int(int *a, int n, int b); -int factorial(int n); -void index_to_perm(int p, int n, int *r); -void index_to_subset(int s, int n, int k, int *r); -void int_to_digit_array(int a, int b, int n, int *r); -void int_to_sum_zero_array(int x, int b, int n, int *a); -int invert_digits(int a, int b, int n); -bool is_perm(int *a, int n); -bool is_subset(int *a, int n, int k); -int perm_sign(int *a, int n); -int perm_to_index(int *a, int n); -int powint(int a, int b); -int subset_to_index(int *a, int n, int k); -void sum_arrays_mod(int *src, int *dst, int n, int m); -void swap(int *a, int *b); -void swapu64(uint64_t *a, uint64_t *b); - -#endif -- cgit v1.3