portable.h (5604B)
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 /* TODO: optimize this (use bit tricks?) */ 13 STATIC_INLINE int 14 popcount_u32(uint32_t x) 15 { 16 int ret; 17 18 for (ret = 0; x != 0; x >>= 1) 19 ret += x & 1; 20 21 return ret; 22 } 23 24 STATIC void 25 pieces(cube_t cube[static 1], uint8_t c[static 8], uint8_t e[static 12]) 26 { 27 memcpy(c, cube->corner, 8); 28 memcpy(e, cube->edge, 12); 29 } 30 31 STATIC_INLINE bool 32 equal(cube_t c1, cube_t c2) 33 { 34 uint8_t i; 35 bool ret; 36 37 ret = true; 38 for (i = 0; i < 8; i++) 39 ret = ret && c1.corner[i] == c2.corner[i]; 40 for (i = 0; i < 12; i++) 41 ret = ret && c1.edge[i] == c2.edge[i]; 42 43 return ret; 44 } 45 46 STATIC_INLINE cube_t 47 invertco(cube_t c) 48 { 49 uint8_t i, piece, orien; 50 cube_t ret; 51 52 ret = c; 53 for (i = 0; i < 8; i++) { 54 piece = c.corner[i]; 55 orien = ((piece << 1) | (piece >> 1)) & COBITS_2; 56 ret.corner[i] = (piece & PBITS) | orien; 57 } 58 59 return ret; 60 } 61 62 STATIC_INLINE void 63 compose_edges_inplace(cube_t c1, cube_t c2, cube_t *ret) 64 { 65 uint8_t i, piece1, piece2, p, orien; 66 67 for (i = 0; i < 12; i++) { 68 piece2 = c2.edge[i]; 69 p = piece2 & PBITS; 70 piece1 = c1.edge[p]; 71 orien = (piece2 ^ piece1) & EOBIT; 72 ret->edge[i] = (piece1 & PBITS) | orien; 73 } 74 } 75 76 STATIC_INLINE void 77 compose_corners_inplace(cube_t c1, cube_t c2, cube_t *ret) 78 { 79 uint8_t i, piece1, piece2, p, orien, aux, auy; 80 81 for (i = 0; i < 8; i++) { 82 piece2 = c2.corner[i]; 83 p = piece2 & PBITS; 84 piece1 = c1.corner[p]; 85 aux = (piece2 & COBITS) + (piece1 & COBITS); 86 auy = (aux + CTWIST_CW) >> 2; 87 orien = (aux + auy) & COBITS_2; 88 ret->corner[i] = (piece1 & PBITS) | orien; 89 } 90 } 91 92 STATIC_INLINE cube_t 93 compose_edges(cube_t c1, cube_t c2) 94 { 95 cube_t ret = ZERO_CUBE; 96 97 compose_edges_inplace(c1, c2, &ret); 98 99 return ret; 100 } 101 102 STATIC_INLINE cube_t 103 compose_corners(cube_t c1, cube_t c2) 104 { 105 cube_t ret = ZERO_CUBE; 106 107 compose_corners_inplace(c1, c2, &ret); 108 109 return ret; 110 } 111 112 STATIC_INLINE cube_t 113 compose(cube_t c1, cube_t c2) 114 { 115 cube_t ret = ZERO_CUBE; 116 117 compose_edges_inplace(c1, c2, &ret); 118 compose_corners_inplace(c1, c2, &ret); 119 120 return ret; 121 } 122 123 cube_t 124 inverse(cube_t cube) 125 { 126 uint8_t i, piece, orien; 127 cube_t ret; 128 129 for (i = 0; i < 12; i++) { 130 piece = cube.edge[i]; 131 orien = piece & EOBIT; 132 ret.edge[piece & PBITS] = i | orien; 133 } 134 135 for (i = 0; i < 8; i++) { 136 piece = cube.corner[i]; 137 orien = ((piece << 1) | (piece >> 1)) & COBITS_2; 138 ret.corner[piece & PBITS] = i | orien; 139 } 140 141 return ret; 142 } 143 144 STATIC_INLINE int64_t 145 coord_co(cube_t c) 146 { 147 int i, p, ret; 148 149 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3) 150 ret += p * (c.corner[i] >> COSHIFT); 151 152 return ret; 153 } 154 155 STATIC_INLINE cube_t 156 invcoord_co(int64_t coord) 157 { 158 int64_t i, c, p; 159 cube_t cube; 160 161 cube = SOLVED_CUBE; 162 for (i = 0, p = 0, c = coord; i < 7; i++, c /= 3) { 163 p += c % 3; 164 cube.corner[i] |= (c % 3) << COSHIFT; 165 } 166 167 cube.corner[7] |= ((3 - (p % 3)) % 3) << COSHIFT; 168 169 return cube; 170 } 171 172 /* 173 For corner separation, we consider the axis (a.k.a. tetrad) each 174 corner belongs to as 0 or 1 and we translate this sequence into binary. 175 Ignoring the last bit, we have a value up to 2^7, but not all values are 176 possible. Encoding this as a number from 0 to C(8,4) would save about 40% 177 of space, but we are not going to use this coordinate in large tables. 178 */ 179 STATIC_INLINE int64_t 180 coord_csep(cube_t c) 181 { 182 int i, p; 183 int64_t ret; 184 185 for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2) 186 ret += p * ((c.corner[i] & CSEPBIT) >> 2); 187 188 return ret; 189 } 190 191 STATIC_INLINE int64_t 192 coord_cocsep(cube_t c) 193 { 194 return (coord_co(c) << 7) + coord_csep(c); 195 } 196 197 STATIC_INLINE int64_t 198 coord_eo(cube_t c) 199 { 200 int i, p; 201 int64_t ret; 202 203 for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2) 204 ret += p * (c.edge[i] >> EOSHIFT); 205 206 return ret; 207 } 208 209 /* 210 We encode the edge separation as a number from 0 to C(12,4)*C(8,4). 211 It can be seen as the composition of two "subset index" coordinates. 212 */ 213 STATIC_INLINE int64_t 214 coord_esep(cube_t c) 215 { 216 int64_t i, j, jj, k, l, ret1, ret2, bit1, bit2, is1; 217 218 for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) { 219 /* Simple version: 220 if (c.edge[i] & ESEPBIT_2) { 221 ret1 += binomial[11-i][k--]; 222 } else { 223 if (c.edge[i] & ESEPBIT_1) 224 ret2 += binomial[7-j][l--]; 225 j++; 226 } 227 */ 228 229 bit1 = (c.edge[i] & ESEPBIT_1) >> 2; 230 bit2 = (c.edge[i] & ESEPBIT_2) >> 3; 231 is1 = (1 - bit2) * bit1; 232 233 ret1 += bit2 * binomial[11-i][k]; 234 k -= bit2; 235 236 jj = j < 8; 237 ret2 += jj * is1 * binomial[7-(j*jj)][l]; 238 l -= is1; 239 j += (1-bit2); 240 } 241 242 return ret1 * 70 + ret2; 243 } 244 245 STATIC_INLINE cube_t 246 invcoord_esep(int64_t esep) 247 { 248 cube_t ret; 249 250 ret = SOLVED_CUBE; 251 invcoord_esep_array(esep % 70, esep / 70, ret.edge); 252 253 return ret; 254 } 255 256 STATIC_INLINE void 257 copy_corners(cube_t dest[static 1], cube_t src) 258 { 259 memcpy(&dest->corner, src.corner, sizeof(src.corner)); 260 } 261 262 STATIC_INLINE void 263 copy_edges(cube_t dest[static 1], cube_t src) 264 { 265 memcpy(&dest->edge, src.edge, sizeof(src.edge)); 266 } 267 268 STATIC_INLINE void 269 set_eo(cube_t cube[static 1], int64_t eo) 270 { 271 uint8_t i, sum, flip; 272 273 for (sum = 0, i = 1; i < 12; i++, eo >>= 1) { 274 flip = eo % 2; 275 sum += flip; 276 cube->edge[i] = (cube->edge[i] & ~EOBIT) | (EOBIT * flip); 277 } 278 cube->edge[0] = (cube->edge[0] & ~EOBIT) | (EOBIT * (sum % 2)); 279 }