gendata_eoesep.h (6421B)
1 STATIC int64_t coord_eoesep_sym(cube_t, const uint32_t [static ESEP_MAX]); 2 STATIC size_t gendata_esep_classes( 3 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); 4 STATIC size_t gendata_eoesep(unsigned char *, uint8_t); 5 STATIC uint32_t gendata_eoesep_bfs(uint8_t, uint8_t [static EOESEP_BUF], 6 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); 7 STATIC uint32_t gendata_eoesep_fromnew(uint8_t, uint8_t [static EOESEP_BUF], 8 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); 9 STATIC uint32_t gendata_eoesep_fromdone(uint8_t, uint8_t [static EOESEP_BUF], 10 uint32_t [static ESEP_MAX], uint16_t [static ESEP_CLASSES]); 11 STATIC uint32_t gendata_eoesep_marksim(int64_t, uint8_t, 12 uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]); 13 STATIC bool gendata_eoesep_next(cube_t, uint8_t, 14 uint8_t [static EOESEP_BUF], uint32_t [static ESEP_MAX]); 15 STATIC uint8_t get_eoesep_pval( 16 const uint8_t [static DIV_ROUND_UP(EOESEP_TABLESIZE, 2)], int64_t); 17 STATIC uint8_t get_eoesep_pval_cube(const unsigned char *, cube_t); 18 STATIC void set_eoesep_pval( 19 uint8_t [static DIV_ROUND_UP(EOESEP_TABLESIZE, 2)], int64_t, uint8_t); 20 21 STATIC int64_t 22 coord_eoesep_sym(cube_t c, const uint32_t esep_classes[static ESEP_MAX]) 23 { 24 uint8_t ttrep; 25 uint32_t edata, class; 26 int64_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[static ESEP_MAX], 40 uint16_t rep[static ESEP_CLASSES] 41 ) 42 { 43 bool visited[ESEP_MAX]; 44 uint8_t t; 45 uint32_t class, cl, ti; 46 int64_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] = 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 int64_t coord; 77 tableinfo_t info; 78 79 if (buf == NULL) 80 goto gendata_eoesep_return_size; 81 82 LOG("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("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[static ESEP_MAX], 125 uint16_t rep[static 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[static ESEP_MAX], 139 uint16_t rep[static ESEP_CLASSES] 140 ) 141 { 142 uint8_t pval; 143 int64_t i, esep, eo, coord, done; 144 145 done = 0; 146 for (i = 0; i < (int64_t)ESEP_CLASSES; i++) { 147 esep = rep[i]; 148 for (eo = 0; eo < POW_2_11; eo++) { 149 coord = (i << INT64_C(11)) + eo; 150 pval = get_eoesep_pval(buf8, coord); 151 if (pval != d-1) 152 continue; 153 154 coord = (esep << INT64_C(11)) + eo; 155 done += gendata_eoesep_marksim( 156 coord, d, buf8, esep_classes); 157 } 158 } 159 160 return done; 161 } 162 163 STATIC uint32_t 164 gendata_eoesep_fromnew( 165 uint8_t d, 166 uint8_t buf8[EOESEP_BUF], 167 uint32_t esep_classes[static ESEP_MAX], 168 uint16_t rep[static ESEP_CLASSES] 169 ) 170 { 171 uint8_t pval; 172 int64_t i, esep, eo, coord, done; 173 cube_t c; 174 175 done = 0; 176 for (i = 0; i < (int64_t)ESEP_CLASSES; i++) { 177 esep = rep[i]; 178 for (eo = 0; eo < POW_2_11; eo++) { 179 coord = (i << INT64_C(11)) + eo; 180 pval = get_eoesep_pval(buf8, coord); 181 if (pval != 15) 182 continue; 183 184 c = invcoord_eoesep((esep << INT64_C(11)) + eo); 185 if (gendata_eoesep_next(c, d, buf8, esep_classes)) { 186 set_eoesep_pval(buf8, coord, d); 187 done++; 188 } 189 } 190 } 191 192 return done; 193 } 194 195 STATIC uint32_t 196 gendata_eoesep_marksim( 197 int64_t i, 198 uint8_t d, 199 uint8_t buf8[static EOESEP_BUF], 200 uint32_t esep_classes[static ESEP_MAX] 201 ) 202 { 203 uint8_t t, m, pval; 204 cube_t c, moved, transformed; 205 uint32_t done; 206 int64_t coord; 207 208 done = 0; 209 c = invcoord_eoesep(i); 210 for (m = 0; m < 18; m++) { 211 moved = move(c, m); 212 for (t = 0; t < NTRANS; t++) { 213 transformed = transform(moved, t); 214 coord = coord_eoesep_sym(transformed, esep_classes); 215 pval = get_eoesep_pval(buf8, coord); 216 if (pval > d) { 217 set_eoesep_pval(buf8, coord, d); 218 done++; 219 } 220 } 221 } 222 223 return done; 224 } 225 226 STATIC bool 227 gendata_eoesep_next( 228 cube_t c, 229 uint8_t d, 230 uint8_t buf8[static EOESEP_BUF], 231 uint32_t esep_classes[static ESEP_MAX] 232 ) 233 { 234 uint8_t m, t, pval; 235 int64_t coord; 236 cube_t moved, transformed; 237 238 for (t = 0; t < NTRANS; t++) { 239 transformed = transform(c, t); 240 for (m = 0; m < 18; m++) { 241 moved = move(transformed, m); 242 coord = coord_eoesep_sym(moved, esep_classes); 243 pval = get_eoesep_pval(buf8, coord); 244 if (pval == d-1) 245 return true; 246 } 247 } 248 249 return false; 250 } 251 252 STATIC uint8_t 253 get_eoesep_pval( 254 const uint8_t table[static DIV_ROUND_UP(EOESEP_TABLESIZE, 2)], 255 int64_t i 256 ) 257 { 258 return (table[EOESEP_INDEX(i)] & EOESEP_MASK(i)) >> EOESEP_SHIFT(i); 259 } 260 261 STATIC uint8_t 262 get_eoesep_pval_cube(const unsigned char *data, cube_t c) 263 { 264 int64_t coord; 265 266 coord = coord_eoesep_sym(c, (const uint32_t *)data); 267 268 return get_eoesep_pval(data + 4*ESEP_MAX, coord); 269 } 270 271 STATIC void 272 set_eoesep_pval( 273 uint8_t table[static DIV_ROUND_UP(EOESEP_TABLESIZE, 2)], 274 int64_t i, 275 uint8_t val 276 ) 277 { 278 table[EOESEP_INDEX(i)] = (table[EOESEP_INDEX(i)] & (~EOESEP_MASK(i))) 279 | (val << EOESEP_SHIFT(i)); 280 }