aboutsummaryrefslogtreecommitdiff
path: root/src/cube.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/cube.c2371
1 files changed, 9 insertions, 2362 deletions
diff --git a/src/cube.c b/src/cube.c
index 02bbc63..27d54b4 100644
--- a/src/cube.c
+++ b/src/cube.c
@@ -2,10 +2,7 @@
2#include <stdbool.h> 2#include <stdbool.h>
3#include <string.h> 3#include <string.h>
4 4
5#include "cube.h"
6
7#ifdef DEBUG 5#ifdef DEBUG
8
9#include <stdio.h> 6#include <stdio.h>
10#define _static 7#define _static
11#define _static_inline 8#define _static_inline
@@ -16,2377 +13,27 @@
16 DBG_LOG(__VA_ARGS__); \ 13 DBG_LOG(__VA_ARGS__); \
17 return retval; \ 14 return retval; \
18 } 15 }
19
20#else 16#else
21
22#define _static static 17#define _static static
23#define _static_inline static inline 18#define _static_inline static inline
24#define DBG_LOG(...) 19#define DBG_LOG(...)
25#define DBG_WARN(condition, ...) 20#define DBG_WARN(condition, ...)
26#define DBG_ASSERT(condition, retval, ...) 21#define DBG_ASSERT(condition, retval, ...)
27
28#endif 22#endif
29 23
30/****************************************************************************** 24#include "cube.h"
31Section: mathematical constants 25#include "constants.h"
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 26
576#if defined(CUBE_AVX2) 27#if defined(CUBE_AVX2)
577
578#include <immintrin.h> 28#include <immintrin.h>
579 29#include "cube_avx2.h"
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) 30#elif defined(CUBE_NEON)
818 31#include "cube_neon.h"
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 32#else
835 33#include "cube_portable.h"
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 34#endif
1062 35
1063/****************************************************************************** 36#include "cube_routines.h"
1064Section: generic methods 37#include "moves.h"
1065 38#include "solve_h48.h"
1066This section contains generic functionality, including the public functions. 39#include "solve_generic.h"
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}

Generated with cgit - Back to sebastiano.tronto.net