nissy.c (13846B)
1 #include <inttypes.h> 2 #include <limits.h> 3 #include <pthread.h> 4 #include <stdatomic.h> 5 #include <stdarg.h> 6 #include <stdbool.h> 7 #include <string.h> 8 9 #include "nissy.h" 10 #include "utils/utils.h" 11 #include "arch/arch.h" 12 #include "core/core.h" 13 #include "solvers/solvers.h" 14 15 long long parse_h48_solver( 16 const char *, uint8_t [static 1], uint8_t [static 1]); 17 STATIC bool checkdata(const char *, const tableinfo_t [static 1]); 18 STATIC bool distribution_equal(const uint64_t [static INFO_DISTRIBUTION_LEN], 19 const uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t); 20 STATIC long long write_result(cube_t, char [static NISSY_SIZE_B32]); 21 STATIC size_t my_strnlen(const char *, size_t); 22 STATIC long long nissy_dataid(const char *, char [static NISSY_DATAID_SIZE]); 23 STATIC long long nissy_gendata_unsafe( 24 const char *, unsigned long long, char *); 25 26 #define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F } 27 struct { 28 char *option; 29 void (*fix)(long long *, long long *, long long *, long long *); 30 } getcube_options[] = { 31 GETCUBE_OPTIONS("fix", getcube_fix), 32 GETCUBE_OPTIONS(NULL, NULL) 33 }; 34 35 long long 36 parse_h48_solver(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) 37 { 38 const char *fullbuf = buf; 39 40 buf += 3; 41 42 if (*buf != 'h') 43 goto parse_h48_solver_error; 44 buf++; 45 46 *h = atoi(buf); 47 48 for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++) 49 if (*buf == 0) 50 goto parse_h48_solver_error; 51 52 if (*buf != 'k') 53 goto parse_h48_solver_error; 54 buf++; 55 56 *k = atoi(buf); 57 58 return *h < 12 && (*k == 2 || (*k == 4 && *h == 0)) ? 0 : 1; 59 60 parse_h48_solver_error: 61 *h = 0; 62 *k = 0; 63 LOG("Error parsing solver: must be in \"h48h*k*\" format," 64 " but got %s\n", fullbuf); 65 return NISSY_ERROR_INVALID_SOLVER; 66 } 67 68 STATIC bool 69 checkdata(const char *buf, const tableinfo_t info[static 1]) 70 { 71 uint64_t distr[INFO_DISTRIBUTION_LEN]; 72 73 if (my_strnlen(info->solver, INFO_SOLVER_STRLEN) 74 == INFO_SOLVER_STRLEN) { 75 LOG("checkdata: error reading table info\n"); 76 return false; 77 } else if (!strncmp(info->solver, "cocsep", 6)) { 78 getdistribution_cocsep( 79 (uint32_t *)((char *)buf + INFOSIZE), distr); 80 } else if (!strncmp(info->solver, "h48", 3)) { 81 getdistribution_h48((uint8_t *)buf + INFOSIZE, distr, 82 info->h48h, info->bits); 83 } else if (!strncmp(info->solver, "coordinate solver for ", 22)) { 84 getdistribution_coord((uint8_t *)buf + INFOSIZE, 85 info->solver + 22, distr); 86 } else if (!strncmp(info->solver, "eoesep data for h48", 19)) { 87 return true; 88 } else if (!strncmp(info->solver, "coord helper table for ", 23)) { 89 return true; 90 } else { 91 LOG("checkdata: unknown solver %s\n", info->solver); 92 return false; 93 } 94 95 return distribution_equal(info->distribution, distr, info->maxvalue); 96 } 97 98 STATIC bool 99 distribution_equal( 100 const uint64_t expected[static INFO_DISTRIBUTION_LEN], 101 const uint64_t actual[static INFO_DISTRIBUTION_LEN], 102 uint8_t maxvalue 103 ) 104 { 105 int wrong; 106 uint8_t i; 107 108 for (i = 0, wrong = 0; i <= MAX(maxvalue, 20); i++) { 109 if (expected[i] != actual[i]) { 110 wrong++; 111 LOG("Value %" PRIu8 ": expected %" PRIu64 ", found %" 112 PRIu64 "\n", i, expected[i], actual[i]); 113 } 114 } 115 116 return wrong == 0; 117 } 118 119 STATIC long long 120 write_result(cube_t cube, char result[static NISSY_SIZE_B32]) 121 { 122 writecube("B32", cube, NISSY_SIZE_B32, result); 123 124 if (!issolvable(cube)) { 125 LOG("Warning: resulting cube is not solvable\n"); 126 return NISSY_WARNING_UNSOLVABLE; 127 } 128 129 return NISSY_OK; 130 } 131 132 STATIC size_t 133 my_strnlen(const char *str, size_t maxlen) 134 { 135 size_t i; 136 137 for (i = 0; i < maxlen; i++) 138 if (str[i] == '\0') 139 return i; 140 141 return maxlen; 142 } 143 144 long long 145 nissy_compose( 146 const char cube[static NISSY_SIZE_B32], 147 const char permutation[static NISSY_SIZE_B32], 148 char result[static NISSY_SIZE_B32] 149 ) 150 { 151 cube_t c, p, res; 152 long long err; 153 154 c = readcube("B32", cube); 155 156 if (!isconsistent(c)) { 157 LOG("Error in nissy_compose: given cube is invalid\n"); 158 err = NISSY_ERROR_INVALID_CUBE; 159 goto nissy_compose_error; 160 } 161 162 p = readcube("B32", permutation); 163 164 if (!isconsistent(p)) { 165 LOG("Error in nissy_compose: given permutation is invalid\n"); 166 err = NISSY_ERROR_INVALID_CUBE; 167 goto nissy_compose_error; 168 } 169 170 res = compose(c, p); 171 172 if (!isconsistent(res)) { 173 LOG("Unknown error: resulting cube is invalid\n"); 174 err = NISSY_ERROR_UNKNOWN; 175 goto nissy_compose_error; 176 } 177 178 return write_result(res, result); 179 180 nissy_compose_error: 181 writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result); 182 return err; 183 } 184 185 long long 186 nissy_inverse( 187 const char cube[static NISSY_SIZE_B32], 188 char result[static NISSY_SIZE_B32] 189 ) 190 { 191 cube_t c, res; 192 long long err; 193 194 c = readcube("B32", cube); 195 196 if (iserror(c)) { 197 LOG("Error in nissy_inverse: given cube is invalid\n"); 198 err = NISSY_ERROR_INVALID_CUBE; 199 goto nissy_inverse_error; 200 } 201 202 res = inverse(c); 203 204 if (!isconsistent(res)) { 205 LOG("Unknown error: inverted cube is invalid\n"); 206 err = NISSY_ERROR_UNKNOWN; 207 goto nissy_inverse_error; 208 } 209 210 return write_result(res, result); 211 212 nissy_inverse_error: 213 writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result); 214 return err; 215 } 216 217 long long 218 nissy_applymoves( 219 const char cube[static NISSY_SIZE_B32], 220 const char *moves, 221 char result[static NISSY_SIZE_B32] 222 ) 223 { 224 cube_t c, res; 225 long long err; 226 227 if (moves == NULL) { 228 LOG("Error: 'moves' argument is NULL\n"); 229 err = NISSY_ERROR_NULL_POINTER; 230 goto nissy_applymoves_error; 231 } 232 233 c = readcube("B32", cube); 234 235 if (!isconsistent(c)) { 236 LOG("Error in nissy_applymoves: given cube is invalid\n"); 237 err = NISSY_ERROR_INVALID_CUBE; 238 goto nissy_applymoves_error; 239 } 240 241 res = applymoves(c, moves); 242 243 if (!isconsistent(res)) { 244 /* Assume we got a reasonable error message from applymoves */ 245 err = NISSY_ERROR_INVALID_MOVES; 246 goto nissy_applymoves_error; 247 } 248 249 return write_result(res, result); 250 251 nissy_applymoves_error: 252 writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result); 253 return err; 254 } 255 256 long long 257 nissy_applytrans( 258 const char cube[static NISSY_SIZE_B32], 259 const char transformation[static NISSY_SIZE_TRANSFORMATION], 260 char result[static NISSY_SIZE_B32] 261 ) 262 { 263 cube_t c, res; 264 long long err; 265 266 c = readcube("B32", cube); 267 268 if (!isconsistent(c)) { 269 LOG("Error in nissy_applytrans: given cube is invalid\n"); 270 err = NISSY_ERROR_INVALID_CUBE; 271 goto nissy_applytrans_error; 272 } 273 274 res = applytrans(c, transformation); 275 276 if (!isconsistent(res)) { 277 /* Assume we got a reasonable error message from applytrans */ 278 err = NISSY_ERROR_INVALID_TRANS; 279 goto nissy_applytrans_error; 280 } 281 282 return write_result(res, result); 283 284 nissy_applytrans_error: 285 writecube("B32", ZERO_CUBE, NISSY_SIZE_B32, result); 286 return err; 287 } 288 289 long long 290 nissy_convert( 291 const char *format_in, 292 const char *format_out, 293 const char *cube_string, 294 unsigned result_size, 295 char result[result_size] 296 ) 297 { 298 cube_t c; 299 long long err; 300 301 if (format_in == NULL) { 302 LOG("Error: 'format_in' argument is NULL\n"); 303 err = NISSY_ERROR_NULL_POINTER; 304 goto nissy_convert_error; 305 } 306 307 if (format_out == NULL) { 308 LOG("Error: 'format_out' argument is NULL\n"); 309 err = NISSY_ERROR_NULL_POINTER; 310 goto nissy_convert_error; 311 } 312 313 if (cube_string == NULL) { 314 LOG("Error: 'cube_string' argument is NULL\n"); 315 err = NISSY_ERROR_NULL_POINTER; 316 goto nissy_convert_error; 317 } 318 319 c = readcube(format_in, cube_string); 320 321 if (!isconsistent(c)) { 322 err = NISSY_ERROR_INVALID_CUBE; 323 goto nissy_convert_error; 324 } 325 326 return writecube(format_out, c, result_size, result); 327 328 nissy_convert_error: 329 result[0] = '\0'; 330 return err; 331 } 332 333 long long 334 nissy_getcube( 335 long long ep, 336 long long eo, 337 long long cp, 338 long long co, 339 const char *options, 340 char result[static NISSY_SIZE_B32] 341 ) 342 { 343 int i; 344 cube_t c; 345 346 if (options == NULL) { 347 LOG("Error: 'options' argument is NULL\n"); 348 return NISSY_ERROR_NULL_POINTER; 349 } 350 351 for (i = 0; getcube_options[i].option != NULL; i++) 352 if (!strcmp(options, getcube_options[i].option)) 353 getcube_options[i].fix(&ep, &eo, &cp, &co); 354 355 c = getcube(ep, eo, cp, co); 356 357 if (!isconsistent(c)) { 358 LOG("Error: could not get cube with ep=%" PRId64 ", eo=%" 359 PRId64 ", cp=%" PRId64 ", co=%" PRId64 ".\n", 360 ep, eo, cp, co); 361 return NISSY_ERROR_OPTIONS; 362 } 363 364 return write_result(c, result); 365 } 366 367 long long 368 nissy_datainfo( 369 uint64_t data_size, 370 const char data[data_size], 371 void (*write)(const char *, ...) 372 ) 373 { 374 uint8_t i; 375 tableinfo_t info; 376 long long ret; 377 378 if ((size_t)data % 8 != 0) { 379 LOG("nissy_datainfo: buffere is not 8-byte aligned\n"); 380 return NISSY_ERROR_DATA; 381 } 382 383 ret = readtableinfo(data_size, data, &info); 384 if (ret != 0) 385 return ret; 386 387 write("\n---------\n\n"); 388 write("Table information for '%s'\n", info.solver); 389 write("\n"); 390 write("Size: %" PRIu64 " bytes\n", info.fullsize); 391 write("Entries: %" PRIu64 " (%" PRIu8 " bits per entry)", 392 info.entries, info.bits); 393 write("\n"); 394 395 switch (info.type) { 396 case TABLETYPE_PRUNING: 397 write("\n"); 398 write("Table distribution:\nValue\tPositions\n"); 399 for (i = 0; i <= info.maxvalue; i++) { 400 write("%" PRIu8 "\t%" PRIu64 "\n", 401 i + info.base, info.distribution[i]); 402 } 403 break; 404 case TABLETYPE_SPECIAL: 405 write("This is an ad-hoc table\n"); 406 break; 407 default: 408 LOG("datainfo: unknown table type\n"); 409 return NISSY_ERROR_DATA; 410 } 411 412 if (info.next != 0) 413 return nissy_datainfo( 414 data_size - info.next, (char *)data + info.next, write); 415 416 write("\n---------\n"); 417 418 return NISSY_OK; 419 } 420 421 STATIC long long 422 nissy_dataid(const char *solver, char dataid[static NISSY_DATAID_SIZE]) 423 { 424 if (!strncmp(solver, "h48", 3)) { 425 uint8_t h, k; 426 long long err; 427 if ((err = parse_h48_solver(solver, &h, &k)) != NISSY_OK) 428 return err; 429 /* TODO: also check that h and k are admissible */ 430 else strcpy(dataid, solver); 431 return err; 432 /* TODO: do this when moved parser */ 433 /* return dataid_h48(solver, dataid); */ 434 } else if (!strncmp(solver, "coord_", 6)) { 435 return dataid_coord(solver+6, dataid); 436 } else { 437 LOG("gendata: unknown solver %s\n", solver); 438 return NISSY_ERROR_INVALID_SOLVER; 439 } 440 } 441 442 long long 443 nissy_solverinfo( 444 const char *solver, 445 char dataid[static NISSY_DATAID_SIZE] 446 ) 447 { 448 long long err; 449 if ((err = nissy_dataid(solver, dataid)) != NISSY_OK) 450 return err; 451 452 /* gendata() handles a NULL *data as a "dryrun" request */ 453 return nissy_gendata_unsafe(solver, 0, NULL); 454 } 455 456 long long 457 nissy_gendata( 458 const char *solver, 459 unsigned long long data_size, 460 char data[data_size] 461 ) 462 { 463 return nissy_gendata_unsafe(solver, data_size, data); 464 } 465 466 STATIC long long 467 nissy_gendata_unsafe( 468 const char *solver, 469 unsigned long long data_size, 470 char *data 471 ) 472 { 473 long long parse_ret; 474 gendata_h48_arg_t arg; 475 476 if (solver == NULL) { 477 LOG("Error: 'solver' argument is NULL\n"); 478 return NISSY_ERROR_NULL_POINTER; 479 } 480 481 if ((size_t)data % 8 != 0) { 482 LOG("nissy_gendata: buffere is not 8-byte aligned\n"); 483 return NISSY_ERROR_DATA; 484 } 485 486 if (!strncmp(solver, "h48", 3)) { 487 arg.buf_size = data_size; 488 arg.buf = data; 489 parse_ret = parse_h48_solver(solver, &arg.h, &arg.k); 490 arg.maxdepth = 20; 491 if (parse_ret != NISSY_OK) 492 return parse_ret; 493 return gendata_h48(&arg); 494 } else if (!strncmp(solver, "coord_", 6)) { 495 return gendata_coord_dispatch(solver+6, data); 496 } else { 497 LOG("gendata: unknown solver %s\n", solver); 498 return NISSY_ERROR_INVALID_SOLVER; 499 } 500 } 501 502 long long 503 nissy_checkdata( 504 unsigned long long data_size, 505 const char data[data_size] 506 ) 507 { 508 char *buf; 509 tableinfo_t info; 510 int64_t err; 511 512 if ((size_t)data % 8 != 0) { 513 LOG("nissy_checkdata: buffere is not 8-byte aligned\n"); 514 return NISSY_ERROR_DATA; 515 } 516 517 for (buf = (char *)data; 518 (err = readtableinfo(data_size, buf, &info)) == NISSY_OK; 519 buf += info.next, data_size -= info.next) 520 { 521 if (!checkdata(buf, &info)) { 522 LOG("Error: data for solver '%s' is corrupted!\n", 523 info.solver); 524 return NISSY_ERROR_DATA; 525 } 526 527 if (info.next == 0) 528 break; 529 } 530 531 return err; 532 } 533 534 long long 535 nissy_solve( 536 const char cube[static NISSY_SIZE_B32], 537 const char *solver, 538 unsigned nissflag, 539 unsigned minmoves, 540 unsigned maxmoves, 541 unsigned maxsols, 542 int optimal, 543 int threads, 544 unsigned long long data_size, 545 const char data[data_size], 546 unsigned sols_size, 547 char sols[sols_size], 548 long long stats[static NISSY_SIZE_SOLVE_STATS] 549 ) 550 { 551 cube_t c; 552 long long parse_ret; 553 uint8_t h, k; 554 int t, opt; 555 556 if (solver == NULL) { 557 LOG("Error: 'solver' argument is NULL\n"); 558 return NISSY_ERROR_NULL_POINTER; 559 } 560 561 c = readcube_B32(cube); 562 563 if (!isconsistent(c)) { 564 LOG("solve: cube is invalid\n"); 565 return NISSY_ERROR_INVALID_CUBE; 566 } 567 568 if (!issolvable(c)) { 569 LOG("solve: cube is not solvable\n"); 570 return NISSY_ERROR_UNSOLVABLE_CUBE; 571 } 572 573 /* TODO: checks for minmoves, maxmoves, nissflag */ 574 575 if (maxsols == 0) { 576 LOG("solve: 'maxsols' is 0, returning no solution\n"); 577 return 0; 578 } 579 580 opt = optimal < 0 ? MAXLEN : optimal; 581 582 t = threads == 0 ? THREADS : threads; 583 if (t < 0) { 584 LOG("solve: 'threads' is negative. Please provide a " 585 "number of threads between 1 and %d\n", THREADS); 586 return NISSY_ERROR_OPTIONS; 587 } 588 if (t > THREADS) { 589 LOG("solve: 'threads' is above the maximum value of %d\n", 590 THREADS); 591 return NISSY_ERROR_OPTIONS; 592 } 593 594 if ((size_t)data % 8 != 0) { 595 LOG("nissy_solve: buffere is not 8-byte aligned\n"); 596 return NISSY_ERROR_DATA; 597 } 598 599 if (!strncmp(solver, "h48", 3)) { 600 parse_ret = parse_h48_solver(solver, &h, &k); 601 if (parse_ret != NISSY_OK) 602 return parse_ret; 603 return solve_h48(c, minmoves, maxmoves, maxsols, 604 opt, t, data_size, data, sols_size, sols, stats); 605 } else if (!strncmp(solver, "coord_", 6)) { 606 return solve_coord_dispatch(c, solver + 6, nissflag, 607 minmoves, maxmoves, maxsols, opt, t, data_size, data, 608 sols_size, sols); 609 } else { 610 LOG("solve: unknown solver '%s'\n", solver); 611 return NISSY_ERROR_INVALID_SOLVER; 612 } 613 } 614 615 long long 616 nissy_countmoves( 617 const char *moves 618 ) 619 { 620 if (moves == NULL) 621 return NISSY_ERROR_NULL_POINTER; 622 623 return countmoves(moves); 624 } 625 626 long long 627 nissy_setlogger( 628 void (*log)(const char *, ...) 629 ) 630 { 631 nissy_log = log; 632 return NISSY_OK; 633 }