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