commit 0c49ed5afc2ae9e4bc4aa1af9c655bbe1f3d14b8
parent 259c7326f78d5495f5dc51c619932599a5279f68
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Sun, 22 Oct 2023 14:48:42 +0200
Small change of plans, moved stuff around
Diffstat:
11 files changed, 1062 insertions(+), 1053 deletions(-)
diff --git a/doc/CUBE_INTERNAL.md b/doc/CUBE_INTERNAL.md
@@ -0,0 +1,24 @@
+# Internal representation of the cube
+
+The plan (TODO) is to have multiple implementations: some that
+take advantage of advanced CPU instructions (SIMD) and a fallback
+"array" representation that works on any architecture.
+
+# Array representation (fallback)
+
+In this implementation of the cube.h interface, the cube is represented
+by two arrays of 8-bit unsigned integers, one for centers and one for
+corners. The 4 leas-significant digits of each bit determine the piece,
+the other 4 are used for orientation or kept to 0.
+
+Edges:
+ xxxopppp (x = unused, o = orientation, p = piece)
+
+Corners:
+ xooxpppp (x = unused, o = orientation, p = piece)
+
+The two bits for CO are shifted to make it possible to perform mod 3
+operations (sum, inverse) using only addition and bitwise operators.
+See below for details.
+
+The third bit is needed because x+y+1 can exceed 4.
diff --git a/doc/CUBE_TEXT.md b/doc/CUBE_TEXT.md
@@ -0,0 +1,37 @@
+# Textual representation of the cube
+
+The functions readcube() and writecube() use different formats to read
+and write a cube to text. Not all formats are supported for both input
+and output.
+
+## H48 - standard format for h48 (read, write)
+
+Each edge is represented by two letters denoting the sides it belongs to
+and one number denoting its orientation (0 oriented, 1 mis-oriented).
+Similarly, each corner is represented by three letters and a number
+(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
+Edge orientation is relative to the F / B axis, corner orientation is
+relative to the U / D axis.
+
+The pieces are ordered such that the solved cube looks like this:
+
+UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
+UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
+
+Whitespace (including newlines) between pieces is ignored when reading
+the cube, and a single whitespace character is added between pieces
+when writing.
+
+The cube after the moves R'U'F looks like this:
+
+FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
+UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
+
+## SRC - representation of the object in C code for cube_array (write)
+
+The exact format depends on the internal cube representation. It is
+guaranteed that, if OUT is the output in this format, the line
+
+cube_t cube = OUT;
+
+is interpreted correctly by h48.
diff --git a/utils/TRANSFORMATIONS.txt b/doc/TRANSFORMATIONS.md
diff --git a/src/constants.h b/src/constants.h
@@ -1,75 +0,0 @@
-/* Standard moves */
-#define U 0U
-#define U2 1U
-#define U3 2U
-#define D 3U
-#define D2 4U
-#define D3 5U
-#define R 6U
-#define R2 7U
-#define R3 8U
-#define L 9U
-#define L2 10U
-#define L3 11U
-#define F 12U
-#define F2 13U
-#define F3 14U
-#define B 15U
-#define B2 16U
-#define B3 17U
-
-/* Regular transformations (rotations) */
-#define UFr 0
-#define ULr 1
-#define UBr 2
-#define URr 3
-#define DFr 4
-#define DLr 5
-#define DBr 6
-#define DRr 7
-#define RUr 8
-#define RFr 9
-#define RDr 10
-#define RBr 11
-#define LUr 12
-#define LFr 13
-#define LDr 14
-#define LBr 15
-#define FUr 16
-#define FRr 17
-#define FDr 18
-#define FLr 19
-#define BUr 20
-#define BRr 21
-#define BDr 22
-#define BLr 23
-
-/* Mirrored transformations */
-#define UFm 24
-#define ULm 25
-#define UBm 26
-#define URm 27
-#define DFm 28
-#define DLm 29
-#define DBm 30
-#define DRm 31
-#define RUm 32
-#define RFm 33
-#define RDm 34
-#define RBm 35
-#define LUm 36
-#define LFm 37
-#define LDm 38
-#define LBm 39
-#define FUm 40
-#define FRm 41
-#define FDm 42
-#define FLm 43
-#define BUm 44
-#define BRm 45
-#define BDm 46
-#define BLm 47
-
-/* Errors */
-#define errormove 99U
-#define errortrans 99U
diff --git a/src/cube.c b/src/cube.c
@@ -0,0 +1,911 @@
+#include <inttypes.h>
+#include <stdbool.h>
+#include <string.h>
+
+#ifdef DEBUG
+#include <stdio.h>
+#endif
+
+#include "cube.h"
+
+#define _c_ufr 0U
+#define _c_ubl 1U
+#define _c_dfl 2U
+#define _c_dbr 3U
+#define _c_ufl 4U
+#define _c_ubr 5U
+#define _c_dfr 6U
+#define _c_dbl 7U
+
+#define _e_uf 0U
+#define _e_ub 1U
+#define _e_db 2U
+#define _e_df 3U
+#define _e_ur 4U
+#define _e_ul 5U
+#define _e_dl 6U
+#define _e_dr 7U
+#define _e_fr 8U
+#define _e_fl 9U
+#define _e_bl 10U
+#define _e_br 11U
+
+#define _eoshift 4U
+#define _coshift 5U
+
+#define _pbits 0xFU
+#define _eobit 0x10U
+#define _cobits 0xF0U
+#define _cobits2 0x60U
+#define _ctwist_cw 0x20U
+#define _ctwist_ccw 0x40U
+#define _eflip 0x10U
+#define _error 0xFFU
+
+static char *cornerstr[] = {
+ [_c_ufr] = "UFR",
+ [_c_ubl] = "UBL",
+ [_c_dfl] = "DFL",
+ [_c_dbr] = "DBR",
+ [_c_ufl] = "UFL",
+ [_c_ubr] = "UBR",
+ [_c_dfr] = "DFR",
+ [_c_dbl] = "DBL"
+};
+
+static char *cornerstralt[] = {
+ [_c_ufr] = "URF",
+ [_c_ubl] = "ULB",
+ [_c_dfl] = "DLF",
+ [_c_dbr] = "DRB",
+ [_c_ufl] = "ULF",
+ [_c_ubr] = "URB",
+ [_c_dfr] = "DRF",
+ [_c_dbl] = "DLB"
+};
+
+static char *edgestr[] = {
+ [_e_uf] = "UF",
+ [_e_ub] = "UB",
+ [_e_db] = "DB",
+ [_e_df] = "DF",
+ [_e_ur] = "UR",
+ [_e_ul] = "UL",
+ [_e_dl] = "DL",
+ [_e_dr] = "DR",
+ [_e_fr] = "FR",
+ [_e_fl] = "FL",
+ [_e_bl] = "BL",
+ [_e_br] = "BR"
+};
+
+static char *movestr[] = {
+ [U] = "U",
+ [U2] = "U2",
+ [U3] = "U'",
+ [D] = "D",
+ [D2] = "D2",
+ [D3] = "D'",
+ [R] = "R",
+ [R2] = "R2",
+ [R3] = "R'",
+ [L] = "L",
+ [L2] = "L2",
+ [L3] = "L'",
+ [F] = "F",
+ [F2] = "F2",
+ [F3] = "F'",
+ [B] = "B",
+ [B2] = "B2",
+ [B3] = "B'",
+};
+
+static char *transstr[] = {
+ [UFr] = "rotation UF",
+ [UFm] = "mirrored UF",
+ [ULr] = "rotation UL",
+ [ULm] = "mirrored UL",
+ [UBr] = "rotation UB",
+ [UBm] = "mirrored UB",
+ [URr] = "rotation UR",
+ [URm] = "mirrored UR",
+ [DFr] = "rotation DF",
+ [DFm] = "mirrored DF",
+ [DLr] = "rotation DL",
+ [DLm] = "mirrored DL",
+ [DBr] = "rotation DB",
+ [DBm] = "mirrored DB",
+ [DRr] = "rotation DR",
+ [DRm] = "mirrored DR",
+ [RUr] = "rotation RU",
+ [RUm] = "mirrored RU",
+ [RFr] = "rotation RF",
+ [RFm] = "mirrored RF",
+ [RDr] = "rotation RD",
+ [RDm] = "mirrored RD",
+ [RBr] = "rotation RB",
+ [RBm] = "mirrored RB",
+ [LUr] = "rotation LU",
+ [LUm] = "mirrored LU",
+ [LFr] = "rotation LF",
+ [LFm] = "mirrored LF",
+ [LDr] = "rotation LD",
+ [LDm] = "mirrored LD",
+ [LBr] = "rotation LB",
+ [LBm] = "mirrored LB",
+ [FUr] = "rotation FU",
+ [FUm] = "mirrored FU",
+ [FRr] = "rotation FR",
+ [FRm] = "mirrored FR",
+ [FDr] = "rotation FD",
+ [FDm] = "mirrored FD",
+ [FLr] = "rotation FL",
+ [FLm] = "mirrored FL",
+ [BUr] = "rotation BU",
+ [BUm] = "mirrored BU",
+ [BRr] = "rotation BR",
+ [BRm] = "mirrored BR",
+ [BDr] = "rotation BD",
+ [BDm] = "mirrored BD",
+ [BLr] = "rotation BL",
+ [BLm] = "mirrored BL",
+};
+
+cube_t solvedcube = {
+ .c = {
+ [_c_ufr] = _c_ufr,
+ [_c_ubl] = _c_ubl,
+ [_c_dfl] = _c_dfl,
+ [_c_dbr] = _c_dbr,
+ [_c_ufl] = _c_ufl,
+ [_c_ubr] = _c_ubr,
+ [_c_dfr] = _c_dfr,
+ [_c_dbl] = _c_dbl
+ },
+ .e = {
+ [_e_uf] = _e_uf,
+ [_e_ub] = _e_ub,
+ [_e_db] = _e_db,
+ [_e_df] = _e_df,
+ [_e_ur] = _e_ur,
+ [_e_ul] = _e_ul,
+ [_e_dl] = _e_dl,
+ [_e_dr] = _e_dr,
+ [_e_fr] = _e_fr,
+ [_e_fl] = _e_fl,
+ [_e_bl] = _e_bl,
+ [_e_br] = _e_br
+ }
+};
+
+static cube_t errorcube = { .e = {0}, .c = {0} };
+
+static bool isconsistent(cube_t);
+static uint8_t readco(char *);
+static uint8_t readcp(char *);
+static uint8_t readeo(char *);
+static uint8_t readep(char *);
+static uint8_t readmove(char);
+static uint8_t readmodifier(char);
+static cube_t readcube_H48(char *);
+static void writecube_H48(cube_t, char *);
+static int writepiece_SRC(uint8_t, char *);
+static void writecube_SRC(cube_t, char *);
+static int permsign(uint8_t *, int);
+
+static uint8_t
+readco(char *str)
+{
+ if (*str == '0')
+ return 0;
+ if (*str == '1')
+ return _ctwist_cw;
+ if (*str == '2')
+ return _ctwist_ccw;
+
+#ifdef DEBUG
+ fprintf(stderr, "Error reading CO\n");
+#endif
+ return _error;
+}
+
+static uint8_t
+readcp(char *str)
+{
+ uint8_t c;
+
+ for (c = 0; c < 8; c++)
+ if (!strncmp(str, cornerstr[c], 3) ||
+ !strncmp(str, cornerstralt[c], 3))
+ return c;
+
+#ifdef DEBUG
+ fprintf(stderr, "Error reading CP\n");
+#endif
+ return _error;
+}
+
+static uint8_t
+readeo(char *str)
+{
+ if (*str == '0')
+ return 0;
+ if (*str == '1')
+ return _eflip;
+
+#ifdef DEBUG
+ fprintf(stderr, "Error reading EO\n");
+#endif
+ return _error;
+}
+
+static uint8_t
+readep(char *str)
+{
+ uint8_t e;
+
+ for (e = 0; e < 12; e++)
+ if (!strncmp(str, edgestr[e], 2))
+ return e;
+
+#ifdef DEBUG
+ fprintf(stderr, "Error reading EP\n");
+#endif
+ return _error;
+}
+
+static cube_t
+readcube_H48(char *buf)
+{
+ int i;
+ uint8_t piece, orient;
+ cube_t ret = {0};
+ char *b = buf;
+
+ for (i = 0; i < 12; i++) {
+ while (*b == ' ' || *b == '\t' || *b == '\n')
+ b++;
+ if ((piece = readep(b)) == _error)
+ return errorcube;
+ b += 2;
+ if ((orient = readeo(b)) == _error)
+ return errorcube;
+ b++;
+ ret.e[i] = piece | orient;
+ }
+ for (i = 0; i < 8; i++) {
+ while (*b == ' ' || *b == '\t' || *b == '\n')
+ b++;
+ if ((piece = readcp(b)) == _error)
+ return errorcube;
+ b += 3;
+ if ((orient = readco(b)) == _error)
+ return errorcube;
+ b++;
+ ret.c[i] = piece | orient;
+ }
+
+ return ret;
+}
+
+cube_t
+readcube(format_t format, char *buf)
+{
+ cube_t ret;
+
+ switch (format) {
+ case H48:
+ ret = readcube_H48(buf);
+ break;
+ default:
+ #ifdef DEBUG
+ fprintf(stderr, "Cannot read cube in the given format\n");
+ #endif
+ ret = errorcube;
+ }
+
+#ifdef DEBUG
+ if (iserror(ret))
+ fprintf(stderr, "readcube error\n");
+#endif
+ return ret;
+}
+
+static void
+writecube_H48(cube_t cube, char *buf)
+{
+ uint8_t piece, orient;
+ int i;
+
+ for (i = 0; i < 12; i++) {
+ piece = cube.e[i] & _pbits;
+ orient = (cube.e[i] & _eobit) >> _eoshift;
+ buf[4*i ] = edgestr[piece][0];
+ buf[4*i + 1] = edgestr[piece][1];
+ buf[4*i + 2] = orient + '0';
+ buf[4*i + 3] = ' ';
+ }
+ for (i = 0; i < 8; i++) {
+ piece = cube.c[i] & _pbits;
+ orient = (cube.c[i] & _cobits) >> _coshift;
+ buf[48 + 5*i ] = cornerstr[piece][0];
+ buf[48 + 5*i + 1] = cornerstr[piece][1];
+ buf[48 + 5*i + 2] = cornerstr[piece][2];
+ buf[48 + 5*i + 3] = orient + '0';
+ buf[48 + 5*i + 4] = ' ';
+ }
+
+ buf[48+39] = '\0';
+}
+
+static int
+writepiece_SRC(uint8_t piece, char *buf)
+{
+ char digits[3];
+ int i, len = 0;
+
+ while (piece != 0) {
+ digits[len++] = (piece % 10) + '0';
+ piece /= 10;
+ }
+
+ if (len == 0)
+ digits[len++] = '0';
+
+ for (i = 0; i < len; i++)
+ buf[i] = digits[len-i-1];
+
+ buf[len] = ',';
+ buf[len+1] = ' ';
+
+ return len+2;
+}
+
+static void
+writecube_SRC(cube_t cube, char *buf)
+{
+ int i, ptr;
+
+ memcpy(buf, "{\n\t.c = {", 9);
+ ptr = 9;
+
+ for (i = 0; i < 8; i++)
+ ptr += writepiece_SRC(cube.c[i], buf + ptr);
+
+ memcpy(buf+ptr-2, "},\n\t.e = {", 10);
+ ptr += 8;
+
+ for (i = 0; i < 12; i++)
+ ptr += writepiece_SRC(cube.e[i], buf + ptr);
+
+ memcpy(buf+ptr-2, "}\n}\0", 4);
+}
+
+void
+writecube(format_t format, cube_t cube, char *buf)
+{
+ char *errormsg;
+ size_t len;
+
+ if (!isconsistent(cube)) {
+ errormsg = "ERROR: cannot write inconsistent cube";
+ goto writecube_error;
+ }
+
+ switch (format) {
+ case H48:
+ writecube_H48(cube, buf);
+ break;
+ case SRC:
+ writecube_SRC(cube, buf);
+ break;
+ default:
+ errormsg = "ERROR: cannot write cube in the given format";
+ goto writecube_error;
+ }
+
+ return;
+
+writecube_error:
+#ifdef DEBUG
+ fprintf(stderr, "writecube error, see stdout for details\n");
+#endif
+ len = strlen(errormsg);
+ memcpy(buf, errormsg, len);
+ buf[len] = '\n';
+ buf[len+1] = '\0';
+}
+
+static uint8_t
+readmove(char c)
+{
+ switch (c) {
+ case 'U':
+ return U;
+ case 'D':
+ return D;
+ case 'R':
+ return R;
+ case 'L':
+ return L;
+ case 'F':
+ return F;
+ case 'B':
+ return B;
+ default:
+ return _error;
+ }
+}
+
+static uint8_t
+readmodifier(char c)
+{
+ switch (c) {
+ case '1': /* Fallthrough */
+ case '2': /* Fallthrough */
+ case '3':
+ return c - '0' - 1;
+ case '\'':
+ return 2;
+ default:
+ return 0;
+ }
+}
+
+int
+readmoves(char *buf, move_t *m)
+{
+ int n;
+ uint64_t r;
+ char *b;
+
+ for (b = buf, n = 0; *b != '\0'; b++) {
+ while (*b == ' ' || *b == '\t' || *b == '\n')
+ b++;
+ if (*b == '\0')
+ return n;
+ if ((r = readmove(*b)) == _error)
+ goto readmoves_error;
+ m[n] = (move_t)r;
+ if ((r = readmodifier(*(b+1))) != 0) {
+ b++;
+ m[n] += r;
+ }
+ n++;
+ }
+
+ return n;
+
+readmoves_error:
+#ifdef DEBUG
+ fprintf(stderr, "readmoves error\n");
+#endif
+ return -1;
+}
+
+trans_t
+readtrans(char *buf)
+{
+ uint8_t t;
+
+ for (t = 0; t < 48; t++)
+ if (!strncmp(buf, transstr[t], 11))
+ return t;
+
+#ifdef DEBUG
+ fprintf(stderr, "readtrans error\n");
+#endif
+ return errortrans;
+}
+
+void
+writemoves(move_t *m, int n, char *buf)
+{
+ int i;
+ size_t len;
+ char *b, *s;
+
+ for (i = 0, b = buf; i < n; i++, b++) {
+ s = movestr[m[i]];
+ len = strlen(s);
+ memcpy(b, s, len);
+ b += len;
+ *b = ' ';
+ }
+ *b = '\0';
+}
+
+void
+writetrans(trans_t t, char *buf)
+{
+ if (t >= 48)
+ memcpy(buf, "error trans", 11);
+ else
+ memcpy(buf, transstr[t], 11);
+ buf[11] = '\0';
+}
+
+static int
+permsign(uint8_t *a, int n)
+{
+ int i, j;
+ uint8_t ret = 0;
+
+ for (i = 0; i < n; i++)
+ for (j = i+1; j < n; j++)
+ ret += (a[i] & _pbits) > (a[j] & _pbits) ? 1 : 0;
+
+ return ret % 2;
+}
+
+static bool
+isconsistent(cube_t c)
+{
+ uint8_t i, p, e;
+ bool found[12];
+
+ for (i = 0; i < 12; i++)
+ found[i] = false;
+ for (i = 0; i < 12; i++) {
+ p = c.e[i] & _pbits;
+ e = c.e[i] & ~_pbits;
+ if (p >= 12)
+ goto inconsistent_ep;
+ if (e != 0 && e != _eobit)
+ goto inconsistent_eo;
+ found[p] = true;
+ }
+ for (i = 0; i < 12; i++)
+ if (!found[i])
+ goto inconsistent_ep;
+
+ for (i = 0; i < 8; i++)
+ found[i] = false;
+ for (i = 0; i < 8; i++) {
+ p = c.c[i] & _pbits;
+ e = c.c[i] & ~_pbits;
+ if (p >= 8)
+ goto inconsistent_cp;
+ if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw)
+ goto inconsistent_co;
+ found[p] = true;
+ }
+ for (i = 0; i < 8; i++)
+ if (!found[i])
+ goto inconsistent_co;
+
+ return true;
+
+inconsistent_ep:
+#ifdef DEBUG
+ fprintf(stderr, "Inconsistent EP\n");
+#endif
+ return false;
+inconsistent_cp:
+#ifdef DEBUG
+ fprintf(stderr, "Inconsistent CP\n");
+#endif
+ return false;
+inconsistent_eo:
+#ifdef DEBUG
+ fprintf(stderr, "Inconsistent EO\n");
+#endif
+ return false;
+inconsistent_co:
+#ifdef DEBUG
+ fprintf(stderr, "Inconsistent CO\n");
+#endif
+ return false;
+}
+
+bool
+issolvable(cube_t cube)
+{
+ int8_t i, eo, co;
+
+#ifdef DEBUG
+ if (!isconsistent(cube))
+ goto issolvable_inconsistent;
+#endif
+
+ if (permsign(cube.e, 12) != permsign(cube.c, 8))
+ goto issolvable_parity;
+
+ eo = 0;
+ for (i = 0; i < 12; i++)
+ eo += (cube.e[i] & _eobit) >> _eoshift;
+ if (eo % 2 != 0)
+ goto issolvable_eo;
+
+ co = 0;
+ for (i = 0; i < 8; i++)
+ co += (cube.c[i] & _cobits) >> _coshift;
+ if (co % 3 != 0)
+ goto issolvable_co;
+
+ return true;
+
+issolvable_inconsistent:
+#ifdef DEBUG
+ fprintf(stderr, "issolvable: cube is inconsistent\n");
+#endif
+ return false;
+issolvable_parity:
+#ifdef DEBUG
+ fprintf(stderr, "EP and CP parities are different\n");
+#endif
+ return false;
+issolvable_eo:
+#ifdef DEBUG
+ fprintf(stderr, "Odd number of flipped edges\n");
+#endif
+ return false;
+issolvable_co:
+#ifdef DEBUG
+ fprintf(stderr, "Sum of corner orientation is not multiple of 3\n");
+#endif
+ return false;
+}
+
+bool
+equal(cube_t cube1, cube_t cube2)
+{
+ uint8_t i;
+
+ for (i = 0; i < 12; i++)
+ if (cube1.e[i] != cube2.e[i])
+ return false;
+
+ for (i = 0; i < 8; i++)
+ if (cube1.c[i] != cube2.c[i])
+ return false;
+
+ return true;
+}
+
+bool
+issolved(cube_t cube)
+{
+ return equal(cube, solvedcube);
+}
+
+bool
+iserror(cube_t cube)
+{
+ return equal(cube, errorcube);
+}
+
+cube_t
+move(cube_t c, move_t m)
+{
+ cube_t ret;
+ uint8_t aux, auy, auz;
+
+#ifdef DEBUG
+ if (!isconsistent(c))
+ goto move_inconsistent;
+#endif
+
+#define PERM4(r, i, j, k, l) \
+ aux = r[i]; \
+ r[i] = r[l]; \
+ r[l] = r[k]; \
+ r[k] = r[j]; \
+ r[j] = aux;
+#define PERM22(r, i, j, k, l) \
+ aux = r[i]; \
+ r[i] = r[j]; \
+ r[j] = aux; \
+ aux = r[k]; \
+ r[k] = r[l]; \
+ r[l] = aux;
+#define CO(a, b) \
+ aux = (a & _cobits) + (b & _cobits); \
+ auy = (aux + _ctwist_cw) >> 2U; \
+ auz = (aux + auy) & _cobits2; \
+ a = (a & _pbits) | auz;
+#define CO4(r, i, j, k, l) \
+ CO(r[i], _ctwist_cw) \
+ CO(r[j], _ctwist_cw) \
+ CO(r[k], _ctwist_ccw) \
+ CO(r[l], _ctwist_ccw)
+#define EO4(r, i, j, k, l) \
+ r[i] ^= _eobit; \
+ r[j] ^= _eobit; \
+ r[k] ^= _eobit; \
+ r[l] ^= _eobit;
+
+ ret = c;
+
+ switch (m) {
+ case U:
+ PERM4(ret.e, _e_uf, _e_ul, _e_ub, _e_ur)
+ PERM4(ret.c, _c_ufr, _c_ufl, _c_ubl, _c_ubr)
+
+ return ret;
+ case U2:
+ PERM22(ret.e, _e_uf, _e_ub, _e_ul, _e_ur)
+ PERM22(ret.c, _c_ufr, _c_ubl, _c_ufl, _c_ubr)
+
+ return ret;
+ case U3:
+ PERM4(ret.e, _e_uf, _e_ur, _e_ub, _e_ul)
+ PERM4(ret.c, _c_ufr, _c_ubr, _c_ubl, _c_ufl)
+
+ return ret;
+ case D:
+ PERM4(ret.e, _e_df, _e_dr, _e_db, _e_dl)
+ PERM4(ret.c, _c_dfr, _c_dbr, _c_dbl, _c_dfl)
+
+ return ret;
+ case D2:
+ PERM22(ret.e, _e_df, _e_db, _e_dr, _e_dl)
+ PERM22(ret.c, _c_dfr, _c_dbl, _c_dbr, _c_dfl)
+
+ return ret;
+ case D3:
+ PERM4(ret.e, _e_df, _e_dl, _e_db, _e_dr)
+ PERM4(ret.c, _c_dfr, _c_dfl, _c_dbl, _c_dbr)
+
+ return ret;
+ case R:
+ PERM4(ret.e, _e_ur, _e_br, _e_dr, _e_fr)
+ PERM4(ret.c, _c_ufr, _c_ubr, _c_dbr, _c_dfr)
+
+ CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
+
+ return ret;
+ case R2:
+ PERM22(ret.e, _e_ur, _e_dr, _e_fr, _e_br)
+ PERM22(ret.c, _c_ufr, _c_dbr, _c_ubr, _c_dfr)
+
+ return ret;
+ case R3:
+ PERM4(ret.e, _e_ur, _e_fr, _e_dr, _e_br)
+ PERM4(ret.c, _c_ufr, _c_dfr, _c_dbr, _c_ubr)
+
+ CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
+
+ return ret;
+ case L:
+ PERM4(ret.e, _e_ul, _e_fl, _e_dl, _e_bl)
+ PERM4(ret.c, _c_ufl, _c_dfl, _c_dbl, _c_ubl)
+
+ CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
+
+ return ret;
+ case L2:
+ PERM22(ret.e, _e_ul, _e_dl, _e_fl, _e_bl)
+ PERM22(ret.c, _c_ufl, _c_dbl, _c_ubl, _c_dfl)
+
+ return ret;
+ case L3:
+ PERM4(ret.e, _e_ul, _e_bl, _e_dl, _e_fl)
+ PERM4(ret.c, _c_ufl, _c_ubl, _c_dbl, _c_dfl)
+
+ CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
+
+ return ret;
+ case F:
+ PERM4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
+ PERM4(ret.c, _c_ufr, _c_dfr, _c_dfl, _c_ufl)
+
+ EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
+ CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
+
+ return ret;
+ case F2:
+ PERM22(ret.e, _e_uf, _e_df, _e_fr, _e_fl)
+ PERM22(ret.c, _c_ufr, _c_dfl, _c_ufl, _c_dfr)
+
+ return ret;
+ case F3:
+ PERM4(ret.e, _e_uf, _e_fl, _e_df, _e_fr)
+ PERM4(ret.c, _c_ufr, _c_ufl, _c_dfl, _c_dfr)
+
+ EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
+ CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
+
+ return ret;
+ case B:
+ PERM4(ret.e, _e_ub, _e_bl, _e_db, _e_br)
+ PERM4(ret.c, _c_ubr, _c_ubl, _c_dbl, _c_dbr)
+
+ EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
+ CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
+
+ return ret;
+ case B2:
+ PERM22(ret.e, _e_ub, _e_db, _e_br, _e_bl)
+ PERM22(ret.c, _c_ubr, _c_dbl, _c_ubl, _c_dbr)
+
+ return ret;
+ case B3:
+ PERM4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
+ PERM4(ret.c, _c_ubr, _c_dbr, _c_dbl, _c_ubl)
+
+ EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
+ CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
+
+ return ret;
+ default:
+ goto move_unknown;
+ }
+
+move_inconsistent:
+ fprintf(stderr, "move error, inconsistent cube\n");
+ goto move_error;
+move_unknown:
+ fprintf(stderr, "mover error, unknown move\n");
+ goto move_error;
+move_error:
+ return errorcube;
+}
+
+cube_t
+inverse(cube_t c)
+{
+ uint8_t i, piece, orien;
+ cube_t ret = {0};
+
+#ifdef DEBUG
+ if (!isconsistent(c))
+ goto inverse_inconsistent;
+#endif
+
+ for (i = 0; i < 12; i++) {
+ piece = c.e[i & _pbits];
+ orien = piece & _eobit;
+ ret.e[piece & _pbits] = i | orien;
+ }
+
+ for (i = 0; i < 8; i++) {
+ piece = c.c[i & _pbits];
+ orien = ((piece << 1) | (piece >> 1)) & _cobits2;
+ ret.c[piece & _pbits] = i | orien;
+ }
+
+ return ret;
+
+inverse_inconsistent:
+ fprintf(stderr, "inverse error, inconsistent cube\n");
+ return errorcube;
+}
+
+cube_t
+compose(cube_t c1, cube_t c2)
+{
+ uint8_t i, piece, orien, aux, auy;
+ cube_t ret = {0};
+
+#ifdef DEBUG
+ if (!isconsistent(c1) || !isconsistent(c2))
+ goto compose_inconsistent;
+#endif
+
+ for (i = 0; i < 12; i++) {
+ piece = c2.e[i] & _pbits;
+ orien = (c2.e[i] ^ c1.e[piece]) & _eobit;
+ ret.e[i] = (c1.e[piece] & _pbits) | orien;
+ }
+
+ for (i = 0; i < 8; i++) {
+ piece = c2.c[i] & _pbits;
+ aux = (c2.c[i] & _cobits) + (c1.c[piece] & _cobits);
+ auy = (aux + _ctwist_cw) >> 2U;
+ orien = (aux + auy) & _cobits2;
+ ret.c[i] = (c1.c[piece] & _pbits) | orien;
+ }
+
+ return ret;
+
+compose_inconsistent:
+ fprintf(stderr, "compose error, inconsistent cube\n");
+ return errorcube;
+}
+
+cube_t
+transform(cube_t c, trans_t t)
+{
+ return errorcube;
+}
diff --git a/src/cube.h b/src/cube.h
@@ -1,14 +1,99 @@
+/* Constants *****************************************************************/
+
+/* Standard moves */
+#define U 0U
+#define U2 1U
+#define U3 2U
+#define D 3U
+#define D2 4U
+#define D3 5U
+#define R 6U
+#define R2 7U
+#define R3 8U
+#define L 9U
+#define L2 10U
+#define L3 11U
+#define F 12U
+#define F2 13U
+#define F3 14U
+#define B 15U
+#define B2 16U
+#define B3 17U
+
+/* Regular transformations (rotations) */
+#define UFr 0
+#define ULr 1
+#define UBr 2
+#define URr 3
+#define DFr 4
+#define DLr 5
+#define DBr 6
+#define DRr 7
+#define RUr 8
+#define RFr 9
+#define RDr 10
+#define RBr 11
+#define LUr 12
+#define LFr 13
+#define LDr 14
+#define LBr 15
+#define FUr 16
+#define FRr 17
+#define FDr 18
+#define FLr 19
+#define BUr 20
+#define BRr 21
+#define BDr 22
+#define BLr 23
+
+/* Mirrored transformations */
+#define UFm 24
+#define ULm 25
+#define UBm 26
+#define URm 27
+#define DFm 28
+#define DLm 29
+#define DBm 30
+#define DRm 31
+#define RUm 32
+#define RFm 33
+#define RDm 34
+#define RBm 35
+#define LUm 36
+#define LFm 37
+#define LDm 38
+#define LBm 39
+#define FUm 40
+#define FRm 41
+#define FDm 42
+#define FLm 43
+#define BUm 44
+#define BRm 45
+#define BDm 46
+#define BLm 47
+
+/* Errors */
+#define errormove 99U
+#define errortrans 99U
+
+/* Types *********************************************************************/
+
/* TODO: ifdef for different implementations */
-#include "cube_array.h"
+/* See doc/CUBE_INTERNAL.md for a description of the cube format */
+typedef struct {
+ uint8_t c[8];
+ uint8_t e[12];
+} cube_t;
-/* For moves and transformations, see constants.h */
typedef uint8_t move_t;
typedef uint8_t trans_t;
extern cube_t solvedcube;
+/* Functions *****************************************************************/
+
/* Not all formats are supported for both read and write. */
-/* See utils/FORMAT.txt for details. */
+/* See doc/CUBE_TEXT.md for details. */
typedef enum {H48, SRC} format_t;
cube_t readcube(format_t, char *);
void writecube(format_t, cube_t, char *);
@@ -28,5 +113,5 @@ cube_t move(cube_t, move_t);
cube_t inverse(cube_t);
cube_t compose(cube_t, cube_t);
-/* See utils/TRANSFORMATIONS.txt for how transformations are applied */
+/* See doc/TRANSFORMATIONS.md for how transformations are applied */
cube_t transform(cube_t, trans_t);
diff --git a/src/cube_array.c b/src/cube_array.c
@@ -1,931 +0,0 @@
-/*
-In this implementation of the cube.h interface, the cube is represented
-by two arrays of 8-bit unsigned integers, one for centers and one for
-corners. The 4 leas-significant digits of each bit determine the piece,
-the other 4 are used for orientation or kept to 0.
-
-Edges:
- xxxopppp (x = unused, o = orientation, p = piece)
-
-Corners:
- xooxpppp (x = unused, o = orientation, p = piece)
-
-The two bits for CO are shifted to make it possible to perform mod 3
-operations (sum, inverse) using only addition and bitwise operators.
-See below for details.
-
-The third bit is needed because x+y+1 can exceed 4.
-*/
-
-#include <inttypes.h>
-#include <stdbool.h>
-#include <string.h>
-
-#ifdef DEBUG
-#include <stdio.h>
-#endif
-
-#include "constants.h"
-#include "cube.h"
-
-#define _c_ufr 0U
-#define _c_ubl 1U
-#define _c_dfl 2U
-#define _c_dbr 3U
-#define _c_ufl 4U
-#define _c_ubr 5U
-#define _c_dfr 6U
-#define _c_dbl 7U
-
-#define _e_uf 0U
-#define _e_ub 1U
-#define _e_db 2U
-#define _e_df 3U
-#define _e_ur 4U
-#define _e_ul 5U
-#define _e_dl 6U
-#define _e_dr 7U
-#define _e_fr 8U
-#define _e_fl 9U
-#define _e_bl 10U
-#define _e_br 11U
-
-#define _eoshift 4U
-#define _coshift 5U
-
-#define _pbits 0xFU
-#define _eobit 0x10U
-#define _cobits 0xF0U
-#define _cobits2 0x60U
-#define _ctwist_cw 0x20U
-#define _ctwist_ccw 0x40U
-#define _eflip 0x10U
-#define _error 0xFFU
-
-static char *cornerstr[] = {
- [_c_ufr] = "UFR",
- [_c_ubl] = "UBL",
- [_c_dfl] = "DFL",
- [_c_dbr] = "DBR",
- [_c_ufl] = "UFL",
- [_c_ubr] = "UBR",
- [_c_dfr] = "DFR",
- [_c_dbl] = "DBL"
-};
-
-static char *cornerstralt[] = {
- [_c_ufr] = "URF",
- [_c_ubl] = "ULB",
- [_c_dfl] = "DLF",
- [_c_dbr] = "DRB",
- [_c_ufl] = "ULF",
- [_c_ubr] = "URB",
- [_c_dfr] = "DRF",
- [_c_dbl] = "DLB"
-};
-
-static char *edgestr[] = {
- [_e_uf] = "UF",
- [_e_ub] = "UB",
- [_e_db] = "DB",
- [_e_df] = "DF",
- [_e_ur] = "UR",
- [_e_ul] = "UL",
- [_e_dl] = "DL",
- [_e_dr] = "DR",
- [_e_fr] = "FR",
- [_e_fl] = "FL",
- [_e_bl] = "BL",
- [_e_br] = "BR"
-};
-
-static char *movestr[] = {
- [U] = "U",
- [U2] = "U2",
- [U3] = "U'",
- [D] = "D",
- [D2] = "D2",
- [D3] = "D'",
- [R] = "R",
- [R2] = "R2",
- [R3] = "R'",
- [L] = "L",
- [L2] = "L2",
- [L3] = "L'",
- [F] = "F",
- [F2] = "F2",
- [F3] = "F'",
- [B] = "B",
- [B2] = "B2",
- [B3] = "B'",
-};
-
-static char *transstr[] = {
- [UFr] = "rotation UF",
- [UFm] = "mirrored UF",
- [ULr] = "rotation UL",
- [ULm] = "mirrored UL",
- [UBr] = "rotation UB",
- [UBm] = "mirrored UB",
- [URr] = "rotation UR",
- [URm] = "mirrored UR",
- [DFr] = "rotation DF",
- [DFm] = "mirrored DF",
- [DLr] = "rotation DL",
- [DLm] = "mirrored DL",
- [DBr] = "rotation DB",
- [DBm] = "mirrored DB",
- [DRr] = "rotation DR",
- [DRm] = "mirrored DR",
- [RUr] = "rotation RU",
- [RUm] = "mirrored RU",
- [RFr] = "rotation RF",
- [RFm] = "mirrored RF",
- [RDr] = "rotation RD",
- [RDm] = "mirrored RD",
- [RBr] = "rotation RB",
- [RBm] = "mirrored RB",
- [LUr] = "rotation LU",
- [LUm] = "mirrored LU",
- [LFr] = "rotation LF",
- [LFm] = "mirrored LF",
- [LDr] = "rotation LD",
- [LDm] = "mirrored LD",
- [LBr] = "rotation LB",
- [LBm] = "mirrored LB",
- [FUr] = "rotation FU",
- [FUm] = "mirrored FU",
- [FRr] = "rotation FR",
- [FRm] = "mirrored FR",
- [FDr] = "rotation FD",
- [FDm] = "mirrored FD",
- [FLr] = "rotation FL",
- [FLm] = "mirrored FL",
- [BUr] = "rotation BU",
- [BUm] = "mirrored BU",
- [BRr] = "rotation BR",
- [BRm] = "mirrored BR",
- [BDr] = "rotation BD",
- [BDm] = "mirrored BD",
- [BLr] = "rotation BL",
- [BLm] = "mirrored BL",
-};
-
-cube_t solvedcube = {
- .c = {
- [_c_ufr] = _c_ufr,
- [_c_ubl] = _c_ubl,
- [_c_dfl] = _c_dfl,
- [_c_dbr] = _c_dbr,
- [_c_ufl] = _c_ufl,
- [_c_ubr] = _c_ubr,
- [_c_dfr] = _c_dfr,
- [_c_dbl] = _c_dbl
- },
- .e = {
- [_e_uf] = _e_uf,
- [_e_ub] = _e_ub,
- [_e_db] = _e_db,
- [_e_df] = _e_df,
- [_e_ur] = _e_ur,
- [_e_ul] = _e_ul,
- [_e_dl] = _e_dl,
- [_e_dr] = _e_dr,
- [_e_fr] = _e_fr,
- [_e_fl] = _e_fl,
- [_e_bl] = _e_bl,
- [_e_br] = _e_br
- }
-};
-
-static cube_t errorcube = { .e = {0}, .c = {0} };
-
-static bool isconsistent(cube_t);
-static uint8_t readco(char *);
-static uint8_t readcp(char *);
-static uint8_t readeo(char *);
-static uint8_t readep(char *);
-static uint8_t readmove(char);
-static uint8_t readmodifier(char);
-static cube_t readcube_H48(char *);
-static void writecube_H48(cube_t, char *);
-static int writepiece_SRC(uint8_t, char *);
-static void writecube_SRC(cube_t, char *);
-static int permsign(uint8_t *, int);
-
-static uint8_t
-readco(char *str)
-{
- if (*str == '0')
- return 0;
- if (*str == '1')
- return _ctwist_cw;
- if (*str == '2')
- return _ctwist_ccw;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading CO\n");
-#endif
- return _error;
-}
-
-static uint8_t
-readcp(char *str)
-{
- uint8_t c;
-
- for (c = 0; c < 8; c++)
- if (!strncmp(str, cornerstr[c], 3) ||
- !strncmp(str, cornerstralt[c], 3))
- return c;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading CP\n");
-#endif
- return _error;
-}
-
-static uint8_t
-readeo(char *str)
-{
- if (*str == '0')
- return 0;
- if (*str == '1')
- return _eflip;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading EO\n");
-#endif
- return _error;
-}
-
-static uint8_t
-readep(char *str)
-{
- uint8_t e;
-
- for (e = 0; e < 12; e++)
- if (!strncmp(str, edgestr[e], 2))
- return e;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading EP\n");
-#endif
- return _error;
-}
-
-static cube_t
-readcube_H48(char *buf)
-{
- int i;
- uint8_t piece, orient;
- cube_t ret = {0};
- char *b = buf;
-
- for (i = 0; i < 12; i++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if ((piece = readep(b)) == _error)
- return errorcube;
- b += 2;
- if ((orient = readeo(b)) == _error)
- return errorcube;
- b++;
- ret.e[i] = piece | orient;
- }
- for (i = 0; i < 8; i++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if ((piece = readcp(b)) == _error)
- return errorcube;
- b += 3;
- if ((orient = readco(b)) == _error)
- return errorcube;
- b++;
- ret.c[i] = piece | orient;
- }
-
- return ret;
-}
-
-cube_t
-readcube(format_t format, char *buf)
-{
- cube_t ret;
-
- switch (format) {
- case H48:
- ret = readcube_H48(buf);
- break;
- default:
- #ifdef DEBUG
- fprintf(stderr, "Cannot read cube in the given format\n");
- #endif
- ret = errorcube;
- }
-
-#ifdef DEBUG
- if (iserror(ret))
- fprintf(stderr, "readcube error\n");
-#endif
- return ret;
-}
-
-static void
-writecube_H48(cube_t cube, char *buf)
-{
- uint8_t piece, orient;
- int i;
-
- for (i = 0; i < 12; i++) {
- piece = cube.e[i] & _pbits;
- orient = (cube.e[i] & _eobit) >> _eoshift;
- buf[4*i ] = edgestr[piece][0];
- buf[4*i + 1] = edgestr[piece][1];
- buf[4*i + 2] = orient + '0';
- buf[4*i + 3] = ' ';
- }
- for (i = 0; i < 8; i++) {
- piece = cube.c[i] & _pbits;
- orient = (cube.c[i] & _cobits) >> _coshift;
- buf[48 + 5*i ] = cornerstr[piece][0];
- buf[48 + 5*i + 1] = cornerstr[piece][1];
- buf[48 + 5*i + 2] = cornerstr[piece][2];
- buf[48 + 5*i + 3] = orient + '0';
- buf[48 + 5*i + 4] = ' ';
- }
-
- buf[48+39] = '\0';
-}
-
-static int
-writepiece_SRC(uint8_t piece, char *buf)
-{
- char digits[3];
- int i, len = 0;
-
- while (piece != 0) {
- digits[len++] = (piece % 10) + '0';
- piece /= 10;
- }
-
- if (len == 0)
- digits[len++] = '0';
-
- for (i = 0; i < len; i++)
- buf[i] = digits[len-i-1];
-
- buf[len] = ',';
- buf[len+1] = ' ';
-
- return len+2;
-}
-
-static void
-writecube_SRC(cube_t cube, char *buf)
-{
- int i, ptr;
-
- memcpy(buf, "{\n\t.c = {", 9);
- ptr = 9;
-
- for (i = 0; i < 8; i++)
- ptr += writepiece_SRC(cube.c[i], buf + ptr);
-
- memcpy(buf+ptr-2, "},\n\t.e = {", 10);
- ptr += 8;
-
- for (i = 0; i < 12; i++)
- ptr += writepiece_SRC(cube.e[i], buf + ptr);
-
- memcpy(buf+ptr-2, "}\n}\0", 4);
-}
-
-void
-writecube(format_t format, cube_t cube, char *buf)
-{
- char *errormsg;
- size_t len;
-
- if (!isconsistent(cube)) {
- errormsg = "ERROR: cannot write inconsistent cube";
- goto writecube_error;
- }
-
- switch (format) {
- case H48:
- writecube_H48(cube, buf);
- break;
- case SRC:
- writecube_SRC(cube, buf);
- break;
- default:
- errormsg = "ERROR: cannot write cube in the given format";
- goto writecube_error;
- }
-
- return;
-
-writecube_error:
-#ifdef DEBUG
- fprintf(stderr, "writecube error, see stdout for details\n");
-#endif
- len = strlen(errormsg);
- memcpy(buf, errormsg, len);
- buf[len] = '\n';
- buf[len+1] = '\0';
-}
-
-static uint8_t
-readmove(char c)
-{
- switch (c) {
- case 'U':
- return U;
- case 'D':
- return D;
- case 'R':
- return R;
- case 'L':
- return L;
- case 'F':
- return F;
- case 'B':
- return B;
- default:
- return _error;
- }
-}
-
-static uint8_t
-readmodifier(char c)
-{
- switch (c) {
- case '1': /* Fallthrough */
- case '2': /* Fallthrough */
- case '3':
- return c - '0' - 1;
- case '\'':
- return 2;
- default:
- return 0;
- }
-}
-
-int
-readmoves(char *buf, move_t *m)
-{
- int n;
- uint64_t r;
- char *b;
-
- for (b = buf, n = 0; *b != '\0'; b++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if (*b == '\0')
- return n;
- if ((r = readmove(*b)) == _error)
- goto readmoves_error;
- m[n] = (move_t)r;
- if ((r = readmodifier(*(b+1))) != 0) {
- b++;
- m[n] += r;
- }
- n++;
- }
-
- return n;
-
-readmoves_error:
-#ifdef DEBUG
- fprintf(stderr, "readmoves error\n");
-#endif
- return -1;
-}
-
-trans_t
-readtrans(char *buf)
-{
- uint8_t t;
-
- for (t = 0; t < 48; t++)
- if (!strncmp(buf, transstr[t], 11))
- return t;
-
-#ifdef DEBUG
- fprintf(stderr, "readtrans error\n");
-#endif
- return errortrans;
-}
-
-void
-writemoves(move_t *m, int n, char *buf)
-{
- int i;
- size_t len;
- char *b, *s;
-
- for (i = 0, b = buf; i < n; i++, b++) {
- s = movestr[m[i]];
- len = strlen(s);
- memcpy(b, s, len);
- b += len;
- *b = ' ';
- }
- *b = '\0';
-}
-
-void
-writetrans(trans_t t, char *buf)
-{
- if (t >= 48)
- memcpy(buf, "error trans", 11);
- else
- memcpy(buf, transstr[t], 11);
- buf[11] = '\0';
-}
-
-static int
-permsign(uint8_t *a, int n)
-{
- int i, j;
- uint8_t ret = 0;
-
- for (i = 0; i < n; i++)
- for (j = i+1; j < n; j++)
- ret += (a[i] & _pbits) > (a[j] & _pbits) ? 1 : 0;
-
- return ret % 2;
-}
-
-static bool
-isconsistent(cube_t c)
-{
- uint8_t i, p, e;
- bool found[12];
-
- for (i = 0; i < 12; i++)
- found[i] = false;
- for (i = 0; i < 12; i++) {
- p = c.e[i] & _pbits;
- e = c.e[i] & ~_pbits;
- if (p >= 12)
- goto inconsistent_ep;
- if (e != 0 && e != _eobit)
- goto inconsistent_eo;
- found[p] = true;
- }
- for (i = 0; i < 12; i++)
- if (!found[i])
- goto inconsistent_ep;
-
- for (i = 0; i < 8; i++)
- found[i] = false;
- for (i = 0; i < 8; i++) {
- p = c.c[i] & _pbits;
- e = c.c[i] & ~_pbits;
- if (p >= 8)
- goto inconsistent_cp;
- if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw)
- goto inconsistent_co;
- found[p] = true;
- }
- for (i = 0; i < 8; i++)
- if (!found[i])
- goto inconsistent_co;
-
- return true;
-
-inconsistent_ep:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent EP\n");
-#endif
- return false;
-inconsistent_cp:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent CP\n");
-#endif
- return false;
-inconsistent_eo:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent EO\n");
-#endif
- return false;
-inconsistent_co:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent CO\n");
-#endif
- return false;
-}
-
-bool
-issolvable(cube_t cube)
-{
- int8_t i, eo, co;
-
-#ifdef DEBUG
- if (!isconsistent(cube))
- goto issolvable_inconsistent;
-#endif
-
- if (permsign(cube.e, 12) != permsign(cube.c, 8))
- goto issolvable_parity;
-
- eo = 0;
- for (i = 0; i < 12; i++)
- eo += (cube.e[i] & _eobit) >> _eoshift;
- if (eo % 2 != 0)
- goto issolvable_eo;
-
- co = 0;
- for (i = 0; i < 8; i++)
- co += (cube.c[i] & _cobits) >> _coshift;
- if (co % 3 != 0)
- goto issolvable_co;
-
- return true;
-
-issolvable_inconsistent:
-#ifdef DEBUG
- fprintf(stderr, "issolvable: cube is inconsistent\n");
-#endif
- return false;
-issolvable_parity:
-#ifdef DEBUG
- fprintf(stderr, "EP and CP parities are different\n");
-#endif
- return false;
-issolvable_eo:
-#ifdef DEBUG
- fprintf(stderr, "Odd number of flipped edges\n");
-#endif
- return false;
-issolvable_co:
-#ifdef DEBUG
- fprintf(stderr, "Sum of corner orientation is not multiple of 3\n");
-#endif
- return false;
-}
-
-bool
-equal(cube_t cube1, cube_t cube2)
-{
- uint8_t i;
-
- for (i = 0; i < 12; i++)
- if (cube1.e[i] != cube2.e[i])
- return false;
-
- for (i = 0; i < 8; i++)
- if (cube1.c[i] != cube2.c[i])
- return false;
-
- return true;
-}
-
-bool
-issolved(cube_t cube)
-{
- return equal(cube, solvedcube);
-}
-
-bool
-iserror(cube_t cube)
-{
- return equal(cube, errorcube);
-}
-
-cube_t
-move(cube_t c, move_t m)
-{
- cube_t ret;
- uint8_t aux, auy, auz;
-
-#ifdef DEBUG
- if (!isconsistent(c))
- goto move_inconsistent;
-#endif
-
-#define PERM4(r, i, j, k, l) \
- aux = r[i]; \
- r[i] = r[l]; \
- r[l] = r[k]; \
- r[k] = r[j]; \
- r[j] = aux;
-#define PERM22(r, i, j, k, l) \
- aux = r[i]; \
- r[i] = r[j]; \
- r[j] = aux; \
- aux = r[k]; \
- r[k] = r[l]; \
- r[l] = aux;
-#define CO(a, b) \
- aux = (a & _cobits) + (b & _cobits); \
- auy = (aux + _ctwist_cw) >> 2U; \
- auz = (aux + auy) & _cobits2; \
- a = (a & _pbits) | auz;
-#define CO4(r, i, j, k, l) \
- CO(r[i], _ctwist_cw) \
- CO(r[j], _ctwist_cw) \
- CO(r[k], _ctwist_ccw) \
- CO(r[l], _ctwist_ccw)
-#define EO4(r, i, j, k, l) \
- r[i] ^= _eobit; \
- r[j] ^= _eobit; \
- r[k] ^= _eobit; \
- r[l] ^= _eobit;
-
- ret = c;
-
- switch (m) {
- case U:
- PERM4(ret.e, _e_uf, _e_ul, _e_ub, _e_ur)
- PERM4(ret.c, _c_ufr, _c_ufl, _c_ubl, _c_ubr)
-
- return ret;
- case U2:
- PERM22(ret.e, _e_uf, _e_ub, _e_ul, _e_ur)
- PERM22(ret.c, _c_ufr, _c_ubl, _c_ufl, _c_ubr)
-
- return ret;
- case U3:
- PERM4(ret.e, _e_uf, _e_ur, _e_ub, _e_ul)
- PERM4(ret.c, _c_ufr, _c_ubr, _c_ubl, _c_ufl)
-
- return ret;
- case D:
- PERM4(ret.e, _e_df, _e_dr, _e_db, _e_dl)
- PERM4(ret.c, _c_dfr, _c_dbr, _c_dbl, _c_dfl)
-
- return ret;
- case D2:
- PERM22(ret.e, _e_df, _e_db, _e_dr, _e_dl)
- PERM22(ret.c, _c_dfr, _c_dbl, _c_dbr, _c_dfl)
-
- return ret;
- case D3:
- PERM4(ret.e, _e_df, _e_dl, _e_db, _e_dr)
- PERM4(ret.c, _c_dfr, _c_dfl, _c_dbl, _c_dbr)
-
- return ret;
- case R:
- PERM4(ret.e, _e_ur, _e_br, _e_dr, _e_fr)
- PERM4(ret.c, _c_ufr, _c_ubr, _c_dbr, _c_dfr)
-
- CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
-
- return ret;
- case R2:
- PERM22(ret.e, _e_ur, _e_dr, _e_fr, _e_br)
- PERM22(ret.c, _c_ufr, _c_dbr, _c_ubr, _c_dfr)
-
- return ret;
- case R3:
- PERM4(ret.e, _e_ur, _e_fr, _e_dr, _e_br)
- PERM4(ret.c, _c_ufr, _c_dfr, _c_dbr, _c_ubr)
-
- CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
-
- return ret;
- case L:
- PERM4(ret.e, _e_ul, _e_fl, _e_dl, _e_bl)
- PERM4(ret.c, _c_ufl, _c_dfl, _c_dbl, _c_ubl)
-
- CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
-
- return ret;
- case L2:
- PERM22(ret.e, _e_ul, _e_dl, _e_fl, _e_bl)
- PERM22(ret.c, _c_ufl, _c_dbl, _c_ubl, _c_dfl)
-
- return ret;
- case L3:
- PERM4(ret.e, _e_ul, _e_bl, _e_dl, _e_fl)
- PERM4(ret.c, _c_ufl, _c_ubl, _c_dbl, _c_dfl)
-
- CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
-
- return ret;
- case F:
- PERM4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
- PERM4(ret.c, _c_ufr, _c_dfr, _c_dfl, _c_ufl)
-
- EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
- CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
-
- return ret;
- case F2:
- PERM22(ret.e, _e_uf, _e_df, _e_fr, _e_fl)
- PERM22(ret.c, _c_ufr, _c_dfl, _c_ufl, _c_dfr)
-
- return ret;
- case F3:
- PERM4(ret.e, _e_uf, _e_fl, _e_df, _e_fr)
- PERM4(ret.c, _c_ufr, _c_ufl, _c_dfl, _c_dfr)
-
- EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
- CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
-
- return ret;
- case B:
- PERM4(ret.e, _e_ub, _e_bl, _e_db, _e_br)
- PERM4(ret.c, _c_ubr, _c_ubl, _c_dbl, _c_dbr)
-
- EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
- CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
-
- return ret;
- case B2:
- PERM22(ret.e, _e_ub, _e_db, _e_br, _e_bl)
- PERM22(ret.c, _c_ubr, _c_dbl, _c_ubl, _c_dbr)
-
- return ret;
- case B3:
- PERM4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
- PERM4(ret.c, _c_ubr, _c_dbr, _c_dbl, _c_ubl)
-
- EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
- CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
-
- return ret;
- default:
- goto move_unknown;
- }
-
-move_inconsistent:
- fprintf(stderr, "move error, inconsistent cube\n");
- goto move_error;
-move_unknown:
- fprintf(stderr, "mover error, unknown move\n");
- goto move_error;
-move_error:
- return errorcube;
-}
-
-cube_t
-inverse(cube_t c)
-{
- uint8_t i, piece, orien;
- cube_t ret = {0};
-
-#ifdef DEBUG
- if (!isconsistent(c))
- goto inverse_inconsistent;
-#endif
-
- for (i = 0; i < 12; i++) {
- piece = c.e[i & _pbits];
- orien = piece & _eobit;
- ret.e[piece & _pbits] = i | orien;
- }
-
- for (i = 0; i < 8; i++) {
- piece = c.c[i & _pbits];
- orien = ((piece << 1) | (piece >> 1)) & _cobits2;
- ret.c[piece & _pbits] = i | orien;
- }
-
- return ret;
-
-inverse_inconsistent:
- fprintf(stderr, "inverse error, inconsistent cube\n");
- return errorcube;
-}
-
-cube_t
-compose(cube_t c1, cube_t c2)
-{
- uint8_t i, piece, orien, aux, auy;
- cube_t ret = {0};
-
-#ifdef DEBUG
- if (!isconsistent(c1) || !isconsistent(c2))
- goto compose_inconsistent;
-#endif
-
- for (i = 0; i < 12; i++) {
- piece = c2.e[i] & _pbits;
- orien = (c2.e[i] ^ c1.e[piece]) & _eobit;
- ret.e[i] = (c1.e[piece] & _pbits) | orien;
- }
-
- for (i = 0; i < 8; i++) {
- piece = c2.c[i] & _pbits;
- aux = (c2.c[i] & _cobits) + (c1.c[piece] & _cobits);
- auy = (aux + _ctwist_cw) >> 2U;
- orien = (aux + auy) & _cobits2;
- ret.c[i] = (c1.c[piece] & _pbits) | orien;
- }
-
- return ret;
-
-compose_inconsistent:
- fprintf(stderr, "compose error, inconsistent cube\n");
- return errorcube;
-}
-
-cube_t
-transform(cube_t c, trans_t t)
-{
- return errorcube;
-}
diff --git a/src/cube_array.h b/src/cube_array.h
@@ -1,6 +0,0 @@
-/* Public properties specific to the array implementation */
-
-typedef struct {
- uint8_t c[8];
- uint8_t e[12];
-} cube_t;
diff --git a/test/05_transform/transform_tests.c b/test/05_transform/transform_tests.c
@@ -3,7 +3,6 @@
#include <stdio.h>
#include "../../src/cube.h"
-#include "../../src/constants.h"
#define STRLENMAX 10000
diff --git a/test/test.sh b/test/test.sh
@@ -5,7 +5,7 @@ CC="cc -DDEBUG -std=c99 -pthread -pedantic -Wall -Wextra \
if [ $(uname) != "OpenBSD" ]; then
CC="$CC -fsanitize=address -fsanitize=undefined"
fi
-SRC="src/cube_array.c"
+SRC="src/cube.c"
TESTBIN="test/run"
TESTOUT="test/last.out"
TESTERR="test/last.err"
diff --git a/utils/FORMAT.txt b/utils/FORMAT.txt
@@ -1,35 +0,0 @@
-The functions readcube() and writecube() use different formats to read
-and write a cube to text. Not all formats are supported for both input
-and output.
-
-# H48 - standard format for h48 (read, write)
-
-Each edge is represented by two letters denoting the sides it belongs to
-and one number denoting its orientation (0 oriented, 1 mis-oriented).
-Similarly, each corner is represented by three letters and a number
-(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
-Edge orientation is relative to the F / B axis, corner orientation is
-relative to the U / D axis.
-
-The pieces are ordered such that the solved cube looks like this:
-
-UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
-UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
-
-Whitespace (including newlines) between pieces is ignored when reading
-the cube, and a single whitespace character is added between pieces
-when writing.
-
-The cube after the moves R'U'F looks like this:
-
-FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
-UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
-
-# SRC - representation of the object in C code for cube_array (write)
-
-The exact format depends on the internal cube representation. It is
-guaranteed that, if OUT is the output in this format, the line
-
-cube_t cube = OUT;
-
-is interpreted correctly by h48.
