symcoord.c (15903B)
1 #include "symcoord.h" 2 3 /* These constants have been computed generating the respective SymData */ 4 #define CLASSES_CP_16 2768 5 #define CLASSES_EOFBEPOS_16 64430 6 7 static uint64_t index_cp_sym16(Cube cube); 8 static uint64_t index_eofbepos_sym16(Cube cube); 9 static uint64_t index_drud_sym16(Cube cube); 10 static uint64_t index_drudfin_noE_sym16(Cube cube); 11 static uint64_t index_nxopt31(Cube cube); 12 13 static uint64_t move_cp_sym16(Move m, uint64_t ind); 14 static uint64_t move_eofbepos_sym16(Move m, uint64_t ind); 15 static uint64_t move_drud_sym16(Move m, uint64_t ind); 16 static uint64_t move_drudfin_noE_sym16(Move m, uint64_t ind); 17 static uint64_t move_nxopt31(Move m, uint64_t ind); 18 19 static int tfind_from_mask(uint64_t mask, Trans *ret); 20 static int tfind_drud_sym16(uint64_t ind, Trans *ret); 21 static int tfind_drudfin_noE_sym16(uint64_t ind, Trans *ret); 22 static int tfind_nxopt31(uint64_t ind, Trans *ret); 23 24 static uint64_t transform_cp(Trans t, uint64_t ind); 25 static uint64_t transform_eofbepos(Trans t, uint64_t ind); 26 static uint64_t transform_drud_sym16(Trans t, uint64_t ind); 27 static uint64_t transform_drudfin_noE_sym16(Trans t, uint64_t ind); 28 static uint64_t transform_nxopt31(Trans t, uint64_t ind); 29 30 static void gensym(SymData *sd); 31 static void init_symc_moves(void); 32 static void init_symc_trans(void); 33 static bool read_symdata_file(SymData *sd); 34 static bool read_symc_moves_file(void); 35 static bool read_symc_trans_file(void); 36 static bool write_symdata_file(SymData *sd); 37 static bool write_symc_moves_file(void); 38 static bool write_symc_trans_file(void); 39 40 /* Some tables ***************************************************************/ 41 42 static uint64_t move_cp_16[NMOVES][CLASSES_CP_16]; 43 static uint64_t move_eofbepos_16[NMOVES][CLASSES_EOFBEPOS_16]; 44 45 static int trans_eofbepos[NTRANS][POW2TO11*BINOM12ON4]; 46 static int trans_epud[NTRANS][FACTORIAL8]; 47 static int trans_cpud_separate[NTRANS][BINOM8ON4]; 48 49 static Trans ttrep_move_cp_16[NMOVES][CLASSES_CP_16]; 50 static Trans ttrep_move_eofbepos_16[NMOVES][CLASSES_EOFBEPOS_16]; 51 52 53 /* Transformation groups and symmetry data ***********************************/ 54 55 static Trans 56 trans_group_udfix[16] = { 57 uf, ur, ub, ul, 58 df, dr, db, dl, 59 uf_mirror, ur_mirror, ub_mirror, ul_mirror, 60 df_mirror, dr_mirror, db_mirror, dl_mirror, 61 }; 62 63 static SymData 64 sd_cp_16 = { 65 .filename = "sd_cp_16_new", 66 .coord = &coord_cp, 67 .sym_coord = &coord_cp_sym16, 68 .ntrans = 16, 69 .trans = trans_group_udfix, 70 .transform = transform_cp, 71 }; 72 73 static SymData 74 sd_eofbepos_16 = { 75 .filename = "sd_eofbepos_16_new", 76 .coord = &coord_eofbepos, 77 .sym_coord = &coord_eofbepos_sym16, 78 .ntrans = 16, 79 .trans = trans_group_udfix, 80 .transform = transform_eofbepos, 81 }; 82 83 SymData * all_sd[] = { 84 &sd_cp_16, 85 &sd_eofbepos_16, 86 NULL 87 }; 88 89 90 /* Coordinates and their implementation **************************************/ 91 92 Coordinate 93 coord_eofbepos_sym16 = { 94 .index = index_eofbepos_sym16, 95 .move = move_eofbepos_sym16, 96 }; 97 98 Coordinate 99 coord_cp_sym16 = { 100 .index = index_cp_sym16, 101 .move = move_cp_sym16, 102 }; 103 104 Coordinate 105 coord_drud_sym16 = { 106 .index = index_drud_sym16, 107 .move = move_drud_sym16, 108 .max = POW3TO7 * CLASSES_EOFBEPOS_16, 109 .base = &coord_eofbepos_sym16, 110 .transform = transform_drud_sym16, 111 .tfind = tfind_drud_sym16, 112 }; 113 114 Coordinate 115 coord_drudfin_noE_sym16 = { 116 .index = index_drudfin_noE_sym16, 117 .move = move_drudfin_noE_sym16, 118 .max = FACTORIAL8 * CLASSES_CP_16, 119 .base = &coord_cp_sym16, 120 .transform = transform_drudfin_noE_sym16, 121 .tfind = tfind_drudfin_noE_sym16, 122 }; 123 124 Coordinate 125 coord_nxopt31 = { 126 .index = index_nxopt31, 127 .move = move_nxopt31, 128 .max = POW3TO7 * BINOM8ON4 * CLASSES_EOFBEPOS_16, 129 .base = &coord_eofbepos_sym16, 130 .transform = transform_nxopt31, 131 .tfind = tfind_nxopt31, 132 }; 133 134 /* Functions *****************************************************************/ 135 136 static uint64_t 137 index_cp_sym16(Cube cube) 138 { 139 return sd_cp_16.class[coord_cp.index(cube)]; 140 } 141 142 static uint64_t 143 index_drud_sym16(Cube cube) 144 { 145 Trans t; 146 147 t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)]; 148 149 return index_eofbepos_sym16(cube) * POW3TO7 + co_ttable[t][cube.coud]; 150 } 151 152 static uint64_t 153 index_drudfin_noE_sym16(Cube cube) 154 { 155 Trans t; 156 Cube c; 157 158 t = sd_cp_16.transtorep[coord_cp.index(cube)]; 159 c = apply_trans(t, cube); 160 161 /* TODO: add transform to coord_epud to make this faster */ 162 return index_cp_sym16(c) * FACTORIAL8 + coord_epud.index(c); 163 } 164 165 static uint64_t 166 index_eofbepos_sym16(Cube cube) 167 { 168 return sd_eofbepos_16.class[coord_eofbepos.index(cube)]; 169 } 170 171 static uint64_t 172 index_nxopt31(Cube cube) 173 { 174 Trans t; 175 uint64_t a; 176 int coud, cp; 177 178 t = sd_eofbepos_16.transtorep[coord_eofbepos.index(cube)]; 179 coud = co_ttable[t][cube.coud]; 180 cp = cp_ttable[t][cube.cp]; 181 a = (index_eofbepos_sym16(cube)*POW3TO7) + coud; 182 183 return a * BINOM8ON4 + coord_cpud_separate.index((Cube){.cp = cp}); 184 } 185 186 static uint64_t 187 move_cp_sym16(Move m, uint64_t ind) 188 { 189 return move_cp_16[m][ind]; 190 } 191 192 static uint64_t 193 move_eofbepos_sym16(Move m, uint64_t ind) 194 { 195 return move_eofbepos_16[m][ind]; 196 } 197 198 static uint64_t 199 move_drud_sym16(Move m, uint64_t ind) 200 { 201 uint64_t coud, eofbepos; 202 Trans ttr; 203 204 eofbepos = move_eofbepos_16[m][ind / POW3TO7]; 205 ttr = ttrep_move_eofbepos_16[m][ind / POW3TO7]; 206 coud = coud_mtable[m][ind % POW3TO7]; 207 coud = co_ttable[ttr][coud]; /* Source is always coud */ 208 209 return eofbepos * POW3TO7 + coud; 210 } 211 212 static uint64_t 213 move_drudfin_noE_sym16(Move m, uint64_t ind) 214 { 215 uint64_t cp, epud; 216 Trans ttr; 217 218 cp = move_cp_16[m][ind / FACTORIAL8]; 219 ttr = ttrep_move_cp_16[m][ind / FACTORIAL8]; 220 epud = coord_epud.move(m, ind % FACTORIAL8); 221 epud = trans_epud[ttr][epud]; 222 223 return cp * FACTORIAL8 + epud; 224 } 225 226 static uint64_t 227 move_nxopt31(Move m, uint64_t ind) 228 { 229 uint64_t eofbepos, cpsep, coud; 230 Trans ttr; 231 232 eofbepos = ind / (POW3TO7 * BINOM8ON4); 233 coud = (ind / BINOM8ON4) % POW3TO7; 234 cpsep = ind % BINOM8ON4; 235 236 ttr = ttrep_move_eofbepos_16[m][eofbepos]; 237 eofbepos = move_eofbepos_16[m][eofbepos]; 238 coud = coud_mtable[m][coud]; 239 coud = co_ttable[ttr][coud]; /* Source is always coud */ 240 cpsep = coord_cpud_separate.move(m, cpsep); 241 cpsep = trans_cpud_separate[ttr][cpsep]; 242 243 return (eofbepos * POW3TO7 + coud) * BINOM8ON4 + cpsep; 244 } 245 246 static uint64_t 247 transform_cp(Trans t, uint64_t ind) 248 { 249 return cp_ttable[t][ind]; 250 } 251 252 static uint64_t 253 transform_eofbepos(Trans t, uint64_t ind) 254 { 255 return trans_eofbepos[t][ind]; 256 } 257 258 static uint64_t 259 transform_drud_sym16(Trans t, uint64_t ind) 260 { 261 uint64_t coud, eofbepos; 262 263 eofbepos = ind / POW3TO7; /* Assum trans fixes eofbepos */ 264 coud = co_ttable[t][ind % POW3TO7]; /* Source is always coud */ 265 266 return eofbepos * POW3TO7 + coud; 267 } 268 269 static uint64_t 270 transform_drudfin_noE_sym16(Trans t, uint64_t ind) 271 { 272 uint64_t cp, epud; 273 274 cp = ind / FACTORIAL8; /* Assume trans fixes cp */ 275 epud = trans_epud[t][ind % FACTORIAL8]; 276 277 return cp * FACTORIAL8 + epud; 278 } 279 280 static uint64_t 281 transform_nxopt31(Trans t, uint64_t ind) 282 { 283 uint64_t eofbepos, cpsep, coud; 284 285 eofbepos = ind / (POW3TO7 * BINOM8ON4); 286 coud = (ind / BINOM8ON4) % POW3TO7; 287 cpsep = ind % BINOM8ON4; 288 289 coud = co_ttable[t][coud]; /* Source is always coud */ 290 cpsep = trans_cpud_separate[t][cpsep]; 291 292 return (eofbepos * POW3TO7 + coud) * BINOM8ON4 + cpsep; 293 } 294 295 static int 296 tfind_from_mask(uint64_t mask, Trans *ret) 297 { 298 Trans t; 299 int i = 0; 300 301 for (t = uf; t < NTRANS; t++) 302 if (((uint64_t)1 << t) & mask) 303 ret[i++] = t; 304 305 return i; 306 } 307 308 static int 309 tfind_drud_sym16(uint64_t ind, Trans *ret) 310 { 311 uint64_t mask = sd_eofbepos_16.selfsim[ind / POW3TO7]; 312 313 return tfind_from_mask(mask, ret); 314 } 315 316 static int 317 tfind_drudfin_noE_sym16(uint64_t ind, Trans *ret) 318 { 319 uint64_t mask = sd_cp_16.selfsim[ind / FACTORIAL8]; 320 321 return tfind_from_mask(mask, ret); 322 } 323 324 static int 325 tfind_nxopt31(uint64_t ind, Trans *ret) 326 { 327 uint64_t mask = sd_eofbepos_16.selfsim[ind / (POW3TO7 * BINOM8ON4)]; 328 329 return tfind_from_mask(mask, ret); 330 } 331 332 /* Other functions ***********************************************************/ 333 334 void 335 free_sd(SymData *sd) 336 { 337 if (sd->generated) { 338 free(sd->class); 339 free(sd->unsym); 340 free(sd->transtorep); 341 } 342 343 sd->generated = false; 344 } 345 346 static void 347 gensym(SymData *sd) 348 { 349 uint64_t i, in, nreps = 0; 350 Trans t; 351 int j; 352 353 if (sd->generated) 354 return; 355 356 sd->class = malloc(sd->coord->max * sizeof(uint64_t)); 357 sd->unsym = malloc(sd->coord->max * sizeof(uint64_t)); 358 sd->transtorep = malloc(sd->coord->max * sizeof(Trans)); 359 sd->selfsim = malloc(sd->coord->max * sizeof(uint64_t)); 360 361 if (read_symdata_file(sd)) { 362 sd->generated = true; 363 return; 364 } 365 366 fprintf(stderr, "Cannot load %s, generating it\n", sd->filename); 367 368 for (i = 0; i < sd->coord->max; i++) 369 sd->class[i] = sd->coord->max + 1; 370 371 for (i = 0; i < sd->coord->max; i++) { 372 if (sd->class[i] == sd->coord->max + 1) { 373 sd->unsym[nreps] = i; 374 sd->transtorep[i] = uf; 375 sd->selfsim[nreps] = (uint64_t)0; 376 for (j = 0; j < sd->ntrans; j++) { 377 t = sd->trans[j]; 378 in = sd->transform(t, i); 379 sd->class[in] = nreps; 380 if (in == i) 381 sd->selfsim[nreps] |= 382 ((uint64_t)1 << t); 383 else 384 sd->transtorep[in] = inverse_trans(t); 385 } 386 nreps++; 387 } 388 } 389 390 sd->sym_coord->max = nreps; 391 sd->unsym = realloc(sd->unsym, nreps * sizeof(uint64_t)); 392 sd->selfsim = realloc(sd->selfsim, nreps * sizeof(uint64_t)); 393 sd->generated = true; 394 395 fprintf(stderr, "Found %" PRIu64 " classes\n", nreps); 396 397 if (!write_symdata_file(sd)) 398 fprintf(stderr, "Error writing SymData file\n"); 399 400 return; 401 } 402 403 static bool 404 read_symdata_file(SymData *sd) 405 { 406 init_env(); 407 408 FILE *f; 409 char fname[strlen(tabledir)+100]; 410 uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; 411 bool r = true; 412 413 strcpy(fname, tabledir); 414 strcat(fname, "/"); 415 strcat(fname, sd->filename); 416 417 if ((f = fopen(fname, "rb")) == NULL) 418 return false; 419 420 r = r && fread(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; 421 r = r && fread(sd->unsym, sizeof(uint64_t), *sn, f) == *sn; 422 r = r && fread(sd->selfsim, sizeof(uint64_t), *sn, f) == *sn; 423 r = r && fread(sd->class, sizeof(uint64_t), n, f) == n; 424 r = r && fread(sd->transtorep, sizeof(Trans), n, f) == n; 425 426 fclose(f); 427 return r; 428 } 429 430 static bool 431 read_symc_moves_file(void) 432 { 433 init_env(); 434 435 Move m; 436 bool r = true; 437 FILE *f; 438 char fname[strlen(tabledir)+100]; 439 440 strcpy(fname, tabledir); 441 strcat(fname, "/symc_moves"); 442 443 if ((f = fopen(fname, "rb")) == NULL) 444 return false; 445 446 for (m = 0; m < NMOVES; m++) { 447 r = r && fread(move_cp_16[m], sizeof(uint64_t), 448 CLASSES_CP_16, f) == CLASSES_CP_16; 449 r = r && fread(move_eofbepos_16[m], sizeof(uint64_t), 450 CLASSES_EOFBEPOS_16, f) == CLASSES_EOFBEPOS_16; 451 452 r = r && fread(ttrep_move_cp_16[m], sizeof(Trans), 453 CLASSES_CP_16, f) == CLASSES_CP_16; 454 r = r && fread(ttrep_move_eofbepos_16[m], sizeof(Trans), 455 CLASSES_EOFBEPOS_16, f) == CLASSES_EOFBEPOS_16; 456 } 457 458 fclose(f); 459 return r; 460 } 461 462 static bool 463 read_symc_trans_file(void) 464 { 465 init_env(); 466 467 Trans t; 468 bool r = true; 469 FILE *f; 470 char fname[strlen(tabledir)+100]; 471 472 strcpy(fname, tabledir); 473 strcat(fname, "/symc_trans"); 474 475 if ((f = fopen(fname, "rb")) == NULL) 476 return false; 477 478 for (t = 0; t < NTRANS; t++) { 479 r = r && fread(trans_eofbepos[t], sizeof(int), 480 POW2TO11*BINOM12ON4, f) == POW2TO11*BINOM12ON4; 481 r = r && fread(trans_epud[t], sizeof(int), 482 FACTORIAL8, f) == FACTORIAL8; 483 r = r && fread(trans_cpud_separate[t], sizeof(int), 484 BINOM8ON4, f) == BINOM8ON4; 485 } 486 487 fclose(f); 488 return r; 489 } 490 491 static bool 492 write_symdata_file(SymData *sd) 493 { 494 init_env(); 495 496 FILE *f; 497 char fname[strlen(tabledir)+100]; 498 uint64_t n = sd->coord->max, *sn = &sd->sym_coord->max; 499 bool r = true; 500 501 strcpy(fname, tabledir); 502 strcat(fname, "/"); 503 strcat(fname, sd->filename); 504 505 if ((f = fopen(fname, "wb")) == NULL) 506 return false; 507 508 r = r && fwrite(&sd->sym_coord->max, sizeof(uint64_t), 1, f) == 1; 509 r = r && fwrite(sd->unsym, sizeof(uint64_t), *sn, f) == *sn; 510 r = r && fwrite(sd->selfsim, sizeof(uint64_t), *sn, f) == *sn; 511 r = r && fwrite(sd->class, sizeof(uint64_t), n, f) == n; 512 r = r && fwrite(sd->transtorep, sizeof(Trans), n, f) == n; 513 514 fclose(f); 515 return r; 516 } 517 518 static bool 519 write_symc_moves_file(void) 520 { 521 init_env(); 522 523 Move m; 524 bool r = true; 525 FILE *f; 526 char fname[strlen(tabledir)+100]; 527 528 strcpy(fname, tabledir); 529 strcat(fname, "/symc_moves"); 530 531 if ((f = fopen(fname, "wb")) == NULL) 532 return false; 533 534 for (m = 0; m < NMOVES; m++) { 535 r = r && fwrite(move_cp_16[m], sizeof(uint64_t), 536 CLASSES_CP_16, f) == CLASSES_CP_16; 537 r = r && fwrite(move_eofbepos_16[m], sizeof(uint64_t), 538 CLASSES_EOFBEPOS_16, f) == CLASSES_EOFBEPOS_16; 539 540 r = r && fwrite(ttrep_move_cp_16[m], sizeof(Trans), 541 CLASSES_CP_16, f) == CLASSES_CP_16; 542 r = r && fwrite(ttrep_move_eofbepos_16[m], sizeof(Trans), 543 CLASSES_EOFBEPOS_16, f) == CLASSES_EOFBEPOS_16; 544 } 545 546 fclose(f); 547 return r; 548 } 549 550 static bool 551 write_symc_trans_file(void) 552 { 553 init_env(); 554 555 Trans t; 556 bool r = true; 557 FILE *f; 558 char fname[strlen(tabledir)+100]; 559 560 strcpy(fname, tabledir); 561 strcat(fname, "/symc_trans"); 562 563 if ((f = fopen(fname, "wb")) == NULL) 564 return false; 565 566 for (t = 0; t < NTRANS; t++) { 567 r = r && fwrite(trans_eofbepos[t], sizeof(int), 568 POW2TO11*BINOM12ON4, f) == POW2TO11*BINOM12ON4; 569 r = r && fwrite(trans_epud[t], sizeof(int), 570 FACTORIAL8, f) == FACTORIAL8; 571 r = r && fwrite(trans_cpud_separate[t], sizeof(int), 572 BINOM8ON4, f) == BINOM8ON4; 573 } 574 575 fclose(f); 576 return r; 577 } 578 579 static void 580 init_symc_moves(void) 581 { 582 uint64_t i, ii, coo; 583 Move j; 584 585 if (read_symc_moves_file()) 586 return; 587 588 for (i = 0; i < CLASSES_CP_16; i++) { 589 ii = sd_cp_16.unsym[i]; 590 for (j = 0; j < NMOVES; j++) { 591 coo = sd_cp_16.coord->move(j, ii); 592 move_cp_16[j][i] = sd_cp_16.class[coo]; 593 ttrep_move_cp_16[j][i] = sd_cp_16.transtorep[coo]; 594 } 595 } 596 597 for (i = 0; i < CLASSES_EOFBEPOS_16; i++) { 598 ii = sd_eofbepos_16.unsym[i]; 599 for (j = 0; j < NMOVES; j++) { 600 coo = sd_eofbepos_16.coord->move(j, ii); 601 move_eofbepos_16[j][i] = sd_eofbepos_16.class[coo]; 602 ttrep_move_eofbepos_16[j][i] = 603 sd_eofbepos_16.transtorep[coo]; 604 } 605 } 606 607 if (!write_symc_moves_file()) 608 fprintf(stderr, "Error writing SymMoves file\n"); 609 } 610 611 void 612 init_symc_trans(void) 613 { 614 uint64_t i; 615 int j, cp; 616 int epe[4] = {FR, FL, BL, BR}; 617 int a[12] = { [8] = 8, [9] = 9, [10] = 10, [11] = 11 }; 618 Cube c; 619 CubeArray *arr, *aux; 620 Trans t; 621 622 if (read_symc_trans_file()) 623 return; 624 625 for (i = 0; i < POW2TO11*BINOM12ON4; i++) { 626 for (j = 0; j < 16; j++) { 627 t = trans_group_udfix[j]; 628 629 arr = new_cubearray((Cube){0}, pf_edges); 630 int_to_sum_zero_array(i % POW2TO11, 2, 12, arr->eofb); 631 epos_to_compatible_ep((i / POW2TO11)*24, arr->ep, epe); 632 fix_eorleoud(arr); 633 c = arrays_to_cube(arr, pf_edges); 634 free_cubearray(arr, pf_edges); 635 636 c = apply_trans(t, c); 637 trans_eofbepos[t][i] = (c.epose/24)*POW2TO11 + c.eofb; 638 } 639 } 640 641 aux = malloc(sizeof(CubeArray)); 642 aux->ep = a; 643 for (i = 0; i < FACTORIAL8; i++) { 644 index_to_perm(i, 8, a); 645 c = arrays_to_cube(aux, pf_ep); 646 for (j = 0; j < 16; j++) { 647 t = trans_group_udfix[j]; 648 arr = new_cubearray(apply_trans(t, c), pf_ep); 649 trans_epud[t][i] = perm_to_index(arr->ep, 8); 650 free_cubearray(arr, pf_ep); 651 } 652 } 653 free(aux); 654 655 for (i = 0; i < BINOM8ON4; i++) { 656 cp = cpud_separate_ant[i]; 657 for (j = 0; j < 16; j++) { 658 t = trans_group_udfix[j]; 659 trans_cpud_separate[t][i] = 660 cpud_separate_ind[cp_ttable[t][cp]]; 661 } 662 } 663 664 if (!write_symc_trans_file()) 665 fprintf(stderr, "Error writing SymTrans file\n"); 666 } 667 668 void 669 init_symcoord(void) 670 { 671 int i; 672 673 static bool initialized = false; 674 if (initialized) 675 return; 676 initialized = true; 677 678 init_coord(); 679 680 init_symc_trans(); 681 682 for (i = 0; all_sd[i] != NULL; i++) 683 gensym(all_sd[i]); 684 685 init_symc_moves(); 686 } 687