aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--README.md107
-rw-r--r--doc/CUBE_INTERNAL.md24
-rw-r--r--doc/CUBE_TEXT.md37
-rw-r--r--doc/TRANSFORMATIONS.md23
-rw-r--r--src/_constants.c72
-rw-r--r--src/cube.h90
-rw-r--r--test/050_transform/transform_tests.c2
7 files changed, 178 insertions, 177 deletions
diff --git a/README.md b/README.md
index fb941c8..59a6bcc 100644
--- a/README.md
+++ b/README.md
@@ -1,6 +1,8 @@
1# Prototype for a new optimal solver 1# Prototype for a new optimal solver
2 2
3Work in progress. 3Work in progress. There is some documentation at the bottom of this page,
4but do not believe it. Everything is in a state of flux and can change
5without notice.
4 6
5## Running tests 7## Running tests
6 8
@@ -38,9 +40,8 @@ $ make test
38 40
39### Documentation and interface 41### Documentation and interface
40 42
41* remove the constant #define's from cube.h (write a comment instead) 43* inline some documentation as comments in cube.h or cube.c
42* reconsider content of cube.h, remove some stuff 44* README.md (maybe convert to txt?) becomes the reference documentation
43* remove doc folder, inline documentation as comments in cube.h or cube.c
44 45
45### AVX2 46### AVX2
46 47
@@ -64,3 +65,101 @@ $ make test
64 [_mm256_shuffle_epi8](https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-10/mm256-shuffle-epi8.html)) 65 [_mm256_shuffle_epi8](https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-10/mm256-shuffle-epi8.html))
65* Inspect compiled assembly 66* Inspect compiled assembly
66* Use valgrind tool cachegrind and other profiling tools 67* Use valgrind tool cachegrind and other profiling tools
68
69
70## Internal representation of the cube
71
72The plan (TODO) is to have multiple implementations: some that
73take advantage of advanced CPU instructions (SIMD) and a fallback
74"array" representation that works on any architecture.
75
76### Array representation (fallback)
77
78In this implementation of the cube.h interface, the cube is represented
79by two arrays of 8-bit unsigned integers, one for centers and one for
80corners. The 4 leas-significant digits of each bit determine the piece,
81the other 4 are used for orientation or kept to 0.
82
83Edges:
84 xxxopppp (x = unused, o = orientation, p = piece)
85
86Corners:
87 xooxpppp (x = unused, o = orientation, p = piece)
88
89The two bits for CO are shifted to make it possible to perform mod 3
90operations (sum, inverse) using only addition and bitwise operators.
91See below for details.
92
93The third bit is needed because x+y+1 can exceed 4.
94
95### AVX2
96
97Work in progress
98
99
100## Textual representation of the cube
101
102The functions readcube() and writecube() use different formats to read
103and write a cube to text. Not all formats are supported for both input
104and output.
105
106### H48 - standard format for h48 (read, write)
107
108Each edge is represented by two letters denoting the sides it belongs to
109and one number denoting its orientation (0 oriented, 1 mis-oriented).
110Similarly, each corner is represented by three letters and a number
111(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
112Edge orientation is relative to the F / B axis, corner orientation is
113relative to the U / D axis.
114
115The pieces are ordered such that the solved cube looks like this:
116
117UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
118UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
119
120Whitespace (including newlines) between pieces is ignored when reading
121the cube, and a single whitespace character is added between pieces
122when writing.
123
124The cube after the moves R'U'F looks like this:
125
126FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
127UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
128
129### SRC - representation of the object in C code for cube_array (write)
130
131The exact format depends on the internal cube representation (TODO: actually
132this is false, because I need all formats for code generation; also adapating
133tests is hard). It is guaranteed that, if OUT is the output in this format,
134the line
135
136cube_t cube = OUT;
137
138is interpreted correctly by h48.
139
140
141## Transformations
142
143Transformations can be either simple rotations or a rotation composed
144with a mirroring.
145
146Simple rotations are denoted by two letters corresponding to the faces
147to be moved to the U and F positions, respectively. For example FD is
148the rotation that brings the F face on top and the D face on front.
149
150A composed rotation + mirror is obtained by applying the corresponding
151rotation to the solved cube mirrored along the M plane.
152
153For example, to apply the transformation RBm (mirrored RB) to a cube C:
154 1a. Apply a mirror along the M plane to the solved cube
155 1b. Rotate the mirrored cube with z' y2
156 3. Apply the cube C to the transformed solved cube
157 4. Apply the transformations of step 1a and 1b in reverse
158
159The orientation of pieces after a rotation ignores the new position
160of centers. A rotated cube can technically be inconsistent, because
161the parity of the edge permutation has to be adjusted considering the
162parity of the centers, which we ignore.
163
164The utility script mirror.sh transforms a solved, rotated cube to its
165mirrored and rotated version.
diff --git a/doc/CUBE_INTERNAL.md b/doc/CUBE_INTERNAL.md
deleted file mode 100644
index fd3148a..0000000
--- a/doc/CUBE_INTERNAL.md
+++ /dev/null
@@ -1,24 +0,0 @@
1# Internal representation of the cube
2
3The plan (TODO) is to have multiple implementations: some that
4take advantage of advanced CPU instructions (SIMD) and a fallback
5"array" representation that works on any architecture.
6
7# Array representation (fallback)
8
9In this implementation of the cube.h interface, the cube is represented
10by two arrays of 8-bit unsigned integers, one for centers and one for
11corners. The 4 leas-significant digits of each bit determine the piece,
12the other 4 are used for orientation or kept to 0.
13
14Edges:
15 xxxopppp (x = unused, o = orientation, p = piece)
16
17Corners:
18 xooxpppp (x = unused, o = orientation, p = piece)
19
20The two bits for CO are shifted to make it possible to perform mod 3
21operations (sum, inverse) using only addition and bitwise operators.
22See below for details.
23
24The third bit is needed because x+y+1 can exceed 4.
diff --git a/doc/CUBE_TEXT.md b/doc/CUBE_TEXT.md
deleted file mode 100644
index b9234fc..0000000
--- a/doc/CUBE_TEXT.md
+++ /dev/null
@@ -1,37 +0,0 @@
1# Textual representation of the cube
2
3The functions readcube() and writecube() use different formats to read
4and write a cube to text. Not all formats are supported for both input
5and output.
6
7## H48 - standard format for h48 (read, write)
8
9Each edge is represented by two letters denoting the sides it belongs to
10and one number denoting its orientation (0 oriented, 1 mis-oriented).
11Similarly, each corner is represented by three letters and a number
12(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
13Edge orientation is relative to the F / B axis, corner orientation is
14relative to the U / D axis.
15
16The pieces are ordered such that the solved cube looks like this:
17
18UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
19UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
20
21Whitespace (including newlines) between pieces is ignored when reading
22the cube, and a single whitespace character is added between pieces
23when writing.
24
25The cube after the moves R'U'F looks like this:
26
27FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
28UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
29
30## SRC - representation of the object in C code for cube_array (write)
31
32The exact format depends on the internal cube representation. It is
33guaranteed that, if OUT is the output in this format, the line
34
35cube_t cube = OUT;
36
37is interpreted correctly by h48.
diff --git a/doc/TRANSFORMATIONS.md b/doc/TRANSFORMATIONS.md
deleted file mode 100644
index 58446e8..0000000
--- a/doc/TRANSFORMATIONS.md
+++ /dev/null
@@ -1,23 +0,0 @@
1Transformations can be either simple rotations or a rotation composed
2with a mirroring.
3
4Simple rotations are denoted by two letters corresponding to the faces
5to be moved to the U and F positions, respectively. For example FD is
6the rotation that brings the F face on top and the D face on front.
7
8A composed rotation + mirror is obtained by applying the corresponding
9rotation to the solved cube mirrored along the M plane.
10
11For example, to apply the transformation RBm (mirrored RB) to a cube C:
12 1a. Apply a mirror along the M plane to the solved cube
13 1b. Rotate the mirrored cube with z' y2
14 3. Apply the cube C to the transformed solved cube
15 4. Apply the transformations of step 1a and 1b in reverse
16
17The orientation of pieces after a rotation ignores the new position
18of centers. A rotated cube can technically be inconsistent, because
19the parity of the edge permutation has to be adjusted considering the
20parity of the centers, which we ignore.
21
22The utility script mirror.sh transforms a solved, rotated cube to its
23mirrored and rotated version.
diff --git a/src/_constants.c b/src/_constants.c
index 0070990..a6b19fe 100644
--- a/src/_constants.c
+++ b/src/_constants.c
@@ -1,3 +1,75 @@
1#define U 0U
2#define U2 1U
3#define U3 2U
4#define D 3U
5#define D2 4U
6#define D3 5U
7#define R 6U
8#define R2 7U
9#define R3 8U
10#define L 9U
11#define L2 10U
12#define L3 11U
13#define F 12U
14#define F2 13U
15#define F3 14U
16#define B 15U
17#define B2 16U
18#define B3 17U
19
20#define UFr 0
21#define ULr 1
22#define UBr 2
23#define URr 3
24#define DFr 4
25#define DLr 5
26#define DBr 6
27#define DRr 7
28#define RUr 8
29#define RFr 9
30#define RDr 10
31#define RBr 11
32#define LUr 12
33#define LFr 13
34#define LDr 14
35#define LBr 15
36#define FUr 16
37#define FRr 17
38#define FDr 18
39#define FLr 19
40#define BUr 20
41#define BRr 21
42#define BDr 22
43#define BLr 23
44
45#define UFm 24
46#define ULm 25
47#define UBm 26
48#define URm 27
49#define DFm 28
50#define DLm 29
51#define DBm 30
52#define DRm 31
53#define RUm 32
54#define RFm 33
55#define RDm 34
56#define RBm 35
57#define LUm 36
58#define LFm 37
59#define LDm 38
60#define LBm 39
61#define FUm 40
62#define FRm 41
63#define FDm 42
64#define FLm 43
65#define BUm 44
66#define BRm 45
67#define BDm 46
68#define BLm 47
69
70#define errormove 99U
71#define errortrans 99U
72
1#define _c_ufr 0U 73#define _c_ufr 0U
2#define _c_ubl 1U 74#define _c_ubl 1U
3#define _c_dfl 2U 75#define _c_dfl 2U
diff --git a/src/cube.h b/src/cube.h
index 43d9172..fd0d3e8 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -1,6 +1,3 @@
1/* Types *********************************************************************/
2
3/* See doc/CUBE_INTERNAL.md for a description of the cube format */
4typedef struct { 1typedef struct {
5 uint8_t c[16]; 2 uint8_t c[16];
6 uint8_t e[16]; 3 uint8_t e[16];
@@ -14,8 +11,6 @@ typedef cube_arr_t cube_t;
14typedef uint8_t move_t; 11typedef uint8_t move_t;
15typedef uint8_t trans_t; 12typedef uint8_t trans_t;
16 13
17/* Functions *****************************************************************/
18
19int readmoves(char *, move_t *); 14int readmoves(char *, move_t *);
20void writemoves(move_t *, int, char *); 15void writemoves(move_t *, int, char *);
21trans_t readtrans(char *); 16trans_t readtrans(char *);
@@ -24,11 +19,9 @@ void writetrans(trans_t, char *);
24move_t inverse_move(move_t); 19move_t inverse_move(move_t);
25trans_t inverse_trans(trans_t); 20trans_t inverse_trans(trans_t);
26 21
27/* Not all formats are supported for both read and write. */
28/* See doc/CUBE_TEXT.md for details. */
29typedef enum {H48, SRC} format_t; 22typedef enum {H48, SRC} format_t;
30cube_t readcube(format_t, char *); 23cube_t readcube(format_t, char *); /* Supports: H48 */
31void writecube(format_t, cube_t, char *); 24void writecube(format_t, cube_t, char *); /* Supports: H48, SRC */
32 25
33cube_t solvedcube(void); 26cube_t solvedcube(void);
34cube_t zerocube(void); 27cube_t zerocube(void);
@@ -41,82 +34,3 @@ cube_t move(cube_t, move_t);
41cube_t inverse(cube_t); 34cube_t inverse(cube_t);
42cube_t compose(cube_t, cube_t); 35cube_t compose(cube_t, cube_t);
43cube_t transform(cube_t, trans_t); 36cube_t transform(cube_t, trans_t);
44
45/* Constants for moves and transformations ***********************************/
46
47/* Standard moves */
48#define U 0U
49#define U2 1U
50#define U3 2U
51#define D 3U
52#define D2 4U
53#define D3 5U
54#define R 6U
55#define R2 7U
56#define R3 8U
57#define L 9U
58#define L2 10U
59#define L3 11U
60#define F 12U
61#define F2 13U
62#define F3 14U
63#define B 15U
64#define B2 16U
65#define B3 17U
66
67/* Regular transformations (rotations) */
68#define UFr 0
69#define ULr 1
70#define UBr 2
71#define URr 3
72#define DFr 4
73#define DLr 5
74#define DBr 6
75#define DRr 7
76#define RUr 8
77#define RFr 9
78#define RDr 10
79#define RBr 11
80#define LUr 12
81#define LFr 13
82#define LDr 14
83#define LBr 15
84#define FUr 16
85#define FRr 17
86#define FDr 18
87#define FLr 19
88#define BUr 20
89#define BRr 21
90#define BDr 22
91#define BLr 23
92
93/* Mirrored transformations */
94#define UFm 24
95#define ULm 25
96#define UBm 26
97#define URm 27
98#define DFm 28
99#define DLm 29
100#define DBm 30
101#define DRm 31
102#define RUm 32
103#define RFm 33
104#define RDm 34
105#define RBm 35
106#define LUm 36
107#define LFm 37
108#define LDm 38
109#define LBm 39
110#define FUm 40
111#define FRm 41
112#define FDm 42
113#define FLm 43
114#define BUm 44
115#define BRm 45
116#define BDm 46
117#define BLm 47
118
119/* Errors */
120#define errormove 99U
121#define errortrans 99U
122
diff --git a/test/050_transform/transform_tests.c b/test/050_transform/transform_tests.c
index 1e49037..fabc9bc 100644
--- a/test/050_transform/transform_tests.c
+++ b/test/050_transform/transform_tests.c
@@ -14,7 +14,7 @@ int main() {
14 fgets(str, STRLENMAX, stdin); 14 fgets(str, STRLENMAX, stdin);
15 t = readtrans(str); 15 t = readtrans(str);
16 16
17 if (t == errortrans) { 17 if (t >= 48) {
18 printf("Error reading trans\n"); 18 printf("Error reading trans\n");
19 return 1; 19 return 1;
20 } 20 }

Generated with cgit - Back to sebastiano.tronto.net