From 25c16cc4350a659ede2a2503c4c5be36264e853d Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sun, 25 Aug 2024 14:36:11 +0200 Subject: Renamed file --- src/solvers/h48/gendata_full.h | 351 ----------------------------------------- src/solvers/h48/gendata_h48.h | 351 +++++++++++++++++++++++++++++++++++++++++ src/solvers/h48/h48.h | 2 +- 3 files changed, 352 insertions(+), 352 deletions(-) delete mode 100644 src/solvers/h48/gendata_full.h create mode 100644 src/solvers/h48/gendata_h48.h diff --git a/src/solvers/h48/gendata_full.h b/src/solvers/h48/gendata_full.h deleted file mode 100644 index 2b1347f..0000000 --- a/src/solvers/h48/gendata_full.h +++ /dev/null @@ -1,351 +0,0 @@ -#define H48_COORDMAX_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) -#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (size_t)(h)) -#define H48_TABLESIZE(h, k) (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) - -#define H48_COEFF(k) (UINT32_C(32) / (uint32_t)(k)) -#define H48_INDEX(i, k) ((uint32_t)(i) / H48_COEFF(k)) -#define H48_SHIFT(i, k) ((uint32_t)(k) * ((uint32_t)(i) % H48_COEFF(k))) -#define H48_MASK(i, k) ((_bit_u32(k) - (uint32_t)(1)) << H48_SHIFT(i, k)) - -#define MAXLEN 20 - -/* -TODO: This loop over similar h48 coordinates can be improved by only -transforming edges, but we need to compose transformations (i.e. conjugate -_t by _ttrep). -*/ -#define _foreach_h48sim(_cube, _cocsepdata, _selfsim, _h, _action) \ - int64_t _cocsep = coord_cocsep(_cube); \ - uint8_t _ttrep = TTREP(_cocsepdata[_cocsep]); \ - uint8_t _inverse_ttrep = inverse_trans(_ttrep); \ - int64_t _coclass = COCLASS(_cocsepdata[_cocsep]); \ - cube_t _rep = transform(_cube, _ttrep); \ - uint64_t _sim = _selfsim[_coclass]; \ - for (uint8_t _t = 0; _t < 48 && _sim; _t++, _sim >>= 1) { \ - if (!(_sim & 1)) continue; \ - _cube = transform(_rep, _t); \ - _cube = transform(_cube, _inverse_ttrep); \ - _action \ - } - -typedef struct { - uint8_t h; - uint8_t k; - uint8_t maxdepth; - void *buf; - uint32_t *info; - uint32_t *cocsepdata; - uint32_t *h48data; - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; -} gendata_h48_arg_t; - -typedef struct { - uint8_t maxdepth; - const uint32_t *cocsepdata; - const cube_t *crep; - const uint64_t *selfsim; - h48map_t *map; -} gendata_h48short_arg_t; - -typedef struct { - uint8_t depth; - uint32_t *cocsepdata; - uint32_t *buf32; - uint64_t *selfsim; - int64_t done; - cube_t *crep; -} bfsarg_esep_t; - -_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t); -_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); - -_static uint64_t gen_h48short(gendata_h48short_arg_t *); -_static size_t gendata_h48(gendata_h48_arg_t *); -_static size_t gendata_h48h0k4(gendata_h48_arg_t *); -_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); -_static size_t gendata_h48k2(gendata_h48_arg_t *); - -_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *); - -_static uint64_t -gen_h48short(gendata_h48short_arg_t *arg) -{ - uint8_t i, m; - int64_t coord; - uint64_t j, oldn; - kvpair_t kv; - cube_t cube, d; - - cube = solvedcube(); - coord = coord_h48(cube, arg->cocsepdata, 11); - h48map_insertmin(arg->map, coord, 0); - oldn = 0; - LOG("Short h48: depth 0\nfound %" PRIu8 "\n", arg->map->n-oldn); - for (i = 0; i < arg->maxdepth; i++) { - LOG("Short h48: depth %" PRIu8 "\n", i+1); - j = 0; - oldn = arg->map->n; - for (kv = h48map_nextkvpair(arg->map, &j); - j != arg->map->capacity; - kv = h48map_nextkvpair(arg->map, &j) - ) { - if (kv.val != i) - continue; - cube = invcoord_h48(kv.key, arg->crep, 11); - for (m = 0; m < 18; m++) { - d = move(cube, m); - _foreach_h48sim( - d, arg->cocsepdata, arg->selfsim, 11, - coord = coord_h48(d, arg->cocsepdata, 11); - h48map_insertmin(arg->map, coord, i+1); - ) - } - } - LOG("found %" PRIu8 "\n", arg->map->n-oldn); - } - - return arg->map->n; -} - -/* Generic function that dispatches to the data generators */ -_static size_t -gendata_h48(gendata_h48_arg_t *arg) -{ - static const size_t infosize = 88; /* TODO: change to e.g. 1024 */ - - size_t cocsepsize, h48size; - - /* TODO: move info at the start */ - arg->cocsepdata = (uint32_t *)arg->buf; - cocsepsize = gendata_cocsep( - (void *)arg->cocsepdata, arg->selfsim, arg->crep); - arg->h48data = arg->cocsepdata + (cocsepsize / sizeof(uint32_t)); - arg->info = arg->h48data + - (H48_TABLESIZE(arg->h, arg->k) / sizeof(uint32_t)); - - if (arg->buf != NULL) - memset(arg->h48data, 0xFF, H48_TABLESIZE(arg->h, arg->k)); - - if (arg->h == 0 && arg->k == 4) { - h48size = gendata_h48h0k4(arg); - } else if (arg->k == 2) { - h48size = gendata_h48k2(arg); - } else { - h48size = 0; - LOG("Cannot generate data for h = %" PRIu8 " and k = %" PRIu8 - " (not implemented yet)\n", arg->h, arg->k); - } - - return infosize + cocsepsize + h48size; -} - -/* -TODO description -generating fixed table with h=0, k=4 -*/ -_static size_t -gendata_h48h0k4(gendata_h48_arg_t *arg) -{ - uint32_t j; - bfsarg_esep_t bfsarg; - int64_t sc, cc, esep_max; -/* - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; - size_t cocsepsize, infosize; -*/ - - if (arg->buf == NULL) - goto gendata_h48h0k4_return_size; -/* - cocsepsize = gendata_cocsep(buf, selfsim, crep); - infosize = 88; - - cocsepdata = (uint32_t *)buf; - buf32 = cocsepdata + cocsepsize / 4; - info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t)); - memset(buf32, 0xFF, H48_TABLESIZE(0, 4)); -*/ - - esep_max = (int64_t)H48_COORDMAX(0); - sc = coord_h48(solved, arg->cocsepdata, 0); - set_esep_pval(arg->h48data, sc, 4, 0); - arg->info[1] = 1; - bfsarg = (bfsarg_esep_t) { - .cocsepdata = arg->cocsepdata, - .buf32 = arg->h48data, - .selfsim = arg->selfsim, - .crep = arg->crep - }; - for ( - bfsarg.done = 1, bfsarg.depth = 1, cc = 0; - bfsarg.done < esep_max && bfsarg.depth <= arg->maxdepth; - bfsarg.depth++ - ) { - LOG("esep: generating depth %" PRIu8 "\n", bfsarg.depth); - cc = gendata_h48h0k4_bfs(&bfsarg); - bfsarg.done += cc; - arg->info[bfsarg.depth+1] = cc; - LOG("found %" PRId64 "\n", cc); - } - - arg->info[0] = bfsarg.depth-1; - - LOG("h48 pruning table computed\n"); - LOG("Maximum pruning value: %" PRIu32 "\n", arg->info[0]); - LOG("Pruning value distribution:\n"); - for (j = 0; j <= arg->info[0]; j++) - LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, arg->info[j+1]); - -gendata_h48h0k4_return_size: - return H48_TABLESIZE(0, 4); -} - -_static int64_t -gendata_h48h0k4_bfs(bfsarg_esep_t *arg) -{ - const uint8_t breakpoint = 10; /* Hand-picked optimal */ - - if (arg->depth < breakpoint) - return gendata_h48h0k4_bfs_fromdone(arg); - else - return gendata_h48h0k4_bfs_fromnew(arg); -} - -_static int64_t -gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) -{ - uint8_t c, m, x; - uint32_t cc; - int64_t i, j, k; - cube_t cube, moved; - - for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { - c = get_esep_pval(arg->buf32, i, 4); - if (c != arg->depth - 1) - continue; - cube = invcoord_h48(i, arg->crep, 0); - for (m = 0; m < 18; m++) { - moved = move(cube, m); - j = coord_h48(moved, arg->cocsepdata, 0); - if (get_esep_pval(arg->buf32, j, 4) <= arg->depth) - continue; - _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, - k = coord_h48(moved, arg->cocsepdata, 0); - x = get_esep_pval(arg->buf32, k, 4); - set_esep_pval(arg->buf32, k, 4, arg->depth); - cc += x != arg->depth; - ) - } - } - - return cc; -} - -_static int64_t -gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) -{ - uint8_t c, m, x; - uint32_t cc; - int64_t i, j; - cube_t cube, moved; - - for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { - c = get_esep_pval(arg->buf32, i, 4); - if (c != 0xF) - continue; - cube = invcoord_h48(i, arg->crep, 0); - for (m = 0; m < 18; m++) { - moved = move(cube, m); - j = coord_h48(moved, arg->cocsepdata, 0); - x = get_esep_pval(arg->buf32, j, 4); - if (x >= arg->depth) - continue; - _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, - j = coord_h48(cube, arg->cocsepdata, 0); - x = get_esep_pval(arg->buf32, j, 4); - set_esep_pval(arg->buf32, j, 4, arg->depth); - cc += x == 0xF; - ) - break; /* Enough to find one, skip the rest */ - } - } - - return cc; -} - -_static size_t -gendata_h48k2(gendata_h48_arg_t *arg) -{ - static const uint8_t shortdepth = 8; - static const uint64_t capacity = 10000019; - static const uint64_t randomizer = 10000079; - static const uint8_t base[] = { - [0] = 8, - [1] = 8, - [2] = 8, - [3] = 8, - [4] = 9, - [5] = 9, - [6] = 9, - [7] = 9, - [8] = 10, - [9] = 10, - [10] = 10, - [11] = 10 - }; - - uint64_t nshort; - h48map_t shortcubes; - gendata_h48short_arg_t shortarg; - - DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); - - if (arg->buf == NULL) - goto gendata_h48k2_return_size; - - LOG("Computing depth <=%" PRIu8 "\n", shortdepth) - h48map_create(&shortcubes, capacity, randomizer); - shortarg = (gendata_h48short_arg_t) { - .maxdepth = shortdepth, - .cocsepdata = arg->cocsepdata, - .crep = arg->crep, - .selfsim = arg->selfsim, - .map = &shortcubes - }; - nshort = gen_h48short(&shortarg); - LOG("Found %" PRIu64 "\n", nshort); - - /* TODO: loop over map, set all found to 0, do 2 moves each */ - LOG("The rest is not implemented yet\n"); - - h48map_destroy(&shortcubes); - -gendata_h48k2_return_size: - return H48_TABLESIZE(arg->h, 2); -} - -_static_inline uint8_t -get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k) -{ - return (buf32[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k); -} - -_static_inline void -set_esep_pval(uint32_t *buf32, int64_t i, uint8_t k, uint8_t val) -{ - buf32[H48_INDEX(i, k)] = (buf32[H48_INDEX(i, k)] & (~H48_MASK(i, k))) - | (val << H48_SHIFT(i, k)); -} - -_static_inline int8_t -get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint32_t *h48data) -{ - int64_t coord; - - coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); - return get_esep_pval(h48data, coord, k); -} diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h new file mode 100644 index 0000000..2b1347f --- /dev/null +++ b/src/solvers/h48/gendata_h48.h @@ -0,0 +1,351 @@ +#define H48_COORDMAX_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) +#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (size_t)(h)) +#define H48_TABLESIZE(h, k) (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) + +#define H48_COEFF(k) (UINT32_C(32) / (uint32_t)(k)) +#define H48_INDEX(i, k) ((uint32_t)(i) / H48_COEFF(k)) +#define H48_SHIFT(i, k) ((uint32_t)(k) * ((uint32_t)(i) % H48_COEFF(k))) +#define H48_MASK(i, k) ((_bit_u32(k) - (uint32_t)(1)) << H48_SHIFT(i, k)) + +#define MAXLEN 20 + +/* +TODO: This loop over similar h48 coordinates can be improved by only +transforming edges, but we need to compose transformations (i.e. conjugate +_t by _ttrep). +*/ +#define _foreach_h48sim(_cube, _cocsepdata, _selfsim, _h, _action) \ + int64_t _cocsep = coord_cocsep(_cube); \ + uint8_t _ttrep = TTREP(_cocsepdata[_cocsep]); \ + uint8_t _inverse_ttrep = inverse_trans(_ttrep); \ + int64_t _coclass = COCLASS(_cocsepdata[_cocsep]); \ + cube_t _rep = transform(_cube, _ttrep); \ + uint64_t _sim = _selfsim[_coclass]; \ + for (uint8_t _t = 0; _t < 48 && _sim; _t++, _sim >>= 1) { \ + if (!(_sim & 1)) continue; \ + _cube = transform(_rep, _t); \ + _cube = transform(_cube, _inverse_ttrep); \ + _action \ + } + +typedef struct { + uint8_t h; + uint8_t k; + uint8_t maxdepth; + void *buf; + uint32_t *info; + uint32_t *cocsepdata; + uint32_t *h48data; + uint64_t selfsim[COCSEP_CLASSES]; + cube_t crep[COCSEP_CLASSES]; +} gendata_h48_arg_t; + +typedef struct { + uint8_t maxdepth; + const uint32_t *cocsepdata; + const cube_t *crep; + const uint64_t *selfsim; + h48map_t *map; +} gendata_h48short_arg_t; + +typedef struct { + uint8_t depth; + uint32_t *cocsepdata; + uint32_t *buf32; + uint64_t *selfsim; + int64_t done; + cube_t *crep; +} bfsarg_esep_t; + +_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t); +_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); + +_static uint64_t gen_h48short(gendata_h48short_arg_t *); +_static size_t gendata_h48(gendata_h48_arg_t *); +_static size_t gendata_h48h0k4(gendata_h48_arg_t *); +_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); +_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); +_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); +_static size_t gendata_h48k2(gendata_h48_arg_t *); + +_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *); + +_static uint64_t +gen_h48short(gendata_h48short_arg_t *arg) +{ + uint8_t i, m; + int64_t coord; + uint64_t j, oldn; + kvpair_t kv; + cube_t cube, d; + + cube = solvedcube(); + coord = coord_h48(cube, arg->cocsepdata, 11); + h48map_insertmin(arg->map, coord, 0); + oldn = 0; + LOG("Short h48: depth 0\nfound %" PRIu8 "\n", arg->map->n-oldn); + for (i = 0; i < arg->maxdepth; i++) { + LOG("Short h48: depth %" PRIu8 "\n", i+1); + j = 0; + oldn = arg->map->n; + for (kv = h48map_nextkvpair(arg->map, &j); + j != arg->map->capacity; + kv = h48map_nextkvpair(arg->map, &j) + ) { + if (kv.val != i) + continue; + cube = invcoord_h48(kv.key, arg->crep, 11); + for (m = 0; m < 18; m++) { + d = move(cube, m); + _foreach_h48sim( + d, arg->cocsepdata, arg->selfsim, 11, + coord = coord_h48(d, arg->cocsepdata, 11); + h48map_insertmin(arg->map, coord, i+1); + ) + } + } + LOG("found %" PRIu8 "\n", arg->map->n-oldn); + } + + return arg->map->n; +} + +/* Generic function that dispatches to the data generators */ +_static size_t +gendata_h48(gendata_h48_arg_t *arg) +{ + static const size_t infosize = 88; /* TODO: change to e.g. 1024 */ + + size_t cocsepsize, h48size; + + /* TODO: move info at the start */ + arg->cocsepdata = (uint32_t *)arg->buf; + cocsepsize = gendata_cocsep( + (void *)arg->cocsepdata, arg->selfsim, arg->crep); + arg->h48data = arg->cocsepdata + (cocsepsize / sizeof(uint32_t)); + arg->info = arg->h48data + + (H48_TABLESIZE(arg->h, arg->k) / sizeof(uint32_t)); + + if (arg->buf != NULL) + memset(arg->h48data, 0xFF, H48_TABLESIZE(arg->h, arg->k)); + + if (arg->h == 0 && arg->k == 4) { + h48size = gendata_h48h0k4(arg); + } else if (arg->k == 2) { + h48size = gendata_h48k2(arg); + } else { + h48size = 0; + LOG("Cannot generate data for h = %" PRIu8 " and k = %" PRIu8 + " (not implemented yet)\n", arg->h, arg->k); + } + + return infosize + cocsepsize + h48size; +} + +/* +TODO description +generating fixed table with h=0, k=4 +*/ +_static size_t +gendata_h48h0k4(gendata_h48_arg_t *arg) +{ + uint32_t j; + bfsarg_esep_t bfsarg; + int64_t sc, cc, esep_max; +/* + uint64_t selfsim[COCSEP_CLASSES]; + cube_t crep[COCSEP_CLASSES]; + size_t cocsepsize, infosize; +*/ + + if (arg->buf == NULL) + goto gendata_h48h0k4_return_size; +/* + cocsepsize = gendata_cocsep(buf, selfsim, crep); + infosize = 88; + + cocsepdata = (uint32_t *)buf; + buf32 = cocsepdata + cocsepsize / 4; + info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t)); + memset(buf32, 0xFF, H48_TABLESIZE(0, 4)); +*/ + + esep_max = (int64_t)H48_COORDMAX(0); + sc = coord_h48(solved, arg->cocsepdata, 0); + set_esep_pval(arg->h48data, sc, 4, 0); + arg->info[1] = 1; + bfsarg = (bfsarg_esep_t) { + .cocsepdata = arg->cocsepdata, + .buf32 = arg->h48data, + .selfsim = arg->selfsim, + .crep = arg->crep + }; + for ( + bfsarg.done = 1, bfsarg.depth = 1, cc = 0; + bfsarg.done < esep_max && bfsarg.depth <= arg->maxdepth; + bfsarg.depth++ + ) { + LOG("esep: generating depth %" PRIu8 "\n", bfsarg.depth); + cc = gendata_h48h0k4_bfs(&bfsarg); + bfsarg.done += cc; + arg->info[bfsarg.depth+1] = cc; + LOG("found %" PRId64 "\n", cc); + } + + arg->info[0] = bfsarg.depth-1; + + LOG("h48 pruning table computed\n"); + LOG("Maximum pruning value: %" PRIu32 "\n", arg->info[0]); + LOG("Pruning value distribution:\n"); + for (j = 0; j <= arg->info[0]; j++) + LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, arg->info[j+1]); + +gendata_h48h0k4_return_size: + return H48_TABLESIZE(0, 4); +} + +_static int64_t +gendata_h48h0k4_bfs(bfsarg_esep_t *arg) +{ + const uint8_t breakpoint = 10; /* Hand-picked optimal */ + + if (arg->depth < breakpoint) + return gendata_h48h0k4_bfs_fromdone(arg); + else + return gendata_h48h0k4_bfs_fromnew(arg); +} + +_static int64_t +gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) +{ + uint8_t c, m, x; + uint32_t cc; + int64_t i, j, k; + cube_t cube, moved; + + for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { + c = get_esep_pval(arg->buf32, i, 4); + if (c != arg->depth - 1) + continue; + cube = invcoord_h48(i, arg->crep, 0); + for (m = 0; m < 18; m++) { + moved = move(cube, m); + j = coord_h48(moved, arg->cocsepdata, 0); + if (get_esep_pval(arg->buf32, j, 4) <= arg->depth) + continue; + _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, + k = coord_h48(moved, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, k, 4); + set_esep_pval(arg->buf32, k, 4, arg->depth); + cc += x != arg->depth; + ) + } + } + + return cc; +} + +_static int64_t +gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) +{ + uint8_t c, m, x; + uint32_t cc; + int64_t i, j; + cube_t cube, moved; + + for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { + c = get_esep_pval(arg->buf32, i, 4); + if (c != 0xF) + continue; + cube = invcoord_h48(i, arg->crep, 0); + for (m = 0; m < 18; m++) { + moved = move(cube, m); + j = coord_h48(moved, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j, 4); + if (x >= arg->depth) + continue; + _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, + j = coord_h48(cube, arg->cocsepdata, 0); + x = get_esep_pval(arg->buf32, j, 4); + set_esep_pval(arg->buf32, j, 4, arg->depth); + cc += x == 0xF; + ) + break; /* Enough to find one, skip the rest */ + } + } + + return cc; +} + +_static size_t +gendata_h48k2(gendata_h48_arg_t *arg) +{ + static const uint8_t shortdepth = 8; + static const uint64_t capacity = 10000019; + static const uint64_t randomizer = 10000079; + static const uint8_t base[] = { + [0] = 8, + [1] = 8, + [2] = 8, + [3] = 8, + [4] = 9, + [5] = 9, + [6] = 9, + [7] = 9, + [8] = 10, + [9] = 10, + [10] = 10, + [11] = 10 + }; + + uint64_t nshort; + h48map_t shortcubes; + gendata_h48short_arg_t shortarg; + + DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); + + if (arg->buf == NULL) + goto gendata_h48k2_return_size; + + LOG("Computing depth <=%" PRIu8 "\n", shortdepth) + h48map_create(&shortcubes, capacity, randomizer); + shortarg = (gendata_h48short_arg_t) { + .maxdepth = shortdepth, + .cocsepdata = arg->cocsepdata, + .crep = arg->crep, + .selfsim = arg->selfsim, + .map = &shortcubes + }; + nshort = gen_h48short(&shortarg); + LOG("Found %" PRIu64 "\n", nshort); + + /* TODO: loop over map, set all found to 0, do 2 moves each */ + LOG("The rest is not implemented yet\n"); + + h48map_destroy(&shortcubes); + +gendata_h48k2_return_size: + return H48_TABLESIZE(arg->h, 2); +} + +_static_inline uint8_t +get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k) +{ + return (buf32[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k); +} + +_static_inline void +set_esep_pval(uint32_t *buf32, int64_t i, uint8_t k, uint8_t val) +{ + buf32[H48_INDEX(i, k)] = (buf32[H48_INDEX(i, k)] & (~H48_MASK(i, k))) + | (val << H48_SHIFT(i, k)); +} + +_static_inline int8_t +get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint32_t *h48data) +{ + int64_t coord; + + coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); + return get_esep_pval(h48data, coord, k); +} diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index d9e8af3..4edc5ac 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h @@ -1,5 +1,5 @@ #include "coordinate.h" #include "map.h" #include "gendata_cocsep.h" -#include "gendata_full.h" +#include "gendata_h48.h" #include "solve.h" -- cgit v1.3 From f2907e471b3caddc5844bc6994e1cbd249019747 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 26 Aug 2024 15:35:09 +0200 Subject: Fixed bug in run solve --- shell.c | 6 +++--- src/nissy.c | 12 ++++++++++-- 2 files changed, 13 insertions(+), 5 deletions(-) diff --git a/shell.c b/shell.c index c1efcbd..66b1444 100644 --- a/shell.c +++ b/shell.c @@ -183,21 +183,21 @@ struct { ), COMMAND( "datasize", - "datasize" _flag_solver " SOLVER " _flag_options " OPTIONS", + "datasize " _flag_solver " SOLVER " _flag_options " OPTIONS", "Return the size in bytes of the data table used by " "SOLVER when called with the given OPTIONS.", datasize_exec ), COMMAND( "gendata", - "gendata" _flag_solver " SOLVER " _flag_options " OPTIONS", + "gendata " _flag_solver " SOLVER " _flag_options " OPTIONS", "Generate the data table used by " "SOLVER when called with the given OPTIONS.", gendata_exec ), COMMAND( "solve", - "solve" _flag_solver " SOLVER " _flag_options " OPTIONS " + "solve " _flag_solver " SOLVER " _flag_options " OPTIONS " "[" _flag_minmoves " n] [" _flag_maxmoves " N] " _flag_cube " CUBE", "Solve the given CUBE using SOLVER with the given OPTIONS, " diff --git a/src/nissy.c b/src/nissy.c index 5641dd9..f8c1f4d 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -26,23 +26,31 @@ struct { _static int parse_h48_options(const char *buf, uint8_t *h, uint8_t *k, uint8_t *maxdepth) { + bool h_valid, k_valid, maxdepth_valid; int i; /* TODO temporarily, options are in the form "h;k;maxdepth" */ if (h != NULL) *h = atoi(buf); + h_valid = h == NULL || *h <= 11; + for (i = 0; buf[i] != ';'; i++) if (buf[i] == 0) goto parse_h48_options_error; + if (k != NULL) *k = atoi(&buf[i+1]); + k_valid = k == NULL || (*k == 2 || *k == 4); + for (i = i+1; buf[i] != ';'; i++) if (buf[i] == 0) goto parse_h48_options_error; + if (maxdepth != NULL) *maxdepth = atoi(&buf[i+1]); + maxdepth_valid = maxdepth == NULL || *maxdepth <= 20; - return (*h <= 11 && (*k == 2 || *k == 4) && *maxdepth <= 20) ? 0 : 1; + return h_valid && k_valid && maxdepth_valid ? 0 : 1; parse_h48_options_error: *h = 0; @@ -202,7 +210,7 @@ nissy_gendata( if (!strcmp(solver, "h48")) { p = parse_h48_options(options, &arg.h, &arg.k, &arg.maxdepth); if (p != 0) { - LOG("gendata: ould not parse options\n"); + LOG("gendata: could not parse options\n"); ret = -1; } else { ret = gendata_h48(&arg); -- cgit v1.3 From c558c7989eaa0921f7b29ee274b325f4f6d97f8c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 26 Aug 2024 21:42:50 +0200 Subject: Gendata added for h48k2, need to verify with new tool --- src/solvers/h48/gendata_cocsep.h | 14 +-- src/solvers/h48/gendata_h48.h | 134 ++++++++++++++++++----- test/112_gen_h48short/00_depth_1.in | 28 +++++ test/112_gen_h48short/00_depth_1.out | 3 + test/112_gen_h48short/01_depth_3.in | 3 + test/112_gen_h48short/01_depth_3.out | 40 +++++++ test/112_gen_h48short/gen_h48short.c | 87 +++++++++++++++ test/112_gendata_h48/00_h_0.in | 2 - test/112_gendata_h48/00_h_0.out | 23 ---- test/112_gendata_h48/gendata_h48_tests.c | 50 --------- test/113_gen_h48short/00_depth_1.in | 28 ----- test/113_gen_h48short/00_depth_1.out | 3 - test/113_gen_h48short/01_depth_3.in | 3 - test/113_gen_h48short/01_depth_3.out | 40 ------- test/113_gen_h48short/gen_h48short.c | 87 --------------- test/120_gendata_h48h0k4/00_h_0.in | 2 + test/120_gendata_h48h0k4/00_h_0.out | 23 ++++ test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c | 50 +++++++++ 18 files changed, 347 insertions(+), 273 deletions(-) create mode 100644 test/112_gen_h48short/00_depth_1.in create mode 100644 test/112_gen_h48short/00_depth_1.out create mode 100644 test/112_gen_h48short/01_depth_3.in create mode 100644 test/112_gen_h48short/01_depth_3.out create mode 100644 test/112_gen_h48short/gen_h48short.c delete mode 100644 test/112_gendata_h48/00_h_0.in delete mode 100644 test/112_gendata_h48/00_h_0.out delete mode 100644 test/112_gendata_h48/gendata_h48_tests.c delete mode 100644 test/113_gen_h48short/00_depth_1.in delete mode 100644 test/113_gen_h48short/00_depth_1.out delete mode 100644 test/113_gen_h48short/01_depth_3.in delete mode 100644 test/113_gen_h48short/01_depth_3.out delete mode 100644 test/113_gen_h48short/gen_h48short.c create mode 100644 test/120_gendata_h48h0k4/00_h_0.in create mode 100644 test/120_gendata_h48h0k4/00_h_0.out create mode 100644 test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h index 13ce68b..0f96da9 100644 --- a/src/solvers/h48/gendata_cocsep.h +++ b/src/solvers/h48/gendata_cocsep.h @@ -18,13 +18,13 @@ typedef struct { uint8_t *visited; uint64_t *selfsim; cube_t *rep; -} dfsarg_cocsep_t; +} cocsep_dfs_arg_t; _static_inline bool get_visited(const uint8_t *, int64_t); _static_inline void set_visited(uint8_t *, int64_t); _static size_t gendata_cocsep(void *, uint64_t *, cube_t *); -_static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *); +_static uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *); _static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *); @@ -45,7 +45,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep) uint32_t *buf32, *info, cc; uint16_t n; uint8_t i, j, visited[COCSEP_VISITEDSIZE]; - dfsarg_cocsep_t arg; + cocsep_dfs_arg_t arg; if (buf == NULL) goto gendata_cocsep_return_size; @@ -56,7 +56,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_t *rep) if (selfsim != NULL) memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); - arg = (dfsarg_cocsep_t) { + arg = (cocsep_dfs_arg_t) { .cube = solved, .n = &n, .buf32 = buf32, @@ -92,14 +92,14 @@ gendata_cocsep_return_size: } _static uint32_t -gendata_cocsep_dfs(dfsarg_cocsep_t *arg) +gendata_cocsep_dfs(cocsep_dfs_arg_t *arg) { uint8_t m; uint32_t cc, class, ttrep, depth, olddepth, tinv; uint64_t t; int64_t i, j; cube_t d; - dfsarg_cocsep_t nextarg; + cocsep_dfs_arg_t nextarg; i = coord_cocsep(arg->cube); olddepth = (uint8_t)(arg->buf32[i] & 0xFF); @@ -135,7 +135,7 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg) return cc; } - memcpy(&nextarg, arg, sizeof(dfsarg_cocsep_t)); + memcpy(&nextarg, arg, sizeof(cocsep_dfs_arg_t)); nextarg.depth++; for (m = 0, cc = 0; m < 18; m++) { nextarg.cube = move(arg->cube, m); diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index 2b1347f..2d222c9 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h @@ -1,6 +1,6 @@ -#define H48_COORDMAX_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) -#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (size_t)(h)) -#define H48_TABLESIZE(h, k) (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) +#define H48_COORDMAX_NOEO ((int64_t)(COCSEP_CLASSES * _12c4 * _8c4)) +#define H48_COORDMAX(h) ((int64_t)(H48_COORDMAX_NOEO << (int64_t)(h))) +#define H48_TABLESIZE(h, k) ((size_t)H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) #define H48_COEFF(k) (UINT32_C(32) / (uint32_t)(k)) #define H48_INDEX(i, k) ((uint32_t)(i) / H48_COEFF(k)) @@ -55,7 +55,23 @@ typedef struct { uint64_t *selfsim; int64_t done; cube_t *crep; -} bfsarg_esep_t; +} h48h0k4_bfs_arg_t; + +typedef struct { + cube_t cube; + uint8_t moves[4]; + uint8_t h; + uint8_t k; + uint8_t base; + uint8_t depth; + uint8_t shortdepth; + uint8_t maxdepth; + uint32_t *cocsepdata; + uint32_t *h48data; + uint64_t *selfsim; + cube_t *crep; + h48map_t *shortcubes; +} h48k2_dfs_arg_t; _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t); _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); @@ -63,10 +79,11 @@ _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); _static uint64_t gen_h48short(gendata_h48short_arg_t *); _static size_t gendata_h48(gendata_h48_arg_t *); _static size_t gendata_h48h0k4(gendata_h48_arg_t *); -_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); -_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); +_static int64_t gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *); +_static int64_t gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *); +_static int64_t gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *); _static size_t gendata_h48k2(gendata_h48_arg_t *); +_static void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg); _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *); @@ -150,31 +167,17 @@ _static size_t gendata_h48h0k4(gendata_h48_arg_t *arg) { uint32_t j; - bfsarg_esep_t bfsarg; + h48h0k4_bfs_arg_t bfsarg; int64_t sc, cc, esep_max; -/* - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; - size_t cocsepsize, infosize; -*/ if (arg->buf == NULL) goto gendata_h48h0k4_return_size; -/* - cocsepsize = gendata_cocsep(buf, selfsim, crep); - infosize = 88; - - cocsepdata = (uint32_t *)buf; - buf32 = cocsepdata + cocsepsize / 4; - info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t)); - memset(buf32, 0xFF, H48_TABLESIZE(0, 4)); -*/ esep_max = (int64_t)H48_COORDMAX(0); sc = coord_h48(solved, arg->cocsepdata, 0); set_esep_pval(arg->h48data, sc, 4, 0); arg->info[1] = 1; - bfsarg = (bfsarg_esep_t) { + bfsarg = (h48h0k4_bfs_arg_t) { .cocsepdata = arg->cocsepdata, .buf32 = arg->h48data, .selfsim = arg->selfsim, @@ -205,7 +208,7 @@ gendata_h48h0k4_return_size: } _static int64_t -gendata_h48h0k4_bfs(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs(h48h0k4_bfs_arg_t *arg) { const uint8_t breakpoint = 10; /* Hand-picked optimal */ @@ -216,7 +219,7 @@ gendata_h48h0k4_bfs(bfsarg_esep_t *arg) } _static int64_t -gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs_fromdone(h48h0k4_bfs_arg_t *arg) { uint8_t c, m, x; uint32_t cc; @@ -246,7 +249,7 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) } _static int64_t -gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) +gendata_h48h0k4_bfs_fromnew(h48h0k4_bfs_arg_t *arg) { uint8_t c, m, x; uint32_t cc; @@ -298,9 +301,13 @@ gendata_h48k2(gendata_h48_arg_t *arg) [11] = 10 }; - uint64_t nshort; + uint8_t t; + int64_t j; + uint64_t nshort, i; h48map_t shortcubes; + kvpair_t kv; gendata_h48short_arg_t shortarg; + h48k2_dfs_arg_t dfsarg; DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); @@ -317,17 +324,84 @@ gendata_h48k2(gendata_h48_arg_t *arg) .map = &shortcubes }; nshort = gen_h48short(&shortarg); - LOG("Found %" PRIu64 "\n", nshort); + LOG("Cubes in <= %" PRIu8 " moves: %" PRIu64 "\n", shortdepth, nshort); + + dfsarg = (h48k2_dfs_arg_t){ + .h = arg->h, + .k = arg->k, + .base = base[arg->h], + .depth = shortdepth, + .shortdepth = shortdepth, + .maxdepth = arg->maxdepth, + .cocsepdata = arg->cocsepdata, + .h48data = arg->h48data, + .selfsim = arg->selfsim, + .crep = arg->crep, + .shortcubes = &shortcubes + }; - /* TODO: loop over map, set all found to 0, do 2 moves each */ - LOG("The rest is not implemented yet\n"); + i = 0; + for (kv = h48map_nextkvpair(&shortcubes, &i); + i != shortcubes.capacity; + kv = h48map_nextkvpair(&shortcubes, &i) + ) { + /* TODO maybe over all sim? */ + dfsarg.cube = invcoord_h48(kv.key, arg->crep, 11); + gendata_h48k2_dfs(&dfsarg); + } h48map_destroy(&shortcubes); + /* TODO: move info update to dfs? */ + memset(arg->info, 0, 5 * sizeof(arg->info[0])); + arg->info[0] = base[arg->k]; + for (j = 0; j < H48_COORDMAX(arg->h); j++) { + t = get_esep_pval(arg->h48data, j, 2); + arg->info[1 + t]++; + } + gendata_h48k2_return_size: return H48_TABLESIZE(arg->h, 2); } +_static void +gendata_h48k2_dfs(h48k2_dfs_arg_t *arg) +{ + uint8_t nmoves; + uint64_t val; + int64_t coord, fullcoord; + h48k2_dfs_arg_t nextarg; + uint8_t m; + + fullcoord = coord_h48(arg->cube, arg->cocsepdata, 11); + coord = fullcoord >> (int64_t)(11 - arg->h); + + val = h48map_value(arg->shortcubes, fullcoord); + + if (arg->depth >= arg->base && arg->depth <= arg->base + 2) + set_esep_pval( + arg->h48data, coord, arg->k, arg->depth - arg->base); + + if ((val < arg->shortdepth) || + (arg->depth > arg->shortdepth && val != MAP_UNSET) || + (arg->depth >= arg->maxdepth || arg->depth >= arg->base + 2)) + return; + + /* TODO: avoid copy, change arg and undo changes after recursion */ + nextarg = *arg; + nextarg.depth = arg->depth + 1; + nmoves = nextarg.depth - arg->shortdepth; + for (m = 0; m < 18; m++) { + nextarg.moves[nmoves - 1] = m; + if (!allowednextmove(nextarg.moves, nmoves)) { + m += 2; + continue; + } + nextarg.cube = move(arg->cube, m); + gendata_h48k2_dfs(&nextarg); + } +} + _static_inline uint8_t get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k) { diff --git a/test/112_gen_h48short/00_depth_1.in b/test/112_gen_h48short/00_depth_1.in new file mode 100644 index 0000000..c86f15b --- /dev/null +++ b/test/112_gen_h48short/00_depth_1.in @@ -0,0 +1,28 @@ +73 +157 +1 + +For longer test: + +20000003 +20000023 +8 + +Short h48: generating depth 0 +found 1 +Short h48: generating depth 1 +found 1 +Short h48: generating depth 2 +found 4 +Short h48: generating depth 3 +found 34 +Short h48: generating depth 4 +found 333 +Short h48: generating depth 5 +found 3815 +Short h48: generating depth 6 +found 45382 +Short h48: generating depth 7 +found 548562 +Short h48: generating depth 8 +found 6839723 diff --git a/test/112_gen_h48short/00_depth_1.out b/test/112_gen_h48short/00_depth_1.out new file mode 100644 index 0000000..b0dba31 --- /dev/null +++ b/test/112_gen_h48short/00_depth_1.out @@ -0,0 +1,3 @@ +2 +0 0 +71075840 1 diff --git a/test/112_gen_h48short/01_depth_3.in b/test/112_gen_h48short/01_depth_3.in new file mode 100644 index 0000000..920e70a --- /dev/null +++ b/test/112_gen_h48short/01_depth_3.in @@ -0,0 +1,3 @@ +73 +157 +3 diff --git a/test/112_gen_h48short/01_depth_3.out b/test/112_gen_h48short/01_depth_3.out new file mode 100644 index 0000000..dbce376 --- /dev/null +++ b/test/112_gen_h48short/01_depth_3.out @@ -0,0 +1,40 @@ +40 +0 0 +70981632 3 +71075840 1 +71086080 3 +142067712 2 +218789888 3 +218884096 2 +283879424 2 +283899904 3 +283953152 3 +283973632 2 +360548808 3 +360835072 3 +473668032 3 +473956352 3 +499869696 3 +500011008 3 +598679552 3 +599109185 3 +662171648 3 +662601226 3 +724818316 3 +725106688 3 +790513664 3 +790607872 3 +904991108 3 +926726144 3 +928729088 3 +1009662340 3 +1088755203 3 +1171758595 3 +1206452224 3 +1206480896 3 +1277360128 3 +1277454336 3 +1403695492 3 +1403697540 3 +1403736452 3 +1403738500 3 diff --git a/test/112_gen_h48short/gen_h48short.c b/test/112_gen_h48short/gen_h48short.c new file mode 100644 index 0000000..335821a --- /dev/null +++ b/test/112_gen_h48short/gen_h48short.c @@ -0,0 +1,87 @@ +#include "../test.h" + +#define COCSEP_CLASSES 3393 +#define MAXPOS 200 + +typedef struct { + uint64_t n; + uint64_t capacity; + uint64_t randomizer; + uint64_t *table; + uint32_t *info; + uint32_t *cocsepdata; + uint32_t *h48data; + uint64_t selfsim[COCSEP_CLASSES]; + cube_t crep[COCSEP_CLASSES]; +} h48map_t; + +typedef struct { + uint64_t key; + uint64_t val; +} kvpair_t; + +typedef struct { + uint8_t maxdepth; + const uint32_t *cocsepdata; + const cube_t *crep; + const uint64_t *selfsim; + h48map_t *map; +} gendata_h48short_arg_t; + +void h48map_create(h48map_t *, uint64_t, uint64_t); +void h48map_destroy(h48map_t *); +kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); +size_t gendata_cocsep(void *, uint64_t *, cube_t *); +uint64_t gen_h48short(gendata_h48short_arg_t *); + +char str[STRLENMAX]; + +int compare(const void *x, const void *y) { + uint64_t a = ((kvpair_t *)x)->key; + uint64_t b = ((kvpair_t *)y)->key; + + if (a > b) return 1; + if (a == b) return 0; + return -1; +} + +uint64_t readl(void) { + fgets(str, STRLENMAX, stdin); + return atoll(str); +} + +void run(void) { + uint32_t cocsepdata[300000]; + h48map_t map; + uint64_t i, j, capacity, randomizer, selfsim[COCSEP_CLASSES]; + kvpair_t kv, b[MAXPOS]; + gendata_h48short_arg_t arg; + cube_t crep[COCSEP_CLASSES]; + + capacity = readl(); + randomizer = readl(); + arg.maxdepth = readl(); + arg.cocsepdata = cocsepdata; + arg.crep = crep; + arg.selfsim = selfsim; + arg.map = ↦ + + h48map_create(&map, capacity, randomizer); + gendata_cocsep(cocsepdata, selfsim, crep); + gen_h48short(&arg); + + i = 0; + for (kv = h48map_nextkvpair(&map, &i), j = 0; + i != map.capacity && j < MAXPOS; + kv = h48map_nextkvpair(&map, &i) + ) { + b[j++] = kv; + } + qsort(b, j, sizeof(kvpair_t), compare); + + printf("%" PRIu64 "\n", map.n); + for (i = 0; i < j; i++) + printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); + + h48map_destroy(&map); +} diff --git a/test/112_gendata_h48/00_h_0.in b/test/112_gendata_h48/00_h_0.in deleted file mode 100644 index cb6e5ed..0000000 --- a/test/112_gendata_h48/00_h_0.in +++ /dev/null @@ -1,2 +0,0 @@ -5 -0 diff --git a/test/112_gendata_h48/00_h_0.out b/test/112_gendata_h48/00_h_0.out deleted file mode 100644 index 04e8bf6..0000000 --- a/test/112_gendata_h48/00_h_0.out +++ /dev/null @@ -1,23 +0,0 @@ -59903605 - -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: 3612 diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/112_gendata_h48/gendata_h48_tests.c deleted file mode 100644 index d6c6cb2..0000000 --- a/test/112_gendata_h48/gendata_h48_tests.c +++ /dev/null @@ -1,50 +0,0 @@ -#include "../test.h" - -#define COCSEP_CLASSES 3393 -#define COCSEPSIZE 1119792 - -typedef struct { - uint8_t h; - uint8_t k; - uint8_t maxdepth; - void *buf; - uint32_t *info; - uint32_t *cocsepdata; - uint32_t *h48data; - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; -} gendata_h48_arg_t; - -int64_t gendata_h48(gendata_h48_arg_t *); - -void run(void) { - char str[STRLENMAX]; - uint8_t i; - gendata_h48_arg_t arg; - size_t result, sz; - - fgets(str, STRLENMAX, stdin); - arg.maxdepth = atoi(str); - fgets(str, STRLENMAX, stdin); - arg.h = atoi(str); - arg.k = 4; - - sz = gendata_h48(&arg); /* With buf = NULL returns data size */ - arg.buf = malloc(sz); - result = gendata_h48(&arg); - - printf("%zu\n\n", result); - - printf("cocsepdata:\n"); - printf("Classes: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-12]); - printf("Max value: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-11]); - for (i = 0; i < 10; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", - i, arg.cocsepdata[COCSEPSIZE/4-10+i]); - - printf("\nh48:\n"); - for (i = 0; i < arg.maxdepth+1; i++) - printf("%" PRIu32 ": %" PRIu32 "\n", i, arg.info[i+1]); - - free(arg.buf); -} diff --git a/test/113_gen_h48short/00_depth_1.in b/test/113_gen_h48short/00_depth_1.in deleted file mode 100644 index c86f15b..0000000 --- a/test/113_gen_h48short/00_depth_1.in +++ /dev/null @@ -1,28 +0,0 @@ -73 -157 -1 - -For longer test: - -20000003 -20000023 -8 - -Short h48: generating depth 0 -found 1 -Short h48: generating depth 1 -found 1 -Short h48: generating depth 2 -found 4 -Short h48: generating depth 3 -found 34 -Short h48: generating depth 4 -found 333 -Short h48: generating depth 5 -found 3815 -Short h48: generating depth 6 -found 45382 -Short h48: generating depth 7 -found 548562 -Short h48: generating depth 8 -found 6839723 diff --git a/test/113_gen_h48short/00_depth_1.out b/test/113_gen_h48short/00_depth_1.out deleted file mode 100644 index b0dba31..0000000 --- a/test/113_gen_h48short/00_depth_1.out +++ /dev/null @@ -1,3 +0,0 @@ -2 -0 0 -71075840 1 diff --git a/test/113_gen_h48short/01_depth_3.in b/test/113_gen_h48short/01_depth_3.in deleted file mode 100644 index 920e70a..0000000 --- a/test/113_gen_h48short/01_depth_3.in +++ /dev/null @@ -1,3 +0,0 @@ -73 -157 -3 diff --git a/test/113_gen_h48short/01_depth_3.out b/test/113_gen_h48short/01_depth_3.out deleted file mode 100644 index dbce376..0000000 --- a/test/113_gen_h48short/01_depth_3.out +++ /dev/null @@ -1,40 +0,0 @@ -40 -0 0 -70981632 3 -71075840 1 -71086080 3 -142067712 2 -218789888 3 -218884096 2 -283879424 2 -283899904 3 -283953152 3 -283973632 2 -360548808 3 -360835072 3 -473668032 3 -473956352 3 -499869696 3 -500011008 3 -598679552 3 -599109185 3 -662171648 3 -662601226 3 -724818316 3 -725106688 3 -790513664 3 -790607872 3 -904991108 3 -926726144 3 -928729088 3 -1009662340 3 -1088755203 3 -1171758595 3 -1206452224 3 -1206480896 3 -1277360128 3 -1277454336 3 -1403695492 3 -1403697540 3 -1403736452 3 -1403738500 3 diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c deleted file mode 100644 index 335821a..0000000 --- a/test/113_gen_h48short/gen_h48short.c +++ /dev/null @@ -1,87 +0,0 @@ -#include "../test.h" - -#define COCSEP_CLASSES 3393 -#define MAXPOS 200 - -typedef struct { - uint64_t n; - uint64_t capacity; - uint64_t randomizer; - uint64_t *table; - uint32_t *info; - uint32_t *cocsepdata; - uint32_t *h48data; - uint64_t selfsim[COCSEP_CLASSES]; - cube_t crep[COCSEP_CLASSES]; -} h48map_t; - -typedef struct { - uint64_t key; - uint64_t val; -} kvpair_t; - -typedef struct { - uint8_t maxdepth; - const uint32_t *cocsepdata; - const cube_t *crep; - const uint64_t *selfsim; - h48map_t *map; -} gendata_h48short_arg_t; - -void h48map_create(h48map_t *, uint64_t, uint64_t); -void h48map_destroy(h48map_t *); -kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *); -size_t gendata_cocsep(void *, uint64_t *, cube_t *); -uint64_t gen_h48short(gendata_h48short_arg_t *); - -char str[STRLENMAX]; - -int compare(const void *x, const void *y) { - uint64_t a = ((kvpair_t *)x)->key; - uint64_t b = ((kvpair_t *)y)->key; - - if (a > b) return 1; - if (a == b) return 0; - return -1; -} - -uint64_t readl(void) { - fgets(str, STRLENMAX, stdin); - return atoll(str); -} - -void run(void) { - uint32_t cocsepdata[300000]; - h48map_t map; - uint64_t i, j, capacity, randomizer, selfsim[COCSEP_CLASSES]; - kvpair_t kv, b[MAXPOS]; - gendata_h48short_arg_t arg; - cube_t crep[COCSEP_CLASSES]; - - capacity = readl(); - randomizer = readl(); - arg.maxdepth = readl(); - arg.cocsepdata = cocsepdata; - arg.crep = crep; - arg.selfsim = selfsim; - arg.map = ↦ - - h48map_create(&map, capacity, randomizer); - gendata_cocsep(cocsepdata, selfsim, crep); - gen_h48short(&arg); - - i = 0; - for (kv = h48map_nextkvpair(&map, &i), j = 0; - i != map.capacity && j < MAXPOS; - kv = h48map_nextkvpair(&map, &i) - ) { - b[j++] = kv; - } - qsort(b, j, sizeof(kvpair_t), compare); - - printf("%" PRIu64 "\n", map.n); - for (i = 0; i < j; i++) - printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val); - - h48map_destroy(&map); -} diff --git a/test/120_gendata_h48h0k4/00_h_0.in b/test/120_gendata_h48h0k4/00_h_0.in new file mode 100644 index 0000000..cb6e5ed --- /dev/null +++ b/test/120_gendata_h48h0k4/00_h_0.in @@ -0,0 +1,2 @@ +5 +0 diff --git a/test/120_gendata_h48h0k4/00_h_0.out b/test/120_gendata_h48h0k4/00_h_0.out new file mode 100644 index 0000000..04e8bf6 --- /dev/null +++ b/test/120_gendata_h48h0k4/00_h_0.out @@ -0,0 +1,23 @@ +59903605 + +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: 3612 diff --git a/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c new file mode 100644 index 0000000..d6c6cb2 --- /dev/null +++ b/test/120_gendata_h48h0k4/gendata_h48h0k4_tests.c @@ -0,0 +1,50 @@ +#include "../test.h" + +#define COCSEP_CLASSES 3393 +#define COCSEPSIZE 1119792 + +typedef struct { + uint8_t h; + uint8_t k; + uint8_t maxdepth; + void *buf; + uint32_t *info; + uint32_t *cocsepdata; + uint32_t *h48data; + uint64_t selfsim[COCSEP_CLASSES]; + cube_t crep[COCSEP_CLASSES]; +} gendata_h48_arg_t; + +int64_t gendata_h48(gendata_h48_arg_t *); + +void run(void) { + char str[STRLENMAX]; + uint8_t i; + gendata_h48_arg_t arg; + size_t result, sz; + + fgets(str, STRLENMAX, stdin); + arg.maxdepth = atoi(str); + fgets(str, STRLENMAX, stdin); + arg.h = atoi(str); + arg.k = 4; + + sz = gendata_h48(&arg); /* With buf = NULL returns data size */ + arg.buf = malloc(sz); + result = gendata_h48(&arg); + + printf("%zu\n\n", result); + + printf("cocsepdata:\n"); + printf("Classes: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-12]); + printf("Max value: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-11]); + for (i = 0; i < 10; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", + i, arg.cocsepdata[COCSEPSIZE/4-10+i]); + + printf("\nh48:\n"); + for (i = 0; i < arg.maxdepth+1; i++) + printf("%" PRIu32 ": %" PRIu32 "\n", i, arg.info[i+1]); + + free(arg.buf); +} -- cgit v1.3 From b5efa2c7bfa259f1b9f5afa68349e2742427de80 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 27 Aug 2024 17:44:17 +0200 Subject: New tool for benchmarking small solver --- tools/001_gendata_h48/gendata_h48.c | 71 ---------------------- tools/001_gendata_h48h0k4/gendata_h48h0k4.c | 71 ++++++++++++++++++++++ tools/003_solve_small/solve_small.c | 94 +++++++++++++++++++++++++++++ 3 files changed, 165 insertions(+), 71 deletions(-) delete mode 100644 tools/001_gendata_h48/gendata_h48.c create mode 100644 tools/001_gendata_h48h0k4/gendata_h48h0k4.c create mode 100644 tools/003_solve_small/solve_small.c diff --git a/tools/001_gendata_h48/gendata_h48.c b/tools/001_gendata_h48/gendata_h48.c deleted file mode 100644 index a73f818..0000000 --- a/tools/001_gendata_h48/gendata_h48.c +++ /dev/null @@ -1,71 +0,0 @@ -#include "../timerun.h" -#include "../../src/nissy.h" - -#define MAXDEPTH 20 -#define HVALUE 0 -#define OPTIONS "0;4;20" -#define LONGOPTIONS "h = 0, k = 4, max depth = 20" - -#define COCSEPSIZE 1119792 -#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) - -uint32_t expected[21] = { - [0] = 1, - [1] = 1, - [2] = 4, - [3] = 34, - [4] = 331, - [5] = 3612, - [6] = 41605, - [7] = 474128, - [8] = 4953846, - [9] = 34776317, - [10] = 68566704, - [11] = 8749194, - [12] = 1673, -}; - -char *buf; - -void run(void) { - uint32_t *h48info, x; - 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); - h48info = (uint32_t *)buf + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4; - for (i = 0; i < MAXDEPTH+1 && h48info[i+1]; i++) { - x = h48info[i+1]; - printf("%d:\t%" PRIu32, i, x); - if (x != expected[i]) - printf(" <--- Error! Expected: %" PRIu32 "\n", - expected[i]); - printf("\n"); - } - } -} - -int main(void) { - int64_t size; - - nissy_setlogger(log_stderr); - - size = nissy_datasize("h48", OPTIONS); - if (size == -1) { - printf("gendata_h48 benchmark: error in datasize\n"); - return 1; - } - - buf = malloc(size); - - timerun(run, "benchmark gendata_h48 " LONGOPTIONS); - - free(buf); - - return 0; -} diff --git a/tools/001_gendata_h48h0k4/gendata_h48h0k4.c b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c new file mode 100644 index 0000000..a73f818 --- /dev/null +++ b/tools/001_gendata_h48h0k4/gendata_h48h0k4.c @@ -0,0 +1,71 @@ +#include "../timerun.h" +#include "../../src/nissy.h" + +#define MAXDEPTH 20 +#define HVALUE 0 +#define OPTIONS "0;4;20" +#define LONGOPTIONS "h = 0, k = 4, max depth = 20" + +#define COCSEPSIZE 1119792 +#define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) + +uint32_t expected[21] = { + [0] = 1, + [1] = 1, + [2] = 4, + [3] = 34, + [4] = 331, + [5] = 3612, + [6] = 41605, + [7] = 474128, + [8] = 4953846, + [9] = 34776317, + [10] = 68566704, + [11] = 8749194, + [12] = 1673, +}; + +char *buf; + +void run(void) { + uint32_t *h48info, x; + 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); + h48info = (uint32_t *)buf + (ETABLESIZE(HVALUE) + COCSEPSIZE) / 4; + for (i = 0; i < MAXDEPTH+1 && h48info[i+1]; i++) { + x = h48info[i+1]; + printf("%d:\t%" PRIu32, i, x); + if (x != expected[i]) + printf(" <--- Error! Expected: %" PRIu32 "\n", + expected[i]); + printf("\n"); + } + } +} + +int main(void) { + int64_t size; + + nissy_setlogger(log_stderr); + + size = nissy_datasize("h48", OPTIONS); + if (size == -1) { + printf("gendata_h48 benchmark: error in datasize\n"); + return 1; + } + + buf = malloc(size); + + timerun(run, "benchmark gendata_h48 " LONGOPTIONS); + + free(buf); + + return 0; +} diff --git a/tools/003_solve_small/solve_small.c b/tools/003_solve_small/solve_small.c new file mode 100644 index 0000000..406e255 --- /dev/null +++ b/tools/003_solve_small/solve_small.c @@ -0,0 +1,94 @@ +#include +#include +#include "../timerun.h" +#include "../../src/nissy.h" + +#define OPTIONS "0;4;20" + +const char *filename = "tables/h48h0k4"; +char *buf; +char *scrambles[] = { + "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */ + "RLUD RLUD RLUD", /* 12 optimal */ + NULL +}; + +void run(void) { + int i; + int64_t n; + char sol[100], cube[22]; + + printf("Solved the following scrambles:\n\n"); + for (i = 0; scrambles[i] != NULL; i++) { + printf("%s\n", scrambles[i]); + fprintf(stderr, "Solving scramble %s\n", scrambles[i]); + if (nissy_frommoves(scrambles[i], cube) == -1) { + fprintf(stderr, "Invalid scramble, " + "continuing with next scramble\n"); + continue; + } + n = nissy_solve( + cube, "h48", OPTIONS, "", 0, 20, 1, -1, buf, sol); + if (n == 0) + fprintf(stderr, "No solution found, " + "continuing with next scramble\n"); + } + printf("\n"); +} + +int getdata(int64_t size) { + int64_t s; + FILE *f; + + buf = malloc(size); + + if ((f = fopen(filename, "rb")) == NULL) { + fprintf(stderr, "Table file not found, generating them." + " This can take a while.\n"); + s = nissy_gendata("h48", OPTIONS, buf); + if (s != size) { + fprintf(stderr, "Error generating table"); + if (s != -1) + fprintf(stderr, " (got %" PRId64 " bytes)", s); + fprintf(stderr, "\n"); + return 1; + } + if ((f = fopen(filename, "wb")) == NULL) { + fprintf(stderr, "Could not write tables to file %s" + ", will be regenerated next time.\n", filename); + } else { + fwrite(buf, size, 1, f); + fclose(f); + } + } else { + fprintf(stderr, "Reading tables from file %s\n", filename); + fread(buf, size, 1, f); + fclose(f); + } + + return 0; +} + +int main(void) { + int64_t size; + + srand(time(NULL)); + + nissy_setlogger(log_stderr); + size = nissy_datasize("h48", OPTIONS); + if (size == -1) { + printf("h48 stats: error in datasize\n"); + return 1; + } + + if (getdata(size) != 0) { + printf("Error getting table, stopping\n"); + free(buf); + return 1; + } + + timerun(run, "small solver benchmark"); + + free(buf); + return 0; +} -- cgit v1.3