fst.c (11276B)
1 #define FST_C 2 3 #include "fst.h" 4 5 static FstCube ep_to_fst_epos(int *ep); 6 static void init_fst_corner_invtables(); 7 static void init_fst_eo_invtables(); 8 static void init_fst_eo_update(uint64_t, uint64_t, int, Cube *); 9 static void init_fst_where_is_edge(); 10 static bool read_fst_tables_file(); 11 static bool write_fst_tables_file(); 12 13 static int edge_slice[12] = {[FR] = 0, [FL] = 0, [BL] = 0, [BR] = 0, 14 [UL] = 1, [UR] = 1, [DR] = 1, [DL] = 1, 15 [UF] = 2, [UB] = 2, [DF] = 2, [DB] = 2}; 16 17 static uint16_t inv_coud[FACTORIAL8][POW3TO7]; 18 static uint16_t inv_cp[FACTORIAL8]; 19 static uint16_t uf_cp_to_fr_cp[FACTORIAL8]; 20 static uint16_t uf_cp_to_rd_cp[FACTORIAL8]; 21 static uint16_t eo_invtable[3][POW2TO11][BINOM12ON4*FACTORIAL4]; 22 static uint16_t fst_where_is_edge_arr[3][12][BINOM12ON4*FACTORIAL4]; 23 24 FstCube 25 cube_to_fst(Cube *cube) 26 { 27 Cube c; 28 FstCube ret; 29 30 copy_cube(cube, &c); 31 ret.uf_eofb = coord_eofb.i[0]->index(&c); 32 ret.uf_eposepe = coord_eposepe.i[0]->index(&c); 33 ret.uf_coud = coord_coud.i[0]->index(&c); 34 ret.uf_cp = coord_cp.i[0]->index(&c); 35 copy_cube(cube, &c); 36 apply_trans(fr, &c); 37 ret.fr_eofb = coord_eofb.i[0]->index(&c); 38 ret.fr_eposepe = coord_eposepe.i[0]->index(&c); 39 ret.fr_coud = coord_coud.i[0]->index(&c); 40 copy_cube(cube, &c); 41 apply_trans(rd, &c); 42 ret.rd_eofb = coord_eofb.i[0]->index(&c); 43 ret.rd_eposepe = coord_eposepe.i[0]->index(&c); 44 ret.rd_coud = coord_coud.i[0]->index(&c); 45 46 return ret; 47 } 48 49 static FstCube 50 ep_to_fst_epos(int *ep) 51 { 52 static int eind[12] = { 53 [FR] = 0, [FL] = 1, [BL] = 2, [BR] = 3, 54 [UR] = 0, [DR] = 1, [DL] = 2, [UL] = 3, 55 [DB] = 0, [DF] = 1, [UF] = 2, [UB] = 3 56 }; 57 static int eptrans_fr[12] = { 58 [FR] = UF, [DF] = UL, [FL] = UB, [UF] = UR, 59 [BR] = DF, [DB] = DL, [BL] = DB, [UB] = DR, 60 [UR] = FR, [DR] = FL, [DL] = BL, [UL] = BR 61 }; 62 static int eptrans_rd[12] = { 63 [DR] = UF, [FR] = UL, [UR] = UB, [BR] = UR, 64 [DL] = DF, [FL] = DL, [UL] = DB, [BL] = DR, 65 [DB] = FR, [DF] = FL, [UF] = BL, [UB] = BR 66 }; 67 68 FstCube ret; 69 int i, ce, cs, cm; 70 int epe[4], eps[4], epm[4], epose[12], eposs[12], eposm[12]; 71 72 memset(epose, 0, 12*sizeof(int)); 73 memset(eposs, 0, 12*sizeof(int)); 74 memset(eposm, 0, 12*sizeof(int)); 75 76 for (i = 0, ce = 0; i < 12; i++) { 77 switch (edge_slice[ep[i]]) { 78 case 0: 79 epose[i] = 1; 80 epe[ce++] = eind[ep[i]]; 81 break; 82 case 1: 83 eposs[eptrans_fr[i]] = eind[ep[i]] + 1; 84 break; 85 default: 86 eposm[eptrans_rd[i]] = eind[ep[i]] + 1; 87 break; 88 } 89 } 90 91 for (i = 0, cs = 0, cm = 0; i < 12; i++) { 92 if (eposs[i]) { 93 eps[cs++] = eposs[i] - 1; 94 eposs[i] = 1; 95 } 96 if (eposm[i]) { 97 epm[cm++] = eposm[i] - 1; 98 eposm[i] = 1; 99 } 100 } 101 102 ret.uf_eposepe = subset_to_index(epose, 12, 4) * FACTORIAL4 + 103 perm_to_index(epe, 4); 104 ret.fr_eposepe = subset_to_index(eposs, 12, 4) * FACTORIAL4 + 105 perm_to_index(eps, 4); 106 ret.rd_eposepe = subset_to_index(eposm, 12, 4) * FACTORIAL4 + 107 perm_to_index(epm, 4); 108 109 return ret; 110 } 111 112 FstCube 113 fst_inverse(FstCube fst) 114 { 115 FstCube ret; 116 int ep_inv[12]; 117 118 ep_inv[FR] = fst_where_is_edge_arr[0][FR][fst.uf_eposepe]; 119 ep_inv[FL] = fst_where_is_edge_arr[0][FL][fst.uf_eposepe]; 120 ep_inv[BL] = fst_where_is_edge_arr[0][BL][fst.uf_eposepe]; 121 ep_inv[BR] = fst_where_is_edge_arr[0][BR][fst.uf_eposepe]; 122 123 ep_inv[UR] = fst_where_is_edge_arr[1][UR][fst.fr_eposepe]; 124 ep_inv[UL] = fst_where_is_edge_arr[1][UL][fst.fr_eposepe]; 125 ep_inv[DR] = fst_where_is_edge_arr[1][DR][fst.fr_eposepe]; 126 ep_inv[DL] = fst_where_is_edge_arr[1][DL][fst.fr_eposepe]; 127 128 ep_inv[UF] = fst_where_is_edge_arr[2][UF][fst.rd_eposepe]; 129 ep_inv[UB] = fst_where_is_edge_arr[2][UB][fst.rd_eposepe]; 130 ep_inv[DF] = fst_where_is_edge_arr[2][DF][fst.rd_eposepe]; 131 ep_inv[DB] = fst_where_is_edge_arr[2][DB][fst.rd_eposepe]; 132 133 ret = ep_to_fst_epos(ep_inv); 134 135 ret.uf_eofb = ((uint16_t)eo_invtable[0][fst.uf_eofb][fst.uf_eposepe]) | 136 ((uint16_t)eo_invtable[1][fst.uf_eofb][fst.fr_eposepe]) | 137 ((uint16_t)eo_invtable[2][fst.uf_eofb][fst.rd_eposepe]); 138 ret.fr_eofb = ((uint16_t)eo_invtable[0][fst.fr_eofb][fst.uf_eposepe]) | 139 ((uint16_t)eo_invtable[1][fst.fr_eofb][fst.fr_eposepe]) | 140 ((uint16_t)eo_invtable[2][fst.fr_eofb][fst.rd_eposepe]); 141 ret.rd_eofb = ((uint16_t)eo_invtable[0][fst.rd_eofb][fst.uf_eposepe]) | 142 ((uint16_t)eo_invtable[1][fst.rd_eofb][fst.fr_eposepe]) | 143 ((uint16_t)eo_invtable[2][fst.rd_eofb][fst.rd_eposepe]); 144 145 ret.uf_cp = inv_cp[fst.uf_cp]; 146 147 ret.uf_coud = inv_coud[fst.uf_cp][fst.uf_coud]; 148 ret.fr_coud = inv_coud[uf_cp_to_fr_cp[fst.uf_cp]][fst.fr_coud]; 149 ret.rd_coud = inv_coud[uf_cp_to_rd_cp[fst.uf_cp]][fst.rd_coud]; 150 151 return ret; 152 } 153 154 bool 155 fst_is_solved(FstCube fst) 156 { 157 /* We only check one orientation */ 158 159 return fst.uf_eofb == 0 && fst.uf_eposepe == 0 && 160 fst.uf_coud == 0 && fst.uf_cp == 0; 161 } 162 163 FstCube 164 fst_move(Move m, FstCube fst) 165 { 166 FstCube ret; 167 Move m_fr, m_rd; 168 169 m_fr = transform_move(fr, m); 170 m_rd = transform_move(rd, m); 171 172 ret.uf_eofb = coord_eofb.mtable[m][fst.uf_eofb]; 173 ret.uf_eposepe = coord_eposepe.mtable[m][fst.uf_eposepe]; 174 ret.uf_coud = coord_coud.mtable[m][fst.uf_coud]; 175 ret.uf_cp = coord_cp.mtable[m][fst.uf_cp]; 176 177 ret.fr_eofb = coord_eofb.mtable[m_fr][fst.fr_eofb]; 178 ret.fr_eposepe = coord_eposepe.mtable[m_fr][fst.fr_eposepe]; 179 ret.fr_coud = coord_coud.mtable[m_fr][fst.fr_coud]; 180 181 ret.rd_eofb = coord_eofb.mtable[m_rd][fst.rd_eofb]; 182 ret.rd_eposepe = coord_eposepe.mtable[m_rd][fst.rd_eposepe]; 183 ret.rd_coud = coord_coud.mtable[m_rd][fst.rd_coud]; 184 185 return ret; 186 } 187 188 void 189 fst_to_cube(FstCube fst, Cube *cube) 190 { 191 Cube e, s, m; 192 int i; 193 194 coord_eposepe.i[0]->to_cube(fst.uf_eposepe, &e); 195 coord_eposepe.i[0]->to_cube(fst.fr_eposepe, &s); 196 apply_trans(inverse_trans(fr), &s); 197 coord_eposepe.i[0]->to_cube(fst.rd_eposepe, &m); 198 apply_trans(inverse_trans(rd), &m); 199 200 for (i = 0; i < 12; i++) { 201 if (edge_slice[e.ep[i]] == 0) 202 cube->ep[i] = e.ep[i]; 203 if (edge_slice[s.ep[i]] == 1) 204 cube->ep[i] = s.ep[i]; 205 if (edge_slice[m.ep[i]] == 2) 206 cube->ep[i] = m.ep[i]; 207 } 208 209 coord_eofb.i[0]->to_cube((uint64_t)fst.uf_eofb, cube); 210 coord_coud.i[0]->to_cube((uint64_t)fst.uf_coud, cube); 211 coord_cp.i[0]->to_cube((uint64_t)fst.uf_cp, cube); 212 213 for (i = 0; i < 6; i++) 214 cube->xp[i] = i; 215 } 216 217 void 218 init_fst() 219 { 220 init_trans(); 221 gen_coord(&coord_eofb); 222 gen_coord(&coord_eposepe); 223 gen_coord(&coord_coud); 224 gen_coord(&coord_cp); 225 226 if (!read_fst_tables_file()) { 227 fprintf(stderr, 228 "Could not load fst_tables, generating them\n"); 229 init_fst_corner_invtables(); 230 init_fst_eo_invtables(); 231 init_fst_where_is_edge(); 232 if (!write_fst_tables_file()) 233 fprintf(stderr, "fst_tables could not be written\b"); 234 } 235 } 236 237 static void 238 init_fst_corner_invtables() 239 { 240 Cube c, d; 241 uint64_t cp, coud; 242 243 for (cp = 0; cp < FACTORIAL8; cp++) { 244 make_solved_corners(&c); 245 coord_cp.i[0]->to_cube(cp, &c); 246 247 copy_cube_corners(&c, &d); 248 invert_cube_corners(&d); 249 inv_cp[cp] = coord_cp.i[0]->index(&d); 250 251 for (coud = 0; coud < POW3TO7; coud++) { 252 copy_cube_corners(&c, &d); 253 coord_coud.i[0]->to_cube(coud, &d); 254 invert_cube_corners(&d); 255 inv_coud[cp][coud] = coord_coud.i[0]->index(&d); 256 } 257 258 copy_cube_corners(&c, &d); 259 apply_trans(fr, &d); 260 uf_cp_to_fr_cp[cp] = coord_cp.i[0]->index(&d); 261 262 copy_cube_corners(&c, &d); 263 apply_trans(rd, &d); 264 uf_cp_to_rd_cp[cp] = coord_cp.i[0]->index(&d); 265 } 266 } 267 268 static void 269 init_fst_eo_invtables() 270 { 271 uint64_t ep, eo; 272 Cube c, d; 273 274 for (ep = 0; ep < BINOM12ON4 * FACTORIAL4; ep++) { 275 make_solved(&c); 276 coord_eposepe.i[0]->to_cube(ep, &c); 277 for (eo = 0; eo < POW2TO11; eo++) { 278 copy_cube_edges(&c, &d); 279 coord_eofb.i[0]->to_cube(eo, &d); 280 init_fst_eo_update(eo, ep, 0, &d); 281 282 apply_trans(inverse_trans(fr), &d); 283 coord_eofb.i[0]->to_cube(eo, &d); 284 init_fst_eo_update(eo, ep, 1, &d); 285 286 copy_cube_edges(&c, &d); 287 apply_trans(inverse_trans(rd), &d); 288 coord_eofb.i[0]->to_cube(eo, &d); 289 init_fst_eo_update(eo, ep, 2, &d); 290 } 291 } 292 } 293 294 static void 295 init_fst_eo_update(uint64_t eo, uint64_t ep, int s, Cube *d) 296 { 297 int i; 298 299 for (i = 0; i < 12; i++) { 300 if (edge_slice[d->ep[i]] == s && d->eo[i] && d->ep[i] != 11) 301 eo_invtable[s][eo][ep] |= 302 ((uint16_t)1) << ((uint16_t)d->ep[i]); 303 } 304 } 305 306 static void 307 init_fst_where_is_edge() 308 { 309 Cube c, d; 310 uint64_t e; 311 312 make_solved(&c); 313 for (e = 0; e < BINOM12ON4 * FACTORIAL4; e++) { 314 coord_eposepe.i[0]->to_cube(e, &c); 315 316 copy_cube_edges(&c, &d); 317 fst_where_is_edge_arr[0][FR][e] = where_is_edge(FR, &d); 318 fst_where_is_edge_arr[0][FL][e] = where_is_edge(FL, &d); 319 fst_where_is_edge_arr[0][BL][e] = where_is_edge(BL, &d); 320 fst_where_is_edge_arr[0][BR][e] = where_is_edge(BR, &d); 321 322 copy_cube_edges(&c, &d); 323 apply_trans(inverse_trans(fr), &d); 324 fst_where_is_edge_arr[1][UL][e] = where_is_edge(UL, &d); 325 fst_where_is_edge_arr[1][UR][e] = where_is_edge(UR, &d); 326 fst_where_is_edge_arr[1][DL][e] = where_is_edge(DL, &d); 327 fst_where_is_edge_arr[1][DR][e] = where_is_edge(DR, &d); 328 329 copy_cube_edges(&c, &d); 330 apply_trans(inverse_trans(rd), &d); 331 fst_where_is_edge_arr[2][UF][e] = where_is_edge(UF, &d); 332 fst_where_is_edge_arr[2][UB][e] = where_is_edge(UB, &d); 333 fst_where_is_edge_arr[2][DF][e] = where_is_edge(DF, &d); 334 fst_where_is_edge_arr[2][DB][e] = where_is_edge(DB, &d); 335 } 336 } 337 338 static bool 339 read_fst_tables_file() 340 { 341 init_env(); 342 343 FILE *f; 344 char fname[strlen(tabledir)+256]; 345 uint64_t i, j, r, total; 346 347 strcpy(fname, tabledir); 348 strcat(fname, "/fst_tables"); 349 350 if ((f = fopen(fname, "rb")) == NULL) 351 return false; 352 353 r = 0; 354 total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); 355 356 for (i = 0; i < FACTORIAL8; i++) 357 r += fread(inv_coud[i], sizeof(uint16_t), POW3TO7, f); 358 r += fread(inv_cp, sizeof(uint16_t), FACTORIAL8, f); 359 r += fread(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); 360 r += fread(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); 361 for (i = 0; i < 3; i++) 362 for (j = 0; j < POW2TO11; j++) 363 r += fread(eo_invtable[i][j], 364 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); 365 for (i = 0; i < 3; i++) 366 for (j = 0; j < 12; j++) 367 r += fread(fst_where_is_edge_arr[i][j], 368 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); 369 370 fclose(f); 371 372 return r == total; 373 } 374 375 static bool 376 write_fst_tables_file() 377 { 378 init_env(); 379 380 FILE *f; 381 char fname[strlen(tabledir)+256]; 382 uint64_t i, j, w, total; 383 384 strcpy(fname, tabledir); 385 strcat(fname, "/fst_tables"); 386 387 if ((f = fopen(fname, "wb")) == NULL) 388 return false; 389 390 w = 0; 391 total = FACTORIAL8*(POW3TO7+3) + 3*BINOM12ON4*FACTORIAL4*(12+POW2TO11); 392 393 for (i = 0; i < FACTORIAL8; i++) 394 w += fwrite(inv_coud[i], sizeof(uint16_t), POW3TO7, f); 395 w += fwrite(inv_cp, sizeof(uint16_t), FACTORIAL8, f); 396 w += fwrite(uf_cp_to_fr_cp, sizeof(uint16_t), FACTORIAL8, f); 397 w += fwrite(uf_cp_to_rd_cp, sizeof(uint16_t), FACTORIAL8, f); 398 for (i = 0; i < 3; i++) 399 for (j = 0; j < POW2TO11; j++) 400 w += fwrite(eo_invtable[i][j], 401 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); 402 for (i = 0; i < 3; i++) 403 for (j = 0; j < 12; j++) 404 w += fwrite(fst_where_is_edge_arr[i][j], 405 sizeof(uint16_t), BINOM12ON4*FACTORIAL4, f); 406 407 fclose(f); 408 409 return w == total; 410 }