coord.c (13514B)
1 #define COORD_C 2 3 #include "coord.h" 4 5 static void gen_coord_comp(Coordinate *coord); 6 static void gen_coord_sym(Coordinate *coord); 7 static bool read_coord_mtable(Coordinate *coord); 8 static bool read_coord_sd(Coordinate *coord); 9 static bool read_coord_ttable(Coordinate *coord); 10 static bool write_coord_mtable(Coordinate *coord); 11 static bool write_coord_sd(Coordinate *coord); 12 static bool write_coord_ttable(Coordinate *coord); 13 14 /* Indexers ******************************************************************/ 15 16 uint64_t 17 index_eofb(Cube *cube) 18 { 19 return (uint64_t)digit_array_to_int(cube->eo, 11, 2); 20 } 21 22 uint64_t 23 index_coud(Cube *cube) 24 { 25 return (uint64_t)digit_array_to_int(cube->co, 7, 3); 26 } 27 28 uint64_t 29 index_cp(Cube *cube) 30 { 31 return (uint64_t)perm_to_index(cube->cp, 8); 32 } 33 34 uint64_t 35 index_cpudsep(Cube *cube) 36 { 37 int i, c[8]; 38 39 for (i = 0; i < 8; i++) 40 c[i] = cube->cp[i] < 4 ? 0 : 1; 41 42 return (uint64_t)subset_to_index(c, 8, 4); 43 } 44 45 uint64_t 46 index_epe(Cube *cube) 47 { 48 int i, e[4]; 49 50 for (i = 0; i < 4; i++) 51 e[i] = cube->ep[i+8] - 8; 52 53 return (uint64_t)perm_to_index(e, 4); 54 } 55 56 uint64_t 57 index_epud(Cube *cube) 58 { 59 return (uint64_t)perm_to_index(cube->ep, 8); 60 } 61 62 uint64_t 63 index_epos(Cube *cube) 64 { 65 int i, a[12]; 66 67 for (i = 0; i < 12; i++) 68 a[i] = (cube->ep[i] < 8) ? 0 : 1; 69 70 return (uint64_t)subset_to_index(a, 12, 4); 71 } 72 73 uint64_t 74 index_eposepe(Cube *cube) 75 { 76 int i, j, e[4]; 77 uint64_t epos, epe; 78 79 epos = (uint64_t)index_epos(cube); 80 for (i = 0, j = 0; i < 12; i++) 81 if (cube->ep[i] >= 8) 82 e[j++] = cube->ep[i] - 8; 83 epe = (uint64_t)perm_to_index(e, 4); 84 85 return epos * FACTORIAL4 + epe; 86 } 87 88 /* Inverse indexers **********************************************************/ 89 90 void 91 invindex_eofb(uint64_t ind, Cube *cube) 92 { 93 int_to_sum_zero_array(ind, 2, 12, cube->eo); 94 } 95 96 void 97 invindex_coud(uint64_t ind, Cube *cube) 98 { 99 int_to_sum_zero_array(ind, 3, 8, cube->co); 100 } 101 102 void 103 invindex_cp(uint64_t ind, Cube *cube) 104 { 105 index_to_perm(ind, 8, cube->cp); 106 } 107 108 void 109 invindex_cpudsep(uint64_t ind, Cube *cube) 110 { 111 int i, j, k, c[8]; 112 113 index_to_subset(ind, 8, 4, c); 114 for (i = 0, j = 0, k = 4; i < 8; i++) 115 cube->cp[i] = c[i] == 0 ? j++ : k++; 116 } 117 118 119 void 120 invindex_epe(uint64_t ind, Cube *cube) 121 { 122 int i; 123 124 index_to_perm(ind, 4, &cube->ep[8]); 125 for (i = 0; i < 4; i++) 126 cube->ep[i+8] += 8; 127 } 128 129 void 130 invindex_epud(uint64_t ind, Cube *cube) 131 { 132 index_to_perm(ind, 8, cube->ep); 133 } 134 135 void 136 invindex_epos(uint64_t ind, Cube *cube) 137 { 138 int i, j, k; 139 140 index_to_subset(ind, 12, 4, cube->ep); 141 for (i = 0, j = 0, k = 8; i < 12; i++) 142 if (cube->ep[i] == 0) 143 cube->ep[i] = j++; 144 else 145 cube->ep[i] = k++; 146 } 147 148 void 149 invindex_eposepe(uint64_t ind, Cube *cube) 150 { 151 int i, j, k, e[4]; 152 uint64_t epos, epe; 153 154 epos = ind / FACTORIAL4; 155 epe = ind % FACTORIAL4; 156 157 index_to_subset(epos, 12, 4, cube->ep); 158 index_to_perm(epe, 4, e); 159 160 for (i = 0, j = 0, k = 0; i < 12; i++) 161 if (cube->ep[i] == 0) 162 cube->ep[i] = j++; 163 else 164 cube->ep[i] = e[k++] + 8; 165 } 166 167 /* Other local functions *****************************************************/ 168 169 uint64_t 170 indexers_getmax(Indexer **is) 171 { 172 int i; 173 uint64_t max = 1; 174 175 for (i = 0; is[i] != NULL; i++) 176 max *= is[i]->n; 177 178 return max; 179 } 180 181 uint64_t 182 indexers_getind(Indexer **is, Cube *c) 183 { 184 int i; 185 uint64_t max = 0; 186 187 for (i = 0; is[i] != NULL; i++) { 188 max *= is[i]->n; 189 max += is[i]->index(c); 190 } 191 192 return max; 193 } 194 195 void 196 indexers_makecube(Indexer **is, uint64_t ind, Cube *c) 197 { 198 /* Warning: anti-indexers are applied in the same order as indexers. */ 199 /* We assume order does not matter, but it would make more sense to */ 200 /* apply them in reverse. */ 201 202 int i; 203 uint64_t m; 204 205 make_solved(c); 206 m = indexers_getmax(is); 207 for (i = 0; is[i] != NULL; i++) { 208 m /= is[i]->n; 209 is[i]->to_cube(ind / m, c); 210 ind %= m; 211 } 212 } 213 214 static void 215 gen_coord_comp(Coordinate *coord) 216 { 217 uint64_t ui; 218 Cube c, mvd; 219 Move m; 220 Trans t; 221 222 coord->max = indexers_getmax(coord->i); 223 224 for (m = 0; m < NMOVES; m++) 225 coord->mtable[m] = malloc(coord->max * sizeof(uint64_t)); 226 227 for (t = 0; t < NTRANS; t++) 228 coord->ttable[t] = malloc(coord->max * sizeof(uint64_t)); 229 230 if (!read_coord_mtable(coord)) { 231 fprintf(stderr, "%s: generating mtable\n", coord->name); 232 233 for (ui = 0; ui < coord->max; ui++) { 234 indexers_makecube(coord->i, ui, &c); 235 for (m = 0; m < NMOVES; m++) { 236 copy_cube(&c, &mvd); 237 apply_move(m, &mvd); 238 coord->mtable[m][ui] = 239 indexers_getind(coord->i, &mvd); 240 } 241 } 242 if (!write_coord_mtable(coord)) 243 fprintf(stderr, "%s: error writing mtable\n", 244 coord->name); 245 246 fprintf(stderr, "%s: mtable generated\n", coord->name); 247 } 248 249 if (!read_coord_ttable(coord)) { 250 fprintf(stderr, "%s: generating ttable\n", coord->name); 251 252 for (ui = 0; ui < coord->max; ui++) { 253 indexers_makecube(coord->i, ui, &c); 254 for (t = 0; t < NTRANS; t++) { 255 copy_cube(&c, &mvd); 256 apply_trans(t, &mvd); 257 coord->ttable[t][ui] = 258 indexers_getind(coord->i, &mvd); 259 } 260 } 261 if (!write_coord_ttable(coord)) 262 fprintf(stderr, "%s: error writing ttable\n", 263 coord->name); 264 } 265 } 266 267 static void 268 gen_coord_sym(Coordinate *coord) 269 { 270 uint64_t i, in, ui, uj, uu, M, nr; 271 int j; 272 Move m; 273 Trans t; 274 275 M = coord->base[0]->max; 276 coord->selfsim = malloc(M * sizeof(uint64_t)); 277 coord->symclass = malloc(M * sizeof(uint64_t)); 278 coord->symrep = malloc(M * sizeof(uint64_t)); 279 coord->transtorep = malloc(M * sizeof(Trans)); 280 281 if (!read_coord_sd(coord)) { 282 fprintf(stderr, "%s: generating syms\n", coord->name); 283 284 for (i = 0; i < M; i++) 285 coord->symclass[i] = M+1; 286 287 for (i = 0, nr = 0; i < M; i++) { 288 if (coord->symclass[i] != M+1) 289 continue; 290 291 coord->symrep[nr] = i; 292 coord->transtorep[i] = uf; 293 coord->selfsim[nr] = (uint64_t)0; 294 for (j = 0; j < coord->tgrp->n; j++) { 295 t = coord->tgrp->t[j]; 296 in = trans_coord(coord->base[0], t, i); 297 coord->symclass[in] = nr; 298 if (in == i) 299 coord->selfsim[nr] |= ((uint64_t)1<<t); 300 else 301 coord->transtorep[in] = 302 inverse_trans(t); 303 } 304 nr++; 305 } 306 307 coord->max = nr; 308 309 fprintf(stderr, "%s: found %" PRIu64 " classes\n", 310 coord->name, nr); 311 if (!write_coord_sd(coord)) 312 fprintf(stderr, "%s: error writing symdata\n", 313 coord->name); 314 } 315 316 coord->symrep = realloc(coord->symrep, coord->max*sizeof(uint64_t)); 317 coord->selfsim = realloc(coord->selfsim, coord->max*sizeof(uint64_t)); 318 319 for (m = 0; m < NMOVES; m++) { 320 coord->mtable[m] = malloc(coord->max*sizeof(uint64_t)); 321 coord->ttrep_move[m] = malloc(coord->max*sizeof(Trans)); 322 } 323 324 if (!read_coord_mtable(coord)) { 325 for (ui = 0; ui < coord->max; ui++) { 326 uu = coord->symrep[ui]; 327 for (m = 0; m < NMOVES; m++) { 328 uj = move_coord(coord->base[0], m, uu, NULL); 329 coord->mtable[m][ui] = coord->symclass[uj]; 330 coord->ttrep_move[m][ui] = 331 coord->transtorep[uj]; 332 } 333 } 334 if (!write_coord_mtable(coord)) 335 fprintf(stderr, "%s: error writing mtable\n", 336 coord->name); 337 } 338 } 339 340 static bool 341 read_coord_mtable(Coordinate *coord) 342 { 343 FILE *f; 344 char fname[strlen(tabledir)+256]; 345 Move m; 346 uint64_t M; 347 bool r; 348 349 strcpy(fname, tabledir); 350 strcat(fname, "/mt_"); 351 strcat(fname, coord->name); 352 353 if ((f = fopen(fname, "rb")) == NULL) 354 return false; 355 356 M = coord->max; 357 r = true; 358 for (m = 0; m < NMOVES; m++) 359 r = r && fread(coord->mtable[m], sizeof(uint64_t), M, f) == M; 360 361 if (coord->type == SYM_COORD) 362 for (m = 0; m < NMOVES; m++) 363 r = r && fread(coord->ttrep_move[m], 364 sizeof(Trans), M, f) == M; 365 366 fclose(f); 367 return r; 368 } 369 370 static bool 371 read_coord_sd(Coordinate *coord) 372 { 373 FILE *f; 374 char fname[strlen(tabledir)+256]; 375 uint64_t M, N; 376 bool r; 377 378 strcpy(fname, tabledir); 379 strcat(fname, "/sd_"); 380 strcat(fname, coord->name); 381 382 if ((f = fopen(fname, "rb")) == NULL) 383 return false; 384 385 r = true; 386 r = r && fread(&coord->max, sizeof(uint64_t), 1, f) == 1; 387 M = coord->max; 388 N = coord->base[0]->max; 389 r = r && fread(coord->symrep, sizeof(uint64_t), M, f) == M; 390 r = r && fread(coord->selfsim, sizeof(uint64_t), M, f) == M; 391 r = r && fread(coord->symclass, sizeof(uint64_t), N, f) == N; 392 r = r && fread(coord->transtorep, sizeof(Trans), N, f) == N; 393 394 fclose(f); 395 return r; 396 } 397 398 static bool 399 read_coord_ttable(Coordinate *coord) 400 { 401 FILE *f; 402 char fname[strlen(tabledir)+256]; 403 Trans t; 404 uint64_t M; 405 bool r; 406 407 strcpy(fname, tabledir); 408 strcat(fname, "/tt_"); 409 strcat(fname, coord->name); 410 411 if ((f = fopen(fname, "rb")) == NULL) 412 return false; 413 414 M = coord->max; 415 r = true; 416 for (t = 0; t < NTRANS; t++) 417 r = r && fread(coord->ttable[t], sizeof(uint64_t), M, f) == M; 418 419 fclose(f); 420 return r; 421 } 422 423 static bool 424 write_coord_mtable(Coordinate *coord) 425 { 426 FILE *f; 427 char fname[strlen(tabledir)+256]; 428 Move m; 429 uint64_t M; 430 bool r; 431 432 strcpy(fname, tabledir); 433 strcat(fname, "/mt_"); 434 strcat(fname, coord->name); 435 436 if ((f = fopen(fname, "wb")) == NULL) 437 return false; 438 439 M = coord->max; 440 r = true; 441 for (m = 0; m < NMOVES; m++) 442 r = r && fwrite(coord->mtable[m], sizeof(uint64_t), M, f) == M; 443 444 if (coord->type == SYM_COORD) 445 for (m = 0; m < NMOVES; m++) 446 r = r && fwrite(coord->ttrep_move[m], 447 sizeof(Trans), M, f) == M; 448 449 fclose(f); 450 return r; 451 } 452 453 static bool 454 write_coord_sd(Coordinate *coord) 455 { 456 FILE *f; 457 char fname[strlen(tabledir)+256]; 458 uint64_t M, N; 459 bool r; 460 461 strcpy(fname, tabledir); 462 strcat(fname, "/sd_"); 463 strcat(fname, coord->name); 464 465 if ((f = fopen(fname, "wb")) == NULL) 466 return false; 467 468 r = true; 469 M = coord->max; 470 N = coord->base[0]->max; 471 r = r && fwrite(&coord->max, sizeof(uint64_t), 1, f) == 1; 472 r = r && fwrite(coord->symrep, sizeof(uint64_t), M, f) == M; 473 r = r && fwrite(coord->selfsim, sizeof(uint64_t), M, f) == M; 474 r = r && fwrite(coord->symclass, sizeof(uint64_t), N, f) == N; 475 r = r && fwrite(coord->transtorep, sizeof(Trans), N, f) == N; 476 477 fclose(f); 478 return r; 479 } 480 481 static bool 482 write_coord_ttable(Coordinate *coord) 483 { 484 FILE *f; 485 char fname[strlen(tabledir)+256]; 486 Trans t; 487 uint64_t M; 488 bool r; 489 490 strcpy(fname, tabledir); 491 strcat(fname, "/tt_"); 492 strcat(fname, coord->name); 493 494 if ((f = fopen(fname, "wb")) == NULL) 495 return false; 496 497 M = coord->max; 498 r = true; 499 for (t = 0; t < NTRANS; t++) 500 r = r && fwrite(coord->ttable[t], sizeof(uint64_t), M, f) == M; 501 502 fclose(f); 503 return r; 504 } 505 506 /* Public functions **********************************************************/ 507 508 void 509 gen_coord(Coordinate *coord) 510 { 511 int i; 512 513 if (coord == NULL || coord->generated) 514 return; 515 516 for (i = 0; i < 2; i++) 517 gen_coord(coord->base[i]); 518 519 switch (coord->type) { 520 case COMP_COORD: 521 if (coord->i[0] == NULL) 522 goto error_gc; 523 gen_coord_comp(coord); 524 break; 525 case SYM_COORD: 526 if (coord->base[0] == NULL || coord->tgrp == NULL) 527 goto error_gc; 528 gen_coord_sym(coord); 529 break; 530 case SYMCOMP_COORD: 531 if (coord->base[0] == NULL || coord->base[1] == NULL) 532 goto error_gc; 533 coord->max = coord->base[0]->max * coord->base[1]->max; 534 break; 535 default: 536 break; 537 } 538 539 coord->generated = true; 540 return; 541 542 error_gc: 543 fprintf(stderr, "Error generating coordinates.\n" 544 "This is a bug, pleae report.\n"); 545 exit(1); 546 } 547 548 uint64_t 549 index_coord(Coordinate *coord, Cube *cube, Trans *offtrans) 550 { 551 uint64_t c[2], cnosym; 552 Trans ttr; 553 554 switch (coord->type) { 555 case COMP_COORD: 556 if (offtrans != NULL) 557 *offtrans = uf; 558 559 return indexers_getind(coord->i, cube); 560 case SYM_COORD: 561 cnosym = index_coord(coord->base[0], cube, NULL); 562 ttr = coord->transtorep[cnosym]; 563 564 if (offtrans != NULL) 565 *offtrans = ttr; 566 567 return coord->symclass[cnosym]; 568 case SYMCOMP_COORD: 569 c[0] = index_coord(coord->base[0], cube, NULL); 570 cnosym = index_coord(coord->base[0]->base[0], cube, NULL); 571 ttr = coord->base[0]->transtorep[cnosym]; 572 c[1] = index_coord(coord->base[1], cube, NULL); 573 c[1] = trans_coord(coord->base[1], ttr, c[1]); 574 575 if (offtrans != NULL) 576 *offtrans = ttr; 577 578 return c[0] * coord->base[1]->max + c[1]; 579 default: 580 break; 581 } 582 583 return coord->max; /* Only reached in case of error */ 584 } 585 586 uint64_t 587 move_coord(Coordinate *coord, Move m, uint64_t ind, Trans *offtrans) 588 { 589 uint64_t i[2], M; 590 Trans ttr; 591 592 /* Some safety checks should be done here, but for performance * 593 * reasons we'd rather do them before calling this function. * 594 * We should check if coord is generated. */ 595 596 switch (coord->type) { 597 case COMP_COORD: 598 if (offtrans != NULL) 599 *offtrans = uf; 600 601 return coord->mtable[m][ind]; 602 case SYM_COORD: 603 ttr = coord->ttrep_move[m][ind]; 604 605 if (offtrans != NULL) 606 *offtrans = ttr; 607 608 return coord->mtable[m][ind]; 609 case SYMCOMP_COORD: 610 M = coord->base[1]->max; 611 i[0] = ind / M; 612 i[1] = ind % M; 613 ttr = coord->base[0]->ttrep_move[m][i[0]]; 614 i[0] = coord->base[0]->mtable[m][i[0]]; 615 i[1] = coord->base[1]->mtable[m][i[1]]; 616 i[1] = coord->base[1]->ttable[ttr][i[1]]; 617 618 if (offtrans != NULL) 619 *offtrans = ttr; 620 621 return i[0] * M + i[1]; 622 default: 623 break; 624 } 625 626 return coord->max; /* Only reached in case of error */ 627 } 628 629 uint64_t 630 trans_coord(Coordinate *coord, Trans t, uint64_t ind) 631 { 632 uint64_t i[2], M; 633 634 /* Some safety checks should be done here, but for performance * 635 * reasons we'd rather do them before calling this function. * 636 * We should check if coord is generated. */ 637 638 switch (coord->type) { 639 case COMP_COORD: 640 return coord->ttable[t][ind]; 641 case SYM_COORD: 642 return ind; 643 case SYMCOMP_COORD: 644 M = coord->base[1]->max; 645 i[0] = ind / M; /* Always fixed */ 646 i[1] = ind % M; 647 i[1] = coord->base[1]->ttable[t][i[1]]; 648 return i[0] * M + i[1]; 649 default: 650 break; 651 } 652 653 return coord->max; /* Only reached in case of error */ 654 }