aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/alg.c459
-rw-r--r--src/alg.h35
-rw-r--r--src/commands.c569
-rw-r--r--src/commands.h211
-rw-r--r--src/coord.c654
-rw-r--r--src/coord.h259
-rw-r--r--src/cube.c270
-rw-r--r--src/cube.h35
-rw-r--r--src/cubetypes.h360
-rw-r--r--src/env.c60
-rw-r--r--src/env.h15
-rw-r--r--src/fst.c401
-rw-r--r--src/fst.h13
-rw-r--r--src/moves.c301
-rw-r--r--src/moves.h17
-rw-r--r--src/movesets.c194
-rw-r--r--src/movesets.h15
-rw-r--r--src/pruning.c400
-rw-r--r--src/pruning.h16
-rw-r--r--src/shell.c177
-rw-r--r--src/shell.h14
-rw-r--r--src/solve.c122
-rw-r--r--src/solve.h54
-rw-r--r--src/solver_step.c306
-rw-r--r--src/solver_step.h12
-rw-r--r--src/steps.c177
-rw-r--r--src/steps.h244
-rw-r--r--src/threader_eager.c163
-rw-r--r--src/threader_eager.h8
-rw-r--r--src/threader_single.c35
-rw-r--r--src/threader_single.h8
-rw-r--r--src/trans.c190
-rw-r--r--src/trans.h32
-rw-r--r--src/utils.c290
-rw-r--r--src/utils.h43
35 files changed, 0 insertions, 6159 deletions
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 @@
1#define ALG_C
2
3#include "alg.h"
4
5static int axis(Move m);
6static void free_alglistnode(AlgListNode *aln);
7static void realloc_alg(Alg *alg, int n);
8
9void
10append_alg(AlgList *l, Alg *alg)
11{
12 AlgListNode *node = malloc(sizeof(AlgListNode));
13 int i;
14
15 node->alg = new_alg("");
16 for (i = 0; i < alg->len; i++)
17 append_move(node->alg, alg->move[i], alg->inv[i]);
18 node->next = NULL;
19
20 if (++l->len == 1)
21 l->first = node;
22 else
23 l->last->next = node;
24 l->last = node;
25}
26
27void
28append_move(Alg *alg, Move m, bool inverse)
29{
30 if (alg->len == alg->allocated)
31 realloc_alg(alg, 2*alg->len);
32
33 alg->move[alg->len] = m;
34 alg->inv [alg->len] = inverse;
35 alg->len++;
36
37 if (inverse)
38 alg->move_inverse[alg->len_inverse++] = m;
39 else
40 alg->move_normal[alg->len_normal++] = m;
41}
42
43static int
44axis(Move m)
45{
46 static int aux[] = {
47 [NULLMOVE] = 0,
48
49 [U] = 1, [U2] = 1, [U3] = 1,
50 [D] = 1, [D2] = 1, [D3] = 1,
51 [Uw] = 1, [Uw2] = 1, [Uw3] = 1,
52 [Dw] = 1, [Dw2] = 1, [Dw3] = 1,
53 [E] = 1, [E2] = 1, [E3] = 1,
54 [y] = 1, [y2] = 1, [y3] = 1,
55
56 [R] = 2, [R2] = 2, [R3] = 2,
57 [L] = 2, [L2] = 2, [L3] = 2,
58 [Rw] = 2, [Rw2] = 2, [Rw3] = 2,
59 [Lw] = 2, [Lw2] = 2, [Lw3] = 2,
60 [M] = 2, [M2] = 2, [M3] = 2,
61 [x] = 2, [x2] = 2, [x3] = 2,
62
63 [F] = 3, [F2] = 3, [F3] = 3,
64 [B] = 3, [B2] = 3, [B3] = 3,
65 [Fw] = 3, [Fw2] = 3, [Fw3] = 3,
66 [Bw] = 3, [Bw2] = 3, [Bw3] = 3,
67 [S] = 3, [S2] = 3, [S3] = 3,
68 [z] = 3, [z2] = 3, [z3] = 3,
69 };
70
71 return aux[m];
72}
73
74Move
75base_move(Move m)
76{
77 if (m == NULLMOVE)
78 return NULLMOVE;
79 else
80 return m - (m-1)%3;
81}
82
83bool
84commute(Move m1, Move m2)
85{
86 return axis(m1) == axis(m2);
87}
88
89int
90compare(Move m1, Move m2)
91{
92 if (!commute(m1, m2))
93 return 0;
94
95 return m1 < m2 ? 1 : -1;
96}
97
98int
99compare_last(Alg *alg, Move m, bool inverse)
100{
101 Move last;
102 int n;
103
104 if (inverse) {
105 n = alg->len_inverse;
106 last = n > 0 ? alg->move_inverse[n-1] : NULLMOVE;
107 } else {
108 n = alg->len_normal;
109 last = n > 0 ? alg->move_normal[n-1] : NULLMOVE;
110 }
111
112 return compare(last, m);
113}
114
115void
116compose_alg(Alg *alg1, Alg *alg2)
117{
118 int i;
119
120 for (i = 0; i < alg2->len; i++)
121 append_move(alg1, alg2->move[i], alg2->inv[i]);
122}
123
124void
125copy_alg(Alg *src, Alg *dst)
126{
127 dst->len = dst->len_normal = dst->len_inverse = 0;
128 compose_alg(dst, src);
129}
130
131void
132free_alg(Alg *alg)
133{
134 free(alg->move);
135 free(alg->inv);
136 free(alg);
137}
138
139void
140free_alglist(AlgList *l)
141{
142 AlgListNode *aux, *i = l->first;
143
144 while (i != NULL) {
145 aux = i->next;
146 free_alglistnode(i);
147 i = aux;
148 }
149 free(l);
150}
151
152static void
153free_alglistnode(AlgListNode *aln)
154{
155 free_alg(aln->alg);
156 free(aln);
157}
158
159Alg *
160inverse_alg(Alg *alg)
161{
162 Alg *ret = new_alg("");
163 int i;
164
165 for (i = alg->len-1; i >= 0; i--)
166 append_move(ret, inverse_move(alg->move[i]), alg->inv[i]);
167
168 return ret;
169}
170
171Move
172inverse_move(Move m)
173{
174 return m == NULLMOVE ? NULLMOVE : m + 2 - 2*((m-1) % 3);
175}
176
177char *
178move_string(Move m)
179{
180 static char move_string_aux[NMOVES][7] = {
181 [NULLMOVE] = "-",
182 [U] = "U", [U2] = "U2", [U3] = "U\'",
183 [D] = "D", [D2] = "D2", [D3] = "D\'",
184 [R] = "R", [R2] = "R2", [R3] = "R\'",
185 [L] = "L", [L2] = "L2", [L3] = "L\'",
186 [F] = "F", [F2] = "F2", [F3] = "F\'",
187 [B] = "B", [B2] = "B2", [B3] = "B\'",
188 [Uw] = "Uw", [Uw2] = "Uw2", [Uw3] = "Uw\'",
189 [Dw] = "Dw", [Dw2] = "Dw2", [Dw3] = "Dw\'",
190 [Rw] = "Rw", [Rw2] = "Rw2", [Rw3] = "Rw\'",
191 [Lw] = "Lw", [Lw2] = "Lw2", [Lw3] = "Lw\'",
192 [Fw] = "Fw", [Fw2] = "Fw2", [Fw3] = "Fw\'",
193 [Bw] = "Bw", [Bw2] = "Bw2", [Bw3] = "Bw\'",
194 [M] = "M", [M2] = "M2", [M3] = "M\'",
195 [E] = "E", [E2] = "E2", [E3] = "E\'",
196 [S] = "S", [S2] = "S2", [S3] = "S\'",
197 [x] = "x", [x2] = "x2", [x3] = "x\'",
198 [y] = "y", [y2] = "y2", [y3] = "y\'",
199 [z] = "z", [z2] = "z2", [z3] = "z\'",
200 };
201
202 return move_string_aux[m];
203}
204
205Alg *
206new_alg(char *str)
207{
208 Alg *alg;
209 int i;
210 bool niss, move_read;
211 Move j, m;
212
213 alg = malloc(sizeof(Alg));
214 alg->allocated = 30;
215 alg->move = malloc(alg->allocated * sizeof(Move));
216 alg->inv = malloc(alg->allocated * sizeof(bool));
217 alg->move_normal = malloc(alg->allocated * sizeof(Move));
218 alg->move_inverse = malloc(alg->allocated * sizeof(Move));
219 alg->len = 0;
220 alg->len_normal = 0;
221 alg->len_inverse = 0;
222
223 niss = false;
224 for (i = 0; str[i]; i++) {
225 if (str[i] == ' ' || str[i] == '\t' || str[i] == '\n')
226 continue;
227
228 if (str[i] == '(' && niss) {
229 fprintf(stderr, "Error reading moves: nested ( )\n");
230 alg->len = alg->len_normal = alg->len_inverse = 0;
231 return alg;
232 }
233
234 if (str[i] == ')' && !niss) {
235 fprintf(stderr, "Error reading moves: unmatched )\n");
236 alg->len = alg->len_normal = alg->len_inverse = 0;
237 return alg;
238 }
239
240 if (str[i] == '(' || str[i] == ')') {
241 niss = !niss;
242 continue;
243 }
244
245 /* Single slash for comments */
246 if (str[i] == '/') {
247 while (str[i] && str[i] != '\n')
248 i++;
249
250 if (!str[i])
251 i--;
252
253 continue;
254 }
255
256 move_read = false;
257 for (j = U; j < NMOVES; j++) {
258 if (str[i] == move_string(j)[0] ||
259 (str[i] >= 'a' && str[i] <= 'z' &&
260 str[i] == move_string(j)[0]-('A'-'a') && j<=B)) {
261 m = j;
262 if (str[i] >= 'a' && str[i] <= 'z' && j<=B) {
263 m += Uw - U;
264 }
265 if (m <= B && str[i+1]=='w') {
266 m += Uw - U;
267 i++;
268 }
269 if (str[i+1]=='2') {
270 m += 1;
271 i++;
272 } else if (str[i+1] == '\'' ||
273 str[i+1] == '3' ||
274 str[i+1] == '`' ) {
275 m += 2;
276 i++;
277 } else if ((int)str[i+1] == -62 &&
278 (int)str[i+2] == -76) {
279 /* Weird apostrophe */
280 m += 2;
281 i += 2;
282 } else if ((int)str[i+1] == -30 &&
283 (int)str[i+2] == -128 &&
284 (int)str[i+3] == -103) {
285 /* MacOS apostrophe */
286 m += 2;
287 i += 3;
288 }
289 append_move(alg, m, niss);
290 move_read = true;
291 break;
292 }
293 }
294
295 if (!move_read) {
296 free(alg);
297 return new_alg("");
298 }
299 }
300
301 if (niss) {
302 fprintf(stderr, "Error reading moves: unmatched (\n");
303 alg->len = alg->len_normal = alg->len_inverse = 0;
304 }
305
306 return alg;
307}
308
309AlgList *
310new_alglist()
311{
312 AlgList *ret = malloc(sizeof(AlgList));
313
314 ret->len = 0;
315 ret->first = NULL;
316 ret->last = NULL;
317
318 return ret;
319}
320
321Alg *
322on_inverse(Alg *alg)
323{
324 Alg *ret = new_alg("");
325 int i;
326
327 for (i = 0; i < alg->len; i++)
328 append_move(ret, alg->move[i], !alg->inv[i]);
329
330 return ret;
331}
332
333void
334print_alg(Alg *alg, bool l)
335{
336 char fill[4];
337 int i;
338 bool niss = false;
339
340 for (i = 0; i < alg->len; i++) {
341 if (!niss && alg->inv[i])
342 strcpy(fill, i == 0 ? "(" : " (");
343 if (niss && !alg->inv[i])
344 strcpy(fill, ") ");
345 if (niss == alg->inv[i])
346 strcpy(fill, i == 0 ? "" : " ");
347
348 printf("%s%s", fill, move_string(alg->move[i]));
349 niss = alg->inv[i];
350 }
351
352 if (niss)
353 printf(")");
354 if (l)
355 printf(" (%d)", alg->len);
356
357 printf("\n");
358}
359
360void
361print_alglist(AlgList *al, bool l)
362{
363 AlgListNode *i;
364
365 for (i = al->first; i != NULL; i = i->next)
366 print_alg(i->alg, l);
367}
368
369static void
370realloc_alg(Alg *alg, int n)
371{
372 if (alg == NULL) {
373 fprintf(stderr, "Error: trying to reallocate NULL alg.\n");
374 return;
375 }
376
377 if (n < alg->len) {
378 fprintf(stderr, "Error: alg too long for reallocation ");
379 fprintf(stderr, "(%d vs %d)\n", alg->len, n);
380 return;
381 }
382
383 if (n > 1000000) {
384 fprintf(stderr, "Warning: very long alg,");
385 fprintf(stderr, "something might go wrong.\n");
386 }
387
388 alg->move = realloc(alg->move, n * sizeof(int));
389 alg->inv = realloc(alg->inv, n * sizeof(int));
390 alg->move_normal = realloc(alg->move_normal, n * sizeof(int));
391 alg->move_inverse = realloc(alg->move_inverse, n * sizeof(int));
392 alg->allocated = n;
393}
394
395void
396remove_last_move(Alg *a)
397{
398 a->len--;
399
400 if (a->inv[a->len])
401 a->len_inverse--;
402 else
403 a->len_normal--;
404}
405
406void
407swapmove(Move *m1, Move *m2)
408{
409 Move aux;
410
411 aux = *m1;
412 *m1 = *m2;
413 *m2 = aux;
414}
415
416char *
417trans_string(Trans t)
418{
419 static char trans_string_aux[NTRANS][20] = {
420 [uf] = "uf", [ur] = "ur", [ub] = "ub", [ul] = "ul",
421 [df] = "df", [dr] = "dr", [db] = "db", [dl] = "dl",
422 [rf] = "rf", [rd] = "rd", [rb] = "rb", [ru] = "ru",
423 [lf] = "lf", [ld] = "ld", [lb] = "lb", [lu] = "lu",
424 [fu] = "fu", [fr] = "fr", [fd] = "fd", [fl] = "fl",
425 [bu] = "bu", [br] = "br", [bd] = "bd", [bl] = "bl",
426
427 [uf_mirror] = "uf*", [ur_mirror] = "ur*",
428 [ub_mirror] = "ub*", [ul_mirror] = "ul*",
429 [df_mirror] = "df*", [dr_mirror] = "dr*",
430 [db_mirror] = "db*", [dl_mirror] = "dl*",
431 [rf_mirror] = "rf*", [rd_mirror] = "rd*",
432 [rb_mirror] = "rb*", [ru_mirror] = "ru*",
433 [lf_mirror] = "lf*", [ld_mirror] = "ld*",
434 [lb_mirror] = "lb*", [lu_mirror] = "lu*",
435 [fu_mirror] = "fu*", [fr_mirror] = "fr*",
436 [fd_mirror] = "fd*", [fl_mirror] = "fl*",
437 [bu_mirror] = "bu*", [br_mirror] = "br*",
438 [bd_mirror] = "bd*", [bl_mirror] = "bl*",
439 };
440
441 return trans_string_aux[t];
442}
443
444Alg *
445unniss(Alg *alg)
446{
447 int i;
448 Alg *ret;
449
450 ret = new_alg("");
451
452 for (i = 0; i < alg->len_normal; i++)
453 append_move(ret, alg->move_normal[i], false);
454
455 for (i = 0; i < alg->len_inverse; i++)
456 append_move(ret, inverse_move(alg->move_inverse[i]), false);
457
458 return ret;
459}
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 @@
1#ifndef ALG_H
2#define ALG_H
3
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7
8#include "cubetypes.h"
9#include "utils.h"
10
11void append_alg(AlgList *l, Alg *alg);
12void append_move(Alg *alg, Move m, bool inverse);
13Move base_move(Move m);
14int compare(Move m1, Move m2); /* Return 1 (m1<m2), 0 or -1 (m1>m2) */
15int compare_last(Alg *alg, Move m, bool inverse);
16void compose_alg(Alg *alg1, Alg *alg2);
17bool commute(Move m1, Move m2);
18void copy_alg(Alg *src, Alg *dst);
19void free_alg(Alg *alg);
20void free_alglist(AlgList *l);
21Alg * inverse_alg(Alg *alg);
22Move inverse_move(Move m);
23char * move_string(Move m);
24Alg * new_alg(char *str);
25AlgList * new_alglist();
26Alg * on_inverse(Alg *alg);
27void print_alg(Alg *alg, bool l);
28void print_alglist(AlgList *al, bool l);
29void remove_last_move(Alg *alg);
30void swapmove(Move *m1, Move *m2);
31char * trans_string(Trans t); /* Here because similar to move_string, move? */
32Alg * unniss(Alg *alg);
33
34#endif
35
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 @@
1#define COMMANDS_C
2
3#include "commands.h"
4
5static bool read_cs(CommandArgs *args, char *str);
6static bool read_scrtype(CommandArgs *args, char *str);
7static bool read_scramble(int c, char **v, CommandArgs *args);
8
9/* Arg parsing functions implementation **************************************/
10
11CommandArgs *
12solve_parse_args(int c, char **v)
13{
14 int i;
15 bool infinitesols, fixedmsols;
16 long val;
17
18 CommandArgs *a = new_args();
19
20 a->opts->min_moves = 0;
21 a->opts->max_moves = 20;
22 a->opts->max_solutions = 1;
23 a->opts->nthreads = 1;
24 a->opts->optimal = -1;
25 a->opts->can_niss = false;
26 a->opts->verbose = false;
27 a->opts->all = false;
28 a->opts->print_number = true;
29 a->opts->count_only = false;
30
31 fixedmsols = false;
32 infinitesols = false;
33
34 for (i = 0; i < c; i++) {
35 if (!strcmp(v[i], "-m") && i+1 < c) {
36 val = strtol(v[++i], NULL, 10);
37 if (val < 0 || val > 100) {
38 fprintf(stderr,
39 "Invalid min number of moves"
40 "(0 <= N <= 100).\n");
41 return a;
42 }
43 a->opts->min_moves = val;
44 } else if (!strcmp(v[i], "-M") && i+1 < c) {
45 val = strtol(v[++i], NULL, 10);
46 if (val < 0 || val > 100) {
47 fprintf(stderr,
48 "Invalid max number of moves"
49 "(0 <= N <= 100).\n");
50 return a;
51 }
52 a->opts->max_moves = val;
53 infinitesols = true;
54 } else if (!strcmp(v[i], "-t") && i+1 < c) {
55 val = strtol(v[++i], NULL, 10);
56 if (val < 1 || val > 64) {
57 fprintf(stderr,
58 "Invalid number of threads."
59 "1 <= t <= 64\n");
60 return a;
61 }
62 a->opts->nthreads = val;
63 } else if (!strcmp(v[i], "-n") && i+1 < c) {
64 val = strtol(v[++i], NULL, 10);
65 if (val < 1 || val > 1000000) {
66 fprintf(stderr,
67 "Invalid number of solutions.\n");
68 return a;
69 }
70 a->opts->max_solutions = val;
71 fixedmsols = true;
72 } else if (!strcmp(v[i], "-o")) {
73 a->opts->optimal = 0;
74 infinitesols = true;
75 } else if (!strcmp(v[i], "-O") && i+1 < c) {
76 val = strtol(v[++i], NULL, 10);
77 if (val < 0 || val > 100 ||
78 (val == 0 && strcmp("0", v[i]))) {
79 fprintf(stderr,
80 "Invalid max number of moves"
81 " (0 <= N <= 100).\n");
82 return a;
83 }
84 a->opts->optimal = val;
85 infinitesols = true;
86 } else if (!strcmp(v[i], "-N")) {
87 a->opts->can_niss = true;
88 } else if (!strcmp(v[i], "-i")) {
89 a->scrstdin = true;
90 } else if (!strcmp(v[i], "-v")) {
91 a->opts->verbose = true;
92 } else if (!strcmp(v[i], "-a")) {
93 a->opts->all = true;
94 } else if (!strcmp(v[i], "-p")) {
95 a->opts->print_number = false;
96 } else if (!strcmp(v[i], "-c")) {
97 a->opts->count_only = true;
98 } else if (!read_cs(a, v[i])) {
99 break;
100 }
101 }
102
103 if (infinitesols && !fixedmsols)
104 a->opts->max_solutions = 1000000; /* 1M = +infty */
105
106 a->success = (a->scrstdin && i == c) || read_scramble(c-i, &v[i], a);
107 return a;
108}
109
110CommandArgs *
111scramble_parse_args(int c, char **v)
112{
113 int i;
114 long val;
115
116 CommandArgs *a = new_args();
117
118 a->success = true;
119 a->n = 1;
120
121 for (i = 0; i < c; i++) {
122 if (!strcmp(v[i], "-n") && i+1 < c) {
123 val = strtol(v[++i], NULL, 10);
124 if (val < 1 || val > 1000000) {
125 fprintf(stderr,
126 "Invalid number of scrambles.\n");
127 a->success = false;
128 return a;
129 }
130 a->n = val;
131 } else if (!read_scrtype(a, v[i])) {
132 a->success = false;
133 return a;
134 }
135 }
136
137 return a;
138}
139
140CommandArgs *
141gen_parse_args(int c, char **v)
142{
143 int val;
144 CommandArgs *a = new_args();
145
146 a->opts->nthreads = 64;
147 a->success = false;
148
149 if (c == 0) {
150 a->success = true;
151 } else {
152 if (!strcmp(v[0], "-t") && c > 1) {
153 val = strtol(v[1], NULL, 10);
154 if (val < 1 || val > 64) {
155 fprintf(stderr,
156 "Invalid number of threads."
157 "1 <= t <= 64\n");
158 return a;
159 }
160 a->opts->nthreads = val;
161 a->success = true;
162 }
163 }
164
165 return a;
166}
167
168CommandArgs *
169help_parse_args(int c, char **v)
170{
171 int i;
172 CommandArgs *a = new_args();
173
174 if (c == 1) {
175 for (i = 0; commands[i] != NULL; i++)
176 if (!strcmp(v[0], commands[i]->name))
177 a->command = commands[i];
178 if (a->command == NULL)
179 fprintf(stderr, "%s: command not found\n", v[0]);
180 }
181
182 a->success = c == 0 || (c == 1 && a->command != NULL);
183 return a;
184}
185
186CommandArgs *
187parse_only_scramble(int c, char **v)
188{
189 CommandArgs *a = new_args();
190
191 if (!strcmp(v[0], "-i")) {
192 a->scrstdin = true;
193 a->success = c == 1;
194 } else {
195 a->success = read_scramble(c, v, a);
196 }
197
198 return a;
199}
200
201CommandArgs *
202parse_no_arg(int c, char **v)
203{
204 CommandArgs *a = new_args();
205
206 a->success = true;
207
208 return a;
209}
210
211/* Exec functions implementation *********************************************/
212
213void
214solve_exec(CommandArgs *args)
215{
216 Cube c;
217 AlgList *sols;
218 Solver *solver[99];
219 Threader *threader;
220
221 make_solved(&c);
222 apply_alg(args->scramble, &c);
223/* TODO: adjust */
224/* threader = &threader_single;*/
225 threader = &threader_eager;
226
227/* TODO: adjust */
228 int i;
229 for (i = 0; args->cs->step[i] != NULL; i++)
230 solver[i] = new_stepsolver_lazy(args->cs->step[i]);
231 solver[i] = NULL;
232 sols = solve(&c, args->opts, solver, threader);
233
234 if (args->opts->count_only)
235 printf("%d\n", sols->len);
236 else
237 print_alglist(sols, args->opts->print_number);
238
239 free_alglist(sols);
240}
241
242void
243scramble_exec(CommandArgs *args)
244{
245 Cube cube;
246 Alg *scr, *ruf, *aux;
247 int i, j, eo, ep, co, cp;
248 uint64_t ui, uj, uk;
249
250 srand(time(NULL));
251
252 for (i = 0; i < args->n; i++) {
253
254 if (!strcmp(args->scrtype, "dr")) {
255 ui = rand() % FACTORIAL8;
256 uj = rand() % FACTORIAL8;
257 uk = rand() % FACTORIAL4;
258
259 make_solved(&cube);
260 index_to_perm(ui, 8, cube.cp);
261 index_to_perm(uj, 8, cube.ep);
262 index_to_perm(uk, 4, cube.ep + 8);
263 for (j = 8; j < 12; j++)
264 cube.ep[j] += 8;
265 } else if (!strcmp(args->scrtype, "htr")) {
266 make_solved(&cube);
267 /* TODO */
268 } else {
269 ep = rand() % FACTORIAL12;
270 cp = rand() % FACTORIAL8;
271 eo = rand() % POW2TO11;
272 co = rand() % POW3TO7;
273
274 if (!strcmp(args->scrtype, "eo")) {
275 eo = 0;
276 } else if (!strcmp(args->scrtype, "corners")) {
277 eo = 0;
278 ep = 0;
279 } else if (!strcmp(args->scrtype, "edges")) {
280 co = 0;
281 cp = 0;
282 }
283
284 make_solved(&cube);
285 index_to_perm(ep, 12, cube.ep);
286 index_to_perm(cp, 8, cube.cp);
287 int_to_sum_zero_array(eo, 2, 12, cube.eo);
288 int_to_sum_zero_array(co, 3, 8, cube.co);
289 }
290
291 if (!is_admissible(&cube)) {
292 if (!strcmp(args->scrtype, "corners"))
293 swap(&cube.cp[UFR], &cube.cp[UFL]);
294 else
295 swap(&cube.ep[UF], &cube.ep[UB]);
296 }
297
298 /* TODO: can be optimized for htr and dr using htrfin, drfin */
299 /*
300 TODO: solve_2phase was removed
301 scr = solve_2phase(&cube, 1);
302 */
303
304 if (!strcmp(args->scrtype, "fmc")) {
305 aux = new_alg("");
306 copy_alg(scr, aux);
307 /* Trick to rufify for free: rotate the scramble *
308 * so that it does not start with F or end with R */
309 for (j = 0; j < NROTATIONS; j++) {
310 if (base_move(scr->move[0]) != F &&
311 base_move(scr->move[0]) != B &&
312 base_move(scr->move[scr->len-1]) != R &&
313 base_move(scr->move[scr->len-1]) != L)
314 break;
315 copy_alg(aux, scr);
316 transform_alg(j, scr);
317 }
318 copy_alg(scr, aux);
319 ruf = new_alg("R' U' F");
320 copy_alg(ruf, scr);
321 compose_alg(scr, aux);
322 compose_alg(scr, ruf);
323 free_alg(aux);
324 free_alg(ruf);
325 }
326 print_alg(scr, false);
327 free_alg(scr);
328 }
329}
330
331void
332gen_exec(CommandArgs *args)
333{
334/* TODO:
335 int i;
336
337 fprintf(stderr, "Generating coordinates...\n");
338 fprintf(stderr, "Generating pruning tables...\n");
339 for (i = 0; all_pd[i] != NULL; i++)
340 genptable(all_pd[i], args->opts->nthreads);
341*/
342
343 fprintf(stderr, "Done!\n");
344}
345
346void
347invert_exec(CommandArgs *args)
348{
349 Alg *inv;
350
351 inv = inverse_alg(args->scramble);
352 print_alg(inv, false);
353
354 free_alg(inv);
355}
356
357void
358steps_exec(CommandArgs *args)
359{
360 int i;
361
362 for (i = 0; csteps[i] != NULL; i++)
363 printf("%-15s %s\n", csteps[i]->shortname, csteps[i]->name);
364}
365
366void
367commands_exec(CommandArgs *args)
368{
369 int i;
370
371 for (i = 0; commands[i] != NULL; i++)
372 printf("%s\n", commands[i]->usage);
373
374}
375
376void
377freemem_exec(CommandArgs *args)
378{
379/* TODO:
380 int i;
381
382 for (i = 0; all_pd[i] != NULL; i++)
383 free_pd(all_pd[i]);
384
385 for (i = 0; all_sd[i] != NULL; i++)
386 free_sd(all_sd[i]);
387*/
388}
389
390void
391print_exec(CommandArgs *args)
392{
393 Cube c;
394
395 make_solved(&c);
396 apply_alg(args->scramble, &c);
397 print_cube(&c);
398}
399
400/*
401void
402twophase_exec(CommandArgs *args)
403{
404 Cube c;
405 Alg *sol;
406
407 make_solved(&c);
408 apply_alg(args->scramble, &c);
409 sol = solve_2phase(&c, 1);
410
411 print_alg(sol, false);
412 free_alg(sol);
413}
414*/
415
416void
417help_exec(CommandArgs *args)
418{
419 if (args->command == NULL) {
420 printf(
421 "Use the nissy command \"help COMMAND\" for a short "
422 "description of a specific command.\n"
423 "Use the nissy command \"commands\" for a list of "
424 "available commands.\n"
425 "See the manual page for more details. The manual"
426 " page is available with \"man nissy\" on a UNIX"
427 " system (such as Linux or MacOS) or in pdf and html"
428 " format in the docs folder.\n"
429 "Nissy is available for free at "
430 "https://nissy.tronto.net\n"
431 );
432 } else {
433 printf("Command %s: %s\nusage: %s\n", args->command->name,
434 args->command->description, args->command->usage);
435 }
436}
437
438void
439quit_exec(CommandArgs *args)
440{
441 exit(0);
442}
443
444void
445cleanup_exec(CommandArgs *args)
446{
447 Alg *alg;
448
449 alg = cleanup(args->scramble);
450 print_alg(alg, false);
451
452 free_alg(alg);
453}
454
455void
456unniss_exec(CommandArgs *args)
457{
458 Alg *aux;
459
460 aux = unniss(args->scramble);
461 print_alg(aux, false);
462 free(aux);
463}
464
465void
466version_exec(CommandArgs *args)
467{
468 printf(VERSION"\n");
469}
470
471/* Local functions implementation ********************************************/
472
473static bool
474read_scramble(int c, char **v, CommandArgs *args)
475{
476 int i, k, n;
477 unsigned int j;
478 char *algstr;
479
480 if (c < 1) {
481 fprintf(stderr, "Error: no scramble given?\n");
482 return false;
483 }
484
485 for(n = 0, i = 0; i < c; i++)
486 n += strlen(v[i]);
487
488 algstr = malloc((n + 1) * sizeof(char));
489 k = 0;
490 for (i = 0; i < c; i++)
491 for (j = 0; j < strlen(v[i]); j++)
492 algstr[k++] = v[i][j];
493 algstr[k] = 0;
494
495 args->scramble = new_alg(algstr);
496 free(algstr);
497
498 if (args->scramble->len == 0)
499 fprintf(stderr, "Error reading scramble\n");
500
501 return args->scramble->len > 0;
502}
503
504static bool
505read_scrtype(CommandArgs *args, char *str)
506{
507 int i;
508 static char *scrtypes[20] =
509 { "eo", "corners", "edges", "fmc", "dr", "htr", NULL };
510
511 for (i = 0; scrtypes[i] != NULL; i++) {
512 if (!strcmp(scrtypes[i], str)) {
513 strcpy(args->scrtype, scrtypes[i]);
514 return true;
515 }
516 }
517
518 return false;
519}
520
521static bool
522read_cs(CommandArgs *args, char *str)
523{
524 int i;
525
526 for (i = 0; csteps[i] != NULL; i++) {
527 if (!strcmp(csteps[i]->shortname, str)) {
528 args->cs = csteps[i];
529 return true;
530 }
531 }
532
533 return false;
534}
535
536/* Public functions implementation *******************************************/
537
538void
539free_args(CommandArgs *args)
540{
541 if (args == NULL)
542 return;
543
544 if (args->scramble != NULL)
545 free_alg(args->scramble);
546 if (args->opts != NULL)
547 free(args->opts);
548
549 /* step and command must not be freed, they are static! */
550
551 free(args);
552}
553
554CommandArgs *
555new_args()
556{
557 CommandArgs *args = malloc(sizeof(CommandArgs));
558
559 args->success = false;
560 args->scrstdin = false;
561 args->scramble = NULL; /* initialized in read_scramble */
562 args->opts = malloc(sizeof(SolveOptions));
563
564 /* step and command are static */
565 args->cs = csteps[0]; /* default: first step in list */
566 args->command = NULL;
567
568 return args;
569}
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 @@
1#ifndef COMMANDS_H
2#define COMMANDS_H
3
4#include <time.h>
5
6#include "solve.h"
7#include "steps.h"
8#include "solver_step.h"
9#include "threader_single.h"
10#include "threader_eager.h"
11
12void free_args(CommandArgs *args);
13CommandArgs * new_args();
14
15/* Arg parsing functions *****************************************************/
16
17CommandArgs * gen_parse_args(int c, char **v);
18CommandArgs * help_parse_args(int c, char **v);
19CommandArgs * parse_only_scramble(int c, char **v);
20CommandArgs * parse_no_arg(int c, char **v);
21CommandArgs * solve_parse_args(int c, char **v);
22CommandArgs * scramble_parse_args(int c, char **v);
23
24/* Exec functions ************************************************************/
25
26void gen_exec(CommandArgs *args);
27void cleanup_exec(CommandArgs *args);
28void invert_exec(CommandArgs *args);
29void solve_exec(CommandArgs *args);
30void scramble_exec(CommandArgs *args);
31void steps_exec(CommandArgs *args);
32void commands_exec(CommandArgs *args);
33void freemem_exec(CommandArgs *args);
34void print_exec(CommandArgs *args);
35/*void twophase_exec(CommandArgs *args);*/
36void help_exec(CommandArgs *args);
37void quit_exec(CommandArgs *args);
38void unniss_exec(CommandArgs *args);
39void version_exec(CommandArgs *args);
40
41/* Commands ******************************************************************/
42
43#ifndef COMMANDS_C
44
45extern Command cleanup_cmd;
46extern Command commands_cmd;
47extern Command freemem_cmd;
48extern Command gen_cmd;
49extern Command help_cmd;
50extern Command invert_cmd;
51extern Command print_cmd;
52extern Command quit_cmd;
53extern Command scramble_cmd;
54extern Command solve_cmd;
55extern Command steps_cmd;
56extern Command unniss_cmd;
57extern Command version_cmd;
58
59extern Command *commands[];
60
61#else
62
63Command
64solve_cmd = {
65 .name = "solve",
66 .usage = "solve STEP [OPTIONS] SCRAMBLE",
67 .description = "Solve a step; see command steps for a list of steps",
68 .parse_args = solve_parse_args,
69 .exec = solve_exec
70};
71
72Command
73scramble_cmd = {
74 .name = "scramble",
75 .usage = "scramble [TYPE] [-n N]",
76 .description = "Get a random-position scramble",
77 .parse_args = scramble_parse_args,
78 .exec = scramble_exec,
79};
80
81Command
82gen_cmd = {
83 .name = "gen",
84 .usage = "gen [-t N]",
85 .description = "Generate all tables [using N threads]",
86 .parse_args = gen_parse_args,
87 .exec = gen_exec
88};
89
90Command
91invert_cmd = {
92 .name = "invert",
93 .usage = "invert SCRAMBLE]",
94 .description = "Invert a scramble",
95 .parse_args = parse_only_scramble,
96 .exec = invert_exec,
97};
98
99Command
100steps_cmd = {
101 .name = "steps",
102 .usage = "steps",
103 .description = "List available steps",
104 .parse_args = parse_no_arg,
105 .exec = steps_exec
106};
107
108Command
109commands_cmd = {
110 .name = "commands",
111 .usage = "commands",
112 .description = "List available commands",
113 .parse_args = parse_no_arg,
114 .exec = commands_exec
115};
116
117Command
118freemem_cmd = {
119 .name = "freemem",
120 .usage = "freemem",
121 .description = "free large tables from RAM",
122 .parse_args = parse_no_arg,
123 .exec = freemem_exec,
124};
125
126Command
127print_cmd = {
128 .name = "print",
129 .usage = "print SCRAMBLE",
130 .description = "Print written description of the cube",
131 .parse_args = parse_only_scramble,
132 .exec = print_exec,
133};
134
135Command
136help_cmd = {
137 .name = "help",
138 .usage = "help [COMMAND]",
139 .description = "Display nissy manual page or help on specific command",
140 .parse_args = help_parse_args,
141 .exec = help_exec,
142};
143
144/*
145Command
146twophase_cmd = {
147 .name = "twophase",
148 .usage = "twophase",
149 .description = "Find a solution quickly using a 2-phase method",
150 .parse_args = parse_only_scramble,
151 .exec = twophase_exec,
152};
153*/
154
155Command
156quit_cmd = {
157 .name = "quit",
158 .usage = "quit",
159 .description = "Quit nissy",
160 .parse_args = parse_no_arg,
161 .exec = quit_exec,
162};
163
164Command
165cleanup_cmd = {
166 .name = "cleanup",
167 .usage = "cleanup SCRAMBLE",
168 .description = "Rewrite a scramble using only standard moves (HTM)",
169 .parse_args = parse_only_scramble,
170 .exec = cleanup_exec,
171};
172
173Command
174unniss_cmd = {
175 .name = "unniss",
176 .usage = "unniss SCRAMBLE",
177 .description = "Rewrite a scramble without NISS",
178 .parse_args = parse_only_scramble,
179 .exec = unniss_exec,
180};
181
182Command
183version_cmd = {
184 .name = "version",
185 .usage = "version",
186 .description = "print nissy version",
187 .parse_args = parse_no_arg,
188 .exec = version_exec,
189};
190
191Command *commands[] = {
192 &commands_cmd,
193 &freemem_cmd,
194 &gen_cmd,
195 &help_cmd,
196 &invert_cmd,
197 &print_cmd,
198 &quit_cmd,
199 &solve_cmd,
200 &scramble_cmd,
201 &steps_cmd,
202/* &twophase_cmd,*/
203 &cleanup_cmd,
204 &unniss_cmd,
205 &version_cmd,
206 NULL
207};
208
209#endif
210
211#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 @@
1#define COORD_C
2
3#include "coord.h"
4
5static void gen_coord_comp(Coordinate *coord);
6static void gen_coord_sym(Coordinate *coord);
7static bool read_coord_mtable(Coordinate *coord);
8static bool read_coord_sd(Coordinate *coord);
9static bool read_coord_ttable(Coordinate *coord);
10static bool write_coord_mtable(Coordinate *coord);
11static bool write_coord_sd(Coordinate *coord);
12static bool write_coord_ttable(Coordinate *coord);
13
14/* Indexers ******************************************************************/
15
16uint64_t
17index_eofb(Cube *cube)
18{
19 return (uint64_t)digit_array_to_int(cube->eo, 11, 2);
20}
21
22uint64_t
23index_coud(Cube *cube)
24{
25 return (uint64_t)digit_array_to_int(cube->co, 7, 3);
26}
27
28uint64_t
29index_cp(Cube *cube)
30{
31 return (uint64_t)perm_to_index(cube->cp, 8);
32}
33
34uint64_t
35index_cpudsep(Cube *cube)
36{
37 int i, c[8];
38
39 for (i = 0; i < 8; i++)
40 c[i] = cube->cp[i] < 4 ? 0 : 1;
41
42 return (uint64_t)subset_to_index(c, 8, 4);
43}
44
45uint64_t
46index_epe(Cube *cube)
47{
48 int i, e[4];
49
50 for (i = 0; i < 4; i++)
51 e[i] = cube->ep[i+8] - 8;
52
53 return (uint64_t)perm_to_index(e, 4);
54}
55
56uint64_t
57index_epud(Cube *cube)
58{
59 return (uint64_t)perm_to_index(cube->ep, 8);
60}
61
62uint64_t
63index_epos(Cube *cube)
64{
65 int i, a[12];
66
67 for (i = 0; i < 12; i++)
68 a[i] = (cube->ep[i] < 8) ? 0 : 1;
69
70 return (uint64_t)subset_to_index(a, 12, 4);
71}
72
73uint64_t
74index_eposepe(Cube *cube)
75{
76 int i, j, e[4];
77 uint64_t epos, epe;
78
79 epos = (uint64_t)index_epos(cube);
80 for (i = 0, j = 0; i < 12; i++)
81 if (cube->ep[i] >= 8)
82 e[j++] = cube->ep[i] - 8;
83 epe = (uint64_t)perm_to_index(e, 4);
84
85 return epos * FACTORIAL4 + epe;
86}
87
88/* Inverse indexers **********************************************************/
89
90void
91invindex_eofb(uint64_t ind, Cube *cube)
92{
93 int_to_sum_zero_array(ind, 2, 12, cube->eo);
94}
95
96void
97invindex_coud(uint64_t ind, Cube *cube)
98{
99 int_to_sum_zero_array(ind, 3, 8, cube->co);
100}
101
102void
103invindex_cp(uint64_t ind, Cube *cube)
104{
105 index_to_perm(ind, 8, cube->cp);
106}
107
108void
109invindex_cpudsep(uint64_t ind, Cube *cube)
110{
111 int i, j, k, c[8];
112
113 index_to_subset(ind, 8, 4, c);
114 for (i = 0, j = 0, k = 4; i < 8; i++)
115 cube->cp[i] = c[i] == 0 ? j++ : k++;
116}
117
118
119void
120invindex_epe(uint64_t ind, Cube *cube)
121{
122 int i;
123
124 index_to_perm(ind, 4, &cube->ep[8]);
125 for (i = 0; i < 4; i++)
126 cube->ep[i+8] += 8;
127}
128
129void
130invindex_epud(uint64_t ind, Cube *cube)
131{
132 index_to_perm(ind, 8, cube->ep);
133}
134
135void
136invindex_epos(uint64_t ind, Cube *cube)
137{
138 int i, j, k;
139
140 index_to_subset(ind, 12, 4, cube->ep);
141 for (i = 0, j = 0, k = 8; i < 12; i++)
142 if (cube->ep[i] == 0)
143 cube->ep[i] = j++;
144 else
145 cube->ep[i] = k++;
146}
147
148void
149invindex_eposepe(uint64_t ind, Cube *cube)
150{
151 int i, j, k, e[4];
152 uint64_t epos, epe;
153
154 epos = ind / FACTORIAL4;
155 epe = ind % FACTORIAL4;
156
157 index_to_subset(epos, 12, 4, cube->ep);
158 index_to_perm(epe, 4, e);
159
160 for (i = 0, j = 0, k = 0; i < 12; i++)
161 if (cube->ep[i] == 0)
162 cube->ep[i] = j++;
163 else
164 cube->ep[i] = e[k++] + 8;
165}
166
167/* Other local functions *****************************************************/
168
169uint64_t
170indexers_getmax(Indexer **is)
171{
172 int i;
173 uint64_t max = 1;
174
175 for (i = 0; is[i] != NULL; i++)
176 max *= is[i]->n;
177
178 return max;
179}
180
181uint64_t
182indexers_getind(Indexer **is, Cube *c)
183{
184 int i;
185 uint64_t max = 0;
186
187 for (i = 0; is[i] != NULL; i++) {
188 max *= is[i]->n;
189 max += is[i]->index(c);
190 }
191
192 return max;
193}
194
195void
196indexers_makecube(Indexer **is, uint64_t ind, Cube *c)
197{
198 /* Warning: anti-indexers are applied in the same order as indexers. */
199 /* We assume order does not matter, but it would make more sense to */
200 /* apply them in reverse. */
201
202 int i;
203 uint64_t m;
204
205 make_solved(c);
206 m = indexers_getmax(is);
207 for (i = 0; is[i] != NULL; i++) {
208 m /= is[i]->n;
209 is[i]->to_cube(ind / m, c);
210 ind %= m;
211 }
212}
213
214static void
215gen_coord_comp(Coordinate *coord)
216{
217 uint64_t ui;
218 Cube c, mvd;
219 Move m;
220 Trans t;
221
222 coord->max = indexers_getmax(coord->i);
223
224 for (m = 0; m < NMOVES; m++)
225 coord->mtable[m] = malloc(coord->max * sizeof(uint64_t));
226
227 for (t = 0; t < NTRANS; t++)
228 coord->ttable[t] = malloc(coord->max * sizeof(uint64_t));
229
230 if (!read_coord_mtable(coord)) {
231 fprintf(stderr, "%s: generating mtable\n", coord->name);
232
233 for (ui = 0; ui < coord->max; ui++) {
234 indexers_makecube(coord->i, ui, &c);
235 for (m = 0; m < NMOVES; m++) {
236 copy_cube(&c, &mvd);
237 apply_move(m, &mvd);
238 coord->mtable[m][ui] =
239 indexers_getind(coord->i, &mvd);
240 }
241 }
242 if (!write_coord_mtable(coord))
243 fprintf(stderr, "%s: error writing mtable\n",
244 coord->name);
245
246 fprintf(stderr, "%s: mtable generated\n", coord->name);
247 }
248
249 if (!read_coord_ttable(coord)) {
250 fprintf(stderr, "%s: generating ttable\n", coord->name);
251
252 for (ui = 0; ui < coord->max; ui++) {
253 indexers_makecube(coord->i, ui, &c);
254 for (t = 0; t < NTRANS; t++) {
255 copy_cube(&c, &mvd);
256 apply_trans(t, &mvd);
257 coord->ttable[t][ui] =
258 indexers_getind(coord->i, &mvd);
259 }
260 }
261 if (!write_coord_ttable(coord))
262 fprintf(stderr, "%s: error writing ttable\n",
263 coord->name);
264 }
265}
266
267static void
268gen_coord_sym(Coordinate *coord)
269{
270 uint64_t i, in, ui, uj, uu, M, nr;
271 int j;
272 Move m;
273 Trans t;
274
275 M = coord->base[0]->max;
276 coord->selfsim = malloc(M * sizeof(uint64_t));
277 coord->symclass = malloc(M * sizeof(uint64_t));
278 coord->symrep = malloc(M * sizeof(uint64_t));
279 coord->transtorep = malloc(M * sizeof(Trans));
280
281 if (!read_coord_sd(coord)) {
282 fprintf(stderr, "%s: generating syms\n", coord->name);
283
284 for (i = 0; i < M; i++)
285 coord->symclass[i] = M+1;
286
287 for (i = 0, nr = 0; i < M; i++) {
288 if (coord->symclass[i] != M+1)
289 continue;
290
291 coord->symrep[nr] = i;
292 coord->transtorep[i] = uf;
293 coord->selfsim[nr] = (uint64_t)0;
294 for (j = 0; j < coord->tgrp->n; j++) {
295 t = coord->tgrp->t[j];
296 in = trans_coord(coord->base[0], t, i);
297 coord->symclass[in] = nr;
298 if (in == i)
299 coord->selfsim[nr] |= ((uint64_t)1<<t);
300 else
301 coord->transtorep[in] =
302 inverse_trans(t);
303 }
304 nr++;
305 }
306
307 coord->max = nr;
308
309 fprintf(stderr, "%s: found %" PRIu64 " classes\n",
310 coord->name, nr);
311 if (!write_coord_sd(coord))
312 fprintf(stderr, "%s: error writing symdata\n",
313 coord->name);
314 }
315
316 coord->symrep = realloc(coord->symrep, coord->max*sizeof(uint64_t));
317 coord->selfsim = realloc(coord->selfsim, coord->max*sizeof(uint64_t));
318
319 for (m = 0; m < NMOVES; m++) {
320 coord->mtable[m] = malloc(coord->max*sizeof(uint64_t));
321 coord->ttrep_move[m] = malloc(coord->max*sizeof(Trans));
322 }
323
324 if (!read_coord_mtable(coord)) {
325 for (ui = 0; ui < coord->max; ui++) {
326 uu = coord->symrep[ui];
327 for (m = 0; m < NMOVES; m++) {
328 uj = move_coord(coord->base[0], m, uu, NULL);
329 coord->mtable[m][ui] = coord->symclass[uj];
330 coord->ttrep_move[m][ui] =
331 coord->transtorep[uj];
332 }
333 }
334 if (!write_coord_mtable(coord))
335 fprintf(stderr, "%s: error writing mtable\n",
336 coord->name);
337 }
338}
339
340static bool
341read_coord_mtable(Coordinate *coord)
342{
343 FILE *f;
344 char fname[strlen(tabledir)+256];
345 Move m;
346 uint64_t M;
347 bool r;
348
349 strcpy(fname, tabledir);
350 strcat(fname, "/mt_");
351 strcat(fname, coord->name);
352
353 if ((f = fopen(fname, "rb")) == NULL)
354 return false;
355
356 M = coord->max;
357 r = true;
358 for (m = 0; m < NMOVES; m++)
359 r = r && fread(coord->mtable[m], sizeof(uint64_t), M, f) == M;
360
361 if (coord->type == SYM_COORD)
362 for (m = 0; m < NMOVES; m++)
363 r = r && fread(coord->ttrep_move[m],
364 sizeof(Trans), M, f) == M;
365
366 fclose(f);
367 return r;
368}
369
370static bool
371read_coord_sd(Coordinate *coord)
372{
373 FILE *f;
374 char fname[strlen(tabledir)+256];
375 uint64_t M, N;
376 bool r;
377
378 strcpy(fname, tabledir);
379 strcat(fname, "/sd_");
380 strcat(fname, coord->name);
381
382 if ((f = fopen(fname, "rb")) == NULL)
383 return false;
384
385 r = true;
386 r = r && fread(&coord->max, sizeof(uint64_t), 1, f) == 1;
387 M = coord->max;
388 N = coord->base[0]->max;
389 r = r && fread(coord->symrep, sizeof(uint64_t), M, f) == M;
390 r = r && fread(coord->selfsim, sizeof(uint64_t), M, f) == M;
391 r = r && fread(coord->symclass, sizeof(uint64_t), N, f) == N;
392 r = r && fread(coord->transtorep, sizeof(Trans), N, f) == N;
393
394 fclose(f);
395 return r;
396}
397
398static bool
399read_coord_ttable(Coordinate *coord)
400{
401 FILE *f;
402 char fname[strlen(tabledir)+256];
403 Trans t;
404 uint64_t M;
405 bool r;
406
407 strcpy(fname, tabledir);
408 strcat(fname, "/tt_");
409 strcat(fname, coord->name);
410
411 if ((f = fopen(fname, "rb")) == NULL)
412 return false;
413
414 M = coord->max;
415 r = true;
416 for (t = 0; t < NTRANS; t++)
417 r = r && fread(coord->ttable[t], sizeof(uint64_t), M, f) == M;
418
419 fclose(f);
420 return r;
421}
422
423static bool
424write_coord_mtable(Coordinate *coord)
425{
426 FILE *f;
427 char fname[strlen(tabledir)+256];
428 Move m;
429 uint64_t M;
430 bool r;
431
432 strcpy(fname, tabledir);
433 strcat(fname, "/mt_");
434 strcat(fname, coord->name);
435
436 if ((f = fopen(fname, "wb")) == NULL)
437 return false;
438
439 M = coord->max;
440 r = true;
441 for (m = 0; m < NMOVES; m++)
442 r = r && fwrite(coord->mtable[m], sizeof(uint64_t), M, f) == M;
443
444 if (coord->type == SYM_COORD)
445 for (m = 0; m < NMOVES; m++)
446 r = r && fwrite(coord->ttrep_move[m],
447 sizeof(Trans), M, f) == M;
448
449 fclose(f);
450 return r;
451}
452
453static bool
454write_coord_sd(Coordinate *coord)
455{
456 FILE *f;
457 char fname[strlen(tabledir)+256];
458 uint64_t M, N;
459 bool r;
460
461 strcpy(fname, tabledir);
462 strcat(fname, "/sd_");
463 strcat(fname, coord->name);
464
465 if ((f = fopen(fname, "wb")) == NULL)
466 return false;
467
468 r = true;
469 M = coord->max;
470 N = coord->base[0]->max;
471 r = r && fwrite(&coord->max, sizeof(uint64_t), 1, f) == 1;
472 r = r && fwrite(coord->symrep, sizeof(uint64_t), M, f) == M;
473 r = r && fwrite(coord->selfsim, sizeof(uint64_t), M, f) == M;
474 r = r && fwrite(coord->symclass, sizeof(uint64_t), N, f) == N;
475 r = r && fwrite(coord->transtorep, sizeof(Trans), N, f) == N;
476
477 fclose(f);
478 return r;
479}
480
481static bool
482write_coord_ttable(Coordinate *coord)
483{
484 FILE *f;
485 char fname[strlen(tabledir)+256];
486 Trans t;
487 uint64_t M;
488 bool r;
489
490 strcpy(fname, tabledir);
491 strcat(fname, "/tt_");
492 strcat(fname, coord->name);
493
494 if ((f = fopen(fname, "wb")) == NULL)
495 return false;
496
497 M = coord->max;
498 r = true;
499 for (t = 0; t < NTRANS; t++)
500 r = r && fwrite(coord->ttable[t], sizeof(uint64_t), M, f) == M;
501
502 fclose(f);
503 return r;
504}
505
506/* Public functions **********************************************************/
507
508void
509gen_coord(Coordinate *coord)
510{
511 int i;
512
513 if (coord == NULL || coord->generated)
514 return;
515
516 for (i = 0; i < 2; i++)
517 gen_coord(coord->base[i]);
518
519 switch (coord->type) {
520 case COMP_COORD:
521 if (coord->i[0] == NULL)
522 goto error_gc;
523 gen_coord_comp(coord);
524 break;
525 case SYM_COORD:
526 if (coord->base[0] == NULL || coord->tgrp == NULL)
527 goto error_gc;
528 gen_coord_sym(coord);
529 break;
530 case SYMCOMP_COORD:
531 if (coord->base[0] == NULL || coord->base[1] == NULL)
532 goto error_gc;
533 coord->max = coord->base[0]->max * coord->base[1]->max;
534 break;
535 default:
536 break;
537 }
538
539 coord->generated = true;
540 return;
541
542error_gc:
543 fprintf(stderr, "Error generating coordinates.\n"
544 "This is a bug, pleae report.\n");
545 exit(1);
546}
547
548uint64_t
549index_coord(Coordinate *coord, Cube *cube, Trans *offtrans)
550{
551 uint64_t c[2], cnosym;
552 Trans ttr;
553
554 switch (coord->type) {
555 case COMP_COORD:
556 if (offtrans != NULL)
557 *offtrans = uf;
558
559 return indexers_getind(coord->i, cube);
560 case SYM_COORD:
561 cnosym = index_coord(coord->base[0], cube, NULL);
562 ttr = coord->transtorep[cnosym];
563
564 if (offtrans != NULL)
565 *offtrans = ttr;
566
567 return coord->symclass[cnosym];
568 case SYMCOMP_COORD:
569 c[0] = index_coord(coord->base[0], cube, NULL);
570 cnosym = index_coord(coord->base[0]->base[0], cube, NULL);
571 ttr = coord->base[0]->transtorep[cnosym];
572 c[1] = index_coord(coord->base[1], cube, NULL);
573 c[1] = trans_coord(coord->base[1], ttr, c[1]);
574
575 if (offtrans != NULL)
576 *offtrans = ttr;
577
578 return c[0] * coord->base[1]->max + c[1];
579 default:
580 break;
581 }
582
583 return coord->max; /* Only reached in case of error */
584}
585
586uint64_t
587move_coord(Coordinate *coord, Move m, uint64_t ind, Trans *offtrans)
588{
589 uint64_t i[2], M;
590 Trans ttr;
591
592 /* Some safety checks should be done here, but for performance *
593 * reasons we'd rather do them before calling this function. *
594 * We should check if coord is generated. */
595
596 switch (coord->type) {
597 case COMP_COORD:
598 if (offtrans != NULL)
599 *offtrans = uf;
600
601 return coord->mtable[m][ind];
602 case SYM_COORD:
603 ttr = coord->ttrep_move[m][ind];
604
605 if (offtrans != NULL)
606 *offtrans = ttr;
607
608 return coord->mtable[m][ind];
609 case SYMCOMP_COORD:
610 M = coord->base[1]->max;
611 i[0] = ind / M;
612 i[1] = ind % M;
613 ttr = coord->base[0]->ttrep_move[m][i[0]];
614 i[0] = coord->base[0]->mtable[m][i[0]];
615 i[1] = coord->base[1]->mtable[m][i[1]];
616 i[1] = coord->base[1]->ttable[ttr][i[1]];
617
618 if (offtrans != NULL)
619 *offtrans = ttr;
620
621 return i[0] * M + i[1];
622 default:
623 break;
624 }
625
626 return coord->max; /* Only reached in case of error */
627}
628
629uint64_t
630trans_coord(Coordinate *coord, Trans t, uint64_t ind)
631{
632 uint64_t i[2], M;
633
634 /* Some safety checks should be done here, but for performance *
635 * reasons we'd rather do them before calling this function. *
636 * We should check if coord is generated. */
637
638 switch (coord->type) {
639 case COMP_COORD:
640 return coord->ttable[t][ind];
641 case SYM_COORD:
642 return ind;
643 case SYMCOMP_COORD:
644 M = coord->base[1]->max;
645 i[0] = ind / M; /* Always fixed */
646 i[1] = ind % M;
647 i[1] = coord->base[1]->ttable[t][i[1]];
648 return i[0] * M + i[1];
649 default:
650 break;
651 }
652
653 return coord->max; /* Only reached in case of error */
654}
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 @@
1#ifndef COORD_H
2#define COORD_H
3
4#include "trans.h"
5
6void gen_coord(Coordinate *coord);
7uint64_t index_coord(Coordinate *coord, Cube *cube,
8 Trans *offtrans);
9uint64_t indexers_getind(Indexer **is, Cube *c);
10void indexers_makecube(Indexer **is, uint64_t ind, Cube *c);
11uint64_t move_coord(Coordinate *coord, Move m,
12 uint64_t ind, Trans *offtrans);
13uint64_t trans_coord(Coordinate *coord, Trans t, uint64_t ind);
14
15/* Base coordinates and their index functions ********************************/
16
17#ifndef COORD_C
18
19extern Coordinate coord_eofb;
20extern Coordinate coord_coud;
21extern Coordinate coord_cp;
22extern Coordinate coord_cpudsep;
23extern Coordinate coord_epos;
24extern Coordinate coord_epe;
25extern Coordinate coord_eposepe;
26extern Coordinate coord_epud;
27extern Coordinate coord_eofbepos;
28extern Coordinate coord_coud_cpudsep;
29extern Coordinate coord_eofbepos_sym16;
30extern Coordinate coord_cp_sym16;
31extern Coordinate coord_corners_sym16;
32extern Coordinate coord_drud_sym16;
33extern Coordinate coord_drudfin_noE_sym16;
34extern Coordinate coord_nxopt31;
35
36extern Coordinate *all_coordinates[];
37
38#else
39
40/* Indexers ******************************************************************/
41
42uint64_t index_eofb(Cube *cube);
43void invindex_eofb(uint64_t ind, Cube *ret);
44Indexer
45i_eofb = {
46 .n = POW2TO11,
47 .index = index_eofb,
48 .to_cube = invindex_eofb,
49};
50
51uint64_t index_coud(Cube *cube);
52void invindex_coud(uint64_t ind, Cube *ret);
53Indexer
54i_coud = {
55 .n = POW3TO7,
56 .index = index_coud,
57 .to_cube = invindex_coud,
58};
59
60uint64_t index_cp(Cube *cube);
61void invindex_cp(uint64_t ind, Cube *ret);
62Indexer
63i_cp = {
64 .n = FACTORIAL8,
65 .index = index_cp,
66 .to_cube = invindex_cp,
67};
68
69uint64_t index_cpudsep(Cube *cube);
70void invindex_cpudsep(uint64_t ind, Cube *ret);
71Indexer
72i_cpudsep = {
73 .n = BINOM8ON4,
74 .index = index_cpudsep,
75 .to_cube = invindex_cpudsep,
76};
77
78uint64_t index_epos(Cube *cube);
79void invindex_epos(uint64_t ind, Cube *ret);
80Indexer
81i_epos = {
82 .n = BINOM12ON4,
83 .index = index_epos,
84 .to_cube = invindex_epos,
85};
86
87uint64_t index_epe(Cube *cube);
88void invindex_epe(uint64_t ind, Cube *ret);
89Indexer
90i_epe = {
91 .n = FACTORIAL4,
92 .index = index_epe,
93 .to_cube = invindex_epe,
94};
95
96uint64_t index_eposepe(Cube *cube);
97void invindex_eposepe(uint64_t ind, Cube *ret);
98Indexer
99i_eposepe = {
100 .n = BINOM12ON4 * FACTORIAL4,
101 .index = index_eposepe,
102 .to_cube = invindex_eposepe,
103};
104
105uint64_t index_epud(Cube *cube);
106void invindex_epud(uint64_t ind, Cube *ret);
107Indexer
108i_epud = {
109 .n = FACTORIAL8,
110 .index = index_epud,
111 .to_cube = invindex_epud,
112};
113
114/* Composite coordinates *****************************************************/
115
116Coordinate
117coord_eofb = {
118 .name = "eofb",
119 .type = COMP_COORD,
120 .i = {&i_eofb, NULL},
121};
122
123Coordinate
124coord_coud = {
125 .name = "coud",
126 .type = COMP_COORD,
127 .i = {&i_coud, NULL},
128};
129
130Coordinate
131coord_cp = {
132 .name = "cp",
133 .type = COMP_COORD,
134 .i = {&i_cp, NULL},
135};
136
137Coordinate
138coord_cpudsep = {
139 .name = "cpudsep",
140 .type = COMP_COORD,
141 .i = {&i_cpudsep, NULL},
142};
143
144Coordinate
145coord_epos = {
146 .name = "epos",
147 .type = COMP_COORD,
148 .i = {&i_epos, NULL},
149};
150
151Coordinate
152coord_epe = {
153 .name = "epe",
154 .type = COMP_COORD,
155 .i = {&i_epe, NULL},
156};
157
158Coordinate
159coord_eposepe = { /* Has to be done by hand, hard compose epos + epe */
160 .name = "eposepe",
161 .type = COMP_COORD,
162 .i = {&i_eposepe, NULL},
163};
164
165Coordinate
166coord_epud = {
167 .name = "epud",
168 .type = COMP_COORD,
169 .i = {&i_epud, NULL},
170};
171
172Coordinate
173coord_eofbepos = {
174 .name = "eofbepos",
175 .type = COMP_COORD,
176 .i = {&i_epos, &i_eofb, NULL},
177};
178
179Coordinate
180coord_coud_cpudsep = {
181 .name = "coud_cpudsep",
182 .type = COMP_COORD,
183 .i = {&i_coud, &i_cpudsep, NULL},
184};
185
186/* Symcoordinates ************************************************************/
187
188Coordinate
189coord_eofbepos_sym16 = {
190 .name = "eofbepos_sym16",
191 .type = SYM_COORD,
192 .base = {&coord_eofbepos, NULL},
193 .tgrp = &tgrp_udfix,
194};
195
196Coordinate
197coord_cp_sym16 = {
198 .name = "cp_sym16",
199 .type = SYM_COORD,
200 .base = {&coord_cp, NULL},
201 .tgrp = &tgrp_udfix,
202};
203
204/* "Symcomp" coordinates *****************************************************/
205
206Coordinate
207coord_corners_sym16 = {
208 .name = "corners_sym16",
209 .type = SYMCOMP_COORD,
210 .base = {&coord_cp_sym16, &coord_coud},
211};
212
213Coordinate
214coord_drud_sym16 = {
215 .name = "drud_sym16",
216 .type = SYMCOMP_COORD,
217 .base = {&coord_eofbepos_sym16, &coord_coud},
218};
219
220Coordinate
221coord_drudfin_noE_sym16 = {
222 .name = "drudfin_noE_sym16",
223 .type = SYMCOMP_COORD,
224 .base = {&coord_cp_sym16, &coord_epud},
225};
226
227Coordinate
228coord_nxopt31 = {
229 .name = "nxopt31",
230 .type = SYMCOMP_COORD,
231 .base = {&coord_eofbepos_sym16, &coord_coud_cpudsep},
232};
233
234/* All coordinates ***********************************************************/
235
236Coordinate *all_coordinates[] = {
237 &coord_eofb,
238 &coord_coud,
239 &coord_cp,
240 &coord_cpudsep,
241 &coord_epos,
242 &coord_epe,
243 &coord_eposepe,
244 &coord_epud,
245 &coord_eofbepos,
246 &coord_coud_cpudsep,
247 &coord_eofbepos_sym16,
248 &coord_cp_sym16,
249 &coord_corners_sym16,
250 &coord_drud_sym16,
251 &coord_drudfin_noE_sym16,
252 &coord_nxopt31,
253 NULL
254};
255
256#endif
257
258#endif
259
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 @@
1#define CUBE_C
2
3#include "cube.h"
4
5static int where_is_piece(int piece, int *arr, int n);
6
7void
8compose_centers(Cube *c2, Cube *c1)
9{
10 apply_permutation(c2->xp, c1->xp, 6);
11}
12
13void
14compose_corners(Cube *c2, Cube *c1)
15{
16 apply_permutation(c2->cp, c1->cp, 8);
17 apply_permutation(c2->cp, c1->co, 8);
18 sum_arrays_mod(c2->co, c1->co, 8, 3);
19}
20
21void
22compose_edges(Cube *c2, Cube *c1)
23{
24 apply_permutation(c2->ep, c1->ep, 12);
25 apply_permutation(c2->ep, c1->eo, 12);
26 sum_arrays_mod(c2->eo, c1->eo, 12, 2);
27}
28
29void
30compose(Cube *c2, Cube *c1)
31{
32 compose_centers(c2, c1);
33 compose_corners(c2, c1);
34 compose_edges(c2, c1);
35}
36
37void
38copy_cube_centers(Cube *src, Cube *dst)
39{
40 memcpy(dst->xp, src->xp, 6 * sizeof(int));
41}
42
43void
44copy_cube_corners(Cube *src, Cube *dst)
45{
46 memcpy(dst->cp, src->cp, 8 * sizeof(int));
47 memcpy(dst->co, src->co, 8 * sizeof(int));
48}
49
50void
51copy_cube_edges(Cube *src, Cube *dst)
52{
53 memcpy(dst->ep, src->ep, 12 * sizeof(int));
54 memcpy(dst->eo, src->eo, 12 * sizeof(int));
55}
56
57void
58copy_cube(Cube *src, Cube *dst)
59{
60 copy_cube_centers(src, dst);
61 copy_cube_corners(src, dst);
62 copy_cube_edges(src, dst);
63}
64
65bool
66equal(Cube *c1, Cube *c2)
67{
68 int i;
69
70 for (i = 0; i < 12; i++)
71 if (c1->ep[i] != c2->ep[i] || c1->eo[i] != c2->eo[i])
72 return false;
73
74 for (i = 0; i < 8; i++)
75 if (c1->cp[i] != c2->cp[i] || c1->co[i] != c2->co[i])
76 return false;
77
78 for (i = 0; i < 6; i++)
79 if (c1->xp[i] != c2->xp[i])
80 return false;
81
82 return true;
83}
84
85void
86invert_cube_centers(Cube *cube)
87{
88 int i;
89 Cube aux;
90
91 copy_cube_centers(cube, &aux);
92
93 for (i = 0; i < 6; i++)
94 cube->xp[aux.xp[i]] = i;
95}
96
97void
98invert_cube_corners(Cube *cube)
99{
100 int i;
101 Cube aux;
102
103 copy_cube_corners(cube, &aux);
104
105 for (i = 0; i < 8; i++) {
106 cube->cp[aux.cp[i]] = i;
107 cube->co[aux.cp[i]] = (3 - aux.co[i]) % 3;
108 }
109}
110
111void
112invert_cube_edges(Cube *cube)
113{
114 int i;
115 Cube aux;
116
117 copy_cube_edges(cube, &aux);
118
119 for (i = 0; i < 12; i++) {
120 cube->ep[aux.ep[i]] = i;
121 cube->eo[aux.ep[i]] = aux.eo[i];
122 }
123}
124
125void
126invert_cube(Cube *cube)
127{
128 invert_cube_centers(cube);
129 invert_cube_corners(cube);
130 invert_cube_edges(cube);
131}
132
133bool
134is_admissible(Cube *c) {
135 bool perm;
136 int sign, i;
137 int sum_e, sum_c;
138
139 perm = is_perm(c->ep, 12) && is_perm(c->cp, 8) && is_perm(c->xp, 6);
140
141 sign = perm_sign(c->ep,12) + perm_sign(c->cp,8) + perm_sign(c->xp,6);
142
143 for (i = 0, sum_e = 0; i < 12; i++)
144 if (c->eo[i] > 1)
145 return false;
146 else
147 sum_e += c->eo[i];
148
149 for (i = 0, sum_c = 0; i < 8; i++)
150 if (c->co[i] > 2)
151 return false;
152 else
153 sum_c += c->co[i];
154
155 return (perm && sign % 2 == 0 && sum_e % 2 == 0 && sum_c % 2 == 0);
156}
157
158bool
159is_solved(Cube *cube)
160{
161 Cube solved_cube;
162 make_solved(&solved_cube);
163
164 return equal(cube, &solved_cube);
165}
166
167void
168make_solved_centers(Cube *cube)
169{
170 static int sorted[6] = {0, 1, 2, 3, 4, 5};
171
172 memcpy(cube->xp, sorted, 6 * sizeof(int));
173}
174
175void
176make_solved_corners(Cube *cube)
177{
178 static int sorted[8] = {0, 1, 2, 3, 4, 5, 6, 7};
179
180 memcpy(cube->cp, sorted, 8 * sizeof(int));
181 memset(cube->co, 0, 8 * sizeof(int));
182}
183
184void
185make_solved_edges(Cube *cube)
186{
187 static int sorted[12] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
188
189 memcpy(cube->ep, sorted, 12 * sizeof(int));
190 memset(cube->eo, 0, 12 * sizeof(int));
191}
192
193void
194make_solved(Cube *cube)
195{
196 make_solved_centers(cube);
197 make_solved_corners(cube);
198 make_solved_edges(cube);
199}
200
201void
202print_cube(Cube *cube)
203{
204 static char edge_string[12][7] = {
205 [UF] = "UF", [UL] = "UL", [UB] = "UB", [UR] = "UR",
206 [DF] = "DF", [DL] = "DL", [DB] = "DB", [DR] = "DR",
207 [FR] = "FR", [FL] = "FL", [BL] = "BL", [BR] = "BR"
208 };
209
210 static char corner_string[8][7] = {
211 [UFR] = "UFR", [UFL] = "UFL", [UBL] = "UBL", [UBR] = "UBR",
212 [DFR] = "DFR", [DFL] = "DFL", [DBL] = "DBL", [DBR] = "DBR"
213 };
214
215 static char center_string[6][7] = {
216 [U_center] = "U", [D_center] = "D",
217 [R_center] = "R", [L_center] = "L",
218 [F_center] = "F", [B_center] = "B"
219 };
220
221 for (int i = 0; i < 12; i++)
222 printf(" %s ", edge_string[cube->ep[i]]);
223 printf("\n");
224
225 for (int i = 0; i < 12; i++)
226 printf(" %" PRIu8 " ", cube->eo[i]);
227 printf("\n");
228
229 for (int i = 0; i < 8; i++)
230 printf("%s ", corner_string[cube->cp[i]]);
231 printf("\n");
232
233 for (int i = 0; i < 8; i++)
234 printf(" %" PRIu8 " ", cube->co[i]);
235 printf("\n");
236
237 for (int i = 0; i < 6; i++)
238 printf(" %s ", center_string[cube->xp[i]]);
239 printf("\n");
240}
241
242int
243where_is_center(Center x, Cube *c)
244{
245 return where_is_piece(x, c->xp, 6);
246}
247
248int
249where_is_corner(Corner k, Cube *c)
250{
251 return where_is_piece(k, c->cp, 8);
252}
253
254int
255where_is_edge(Edge e, Cube *c)
256{
257 return where_is_piece(e, c->ep, 12);
258}
259
260static int
261where_is_piece(int piece, int *arr, int n)
262{
263 int i;
264
265 for (i = 0; i < n; i++)
266 if (arr[i] == piece)
267 return i;
268
269 return -1;
270}
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 @@
1#ifndef CUBE_H
2#define CUBE_H
3
4#include <stdio.h>
5
6#include "cubetypes.h"
7#include "env.h"
8#include "utils.h"
9
10void compose(Cube *c2, Cube *c1); /* Use c2 as an alg on c1 */
11void compose_centers(Cube *c2, Cube *c1);
12void compose_corners(Cube *c2, Cube *c1);
13void compose_edges(Cube *c2, Cube *c1);
14void copy_cube(Cube *src, Cube *dst);
15void copy_cube_centers(Cube *src, Cube *dst);
16void copy_cube_corners(Cube *src, Cube *dst);
17void copy_cube_edges(Cube *src, Cube *dst);
18bool equal(Cube *c1, Cube *c2);
19void invert_cube(Cube *cube);
20void invert_cube_centers(Cube *cube);
21void invert_cube_corners(Cube *cube);
22void invert_cube_edges(Cube *cube);
23bool is_admissible(Cube *cube);
24bool is_solved(Cube *cube);
25void make_solved(Cube *cube);
26void make_solved_centers(Cube *cube);
27void make_solved_corners(Cube *cube);
28void make_solved_edges(Cube *cube);
29void print_cube(Cube *cube);
30int where_is_center(Center x, Cube *c);
31int where_is_corner(Corner k, Cube *c);
32int where_is_edge(Edge e, Cube *c);
33
34#endif
35
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 @@
1#ifndef CUBETYPES_H
2#define CUBETYPES_H
3
4#include <stdbool.h>
5#include <inttypes.h>
6#include <pthread.h>
7
8#define NMOVES 55 /* Actually 54, but one is NULLMOVE */
9#define NTRANS 48
10#define NROTATIONS 24
11#define entry_group_t uint8_t /* For pruning tables */
12
13#define MAX_N_COORD 6
14
15/* Enums *********************************************************************/
16
17typedef enum
18center
19{
20 U_center, D_center,
21 R_center, L_center,
22 F_center, B_center
23} Center;
24
25typedef enum
26corner
27{
28 UFR, UFL, UBL, UBR,
29 DFR, DFL, DBL, DBR
30} Corner;
31
32typedef enum
33coordtype
34{
35 COMP_COORD, SYM_COORD, SYMCOMP_COORD
36} CoordType;
37
38typedef enum
39edge
40{
41 UF, UL, UB, UR,
42 DF, DL, DB, DR,
43 FR, FL, BL, BR
44} Edge;
45
46typedef enum
47move
48{
49 NULLMOVE,
50 U, U2, U3, D, D2, D3,
51 R, R2, R3, L, L2, L3,
52 F, F2, F3, B, B2, B3,
53 Uw, Uw2, Uw3, Dw, Dw2, Dw3,
54 Rw, Rw2, Rw3, Lw, Lw2, Lw3,
55 Fw, Fw2, Fw3, Bw, Bw2, Bw3,
56 M, M2, M3,
57 S, S2, S3,
58 E, E2, E3,
59 x, x2, x3,
60 y, y2, y3,
61 z, z2, z3,
62} Move;
63
64typedef enum
65trans
66{
67 uf, ur, ub, ul,
68 df, dr, db, dl,
69 rf, rd, rb, ru,
70 lf, ld, lb, lu,
71 fu, fr, fd, fl,
72 bu, br, bd, bl,
73 uf_mirror, ur_mirror, ub_mirror, ul_mirror,
74 df_mirror, dr_mirror, db_mirror, dl_mirror,
75 rf_mirror, rd_mirror, rb_mirror, ru_mirror,
76 lf_mirror, ld_mirror, lb_mirror, lu_mirror,
77 fu_mirror, fr_mirror, fd_mirror, fl_mirror,
78 bu_mirror, br_mirror, bd_mirror, bl_mirror,
79} Trans;
80
81
82/* Typedefs ******************************************************************/
83
84typedef struct alg Alg;
85typedef struct alglist AlgList;
86typedef struct alglistnode AlgListNode;
87typedef struct choicestep ChoiceStep;
88typedef struct command Command;
89typedef struct commandargs CommandArgs;
90typedef struct coordinate Coordinate;
91typedef struct cube Cube;
92/*typedef struct dfsarg DfsArg;*/
93typedef struct fstcube FstCube;
94typedef struct indexer Indexer;
95typedef struct movable Movable;
96typedef struct moveset Moveset;
97typedef struct prunedata PruneData;
98typedef struct solveoptions SolveOptions;
99typedef struct step Step;
100typedef struct symdata SymData;
101typedef struct threaddatasolve ThreadDataSolve;
102typedef struct threaddatagenpt ThreadDataGenpt;
103typedef struct transgroup TransGroup;
104
105typedef bool (*Checker) (Cube *);
106typedef bool (*CubeTester) (Cube *, Alg *);
107/*typedef bool (*DfsMover) (DfsArg *);*/
108typedef void (*DfsExtraCopier) (void *, void *);
109typedef Alg * (*Validator) (Alg *);
110typedef void (*Exec) (CommandArgs *);
111typedef CommandArgs * (*ArgParser) (int, char **);
112typedef bool (*Tester) (void);
113typedef int (*TransFinder) (uint64_t, Trans *);
114
115
116/* Structs *******************************************************************/
117
118struct
119alg
120{
121 Move * move;
122 bool * inv;
123 int len;
124 int allocated;
125 Move * move_normal;
126 int len_normal;
127 Move * move_inverse;
128 int len_inverse;
129};
130
131struct
132alglist
133{
134 AlgListNode * first;
135 AlgListNode * last;
136 int len;
137};
138
139struct
140alglistnode
141{
142 Alg * alg;
143 AlgListNode * next;
144};
145
146struct
147choicestep
148{
149 char * shortname;
150 char * name;
151 Step * step[99];
152 Trans t[99];
153 char * ready_msg;
154};
155
156struct
157command
158{
159 char * name;
160 char * usage;
161 char * description;
162 ArgParser parse_args;
163 Exec exec;
164};
165
166struct
167commandargs
168{
169 bool success;
170 Alg * scramble;
171 SolveOptions * opts;
172 ChoiceStep * cs;
173 Command * command; /* For help */
174 int n;
175 char scrtype[20];
176 bool scrstdin;
177 bool header;
178};
179
180struct
181coordinate
182{
183 char * name;
184 CoordType type;
185 bool generated;
186 Indexer * i[99];
187 uint64_t max;
188 uint64_t * mtable[NMOVES];
189 uint64_t * ttable[NTRANS];
190 TransGroup * tgrp;
191 Coordinate * base[2];
192 uint64_t * symclass;
193 uint64_t * symrep;
194 Trans * transtorep;
195 Trans * ttrep_move[NMOVES];
196 uint64_t * selfsim;
197};
198
199struct
200cube
201{
202 int ep[12];
203 int eo[12];
204 int cp[8];
205 int co[8];
206 int xp[6];
207};
208
209/*
210struct
211movable
212{
213 uint64_t val;
214 Trans t;
215};
216*/
217
218/*
219struct
220dfsarg
221{
222 Cube * cube;
223 Movable ind[MAX_N_COORD];
224 Trans t;
225 Step * s;
226 SolveOptions * opts;
227 int d;
228 int bound;
229 bool niss;
230 AlgList * sols;
231 pthread_mutex_t * sols_mutex;
232 Alg * current_alg;
233 void * extra;
234};
235*/
236
237/*
238struct
239dfsarg
240{
241 void * cube_data;
242 SolveOptions * opts;
243 int d;
244 int bound;
245 bool niss;
246 AlgList * sols;
247 Alg * current_alg;
248 Solver * solver;
249 Threader * threader;
250};
251*/
252
253struct
254fstcube
255{
256 uint16_t uf_eofb;
257 uint16_t uf_eposepe;
258 uint16_t uf_coud;
259 uint16_t uf_cp;
260 uint16_t fr_eofb;
261 uint16_t fr_eposepe;
262 uint16_t fr_coud;
263 uint16_t rd_eofb;
264 uint16_t rd_eposepe;
265 uint16_t rd_coud;
266};
267
268struct
269indexer
270{
271 int n;
272 uint64_t (*index)(Cube *);
273 void (*to_cube)(uint64_t, Cube *);
274};
275
276struct
277moveset
278{
279 char * name;
280 bool (*allowed)(Move);
281 bool (*can_append)(Alg *, Move, bool);
282 bool (*cancel_niss)(Alg *);
283 Move sorted_moves[NMOVES+1];
284};
285
286struct
287prunedata
288{
289 entry_group_t * ptable;
290 uint64_t n;
291 Coordinate * coord;
292 Moveset * moveset;
293 uint64_t count[16];
294 bool compact;
295 int base;
296};
297
298struct
299solveoptions
300{
301 int min_moves;
302 int max_moves;
303 int max_solutions;
304 int nthreads;
305 int optimal;
306 bool can_niss;
307 bool verbose;
308 bool all;
309 bool print_number;
310 bool count_only;
311};
312
313struct
314step
315{
316 Checker ready;
317 bool final;
318 Moveset * moveset;
319 int n_coord;
320 Coordinate * coord[MAX_N_COORD];
321 Trans coord_trans[MAX_N_COORD];
322 PruneData * pd[MAX_N_COORD];
323 bool pd_compact[MAX_N_COORD];
324 Validator is_valid;
325 /*DfsMover custom_move_checkstop;*/
326 DfsExtraCopier copy_extra;
327};
328
329/*
330struct
331threaddatasolve
332{
333 DfsArg arg;
334 int thid;
335 AlgList * start;
336 AlgListNode ** node;
337 pthread_mutex_t * start_mutex;
338};
339*/
340
341struct
342threaddatagenpt
343{
344 int thid;
345 int nthreads;
346 PruneData * pd;
347 int d;
348 int nchunks;
349 pthread_mutex_t ** mutex;
350 pthread_mutex_t * upmutex;
351};
352
353struct
354transgroup
355{
356 int n;
357 Trans t[NTRANS];
358};
359
360#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 @@
1#define ENV_C
2
3#include "env.h"
4
5bool initialized_env = false;
6char *tabledir;
7
8void
9mymkdir(char *d, int m)
10{
11#ifdef _WIN32
12 mkdir(d);
13#else
14 mkdir(d, m);
15#endif
16}
17
18void
19init_env()
20{
21 char *nissydata = getenv("NISSYDATA");
22 char *localdata = getenv("XDG_DATA_HOME");
23 char *home = getenv("HOME");
24 bool read, write;
25
26 if (initialized_env)
27 return;
28
29 if (nissydata != NULL) {
30 tabledir = malloc((strlen(nissydata) + 20) * sizeof(char));
31 strcpy(tabledir, nissydata);
32 } else if (localdata != NULL) {
33 tabledir = malloc((strlen(localdata) + 20) * sizeof(char));
34 strcpy(tabledir, localdata);
35 strcat(tabledir, "/nissy");
36 } else if (home != NULL) {
37 tabledir = malloc((strlen(home) + 20) * sizeof(char));
38 strcpy(tabledir, home);
39 strcat(tabledir, "/.nissy");
40 } else {
41 tabledir = malloc(20 * sizeof(char));
42 strcpy(tabledir, ".");
43 }
44
45 mymkdir(tabledir, 0777);
46 strcat(tabledir, "/tables");
47 mymkdir(tabledir, 0777);
48
49 read = !access(tabledir, R_OK);
50 write = !access(tabledir, W_OK);
51
52 if (!read) {
53 fprintf(stderr, "Table files cannot be read.\n");
54 } else if (!write) {
55 fprintf(stderr, "Data directory not writable: ");
56 fprintf(stderr, "tables can be loaded, but not saved.\n");
57 }
58
59 initialized_env = true;
60}
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 @@
1#ifndef ENV_H
2#define ENV_H
3
4#include <stdbool.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
8#include <unistd.h>
9#include <sys/stat.h>
10
11void init_env();
12
13extern char *tabledir;
14
15#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 @@
1#define FST_C
2
3#include "fst.h"
4
5static FstCube ep_to_fst_epos(int *ep);
6static void init_fst_corner_invtables();
7static void init_fst_eo_invtables();
8static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *);
9static void init_fst_where_is_edge();
10static bool read_fst_tables_file();
11static bool write_fst_tables_file();
12
13static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0,
14 [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1,
15 [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2};
16
17static uint16_t inv_coud[FACTORIAL8][POW3TO7];
18static uint16_t inv_cp[FACTORIAL8];
19static uint16_t uf_cp_to_fr_cp[FACTORIAL8];
20static uint16_t uf_cp_to_rd_cp[FACTORIAL8];
21static uint16_t eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4];
22static uint16_t fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4];
23
24FstCube
25cube_to_fst(Cube *cube)
26{
27 Cube c;
28 FstCube ret;
29
30 copy_cube(cube, &c);
31 ret.uf_eofb = coord_eofb.i[0]->index(&c);
32 ret.uf_eposepe = coord_eposepe.i[0]->index(&c);
33 ret.uf_coud = coord_coud.i[0]->index(&c);
34 ret.uf_cp = coord_cp.i[0]->index(&c);
35 copy_cube(cube, &c);
36 apply_trans(fr, &c);
37 ret.fr_eofb = coord_eofb.i[0]->index(&c);
38 ret.fr_eposepe = coord_eposepe.i[0]->index(&c);
39 ret.fr_coud = coord_coud.i[0]->index(&c);
40 copy_cube(cube, &c);
41 apply_trans(rd, &c);
42 ret.rd_eofb = coord_eofb.i[0]->index(&c);
43 ret.rd_eposepe = coord_eposepe.i[0]->index(&c);
44 ret.rd_coud = coord_coud.i[0]->index(&c);
45
46 return ret;
47}
48
49static FstCube
50ep_to_fst_epos(int *ep)
51{
52 static int eind[12] = {
53 [FR] = 0, [FL] = 1, [BL] = 2, [BR] = 3,
54 [UR] = 0, [DR] = 1, [DL] = 2, [UL] = 3,
55 [DB] = 0, [DF] = 1, [UF] = 2, [UB] = 3
56 };
57 static int eptrans_fr[12] = {
58 [FR] = UF, [DF] = UL, [FL] = UB, [UF] = UR,
59 [BR] = DF, [DB] = DL, [BL] = DB, [UB] = DR,
60 [UR] = FR, [DR] = FL, [DL] = BL, [UL] = BR
61 };
62 static int eptrans_rd[12] = {
63 [DR] = UF, [FR] = UL, [UR] = UB, [BR] = UR,
64 [DL] = DF, [FL] = DL, [UL] = DB, [BL] = DR,
65 [DB] = FR, [DF] = FL, [UF] = BL, [UB] = BR
66 };
67
68 FstCube ret;
69 int i, ce, cs, cm;
70 int epe[4], eps[4], epm[4], epose[12], eposs[12], eposm[12];
71
72 memset(epose, 0, 12*sizeof(int));
73 memset(eposs, 0, 12*sizeof(int));
74 memset(eposm, 0, 12*sizeof(int));
75
76 for (i = 0, ce = 0; i < 12; i++) {
77 switch (edge_slice[ep[i]]) {
78 case 0:
79 epose[i] = 1;
80 epe[ce++] = eind[ep[i]];
81 break;
82 case 1:
83 eposs[eptrans_fr[i]] = eind[ep[i]] + 1;
84 break;
85 default:
86 eposm[eptrans_rd[i]] = eind[ep[i]] + 1;
87 break;
88 }
89 }
90
91 for (i = 0, cs = 0, cm = 0; i < 12; i++) {
92 if (eposs[i]) {
93 eps[cs++] = eposs[i] - 1;
94 eposs[i] = 1;
95 }
96 if (eposm[i]) {
97 epm[cm++] = eposm[i] - 1;
98 eposm[i] = 1;
99 }
100 }
101
102 ret.uf_eposepe = subset_to_index(epose, 12, 4) * FACTORIAL4 +
103 perm_to_index(epe, 4);
104 ret.fr_eposepe = subset_to_index(eposs, 12, 4) * FACTORIAL4 +
105 perm_to_index(eps, 4);
106 ret.rd_eposepe = subset_to_index(eposm, 12, 4) * FACTORIAL4 +
107 perm_to_index(epm, 4);
108
109 return ret;
110}
111
112FstCube
113fst_inverse(FstCube fst)
114{
115 FstCube ret;
116 int ep_inv[12];
117
118 ep_inv[FR] = fst_where_is_edge_arr[0][FR][fst.uf_eposepe];
119 ep_inv[FL] = fst_where_is_edge_arr[0][FL][fst.uf_eposepe];
120 ep_inv[BL] = fst_where_is_edge_arr[0][BL][fst.uf_eposepe];
121 ep_inv[BR] = fst_where_is_edge_arr[0][BR][fst.uf_eposepe];
122
123 ep_inv[UR] = fst_where_is_edge_arr[1][UR][fst.fr_eposepe];
124 ep_inv[UL] = fst_where_is_edge_arr[1][UL][fst.fr_eposepe];
125 ep_inv[DR] = fst_where_is_edge_arr[1][DR][fst.fr_eposepe];
126 ep_inv[DL] = fst_where_is_edge_arr[1][DL][fst.fr_eposepe];
127
128 ep_inv[UF] = fst_where_is_edge_arr[2][UF][fst.rd_eposepe];
129 ep_inv[UB] = fst_where_is_edge_arr[2][UB][fst.rd_eposepe];
130 ep_inv[DF] = fst_where_is_edge_arr[2][DF][fst.rd_eposepe];
131 ep_inv[DB] = fst_where_is_edge_arr[2][DB][fst.rd_eposepe];
132
133 ret = ep_to_fst_epos(ep_inv);
134
135 ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) |
136 ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) |
137 ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]);
138 ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) |
139 ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) |
140 ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]);
141 ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) |
142 ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) |
143 ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]);
144
145 ret.uf_cp = inv_cp[fst.uf_cp];
146
147 ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud];
148 ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud];
149 ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud];
150
151 return ret;
152}
153
154FstCube
155fst_move(Move m, FstCube fst)
156{
157 FstCube ret;
158 Move m_fr, m_rd;
159
160 m_fr = transform_move(fr, m);
161 m_rd = transform_move(rd, m);
162
163 ret.uf_eofb = coord_eofb.mtable[m][fst.uf_eofb];
164 ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe];
165 ret.uf_coud = coord_coud.mtable[m][fst.uf_coud];
166 ret.uf_cp = coord_cp.mtable[m][fst.uf_cp];
167
168 ret.fr_eofb = coord_eofb.mtable[m_fr][fst.fr_eofb];
169 ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe];
170 ret.fr_coud = coord_coud.mtable[m_fr][fst.fr_coud];
171
172 ret.rd_eofb = coord_eofb.mtable[m_rd][fst.rd_eofb];
173 ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe];
174 ret.rd_coud = coord_coud.mtable[m_rd][fst.rd_coud];
175
176 return ret;
177}
178
179void
180fst_to_cube(FstCube fst, Cube *cube)
181{
182 Cube e, s, m;
183 int i;
184
185 coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e);
186 coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s);
187 apply_trans(inverse_trans(fr), &s);
188 coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m);
189 apply_trans(inverse_trans(rd), &m);
190
191 for (i = 0; i < 12; i++) {
192 if (edge_slice[e.ep[i]] == 0)
193 cube->ep[i] = e.ep[i];
194 if (edge_slice[s.ep[i]] == 1)
195 cube->ep[i] = s.ep[i];
196 if (edge_slice[m.ep[i]] == 2)
197 cube->ep[i] = m.ep[i];
198 }
199
200 coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube);
201 coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube);
202 coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube);
203
204 for (i = 0; i < 6; i++)
205 cube->xp[i] = i;
206}
207
208void
209init_fst()
210{
211 init_trans();
212 gen_coord(&coord_eofb);
213 gen_coord(&coord_eposepe);
214 gen_coord(&coord_coud);
215 gen_coord(&coord_cp);
216
217 if (!read_fst_tables_file()) {
218 fprintf(stderr,
219 "Could not load fst_tables, generating them\n");
220 init_fst_corner_invtables();
221 init_fst_eo_invtables();
222 init_fst_where_is_edge();
223 if (!write_fst_tables_file())
224 fprintf(stderr, "fst_tables could not be written\b");
225 }
226}
227
228static void
229init_fst_corner_invtables()
230{
231 Cube c, d;
232 uint64_t cp, coud;
233
234 for (cp = 0; cp < FACTORIAL8; cp++) {
235 make_solved_corners(&c);
236 coord_cp.i[0]->to_cube(cp, &c);
237
238 copy_cube_corners(&c, &d);
239 invert_cube_corners(&d);
240 inv_cp[cp] = coord_cp.i[0]->index(&d);
241
242 for (coud = 0; coud < POW3TO7; coud++) {
243 copy_cube_corners(&c, &d);
244 coord_coud.i[0]->to_cube(coud, &d);
245 invert_cube_corners(&d);
246 inv_coud[cp][coud] = coord_coud.i[0]->index(&d);
247 }
248
249 copy_cube_corners(&c, &d);
250 apply_trans(fr, &d);
251 uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d);
252
253 copy_cube_corners(&c, &d);
254 apply_trans(rd, &d);
255 uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d);
256 }
257}
258
259static void
260init_fst_eo_invtables()
261{
262 uint64_t ep, eo;
263 Cube c, d;
264
265 for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) {
266 make_solved(&c);
267 coord_eposepe.i[0]->to_cube(ep, &c);
268 for (eo = 0; eo < POW2TO11; eo++) {
269 copy_cube_edges(&c, &d);
270 coord_eofb.i[0]->to_cube(eo, &d);
271 init_fst_eo_update(eo, ep, 0, &d);
272
273 apply_trans(inverse_trans(fr), &d);
274 coord_eofb.i[0]->to_cube(eo, &d);
275 init_fst_eo_update(eo, ep, 1, &d);
276
277 copy_cube_edges(&c, &d);
278 apply_trans(inverse_trans(rd), &d);
279 coord_eofb.i[0]->to_cube(eo, &d);
280 init_fst_eo_update(eo, ep, 2, &d);
281 }
282 }
283}
284
285static void
286init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d)
287{
288 int i;
289
290 for (i = 0; i < 12; i++) {
291 if (edge_slice[d->ep[i]] == s && d->eo[i] && d->ep[i] != 11)
292 eo_invtable[s][eo][ep] |=
293 ((uint16_t)1) << ((uint16_t)d->ep[i]);
294 }
295}
296
297static void
298init_fst_where_is_edge()
299{
300 Cube c, d;
301 uint64_t e;
302
303 make_solved(&c);
304 for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) {
305 coord_eposepe.i[0]->to_cube(e, &c);
306
307 copy_cube_edges(&c, &d);
308 fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d);
309 fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d);
310 fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d);
311 fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d);
312
313 copy_cube_edges(&c, &d);
314 apply_trans(inverse_trans(fr), &d);
315 fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d);
316 fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d);
317 fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d);
318 fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d);
319
320 copy_cube_edges(&c, &d);
321 apply_trans(inverse_trans(rd), &d);
322 fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d);
323 fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d);
324 fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d);
325 fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &d);
326 }
327}
328
329static bool
330read_fst_tables_file()
331{
332 init_env();
333
334 FILE *f;
335 char fname[strlen(tabledir)+256];
336 uint64_t i, j, r, total;
337
338 strcpy(fname, tabledir);
339 strcat(fname, "/fst_tables");
340
341 if ((f = fopen(fname, "rb")) == NULL)
342 return false;
343
344 r = 0;
345 total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11);
346
347 for (i = 0; i < FACTORIAL8; i++)
348 r += fread(inv_coud[i], sizeof(uint16_t), POW3TO7, f);
349 r += fread(inv_cp, sizeof(uint16_t), FACTORIAL8, f);
350 r += fread(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f);
351 r += fread(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f);
352 for (i = 0; i < 3; i++)
353 for (j = 0; j < POW2TO11; j++)
354 r += fread(eo_invtable[i][j],
355 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f);
356 for (i = 0; i < 3; i++)
357 for (j = 0; j < 12; j++)
358 r += fread(fst_where_is_edge_arr[i][j],
359 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f);
360
361 fclose(f);
362
363 return r == total;
364}
365
366static bool
367write_fst_tables_file()
368{
369 init_env();
370
371 FILE *f;
372 char fname[strlen(tabledir)+256];
373 uint64_t i, j, w, total;
374
375 strcpy(fname, tabledir);
376 strcat(fname, "/fst_tables");
377
378 if ((f = fopen(fname, "wb")) == NULL)
379 return false;
380
381 w = 0;
382 total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11);
383
384 for (i = 0; i < FACTORIAL8; i++)
385 w += fwrite(inv_coud[i], sizeof(uint16_t), POW3TO7, f);
386 w += fwrite(inv_cp, sizeof(uint16_t), FACTORIAL8, f);
387 w += fwrite(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f);
388 w += fwrite(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f);
389 for (i = 0; i < 3; i++)
390 for (j = 0; j < POW2TO11; j++)
391 w += fwrite(eo_invtable[i][j],
392 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f);
393 for (i = 0; i < 3; i++)
394 for (j = 0; j < 12; j++)
395 w += fwrite(fst_where_is_edge_arr[i][j],
396 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f);
397
398 fclose(f);
399
400 return w == total;
401}
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 @@
1#ifndef FST_H
2#define FST_H
3
4#include "coord.h"
5
6FstCube cube_to_fst(Cube *cube);
7FstCube fst_inverse(FstCube fst);
8FstCube fst_move(Move m, FstCube fst);
9void fst_to_cube(FstCube fst, Cube *cube);
10void init_fst();
11
12#endif
13
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 @@
1#define MOVES_C
2
3#include "moves.h"
4
5/* Local functions ***********************************************************/
6
7static void cleanup_aux(Alg *alg, Alg *ret, bool inv);
8
9/* Tables and other data *****************************************************/
10
11/* Moves are represented as cubes and applied using compose(). Every move is *
12 * translated to a an <U, x, y> alg before filling the transition tables. *
13 * See init_moves(). */
14
15static Cube move_array[NMOVES];
16
17static char equiv_alg_string[100][NMOVES] = {
18 [NULLMOVE] = "",
19
20 [U] = " U ",
21 [U2] = " UU ",
22 [U3] = " UUU ",
23 [D] = " xx U xx ",
24 [D2] = " xx UU xx ",
25 [D3] = " xx UUU xx ",
26 [R] = " yx U xxxyyy ",
27 [R2] = " yx UU xxxyyy ",
28 [R3] = " yx UUU xxxyyy ",
29 [L] = " yyyx U xxxy ",
30 [L2] = " yyyx UU xxxy ",
31 [L3] = " yyyx UUU xxxy ",
32 [F] = " x U xxx ",
33 [F2] = " x UU xxx ",
34 [F3] = " x UUU xxx ",
35 [B] = " xxx U x ",
36 [B2] = " xxx UU x ",
37 [B3] = " xxx UUU x ",
38
39 [Uw] = " xx U xx y ",
40 [Uw2] = " xx UU xx yy ",
41 [Uw3] = " xx UUU xx yyy ",
42 [Dw] = " U yyy ",
43 [Dw2] = " UU yy ",
44 [Dw3] = " UUU y ",
45 [Rw] = " yyyx U xxxy x ",
46 [Rw2] = " yyyx UU xxxy xx ",
47 [Rw3] = " yyyx UUU xxxy xxx ",
48 [Lw] = " yx U xxxyyy xxx ",
49 [Lw2] = " yx UU xxxyyy xx ",
50 [Lw3] = " yx UUU xxxyyy x ",
51 [Fw] = " xxx U x yxxxyyy ",
52 [Fw2] = " xxx UU x yxxyyy ",
53 [Fw3] = " xxx UUU x yxyyy ",
54 [Bw] = " x U xxx yxyyy ",
55 [Bw2] = " x UU xxx yxxyyy ",
56 [Bw3] = " x UUU xxx yxxxyyy ",
57
58 [M] = " yx U xx UUU yxyyy ",
59 [M2] = " yx UU xx UU xxxy ",
60 [M3] = " yx UUU xx U yxxxy ",
61 [S] = " x UUU xx U yyyx ",
62 [S2] = " x UU xx UU yyx ",
63 [S3] = " x U xx UUU yx ",
64 [E] = " U xx UUU xxyyy ",
65 [E2] = " UU xx UU xxyy ",
66 [E3] = " UUU xx U xxy ",
67
68 [x] = " x ",
69 [x2] = " xx ",
70 [x3] = " xxx ",
71 [y] = " y ",
72 [y2] = " yy ",
73 [y3] = " yyy ",
74 [z] = " yyy x y ",
75 [z2] = " yy xx ",
76 [z3] = " y x yyy "
77};
78
79
80/* Public functions **********************************************************/
81
82void
83apply_alg(Alg *alg, Cube *cube)
84{
85 Cube aux;
86 int i;
87
88 copy_cube(cube, &aux);
89 make_solved(cube);
90
91 for (i = 0; i < alg->len; i++)
92 if (alg->inv[i])
93 apply_move(alg->move[i], cube);
94
95 invert_cube(cube);
96 compose(&aux, cube);
97
98 for (i = 0; i < alg->len; i++)
99 if (!alg->inv[i])
100 apply_move(alg->move[i], cube);
101}
102
103void
104apply_move(Move m, Cube *cube)
105{
106 compose(&move_array[m], cube);
107}
108
109void
110apply_move_centers(Move m, Cube *cube)
111{
112 compose_centers(&move_array[m], cube);
113}
114
115void
116apply_move_corners(Move m, Cube *cube)
117{
118 compose_corners(&move_array[m], cube);
119}
120
121void
122apply_move_edges(Move m, Cube *cube)
123{
124 compose_edges(&move_array[m], cube);
125}
126
127Alg *
128cleanup(Alg *alg)
129{
130 int i, j, k, b[2], n, L;
131 Move bb, m;
132 Alg *ret;
133
134 ret = new_alg("");
135 cleanup_aux(alg, ret, false);
136 cleanup_aux(alg, ret, true);
137
138 do {
139 for (i = 0, j = 0, n = 0; i < ret->len; i = j) {
140 if (ret->move[i] > B3) {
141 ret->move[n] = ret->move[i];
142 ret->inv[n] = ret->inv[i];
143 n++;
144 j++;
145 continue;
146 }
147
148 bb = 1 + ((base_move(ret->move[i]) - 1)/6)*6;
149 while (j < ret->len &&
150 ret->move[j] <= B3 &&
151 ret->inv[j] == ret->inv[i] &&
152 1 + ((base_move(ret->move[j]) - 1)/6)*6 == bb)
153 j++;
154
155 for (k = i, b[0] = 0, b[1] = 0; k < j; k++) {
156 m = ret->move[k];
157 if (base_move(m) == bb)
158 b[0] = (b[0]+1+m-base_move(m)) % 4;
159 else
160 b[1] = (b[1]+1+m-base_move(m)) % 4;
161 }
162
163 for (k = 0; k < 2; k++) {
164 if (b[k] != 0) {
165 ret->move[n] = bb + b[k] - 1 + 3*k;
166 ret->inv[n] = ret->inv[i];
167 n++;
168 }
169 }
170 }
171
172 L = ret->len;
173 ret->len = n;
174 } while (L != n);
175
176 return ret;
177}
178
179static void
180cleanup_aux(Alg *alg, Alg *ret, bool inv)
181{
182 int i, j;
183 Cube c, d;
184 Move m;
185 Alg *equiv_alg;
186
187 make_solved(&c);
188 for (i = 0; i < alg->len; i++) {
189 if (alg->inv[i] != inv)
190 continue;
191
192 equiv_alg = new_alg(equiv_alg_string[alg->move[i]]);
193
194 for (j = 0; j < equiv_alg->len; j++)
195 if (equiv_alg->move[j] == U)
196 append_move(ret, 3 * c.xp[U_center] + 1, inv);
197 else
198 apply_move(equiv_alg->move[j], &c);
199
200 free_alg(equiv_alg);
201 }
202
203 m = NULLMOVE;
204 switch (c.xp[F_center]) {
205 case U_center:
206 m = x3;
207 break;
208 case D_center:
209 m = x;
210 break;
211 case R_center:
212 m = y;
213 break;
214 case L_center:
215 m = y3;
216 break;
217 case B_center:
218 if (c.xp[U_center] == U_center)
219 m = y2;
220 else
221 m = x2;
222 break;
223 default:
224 break;
225 }
226
227 make_solved(&d);
228 apply_move(m, &d);
229 if (m != NULLMOVE)
230 append_move(ret, m, inv);
231
232 m = NULLMOVE;
233 if (c.xp[U_center] == d.xp[D_center]) {
234 m = z2;
235 } else if (c.xp[U_center] == d.xp[R_center]) {
236 m = z3;
237 } else if (c.xp[U_center] == d.xp[L_center]) {
238 m = z;
239 }
240 if (m != NULLMOVE)
241 append_move(ret, m, inv);
242}
243
244void
245init_moves() {
246 static bool initialized = false;
247 if (initialized)
248 return;
249 initialized = true;
250
251 Move m;
252 Alg *equiv_alg[NMOVES];
253
254 static const Cube mcu = {
255 .ep = { UR, UF, UL, UB, DF, DL, DB, DR, FR, FL, BL, BR },
256 .cp = { UBR, UFR, UFL, UBL, DFR, DFL, DBL, DBR },
257 };
258 static const Cube mcx = {
259 .ep = { DF, FL, UF, FR, DB, BL, UB, BR, DR, DL, UL, UR },
260 .eo = { [UF] = 1, [UB] = 1, [DF] = 1, [DB] = 1 },
261 .cp = { DFR, DFL, UFL, UFR, DBR, DBL, UBL, UBR },
262 .co = { [UFR] = 2, [UBR] = 1, [UFL] = 1, [UBL] = 2,
263 [DBR] = 2, [DFR] = 1, [DBL] = 1, [DFL] = 2 },
264 .xp = { F_center, B_center, R_center,
265 L_center, D_center, U_center },
266 };
267 static const Cube mcy = {
268 .ep = { UR, UF, UL, UB, DR, DF, DL, DB, BR, FR, FL, BL },
269 .eo = { [FR] = 1, [FL] = 1, [BL] = 1, [BR] = 1 },
270 .cp = { UBR, UFR, UFL, UBL, DBR, DFR, DFL, DBL },
271 .xp = { U_center, D_center, B_center,
272 F_center, R_center, L_center },
273 };
274
275 move_array[U] = mcu;
276 move_array[x] = mcx;
277 move_array[y] = mcy;
278
279 for (m = 0; m < NMOVES; m++)
280 equiv_alg[m] = new_alg(equiv_alg_string[m]);
281
282 for (m = 0; m < NMOVES; m++) {
283 switch (m) {
284 case NULLMOVE:
285 make_solved(&move_array[m]);
286 break;
287 case U:
288 case x:
289 case y:
290 break;
291 default:
292 make_solved(&move_array[m]);
293 apply_alg(equiv_alg[m], &move_array[m]);
294 break;
295 }
296 }
297
298 for (m = 0; m < NMOVES; m++)
299 free_alg(equiv_alg[m]);
300}
301
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 @@
1#ifndef MOVES_H
2#define MOVES_H
3
4#include "alg.h"
5#include "cube.h"
6#include "env.h"
7
8void apply_alg(Alg *alg, Cube *cube);
9void apply_move(Move m, Cube *cube);
10void apply_move_centers(Move m, Cube *cube);
11void apply_move_corners(Move m, Cube *cube);
12void apply_move_edges(Move m, Cube *cube);
13Alg * cleanup(Alg *alg);
14
15void init_moves();
16
17#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 @@
1#define MOVESETS_C
2
3#include "movesets.h"
4
5static bool allowed_HTM(Move m);
6static bool allowed_URF(Move m);
7static bool allowed_eofb(Move m);
8static bool allowed_drud(Move m);
9static bool allowed_htr(Move m);
10static bool can_append_HTM(Move l2, Move l1, Move m);
11static bool can_append_HTM_cached(Alg *alg, Move m, bool inverse);
12static bool cancel_niss_HTM_cached(Alg *alg);
13static void init_can_append_HTM();
14
15Moveset
16moveset_HTM = {
17 .name = "HTM",
18 .allowed = allowed_HTM,
19 .can_append = can_append_HTM_cached,
20 .cancel_niss = cancel_niss_HTM_cached,
21};
22
23Moveset
24moveset_URF = {
25 .name = "URF",
26 .allowed = allowed_URF,
27 .can_append = can_append_HTM_cached,
28 .cancel_niss = cancel_niss_HTM_cached,
29};
30
31Moveset
32moveset_eofb = {
33 .name = "eofb",
34 .allowed = allowed_eofb,
35 .can_append = can_append_HTM_cached,
36 .cancel_niss = cancel_niss_HTM_cached,
37};
38
39Moveset
40moveset_drud = {
41 .name = "drud",
42 .allowed = allowed_drud,
43 .can_append = can_append_HTM_cached,
44 .cancel_niss = cancel_niss_HTM_cached,
45};
46
47Moveset
48moveset_htr = {
49 .name = "htr",
50 .allowed = allowed_htr,
51 .can_append = can_append_HTM_cached,
52 .cancel_niss = cancel_niss_HTM_cached,
53};
54
55Moveset *
56all_movesets[] = {
57 &moveset_HTM,
58 &moveset_URF,
59 &moveset_eofb,
60 &moveset_drud,
61 &moveset_htr,
62 NULL
63};
64
65static uint64_t can_append_HTM_mask[NMOVES][NMOVES];
66
67static bool
68allowed_HTM(Move m)
69{
70 return m >= U && m <= B3;
71}
72
73static bool
74allowed_URF(Move m)
75{
76 Move b = base_move(m);
77
78 return b == U || b == R || b == F;
79}
80
81static bool
82allowed_eofb(Move m)
83{
84 Move b = base_move(m);
85
86 return b == U || b == D || b == R || b == L ||
87 ((b == F || b == B) && m == b+1);
88}
89
90static bool
91allowed_drud(Move m)
92{
93 Move b = base_move(m);
94
95 return b == U || b == D ||
96 ((b == R || b == L || b == F || b == B) && m == b + 1);
97}
98
99static bool
100allowed_htr(Move m)
101{
102 Move b = base_move(m);
103
104 return moveset_HTM.allowed(m) && m == b + 1;
105}
106
107static bool
108can_append_HTM(Move l2, Move l1, Move m)
109{
110 bool cancel, cancel_last, cancel_swap;
111
112 cancel_last = l1 != NULLMOVE && base_move(l1) == base_move(m);
113 cancel_swap = l2 != NULLMOVE && base_move(l2) == base_move(m);
114 cancel = cancel_last || (commute(l1, l2) && cancel_swap);
115
116 return !cancel;
117}
118
119static bool
120can_append_HTM_cached(Alg *alg, Move m, bool inverse)
121{
122 Move *moves, l1, l2;
123 uint64_t mbit;
124 int n;
125
126 if (inverse) {
127 moves = alg->move_inverse;
128 n = alg->len_inverse;
129 } else {
130 moves = alg->move_normal;
131 n = alg->len_normal;
132 }
133
134 l1 = n > 0 ? moves[n-1] : NULLMOVE;
135 l2 = n > 1 ? moves[n-2] : NULLMOVE;
136
137 mbit = ((uint64_t)1) << m;
138
139 return can_append_HTM_mask[l2][l1] & mbit;
140}
141
142static bool
143cancel_niss_HTM_cached(Alg *alg)
144{
145 Move i1, i2;
146 int n;
147 bool can_first, can_swap;
148
149 n = alg->len_inverse;
150 i1 = n > 0 ? alg->move_inverse[n-1] : NULLMOVE;
151 i2 = n > 1 ? alg->move_inverse[n-2] : NULLMOVE;
152
153 can_first = can_append_HTM_cached(alg, inverse_move(i1), false);
154 can_swap = can_append_HTM_cached(alg, inverse_move(i2), false);
155
156 return can_first && (!commute(i1, i2) || can_swap);
157}
158
159static void
160init_can_append_HTM()
161{
162 Move l2, l1, m;
163
164 for (l1 = 0; l1 < NMOVES; l1++)
165 for (l2 = 0; l2 < NMOVES; l2++)
166 for (m = 0; m < NMOVES; m++)
167 if (can_append_HTM(l2, l1, m))
168 can_append_HTM_mask[l2][l1]
169 |= (((uint64_t)1) << m);
170}
171
172void
173init_moveset(Moveset *ms)
174{
175 int j;
176 Move m;
177
178 for (j = 0, m = U; m < NMOVES; m++)
179 if (ms->allowed(m))
180 ms->sorted_moves[j++] = m;
181 ms->sorted_moves[j] = NULLMOVE;
182
183/* TODO: should be here? maybe just init all movesets together anyway... */
184 init_can_append_HTM();
185}
186
187void
188init_movesets()
189{
190 int i;
191
192 for (i = 0; all_movesets[i] != NULL; i++)
193 init_moveset(all_movesets[i]);
194}
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 @@
1#ifndef MOVESETS_H
2#define MOVESETS_H
3
4#include "alg.h"
5
6void init_moveset(Moveset *);
7void init_movesets();
8
9extern Moveset moveset_HTM;
10extern Moveset moveset_URF;
11extern Moveset moveset_eofb;
12extern Moveset moveset_drud;
13extern Moveset moveset_htr;
14
15#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 @@
1#define PRUNING_C
2
3#include "pruning.h"
4
5#define ENTRIES_PER_GROUP (2*sizeof(entry_group_t))
6#define ENTRIES_PER_GROUP_COMPACT (4*sizeof(entry_group_t))
7
8static int findchunk(PruneData *pd, int nchunks, uint64_t i);
9static void genptable_bfs(PruneData *pd, int d, int nt, int nc);
10static void genptable_fixnasty(PruneData *pd, int d, int nthreads);
11static void * instance_bfs(void *arg);
12static void * instance_fixnasty(void *arg);
13static void ptable_update(PruneData *pd, uint64_t ind, int m);
14static bool read_ptable_file(PruneData *pd);
15static bool write_ptable_file(PruneData *pd);
16
17PruneData *active_pd[256];
18
19int
20findchunk(PruneData *pd, int nchunks, uint64_t i)
21{
22 uint64_t chunksize;
23
24 chunksize = pd->coord->max / (uint64_t)nchunks;
25 chunksize += ENTRIES_PER_GROUP - (chunksize % ENTRIES_PER_GROUP);
26
27 return MIN(nchunks-1, (int)(i / chunksize));
28}
29
30PruneData *
31genptable(PruneData *pd, int nthreads)
32{
33 int d, nchunks, i, maxv;
34 uint64_t oldn;
35
36 for (i = 0; active_pd[i] != NULL; i++) {
37 if (active_pd[i]->coord == pd->coord &&
38 active_pd[i]->moveset == pd->moveset &&
39 active_pd[i]->compact == pd->compact)
40 return active_pd[i];
41 }
42
43 init_moveset(pd->moveset);
44 gen_coord(pd->coord);
45
46 pd->ptable = malloc(ptablesize(pd) * sizeof(entry_group_t));
47
48 if (read_ptable_file(pd))
49 goto genptable_done;
50
51 if (nthreads < 4) {
52 fprintf(stderr,
53 "--- Warning ---\n"
54 "You are using only %d threads to generate the pruning"
55 "tables. This can take a while.\n"
56 "Unless you did this intentionally, you should re-run"
57 "this command with `-t 4' or more.\n"
58 "---------------\n\n", nthreads
59 );
60 }
61
62 nchunks = MIN(ptablesize(pd), 100000);
63 fprintf(stderr, "Generating pt_%s_%s with %d threads\n",
64 pd->coord->name, pd->moveset->name, nthreads);
65
66 memset(pd->ptable, ~(uint8_t)0, ptablesize(pd)*sizeof(entry_group_t));
67 for (i = 0; i < 16; i++)
68 pd->count[i] = 0;
69
70 ptable_update(pd, 0, 0);
71 pd->n = 1;
72 oldn = 0;
73 genptable_fixnasty(pd, 0, nthreads);
74 fprintf(stderr, "Depth %d done, generated %"
75 PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
76 0, pd->n - oldn, pd->n, pd->coord->max);
77 oldn = pd->n;
78 pd->count[0] = pd->n;
79
80 maxv = pd->compact ? MIN(15, pd->base + 4) : 15;
81 for (d = 0; d < maxv && pd->n < pd->coord->max; d++) {
82 genptable_bfs(pd, d, nthreads, nchunks);
83 genptable_fixnasty(pd, d+1, nthreads);
84 fprintf(stderr, "Depth %d done, generated %"
85 PRIu64 "\t(%" PRIu64 "/%" PRIu64 ")\n",
86 d+1, pd->n - oldn, pd->n, pd->coord->max);
87 pd->count[d+1] = pd->n - oldn;
88 oldn = pd->n;
89 }
90 if (pd->compact)
91 fprintf(stderr, "Compact table, values above "
92 "%d are inaccurate.\n", maxv-1);
93 fprintf(stderr, "Pruning table generated!\n");
94
95 if (!write_ptable_file(pd))
96 fprintf(stderr, "Error writing ptable file\n");
97
98genptable_done:
99 for (i = 0; active_pd[i] != NULL; i++);
100 return active_pd[i] = pd;
101}
102
103static void
104genptable_bfs(PruneData *pd, int d, int nthreads, int nchunks)
105{
106 int i;
107 pthread_t t[nthreads];
108 ThreadDataGenpt td[nthreads];
109 pthread_mutex_t *mtx[nchunks], *upmtx;
110
111 upmtx = malloc(sizeof(pthread_mutex_t));
112 pthread_mutex_init(upmtx, NULL);
113 for (i = 0; i < nchunks; i++) {
114 mtx[i] = malloc(sizeof(pthread_mutex_t));
115 pthread_mutex_init(mtx[i], NULL);
116 }
117
118 for (i = 0; i < nthreads; i++) {
119 td[i].thid = i;
120 td[i].nthreads = nthreads;
121 td[i].pd = pd;
122 td[i].d = d;
123 td[i].nchunks = nchunks;
124 td[i].mutex = mtx;
125 td[i].upmutex = upmtx;
126 pthread_create(&t[i], NULL, instance_bfs, &td[i]);
127 }
128
129 for (i = 0; i < nthreads; i++)
130 pthread_join(t[i], NULL);
131
132 free(upmtx);
133 for (i = 0; i < nchunks; i++)
134 free(mtx[i]);
135}
136
137static void
138genptable_fixnasty(PruneData *pd, int d, int nthreads)
139{
140 int i;
141 pthread_t t[nthreads];
142 ThreadDataGenpt td[nthreads];
143 pthread_mutex_t *upmtx;
144
145 if (pd->coord->type != SYMCOMP_COORD)
146 return;
147
148 upmtx = malloc(sizeof(pthread_mutex_t));
149 pthread_mutex_init(upmtx, NULL);
150 for (i = 0; i < nthreads; i++) {
151 td[i].thid = i;
152 td[i].nthreads = nthreads;
153 td[i].pd = pd;
154 td[i].d = d;
155 td[i].upmutex = upmtx;
156 pthread_create(&t[i], NULL, instance_fixnasty, &td[i]);
157 }
158
159 for (i = 0; i < nthreads; i++)
160 pthread_join(t[i], NULL);
161
162 free(upmtx);
163}
164
165static void *
166instance_bfs(void *arg)
167{
168 ThreadDataGenpt *td;
169 uint64_t i, ii, blocksize, rmin, rmax, updated;
170 int j, pval, ichunk, oldc, newc;
171 Move *ms;
172
173 td = (ThreadDataGenpt *)arg;
174 ms = td->pd->moveset->sorted_moves;
175 blocksize = td->pd->coord->max / (uint64_t)td->nthreads;
176 rmin = ((uint64_t)td->thid) * blocksize;
177 rmax = td->thid == td->nthreads - 1 ?
178 td->pd->coord->max :
179 ((uint64_t)td->thid + 1) * blocksize;
180
181 if (td->pd->compact) {
182 if (td->d <= td->pd->base) {
183 oldc = 1;
184 newc = 1;
185 } else {
186 oldc = td->d - td->pd->base;
187 newc = td->d - td->pd->base;
188 }
189 } else {
190 oldc = td->d;
191 newc = td->d + 1;
192 }
193
194 updated = 0;
195 for (i = rmin; i < rmax; i++) {
196 ichunk = findchunk(td->pd, td->nchunks, i);
197 pthread_mutex_lock(td->mutex[ichunk]);
198 pval = ptableval(td->pd, i);
199 pthread_mutex_unlock(td->mutex[ichunk]);
200 if (pval == oldc) {
201 for (j = 0; ms[j] != NULLMOVE; j++) {
202 ii = move_coord(td->pd->coord, ms[j], i, NULL);
203 ichunk = findchunk(td->pd, td->nchunks, ii);
204 pthread_mutex_lock(td->mutex[ichunk]);
205 pval = ptableval(td->pd, ii);
206 if (pval > newc) {
207 ptable_update(td->pd, ii, newc);
208 updated++;
209 }
210 pthread_mutex_unlock(td->mutex[ichunk]);
211 }
212 if (td->pd->compact && td->d <= td->pd->base) {
213 ichunk = findchunk(td->pd, td->nchunks, i);
214 pthread_mutex_lock(td->mutex[ichunk]);
215 ptable_update(td->pd, i, 0);
216 pthread_mutex_unlock(td->mutex[ichunk]);
217 }
218 }
219 }
220
221 pthread_mutex_lock(td->upmutex);
222 td->pd->n += updated;
223 pthread_mutex_unlock(td->upmutex);
224
225 return NULL;
226}
227
228static void *
229instance_fixnasty(void *arg)
230{
231 ThreadDataGenpt *td;
232 uint64_t i, ii, blocksize, rmin, rmax, updated, ss, M;
233 int j, oldc;
234 Trans t;
235
236 td = (ThreadDataGenpt *)arg;
237
238 /* We know type = SYMCOMP_COORD */
239 M = td->pd->coord->base[1]->max;
240 blocksize = (td->pd->coord->base[0]->max / td->nthreads) * M;
241 rmin = ((uint64_t)td->thid) * blocksize;
242 rmax = td->thid == td->nthreads - 1 ?
243 td->pd->coord->max :
244 ((uint64_t)td->thid + 1) * blocksize;
245
246 if (td->pd->compact) {
247 if (td->d <= td->pd->base)
248 oldc = 1;
249 else
250 oldc = td->d - td->pd->base;
251 } else {
252 oldc = td->d;
253 }
254
255 updated = 0;
256 for (i = rmin; i < rmax; i++) {
257 if (ptableval(td->pd, i) == oldc) {
258 ss = td->pd->coord->base[0]->selfsim[i/M];
259 for (j = 0; j < td->pd->coord->base[0]->tgrp->n; j++) {
260 t = td->pd->coord->base[0]->tgrp->t[j];
261 if (t == uf || !(ss & ((uint64_t)1<<t)))
262 continue;
263 ii = trans_coord(td->pd->coord, t, i);
264 if (ptableval(td->pd, ii) > oldc) {
265 ptable_update(td->pd, ii, oldc);
266 updated++;
267 }
268 }
269 }
270 }
271
272 pthread_mutex_lock(td->upmutex);
273 td->pd->n += updated;
274 pthread_mutex_unlock(td->upmutex);
275
276 return NULL;
277}
278
279void
280print_ptable(PruneData *pd)
281{
282 uint64_t i;
283
284 printf("Table %s_%s\n", pd->coord->name, pd->moveset->name);
285
286 if (pd->compact) {
287 printf("Compract table with base value: %d\n", pd->base);
288 printf("Values above %d are inaccurate.\n", pd->base + 3);
289 }
290
291 for (i = 0; i < 16; i++)
292 printf("%2" PRIu64 "\t%10" PRIu64 "\n", i, pd->count[i]);
293}
294
295uint64_t
296ptablesize(PruneData *pd)
297{
298 uint64_t e;
299
300 e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
301
302 return (pd->coord->max + e - 1) / e;
303}
304
305static void
306ptable_update(PruneData *pd, uint64_t ind, int n)
307{
308 int sh;
309 entry_group_t f, mask;
310 uint64_t i, e, b;
311
312 e = pd->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP;
313 b = pd->compact ? 2 : 4;
314 f = pd->compact ? 3 : 15;
315
316 sh = b * (ind % e);
317 mask = f << sh;
318 i = ind / e;
319
320 pd->ptable[i] &= ~mask;
321 pd->ptable[i] |= (((entry_group_t)n) & f) << sh;
322}
323
324int
325ptableval(PruneData *pd, uint64_t ind)
326{
327 int sh;
328 uint64_t e;
329 entry_group_t m;
330
331 if (pd->compact) {
332 e = ENTRIES_PER_GROUP_COMPACT;
333 m = 3;
334 sh = (ind % e) * 2;
335 } else {
336 e = ENTRIES_PER_GROUP;
337 m = 15;
338 sh = (ind % e) * 4;
339 }
340
341 return (pd->ptable[ind/e] & (m << sh)) >> sh;
342}
343
344static bool
345read_ptable_file(PruneData *pd)
346{
347 init_env();
348
349 FILE *f;
350 char fname[strlen(tabledir)+256];
351 int i;
352 uint64_t r;
353
354 strcpy(fname, tabledir);
355 strcat(fname, "/pt_");
356 strcat(fname, pd->coord->name);
357 strcat(fname, "_");
358 strcat(fname, pd->moveset->name);
359
360 if ((f = fopen(fname, "rb")) == NULL)
361 return false;
362
363 r = fread(&(pd->base), sizeof(int), 1, f);
364 for (i = 0; i < 16; i++)
365 r += fread(&(pd->count[i]), sizeof(uint64_t), 1, f);
366 r += fread(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
367
368 fclose(f);
369
370 return r == 17 + ptablesize(pd);
371}
372
373static bool
374write_ptable_file(PruneData *pd)
375{
376 init_env();
377
378 FILE *f;
379 char fname[strlen(tabledir)+256];
380 int i;
381 uint64_t w;
382
383 strcpy(fname, tabledir);
384 strcat(fname, "/pt_");
385 strcat(fname, pd->coord->name);
386 strcat(fname, "_");
387 strcat(fname, pd->moveset->name);
388
389 if ((f = fopen(fname, "wb")) == NULL)
390 return false;
391
392 w = fwrite(&(pd->base), sizeof(int), 1, f);
393 for (i = 0; i < 16; i++)
394 w += fwrite(&(pd->count[i]), sizeof(uint64_t), 1, f);
395 w += fwrite(pd->ptable, sizeof(entry_group_t), ptablesize(pd), f);
396 fclose(f);
397
398 return w == 17 + ptablesize(pd);
399}
400
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 @@
1#ifndef PRUNING_H
2#define PRUNING_H
3
4#include "coord.h"
5#include "movesets.h"
6
7void free_pd(PruneData *pd);
8PruneData * genptable(PruneData *data, int nthreads);
9void print_ptable(PruneData *pd);
10uint64_t ptablesize(PruneData *pd);
11int ptableval(PruneData *pd, uint64_t ind);
12
13extern PruneData *active_pd[256];
14
15#endif
16
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 @@
1#define SHELL_C
2
3#include "shell.h"
4
5static void cleanwhitespaces(char *line);
6static int parseline(char *line, char **v);
7
8bool
9checkfiles()
10{
11 /* TODO: add more checks (other files, use checksum...) */
12 /* How to check for pruning tables with new method? */
13 /* Solution: use list of steps */
14 /*
15 char fname[strlen(tabledir)+100];
16 int i;
17
18 for (i = 0; all_pd[i] != NULL; i++) {
19 strcpy(fname, tabledir);
20 strcat(fname, "/");
21 strcat(fname, all_pd[i]->filename);
22 if ((f = fopen(fname, "rb")) == NULL)
23 return false;
24 else
25 fclose(f);
26 }
27 */
28
29 return true;
30}
31
32static void
33cleanwhitespaces(char *line)
34{
35 char *i;
36
37 for (i = line; *i != 0; i++)
38 if (*i == '\t' || *i == '\n')
39 *i = ' ';
40}
41
42/* This function assumes that **v is large enough */
43static int
44parseline(char *line, char **v)
45{
46 char *t;
47 int n = 0;
48
49 cleanwhitespaces(line);
50
51 for (t = strtok(line, " "); t != NULL; t = strtok(NULL, " "))
52 strcpy(v[n++], t);
53
54 return n;
55}
56
57void
58exec_args(int c, char **v)
59{
60 int i;
61 char line[MAXLINELEN];
62 Command *cmd = NULL;
63 CommandArgs *args;
64 Alg *scramble;
65
66 for (i = 0; commands[i] != NULL; i++)
67 if (!strcmp(v[0], commands[i]->name))
68 cmd = commands[i];
69
70 if (cmd == NULL) {
71 fprintf(stderr, "%s: command not found\n", v[0]);
72 return;
73 }
74
75 args = cmd->parse_args(c-1, &v[1]);
76 if (!args->success) {
77 fprintf(stderr, "usage: %s\n", cmd->usage);
78 return;
79 }
80
81 if (args->scrstdin) {
82 while (true) {
83 if (fgets(line, MAXLINELEN, stdin) == NULL) {
84 clearerr(stdin);
85 break;
86 }
87
88 scramble = new_alg(line);
89
90 printf(">>> Line: %s", line);
91
92 if (scramble != NULL && scramble->len > 0) {
93 args->scramble = scramble;
94 cmd->exec(args);
95 free_alg(scramble);
96 args->scramble = NULL;
97 }
98 }
99 } else {
100 cmd->exec(args);
101 }
102 free_args(args);
103}
104
105void
106launch(bool batchmode)
107{
108 int i, shell_argc;
109 char line[MAXLINELEN], **shell_argv;
110
111 shell_argv = malloc(MAXNTOKENS * sizeof(char *));
112 for (i = 0; i < MAXNTOKENS; i++)
113 shell_argv[i] = malloc((MAXTOKENLEN+1) * sizeof(char));
114
115 if (!batchmode) {
116 fprintf(stderr, "Welcome to Nissy "VERSION".\n"
117 "Type \"commands\" for a list of commands.\n");
118 }
119
120 while (true) {
121 if (!batchmode) {
122 fprintf(stdout, "nissy-# ");
123 }
124
125 if (fgets(line, MAXLINELEN, stdin) == NULL)
126 break;
127
128 if (batchmode) {
129 printf(">>>\n"
130 ">>> Executing command: %s"
131 ">>>\n", line);
132 }
133
134 shell_argc = parseline(line, shell_argv);
135
136 if (shell_argc > 0)
137 exec_args(shell_argc, shell_argv);
138 }
139
140 for (i = 0; i < MAXNTOKENS; i++)
141 free(shell_argv[i]);
142 free(shell_argv);
143}
144
145#ifndef TEST
146int
147main(int argc, char *argv[])
148{
149 char *closing_cmd[1] = { "freemem" };
150
151 init_env();
152 init_trans();
153
154 if (!checkfiles()) {
155 fprintf(stderr,
156 "--- Warning ---\n"
157 "Some pruning tables are missing or unreadable\n"
158 "You can generate them with `nissy gen'.\n"
159 "---------------\n\n"
160 );
161 }
162
163 if (argc > 1) {
164 if (!strcmp(argv[1], "-b")) {
165 launch(true);
166 } else {
167 exec_args(argc-1, &argv[1]);
168 }
169 } else {
170 launch(false);
171 }
172
173 exec_args(1, closing_cmd);
174
175 return 0;
176}
177#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 @@
1#ifndef SHELL_H
2#define SHELL_H
3
4#include "commands.h"
5
6#define MAXLINELEN 10000
7#define MAXTOKENLEN 255
8#define MAXNTOKENS 255
9
10bool checkfiles();
11void exec_args(int c, char **v);
12void launch(bool batchmode);
13
14#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 @@
1#define SOLVE_C
2
3#include "solve.h"
4
5void
6dfs(DfsArg *arg, Solver *solver, Threader *threader)
7{
8 int i;
9 DfsArg newarg;
10 Alg *sol;
11 Move m;
12
13 if (arg->current_alg->len > arg->d)
14 return;
15
16 if (solver->is_solved(solver->param, arg->cubedata)) {
17/* TODO: the "all" option should be re-implemented as setting
18validate to null */
19
20/* TODO: we also have to check if cancel with NISS;
21we can't because we have no access to the s->final field
22this should be done by the step's validator? */
23 sol = solver->validate_solution(solver->param,arg->current_alg);
24 bool accepted = sol != NULL;
25 bool too_short = arg->current_alg->len != arg->d;
26
27 if (accepted && !too_short) {
28/* TODO: arg->t got lost in refactoring */
29/* transform_alg(inverse_trans(arg->t), sol);*/
30 if (arg->opts->verbose)
31 print_alg(sol, false);
32 threader->append_sol(sol, arg->threaddata);
33 }
34 return;
35 }
36
37 if (arg->current_alg->len == arg->d)
38 return;
39
40/* TODO: do not alloc */
41 newarg.cubedata = solver->alloc_cubedata(solver->param);
42 for (i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
43 m = solver->moveset->sorted_moves[i];
44 if (solver->moveset->can_append(arg->current_alg, m, arg->niss)
45 && compare_last(arg->current_alg, m, arg->niss) >= 0) {
46 append_move(arg->current_alg, m, arg->niss);
47
48 solver->copy_cubedata(
49 solver->param, arg->cubedata, newarg.cubedata);
50 newarg.threaddata = arg->threaddata;
51 newarg.opts = arg->opts;
52 newarg.d = arg->d;
53 newarg.niss = arg->niss;
54 newarg.current_alg = arg->current_alg;
55 if (!solver->move_check_stop(
56 solver->param, &newarg, threader))
57 dfs(&newarg, solver, threader);
58
59 remove_last_move(arg->current_alg);
60 }
61 }
62 solver->free_cubedata(solver->param, newarg.cubedata);
63
64 if (arg->opts->can_niss && !arg->niss &&
65 solver->niss_makes_sense(
66 solver->param, arg->cubedata, arg->current_alg)) {
67 solver->invert_cube(solver->param, arg->cubedata);
68 arg->niss = true;
69 dfs(arg, solver, threader);
70 }
71}
72
73AlgList *
74solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
75{
76 int i, d, optimal;
77 bool ready[MAX_SOLVERS], stop, one_ready;
78 DfsArg arg[MAX_SOLVERS];
79 AlgList *sols;
80
81 one_ready = false;
82 for (i = 0; solver[i] != NULL; i++) {
83 arg[i].cubedata =
84 solver[i]->prepare_cube(solver[i]->param, cube);
85 arg[i].opts = opts;
86 ready[i] = arg[i].cubedata != NULL;
87 one_ready = one_ready || ready[i];
88 }
89
90 sols = new_alglist();
91 if (!one_ready) {
92 fprintf(stderr, "Cube not ready for solving\n");
93 return sols;
94 }
95
96 optimal = opts->max_moves;
97 stop = false;
98 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
99 if (opts->verbose)
100 fprintf(stderr, "Searching depth %d\n", d);
101
102 for (i = 0; solver[i] != NULL && !stop; i++) {
103 if (!ready[i])
104 continue;
105
106 arg[i].d = d;
107 threader->dispatch(&arg[i], sols, solver[i], threader);
108
109 if (sols->len > 0)
110 optimal = MIN(optimal, d);
111
112 stop = sols->len >= opts->max_solutions;
113 }
114 stop = stop ||
115 (opts->optimal != -1 && d >= opts->optimal + optimal);
116 }
117
118/* TODO: some cleanup (free cubedata) */
119/* TODO: actually, preparation should be done somewhere else */
120
121 return sols;
122}
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 @@
1#ifndef SOLVE_H
2#define SOLVE_H
3
4#include "moves.h"
5
6#define MAX_SOLVERS 99
7
8typedef struct dfsarg DfsArg;
9typedef struct threader Threader;
10typedef struct solver Solver;
11
12/* TODO: add solver and threader in DfsData, remove from dispatch args and similar */
13
14struct dfsarg {
15 void * cubedata;
16 void * threaddata;
17 SolveOptions * opts;
18 int d;
19 bool niss;
20 Alg * current_alg;
21};
22
23struct threader {
24 void (*append_sol)(Alg *, void *);
25 void (*dispatch)(DfsArg *, AlgList *, Solver *, Threader *);
26 int (*get_nsol)(void *);
27/* TODO: threader should have param, like solver? */
28};
29
30struct solver {
31 Moveset * moveset;
32 bool (*move_check_stop)(void *, DfsArg *, Threader *);
33 Alg * (*validate_solution)(void *, Alg *);
34 bool (*niss_makes_sense)(void *, void *, Alg *);
35/* TODO: move param to somewhere where it makes more sense */
36 void * param;
37/* TODO: the following should be part of a generic cube description */
38/* TODO: remove alloc? */
39/* TODO: revisit apply_move, maybe apply_alg? or both? */
40 void * (*alloc_cubedata)(void *);
41 void (*copy_cubedata)(void *, void *, void *);
42 void (*free_cubedata)(void *, void *);
43 void (*invert_cube)(void *, void *);
44 bool (*is_solved)(void *, void *);
45 void (*apply_move)(void *, void *, Move);
46/* TODO: remove dependence on Cube, preparation should be done before */
47 void * (*prepare_cube)(void *, Cube *);
48};
49
50void dfs(DfsArg *, Solver *, Threader *);
51/* TODO: remove dependence on Cube, preparation should be done before */
52AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *);
53
54#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 @@
1#include "solver_step.h"
2
3typedef struct {
4 Cube * cube;
5 uint64_t * val;
6 Trans * t;
7} CubeData;
8
9static void apply_move_cubedata(void *, void *, Move);
10static void init_indexes(Step *, CubeData *);
11static void * prepare_cube(void *, Cube *);
12static bool move_check_stop_eager(void *, DfsArg *, Threader *);
13static bool move_check_stop_lazy(void *, DfsArg *, Threader *);
14static bool move_check_stop_nonsol(void *, DfsArg *, Threader *);
15static bool is_solved_step(void *, void *);
16static Alg * validate_solution(void *, Alg *);
17static void * alloc_cubedata(void *);
18static void copy_cubedata(void *, void *, void *);
19static void free_cubedata(void *, void *);
20static void invert_cubedata(void *, void *);
21static bool niss_makes_sense(void *, void *, Alg *);
22static Solver * new_stepsolver_nocheckstop(Step *step);
23
24static void
25apply_move_cubedata(void *param, void *cubedata, Move m)
26{
27 Step *s = (Step *)param;
28 CubeData *data = (CubeData *)cubedata;
29
30 Trans tt;
31 for (int i = 0; i < s->n_coord; i++) {
32 Move mm = transform_move(data->t[i], m);
33 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
34 data->t[i] = transform_trans(tt, data->t[i]);
35 }
36}
37
38static void
39init_indexes(Step *step, CubeData *data)
40{
41 int i;
42 Cube moved;
43 Trans t, tt;
44
45 for (i = 0; i < step->n_coord; i++) {
46 t = step->coord_trans[i];
47 copy_cube(data->cube, &moved);
48 apply_trans(t, &moved);
49 data->val[i] = index_coord(step->coord[i], &moved, &tt);
50 data->t[i] = transform_trans(tt, t);
51 }
52}
53
54static void *
55prepare_cube(void *param, Cube *cube)
56{
57 int i;
58 Step *s;
59 CubeData *data;
60
61 s = (Step *)param;
62
63 for (i = 0; i < s->n_coord; i++) {
64 s->pd[i] = malloc(sizeof(PruneData));
65 s->pd[i]->moveset = s->moveset;
66/* TODO: check if moveset initialization works fine,
67 e.g. if there is a variable to save the initialized status
68 or if it gets initialized multiple times */
69 init_moveset(s->moveset);
70 s->pd[i]->coord = s->coord[i];
71 gen_coord(s->coord[i]);
72 s->pd[i]->compact = s->pd_compact[i];
73 s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */
74 }
75
76 data = alloc_cubedata(param);
77 data->cube = malloc(sizeof(Cube));
78 copy_cube(cube, data->cube);
79 init_indexes(s, data);
80
81 return data;
82}
83
84static bool
85move_check_stop_eager(void *param, DfsArg *arg, Threader *threader)
86{
87 int nsol;
88
89 if (move_check_stop_nonsol(param, arg, threader))
90 return true;
91
92 nsol = threader->get_nsol(arg->threaddata);
93 return nsol >= arg->opts->max_solutions;
94}
95
96static bool
97move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader)
98{
99 int nsol;
100
101 nsol = threader->get_nsol(arg->threaddata);
102 if (nsol >= arg->opts->max_solutions)
103 return true;
104
105 return move_check_stop_nonsol(param, arg, threader);
106}
107
108/* TODO: split in 2 (nissable / non-nissable) and only move cube
109 when nissable */
110static bool
111move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader)
112{
113 int i, goal, bound;
114 Move mm, lastmove;
115 Trans tt = uf;
116 CubeData *data;
117 Step *s;
118
119 s = (Step *)param;
120 data = (CubeData *)arg->cubedata;
121
122
123 bound = 0;
124 goal = arg->d - arg->current_alg->len;
125/* TODO: check if len is 0 */
126 lastmove = arg->current_alg->move[arg->current_alg->len-1];
127 for (i = 0; i < s->n_coord; i++) {
128 mm = transform_move(data->t[i], lastmove);
129 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
130 data->t[i] = transform_trans(tt, data->t[i]);
131
132 bound = MAX(bound, ptableval(s->pd[i], data->val[i]));
133 if (arg->opts->can_niss && !arg->niss)
134 bound = MIN(1, bound);
135
136 if (bound > goal) {
137 return true;
138 }
139 }
140 if (arg->opts->can_niss && !arg->niss)
141 apply_move(lastmove, data->cube);
142
143 return false;
144}
145
146static bool
147is_solved_step(void *param, void *cubedata)
148{
149 int i;
150 Step *s;
151 CubeData *data;
152
153 s = (Step *)param;
154 data = (CubeData *)cubedata;
155
156 for (i = 0; i < s->n_coord; i++)
157 if (data->val[i] != 0)
158 return false;
159
160 return true;
161}
162
163static Alg *
164validate_solution(void *param, Alg *alg)
165{
166 return ((Step *)param)->is_valid(alg);
167}
168
169static void *
170alloc_cubedata(void *param)
171{
172 Step *s;
173 CubeData *data;
174
175 s = (Step *)param;
176
177 data = malloc(sizeof(CubeData));
178 /* We do not need to allocate a cube */
179 data->val = malloc(s->n_coord * sizeof(uint64_t));
180 data->t = malloc(s->n_coord * sizeof(Trans));
181
182 return data;
183}
184
185static void
186copy_cubedata(void *param, void *src, void *dst)
187{
188 int i;
189 Step *s;
190 CubeData *newdata, *olddata;
191
192 s = (Step *)param;
193 olddata = (CubeData *)src;
194 newdata = (CubeData *)dst;
195
196/* TODO: do not copy if not nissable */
197 newdata->cube = malloc(sizeof(Cube));
198 copy_cube(olddata->cube, newdata->cube);
199 for (i = 0; i < s->n_coord; i++) {
200 newdata->val[i] = olddata->val[i];
201 newdata->t[i] = olddata->t[i];
202 }
203}
204
205static void
206free_cubedata(void *param, void *cubedata)
207{
208 CubeData *data;
209
210 data = (CubeData *)cubedata;
211
212 free(data->t);
213 free(data->val);
214 free(data->cube);
215 free(data);
216}
217
218static void
219invert_cubedata(void *param, void *cubedata)
220{
221 Step *s;
222 CubeData *data;
223
224 s = (Step *)param;
225 data = (CubeData *)cubedata;
226
227 invert_cube(data->cube);
228 init_indexes(s, data);
229}
230
231static bool
232niss_makes_sense(void *param, void *cubedata, Alg *alg)
233{
234 Step *s;
235 CubeData *data;
236
237 s = (Step *)param;
238 data = (CubeData *)cubedata;
239
240 if (s->final)
241 return false;
242
243 if (alg->len_normal == 0)
244 return true;
245
246 Move m = inverse_move(alg->move_normal[alg->len_normal-1]);
247 for (int i = 0; i < s->n_coord; i++) {
248 Move mm = transform_move(data->t[i], m);
249 uint64_t u = move_coord(s->coord[i], mm, 0, NULL);
250 if (ptableval(s->pd[i], u) > 0)
251 return true;
252 }
253
254 return false;
255}
256
257static Solver *
258new_stepsolver_nocheckstop(Step *step)
259{
260 Solver *solver;
261
262 solver = malloc(sizeof(Solver));
263
264 solver->moveset = step->moveset;
265 solver->param = step;
266
267 solver->apply_move = apply_move_cubedata;
268 solver->prepare_cube = prepare_cube;
269 solver->is_solved = is_solved_step;
270 solver->validate_solution = validate_solution;
271 solver->alloc_cubedata = alloc_cubedata;
272 solver->copy_cubedata = copy_cubedata;
273 solver->free_cubedata = free_cubedata;
274 solver->invert_cube = invert_cubedata;
275 solver->niss_makes_sense = niss_makes_sense;
276
277 return solver;
278}
279
280Solver *
281new_stepsolver_eager(Step *step)
282{
283 Solver *solver;
284
285 solver = new_stepsolver_nocheckstop(step);
286 solver->move_check_stop = move_check_stop_eager;
287
288 return solver;
289}
290
291Solver *
292new_stepsolver_lazy(Step *step)
293{
294 Solver *solver;
295
296 solver = new_stepsolver_nocheckstop(step);
297 solver->move_check_stop = move_check_stop_lazy;
298
299 return solver;
300}
301
302void
303free_stepsolver(Solver *solver)
304{
305 free(solver);
306}
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 @@
1#ifndef SOLVER_STEP_H
2#define SOLVER_STEP_H
3
4#include "cube.h"
5#include "solve.h"
6#include "steps.h"
7
8Solver *new_stepsolver_eager(Step *);
9Solver *new_stepsolver_lazy(Step *);
10void free_stepsolver(Solver *);
11
12#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 @@
1#define STEPS_C
2
3#include "steps.h"
4
5/* TODO: change all checkers to use coordinates! */
6
7bool
8check_centers(Cube *cube)
9{
10 int i;
11
12 for (i = 0; i < 6; i++)
13 if (cube->xp[i] != i)
14 return false;
15
16 return true;
17}
18
19bool
20check_coud_HTM(Cube *cube)
21{
22 int i;
23
24 for (i = 0; i < 8; i++)
25 if (cube->co[i] != 0)
26 return false;
27
28 return true;
29}
30
31bool
32check_coud_URF(Cube *cube)
33{
34 Cube c2, c3;
35
36 copy_cube(cube, &c2);
37 copy_cube(cube, &c3);
38
39 apply_move(z, &c2);
40 apply_move(x, &c3);
41
42 return check_coud_HTM(cube) ||
43 check_coud_HTM(&c2) ||
44 check_coud_HTM(&c3);
45}
46
47bool
48check_cp_HTM(Cube *cube)
49{
50 int i;
51
52 for (i = 0; i < 8; i++)
53 if (cube->cp[i] != i)
54 return false;
55
56 return true;
57}
58
59bool
60check_corners_HTM(Cube *cube)
61{
62 return check_coud_HTM(cube) && check_cp_HTM(cube);
63}
64
65bool
66check_corners_URF(Cube *cube)
67{
68 Cube c;
69 Trans i;
70
71 for (i = 0; i < NROTATIONS; i++) {
72 copy_cube(cube, &c);
73 apply_alg(rotation_alg(i), &c);
74 if (check_corners_HTM(&c))
75 return true;
76 }
77
78 return false;
79}
80
81bool
82check_cornershtr(Cube *cube)
83{
84 /* TODO (use coord) */
85 return true;
86}
87
88bool
89check_eofb(Cube *cube)
90{
91 /* TODO (use coord) */
92 return true;
93}
94
95bool
96check_drud(Cube *cube)
97{
98 /* TODO (use coord) */
99 return true;
100}
101
102bool
103check_htr(Cube *cube)
104{
105 /* TODO (check_drud(cube) and coord_htr_drud == 0) */
106 return true;
107}
108
109Alg *
110validate_singlecw_ending(Alg *alg)
111{
112 int i;
113 bool nor, inv;
114 Alg *ret;
115 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
116
117 for (i = 0; i < alg->len; i++) {
118 if (alg->inv[i]) {
119 l2i = l1i;
120 l1i = alg->move[i];
121 } else {
122 l2 = l1;
123 l1 = alg->move[i];
124 }
125 }
126
127 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2));
128 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i));
129
130 if (nor && inv) {
131 ret = new_alg("");
132 copy_alg(alg, ret);
133 } else {
134 ret = NULL;
135 }
136
137 return ret;
138}
139
140/* Public functions **********************************************************/
141
142/*
143void
144compute_ind(Step *s, Cube *cube, Movable *ind)
145{
146 int i;
147 Cube mvd;
148 Trans t, tt;
149
150 for (i = 0; i < s->n_coord; i++) {
151 t = s->coord_trans[i];
152 copy_cube(cube, &mvd);
153 apply_trans(t, &mvd);
154
155 ind[i].val = index_coord(s->coord[i], &mvd, &tt);
156 ind[i].t = transform_trans(tt, t);
157 }
158}
159*/
160
161void
162prepare_cs(ChoiceStep *cs, SolveOptions *opts)
163{
164 int i, j;
165 Step *s;
166
167 for (i = 0; cs->step[i] != NULL; i++) {
168 s = cs->step[i];
169 for (j = 0; j < s->n_coord; j++) {
170 s->pd[j] = malloc(sizeof(PruneData));
171 s->pd[j]->moveset = s->moveset;
172 s->pd[j]->coord = s->coord[j];
173 s->pd[j]->compact = s->pd_compact[j];
174 s->pd[j] = genptable(s->pd[j], opts->nthreads);
175 }
176 }
177}
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 @@
1#ifndef STEPS_H
2#define STEPS_H
3
4#include "pruning.h"
5#include "movesets.h"
6
7bool check_centers(Cube *cube);
8bool check_coud_HTM(Cube *cube);
9bool check_coud_URF(Cube *cube);
10bool check_cp_HTM(Cube *cube);
11bool check_corners_HTM(Cube *cube);
12bool check_corners_URF(Cube *cube);
13bool check_cornershtr(Cube *cube);
14bool check_eofb(Cube *cube);
15bool check_drud(Cube *cube);
16bool check_htr(Cube *cube);
17/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/
18void prepare_cs(ChoiceStep *cs, SolveOptions *opts);
19bool always_valid(Alg *alg);
20Alg * validate_singlecw_ending(Alg *alg);
21
22#ifndef STEPS_C
23
24extern char check_centers_msg[100];
25extern char check_eo_msg[100];
26extern char check_dr_msg[100];
27extern char check_htr_msg[100];
28extern char check_drany_msg[100];
29
30extern Step step_eofb_HTM;
31extern Step step_drud_HTM;
32extern Step step_drfin_drud;
33
34extern ChoiceStep optimal_HTM;
35extern ChoiceStep eoany_HTM;
36extern ChoiceStep eofb_HTM;
37extern ChoiceStep eorl_HTM;
38extern ChoiceStep eoud_HTM;
39extern ChoiceStep drany_HTM;
40extern ChoiceStep drud_HTM;
41extern ChoiceStep drrl_HTM;
42extern ChoiceStep drfb_HTM;
43extern ChoiceStep dranyfin_DR;
44extern ChoiceStep drudfin_drud;
45extern ChoiceStep drrlfin_drrl;
46extern ChoiceStep drfbfin_drfb;
47
48extern ChoiceStep *csteps[];
49
50#else
51
52char check_centers_msg[100] = "cube must be oriented (centers solved)";
53char check_eo_msg[100] = "EO must be solved on given axis";
54char check_dr_msg[100] = "DR must be solved on given axis";
55char check_htr_msg[100] = "HTR must be solved";
56char check_drany_msg[100] = "DR must be solved on at least one axis";
57
58/* Optimal after EO ******************/
59/* TODO: eofin_eo (generic), eofbfin_eofb, eorlfin_eorl, eoudfin_eoud */
60
61/* EO steps **************************/
62/* TODO: eoany_HTM (generic), eofb_HTM, eorl_HTM, eoud_HTM */
63
64Step
65step_eofb_HTM = {
66 .ready = check_centers,
67 .final = false,
68 .moveset = &moveset_HTM,
69 .n_coord = 1,
70 .coord = {&coord_eofb},
71 .coord_trans = {uf},
72 .is_valid = validate_singlecw_ending,
73};
74ChoiceStep
75eoany_HTM = {
76 .shortname = "eo",
77 .name = "EO on any axis",
78 .step = {&step_eofb_HTM, &step_eofb_HTM, &step_eofb_HTM, NULL},
79 .t = {uf, ur, fd},
80 .ready_msg = check_centers_msg,
81};
82ChoiceStep
83eofb_HTM = {
84 .shortname = "eofb",
85 .name = "EO on F/B",
86 .step = {&step_eofb_HTM, NULL},
87 .t = {uf},
88 .ready_msg = check_centers_msg,
89};
90ChoiceStep
91eorl_HTM = {
92 .shortname = "eorl",
93 .name = "EO on R/L",
94 .step = {&step_eofb_HTM, NULL},
95 .t = {ur},
96 .ready_msg = check_centers_msg,
97};
98ChoiceStep
99eoud_HTM = {
100 .shortname = "eoud",
101 .name = "EO on U/D",
102 .step = {&step_eofb_HTM, NULL},
103 .t = {fd},
104 .ready_msg = check_centers_msg,
105};
106
107/* CO steps **************************/
108/* TODO: coany_HTM (generic), cofb_HTM, corl_HTM, coud_HTM */
109/* TODO: coany_URF (generic), cofb_URF, corl_URF, coud_URF */
110
111/* Misc corner steps *****************/
112/* TODO: cornershtr_HTM, cornershtr_URF, corners_HTM, corners_URF */
113/* TODO (new): corners_drud */
114
115/* DR steps **************************/
116/* TODO: dr_eo (generic) */
117/* TODO: dr_eofb (generic), dr_eorl (generic), dr_eoud (generic) */
118/* TODO: drud_eofb, drrl_eofb, drud_eorl, drfb_eorl, drrl_eoud, drfb_eoud */
119
120Step
121step_drud_HTM = {
122 .ready = check_centers,
123 .final = false,
124 .moveset = &moveset_HTM,
125 .n_coord = 1,
126 .coord = {&coord_drud_sym16},
127 .coord_trans = {uf},
128 .is_valid = validate_singlecw_ending,
129};
130ChoiceStep
131drany_HTM = {
132 .shortname = "dr",
133 .name = "DR on any axis",
134 .step = {&step_drud_HTM, &step_drud_HTM, &step_drud_HTM, NULL},
135 .t = {uf, rf, fd},
136 .ready_msg = check_centers_msg,
137};
138ChoiceStep
139drud_HTM = {
140 .shortname = "drud",
141 .name = "DR on U/D",
142 .step = {&step_drud_HTM, NULL},
143 .t = {uf},
144 .ready_msg = check_centers_msg,
145};
146ChoiceStep
147drrl_HTM = {
148 .shortname = "drrl",
149 .name = "DR on R/L",
150 .step = {&step_drud_HTM, NULL},
151 .t = {rf},
152 .ready_msg = check_centers_msg,
153};
154ChoiceStep
155drfb_HTM = {
156 .shortname = "drfb",
157 .name = "DR on F/B",
158 .step = {&step_drud_HTM, NULL},
159 .t = {fd},
160 .ready_msg = check_centers_msg,
161};
162
163/* DR finish steps */
164Step
165step_drfin_drud = {
166 .ready = check_drud,
167 .final = true,
168 .moveset = &moveset_drud,
169 .n_coord = 1,
170 .coord = {&coord_drudfin_noE_sym16}, /* TODO: maybe no noE */
171 .coord_trans = {uf},
172 .is_valid = NULL,
173};
174ChoiceStep
175dranyfin_DR = {
176 .shortname = "drfin",
177 .name = "DR finish on any axis without breaking DR",
178 .step = {&step_drfin_drud, &step_drfin_drud,
179 &step_drfin_drud, NULL},
180 .t = {uf, rf, fd},
181 .ready_msg = check_dr_msg,
182};
183ChoiceStep
184drudfin_drud = {
185 .shortname = "drudfin",
186 .name = "DR finis on U/D without breaking DR",
187 .step = {&step_drfin_drud, NULL},
188 .t = {uf},
189 .ready_msg = check_dr_msg,
190};
191ChoiceStep
192drrlfin_drrl = {
193 .shortname = "drrlfin",
194 .name = "DR finish on R/L without breaking DR",
195 .step = {&step_drfin_drud, NULL},
196 .t = {rf},
197 .ready_msg = check_dr_msg,
198};
199ChoiceStep
200drfbfin_drfb = {
201 .shortname = "drfbfin",
202 .name = "DR finish on F/B without breaking DR",
203 .step = {&step_drfin_drud, NULL},
204 .t = {fd},
205 .ready_msg = check_dr_msg,
206};
207
208/* HTR from DR */
209/* TODO: htr_any (generic), htr_drud, htr_drrl, htr_drfb */
210
211/* HTR finish */
212/* TODO: htrfin_htr */
213
214ChoiceStep *csteps[] = {
215/* TODO: re-implement optimal
216 &optimal_HTM,
217*/
218
219 &eoany_HTM, &eofb_HTM, &eorl_HTM, &eoud_HTM,
220 &drany_HTM, &drud_HTM, &drrl_HTM, &drfb_HTM,
221 &dranyfin_DR, &drudfin_drud, &drrlfin_drrl, &drfbfin_drfb,
222
223NULL
224/* TODO:
225 &optimal_light_HTM,
226
227 &eofin_eo, &eofbfin_eofb, &eorlfin_eorl, &eoudfin_eoud,
228 &coany_HTM, &coud_HTM, &corl_HTM, &cofb_HTM,
229 &coany_URF, &coud_URF, &corl_URF, &cofb_URF,
230 &dr_eo, &dr_eofb, &dr_eorl, &dr_eoud,
231 &drud_eofb, &drrl_eofb,
232 &drud_eorl, &drfb_eorl,
233 &drfb_eoud, &drrl_eoud,
234 &htr_any, &htr_drud, &htr_drrl, &htr_drfb,
235 &htrfin_htr,
236 &cornershtr_HTM, &cornershtr_URF, &corners_HTM, &corners_URF,
237 NULL
238*/
239
240};
241
242#endif
243
244#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 @@
1#include <pthread.h>
2#include "threader_eager.h"
3
4typedef struct {
5 AlgList * sols;
6 pthread_mutex_t * sols_mutex;
7} ThreadData;
8
9typedef struct {
10 DfsArg * arg;
11 Solver * solver;
12 Threader * threader;
13 AlgList * starts;
14 AlgListNode ** node;
15 pthread_mutex_t * start_mutex;
16} ThreadInitData;
17
18static void append_sol(Alg *, void *);
19static void * instance_thread(void *);
20static void dispatch(DfsArg *, AlgList *, Solver *, Threader *);
21static AlgList * possible_starts(DfsArg *, Solver *);
22static int get_nsol(void *);
23
24Threader threader_eager = {
25 .append_sol = append_sol,
26 .dispatch = dispatch,
27 .get_nsol = get_nsol,
28};
29
30static void
31append_sol(Alg *alg, void *threaddata)
32{
33 ThreadData *td = (ThreadData *)threaddata;
34
35 pthread_mutex_lock(td->sols_mutex);
36 append_alg(td->sols, alg);
37 pthread_mutex_unlock(td->sols_mutex);
38}
39
40static AlgList *
41possible_starts(DfsArg *arg, Solver *solver)
42{
43 AlgList *ret = new_alglist();
44
45 if (solver->is_solved(solver->param, arg->cubedata)) {
46 if (arg->opts->min_moves == 0 && arg->d == 0)
47 append_sol(new_alg(""), arg->threaddata);
48 return ret;
49 }
50
51 for (int i = 0; solver->moveset->sorted_moves[i] != NULLMOVE; i++) {
52 Move m = solver->moveset->sorted_moves[i];
53 Alg *alg = new_alg("");
54 append_move(alg, m, false);
55 append_alg(ret, alg);
56 free_alg(alg);
57
58/* TODO: check if step not final */
59 if (arg->opts->can_niss) {
60 alg = new_alg("");
61 append_move(alg, m, true);
62 append_alg(ret, alg);
63 free_alg(alg);
64 }
65 }
66
67 return ret;
68}
69
70static void *
71instance_thread(void *arg)
72{
73 ThreadInitData *tid = (ThreadInitData *)arg;
74
75 while (true) {
76 pthread_mutex_lock(tid->start_mutex);
77 AlgListNode *node = *(tid->node);
78 if (node == NULL) {
79 pthread_mutex_unlock(tid->start_mutex);
80 break;
81 }
82 *(tid->node) = (*(tid->node))->next;
83 pthread_mutex_unlock(tid->start_mutex);
84
85/* TODO: adjust for longer (arbitrarily long?) starting sequences */
86 void *data = tid->solver->alloc_cubedata(tid->solver->param);
87 tid->solver->copy_cubedata(
88 tid->solver->param, tid->arg->cubedata, data);
89 bool inv = node->alg->inv[node->alg->len-1];
90 if (inv)
91 tid->solver->invert_cube(
92 tid->solver->param, data);
93 tid->solver->apply_move(
94 tid->solver->param, data, node->alg->move[0]);
95
96 DfsArg newarg;
97 newarg.cubedata = data;
98 newarg.threaddata = tid->arg->threaddata;
99 newarg.opts = tid->arg->opts;
100 newarg.d = tid->arg->d;
101 newarg.niss = inv;
102 newarg.current_alg = new_alg("");
103 copy_alg(node->alg, newarg.current_alg);
104
105 dfs(&newarg, tid->solver, tid->threader);
106
107 tid->solver->free_cubedata(tid->solver->param, data);
108 free_alg(newarg.current_alg);
109 }
110
111 return NULL;
112}
113
114static void
115dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader)
116{
117 int nthreads = arg->opts->nthreads;
118 ThreadInitData tid[nthreads];
119 pthread_t t[nthreads];
120
121 pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t));
122 pthread_mutex_init(sols_mutex, NULL);
123
124 arg->threaddata = malloc(sizeof(ThreadData));
125 ThreadData *td = (ThreadData *)arg->threaddata;
126 td->sols = sols;
127 td->sols_mutex = sols_mutex;
128
129 AlgList *starts = possible_starts(arg, solver);
130 AlgListNode *node = starts->first;
131 pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t));
132 pthread_mutex_init(start_mutex, NULL);
133 for (int i = 0; i < nthreads; i++) {
134 tid[i].arg = arg;
135 tid[i].solver = solver;
136 tid[i].threader = threader;
137 tid[i].starts = starts;
138 tid[i].node = &node;
139 tid[i].start_mutex = start_mutex;
140
141 pthread_create(&t[i], NULL, instance_thread, &tid[i]);
142 }
143
144 for (int i = 0; i < nthreads; i++)
145 pthread_join(t[i], NULL);
146
147 free(td);
148 free(sols_mutex);
149 free_alglist(starts);
150 free(start_mutex);
151}
152
153static int
154get_nsol(void *threaddata)
155{
156 ThreadData *td = (ThreadData *)threaddata;
157
158 pthread_mutex_lock(td->sols_mutex);
159 int n = td->sols->len;
160 pthread_mutex_unlock(td->sols_mutex);
161
162 return n;
163}
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 @@
1#ifndef THREADER_EAGER_H
2#define THREADER_EAGER_H
3
4#include "solve.h"
5
6extern Threader threader_eager;
7
8#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 @@
1#include "threader_single.h"
2
3static void append_sol(Alg *, void *);
4static void dispatch(DfsArg *, AlgList *, Solver *, Threader *);
5static int get_nsol(void *);
6
7Threader threader_single = {
8 .append_sol = append_sol,
9 .dispatch = dispatch,
10 .get_nsol = get_nsol,
11};
12
13static void
14append_sol(Alg *alg, void *threaddata)
15{
16 append_alg((AlgList *)threaddata, alg);
17}
18
19static void
20dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader)
21{
22 arg->threaddata = sols;
23 arg->niss = false;
24 arg->current_alg = new_alg("");
25
26 dfs(arg, solver, threader);
27
28 free_alg(arg->current_alg);
29}
30
31static int
32get_nsol(void *threaddata)
33{
34 return ((AlgList *)threaddata)->len;
35}
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 @@
1#ifndef THREADER_SINGLE_H
2#define THREADER_SINGLE_H
3
4#include "solve.h"
5
6extern Threader threader_single;
7
8#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 @@
1#define TRANS_C
2
3#include "trans.h"
4
5/* Local functions ***********************************************************/
6
7/* Tables and other data *****************************************************/
8
9static Cube mirror_cube = {
10.ep = { [UF] = UF, [UL] = UR, [UB] = UB, [UR] = UL,
11 [DF] = DF, [DL] = DR, [DB] = DB, [DR] = DL,
12 [FR] = FL, [FL] = FR, [BL] = BR, [BR] = BL },
13.cp = { [UFR] = UFL, [UFL] = UFR, [UBL] = UBR, [UBR] = UBL,
14 [DFR] = DFL, [DFL] = DFR, [DBL] = DBR, [DBR] = DBL },
15.xp = { [U_center] = U_center, [D_center] = D_center,
16 [R_center] = L_center, [L_center] = R_center,
17 [F_center] = F_center, [B_center] = B_center }
18};
19
20static char rotation_alg_string[100][NROTATIONS] = {
21 [uf] = "", [ur] = "y", [ub] = "y2", [ul] = "y3",
22 [df] = "z2", [dr] = "y z2", [db] = "x2", [dl] = "y3 z2",
23 [rf] = "z3", [rd] = "z3 y", [rb] = "z3 y2", [ru] = "z3 y3",
24 [lf] = "z", [ld] = "z y3", [lb] = "z y2", [lu] = "z y",
25 [fu] = "x y2", [fr] = "x y", [fd] = "x", [fl] = "x y3",
26 [bu] = "x3", [br] = "x3 y", [bd] = "x3 y2", [bl] = "x3 y3",
27};
28
29Alg *rotation_alg_arr[NROTATIONS];
30Move moves_ttable[NTRANS][NMOVES];
31Trans trans_ttable[NTRANS][NTRANS];
32Trans trans_itable[NTRANS];
33
34/* Public functions **********************************************************/
35
36void
37apply_trans(Trans t, Cube *cube)
38{
39 Cube aux;
40 Alg *inv;
41 int i;
42
43 inv = inverse_alg(rotation_alg(t % NROTATIONS));
44 copy_cube(cube, &aux);
45 make_solved(cube);
46
47 if (t >= NROTATIONS)
48 compose(&mirror_cube, cube);
49 apply_alg(inv, cube);
50 compose(&aux, cube);
51 apply_alg(rotation_alg(t % NROTATIONS), cube);
52 if (t >= NROTATIONS) {
53 compose(&mirror_cube, cube);
54 for (i = 0; i < 8; i++)
55 cube->co[i] = (3 - cube->co[i]) % 3;
56 }
57
58 free_alg(inv);
59}
60
61/*
62Trans
63inverse_trans(Trans t)
64{
65 static Trans inverse_trans_aux[NTRANS] = {
66 [uf] = uf, [ur] = ul, [ul] = ur, [ub] = ub,
67 [df] = df, [dr] = dr, [dl] = dl, [db] = db,
68 [rf] = lf, [rd] = bl, [rb] = rb, [ru] = fr,
69 [lf] = rf, [ld] = br, [lb] = lb, [lu] = fl,
70 [fu] = fu, [fr] = ru, [fd] = bu, [fl] = lu,
71 [bu] = fd, [br] = ld, [bd] = bd, [bl] = rd,
72
73 [uf_mirror] = uf_mirror, [ur_mirror] = ur_mirror,
74 [ul_mirror] = ul_mirror, [ub_mirror] = ub_mirror,
75 [df_mirror] = df_mirror, [dr_mirror] = dl_mirror,
76 [dl_mirror] = dr_mirror, [db_mirror] = db_mirror,
77 [rf_mirror] = rf_mirror, [rd_mirror] = br_mirror,
78 [rb_mirror] = lb_mirror, [ru_mirror] = fl_mirror,
79 [lf_mirror] = lf_mirror, [ld_mirror] = bl_mirror,
80 [lb_mirror] = rb_mirror, [lu_mirror] = fr_mirror,
81 [fu_mirror] = fu_mirror, [fr_mirror] = lu_mirror,
82 [fd_mirror] = bu_mirror, [fl_mirror] = ru_mirror,
83 [bu_mirror] = fd_mirror, [br_mirror] = rd_mirror,
84 [bd_mirror] = bd_mirror, [bl_mirror] = ld_mirror
85 };
86
87 return inverse_trans_aux[t];
88}
89*/
90
91Trans
92inverse_trans(Trans t)
93{
94 return trans_itable[t];
95}
96
97Alg *
98rotation_alg(Trans i)
99{
100 return rotation_alg_arr[i % NROTATIONS];
101}
102
103void
104transform_alg(Trans t, Alg *alg)
105{
106 int i;
107
108 for (i = 0; i < alg->len; i++)
109 alg->move[i] = transform_move(t, alg->move[i]);
110}
111
112Move
113transform_move(Trans t, Move m)
114{
115 return moves_ttable[t][m];
116}
117
118Trans
119transform_trans(Trans t, Trans m)
120{
121 return trans_ttable[t][m];
122}
123
124void
125init_trans() {
126 static bool initialized = false;
127 if (initialized)
128 return;
129 initialized = true;
130
131 int i;
132 Alg *nonsym_alg, *nonsym_inv;
133 Cube aux, cube;
134 Move mi, move;
135 Trans t, u, v;
136
137 init_moves();
138
139 for (i = 0; i < NROTATIONS; i++)
140 rotation_alg_arr[i] = new_alg(rotation_alg_string[i]);
141
142 for (t = 0; t < NTRANS; t++) {
143 for (mi = 0; mi < NMOVES; mi++) {
144 make_solved(&aux);
145 apply_move(mi, &aux);
146 apply_trans(t, &aux);
147 for (move = 0; move < NMOVES; move++) {
148 copy_cube(&aux, &cube);
149 apply_move(inverse_move(move), &cube);
150 if (is_solved(&cube)) {
151 moves_ttable[t][mi] = move;
152 break;
153 }
154 }
155 }
156 }
157
158 nonsym_alg = new_alg("R' U' F");
159 nonsym_inv = inverse_alg(nonsym_alg);
160
161 for (t = 0; t < NTRANS; t++) {
162 for (u = 0; u < NTRANS; u++) {
163 make_solved(&aux);
164 apply_alg(nonsym_alg, &aux);
165 apply_trans(u, &aux);
166 apply_trans(t, &aux);
167 for (v = 0; v < NTRANS; v++) {
168 copy_cube(&aux, &cube);
169 apply_trans(v, &cube);
170 apply_alg(nonsym_inv, &cube);
171 if (is_solved(&cube)) {
172 /* This is the inverse of the correct
173 value, it will be inverted later */
174 trans_ttable[t][u] = v;
175 if (v == uf)
176 trans_itable[t] = u;
177 break;
178 }
179 }
180 }
181 }
182 for (t = 0; t < NTRANS; t++)
183 for (u = 0; u < NTRANS; u++)
184 trans_ttable[t][u] = trans_itable[trans_ttable[t][u]];
185
186
187 free_alg(nonsym_alg);
188 free_alg(nonsym_inv);
189}
190
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 @@
1#ifndef TRANS_H
2#define TRANS_H
3
4#include "moves.h"
5
6void apply_trans(Trans t, Cube *cube);
7Trans inverse_trans(Trans t);
8Alg * rotation_alg(Trans i);
9void transform_alg(Trans t, Alg *alg);
10Move transform_move(Trans t, Move m);
11Trans transform_trans(Trans t, Trans m);
12
13void init_trans();
14
15#ifndef TRANS_C
16
17extern TransGroup tgrp_udfix;
18
19#else
20
21TransGroup
22tgrp_udfix = {
23 .n = 16,
24 .t = { uf, ur, ub, ul,
25 df, dr, db, dl,
26 uf_mirror, ur_mirror, ub_mirror, ul_mirror,
27 df_mirror, dr_mirror, db_mirror, dl_mirror },
28};
29
30#endif
31
32#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 @@
1#define UTILS_C
2
3#include "utils.h"
4
5void
6apply_permutation(int *perm, int *set, int n)
7{
8 int *aux = malloc(n * sizeof(int));
9 int i;
10
11 if (!is_perm(perm, n))
12 return;
13
14 for (i = 0; i < n; i++)
15 aux[i] = set[perm[i]];
16
17 memcpy(set, aux, n * sizeof(int));
18 free(aux);
19}
20
21int
22binomial(int n, int k)
23{
24 if (n < 0 || k < 0 || k > n)
25 return 0;
26
27 return factorial(n) / (factorial(k) * factorial(n-k));
28}
29
30int
31digit_array_to_int(int *a, int n, int b)
32{
33 int i, ret = 0, p = 1;
34
35 for (i = 0; i < n; i++, p *= b)
36 ret += a[i] * p;
37
38 return ret;
39}
40
41int
42factorial(int n)
43{
44 int i, ret = 1;
45
46 if (n < 0)
47 return 0;
48
49 for (i = 1; i <= n; i++)
50 ret *= i;
51
52 return ret;
53}
54
55void
56index_to_perm(int p, int n, int *r)
57{
58 int *a = malloc(n * sizeof(int));
59 int i, j, c;
60
61 for (i = 0; i < n; i++)
62 a[i] = 0;
63
64 if (p < 0 || p >= factorial(n))
65 for (i = 0; i < n; i++)
66 r[i] = -1;
67
68 for (i = 0; i < n; i++) {
69 c = 0;
70 j = 0;
71 while (c <= p / factorial(n-i-1))
72 c += a[j++] ? 0 : 1;
73 r[i] = j-1;
74 a[j-1] = 1;
75 p %= factorial(n-i-1);
76 }
77
78 free(a);
79}
80
81void
82index_to_subset(int s, int n, int k, int *r)
83{
84 int i, j, v;
85
86 if (s < 0 || s >= binomial(n, k)) {
87 for (i = 0; i < n; i++)
88 r[i] = -1;
89 return;
90 }
91
92 for (i = 0; i < n; i++) {
93 if (k == n-i) {
94 for (j = i; j < n; j++)
95 r[j] = 1;
96 return;
97 }
98
99 if (k == 0) {
100 for (j = i; j < n; j++)
101 r[j] = 0;
102 return;
103 }
104
105 v = binomial(n-i-1, k);
106 if (s >= v) {
107 r[i] = 1;
108 k--;
109 s -= v;
110 } else {
111 r[i] = 0;
112 }
113 }
114}
115
116void
117int_to_digit_array(int a, int b, int n, int *r)
118{
119 int i;
120
121 if (b <= 1)
122 for (i = 0; i < n; i++)
123 r[i] = 0;
124 else
125 for (i = 0; i < n; i++, a /= b)
126 r[i] = a % b;
127}
128
129void
130int_to_sum_zero_array(int x, int b, int n, int *a)
131{
132 int i, s = 0;
133
134 if (b <= 1) {
135 for (i = 0; i < n; i++)
136 a[i] = 0;
137 } else {
138 int_to_digit_array(x, b, n-1, a);
139 for (i = 0; i < n - 1; i++)
140 s = (s + a[i]) % b;
141 a[n-1] = (b - s) % b;
142 }
143}
144
145int
146invert_digits(int a, int b, int n)
147{
148 int i, ret, *r = malloc(n * sizeof(int));
149
150 int_to_digit_array(a, b, n, r);
151 for (i = 0; i < n; i++)
152 r[i] = (b-r[i]) % b;
153
154 ret = digit_array_to_int(r, n, b);
155 free(r);
156 return ret;
157}
158
159bool
160is_perm(int *a, int n)
161{
162 int *aux = malloc(n * sizeof(int));
163 int i;
164 bool ret = true;
165
166 for (i = 0; i < n; i++)
167 aux[i] = 0;
168
169 for (i = 0; i < n; i++) {
170 if (a[i] < 0 || a[i] >= n)
171 ret = false;
172 else
173 aux[a[i]] = 1;
174 }
175
176 for (i = 0; i < n; i++)
177 if (!aux[i])
178 ret = false;
179
180 free(aux);
181 return ret;
182}
183
184bool
185is_subset(int *a, int n, int k)
186{
187 int i, sum = 0;
188
189 for (i = 0; i < n; i++)
190 sum += a[i] ? 1 : 0;
191
192 return sum == k;
193}
194
195int
196perm_sign(int *a, int n)
197{
198 int i, j, ret = 0;
199
200 if (!is_perm(a, n))
201 return -1;
202
203 for (i = 0; i < n; i++)
204 for (j = i+1; j < n; j++)
205 ret += (a[i] > a[j]) ? 1 : 0;
206
207 return ret % 2;
208}
209
210int
211perm_to_index(int *a, int n)
212{
213 int i, j, c, ret = 0;
214
215 if (!is_perm(a, n))
216 return factorial(n);
217
218 for (i = 0; i < n; i++) {
219 c = 0;
220 for (j = i+1; j < n; j++)
221 c += (a[i] > a[j]) ? 1 : 0;
222 ret += factorial(n-i-1) * c;
223 }
224
225 return ret;
226}
227
228int
229powint(int a, int b)
230{
231 if (b < 0)
232 return 0;
233 if (b == 0)
234 return 1;
235
236 if (b % 2)
237 return a * powint(a, b-1);
238 else
239 return powint(a*a, b/2);
240}
241
242int
243subset_to_index(int *a, int n, int k)
244{
245 int i, ret = 0;
246
247 if (!is_subset(a, n, k))
248 return binomial(n, k);
249
250 for (i = 0; i < n; i++) {
251 if (k == n-i)
252 return ret;
253 if (a[i]) {
254 ret += binomial(n-i-1, k);
255 k--;
256 }
257 }
258
259 return ret;
260}
261
262void
263sum_arrays_mod(int *src, int *dst, int n, int m)
264{
265 int i;
266
267 for (i = 0; i < n; i++)
268 dst[i] = (m <= 0) ? 0 : (src[i] + dst[i]) % m;
269}
270
271void
272swap(int *a, int *b)
273{
274 int aux;
275
276 aux = *a;
277 *a = *b;
278 *b = aux;
279}
280
281void
282swapu64(uint64_t *a, uint64_t *b)
283{
284 uint64_t aux;
285
286 aux = *a;
287 *a = *b;
288 *b = aux;
289}
290
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 @@
1#ifndef UTILS_H
2#define UTILS_H
3
4#include <stdbool.h>
5#include <stdint.h>
6#include <stdlib.h>
7#include <string.h>
8
9#define POW2TO6 64ULL
10#define POW2TO11 2048ULL
11#define POW2TO12 4096ULL
12#define POW3TO7 2187ULL
13#define POW3TO8 6561ULL
14#define FACTORIAL4 24ULL
15#define FACTORIAL6 720ULL
16#define FACTORIAL7 5040ULL
17#define FACTORIAL8 40320ULL
18#define FACTORIAL12 479001600ULL
19#define BINOM12ON4 495ULL
20#define BINOM8ON4 70ULL
21#define MIN(a,b) (((a) < (b)) ? (a) : (b))
22#define MAX(a,b) (((a) > (b)) ? (a) : (b))
23
24void apply_permutation(int *perm, int *set, int n);
25int binomial(int n, int k);
26int digit_array_to_int(int *a, int n, int b);
27int factorial(int n);
28void index_to_perm(int p, int n, int *r);
29void index_to_subset(int s, int n, int k, int *r);
30void int_to_digit_array(int a, int b, int n, int *r);
31void int_to_sum_zero_array(int x, int b, int n, int *a);
32int invert_digits(int a, int b, int n);
33bool is_perm(int *a, int n);
34bool is_subset(int *a, int n, int k);
35int perm_sign(int *a, int n);
36int perm_to_index(int *a, int n);
37int powint(int a, int b);
38int subset_to_index(int *a, int n, int k);
39void sum_arrays_mod(int *src, int *dst, int n, int m);
40void swap(int *a, int *b);
41void swapu64(uint64_t *a, uint64_t *b);
42
43#endif

Generated with cgit - Back to sebastiano.tronto.net