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