aboutsummaryrefslogtreecommitdiff
path: root/old
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-06-13 22:28:49 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2024-06-13 22:28:49 +0200
commitc04a283a7ab97903683f5f7268068aef69f5bddf (patch)
tree9809c4a71c2ad1a5123371c32c34f03b1b703ecf /old
parent7812684339d03f6993882358b0045c1bc2d5032c (diff)
downloadnissy-core-c04a283a7ab97903683f5f7268068aef69f5bddf.tar.gz
nissy-core-c04a283a7ab97903683f5f7268068aef69f5bddf.zip
Added benchmark; removed old folder
Diffstat (limited to 'old')
-rw-r--r--old/benchmark/bench.c83
-rwxr-xr-xold/benchmark/bench.sh21
-rw-r--r--old/benchmark/cube-bench.c147
-rw-r--r--old/cube_h_with_format_documentation147
-rw-r--r--old/manualsimd/cube.c888
-rw-r--r--old/manualsimd/cube.h27
6 files changed, 0 insertions, 1313 deletions
diff --git a/old/benchmark/bench.c b/old/benchmark/bench.c
deleted file mode 100644
index 2c3358f..0000000
--- a/old/benchmark/bench.c
+++ /dev/null
@@ -1,83 +0,0 @@
1#include <stdbool.h>
2#include <stdint.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <time.h>
6
7#include "../cube.h"
8
9#define MOVES 100000000
10#define TRANS 100000000
11#define COMPOSE 100000000
12#define INVERSE 100000000
13
14double
15bench(cube_t (*run)(int64_t), int64_t n, char *name)
16{
17 char str[1000];
18 cube_t cube;
19 struct timespec start, end;
20 double tdiff, tdsec, tdnano;
21
22 printf("\n");
23 fflush(stdout);
24
25 if (run == NULL) {
26 printf("> %s: nothing to run!\n", name);
27 fflush(stdout);
28 return -1.0;
29 }
30
31 printf("> %s: running benchmark...\n", name);
32 fflush(stdout);
33 clock_gettime(CLOCK_MONOTONIC, &start);
34
35 cube = run(n);
36 writecube("H48", cube, str);
37 str[3] = 0;
38 printf("> %s: resulting cube, first piece: %s\n", name, str);
39 fflush(stdout);
40
41 clock_gettime(CLOCK_MONOTONIC, &end);
42 tdsec = end.tv_sec - start.tv_sec;
43 tdnano = end.tv_nsec - start.tv_nsec;
44 tdiff = tdsec + 1e-9 * tdnano;
45 printf("> %s: %.4fs\n", name, tdiff);
46 fflush(stdout);
47
48 return tdiff;
49}
50
51int main() {
52 double tmoves, ttrans, tcompose, tinverse;
53
54 printf(
55 "Benchmarks settings:\n"
56 "MOVES:\t%d\nTRANS:\t%d\nCOMPOSE:\t%d\nINVERSE:\t%d\n",
57 MOVES, TRANS, COMPOSE, INVERSE
58 );
59 fflush(stdout);
60
61 srand(time(NULL));
62
63 tmoves = bench(run_moves, MOVES, "moves");
64 ttrans = bench(run_trans, TRANS, "trans");
65 tcompose = bench(run_compose, COMPOSE, "compose");
66 tinverse = bench(run_inverse, INVERSE, "inverse");
67
68 printf(
69 "\nBenchmark summary:\n"
70 "moves: %d moves in %.4fs (%.4f MTPS)\n"
71 "trans: %d transformations in %.4fs (%.4f MTPS)\n"
72 "compose: %d compositions in %.4fs (%.4f MCPS)\n"
73 "inverse: %d inverses in %.4fs (%.4f MIPS)\n"
74 "Total time: %.4f\n",
75 MOVES, tmoves, MOVES / (1e6 * tmoves),
76 TRANS, ttrans, TRANS / (1e6 * ttrans),
77 COMPOSE, tcompose, COMPOSE / (1e6 * tcompose),
78 INVERSE, tinverse, INVERSE / (1e6 * tinverse),
79 tmoves + ttrans + tcompose + tinverse
80 );
81
82 return 0;
83}
diff --git a/old/benchmark/bench.sh b/old/benchmark/bench.sh
deleted file mode 100755
index cc31c1e..0000000
--- a/old/benchmark/bench.sh
+++ /dev/null
@@ -1,21 +0,0 @@
1#!/bin/sh
2
3CC="cc -std=c99 -O3 -D$CUBETYPE"
4if [ "$CUBETYPE" = "CUBE_AVX2" ]; then
5 CC="$CC -mavx2"
6fi
7
8BENCHBIN="benchmark/run"
9BENCHDIR="benchmark/results"
10CUBEOBJ="cube.o"
11
12$CC -D_POSIX_C_SOURCE=199309L -o $BENCHBIN benchmark/bench.c $CUBEOBJ || exit 1
13
14d="$(date +'%Y-%m-%d-%H-%M-%S')"
15mkdir -p "$BENCHDIR"
16$BENCHBIN | tee "$BENCHDIR/results-$d.txt" "$BENCHDIR/results.txt"
17
18echo ""
19echo "Results saved to $BENCHDIR/results.txt"
20
21rm -rf $BENCHBIN $CUBEOBJ
diff --git a/old/benchmark/cube-bench.c b/old/benchmark/cube-bench.c
deleted file mode 100644
index 26d12a4..0000000
--- a/old/benchmark/cube-bench.c
+++ /dev/null
@@ -1,147 +0,0 @@
1/******************************************************************************
2Section: benchmarks
3
4Here you can find some simple functions that can be used to benchmark the
5rest of the code.
6******************************************************************************/
7
8#define RANDOMCUBES 157
9
10static void
11setup_randomcubes(cube_fast_t *cubes)
12{
13 int i;
14
15 for (i = 0; i < RANDOMCUBES; i++)
16 cubes[i] = run_moves(i*4);
17}
18
19cube_t
20run_moves(int64_t n)
21{
22 cube_fast_t fast;
23 int64_t m, i;
24
25 fast = solvedcube();
26 m = n / 18;
27
28 for (i = 0; i < m; i++) {
29 fast = _move_U(fast);
30 fast = _move_U2(fast);
31 fast = _move_U3(fast);
32 fast = _move_D(fast);
33 fast = _move_D2(fast);
34 fast = _move_D3(fast);
35 fast = _move_R(fast);
36 fast = _move_R2(fast);
37 fast = _move_R3(fast);
38 fast = _move_L(fast);
39 fast = _move_L2(fast);
40 fast = _move_L3(fast);
41 fast = _move_F(fast);
42 fast = _move_F2(fast);
43 fast = _move_F3(fast);
44 fast = _move_B(fast);
45 fast = _move_B2(fast);
46 fast = _move_B3(fast);
47 }
48
49 for (i = m * 18; i < n; i++)
50 fast = _move_F(fast);
51
52 return fast;
53}
54
55cube_t
56run_trans(int64_t n)
57{
58 cube_fast_t fast;
59 int64_t m, i;
60
61 fast = run_moves(33);
62 m = n / 18;
63
64 for (i = 0; i < m; i++) {
65 fast = _trans_UFr(fast);
66 fast = _trans_ULr(fast);
67 fast = _trans_UBr(fast);
68 fast = _trans_URr(fast);
69 fast = _trans_DFr(fast);
70 fast = _trans_DLr(fast);
71 fast = _trans_DBr(fast);
72 fast = _trans_DRr(fast);
73 fast = _trans_RUr(fast);
74 fast = _trans_RFr(fast);
75 fast = _trans_RDr(fast);
76 fast = _trans_RBr(fast);
77 fast = _trans_LUr(fast);
78 fast = _trans_LFr(fast);
79 fast = _trans_LDr(fast);
80 fast = _trans_LBr(fast);
81 fast = _trans_FUr(fast);
82 fast = _trans_FRr(fast);
83 fast = _trans_FDr(fast);
84 fast = _trans_FLr(fast);
85 fast = _trans_BUr(fast);
86 fast = _trans_BRr(fast);
87 fast = _trans_BDr(fast);
88 fast = _trans_BLr(fast);
89 fast = _trans_UFm(fast);
90 fast = _trans_ULm(fast);
91 fast = _trans_UBm(fast);
92 fast = _trans_URm(fast);
93 fast = _trans_DFm(fast);
94 fast = _trans_DLm(fast);
95 fast = _trans_DBm(fast);
96 fast = _trans_DRm(fast);
97 fast = _trans_RUm(fast);
98 fast = _trans_RFm(fast);
99 fast = _trans_RDm(fast);
100 fast = _trans_RBm(fast);
101 fast = _trans_LUm(fast);
102 fast = _trans_LFm(fast);
103 fast = _trans_LDm(fast);
104 fast = _trans_LBm(fast);
105 fast = _trans_FUm(fast);
106 fast = _trans_FRm(fast);
107 fast = _trans_FDm(fast);
108 fast = _trans_FLm(fast);
109 fast = _trans_BUm(fast);
110 fast = _trans_BRm(fast);
111 fast = _trans_BDm(fast);
112 fast = _trans_BLm(fast);
113 }
114
115 for (i = m * 18; i < n; i++)
116 fast = _trans_FRm(fast);
117
118 return fast;
119}
120
121cube_t
122run_compose(int64_t n)
123{
124 cube_fast_t fast, cubes[RANDOMCUBES];
125 int64_t i;
126
127 setup_randomcubes(cubes);
128
129 for (i = 0; i < n; i++)
130 fast = compose_fast(fast, cubes[i % RANDOMCUBES]);
131
132 return fast;
133}
134
135cube_t
136run_inverse(int64_t n)
137{
138 cube_fast_t fast, cubes[RANDOMCUBES];
139 int64_t i;
140
141 setup_randomcubes(cubes);
142
143 for (i = 0; i < n; i++)
144 fast = inverse_fast(cubes[i % RANDOMCUBES]);
145
146 return fast;
147}
diff --git a/old/cube_h_with_format_documentation b/old/cube_h_with_format_documentation
deleted file mode 100644
index 3cbc3b5..0000000
--- a/old/cube_h_with_format_documentation
+++ /dev/null
@@ -1,147 +0,0 @@
1/******************************************************************************
2Cube type definition
3
4Each piece is represented by an (unsigned) 8-bit integer. The 4
5least-significant bits determine which piece it is, the other 4 determine
6the orientation.
7
8Edges are numbered as follows (see also cube.c):
9UF=0 UB=1 DB=2 DF=3 UR=4 UL=5 DL=6 DR=7 FR=8 FL=9 BL=10 BR=11
10
11Corners are numbered as follows:
12UFR=0 UBL=1 DFL=2 DBR=3 UFL=4 UBR=5 DFR=6 DBL=7
13
14The orientation of the edges is with respect to F/B, the orientation of
15corners is with respect to U/D.
16
17The permutation of the center pieces is not stored. This means that the
18cube is assumed to be in a fixed orientation.
19
20TODO: define EO and CO better, explain how to use them
21TODO: encode centers?
22
23The exact cube type structure depends on your system's configuration. If
24you operate on the cube only via the functions provided below, you don't
25need to worry about this.
26******************************************************************************/
27
28/* Apply the second cube on the first as a move sequence */
29cube_t compose(cube_t, cube_t);
30
31/* Invert the cube */
32cube_t inverse(cube_t);
33
34/* Check if a cube represent a valid state (possibly unsolvable) */
35
36/* TODO comment on these and the format for moves and trans */
37/* For trans, only one trans is supported */
38cube_t applymoves(cube_t, const char *);
39cube_t applytrans(cube_t, const char *);
40
41/******************************************************************************
42Read / write utilities
43
44Reading and writing is not done directly via stdin / stdout, but via an
45array of char (called buf in the prototypes below).
46
47Multiple representations of the cube as text are supported:
48
49- H48: a human-readable format.
50 Each edge is represented by two letters denoting the sides it
51 belongs to and one number denoting its orientation (0 oriented, 1
52 mis-oriented). Similarly, each corner is represented by three letters and
53 a number (0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
54
55 The solved cube looks like this:
56
57 UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0
58 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
59
60 The cube after the moves R'U'F looks like this:
61
62 FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0
63 UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
64
65 Whitespace (including newlines) between pieces is ignored when reading the
66 cube. A single whitespace character is added between pieces when writing.
67
68- SRC: format used to generate code for internal use.
69 If OUT is the output in SRC format, one can use `cube_t cube = OUT` to
70 declare a new cube object.
71
72- LST: a format for internal use and generating code.
73 The cube is printed as a comma-separated list of 20 integers, as they appear
74 in cube_t. Corners come first, followed by edge (unlike H48).
75******************************************************************************/
76
77cube_t readcube(const char *format, const char *buf);
78void writecube(const char *format, cube_t cube, char *buf);
79
80/******************************************************************************
81Solvers
82
83The solutions are returned as a newline-separated list of characters. Moves
84are separated by single spaces.
85
86Unless specified otherwise, all the solutions are not trivially simplifiable.
87This means that sequences like U U2 or R L R will not appear in any solution.
88Moreover, two consecutive parallel moves are always going to be sorted in
89increasing order. For example, L R2 may never appear in a solution, but R2 L
90could.
91******************************************************************************/
92
93int64_t solve(
94 /* The cube to solve. Must be solvable. */
95 cube_t cube,
96
97 /* Supported solvers:
98 * "optimal" - currently the same as "simple"
99 * "simple" - a simple, slow solver without tables
100 */
101 const char *solver,
102
103 /* Some solvers accept extra options,like "!filter". */
104 const char *options,
105
106 /* Can be "normal", "inverse", "mixed" or "linear". */
107 const char *nisstype,
108
109 /* The minimum number of moves. Must be >= 0. */
110 int8_t minmoves,
111
112 /* The maximum number of moves. If negative, the maximum length
113 * is unlimited.
114 */
115 int8_t maxmoves,
116
117 /* The maximum number of solutions. */
118 int64_t maxsols,
119
120 /* All solutions at most "optimal" moves from the shortest solution
121 * (respecting minmoves) are found. If negative, it is ignored.
122 */
123 int8_t optimal,
124
125 /* Some solvers require extra data to function properly (for example,
126 * pruning tables). This data can be generated with gendata().
127 */
128 const void *data,
129
130 /* The solutions (return parameter) */
131 char *solutions
132);
133
134/* Solving n cubes optimally, one solutions per cube. Options are similar
135 * to solve().
136 */
137void multisolve(
138 int n,
139 cube_t *cube,
140 const char *solver,
141 const void *data,
142 char *sols
143);
144
145/* Returns the number of bytes written to data, -1 in case of error.
146 * TODO: write down how much memory every solver requires. */
147int64_t gendata(const char *solver, const char *options, void *data);
diff --git a/old/manualsimd/cube.c b/old/manualsimd/cube.c
deleted file mode 100644
index 4372b5e..0000000
--- a/old/manualsimd/cube.c
+++ /dev/null
@@ -1,888 +0,0 @@
1/*
2# Cube representation, moves, transformations and (tentatively) indexing
3
4## Textual description
5
6The functions readcube() and writecube() use the following format.
7Each edge is represented by two letters denoting the sides it belongs to
8and one number denoting its orientation (0 oriented, 1 mis-oriented).
9Similarly, each corner is represented by three letters and a number
10(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
11Edge orientation is relative to the F / B axis, corner orientation is
12relative to the U / D axis.
13
14The correct order of the pieces is the same as that defined in the
15section "Internal cube representation", except that pieces are read
16left-to-right. Pieces are divided by slices, so the ordering is not the
17most intuitive, but it is more convenient for the internal representation.
18
19Whitespaces between pieces are ignored when reading the cube, and a
20single whitespace character is added between pieces when writing.
21
22For example, the solved cube looks like this:
23
24UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 \ (no newline)
25UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
26
27The cube after the moves R'U'F looks like this:
28
29FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 \ (no newline)
30UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
31
32More formats might be supported in the future.
33
34## Internal cube representation
35
36The cube_t data structure implemented in this file is designed to
37efficiently perform common operations on a 3x3x3 Rubik's cube when
38solving it with an iterative-deepening DFS search. It is not the most
39general, complete, easy to read or compact one. Since the cube can
40be trivially reoriented before the search, we only encode permutations
41of the cube that keep the center pieces in a fixed position (that is,
42we do not encode the position of the centers).
43
44The cube state is encoded in two 64-bit integers, one for edges and one
45for centers. We explain how edges are encoded first, and the highlight
46the few differences with corners afterwards.
47
48For encoding edges, only the 60 least-significant bits are used. Each
49edge described by 5 bits. The position of a 5-bit block in the 64-bit
50integer determine the position of the edge piece in the cube, according
51to the following table (least-significant bits on the right):
52
5355-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
54 BR BL FL FR DR DL UL UR DF DB UB UF
55ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
56
57For each edge, the 4 least-significant bits ('ssee' in the table)
58determine the piece. The two bits marked with 'ss' determine the internal
59slice the piece belongs to, i.e. they are either '00' for M, '01' for
60S or '10' for E. The other two bits (marked with 'ee') determine the
61actual edge piece among the 4 in the same slice, and they are assigned
62somewhat arbitarily. Using this representation and the ordering defined
63in the table above, the edges are correctly permuted when these 4 bits
64for each represent the numbers 0 to 11 in the correct order.
65
66The last bit determines the orientation. The orientation of an edge
67depends on its position, and it is defined being 0 if the edge can be
68moved to its place in the solved orientation by permutations in the
69subgroup <U, D, R, L, F2, B2>.
70
71Corners are encoded in the 48 least-significant bits, and are described
72by 6 bits each, their position being defined by the following table:
73
74 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
75 DBL DFL UBR UFL DBR DFL UBL UFR
76oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
77
78The bit marked with an 'x' describes the axis the corner belongs to.
79The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
80four corners form the axis marked with 1. Then two bits are needed to
81identify the corner among the four of the same axis. The last three bits
82determine the orientation, where one corner is defined to be oriented
83(marked with '000') if its top or bottom sticker faces the top or bottom
84side. A corner a clockwise turn away from being oriented, thus requiring
85a counter-clockwise turn to be oriented correctly, is marked with '001',
86and a corner a counter-clockwise turn away is marked with '010'. The most
87significant bit is not used to determine the corner orientation, but it
88must always be set to '0' to simplify the moving operations (see below).
89
90## Basic moves
91
92The 18 basic moves of the cube could be performed by applying a suitable
93general permutation (see below), but they have instead been manually
94implemented with a few simple operations each, to improve performance.
95
96For each move we first permute the pieces. This amounts to shifting
97around 4 blocks of bits for edges and 4 for corners. Since in some cases
98adjacent pieces on the cube are also adjacent in the bit representation we
99use, we can save some operations by shifting multiple blocks together.
100
101There are some moves that change the orientation of the pieces. Namely,
102the moves F, F', B and B' change the orientation of the edges and those
103moves as well as R, R', L and L' change the orientation of the corners.
104Edge orientation is easy to address: we simply xor the edge representation
105by a bit mask with zeroes everywhere except for the 4 edges that need
106to be flipped (i.e. the ones on the twisted face).
107
108Corner orientation is harder to reproduce efficiently working only with
109bitwise operations, as it involves performing operations modulo 3.
110However, with the help of the extra bit we reserved, we are able to
111do this using only two additions and 3 bitwise operations, without
112any multiplication, division or modulo operation. The trick is
113to use the following formula to sum two numbers x, y in {0,1,2}:
114
115 ((x+y) + (x+y+1)/4) % 4
116
117The thrid bit is needed because x+y and x+y+1 can exceed 3. We can
118apply this operation to multiple pairs of bits representing ternary
119digits at once using binary operations. See the function coapply()
120below for the details.
121
122## Inverting the cube
123
124TODO
125
126## Transformations (conjugations by full-cube rotations)
127
128TODO
129
130## Indexing (tentative)
131
132TODO - subgroup description etc
133
134*/
135
136#include <stdbool.h>
137#include <stdint.h>
138#include <string.h>
139
140#ifdef DEBUG
141#include <stdio.h>
142#endif
143
144#include "cube.h"
145
146#define _error 0xFFFFFFFF
147
148#define _eoblock 0x10ULL /* 10000 */
149#define _epblock 0x0FULL /* 01111 */
150#define _eblock 0x1FULL /* 11111 */
151#define _eblock2 0x3FFULL /* 1111111111 */
152
153#define _coblock 0x18ULL /* 011000 */
154#define _cpblock 0x07ULL /* 000111 */
155#define _cblock 0x3FULL /* 111111 */
156#define _cblock2 0xFFFULL /* 111111111111 */
157
158#define _eomask 0x842108421084210ULL /* 10000 repeated 12 times */
159#define _comask 0x618618618618ULL /* 011000 repeated 8 times */
160#define _coonemask 0x208208208208ULL /* 001000 repeated 8 times */
161#define _coextramask 0x820820820820ULL /* 100000 repeated 8 times */
162
163#define _emask_u (_eblock2 | _eblock2 << 20ULL)
164#define _emask_d (_eblock2 << 10ULL | _eblock2 << 30ULL)
165#define _emask_r (_eblock << 20ULL | _eblock2 << 35ULL | _eblock << 55ULL)
166#define _emask_l (_eblock2 << 45ULL | _eblock2 << 25ULL)
167#define _emask_f (_eblock | _eblock << 15ULL | _eblock2 << 40ULL)
168#define _emask_b (_eblock2 << 5ULL | _eblock2 << 50ULL)
169
170#define _cmask_u (_cblock2 | _cblock2 << 24ULL)
171#define _cmask_d (_cblock2 << 12ULL | _cblock2 << 36ULL)
172#define _cmask_r (_cblock | _cblock << 18ULL | _cblock2 << 30ULL)
173#define _cmask_l (_cblock2 << 6ULL | _cblock << 24ULL | _cblock << 42ULL)
174#define _cmask_f (_cblock | _cblock << 12ULL | _cblock << 24ULL | _cblock << 36ULL)
175#define _cmask_b (_cblock << 6ULL | _cblock << 18ULL | _cblock << 30ULL | _cblock << 42ULL)
176
177#define _eomask_f (1ULL << 4ULL | 1ULL << 19ULL | 1ULL << 44ULL | 1ULL << 49ULL)
178#define _eomask_b (1ULL << 9ULL | 1ULL << 14ULL | 1ULL << 54ULL | 1ULL << 59ULL)
179
180#define _comask_r (2ULL << 3ULL | 1ULL << 33ULL | 2ULL << 21ULL | 1ULL << 39ULL)
181#define _comask_l (1ULL << 27ULL | 2ULL << 9ULL | 2ULL << 15ULL | 1ULL << 45ULL)
182#define _comask_f (1ULL << 3ULL | 1ULL << 15ULL | 2ULL << 27ULL | 2ULL << 39ULL)
183#define _comask_b (1ULL << 9ULL | 1ULL << 21ULL | 2ULL << 33ULL | 2ULL << 45ULL)
184
185static inline uint64_t coapply(uint64_t, uint64_t);
186static uint64_t permsign(uint64_t *, int);
187static uint64_t readep(char *);
188static uint64_t readeo(char *);
189static uint64_t readcp(char *);
190static uint64_t readco(char *);
191static uint64_t readmove(char);
192static uint64_t readmodifier(char);
193
194static char *edgestr[] = {
195 "UF", "UB", "DB", "DF",
196 "UR", "UL", "DL", "DR",
197 "FR", "FL", "BL", "BR"
198};
199static char *cornerstr[] = {
200 "UFR", "UBL", "DFL", "DBR",
201 "UFL", "UBR", "DFR", "DBL"
202};
203static char *cornerstralt[] = {
204 "URF", "ULB", "DLF", "DRB",
205 "ULF", "URB", "DRF", "DLB"
206};
207static char *movestr[] = {
208 [U] = "U", [U2] = "U2", [U3] = "U'",
209 [D] = "D", [D2] = "D2", [D3] = "D'",
210 [R] = "R", [R2] = "R2", [R3] = "R'",
211 [L] = "L", [L2] = "L2", [L3] = "L'",
212 [F] = "F", [F2] = "F2", [F3] = "F'",
213 [B] = "B", [B2] = "B2", [B3] = "B'",
214};
215
216cube_t solvedcube = { .e = 0x5A928398A418820ULL, .c = 0x1C61440C2040ULL };
217cube_t errorcube = { .e = _error, .c = _error };
218
219
220static uint64_t
221permsign(uint64_t *a, int n)
222{
223 int i, j;
224 uint64_t ret;
225
226 ret = 0;
227
228 for (i = 0; i < n; i++)
229 for (j = i+1; j < n; j++)
230 ret += a[i] > a[j] ? 1 : 0;
231
232 return ret % 2;
233}
234
235bool
236isconsistent(cube_t cube)
237{
238 uint64_t x, p[12], sum, co;
239 bool found[12];
240 int i;
241
242 sum = 0;
243
244 /* Check for EP consistency */
245 for (i = 0; i < 12; i++)
246 found[i] = false;
247 for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
248 p[i] = x & _epblock;
249 if (p[i] >= 12)
250 goto inconsistent_ep;
251 found[p[i]] = true;
252 }
253 for (i = 0; i < 12; i++)
254 if (!found[i])
255 goto inconsistent_ep;
256 sum = permsign(p, 12);
257
258 /* Check for CP consistency */
259 for (i = 0; i < 8; i++)
260 found[i] = false;
261 for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
262 p[i] = x & _cpblock;
263 if (p[i] >= 8)
264 goto inconsistent_cp;
265 found[p[i]] = true;
266 }
267 for (i = 0; i < 8; i++)
268 if (!found[i])
269 goto inconsistent_cp;
270 sum += permsign(p, 8);
271
272 /* Check permutation parity */
273 if (sum % 2 != 0)
274 goto inconsistent_parity;
275
276 /* Check for EO parity */
277 for (i = 0, sum = 0, x = cube.e; i < 12; i++, x >>= 5ULL)
278 sum += (x & _eoblock) >> 4ULL;
279 if (sum % 2 != 0)
280 goto inconsistent_eo;
281
282 /* Check for CO parity */
283 for (i = 0, sum = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
284 co = (x & _coblock) >> 3ULL;
285 if (co > 2)
286 goto inconsistent_co3;
287 sum += co;
288 }
289 if (sum % 3 != 0)
290 goto inconsistent_co;
291
292 /* Check that CO extra bit is zero */
293 if (cube.c & _coextramask)
294 goto inconsistent_coextra;
295
296 return true;
297
298inconsistent_ep:
299#ifdef DEBUG
300 fprintf(stderr, "Inconsistent EP\n");
301#endif
302 goto inconsistent_return;
303inconsistent_cp:
304#ifdef DEBUG
305 fprintf(stderr, "Inconsistent CP\n");
306#endif
307 goto inconsistent_return;
308inconsistent_parity:
309#ifdef DEBUG
310 fprintf(stderr, "Inconsistent parity\n");
311#endif
312 goto inconsistent_return;
313inconsistent_eo:
314#ifdef DEBUG
315 fprintf(stderr, "Inconsistent EO\n");
316#endif
317 goto inconsistent_return;
318inconsistent_co3:
319#ifdef DEBUG
320 fprintf(stderr, "Inconsistent CO=3\n");
321#endif
322 goto inconsistent_return;
323inconsistent_co:
324#ifdef DEBUG
325 fprintf(stderr, "Inconsistent CO\n");
326#endif
327 goto inconsistent_return;
328inconsistent_coextra:
329#ifdef DEBUG
330 fprintf(stderr, "Inconsistent extra bit for CO\n");
331#endif
332 goto inconsistent_return;
333inconsistent_return:
334 return false;
335}
336
337bool
338issolved(cube_t cube)
339{
340 return cube.c == solvedcube.c && cube.e == solvedcube.e;
341}
342
343
344static uint64_t
345readep(char *str)
346{
347 uint64_t e;
348
349 for (e = 0; e < 12; e++)
350 if (!strncmp(str, edgestr[e], 2))
351 return e;
352
353#ifdef DEBUG
354 fprintf(stderr, "Error reading EP\n");
355#endif
356 return _error;
357}
358
359static uint64_t
360readeo(char *str)
361{
362 if (*str == '0')
363 return 0ULL;
364 if (*str == '1')
365 return 1ULL;
366
367#ifdef DEBUG
368 fprintf(stderr, "Error reading EO\n");
369#endif
370 return _error;
371}
372
373static uint64_t
374readcp(char *str)
375{
376 uint64_t c;
377
378 for (c = 0; c < 8; c++)
379 if (!strncmp(str, cornerstr[c], 3) ||
380 !strncmp(str, cornerstralt[c], 3))
381 return c;
382
383#ifdef DEBUG
384 fprintf(stderr, "Error reading CP\n");
385#endif
386 return _error;
387}
388
389static uint64_t
390readco(char *str)
391{
392 if (*str == '0')
393 return 0ULL;
394 if (*str == '1')
395 return 1ULL;
396 if (*str == '2')
397 return 2ULL;
398
399#ifdef DEBUG
400 fprintf(stderr, "Error reading CO\n");
401#endif
402 return _error;
403}
404
405cube_t
406readcube(char *buf)
407{
408 int i;
409 uint64_t piece, orient;
410 cube_t ret = {0};
411 char *b = buf;
412
413 for (i = 0; i < 12; i++) {
414 while (*b == ' ' || *b == '\t' || *b == '\n')
415 b++;
416 if ((piece = readep(b)) == _error)
417 goto readcube_error;
418 b += 2;
419 if ((orient = readeo(b)) == _error)
420 goto readcube_error;
421 b++;
422 ret.e |= (piece << (i * 5ULL)) | (orient << (i * 5ULL + 4ULL));
423 }
424 for (i = 0; i < 8; i++) {
425 while (*b == ' ' || *b == '\t' || *b == '\n')
426 b++;
427 if ((piece = readcp(b)) == _error)
428 goto readcube_error;
429 b += 3;
430 if ((orient = readco(b)) == _error)
431 goto readcube_error;
432 b++;
433 ret.c |= (piece << (i * 6ULL)) | (orient << (i * 6ULL + 3ULL));
434 }
435
436 return ret;
437
438readcube_error:
439#ifdef DEBUG
440 fprintf(stderr, "readcube error\n");
441#endif
442 return errorcube;
443}
444
445void
446writecube(cube_t cube, char *buf)
447{
448 char *errormsg;
449 uint64_t piece, orien, x;
450 size_t len;
451 int i;
452
453 if (!isconsistent(cube)) {
454 errormsg = "ERROR: cannot write inconsistent cube";
455 goto writecube_error;
456 }
457
458 for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
459 piece = x & _epblock;
460 orien = (x & _eoblock) >> 4ULL;
461 buf[4*i ] = edgestr[piece][0];
462 buf[4*i + 1] = edgestr[piece][1];
463 buf[4*i + 2] = orien + '0';
464 buf[4*i + 3] = ' ';
465 }
466 for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
467 piece = x & _cpblock;
468 orien = (x & _coblock) >> 3ULL;
469 buf[48 + 5*i ] = cornerstr[piece][0];
470 buf[48 + 5*i + 1] = cornerstr[piece][1];
471 buf[48 + 5*i + 2] = cornerstr[piece][2];
472 buf[48 + 5*i + 3] = orien + '0';
473 buf[48 + 5*i + 4] = ' ';
474 }
475
476 buf[48+39] = '\0';
477
478 return;
479
480writecube_error:
481#ifdef DEBUG
482 fprintf(stderr, "writecube error, see stdout for details\n");
483#endif
484 len = strlen(errormsg);
485 memcpy(buf, errormsg, len);
486 buf[len] = '\n';
487 buf[len+1] = '\0';
488}
489
490
491static uint64_t
492readmove(char c)
493{
494 switch (c) {
495 case 'U':
496 return U;
497 case 'D':
498 return D;
499 case 'R':
500 return R;
501 case 'L':
502 return L;
503 case 'F':
504 return F;
505 case 'B':
506 return B;
507 default:
508 return _error;
509 }
510}
511
512static uint64_t
513readmodifier(char c)
514{
515 switch (c) {
516 case '1': /* Fallthrough */
517 case '2': /* Fallthrough */
518 case '3':
519 return c - '0' - 1;
520 case '\'':
521 return 2;
522 default:
523 return 0;
524 }
525}
526
527int
528readmoves(char *buf, move_t *m)
529{
530 int n;
531 uint64_t r;
532 char *b;
533
534 for (b = buf, n = 0; *b != '\0'; b++) {
535 while (*b == ' ' || *b == '\t' || *b == '\n')
536 b++;
537 if (*b == '\0')
538 return n;
539 if ((r = readmove(*b)) == _error)
540 goto readmoves_error;
541 m[n] = (move_t)r;
542 if ((r = readmodifier(*(b+1))) != 0) {
543 b++;
544 m[n] += r;
545 }
546 n++;
547 }
548
549 return n;
550
551readmoves_error:
552#ifdef DEBUG
553 fprintf(stderr, "readmoves error\n");
554#endif
555 return -1;
556}
557
558void
559writemoves(move_t *m, int n, char *buf)
560{
561 int i;
562 size_t len;
563 char *b, *s;
564
565 for (i = 0, b = buf; i < n; i++, b++) {
566 s = movestr[m[i]];
567 len = strlen(s);
568 memcpy(b, s, len);
569 b += len;
570 *b = ' ';
571 }
572 *b = '\0';
573}
574
575
576static inline uint64_t
577coapply(uint64_t c, uint64_t m)
578{
579 uint64_t z, b;
580
581 z = c + m;
582 b = ((z + _coonemask) & _coextramask) >> 2ULL;
583
584 return (z + b) & ~_coextramask;
585}
586
587cube_t
588move(cube_t c, move_t m)
589{
590 cube_t ret = {0};
591
592#ifdef DEBUG
593 if (!isconsistent(c)) {
594 fprintf(stderr, "move error, inconsistent cube\n");
595 goto move_error;
596 }
597#endif
598
599 switch (m) {
600 case U:
601 ret.e = c.e & ~_emask_u;
602 ret.e |=
603 (c.e & _eblock) << 25ULL |
604 (c.e & _eblock << 5ULL) << 15ULL |
605 (c.e & _eblock2 << 20ULL) >> 20ULL;
606
607 ret.c = c.c & ~_cmask_u;
608 ret.c |=
609 (c.c & _cblock2) << 24ULL |
610 (c.c & _cblock << 24ULL) >> 18ULL |
611 (c.c & _cblock << 30ULL) >> 30ULL;
612
613 return ret;
614 case U2:
615 ret.e = c.e & ~_emask_u;
616 ret.e |=
617 (c.e & (_eblock | _eblock << 20ULL)) << 5ULL |
618 (c.e & (_eblock << 5ULL | _eblock << 25ULL)) >> 5ULL;
619
620 ret.c = c.c & ~_cmask_u;
621 ret.c |=
622 (c.c & (_cblock | _cblock << 24ULL)) << 6ULL |
623 (c.c & (_cblock << 6ULL | _cblock << 30ULL)) >> 6ULL;
624
625 return ret;
626 case U3:
627 ret.e = c.e & ~_emask_u;
628 ret.e |=
629 (c.e & _eblock2) << 20ULL |
630 (c.e & _eblock << 25ULL) >> 25ULL |
631 (c.e & _eblock << 20ULL) >> 15ULL;
632
633 ret.c = c.c & ~_cmask_u;
634 ret.c |=
635 (c.c & _cblock) << 30ULL |
636 (c.c & _cblock << 6ULL) << 18ULL |
637 (c.c & _cblock2 << 24ULL) >> 24ULL;
638
639 return ret;
640 case D:
641 ret.e = c.e & ~_emask_d;
642 ret.e |=
643 (c.e & _eblock2 << 10ULL) << 20ULL |
644 (c.e & _eblock << 30ULL) >> 15ULL |
645 (c.e & _eblock << 35ULL) >> 25ULL;
646
647 ret.c = c.c & ~_cmask_d;
648 ret.c |=
649 (c.c & _cblock2 << 12ULL) << 24ULL |
650 (c.c & _cblock << 36ULL) >> 18ULL |
651 (c.c & _cblock << 42ULL) >> 30ULL;
652
653 return ret;
654 case D2:
655 ret.e = c.e & ~_emask_d;
656 ret.e |=
657 (c.e & (_eblock << 10ULL | _eblock << 30ULL)) << 5ULL |
658 (c.e & (_eblock << 15ULL | _eblock << 35ULL)) >> 5ULL;
659
660 ret.c = c.c & ~_cmask_d;
661 ret.c |=
662 (c.c & (_cblock << 12ULL | _cblock << 36ULL)) << 6ULL |
663 (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 6ULL;
664
665 return ret;
666 case D3:
667 ret.e = c.e & ~_emask_d;
668 ret.e |=
669 (c.e & _eblock << 10ULL) << 25ULL |
670 (c.e & _eblock << 15ULL) << 15ULL |
671 (c.e & _eblock2 << 30ULL) >> 20ULL;
672
673 ret.c = c.c & ~_cmask_d;
674 ret.c |=
675 (c.c & _cblock << 12ULL) << 30ULL |
676 (c.c & _cblock << 18ULL) << 18ULL |
677 (c.c & _cblock2 << 36ULL) >> 24ULL;
678
679 return ret;
680 case R:
681 ret.e = c.e & ~_emask_r;
682 ret.e |=
683 (c.e & _eblock << 20ULL) << 35ULL |
684 (c.e & _eblock << 55ULL) >> 20ULL |
685 (c.e & _eblock << 35ULL) << 5ULL |
686 (c.e & _eblock << 40ULL) >> 20ULL;
687
688 ret.c = c.c & ~_cmask_r;
689 ret.c |=
690 (c.c & _cblock) << 30ULL |
691 (c.c & _cblock << 30ULL) >> 12ULL |
692 (c.c & _cblock << 18ULL) << 18ULL |
693 (c.c & _cblock << 36ULL) >> 36ULL;
694
695 ret.c = coapply(ret.c, _comask_r);
696
697 return ret;
698 case R2:
699 ret.e = c.e & ~_emask_r;
700 ret.e |=
701 (c.e & (_eblock << 20ULL | _eblock << 40ULL)) << 15ULL |
702 (c.e & (_eblock << 35ULL | _eblock << 55ULL)) >> 15ULL;
703
704 ret.c = c.c & ~_cmask_r;
705 ret.c |=
706 (c.c & _cblock) << 18ULL |
707 (c.c & _cblock << 18ULL) >> 18ULL |
708 (c.c & _cblock << 30ULL) << 6ULL |
709 (c.c & _cblock << 36ULL) >> 6ULL;
710
711 return ret;
712 case R3:
713 ret.e = c.e & ~_emask_r;
714 ret.e |=
715 (c.e & (_eblock << 20ULL | _eblock << 35ULL)) << 20ULL |
716 (c.e & _eblock << 55ULL) >> 35ULL |
717 (c.e & _eblock << 40ULL) >> 5ULL;
718
719 ret.c = c.c & ~_cmask_r;
720 ret.c |=
721 (c.c & _cblock) << 36ULL |
722 (c.c & _cblock << 30ULL) >> 30ULL |
723 (c.c & _cblock << 18ULL) << 12ULL |
724 (c.c & _cblock << 36ULL) >> 18ULL;
725
726 ret.c = coapply(ret.c, _comask_r);
727
728 return ret;
729 case L:
730 ret.e = c.e & ~_emask_l;
731 ret.e |=
732 (c.e & _eblock2 << 25ULL) << 20ULL |
733 (c.e & _eblock << 45ULL) >> 15ULL |
734 (c.e & _eblock << 50ULL) >> 25ULL;
735
736 ret.c = c.c & ~_cmask_l;
737 ret.c |=
738 (c.c & _cblock << 6ULL) << 18ULL |
739 (c.c & _cblock << 12ULL) << 30ULL |
740 (c.c & _cblock << 24ULL) >> 12ULL |
741 (c.c & _cblock << 42ULL) >> 36ULL;
742
743 ret.c = coapply(ret.c, _comask_l);
744
745 return ret;
746 case L2:
747 ret.e = c.e & ~_emask_l;
748 ret.e |=
749 (c.e & (_eblock << 25ULL | _eblock << 45ULL)) << 5ULL |
750 (c.e & (_eblock << 30ULL | _eblock << 50ULL)) >> 5ULL;
751
752 ret.c = c.c & ~_cmask_l;
753 ret.c |=
754 (c.c & _cblock << 6ULL) << 6ULL |
755 (c.c & _cblock << 12ULL) >> 6ULL |
756 (c.c & _cblock << 24ULL) << 18ULL |
757 (c.c & _cblock << 42ULL) >> 18ULL;
758
759 return ret;
760 case L3:
761 ret.e = c.e & ~_emask_l;
762 ret.e |=
763 (c.e & _eblock << 25ULL) << 25ULL |
764 (c.e & _eblock << 30ULL) << 15ULL |
765 (c.e & _eblock2 << 45ULL) >> 20ULL;
766
767 ret.c = c.c & ~_cmask_l;
768 ret.c |=
769 (c.c & _cblock << 6ULL) << 36ULL |
770 (c.c & _cblock << 12ULL) << 12ULL |
771 (c.c & _cblock << 24ULL) >> 18ULL |
772 (c.c & _cblock << 42ULL) >> 30ULL;
773
774 ret.c = coapply(ret.c, _comask_l);
775
776 return ret;
777 case F:
778 ret.e = c.e & ~_emask_f;
779 ret.e |=
780 (c.e & _eblock) << 40ULL |
781 (c.e & _eblock << 15ULL) << 30ULL |
782 (c.e & _eblock << 40ULL) >> 25ULL |
783 (c.e & _eblock << 45ULL) >> 45ULL;
784
785 ret.e ^= _eomask_f;
786
787 ret.c = c.c & ~_cmask_f;
788 ret.c |=
789 (c.c & _cblock) << 36ULL |
790 (c.c & (_cblock << 24ULL | _cblock << 36ULL)) >> 24ULL |
791 (c.c & _cblock << 12ULL) << 12ULL;
792
793 ret.c = coapply(ret.c, _comask_f);
794
795 return ret;
796 case F2:
797 ret.e = c.e & ~_emask_f;
798 ret.e |=
799 (c.e & _eblock) << 15ULL |
800 (c.e & _eblock << 15ULL) >> 15ULL |
801 (c.e & _eblock << 40ULL) << 5ULL |
802 (c.e & _eblock << 45ULL) >> 5ULL;
803
804 ret.c = c.c & ~_cmask_f;
805 ret.c |=
806 (c.c & (_cblock | _cblock << 24ULL)) << 12ULL |
807 (c.c & (_cblock << 12ULL | _cblock << 36ULL)) >> 12ULL;
808
809 return ret;
810 case F3:
811 ret.e = c.e & ~_emask_f;
812 ret.e |=
813 (c.e & _eblock) << 45ULL |
814 (c.e & _eblock << 15ULL) << 25ULL |
815 (c.e & _eblock << 40ULL) >> 40ULL |
816 (c.e & _eblock << 45ULL) >> 30ULL;
817
818 ret.e ^= _eomask_f;
819
820 ret.c = c.c & ~_cmask_f;
821 ret.c |=
822 (c.c & (_cblock | _cblock << 12ULL)) << 24ULL |
823 (c.c & _cblock << 24ULL) >> 12ULL |
824 (c.c & _cblock << 36ULL) >> 36ULL;
825
826 ret.c = coapply(ret.c, _comask_f);
827
828 return ret;
829 case B:
830 ret.e = c.e & ~_emask_b;
831 ret.e |=
832 (c.e & _eblock2 << 5ULL) << 45ULL |
833 (c.e & _eblock << 50ULL) >> 40ULL |
834 (c.e & _eblock << 55ULL) >> 50ULL;
835
836 ret.e ^= _eomask_b;
837
838 ret.c = c.c & ~_cmask_b;
839 ret.c |=
840 (c.c & _cblock << 6ULL) << 36ULL |
841 (c.c & _cblock << 18ULL) << 12ULL |
842 (c.c & (_cblock << 30ULL | _cblock << 42ULL)) >> 24ULL;
843
844 ret.c = coapply(ret.c, _comask_b);
845
846 return ret;
847 case B2:
848 ret.e = c.e & ~_emask_b;
849 ret.e |=
850 (c.e & (_eblock << 5ULL | _eblock << 50ULL)) << 5ULL |
851 (c.e & (_eblock << 10ULL | _eblock << 55ULL)) >> 5ULL;
852
853 ret.c = c.c & ~_cmask_b;
854 ret.c |=
855 (c.c & (_cblock << 6ULL | _cblock << 30ULL)) << 12ULL |
856 (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 12ULL;
857
858 return ret;
859 case B3:
860 ret.e = c.e & ~_emask_b;
861 ret.e |=
862 (c.e & _eblock << 5ULL) << 50ULL |
863 (c.e & _eblock << 10ULL) << 40ULL |
864 (c.e & _eblock2 << 50ULL) >> 45ULL;
865
866 ret.e ^= _eomask_b;
867
868 ret.c = c.c & ~_cmask_b;
869 ret.c |=
870 (c.c & (_cblock << 6ULL | _cblock << 18ULL)) << 24ULL |
871 (c.c & _cblock << 30ULL) >> 12ULL |
872 (c.c & _cblock << 42ULL) >> 36ULL;
873
874 ret.c = coapply(ret.c, _comask_b);
875
876 return ret;
877 default:
878 goto move_unknown;
879 }
880
881move_unknown:
882#ifdef DEBUG
883 fprintf(stderr, "move error, unknow move\n");
884#endif
885 goto move_error;
886move_error:
887 return errorcube;
888}
diff --git a/old/manualsimd/cube.h b/old/manualsimd/cube.h
deleted file mode 100644
index b916f96..0000000
--- a/old/manualsimd/cube.h
+++ /dev/null
@@ -1,27 +0,0 @@
1typedef enum {
2 U, U2, U3, D, D2, D3,
3 R, R2, R3, L, L2, L3,
4 F, F2, F3, B, B2, B3
5} move_t;
6typedef struct {
7 uint64_t e;
8 uint64_t c;
9} cube_t;
10
11extern cube_t solvedcube;
12extern cube_t errorcube;
13
14bool isconsistent(cube_t);
15bool issolved(cube_t);
16
17cube_t readcube(char *);
18void writecube(cube_t, char *);
19
20int readmoves(char *, move_t *);
21void writemoves(move_t *, int, char *);
22
23cube_t move(cube_t, move_t);
24
25/*
26cube_t inverse(cube_t);
27*/

Generated with cgit - Back to sebastiano.tronto.net