nissy-core

The "engine" of nissy, including the H48 optimal solver.
git clone https://git.tronto.net/nissy-core
Download | Log | Files | Refs | README | LICENSE

cube.h (7755B)

      1 STATIC bool cube_true(cube_t);
      2 
      3 STATIC cube_t cubefromarray(uint8_t [static 8], uint8_t [static 12]);
      4 STATIC bool isconsistent(oriented_cube_t);
      5 STATIC bool issolvable(oriented_cube_t);
      6 STATIC bool issolved(oriented_cube_t);
      7 STATIC bool iserror(oriented_cube_t);
      8 STATIC void getcube_fix(long long *, long long *,
      9     long long *, long long *, long long *);
     10 STATIC cube_t getcube(uint64_t, uint64_t, uint64_t, uint64_t);
     11 
     12 STATIC oriented_cube_t readcube(const char *);
     13 STATIC int64_t writecube(oriented_cube_t, size_t n, char [n]);
     14 STATIC uint8_t readco(const char *);
     15 STATIC uint8_t readcp(const char *);
     16 STATIC uint8_t readeo(const char *);
     17 STATIC uint8_t readep(const char *);
     18 
     19 STATIC uint8_t b32toedge(char);
     20 STATIC uint8_t b32tocorner(char);
     21 STATIC char edgetob32(uint8_t);
     22 STATIC char cornertob32(uint8_t);
     23 
     24 /* Used e.g. by the CORNERS coordinate, when a function pointer is needed */
     25 STATIC bool
     26 cube_true(cube_t cube)
     27 {
     28 	return true;
     29 }
     30 
     31 STATIC cube_t
     32 cubefromarray(uint8_t c[static 8], uint8_t e[static 12])
     33 {
     34 	return STATIC_CUBE(
     35 	    c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7],
     36 	    e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7],
     37 	    e[8], e[9], e[10], e[11]);
     38 }
     39 
     40 STATIC bool
     41 isconsistent(oriented_cube_t cube)
     42 {
     43 	uint8_t i, p, e, piece, corner[8], edge[12];
     44 	bool found[12];
     45 
     46 	pieces(&cube.cube, corner, edge);
     47 
     48 	for (i = 0; i < 12; i++)
     49 		found[i] = false;
     50 	for (i = 0; i < 12; i++) {
     51 		piece = edge[i];
     52 		p = piece & PBITS;
     53 		e = piece & EOBIT;
     54 		if (p >= 12)
     55 			goto inconsistent_ep;
     56 		if (e != 0 && e != EOBIT)
     57 			goto inconsistent_eo;
     58 		found[p] = true;
     59 	}
     60 	for (i = 0; i < 12; i++)
     61 		if (!found[i])
     62 			goto inconsistent_ep;
     63 
     64 	for (i = 0; i < 8; i++)
     65 		found[i] = false;
     66 	for (i = 0; i < 8; i++) {
     67 		piece = corner[i];
     68 		p = piece & PBITS;
     69 		e = piece & COBITS;
     70 		if (p >= 8)
     71 			goto inconsistent_cp;
     72 		if (e != 0 && e != CTWIST_CW && e != CTWIST_CCW)
     73 			goto inconsistent_co;
     74 		found[p] = true;
     75 	}
     76 	for (i = 0; i < 8; i++)
     77 		if (!found[i])
     78 			goto inconsistent_cp;
     79 
     80 	if (cube.orientation >= 24)
     81 		goto inconsistent_orientation;
     82 
     83 	return true;
     84 
     85 inconsistent_ep:
     86 inconsistent_cp:
     87 inconsistent_eo:
     88 inconsistent_co:
     89 inconsistent_orientation:
     90 	/* We used to do more logging here, hence the different labels */
     91 	return false;
     92 }
     93 
     94 STATIC bool
     95 issolvable(oriented_cube_t cube)
     96 {
     97 	uint8_t i, eo, co, piece, edge[12], corner[8], ep[12], cp[8];
     98 
     99 	DBG_ASSERT(isconsistent(cube), "issolvable: cube is inconsistent\n");
    100 
    101 	pieces(&cube.cube, corner, edge);
    102 	for (i = 0; i < 12; i++)
    103 		ep[i] = edge[i] & PBITS;
    104 	for (i = 0; i < 8; i++)
    105 		cp[i] = corner[i] & PBITS;
    106 
    107 	if (permsign(12, ep) != permsign(8, cp))
    108 		goto issolvable_parity;
    109 
    110 	eo = 0;
    111 	for (i = 0; i < 12; i++) {
    112 		piece = edge[i];
    113 		eo += (piece & EOBIT) >> EOSHIFT;
    114 	}
    115 	if (eo % 2 != 0)
    116 		goto issolvable_eo;
    117 
    118 	co = 0;
    119 	for (i = 0; i < 8; i++) {
    120 		piece = corner[i];
    121 		co += (piece & COBITS) >> COSHIFT;
    122 	}
    123 	if (co % 3 != 0)
    124 		goto issolvable_co;
    125 
    126 	return true;
    127 
    128 issolvable_parity:
    129 	LOG("There is parity\n");
    130 	return false;
    131 issolvable_eo:
    132 	LOG("EO is not solvable\n");
    133 	return false;
    134 issolvable_co:
    135 	LOG("CO is not solvable\n");
    136 	return false;
    137 }
    138 
    139 bool
    140 issolved(oriented_cube_t cube)
    141 {
    142 	return equal(cube.cube, SOLVED_CUBE);
    143 }
    144 
    145 bool
    146 iserror(oriented_cube_t cube)
    147 {
    148 	return equal(cube.cube, ZERO_CUBE);
    149 }
    150 
    151 STATIC void
    152 getcube_fix(
    153 	long long *ep,
    154 	long long *eo,
    155 	long long *cp,
    156 	long long *co,
    157 	long long *orien
    158 )
    159 {
    160 	uint8_t e[12], c[8], coarr[8];
    161 
    162 	*ep = POSITIVE_MOD(*ep, (long long)FACT_12);
    163 	*eo = POSITIVE_MOD(*eo, (long long)POW_2_11);
    164 	*cp = POSITIVE_MOD(*cp, (long long)FACT_8);
    165 	*co = POSITIVE_MOD(*co, (long long)POW_3_7);
    166 	*orien = POSITIVE_MOD(*orien, 24LL);
    167 
    168 	indextoperm((uint64_t)*ep, 12, e);
    169 	indextoperm((uint64_t)*cp, 8, c);
    170 	if (permsign(12, e) != permsign(8, c)) {
    171 		SWAP(c[0], c[1]);
    172 		*cp = (long long)permtoindex(8, c);
    173 
    174 		sumzerotodigits((uint64_t)*co, 8, 3, coarr);
    175 		SWAP(coarr[0], coarr[1]);
    176 		*co = (uint64_t)digitstosumzero(8, coarr, 3);
    177 	}
    178 }
    179 
    180 STATIC cube_t
    181 getcube(uint64_t ep, uint64_t eo, uint64_t cp, uint64_t co)
    182 {
    183 	uint8_t i, earr[12], carr[8], eoarr[12], coarr[8];
    184 
    185 	sumzerotodigits(eo, 12, 2, eoarr);
    186 	DBG_ASSERT(eoarr[0] != UINT8_ERROR, "Error making EO");
    187 	indextoperm(ep, 12, earr);
    188 	DBG_ASSERT(earr[0] != UINT8_ERROR, "Error making EP");
    189 	for (i = 0; i < 12; i++)
    190 		earr[i] |= eoarr[i] << EOSHIFT;
    191 
    192 	sumzerotodigits(co, 8, 3, coarr);
    193 	DBG_ASSERT(coarr[0] != UINT8_ERROR, "Error making CO");
    194 	indextoperm(cp, 8, carr);
    195 	DBG_ASSERT(carr[0] != UINT8_ERROR, "Error making CP");
    196 	for (i = 0; i < 8; i++)
    197 		carr[i] |= coarr[i] << COSHIFT;
    198 
    199 	return cubefromarray(carr, earr);
    200 }
    201 
    202 STATIC uint8_t
    203 readco(const char *str)
    204 {
    205 	if (*str == '0')
    206 		return 0;
    207 	if (*str == '1')
    208 		return CTWIST_CW;
    209 	if (*str == '2')
    210 		return CTWIST_CCW;
    211 
    212 	LOG("Error reading CO\n");
    213 	return UINT8_ERROR;
    214 }
    215 
    216 STATIC uint8_t
    217 readcp(const char *str)
    218 {
    219 	uint8_t c;
    220 
    221 	for (c = 0; c < 8; c++)
    222 		if (!strncmp(str, cornerstr[c], 3) ||
    223 		    !strncmp(str, cornerstralt[c], 3))
    224 			return c;
    225 
    226 	LOG("Error reading CP\n");
    227 	return UINT8_ERROR;
    228 }
    229 
    230 STATIC uint8_t
    231 readeo(const char *str)
    232 {
    233 	if (*str == '0')
    234 		return 0;
    235 	if (*str == '1')
    236 		return EFLIP;
    237 
    238 	LOG("Error reading EO\n");
    239 	return UINT8_ERROR;
    240 }
    241 
    242 STATIC uint8_t
    243 readep(const char *str)
    244 {
    245 	uint8_t e;
    246 
    247 	for (e = 0; e < 12; e++)
    248 		if (!strncmp(str, edgestr[e], 2))
    249 			return e;
    250 
    251 	LOG("Error reading EP\n");
    252 	return UINT8_ERROR;
    253 }
    254 
    255 STATIC oriented_cube_t
    256 readcube(const char *buf)
    257 {
    258 	int i;
    259 	uint8_t c[8], e[12], orientation;
    260 
    261 	for (i = 0; i < 8; i++) {
    262 		c[i] = b32tocorner(buf[i]);
    263 		if (c[i] == UINT8_ERROR) {
    264 			LOG("Error reading corner %d ", i);
    265 			if (buf[i] == 0) {
    266 				LOG("(string terminated early)\n");
    267 			} else {
    268 				LOG("(char '%c')\n", buf[i]);
    269 			}
    270 			return ZERO_ORIENTED_CUBE;
    271 		}
    272 	}
    273 
    274 	if (buf[8] != '=') {
    275 		LOG("Error reading separator: a single '=' "
    276 		    "must be used to separate edges and corners\n");
    277 		return ZERO_ORIENTED_CUBE;
    278 	}
    279 
    280 	for (i = 0; i < 12; i++) {
    281 		e[i] = b32toedge(buf[i+9]);
    282 		if (e[i] == UINT8_ERROR) {
    283 			LOG("Error reading edge %d ", i);
    284 			if (buf[i+9] == 0) {
    285 				LOG("(string terminated early)\n");
    286 			} else {
    287 				LOG("(char '%c')\n", buf[i+9]);
    288 			}
    289 			return ZERO_ORIENTED_CUBE;
    290 		}
    291 	}
    292 
    293 	orientation = (uint8_t)(buf[22] - 'A');
    294 	if (orientation >= 24) {
    295 		LOG("Error reading orientation: impossible value %" PRIu8
    296 		    " (%c)\n", orientation, buf[22]);
    297 		return ZERO_ORIENTED_CUBE;
    298 	}
    299 
    300 	return (oriented_cube_t) {
    301 		.cube = cubefromarray(c, e),
    302 		.orientation = orientation
    303 	};
    304 }
    305 
    306 STATIC int64_t
    307 writecube(oriented_cube_t cube, size_t buf_size, char buf[buf_size])
    308 {
    309 	int i;
    310 	uint8_t corner[8], edge[12];
    311 
    312 	if (buf_size < NISSY_SIZE_CUBE) {
    313 		LOG("Cannot write cube: buffer size must be at least %u "
    314 		    "bytes, but the provided one is %zu bytes.\n",
    315 		    NISSY_SIZE_CUBE, buf_size);
    316 		return NISSY_ERROR_BUFFER_SIZE;
    317 	}
    318 
    319 	pieces(&cube.cube, corner, edge);
    320 
    321 	for (i = 0; i < 8; i++)
    322 		buf[i] = cornertob32(corner[i]);
    323 
    324 	buf[8] = '=';
    325 
    326 	for (i = 0; i < 12; i++)
    327 		buf[i+9] = edgetob32(edge[i]);
    328 
    329 	buf[21] = '=';
    330 	buf[22] = (char)cube.orientation + 'A';
    331 	buf[23] = '\0';
    332 
    333 	return NISSY_OK;
    334 }
    335 
    336 STATIC uint8_t
    337 b32toedge(char c)
    338 {
    339 	if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'f')))
    340 		return UINT8_ERROR;
    341 
    342 	return c <= 'Z' ? (uint8_t)(c - 'A') : (uint8_t)(c - 'a') + 26;
    343 }
    344 
    345 STATIC uint8_t
    346 b32tocorner(char c) {
    347 	uint8_t val;
    348 
    349 	if (!((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'f')))
    350 		return UINT8_ERROR;
    351 
    352 	val = c <= 'Z' ? (uint8_t)(c - 'A') : (uint8_t)(c - 'a') + 26;
    353 
    354 	return (val & 7) | ((val & 24) << 2);
    355 }
    356 
    357 STATIC char
    358 edgetob32(uint8_t edge)
    359 {
    360 	return edge < 26 ? 'A' + (char)edge : 'a' + (char)(edge - 26);
    361 }
    362 
    363 STATIC char
    364 cornertob32(uint8_t corner)
    365 {
    366 	uint8_t val;
    367 
    368 	val = (corner & 7) | ((corner & 96) >> 2);
    369 
    370 	return val < 26 ? 'A' + (char)val : 'a' + (char)(val - 26);
    371 }