moves.h (15171B)
1 #define MOVE(M, c) compose(c, MOVE_CUBE_ ## M) 2 #define PREMOVE(M, c) compose(MOVE_CUBE_ ## M, c) 3 4 STATIC uint8_t readmove(char); 5 STATIC int64_t readmoves(const char *, 6 size_t, size_t, size_t *, size_t *, uint8_t *, uint8_t *); 7 STATIC int64_t readmoves_struct(const char *, moves_struct_t [static 1]); 8 STATIC int64_t countmoves(const char *); 9 STATIC bool moves_struct_equal( 10 const moves_struct_t [static 1], const moves_struct_t [static 1]); 11 STATIC long long comparemoves(const char *, const char *); 12 STATIC uint8_t readmodifier(char); 13 STATIC int64_t writemoves(size_t, const uint8_t *, size_t, char *); 14 STATIC int64_t writemoves_struct( 15 const moves_struct_t [static 1], size_t, char *); 16 17 STATIC_INLINE bool allowednextmove(uint8_t, uint8_t); 18 STATIC bool allowedmoves(size_t, const uint8_t *); 19 20 STATIC_INLINE uint8_t movebase(uint8_t); 21 STATIC_INLINE uint8_t moveaxis(uint8_t); 22 STATIC_INLINE bool isbase(uint8_t); 23 STATIC_INLINE bool parallel(uint8_t, uint8_t); 24 STATIC_INLINE uint8_t moveopposite(uint8_t); 25 STATIC_INLINE uint8_t reorient_move(uint8_t, uint8_t); 26 STATIC_INLINE uint8_t inverse_reorient_move(uint8_t, uint8_t); 27 STATIC_INLINE uint8_t movefollow(uint8_t); 28 STATIC uint8_t transform_move_basic(uint8_t, uint8_t); 29 STATIC uint8_t transform_move(uint8_t, uint8_t); 30 31 STATIC cube_t move(cube_t, uint8_t); 32 STATIC cube_t premove(cube_t, uint8_t); 33 STATIC uint8_t inverse_move(uint8_t); 34 STATIC void sortparallel_moves(size_t, uint8_t*); 35 STATIC bool are_lastmoves_singlecw(size_t, const uint8_t*); 36 37 STATIC int64_t move_variations(const char *, const char *, size_t, char *); 38 STATIC int64_t move_variations_lastqt( 39 const moves_struct_t [static 1], size_t, char *); 40 STATIC int64_t move_variations_unniss( 41 const moves_struct_t [static 1], size_t, char *); 42 43 #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \ 44 RET_ERROR, ARG_ACTION) \ 45 const char *VAR_B; \ 46 uint8_t VAR_MOVE_NOMOD, VAR_MOD; \ 47 bool VAR_IN_PARENTHESES = false; \ 48 for (VAR_B = ARG_BUF, ARG_C = 0; *VAR_B != '\0'; VAR_B++, ARG_C++) { \ 49 while (*VAR_B == ' ' || *VAR_B == '\t' || *VAR_B == '\n') \ 50 VAR_B++; \ 51 if (*VAR_B == '\0' || ARG_C == ARG_MAX) \ 52 break; \ 53 if (*VAR_B == '(') { \ 54 if (VAR_IN_PARENTHESES) { \ 55 LOG("Nested parentheses in move sequence\n"); \ 56 return RET_ERROR; \ 57 } \ 58 VAR_IN_PARENTHESES = true; \ 59 continue; \ 60 } \ 61 if (*VAR_B == ')') { \ 62 if (!VAR_IN_PARENTHESES) { \ 63 LOG("Mismatched ')' in move sequence\n"); \ 64 return RET_ERROR; \ 65 } \ 66 VAR_IN_PARENTHESES = false; \ 67 continue; \ 68 } \ 69 if ((VAR_MOVE_NOMOD = readmove(*VAR_B)) == UINT8_ERROR) { \ 70 LOG("Unknown move: %c\n", *VAR_B); \ 71 return RET_ERROR; \ 72 } \ 73 if (*(VAR_B+1) == 'w') { \ 74 VAR_MOVE_NOMOD += 18; \ 75 VAR_B++; \ 76 } \ 77 if ((VAR_MOD = readmodifier(*(VAR_B+1))) != 0) \ 78 VAR_B++; \ 79 ARG_MOVE = VAR_MOVE_NOMOD + VAR_MOD; \ 80 ARG_ACTION \ 81 } \ 82 if (VAR_IN_PARENTHESES) { \ 83 LOG("Mismatched '(' in move sequence\n"); \ 84 return RET_ERROR; \ 85 } 86 87 STATIC uint8_t 88 readmove(char c) 89 { 90 switch (c) { 91 case 'U': 92 return MOVE_U; 93 case 'D': 94 return MOVE_D; 95 case 'R': 96 return MOVE_R; 97 case 'L': 98 return MOVE_L; 99 case 'F': 100 return MOVE_F; 101 case 'B': 102 return MOVE_B; 103 case 'M': 104 return MOVE_M; 105 case 'S': 106 return MOVE_S; 107 case 'E': 108 return MOVE_E; 109 case 'x': 110 return MOVE_x; 111 case 'y': 112 return MOVE_y; 113 case 'z': 114 return MOVE_z; 115 default: 116 return UINT8_ERROR; 117 } 118 } 119 120 STATIC uint8_t 121 readmodifier(char c) 122 { 123 switch (c) { 124 case '1': /* Fallthrough */ 125 case '2': /* Fallthrough */ 126 case '3': 127 return c - '0' - 1; 128 case '\'': 129 return 2; 130 default: 131 return 0; 132 } 133 } 134 135 STATIC int64_t 136 readmoves( 137 const char *buf, 138 size_t nsize, 139 size_t invsize, 140 size_t *n, 141 size_t *i, 142 uint8_t *normal, 143 uint8_t *inverse 144 ) 145 { 146 uint8_t m; 147 uint64_t c; 148 149 *n = *i = 0; 150 FOREACH_READMOVE(buf, m, c, nsize+invsize, NISSY_ERROR_INVALID_MOVES, 151 if (!VAR_IN_PARENTHESES) { 152 if (*n >= nsize-1) { 153 LOG("Error in readmoves: normal buffer\n"); 154 return NISSY_ERROR_BUFFER_SIZE; 155 } 156 normal[(*n)++] = m; 157 } else { 158 if (*i >= invsize-1) { 159 LOG("Error in readmoves: inverse buffer\n"); 160 return NISSY_ERROR_BUFFER_SIZE; 161 } 162 inverse[(*i)++] = m; 163 } 164 ) 165 166 return (int64_t)c; 167 } 168 169 STATIC int64_t 170 readmoves_struct(const char *moves, moves_struct_t ret[static 1]) 171 { 172 return readmoves(moves, NISSY_SIZE_MOVES, NISSY_SIZE_MOVES, 173 &ret->nnormal, &ret->ninverse, ret->normal, ret->inverse); 174 } 175 176 STATIC int64_t 177 countmoves(const char *buf) 178 { 179 uint8_t m; 180 uint64_t c; 181 int64_t count; 182 183 count = 0; 184 FOREACH_READMOVE(buf, m, c, INT_MAX, NISSY_ERROR_INVALID_MOVES, 185 count += m <= MOVE_Bw3 ? 1 : (m <= MOVE_E3 ? 2 : 0); 186 ) 187 188 return count; 189 } 190 191 STATIC bool 192 moves_struct_equal( 193 const moves_struct_t ms1[static 1], 194 const moves_struct_t ms2[static 1] 195 ) 196 { 197 size_t i; 198 199 if (ms1->nnormal != ms2->nnormal || ms1->ninverse != ms2->ninverse) 200 return false; 201 202 for (i = 0; i < ms1->nnormal; i++) 203 if (ms1->normal[i] != ms2->normal[i]) 204 return false; 205 206 for (i = 0; i < ms1->ninverse; i++) 207 if (ms1->inverse[i] != ms2->inverse[i]) 208 return false; 209 210 return true; 211 } 212 213 STATIC long long 214 comparemoves(const char *moves1, const char *moves2) 215 { 216 int64_t err; 217 moves_struct_t ms1, ms2; 218 219 if ((err = readmoves_struct(moves1, &ms1)) < 0) 220 return err; 221 sortparallel_moves(ms1.nnormal, ms1.normal); 222 sortparallel_moves(ms1.ninverse, ms1.inverse); 223 224 if ((err = readmoves_struct(moves2, &ms2)) < 0) 225 return err; 226 sortparallel_moves(ms2.nnormal, ms2.normal); 227 sortparallel_moves(ms2.ninverse, ms2.inverse); 228 229 if (moves_struct_equal(&ms1, &ms2)) 230 return NISSY_COMPARE_MOVES_EQUAL; 231 232 /* 233 TODO: more types of move comparison 234 - up to moving rotations around 235 - up to rotation 236 - up transformation (including mirror or not including it) 237 - ... 238 */ 239 240 return NISSY_COMPARE_MOVES_DIFFERENT; 241 } 242 243 STATIC int64_t 244 writemoves( 245 size_t nmoves, 246 const uint8_t *m, 247 size_t buf_size, 248 char *buf 249 ) 250 { 251 size_t i, len, w; 252 const char *s; 253 254 if (buf_size == 0) { 255 LOG("Error: cannot write moves to buffer of size 0.\n"); 256 return NISSY_ERROR_BUFFER_SIZE; 257 } 258 259 for (i = 0, w = 0; i < nmoves; i++, w++) { 260 s = movestr[m[i]]; 261 len = strlen(s); 262 if (len + w >= buf_size) { 263 LOG("Error: the given buffer is too small for " 264 "writing the given moves.\n"); 265 goto writemoves_error; 266 } 267 memcpy(buf+w, s, len); 268 w += len; 269 buf[w] = ' '; 270 } 271 272 if (w > 0) w--; /* Remove last space */ 273 buf[w] = '\0'; 274 275 return (int64_t)w; 276 277 writemoves_error: 278 *buf = '\0'; 279 return NISSY_ERROR_BUFFER_SIZE; 280 } 281 282 STATIC int64_t 283 writemoves_struct( 284 const moves_struct_t moves[static 1], 285 size_t buf_size, 286 char *buf 287 ) 288 { 289 int64_t w, u; 290 291 w = 0; 292 if (moves->nnormal > 0) { 293 w = writemoves(moves->nnormal, moves->normal, buf_size, buf); 294 if (w < 0) 295 goto writemoves_struct_error; 296 } 297 298 u = 0; 299 if (moves->ninverse > 0) { 300 if (moves->nnormal > 0) { 301 if ((size_t)w >= buf_size) 302 goto writemoves_struct_error; 303 buf[w++] = ' '; 304 } 305 if ((size_t)w >= buf_size) 306 goto writemoves_struct_error; 307 buf[w++] = '('; 308 309 u = writemoves(moves->ninverse, moves->inverse, 310 buf_size-w, buf+w); 311 if (u < 0) 312 goto writemoves_struct_error; 313 314 if ((size_t)w >= buf_size) 315 goto writemoves_struct_error; 316 buf[w + (u++)] = ')'; 317 } 318 319 buf[u+w] = '\0'; 320 return u+w; 321 322 writemoves_struct_error: 323 buf[w] = '\0'; 324 return NISSY_ERROR_BUFFER_SIZE; 325 } 326 327 STATIC_INLINE bool 328 allowednextmove(uint8_t m1, uint8_t m2) 329 { 330 return allowedmask[movebase(m1)] & MM_SINGLE(m2); 331 } 332 333 STATIC bool 334 allowedmoves(size_t n, const uint8_t *m) 335 { 336 uint8_t j; 337 338 for (j = 1; j < n; j++) 339 if (!allowednextmove(m[j-1], m[j])) 340 return false; 341 342 return true; 343 } 344 345 STATIC_INLINE uint8_t 346 movebase(uint8_t move) 347 { 348 return move / 3; 349 } 350 351 STATIC_INLINE uint8_t 352 moveaxis(uint8_t move) 353 { 354 return move / 6; 355 } 356 357 STATIC_INLINE bool 358 isbase(uint8_t move) 359 { 360 return move == 3 * movebase(move); 361 } 362 363 STATIC_INLINE bool 364 parallel(uint8_t m1, uint8_t m2) 365 { 366 return moveaxis(movefollow(m1)) == moveaxis(movefollow(m2)); 367 } 368 369 STATIC_INLINE uint8_t 370 moveopposite(uint8_t move) 371 { 372 return movebase(move) == 2 * moveaxis(move) ? move + 3 : move - 3; 373 } 374 375 STATIC_INLINE uint8_t 376 reorient_move(uint8_t m, uint8_t or) 377 { 378 return transform_move(m, orientation_trans[or]); 379 } 380 381 STATIC_INLINE uint8_t 382 inverse_reorient_move(uint8_t m, uint8_t or) 383 { 384 return transform_move(m, inverse_trans_table[orientation_trans[or]]); 385 } 386 387 STATIC_INLINE uint8_t 388 movefollow(uint8_t move) 389 { 390 uint8_t b, m; 391 392 if (move <= MOVE_B3) 393 return move; 394 395 if (move <= MOVE_Bw3) 396 return move - MOVE_Uw; 397 398 b = UINT8_C(3) * (move / UINT8_C(3)); 399 m = move - b; 400 switch (b) { 401 case MOVE_M: 402 return MOVE_L + m; 403 case MOVE_S: 404 return MOVE_F + m; 405 case MOVE_E: 406 return MOVE_D + m; 407 case MOVE_x: 408 return MOVE_R + m; 409 case MOVE_y: 410 return MOVE_U + m; 411 case MOVE_z: 412 return MOVE_F + m; 413 default: 414 return UINT8_ERROR; 415 } 416 } 417 418 STATIC cube_t 419 move(cube_t c, uint8_t m) 420 { 421 switch (m) { 422 case MOVE_U: 423 return MOVE(U, c); 424 case MOVE_U2: 425 return MOVE(U2, c); 426 case MOVE_U3: 427 return MOVE(U3, c); 428 case MOVE_D: 429 return MOVE(D, c); 430 case MOVE_D2: 431 return MOVE(D2, c); 432 case MOVE_D3: 433 return MOVE(D3, c); 434 case MOVE_R: 435 return MOVE(R, c); 436 case MOVE_R2: 437 return MOVE(R2, c); 438 case MOVE_R3: 439 return MOVE(R3, c); 440 case MOVE_L: 441 return MOVE(L, c); 442 case MOVE_L2: 443 return MOVE(L2, c); 444 case MOVE_L3: 445 return MOVE(L3, c); 446 case MOVE_F: 447 return MOVE(F, c); 448 case MOVE_F2: 449 return MOVE(F2, c); 450 case MOVE_F3: 451 return MOVE(F3, c); 452 case MOVE_B: 453 return MOVE(B, c); 454 case MOVE_B2: 455 return MOVE(B2, c); 456 case MOVE_B3: 457 return MOVE(B3, c); 458 default: 459 LOG("move error: %" PRIu8 " is not a basic move\n", m); 460 return ZERO_CUBE; 461 } 462 } 463 464 STATIC uint8_t 465 transform_move_basic(uint8_t m, uint8_t t) 466 { 467 uint8_t a, base, modifier; 468 469 if (t > 47) { 470 LOG("transform_move: invalid trans %" PRIu8 "\n", t); 471 return UINT8_ERROR; 472 } 473 474 a = moveaxis(m); 475 base = trans_move_table[t][a]; 476 if (movebase(m) != 2 * a) 477 base = moveopposite(base); 478 479 modifier = m % 3; 480 if (t >= TRANS_UFm) 481 modifier = 2 - modifier; 482 483 return base + modifier; 484 } 485 486 STATIC uint8_t 487 transform_move(uint8_t m, uint8_t t) 488 { 489 if (m <= MOVE_B3) 490 return transform_move_basic(m, t); 491 492 if (m >= MOVE_Uw && m <= MOVE_Bw3) 493 return 18+transform_move_basic(m-18, t); 494 495 if (m >= MOVE_M && m <= MOVE_E3) 496 return basic_to_slice[ 497 transform_move_basic(slice_to_basic[m], t)]; 498 499 if (m >= MOVE_x && m <= MOVE_z3) 500 return basic_to_rotation[ 501 transform_move_basic(rotation_to_basic[m], t)]; 502 503 LOG("transform_move: invalid move %" PRIu8 "\n", m); 504 return UINT8_ERROR; 505 } 506 507 /* Applies the INVERSE of m BEFORE the scramble corresponding to c */ 508 STATIC cube_t 509 premove(cube_t c, uint8_t m) 510 { 511 switch (m) { 512 case MOVE_U: 513 return PREMOVE(U3, c); 514 case MOVE_U2: 515 return PREMOVE(U2, c); 516 case MOVE_U3: 517 return PREMOVE(U, c); 518 case MOVE_D: 519 return PREMOVE(D3, c); 520 case MOVE_D2: 521 return PREMOVE(D2, c); 522 case MOVE_D3: 523 return PREMOVE(D, c); 524 case MOVE_R: 525 return PREMOVE(R3, c); 526 case MOVE_R2: 527 return PREMOVE(R2, c); 528 case MOVE_R3: 529 return PREMOVE(R, c); 530 case MOVE_L: 531 return PREMOVE(L3, c); 532 case MOVE_L2: 533 return PREMOVE(L2, c); 534 case MOVE_L3: 535 return PREMOVE(L, c); 536 case MOVE_F: 537 return PREMOVE(F3, c); 538 case MOVE_F2: 539 return PREMOVE(F2, c); 540 case MOVE_F3: 541 return PREMOVE(F, c); 542 case MOVE_B: 543 return PREMOVE(B3, c); 544 case MOVE_B2: 545 return PREMOVE(B2, c); 546 case MOVE_B3: 547 return PREMOVE(B, c); 548 default: 549 LOG("premove error: unknown move %" PRIu8 "\n", m); 550 return ZERO_CUBE; 551 } 552 } 553 554 STATIC uint8_t 555 inverse_move(uint8_t m) 556 { 557 return m - 2 * (m % 3) + 2; 558 } 559 560 STATIC void 561 sortparallel_moves(size_t n, uint8_t *moves) 562 { 563 uint8_t i; 564 565 if (n < 2) 566 return; 567 568 for (i = 0; i < n-1; i++) 569 if (parallel(moves[i], moves[i+1]) && moves[i] > moves[i+1]) 570 SWAP(moves[i], moves[i+1]); 571 } 572 573 STATIC bool 574 are_lastmoves_singlecw(size_t n, const uint8_t *moves) 575 { 576 bool two; 577 578 if (n == 0) 579 return true; 580 581 two = n > 1 && parallel(moves[n-1], moves[n-2]); 582 583 return isbase(moves[n-1]) && (!two || isbase(moves[n-2])); 584 } 585 586 STATIC int64_t 587 move_variations( 588 const char *moves, 589 const char *variation, 590 size_t result_size, 591 char *result 592 ) 593 { 594 moves_struct_t m; 595 int64_t err; 596 597 err = readmoves_struct(moves, &m); 598 if (err < 0) { 599 LOG("[variations] Error reading moves.\n"); 600 return err; 601 } 602 603 if (!strcmp(variation, "lastqt")) { 604 return move_variations_lastqt(&m, result_size, result); 605 } else if (!strcmp(variation, "unniss")) { 606 return move_variations_unniss(&m, result_size, result); 607 } else { 608 LOG("[variations] Error: unknown variation '%s'\n", variation); 609 return NISSY_ERROR_INVALID_VARIATION; 610 } 611 } 612 613 STATIC int64_t 614 move_variations_lastqt( 615 const moves_struct_t s[static 1], 616 size_t result_size, 617 char *result 618 ) 619 { 620 uint8_t n1, n2, i1, i2, swapn1, swapn2, swapi1, swapi2, i, j, k, l; 621 int8_t in1, in2, ii1, ii2; 622 int64_t err, count; 623 size_t u; 624 moves_struct_t ss; 625 626 in1 = s->nnormal-1; 627 in2 = s->nnormal-2; 628 ii1 = s->ninverse-1; 629 ii2 = s->ninverse-2; 630 631 n1 = in1 >= 0 ? s->normal[in1] : UINT8_ERROR; 632 n2 = in2 >= 0 ? s->normal[in2] : UINT8_ERROR; 633 i1 = ii1 >= 0 ? s->inverse[ii1] : UINT8_ERROR; 634 i2 = ii2 >= 0 ? s->inverse[ii2] : UINT8_ERROR; 635 636 swapn1 = in1 >= 0 && n1 % 3 != 1 ? 1 : 0; 637 swapn2 = swapn1 && in2 >= 0 && n2 % 3 != 1 && parallel(n1, n2) ? 1 : 0; 638 swapi1 = ii1 >= 0 && i1 % 3 != 1 ? 1 : 0; 639 swapi2 = swapi1 && ii2 >= 0 && i2 % 3 != 1 && parallel(i1, i2) ? 1 : 0; 640 641 /* Reset ending qt to base so that they are sorted */ 642 ss = *s; 643 if (swapn1 == 1) ss.normal[in1] = 3*movebase(n1); 644 if (swapn2 == 1) ss.normal[in2] = 3*movebase(n2); 645 if (swapi1 == 1) ss.inverse[ii1] = 3*movebase(i1); 646 if (swapi2 == 1) ss.inverse[ii2] = 3*movebase(i2); 647 648 u = 0; 649 count = 0; 650 for (i = 0; i <= swapn2; i++) { 651 if (i == 1) ss.normal[in2] += 2; 652 for (j = 0; j <= swapn1; j++) { 653 if (j == 1) ss.normal[in1] += 2; 654 for (k = 0; k <= swapi2; k++) { 655 if (k == 1) ss.inverse[ii2] += 2; 656 for (l = 0; l <= swapi1; l++) { 657 if (l == 1) ss.inverse[ii1] += 2; 658 659 err = writemoves_struct( 660 &ss, result_size-u, result+u); 661 if (err < 0) 662 goto lastqt_error; 663 u += err; 664 count++; 665 666 if (u >= result_size) 667 goto lastqt_error; 668 result[u++] = '\n'; 669 result[u] = '\0'; 670 671 if (l == 1) ss.inverse[ii1] -= 2; 672 } 673 if (k == 1) ss.inverse[ii2] -= 2; 674 } 675 if (j == 1) ss.normal[in1] -= 2; 676 } 677 if (i == 1) ss.normal[in2] -= 2; 678 } 679 680 return count; 681 682 lastqt_error: 683 LOG("[variations] Error writing result.\n"); 684 return NISSY_ERROR_BUFFER_SIZE; 685 } 686 687 STATIC int64_t 688 move_variations_unniss( 689 const moves_struct_t s[static 1], 690 size_t result_size, 691 char *result 692 ) 693 { 694 size_t i, tot; 695 uint8_t res[NISSY_SIZE_MOVES]; 696 int64_t err; 697 698 tot = s->nnormal + s->ninverse; 699 if (tot > NISSY_SIZE_MOVES) { 700 LOG("[variations] Error: %zu total moves, more than maximum " 701 "allowed %zu", tot, NISSY_SIZE_MOVES); 702 return NISSY_ERROR_BUFFER_SIZE; 703 } 704 705 for (i = 0; i < s->nnormal; i++) 706 res[i] = s->normal[i]; 707 for (i = 0; i < s->ninverse; i++) 708 res[i+s->nnormal] = inverse_move(s->inverse[s->ninverse-i-1]); 709 710 err = writemoves(tot, res, result_size, result); 711 if (err < 0 || (size_t)err > result_size) 712 goto unniss_error; 713 714 result[err++] = '\n'; 715 result[err] = '\0'; 716 return 1; 717 718 unniss_error: 719 LOG("[variations] Error writing result.\n"); 720 return NISSY_ERROR_BUFFER_SIZE; 721 }