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 (7585B)

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