nissbranch ver1

4 files changed, 201 insertions, 202 deletions

diff --git a/.gitignore b/.gitignore
index 236d875..c2ff877 100644
--- a/.gitignore
+++ b/.gitignore
@@ -7,6 +7,7 @@ run
 tables/*
 test/*/runtest
 test/run
+test/run.DSYM
 run.DSYM
 test/last.*
 tools/results
diff --git a/src/core/cube.h b/src/core/cube.h
index b24fb5c..4b28103 100644
--- a/src/core/cube.h
+++ b/src/core/cube.h
@@ -13,11 +13,13 @@ _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 move(cube_t, uint8_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])
 {
@@ -239,159 +241,6 @@ applytrans(cube_t cube, const char *buf)
         return transform(cube, t);
 }
 
-_static cube_t
-move(cube_t c, uint8_t m)
-{
-        switch (m) {
-        case _move_U:
-                return _move(U, c);
-        case _move_U2:
-                return _move(U2, c);
-        case _move_U3:
-                return _move(U3, c);
-        case _move_D:
-                return _move(D, c);
-        case _move_D2:
-                return _move(D2, c);
-        case _move_D3:
-                return _move(D3, c);
-        case _move_R:
-                return _move(R, c);
-        case _move_R2:
-                return _move(R2, c);
-        case _move_R3:
-                return _move(R3, c);
-        case _move_L:
-                return _move(L, c);
-        case _move_L2:
-                return _move(L2, c);
-        case _move_L3:
-                return _move(L3, c);
-        case _move_F:
-                return _move(F, c);
-        case _move_F2:
-                return _move(F2, c);
-        case _move_F3:
-                return _move(F3, c);
-        case _move_B:
-                return _move(B, c);
-        case _move_B2:
-                return _move(B2, c);
-        case _move_B3:
-                return _move(B3, c);
-        default:
-                LOG("move error, unknown move\n");
-                return zero;
-        }
-}
-
-_static cube_t
-premove(cube_t c, uint8_t m){
-                switch (m) {
-        case _move_U:
-                return _premove(U3, c);
-        case _move_U2:
-                return _premove(U2, c);
-        case _move_U3:
-                return _premove(U, c);
-        case _move_D:
-                return _premove(D3, c);
-        case _move_D2:
-                return _premove(D2, c);
-        case _move_D3:
-                return _premove(D, c);
-        case _move_R:
-                return _premove(R3, c);
-        case _move_R2:
-                return _premove(R2, c);
-        case _move_R3:
-                return _premove(R, c);
-        case _move_L:
-                return _premove(L3, c);
-        case _move_L2:
-                return _premove(L2, c);
-        case _move_L3:
-                return _premove(L, c);
-        case _move_F:
-                return _premove(F3, c);
-        case _move_F2:
-                return _premove(F2, c);
-        case _move_F3:
-                return _premove(F, c);
-        case _move_B:
-                return _premove(B3, c);
-        case _move_B2:
-                return _premove(B2, c);
-        case _move_B3:
-                return _premove(B, c);
-        default:
-                LOG("move error, unknown move\n");
-                return zero;
-        }
-}
-_static uint8_t
-invertmove(uint8_t m)
-{
-        switch (m) {
-        case _move_U:
-                return _move_U3;
-        case _move_U2:
-                return _move_U2;
-        case _move_U3:
-                return _move_U;
-        case _move_D:
-                return _move_D3;
-        case _move_D2:
-                return _move_D2;
-        case _move_D3:
-                return _move_D;
-        case _move_R:
-                return _move_R3;
-        case _move_R2:
-                return _move_R2;
-        case _move_R3:
-                return _move_R;
-        case _move_L:
-                return _move_L3;
-        case _move_L2:
-                return _move_L2;
-        case _move_L3:
-                return _move_L;
-        case _move_F:
-                return _move_F3;
-        case _move_F2:
-                return _move_F2;
-        case _move_F3:
-                return _move_F;
-        case _move_B:
-                return _move_B3;
-        case _move_B2:
-                return _move_B2;
-        case _move_B3:
-                return _move_B;
-        default:
-                LOG("invertmove error, unknown move\n");
-                return _error;
-        }
-}
-
-_static uint8_t*
-invertpremoves(uint8_t *moves, uint8_t nmoves)
-{
-        uint8_t i;
-        uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
-
-        for (i = 0; i < nmoves; i++)
-                ret[i] = invertmove(moves[i]);
-
-        // invert elements in the array
-        for (i = 0; i < nmoves / 2; i++)
-                _swap(ret[i], ret[nmoves - i - 1]);
-        return ret;
-}
-
-
-
 /*
 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 7da6405..726a452 100644
--- a/src/core/moves.h
+++ b/src/core/moves.h
@@ -1,8 +1,23 @@
+/* probably these can be placed in constants file */
+#define NONISS 0x00
+#define NISS 0x01
+#define INVERSEBRANCH 0x03
+#define BRANCH 0x02
+#define ALLMOVES 0x3FFFF
+#define NOHALFTURNS 0x2DB6D
+
 _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);
 _static_inline uint8_t moveaxis(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 bool
 allowednextmove(uint8_t *moves, uint8_t n)
 {
@@ -28,6 +43,40 @@ allowednextmove(uint8_t *moves, uint8_t n)
         return axis[1] != axis[2] || base[0] != base[2];
 }
 
+static uint32_t 
+disable_moves(uint32_t current_result, uint8_t base_index)
+{
+        return current_result & ~((1 << base_index) | (1 << (base_index + 1)) | (1 << (base_index + 2)));
+}
+
+_static uint32_t
+allowednextmoveH48(uint8_t *moves, uint8_t n, uint32_t h48branch)
+{
+        uint32_t result = ALLMOVES;
+        if (h48branch & BRANCH)
+                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 >= 9)
+                result = disable_moves(result, (base1 * 3) - 9);
+
+        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)
 {
@@ -45,3 +94,116 @@ moveaxis(uint8_t move)
 {
         return move / 6;
 }
+
+_static cube_t
+move(cube_t c, uint8_t m)
+{
+        switch (m) {
+        case _move_U:
+                return _move(U, c);
+        case _move_U2:
+                return _move(U2, c);
+        case _move_U3:
+                return _move(U3, c);
+        case _move_D:
+                return _move(D, c);
+        case _move_D2:
+                return _move(D2, c);
+        case _move_D3:
+                return _move(D3, c);
+        case _move_R:
+                return _move(R, c);
+        case _move_R2:
+                return _move(R2, c);
+        case _move_R3:
+                return _move(R3, c);
+        case _move_L:
+                return _move(L, c);
+        case _move_L2:
+                return _move(L2, c);
+        case _move_L3:
+                return _move(L3, c);
+        case _move_F:
+                return _move(F, c);
+        case _move_F2:
+                return _move(F2, c);
+        case _move_F3:
+                return _move(F3, c);
+        case _move_B:
+                return _move(B, c);
+        case _move_B2:
+                return _move(B2, c);
+        case _move_B3:
+                return _move(B3, c);
+        default:
+                LOG("move error, unknown move\n");
+                return zero;
+        }
+}
+
+_static cube_t
+premove(cube_t c, uint8_t m)
+{
+                switch (m) {
+        case _move_U:
+                return _premove(U3, c);
+        case _move_U2:
+                return _premove(U2, c);
+        case _move_U3:
+                return _premove(U, c);
+        case _move_D:
+                return _premove(D3, c);
+        case _move_D2:
+                return _premove(D2, c);
+        case _move_D3:
+                return _premove(D, c);
+        case _move_R:
+                return _premove(R3, c);
+        case _move_R2:
+                return _premove(R2, c);
+        case _move_R3:
+                return _premove(R, c);
+        case _move_L:
+                return _premove(L3, c);
+        case _move_L2:
+                return _premove(L2, c);
+        case _move_L3:
+                return _premove(L, c);
+        case _move_F:
+                return _premove(F3, c);
+        case _move_F2:
+                return _premove(F2, c);
+        case _move_F3:
+                return _premove(F, c);
+        case _move_B:
+                return _premove(B3, c);
+        case _move_B2:
+                return _premove(B2, c);
+        case _move_B3:
+                return _premove(B, c);
+        default:
+                LOG("move error, unknown move\n");
+                return zero;
+        }
+}
+
+_static uint8_t
+inverse_move(uint8_t m)
+{
+        return m - 2 * (m % 3) + 2;     
+}
+
+_static uint8_t*
+invertpremoves(uint8_t *moves, uint8_t nmoves)
+{
+        uint8_t i;
+        uint8_t *ret = malloc(nmoves * sizeof(uint8_t));
+
+        for (i = 0; i < nmoves; i++)
+                ret[i] = inverse_move(moves[i]);
+
+        // invert elements in the array
+        for (i = 0; i < nmoves / 2; i++)
+                _swap(ret[i], ret[nmoves - i - 1]);
+        return ret;
+}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 7430228..751df8f 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -11,10 +11,9 @@ typedef struct {
         uint32_t *cocsepdata;
         uint32_t *h48data;
         char **nextsol;
-        bool niss;
+        uint8_t nissbranch;
         int8_t npremoves;
         uint8_t premoves[MAXLEN];
-        int8_t totmoves;
 } dfsarg_solveh48_t;
 
 typedef struct {
@@ -65,37 +64,30 @@ _static_inline bool
 solve_h48_stop(dfsarg_solveh48_t *arg)
 {
         uint32_t data, data_inv;
-        int8_t bound, newbound;
-        bool niss = false;
+        int8_t bound;
 
+        arg->nissbranch = NONISS;
         bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
-        if (bound + arg->totmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
 
-        newbound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
-        if (newbound + arg->totmoves > arg->depth)
+        bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
-        if (newbound < bound) {
-                bound = newbound;
-                niss = true;
-        }
 
-        newbound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
+        bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data);
         // LOG("Using pval %" PRId8 "\n", bound);
-        if (newbound + arg->totmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves > arg->depth)
                 return true;
-        if (newbound < bound) {
-                bound = newbound;
-                niss = false;
-        }
-        newbound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data);
-        if (newbound + arg->totmoves > arg->depth)
+        if (bound + arg->nmoves + arg->npremoves == arg->depth)
+                arg->nissbranch = 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 (newbound < bound) {
-                bound = newbound;
-                niss = true;
-        }
-        arg->niss = niss;
+        if (bound + arg->nmoves + arg->npremoves == arg->depth)
+                arg->nissbranch = BRANCH;
+
         return false;
 }
 
@@ -113,7 +105,7 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
                 return 0;
 
         if (issolved(arg->cube)) {
-                if (arg->totmoves != arg->depth)
+                if (arg->nmoves + arg->npremoves != arg->depth)
                         return 0;
                 solve_h48_appendsolution(arg);
                 return 1;
@@ -122,34 +114,28 @@ solve_h48_dfs(dfsarg_solveh48_t *arg)
         /* TODO: avoid copy, change arg and undo changes after recursion */
         nextarg = *arg;
         ret = 0;
-        nextarg.totmoves = arg->totmoves + 1;
-        if(arg->niss) {
-                nextarg.npremoves = arg->npremoves + 1;
+        uint32_t allowed;
+        if(arg->nissbranch & 0x01) {
+                allowed = allowednextmoveH48(arg->premoves, arg->npremoves, arg->nissbranch);
                 for (m = 0; m < 18; m++) {
-                        nextarg.premoves[arg->npremoves] = m;
-                if (!allowednextmove(nextarg.premoves, nextarg.npremoves)) {
-                        /* If a move is not allowed, neither are its 180
-                         * and 270 degree variations */
-                        m += 2;
-                        continue;
-                }
-                nextarg.cube = premove(arg->cube, m);
-                nextarg.inverse = move(arg->inverse, m);
-                ret += solve_h48_dfs(&nextarg);
+                        if(allowed & (1 << m)) {
+                                nextarg.npremoves = arg->npremoves + 1;
+                                nextarg.premoves[arg->npremoves] = m;
+                                nextarg.inverse = move(arg->inverse, m);
+                                nextarg.cube = premove(arg->cube, m);
+                                ret += solve_h48_dfs(&nextarg);
+                        }
                 }
         } else {
-                nextarg.nmoves = arg->nmoves + 1;
+                allowed = allowednextmoveH48(arg->moves, arg->nmoves, arg->nissbranch);
                 for (m = 0; m < 18; m++) {
-                        nextarg.moves[arg->nmoves] = m;
-                        if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
-                                /* If a move is not allowed, neither are its 180
-                                * and 270 degree variations */
-                                m += 2;
-                                continue;
+                        if (allowed & (1 << m)) {
+                                nextarg.nmoves = arg->nmoves + 1;
+                                nextarg.moves[arg->nmoves] = m;
+                                nextarg.cube = move(arg->cube, m);
+                                nextarg.inverse = premove(arg->inverse, m);
+                                ret += solve_h48_dfs(&nextarg);
                         }
-                        nextarg.cube = move(arg->cube, m);
-                        nextarg.inverse = premove(arg->inverse, m);
-                        ret += solve_h48_dfs(&nextarg);
                 }
         }
 
@@ -192,6 +178,7 @@ solve_h48(
                 LOG("Found %" PRId64 " solutions, searching at depth %"
                     PRId8 "\n", nsols, arg.depth);
                 arg.nmoves = 0;
+                arg.npremoves = 0;
                 solve_h48_dfs(&arg);
         }