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 }