From 8bacac732dcb2c0118e47e1bb81be855f4a0bf58 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 20 May 2024 17:39:07 +0200 Subject: Tests for gendata h48 --- src/cube_avx2.h | 10 ++++++---- src/solve_h48.h | 43 ++++++++++++++++++++++++------------------- 2 files changed, 30 insertions(+), 23 deletions(-) (limited to 'src') diff --git a/src/cube_avx2.h b/src/cube_avx2.h index d39da94..934737c 100644 --- 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 index b95e6ce..be2c328 100644 --- 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 -- cgit v1.3