commit 28ad019d62583b7e89b4e76922aa73857d5876eb
parent 49b9c4a516f72e03d53277075f4580e2df8f0e63
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Tue, 28 May 2024 15:42:26 +0200
Added roadmap for refactor and some simple routines
Diffstat:
15 files changed, 143 insertions(+), 13 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,12 +1,30 @@
-Correctness
- - check all bitwise operations specifically
- - consider adding more warnings (-pedantic?) or using more static analyzers
+Refactoring: remove cube_fast_t and add b32 format
+ x added b32 converter by piece (not tested, will be tested automatically)
+ x added piece functions (e.g. corner(cube, i))
+ (would be more efficient to just convert the whole thing to arrays...)
+ - replace all usages of cube_t with cube_fast_t and piece functions
+ (this is mainly in cube_routines)
+ (fix tests in tandem with main code)
+ cubetofast fasttocube
+ zero and solved
+ solvedcube(void)
+ [cube.h] isconsistent, issolvable, issolved, equal, iserror
+ [cube.h] compose, inverse
+ [cube.h] applymoves, applytrans
+ [cube.h] readcube writecube
+ [cube.h] solve
+ - add b32 i/o format as default
+ - remove cube_t type
+ - rename cube_fast_t to cube_t
+ - if all public functions work with strings, always use return value
+ as error code (solve already does this), and use string as buffer
+ to print error
Solver
- write a solver (how many tricks? some, but not all are needed)
More utilities for tables (in cube.h)
- - a "dryrun" function that only tells you the size needed
+ - for tables, a "dryrun" function that only tells you the size needed
- check hash of generated data
Goal: find out which k value is best
@@ -15,9 +33,6 @@ Goal: find out which k value is best
- benchmark for different sizes!
Refactoring
- - remove cube type and some low-level utilities from interface,
- rename cube_fast_t to cube_t
- - add b64 i/o format, base64 encoded cube, one 6-bit word per piece
- transformations: remove switch to make shorter, but keep performance
## H48 optimal solver (some has already been implemented)
diff --git a/src/cube.c b/src/cube.c
@@ -9,10 +9,8 @@
#define DBG_LOG(...) fprintf(stderr, __VA_ARGS__)
#define DBG_WARN(condition, ...) if (!(condition)) DBG_LOG(__VA_ARGS__);
#define DBG_ASSERT(condition, retval, ...) \
- if (!(condition)) { \
- DBG_LOG(__VA_ARGS__); \
- return retval; \
- }
+ if (!(condition)) { DBG_LOG(__VA_ARGS__); return retval; }
+
#else
#define _static static
#define _static_inline static inline
diff --git a/src/cube_avx2.h b/src/cube_avx2.h
@@ -14,6 +14,8 @@ _static_inline cube_fast_t fastcube(
uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
);
+_static uint8_t corner(cube_fast_t, int);
+_static uint8_t edge(cube_fast_t, int);
_static cube_fast_t cubetofast(cube_t);
_static cube_t fasttocube(cube_fast_t);
_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
@@ -68,6 +70,28 @@ fastcube(
);
}
+_static uint8_t
+corner(cube_fast_t c, int i)
+{
+ uint8_t aux[32];
+
+ DBG_ASSERT(i >= 0 && i < 8, 255, "Corner must be between 0 and 7\n");
+ _mm256_storeu_si256((__m256i_u *)aux, c);
+
+ return aux[i];
+}
+
+_static uint8_t
+edge(cube_fast_t c, int i)
+{
+ uint8_t aux[32];
+
+ DBG_ASSERT(i >= 0 && i < 12, 255, "Edge must be between 0 and 11\n");
+ _mm256_storeu_si256((__m256i_u *)aux, c);
+
+ return aux[i+16];
+}
+
_static cube_fast_t
cubetofast(cube_t a)
{
@@ -338,4 +362,3 @@ invcoord_fast_esep(int64_t esep)
return ret;
}
-
diff --git a/src/cube_portable.h b/src/cube_portable.h
@@ -1,4 +1,7 @@
-typedef cube_t cube_fast_t;
+typedef struct {
+ uint8_t corner[8];
+ uint8_t edge[12];
+} cube_fast_t;
_static_inline cube_fast_t fastcube(
uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
@@ -6,6 +9,8 @@ _static_inline cube_fast_t fastcube(
uint8_t, uint8_t, uint8_t, uint8_t, uint8_t,
uint8_t, uint8_t, uint8_t, uint8_t, uint8_t
);
+_static uint8_t corner(cube_fast_t, int);
+_static uint8_t edge(cube_fast_t, int);
_static cube_fast_t cubetofast(cube_t);
_static cube_t fasttocube(cube_fast_t);
_static_inline bool equal_fast(cube_fast_t, cube_fast_t);
@@ -66,6 +71,21 @@ fastcube(
return cube;
}
+_static uint8_t
+corner(cube_fast_t c, int i)
+{
+ DBG_ASSERT(i >= 0 && i < 8, 255, "Corner must be between 0 and 7\n");
+
+ return c.corner[i];
+}
+_static uint8_t
+edge(cube_fast_t c, int i)
+{
+ DBG_ASSERT(i >= 0 && i < 12, 255, "Edge must be between 0 and 11\n");
+
+ return c.edge[i];
+}
+
_static cube_fast_t
cubetofast(cube_t cube)
{
diff --git a/src/cube_routines.h b/src/cube_routines.h
@@ -12,6 +12,10 @@ _static cube_t readcube_LST(const char *);
_static int writepiece_LST(uint8_t, char *);
_static void writecube_H48(cube_t, char *);
_static void writecube_LST(cube_t, char *);
+_static uint8_t b32toedge(char);
+_static uint8_t b32tocorner(char);
+_static char edgetob32(uint8_t);
+_static char cornertob32(uint8_t);
_static uint8_t readmove(char);
_static uint8_t readmodifier(char);
_static uint8_t readtrans(const char *);
@@ -494,6 +498,43 @@ writecube_LST(cube_t cube, char *buf)
}
_static uint8_t
+b32toedge(char c)
+{
+ DBG_ASSERT((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'g'), 255,
+ "Error reading base32 piece");
+
+ return c <= 'Z' ? (uint8_t)(c - 'A') : (uint8_t)(c - 'a');
+}
+
+_static uint8_t
+b32tocorner(char c) {
+ uint8_t val;
+
+ DBG_ASSERT((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'g'), 255,
+ "Error reading base32 piece");
+
+ val = c <= 'Z' ? (uint8_t)(c - 'A') : (uint8_t)(c - 'a') + 26;
+
+ return (val & 7) | ((val & 24) << 2);
+}
+
+_static char
+edgetob32(uint8_t edge)
+{
+ return edge <= 26 ? 'A' + (char)edge : 'a' + (char)(edge - 26);
+}
+
+_static char
+cornertob32(uint8_t corner)
+{
+ uint8_t val;
+
+ val = (corner & 7) | ((corner & 96) >> 2);
+
+ return val <= 26 ? 'A' + (char)val : 'a' + (char)(val - 26);
+}
+
+_static uint8_t
readmove(char c)
{
switch (c) {
diff --git a/test/001_cube_conversion/00_solved.in b/test/001_pieces/01_solved.in
diff --git a/test/001_pieces/01_solved.out b/test/001_pieces/01_solved.out
@@ -0,0 +1,2 @@
+0 1 2 3 4 5 6 7
+0 1 2 3 4 5 6 7 8 9 10 11
diff --git a/test/001_pieces/02_scrambled.in b/test/001_pieces/02_scrambled.in
@@ -0,0 +1 @@
+FL0 DB0 UB1 FR0 UR0 DF0 UF0 BR1 UL1 BL1 DL0 DR0 DFR1 UFR1 UBR1 UFL2 DBR2 DFL0 DBL2 UBL0
diff --git a/test/001_pieces/02_scrambled.out b/test/001_pieces/02_scrambled.out
@@ -0,0 +1,2 @@
+38 32 37 68 67 2 71 1
+9 2 17 8 4 3 0 27 21 26 6 7
diff --git a/test/001_pieces/pieces_tests.c b/test/001_pieces/pieces_tests.c
@@ -0,0 +1,28 @@
+#include "../test.h"
+
+uint8_t corner(cube_fast_t, int);
+uint8_t edge(cube_fast_t, int);
+
+int main(void) {
+ int i;
+ char str[STRLENMAX], *aux;
+ cube_t cube;
+ cube_fast_t fast;
+
+ aux = str;
+ while (fgets(aux, STRLENMAX, stdin) != NULL)
+ while (*aux != '\n')
+ aux++;
+
+ cube = readcube("H48", str);
+ fast = cubetofast(cube);
+
+ for (i = 0; i < 8; i++)
+ printf("%" PRIu8 " ", corner(fast, i));
+ printf("\n");
+ for (i = 0; i < 12; i++)
+ printf("%" PRIu8 " ", edge(fast, i));
+ printf("\n");
+
+ return 0;
+}
diff --git a/test/001_cube_conversion/00_solved.out b/test/002_cube_conversion/00_solved.in
diff --git a/test/001_cube_conversion/00_solved.in b/test/002_cube_conversion/00_solved.out
diff --git a/test/001_cube_conversion/01_scrambled.in b/test/002_cube_conversion/01_scrambled.in
diff --git a/test/001_cube_conversion/01_scrambled.out b/test/002_cube_conversion/01_scrambled.out
diff --git a/test/001_cube_conversion/cube_conversion_tests.c b/test/002_cube_conversion/cube_conversion_tests.c
