solve.h (20268B)
1 #define H48_STARTING_MOVES 4 2 #define H48_STARTING_CUBES 43254 3 #define H48_SORT_TASKS_MIN_DEPTH 16 4 #define H48_LOG_PROGRESS_MIN_DEPTH 15 5 6 typedef struct { 7 cube_t cube; 8 uint8_t moves[H48_STARTING_MOVES]; 9 int64_t rank; 10 uint64_t tmask[H48_STARTING_MOVES]; 11 uint8_t pval; 12 } solve_h48_task_t; 13 14 typedef struct { 15 cube_t start_cube; 16 cube_t cube; 17 cube_t inverse; 18 int8_t target_depth; 19 solution_moves_t *solution_moves; 20 solution_settings_t *solution_settings; 21 const uint64_t *tmask; 22 solution_list_t *solution_list; 23 uint8_t lb_normal; 24 uint8_t lb_inverse; 25 uint8_t h; 26 uint8_t base; 27 const uint32_t *cocsepdata; 28 const unsigned char *h48data; 29 const unsigned char *eoesepdata; 30 uint64_t movemask_normal; 31 uint64_t movemask_inverse; 32 uint64_t nodes_visited; 33 uint64_t table_fallbacks; 34 uint64_t table_lookups; 35 int8_t threads; 36 int ntasks; 37 solve_h48_task_t *tasks; 38 int thread_id; 39 wrapthread_define_struct_mutex_t(*solutions_mutex); 40 wrapthread_atomic int *status; 41 wrapthread_atomic bool thread_done; 42 } dfsarg_solve_h48_t; 43 44 typedef struct { 45 cube_t cube; 46 int8_t nmoves; 47 uint8_t moves[H48_STARTING_MOVES]; 48 int8_t minmoves; 49 int8_t maxmoves; 50 int8_t *shortest_sol; 51 uint64_t tmask[H48_STARTING_MOVES]; 52 } dfsarg_solve_h48_maketasks_t; 53 54 typedef struct { 55 cube_t cube; 56 cube_t inverse; 57 uint64_t coord; 58 uint8_t m; 59 uint8_t pn; 60 uint8_t pi; 61 uint8_t stop; 62 } h48_prune_t; 63 64 STATIC long long solve_h48_dispatch(oriented_cube_t, const char *, unsigned, 65 unsigned, unsigned, unsigned, unsigned, unsigned, unsigned long long, 66 const unsigned char *, unsigned, char *, 67 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); 68 STATIC_INLINE void h48_prune_pipeline(dfsarg_solve_h48_t [static 1], 69 h48_prune_t [static NMOVES], uint8_t, bool); 70 STATIC_INLINE uint8_t h48_prune_lookup( 71 uint64_t, cube_t, dfsarg_solve_h48_t [static 1]); 72 STATIC_INLINE uint8_t h48_prune_lookup_nocoord( 73 cube_t, dfsarg_solve_h48_t [static 1]); 74 STATIC_INLINE void h48_prune_restore_normal(const h48_prune_t [static 1], 75 dfsarg_solve_h48_t [static 1], uint8_t); 76 STATIC_INLINE void h48_prune_restore_inverse(const h48_prune_t [static 1], 77 dfsarg_solve_h48_t [static 1], uint8_t); 78 STATIC int64_t solve_h48_maketasks( 79 dfsarg_solve_h48_t [static 1], dfsarg_solve_h48_maketasks_t [static 1], 80 solve_h48_task_t [static H48_STARTING_CUBES], int [static 1]); 81 STATIC void *solve_h48_runthread(void *); 82 STATIC int64_t solve_h48_dfs(dfsarg_solve_h48_t [static 1]); 83 STATIC void solve_h48_log_solutions(solution_list_t [static 1], size_t); 84 STATIC int solve_h48_compare_tasks(const void *, const void *); 85 STATIC int64_t solve_h48(oriented_cube_t, uint8_t, uint8_t, uint64_t, uint8_t, 86 uint8_t, uint64_t, const unsigned char *, size_t, char *, 87 long long [static NISSY_SIZE_SOLVE_STATS], int (*)(void *), void *); 88 89 STATIC long long solve_h48_dispatch( 90 oriented_cube_t oc, 91 const char *solver, 92 unsigned nissflag, 93 unsigned minmoves, 94 unsigned maxmoves, 95 unsigned maxsols, 96 unsigned optimal, 97 unsigned threads, 98 unsigned long long data_size, 99 const unsigned char *data, 100 unsigned sols_size, 101 char *sols, 102 long long stats[static NISSY_SIZE_SOLVE_STATS], 103 int (*poll_status)(void *), 104 void *poll_status_data 105 ) 106 { 107 uint8_t h; 108 long long err; 109 110 err = parse_h48h(solver, &h); 111 if (err != NISSY_OK) 112 return err; 113 114 return solve_h48(oc, minmoves, maxmoves, maxsols, optimal, threads, 115 data_size, data, sols_size, sols, stats, 116 poll_status, poll_status_data); 117 } 118 119 STATIC_INLINE uint8_t 120 h48_prune_lookup( 121 uint64_t coord, 122 cube_t cube, 123 dfsarg_solve_h48_t arg[static 1] 124 ) 125 { 126 uint8_t p, pmin, pe; 127 128 arg->table_lookups++; 129 p = get_h48_pval_and_min(arg->h48data, coord, &pmin); 130 if (p == 0) { 131 arg->table_fallbacks++; 132 pe = get_eoesep_pval_cube(arg->eoesepdata, cube); 133 return MAX(pmin, pe); 134 } else { 135 return p + arg->base; 136 } 137 } 138 139 STATIC_INLINE uint8_t 140 h48_prune_lookup_nocoord( 141 cube_t cube, 142 dfsarg_solve_h48_t arg[static 1] 143 ) 144 { 145 uint32_t cdata; 146 uint64_t coord; 147 148 get_h48_cdata(cube, arg->cocsepdata, &cdata); 149 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), arg->h); 150 return h48_prune_lookup(coord, cube, arg); 151 } 152 153 STATIC_INLINE void 154 h48_prune_pipeline( 155 dfsarg_solve_h48_t arg[static 1], 156 h48_prune_t prune[static NMOVES], 157 uint8_t target, 158 bool normal 159 ) 160 { 161 uint64_t i; 162 uint32_t cdata; 163 uint8_t m, p; 164 165 /* Stage 0: initialize the neighbors array */ 166 memset(prune, 0, NMOVES * sizeof(h48_prune_t)); 167 if (normal) { 168 for (m = 0; m < NMOVES; m++) { 169 prune[m].pi = m % 3 == 1 ? arg->lb_inverse : 0; 170 if (!(arg->movemask_normal & MM_SINGLE(m)) || 171 prune[m].pi > target) { 172 prune[m].stop = 1; 173 continue; 174 } 175 prune[m].cube = move(arg->cube, m); 176 prune[m].inverse = premove(arg->inverse, m); 177 prune[m].m = m; 178 arg->nodes_visited++; 179 } 180 } else { 181 for (m = 0; m < NMOVES; m++) { 182 prune[m].pi = m % 3 == 1 ? arg->lb_normal : 0; 183 if (!(arg->movemask_inverse & MM_SINGLE(m)) || 184 prune[m].pi > target) { 185 prune[m].stop = 1; 186 continue; 187 } 188 prune[m].cube = move(arg->inverse, m); 189 prune[m].inverse = premove(arg->cube, m); 190 prune[m].m = m; 191 arg->nodes_visited++; 192 } 193 } 194 195 /* We'll never get a bound higher than base + 3 */ 196 if (target > arg->base + 3) 197 return; 198 199 /* Stage 1: cdata and prefetch inverse */ 200 for (m = 0; m < NMOVES; m++) { 201 if (prune[m].stop) 202 continue; 203 204 p = get_h48_cdata(prune[m].inverse, arg->cocsepdata, &cdata); 205 if (p > target) { 206 prune[m].stop = 1; 207 continue; 208 } 209 if (prune[m].pi == 0) { 210 prune[m].coord = coord_h48_edges(prune[m].inverse, 211 COCLASS(cdata), TTREP(cdata), arg->h); 212 i = H48_INDEX(H48_LINE_EXT(prune[m].coord)); 213 prefetch(arg->h48data, i); 214 } 215 } 216 217 /* Stage 2: get pval from inverse, prefetch normal */ 218 for (m = 0; m < NMOVES; m++) { 219 if (prune[m].stop) 220 continue; 221 222 if (prune[m].pi == 0) { 223 prune[m].pi = h48_prune_lookup( 224 prune[m].coord, prune[m].inverse, arg); 225 if (prune[m].pi > target) { 226 prune[m].stop = 1; 227 continue; 228 } 229 } 230 231 p = get_h48_cdata(prune[m].cube, arg->cocsepdata, &cdata); 232 if (p > target) { 233 prune[m].stop = 1; 234 continue; 235 } 236 prune[m].coord = coord_h48_edges( 237 prune[m].cube, COCLASS(cdata), TTREP(cdata), arg->h); 238 i = H48_INDEX(H48_LINE_EXT(prune[m].coord)); 239 prefetch(arg->h48data, i); 240 } 241 242 /* Stage 3: get pval from normal */ 243 for (m = 0; m < NMOVES; m++) { 244 if (prune[m].stop) 245 continue; 246 247 prune[m].pn = h48_prune_lookup( 248 prune[m].coord, prune[m].cube, arg); 249 prune[m].stop = prune[m].pn > target; 250 } 251 } 252 253 STATIC_INLINE void 254 h48_prune_restore_normal( 255 const h48_prune_t prune[static 1], 256 dfsarg_solve_h48_t arg[static 1], 257 uint8_t target 258 ) 259 { 260 uint8_t nm; 261 262 arg->cube = prune->cube; 263 arg->inverse = prune->inverse; 264 arg->lb_inverse = prune->pi; 265 arg->lb_normal = prune->pn; 266 267 nm = arg->solution_moves->nmoves; 268 arg->solution_moves->moves[nm-1] = prune->m; 269 arg->movemask_normal = allowedmask[movebase(prune->m)]; 270 271 if (arg->lb_inverse == target) 272 arg->movemask_normal &= MM18_NOHALFTURNS; 273 if (arg->lb_normal == target) 274 arg->movemask_inverse &= MM18_NOHALFTURNS; 275 } 276 277 STATIC_INLINE void 278 h48_prune_restore_inverse( 279 const h48_prune_t prune[static 1], 280 dfsarg_solve_h48_t arg[static 1], 281 uint8_t target 282 ) 283 { 284 uint8_t nm; 285 286 arg->cube = prune->inverse; 287 arg->inverse = prune->cube; 288 arg->lb_inverse = prune->pn; 289 arg->lb_normal = prune->pi; 290 291 nm = arg->solution_moves->npremoves; 292 arg->solution_moves->premoves[nm-1] = prune->m; 293 arg->movemask_inverse = allowedmask[movebase(prune->m)]; 294 295 if (arg->lb_inverse == target) 296 arg->movemask_normal &= MM18_NOHALFTURNS; 297 if (arg->lb_normal == target) 298 arg->movemask_inverse &= MM18_NOHALFTURNS; 299 } 300 301 STATIC int64_t 302 solve_h48_dfs(dfsarg_solve_h48_t arg[static 1]) 303 { 304 int64_t ret, n; 305 uint8_t m, nm, nn, ni, target; 306 uint64_t mm_normal, mm_inverse; 307 cube_t cube, backup_cube, backup_inverse; 308 h48_prune_t prune[NMOVES]; 309 310 if (equal(arg->cube, SOLVED_CUBE) || /* Solved before target depth */ 311 arg->solution_list->nsols >= arg->solution_settings->maxsolutions) 312 return 0; 313 314 nn = arg->solution_moves->nmoves; 315 ni = arg->solution_moves->npremoves; 316 nm = nn + ni; 317 target = arg->target_depth - (nm + 1); 318 mm_normal = arg->movemask_normal; 319 mm_inverse = arg->movemask_inverse; 320 if (target == 0) { /* Last move */ 321 arg->solution_moves->nmoves++; 322 for (m = 0; m < NMOVES; m++) { 323 if (!(mm_normal & mm_inverse & MM_SINGLE(m))) 324 continue; 325 cube = move(arg->cube, m); 326 arg->solution_moves->moves[nn] = m; 327 arg->nodes_visited++; 328 if (!equal(cube, SOLVED_CUBE)) 329 continue; 330 wrapthread_mutex_lock(arg->solutions_mutex); 331 ret = appendsolution(arg->solution_moves, 332 H48_STARTING_MOVES, arg->tmask, 333 arg->solution_settings, arg->solution_list); 334 wrapthread_mutex_unlock(arg->solutions_mutex); 335 arg->solution_moves->nmoves--; 336 return ret; 337 } 338 arg->solution_moves->nmoves--; 339 return 0; 340 } 341 342 backup_cube = arg->cube; 343 backup_inverse = arg->inverse; 344 345 ret = 0; 346 if (popcount_u32(mm_normal) <= popcount_u32(mm_inverse)) { 347 h48_prune_pipeline(arg, prune, target, true); 348 arg->solution_moves->nmoves++; 349 for (m = 0; m < NMOVES; m++) { 350 if (prune[m].stop) 351 continue; 352 arg->movemask_normal = mm_normal; 353 arg->movemask_inverse = mm_inverse; 354 h48_prune_restore_normal(&prune[m], arg, target); 355 n = solve_h48_dfs(arg); 356 if (n < 0) 357 return n; 358 ret += n; 359 } 360 arg->solution_moves->nmoves--; 361 } else { 362 h48_prune_pipeline(arg, prune, target, false); 363 arg->solution_moves->npremoves++; 364 for (m = 0; m < NMOVES; m++) { 365 if (prune[m].stop) 366 continue; 367 arg->movemask_normal = mm_normal; 368 arg->movemask_inverse = mm_inverse; 369 h48_prune_restore_inverse(&prune[m], arg, target); 370 n = solve_h48_dfs(arg); 371 if (n < 0) 372 return n; 373 ret += n; 374 } 375 arg->solution_moves->npremoves--; 376 } 377 378 arg->cube = backup_cube; 379 arg->inverse = backup_inverse; 380 arg->movemask_normal = mm_normal; 381 arg->movemask_inverse = mm_inverse; 382 383 return ret; 384 } 385 386 STATIC void * 387 solve_h48_runthread(void *arg) 388 { 389 int i, j; 390 uint8_t lastmove; 391 int64_t d, f, nprev; 392 dfsarg_solve_h48_t *dfsarg; 393 394 dfsarg = (dfsarg_solve_h48_t *)arg; 395 396 nprev = 0; 397 for (i = dfsarg->thread_id; i < dfsarg->ntasks; i += dfsarg->threads) { 398 if (*dfsarg->status == NISSY_STATUS_STOP) 399 goto solve_h48_runthread_end; 400 while (*dfsarg->status == NISSY_STATUS_PAUSE) 401 msleep(BASE_SLEEP_TIME); 402 403 solution_moves_reset(dfsarg->solution_moves); 404 memcpy(dfsarg->solution_moves->moves, 405 dfsarg->tasks[i].moves, H48_STARTING_MOVES); 406 dfsarg->solution_moves->nmoves = H48_STARTING_MOVES; 407 408 dfsarg->cube = dfsarg->start_cube; 409 for (j = 0; j < H48_STARTING_MOVES; j++) 410 dfsarg->cube = 411 move(dfsarg->cube, dfsarg->tasks[i].moves[j]); 412 dfsarg->inverse = inverse(dfsarg->cube); 413 414 dfsarg->nodes_visited++; 415 if (dfsarg->tasks[i].pval + H48_STARTING_MOVES 416 > dfsarg->target_depth) 417 continue; 418 419 dfsarg->lb_normal = 0; 420 dfsarg->lb_inverse = 0; 421 dfsarg->movemask_normal = allowedmask[ 422 movebase(dfsarg->tasks[i].moves[H48_STARTING_MOVES-1])]; 423 dfsarg->movemask_inverse = MM18_ALLMOVES; 424 dfsarg->tmask = dfsarg->tasks[i].tmask; 425 426 solve_h48_dfs(dfsarg); 427 428 /* 429 We compute the "rank" of each taks, which is used in the next 430 step of the IDFS to sort them. This heuristically leads us 431 faster to a solution. The rank is computed by taking the 432 number of nodes visited, adjusted by a factor of about 433 sqrt(2)/sqrt(3) because there are more sequences starting with 434 U, R and F than with D, L and B, as we don't allow e.g. both 435 U D and D U, but only U D. 436 This trick was suggested by Chen Shuang, the implementation is 437 inspired by Andrew Skalski's vcube. 438 */ 439 lastmove = dfsarg->tasks[i].moves[H48_STARTING_MOVES-1]; 440 d = (int64_t)dfsarg->nodes_visited - nprev; 441 f = movebase(lastmove) % 2 == 0 ? 47525 : 58206; 442 dfsarg->tasks[i].rank = d * f; 443 nprev = dfsarg->nodes_visited; 444 } 445 446 solve_h48_runthread_end: 447 dfsarg->thread_done = true; 448 return NULL; 449 } 450 451 STATIC int64_t 452 solve_h48_maketasks( 453 dfsarg_solve_h48_t solve_arg[static 1], 454 dfsarg_solve_h48_maketasks_t mtarg[static 1], 455 solve_h48_task_t tasks[static H48_STARTING_CUBES], 456 int ntasks[static 1] 457 ) 458 { 459 int r; 460 int64_t appret; 461 uint8_t m, t; 462 uint64_t mm; 463 cube_t backup_cube; 464 solution_moves_t moves; 465 466 if (equal(mtarg->cube, SOLVED_CUBE)) { 467 if (mtarg->nmoves > mtarg->maxmoves || 468 mtarg->nmoves < mtarg->minmoves || 469 solutions_done(solve_arg->solution_list, 470 solve_arg->solution_settings, mtarg->nmoves)) 471 return NISSY_OK; 472 473 solution_moves_reset(&moves); 474 moves.nmoves = mtarg->nmoves; 475 memcpy(moves.moves, mtarg->moves, mtarg->nmoves); 476 477 appret = appendsolution(&moves, mtarg->nmoves, mtarg->tmask, 478 solve_arg->solution_settings, solve_arg->solution_list); 479 return appret < 0 ? appret : NISSY_OK; 480 } 481 482 if (mtarg->nmoves == H48_STARTING_MOVES) { 483 tasks[*ntasks].cube = mtarg->cube; 484 tasks[*ntasks].pval = 485 h48_prune_lookup_nocoord(mtarg->cube, solve_arg); 486 memcpy(tasks[*ntasks].moves, mtarg->moves, 487 H48_STARTING_MOVES * sizeof(uint8_t)); 488 memcpy(tasks[*ntasks].tmask, mtarg->tmask, 489 H48_STARTING_MOVES * sizeof(uint64_t)); 490 (*ntasks)++; 491 return NISSY_OK; 492 } 493 494 if (mtarg->nmoves == 0) { 495 mm = MM18_ALLMOVES; 496 } else { 497 m = mtarg->moves[mtarg->nmoves-1]; 498 mm = allowedmask[movebase(m)]; 499 } 500 501 mtarg->tmask[mtarg->nmoves] = symmetry_mask(mtarg->cube); 502 503 mtarg->nmoves++; 504 backup_cube = mtarg->cube; 505 for (m = 0; m < NMOVES; m++) { 506 if (!(mm & MM_SINGLE(m))) 507 continue; 508 509 mtarg->moves[mtarg->nmoves-1] = m; 510 mtarg->cube = move(backup_cube, m); 511 r = solve_h48_maketasks(solve_arg, mtarg, tasks, ntasks); 512 if (r < 0) 513 return r; 514 515 /* Avoid symmetry-equivalent moves from the starting cube */ 516 for (t = 0; t < NTRANS; t++) 517 if (mtarg->tmask[mtarg->nmoves-1] & TM_SINGLE(t)) 518 mm &= ~MM_SINGLE(transform_move(m, t)); 519 } 520 mtarg->nmoves--; 521 mtarg->cube = backup_cube; 522 523 return NISSY_OK; 524 } 525 526 STATIC void 527 solve_h48_log_solutions(solution_list_t s[static 1], size_t e) 528 { 529 size_t i; 530 char b; 531 while (e != s->used) { 532 LOG("[h48 solve] Found solution: "); 533 for (i = e; s->buf[i] != '\n' && s->buf[i] != '\0'; i++) ; 534 b = s->buf[i]; 535 s->buf[i] = '\0'; 536 LOG("%s\n", s->buf + e); 537 s->buf[i] = b; 538 e = i + 1; 539 } 540 } 541 542 STATIC int 543 solve_h48_compare_tasks(const void *x, const void *y) 544 { 545 int64_t nodes_x = ((solve_h48_task_t *)x)->rank; 546 int64_t nodes_y = ((solve_h48_task_t *)y)->rank; 547 548 /* Same as returning nodes_y - nodes_x, but avoids overflow */ 549 return (nodes_x < nodes_y) - (nodes_x > nodes_y); 550 } 551 552 STATIC int64_t 553 solve_h48( 554 oriented_cube_t oc, 555 uint8_t minmoves, 556 uint8_t maxmoves, 557 uint64_t maxsolutions, 558 uint8_t optimal, 559 uint8_t threads, 560 uint64_t data_size, 561 const unsigned char *data, 562 size_t solutions_size, 563 char *solutions, 564 long long stats[static NISSY_SIZE_SOLVE_STATS], 565 int (*poll_status)(void *), 566 void *poll_status_data 567 ) 568 { 569 int i, ntasks; 570 bool td; 571 wrapthread_atomic int status, prev_status; 572 size_t lastused; 573 int8_t d; 574 dfsarg_solve_h48_t arg[THREADS]; 575 solve_h48_task_t tasks[H48_STARTING_CUBES]; 576 dfsarg_solve_h48_maketasks_t mtarg; 577 long double fallback_rate, lookups_per_node; 578 uint64_t offset; 579 uint64_t nodes_visited, table_lookups, table_fallbacks; 580 tableinfo_t info, fbinfo2; 581 const uint32_t *cocsepdata; 582 const unsigned char *h48data; 583 const unsigned char *eoesep; 584 solution_moves_t solution_moves[THREADS]; 585 solution_settings_t settings; 586 solution_list_t sollist; 587 wrapthread_define_var_thread_t(thread[THREADS]); 588 wrapthread_define_var_mutex_t(solutions_mutex); 589 590 if (!solution_list_init(&sollist, solutions_size, solutions)) 591 goto solve_h48_error_solutions_buffer; 592 593 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) 594 goto solve_h48_error_data; 595 596 cocsepdata = (uint32_t *)(data + INFOSIZE); 597 h48data = data + COCSEP_FULLSIZE + INFOSIZE; 598 599 /* Read additional eoesep table */ 600 offset = info.next; 601 if (readtableinfo_n(data_size, data, 3, &fbinfo2) 602 != NISSY_OK) 603 goto solve_h48_error_data; 604 605 /* Some heuristic check to see that it is eoesep */ 606 if (fbinfo2.bits != 4 || fbinfo2.type != TABLETYPE_SPECIAL) 607 goto solve_h48_error_data; 608 eoesep = h48data + offset; 609 610 settings = (solution_settings_t) { 611 .unniss = true, 612 .maxmoves = maxmoves, 613 .maxsolutions = maxsolutions, 614 .optimal = optimal, 615 .orientation = oc.orientation, 616 }; 617 618 for (i = 0; i < threads; i++) { 619 arg[i] = (dfsarg_solve_h48_t) { 620 .start_cube = oc.cube, 621 .cube = oc.cube, 622 .h = info.h48h, 623 .base = info.base, 624 .cocsepdata = cocsepdata, 625 .h48data = h48data, 626 .eoesepdata = eoesep, 627 .solution_moves = &solution_moves[i], 628 .solution_settings = &settings, 629 .solution_list = &sollist, 630 .nodes_visited = 0, 631 .table_fallbacks = 0, 632 .table_lookups = 0, 633 .threads = threads, 634 .thread_id = i, 635 .solutions_mutex = &solutions_mutex, 636 .status = &status, 637 }; 638 639 } 640 641 wrapthread_mutex_init(&solutions_mutex, NULL); 642 643 mtarg = (dfsarg_solve_h48_maketasks_t) { 644 .cube = oc.cube, 645 .nmoves = 0, 646 .minmoves = minmoves, 647 .maxmoves = maxmoves, 648 }; 649 ntasks = 0; 650 solve_h48_maketasks(&arg[0], &mtarg, tasks, &ntasks); 651 if (ntasks < 0) 652 goto solve_h48_error_solutions_buffer; 653 if (solutions_done(&sollist, &settings, 654 MAX(minmoves, H48_STARTING_MOVES))) 655 goto solve_h48_done; 656 657 for (i = 0; i < threads; i++) { 658 arg[i].ntasks = ntasks; 659 arg[i].tasks = tasks; 660 } 661 662 LOG("[H48 solve] Prepared %d tasks\n", ntasks); 663 664 solve_h48_log_solutions(&sollist, 0); 665 lastused = sollist.used; 666 status = poll_status == NULL ? NISSY_STATUS_RUN : 667 poll_status(poll_status_data); 668 if (!NISSY_CANSLEEP) { 669 LOG("[solve h48] Pause / Stop / Resume functionality won't " 670 "be available on this system (can't sleep()).\n"); 671 } 672 for ( 673 d = MAX(minmoves, H48_STARTING_MOVES + 1); 674 !(solutions_done(&sollist, &settings, d)) && 675 status != NISSY_STATUS_STOP; 676 d++ 677 ) { 678 if (d >= H48_LOG_PROGRESS_MIN_DEPTH) { 679 LOG("[H48 solve] Found %" PRIu64 " solutions, " 680 "searching at depth %" PRId8 "\n", 681 sollist.nsols, d); 682 } 683 684 if (d >= H48_SORT_TASKS_MIN_DEPTH) 685 qsort(tasks, ntasks, sizeof(solve_h48_task_t), 686 solve_h48_compare_tasks); 687 688 for (i = 0; i < threads; i++) { 689 arg[i].target_depth = d; 690 arg[i].thread_done = false; 691 wrapthread_create( 692 &thread[i], NULL, solve_h48_runthread, &arg[i]); 693 } 694 695 /* Log solutions and handle pause / stop / resume */ 696 if (poll_status != NULL && d >= 15 && NISSY_CANSLEEP) { 697 td = false; 698 while (!td && status != NISSY_STATUS_STOP) { 699 msleep(BASE_SLEEP_TIME); 700 701 wrapthread_mutex_lock(&solutions_mutex); 702 solve_h48_log_solutions(&sollist, lastused); 703 lastused = sollist.used; 704 wrapthread_mutex_unlock(&solutions_mutex); 705 706 prev_status = status; 707 status = poll_status(poll_status_data); 708 if (status != prev_status) { 709 if (status == NISSY_STATUS_PAUSE) 710 LOG("[H48 solve] Paused\n"); 711 if (status == NISSY_STATUS_RUN) 712 LOG("[H48 solve] Resumed\n"); 713 } 714 715 for (td = true, i = 0; i < threads; i++) 716 td = td && arg[i].thread_done; 717 } 718 } 719 720 for (i = 0; i < threads; i++) 721 wrapthread_join(thread[i], NULL); 722 723 solve_h48_log_solutions(&sollist, lastused); 724 lastused = sollist.used; 725 } 726 727 if (status == NISSY_STATUS_STOP) { 728 LOG("[H48 solve] Received stop request, ending solution " 729 "search early.\n"); 730 } 731 732 solve_h48_done: 733 nodes_visited = table_lookups = table_fallbacks = 0; 734 for (i = 0; i < threads; i++) { 735 nodes_visited += arg[i].nodes_visited; 736 table_fallbacks += arg[i].table_fallbacks; 737 table_lookups += arg[i].table_lookups; 738 } 739 740 stats[0] = nodes_visited; 741 stats[1] = table_lookups; 742 stats[2] = table_fallbacks; 743 lookups_per_node = table_lookups / (long double)nodes_visited; 744 fallback_rate = nodes_visited == 0 ? 0.0 : 745 (table_fallbacks * 100) / (long double)table_lookups; 746 LOG("[H48 solve] Nodes visited: %" PRId64 "\n", nodes_visited); 747 LOG("[H48 solve] Lookups: %" PRId64 " (%.3Lf per node)\n", 748 table_lookups, lookups_per_node); 749 LOG("[H48 solve] Table fallbacks: %" PRId64 " (%.3Lf%%)\n", 750 table_fallbacks, fallback_rate); 751 752 return sollist.nsols; 753 754 solve_h48_error_data: 755 LOG("[H48 solve] Error reading data table\n"); 756 return NISSY_ERROR_DATA; 757 758 solve_h48_error_solutions_buffer: 759 return NISSY_ERROR_BUFFER_SIZE; 760 }