aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Makefile10
-rw-r--r--README.md22
-rw-r--r--config.mk7
-rwxr-xr-xconfigure.sh18
-rw-r--r--src/_base_arr.c30
-rw-r--r--src/_base_avx2.c28
-rw-r--r--src/_constants.c7
-rw-r--r--src/_move_logic_arr.c149
-rw-r--r--src/_move_logic_avx2.c3
-rw-r--r--src/_trans_move_avx2.c2
-rw-r--r--src/cube.c296
-rw-r--r--src/cube.h10
12 files changed, 359 insertions, 223 deletions
diff --git a/Makefile b/Makefile
index 7459910..54848ac 100644
--- a/Makefile
+++ b/Makefile
@@ -1,15 +1,5 @@
1# See LICENSE file for copyright and license details.
2
3include config.mk 1include config.mk
4 2
5CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra \
6 -Wno-unused-parameter -O3
7DBGFLAGS = -DDEBUG -std=c99 -pthread -pedantic -Wall -Wextra \
8 -Wno-unused-parameter -Wno-unused-function -g3 \
9 -fsanitize=address -fsanitize=undefined
10
11CC = cc
12
13all: cube.o debugcube.o 3all: cube.o debugcube.o
14 4
15cube.o: clean 5cube.o: clean
diff --git a/README.md b/README.md
index 08defe2..cff5110 100644
--- a/README.md
+++ b/README.md
@@ -2,18 +2,32 @@
2 2
3Work in progress. 3Work in progress.
4 4
5TODO: 5## Running tests
6
7```
8$ ./configure.sh # Run 'TYPE=AVX2 ./configure.sh' to use AVX2 instead
9$ make test
10```
11
12## TODO:
13
14### AVX2
15
16* static `solvedcube` and co don't work, turn into functions?
17* implement missing stuff (moves, transform)
18* optimize things that use _base functions
19
20### More features
6 21
7* AVX2 compile-time switch
8* coordinates: co, eo, epsep, cpsep_sym, cocpsep_sym, cphtr_sym, cocphtr_sym 22* coordinates: co, eo, epsep, cpsep_sym, cocpsep_sym, cphtr_sym, cocphtr_sym
9* pruning tables (1 bit per entry + fallback) 23* pruning tables (1 bit per entry + fallback)
10* solve.c 24* solve.c
11 25
12Optimizations: 26### Optimizations:
13 27
14* multi-move (up to 4/5 moves at once) 28* multi-move (up to 4/5 moves at once)
15 29
16Things I need to learn: 30### Things I need to learn:
17 31
18* Use AVX2 instructions, in particular 32* Use AVX2 instructions, in particular
19 [_mm256_shuffle_epi8](https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-10/mm256-shuffle-epi8.html)) 33 [_mm256_shuffle_epi8](https://www.intel.com/content/www/us/en/docs/cpp-compiler/developer-guide-reference/2021-10/mm256-shuffle-epi8.html))
diff --git a/config.mk b/config.mk
index f71c9a5..bf99225 100644
--- a/config.mk
+++ b/config.mk
@@ -1 +1,6 @@
1CUBETYPE = CUBE_$(TYPE) 1CUBETYPE = CUBE_
2
3CFLAGS = -std=c99 -pthread -pedantic -Wall -Wextra -Wno-unused-parameter -O3
4DBGFLAGS = -DDEBUG -std=c99 -pthread -pedantic -Wall -Wextra -Wno-unused-parameter -Wno-unused-function -g3 -fsanitize=address -fsanitize=undefined
5
6CC = cc
diff --git a/configure.sh b/configure.sh
new file mode 100755
index 0000000..17673fc
--- /dev/null
+++ b/configure.sh
@@ -0,0 +1,18 @@
1#!/bin/sh
2
3CFLAGS="-std=c99 -pthread -pedantic -Wall -Wextra -Wno-unused-parameter -O3"
4DBGFLAGS="-DDEBUG -std=c99 -pthread -pedantic -Wall -Wextra -Wno-unused-parameter -Wno-unused-function -g3 -fsanitize=address -fsanitize=undefined"
5
6if [ "$TYPE" = "AVX2" ]; then
7 CFLAGS="$CFLAGS -mavx2"
8 DBGFLAGS="$DBGFLAGS -mavx2"
9fi
10
11{
12echo "CUBETYPE = CUBE_$TYPE";
13echo "";
14echo "CFLAGS = $CFLAGS";
15echo "DBGFLAGS = $DBGFLAGS";
16echo "";
17echo "CC = cc"
18} > config.mk
diff --git a/src/_base_arr.c b/src/_base_arr.c
new file mode 100644
index 0000000..2169cd5
--- /dev/null
+++ b/src/_base_arr.c
@@ -0,0 +1,30 @@
1cube_t solvedcube = {
2 .c = {0, 1, 2, 3, 4, 5, 6, 7},
3 .e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
4};
5static cube_t errorcube = { .e = {0}, .c = {0} };
6static cube_t zerocube = { .e = {0}, .c = {0} };
7
8static uint8_t
9get_edge(cube_t c, uint8_t i)
10{
11 return c.e[i];
12}
13
14static uint8_t
15get_corner(cube_t c, uint8_t i)
16{
17 return c.c[i];
18}
19
20static void
21set_edge(cube_t *c, uint8_t i, uint8_t p)
22{
23 c->e[i] = p;
24}
25
26static void
27set_corner(cube_t *c, uint8_t i, uint8_t p)
28{
29 c->c[i] = p;
30}
diff --git a/src/_base_avx2.c b/src/_base_avx2.c
new file mode 100644
index 0000000..7af88eb
--- /dev/null
+++ b/src/_base_avx2.c
@@ -0,0 +1,28 @@
1#define solvedcube _mm256_set_epi8( \
2 0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 5, 4, 3, 2, 1, 0, /* Corners */ \
3 0, 0, 0, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 /* Edges */ \
4)
5#define errorcube _mm256_setzero_si256()
6#define zerocube _mm256_setzero_si256()
7
8static uint8_t
9get_edge(cube_t c, uint8_t i)
10{
11 return 0;
12}
13
14static uint8_t
15get_corner(cube_t c, uint8_t i)
16{
17 return 0;
18}
19
20static void
21set_edge(cube_t *c, uint8_t i, uint8_t p)
22{
23}
24
25static void
26set_corner(cube_t *c, uint8_t i, uint8_t p)
27{
28}
diff --git a/src/_constants.c b/src/_constants.c
index 90deffe..3121e3b 100644
--- a/src/_constants.c
+++ b/src/_constants.c
@@ -104,13 +104,6 @@ trans_t inverse_trans[] = {
104 [BRm] = RDm, 104 [BRm] = RDm,
105}; 105};
106 106
107cube_t solvedcube = {
108 .c = {0, 1, 2, 3, 4, 5, 6, 7},
109 .e = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
110};
111
112static cube_t errorcube = { .e = {0}, .c = {0} };
113
114static char *cornerstr[] = { 107static char *cornerstr[] = {
115 [_c_ufr] = "UFR", 108 [_c_ufr] = "UFR",
116 [_c_ubl] = "UBL", 109 [_c_ubl] = "UBL",
diff --git a/src/_move_logic_arr.c b/src/_move_logic_arr.c
new file mode 100644
index 0000000..d8aec10
--- /dev/null
+++ b/src/_move_logic_arr.c
@@ -0,0 +1,149 @@
1#define PERM4(r, i, j, k, l) \
2 aux = r[i]; \
3 r[i] = r[l]; \
4 r[l] = r[k]; \
5 r[k] = r[j]; \
6 r[j] = aux;
7#define PERM22(r, i, j, k, l) \
8 aux = r[i]; \
9 r[i] = r[j]; \
10 r[j] = aux; \
11 aux = r[k]; \
12 r[k] = r[l]; \
13 r[l] = aux;
14#define CO(a, b) \
15 aux = (a & _cobits) + (b & _cobits); \
16 auy = (aux + _ctwist_cw) >> 2U; \
17 auz = (aux + auy) & _cobits2; \
18 a = (a & _pbits) | auz;
19#define CO4(r, i, j, k, l) \
20 CO(r[i], _ctwist_cw) \
21 CO(r[j], _ctwist_cw) \
22 CO(r[k], _ctwist_ccw) \
23 CO(r[l], _ctwist_ccw)
24#define EO4(r, i, j, k, l) \
25 r[i] ^= _eobit; \
26 r[j] ^= _eobit; \
27 r[k] ^= _eobit; \
28 r[l] ^= _eobit;
29
30uint8_t aux, auy, auz;
31cube_t ret = c;
32
33switch (m) {
34case U:
35 PERM4(ret.e, _e_uf, _e_ul, _e_ub, _e_ur)
36 PERM4(ret.c, _c_ufr, _c_ufl, _c_ubl, _c_ubr)
37
38 return ret;
39case U2:
40 PERM22(ret.e, _e_uf, _e_ub, _e_ul, _e_ur)
41 PERM22(ret.c, _c_ufr, _c_ubl, _c_ufl, _c_ubr)
42
43 return ret;
44case U3:
45 PERM4(ret.e, _e_uf, _e_ur, _e_ub, _e_ul)
46 PERM4(ret.c, _c_ufr, _c_ubr, _c_ubl, _c_ufl)
47
48 return ret;
49case D:
50 PERM4(ret.e, _e_df, _e_dr, _e_db, _e_dl)
51 PERM4(ret.c, _c_dfr, _c_dbr, _c_dbl, _c_dfl)
52
53 return ret;
54case D2:
55 PERM22(ret.e, _e_df, _e_db, _e_dr, _e_dl)
56 PERM22(ret.c, _c_dfr, _c_dbl, _c_dbr, _c_dfl)
57
58 return ret;
59case D3:
60 PERM4(ret.e, _e_df, _e_dl, _e_db, _e_dr)
61 PERM4(ret.c, _c_dfr, _c_dfl, _c_dbl, _c_dbr)
62
63 return ret;
64case R:
65 PERM4(ret.e, _e_ur, _e_br, _e_dr, _e_fr)
66 PERM4(ret.c, _c_ufr, _c_ubr, _c_dbr, _c_dfr)
67
68 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
69
70 return ret;
71case R2:
72 PERM22(ret.e, _e_ur, _e_dr, _e_fr, _e_br)
73 PERM22(ret.c, _c_ufr, _c_dbr, _c_ubr, _c_dfr)
74
75 return ret;
76case R3:
77 PERM4(ret.e, _e_ur, _e_fr, _e_dr, _e_br)
78 PERM4(ret.c, _c_ufr, _c_dfr, _c_dbr, _c_ubr)
79
80 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
81
82 return ret;
83case L:
84 PERM4(ret.e, _e_ul, _e_fl, _e_dl, _e_bl)
85 PERM4(ret.c, _c_ufl, _c_dfl, _c_dbl, _c_ubl)
86
87 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
88
89 return ret;
90case L2:
91 PERM22(ret.e, _e_ul, _e_dl, _e_fl, _e_bl)
92 PERM22(ret.c, _c_ufl, _c_dbl, _c_ubl, _c_dfl)
93
94 return ret;
95case L3:
96 PERM4(ret.e, _e_ul, _e_bl, _e_dl, _e_fl)
97 PERM4(ret.c, _c_ufl, _c_ubl, _c_dbl, _c_dfl)
98
99 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
100
101 return ret;
102case F:
103 PERM4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
104 PERM4(ret.c, _c_ufr, _c_dfr, _c_dfl, _c_ufl)
105
106 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
107 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
108
109 return ret;
110case F2:
111 PERM22(ret.e, _e_uf, _e_df, _e_fr, _e_fl)
112 PERM22(ret.c, _c_ufr, _c_dfl, _c_ufl, _c_dfr)
113
114 return ret;
115case F3:
116 PERM4(ret.e, _e_uf, _e_fl, _e_df, _e_fr)
117 PERM4(ret.c, _c_ufr, _c_ufl, _c_dfl, _c_dfr)
118
119 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
120 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
121
122 return ret;
123case B:
124 PERM4(ret.e, _e_ub, _e_bl, _e_db, _e_br)
125 PERM4(ret.c, _c_ubr, _c_ubl, _c_dbl, _c_dbr)
126
127 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
128 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
129
130 return ret;
131case B2:
132 PERM22(ret.e, _e_ub, _e_db, _e_br, _e_bl)
133 PERM22(ret.c, _c_ubr, _c_dbl, _c_ubl, _c_dbr)
134
135 return ret;
136case B3:
137 PERM4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
138 PERM4(ret.c, _c_ubr, _c_dbr, _c_dbl, _c_ubl)
139
140 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
141 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
142
143 return ret;
144default:
145#ifdef DEBUG
146 fprintf(stderr, "mover error, unknown move\n");
147#endif
148 goto move_error;
149}
diff --git a/src/_move_logic_avx2.c b/src/_move_logic_avx2.c
new file mode 100644
index 0000000..7bf881c
--- /dev/null
+++ b/src/_move_logic_avx2.c
@@ -0,0 +1,3 @@
1static cube_t move_cube[18]; /* TODO */
2
3return compose(move_cube[m], c);
diff --git a/src/_trans_move_avx2.c b/src/_trans_move_avx2.c
new file mode 100644
index 0000000..38b825e
--- /dev/null
+++ b/src/_trans_move_avx2.c
@@ -0,0 +1,2 @@
1static cube_t trans_move_cube[48];
2static cube_t trans_move_cube_inverse[48];
diff --git a/src/cube.c b/src/cube.c
index 1e27de9..4651b00 100644
--- a/src/cube.c
+++ b/src/cube.c
@@ -2,6 +2,10 @@
2#include <stdbool.h> 2#include <stdbool.h>
3#include <string.h> 3#include <string.h>
4 4
5#ifdef CUBE_AVX2
6#include <immintrin.h>
7#endif
8
5#ifdef DEBUG 9#ifdef DEBUG
6#include <stdio.h> 10#include <stdio.h>
7#endif 11#endif
@@ -10,6 +14,12 @@
10 14
11#include "_constants.c" 15#include "_constants.c"
12 16
17#ifdef CUBE_AVX2
18#include "_base_avx2.c"
19#else
20#include "_base_arr.c"
21#endif
22
13static bool isconsistent(cube_t); 23static bool isconsistent(cube_t);
14static cube_t flipallcorners(cube_t); 24static cube_t flipallcorners(cube_t);
15static uint8_t readco(char *); 25static uint8_t readco(char *);
@@ -90,7 +100,7 @@ readcube_H48(char *buf)
90{ 100{
91 int i; 101 int i;
92 uint8_t piece, orient; 102 uint8_t piece, orient;
93 cube_t ret = {0}; 103 cube_t ret = zerocube;
94 char *b = buf; 104 char *b = buf;
95 105
96 for (i = 0; i < 12; i++) { 106 for (i = 0; i < 12; i++) {
@@ -102,7 +112,7 @@ readcube_H48(char *buf)
102 if ((orient = readeo(b)) == _error) 112 if ((orient = readeo(b)) == _error)
103 return errorcube; 113 return errorcube;
104 b++; 114 b++;
105 ret.e[i] = piece | orient; 115 set_edge(&ret, i, piece | orient);
106 } 116 }
107 for (i = 0; i < 8; i++) { 117 for (i = 0; i < 8; i++) {
108 while (*b == ' ' || *b == '\t' || *b == '\n') 118 while (*b == ' ' || *b == '\t' || *b == '\n')
@@ -113,7 +123,7 @@ readcube_H48(char *buf)
113 if ((orient = readco(b)) == _error) 123 if ((orient = readco(b)) == _error)
114 return errorcube; 124 return errorcube;
115 b++; 125 b++;
116 ret.c[i] = piece | orient; 126 set_corner(&ret, i, piece | orient);
117 } 127 }
118 128
119 return ret; 129 return ret;
@@ -145,23 +155,25 @@ readcube(format_t format, char *buf)
145static void 155static void
146writecube_H48(cube_t cube, char *buf) 156writecube_H48(cube_t cube, char *buf)
147{ 157{
148 uint8_t piece, orient; 158 uint8_t piece, perm, orient;
149 int i; 159 int i;
150 160
151 for (i = 0; i < 12; i++) { 161 for (i = 0; i < 12; i++) {
152 piece = cube.e[i] & _pbits; 162 piece = get_edge(cube, i);
153 orient = (cube.e[i] & _eobit) >> _eoshift; 163 perm = piece & _pbits;
154 buf[4*i ] = edgestr[piece][0]; 164 orient = (piece & _eobit) >> _eoshift;
155 buf[4*i + 1] = edgestr[piece][1]; 165 buf[4*i ] = edgestr[perm][0];
166 buf[4*i + 1] = edgestr[perm][1];
156 buf[4*i + 2] = orient + '0'; 167 buf[4*i + 2] = orient + '0';
157 buf[4*i + 3] = ' '; 168 buf[4*i + 3] = ' ';
158 } 169 }
159 for (i = 0; i < 8; i++) { 170 for (i = 0; i < 8; i++) {
160 piece = cube.c[i] & _pbits; 171 piece = get_corner(cube, i);
161 orient = (cube.c[i] & _cobits) >> _coshift; 172 perm = piece & _pbits;
162 buf[48 + 5*i ] = cornerstr[piece][0]; 173 orient = (piece & _cobits) >> _coshift;
163 buf[48 + 5*i + 1] = cornerstr[piece][1]; 174 buf[48 + 5*i ] = cornerstr[perm][0];
164 buf[48 + 5*i + 2] = cornerstr[piece][2]; 175 buf[48 + 5*i + 1] = cornerstr[perm][1];
176 buf[48 + 5*i + 2] = cornerstr[perm][2];
165 buf[48 + 5*i + 3] = orient + '0'; 177 buf[48 + 5*i + 3] = orient + '0';
166 buf[48 + 5*i + 4] = ' '; 178 buf[48 + 5*i + 4] = ' ';
167 } 179 }
@@ -196,18 +208,23 @@ static void
196writecube_SRC(cube_t cube, char *buf) 208writecube_SRC(cube_t cube, char *buf)
197{ 209{
198 int i, ptr; 210 int i, ptr;
211 uint8_t piece;
199 212
200 memcpy(buf, "{\n\t.c = {", 9); 213 memcpy(buf, "{\n\t.c = {", 9);
201 ptr = 9; 214 ptr = 9;
202 215
203 for (i = 0; i < 8; i++) 216 for (i = 0; i < 8; i++) {
204 ptr += writepiece_SRC(cube.c[i], buf + ptr); 217 piece = get_corner(cube, i);
218 ptr += writepiece_SRC(piece, buf + ptr);
219 }
205 220
206 memcpy(buf+ptr-2, "},\n\t.e = {", 10); 221 memcpy(buf+ptr-2, "},\n\t.e = {", 10);
207 ptr += 8; 222 ptr += 8;
208 223
209 for (i = 0; i < 12; i++) 224 for (i = 0; i < 12; i++) {
210 ptr += writepiece_SRC(cube.e[i], buf + ptr); 225 piece = get_edge(cube, i);
226 ptr += writepiece_SRC(piece, buf + ptr);
227 }
211 228
212 memcpy(buf+ptr-2, "}\n}\0", 4); 229 memcpy(buf+ptr-2, "}\n}\0", 4);
213} 230}
@@ -364,7 +381,7 @@ permsign(uint8_t *a, int n)
364 381
365 for (i = 0; i < n; i++) 382 for (i = 0; i < n; i++)
366 for (j = i+1; j < n; j++) 383 for (j = i+1; j < n; j++)
367 ret += (a[i] & _pbits) > (a[j] & _pbits) ? 1 : 0; 384 ret += a[i] > a[j] ? 1 : 0;
368 385
369 return ret % 2; 386 return ret % 2;
370} 387}
@@ -372,14 +389,15 @@ permsign(uint8_t *a, int n)
372static bool 389static bool
373isconsistent(cube_t c) 390isconsistent(cube_t c)
374{ 391{
375 uint8_t i, p, e; 392 uint8_t i, p, e, piece;
376 bool found[12]; 393 bool found[12];
377 394
378 for (i = 0; i < 12; i++) 395 for (i = 0; i < 12; i++)
379 found[i] = false; 396 found[i] = false;
380 for (i = 0; i < 12; i++) { 397 for (i = 0; i < 12; i++) {
381 p = c.e[i] & _pbits; 398 piece = get_edge(c, i);
382 e = c.e[i] & ~_pbits; 399 p = piece & _pbits;
400 e = piece & _eobit;
383 if (p >= 12) 401 if (p >= 12)
384 goto inconsistent_ep; 402 goto inconsistent_ep;
385 if (e != 0 && e != _eobit) 403 if (e != 0 && e != _eobit)
@@ -393,8 +411,9 @@ isconsistent(cube_t c)
393 for (i = 0; i < 8; i++) 411 for (i = 0; i < 8; i++)
394 found[i] = false; 412 found[i] = false;
395 for (i = 0; i < 8; i++) { 413 for (i = 0; i < 8; i++) {
396 p = c.c[i] & _pbits; 414 piece = get_corner(c, i);
397 e = c.c[i] & ~_pbits; 415 p = piece & _pbits;
416 e = piece & _cobits;
398 if (p >= 8) 417 if (p >= 8)
399 goto inconsistent_cp; 418 goto inconsistent_cp;
400 if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw) 419 if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw)
@@ -432,7 +451,7 @@ inconsistent_co:
432bool 451bool
433issolvable(cube_t cube) 452issolvable(cube_t cube)
434{ 453{
435 int8_t i, eo, co; 454 uint8_t i, eo, co, piece, e[12], c[8];
436 455
437#ifdef DEBUG 456#ifdef DEBUG
438 if (!isconsistent(cube)) { 457 if (!isconsistent(cube)) {
@@ -441,18 +460,27 @@ issolvable(cube_t cube)
441 } 460 }
442#endif 461#endif
443 462
444 if (permsign(cube.e, 12) != permsign(cube.c, 8)) 463 for (i = 0; i < 12; i++)
464 e[i] = get_edge(cube, i) & _pbits;
465 for (i = 0; i < 8; i++)
466 c[i] = get_corner(cube, i) & _pbits;
467
468 if (permsign(e, 12) != permsign(c, 8))
445 goto issolvable_parity; 469 goto issolvable_parity;
446 470
447 eo = 0; 471 eo = 0;
448 for (i = 0; i < 12; i++) 472 for (i = 0; i < 12; i++) {
449 eo += (cube.e[i] & _eobit) >> _eoshift; 473 piece = get_edge(cube, i);
474 eo += (piece & _eobit) >> _eoshift;
475 }
450 if (eo % 2 != 0) 476 if (eo % 2 != 0)
451 goto issolvable_eo; 477 goto issolvable_eo;
452 478
453 co = 0; 479 co = 0;
454 for (i = 0; i < 8; i++) 480 for (i = 0; i < 8; i++) {
455 co += (cube.c[i] & _cobits) >> _coshift; 481 piece = get_corner(cube, i);
482 co += (piece & _cobits) >> _coshift;
483 }
456 if (co % 3 != 0) 484 if (co % 3 != 0)
457 goto issolvable_co; 485 goto issolvable_co;
458 486
@@ -478,6 +506,15 @@ issolvable_co:
478bool 506bool
479equal(cube_t cube1, cube_t cube2) 507equal(cube_t cube1, cube_t cube2)
480{ 508{
509#ifdef CUBE_AVX2
510 uint32_t mask;
511 __m256i cmp;
512
513 cmp = _mm256_cmpeq_epi8(cube1, cube2);
514 mask = _mm256_movemask_epi8(cmp);
515
516 return mask == 0xffffffffU;
517#else
481 uint8_t i; 518 uint8_t i;
482 519
483 for (i = 0; i < 12; i++) 520 for (i = 0; i < 12; i++)
@@ -489,6 +526,7 @@ equal(cube_t cube1, cube_t cube2)
489 return false; 526 return false;
490 527
491 return true; 528 return true;
529#endif
492} 530}
493 531
494bool 532bool
@@ -506,9 +544,6 @@ iserror(cube_t cube)
506cube_t 544cube_t
507move(cube_t c, move_t m) 545move(cube_t c, move_t m)
508{ 546{
509 cube_t ret;
510 uint8_t aux, auy, auz;
511
512#ifdef DEBUG 547#ifdef DEBUG
513 if (!isconsistent(c)) { 548 if (!isconsistent(c)) {
514 fprintf(stderr, "move error, inconsistent cube\n"); 549 fprintf(stderr, "move error, inconsistent cube\n");
@@ -516,154 +551,11 @@ move(cube_t c, move_t m)
516 } 551 }
517#endif 552#endif
518 553
519#define PERM4(r, i, j, k, l) \ 554#ifdef CUBE_AVX2
520 aux = r[i]; \ 555#include "_move_logic_avx2.c"
521 r[i] = r[l]; \ 556#else
522 r[l] = r[k]; \ 557#include "_move_logic_arr.c"
523 r[k] = r[j]; \
524 r[j] = aux;
525#define PERM22(r, i, j, k, l) \
526 aux = r[i]; \
527 r[i] = r[j]; \
528 r[j] = aux; \
529 aux = r[k]; \
530 r[k] = r[l]; \
531 r[l] = aux;
532#define CO(a, b) \
533 aux = (a & _cobits) + (b & _cobits); \
534 auy = (aux + _ctwist_cw) >> 2U; \
535 auz = (aux + auy) & _cobits2; \
536 a = (a & _pbits) | auz;
537#define CO4(r, i, j, k, l) \
538 CO(r[i], _ctwist_cw) \
539 CO(r[j], _ctwist_cw) \
540 CO(r[k], _ctwist_ccw) \
541 CO(r[l], _ctwist_ccw)
542#define EO4(r, i, j, k, l) \
543 r[i] ^= _eobit; \
544 r[j] ^= _eobit; \
545 r[k] ^= _eobit; \
546 r[l] ^= _eobit;
547
548 ret = c;
549
550 switch (m) {
551 case U:
552 PERM4(ret.e, _e_uf, _e_ul, _e_ub, _e_ur)
553 PERM4(ret.c, _c_ufr, _c_ufl, _c_ubl, _c_ubr)
554
555 return ret;
556 case U2:
557 PERM22(ret.e, _e_uf, _e_ub, _e_ul, _e_ur)
558 PERM22(ret.c, _c_ufr, _c_ubl, _c_ufl, _c_ubr)
559
560 return ret;
561 case U3:
562 PERM4(ret.e, _e_uf, _e_ur, _e_ub, _e_ul)
563 PERM4(ret.c, _c_ufr, _c_ubr, _c_ubl, _c_ufl)
564
565 return ret;
566 case D:
567 PERM4(ret.e, _e_df, _e_dr, _e_db, _e_dl)
568 PERM4(ret.c, _c_dfr, _c_dbr, _c_dbl, _c_dfl)
569
570 return ret;
571 case D2:
572 PERM22(ret.e, _e_df, _e_db, _e_dr, _e_dl)
573 PERM22(ret.c, _c_dfr, _c_dbl, _c_dbr, _c_dfl)
574
575 return ret;
576 case D3:
577 PERM4(ret.e, _e_df, _e_dl, _e_db, _e_dr)
578 PERM4(ret.c, _c_dfr, _c_dfl, _c_dbl, _c_dbr)
579
580 return ret;
581 case R:
582 PERM4(ret.e, _e_ur, _e_br, _e_dr, _e_fr)
583 PERM4(ret.c, _c_ufr, _c_ubr, _c_dbr, _c_dfr)
584
585 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
586
587 return ret;
588 case R2:
589 PERM22(ret.e, _e_ur, _e_dr, _e_fr, _e_br)
590 PERM22(ret.c, _c_ufr, _c_dbr, _c_ubr, _c_dfr)
591
592 return ret;
593 case R3:
594 PERM4(ret.e, _e_ur, _e_fr, _e_dr, _e_br)
595 PERM4(ret.c, _c_ufr, _c_dfr, _c_dbr, _c_ubr)
596
597 CO4(ret.c, _c_ubr, _c_dfr, _c_ufr, _c_dbr)
598
599 return ret;
600 case L:
601 PERM4(ret.e, _e_ul, _e_fl, _e_dl, _e_bl)
602 PERM4(ret.c, _c_ufl, _c_dfl, _c_dbl, _c_ubl)
603
604 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
605
606 return ret;
607 case L2:
608 PERM22(ret.e, _e_ul, _e_dl, _e_fl, _e_bl)
609 PERM22(ret.c, _c_ufl, _c_dbl, _c_ubl, _c_dfl)
610
611 return ret;
612 case L3:
613 PERM4(ret.e, _e_ul, _e_bl, _e_dl, _e_fl)
614 PERM4(ret.c, _c_ufl, _c_ubl, _c_dbl, _c_dfl)
615
616 CO4(ret.c, _c_ufl, _c_dbl, _c_dfl, _c_ubl)
617
618 return ret;
619 case F:
620 PERM4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
621 PERM4(ret.c, _c_ufr, _c_dfr, _c_dfl, _c_ufl)
622
623 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
624 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
625
626 return ret;
627 case F2:
628 PERM22(ret.e, _e_uf, _e_df, _e_fr, _e_fl)
629 PERM22(ret.c, _c_ufr, _c_dfl, _c_ufl, _c_dfr)
630
631 return ret;
632 case F3:
633 PERM4(ret.e, _e_uf, _e_fl, _e_df, _e_fr)
634 PERM4(ret.c, _c_ufr, _c_ufl, _c_dfl, _c_dfr)
635
636 EO4(ret.e, _e_uf, _e_fr, _e_df, _e_fl)
637 CO4(ret.c, _c_ufr, _c_dfl, _c_dfr, _c_ufl)
638
639 return ret;
640 case B:
641 PERM4(ret.e, _e_ub, _e_bl, _e_db, _e_br)
642 PERM4(ret.c, _c_ubr, _c_ubl, _c_dbl, _c_dbr)
643
644 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
645 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
646
647 return ret;
648 case B2:
649 PERM22(ret.e, _e_ub, _e_db, _e_br, _e_bl)
650 PERM22(ret.c, _c_ubr, _c_dbl, _c_ubl, _c_dbr)
651
652 return ret;
653 case B3:
654 PERM4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
655 PERM4(ret.c, _c_ubr, _c_dbr, _c_dbl, _c_ubl)
656
657 EO4(ret.e, _e_ub, _e_br, _e_db, _e_bl)
658 CO4(ret.c, _c_ubl, _c_dbr, _c_dbl, _c_ubr)
659
660 return ret;
661 default:
662#ifdef DEBUG
663 fprintf(stderr, "mover error, unknown move\n");
664#endif 558#endif
665 goto move_error;
666 }
667 559
668move_error: 560move_error:
669 return errorcube; 561 return errorcube;
@@ -672,8 +564,9 @@ move_error:
672cube_t 564cube_t
673inverse(cube_t c) 565inverse(cube_t c)
674{ 566{
567 /* TODO: optimize for avx2 */
675 uint8_t i, piece, orien; 568 uint8_t i, piece, orien;
676 cube_t ret = {0}; 569 cube_t ret = zerocube;
677 570
678#ifdef DEBUG 571#ifdef DEBUG
679 if (!isconsistent(c)) { 572 if (!isconsistent(c)) {
@@ -683,15 +576,15 @@ inverse(cube_t c)
683#endif 576#endif
684 577
685 for (i = 0; i < 12; i++) { 578 for (i = 0; i < 12; i++) {
686 piece = c.e[i & _pbits]; 579 piece = get_edge(c, i);
687 orien = piece & _eobit; 580 orien = piece & _eobit;
688 ret.e[piece & _pbits] = i | orien; 581 set_edge(&ret, piece & _pbits, i | orien);
689 } 582 }
690 583
691 for (i = 0; i < 8; i++) { 584 for (i = 0; i < 8; i++) {
692 piece = c.c[i & _pbits]; 585 piece = get_corner(c, i);
693 orien = ((piece << 1) | (piece >> 1)) & _cobits2; 586 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
694 ret.c[piece & _pbits] = i | orien; 587 set_corner(&ret, piece & _pbits, i | orien);
695 } 588 }
696 589
697 return ret; 590 return ret;
@@ -700,8 +593,9 @@ inverse(cube_t c)
700cube_t 593cube_t
701compose(cube_t c1, cube_t c2) 594compose(cube_t c1, cube_t c2)
702{ 595{
703 uint8_t i, piece, orien, aux, auy; 596 /* TODO: optimize for avx2 */
704 cube_t ret = {0}; 597 uint8_t i, piece1, piece2, p, orien, aux, auy;
598 cube_t ret = zerocube;
705 599
706#ifdef DEBUG 600#ifdef DEBUG
707 if (!isconsistent(c1) || !isconsistent(c2)) { 601 if (!isconsistent(c1) || !isconsistent(c2)) {
@@ -711,17 +605,21 @@ compose(cube_t c1, cube_t c2)
711#endif 605#endif
712 606
713 for (i = 0; i < 12; i++) { 607 for (i = 0; i < 12; i++) {
714 piece = c2.e[i] & _pbits; 608 piece2 = get_edge(c2, i);
715 orien = (c2.e[i] ^ c1.e[piece]) & _eobit; 609 p = piece2 & _pbits;
716 ret.e[i] = (c1.e[piece] & _pbits) | orien; 610 piece1 = get_edge(c1, p);
611 orien = (piece2 ^ piece1) & _eobit;
612 set_edge(&ret, i, (piece1 & _pbits) | orien);
717 } 613 }
718 614
719 for (i = 0; i < 8; i++) { 615 for (i = 0; i < 8; i++) {
720 piece = c2.c[i] & _pbits; 616 piece2 = get_corner(c2, i);
721 aux = (c2.c[i] & _cobits) + (c1.c[piece] & _cobits); 617 p = piece2 & _pbits;
618 piece1 = get_corner(c1, p);
619 aux = (piece2 & _cobits) + (piece1 & _cobits);
722 auy = (aux + _ctwist_cw) >> 2U; 620 auy = (aux + _ctwist_cw) >> 2U;
723 orien = (aux + auy) & _cobits2; 621 orien = (aux + auy) & _cobits2;
724 ret.c[i] = (c1.c[piece] & _pbits) | orien; 622 set_corner(&ret, i, (piece1 & _pbits) | orien);
725 } 623 }
726 624
727 return ret; 625 return ret;
@@ -730,14 +628,16 @@ compose(cube_t c1, cube_t c2)
730static cube_t 628static cube_t
731flipallcorners(cube_t c) 629flipallcorners(cube_t c)
732{ 630{
631/* TODO: optimize for avx2, can be a couple of instructions */
632
733 uint8_t i, piece, orien; 633 uint8_t i, piece, orien;
734 cube_t ret; 634 cube_t ret;
735 635
736 ret = c; 636 ret = c;
737 for (i = 0; i < 8; i++) { 637 for (i = 0; i < 8; i++) {
738 piece = ret.c[i]; 638 piece = get_corner(c, i);
739 orien = ((piece << 1) | (piece >> 1)) & _cobits2; 639 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
740 ret.c[i] = (piece & _pbits) | orien; 640 set_corner(&ret, i, (piece & _pbits) | orien);
741 } 641 }
742 642
743 return ret; 643 return ret;
@@ -746,8 +646,6 @@ flipallcorners(cube_t c)
746cube_t 646cube_t
747transform(cube_t c, trans_t t) 647transform(cube_t c, trans_t t)
748{ 648{
749#include "_trans_move_arr.c"
750
751 cube_t ret; 649 cube_t ret;
752 650
753#ifdef DEBUG 651#ifdef DEBUG
@@ -761,6 +659,12 @@ transform(cube_t c, trans_t t)
761 } 659 }
762#endif 660#endif
763 661
662#ifdef CUBE_AVX2
663#include "_trans_move_avx2.c"
664#else
665#include "_trans_move_arr.c"
666#endif
667
764 ret = compose(solvedcube, trans_move_cube[t]); 668 ret = compose(solvedcube, trans_move_cube[t]);
765 ret = compose(ret, c); 669 ret = compose(ret, c);
766 ret = compose(ret, trans_move_cube_inverse[t]); 670 ret = compose(ret, trans_move_cube_inverse[t]);
diff --git a/src/cube.h b/src/cube.h
index 363cad4..4c6de2f 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -1,11 +1,11 @@
1/* Types *********************************************************************/ 1/* Types *********************************************************************/
2 2
3/* TODO: ifdef for different implementations */
4/* See doc/CUBE_INTERNAL.md for a description of the cube format */ 3/* See doc/CUBE_INTERNAL.md for a description of the cube format */
5typedef struct { 4#ifdef CUBE_AVX2
6 uint8_t c[8]; 5typedef __m256i cube_t;
7 uint8_t e[12]; 6#else
8} cube_t; 7typedef struct { uint8_t c[8]; uint8_t e[12]; } cube_t;
8#endif
9 9
10typedef uint8_t move_t; 10typedef uint8_t move_t;
11typedef uint8_t trans_t; 11typedef uint8_t trans_t;

Generated with cgit - Back to sebastiano.tronto.net