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

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