aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-05-10 08:55:03 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2024-05-10 08:55:03 +0200
commit75966319fd5891c2c1bd35b1f7c93eab172fd28e (patch)
tree850a69906c7140be36670f2014e78ff91a96ab33 /src
parent15a072db18e441db5aa9e5339341fa1a466b504a (diff)
downloadnissy-core-75966319fd5891c2c1bd35b1f7c93eab172fd28e.tar.gz
nissy-core-75966319fd5891c2c1bd35b1f7c93eab172fd28e.zip
Moved to src/
Diffstat (limited to 'src')
-rw-r--r--src/cube.c2392
-rw-r--r--src/cube.h164
2 files changed, 2556 insertions, 0 deletions
diff --git a/src/cube.c b/src/cube.c
new file mode 100644
index 0000000..02bbc63
--- /dev/null
+++ b/src/cube.c
@@ -0,0 +1,2392 @@
1#include <inttypes.h>
2#include <stdbool.h>
3#include <string.h>
4
5#include "cube.h"
6
7#ifdef DEBUG
8
9#include <stdio.h>
10#define _static
11#define _static_inline
12#define DBG_LOG(...) fprintf(stderr, __VA_ARGS__)
13#define DBG_WARN(condition, ...) if (!(condition)) DBG_LOG(__VA_ARGS__);
14#define DBG_ASSERT(condition, retval, ...) \
15 if (!(condition)) { \
16 DBG_LOG(__VA_ARGS__); \
17 return retval; \
18 }
19
20#else
21
22#define _static static
23#define _static_inline static inline
24#define DBG_LOG(...)
25#define DBG_WARN(condition, ...)
26#define DBG_ASSERT(condition, retval, ...)
27
28#endif
29
30/******************************************************************************
31Section: mathematical constants
32******************************************************************************/
33
34#define _2p11 2048U
35#define _2p12 4096U
36#define _3p7 2187U
37#define _3p8 6561U
38#define _12c4 495U
39#define _8c4 70U
40
41#define COCSEP_CLASSES 3393U
42
43_static int64_t binomial[12][12] = {
44 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
45 {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
46 {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
47 {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0},
48 {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0},
49 {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0},
50 {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0},
51 {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0},
52 {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0},
53 {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0},
54 {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0},
55 {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
56};
57
58/******************************************************************************
59Section: moves definitions and tables
60******************************************************************************/
61
62#define _move_U 0U
63#define _move_U2 1U
64#define _move_U3 2U
65#define _move_D 3U
66#define _move_D2 4U
67#define _move_D3 5U
68#define _move_R 6U
69#define _move_R2 7U
70#define _move_R3 8U
71#define _move_L 9U
72#define _move_L2 10U
73#define _move_L3 11U
74#define _move_F 12U
75#define _move_F2 13U
76#define _move_F3 14U
77#define _move_B 15U
78#define _move_B2 16U
79#define _move_B3 17U
80
81#define _trans_UFr 0
82#define _trans_ULr 1
83#define _trans_UBr 2
84#define _trans_URr 3
85#define _trans_DFr 4
86#define _trans_DLr 5
87#define _trans_DBr 6
88#define _trans_DRr 7
89#define _trans_RUr 8
90#define _trans_RFr 9
91#define _trans_RDr 10
92#define _trans_RBr 11
93#define _trans_LUr 12
94#define _trans_LFr 13
95#define _trans_LDr 14
96#define _trans_LBr 15
97#define _trans_FUr 16
98#define _trans_FRr 17
99#define _trans_FDr 18
100#define _trans_FLr 19
101#define _trans_BUr 20
102#define _trans_BRr 21
103#define _trans_BDr 22
104#define _trans_BLr 23
105
106#define _trans_UFm 24
107#define _trans_ULm 25
108#define _trans_UBm 26
109#define _trans_URm 27
110#define _trans_DFm 28
111#define _trans_DLm 29
112#define _trans_DBm 30
113#define _trans_DRm 31
114#define _trans_RUm 32
115#define _trans_RFm 33
116#define _trans_RDm 34
117#define _trans_RBm 35
118#define _trans_LUm 36
119#define _trans_LFm 37
120#define _trans_LDm 38
121#define _trans_LBm 39
122#define _trans_FUm 40
123#define _trans_FRm 41
124#define _trans_FDm 42
125#define _trans_FLm 43
126#define _trans_BUm 44
127#define _trans_BRm 45
128#define _trans_BDm 46
129#define _trans_BLm 47
130
131#define _c_ufr 0U
132#define _c_ubl 1U
133#define _c_dfl 2U
134#define _c_dbr 3U
135#define _c_ufl 4U
136#define _c_ubr 5U
137#define _c_dfr 6U
138#define _c_dbl 7U
139
140#define _e_uf 0U
141#define _e_ub 1U
142#define _e_db 2U
143#define _e_df 3U
144#define _e_ur 4U
145#define _e_ul 5U
146#define _e_dl 6U
147#define _e_dr 7U
148#define _e_fr 8U
149#define _e_fl 9U
150#define _e_bl 10U
151#define _e_br 11U
152
153#define _eoshift 4U
154#define _coshift 5U
155
156#define _pbits 0xFU
157#define _esepbit1 0x4U
158#define _esepbit2 0x8U
159#define _csepbit 0x4U
160#define _eobit 0x10U
161#define _cobits 0xF0U
162#define _cobits2 0x60U
163#define _ctwist_cw 0x20U
164#define _ctwist_ccw 0x40U
165#define _eflip 0x10U
166#define _error 0xFFU
167
168_static cube_t zero = { .corner = {0}, .edge = {0} };
169_static cube_t solved = {
170 .corner = {0, 1, 2, 3, 4, 5, 6, 7},
171 .edge = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
172};
173
174#define zero_fast fastcube( \
175 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
176#define solved_fast fastcube( \
177 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
178
179#define _move_cube_U fastcube( \
180 5, 4, 2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 1, 0, 6, 7, 8, 9, 10, 11)
181#define _move_cube_U2 fastcube( \
182 1, 0, 2, 3, 5, 4, 6, 7, 1, 0, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11)
183#define _move_cube_U3 fastcube( \
184 4, 5, 2, 3, 1, 0, 6, 7, 5, 4, 2, 3, 0, 1, 6, 7, 8, 9, 10, 11)
185#define _move_cube_D fastcube( \
186 0, 1, 7, 6, 4, 5, 2, 3, 0, 1, 7, 6, 4, 5, 2, 3, 8, 9, 10, 11)
187#define _move_cube_D2 fastcube( \
188 0, 1, 3, 2, 4, 5, 7, 6, 0, 1, 3, 2, 4, 5, 7, 6, 8, 9, 10, 11)
189#define _move_cube_D3 fastcube( \
190 0, 1, 6, 7, 4, 5, 3, 2, 0, 1, 6, 7, 4, 5, 3, 2, 8, 9, 10, 11)
191#define _move_cube_R fastcube( \
192 70, 1, 2, 69, 4, 32, 35, 7, 0, 1, 2, 3, 8, 5, 6, 11, 7, 9, 10, 4)
193#define _move_cube_R2 fastcube( \
194 3, 1, 2, 0, 4, 6, 5, 7, 0, 1, 2, 3, 7, 5, 6, 4, 11, 9, 10, 8)
195#define _move_cube_R3 fastcube( \
196 69, 1, 2, 70, 4, 35, 32, 7, 0, 1, 2, 3, 11, 5, 6, 8, 4, 9, 10, 7)
197#define _move_cube_L fastcube( \
198 0, 71, 68, 3, 33, 5, 6, 34, 0, 1, 2, 3, 4, 10, 9, 7, 8, 5, 6, 11)
199#define _move_cube_L2 fastcube( \
200 0, 2, 1, 3, 7, 5, 6, 4, 0, 1, 2, 3, 4, 6, 5, 7, 8, 10, 9, 11)
201#define _move_cube_L3 fastcube( \
202 0, 68, 71, 3, 34, 5, 6, 33, 0, 1, 2, 3, 4, 9, 10, 7, 8, 6, 5, 11)
203#define _move_cube_F fastcube( \
204 36, 1, 38, 3, 66, 5, 64, 7, 25, 1, 2, 24, 4, 5, 6, 7, 16, 19, 10, 11)
205#define _move_cube_F2 fastcube( \
206 2, 1, 0, 3, 6, 5, 4, 7, 3, 1, 2, 0, 4, 5, 6, 7, 9, 8, 10, 11)
207#define _move_cube_F3 fastcube( \
208 38, 1, 36, 3, 64, 5, 66, 7, 24, 1, 2, 25, 4, 5, 6, 7, 19, 16, 10, 11)
209#define _move_cube_B fastcube( \
210 0, 37, 2, 39, 4, 67, 6, 65, 0, 27, 26, 3, 4, 5, 6, 7, 8, 9, 17, 18)
211#define _move_cube_B2 fastcube( \
212 0, 3, 2, 1, 4, 7, 6, 5, 0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 11, 10)
213#define _move_cube_B3 fastcube( \
214 0, 39, 2, 37, 4, 65, 6, 67, 0, 26, 27, 3, 4, 5, 6, 7, 8, 9, 18, 17)
215
216#define _trans_cube_UFr fastcube( \
217 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
218#define _trans_cube_UFr_inverse fastcube( \
219 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
220#define _trans_cube_ULr fastcube( \
221 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24)
222#define _trans_cube_ULr_inverse fastcube( \
223 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26)
224#define _trans_cube_UBr fastcube( \
225 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9)
226#define _trans_cube_UBr_inverse fastcube( \
227 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9)
228#define _trans_cube_URr fastcube( \
229 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26)
230#define _trans_cube_URr_inverse fastcube( \
231 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24)
232#define _trans_cube_DFr fastcube( \
233 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10)
234#define _trans_cube_DFr_inverse fastcube( \
235 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10)
236#define _trans_cube_DLr fastcube( \
237 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27)
238#define _trans_cube_DLr_inverse fastcube( \
239 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27)
240#define _trans_cube_DBr fastcube( \
241 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8)
242#define _trans_cube_DBr_inverse fastcube( \
243 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8)
244#define _trans_cube_DRr fastcube( \
245 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25)
246#define _trans_cube_DRr_inverse fastcube( \
247 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25)
248#define _trans_cube_RUr fastcube( \
249 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3)
250#define _trans_cube_RUr_inverse fastcube( \
251 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21)
252#define _trans_cube_RFr fastcube( \
253 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18)
254#define _trans_cube_RFr_inverse fastcube( \
255 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17)
256#define _trans_cube_RDr fastcube( \
257 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1)
258#define _trans_cube_RDr_inverse fastcube( \
259 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20)
260#define _trans_cube_RBr fastcube( \
261 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16)
262#define _trans_cube_RBr_inverse fastcube( \
263 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16)
264#define _trans_cube_LUr fastcube( \
265 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2)
266#define _trans_cube_LUr_inverse fastcube( \
267 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23)
268#define _trans_cube_LFr fastcube( \
269 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17)
270#define _trans_cube_LFr_inverse fastcube( \
271 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18)
272#define _trans_cube_LDr fastcube( \
273 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0)
274#define _trans_cube_LDr_inverse fastcube( \
275 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22)
276#define _trans_cube_LBr fastcube( \
277 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19)
278#define _trans_cube_LBr_inverse fastcube( \
279 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19)
280#define _trans_cube_FUr fastcube( \
281 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6)
282#define _trans_cube_FUr_inverse fastcube( \
283 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6)
284#define _trans_cube_FRr fastcube( \
285 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21)
286#define _trans_cube_FRr_inverse fastcube( \
287 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3)
288#define _trans_cube_FDr fastcube( \
289 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4)
290#define _trans_cube_FDr_inverse fastcube( \
291 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7)
292#define _trans_cube_FLr fastcube( \
293 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23)
294#define _trans_cube_FLr_inverse fastcube( \
295 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2)
296#define _trans_cube_BUr fastcube( \
297 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7)
298#define _trans_cube_BUr_inverse fastcube( \
299 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4)
300#define _trans_cube_BRr fastcube( \
301 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22)
302#define _trans_cube_BRr_inverse fastcube( \
303 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0)
304#define _trans_cube_BDr fastcube( \
305 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5)
306#define _trans_cube_BDr_inverse fastcube( \
307 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5)
308#define _trans_cube_BLr fastcube( \
309 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20)
310#define _trans_cube_BLr_inverse fastcube( \
311 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1)
312#define _trans_cube_UFm fastcube( \
313 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10)
314#define _trans_cube_UFm_inverse fastcube( \
315 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10)
316#define _trans_cube_ULm fastcube( \
317 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25)
318#define _trans_cube_ULm_inverse fastcube( \
319 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25)
320#define _trans_cube_UBm fastcube( \
321 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8)
322#define _trans_cube_UBm_inverse fastcube( \
323 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8)
324#define _trans_cube_URm fastcube( \
325 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27)
326#define _trans_cube_URm_inverse fastcube( \
327 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27)
328#define _trans_cube_DFm fastcube( \
329 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11)
330#define _trans_cube_DFm_inverse fastcube( \
331 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11)
332#define _trans_cube_DLm fastcube( \
333 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26)
334#define _trans_cube_DLm_inverse fastcube( \
335 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24)
336#define _trans_cube_DBm fastcube( \
337 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9)
338#define _trans_cube_DBm_inverse fastcube( \
339 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9)
340#define _trans_cube_DRm fastcube( \
341 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24)
342#define _trans_cube_DRm_inverse fastcube( \
343 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26)
344#define _trans_cube_RUm fastcube( \
345 68, 71, 69, 70, 33, 34, 32, 35, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3)
346#define _trans_cube_RUm_inverse fastcube( \
347 70, 68, 69, 71, 32, 34, 35, 33, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22)
348#define _trans_cube_RFm fastcube( \
349 34, 33, 32, 35, 68, 71, 70, 69, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18)
350#define _trans_cube_RFm_inverse fastcube( \
351 66, 65, 64, 67, 36, 39, 38, 37, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18)
352#define _trans_cube_RDm fastcube( \
353 71, 68, 70, 69, 34, 33, 35, 32, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1)
354#define _trans_cube_RDm_inverse fastcube( \
355 71, 69, 68, 70, 33, 35, 34, 32, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23)
356#define _trans_cube_RBm fastcube( \
357 33, 34, 35, 32, 71, 68, 69, 70, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16)
358#define _trans_cube_RBm_inverse fastcube( \
359 67, 64, 65, 66, 37, 38, 39, 36, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19)
360#define _trans_cube_LUm fastcube( \
361 69, 70, 68, 71, 32, 35, 33, 34, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2)
362#define _trans_cube_LUm_inverse fastcube( \
363 68, 70, 71, 69, 34, 32, 33, 35, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20)
364#define _trans_cube_LFm fastcube( \
365 32, 35, 34, 33, 70, 69, 68, 71, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17)
366#define _trans_cube_LFm_inverse fastcube( \
367 64, 67, 66, 65, 38, 37, 36, 39, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17)
368#define _trans_cube_LDm fastcube( \
369 70, 69, 71, 68, 35, 32, 34, 33, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
370#define _trans_cube_LDm_inverse fastcube( \
371 69, 71, 70, 68, 35, 33, 32, 34, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21)
372#define _trans_cube_LBm fastcube( \
373 35, 32, 33, 34, 69, 70, 71, 68, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19)
374#define _trans_cube_LBm_inverse fastcube( \
375 65, 66, 67, 64, 39, 36, 37, 38, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16)
376#define _trans_cube_FUm fastcube( \
377 64, 66, 65, 67, 36, 38, 37, 39, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7)
378#define _trans_cube_FUm_inverse fastcube( \
379 32, 34, 33, 35, 68, 70, 69, 71, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7)
380#define _trans_cube_FRm fastcube( \
381 36, 38, 39, 37, 66, 64, 65, 67, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20)
382#define _trans_cube_FRm_inverse fastcube( \
383 37, 38, 36, 39, 64, 67, 65, 66, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2)
384#define _trans_cube_FDm fastcube( \
385 66, 64, 67, 65, 38, 36, 39, 37, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5)
386#define _trans_cube_FDm_inverse fastcube( \
387 33, 35, 32, 34, 69, 71, 68, 70, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6)
388#define _trans_cube_FLm fastcube( \
389 38, 36, 37, 39, 64, 66, 67, 65, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22)
390#define _trans_cube_FLm_inverse fastcube( \
391 36, 39, 37, 38, 65, 66, 64, 67, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3)
392#define _trans_cube_BUm fastcube( \
393 65, 67, 64, 66, 37, 39, 36, 38, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6)
394#define _trans_cube_BUm_inverse fastcube( \
395 34, 32, 35, 33, 70, 68, 71, 69, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5)
396#define _trans_cube_BRm fastcube( \
397 39, 37, 36, 38, 65, 67, 66, 64, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23)
398#define _trans_cube_BRm_inverse fastcube( \
399 39, 36, 38, 37, 66, 65, 67, 64, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1)
400#define _trans_cube_BDm fastcube( \
401 67, 65, 66, 64, 39, 37, 38, 36, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4)
402#define _trans_cube_BDm_inverse fastcube( \
403 35, 33, 34, 32, 71, 69, 70, 68, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4)
404#define _trans_cube_BLm fastcube( \
405 37, 39, 38, 36, 67, 65, 64, 66, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21)
406#define _trans_cube_BLm_inverse fastcube( \
407 38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
408
409_static const char *cornerstr[] = {
410 [_c_ufr] = "UFR",
411 [_c_ubl] = "UBL",
412 [_c_dfl] = "DFL",
413 [_c_dbr] = "DBR",
414 [_c_ufl] = "UFL",
415 [_c_ubr] = "UBR",
416 [_c_dfr] = "DFR",
417 [_c_dbl] = "DBL"
418};
419
420_static const char *cornerstralt[] = {
421 [_c_ufr] = "URF",
422 [_c_ubl] = "ULB",
423 [_c_dfl] = "DLF",
424 [_c_dbr] = "DRB",
425 [_c_ufl] = "ULF",
426 [_c_ubr] = "URB",
427 [_c_dfr] = "DRF",
428 [_c_dbl] = "DLB"
429};
430
431_static const char *edgestr[] = {
432 [_e_uf] = "UF",
433 [_e_ub] = "UB",
434 [_e_db] = "DB",
435 [_e_df] = "DF",
436 [_e_ur] = "UR",
437 [_e_ul] = "UL",
438 [_e_dl] = "DL",
439 [_e_dr] = "DR",
440 [_e_fr] = "FR",
441 [_e_fl] = "FL",
442 [_e_bl] = "BL",
443 [_e_br] = "BR"
444};
445
446_static const char *movestr[] = {
447 [_move_U] = "U",
448 [_move_U2] = "U2",
449 [_move_U3] = "U'",
450 [_move_D] = "D",
451 [_move_D2] = "D2",
452 [_move_D3] = "D'",
453 [_move_R] = "R",
454 [_move_R2] = "R2",
455 [_move_R3] = "R'",
456 [_move_L] = "L",
457 [_move_L2] = "L2",
458 [_move_L3] = "L'",
459 [_move_F] = "F",
460 [_move_F2] = "F2",
461 [_move_F3] = "F'",
462 [_move_B] = "B",
463 [_move_B2] = "B2",
464 [_move_B3] = "B'",
465};
466
467_static const char *transstr[] = {
468 [_trans_UFr] = "rotation UF",
469 [_trans_UFm] = "mirrored UF",
470 [_trans_ULr] = "rotation UL",
471 [_trans_ULm] = "mirrored UL",
472 [_trans_UBr] = "rotation UB",
473 [_trans_UBm] = "mirrored UB",
474 [_trans_URr] = "rotation UR",
475 [_trans_URm] = "mirrored UR",
476 [_trans_DFr] = "rotation DF",
477 [_trans_DFm] = "mirrored DF",
478 [_trans_DLr] = "rotation DL",
479 [_trans_DLm] = "mirrored DL",
480 [_trans_DBr] = "rotation DB",
481 [_trans_DBm] = "mirrored DB",
482 [_trans_DRr] = "rotation DR",
483 [_trans_DRm] = "mirrored DR",
484 [_trans_RUr] = "rotation RU",
485 [_trans_RUm] = "mirrored RU",
486 [_trans_RFr] = "rotation RF",
487 [_trans_RFm] = "mirrored RF",
488 [_trans_RDr] = "rotation RD",
489 [_trans_RDm] = "mirrored RD",
490 [_trans_RBr] = "rotation RB",
491 [_trans_RBm] = "mirrored RB",
492 [_trans_LUr] = "rotation LU",
493 [_trans_LUm] = "mirrored LU",
494 [_trans_LFr] = "rotation LF",
495 [_trans_LFm] = "mirrored LF",
496 [_trans_LDr] = "rotation LD",
497 [_trans_LDm] = "mirrored LD",
498 [_trans_LBr] = "rotation LB",
499 [_trans_LBm] = "mirrored LB",
500 [_trans_FUr] = "rotation FU",
501 [_trans_FUm] = "mirrored FU",
502 [_trans_FRr] = "rotation FR",
503 [_trans_FRm] = "mirrored FR",
504 [_trans_FDr] = "rotation FD",
505 [_trans_FDm] = "mirrored FD",
506 [_trans_FLr] = "rotation FL",
507 [_trans_FLm] = "mirrored FL",
508 [_trans_BUr] = "rotation BU",
509 [_trans_BUm] = "mirrored BU",
510 [_trans_BRr] = "rotation BR",
511 [_trans_BRm] = "mirrored BR",
512 [_trans_BDr] = "rotation BD",
513 [_trans_BDm] = "mirrored BD",
514 [_trans_BLr] = "rotation BL",
515 [_trans_BLm] = "mirrored BL",
516};
517
518static uint8_t inverse_trans_table[48] = {
519 [_trans_UFr] = _trans_UFr,
520 [_trans_UFm] = _trans_UFm,
521 [_trans_ULr] = _trans_URr,
522 [_trans_ULm] = _trans_ULm,
523 [_trans_UBr] = _trans_UBr,
524 [_trans_UBm] = _trans_UBm,
525 [_trans_URr] = _trans_ULr,
526 [_trans_URm] = _trans_URm,
527 [_trans_DFr] = _trans_DFr,
528 [_trans_DFm] = _trans_DFm,
529 [_trans_DLr] = _trans_DLr,
530 [_trans_DLm] = _trans_DRm,
531 [_trans_DBr] = _trans_DBr,
532 [_trans_DBm] = _trans_DBm,
533 [_trans_DRr] = _trans_DRr,
534 [_trans_DRm] = _trans_DLm,
535 [_trans_RUr] = _trans_FRr,
536 [_trans_RUm] = _trans_FLm,
537 [_trans_RFr] = _trans_LFr,
538 [_trans_RFm] = _trans_RFm,
539 [_trans_RDr] = _trans_BLr,
540 [_trans_RDm] = _trans_BRm,
541 [_trans_RBr] = _trans_RBr,
542 [_trans_RBm] = _trans_LBm,
543 [_trans_LUr] = _trans_FLr,
544 [_trans_LUm] = _trans_FRm,
545 [_trans_LFr] = _trans_RFr,
546 [_trans_LFm] = _trans_LFm,
547 [_trans_LDr] = _trans_BRr,
548 [_trans_LDm] = _trans_BLm,
549 [_trans_LBr] = _trans_LBr,
550 [_trans_LBm] = _trans_RBm,
551 [_trans_FUr] = _trans_FUr,
552 [_trans_FUm] = _trans_FUm,
553 [_trans_FRr] = _trans_RUr,
554 [_trans_FRm] = _trans_LUm,
555 [_trans_FDr] = _trans_BUr,
556 [_trans_FDm] = _trans_BUm,
557 [_trans_FLr] = _trans_LUr,
558 [_trans_FLm] = _trans_RUm,
559 [_trans_BUr] = _trans_FDr,
560 [_trans_BUm] = _trans_FDm,
561 [_trans_BRr] = _trans_LDr,
562 [_trans_BRm] = _trans_RDm,
563 [_trans_BDr] = _trans_BDr,
564 [_trans_BDm] = _trans_BDm,
565 [_trans_BLr] = _trans_RDr,
566 [_trans_BLm] = _trans_LDm,
567};
568
569/******************************************************************************
570Section: AVX2 fast methods
571
572This section contains performance-critical methods that rely on AVX2
573intructions such as routines for moving or transforming the cube.
574******************************************************************************/
575
576#if defined(CUBE_AVX2)
577
578#include <immintrin.h>
579
580typedef __m256i cube_fast_t;
581
582#define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060)
583#define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020)
584#define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707)
585#define _ep_avx2 _mm256_set_epi64x(0x0F0F0F0F, 0x0F0F0F0F0F0F0F0F, 0, 0)
586#define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0)
587
588_static_inline cube_fast_t fastcube(
589 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
590 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
591 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
592 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
593);
594_static cube_fast_t cubetofast(cube_t);
595_static cube_t fasttocube(cube_fast_t);
596_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
597_static_inline bool issolved_fast(cube_fast_t);
598_static_inline cube_fast_t invertco_fast(cube_fast_t);
599_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
600
601_static_inline int64_t coord_fast_co(cube_fast_t);
602_static_inline int64_t coord_fast_csep(cube_fast_t);
603_static_inline int64_t coord_fast_cocsep(cube_fast_t);
604_static_inline int64_t coord_fast_eo(cube_fast_t);
605_static_inline int64_t coord_fast_esep(cube_fast_t);
606
607_static_inline cube_fast_t
608fastcube(
609 uint8_t c_ufr,
610 uint8_t c_ubl,
611 uint8_t c_dfl,
612 uint8_t c_dbr,
613 uint8_t c_ufl,
614 uint8_t c_ubr,
615 uint8_t c_dfr,
616 uint8_t c_dbl,
617
618 uint8_t e_uf,
619 uint8_t e_ub,
620 uint8_t e_db,
621 uint8_t e_df,
622 uint8_t e_ur,
623 uint8_t e_ul,
624 uint8_t e_dl,
625 uint8_t e_dr,
626 uint8_t e_fr,
627 uint8_t e_fl,
628 uint8_t e_bl,
629 uint8_t e_br
630)
631{
632 return _mm256_set_epi8(
633 0, 0, 0, 0, e_br, e_bl, e_fl, e_fr,
634 e_dr, e_dl, e_ul, e_ur, e_df, e_db, e_ub, e_uf,
635 0, 0, 0, 0, 0, 0, 0, 0,
636 c_dbl, c_dfr, c_ubr, c_ufl, c_dbr, c_dfl, c_ubl, c_ufr
637 );
638}
639
640_static cube_fast_t
641cubetofast(cube_t a)
642{
643 uint8_t aux[32];
644
645 memset(aux, 0, 32);
646 memcpy(aux, &a.corner, 8);
647 memcpy(aux + 16, &a.edge, 12);
648
649 return _mm256_loadu_si256((__m256i_u *)&aux);
650}
651
652_static cube_t
653fasttocube(cube_fast_t c)
654{
655 cube_t a;
656 uint8_t aux[32];
657
658 _mm256_storeu_si256((__m256i_u *)aux, c);
659 memcpy(&a.corner, aux, 8);
660 memcpy(&a.edge, aux + 16, 12);
661
662 return a;
663}
664
665_static_inline bool
666equal_fast(cube_fast_t c1, cube_fast_t c2)
667{
668 int32_t mask;
669 __m256i cmp;
670
671 cmp = _mm256_cmpeq_epi8(c1, c2);
672 mask = _mm256_movemask_epi8(cmp);
673
674 return mask == ~0;
675}
676
677_static_inline bool
678issolved_fast(cube_fast_t cube)
679{
680 return equal_fast(cube, solved_fast);
681}
682
683_static_inline cube_fast_t
684invertco_fast(cube_fast_t c)
685{
686 cube_fast_t co, shleft, shright, summed, newco, cleanco, ret;
687
688 co = _mm256_and_si256(c, _co2_avx2);
689 shleft = _mm256_slli_epi32(co, 1);
690 shright = _mm256_srli_epi32(co, 1);
691 summed = _mm256_or_si256(shleft, shright);
692 newco = _mm256_and_si256(summed, _co2_avx2);
693 cleanco = _mm256_xor_si256(c, co);
694 ret = _mm256_or_si256(cleanco, newco);
695
696 return ret;
697}
698
699_static_inline cube_fast_t
700compose_fast(cube_fast_t c1, cube_fast_t c2)
701{
702 cube_fast_t s, b, eo2, co1, co2, aux, auy1, auy2, auz1, auz2;
703
704 /* Permute and clean unused bits */
705 s = _mm256_shuffle_epi8(c1, c2);
706 b = _mm256_set_epi8(
707 ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
708 ~0, ~0, ~0, ~0, ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0
709 );
710 s = _mm256_andnot_si256(b, s);
711
712 /* Change EO */
713 eo2 = _mm256_and_si256(c2, _eo_avx2);
714 s = _mm256_xor_si256(s, eo2);
715
716 /* Change CO */
717 co1 = _mm256_and_si256(s, _co2_avx2);
718 co2 = _mm256_and_si256(c2, _co2_avx2);
719 aux = _mm256_add_epi8(co1, co2);
720 auy1 = _mm256_add_epi8(aux, _cocw_avx2);
721 auy2 = _mm256_srli_epi32(auy1, 2);
722 auz1 = _mm256_add_epi8(aux, auy2);
723 auz2 = _mm256_and_si256(auz1, _co2_avx2);
724
725 /* Put together */
726 s = _mm256_andnot_si256(_co2_avx2, s);
727 s = _mm256_or_si256(s, auz2);
728
729 return s;
730}
731
732_static_inline int64_t
733coord_fast_co(cube_fast_t c)
734{
735 cube_fast_t co;
736 int64_t mem[4], ret, i, p;
737
738 co = _mm256_and_si256(c, _co2_avx2);
739 _mm256_storeu_si256((__m256i *)mem, co);
740
741 mem[0] >>= 5L;
742 for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8L, p *= 3)
743 ret += (mem[0] & 3L) * p;
744
745 return ret;
746}
747
748_static_inline int64_t
749coord_fast_csep(cube_fast_t c)
750{
751 cube_fast_t cp, shifted;
752 int64_t mask;
753
754 cp = _mm256_and_si256(c, _cp_avx2);
755 shifted = _mm256_slli_epi32(cp, 5);
756 mask = _mm256_movemask_epi8(shifted);
757
758 return mask & 0x7F;
759}
760
761_static_inline int64_t
762coord_fast_cocsep(cube_fast_t c)
763{
764 return (coord_fast_co(c) << 7) + coord_fast_csep(c);
765}
766
767_static_inline int64_t
768coord_fast_eo(cube_fast_t c)
769{
770 cube_fast_t eo, shifted;
771 int64_t mask;
772
773 eo = _mm256_and_si256(c, _eo_avx2);
774 shifted = _mm256_slli_epi32(eo, 3);
775 mask = _mm256_movemask_epi8(shifted);
776
777 return mask >> 17;
778}
779
780_static_inline int64_t
781coord_fast_esep(cube_fast_t c)
782{
783 cube_fast_t ep;
784 int64_t e, mem[4], i, j, k, l, ret1, ret2, bit1, bit2, is1;
785
786 ep = _mm256_and_si256(c, _ep_avx2);
787 _mm256_storeu_si256((__m256i *)mem, ep);
788
789 mem[3] <<= 8L;
790 ret1 = ret2 = 0;
791 k = l = 4;
792 for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8L) {
793 e = mem[i/8 + 2];
794
795 bit1 = (e & _esepbit1) >> 2L;
796 bit2 = (e & _esepbit2) >> 3L;
797 is1 = (1 - bit2) * bit1;
798
799 ret1 += bit2 * binomial[11-i][k];
800 k -= bit2;
801
802 ret2 += is1 * binomial[7-j][l];
803 l -= is1;
804 j += (1-bit2);
805 }
806
807 return ret1 * 70 + ret2;
808}
809
810/******************************************************************************
811Section: ARM NEON fast methods
812
813This section contains performance-critical methods that rely on ARM NEON
814intructions such as routines for moving or transforming the cube.
815******************************************************************************/
816
817#elif defined(CUBE_NEON)
818
819typedef struct {
820 uint8x16_t corner;
821 uint8x16_t edge;
822} cube_fast_t;
823
824/* TODO! */
825
826/******************************************************************************
827Section: portable fast methods
828
829This section contains performance-critical methods that do not use
830advanced CPU instructions. They are used as an alternative to the ones
831in the previous section(s) for unsupported architectures.
832******************************************************************************/
833
834#else
835
836typedef cube_t cube_fast_t;
837
838_static_inline cube_fast_t fastcube(
839 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
840 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
841 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
842 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
843);
844_static cube_fast_t cubetofast(cube_t);
845_static cube_t fasttocube(cube_fast_t);
846_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
847_static_inline bool issolved_fast(cube_fast_t);
848_static_inline cube_fast_t invertco_fast(cube_fast_t);
849_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
850
851_static_inline int64_t coord_fast_co(cube_fast_t);
852_static_inline int64_t coord_fast_csep(cube_fast_t);
853_static_inline int64_t coord_fast_cocsep(cube_fast_t);
854_static_inline int64_t coord_fast_eo(cube_fast_t);
855_static_inline int64_t coord_fast_esep(cube_fast_t);
856
857_static_inline cube_fast_t
858fastcube(
859 uint8_t c_ufr,
860 uint8_t c_ubl,
861 uint8_t c_dfl,
862 uint8_t c_dbr,
863 uint8_t c_ufl,
864 uint8_t c_ubr,
865 uint8_t c_dfr,
866 uint8_t c_dbl,
867
868 uint8_t e_uf,
869 uint8_t e_ub,
870 uint8_t e_db,
871 uint8_t e_df,
872 uint8_t e_ur,
873 uint8_t e_ul,
874 uint8_t e_dl,
875 uint8_t e_dr,
876 uint8_t e_fr,
877 uint8_t e_fl,
878 uint8_t e_bl,
879 uint8_t e_br
880)
881{
882 cube_fast_t cube = {
883 .corner = {
884 c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl
885 },
886 .edge = {
887 e_uf, e_ub, e_db, e_df, e_ur, e_ul,
888 e_dl, e_dr, e_fr, e_fl, e_bl, e_br
889 }
890 };
891
892 return cube;
893}
894
895_static cube_fast_t
896cubetofast(cube_t cube)
897{
898 cube_fast_t fast;
899 memcpy(&fast, &cube, sizeof(cube_fast_t));
900 return fast;
901}
902
903_static cube_t
904fasttocube(cube_fast_t fast)
905{
906 cube_t cube;
907 memcpy(&cube, &fast, sizeof(cube_fast_t));
908 return cube;
909}
910
911_static_inline bool
912equal_fast(cube_fast_t c1, cube_fast_t c2)
913{
914 uint8_t i;
915 bool ret;
916
917 ret = true;
918 for (i = 0; i < 8; i++)
919 ret = ret && c1.corner[i] == c2.corner[i];
920 for (i = 0; i < 12; i++)
921 ret = ret && c1.edge[i] == c2.edge[i];
922
923 return ret;
924}
925
926_static_inline bool
927issolved_fast(cube_fast_t cube)
928{
929 return equal_fast(cube, solved_fast);
930}
931
932_static_inline cube_fast_t
933invertco_fast(cube_fast_t c)
934{
935 uint8_t i, piece, orien;
936 cube_fast_t ret;
937
938 ret = c;
939 for (i = 0; i < 8; i++) {
940 piece = c.corner[i];
941 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
942 ret.corner[i] = (piece & _pbits) | orien;
943 }
944
945 return ret;
946}
947
948_static_inline cube_fast_t
949compose_fast(cube_fast_t c1, cube_fast_t c2)
950{
951 cube_fast_t ret;
952 uint8_t i, piece1, piece2, p, orien, aux, auy;
953
954 ret = zero_fast;
955
956 for (i = 0; i < 12; i++) {
957 piece2 = c2.edge[i];
958 p = piece2 & _pbits;
959 piece1 = c1.edge[p];
960 orien = (piece2 ^ piece1) & _eobit;
961 ret.edge[i] = (piece1 & _pbits) | orien;
962 }
963
964 for (i = 0; i < 8; i++) {
965 piece2 = c2.corner[i];
966 p = piece2 & _pbits;
967 piece1 = c1.corner[p];
968 aux = (piece2 & _cobits) + (piece1 & _cobits);
969 auy = (aux + _ctwist_cw) >> 2U;
970 orien = (aux + auy) & _cobits2;
971 ret.corner[i] = (piece1 & _pbits) | orien;
972 }
973
974 return ret;
975}
976
977_static_inline int64_t
978coord_fast_co(cube_fast_t c)
979{
980 int i, p;
981 int64_t ret;
982
983 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3)
984 ret += p * (c.corner[i] >> _coshift);
985
986 return ret;
987}
988
989/*
990For corner separation, we consider the axis (a.k.a. tetrad) each
991corner belongs to as 0 or 1 and we translate this sequence into binary.
992Ignoring the last bit, we have a value up to 2^7, but not all values are
993possible. Encoding this as a number from 0 to C(8,4) would save about 40%
994of space, but we are not going to use this coordinate in large tables.
995*/
996_static_inline int64_t
997coord_fast_csep(cube_fast_t c)
998{
999 int i, p;
1000 int64_t ret;
1001
1002 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2)
1003 ret += p * ((c.corner[i] & _csepbit) >> 2U);
1004
1005 return ret;
1006}
1007
1008_static_inline int64_t
1009coord_fast_cocsep(cube_fast_t c)
1010{
1011 return (coord_fast_co(c) << 7) + coord_fast_csep(c);
1012}
1013
1014_static_inline int64_t
1015coord_fast_eo(cube_fast_t c)
1016{
1017 int i, p;
1018 int64_t ret;
1019
1020 for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2)
1021 ret += p * (c.edge[i] >> _eoshift);
1022
1023 return ret;
1024}
1025
1026/*
1027We encode the edge separation as a number from 0 to C(12,4)*C(8,4).
1028It can be seen as the composition of two "subset index" coordinates.
1029*/
1030_static_inline int64_t
1031coord_fast_esep(cube_fast_t c)
1032{
1033 int64_t i, j, k, l, ret1, ret2, bit1, bit2, is1;
1034
1035 for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) {
1036 /* Simple version:
1037 if (c.edge[i] & _esepbit2) {
1038 ret1 += binomial[11-i][k--];
1039 } else {
1040 if (c.edge[i] & _esepbit1)
1041 ret2 += binomial[7-j][l--];
1042 j++;
1043 }
1044 */
1045
1046 bit1 = (c.edge[i] & _esepbit1) >> 2U;
1047 bit2 = (c.edge[i] & _esepbit2) >> 3U;
1048 is1 = (1 - bit2) * bit1;
1049
1050 ret1 += bit2 * binomial[11-i][k];
1051 k -= bit2;
1052
1053 ret2 += is1 * binomial[7-j][l];
1054 l -= is1;
1055 j += (1-bit2);
1056 }
1057
1058 return ret1 * 70 + ret2;
1059}
1060
1061#endif
1062
1063/******************************************************************************
1064Section: generic methods
1065
1066This section contains generic functionality, including the public functions.
1067Some of these routines depend on the efficient functions implemented in the
1068previous sections, while some other operate directly on the cube.
1069******************************************************************************/
1070
1071#define _move(M, c) compose_fast(c, _move_cube_ ## M)
1072#define _premove(M, c) compose_fast(_move_cube_ ## M, c)
1073#define _trans_rotation(T, c) \
1074 compose_fast(compose_fast(_trans_cube_ ## T, c), \
1075 _trans_cube_ ## T ## _inverse)
1076#define _trans_mirrored(T, c) \
1077 invertco_fast(compose_fast(compose_fast(_trans_cube_ ## T, c), \
1078 _trans_cube_ ## T ## _inverse))
1079
1080_static int permsign(uint8_t *, int);
1081_static uint8_t readco(const char *);
1082_static uint8_t readcp(const char *);
1083_static uint8_t readeo(const char *);
1084_static uint8_t readep(const char *);
1085_static cube_t readcube_H48(const char *);
1086_static uint8_t readpiece_LST(const char **);
1087_static cube_t readcube_LST(const char *);
1088_static int writepiece_LST(uint8_t, char *);
1089_static void writecube_H48(cube_t, char *);
1090_static void writecube_LST(cube_t, char *);
1091_static uint8_t readmove(char);
1092_static uint8_t readmodifier(char);
1093_static uint8_t readtrans(const char *);
1094_static int writemoves(uint8_t *, int, char *);
1095_static void writetrans(uint8_t, char *);
1096_static cube_fast_t move(cube_fast_t, uint8_t);
1097_static cube_fast_t transform(cube_fast_t, uint8_t);
1098
1099_static_inline int64_t coord_h48(cube_fast_t, uint32_t *, uint8_t);
1100
1101cube_t
1102solvedcube(void)
1103{
1104 return solved;
1105}
1106
1107bool
1108isconsistent(cube_t cube)
1109{
1110 uint8_t i, p, e, piece;
1111 bool found[12];
1112
1113 for (i = 0; i < 12; i++)
1114 found[i] = false;
1115 for (i = 0; i < 12; i++) {
1116 piece = cube.edge[i];
1117 p = piece & _pbits;
1118 e = piece & _eobit;
1119 if (p >= 12)
1120 goto inconsistent_ep;
1121 if (e != 0 && e != _eobit)
1122 goto inconsistent_eo;
1123 found[p] = true;
1124 }
1125 for (i = 0; i < 12; i++)
1126 if (!found[i])
1127 goto inconsistent_ep;
1128
1129 for (i = 0; i < 8; i++)
1130 found[i] = false;
1131 for (i = 0; i < 8; i++) {
1132 piece = cube.corner[i];
1133 p = piece & _pbits;
1134 e = piece & _cobits;
1135 if (p >= 8)
1136 goto inconsistent_cp;
1137 if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw)
1138 goto inconsistent_co;
1139 found[p] = true;
1140 }
1141 for (i = 0; i < 8; i++)
1142 if (!found[i])
1143 goto inconsistent_co;
1144
1145 return true;
1146
1147inconsistent_ep:
1148 DBG_LOG("Inconsistent EP\n");
1149 return false;
1150inconsistent_cp:
1151 DBG_LOG("Inconsistent CP\n");
1152 return false;
1153inconsistent_eo:
1154 DBG_LOG("Inconsistent EO\n");
1155 return false;
1156inconsistent_co:
1157 DBG_LOG("Inconsistent CO\n");
1158 return false;
1159}
1160
1161bool
1162issolvable(cube_t cube)
1163{
1164 uint8_t i, eo, co, piece, edges[12], corners[8];
1165
1166 DBG_ASSERT(isconsistent(cube), false,
1167 "issolvable: cube is inconsistent\n");
1168
1169 for (i = 0; i < 12; i++)
1170 edges[i] = cube.edge[i] & _pbits;
1171 for (i = 0; i < 8; i++)
1172 corners[i] = cube.corner[i] & _pbits;
1173
1174 if (permsign(edges, 12) != permsign(corners, 8))
1175 goto issolvable_parity;
1176
1177 eo = 0;
1178 for (i = 0; i < 12; i++) {
1179 piece = cube.edge[i];
1180 eo += (piece & _eobit) >> _eoshift;
1181 }
1182 if (eo % 2 != 0)
1183 goto issolvable_eo;
1184
1185 co = 0;
1186 for (i = 0; i < 8; i++) {
1187 piece = cube.corner[i];
1188 co += (piece & _cobits) >> _coshift;
1189 }
1190 if (co % 3 != 0)
1191 goto issolvable_co;
1192
1193 return true;
1194
1195issolvable_parity:
1196 DBG_LOG("EP and CP parities are different\n");
1197 return false;
1198issolvable_eo:
1199 DBG_LOG("Odd number of flipped edges\n");
1200 return false;
1201issolvable_co:
1202 DBG_LOG("Sum of corner orientation is not multiple of 3\n");
1203 return false;
1204}
1205
1206bool
1207issolved(cube_t cube)
1208{
1209 return equal(cube, solved);
1210}
1211
1212bool
1213equal(cube_t c1, cube_t c2)
1214{
1215 int i;
1216 bool ret;
1217
1218 ret = true;
1219 for (i = 0; i < 8; i++)
1220 ret = ret && c1.corner[i] == c2.corner[i];
1221 for (i = 0; i < 12; i++)
1222 ret = ret && c1.edge[i] == c2.edge[i];
1223
1224 return ret;
1225}
1226
1227bool
1228iserror(cube_t cube)
1229{
1230 return equal(cube, zero);
1231}
1232
1233cube_t
1234compose(cube_t c1, cube_t c2)
1235{
1236 DBG_ASSERT(isconsistent(c1) && isconsistent(c2),
1237 zero, "compose error: inconsistent cube\n")
1238
1239 return fasttocube(compose_fast(cubetofast(c1), cubetofast(c2)));
1240}
1241
1242cube_t
1243inverse(cube_t cube)
1244{
1245 cube_t ret;
1246 uint8_t i, piece, orien;
1247
1248 DBG_ASSERT(isconsistent(cube), zero,
1249 "inverse error: inconsistent cube\n");
1250
1251 ret = zero;
1252
1253 for (i = 0; i < 12; i++) {
1254 piece = cube.edge[i];
1255 orien = piece & _eobit;
1256 ret.edge[piece & _pbits] = i | orien;
1257 }
1258
1259 for (i = 0; i < 8; i++) {
1260 piece = cube.corner[i];
1261 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
1262 ret.corner[piece & _pbits] = i | orien;
1263 }
1264
1265 return ret;
1266}
1267
1268cube_t
1269applymoves(cube_t cube, const char *buf)
1270{
1271 cube_fast_t fast;
1272 uint8_t r, m;
1273 const char *b;
1274
1275 DBG_ASSERT(isconsistent(cube), zero,
1276 "move error: inconsistent cube\n");
1277
1278 fast = cubetofast(cube);
1279
1280 for (b = buf; *b != '\0'; b++) {
1281 while (*b == ' ' || *b == '\t' || *b == '\n')
1282 b++;
1283 if (*b == '\0')
1284 goto applymoves_finish;
1285 if ((r = readmove(*b)) == _error)
1286 goto applymoves_error;
1287 if ((m = readmodifier(*(b+1))) != 0)
1288 b++;
1289 fast = move(fast, r + m);
1290 }
1291
1292applymoves_finish:
1293 return fasttocube(fast);
1294
1295applymoves_error:
1296 DBG_LOG("applymoves error\n");
1297 return zero;
1298}
1299
1300cube_t
1301applytrans(cube_t cube, const char *buf)
1302{
1303 cube_fast_t fast;
1304 uint8_t t;
1305
1306 DBG_ASSERT(isconsistent(cube), zero,
1307 "transformation error: inconsistent cube\n");
1308
1309 t = readtrans(buf);
1310 fast = cubetofast(cube);
1311 fast = transform(fast, t);
1312
1313 return fasttocube(fast);
1314}
1315
1316cube_t
1317readcube(const char *format, const char *buf)
1318{
1319 cube_t cube;
1320
1321 if (!strcmp(format, "H48")) {
1322 cube = readcube_H48(buf);
1323 } else if (!strcmp(format, "LST")) {
1324 cube = readcube_LST(buf);
1325 } else {
1326 DBG_LOG("Cannot read cube in the given format\n");
1327 cube = zero;
1328 }
1329
1330 return cube;
1331}
1332
1333void
1334writecube(const char *format, cube_t cube, char *buf)
1335{
1336 char *errormsg;
1337 size_t len;
1338
1339 if (!isconsistent(cube)) {
1340 errormsg = "ERROR: cannot write inconsistent cube";
1341 goto writecube_error;
1342 }
1343
1344 if (!strcmp(format, "H48")) {
1345 writecube_H48(cube, buf);
1346 } else if (!strcmp(format, "LST")) {
1347 writecube_LST(cube, buf);
1348 } else {
1349 errormsg = "ERROR: cannot write cube in the given format";
1350 goto writecube_error;
1351 }
1352
1353 return;
1354
1355writecube_error:
1356 DBG_LOG("writecube error, see stdout for details\n");
1357 len = strlen(errormsg);
1358 memcpy(buf, errormsg, len);
1359 buf[len] = '\n';
1360 buf[len+1] = '\0';
1361}
1362
1363_static int
1364permsign(uint8_t *a, int n)
1365{
1366 int i, j;
1367 uint8_t ret = 0;
1368
1369 for (i = 0; i < n; i++)
1370 for (j = i+1; j < n; j++)
1371 ret += a[i] > a[j] ? 1 : 0;
1372
1373 return ret % 2;
1374}
1375
1376_static uint8_t
1377readco(const char *str)
1378{
1379 if (*str == '0')
1380 return 0;
1381 if (*str == '1')
1382 return _ctwist_cw;
1383 if (*str == '2')
1384 return _ctwist_ccw;
1385
1386 DBG_LOG("Error reading CO\n");
1387 return _error;
1388}
1389
1390_static uint8_t
1391readcp(const char *str)
1392{
1393 uint8_t c;
1394
1395 for (c = 0; c < 8; c++)
1396 if (!strncmp(str, cornerstr[c], 3) ||
1397 !strncmp(str, cornerstralt[c], 3))
1398 return c;
1399
1400 DBG_LOG("Error reading CP\n");
1401 return _error;
1402}
1403
1404_static uint8_t
1405readeo(const char *str)
1406{
1407 if (*str == '0')
1408 return 0;
1409 if (*str == '1')
1410 return _eflip;
1411
1412 DBG_LOG("Error reading EO\n");
1413 return _error;
1414}
1415
1416_static uint8_t
1417readep(const char *str)
1418{
1419 uint8_t e;
1420
1421 for (e = 0; e < 12; e++)
1422 if (!strncmp(str, edgestr[e], 2))
1423 return e;
1424
1425 DBG_LOG("Error reading EP\n");
1426 return _error;
1427}
1428
1429_static cube_t
1430readcube_H48(const char *buf)
1431{
1432 int i;
1433 uint8_t piece, orient;
1434 cube_t ret = {0};
1435 const char *b;
1436
1437 b = buf;
1438
1439 for (i = 0; i < 12; i++) {
1440 while (*b == ' ' || *b == '\t' || *b == '\n')
1441 b++;
1442 if ((piece = readep(b)) == _error)
1443 return zero;
1444 b += 2;
1445 if ((orient = readeo(b)) == _error)
1446 return zero;
1447 b++;
1448 ret.edge[i] = piece | orient;
1449 }
1450 for (i = 0; i < 8; i++) {
1451 while (*b == ' ' || *b == '\t' || *b == '\n')
1452 b++;
1453 if ((piece = readcp(b)) == _error)
1454 return zero;
1455 b += 3;
1456 if ((orient = readco(b)) == _error)
1457 return zero;
1458 b++;
1459 ret.corner[i] = piece | orient;
1460 }
1461
1462 return ret;
1463}
1464
1465_static uint8_t
1466readpiece_LST(const char **b)
1467{
1468 uint8_t ret;
1469 bool read;
1470
1471 while (**b == ',' || **b == ' ' || **b == '\t' || **b == '\n')
1472 (*b)++;
1473
1474 for (ret = 0, read = false; **b >= '0' && **b <= '9'; (*b)++) {
1475 read = true;
1476 ret = ret * 10 + (**b) - '0';
1477 }
1478
1479 return read ? ret : _error;
1480}
1481
1482_static cube_t
1483readcube_LST(const char *buf)
1484{
1485 int i;
1486 cube_t ret = {0};
1487
1488 for (i = 0; i < 8; i++)
1489 ret.corner[i] = readpiece_LST(&buf);
1490
1491 for (i = 0; i < 12; i++)
1492 ret.edge[i] = readpiece_LST(&buf);
1493
1494 return ret;
1495}
1496
1497_static int
1498writepiece_LST(uint8_t piece, char *buf)
1499{
1500 char digits[3];
1501 int i, len = 0;
1502
1503 while (piece != 0) {
1504 digits[len++] = (piece % 10) + '0';
1505 piece /= 10;
1506 }
1507
1508 if (len == 0)
1509 digits[len++] = '0';
1510
1511 for (i = 0; i < len; i++)
1512 buf[i] = digits[len-i-1];
1513
1514 buf[len] = ',';
1515 buf[len+1] = ' ';
1516
1517 return len+2;
1518}
1519
1520_static void
1521writecube_H48(cube_t cube, char *buf)
1522{
1523 uint8_t piece, perm, orient;
1524 int i;
1525
1526 for (i = 0; i < 12; i++) {
1527 piece = cube.edge[i];
1528 perm = piece & _pbits;
1529 orient = (piece & _eobit) >> _eoshift;
1530 buf[4*i ] = edgestr[perm][0];
1531 buf[4*i + 1] = edgestr[perm][1];
1532 buf[4*i + 2] = orient + '0';
1533 buf[4*i + 3] = ' ';
1534 }
1535 for (i = 0; i < 8; i++) {
1536 piece = cube.corner[i];
1537 perm = piece & _pbits;
1538 orient = (piece & _cobits) >> _coshift;
1539 buf[48 + 5*i ] = cornerstr[perm][0];
1540 buf[48 + 5*i + 1] = cornerstr[perm][1];
1541 buf[48 + 5*i + 2] = cornerstr[perm][2];
1542 buf[48 + 5*i + 3] = orient + '0';
1543 buf[48 + 5*i + 4] = ' ';
1544 }
1545
1546 buf[48+39] = '\0';
1547}
1548
1549_static void
1550writecube_LST(cube_t cube, char *buf)
1551{
1552 int i, ptr;
1553 uint8_t piece;
1554
1555 ptr = 0;
1556
1557 for (i = 0; i < 8; i++) {
1558 piece = cube.corner[i];
1559 ptr += writepiece_LST(piece, buf + ptr);
1560 }
1561
1562 for (i = 0; i < 12; i++) {
1563 piece = cube.edge[i];
1564 ptr += writepiece_LST(piece, buf + ptr);
1565 }
1566
1567 *(buf+ptr-2) = 0;
1568}
1569
1570_static uint8_t
1571readmove(char c)
1572{
1573 switch (c) {
1574 case 'U':
1575 return _move_U;
1576 case 'D':
1577 return _move_D;
1578 case 'R':
1579 return _move_R;
1580 case 'L':
1581 return _move_L;
1582 case 'F':
1583 return _move_F;
1584 case 'B':
1585 return _move_B;
1586 default:
1587 return _error;
1588 }
1589}
1590
1591_static uint8_t
1592readmodifier(char c)
1593{
1594 switch (c) {
1595 case '1': /* Fallthrough */
1596 case '2': /* Fallthrough */
1597 case '3':
1598 return c - '0' - 1;
1599 case '\'':
1600 return 2;
1601 default:
1602 return 0;
1603 }
1604}
1605
1606_static uint8_t
1607readtrans(const char *buf)
1608{
1609 uint8_t t;
1610
1611 for (t = 0; t < 48; t++)
1612 if (!strncmp(buf, transstr[t], 11))
1613 return t;
1614
1615 DBG_LOG("readtrans error\n");
1616 return _error;
1617}
1618
1619_static int
1620writemoves(uint8_t *m, int n, char *buf)
1621{
1622 int i;
1623 size_t len;
1624 const char *s;
1625 char *b;
1626
1627 for (i = 0, b = buf; i < n; i++, b++) {
1628 s = movestr[m[i]];
1629 len = strlen(s);
1630 memcpy(b, s, len);
1631 b += len;
1632 *b = ' ';
1633 }
1634
1635 if (b != buf)
1636 b--; /* Remove last space */
1637 *b = '\0';
1638
1639 return b - buf;
1640}
1641
1642_static void
1643writetrans(uint8_t t, char *buf)
1644{
1645 if (t >= 48)
1646 memcpy(buf, "error trans", 11);
1647 else
1648 memcpy(buf, transstr[t], 11);
1649 buf[11] = '\0';
1650}
1651
1652_static cube_fast_t
1653move(cube_fast_t c, uint8_t m)
1654{
1655 switch (m) {
1656 case _move_U:
1657 return _move(U, c);
1658 case _move_U2:
1659 return _move(U2, c);
1660 case _move_U3:
1661 return _move(U3, c);
1662 case _move_D:
1663 return _move(D, c);
1664 case _move_D2:
1665 return _move(D2, c);
1666 case _move_D3:
1667 return _move(D3, c);
1668 case _move_R:
1669 return _move(R, c);
1670 case _move_R2:
1671 return _move(R2, c);
1672 case _move_R3:
1673 return _move(R3, c);
1674 case _move_L:
1675 return _move(L, c);
1676 case _move_L2:
1677 return _move(L2, c);
1678 case _move_L3:
1679 return _move(L3, c);
1680 case _move_F:
1681 return _move(F, c);
1682 case _move_F2:
1683 return _move(F2, c);
1684 case _move_F3:
1685 return _move(F3, c);
1686 case _move_B:
1687 return _move(B, c);
1688 case _move_B2:
1689 return _move(B2, c);
1690 case _move_B3:
1691 return _move(B3, c);
1692 default:
1693 DBG_LOG("move error, unknown move\n");
1694 return zero_fast;
1695 }
1696}
1697
1698_static cube_fast_t
1699transform(cube_fast_t c, uint8_t t)
1700{
1701 switch (t) {
1702 case _trans_UFr:
1703 return _trans_rotation(UFr, c);
1704 case _trans_ULr:
1705 return _trans_rotation(ULr, c);
1706 case _trans_UBr:
1707 return _trans_rotation(UBr, c);
1708 case _trans_URr:
1709 return _trans_rotation(URr, c);
1710 case _trans_DFr:
1711 return _trans_rotation(DFr, c);
1712 case _trans_DLr:
1713 return _trans_rotation(DLr, c);
1714 case _trans_DBr:
1715 return _trans_rotation(DBr, c);
1716 case _trans_DRr:
1717 return _trans_rotation(DRr, c);
1718 case _trans_RUr:
1719 return _trans_rotation(RUr, c);
1720 case _trans_RFr:
1721 return _trans_rotation(RFr, c);
1722 case _trans_RDr:
1723 return _trans_rotation(RDr, c);
1724 case _trans_RBr:
1725 return _trans_rotation(RBr, c);
1726 case _trans_LUr:
1727 return _trans_rotation(LUr, c);
1728 case _trans_LFr:
1729 return _trans_rotation(LFr, c);
1730 case _trans_LDr:
1731 return _trans_rotation(LDr, c);
1732 case _trans_LBr:
1733 return _trans_rotation(LBr, c);
1734 case _trans_FUr:
1735 return _trans_rotation(FUr, c);
1736 case _trans_FRr:
1737 return _trans_rotation(FRr, c);
1738 case _trans_FDr:
1739 return _trans_rotation(FDr, c);
1740 case _trans_FLr:
1741 return _trans_rotation(FLr, c);
1742 case _trans_BUr:
1743 return _trans_rotation(BUr, c);
1744 case _trans_BRr:
1745 return _trans_rotation(BRr, c);
1746 case _trans_BDr:
1747 return _trans_rotation(BDr, c);
1748 case _trans_BLr:
1749 return _trans_rotation(BLr, c);
1750 case _trans_UFm:
1751 return _trans_mirrored(UFm, c);
1752 case _trans_ULm:
1753 return _trans_mirrored(ULm, c);
1754 case _trans_UBm:
1755 return _trans_mirrored(UBm, c);
1756 case _trans_URm:
1757 return _trans_mirrored(URm, c);
1758 case _trans_DFm:
1759 return _trans_mirrored(DFm, c);
1760 case _trans_DLm:
1761 return _trans_mirrored(DLm, c);
1762 case _trans_DBm:
1763 return _trans_mirrored(DBm, c);
1764 case _trans_DRm:
1765 return _trans_mirrored(DRm, c);
1766 case _trans_RUm:
1767 return _trans_mirrored(RUm, c);
1768 case _trans_RFm:
1769 return _trans_mirrored(RFm, c);
1770 case _trans_RDm:
1771 return _trans_mirrored(RDm, c);
1772 case _trans_RBm:
1773 return _trans_mirrored(RBm, c);
1774 case _trans_LUm:
1775 return _trans_mirrored(LUm, c);
1776 case _trans_LFm:
1777 return _trans_mirrored(LFm, c);
1778 case _trans_LDm:
1779 return _trans_mirrored(LDm, c);
1780 case _trans_LBm:
1781 return _trans_mirrored(LBm, c);
1782 case _trans_FUm:
1783 return _trans_mirrored(FUm, c);
1784 case _trans_FRm:
1785 return _trans_mirrored(FRm, c);
1786 case _trans_FDm:
1787 return _trans_mirrored(FDm, c);
1788 case _trans_FLm:
1789 return _trans_mirrored(FLm, c);
1790 case _trans_BUm:
1791 return _trans_mirrored(BUm, c);
1792 case _trans_BRm:
1793 return _trans_mirrored(BRm, c);
1794 case _trans_BDm:
1795 return _trans_mirrored(BDm, c);
1796 case _trans_BLm:
1797 return _trans_mirrored(BLm, c);
1798 default:
1799 DBG_LOG("transform error, unknown transformation\n");
1800 return zero_fast;
1801 }
1802}
1803
1804/* h is the number of eo bits used */
1805_static_inline int64_t
1806coord_h48(cube_fast_t c, uint32_t *cocsepdata, uint8_t h)
1807{
1808 cube_fast_t d;
1809 int64_t cocsep, coclass, esep, eo, esize, ret;
1810 uint32_t data;
1811 uint8_t ttrep;
1812
1813 DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n");
1814
1815 cocsep = coord_fast_cocsep(c);
1816 data = cocsepdata[cocsep];
1817 coclass = (data & (0xFFFFU << 16U)) >> 16U;
1818 ttrep = (data & (0xFFU << 8U)) >> 8U;
1819
1820 d = transform(c, ttrep); /* TODO: transform only edges */
1821 esep = coord_fast_esep(d);
1822 eo = coord_fast_eo(d);
1823
1824 esize = (_12c4 * _8c4) << h;
1825 ret = (coclass * esize) + (esep << h) + (eo >> (11-h));
1826
1827 return ret;
1828}
1829
1830/******************************************************************************
1831Section: moves, move sequences and transformations
1832
1833This section contains methods to work with moves and arrays of moves. They
1834do not rely on the cube structure.
1835******************************************************************************/
1836
1837_static_inline bool allowednextmove(uint8_t *, uint8_t);
1838_static_inline uint8_t inverse_trans(uint8_t);
1839_static_inline uint8_t movebase(uint8_t);
1840_static_inline uint8_t moveaxis(uint8_t);
1841
1842_static bool
1843allowednextmove(uint8_t *moves, uint8_t n)
1844{
1845 uint8_t base[3], axis[3];
1846
1847 if (n < 2)
1848 return true;
1849
1850 base[0] = movebase(moves[n-1]);
1851 axis[0] = moveaxis(moves[n-1]);
1852 base[1] = movebase(moves[n-2]);
1853 axis[1] = moveaxis(moves[n-2]);
1854
1855 if (base[0] == base[1] || (axis[0] == axis[1] && base[0] < base[1]))
1856 return false;
1857
1858 if (n == 2)
1859 return true;
1860
1861 base[2] = movebase(moves[n-3]);
1862 axis[2] = moveaxis(moves[n-3]);
1863
1864 return axis[1] != axis[2] || base[0] != base[2];
1865}
1866
1867_static_inline uint8_t
1868inverse_trans(uint8_t t)
1869{
1870 return inverse_trans_table[t];
1871}
1872
1873_static_inline uint8_t
1874movebase(uint8_t move)
1875{
1876 return move / 3;
1877}
1878
1879_static_inline uint8_t
1880moveaxis(uint8_t move)
1881{
1882 return move / 6;
1883}
1884
1885/******************************************************************************
1886Section: auxiliary procedures for H48 optimal solver (temporary)
1887******************************************************************************/
1888
1889#define _esep_ind(i) (i / 8U)
1890#define _esep_shift(i) (4U * (i % 8U))
1891#define _esep_mask(i) (((1U << 4U) - 1U) << _esep_shift(i))
1892#define _visited_ind(i) (i / 8U)
1893#define _visited_mask(i) (1U << (i % 8U))
1894
1895typedef struct {
1896 cube_fast_t cube;
1897 uint8_t *visited;
1898 uint8_t *moves;
1899 uint8_t nmoves;
1900 uint8_t depth;
1901 uint16_t *nclasses;
1902 uint32_t *cocsepdata;
1903 uint32_t *buf32;
1904} dfsarg_gendata_t;
1905
1906_static size_t gendata_cocsep(void *);
1907_static uint32_t gendata_cocsep_dfs( /* TODO: use dfsarg */
1908 cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *, uint8_t *);
1909
1910_static size_t gendata_esep(const void *, void *);
1911_static uint32_t gendata_esep_dfs(dfsarg_gendata_t *);
1912
1913_static_inline bool get_visited(const uint8_t *, int64_t);
1914_static_inline void set_visited(uint8_t *, int64_t);
1915_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
1916_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
1917
1918/*
1919Each element of the cocsep table is a uint32_t used as follows:
1920 - Lowest 8-bit block: pruning value
1921 - Second-lower 8-bit block: "ttrep" (transformation to representative)
1922 - Top 16-bit block: symcoord value
1923After the data as described above, more auxiliary information is appended:
1924 - A uint32_t representing the number of symmetry classes
1925 - A uint32_t representing the highest value of the pruning table
1926 - One uint32_t for each "line" of the pruning table, representing the number
1927 of positions having that pruning value.
1928*/
1929_static size_t
1930gendata_cocsep(void *buf)
1931{
1932 size_t tablesize = _3p7 << 7U;
1933 size_t visitedsize = (tablesize + 7U) / 8U;
1934 size_t infosize = 12;
1935
1936 cube_fast_t solved;
1937 uint32_t *buf32, *info, cc;
1938 uint16_t n;
1939 uint8_t i, j, visited[visitedsize];
1940
1941 buf32 = (uint32_t *)buf;
1942 info = buf32 + tablesize;
1943 memset(buf32, 0xFFU, 4*tablesize);
1944 memset(info, 0, 4*infosize);
1945
1946 solved = cubetofast(solvedcube());
1947 for (i = 0, n = 0, cc = 0; i < 10; i++) {
1948 memset(visited, 0, visitedsize);
1949 DBG_LOG("cocsep: generating depth %" PRIu8 "\n", i);
1950 cc = gendata_cocsep_dfs(solved, 0, i, &n, buf32, visited);
1951 info[i+2] = cc;
1952 DBG_LOG("found %" PRIu32 "\n", cc);
1953 }
1954
1955 info[0] = (uint32_t)n;
1956 info[1] = 9U; /* Known max pruning value */
1957 DBG_ASSERT(n == COCSEP_CLASSES, 0,
1958 "cocsep: computed %" PRIu16 " symmetry classes, "
1959 "expected %" PRIu16 "\n", n, COCSEP_CLASSES);
1960
1961 DBG_LOG("cocsep data computed\n");
1962 DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]);
1963 DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[1]);
1964 DBG_LOG("Pruning value distribution:\n");
1965 for (j = 0; j < 10; j++)
1966 DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+2]);
1967
1968 return 4*(tablesize + infosize);
1969}
1970
1971_static uint32_t
1972gendata_cocsep_dfs(
1973 cube_fast_t c,
1974 uint8_t depth,
1975 uint8_t maxdepth,
1976 uint16_t *n,
1977 uint32_t *buf32,
1978 uint8_t *visited
1979)
1980{
1981 uint8_t m, t, tinv, olddepth;
1982 uint32_t cc;
1983 int64_t i;
1984 cube_fast_t d;
1985
1986 i = coord_fast_cocsep(c);
1987 olddepth = (uint8_t)(buf32[i] & 0xFFU);
1988 if (olddepth < depth || get_visited(visited, i))
1989 return 0;
1990 set_visited(visited, i);
1991
1992 if (depth == maxdepth) {
1993 if ((buf32[i] & 0xFFU) != 0xFFU)
1994 return 0;
1995
1996 for (t = 0, cc = 0; t < 48; t++) {
1997 d = transform(c, t);
1998 i = coord_fast_cocsep(d);
1999 set_visited(visited, i);
2000 tinv = inverse_trans(t);
2001 cc += (buf32[i] & 0xFFU) == 0xFFU;
2002 buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
2003 }
2004 (*n)++;
2005
2006 return cc;
2007 }
2008
2009 for (m = 0, cc = 0; m < 18; m++) {
2010 d = move(c, m);
2011 cc += gendata_cocsep_dfs(d, depth+1, maxdepth, n, buf32, visited);
2012 }
2013
2014 return cc;
2015}
2016
2017/*
2018TODO description
2019generating fixed table with h=0, k=4
2020*/
2021_static size_t
2022gendata_esep(const void *cocsepdata, void *buf)
2023{
2024 size_t tablesize = (COCSEP_CLASSES * _12c4 * _8c4) / 2U;
2025 size_t visitedsize = (tablesize * 2U + 7U) / 8U;
2026 size_t infosize = 25; /* TODO unknown yet */
2027
2028 uint32_t *buf32, *info, cc;
2029 uint8_t moves[20];
2030 dfsarg_gendata_t arg;
2031
2032 arg.visited = malloc(visitedsize);
2033 buf32 = (uint32_t *)buf;
2034 info = buf32 + tablesize;
2035 memset(buf32, 0xFFU, 4*tablesize);
2036 memset(info, 0, 4*infosize);
2037
2038 arg.cube = cubetofast(solvedcube());
2039 arg.moves = moves;
2040 arg.nmoves = 0;
2041 arg.cocsepdata = (uint32_t *)cocsepdata;
2042 arg.buf32 = buf32;
2043 /* TODO loop until no more is done, not until 12! (or hardcode limits)*/
2044 for (arg.depth = 0, cc = 0; arg.depth < 12; arg.depth++) {
2045 DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
2046 memset(arg.visited, 0, visitedsize);
2047 cc = gendata_esep_dfs(&arg);
2048 info[arg.depth+1] = cc;
2049 DBG_LOG("found %" PRIu32 "\n", cc);
2050 }
2051 free(arg.visited);
2052
2053 return cc;
2054}
2055
2056_static uint32_t
2057gendata_esep_dfs(dfsarg_gendata_t *arg)
2058{
2059 uint8_t m, t, olddepth;
2060 uint32_t cc;
2061 uint64_t i;
2062 cube_fast_t d;
2063 dfsarg_gendata_t nextarg;
2064
2065 if (!allowednextmove(arg->moves, arg->nmoves))
2066 return 0;
2067
2068 if (arg->nmoves > 0)
2069 arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]);
2070
2071 i = coord_h48(arg->cube, arg->cocsepdata, 0U);
2072 olddepth = get_esep_pval(arg->buf32, i);
2073
2074 if (olddepth < arg->nmoves || get_visited(arg->visited, i))
2075 return 0;
2076 set_visited(arg->visited, i);
2077
2078 if (arg->nmoves == arg->depth) {
2079 if (olddepth != 15U)
2080 return 0;
2081
2082 for (t = 0, cc = 0; t < 48; t++) {
2083 d = transform(arg->cube, t);
2084 i = coord_h48(d, arg->cocsepdata, 0U);
2085 set_visited(arg->visited, i);
2086 cc += get_esep_pval(arg->buf32, i) == 15U;
2087 set_esep_pval(arg->buf32, i, arg->depth);
2088 }
2089
2090 return cc;
2091 }
2092
2093
2094 nextarg = *arg;
2095 nextarg.nmoves = arg->nmoves + 1;
2096 for (m = 0, cc = 0; m < 18; m++) {
2097 nextarg.cube = arg->cube;
2098 nextarg.moves[arg->nmoves] = m;
2099 cc += gendata_esep_dfs(&nextarg);
2100 }
2101
2102 return cc;
2103}
2104
2105_static_inline bool get_visited(const uint8_t *a, int64_t i)
2106{
2107 return a[_visited_ind(i)] & _visited_mask(i);
2108}
2109
2110_static_inline void set_visited(uint8_t *a, int64_t i)
2111{
2112 a[_visited_ind(i)] |= _visited_mask(i);
2113}
2114
2115_static_inline uint8_t
2116get_esep_pval(const uint32_t *buf32, int64_t i)
2117{
2118 return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i);
2119}
2120
2121_static_inline void
2122set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
2123{
2124 buf32[_esep_ind(i)] =
2125 (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i));
2126}
2127
2128/******************************************************************************
2129Section: solvers
2130
2131Here you can find the implementation of all the solving algorithms.
2132******************************************************************************/
2133
2134typedef struct {
2135 cube_fast_t cube;
2136 uint8_t depth;
2137 int64_t maxsols;
2138 char **nextsol;
2139 int64_t *nsols;
2140 uint8_t nmoves;
2141 uint8_t moves[20];
2142 uint8_t (*estimate)(cube_fast_t);
2143} dfsarg_generic_t;
2144
2145_static void solve_generic_appendsolution(dfsarg_generic_t *);
2146_static int solve_generic_dfs(dfsarg_generic_t *);
2147_static int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t,
2148 int8_t, char *, uint8_t (*)(cube_fast_t));
2149_static uint8_t estimate_simple(cube_fast_t);
2150_static int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *);
2151
2152int64_t
2153solve(
2154 cube_t cube,
2155 const char *solver,
2156 const char *options,
2157 const char *nisstype,
2158 int8_t minmoves,
2159 int8_t maxmoves,
2160 int64_t maxsols,
2161 int8_t optimal,
2162 const void *data,
2163 char *solutions
2164)
2165{
2166 DBG_WARN(!strcmp(options, ""),
2167 "solve: 'options' not implemented yet, ignoring\n");
2168
2169 DBG_WARN(!strcmp(nisstype, ""),
2170 "solve: NISS not implemented yet, ignoring 'nisstype'\n");
2171
2172 DBG_WARN(data == NULL,
2173 "solve: 'data' not implemented yet, ignoring\n");
2174
2175 if (!strcmp(solver, "optimal") || !strcmp(solver, "simple")) {
2176 return solve_simple(
2177 cube,
2178 minmoves,
2179 maxmoves,
2180 maxsols,
2181 optimal,
2182 solutions
2183 );
2184 } else {
2185 DBG_LOG("solve: unknown solver '%s'\n", solver);
2186 return -1;
2187 }
2188
2189 DBG_LOG("solve: error\n");
2190 return -1;
2191}
2192
2193void
2194multisolve(
2195 int n,
2196 cube_t *cube,
2197 const char *solver,
2198 const void *data,
2199 char *sols
2200)
2201{
2202 char *s;
2203 int i;
2204
2205 s = sols;
2206 for (i = 0; i < n; i++) {
2207 solve(cube[i], solver, "", "normal", 0, -1, 1, 0, NULL, s);
2208 while (s++);
2209 }
2210}
2211
2212int64_t
2213gendata(const char *solver, void *data)
2214{
2215 DBG_LOG("gendata: not implemented yet\n");
2216
2217 return -1;
2218}
2219
2220_static void
2221solve_generic_appendsolution(dfsarg_generic_t *arg)
2222{
2223 int strl;
2224
2225 strl = writemoves(arg->moves, arg->depth, *arg->nextsol);
2226 DBG_LOG("Solution found: %s\n", *arg->nextsol);
2227 *arg->nextsol += strl;
2228 **arg->nextsol = '\n';
2229 (*arg->nextsol)++;
2230 (*arg->nsols)++;
2231}
2232
2233_static int
2234solve_generic_dfs(dfsarg_generic_t *arg)
2235{
2236 dfsarg_generic_t nextarg;
2237 uint8_t m, bound;
2238 int64_t ret;
2239
2240 if (!allowednextmove(arg->moves, arg->nmoves))
2241 return 0;
2242
2243 if (arg->nmoves > 0)
2244 arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]);
2245
2246 bound = arg->estimate(arg->cube);
2247 if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth)
2248 return 0;
2249
2250 if (bound == 0) {
2251 if (arg->nmoves != arg->depth)
2252 return 0;
2253 solve_generic_appendsolution(arg);
2254 return 1;
2255 }
2256
2257 /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */
2258 nextarg = *arg;
2259 nextarg.nmoves = arg->nmoves + 1;
2260 for (m = 0, ret = 0; m < 18; m++) {
2261 nextarg.cube = arg->cube;
2262 nextarg.moves[arg->nmoves] = m;
2263 ret += solve_generic_dfs(&nextarg);
2264 }
2265
2266 return ret;
2267}
2268
2269_static int64_t
2270solve_generic(
2271 cube_t cube,
2272 const char *nisstype,
2273 /* TODO: handle NISS */
2274 int8_t minmoves,
2275 int8_t maxmoves,
2276 int64_t maxsols,
2277 int8_t optimal,
2278 char *sols,
2279 uint8_t (*estimate)(cube_fast_t)
2280 /* TODO: add validator */
2281 /* TODO: maybe add data for estimate */
2282 /* TODO: add moveset (and allowednext?) */
2283)
2284{
2285 dfsarg_generic_t arg;
2286 int64_t ret, tmp, first;
2287
2288 if (!issolvable(cube)) {
2289 DBG_LOG("solve: cube is not solvable\n");
2290 return -1;
2291 }
2292
2293 if (issolved(cube)) {
2294 DBG_LOG("solve: cube is already solved\n");
2295 sols[0] = '\n';
2296 sols[1] = 0;
2297 return 1;
2298 }
2299
2300 DBG_WARN(!strcmp(nisstype, ""),
2301 "solve: NISS not implemented yet, 'nisstype' ignored\n");
2302
2303 if (minmoves < 0) {
2304 DBG_LOG("solve: 'minmoves' is negative, setting to 0\n");
2305 minmoves = 0;
2306 }
2307
2308 if (maxmoves < 0) {
2309 DBG_LOG("solve: invalid 'maxmoves', setting to 20\n");
2310 maxmoves = 20;
2311 }
2312
2313 if (maxsols < 0) {
2314 DBG_LOG("solve: 'maxsols' is negative\n");
2315 return -1;
2316 }
2317
2318 if (maxsols == 0) {
2319 DBG_LOG("solve: 'maxsols' is 0\n");
2320 return 0;
2321 }
2322
2323 if (sols == NULL) {
2324 DBG_LOG("solve: return parameter 'sols' is NULL\n");
2325 return -1;
2326 }
2327
2328 if (estimate == NULL) {
2329 DBG_LOG("solve: 'estimate' is NULL\n");
2330 return -1;
2331 }
2332
2333 arg = (dfsarg_generic_t) {
2334 .cube = cubetofast(cube),
2335 .maxsols = maxsols,
2336 .nextsol = &sols,
2337 .nsols = &ret,
2338 .nmoves = 0,
2339 .moves = {0},
2340 .estimate = estimate,
2341 };
2342
2343 ret = 0;
2344 first = -1;
2345 for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) {
2346 tmp = solve_generic_dfs(&arg);
2347 if (tmp != 0)
2348 first = arg.depth;
2349
2350 DBG_LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n",
2351 tmp, tmp == 1 ? "" : "s", arg.depth);
2352
2353 if (ret >= maxsols)
2354 break;
2355
2356 if (optimal >= 0 && first >= 0 && arg.depth - first == optimal)
2357 break;
2358 }
2359
2360 DBG_ASSERT(ret <= maxsols, ret,
2361 "solve: found more than 'maxsols' solutions\n");
2362
2363 return ret;
2364}
2365
2366_static uint8_t
2367estimate_simple(cube_fast_t cube)
2368{
2369 return issolved_fast(cube) ? 0 : 1;
2370}
2371
2372_static int64_t
2373solve_simple(
2374 cube_t cube,
2375 int8_t minmoves,
2376 int8_t maxmoves,
2377 int64_t maxsols,
2378 int8_t optimal,
2379 char *solutions
2380)
2381{
2382 return solve_generic(
2383 cube,
2384 "",
2385 minmoves,
2386 maxmoves,
2387 maxsols,
2388 optimal,
2389 solutions,
2390 &estimate_simple
2391 );
2392}
diff --git a/src/cube.h b/src/cube.h
new file mode 100644
index 0000000..32547cf
--- /dev/null
+++ b/src/cube.h
@@ -0,0 +1,164 @@
1/******************************************************************************
2Cube type definition
3
4Each piece is represented by an (unsigned) 8-bit integer. The 4
5least-significant bits determine which piece it is, the other 4 determine
6the orientation.
7
8Edges are numbered as follows (see also cube.c):
9UF=0 UB=1 DB=2 DF=3 UR=4 UL=5 DL=6 DR=7 FR=8 FL=9 BL=10 BR=11
10
11Corners are numbered as follows:
12UFR=0 UBL=1 DFL=2 DBR=3 UFL=4 UBR=5 DFR=6 DBL=7
13
14The orientation of the edges is with respect to F/B, the orientation of
15corners is with respect to U/D.
16
17The permutation of the center pieces is not stored. This means that the
18cube is assumed to be in a fixed orientation.
19
20TODO: define EO and CO better, explain how to use them
21TODO: encode centers?
22
23The exact cube type structure depends on your system's configuration. If
24you operate on the cube only via the functions provided below, you don't
25need to worry about this.
26******************************************************************************/
27
28typedef struct {
29 uint8_t corner[8];
30 uint8_t edge[12];
31} cube_t;
32
33/* Returns a copy of the solved cube */
34cube_t solvedcube(void);
35
36/* Basic checks on the cube */
37bool isconsistent(cube_t);
38bool issolvable(cube_t);
39bool issolved(cube_t);
40bool equal(cube_t, cube_t);
41
42/* All functions can return an error value, use iserror() to check this */
43bool iserror(cube_t);
44
45/* Apply the second cube on the first as a move sequence */
46cube_t compose(cube_t, cube_t);
47
48/* Invert the cube */
49cube_t inverse(cube_t);
50
51/* Check if a cube represent a valid state (possibly unsolvable) */
52
53/* TODO comment on these and the format for moves and trans */
54/* For trans, only one trans is supported */
55cube_t applymoves(cube_t, const char *);
56cube_t applytrans(cube_t, const char *);
57
58/******************************************************************************
59Read / write utilities
60
61Reading and writing is not done directly via stdin / stdout, but via an
62array of char (called buf in the prototypes below).
63
64Multiple representations of the cube as text are supported:
65
66- H48: a human-readable format.
67 Each edge is represented by two letters denoting the sides it
68 belongs to and one number denoting its orientation (0 oriented, 1
69 mis-oriented). Similarly, each corner is represented by three letters and
70 a number (0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
71
72 The solved cube looks like this:
73
74 UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
75 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
76
77 The cube after the moves R'U'F looks like this:
78
79 FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
80 UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
81
82 Whitespace (including newlines) between pieces is ignored when reading the
83 cube. A single whitespace character is added between pieces when writing.
84
85- SRC: format used to generate code for internal use.
86 If OUT is the output in SRC format, one can use `cube_t cube = OUT` to
87 declare a new cube object.
88
89- LST: a format for internal use and generating code.
90 The cube is printed as a comma-separated list of 20 integers, as they appear
91 in cube_t. Corners come first, followed by edge (unlike H48).
92******************************************************************************/
93
94cube_t readcube(const char *format, const char *buf);
95void writecube(const char *format, cube_t cube, char *buf);
96
97/******************************************************************************
98Solvers
99
100The solutions are returned as a newline-separated list of characters. Moves
101are separated by single spaces.
102
103Unless specified otherwise, all the solutions are not trivially simplifiable.
104This means that sequences like U U2 or R L R will not appear in any solution.
105Moreover, two consecutive parallel moves are always going to be sorted in
106increasing order. For example, L R2 may never appear in a solution, but R2 L
107could.
108******************************************************************************/
109
110int64_t solve(
111 /* The cube to solve. Must be solvable. */
112 cube_t cube,
113
114 /* Supported solvers:
115 * "optimal" - currently the same as "simple"
116 * "simple" - a simple, slow solver without tables
117 */
118 const char *solver,
119
120 /* Some solvers accept extra options,like "!filter". */
121 const char *options,
122
123 /* Can be "normal", "inverse", "mixed" or "linear". */
124 const char *nisstype,
125
126 /* The minimum number of moves. Must be >= 0. */
127 int8_t minmoves,
128
129 /* The maximum number of moves. If negative, the maximum length
130 * is unlimited.
131 */
132 int8_t maxmoves,
133
134 /* The maximum number of solutions. */
135 int64_t maxsols,
136
137 /* All solutions at most "optimal" moves from the shortest solution
138 * (respecting minmoves) are found. If negative, it is ignored.
139 */
140 int8_t optimal,
141
142 /* Some solvers require extra data to function properly (for example,
143 * pruning tables). This data can be generated with gendata().
144 */
145 const void *data,
146
147 /* The solutions (return parameter) */
148 char *solutions
149);
150
151/* Solving n cubes optimally, one solutions per cube. Options are similar
152 * to solve().
153 */
154void multisolve(
155 int n,
156 cube_t *cube,
157 const char *solver,
158 const void *data,
159 char *sols
160);
161
162/* Returns the number of bytes written to data, -1 in case of error.
163 * TODO: write down how much memory every solver requires. */
164int64_t gendata(const char *solver, void *data);

Generated with cgit - Back to sebastiano.tronto.net