commit 8bacac732dcb2c0118e47e1bb81be855f4a0bf58
parent 4dde2625a1bcb5381b50b22e7212070266cd224f
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date: Mon, 20 May 2024 17:39:07 +0200
Tests for gendata h48
Diffstat:
8 files changed, 80 insertions(+), 31 deletions(-)
diff --git a/configure.sh b/configure.sh
@@ -18,7 +18,7 @@ WFLAGS="-pedantic -Wall -Wextra -Wno-unused-parameter -Wno-unused-function"
SAN="$ADDR $UNDEF"
CFLAGS="$STD $WFLAGS $AVX -O3"
-DBGFLAGS="$STD $WFLAGS $AVX -g3 -DDEBUG"
+DBGFLAGS="$STD $WFLAGS $SAN $AVX -g3 -DDEBUG"
echo "Cube type: CUBE_$TYPE"
echo "Compiler: ${CC:-cc}"
diff --git a/src/cube_avx2.h b/src/cube_avx2.h
@@ -207,7 +207,7 @@ _static_inline int64_t
coord_fast_esep(cube_fast_t c)
{
cube_fast_t ep;
- int64_t e, mem[4], i, j, k, l, ret1, ret2, bit1, bit2, is1;
+ int64_t e, mem[4], i, j, jj, k, l, ret1, ret2, bit1, bit2, is1;
ep = _mm256_and_si256(c, _ep_avx2);
_mm256_storeu_si256((__m256i *)mem, ep);
@@ -225,7 +225,8 @@ coord_fast_esep(cube_fast_t c)
ret1 += bit2 * binomial[11-i][k];
k -= bit2;
- ret2 += is1 * binomial[7-j][l];
+ jj = j < 8;
+ ret2 += jj * is1 * binomial[7-(j*jj)][l];
l -= is1;
j += (1-bit2);
}
@@ -274,7 +275,7 @@ _static_inline cube_fast_t
invcoord_fast_esep(int64_t esep)
{
cube_fast_t eee, ret;
- int64_t i, j, k, l, s, v, w, is1, set1, set2;
+ int64_t i, j, jj, k, l, s, v, w, is1, set1, set2;
uint8_t bit2, bit1, mem[32];
uint8_t slice[3] = {0};
@@ -283,7 +284,8 @@ invcoord_fast_esep(int64_t esep)
for (i = 0, j = 0, k = 4, l = 4; i < 12; i++) {
v = binomial[11-i][k];
- w = binomial[7-j][l];
+ jj = j < 8;
+ w = jj * binomial[7-(j*jj)][l];
bit2 = set2 >= v;
bit1 = set1 >= w;
is1 = (1 - bit2) * bit1;
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -1,12 +1,10 @@
#define COCSEP_CLASSES 3393U
#define COCSEP_TABLESIZE (_3p7 << 7U)
#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + 7U) / 8U)
-#define COCSEP_INFOSIZE 12U
-#define COCSEP_FULLSIZE (4 * (COCSEP_TABLESIZE + COCSEP_INFOSIZE))
+#define COCSEP_FULLSIZE (4*(COCSEP_TABLESIZE + 12))
#define ESEP_MAX(h) ((COCSEP_CLASSES * _12c4 * _8c4) << (h))
-#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) >> (k))
-#define ESEP_INFOSIZE 25 /* TODO unknown yet */
+#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / (8U / (k)))
#define H48_ESIZE(h) ((_12c4 * _8c4) << (h))
@@ -41,7 +39,7 @@ _static_inline cube_fast_t invcoord_h48(int64_t, const cube_fast_t *, uint8_t);
_static size_t gendata_cocsep(void *, uint64_t *, cube_fast_t *);
_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
-_static size_t gendata_h48(void *, uint8_t);
+_static size_t gendata_h48(void *, uint8_t, uint8_t);
_static uint64_t gendata_esep_bfs(bfsarg_esep_t *);
_static_inline bool get_visited(const uint8_t *, int64_t);
@@ -120,7 +118,6 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep)
buf32 = (uint32_t *)buf;
info = buf32 + COCSEP_TABLESIZE;
memset(buf32, 0xFFU, sizeof(uint32_t) * COCSEP_TABLESIZE);
- memset(info, 0, sizeof(uint32_t) * COCSEP_INFOSIZE);
memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
arg = (dfsarg_cocsep_t) {
@@ -163,7 +160,6 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
uint8_t m, t, tinv, olddepth;
uint32_t cc;
int64_t i, ii;
- uint64_t sim;
cube_fast_t d;
dfsarg_cocsep_t nextarg;
@@ -208,10 +204,10 @@ TODO description
generating fixed table with h=0, k=4
*/
_static size_t
-gendata_h48(void *buf, uint8_t h)
+gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
{
- const int k = 1; /* TODO: other cases? */
- uint32_t *buf32, *info, *cocsepdata;
+ const int k = 4; /* TODO: other cases? */
+ uint32_t j, *buf32, *info, *cocsepdata;
bfsarg_esep_t arg;
int64_t sc, cc, tot;
uint64_t selfsim[COCSEP_CLASSES];
@@ -219,17 +215,14 @@ gendata_h48(void *buf, uint8_t h)
size_t cocsepsize;
cocsepsize = gendata_cocsep(buf, selfsim, crep);
- DBG_ASSERT(cocsepsize == COCSEP_FULLSIZE, 0,
- "gendata_h48: error computing cocsep data\n");
-
cocsepdata = (uint32_t *)buf;
- buf32 = cocsepdata + cocsepsize;
- info = buf32 + ESEP_TABLESIZE(h, k);
- memset(buf32, 0xFFU, sizeof(uint32_t) * ESEP_TABLESIZE(h, k));
- memset(info, 0, sizeof(uint32_t) * ESEP_INFOSIZE);
+ buf32 = cocsepdata + cocsepsize/4;
+ info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t));
+ memset(buf32, 0xFFU, ESEP_TABLESIZE(h, k));
sc = coord_h48(cubetofast(solved), cocsepdata, h);
set_esep_pval(buf32, sc, 0);
+ info[1] = 1;
arg = (bfsarg_esep_t) {
.h = h,
.cocsepdata = cocsepdata,
@@ -237,7 +230,11 @@ gendata_h48(void *buf, uint8_t h)
.crep = crep,
.selfsim = selfsim
};
- for (tot = 1, arg.depth = 1, cc = 0; tot < ESEP_MAX(h); arg.depth++) {
+ for (
+ tot = 1, arg.depth = 1, cc = 0;
+ tot < ESEP_MAX(h) && arg.depth <= maxdepth;
+ arg.depth++
+ ) {
DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
cc = gendata_esep_bfs(&arg);
tot += cc;
@@ -245,7 +242,15 @@ gendata_h48(void *buf, uint8_t h)
DBG_LOG("found %" PRIu64 "\n", cc);
}
- return COCSEP_FULLSIZE + cc;
+ info[0] = arg.depth-1;
+
+ DBG_LOG("h48 pruning table computed\n");
+ DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[0]);
+ DBG_LOG("Pruning value distribution:\n");
+ for (j = 0; j <= info[0]; j++)
+ DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]);
+
+ return COCSEP_FULLSIZE + ESEP_TABLESIZE(h, k) + 4*(info[0]+2);
}
_static uint64_t
diff --git a/test/102_gendata_h48/00_all.in b/test/102_gendata_h48/00_all.in
diff --git a/test/102_gendata_h48/00_all.out b/test/102_gendata_h48/00_all.out
@@ -1 +0,0 @@
-something
diff --git a/test/102_gendata_h48/00_h_0.in b/test/102_gendata_h48/00_h_0.in
@@ -0,0 +1 @@
+0
diff --git a/test/102_gendata_h48/00_h_0.out b/test/102_gendata_h48/00_h_0.out
@@ -0,0 +1,23 @@
+59903545
+
+cocsepdata:
+Classes: 3393
+Max value: 9
+0: 1
+1: 6
+2: 63
+3: 468
+4: 3068
+5: 15438
+6: 53814
+7: 71352
+8: 8784
+9: 96
+
+h48:
+0: 1
+1: 1
+2: 4
+3: 34
+4: 331
+5: 3608
diff --git a/test/102_gendata_h48/gendata_h48_tests.c b/test/102_gendata_h48/gendata_h48_tests.c
@@ -1,18 +1,37 @@
#include "../test.h"
-#define H 0
-#define SIZE (120000000 << (H))
+#define MAXH 1
+#define MAXDEPTH 5
+#define COCSEPSIZE 1119792
+#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (h))
+#define SIZE (60000000 << MAXH)
-uint32_t buf[SIZE];
+uint32_t buf[SIZE/4];
-size_t gendata_h48(void *, uint8_t);
+size_t gendata_h48(void *, uint8_t, uint8_t);
int main(void) {
+ char str[STRLENMAX];
+ uint8_t h, i;
+ uint32_t *h48info;
size_t result;
- result = gendata_h48(buf, H);
+ fgets(str, STRLENMAX, stdin);
+ h = atoi(str);
+ result = gendata_h48(buf, h, MAXDEPTH);
+ h48info = buf + (ETABLESIZE(h) + COCSEPSIZE) / 4;
- printf("nothing\n");
+ printf("%zu\n\n", result);
+
+ printf("cocsepdata:\n");
+ printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]);
+ printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]);
+ for (i = 0; i < 10; i++)
+ printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]);
+
+ printf("\nh48:\n");
+ for (i = 0; i < MAXDEPTH+1; i++)
+ printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]);
return 0;
}
