diff options
Diffstat (limited to '')
| -rw-r--r-- | cube.c | 175 |
1 files changed, 63 insertions, 112 deletions
| @@ -4,6 +4,15 @@ | |||
| 4 | 4 | ||
| 5 | #ifdef DEBUG | 5 | #ifdef DEBUG |
| 6 | #include <stdio.h> | 6 | #include <stdio.h> |
| 7 | #define DBG_LOG(...) fprintf(stderr, __VA_ARGS__) | ||
| 8 | #define DBG_ASSERT(condition, retval, ...) \ | ||
| 9 | if (!(condition)) { \ | ||
| 10 | DBG_LOG(__VA_ARGS__); \ | ||
| 11 | return retval; \ | ||
| 12 | } | ||
| 13 | #else | ||
| 14 | #define DBG_LOG(...) | ||
| 15 | #define DBG_ASSERT(condition, retval, ...) | ||
| 7 | #endif | 16 | #endif |
| 8 | 17 | ||
| 9 | #include "cube.h" | 18 | #include "cube.h" |
| @@ -265,11 +274,11 @@ static void writecube_array_SRC(cube_array_t, char *); | |||
| 265 | static uint8_t readmove(char); | 274 | static uint8_t readmove(char); |
| 266 | static uint8_t readmodifier(char); | 275 | static uint8_t readmodifier(char); |
| 267 | 276 | ||
| 268 | cube_array_t solvedcube_array = { | 277 | cube_array_t _solvedcube_array = { |
| 269 | .c = {0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0}, | 278 | .c = {0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0}, |
| 270 | .e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0} | 279 | .e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0} |
| 271 | }; | 280 | }; |
| 272 | cube_array_t zerocube_array = { .e = {0}, .c = {0} }; | 281 | cube_array_t _zerocube_array = { .e = {0}, .c = {0} }; |
| 273 | 282 | ||
| 274 | static void | 283 | static void |
| 275 | setzero_array(cube_array_t *arr) | 284 | setzero_array(cube_array_t *arr) |
| @@ -295,7 +304,7 @@ equal_array(cube_array_t c1, cube_array_t c2) | |||
| 295 | static bool | 304 | static bool |
| 296 | iserror_array(cube_array_t arr) | 305 | iserror_array(cube_array_t arr) |
| 297 | { | 306 | { |
| 298 | return equal_array(arr, zerocube_array); | 307 | return equal_array(arr, _zerocube_array); |
| 299 | } | 308 | } |
| 300 | 309 | ||
| 301 | static uint8_t | 310 | static uint8_t |
| @@ -308,9 +317,7 @@ readco(char *str) | |||
| 308 | if (*str == '2') | 317 | if (*str == '2') |
| 309 | return _ctwist_ccw; | 318 | return _ctwist_ccw; |
| 310 | 319 | ||
| 311 | #ifdef DEBUG | 320 | DBG_LOG("Error reading CO\n"); |
| 312 | fprintf(stderr, "Error reading CO\n"); | ||
| 313 | #endif | ||
| 314 | return _error; | 321 | return _error; |
| 315 | } | 322 | } |
| 316 | 323 | ||
| @@ -324,9 +331,7 @@ readcp(char *str) | |||
| 324 | !strncmp(str, cornerstralt[c], 3)) | 331 | !strncmp(str, cornerstralt[c], 3)) |
| 325 | return c; | 332 | return c; |
| 326 | 333 | ||
| 327 | #ifdef DEBUG | 334 | DBG_LOG("Error reading CP\n"); |
| 328 | fprintf(stderr, "Error reading CP\n"); | ||
| 329 | #endif | ||
| 330 | return _error; | 335 | return _error; |
| 331 | } | 336 | } |
| 332 | 337 | ||
| @@ -338,9 +343,7 @@ readeo(char *str) | |||
| 338 | if (*str == '1') | 343 | if (*str == '1') |
| 339 | return _eflip; | 344 | return _eflip; |
| 340 | 345 | ||
| 341 | #ifdef DEBUG | 346 | DBG_LOG("Error reading EO\n"); |
| 342 | fprintf(stderr, "Error reading EO\n"); | ||
| 343 | #endif | ||
| 344 | return _error; | 347 | return _error; |
| 345 | } | 348 | } |
| 346 | 349 | ||
| @@ -353,9 +356,7 @@ readep(char *str) | |||
| 353 | if (!strncmp(str, edgestr[e], 2)) | 356 | if (!strncmp(str, edgestr[e], 2)) |
| 354 | return e; | 357 | return e; |
| 355 | 358 | ||
| 356 | #ifdef DEBUG | 359 | DBG_LOG("Error reading EP\n"); |
| 357 | fprintf(stderr, "Error reading EP\n"); | ||
| 358 | #endif | ||
| 359 | return _error; | 360 | return _error; |
| 360 | } | 361 | } |
| 361 | 362 | ||
| @@ -373,10 +374,10 @@ readcube_array_H48(char *buf) | |||
| 373 | while (*b == ' ' || *b == '\t' || *b == '\n') | 374 | while (*b == ' ' || *b == '\t' || *b == '\n') |
| 374 | b++; | 375 | b++; |
| 375 | if ((piece = readep(b)) == _error) | 376 | if ((piece = readep(b)) == _error) |
| 376 | return zerocube_array; | 377 | return _zerocube_array; |
| 377 | b += 2; | 378 | b += 2; |
| 378 | if ((orient = readeo(b)) == _error) | 379 | if ((orient = readeo(b)) == _error) |
| 379 | return zerocube_array; | 380 | return _zerocube_array; |
| 380 | b++; | 381 | b++; |
| 381 | set_edge(ret, i, piece | orient); | 382 | set_edge(ret, i, piece | orient); |
| 382 | } | 383 | } |
| @@ -384,10 +385,10 @@ readcube_array_H48(char *buf) | |||
| 384 | while (*b == ' ' || *b == '\t' || *b == '\n') | 385 | while (*b == ' ' || *b == '\t' || *b == '\n') |
| 385 | b++; | 386 | b++; |
| 386 | if ((piece = readcp(b)) == _error) | 387 | if ((piece = readcp(b)) == _error) |
| 387 | return zerocube_array; | 388 | return _zerocube_array; |
| 388 | b += 3; | 389 | b += 3; |
| 389 | if ((orient = readco(b)) == _error) | 390 | if ((orient = readco(b)) == _error) |
| 390 | return zerocube_array; | 391 | return _zerocube_array; |
| 391 | b++; | 392 | b++; |
| 392 | set_corner(ret, i, piece | orient); | 393 | set_corner(ret, i, piece | orient); |
| 393 | } | 394 | } |
| @@ -405,16 +406,11 @@ readcube_array(format_t format, char *buf) | |||
| 405 | arr = readcube_array_H48(buf); | 406 | arr = readcube_array_H48(buf); |
| 406 | break; | 407 | break; |
| 407 | default: | 408 | default: |
| 408 | #ifdef DEBUG | 409 | DBG_LOG("Cannot read cube in the given format\n"); |
| 409 | fprintf(stderr, "Cannot read cube in the given format\n"); | ||
| 410 | #endif | ||
| 411 | setzero_array(&arr); | 410 | setzero_array(&arr); |
| 412 | } | 411 | } |
| 413 | 412 | ||
| 414 | #ifdef DEBUG | 413 | DBG_ASSERT(!iserror_array(arr), arr, "readcube error\n"); |
| 415 | if (iserror_array(arr)) | ||
| 416 | fprintf(stderr, "readcube error\n"); | ||
| 417 | #endif | ||
| 418 | return arr; | 414 | return arr; |
| 419 | } | 415 | } |
| 420 | 416 | ||
| @@ -550,9 +546,7 @@ writecube_array(format_t format, cube_array_t a, char *buf) | |||
| 550 | return; | 546 | return; |
| 551 | 547 | ||
| 552 | writecube_error: | 548 | writecube_error: |
| 553 | #ifdef DEBUG | 549 | DBG_LOG("writecube error, see stdout for details\n"); |
| 554 | fprintf(stderr, "writecube error, see stdout for details\n"); | ||
| 555 | #endif | ||
| 556 | len = strlen(errormsg); | 550 | len = strlen(errormsg); |
| 557 | memcpy(buf, errormsg, len); | 551 | memcpy(buf, errormsg, len); |
| 558 | buf[len] = '\n'; | 552 | buf[len] = '\n'; |
| @@ -620,9 +614,7 @@ readmoves(char *buf, move_t *m) | |||
| 620 | return n; | 614 | return n; |
| 621 | 615 | ||
| 622 | readmoves_error: | 616 | readmoves_error: |
| 623 | #ifdef DEBUG | 617 | DBG_LOG("readmoves error\n"); |
| 624 | fprintf(stderr, "readmoves error\n"); | ||
| 625 | #endif | ||
| 626 | return -1; | 618 | return -1; |
| 627 | } | 619 | } |
| 628 | 620 | ||
| @@ -635,9 +627,7 @@ readtrans(char *buf) | |||
| 635 | if (!strncmp(buf, transstr[t], 11)) | 627 | if (!strncmp(buf, transstr[t], 11)) |
| 636 | return t; | 628 | return t; |
| 637 | 629 | ||
| 638 | #ifdef DEBUG | 630 | DBG_LOG("readtrans error\n"); |
| 639 | fprintf(stderr, "readtrans error\n"); | ||
| 640 | #endif | ||
| 641 | return errortrans; | 631 | return errortrans; |
| 642 | } | 632 | } |
| 643 | 633 | ||
| @@ -722,24 +712,16 @@ isconsistent_array(cube_array_t c) | |||
| 722 | return true; | 712 | return true; |
| 723 | 713 | ||
| 724 | inconsistent_ep: | 714 | inconsistent_ep: |
| 725 | #ifdef DEBUG | 715 | DBG_LOG("Inconsistent EP\n"); |
| 726 | fprintf(stderr, "Inconsistent EP\n"); | ||
| 727 | #endif | ||
| 728 | return false; | 716 | return false; |
| 729 | inconsistent_cp: | 717 | inconsistent_cp: |
| 730 | #ifdef DEBUG | 718 | DBG_LOG("Inconsistent CP\n"); |
| 731 | fprintf(stderr, "Inconsistent CP\n"); | ||
| 732 | #endif | ||
| 733 | return false; | 719 | return false; |
| 734 | inconsistent_eo: | 720 | inconsistent_eo: |
| 735 | #ifdef DEBUG | 721 | DBG_LOG("Inconsistent EO\n"); |
| 736 | fprintf(stderr, "Inconsistent EO\n"); | ||
| 737 | #endif | ||
| 738 | return false; | 722 | return false; |
| 739 | inconsistent_co: | 723 | inconsistent_co: |
| 740 | #ifdef DEBUG | 724 | DBG_LOG("Inconsistent CO\n"); |
| 741 | fprintf(stderr, "Inconsistent CO\n"); | ||
| 742 | #endif | ||
| 743 | return false; | 725 | return false; |
| 744 | } | 726 | } |
| 745 | 727 | ||
| @@ -748,12 +730,8 @@ issolvable_array(cube_array_t c) | |||
| 748 | { | 730 | { |
| 749 | uint8_t i, eo, co, piece, edges[12], corners[8]; | 731 | uint8_t i, eo, co, piece, edges[12], corners[8]; |
| 750 | 732 | ||
| 751 | #ifdef DEBUG | 733 | DBG_ASSERT(isconsistent_array(c), false, |
| 752 | if (!isconsistent_array(c)) { | 734 | "issolvable: cube is inconsistent\n"); |
| 753 | fprintf(stderr, "issolvable: cube is inconsistent\n"); | ||
| 754 | return false; | ||
| 755 | } | ||
| 756 | #endif | ||
| 757 | 735 | ||
| 758 | for (i = 0; i < 12; i++) | 736 | for (i = 0; i < 12; i++) |
| 759 | edges[i] = get_edge(c, i) & _pbits; | 737 | edges[i] = get_edge(c, i) & _pbits; |
| @@ -782,19 +760,13 @@ issolvable_array(cube_array_t c) | |||
| 782 | return true; | 760 | return true; |
| 783 | 761 | ||
| 784 | issolvable_parity: | 762 | issolvable_parity: |
| 785 | #ifdef DEBUG | 763 | DBG_LOG("EP and CP parities are different\n"); |
| 786 | fprintf(stderr, "EP and CP parities are different\n"); | ||
| 787 | #endif | ||
| 788 | return false; | 764 | return false; |
| 789 | issolvable_eo: | 765 | issolvable_eo: |
| 790 | #ifdef DEBUG | 766 | DBG_LOG("Odd number of flipped edges\n"); |
| 791 | fprintf(stderr, "Odd number of flipped edges\n"); | ||
| 792 | #endif | ||
| 793 | return false; | 767 | return false; |
| 794 | issolvable_co: | 768 | issolvable_co: |
| 795 | #ifdef DEBUG | 769 | DBG_LOG("Sum of corner orientation is not multiple of 3\n"); |
| 796 | fprintf(stderr, "Sum of corner orientation is not multiple of 3\n"); | ||
| 797 | #endif | ||
| 798 | return false; | 770 | return false; |
| 799 | } | 771 | } |
| 800 | 772 | ||
| @@ -813,6 +785,12 @@ Note: the #ifdef below is closed in the next section. | |||
| 813 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060) | 785 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060) |
| 814 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020) | 786 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020) |
| 815 | #define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0) | 787 | #define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0) |
| 788 | #define _zerocube _mm256_set_epi64x(0, 0, 0, 0); | ||
| 789 | #define _solvedcube _mm256_set_epi8( \ | ||
| 790 | 0, 0, 0, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, \ | ||
| 791 | 0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 5, 4, 3, 2, 1, 0 \ | ||
| 792 | ) | ||
| 793 | |||
| 816 | 794 | ||
| 817 | static cube_t _arraytocube(cube_array_t); | 795 | static cube_t _arraytocube(cube_array_t); |
| 818 | static void _cubetoarray(cube_t, cube_array_t *); | 796 | static void _cubetoarray(cube_t, cube_array_t *); |
| @@ -2157,6 +2135,12 @@ in the previous section(s) for unsupported architectures. | |||
| 2157 | r[k] ^= _eobit; \ | 2135 | r[k] ^= _eobit; \ |
| 2158 | r[l] ^= _eobit; | 2136 | r[l] ^= _eobit; |
| 2159 | 2137 | ||
| 2138 | static const cube_t _solvedcube = { | ||
| 2139 | .c = {0, 1, 2, 3, 4, 5, 6, 7, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 2140 | .e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 0, 0, 0} | ||
| 2141 | }; | ||
| 2142 | static const cube_t _zerocube = { .e = {0}, .c = {0} }; | ||
| 2143 | |||
| 2160 | static cube_t _arraytocube(cube_array_t); | 2144 | static cube_t _arraytocube(cube_array_t); |
| 2161 | static void _cubetoarray(cube_t, cube_array_t *); | 2145 | static void _cubetoarray(cube_t, cube_array_t *); |
| 2162 | static inline bool _equal(cube_t, cube_t); | 2146 | static inline bool _equal(cube_t, cube_t); |
| @@ -3387,7 +3371,7 @@ _inverse(cube_t c) | |||
| 3387 | cube_t ret; | 3371 | cube_t ret; |
| 3388 | uint8_t i, piece, orien; | 3372 | uint8_t i, piece, orien; |
| 3389 | 3373 | ||
| 3390 | ret = _arraytocube(zerocube_array); | 3374 | ret = _zerocube; |
| 3391 | 3375 | ||
| 3392 | for (i = 0; i < 12; i++) { | 3376 | for (i = 0; i < 12; i++) { |
| 3393 | piece = get_edge(c, i); | 3377 | piece = get_edge(c, i); |
| @@ -3410,7 +3394,7 @@ _compose(cube_t c1, cube_t c2) | |||
| 3410 | cube_t ret; | 3394 | cube_t ret; |
| 3411 | uint8_t i, piece1, piece2, p, orien, aux, auy; | 3395 | uint8_t i, piece1, piece2, p, orien, aux, auy; |
| 3412 | 3396 | ||
| 3413 | ret = _arraytocube(zerocube_array); | 3397 | ret = _zerocube; |
| 3414 | 3398 | ||
| 3415 | for (i = 0; i < 12; i++) { | 3399 | for (i = 0; i < 12; i++) { |
| 3416 | piece2 = get_edge(c2, i); | 3400 | piece2 = get_edge(c2, i); |
| @@ -3460,24 +3444,13 @@ of them are public functions from cube.h | |||
| 3460 | cube_t | 3444 | cube_t |
| 3461 | solvedcube(void) | 3445 | solvedcube(void) |
| 3462 | { | 3446 | { |
| 3463 | cube_t solved; | 3447 | return _solvedcube; |
| 3464 | solved = _arraytocube(solvedcube_array); | ||
| 3465 | return solved; | ||
| 3466 | } | ||
| 3467 | |||
| 3468 | cube_t | ||
| 3469 | zerocube(void) | ||
| 3470 | { | ||
| 3471 | cube_t solved; | ||
| 3472 | solved = _arraytocube(zerocube_array); | ||
| 3473 | return solved; | ||
| 3474 | } | 3448 | } |
| 3475 | 3449 | ||
| 3476 | cube_t | 3450 | cube_t |
| 3477 | readcube(format_t format, char *buf) | 3451 | readcube(format_t format, char *buf) |
| 3478 | { | 3452 | { |
| 3479 | cube_array_t arr; | 3453 | cube_array_t arr = readcube_array(format, buf); |
| 3480 | arr = readcube_array(format, buf); | ||
| 3481 | return _arraytocube(arr); | 3454 | return _arraytocube(arr); |
| 3482 | } | 3455 | } |
| 3483 | 3456 | ||
| @@ -3522,20 +3495,14 @@ equal(cube_t c1, cube_t c2) | |||
| 3522 | bool | 3495 | bool |
| 3523 | issolved(cube_t cube) | 3496 | issolved(cube_t cube) |
| 3524 | { | 3497 | { |
| 3525 | cube_t solved; | 3498 | return equal(cube, _solvedcube); |
| 3526 | solved = _arraytocube(solvedcube_array); | ||
| 3527 | return equal(cube, solved); | ||
| 3528 | } | 3499 | } |
| 3529 | 3500 | ||
| 3530 | cube_t | 3501 | cube_t |
| 3531 | move(cube_t c, move_t m) | 3502 | move(cube_t c, move_t m) |
| 3532 | { | 3503 | { |
| 3533 | #ifdef DEBUG | 3504 | DBG_ASSERT(isconsistent(c), _zerocube, |
| 3534 | if (!isconsistent(c)) { | 3505 | "move error: inconsistent cube\n"); |
| 3535 | fprintf(stderr, "move error, inconsistent cube\n"); | ||
| 3536 | return _arraytocube(zerocube_array); | ||
| 3537 | } | ||
| 3538 | #endif | ||
| 3539 | 3506 | ||
| 3540 | switch (m) { | 3507 | switch (m) { |
| 3541 | case U: | 3508 | case U: |
| @@ -3575,22 +3542,16 @@ move(cube_t c, move_t m) | |||
| 3575 | case B3: | 3542 | case B3: |
| 3576 | return _move_B3(c); | 3543 | return _move_B3(c); |
| 3577 | default: | 3544 | default: |
| 3578 | #ifdef DEBUG | 3545 | DBG_LOG("mover error, unknown move\n"); |
| 3579 | fprintf(stderr, "mover error, unknown move\n"); | 3546 | return _zerocube; |
| 3580 | #endif | ||
| 3581 | return _arraytocube(zerocube_array); | ||
| 3582 | } | 3547 | } |
| 3583 | } | 3548 | } |
| 3584 | 3549 | ||
| 3585 | cube_t | 3550 | cube_t |
| 3586 | inverse(cube_t c) | 3551 | inverse(cube_t c) |
| 3587 | { | 3552 | { |
| 3588 | #ifdef DEBUG | 3553 | DBG_ASSERT(isconsistent(c), _zerocube, |
| 3589 | if (!isconsistent(c)) { | 3554 | "inverse error: inconsistent cube\n"); |
| 3590 | fprintf(stderr, "inverse error, inconsistent cube\n"); | ||
| 3591 | return zerocube(); | ||
| 3592 | } | ||
| 3593 | #endif | ||
| 3594 | 3555 | ||
| 3595 | return _inverse(c); | 3556 | return _inverse(c); |
| 3596 | } | 3557 | } |
| @@ -3598,12 +3559,8 @@ inverse(cube_t c) | |||
| 3598 | cube_t | 3559 | cube_t |
| 3599 | compose(cube_t c1, cube_t c2) | 3560 | compose(cube_t c1, cube_t c2) |
| 3600 | { | 3561 | { |
| 3601 | #ifdef DEBUG | 3562 | DBG_ASSERT(isconsistent(c1) && isconsistent(c2), |
| 3602 | if (!isconsistent(c1) || !isconsistent(c2)) { | 3563 | _zerocube, "compose error: inconsistent cube\n") |
| 3603 | fprintf(stderr, "compose error, inconsistent cube\n"); | ||
| 3604 | return zerocube(); | ||
| 3605 | } | ||
| 3606 | #endif | ||
| 3607 | 3564 | ||
| 3608 | return _compose(c1, c2); | 3565 | return _compose(c1, c2); |
| 3609 | } | 3566 | } |
| @@ -3611,12 +3568,8 @@ compose(cube_t c1, cube_t c2) | |||
| 3611 | cube_t | 3568 | cube_t |
| 3612 | transform(cube_t c, trans_t t) | 3569 | transform(cube_t c, trans_t t) |
| 3613 | { | 3570 | { |
| 3614 | #ifdef DEBUG | 3571 | DBG_ASSERT(isconsistent(c), _zerocube, |
| 3615 | if (!isconsistent(c)) { | 3572 | "transform error: inconsistent cube\n"); |
| 3616 | fprintf(stderr, "transform error, inconsistent cube\n"); | ||
| 3617 | return zerocube(); | ||
| 3618 | } | ||
| 3619 | #endif | ||
| 3620 | 3573 | ||
| 3621 | switch (t) { | 3574 | switch (t) { |
| 3622 | case UFr: | 3575 | case UFr: |
| @@ -3716,10 +3669,8 @@ transform(cube_t c, trans_t t) | |||
| 3716 | case BLm: | 3669 | case BLm: |
| 3717 | return _trans_BLm(c); | 3670 | return _trans_BLm(c); |
| 3718 | default: | 3671 | default: |
| 3719 | #ifdef DEBUG | 3672 | DBG_LOG("transform error, unknown transformation\n"); |
| 3720 | fprintf(stderr, "transform error, unknown transformation\n"); | 3673 | return _zerocube; |
| 3721 | #endif | ||
| 3722 | return zerocube(); | ||
| 3723 | } | 3674 | } |
| 3724 | } | 3675 | } |
| 3725 | 3676 | ||
