diff options
Diffstat (limited to '')
| -rw-r--r-- | src/constants.h | 214 | ||||
| -rw-r--r-- | src/cube_avx2.h | 32 | ||||
| -rw-r--r-- | src/cube_portable.h | 17 | ||||
| -rw-r--r-- | src/cube_routines.h | 6 | ||||
| -rw-r--r-- | src/solve_h48.h | 114 |
5 files changed, 203 insertions, 180 deletions
diff --git a/src/constants.h b/src/constants.h index 00061bd..1a5453c 100644 --- a/src/constants.h +++ b/src/constants.h | |||
| @@ -1,9 +1,13 @@ | |||
| 1 | #define _2p11 2048U | 1 | #define _bit_u8(i) (UINT8_C(1) << (uint8_t)(i)) |
| 2 | #define _2p12 4096U | 2 | #define _bit_u32(i) (UINT32_C(1) << (uint32_t)(i)) |
| 3 | #define _3p7 2187U | 3 | #define _bit_u64(i) (UINT64_C(1) << (uint64_t)(i)) |
| 4 | #define _3p8 6561U | 4 | |
| 5 | #define _12c4 495U | 5 | #define _2p11 INT64_C(2048) |
| 6 | #define _8c4 70U | 6 | #define _2p12 INT64_C(4096) |
| 7 | #define _3p7 INT64_C(2187) | ||
| 8 | #define _3p8 INT64_C(6561) | ||
| 9 | #define _12c4 INT64_C(495) | ||
| 10 | #define _8c4 INT64_C(70) | ||
| 7 | 11 | ||
| 8 | _static int64_t binomial[12][12] = { | 12 | _static int64_t binomial[12][12] = { |
| 9 | {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | 13 | {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, |
| @@ -20,111 +24,111 @@ _static int64_t binomial[12][12] = { | |||
| 20 | {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1}, | 24 | {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1}, |
| 21 | }; | 25 | }; |
| 22 | 26 | ||
| 23 | #define _move_U 0U | 27 | #define _move_U UINT8_C(0) |
| 24 | #define _move_U2 1U | 28 | #define _move_U2 UINT8_C(1) |
| 25 | #define _move_U3 2U | 29 | #define _move_U3 UINT8_C(2) |
| 26 | #define _move_D 3U | 30 | #define _move_D UINT8_C(3) |
| 27 | #define _move_D2 4U | 31 | #define _move_D2 UINT8_C(4) |
| 28 | #define _move_D3 5U | 32 | #define _move_D3 UINT8_C(5) |
| 29 | #define _move_R 6U | 33 | #define _move_R UINT8_C(6) |
| 30 | #define _move_R2 7U | 34 | #define _move_R2 UINT8_C(7) |
| 31 | #define _move_R3 8U | 35 | #define _move_R3 UINT8_C(8) |
| 32 | #define _move_L 9U | 36 | #define _move_L UINT8_C(9) |
| 33 | #define _move_L2 10U | 37 | #define _move_L2 UINT8_C(10) |
| 34 | #define _move_L3 11U | 38 | #define _move_L3 UINT8_C(11) |
| 35 | #define _move_F 12U | 39 | #define _move_F UINT8_C(12) |
| 36 | #define _move_F2 13U | 40 | #define _move_F2 UINT8_C(13) |
| 37 | #define _move_F3 14U | 41 | #define _move_F3 UINT8_C(14) |
| 38 | #define _move_B 15U | 42 | #define _move_B UINT8_C(15) |
| 39 | #define _move_B2 16U | 43 | #define _move_B2 UINT8_C(16) |
| 40 | #define _move_B3 17U | 44 | #define _move_B3 UINT8_C(17) |
| 41 | 45 | ||
| 42 | #define _trans_UFr 0 | 46 | #define _trans_UFr UINT8_C(0) |
| 43 | #define _trans_ULr 1 | 47 | #define _trans_ULr UINT8_C(1) |
| 44 | #define _trans_UBr 2 | 48 | #define _trans_UBr UINT8_C(2) |
| 45 | #define _trans_URr 3 | 49 | #define _trans_URr UINT8_C(3) |
| 46 | #define _trans_DFr 4 | 50 | #define _trans_DFr UINT8_C(4) |
| 47 | #define _trans_DLr 5 | 51 | #define _trans_DLr UINT8_C(5) |
| 48 | #define _trans_DBr 6 | 52 | #define _trans_DBr UINT8_C(6) |
| 49 | #define _trans_DRr 7 | 53 | #define _trans_DRr UINT8_C(7) |
| 50 | #define _trans_RUr 8 | 54 | #define _trans_RUr UINT8_C(8) |
| 51 | #define _trans_RFr 9 | 55 | #define _trans_RFr UINT8_C(9) |
| 52 | #define _trans_RDr 10 | 56 | #define _trans_RDr UINT8_C(10) |
| 53 | #define _trans_RBr 11 | 57 | #define _trans_RBr UINT8_C(11) |
| 54 | #define _trans_LUr 12 | 58 | #define _trans_LUr UINT8_C(12) |
| 55 | #define _trans_LFr 13 | 59 | #define _trans_LFr UINT8_C(13) |
| 56 | #define _trans_LDr 14 | 60 | #define _trans_LDr UINT8_C(14) |
| 57 | #define _trans_LBr 15 | 61 | #define _trans_LBr UINT8_C(15) |
| 58 | #define _trans_FUr 16 | 62 | #define _trans_FUr UINT8_C(16) |
| 59 | #define _trans_FRr 17 | 63 | #define _trans_FRr UINT8_C(17) |
| 60 | #define _trans_FDr 18 | 64 | #define _trans_FDr UINT8_C(18) |
| 61 | #define _trans_FLr 19 | 65 | #define _trans_FLr UINT8_C(19) |
| 62 | #define _trans_BUr 20 | 66 | #define _trans_BUr UINT8_C(20) |
| 63 | #define _trans_BRr 21 | 67 | #define _trans_BRr UINT8_C(21) |
| 64 | #define _trans_BDr 22 | 68 | #define _trans_BDr UINT8_C(22) |
| 65 | #define _trans_BLr 23 | 69 | #define _trans_BLr UINT8_C(23) |
| 66 | 70 | ||
| 67 | #define _trans_UFm 24 | 71 | #define _trans_UFm UINT8_C(24) |
| 68 | #define _trans_ULm 25 | 72 | #define _trans_ULm UINT8_C(25) |
| 69 | #define _trans_UBm 26 | 73 | #define _trans_UBm UINT8_C(26) |
| 70 | #define _trans_URm 27 | 74 | #define _trans_URm UINT8_C(27) |
| 71 | #define _trans_DFm 28 | 75 | #define _trans_DFm UINT8_C(28) |
| 72 | #define _trans_DLm 29 | 76 | #define _trans_DLm UINT8_C(29) |
| 73 | #define _trans_DBm 30 | 77 | #define _trans_DBm UINT8_C(30) |
| 74 | #define _trans_DRm 31 | 78 | #define _trans_DRm UINT8_C(31) |
| 75 | #define _trans_RUm 32 | 79 | #define _trans_RUm UINT8_C(32) |
| 76 | #define _trans_RFm 33 | 80 | #define _trans_RFm UINT8_C(33) |
| 77 | #define _trans_RDm 34 | 81 | #define _trans_RDm UINT8_C(34) |
| 78 | #define _trans_RBm 35 | 82 | #define _trans_RBm UINT8_C(35) |
| 79 | #define _trans_LUm 36 | 83 | #define _trans_LUm UINT8_C(36) |
| 80 | #define _trans_LFm 37 | 84 | #define _trans_LFm UINT8_C(37) |
| 81 | #define _trans_LDm 38 | 85 | #define _trans_LDm UINT8_C(38) |
| 82 | #define _trans_LBm 39 | 86 | #define _trans_LBm UINT8_C(39) |
| 83 | #define _trans_FUm 40 | 87 | #define _trans_FUm UINT8_C(40) |
| 84 | #define _trans_FRm 41 | 88 | #define _trans_FRm UINT8_C(41) |
| 85 | #define _trans_FDm 42 | 89 | #define _trans_FDm UINT8_C(42) |
| 86 | #define _trans_FLm 43 | 90 | #define _trans_FLm UINT8_C(43) |
| 87 | #define _trans_BUm 44 | 91 | #define _trans_BUm UINT8_C(44) |
| 88 | #define _trans_BRm 45 | 92 | #define _trans_BRm UINT8_C(45) |
| 89 | #define _trans_BDm 46 | 93 | #define _trans_BDm UINT8_C(46) |
| 90 | #define _trans_BLm 47 | 94 | #define _trans_BLm UINT8_C(47) |
| 91 | 95 | ||
| 92 | #define _c_ufr 0U | 96 | #define _c_ufr UINT8_C(0) |
| 93 | #define _c_ubl 1U | 97 | #define _c_ubl UINT8_C(1) |
| 94 | #define _c_dfl 2U | 98 | #define _c_dfl UINT8_C(2) |
| 95 | #define _c_dbr 3U | 99 | #define _c_dbr UINT8_C(3) |
| 96 | #define _c_ufl 4U | 100 | #define _c_ufl UINT8_C(4) |
| 97 | #define _c_ubr 5U | 101 | #define _c_ubr UINT8_C(5) |
| 98 | #define _c_dfr 6U | 102 | #define _c_dfr UINT8_C(6) |
| 99 | #define _c_dbl 7U | 103 | #define _c_dbl UINT8_C(7) |
| 100 | 104 | ||
| 101 | #define _e_uf 0U | 105 | #define _e_uf UINT8_C(0) |
| 102 | #define _e_ub 1U | 106 | #define _e_ub UINT8_C(1) |
| 103 | #define _e_db 2U | 107 | #define _e_db UINT8_C(2) |
| 104 | #define _e_df 3U | 108 | #define _e_df UINT8_C(3) |
| 105 | #define _e_ur 4U | 109 | #define _e_ur UINT8_C(4) |
| 106 | #define _e_ul 5U | 110 | #define _e_ul UINT8_C(5) |
| 107 | #define _e_dl 6U | 111 | #define _e_dl UINT8_C(6) |
| 108 | #define _e_dr 7U | 112 | #define _e_dr UINT8_C(7) |
| 109 | #define _e_fr 8U | 113 | #define _e_fr UINT8_C(8) |
| 110 | #define _e_fl 9U | 114 | #define _e_fl UINT8_C(9) |
| 111 | #define _e_bl 10U | 115 | #define _e_bl UINT8_C(10) |
| 112 | #define _e_br 11U | 116 | #define _e_br UINT8_C(11) |
| 113 | 117 | ||
| 114 | #define _eoshift 4U | 118 | #define _eoshift UINT8_C(4) |
| 115 | #define _coshift 5U | 119 | #define _coshift UINT8_C(5) |
| 116 | 120 | ||
| 117 | #define _pbits 0xFU | 121 | #define _pbits UINT8_C(0xF) |
| 118 | #define _esepbit1 0x4U | 122 | #define _esepbit1 UINT8_C(0x4) |
| 119 | #define _esepbit2 0x8U | 123 | #define _esepbit2 UINT8_C(0x8) |
| 120 | #define _csepbit 0x4U | 124 | #define _csepbit UINT8_C(0x4) |
| 121 | #define _eobit 0x10U | 125 | #define _eobit UINT8_C(0x10) |
| 122 | #define _cobits 0xF0U | 126 | #define _cobits UINT8_C(0xF0) |
| 123 | #define _cobits2 0x60U | 127 | #define _cobits2 UINT8_C(0x60) |
| 124 | #define _ctwist_cw 0x20U | 128 | #define _ctwist_cw UINT8_C(0x20) |
| 125 | #define _ctwist_ccw 0x40U | 129 | #define _ctwist_ccw UINT8_C(0x40) |
| 126 | #define _eflip 0x10U | 130 | #define _eflip UINT8_C(0x10) |
| 127 | #define _error 0xFFU | 131 | #define _error UINT8_C(0xFF) |
| 128 | 132 | ||
| 129 | _static cube_t zero = { .corner = {0}, .edge = {0} }; | 133 | _static cube_t zero = { .corner = {0}, .edge = {0} }; |
| 130 | _static cube_t solved = { | 134 | _static cube_t solved = { |
diff --git a/src/cube_avx2.h b/src/cube_avx2.h index ad4aadb..233afed 100644 --- a/src/cube_avx2.h +++ b/src/cube_avx2.h | |||
| @@ -1,10 +1,12 @@ | |||
| 1 | typedef __m256i cube_fast_t; | 1 | typedef __m256i cube_fast_t; |
| 2 | 2 | ||
| 3 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060) | 3 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x6060606060606060)) |
| 4 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020) | 4 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x2020202020202020)) |
| 5 | #define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707) | 5 | #define _cp_avx2 _mm256_set_epi64x(0, 0, 0, INT64_C(0x0707070707070707)) |
| 6 | #define _ep_avx2 _mm256_set_epi64x(0x0F0F0F0F, 0x0F0F0F0F0F0F0F0F, 0, 0) | 6 | #define _ep_avx2 \ |
| 7 | #define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0) | 7 | _mm256_set_epi64x(INT64_C(0x0F0F0F0F), INT64_C(0x0F0F0F0F0F0F0F0F), 0, 0) |
| 8 | #define _eo_avx2 \ | ||
| 9 | _mm256_set_epi64x(INT64_C(0x10101010), INT64_C(0x1010101010101010), 0, 0) | ||
| 8 | 10 | ||
| 9 | _static_inline cube_fast_t fastcube( | 11 | _static_inline cube_fast_t fastcube( |
| 10 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | 12 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, |
| @@ -194,9 +196,9 @@ coord_fast_co(cube_fast_t c) | |||
| 194 | co = _mm256_and_si256(c, _co2_avx2); | 196 | co = _mm256_and_si256(c, _co2_avx2); |
| 195 | _mm256_storeu_si256((__m256i *)mem, co); | 197 | _mm256_storeu_si256((__m256i *)mem, co); |
| 196 | 198 | ||
| 197 | mem[0] >>= 5L; | 199 | mem[0] >>= 5; |
| 198 | for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8L, p *= 3) | 200 | for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8, p *= 3) |
| 199 | ret += (mem[0] & 3L) * p; | 201 | ret += (mem[0] & 3) * p; |
| 200 | 202 | ||
| 201 | return ret; | 203 | return ret; |
| 202 | } | 204 | } |
| @@ -242,14 +244,14 @@ coord_fast_esep(cube_fast_t c) | |||
| 242 | ep = _mm256_and_si256(c, _ep_avx2); | 244 | ep = _mm256_and_si256(c, _ep_avx2); |
| 243 | _mm256_storeu_si256((__m256i *)mem, ep); | 245 | _mm256_storeu_si256((__m256i *)mem, ep); |
| 244 | 246 | ||
| 245 | mem[3] <<= 8L; | 247 | mem[3] <<= 8; |
| 246 | ret1 = ret2 = 0; | 248 | ret1 = ret2 = 0; |
| 247 | k = l = 4; | 249 | k = l = 4; |
| 248 | for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8L) { | 250 | for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8) { |
| 249 | e = mem[i/8 + 2]; | 251 | e = mem[i/8 + 2]; |
| 250 | 252 | ||
| 251 | bit1 = (e & _esepbit1) >> 2L; | 253 | bit1 = (e & _esepbit1) >> 2; |
| 252 | bit2 = (e & _esepbit2) >> 3L; | 254 | bit2 = (e & _esepbit2) >> 3; |
| 253 | is1 = (1 - bit2) * bit1; | 255 | is1 = (1 - bit2) * bit1; |
| 254 | 256 | ||
| 255 | ret1 += bit2 * binomial[11-i][k]; | 257 | ret1 += bit2 * binomial[11-i][k]; |
| @@ -305,8 +307,8 @@ _static_inline cube_fast_t | |||
| 305 | invcoord_fast_esep(int64_t esep) | 307 | invcoord_fast_esep(int64_t esep) |
| 306 | { | 308 | { |
| 307 | cube_fast_t eee, ret; | 309 | cube_fast_t eee, ret; |
| 308 | int64_t i, j, jj, k, l, s, v, w, is1, set1, set2; | 310 | int64_t bit1, bit2, i, j, jj, k, l, s, v, w, is1, set1, set2; |
| 309 | uint8_t bit2, bit1, mem[32]; | 311 | uint8_t mem[32]; |
| 310 | uint8_t slice[3] = {0}; | 312 | uint8_t slice[3] = {0}; |
| 311 | 313 | ||
| 312 | set1 = esep % 70; | 314 | set1 = esep % 70; |
| @@ -327,7 +329,7 @@ invcoord_fast_esep(int64_t esep) | |||
| 327 | j += (1-bit2); | 329 | j += (1-bit2); |
| 328 | s = 2*bit2 + (1-bit2)*bit1; | 330 | s = 2*bit2 + (1-bit2)*bit1; |
| 329 | 331 | ||
| 330 | mem[i+16] = (slice[s]++) | (s << 2); | 332 | mem[i+16] = (slice[s]++) | (uint8_t)(s << 2); |
| 331 | } | 333 | } |
| 332 | 334 | ||
| 333 | ret = cubetofast(solved); | 335 | ret = cubetofast(solved); |
diff --git a/src/cube_portable.h b/src/cube_portable.h index d62661a..2999d8a 100644 --- a/src/cube_portable.h +++ b/src/cube_portable.h | |||
| @@ -143,7 +143,7 @@ compose_corners_inplace(cube_fast_t c1, cube_fast_t c2, cube_fast_t *ret) | |||
| 143 | p = piece2 & _pbits; | 143 | p = piece2 & _pbits; |
| 144 | piece1 = c1.corner[p]; | 144 | piece1 = c1.corner[p]; |
| 145 | aux = (piece2 & _cobits) + (piece1 & _cobits); | 145 | aux = (piece2 & _cobits) + (piece1 & _cobits); |
| 146 | auy = (aux + _ctwist_cw) >> 2U; | 146 | auy = (aux + _ctwist_cw) >> 2; |
| 147 | orien = (aux + auy) & _cobits2; | 147 | orien = (aux + auy) & _cobits2; |
| 148 | ret->corner[i] = (piece1 & _pbits) | orien; | 148 | ret->corner[i] = (piece1 & _pbits) | orien; |
| 149 | } | 149 | } |
| @@ -206,7 +206,7 @@ coord_fast_csep(cube_fast_t c) | |||
| 206 | int64_t ret; | 206 | int64_t ret; |
| 207 | 207 | ||
| 208 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2) | 208 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2) |
| 209 | ret += p * ((c.corner[i] & _csepbit) >> 2U); | 209 | ret += p * ((c.corner[i] & _csepbit) >> 2); |
| 210 | 210 | ||
| 211 | return ret; | 211 | return ret; |
| 212 | } | 212 | } |
| @@ -249,8 +249,8 @@ coord_fast_esep(cube_fast_t c) | |||
| 249 | } | 249 | } |
| 250 | */ | 250 | */ |
| 251 | 251 | ||
| 252 | bit1 = (c.edge[i] & _esepbit1) >> 2U; | 252 | bit1 = (c.edge[i] & _esepbit1) >> 2; |
| 253 | bit2 = (c.edge[i] & _esepbit2) >> 3U; | 253 | bit2 = (c.edge[i] & _esepbit2) >> 3; |
| 254 | is1 = (1 - bit2) * bit1; | 254 | is1 = (1 - bit2) * bit1; |
| 255 | 255 | ||
| 256 | ret1 += bit2 * binomial[11-i][k]; | 256 | ret1 += bit2 * binomial[11-i][k]; |
| @@ -280,22 +280,21 @@ copy_edges_fast(cube_fast_t *dest, cube_fast_t src) | |||
| 280 | _static_inline void | 280 | _static_inline void |
| 281 | set_eo_fast(cube_fast_t *cube, int64_t eo) | 281 | set_eo_fast(cube_fast_t *cube, int64_t eo) |
| 282 | { | 282 | { |
| 283 | int i, sum, flip; | 283 | uint8_t i, sum, flip; |
| 284 | 284 | ||
| 285 | for (sum = 0, i = 1; i < 12; i++, eo >>= 1) { | 285 | for (sum = 0, i = 1; i < 12; i++, eo >>= 1) { |
| 286 | flip = eo % 2; | 286 | flip = eo % 2; |
| 287 | sum += flip; | 287 | sum += flip; |
| 288 | cube->edge[i] = (cube->edge[i] & ~_eobit) | (_eobit * flip); | 288 | cube->edge[i] = (cube->edge[i] & ~_eobit) | (_eobit * flip); |
| 289 | } | 289 | } |
| 290 | cube->edge[0] = (cube->edge[0] & ~_eobit) | (_eobit * (sum%2)); | 290 | cube->edge[0] = (cube->edge[0] & ~_eobit) | (_eobit * (sum % 2)); |
| 291 | } | 291 | } |
| 292 | 292 | ||
| 293 | _static_inline cube_fast_t | 293 | _static_inline cube_fast_t |
| 294 | invcoord_fast_esep(int64_t esep) | 294 | invcoord_fast_esep(int64_t esep) |
| 295 | { | 295 | { |
| 296 | cube_fast_t ret; | 296 | cube_fast_t ret; |
| 297 | int64_t i, j, jj, k, l, s, v, w, is1, set1, set2; | 297 | int64_t bit1, bit2, i, j, jj, k, l, s, v, w, is1, set1, set2; |
| 298 | uint8_t bit2, bit1; | ||
| 299 | uint8_t slice[3] = {0}; | 298 | uint8_t slice[3] = {0}; |
| 300 | 299 | ||
| 301 | ret = cubetofast(solved); | 300 | ret = cubetofast(solved); |
| @@ -317,7 +316,7 @@ invcoord_fast_esep(int64_t esep) | |||
| 317 | j += (1-bit2); | 316 | j += (1-bit2); |
| 318 | s = 2*bit2 + (1-bit2)*bit1; | 317 | s = 2*bit2 + (1-bit2)*bit1; |
| 319 | 318 | ||
| 320 | ret.edge[i] = (slice[s]++) | (s << 2); | 319 | ret.edge[i] = (slice[s]++) | (uint8_t)(s << 2); |
| 321 | } | 320 | } |
| 322 | 321 | ||
| 323 | return ret; | 322 | return ret; |
diff --git a/src/cube_routines.h b/src/cube_routines.h index 1585e67..fb19355 100644 --- a/src/cube_routines.h +++ b/src/cube_routines.h | |||
| @@ -422,8 +422,9 @@ _static int | |||
| 422 | writepiece_LST(uint8_t piece, char *buf) | 422 | writepiece_LST(uint8_t piece, char *buf) |
| 423 | { | 423 | { |
| 424 | char digits[3]; | 424 | char digits[3]; |
| 425 | int i, len = 0; | 425 | int i, len; |
| 426 | 426 | ||
| 427 | len = 0; | ||
| 427 | while (piece != 0) { | 428 | while (piece != 0) { |
| 428 | digits[len++] = (piece % 10) + '0'; | 429 | digits[len++] = (piece % 10) + '0'; |
| 429 | piece /= 10; | 430 | piece /= 10; |
| @@ -473,7 +474,8 @@ writecube_H48(cube_t cube, char *buf) | |||
| 473 | _static void | 474 | _static void |
| 474 | writecube_LST(cube_t cube, char *buf) | 475 | writecube_LST(cube_t cube, char *buf) |
| 475 | { | 476 | { |
| 476 | int i, ptr; | 477 | int i; |
| 478 | size_t ptr; | ||
| 477 | uint8_t piece; | 479 | uint8_t piece; |
| 478 | 480 | ||
| 479 | ptr = 0; | 481 | ptr = 0; |
diff --git a/src/solve_h48.h b/src/solve_h48.h index ecb0863..abf7a86 100644 --- a/src/solve_h48.h +++ b/src/solve_h48.h | |||
| @@ -1,18 +1,23 @@ | |||
| 1 | #define COCSEP_CLASSES 3393U | 1 | #define COCSEP_CLASSES ((size_t)3393) |
| 2 | #define COCSEP_TABLESIZE (_3p7 << 7ULL) | 2 | #define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7) |
| 3 | #define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + 7ULL) / 8ULL) | 3 | #define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8) |
| 4 | #define COCSEP_FULLSIZE (4*(COCSEP_TABLESIZE + 12)) | 4 | #define COCSEP_FULLSIZE ((size_t)4 * (COCSEP_TABLESIZE + (size_t)12)) |
| 5 | 5 | ||
| 6 | #define ESEP_MAX(h) ((COCSEP_CLASSES * _12c4 * _8c4) << (h)) | 6 | #define ESEP_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4) |
| 7 | #define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / (8U / (k))) | 7 | #define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h)) |
| 8 | #define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k))) | ||
| 8 | 9 | ||
| 9 | #define H48_ESIZE(h) ((_12c4 * _8c4) << (h)) | 10 | #define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16)) |
| 11 | #define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16)) | ||
| 12 | #define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8)) | ||
| 13 | #define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8)) | ||
| 14 | #define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h)) | ||
| 10 | 15 | ||
| 11 | #define _esep_ind(i) (i / 8ULL) | 16 | #define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8)) |
| 12 | #define _esep_shift(i) (4ULL * (i % 8ULL)) | 17 | #define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8))) |
| 13 | #define _esep_mask(i) (((1ULL << 4ULL) - 1ULL) << _esep_shift(i)) | 18 | #define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i)) |
| 14 | #define _visited_ind(i) (i / 8ULL) | 19 | #define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8)) |
| 15 | #define _visited_mask(i) (1ULL << (i % 8ULL)) | 20 | #define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8))) |
| 16 | 21 | ||
| 17 | typedef struct { | 22 | typedef struct { |
| 18 | cube_fast_t cube; | 23 | cube_fast_t cube; |
| @@ -59,8 +64,8 @@ coord_h48(cube_fast_t c, const uint32_t *cocsepdata, uint8_t h) | |||
| 59 | 64 | ||
| 60 | cocsep = coord_fast_cocsep(c); | 65 | cocsep = coord_fast_cocsep(c); |
| 61 | data = cocsepdata[cocsep]; | 66 | data = cocsepdata[cocsep]; |
| 62 | coclass = (data & (0xFFFFU << 16U)) >> 16U; | 67 | coclass = (int64_t)COCLASS(data); |
| 63 | ttrep = (data & (0xFFU << 8U)) >> 8U; | 68 | ttrep = (int64_t)TTREP(data); |
| 64 | 69 | ||
| 65 | return coord_h48_edges(c, coclass, ttrep, h); | 70 | return coord_h48_edges(c, coclass, ttrep, h); |
| 66 | } | 71 | } |
| @@ -69,13 +74,14 @@ _static_inline int64_t | |||
| 69 | coord_h48_edges(cube_fast_t c, int64_t coclass, uint8_t t, uint8_t h) | 74 | coord_h48_edges(cube_fast_t c, int64_t coclass, uint8_t t, uint8_t h) |
| 70 | { | 75 | { |
| 71 | cube_fast_t d; | 76 | cube_fast_t d; |
| 72 | int64_t esep, eo; | 77 | int64_t esep, eo, edges; |
| 73 | 78 | ||
| 74 | d = transform_edges(c, t); | 79 | d = transform_edges(c, t); |
| 75 | esep = coord_fast_esep(d); | 80 | esep = coord_fast_esep(d); |
| 76 | eo = coord_fast_eo(d); | 81 | eo = coord_fast_eo(d); |
| 82 | edges = (esep << (int64_t)h) + (eo >> (11 - (int64_t)h)); | ||
| 77 | 83 | ||
| 78 | return (coclass * H48_ESIZE(h)) + (esep << h) + (eo >> (11-h)); | 84 | return coclass * H48_ESIZE(h) + edges; |
| 79 | } | 85 | } |
| 80 | 86 | ||
| 81 | /* | 87 | /* |
| @@ -85,15 +91,17 @@ returned cube is a transformed cube of one that gives the correct value. | |||
| 85 | */ | 91 | */ |
| 86 | _static_inline cube_fast_t | 92 | _static_inline cube_fast_t |
| 87 | invcoord_h48(int64_t i, const cube_fast_t *crep, uint8_t h) { | 93 | invcoord_h48(int64_t i, const cube_fast_t *crep, uint8_t h) { |
| 88 | cube_fast_t ret; int64_t coclass, ee, esep, eo; | 94 | cube_fast_t ret; |
| 95 | int64_t hh, coclass, ee, esep, eo; | ||
| 89 | 96 | ||
| 90 | DBG_ASSERT(h <= 11, cubetofast(zero), | 97 | DBG_ASSERT(h <= 11, cubetofast(zero), |
| 91 | "invcoord_h48: h must be between 0 and 11\n"); | 98 | "invcoord_h48: h must be between 0 and 11\n"); |
| 92 | 99 | ||
| 100 | hh = (int64_t)h; | ||
| 93 | coclass = i / H48_ESIZE(h); | 101 | coclass = i / H48_ESIZE(h); |
| 94 | ee = i % H48_ESIZE(h); | 102 | ee = i % H48_ESIZE(h); |
| 95 | esep = ee >> h; | 103 | esep = ee >> hh; |
| 96 | eo = (ee & ((1<<h)-1)) << (11-h); | 104 | eo = (ee & ((1 << hh) - 1)) << (11 - hh); |
| 97 | 105 | ||
| 98 | ret = invcoord_fast_esep(esep); | 106 | ret = invcoord_fast_esep(esep); |
| 99 | copy_corners_fast(&ret, crep[coclass]); | 107 | copy_corners_fast(&ret, crep[coclass]); |
| @@ -123,7 +131,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep) | |||
| 123 | 131 | ||
| 124 | buf32 = (uint32_t *)buf; | 132 | buf32 = (uint32_t *)buf; |
| 125 | info = buf32 + COCSEP_TABLESIZE; | 133 | info = buf32 + COCSEP_TABLESIZE; |
| 126 | memset(buf32, 0xFFU, sizeof(uint32_t) * COCSEP_TABLESIZE); | 134 | memset(buf32, 0xFF, sizeof(uint32_t) * COCSEP_TABLESIZE); |
| 127 | memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); | 135 | memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); |
| 128 | 136 | ||
| 129 | arg = (dfsarg_cocsep_t) { | 137 | arg = (dfsarg_cocsep_t) { |
| @@ -145,10 +153,10 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep) | |||
| 145 | } | 153 | } |
| 146 | 154 | ||
| 147 | info[0] = (uint32_t)n; | 155 | info[0] = (uint32_t)n; |
| 148 | info[1] = 9U; /* Known max pruning value */ | 156 | info[1] = 9; /* Known max pruning value */ |
| 149 | DBG_ASSERT(n == COCSEP_CLASSES, 0, | 157 | DBG_ASSERT(n == COCSEP_CLASSES, 0, |
| 150 | "cocsep: computed %" PRIu16 " symmetry classes, " | 158 | "cocsep: computed %" PRIu16 " symmetry classes, " |
| 151 | "expected %" PRIu16 "\n", n, COCSEP_CLASSES); | 159 | "expected %zu\n", n, COCSEP_CLASSES); |
| 152 | 160 | ||
| 153 | DBG_LOG("cocsep data computed\n"); | 161 | DBG_LOG("cocsep data computed\n"); |
| 154 | DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]); | 162 | DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]); |
| @@ -163,33 +171,37 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep) | |||
| 163 | _static uint32_t | 171 | _static uint32_t |
| 164 | gendata_cocsep_dfs(dfsarg_cocsep_t *arg) | 172 | gendata_cocsep_dfs(dfsarg_cocsep_t *arg) |
| 165 | { | 173 | { |
| 166 | uint8_t m, tinv, olddepth; | 174 | uint8_t m, tinv; |
| 167 | uint32_t cc; | 175 | uint32_t cc, class, ttrep, depth, olddepth; |
| 168 | uint64_t t, is; | 176 | uint64_t t, is; |
| 169 | int64_t i, ii; | 177 | int64_t i, j; |
| 170 | cube_fast_t d; | 178 | cube_fast_t d; |
| 171 | dfsarg_cocsep_t nextarg; | 179 | dfsarg_cocsep_t nextarg; |
| 172 | 180 | ||
| 173 | i = coord_fast_cocsep(arg->cube); | 181 | i = coord_fast_cocsep(arg->cube); |
| 174 | olddepth = (uint8_t)(arg->buf32[i] & 0xFFU); | 182 | olddepth = (uint8_t)(arg->buf32[i] & 0xFF); |
| 175 | if (olddepth < arg->depth || get_visited(arg->visited, i)) | 183 | if (olddepth < arg->depth || get_visited(arg->visited, i)) |
| 176 | return 0; | 184 | return 0; |
| 177 | set_visited(arg->visited, i); | 185 | set_visited(arg->visited, i); |
| 178 | 186 | ||
| 179 | if (arg->depth == arg->maxdepth) { | 187 | if (arg->depth == arg->maxdepth) { |
| 180 | if ((arg->buf32[i] & 0xFFU) != 0xFFU) | 188 | if ((arg->buf32[i] & 0xFF) != 0xFF) |
| 181 | return 0; | 189 | return 0; |
| 182 | 190 | ||
| 183 | for (t = 0, cc = 0; t < 48; t++) { | 191 | for (t = 0, cc = 0; t < 48; t++) { |
| 184 | d = transform_corners(arg->cube, t); | 192 | d = transform_corners(arg->cube, t); |
| 185 | ii = coord_fast_cocsep(d); | 193 | j = coord_fast_cocsep(d); |
| 186 | is = (i == ii); | 194 | is = (i == j); |
| 187 | arg->selfsim[*arg->n] |= is << t; | 195 | arg->selfsim[*arg->n] |= is << t; |
| 188 | set_visited(arg->visited, ii); | 196 | set_visited(arg->visited, j); |
| 189 | tinv = inverse_trans(t); | 197 | tinv = inverse_trans(t); |
| 190 | cc += (arg->buf32[ii] & 0xFFU) == 0xFFU; | 198 | olddepth = (uint8_t)(arg->buf32[j] & 0xFF); |
| 191 | arg->buf32[ii] = | 199 | cc += olddepth == 0xFF; |
| 192 | (*arg->n << 16U) | (tinv << 8U) | arg->depth; | 200 | |
| 201 | class = (uint32_t)(*arg->n) << 16; | ||
| 202 | ttrep = (uint32_t)tinv << 8; | ||
| 203 | depth = (uint32_t)arg->depth; | ||
| 204 | arg->buf32[j] = class | ttrep | depth; | ||
| 193 | } | 205 | } |
| 194 | arg->rep[*arg->n] = arg->cube; | 206 | arg->rep[*arg->n] = arg->cube; |
| 195 | (*arg->n)++; | 207 | (*arg->n)++; |
| @@ -217,16 +229,17 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth) | |||
| 217 | const int k = 4; /* TODO: other cases? */ | 229 | const int k = 4; /* TODO: other cases? */ |
| 218 | uint32_t j, *buf32, *info, *cocsepdata; | 230 | uint32_t j, *buf32, *info, *cocsepdata; |
| 219 | bfsarg_esep_t arg; | 231 | bfsarg_esep_t arg; |
| 220 | int64_t sc, cc, tot; | 232 | int64_t sc, cc, tot, esep_max; |
| 221 | uint64_t selfsim[COCSEP_CLASSES]; | 233 | uint64_t selfsim[COCSEP_CLASSES]; |
| 222 | cube_fast_t crep[COCSEP_CLASSES]; | 234 | cube_fast_t crep[COCSEP_CLASSES]; |
| 223 | size_t cocsepsize; | 235 | size_t cocsepsize, infosize; |
| 224 | 236 | ||
| 237 | esep_max = (int64_t)ESEP_MAX(h); | ||
| 225 | cocsepsize = gendata_cocsep(buf, selfsim, crep); | 238 | cocsepsize = gendata_cocsep(buf, selfsim, crep); |
| 226 | cocsepdata = (uint32_t *)buf; | 239 | cocsepdata = (uint32_t *)buf; |
| 227 | buf32 = cocsepdata + cocsepsize/4; | 240 | buf32 = cocsepdata + cocsepsize / 4; |
| 228 | info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t)); | 241 | info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t)); |
| 229 | memset(buf32, 0xFFU, ESEP_TABLESIZE(h, k)); | 242 | memset(buf32, 0xFF, ESEP_TABLESIZE(h, k)); |
| 230 | 243 | ||
| 231 | sc = coord_h48(cubetofast(solved), cocsepdata, h); | 244 | sc = coord_h48(cubetofast(solved), cocsepdata, h); |
| 232 | set_esep_pval(buf32, sc, 0); | 245 | set_esep_pval(buf32, sc, 0); |
| @@ -240,7 +253,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth) | |||
| 240 | }; | 253 | }; |
| 241 | for ( | 254 | for ( |
| 242 | tot = 1, arg.depth = 1, cc = 0; | 255 | tot = 1, arg.depth = 1, cc = 0; |
| 243 | tot < ESEP_MAX(h) && arg.depth <= maxdepth; | 256 | tot < esep_max && arg.depth <= maxdepth; |
| 244 | arg.depth++ | 257 | arg.depth++ |
| 245 | ) { | 258 | ) { |
| 246 | DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth); | 259 | DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth); |
| @@ -251,6 +264,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth) | |||
| 251 | } | 264 | } |
| 252 | 265 | ||
| 253 | info[0] = arg.depth-1; | 266 | info[0] = arg.depth-1; |
| 267 | infosize = 4 * (size_t)(info[0] + 2); | ||
| 254 | 268 | ||
| 255 | DBG_LOG("h48 pruning table computed\n"); | 269 | DBG_LOG("h48 pruning table computed\n"); |
| 256 | DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[0]); | 270 | DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[0]); |
| @@ -258,7 +272,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth) | |||
| 258 | for (j = 0; j <= info[0]; j++) | 272 | for (j = 0; j <= info[0]; j++) |
| 259 | DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]); | 273 | DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]); |
| 260 | 274 | ||
| 261 | return COCSEP_FULLSIZE + ESEP_TABLESIZE(h, k) + 4*(info[0]+2); | 275 | return cocsepsize + ESEP_TABLESIZE(h, k) + infosize; |
| 262 | } | 276 | } |
| 263 | 277 | ||
| 264 | _static uint64_t | 278 | _static uint64_t |
| @@ -266,10 +280,12 @@ gendata_esep_bfs(bfsarg_esep_t *arg) | |||
| 266 | { | 280 | { |
| 267 | uint8_t c, m, x; | 281 | uint8_t c, m, x; |
| 268 | uint32_t cc; | 282 | uint32_t cc; |
| 269 | uint64_t i, j, k, t, cocsep_coord, sim; | 283 | int64_t i, j, k, t, cocsep_coord, sim, esep_max; |
| 270 | cube_fast_t cube, moved, transd; | 284 | cube_fast_t cube, moved, transd; |
| 271 | 285 | ||
| 272 | for (i = 0, cc = 0; i < ESEP_MAX(arg->h); i++) { | 286 | esep_max = (uint64_t)ESEP_MAX(arg->h); |
| 287 | |||
| 288 | for (i = 0, cc = 0; i < esep_max; i++) { | ||
| 273 | c = get_esep_pval(arg->buf32, i); | 289 | c = get_esep_pval(arg->buf32, i); |
| 274 | if (c != arg->depth - 1) | 290 | if (c != arg->depth - 1) |
| 275 | continue; | 291 | continue; |
| @@ -288,9 +304,9 @@ gendata_esep_bfs(bfsarg_esep_t *arg) | |||
| 288 | set_esep_pval(arg->buf32, j, arg->depth); | 304 | set_esep_pval(arg->buf32, j, arg->depth); |
| 289 | cc += x != arg->depth; | 305 | cc += x != arg->depth; |
| 290 | cocsep_coord = j / H48_ESIZE(arg->h); | 306 | cocsep_coord = j / H48_ESIZE(arg->h); |
| 291 | sim = arg->selfsim[cocsep_coord] >> 1ULL; | 307 | sim = arg->selfsim[cocsep_coord] >> 1; |
| 292 | for (t = 1; t < 48 && sim; t++, sim >>= 1ULL) { | 308 | for (t = 1; t < 48 && sim; t++, sim >>= 1) { |
| 293 | if (!(sim & 1ULL)) | 309 | if (!(sim & 1)) |
| 294 | continue; | 310 | continue; |
| 295 | transd = transform(moved, t); | 311 | transd = transform(moved, t); |
| 296 | k = coord_h48(transd, arg->cocsepdata, arg->h); | 312 | k = coord_h48(transd, arg->cocsepdata, arg->h); |
| @@ -308,23 +324,23 @@ gendata_esep_bfs(bfsarg_esep_t *arg) | |||
| 308 | 324 | ||
| 309 | _static_inline bool get_visited(const uint8_t *a, int64_t i) | 325 | _static_inline bool get_visited(const uint8_t *a, int64_t i) |
| 310 | { | 326 | { |
| 311 | return a[_visited_ind(i)] & _visited_mask(i); | 327 | return a[VISITED_IND(i)] & VISITED_MASK(i); |
| 312 | } | 328 | } |
| 313 | 329 | ||
| 314 | _static_inline void set_visited(uint8_t *a, int64_t i) | 330 | _static_inline void set_visited(uint8_t *a, int64_t i) |
| 315 | { | 331 | { |
| 316 | a[_visited_ind(i)] |= _visited_mask(i); | 332 | a[VISITED_IND(i)] |= VISITED_MASK(i); |
| 317 | } | 333 | } |
| 318 | 334 | ||
| 319 | _static_inline uint8_t | 335 | _static_inline uint8_t |
| 320 | get_esep_pval(const uint32_t *buf32, int64_t i) | 336 | get_esep_pval(const uint32_t *buf32, int64_t i) |
| 321 | { | 337 | { |
| 322 | return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i); | 338 | return (buf32[ESEP_IND(i)] & ESEP_MASK(i)) >> ESEP_SHIFT(i); |
| 323 | } | 339 | } |
| 324 | 340 | ||
| 325 | _static_inline void | 341 | _static_inline void |
| 326 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) | 342 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) |
| 327 | { | 343 | { |
| 328 | buf32[_esep_ind(i)] = | 344 | buf32[ESEP_IND(i)] = |
| 329 | (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i)); | 345 | (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i)); |
| 330 | } | 346 | } |
