aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-05-10 09:10:12 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2024-05-10 09:10:12 +0200
commita660922d738b78b11fc78207daabea031058f710 (patch)
treedb46bd95bffeb330cea6066c77f2709f96c033aa
parent75966319fd5891c2c1bd35b1f7c93eab172fd28e (diff)
downloadnissy-core-a660922d738b78b11fc78207daabea031058f710.tar.gz
nissy-core-a660922d738b78b11fc78207daabea031058f710.zip
Split into .h files
Diffstat
-rw-r--r--src/constants.h530
-rw-r--r--src/cube.c2371
-rw-r--r--src/cube_avx2.h229
-rw-r--r--src/cube_neon.h6
-rw-r--r--src/cube_portable.h224
-rw-r--r--src/cube_routines.h730
-rw-r--r--src/moves.h47
-rw-r--r--src/solve_generic.h259
-rw-r--r--src/solve_h48.h266
9 files changed, 2300 insertions, 2362 deletions
diff --git a/src/constants.h b/src/constants.h
new file mode 100644
index 0000000..df444b1
--- /dev/null
+++ b/src/constants.h
@@ -0,0 +1,530 @@
1#define _2p11 2048U
2#define _2p12 4096U
3#define _3p7 2187U
4#define _3p8 6561U
5#define _12c4 495U
6#define _8c4 70U
7
8#define COCSEP_CLASSES 3393U
9
10_static int64_t binomial[12][12] = {
11 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
12 {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
13 {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0},
14 {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0},
15 {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0},
16 {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0},
17 {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0},
18 {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0},
19 {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0},
20 {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0},
21 {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0},
22 {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1},
23};
24
25#define _move_U 0U
26#define _move_U2 1U
27#define _move_U3 2U
28#define _move_D 3U
29#define _move_D2 4U
30#define _move_D3 5U
31#define _move_R 6U
32#define _move_R2 7U
33#define _move_R3 8U
34#define _move_L 9U
35#define _move_L2 10U
36#define _move_L3 11U
37#define _move_F 12U
38#define _move_F2 13U
39#define _move_F3 14U
40#define _move_B 15U
41#define _move_B2 16U
42#define _move_B3 17U
43
44#define _trans_UFr 0
45#define _trans_ULr 1
46#define _trans_UBr 2
47#define _trans_URr 3
48#define _trans_DFr 4
49#define _trans_DLr 5
50#define _trans_DBr 6
51#define _trans_DRr 7
52#define _trans_RUr 8
53#define _trans_RFr 9
54#define _trans_RDr 10
55#define _trans_RBr 11
56#define _trans_LUr 12
57#define _trans_LFr 13
58#define _trans_LDr 14
59#define _trans_LBr 15
60#define _trans_FUr 16
61#define _trans_FRr 17
62#define _trans_FDr 18
63#define _trans_FLr 19
64#define _trans_BUr 20
65#define _trans_BRr 21
66#define _trans_BDr 22
67#define _trans_BLr 23
68
69#define _trans_UFm 24
70#define _trans_ULm 25
71#define _trans_UBm 26
72#define _trans_URm 27
73#define _trans_DFm 28
74#define _trans_DLm 29
75#define _trans_DBm 30
76#define _trans_DRm 31
77#define _trans_RUm 32
78#define _trans_RFm 33
79#define _trans_RDm 34
80#define _trans_RBm 35
81#define _trans_LUm 36
82#define _trans_LFm 37
83#define _trans_LDm 38
84#define _trans_LBm 39
85#define _trans_FUm 40
86#define _trans_FRm 41
87#define _trans_FDm 42
88#define _trans_FLm 43
89#define _trans_BUm 44
90#define _trans_BRm 45
91#define _trans_BDm 46
92#define _trans_BLm 47
93
94#define _c_ufr 0U
95#define _c_ubl 1U
96#define _c_dfl 2U
97#define _c_dbr 3U
98#define _c_ufl 4U
99#define _c_ubr 5U
100#define _c_dfr 6U
101#define _c_dbl 7U
102
103#define _e_uf 0U
104#define _e_ub 1U
105#define _e_db 2U
106#define _e_df 3U
107#define _e_ur 4U
108#define _e_ul 5U
109#define _e_dl 6U
110#define _e_dr 7U
111#define _e_fr 8U
112#define _e_fl 9U
113#define _e_bl 10U
114#define _e_br 11U
115
116#define _eoshift 4U
117#define _coshift 5U
118
119#define _pbits 0xFU
120#define _esepbit1 0x4U
121#define _esepbit2 0x8U
122#define _csepbit 0x4U
123#define _eobit 0x10U
124#define _cobits 0xF0U
125#define _cobits2 0x60U
126#define _ctwist_cw 0x20U
127#define _ctwist_ccw 0x40U
128#define _eflip 0x10U
129#define _error 0xFFU
130
131_static cube_t zero = { .corner = {0}, .edge = {0} };
132_static cube_t solved = {
133 .corner = {0, 1, 2, 3, 4, 5, 6, 7},
134 .edge = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
135};
136
137#define zero_fast fastcube( \
138 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
139#define solved_fast fastcube( \
140 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
141
142#define _move_cube_U fastcube( \
143 5, 4, 2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 1, 0, 6, 7, 8, 9, 10, 11)
144#define _move_cube_U2 fastcube( \
145 1, 0, 2, 3, 5, 4, 6, 7, 1, 0, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11)
146#define _move_cube_U3 fastcube( \
147 4, 5, 2, 3, 1, 0, 6, 7, 5, 4, 2, 3, 0, 1, 6, 7, 8, 9, 10, 11)
148#define _move_cube_D fastcube( \
149 0, 1, 7, 6, 4, 5, 2, 3, 0, 1, 7, 6, 4, 5, 2, 3, 8, 9, 10, 11)
150#define _move_cube_D2 fastcube( \
151 0, 1, 3, 2, 4, 5, 7, 6, 0, 1, 3, 2, 4, 5, 7, 6, 8, 9, 10, 11)
152#define _move_cube_D3 fastcube( \
153 0, 1, 6, 7, 4, 5, 3, 2, 0, 1, 6, 7, 4, 5, 3, 2, 8, 9, 10, 11)
154#define _move_cube_R fastcube( \
155 70, 1, 2, 69, 4, 32, 35, 7, 0, 1, 2, 3, 8, 5, 6, 11, 7, 9, 10, 4)
156#define _move_cube_R2 fastcube( \
157 3, 1, 2, 0, 4, 6, 5, 7, 0, 1, 2, 3, 7, 5, 6, 4, 11, 9, 10, 8)
158#define _move_cube_R3 fastcube( \
159 69, 1, 2, 70, 4, 35, 32, 7, 0, 1, 2, 3, 11, 5, 6, 8, 4, 9, 10, 7)
160#define _move_cube_L fastcube( \
161 0, 71, 68, 3, 33, 5, 6, 34, 0, 1, 2, 3, 4, 10, 9, 7, 8, 5, 6, 11)
162#define _move_cube_L2 fastcube( \
163 0, 2, 1, 3, 7, 5, 6, 4, 0, 1, 2, 3, 4, 6, 5, 7, 8, 10, 9, 11)
164#define _move_cube_L3 fastcube( \
165 0, 68, 71, 3, 34, 5, 6, 33, 0, 1, 2, 3, 4, 9, 10, 7, 8, 6, 5, 11)
166#define _move_cube_F fastcube( \
167 36, 1, 38, 3, 66, 5, 64, 7, 25, 1, 2, 24, 4, 5, 6, 7, 16, 19, 10, 11)
168#define _move_cube_F2 fastcube( \
169 2, 1, 0, 3, 6, 5, 4, 7, 3, 1, 2, 0, 4, 5, 6, 7, 9, 8, 10, 11)
170#define _move_cube_F3 fastcube( \
171 38, 1, 36, 3, 64, 5, 66, 7, 24, 1, 2, 25, 4, 5, 6, 7, 19, 16, 10, 11)
172#define _move_cube_B fastcube( \
173 0, 37, 2, 39, 4, 67, 6, 65, 0, 27, 26, 3, 4, 5, 6, 7, 8, 9, 17, 18)
174#define _move_cube_B2 fastcube( \
175 0, 3, 2, 1, 4, 7, 6, 5, 0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 11, 10)
176#define _move_cube_B3 fastcube( \
177 0, 39, 2, 37, 4, 65, 6, 67, 0, 26, 27, 3, 4, 5, 6, 7, 8, 9, 18, 17)
178
179#define _trans_cube_UFr fastcube( \
180 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
181#define _trans_cube_UFr_inverse fastcube( \
182 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
183#define _trans_cube_ULr fastcube( \
184 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24)
185#define _trans_cube_ULr_inverse fastcube( \
186 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26)
187#define _trans_cube_UBr fastcube( \
188 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9)
189#define _trans_cube_UBr_inverse fastcube( \
190 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9)
191#define _trans_cube_URr fastcube( \
192 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26)
193#define _trans_cube_URr_inverse fastcube( \
194 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24)
195#define _trans_cube_DFr fastcube( \
196 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10)
197#define _trans_cube_DFr_inverse fastcube( \
198 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10)
199#define _trans_cube_DLr fastcube( \
200 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27)
201#define _trans_cube_DLr_inverse fastcube( \
202 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27)
203#define _trans_cube_DBr fastcube( \
204 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8)
205#define _trans_cube_DBr_inverse fastcube( \
206 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8)
207#define _trans_cube_DRr fastcube( \
208 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25)
209#define _trans_cube_DRr_inverse fastcube( \
210 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25)
211#define _trans_cube_RUr fastcube( \
212 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3)
213#define _trans_cube_RUr_inverse fastcube( \
214 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21)
215#define _trans_cube_RFr fastcube( \
216 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18)
217#define _trans_cube_RFr_inverse fastcube( \
218 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17)
219#define _trans_cube_RDr fastcube( \
220 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1)
221#define _trans_cube_RDr_inverse fastcube( \
222 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20)
223#define _trans_cube_RBr fastcube( \
224 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16)
225#define _trans_cube_RBr_inverse fastcube( \
226 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16)
227#define _trans_cube_LUr fastcube( \
228 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2)
229#define _trans_cube_LUr_inverse fastcube( \
230 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23)
231#define _trans_cube_LFr fastcube( \
232 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17)
233#define _trans_cube_LFr_inverse fastcube( \
234 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18)
235#define _trans_cube_LDr fastcube( \
236 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0)
237#define _trans_cube_LDr_inverse fastcube( \
238 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22)
239#define _trans_cube_LBr fastcube( \
240 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19)
241#define _trans_cube_LBr_inverse fastcube( \
242 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19)
243#define _trans_cube_FUr fastcube( \
244 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6)
245#define _trans_cube_FUr_inverse fastcube( \
246 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6)
247#define _trans_cube_FRr fastcube( \
248 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21)
249#define _trans_cube_FRr_inverse fastcube( \
250 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3)
251#define _trans_cube_FDr fastcube( \
252 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4)
253#define _trans_cube_FDr_inverse fastcube( \
254 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7)
255#define _trans_cube_FLr fastcube( \
256 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23)
257#define _trans_cube_FLr_inverse fastcube( \
258 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2)
259#define _trans_cube_BUr fastcube( \
260 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7)
261#define _trans_cube_BUr_inverse fastcube( \
262 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4)
263#define _trans_cube_BRr fastcube( \
264 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22)
265#define _trans_cube_BRr_inverse fastcube( \
266 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0)
267#define _trans_cube_BDr fastcube( \
268 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5)
269#define _trans_cube_BDr_inverse fastcube( \
270 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5)
271#define _trans_cube_BLr fastcube( \
272 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20)
273#define _trans_cube_BLr_inverse fastcube( \
274 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1)
275#define _trans_cube_UFm fastcube( \
276 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10)
277#define _trans_cube_UFm_inverse fastcube( \
278 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10)
279#define _trans_cube_ULm fastcube( \
280 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25)
281#define _trans_cube_ULm_inverse fastcube( \
282 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25)
283#define _trans_cube_UBm fastcube( \
284 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8)
285#define _trans_cube_UBm_inverse fastcube( \
286 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8)
287#define _trans_cube_URm fastcube( \
288 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27)
289#define _trans_cube_URm_inverse fastcube( \
290 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27)
291#define _trans_cube_DFm fastcube( \
292 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11)
293#define _trans_cube_DFm_inverse fastcube( \
294 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11)
295#define _trans_cube_DLm fastcube( \
296 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26)
297#define _trans_cube_DLm_inverse fastcube( \
298 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24)
299#define _trans_cube_DBm fastcube( \
300 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9)
301#define _trans_cube_DBm_inverse fastcube( \
302 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9)
303#define _trans_cube_DRm fastcube( \
304 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24)
305#define _trans_cube_DRm_inverse fastcube( \
306 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26)
307#define _trans_cube_RUm fastcube( \
308 68, 71, 69, 70, 33, 34, 32, 35, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3)
309#define _trans_cube_RUm_inverse fastcube( \
310 70, 68, 69, 71, 32, 34, 35, 33, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22)
311#define _trans_cube_RFm fastcube( \
312 34, 33, 32, 35, 68, 71, 70, 69, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18)
313#define _trans_cube_RFm_inverse fastcube( \
314 66, 65, 64, 67, 36, 39, 38, 37, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18)
315#define _trans_cube_RDm fastcube( \
316 71, 68, 70, 69, 34, 33, 35, 32, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1)
317#define _trans_cube_RDm_inverse fastcube( \
318 71, 69, 68, 70, 33, 35, 34, 32, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23)
319#define _trans_cube_RBm fastcube( \
320 33, 34, 35, 32, 71, 68, 69, 70, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16)
321#define _trans_cube_RBm_inverse fastcube( \
322 67, 64, 65, 66, 37, 38, 39, 36, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19)
323#define _trans_cube_LUm fastcube( \
324 69, 70, 68, 71, 32, 35, 33, 34, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2)
325#define _trans_cube_LUm_inverse fastcube( \
326 68, 70, 71, 69, 34, 32, 33, 35, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20)
327#define _trans_cube_LFm fastcube( \
328 32, 35, 34, 33, 70, 69, 68, 71, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17)
329#define _trans_cube_LFm_inverse fastcube( \
330 64, 67, 66, 65, 38, 37, 36, 39, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17)
331#define _trans_cube_LDm fastcube( \
332 70, 69, 71, 68, 35, 32, 34, 33, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
333#define _trans_cube_LDm_inverse fastcube( \
334 69, 71, 70, 68, 35, 33, 32, 34, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21)
335#define _trans_cube_LBm fastcube( \
336 35, 32, 33, 34, 69, 70, 71, 68, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19)
337#define _trans_cube_LBm_inverse fastcube( \
338 65, 66, 67, 64, 39, 36, 37, 38, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16)
339#define _trans_cube_FUm fastcube( \
340 64, 66, 65, 67, 36, 38, 37, 39, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7)
341#define _trans_cube_FUm_inverse fastcube( \
342 32, 34, 33, 35, 68, 70, 69, 71, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7)
343#define _trans_cube_FRm fastcube( \
344 36, 38, 39, 37, 66, 64, 65, 67, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20)
345#define _trans_cube_FRm_inverse fastcube( \
346 37, 38, 36, 39, 64, 67, 65, 66, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2)
347#define _trans_cube_FDm fastcube( \
348 66, 64, 67, 65, 38, 36, 39, 37, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5)
349#define _trans_cube_FDm_inverse fastcube( \
350 33, 35, 32, 34, 69, 71, 68, 70, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6)
351#define _trans_cube_FLm fastcube( \
352 38, 36, 37, 39, 64, 66, 67, 65, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22)
353#define _trans_cube_FLm_inverse fastcube( \
354 36, 39, 37, 38, 65, 66, 64, 67, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3)
355#define _trans_cube_BUm fastcube( \
356 65, 67, 64, 66, 37, 39, 36, 38, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6)
357#define _trans_cube_BUm_inverse fastcube( \
358 34, 32, 35, 33, 70, 68, 71, 69, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5)
359#define _trans_cube_BRm fastcube( \
360 39, 37, 36, 38, 65, 67, 66, 64, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23)
361#define _trans_cube_BRm_inverse fastcube( \
362 39, 36, 38, 37, 66, 65, 67, 64, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1)
363#define _trans_cube_BDm fastcube( \
364 67, 65, 66, 64, 39, 37, 38, 36, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4)
365#define _trans_cube_BDm_inverse fastcube( \
366 35, 33, 34, 32, 71, 69, 70, 68, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4)
367#define _trans_cube_BLm fastcube( \
368 37, 39, 38, 36, 67, 65, 64, 66, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21)
369#define _trans_cube_BLm_inverse fastcube( \
370 38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0)
371
372_static const char *cornerstr[] = {
373 [_c_ufr] = "UFR",
374 [_c_ubl] = "UBL",
375 [_c_dfl] = "DFL",
376 [_c_dbr] = "DBR",
377 [_c_ufl] = "UFL",
378 [_c_ubr] = "UBR",
379 [_c_dfr] = "DFR",
380 [_c_dbl] = "DBL"
381};
382
383_static const char *cornerstralt[] = {
384 [_c_ufr] = "URF",
385 [_c_ubl] = "ULB",
386 [_c_dfl] = "DLF",
387 [_c_dbr] = "DRB",
388 [_c_ufl] = "ULF",
389 [_c_ubr] = "URB",
390 [_c_dfr] = "DRF",
391 [_c_dbl] = "DLB"
392};
393
394_static const char *edgestr[] = {
395 [_e_uf] = "UF",
396 [_e_ub] = "UB",
397 [_e_db] = "DB",
398 [_e_df] = "DF",
399 [_e_ur] = "UR",
400 [_e_ul] = "UL",
401 [_e_dl] = "DL",
402 [_e_dr] = "DR",
403 [_e_fr] = "FR",
404 [_e_fl] = "FL",
405 [_e_bl] = "BL",
406 [_e_br] = "BR"
407};
408
409_static const char *movestr[] = {
410 [_move_U] = "U",
411 [_move_U2] = "U2",
412 [_move_U3] = "U'",
413 [_move_D] = "D",
414 [_move_D2] = "D2",
415 [_move_D3] = "D'",
416 [_move_R] = "R",
417 [_move_R2] = "R2",
418 [_move_R3] = "R'",
419 [_move_L] = "L",
420 [_move_L2] = "L2",
421 [_move_L3] = "L'",
422 [_move_F] = "F",
423 [_move_F2] = "F2",
424 [_move_F3] = "F'",
425 [_move_B] = "B",
426 [_move_B2] = "B2",
427 [_move_B3] = "B'",
428};
429
430_static const char *transstr[] = {
431 [_trans_UFr] = "rotation UF",
432 [_trans_UFm] = "mirrored UF",
433 [_trans_ULr] = "rotation UL",
434 [_trans_ULm] = "mirrored UL",
435 [_trans_UBr] = "rotation UB",
436 [_trans_UBm] = "mirrored UB",
437 [_trans_URr] = "rotation UR",
438 [_trans_URm] = "mirrored UR",
439 [_trans_DFr] = "rotation DF",
440 [_trans_DFm] = "mirrored DF",
441 [_trans_DLr] = "rotation DL",
442 [_trans_DLm] = "mirrored DL",
443 [_trans_DBr] = "rotation DB",
444 [_trans_DBm] = "mirrored DB",
445 [_trans_DRr] = "rotation DR",
446 [_trans_DRm] = "mirrored DR",
447 [_trans_RUr] = "rotation RU",
448 [_trans_RUm] = "mirrored RU",
449 [_trans_RFr] = "rotation RF",
450 [_trans_RFm] = "mirrored RF",
451 [_trans_RDr] = "rotation RD",
452 [_trans_RDm] = "mirrored RD",
453 [_trans_RBr] = "rotation RB",
454 [_trans_RBm] = "mirrored RB",
455 [_trans_LUr] = "rotation LU",
456 [_trans_LUm] = "mirrored LU",
457 [_trans_LFr] = "rotation LF",
458 [_trans_LFm] = "mirrored LF",
459 [_trans_LDr] = "rotation LD",
460 [_trans_LDm] = "mirrored LD",
461 [_trans_LBr] = "rotation LB",
462 [_trans_LBm] = "mirrored LB",
463 [_trans_FUr] = "rotation FU",
464 [_trans_FUm] = "mirrored FU",
465 [_trans_FRr] = "rotation FR",
466 [_trans_FRm] = "mirrored FR",
467 [_trans_FDr] = "rotation FD",
468 [_trans_FDm] = "mirrored FD",
469 [_trans_FLr] = "rotation FL",
470 [_trans_FLm] = "mirrored FL",
471 [_trans_BUr] = "rotation BU",
472 [_trans_BUm] = "mirrored BU",
473 [_trans_BRr] = "rotation BR",
474 [_trans_BRm] = "mirrored BR",
475 [_trans_BDr] = "rotation BD",
476 [_trans_BDm] = "mirrored BD",
477 [_trans_BLr] = "rotation BL",
478 [_trans_BLm] = "mirrored BL",
479};
480
481static uint8_t inverse_trans_table[48] = {
482 [_trans_UFr] = _trans_UFr,
483 [_trans_UFm] = _trans_UFm,
484 [_trans_ULr] = _trans_URr,
485 [_trans_ULm] = _trans_ULm,
486 [_trans_UBr] = _trans_UBr,
487 [_trans_UBm] = _trans_UBm,
488 [_trans_URr] = _trans_ULr,
489 [_trans_URm] = _trans_URm,
490 [_trans_DFr] = _trans_DFr,
491 [_trans_DFm] = _trans_DFm,
492 [_trans_DLr] = _trans_DLr,
493 [_trans_DLm] = _trans_DRm,
494 [_trans_DBr] = _trans_DBr,
495 [_trans_DBm] = _trans_DBm,
496 [_trans_DRr] = _trans_DRr,
497 [_trans_DRm] = _trans_DLm,
498 [_trans_RUr] = _trans_FRr,
499 [_trans_RUm] = _trans_FLm,
500 [_trans_RFr] = _trans_LFr,
501 [_trans_RFm] = _trans_RFm,
502 [_trans_RDr] = _trans_BLr,
503 [_trans_RDm] = _trans_BRm,
504 [_trans_RBr] = _trans_RBr,
505 [_trans_RBm] = _trans_LBm,
506 [_trans_LUr] = _trans_FLr,
507 [_trans_LUm] = _trans_FRm,
508 [_trans_LFr] = _trans_RFr,
509 [_trans_LFm] = _trans_LFm,
510 [_trans_LDr] = _trans_BRr,
511 [_trans_LDm] = _trans_BLm,
512 [_trans_LBr] = _trans_LBr,
513 [_trans_LBm] = _trans_RBm,
514 [_trans_FUr] = _trans_FUr,
515 [_trans_FUm] = _trans_FUm,
516 [_trans_FRr] = _trans_RUr,
517 [_trans_FRm] = _trans_LUm,
518 [_trans_FDr] = _trans_BUr,
519 [_trans_FDm] = _trans_BUm,
520 [_trans_FLr] = _trans_LUr,
521 [_trans_FLm] = _trans_RUm,
522 [_trans_BUr] = _trans_FDr,
523 [_trans_BUm] = _trans_FDm,
524 [_trans_BRr] = _trans_LDr,
525 [_trans_BRm] = _trans_RDm,
526 [_trans_BDr] = _trans_BDr,
527 [_trans_BDm] = _trans_BDm,
528 [_trans_BLr] = _trans_RDr,
529 [_trans_BLm] = _trans_LDm,
530};
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}
diff --git a/src/cube_avx2.h b/src/cube_avx2.h
new file mode 100644
index 0000000..c61813f
--- /dev/null
+++ b/src/cube_avx2.h
@@ -0,0 +1,229 @@
1typedef __m256i cube_fast_t;
2
3#define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060)
4#define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020)
5#define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707)
6#define _ep_avx2 _mm256_set_epi64x(0x0F0F0F0F, 0x0F0F0F0F0F0F0F0F, 0, 0)
7#define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0)
8
9_static_inline cube_fast_t fastcube(
10 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
11 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
12 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
13 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
14);
15_static cube_fast_t cubetofast(cube_t);
16_static cube_t fasttocube(cube_fast_t);
17_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
18_static_inline bool issolved_fast(cube_fast_t);
19_static_inline cube_fast_t invertco_fast(cube_fast_t);
20_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
21
22_static_inline int64_t coord_fast_co(cube_fast_t);
23_static_inline int64_t coord_fast_csep(cube_fast_t);
24_static_inline int64_t coord_fast_cocsep(cube_fast_t);
25_static_inline int64_t coord_fast_eo(cube_fast_t);
26_static_inline int64_t coord_fast_esep(cube_fast_t);
27
28_static_inline cube_fast_t
29fastcube(
30 uint8_t c_ufr,
31 uint8_t c_ubl,
32 uint8_t c_dfl,
33 uint8_t c_dbr,
34 uint8_t c_ufl,
35 uint8_t c_ubr,
36 uint8_t c_dfr,
37 uint8_t c_dbl,
38
39 uint8_t e_uf,
40 uint8_t e_ub,
41 uint8_t e_db,
42 uint8_t e_df,
43 uint8_t e_ur,
44 uint8_t e_ul,
45 uint8_t e_dl,
46 uint8_t e_dr,
47 uint8_t e_fr,
48 uint8_t e_fl,
49 uint8_t e_bl,
50 uint8_t e_br
51)
52{
53 return _mm256_set_epi8(
54 0, 0, 0, 0, e_br, e_bl, e_fl, e_fr,
55 e_dr, e_dl, e_ul, e_ur, e_df, e_db, e_ub, e_uf,
56 0, 0, 0, 0, 0, 0, 0, 0,
57 c_dbl, c_dfr, c_ubr, c_ufl, c_dbr, c_dfl, c_ubl, c_ufr
58 );
59}
60
61_static cube_fast_t
62cubetofast(cube_t a)
63{
64 uint8_t aux[32];
65
66 memset(aux, 0, 32);
67 memcpy(aux, &a.corner, 8);
68 memcpy(aux + 16, &a.edge, 12);
69
70 return _mm256_loadu_si256((__m256i_u *)&aux);
71}
72
73_static cube_t
74fasttocube(cube_fast_t c)
75{
76 cube_t a;
77 uint8_t aux[32];
78
79 _mm256_storeu_si256((__m256i_u *)aux, c);
80 memcpy(&a.corner, aux, 8);
81 memcpy(&a.edge, aux + 16, 12);
82
83 return a;
84}
85
86_static_inline bool
87equal_fast(cube_fast_t c1, cube_fast_t c2)
88{
89 int32_t mask;
90 __m256i cmp;
91
92 cmp = _mm256_cmpeq_epi8(c1, c2);
93 mask = _mm256_movemask_epi8(cmp);
94
95 return mask == ~0;
96}
97
98_static_inline bool
99issolved_fast(cube_fast_t cube)
100{
101 return equal_fast(cube, solved_fast);
102}
103
104_static_inline cube_fast_t
105invertco_fast(cube_fast_t c)
106{
107 cube_fast_t co, shleft, shright, summed, newco, cleanco, ret;
108
109 co = _mm256_and_si256(c, _co2_avx2);
110 shleft = _mm256_slli_epi32(co, 1);
111 shright = _mm256_srli_epi32(co, 1);
112 summed = _mm256_or_si256(shleft, shright);
113 newco = _mm256_and_si256(summed, _co2_avx2);
114 cleanco = _mm256_xor_si256(c, co);
115 ret = _mm256_or_si256(cleanco, newco);
116
117 return ret;
118}
119
120_static_inline cube_fast_t
121compose_fast(cube_fast_t c1, cube_fast_t c2)
122{
123 cube_fast_t s, b, eo2, co1, co2, aux, auy1, auy2, auz1, auz2;
124
125 /* Permute and clean unused bits */
126 s = _mm256_shuffle_epi8(c1, c2);
127 b = _mm256_set_epi8(
128 ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
129 ~0, ~0, ~0, ~0, ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0
130 );
131 s = _mm256_andnot_si256(b, s);
132
133 /* Change EO */
134 eo2 = _mm256_and_si256(c2, _eo_avx2);
135 s = _mm256_xor_si256(s, eo2);
136
137 /* Change CO */
138 co1 = _mm256_and_si256(s, _co2_avx2);
139 co2 = _mm256_and_si256(c2, _co2_avx2);
140 aux = _mm256_add_epi8(co1, co2);
141 auy1 = _mm256_add_epi8(aux, _cocw_avx2);
142 auy2 = _mm256_srli_epi32(auy1, 2);
143 auz1 = _mm256_add_epi8(aux, auy2);
144 auz2 = _mm256_and_si256(auz1, _co2_avx2);
145
146 /* Put together */
147 s = _mm256_andnot_si256(_co2_avx2, s);
148 s = _mm256_or_si256(s, auz2);
149
150 return s;
151}
152
153_static_inline int64_t
154coord_fast_co(cube_fast_t c)
155{
156 cube_fast_t co;
157 int64_t mem[4], ret, i, p;
158
159 co = _mm256_and_si256(c, _co2_avx2);
160 _mm256_storeu_si256((__m256i *)mem, co);
161
162 mem[0] >>= 5L;
163 for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8L, p *= 3)
164 ret += (mem[0] & 3L) * p;
165
166 return ret;
167}
168
169_static_inline int64_t
170coord_fast_csep(cube_fast_t c)
171{
172 cube_fast_t cp, shifted;
173 int64_t mask;
174
175 cp = _mm256_and_si256(c, _cp_avx2);
176 shifted = _mm256_slli_epi32(cp, 5);
177 mask = _mm256_movemask_epi8(shifted);
178
179 return mask & 0x7F;
180}
181
182_static_inline int64_t
183coord_fast_cocsep(cube_fast_t c)
184{
185 return (coord_fast_co(c) << 7) + coord_fast_csep(c);
186}
187
188_static_inline int64_t
189coord_fast_eo(cube_fast_t c)
190{
191 cube_fast_t eo, shifted;
192 int64_t mask;
193
194 eo = _mm256_and_si256(c, _eo_avx2);
195 shifted = _mm256_slli_epi32(eo, 3);
196 mask = _mm256_movemask_epi8(shifted);
197
198 return mask >> 17;
199}
200
201_static_inline int64_t
202coord_fast_esep(cube_fast_t c)
203{
204 cube_fast_t ep;
205 int64_t e, mem[4], i, j, k, l, ret1, ret2, bit1, bit2, is1;
206
207 ep = _mm256_and_si256(c, _ep_avx2);
208 _mm256_storeu_si256((__m256i *)mem, ep);
209
210 mem[3] <<= 8L;
211 ret1 = ret2 = 0;
212 k = l = 4;
213 for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8L) {
214 e = mem[i/8 + 2];
215
216 bit1 = (e & _esepbit1) >> 2L;
217 bit2 = (e & _esepbit2) >> 3L;
218 is1 = (1 - bit2) * bit1;
219
220 ret1 += bit2 * binomial[11-i][k];
221 k -= bit2;
222
223 ret2 += is1 * binomial[7-j][l];
224 l -= is1;
225 j += (1-bit2);
226 }
227
228 return ret1 * 70 + ret2;
229}
diff --git a/src/cube_neon.h b/src/cube_neon.h
new file mode 100644
index 0000000..cb2d815
--- /dev/null
+++ b/src/cube_neon.h
@@ -0,0 +1,6 @@
1/* TODO! */
2
3typedef struct {
4 uint8x16_t corner;
5 uint8x16_t edge;
6} cube_fast_t;
diff --git a/src/cube_portable.h b/src/cube_portable.h
new file mode 100644
index 0000000..281faa0
--- /dev/null
+++ b/src/cube_portable.h
@@ -0,0 +1,224 @@
1typedef cube_t cube_fast_t;
2
3_static_inline cube_fast_t fastcube(
4 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
5 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
6 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
7 uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
8);
9_static cube_fast_t cubetofast(cube_t);
10_static cube_t fasttocube(cube_fast_t);
11_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
12_static_inline bool issolved_fast(cube_fast_t);
13_static_inline cube_fast_t invertco_fast(cube_fast_t);
14_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
15
16_static_inline int64_t coord_fast_co(cube_fast_t);
17_static_inline int64_t coord_fast_csep(cube_fast_t);
18_static_inline int64_t coord_fast_cocsep(cube_fast_t);
19_static_inline int64_t coord_fast_eo(cube_fast_t);
20_static_inline int64_t coord_fast_esep(cube_fast_t);
21
22_static_inline cube_fast_t
23fastcube(
24 uint8_t c_ufr,
25 uint8_t c_ubl,
26 uint8_t c_dfl,
27 uint8_t c_dbr,
28 uint8_t c_ufl,
29 uint8_t c_ubr,
30 uint8_t c_dfr,
31 uint8_t c_dbl,
32
33 uint8_t e_uf,
34 uint8_t e_ub,
35 uint8_t e_db,
36 uint8_t e_df,
37 uint8_t e_ur,
38 uint8_t e_ul,
39 uint8_t e_dl,
40 uint8_t e_dr,
41 uint8_t e_fr,
42 uint8_t e_fl,
43 uint8_t e_bl,
44 uint8_t e_br
45)
46{
47 cube_fast_t cube = {
48 .corner = {
49 c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl
50 },
51 .edge = {
52 e_uf, e_ub, e_db, e_df, e_ur, e_ul,
53 e_dl, e_dr, e_fr, e_fl, e_bl, e_br
54 }
55 };
56
57 return cube;
58}
59
60_static cube_fast_t
61cubetofast(cube_t cube)
62{
63 cube_fast_t fast;
64 memcpy(&fast, &cube, sizeof(cube_fast_t));
65 return fast;
66}
67
68_static cube_t
69fasttocube(cube_fast_t fast)
70{
71 cube_t cube;
72 memcpy(&cube, &fast, sizeof(cube_fast_t));
73 return cube;
74}
75
76_static_inline bool
77equal_fast(cube_fast_t c1, cube_fast_t c2)
78{
79 uint8_t i;
80 bool ret;
81
82 ret = true;
83 for (i = 0; i < 8; i++)
84 ret = ret && c1.corner[i] == c2.corner[i];
85 for (i = 0; i < 12; i++)
86 ret = ret && c1.edge[i] == c2.edge[i];
87
88 return ret;
89}
90
91_static_inline bool
92issolved_fast(cube_fast_t cube)
93{
94 return equal_fast(cube, solved_fast);
95}
96
97_static_inline cube_fast_t
98invertco_fast(cube_fast_t c)
99{
100 uint8_t i, piece, orien;
101 cube_fast_t ret;
102
103 ret = c;
104 for (i = 0; i < 8; i++) {
105 piece = c.corner[i];
106 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
107 ret.corner[i] = (piece & _pbits) | orien;
108 }
109
110 return ret;
111}
112
113_static_inline cube_fast_t
114compose_fast(cube_fast_t c1, cube_fast_t c2)
115{
116 cube_fast_t ret;
117 uint8_t i, piece1, piece2, p, orien, aux, auy;
118
119 ret = zero_fast;
120
121 for (i = 0; i < 12; i++) {
122 piece2 = c2.edge[i];
123 p = piece2 & _pbits;
124 piece1 = c1.edge[p];
125 orien = (piece2 ^ piece1) & _eobit;
126 ret.edge[i] = (piece1 & _pbits) | orien;
127 }
128
129 for (i = 0; i < 8; i++) {
130 piece2 = c2.corner[i];
131 p = piece2 & _pbits;
132 piece1 = c1.corner[p];
133 aux = (piece2 & _cobits) + (piece1 & _cobits);
134 auy = (aux + _ctwist_cw) >> 2U;
135 orien = (aux + auy) & _cobits2;
136 ret.corner[i] = (piece1 & _pbits) | orien;
137 }
138
139 return ret;
140}
141
142_static_inline int64_t
143coord_fast_co(cube_fast_t c)
144{
145 int i, p;
146 int64_t ret;
147
148 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3)
149 ret += p * (c.corner[i] >> _coshift);
150
151 return ret;
152}
153
154/*
155For corner separation, we consider the axis (a.k.a. tetrad) each
156corner belongs to as 0 or 1 and we translate this sequence into binary.
157Ignoring the last bit, we have a value up to 2^7, but not all values are
158possible. Encoding this as a number from 0 to C(8,4) would save about 40%
159of space, but we are not going to use this coordinate in large tables.
160*/
161_static_inline int64_t
162coord_fast_csep(cube_fast_t c)
163{
164 int i, p;
165 int64_t ret;
166
167 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2)
168 ret += p * ((c.corner[i] & _csepbit) >> 2U);
169
170 return ret;
171}
172
173_static_inline int64_t
174coord_fast_cocsep(cube_fast_t c)
175{
176 return (coord_fast_co(c) << 7) + coord_fast_csep(c);
177}
178
179_static_inline int64_t
180coord_fast_eo(cube_fast_t c)
181{
182 int i, p;
183 int64_t ret;
184
185 for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2)
186 ret += p * (c.edge[i] >> _eoshift);
187
188 return ret;
189}
190
191/*
192We encode the edge separation as a number from 0 to C(12,4)*C(8,4).
193It can be seen as the composition of two "subset index" coordinates.
194*/
195_static_inline int64_t
196coord_fast_esep(cube_fast_t c)
197{
198 int64_t i, j, k, l, ret1, ret2, bit1, bit2, is1;
199
200 for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) {
201 /* Simple version:
202 if (c.edge[i] & _esepbit2) {
203 ret1 += binomial[11-i][k--];
204 } else {
205 if (c.edge[i] & _esepbit1)
206 ret2 += binomial[7-j][l--];
207 j++;
208 }
209 */
210
211 bit1 = (c.edge[i] & _esepbit1) >> 2U;
212 bit2 = (c.edge[i] & _esepbit2) >> 3U;
213 is1 = (1 - bit2) * bit1;
214
215 ret1 += bit2 * binomial[11-i][k];
216 k -= bit2;
217
218 ret2 += is1 * binomial[7-j][l];
219 l -= is1;
220 j += (1-bit2);
221 }
222
223 return ret1 * 70 + ret2;
224}
diff --git a/src/cube_routines.h b/src/cube_routines.h
new file mode 100644
index 0000000..b1f8eac
--- /dev/null
+++ b/src/cube_routines.h
@@ -0,0 +1,730 @@
1#define _move(M, c) compose_fast(c, _move_cube_ ## M)
2#define _premove(M, c) compose_fast(_move_cube_ ## M, c)
3#define _trans_rotation(T, c) \
4 compose_fast(compose_fast(_trans_cube_ ## T, c), \
5 _trans_cube_ ## T ## _inverse)
6#define _trans_mirrored(T, c) \
7 invertco_fast(compose_fast(compose_fast(_trans_cube_ ## T, c), \
8 _trans_cube_ ## T ## _inverse))
9
10_static int permsign(uint8_t *, int);
11_static uint8_t readco(const char *);
12_static uint8_t readcp(const char *);
13_static uint8_t readeo(const char *);
14_static uint8_t readep(const char *);
15_static cube_t readcube_H48(const char *);
16_static uint8_t readpiece_LST(const char **);
17_static cube_t readcube_LST(const char *);
18_static int writepiece_LST(uint8_t, char *);
19_static void writecube_H48(cube_t, char *);
20_static void writecube_LST(cube_t, char *);
21_static uint8_t readmove(char);
22_static uint8_t readmodifier(char);
23_static uint8_t readtrans(const char *);
24_static int writemoves(uint8_t *, int, char *);
25_static void writetrans(uint8_t, char *);
26_static cube_fast_t move(cube_fast_t, uint8_t);
27_static cube_fast_t transform(cube_fast_t, uint8_t);
28
29cube_t
30solvedcube(void)
31{
32 return solved;
33}
34
35bool
36isconsistent(cube_t cube)
37{
38 uint8_t i, p, e, piece;
39 bool found[12];
40
41 for (i = 0; i < 12; i++)
42 found[i] = false;
43 for (i = 0; i < 12; i++) {
44 piece = cube.edge[i];
45 p = piece & _pbits;
46 e = piece & _eobit;
47 if (p >= 12)
48 goto inconsistent_ep;
49 if (e != 0 && e != _eobit)
50 goto inconsistent_eo;
51 found[p] = true;
52 }
53 for (i = 0; i < 12; i++)
54 if (!found[i])
55 goto inconsistent_ep;
56
57 for (i = 0; i < 8; i++)
58 found[i] = false;
59 for (i = 0; i < 8; i++) {
60 piece = cube.corner[i];
61 p = piece & _pbits;
62 e = piece & _cobits;
63 if (p >= 8)
64 goto inconsistent_cp;
65 if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw)
66 goto inconsistent_co;
67 found[p] = true;
68 }
69 for (i = 0; i < 8; i++)
70 if (!found[i])
71 goto inconsistent_co;
72
73 return true;
74
75inconsistent_ep:
76 DBG_LOG("Inconsistent EP\n");
77 return false;
78inconsistent_cp:
79 DBG_LOG("Inconsistent CP\n");
80 return false;
81inconsistent_eo:
82 DBG_LOG("Inconsistent EO\n");
83 return false;
84inconsistent_co:
85 DBG_LOG("Inconsistent CO\n");
86 return false;
87}
88
89bool
90issolvable(cube_t cube)
91{
92 uint8_t i, eo, co, piece, edges[12], corners[8];
93
94 DBG_ASSERT(isconsistent(cube), false,
95 "issolvable: cube is inconsistent\n");
96
97 for (i = 0; i < 12; i++)
98 edges[i] = cube.edge[i] & _pbits;
99 for (i = 0; i < 8; i++)
100 corners[i] = cube.corner[i] & _pbits;
101
102 if (permsign(edges, 12) != permsign(corners, 8))
103 goto issolvable_parity;
104
105 eo = 0;
106 for (i = 0; i < 12; i++) {
107 piece = cube.edge[i];
108 eo += (piece & _eobit) >> _eoshift;
109 }
110 if (eo % 2 != 0)
111 goto issolvable_eo;
112
113 co = 0;
114 for (i = 0; i < 8; i++) {
115 piece = cube.corner[i];
116 co += (piece & _cobits) >> _coshift;
117 }
118 if (co % 3 != 0)
119 goto issolvable_co;
120
121 return true;
122
123issolvable_parity:
124 DBG_LOG("EP and CP parities are different\n");
125 return false;
126issolvable_eo:
127 DBG_LOG("Odd number of flipped edges\n");
128 return false;
129issolvable_co:
130 DBG_LOG("Sum of corner orientation is not multiple of 3\n");
131 return false;
132}
133
134bool
135issolved(cube_t cube)
136{
137 return equal(cube, solved);
138}
139
140bool
141equal(cube_t c1, cube_t c2)
142{
143 int i;
144 bool ret;
145
146 ret = true;
147 for (i = 0; i < 8; i++)
148 ret = ret && c1.corner[i] == c2.corner[i];
149 for (i = 0; i < 12; i++)
150 ret = ret && c1.edge[i] == c2.edge[i];
151
152 return ret;
153}
154
155bool
156iserror(cube_t cube)
157{
158 return equal(cube, zero);
159}
160
161cube_t
162compose(cube_t c1, cube_t c2)
163{
164 DBG_ASSERT(isconsistent(c1) && isconsistent(c2),
165 zero, "compose error: inconsistent cube\n")
166
167 return fasttocube(compose_fast(cubetofast(c1), cubetofast(c2)));
168}
169
170cube_t
171inverse(cube_t cube)
172{
173 cube_t ret;
174 uint8_t i, piece, orien;
175
176 DBG_ASSERT(isconsistent(cube), zero,
177 "inverse error: inconsistent cube\n");
178
179 ret = zero;
180
181 for (i = 0; i < 12; i++) {
182 piece = cube.edge[i];
183 orien = piece & _eobit;
184 ret.edge[piece & _pbits] = i | orien;
185 }
186
187 for (i = 0; i < 8; i++) {
188 piece = cube.corner[i];
189 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
190 ret.corner[piece & _pbits] = i | orien;
191 }
192
193 return ret;
194}
195
196cube_t
197applymoves(cube_t cube, const char *buf)
198{
199 cube_fast_t fast;
200 uint8_t r, m;
201 const char *b;
202
203 DBG_ASSERT(isconsistent(cube), zero,
204 "move error: inconsistent cube\n");
205
206 fast = cubetofast(cube);
207
208 for (b = buf; *b != '\0'; b++) {
209 while (*b == ' ' || *b == '\t' || *b == '\n')
210 b++;
211 if (*b == '\0')
212 goto applymoves_finish;
213 if ((r = readmove(*b)) == _error)
214 goto applymoves_error;
215 if ((m = readmodifier(*(b+1))) != 0)
216 b++;
217 fast = move(fast, r + m);
218 }
219
220applymoves_finish:
221 return fasttocube(fast);
222
223applymoves_error:
224 DBG_LOG("applymoves error\n");
225 return zero;
226}
227
228cube_t
229applytrans(cube_t cube, const char *buf)
230{
231 cube_fast_t fast;
232 uint8_t t;
233
234 DBG_ASSERT(isconsistent(cube), zero,
235 "transformation error: inconsistent cube\n");
236
237 t = readtrans(buf);
238 fast = cubetofast(cube);
239 fast = transform(fast, t);
240
241 return fasttocube(fast);
242}
243
244cube_t
245readcube(const char *format, const char *buf)
246{
247 cube_t cube;
248
249 if (!strcmp(format, "H48")) {
250 cube = readcube_H48(buf);
251 } else if (!strcmp(format, "LST")) {
252 cube = readcube_LST(buf);
253 } else {
254 DBG_LOG("Cannot read cube in the given format\n");
255 cube = zero;
256 }
257
258 return cube;
259}
260
261void
262writecube(const char *format, cube_t cube, char *buf)
263{
264 char *errormsg;
265 size_t len;
266
267 if (!isconsistent(cube)) {
268 errormsg = "ERROR: cannot write inconsistent cube";
269 goto writecube_error;
270 }
271
272 if (!strcmp(format, "H48")) {
273 writecube_H48(cube, buf);
274 } else if (!strcmp(format, "LST")) {
275 writecube_LST(cube, buf);
276 } else {
277 errormsg = "ERROR: cannot write cube in the given format";
278 goto writecube_error;
279 }
280
281 return;
282
283writecube_error:
284 DBG_LOG("writecube error, see stdout for details\n");
285 len = strlen(errormsg);
286 memcpy(buf, errormsg, len);
287 buf[len] = '\n';
288 buf[len+1] = '\0';
289}
290
291_static int
292permsign(uint8_t *a, int n)
293{
294 int i, j;
295 uint8_t ret = 0;
296
297 for (i = 0; i < n; i++)
298 for (j = i+1; j < n; j++)
299 ret += a[i] > a[j] ? 1 : 0;
300
301 return ret % 2;
302}
303
304_static uint8_t
305readco(const char *str)
306{
307 if (*str == '0')
308 return 0;
309 if (*str == '1')
310 return _ctwist_cw;
311 if (*str == '2')
312 return _ctwist_ccw;
313
314 DBG_LOG("Error reading CO\n");
315 return _error;
316}
317
318_static uint8_t
319readcp(const char *str)
320{
321 uint8_t c;
322
323 for (c = 0; c < 8; c++)
324 if (!strncmp(str, cornerstr[c], 3) ||
325 !strncmp(str, cornerstralt[c], 3))
326 return c;
327
328 DBG_LOG("Error reading CP\n");
329 return _error;
330}
331
332_static uint8_t
333readeo(const char *str)
334{
335 if (*str == '0')
336 return 0;
337 if (*str == '1')
338 return _eflip;
339
340 DBG_LOG("Error reading EO\n");
341 return _error;
342}
343
344_static uint8_t
345readep(const char *str)
346{
347 uint8_t e;
348
349 for (e = 0; e < 12; e++)
350 if (!strncmp(str, edgestr[e], 2))
351 return e;
352
353 DBG_LOG("Error reading EP\n");
354 return _error;
355}
356
357_static cube_t
358readcube_H48(const char *buf)
359{
360 int i;
361 uint8_t piece, orient;
362 cube_t ret = {0};
363 const char *b;
364
365 b = buf;
366
367 for (i = 0; i < 12; i++) {
368 while (*b == ' ' || *b == '\t' || *b == '\n')
369 b++;
370 if ((piece = readep(b)) == _error)
371 return zero;
372 b += 2;
373 if ((orient = readeo(b)) == _error)
374 return zero;
375 b++;
376 ret.edge[i] = piece | orient;
377 }
378 for (i = 0; i < 8; i++) {
379 while (*b == ' ' || *b == '\t' || *b == '\n')
380 b++;
381 if ((piece = readcp(b)) == _error)
382 return zero;
383 b += 3;
384 if ((orient = readco(b)) == _error)
385 return zero;
386 b++;
387 ret.corner[i] = piece | orient;
388 }
389
390 return ret;
391}
392
393_static uint8_t
394readpiece_LST(const char **b)
395{
396 uint8_t ret;
397 bool read;
398
399 while (**b == ',' || **b == ' ' || **b == '\t' || **b == '\n')
400 (*b)++;
401
402 for (ret = 0, read = false; **b >= '0' && **b <= '9'; (*b)++) {
403 read = true;
404 ret = ret * 10 + (**b) - '0';
405 }
406
407 return read ? ret : _error;
408}
409
410_static cube_t
411readcube_LST(const char *buf)
412{
413 int i;
414 cube_t ret = {0};
415
416 for (i = 0; i < 8; i++)
417 ret.corner[i] = readpiece_LST(&buf);
418
419 for (i = 0; i < 12; i++)
420 ret.edge[i] = readpiece_LST(&buf);
421
422 return ret;
423}
424
425_static int
426writepiece_LST(uint8_t piece, char *buf)
427{
428 char digits[3];
429 int i, len = 0;
430
431 while (piece != 0) {
432 digits[len++] = (piece % 10) + '0';
433 piece /= 10;
434 }
435
436 if (len == 0)
437 digits[len++] = '0';
438
439 for (i = 0; i < len; i++)
440 buf[i] = digits[len-i-1];
441
442 buf[len] = ',';
443 buf[len+1] = ' ';
444
445 return len+2;
446}
447
448_static void
449writecube_H48(cube_t cube, char *buf)
450{
451 uint8_t piece, perm, orient;
452 int i;
453
454 for (i = 0; i < 12; i++) {
455 piece = cube.edge[i];
456 perm = piece & _pbits;
457 orient = (piece & _eobit) >> _eoshift;
458 buf[4*i ] = edgestr[perm][0];
459 buf[4*i + 1] = edgestr[perm][1];
460 buf[4*i + 2] = orient + '0';
461 buf[4*i + 3] = ' ';
462 }
463 for (i = 0; i < 8; i++) {
464 piece = cube.corner[i];
465 perm = piece & _pbits;
466 orient = (piece & _cobits) >> _coshift;
467 buf[48 + 5*i ] = cornerstr[perm][0];
468 buf[48 + 5*i + 1] = cornerstr[perm][1];
469 buf[48 + 5*i + 2] = cornerstr[perm][2];
470 buf[48 + 5*i + 3] = orient + '0';
471 buf[48 + 5*i + 4] = ' ';
472 }
473
474 buf[48+39] = '\0';
475}
476
477_static void
478writecube_LST(cube_t cube, char *buf)
479{
480 int i, ptr;
481 uint8_t piece;
482
483 ptr = 0;
484
485 for (i = 0; i < 8; i++) {
486 piece = cube.corner[i];
487 ptr += writepiece_LST(piece, buf + ptr);
488 }
489
490 for (i = 0; i < 12; i++) {
491 piece = cube.edge[i];
492 ptr += writepiece_LST(piece, buf + ptr);
493 }
494
495 *(buf+ptr-2) = 0;
496}
497
498_static uint8_t
499readmove(char c)
500{
501 switch (c) {
502 case 'U':
503 return _move_U;
504 case 'D':
505 return _move_D;
506 case 'R':
507 return _move_R;
508 case 'L':
509 return _move_L;
510 case 'F':
511 return _move_F;
512 case 'B':
513 return _move_B;
514 default:
515 return _error;
516 }
517}
518
519_static uint8_t
520readmodifier(char c)
521{
522 switch (c) {
523 case '1': /* Fallthrough */
524 case '2': /* Fallthrough */
525 case '3':
526 return c - '0' - 1;
527 case '\'':
528 return 2;
529 default:
530 return 0;
531 }
532}
533
534_static uint8_t
535readtrans(const char *buf)
536{
537 uint8_t t;
538
539 for (t = 0; t < 48; t++)
540 if (!strncmp(buf, transstr[t], 11))
541 return t;
542
543 DBG_LOG("readtrans error\n");
544 return _error;
545}
546
547_static int
548writemoves(uint8_t *m, int n, char *buf)
549{
550 int i;
551 size_t len;
552 const char *s;
553 char *b;
554
555 for (i = 0, b = buf; i < n; i++, b++) {
556 s = movestr[m[i]];
557 len = strlen(s);
558 memcpy(b, s, len);
559 b += len;
560 *b = ' ';
561 }
562
563 if (b != buf)
564 b--; /* Remove last space */
565 *b = '\0';
566
567 return b - buf;
568}
569
570_static void
571writetrans(uint8_t t, char *buf)
572{
573 if (t >= 48)
574 memcpy(buf, "error trans", 11);
575 else
576 memcpy(buf, transstr[t], 11);
577 buf[11] = '\0';
578}
579
580_static cube_fast_t
581move(cube_fast_t c, uint8_t m)
582{
583 switch (m) {
584 case _move_U:
585 return _move(U, c);
586 case _move_U2:
587 return _move(U2, c);
588 case _move_U3:
589 return _move(U3, c);
590 case _move_D:
591 return _move(D, c);
592 case _move_D2:
593 return _move(D2, c);
594 case _move_D3:
595 return _move(D3, c);
596 case _move_R:
597 return _move(R, c);
598 case _move_R2:
599 return _move(R2, c);
600 case _move_R3:
601 return _move(R3, c);
602 case _move_L:
603 return _move(L, c);
604 case _move_L2:
605 return _move(L2, c);
606 case _move_L3:
607 return _move(L3, c);
608 case _move_F:
609 return _move(F, c);
610 case _move_F2:
611 return _move(F2, c);
612 case _move_F3:
613 return _move(F3, c);
614 case _move_B:
615 return _move(B, c);
616 case _move_B2:
617 return _move(B2, c);
618 case _move_B3:
619 return _move(B3, c);
620 default:
621 DBG_LOG("move error, unknown move\n");
622 return zero_fast;
623 }
624}
625
626_static cube_fast_t
627transform(cube_fast_t c, uint8_t t)
628{
629 switch (t) {
630 case _trans_UFr:
631 return _trans_rotation(UFr, c);
632 case _trans_ULr:
633 return _trans_rotation(ULr, c);
634 case _trans_UBr:
635 return _trans_rotation(UBr, c);
636 case _trans_URr:
637 return _trans_rotation(URr, c);
638 case _trans_DFr:
639 return _trans_rotation(DFr, c);
640 case _trans_DLr:
641 return _trans_rotation(DLr, c);
642 case _trans_DBr:
643 return _trans_rotation(DBr, c);
644 case _trans_DRr:
645 return _trans_rotation(DRr, c);
646 case _trans_RUr:
647 return _trans_rotation(RUr, c);
648 case _trans_RFr:
649 return _trans_rotation(RFr, c);
650 case _trans_RDr:
651 return _trans_rotation(RDr, c);
652 case _trans_RBr:
653 return _trans_rotation(RBr, c);
654 case _trans_LUr:
655 return _trans_rotation(LUr, c);
656 case _trans_LFr:
657 return _trans_rotation(LFr, c);
658 case _trans_LDr:
659 return _trans_rotation(LDr, c);
660 case _trans_LBr:
661 return _trans_rotation(LBr, c);
662 case _trans_FUr:
663 return _trans_rotation(FUr, c);
664 case _trans_FRr:
665 return _trans_rotation(FRr, c);
666 case _trans_FDr:
667 return _trans_rotation(FDr, c);
668 case _trans_FLr:
669 return _trans_rotation(FLr, c);
670 case _trans_BUr:
671 return _trans_rotation(BUr, c);
672 case _trans_BRr:
673 return _trans_rotation(BRr, c);
674 case _trans_BDr:
675 return _trans_rotation(BDr, c);
676 case _trans_BLr:
677 return _trans_rotation(BLr, c);
678 case _trans_UFm:
679 return _trans_mirrored(UFm, c);
680 case _trans_ULm:
681 return _trans_mirrored(ULm, c);
682 case _trans_UBm:
683 return _trans_mirrored(UBm, c);
684 case _trans_URm:
685 return _trans_mirrored(URm, c);
686 case _trans_DFm:
687 return _trans_mirrored(DFm, c);
688 case _trans_DLm:
689 return _trans_mirrored(DLm, c);
690 case _trans_DBm:
691 return _trans_mirrored(DBm, c);
692 case _trans_DRm:
693 return _trans_mirrored(DRm, c);
694 case _trans_RUm:
695 return _trans_mirrored(RUm, c);
696 case _trans_RFm:
697 return _trans_mirrored(RFm, c);
698 case _trans_RDm:
699 return _trans_mirrored(RDm, c);
700 case _trans_RBm:
701 return _trans_mirrored(RBm, c);
702 case _trans_LUm:
703 return _trans_mirrored(LUm, c);
704 case _trans_LFm:
705 return _trans_mirrored(LFm, c);
706 case _trans_LDm:
707 return _trans_mirrored(LDm, c);
708 case _trans_LBm:
709 return _trans_mirrored(LBm, c);
710 case _trans_FUm:
711 return _trans_mirrored(FUm, c);
712 case _trans_FRm:
713 return _trans_mirrored(FRm, c);
714 case _trans_FDm:
715 return _trans_mirrored(FDm, c);
716 case _trans_FLm:
717 return _trans_mirrored(FLm, c);
718 case _trans_BUm:
719 return _trans_mirrored(BUm, c);
720 case _trans_BRm:
721 return _trans_mirrored(BRm, c);
722 case _trans_BDm:
723 return _trans_mirrored(BDm, c);
724 case _trans_BLm:
725 return _trans_mirrored(BLm, c);
726 default:
727 DBG_LOG("transform error, unknown transformation\n");
728 return zero_fast;
729 }
730}
diff --git a/src/moves.h b/src/moves.h
new file mode 100644
index 0000000..7da6405
--- /dev/null
+++ b/src/moves.h
@@ -0,0 +1,47 @@
1_static_inline bool allowednextmove(uint8_t *, uint8_t);
2_static_inline uint8_t inverse_trans(uint8_t);
3_static_inline uint8_t movebase(uint8_t);
4_static_inline uint8_t moveaxis(uint8_t);
5
6_static bool
7allowednextmove(uint8_t *moves, uint8_t n)
8{
9 uint8_t base[3], axis[3];
10
11 if (n < 2)
12 return true;
13
14 base[0] = movebase(moves[n-1]);
15 axis[0] = moveaxis(moves[n-1]);
16 base[1] = movebase(moves[n-2]);
17 axis[1] = moveaxis(moves[n-2]);
18
19 if (base[0] == base[1] || (axis[0] == axis[1] && base[0] < base[1]))
20 return false;
21
22 if (n == 2)
23 return true;
24
25 base[2] = movebase(moves[n-3]);
26 axis[2] = moveaxis(moves[n-3]);
27
28 return axis[1] != axis[2] || base[0] != base[2];
29}
30
31_static_inline uint8_t
32inverse_trans(uint8_t t)
33{
34 return inverse_trans_table[t];
35}
36
37_static_inline uint8_t
38movebase(uint8_t move)
39{
40 return move / 3;
41}
42
43_static_inline uint8_t
44moveaxis(uint8_t move)
45{
46 return move / 6;
47}
diff --git a/src/solve_generic.h b/src/solve_generic.h
new file mode 100644
index 0000000..925aa33
--- /dev/null
+++ b/src/solve_generic.h
@@ -0,0 +1,259 @@
1typedef struct {
2 cube_fast_t cube;
3 uint8_t depth;
4 int64_t maxsols;
5 char **nextsol;
6 int64_t *nsols;
7 uint8_t nmoves;
8 uint8_t moves[20];
9 uint8_t (*estimate)(cube_fast_t);
10} dfsarg_generic_t;
11
12_static void solve_generic_appendsolution(dfsarg_generic_t *);
13_static int solve_generic_dfs(dfsarg_generic_t *);
14_static int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t,
15 int8_t, char *, uint8_t (*)(cube_fast_t));
16_static uint8_t estimate_simple(cube_fast_t);
17_static int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *);
18
19int64_t
20solve(
21 cube_t cube,
22 const char *solver,
23 const char *options,
24 const char *nisstype,
25 int8_t minmoves,
26 int8_t maxmoves,
27 int64_t maxsols,
28 int8_t optimal,
29 const void *data,
30 char *solutions
31)
32{
33 DBG_WARN(!strcmp(options, ""),
34 "solve: 'options' not implemented yet, ignoring\n");
35
36 DBG_WARN(!strcmp(nisstype, ""),
37 "solve: NISS not implemented yet, ignoring 'nisstype'\n");
38
39 DBG_WARN(data == NULL,
40 "solve: 'data' not implemented yet, ignoring\n");
41
42 if (!strcmp(solver, "optimal") || !strcmp(solver, "simple")) {
43 return solve_simple(
44 cube,
45 minmoves,
46 maxmoves,
47 maxsols,
48 optimal,
49 solutions
50 );
51 } else {
52 DBG_LOG("solve: unknown solver '%s'\n", solver);
53 return -1;
54 }
55
56 DBG_LOG("solve: error\n");
57 return -1;
58}
59
60void
61multisolve(
62 int n,
63 cube_t *cube,
64 const char *solver,
65 const void *data,
66 char *sols
67)
68{
69 char *s;
70 int i;
71
72 s = sols;
73 for (i = 0; i < n; i++) {
74 solve(cube[i], solver, "", "normal", 0, -1, 1, 0, NULL, s);
75 while (s++);
76 }
77}
78
79int64_t
80gendata(const char *solver, void *data)
81{
82 DBG_LOG("gendata: not implemented yet\n");
83
84 return -1;
85}
86
87_static void
88solve_generic_appendsolution(dfsarg_generic_t *arg)
89{
90 int strl;
91
92 strl = writemoves(arg->moves, arg->depth, *arg->nextsol);
93 DBG_LOG("Solution found: %s\n", *arg->nextsol);
94 *arg->nextsol += strl;
95 **arg->nextsol = '\n';
96 (*arg->nextsol)++;
97 (*arg->nsols)++;
98}
99
100_static int
101solve_generic_dfs(dfsarg_generic_t *arg)
102{
103 dfsarg_generic_t nextarg;
104 uint8_t m, bound;
105 int64_t ret;
106
107 if (!allowednextmove(arg->moves, arg->nmoves))
108 return 0;
109
110 if (arg->nmoves > 0)
111 arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]);
112
113 bound = arg->estimate(arg->cube);
114 if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth)
115 return 0;
116
117 if (bound == 0) {
118 if (arg->nmoves != arg->depth)
119 return 0;
120 solve_generic_appendsolution(arg);
121 return 1;
122 }
123
124 /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */
125 nextarg = *arg;
126 nextarg.nmoves = arg->nmoves + 1;
127 for (m = 0, ret = 0; m < 18; m++) {
128 nextarg.cube = arg->cube;
129 nextarg.moves[arg->nmoves] = m;
130 ret += solve_generic_dfs(&nextarg);
131 }
132
133 return ret;
134}
135
136_static int64_t
137solve_generic(
138 cube_t cube,
139 const char *nisstype,
140 /* TODO: handle NISS */
141 int8_t minmoves,
142 int8_t maxmoves,
143 int64_t maxsols,
144 int8_t optimal,
145 char *sols,
146 uint8_t (*estimate)(cube_fast_t)
147 /* TODO: add validator */
148 /* TODO: maybe add data for estimate */
149 /* TODO: add moveset (and allowednext?) */
150)
151{
152 dfsarg_generic_t arg;
153 int64_t ret, tmp, first;
154
155 if (!issolvable(cube)) {
156 DBG_LOG("solve: cube is not solvable\n");
157 return -1;
158 }
159
160 if (issolved(cube)) {
161 DBG_LOG("solve: cube is already solved\n");
162 sols[0] = '\n';
163 sols[1] = 0;
164 return 1;
165 }
166
167 DBG_WARN(!strcmp(nisstype, ""),
168 "solve: NISS not implemented yet, 'nisstype' ignored\n");
169
170 if (minmoves < 0) {
171 DBG_LOG("solve: 'minmoves' is negative, setting to 0\n");
172 minmoves = 0;
173 }
174
175 if (maxmoves < 0) {
176 DBG_LOG("solve: invalid 'maxmoves', setting to 20\n");
177 maxmoves = 20;
178 }
179
180 if (maxsols < 0) {
181 DBG_LOG("solve: 'maxsols' is negative\n");
182 return -1;
183 }
184
185 if (maxsols == 0) {
186 DBG_LOG("solve: 'maxsols' is 0\n");
187 return 0;
188 }
189
190 if (sols == NULL) {
191 DBG_LOG("solve: return parameter 'sols' is NULL\n");
192 return -1;
193 }
194
195 if (estimate == NULL) {
196 DBG_LOG("solve: 'estimate' is NULL\n");
197 return -1;
198 }
199
200 arg = (dfsarg_generic_t) {
201 .cube = cubetofast(cube),
202 .maxsols = maxsols,
203 .nextsol = &sols,
204 .nsols = &ret,
205 .nmoves = 0,
206 .moves = {0},
207 .estimate = estimate,
208 };
209
210 ret = 0;
211 first = -1;
212 for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) {
213 tmp = solve_generic_dfs(&arg);
214 if (tmp != 0)
215 first = arg.depth;
216
217 DBG_LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n",
218 tmp, tmp == 1 ? "" : "s", arg.depth);
219
220 if (ret >= maxsols)
221 break;
222
223 if (optimal >= 0 && first >= 0 && arg.depth - first == optimal)
224 break;
225 }
226
227 DBG_ASSERT(ret <= maxsols, ret,
228 "solve: found more than 'maxsols' solutions\n");
229
230 return ret;
231}
232
233_static uint8_t
234estimate_simple(cube_fast_t cube)
235{
236 return issolved_fast(cube) ? 0 : 1;
237}
238
239_static int64_t
240solve_simple(
241 cube_t cube,
242 int8_t minmoves,
243 int8_t maxmoves,
244 int64_t maxsols,
245 int8_t optimal,
246 char *solutions
247)
248{
249 return solve_generic(
250 cube,
251 "",
252 minmoves,
253 maxmoves,
254 maxsols,
255 optimal,
256 solutions,
257 &estimate_simple
258 );
259}
diff --git a/src/solve_h48.h b/src/solve_h48.h
new file mode 100644
index 0000000..84bea31
--- /dev/null
+++ b/src/solve_h48.h
@@ -0,0 +1,266 @@
1#define _esep_ind(i) (i / 8U)
2#define _esep_shift(i) (4U * (i % 8U))
3#define _esep_mask(i) (((1U << 4U) - 1U) << _esep_shift(i))
4#define _visited_ind(i) (i / 8U)
5#define _visited_mask(i) (1U << (i % 8U))
6
7typedef struct {
8 cube_fast_t cube;
9 uint8_t *visited;
10 uint8_t *moves;
11 uint8_t nmoves;
12 uint8_t depth;
13 uint16_t *nclasses;
14 uint32_t *cocsepdata;
15 uint32_t *buf32;
16} dfsarg_gendata_t;
17
18_static_inline int64_t coord_h48(cube_fast_t, uint32_t *, uint8_t);
19
20_static size_t gendata_cocsep(void *);
21_static uint32_t gendata_cocsep_dfs( /* TODO: use dfsarg */
22 cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *, uint8_t *);
23
24_static size_t gendata_esep(const void *, void *);
25_static uint32_t gendata_esep_dfs(dfsarg_gendata_t *);
26
27_static_inline bool get_visited(const uint8_t *, int64_t);
28_static_inline void set_visited(uint8_t *, int64_t);
29_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
30_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
31
32/* h is the number of eo bits used */
33_static_inline int64_t
34coord_h48(cube_fast_t c, uint32_t *cocsepdata, uint8_t h)
35{
36 cube_fast_t d;
37 int64_t cocsep, coclass, esep, eo, esize, ret;
38 uint32_t data;
39 uint8_t ttrep;
40
41 DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n");
42
43 cocsep = coord_fast_cocsep(c);
44 data = cocsepdata[cocsep];
45 coclass = (data & (0xFFFFU << 16U)) >> 16U;
46 ttrep = (data & (0xFFU << 8U)) >> 8U;
47
48 d = transform(c, ttrep); /* TODO: transform only edges */
49 esep = coord_fast_esep(d);
50 eo = coord_fast_eo(d);
51
52 esize = (_12c4 * _8c4) << h;
53 ret = (coclass * esize) + (esep << h) + (eo >> (11-h));
54
55 return ret;
56}
57
58/*
59Each element of the cocsep table is a uint32_t used as follows:
60 - Lowest 8-bit block: pruning value
61 - Second-lower 8-bit block: "ttrep" (transformation to representative)
62 - Top 16-bit block: symcoord value
63After the data as described above, more auxiliary information is appended:
64 - A uint32_t representing the number of symmetry classes
65 - A uint32_t representing the highest value of the pruning table
66 - One uint32_t for each "line" of the pruning table, representing the number
67 of positions having that pruning value.
68*/
69_static size_t
70gendata_cocsep(void *buf)
71{
72 size_t tablesize = _3p7 << 7U;
73 size_t visitedsize = (tablesize + 7U) / 8U;
74 size_t infosize = 12;
75
76 cube_fast_t solved;
77 uint32_t *buf32, *info, cc;
78 uint16_t n;
79 uint8_t i, j, visited[visitedsize];
80
81 buf32 = (uint32_t *)buf;
82 info = buf32 + tablesize;
83 memset(buf32, 0xFFU, 4*tablesize);
84 memset(info, 0, 4*infosize);
85
86 solved = cubetofast(solvedcube());
87 for (i = 0, n = 0, cc = 0; i < 10; i++) {
88 memset(visited, 0, visitedsize);
89 DBG_LOG("cocsep: generating depth %" PRIu8 "\n", i);
90 cc = gendata_cocsep_dfs(solved, 0, i, &n, buf32, visited);
91 info[i+2] = cc;
92 DBG_LOG("found %" PRIu32 "\n", cc);
93 }
94
95 info[0] = (uint32_t)n;
96 info[1] = 9U; /* Known max pruning value */
97 DBG_ASSERT(n == COCSEP_CLASSES, 0,
98 "cocsep: computed %" PRIu16 " symmetry classes, "
99 "expected %" PRIu16 "\n", n, COCSEP_CLASSES);
100
101 DBG_LOG("cocsep data computed\n");
102 DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]);
103 DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[1]);
104 DBG_LOG("Pruning value distribution:\n");
105 for (j = 0; j < 10; j++)
106 DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+2]);
107
108 return 4*(tablesize + infosize);
109}
110
111_static uint32_t
112gendata_cocsep_dfs(
113 cube_fast_t c,
114 uint8_t depth,
115 uint8_t maxdepth,
116 uint16_t *n,
117 uint32_t *buf32,
118 uint8_t *visited
119)
120{
121 uint8_t m, t, tinv, olddepth;
122 uint32_t cc;
123 int64_t i;
124 cube_fast_t d;
125
126 i = coord_fast_cocsep(c);
127 olddepth = (uint8_t)(buf32[i] & 0xFFU);
128 if (olddepth < depth || get_visited(visited, i))
129 return 0;
130 set_visited(visited, i);
131
132 if (depth == maxdepth) {
133 if ((buf32[i] & 0xFFU) != 0xFFU)
134 return 0;
135
136 for (t = 0, cc = 0; t < 48; t++) {
137 d = transform(c, t);
138 i = coord_fast_cocsep(d);
139 set_visited(visited, i);
140 tinv = inverse_trans(t);
141 cc += (buf32[i] & 0xFFU) == 0xFFU;
142 buf32[i] = (*n << 16U) | (tinv << 8U) | depth;
143 }
144 (*n)++;
145
146 return cc;
147 }
148
149 for (m = 0, cc = 0; m < 18; m++) {
150 d = move(c, m);
151 cc += gendata_cocsep_dfs(d, depth+1, maxdepth, n, buf32, visited);
152 }
153
154 return cc;
155}
156
157/*
158TODO description
159generating fixed table with h=0, k=4
160*/
161_static size_t
162gendata_esep(const void *cocsepdata, void *buf)
163{
164 size_t tablesize = (COCSEP_CLASSES * _12c4 * _8c4) / 2U;
165 size_t visitedsize = (tablesize * 2U + 7U) / 8U;
166 size_t infosize = 25; /* TODO unknown yet */
167
168 uint32_t *buf32, *info, cc;
169 uint8_t moves[20];
170 dfsarg_gendata_t arg;
171
172 arg.visited = malloc(visitedsize);
173 buf32 = (uint32_t *)buf;
174 info = buf32 + tablesize;
175 memset(buf32, 0xFFU, 4*tablesize);
176 memset(info, 0, 4*infosize);
177
178 arg.cube = cubetofast(solvedcube());
179 arg.moves = moves;
180 arg.nmoves = 0;
181 arg.cocsepdata = (uint32_t *)cocsepdata;
182 arg.buf32 = buf32;
183 /* TODO loop until no more is done, not until 12! (or hardcode limits)*/
184 for (arg.depth = 0, cc = 0; arg.depth < 12; arg.depth++) {
185 DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
186 memset(arg.visited, 0, visitedsize);
187 cc = gendata_esep_dfs(&arg);
188 info[arg.depth+1] = cc;
189 DBG_LOG("found %" PRIu32 "\n", cc);
190 }
191 free(arg.visited);
192
193 return cc;
194}
195
196_static uint32_t
197gendata_esep_dfs(dfsarg_gendata_t *arg)
198{
199 uint8_t m, t, olddepth;
200 uint32_t cc;
201 uint64_t i;
202 cube_fast_t d;
203 dfsarg_gendata_t nextarg;
204
205 if (!allowednextmove(arg->moves, arg->nmoves))
206 return 0;
207
208 if (arg->nmoves > 0)
209 arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]);
210
211 i = coord_h48(arg->cube, arg->cocsepdata, 0U);
212 olddepth = get_esep_pval(arg->buf32, i);
213
214 if (olddepth < arg->nmoves || get_visited(arg->visited, i))
215 return 0;
216 set_visited(arg->visited, i);
217
218 if (arg->nmoves == arg->depth) {
219 if (olddepth != 15U)
220 return 0;
221
222 for (t = 0, cc = 0; t < 48; t++) {
223 d = transform(arg->cube, t);
224 i = coord_h48(d, arg->cocsepdata, 0U);
225 set_visited(arg->visited, i);
226 cc += get_esep_pval(arg->buf32, i) == 15U;
227 set_esep_pval(arg->buf32, i, arg->depth);
228 }
229
230 return cc;
231 }
232
233
234 nextarg = *arg;
235 nextarg.nmoves = arg->nmoves + 1;
236 for (m = 0, cc = 0; m < 18; m++) {
237 nextarg.cube = arg->cube;
238 nextarg.moves[arg->nmoves] = m;
239 cc += gendata_esep_dfs(&nextarg);
240 }
241
242 return cc;
243}
244
245_static_inline bool get_visited(const uint8_t *a, int64_t i)
246{
247 return a[_visited_ind(i)] & _visited_mask(i);
248}
249
250_static_inline void set_visited(uint8_t *a, int64_t i)
251{
252 a[_visited_ind(i)] |= _visited_mask(i);
253}
254
255_static_inline uint8_t
256get_esep_pval(const uint32_t *buf32, int64_t i)
257{
258 return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i);
259}
260
261_static_inline void
262set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
263{
264 buf32[_esep_ind(i)] =
265 (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i));
266}

Generated with cgit - Back to sebastiano.tronto.net