From 518d98ad5f9eec0cf4124375bdbb84d1296b3f3f Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Thu, 4 Jul 2024 17:09:55 +0200 Subject: (almost) added getcube --- src/constants.h | 4 ++ src/cube.c | 1 + src/cube.h | 7 ++- src/cube_generic.h | 59 +++++++++++++++++++------ src/cube_public.h | 30 ++++++++++--- src/io_cube.h | 11 ----- src/utils.h | 125 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 205 insertions(+), 32 deletions(-) create mode 100644 src/utils.h (limited to 'src') 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 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,13 +10,23 @@ _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) { @@ -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; +} -- cgit v1.3