commit c9e2d6466e42d6b779ac9ffa7c5ee9a9c7558df8 parent ff4bde84872ec0b93f0f097f5a56bd5e7cbb0311 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue, 3 Sep 2024 21:52:16 +0200 Moved stuff around Diffstat:
29 files changed, 168 insertions(+), 160 deletions(-)
diff --git a/configure.sh b/configure.sh @@ -16,15 +16,18 @@ detectsan() { TYPE=${TYPE-"$detected"} STD="-std=c99" -WFLAGS="-pedantic -Wall -Wextra -Wno-unused-parameter -Wno-unused-function" +WFLAGS="-pedantic -Wall -Wextra" +# -Wstringop-overflow seems to be causing problems when combined with -O3 +# Someone else complained here: https://access.redhat.com/solutions/6755371 +WNOFLAGS="-Wno-unused-parameter -Wno-unused-function -Wno-stringop-overflow" [ "$TYPE" = "AVX2" ] && AVX="-mavx2" [ -n "$(detectsan address)" ] && ADDR="-fsanitize=address" [ -n "$(detectsan undefined)" ] && UNDEF="-fsanitize=undefined" SAN="$ADDR $UNDEF" LIBS="-lpthread" -CFLAGS="$STD $LIBS $WFLAGS $AVX -O3" -DBGFLAGS="$STD $LIBS $WFLAGS $SAN $AVX -g3 -DDEBUG" +CFLAGS="$STD $LIBS $WFLAGS $WNOFLAGS $AVX -O3" +DBGFLAGS="$STD $LIBS $WFLAGS $WNOFLAGS $SAN $AVX -g3 -DDEBUG" echo "Cube type: CUBE_$TYPE" echo "Compiler: ${CC:-cc}" diff --git a/src/core/cube.h b/src/core/cube.h @@ -1,25 +1,12 @@ -#define _move(M, c) compose(c, _move_cube_ ## M) -#define _premove(M, c) compose(_move_cube_ ## M, c) - _static cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]); _static cube_t solvedcube(void); _static bool isconsistent(cube_t); _static bool issolvable(cube_t); _static bool issolved(cube_t); _static bool iserror(cube_t); -_static cube_t applymoves(cube_t, const char *); -_static cube_t applytrans(cube_t, const char *); -_static cube_t frommoves(const char *); _static void getcube_fix(int64_t *, int64_t *, int64_t *, int64_t *); _static cube_t getcube(int64_t, int64_t, int64_t, int64_t); -_static cube_t transform_edges(cube_t, uint8_t); -_static cube_t transform_corners(cube_t, uint8_t); -_static cube_t transform(cube_t, uint8_t); - -/* declared in moves.h */ -_static cube_t move(cube_t, uint8_t); - _static cube_t cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) { @@ -149,41 +136,6 @@ iserror(cube_t cube) return equal(cube, zero); } -_static cube_t -applymoves(cube_t cube, const char *buf) -{ - uint8_t r, m; - const char *b; - - DBG_ASSERT(isconsistent(cube), zero, - "move error: inconsistent cube\n"); - - for (b = buf; *b != '\0'; b++) { - while (*b == ' ' || *b == '\t' || *b == '\n') - b++; - if (*b == '\0') - goto applymoves_finish; - if ((r = readmove(*b)) == _error) - goto applymoves_error; - if ((m = readmodifier(*(b+1))) != 0) - b++; - cube = move(cube, r + m); - } - -applymoves_finish: - return cube; - -applymoves_error: - LOG("applymoves error\n"); - return zero; -} - -_static cube_t -frommoves(const char *buf) -{ - return applymoves(solved, buf); -} - _static void getcube_fix(int64_t *ep, int64_t *eo, int64_t *cp, int64_t *co) { @@ -227,21 +179,3 @@ getcube(int64_t ep, int64_t eo, int64_t cp, int64_t co) return cubefromarray(carr, earr); } - -_static cube_t -applytrans(cube_t cube, const char *buf) -{ - uint8_t t; - - DBG_ASSERT(isconsistent(cube), zero, - "transformation error: inconsistent cube\n"); - - t = readtrans(buf); - - return transform(cube, t); -} - -/* -TODO transform is now relegated to a separated file because it is too long. -It would be nice to make it shorter without loosing performance. -*/ diff --git a/src/core/moves.h b/src/core/moves.h @@ -1,13 +1,7 @@ -/* probably these can be placed in constants file */ -#define NORMAL 0x00 -#define INVERSE 0x01 -#define INVERSEBRANCH 0x03 -#define NORMALBRANCH 0x02 -#define ALLMOVES 0x3FFFF -#define NOHALFTURNS 0x2DB6D +#define _move(M, c) compose(c, _move_cube_ ## M) +#define _premove(M, c) compose(_move_cube_ ## M, c) _static_inline bool allowednextmove(uint8_t *, uint8_t); -_static uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t); _static_inline uint8_t inverse_trans(uint8_t); _static_inline uint8_t movebase(uint8_t); @@ -17,7 +11,10 @@ _static_inline uint32_t disable_moves(uint32_t, uint8_t); _static cube_t move(cube_t, uint8_t); _static cube_t premove(cube_t, uint8_t); _static uint8_t inverse_move(uint8_t); -_static uint8_t* invertpremoves(uint8_t *, uint8_t); +_static void invertmoves(uint8_t *, uint8_t, uint8_t *); + +_static cube_t applymoves(cube_t, const char *); +_static cube_t frommoves(const char *); _static bool allowednextmove(uint8_t *moves, uint8_t n) @@ -50,34 +47,6 @@ disable_moves(uint32_t current_result, uint8_t base_index) return current_result & ~(7 << base_index); } -_static uint32_t -allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch) -{ - uint32_t result = ALLMOVES; - if (h48branch & NORMALBRANCH) - result &= NOHALFTURNS; - if (n < 1) - return result; - - uint8_t base1 = movebase(moves[n-1]); - uint8_t axis1 = moveaxis(moves[n-1]); - - result = disable_moves(result, base1 * 3); - if (base1 % 2) - result = disable_moves(result, (base1 - 1) * 3); - - if (n == 1) - return result; - - uint8_t base2 = movebase(moves[n-2]); - uint8_t axis2 = moveaxis(moves[n-2]); - - if(axis1 == axis2) - result = disable_moves(result, base2 * 3); - - return result; -} - _static_inline uint8_t inverse_trans(uint8_t t) { @@ -194,17 +163,46 @@ inverse_move(uint8_t m) return m - 2 * (m % 3) + 2; } -_static uint8_t* -invertpremoves(uint8_t *moves, uint8_t nmoves) +_static void +invertmoves(uint8_t *moves, uint8_t nmoves, uint8_t *ret) { uint8_t i; - uint8_t *ret = malloc(nmoves * sizeof(uint8_t)); for (i = 0; i < nmoves; i++) - ret[i] = inverse_move(moves[i]); + ret[i] = inverse_move(moves[nmoves - i - 1]); +} - // invert elements in the array - for (i = 0; i < nmoves / 2; i++) - _swap(ret[i], ret[nmoves - i - 1]); - return ret; +_static cube_t +applymoves(cube_t cube, const char *buf) +{ + uint8_t r, m; + const char *b; + + DBG_ASSERT(isconsistent(cube), zero, + "move error: inconsistent cube\n"); + + for (b = buf; *b != '\0'; b++) { + while (*b == ' ' || *b == '\t' || *b == '\n') + b++; + if (*b == '\0') + goto applymoves_finish; + if ((r = readmove(*b)) == _error) + goto applymoves_error; + if ((m = readmodifier(*(b+1))) != 0) + b++; + cube = move(cube, r + m); + } + +applymoves_finish: + return cube; + +applymoves_error: + LOG("applymoves error\n"); + return zero; +} + +_static cube_t +frommoves(const char *buf) +{ + return applymoves(solved, buf); } diff --git a/src/core/transform.h b/src/core/transform.h @@ -19,6 +19,11 @@ invertco(compose(compose(_trans_cube_ ## T, c), \ _trans_cube_ ## T ## _inverse)) +_static cube_t transform_edges(cube_t, uint8_t); +_static cube_t transform_corners(cube_t, uint8_t); +_static cube_t transform(cube_t, uint8_t); +_static cube_t applytrans(cube_t, const char *); + static cube_t cube_trans_table[48] = { [_trans_UFr] = _trans_cube_UFr, [_trans_UFm] = _trans_cube_UFm, @@ -174,3 +179,16 @@ transform(cube_t c, uint8_t t) return t < 24 ? ret : invertco(ret); } + +_static cube_t +applytrans(cube_t cube, const char *buf) +{ + uint8_t t; + + DBG_ASSERT(isconsistent(cube), zero, + "transformation error: inconsistent cube\n"); + + t = readtrans(buf); + + return transform(cube, t); +} diff --git a/src/core/transform_with_switch.h b/src/core/transform_with_switch.h @@ -17,6 +17,11 @@ invertco(compose(compose(_trans_cube_ ## T, c), \ _trans_cube_ ## T ## _inverse)) +_static cube_t transform_edges(cube_t, uint8_t); +_static cube_t transform_corners(cube_t, uint8_t); +_static cube_t transform(cube_t, uint8_t); +_static cube_t applytrans(cube_t, const char *); + _static cube_t transform_edges(cube_t c, uint8_t t) { @@ -334,3 +339,16 @@ transform(cube_t c, uint8_t t) return zero; } } + +_static cube_t +applytrans(cube_t cube, const char *buf) +{ + uint8_t t; + + DBG_ASSERT(isconsistent(cube), zero, + "transformation error: inconsistent cube\n"); + + t = readtrans(buf); + + return transform(cube, t); +} diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h @@ -26,6 +26,8 @@ typedef struct { char *s; } dfsarg_solveh48stats_t; +_static uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint32_t); + _static void solve_h48_appendsolution(dfsarg_solveh48_t *); _static_inline bool solve_h48_stop(dfsarg_solveh48_t *); _static int64_t solve_h48_dfs(dfsarg_solveh48_t *); @@ -34,10 +36,39 @@ _static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_t, uint8_t, cons _static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); _static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); +_static uint32_t +allowednextmove_h48(uint8_t *moves, uint8_t n, uint32_t h48branch) +{ + uint32_t result = _mm_allmoves; + if (h48branch & _mm_normalbranch) + result &= _mm_nohalfturns; + if (n < 1) + return result; + + uint8_t base1 = movebase(moves[n-1]); + uint8_t axis1 = moveaxis(moves[n-1]); + + result = disable_moves(result, base1 * 3); + if (base1 % 2) + result = disable_moves(result, (base1 - 1) * 3); + + if (n == 1) + return result; + + uint8_t base2 = movebase(moves[n-2]); + uint8_t axis2 = moveaxis(moves[n-2]); + + if(axis1 == axis2) + result = disable_moves(result, base2 * 3); + + return result; +} + _static void solve_h48_appendsolution(dfsarg_solveh48_t *arg) { int strl; + uint8_t invertedpremoves[MAXLEN]; char *solution = *arg->nextsol; strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); @@ -47,9 +78,8 @@ solve_h48_appendsolution(dfsarg_solveh48_t *arg) **arg->nextsol = ' '; (*arg->nextsol)++; - uint8_t* invertedpremoves = invertpremoves(arg->premoves, arg->npremoves); + invertmoves(arg->premoves, arg->npremoves, invertedpremoves); strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); - free(invertedpremoves); *arg->nextsol += strl; } LOG("Solution found: %s\n", solution); @@ -65,7 +95,7 @@ solve_h48_stop(dfsarg_solveh48_t *arg) uint32_t data, data_inv; int8_t bound; - arg->nissbranch = NORMAL; + arg->nissbranch = _mm_normal; bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data); if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; @@ -79,13 +109,13 @@ solve_h48_stop(dfsarg_solveh48_t *arg) if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; if (bound + arg->nmoves + arg->npremoves == arg->depth) - arg->nissbranch = INVERSEBRANCH; + arg->nissbranch = _mm_inversebranch; bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data); if (bound + arg->nmoves + arg->npremoves > arg->depth) return true; if (bound + arg->nmoves + arg->npremoves == arg->depth) - arg->nissbranch = NORMALBRANCH; + arg->nissbranch = _mm_normalbranch; return false; } @@ -114,8 +144,8 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) nextarg = *arg; ret = 0; uint32_t allowed; - if(arg->nissbranch & INVERSE) { - allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch); + if(arg->nissbranch & _mm_inverse) { + allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); for (m = 0; m < 18; m++) { if(allowed & (1 << m)) { nextarg.npremoves = arg->npremoves + 1; @@ -126,7 +156,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg) } } } else { - allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch); + allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); for (m = 0; m < 18; m++) { if (allowed & (1 << m)) { nextarg.nmoves = arg->nmoves + 1; diff --git a/src/utils/constants.h b/src/utils/constants.h @@ -97,6 +97,13 @@ _static int64_t binomial[12][12] = { #define _trans_BDm UINT8_C(46) #define _trans_BLm UINT8_C(47) +#define _mm_normal UINT32_C(0x00) +#define _mm_inverse UINT32_C(0x01) +#define _mm_inversebranch UINT32_C(0x03) +#define _mm_normalbranch UINT32_C(0x02) +#define _mm_allmoves UINT32_C(0x3FFFF) +#define _mm_nohalfturns UINT32_C(0x2DB6D) + #define _c_ufr UINT8_C(0) #define _c_ubl UINT8_C(1) #define _c_dfl UINT8_C(2) diff --git a/test/082_allowednext_h48/allowednext_h48_tests.c b/test/082_allowednext_h48/allowednext_h48_tests.c @@ -1,38 +0,0 @@ -#include "../test.h" - -uint32_t allowednextmoveH48(uint8_t *, uint8_t, uint32_t); - -static char *moves[] = { - "U", "U2", "U'", - "D", "D2", "D'", - "R", "R2", "R'", - "L", "L2", "L'", - "F", "F2", "F'", - "B", "B2", "B'", -}; - -void run(void) { - char movestr[STRLENMAX]; - uint8_t m[100]; - int n, i, j, bound; - - fgets(movestr, STRLENMAX, stdin); - bound = atoi(movestr); - - fgets(movestr, STRLENMAX, stdin); - n = atoi(movestr); - - for (i = 0; i < n; i++) { - fgets(movestr, STRLENMAX, stdin); - movestr[strcspn(movestr, "\n")] = 0; - for (j = 0; j < 18; j++) - if (!strcmp(movestr, moves[j])) - m[i] = j; - } - - fprintf(stderr, "Last two: %s, %s\n", - n > 1 ? moves[m[n-2]] : "-", - n > 0 ? moves[m[n-1]] : "-"); - uint32_t allowed = allowednextmoveH48(m, n, bound); - printf("0x%05X\n", allowed); -} diff --git a/test/082_allowednext_h48/00_empty_U.in b/test/130_allowednext_h48/00_empty_U.in diff --git a/test/082_allowednext_h48/00_empty_U.out b/test/130_allowednext_h48/00_empty_U.out diff --git a/test/082_allowednext_h48/01_F.in b/test/130_allowednext_h48/01_F.in diff --git a/test/082_allowednext_h48/01_F.out b/test/130_allowednext_h48/01_F.out diff --git a/test/082_allowednext_h48/02_U2.in b/test/130_allowednext_h48/02_U2.in diff --git a/test/082_allowednext_h48/02_U2.out b/test/130_allowednext_h48/02_U2.out diff --git a/test/082_allowednext_h48/03_R_L.in b/test/130_allowednext_h48/03_R_L.in diff --git a/test/082_allowednext_h48/03_R_L.out b/test/130_allowednext_h48/03_R_L.out diff --git a/test/082_allowednext_h48/04_D.in b/test/130_allowednext_h48/04_D.in diff --git a/test/082_allowednext_h48/04_D.out b/test/130_allowednext_h48/04_D.out diff --git a/test/082_allowednext_h48/05_U_F_B2.in b/test/130_allowednext_h48/05_U_F_B2.in diff --git a/test/082_allowednext_h48/05_U_F_B2.out b/test/130_allowednext_h48/05_U_F_B2.out diff --git a/test/082_allowednext_h48/06_empty_bound.in b/test/130_allowednext_h48/06_empty_bound.in diff --git a/test/082_allowednext_h48/06_empty_bound.out b/test/130_allowednext_h48/06_empty_bound.out diff --git a/test/082_allowednext_h48/07_F_bound.in b/test/130_allowednext_h48/07_F_bound.in diff --git a/test/082_allowednext_h48/07_F_bound.out b/test/130_allowednext_h48/07_F_bound.out diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.in b/test/130_allowednext_h48/08_U_D_bound_inverse.in diff --git a/test/082_allowednext_h48/08_U_D_bound_inverse.out b/test/130_allowednext_h48/08_U_D_bound_inverse.out diff --git a/test/082_allowednext_h48/09_R_false_bound.in b/test/130_allowednext_h48/09_R_false_bound.in diff --git a/test/082_allowednext_h48/09_R_false_bound.out b/test/130_allowednext_h48/09_R_false_bound.out diff --git a/test/130_allowednext_h48/allowednext_h48_tests.c b/test/130_allowednext_h48/allowednext_h48_tests.c @@ -0,0 +1,38 @@ +#include "../test.h" + +uint32_t allowednextmove_h48(uint8_t *, uint8_t, uint32_t); + +static char *moves[] = { + "U", "U2", "U'", + "D", "D2", "D'", + "R", "R2", "R'", + "L", "L2", "L'", + "F", "F2", "F'", + "B", "B2", "B'", +}; + +void run(void) { + char movestr[STRLENMAX]; + uint8_t m[100]; + int n, i, j, bound; + + fgets(movestr, STRLENMAX, stdin); + bound = atoi(movestr); + + fgets(movestr, STRLENMAX, stdin); + n = atoi(movestr); + + for (i = 0; i < n; i++) { + fgets(movestr, STRLENMAX, stdin); + movestr[strcspn(movestr, "\n")] = 0; + for (j = 0; j < 18; j++) + if (!strcmp(movestr, moves[j])) + m[i] = j; + } + + fprintf(stderr, "Last two: %s, %s\n", + n > 1 ? moves[m[n-2]] : "-", + n > 0 ? moves[m[n-1]] : "-"); + uint32_t allowed = allowednextmove_h48(m, n, bound); + printf("0x%05X\n", allowed); +}