diff options
| author | Sebastiano Tronto <sebastiano@tronto.net> | 2024-08-25 14:35:45 +0200 |
|---|---|---|
| committer | Sebastiano Tronto <sebastiano@tronto.net> | 2024-08-25 14:35:45 +0200 |
| commit | cdf311166da0171c2787fb1745072cd14569ff4f (patch) | |
| tree | 82db218e948bff91c1dc57a7ac25d8b5d944ec12 | |
| parent | dd44adceed44bec3dc313b77ec6f69123dc59016 (diff) | |
| download | nissy-core-cdf311166da0171c2787fb1745072cd14569ff4f.tar.gz nissy-core-cdf311166da0171c2787fb1745072cd14569ff4f.zip | |
Refactor table generation
| -rw-r--r-- | src/nissy.c | 63 | ||||
| -rw-r--r-- | src/solvers/h48/gendata_full.h | 196 | ||||
| -rw-r--r-- | src/solvers/h48/solve.h | 11 | ||||
| -rw-r--r-- | test/112_gendata_h48/gendata_h48_tests.c | 51 | ||||
| -rw-r--r-- | test/113_gen_h48short/gen_h48short.c | 5 | ||||
| -rw-r--r-- | tools/001_gendata_h48/gendata_h48.c | 4 |
6 files changed, 201 insertions, 129 deletions
diff --git a/src/nissy.c b/src/nissy.c index fac7a20..5641dd9 100644 --- a/src/nissy.c +++ b/src/nissy.c | |||
| @@ -10,6 +10,7 @@ | |||
| 10 | 10 | ||
| 11 | #include "nissy.h" | 11 | #include "nissy.h" |
| 12 | 12 | ||
| 13 | _static int parse_h48_options(const char *, uint8_t *, uint8_t *, uint8_t *); | ||
| 13 | _static int64_t write_result(cube_t, char [static 22]); | 14 | _static int64_t write_result(cube_t, char [static 22]); |
| 14 | 15 | ||
| 15 | /* TODO: add option to get DR, maybe C-only, E-only, eo... */ | 16 | /* TODO: add option to get DR, maybe C-only, E-only, eo... */ |
| @@ -22,6 +23,36 @@ struct { | |||
| 22 | GETCUBE_OPTIONS(NULL, NULL) | 23 | GETCUBE_OPTIONS(NULL, NULL) |
| 23 | }; | 24 | }; |
| 24 | 25 | ||
| 26 | _static int | ||
| 27 | parse_h48_options(const char *buf, uint8_t *h, uint8_t *k, uint8_t *maxdepth) | ||
| 28 | { | ||
| 29 | int i; | ||
| 30 | |||
| 31 | /* TODO temporarily, options are in the form "h;k;maxdepth" */ | ||
| 32 | if (h != NULL) | ||
| 33 | *h = atoi(buf); | ||
| 34 | for (i = 0; buf[i] != ';'; i++) | ||
| 35 | if (buf[i] == 0) | ||
| 36 | goto parse_h48_options_error; | ||
| 37 | if (k != NULL) | ||
| 38 | *k = atoi(&buf[i+1]); | ||
| 39 | for (i = i+1; buf[i] != ';'; i++) | ||
| 40 | if (buf[i] == 0) | ||
| 41 | goto parse_h48_options_error; | ||
| 42 | if (maxdepth != NULL) | ||
| 43 | *maxdepth = atoi(&buf[i+1]); | ||
| 44 | |||
| 45 | return (*h <= 11 && (*k == 2 || *k == 4) && *maxdepth <= 20) ? 0 : 1; | ||
| 46 | |||
| 47 | parse_h48_options_error: | ||
| 48 | *h = 0; | ||
| 49 | *k = 0; | ||
| 50 | *maxdepth = 0; | ||
| 51 | LOG("Error parsing options: must be in \"h;k;maxdepth\" format " | ||
| 52 | " (instead it was \"%s\")\n", buf); | ||
| 53 | return -1; | ||
| 54 | } | ||
| 55 | |||
| 25 | _static int64_t | 56 | _static int64_t |
| 26 | write_result(cube_t cube, char result[static 22]) | 57 | write_result(cube_t cube, char result[static 22]) |
| 27 | { | 58 | { |
| @@ -163,19 +194,19 @@ nissy_gendata( | |||
| 163 | void *data | 194 | void *data |
| 164 | ) | 195 | ) |
| 165 | { | 196 | { |
| 197 | int p; | ||
| 166 | int64_t ret; | 198 | int64_t ret; |
| 167 | uint8_t i; | ||
| 168 | gendata_h48_arg_t arg; | 199 | gendata_h48_arg_t arg; |
| 169 | 200 | ||
| 170 | arg.buf = data; | 201 | arg.buf = data; |
| 171 | if (!strcmp(solver, "h48")) { | 202 | if (!strcmp(solver, "h48")) { |
| 172 | /* options are in the form "h;k;maxdepth" */ | 203 | p = parse_h48_options(options, &arg.h, &arg.k, &arg.maxdepth); |
| 173 | arg.h = atoi(options); | 204 | if (p != 0) { |
| 174 | for (i = 0; options[i] != ';'; i++) ; | 205 | LOG("gendata: ould not parse options\n"); |
| 175 | arg.k = atoi(&options[i+1]); | 206 | ret = -1; |
| 176 | for (i = i+1; options[i] != ';'; i++) ; | 207 | } else { |
| 177 | arg.maxdepth = atoi(&options[i+1]); | 208 | ret = gendata_h48(&arg); |
| 178 | ret = gendata_h48(&arg); | 209 | } |
| 179 | } else if (!strcmp(solver, "h48stats")) { | 210 | } else if (!strcmp(solver, "h48stats")) { |
| 180 | arg.h = 0; | 211 | arg.h = 0; |
| 181 | arg.k = 4; | 212 | arg.k = 4; |
| @@ -204,8 +235,9 @@ nissy_solve( | |||
| 204 | ) | 235 | ) |
| 205 | { | 236 | { |
| 206 | cube_t c; | 237 | cube_t c; |
| 238 | int p; | ||
| 207 | int64_t ret; | 239 | int64_t ret; |
| 208 | int h; | 240 | uint8_t h, k; |
| 209 | 241 | ||
| 210 | c = readcube_B32(cube); | 242 | c = readcube_B32(cube); |
| 211 | 243 | ||
| @@ -241,11 +273,14 @@ nissy_solve( | |||
| 241 | 273 | ||
| 242 | /* TODO define and use solve_options_t */ | 274 | /* TODO define and use solve_options_t */ |
| 243 | if (!strcmp(solver, "h48")) { | 275 | if (!strcmp(solver, "h48")) { |
| 244 | h = atoi(options); /* TODO: better parsing */ | 276 | p = parse_h48_options(options, &h, &k, NULL); |
| 245 | ret = solve_h48( | 277 | if (p != 0) { |
| 246 | c, minmoves, maxmoves, maxsolutions, | 278 | LOG("gendata: could not parse options\n"); |
| 247 | (uint8_t)h, data, solutions); | 279 | ret = -1; |
| 248 | ret = -1; | 280 | } else { |
| 281 | ret = solve_h48(c, minmoves, maxmoves, maxsolutions, | ||
| 282 | h, k, data, solutions); | ||
| 283 | } | ||
| 249 | } else if (!strcmp(solver, "h48stats")) { | 284 | } else if (!strcmp(solver, "h48stats")) { |
| 250 | ret = solve_h48stats(c, maxmoves, data, solutions); | 285 | ret = solve_h48stats(c, maxmoves, data, solutions); |
| 251 | } else if (!strcmp(solver, "simple")) { | 286 | } else if (!strcmp(solver, "simple")) { |
diff --git a/src/solvers/h48/gendata_full.h b/src/solvers/h48/gendata_full.h index be234d9..2b1347f 100644 --- a/src/solvers/h48/gendata_full.h +++ b/src/solvers/h48/gendata_full.h | |||
| @@ -1,10 +1,11 @@ | |||
| 1 | #define ESEP_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) | 1 | #define H48_COORDMAX_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) |
| 2 | #define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h)) | 2 | #define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (size_t)(h)) |
| 3 | #define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k))) | 3 | #define H48_TABLESIZE(h, k) (H48_COORDMAX((h)) / ((size_t)8 / (size_t)(k))) |
| 4 | 4 | ||
| 5 | #define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8)) | 5 | #define H48_COEFF(k) (UINT32_C(32) / (uint32_t)(k)) |
| 6 | #define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8))) | 6 | #define H48_INDEX(i, k) ((uint32_t)(i) / H48_COEFF(k)) |
| 7 | #define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i)) | 7 | #define H48_SHIFT(i, k) ((uint32_t)(k) * ((uint32_t)(i) % H48_COEFF(k))) |
| 8 | #define H48_MASK(i, k) ((_bit_u32(k) - (uint32_t)(1)) << H48_SHIFT(i, k)) | ||
| 8 | 9 | ||
| 9 | #define MAXLEN 20 | 10 | #define MAXLEN 20 |
| 10 | 11 | ||
| @@ -31,7 +32,12 @@ typedef struct { | |||
| 31 | uint8_t h; | 32 | uint8_t h; |
| 32 | uint8_t k; | 33 | uint8_t k; |
| 33 | uint8_t maxdepth; | 34 | uint8_t maxdepth; |
| 34 | void * buf; | 35 | void *buf; |
| 36 | uint32_t *info; | ||
| 37 | uint32_t *cocsepdata; | ||
| 38 | uint32_t *h48data; | ||
| 39 | uint64_t selfsim[COCSEP_CLASSES]; | ||
| 40 | cube_t crep[COCSEP_CLASSES]; | ||
| 35 | } gendata_h48_arg_t; | 41 | } gendata_h48_arg_t; |
| 36 | 42 | ||
| 37 | typedef struct { | 43 | typedef struct { |
| @@ -51,18 +57,18 @@ typedef struct { | |||
| 51 | cube_t *crep; | 57 | cube_t *crep; |
| 52 | } bfsarg_esep_t; | 58 | } bfsarg_esep_t; |
| 53 | 59 | ||
| 54 | _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t); | 60 | _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t, uint8_t); |
| 55 | _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t); | 61 | _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t, uint8_t); |
| 56 | 62 | ||
| 57 | _static uint64_t gen_h48short(gendata_h48short_arg_t *); | 63 | _static uint64_t gen_h48short(gendata_h48short_arg_t *); |
| 58 | _static size_t gendata_h48(gendata_h48_arg_t *); | 64 | _static size_t gendata_h48(gendata_h48_arg_t *); |
| 59 | _static size_t gendata_h48h0k4(void *, uint8_t); | 65 | _static size_t gendata_h48h0k4(gendata_h48_arg_t *); |
| 60 | _static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); | 66 | _static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *); |
| 61 | _static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); | 67 | _static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *); |
| 62 | _static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); | 68 | _static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *); |
| 63 | _static size_t gendata_h48k2(void *, uint8_t, uint8_t); | 69 | _static size_t gendata_h48k2(gendata_h48_arg_t *); |
| 64 | 70 | ||
| 65 | _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *); | 71 | _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint32_t *); |
| 66 | 72 | ||
| 67 | _static uint64_t | 73 | _static uint64_t |
| 68 | gen_h48short(gendata_h48short_arg_t *arg) | 74 | gen_h48short(gendata_h48short_arg_t *arg) |
| @@ -108,14 +114,32 @@ gen_h48short(gendata_h48short_arg_t *arg) | |||
| 108 | _static size_t | 114 | _static size_t |
| 109 | gendata_h48(gendata_h48_arg_t *arg) | 115 | gendata_h48(gendata_h48_arg_t *arg) |
| 110 | { | 116 | { |
| 117 | static const size_t infosize = 88; /* TODO: change to e.g. 1024 */ | ||
| 118 | |||
| 119 | size_t cocsepsize, h48size; | ||
| 120 | |||
| 121 | /* TODO: move info at the start */ | ||
| 122 | arg->cocsepdata = (uint32_t *)arg->buf; | ||
| 123 | cocsepsize = gendata_cocsep( | ||
| 124 | (void *)arg->cocsepdata, arg->selfsim, arg->crep); | ||
| 125 | arg->h48data = arg->cocsepdata + (cocsepsize / sizeof(uint32_t)); | ||
| 126 | arg->info = arg->h48data + | ||
| 127 | (H48_TABLESIZE(arg->h, arg->k) / sizeof(uint32_t)); | ||
| 128 | |||
| 129 | if (arg->buf != NULL) | ||
| 130 | memset(arg->h48data, 0xFF, H48_TABLESIZE(arg->h, arg->k)); | ||
| 131 | |||
| 111 | if (arg->h == 0 && arg->k == 4) { | 132 | if (arg->h == 0 && arg->k == 4) { |
| 112 | return gendata_h48h0k4(arg->buf, arg->maxdepth); | 133 | h48size = gendata_h48h0k4(arg); |
| 113 | } else if (arg->k == 2) { | 134 | } else if (arg->k == 2) { |
| 114 | return gendata_h48k2(arg->buf, arg->h, arg->maxdepth); | 135 | h48size = gendata_h48k2(arg); |
| 136 | } else { | ||
| 137 | h48size = 0; | ||
| 138 | LOG("Cannot generate data for h = %" PRIu8 " and k = %" PRIu8 | ||
| 139 | " (not implemented yet)\n", arg->h, arg->k); | ||
| 115 | } | 140 | } |
| 116 | 141 | ||
| 117 | LOG("Cannot generate data for h = %" PRIu8 " and k = %" PRIu8 | 142 | return infosize + cocsepsize + h48size; |
| 118 | " (not implemented yet)\n", arg->h, arg->k); | ||
| 119 | } | 143 | } |
| 120 | 144 | ||
| 121 | /* | 145 | /* |
| @@ -123,59 +147,61 @@ TODO description | |||
| 123 | generating fixed table with h=0, k=4 | 147 | generating fixed table with h=0, k=4 |
| 124 | */ | 148 | */ |
| 125 | _static size_t | 149 | _static size_t |
| 126 | gendata_h48h0k4(void *buf, uint8_t maxdepth) | 150 | gendata_h48h0k4(gendata_h48_arg_t *arg) |
| 127 | { | 151 | { |
| 128 | uint32_t j, *buf32, *info, *cocsepdata; | 152 | uint32_t j; |
| 129 | bfsarg_esep_t arg; | 153 | bfsarg_esep_t bfsarg; |
| 130 | int64_t sc, cc, esep_max; | 154 | int64_t sc, cc, esep_max; |
| 155 | /* | ||
| 131 | uint64_t selfsim[COCSEP_CLASSES]; | 156 | uint64_t selfsim[COCSEP_CLASSES]; |
| 132 | cube_t crep[COCSEP_CLASSES]; | 157 | cube_t crep[COCSEP_CLASSES]; |
| 133 | size_t cocsepsize, infosize; | 158 | size_t cocsepsize, infosize; |
| 159 | */ | ||
| 134 | 160 | ||
| 135 | if (buf == NULL) | 161 | if (arg->buf == NULL) |
| 136 | goto gendata_h48h0k4_return_size; | 162 | goto gendata_h48h0k4_return_size; |
| 137 | 163 | /* | |
| 138 | /* TODO: move info at start of tables (all tables!) */ | ||
| 139 | cocsepsize = gendata_cocsep(buf, selfsim, crep); | 164 | cocsepsize = gendata_cocsep(buf, selfsim, crep); |
| 140 | infosize = 88; | 165 | infosize = 88; |
| 141 | 166 | ||
| 142 | esep_max = (int64_t)ESEP_MAX(0); | ||
| 143 | cocsepdata = (uint32_t *)buf; | 167 | cocsepdata = (uint32_t *)buf; |
| 144 | buf32 = cocsepdata + cocsepsize / 4; | 168 | buf32 = cocsepdata + cocsepsize / 4; |
| 145 | info = buf32 + (ESEP_TABLESIZE(0, 4) / sizeof(uint32_t)); | 169 | info = buf32 + (H48_TABLESIZE(0, 4) / sizeof(uint32_t)); |
| 146 | memset(buf32, 0xFF, ESEP_TABLESIZE(0, 4)); | 170 | memset(buf32, 0xFF, H48_TABLESIZE(0, 4)); |
| 171 | */ | ||
| 147 | 172 | ||
| 148 | sc = coord_h48(solved, cocsepdata, 0); | 173 | esep_max = (int64_t)H48_COORDMAX(0); |
| 149 | set_esep_pval(buf32, sc, 0); | 174 | sc = coord_h48(solved, arg->cocsepdata, 0); |
| 150 | info[1] = 1; | 175 | set_esep_pval(arg->h48data, sc, 4, 0); |
| 151 | arg = (bfsarg_esep_t) { | 176 | arg->info[1] = 1; |
| 152 | .cocsepdata = cocsepdata, | 177 | bfsarg = (bfsarg_esep_t) { |
| 153 | .buf32 = buf32, | 178 | .cocsepdata = arg->cocsepdata, |
| 154 | .selfsim = selfsim, | 179 | .buf32 = arg->h48data, |
| 155 | .crep = crep | 180 | .selfsim = arg->selfsim, |
| 181 | .crep = arg->crep | ||
| 156 | }; | 182 | }; |
| 157 | for ( | 183 | for ( |
| 158 | arg.done = 1, arg.depth = 1, cc = 0; | 184 | bfsarg.done = 1, bfsarg.depth = 1, cc = 0; |
| 159 | arg.done < esep_max && arg.depth <= maxdepth; | 185 | bfsarg.done < esep_max && bfsarg.depth <= arg->maxdepth; |
| 160 | arg.depth++ | 186 | bfsarg.depth++ |
| 161 | ) { | 187 | ) { |
| 162 | LOG("esep: generating depth %" PRIu8 "\n", arg.depth); | 188 | LOG("esep: generating depth %" PRIu8 "\n", bfsarg.depth); |
| 163 | cc = gendata_h48h0k4_bfs(&arg); | 189 | cc = gendata_h48h0k4_bfs(&bfsarg); |
| 164 | arg.done += cc; | 190 | bfsarg.done += cc; |
| 165 | info[arg.depth+1] = cc; | 191 | arg->info[bfsarg.depth+1] = cc; |
| 166 | LOG("found %" PRId64 "\n", cc); | 192 | LOG("found %" PRId64 "\n", cc); |
| 167 | } | 193 | } |
| 168 | 194 | ||
| 169 | info[0] = arg.depth-1; | 195 | arg->info[0] = bfsarg.depth-1; |
| 170 | 196 | ||
| 171 | LOG("h48 pruning table computed\n"); | 197 | LOG("h48 pruning table computed\n"); |
| 172 | LOG("Maximum pruning value: %" PRIu32 "\n", info[0]); | 198 | LOG("Maximum pruning value: %" PRIu32 "\n", arg->info[0]); |
| 173 | LOG("Pruning value distribution:\n"); | 199 | LOG("Pruning value distribution:\n"); |
| 174 | for (j = 0; j <= info[0]; j++) | 200 | for (j = 0; j <= arg->info[0]; j++) |
| 175 | LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]); | 201 | LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, arg->info[j+1]); |
| 176 | 202 | ||
| 177 | gendata_h48h0k4_return_size: | 203 | gendata_h48h0k4_return_size: |
| 178 | return cocsepsize + ESEP_TABLESIZE(0, 4) + infosize; | 204 | return H48_TABLESIZE(0, 4); |
| 179 | } | 205 | } |
| 180 | 206 | ||
| 181 | _static int64_t | 207 | _static int64_t |
| @@ -197,20 +223,20 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg) | |||
| 197 | int64_t i, j, k; | 223 | int64_t i, j, k; |
| 198 | cube_t cube, moved; | 224 | cube_t cube, moved; |
| 199 | 225 | ||
| 200 | for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { | 226 | for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { |
| 201 | c = get_esep_pval(arg->buf32, i); | 227 | c = get_esep_pval(arg->buf32, i, 4); |
| 202 | if (c != arg->depth - 1) | 228 | if (c != arg->depth - 1) |
| 203 | continue; | 229 | continue; |
| 204 | cube = invcoord_h48(i, arg->crep, 0); | 230 | cube = invcoord_h48(i, arg->crep, 0); |
| 205 | for (m = 0; m < 18; m++) { | 231 | for (m = 0; m < 18; m++) { |
| 206 | moved = move(cube, m); | 232 | moved = move(cube, m); |
| 207 | j = coord_h48(moved, arg->cocsepdata, 0); | 233 | j = coord_h48(moved, arg->cocsepdata, 0); |
| 208 | if (get_esep_pval(arg->buf32, j) <= arg->depth) | 234 | if (get_esep_pval(arg->buf32, j, 4) <= arg->depth) |
| 209 | continue; | 235 | continue; |
| 210 | _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, | 236 | _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0, |
| 211 | k = coord_h48(moved, arg->cocsepdata, 0); | 237 | k = coord_h48(moved, arg->cocsepdata, 0); |
| 212 | x = get_esep_pval(arg->buf32, k); | 238 | x = get_esep_pval(arg->buf32, k, 4); |
| 213 | set_esep_pval(arg->buf32, k, arg->depth); | 239 | set_esep_pval(arg->buf32, k, 4, arg->depth); |
| 214 | cc += x != arg->depth; | 240 | cc += x != arg->depth; |
| 215 | ) | 241 | ) |
| 216 | } | 242 | } |
| @@ -227,21 +253,21 @@ gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) | |||
| 227 | int64_t i, j; | 253 | int64_t i, j; |
| 228 | cube_t cube, moved; | 254 | cube_t cube, moved; |
| 229 | 255 | ||
| 230 | for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) { | 256 | for (i = 0, cc = 0; i < (int64_t)H48_COORDMAX(0); i++) { |
| 231 | c = get_esep_pval(arg->buf32, i); | 257 | c = get_esep_pval(arg->buf32, i, 4); |
| 232 | if (c != 0xF) | 258 | if (c != 0xF) |
| 233 | continue; | 259 | continue; |
| 234 | cube = invcoord_h48(i, arg->crep, 0); | 260 | cube = invcoord_h48(i, arg->crep, 0); |
| 235 | for (m = 0; m < 18; m++) { | 261 | for (m = 0; m < 18; m++) { |
| 236 | moved = move(cube, m); | 262 | moved = move(cube, m); |
| 237 | j = coord_h48(moved, arg->cocsepdata, 0); | 263 | j = coord_h48(moved, arg->cocsepdata, 0); |
| 238 | x = get_esep_pval(arg->buf32, j); | 264 | x = get_esep_pval(arg->buf32, j, 4); |
| 239 | if (x >= arg->depth) | 265 | if (x >= arg->depth) |
| 240 | continue; | 266 | continue; |
| 241 | _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, | 267 | _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0, |
| 242 | j = coord_h48(cube, arg->cocsepdata, 0); | 268 | j = coord_h48(cube, arg->cocsepdata, 0); |
| 243 | x = get_esep_pval(arg->buf32, j); | 269 | x = get_esep_pval(arg->buf32, j, 4); |
| 244 | set_esep_pval(arg->buf32, j, arg->depth); | 270 | set_esep_pval(arg->buf32, j, 4, arg->depth); |
| 245 | cc += x == 0xF; | 271 | cc += x == 0xF; |
| 246 | ) | 272 | ) |
| 247 | break; /* Enough to find one, skip the rest */ | 273 | break; /* Enough to find one, skip the rest */ |
| @@ -252,11 +278,12 @@ gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg) | |||
| 252 | } | 278 | } |
| 253 | 279 | ||
| 254 | _static size_t | 280 | _static size_t |
| 255 | gendata_h48k2(void *buf, uint8_t h, uint8_t maxdepth) | 281 | gendata_h48k2(gendata_h48_arg_t *arg) |
| 256 | { | 282 | { |
| 257 | static uint64_t capacity = 10000019; /* First prime after 1e8 */ | 283 | static const uint8_t shortdepth = 8; |
| 258 | static uint64_t randomizer = 10000079; /* Second prime after 1e8 */ | 284 | static const uint64_t capacity = 10000019; |
| 259 | static uint8_t base[] = { | 285 | static const uint64_t randomizer = 10000079; |
| 286 | static const uint8_t base[] = { | ||
| 260 | [0] = 8, | 287 | [0] = 8, |
| 261 | [1] = 8, | 288 | [1] = 8, |
| 262 | [2] = 8, | 289 | [2] = 8, |
| @@ -272,58 +299,53 @@ gendata_h48k2(void *buf, uint8_t h, uint8_t maxdepth) | |||
| 272 | }; | 299 | }; |
| 273 | 300 | ||
| 274 | uint64_t nshort; | 301 | uint64_t nshort; |
| 275 | uint32_t *buf32, *info, *cocsepdata; | 302 | h48map_t shortcubes; |
| 276 | h48map_t depth8cubes; | ||
| 277 | gendata_h48short_arg_t shortarg; | 303 | gendata_h48short_arg_t shortarg; |
| 278 | uint64_t selfsim[COCSEP_CLASSES]; | ||
| 279 | cube_t crep[COCSEP_CLASSES]; | ||
| 280 | size_t cocsepsize, infosize; | ||
| 281 | 304 | ||
| 282 | DBG_ASSERT(base[h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); | 305 | DBG_ASSERT(base[arg->h] == 8, 0, "Only implemented for h <= 3 (base 8)\n"); |
| 283 | 306 | ||
| 284 | if (buf == NULL) | 307 | if (arg->buf == NULL) |
| 285 | goto gendata_h48k2_return_size; | 308 | goto gendata_h48k2_return_size; |
| 286 | 309 | ||
| 287 | cocsepdata = (uint32_t *)buf; | 310 | LOG("Computing depth <=%" PRIu8 "\n", shortdepth) |
| 288 | cocsepsize = gendata_cocsep(buf, selfsim, crep); | 311 | h48map_create(&shortcubes, capacity, randomizer); |
| 289 | infosize = 88; | ||
| 290 | |||
| 291 | h48map_create(&depth8cubes, capacity, randomizer); | ||
| 292 | shortarg = (gendata_h48short_arg_t) { | 312 | shortarg = (gendata_h48short_arg_t) { |
| 293 | .maxdepth = 8, | 313 | .maxdepth = shortdepth, |
| 294 | .cocsepdata = cocsepdata, | 314 | .cocsepdata = arg->cocsepdata, |
| 295 | .crep = crep, | 315 | .crep = arg->crep, |
| 296 | .selfsim = selfsim, | 316 | .selfsim = arg->selfsim, |
| 297 | .map = &depth8cubes | 317 | .map = &shortcubes |
| 298 | }; | 318 | }; |
| 299 | |||
| 300 | nshort = gen_h48short(&shortarg); | 319 | nshort = gen_h48short(&shortarg); |
| 301 | LOG("%" PRIu64 "\n", nshort); | 320 | LOG("Found %" PRIu64 "\n", nshort); |
| 321 | |||
| 322 | /* TODO: loop over map, set all found to 0, do 2 moves each */ | ||
| 323 | LOG("The rest is not implemented yet\n"); | ||
| 302 | 324 | ||
| 303 | h48map_destroy(&depth8cubes); | 325 | h48map_destroy(&shortcubes); |
| 304 | 326 | ||
| 305 | gendata_h48k2_return_size: | 327 | gendata_h48k2_return_size: |
| 306 | return cocsepsize + ESEP_TABLESIZE(h, 2) + infosize; | 328 | return H48_TABLESIZE(arg->h, 2); |
| 307 | } | 329 | } |
| 308 | 330 | ||
| 309 | _static_inline uint8_t | 331 | _static_inline uint8_t |
| 310 | get_esep_pval(const uint32_t *buf32, int64_t i) | 332 | get_esep_pval(const uint32_t *buf32, int64_t i, uint8_t k) |
| 311 | { | 333 | { |
| 312 | return (buf32[ESEP_IND(i)] & ESEP_MASK(i)) >> ESEP_SHIFT(i); | 334 | return (buf32[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k); |
| 313 | } | 335 | } |
| 314 | 336 | ||
| 315 | _static_inline void | 337 | _static_inline void |
| 316 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) | 338 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t k, uint8_t val) |
| 317 | { | 339 | { |
| 318 | buf32[ESEP_IND(i)] = | 340 | buf32[H48_INDEX(i, k)] = (buf32[H48_INDEX(i, k)] & (~H48_MASK(i, k))) |
| 319 | (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i)); | 341 | | (val << H48_SHIFT(i, k)); |
| 320 | } | 342 | } |
| 321 | 343 | ||
| 322 | _static_inline int8_t | 344 | _static_inline int8_t |
| 323 | get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data) | 345 | get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint32_t *h48data) |
| 324 | { | 346 | { |
| 325 | int64_t coord; | 347 | int64_t coord; |
| 326 | 348 | ||
| 327 | coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); | 349 | coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h); |
| 328 | return get_esep_pval(h48data, coord); | 350 | return get_esep_pval(h48data, coord, k); |
| 329 | } | 351 | } |
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 8531a40..0843792 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h | |||
| @@ -7,6 +7,7 @@ typedef struct { | |||
| 7 | int64_t *nsols; | 7 | int64_t *nsols; |
| 8 | int64_t maxsolutions; | 8 | int64_t maxsolutions; |
| 9 | uint8_t h; | 9 | uint8_t h; |
| 10 | uint8_t k; | ||
| 10 | uint32_t *cocsepdata; | 11 | uint32_t *cocsepdata; |
| 11 | uint32_t *h48data; | 12 | uint32_t *h48data; |
| 12 | char **nextsol; | 13 | char **nextsol; |
| @@ -26,7 +27,7 @@ _static void solve_h48_appendsolution(dfsarg_solveh48_t *); | |||
| 26 | _static_inline bool solve_h48_stop(dfsarg_solveh48_t *); | 27 | _static_inline bool solve_h48_stop(dfsarg_solveh48_t *); |
| 27 | _static int64_t solve_h48_dfs(dfsarg_solveh48_t *); | 28 | _static int64_t solve_h48_dfs(dfsarg_solveh48_t *); |
| 28 | _static int64_t solve_h48( | 29 | _static int64_t solve_h48( |
| 29 | cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *); | 30 | cube_t, int8_t, int8_t, int8_t, uint8_t, uint8_t, const void *, char *); |
| 30 | 31 | ||
| 31 | _static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); | 32 | _static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *); |
| 32 | _static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); | 33 | _static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]); |
| @@ -59,12 +60,12 @@ solve_h48_stop(dfsarg_solveh48_t *arg) | |||
| 59 | return true; | 60 | return true; |
| 60 | 61 | ||
| 61 | /* | 62 | /* |
| 62 | bound = get_h48_bound(arg->cube, data, arg->h, arg->h48data); | 63 | bound = get_h48_bound(arg->cube, data, arg->h, arg->k, arg->h48data); |
| 63 | LOG("Using pval %" PRId8 "\n", bound); | 64 | LOG("Using pval %" PRId8 "\n", bound); |
| 64 | if (bound + arg->nmoves > arg->depth) | 65 | if (bound + arg->nmoves > arg->depth) |
| 65 | return true; | 66 | return true; |
| 66 | 67 | ||
| 67 | bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->h48data); | 68 | bound = get_h48_bound(arg->inverse, data_inv, arg->h, arg->k, arg->h48data); |
| 68 | if (bound + arg->nmoves > arg->depth) | 69 | if (bound + arg->nmoves > arg->depth) |
| 69 | return true; | 70 | return true; |
| 70 | */ | 71 | */ |
| @@ -119,6 +120,7 @@ solve_h48( | |||
| 119 | int8_t maxmoves, | 120 | int8_t maxmoves, |
| 120 | int8_t maxsolutions, | 121 | int8_t maxsolutions, |
| 121 | uint8_t h, | 122 | uint8_t h, |
| 123 | uint8_t k, | ||
| 122 | const void *data, | 124 | const void *data, |
| 123 | char *solutions | 125 | char *solutions |
| 124 | ) | 126 | ) |
| @@ -132,6 +134,7 @@ solve_h48( | |||
| 132 | .nsols = &nsols, | 134 | .nsols = &nsols, |
| 133 | .maxsolutions = maxsolutions, | 135 | .maxsolutions = maxsolutions, |
| 134 | .h = h, | 136 | .h = h, |
| 137 | .k = k, | ||
| 135 | .cocsepdata = (uint32_t *)data, | 138 | .cocsepdata = (uint32_t *)data, |
| 136 | .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4, | 139 | .h48data = ((uint32_t *)data) + COCSEP_FULLSIZE / 4, |
| 137 | .nextsol = &solutions | 140 | .nextsol = &solutions |
| @@ -175,7 +178,7 @@ solve_h48stats_dfs(dfsarg_solveh48stats_t *arg) | |||
| 175 | 178 | ||
| 176 | /* Check h48 lower bound for h=0 (esep, but no eo) */ | 179 | /* Check h48 lower bound for h=0 (esep, but no eo) */ |
| 177 | coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0); | 180 | coord = coord_h48_edges(arg->cube, COCLASS(d), TTREP(d), 0); |
| 178 | bound = get_esep_pval(arg->h48data, coord); | 181 | bound = get_esep_pval(arg->h48data, coord, 4); |
| 179 | if (bound + arg->nmoves > arg->depth) | 182 | if (bound + arg->nmoves > arg->depth) |
| 180 | return 0; | 183 | return 0; |
| 181 | 184 | ||
diff --git a/test/112_gendata_h48/gendata_h48_tests.c b/test/112_gendata_h48/gendata_h48_tests.c index 485d9d0..d6c6cb2 100644 --- a/test/112_gendata_h48/gendata_h48_tests.c +++ b/test/112_gendata_h48/gendata_h48_tests.c | |||
| @@ -1,43 +1,50 @@ | |||
| 1 | #include "../test.h" | 1 | #include "../test.h" |
| 2 | 2 | ||
| 3 | #define COCSEP_CLASSES 3393 | ||
| 3 | #define COCSEPSIZE 1119792 | 4 | #define COCSEPSIZE 1119792 |
| 4 | #define ETABLESIZE ((3393 * 495 * 70) >> 1) | ||
| 5 | 5 | ||
| 6 | int64_t gendata_h48h0k4(void *, uint8_t); | 6 | typedef struct { |
| 7 | uint8_t h; | ||
| 8 | uint8_t k; | ||
| 9 | uint8_t maxdepth; | ||
| 10 | void *buf; | ||
| 11 | uint32_t *info; | ||
| 12 | uint32_t *cocsepdata; | ||
| 13 | uint32_t *h48data; | ||
| 14 | uint64_t selfsim[COCSEP_CLASSES]; | ||
| 15 | cube_t crep[COCSEP_CLASSES]; | ||
| 16 | } gendata_h48_arg_t; | ||
| 7 | 17 | ||
| 8 | int64_t gendata_h48_fixture(void *buf, uint8_t maxdepth, uint8_t h) { | 18 | int64_t gendata_h48(gendata_h48_arg_t *); |
| 9 | if (h == 0) | ||
| 10 | return gendata_h48h0k4(buf, maxdepth); | ||
| 11 | fprintf(stderr, "Error: gendata h48 for h>0 not implemented yet\n"); | ||
| 12 | exit(1); | ||
| 13 | } | ||
| 14 | 19 | ||
| 15 | void run(void) { | 20 | void run(void) { |
| 16 | char str[STRLENMAX]; | 21 | char str[STRLENMAX]; |
| 17 | uint8_t i, maxdepth, h; | 22 | uint8_t i; |
| 18 | uint32_t *buf, *h48info; | 23 | gendata_h48_arg_t arg; |
| 19 | size_t result; | 24 | size_t result, sz; |
| 20 | 25 | ||
| 21 | fgets(str, STRLENMAX, stdin); | 26 | fgets(str, STRLENMAX, stdin); |
| 22 | maxdepth = atoi(str); | 27 | arg.maxdepth = atoi(str); |
| 23 | fgets(str, STRLENMAX, stdin); | 28 | fgets(str, STRLENMAX, stdin); |
| 24 | h = atoi(str); | 29 | arg.h = atoi(str); |
| 30 | arg.k = 4; | ||
| 25 | 31 | ||
| 26 | buf = (uint32_t *)malloc(sizeof(uint32_t) * 60000000); | 32 | sz = gendata_h48(&arg); /* With buf = NULL returns data size */ |
| 27 | result = gendata_h48_fixture(buf, maxdepth, h); | 33 | arg.buf = malloc(sz); |
| 28 | h48info = buf + (ETABLESIZE + COCSEPSIZE) / 4; | 34 | result = gendata_h48(&arg); |
| 29 | 35 | ||
| 30 | printf("%zu\n\n", result); | 36 | printf("%zu\n\n", result); |
| 31 | 37 | ||
| 32 | printf("cocsepdata:\n"); | 38 | printf("cocsepdata:\n"); |
| 33 | printf("Classes: %" PRIu32 "\n", buf[COCSEPSIZE/4-12]); | 39 | printf("Classes: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-12]); |
| 34 | printf("Max value: %" PRIu32 "\n", buf[COCSEPSIZE/4-11]); | 40 | printf("Max value: %" PRIu32 "\n", arg.cocsepdata[COCSEPSIZE/4-11]); |
| 35 | for (i = 0; i < 10; i++) | 41 | for (i = 0; i < 10; i++) |
| 36 | printf("%" PRIu32 ": %" PRIu32 "\n", i, buf[COCSEPSIZE/4-10+i]); | 42 | printf("%" PRIu32 ": %" PRIu32 "\n", |
| 43 | i, arg.cocsepdata[COCSEPSIZE/4-10+i]); | ||
| 37 | 44 | ||
| 38 | printf("\nh48:\n"); | 45 | printf("\nh48:\n"); |
| 39 | for (i = 0; i < maxdepth+1; i++) | 46 | for (i = 0; i < arg.maxdepth+1; i++) |
| 40 | printf("%" PRIu32 ": %" PRIu32 "\n", i, h48info[i+1]); | 47 | printf("%" PRIu32 ": %" PRIu32 "\n", i, arg.info[i+1]); |
| 41 | 48 | ||
| 42 | free(buf); | 49 | free(arg.buf); |
| 43 | } | 50 | } |
diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c index 92d346a..335821a 100644 --- a/test/113_gen_h48short/gen_h48short.c +++ b/test/113_gen_h48short/gen_h48short.c | |||
| @@ -8,6 +8,11 @@ typedef struct { | |||
| 8 | uint64_t capacity; | 8 | uint64_t capacity; |
| 9 | uint64_t randomizer; | 9 | uint64_t randomizer; |
| 10 | uint64_t *table; | 10 | uint64_t *table; |
| 11 | uint32_t *info; | ||
| 12 | uint32_t *cocsepdata; | ||
| 13 | uint32_t *h48data; | ||
| 14 | uint64_t selfsim[COCSEP_CLASSES]; | ||
| 15 | cube_t crep[COCSEP_CLASSES]; | ||
| 11 | } h48map_t; | 16 | } h48map_t; |
| 12 | 17 | ||
| 13 | typedef struct { | 18 | typedef struct { |
diff --git a/tools/001_gendata_h48/gendata_h48.c b/tools/001_gendata_h48/gendata_h48.c index da0b4ad..a73f818 100644 --- a/tools/001_gendata_h48/gendata_h48.c +++ b/tools/001_gendata_h48/gendata_h48.c | |||
| @@ -3,8 +3,8 @@ | |||
| 3 | 3 | ||
| 4 | #define MAXDEPTH 20 | 4 | #define MAXDEPTH 20 |
| 5 | #define HVALUE 0 | 5 | #define HVALUE 0 |
| 6 | #define OPTIONS "0;20" | 6 | #define OPTIONS "0;4;20" |
| 7 | #define LONGOPTIONS "h = 0, max depth = 20" | 7 | #define LONGOPTIONS "h = 0, k = 4, max depth = 20" |
| 8 | 8 | ||
| 9 | #define COCSEPSIZE 1119792 | 9 | #define COCSEPSIZE 1119792 |
| 10 | #define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) | 10 | #define ETABLESIZE(h) (((3393 * 495 * 70) >> 1) << (size_t)(h)) |
