aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/solve.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48/solve.h')
-rw-r--r--src/solvers/h48/solve.h610
1 files changed, 446 insertions, 164 deletions
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index d506596..8666007 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -1,9 +1,26 @@
1#define STARTING_MOVES 3
2#define STARTING_CUBES 3240 /* Number of 3-move sequences */
3
4typedef struct {
5 cube_t cube;
6 uint8_t moves[STARTING_MOVES];
7 uint64_t symmask0;
8} solve_h48_task_t;
9
1typedef struct { 10typedef struct {
11 cube_t start_cube;
12 uint64_t symmask0;
2 cube_t cube; 13 cube_t cube;
3 cube_t inverse; 14 cube_t inverse;
4 int8_t nmoves;
5 int8_t depth; 15 int8_t depth;
16 int8_t nmoves;
6 uint8_t moves[MAXLEN]; 17 uint8_t moves[MAXLEN];
18 int8_t npremoves;
19 uint8_t premoves[MAXLEN];
20 int8_t lb_normal;
21 int8_t lb_inverse;
22 bool use_lb_normal;
23 bool use_lb_inverse;
7 _Atomic int64_t *nsols; 24 _Atomic int64_t *nsols;
8 int64_t maxsolutions; 25 int64_t maxsolutions;
9 uint8_t h; 26 uint8_t h;
@@ -11,209 +28,385 @@ typedef struct {
11 uint8_t base; 28 uint8_t base;
12 const uint32_t *cocsepdata; 29 const uint32_t *cocsepdata;
13 const uint8_t *h48data; 30 const uint8_t *h48data;
14 const uint8_t *h48data_fallback; 31 const uint8_t *h48data_fallback_h0k4;
32 const void *h48data_fallback_eoesep;
15 uint64_t solutions_size; 33 uint64_t solutions_size;
16 char **nextsol; 34 uint64_t *solutions_used;
17 uint8_t nissbranch; 35 char **solutions;
18 int8_t npremoves; 36 uint32_t movemask_normal;
19 uint8_t premoves[MAXLEN]; 37 uint32_t movemask_inverse;
20 long long nodes_visited; 38 int64_t nodes_visited;
21 long long table_fallbacks; 39 int64_t table_fallbacks;
22} dfsarg_solveh48_t; 40 int64_t table_lookups;
41 int ntasks;
42 solve_h48_task_t *tasks;
43 int thread_id;
44 pthread_mutex_t *solutions_mutex;
45} dfsarg_solve_h48_t;
23 46
24STATIC uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint8_t); 47typedef struct {
48 cube_t cube;
49 int8_t nmoves;
50 uint8_t moves[STARTING_MOVES];
51 int8_t minmoves;
52 int8_t maxmoves;
53} dfsarg_solve_h48_maketasks_t;
25 54
26STATIC void solve_h48_appendsolution(dfsarg_solveh48_t *); 55STATIC int64_t solve_h48_appendsolution(dfsarg_solve_h48_t *);
27STATIC_INLINE bool solve_h48_stop(dfsarg_solveh48_t *); 56STATIC bool solve_h48_appendmoves(dfsarg_solve_h48_t *, int8_t,
28STATIC int64_t solve_h48_dfs(dfsarg_solveh48_t *); 57 uint8_t *, uint8_t);
29STATIC int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint64_t, 58STATIC bool solve_h48_appendchar(dfsarg_solve_h48_t *, char);
59STATIC_INLINE bool solve_h48_stop(dfsarg_solve_h48_t *);
60STATIC int64_t solve_h48_maketasks(
61 dfsarg_solve_h48_t *, dfsarg_solve_h48_maketasks_t *,
62 solve_h48_task_t [static STARTING_CUBES], int *);
63STATIC void *solve_h48_runthread(void *);
64STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t *);
65STATIC int64_t solve_h48(cube_t, int8_t, int8_t, uint64_t, uint64_t,
30 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]); 66 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
31 67
32STATIC uint32_t 68STATIC int64_t
33allowednextmove_h48(uint8_t *moves, uint8_t n, uint8_t h48branch) 69solve_h48_appendsolution(dfsarg_solve_h48_t *arg)
34{ 70{
35 uint32_t result = MM_ALLMOVES; 71 uint8_t t;
36 if (h48branch & MM_NORMALBRANCH) 72 int64_t ret;
37 result &= MM_NOHALFTURNS; 73 uint64_t solstart;
38 if (n < 1)
39 return result;
40 74
41 uint8_t base1 = movebase(moves[n-1]); 75 if (*arg->nsols >= arg->maxsolutions)
42 uint8_t axis1 = moveaxis(moves[n-1]); 76 return 0;
43 77
44 result = disable_moves(result, base1 * 3); 78 solstart = *arg->solutions_used;
45 if (base1 % 2) 79 invertmoves(arg->premoves, arg->npremoves, arg->moves + arg->nmoves);
46 result = disable_moves(result, (base1 - 1) * 3);
47 80
48 if (n == 1) 81 /* Do not append the solution in case premoves cancel with normal */
49 return result; 82 if (arg->npremoves > 0 && !allowednextmove(arg->moves, arg->nmoves+1))
83 return 0;
84 if (arg->npremoves > 1 && !allowednextmove(arg->moves, arg->nmoves+2))
85 return 0;
50 86
51 uint8_t base2 = movebase(moves[n-2]); 87 for (t = 0, ret = 0; t < 48 && *arg->nsols < arg->maxsolutions; t++) {
52 uint8_t axis2 = moveaxis(moves[n-2]); 88 if (!(arg->symmask0 & (UINT64_C(1) << (uint64_t)t)))
89 continue;
53 90
54 if(axis1 == axis2) 91 if (!solve_h48_appendmoves(arg, arg->nmoves + arg->npremoves,
55 result = disable_moves(result, base2 * 3); 92 arg->moves, t))
93 goto solve_h48_appendsolution_error;
94
95 LOG("Solution found: %s\n", *arg->solutions + solstart);
56 96
57 return result; 97 if (!solve_h48_appendchar(arg, '\n'))
98 goto solve_h48_appendsolution_error;
99 (*arg->nsols)++;
100 ret++;
101 }
102
103 return ret;
104
105solve_h48_appendsolution_error:
106 LOG("Could not append solution to buffer: size too small\n");
107 return NISSY_ERROR_BUFFER_SIZE;
58} 108}
59 109
60STATIC void 110STATIC bool
61solve_h48_appendsolution(dfsarg_solveh48_t *arg) 111solve_h48_appendmoves(
112 dfsarg_solve_h48_t *arg,
113 int8_t n,
114 uint8_t *moves,
115 uint8_t t
116)
62{ 117{
118 int i;
63 int64_t strl; 119 int64_t strl;
64 uint8_t invertedpremoves[MAXLEN]; 120 uint8_t mm[MAXLEN];
65 char *solution = *arg->nextsol;
66 121
67 strl = writemoves( 122 for (i = 0; i < n; i++)
68 arg->moves, arg->nmoves, arg->solutions_size, *arg->nextsol); 123 mm[i] = transform_move(moves[i], t);
69 124
70 if (strl < 0) 125 strl = writemoves(mm, n, arg->solutions_size - *arg->solutions_used,
71 goto solve_h48_appendsolution_error; 126 *arg->solutions + *arg->solutions_used);
72 *arg->nextsol += strl-1;
73 arg->solutions_size -= strl-1;
74 127
75 if (arg->npremoves) { 128 if (strl < 0)
76 **arg->nextsol = ' '; 129 return false;
77 (*arg->nextsol)++;
78 arg->solutions_size--;
79 130
80 invertmoves(arg->premoves, arg->npremoves, invertedpremoves); 131 *arg->solutions_used += MAX(0, strl-1);
81 strl = writemoves(invertedpremoves, 132 return true;
82 arg->npremoves, arg->solutions_size, *arg->nextsol); 133}
83 134
84 if (strl < 0) 135STATIC bool
85 goto solve_h48_appendsolution_error; 136solve_h48_appendchar(dfsarg_solve_h48_t *arg, char c)
86 *arg->nextsol += strl-1; 137{
87 arg->solutions_size -= strl-1; 138 if (arg->solutions_size <= *arg->solutions_used)
88 } 139 return false;
89 LOG("Solution found: %s\n", solution);
90 140
91 **arg->nextsol = '\n'; 141 *(*arg->solutions + *arg->solutions_used) = c;
92 (*arg->nextsol)++; 142 (*arg->solutions_used)++;
93 arg->solutions_size--;
94 (*arg->nsols)++;
95 143
96solve_h48_appendsolution_error: 144 return true;
97 /* We could add some logging, but writemoves() already does */
98 return;
99} 145}
100 146
101STATIC_INLINE bool 147STATIC_INLINE bool
102solve_h48_stop(dfsarg_solveh48_t *arg) 148solve_h48_stop(dfsarg_solve_h48_t *arg)
103{ 149{
104 uint32_t data, data_inv; 150 uint32_t data, data_inv;
105 int8_t cbound, cbound_inv, h48bound, h48bound_inv; 151 int64_t coord;
106 int64_t coord, coord_inv; 152 int8_t target, nh;
153 uint8_t pval_cocsep, pval_eoesep;
107 154
155 target = arg->depth - arg->nmoves - arg->npremoves;
156 if (target <= 0 || *arg->nsols == arg->maxsolutions)
157 return true;
158
159 arg->movemask_normal = arg->movemask_inverse = MM_ALLMOVES;
108 arg->nodes_visited++; 160 arg->nodes_visited++;
109 161
110 arg->nissbranch = MM_NORMAL; 162 /* Preliminary probing using last computed bound, if possible */
111 cbound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); 163
112 if (cbound + arg->nmoves + arg->npremoves > arg->depth) 164 if ((arg->use_lb_normal && arg->lb_normal > target) ||
165 (arg->use_lb_inverse && arg->lb_inverse > target))
113 return true; 166 return true;
114 167
115 cbound_inv = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv); 168 /* Preliminary corner probing */
116 if (cbound_inv + arg->nmoves + arg->npremoves > arg->depth) 169
170 if (get_h48_cdata(arg->cube, arg->cocsepdata, &data) > target ||
171 get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv) > target)
117 return true; 172 return true;
118 173
119 coord = coord_h48_edges(arg->cube, COCLASS(data), TTREP(data), arg->h); 174 /* Inverse probing */
120 h48bound = get_h48_pval(arg->h48data, coord, arg->k);
121 175
122 /* If the h48 bound is > 0, we add the base value. */ 176 if (!arg->use_lb_inverse) {
123 /* Otherwise, we use the fallback h0k4 value instead. */ 177 coord = coord_h48_edges(
178 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h);
179 arg->lb_inverse = get_h48_pval(arg->h48data, coord, arg->k);
180 arg->table_lookups++;
124 181
125 if (arg->k == 2) { 182 if (arg->k == 2 && arg->lb_inverse == 0) {
126 if (h48bound == 0) {
127 arg->table_fallbacks++; 183 arg->table_fallbacks++;
128 h48bound = get_h48_pval( 184
129 arg->h48data_fallback, coord >> arg->h, 4); 185 pval_cocsep = get_h48_pval(
186 arg->h48data_fallback_h0k4, coord >> arg->h, 4);
187 pval_eoesep = get_eoesep_pval_cube(
188 arg->h48data_fallback_eoesep, arg->inverse);
189 arg->lb_inverse = MAX(pval_cocsep, pval_eoesep);
130 } else { 190 } else {
131 h48bound += arg->base; 191 arg->lb_inverse += arg->base;
132 } 192 }
193
194 arg->use_lb_inverse = true;
133 } 195 }
134 if (h48bound + arg->nmoves + arg->npremoves > arg->depth) 196
197 if (arg->lb_inverse > target)
135 return true; 198 return true;
136 if (h48bound + arg->nmoves + arg->npremoves == arg->depth) 199 nh = arg->lb_inverse == target;
137 arg->nissbranch = MM_INVERSEBRANCH; 200 arg->movemask_normal = nh * MM_NOHALFTURNS + (1-nh) * MM_ALLMOVES;
201
202 /* Normal probing */
138 203
139 coord_inv = coord_h48_edges( 204 if (!arg->use_lb_normal) {
140 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); 205 coord = coord_h48_edges(
141 h48bound_inv = get_h48_pval(arg->h48data, coord_inv, arg->k); 206 arg->cube, COCLASS(data), TTREP(data), arg->h);
142 if (arg->k == 2) { 207 arg->lb_normal = get_h48_pval(arg->h48data, coord, arg->k);
143 if (h48bound_inv == 0) { 208 arg->table_lookups++;
209
210 if (arg->k == 2 && arg->lb_normal == 0) {
144 arg->table_fallbacks++; 211 arg->table_fallbacks++;
145 h48bound_inv = get_h48_pval( 212
146 arg->h48data_fallback, coord_inv >> arg->h, 4); 213 pval_cocsep = get_h48_pval(
214 arg->h48data_fallback_h0k4, coord >> arg->h, 4);
215 pval_eoesep = get_eoesep_pval_cube(
216 arg->h48data_fallback_eoesep, arg->cube);
217 arg->lb_normal = MAX(pval_cocsep, pval_eoesep);
147 } else { 218 } else {
148 h48bound_inv += arg->base; 219 arg->lb_normal += arg->base;
149 } 220 }
221
222 arg->use_lb_normal = true;
150 } 223 }
151 if (h48bound_inv + arg->nmoves + arg->npremoves > arg->depth) 224
225 if (arg->lb_normal > target)
152 return true; 226 return true;
153 if (h48bound_inv + arg->nmoves + arg->npremoves == arg->depth) 227 nh = arg->lb_normal == target;
154 arg->nissbranch = MM_NORMALBRANCH; 228 arg->movemask_inverse = nh * MM_NOHALFTURNS + (1-nh) * MM_ALLMOVES;
155 229
156 return false; 230 return false;
157} 231}
158 232
159STATIC int64_t 233STATIC int64_t
160solve_h48_dfs(dfsarg_solveh48_t *arg) 234solve_h48_dfs(dfsarg_solve_h48_t *arg)
161{ 235{
162 dfsarg_solveh48_t nextarg; 236 int64_t ret, n;
163 int64_t ret; 237 uint8_t m, lbn, lbi;
164 uint8_t m; 238 uint32_t mm_normal, mm_inverse;
165 239 bool ulbi, ulbn;
166 if (*arg->nsols == arg->maxsolutions) 240 cube_t backup_cube, backup_inverse;
167 return 0;
168
169 if (solve_h48_stop(arg))
170 return 0;
171 241
172 if (issolved(arg->cube)) { 242 if (issolved(arg->cube)) {
173 if (arg->nmoves + arg->npremoves != arg->depth) 243 if (arg->nmoves + arg->npremoves != arg->depth)
174 return 0; 244 return 0;
175 solve_h48_appendsolution(arg); 245 pthread_mutex_lock(arg->solutions_mutex);
176 return 1; 246 ret = solve_h48_appendsolution(arg);
247 pthread_mutex_unlock(arg->solutions_mutex);
248 return ret;
177 } 249 }
178 250
179 nextarg = *arg; 251 if (solve_h48_stop(arg))
252 return 0;
253
254 backup_cube = arg->cube;
255 backup_inverse = arg->inverse;
256 lbn = arg->lb_normal;
257 lbi = arg->lb_inverse;
258 ulbn = arg->use_lb_normal;
259 ulbi = arg->use_lb_inverse;
260
180 ret = 0; 261 ret = 0;
181 uint32_t allowed; 262 mm_normal = allowednextmove_mask(arg->moves, arg->nmoves) &
182 if(arg->nissbranch & MM_INVERSE) { 263 arg->movemask_normal;
183 allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); 264 mm_inverse = allowednextmove_mask(arg->premoves, arg->npremoves) &
265 arg->movemask_inverse;
266 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) {
267 arg->nmoves++;
184 for (m = 0; m < 18; m++) { 268 for (m = 0; m < 18; m++) {
185 if(allowed & (1 << m)) { 269 if (!(mm_normal & (1 << m)))
186 nextarg.npremoves = arg->npremoves + 1; 270 continue;
187 nextarg.premoves[arg->npremoves] = m; 271 arg->moves[arg->nmoves-1] = m;
188 nextarg.inverse = move(arg->inverse, m); 272 arg->cube = move(backup_cube, m);
189 nextarg.cube = premove(arg->cube, m); 273 arg->inverse = premove(backup_inverse, m);
190 ret += solve_h48_dfs(&nextarg); 274 arg->lb_inverse = lbi;
191 } 275 arg->use_lb_normal = false;
276 arg->use_lb_inverse = ulbi && m % 3 == 1;
277 n = solve_h48_dfs(arg);
278 if (n < 0)
279 return n;
280 ret += n;
192 } 281 }
282 arg->nmoves--;
193 } else { 283 } else {
194 allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); 284 arg->npremoves++;
195 for (m = 0; m < 18; m++) { 285 for (m = 0; m < 18; m++) {
196 if (allowed & (1 << m)) { 286 if(!(mm_inverse & (1 << m)))
197 nextarg.nmoves = arg->nmoves + 1; 287 continue;
198 nextarg.moves[arg->nmoves] = m; 288 arg->premoves[arg->npremoves-1] = m;
199 nextarg.cube = move(arg->cube, m); 289 arg->inverse = move(backup_inverse, m);
200 nextarg.inverse = premove(arg->inverse, m); 290 arg->cube = premove(backup_cube, m);
201 ret += solve_h48_dfs(&nextarg); 291 arg->lb_normal = lbn;
202 } 292 arg->use_lb_inverse = false;
293 arg->use_lb_normal = ulbn && m % 3 == 1;
294 n = solve_h48_dfs(arg);
295 if (n < 0)
296 return n;
297 ret += n;
203 } 298 }
299 arg->npremoves--;
204 } 300 }
205 301
206 arg->nodes_visited = nextarg.nodes_visited; 302 arg->cube = backup_cube;
207 arg->table_fallbacks = nextarg.table_fallbacks; 303 arg->inverse = backup_inverse;
304
208 return ret; 305 return ret;
209} 306}
210 307
308STATIC void *
309solve_h48_runthread(void *arg)
310{
311 int i, j;
312 solve_h48_task_t task;
313 dfsarg_solve_h48_t * dfsarg;
314 cube_t cube;
315
316 dfsarg = (dfsarg_solve_h48_t *)arg;
317 cube = dfsarg->start_cube;
318
319 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += THREADS) {
320 task = dfsarg->tasks[i];
321 memcpy(dfsarg->moves, task.moves, STARTING_MOVES);
322 dfsarg->cube = cube;
323 for (j = 0; j < STARTING_MOVES; j++)
324 dfsarg->cube = move(
325 dfsarg->cube, dfsarg->moves[j]);
326 dfsarg->inverse = inverse(dfsarg->cube);
327 dfsarg->nmoves = STARTING_MOVES;
328 dfsarg->npremoves = 0;
329 dfsarg->lb_normal = 0;
330 dfsarg->lb_inverse = 0;
331 dfsarg->use_lb_normal = false;
332 dfsarg->use_lb_inverse = false;
333 dfsarg->movemask_normal = MM_ALLMOVES;
334 dfsarg->movemask_inverse = MM_ALLMOVES;
335
336 solve_h48_dfs(dfsarg);
337 }
338
339 return NULL;
340}
341
342STATIC int64_t
343solve_h48_maketasks(
344 dfsarg_solve_h48_t *solve_arg,
345 dfsarg_solve_h48_maketasks_t *maketasks_arg,
346 solve_h48_task_t tasks[static STARTING_CUBES],
347 int *ntasks
348)
349{
350 int r;
351 int64_t appret;
352 uint8_t m, t;
353 uint32_t mm;
354 cube_t backup_cube;
355
356 if (issolved(maketasks_arg->cube)) {
357 if (maketasks_arg->nmoves > maketasks_arg->maxmoves ||
358 maketasks_arg->nmoves < maketasks_arg->minmoves ||
359 *solve_arg->nsols >= solve_arg->maxsolutions)
360 return NISSY_OK;
361 memcpy(solve_arg->moves,
362 maketasks_arg->moves, maketasks_arg->nmoves);
363 solve_arg->nmoves = maketasks_arg->nmoves;
364 appret = solve_h48_appendsolution(solve_arg);
365 return appret < 0 ? appret : NISSY_OK;
366 }
367
368 if (maketasks_arg->nmoves == STARTING_MOVES) {
369 tasks[*ntasks].cube = maketasks_arg->cube;
370 memcpy(tasks[*ntasks].moves,
371 maketasks_arg->moves, STARTING_MOVES);
372 (*ntasks)++;
373 return NISSY_OK;
374 }
375
376 mm = allowednextmove_mask(maketasks_arg->moves, maketasks_arg->nmoves);
377
378 maketasks_arg->nmoves++;
379 backup_cube = maketasks_arg->cube;
380 for (m = 0; m < 18; m++) {
381 if (!(mm & (1 << m)))
382 continue;
383 maketasks_arg->moves[maketasks_arg->nmoves-1] = m;
384 maketasks_arg->cube = move(backup_cube, m);
385 r = solve_h48_maketasks(
386 solve_arg, maketasks_arg, tasks, ntasks);
387 if (r < 0)
388 return r;
389
390 /* Avoid symmetry-equivalent moves from the starting cube */
391 if (maketasks_arg->nmoves == 1)
392 for (t = 0; t < 48; t++)
393 if (solve_arg->symmask0 &
394 (UINT64_C(1) << (uint64_t)t))
395 mm &= ~(UINT32_C(1) <<
396 (uint32_t)transform_move(m, t));
397 }
398 maketasks_arg->nmoves--;
399 maketasks_arg->cube = backup_cube;
400
401 return NISSY_OK;
402}
403
211STATIC int64_t 404STATIC int64_t
212solve_h48( 405solve_h48(
213 cube_t cube, 406 cube_t cube,
214 int8_t minmoves, 407 int8_t minmoves,
215 int8_t maxmoves, 408 int8_t maxmoves,
216 int8_t maxsolutions, 409 uint64_t maxsolutions,
217 uint64_t data_size, 410 uint64_t data_size,
218 const void *data, 411 const void *data,
219 uint64_t solutions_size, 412 uint64_t solutions_size,
@@ -221,61 +414,150 @@ solve_h48(
221 long long stats[static NISSY_SIZE_SOLVE_STATS] 414 long long stats[static NISSY_SIZE_SOLVE_STATS]
222) 415)
223{ 416{
417 int i, ntasks, eoesep_table_index;
418 int8_t d;
224 _Atomic int64_t nsols; 419 _Atomic int64_t nsols;
225 dfsarg_solveh48_t arg; 420 dfsarg_solve_h48_t arg[THREADS];
226 tableinfo_t info, fbinfo; 421 solve_h48_task_t tasks[STARTING_CUBES];
422 dfsarg_solve_h48_maketasks_t maketasks_arg;
423 long double fallback_rate, lookups_per_node;
424 uint64_t solutions_used, symmask, offset;
425 int64_t nodes_visited, table_lookups, table_fallbacks;
426 tableinfo_t info, fbinfo, fbinfo2;
427 const uint32_t *cocsepdata;
428 const uint8_t *fallback, *h48data;
429 const void *fallback2;
430 pthread_t thread[THREADS];
431 pthread_mutex_t solutions_mutex;
227 432
228 if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 433 if(readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
229 goto solve_h48_error_data; 434 goto solve_h48_error_data;
230 435
231 arg = (dfsarg_solveh48_t) { 436 cocsepdata = (uint32_t *)((char *)data + INFOSIZE);
232 .cube = cube, 437 h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE;
233 .inverse = inverse(cube),
234 .nsols = &nsols,
235 .maxsolutions = maxsolutions,
236 .h = info.h48h,
237 .k = info.bits,
238 .base = info.base,
239 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
240 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
241 .solutions_size = solutions_size,
242 .nextsol = &solutions,
243 .nodes_visited = 0,
244 .table_fallbacks = 0
245 };
246 438
439 /* Read fallback table(s) */
440 fallback = NULL;
441 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
442 goto solve_h48_error_data;
443 offset = info.next;
444 eoesep_table_index = 3;
247 if (info.bits == 2) { 445 if (info.bits == 2) {
248 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
249 goto solve_h48_error_data;
250 /* We only support h0k4 as fallback table */ 446 /* We only support h0k4 as fallback table */
251 if (fbinfo.h48h != 0 || fbinfo.bits != 4) 447 if (fbinfo.h48h != 0 || fbinfo.bits != 4)
252 goto solve_h48_error_data; 448 goto solve_h48_error_data;
253 arg.h48data_fallback = arg.h48data + info.next; 449 fallback = h48data + offset;
254 } else { 450 offset += fbinfo.next;
255 arg.h48data_fallback = NULL; 451 eoesep_table_index++;
452 }
453
454 if (readtableinfo_n(data_size, data, eoesep_table_index, &fbinfo2)
455 != NISSY_OK)
456 goto solve_h48_error_data;
457
458 /* Some heuristic check to see that it is eoesep */
459 if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL)
460 goto solve_h48_error_data;
461 fallback2 = h48data + offset;
462
463 symmask = symmetry_mask(cube);
464 for (i = 0; i < THREADS; i++) {
465 arg[i] = (dfsarg_solve_h48_t) {
466 .start_cube = cube,
467 .cube = cube,
468 .symmask0 = symmask,
469 .nsols = &nsols,
470 .maxsolutions = maxsolutions,
471 .h = info.h48h,
472 .k = info.bits,
473 .base = info.base,
474 .cocsepdata = cocsepdata,
475 .h48data = h48data,
476 .h48data_fallback_h0k4 = fallback,
477 .h48data_fallback_eoesep = fallback2,
478 .solutions_size = solutions_size,
479 .solutions_used = &solutions_used,
480 .solutions = &solutions,
481 .nodes_visited = 0,
482 .table_fallbacks = 0,
483 .table_lookups = 0,
484 .thread_id = i,
485 .solutions_mutex = &solutions_mutex,
486 };
487
256 } 488 }
257 489
258 nsols = 0; 490 nsols = 0;
259 for (arg.depth = minmoves; 491 solutions_used = 0;
260 arg.depth <= maxmoves && nsols < maxsolutions; 492
261 arg.depth++) 493 pthread_mutex_init(&solutions_mutex, NULL);
262 { 494
263 LOG("Found %" PRId64 " solutions, searching at depth %" 495 maketasks_arg = (dfsarg_solve_h48_maketasks_t) {
264 PRId8 "\n", nsols, arg.depth); 496 .cube = cube,
265 arg.nmoves = 0; 497 .nmoves = 0,
266 arg.npremoves = 0; 498 .minmoves = minmoves,
267 solve_h48_dfs(&arg); 499 .maxmoves = maxmoves,
500 };
501 ntasks = 0;
502 solve_h48_maketasks(&arg[0], &maketasks_arg, tasks, &ntasks);
503 if (ntasks < 0)
504 goto solve_h48_error_solutions_buffer;
505 if (*arg[0].nsols >= (int64_t)maxsolutions)
506 goto solve_h48_done;
507
508 for (i = 0; i < THREADS; i++) {
509 arg[i].ntasks = ntasks;
510 arg[i].tasks = tasks;
268 } 511 }
269 **arg.nextsol = '\0';
270 512
271 stats[0] = arg.nodes_visited; 513 LOG("Prepared %d tasks\n", ntasks);
272 stats[1] = arg.table_fallbacks; 514
273 LOG("Nodes visited: %lld\nTable fallbacks: %lld\n", 515 for (
274 arg.nodes_visited, arg.table_fallbacks); 516 d = MAX(minmoves, STARTING_MOVES + 1);
517 d <= maxmoves && nsols < (int64_t)maxsolutions;
518 d++
519 ) {
520 if (d >= 10)
521 LOG("Found %" PRId64 " solutions, searching at depth %"
522 PRId8 "\n", nsols, d);
523 for (i = 0; i < THREADS; i++) {
524 arg[i].depth = d;
525 pthread_create(
526 &thread[i], NULL, solve_h48_runthread, &arg[i]);
527 }
528 for (i = 0; i < THREADS; i++)
529 pthread_join(thread[i], NULL);
530 }
531
532solve_h48_done:
533 if (!solve_h48_appendchar(&arg[0], '\0'))
534 goto solve_h48_error_solutions_buffer;
535
536 nodes_visited = table_lookups = table_fallbacks = 0;
537 for (i = 0; i < THREADS; i++) {
538 nodes_visited += arg[i].nodes_visited;
539 table_fallbacks += arg[i].table_fallbacks;
540 table_lookups += arg[i].table_lookups;
541 }
542
543 stats[0] = nodes_visited;
544 stats[1] = table_lookups;
545 stats[2] = table_fallbacks;
546 lookups_per_node = table_lookups / (long double)nodes_visited;
547 fallback_rate = nodes_visited == 0 ? 0.0 :
548 (table_fallbacks * 100) / (long double)table_lookups;
549 LOG("Nodes visited: %" PRId64 "\n", nodes_visited);
550 LOG("Lookups: %" PRId64 " (%.3Lf per node)\n",
551 table_lookups, lookups_per_node);
552 LOG("Table fallbacks: %" PRId64 " (%.3Lf%%)\n",
553 table_fallbacks, fallback_rate);
275 554
276 return nsols; 555 return nsols;
277 556
278solve_h48_error_data: 557solve_h48_error_data:
279 LOG("solve_h48: error reading table\n"); 558 LOG("solve_h48: error reading table\n");
280 return NISSY_ERROR_DATA; 559 return NISSY_ERROR_DATA;
560
561solve_h48_error_solutions_buffer:
562 return NISSY_ERROR_BUFFER_SIZE;
281} 563}

Generated with cgit - Back to sebastiano.tronto.net