From 28ad019d62583b7e89b4e76922aa73857d5876eb Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 28 May 2024 15:42:26 +0200 Subject: Added roadmap for refactor and some simple routines --- TODO.txt | 29 +++++++++++++---- src/cube.c | 6 ++-- src/cube_avx2.h | 25 ++++++++++++++- src/cube_portable.h | 22 ++++++++++++- src/cube_routines.h | 41 ++++++++++++++++++++++++ test/001_cube_conversion/00_solved.in | 1 - test/001_cube_conversion/00_solved.out | 1 - test/001_cube_conversion/01_scrambled.in | 1 - test/001_cube_conversion/01_scrambled.out | 1 - test/001_cube_conversion/cube_conversion_tests.c | 25 --------------- test/001_pieces/01_solved.in | 1 + test/001_pieces/01_solved.out | 2 ++ test/001_pieces/02_scrambled.in | 1 + test/001_pieces/02_scrambled.out | 2 ++ test/001_pieces/pieces_tests.c | 28 ++++++++++++++++ test/002_cube_conversion/00_solved.in | 1 + test/002_cube_conversion/00_solved.out | 1 + test/002_cube_conversion/01_scrambled.in | 1 + test/002_cube_conversion/01_scrambled.out | 1 + test/002_cube_conversion/cube_conversion_tests.c | 25 +++++++++++++++ 20 files changed, 173 insertions(+), 42 deletions(-) delete mode 100644 test/001_cube_conversion/00_solved.in delete mode 100644 test/001_cube_conversion/00_solved.out delete mode 100644 test/001_cube_conversion/01_scrambled.in delete mode 100644 test/001_cube_conversion/01_scrambled.out delete mode 100644 test/001_cube_conversion/cube_conversion_tests.c create mode 100644 test/001_pieces/01_solved.in create mode 100644 test/001_pieces/01_solved.out create mode 100644 test/001_pieces/02_scrambled.in create mode 100644 test/001_pieces/02_scrambled.out create mode 100644 test/001_pieces/pieces_tests.c create mode 100644 test/002_cube_conversion/00_solved.in create mode 100644 test/002_cube_conversion/00_solved.out create mode 100644 test/002_cube_conversion/01_scrambled.in create mode 100644 test/002_cube_conversion/01_scrambled.out create mode 100644 test/002_cube_conversion/cube_conversion_tests.c diff --git a/TODO.txt b/TODO.txt index b310e70..99e71d5 100644 --- 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 index e1a53e5..df48d7e 100644 --- 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 index 233afed..f3fe731 100644 --- 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 index 2999d8a..48885ff 100644 --- 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 index fb19355..3730e90 100644 --- 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 *); @@ -493,6 +497,43 @@ writecube_LST(cube_t cube, char *buf) *(buf+ptr-2) = 0; } +_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) { diff --git a/test/001_cube_conversion/00_solved.in b/test/001_cube_conversion/00_solved.in deleted file mode 100644 index dff224d..0000000 --- a/test/001_cube_conversion/00_solved.in +++ /dev/null @@ -1 +0,0 @@ -UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/001_cube_conversion/00_solved.out b/test/001_cube_conversion/00_solved.out deleted file mode 100644 index dff224d..0000000 --- a/test/001_cube_conversion/00_solved.out +++ /dev/null @@ -1 +0,0 @@ -UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/001_cube_conversion/01_scrambled.in b/test/001_cube_conversion/01_scrambled.in deleted file mode 100644 index 453cc8a..0000000 --- a/test/001_cube_conversion/01_scrambled.in +++ /dev/null @@ -1 +0,0 @@ -BL1 DB0 UL1 DF0 BR1 UF1 DL0 FL1 UB0 DR1 FR1 UR1 UBR2 UBL1 DFR2 DBL2 DBR0 DFL0 UFR0 UFL2 diff --git a/test/001_cube_conversion/01_scrambled.out b/test/001_cube_conversion/01_scrambled.out deleted file mode 100644 index 453cc8a..0000000 --- a/test/001_cube_conversion/01_scrambled.out +++ /dev/null @@ -1 +0,0 @@ -BL1 DB0 UL1 DF0 BR1 UF1 DL0 FL1 UB0 DR1 FR1 UR1 UBR2 UBL1 DFR2 DBL2 DBR0 DFL0 UFR0 UFL2 diff --git a/test/001_cube_conversion/cube_conversion_tests.c b/test/001_cube_conversion/cube_conversion_tests.c deleted file mode 100644 index df03eb6..0000000 --- a/test/001_cube_conversion/cube_conversion_tests.c +++ /dev/null @@ -1,25 +0,0 @@ -#include "../test.h" - -bool equal(cube_t, cube_t); - -int main(void) { - char cubestr[STRLENMAX]; - cube_t cube, cube2; - cube_fast_t fast; - - fgets(cubestr, STRLENMAX, stdin); - cube = readcube("H48", cubestr); - fast = cubetofast(cube); - cube2 = fasttocube(fast); - - if (iserror(cube)) { - printf("Error reading cube\n"); - } else if (iserror(cube2)) { - printf("Error converting cube\n"); - } else { - writecube("H48", cube2, cubestr); - printf("%s\n", cubestr); - } - - return 0; -} diff --git a/test/001_pieces/01_solved.in b/test/001_pieces/01_solved.in new file mode 100644 index 0000000..dff224d --- /dev/null +++ b/test/001_pieces/01_solved.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/001_pieces/01_solved.out b/test/001_pieces/01_solved.out new file mode 100644 index 0000000..94eb955 --- /dev/null +++ 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 new file mode 100644 index 0000000..6a05bbc --- /dev/null +++ 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 new file mode 100644 index 0000000..136336a --- /dev/null +++ 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 new file mode 100644 index 0000000..f3d8d4e --- /dev/null +++ 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/002_cube_conversion/00_solved.in b/test/002_cube_conversion/00_solved.in new file mode 100644 index 0000000..dff224d --- /dev/null +++ b/test/002_cube_conversion/00_solved.in @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/002_cube_conversion/00_solved.out b/test/002_cube_conversion/00_solved.out new file mode 100644 index 0000000..dff224d --- /dev/null +++ b/test/002_cube_conversion/00_solved.out @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/002_cube_conversion/01_scrambled.in b/test/002_cube_conversion/01_scrambled.in new file mode 100644 index 0000000..453cc8a --- /dev/null +++ b/test/002_cube_conversion/01_scrambled.in @@ -0,0 +1 @@ +BL1 DB0 UL1 DF0 BR1 UF1 DL0 FL1 UB0 DR1 FR1 UR1 UBR2 UBL1 DFR2 DBL2 DBR0 DFL0 UFR0 UFL2 diff --git a/test/002_cube_conversion/01_scrambled.out b/test/002_cube_conversion/01_scrambled.out new file mode 100644 index 0000000..453cc8a --- /dev/null +++ b/test/002_cube_conversion/01_scrambled.out @@ -0,0 +1 @@ +BL1 DB0 UL1 DF0 BR1 UF1 DL0 FL1 UB0 DR1 FR1 UR1 UBR2 UBL1 DFR2 DBL2 DBR0 DFL0 UFR0 UFL2 diff --git a/test/002_cube_conversion/cube_conversion_tests.c b/test/002_cube_conversion/cube_conversion_tests.c new file mode 100644 index 0000000..df03eb6 --- /dev/null +++ b/test/002_cube_conversion/cube_conversion_tests.c @@ -0,0 +1,25 @@ +#include "../test.h" + +bool equal(cube_t, cube_t); + +int main(void) { + char cubestr[STRLENMAX]; + cube_t cube, cube2; + cube_fast_t fast; + + fgets(cubestr, STRLENMAX, stdin); + cube = readcube("H48", cubestr); + fast = cubetofast(cube); + cube2 = fasttocube(fast); + + if (iserror(cube)) { + printf("Error reading cube\n"); + } else if (iserror(cube2)) { + printf("Error converting cube\n"); + } else { + writecube("H48", cube2, cubestr); + printf("%s\n", cubestr); + } + + return 0; +} -- cgit v1.3