gendata.h (8313B)
1 STATIC size_t gendata_coord(const coord_t [static 1], unsigned char *); 2 STATIC size_t gendata_multicoord( 3 const multicoord_t [static 1], unsigned char *); 4 STATIC long long gendata_coord_dispatch(const char *, unsigned long long, 5 unsigned char *); 6 STATIC tableinfo_t genptable_coord( 7 const coord_t [static 1], const unsigned char *, unsigned char *); 8 STATIC uint64_t genptable_coord_init_solved( 9 const coord_t [static 1], const unsigned char *, unsigned char *); 10 STATIC bool switch_to_fromnew(uint64_t, uint64_t, uint64_t); 11 STATIC uint64_t genptable_coord_fillneighbors(const coord_t [static 1], 12 const unsigned char *, uint64_t, uint8_t, unsigned char *); 13 STATIC uint64_t genptable_coord_fillfromnew(const coord_t [static 1], 14 const unsigned char *, uint64_t, uint8_t, unsigned char *); 15 STATIC uint8_t get_coord_pval( 16 const coord_t [static 1], const unsigned char *, uint64_t); 17 STATIC void set_coord_pval( 18 const coord_t [static 1], unsigned char *, uint64_t, uint8_t); 19 20 STATIC long long 21 gendata_coord_dispatch( 22 const char *coordstr, 23 unsigned long long bufsize, 24 unsigned char *buf 25 ) 26 { 27 coord_t *coord; 28 multicoord_t *mcoord; 29 30 parse_coord_and_trans(coordstr, &coord, &mcoord, NULL); 31 32 if (coord != NULL) 33 return gendata_coord(coord, buf); 34 35 if (mcoord != NULL) 36 return gendata_multicoord(mcoord, buf); 37 38 LOG("Error: could not parse coordinate '%s'\n", coordstr); 39 return NISSY_ERROR_INVALID_SOLVER; 40 } 41 42 STATIC size_t 43 gendata_coord(const coord_t coord[static 1], unsigned char *buf) 44 { 45 uint64_t coord_dsize, tablesize, ninfo; 46 unsigned char *pruningbuf, *coord_data; 47 unsigned char *table; 48 tableinfo_t coord_data_info, pruning_info; 49 50 coord_data = buf == NULL ? NULL : buf + INFOSIZE; 51 coord_dsize = coord->gendata(coord_data); 52 if (coord_dsize == SIZE_MAX) 53 goto gendata_coord_error; 54 55 ninfo = coord_dsize == 0 ? 1 : 2; 56 tablesize = DIV_ROUND_UP(coord->max, 2); 57 58 if (buf == NULL) 59 goto gendata_coord_return_size; 60 61 if (ninfo == 2) { 62 coord_data_info = (tableinfo_t) { 63 .solver = "coord helper table for ", 64 .type = TABLETYPE_SPECIAL, 65 .infosize = INFOSIZE, 66 .fullsize = INFOSIZE + coord_dsize, 67 .hash = 0, 68 .next = INFOSIZE + coord_dsize, 69 70 /* Unknown / non-applicable values */ 71 .entries = 0, 72 .classes = 0, 73 .bits = 0, 74 .base = 0, 75 .maxvalue = 0, 76 }; 77 78 append_name(&coord_data_info, coord->name); 79 writetableinfo(&coord_data_info, INFOSIZE + coord_dsize, buf); 80 81 pruningbuf = buf + INFOSIZE + coord_dsize; 82 } else { 83 pruningbuf = buf; 84 } 85 86 table = pruningbuf + INFOSIZE; 87 pruning_info = genptable_coord(coord, coord_data, table); 88 writetableinfo(&pruning_info, INFOSIZE + tablesize, pruningbuf); 89 90 gendata_coord_return_size: 91 return ninfo * INFOSIZE + coord_dsize + tablesize; 92 93 gendata_coord_error: 94 LOG("Unexpected error generating coordinate data\n"); 95 return 0; 96 } 97 98 STATIC size_t 99 gendata_multicoord(const multicoord_t mcoord[static 1], unsigned char *buf) 100 { 101 unsigned char *b; 102 size_t i, s, ret; 103 tableinfo_t info; 104 105 info = (tableinfo_t) { 106 .solver = "multicoordinate table for ", 107 .type = TABLETYPE_MULTI, 108 .infosize = INFOSIZE, 109 .fullsize = INFOSIZE, 110 .hash = 0, 111 .next = INFOSIZE, 112 113 /* Unknown / non-applicable values */ 114 .entries = 0, 115 .classes = 0, 116 .bits = 0, 117 .base = 0, 118 .maxvalue = 0, 119 }; 120 121 append_name(&info, mcoord->name); 122 if (buf != NULL) 123 writetableinfo(&info, INFOSIZE, buf); 124 ret = INFOSIZE; 125 126 for (i = 0; mcoord->coordinates[i] != NULL; i++) { 127 b = buf == NULL ? NULL : buf + ret; 128 s = gendata_coord(mcoord->coordinates[i], b); 129 if (s == 0) 130 return 0; 131 132 ret += s; 133 134 /* Pad so that each coordinate's table is 8-byte aligned */ 135 while (ret % 8 != 0) 136 buf[ret++] = 0; 137 } 138 139 return ret; 140 } 141 142 STATIC tableinfo_t 143 genptable_coord( 144 const coord_t coord[static 1], 145 const unsigned char *data, 146 unsigned char *table 147 ) 148 { 149 uint64_t tablesize, i, d, tot, t, nm; 150 tableinfo_t info; 151 152 tablesize = DIV_ROUND_UP(coord->max, 2); 153 info = (tableinfo_t) { 154 .solver = "coordinate solver for ", 155 .type = TABLETYPE_PRUNING, 156 .infosize = INFOSIZE, 157 .fullsize = INFOSIZE + tablesize, 158 .hash = 0, 159 .entries = coord->max, 160 .classes = 0, 161 .bits = 4, 162 .base = 0, 163 .maxvalue = 0, 164 .next = 0 165 }; 166 167 memset(table, 0xFF, tablesize); 168 memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); 169 append_name(&info, coord->name); 170 171 tot = info.distribution[0] = 172 genptable_coord_init_solved(coord, data, table); 173 nm = popcount_u32(coord->moves_mask_gendata); 174 for (d = 1; tot < coord->max && d < 15; d++) { 175 t = 0; 176 if (switch_to_fromnew(tot, coord->max, nm)) { 177 for (i = 0; i < coord->max; i++) 178 if (get_coord_pval(coord, table, i) > d) 179 t += genptable_coord_fillfromnew( 180 coord, data, i, d, table); 181 } else { 182 for (i = 0; i < coord->max; i++) 183 if (get_coord_pval(coord, table, i) == d-1) 184 t += genptable_coord_fillneighbors( 185 coord, data, i, d, table); 186 } 187 tot += t; 188 info.distribution[d] = t; 189 LOG("[%s gendata] Depth %" PRIu64 ": found %" PRIu64 " (%" 190 PRIu64 " of %" PRIu64 ")\n", 191 coord->name, d, t, tot, coord->max); 192 } 193 if (tot == coord->max) { 194 info.maxvalue = d-1; 195 } else { 196 LOG("[%s gendata] Depth >= 15: %" PRIu64 " remaining\n", 197 coord->name, coord->max - tot); 198 info.distribution[d] = coord->max - tot; 199 info.maxvalue = 15; 200 } 201 202 return info; 203 } 204 205 STATIC uint64_t 206 genptable_coord_init_solved( 207 const coord_t coord[static 1], 208 const unsigned char *coord_data, 209 unsigned char *table 210 ) 211 { 212 uint64_t i, max_solved, ret; 213 214 max_solved = coord->is_solved == NULL ? 1 : coord->max; 215 216 for (i = 0, ret = 0; i < max_solved; i++) { 217 if (coord_is_solved(coord, i, coord_data)) { 218 set_coord_pval(coord, table, i, 0); 219 ret++; 220 } 221 } 222 223 return ret; 224 } 225 226 STATIC bool 227 switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm) 228 { 229 /* 230 Heuristic to determine if it is more conveniente to loop over 231 done coordinates and fill the new discovered, or to loop from new 232 coordinates and fill them if they have a done neighbor. 233 */ 234 235 double r = (double)done / (double)max; 236 return 1.0 - intpow(1.0-r, nm) > nm * (1.0-r); 237 } 238 239 STATIC uint64_t 240 genptable_coord_fillneighbors( 241 const coord_t coord[static 1], 242 const unsigned char *data, 243 uint64_t i, 244 uint8_t d, 245 unsigned char *table 246 ) 247 { 248 bool isnasty; 249 uint8_t m; 250 uint64_t ii, j, t, tot; 251 cube_t c, moved; 252 253 c = coord->cube(i, data); 254 tot = 0; 255 for (m = 0; m < NMOVES; m++) { 256 if (!((UINT32_C(1) << (uint32_t)m) & 257 coord->moves_mask_gendata)) 258 continue; 259 moved = move(c, m); 260 ii = coord->coord(moved, data); 261 isnasty = coord->isnasty(ii, data); 262 for (t = 0; t < NTRANS && (t == 0 || isnasty); t++) { 263 if (!((UINT64_C(1) << t) & coord->trans_mask)) 264 continue; 265 266 j = coord->coord(transform(moved, t), data); 267 if (get_coord_pval(coord, table, j) > d) { 268 set_coord_pval(coord, table, j, d); 269 tot++; 270 } 271 } 272 } 273 274 return tot; 275 } 276 277 STATIC uint64_t 278 genptable_coord_fillfromnew( 279 const coord_t coord[static 1], 280 const unsigned char *data, 281 uint64_t i, 282 uint8_t d, 283 unsigned char *table 284 ) 285 { 286 bool found; 287 uint8_t m; 288 uint64_t tot, t, ii, j, nsim, sim[NTRANS]; 289 cube_t c; 290 291 tot = 0; 292 c = coord->cube(i, data); 293 294 for (t = 0, nsim = 0; t < NTRANS; t++) { 295 if (!((UINT64_C(1) << t) & coord->trans_mask)) 296 continue; 297 298 ii = coord->coord(transform(c, t), data); 299 for (j = 0, found = false; j < nsim && !found; j++) 300 found = sim[j] == ii; 301 if (!found) 302 sim[nsim++] = ii; 303 } 304 305 for (j = 0, found = false; j < nsim && !found; j++) { 306 c = coord->cube(sim[j], data); 307 for (m = 0; m < NMOVES; m++) { 308 if (!((UINT32_C(1) << (uint32_t)m) & 309 coord->moves_mask_gendata)) 310 continue; 311 ii = coord->coord(move(c, m), data); 312 if (get_coord_pval(coord, table, ii) < d) { 313 found = true; 314 break; 315 } 316 } 317 } 318 319 tot = 0; 320 if (found) { 321 for (j = 0; j < nsim; j++) { 322 if (get_coord_pval(coord, table, sim[j]) > d) { 323 set_coord_pval(coord, table, sim[j], d); 324 tot++; 325 } 326 } 327 } 328 329 return tot; 330 } 331 332 STATIC uint8_t 333 get_coord_pval( 334 const coord_t coord[static 1], 335 const unsigned char *table, 336 uint64_t i 337 ) 338 { 339 return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i); 340 } 341 342 STATIC void 343 set_coord_pval( 344 const coord_t coord[static 1], 345 unsigned char *table, 346 uint64_t i, 347 uint8_t val 348 ) 349 { 350 table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i))) 351 | (val << COORD_SHIFT(i)); 352 }