From c9e2d6466e42d6b779ac9ffa7c5ee9a9c7558df8 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 3 Sep 2024 21:52:16 +0200 Subject: Moved stuff around --- src/core/cube.h | 66 ------------------------------ src/core/moves.h | 88 ++++++++++++++++++++-------------------- src/core/transform.h | 18 ++++++++ src/core/transform_with_switch.h | 18 ++++++++ src/solvers/h48/solve.h | 46 +++++++++++++++++---- src/utils/constants.h | 7 ++++ 6 files changed, 124 insertions(+), 119 deletions(-) (limited to 'src') diff --git a/src/core/cube.h b/src/core/cube.h index 4b28103..df5161a 100644 --- 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 index 8f9c8f5..71ef470 100644 --- 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 index 358b051..fa7ce59 100644 --- 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 index d3a108c..429e656 100644 --- 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 index bbe59e5..3878498 100644 --- 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 index 52e2810..34b4f00 100644 --- 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) -- cgit v1.3