Moved documentation around, improved configure.sh

6 files changed, 239 insertions, 195 deletions

diff --git a/README.md b/README.md
index aa5c4f7..4a0157a 100644
--- a/README.md
+++ b/README.md
@@ -1,8 +1,7 @@
 # Prototype for a new optimal solver
 
-Work in progress. There is some documentation at the bottom of this page,
-but do not believe it. Everything is in a state of flux and can change
-without notice.
+Work in progress. Everything is in a state of flux and can change without
+notice.
 
 ## Building and running tests
 
@@ -34,173 +33,3 @@ $ make benchmark
 ```
 
 for benchmarks.
-
-## TODO:
-
-### Generic solver
-
-* finish implementation
-* tests: solve full cube (max 7-8 moves?)
-* more tests: eo and other stuff
-* benchmarks
-
-### Add NISS
-
-* Add mask to moves (e.g. U | NISS where NISS = 32 or something)
-* Adapt readmoves and writemoves
-
-### Coordinates
-
-* [done] eo
-* co
-* ep
-* epsep
-* cp
-* cpsep
-* cphtr
-
-What about symcoord?
-
-### Solving
-
-All solving functions take a cube and some parameters as input.
-
-* Depth [uint, <= 20]: all solvers work at fixed depth. The caller
-  implementation can implement an A* search.
-* max [int]: the maximum number of solutions to find. Set to a negative
-  value for all solutions.
-* sol [move_t *]: the array for returning the solutions. The caller
-  should make sure that it can hold at least max * depth values.
-* Table [uint8_t *]: table with all the necessare pre-computed info.
-  The table can be generated with a companion function, but reading
-  from and writing to file is delegated to the caller implementation.
-
-Implement the following solvers:
-* Slow: basic solver without any table.
-* H48: one-bit-per-entry table + fallback, 48 symmetries and so on.
-  See planner.
-* nxopt31: mostly for comparison.
-* other nxopt solvers: make generic and take the type as parameter.
-* Step solver: take a coordinate function and a moveset as a parameter.
-
-### cube.h changes
-
-* better documentation: add parameter names, one-line comment
-  for each function
-* prefix public functions with nissy_ or something similar
-* move() that takes a string (alg) as input
-* Add single moves and transformations to the interface? (performance!)
-
-### Documentation and interface
-
-* inline some documentation as comments in source code
-* README.md (maybe convert to txt?) becomes the reference documentation
-
-### Optimizations
-
-* Trans: don't do full compose, for some trans composing perm is enough.
-  Split out sumco() as a separate function and refactor, optimize.
-* Use multi-move (up to 4/5 moves at once)
-* 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?
-* Improve avx2 instructions in general
-
-## Internal representation of the cube
-
-The plan (TODO) is to have multiple implementations: some that
-take advantage of advanced CPU instructions (SIMD) and a fallback
-"array" representation that works on any architecture.
-
-### Array representation (fallback)
-
-In this implementation of the cube.h interface, the cube is represented
-by two arrays of 8-bit unsigned integers, one for centers and one for
-corners.  The 4 leas-significant digits of each bit determine the piece,
-the other 4 are used for orientation or kept to 0.
-
-Edges:
-        xxxopppp (x = unused, o = orientation, p = piece)
-
-Corners:
-        xooxpppp (x = unused, o = orientation, p = piece)
-
-The two bits for CO are shifted to make it possible to perform mod 3
-operations (sum, inverse) using only addition and bitwise operators.
-See below for details.
-
-The third bit is needed because x+y+1 can exceed 4.
-
-### AVX2
-
-Work in progress
-
-
-## Textual representation of the cube
-
-The functions readcube() and writecube() use different formats to read
-and write a cube to text. Not all formats are supported for both input
-and output.
-
-### H48 - standard format for h48 (read, write)
-
-Each edge is represented by two letters denoting the sides it belongs to
-and one number denoting its orientation (0 oriented, 1 mis-oriented).
-Similarly, each corner is represented by three letters and a number
-(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
-Edge orientation is relative to the F / B axis, corner orientation is
-relative to the U / D axis.
-
-The pieces are ordered such that the solved cube looks like this:
-
-UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
-UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
-
-Whitespace (including newlines) between pieces is ignored when reading
-the cube, and a single whitespace character is added between pieces
-when writing.
-
-The cube after the moves R'U'F looks like this:
-
-FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
-UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
-
-### SRC - representation of the object in C code for cube_array (write)
-
-The exact format depends on the internal cube representation (TODO: actually
-this is false, because I need all formats for code generation; also adapating
-tests is hard). It is guaranteed that, if OUT is the output in this format,
-the line
-
-cube_t cube = OUT;
-
-is interpreted correctly by h48.
-
-
-## Transformations
-
-Transformations can be either simple rotations or a rotation composed
-with a mirroring.
-
-Simple rotations are denoted by two letters corresponding to the faces
-to be moved to the U and F positions, respectively. For example FD is
-the rotation that brings the F face on top and the D face on front.
-
-A composed rotation + mirror is obtained by applying the corresponding
-rotation to the solved cube mirrored along the M plane.
-
-For example, to apply the transformation RBm (mirrored RB) to a cube C:
-        1a. Apply a mirror along the M plane to the solved cube
-        1b. Rotate the mirrored cube with z' y2
-        3.  Apply the cube C to the transformed solved cube
-        4.  Apply the transformations of step 1a and 1b in reverse
-
-The orientation of pieces after a rotation ignores the new position
-of centers.  A rotated cube can technically be inconsistent, because
-the parity of the edge permutation has to be adjusted considering the
-parity of the centers, which we ignore.
-
-The utility script mirror.sh transforms a solved, rotated cube to its
-mirrored and rotated version.
diff --git a/TODO.txt b/TODO.txt
new file mode 100644
index 0000000..69d528a
--- /dev/null
+++ b/TODO.txt
@@ -0,0 +1,69 @@
+### Generic solver
+
+* finish implementation
+* tests: solve full cube (max 7-8 moves?)
+* more tests: eo and other stuff
+* benchmarks
+
+### Coordinates
+
+* [done] eo
+* co
+* ep
+* epsep
+* cp
+* cpsep
+* cphtr
+
+What about symcoord?
+
+### Solving
+
+All solving functions take a cube and some parameters as input.
+
+* Depth [uint, <= 20]: all solvers work at fixed depth. The caller
+  implementation can implement an A* search.
+* max [int]: the maximum number of solutions to find. Set to a negative
+  value for all solutions.
+* sol [move_t *]: the array for returning the solutions. The caller
+  should make sure that it can hold at least max * depth values.
+* Table [uint8_t *]: table with all the necessare pre-computed info.
+  The table can be generated with a companion function, but reading
+  from and writing to file is delegated to the caller implementation.
+
+Implement the following solvers:
+* Slow: basic solver without any table.
+* H48: one-bit-per-entry table + fallback, 48 symmetries and so on.
+  See planner.
+* nxopt31: mostly for comparison.
+* other nxopt solvers: make generic and take the type as parameter.
+* Step solver: take a coordinate function and a moveset as a parameter.
+
+### cube.h changes
+
+* better documentation: add parameter names, one-line comment
+  for each function
+* prefix public functions with nissy_ or something similar
+* move() that takes a string (alg) as input
+* readtrans() should work like readmoves (read multiple, return n)
+* Add single moves and transformations to the interface? (performance!)
+
+### Optimizations
+
+* Trans: don't do full compose, for some trans composing perm is enough.
+  Split out sumco() as a separate function and refactor, optimize.
+* Use multi-move (up to 4/5 moves at once)
+* 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?
+* Improve avx2 instructions in general
+
+### Improvements and other things
+
+* NISS: Add mask to moves (e.g. U | NISS where NISS = 32 or something);
+  adapt readmoves and writemoves.
+* Consider adding centers and other moves (for avx2: centers in the
+  same lane as corners, numbered from 9 to 14)
+* rename to: libnissy? (also change all references to cube.c in doc)
diff --git a/configure.sh b/configure.sh
index 44774cd..9a790ca 100755
--- a/configure.sh
+++ b/configure.sh
@@ -1,5 +1,8 @@
 #!/bin/sh
 
+cc -mavx2 utils/detect-immintrin.c && detected="AVX2" && rm a.out
+TYPE=${TYPE-"$detected"}
+
 STD="-std=c99"
 WFLAGS="-pedantic -Wall -Wextra -Wno-unused-parameter -Wno-unused-function"
 [ "$TYPE" = "AVX2" ] && AVX="-mavx2"
diff --git a/cube.c b/cube.c
index cc38be7..3ba3926 100644
--- a/cube.c
+++ b/cube.c
@@ -94,9 +94,6 @@ Section: constants and strings
 #define BDm 46
 #define BLm 47
 
-#define errormove 99U
-#define errortrans 99U
-
 #define _c_ufr      0U
 #define _c_ubl      1U
 #define _c_dfl      2U
@@ -620,7 +617,7 @@ readtrans(char *buf)
                         return t;
 
         DBG_LOG("readtrans error\n");
-        return errortrans;
+        return _error;
 }
 
 void
diff --git a/cube.h b/cube.h
index 56118c2..3f9b509 100644
--- a/cube.h
+++ b/cube.h
@@ -1,36 +1,177 @@
+/******************************************************************************
+Cube type definition
+
+Each piece is represented by an (unsigned) 8-bit integer. The 4
+least-significant bits determine which piece it is, the other 4 determine
+the orientation.
+
+Edges are numbered as follows (see also cube.c):
+UF=0 UB=1 DB=2 DF=3 UR=4 UL=5 DL=6 DR=7 FR=8 FL=9 BL=10 BR=11
+
+Corners are numbered as follows:
+UFR=0 UBL=1 DFL=2 DBR=3 UFL=4 UBR=5 DFR=6 DBL=7
+
+The orientation of the edges is with respect to F/B, the orientation of
+corners is with respect to U/D.
+
+The permutation of the center pieces is not stored. This means that the
+cube is assumed to be in a fixed orientation.
+
+TODO: encode centers?
+
+The exact cube type structure depends on your system's configuration. If
+you operate on the cube only via the functions provided below, you don't
+need to worry about this.
+******************************************************************************/
+
 #ifdef CUBE_AVX2
 typedef __m256i cube_t;
 #else
 typedef struct {
-        uint8_t c[8];
-        uint8_t e[12];
+        uint8_t c[8];   /* Corners */
+        uint8_t e[12];  /* Edges   */
 } cube_t;
 #endif
 
-typedef uint8_t move_t;
-typedef uint8_t trans_t;
-
-int readmoves(char *, move_t *);
-void writemoves(move_t *, int, char *);
-trans_t readtrans(char *);
-void writetrans(trans_t, char *);
-
-typedef enum {AVX, H48, SRC} format_t;
-cube_t readcube(format_t, char *);        /* Supports: H48 */
-void writecube(format_t, cube_t, char *); /* Supports: AVX, H48, SRC */
-
+/* Returns a copy of the solved cube */
 cube_t solvedcube(void);
+
+/* Basic checks on the cube */
 bool issolvable(cube_t);
 bool equal(cube_t, cube_t);
 bool issolved(cube_t);
+
+/* Apply the second cube on the first as a move sequence */
+cube_t compose(cube_t, cube_t);
+
+/* Invert the cube */
+cube_t inverse(cube_t);
+
+/* All functions can return an error value, use iserror() to check this */
 bool iserror(cube_t);
 
+/******************************************************************************
+Moves and transformations
+
+Moves and transformations are represented each as an (unsigned) 8 bit integer.
+
+Moves are numbered as follows:
+U=0  U2=1  U'=2  D=3  D2=4  D'=5
+R=6  R2=7  R'=8  L=9  L2=10 L'=11
+F=12 F2=13 F'=14 B=15 B2=16 B'=17
+
+TODO: NISS
+
+TODO: Extend the moveset?
+
+Transformations can be either simple rotations or a rotation composed
+with a mirroring.  A composed rotation + mirror is obtained by applying
+the corresponding rotation to the solved cube mirrored along the M plane.
+
+For example, to apply the transformation RBm (mirrored RB) to a cube C:
+        1. Apply a mirror along the M plane to the solved cube
+        2. Rotate the mirrored cube with z' y2
+        3. Apply the cube C to the transformed solved cube
+        4. Apply the transformations of step 1a and 1b in reverse
+
+See cube.c for a full list of transformations.
+******************************************************************************/
+
+typedef uint8_t move_t;
+typedef uint8_t trans_t;
+
+/* Apply a move or a transformation on the cube */
 cube_t move(cube_t, move_t);
-cube_t inverse(cube_t);
-cube_t compose(cube_t, cube_t);
 cube_t transform(cube_t, trans_t);
 
-int16_t coord_eo(cube_t);
+/******************************************************************************
+Read / write utilities
+
+Reading and writing is not done directly via stdin / stdout, but via an
+array of char (called buf in the prototypes below).
+
+Multiple representations of the cube as text are supported, although
+not all of them are supported for both reading and writing. See below
+for details. More formats may be supported in the future.
+
+Moves are read using the standard notation. Each move (U, D, R, L, F,
+B) can be followed by a modifier (1, 2, 3, '). Whitespace (spaces, tabs,
+newlines) are ignored. Parantheses and other notation is not supported.
+TODO: parantheses for NISS
+
+For how transformations are read or written, see cube.c.
+******************************************************************************/
+
+/* The different formats for reading or writing the cube */
+typedef enum {
+        H48, /* H48 is a human-readable format.
+              *
+              * Each edge is represented by two letters denoting the sides it
+              * belongs to and one number denoting its orientation (0 oriented,
+              * 1 mis-oriented). Similarly, each corner is represented by three
+              * letters and a number (0 oriented, 1 twisted clockwise, 2
+              * twisted counter-clockwise).
+              *
+              * The solved cube looks like this:
+              *
+              * UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
+              * UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
+              *
+              * The cube after the moves R'U'F looks like this:
+              *
+              * FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
+              * UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
+              *
+              * Whitespace (including newlines) between pieces is ignored when
+              * reading the cube. A single whitespace character is added
+              * between pieces when writing.
+              */
+        SRC, /* The SRC format can be used to generate code for internal use.
+              *
+              * In cube.c, a type called cube_array_t is defined and used for
+              * basic, non-performance-critical methods. If OUT is the output
+              * in SRC format, the following line can be used to declare a new
+              * cube object:
+              *
+              * cube_array_t cube = OUT
+              */
+        AVX, /* The AVX format is analogous to SRC, but for the AVX2 internal
+              * representation of the cube.
+              */
+} format_t;
+
+/* Reads a cube from buf in the specified format, and return it.
+ * Supported formats: H48.
+ */
+cube_t readcube(format_t format, char *buf);
+
+/* Write the given cube to buf in the specified format.
+ * Supported formats: H48, SRC, AVX.
+ */
+void writecube(format_t format, cube_t cube, char *buf);
+
+/* Utilities for reading and writing moves */
+int readmoves(char *buf, move_t *moves);
+void writemoves(move_t *moves, int n, char *buf);
+trans_t readtrans(char *buf);
+void writetrans(trans_t trans, char *buf);
+
+/******************************************************************************
+Coordinates
+
+The coordinate functions compute one aspect of the cube (for example,
+the edge orientation) and they return it as an integer. They are used
+for example to build pruning tables for various solving methods.
+******************************************************************************/
+
+int16_t coord_eo(cube_t); /* Edge orientation */
+
+/******************************************************************************
+Solvers
+
+Solvers return -1 in case of error, the number of solutions otherwise
+
+TODO
+******************************************************************************/
 
-/* Solvers return -1 in case of error, the number of solutions otherwise */
 int solve_generic(cube_t, int (*)(cube_t), uint8_t, int, move_t *);
diff --git a/utils/detect-immintrin.c b/utils/detect-immintrin.c
new file mode 100644
index 0000000..20da678
--- /dev/null
+++ b/utils/detect-immintrin.c
@@ -0,0 +1,5 @@
+#include <immintrin.h>
+
+int main() {
+        return 0;
+}