gendata_eoesep.h (6447B)
1 STATIC uint64_t coord_eoesep_sym(cube_t, const uint32_t [SIZE(ESEP_MAX)]); 2 STATIC size_t gendata_esep_classes( 3 uint32_t [SIZE(ESEP_MAX)], uint16_t [SIZE(ESEP_CLASSES)]); 4 STATIC size_t gendata_eoesep(unsigned char *, uint8_t); 5 STATIC uint32_t gendata_eoesep_bfs(uint8_t, uint8_t [SIZE(EOESEP_BUF)], 6 uint32_t [SIZE(ESEP_MAX)], uint16_t [SIZE(ESEP_CLASSES)]); 7 STATIC uint32_t gendata_eoesep_fromnew(uint8_t, uint8_t [SIZE(EOESEP_BUF)], 8 uint32_t [SIZE(ESEP_MAX)], uint16_t [SIZE(ESEP_CLASSES)]); 9 STATIC uint32_t gendata_eoesep_fromdone(uint8_t, uint8_t [SIZE(EOESEP_BUF)], 10 uint32_t [SIZE(ESEP_MAX)], uint16_t [SIZE(ESEP_CLASSES)]); 11 STATIC uint32_t gendata_eoesep_marksim(uint64_t, uint8_t, 12 uint8_t [SIZE(EOESEP_BUF)], uint32_t [SIZE(ESEP_MAX)]); 13 STATIC bool gendata_eoesep_next(cube_t, uint8_t, 14 uint8_t [SIZE(EOESEP_BUF)], uint32_t [SIZE(ESEP_MAX)]); 15 STATIC uint8_t get_eoesep_pval( 16 const uint8_t [SIZE(DIV_ROUND_UP(EOESEP_TABLESIZE, 2))], uint64_t); 17 STATIC uint8_t get_eoesep_pval_cube(const unsigned char *, cube_t); 18 STATIC void set_eoesep_pval( 19 uint8_t [SIZE(DIV_ROUND_UP(EOESEP_TABLESIZE, 2))], uint64_t, uint8_t); 20 21 STATIC uint64_t 22 coord_eoesep_sym(cube_t c, const uint32_t esep_classes[SIZE(ESEP_MAX)]) 23 { 24 uint8_t ttrep; 25 uint32_t edata, class; 26 uint64_t esep, eo; 27 28 esep = coord_esep(c); 29 edata = esep_classes[esep]; 30 class = ECLASS(edata); 31 ttrep = TTREP(edata); 32 eo = coord_eo(transform(c, ttrep)); 33 34 return (class << UINT32_C(11)) + eo; 35 } 36 37 STATIC size_t 38 gendata_esep_classes( 39 uint32_t esep_classes[SIZE(ESEP_MAX)], 40 uint16_t rep[SIZE(ESEP_CLASSES)] 41 ) 42 { 43 bool visited[ESEP_MAX]; 44 uint8_t t; 45 uint32_t class, cl, ti; 46 uint64_t i, j; 47 cube_t c; 48 49 memset(visited, 0, ESEP_MAX * sizeof(bool)); 50 class = 0; 51 for (i = 0; i < ESEP_MAX; i++) { 52 if (visited[i]) 53 continue; 54 c = invcoord_esep(i); 55 for (t = 0; t < NTRANS; t++) { 56 j = coord_esep(transform(c, t)); 57 cl = class << UINT32_C(16); 58 ti = inverse_trans(t) << UINT32_C(8); 59 esep_classes[j] = cl | ti; 60 visited[j] = true; 61 } 62 rep[class] = (uint16_t)i; 63 class++; 64 } 65 66 return class; 67 } 68 69 STATIC size_t 70 gendata_eoesep(unsigned char *buf, uint8_t maxdepth) 71 { 72 uint8_t d; 73 unsigned char *buf8; 74 uint16_t rep[ESEP_CLASSES]; 75 uint32_t *esep_classes, done, level; 76 uint64_t coord; 77 tableinfo_t info; 78 79 if (buf == NULL) 80 goto gendata_eoesep_return_size; 81 82 LOG("[H48 gendata] Computing eoesep data\n"); 83 memset(buf, 0xFF, EOESEP_FULLSIZE); 84 esep_classes = (uint32_t *)(buf + INFOSIZE); 85 buf8 = buf + INFOSIZE + 4*ESEP_MAX; 86 gendata_esep_classes(esep_classes, rep); 87 88 info = (tableinfo_t) { 89 .solver = "eoesep data for h48", 90 .type = TABLETYPE_SPECIAL, 91 .infosize = INFOSIZE, 92 .fullsize = EOESEP_FULLSIZE, 93 .hash = 0, 94 .entries = EOESEP_TABLESIZE, 95 .classes = ESEP_CLASSES, 96 .bits = 4, 97 .base = 0, 98 .maxvalue = 11, 99 .next = 0 100 }; 101 102 coord = 0; /* Assumed coordinate of solved cube */ 103 set_eoesep_pval(buf8, coord, 0); 104 done = 1; 105 info.distribution[0] = 1; 106 for (d = 1; d <= maxdepth && done < EOESEP_TABLESIZE; d++) { 107 level = gendata_eoesep_bfs(d, buf8, esep_classes, rep); 108 done += level; 109 info.distribution[d] = level; 110 } 111 112 writetableinfo(&info, EOESEP_FULLSIZE, buf); 113 114 LOG("[H48 gendata] eoesep data computed\n"); 115 116 gendata_eoesep_return_size: 117 return EOESEP_FULLSIZE; 118 } 119 120 STATIC uint32_t 121 gendata_eoesep_bfs( 122 uint8_t d, 123 uint8_t buf8[EOESEP_BUF], 124 uint32_t esep_classes[SIZE(ESEP_MAX)], 125 uint16_t rep[SIZE(ESEP_CLASSES)] 126 ) 127 { 128 if (d < 9) 129 return gendata_eoesep_fromdone(d, buf8, esep_classes, rep); 130 else 131 return gendata_eoesep_fromnew(d, buf8, esep_classes, rep); 132 } 133 134 STATIC uint32_t 135 gendata_eoesep_fromdone( 136 uint8_t d, 137 uint8_t buf8[EOESEP_BUF], 138 uint32_t esep_classes[SIZE(ESEP_MAX)], 139 uint16_t rep[SIZE(ESEP_CLASSES)] 140 ) 141 { 142 uint8_t pval; 143 uint32_t done; 144 uint64_t i, esep, eo, coord; 145 146 done = 0; 147 for (i = 0; i < ESEP_CLASSES; i++) { 148 esep = rep[i]; 149 for (eo = 0; eo < POW_2_11; eo++) { 150 coord = (i << UINT64_C(11)) + eo; 151 pval = get_eoesep_pval(buf8, coord); 152 if (pval != d-1) 153 continue; 154 155 coord = (esep << UINT64_C(11)) + eo; 156 done += gendata_eoesep_marksim( 157 coord, d, buf8, esep_classes); 158 } 159 } 160 161 return done; 162 } 163 164 STATIC uint32_t 165 gendata_eoesep_fromnew( 166 uint8_t d, 167 uint8_t buf8[EOESEP_BUF], 168 uint32_t esep_classes[SIZE(ESEP_MAX)], 169 uint16_t rep[SIZE(ESEP_CLASSES)] 170 ) 171 { 172 uint8_t pval; 173 uint32_t done; 174 uint64_t i, esep, eo, coord; 175 cube_t c; 176 177 done = 0; 178 for (i = 0; i < ESEP_CLASSES; i++) { 179 esep = rep[i]; 180 for (eo = 0; eo < POW_2_11; eo++) { 181 coord = (i << UINT64_C(11)) + eo; 182 pval = get_eoesep_pval(buf8, coord); 183 if (pval != 15) 184 continue; 185 186 c = invcoord_eoesep((esep << UINT64_C(11)) + eo); 187 if (gendata_eoesep_next(c, d, buf8, esep_classes)) { 188 set_eoesep_pval(buf8, coord, d); 189 done++; 190 } 191 } 192 } 193 194 return done; 195 } 196 197 STATIC uint32_t 198 gendata_eoesep_marksim( 199 uint64_t i, 200 uint8_t d, 201 uint8_t buf8[SIZE(EOESEP_BUF)], 202 uint32_t esep_classes[SIZE(ESEP_MAX)] 203 ) 204 { 205 uint8_t t, m, pval; 206 cube_t c, moved, transformed; 207 uint32_t done; 208 int64_t coord; 209 210 done = 0; 211 c = invcoord_eoesep(i); 212 for (m = 0; m < 18; m++) { 213 moved = move(c, m); 214 for (t = 0; t < NTRANS; t++) { 215 transformed = transform(moved, t); 216 coord = coord_eoesep_sym(transformed, esep_classes); 217 pval = get_eoesep_pval(buf8, coord); 218 if (pval > d) { 219 set_eoesep_pval(buf8, coord, d); 220 done++; 221 } 222 } 223 } 224 225 return done; 226 } 227 228 STATIC bool 229 gendata_eoesep_next( 230 cube_t c, 231 uint8_t d, 232 uint8_t buf8[SIZE(EOESEP_BUF)], 233 uint32_t esep_classes[SIZE(ESEP_MAX)] 234 ) 235 { 236 uint8_t m, t, pval; 237 uint64_t coord; 238 cube_t moved, transformed; 239 240 for (t = 0; t < NTRANS; t++) { 241 transformed = transform(c, t); 242 for (m = 0; m < 18; m++) { 243 moved = move(transformed, m); 244 coord = coord_eoesep_sym(moved, esep_classes); 245 pval = get_eoesep_pval(buf8, coord); 246 if (pval == d-1) 247 return true; 248 } 249 } 250 251 return false; 252 } 253 254 STATIC uint8_t 255 get_eoesep_pval( 256 const uint8_t table[SIZE(DIV_ROUND_UP(EOESEP_TABLESIZE, 2))], 257 uint64_t i 258 ) 259 { 260 return (table[EOESEP_INDEX(i)] & EOESEP_MASK(i)) >> EOESEP_SHIFT(i); 261 } 262 263 STATIC uint8_t 264 get_eoesep_pval_cube(const unsigned char *data, cube_t c) 265 { 266 uint64_t coord; 267 268 coord = coord_eoesep_sym(c, (const uint32_t *)data); 269 270 return get_eoesep_pval(data + 4*ESEP_MAX, coord); 271 } 272 273 STATIC void 274 set_eoesep_pval( 275 uint8_t table[SIZE(DIV_ROUND_UP(EOESEP_TABLESIZE, 2))], 276 uint64_t i, 277 uint8_t val 278 ) 279 { 280 table[EOESEP_INDEX(i)] = (table[EOESEP_INDEX(i)] & (~EOESEP_MASK(i))) 281 | (val << EOESEP_SHIFT(i)); 282 }