aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2023-03-05 10:13:01 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2023-03-05 10:13:01 +0100
commit87a15e960e31365698df7e06cd3e6b851e17c1a5 (patch)
tree606a42e6251df3c24d92a2edefce723bdd103620 /src
parent3bfd0bb403d62bd942d1912d085ea59b156062fd (diff)
downloadnissy-87a15e960e31365698df7e06cd3e6b851e17c1a5.tar.gz
nissy-87a15e960e31365698df7e06cd3e6b851e17c1a5.zip
I made a mess, but it works. Still need to implement new optimal solver.
After that, a big redesign is due.
Diffstat (limited to '')
-rw-r--r--src/alg.c127
-rw-r--r--src/alg.h76
-rw-r--r--src/commands.c18
-rw-r--r--src/commands.h9
-rw-r--r--src/cubetypes.h36
-rw-r--r--src/movesets.c194
-rw-r--r--src/movesets.h15
-rw-r--r--src/pruning.h1
-rw-r--r--src/solve.c513
-rw-r--r--src/solve.h50
-rw-r--r--src/solver_step.c296
-rw-r--r--src/solver_step.h12
-rw-r--r--src/steps.c14
-rw-r--r--src/steps.h5
-rw-r--r--src/threader_eager.c162
-rw-r--r--src/threader_eager.h8
-rw-r--r--src/threader_single.c35
-rw-r--r--src/threader_single.h8
18 files changed, 957 insertions, 622 deletions
diff --git a/src/alg.c b/src/alg.c
index 2815599..d806178 100644
--- a/src/alg.c
+++ b/src/alg.c
@@ -6,57 +6,6 @@ static int axis(Move m);
6static void free_alglistnode(AlgListNode *aln); 6static void free_alglistnode(AlgListNode *aln);
7static void realloc_alg(Alg *alg, int n); 7static void realloc_alg(Alg *alg, int n);
8 8
9bool
10allowed_HTM(Move m)
11{
12 return m >= U && m <= B3;
13}
14
15bool
16allowed_URF(Move m)
17{
18 Move b = base_move(m);
19
20 return b == U || b == R || b == F;
21}
22
23bool
24allowed_eofb(Move m)
25{
26 Move b = base_move(m);
27
28 return b == U || b == D || b == R || b == L ||
29 ((b == F || b == B) && m == b+1);
30}
31
32bool
33allowed_drud(Move m)
34{
35 Move b = base_move(m);
36
37 return b == U || b == D ||
38 ((b == R || b == L || b == F || b == B) && m == b + 1);
39}
40
41bool
42allowed_htr(Move m)
43{
44 Move b = base_move(m);
45
46 return moveset_HTM.allowed(m) && m == b + 1;
47}
48
49bool
50allowed_next_all(Move l2, Move l1, Move m)
51{
52 bool p, q;
53
54 p = l1 != NULLMOVE && base_move(l1) == base_move(m);
55 q = l2 != NULLMOVE && base_move(l2) == base_move(m);
56
57 return !(p || (commute(l1, l2) && q));
58}
59
60void 9void
61append_alg(AlgList *l, Alg *alg) 10append_alg(AlgList *l, Alg *alg)
62{ 11{
@@ -137,6 +86,32 @@ commute(Move m1, Move m2)
137 return axis(m1) == axis(m2); 86 return axis(m1) == axis(m2);
138} 87}
139 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
140void 115void
141compose_alg(Alg *alg1, Alg *alg2) 116compose_alg(Alg *alg1, Alg *alg2)
142{ 117{
@@ -355,19 +330,6 @@ on_inverse(Alg *alg)
355 return ret; 330 return ret;
356} 331}
357 332
358bool
359possible_next(Move m, Moveset *ms, Move l0, Move l1)
360{
361 bool allowed, order;
362 uint64_t mbit;
363
364 mbit = ((uint64_t)1) << m;
365 allowed = mbit & ms->mask[l1][l0];
366 order = !commute(l0, m) || l0 < m;
367
368 return allowed && order;
369}
370
371void 333void
372print_alg(Alg *alg, bool l) 334print_alg(Alg *alg, bool l)
373{ 335{
@@ -431,6 +393,17 @@ realloc_alg(Alg *alg, int n)
431} 393}
432 394
433void 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
434swapmove(Move *m1, Move *m2) 407swapmove(Move *m1, Move *m2)
435{ 408{
436 Move aux; 409 Move aux;
@@ -484,29 +457,3 @@ unniss(Alg *alg)
484 457
485 return ret; 458 return ret;
486} 459}
487
488void
489init_moveset(Moveset *ms)
490{
491 int j;
492 uint64_t l, one;
493 Move m, l2, l1;
494
495 one = 1;
496
497 for (j = 0, m = U; m < NMOVES; m++)
498 if (ms->allowed(m))
499 ms->sorted_moves[j++] = m;
500 ms->sorted_moves[j] = NULLMOVE;
501
502 for (l1 = 0; l1 < NMOVES; l1++) {
503 for (l2 = 0; l2 < NMOVES; l2++) {
504 ms->mask[l2][l1] = 0;
505 for (l = 0; ms->sorted_moves[l] != NULLMOVE; l++) {
506 m = ms->sorted_moves[l];
507 if (ms->allowed_next(l2, l1, m))
508 ms->mask[l2][l1] |= (one<<m);
509 }
510 }
511 }
512}
diff --git a/src/alg.h b/src/alg.h
index b65a55e..967cd92 100644
--- a/src/alg.h
+++ b/src/alg.h
@@ -8,21 +8,11 @@
8#include "cubetypes.h" 8#include "cubetypes.h"
9#include "utils.h" 9#include "utils.h"
10 10
11bool allowed_all(Move m);
12bool allowed_HTM(Move m);
13bool allowed_URF(Move m);
14bool allowed_eofb(Move m);
15bool allowed_drud(Move m);
16bool allowed_htr(Move m);
17bool allowed_next_all(Move l2, Move l1, Move m);
18
19void moveset_to_list(Moveset ms, Move *lst);
20void init_moveset(Moveset *ms);
21bool possible_next(Move m, Moveset *ms, Move l0, Move l1);
22
23void append_alg(AlgList *l, Alg *alg); 11void append_alg(AlgList *l, Alg *alg);
24void append_move(Alg *alg, Move m, bool inverse); 12void append_move(Alg *alg, Move m, bool inverse);
25Move base_move(Move m); 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);
26void compose_alg(Alg *alg1, Alg *alg2); 16void compose_alg(Alg *alg1, Alg *alg2);
27bool commute(Move m1, Move m2); 17bool commute(Move m1, Move m2);
28void copy_alg(Alg *src, Alg *dst); 18void copy_alg(Alg *src, Alg *dst);
@@ -36,70 +26,10 @@ AlgList * new_alglist();
36Alg * on_inverse(Alg *alg); 26Alg * on_inverse(Alg *alg);
37void print_alg(Alg *alg, bool l); 27void print_alg(Alg *alg, bool l);
38void print_alglist(AlgList *al, bool l); 28void print_alglist(AlgList *al, bool l);
29void remove_last_move(Alg *alg);
39void swapmove(Move *m1, Move *m2); 30void swapmove(Move *m1, Move *m2);
40char * trans_string(Trans t); /* Here because similar to move_string, move? */ 31char * trans_string(Trans t); /* Here because similar to move_string, move? */
41Alg * unniss(Alg *alg); 32Alg * unniss(Alg *alg);
42 33
43/* Movesets ******************************************************************/
44
45#ifndef ALG_C
46
47extern Moveset moveset_HTM;
48extern Moveset moveset_URF;
49extern Moveset moveset_eofb;
50extern Moveset moveset_drud;
51extern Moveset moveset_htr;
52
53extern Moveset * all_ms[];
54
55#else
56
57Moveset
58moveset_HTM = {
59 .name = "HTM",
60 .allowed = allowed_HTM,
61 .allowed_next = allowed_next_all,
62};
63
64Moveset
65moveset_URF = {
66 .name = "URF",
67 .allowed = allowed_URF,
68 .allowed_next = allowed_next_all,
69};
70
71Moveset
72moveset_eofb = {
73 .name = "eofb",
74 .allowed = allowed_eofb,
75 .allowed_next = allowed_next_all,
76};
77
78Moveset
79moveset_drud = {
80 .name = "drud",
81 .allowed = allowed_drud,
82 .allowed_next = allowed_next_all,
83};
84
85Moveset
86moveset_htr = {
87 .name = "htr",
88 .allowed = allowed_htr,
89 .allowed_next = allowed_next_all,
90};
91
92Moveset *
93all_ms[] = {
94 &moveset_HTM,
95 &moveset_URF,
96 &moveset_eofb,
97 &moveset_drud,
98 &moveset_htr,
99 NULL
100};
101
102#endif
103
104#endif 34#endif
105 35
diff --git a/src/commands.c b/src/commands.c
index 9ac1ae6..a9e8fc9 100644
--- a/src/commands.c
+++ b/src/commands.c
@@ -215,10 +215,21 @@ solve_exec(CommandArgs *args)
215{ 215{
216 Cube c; 216 Cube c;
217 AlgList *sols; 217 AlgList *sols;
218 Solver *solver[99];
219 Threader *threader;
218 220
219 make_solved(&c); 221 make_solved(&c);
220 apply_alg(args->scramble, &c); 222 apply_alg(args->scramble, &c);
221 sols = solve(&c, args->cs, args->opts); 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);
222 233
223 if (args->opts->count_only) 234 if (args->opts->count_only)
224 printf("%d\n", sols->len); 235 printf("%d\n", sols->len);
@@ -285,7 +296,10 @@ scramble_exec(CommandArgs *args)
285 } 296 }
286 297
287 /* TODO: can be optimized for htr and dr using htrfin, drfin */ 298 /* TODO: can be optimized for htr and dr using htrfin, drfin */
299 /*
300 TODO: solve_2phase was removed
288 scr = solve_2phase(&cube, 1); 301 scr = solve_2phase(&cube, 1);
302 */
289 303
290 if (!strcmp(args->scrtype, "fmc")) { 304 if (!strcmp(args->scrtype, "fmc")) {
291 aux = new_alg(""); 305 aux = new_alg("");
@@ -383,6 +397,7 @@ print_exec(CommandArgs *args)
383 print_cube(&c); 397 print_cube(&c);
384} 398}
385 399
400/*
386void 401void
387twophase_exec(CommandArgs *args) 402twophase_exec(CommandArgs *args)
388{ 403{
@@ -396,6 +411,7 @@ twophase_exec(CommandArgs *args)
396 print_alg(sol, false); 411 print_alg(sol, false);
397 free_alg(sol); 412 free_alg(sol);
398} 413}
414*/
399 415
400void 416void
401help_exec(CommandArgs *args) 417help_exec(CommandArgs *args)
diff --git a/src/commands.h b/src/commands.h
index 5d9f4ee..65708e0 100644
--- a/src/commands.h
+++ b/src/commands.h
@@ -5,6 +5,9 @@
5 5
6#include "solve.h" 6#include "solve.h"
7#include "steps.h" 7#include "steps.h"
8#include "solver_step.h"
9#include "threader_single.h"
10#include "threader_eager.h"
8 11
9void free_args(CommandArgs *args); 12void free_args(CommandArgs *args);
10CommandArgs * new_args(); 13CommandArgs * new_args();
@@ -29,7 +32,7 @@ void steps_exec(CommandArgs *args);
29void commands_exec(CommandArgs *args); 32void commands_exec(CommandArgs *args);
30void freemem_exec(CommandArgs *args); 33void freemem_exec(CommandArgs *args);
31void print_exec(CommandArgs *args); 34void print_exec(CommandArgs *args);
32void twophase_exec(CommandArgs *args); 35/*void twophase_exec(CommandArgs *args);*/
33void help_exec(CommandArgs *args); 36void help_exec(CommandArgs *args);
34void quit_exec(CommandArgs *args); 37void quit_exec(CommandArgs *args);
35void unniss_exec(CommandArgs *args); 38void unniss_exec(CommandArgs *args);
@@ -138,6 +141,7 @@ help_cmd = {
138 .exec = help_exec, 141 .exec = help_exec,
139}; 142};
140 143
144/*
141Command 145Command
142twophase_cmd = { 146twophase_cmd = {
143 .name = "twophase", 147 .name = "twophase",
@@ -146,6 +150,7 @@ twophase_cmd = {
146 .parse_args = parse_only_scramble, 150 .parse_args = parse_only_scramble,
147 .exec = twophase_exec, 151 .exec = twophase_exec,
148}; 152};
153*/
149 154
150Command 155Command
151quit_cmd = { 156quit_cmd = {
@@ -194,7 +199,7 @@ Command *commands[] = {
194 &solve_cmd, 199 &solve_cmd,
195 &scramble_cmd, 200 &scramble_cmd,
196 &steps_cmd, 201 &steps_cmd,
197 &twophase_cmd, 202/* &twophase_cmd,*/
198 &cleanup_cmd, 203 &cleanup_cmd,
199 &unniss_cmd, 204 &unniss_cmd,
200 &version_cmd, 205 &version_cmd,
diff --git a/src/cubetypes.h b/src/cubetypes.h
index 8d38904..3752019 100644
--- a/src/cubetypes.h
+++ b/src/cubetypes.h
@@ -89,7 +89,7 @@ typedef struct command Command;
89typedef struct commandargs CommandArgs; 89typedef struct commandargs CommandArgs;
90typedef struct coordinate Coordinate; 90typedef struct coordinate Coordinate;
91typedef struct cube Cube; 91typedef struct cube Cube;
92typedef struct dfsarg DfsArg; 92/*typedef struct dfsarg DfsArg;*/
93typedef struct fstcube FstCube; 93typedef struct fstcube FstCube;
94typedef struct indexer Indexer; 94typedef struct indexer Indexer;
95typedef struct movable Movable; 95typedef struct movable Movable;
@@ -104,9 +104,9 @@ typedef struct transgroup TransGroup;
104 104
105typedef bool (*Checker) (Cube *); 105typedef bool (*Checker) (Cube *);
106typedef bool (*CubeTester) (Cube *, Alg *); 106typedef bool (*CubeTester) (Cube *, Alg *);
107typedef bool (*DfsMover) (DfsArg *); 107/*typedef bool (*DfsMover) (DfsArg *);*/
108typedef void (*DfsExtraCopier) (void *, void *); 108typedef void (*DfsExtraCopier) (void *, void *);
109typedef bool (*Validator) (Alg *); 109typedef Alg * (*Validator) (Alg *);
110typedef void (*Exec) (CommandArgs *); 110typedef void (*Exec) (CommandArgs *);
111typedef CommandArgs * (*ArgParser) (int, char **); 111typedef CommandArgs * (*ArgParser) (int, char **);
112typedef bool (*Tester) (void); 112typedef bool (*Tester) (void);
@@ -206,13 +206,16 @@ cube
206 int xp[6]; 206 int xp[6];
207}; 207};
208 208
209/*
209struct 210struct
210movable 211movable
211{ 212{
212 uint64_t val; 213 uint64_t val;
213 Trans t; 214 Trans t;
214}; 215};
216*/
215 217
218/*
216struct 219struct
217dfsarg 220dfsarg
218{ 221{
@@ -224,13 +227,28 @@ dfsarg
224 int d; 227 int d;
225 int bound; 228 int bound;
226 bool niss; 229 bool niss;
227 Move last[2];
228 Move lastinv[2];
229 AlgList * sols; 230 AlgList * sols;
230 pthread_mutex_t * sols_mutex; 231 pthread_mutex_t * sols_mutex;
231 Alg * current_alg; 232 Alg * current_alg;
232 void * extra; 233 void * extra;
233}; 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*/
234 252
235struct 253struct
236fstcube 254fstcube
@@ -260,9 +278,9 @@ moveset
260{ 278{
261 char * name; 279 char * name;
262 bool (*allowed)(Move); 280 bool (*allowed)(Move);
263 bool (*allowed_next)(Move, Move, Move); 281 bool (*can_append)(Alg *, Move, bool);
282 bool (*cancel_niss)(Alg *);
264 Move sorted_moves[NMOVES+1]; 283 Move sorted_moves[NMOVES+1];
265 uint64_t mask[NMOVES][NMOVES];
266}; 284};
267 285
268struct 286struct
@@ -304,10 +322,11 @@ step
304 PruneData * pd[MAX_N_COORD]; 322 PruneData * pd[MAX_N_COORD];
305 bool pd_compact[MAX_N_COORD]; 323 bool pd_compact[MAX_N_COORD];
306 Validator is_valid; 324 Validator is_valid;
307 DfsMover custom_move_checkstop; 325 /*DfsMover custom_move_checkstop;*/
308 DfsExtraCopier copy_extra; 326 DfsExtraCopier copy_extra;
309}; 327};
310 328
329/*
311struct 330struct
312threaddatasolve 331threaddatasolve
313{ 332{
@@ -317,6 +336,7 @@ threaddatasolve
317 AlgListNode ** node; 336 AlgListNode ** node;
318 pthread_mutex_t * start_mutex; 337 pthread_mutex_t * start_mutex;
319}; 338};
339*/
320 340
321struct 341struct
322threaddatagenpt 342threaddatagenpt
diff --git a/src/movesets.c b/src/movesets.c
new file mode 100644
index 0000000..d8f5bc1
--- /dev/null
+++ b/src/movesets.c
@@ -0,0 +1,194 @@
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
new file mode 100644
index 0000000..a02d171
--- /dev/null
+++ b/src/movesets.h
@@ -0,0 +1,15 @@
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.h b/src/pruning.h
index 86691c1..93ae863 100644
--- a/src/pruning.h
+++ b/src/pruning.h
@@ -2,6 +2,7 @@
2#define PRUNING_H 2#define PRUNING_H
3 3
4#include "coord.h" 4#include "coord.h"
5#include "movesets.h"
5 6
6void free_pd(PruneData *pd); 7void free_pd(PruneData *pd);
7PruneData * genptable(PruneData *data, int nthreads); 8PruneData * genptable(PruneData *data, int nthreads);
diff --git a/src/solve.c b/src/solve.c
index d5a8f3d..41f99a2 100644
--- a/src/solve.c
+++ b/src/solve.c
@@ -2,485 +2,118 @@
2 2
3#include "solve.h" 3#include "solve.h"
4 4
5/* Local functions ***********************************************************/ 5void
6 6dfs(DfsArg *arg, Solver *solver, Threader *threader)
7static bool cancel_niss(DfsArg *arg);
8static void copy_dfsarg(DfsArg *src, DfsArg *dst);
9static void dfs(DfsArg *arg);
10static void dfs_add_sol(DfsArg *arg);
11static void dfs_niss(DfsArg *arg);
12static bool dfs_move_checkstop(DfsArg *arg);
13static void * instance_thread(void *arg);
14static void multidfs(DfsArg *arg);
15static bool niss_makes_sense(DfsArg *arg);
16static bool solvestop(int d, int op, SolveOptions *opts, AlgList *sols);
17
18/* Local functions ***********************************************************/
19
20static bool
21cancel_niss(DfsArg *arg)
22{
23 Moveset *ms;
24 Move i1, i2;
25 bool p, p1, p2, q, q1, q2;
26
27 if (arg->lastinv[0] == NULLMOVE)
28 return false;
29
30 ms = arg->s->moveset;
31 i1 = inverse_move(arg->lastinv[0]);
32 i2 = inverse_move(arg->lastinv[1]);
33
34 p1 = !ms->allowed_next(arg->last[1], arg->last[0], i1);
35 p2 = !ms->allowed_next(arg->last[1], i1, arg->last[0]);
36 p = p1 || (commute(i1, arg->last[0]) && p2);
37
38 q1 = !ms->allowed_next(arg->last[1], arg->last[0], i2);
39 q2 = !ms->allowed_next(arg->last[1], i2, arg->last[0]);
40 q = q1 || (commute(i2, arg->last[0]) && q2);
41
42 return p || (commute(i1, i2) && q);
43}
44
45static void
46copy_dfsarg(DfsArg *src, DfsArg *dst)
47{ 7{
48 int i; 8 int i;
49
50 dst->cube = src->cube;
51 dst->t = src->t;
52 dst->s = src->s;
53 dst->opts = src->opts;
54 dst->d = src->d;
55 dst->bound = src->bound; /* In theory not needed */
56 dst->niss = src->niss;
57 dst->sols = src->sols;
58 dst->sols_mutex = src->sols_mutex;
59 dst->current_alg = src->current_alg;
60
61 for (i = 0; i < 2; i++) {
62 dst->last[i] = src->last[i];
63 dst->lastinv[i] = src->lastinv[i];
64 }
65
66 for (i = 0; i < src->s->n_coord; i++) {
67 dst->ind[i].val = src->ind[i].val;
68 dst->ind[i].t = src->ind[i].t;
69 }
70
71 src->s->copy_extra(src, dst);
72}
73
74static void
75dfs(DfsArg *arg)
76{
77 int i;
78 Move m, l0, l1;
79 DfsArg newarg; 9 DfsArg newarg;
10 Alg *sol;
11 Move m;
80 12
81 if (dfs_move_checkstop(arg)) 13 if (arg->current_alg->len > arg->d)
82 return;
83
84 if (arg->bound == 0) {
85 if (arg->current_alg->len == arg->d)
86 dfs_add_sol(arg);
87 return; 14 return;
88 }
89
90 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) {
91 m = arg->s->moveset->sorted_moves[i];
92 l0 = arg->last[0];
93 l1 = arg->last[1];
94 if (possible_next(m, arg->s->moveset, l0, l1)) {
95 copy_dfsarg(arg, &newarg);
96 newarg.last[1] = l0;
97 newarg.last[0] = m;
98 append_move(arg->current_alg, m, newarg.niss);
99 dfs(&newarg);
100 arg->current_alg->len--;
101 }
102 }
103
104 if (niss_makes_sense(arg))
105 dfs_niss(arg);
106}
107
108static void
109dfs_add_sol(DfsArg *arg)
110{
111 bool valid, accepted, nisscanc;
112 15
113 valid = arg->s->is_valid==NULL || arg->s->is_valid(arg->current_alg); 16 if (solver->is_solved(solver->param, arg->cubedata)) {
114 accepted = valid || arg->opts->all; 17/* TODO: the "all" option should be re-implemented as setting
115 nisscanc = arg->s->final && cancel_niss(arg); 18validate to null */
116 19
117 if (accepted && !nisscanc) { 20/* TODO: we also have to check if cancel with NISS;
118 pthread_mutex_lock(arg->sols_mutex); 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;
119 26
120 if (arg->sols->len < arg->opts->max_solutions) { 27 if (accepted && !too_short) {
121 append_alg(arg->sols, arg->current_alg); 28/* TODO: arg->t got lost in refactoring */
122 transform_alg( 29/* transform_alg(inverse_trans(arg->t), sol);*/
123 inverse_trans(arg->t), arg->sols->last->alg);
124 if (arg->opts->verbose) 30 if (arg->opts->verbose)
125 print_alg(arg->sols->last->alg, false); 31 print_alg(sol, false);
32 threader->append_sol(sol, arg->threaddata);
126 } 33 }
127 34 return;
128 pthread_mutex_unlock(arg->sols_mutex);
129 }
130}
131
132static void
133dfs_niss(DfsArg *arg)
134{
135 DfsArg newarg;
136 Alg *inv;
137 Cube *c;
138
139 copy_dfsarg(arg, &newarg);
140
141 /* Invert current alg and scramble */
142 newarg.cube = malloc(sizeof(Cube));
143 inv = inverse_alg(arg->current_alg);
144 c = malloc(sizeof(Cube));
145 make_solved(newarg.cube);
146 apply_alg(inv, newarg.cube);
147 copy_cube(arg->cube, c);
148 invert_cube(c);
149 compose(c, newarg.cube);
150
151 /* New indexes */
152 compute_ind(newarg.s, newarg.cube, newarg.ind);
153
154 swapmove(&(newarg.last[0]), &(newarg.lastinv[0]));
155 swapmove(&(newarg.last[1]), &(newarg.lastinv[1]));
156 newarg.niss = !(arg->niss);
157
158 dfs(&newarg);
159
160 free_alg(inv);
161 free(c);
162 free(newarg.cube);
163}
164
165static bool
166dfs_move_checkstop(DfsArg *arg)
167{
168 int i, goal, nsols;
169 Move mm;
170 Trans tt = uf; /* Avoid uninitialized warning */
171
172 /* Moving and computing bound */
173 arg->bound = 0;
174 goal = arg->d - arg->current_alg->len;
175 for (i = 0; i < arg->s->n_coord; i++) {
176 if (arg->last[0] != NULLMOVE) {
177 mm = transform_move(arg->ind[i].t, arg->last[0]);
178 arg->ind[i].val = move_coord(arg->s->coord[i],
179 mm, arg->ind[i].val, &tt);
180 arg->ind[i].t = transform_trans(tt, arg->ind[i].t);
181 }
182
183 arg->bound =
184 MAX(arg->bound, ptableval(arg->s->pd[i], arg->ind[i].val));
185 if (arg->opts->can_niss && !arg->niss)
186 arg->bound = MIN(1, arg->bound);
187
188 if (arg->bound > goal)
189 return true;
190 }
191
192 pthread_mutex_lock(arg->sols_mutex);
193 nsols = arg->sols->len;
194 pthread_mutex_unlock(arg->sols_mutex);
195
196 return nsols >= arg->opts->max_solutions;
197}
198
199static void *
200instance_thread(void *arg)
201{
202 bool b, inv;
203 Cube c;
204 Move m;
205 ThreadDataSolve *td;
206 AlgListNode *node;
207 DfsArg darg;
208
209 td = (ThreadDataSolve *)arg;
210
211 while (1) {
212 b = false;
213
214 pthread_mutex_lock(td->start_mutex);
215 if ((node = *(td->node)) == NULL)
216 b = true;
217 else
218 *(td->node) = (*(td->node))->next;
219 pthread_mutex_unlock(td->start_mutex);
220
221 if (b)
222 break;
223
224 inv = node->alg->inv[0];
225 m = node->alg->move[0];
226
227 copy_cube(td->arg.cube, &c);
228 if (inv)
229 invert_cube(&c);
230
231 copy_dfsarg(&td->arg, &darg);
232 compute_ind(td->arg.s, &c, darg.ind);
233 darg.cube = &c;
234
235 darg.niss = inv;
236 darg.last[0] = m;
237 darg.last[1] = NULLMOVE;
238 darg.lastinv[0] = NULLMOVE;
239 darg.lastinv[1] = NULLMOVE;
240 darg.current_alg = new_alg("");
241 append_move(darg.current_alg, m, inv);
242
243 dfs(&darg);
244
245 free_alg(darg.current_alg);
246 } 35 }
247 36
248 return NULL; 37 if (arg->current_alg->len == arg->d)
249} 38 return;
250
251static void
252multidfs(DfsArg *arg)
253{
254 int i;
255 Cube local_cube;
256 Alg *alg;
257 AlgList *start;
258 AlgListNode **node;
259 pthread_t t[arg->opts->nthreads];
260 ThreadDataSolve td[arg->opts->nthreads];
261 pthread_mutex_t *start_mutex, *sols_mutex;
262 39
263 node = malloc(sizeof(AlgListNode *)); 40/* TODO: do not alloc */
264 start_mutex = malloc(sizeof(pthread_mutex_t)); 41 newarg.cubedata = solver->alloc_cubedata(solver->param);
265 sols_mutex = malloc(sizeof(pthread_mutex_t)); 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);
266 47
267 start = new_alglist(); 48 solver->copy_cubedata(
268 pthread_mutex_init(start_mutex, NULL); 49 solver->param, arg->cubedata, newarg.cubedata);
269 pthread_mutex_init(sols_mutex, NULL); 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);
270 58
271 for (i = 0; arg->s->moveset->sorted_moves[i] != NULLMOVE; i++) { 59 remove_last_move(arg->current_alg);
272 alg = new_alg("");
273 append_move(alg, arg->s->moveset->sorted_moves[i], false);
274 append_alg(start, alg);
275 if (arg->opts->can_niss && !arg->s->final) {
276 alg->inv[0] = true;
277 append_alg(start, alg);
278 } 60 }
279 free_alg(alg);
280 } 61 }
281 *node = start->first; 62 solver->free_cubedata(solver->param, newarg.cubedata);
282
283 copy_cube(arg->cube, &local_cube);
284
285 for (i = 0; i < arg->opts->nthreads; i++) {
286 copy_dfsarg(arg, &(td[i].arg));
287 td[i].arg.cube = &local_cube;
288 td[i].arg.sols_mutex = sols_mutex;
289
290 td[i].thid = i;
291 td[i].start = start;
292 td[i].node = node;
293 td[i].start_mutex = start_mutex;
294
295 pthread_create(&t[i], NULL, instance_thread, &td[i]);
296 }
297
298 for (i = 0; i < arg->opts->nthreads; i++)
299 pthread_join(t[i], NULL);
300
301 free_alglist(start);
302 free(node);
303 free(start_mutex);
304 free(sols_mutex);
305}
306
307static bool
308niss_makes_sense(DfsArg *arg)
309{
310 Move m, mm;
311 uint64_t u;
312 int i;
313
314 if (arg->s->final || arg->niss || !arg->opts->can_niss)
315 return false;
316
317 if (arg->last[0] == NULLMOVE)
318 return true;
319 63
320 m = inverse_move(arg->last[0]); 64 if (arg->opts->can_niss && !arg->niss &&
321 for (i = 0; i < arg->s->n_coord; i++) { 65 solver->niss_makes_sense(
322 mm = transform_move(arg->ind[i].t, m); 66 solver->param, arg->cubedata, arg->current_alg)) {
323 u = move_coord(arg->s->coord[i], mm, 0, NULL); 67 solver->invert_cube(solver->param, arg->cubedata);
324 if (ptableval(arg->s->pd[i], u) > 0) 68 arg->niss = true;
325 return true; 69 dfs(arg, solver, threader);
326 } 70 }
327
328 return false;
329} 71}
330 72
331static bool
332solvestop(int d, int op, SolveOptions *opts, AlgList *sols)
333{
334 bool opt_done, max_moves_exceeded, max_sols_exceeded;
335
336 opt_done = opts->optimal != -1 && op != -1 && d > opts->optimal + op;
337 max_moves_exceeded = d > opts->max_moves;
338 max_sols_exceeded = sols->len >= opts->max_solutions;
339
340 return opt_done || max_moves_exceeded || max_sols_exceeded;
341}
342
343/* Public functions **********************************************************/
344
345AlgList * 73AlgList *
346solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts) 74solve(Cube *cube, SolveOptions *opts, Solver **solver, Threader *threader)
347{ 75{
348 int i, j, d, op, est; 76 int i, d, optimal;
349 bool ready[99], one_ready, zerosol; 77 bool ready[MAX_SOLVERS], stop, one_ready;
350 Movable ind[99][10]; 78 DfsArg arg[MAX_SOLVERS];
351 AlgList *s; 79 AlgList *sols;
352 Cube *c[99];
353 DfsArg arg[99];
354
355 prepare_cs(cs, opts);
356 s = new_alglist();
357
358 for (i = 0, one_ready = false; cs->step[i] != NULL; i++) {
359 c[i] = malloc(sizeof(Cube));
360 copy_cube(cube, c[i]);
361 apply_trans(cs->t[i], c[i]);
362 80
363 arg[i].cube = c[i]; 81 one_ready = false;
364 arg[i].t = cs->t[i]; 82 for (i = 0; solver[i] != NULL; i++) {
365 arg[i].s = cs->step[i]; 83 arg[i].cubedata =
84 solver[i]->prepare_cube(solver[i]->param, cube);
366 arg[i].opts = opts; 85 arg[i].opts = opts;
367 arg[i].sols = s; 86 ready[i] = arg[i].cubedata != NULL;
368 87 one_ready = one_ready || ready[i];
369 if ((ready[i] = cs->step[i]->ready(c[i]))) {
370 one_ready = true;
371 /* Only for local use for 0 moves solutions */
372 compute_ind(cs->step[i], c[i], ind[i]);
373 }
374 }
375 if (!one_ready) {
376 fprintf(stderr, "Cube not ready for solving step: ");
377 fprintf(stderr, "%s\n", cs->ready_msg);
378 return s;
379 } 88 }
380 89
381 /* If the empty moves sequence is a solution for one of the 90 sols = new_alglist();
382 * alternatives, all longer solutions will be discarded, so we may 91 if (!one_ready) {
383 * just set its ready[] value to false. If the solution is accepted 92 fprintf(stderr, "Cube not ready for solving\n");
384 * we append it and start searching from d = 1. */ 93 return sols;
385 for (i = 0, zerosol = false; cs->step[i] != NULL; i++) {
386 if (ready[i]) {
387 est = 0;
388 for (j = 0; j < cs->step[i]->n_coord; j++)
389 est = MAX(est, ptableval(cs->step[i]->pd[j],
390 ind[i][j].val));
391 if (est == 0) {
392 ready[i] = false;
393 zerosol = true;
394 }
395 }
396 }
397 if (zerosol && opts->min_moves == 0) {
398 append_alg(s, new_alg(""));
399 opts->min_moves = 1;
400 if (opts->verbose)
401 printf("Step is already solved"
402 "(empty alg is a solution)\n");
403 } 94 }
404 95
405 for (d = opts->min_moves, op = -1; !solvestop(d, op, opts, s); d++) { 96 optimal = opts->max_moves;
97 stop = false;
98 for (d = opts->min_moves; d <= opts->max_moves && !stop; d++) {
406 if (opts->verbose) 99 if (opts->verbose)
407 fprintf(stderr, "Searching depth %d\n", d); 100 fprintf(stderr, "Searching depth %d\n", d);
408 101
409 for (i=0; cs->step[i]!=NULL && !solvestop(d,op,opts,s); i++) { 102 for (i = 0; solver[i] != NULL && !stop; i++) {
410 if (!ready[i]) 103 if (!ready[i])
411 continue; 104 continue;
412 105
413 arg[i].d = d; 106 arg[i].d = d;
414 multidfs(&arg[i]); 107 threader->dispatch(&arg[i], sols, solver[i], threader);
415
416 if (s->len > 0 && op == -1)
417 op = d;
418 }
419 }
420
421 for (i = 0; cs->step[i] != NULL; i++)
422 free(c[i]);
423
424 return s;
425}
426 108
427/* TODO: make more general! */ 109 if (sols->len > 0)
428Alg * 110 optimal = MIN(optimal, d);
429solve_2phase(Cube *cube, int nthreads)
430{
431 int bestlen, newb;
432 Alg *bestalg, *ret;
433 AlgList *sols1, *sols2;
434 AlgListNode *i;
435 Cube c;
436 SolveOptions opts1, opts2;
437
438 opts1.min_moves = 0;
439 opts1.max_moves = 13;
440 opts1.max_solutions = 20;
441 opts1.nthreads = nthreads;
442 opts1.optimal = 3;
443 opts1.can_niss = false;
444 opts1.verbose = false;
445 opts1.all = true;
446 111
447 opts2.min_moves = 0; 112 stop = sols->len >= opts->max_solutions;
448 opts2.max_moves = 19;
449 opts2.max_solutions = 1;
450 opts2.nthreads = nthreads;
451 opts2.can_niss = false;
452 opts2.verbose = false;
453
454 /* We skip step1 if it is solved on U/D */
455 if (check_drud(cube)) {
456 sols1 = new_alglist();
457 append_alg(sols1, new_alg(""));
458 } else {
459 sols1 = solve(cube, &drud_HTM, &opts1);
460 }
461 bestalg = new_alg("");
462 bestlen = 999;
463 for (i = sols1->first; i != NULL; i = i->next) {
464 copy_cube(cube, &c);
465 apply_alg(i->alg, &c);
466 sols2 = solve(&c, &dranyfin_DR, &opts2);
467
468 if (sols2->len > 0) {
469 newb = i->alg->len + sols2->first->alg->len;
470 if (newb < bestlen) {
471 bestlen = newb;
472 copy_alg(i->alg, bestalg);
473 compose_alg(bestalg, sols2->first->alg);
474 }
475 } 113 }
476 114 stop = stop ||
477 free_alglist(sols2); 115 (opts->optimal != -1 && d >= opts->optimal + optimal);
478 } 116 }
479 117
480 free_alglist(sols1); 118 return sols;
481
482 ret = cleanup(bestalg);
483 free_alg(bestalg);
484
485 return ret;
486} 119}
diff --git a/src/solve.h b/src/solve.h
index 9a284ff..b09c81b 100644
--- a/src/solve.h
+++ b/src/solve.h
@@ -2,10 +2,52 @@
2#define SOLVE_H 2#define SOLVE_H
3 3
4#include "moves.h" 4#include "moves.h"
5#include "steps.h"
6#include "trans.h"
7 5
8AlgList * solve(Cube *cube, ChoiceStep *cs, SolveOptions *opts); 6#define MAX_SOLVERS 99
9Alg * solve_2phase(Cube *cube, int nthreads); 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 void * (*alloc_cubedata)(void *);
40 void (*copy_cubedata)(void *, void *, void *);
41 void (*free_cubedata)(void *, void *);
42 void (*invert_cube)(void *, void *);
43 bool (*is_solved)(void *, void *);
44 void (*apply_alg)(void *, void *, Alg *);
45/* TODO: remove dependence on Cube, preparation should be done before */
46 void * (*prepare_cube)(void *, Cube *);
47};
48
49void dfs(DfsArg *, Solver *, Threader *);
50/* TODO: remove dependence on Cube, preparation should be done before */
51AlgList * solve(Cube *, SolveOptions *, Solver **, Threader *);
10 52
11#endif 53#endif
diff --git a/src/solver_step.c b/src/solver_step.c
new file mode 100644
index 0000000..5c9d149
--- /dev/null
+++ b/src/solver_step.c
@@ -0,0 +1,296 @@
1#include "solver_step.h"
2
3typedef struct {
4 Cube * cube;
5 uint64_t * val;
6 Trans * t;
7} CubeData;
8
9static void apply_alg_cubedata(void *, void *, Alg *);
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_alg_cubedata(void *param, void *cubedata, Alg *alg)
26{
27 Step *s = (Step *)param;
28 CubeData *data = (CubeData *)cubedata;
29
30 apply_alg(alg, data->cube);
31 init_indexes(s, data);
32}
33
34static void
35init_indexes(Step *step, CubeData *data)
36{
37 int i;
38 Cube moved;
39 Trans t, tt;
40
41 for (i = 0; i < step->n_coord; i++) {
42 t = step->coord_trans[i];
43 copy_cube(data->cube, &moved);
44 apply_trans(t, &moved);
45 data->val[i] = index_coord(step->coord[i], &moved, &tt);
46 data->t[i] = transform_trans(tt, t);
47 }
48}
49
50static void *
51prepare_cube(void *param, Cube *cube)
52{
53 int i;
54 Step *s;
55 CubeData *data;
56
57 s = (Step *)param;
58
59 for (i = 0; i < s->n_coord; i++) {
60 s->pd[i] = malloc(sizeof(PruneData));
61 s->pd[i]->moveset = s->moveset;
62/* TODO: check if moveset initialization works fine,
63 e.g. if there is a variable to save the initialized status
64 or if it gets initialized multiple times */
65 init_moveset(s->moveset);
66 s->pd[i]->coord = s->coord[i];
67 gen_coord(s->coord[i]);
68 s->pd[i]->compact = s->pd_compact[i];
69 s->pd[i] = genptable(s->pd[i], 4); /* TODO: threads */
70 }
71
72 data = alloc_cubedata(param);
73 data->cube = malloc(sizeof(Cube));
74 copy_cube(cube, data->cube);
75 init_indexes(s, data);
76
77 return data;
78}
79
80static bool
81move_check_stop_eager(void *param, DfsArg *arg, Threader *threader)
82{
83 int nsol;
84
85 if (move_check_stop_nonsol(param, arg, threader))
86 return true;
87
88 nsol = threader->get_nsol(arg->threaddata);
89 return nsol >= arg->opts->max_solutions;
90}
91
92static bool
93move_check_stop_lazy(void *param, DfsArg *arg, Threader *threader)
94{
95 int nsol;
96
97 nsol = threader->get_nsol(arg->threaddata);
98 if (nsol >= arg->opts->max_solutions)
99 return true;
100
101 return move_check_stop_nonsol(param, arg, threader);
102}
103
104static bool
105move_check_stop_nonsol(void *param, DfsArg *arg, Threader *threader)
106{
107 int i, goal, bound;
108 Move mm, lastmove;
109 Trans tt = uf;
110 CubeData *data;
111 Step *s;
112
113 s = (Step *)param;
114 data = (CubeData *)arg->cubedata;
115
116 bound = 0;
117 goal = arg->d - arg->current_alg->len;
118/* TODO: check if len is 0 */
119 lastmove = arg->current_alg->move[arg->current_alg->len-1];
120 for (i = 0; i < s->n_coord; i++) {
121 mm = transform_move(data->t[i], lastmove);
122 data->val[i] = move_coord(s->coord[i], mm, data->val[i], &tt);
123 data->t[i] = transform_trans(tt, data->t[i]);
124
125 bound = MAX(bound, ptableval(s->pd[i], data->val[i]));
126 if (arg->opts->can_niss && !arg->niss)
127 bound = MIN(1, bound);
128
129 if (bound > goal) {
130 return true;
131 }
132 }
133
134 return false;
135}
136
137static bool
138is_solved_step(void *param, void *cubedata)
139{
140 int i;
141 Step *s;
142 CubeData *data;
143
144 s = (Step *)param;
145 data = (CubeData *)cubedata;
146
147 for (i = 0; i < s->n_coord; i++)
148 if (data->val[i] != 0)
149 return false;
150
151 return true;
152}
153
154static Alg *
155validate_solution(void *param, Alg *alg)
156{
157 return ((Step *)param)->is_valid(alg);
158}
159
160static void *
161alloc_cubedata(void *param)
162{
163 Step *s;
164 CubeData *data;
165
166 s = (Step *)param;
167
168 data = malloc(sizeof(CubeData));
169 /* We do not need to allocate a cube */
170 data->val = malloc(s->n_coord * sizeof(uint64_t));
171 data->t = malloc(s->n_coord * sizeof(Trans));
172
173 return data;
174}
175
176static void
177copy_cubedata(void *param, void *src, void *dst)
178{
179 int i;
180 Step *s;
181 CubeData *newdata, *olddata;
182
183 s = (Step *)param;
184 olddata = (CubeData *)src;
185 newdata = (CubeData *)dst;
186
187 /* Copy reference: we never move the cube */
188 newdata->cube = olddata->cube;
189 for (i = 0; i < s->n_coord; i++) {
190 newdata->val[i] = olddata->val[i];
191 newdata->t[i] = olddata->t[i];
192 }
193}
194
195static void
196free_cubedata(void *param, void *cubedata)
197{
198 CubeData *data;
199
200 data = (CubeData *)cubedata;
201
202 free(data->t);
203 free(data->val);
204 /* We do not free the cube */
205 free(data);
206}
207
208static void
209invert_cubedata(void *param, void *cubedata)
210{
211 Step *s;
212 CubeData *data;
213
214 s = (Step *)param;
215 data = (CubeData *)cubedata;
216
217 invert_cube(data->cube);
218 init_indexes(s, data);
219}
220
221static bool
222niss_makes_sense(void *param, void *cubedata, Alg *alg)
223{
224 Step *s;
225 CubeData *data;
226
227 s = (Step *)param;
228 data = (CubeData *)cubedata;
229
230 if (s->final)
231 return false;
232
233 if (alg->len_normal == 0)
234 return true;
235
236 Move m = inverse_move(alg->move_normal[alg->len_normal-1]);
237 for (int i = 0; i < s->n_coord; i++) {
238 Move mm = transform_move(data->t[i], m);
239 uint64_t u = move_coord(s->coord[i], mm, 0, NULL);
240 if (ptableval(s->pd[i], u) > 0)
241 return true;
242 }
243
244 return false;
245}
246
247static Solver *
248new_stepsolver_nocheckstop(Step *step)
249{
250 Solver *solver;
251
252 solver = malloc(sizeof(Solver));
253
254 solver->moveset = step->moveset;
255 solver->param = step;
256
257 solver->apply_alg = apply_alg_cubedata;
258 solver->prepare_cube = prepare_cube;
259 solver->is_solved = is_solved_step;
260 solver->validate_solution = validate_solution;
261 solver->alloc_cubedata = alloc_cubedata;
262 solver->copy_cubedata = copy_cubedata;
263 solver->free_cubedata = free_cubedata;
264 solver->invert_cube = invert_cubedata;
265 solver->niss_makes_sense = niss_makes_sense;
266
267 return solver;
268}
269
270Solver *
271new_stepsolver_eager(Step *step)
272{
273 Solver *solver;
274
275 solver = new_stepsolver_nocheckstop(step);
276 solver->move_check_stop = move_check_stop_eager;
277
278 return solver;
279}
280
281Solver *
282new_stepsolver_lazy(Step *step)
283{
284 Solver *solver;
285
286 solver = new_stepsolver_nocheckstop(step);
287 solver->move_check_stop = move_check_stop_lazy;
288
289 return solver;
290}
291
292void
293free_stepsolver(Solver *solver)
294{
295 free(solver);
296}
diff --git a/src/solver_step.h b/src/solver_step.h
new file mode 100644
index 0000000..f68d077
--- /dev/null
+++ b/src/solver_step.h
@@ -0,0 +1,12 @@
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
index 2f5fd2c..cdba763 100644
--- a/src/steps.c
+++ b/src/steps.c
@@ -106,11 +106,12 @@ check_htr(Cube *cube)
106 return true; 106 return true;
107} 107}
108 108
109bool 109Alg *
110validate_singlecw_ending(Alg *alg) 110validate_singlecw_ending(Alg *alg)
111{ 111{
112 int i; 112 int i;
113 bool nor, inv; 113 bool nor, inv;
114 Alg *ret;
114 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE; 115 Move l2 = NULLMOVE, l1 = NULLMOVE, l2i = NULLMOVE, l1i = NULLMOVE;
115 116
116 for (i = 0; i < alg->len; i++) { 117 for (i = 0; i < alg->len; i++) {
@@ -126,11 +127,19 @@ validate_singlecw_ending(Alg *alg)
126 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2)); 127 nor = l1 ==base_move(l1) && (!commute(l1, l2) ||l2 ==base_move(l2));
127 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i)); 128 inv = l1i==base_move(l1i) && (!commute(l1i,l2i)||l2i==base_move(l2i));
128 129
129 return nor && inv; 130 if (nor && inv) {
131 ret = new_alg("");
132 copy_alg(alg, ret);
133 } else {
134 ret = NULL;
135 }
136
137 return ret;
130} 138}
131 139
132/* Public functions **********************************************************/ 140/* Public functions **********************************************************/
133 141
142/*
134void 143void
135compute_ind(Step *s, Cube *cube, Movable *ind) 144compute_ind(Step *s, Cube *cube, Movable *ind)
136{ 145{
@@ -147,6 +156,7 @@ compute_ind(Step *s, Cube *cube, Movable *ind)
147 ind[i].t = transform_trans(tt, t); 156 ind[i].t = transform_trans(tt, t);
148 } 157 }
149} 158}
159*/
150 160
151void 161void
152prepare_cs(ChoiceStep *cs, SolveOptions *opts) 162prepare_cs(ChoiceStep *cs, SolveOptions *opts)
diff --git a/src/steps.h b/src/steps.h
index 0511b27..206f8b4 100644
--- a/src/steps.h
+++ b/src/steps.h
@@ -2,6 +2,7 @@
2#define STEPS_H 2#define STEPS_H
3 3
4#include "pruning.h" 4#include "pruning.h"
5#include "movesets.h"
5 6
6bool check_centers(Cube *cube); 7bool check_centers(Cube *cube);
7bool check_coud_HTM(Cube *cube); 8bool check_coud_HTM(Cube *cube);
@@ -13,10 +14,10 @@ bool check_cornershtr(Cube *cube);
13bool check_eofb(Cube *cube); 14bool check_eofb(Cube *cube);
14bool check_drud(Cube *cube); 15bool check_drud(Cube *cube);
15bool check_htr(Cube *cube); 16bool check_htr(Cube *cube);
16void compute_ind(Step *a, Cube *cube, Movable *ind); 17/*void compute_ind(Step *a, Cube *cube, Movable *ind);*/
17void prepare_cs(ChoiceStep *cs, SolveOptions *opts); 18void prepare_cs(ChoiceStep *cs, SolveOptions *opts);
18bool always_valid(Alg *alg); 19bool always_valid(Alg *alg);
19bool validate_singlecw_ending(Alg *alg); 20Alg * validate_singlecw_ending(Alg *alg);
20 21
21#ifndef STEPS_C 22#ifndef STEPS_C
22 23
diff --git a/src/threader_eager.c b/src/threader_eager.c
new file mode 100644
index 0000000..7013518
--- /dev/null
+++ b/src/threader_eager.c
@@ -0,0 +1,162 @@
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)
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 void *data = tid->solver->alloc_cubedata(tid->solver->param);
86 tid->solver->copy_cubedata(
87 tid->solver->param, tid->arg->cubedata, data);
88 tid->solver->apply_alg(
89 tid->solver->param, data, node->alg);
90 bool inv = node->alg->inv[node->alg->len-1];
91 if (inv)
92 tid->solver->invert_cube(
93 tid->solver->param, data);
94
95 DfsArg newarg;
96 newarg.cubedata = data;
97 newarg.threaddata = tid->arg->threaddata;
98 newarg.opts = tid->arg->opts;
99 newarg.d = tid->arg->d;
100 newarg.niss = inv;
101 newarg.current_alg = new_alg("");
102 copy_alg(node->alg, newarg.current_alg);
103
104 dfs(&newarg, tid->solver, tid->threader);
105
106 tid->solver->free_cubedata(tid->solver->param, data);
107 free_alg(newarg.current_alg);
108 }
109
110 return NULL;
111}
112
113static void
114dispatch(DfsArg *arg, AlgList *sols, Solver *solver, Threader *threader)
115{
116 int nthreads = arg->opts->nthreads;
117 ThreadInitData tid[nthreads];
118 pthread_t t[nthreads];
119
120 pthread_mutex_t *sols_mutex = malloc(sizeof(pthread_mutex_t));
121 pthread_mutex_init(sols_mutex, NULL);
122
123 arg->threaddata = malloc(sizeof(ThreadData));
124 ThreadData *td = (ThreadData *)arg->threaddata;
125 td->sols = sols;
126 td->sols_mutex = sols_mutex;
127
128 AlgList *starts = possible_starts(arg, solver);
129 AlgListNode *node = starts->first;
130 pthread_mutex_t *start_mutex = malloc(sizeof(pthread_mutex_t));
131 pthread_mutex_init(start_mutex, NULL);
132 for (int i = 0; i < nthreads; i++) {
133 tid[i].arg = arg;
134 tid[i].solver = solver;
135 tid[i].threader = threader;
136 tid[i].starts = starts;
137 tid[i].node = &node;
138 tid[i].start_mutex = start_mutex;
139
140 pthread_create(&t[i], NULL, instance_thread, &tid[i]);
141 }
142
143 for (int i = 0; i < nthreads; i++)
144 pthread_join(t[i], NULL);
145
146 free(td);
147 free(sols_mutex);
148 free_alglist(starts);
149 free(start_mutex);
150}
151
152static int
153get_nsol(void *threaddata)
154{
155 ThreadData *td = (ThreadData *)threaddata;
156
157 pthread_mutex_lock(td->sols_mutex);
158 int n = td->sols->len;
159 pthread_mutex_unlock(td->sols_mutex);
160
161 return n;
162}
diff --git a/src/threader_eager.h b/src/threader_eager.h
new file mode 100644
index 0000000..e39b27f
--- /dev/null
+++ b/src/threader_eager.h
@@ -0,0 +1,8 @@
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
new file mode 100644
index 0000000..232835d
--- /dev/null
+++ b/src/threader_single.c
@@ -0,0 +1,35 @@
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
new file mode 100644
index 0000000..2c0bfab
--- /dev/null
+++ b/src/threader_single.h
@@ -0,0 +1,8 @@
1#ifndef THREADER_SINGLE_H
2#define THREADER_SINGLE_H
3
4#include "solve.h"
5
6extern Threader threader_single;
7
8#endif

Generated with cgit - Back to sebastiano.tronto.net