gendata.h (8360B)
1 STATIC size_t gendata_coord(const coord_t [NON_NULL], unsigned char *); 2 STATIC size_t gendata_multicoord( 3 const multicoord_t [NON_NULL], 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 [NON_NULL], const unsigned char *, unsigned char *); 8 STATIC uint64_t genptable_coord_init_solved( 9 const coord_t [NON_NULL], 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 [NON_NULL], 12 const unsigned char *, uint64_t, uint8_t, unsigned char *); 13 STATIC uint64_t genptable_coord_fillfromnew(const coord_t [NON_NULL], 14 const unsigned char *, uint64_t, uint8_t, unsigned char *); 15 STATIC uint8_t get_coord_pval( 16 const coord_t [NON_NULL], const unsigned char *, uint64_t); 17 STATIC void set_coord_pval( 18 const coord_t [NON_NULL], 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[NON_NULL], 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[NON_NULL], 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[NON_NULL], 145 const unsigned char *data, 146 unsigned char *table 147 ) 148 { 149 uint64_t tablesize, i, tot, t, nm; 150 uint8_t d; 151 tableinfo_t info; 152 153 tablesize = DIV_ROUND_UP(coord->max, 2); 154 info = (tableinfo_t) { 155 .solver = "coordinate solver for ", 156 .type = TABLETYPE_PRUNING, 157 .infosize = INFOSIZE, 158 .fullsize = INFOSIZE + tablesize, 159 .hash = 0, 160 .entries = coord->max, 161 .classes = 0, 162 .bits = 4, 163 .base = 0, 164 .maxvalue = 0, 165 .next = 0 166 }; 167 168 memset(table, 0xFF, tablesize); 169 memset(info.distribution, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t)); 170 append_name(&info, coord->name); 171 172 tot = info.distribution[0] = 173 genptable_coord_init_solved(coord, data, table); 174 nm = popcount_u64(coord->moves_mask_gendata); 175 for (d = 1; tot < coord->max && d < 15; d++) { 176 t = 0; 177 if (switch_to_fromnew(tot, coord->max, nm)) { 178 for (i = 0; i < coord->max; i++) 179 if (get_coord_pval(coord, table, i) > d) 180 t += genptable_coord_fillfromnew( 181 coord, data, i, d, table); 182 } else { 183 for (i = 0; i < coord->max; i++) 184 if (get_coord_pval(coord, table, i) == d-1) 185 t += genptable_coord_fillneighbors( 186 coord, data, i, d, table); 187 } 188 tot += t; 189 info.distribution[d] = t; 190 LOG("[%s gendata] Depth %" PRIu64 ": found %" PRIu64 " (%" 191 PRIu64 " of %" PRIu64 ")\n", 192 coord->name, d, t, tot, coord->max); 193 } 194 if (tot == coord->max) { 195 info.maxvalue = d-1; 196 } else { 197 LOG("[%s gendata] Depth >= 15: %" PRIu64 " remaining\n", 198 coord->name, coord->max - tot); 199 info.distribution[d] = coord->max - tot; 200 info.maxvalue = 15; 201 } 202 203 return info; 204 } 205 206 STATIC uint64_t 207 genptable_coord_init_solved( 208 const coord_t coord[NON_NULL], 209 const unsigned char *coord_data, 210 unsigned char *table 211 ) 212 { 213 uint64_t i, max_solved, ret; 214 215 max_solved = coord->is_solved == NULL ? 1 : coord->max; 216 217 for (i = 0, ret = 0; i < max_solved; i++) { 218 if (coord_is_solved(coord, i, coord_data)) { 219 set_coord_pval(coord, table, i, 0); 220 ret++; 221 } 222 } 223 224 return ret; 225 } 226 227 STATIC bool 228 switch_to_fromnew(uint64_t done, uint64_t max, uint64_t nm) 229 { 230 /* 231 Heuristic to determine if it is more conveniente to loop over 232 done coordinates and fill the new discovered, or to loop from new 233 coordinates and fill them if they have a done neighbor. 234 */ 235 236 double r = (double)done / (double)max; 237 return 1.0 - intpow(1.0-r, nm) > nm * (1.0-r); 238 } 239 240 STATIC uint64_t 241 genptable_coord_fillneighbors( 242 const coord_t coord[NON_NULL], 243 const unsigned char *data, 244 uint64_t i, 245 uint8_t d, 246 unsigned char *table 247 ) 248 { 249 bool isnasty; 250 uint8_t m; 251 uint64_t ii, j, tot; 252 uint8_t t; 253 cube_t c, moved; 254 255 c = coord->cube(i, data); 256 tot = 0; 257 for (m = 0; m < NMOVES; m++) { 258 if (!((UINT64_C(1) << (uint64_t)m) & 259 coord->moves_mask_gendata)) 260 continue; 261 moved = move(c, m); 262 ii = coord->coord(moved, data); 263 isnasty = coord->isnasty(ii, data); 264 for (t = 0; t < NTRANS && (t == 0 || isnasty); t++) { 265 if (!((UINT64_C(1) << (uint64_t)t) & coord->trans_mask)) 266 continue; 267 268 j = coord->coord(transform(moved, t), data); 269 if (get_coord_pval(coord, table, j) > d) { 270 set_coord_pval(coord, table, j, d); 271 tot++; 272 } 273 } 274 } 275 276 return tot; 277 } 278 279 STATIC uint64_t 280 genptable_coord_fillfromnew( 281 const coord_t coord[NON_NULL], 282 const unsigned char *data, 283 uint64_t i, 284 uint8_t d, 285 unsigned char *table 286 ) 287 { 288 bool found; 289 uint8_t m; 290 uint64_t tot, j, ii, nsim, sim[NTRANS]; 291 uint8_t t; 292 cube_t c; 293 294 tot = 0; 295 c = coord->cube(i, data); 296 297 for (t = 0, nsim = 0; t < NTRANS; t++) { 298 if (!((UINT64_C(1) << (uint64_t)t) & coord->trans_mask)) 299 continue; 300 301 ii = coord->coord(transform(c, t), data); 302 for (j = 0, found = false; j < nsim && !found; j++) 303 found = sim[j] == ii; 304 if (!found) 305 sim[nsim++] = ii; 306 } 307 308 for (j = 0, found = false; j < nsim && !found; j++) { 309 c = coord->cube(sim[j], data); 310 for (m = 0; m < NMOVES; m++) { 311 if (!((UINT64_C(1) << (uint64_t)m) & 312 coord->moves_mask_gendata)) 313 continue; 314 ii = coord->coord(move(c, m), data); 315 if (get_coord_pval(coord, table, ii) < d) { 316 found = true; 317 break; 318 } 319 } 320 } 321 322 tot = 0; 323 if (found) { 324 for (j = 0; j < nsim; j++) { 325 if (get_coord_pval(coord, table, sim[j]) > d) { 326 set_coord_pval(coord, table, sim[j], d); 327 tot++; 328 } 329 } 330 } 331 332 return tot; 333 } 334 335 STATIC uint8_t 336 get_coord_pval( 337 const coord_t coord[NON_NULL], 338 const unsigned char *table, 339 uint64_t i 340 ) 341 { 342 return (table[COORD_INDEX(i)] & COORD_MASK(i)) >> COORD_SHIFT(i); 343 } 344 345 STATIC void 346 set_coord_pval( 347 const coord_t coord[NON_NULL], 348 unsigned char *table, 349 uint64_t i, 350 uint8_t val 351 ) 352 { 353 table[COORD_INDEX(i)] = (table[COORD_INDEX(i)] & (~COORD_MASK(i))) 354 | (val << COORD_SHIFT(i)); 355 }