commit 1809d7b212128fcdcb481002a17db5dc97a15e03 parent d26d9e46d305b3ab3c6ae3b55f1859cf413a1c94 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri, 17 May 2024 17:42:43 +0200 Added inverse eo and copy_{edges,corners} Diffstat:
26 files changed, 252 insertions(+), 20 deletions(-)
diff --git a/TODO.txt b/TODO.txt @@ -1,7 +1,7 @@ In progress: go back to nissy-style BFS for eosep data computation - (done) compute selfsim and cocsep representatives - - implement set_eo_fast for invcoord_h48 (with tests for set_eo_fast) - also: implement other set_stuff methods for fast cube representation + - (done) implement set_eo_fast for invcoord_h48 + - add unit tests for invcoord_h48 (compute tables, if needed) - in gendata_esep, compute representatives for esep inverse coordinate - change to BFS diff --git a/src/cube.c b/src/cube.c @@ -1,5 +1,6 @@ #include <inttypes.h> #include <stdbool.h> +#include <stdlib.h> /* TODO: Used only for malloc, remove if possible */ #include <string.h> #ifdef DEBUG diff --git a/src/cube_avx2.h b/src/cube_avx2.h @@ -23,9 +23,12 @@ _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_cocsep(cube_fast_t); _static_inline int64_t coord_fast_eo(cube_fast_t); -_static_inline void set_eo_fast(cube_fast_t *, int64_t); _static_inline int64_t coord_fast_esep(cube_fast_t); +_static_inline void copy_corners_fast(cube_fast_t *, cube_fast_t); +_static_inline void copy_edges_fast(cube_fast_t *, cube_fast_t); +_static_inline void set_eo_fast(cube_fast_t *, int64_t); + _static_inline cube_fast_t fastcube( uint8_t c_ufr, @@ -199,12 +202,6 @@ coord_fast_eo(cube_fast_t c) return mask >> 17; } -_static_inline void -set_eo_fast(cube_fast_t *c, int64_t eo) -{ - /* TODO */ -} - _static_inline int64_t coord_fast_esep(cube_fast_t c) { @@ -234,3 +231,40 @@ coord_fast_esep(cube_fast_t c) return ret1 * 70 + ret2; } + +_static_inline void +copy_corners_fast(cube_fast_t *dest, cube_fast_t src) +{ + *dest = _mm256_blend_epi32(*dest, src, 0x0F); +} + +_static_inline void +copy_edges_fast(cube_fast_t *dest, cube_fast_t src) +{ + *dest = _mm256_blend_epi32(*dest, src, 0xF0); +} + +_static_inline void +set_eo_fast(cube_fast_t *cube, int64_t eo) +{ + int64_t eo12, eotop, eobot; + __m256i veo; + + eo12 = (eo << 1) + (_mm_popcnt_u64(eo) % 2); + eotop = (eo12 & (1 << 11)) << 17 | + (eo12 & (1 << 10)) << 10 | + (eo12 & (1 << 9)) << 3 | + (eo12 & (1 << 8)) >> 4; + eobot = (eo12 & (1 << 7)) << 53 | + (eo12 & (1 << 6)) << 46 | + (eo12 & (1 << 5)) << 39 | + (eo12 & (1 << 4)) << 32 | + (eo12 & (1 << 3)) << 25 | + (eo12 & (1 << 2)) << 18 | + (eo12 & (1 << 1)) << 11 | + (eo12 & 1) << 4; + veo = _mm256_set_epi64x(eotop, eobot, 0, 0); + + *cube = _mm256_andnot_si256(_eo_avx2, *cube); + *cube = _mm256_or_si256(*cube, veo); +} diff --git a/src/cube_portable.h b/src/cube_portable.h @@ -17,9 +17,12 @@ _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_cocsep(cube_fast_t); _static_inline int64_t coord_fast_eo(cube_fast_t); -_static_inline void set_eo_fast(cube_fast_t *, int64_t eo); _static_inline int64_t coord_fast_esep(cube_fast_t); +_static_inline void copy_corners_fast(cube_fast_t *, cube_fast_t); +_static_inline void copy_edges_fast(cube_fast_t *, cube_fast_t); +_static_inline void set_eo_fast(cube_fast_t *, int64_t); + _static_inline cube_fast_t fastcube( uint8_t c_ufr, @@ -189,12 +192,6 @@ coord_fast_eo(cube_fast_t c) return ret; } -_static_inline void -_set_eo_fast(cube_fast_t *cube, int64_t eo) -{ - /* TODO */ -} - /* We encode the edge separation as a number from 0 to C(12,4)*C(8,4). It can be seen as the composition of two "subset index" coordinates. @@ -229,3 +226,28 @@ coord_fast_esep(cube_fast_t c) return ret1 * 70 + ret2; } + +_static_inline void +copy_corners_fast(cube_fast_t *dest, cube_fast_t src) +{ + memcpy(&dest->corner, src.corner, sizeof(src.corner)); +} + +_static_inline void +copy_edges_fast(cube_fast_t *dest, cube_fast_t src) +{ + memcpy(&dest->edge, src.edge, sizeof(src.edge)); +} + +_static_inline void +set_eo_fast(cube_fast_t *cube, int64_t eo) +{ + int i, sum, flip; + + for (sum = 0, i = 1; i < 12; i++, eo >>= 1) { + flip = eo % 2; + sum += flip; + cube->edge[i] = (cube->edge[i] & ~_eobit) | (_eobit * flip); + } + cube->edge[0] = (cube->edge[0] & ~_eobit) | (_eobit * (sum%2)); +} diff --git a/src/solve_h48.h b/src/solve_h48.h @@ -88,16 +88,17 @@ invcoord_h48( cube_fast_t ret; int64_t coclass, ee, esep, eo; + DBG_ASSERT(h <= 11, cubetofast(zero), + "invcoord_h48: h must be between 0 and 11\n"); + coclass = i / H48_ESIZE; ee = i % H48_ESIZE; esep = ee >> h; eo = (ee & ((1<<h)-1)) << (11-h); -/* TODO: implement set_stuff methods - ret.c = crep[coclass]; - ret.e = erep[esep]; + copy_corners_fast(&ret, crep[coclass]); + copy_edges_fast(&ret, erep[esep]); set_eo_fast(&ret, eo); -*/ return ret; } diff --git a/test/075_set_eo/00_solved_0.in b/test/075_set_eo/00_solved_0.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +0 diff --git a/test/075_set_eo/00_solved_0.out b/test/075_set_eo/00_solved_0.out @@ -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/075_set_eo/01_solved_1.in b/test/075_set_eo/01_solved_1.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +2047 diff --git a/test/075_set_eo/01_solved_1.out b/test/075_set_eo/01_solved_1.out @@ -0,0 +1 @@ +UF1 UB1 DB1 DF1 UR1 UL1 DL1 DR1 FR1 FL1 BL1 BR1 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/075_set_eo/02_solved_other.in b/test/075_set_eo/02_solved_other.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +20 diff --git a/test/075_set_eo/02_solved_other.out b/test/075_set_eo/02_solved_other.out @@ -0,0 +1 @@ +UF0 UB0 DB0 DF1 UR0 UL1 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/075_set_eo/03_solved_firstlast.in b/test/075_set_eo/03_solved_firstlast.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +1024 diff --git a/test/075_set_eo/03_solved_firstlast.out b/test/075_set_eo/03_solved_firstlast.out @@ -0,0 +1 @@ +UF1 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR1 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/075_set_eo/10_scrambled_0.in b/test/075_set_eo/10_scrambled_0.in @@ -0,0 +1,4 @@ +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 +0 + +// 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/075_set_eo/10_scrambled_0.out b/test/075_set_eo/10_scrambled_0.out @@ -0,0 +1 @@ +UL0 BL0 BR0 DL0 FR0 DF0 DB0 DR0 UB0 FL0 UF0 UR0 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 diff --git a/test/075_set_eo/11_scrambled_1.in b/test/075_set_eo/11_scrambled_1.in @@ -0,0 +1,4 @@ +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 +2047 + +// 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/075_set_eo/11_scrambled_1.out b/test/075_set_eo/11_scrambled_1.out @@ -0,0 +1 @@ +UL1 BL1 BR1 DL1 FR1 DF1 DB1 DR1 UB1 FL1 UF1 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 diff --git a/test/075_set_eo/set_eo_tests.c b/test/075_set_eo/set_eo_tests.c @@ -0,0 +1,38 @@ +#include "../test.h" + +int64_t coord_fast_eo(cube_fast_t); +void set_eo_fast(cube_fast_t *, int64_t); +cube_fast_t cubetofast(cube_t); +cube_t fasttocube(cube_fast_t); + +int main(void) { + char str[STRLENMAX]; + cube_t cube; + cube_fast_t fast; + int64_t eo; + + fgets(str, STRLENMAX, stdin); + cube = readcube("H48", str); + fast = cubetofast(cube); + fgets(str, STRLENMAX, stdin); + eo = atoi(str); + + set_eo_fast(&fast, eo); + + cube = fasttocube(fast); + if (iserror(cube)) { + printf("Error setting EO\n"); + } else if (!isconsistent(cube)) { + fprintf(stderr, "edges: "); + for (int i = 0; i < 12; i++) fprintf(stderr, "%d ", cube.edge[i]); + fprintf(stderr, "\n"); + for (int i = 0; i < 8; i++) fprintf(stderr, "%d ", cube.corner[i]); + fprintf(stderr, "\n"); + printf("Setting EO resulted in inconsistent cube\n"); + } else { + writecube("H48", cube, str); + printf("%s\n", str); + } + + return 0; +} diff --git a/test/076_copy_corners/00_solved_scrambled.in b/test/076_copy_corners/00_solved_scrambled.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 diff --git a/test/076_copy_corners/00_solved_scrambled.out b/test/076_copy_corners/00_solved_scrambled.out @@ -0,0 +1 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 diff --git a/test/076_copy_corners/copy_corners_tests.c b/test/076_copy_corners/copy_corners_tests.c @@ -0,0 +1,33 @@ +#include "../test.h" + +void copy_corners_fast(cube_fast_t *, cube_fast_t); +cube_fast_t cubetofast(cube_t); +cube_t fasttocube(cube_fast_t); + +int main(void) { + char str[STRLENMAX]; + cube_t c1, c2; + cube_fast_t f1, f2; + + fgets(str, STRLENMAX, stdin); + c1 = readcube("H48", str); + f1 = cubetofast(c1); + + fgets(str, STRLENMAX, stdin); + c2 = readcube("H48", str); + f2 = cubetofast(c2); + + copy_corners_fast(&f1, f2); + + c1 = fasttocube(f1); + if (iserror(c1)) { + printf("Error setting EO\n"); + } else if (!isconsistent(c1)) { + printf("Setting EO resulted in inconsistent cube\n"); + } else { + writecube("H48", c1, str); + printf("%s\n", str); + } + + return 0; +} diff --git a/test/077_copy_edges/00_solved_scrambled.in b/test/077_copy_edges/00_solved_scrambled.in @@ -0,0 +1,2 @@ +UF0 UB0 DB0 DF0 UR0 UL0 DL0 DR0 FR0 FL0 BL0 BR0 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 DFL0 UFR1 DBR1 UBR2 DBL2 DFR0 UFL1 UBL2 diff --git a/test/077_copy_edges/00_solved_scrambled.out b/test/077_copy_edges/00_solved_scrambled.out @@ -0,0 +1 @@ +UL0 BL0 BR1 DL0 FR0 DF0 DB1 DR1 UB0 FL0 UF0 UR1 UFR0 UBL0 DFL0 DBR0 UFL0 UBR0 DFR0 DBL0 diff --git a/test/077_copy_edges/copy_edges_tests.c b/test/077_copy_edges/copy_edges_tests.c @@ -0,0 +1,33 @@ +#include "../test.h" + +void copy_edges_fast(cube_fast_t *, cube_fast_t); +cube_fast_t cubetofast(cube_t); +cube_t fasttocube(cube_fast_t); + +int main(void) { + char str[STRLENMAX]; + cube_t c1, c2; + cube_fast_t f1, f2; + + fgets(str, STRLENMAX, stdin); + c1 = readcube("H48", str); + f1 = cubetofast(c1); + + fgets(str, STRLENMAX, stdin); + c2 = readcube("H48", str); + f2 = cubetofast(c2); + + copy_edges_fast(&f1, f2); + + c1 = fasttocube(f1); + if (iserror(c1)) { + printf("Error setting EO\n"); + } else if (!isconsistent(c1)) { + printf("Setting EO resulted in inconsistent cube\n"); + } else { + writecube("H48", c1, str); + printf("%s\n", str); + } + + return 0; +} diff --git a/test/test b/test/test @@ -0,0 +1,41 @@ +#!/bin/sh + +detectsan() { cc -fsanitize=$1 -dM -E -x c - </dev/null | grep "SANITIZE"; } + +re="${TEST:-$@}" + +CC="cc -DDEBUG -std=c99 -pedantic -Wall -Wextra \ + -Wno-unused-parameter -Wno-unused-function -g3 -D$CUBETYPE" + +[ "$CUBETYPE" = "CUBE_AVX2" ] && CC="$CC -mavx2" +[ -n "$(detectsan address)" ] && CC="$CC -fsanitize=address" +[ -n "$(detectsan undefined)" ] && CC="$CC -fsanitize=undefined" + +TESTBIN="test/run" +TESTOUT="test/last.out" +TESTERR="test/last.err" +CUBEOBJ="debugcube.o" + +for t in test/*; do + if [ -n "$re" ] && [ -z "$(echo "$t" | grep "$re")" ]; then + continue + fi + if [ ! -d $t ]; then continue; fi + $CC -o $TESTBIN $t/*.c $CUBEOBJ || exit 1; + for cin in $t/*.in; do + c=$(echo "$cin" | sed 's/\.in//') + cout=$c.out + printf "$c: " + $TESTBIN < "$cin" > $TESTOUT 2> $TESTERR + if diff $cout $TESTOUT; then + printf "OK\n" + else + printf "Test failed! stderr:\n" + cat $TESTERR + exit 1 + fi + done +done + +echo "All tests passed!" +rm -rf $TESTBIN $TESTOUT $TESTERR $CUBEOBJ diff --git a/test/test.h b/test/test.h @@ -21,6 +21,7 @@ typedef cube_t cube_fast_t; /* Basic functions used in most tests */ cube_t solvedcube(void); bool iserror(cube_t); +bool isconsistent(cube_t); bool issolvable(cube_t); bool issolved(cube_t); cube_t readcube(char *, char *);