From 7faca28009c5efb0ba2b897b34dbdcac47a1a6f3 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Fri, 25 Apr 2025 10:09:22 +0200 Subject: NISS --- src/core/constants.h | 76 ++++++++++++++++++++++++++++++++----------- src/core/core.h | 1 + src/core/cube.h | 8 ----- src/core/moves.h | 84 +++++++++++++++++------------------------------- src/core/oriented_cube.h | 78 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 166 insertions(+), 81 deletions(-) create mode 100644 src/core/oriented_cube.h (limited to 'src/core') diff --git a/src/core/constants.h b/src/core/constants.h index 2908f28..fb1450e 100644 --- a/src/core/constants.h +++ b/src/core/constants.h @@ -348,22 +348,22 @@ #define NMOVES_EXTENDED (1+MOVE_z3) #define NTRANS (1+TRANS_BLm) -#define MM_ALLMOVES UINT32_C(0x3FFFF) -#define MM_NOHALFTURNS UINT32_C(0x2DB6D) -#define MM_SINGLE(m) (UINT32_C(1) << (uint32_t)(m)) -#define MM_FACE(m) (UINT32_C(7) << (uint32_t)(m)) -#define MM_EO (\ - MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\ - MM_FACE(MOVE_R) | MM_FACE(MOVE_L) |\ +#define MM_SINGLE(m) (UINT64_C(1) << (uint64_t)(m)) +#define MM18_ALLMOVES UINT64_C(0x3FFFF) +#define MM18_NOHALFTURNS UINT64_C(0x2DB6D) +#define MM18_FACE(m) (UINT64_C(7) << (uint64_t)(m)) +#define MM18_EO (\ + MM18_FACE(MOVE_U) | MM18_FACE(MOVE_D) |\ + MM18_FACE(MOVE_R) | MM18_FACE(MOVE_L) |\ MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2)) -#define MM_DR (\ - MM_FACE(MOVE_U) | MM_FACE(MOVE_D) |\ +#define MM18_DR (\ + MM18_FACE(MOVE_U) | MM18_FACE(MOVE_D) |\ MM_SINGLE(MOVE_R2) | MM_SINGLE(MOVE_L2) |\ MM_SINGLE(MOVE_F2) | MM_SINGLE(MOVE_B2)) -#define MM_HTR (MM_ALLMOVES & ~MM_NOHALFTURNS) +#define MM18_HTR (MM18_ALLMOVES & ~MM18_NOHALFTURNS) -#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF) #define TM_SINGLE(t) (UINT64_C(1) << (uint64_t)(t)) +#define TM_ALLTRANS UINT64_C(0xFFFFFFFFFFFF) #define TM_UDRLFIX (\ TM_SINGLE(TRANS_UFr) | TM_SINGLE(TRANS_UBr) | TM_SINGLE(TRANS_UFm) | \ TM_SINGLE(TRANS_UBm) | TM_SINGLE(TRANS_DFr) | TM_SINGLE(TRANS_DBr) | \ @@ -423,13 +423,26 @@ #define ORIENTATION_BU UINT8_C(22) #define ORIENTATION_BL UINT8_C(23) -STATIC const uint32_t allowedmask[] = { - UINT32_C(0x3FFF8), - UINT32_C(0x3FFC0), - UINT32_C(0x3FE3F), - UINT32_C(0x3F03F), - UINT32_C(0x38FFF), - UINT32_C(0x00FFF) +/* This is only meant to work for the 18 base moves, for now */ +STATIC const uint64_t allowedmask[] = { + [MOVE_U / 3] = UINT64_C(0x3FFF8), + [MOVE_D / 3] = UINT64_C(0x3FFC0), + [MOVE_R / 3] = UINT64_C(0x3FE3F), + [MOVE_L / 3] = UINT64_C(0x3F03F), + [MOVE_F / 3] = UINT64_C(0x38FFF), + [MOVE_B / 3] = UINT64_C(0x00FFF), + [MOVE_Uw / 3] = 0, + [MOVE_Dw / 3] = 0, + [MOVE_Rw / 3] = 0, + [MOVE_Lw / 3] = 0, + [MOVE_Fw / 3] = 0, + [MOVE_Bw / 3] = 0, + [MOVE_M / 3] = 0, + [MOVE_S / 3] = 0, + [MOVE_E / 3] = 0, + [MOVE_x / 3] = 0, + [MOVE_y / 3] = 0, + [MOVE_z / 3] = 0, }; STATIC const char *cornerstr[] = { @@ -682,6 +695,33 @@ STATIC uint8_t trans_move_table[][3] = { [TRANS_BLm] = { MOVE_B, MOVE_U, MOVE_R }, }; +STATIC uint8_t orientation_moves[][3] = { + [ORIENTATION_UF] = { UINT8_MAX }, + [ORIENTATION_UR] = { MOVE_y, UINT8_MAX }, + [ORIENTATION_UB] = { MOVE_y2, UINT8_MAX }, + [ORIENTATION_UL] = { MOVE_y3, UINT8_MAX }, + [ORIENTATION_DF] = { MOVE_z2, UINT8_MAX }, + [ORIENTATION_DR] = { MOVE_y, MOVE_z2, UINT8_MAX }, + [ORIENTATION_DB] = { MOVE_y2, MOVE_z2, UINT8_MAX }, + [ORIENTATION_DL] = { MOVE_y3, MOVE_z2, UINT8_MAX }, + [ORIENTATION_RF] = { MOVE_z3, UINT8_MAX }, + [ORIENTATION_RD] = { MOVE_z3, MOVE_y, UINT8_MAX }, + [ORIENTATION_RB] = { MOVE_z3, MOVE_y2, UINT8_MAX }, + [ORIENTATION_RU] = { MOVE_z3, MOVE_y3, UINT8_MAX }, + [ORIENTATION_LF] = { MOVE_z, UINT8_MAX }, + [ORIENTATION_LD] = { MOVE_z, MOVE_y3, UINT8_MAX }, + [ORIENTATION_LB] = { MOVE_z, MOVE_y2, UINT8_MAX }, + [ORIENTATION_LU] = { MOVE_z, MOVE_y, UINT8_MAX }, + [ORIENTATION_FD] = { MOVE_x, UINT8_MAX }, + [ORIENTATION_FR] = { MOVE_x, MOVE_y, UINT8_MAX }, + [ORIENTATION_FU] = { MOVE_x, MOVE_y2, UINT8_MAX }, + [ORIENTATION_FL] = { MOVE_x, MOVE_y3, UINT8_MAX }, + [ORIENTATION_BD] = { MOVE_x3, MOVE_y2, UINT8_MAX }, + [ORIENTATION_BR] = { MOVE_x3, MOVE_y, UINT8_MAX }, + [ORIENTATION_BU] = { MOVE_x3, UINT8_MAX }, + [ORIENTATION_BL] = { MOVE_x3, MOVE_y3, UINT8_MAX }, +}; + STATIC uint8_t orientation_transition_table[][3] = { [ORIENTATION_UF] = { ORIENTATION_FD, ORIENTATION_UR, ORIENTATION_LF }, [ORIENTATION_UR] = { ORIENTATION_RD, ORIENTATION_UB, ORIENTATION_FR }, diff --git a/src/core/core.h b/src/core/core.h index b56106e..5e0faaa 100644 --- a/src/core/core.h +++ b/src/core/core.h @@ -3,3 +3,4 @@ #include "cube.h" #include "moves.h" #include "transform.h" +#include "oriented_cube.h" diff --git a/src/core/cube.h b/src/core/cube.h index 88e1ca9..842ec59 100644 --- a/src/core/cube.h +++ b/src/core/cube.h @@ -1,4 +1,3 @@ -STATIC oriented_cube_t solvedcube(void); STATIC cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]); STATIC bool isconsistent(oriented_cube_t); STATIC bool issolvable(oriented_cube_t); @@ -20,13 +19,6 @@ STATIC uint8_t b32tocorner(char); STATIC char edgetob32(uint8_t); STATIC char cornertob32(uint8_t); -/* This is used only in tests, use SOLVED_ORIENTED_CUBE everywhere else */ -STATIC oriented_cube_t -solvedcube(void) -{ - return SOLVED_ORIENTED_CUBE; -} - STATIC cube_t cubefromarray(uint8_t c[static 8], uint8_t e[static 12]) { diff --git a/src/core/moves.h b/src/core/moves.h index dc580be..008e928 100644 --- a/src/core/moves.h +++ b/src/core/moves.h @@ -2,7 +2,8 @@ #define PREMOVE(M, c) compose(MOVE_CUBE_ ## M, c) STATIC uint8_t readmove(char); -STATIC int64_t readmoves(const char *, size_t n, uint8_t [n]); +STATIC int64_t readmoves(const char *, + size_t n, size_t m, uint64_t *, uint64_t *, uint8_t [n], uint8_t [m]); STATIC int64_t countmoves(const char *); STATIC uint8_t readmodifier(char); STATIC int64_t writemoves(size_t n, const uint8_t [n], size_t m, char [m]); @@ -21,14 +22,11 @@ STATIC_INLINE uint8_t movefollow(uint8_t); STATIC uint8_t transform_move(uint8_t, uint8_t); STATIC cube_t move(cube_t, uint8_t); -STATIC oriented_cube_t move_extended(oriented_cube_t, uint8_t); STATIC cube_t premove(cube_t, uint8_t); STATIC uint8_t inverse_move(uint8_t); STATIC void sortparallel_moves(size_t n, uint8_t [n]); STATIC bool are_lastmoves_singlecw(size_t n, const uint8_t [n]); -STATIC oriented_cube_t applymoves(oriented_cube_t, const char *); - #define FOREACH_READMOVE(ARG_BUF, ARG_MOVE, ARG_C, ARG_MAX, \ RET_ERROR, ARG_ACTION) \ const char *VAR_B; \ @@ -118,14 +116,34 @@ readmodifier(char c) } STATIC int64_t -readmoves(const char *buf, size_t n, uint8_t ret[n]) +readmoves( + const char *buf, + size_t nsize, + size_t invsize, + uint64_t *n, + uint64_t *i, + uint8_t normal[nsize], + uint8_t inverse[invsize] +) { -// TODO: modify to accept NISS uint8_t m; uint64_t c; - FOREACH_READMOVE(buf, m, c, n, NISSY_ERROR_INVALID_MOVES, - ret[c] = m; + *n = *i = 0; + FOREACH_READMOVE(buf, m, c, nsize+invsize, NISSY_ERROR_INVALID_MOVES, + if (!VAR_IN_PARENTHESES) { + if (*n >= nsize-1) { + LOG("Error in readmoves: normal buffer\n"); + return NISSY_ERROR_BUFFER_SIZE; + } + normal[(*n)++] = m; + } else { + if (*i >= invsize-1) { + LOG("Error in readmoves: inverse buffer\n"); + return NISSY_ERROR_BUFFER_SIZE; + } + inverse[(*i)++] = m; + } ) return (int64_t)c; @@ -188,9 +206,7 @@ writemoves_error: STATIC_INLINE bool allowednextmove(uint8_t m1, uint8_t m2) { -// TODO: adjust allowedmask -// TODO: movemask is now 64 bits - return allowedmask[movebase(m1)] & (UINT32_C(1) << m2); + return allowedmask[movebase(m1)] & MM_SINGLE(m2); } STATIC bool @@ -226,9 +242,7 @@ isbase(uint8_t move) STATIC_INLINE bool parallel(uint8_t m1, uint8_t m2) { -// TODO add unit tests -//TODO fix the logic (maybe use moveaxis(movefollow)), then remove comment - return moveaxis(m1) == moveaxis(m2); + return moveaxis(movefollow(m1)) == moveaxis(movefollow(m2)); } STATIC_INLINE uint8_t @@ -249,7 +263,6 @@ inverse_reorient_move(uint8_t m, uint8_t or) return transform_move(m, inverse_trans_table[orientation_trans[or]]); } -/* This is currently unused, but it may turn out to be useful at some point */ STATIC_INLINE uint8_t movefollow(uint8_t move) { @@ -351,27 +364,6 @@ transform_move(uint8_t m, uint8_t t) return base + modifier; } -STATIC oriented_cube_t -move_extended(oriented_cube_t c, uint8_t m) -{ - int i; - equivalent_moves_t eqm; - oriented_cube_t ret; - - eqm = equivalent_moves_table[m]; - ret = c; - - for (i = 0; eqm.move[i] != UINT8_MAX; i++) - ret.cube = move( - ret.cube, reorient_move(eqm.move[i], ret.orientation)); - - for (i = 0; eqm.rotation[i] != UINT8_MAX; i++) - ret.orientation = orientation_transition_table[ - ret.orientation][eqm.rotation[i]]; - - return ret; -} - /* Applies the INVERSE of m BEFORE the scramble corresponding to c */ STATIC cube_t premove(cube_t c, uint8_t m) @@ -428,15 +420,13 @@ inverse_move(uint8_t m) STATIC void sortparallel_moves(size_t n, uint8_t moves[n]) { -// TODO: fix for wide moves... uint8_t i; if (n < 2) return; for (i = 0; i < n-1; i++) - if (moveaxis(moves[i]) == moveaxis(moves[i+1]) && - movebase(moves[i]) == movebase(moves[i+1]) + 1) + if (parallel(moves[i], moves[i+1]) && moves[i] > moves[i+1]) SWAP(moves[i], moves[i+1]); } @@ -452,19 +442,3 @@ are_lastmoves_singlecw(size_t n, const uint8_t moves[n]) return isbase(moves[n-1]) && (!two || isbase(moves[n-2])); } - -STATIC oriented_cube_t -applymoves(oriented_cube_t cube, const char *buf) -{ - int c; - uint8_t m; - - DBG_ASSERT(isconsistent(cube), ZERO_ORIENTED_CUBE, - "move error: inconsistent cube\n"); - - FOREACH_READMOVE(buf, m, c, -1, ZERO_ORIENTED_CUBE, - cube = move_extended(cube, m); - ) - - return cube; -} diff --git a/src/core/oriented_cube.h b/src/core/oriented_cube.h new file mode 100644 index 0000000..2c86af0 --- /dev/null +++ b/src/core/oriented_cube.h @@ -0,0 +1,78 @@ +STATIC oriented_cube_t solvedcube(void); + +STATIC oriented_cube_t move_extended(oriented_cube_t, uint8_t); +STATIC oriented_cube_t applymoves(oriented_cube_t, const char *); + +/* This is used only in tests, use SOLVED_ORIENTED_CUBE everywhere else */ +STATIC oriented_cube_t +solvedcube(void) +{ + return SOLVED_ORIENTED_CUBE; +} + +STATIC oriented_cube_t +compose_oriented(oriented_cube_t c, oriented_cube_t d) +{ + int i; + cube_t transformed_d; + oriented_cube_t ret; + + transformed_d = transform(d.cube, orientation_trans[c.orientation]); + + ret.cube = compose(c.cube, transformed_d); + ret.orientation = c.orientation; + + for (i = 0; orientation_moves[d.orientation][i] != UINT8_MAX; i++) + ret = move_extended(ret, orientation_moves[d.orientation][i]); + + return ret; +} + +STATIC oriented_cube_t +move_extended(oriented_cube_t c, uint8_t m) +{ + int i; + equivalent_moves_t eqm; + oriented_cube_t ret; + + eqm = equivalent_moves_table[m]; + ret = c; + + for (i = 0; eqm.move[i] != UINT8_MAX; i++) + ret.cube = move( + ret.cube, reorient_move(eqm.move[i], ret.orientation)); + + for (i = 0; eqm.rotation[i] != UINT8_MAX; i++) + ret.orientation = orientation_transition_table[ + ret.orientation][eqm.rotation[i]]; + + return ret; +} + +STATIC oriented_cube_t +applymoves(oriented_cube_t cube, const char *buf) +{ + int count; + uint8_t m; + oriented_cube_t c, cinv; + + DBG_ASSERT(isconsistent(cube), ZERO_ORIENTED_CUBE, + "move error: inconsistent cube\n"); + + c = cube; + cinv = SOLVED_ORIENTED_CUBE; + FOREACH_READMOVE(buf, m, count, -1, ZERO_ORIENTED_CUBE, + if (!VAR_IN_PARENTHESES) + c = move_extended(c, m); + else + cinv = move_extended(cinv, m); + ) + + if (cinv.orientation != ORIENTATION_UF) { + LOG("Error applying moves: NISS part must not move centers\n"); + return ZERO_ORIENTED_CUBE; + } + + cinv.cube = inverse(cinv.cube); + return compose_oriented(cinv, c); +} -- cgit v1.3