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