Added avx2 moves

5 files changed, 266 insertions, 14 deletions

diff --git a/README.md b/README.md
index 2990c29..571a859 100644
--- a/README.md
+++ b/README.md
@@ -15,10 +15,7 @@ $ make test
 
 ### Make AVX2 work
 
-* inline moves for avx2
 * fix base get_ and set_ macros (constant arguments?)
-* optimize inverse for avx2
-* other things to optimize?
 
 ### Documentation and interface
 
@@ -37,10 +34,13 @@ $ make test
 * Takes as parameters the amount of memory to use and a FILE for the tables
 * Use multi-move (up to 4/5 moves at once)
 
-### Things I need to learn:
+### Future optimizations
 
-* Inspect compiled assembly
-* Use valgrind tool cachegrind and other profiling tools
+* CO is the worst part of moving, transforming and inverting. Try basing
+  everything on representing the cube without CO and apply it only at the
+  end to check that it is actually solved.
+* see if vcube's method to flip all corners is better
+* find a better way for computing the inverse?
 
 ## Internal representation of the cube
 
diff --git a/src/_moves_avx2.c b/src/_moves_avx2.c
index d72f45f..0c1f6a3 100644
--- a/src/_moves_avx2.c
+++ b/src/_moves_avx2.c
@@ -1,2 +1,197 @@
-/* TODO: return compose(c, (some avx garbage));
-*/
+static inline cube_t
+inline_move_U(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 7, 6, 0, 1, 3, 2, 5, 4,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 1, 0, 3, 2, 4, 5
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_U2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 7, 6, 4, 5, 3, 2, 0, 1,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 4, 5, 3, 2, 0, 1
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_U3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 7, 6, 1, 0, 3, 2, 4, 5,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 6, 0, 1, 3, 2, 5, 4
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_D(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 3, 2, 5, 4, 6, 7, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 3, 2, 5, 4, 6, 7, 1, 0
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_D2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 6, 7, 5, 4, 2, 3, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 6, 7, 5, 4, 2, 3, 1, 0
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_D3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 9, 8, 2, 3, 5, 4, 7, 6, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 5, 4, 7, 6, 1, 0
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_R(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 4, 10, 9, 7, 11, 6, 5, 8, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 35, 32, 4, 69, 2, 1, 70
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_R2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 8, 10, 9, 11, 4, 6, 5, 7, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 5, 6, 4, 0, 2, 1, 3
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_R3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 7, 10, 9, 4, 8, 6, 5, 11, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 32, 35, 4, 70, 2, 1, 69
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_L(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 6, 5, 8, 7, 9, 10, 4, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 34, 6, 5, 33, 3, 68, 71, 0
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_L2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 9, 10, 8, 7, 5, 6, 4, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 4, 6, 5, 7, 3, 1, 2, 0
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_L3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 5, 6, 8, 7, 10, 9, 4, 3, 2, 1, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 33, 6, 5, 34, 3, 71, 68, 0
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_F(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 19, 16, 7, 6, 5, 4, 24, 2, 1, 25,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 64, 5, 66, 3, 38, 1, 36
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_F2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 8, 9, 7, 6, 5, 4, 0, 2, 1, 3,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 5, 6, 3, 0, 1, 2
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_F3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 11, 10, 16, 19, 7, 6, 5, 4, 25, 2, 1, 24,
+                0, 0, 0, 0, 0, 0, 0, 0, 7, 66, 5, 64, 3, 36, 1, 38
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_B(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 18, 17, 9, 8, 7, 6, 5, 4, 3, 26, 27, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 65, 6, 67, 4, 39, 2, 37, 0
+        );
+
+        return compose(c, m);
+}
+
+static inline cube_t
+inline_move_B2(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 10, 11, 9, 8, 7, 6, 5, 4, 3, 1, 2, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 5, 6, 7, 4, 1, 2, 3, 0
+        );
+
+        return _mm256_shuffle_epi8(c, m);
+}
+
+static inline cube_t
+inline_move_B3(cube_t c)
+{
+        cube_t m = _mm256_set_epi8(
+                0, 0, 0, 0, 17, 18, 9, 8, 7, 6, 5, 4, 3, 27, 26, 0,
+                0, 0, 0, 0, 0, 0, 0, 0, 67, 6, 65, 4, 37, 2, 39, 0
+        );
+
+        return compose(c, m);
+}
diff --git a/src/cube.c b/src/cube.c
index 73f50af..401895e 100644
--- a/src/cube.c
+++ b/src/cube.c
@@ -269,6 +269,7 @@ static char *transstr[] = {
         [BLm] = "mirrored BL",
 };
 
+static inline cube_t inline_compose(cube_t, cube_t);
 static bool isconsistent(cube_t);
 static cube_t flipallcorners(cube_t);
 static uint8_t readco(char *);
@@ -909,18 +910,49 @@ cube_t
 inverse(cube_t c)
 {
         /* TODO: optimize for avx2 */
-        uint8_t i, piece, orien;
         cube_t ret;
 
-        setzero(ret);
-
 #ifdef DEBUG
         if (!isconsistent(c)) {
                 fprintf(stderr, "inverse error, inconsistent cube\n");
+                setzero(ret);
                 return ret;
         }
 #endif
 
+#ifdef CUBE_AVX2
+        /* Method taken from Andrew Skalski's vcube[1]. The addition sequence
+         * was generated using [2].
+         * [1] https://github.com/Voltara/vcube
+         * [2] http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
+         */
+        cube_t v3, vi;
+
+        v3 = _mm256_shuffle_epi8(c, c);
+        v3 = _mm256_shuffle_epi8(v3, c);
+        vi = _mm256_shuffle_epi8(v3, v3);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, v3);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, c);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        vi = _mm256_shuffle_epi8(vi, v3);
+        vi = _mm256_shuffle_epi8(vi, vi);
+        ret = _mm256_shuffle_epi8(vi, c);
+        
+        return flipallcorners(ret);
+#else
+        uint8_t i, piece, orien;
+
+        setzero(ret);
+
         for (i = 0; i < 12; i++) {
                 piece = get_edge(c, i);
                 orien = piece & _eobit;
@@ -932,12 +964,13 @@ inverse(cube_t c)
                 orien = ((piece << 1) | (piece >> 1)) & _cobits2;
                 set_corner(ret, piece & _pbits, i | orien);
         }
+#endif
 
         return ret;
 }
 
-cube_t
-compose(cube_t c1, cube_t c2)
+static inline cube_t
+inline_compose(cube_t c1, cube_t c2)
 {
         cube_t ret;
 
@@ -992,6 +1025,12 @@ compose(cube_t c1, cube_t c2)
 }
 
 cube_t
+compose(cube_t c1, cube_t c2)
+{
+        return inline_compose(c1, c2);
+}
+
+cube_t
 transform(cube_t c, trans_t t)
 {
         cube_t ret;
diff --git a/utils/genmovecode.sh b/utils/genmovecode.sh
new file mode 100755
index 0000000..c389ea8
--- /dev/null
+++ b/utils/genmovecode.sh
@@ -0,0 +1,19 @@
+#!/bin/sh
+
+type="${1:-src}"
+
+gcc -DDEBUG h48_to_"$type".c ../src/cube.c -o h48_to_"$type"
+
+genfuncs() {
+        for f in move_??_*.txt; do
+                move="$(echo $f | sed 's/.*_// ; s/\.txt//')"
+                printf 'static inline cube_t\ninline_move_%s' "$move"
+                printf '(cube_t c)\n{\n'
+                printf '\tcube_t m = '
+                ./h48_to_"$type" <"$f" | sed '2,4s/^/\t/'
+                printf ';\n\n\treturn compose(c, m);\n}\n\n'
+        done
+}
+
+genfuncs
+rm -f h48_to_"$type" invert
diff --git a/utils/gentranscode.sh b/utils/gentranscode.sh
index e874ad4..7749ba7 100755
--- a/utils/gentranscode.sh
+++ b/utils/gentranscode.sh
@@ -23,7 +23,6 @@ genfuncs() {
         for f in transform_??_???.txt; do
                 trans="$(echo $f | sed 's/.*_// ; s/\.txt//')"
                 printf 'static inline cube_t\ninline_trans_%s' "$trans"
-                [ "$1" = "-i" ] && printf '_inverse'
                 printf '(cube_t c)\n{\n'
                 printf '\tcube_t ret;\n\n'
                 printf '\tcube_t tn = '