From 7defd8041e6050a9adf7927b43fd249d75d6389f Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Tue, 4 Mar 2025 08:24:39 +0100 Subject: Begin work for coordinate solver --- src/solvers/coord/common.h | 20 +++++ src/solvers/coord/coord_solve.h | 3 + src/solvers/coord/coord_types_macros.h | 13 ++++ src/solvers/coord/eo.h | 33 ++++++++ src/solvers/coord/gendata_coord.h | 134 +++++++++++++++++++++++++++++++++ 5 files changed, 203 insertions(+) create mode 100644 src/solvers/coord/common.h create mode 100644 src/solvers/coord/coord_solve.h create mode 100644 src/solvers/coord/coord_types_macros.h create mode 100644 src/solvers/coord/eo.h create mode 100644 src/solvers/coord/gendata_coord.h (limited to 'src/solvers/coord') diff --git a/src/solvers/coord/common.h b/src/solvers/coord/common.h new file mode 100644 index 0000000..b54e5e2 --- /dev/null +++ b/src/solvers/coord/common.h @@ -0,0 +1,20 @@ +#include "eo.h" + +coord_t *all_coordinates[] = { + &coordinate_eo, + NULL +}; + +STATIC void append_coord_name(const coord_t *, char *); + +STATIC void +append_coord_name(const coord_t *coord, char *str) +{ + int i, j; + + i = 0; + j = strlen(str); + while (coord->name[i]) str[j++] = coord->name[i++]; + + str[j] = '\0'; +} diff --git a/src/solvers/coord/coord_solve.h b/src/solvers/coord/coord_solve.h new file mode 100644 index 0000000..1d7c036 --- /dev/null +++ b/src/solvers/coord/coord_solve.h @@ -0,0 +1,3 @@ +#include "coord_types_macros.h" +#include "common.h" +#include "gendata_coord.h" diff --git a/src/solvers/coord/coord_types_macros.h b/src/solvers/coord/coord_types_macros.h new file mode 100644 index 0000000..4f2877c --- /dev/null +++ b/src/solvers/coord/coord_types_macros.h @@ -0,0 +1,13 @@ +#define COORD_INDEX(i) ((i)/2) +#define COORD_SHIFT(i) (UINT8_C(4) * (uint8_t)((i) % 2)) +#define COORD_MASK(i) (UINT8_C(0xF) << COORD_SHIFT(i)) + +typedef struct { + char name[255]; + uint64_t (*coord)(cube_t, const void *); + cube_t (*cube)(uint64_t, const void *); + size_t (*gendata)(void *); + uint64_t max; + uint32_t moves_mask; + uint64_t trans_mask; +} coord_t; diff --git a/src/solvers/coord/eo.h b/src/solvers/coord/eo.h new file mode 100644 index 0000000..d6604d9 --- /dev/null +++ b/src/solvers/coord/eo.h @@ -0,0 +1,33 @@ +STATIC uint64_t coordinate_eo_coord(cube_t, const void *); +STATIC cube_t coordinate_eo_cube(uint64_t, const void *); +STATIC uint64_t coordinate_eo_gendata(void *); + +STATIC coord_t coordinate_eo = { + .name = "EO", + .coord = &coordinate_eo_coord, + .cube = &coordinate_eo_cube, + .gendata = coordinate_eo_gendata, + .max = POW_2_11, + .trans_mask = TM_ALLTRANS, + .moves_mask = MM_ALLMOVES, +}; + +STATIC uint64_t +coordinate_eo_coord(cube_t c, const void *data) +{ + return (uint64_t)coord_eo(c); +} + +STATIC cube_t +coordinate_eo_cube(uint64_t c, const void *data) +{ + cube_t cube = SOLVED_CUBE; + set_eo(&cube, (int64_t)c); + return cube; +} + +STATIC size_t +coordinate_eo_gendata(void *data) +{ + return 0; +} diff --git a/src/solvers/coord/gendata_coord.h b/src/solvers/coord/gendata_coord.h new file mode 100644 index 0000000..b3932cd --- /dev/null +++ b/src/solvers/coord/gendata_coord.h @@ -0,0 +1,134 @@ +STATIC size_t gendata_coordinate(const coord_t *, void *); +STATIC size_t gendata_coordinate_name(const char *, void *); +STATIC tableinfo_t genptable_coordinate(const coord_t *, const void *, uint8_t *); +STATIC uint8_t get_coord_pval(const coord_t *, const uint8_t *, uint64_t); +STATIC void set_coord_pval(const coord_t *, uint8_t *, uint64_t, uint8_t); + +STATIC size_t +gendata_coordinate_name(const char *name, void *buf) +{ + int i; + + for (i = 0; all_coordinates[i] != NULL; i++) + if (strcmp(all_coordinates[i]->name, name) == 0) + return gendata_coordinate(all_coordinates[i], buf); + + LOG("Cannot generate data for coordinate '%s': not found\n", name); + return 0; +} + +STATIC size_t +gendata_coordinate(const coord_t *coord, void *buf) +{ + uint64_t coord_dsize, tablesize, ninfo; + void *pruningbuf, *coord_data; + uint8_t *table; + tableinfo_t coord_data_info, pruning_info; + + coord_data = buf == NULL ? NULL : ((uint8_t *)buf) + INFOSIZE; + coord_dsize = coord->gendata(coord_data); + ninfo = coord_dsize == 0 ? 1 : 2; + tablesize = DIV_ROUND_UP(coord->max, 2); + + if (buf == NULL) + goto gendata_coordinate_return_size; + + if (ninfo == 2) { + coord_data_info = (tableinfo_t) { + .solver = "coord helper table for ", + .type = TABLETYPE_SPECIAL, + .infosize = INFOSIZE, + .fullsize = INFOSIZE + coord_dsize, + .hash = 0, /* TODO */ + .next = INFOSIZE + coord_dsize, + + /* Unknown / non-applicable values */ + .entries = 0, + .classes = 0, + .bits = 0, + .base = 0, + .maxvalue = 0, + }; + + append_coord_name(coord, coord_data_info.solver); + + writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf); + + pruningbuf = ((uint8_t *)buf) + INFOSIZE + coord_dsize; + } else { + pruningbuf = buf; + } + + table = ((uint8_t *)pruningbuf) + INFOSIZE; + pruning_info = genptable_coordinate(coord, coord_data, table); + writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf); + +gendata_coordinate_return_size: + return ninfo * INFOSIZE + coord_dsize + tablesize; +} + +STATIC tableinfo_t +genptable_coordinate(const coord_t *coord, const void *data, uint8_t *table) +{ + uint64_t tablesize, i, j, d, tot; + tableinfo_t info; + uint8_t m; + cube_t c, cc; + + tablesize = DIV_ROUND_UP(coord->max, 2); + + memset(table, 0xFF, tablesize); + + info = (tableinfo_t) { + .solver = "coordinate solver for ", + .type = TABLETYPE_PRUNING, + .infosize = INFOSIZE, + .fullsize = INFOSIZE + tablesize, + .hash = 0, /* TODO */ + .entries = coord->max, + .classes = 0, + .bits = 4, + .base = 0, + .maxvalue = 0, + .next = 0 + }; + + memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); + append_coord_name(coord, info.solver); + + i = coord->coord(SOLVED_CUBE, data); + set_coord_pval(coord, table, i, 0); + info.distribution[0] = 1; + for (d = 1, tot = 1; tot < coord->max; d++) { + for (i = 0; i < coord->max; i++) { + if (get_coord_pval(coord, table, i) == d-1) { + c = coord->cube(i, data); + for (m = 0; m < 18; m++) { + cc = move(c, m); + j = coord->coord(cc, data); + if (get_coord_pval(coord, table, j) > d) { + set_coord_pval(coord, table, j, d); + tot++; + info.distribution[d]++; + } + } + } + } + } + info.maxvalue = d-1; + + return info; +} + +STATIC uint8_t +get_coord_pval(const coord_t *coord, const uint8_t *table, uint64_t i) +{ + return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i); +} + +STATIC void +set_coord_pval(const coord_t *coord, uint8_t *table, uint64_t i, uint8_t val) +{ + table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i))) + | (val << COORD_SHIFT(i)); +} -- cgit v1.3