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

portable.h (7733B)


      1 #define STATIC_CUBE(c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl, \
      2     e_uf, e_ub, e_db, e_df, e_ur, e_ul, e_dl, e_dr, e_fr, e_fl, e_bl, e_br) \
      3     ((cube_t) { \
      4         .corner = { c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl }, \
      5         .edge = { e_uf, e_ub, e_db, e_df, e_ur, e_ul, \
      6                   e_dl, e_dr, e_fr, e_fl, e_bl, e_br } })
      7 #define ZERO_CUBE STATIC_CUBE( \
      8     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
      9 #define SOLVED_CUBE STATIC_CUBE( \
     10     0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
     11 
     12 STATIC_INLINE int
     13 popcount_u32(uint32_t x)
     14 {
     15 	/*
     16 	Bit trick: accumulate in pairs of bits, quads of bits and so on,
     17 	until the final result is the sum of all bits.
     18 
     19 	x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
     20 	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
     21 	x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
     22 	x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
     23 	x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);
     24 
     25 	The actual method we use is a small optimization of the one above.
     26 	*/
     27 
     28 	x -= (x >> UINT32_C(1)) & UINT32_C(0x55555555);
     29 	x = (x & UINT32_C(0x33333333)) +
     30 	    ((x >> UINT32_C(2)) & UINT32_C(0x33333333));
     31 	x = (x + (x >> UINT32_C(4))) & UINT32_C(0x0F0F0F0F);
     32 	x = (x * UINT32_C(0x01010101)) >> UINT32_C(24);
     33 
     34 	return (int)x;
     35 }
     36 
     37 STATIC void
     38 pieces(cube_t cube[static 1], uint8_t c[static 8], uint8_t e[static 12])
     39 {
     40 	memcpy(c, cube->corner, 8);
     41 	memcpy(e, cube->edge, 12);
     42 }
     43 
     44 STATIC_INLINE bool
     45 equal(cube_t c1, cube_t c2)
     46 {
     47 	uint8_t i;
     48 	bool ret;
     49 
     50 	ret = true;
     51 	for (i = 0; i < 8; i++)
     52 		ret = ret && c1.corner[i] == c2.corner[i];
     53 	for (i = 0; i < 12; i++)
     54 		ret = ret && c1.edge[i] == c2.edge[i];
     55 
     56 	return ret;
     57 }
     58 
     59 STATIC_INLINE cube_t
     60 invertco(cube_t c)
     61 {
     62 	uint8_t i, piece, orien;
     63 	cube_t ret;
     64 
     65 	ret = c;
     66 	for (i = 0; i < 8; i++) {
     67 		piece = c.corner[i];
     68 		orien = ((piece << 1) | (piece >> 1)) & COBITS_2;
     69 		ret.corner[i] = (piece & PBITS) | orien;
     70 	}
     71 
     72 	return ret;
     73 }
     74 
     75 STATIC_INLINE void
     76 compose_edges_inplace(cube_t c1, cube_t c2, cube_t *ret)
     77 {
     78 	uint8_t i, piece1, piece2, p, orien;
     79 
     80 	for (i = 0; i < 12; i++) {
     81 		piece2 = c2.edge[i];
     82 		p = piece2 & PBITS;
     83 		piece1 = c1.edge[p];
     84 		orien = (piece2 ^ piece1) & EOBIT;
     85 		ret->edge[i] = (piece1 & PBITS) | orien;
     86 	}
     87 }
     88 
     89 STATIC_INLINE void
     90 compose_corners_inplace(cube_t c1, cube_t c2, cube_t *ret)
     91 {
     92 	uint8_t i, piece1, piece2, p, orien, aux, auy;
     93 
     94 	for (i = 0; i < 8; i++) {
     95 		piece2 = c2.corner[i];
     96 		p = piece2 & PBITS;
     97 		piece1 = c1.corner[p];
     98 		aux = (piece2 & COBITS) + (piece1 & COBITS);
     99 		auy = (aux + CTWIST_CW) >> 2;
    100 		orien = (aux + auy) & COBITS_2;
    101 		ret->corner[i] = (piece1 & PBITS) | orien;
    102 	}
    103 }
    104 
    105 STATIC_INLINE cube_t
    106 compose_edges(cube_t c1, cube_t c2)
    107 {
    108 	cube_t ret = ZERO_CUBE;
    109 
    110 	compose_edges_inplace(c1, c2, &ret);
    111 
    112 	return ret;
    113 }
    114 
    115 STATIC_INLINE cube_t
    116 compose_corners(cube_t c1, cube_t c2)
    117 {
    118 	cube_t ret = ZERO_CUBE;
    119 
    120 	compose_corners_inplace(c1, c2, &ret);
    121 
    122 	return ret;
    123 }
    124 
    125 STATIC_INLINE cube_t
    126 compose(cube_t c1, cube_t c2)
    127 {
    128 	cube_t ret = ZERO_CUBE;
    129 
    130 	compose_edges_inplace(c1, c2, &ret);
    131 	compose_corners_inplace(c1, c2, &ret);
    132 
    133 	return ret;
    134 }
    135 
    136 cube_t
    137 inverse(cube_t cube)
    138 {
    139 	uint8_t i, piece, orien;
    140 	cube_t ret;
    141 
    142 	for (i = 0; i < 12; i++) {
    143 		piece = cube.edge[i];
    144 		orien = piece & EOBIT;
    145 		ret.edge[piece & PBITS] = i | orien;
    146 	}
    147 
    148 	for (i = 0; i < 8; i++) {
    149 		piece = cube.corner[i];
    150 		orien = ((piece << 1) | (piece >> 1)) & COBITS_2;
    151 		ret.corner[piece & PBITS] = i | orien;
    152 	}
    153 
    154 	return ret;
    155 }
    156 
    157 STATIC_INLINE uint64_t
    158 coord_co(cube_t c)
    159 {
    160 	int i, p, ret;
    161 
    162 	for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3)
    163 		ret += p * (c.corner[i] >> COSHIFT);
    164 
    165 	return ret;
    166 }
    167 
    168 STATIC_INLINE cube_t
    169 invcoord_co(uint64_t coord)
    170 {
    171 	uint64_t i, c, p;
    172 	cube_t cube;
    173 
    174 	cube = SOLVED_CUBE;
    175 	for (i = 0, p = 0, c = coord; i < 7; i++, c /= 3) {
    176 		p += c % 3;
    177 		cube.corner[i] |= (c % 3) << COSHIFT;
    178 	}
    179 
    180 	cube.corner[7] |= ((3 - (p % 3)) % 3) << COSHIFT;
    181 
    182 	return cube;
    183 }
    184 
    185 /*
    186 For corner separation, we consider the axis (a.k.a. tetrad) each
    187 corner belongs to as 0 or 1 and we translate this sequence into binary.
    188 Ignoring the last bit, we have a value up to 2^7, but not all values are
    189 possible. Encoding this as a number from 0 to C(8,4) would save about 40%
    190 of space, but we are not going to use this coordinate in large tables.
    191 */
    192 STATIC_INLINE uint64_t
    193 coord_csep(cube_t c)
    194 {
    195 	int i, p;
    196 	uint64_t ret;
    197 
    198 	for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2)
    199 		ret += p * ((c.corner[i] & CSEPBIT) >> 2);
    200 
    201 	return ret;
    202 }
    203 
    204 STATIC_INLINE uint64_t
    205 coord_cocsep(cube_t c)
    206 {
    207 	return (coord_co(c) << 7) + coord_csep(c);
    208 }
    209 
    210 STATIC_INLINE uint64_t
    211 coord_eo(cube_t c)
    212 {
    213 	int i, p;
    214 	uint64_t ret;
    215 
    216 	for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2)
    217 		ret += p * (c.edge[i] >> EOSHIFT);
    218 
    219 	return ret;
    220 }
    221 
    222 /*
    223 We encode the edge separation as a number from 0 to C(12,4)*C(8,4).
    224 It can be seen as the composition of two "subset index" coordinates.
    225 */
    226 STATIC_INLINE uint64_t
    227 coord_esep(cube_t c)
    228 {
    229 	uint64_t i, j, jj, k, l, ret1, ret2, bit1, bit2, is1;
    230 
    231 	for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) {
    232 		/* Simple version:
    233 		if (c.edge[i] & ESEPBIT_2) {
    234 			ret1 += binomial[11-i][k--];
    235 		} else {
    236 			if (c.edge[i] & ESEPBIT_1)
    237 				ret2 += binomial[7-j][l--];
    238 			j++;
    239 		}
    240 		*/
    241 
    242 		bit1 = (c.edge[i] & ESEPBIT_1) >> 2;
    243 		bit2 = (c.edge[i] & ESEPBIT_2) >> 3;
    244 		is1 = (1 - bit2) * bit1;
    245 
    246 		ret1 += bit2 * binomial[11-i][k];
    247 		k -= bit2;
    248 
    249 		jj = j < 8;
    250 		ret2 += jj * is1 * binomial[7-(j*jj)][l];
    251 		l -= is1;
    252 		j += (1-bit2);
    253 	}
    254 
    255 	return ret1 * 70 + ret2;
    256 }
    257 
    258 STATIC_INLINE cube_t
    259 invcoord_esep(uint64_t esep)
    260 {
    261 	cube_t ret;
    262 
    263 	ret = SOLVED_CUBE;
    264 	invcoord_esep_array(esep % 70, esep / 70, ret.edge);
    265 
    266 	return ret;
    267 }
    268 
    269 STATIC_INLINE void
    270 copy_corners(cube_t dest[static 1], cube_t src)
    271 {
    272 	memcpy(&dest->corner, src.corner, sizeof(src.corner));
    273 }
    274 
    275 STATIC_INLINE void
    276 copy_edges(cube_t dest[static 1], cube_t src)
    277 {
    278 	memcpy(&dest->edge, src.edge, sizeof(src.edge));
    279 }
    280 
    281 STATIC_INLINE void
    282 set_eo(cube_t cube[static 1], uint64_t eo)
    283 {
    284 	uint8_t i, sum, flip;
    285 
    286 	for (sum = 0, i = 1; i < 12; i++, eo >>= 1) {
    287 		flip = eo % 2;
    288 		sum += flip;
    289 		cube->edge[i] = (cube->edge[i] & ~EOBIT) | (EOBIT * flip);
    290 	}
    291 	cube->edge[0] = (cube->edge[0] & ~EOBIT) | (EOBIT * (sum % 2));
    292 }
    293 
    294 STATIC_INLINE uint64_t
    295 coord_cp(cube_t cube)
    296 {
    297 	int i;
    298 
    299 	for (i = 0; i < 8; i++)
    300 		cube.corner[i] &= PBITS;
    301 
    302 	return permtoindex(8, cube.corner);
    303 }
    304 
    305 STATIC_INLINE cube_t
    306 invcoord_cp(uint64_t i)
    307 {
    308 	uint8_t c[8];
    309 
    310 	indextoperm(i, 8, c);
    311 
    312 	return STATIC_CUBE(c[0], c[1], c[2], c[3], c[4], c[5], c[6], c[7],
    313 	    0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);
    314 }
    315 
    316 STATIC_INLINE uint64_t
    317 coord_epud(cube_t cube)
    318 {
    319 	int i;
    320 
    321 	for (i = 0; i < 8; i++)
    322 		cube.edge[i] &= PBITS;
    323 
    324 	return permtoindex(8, cube.edge);
    325 }
    326 
    327 STATIC_INLINE cube_t
    328 invcoord_epud(uint64_t i)
    329 {
    330 	uint8_t e[8];
    331 
    332 	indextoperm(i, 8, e);
    333 
    334 	return STATIC_CUBE(0, 1, 2, 3, 4, 5, 6, 7,
    335 	    e[0], e[1], e[2], e[3], e[4], e[5], e[6], e[7], 8, 9, 10, 11);
    336 }
    337 
    338 STATIC_INLINE uint64_t
    339 coord_epe(cube_t cube)
    340 {
    341         int i;
    342 
    343         for (i = 8; i < 12; i++)
    344                 cube.edge[i] = (cube.edge[i] & PBITS) - 8;
    345 
    346         return permtoindex(4, cube.edge+8);
    347 }
    348 
    349 STATIC_INLINE cube_t
    350 invcoord_epe(uint64_t i)
    351 {
    352         uint8_t e[4];
    353 
    354         indextoperm(i, 4, e);
    355 
    356         return STATIC_CUBE(0, 1, 2, 3, 4, 5, 6, 7,
    357             0, 1, 2, 3, 4, 5, 6, 7, e[0]+8, e[1]+8, e[2]+8, e[3]+8);
    358 }
    359 
    360 STATIC_INLINE bool
    361 is_eo_even(cube_t cube)
    362 {
    363 	uint8_t i, count;
    364 
    365 	for (i = 0, count = 0; i < 12; i++)
    366 		count += (cube.edge[i] & EOBIT) >> EOSHIFT;
    367 
    368 	return count % 2 == 0;
    369 }
    370 
    371 STATIC_INLINE uint64_t
    372 coord_epudsep(cube_t cube)
    373 {
    374 	return coord_epudsep_array(cube.edge);
    375 }
    376 
    377 STATIC_INLINE cube_t
    378 invcoord_epudsep(uint64_t c)
    379 {
    380 	cube_t ret;
    381 
    382 	ret = SOLVED_CUBE;
    383 	invcoord_epudsep_array(c, ret.edge);
    384 	return ret;
    385 }