commit 9b0be93fb5fe23ae9f1a7a57b9db60561d8673e8
parent 0083a7eb4677542aced3ea2fa335bc9cf1f7b419
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Fri, 29 Mar 2024 09:28:59 +0100
Added coordinate cpsep
Diffstat:
21 files changed, 77 insertions(+), 4 deletions(-)
diff --git a/TODO.txt b/TODO.txt
@@ -1,9 +1,9 @@
## (find better name) H48 solver, ideas
-TODO next: implement cosep coordinate
+TODO next: epsep, precise coordinate unlike cpsep which is redundant
-First compute co + csep. Use csep as a binary number (2^8 instead of 70,
-loose a factor of 3.66 but still fits in a few megabytes or less). Use
+First compute co + csep. Use csep as a binary number (2^7 instead of 70,
+loose a factor of 1.8 but still fits in a few megabytes or less). Use
co + csep as an index in a table whose entries have: 6 bits for ttrep,
12 bits for rep, 4 bits for pruning. Optionally, 4 more bits could be
used for the base of the pruning table, if we want to have a different
diff --git a/cube.c b/cube.c
@@ -5,6 +5,7 @@
#include "cube.h"
#ifdef DEBUG
+
#include <stdio.h>
#define _static
#define _static_inline
@@ -15,12 +16,15 @@
DBG_LOG(__VA_ARGS__); \
return retval; \
}
+
#else
+
#define _static static
#define _static_inline static inline
#define DBG_LOG(...)
#define DBG_WARN(condition, ...)
#define DBG_ASSERT(condition, retval, ...)
+
#endif
/******************************************************************************
@@ -495,6 +499,7 @@ typedef __m256i cube_fast_t;
#define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060)
#define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020)
+#define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707)
#define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0)
_static_inline cube_fast_t fastcube(
@@ -511,6 +516,7 @@ _static_inline cube_fast_t invertco_fast(cube_fast_t);
_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
_static_inline int64_t coord_fast_co(cube_fast_t);
+_static_inline int64_t coord_fast_csep(cube_fast_t);
_static_inline int64_t coord_fast_eo(cube_fast_t);
_static_inline cube_fast_t
@@ -641,7 +647,7 @@ compose_fast(cube_fast_t c1, cube_fast_t c2)
_static_inline int64_t
coord_fast_co(cube_fast_t c)
{
- cube_fast_t co, shifted;
+ cube_fast_t co;
int64_t mem[4], ret, i, p;
co = _mm256_and_si256(c, _co2_avx2);
@@ -655,6 +661,19 @@ coord_fast_co(cube_fast_t c)
}
_static_inline int64_t
+coord_fast_csep(cube_fast_t c)
+{
+ cube_fast_t cp, shifted;
+ int64_t mask;
+
+ cp = _mm256_and_si256(c, _cp_avx2);
+ shifted = _mm256_slli_epi32(cp, 5);
+ mask = _mm256_movemask_epi8(shifted);
+
+ return mask & 0x7F;
+}
+
+_static_inline int64_t
coord_fast_eo(cube_fast_t c)
{
cube_fast_t eo, shifted;
@@ -709,6 +728,7 @@ _static_inline cube_fast_t invertco_fast(cube_fast_t);
_static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t);
_static_inline int64_t coord_fast_co(cube_fast_t);
+_static_inline int64_t coord_fast_csep(cube_fast_t);
_static_inline int64_t coord_fast_eo(cube_fast_t);
_static_inline cube_fast_t
@@ -844,6 +864,18 @@ coord_fast_co(cube_fast_t c)
}
_static_inline int64_t
+coord_fast_csep(cube_fast_t c)
+{
+ int i, p;
+ int64_t ret;
+
+ for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2)
+ ret += p * ((c.corner[i] & _pbits) >> 2U);
+
+ return ret;
+}
+
+_static_inline int64_t
coord_fast_eo(cube_fast_t c)
{
int i, p;
diff --git a/test/073_coord_csep/00_solved.in b/test/073_coord_csep/00_solved.in
@@ -0,0 +1 @@
+UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0
diff --git a/test/073_coord_csep/00_solved.out b/test/073_coord_csep/00_solved.out
@@ -0,0 +1 @@
+112
diff --git a/test/073_coord_csep/01_U.in b/test/073_coord_csep/01_U.in
@@ -0,0 +1 @@
+UR0 UL0 DB0 DF0 UB0 UF0 DL0 DR0 FR0 FL0 BL0 BR0 UBR0 UFL0 DFL0 DBR0 UFR0 UBL0 DFR0 DBL0
diff --git a/test/073_coord_csep/01_U.out b/test/073_coord_csep/01_U.out
@@ -0,0 +1 @@
+67
diff --git a/test/073_coord_csep/02_U2.in b/test/073_coord_csep/02_U2.in
@@ -0,0 +1 @@
+UB0 UF0 DB0 DF0 UL0 UR0 DL0 DR0 FR0 FL0 BL0 BR0 UBL0 UFR0 DFL0 DBR0 UBR0 UFL0 DFR0 DBL0
diff --git a/test/073_coord_csep/02_U2.out b/test/073_coord_csep/02_U2.out
@@ -0,0 +1 @@
+112
diff --git a/test/073_coord_csep/03_U3.in b/test/073_coord_csep/03_U3.in
@@ -0,0 +1 @@
+UL0 UR0 DB0 DF0 UF0 UB0 DL0 DR0 FR0 FL0 BL0 BR0 UFL0 UBR0 DFL0 DBR0 UBL0 UFR0 DFR0 DBL0
diff --git a/test/073_coord_csep/03_U3.out b/test/073_coord_csep/03_U3.out
@@ -0,0 +1 @@
+67
diff --git a/test/073_coord_csep/04_D.in b/test/073_coord_csep/04_D.in
@@ -0,0 +1 @@
+UF0 UB0 DR0 DL0 UR0 UL0 DB0 DF0 FR0 FL0 BL0 BR0 UFR0 UBL0 DBL0 DFR0 UFL0 UBR0 DFL0 DBR0
diff --git a/test/073_coord_csep/04_D.out b/test/073_coord_csep/04_D.out
@@ -0,0 +1 @@
+60
diff --git a/test/073_coord_csep/07_R.in b/test/073_coord_csep/07_R.in
@@ -0,0 +1 @@
+UF0 UB0 DB0 DF0 FR0 UL0 DL0 BR0 DR0 FL0 BL0 UR0 DFR2 UBL0 DFL0 UBR2 UFL0 UFR1 DBR1 DBL0
diff --git a/test/073_coord_csep/07_R.out b/test/073_coord_csep/07_R.out
@@ -0,0 +1 @@
+25
diff --git a/test/073_coord_csep/08_R2.in b/test/073_coord_csep/08_R2.in
@@ -0,0 +1 @@
+UF0 UB0 DB0 DF0 DR0 UL0 DL0 UR0 BR0 FL0 BL0 FR0 DBR0 UBL0 DFL0 UFR0 UFL0 DFR0 UBR0 DBL0
diff --git a/test/073_coord_csep/08_R2.out b/test/073_coord_csep/08_R2.out
@@ -0,0 +1 @@
+112
diff --git a/test/073_coord_csep/13_F.in b/test/073_coord_csep/13_F.in
@@ -0,0 +1 @@
+FL1 UB0 DB0 FR1 UR0 UL0 DL0 DR0 UF1 DF1 BL0 BR0 UFL1 UBL0 DFR1 DBR0 DFL2 UBR0 UFR2 DBL0
diff --git a/test/073_coord_csep/13_F.out b/test/073_coord_csep/13_F.out
@@ -0,0 +1 @@
+37
diff --git a/test/073_coord_csep/20_scrambled.in b/test/073_coord_csep/20_scrambled.in
@@ -0,0 +1,3 @@
+UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2
+
+// Scramble: U R D' L D' F L2 D L F B D2 B' L2 F U2 L2 D2 R2 L2 B'
diff --git a/test/073_coord_csep/20_scrambled.out b/test/073_coord_csep/20_scrambled.out
@@ -0,0 +1 @@
+120
diff --git a/test/073_coord_csep/coord_csep_tests.c b/test/073_coord_csep/coord_csep_tests.c
@@ -0,0 +1,21 @@
+#include "../test.h"
+
+int64_t coord_fast_csep(cube_fast_t);
+cube_fast_t cubetofast(cube_t);
+
+int main(void) {
+ char str[STRLENMAX];
+ cube_t cube;
+ cube_fast_t fast;
+ int64_t result;
+
+ fgets(str, STRLENMAX, stdin);
+ cube = readcube("H48", str);
+ fast = cubetofast(cube);
+
+ result = coord_fast_csep(fast);
+
+ printf("%" PRId64 "\n", result);
+
+ return 0;
+}
