nissy-fmc

A Rubik's cube FMC assistant
git clone https://git.tronto.net/nissy-fmc
Download | Log | Files | Refs | README | LICENSE

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 }