aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--LICENSE4
-rw-r--r--Makefile6
-rw-r--r--shell.c2
-rw-r--r--src/arch/arch.h41
-rw-r--r--src/arch/avx2.h (renamed from src/cube_avx2.h)22
-rw-r--r--src/arch/common.h19
-rw-r--r--src/arch/neon.h (renamed from src/cube_neon.h)29
-rw-r--r--src/arch/portable.h (renamed from src/cube_portable.h)26
-rw-r--r--src/core/constant_cubes.h (renamed from src/constant_cubes.h)0
-rw-r--r--src/core/core.h13
-rw-r--r--src/core/cube.h (renamed from src/cube_generic.h)0
-rw-r--r--src/core/io_cube.h (renamed from src/io_cube.h)0
-rw-r--r--src/core/io_moves.h (renamed from src/io_move_trans.h)25
-rw-r--r--src/core/io_trans.h25
-rw-r--r--src/core/moves.h (renamed from src/moves.h)0
-rw-r--r--src/core/transform.h (renamed from src/cube_transform.h)0
-rw-r--r--src/core/transform_with_switch.h (renamed from src/cube_transform_with_switch.h)0
-rw-r--r--src/cube.c55
-rw-r--r--src/nissy.c (renamed from src/cube_public.h)12
-rw-r--r--src/nissy.h (renamed from src/cube.h)0
-rw-r--r--src/solvers/generic/generic.h (renamed from src/solve_generic.h)0
-rw-r--r--src/solvers/h48/coordinate.h68
-rw-r--r--src/solvers/h48/gendata.h (renamed from src/solve_h48.h)426
-rw-r--r--src/solvers/h48/h48.h4
-rw-r--r--src/solvers/h48/map.h104
-rw-r--r--src/solvers/h48/solve.h242
-rw-r--r--src/solvers/solvers.h2
-rw-r--r--src/utils/constants.h (renamed from src/constants.h)0
-rw-r--r--src/utils/dbg_log.h16
-rw-r--r--src/utils/math.h (renamed from src/utils.h)0
-rw-r--r--src/utils/utils.h3
-rw-r--r--test/test.h21
-rw-r--r--tools/001_gendata_h48/gendata_h48.c2
-rw-r--r--tools/002_stats_tables_h48/stats_tables_h48.c2
-rwxr-xr-xutils/genmovecode.sh2
-rwxr-xr-xutils/gentranscode.sh4
-rw-r--r--utils/h48_to_lst.c2
-rw-r--r--utils/invert.c2
38 files changed, 572 insertions, 607 deletions
diff --git a/LICENSE b/LICENSE
index 8af6571..7c787f3 100644
--- a/LICENSE
+++ b/LICENSE
@@ -2,7 +2,9 @@ The following license applies to every C source code and header file
2distributed with this LICENSE file. 2distributed with this LICENSE file.
3 3
4 h48 - a prototype for an optimal rubik's cube solver 4 h48 - a prototype for an optimal rubik's cube solver
5 Copyright (C) 2023 Sebastiano Tronto <sebastiano@tronto.net> 5 Copyright (C) 2023-2024
6 Sebastiano Tronto <sebastiano@tronto.net>
7 Enrico Tenuti <>
6 8
7 This program is free software: you can redistribute it and/or modify 9 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by 10 it under the terms of the GNU General Public License as published by
diff --git a/Makefile b/Makefile
index 5130940..0b7204e 100644
--- a/Makefile
+++ b/Makefile
@@ -3,13 +3,13 @@ include config.mk
3all: cube.o debugcube.o 3all: cube.o debugcube.o
4 4
5cube.s: clean 5cube.s: clean
6 ${CC} -D${CUBETYPE} ${CFLAGS} -c -S -o cube.s src/cube.c 6 ${CC} -D${CUBETYPE} ${CFLAGS} -c -S -o cube.s src/nissy.c
7 7
8cube.o: clean 8cube.o: clean
9 ${CC} -D${CUBETYPE} ${CFLAGS} -c -o cube.o src/cube.c 9 ${CC} -D${CUBETYPE} ${CFLAGS} -c -o cube.o src/nissy.c
10 10
11debugcube.o: clean 11debugcube.o: clean
12 ${CC} -D${CUBETYPE} ${DBGFLAGS} -c -o debugcube.o src/cube.c 12 ${CC} -D${CUBETYPE} ${DBGFLAGS} -c -o debugcube.o src/nissy.c
13 13
14clean: 14clean:
15 rm -rf *.o run 15 rm -rf *.o run
diff --git a/shell.c b/shell.c
index 9c5ac08..c1efcbd 100644
--- a/shell.c
+++ b/shell.c
@@ -7,7 +7,7 @@
7#include <string.h> 7#include <string.h>
8#include <time.h> 8#include <time.h>
9 9
10#include "src/cube.h" 10#include "src/nissy.h"
11 11
12#define PRINTCUBE_BUFFER_SIZE 1024 /* Should be enough */ 12#define PRINTCUBE_BUFFER_SIZE 1024 /* Should be enough */
13#define SOLUTIONS_BUFFER_SIZE 500000 /* Should be enough */ 13#define SOLUTIONS_BUFFER_SIZE 500000 /* Should be enough */
diff --git a/src/arch/arch.h b/src/arch/arch.h
new file mode 100644
index 0000000..d5e0218
--- /dev/null
+++ b/src/arch/arch.h
@@ -0,0 +1,41 @@
1#if defined(CUBE_AVX2)
2
3#include <immintrin.h>
4
5typedef __m256i cube_t;
6
7#if !defined(TEST_H)
8#include "common.h"
9#include "avx2.h"
10#endif
11
12#elif defined(CUBE_NEON)
13
14#include <stdlib.h>
15#include <arm_neon.h>
16
17typedef struct {
18 uint8x16_t corner;
19 uint8x16_t edge;
20} cube_t;
21
22#if !defined(TEST_H)
23#include "common.h"
24#include "neon.h"
25#endif
26
27#else
28
29#include <stdlib.h>
30
31typedef struct {
32 uint8_t corner[8];
33 uint8_t edge[12];
34} cube_t;
35
36#if !defined(TEST_H)
37#include "common.h"
38#include "portable.h"
39#endif
40
41#endif
diff --git a/src/cube_avx2.h b/src/arch/avx2.h
index b189023..59a0d6c 100644
--- a/src/cube_avx2.h
+++ b/src/arch/avx2.h
@@ -1,5 +1,3 @@
1typedef __m256i cube_t;
2
3#define _co2_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x6060606060606060)) 1#define _co2_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x6060606060606060))
4#define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x2020202020202020)) 2#define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x2020202020202020))
5#define _cp_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x0707070707070707)) 3#define _cp_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x0707070707070707))
@@ -18,26 +16,6 @@ typedef __m256i cube_t;
18#define solved static_cube( \ 16#define solved static_cube( \
19 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) 17 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
20 18
21_static void pieces(cube_t *, uint8_t [static 8], uint8_t [static 12]);
22_static_inline bool equal(cube_t, cube_t);
23_static_inline cube_t invertco(cube_t);
24_static_inline cube_t compose_epcpeo(cube_t, cube_t);
25_static_inline cube_t compose_edges(cube_t, cube_t);
26_static_inline cube_t compose_corners(cube_t, cube_t);
27_static_inline cube_t compose(cube_t, cube_t);
28_static_inline cube_t inverse(cube_t);
29
30_static_inline int64_t coord_co(cube_t);
31_static_inline int64_t coord_csep(cube_t);
32_static_inline int64_t coord_cocsep(cube_t);
33_static_inline int64_t coord_eo(cube_t);
34_static_inline int64_t coord_esep(cube_t);
35
36_static_inline void copy_corners(cube_t *, cube_t);
37_static_inline void copy_edges(cube_t *, cube_t);
38_static_inline void set_eo(cube_t *, int64_t);
39_static_inline cube_t invcoord_esep(int64_t);
40
41_static void 19_static void
42pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12]) 20pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12])
43{ 21{
diff --git a/src/arch/common.h b/src/arch/common.h
new file mode 100644
index 0000000..cd2d36e
--- /dev/null
+++ b/src/arch/common.h
@@ -0,0 +1,19 @@
1_static void pieces(cube_t *, uint8_t [static 8], uint8_t [static 12]);
2_static_inline bool equal(cube_t, cube_t);
3_static_inline cube_t invertco(cube_t);
4_static_inline cube_t compose_epcpeo(cube_t, cube_t);
5_static_inline cube_t compose_edges(cube_t, cube_t);
6_static_inline cube_t compose_corners(cube_t, cube_t);
7_static_inline cube_t compose(cube_t, cube_t);
8_static_inline cube_t inverse(cube_t);
9
10_static_inline int64_t coord_co(cube_t);
11_static_inline int64_t coord_csep(cube_t);
12_static_inline int64_t coord_cocsep(cube_t);
13_static_inline int64_t coord_eo(cube_t);
14_static_inline int64_t coord_esep(cube_t);
15
16_static_inline void copy_corners(cube_t *, cube_t);
17_static_inline void copy_edges(cube_t *, cube_t);
18_static_inline void set_eo(cube_t *, int64_t);
19_static_inline cube_t invcoord_esep(int64_t);
diff --git a/src/cube_neon.h b/src/arch/neon.h
index 23e5565..a75f86d 100644
--- a/src/cube_neon.h
+++ b/src/arch/neon.h
@@ -1,10 +1,3 @@
1// cube_t
2typedef struct
3{
4 uint8x16_t corner;
5 uint8x16_t edge;
6} cube_t;
7
8#define _co2_neon vdupq_n_u8(0x60) 1#define _co2_neon vdupq_n_u8(0x60)
9#define _cocw_neon vdupq_n_u8(0x20) 2#define _cocw_neon vdupq_n_u8(0x20)
10#define _cp_neon vdupq_n_u8(0x07) 3#define _cp_neon vdupq_n_u8(0x07)
@@ -30,28 +23,6 @@ typedef struct
30#define solved static_cube( \ 23#define solved static_cube( \
31 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) 24 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
32 25
33// Functions
34_static void pieces(cube_t *, uint8_t[static 8], uint8_t[static 12]);
35_static_inline bool equal(cube_t, cube_t);
36_static_inline cube_t invertco(cube_t);
37_static_inline cube_t compose_edges(cube_t, cube_t);
38_static_inline cube_t compose_corners(cube_t, cube_t);
39_static_inline uint8x16_t compose_edges_slim(uint8x16_t, uint8x16_t);
40_static_inline uint8x16_t compose_corners_slim(uint8x16_t, uint8x16_t);
41_static_inline cube_t compose(cube_t, cube_t);
42_static_inline cube_t inverse(cube_t);
43
44_static_inline int64_t coord_co(cube_t);
45_static_inline int64_t coord_csep(cube_t);
46_static_inline int64_t coord_cocsep(cube_t);
47_static_inline int64_t coord_eo(cube_t);
48_static_inline int64_t coord_esep(cube_t);
49
50_static_inline void copy_corners(cube_t *, cube_t);
51_static_inline void copy_edges(cube_t *, cube_t);
52_static_inline void set_eo(cube_t *, int64_t);
53_static_inline cube_t invcoord_esep(int64_t);
54
55_static void 26_static void
56pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12]) 27pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12])
57{ 28{
diff --git a/src/cube_portable.h b/src/arch/portable.h
index 77e803b..b8330af 100644
--- a/src/cube_portable.h
+++ b/src/arch/portable.h
@@ -1,8 +1,3 @@
1typedef struct {
2 uint8_t corner[8];
3 uint8_t edge[12];
4} cube_t;
5
6#define static_cube(c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl, \ 1#define static_cube(c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl, \
7 e_uf, e_ub, e_db, e_df, e_ur, e_ul, e_dl, e_dr, e_fr, e_fl, e_bl, e_br) \ 2 e_uf, e_ub, e_db, e_df, e_ur, e_ul, e_dl, e_dr, e_fr, e_fl, e_bl, e_br) \
8 ((cube_t) { \ 3 ((cube_t) { \
@@ -14,27 +9,6 @@ typedef struct {
14#define solved static_cube( \ 9#define solved static_cube( \
15 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) 10 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
16 11
17_static void pieces(cube_t *, uint8_t [static 8], uint8_t [static 12]);
18_static_inline bool equal(cube_t, cube_t);
19_static_inline cube_t invertco(cube_t);
20_static_inline void compose_edges_inplace(cube_t, cube_t, cube_t *);
21_static_inline void compose_corners_inplace(cube_t, cube_t, cube_t *);
22_static_inline cube_t compose_edges(cube_t, cube_t);
23_static_inline cube_t compose_corners(cube_t, cube_t);
24_static_inline cube_t compose(cube_t, cube_t);
25_static_inline cube_t inverse(cube_t);
26
27_static_inline int64_t coord_co(cube_t);
28_static_inline int64_t coord_csep(cube_t);
29_static_inline int64_t coord_cocsep(cube_t);
30_static_inline int64_t coord_eo(cube_t);
31_static_inline int64_t coord_esep(cube_t);
32
33_static_inline void copy_corners(cube_t *, cube_t);
34_static_inline void copy_edges(cube_t *, cube_t);
35_static_inline void set_eo(cube_t *, int64_t);
36_static_inline cube_t invcoord_esep(int64_t);
37
38_static void 12_static void
39pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12]) 13pieces(cube_t *cube, uint8_t c[static 8], uint8_t e[static 12])
40{ 14{
diff --git a/src/constant_cubes.h b/src/core/constant_cubes.h
index b7748d8..b7748d8 100644
--- a/src/constant_cubes.h
+++ b/src/core/constant_cubes.h
diff --git a/src/core/core.h b/src/core/core.h
new file mode 100644
index 0000000..6ffd76f
--- /dev/null
+++ b/src/core/core.h
@@ -0,0 +1,13 @@
1#include "constant_cubes.h"
2#include "io_moves.h"
3#include "io_trans.h"
4#include "cube.h"
5#include "io_cube.h"
6#include "moves.h"
7
8/* TODO: work in progress */
9#if 0
10#include "transform.h"
11#else
12#include "transform_with_switch.h"
13#endif
diff --git a/src/cube_generic.h b/src/core/cube.h
index fe36f90..fe36f90 100644
--- a/src/cube_generic.h
+++ b/src/core/cube.h
diff --git a/src/io_cube.h b/src/core/io_cube.h
index 956494d..956494d 100644
--- a/src/io_cube.h
+++ b/src/core/io_cube.h
diff --git a/src/io_move_trans.h b/src/core/io_moves.h
index cfeb93c..eb6290e 100644
--- a/src/io_move_trans.h
+++ b/src/core/io_moves.h
@@ -1,8 +1,6 @@
1_static uint8_t readmove(char); 1_static uint8_t readmove(char);
2_static uint8_t readmodifier(char); 2_static uint8_t readmodifier(char);
3_static uint8_t readtrans(const char *);
4_static int writemoves(uint8_t *, int, char *); 3_static int writemoves(uint8_t *, int, char *);
5_static void writetrans(uint8_t, char *);
6 4
7_static uint8_t 5_static uint8_t
8readmove(char c) 6readmove(char c)
@@ -40,19 +38,6 @@ readmodifier(char c)
40 } 38 }
41} 39}
42 40
43_static uint8_t
44readtrans(const char *buf)
45{
46 uint8_t t;
47
48 for (t = 0; t < 48; t++)
49 if (!strncmp(buf, transstr[t], 11))
50 return t;
51
52 LOG("readtrans error\n");
53 return _error;
54}
55
56_static int 41_static int
57writemoves(uint8_t *m, int n, char *buf) 42writemoves(uint8_t *m, int n, char *buf)
58{ 43{
@@ -75,13 +60,3 @@ writemoves(uint8_t *m, int n, char *buf)
75 60
76 return b - buf; 61 return b - buf;
77} 62}
78
79_static void
80writetrans(uint8_t t, char *buf)
81{
82 if (t >= 48)
83 memcpy(buf, "error trans", 11);
84 else
85 memcpy(buf, transstr[t], 11);
86 buf[11] = '\0';
87}
diff --git a/src/core/io_trans.h b/src/core/io_trans.h
new file mode 100644
index 0000000..7187b7a
--- /dev/null
+++ b/src/core/io_trans.h
@@ -0,0 +1,25 @@
1_static uint8_t readtrans(const char *);
2_static void writetrans(uint8_t, char *);
3
4_static uint8_t
5readtrans(const char *buf)
6{
7 uint8_t t;
8
9 for (t = 0; t < 48; t++)
10 if (!strncmp(buf, transstr[t], 11))
11 return t;
12
13 LOG("readtrans error\n");
14 return _error;
15}
16
17_static void
18writetrans(uint8_t t, char *buf)
19{
20 if (t >= 48)
21 memcpy(buf, "error trans", 11);
22 else
23 memcpy(buf, transstr[t], 11);
24 buf[11] = '\0';
25}
diff --git a/src/moves.h b/src/core/moves.h
index 7da6405..7da6405 100644
--- a/src/moves.h
+++ b/src/core/moves.h
diff --git a/src/cube_transform.h b/src/core/transform.h
index 358b051..358b051 100644
--- a/src/cube_transform.h
+++ b/src/core/transform.h
diff --git a/src/cube_transform_with_switch.h b/src/core/transform_with_switch.h
index d3a108c..d3a108c 100644
--- a/src/cube_transform_with_switch.h
+++ b/src/core/transform_with_switch.h
diff --git a/src/cube.c b/src/cube.c
deleted file mode 100644
index e8dedec..0000000
--- a/src/cube.c
+++ /dev/null
@@ -1,55 +0,0 @@
1#include <inttypes.h>
2#include <stdarg.h>
3#include <stdbool.h>
4#include <string.h>
5
6void (*nissy_log)(const char *, ...);
7
8#define LOG(...) if (nissy_log != NULL) nissy_log(__VA_ARGS__);
9
10#ifdef DEBUG
11#define _static
12#define _static_inline
13#define DBG_WARN(condition, ...) if (!(condition)) LOG(__VA_ARGS__);
14#define DBG_ASSERT(condition, retval, ...) \
15 if (!(condition)) { LOG(__VA_ARGS__); return retval; }
16#else
17#define _static static
18#define _static_inline static inline
19#define DBG_WARN(condition, ...)
20#define DBG_ASSERT(condition, retval, ...)
21#endif
22
23#include "constants.h"
24#include "utils.h"
25
26#if defined(CUBE_AVX2)
27#include <immintrin.h>
28#include "cube_avx2.h"
29#elif defined(CUBE_NEON)
30#include <stdlib.h>
31#include <arm_neon.h>
32#include "cube_neon.h"
33#else
34#include <stdlib.h> /* TODO: check if can be removed */
35#include "cube_portable.h"
36#endif
37
38#include "io_move_trans.h"
39#include "constant_cubes.h"
40#include "cube_generic.h"
41#include "io_cube.h"
42
43/* TODO: work in progress */
44#if 0
45#include "constant_cubes_transform.h"
46#include "cube_transform.h"
47#else
48#include "cube_transform_with_switch.h"
49#endif
50
51#include "moves.h"
52#include "solve_h48.h"
53#include "solve_generic.h"
54
55#include "cube_public.h"
diff --git a/src/cube_public.h b/src/nissy.c
index e080f40..9df775c 100644
--- a/src/cube_public.h
+++ b/src/nissy.c
@@ -1,4 +1,14 @@
1#include "cube.h" 1#include <inttypes.h>
2#include <stdarg.h>
3#include <stdbool.h>
4#include <string.h>
5
6#include "utils/utils.h"
7#include "arch/arch.h"
8#include "core/core.h"
9#include "solvers/solvers.h"
10
11#include "nissy.h"
2 12
3_static int64_t write_result(cube_t, char [static 22]); 13_static int64_t write_result(cube_t, char [static 22]);
4 14
diff --git a/src/cube.h b/src/nissy.h
index 346b99a..346b99a 100644
--- a/src/cube.h
+++ b/src/nissy.h
diff --git a/src/solve_generic.h b/src/solvers/generic/generic.h
index 41d995a..41d995a 100644
--- a/src/solve_generic.h
+++ b/src/solvers/generic/generic.h
diff --git a/src/solvers/h48/coordinate.h b/src/solvers/h48/coordinate.h
new file mode 100644
index 0000000..47b805d
--- /dev/null
+++ b/src/solvers/h48/coordinate.h
@@ -0,0 +1,68 @@
1#define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h))
2
3#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16))
4#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16))
5#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8))
6#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8))
7
8_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
9_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
10_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
11
12_static_inline int64_t
13coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
14{
15 int64_t cocsep, coclass;
16 uint32_t data;
17 uint8_t ttrep;
18
19 DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n");
20
21 cocsep = coord_cocsep(c);
22 data = cocsepdata[cocsep];
23 coclass = (int64_t)COCLASS(data);
24 ttrep = (int64_t)TTREP(data);
25
26 return coord_h48_edges(c, coclass, ttrep, h);
27}
28
29_static_inline int64_t
30coord_h48_edges(cube_t c, int64_t coclass, uint8_t ttrep, uint8_t h)
31{
32 cube_t d;
33 int64_t esep, eo, edges;
34
35 d = transform_edges(c, ttrep);
36 esep = coord_esep(d);
37 eo = coord_eo(d);
38 edges = (esep << 11) + eo;
39
40 return (coclass * H48_ESIZE(11) + edges) >> (11 - (int64_t)h);
41}
42
43/*
44This function does not necessarily return a cube whose coordinate is
45the given value, because it works up to symmetry. This means that the
46returned cube is a transformed cube of one that gives the correct value.
47*/
48_static_inline cube_t
49invcoord_h48(int64_t i, const cube_t *crep, uint8_t h)
50{
51 cube_t ret;
52 int64_t hh, coclass, ee, esep, eo;
53
54 DBG_ASSERT(h <= 11, zero,
55 "invcoord_h48: h must be between 0 and 11\n");
56
57 hh = (int64_t)h;
58 coclass = i / H48_ESIZE(h);
59 ee = i % H48_ESIZE(h);
60 esep = ee >> hh;
61 eo = (ee & ((1 << hh) - 1)) << (11 - hh);
62
63 ret = invcoord_esep(esep);
64 copy_corners(&ret, crep[coclass]);
65 set_eo(&ret, eo);
66
67 return ret;
68}
diff --git a/src/solve_h48.h b/src/solvers/h48/gendata.h
index 1701268..d6bf85b 100644
--- a/src/solve_h48.h
+++ b/src/solvers/h48/gendata.h
@@ -1,7 +1,3 @@
1#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF)
2#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF)
3#define MAP_KEYSHIFT UINT64_C(40)
4
5#define COCSEP_CLASSES ((size_t)3393) 1#define COCSEP_CLASSES ((size_t)3393)
6#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7) 2#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7)
7#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8) 3#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8)
@@ -11,24 +7,19 @@
11#define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h)) 7#define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h))
12#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k))) 8#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k)))
13 9
14#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16))
15#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16))
16#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8))
17#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8))
18#define CBOUND_MASK UINT32_C(0xFF)
19#define CBOUND(x) ((x) & CBOUND_MASK)
20#define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h))
21
22#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8)) 10#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8))
23#define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8))) 11#define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8)))
24#define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i)) 12#define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i))
25#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8)) 13#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8))
26#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8))) 14#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8)))
27 15
28#define MAX_SOLUTION_LENGTH 20 16#define CBOUND_MASK UINT32_C(0xFF)
17#define CBOUND(x) ((x) & CBOUND_MASK)
18
19#define MAXLEN 20
29 20
30/* 21/*
31TODO: This loop other similar h48 coordinates can be improved by only 22TODO: This loop over similar h48 coordinates can be improved by only
32transforming edges, but we need to compose transformations (i.e. conjugate 23transforming edges, but we need to compose transformations (i.e. conjugate
33_t by _ttrep). 24_t by _ttrep).
34*/ 25*/
@@ -47,18 +38,6 @@ _t by _ttrep).
47 } 38 }
48 39
49typedef struct { 40typedef struct {
50 uint64_t n;
51 uint64_t capacity;
52 uint64_t randomizer;
53 uint64_t *table;
54} h48map_t;
55
56typedef struct {
57 uint64_t key;
58 uint64_t val;
59} kvpair_t;
60
61typedef struct {
62 cube_t cube; 41 cube_t cube;
63 uint8_t depth; 42 uint8_t depth;
64 uint8_t maxdepth; 43 uint8_t maxdepth;
@@ -74,7 +53,7 @@ typedef struct {
74 cube_t cube; 53 cube_t cube;
75 int8_t nmoves; 54 int8_t nmoves;
76 int8_t depth; 55 int8_t depth;
77 uint8_t moves[MAX_SOLUTION_LENGTH]; 56 uint8_t moves[MAXLEN];
78 uint32_t *cocsepdata; 57 uint32_t *cocsepdata;
79 h48map_t *visited; 58 h48map_t *visited;
80} dfsarg_genh48set_t; 59} dfsarg_genh48set_t;
@@ -88,42 +67,6 @@ typedef struct {
88 cube_t *crep; 67 cube_t *crep;
89} bfsarg_esep_t; 68} bfsarg_esep_t;
90 69
91typedef struct {
92 cube_t cube;
93 cube_t inverse;
94 int8_t nmoves;
95 int8_t depth;
96 uint8_t moves[MAX_SOLUTION_LENGTH];
97 int64_t *nsols;
98 int64_t maxsolutions;
99 uint8_t h;
100 uint32_t *cocsepdata;
101 uint32_t *h48data;
102 char **nextsol;
103} dfsarg_solveh48_t;
104
105typedef struct {
106 cube_t cube;
107 int8_t nmoves;
108 int8_t depth;
109 uint8_t moves[MAX_SOLUTION_LENGTH];
110 uint32_t *cocsepdata;
111 uint32_t *h48data;
112 char *s;
113} dfsarg_solveh48stats_t;
114
115_static void h48map_create(h48map_t *, uint64_t, uint64_t);
116_static void h48map_clear(h48map_t *);
117_static void h48map_destroy(h48map_t *);
118_static uint64_t h48map_lookup(h48map_t *, uint64_t);
119_static void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
120_static uint64_t h48map_value(h48map_t *, uint64_t);
121_static kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
122
123_static_inline int64_t coord_h48(cube_t, const uint32_t *, uint8_t);
124_static_inline int64_t coord_h48_edges(cube_t, int64_t, uint8_t, uint8_t);
125_static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
126
127_static_inline bool get_visited(const uint8_t *, int64_t); 70_static_inline bool get_visited(const uint8_t *, int64_t);
128_static_inline void set_visited(uint8_t *, int64_t); 71_static_inline void set_visited(uint8_t *, int64_t);
129_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t); 72_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
@@ -138,155 +81,8 @@ _static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
138_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); 81_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
139_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); 82_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
140 83
141_static void solve_h48_appendsolution(dfsarg_solveh48_t *);
142_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); 84_static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
143_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *); 85_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
144_static_inline bool solve_h48_stop(dfsarg_solveh48_t *);
145_static int64_t solve_h48_dfs(dfsarg_solveh48_t *);
146_static int64_t solve_h48(
147 cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
148
149_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
150_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
151
152_static void
153h48map_create(h48map_t *map, uint64_t capacity, uint64_t randomizer)
154{
155 map->capacity = capacity;
156 map->randomizer = randomizer;
157
158 map->table = malloc(map->capacity * sizeof(int64_t));
159 h48map_clear(map);
160}
161
162_static void
163h48map_clear(h48map_t *map)
164{
165 memset(map->table, 0xFF, map->capacity * sizeof(uint64_t));
166 map->n = 0;
167}
168
169_static void
170h48map_destroy(h48map_t *map)
171{
172 free(map->table);
173}
174
175_static_inline uint64_t
176h48map_lookup(h48map_t *map, uint64_t x)
177{
178 uint64_t hash, i;
179
180 hash = ((x % map->capacity) * map->randomizer) % map->capacity;
181 for (i = hash;
182 map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
183 i = (i+1) % map->capacity
184 ) ;
185
186 return i;
187}
188
189_static_inline void
190h48map_insertmin(h48map_t *map, uint64_t key, uint64_t val)
191{
192 uint64_t i, oldval, min;
193
194 i = h48map_lookup(map, key);
195 oldval = map->table[i] >> MAP_KEYSHIFT;
196 min = _min(val, oldval);
197
198 map->n += map->table[i] == MAP_UNSET;
199 map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT);
200}
201
202_static_inline uint64_t
203h48map_value(h48map_t *map, uint64_t key)
204{
205 return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT;
206}
207
208_static kvpair_t
209h48map_nextkvpair(h48map_t *map, uint64_t *p)
210{
211 kvpair_t kv;
212 uint64_t pair;
213
214 kv.key = MAP_UNSET;
215 kv.val = MAP_UNSET;
216
217 DBG_ASSERT(*p < map->capacity, kv,
218 "Error looping over map: given index %" PRIu64 " is out of "
219 "range [0,%" PRIu64 "]", *p, map->capacity);
220
221 for ( ; *p < map->capacity; (*p)++) {
222 if (map->table[*p] != MAP_UNSET) {
223 pair = map->table[(*p)++];
224 kv.key = pair & MAP_KEYMASK;
225 kv.val = pair >> MAP_KEYSHIFT;
226 return kv;
227 }
228 }
229
230 return kv;
231}
232
233_static_inline int64_t
234coord_h48(cube_t c, const uint32_t *cocsepdata, uint8_t h)
235{
236 int64_t cocsep, coclass;
237 uint32_t data;
238 uint8_t ttrep;
239
240 DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n");
241
242 cocsep = coord_cocsep(c);
243 data = cocsepdata[cocsep];
244 coclass = (int64_t)COCLASS(data);
245 ttrep = (int64_t)TTREP(data);
246
247 return coord_h48_edges(c, coclass, ttrep, h);
248}
249
250_static_inline int64_t
251coord_h48_edges(cube_t c, int64_t coclass, uint8_t ttrep, uint8_t h)
252{
253 cube_t d;
254 int64_t esep, eo, edges;
255
256 d = transform_edges(c, ttrep);
257 esep = coord_esep(d);
258 eo = coord_eo(d);
259 edges = (esep << 11) + eo;
260
261 return (coclass * H48_ESIZE(11) + edges) >> (11 - (int64_t)h);
262}
263
264/*
265This function does not necessarily return a cube whose coordinate is
266the given value, because it works up to symmetry. This means that the
267returned cube is a transformed cube of one that gives the correct value.
268*/
269_static_inline cube_t
270invcoord_h48(int64_t i, const cube_t *crep, uint8_t h)
271{
272 cube_t ret;
273 int64_t hh, coclass, ee, esep, eo;
274
275 DBG_ASSERT(h <= 11, zero,
276 "invcoord_h48: h must be between 0 and 11\n");
277
278 hh = (int64_t)h;
279 coclass = i / H48_ESIZE(h);
280 ee = i % H48_ESIZE(h);
281 esep = ee >> hh;
282 eo = (ee & ((1 << hh) - 1)) << (11 - hh);
283
284 ret = invcoord_esep(esep);
285 copy_corners(&ret, crep[coclass]);
286 set_eo(&ret, eo);
287
288 return ret;
289}
290 86
291/* 87/*
292Each element of the cocsep table is a uint32_t used as follows: 88Each element of the cocsep table is a uint32_t used as follows:
@@ -608,19 +404,6 @@ set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
608 (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i)); 404 (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i));
609} 405}
610 406
611_static void
612solve_h48_appendsolution(dfsarg_solveh48_t *arg)
613{
614 int strl;
615
616 strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
617 LOG("Solution found: %s\n", *arg->nextsol);
618 *arg->nextsol += strl;
619 **arg->nextsol = '\n';
620 (*arg->nextsol)++;
621 (*arg->nsols)++;
622}
623
624_static_inline int8_t 407_static_inline int8_t
625get_h48_cdata(cube_t cube, uint32_t *cocsepdata, uint32_t *cdata) 408get_h48_cdata(cube_t cube, uint32_t *cocsepdata, uint32_t *cdata)
626{ 409{
@@ -640,200 +423,3 @@ get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data)
640 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); 423 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
641 return get_esep_pval(h48data, coord); 424 return get_esep_pval(h48data, coord);
642} 425}
643
644_static_inline bool
645solve_h48_stop(dfsarg_solveh48_t *arg)
646{
647 uint32_t data, data_inv;
648 int8_t bound;
649
650 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
651 if (bound + arg->nmoves > arg->depth)
652 return true;
653
654 bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
655 if (bound + arg->nmoves > arg->depth)
656 return true;
657
658/*
659 bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data);
660LOG("Using pval %" PRId8 "\n", bound);
661 if (bound + arg->nmoves > arg->depth)
662 return true;
663
664 bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data);
665 if (bound + arg->nmoves > arg->depth)
666 return true;
667*/
668
669 return false;
670}
671
672_static int64_t
673solve_h48_dfs(dfsarg_solveh48_t *arg)
674{
675 dfsarg_solveh48_t nextarg;
676 int64_t ret;
677 uint8_t m;
678
679 if (*arg->nsols == arg->maxsolutions)
680 return 0;
681
682 if (solve_h48_stop(arg))
683 return 0;
684
685 if (issolved(arg->cube)) {
686 if (arg->nmoves != arg->depth)
687 return 0;
688 solve_h48_appendsolution(arg);
689 return 1;
690 }
691
692 /* TODO: avoid copy, change arg and undo changes after recursion */
693 nextarg = *arg;
694 nextarg.nmoves = arg->nmoves + 1;
695 ret = 0;
696 for (m = 0; m < 18; m++) {
697 nextarg.moves[arg->nmoves] = m;
698 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
699 /* If a move is not allowed, neither are its 180
700 * and 270 degree variations */
701 m += 2;
702 continue;
703 }
704 nextarg.cube = move(arg->cube, m);
705 nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
706 ret += solve_h48_dfs(&nextarg);
707 }
708
709 return ret;
710}
711
712_static int64_t
713solve_h48(
714 cube_t cube,
715 int8_t minmoves,
716 int8_t maxmoves,
717 int8_t maxsolutions,
718 uint8_t h,
719 const void *data,
720 char *solutions
721)
722{
723 int64_t nsols;
724 dfsarg_solveh48_t arg;
725
726 arg = (dfsarg_solveh48_t) {
727 .cube = cube,
728 .inverse = inverse(cube),
729 .nsols = &nsols,
730 .maxsolutions = maxsolutions,
731 .h = h,
732 .cocsepdata = (uint32_t *)data,
733 .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4,
734 .nextsol = &solutions
735 };
736
737 nsols = 0;
738 for (arg.depth = minmoves;
739 arg.depth <= maxmoves && nsols < maxsolutions;
740 arg.depth++)
741 {
742 LOG("Found %" PRId64 " solutions, searching at depth %"
743 PRId8 "\n", nsols, arg.depth);
744 arg.nmoves = 0;
745 solve_h48_dfs(&arg);
746 }
747
748 return nsols;
749}
750
751/*
752The h48stats solver computes how many moves it takes to solve to
753each of the 12 h48 coordinates, one for each value of h from 0 to 11.
754The solutions array is filled with the length of the solutions. The
755solution array is therefore not a printable string.
756*/
757_static int64_t
758solve_h48stats_dfs(dfsarg_solveh48stats_t *arg)
759{
760 const int64_t limit = 11;
761
762 int8_t bound, u;
763 uint8_t m;
764 uint32_t d;
765 int64_t coord, h;
766 dfsarg_solveh48stats_t nextarg;
767
768 /* Check cocsep lower bound (corners only) */
769 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d);
770 if (bound + arg->nmoves > arg->depth)
771 return 0;
772
773 /* Check h48 lower bound for h=0 (esep, but no eo) */
774 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0);
775 bound = get_esep_pval(arg->h48data, coord);
776 if (bound + arg->nmoves > arg->depth)
777 return 0;
778
779 /* Update all other values, if solved */
780 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11);
781 for (h = 0; h <= limit; h++) {
782 u = coord >> (11-h) == 0 && arg->s[h] == 99;
783 arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h];
784 }
785
786 if (arg->s[limit] != 99)
787 return 0;
788
789 nextarg = *arg;
790 nextarg.nmoves = arg->nmoves + 1;
791 for (m = 0; m < 18; m++) {
792 nextarg.moves[arg->nmoves] = m;
793 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
794 /* If a move is not allowed, neither are its 180
795 * and 270 degree variations */
796 m += 2;
797 continue;
798 }
799 nextarg.cube = move(arg->cube, m);
800 solve_h48stats_dfs(&nextarg);
801 }
802
803 return 0;
804}
805
806_static int64_t
807solve_h48stats(
808 cube_t cube,
809 int8_t maxmoves,
810 const void *data,
811 char solutions[static 12]
812)
813{
814 int i;
815 size_t cocsepsize;
816 dfsarg_solveh48stats_t arg;
817
818 cocsepsize = gendata_cocsep(NULL, NULL, NULL);
819
820 arg = (dfsarg_solveh48stats_t) {
821 .cube = cube,
822 .cocsepdata = (uint32_t *)data,
823 .h48data = ((uint32_t *)data) + (cocsepsize/4),
824 .s = solutions
825 };
826
827 for (i = 0; i < 12; i++)
828 solutions[i] = (char)99;
829
830 for (arg.depth = 0;
831 arg.depth <= maxmoves && solutions[11] == 99;
832 arg.depth++)
833 {
834 arg.nmoves = 0;
835 solve_h48stats_dfs(&arg);
836 }
837
838 return 0;
839}
diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h
new file mode 100644
index 0000000..d33ad63
--- /dev/null
+++ b/src/solvers/h48/h48.h
@@ -0,0 +1,4 @@
1#include "coordinate.h"
2#include "map.h"
3#include "gendata.h"
4#include "solve.h"
diff --git a/src/solvers/h48/map.h b/src/solvers/h48/map.h
new file mode 100644
index 0000000..82e5a2c
--- /dev/null
+++ b/src/solvers/h48/map.h
@@ -0,0 +1,104 @@
1#define MAP_UNSET UINT64_C(0xFFFFFFFFFFFFFFFF)
2#define MAP_KEYMASK UINT64_C(0xFFFFFFFFFF)
3#define MAP_KEYSHIFT UINT64_C(40)
4
5typedef struct {
6 uint64_t n;
7 uint64_t capacity;
8 uint64_t randomizer;
9 uint64_t *table;
10} h48map_t;
11
12typedef struct {
13 uint64_t key;
14 uint64_t val;
15} kvpair_t;
16
17_static void h48map_create(h48map_t *, uint64_t, uint64_t);
18_static void h48map_clear(h48map_t *);
19_static void h48map_destroy(h48map_t *);
20_static uint64_t h48map_lookup(h48map_t *, uint64_t);
21_static void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
22_static uint64_t h48map_value(h48map_t *, uint64_t);
23_static kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
24
25_static void
26h48map_create(h48map_t *map, uint64_t capacity, uint64_t randomizer)
27{
28 map->capacity = capacity;
29 map->randomizer = randomizer;
30
31 map->table = malloc(map->capacity * sizeof(int64_t));
32 h48map_clear(map);
33}
34
35_static void
36h48map_clear(h48map_t *map)
37{
38 memset(map->table, 0xFF, map->capacity * sizeof(uint64_t));
39 map->n = 0;
40}
41
42_static void
43h48map_destroy(h48map_t *map)
44{
45 free(map->table);
46}
47
48_static_inline uint64_t
49h48map_lookup(h48map_t *map, uint64_t x)
50{
51 uint64_t hash, i;
52
53 hash = ((x % map->capacity) * map->randomizer) % map->capacity;
54 for (i = hash;
55 map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
56 i = (i+1) % map->capacity
57 ) ;
58
59 return i;
60}
61
62_static_inline void
63h48map_insertmin(h48map_t *map, uint64_t key, uint64_t val)
64{
65 uint64_t i, oldval, min;
66
67 i = h48map_lookup(map, key);
68 oldval = map->table[i] >> MAP_KEYSHIFT;
69 min = _min(val, oldval);
70
71 map->n += map->table[i] == MAP_UNSET;
72 map->table[i] = (key & MAP_KEYMASK) | (min << MAP_KEYSHIFT);
73}
74
75_static_inline uint64_t
76h48map_value(h48map_t *map, uint64_t key)
77{
78 return map->table[h48map_lookup(map, key)] >> MAP_KEYSHIFT;
79}
80
81_static kvpair_t
82h48map_nextkvpair(h48map_t *map, uint64_t *p)
83{
84 kvpair_t kv;
85 uint64_t pair;
86
87 kv.key = MAP_UNSET;
88 kv.val = MAP_UNSET;
89
90 DBG_ASSERT(*p < map->capacity, kv,
91 "Error looping over map: given index %" PRIu64 " is out of "
92 "range [0,%" PRIu64 "]", *p, map->capacity);
93
94 for ( ; *p < map->capacity; (*p)++) {
95 if (map->table[*p] != MAP_UNSET) {
96 pair = map->table[(*p)++];
97 kv.key = pair & MAP_KEYMASK;
98 kv.val = pair >> MAP_KEYSHIFT;
99 return kv;
100 }
101 }
102
103 return kv;
104}
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
new file mode 100644
index 0000000..8531a40
--- /dev/null
+++ b/src/solvers/h48/solve.h
@@ -0,0 +1,242 @@
1typedef struct {
2 cube_t cube;
3 cube_t inverse;
4 int8_t nmoves;
5 int8_t depth;
6 uint8_t moves[MAXLEN];
7 int64_t *nsols;
8 int64_t maxsolutions;
9 uint8_t h;
10 uint32_t *cocsepdata;
11 uint32_t *h48data;
12 char **nextsol;
13} dfsarg_solveh48_t;
14
15typedef struct {
16 cube_t cube;
17 int8_t nmoves;
18 int8_t depth;
19 uint8_t moves[MAXLEN];
20 uint32_t *cocsepdata;
21 uint32_t *h48data;
22 char *s;
23} dfsarg_solveh48stats_t;
24
25_static void solve_h48_appendsolution(dfsarg_solveh48_t *);
26_static_inline bool solve_h48_stop(dfsarg_solveh48_t *);
27_static int64_t solve_h48_dfs(dfsarg_solveh48_t *);
28_static int64_t solve_h48(
29 cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
30
31_static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
32_static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
33
34_static void
35solve_h48_appendsolution(dfsarg_solveh48_t *arg)
36{
37 int strl;
38
39 strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol);
40 LOG("Solution found: %s\n", *arg->nextsol);
41 *arg->nextsol += strl;
42 **arg->nextsol = '\n';
43 (*arg->nextsol)++;
44 (*arg->nsols)++;
45}
46
47_static_inline bool
48solve_h48_stop(dfsarg_solveh48_t *arg)
49{
50 uint32_t data, data_inv;
51 int8_t bound;
52
53 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &data);
54 if (bound + arg->nmoves > arg->depth)
55 return true;
56
57 bound = get_h48_cdata(arg->inverse, arg->cocsepdata, &data_inv);
58 if (bound + arg->nmoves > arg->depth)
59 return true;
60
61/*
62 bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data);
63LOG("Using pval %" PRId8 "\n", bound);
64 if (bound + arg->nmoves > arg->depth)
65 return true;
66
67 bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data);
68 if (bound + arg->nmoves > arg->depth)
69 return true;
70*/
71
72 return false;
73}
74
75_static int64_t
76solve_h48_dfs(dfsarg_solveh48_t *arg)
77{
78 dfsarg_solveh48_t nextarg;
79 int64_t ret;
80 uint8_t m;
81
82 if (*arg->nsols == arg->maxsolutions)
83 return 0;
84
85 if (solve_h48_stop(arg))
86 return 0;
87
88 if (issolved(arg->cube)) {
89 if (arg->nmoves != arg->depth)
90 return 0;
91 solve_h48_appendsolution(arg);
92 return 1;
93 }
94
95 /* TODO: avoid copy, change arg and undo changes after recursion */
96 nextarg = *arg;
97 nextarg.nmoves = arg->nmoves + 1;
98 ret = 0;
99 for (m = 0; m < 18; m++) {
100 nextarg.moves[arg->nmoves] = m;
101 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
102 /* If a move is not allowed, neither are its 180
103 * and 270 degree variations */
104 m += 2;
105 continue;
106 }
107 nextarg.cube = move(arg->cube, m);
108 nextarg.inverse = inverse(nextarg.cube); /* TODO: use premove */
109 ret += solve_h48_dfs(&nextarg);
110 }
111
112 return ret;
113}
114
115_static int64_t
116solve_h48(
117 cube_t cube,
118 int8_t minmoves,
119 int8_t maxmoves,
120 int8_t maxsolutions,
121 uint8_t h,
122 const void *data,
123 char *solutions
124)
125{
126 int64_t nsols;
127 dfsarg_solveh48_t arg;
128
129 arg = (dfsarg_solveh48_t) {
130 .cube = cube,
131 .inverse = inverse(cube),
132 .nsols = &nsols,
133 .maxsolutions = maxsolutions,
134 .h = h,
135 .cocsepdata = (uint32_t *)data,
136 .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4,
137 .nextsol = &solutions
138 };
139
140 nsols = 0;
141 for (arg.depth = minmoves;
142 arg.depth <= maxmoves && nsols < maxsolutions;
143 arg.depth++)
144 {
145 LOG("Found %" PRId64 " solutions, searching at depth %"
146 PRId8 "\n", nsols, arg.depth);
147 arg.nmoves = 0;
148 solve_h48_dfs(&arg);
149 }
150
151 return nsols;
152}
153
154/*
155The h48stats solver computes how many moves it takes to solve to
156each of the 12 h48 coordinates, one for each value of h from 0 to 11.
157The solutions array is filled with the length of the solutions. The
158solution array is therefore not a printable string.
159*/
160_static int64_t
161solve_h48stats_dfs(dfsarg_solveh48stats_t *arg)
162{
163 const int64_t limit = 11;
164
165 int8_t bound, u;
166 uint8_t m;
167 uint32_t d;
168 int64_t coord, h;
169 dfsarg_solveh48stats_t nextarg;
170
171 /* Check cocsep lower bound (corners only) */
172 bound = get_h48_cdata(arg->cube, arg->cocsepdata, &d);
173 if (bound + arg->nmoves > arg->depth)
174 return 0;
175
176 /* Check h48 lower bound for h=0 (esep, but no eo) */
177 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0);
178 bound = get_esep_pval(arg->h48data, coord);
179 if (bound + arg->nmoves > arg->depth)
180 return 0;
181
182 /* Update all other values, if solved */
183 coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 11);
184 for (h = 0; h <= limit; h++) {
185 u = coord >> (11-h) == 0 && arg->s[h] == 99;
186 arg->s[h] = u * arg->nmoves + (1-u) * arg->s[h];
187 }
188
189 if (arg->s[limit] != 99)
190 return 0;
191
192 nextarg = *arg;
193 nextarg.nmoves = arg->nmoves + 1;
194 for (m = 0; m < 18; m++) {
195 nextarg.moves[arg->nmoves] = m;
196 if (!allowednextmove(nextarg.moves, nextarg.nmoves)) {
197 /* If a move is not allowed, neither are its 180
198 * and 270 degree variations */
199 m += 2;
200 continue;
201 }
202 nextarg.cube = move(arg->cube, m);
203 solve_h48stats_dfs(&nextarg);
204 }
205
206 return 0;
207}
208
209_static int64_t
210solve_h48stats(
211 cube_t cube,
212 int8_t maxmoves,
213 const void *data,
214 char solutions[static 12]
215)
216{
217 int i;
218 size_t cocsepsize;
219 dfsarg_solveh48stats_t arg;
220
221 cocsepsize = gendata_cocsep(NULL, NULL, NULL);
222
223 arg = (dfsarg_solveh48stats_t) {
224 .cube = cube,
225 .cocsepdata = (uint32_t *)data,
226 .h48data = ((uint32_t *)data) + (cocsepsize/4),
227 .s = solutions
228 };
229
230 for (i = 0; i < 12; i++)
231 solutions[i] = (char)99;
232
233 for (arg.depth = 0;
234 arg.depth <= maxmoves && solutions[11] == 99;
235 arg.depth++)
236 {
237 arg.nmoves = 0;
238 solve_h48stats_dfs(&arg);
239 }
240
241 return 0;
242}
diff --git a/src/solvers/solvers.h b/src/solvers/solvers.h
new file mode 100644
index 0000000..66c9b27
--- /dev/null
+++ b/src/solvers/solvers.h
@@ -0,0 +1,2 @@
1#include "generic/generic.h"
2#include "h48/h48.h"
diff --git a/src/constants.h b/src/utils/constants.h
index 52e2810..52e2810 100644
--- a/src/constants.h
+++ b/src/utils/constants.h
diff --git a/src/utils/dbg_log.h b/src/utils/dbg_log.h
new file mode 100644
index 0000000..427eceb
--- /dev/null
+++ b/src/utils/dbg_log.h
@@ -0,0 +1,16 @@
1void (*nissy_log)(const char *, ...);
2
3#define LOG(...) if (nissy_log != NULL) nissy_log(__VA_ARGS__);
4
5#ifdef DEBUG
6#define _static
7#define _static_inline
8#define DBG_WARN(condition, ...) if (!(condition)) LOG(__VA_ARGS__);
9#define DBG_ASSERT(condition, retval, ...) \
10 if (!(condition)) { LOG(__VA_ARGS__); return retval; }
11#else
12#define _static static
13#define _static_inline static inline
14#define DBG_WARN(condition, ...)
15#define DBG_ASSERT(condition, retval, ...)
16#endif
diff --git a/src/utils.h b/src/utils/math.h
index 87402e6..87402e6 100644
--- a/src/utils.h
+++ b/src/utils/math.h
diff --git a/src/utils/utils.h b/src/utils/utils.h
new file mode 100644
index 0000000..ce4355e
--- /dev/null
+++ b/src/utils/utils.h
@@ -0,0 +1,3 @@
1#include "dbg_log.h"
2#include "constants.h"
3#include "math.h"
diff --git a/test/test.h b/test/test.h
index 1f4b2c3..d7658cb 100644
--- a/test/test.h
+++ b/test/test.h
@@ -1,3 +1,5 @@
1#define TEST_H
2
1#include <inttypes.h> 3#include <inttypes.h>
2#include <stdarg.h> 4#include <stdarg.h>
3#include <stdbool.h> 5#include <stdbool.h>
@@ -5,24 +7,9 @@
5#include <stdlib.h> 7#include <stdlib.h>
6#include <string.h> 8#include <string.h>
7 9
8#define STRLENMAX 10000 10#include "../src/arch/arch.h"
9 11
10#if defined(CUBE_AVX2) 12#define STRLENMAX 10000
11#include <immintrin.h>
12typedef __m256i cube_t;
13#elif defined(CUBE_NEON)
14#include <stdlib.h>
15#include <arm_neon.h>
16typedef struct {
17 uint8x16_t corner;
18 uint8x16_t edge;
19} cube_t;
20#else
21typedef struct {
22 uint8_t corner[8];
23 uint8_t edge[12];
24} cube_t;
25#endif
26 13
27/* Basic functions used in most tests */ 14/* Basic functions used in most tests */
28cube_t solvedcube(void); 15cube_t solvedcube(void);
diff --git a/tools/001_gendata_h48/gendata_h48.c b/tools/001_gendata_h48/gendata_h48.c
index 0456616..da0b4ad 100644
--- a/tools/001_gendata_h48/gendata_h48.c
+++ b/tools/001_gendata_h48/gendata_h48.c
@@ -1,5 +1,5 @@
1#include "../timerun.h" 1#include "../timerun.h"
2#include "../../src/cube.h" 2#include "../../src/nissy.h"
3 3
4#define MAXDEPTH 20 4#define MAXDEPTH 20
5#define HVALUE 0 5#define HVALUE 0
diff --git a/tools/002_stats_tables_h48/stats_tables_h48.c b/tools/002_stats_tables_h48/stats_tables_h48.c
index 7df396a..2e48497 100644
--- a/tools/002_stats_tables_h48/stats_tables_h48.c
+++ b/tools/002_stats_tables_h48/stats_tables_h48.c
@@ -1,7 +1,7 @@
1#include <pthread.h> 1#include <pthread.h>
2#include <time.h> 2#include <time.h>
3#include "../timerun.h" 3#include "../timerun.h"
4#include "../../src/cube.h" 4#include "../../src/nissy.h"
5 5
6#define MAXMOVES 20 6#define MAXMOVES 20
7#define NTHREADS 32 7#define NTHREADS 32
diff --git a/utils/genmovecode.sh b/utils/genmovecode.sh
index daf268e..ddde0f7 100755
--- a/utils/genmovecode.sh
+++ b/utils/genmovecode.sh
@@ -1,6 +1,6 @@
1#!/bin/sh 1#!/bin/sh
2 2
3cc -DDEBUG h48_to_lst.c ../src/cube.c -o h48_to_lst 3cc -DDEBUG h48_to_lst.c ../src/nissy.c -o h48_to_lst
4 4
5gen() { 5gen() {
6 for f in cubes/move_??_*.txt; do 6 for f in cubes/move_??_*.txt; do
diff --git a/utils/gentranscode.sh b/utils/gentranscode.sh
index 9f9ec4d..e3e199e 100755
--- a/utils/gentranscode.sh
+++ b/utils/gentranscode.sh
@@ -1,7 +1,7 @@
1#!/bin/sh 1#!/bin/sh
2 2
3cc -DDEBUG h48_to_lst.c ../src/cube.c -o h48_to_lst 3cc -DDEBUG h48_to_lst.c ../src/nissy.c -o h48_to_lst
4cc -DDEBUG invert.c ../src/cube.c -o invert 4cc -DDEBUG invert.c ../src/nissy.c -o invert
5 5
6lineavx() { printf '#define _trans_cube_%s ' "$1"; } 6lineavx() { printf '#define _trans_cube_%s ' "$1"; }
7linesrc() { printf '_static cube_fast_t _trans_cube_%s = ' "$1"; } 7linesrc() { printf '_static cube_fast_t _trans_cube_%s = ' "$1"; }
diff --git a/utils/h48_to_lst.c b/utils/h48_to_lst.c
index 977c95d..03265b7 100644
--- a/utils/h48_to_lst.c
+++ b/utils/h48_to_lst.c
@@ -2,7 +2,7 @@
2#include <inttypes.h> 2#include <inttypes.h>
3#include <stdbool.h> 3#include <stdbool.h>
4 4
5#include "../src/cube.h" 5#include "../src/nissy.h"
6 6
7#define STRLENMAX 1000 7#define STRLENMAX 1000
8 8
diff --git a/utils/invert.c b/utils/invert.c
index 9121a47..41580c0 100644
--- a/utils/invert.c
+++ b/utils/invert.c
@@ -2,7 +2,7 @@
2#include <inttypes.h> 2#include <inttypes.h>
3#include <stdbool.h> 3#include <stdbool.h>
4 4
5#include "../src/cube.h" 5#include "../src/nissy.h"
6 6
7#define STRLENMAX 1000 7#define STRLENMAX 1000
8 8

Generated with cgit - Back to sebastiano.tronto.net