aboutsummaryrefslogtreecommitdiff
path: root/src/coord.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/coord.c')
-rw-r--r--src/coord.c976
1 files changed, 524 insertions, 452 deletions
diff --git a/src/coord.c b/src/coord.c
index a9df9fd..06f7474 100644
--- a/src/coord.c
+++ b/src/coord.c
@@ -1,611 +1,683 @@
1#include "coord.h" 1#define COORD_C
2
3static uint64_t index_eofb(Cube cube);
4static uint64_t index_eofbepos(Cube cube);
5static uint64_t index_epud(Cube cube);
6static uint64_t index_coud(Cube cube);
7static uint64_t index_corners(Cube cube);
8static uint64_t index_cp(Cube cube);
9static uint64_t index_cphtr(Cube cube);
10static uint64_t index_cornershtr(Cube cube);
11static uint64_t index_cornershtrfin(Cube cube);
12static uint64_t index_drud(Cube cube);
13static uint64_t index_drud_eofb(Cube cube);
14static uint64_t index_htr_drud(Cube cube);
15static uint64_t index_htrfin(Cube cube);
16static uint64_t index_cpud_separate(Cube cube);
17
18static uint64_t move_eofb(Move m, uint64_t ind);
19static uint64_t move_eofbepos(Move m, uint64_t ind);
20static uint64_t move_epud(Move m, uint64_t ind);
21static uint64_t move_coud(Move m, uint64_t ind);
22static uint64_t move_corners(Move m, uint64_t ind);
23static uint64_t move_cp(Move m, uint64_t ind);
24static uint64_t move_cphtr(Move m, uint64_t ind);
25static uint64_t move_cornershtr(Move m, uint64_t ind);
26static uint64_t move_cornershtrfin(Move m, uint64_t ind);
27static uint64_t move_drud(Move m, uint64_t ind);
28static uint64_t move_drud_eofb(Move m, uint64_t ind);
29static uint64_t move_htr_drud(Move m, uint64_t ind);
30static uint64_t move_htrfin(Move m, uint64_t ind);
31static uint64_t move_cpud_separate(Move m, uint64_t ind);
32 2
33static void init_cphtr_cosets(); 3#include "coord.h"
34static void init_cphtr_left_cosets_bfs(int i, int c);
35static void init_cphtr_right_cosets_color(int i, int c);
36static void init_cpud_separate();
37static void init_cornershtrfin();
38static void init_htr_eposs();
39 4
5static uint64_t indexers_getind(Indexer **is, Cube *c);
6static uint64_t indexers_getmax(Indexer **is);
7static void indexers_makecube(Indexer **is, uint64_t ind, Cube *c);
8static void gen_coord_comp(Coordinate *coord);
9static void gen_coord_sym(Coordinate *coord);
10static bool read_coord_mtable(Coordinate *coord);
11static bool read_coord_sd(Coordinate *coord);
12static bool read_coord_ttable(Coordinate *coord);
13static bool write_coord_mtable(Coordinate *coord);
14static bool write_coord_sd(Coordinate *coord);
15static bool write_coord_ttable(Coordinate *coord);
40 16
41/* All sorts of useful costants and tables **********************************/ 17/* Indexers ******************************************************************/
42 18
43static int cphtr_left_cosets[FACTORIAL8]; 19uint64_t
44static int cphtr_right_cosets[FACTORIAL8]; 20index_eofb(Cube *cube)
45static int cphtr_right_rep[BINOM8ON4*6]; 21{
46int cpud_separate_ind[FACTORIAL8]; 22 return (uint64_t)digit_array_to_int(cube->eo, 11, 2);
47int cpud_separate_ant[BINOM8ON4]; 23}
48static int cornershtrfin_ind[FACTORIAL8];
49int cornershtrfin_ant[24*24/6];
50static int htr_eposs_ind[BINOM12ON4];
51static int htr_eposs_ant[BINOM8ON4];
52 24
53/* Coordinates and their implementation **************************************/ 25uint64_t
26index_coud(Cube *cube)
27{
28 return (uint64_t)digit_array_to_int(cube->co, 7, 3);
29}
54 30
55Coordinate 31uint64_t
56coord_eofb = { 32index_cp(Cube *cube)
57 .index = index_eofb, 33{
58 .max = POW2TO11, 34 return (uint64_t)perm_to_index(cube->cp, 8);
59 .move = move_eofb, 35}
60};
61 36
62Coordinate 37uint64_t
63coord_eofbepos = { 38index_cpudsep(Cube *cube)
64 .index = index_eofbepos, 39{
65 .max = POW2TO11 * BINOM12ON4, 40 int i, c[8];
66 .move = move_eofbepos,
67};
68 41
69Coordinate 42 for (i = 0; i < 8; i++)
70coord_coud = { 43 c[i] = cube->cp[i] < 4 ? 0 : 1;
71 .index = index_coud,
72 .max = POW3TO7,
73 .move = move_coud,
74};
75 44
76Coordinate 45 return (uint64_t)subset_to_index(c, 8, 4);
77coord_corners = { 46}
78 .index = index_corners,
79 .max = POW3TO7 * FACTORIAL8,
80 .move = move_corners,
81};
82 47
83Coordinate 48uint64_t
84coord_cp = { 49index_epe(Cube *cube)
85 .index = index_cp, 50{
86 .max = FACTORIAL8, 51 int i, e[4];
87 .move = move_cp,
88};
89 52
90Coordinate 53 for (i = 0; i < 4; i++)
91coord_cphtr = { 54 e[i] = cube->ep[i+8] - 8;
92 .index = index_cphtr,
93 .max = BINOM8ON4 * 6,
94 .move = move_cphtr,
95};
96 55
97Coordinate 56 return (uint64_t)perm_to_index(e, 4);
98coord_cornershtr = { 57}
99 .index = index_cornershtr,
100 .max = POW3TO7 * BINOM8ON4 * 6,
101 .move = move_cornershtr,
102};
103 58
104Coordinate 59uint64_t
105coord_cornershtrfin = { 60index_epud(Cube *cube)
106 .index = index_cornershtrfin, 61{
107 .max = 24*24/6, 62 return (uint64_t)perm_to_index(cube->ep, 8);
108 .move = move_cornershtrfin, 63}
109};
110 64
111Coordinate 65uint64_t
112coord_epud = { 66index_epos(Cube *cube)
113 .index = index_epud, 67{
114 .max = FACTORIAL8, 68 int i, a[12];
115 .move = move_epud,
116};
117 69
118Coordinate 70 for (i = 0; i < 12; i++)
119coord_drud = { 71 a[i] = (cube->ep[i] < 8) ? 0 : 1;
120 .index = index_drud,
121 .max = POW2TO11 * POW3TO7 * BINOM12ON4,
122 .move = move_drud,
123};
124 72
125Coordinate 73 return (uint64_t)subset_to_index(a, 12, 4);
126coord_htr_drud = { 74}
127 .index = index_htr_drud,
128 .max = BINOM8ON4 * 6 * BINOM8ON4,
129 .move = move_htr_drud,
130};
131 75
132Coordinate 76uint64_t
133coord_htrfin = { 77index_eposepe(Cube *cube)
134 .index = index_htrfin, 78{
135 .max = 24 * 24 * 24 *24 * 24 / 6, /* should be /12 but it's ok */ 79 int i, j, e[4];
136 .move = move_htrfin, 80 uint64_t epos, epe;
137};
138 81
139Coordinate 82 epos = (uint64_t)index_epos(cube);
140coord_drud_eofb = { 83 for (i = 0, j = 0; i < 12; i++)
141 .index = index_drud_eofb, 84 if (cube->ep[i] >= 8)
142 .max = POW3TO7 * BINOM12ON4, 85 e[j++] = cube->ep[i] - 8;
143 .move = move_drud_eofb, 86 epe = (uint64_t)perm_to_index(e, 4);
144};
145 87
146Coordinate 88 return epos * FACTORIAL4 + epe;
147coord_cpud_separate = { 89}
148 .index = index_cpud_separate,
149 .max = BINOM8ON4,
150 .move = move_cpud_separate,
151};
152 90
153/* Indexers ******************************************************************/ 91/* Inverse indexers **********************************************************/
154 92
155static uint64_t 93void
156index_eofb(Cube cube) 94invindex_eofb(uint64_t ind, Cube *cube)
157{ 95{
158 return cube.eofb; 96 int_to_sum_zero_array(ind, 2, 12, cube->eo);
159} 97}
160 98
161static uint64_t 99void
162index_eofbepos(Cube cube) 100invindex_coud(uint64_t ind, Cube *cube)
163{ 101{
164 return (cube.epose / FACTORIAL4) * POW2TO11 + cube.eofb; 102 int_to_sum_zero_array(ind, 3, 8, cube->co);
165} 103}
166 104
167static uint64_t 105void
168index_epud(Cube cube) 106invindex_cp(uint64_t ind, Cube *cube)
169{ 107{
170 uint64_t ret; 108 index_to_perm(ind, 8, cube->cp);
171 CubeArray *arr = new_cubearray(cube, pf_ep);
172
173 ret = perm_to_index(arr->ep, 8);
174 free_cubearray(arr, pf_ep);
175
176 return ret;
177} 109}
178 110
179static uint64_t 111void
180index_coud(Cube cube) 112invindex_cpudsep(uint64_t ind, Cube *cube)
181{ 113{
182 return cube.coud; 114 int i, j, k, c[8];
183}
184 115
185static uint64_t 116 index_to_subset(ind, 8, 4, c);
186index_corners(Cube cube) 117 for (i = 0, j = 0, k = 4; i < 8; i++)
187{ 118 cube->cp[i] = c[i] == 0 ? j++ : k++;
188 return cube.coud * FACTORIAL8 + cube.cp;
189} 119}
190 120
191static uint64_t
192index_cp(Cube cube)
193{
194 return cube.cp;
195}
196 121
197static uint64_t 122void
198index_cphtr(Cube cube) 123invindex_epe(uint64_t ind, Cube *cube)
199{ 124{
200 return cphtr_right_cosets[cube.cp]; 125 int i;
126
127 index_to_perm(ind, 4, &cube->ep[8]);
128 for (i = 0; i < 4; i++)
129 cube->ep[i+8] += 8;
201} 130}
202 131
203static uint64_t 132void
204index_cornershtr(Cube cube) 133invindex_epud(uint64_t ind, Cube *cube)
205{ 134{
206 return cube.coud * BINOM8ON4 * 6 + index_cphtr(cube); 135 index_to_perm(ind, 8, cube->ep);
207} 136}
208 137
209static uint64_t 138void
210index_cornershtrfin(Cube cube) 139invindex_epos(uint64_t ind, Cube *cube)
211{ 140{
212 return cornershtrfin_ind[cube.cp]; 141 int i, j, k;
142
143 index_to_subset(ind, 12, 4, cube->ep);
144 for (i = 0, j = 0, k = 8; i < 12; i++)
145 if (cube->ep[i] == 0)
146 cube->ep[i] = j++;
147 else
148 cube->ep[i] = k++;
213} 149}
214 150
215static uint64_t 151void
216index_drud(Cube cube) 152invindex_eposepe(uint64_t ind, Cube *cube)
217{ 153{
218 uint64_t a, b, c; 154 int i, j, k, e[4];
155 uint64_t epos, epe;
219 156
220 a = cube.eofb; 157 epos = ind / FACTORIAL4;
221 b = cube.coud; 158 epe = ind % FACTORIAL4;
222 c = cube.epose / FACTORIAL4;
223 159
224 b *= POW2TO11; 160 index_to_subset(epos, 12, 4, cube->ep);
225 c *= POW2TO11 * POW3TO7; 161 index_to_perm(epe, 4, e);
226 162
227 return a + b + c; 163 for (i = 0, j = 0, k = 0; i < 12; i++)
164 if (cube->ep[i] == 0)
165 cube->ep[i] = j++;
166 else
167 cube->ep[i] = e[k++] + 8;
228} 168}
229 169
230static uint64_t 170/* Other local functions *****************************************************/
231index_drud_eofb(Cube cube)
232{
233 return index_drud(cube) / POW2TO11;
234}
235 171
236static uint64_t 172static uint64_t
237index_htr_drud(Cube cube) 173indexers_getmax(Indexer **is)
238{ 174{
239 uint64_t a, b; 175 int i;
176 uint64_t max = 1;
240 177
241 a = index_cphtr(cube); 178 for (i = 0; is[i] != NULL; i++)
242 b = htr_eposs_ind[cube.eposs/24]; 179 max *= is[i]->n;
243 180
244 return a * BINOM8ON4 + b; 181 return max;
245} 182}
246 183
247static uint64_t 184static uint64_t
248index_htrfin(Cube cube) 185indexers_getind(Indexer **is, Cube *c)
249{ 186{
250 uint64_t epe, eps, epm, cp, ep; 187 int i;
188 uint64_t max = 0;
251 189
252 epe = cube.epose % 24; 190 for (i = 0; is[i] != NULL; i++) {
253 eps = cube.eposs % 24; 191 max *= is[i]->n;
254 epm = cube.eposm % 24; 192 max += is[i]->index(c);
255 ep = (epe * 24 + eps) *24 + epm; 193 }
256 cp = index_cornershtrfin(cube);
257 194
258 return cp * 24 * 24 * 24 + ep; 195 return max;
259} 196}
260 197
261static uint64_t 198static void
262index_cpud_separate(Cube cube) 199indexers_makecube(Indexer **is, uint64_t ind, Cube *c)
263{ 200{
264 return cpud_separate_ind[cube.cp]; 201 /* Warning: anti-indexers are applied in the same order as indexers. */
265} 202 /* We assume order does not matter, but it would make more sense to */
203 /* Apply them in reverse. */
266 204
267/* Coordinate movers *********************************************************/ 205 int i;
206 uint64_t m;
268 207
269static uint64_t 208 make_solved(c);
270move_eofb(Move m, uint64_t ind) 209 m = indexers_getmax(is);
271{ 210 for (i = 0; is[i] != NULL; i++) {
272 return eofb_mtable[m][ind]; 211 m /= is[i]->n;
212 is[i]->to_cube(ind / m, c);
213 ind %= m;
214 }
273} 215}
274 216
275static uint64_t 217static void
276move_eofbepos(Move m, uint64_t ind) 218gen_coord_comp(Coordinate *coord)
277{ 219{
278 uint64_t a, b; 220 uint64_t ui;
221 Cube c, mvd;
222 Move m;
223 Trans t;
279 224
280 a = epose_mtable[m][(ind / POW2TO11)*24]; 225 coord->max = indexers_getmax(coord->i);
281 b = eofb_mtable[m][ind % POW2TO11];
282 226
283 return (a/24) * POW2TO11 + b; 227 for (m = 0; m < NMOVES; m++)
284} 228 coord->mtable[m] = malloc(coord->max * sizeof(uint64_t));
285 229
286static uint64_t 230 for (t = 0; t < NTRANS; t++)
287move_epud(Move m, uint64_t ind) 231 coord->ttable[t] = malloc(coord->max * sizeof(uint64_t));
288{
289 /* TODO: save to file? */
290 static bool initialized = false;
291 static int a[12] = { [8] = 8, [9] = 9, [10] = 10, [11] = 11 };
292 static int shortlist[NMOVES] = {
293 [U] = 0, [U2] = 1, [U3] = 2, [D] = 3, [D2] = 4, [D3] = 5,
294 [R2] = 6, [L2] = 7, [F2] = 8, [B2] = 9
295 };
296 static uint64_t aux[10][FACTORIAL8];
297 uint64_t ui;
298 int j;
299 Move mj;
300 Cube c;
301 CubeArray *arr, *auxarr;
302 232
303 if (!moveset_drud.allowed(m)) { 233 if (!read_coord_mtable(coord)) {
304 fprintf(stderr, "Move not allowed for epud\n" 234 fprintf(stderr, "%s: generating mtable\n", coord->name);
305 "This is a bug, please report\n");
306 return coord_epud.max;
307 }
308 235
309 if (!initialized) { 236 for (ui = 0; ui < coord->max; ui++) {
310 auxarr = malloc(sizeof(CubeArray)); 237 indexers_makecube(coord->i, ui, &c);
311 auxarr->ep = a; 238 for (m = 0; m < NMOVES; m++) {
312 for (ui = 0; ui < coord_epud.max; ui++) { 239 copy_cube(&c, &mvd);
313 index_to_perm(ui, 8, a); 240 apply_move(m, &mvd);
314 c = arrays_to_cube(auxarr, pf_ep); 241 coord->mtable[m][ui] =
315 for (j = 0; moveset_drud.sorted_moves[j] != NULLMOVE; 242 indexers_getind(coord->i, &mvd);
316 j++) {
317 mj = moveset_drud.sorted_moves[j];
318 arr = new_cubearray(apply_move(mj, c), pf_ep);
319 aux[shortlist[mj]][ui] =
320 perm_to_index(arr->ep, 8);
321 free_cubearray(arr, pf_ep);
322 } 243 }
323 } 244 }
324 free(auxarr); 245 if (!write_coord_mtable(coord))
325 246 fprintf(stderr, "%s: error writing mtable\n",
326 initialized = true; 247 coord->name);
248
249 fprintf(stderr, "%s: mtable generated\n", coord->name);
327 } 250 }
328 251
329 return aux[shortlist[m]][ind]; 252 if (!read_coord_ttable(coord)) {
330} 253 fprintf(stderr, "%s: generating ttable\n", coord->name);
331 254
332static uint64_t 255 for (ui = 0; ui < coord->max; ui++) {
333move_coud(Move m, uint64_t ind) 256 indexers_makecube(coord->i, ui, &c);
334{ 257 for (t = 0; t < NTRANS; t++) {
335 return coud_mtable[m][ind]; 258 copy_cube(&c, &mvd);
259 apply_trans(t, &mvd);
260 coord->ttable[t][ui] =
261 indexers_getind(coord->i, &mvd);
262 }
263 }
264 if (!write_coord_ttable(coord))
265 fprintf(stderr, "%s: error writing ttable\n",
266 coord->name);
267 }
336} 268}
337 269
338static uint64_t 270static void
339move_corners(Move m, uint64_t ind) 271gen_coord_sym(Coordinate *coord)
340{ 272{
341 uint64_t a, b; 273 uint64_t i, in, ui, uj, uu, M, nr;
274 int j;
275 Move m;
276 Trans t;
342 277
343 a = coud_mtable[m][ind / FACTORIAL8]; 278 M = coord->base[0]->max;
344 b = cp_mtable[m][ind % FACTORIAL8]; 279 coord->selfsim = malloc(M * sizeof(uint64_t));
280 coord->symclass = malloc(M * sizeof(uint64_t));
281 coord->symrep = malloc(M * sizeof(uint64_t));
282 coord->transtorep = malloc(M * sizeof(Trans));
345 283
346 return a * FACTORIAL8 + b; 284 if (!read_coord_sd(coord)) {
347} 285 fprintf(stderr, "%s: generating syms\n", coord->name);
348 286
349static uint64_t 287 for (i = 0; i < M; i++)
350move_cp(Move m, uint64_t ind) 288 coord->symclass[i] = M+1;
351{
352 return cp_mtable[m][ind];
353}
354 289
355static uint64_t 290 for (i = 0, nr = 0; i < M; i++) {
356move_cphtr(Move m, uint64_t ind) 291 if (coord->symclass[i] != M+1)
357{ 292 continue;
358 static bool initialized = false; 293
359 static uint64_t aux[NMOVES][BINOM8ON4*6]; 294 coord->symrep[nr] = i;
360 uint64_t ui; 295 coord->transtorep[i] = uf;
361 Move j; 296 coord->selfsim[nr] = (uint64_t)0;
297 for (j = 0; j < coord->tgrp->n; j++) {
298 t = coord->tgrp->t[j];
299 in = trans_coord(coord->base[0], t, i);
300 coord->symclass[in] = nr;
301 if (in == i)
302 coord->selfsim[nr] |= ((uint64_t)1<<t);
303 else
304 coord->transtorep[in] =
305 inverse_trans(t);
306 }
307 nr++;
308 }
309
310 coord->max = nr;
311
312 fprintf(stderr, "%s: found %" PRIu64 " classes\n",
313 coord->name, nr);
314 if (!write_coord_sd(coord))
315 fprintf(stderr, "%s: error writing symdata\n",
316 coord->name);
317 }
362 318
363 if (!initialized) { 319 coord->symrep = realloc(coord->symrep, coord->max*sizeof(uint64_t));
364 for (ui = 0; ui < BINOM8ON4*6; ui++) 320 coord->selfsim = realloc(coord->selfsim, coord->max*sizeof(uint64_t));
365 for (j = U; j < NMOVES; j++)
366 aux[j][ui] = cphtr_right_cosets[
367 cp_mtable[j][cphtr_right_rep[ui]]];
368 321
369 initialized = true; 322 for (m = 0; m < NMOVES; m++) {
323 coord->mtable[m] = malloc(coord->max*sizeof(uint64_t));
324 coord->ttrep_move[m] = malloc(coord->max*sizeof(Trans));
370 } 325 }
371 326
372 return aux[m][ind]; 327 if (!read_coord_mtable(coord)) {
328 for (ui = 0; ui < coord->max; ui++) {
329 uu = coord->symrep[ui];
330 for (m = 0; m < NMOVES; m++) {
331 uj = move_coord(coord->base[0], m, uu, NULL);
332 coord->mtable[m][ui] = coord->symclass[uj];
333 coord->ttrep_move[m][ui] =
334 coord->transtorep[uj];
335 }
336 }
337 if (!write_coord_mtable(coord))
338 fprintf(stderr, "%s: error writing mtable\n",
339 coord->name);
340 }
373} 341}
374 342
375static uint64_t 343static bool
376move_cornershtr(Move m, uint64_t ind) 344read_coord_mtable(Coordinate *coord)
377{ 345{
378 uint64_t a, b; 346 FILE *f;
347 char fname[strlen(tabledir)+256];
348 Move m;
349 uint64_t M;
350 bool r;
379 351
380 a = coud_mtable[m][ind/(BINOM8ON4 * 6)]; 352 strcpy(fname, tabledir);
381 b = move_cphtr(m, ind % (BINOM8ON4 * 6)); 353 strcat(fname, "/mt_");
354 strcat(fname, coord->name);
382 355
383 return a * BINOM8ON4 * 6 + b; 356 if ((f = fopen(fname, "rb")) == NULL)
384} 357 return false;
385 358
386static uint64_t 359 M = coord->max;
387move_cornershtrfin(Move m, uint64_t ind) 360 r = true;
388{ 361 for (m = 0; m < NMOVES; m++)
389 int a; 362 r = r && fread(coord->mtable[m], sizeof(uint64_t), M, f) == M;
390 363
391 a = cp_mtable[m][cornershtrfin_ant[ind]]; 364 if (coord->type == SYM_COORD)
365 for (m = 0; m < NMOVES; m++)
366 r = r && fread(coord->ttrep_move[m],
367 sizeof(Trans), M, f) == M;
392 368
393 return cornershtrfin_ind[a]; 369 fclose(f);
370 return r;
394} 371}
395 372
396static uint64_t 373static bool
397move_drud(Move m, uint64_t ind) 374read_coord_sd(Coordinate *coord)
398{ 375{
399 uint64_t a, b, c; 376 FILE *f;
377 char fname[strlen(tabledir)+256];
378 uint64_t M, N;
379 bool r;
380
381 strcpy(fname, tabledir);
382 strcat(fname, "/sd_");
383 strcat(fname, coord->name);
400 384
401 a = eofb_mtable[m][ind % POW2TO11]; 385 if ((f = fopen(fname, "rb")) == NULL)
402 b = coud_mtable[m][(ind / POW2TO11) % POW3TO7]; 386 return false;
403 c = epose_mtable[m][ind / (POW2TO11 * POW3TO7)];
404 387
405 return a + (b + c * POW3TO7) * POW2TO11; 388 r = true;
389 r = r && fread(&coord->max, sizeof(uint64_t), 1, f) == 1;
390 M = coord->max;
391 N = coord->base[0]->max;
392 r = r && fread(coord->symrep, sizeof(uint64_t), M, f) == M;
393 r = r && fread(coord->selfsim, sizeof(uint64_t), M, f) == M;
394 r = r && fread(coord->symclass, sizeof(uint64_t), N, f) == N;
395 r = r && fread(coord->transtorep, sizeof(Trans), N, f) == N;
396
397 fclose(f);
398 return r;
406} 399}
407 400
408static uint64_t 401static bool
409move_drud_eofb(Move m, uint64_t ind) 402read_coord_ttable(Coordinate *coord)
410{ 403{
411 uint64_t a, b; 404 FILE *f;
405 char fname[strlen(tabledir)+256];
406 Trans t;
407 uint64_t M;
408 bool r;
409
410 strcpy(fname, tabledir);
411 strcat(fname, "/tt_");
412 strcat(fname, coord->name);
412 413
413 a = coud_mtable[m][ind % POW3TO7]; 414 if ((f = fopen(fname, "rb")) == NULL)
414 b = epose_mtable[m][(ind / POW3TO7) * 24] / 24; 415 return false;
415 416
416 return a + b * POW3TO7; 417 M = coord->max;
418 r = true;
419 for (t = 0; t < NTRANS; t++)
420 r = r && fread(coord->ttable[t], sizeof(uint64_t), M, f) == M;
421
422 fclose(f);
423 return r;
417} 424}
418 425
419static uint64_t 426static bool
420move_htr_drud(Move m, uint64_t ind) 427write_coord_mtable(Coordinate *coord)
421{ 428{
422 uint64_t a, b; 429 FILE *f;
430 char fname[strlen(tabledir)+256];
431 Move m;
432 uint64_t M;
433 bool r;
434
435 strcpy(fname, tabledir);
436 strcat(fname, "/mt_");
437 strcat(fname, coord->name);
438
439 if ((f = fopen(fname, "wb")) == NULL)
440 return false;
423 441
424 a = move_cphtr(m, ind/BINOM8ON4); 442 M = coord->max;
425 b = eposs_mtable[m][htr_eposs_ant[ind%BINOM8ON4]]; 443 r = true;
444 for (m = 0; m < NMOVES; m++)
445 r = r && fwrite(coord->mtable[m], sizeof(uint64_t), M, f) == M;
426 446
427 return a*BINOM8ON4 + htr_eposs_ind[b/24]; 447 if (coord->type == SYM_COORD)
448 for (m = 0; m < NMOVES; m++)
449 r = r && fwrite(coord->ttrep_move[m],
450 sizeof(Trans), M, f) == M;
451
452 fclose(f);
453 return r;
428} 454}
429 455
430static uint64_t 456static bool
431move_htrfin(Move m, uint64_t ind) 457write_coord_sd(Coordinate *coord)
432{ 458{
433 uint64_t a, b, bm, bs, be; 459 FILE *f;
460 char fname[strlen(tabledir)+256];
461 uint64_t M, N;
462 bool r;
434 463
435 a = move_cornershtrfin(m, ind / (24*24*24)); 464 strcpy(fname, tabledir);
436 bm = eposm_mtable[m][ind%24] % 24; 465 strcat(fname, "/sd_");
437 bs = eposs_mtable[m][(ind/24)%24] % 24; 466 strcat(fname, coord->name);
438 be = epose_mtable[m][(ind/(24*24))%24] % 24;
439 b = (be * 24 + bs) * 24 + bm;
440 467
441 return a * (24*24*24) + b; 468 if ((f = fopen(fname, "wb")) == NULL)
469 return false;
470
471 r = true;
472 M = coord->max;
473 N = coord->base[0]->max;
474 r = r && fwrite(&coord->max, sizeof(uint64_t), 1, f) == 1;
475 r = r && fwrite(coord->symrep, sizeof(uint64_t), M, f) == M;
476 r = r && fwrite(coord->selfsim, sizeof(uint64_t), M, f) == M;
477 r = r && fwrite(coord->symclass, sizeof(uint64_t), N, f) == N;
478 r = r && fwrite(coord->transtorep, sizeof(Trans), N, f) == N;
479
480 fclose(f);
481 return r;
442} 482}
443 483
444static uint64_t 484static bool
445move_cpud_separate(Move m, uint64_t ind) 485write_coord_ttable(Coordinate *coord)
446{ 486{
447 return cpud_separate_ind[cp_mtable[m][cpud_separate_ant[ind]]]; 487 FILE *f;
488 char fname[strlen(tabledir)+256];
489 Trans t;
490 uint64_t M;
491 bool r;
492
493 strcpy(fname, tabledir);
494 strcat(fname, "/tt_");
495 strcat(fname, coord->name);
496
497 if ((f = fopen(fname, "wb")) == NULL)
498 return false;
499
500 M = coord->max;
501 r = true;
502 for (t = 0; t < NTRANS; t++)
503 r = r && fwrite(coord->ttable[t], sizeof(uint64_t), M, f) == M;
504
505 fclose(f);
506 return r;
448} 507}
449 508
450/* Init functions implementation *********************************************/ 509/* Public functions **********************************************************/
451 510
452/* 511void
453 * There is certainly a better way to do this, but for now I just use 512gen_coord(Coordinate *coord)
454 * a "graph coloring" algorithm to compute the left cosets, and I compose
455 * with every possible cp to get the right cosets (it is possible that I am
456 * mixing up left and right).
457 *
458 * For doing it better "Mathematically", we need 3 things:
459 * - Checking that cp separates the orbits (UFR,UBL,DFL,DBR) and the other
460 * This is easy and it is done in the commented function cphtr_cp().
461 * - Check that there is no ep/cp parity
462 * - Check that we are not in the "3c" case; this is the part I don't
463 * know how to do.
464 */
465static void
466init_cphtr_cosets()
467{ 513{
468 unsigned int i; 514 int i;
469 int c = 0, d = 0; 515
516 if (coord == NULL || coord->generated)
517 return;
518
519 for (i = 0; i < 2; i++)
520 gen_coord(coord->base[i]);
470 521
471 for (i = 0; i < FACTORIAL8; i++) { 522 switch (coord->type) {
472 cphtr_left_cosets[i] = -1; 523 case COMP_COORD:
473 cphtr_right_cosets[i] = -1; 524 if (coord->i[0] == NULL)
525 goto error_gc;
526 gen_coord_comp(coord);
527 break;
528 case SYM_COORD:
529 if (coord->base[0] == NULL || coord->tgrp == NULL)
530 goto error_gc;
531 gen_coord_sym(coord);
532 break;
533 case SYMCOMP_COORD:
534 if (coord->base[0] == NULL || coord->base[1] == NULL)
535 goto error_gc;
536 coord->max = coord->base[0]->max * coord->base[1]->max;
537 break;
538 default:
539 break;
474 } 540 }
475 541
476 /* First we compute left cosets with a bfs */ 542 coord->generated = true;
477 for (i = 0; i < FACTORIAL8; i++) 543 return;
478 if (cphtr_left_cosets[i] == -1)
479 init_cphtr_left_cosets_bfs(i, c++);
480 544
481 /* Then we compute right cosets using compose() */ 545error_gc:
482 for (i = 0; i < FACTORIAL8; i++) 546 fprintf(stderr, "Error generating coordinates.\n"
483 if (cphtr_right_cosets[i] == -1) 547 "This is a bug, pleae report.\n");
484 init_cphtr_right_cosets_color(i, d++); 548 exit(1);
485} 549}
486 550
487static void 551uint64_t
488init_cphtr_left_cosets_bfs(int i, int c) 552index_coord(Coordinate *coord, Cube *cube, Trans *offtrans)
489{ 553{
490 int j, jj, next[FACTORIAL8], next2[FACTORIAL8], n, n2; 554 uint64_t c[2], cnosym;
555 Trans ttr;
491 556
492 Move k; 557 switch (coord->type) {
558 case COMP_COORD:
559 if (offtrans != NULL)
560 *offtrans = uf;
493 561
494 n = 1; 562 return indexers_getind(coord->i, cube);
495 next[0] = i; 563 case SYM_COORD:
496 cphtr_left_cosets[i] = c; 564 cnosym = index_coord(coord->base[0], cube, NULL);
565 ttr = coord->transtorep[cnosym];
497 566
498 while (n != 0) { 567 if (offtrans != NULL)
499 for (j = 0, n2 = 0; j < n; j++) { 568 *offtrans = ttr;
500 for (k = U2; k < B3; k++) {
501 if (!moveset_htr.allowed(k))
502 continue;
503 jj = apply_move(k, (Cube){ .cp = next[j] }).cp;
504 569
505 if (cphtr_left_cosets[jj] == -1) { 570 return coord->symclass[cnosym];
506 cphtr_left_cosets[jj] = c; 571 case SYMCOMP_COORD:
507 next2[n2++] = jj; 572 c[0] = index_coord(coord->base[0], cube, NULL);
508 } 573 cnosym = index_coord(coord->base[0]->base[0], cube, NULL);
509 } 574 ttr = coord->base[0]->transtorep[cnosym];
510 } 575 c[1] = index_coord(coord->base[1], cube, NULL);
576 c[1] = trans_coord(coord->base[1], ttr, c[1]);
511 577
512 for (j = 0; j < n2; j++) 578 if (offtrans != NULL)
513 next[j] = next2[j]; 579 *offtrans = ttr;
514 n = n2; 580
581 return c[0] * coord->base[1]->max + c[1];
582 default:
583 break;
515 } 584 }
585
586 return coord->max; /* Only reached in case of error */
516} 587}
517 588
518static void 589uint64_t
519init_cphtr_right_cosets_color(int i, int d) 590move_coord(Coordinate *coord, Move m, uint64_t ind, Trans *offtrans)
520{ 591{
521 int cp; 592 uint64_t i[2], M;
522 unsigned int j; 593 Trans ttr;
523 594
524 cphtr_right_rep[d] = i; 595 /* Some safety checks should be done here, but for performance *
525 for (j = 0; j < FACTORIAL8; j++) { 596 * reasons we'd rather do them before calling this function. *
526 if (cphtr_left_cosets[j] == 0) { 597 * We should check if coord is generated. */
527 cp = compose((Cube){.cp = i}, (Cube){.cp = j}).cp;
528 cphtr_right_cosets[cp] = d;
529 }
530 }
531}
532 598
533static void 599 switch (coord->type) {
534init_cpud_separate() 600 case COMP_COORD:
535{ 601 if (offtrans != NULL)
536 unsigned int ui; 602 *offtrans = uf;
537 int i, co[8];
538 603
539 for (ui = 0; ui < FACTORIAL8; ui++) { 604 return coord->mtable[m][ind];
540 for (i = 0; i < 8; i++) 605 case SYM_COORD:
541 co[i] = what_corner_at((Cube){.cp=ui},i)>UBR ? 1 : 0; 606 ttr = coord->ttrep_move[m][ind];
542 cpud_separate_ind[ui] = subset_to_index(co, 8, 4);
543 cpud_separate_ant[cpud_separate_ind[ui]] = ui;
544 }
545}
546 607
547static void 608 if (offtrans != NULL)
548init_cornershtrfin() 609 *offtrans = ttr;
549{
550 unsigned int i, j;
551 int n, c;
552 Move m;
553 610
554 for (i = 0; i < FACTORIAL8; i++) 611 return coord->mtable[m][ind];
555 cornershtrfin_ind[i] = -1; 612 case SYMCOMP_COORD:
556 cornershtrfin_ind[0] = 0; 613 M = coord->base[1]->max;
614 i[0] = ind / M;
615 i[1] = ind % M;
616 ttr = coord->base[0]->ttrep_move[m][i[0]];
617 i[0] = coord->base[0]->mtable[m][i[0]];
618 i[1] = coord->base[1]->mtable[m][i[1]];
619 i[1] = coord->base[1]->ttable[ttr][i[1]];
557 620
558 /* 10-pass, I think 5 is enough, but just in case */ 621 if (offtrans != NULL)
559 n = 1; 622 *offtrans = ttr;
560 for (i = 0; i < 10; i++) { 623
561 for (j = 0; j < FACTORIAL8; j++) { 624 return i[0] * M + i[1];
562 if (cornershtrfin_ind[j] == -1) 625 default:
563 continue; 626 break;
564 for (m = U; m < NMOVES; m++) {
565 if (moveset_htr.allowed(m)) {
566 c = cp_mtable[m][j];
567 if (cornershtrfin_ind[c] == -1) {
568 cornershtrfin_ind[c] = n;
569 cornershtrfin_ant[n] = c;
570 n++;
571 }
572 }
573 }
574 }
575 } 627 }
628
629 return coord->max; /* Only reached in case of error */
576} 630}
577 631
578void 632bool
579init_htr_eposs() 633test_coord(Coordinate *coord)
580{ 634{
581 int ep[12], ep2[12]; 635 uint64_t ui, uj;
582 int eps_solved[4] = {UL, UR, DL, DR}; 636 Cube c;
583 unsigned int i, j;
584 637
585 for (i = 0; i < BINOM12ON4; i++) { 638 if (coord->type != COMP_COORD) {
586 for (j = 0; j < 12; j++) 639 fprintf(stderr, "Can only test COMP_COORD\n");
587 ep[j] = ep2[j] = 0; 640 return false;
588 epos_to_partial_ep(i*24, ep, eps_solved);
589 for (j = 0; j < 8; j++)
590 ep2[j/2 + 4*(j%2)] = ep[j] ? 1 : 0;
591 htr_eposs_ind[i] = subset_to_index(ep2, 8, 4);
592 htr_eposs_ant[htr_eposs_ind[i]] = i*24;
593 } 641 }
642
643 gen_coord(coord);
644 for (ui = 0; ui < coord->max; ui++) {
645 indexers_makecube(coord->i, ui, &c);
646 uj = indexers_getind(coord->i, &c);
647 if (ui != uj) {
648 fprintf(stderr, "%s: error: %" PRIu64 " different"
649 " from %" PRIu64 "\n", coord->name, uj, ui);
650 return false;
651 }
652 }
653
654 fprintf(stderr, "%s: test passed\n", coord->name);
655 return true;
594} 656}
595 657
596void 658uint64_t
597init_coord() 659trans_coord(Coordinate *coord, Trans t, uint64_t ind)
598{ 660{
599 static bool initialized = false; 661 uint64_t i[2], M;
600 if (initialized)
601 return;
602 initialized = true;
603 662
604 init_trans(); 663 /* Some safety checks should be done here, but for performance *
664 * reasons we'd rather do them before calling this function. *
665 * We should check if coord is generated. */
605 666
606 init_cphtr_cosets(); 667 switch (coord->type) {
607 init_cornershtrfin(); 668 case COMP_COORD:
608 init_htr_eposs(); 669 return coord->ttable[t][ind];
609 init_cpud_separate(); 670 case SYM_COORD:
610} 671 return ind;
672 case SYMCOMP_COORD:
673 M = coord->base[1]->max;
674 i[0] = ind / M; /* Always fixed */
675 i[1] = ind % M;
676 i[1] = coord->base[1]->ttable[t][i[1]];
677 return i[0] * M + i[1];
678 default:
679 break;
680 }
611 681
682 return coord->max; /* Only reached in case of error */
683}

Generated with cgit - Back to sebastiano.tronto.net