(almost) added getcube

7 files changed, 205 insertions, 32 deletions

diff --git a/src/constants.h b/src/constants.h
index c8909d7..52e2810 100644
--- a/src/constants.h
+++ b/src/constants.h
@@ -2,10 +2,14 @@
 #define _bit_u32(i) (UINT32_C(1) << (uint32_t)(i))
 #define _bit_u64(i) (UINT64_C(1) << (uint64_t)(i))
 
+#define _max_factorial INT64_C(12)
+
 #define _2p11  INT64_C(2048)
 #define _2p12  INT64_C(4096)
 #define _3p7   INT64_C(2187)
 #define _3p8   INT64_C(6561)
+#define _12f   INT64_C(479001600)
+#define _8f    INT64_C(40320)
 #define _12c4  INT64_C(495)
 #define _8c4   INT64_C(70)
 
diff --git a/src/cube.c b/src/cube.c
index 54876a7..1f8711c 100644
--- a/src/cube.c
+++ b/src/cube.c
@@ -21,6 +21,7 @@ void (*nissy_log)(const char *, ...);
 #endif
 
 #include "constants.h"
+#include "utils.h"
 
 #if defined(CUBE_AVX2)
 #include <immintrin.h>
diff --git a/src/cube.h b/src/cube.h
index d3d096a..28737c4 100644
--- a/src/cube.h
+++ b/src/cube.h
@@ -41,8 +41,11 @@ int64_t nissy_convert(
         char *result
 );
 
-int64_t nissy_gencube(
-        uint8_t id[16],
+int64_t nissy_getcube(
+        int64_t ep,
+        int64_t eo,
+        int64_t cp,
+        int64_t co,
         const char *options,
         char result[static 22]
 );
diff --git a/src/cube_generic.h b/src/cube_generic.h
index 7095c3a..c40844d 100644
--- a/src/cube_generic.h
+++ b/src/cube_generic.h
@@ -1,6 +1,7 @@
 #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);
@@ -9,14 +10,24 @@ _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 int permsign(uint8_t *, int);
 _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);
 
 _static cube_t
+cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
+{
+        return static_cube(
+            c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7],
+            e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7],
+            e[8], e[9], e[10], e[11]);
+}
+
+_static cube_t
 solvedcube(void)
 {
         return solved;
@@ -171,6 +182,39 @@ frommoves(const char *buf)
         return applymoves(solved, buf);
 }
 
+_static void
+getcube_fix(int64_t *ep, int64_t *eo, int64_t *cp, int64_t *co)
+{
+        uint8_t e[12], c[8], aux;
+
+        *ep %= _12f;
+        *eo %= _2p11;
+        *cp %= _8f;
+        *cp %= _3p7;
+
+        indextoperm(*ep, 12, e);
+        indextoperm(*cp, 8, c);
+        if (permsign(e, 12) != permsign(c, 8)) {
+                aux = c[0];
+                c[0] = c[1];
+                c[1] = aux;
+                *cp = permtoindex(c, 8);
+        }
+}
+
+_static cube_t
+getcube(int64_t ep, int64_t eo, int64_t cp, int64_t co)
+{
+        uint8_t e[12], c[8];
+
+        indextoperm(ep, 12, e);
+        indextoperm(cp, 8, c);
+
+        /* TODO: orientation */
+
+        return cubefromarray(c, e);
+}
+
 _static cube_t
 applytrans(cube_t cube, const char *buf)
 {
@@ -184,19 +228,6 @@ applytrans(cube_t cube, const char *buf)
         return transform(cube, t);
 }
 
-_static int
-permsign(uint8_t *a, int n)
-{
-        int i, j;
-        uint8_t ret = 0;
-
-        for (i = 0; i < n; i++)
-                for (j = i+1; j < n; j++)
-                        ret += a[i] > a[j] ? 1 : 0;
-
-        return ret % 2;
-}
-
 _static cube_t
 move(cube_t c, uint8_t m)
 {
diff --git a/src/cube_public.h b/src/cube_public.h
index fe003c9..b537019 100644
--- a/src/cube_public.h
+++ b/src/cube_public.h
@@ -2,6 +2,16 @@
 
 _static int64_t write_result(cube_t, char [static 22]);
 
+/* TODO: add option to get DR, maybe C-only, E-only, eo... */
+#define GETCUBE_OPTIONS(S, F) { .option = S, .fix = F }
+struct {
+        char *option;
+        void (*fix)(int64_t *, int64_t *, int64_t *, int64_t *);
+} getcube_options[] = {
+        GETCUBE_OPTIONS("fix", getcube_fix),
+        GETCUBE_OPTIONS(NULL, NULL)
+};
+
 _static int64_t
 write_result(cube_t cube, char result[static 22])
 {
@@ -105,15 +115,25 @@ nissy_convert(
 }
 
 int64_t
-nissy_gencube(
-        uint8_t id[16],
+nissy_getcube(
+        int64_t ep,
+        int64_t eo,
+        int64_t cp,
+        int64_t co,
         const char *options,
         char result[static 22]
 )
 {
-        /* TODO: compute cube from id % (number of positions) */
-        /* options can be used for generating e.g. DR-state cube */
-        return -1;
+        int i;
+        cube_t c;
+
+        for (i = 0; getcube_options[i].option != NULL; i++)
+                if (!strcmp(options, getcube_options[i].option))
+                        getcube_options[i].fix(&ep, &eo, &cp, &co);
+
+        c = getcube(ep, eo, cp, co);
+
+        return write_result(c, result);
 }
 
 int64_t
diff --git a/src/io_cube.h b/src/io_cube.h
index 95c1882..956494d 100644
--- a/src/io_cube.h
+++ b/src/io_cube.h
@@ -1,5 +1,3 @@
-_static cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]);
-
 _static uint8_t readco(const char *);
 _static uint8_t readcp(const char *);
 _static uint8_t readeo(const char *);
@@ -31,15 +29,6 @@ _static struct {
         { .name = "NONE", .read = NULL, .write = NULL },
 };
 
-_static_inline cube_t
-cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
-{
-        return static_cube(
-            c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7],
-            e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7],
-            e[8], e[9], e[10], e[11]);
-}
-
 cube_t
 readcube(const char *format, const char *buf)
 {
diff --git a/src/utils.h b/src/utils.h
new file mode 100644
index 0000000..0c0b4d1
--- /dev/null
+++ b/src/utils.h
@@ -0,0 +1,125 @@
+_static int64_t factorial(int64_t);
+_static bool isperm(uint8_t *, int64_t);
+_static int64_t permtoindex(uint8_t *, int64_t);
+_static void indextoperm(int64_t, int64_t, uint8_t *);
+_static int permsign(uint8_t *, int64_t);
+
+_static int64_t
+factorial(int64_t n)
+{
+        int64_t i, ret;
+
+        if (n > _max_factorial) {
+                LOG("Error: won't compute factorial for n=%" PRId64 " because"
+                    " it is larger than %" PRId64 "\n", n, _max_factorial);
+                return -1;
+        }
+
+        if (n < 0)
+                return 0;
+
+        for (i = 1, ret = 1; i <= n; i++)
+                ret *= i;
+
+        return ret;
+}
+
+_static bool
+isperm(uint8_t *a, int64_t n)
+{
+        int64_t i;
+        bool aux[_max_factorial+1];
+
+        if (n > _max_factorial) {
+                LOG("Error: won't compute 'isperm()' for n=%" PRId64 " because"
+                    " it is larger than %" PRId64 "\n", n, _max_factorial);
+                return false;
+        }
+
+        memset(aux, false, n);
+        
+        for (i = 0; i < n; i++) {
+                if (a[i] < 0 || a[i] >= n)
+                        return false;
+                else
+                        aux[a[i]] = true;
+        }
+
+        for (i = 0; i < n; i++)
+                if (!aux[i])
+                        return false;
+
+        return true;
+}
+
+_static int64_t
+permtoindex(uint8_t *a, int64_t n)
+{
+        int64_t i, j, c, ret;
+
+        if (n > _max_factorial) {
+                LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
+                    " because it is larger than %" PRId64 "\n",
+                    n, _max_factorial);
+                return -1;
+        }
+
+        if (!isperm(a, n))
+                return -1;
+
+        for (i = 0, ret = 0; i < n; i++) {
+                for (j = i+1, c = 0; j < n; j++)
+                        c += (a[i] > a[j]) ? 1 : 0;
+                ret += factorial(n-i-1) * c;
+        }
+
+        return ret;
+}
+
+_static void
+indextoperm(int64_t p, int64_t n, uint8_t *r)
+{
+        int64_t i, j, c;
+        uint8_t a[_max_factorial+1];
+
+        if (n > _max_factorial) {
+                LOG("Error: won't compute 'permtoindex()' for n=%" PRId64
+                    " because it is larger than %" PRId64 "\n",
+                    n, _max_factorial);
+                goto indextoperm_error;
+        }
+
+        memset(a, 0, n);
+
+        if (p < 0 || p >= factorial(n))
+                goto indextoperm_error;
+
+        for (i = 0; i < n; i++) {
+                for (j = 0, c = 0; c <= p / factorial(n-i-1); j++)
+                        c += a[j] ? 0 : 1;
+                r[i] = j-1;
+                a[j-1] = 1;
+                p %= factorial(n-i-1);
+        }
+
+        if (!isperm(r, n))
+                goto indextoperm_error;
+
+        return;
+
+indextoperm_error:
+        memset(r, _error, n);
+}
+
+_static int
+permsign(uint8_t *a, int64_t n)
+{
+        int i, j;
+        uint8_t ret;
+
+        for (i = 0, ret = 0; i < n; i++)
+                for (j = i+1; j < n; j++)
+                        ret += a[i] > a[j] ? 1 : 0;
+
+        return ret % 2;
+}