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