coord.c (9182B)
1 #include <inttypes.h> 2 #include <stdbool.h> 3 #include <stdlib.h> 4 #include <string.h> 5 6 #include "cube.h" 7 #include "coord.h" 8 9 typedef void (Copier)(void *, void *, size_t); 10 11 static size_t copy_coord_sd(Coordinate *, char *, Copier *); 12 static size_t copy_coord_mtable(Coordinate *, char *, Copier *); 13 static size_t copy_coord_ttrep_move(Coordinate *, char *, Copier *); 14 static size_t copy_coord_ttable(Coordinate *, char *, Copier *); 15 static size_t copy_ptable(Coordinate *, char *, Copier *); 16 17 static void readin (void *t, void *b, size_t n) { memcpy(t, b, n); } 18 static void writeout(void *t, void *b, size_t n) { memcpy(b, t, n); } 19 20 coord_value_t 21 indexers_getmax(Indexer **is) 22 { 23 int i; 24 coord_value_t max = 1; 25 26 for (i = 0; is[i] != NULL; i++) 27 max *= is[i]->n; 28 29 return max; 30 } 31 32 coord_value_t 33 indexers_getind(Indexer **is, Cube *c) 34 { 35 int i; 36 coord_value_t max = 0; 37 38 for (i = 0; is[i] != NULL; i++) { 39 max *= is[i]->n; 40 max += is[i]->index(c); 41 } 42 43 return max; 44 } 45 46 void 47 indexers_makecube(Indexer **is, coord_value_t ind, Cube *c) 48 { 49 /* Warning: anti-indexers are applied in the same order as indexers. */ 50 /* We assume order does not matter, but it would make more sense to */ 51 /* Apply them in reverse. */ 52 53 int i; 54 coord_value_t m; 55 56 make_solved(c); 57 m = indexers_getmax(is); 58 for (i = 0; is[i] != NULL; i++) { 59 m /= is[i]->n; 60 is[i]->to_cube(ind / m, c); 61 ind %= m; 62 } 63 } 64 65 void 66 alloc_sd(Coordinate *coord, bool gen) 67 { 68 size_t M; 69 70 M = coord->base[0]->max; 71 coord->symclass = malloc(M * sizeof(coord_value_t)); 72 coord->transtorep = malloc(M * sizeof(Trans)); 73 if (gen) { 74 coord->selfsim = malloc(M * sizeof(coord_value_t)); 75 coord->symrep = malloc(M * sizeof(coord_value_t)); 76 } 77 } 78 79 void 80 alloc_mtable(Coordinate *coord) 81 { 82 Move m; 83 84 for (m = 0; m < NMOVES_HTM; m++) 85 coord->mtable[m] = malloc(coord->max * sizeof(coord_value_t)); 86 } 87 88 void 89 alloc_ttrep_move(Coordinate *coord) 90 { 91 Move m; 92 93 for (m = 0; m < NMOVES_HTM; m++) 94 coord->ttrep_move[m] = malloc(coord->max * sizeof(Trans)); 95 } 96 97 void 98 alloc_ttable(Coordinate *coord) 99 { 100 Trans t; 101 102 for (t = 0; t < NTRANS; t++) 103 coord->ttable[t] = malloc(coord->max * sizeof(coord_value_t)); 104 } 105 106 void 107 alloc_ptable(Coordinate *coord, bool gen) 108 { 109 size_t sz; 110 111 coord->compact = coord->base[1] != NULL; 112 sz = ptablesize(coord) * (coord->compact && gen ? 2 : 1); 113 coord->ptable = malloc(sz * sizeof(entry_group_t)); 114 } 115 116 static size_t 117 copy_coord_mtable(Coordinate *coord, char *buf, Copier *copy) 118 { 119 Move m; 120 size_t b, rowsize; 121 122 b = 0; 123 rowsize = coord->max * sizeof(coord_value_t); 124 for (m = 0; m < NMOVES_HTM; m++) { 125 copy(coord->mtable[m], &buf[b], rowsize); 126 b += rowsize; 127 } 128 129 return b; 130 } 131 132 static size_t 133 copy_coord_ttrep_move(Coordinate *coord, char *buf, Copier *copy) 134 { 135 Move m; 136 size_t b, rowsize; 137 138 b = 0; 139 rowsize = coord->max * sizeof(Trans); 140 for (m = 0; m < NMOVES_HTM; m++) { 141 copy(coord->ttrep_move[m], &buf[b], rowsize); 142 b += rowsize; 143 } 144 145 return b; 146 } 147 148 static size_t 149 copy_coord_sd(Coordinate *coord, char *buf, Copier *copy) 150 { 151 size_t b, size_max, rowsize_ttr, rowsize_symc; 152 153 b = 0; 154 155 size_max = sizeof(coord_value_t); 156 copy(&coord->max, &buf[b], size_max); 157 b += size_max; 158 159 rowsize_ttr = coord->base[0]->max * sizeof(Trans); 160 copy(coord->transtorep, &buf[b], rowsize_ttr); 161 b += rowsize_ttr; 162 163 rowsize_symc = coord->base[0]->max * sizeof(coord_value_t); 164 copy(coord->symclass, &buf[b], rowsize_symc); 165 b += rowsize_symc; 166 167 return b; 168 } 169 170 static size_t 171 copy_coord_ttable(Coordinate *coord, char *buf, Copier *copy) 172 { 173 Trans t; 174 size_t b, rowsize; 175 176 b = 0; 177 rowsize = coord->max * sizeof(coord_value_t); 178 for (t = 0; t < NTRANS; t++) { 179 copy(coord->ttable[t], &buf[b], rowsize); 180 b += rowsize; 181 } 182 183 return b; 184 } 185 186 static size_t 187 copy_ptable(Coordinate *coord, char *buf, Copier *copy) 188 { 189 size_t b, size_base, size_count, size_ptable; 190 191 b = 0; 192 193 size_base = sizeof(coord->ptablebase); 194 copy(&coord->ptablebase, &buf[b], size_base); 195 b += size_base; 196 197 size_count = 16 * sizeof(coord_value_t); 198 copy(&coord->count, &buf[b], size_count); 199 b += size_count; 200 201 size_ptable = ptablesize(coord) * sizeof(entry_group_t); 202 copy(coord->ptable, &buf[b], size_ptable); 203 b += size_ptable; 204 205 return b; 206 } 207 208 coord_value_t 209 index_coord(Coordinate *coord, Cube *cube, Trans *offtrans) 210 { 211 coord_value_t c[2], cnosym; 212 Trans ttr; 213 214 switch (coord->type) { 215 case COMP_COORD: 216 if (offtrans != NULL) 217 *offtrans = uf; 218 219 return indexers_getind(coord->i, cube); 220 case SYM_COORD: 221 cnosym = index_coord(coord->base[0], cube, NULL); 222 ttr = coord->transtorep[cnosym]; 223 224 if (offtrans != NULL) 225 *offtrans = ttr; 226 227 return coord->symclass[cnosym]; 228 case SYMCOMP_COORD: 229 c[0] = index_coord(coord->base[0], cube, NULL); 230 cnosym = index_coord(coord->base[0]->base[0], cube, NULL); 231 ttr = coord->base[0]->transtorep[cnosym]; 232 c[1] = index_coord(coord->base[1], cube, NULL); 233 c[1] = trans_coord(coord->base[1], ttr, c[1]); 234 235 if (offtrans != NULL) 236 *offtrans = ttr; 237 238 return c[0] * coord->base[1]->max + c[1]; 239 default: 240 break; 241 } 242 243 return coord->max; /* Only reached in case of error */ 244 } 245 246 coord_value_t 247 move_coord(Coordinate *coord, Move m, coord_value_t ind, Trans *offtrans) 248 { 249 coord_value_t i[2], M; 250 Trans ttr; 251 252 /* Some safety checks should be done here, but for performance * 253 * reasons we'd rather do them before calling this function. * 254 * We should check if coord is generated. */ 255 256 switch (coord->type) { 257 case COMP_COORD: 258 if (offtrans != NULL) 259 *offtrans = uf; 260 261 return coord->mtable[m][ind]; 262 case SYM_COORD: 263 ttr = coord->ttrep_move[m][ind]; 264 265 if (offtrans != NULL) 266 *offtrans = ttr; 267 268 return coord->mtable[m][ind]; 269 case SYMCOMP_COORD: 270 M = coord->base[1]->max; 271 i[0] = ind / M; 272 i[1] = ind % M; 273 ttr = coord->base[0]->ttrep_move[m][i[0]]; 274 i[0] = coord->base[0]->mtable[m][i[0]]; 275 i[1] = coord->base[1]->mtable[m][i[1]]; 276 i[1] = coord->base[1]->ttable[ttr][i[1]]; 277 278 if (offtrans != NULL) 279 *offtrans = ttr; 280 281 return i[0] * M + i[1]; 282 default: 283 break; 284 } 285 286 return coord->max; /* Only reached in case of error */ 287 } 288 289 coord_value_t 290 trans_coord(Coordinate *coord, Trans t, coord_value_t ind) 291 { 292 coord_value_t i[2], M; 293 294 /* Some safety checks should be done here, but for performance * 295 * reasons we'd rather do them before calling this function. * 296 * We should check if coord is generated. */ 297 298 switch (coord->type) { 299 case COMP_COORD: 300 return coord->ttable[t][ind]; 301 case SYM_COORD: 302 return ind; 303 case SYMCOMP_COORD: 304 M = coord->base[1]->max; 305 i[0] = ind / M; /* Always fixed */ 306 i[1] = ind % M; 307 i[1] = coord->base[1]->ttable[t][i[1]]; 308 return i[0] * M + i[1]; 309 default: 310 break; 311 } 312 313 return coord->max; /* Only reached in case of error */ 314 } 315 316 size_t 317 ptablesize(Coordinate *coord) 318 { 319 coord_value_t e; 320 321 e = coord->compact ? ENTRIES_PER_GROUP_COMPACT : ENTRIES_PER_GROUP; 322 323 return (coord->max + e - 1) / e; 324 } 325 326 void 327 ptableupdate(Coordinate *coord, coord_value_t ind, int n) 328 { 329 int sh; 330 entry_group_t mask; 331 coord_value_t i; 332 333 if (ptableval(coord, ind) <= n) 334 return; 335 336 sh = 4 * (ind % ENTRIES_PER_GROUP); 337 mask = ((entry_group_t)15) << sh; 338 i = ind/ENTRIES_PER_GROUP; 339 coord->ptable[i] &= ~mask; 340 coord->ptable[i] |= (((entry_group_t)n)&15) << sh; 341 342 coord->updated++; 343 } 344 345 int 346 ptableval(Coordinate *coord, coord_value_t ind) 347 { 348 int ret, j, sh; 349 coord_value_t e, ii; 350 351 if (coord->compact) { 352 e = ENTRIES_PER_GROUP_COMPACT; 353 sh = (ind % e) * 2; 354 ret = (coord->ptable[ind/e] & (3 << sh)) >> sh; 355 if (ret != 0) 356 return ret + coord->ptablebase; 357 for (j = 0; j < 2 && coord->base[j] != NULL; j++) ; 358 j--; 359 for ( ; j >= 0; j--) { 360 ii = ind % coord->base[j]->max; 361 ret = MAX(ret, ptableval(coord->base[j], ii)); 362 ind /= coord->base[j]->max; 363 } 364 return ret; 365 } 366 367 e = ENTRIES_PER_GROUP; 368 sh = (ind % e) * 4; 369 return (coord->ptable[ind/e] & (15 << sh)) >> sh; 370 } 371 372 static size_t 373 copy_coord(Coordinate *coord, char *buf, bool alloc, Copier *copy) 374 { 375 size_t b; 376 377 b = 0; 378 switch (coord->type) { 379 case COMP_COORD: 380 if (alloc) { 381 coord->max = indexers_getmax(coord->i); 382 alloc_mtable(coord); 383 } 384 b += copy_coord_mtable(coord, &buf[b], copy); 385 386 if (alloc) 387 alloc_ttable(coord); 388 b += copy_coord_ttable(coord, &buf[b], copy); 389 390 if (alloc) 391 alloc_ptable(coord, false); 392 b += copy_ptable(coord, &buf[b], copy); 393 394 break; 395 case SYM_COORD: 396 if (alloc) { 397 coord->base[0]->max = 398 indexers_getmax(coord->base[0]->i); 399 alloc_sd(coord, false); 400 } 401 b += copy_coord_sd(coord, &buf[b], copy); 402 403 if (alloc) 404 alloc_mtable(coord); 405 b += copy_coord_mtable(coord, &buf[b], copy); 406 407 if (alloc) 408 alloc_ttrep_move(coord); 409 b += copy_coord_ttrep_move(coord, &buf[b], copy); 410 411 if (alloc) 412 alloc_ptable(coord, false); 413 b += copy_ptable(coord, &buf[b], copy); 414 415 break; 416 case SYMCOMP_COORD: 417 if (alloc) { 418 coord->max = coord->base[0]->max * coord->base[1]->max; 419 alloc_ptable(coord, false); 420 } 421 b += copy_ptable(coord, &buf[b], copy); 422 423 break; 424 default: 425 break; 426 } 427 428 return b; 429 } 430 431 size_t 432 read_coord(Coordinate *coord, char *buf) 433 { 434 return copy_coord(coord, buf, true, readin); 435 } 436 437 size_t 438 write_coord(Coordinate *coord, char *buf) 439 { 440 return copy_coord(coord, buf, false, writeout); 441 }