aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2023-09-08 18:28:30 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2023-09-08 18:28:30 +0200
commit4d08bf731a099de2d174c73489636e1a12935aee (patch)
treec751858cb6e33172c97a1123432f7c59d7d94d7e /src
parentc5dfc897160bc9bbc6a91c77b5d58d421fd1cfe1 (diff)
downloadnissy-core-4d08bf731a099de2d174c73489636e1a12935aee.tar.gz
nissy-core-4d08bf731a099de2d174c73489636e1a12935aee.zip
New implementation, moved old to experiments/
Diffstat (limited to 'src')
-rw-r--r--src/array_cube.c712
-rw-r--r--src/cube.c888
-rw-r--r--src/cube.h42
3 files changed, 746 insertions, 896 deletions
diff --git a/src/array_cube.c b/src/array_cube.c
new file mode 100644
index 0000000..3445658
--- /dev/null
+++ b/src/array_cube.c
@@ -0,0 +1,712 @@
1/*
2In this implementation of the cube.h interface, the cube is represented
3by two arrays of 8-bit unsigned integers, one for centers and one for
4corners. The 4 leas-significant digits of each bit determine the piece,
5the other 4 are used for orientation or kept to 0.
6
7Edges:
8 xxxopppp (x = unused, o = orientation, p = piece)
9
10Corners:
11 xooxpppp (x = unused, o = orientation, p = piece)
12
13The two bits for CO are shifted to make it possible to perform mod 3
14operations (sum, inverse) using only addition and bitwise operators.
15See below for details.
16
17The third bit is needed because x+y+1 can exceed 4.
18*/
19
20#include <inttypes.h>
21#include <stdbool.h>
22#include <string.h>
23
24#ifdef DEBUG
25#include <stdio.h>
26#endif
27
28#include "cube.h"
29
30#define _c_ufr 0U
31#define _c_ubl 1U
32#define _c_dfl 2U
33#define _c_dbr 3U
34#define _c_ufl 4U
35#define _c_ubr 5U
36#define _c_dfr 6U
37#define _c_dbl 7U
38
39#define _e_uf 0U
40#define _e_ub 1U
41#define _e_db 2U
42#define _e_df 3U
43#define _e_ur 4U
44#define _e_ul 5U
45#define _e_dl 6U
46#define _e_dr 7U
47#define _e_fr 8U
48#define _e_fl 9U
49#define _e_bl 10U
50#define _e_br 11U
51
52#define _eoshift 4U
53#define _coshift 5U
54
55#define _pbits 0xFU
56#define _eobit 0x10U
57#define _cobits 0xF0U
58#define _cobits2 0x60U
59#define _ctwist_cw 0x20U
60#define _ctwist_ccw 0x40U
61#define _eflip 0x10U
62#define _error 0xFFU
63
64static char *cornerstr[] = {
65 [_c_ufr] = "UFR",
66 [_c_ubl] = "UBL",
67 [_c_dfl] = "DFL",
68 [_c_dbr] = "DBR",
69 [_c_ufl] = "UFL",
70 [_c_ubr] = "UBR",
71 [_c_dfr] = "DFR",
72 [_c_dbl] = "DBL"
73};
74
75static char *cornerstralt[] = {
76 [_c_ufr] = "URF",
77 [_c_ubl] = "ULB",
78 [_c_dfl] = "DLF",
79 [_c_dbr] = "DRB",
80 [_c_ufl] = "ULF",
81 [_c_ubr] = "URB",
82 [_c_dfr] = "DRF",
83 [_c_dbl] = "DLB"
84};
85
86static char *edgestr[] = {
87 [_e_uf] = "UF",
88 [_e_ub] = "UB",
89 [_e_db] = "DB",
90 [_e_df] = "DF",
91 [_e_ur] = "UR",
92 [_e_ul] = "UL",
93 [_e_dl] = "DL",
94 [_e_dr] = "DR",
95 [_e_fr] = "FR",
96 [_e_fl] = "FL",
97 [_e_bl] = "BL",
98 [_e_br] = "BR"
99};
100
101static char *movestr[] = {
102 [U] = "U",
103 [U2] = "U2",
104 [U3] = "U'",
105 [D] = "D",
106 [D2] = "D2",
107 [D3] = "D'",
108 [R] = "R",
109 [R2] = "R2",
110 [R3] = "R'",
111 [L] = "L",
112 [L2] = "L2",
113 [L3] = "L'",
114 [F] = "F",
115 [F2] = "F2",
116 [F3] = "F'",
117 [B] = "B",
118 [B2] = "B2",
119 [B3] = "B'",
120};
121
122cube_t solvedcube = {
123 .c = {
124 [_c_ufr] = _c_ufr,
125 [_c_ubl] = _c_ubl,
126 [_c_dfl] = _c_dfl,
127 [_c_dbr] = _c_dbr,
128 [_c_ufl] = _c_ufl,
129 [_c_ubr] = _c_ubr,
130 [_c_dfr] = _c_dfr,
131 [_c_dbl] = _c_dbl
132 },
133 .e = {
134 [_e_uf] = _e_uf,
135 [_e_ub] = _e_ub,
136 [_e_db] = _e_db,
137 [_e_df] = _e_df,
138 [_e_ur] = _e_ur,
139 [_e_ul] = _e_ul,
140 [_e_dl] = _e_dl,
141 [_e_dr] = _e_dr,
142 [_e_fr] = _e_fr,
143 [_e_fl] = _e_fl,
144 [_e_bl] = _e_bl,
145 [_e_br] = _e_br
146 }
147};
148
149static cube_t errorcube = { .e = {0}, .c = {0} };
150
151static uint8_t readco(char *);
152static uint8_t readcp(char *);
153static uint8_t readeo(char *);
154static uint8_t readep(char *);
155static uint8_t readmove(char);
156static uint8_t readmodifier(char);
157static int permsign(uint8_t *, int);
158static cube_t compose(cube_t, cube_t);
159
160static uint8_t
161readco(char *str)
162{
163 if (*str == '0')
164 return 0;
165 if (*str == '1')
166 return _ctwist_cw;
167 if (*str == '2')
168 return _ctwist_ccw;
169
170#ifdef DEBUG
171 fprintf(stderr, "Error reading CO\n");
172#endif
173 return _error;
174}
175
176static uint8_t
177readcp(char *str)
178{
179 uint8_t c;
180
181 for (c = 0; c < 8; c++)
182 if (!strncmp(str, cornerstr[c], 3) ||
183 !strncmp(str, cornerstralt[c], 3))
184 return c;
185
186#ifdef DEBUG
187 fprintf(stderr, "Error reading CP\n");
188#endif
189 return _error;
190}
191
192static uint8_t
193readeo(char *str)
194{
195 if (*str == '0')
196 return 0;
197 if (*str == '1')
198 return _eflip;
199
200#ifdef DEBUG
201 fprintf(stderr, "Error reading EO\n");
202#endif
203 return _error;
204}
205
206static uint8_t
207readep(char *str)
208{
209 uint8_t e;
210
211 for (e = 0; e < 12; e++)
212 if (!strncmp(str, edgestr[e], 2))
213 return e;
214
215#ifdef DEBUG
216 fprintf(stderr, "Error reading EP\n");
217#endif
218 return _error;
219}
220
221cube_t
222readcube(char *buf)
223{
224 int i;
225 uint8_t piece, orient;
226 cube_t ret = {0};
227 char *b = buf;
228
229 for (i = 0; i < 12; i++) {
230 while (*b == ' ' || *b == '\t' || *b == '\n')
231 b++;
232 if ((piece = readep(b)) == _error)
233 goto readcube_error;
234 b += 2;
235 if ((orient = readeo(b)) == _error)
236 goto readcube_error;
237 b++;
238 ret.e[i] = piece | orient;
239 }
240 for (i = 0; i < 8; i++) {
241 while (*b == ' ' || *b == '\t' || *b == '\n')
242 b++;
243 if ((piece = readcp(b)) == _error)
244 goto readcube_error;
245 b += 3;
246 if ((orient = readco(b)) == _error)
247 goto readcube_error;
248 b++;
249 ret.c[i] = piece | orient;
250 }
251
252 return ret;
253
254readcube_error:
255#ifdef DEBUG
256 fprintf(stderr, "readcube error\n");
257#endif
258 return errorcube;
259}
260
261void
262writecube(cube_t cube, char *buf)
263{
264 char *errormsg;
265 uint8_t piece, orient;
266 size_t len;
267 int i;
268
269 if (!isconsistent(cube)) {
270 errormsg = "ERROR: cannot write inconsistent cube";
271 goto writecube_error;
272 }
273
274 for (i = 0; i < 12; i++) {
275 piece = cube.e[i] & _pbits;
276 orient = (cube.e[i] & _eobit) >> _eoshift;
277 buf[4*i ] = edgestr[piece][0];
278 buf[4*i + 1] = edgestr[piece][1];
279 buf[4*i + 2] = orient + '0';
280 buf[4*i + 3] = ' ';
281 }
282 for (i = 0; i < 8; i++) {
283 piece = cube.c[i] & _pbits;
284 orient = (cube.c[i] & _cobits) >> _coshift;
285 buf[48 + 5*i ] = cornerstr[piece][0];
286 buf[48 + 5*i + 1] = cornerstr[piece][1];
287 buf[48 + 5*i + 2] = cornerstr[piece][2];
288 buf[48 + 5*i + 3] = orient + '0';
289 buf[48 + 5*i + 4] = ' ';
290 }
291
292 buf[48+39] = '\0';
293
294 return;
295
296writecube_error:
297#ifdef DEBUG
298 fprintf(stderr, "writecube error, see stdout for details\n");
299#endif
300 len = strlen(errormsg);
301 memcpy(buf, errormsg, len);
302 buf[len] = '\n';
303 buf[len+1] = '\0';
304}
305
306
307static uint8_t
308readmove(char c)
309{
310 switch (c) {
311 case 'U':
312 return U;
313 case 'D':
314 return D;
315 case 'R':
316 return R;
317 case 'L':
318 return L;
319 case 'F':
320 return F;
321 case 'B':
322 return B;
323 default:
324 return _error;
325 }
326}
327
328static uint8_t
329readmodifier(char c)
330{
331 switch (c) {
332 case '1': /* Fallthrough */
333 case '2': /* Fallthrough */
334 case '3':
335 return c - '0' - 1;
336 case '\'':
337 return 2;
338 default:
339 return 0;
340 }
341}
342
343int
344readmoves(char *buf, move_t *m)
345{
346 int n;
347 uint64_t r;
348 char *b;
349
350 for (b = buf, n = 0; *b != '\0'; b++) {
351 while (*b == ' ' || *b == '\t' || *b == '\n')
352 b++;
353 if (*b == '\0')
354 return n;
355 if ((r = readmove(*b)) == _error)
356 goto readmoves_error;
357 m[n] = (move_t)r;
358 if ((r = readmodifier(*(b+1))) != 0) {
359 b++;
360 m[n] += r;
361 }
362 n++;
363 }
364
365 return n;
366
367readmoves_error:
368#ifdef DEBUG
369 fprintf(stderr, "readmoves error\n");
370#endif
371 return -1;
372}
373
374void
375writemoves(move_t *m, int n, char *buf)
376{
377 int i;
378 size_t len;
379 char *b, *s;
380
381 for (i = 0, b = buf; i < n; i++, b++) {
382 s = movestr[m[i]];
383 len = strlen(s);
384 memcpy(b, s, len);
385 b += len;
386 *b = ' ';
387 }
388 *b = '\0';
389}
390
391
392static int
393permsign(uint8_t *a, int n)
394{
395 int i, j;
396 uint8_t ret = 0;
397
398 for (i = 0; i < n; i++)
399 for (j = i+1; j < n; j++)
400 ret += (a[i] & _pbits) > (a[j] & _pbits) ? 1 : 0;
401
402 return ret % 2;
403}
404
405bool
406isconsistent(cube_t cube)
407{
408 int8_t p, psum, eosum, co, cosum;
409 bool found[12];
410 int i;
411
412 psum = 0;
413 for (i = 0; i < 12; i++)
414 found[i] = false;
415 for (i = 0; i < 12; i++) {
416 p = cube.e[i] & _pbits;
417 if (p >= 12)
418 goto inconsistent_ep;
419 found[p] = true;
420 }
421 for (i = 0; i < 12; i++)
422 if (!found[i])
423 goto inconsistent_ep;
424 psum = permsign(cube.e, 12);
425
426 for (i = 0; i < 8; i++)
427 found[i] = false;
428 for (i = 0; i < 8; i++) {
429 p = cube.c[i] & _pbits;
430 if (p >= 8)
431 goto inconsistent_cp;
432 found[p] = true;
433 }
434 for (i = 0; i < 8; i++)
435 if (!found[i])
436 goto inconsistent_cp;
437 psum += permsign(cube.c, 8);
438
439 if (psum % 2 != 0)
440 goto inconsistent_parity;
441
442 eosum = 0;
443 for (i = 0; i < 12; i++)
444 eosum += (cube.e[i] & _eobit) >> _eoshift;
445 if (eosum % 2 != 0)
446 goto inconsistent_eo;
447
448 cosum = 0;
449 for (i = 0; i < 8; i++) {
450 co = (cube.c[i] & _cobits) >> _coshift;
451 if (co > 2)
452 goto inconsistent_co;
453 cosum += co;
454 }
455 if (cosum % 3 != 0)
456 goto inconsistent_co;
457
458 return true;
459
460inconsistent_ep:
461#ifdef DEBUG
462 fprintf(stderr, "Inconsistent EP\n");
463#endif
464 goto inconsistent_return;
465inconsistent_cp:
466#ifdef DEBUG
467 fprintf(stderr, "Inconsistent CP\n");
468#endif
469 goto inconsistent_return;
470inconsistent_parity:
471#ifdef DEBUG
472 fprintf(stderr, "Inconsistent parity\n");
473#endif
474 goto inconsistent_return;
475inconsistent_eo:
476#ifdef DEBUG
477 fprintf(stderr, "Inconsistent EO\n");
478#endif
479 goto inconsistent_return;
480inconsistent_co:
481#ifdef DEBUG
482 fprintf(stderr, "Inconsistent CO\n");
483#endif
484 goto inconsistent_return;
485inconsistent_return:
486 return false;
487}
488
489bool
490equal(cube_t cube1, cube_t cube2)
491{
492 uint8_t i;
493
494 for (i = 0; i < 12; i++)
495 if (cube1.e[i] != cube2.e[i])
496 return false;
497
498 for (i = 0; i < 8; i++)
499 if (cube1.c[i] != cube2.c[i])
500 return false;
501
502 return true;
503}
504
505bool
506issolved(cube_t cube)
507{
508 return equal(cube, solvedcube);
509}
510
511bool
512iserror(cube_t cube)
513{
514 return equal(cube, errorcube);
515}
516
517cube_t
518move(cube_t c, move_t m)
519{
520 cube_t ret;
521 uint8_t aux, auy, auz;
522
523#ifdef DEBUG
524 if (!isconsistent(c))
525 goto move_inconsistent;
526#endif
527
528#define PERM4(r, i, j, k, l) \
529 aux = r[i]; \
530 r[i] = r[l]; \
531 r[l] = r[k]; \
532 r[k] = r[j]; \
533 r[j] = aux;
534#define PERM22(r, i, j, k, l) \
535 aux = r[i]; \
536 r[i] = r[j]; \
537 r[j] = aux; \
538 aux = r[k]; \
539 r[k] = r[l]; \
540 r[l] = aux;
541#define CO(a, b) \
542 aux = (a & _cobits) + (b & _cobits); \
543 auy = (aux + _ctwist_cw) >> 2U; \
544 auz = (aux + auy) & _cobits2; \
545 a = (a & _pbits) | auz;
546#define CO4(r, i, j, k, l) \
547 CO(r[i], _ctwist_cw) \
548 CO(r[j], _ctwist_cw) \
549 CO(r[k], _ctwist_ccw) \
550 CO(r[l], _ctwist_ccw)
551#define EO4(r, i, j, k, l) \
552 r[i] ^= _eobit; \
553 r[j] ^= _eobit; \
554 r[k] ^= _eobit; \
555 r[l] ^= _eobit;
556
557 ret = c;
558
559 switch (m) {
560 case U:
561 PERM4(ret.e, _e_uf, _e_ul, _e_ub, _e_ur)
562 PERM4(ret.c, _c_ufr, _c_ufl, _c_ubl, _c_ubr)
563
564 return ret;
565 case U2:
566 PERM22(ret.e, _e_uf, _e_ub, _e_ul, _e_ur)
567 PERM22(ret.c, _c_ufr, _c_ubl, _c_ufl, _c_ubr)
568
569 return ret;
570 case U3:
571 PERM4(ret.e, _e_uf, _e_ur, _e_ub, _e_ul)
572 PERM4(ret.c, _c_ufr, _c_ubr, _c_ubl, _c_ufl)
573
574 return ret;
575 case D:
576 PERM4(ret.e, _e_df, _e_dr, _e_db, _e_dl)
577 PERM4(ret.c, _c_dfr, _c_dbr, _c_dbl, _c_dfl)
578
579 return ret;
580 case D2:
581 PERM22(ret.e, _e_df, _e_db, _e_dr, _e_dl)
582 PERM22(ret.c, _c_dfr, _c_dbl, _c_dbr, _c_dfl)
583
584 return ret;
585 case D3:
586 PERM4(ret.e, _e_df, _e_dl, _e_db, _e_dr)
587 PERM4(ret.c, _c_dfr, _c_dfl, _c_dbl, _c_dbr)
588
589 return ret;
590 case R:
591 PERM4(ret.e, _e_ur, _e_br, _e_dr, _e_fr)
592 PERM4(ret.c, _c_ufr, _c_ubr, _c_dbr, _c_dfr)
593
594 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
595
596 return ret;
597 case R2:
598 PERM22(ret.e, _e_ur, _e_dr, _e_fr, _e_br)
599 PERM22(ret.c, _c_ufr, _c_dbr, _c_ubr, _c_dfr)
600
601 return ret;
602 case R3:
603 PERM4(ret.e, _e_ur, _e_fr, _e_dr, _e_br)
604 PERM4(ret.c, _c_ufr, _c_dfr, _c_dbr, _c_ubr)
605
606 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
607
608 return ret;
609 case L:
610 PERM4(ret.e, _e_ul, _e_fl, _e_dl, _e_bl)
611 PERM4(ret.c, _c_ufl, _c_dfl, _c_dbl, _c_ubl)
612
613 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
614
615 return ret;
616 case L2:
617 PERM22(ret.e, _e_ul, _e_dl, _e_fl, _e_bl)
618 PERM22(ret.c, _c_ufl, _c_dbl, _c_ubl, _c_dfl)
619
620 return ret;
621 case L3:
622 PERM4(ret.e, _e_ul, _e_bl, _e_dl, _e_fl)
623 PERM4(ret.c, _c_ufl, _c_ubl, _c_dbl, _c_dfl)
624
625 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
626
627 return ret;
628 case F:
629 PERM4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
630 PERM4(ret.c, _c_ufr, _c_dfr, _c_dfl, _c_ufl)
631
632 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
633 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
634
635 return ret;
636 case F2:
637 PERM22(ret.e, _e_uf, _e_df, _e_fr, _e_fl)
638 PERM22(ret.c, _c_ufr, _c_dfl, _c_ufl, _c_dfr)
639
640 return ret;
641 case F3:
642 PERM4(ret.e, _e_uf, _e_fl, _e_df, _e_fr)
643 PERM4(ret.c, _c_ufr, _c_ufl, _c_dfl, _c_dfr)
644
645 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
646 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
647
648 return ret;
649 case B:
650 PERM4(ret.e, _e_ub, _e_bl, _e_db, _e_br)
651 PERM4(ret.c, _c_ubr, _c_ubl, _c_dbl, _c_dbr)
652
653 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
654 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
655
656 return ret;
657 case B2:
658 PERM22(ret.e, _e_ub, _e_db, _e_br, _e_bl)
659 PERM22(ret.c, _c_ubr, _c_dbl, _c_ubl, _c_dbr)
660
661 return ret;
662 case B3:
663 PERM4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
664 PERM4(ret.c, _c_ubr, _c_dbr, _c_dbl, _c_ubl)
665
666 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
667 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
668
669 return ret;
670 default:
671 goto move_unknown;
672 }
673
674move_inconsistent:
675 fprintf(stderr, "move error, inconsistent cube\n");
676 goto move_error;
677move_unknown:
678 fprintf(stderr, "mover error, unknown move\n");
679 goto move_error;
680move_error:
681 return errorcube;
682}
683
684cube_t
685inverse(cube_t c)
686{
687 uint8_t i, piece, orien;
688 cube_t ret = {0};
689
690#ifdef DEBUG
691 if (!isconsistent(c))
692 goto inverse_inconsistent;
693#endif
694
695 for (i = 0; i < 12; i++) {
696 piece = c.e[i & _pbits];
697 orien = piece & _eobit;
698 ret.e[piece & _pbits] = i | orien;
699 }
700
701 for (i = 0; i < 8; i++) {
702 piece = c.c[i & _pbits];
703 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
704 ret.c[piece & _pbits] = i | orien;
705 }
706
707 return ret;
708
709inverse_inconsistent:
710 fprintf(stderr, "inverse error, inconsistent cube\n");
711 return errorcube;
712}
diff --git a/src/cube.c b/src/cube.c
deleted file mode 100644
index 4372b5e..0000000
--- a/src/cube.c
+++ /dev/null
@@ -1,888 +0,0 @@
1/*
2# Cube representation, moves, transformations and (tentatively) indexing
3
4## Textual description
5
6The functions readcube() and writecube() use the following format.
7Each edge is represented by two letters denoting the sides it belongs to
8and one number denoting its orientation (0 oriented, 1 mis-oriented).
9Similarly, each corner is represented by three letters and a number
10(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
11Edge orientation is relative to the F / B axis, corner orientation is
12relative to the U / D axis.
13
14The correct order of the pieces is the same as that defined in the
15section "Internal cube representation", except that pieces are read
16left-to-right. Pieces are divided by slices, so the ordering is not the
17most intuitive, but it is more convenient for the internal representation.
18
19Whitespaces between pieces are ignored when reading the cube, and a
20single whitespace character is added between pieces when writing.
21
22For example, the solved cube looks like this:
23
24UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 \ (no newline)
25UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
26
27The cube after the moves R'U'F looks like this:
28
29FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 \ (no newline)
30UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
31
32More formats might be supported in the future.
33
34## Internal cube representation
35
36The cube_t data structure implemented in this file is designed to
37efficiently perform common operations on a 3x3x3 Rubik's cube when
38solving it with an iterative-deepening DFS search. It is not the most
39general, complete, easy to read or compact one. Since the cube can
40be trivially reoriented before the search, we only encode permutations
41of the cube that keep the center pieces in a fixed position (that is,
42we do not encode the position of the centers).
43
44The cube state is encoded in two 64-bit integers, one for edges and one
45for centers. We explain how edges are encoded first, and the highlight
46the few differences with corners afterwards.
47
48For encoding edges, only the 60 least-significant bits are used. Each
49edge described by 5 bits. The position of a 5-bit block in the 64-bit
50integer determine the position of the edge piece in the cube, according
51to the following table (least-significant bits on the right):
52
5355-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
54 BR BL FL FR DR DL UL UR DF DB UB UF
55ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
56
57For each edge, the 4 least-significant bits ('ssee' in the table)
58determine the piece. The two bits marked with 'ss' determine the internal
59slice the piece belongs to, i.e. they are either '00' for M, '01' for
60S or '10' for E. The other two bits (marked with 'ee') determine the
61actual edge piece among the 4 in the same slice, and they are assigned
62somewhat arbitarily. Using this representation and the ordering defined
63in the table above, the edges are correctly permuted when these 4 bits
64for each represent the numbers 0 to 11 in the correct order.
65
66The last bit determines the orientation. The orientation of an edge
67depends on its position, and it is defined being 0 if the edge can be
68moved to its place in the solved orientation by permutations in the
69subgroup <U, D, R, L, F2, B2>.
70
71Corners are encoded in the 48 least-significant bits, and are described
72by 6 bits each, their position being defined by the following table:
73
74 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
75 DBL DFL UBR UFL DBR DFL UBL UFR
76oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
77
78The bit marked with an 'x' describes the axis the corner belongs to.
79The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
80four corners form the axis marked with 1. Then two bits are needed to
81identify the corner among the four of the same axis. The last three bits
82determine the orientation, where one corner is defined to be oriented
83(marked with '000') if its top or bottom sticker faces the top or bottom
84side. A corner a clockwise turn away from being oriented, thus requiring
85a counter-clockwise turn to be oriented correctly, is marked with '001',
86and a corner a counter-clockwise turn away is marked with '010'. The most
87significant bit is not used to determine the corner orientation, but it
88must always be set to '0' to simplify the moving operations (see below).
89
90## Basic moves
91
92The 18 basic moves of the cube could be performed by applying a suitable
93general permutation (see below), but they have instead been manually
94implemented with a few simple operations each, to improve performance.
95
96For each move we first permute the pieces. This amounts to shifting
97around 4 blocks of bits for edges and 4 for corners. Since in some cases
98adjacent pieces on the cube are also adjacent in the bit representation we
99use, we can save some operations by shifting multiple blocks together.
100
101There are some moves that change the orientation of the pieces. Namely,
102the moves F, F', B and B' change the orientation of the edges and those
103moves as well as R, R', L and L' change the orientation of the corners.
104Edge orientation is easy to address: we simply xor the edge representation
105by a bit mask with zeroes everywhere except for the 4 edges that need
106to be flipped (i.e. the ones on the twisted face).
107
108Corner orientation is harder to reproduce efficiently working only with
109bitwise operations, as it involves performing operations modulo 3.
110However, with the help of the extra bit we reserved, we are able to
111do this using only two additions and 3 bitwise operations, without
112any multiplication, division or modulo operation. The trick is
113to use the following formula to sum two numbers x, y in {0,1,2}:
114
115 ((x+y) + (x+y+1)/4) % 4
116
117The thrid bit is needed because x+y and x+y+1 can exceed 3. We can
118apply this operation to multiple pairs of bits representing ternary
119digits at once using binary operations. See the function coapply()
120below for the details.
121
122## Inverting the cube
123
124TODO
125
126## Transformations (conjugations by full-cube rotations)
127
128TODO
129
130## Indexing (tentative)
131
132TODO - subgroup description etc
133
134*/
135
136#include <stdbool.h>
137#include <stdint.h>
138#include <string.h>
139
140#ifdef DEBUG
141#include <stdio.h>
142#endif
143
144#include "cube.h"
145
146#define _error 0xFFFFFFFF
147
148#define _eoblock 0x10ULL /* 10000 */
149#define _epblock 0x0FULL /* 01111 */
150#define _eblock 0x1FULL /* 11111 */
151#define _eblock2 0x3FFULL /* 1111111111 */
152
153#define _coblock 0x18ULL /* 011000 */
154#define _cpblock 0x07ULL /* 000111 */
155#define _cblock 0x3FULL /* 111111 */
156#define _cblock2 0xFFFULL /* 111111111111 */
157
158#define _eomask 0x842108421084210ULL /* 10000 repeated 12 times */
159#define _comask 0x618618618618ULL /* 011000 repeated 8 times */
160#define _coonemask 0x208208208208ULL /* 001000 repeated 8 times */
161#define _coextramask 0x820820820820ULL /* 100000 repeated 8 times */
162
163#define _emask_u (_eblock2 | _eblock2 << 20ULL)
164#define _emask_d (_eblock2 << 10ULL | _eblock2 << 30ULL)
165#define _emask_r (_eblock << 20ULL | _eblock2 << 35ULL | _eblock << 55ULL)
166#define _emask_l (_eblock2 << 45ULL | _eblock2 << 25ULL)
167#define _emask_f (_eblock | _eblock << 15ULL | _eblock2 << 40ULL)
168#define _emask_b (_eblock2 << 5ULL | _eblock2 << 50ULL)
169
170#define _cmask_u (_cblock2 | _cblock2 << 24ULL)
171#define _cmask_d (_cblock2 << 12ULL | _cblock2 << 36ULL)
172#define _cmask_r (_cblock | _cblock << 18ULL | _cblock2 << 30ULL)
173#define _cmask_l (_cblock2 << 6ULL | _cblock << 24ULL | _cblock << 42ULL)
174#define _cmask_f (_cblock | _cblock << 12ULL | _cblock << 24ULL | _cblock << 36ULL)
175#define _cmask_b (_cblock << 6ULL | _cblock << 18ULL | _cblock << 30ULL | _cblock << 42ULL)
176
177#define _eomask_f (1ULL << 4ULL | 1ULL << 19ULL | 1ULL << 44ULL | 1ULL << 49ULL)
178#define _eomask_b (1ULL << 9ULL | 1ULL << 14ULL | 1ULL << 54ULL | 1ULL << 59ULL)
179
180#define _comask_r (2ULL << 3ULL | 1ULL << 33ULL | 2ULL << 21ULL | 1ULL << 39ULL)
181#define _comask_l (1ULL << 27ULL | 2ULL << 9ULL | 2ULL << 15ULL | 1ULL << 45ULL)
182#define _comask_f (1ULL << 3ULL | 1ULL << 15ULL | 2ULL << 27ULL | 2ULL << 39ULL)
183#define _comask_b (1ULL << 9ULL | 1ULL << 21ULL | 2ULL << 33ULL | 2ULL << 45ULL)
184
185static inline uint64_t coapply(uint64_t, uint64_t);
186static uint64_t permsign(uint64_t *, int);
187static uint64_t readep(char *);
188static uint64_t readeo(char *);
189static uint64_t readcp(char *);
190static uint64_t readco(char *);
191static uint64_t readmove(char);
192static uint64_t readmodifier(char);
193
194static char *edgestr[] = {
195 "UF", "UB", "DB", "DF",
196 "UR", "UL", "DL", "DR",
197 "FR", "FL", "BL", "BR"
198};
199static char *cornerstr[] = {
200 "UFR", "UBL", "DFL", "DBR",
201 "UFL", "UBR", "DFR", "DBL"
202};
203static char *cornerstralt[] = {
204 "URF", "ULB", "DLF", "DRB",
205 "ULF", "URB", "DRF", "DLB"
206};
207static char *movestr[] = {
208 [U] = "U", [U2] = "U2", [U3] = "U'",
209 [D] = "D", [D2] = "D2", [D3] = "D'",
210 [R] = "R", [R2] = "R2", [R3] = "R'",
211 [L] = "L", [L2] = "L2", [L3] = "L'",
212 [F] = "F", [F2] = "F2", [F3] = "F'",
213 [B] = "B", [B2] = "B2", [B3] = "B'",
214};
215
216cube_t solvedcube = { .e = 0x5A928398A418820ULL, .c = 0x1C61440C2040ULL };
217cube_t errorcube = { .e = _error, .c = _error };
218
219
220static uint64_t
221permsign(uint64_t *a, int n)
222{
223 int i, j;
224 uint64_t ret;
225
226 ret = 0;
227
228 for (i = 0; i < n; i++)
229 for (j = i+1; j < n; j++)
230 ret += a[i] > a[j] ? 1 : 0;
231
232 return ret % 2;
233}
234
235bool
236isconsistent(cube_t cube)
237{
238 uint64_t x, p[12], sum, co;
239 bool found[12];
240 int i;
241
242 sum = 0;
243
244 /* Check for EP consistency */
245 for (i = 0; i < 12; i++)
246 found[i] = false;
247 for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
248 p[i] = x & _epblock;
249 if (p[i] >= 12)
250 goto inconsistent_ep;
251 found[p[i]] = true;
252 }
253 for (i = 0; i < 12; i++)
254 if (!found[i])
255 goto inconsistent_ep;
256 sum = permsign(p, 12);
257
258 /* Check for CP consistency */
259 for (i = 0; i < 8; i++)
260 found[i] = false;
261 for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
262 p[i] = x & _cpblock;
263 if (p[i] >= 8)
264 goto inconsistent_cp;
265 found[p[i]] = true;
266 }
267 for (i = 0; i < 8; i++)
268 if (!found[i])
269 goto inconsistent_cp;
270 sum += permsign(p, 8);
271
272 /* Check permutation parity */
273 if (sum % 2 != 0)
274 goto inconsistent_parity;
275
276 /* Check for EO parity */
277 for (i = 0, sum = 0, x = cube.e; i < 12; i++, x >>= 5ULL)
278 sum += (x & _eoblock) >> 4ULL;
279 if (sum % 2 != 0)
280 goto inconsistent_eo;
281
282 /* Check for CO parity */
283 for (i = 0, sum = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
284 co = (x & _coblock) >> 3ULL;
285 if (co > 2)
286 goto inconsistent_co3;
287 sum += co;
288 }
289 if (sum % 3 != 0)
290 goto inconsistent_co;
291
292 /* Check that CO extra bit is zero */
293 if (cube.c & _coextramask)
294 goto inconsistent_coextra;
295
296 return true;
297
298inconsistent_ep:
299#ifdef DEBUG
300 fprintf(stderr, "Inconsistent EP\n");
301#endif
302 goto inconsistent_return;
303inconsistent_cp:
304#ifdef DEBUG
305 fprintf(stderr, "Inconsistent CP\n");
306#endif
307 goto inconsistent_return;
308inconsistent_parity:
309#ifdef DEBUG
310 fprintf(stderr, "Inconsistent parity\n");
311#endif
312 goto inconsistent_return;
313inconsistent_eo:
314#ifdef DEBUG
315 fprintf(stderr, "Inconsistent EO\n");
316#endif
317 goto inconsistent_return;
318inconsistent_co3:
319#ifdef DEBUG
320 fprintf(stderr, "Inconsistent CO=3\n");
321#endif
322 goto inconsistent_return;
323inconsistent_co:
324#ifdef DEBUG
325 fprintf(stderr, "Inconsistent CO\n");
326#endif
327 goto inconsistent_return;
328inconsistent_coextra:
329#ifdef DEBUG
330 fprintf(stderr, "Inconsistent extra bit for CO\n");
331#endif
332 goto inconsistent_return;
333inconsistent_return:
334 return false;
335}
336
337bool
338issolved(cube_t cube)
339{
340 return cube.c == solvedcube.c && cube.e == solvedcube.e;
341}
342
343
344static uint64_t
345readep(char *str)
346{
347 uint64_t e;
348
349 for (e = 0; e < 12; e++)
350 if (!strncmp(str, edgestr[e], 2))
351 return e;
352
353#ifdef DEBUG
354 fprintf(stderr, "Error reading EP\n");
355#endif
356 return _error;
357}
358
359static uint64_t
360readeo(char *str)
361{
362 if (*str == '0')
363 return 0ULL;
364 if (*str == '1')
365 return 1ULL;
366
367#ifdef DEBUG
368 fprintf(stderr, "Error reading EO\n");
369#endif
370 return _error;
371}
372
373static uint64_t
374readcp(char *str)
375{
376 uint64_t c;
377
378 for (c = 0; c < 8; c++)
379 if (!strncmp(str, cornerstr[c], 3) ||
380 !strncmp(str, cornerstralt[c], 3))
381 return c;
382
383#ifdef DEBUG
384 fprintf(stderr, "Error reading CP\n");
385#endif
386 return _error;
387}
388
389static uint64_t
390readco(char *str)
391{
392 if (*str == '0')
393 return 0ULL;
394 if (*str == '1')
395 return 1ULL;
396 if (*str == '2')
397 return 2ULL;
398
399#ifdef DEBUG
400 fprintf(stderr, "Error reading CO\n");
401#endif
402 return _error;
403}
404
405cube_t
406readcube(char *buf)
407{
408 int i;
409 uint64_t piece, orient;
410 cube_t ret = {0};
411 char *b = buf;
412
413 for (i = 0; i < 12; i++) {
414 while (*b == ' ' || *b == '\t' || *b == '\n')
415 b++;
416 if ((piece = readep(b)) == _error)
417 goto readcube_error;
418 b += 2;
419 if ((orient = readeo(b)) == _error)
420 goto readcube_error;
421 b++;
422 ret.e |= (piece << (i * 5ULL)) | (orient << (i * 5ULL + 4ULL));
423 }
424 for (i = 0; i < 8; i++) {
425 while (*b == ' ' || *b == '\t' || *b == '\n')
426 b++;
427 if ((piece = readcp(b)) == _error)
428 goto readcube_error;
429 b += 3;
430 if ((orient = readco(b)) == _error)
431 goto readcube_error;
432 b++;
433 ret.c |= (piece << (i * 6ULL)) | (orient << (i * 6ULL + 3ULL));
434 }
435
436 return ret;
437
438readcube_error:
439#ifdef DEBUG
440 fprintf(stderr, "readcube error\n");
441#endif
442 return errorcube;
443}
444
445void
446writecube(cube_t cube, char *buf)
447{
448 char *errormsg;
449 uint64_t piece, orien, x;
450 size_t len;
451 int i;
452
453 if (!isconsistent(cube)) {
454 errormsg = "ERROR: cannot write inconsistent cube";
455 goto writecube_error;
456 }
457
458 for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
459 piece = x & _epblock;
460 orien = (x & _eoblock) >> 4ULL;
461 buf[4*i ] = edgestr[piece][0];
462 buf[4*i + 1] = edgestr[piece][1];
463 buf[4*i + 2] = orien + '0';
464 buf[4*i + 3] = ' ';
465 }
466 for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
467 piece = x & _cpblock;
468 orien = (x & _coblock) >> 3ULL;
469 buf[48 + 5*i ] = cornerstr[piece][0];
470 buf[48 + 5*i + 1] = cornerstr[piece][1];
471 buf[48 + 5*i + 2] = cornerstr[piece][2];
472 buf[48 + 5*i + 3] = orien + '0';
473 buf[48 + 5*i + 4] = ' ';
474 }
475
476 buf[48+39] = '\0';
477
478 return;
479
480writecube_error:
481#ifdef DEBUG
482 fprintf(stderr, "writecube error, see stdout for details\n");
483#endif
484 len = strlen(errormsg);
485 memcpy(buf, errormsg, len);
486 buf[len] = '\n';
487 buf[len+1] = '\0';
488}
489
490
491static uint64_t
492readmove(char c)
493{
494 switch (c) {
495 case 'U':
496 return U;
497 case 'D':
498 return D;
499 case 'R':
500 return R;
501 case 'L':
502 return L;
503 case 'F':
504 return F;
505 case 'B':
506 return B;
507 default:
508 return _error;
509 }
510}
511
512static uint64_t
513readmodifier(char c)
514{
515 switch (c) {
516 case '1': /* Fallthrough */
517 case '2': /* Fallthrough */
518 case '3':
519 return c - '0' - 1;
520 case '\'':
521 return 2;
522 default:
523 return 0;
524 }
525}
526
527int
528readmoves(char *buf, move_t *m)
529{
530 int n;
531 uint64_t r;
532 char *b;
533
534 for (b = buf, n = 0; *b != '\0'; b++) {
535 while (*b == ' ' || *b == '\t' || *b == '\n')
536 b++;
537 if (*b == '\0')
538 return n;
539 if ((r = readmove(*b)) == _error)
540 goto readmoves_error;
541 m[n] = (move_t)r;
542 if ((r = readmodifier(*(b+1))) != 0) {
543 b++;
544 m[n] += r;
545 }
546 n++;
547 }
548
549 return n;
550
551readmoves_error:
552#ifdef DEBUG
553 fprintf(stderr, "readmoves error\n");
554#endif
555 return -1;
556}
557
558void
559writemoves(move_t *m, int n, char *buf)
560{
561 int i;
562 size_t len;
563 char *b, *s;
564
565 for (i = 0, b = buf; i < n; i++, b++) {
566 s = movestr[m[i]];
567 len = strlen(s);
568 memcpy(b, s, len);
569 b += len;
570 *b = ' ';
571 }
572 *b = '\0';
573}
574
575
576static inline uint64_t
577coapply(uint64_t c, uint64_t m)
578{
579 uint64_t z, b;
580
581 z = c + m;
582 b = ((z + _coonemask) & _coextramask) >> 2ULL;
583
584 return (z + b) & ~_coextramask;
585}
586
587cube_t
588move(cube_t c, move_t m)
589{
590 cube_t ret = {0};
591
592#ifdef DEBUG
593 if (!isconsistent(c)) {
594 fprintf(stderr, "move error, inconsistent cube\n");
595 goto move_error;
596 }
597#endif
598
599 switch (m) {
600 case U:
601 ret.e = c.e & ~_emask_u;
602 ret.e |=
603 (c.e & _eblock) << 25ULL |
604 (c.e & _eblock << 5ULL) << 15ULL |
605 (c.e & _eblock2 << 20ULL) >> 20ULL;
606
607 ret.c = c.c & ~_cmask_u;
608 ret.c |=
609 (c.c & _cblock2) << 24ULL |
610 (c.c & _cblock << 24ULL) >> 18ULL |
611 (c.c & _cblock << 30ULL) >> 30ULL;
612
613 return ret;
614 case U2:
615 ret.e = c.e & ~_emask_u;
616 ret.e |=
617 (c.e & (_eblock | _eblock << 20ULL)) << 5ULL |
618 (c.e & (_eblock << 5ULL | _eblock << 25ULL)) >> 5ULL;
619
620 ret.c = c.c & ~_cmask_u;
621 ret.c |=
622 (c.c & (_cblock | _cblock << 24ULL)) << 6ULL |
623 (c.c & (_cblock << 6ULL | _cblock << 30ULL)) >> 6ULL;
624
625 return ret;
626 case U3:
627 ret.e = c.e & ~_emask_u;
628 ret.e |=
629 (c.e & _eblock2) << 20ULL |
630 (c.e & _eblock << 25ULL) >> 25ULL |
631 (c.e & _eblock << 20ULL) >> 15ULL;
632
633 ret.c = c.c & ~_cmask_u;
634 ret.c |=
635 (c.c & _cblock) << 30ULL |
636 (c.c & _cblock << 6ULL) << 18ULL |
637 (c.c & _cblock2 << 24ULL) >> 24ULL;
638
639 return ret;
640 case D:
641 ret.e = c.e & ~_emask_d;
642 ret.e |=
643 (c.e & _eblock2 << 10ULL) << 20ULL |
644 (c.e & _eblock << 30ULL) >> 15ULL |
645 (c.e & _eblock << 35ULL) >> 25ULL;
646
647 ret.c = c.c & ~_cmask_d;
648 ret.c |=
649 (c.c & _cblock2 << 12ULL) << 24ULL |
650 (c.c & _cblock << 36ULL) >> 18ULL |
651 (c.c & _cblock << 42ULL) >> 30ULL;
652
653 return ret;
654 case D2:
655 ret.e = c.e & ~_emask_d;
656 ret.e |=
657 (c.e & (_eblock << 10ULL | _eblock << 30ULL)) << 5ULL |
658 (c.e & (_eblock << 15ULL | _eblock << 35ULL)) >> 5ULL;
659
660 ret.c = c.c & ~_cmask_d;
661 ret.c |=
662 (c.c & (_cblock << 12ULL | _cblock << 36ULL)) << 6ULL |
663 (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 6ULL;
664
665 return ret;
666 case D3:
667 ret.e = c.e & ~_emask_d;
668 ret.e |=
669 (c.e & _eblock << 10ULL) << 25ULL |
670 (c.e & _eblock << 15ULL) << 15ULL |
671 (c.e & _eblock2 << 30ULL) >> 20ULL;
672
673 ret.c = c.c & ~_cmask_d;
674 ret.c |=
675 (c.c & _cblock << 12ULL) << 30ULL |
676 (c.c & _cblock << 18ULL) << 18ULL |
677 (c.c & _cblock2 << 36ULL) >> 24ULL;
678
679 return ret;
680 case R:
681 ret.e = c.e & ~_emask_r;
682 ret.e |=
683 (c.e & _eblock << 20ULL) << 35ULL |
684 (c.e & _eblock << 55ULL) >> 20ULL |
685 (c.e & _eblock << 35ULL) << 5ULL |
686 (c.e & _eblock << 40ULL) >> 20ULL;
687
688 ret.c = c.c & ~_cmask_r;
689 ret.c |=
690 (c.c & _cblock) << 30ULL |
691 (c.c & _cblock << 30ULL) >> 12ULL |
692 (c.c & _cblock << 18ULL) << 18ULL |
693 (c.c & _cblock << 36ULL) >> 36ULL;
694
695 ret.c = coapply(ret.c, _comask_r);
696
697 return ret;
698 case R2:
699 ret.e = c.e & ~_emask_r;
700 ret.e |=
701 (c.e & (_eblock << 20ULL | _eblock << 40ULL)) << 15ULL |
702 (c.e & (_eblock << 35ULL | _eblock << 55ULL)) >> 15ULL;
703
704 ret.c = c.c & ~_cmask_r;
705 ret.c |=
706 (c.c & _cblock) << 18ULL |
707 (c.c & _cblock << 18ULL) >> 18ULL |
708 (c.c & _cblock << 30ULL) << 6ULL |
709 (c.c & _cblock << 36ULL) >> 6ULL;
710
711 return ret;
712 case R3:
713 ret.e = c.e & ~_emask_r;
714 ret.e |=
715 (c.e & (_eblock << 20ULL | _eblock << 35ULL)) << 20ULL |
716 (c.e & _eblock << 55ULL) >> 35ULL |
717 (c.e & _eblock << 40ULL) >> 5ULL;
718
719 ret.c = c.c & ~_cmask_r;
720 ret.c |=
721 (c.c & _cblock) << 36ULL |
722 (c.c & _cblock << 30ULL) >> 30ULL |
723 (c.c & _cblock << 18ULL) << 12ULL |
724 (c.c & _cblock << 36ULL) >> 18ULL;
725
726 ret.c = coapply(ret.c, _comask_r);
727
728 return ret;
729 case L:
730 ret.e = c.e & ~_emask_l;
731 ret.e |=
732 (c.e & _eblock2 << 25ULL) << 20ULL |
733 (c.e & _eblock << 45ULL) >> 15ULL |
734 (c.e & _eblock << 50ULL) >> 25ULL;
735
736 ret.c = c.c & ~_cmask_l;
737 ret.c |=
738 (c.c & _cblock << 6ULL) << 18ULL |
739 (c.c & _cblock << 12ULL) << 30ULL |
740 (c.c & _cblock << 24ULL) >> 12ULL |
741 (c.c & _cblock << 42ULL) >> 36ULL;
742
743 ret.c = coapply(ret.c, _comask_l);
744
745 return ret;
746 case L2:
747 ret.e = c.e & ~_emask_l;
748 ret.e |=
749 (c.e & (_eblock << 25ULL | _eblock << 45ULL)) << 5ULL |
750 (c.e & (_eblock << 30ULL | _eblock << 50ULL)) >> 5ULL;
751
752 ret.c = c.c & ~_cmask_l;
753 ret.c |=
754 (c.c & _cblock << 6ULL) << 6ULL |
755 (c.c & _cblock << 12ULL) >> 6ULL |
756 (c.c & _cblock << 24ULL) << 18ULL |
757 (c.c & _cblock << 42ULL) >> 18ULL;
758
759 return ret;
760 case L3:
761 ret.e = c.e & ~_emask_l;
762 ret.e |=
763 (c.e & _eblock << 25ULL) << 25ULL |
764 (c.e & _eblock << 30ULL) << 15ULL |
765 (c.e & _eblock2 << 45ULL) >> 20ULL;
766
767 ret.c = c.c & ~_cmask_l;
768 ret.c |=
769 (c.c & _cblock << 6ULL) << 36ULL |
770 (c.c & _cblock << 12ULL) << 12ULL |
771 (c.c & _cblock << 24ULL) >> 18ULL |
772 (c.c & _cblock << 42ULL) >> 30ULL;
773
774 ret.c = coapply(ret.c, _comask_l);
775
776 return ret;
777 case F:
778 ret.e = c.e & ~_emask_f;
779 ret.e |=
780 (c.e & _eblock) << 40ULL |
781 (c.e & _eblock << 15ULL) << 30ULL |
782 (c.e & _eblock << 40ULL) >> 25ULL |
783 (c.e & _eblock << 45ULL) >> 45ULL;
784
785 ret.e ^= _eomask_f;
786
787 ret.c = c.c & ~_cmask_f;
788 ret.c |=
789 (c.c & _cblock) << 36ULL |
790 (c.c & (_cblock << 24ULL | _cblock << 36ULL)) >> 24ULL |
791 (c.c & _cblock << 12ULL) << 12ULL;
792
793 ret.c = coapply(ret.c, _comask_f);
794
795 return ret;
796 case F2:
797 ret.e = c.e & ~_emask_f;
798 ret.e |=
799 (c.e & _eblock) << 15ULL |
800 (c.e & _eblock << 15ULL) >> 15ULL |
801 (c.e & _eblock << 40ULL) << 5ULL |
802 (c.e & _eblock << 45ULL) >> 5ULL;
803
804 ret.c = c.c & ~_cmask_f;
805 ret.c |=
806 (c.c & (_cblock | _cblock << 24ULL)) << 12ULL |
807 (c.c & (_cblock << 12ULL | _cblock << 36ULL)) >> 12ULL;
808
809 return ret;
810 case F3:
811 ret.e = c.e & ~_emask_f;
812 ret.e |=
813 (c.e & _eblock) << 45ULL |
814 (c.e & _eblock << 15ULL) << 25ULL |
815 (c.e & _eblock << 40ULL) >> 40ULL |
816 (c.e & _eblock << 45ULL) >> 30ULL;
817
818 ret.e ^= _eomask_f;
819
820 ret.c = c.c & ~_cmask_f;
821 ret.c |=
822 (c.c & (_cblock | _cblock << 12ULL)) << 24ULL |
823 (c.c & _cblock << 24ULL) >> 12ULL |
824 (c.c & _cblock << 36ULL) >> 36ULL;
825
826 ret.c = coapply(ret.c, _comask_f);
827
828 return ret;
829 case B:
830 ret.e = c.e & ~_emask_b;
831 ret.e |=
832 (c.e & _eblock2 << 5ULL) << 45ULL |
833 (c.e & _eblock << 50ULL) >> 40ULL |
834 (c.e & _eblock << 55ULL) >> 50ULL;
835
836 ret.e ^= _eomask_b;
837
838 ret.c = c.c & ~_cmask_b;
839 ret.c |=
840 (c.c & _cblock << 6ULL) << 36ULL |
841 (c.c & _cblock << 18ULL) << 12ULL |
842 (c.c & (_cblock << 30ULL | _cblock << 42ULL)) >> 24ULL;
843
844 ret.c = coapply(ret.c, _comask_b);
845
846 return ret;
847 case B2:
848 ret.e = c.e & ~_emask_b;
849 ret.e |=
850 (c.e & (_eblock << 5ULL | _eblock << 50ULL)) << 5ULL |
851 (c.e & (_eblock << 10ULL | _eblock << 55ULL)) >> 5ULL;
852
853 ret.c = c.c & ~_cmask_b;
854 ret.c |=
855 (c.c & (_cblock << 6ULL | _cblock << 30ULL)) << 12ULL |
856 (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 12ULL;
857
858 return ret;
859 case B3:
860 ret.e = c.e & ~_emask_b;
861 ret.e |=
862 (c.e & _eblock << 5ULL) << 50ULL |
863 (c.e & _eblock << 10ULL) << 40ULL |
864 (c.e & _eblock2 << 50ULL) >> 45ULL;
865
866 ret.e ^= _eomask_b;
867
868 ret.c = c.c & ~_cmask_b;
869 ret.c |=
870 (c.c & (_cblock << 6ULL | _cblock << 18ULL)) << 24ULL |
871 (c.c & _cblock << 30ULL) >> 12ULL |
872 (c.c & _cblock << 42ULL) >> 36ULL;
873
874 ret.c = coapply(ret.c, _comask_b);
875
876 return ret;
877 default:
878 goto move_unknown;
879 }
880
881move_unknown:
882#ifdef DEBUG
883 fprintf(stderr, "move error, unknow move\n");
884#endif
885 goto move_error;
886move_error:
887 return errorcube;
888}
diff --git a/src/cube.h b/src/cube.h
index b916f96..836bb5d 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -3,25 +3,51 @@ typedef enum {
3 R, R2, R3, L, L2, L3, 3 R, R2, R3, L, L2, L3,
4 F, F2, F3, B, B2, B3 4 F, F2, F3, B, B2, B3
5} move_t; 5} move_t;
6
6typedef struct { 7typedef struct {
7 uint64_t e; 8 uint8_t c[8];
8 uint64_t c; 9 uint8_t e[12];
9} cube_t; 10} cube_t;
10 11
11extern cube_t solvedcube; 12extern cube_t solvedcube;
12extern cube_t errorcube;
13 13
14bool isconsistent(cube_t); 14/*
15bool issolved(cube_t); 15The functions readcube() and writecube() use the following format.
16
17Each edge is represented by two letters denoting the sides it belongs to
18and one number denoting its orientation (0 oriented, 1 mis-oriented).
19Similarly, each corner is represented by three letters and a number
20(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
21Edge orientation is relative to the F / B axis, corner orientation is
22relative to the U / D axis.
23
24The pieces are ordered such that the solved cube looks like this:
25
26UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
27UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
28
29Whitespace (including newlines) between pieces is ignored when reading
30the cube, and a single whitespace character is added between pieces
31when writing.
32
33The cube after the moves R'U'F looks like this:
34
35FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
36UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
37
38More formats might be supported in the future.
39*/
16 40
17cube_t readcube(char *); 41cube_t readcube(char *);
18void writecube(cube_t, char *); 42void writecube(cube_t, char *);
19 43
44bool isconsistent(cube_t);
45bool equal(cube_t, cube_t);
46bool issolved(cube_t);
47bool iserror(cube_t);
48
20int readmoves(char *, move_t *); 49int readmoves(char *, move_t *);
21void writemoves(move_t *, int, char *); 50void writemoves(move_t *, int, char *);
22 51
23cube_t move(cube_t, move_t); 52cube_t move(cube_t, move_t);
24
25/*
26cube_t inverse(cube_t); 53cube_t inverse(cube_t);
27*/

Generated with cgit - Back to sebastiano.tronto.net