commit c04a283a7ab97903683f5f7268068aef69f5bddf
parent 7812684339d03f6993882358b0045c1bc2d5032c
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Thu, 13 Jun 2024 22:28:49 +0200
Added benchmark; removed old folder
Diffstat:
13 files changed, 124 insertions(+), 1173 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,7 +1,5 @@
-generated
config.mk
benchmark/results
-old/benchmark/results
benchmark/run
gen
debuggen
diff --git a/Makefile b/Makefile
@@ -18,7 +18,7 @@ test: debugcube.o
CUBETYPE=${CUBETYPE} TEST=${TEST} ./test/test.sh
benchmark: cube.o
- CUBETYPE=${CUBETYPE} ./benchmark/bench.sh
+ CUBETYPE=${CUBETYPE} ./benchmark/benchmark.sh
gen: cube.o
${CC} ${CFLAGS} -o gen cube.o tables/tables.c
diff --git a/TODO.txt b/TODO.txt
@@ -1,4 +1,9 @@
+Fixes
+ - tables/tables.c: fix, use new nissy_gendata and nissy_datasize
+
Solver
+ - benchmark for solve
+ table generation, where to keep tables? in benchmark folder or in tables/?
- write a solver (how many tricks? some, but not all are needed)
More utilities for tables (in cube.h)
diff --git a/benchmark/00_gendata_h48/gendata_h48_benchmark.c b/benchmark/00_gendata_h48/gendata_h48_benchmark.c
@@ -0,0 +1,42 @@
+#include "../benchmark.h"
+#include "../../src/cube.h"
+
+#define MAXDEPTH 10
+#define HVALUE 2
+#define OPTIONS "2;10"
+#define LONGOPTIONS "h = 2, max depth = 10"
+
+char *buf;
+
+void run(void) {
+ uint32_t *buf32;
+ int i;
+ int64_t s;
+
+ s = nissy_gendata("H48", OPTIONS, buf);
+
+ if (s == -1) {
+ printf("Error generating table\n");
+ } else {
+ printf("Succesfully generated %" PRId64 " bytes. Table:\n", s);
+ buf32 = (uint32_t *)&buf[s-sizeof(uint32_t)*(MAXDEPTH+1)];
+ for (i = 0; i <= MAXDEPTH; i++)
+ printf("%d:\t%" PRId32 "\n", i, buf32[i]);
+ }
+}
+
+int main() {
+ int64_t size;
+
+ size = nissy_datasize("H48", OPTIONS);
+ if (size == -1) {
+ printf("gendata_h48 benchmark: error in datasize\n");
+ return 1;
+ }
+
+ buf = malloc(size);
+
+ time_benchmark(run, "gendata_h48 " LONGOPTIONS);
+
+ return 0;
+}
diff --git a/benchmark/benchmark.h b/benchmark/benchmark.h
@@ -0,0 +1,39 @@
+#include <stdbool.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+
+double
+time_benchmark(void (*run)(void), char *name)
+{
+ struct timespec start, end;
+ double tdiff, tdsec, tdnano;
+
+ printf("\n");
+ fflush(stdout);
+
+ if (run == NULL) {
+ printf("> %s: nothing to run!\n", name);
+ fflush(stdout);
+ return -1.0;
+ }
+
+ printf("Benchmark: %s\n\n", name);
+ printf("==========\n");
+ fflush(stdout);
+
+ clock_gettime(CLOCK_MONOTONIC, &start);
+ run();
+ clock_gettime(CLOCK_MONOTONIC, &end);
+
+ tdsec = end.tv_sec - start.tv_sec;
+ tdnano = end.tv_nsec - start.tv_nsec;
+ tdiff = tdsec + 1e-9 * tdnano;
+
+ printf("==========\n");
+ printf("\nTotal time: %.4fs\n", tdiff);
+ fflush(stdout);
+
+ return tdiff;
+}
diff --git a/benchmark/benchmark.sh b/benchmark/benchmark.sh
@@ -0,0 +1,27 @@
+#!/bin/sh
+
+re="${RUN:-$@}"
+
+CC="cc -std=c99 -pedantic -Wall -Wextra \
+ -Wno-unused-parameter -Wno-unused-function -O3 -D$CUBETYPE \
+ -D_POSIX_C_SOURCE=199309L"
+
+[ "$CUBETYPE" = "CUBE_AVX2" ] && CC="$CC -mavx2"
+
+BIN="benchmark/run"
+RES="benchmark/results"
+CUBEOBJ="cube.o"
+d="$(date +'%Y-%m-%d-%H-%M-%S')"
+
+mkdir -p "$RES"
+
+for t in benchmark/*; do
+ if [ -n "$re" ] && [ -z "$(echo "$t" | grep "$re")" ]; then
+ continue
+ fi
+ if [ ! -d "$t" ] || [ "$t" = "benchmark/results" ]; then continue; fi
+ $CC -o $BIN $t/*.c $CUBEOBJ || exit 1;
+ $BIN | tee "$RES/results-$d.txt" "$RES/results-last.txt"
+done
+
+rm -rf $BIN $CUBEOBJ
diff --git a/old/benchmark/bench.c b/old/benchmark/bench.c
@@ -1,83 +0,0 @@
-#include <stdbool.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-
-#include "../cube.h"
-
-#define MOVES 100000000
-#define TRANS 100000000
-#define COMPOSE 100000000
-#define INVERSE 100000000
-
-double
-bench(cube_t (*run)(int64_t), int64_t n, char *name)
-{
- char str[1000];
- cube_t cube;
- struct timespec start, end;
- double tdiff, tdsec, tdnano;
-
- printf("\n");
- fflush(stdout);
-
- if (run == NULL) {
- printf("> %s: nothing to run!\n", name);
- fflush(stdout);
- return -1.0;
- }
-
- printf("> %s: running benchmark...\n", name);
- fflush(stdout);
- clock_gettime(CLOCK_MONOTONIC, &start);
-
- cube = run(n);
- writecube("H48", cube, str);
- str[3] = 0;
- printf("> %s: resulting cube, first piece: %s\n", name, str);
- fflush(stdout);
-
- clock_gettime(CLOCK_MONOTONIC, &end);
- tdsec = end.tv_sec - start.tv_sec;
- tdnano = end.tv_nsec - start.tv_nsec;
- tdiff = tdsec + 1e-9 * tdnano;
- printf("> %s: %.4fs\n", name, tdiff);
- fflush(stdout);
-
- return tdiff;
-}
-
-int main() {
- double tmoves, ttrans, tcompose, tinverse;
-
- printf(
- "Benchmarks settings:\n"
- "MOVES:\t%d\nTRANS:\t%d\nCOMPOSE:\t%d\nINVERSE:\t%d\n",
- MOVES, TRANS, COMPOSE, INVERSE
- );
- fflush(stdout);
-
- srand(time(NULL));
-
- tmoves = bench(run_moves, MOVES, "moves");
- ttrans = bench(run_trans, TRANS, "trans");
- tcompose = bench(run_compose, COMPOSE, "compose");
- tinverse = bench(run_inverse, INVERSE, "inverse");
-
- printf(
- "\nBenchmark summary:\n"
- "moves: %d moves in %.4fs (%.4f MTPS)\n"
- "trans: %d transformations in %.4fs (%.4f MTPS)\n"
- "compose: %d compositions in %.4fs (%.4f MCPS)\n"
- "inverse: %d inverses in %.4fs (%.4f MIPS)\n"
- "Total time: %.4f\n",
- MOVES, tmoves, MOVES / (1e6 * tmoves),
- TRANS, ttrans, TRANS / (1e6 * ttrans),
- COMPOSE, tcompose, COMPOSE / (1e6 * tcompose),
- INVERSE, tinverse, INVERSE / (1e6 * tinverse),
- tmoves + ttrans + tcompose + tinverse
- );
-
- return 0;
-}
diff --git a/old/benchmark/bench.sh b/old/benchmark/bench.sh
@@ -1,21 +0,0 @@
-#!/bin/sh
-
-CC="cc -std=c99 -O3 -D$CUBETYPE"
-if [ "$CUBETYPE" = "CUBE_AVX2" ]; then
- CC="$CC -mavx2"
-fi
-
-BENCHBIN="benchmark/run"
-BENCHDIR="benchmark/results"
-CUBEOBJ="cube.o"
-
-$CC -D_POSIX_C_SOURCE=199309L -o $BENCHBIN benchmark/bench.c $CUBEOBJ || exit 1
-
-d="$(date +'%Y-%m-%d-%H-%M-%S')"
-mkdir -p "$BENCHDIR"
-$BENCHBIN | tee "$BENCHDIR/results-$d.txt" "$BENCHDIR/results.txt"
-
-echo ""
-echo "Results saved to $BENCHDIR/results.txt"
-
-rm -rf $BENCHBIN $CUBEOBJ
diff --git a/old/benchmark/cube-bench.c b/old/benchmark/cube-bench.c
@@ -1,147 +0,0 @@
-/******************************************************************************
-Section: benchmarks
-
-Here you can find some simple functions that can be used to benchmark the
-rest of the code.
-******************************************************************************/
-
-#define RANDOMCUBES 157
-
-static void
-setup_randomcubes(cube_fast_t *cubes)
-{
- int i;
-
- for (i = 0; i < RANDOMCUBES; i++)
- cubes[i] = run_moves(i*4);
-}
-
-cube_t
-run_moves(int64_t n)
-{
- cube_fast_t fast;
- int64_t m, i;
-
- fast = solvedcube();
- m = n / 18;
-
- for (i = 0; i < m; i++) {
- fast = _move_U(fast);
- fast = _move_U2(fast);
- fast = _move_U3(fast);
- fast = _move_D(fast);
- fast = _move_D2(fast);
- fast = _move_D3(fast);
- fast = _move_R(fast);
- fast = _move_R2(fast);
- fast = _move_R3(fast);
- fast = _move_L(fast);
- fast = _move_L2(fast);
- fast = _move_L3(fast);
- fast = _move_F(fast);
- fast = _move_F2(fast);
- fast = _move_F3(fast);
- fast = _move_B(fast);
- fast = _move_B2(fast);
- fast = _move_B3(fast);
- }
-
- for (i = m * 18; i < n; i++)
- fast = _move_F(fast);
-
- return fast;
-}
-
-cube_t
-run_trans(int64_t n)
-{
- cube_fast_t fast;
- int64_t m, i;
-
- fast = run_moves(33);
- m = n / 18;
-
- for (i = 0; i < m; i++) {
- fast = _trans_UFr(fast);
- fast = _trans_ULr(fast);
- fast = _trans_UBr(fast);
- fast = _trans_URr(fast);
- fast = _trans_DFr(fast);
- fast = _trans_DLr(fast);
- fast = _trans_DBr(fast);
- fast = _trans_DRr(fast);
- fast = _trans_RUr(fast);
- fast = _trans_RFr(fast);
- fast = _trans_RDr(fast);
- fast = _trans_RBr(fast);
- fast = _trans_LUr(fast);
- fast = _trans_LFr(fast);
- fast = _trans_LDr(fast);
- fast = _trans_LBr(fast);
- fast = _trans_FUr(fast);
- fast = _trans_FRr(fast);
- fast = _trans_FDr(fast);
- fast = _trans_FLr(fast);
- fast = _trans_BUr(fast);
- fast = _trans_BRr(fast);
- fast = _trans_BDr(fast);
- fast = _trans_BLr(fast);
- fast = _trans_UFm(fast);
- fast = _trans_ULm(fast);
- fast = _trans_UBm(fast);
- fast = _trans_URm(fast);
- fast = _trans_DFm(fast);
- fast = _trans_DLm(fast);
- fast = _trans_DBm(fast);
- fast = _trans_DRm(fast);
- fast = _trans_RUm(fast);
- fast = _trans_RFm(fast);
- fast = _trans_RDm(fast);
- fast = _trans_RBm(fast);
- fast = _trans_LUm(fast);
- fast = _trans_LFm(fast);
- fast = _trans_LDm(fast);
- fast = _trans_LBm(fast);
- fast = _trans_FUm(fast);
- fast = _trans_FRm(fast);
- fast = _trans_FDm(fast);
- fast = _trans_FLm(fast);
- fast = _trans_BUm(fast);
- fast = _trans_BRm(fast);
- fast = _trans_BDm(fast);
- fast = _trans_BLm(fast);
- }
-
- for (i = m * 18; i < n; i++)
- fast = _trans_FRm(fast);
-
- return fast;
-}
-
-cube_t
-run_compose(int64_t n)
-{
- cube_fast_t fast, cubes[RANDOMCUBES];
- int64_t i;
-
- setup_randomcubes(cubes);
-
- for (i = 0; i < n; i++)
- fast = compose_fast(fast, cubes[i % RANDOMCUBES]);
-
- return fast;
-}
-
-cube_t
-run_inverse(int64_t n)
-{
- cube_fast_t fast, cubes[RANDOMCUBES];
- int64_t i;
-
- setup_randomcubes(cubes);
-
- for (i = 0; i < n; i++)
- fast = inverse_fast(cubes[i % RANDOMCUBES]);
-
- return fast;
-}
diff --git a/old/manualsimd/cube.c b/old/manualsimd/cube.c
@@ -1,888 +0,0 @@
-/*
-# Cube representation, moves, transformations and (tentatively) indexing
-
-## Textual description
-
-The functions readcube() and writecube() use the following format.
-Each edge is represented by two letters denoting the sides it belongs to
-and one number denoting its orientation (0 oriented, 1 mis-oriented).
-Similarly, each corner is represented by three letters and a number
-(0 oriented, 1 twisted clockwise, 2 twisted counter-clockwise).
-Edge orientation is relative to the F / B axis, corner orientation is
-relative to the U / D axis.
-
-The correct order of the pieces is the same as that defined in the
-section "Internal cube representation", except that pieces are read
-left-to-right. Pieces are divided by slices, so the ordering is not the
-most intuitive, but it is more convenient for the internal representation.
-
-Whitespaces between pieces are ignored when reading the cube, and a
-single whitespace character is added between pieces when writing.
-
-For example, the solved cube looks like this:
-
-UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 \ (no newline)
-UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
-
-The cube after the moves R'U'F looks like this:
-
-FL1 BR0 DB0 UR1 UF0 UB0 DL0 FR0 UL1 DF1 BL0 DR0 \ (no newline)
-UBL1 DBR1 UFR2 DFR2 DFL2 UBL2 UFL2 DBL0
-
-More formats might be supported in the future.
-
-## Internal cube representation
-
-The cube_t data structure implemented in this file is designed to
-efficiently perform common operations on a 3x3x3 Rubik's cube when
-solving it with an iterative-deepening DFS search. It is not the most
-general, complete, easy to read or compact one. Since the cube can
-be trivially reoriented before the search, we only encode permutations
-of the cube that keep the center pieces in a fixed position (that is,
-we do not encode the position of the centers).
-
-The cube state is encoded in two 64-bit integers, one for edges and one
-for centers. We explain how edges are encoded first, and the highlight
-the few differences with corners afterwards.
-
-For encoding edges, only the 60 least-significant bits are used. Each
-edge described by 5 bits. The position of a 5-bit block in the 64-bit
-integer determine the position of the edge piece in the cube, according
-to the following table (least-significant bits on the right):
-
-55-59 50-54 45-49 40-44 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
- BR BL FL FR DR DL UL UR DF DB UB UF
-ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee ossee
-
-For each edge, the 4 least-significant bits ('ssee' in the table)
-determine the piece. The two bits marked with 'ss' determine the internal
-slice the piece belongs to, i.e. they are either '00' for M, '01' for
-S or '10' for E. The other two bits (marked with 'ee') determine the
-actual edge piece among the 4 in the same slice, and they are assigned
-somewhat arbitarily. Using this representation and the ordering defined
-in the table above, the edges are correctly permuted when these 4 bits
-for each represent the numbers 0 to 11 in the correct order.
-
-The last bit determines the orientation. The orientation of an edge
-depends on its position, and it is defined being 0 if the edge can be
-moved to its place in the solved orientation by permutations in the
-subgroup <U, D, R, L, F2, B2>.
-
-Corners are encoded in the 48 least-significant bits, and are described
-by 6 bits each, their position being defined by the following table:
-
- 35-39 30-34 25-29 20-24 15-19 10-14 5-9 0-4
- DBL DFL UBR UFL DBR DFL UBL UFR
-oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc oooxcc
-
-The bit marked with an 'x' describes the axis the corner belongs to.
-The 0 axis consists of the corners UFR, UBL, DFL and DBR, and the other
-four corners form the axis marked with 1. Then two bits are needed to
-identify the corner among the four of the same axis. The last three bits
-determine the orientation, where one corner is defined to be oriented
-(marked with '000') if its top or bottom sticker faces the top or bottom
-side. A corner a clockwise turn away from being oriented, thus requiring
-a counter-clockwise turn to be oriented correctly, is marked with '001',
-and a corner a counter-clockwise turn away is marked with '010'. The most
-significant bit is not used to determine the corner orientation, but it
-must always be set to '0' to simplify the moving operations (see below).
-
-## Basic moves
-
-The 18 basic moves of the cube could be performed by applying a suitable
-general permutation (see below), but they have instead been manually
-implemented with a few simple operations each, to improve performance.
-
-For each move we first permute the pieces. This amounts to shifting
-around 4 blocks of bits for edges and 4 for corners. Since in some cases
-adjacent pieces on the cube are also adjacent in the bit representation we
-use, we can save some operations by shifting multiple blocks together.
-
-There are some moves that change the orientation of the pieces. Namely,
-the moves F, F', B and B' change the orientation of the edges and those
-moves as well as R, R', L and L' change the orientation of the corners.
-Edge orientation is easy to address: we simply xor the edge representation
-by a bit mask with zeroes everywhere except for the 4 edges that need
-to be flipped (i.e. the ones on the twisted face).
-
-Corner orientation is harder to reproduce efficiently working only with
-bitwise operations, as it involves performing operations modulo 3.
-However, with the help of the extra bit we reserved, we are able to
-do this using only two additions and 3 bitwise operations, without
-any multiplication, division or modulo operation. The trick is
-to use the following formula to sum two numbers x, y in {0,1,2}:
-
- ((x+y) + (x+y+1)/4) % 4
-
-The thrid bit is needed because x+y and x+y+1 can exceed 3. We can
-apply this operation to multiple pairs of bits representing ternary
-digits at once using binary operations. See the function coapply()
-below for the details.
-
-## Inverting the cube
-
-TODO
-
-## Transformations (conjugations by full-cube rotations)
-
-TODO
-
-## Indexing (tentative)
-
-TODO - subgroup description etc
-
-*/
-
-#include <stdbool.h>
-#include <stdint.h>
-#include <string.h>
-
-#ifdef DEBUG
-#include <stdio.h>
-#endif
-
-#include "cube.h"
-
-#define _error 0xFFFFFFFF
-
-#define _eoblock 0x10ULL /* 10000 */
-#define _epblock 0x0FULL /* 01111 */
-#define _eblock 0x1FULL /* 11111 */
-#define _eblock2 0x3FFULL /* 1111111111 */
-
-#define _coblock 0x18ULL /* 011000 */
-#define _cpblock 0x07ULL /* 000111 */
-#define _cblock 0x3FULL /* 111111 */
-#define _cblock2 0xFFFULL /* 111111111111 */
-
-#define _eomask 0x842108421084210ULL /* 10000 repeated 12 times */
-#define _comask 0x618618618618ULL /* 011000 repeated 8 times */
-#define _coonemask 0x208208208208ULL /* 001000 repeated 8 times */
-#define _coextramask 0x820820820820ULL /* 100000 repeated 8 times */
-
-#define _emask_u (_eblock2 | _eblock2 << 20ULL)
-#define _emask_d (_eblock2 << 10ULL | _eblock2 << 30ULL)
-#define _emask_r (_eblock << 20ULL | _eblock2 << 35ULL | _eblock << 55ULL)
-#define _emask_l (_eblock2 << 45ULL | _eblock2 << 25ULL)
-#define _emask_f (_eblock | _eblock << 15ULL | _eblock2 << 40ULL)
-#define _emask_b (_eblock2 << 5ULL | _eblock2 << 50ULL)
-
-#define _cmask_u (_cblock2 | _cblock2 << 24ULL)
-#define _cmask_d (_cblock2 << 12ULL | _cblock2 << 36ULL)
-#define _cmask_r (_cblock | _cblock << 18ULL | _cblock2 << 30ULL)
-#define _cmask_l (_cblock2 << 6ULL | _cblock << 24ULL | _cblock << 42ULL)
-#define _cmask_f (_cblock | _cblock << 12ULL | _cblock << 24ULL | _cblock << 36ULL)
-#define _cmask_b (_cblock << 6ULL | _cblock << 18ULL | _cblock << 30ULL | _cblock << 42ULL)
-
-#define _eomask_f (1ULL << 4ULL | 1ULL << 19ULL | 1ULL << 44ULL | 1ULL << 49ULL)
-#define _eomask_b (1ULL << 9ULL | 1ULL << 14ULL | 1ULL << 54ULL | 1ULL << 59ULL)
-
-#define _comask_r (2ULL << 3ULL | 1ULL << 33ULL | 2ULL << 21ULL | 1ULL << 39ULL)
-#define _comask_l (1ULL << 27ULL | 2ULL << 9ULL | 2ULL << 15ULL | 1ULL << 45ULL)
-#define _comask_f (1ULL << 3ULL | 1ULL << 15ULL | 2ULL << 27ULL | 2ULL << 39ULL)
-#define _comask_b (1ULL << 9ULL | 1ULL << 21ULL | 2ULL << 33ULL | 2ULL << 45ULL)
-
-static inline uint64_t coapply(uint64_t, uint64_t);
-static uint64_t permsign(uint64_t *, int);
-static uint64_t readep(char *);
-static uint64_t readeo(char *);
-static uint64_t readcp(char *);
-static uint64_t readco(char *);
-static uint64_t readmove(char);
-static uint64_t readmodifier(char);
-
-static char *edgestr[] = {
- "UF", "UB", "DB", "DF",
- "UR", "UL", "DL", "DR",
- "FR", "FL", "BL", "BR"
-};
-static char *cornerstr[] = {
- "UFR", "UBL", "DFL", "DBR",
- "UFL", "UBR", "DFR", "DBL"
-};
-static char *cornerstralt[] = {
- "URF", "ULB", "DLF", "DRB",
- "ULF", "URB", "DRF", "DLB"
-};
-static char *movestr[] = {
- [U] = "U", [U2] = "U2", [U3] = "U'",
- [D] = "D", [D2] = "D2", [D3] = "D'",
- [R] = "R", [R2] = "R2", [R3] = "R'",
- [L] = "L", [L2] = "L2", [L3] = "L'",
- [F] = "F", [F2] = "F2", [F3] = "F'",
- [B] = "B", [B2] = "B2", [B3] = "B'",
-};
-
-cube_t solvedcube = { .e = 0x5A928398A418820ULL, .c = 0x1C61440C2040ULL };
-cube_t errorcube = { .e = _error, .c = _error };
-
-
-static uint64_t
-permsign(uint64_t *a, int n)
-{
- int i, j;
- uint64_t ret;
-
- 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;
-}
-
-bool
-isconsistent(cube_t cube)
-{
- uint64_t x, p[12], sum, co;
- bool found[12];
- int i;
-
- sum = 0;
-
- /* Check for EP consistency */
- for (i = 0; i < 12; i++)
- found[i] = false;
- for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
- p[i] = x & _epblock;
- if (p[i] >= 12)
- goto inconsistent_ep;
- found[p[i]] = true;
- }
- for (i = 0; i < 12; i++)
- if (!found[i])
- goto inconsistent_ep;
- sum = permsign(p, 12);
-
- /* Check for CP consistency */
- for (i = 0; i < 8; i++)
- found[i] = false;
- for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
- p[i] = x & _cpblock;
- if (p[i] >= 8)
- goto inconsistent_cp;
- found[p[i]] = true;
- }
- for (i = 0; i < 8; i++)
- if (!found[i])
- goto inconsistent_cp;
- sum += permsign(p, 8);
-
- /* Check permutation parity */
- if (sum % 2 != 0)
- goto inconsistent_parity;
-
- /* Check for EO parity */
- for (i = 0, sum = 0, x = cube.e; i < 12; i++, x >>= 5ULL)
- sum += (x & _eoblock) >> 4ULL;
- if (sum % 2 != 0)
- goto inconsistent_eo;
-
- /* Check for CO parity */
- for (i = 0, sum = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
- co = (x & _coblock) >> 3ULL;
- if (co > 2)
- goto inconsistent_co3;
- sum += co;
- }
- if (sum % 3 != 0)
- goto inconsistent_co;
-
- /* Check that CO extra bit is zero */
- if (cube.c & _coextramask)
- goto inconsistent_coextra;
-
- return true;
-
-inconsistent_ep:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent EP\n");
-#endif
- goto inconsistent_return;
-inconsistent_cp:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent CP\n");
-#endif
- goto inconsistent_return;
-inconsistent_parity:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent parity\n");
-#endif
- goto inconsistent_return;
-inconsistent_eo:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent EO\n");
-#endif
- goto inconsistent_return;
-inconsistent_co3:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent CO=3\n");
-#endif
- goto inconsistent_return;
-inconsistent_co:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent CO\n");
-#endif
- goto inconsistent_return;
-inconsistent_coextra:
-#ifdef DEBUG
- fprintf(stderr, "Inconsistent extra bit for CO\n");
-#endif
- goto inconsistent_return;
-inconsistent_return:
- return false;
-}
-
-bool
-issolved(cube_t cube)
-{
- return cube.c == solvedcube.c && cube.e == solvedcube.e;
-}
-
-
-static uint64_t
-readep(char *str)
-{
- uint64_t e;
-
- for (e = 0; e < 12; e++)
- if (!strncmp(str, edgestr[e], 2))
- return e;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading EP\n");
-#endif
- return _error;
-}
-
-static uint64_t
-readeo(char *str)
-{
- if (*str == '0')
- return 0ULL;
- if (*str == '1')
- return 1ULL;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading EO\n");
-#endif
- return _error;
-}
-
-static uint64_t
-readcp(char *str)
-{
- uint64_t c;
-
- for (c = 0; c < 8; c++)
- if (!strncmp(str, cornerstr[c], 3) ||
- !strncmp(str, cornerstralt[c], 3))
- return c;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading CP\n");
-#endif
- return _error;
-}
-
-static uint64_t
-readco(char *str)
-{
- if (*str == '0')
- return 0ULL;
- if (*str == '1')
- return 1ULL;
- if (*str == '2')
- return 2ULL;
-
-#ifdef DEBUG
- fprintf(stderr, "Error reading CO\n");
-#endif
- return _error;
-}
-
-cube_t
-readcube(char *buf)
-{
- int i;
- uint64_t piece, orient;
- cube_t ret = {0};
- char *b = buf;
-
- for (i = 0; i < 12; i++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if ((piece = readep(b)) == _error)
- goto readcube_error;
- b += 2;
- if ((orient = readeo(b)) == _error)
- goto readcube_error;
- b++;
- ret.e |= (piece << (i * 5ULL)) | (orient << (i * 5ULL + 4ULL));
- }
- for (i = 0; i < 8; i++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if ((piece = readcp(b)) == _error)
- goto readcube_error;
- b += 3;
- if ((orient = readco(b)) == _error)
- goto readcube_error;
- b++;
- ret.c |= (piece << (i * 6ULL)) | (orient << (i * 6ULL + 3ULL));
- }
-
- return ret;
-
-readcube_error:
-#ifdef DEBUG
- fprintf(stderr, "readcube error\n");
-#endif
- return errorcube;
-}
-
-void
-writecube(cube_t cube, char *buf)
-{
- char *errormsg;
- uint64_t piece, orien, x;
- size_t len;
- int i;
-
- if (!isconsistent(cube)) {
- errormsg = "ERROR: cannot write inconsistent cube";
- goto writecube_error;
- }
-
- for (i = 0, x = cube.e; i < 12; i++, x >>= 5ULL) {
- piece = x & _epblock;
- orien = (x & _eoblock) >> 4ULL;
- buf[4*i ] = edgestr[piece][0];
- buf[4*i + 1] = edgestr[piece][1];
- buf[4*i + 2] = orien + '0';
- buf[4*i + 3] = ' ';
- }
- for (i = 0, x = cube.c; i < 8; i++, x >>= 6ULL) {
- piece = x & _cpblock;
- orien = (x & _coblock) >> 3ULL;
- buf[48 + 5*i ] = cornerstr[piece][0];
- buf[48 + 5*i + 1] = cornerstr[piece][1];
- buf[48 + 5*i + 2] = cornerstr[piece][2];
- buf[48 + 5*i + 3] = orien + '0';
- buf[48 + 5*i + 4] = ' ';
- }
-
- buf[48+39] = '\0';
-
- return;
-
-writecube_error:
-#ifdef DEBUG
- fprintf(stderr, "writecube error, see stdout for details\n");
-#endif
- len = strlen(errormsg);
- memcpy(buf, errormsg, len);
- buf[len] = '\n';
- buf[len+1] = '\0';
-}
-
-
-static uint64_t
-readmove(char c)
-{
- switch (c) {
- case 'U':
- return U;
- case 'D':
- return D;
- case 'R':
- return R;
- case 'L':
- return L;
- case 'F':
- return F;
- case 'B':
- return B;
- default:
- return _error;
- }
-}
-
-static uint64_t
-readmodifier(char c)
-{
- switch (c) {
- case '1': /* Fallthrough */
- case '2': /* Fallthrough */
- case '3':
- return c - '0' - 1;
- case '\'':
- return 2;
- default:
- return 0;
- }
-}
-
-int
-readmoves(char *buf, move_t *m)
-{
- int n;
- uint64_t r;
- char *b;
-
- for (b = buf, n = 0; *b != '\0'; b++) {
- while (*b == ' ' || *b == '\t' || *b == '\n')
- b++;
- if (*b == '\0')
- return n;
- if ((r = readmove(*b)) == _error)
- goto readmoves_error;
- m[n] = (move_t)r;
- if ((r = readmodifier(*(b+1))) != 0) {
- b++;
- m[n] += r;
- }
- n++;
- }
-
- return n;
-
-readmoves_error:
-#ifdef DEBUG
- fprintf(stderr, "readmoves error\n");
-#endif
- return -1;
-}
-
-void
-writemoves(move_t *m, int n, char *buf)
-{
- int i;
- size_t len;
- char *b, *s;
-
- for (i = 0, b = buf; i < n; i++, b++) {
- s = movestr[m[i]];
- len = strlen(s);
- memcpy(b, s, len);
- b += len;
- *b = ' ';
- }
- *b = '\0';
-}
-
-
-static inline uint64_t
-coapply(uint64_t c, uint64_t m)
-{
- uint64_t z, b;
-
- z = c + m;
- b = ((z + _coonemask) & _coextramask) >> 2ULL;
-
- return (z + b) & ~_coextramask;
-}
-
-cube_t
-move(cube_t c, move_t m)
-{
- cube_t ret = {0};
-
-#ifdef DEBUG
- if (!isconsistent(c)) {
- fprintf(stderr, "move error, inconsistent cube\n");
- goto move_error;
- }
-#endif
-
- switch (m) {
- case U:
- ret.e = c.e & ~_emask_u;
- ret.e |=
- (c.e & _eblock) << 25ULL |
- (c.e & _eblock << 5ULL) << 15ULL |
- (c.e & _eblock2 << 20ULL) >> 20ULL;
-
- ret.c = c.c & ~_cmask_u;
- ret.c |=
- (c.c & _cblock2) << 24ULL |
- (c.c & _cblock << 24ULL) >> 18ULL |
- (c.c & _cblock << 30ULL) >> 30ULL;
-
- return ret;
- case U2:
- ret.e = c.e & ~_emask_u;
- ret.e |=
- (c.e & (_eblock | _eblock << 20ULL)) << 5ULL |
- (c.e & (_eblock << 5ULL | _eblock << 25ULL)) >> 5ULL;
-
- ret.c = c.c & ~_cmask_u;
- ret.c |=
- (c.c & (_cblock | _cblock << 24ULL)) << 6ULL |
- (c.c & (_cblock << 6ULL | _cblock << 30ULL)) >> 6ULL;
-
- return ret;
- case U3:
- ret.e = c.e & ~_emask_u;
- ret.e |=
- (c.e & _eblock2) << 20ULL |
- (c.e & _eblock << 25ULL) >> 25ULL |
- (c.e & _eblock << 20ULL) >> 15ULL;
-
- ret.c = c.c & ~_cmask_u;
- ret.c |=
- (c.c & _cblock) << 30ULL |
- (c.c & _cblock << 6ULL) << 18ULL |
- (c.c & _cblock2 << 24ULL) >> 24ULL;
-
- return ret;
- case D:
- ret.e = c.e & ~_emask_d;
- ret.e |=
- (c.e & _eblock2 << 10ULL) << 20ULL |
- (c.e & _eblock << 30ULL) >> 15ULL |
- (c.e & _eblock << 35ULL) >> 25ULL;
-
- ret.c = c.c & ~_cmask_d;
- ret.c |=
- (c.c & _cblock2 << 12ULL) << 24ULL |
- (c.c & _cblock << 36ULL) >> 18ULL |
- (c.c & _cblock << 42ULL) >> 30ULL;
-
- return ret;
- case D2:
- ret.e = c.e & ~_emask_d;
- ret.e |=
- (c.e & (_eblock << 10ULL | _eblock << 30ULL)) << 5ULL |
- (c.e & (_eblock << 15ULL | _eblock << 35ULL)) >> 5ULL;
-
- ret.c = c.c & ~_cmask_d;
- ret.c |=
- (c.c & (_cblock << 12ULL | _cblock << 36ULL)) << 6ULL |
- (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 6ULL;
-
- return ret;
- case D3:
- ret.e = c.e & ~_emask_d;
- ret.e |=
- (c.e & _eblock << 10ULL) << 25ULL |
- (c.e & _eblock << 15ULL) << 15ULL |
- (c.e & _eblock2 << 30ULL) >> 20ULL;
-
- ret.c = c.c & ~_cmask_d;
- ret.c |=
- (c.c & _cblock << 12ULL) << 30ULL |
- (c.c & _cblock << 18ULL) << 18ULL |
- (c.c & _cblock2 << 36ULL) >> 24ULL;
-
- return ret;
- case R:
- ret.e = c.e & ~_emask_r;
- ret.e |=
- (c.e & _eblock << 20ULL) << 35ULL |
- (c.e & _eblock << 55ULL) >> 20ULL |
- (c.e & _eblock << 35ULL) << 5ULL |
- (c.e & _eblock << 40ULL) >> 20ULL;
-
- ret.c = c.c & ~_cmask_r;
- ret.c |=
- (c.c & _cblock) << 30ULL |
- (c.c & _cblock << 30ULL) >> 12ULL |
- (c.c & _cblock << 18ULL) << 18ULL |
- (c.c & _cblock << 36ULL) >> 36ULL;
-
- ret.c = coapply(ret.c, _comask_r);
-
- return ret;
- case R2:
- ret.e = c.e & ~_emask_r;
- ret.e |=
- (c.e & (_eblock << 20ULL | _eblock << 40ULL)) << 15ULL |
- (c.e & (_eblock << 35ULL | _eblock << 55ULL)) >> 15ULL;
-
- ret.c = c.c & ~_cmask_r;
- ret.c |=
- (c.c & _cblock) << 18ULL |
- (c.c & _cblock << 18ULL) >> 18ULL |
- (c.c & _cblock << 30ULL) << 6ULL |
- (c.c & _cblock << 36ULL) >> 6ULL;
-
- return ret;
- case R3:
- ret.e = c.e & ~_emask_r;
- ret.e |=
- (c.e & (_eblock << 20ULL | _eblock << 35ULL)) << 20ULL |
- (c.e & _eblock << 55ULL) >> 35ULL |
- (c.e & _eblock << 40ULL) >> 5ULL;
-
- ret.c = c.c & ~_cmask_r;
- ret.c |=
- (c.c & _cblock) << 36ULL |
- (c.c & _cblock << 30ULL) >> 30ULL |
- (c.c & _cblock << 18ULL) << 12ULL |
- (c.c & _cblock << 36ULL) >> 18ULL;
-
- ret.c = coapply(ret.c, _comask_r);
-
- return ret;
- case L:
- ret.e = c.e & ~_emask_l;
- ret.e |=
- (c.e & _eblock2 << 25ULL) << 20ULL |
- (c.e & _eblock << 45ULL) >> 15ULL |
- (c.e & _eblock << 50ULL) >> 25ULL;
-
- ret.c = c.c & ~_cmask_l;
- ret.c |=
- (c.c & _cblock << 6ULL) << 18ULL |
- (c.c & _cblock << 12ULL) << 30ULL |
- (c.c & _cblock << 24ULL) >> 12ULL |
- (c.c & _cblock << 42ULL) >> 36ULL;
-
- ret.c = coapply(ret.c, _comask_l);
-
- return ret;
- case L2:
- ret.e = c.e & ~_emask_l;
- ret.e |=
- (c.e & (_eblock << 25ULL | _eblock << 45ULL)) << 5ULL |
- (c.e & (_eblock << 30ULL | _eblock << 50ULL)) >> 5ULL;
-
- ret.c = c.c & ~_cmask_l;
- ret.c |=
- (c.c & _cblock << 6ULL) << 6ULL |
- (c.c & _cblock << 12ULL) >> 6ULL |
- (c.c & _cblock << 24ULL) << 18ULL |
- (c.c & _cblock << 42ULL) >> 18ULL;
-
- return ret;
- case L3:
- ret.e = c.e & ~_emask_l;
- ret.e |=
- (c.e & _eblock << 25ULL) << 25ULL |
- (c.e & _eblock << 30ULL) << 15ULL |
- (c.e & _eblock2 << 45ULL) >> 20ULL;
-
- ret.c = c.c & ~_cmask_l;
- ret.c |=
- (c.c & _cblock << 6ULL) << 36ULL |
- (c.c & _cblock << 12ULL) << 12ULL |
- (c.c & _cblock << 24ULL) >> 18ULL |
- (c.c & _cblock << 42ULL) >> 30ULL;
-
- ret.c = coapply(ret.c, _comask_l);
-
- return ret;
- case F:
- ret.e = c.e & ~_emask_f;
- ret.e |=
- (c.e & _eblock) << 40ULL |
- (c.e & _eblock << 15ULL) << 30ULL |
- (c.e & _eblock << 40ULL) >> 25ULL |
- (c.e & _eblock << 45ULL) >> 45ULL;
-
- ret.e ^= _eomask_f;
-
- ret.c = c.c & ~_cmask_f;
- ret.c |=
- (c.c & _cblock) << 36ULL |
- (c.c & (_cblock << 24ULL | _cblock << 36ULL)) >> 24ULL |
- (c.c & _cblock << 12ULL) << 12ULL;
-
- ret.c = coapply(ret.c, _comask_f);
-
- return ret;
- case F2:
- ret.e = c.e & ~_emask_f;
- ret.e |=
- (c.e & _eblock) << 15ULL |
- (c.e & _eblock << 15ULL) >> 15ULL |
- (c.e & _eblock << 40ULL) << 5ULL |
- (c.e & _eblock << 45ULL) >> 5ULL;
-
- ret.c = c.c & ~_cmask_f;
- ret.c |=
- (c.c & (_cblock | _cblock << 24ULL)) << 12ULL |
- (c.c & (_cblock << 12ULL | _cblock << 36ULL)) >> 12ULL;
-
- return ret;
- case F3:
- ret.e = c.e & ~_emask_f;
- ret.e |=
- (c.e & _eblock) << 45ULL |
- (c.e & _eblock << 15ULL) << 25ULL |
- (c.e & _eblock << 40ULL) >> 40ULL |
- (c.e & _eblock << 45ULL) >> 30ULL;
-
- ret.e ^= _eomask_f;
-
- ret.c = c.c & ~_cmask_f;
- ret.c |=
- (c.c & (_cblock | _cblock << 12ULL)) << 24ULL |
- (c.c & _cblock << 24ULL) >> 12ULL |
- (c.c & _cblock << 36ULL) >> 36ULL;
-
- ret.c = coapply(ret.c, _comask_f);
-
- return ret;
- case B:
- ret.e = c.e & ~_emask_b;
- ret.e |=
- (c.e & _eblock2 << 5ULL) << 45ULL |
- (c.e & _eblock << 50ULL) >> 40ULL |
- (c.e & _eblock << 55ULL) >> 50ULL;
-
- ret.e ^= _eomask_b;
-
- ret.c = c.c & ~_cmask_b;
- ret.c |=
- (c.c & _cblock << 6ULL) << 36ULL |
- (c.c & _cblock << 18ULL) << 12ULL |
- (c.c & (_cblock << 30ULL | _cblock << 42ULL)) >> 24ULL;
-
- ret.c = coapply(ret.c, _comask_b);
-
- return ret;
- case B2:
- ret.e = c.e & ~_emask_b;
- ret.e |=
- (c.e & (_eblock << 5ULL | _eblock << 50ULL)) << 5ULL |
- (c.e & (_eblock << 10ULL | _eblock << 55ULL)) >> 5ULL;
-
- ret.c = c.c & ~_cmask_b;
- ret.c |=
- (c.c & (_cblock << 6ULL | _cblock << 30ULL)) << 12ULL |
- (c.c & (_cblock << 18ULL | _cblock << 42ULL)) >> 12ULL;
-
- return ret;
- case B3:
- ret.e = c.e & ~_emask_b;
- ret.e |=
- (c.e & _eblock << 5ULL) << 50ULL |
- (c.e & _eblock << 10ULL) << 40ULL |
- (c.e & _eblock2 << 50ULL) >> 45ULL;
-
- ret.e ^= _eomask_b;
-
- ret.c = c.c & ~_cmask_b;
- ret.c |=
- (c.c & (_cblock << 6ULL | _cblock << 18ULL)) << 24ULL |
- (c.c & _cblock << 30ULL) >> 12ULL |
- (c.c & _cblock << 42ULL) >> 36ULL;
-
- ret.c = coapply(ret.c, _comask_b);
-
- return ret;
- default:
- goto move_unknown;
- }
-
-move_unknown:
-#ifdef DEBUG
- fprintf(stderr, "move error, unknow move\n");
-#endif
- goto move_error;
-move_error:
- return errorcube;
-}
diff --git a/old/manualsimd/cube.h b/old/manualsimd/cube.h
@@ -1,27 +0,0 @@
-typedef enum {
- U, U2, U3, D, D2, D3,
- R, R2, R3, L, L2, L3,
- F, F2, F3, B, B2, B3
-} move_t;
-typedef struct {
- uint64_t e;
- uint64_t c;
-} cube_t;
-
-extern cube_t solvedcube;
-extern cube_t errorcube;
-
-bool isconsistent(cube_t);
-bool issolved(cube_t);
-
-cube_t readcube(char *);
-void writecube(cube_t, char *);
-
-int readmoves(char *, move_t *);
-void writemoves(move_t *, int, char *);
-
-cube_t move(cube_t, move_t);
-
-/*
-cube_t inverse(cube_t);
-*/
diff --git a/src/solve_generic.h b/src/solve_generic.h
@@ -235,12 +235,18 @@ int64_t
gendata(const char *solver, const char *options, void *data)
{
int64_t ret;
- uint8_t maxdepth;
+ uint8_t maxdepth, h, i, j;
if (!strcmp(solver, "H48")) {
- /* TODO: write a generic parser for options */
- maxdepth = atoi(options);
- ret = gendata_h48(data, 0, maxdepth);
+ /*
+ TODO: write a generic parser for options
+ for now it accepts "h;maxdepth"
+ */
+ for (i = 0; options[i] != ';'; i++) ;
+ for (j = i; options[j]; j++) ;
+ h = atoi(options);
+ maxdepth = atoi(&options[i+1]);
+ ret = gendata_h48(data, h, maxdepth);
} else {
DBG_LOG("gendata: implemented only for H48 solver\n");
ret = -1;
diff --git a/old/cube_h_with_format_documentation b/utils/cube_h_with_format_documentation