commit e082001f7c7c8ce0d20aebad4e6d6f22d3bf854c
parent 72c9082c9824c7ffecc97a94083aa350956285e4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Wed, 8 Nov 2023 16:18:14 +0100
Moved documentation around, improved configure.sh
Diffstat:
| M | README.md | | | 175 | +------------------------------------------------------------------------------ |
| A | TODO.txt | | | 69 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | configure.sh | | | 3 | +++ |
| M | cube.c | | | 5 | +---- |
| M | cube.h | | | 177 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------- |
| A | utils/detect-immintrin.c | | | 5 | +++++ |
6 files changed, 239 insertions(+), 195 deletions(-)
diff --git 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -0,0 +1,5 @@
+#include <immintrin.h>
+
+int main() {
+ return 0;
+}
