diff options
| author | Sebastiano Tronto <sebastiano@tronto.net> | 2024-05-10 09:10:12 +0200 |
|---|---|---|
| committer | Sebastiano Tronto <sebastiano@tronto.net> | 2024-05-10 09:10:12 +0200 |
| commit | a660922d738b78b11fc78207daabea031058f710 (patch) | |
| tree | db46bd95bffeb330cea6066c77f2709f96c033aa | |
| parent | 75966319fd5891c2c1bd35b1f7c93eab172fd28e (diff) | |
| download | nissy-core-a660922d738b78b11fc78207daabea031058f710.tar.gz nissy-core-a660922d738b78b11fc78207daabea031058f710.zip | |
Split into .h files
Diffstat (limited to '')
| -rw-r--r-- | src/constants.h | 530 | ||||
| -rw-r--r-- | src/cube.c | 2371 | ||||
| -rw-r--r-- | src/cube_avx2.h | 229 | ||||
| -rw-r--r-- | src/cube_neon.h | 6 | ||||
| -rw-r--r-- | src/cube_portable.h | 224 | ||||
| -rw-r--r-- | src/cube_routines.h | 730 | ||||
| -rw-r--r-- | src/moves.h | 47 | ||||
| -rw-r--r-- | src/solve_generic.h | 259 | ||||
| -rw-r--r-- | src/solve_h48.h | 266 |
9 files changed, 2300 insertions, 2362 deletions
diff --git a/src/constants.h b/src/constants.h new file mode 100644 index 0000000..df444b1 --- /dev/null +++ b/src/constants.h | |||
| @@ -0,0 +1,530 @@ | |||
| 1 | #define _2p11 2048U | ||
| 2 | #define _2p12 4096U | ||
| 3 | #define _3p7 2187U | ||
| 4 | #define _3p8 6561U | ||
| 5 | #define _12c4 495U | ||
| 6 | #define _8c4 70U | ||
| 7 | |||
| 8 | #define COCSEP_CLASSES 3393U | ||
| 9 | |||
| 10 | _static int64_t binomial[12][12] = { | ||
| 11 | {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 12 | {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 13 | {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 14 | {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 15 | {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0}, | ||
| 16 | {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0}, | ||
| 17 | {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0}, | ||
| 18 | {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0}, | ||
| 19 | {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0}, | ||
| 20 | {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0}, | ||
| 21 | {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0}, | ||
| 22 | {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1}, | ||
| 23 | }; | ||
| 24 | |||
| 25 | #define _move_U 0U | ||
| 26 | #define _move_U2 1U | ||
| 27 | #define _move_U3 2U | ||
| 28 | #define _move_D 3U | ||
| 29 | #define _move_D2 4U | ||
| 30 | #define _move_D3 5U | ||
| 31 | #define _move_R 6U | ||
| 32 | #define _move_R2 7U | ||
| 33 | #define _move_R3 8U | ||
| 34 | #define _move_L 9U | ||
| 35 | #define _move_L2 10U | ||
| 36 | #define _move_L3 11U | ||
| 37 | #define _move_F 12U | ||
| 38 | #define _move_F2 13U | ||
| 39 | #define _move_F3 14U | ||
| 40 | #define _move_B 15U | ||
| 41 | #define _move_B2 16U | ||
| 42 | #define _move_B3 17U | ||
| 43 | |||
| 44 | #define _trans_UFr 0 | ||
| 45 | #define _trans_ULr 1 | ||
| 46 | #define _trans_UBr 2 | ||
| 47 | #define _trans_URr 3 | ||
| 48 | #define _trans_DFr 4 | ||
| 49 | #define _trans_DLr 5 | ||
| 50 | #define _trans_DBr 6 | ||
| 51 | #define _trans_DRr 7 | ||
| 52 | #define _trans_RUr 8 | ||
| 53 | #define _trans_RFr 9 | ||
| 54 | #define _trans_RDr 10 | ||
| 55 | #define _trans_RBr 11 | ||
| 56 | #define _trans_LUr 12 | ||
| 57 | #define _trans_LFr 13 | ||
| 58 | #define _trans_LDr 14 | ||
| 59 | #define _trans_LBr 15 | ||
| 60 | #define _trans_FUr 16 | ||
| 61 | #define _trans_FRr 17 | ||
| 62 | #define _trans_FDr 18 | ||
| 63 | #define _trans_FLr 19 | ||
| 64 | #define _trans_BUr 20 | ||
| 65 | #define _trans_BRr 21 | ||
| 66 | #define _trans_BDr 22 | ||
| 67 | #define _trans_BLr 23 | ||
| 68 | |||
| 69 | #define _trans_UFm 24 | ||
| 70 | #define _trans_ULm 25 | ||
| 71 | #define _trans_UBm 26 | ||
| 72 | #define _trans_URm 27 | ||
| 73 | #define _trans_DFm 28 | ||
| 74 | #define _trans_DLm 29 | ||
| 75 | #define _trans_DBm 30 | ||
| 76 | #define _trans_DRm 31 | ||
| 77 | #define _trans_RUm 32 | ||
| 78 | #define _trans_RFm 33 | ||
| 79 | #define _trans_RDm 34 | ||
| 80 | #define _trans_RBm 35 | ||
| 81 | #define _trans_LUm 36 | ||
| 82 | #define _trans_LFm 37 | ||
| 83 | #define _trans_LDm 38 | ||
| 84 | #define _trans_LBm 39 | ||
| 85 | #define _trans_FUm 40 | ||
| 86 | #define _trans_FRm 41 | ||
| 87 | #define _trans_FDm 42 | ||
| 88 | #define _trans_FLm 43 | ||
| 89 | #define _trans_BUm 44 | ||
| 90 | #define _trans_BRm 45 | ||
| 91 | #define _trans_BDm 46 | ||
| 92 | #define _trans_BLm 47 | ||
| 93 | |||
| 94 | #define _c_ufr 0U | ||
| 95 | #define _c_ubl 1U | ||
| 96 | #define _c_dfl 2U | ||
| 97 | #define _c_dbr 3U | ||
| 98 | #define _c_ufl 4U | ||
| 99 | #define _c_ubr 5U | ||
| 100 | #define _c_dfr 6U | ||
| 101 | #define _c_dbl 7U | ||
| 102 | |||
| 103 | #define _e_uf 0U | ||
| 104 | #define _e_ub 1U | ||
| 105 | #define _e_db 2U | ||
| 106 | #define _e_df 3U | ||
| 107 | #define _e_ur 4U | ||
| 108 | #define _e_ul 5U | ||
| 109 | #define _e_dl 6U | ||
| 110 | #define _e_dr 7U | ||
| 111 | #define _e_fr 8U | ||
| 112 | #define _e_fl 9U | ||
| 113 | #define _e_bl 10U | ||
| 114 | #define _e_br 11U | ||
| 115 | |||
| 116 | #define _eoshift 4U | ||
| 117 | #define _coshift 5U | ||
| 118 | |||
| 119 | #define _pbits 0xFU | ||
| 120 | #define _esepbit1 0x4U | ||
| 121 | #define _esepbit2 0x8U | ||
| 122 | #define _csepbit 0x4U | ||
| 123 | #define _eobit 0x10U | ||
| 124 | #define _cobits 0xF0U | ||
| 125 | #define _cobits2 0x60U | ||
| 126 | #define _ctwist_cw 0x20U | ||
| 127 | #define _ctwist_ccw 0x40U | ||
| 128 | #define _eflip 0x10U | ||
| 129 | #define _error 0xFFU | ||
| 130 | |||
| 131 | _static cube_t zero = { .corner = {0}, .edge = {0} }; | ||
| 132 | _static cube_t solved = { | ||
| 133 | .corner = {0, 1, 2, 3, 4, 5, 6, 7}, | ||
| 134 | .edge = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} | ||
| 135 | }; | ||
| 136 | |||
| 137 | #define zero_fast fastcube( \ | ||
| 138 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) | ||
| 139 | #define solved_fast fastcube( \ | ||
| 140 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 141 | |||
| 142 | #define _move_cube_U fastcube( \ | ||
| 143 | 5, 4, 2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 1, 0, 6, 7, 8, 9, 10, 11) | ||
| 144 | #define _move_cube_U2 fastcube( \ | ||
| 145 | 1, 0, 2, 3, 5, 4, 6, 7, 1, 0, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11) | ||
| 146 | #define _move_cube_U3 fastcube( \ | ||
| 147 | 4, 5, 2, 3, 1, 0, 6, 7, 5, 4, 2, 3, 0, 1, 6, 7, 8, 9, 10, 11) | ||
| 148 | #define _move_cube_D fastcube( \ | ||
| 149 | 0, 1, 7, 6, 4, 5, 2, 3, 0, 1, 7, 6, 4, 5, 2, 3, 8, 9, 10, 11) | ||
| 150 | #define _move_cube_D2 fastcube( \ | ||
| 151 | 0, 1, 3, 2, 4, 5, 7, 6, 0, 1, 3, 2, 4, 5, 7, 6, 8, 9, 10, 11) | ||
| 152 | #define _move_cube_D3 fastcube( \ | ||
| 153 | 0, 1, 6, 7, 4, 5, 3, 2, 0, 1, 6, 7, 4, 5, 3, 2, 8, 9, 10, 11) | ||
| 154 | #define _move_cube_R fastcube( \ | ||
| 155 | 70, 1, 2, 69, 4, 32, 35, 7, 0, 1, 2, 3, 8, 5, 6, 11, 7, 9, 10, 4) | ||
| 156 | #define _move_cube_R2 fastcube( \ | ||
| 157 | 3, 1, 2, 0, 4, 6, 5, 7, 0, 1, 2, 3, 7, 5, 6, 4, 11, 9, 10, 8) | ||
| 158 | #define _move_cube_R3 fastcube( \ | ||
| 159 | 69, 1, 2, 70, 4, 35, 32, 7, 0, 1, 2, 3, 11, 5, 6, 8, 4, 9, 10, 7) | ||
| 160 | #define _move_cube_L fastcube( \ | ||
| 161 | 0, 71, 68, 3, 33, 5, 6, 34, 0, 1, 2, 3, 4, 10, 9, 7, 8, 5, 6, 11) | ||
| 162 | #define _move_cube_L2 fastcube( \ | ||
| 163 | 0, 2, 1, 3, 7, 5, 6, 4, 0, 1, 2, 3, 4, 6, 5, 7, 8, 10, 9, 11) | ||
| 164 | #define _move_cube_L3 fastcube( \ | ||
| 165 | 0, 68, 71, 3, 34, 5, 6, 33, 0, 1, 2, 3, 4, 9, 10, 7, 8, 6, 5, 11) | ||
| 166 | #define _move_cube_F fastcube( \ | ||
| 167 | 36, 1, 38, 3, 66, 5, 64, 7, 25, 1, 2, 24, 4, 5, 6, 7, 16, 19, 10, 11) | ||
| 168 | #define _move_cube_F2 fastcube( \ | ||
| 169 | 2, 1, 0, 3, 6, 5, 4, 7, 3, 1, 2, 0, 4, 5, 6, 7, 9, 8, 10, 11) | ||
| 170 | #define _move_cube_F3 fastcube( \ | ||
| 171 | 38, 1, 36, 3, 64, 5, 66, 7, 24, 1, 2, 25, 4, 5, 6, 7, 19, 16, 10, 11) | ||
| 172 | #define _move_cube_B fastcube( \ | ||
| 173 | 0, 37, 2, 39, 4, 67, 6, 65, 0, 27, 26, 3, 4, 5, 6, 7, 8, 9, 17, 18) | ||
| 174 | #define _move_cube_B2 fastcube( \ | ||
| 175 | 0, 3, 2, 1, 4, 7, 6, 5, 0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 11, 10) | ||
| 176 | #define _move_cube_B3 fastcube( \ | ||
| 177 | 0, 39, 2, 37, 4, 65, 6, 67, 0, 26, 27, 3, 4, 5, 6, 7, 8, 9, 18, 17) | ||
| 178 | |||
| 179 | #define _trans_cube_UFr fastcube( \ | ||
| 180 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 181 | #define _trans_cube_UFr_inverse fastcube( \ | ||
| 182 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 183 | #define _trans_cube_ULr fastcube( \ | ||
| 184 | 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24) | ||
| 185 | #define _trans_cube_ULr_inverse fastcube( \ | ||
| 186 | 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26) | ||
| 187 | #define _trans_cube_UBr fastcube( \ | ||
| 188 | 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9) | ||
| 189 | #define _trans_cube_UBr_inverse fastcube( \ | ||
| 190 | 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9) | ||
| 191 | #define _trans_cube_URr fastcube( \ | ||
| 192 | 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26) | ||
| 193 | #define _trans_cube_URr_inverse fastcube( \ | ||
| 194 | 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24) | ||
| 195 | #define _trans_cube_DFr fastcube( \ | ||
| 196 | 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10) | ||
| 197 | #define _trans_cube_DFr_inverse fastcube( \ | ||
| 198 | 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10) | ||
| 199 | #define _trans_cube_DLr fastcube( \ | ||
| 200 | 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27) | ||
| 201 | #define _trans_cube_DLr_inverse fastcube( \ | ||
| 202 | 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27) | ||
| 203 | #define _trans_cube_DBr fastcube( \ | ||
| 204 | 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8) | ||
| 205 | #define _trans_cube_DBr_inverse fastcube( \ | ||
| 206 | 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8) | ||
| 207 | #define _trans_cube_DRr fastcube( \ | ||
| 208 | 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25) | ||
| 209 | #define _trans_cube_DRr_inverse fastcube( \ | ||
| 210 | 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25) | ||
| 211 | #define _trans_cube_RUr fastcube( \ | ||
| 212 | 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3) | ||
| 213 | #define _trans_cube_RUr_inverse fastcube( \ | ||
| 214 | 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21) | ||
| 215 | #define _trans_cube_RFr fastcube( \ | ||
| 216 | 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18) | ||
| 217 | #define _trans_cube_RFr_inverse fastcube( \ | ||
| 218 | 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17) | ||
| 219 | #define _trans_cube_RDr fastcube( \ | ||
| 220 | 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1) | ||
| 221 | #define _trans_cube_RDr_inverse fastcube( \ | ||
| 222 | 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20) | ||
| 223 | #define _trans_cube_RBr fastcube( \ | ||
| 224 | 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16) | ||
| 225 | #define _trans_cube_RBr_inverse fastcube( \ | ||
| 226 | 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16) | ||
| 227 | #define _trans_cube_LUr fastcube( \ | ||
| 228 | 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2) | ||
| 229 | #define _trans_cube_LUr_inverse fastcube( \ | ||
| 230 | 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23) | ||
| 231 | #define _trans_cube_LFr fastcube( \ | ||
| 232 | 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17) | ||
| 233 | #define _trans_cube_LFr_inverse fastcube( \ | ||
| 234 | 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18) | ||
| 235 | #define _trans_cube_LDr fastcube( \ | ||
| 236 | 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0) | ||
| 237 | #define _trans_cube_LDr_inverse fastcube( \ | ||
| 238 | 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22) | ||
| 239 | #define _trans_cube_LBr fastcube( \ | ||
| 240 | 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19) | ||
| 241 | #define _trans_cube_LBr_inverse fastcube( \ | ||
| 242 | 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19) | ||
| 243 | #define _trans_cube_FUr fastcube( \ | ||
| 244 | 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6) | ||
| 245 | #define _trans_cube_FUr_inverse fastcube( \ | ||
| 246 | 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6) | ||
| 247 | #define _trans_cube_FRr fastcube( \ | ||
| 248 | 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21) | ||
| 249 | #define _trans_cube_FRr_inverse fastcube( \ | ||
| 250 | 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3) | ||
| 251 | #define _trans_cube_FDr fastcube( \ | ||
| 252 | 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4) | ||
| 253 | #define _trans_cube_FDr_inverse fastcube( \ | ||
| 254 | 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7) | ||
| 255 | #define _trans_cube_FLr fastcube( \ | ||
| 256 | 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23) | ||
| 257 | #define _trans_cube_FLr_inverse fastcube( \ | ||
| 258 | 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2) | ||
| 259 | #define _trans_cube_BUr fastcube( \ | ||
| 260 | 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7) | ||
| 261 | #define _trans_cube_BUr_inverse fastcube( \ | ||
| 262 | 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4) | ||
| 263 | #define _trans_cube_BRr fastcube( \ | ||
| 264 | 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22) | ||
| 265 | #define _trans_cube_BRr_inverse fastcube( \ | ||
| 266 | 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0) | ||
| 267 | #define _trans_cube_BDr fastcube( \ | ||
| 268 | 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5) | ||
| 269 | #define _trans_cube_BDr_inverse fastcube( \ | ||
| 270 | 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5) | ||
| 271 | #define _trans_cube_BLr fastcube( \ | ||
| 272 | 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20) | ||
| 273 | #define _trans_cube_BLr_inverse fastcube( \ | ||
| 274 | 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1) | ||
| 275 | #define _trans_cube_UFm fastcube( \ | ||
| 276 | 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10) | ||
| 277 | #define _trans_cube_UFm_inverse fastcube( \ | ||
| 278 | 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10) | ||
| 279 | #define _trans_cube_ULm fastcube( \ | ||
| 280 | 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25) | ||
| 281 | #define _trans_cube_ULm_inverse fastcube( \ | ||
| 282 | 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25) | ||
| 283 | #define _trans_cube_UBm fastcube( \ | ||
| 284 | 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8) | ||
| 285 | #define _trans_cube_UBm_inverse fastcube( \ | ||
| 286 | 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8) | ||
| 287 | #define _trans_cube_URm fastcube( \ | ||
| 288 | 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27) | ||
| 289 | #define _trans_cube_URm_inverse fastcube( \ | ||
| 290 | 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27) | ||
| 291 | #define _trans_cube_DFm fastcube( \ | ||
| 292 | 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11) | ||
| 293 | #define _trans_cube_DFm_inverse fastcube( \ | ||
| 294 | 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11) | ||
| 295 | #define _trans_cube_DLm fastcube( \ | ||
| 296 | 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26) | ||
| 297 | #define _trans_cube_DLm_inverse fastcube( \ | ||
| 298 | 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24) | ||
| 299 | #define _trans_cube_DBm fastcube( \ | ||
| 300 | 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9) | ||
| 301 | #define _trans_cube_DBm_inverse fastcube( \ | ||
| 302 | 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9) | ||
| 303 | #define _trans_cube_DRm fastcube( \ | ||
| 304 | 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24) | ||
| 305 | #define _trans_cube_DRm_inverse fastcube( \ | ||
| 306 | 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26) | ||
| 307 | #define _trans_cube_RUm fastcube( \ | ||
| 308 | 68, 71, 69, 70, 33, 34, 32, 35, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3) | ||
| 309 | #define _trans_cube_RUm_inverse fastcube( \ | ||
| 310 | 70, 68, 69, 71, 32, 34, 35, 33, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22) | ||
| 311 | #define _trans_cube_RFm fastcube( \ | ||
| 312 | 34, 33, 32, 35, 68, 71, 70, 69, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18) | ||
| 313 | #define _trans_cube_RFm_inverse fastcube( \ | ||
| 314 | 66, 65, 64, 67, 36, 39, 38, 37, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18) | ||
| 315 | #define _trans_cube_RDm fastcube( \ | ||
| 316 | 71, 68, 70, 69, 34, 33, 35, 32, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1) | ||
| 317 | #define _trans_cube_RDm_inverse fastcube( \ | ||
| 318 | 71, 69, 68, 70, 33, 35, 34, 32, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23) | ||
| 319 | #define _trans_cube_RBm fastcube( \ | ||
| 320 | 33, 34, 35, 32, 71, 68, 69, 70, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16) | ||
| 321 | #define _trans_cube_RBm_inverse fastcube( \ | ||
| 322 | 67, 64, 65, 66, 37, 38, 39, 36, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19) | ||
| 323 | #define _trans_cube_LUm fastcube( \ | ||
| 324 | 69, 70, 68, 71, 32, 35, 33, 34, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2) | ||
| 325 | #define _trans_cube_LUm_inverse fastcube( \ | ||
| 326 | 68, 70, 71, 69, 34, 32, 33, 35, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20) | ||
| 327 | #define _trans_cube_LFm fastcube( \ | ||
| 328 | 32, 35, 34, 33, 70, 69, 68, 71, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17) | ||
| 329 | #define _trans_cube_LFm_inverse fastcube( \ | ||
| 330 | 64, 67, 66, 65, 38, 37, 36, 39, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17) | ||
| 331 | #define _trans_cube_LDm fastcube( \ | ||
| 332 | 70, 69, 71, 68, 35, 32, 34, 33, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0) | ||
| 333 | #define _trans_cube_LDm_inverse fastcube( \ | ||
| 334 | 69, 71, 70, 68, 35, 33, 32, 34, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21) | ||
| 335 | #define _trans_cube_LBm fastcube( \ | ||
| 336 | 35, 32, 33, 34, 69, 70, 71, 68, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19) | ||
| 337 | #define _trans_cube_LBm_inverse fastcube( \ | ||
| 338 | 65, 66, 67, 64, 39, 36, 37, 38, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16) | ||
| 339 | #define _trans_cube_FUm fastcube( \ | ||
| 340 | 64, 66, 65, 67, 36, 38, 37, 39, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7) | ||
| 341 | #define _trans_cube_FUm_inverse fastcube( \ | ||
| 342 | 32, 34, 33, 35, 68, 70, 69, 71, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7) | ||
| 343 | #define _trans_cube_FRm fastcube( \ | ||
| 344 | 36, 38, 39, 37, 66, 64, 65, 67, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20) | ||
| 345 | #define _trans_cube_FRm_inverse fastcube( \ | ||
| 346 | 37, 38, 36, 39, 64, 67, 65, 66, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2) | ||
| 347 | #define _trans_cube_FDm fastcube( \ | ||
| 348 | 66, 64, 67, 65, 38, 36, 39, 37, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5) | ||
| 349 | #define _trans_cube_FDm_inverse fastcube( \ | ||
| 350 | 33, 35, 32, 34, 69, 71, 68, 70, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6) | ||
| 351 | #define _trans_cube_FLm fastcube( \ | ||
| 352 | 38, 36, 37, 39, 64, 66, 67, 65, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22) | ||
| 353 | #define _trans_cube_FLm_inverse fastcube( \ | ||
| 354 | 36, 39, 37, 38, 65, 66, 64, 67, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3) | ||
| 355 | #define _trans_cube_BUm fastcube( \ | ||
| 356 | 65, 67, 64, 66, 37, 39, 36, 38, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6) | ||
| 357 | #define _trans_cube_BUm_inverse fastcube( \ | ||
| 358 | 34, 32, 35, 33, 70, 68, 71, 69, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5) | ||
| 359 | #define _trans_cube_BRm fastcube( \ | ||
| 360 | 39, 37, 36, 38, 65, 67, 66, 64, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23) | ||
| 361 | #define _trans_cube_BRm_inverse fastcube( \ | ||
| 362 | 39, 36, 38, 37, 66, 65, 67, 64, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1) | ||
| 363 | #define _trans_cube_BDm fastcube( \ | ||
| 364 | 67, 65, 66, 64, 39, 37, 38, 36, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4) | ||
| 365 | #define _trans_cube_BDm_inverse fastcube( \ | ||
| 366 | 35, 33, 34, 32, 71, 69, 70, 68, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4) | ||
| 367 | #define _trans_cube_BLm fastcube( \ | ||
| 368 | 37, 39, 38, 36, 67, 65, 64, 66, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21) | ||
| 369 | #define _trans_cube_BLm_inverse fastcube( \ | ||
| 370 | 38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0) | ||
| 371 | |||
| 372 | _static const char *cornerstr[] = { | ||
| 373 | [_c_ufr] = "UFR", | ||
| 374 | [_c_ubl] = "UBL", | ||
| 375 | [_c_dfl] = "DFL", | ||
| 376 | [_c_dbr] = "DBR", | ||
| 377 | [_c_ufl] = "UFL", | ||
| 378 | [_c_ubr] = "UBR", | ||
| 379 | [_c_dfr] = "DFR", | ||
| 380 | [_c_dbl] = "DBL" | ||
| 381 | }; | ||
| 382 | |||
| 383 | _static const char *cornerstralt[] = { | ||
| 384 | [_c_ufr] = "URF", | ||
| 385 | [_c_ubl] = "ULB", | ||
| 386 | [_c_dfl] = "DLF", | ||
| 387 | [_c_dbr] = "DRB", | ||
| 388 | [_c_ufl] = "ULF", | ||
| 389 | [_c_ubr] = "URB", | ||
| 390 | [_c_dfr] = "DRF", | ||
| 391 | [_c_dbl] = "DLB" | ||
| 392 | }; | ||
| 393 | |||
| 394 | _static const char *edgestr[] = { | ||
| 395 | [_e_uf] = "UF", | ||
| 396 | [_e_ub] = "UB", | ||
| 397 | [_e_db] = "DB", | ||
| 398 | [_e_df] = "DF", | ||
| 399 | [_e_ur] = "UR", | ||
| 400 | [_e_ul] = "UL", | ||
| 401 | [_e_dl] = "DL", | ||
| 402 | [_e_dr] = "DR", | ||
| 403 | [_e_fr] = "FR", | ||
| 404 | [_e_fl] = "FL", | ||
| 405 | [_e_bl] = "BL", | ||
| 406 | [_e_br] = "BR" | ||
| 407 | }; | ||
| 408 | |||
| 409 | _static const char *movestr[] = { | ||
| 410 | [_move_U] = "U", | ||
| 411 | [_move_U2] = "U2", | ||
| 412 | [_move_U3] = "U'", | ||
| 413 | [_move_D] = "D", | ||
| 414 | [_move_D2] = "D2", | ||
| 415 | [_move_D3] = "D'", | ||
| 416 | [_move_R] = "R", | ||
| 417 | [_move_R2] = "R2", | ||
| 418 | [_move_R3] = "R'", | ||
| 419 | [_move_L] = "L", | ||
| 420 | [_move_L2] = "L2", | ||
| 421 | [_move_L3] = "L'", | ||
| 422 | [_move_F] = "F", | ||
| 423 | [_move_F2] = "F2", | ||
| 424 | [_move_F3] = "F'", | ||
| 425 | [_move_B] = "B", | ||
| 426 | [_move_B2] = "B2", | ||
| 427 | [_move_B3] = "B'", | ||
| 428 | }; | ||
| 429 | |||
| 430 | _static const char *transstr[] = { | ||
| 431 | [_trans_UFr] = "rotation UF", | ||
| 432 | [_trans_UFm] = "mirrored UF", | ||
| 433 | [_trans_ULr] = "rotation UL", | ||
| 434 | [_trans_ULm] = "mirrored UL", | ||
| 435 | [_trans_UBr] = "rotation UB", | ||
| 436 | [_trans_UBm] = "mirrored UB", | ||
| 437 | [_trans_URr] = "rotation UR", | ||
| 438 | [_trans_URm] = "mirrored UR", | ||
| 439 | [_trans_DFr] = "rotation DF", | ||
| 440 | [_trans_DFm] = "mirrored DF", | ||
| 441 | [_trans_DLr] = "rotation DL", | ||
| 442 | [_trans_DLm] = "mirrored DL", | ||
| 443 | [_trans_DBr] = "rotation DB", | ||
| 444 | [_trans_DBm] = "mirrored DB", | ||
| 445 | [_trans_DRr] = "rotation DR", | ||
| 446 | [_trans_DRm] = "mirrored DR", | ||
| 447 | [_trans_RUr] = "rotation RU", | ||
| 448 | [_trans_RUm] = "mirrored RU", | ||
| 449 | [_trans_RFr] = "rotation RF", | ||
| 450 | [_trans_RFm] = "mirrored RF", | ||
| 451 | [_trans_RDr] = "rotation RD", | ||
| 452 | [_trans_RDm] = "mirrored RD", | ||
| 453 | [_trans_RBr] = "rotation RB", | ||
| 454 | [_trans_RBm] = "mirrored RB", | ||
| 455 | [_trans_LUr] = "rotation LU", | ||
| 456 | [_trans_LUm] = "mirrored LU", | ||
| 457 | [_trans_LFr] = "rotation LF", | ||
| 458 | [_trans_LFm] = "mirrored LF", | ||
| 459 | [_trans_LDr] = "rotation LD", | ||
| 460 | [_trans_LDm] = "mirrored LD", | ||
| 461 | [_trans_LBr] = "rotation LB", | ||
| 462 | [_trans_LBm] = "mirrored LB", | ||
| 463 | [_trans_FUr] = "rotation FU", | ||
| 464 | [_trans_FUm] = "mirrored FU", | ||
| 465 | [_trans_FRr] = "rotation FR", | ||
| 466 | [_trans_FRm] = "mirrored FR", | ||
| 467 | [_trans_FDr] = "rotation FD", | ||
| 468 | [_trans_FDm] = "mirrored FD", | ||
| 469 | [_trans_FLr] = "rotation FL", | ||
| 470 | [_trans_FLm] = "mirrored FL", | ||
| 471 | [_trans_BUr] = "rotation BU", | ||
| 472 | [_trans_BUm] = "mirrored BU", | ||
| 473 | [_trans_BRr] = "rotation BR", | ||
| 474 | [_trans_BRm] = "mirrored BR", | ||
| 475 | [_trans_BDr] = "rotation BD", | ||
| 476 | [_trans_BDm] = "mirrored BD", | ||
| 477 | [_trans_BLr] = "rotation BL", | ||
| 478 | [_trans_BLm] = "mirrored BL", | ||
| 479 | }; | ||
| 480 | |||
| 481 | static uint8_t inverse_trans_table[48] = { | ||
| 482 | [_trans_UFr] = _trans_UFr, | ||
| 483 | [_trans_UFm] = _trans_UFm, | ||
| 484 | [_trans_ULr] = _trans_URr, | ||
| 485 | [_trans_ULm] = _trans_ULm, | ||
| 486 | [_trans_UBr] = _trans_UBr, | ||
| 487 | [_trans_UBm] = _trans_UBm, | ||
| 488 | [_trans_URr] = _trans_ULr, | ||
| 489 | [_trans_URm] = _trans_URm, | ||
| 490 | [_trans_DFr] = _trans_DFr, | ||
| 491 | [_trans_DFm] = _trans_DFm, | ||
| 492 | [_trans_DLr] = _trans_DLr, | ||
| 493 | [_trans_DLm] = _trans_DRm, | ||
| 494 | [_trans_DBr] = _trans_DBr, | ||
| 495 | [_trans_DBm] = _trans_DBm, | ||
| 496 | [_trans_DRr] = _trans_DRr, | ||
| 497 | [_trans_DRm] = _trans_DLm, | ||
| 498 | [_trans_RUr] = _trans_FRr, | ||
| 499 | [_trans_RUm] = _trans_FLm, | ||
| 500 | [_trans_RFr] = _trans_LFr, | ||
| 501 | [_trans_RFm] = _trans_RFm, | ||
| 502 | [_trans_RDr] = _trans_BLr, | ||
| 503 | [_trans_RDm] = _trans_BRm, | ||
| 504 | [_trans_RBr] = _trans_RBr, | ||
| 505 | [_trans_RBm] = _trans_LBm, | ||
| 506 | [_trans_LUr] = _trans_FLr, | ||
| 507 | [_trans_LUm] = _trans_FRm, | ||
| 508 | [_trans_LFr] = _trans_RFr, | ||
| 509 | [_trans_LFm] = _trans_LFm, | ||
| 510 | [_trans_LDr] = _trans_BRr, | ||
| 511 | [_trans_LDm] = _trans_BLm, | ||
| 512 | [_trans_LBr] = _trans_LBr, | ||
| 513 | [_trans_LBm] = _trans_RBm, | ||
| 514 | [_trans_FUr] = _trans_FUr, | ||
| 515 | [_trans_FUm] = _trans_FUm, | ||
| 516 | [_trans_FRr] = _trans_RUr, | ||
| 517 | [_trans_FRm] = _trans_LUm, | ||
| 518 | [_trans_FDr] = _trans_BUr, | ||
| 519 | [_trans_FDm] = _trans_BUm, | ||
| 520 | [_trans_FLr] = _trans_LUr, | ||
| 521 | [_trans_FLm] = _trans_RUm, | ||
| 522 | [_trans_BUr] = _trans_FDr, | ||
| 523 | [_trans_BUm] = _trans_FDm, | ||
| 524 | [_trans_BRr] = _trans_LDr, | ||
| 525 | [_trans_BRm] = _trans_RDm, | ||
| 526 | [_trans_BDr] = _trans_BDr, | ||
| 527 | [_trans_BDm] = _trans_BDm, | ||
| 528 | [_trans_BLr] = _trans_RDr, | ||
| 529 | [_trans_BLm] = _trans_LDm, | ||
| 530 | }; | ||
| @@ -2,10 +2,7 @@ | |||
| 2 | #include <stdbool.h> | 2 | #include <stdbool.h> |
| 3 | #include <string.h> | 3 | #include <string.h> |
| 4 | 4 | ||
| 5 | #include "cube.h" | ||
| 6 | |||
| 7 | #ifdef DEBUG | 5 | #ifdef DEBUG |
| 8 | |||
| 9 | #include <stdio.h> | 6 | #include <stdio.h> |
| 10 | #define _static | 7 | #define _static |
| 11 | #define _static_inline | 8 | #define _static_inline |
| @@ -16,2377 +13,27 @@ | |||
| 16 | DBG_LOG(__VA_ARGS__); \ | 13 | DBG_LOG(__VA_ARGS__); \ |
| 17 | return retval; \ | 14 | return retval; \ |
| 18 | } | 15 | } |
| 19 | |||
| 20 | #else | 16 | #else |
| 21 | |||
| 22 | #define _static static | 17 | #define _static static |
| 23 | #define _static_inline static inline | 18 | #define _static_inline static inline |
| 24 | #define DBG_LOG(...) | 19 | #define DBG_LOG(...) |
| 25 | #define DBG_WARN(condition, ...) | 20 | #define DBG_WARN(condition, ...) |
| 26 | #define DBG_ASSERT(condition, retval, ...) | 21 | #define DBG_ASSERT(condition, retval, ...) |
| 27 | |||
| 28 | #endif | 22 | #endif |
| 29 | 23 | ||
| 30 | /****************************************************************************** | 24 | #include "cube.h" |
| 31 | Section: mathematical constants | 25 | #include "constants.h" |
| 32 | ******************************************************************************/ | ||
| 33 | |||
| 34 | #define _2p11 2048U | ||
| 35 | #define _2p12 4096U | ||
| 36 | #define _3p7 2187U | ||
| 37 | #define _3p8 6561U | ||
| 38 | #define _12c4 495U | ||
| 39 | #define _8c4 70U | ||
| 40 | |||
| 41 | #define COCSEP_CLASSES 3393U | ||
| 42 | |||
| 43 | _static int64_t binomial[12][12] = { | ||
| 44 | {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 45 | {1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 46 | {1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 47 | {1, 3, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0}, | ||
| 48 | {1, 4, 6, 4, 1, 0, 0, 0, 0, 0, 0, 0}, | ||
| 49 | {1, 5, 10, 10, 5, 1, 0, 0, 0, 0, 0, 0}, | ||
| 50 | {1, 6, 15, 20, 15, 6, 1, 0, 0, 0, 0, 0}, | ||
| 51 | {1, 7, 21, 35, 35, 21, 7, 1, 0, 0, 0, 0}, | ||
| 52 | {1, 8, 28, 56, 70, 56, 28, 8, 1, 0, 0, 0}, | ||
| 53 | {1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 0, 0}, | ||
| 54 | {1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 0}, | ||
| 55 | {1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1}, | ||
| 56 | }; | ||
| 57 | |||
| 58 | /****************************************************************************** | ||
| 59 | Section: moves definitions and tables | ||
| 60 | ******************************************************************************/ | ||
| 61 | |||
| 62 | #define _move_U 0U | ||
| 63 | #define _move_U2 1U | ||
| 64 | #define _move_U3 2U | ||
| 65 | #define _move_D 3U | ||
| 66 | #define _move_D2 4U | ||
| 67 | #define _move_D3 5U | ||
| 68 | #define _move_R 6U | ||
| 69 | #define _move_R2 7U | ||
| 70 | #define _move_R3 8U | ||
| 71 | #define _move_L 9U | ||
| 72 | #define _move_L2 10U | ||
| 73 | #define _move_L3 11U | ||
| 74 | #define _move_F 12U | ||
| 75 | #define _move_F2 13U | ||
| 76 | #define _move_F3 14U | ||
| 77 | #define _move_B 15U | ||
| 78 | #define _move_B2 16U | ||
| 79 | #define _move_B3 17U | ||
| 80 | |||
| 81 | #define _trans_UFr 0 | ||
| 82 | #define _trans_ULr 1 | ||
| 83 | #define _trans_UBr 2 | ||
| 84 | #define _trans_URr 3 | ||
| 85 | #define _trans_DFr 4 | ||
| 86 | #define _trans_DLr 5 | ||
| 87 | #define _trans_DBr 6 | ||
| 88 | #define _trans_DRr 7 | ||
| 89 | #define _trans_RUr 8 | ||
| 90 | #define _trans_RFr 9 | ||
| 91 | #define _trans_RDr 10 | ||
| 92 | #define _trans_RBr 11 | ||
| 93 | #define _trans_LUr 12 | ||
| 94 | #define _trans_LFr 13 | ||
| 95 | #define _trans_LDr 14 | ||
| 96 | #define _trans_LBr 15 | ||
| 97 | #define _trans_FUr 16 | ||
| 98 | #define _trans_FRr 17 | ||
| 99 | #define _trans_FDr 18 | ||
| 100 | #define _trans_FLr 19 | ||
| 101 | #define _trans_BUr 20 | ||
| 102 | #define _trans_BRr 21 | ||
| 103 | #define _trans_BDr 22 | ||
| 104 | #define _trans_BLr 23 | ||
| 105 | |||
| 106 | #define _trans_UFm 24 | ||
| 107 | #define _trans_ULm 25 | ||
| 108 | #define _trans_UBm 26 | ||
| 109 | #define _trans_URm 27 | ||
| 110 | #define _trans_DFm 28 | ||
| 111 | #define _trans_DLm 29 | ||
| 112 | #define _trans_DBm 30 | ||
| 113 | #define _trans_DRm 31 | ||
| 114 | #define _trans_RUm 32 | ||
| 115 | #define _trans_RFm 33 | ||
| 116 | #define _trans_RDm 34 | ||
| 117 | #define _trans_RBm 35 | ||
| 118 | #define _trans_LUm 36 | ||
| 119 | #define _trans_LFm 37 | ||
| 120 | #define _trans_LDm 38 | ||
| 121 | #define _trans_LBm 39 | ||
| 122 | #define _trans_FUm 40 | ||
| 123 | #define _trans_FRm 41 | ||
| 124 | #define _trans_FDm 42 | ||
| 125 | #define _trans_FLm 43 | ||
| 126 | #define _trans_BUm 44 | ||
| 127 | #define _trans_BRm 45 | ||
| 128 | #define _trans_BDm 46 | ||
| 129 | #define _trans_BLm 47 | ||
| 130 | |||
| 131 | #define _c_ufr 0U | ||
| 132 | #define _c_ubl 1U | ||
| 133 | #define _c_dfl 2U | ||
| 134 | #define _c_dbr 3U | ||
| 135 | #define _c_ufl 4U | ||
| 136 | #define _c_ubr 5U | ||
| 137 | #define _c_dfr 6U | ||
| 138 | #define _c_dbl 7U | ||
| 139 | |||
| 140 | #define _e_uf 0U | ||
| 141 | #define _e_ub 1U | ||
| 142 | #define _e_db 2U | ||
| 143 | #define _e_df 3U | ||
| 144 | #define _e_ur 4U | ||
| 145 | #define _e_ul 5U | ||
| 146 | #define _e_dl 6U | ||
| 147 | #define _e_dr 7U | ||
| 148 | #define _e_fr 8U | ||
| 149 | #define _e_fl 9U | ||
| 150 | #define _e_bl 10U | ||
| 151 | #define _e_br 11U | ||
| 152 | |||
| 153 | #define _eoshift 4U | ||
| 154 | #define _coshift 5U | ||
| 155 | |||
| 156 | #define _pbits 0xFU | ||
| 157 | #define _esepbit1 0x4U | ||
| 158 | #define _esepbit2 0x8U | ||
| 159 | #define _csepbit 0x4U | ||
| 160 | #define _eobit 0x10U | ||
| 161 | #define _cobits 0xF0U | ||
| 162 | #define _cobits2 0x60U | ||
| 163 | #define _ctwist_cw 0x20U | ||
| 164 | #define _ctwist_ccw 0x40U | ||
| 165 | #define _eflip 0x10U | ||
| 166 | #define _error 0xFFU | ||
| 167 | |||
| 168 | _static cube_t zero = { .corner = {0}, .edge = {0} }; | ||
| 169 | _static cube_t solved = { | ||
| 170 | .corner = {0, 1, 2, 3, 4, 5, 6, 7}, | ||
| 171 | .edge = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11} | ||
| 172 | }; | ||
| 173 | |||
| 174 | #define zero_fast fastcube( \ | ||
| 175 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0) | ||
| 176 | #define solved_fast fastcube( \ | ||
| 177 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 178 | |||
| 179 | #define _move_cube_U fastcube( \ | ||
| 180 | 5, 4, 2, 3, 0, 1, 6, 7, 4, 5, 2, 3, 1, 0, 6, 7, 8, 9, 10, 11) | ||
| 181 | #define _move_cube_U2 fastcube( \ | ||
| 182 | 1, 0, 2, 3, 5, 4, 6, 7, 1, 0, 2, 3, 5, 4, 6, 7, 8, 9, 10, 11) | ||
| 183 | #define _move_cube_U3 fastcube( \ | ||
| 184 | 4, 5, 2, 3, 1, 0, 6, 7, 5, 4, 2, 3, 0, 1, 6, 7, 8, 9, 10, 11) | ||
| 185 | #define _move_cube_D fastcube( \ | ||
| 186 | 0, 1, 7, 6, 4, 5, 2, 3, 0, 1, 7, 6, 4, 5, 2, 3, 8, 9, 10, 11) | ||
| 187 | #define _move_cube_D2 fastcube( \ | ||
| 188 | 0, 1, 3, 2, 4, 5, 7, 6, 0, 1, 3, 2, 4, 5, 7, 6, 8, 9, 10, 11) | ||
| 189 | #define _move_cube_D3 fastcube( \ | ||
| 190 | 0, 1, 6, 7, 4, 5, 3, 2, 0, 1, 6, 7, 4, 5, 3, 2, 8, 9, 10, 11) | ||
| 191 | #define _move_cube_R fastcube( \ | ||
| 192 | 70, 1, 2, 69, 4, 32, 35, 7, 0, 1, 2, 3, 8, 5, 6, 11, 7, 9, 10, 4) | ||
| 193 | #define _move_cube_R2 fastcube( \ | ||
| 194 | 3, 1, 2, 0, 4, 6, 5, 7, 0, 1, 2, 3, 7, 5, 6, 4, 11, 9, 10, 8) | ||
| 195 | #define _move_cube_R3 fastcube( \ | ||
| 196 | 69, 1, 2, 70, 4, 35, 32, 7, 0, 1, 2, 3, 11, 5, 6, 8, 4, 9, 10, 7) | ||
| 197 | #define _move_cube_L fastcube( \ | ||
| 198 | 0, 71, 68, 3, 33, 5, 6, 34, 0, 1, 2, 3, 4, 10, 9, 7, 8, 5, 6, 11) | ||
| 199 | #define _move_cube_L2 fastcube( \ | ||
| 200 | 0, 2, 1, 3, 7, 5, 6, 4, 0, 1, 2, 3, 4, 6, 5, 7, 8, 10, 9, 11) | ||
| 201 | #define _move_cube_L3 fastcube( \ | ||
| 202 | 0, 68, 71, 3, 34, 5, 6, 33, 0, 1, 2, 3, 4, 9, 10, 7, 8, 6, 5, 11) | ||
| 203 | #define _move_cube_F fastcube( \ | ||
| 204 | 36, 1, 38, 3, 66, 5, 64, 7, 25, 1, 2, 24, 4, 5, 6, 7, 16, 19, 10, 11) | ||
| 205 | #define _move_cube_F2 fastcube( \ | ||
| 206 | 2, 1, 0, 3, 6, 5, 4, 7, 3, 1, 2, 0, 4, 5, 6, 7, 9, 8, 10, 11) | ||
| 207 | #define _move_cube_F3 fastcube( \ | ||
| 208 | 38, 1, 36, 3, 64, 5, 66, 7, 24, 1, 2, 25, 4, 5, 6, 7, 19, 16, 10, 11) | ||
| 209 | #define _move_cube_B fastcube( \ | ||
| 210 | 0, 37, 2, 39, 4, 67, 6, 65, 0, 27, 26, 3, 4, 5, 6, 7, 8, 9, 17, 18) | ||
| 211 | #define _move_cube_B2 fastcube( \ | ||
| 212 | 0, 3, 2, 1, 4, 7, 6, 5, 0, 2, 1, 3, 4, 5, 6, 7, 8, 9, 11, 10) | ||
| 213 | #define _move_cube_B3 fastcube( \ | ||
| 214 | 0, 39, 2, 37, 4, 65, 6, 67, 0, 26, 27, 3, 4, 5, 6, 7, 8, 9, 18, 17) | ||
| 215 | |||
| 216 | #define _trans_cube_UFr fastcube( \ | ||
| 217 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 218 | #define _trans_cube_UFr_inverse fastcube( \ | ||
| 219 | 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) | ||
| 220 | #define _trans_cube_ULr fastcube( \ | ||
| 221 | 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24) | ||
| 222 | #define _trans_cube_ULr_inverse fastcube( \ | ||
| 223 | 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26) | ||
| 224 | #define _trans_cube_UBr fastcube( \ | ||
| 225 | 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9) | ||
| 226 | #define _trans_cube_UBr_inverse fastcube( \ | ||
| 227 | 1, 0, 3, 2, 5, 4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6, 10, 11, 8, 9) | ||
| 228 | #define _trans_cube_URr fastcube( \ | ||
| 229 | 5, 4, 6, 7, 0, 1, 3, 2, 4, 5, 6, 7, 1, 0, 3, 2, 27, 24, 25, 26) | ||
| 230 | #define _trans_cube_URr_inverse fastcube( \ | ||
| 231 | 4, 5, 7, 6, 1, 0, 2, 3, 5, 4, 7, 6, 0, 1, 2, 3, 25, 26, 27, 24) | ||
| 232 | #define _trans_cube_DFr fastcube( \ | ||
| 233 | 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10) | ||
| 234 | #define _trans_cube_DFr_inverse fastcube( \ | ||
| 235 | 2, 3, 0, 1, 6, 7, 4, 5, 3, 2, 1, 0, 6, 7, 4, 5, 9, 8, 11, 10) | ||
| 236 | #define _trans_cube_DLr fastcube( \ | ||
| 237 | 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27) | ||
| 238 | #define _trans_cube_DLr_inverse fastcube( \ | ||
| 239 | 7, 6, 4, 5, 2, 3, 1, 0, 6, 7, 4, 5, 2, 3, 0, 1, 26, 25, 24, 27) | ||
| 240 | #define _trans_cube_DBr fastcube( \ | ||
| 241 | 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8) | ||
| 242 | #define _trans_cube_DBr_inverse fastcube( \ | ||
| 243 | 3, 2, 1, 0, 7, 6, 5, 4, 2, 3, 0, 1, 7, 6, 5, 4, 11, 10, 9, 8) | ||
| 244 | #define _trans_cube_DRr fastcube( \ | ||
| 245 | 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25) | ||
| 246 | #define _trans_cube_DRr_inverse fastcube( \ | ||
| 247 | 6, 7, 5, 4, 3, 2, 0, 1, 7, 6, 5, 4, 3, 2, 1, 0, 24, 27, 26, 25) | ||
| 248 | #define _trans_cube_RUr fastcube( \ | ||
| 249 | 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3) | ||
| 250 | #define _trans_cube_RUr_inverse fastcube( \ | ||
| 251 | 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21) | ||
| 252 | #define _trans_cube_RFr fastcube( \ | ||
| 253 | 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18) | ||
| 254 | #define _trans_cube_RFr_inverse fastcube( \ | ||
| 255 | 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17) | ||
| 256 | #define _trans_cube_RDr fastcube( \ | ||
| 257 | 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1) | ||
| 258 | #define _trans_cube_RDr_inverse fastcube( \ | ||
| 259 | 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20) | ||
| 260 | #define _trans_cube_RBr fastcube( \ | ||
| 261 | 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16) | ||
| 262 | #define _trans_cube_RBr_inverse fastcube( \ | ||
| 263 | 37, 38, 39, 36, 67, 64, 65, 66, 27, 24, 25, 26, 20, 23, 22, 21, 17, 18, 19, 16) | ||
| 264 | #define _trans_cube_LUr fastcube( \ | ||
| 265 | 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2) | ||
| 266 | #define _trans_cube_LUr_inverse fastcube( \ | ||
| 267 | 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23) | ||
| 268 | #define _trans_cube_LFr fastcube( \ | ||
| 269 | 36, 39, 38, 37, 66, 65, 64, 67, 25, 26, 27, 24, 21, 22, 23, 20, 16, 19, 18, 17) | ||
| 270 | #define _trans_cube_LFr_inverse fastcube( \ | ||
| 271 | 38, 37, 36, 39, 64, 67, 66, 65, 24, 27, 26, 25, 23, 20, 21, 22, 19, 16, 17, 18) | ||
| 272 | #define _trans_cube_LDr fastcube( \ | ||
| 273 | 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0) | ||
| 274 | #define _trans_cube_LDr_inverse fastcube( \ | ||
| 275 | 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22) | ||
| 276 | #define _trans_cube_LBr fastcube( \ | ||
| 277 | 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19) | ||
| 278 | #define _trans_cube_LBr_inverse fastcube( \ | ||
| 279 | 39, 36, 37, 38, 65, 66, 67, 64, 26, 25, 24, 27, 22, 21, 20, 23, 18, 17, 16, 19) | ||
| 280 | #define _trans_cube_FUr fastcube( \ | ||
| 281 | 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6) | ||
| 282 | #define _trans_cube_FUr_inverse fastcube( \ | ||
| 283 | 68, 70, 69, 71, 32, 34, 33, 35, 16, 19, 18, 17, 9, 8, 11, 10, 5, 4, 7, 6) | ||
| 284 | #define _trans_cube_FRr fastcube( \ | ||
| 285 | 32, 34, 35, 33, 70, 68, 69, 71, 8, 9, 10, 11, 16, 19, 18, 17, 20, 23, 22, 21) | ||
| 286 | #define _trans_cube_FRr_inverse fastcube( \ | ||
| 287 | 64, 67, 65, 66, 37, 38, 36, 39, 20, 23, 22, 21, 24, 27, 26, 25, 0, 1, 2, 3) | ||
| 288 | #define _trans_cube_FDr fastcube( \ | ||
| 289 | 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4) | ||
| 290 | #define _trans_cube_FDr_inverse fastcube( \ | ||
| 291 | 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7) | ||
| 292 | #define _trans_cube_FLr fastcube( \ | ||
| 293 | 34, 32, 33, 35, 68, 70, 71, 69, 9, 8, 11, 10, 19, 16, 17, 18, 22, 21, 20, 23) | ||
| 294 | #define _trans_cube_FLr_inverse fastcube( \ | ||
| 295 | 65, 66, 64, 67, 36, 39, 37, 38, 21, 22, 23, 20, 26, 25, 24, 27, 1, 0, 3, 2) | ||
| 296 | #define _trans_cube_BUr fastcube( \ | ||
| 297 | 69, 71, 68, 70, 33, 35, 32, 34, 17, 18, 19, 16, 11, 10, 9, 8, 4, 5, 6, 7) | ||
| 298 | #define _trans_cube_BUr_inverse fastcube( \ | ||
| 299 | 70, 68, 71, 69, 34, 32, 35, 33, 19, 16, 17, 18, 8, 9, 10, 11, 7, 6, 5, 4) | ||
| 300 | #define _trans_cube_BRr fastcube( \ | ||
| 301 | 35, 33, 32, 34, 69, 71, 70, 68, 11, 10, 9, 8, 18, 17, 16, 19, 23, 20, 21, 22) | ||
| 302 | #define _trans_cube_BRr_inverse fastcube( \ | ||
| 303 | 66, 65, 67, 64, 39, 36, 38, 37, 22, 21, 20, 23, 25, 26, 27, 24, 3, 2, 1, 0) | ||
| 304 | #define _trans_cube_BDr fastcube( \ | ||
| 305 | 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5) | ||
| 306 | #define _trans_cube_BDr_inverse fastcube( \ | ||
| 307 | 71, 69, 70, 68, 35, 33, 34, 32, 18, 17, 16, 19, 10, 11, 8, 9, 6, 7, 4, 5) | ||
| 308 | #define _trans_cube_BLr fastcube( \ | ||
| 309 | 33, 35, 34, 32, 71, 69, 68, 70, 10, 11, 8, 9, 17, 18, 19, 16, 21, 22, 23, 20) | ||
| 310 | #define _trans_cube_BLr_inverse fastcube( \ | ||
| 311 | 67, 64, 66, 65, 38, 37, 39, 36, 23, 20, 21, 22, 27, 24, 25, 26, 2, 3, 0, 1) | ||
| 312 | #define _trans_cube_UFm fastcube( \ | ||
| 313 | 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10) | ||
| 314 | #define _trans_cube_UFm_inverse fastcube( \ | ||
| 315 | 4, 5, 6, 7, 0, 1, 2, 3, 0, 1, 2, 3, 5, 4, 7, 6, 9, 8, 11, 10) | ||
| 316 | #define _trans_cube_ULm fastcube( \ | ||
| 317 | 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25) | ||
| 318 | #define _trans_cube_ULm_inverse fastcube( \ | ||
| 319 | 0, 1, 3, 2, 5, 4, 6, 7, 4, 5, 6, 7, 0, 1, 2, 3, 24, 27, 26, 25) | ||
| 320 | #define _trans_cube_UBm fastcube( \ | ||
| 321 | 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8) | ||
| 322 | #define _trans_cube_UBm_inverse fastcube( \ | ||
| 323 | 5, 4, 7, 6, 1, 0, 3, 2, 1, 0, 3, 2, 4, 5, 6, 7, 11, 10, 9, 8) | ||
| 324 | #define _trans_cube_URm fastcube( \ | ||
| 325 | 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27) | ||
| 326 | #define _trans_cube_URm_inverse fastcube( \ | ||
| 327 | 1, 0, 2, 3, 4, 5, 7, 6, 5, 4, 7, 6, 1, 0, 3, 2, 26, 25, 24, 27) | ||
| 328 | #define _trans_cube_DFm fastcube( \ | ||
| 329 | 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11) | ||
| 330 | #define _trans_cube_DFm_inverse fastcube( \ | ||
| 331 | 6, 7, 4, 5, 2, 3, 0, 1, 3, 2, 1, 0, 7, 6, 5, 4, 8, 9, 10, 11) | ||
| 332 | #define _trans_cube_DLm fastcube( \ | ||
| 333 | 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26) | ||
| 334 | #define _trans_cube_DLm_inverse fastcube( \ | ||
| 335 | 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24) | ||
| 336 | #define _trans_cube_DBm fastcube( \ | ||
| 337 | 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9) | ||
| 338 | #define _trans_cube_DBm_inverse fastcube( \ | ||
| 339 | 7, 6, 5, 4, 3, 2, 1, 0, 2, 3, 0, 1, 6, 7, 4, 5, 10, 11, 8, 9) | ||
| 340 | #define _trans_cube_DRm fastcube( \ | ||
| 341 | 2, 3, 1, 0, 7, 6, 4, 5, 6, 7, 4, 5, 3, 2, 1, 0, 25, 26, 27, 24) | ||
| 342 | #define _trans_cube_DRm_inverse fastcube( \ | ||
| 343 | 3, 2, 0, 1, 6, 7, 5, 4, 7, 6, 5, 4, 2, 3, 0, 1, 27, 24, 25, 26) | ||
| 344 | #define _trans_cube_RUm fastcube( \ | ||
| 345 | 68, 71, 69, 70, 33, 34, 32, 35, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3) | ||
| 346 | #define _trans_cube_RUm_inverse fastcube( \ | ||
| 347 | 70, 68, 69, 71, 32, 34, 35, 33, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22) | ||
| 348 | #define _trans_cube_RFm fastcube( \ | ||
| 349 | 34, 33, 32, 35, 68, 71, 70, 69, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18) | ||
| 350 | #define _trans_cube_RFm_inverse fastcube( \ | ||
| 351 | 66, 65, 64, 67, 36, 39, 38, 37, 25, 26, 27, 24, 22, 21, 20, 23, 19, 16, 17, 18) | ||
| 352 | #define _trans_cube_RDm fastcube( \ | ||
| 353 | 71, 68, 70, 69, 34, 33, 35, 32, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1) | ||
| 354 | #define _trans_cube_RDm_inverse fastcube( \ | ||
| 355 | 71, 69, 68, 70, 33, 35, 34, 32, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23) | ||
| 356 | #define _trans_cube_RBm fastcube( \ | ||
| 357 | 33, 34, 35, 32, 71, 68, 69, 70, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16) | ||
| 358 | #define _trans_cube_RBm_inverse fastcube( \ | ||
| 359 | 67, 64, 65, 66, 37, 38, 39, 36, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19) | ||
| 360 | #define _trans_cube_LUm fastcube( \ | ||
| 361 | 69, 70, 68, 71, 32, 35, 33, 34, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2) | ||
| 362 | #define _trans_cube_LUm_inverse fastcube( \ | ||
| 363 | 68, 70, 71, 69, 34, 32, 33, 35, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20) | ||
| 364 | #define _trans_cube_LFm fastcube( \ | ||
| 365 | 32, 35, 34, 33, 70, 69, 68, 71, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17) | ||
| 366 | #define _trans_cube_LFm_inverse fastcube( \ | ||
| 367 | 64, 67, 66, 65, 38, 37, 36, 39, 24, 27, 26, 25, 20, 23, 22, 21, 16, 19, 18, 17) | ||
| 368 | #define _trans_cube_LDm fastcube( \ | ||
| 369 | 70, 69, 71, 68, 35, 32, 34, 33, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0) | ||
| 370 | #define _trans_cube_LDm_inverse fastcube( \ | ||
| 371 | 69, 71, 70, 68, 35, 33, 32, 34, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21) | ||
| 372 | #define _trans_cube_LBm fastcube( \ | ||
| 373 | 35, 32, 33, 34, 69, 70, 71, 68, 27, 24, 25, 26, 23, 20, 21, 22, 18, 17, 16, 19) | ||
| 374 | #define _trans_cube_LBm_inverse fastcube( \ | ||
| 375 | 65, 66, 67, 64, 39, 36, 37, 38, 26, 25, 24, 27, 21, 22, 23, 20, 17, 18, 19, 16) | ||
| 376 | #define _trans_cube_FUm fastcube( \ | ||
| 377 | 64, 66, 65, 67, 36, 38, 37, 39, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7) | ||
| 378 | #define _trans_cube_FUm_inverse fastcube( \ | ||
| 379 | 32, 34, 33, 35, 68, 70, 69, 71, 16, 19, 18, 17, 8, 9, 10, 11, 4, 5, 6, 7) | ||
| 380 | #define _trans_cube_FRm fastcube( \ | ||
| 381 | 36, 38, 39, 37, 66, 64, 65, 67, 9, 8, 11, 10, 16, 19, 18, 17, 21, 22, 23, 20) | ||
| 382 | #define _trans_cube_FRm_inverse fastcube( \ | ||
| 383 | 37, 38, 36, 39, 64, 67, 65, 66, 20, 23, 22, 21, 27, 24, 25, 26, 1, 0, 3, 2) | ||
| 384 | #define _trans_cube_FDm fastcube( \ | ||
| 385 | 66, 64, 67, 65, 38, 36, 39, 37, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5) | ||
| 386 | #define _trans_cube_FDm_inverse fastcube( \ | ||
| 387 | 33, 35, 32, 34, 69, 71, 68, 70, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6) | ||
| 388 | #define _trans_cube_FLm fastcube( \ | ||
| 389 | 38, 36, 37, 39, 64, 66, 67, 65, 8, 9, 10, 11, 19, 16, 17, 18, 23, 20, 21, 22) | ||
| 390 | #define _trans_cube_FLm_inverse fastcube( \ | ||
| 391 | 36, 39, 37, 38, 65, 66, 64, 67, 21, 22, 23, 20, 25, 26, 27, 24, 0, 1, 2, 3) | ||
| 392 | #define _trans_cube_BUm fastcube( \ | ||
| 393 | 65, 67, 64, 66, 37, 39, 36, 38, 17, 18, 19, 16, 10, 11, 8, 9, 5, 4, 7, 6) | ||
| 394 | #define _trans_cube_BUm_inverse fastcube( \ | ||
| 395 | 34, 32, 35, 33, 70, 68, 71, 69, 19, 16, 17, 18, 9, 8, 11, 10, 6, 7, 4, 5) | ||
| 396 | #define _trans_cube_BRm fastcube( \ | ||
| 397 | 39, 37, 36, 38, 65, 67, 66, 64, 10, 11, 8, 9, 18, 17, 16, 19, 22, 21, 20, 23) | ||
| 398 | #define _trans_cube_BRm_inverse fastcube( \ | ||
| 399 | 39, 36, 38, 37, 66, 65, 67, 64, 22, 21, 20, 23, 26, 25, 24, 27, 2, 3, 0, 1) | ||
| 400 | #define _trans_cube_BDm fastcube( \ | ||
| 401 | 67, 65, 66, 64, 39, 37, 38, 36, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4) | ||
| 402 | #define _trans_cube_BDm_inverse fastcube( \ | ||
| 403 | 35, 33, 34, 32, 71, 69, 70, 68, 18, 17, 16, 19, 11, 10, 9, 8, 7, 6, 5, 4) | ||
| 404 | #define _trans_cube_BLm fastcube( \ | ||
| 405 | 37, 39, 38, 36, 67, 65, 64, 66, 11, 10, 9, 8, 17, 18, 19, 16, 20, 23, 22, 21) | ||
| 406 | #define _trans_cube_BLm_inverse fastcube( \ | ||
| 407 | 38, 37, 39, 36, 67, 64, 66, 65, 23, 20, 21, 22, 24, 27, 26, 25, 3, 2, 1, 0) | ||
| 408 | |||
| 409 | _static const char *cornerstr[] = { | ||
| 410 | [_c_ufr] = "UFR", | ||
| 411 | [_c_ubl] = "UBL", | ||
| 412 | [_c_dfl] = "DFL", | ||
| 413 | [_c_dbr] = "DBR", | ||
| 414 | [_c_ufl] = "UFL", | ||
| 415 | [_c_ubr] = "UBR", | ||
| 416 | [_c_dfr] = "DFR", | ||
| 417 | [_c_dbl] = "DBL" | ||
| 418 | }; | ||
| 419 | |||
| 420 | _static const char *cornerstralt[] = { | ||
| 421 | [_c_ufr] = "URF", | ||
| 422 | [_c_ubl] = "ULB", | ||
| 423 | [_c_dfl] = "DLF", | ||
| 424 | [_c_dbr] = "DRB", | ||
| 425 | [_c_ufl] = "ULF", | ||
| 426 | [_c_ubr] = "URB", | ||
| 427 | [_c_dfr] = "DRF", | ||
| 428 | [_c_dbl] = "DLB" | ||
| 429 | }; | ||
| 430 | |||
| 431 | _static const char *edgestr[] = { | ||
| 432 | [_e_uf] = "UF", | ||
| 433 | [_e_ub] = "UB", | ||
| 434 | [_e_db] = "DB", | ||
| 435 | [_e_df] = "DF", | ||
| 436 | [_e_ur] = "UR", | ||
| 437 | [_e_ul] = "UL", | ||
| 438 | [_e_dl] = "DL", | ||
| 439 | [_e_dr] = "DR", | ||
| 440 | [_e_fr] = "FR", | ||
| 441 | [_e_fl] = "FL", | ||
| 442 | [_e_bl] = "BL", | ||
| 443 | [_e_br] = "BR" | ||
| 444 | }; | ||
| 445 | |||
| 446 | _static const char *movestr[] = { | ||
| 447 | [_move_U] = "U", | ||
| 448 | [_move_U2] = "U2", | ||
| 449 | [_move_U3] = "U'", | ||
| 450 | [_move_D] = "D", | ||
| 451 | [_move_D2] = "D2", | ||
| 452 | [_move_D3] = "D'", | ||
| 453 | [_move_R] = "R", | ||
| 454 | [_move_R2] = "R2", | ||
| 455 | [_move_R3] = "R'", | ||
| 456 | [_move_L] = "L", | ||
| 457 | [_move_L2] = "L2", | ||
| 458 | [_move_L3] = "L'", | ||
| 459 | [_move_F] = "F", | ||
| 460 | [_move_F2] = "F2", | ||
| 461 | [_move_F3] = "F'", | ||
| 462 | [_move_B] = "B", | ||
| 463 | [_move_B2] = "B2", | ||
| 464 | [_move_B3] = "B'", | ||
| 465 | }; | ||
| 466 | |||
| 467 | _static const char *transstr[] = { | ||
| 468 | [_trans_UFr] = "rotation UF", | ||
| 469 | [_trans_UFm] = "mirrored UF", | ||
| 470 | [_trans_ULr] = "rotation UL", | ||
| 471 | [_trans_ULm] = "mirrored UL", | ||
| 472 | [_trans_UBr] = "rotation UB", | ||
| 473 | [_trans_UBm] = "mirrored UB", | ||
| 474 | [_trans_URr] = "rotation UR", | ||
| 475 | [_trans_URm] = "mirrored UR", | ||
| 476 | [_trans_DFr] = "rotation DF", | ||
| 477 | [_trans_DFm] = "mirrored DF", | ||
| 478 | [_trans_DLr] = "rotation DL", | ||
| 479 | [_trans_DLm] = "mirrored DL", | ||
| 480 | [_trans_DBr] = "rotation DB", | ||
| 481 | [_trans_DBm] = "mirrored DB", | ||
| 482 | [_trans_DRr] = "rotation DR", | ||
| 483 | [_trans_DRm] = "mirrored DR", | ||
| 484 | [_trans_RUr] = "rotation RU", | ||
| 485 | [_trans_RUm] = "mirrored RU", | ||
| 486 | [_trans_RFr] = "rotation RF", | ||
| 487 | [_trans_RFm] = "mirrored RF", | ||
| 488 | [_trans_RDr] = "rotation RD", | ||
| 489 | [_trans_RDm] = "mirrored RD", | ||
| 490 | [_trans_RBr] = "rotation RB", | ||
| 491 | [_trans_RBm] = "mirrored RB", | ||
| 492 | [_trans_LUr] = "rotation LU", | ||
| 493 | [_trans_LUm] = "mirrored LU", | ||
| 494 | [_trans_LFr] = "rotation LF", | ||
| 495 | [_trans_LFm] = "mirrored LF", | ||
| 496 | [_trans_LDr] = "rotation LD", | ||
| 497 | [_trans_LDm] = "mirrored LD", | ||
| 498 | [_trans_LBr] = "rotation LB", | ||
| 499 | [_trans_LBm] = "mirrored LB", | ||
| 500 | [_trans_FUr] = "rotation FU", | ||
| 501 | [_trans_FUm] = "mirrored FU", | ||
| 502 | [_trans_FRr] = "rotation FR", | ||
| 503 | [_trans_FRm] = "mirrored FR", | ||
| 504 | [_trans_FDr] = "rotation FD", | ||
| 505 | [_trans_FDm] = "mirrored FD", | ||
| 506 | [_trans_FLr] = "rotation FL", | ||
| 507 | [_trans_FLm] = "mirrored FL", | ||
| 508 | [_trans_BUr] = "rotation BU", | ||
| 509 | [_trans_BUm] = "mirrored BU", | ||
| 510 | [_trans_BRr] = "rotation BR", | ||
| 511 | [_trans_BRm] = "mirrored BR", | ||
| 512 | [_trans_BDr] = "rotation BD", | ||
| 513 | [_trans_BDm] = "mirrored BD", | ||
| 514 | [_trans_BLr] = "rotation BL", | ||
| 515 | [_trans_BLm] = "mirrored BL", | ||
| 516 | }; | ||
| 517 | |||
| 518 | static uint8_t inverse_trans_table[48] = { | ||
| 519 | [_trans_UFr] = _trans_UFr, | ||
| 520 | [_trans_UFm] = _trans_UFm, | ||
| 521 | [_trans_ULr] = _trans_URr, | ||
| 522 | [_trans_ULm] = _trans_ULm, | ||
| 523 | [_trans_UBr] = _trans_UBr, | ||
| 524 | [_trans_UBm] = _trans_UBm, | ||
| 525 | [_trans_URr] = _trans_ULr, | ||
| 526 | [_trans_URm] = _trans_URm, | ||
| 527 | [_trans_DFr] = _trans_DFr, | ||
| 528 | [_trans_DFm] = _trans_DFm, | ||
| 529 | [_trans_DLr] = _trans_DLr, | ||
| 530 | [_trans_DLm] = _trans_DRm, | ||
| 531 | [_trans_DBr] = _trans_DBr, | ||
| 532 | [_trans_DBm] = _trans_DBm, | ||
| 533 | [_trans_DRr] = _trans_DRr, | ||
| 534 | [_trans_DRm] = _trans_DLm, | ||
| 535 | [_trans_RUr] = _trans_FRr, | ||
| 536 | [_trans_RUm] = _trans_FLm, | ||
| 537 | [_trans_RFr] = _trans_LFr, | ||
| 538 | [_trans_RFm] = _trans_RFm, | ||
| 539 | [_trans_RDr] = _trans_BLr, | ||
| 540 | [_trans_RDm] = _trans_BRm, | ||
| 541 | [_trans_RBr] = _trans_RBr, | ||
| 542 | [_trans_RBm] = _trans_LBm, | ||
| 543 | [_trans_LUr] = _trans_FLr, | ||
| 544 | [_trans_LUm] = _trans_FRm, | ||
| 545 | [_trans_LFr] = _trans_RFr, | ||
| 546 | [_trans_LFm] = _trans_LFm, | ||
| 547 | [_trans_LDr] = _trans_BRr, | ||
| 548 | [_trans_LDm] = _trans_BLm, | ||
| 549 | [_trans_LBr] = _trans_LBr, | ||
| 550 | [_trans_LBm] = _trans_RBm, | ||
| 551 | [_trans_FUr] = _trans_FUr, | ||
| 552 | [_trans_FUm] = _trans_FUm, | ||
| 553 | [_trans_FRr] = _trans_RUr, | ||
| 554 | [_trans_FRm] = _trans_LUm, | ||
| 555 | [_trans_FDr] = _trans_BUr, | ||
| 556 | [_trans_FDm] = _trans_BUm, | ||
| 557 | [_trans_FLr] = _trans_LUr, | ||
| 558 | [_trans_FLm] = _trans_RUm, | ||
| 559 | [_trans_BUr] = _trans_FDr, | ||
| 560 | [_trans_BUm] = _trans_FDm, | ||
| 561 | [_trans_BRr] = _trans_LDr, | ||
| 562 | [_trans_BRm] = _trans_RDm, | ||
| 563 | [_trans_BDr] = _trans_BDr, | ||
| 564 | [_trans_BDm] = _trans_BDm, | ||
| 565 | [_trans_BLr] = _trans_RDr, | ||
| 566 | [_trans_BLm] = _trans_LDm, | ||
| 567 | }; | ||
| 568 | |||
| 569 | /****************************************************************************** | ||
| 570 | Section: AVX2 fast methods | ||
| 571 | |||
| 572 | This section contains performance-critical methods that rely on AVX2 | ||
| 573 | intructions such as routines for moving or transforming the cube. | ||
| 574 | ******************************************************************************/ | ||
| 575 | 26 | ||
| 576 | #if defined(CUBE_AVX2) | 27 | #if defined(CUBE_AVX2) |
| 577 | |||
| 578 | #include <immintrin.h> | 28 | #include <immintrin.h> |
| 579 | 29 | #include "cube_avx2.h" | |
| 580 | typedef __m256i cube_fast_t; | ||
| 581 | |||
| 582 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060) | ||
| 583 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020) | ||
| 584 | #define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707) | ||
| 585 | #define _ep_avx2 _mm256_set_epi64x(0x0F0F0F0F, 0x0F0F0F0F0F0F0F0F, 0, 0) | ||
| 586 | #define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0) | ||
| 587 | |||
| 588 | _static_inline cube_fast_t fastcube( | ||
| 589 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 590 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 591 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 592 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t | ||
| 593 | ); | ||
| 594 | _static cube_fast_t cubetofast(cube_t); | ||
| 595 | _static cube_t fasttocube(cube_fast_t); | ||
| 596 | _static_inline bool equal_fast(cube_fast_t, cube_fast_t); | ||
| 597 | _static_inline bool issolved_fast(cube_fast_t); | ||
| 598 | _static_inline cube_fast_t invertco_fast(cube_fast_t); | ||
| 599 | _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t); | ||
| 600 | |||
| 601 | _static_inline int64_t coord_fast_co(cube_fast_t); | ||
| 602 | _static_inline int64_t coord_fast_csep(cube_fast_t); | ||
| 603 | _static_inline int64_t coord_fast_cocsep(cube_fast_t); | ||
| 604 | _static_inline int64_t coord_fast_eo(cube_fast_t); | ||
| 605 | _static_inline int64_t coord_fast_esep(cube_fast_t); | ||
| 606 | |||
| 607 | _static_inline cube_fast_t | ||
| 608 | fastcube( | ||
| 609 | uint8_t c_ufr, | ||
| 610 | uint8_t c_ubl, | ||
| 611 | uint8_t c_dfl, | ||
| 612 | uint8_t c_dbr, | ||
| 613 | uint8_t c_ufl, | ||
| 614 | uint8_t c_ubr, | ||
| 615 | uint8_t c_dfr, | ||
| 616 | uint8_t c_dbl, | ||
| 617 | |||
| 618 | uint8_t e_uf, | ||
| 619 | uint8_t e_ub, | ||
| 620 | uint8_t e_db, | ||
| 621 | uint8_t e_df, | ||
| 622 | uint8_t e_ur, | ||
| 623 | uint8_t e_ul, | ||
| 624 | uint8_t e_dl, | ||
| 625 | uint8_t e_dr, | ||
| 626 | uint8_t e_fr, | ||
| 627 | uint8_t e_fl, | ||
| 628 | uint8_t e_bl, | ||
| 629 | uint8_t e_br | ||
| 630 | ) | ||
| 631 | { | ||
| 632 | return _mm256_set_epi8( | ||
| 633 | 0, 0, 0, 0, e_br, e_bl, e_fl, e_fr, | ||
| 634 | e_dr, e_dl, e_ul, e_ur, e_df, e_db, e_ub, e_uf, | ||
| 635 | 0, 0, 0, 0, 0, 0, 0, 0, | ||
| 636 | c_dbl, c_dfr, c_ubr, c_ufl, c_dbr, c_dfl, c_ubl, c_ufr | ||
| 637 | ); | ||
| 638 | } | ||
| 639 | |||
| 640 | _static cube_fast_t | ||
| 641 | cubetofast(cube_t a) | ||
| 642 | { | ||
| 643 | uint8_t aux[32]; | ||
| 644 | |||
| 645 | memset(aux, 0, 32); | ||
| 646 | memcpy(aux, &a.corner, 8); | ||
| 647 | memcpy(aux + 16, &a.edge, 12); | ||
| 648 | |||
| 649 | return _mm256_loadu_si256((__m256i_u *)&aux); | ||
| 650 | } | ||
| 651 | |||
| 652 | _static cube_t | ||
| 653 | fasttocube(cube_fast_t c) | ||
| 654 | { | ||
| 655 | cube_t a; | ||
| 656 | uint8_t aux[32]; | ||
| 657 | |||
| 658 | _mm256_storeu_si256((__m256i_u *)aux, c); | ||
| 659 | memcpy(&a.corner, aux, 8); | ||
| 660 | memcpy(&a.edge, aux + 16, 12); | ||
| 661 | |||
| 662 | return a; | ||
| 663 | } | ||
| 664 | |||
| 665 | _static_inline bool | ||
| 666 | equal_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 667 | { | ||
| 668 | int32_t mask; | ||
| 669 | __m256i cmp; | ||
| 670 | |||
| 671 | cmp = _mm256_cmpeq_epi8(c1, c2); | ||
| 672 | mask = _mm256_movemask_epi8(cmp); | ||
| 673 | |||
| 674 | return mask == ~0; | ||
| 675 | } | ||
| 676 | |||
| 677 | _static_inline bool | ||
| 678 | issolved_fast(cube_fast_t cube) | ||
| 679 | { | ||
| 680 | return equal_fast(cube, solved_fast); | ||
| 681 | } | ||
| 682 | |||
| 683 | _static_inline cube_fast_t | ||
| 684 | invertco_fast(cube_fast_t c) | ||
| 685 | { | ||
| 686 | cube_fast_t co, shleft, shright, summed, newco, cleanco, ret; | ||
| 687 | |||
| 688 | co = _mm256_and_si256(c, _co2_avx2); | ||
| 689 | shleft = _mm256_slli_epi32(co, 1); | ||
| 690 | shright = _mm256_srli_epi32(co, 1); | ||
| 691 | summed = _mm256_or_si256(shleft, shright); | ||
| 692 | newco = _mm256_and_si256(summed, _co2_avx2); | ||
| 693 | cleanco = _mm256_xor_si256(c, co); | ||
| 694 | ret = _mm256_or_si256(cleanco, newco); | ||
| 695 | |||
| 696 | return ret; | ||
| 697 | } | ||
| 698 | |||
| 699 | _static_inline cube_fast_t | ||
| 700 | compose_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 701 | { | ||
| 702 | cube_fast_t s, b, eo2, co1, co2, aux, auy1, auy2, auz1, auz2; | ||
| 703 | |||
| 704 | /* Permute and clean unused bits */ | ||
| 705 | s = _mm256_shuffle_epi8(c1, c2); | ||
| 706 | b = _mm256_set_epi8( | ||
| 707 | ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||
| 708 | ~0, ~0, ~0, ~0, ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0 | ||
| 709 | ); | ||
| 710 | s = _mm256_andnot_si256(b, s); | ||
| 711 | |||
| 712 | /* Change EO */ | ||
| 713 | eo2 = _mm256_and_si256(c2, _eo_avx2); | ||
| 714 | s = _mm256_xor_si256(s, eo2); | ||
| 715 | |||
| 716 | /* Change CO */ | ||
| 717 | co1 = _mm256_and_si256(s, _co2_avx2); | ||
| 718 | co2 = _mm256_and_si256(c2, _co2_avx2); | ||
| 719 | aux = _mm256_add_epi8(co1, co2); | ||
| 720 | auy1 = _mm256_add_epi8(aux, _cocw_avx2); | ||
| 721 | auy2 = _mm256_srli_epi32(auy1, 2); | ||
| 722 | auz1 = _mm256_add_epi8(aux, auy2); | ||
| 723 | auz2 = _mm256_and_si256(auz1, _co2_avx2); | ||
| 724 | |||
| 725 | /* Put together */ | ||
| 726 | s = _mm256_andnot_si256(_co2_avx2, s); | ||
| 727 | s = _mm256_or_si256(s, auz2); | ||
| 728 | |||
| 729 | return s; | ||
| 730 | } | ||
| 731 | |||
| 732 | _static_inline int64_t | ||
| 733 | coord_fast_co(cube_fast_t c) | ||
| 734 | { | ||
| 735 | cube_fast_t co; | ||
| 736 | int64_t mem[4], ret, i, p; | ||
| 737 | |||
| 738 | co = _mm256_and_si256(c, _co2_avx2); | ||
| 739 | _mm256_storeu_si256((__m256i *)mem, co); | ||
| 740 | |||
| 741 | mem[0] >>= 5L; | ||
| 742 | for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8L, p *= 3) | ||
| 743 | ret += (mem[0] & 3L) * p; | ||
| 744 | |||
| 745 | return ret; | ||
| 746 | } | ||
| 747 | |||
| 748 | _static_inline int64_t | ||
| 749 | coord_fast_csep(cube_fast_t c) | ||
| 750 | { | ||
| 751 | cube_fast_t cp, shifted; | ||
| 752 | int64_t mask; | ||
| 753 | |||
| 754 | cp = _mm256_and_si256(c, _cp_avx2); | ||
| 755 | shifted = _mm256_slli_epi32(cp, 5); | ||
| 756 | mask = _mm256_movemask_epi8(shifted); | ||
| 757 | |||
| 758 | return mask & 0x7F; | ||
| 759 | } | ||
| 760 | |||
| 761 | _static_inline int64_t | ||
| 762 | coord_fast_cocsep(cube_fast_t c) | ||
| 763 | { | ||
| 764 | return (coord_fast_co(c) << 7) + coord_fast_csep(c); | ||
| 765 | } | ||
| 766 | |||
| 767 | _static_inline int64_t | ||
| 768 | coord_fast_eo(cube_fast_t c) | ||
| 769 | { | ||
| 770 | cube_fast_t eo, shifted; | ||
| 771 | int64_t mask; | ||
| 772 | |||
| 773 | eo = _mm256_and_si256(c, _eo_avx2); | ||
| 774 | shifted = _mm256_slli_epi32(eo, 3); | ||
| 775 | mask = _mm256_movemask_epi8(shifted); | ||
| 776 | |||
| 777 | return mask >> 17; | ||
| 778 | } | ||
| 779 | |||
| 780 | _static_inline int64_t | ||
| 781 | coord_fast_esep(cube_fast_t c) | ||
| 782 | { | ||
| 783 | cube_fast_t ep; | ||
| 784 | int64_t e, mem[4], i, j, k, l, ret1, ret2, bit1, bit2, is1; | ||
| 785 | |||
| 786 | ep = _mm256_and_si256(c, _ep_avx2); | ||
| 787 | _mm256_storeu_si256((__m256i *)mem, ep); | ||
| 788 | |||
| 789 | mem[3] <<= 8L; | ||
| 790 | ret1 = ret2 = 0; | ||
| 791 | k = l = 4; | ||
| 792 | for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8L) { | ||
| 793 | e = mem[i/8 + 2]; | ||
| 794 | |||
| 795 | bit1 = (e & _esepbit1) >> 2L; | ||
| 796 | bit2 = (e & _esepbit2) >> 3L; | ||
| 797 | is1 = (1 - bit2) * bit1; | ||
| 798 | |||
| 799 | ret1 += bit2 * binomial[11-i][k]; | ||
| 800 | k -= bit2; | ||
| 801 | |||
| 802 | ret2 += is1 * binomial[7-j][l]; | ||
| 803 | l -= is1; | ||
| 804 | j += (1-bit2); | ||
| 805 | } | ||
| 806 | |||
| 807 | return ret1 * 70 + ret2; | ||
| 808 | } | ||
| 809 | |||
| 810 | /****************************************************************************** | ||
| 811 | Section: ARM NEON fast methods | ||
| 812 | |||
| 813 | This section contains performance-critical methods that rely on ARM NEON | ||
| 814 | intructions such as routines for moving or transforming the cube. | ||
| 815 | ******************************************************************************/ | ||
| 816 | |||
| 817 | #elif defined(CUBE_NEON) | 30 | #elif defined(CUBE_NEON) |
| 818 | 31 | #include "cube_neon.h" | |
| 819 | typedef struct { | ||
| 820 | uint8x16_t corner; | ||
| 821 | uint8x16_t edge; | ||
| 822 | } cube_fast_t; | ||
| 823 | |||
| 824 | /* TODO! */ | ||
| 825 | |||
| 826 | /****************************************************************************** | ||
| 827 | Section: portable fast methods | ||
| 828 | |||
| 829 | This section contains performance-critical methods that do not use | ||
| 830 | advanced CPU instructions. They are used as an alternative to the ones | ||
| 831 | in the previous section(s) for unsupported architectures. | ||
| 832 | ******************************************************************************/ | ||
| 833 | |||
| 834 | #else | 32 | #else |
| 835 | 33 | #include "cube_portable.h" | |
| 836 | typedef cube_t cube_fast_t; | ||
| 837 | |||
| 838 | _static_inline cube_fast_t fastcube( | ||
| 839 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 840 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 841 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 842 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t | ||
| 843 | ); | ||
| 844 | _static cube_fast_t cubetofast(cube_t); | ||
| 845 | _static cube_t fasttocube(cube_fast_t); | ||
| 846 | _static_inline bool equal_fast(cube_fast_t, cube_fast_t); | ||
| 847 | _static_inline bool issolved_fast(cube_fast_t); | ||
| 848 | _static_inline cube_fast_t invertco_fast(cube_fast_t); | ||
| 849 | _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t); | ||
| 850 | |||
| 851 | _static_inline int64_t coord_fast_co(cube_fast_t); | ||
| 852 | _static_inline int64_t coord_fast_csep(cube_fast_t); | ||
| 853 | _static_inline int64_t coord_fast_cocsep(cube_fast_t); | ||
| 854 | _static_inline int64_t coord_fast_eo(cube_fast_t); | ||
| 855 | _static_inline int64_t coord_fast_esep(cube_fast_t); | ||
| 856 | |||
| 857 | _static_inline cube_fast_t | ||
| 858 | fastcube( | ||
| 859 | uint8_t c_ufr, | ||
| 860 | uint8_t c_ubl, | ||
| 861 | uint8_t c_dfl, | ||
| 862 | uint8_t c_dbr, | ||
| 863 | uint8_t c_ufl, | ||
| 864 | uint8_t c_ubr, | ||
| 865 | uint8_t c_dfr, | ||
| 866 | uint8_t c_dbl, | ||
| 867 | |||
| 868 | uint8_t e_uf, | ||
| 869 | uint8_t e_ub, | ||
| 870 | uint8_t e_db, | ||
| 871 | uint8_t e_df, | ||
| 872 | uint8_t e_ur, | ||
| 873 | uint8_t e_ul, | ||
| 874 | uint8_t e_dl, | ||
| 875 | uint8_t e_dr, | ||
| 876 | uint8_t e_fr, | ||
| 877 | uint8_t e_fl, | ||
| 878 | uint8_t e_bl, | ||
| 879 | uint8_t e_br | ||
| 880 | ) | ||
| 881 | { | ||
| 882 | cube_fast_t cube = { | ||
| 883 | .corner = { | ||
| 884 | c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl | ||
| 885 | }, | ||
| 886 | .edge = { | ||
| 887 | e_uf, e_ub, e_db, e_df, e_ur, e_ul, | ||
| 888 | e_dl, e_dr, e_fr, e_fl, e_bl, e_br | ||
| 889 | } | ||
| 890 | }; | ||
| 891 | |||
| 892 | return cube; | ||
| 893 | } | ||
| 894 | |||
| 895 | _static cube_fast_t | ||
| 896 | cubetofast(cube_t cube) | ||
| 897 | { | ||
| 898 | cube_fast_t fast; | ||
| 899 | memcpy(&fast, &cube, sizeof(cube_fast_t)); | ||
| 900 | return fast; | ||
| 901 | } | ||
| 902 | |||
| 903 | _static cube_t | ||
| 904 | fasttocube(cube_fast_t fast) | ||
| 905 | { | ||
| 906 | cube_t cube; | ||
| 907 | memcpy(&cube, &fast, sizeof(cube_fast_t)); | ||
| 908 | return cube; | ||
| 909 | } | ||
| 910 | |||
| 911 | _static_inline bool | ||
| 912 | equal_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 913 | { | ||
| 914 | uint8_t i; | ||
| 915 | bool ret; | ||
| 916 | |||
| 917 | ret = true; | ||
| 918 | for (i = 0; i < 8; i++) | ||
| 919 | ret = ret && c1.corner[i] == c2.corner[i]; | ||
| 920 | for (i = 0; i < 12; i++) | ||
| 921 | ret = ret && c1.edge[i] == c2.edge[i]; | ||
| 922 | |||
| 923 | return ret; | ||
| 924 | } | ||
| 925 | |||
| 926 | _static_inline bool | ||
| 927 | issolved_fast(cube_fast_t cube) | ||
| 928 | { | ||
| 929 | return equal_fast(cube, solved_fast); | ||
| 930 | } | ||
| 931 | |||
| 932 | _static_inline cube_fast_t | ||
| 933 | invertco_fast(cube_fast_t c) | ||
| 934 | { | ||
| 935 | uint8_t i, piece, orien; | ||
| 936 | cube_fast_t ret; | ||
| 937 | |||
| 938 | ret = c; | ||
| 939 | for (i = 0; i < 8; i++) { | ||
| 940 | piece = c.corner[i]; | ||
| 941 | orien = ((piece << 1) | (piece >> 1)) & _cobits2; | ||
| 942 | ret.corner[i] = (piece & _pbits) | orien; | ||
| 943 | } | ||
| 944 | |||
| 945 | return ret; | ||
| 946 | } | ||
| 947 | |||
| 948 | _static_inline cube_fast_t | ||
| 949 | compose_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 950 | { | ||
| 951 | cube_fast_t ret; | ||
| 952 | uint8_t i, piece1, piece2, p, orien, aux, auy; | ||
| 953 | |||
| 954 | ret = zero_fast; | ||
| 955 | |||
| 956 | for (i = 0; i < 12; i++) { | ||
| 957 | piece2 = c2.edge[i]; | ||
| 958 | p = piece2 & _pbits; | ||
| 959 | piece1 = c1.edge[p]; | ||
| 960 | orien = (piece2 ^ piece1) & _eobit; | ||
| 961 | ret.edge[i] = (piece1 & _pbits) | orien; | ||
| 962 | } | ||
| 963 | |||
| 964 | for (i = 0; i < 8; i++) { | ||
| 965 | piece2 = c2.corner[i]; | ||
| 966 | p = piece2 & _pbits; | ||
| 967 | piece1 = c1.corner[p]; | ||
| 968 | aux = (piece2 & _cobits) + (piece1 & _cobits); | ||
| 969 | auy = (aux + _ctwist_cw) >> 2U; | ||
| 970 | orien = (aux + auy) & _cobits2; | ||
| 971 | ret.corner[i] = (piece1 & _pbits) | orien; | ||
| 972 | } | ||
| 973 | |||
| 974 | return ret; | ||
| 975 | } | ||
| 976 | |||
| 977 | _static_inline int64_t | ||
| 978 | coord_fast_co(cube_fast_t c) | ||
| 979 | { | ||
| 980 | int i, p; | ||
| 981 | int64_t ret; | ||
| 982 | |||
| 983 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3) | ||
| 984 | ret += p * (c.corner[i] >> _coshift); | ||
| 985 | |||
| 986 | return ret; | ||
| 987 | } | ||
| 988 | |||
| 989 | /* | ||
| 990 | For corner separation, we consider the axis (a.k.a. tetrad) each | ||
| 991 | corner belongs to as 0 or 1 and we translate this sequence into binary. | ||
| 992 | Ignoring the last bit, we have a value up to 2^7, but not all values are | ||
| 993 | possible. Encoding this as a number from 0 to C(8,4) would save about 40% | ||
| 994 | of space, but we are not going to use this coordinate in large tables. | ||
| 995 | */ | ||
| 996 | _static_inline int64_t | ||
| 997 | coord_fast_csep(cube_fast_t c) | ||
| 998 | { | ||
| 999 | int i, p; | ||
| 1000 | int64_t ret; | ||
| 1001 | |||
| 1002 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2) | ||
| 1003 | ret += p * ((c.corner[i] & _csepbit) >> 2U); | ||
| 1004 | |||
| 1005 | return ret; | ||
| 1006 | } | ||
| 1007 | |||
| 1008 | _static_inline int64_t | ||
| 1009 | coord_fast_cocsep(cube_fast_t c) | ||
| 1010 | { | ||
| 1011 | return (coord_fast_co(c) << 7) + coord_fast_csep(c); | ||
| 1012 | } | ||
| 1013 | |||
| 1014 | _static_inline int64_t | ||
| 1015 | coord_fast_eo(cube_fast_t c) | ||
| 1016 | { | ||
| 1017 | int i, p; | ||
| 1018 | int64_t ret; | ||
| 1019 | |||
| 1020 | for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2) | ||
| 1021 | ret += p * (c.edge[i] >> _eoshift); | ||
| 1022 | |||
| 1023 | return ret; | ||
| 1024 | } | ||
| 1025 | |||
| 1026 | /* | ||
| 1027 | We encode the edge separation as a number from 0 to C(12,4)*C(8,4). | ||
| 1028 | It can be seen as the composition of two "subset index" coordinates. | ||
| 1029 | */ | ||
| 1030 | _static_inline int64_t | ||
| 1031 | coord_fast_esep(cube_fast_t c) | ||
| 1032 | { | ||
| 1033 | int64_t i, j, k, l, ret1, ret2, bit1, bit2, is1; | ||
| 1034 | |||
| 1035 | for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) { | ||
| 1036 | /* Simple version: | ||
| 1037 | if (c.edge[i] & _esepbit2) { | ||
| 1038 | ret1 += binomial[11-i][k--]; | ||
| 1039 | } else { | ||
| 1040 | if (c.edge[i] & _esepbit1) | ||
| 1041 | ret2 += binomial[7-j][l--]; | ||
| 1042 | j++; | ||
| 1043 | } | ||
| 1044 | */ | ||
| 1045 | |||
| 1046 | bit1 = (c.edge[i] & _esepbit1) >> 2U; | ||
| 1047 | bit2 = (c.edge[i] & _esepbit2) >> 3U; | ||
| 1048 | is1 = (1 - bit2) * bit1; | ||
| 1049 | |||
| 1050 | ret1 += bit2 * binomial[11-i][k]; | ||
| 1051 | k -= bit2; | ||
| 1052 | |||
| 1053 | ret2 += is1 * binomial[7-j][l]; | ||
| 1054 | l -= is1; | ||
| 1055 | j += (1-bit2); | ||
| 1056 | } | ||
| 1057 | |||
| 1058 | return ret1 * 70 + ret2; | ||
| 1059 | } | ||
| 1060 | |||
| 1061 | #endif | 34 | #endif |
| 1062 | 35 | ||
| 1063 | /****************************************************************************** | 36 | #include "cube_routines.h" |
| 1064 | Section: generic methods | 37 | #include "moves.h" |
| 1065 | 38 | #include "solve_h48.h" | |
| 1066 | This section contains generic functionality, including the public functions. | 39 | #include "solve_generic.h" |
| 1067 | Some of these routines depend on the efficient functions implemented in the | ||
| 1068 | previous sections, while some other operate directly on the cube. | ||
| 1069 | ******************************************************************************/ | ||
| 1070 | |||
| 1071 | #define _move(M, c) compose_fast(c, _move_cube_ ## M) | ||
| 1072 | #define _premove(M, c) compose_fast(_move_cube_ ## M, c) | ||
| 1073 | #define _trans_rotation(T, c) \ | ||
| 1074 | compose_fast(compose_fast(_trans_cube_ ## T, c), \ | ||
| 1075 | _trans_cube_ ## T ## _inverse) | ||
| 1076 | #define _trans_mirrored(T, c) \ | ||
| 1077 | invertco_fast(compose_fast(compose_fast(_trans_cube_ ## T, c), \ | ||
| 1078 | _trans_cube_ ## T ## _inverse)) | ||
| 1079 | |||
| 1080 | _static int permsign(uint8_t *, int); | ||
| 1081 | _static uint8_t readco(const char *); | ||
| 1082 | _static uint8_t readcp(const char *); | ||
| 1083 | _static uint8_t readeo(const char *); | ||
| 1084 | _static uint8_t readep(const char *); | ||
| 1085 | _static cube_t readcube_H48(const char *); | ||
| 1086 | _static uint8_t readpiece_LST(const char **); | ||
| 1087 | _static cube_t readcube_LST(const char *); | ||
| 1088 | _static int writepiece_LST(uint8_t, char *); | ||
| 1089 | _static void writecube_H48(cube_t, char *); | ||
| 1090 | _static void writecube_LST(cube_t, char *); | ||
| 1091 | _static uint8_t readmove(char); | ||
| 1092 | _static uint8_t readmodifier(char); | ||
| 1093 | _static uint8_t readtrans(const char *); | ||
| 1094 | _static int writemoves(uint8_t *, int, char *); | ||
| 1095 | _static void writetrans(uint8_t, char *); | ||
| 1096 | _static cube_fast_t move(cube_fast_t, uint8_t); | ||
| 1097 | _static cube_fast_t transform(cube_fast_t, uint8_t); | ||
| 1098 | |||
| 1099 | _static_inline int64_t coord_h48(cube_fast_t, uint32_t *, uint8_t); | ||
| 1100 | |||
| 1101 | cube_t | ||
| 1102 | solvedcube(void) | ||
| 1103 | { | ||
| 1104 | return solved; | ||
| 1105 | } | ||
| 1106 | |||
| 1107 | bool | ||
| 1108 | isconsistent(cube_t cube) | ||
| 1109 | { | ||
| 1110 | uint8_t i, p, e, piece; | ||
| 1111 | bool found[12]; | ||
| 1112 | |||
| 1113 | for (i = 0; i < 12; i++) | ||
| 1114 | found[i] = false; | ||
| 1115 | for (i = 0; i < 12; i++) { | ||
| 1116 | piece = cube.edge[i]; | ||
| 1117 | p = piece & _pbits; | ||
| 1118 | e = piece & _eobit; | ||
| 1119 | if (p >= 12) | ||
| 1120 | goto inconsistent_ep; | ||
| 1121 | if (e != 0 && e != _eobit) | ||
| 1122 | goto inconsistent_eo; | ||
| 1123 | found[p] = true; | ||
| 1124 | } | ||
| 1125 | for (i = 0; i < 12; i++) | ||
| 1126 | if (!found[i]) | ||
| 1127 | goto inconsistent_ep; | ||
| 1128 | |||
| 1129 | for (i = 0; i < 8; i++) | ||
| 1130 | found[i] = false; | ||
| 1131 | for (i = 0; i < 8; i++) { | ||
| 1132 | piece = cube.corner[i]; | ||
| 1133 | p = piece & _pbits; | ||
| 1134 | e = piece & _cobits; | ||
| 1135 | if (p >= 8) | ||
| 1136 | goto inconsistent_cp; | ||
| 1137 | if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw) | ||
| 1138 | goto inconsistent_co; | ||
| 1139 | found[p] = true; | ||
| 1140 | } | ||
| 1141 | for (i = 0; i < 8; i++) | ||
| 1142 | if (!found[i]) | ||
| 1143 | goto inconsistent_co; | ||
| 1144 | |||
| 1145 | return true; | ||
| 1146 | |||
| 1147 | inconsistent_ep: | ||
| 1148 | DBG_LOG("Inconsistent EP\n"); | ||
| 1149 | return false; | ||
| 1150 | inconsistent_cp: | ||
| 1151 | DBG_LOG("Inconsistent CP\n"); | ||
| 1152 | return false; | ||
| 1153 | inconsistent_eo: | ||
| 1154 | DBG_LOG("Inconsistent EO\n"); | ||
| 1155 | return false; | ||
| 1156 | inconsistent_co: | ||
| 1157 | DBG_LOG("Inconsistent CO\n"); | ||
| 1158 | return false; | ||
| 1159 | } | ||
| 1160 | |||
| 1161 | bool | ||
| 1162 | issolvable(cube_t cube) | ||
| 1163 | { | ||
| 1164 | uint8_t i, eo, co, piece, edges[12], corners[8]; | ||
| 1165 | |||
| 1166 | DBG_ASSERT(isconsistent(cube), false, | ||
| 1167 | "issolvable: cube is inconsistent\n"); | ||
| 1168 | |||
| 1169 | for (i = 0; i < 12; i++) | ||
| 1170 | edges[i] = cube.edge[i] & _pbits; | ||
| 1171 | for (i = 0; i < 8; i++) | ||
| 1172 | corners[i] = cube.corner[i] & _pbits; | ||
| 1173 | |||
| 1174 | if (permsign(edges, 12) != permsign(corners, 8)) | ||
| 1175 | goto issolvable_parity; | ||
| 1176 | |||
| 1177 | eo = 0; | ||
| 1178 | for (i = 0; i < 12; i++) { | ||
| 1179 | piece = cube.edge[i]; | ||
| 1180 | eo += (piece & _eobit) >> _eoshift; | ||
| 1181 | } | ||
| 1182 | if (eo % 2 != 0) | ||
| 1183 | goto issolvable_eo; | ||
| 1184 | |||
| 1185 | co = 0; | ||
| 1186 | for (i = 0; i < 8; i++) { | ||
| 1187 | piece = cube.corner[i]; | ||
| 1188 | co += (piece & _cobits) >> _coshift; | ||
| 1189 | } | ||
| 1190 | if (co % 3 != 0) | ||
| 1191 | goto issolvable_co; | ||
| 1192 | |||
| 1193 | return true; | ||
| 1194 | |||
| 1195 | issolvable_parity: | ||
| 1196 | DBG_LOG("EP and CP parities are different\n"); | ||
| 1197 | return false; | ||
| 1198 | issolvable_eo: | ||
| 1199 | DBG_LOG("Odd number of flipped edges\n"); | ||
| 1200 | return false; | ||
| 1201 | issolvable_co: | ||
| 1202 | DBG_LOG("Sum of corner orientation is not multiple of 3\n"); | ||
| 1203 | return false; | ||
| 1204 | } | ||
| 1205 | |||
| 1206 | bool | ||
| 1207 | issolved(cube_t cube) | ||
| 1208 | { | ||
| 1209 | return equal(cube, solved); | ||
| 1210 | } | ||
| 1211 | |||
| 1212 | bool | ||
| 1213 | equal(cube_t c1, cube_t c2) | ||
| 1214 | { | ||
| 1215 | int i; | ||
| 1216 | bool ret; | ||
| 1217 | |||
| 1218 | ret = true; | ||
| 1219 | for (i = 0; i < 8; i++) | ||
| 1220 | ret = ret && c1.corner[i] == c2.corner[i]; | ||
| 1221 | for (i = 0; i < 12; i++) | ||
| 1222 | ret = ret && c1.edge[i] == c2.edge[i]; | ||
| 1223 | |||
| 1224 | return ret; | ||
| 1225 | } | ||
| 1226 | |||
| 1227 | bool | ||
| 1228 | iserror(cube_t cube) | ||
| 1229 | { | ||
| 1230 | return equal(cube, zero); | ||
| 1231 | } | ||
| 1232 | |||
| 1233 | cube_t | ||
| 1234 | compose(cube_t c1, cube_t c2) | ||
| 1235 | { | ||
| 1236 | DBG_ASSERT(isconsistent(c1) && isconsistent(c2), | ||
| 1237 | zero, "compose error: inconsistent cube\n") | ||
| 1238 | |||
| 1239 | return fasttocube(compose_fast(cubetofast(c1), cubetofast(c2))); | ||
| 1240 | } | ||
| 1241 | |||
| 1242 | cube_t | ||
| 1243 | inverse(cube_t cube) | ||
| 1244 | { | ||
| 1245 | cube_t ret; | ||
| 1246 | uint8_t i, piece, orien; | ||
| 1247 | |||
| 1248 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 1249 | "inverse error: inconsistent cube\n"); | ||
| 1250 | |||
| 1251 | ret = zero; | ||
| 1252 | |||
| 1253 | for (i = 0; i < 12; i++) { | ||
| 1254 | piece = cube.edge[i]; | ||
| 1255 | orien = piece & _eobit; | ||
| 1256 | ret.edge[piece & _pbits] = i | orien; | ||
| 1257 | } | ||
| 1258 | |||
| 1259 | for (i = 0; i < 8; i++) { | ||
| 1260 | piece = cube.corner[i]; | ||
| 1261 | orien = ((piece << 1) | (piece >> 1)) & _cobits2; | ||
| 1262 | ret.corner[piece & _pbits] = i | orien; | ||
| 1263 | } | ||
| 1264 | |||
| 1265 | return ret; | ||
| 1266 | } | ||
| 1267 | |||
| 1268 | cube_t | ||
| 1269 | applymoves(cube_t cube, const char *buf) | ||
| 1270 | { | ||
| 1271 | cube_fast_t fast; | ||
| 1272 | uint8_t r, m; | ||
| 1273 | const char *b; | ||
| 1274 | |||
| 1275 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 1276 | "move error: inconsistent cube\n"); | ||
| 1277 | |||
| 1278 | fast = cubetofast(cube); | ||
| 1279 | |||
| 1280 | for (b = buf; *b != '\0'; b++) { | ||
| 1281 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 1282 | b++; | ||
| 1283 | if (*b == '\0') | ||
| 1284 | goto applymoves_finish; | ||
| 1285 | if ((r = readmove(*b)) == _error) | ||
| 1286 | goto applymoves_error; | ||
| 1287 | if ((m = readmodifier(*(b+1))) != 0) | ||
| 1288 | b++; | ||
| 1289 | fast = move(fast, r + m); | ||
| 1290 | } | ||
| 1291 | |||
| 1292 | applymoves_finish: | ||
| 1293 | return fasttocube(fast); | ||
| 1294 | |||
| 1295 | applymoves_error: | ||
| 1296 | DBG_LOG("applymoves error\n"); | ||
| 1297 | return zero; | ||
| 1298 | } | ||
| 1299 | |||
| 1300 | cube_t | ||
| 1301 | applytrans(cube_t cube, const char *buf) | ||
| 1302 | { | ||
| 1303 | cube_fast_t fast; | ||
| 1304 | uint8_t t; | ||
| 1305 | |||
| 1306 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 1307 | "transformation error: inconsistent cube\n"); | ||
| 1308 | |||
| 1309 | t = readtrans(buf); | ||
| 1310 | fast = cubetofast(cube); | ||
| 1311 | fast = transform(fast, t); | ||
| 1312 | |||
| 1313 | return fasttocube(fast); | ||
| 1314 | } | ||
| 1315 | |||
| 1316 | cube_t | ||
| 1317 | readcube(const char *format, const char *buf) | ||
| 1318 | { | ||
| 1319 | cube_t cube; | ||
| 1320 | |||
| 1321 | if (!strcmp(format, "H48")) { | ||
| 1322 | cube = readcube_H48(buf); | ||
| 1323 | } else if (!strcmp(format, "LST")) { | ||
| 1324 | cube = readcube_LST(buf); | ||
| 1325 | } else { | ||
| 1326 | DBG_LOG("Cannot read cube in the given format\n"); | ||
| 1327 | cube = zero; | ||
| 1328 | } | ||
| 1329 | |||
| 1330 | return cube; | ||
| 1331 | } | ||
| 1332 | |||
| 1333 | void | ||
| 1334 | writecube(const char *format, cube_t cube, char *buf) | ||
| 1335 | { | ||
| 1336 | char *errormsg; | ||
| 1337 | size_t len; | ||
| 1338 | |||
| 1339 | if (!isconsistent(cube)) { | ||
| 1340 | errormsg = "ERROR: cannot write inconsistent cube"; | ||
| 1341 | goto writecube_error; | ||
| 1342 | } | ||
| 1343 | |||
| 1344 | if (!strcmp(format, "H48")) { | ||
| 1345 | writecube_H48(cube, buf); | ||
| 1346 | } else if (!strcmp(format, "LST")) { | ||
| 1347 | writecube_LST(cube, buf); | ||
| 1348 | } else { | ||
| 1349 | errormsg = "ERROR: cannot write cube in the given format"; | ||
| 1350 | goto writecube_error; | ||
| 1351 | } | ||
| 1352 | |||
| 1353 | return; | ||
| 1354 | |||
| 1355 | writecube_error: | ||
| 1356 | DBG_LOG("writecube error, see stdout for details\n"); | ||
| 1357 | len = strlen(errormsg); | ||
| 1358 | memcpy(buf, errormsg, len); | ||
| 1359 | buf[len] = '\n'; | ||
| 1360 | buf[len+1] = '\0'; | ||
| 1361 | } | ||
| 1362 | |||
| 1363 | _static int | ||
| 1364 | permsign(uint8_t *a, int n) | ||
| 1365 | { | ||
| 1366 | int i, j; | ||
| 1367 | uint8_t ret = 0; | ||
| 1368 | |||
| 1369 | for (i = 0; i < n; i++) | ||
| 1370 | for (j = i+1; j < n; j++) | ||
| 1371 | ret += a[i] > a[j] ? 1 : 0; | ||
| 1372 | |||
| 1373 | return ret % 2; | ||
| 1374 | } | ||
| 1375 | |||
| 1376 | _static uint8_t | ||
| 1377 | readco(const char *str) | ||
| 1378 | { | ||
| 1379 | if (*str == '0') | ||
| 1380 | return 0; | ||
| 1381 | if (*str == '1') | ||
| 1382 | return _ctwist_cw; | ||
| 1383 | if (*str == '2') | ||
| 1384 | return _ctwist_ccw; | ||
| 1385 | |||
| 1386 | DBG_LOG("Error reading CO\n"); | ||
| 1387 | return _error; | ||
| 1388 | } | ||
| 1389 | |||
| 1390 | _static uint8_t | ||
| 1391 | readcp(const char *str) | ||
| 1392 | { | ||
| 1393 | uint8_t c; | ||
| 1394 | |||
| 1395 | for (c = 0; c < 8; c++) | ||
| 1396 | if (!strncmp(str, cornerstr[c], 3) || | ||
| 1397 | !strncmp(str, cornerstralt[c], 3)) | ||
| 1398 | return c; | ||
| 1399 | |||
| 1400 | DBG_LOG("Error reading CP\n"); | ||
| 1401 | return _error; | ||
| 1402 | } | ||
| 1403 | |||
| 1404 | _static uint8_t | ||
| 1405 | readeo(const char *str) | ||
| 1406 | { | ||
| 1407 | if (*str == '0') | ||
| 1408 | return 0; | ||
| 1409 | if (*str == '1') | ||
| 1410 | return _eflip; | ||
| 1411 | |||
| 1412 | DBG_LOG("Error reading EO\n"); | ||
| 1413 | return _error; | ||
| 1414 | } | ||
| 1415 | |||
| 1416 | _static uint8_t | ||
| 1417 | readep(const char *str) | ||
| 1418 | { | ||
| 1419 | uint8_t e; | ||
| 1420 | |||
| 1421 | for (e = 0; e < 12; e++) | ||
| 1422 | if (!strncmp(str, edgestr[e], 2)) | ||
| 1423 | return e; | ||
| 1424 | |||
| 1425 | DBG_LOG("Error reading EP\n"); | ||
| 1426 | return _error; | ||
| 1427 | } | ||
| 1428 | |||
| 1429 | _static cube_t | ||
| 1430 | readcube_H48(const char *buf) | ||
| 1431 | { | ||
| 1432 | int i; | ||
| 1433 | uint8_t piece, orient; | ||
| 1434 | cube_t ret = {0}; | ||
| 1435 | const char *b; | ||
| 1436 | |||
| 1437 | b = buf; | ||
| 1438 | |||
| 1439 | for (i = 0; i < 12; i++) { | ||
| 1440 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 1441 | b++; | ||
| 1442 | if ((piece = readep(b)) == _error) | ||
| 1443 | return zero; | ||
| 1444 | b += 2; | ||
| 1445 | if ((orient = readeo(b)) == _error) | ||
| 1446 | return zero; | ||
| 1447 | b++; | ||
| 1448 | ret.edge[i] = piece | orient; | ||
| 1449 | } | ||
| 1450 | for (i = 0; i < 8; i++) { | ||
| 1451 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 1452 | b++; | ||
| 1453 | if ((piece = readcp(b)) == _error) | ||
| 1454 | return zero; | ||
| 1455 | b += 3; | ||
| 1456 | if ((orient = readco(b)) == _error) | ||
| 1457 | return zero; | ||
| 1458 | b++; | ||
| 1459 | ret.corner[i] = piece | orient; | ||
| 1460 | } | ||
| 1461 | |||
| 1462 | return ret; | ||
| 1463 | } | ||
| 1464 | |||
| 1465 | _static uint8_t | ||
| 1466 | readpiece_LST(const char **b) | ||
| 1467 | { | ||
| 1468 | uint8_t ret; | ||
| 1469 | bool read; | ||
| 1470 | |||
| 1471 | while (**b == ',' || **b == ' ' || **b == '\t' || **b == '\n') | ||
| 1472 | (*b)++; | ||
| 1473 | |||
| 1474 | for (ret = 0, read = false; **b >= '0' && **b <= '9'; (*b)++) { | ||
| 1475 | read = true; | ||
| 1476 | ret = ret * 10 + (**b) - '0'; | ||
| 1477 | } | ||
| 1478 | |||
| 1479 | return read ? ret : _error; | ||
| 1480 | } | ||
| 1481 | |||
| 1482 | _static cube_t | ||
| 1483 | readcube_LST(const char *buf) | ||
| 1484 | { | ||
| 1485 | int i; | ||
| 1486 | cube_t ret = {0}; | ||
| 1487 | |||
| 1488 | for (i = 0; i < 8; i++) | ||
| 1489 | ret.corner[i] = readpiece_LST(&buf); | ||
| 1490 | |||
| 1491 | for (i = 0; i < 12; i++) | ||
| 1492 | ret.edge[i] = readpiece_LST(&buf); | ||
| 1493 | |||
| 1494 | return ret; | ||
| 1495 | } | ||
| 1496 | |||
| 1497 | _static int | ||
| 1498 | writepiece_LST(uint8_t piece, char *buf) | ||
| 1499 | { | ||
| 1500 | char digits[3]; | ||
| 1501 | int i, len = 0; | ||
| 1502 | |||
| 1503 | while (piece != 0) { | ||
| 1504 | digits[len++] = (piece % 10) + '0'; | ||
| 1505 | piece /= 10; | ||
| 1506 | } | ||
| 1507 | |||
| 1508 | if (len == 0) | ||
| 1509 | digits[len++] = '0'; | ||
| 1510 | |||
| 1511 | for (i = 0; i < len; i++) | ||
| 1512 | buf[i] = digits[len-i-1]; | ||
| 1513 | |||
| 1514 | buf[len] = ','; | ||
| 1515 | buf[len+1] = ' '; | ||
| 1516 | |||
| 1517 | return len+2; | ||
| 1518 | } | ||
| 1519 | |||
| 1520 | _static void | ||
| 1521 | writecube_H48(cube_t cube, char *buf) | ||
| 1522 | { | ||
| 1523 | uint8_t piece, perm, orient; | ||
| 1524 | int i; | ||
| 1525 | |||
| 1526 | for (i = 0; i < 12; i++) { | ||
| 1527 | piece = cube.edge[i]; | ||
| 1528 | perm = piece & _pbits; | ||
| 1529 | orient = (piece & _eobit) >> _eoshift; | ||
| 1530 | buf[4*i ] = edgestr[perm][0]; | ||
| 1531 | buf[4*i + 1] = edgestr[perm][1]; | ||
| 1532 | buf[4*i + 2] = orient + '0'; | ||
| 1533 | buf[4*i + 3] = ' '; | ||
| 1534 | } | ||
| 1535 | for (i = 0; i < 8; i++) { | ||
| 1536 | piece = cube.corner[i]; | ||
| 1537 | perm = piece & _pbits; | ||
| 1538 | orient = (piece & _cobits) >> _coshift; | ||
| 1539 | buf[48 + 5*i ] = cornerstr[perm][0]; | ||
| 1540 | buf[48 + 5*i + 1] = cornerstr[perm][1]; | ||
| 1541 | buf[48 + 5*i + 2] = cornerstr[perm][2]; | ||
| 1542 | buf[48 + 5*i + 3] = orient + '0'; | ||
| 1543 | buf[48 + 5*i + 4] = ' '; | ||
| 1544 | } | ||
| 1545 | |||
| 1546 | buf[48+39] = '\0'; | ||
| 1547 | } | ||
| 1548 | |||
| 1549 | _static void | ||
| 1550 | writecube_LST(cube_t cube, char *buf) | ||
| 1551 | { | ||
| 1552 | int i, ptr; | ||
| 1553 | uint8_t piece; | ||
| 1554 | |||
| 1555 | ptr = 0; | ||
| 1556 | |||
| 1557 | for (i = 0; i < 8; i++) { | ||
| 1558 | piece = cube.corner[i]; | ||
| 1559 | ptr += writepiece_LST(piece, buf + ptr); | ||
| 1560 | } | ||
| 1561 | |||
| 1562 | for (i = 0; i < 12; i++) { | ||
| 1563 | piece = cube.edge[i]; | ||
| 1564 | ptr += writepiece_LST(piece, buf + ptr); | ||
| 1565 | } | ||
| 1566 | |||
| 1567 | *(buf+ptr-2) = 0; | ||
| 1568 | } | ||
| 1569 | |||
| 1570 | _static uint8_t | ||
| 1571 | readmove(char c) | ||
| 1572 | { | ||
| 1573 | switch (c) { | ||
| 1574 | case 'U': | ||
| 1575 | return _move_U; | ||
| 1576 | case 'D': | ||
| 1577 | return _move_D; | ||
| 1578 | case 'R': | ||
| 1579 | return _move_R; | ||
| 1580 | case 'L': | ||
| 1581 | return _move_L; | ||
| 1582 | case 'F': | ||
| 1583 | return _move_F; | ||
| 1584 | case 'B': | ||
| 1585 | return _move_B; | ||
| 1586 | default: | ||
| 1587 | return _error; | ||
| 1588 | } | ||
| 1589 | } | ||
| 1590 | |||
| 1591 | _static uint8_t | ||
| 1592 | readmodifier(char c) | ||
| 1593 | { | ||
| 1594 | switch (c) { | ||
| 1595 | case '1': /* Fallthrough */ | ||
| 1596 | case '2': /* Fallthrough */ | ||
| 1597 | case '3': | ||
| 1598 | return c - '0' - 1; | ||
| 1599 | case '\'': | ||
| 1600 | return 2; | ||
| 1601 | default: | ||
| 1602 | return 0; | ||
| 1603 | } | ||
| 1604 | } | ||
| 1605 | |||
| 1606 | _static uint8_t | ||
| 1607 | readtrans(const char *buf) | ||
| 1608 | { | ||
| 1609 | uint8_t t; | ||
| 1610 | |||
| 1611 | for (t = 0; t < 48; t++) | ||
| 1612 | if (!strncmp(buf, transstr[t], 11)) | ||
| 1613 | return t; | ||
| 1614 | |||
| 1615 | DBG_LOG("readtrans error\n"); | ||
| 1616 | return _error; | ||
| 1617 | } | ||
| 1618 | |||
| 1619 | _static int | ||
| 1620 | writemoves(uint8_t *m, int n, char *buf) | ||
| 1621 | { | ||
| 1622 | int i; | ||
| 1623 | size_t len; | ||
| 1624 | const char *s; | ||
| 1625 | char *b; | ||
| 1626 | |||
| 1627 | for (i = 0, b = buf; i < n; i++, b++) { | ||
| 1628 | s = movestr[m[i]]; | ||
| 1629 | len = strlen(s); | ||
| 1630 | memcpy(b, s, len); | ||
| 1631 | b += len; | ||
| 1632 | *b = ' '; | ||
| 1633 | } | ||
| 1634 | |||
| 1635 | if (b != buf) | ||
| 1636 | b--; /* Remove last space */ | ||
| 1637 | *b = '\0'; | ||
| 1638 | |||
| 1639 | return b - buf; | ||
| 1640 | } | ||
| 1641 | |||
| 1642 | _static void | ||
| 1643 | writetrans(uint8_t t, char *buf) | ||
| 1644 | { | ||
| 1645 | if (t >= 48) | ||
| 1646 | memcpy(buf, "error trans", 11); | ||
| 1647 | else | ||
| 1648 | memcpy(buf, transstr[t], 11); | ||
| 1649 | buf[11] = '\0'; | ||
| 1650 | } | ||
| 1651 | |||
| 1652 | _static cube_fast_t | ||
| 1653 | move(cube_fast_t c, uint8_t m) | ||
| 1654 | { | ||
| 1655 | switch (m) { | ||
| 1656 | case _move_U: | ||
| 1657 | return _move(U, c); | ||
| 1658 | case _move_U2: | ||
| 1659 | return _move(U2, c); | ||
| 1660 | case _move_U3: | ||
| 1661 | return _move(U3, c); | ||
| 1662 | case _move_D: | ||
| 1663 | return _move(D, c); | ||
| 1664 | case _move_D2: | ||
| 1665 | return _move(D2, c); | ||
| 1666 | case _move_D3: | ||
| 1667 | return _move(D3, c); | ||
| 1668 | case _move_R: | ||
| 1669 | return _move(R, c); | ||
| 1670 | case _move_R2: | ||
| 1671 | return _move(R2, c); | ||
| 1672 | case _move_R3: | ||
| 1673 | return _move(R3, c); | ||
| 1674 | case _move_L: | ||
| 1675 | return _move(L, c); | ||
| 1676 | case _move_L2: | ||
| 1677 | return _move(L2, c); | ||
| 1678 | case _move_L3: | ||
| 1679 | return _move(L3, c); | ||
| 1680 | case _move_F: | ||
| 1681 | return _move(F, c); | ||
| 1682 | case _move_F2: | ||
| 1683 | return _move(F2, c); | ||
| 1684 | case _move_F3: | ||
| 1685 | return _move(F3, c); | ||
| 1686 | case _move_B: | ||
| 1687 | return _move(B, c); | ||
| 1688 | case _move_B2: | ||
| 1689 | return _move(B2, c); | ||
| 1690 | case _move_B3: | ||
| 1691 | return _move(B3, c); | ||
| 1692 | default: | ||
| 1693 | DBG_LOG("move error, unknown move\n"); | ||
| 1694 | return zero_fast; | ||
| 1695 | } | ||
| 1696 | } | ||
| 1697 | |||
| 1698 | _static cube_fast_t | ||
| 1699 | transform(cube_fast_t c, uint8_t t) | ||
| 1700 | { | ||
| 1701 | switch (t) { | ||
| 1702 | case _trans_UFr: | ||
| 1703 | return _trans_rotation(UFr, c); | ||
| 1704 | case _trans_ULr: | ||
| 1705 | return _trans_rotation(ULr, c); | ||
| 1706 | case _trans_UBr: | ||
| 1707 | return _trans_rotation(UBr, c); | ||
| 1708 | case _trans_URr: | ||
| 1709 | return _trans_rotation(URr, c); | ||
| 1710 | case _trans_DFr: | ||
| 1711 | return _trans_rotation(DFr, c); | ||
| 1712 | case _trans_DLr: | ||
| 1713 | return _trans_rotation(DLr, c); | ||
| 1714 | case _trans_DBr: | ||
| 1715 | return _trans_rotation(DBr, c); | ||
| 1716 | case _trans_DRr: | ||
| 1717 | return _trans_rotation(DRr, c); | ||
| 1718 | case _trans_RUr: | ||
| 1719 | return _trans_rotation(RUr, c); | ||
| 1720 | case _trans_RFr: | ||
| 1721 | return _trans_rotation(RFr, c); | ||
| 1722 | case _trans_RDr: | ||
| 1723 | return _trans_rotation(RDr, c); | ||
| 1724 | case _trans_RBr: | ||
| 1725 | return _trans_rotation(RBr, c); | ||
| 1726 | case _trans_LUr: | ||
| 1727 | return _trans_rotation(LUr, c); | ||
| 1728 | case _trans_LFr: | ||
| 1729 | return _trans_rotation(LFr, c); | ||
| 1730 | case _trans_LDr: | ||
| 1731 | return _trans_rotation(LDr, c); | ||
| 1732 | case _trans_LBr: | ||
| 1733 | return _trans_rotation(LBr, c); | ||
| 1734 | case _trans_FUr: | ||
| 1735 | return _trans_rotation(FUr, c); | ||
| 1736 | case _trans_FRr: | ||
| 1737 | return _trans_rotation(FRr, c); | ||
| 1738 | case _trans_FDr: | ||
| 1739 | return _trans_rotation(FDr, c); | ||
| 1740 | case _trans_FLr: | ||
| 1741 | return _trans_rotation(FLr, c); | ||
| 1742 | case _trans_BUr: | ||
| 1743 | return _trans_rotation(BUr, c); | ||
| 1744 | case _trans_BRr: | ||
| 1745 | return _trans_rotation(BRr, c); | ||
| 1746 | case _trans_BDr: | ||
| 1747 | return _trans_rotation(BDr, c); | ||
| 1748 | case _trans_BLr: | ||
| 1749 | return _trans_rotation(BLr, c); | ||
| 1750 | case _trans_UFm: | ||
| 1751 | return _trans_mirrored(UFm, c); | ||
| 1752 | case _trans_ULm: | ||
| 1753 | return _trans_mirrored(ULm, c); | ||
| 1754 | case _trans_UBm: | ||
| 1755 | return _trans_mirrored(UBm, c); | ||
| 1756 | case _trans_URm: | ||
| 1757 | return _trans_mirrored(URm, c); | ||
| 1758 | case _trans_DFm: | ||
| 1759 | return _trans_mirrored(DFm, c); | ||
| 1760 | case _trans_DLm: | ||
| 1761 | return _trans_mirrored(DLm, c); | ||
| 1762 | case _trans_DBm: | ||
| 1763 | return _trans_mirrored(DBm, c); | ||
| 1764 | case _trans_DRm: | ||
| 1765 | return _trans_mirrored(DRm, c); | ||
| 1766 | case _trans_RUm: | ||
| 1767 | return _trans_mirrored(RUm, c); | ||
| 1768 | case _trans_RFm: | ||
| 1769 | return _trans_mirrored(RFm, c); | ||
| 1770 | case _trans_RDm: | ||
| 1771 | return _trans_mirrored(RDm, c); | ||
| 1772 | case _trans_RBm: | ||
| 1773 | return _trans_mirrored(RBm, c); | ||
| 1774 | case _trans_LUm: | ||
| 1775 | return _trans_mirrored(LUm, c); | ||
| 1776 | case _trans_LFm: | ||
| 1777 | return _trans_mirrored(LFm, c); | ||
| 1778 | case _trans_LDm: | ||
| 1779 | return _trans_mirrored(LDm, c); | ||
| 1780 | case _trans_LBm: | ||
| 1781 | return _trans_mirrored(LBm, c); | ||
| 1782 | case _trans_FUm: | ||
| 1783 | return _trans_mirrored(FUm, c); | ||
| 1784 | case _trans_FRm: | ||
| 1785 | return _trans_mirrored(FRm, c); | ||
| 1786 | case _trans_FDm: | ||
| 1787 | return _trans_mirrored(FDm, c); | ||
| 1788 | case _trans_FLm: | ||
| 1789 | return _trans_mirrored(FLm, c); | ||
| 1790 | case _trans_BUm: | ||
| 1791 | return _trans_mirrored(BUm, c); | ||
| 1792 | case _trans_BRm: | ||
| 1793 | return _trans_mirrored(BRm, c); | ||
| 1794 | case _trans_BDm: | ||
| 1795 | return _trans_mirrored(BDm, c); | ||
| 1796 | case _trans_BLm: | ||
| 1797 | return _trans_mirrored(BLm, c); | ||
| 1798 | default: | ||
| 1799 | DBG_LOG("transform error, unknown transformation\n"); | ||
| 1800 | return zero_fast; | ||
| 1801 | } | ||
| 1802 | } | ||
| 1803 | |||
| 1804 | /* h is the number of eo bits used */ | ||
| 1805 | _static_inline int64_t | ||
| 1806 | coord_h48(cube_fast_t c, uint32_t *cocsepdata, uint8_t h) | ||
| 1807 | { | ||
| 1808 | cube_fast_t d; | ||
| 1809 | int64_t cocsep, coclass, esep, eo, esize, ret; | ||
| 1810 | uint32_t data; | ||
| 1811 | uint8_t ttrep; | ||
| 1812 | |||
| 1813 | DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n"); | ||
| 1814 | |||
| 1815 | cocsep = coord_fast_cocsep(c); | ||
| 1816 | data = cocsepdata[cocsep]; | ||
| 1817 | coclass = (data & (0xFFFFU << 16U)) >> 16U; | ||
| 1818 | ttrep = (data & (0xFFU << 8U)) >> 8U; | ||
| 1819 | |||
| 1820 | d = transform(c, ttrep); /* TODO: transform only edges */ | ||
| 1821 | esep = coord_fast_esep(d); | ||
| 1822 | eo = coord_fast_eo(d); | ||
| 1823 | |||
| 1824 | esize = (_12c4 * _8c4) << h; | ||
| 1825 | ret = (coclass * esize) + (esep << h) + (eo >> (11-h)); | ||
| 1826 | |||
| 1827 | return ret; | ||
| 1828 | } | ||
| 1829 | |||
| 1830 | /****************************************************************************** | ||
| 1831 | Section: moves, move sequences and transformations | ||
| 1832 | |||
| 1833 | This section contains methods to work with moves and arrays of moves. They | ||
| 1834 | do not rely on the cube structure. | ||
| 1835 | ******************************************************************************/ | ||
| 1836 | |||
| 1837 | _static_inline bool allowednextmove(uint8_t *, uint8_t); | ||
| 1838 | _static_inline uint8_t inverse_trans(uint8_t); | ||
| 1839 | _static_inline uint8_t movebase(uint8_t); | ||
| 1840 | _static_inline uint8_t moveaxis(uint8_t); | ||
| 1841 | |||
| 1842 | _static bool | ||
| 1843 | allowednextmove(uint8_t *moves, uint8_t n) | ||
| 1844 | { | ||
| 1845 | uint8_t base[3], axis[3]; | ||
| 1846 | |||
| 1847 | if (n < 2) | ||
| 1848 | return true; | ||
| 1849 | |||
| 1850 | base[0] = movebase(moves[n-1]); | ||
| 1851 | axis[0] = moveaxis(moves[n-1]); | ||
| 1852 | base[1] = movebase(moves[n-2]); | ||
| 1853 | axis[1] = moveaxis(moves[n-2]); | ||
| 1854 | |||
| 1855 | if (base[0] == base[1] || (axis[0] == axis[1] && base[0] < base[1])) | ||
| 1856 | return false; | ||
| 1857 | |||
| 1858 | if (n == 2) | ||
| 1859 | return true; | ||
| 1860 | |||
| 1861 | base[2] = movebase(moves[n-3]); | ||
| 1862 | axis[2] = moveaxis(moves[n-3]); | ||
| 1863 | |||
| 1864 | return axis[1] != axis[2] || base[0] != base[2]; | ||
| 1865 | } | ||
| 1866 | |||
| 1867 | _static_inline uint8_t | ||
| 1868 | inverse_trans(uint8_t t) | ||
| 1869 | { | ||
| 1870 | return inverse_trans_table[t]; | ||
| 1871 | } | ||
| 1872 | |||
| 1873 | _static_inline uint8_t | ||
| 1874 | movebase(uint8_t move) | ||
| 1875 | { | ||
| 1876 | return move / 3; | ||
| 1877 | } | ||
| 1878 | |||
| 1879 | _static_inline uint8_t | ||
| 1880 | moveaxis(uint8_t move) | ||
| 1881 | { | ||
| 1882 | return move / 6; | ||
| 1883 | } | ||
| 1884 | |||
| 1885 | /****************************************************************************** | ||
| 1886 | Section: auxiliary procedures for H48 optimal solver (temporary) | ||
| 1887 | ******************************************************************************/ | ||
| 1888 | |||
| 1889 | #define _esep_ind(i) (i / 8U) | ||
| 1890 | #define _esep_shift(i) (4U * (i % 8U)) | ||
| 1891 | #define _esep_mask(i) (((1U << 4U) - 1U) << _esep_shift(i)) | ||
| 1892 | #define _visited_ind(i) (i / 8U) | ||
| 1893 | #define _visited_mask(i) (1U << (i % 8U)) | ||
| 1894 | |||
| 1895 | typedef struct { | ||
| 1896 | cube_fast_t cube; | ||
| 1897 | uint8_t *visited; | ||
| 1898 | uint8_t *moves; | ||
| 1899 | uint8_t nmoves; | ||
| 1900 | uint8_t depth; | ||
| 1901 | uint16_t *nclasses; | ||
| 1902 | uint32_t *cocsepdata; | ||
| 1903 | uint32_t *buf32; | ||
| 1904 | } dfsarg_gendata_t; | ||
| 1905 | |||
| 1906 | _static size_t gendata_cocsep(void *); | ||
| 1907 | _static uint32_t gendata_cocsep_dfs( /* TODO: use dfsarg */ | ||
| 1908 | cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *, uint8_t *); | ||
| 1909 | |||
| 1910 | _static size_t gendata_esep(const void *, void *); | ||
| 1911 | _static uint32_t gendata_esep_dfs(dfsarg_gendata_t *); | ||
| 1912 | |||
| 1913 | _static_inline bool get_visited(const uint8_t *, int64_t); | ||
| 1914 | _static_inline void set_visited(uint8_t *, int64_t); | ||
| 1915 | _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t); | ||
| 1916 | _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t); | ||
| 1917 | |||
| 1918 | /* | ||
| 1919 | Each element of the cocsep table is a uint32_t used as follows: | ||
| 1920 | - Lowest 8-bit block: pruning value | ||
| 1921 | - Second-lower 8-bit block: "ttrep" (transformation to representative) | ||
| 1922 | - Top 16-bit block: symcoord value | ||
| 1923 | After the data as described above, more auxiliary information is appended: | ||
| 1924 | - A uint32_t representing the number of symmetry classes | ||
| 1925 | - A uint32_t representing the highest value of the pruning table | ||
| 1926 | - One uint32_t for each "line" of the pruning table, representing the number | ||
| 1927 | of positions having that pruning value. | ||
| 1928 | */ | ||
| 1929 | _static size_t | ||
| 1930 | gendata_cocsep(void *buf) | ||
| 1931 | { | ||
| 1932 | size_t tablesize = _3p7 << 7U; | ||
| 1933 | size_t visitedsize = (tablesize + 7U) / 8U; | ||
| 1934 | size_t infosize = 12; | ||
| 1935 | |||
| 1936 | cube_fast_t solved; | ||
| 1937 | uint32_t *buf32, *info, cc; | ||
| 1938 | uint16_t n; | ||
| 1939 | uint8_t i, j, visited[visitedsize]; | ||
| 1940 | |||
| 1941 | buf32 = (uint32_t *)buf; | ||
| 1942 | info = buf32 + tablesize; | ||
| 1943 | memset(buf32, 0xFFU, 4*tablesize); | ||
| 1944 | memset(info, 0, 4*infosize); | ||
| 1945 | |||
| 1946 | solved = cubetofast(solvedcube()); | ||
| 1947 | for (i = 0, n = 0, cc = 0; i < 10; i++) { | ||
| 1948 | memset(visited, 0, visitedsize); | ||
| 1949 | DBG_LOG("cocsep: generating depth %" PRIu8 "\n", i); | ||
| 1950 | cc = gendata_cocsep_dfs(solved, 0, i, &n, buf32, visited); | ||
| 1951 | info[i+2] = cc; | ||
| 1952 | DBG_LOG("found %" PRIu32 "\n", cc); | ||
| 1953 | } | ||
| 1954 | |||
| 1955 | info[0] = (uint32_t)n; | ||
| 1956 | info[1] = 9U; /* Known max pruning value */ | ||
| 1957 | DBG_ASSERT(n == COCSEP_CLASSES, 0, | ||
| 1958 | "cocsep: computed %" PRIu16 " symmetry classes, " | ||
| 1959 | "expected %" PRIu16 "\n", n, COCSEP_CLASSES); | ||
| 1960 | |||
| 1961 | DBG_LOG("cocsep data computed\n"); | ||
| 1962 | DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]); | ||
| 1963 | DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[1]); | ||
| 1964 | DBG_LOG("Pruning value distribution:\n"); | ||
| 1965 | for (j = 0; j < 10; j++) | ||
| 1966 | DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+2]); | ||
| 1967 | |||
| 1968 | return 4*(tablesize + infosize); | ||
| 1969 | } | ||
| 1970 | |||
| 1971 | _static uint32_t | ||
| 1972 | gendata_cocsep_dfs( | ||
| 1973 | cube_fast_t c, | ||
| 1974 | uint8_t depth, | ||
| 1975 | uint8_t maxdepth, | ||
| 1976 | uint16_t *n, | ||
| 1977 | uint32_t *buf32, | ||
| 1978 | uint8_t *visited | ||
| 1979 | ) | ||
| 1980 | { | ||
| 1981 | uint8_t m, t, tinv, olddepth; | ||
| 1982 | uint32_t cc; | ||
| 1983 | int64_t i; | ||
| 1984 | cube_fast_t d; | ||
| 1985 | |||
| 1986 | i = coord_fast_cocsep(c); | ||
| 1987 | olddepth = (uint8_t)(buf32[i] & 0xFFU); | ||
| 1988 | if (olddepth < depth || get_visited(visited, i)) | ||
| 1989 | return 0; | ||
| 1990 | set_visited(visited, i); | ||
| 1991 | |||
| 1992 | if (depth == maxdepth) { | ||
| 1993 | if ((buf32[i] & 0xFFU) != 0xFFU) | ||
| 1994 | return 0; | ||
| 1995 | |||
| 1996 | for (t = 0, cc = 0; t < 48; t++) { | ||
| 1997 | d = transform(c, t); | ||
| 1998 | i = coord_fast_cocsep(d); | ||
| 1999 | set_visited(visited, i); | ||
| 2000 | tinv = inverse_trans(t); | ||
| 2001 | cc += (buf32[i] & 0xFFU) == 0xFFU; | ||
| 2002 | buf32[i] = (*n << 16U) | (tinv << 8U) | depth; | ||
| 2003 | } | ||
| 2004 | (*n)++; | ||
| 2005 | |||
| 2006 | return cc; | ||
| 2007 | } | ||
| 2008 | |||
| 2009 | for (m = 0, cc = 0; m < 18; m++) { | ||
| 2010 | d = move(c, m); | ||
| 2011 | cc += gendata_cocsep_dfs(d, depth+1, maxdepth, n, buf32, visited); | ||
| 2012 | } | ||
| 2013 | |||
| 2014 | return cc; | ||
| 2015 | } | ||
| 2016 | |||
| 2017 | /* | ||
| 2018 | TODO description | ||
| 2019 | generating fixed table with h=0, k=4 | ||
| 2020 | */ | ||
| 2021 | _static size_t | ||
| 2022 | gendata_esep(const void *cocsepdata, void *buf) | ||
| 2023 | { | ||
| 2024 | size_t tablesize = (COCSEP_CLASSES * _12c4 * _8c4) / 2U; | ||
| 2025 | size_t visitedsize = (tablesize * 2U + 7U) / 8U; | ||
| 2026 | size_t infosize = 25; /* TODO unknown yet */ | ||
| 2027 | |||
| 2028 | uint32_t *buf32, *info, cc; | ||
| 2029 | uint8_t moves[20]; | ||
| 2030 | dfsarg_gendata_t arg; | ||
| 2031 | |||
| 2032 | arg.visited = malloc(visitedsize); | ||
| 2033 | buf32 = (uint32_t *)buf; | ||
| 2034 | info = buf32 + tablesize; | ||
| 2035 | memset(buf32, 0xFFU, 4*tablesize); | ||
| 2036 | memset(info, 0, 4*infosize); | ||
| 2037 | |||
| 2038 | arg.cube = cubetofast(solvedcube()); | ||
| 2039 | arg.moves = moves; | ||
| 2040 | arg.nmoves = 0; | ||
| 2041 | arg.cocsepdata = (uint32_t *)cocsepdata; | ||
| 2042 | arg.buf32 = buf32; | ||
| 2043 | /* TODO loop until no more is done, not until 12! (or hardcode limits)*/ | ||
| 2044 | for (arg.depth = 0, cc = 0; arg.depth < 12; arg.depth++) { | ||
| 2045 | DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth); | ||
| 2046 | memset(arg.visited, 0, visitedsize); | ||
| 2047 | cc = gendata_esep_dfs(&arg); | ||
| 2048 | info[arg.depth+1] = cc; | ||
| 2049 | DBG_LOG("found %" PRIu32 "\n", cc); | ||
| 2050 | } | ||
| 2051 | free(arg.visited); | ||
| 2052 | |||
| 2053 | return cc; | ||
| 2054 | } | ||
| 2055 | |||
| 2056 | _static uint32_t | ||
| 2057 | gendata_esep_dfs(dfsarg_gendata_t *arg) | ||
| 2058 | { | ||
| 2059 | uint8_t m, t, olddepth; | ||
| 2060 | uint32_t cc; | ||
| 2061 | uint64_t i; | ||
| 2062 | cube_fast_t d; | ||
| 2063 | dfsarg_gendata_t nextarg; | ||
| 2064 | |||
| 2065 | if (!allowednextmove(arg->moves, arg->nmoves)) | ||
| 2066 | return 0; | ||
| 2067 | |||
| 2068 | if (arg->nmoves > 0) | ||
| 2069 | arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); | ||
| 2070 | |||
| 2071 | i = coord_h48(arg->cube, arg->cocsepdata, 0U); | ||
| 2072 | olddepth = get_esep_pval(arg->buf32, i); | ||
| 2073 | |||
| 2074 | if (olddepth < arg->nmoves || get_visited(arg->visited, i)) | ||
| 2075 | return 0; | ||
| 2076 | set_visited(arg->visited, i); | ||
| 2077 | |||
| 2078 | if (arg->nmoves == arg->depth) { | ||
| 2079 | if (olddepth != 15U) | ||
| 2080 | return 0; | ||
| 2081 | |||
| 2082 | for (t = 0, cc = 0; t < 48; t++) { | ||
| 2083 | d = transform(arg->cube, t); | ||
| 2084 | i = coord_h48(d, arg->cocsepdata, 0U); | ||
| 2085 | set_visited(arg->visited, i); | ||
| 2086 | cc += get_esep_pval(arg->buf32, i) == 15U; | ||
| 2087 | set_esep_pval(arg->buf32, i, arg->depth); | ||
| 2088 | } | ||
| 2089 | |||
| 2090 | return cc; | ||
| 2091 | } | ||
| 2092 | |||
| 2093 | |||
| 2094 | nextarg = *arg; | ||
| 2095 | nextarg.nmoves = arg->nmoves + 1; | ||
| 2096 | for (m = 0, cc = 0; m < 18; m++) { | ||
| 2097 | nextarg.cube = arg->cube; | ||
| 2098 | nextarg.moves[arg->nmoves] = m; | ||
| 2099 | cc += gendata_esep_dfs(&nextarg); | ||
| 2100 | } | ||
| 2101 | |||
| 2102 | return cc; | ||
| 2103 | } | ||
| 2104 | |||
| 2105 | _static_inline bool get_visited(const uint8_t *a, int64_t i) | ||
| 2106 | { | ||
| 2107 | return a[_visited_ind(i)] & _visited_mask(i); | ||
| 2108 | } | ||
| 2109 | |||
| 2110 | _static_inline void set_visited(uint8_t *a, int64_t i) | ||
| 2111 | { | ||
| 2112 | a[_visited_ind(i)] |= _visited_mask(i); | ||
| 2113 | } | ||
| 2114 | |||
| 2115 | _static_inline uint8_t | ||
| 2116 | get_esep_pval(const uint32_t *buf32, int64_t i) | ||
| 2117 | { | ||
| 2118 | return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i); | ||
| 2119 | } | ||
| 2120 | |||
| 2121 | _static_inline void | ||
| 2122 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) | ||
| 2123 | { | ||
| 2124 | buf32[_esep_ind(i)] = | ||
| 2125 | (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i)); | ||
| 2126 | } | ||
| 2127 | |||
| 2128 | /****************************************************************************** | ||
| 2129 | Section: solvers | ||
| 2130 | |||
| 2131 | Here you can find the implementation of all the solving algorithms. | ||
| 2132 | ******************************************************************************/ | ||
| 2133 | |||
| 2134 | typedef struct { | ||
| 2135 | cube_fast_t cube; | ||
| 2136 | uint8_t depth; | ||
| 2137 | int64_t maxsols; | ||
| 2138 | char **nextsol; | ||
| 2139 | int64_t *nsols; | ||
| 2140 | uint8_t nmoves; | ||
| 2141 | uint8_t moves[20]; | ||
| 2142 | uint8_t (*estimate)(cube_fast_t); | ||
| 2143 | } dfsarg_generic_t; | ||
| 2144 | |||
| 2145 | _static void solve_generic_appendsolution(dfsarg_generic_t *); | ||
| 2146 | _static int solve_generic_dfs(dfsarg_generic_t *); | ||
| 2147 | _static int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t, | ||
| 2148 | int8_t, char *, uint8_t (*)(cube_fast_t)); | ||
| 2149 | _static uint8_t estimate_simple(cube_fast_t); | ||
| 2150 | _static int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *); | ||
| 2151 | |||
| 2152 | int64_t | ||
| 2153 | solve( | ||
| 2154 | cube_t cube, | ||
| 2155 | const char *solver, | ||
| 2156 | const char *options, | ||
| 2157 | const char *nisstype, | ||
| 2158 | int8_t minmoves, | ||
| 2159 | int8_t maxmoves, | ||
| 2160 | int64_t maxsols, | ||
| 2161 | int8_t optimal, | ||
| 2162 | const void *data, | ||
| 2163 | char *solutions | ||
| 2164 | ) | ||
| 2165 | { | ||
| 2166 | DBG_WARN(!strcmp(options, ""), | ||
| 2167 | "solve: 'options' not implemented yet, ignoring\n"); | ||
| 2168 | |||
| 2169 | DBG_WARN(!strcmp(nisstype, ""), | ||
| 2170 | "solve: NISS not implemented yet, ignoring 'nisstype'\n"); | ||
| 2171 | |||
| 2172 | DBG_WARN(data == NULL, | ||
| 2173 | "solve: 'data' not implemented yet, ignoring\n"); | ||
| 2174 | |||
| 2175 | if (!strcmp(solver, "optimal") || !strcmp(solver, "simple")) { | ||
| 2176 | return solve_simple( | ||
| 2177 | cube, | ||
| 2178 | minmoves, | ||
| 2179 | maxmoves, | ||
| 2180 | maxsols, | ||
| 2181 | optimal, | ||
| 2182 | solutions | ||
| 2183 | ); | ||
| 2184 | } else { | ||
| 2185 | DBG_LOG("solve: unknown solver '%s'\n", solver); | ||
| 2186 | return -1; | ||
| 2187 | } | ||
| 2188 | |||
| 2189 | DBG_LOG("solve: error\n"); | ||
| 2190 | return -1; | ||
| 2191 | } | ||
| 2192 | |||
| 2193 | void | ||
| 2194 | multisolve( | ||
| 2195 | int n, | ||
| 2196 | cube_t *cube, | ||
| 2197 | const char *solver, | ||
| 2198 | const void *data, | ||
| 2199 | char *sols | ||
| 2200 | ) | ||
| 2201 | { | ||
| 2202 | char *s; | ||
| 2203 | int i; | ||
| 2204 | |||
| 2205 | s = sols; | ||
| 2206 | for (i = 0; i < n; i++) { | ||
| 2207 | solve(cube[i], solver, "", "normal", 0, -1, 1, 0, NULL, s); | ||
| 2208 | while (s++); | ||
| 2209 | } | ||
| 2210 | } | ||
| 2211 | |||
| 2212 | int64_t | ||
| 2213 | gendata(const char *solver, void *data) | ||
| 2214 | { | ||
| 2215 | DBG_LOG("gendata: not implemented yet\n"); | ||
| 2216 | |||
| 2217 | return -1; | ||
| 2218 | } | ||
| 2219 | |||
| 2220 | _static void | ||
| 2221 | solve_generic_appendsolution(dfsarg_generic_t *arg) | ||
| 2222 | { | ||
| 2223 | int strl; | ||
| 2224 | |||
| 2225 | strl = writemoves(arg->moves, arg->depth, *arg->nextsol); | ||
| 2226 | DBG_LOG("Solution found: %s\n", *arg->nextsol); | ||
| 2227 | *arg->nextsol += strl; | ||
| 2228 | **arg->nextsol = '\n'; | ||
| 2229 | (*arg->nextsol)++; | ||
| 2230 | (*arg->nsols)++; | ||
| 2231 | } | ||
| 2232 | |||
| 2233 | _static int | ||
| 2234 | solve_generic_dfs(dfsarg_generic_t *arg) | ||
| 2235 | { | ||
| 2236 | dfsarg_generic_t nextarg; | ||
| 2237 | uint8_t m, bound; | ||
| 2238 | int64_t ret; | ||
| 2239 | |||
| 2240 | if (!allowednextmove(arg->moves, arg->nmoves)) | ||
| 2241 | return 0; | ||
| 2242 | |||
| 2243 | if (arg->nmoves > 0) | ||
| 2244 | arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); | ||
| 2245 | |||
| 2246 | bound = arg->estimate(arg->cube); | ||
| 2247 | if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth) | ||
| 2248 | return 0; | ||
| 2249 | |||
| 2250 | if (bound == 0) { | ||
| 2251 | if (arg->nmoves != arg->depth) | ||
| 2252 | return 0; | ||
| 2253 | solve_generic_appendsolution(arg); | ||
| 2254 | return 1; | ||
| 2255 | } | ||
| 2256 | |||
| 2257 | /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */ | ||
| 2258 | nextarg = *arg; | ||
| 2259 | nextarg.nmoves = arg->nmoves + 1; | ||
| 2260 | for (m = 0, ret = 0; m < 18; m++) { | ||
| 2261 | nextarg.cube = arg->cube; | ||
| 2262 | nextarg.moves[arg->nmoves] = m; | ||
| 2263 | ret += solve_generic_dfs(&nextarg); | ||
| 2264 | } | ||
| 2265 | |||
| 2266 | return ret; | ||
| 2267 | } | ||
| 2268 | |||
| 2269 | _static int64_t | ||
| 2270 | solve_generic( | ||
| 2271 | cube_t cube, | ||
| 2272 | const char *nisstype, | ||
| 2273 | /* TODO: handle NISS */ | ||
| 2274 | int8_t minmoves, | ||
| 2275 | int8_t maxmoves, | ||
| 2276 | int64_t maxsols, | ||
| 2277 | int8_t optimal, | ||
| 2278 | char *sols, | ||
| 2279 | uint8_t (*estimate)(cube_fast_t) | ||
| 2280 | /* TODO: add validator */ | ||
| 2281 | /* TODO: maybe add data for estimate */ | ||
| 2282 | /* TODO: add moveset (and allowednext?) */ | ||
| 2283 | ) | ||
| 2284 | { | ||
| 2285 | dfsarg_generic_t arg; | ||
| 2286 | int64_t ret, tmp, first; | ||
| 2287 | |||
| 2288 | if (!issolvable(cube)) { | ||
| 2289 | DBG_LOG("solve: cube is not solvable\n"); | ||
| 2290 | return -1; | ||
| 2291 | } | ||
| 2292 | |||
| 2293 | if (issolved(cube)) { | ||
| 2294 | DBG_LOG("solve: cube is already solved\n"); | ||
| 2295 | sols[0] = '\n'; | ||
| 2296 | sols[1] = 0; | ||
| 2297 | return 1; | ||
| 2298 | } | ||
| 2299 | |||
| 2300 | DBG_WARN(!strcmp(nisstype, ""), | ||
| 2301 | "solve: NISS not implemented yet, 'nisstype' ignored\n"); | ||
| 2302 | |||
| 2303 | if (minmoves < 0) { | ||
| 2304 | DBG_LOG("solve: 'minmoves' is negative, setting to 0\n"); | ||
| 2305 | minmoves = 0; | ||
| 2306 | } | ||
| 2307 | |||
| 2308 | if (maxmoves < 0) { | ||
| 2309 | DBG_LOG("solve: invalid 'maxmoves', setting to 20\n"); | ||
| 2310 | maxmoves = 20; | ||
| 2311 | } | ||
| 2312 | |||
| 2313 | if (maxsols < 0) { | ||
| 2314 | DBG_LOG("solve: 'maxsols' is negative\n"); | ||
| 2315 | return -1; | ||
| 2316 | } | ||
| 2317 | |||
| 2318 | if (maxsols == 0) { | ||
| 2319 | DBG_LOG("solve: 'maxsols' is 0\n"); | ||
| 2320 | return 0; | ||
| 2321 | } | ||
| 2322 | |||
| 2323 | if (sols == NULL) { | ||
| 2324 | DBG_LOG("solve: return parameter 'sols' is NULL\n"); | ||
| 2325 | return -1; | ||
| 2326 | } | ||
| 2327 | |||
| 2328 | if (estimate == NULL) { | ||
| 2329 | DBG_LOG("solve: 'estimate' is NULL\n"); | ||
| 2330 | return -1; | ||
| 2331 | } | ||
| 2332 | |||
| 2333 | arg = (dfsarg_generic_t) { | ||
| 2334 | .cube = cubetofast(cube), | ||
| 2335 | .maxsols = maxsols, | ||
| 2336 | .nextsol = &sols, | ||
| 2337 | .nsols = &ret, | ||
| 2338 | .nmoves = 0, | ||
| 2339 | .moves = {0}, | ||
| 2340 | .estimate = estimate, | ||
| 2341 | }; | ||
| 2342 | |||
| 2343 | ret = 0; | ||
| 2344 | first = -1; | ||
| 2345 | for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) { | ||
| 2346 | tmp = solve_generic_dfs(&arg); | ||
| 2347 | if (tmp != 0) | ||
| 2348 | first = arg.depth; | ||
| 2349 | |||
| 2350 | DBG_LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n", | ||
| 2351 | tmp, tmp == 1 ? "" : "s", arg.depth); | ||
| 2352 | |||
| 2353 | if (ret >= maxsols) | ||
| 2354 | break; | ||
| 2355 | |||
| 2356 | if (optimal >= 0 && first >= 0 && arg.depth - first == optimal) | ||
| 2357 | break; | ||
| 2358 | } | ||
| 2359 | |||
| 2360 | DBG_ASSERT(ret <= maxsols, ret, | ||
| 2361 | "solve: found more than 'maxsols' solutions\n"); | ||
| 2362 | |||
| 2363 | return ret; | ||
| 2364 | } | ||
| 2365 | |||
| 2366 | _static uint8_t | ||
| 2367 | estimate_simple(cube_fast_t cube) | ||
| 2368 | { | ||
| 2369 | return issolved_fast(cube) ? 0 : 1; | ||
| 2370 | } | ||
| 2371 | |||
| 2372 | _static int64_t | ||
| 2373 | solve_simple( | ||
| 2374 | cube_t cube, | ||
| 2375 | int8_t minmoves, | ||
| 2376 | int8_t maxmoves, | ||
| 2377 | int64_t maxsols, | ||
| 2378 | int8_t optimal, | ||
| 2379 | char *solutions | ||
| 2380 | ) | ||
| 2381 | { | ||
| 2382 | return solve_generic( | ||
| 2383 | cube, | ||
| 2384 | "", | ||
| 2385 | minmoves, | ||
| 2386 | maxmoves, | ||
| 2387 | maxsols, | ||
| 2388 | optimal, | ||
| 2389 | solutions, | ||
| 2390 | &estimate_simple | ||
| 2391 | ); | ||
| 2392 | } | ||
diff --git a/src/cube_avx2.h b/src/cube_avx2.h new file mode 100644 index 0000000..c61813f --- /dev/null +++ b/src/cube_avx2.h | |||
| @@ -0,0 +1,229 @@ | |||
| 1 | typedef __m256i cube_fast_t; | ||
| 2 | |||
| 3 | #define _co2_avx2 _mm256_set_epi64x(0, 0, 0, 0x6060606060606060) | ||
| 4 | #define _cocw_avx2 _mm256_set_epi64x(0, 0, 0, 0x2020202020202020) | ||
| 5 | #define _cp_avx2 _mm256_set_epi64x(0, 0, 0, 0x0707070707070707) | ||
| 6 | #define _ep_avx2 _mm256_set_epi64x(0x0F0F0F0F, 0x0F0F0F0F0F0F0F0F, 0, 0) | ||
| 7 | #define _eo_avx2 _mm256_set_epi64x(0x10101010, 0x1010101010101010, 0, 0) | ||
| 8 | |||
| 9 | _static_inline cube_fast_t fastcube( | ||
| 10 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 11 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 12 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 13 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t | ||
| 14 | ); | ||
| 15 | _static cube_fast_t cubetofast(cube_t); | ||
| 16 | _static cube_t fasttocube(cube_fast_t); | ||
| 17 | _static_inline bool equal_fast(cube_fast_t, cube_fast_t); | ||
| 18 | _static_inline bool issolved_fast(cube_fast_t); | ||
| 19 | _static_inline cube_fast_t invertco_fast(cube_fast_t); | ||
| 20 | _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t); | ||
| 21 | |||
| 22 | _static_inline int64_t coord_fast_co(cube_fast_t); | ||
| 23 | _static_inline int64_t coord_fast_csep(cube_fast_t); | ||
| 24 | _static_inline int64_t coord_fast_cocsep(cube_fast_t); | ||
| 25 | _static_inline int64_t coord_fast_eo(cube_fast_t); | ||
| 26 | _static_inline int64_t coord_fast_esep(cube_fast_t); | ||
| 27 | |||
| 28 | _static_inline cube_fast_t | ||
| 29 | fastcube( | ||
| 30 | uint8_t c_ufr, | ||
| 31 | uint8_t c_ubl, | ||
| 32 | uint8_t c_dfl, | ||
| 33 | uint8_t c_dbr, | ||
| 34 | uint8_t c_ufl, | ||
| 35 | uint8_t c_ubr, | ||
| 36 | uint8_t c_dfr, | ||
| 37 | uint8_t c_dbl, | ||
| 38 | |||
| 39 | uint8_t e_uf, | ||
| 40 | uint8_t e_ub, | ||
| 41 | uint8_t e_db, | ||
| 42 | uint8_t e_df, | ||
| 43 | uint8_t e_ur, | ||
| 44 | uint8_t e_ul, | ||
| 45 | uint8_t e_dl, | ||
| 46 | uint8_t e_dr, | ||
| 47 | uint8_t e_fr, | ||
| 48 | uint8_t e_fl, | ||
| 49 | uint8_t e_bl, | ||
| 50 | uint8_t e_br | ||
| 51 | ) | ||
| 52 | { | ||
| 53 | return _mm256_set_epi8( | ||
| 54 | 0, 0, 0, 0, e_br, e_bl, e_fl, e_fr, | ||
| 55 | e_dr, e_dl, e_ul, e_ur, e_df, e_db, e_ub, e_uf, | ||
| 56 | 0, 0, 0, 0, 0, 0, 0, 0, | ||
| 57 | c_dbl, c_dfr, c_ubr, c_ufl, c_dbr, c_dfl, c_ubl, c_ufr | ||
| 58 | ); | ||
| 59 | } | ||
| 60 | |||
| 61 | _static cube_fast_t | ||
| 62 | cubetofast(cube_t a) | ||
| 63 | { | ||
| 64 | uint8_t aux[32]; | ||
| 65 | |||
| 66 | memset(aux, 0, 32); | ||
| 67 | memcpy(aux, &a.corner, 8); | ||
| 68 | memcpy(aux + 16, &a.edge, 12); | ||
| 69 | |||
| 70 | return _mm256_loadu_si256((__m256i_u *)&aux); | ||
| 71 | } | ||
| 72 | |||
| 73 | _static cube_t | ||
| 74 | fasttocube(cube_fast_t c) | ||
| 75 | { | ||
| 76 | cube_t a; | ||
| 77 | uint8_t aux[32]; | ||
| 78 | |||
| 79 | _mm256_storeu_si256((__m256i_u *)aux, c); | ||
| 80 | memcpy(&a.corner, aux, 8); | ||
| 81 | memcpy(&a.edge, aux + 16, 12); | ||
| 82 | |||
| 83 | return a; | ||
| 84 | } | ||
| 85 | |||
| 86 | _static_inline bool | ||
| 87 | equal_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 88 | { | ||
| 89 | int32_t mask; | ||
| 90 | __m256i cmp; | ||
| 91 | |||
| 92 | cmp = _mm256_cmpeq_epi8(c1, c2); | ||
| 93 | mask = _mm256_movemask_epi8(cmp); | ||
| 94 | |||
| 95 | return mask == ~0; | ||
| 96 | } | ||
| 97 | |||
| 98 | _static_inline bool | ||
| 99 | issolved_fast(cube_fast_t cube) | ||
| 100 | { | ||
| 101 | return equal_fast(cube, solved_fast); | ||
| 102 | } | ||
| 103 | |||
| 104 | _static_inline cube_fast_t | ||
| 105 | invertco_fast(cube_fast_t c) | ||
| 106 | { | ||
| 107 | cube_fast_t co, shleft, shright, summed, newco, cleanco, ret; | ||
| 108 | |||
| 109 | co = _mm256_and_si256(c, _co2_avx2); | ||
| 110 | shleft = _mm256_slli_epi32(co, 1); | ||
| 111 | shright = _mm256_srli_epi32(co, 1); | ||
| 112 | summed = _mm256_or_si256(shleft, shright); | ||
| 113 | newco = _mm256_and_si256(summed, _co2_avx2); | ||
| 114 | cleanco = _mm256_xor_si256(c, co); | ||
| 115 | ret = _mm256_or_si256(cleanco, newco); | ||
| 116 | |||
| 117 | return ret; | ||
| 118 | } | ||
| 119 | |||
| 120 | _static_inline cube_fast_t | ||
| 121 | compose_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 122 | { | ||
| 123 | cube_fast_t s, b, eo2, co1, co2, aux, auy1, auy2, auz1, auz2; | ||
| 124 | |||
| 125 | /* Permute and clean unused bits */ | ||
| 126 | s = _mm256_shuffle_epi8(c1, c2); | ||
| 127 | b = _mm256_set_epi8( | ||
| 128 | ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||
| 129 | ~0, ~0, ~0, ~0, ~0, ~0, ~0, ~0, 0, 0, 0, 0, 0, 0, 0, 0 | ||
| 130 | ); | ||
| 131 | s = _mm256_andnot_si256(b, s); | ||
| 132 | |||
| 133 | /* Change EO */ | ||
| 134 | eo2 = _mm256_and_si256(c2, _eo_avx2); | ||
| 135 | s = _mm256_xor_si256(s, eo2); | ||
| 136 | |||
| 137 | /* Change CO */ | ||
| 138 | co1 = _mm256_and_si256(s, _co2_avx2); | ||
| 139 | co2 = _mm256_and_si256(c2, _co2_avx2); | ||
| 140 | aux = _mm256_add_epi8(co1, co2); | ||
| 141 | auy1 = _mm256_add_epi8(aux, _cocw_avx2); | ||
| 142 | auy2 = _mm256_srli_epi32(auy1, 2); | ||
| 143 | auz1 = _mm256_add_epi8(aux, auy2); | ||
| 144 | auz2 = _mm256_and_si256(auz1, _co2_avx2); | ||
| 145 | |||
| 146 | /* Put together */ | ||
| 147 | s = _mm256_andnot_si256(_co2_avx2, s); | ||
| 148 | s = _mm256_or_si256(s, auz2); | ||
| 149 | |||
| 150 | return s; | ||
| 151 | } | ||
| 152 | |||
| 153 | _static_inline int64_t | ||
| 154 | coord_fast_co(cube_fast_t c) | ||
| 155 | { | ||
| 156 | cube_fast_t co; | ||
| 157 | int64_t mem[4], ret, i, p; | ||
| 158 | |||
| 159 | co = _mm256_and_si256(c, _co2_avx2); | ||
| 160 | _mm256_storeu_si256((__m256i *)mem, co); | ||
| 161 | |||
| 162 | mem[0] >>= 5L; | ||
| 163 | for (i = 0, ret = 0, p = 1; i < 7; i++, mem[0] >>= 8L, p *= 3) | ||
| 164 | ret += (mem[0] & 3L) * p; | ||
| 165 | |||
| 166 | return ret; | ||
| 167 | } | ||
| 168 | |||
| 169 | _static_inline int64_t | ||
| 170 | coord_fast_csep(cube_fast_t c) | ||
| 171 | { | ||
| 172 | cube_fast_t cp, shifted; | ||
| 173 | int64_t mask; | ||
| 174 | |||
| 175 | cp = _mm256_and_si256(c, _cp_avx2); | ||
| 176 | shifted = _mm256_slli_epi32(cp, 5); | ||
| 177 | mask = _mm256_movemask_epi8(shifted); | ||
| 178 | |||
| 179 | return mask & 0x7F; | ||
| 180 | } | ||
| 181 | |||
| 182 | _static_inline int64_t | ||
| 183 | coord_fast_cocsep(cube_fast_t c) | ||
| 184 | { | ||
| 185 | return (coord_fast_co(c) << 7) + coord_fast_csep(c); | ||
| 186 | } | ||
| 187 | |||
| 188 | _static_inline int64_t | ||
| 189 | coord_fast_eo(cube_fast_t c) | ||
| 190 | { | ||
| 191 | cube_fast_t eo, shifted; | ||
| 192 | int64_t mask; | ||
| 193 | |||
| 194 | eo = _mm256_and_si256(c, _eo_avx2); | ||
| 195 | shifted = _mm256_slli_epi32(eo, 3); | ||
| 196 | mask = _mm256_movemask_epi8(shifted); | ||
| 197 | |||
| 198 | return mask >> 17; | ||
| 199 | } | ||
| 200 | |||
| 201 | _static_inline int64_t | ||
| 202 | coord_fast_esep(cube_fast_t c) | ||
| 203 | { | ||
| 204 | cube_fast_t ep; | ||
| 205 | int64_t e, mem[4], i, j, k, l, ret1, ret2, bit1, bit2, is1; | ||
| 206 | |||
| 207 | ep = _mm256_and_si256(c, _ep_avx2); | ||
| 208 | _mm256_storeu_si256((__m256i *)mem, ep); | ||
| 209 | |||
| 210 | mem[3] <<= 8L; | ||
| 211 | ret1 = ret2 = 0; | ||
| 212 | k = l = 4; | ||
| 213 | for (i = 0, j = 0; i < 12; i++, mem[i/8 + 2] >>= 8L) { | ||
| 214 | e = mem[i/8 + 2]; | ||
| 215 | |||
| 216 | bit1 = (e & _esepbit1) >> 2L; | ||
| 217 | bit2 = (e & _esepbit2) >> 3L; | ||
| 218 | is1 = (1 - bit2) * bit1; | ||
| 219 | |||
| 220 | ret1 += bit2 * binomial[11-i][k]; | ||
| 221 | k -= bit2; | ||
| 222 | |||
| 223 | ret2 += is1 * binomial[7-j][l]; | ||
| 224 | l -= is1; | ||
| 225 | j += (1-bit2); | ||
| 226 | } | ||
| 227 | |||
| 228 | return ret1 * 70 + ret2; | ||
| 229 | } | ||
diff --git a/src/cube_neon.h b/src/cube_neon.h new file mode 100644 index 0000000..cb2d815 --- /dev/null +++ b/src/cube_neon.h | |||
| @@ -0,0 +1,6 @@ | |||
| 1 | /* TODO! */ | ||
| 2 | |||
| 3 | typedef struct { | ||
| 4 | uint8x16_t corner; | ||
| 5 | uint8x16_t edge; | ||
| 6 | } cube_fast_t; | ||
diff --git a/src/cube_portable.h b/src/cube_portable.h new file mode 100644 index 0000000..281faa0 --- /dev/null +++ b/src/cube_portable.h | |||
| @@ -0,0 +1,224 @@ | |||
| 1 | typedef cube_t cube_fast_t; | ||
| 2 | |||
| 3 | _static_inline cube_fast_t fastcube( | ||
| 4 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 5 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 6 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t, | ||
| 7 | uint8_t, uint8_t, uint8_t, uint8_t, uint8_t | ||
| 8 | ); | ||
| 9 | _static cube_fast_t cubetofast(cube_t); | ||
| 10 | _static cube_t fasttocube(cube_fast_t); | ||
| 11 | _static_inline bool equal_fast(cube_fast_t, cube_fast_t); | ||
| 12 | _static_inline bool issolved_fast(cube_fast_t); | ||
| 13 | _static_inline cube_fast_t invertco_fast(cube_fast_t); | ||
| 14 | _static_inline cube_fast_t compose_fast(cube_fast_t, cube_fast_t); | ||
| 15 | |||
| 16 | _static_inline int64_t coord_fast_co(cube_fast_t); | ||
| 17 | _static_inline int64_t coord_fast_csep(cube_fast_t); | ||
| 18 | _static_inline int64_t coord_fast_cocsep(cube_fast_t); | ||
| 19 | _static_inline int64_t coord_fast_eo(cube_fast_t); | ||
| 20 | _static_inline int64_t coord_fast_esep(cube_fast_t); | ||
| 21 | |||
| 22 | _static_inline cube_fast_t | ||
| 23 | fastcube( | ||
| 24 | uint8_t c_ufr, | ||
| 25 | uint8_t c_ubl, | ||
| 26 | uint8_t c_dfl, | ||
| 27 | uint8_t c_dbr, | ||
| 28 | uint8_t c_ufl, | ||
| 29 | uint8_t c_ubr, | ||
| 30 | uint8_t c_dfr, | ||
| 31 | uint8_t c_dbl, | ||
| 32 | |||
| 33 | uint8_t e_uf, | ||
| 34 | uint8_t e_ub, | ||
| 35 | uint8_t e_db, | ||
| 36 | uint8_t e_df, | ||
| 37 | uint8_t e_ur, | ||
| 38 | uint8_t e_ul, | ||
| 39 | uint8_t e_dl, | ||
| 40 | uint8_t e_dr, | ||
| 41 | uint8_t e_fr, | ||
| 42 | uint8_t e_fl, | ||
| 43 | uint8_t e_bl, | ||
| 44 | uint8_t e_br | ||
| 45 | ) | ||
| 46 | { | ||
| 47 | cube_fast_t cube = { | ||
| 48 | .corner = { | ||
| 49 | c_ufr, c_ubl, c_dfl, c_dbr, c_ufl, c_ubr, c_dfr, c_dbl | ||
| 50 | }, | ||
| 51 | .edge = { | ||
| 52 | e_uf, e_ub, e_db, e_df, e_ur, e_ul, | ||
| 53 | e_dl, e_dr, e_fr, e_fl, e_bl, e_br | ||
| 54 | } | ||
| 55 | }; | ||
| 56 | |||
| 57 | return cube; | ||
| 58 | } | ||
| 59 | |||
| 60 | _static cube_fast_t | ||
| 61 | cubetofast(cube_t cube) | ||
| 62 | { | ||
| 63 | cube_fast_t fast; | ||
| 64 | memcpy(&fast, &cube, sizeof(cube_fast_t)); | ||
| 65 | return fast; | ||
| 66 | } | ||
| 67 | |||
| 68 | _static cube_t | ||
| 69 | fasttocube(cube_fast_t fast) | ||
| 70 | { | ||
| 71 | cube_t cube; | ||
| 72 | memcpy(&cube, &fast, sizeof(cube_fast_t)); | ||
| 73 | return cube; | ||
| 74 | } | ||
| 75 | |||
| 76 | _static_inline bool | ||
| 77 | equal_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 78 | { | ||
| 79 | uint8_t i; | ||
| 80 | bool ret; | ||
| 81 | |||
| 82 | ret = true; | ||
| 83 | for (i = 0; i < 8; i++) | ||
| 84 | ret = ret && c1.corner[i] == c2.corner[i]; | ||
| 85 | for (i = 0; i < 12; i++) | ||
| 86 | ret = ret && c1.edge[i] == c2.edge[i]; | ||
| 87 | |||
| 88 | return ret; | ||
| 89 | } | ||
| 90 | |||
| 91 | _static_inline bool | ||
| 92 | issolved_fast(cube_fast_t cube) | ||
| 93 | { | ||
| 94 | return equal_fast(cube, solved_fast); | ||
| 95 | } | ||
| 96 | |||
| 97 | _static_inline cube_fast_t | ||
| 98 | invertco_fast(cube_fast_t c) | ||
| 99 | { | ||
| 100 | uint8_t i, piece, orien; | ||
| 101 | cube_fast_t ret; | ||
| 102 | |||
| 103 | ret = c; | ||
| 104 | for (i = 0; i < 8; i++) { | ||
| 105 | piece = c.corner[i]; | ||
| 106 | orien = ((piece << 1) | (piece >> 1)) & _cobits2; | ||
| 107 | ret.corner[i] = (piece & _pbits) | orien; | ||
| 108 | } | ||
| 109 | |||
| 110 | return ret; | ||
| 111 | } | ||
| 112 | |||
| 113 | _static_inline cube_fast_t | ||
| 114 | compose_fast(cube_fast_t c1, cube_fast_t c2) | ||
| 115 | { | ||
| 116 | cube_fast_t ret; | ||
| 117 | uint8_t i, piece1, piece2, p, orien, aux, auy; | ||
| 118 | |||
| 119 | ret = zero_fast; | ||
| 120 | |||
| 121 | for (i = 0; i < 12; i++) { | ||
| 122 | piece2 = c2.edge[i]; | ||
| 123 | p = piece2 & _pbits; | ||
| 124 | piece1 = c1.edge[p]; | ||
| 125 | orien = (piece2 ^ piece1) & _eobit; | ||
| 126 | ret.edge[i] = (piece1 & _pbits) | orien; | ||
| 127 | } | ||
| 128 | |||
| 129 | for (i = 0; i < 8; i++) { | ||
| 130 | piece2 = c2.corner[i]; | ||
| 131 | p = piece2 & _pbits; | ||
| 132 | piece1 = c1.corner[p]; | ||
| 133 | aux = (piece2 & _cobits) + (piece1 & _cobits); | ||
| 134 | auy = (aux + _ctwist_cw) >> 2U; | ||
| 135 | orien = (aux + auy) & _cobits2; | ||
| 136 | ret.corner[i] = (piece1 & _pbits) | orien; | ||
| 137 | } | ||
| 138 | |||
| 139 | return ret; | ||
| 140 | } | ||
| 141 | |||
| 142 | _static_inline int64_t | ||
| 143 | coord_fast_co(cube_fast_t c) | ||
| 144 | { | ||
| 145 | int i, p; | ||
| 146 | int64_t ret; | ||
| 147 | |||
| 148 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 3) | ||
| 149 | ret += p * (c.corner[i] >> _coshift); | ||
| 150 | |||
| 151 | return ret; | ||
| 152 | } | ||
| 153 | |||
| 154 | /* | ||
| 155 | For corner separation, we consider the axis (a.k.a. tetrad) each | ||
| 156 | corner belongs to as 0 or 1 and we translate this sequence into binary. | ||
| 157 | Ignoring the last bit, we have a value up to 2^7, but not all values are | ||
| 158 | possible. Encoding this as a number from 0 to C(8,4) would save about 40% | ||
| 159 | of space, but we are not going to use this coordinate in large tables. | ||
| 160 | */ | ||
| 161 | _static_inline int64_t | ||
| 162 | coord_fast_csep(cube_fast_t c) | ||
| 163 | { | ||
| 164 | int i, p; | ||
| 165 | int64_t ret; | ||
| 166 | |||
| 167 | for (ret = 0, i = 0, p = 1; i < 7; i++, p *= 2) | ||
| 168 | ret += p * ((c.corner[i] & _csepbit) >> 2U); | ||
| 169 | |||
| 170 | return ret; | ||
| 171 | } | ||
| 172 | |||
| 173 | _static_inline int64_t | ||
| 174 | coord_fast_cocsep(cube_fast_t c) | ||
| 175 | { | ||
| 176 | return (coord_fast_co(c) << 7) + coord_fast_csep(c); | ||
| 177 | } | ||
| 178 | |||
| 179 | _static_inline int64_t | ||
| 180 | coord_fast_eo(cube_fast_t c) | ||
| 181 | { | ||
| 182 | int i, p; | ||
| 183 | int64_t ret; | ||
| 184 | |||
| 185 | for (ret = 0, i = 1, p = 1; i < 12; i++, p *= 2) | ||
| 186 | ret += p * (c.edge[i] >> _eoshift); | ||
| 187 | |||
| 188 | return ret; | ||
| 189 | } | ||
| 190 | |||
| 191 | /* | ||
| 192 | We encode the edge separation as a number from 0 to C(12,4)*C(8,4). | ||
| 193 | It can be seen as the composition of two "subset index" coordinates. | ||
| 194 | */ | ||
| 195 | _static_inline int64_t | ||
| 196 | coord_fast_esep(cube_fast_t c) | ||
| 197 | { | ||
| 198 | int64_t i, j, k, l, ret1, ret2, bit1, bit2, is1; | ||
| 199 | |||
| 200 | for (i = 0, j = 0, k = 4, l = 4, ret1 = 0, ret2 = 0; i < 12; i++) { | ||
| 201 | /* Simple version: | ||
| 202 | if (c.edge[i] & _esepbit2) { | ||
| 203 | ret1 += binomial[11-i][k--]; | ||
| 204 | } else { | ||
| 205 | if (c.edge[i] & _esepbit1) | ||
| 206 | ret2 += binomial[7-j][l--]; | ||
| 207 | j++; | ||
| 208 | } | ||
| 209 | */ | ||
| 210 | |||
| 211 | bit1 = (c.edge[i] & _esepbit1) >> 2U; | ||
| 212 | bit2 = (c.edge[i] & _esepbit2) >> 3U; | ||
| 213 | is1 = (1 - bit2) * bit1; | ||
| 214 | |||
| 215 | ret1 += bit2 * binomial[11-i][k]; | ||
| 216 | k -= bit2; | ||
| 217 | |||
| 218 | ret2 += is1 * binomial[7-j][l]; | ||
| 219 | l -= is1; | ||
| 220 | j += (1-bit2); | ||
| 221 | } | ||
| 222 | |||
| 223 | return ret1 * 70 + ret2; | ||
| 224 | } | ||
diff --git a/src/cube_routines.h b/src/cube_routines.h new file mode 100644 index 0000000..b1f8eac --- /dev/null +++ b/src/cube_routines.h | |||
| @@ -0,0 +1,730 @@ | |||
| 1 | #define _move(M, c) compose_fast(c, _move_cube_ ## M) | ||
| 2 | #define _premove(M, c) compose_fast(_move_cube_ ## M, c) | ||
| 3 | #define _trans_rotation(T, c) \ | ||
| 4 | compose_fast(compose_fast(_trans_cube_ ## T, c), \ | ||
| 5 | _trans_cube_ ## T ## _inverse) | ||
| 6 | #define _trans_mirrored(T, c) \ | ||
| 7 | invertco_fast(compose_fast(compose_fast(_trans_cube_ ## T, c), \ | ||
| 8 | _trans_cube_ ## T ## _inverse)) | ||
| 9 | |||
| 10 | _static int permsign(uint8_t *, int); | ||
| 11 | _static uint8_t readco(const char *); | ||
| 12 | _static uint8_t readcp(const char *); | ||
| 13 | _static uint8_t readeo(const char *); | ||
| 14 | _static uint8_t readep(const char *); | ||
| 15 | _static cube_t readcube_H48(const char *); | ||
| 16 | _static uint8_t readpiece_LST(const char **); | ||
| 17 | _static cube_t readcube_LST(const char *); | ||
| 18 | _static int writepiece_LST(uint8_t, char *); | ||
| 19 | _static void writecube_H48(cube_t, char *); | ||
| 20 | _static void writecube_LST(cube_t, char *); | ||
| 21 | _static uint8_t readmove(char); | ||
| 22 | _static uint8_t readmodifier(char); | ||
| 23 | _static uint8_t readtrans(const char *); | ||
| 24 | _static int writemoves(uint8_t *, int, char *); | ||
| 25 | _static void writetrans(uint8_t, char *); | ||
| 26 | _static cube_fast_t move(cube_fast_t, uint8_t); | ||
| 27 | _static cube_fast_t transform(cube_fast_t, uint8_t); | ||
| 28 | |||
| 29 | cube_t | ||
| 30 | solvedcube(void) | ||
| 31 | { | ||
| 32 | return solved; | ||
| 33 | } | ||
| 34 | |||
| 35 | bool | ||
| 36 | isconsistent(cube_t cube) | ||
| 37 | { | ||
| 38 | uint8_t i, p, e, piece; | ||
| 39 | bool found[12]; | ||
| 40 | |||
| 41 | for (i = 0; i < 12; i++) | ||
| 42 | found[i] = false; | ||
| 43 | for (i = 0; i < 12; i++) { | ||
| 44 | piece = cube.edge[i]; | ||
| 45 | p = piece & _pbits; | ||
| 46 | e = piece & _eobit; | ||
| 47 | if (p >= 12) | ||
| 48 | goto inconsistent_ep; | ||
| 49 | if (e != 0 && e != _eobit) | ||
| 50 | goto inconsistent_eo; | ||
| 51 | found[p] = true; | ||
| 52 | } | ||
| 53 | for (i = 0; i < 12; i++) | ||
| 54 | if (!found[i]) | ||
| 55 | goto inconsistent_ep; | ||
| 56 | |||
| 57 | for (i = 0; i < 8; i++) | ||
| 58 | found[i] = false; | ||
| 59 | for (i = 0; i < 8; i++) { | ||
| 60 | piece = cube.corner[i]; | ||
| 61 | p = piece & _pbits; | ||
| 62 | e = piece & _cobits; | ||
| 63 | if (p >= 8) | ||
| 64 | goto inconsistent_cp; | ||
| 65 | if (e != 0 && e != _ctwist_cw && e != _ctwist_ccw) | ||
| 66 | goto inconsistent_co; | ||
| 67 | found[p] = true; | ||
| 68 | } | ||
| 69 | for (i = 0; i < 8; i++) | ||
| 70 | if (!found[i]) | ||
| 71 | goto inconsistent_co; | ||
| 72 | |||
| 73 | return true; | ||
| 74 | |||
| 75 | inconsistent_ep: | ||
| 76 | DBG_LOG("Inconsistent EP\n"); | ||
| 77 | return false; | ||
| 78 | inconsistent_cp: | ||
| 79 | DBG_LOG("Inconsistent CP\n"); | ||
| 80 | return false; | ||
| 81 | inconsistent_eo: | ||
| 82 | DBG_LOG("Inconsistent EO\n"); | ||
| 83 | return false; | ||
| 84 | inconsistent_co: | ||
| 85 | DBG_LOG("Inconsistent CO\n"); | ||
| 86 | return false; | ||
| 87 | } | ||
| 88 | |||
| 89 | bool | ||
| 90 | issolvable(cube_t cube) | ||
| 91 | { | ||
| 92 | uint8_t i, eo, co, piece, edges[12], corners[8]; | ||
| 93 | |||
| 94 | DBG_ASSERT(isconsistent(cube), false, | ||
| 95 | "issolvable: cube is inconsistent\n"); | ||
| 96 | |||
| 97 | for (i = 0; i < 12; i++) | ||
| 98 | edges[i] = cube.edge[i] & _pbits; | ||
| 99 | for (i = 0; i < 8; i++) | ||
| 100 | corners[i] = cube.corner[i] & _pbits; | ||
| 101 | |||
| 102 | if (permsign(edges, 12) != permsign(corners, 8)) | ||
| 103 | goto issolvable_parity; | ||
| 104 | |||
| 105 | eo = 0; | ||
| 106 | for (i = 0; i < 12; i++) { | ||
| 107 | piece = cube.edge[i]; | ||
| 108 | eo += (piece & _eobit) >> _eoshift; | ||
| 109 | } | ||
| 110 | if (eo % 2 != 0) | ||
| 111 | goto issolvable_eo; | ||
| 112 | |||
| 113 | co = 0; | ||
| 114 | for (i = 0; i < 8; i++) { | ||
| 115 | piece = cube.corner[i]; | ||
| 116 | co += (piece & _cobits) >> _coshift; | ||
| 117 | } | ||
| 118 | if (co % 3 != 0) | ||
| 119 | goto issolvable_co; | ||
| 120 | |||
| 121 | return true; | ||
| 122 | |||
| 123 | issolvable_parity: | ||
| 124 | DBG_LOG("EP and CP parities are different\n"); | ||
| 125 | return false; | ||
| 126 | issolvable_eo: | ||
| 127 | DBG_LOG("Odd number of flipped edges\n"); | ||
| 128 | return false; | ||
| 129 | issolvable_co: | ||
| 130 | DBG_LOG("Sum of corner orientation is not multiple of 3\n"); | ||
| 131 | return false; | ||
| 132 | } | ||
| 133 | |||
| 134 | bool | ||
| 135 | issolved(cube_t cube) | ||
| 136 | { | ||
| 137 | return equal(cube, solved); | ||
| 138 | } | ||
| 139 | |||
| 140 | bool | ||
| 141 | equal(cube_t c1, cube_t c2) | ||
| 142 | { | ||
| 143 | int i; | ||
| 144 | bool ret; | ||
| 145 | |||
| 146 | ret = true; | ||
| 147 | for (i = 0; i < 8; i++) | ||
| 148 | ret = ret && c1.corner[i] == c2.corner[i]; | ||
| 149 | for (i = 0; i < 12; i++) | ||
| 150 | ret = ret && c1.edge[i] == c2.edge[i]; | ||
| 151 | |||
| 152 | return ret; | ||
| 153 | } | ||
| 154 | |||
| 155 | bool | ||
| 156 | iserror(cube_t cube) | ||
| 157 | { | ||
| 158 | return equal(cube, zero); | ||
| 159 | } | ||
| 160 | |||
| 161 | cube_t | ||
| 162 | compose(cube_t c1, cube_t c2) | ||
| 163 | { | ||
| 164 | DBG_ASSERT(isconsistent(c1) && isconsistent(c2), | ||
| 165 | zero, "compose error: inconsistent cube\n") | ||
| 166 | |||
| 167 | return fasttocube(compose_fast(cubetofast(c1), cubetofast(c2))); | ||
| 168 | } | ||
| 169 | |||
| 170 | cube_t | ||
| 171 | inverse(cube_t cube) | ||
| 172 | { | ||
| 173 | cube_t ret; | ||
| 174 | uint8_t i, piece, orien; | ||
| 175 | |||
| 176 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 177 | "inverse error: inconsistent cube\n"); | ||
| 178 | |||
| 179 | ret = zero; | ||
| 180 | |||
| 181 | for (i = 0; i < 12; i++) { | ||
| 182 | piece = cube.edge[i]; | ||
| 183 | orien = piece & _eobit; | ||
| 184 | ret.edge[piece & _pbits] = i | orien; | ||
| 185 | } | ||
| 186 | |||
| 187 | for (i = 0; i < 8; i++) { | ||
| 188 | piece = cube.corner[i]; | ||
| 189 | orien = ((piece << 1) | (piece >> 1)) & _cobits2; | ||
| 190 | ret.corner[piece & _pbits] = i | orien; | ||
| 191 | } | ||
| 192 | |||
| 193 | return ret; | ||
| 194 | } | ||
| 195 | |||
| 196 | cube_t | ||
| 197 | applymoves(cube_t cube, const char *buf) | ||
| 198 | { | ||
| 199 | cube_fast_t fast; | ||
| 200 | uint8_t r, m; | ||
| 201 | const char *b; | ||
| 202 | |||
| 203 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 204 | "move error: inconsistent cube\n"); | ||
| 205 | |||
| 206 | fast = cubetofast(cube); | ||
| 207 | |||
| 208 | for (b = buf; *b != '\0'; b++) { | ||
| 209 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 210 | b++; | ||
| 211 | if (*b == '\0') | ||
| 212 | goto applymoves_finish; | ||
| 213 | if ((r = readmove(*b)) == _error) | ||
| 214 | goto applymoves_error; | ||
| 215 | if ((m = readmodifier(*(b+1))) != 0) | ||
| 216 | b++; | ||
| 217 | fast = move(fast, r + m); | ||
| 218 | } | ||
| 219 | |||
| 220 | applymoves_finish: | ||
| 221 | return fasttocube(fast); | ||
| 222 | |||
| 223 | applymoves_error: | ||
| 224 | DBG_LOG("applymoves error\n"); | ||
| 225 | return zero; | ||
| 226 | } | ||
| 227 | |||
| 228 | cube_t | ||
| 229 | applytrans(cube_t cube, const char *buf) | ||
| 230 | { | ||
| 231 | cube_fast_t fast; | ||
| 232 | uint8_t t; | ||
| 233 | |||
| 234 | DBG_ASSERT(isconsistent(cube), zero, | ||
| 235 | "transformation error: inconsistent cube\n"); | ||
| 236 | |||
| 237 | t = readtrans(buf); | ||
| 238 | fast = cubetofast(cube); | ||
| 239 | fast = transform(fast, t); | ||
| 240 | |||
| 241 | return fasttocube(fast); | ||
| 242 | } | ||
| 243 | |||
| 244 | cube_t | ||
| 245 | readcube(const char *format, const char *buf) | ||
| 246 | { | ||
| 247 | cube_t cube; | ||
| 248 | |||
| 249 | if (!strcmp(format, "H48")) { | ||
| 250 | cube = readcube_H48(buf); | ||
| 251 | } else if (!strcmp(format, "LST")) { | ||
| 252 | cube = readcube_LST(buf); | ||
| 253 | } else { | ||
| 254 | DBG_LOG("Cannot read cube in the given format\n"); | ||
| 255 | cube = zero; | ||
| 256 | } | ||
| 257 | |||
| 258 | return cube; | ||
| 259 | } | ||
| 260 | |||
| 261 | void | ||
| 262 | writecube(const char *format, cube_t cube, char *buf) | ||
| 263 | { | ||
| 264 | char *errormsg; | ||
| 265 | size_t len; | ||
| 266 | |||
| 267 | if (!isconsistent(cube)) { | ||
| 268 | errormsg = "ERROR: cannot write inconsistent cube"; | ||
| 269 | goto writecube_error; | ||
| 270 | } | ||
| 271 | |||
| 272 | if (!strcmp(format, "H48")) { | ||
| 273 | writecube_H48(cube, buf); | ||
| 274 | } else if (!strcmp(format, "LST")) { | ||
| 275 | writecube_LST(cube, buf); | ||
| 276 | } else { | ||
| 277 | errormsg = "ERROR: cannot write cube in the given format"; | ||
| 278 | goto writecube_error; | ||
| 279 | } | ||
| 280 | |||
| 281 | return; | ||
| 282 | |||
| 283 | writecube_error: | ||
| 284 | DBG_LOG("writecube error, see stdout for details\n"); | ||
| 285 | len = strlen(errormsg); | ||
| 286 | memcpy(buf, errormsg, len); | ||
| 287 | buf[len] = '\n'; | ||
| 288 | buf[len+1] = '\0'; | ||
| 289 | } | ||
| 290 | |||
| 291 | _static int | ||
| 292 | permsign(uint8_t *a, int n) | ||
| 293 | { | ||
| 294 | int i, j; | ||
| 295 | uint8_t ret = 0; | ||
| 296 | |||
| 297 | for (i = 0; i < n; i++) | ||
| 298 | for (j = i+1; j < n; j++) | ||
| 299 | ret += a[i] > a[j] ? 1 : 0; | ||
| 300 | |||
| 301 | return ret % 2; | ||
| 302 | } | ||
| 303 | |||
| 304 | _static uint8_t | ||
| 305 | readco(const char *str) | ||
| 306 | { | ||
| 307 | if (*str == '0') | ||
| 308 | return 0; | ||
| 309 | if (*str == '1') | ||
| 310 | return _ctwist_cw; | ||
| 311 | if (*str == '2') | ||
| 312 | return _ctwist_ccw; | ||
| 313 | |||
| 314 | DBG_LOG("Error reading CO\n"); | ||
| 315 | return _error; | ||
| 316 | } | ||
| 317 | |||
| 318 | _static uint8_t | ||
| 319 | readcp(const char *str) | ||
| 320 | { | ||
| 321 | uint8_t c; | ||
| 322 | |||
| 323 | for (c = 0; c < 8; c++) | ||
| 324 | if (!strncmp(str, cornerstr[c], 3) || | ||
| 325 | !strncmp(str, cornerstralt[c], 3)) | ||
| 326 | return c; | ||
| 327 | |||
| 328 | DBG_LOG("Error reading CP\n"); | ||
| 329 | return _error; | ||
| 330 | } | ||
| 331 | |||
| 332 | _static uint8_t | ||
| 333 | readeo(const char *str) | ||
| 334 | { | ||
| 335 | if (*str == '0') | ||
| 336 | return 0; | ||
| 337 | if (*str == '1') | ||
| 338 | return _eflip; | ||
| 339 | |||
| 340 | DBG_LOG("Error reading EO\n"); | ||
| 341 | return _error; | ||
| 342 | } | ||
| 343 | |||
| 344 | _static uint8_t | ||
| 345 | readep(const char *str) | ||
| 346 | { | ||
| 347 | uint8_t e; | ||
| 348 | |||
| 349 | for (e = 0; e < 12; e++) | ||
| 350 | if (!strncmp(str, edgestr[e], 2)) | ||
| 351 | return e; | ||
| 352 | |||
| 353 | DBG_LOG("Error reading EP\n"); | ||
| 354 | return _error; | ||
| 355 | } | ||
| 356 | |||
| 357 | _static cube_t | ||
| 358 | readcube_H48(const char *buf) | ||
| 359 | { | ||
| 360 | int i; | ||
| 361 | uint8_t piece, orient; | ||
| 362 | cube_t ret = {0}; | ||
| 363 | const char *b; | ||
| 364 | |||
| 365 | b = buf; | ||
| 366 | |||
| 367 | for (i = 0; i < 12; i++) { | ||
| 368 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 369 | b++; | ||
| 370 | if ((piece = readep(b)) == _error) | ||
| 371 | return zero; | ||
| 372 | b += 2; | ||
| 373 | if ((orient = readeo(b)) == _error) | ||
| 374 | return zero; | ||
| 375 | b++; | ||
| 376 | ret.edge[i] = piece | orient; | ||
| 377 | } | ||
| 378 | for (i = 0; i < 8; i++) { | ||
| 379 | while (*b == ' ' || *b == '\t' || *b == '\n') | ||
| 380 | b++; | ||
| 381 | if ((piece = readcp(b)) == _error) | ||
| 382 | return zero; | ||
| 383 | b += 3; | ||
| 384 | if ((orient = readco(b)) == _error) | ||
| 385 | return zero; | ||
| 386 | b++; | ||
| 387 | ret.corner[i] = piece | orient; | ||
| 388 | } | ||
| 389 | |||
| 390 | return ret; | ||
| 391 | } | ||
| 392 | |||
| 393 | _static uint8_t | ||
| 394 | readpiece_LST(const char **b) | ||
| 395 | { | ||
| 396 | uint8_t ret; | ||
| 397 | bool read; | ||
| 398 | |||
| 399 | while (**b == ',' || **b == ' ' || **b == '\t' || **b == '\n') | ||
| 400 | (*b)++; | ||
| 401 | |||
| 402 | for (ret = 0, read = false; **b >= '0' && **b <= '9'; (*b)++) { | ||
| 403 | read = true; | ||
| 404 | ret = ret * 10 + (**b) - '0'; | ||
| 405 | } | ||
| 406 | |||
| 407 | return read ? ret : _error; | ||
| 408 | } | ||
| 409 | |||
| 410 | _static cube_t | ||
| 411 | readcube_LST(const char *buf) | ||
| 412 | { | ||
| 413 | int i; | ||
| 414 | cube_t ret = {0}; | ||
| 415 | |||
| 416 | for (i = 0; i < 8; i++) | ||
| 417 | ret.corner[i] = readpiece_LST(&buf); | ||
| 418 | |||
| 419 | for (i = 0; i < 12; i++) | ||
| 420 | ret.edge[i] = readpiece_LST(&buf); | ||
| 421 | |||
| 422 | return ret; | ||
| 423 | } | ||
| 424 | |||
| 425 | _static int | ||
| 426 | writepiece_LST(uint8_t piece, char *buf) | ||
| 427 | { | ||
| 428 | char digits[3]; | ||
| 429 | int i, len = 0; | ||
| 430 | |||
| 431 | while (piece != 0) { | ||
| 432 | digits[len++] = (piece % 10) + '0'; | ||
| 433 | piece /= 10; | ||
| 434 | } | ||
| 435 | |||
| 436 | if (len == 0) | ||
| 437 | digits[len++] = '0'; | ||
| 438 | |||
| 439 | for (i = 0; i < len; i++) | ||
| 440 | buf[i] = digits[len-i-1]; | ||
| 441 | |||
| 442 | buf[len] = ','; | ||
| 443 | buf[len+1] = ' '; | ||
| 444 | |||
| 445 | return len+2; | ||
| 446 | } | ||
| 447 | |||
| 448 | _static void | ||
| 449 | writecube_H48(cube_t cube, char *buf) | ||
| 450 | { | ||
| 451 | uint8_t piece, perm, orient; | ||
| 452 | int i; | ||
| 453 | |||
| 454 | for (i = 0; i < 12; i++) { | ||
| 455 | piece = cube.edge[i]; | ||
| 456 | perm = piece & _pbits; | ||
| 457 | orient = (piece & _eobit) >> _eoshift; | ||
| 458 | buf[4*i ] = edgestr[perm][0]; | ||
| 459 | buf[4*i + 1] = edgestr[perm][1]; | ||
| 460 | buf[4*i + 2] = orient + '0'; | ||
| 461 | buf[4*i + 3] = ' '; | ||
| 462 | } | ||
| 463 | for (i = 0; i < 8; i++) { | ||
| 464 | piece = cube.corner[i]; | ||
| 465 | perm = piece & _pbits; | ||
| 466 | orient = (piece & _cobits) >> _coshift; | ||
| 467 | buf[48 + 5*i ] = cornerstr[perm][0]; | ||
| 468 | buf[48 + 5*i + 1] = cornerstr[perm][1]; | ||
| 469 | buf[48 + 5*i + 2] = cornerstr[perm][2]; | ||
| 470 | buf[48 + 5*i + 3] = orient + '0'; | ||
| 471 | buf[48 + 5*i + 4] = ' '; | ||
| 472 | } | ||
| 473 | |||
| 474 | buf[48+39] = '\0'; | ||
| 475 | } | ||
| 476 | |||
| 477 | _static void | ||
| 478 | writecube_LST(cube_t cube, char *buf) | ||
| 479 | { | ||
| 480 | int i, ptr; | ||
| 481 | uint8_t piece; | ||
| 482 | |||
| 483 | ptr = 0; | ||
| 484 | |||
| 485 | for (i = 0; i < 8; i++) { | ||
| 486 | piece = cube.corner[i]; | ||
| 487 | ptr += writepiece_LST(piece, buf + ptr); | ||
| 488 | } | ||
| 489 | |||
| 490 | for (i = 0; i < 12; i++) { | ||
| 491 | piece = cube.edge[i]; | ||
| 492 | ptr += writepiece_LST(piece, buf + ptr); | ||
| 493 | } | ||
| 494 | |||
| 495 | *(buf+ptr-2) = 0; | ||
| 496 | } | ||
| 497 | |||
| 498 | _static uint8_t | ||
| 499 | readmove(char c) | ||
| 500 | { | ||
| 501 | switch (c) { | ||
| 502 | case 'U': | ||
| 503 | return _move_U; | ||
| 504 | case 'D': | ||
| 505 | return _move_D; | ||
| 506 | case 'R': | ||
| 507 | return _move_R; | ||
| 508 | case 'L': | ||
| 509 | return _move_L; | ||
| 510 | case 'F': | ||
| 511 | return _move_F; | ||
| 512 | case 'B': | ||
| 513 | return _move_B; | ||
| 514 | default: | ||
| 515 | return _error; | ||
| 516 | } | ||
| 517 | } | ||
| 518 | |||
| 519 | _static uint8_t | ||
| 520 | readmodifier(char c) | ||
| 521 | { | ||
| 522 | switch (c) { | ||
| 523 | case '1': /* Fallthrough */ | ||
| 524 | case '2': /* Fallthrough */ | ||
| 525 | case '3': | ||
| 526 | return c - '0' - 1; | ||
| 527 | case '\'': | ||
| 528 | return 2; | ||
| 529 | default: | ||
| 530 | return 0; | ||
| 531 | } | ||
| 532 | } | ||
| 533 | |||
| 534 | _static uint8_t | ||
| 535 | readtrans(const char *buf) | ||
| 536 | { | ||
| 537 | uint8_t t; | ||
| 538 | |||
| 539 | for (t = 0; t < 48; t++) | ||
| 540 | if (!strncmp(buf, transstr[t], 11)) | ||
| 541 | return t; | ||
| 542 | |||
| 543 | DBG_LOG("readtrans error\n"); | ||
| 544 | return _error; | ||
| 545 | } | ||
| 546 | |||
| 547 | _static int | ||
| 548 | writemoves(uint8_t *m, int n, char *buf) | ||
| 549 | { | ||
| 550 | int i; | ||
| 551 | size_t len; | ||
| 552 | const char *s; | ||
| 553 | char *b; | ||
| 554 | |||
| 555 | for (i = 0, b = buf; i < n; i++, b++) { | ||
| 556 | s = movestr[m[i]]; | ||
| 557 | len = strlen(s); | ||
| 558 | memcpy(b, s, len); | ||
| 559 | b += len; | ||
| 560 | *b = ' '; | ||
| 561 | } | ||
| 562 | |||
| 563 | if (b != buf) | ||
| 564 | b--; /* Remove last space */ | ||
| 565 | *b = '\0'; | ||
| 566 | |||
| 567 | return b - buf; | ||
| 568 | } | ||
| 569 | |||
| 570 | _static void | ||
| 571 | writetrans(uint8_t t, char *buf) | ||
| 572 | { | ||
| 573 | if (t >= 48) | ||
| 574 | memcpy(buf, "error trans", 11); | ||
| 575 | else | ||
| 576 | memcpy(buf, transstr[t], 11); | ||
| 577 | buf[11] = '\0'; | ||
| 578 | } | ||
| 579 | |||
| 580 | _static cube_fast_t | ||
| 581 | move(cube_fast_t c, uint8_t m) | ||
| 582 | { | ||
| 583 | switch (m) { | ||
| 584 | case _move_U: | ||
| 585 | return _move(U, c); | ||
| 586 | case _move_U2: | ||
| 587 | return _move(U2, c); | ||
| 588 | case _move_U3: | ||
| 589 | return _move(U3, c); | ||
| 590 | case _move_D: | ||
| 591 | return _move(D, c); | ||
| 592 | case _move_D2: | ||
| 593 | return _move(D2, c); | ||
| 594 | case _move_D3: | ||
| 595 | return _move(D3, c); | ||
| 596 | case _move_R: | ||
| 597 | return _move(R, c); | ||
| 598 | case _move_R2: | ||
| 599 | return _move(R2, c); | ||
| 600 | case _move_R3: | ||
| 601 | return _move(R3, c); | ||
| 602 | case _move_L: | ||
| 603 | return _move(L, c); | ||
| 604 | case _move_L2: | ||
| 605 | return _move(L2, c); | ||
| 606 | case _move_L3: | ||
| 607 | return _move(L3, c); | ||
| 608 | case _move_F: | ||
| 609 | return _move(F, c); | ||
| 610 | case _move_F2: | ||
| 611 | return _move(F2, c); | ||
| 612 | case _move_F3: | ||
| 613 | return _move(F3, c); | ||
| 614 | case _move_B: | ||
| 615 | return _move(B, c); | ||
| 616 | case _move_B2: | ||
| 617 | return _move(B2, c); | ||
| 618 | case _move_B3: | ||
| 619 | return _move(B3, c); | ||
| 620 | default: | ||
| 621 | DBG_LOG("move error, unknown move\n"); | ||
| 622 | return zero_fast; | ||
| 623 | } | ||
| 624 | } | ||
| 625 | |||
| 626 | _static cube_fast_t | ||
| 627 | transform(cube_fast_t c, uint8_t t) | ||
| 628 | { | ||
| 629 | switch (t) { | ||
| 630 | case _trans_UFr: | ||
| 631 | return _trans_rotation(UFr, c); | ||
| 632 | case _trans_ULr: | ||
| 633 | return _trans_rotation(ULr, c); | ||
| 634 | case _trans_UBr: | ||
| 635 | return _trans_rotation(UBr, c); | ||
| 636 | case _trans_URr: | ||
| 637 | return _trans_rotation(URr, c); | ||
| 638 | case _trans_DFr: | ||
| 639 | return _trans_rotation(DFr, c); | ||
| 640 | case _trans_DLr: | ||
| 641 | return _trans_rotation(DLr, c); | ||
| 642 | case _trans_DBr: | ||
| 643 | return _trans_rotation(DBr, c); | ||
| 644 | case _trans_DRr: | ||
| 645 | return _trans_rotation(DRr, c); | ||
| 646 | case _trans_RUr: | ||
| 647 | return _trans_rotation(RUr, c); | ||
| 648 | case _trans_RFr: | ||
| 649 | return _trans_rotation(RFr, c); | ||
| 650 | case _trans_RDr: | ||
| 651 | return _trans_rotation(RDr, c); | ||
| 652 | case _trans_RBr: | ||
| 653 | return _trans_rotation(RBr, c); | ||
| 654 | case _trans_LUr: | ||
| 655 | return _trans_rotation(LUr, c); | ||
| 656 | case _trans_LFr: | ||
| 657 | return _trans_rotation(LFr, c); | ||
| 658 | case _trans_LDr: | ||
| 659 | return _trans_rotation(LDr, c); | ||
| 660 | case _trans_LBr: | ||
| 661 | return _trans_rotation(LBr, c); | ||
| 662 | case _trans_FUr: | ||
| 663 | return _trans_rotation(FUr, c); | ||
| 664 | case _trans_FRr: | ||
| 665 | return _trans_rotation(FRr, c); | ||
| 666 | case _trans_FDr: | ||
| 667 | return _trans_rotation(FDr, c); | ||
| 668 | case _trans_FLr: | ||
| 669 | return _trans_rotation(FLr, c); | ||
| 670 | case _trans_BUr: | ||
| 671 | return _trans_rotation(BUr, c); | ||
| 672 | case _trans_BRr: | ||
| 673 | return _trans_rotation(BRr, c); | ||
| 674 | case _trans_BDr: | ||
| 675 | return _trans_rotation(BDr, c); | ||
| 676 | case _trans_BLr: | ||
| 677 | return _trans_rotation(BLr, c); | ||
| 678 | case _trans_UFm: | ||
| 679 | return _trans_mirrored(UFm, c); | ||
| 680 | case _trans_ULm: | ||
| 681 | return _trans_mirrored(ULm, c); | ||
| 682 | case _trans_UBm: | ||
| 683 | return _trans_mirrored(UBm, c); | ||
| 684 | case _trans_URm: | ||
| 685 | return _trans_mirrored(URm, c); | ||
| 686 | case _trans_DFm: | ||
| 687 | return _trans_mirrored(DFm, c); | ||
| 688 | case _trans_DLm: | ||
| 689 | return _trans_mirrored(DLm, c); | ||
| 690 | case _trans_DBm: | ||
| 691 | return _trans_mirrored(DBm, c); | ||
| 692 | case _trans_DRm: | ||
| 693 | return _trans_mirrored(DRm, c); | ||
| 694 | case _trans_RUm: | ||
| 695 | return _trans_mirrored(RUm, c); | ||
| 696 | case _trans_RFm: | ||
| 697 | return _trans_mirrored(RFm, c); | ||
| 698 | case _trans_RDm: | ||
| 699 | return _trans_mirrored(RDm, c); | ||
| 700 | case _trans_RBm: | ||
| 701 | return _trans_mirrored(RBm, c); | ||
| 702 | case _trans_LUm: | ||
| 703 | return _trans_mirrored(LUm, c); | ||
| 704 | case _trans_LFm: | ||
| 705 | return _trans_mirrored(LFm, c); | ||
| 706 | case _trans_LDm: | ||
| 707 | return _trans_mirrored(LDm, c); | ||
| 708 | case _trans_LBm: | ||
| 709 | return _trans_mirrored(LBm, c); | ||
| 710 | case _trans_FUm: | ||
| 711 | return _trans_mirrored(FUm, c); | ||
| 712 | case _trans_FRm: | ||
| 713 | return _trans_mirrored(FRm, c); | ||
| 714 | case _trans_FDm: | ||
| 715 | return _trans_mirrored(FDm, c); | ||
| 716 | case _trans_FLm: | ||
| 717 | return _trans_mirrored(FLm, c); | ||
| 718 | case _trans_BUm: | ||
| 719 | return _trans_mirrored(BUm, c); | ||
| 720 | case _trans_BRm: | ||
| 721 | return _trans_mirrored(BRm, c); | ||
| 722 | case _trans_BDm: | ||
| 723 | return _trans_mirrored(BDm, c); | ||
| 724 | case _trans_BLm: | ||
| 725 | return _trans_mirrored(BLm, c); | ||
| 726 | default: | ||
| 727 | DBG_LOG("transform error, unknown transformation\n"); | ||
| 728 | return zero_fast; | ||
| 729 | } | ||
| 730 | } | ||
diff --git a/src/moves.h b/src/moves.h new file mode 100644 index 0000000..7da6405 --- /dev/null +++ b/src/moves.h | |||
| @@ -0,0 +1,47 @@ | |||
| 1 | _static_inline bool allowednextmove(uint8_t *, uint8_t); | ||
| 2 | _static_inline uint8_t inverse_trans(uint8_t); | ||
| 3 | _static_inline uint8_t movebase(uint8_t); | ||
| 4 | _static_inline uint8_t moveaxis(uint8_t); | ||
| 5 | |||
| 6 | _static bool | ||
| 7 | allowednextmove(uint8_t *moves, uint8_t n) | ||
| 8 | { | ||
| 9 | uint8_t base[3], axis[3]; | ||
| 10 | |||
| 11 | if (n < 2) | ||
| 12 | return true; | ||
| 13 | |||
| 14 | base[0] = movebase(moves[n-1]); | ||
| 15 | axis[0] = moveaxis(moves[n-1]); | ||
| 16 | base[1] = movebase(moves[n-2]); | ||
| 17 | axis[1] = moveaxis(moves[n-2]); | ||
| 18 | |||
| 19 | if (base[0] == base[1] || (axis[0] == axis[1] && base[0] < base[1])) | ||
| 20 | return false; | ||
| 21 | |||
| 22 | if (n == 2) | ||
| 23 | return true; | ||
| 24 | |||
| 25 | base[2] = movebase(moves[n-3]); | ||
| 26 | axis[2] = moveaxis(moves[n-3]); | ||
| 27 | |||
| 28 | return axis[1] != axis[2] || base[0] != base[2]; | ||
| 29 | } | ||
| 30 | |||
| 31 | _static_inline uint8_t | ||
| 32 | inverse_trans(uint8_t t) | ||
| 33 | { | ||
| 34 | return inverse_trans_table[t]; | ||
| 35 | } | ||
| 36 | |||
| 37 | _static_inline uint8_t | ||
| 38 | movebase(uint8_t move) | ||
| 39 | { | ||
| 40 | return move / 3; | ||
| 41 | } | ||
| 42 | |||
| 43 | _static_inline uint8_t | ||
| 44 | moveaxis(uint8_t move) | ||
| 45 | { | ||
| 46 | return move / 6; | ||
| 47 | } | ||
diff --git a/src/solve_generic.h b/src/solve_generic.h new file mode 100644 index 0000000..925aa33 --- /dev/null +++ b/src/solve_generic.h | |||
| @@ -0,0 +1,259 @@ | |||
| 1 | typedef struct { | ||
| 2 | cube_fast_t cube; | ||
| 3 | uint8_t depth; | ||
| 4 | int64_t maxsols; | ||
| 5 | char **nextsol; | ||
| 6 | int64_t *nsols; | ||
| 7 | uint8_t nmoves; | ||
| 8 | uint8_t moves[20]; | ||
| 9 | uint8_t (*estimate)(cube_fast_t); | ||
| 10 | } dfsarg_generic_t; | ||
| 11 | |||
| 12 | _static void solve_generic_appendsolution(dfsarg_generic_t *); | ||
| 13 | _static int solve_generic_dfs(dfsarg_generic_t *); | ||
| 14 | _static int64_t solve_generic(cube_t, const char *, int8_t, int8_t, int64_t, | ||
| 15 | int8_t, char *, uint8_t (*)(cube_fast_t)); | ||
| 16 | _static uint8_t estimate_simple(cube_fast_t); | ||
| 17 | _static int64_t solve_simple(cube_t, int8_t, int8_t, int64_t, int8_t, char *); | ||
| 18 | |||
| 19 | int64_t | ||
| 20 | solve( | ||
| 21 | cube_t cube, | ||
| 22 | const char *solver, | ||
| 23 | const char *options, | ||
| 24 | const char *nisstype, | ||
| 25 | int8_t minmoves, | ||
| 26 | int8_t maxmoves, | ||
| 27 | int64_t maxsols, | ||
| 28 | int8_t optimal, | ||
| 29 | const void *data, | ||
| 30 | char *solutions | ||
| 31 | ) | ||
| 32 | { | ||
| 33 | DBG_WARN(!strcmp(options, ""), | ||
| 34 | "solve: 'options' not implemented yet, ignoring\n"); | ||
| 35 | |||
| 36 | DBG_WARN(!strcmp(nisstype, ""), | ||
| 37 | "solve: NISS not implemented yet, ignoring 'nisstype'\n"); | ||
| 38 | |||
| 39 | DBG_WARN(data == NULL, | ||
| 40 | "solve: 'data' not implemented yet, ignoring\n"); | ||
| 41 | |||
| 42 | if (!strcmp(solver, "optimal") || !strcmp(solver, "simple")) { | ||
| 43 | return solve_simple( | ||
| 44 | cube, | ||
| 45 | minmoves, | ||
| 46 | maxmoves, | ||
| 47 | maxsols, | ||
| 48 | optimal, | ||
| 49 | solutions | ||
| 50 | ); | ||
| 51 | } else { | ||
| 52 | DBG_LOG("solve: unknown solver '%s'\n", solver); | ||
| 53 | return -1; | ||
| 54 | } | ||
| 55 | |||
| 56 | DBG_LOG("solve: error\n"); | ||
| 57 | return -1; | ||
| 58 | } | ||
| 59 | |||
| 60 | void | ||
| 61 | multisolve( | ||
| 62 | int n, | ||
| 63 | cube_t *cube, | ||
| 64 | const char *solver, | ||
| 65 | const void *data, | ||
| 66 | char *sols | ||
| 67 | ) | ||
| 68 | { | ||
| 69 | char *s; | ||
| 70 | int i; | ||
| 71 | |||
| 72 | s = sols; | ||
| 73 | for (i = 0; i < n; i++) { | ||
| 74 | solve(cube[i], solver, "", "normal", 0, -1, 1, 0, NULL, s); | ||
| 75 | while (s++); | ||
| 76 | } | ||
| 77 | } | ||
| 78 | |||
| 79 | int64_t | ||
| 80 | gendata(const char *solver, void *data) | ||
| 81 | { | ||
| 82 | DBG_LOG("gendata: not implemented yet\n"); | ||
| 83 | |||
| 84 | return -1; | ||
| 85 | } | ||
| 86 | |||
| 87 | _static void | ||
| 88 | solve_generic_appendsolution(dfsarg_generic_t *arg) | ||
| 89 | { | ||
| 90 | int strl; | ||
| 91 | |||
| 92 | strl = writemoves(arg->moves, arg->depth, *arg->nextsol); | ||
| 93 | DBG_LOG("Solution found: %s\n", *arg->nextsol); | ||
| 94 | *arg->nextsol += strl; | ||
| 95 | **arg->nextsol = '\n'; | ||
| 96 | (*arg->nextsol)++; | ||
| 97 | (*arg->nsols)++; | ||
| 98 | } | ||
| 99 | |||
| 100 | _static int | ||
| 101 | solve_generic_dfs(dfsarg_generic_t *arg) | ||
| 102 | { | ||
| 103 | dfsarg_generic_t nextarg; | ||
| 104 | uint8_t m, bound; | ||
| 105 | int64_t ret; | ||
| 106 | |||
| 107 | if (!allowednextmove(arg->moves, arg->nmoves)) | ||
| 108 | return 0; | ||
| 109 | |||
| 110 | if (arg->nmoves > 0) | ||
| 111 | arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); | ||
| 112 | |||
| 113 | bound = arg->estimate(arg->cube); | ||
| 114 | if (*arg->nsols == arg->maxsols || bound + arg->nmoves > arg->depth) | ||
| 115 | return 0; | ||
| 116 | |||
| 117 | if (bound == 0) { | ||
| 118 | if (arg->nmoves != arg->depth) | ||
| 119 | return 0; | ||
| 120 | solve_generic_appendsolution(arg); | ||
| 121 | return 1; | ||
| 122 | } | ||
| 123 | |||
| 124 | /* memcpy(&nextarg, arg, sizeof(dfsarg_generic_t)); */ | ||
| 125 | nextarg = *arg; | ||
| 126 | nextarg.nmoves = arg->nmoves + 1; | ||
| 127 | for (m = 0, ret = 0; m < 18; m++) { | ||
| 128 | nextarg.cube = arg->cube; | ||
| 129 | nextarg.moves[arg->nmoves] = m; | ||
| 130 | ret += solve_generic_dfs(&nextarg); | ||
| 131 | } | ||
| 132 | |||
| 133 | return ret; | ||
| 134 | } | ||
| 135 | |||
| 136 | _static int64_t | ||
| 137 | solve_generic( | ||
| 138 | cube_t cube, | ||
| 139 | const char *nisstype, | ||
| 140 | /* TODO: handle NISS */ | ||
| 141 | int8_t minmoves, | ||
| 142 | int8_t maxmoves, | ||
| 143 | int64_t maxsols, | ||
| 144 | int8_t optimal, | ||
| 145 | char *sols, | ||
| 146 | uint8_t (*estimate)(cube_fast_t) | ||
| 147 | /* TODO: add validator */ | ||
| 148 | /* TODO: maybe add data for estimate */ | ||
| 149 | /* TODO: add moveset (and allowednext?) */ | ||
| 150 | ) | ||
| 151 | { | ||
| 152 | dfsarg_generic_t arg; | ||
| 153 | int64_t ret, tmp, first; | ||
| 154 | |||
| 155 | if (!issolvable(cube)) { | ||
| 156 | DBG_LOG("solve: cube is not solvable\n"); | ||
| 157 | return -1; | ||
| 158 | } | ||
| 159 | |||
| 160 | if (issolved(cube)) { | ||
| 161 | DBG_LOG("solve: cube is already solved\n"); | ||
| 162 | sols[0] = '\n'; | ||
| 163 | sols[1] = 0; | ||
| 164 | return 1; | ||
| 165 | } | ||
| 166 | |||
| 167 | DBG_WARN(!strcmp(nisstype, ""), | ||
| 168 | "solve: NISS not implemented yet, 'nisstype' ignored\n"); | ||
| 169 | |||
| 170 | if (minmoves < 0) { | ||
| 171 | DBG_LOG("solve: 'minmoves' is negative, setting to 0\n"); | ||
| 172 | minmoves = 0; | ||
| 173 | } | ||
| 174 | |||
| 175 | if (maxmoves < 0) { | ||
| 176 | DBG_LOG("solve: invalid 'maxmoves', setting to 20\n"); | ||
| 177 | maxmoves = 20; | ||
| 178 | } | ||
| 179 | |||
| 180 | if (maxsols < 0) { | ||
| 181 | DBG_LOG("solve: 'maxsols' is negative\n"); | ||
| 182 | return -1; | ||
| 183 | } | ||
| 184 | |||
| 185 | if (maxsols == 0) { | ||
| 186 | DBG_LOG("solve: 'maxsols' is 0\n"); | ||
| 187 | return 0; | ||
| 188 | } | ||
| 189 | |||
| 190 | if (sols == NULL) { | ||
| 191 | DBG_LOG("solve: return parameter 'sols' is NULL\n"); | ||
| 192 | return -1; | ||
| 193 | } | ||
| 194 | |||
| 195 | if (estimate == NULL) { | ||
| 196 | DBG_LOG("solve: 'estimate' is NULL\n"); | ||
| 197 | return -1; | ||
| 198 | } | ||
| 199 | |||
| 200 | arg = (dfsarg_generic_t) { | ||
| 201 | .cube = cubetofast(cube), | ||
| 202 | .maxsols = maxsols, | ||
| 203 | .nextsol = &sols, | ||
| 204 | .nsols = &ret, | ||
| 205 | .nmoves = 0, | ||
| 206 | .moves = {0}, | ||
| 207 | .estimate = estimate, | ||
| 208 | }; | ||
| 209 | |||
| 210 | ret = 0; | ||
| 211 | first = -1; | ||
| 212 | for (arg.depth = minmoves; arg.depth <= maxmoves; arg.depth++) { | ||
| 213 | tmp = solve_generic_dfs(&arg); | ||
| 214 | if (tmp != 0) | ||
| 215 | first = arg.depth; | ||
| 216 | |||
| 217 | DBG_LOG("Found %" PRId64 " solution%s at depth %" PRIu8 "\n", | ||
| 218 | tmp, tmp == 1 ? "" : "s", arg.depth); | ||
| 219 | |||
| 220 | if (ret >= maxsols) | ||
| 221 | break; | ||
| 222 | |||
| 223 | if (optimal >= 0 && first >= 0 && arg.depth - first == optimal) | ||
| 224 | break; | ||
| 225 | } | ||
| 226 | |||
| 227 | DBG_ASSERT(ret <= maxsols, ret, | ||
| 228 | "solve: found more than 'maxsols' solutions\n"); | ||
| 229 | |||
| 230 | return ret; | ||
| 231 | } | ||
| 232 | |||
| 233 | _static uint8_t | ||
| 234 | estimate_simple(cube_fast_t cube) | ||
| 235 | { | ||
| 236 | return issolved_fast(cube) ? 0 : 1; | ||
| 237 | } | ||
| 238 | |||
| 239 | _static int64_t | ||
| 240 | solve_simple( | ||
| 241 | cube_t cube, | ||
| 242 | int8_t minmoves, | ||
| 243 | int8_t maxmoves, | ||
| 244 | int64_t maxsols, | ||
| 245 | int8_t optimal, | ||
| 246 | char *solutions | ||
| 247 | ) | ||
| 248 | { | ||
| 249 | return solve_generic( | ||
| 250 | cube, | ||
| 251 | "", | ||
| 252 | minmoves, | ||
| 253 | maxmoves, | ||
| 254 | maxsols, | ||
| 255 | optimal, | ||
| 256 | solutions, | ||
| 257 | &estimate_simple | ||
| 258 | ); | ||
| 259 | } | ||
diff --git a/src/solve_h48.h b/src/solve_h48.h new file mode 100644 index 0000000..84bea31 --- /dev/null +++ b/src/solve_h48.h | |||
| @@ -0,0 +1,266 @@ | |||
| 1 | #define _esep_ind(i) (i / 8U) | ||
| 2 | #define _esep_shift(i) (4U * (i % 8U)) | ||
| 3 | #define _esep_mask(i) (((1U << 4U) - 1U) << _esep_shift(i)) | ||
| 4 | #define _visited_ind(i) (i / 8U) | ||
| 5 | #define _visited_mask(i) (1U << (i % 8U)) | ||
| 6 | |||
| 7 | typedef struct { | ||
| 8 | cube_fast_t cube; | ||
| 9 | uint8_t *visited; | ||
| 10 | uint8_t *moves; | ||
| 11 | uint8_t nmoves; | ||
| 12 | uint8_t depth; | ||
| 13 | uint16_t *nclasses; | ||
| 14 | uint32_t *cocsepdata; | ||
| 15 | uint32_t *buf32; | ||
| 16 | } dfsarg_gendata_t; | ||
| 17 | |||
| 18 | _static_inline int64_t coord_h48(cube_fast_t, uint32_t *, uint8_t); | ||
| 19 | |||
| 20 | _static size_t gendata_cocsep(void *); | ||
| 21 | _static uint32_t gendata_cocsep_dfs( /* TODO: use dfsarg */ | ||
| 22 | cube_fast_t, uint8_t, uint8_t, uint16_t *, uint32_t *, uint8_t *); | ||
| 23 | |||
| 24 | _static size_t gendata_esep(const void *, void *); | ||
| 25 | _static uint32_t gendata_esep_dfs(dfsarg_gendata_t *); | ||
| 26 | |||
| 27 | _static_inline bool get_visited(const uint8_t *, int64_t); | ||
| 28 | _static_inline void set_visited(uint8_t *, int64_t); | ||
| 29 | _static_inline uint8_t get_esep_pval(const uint32_t *, int64_t); | ||
| 30 | _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t); | ||
| 31 | |||
| 32 | /* h is the number of eo bits used */ | ||
| 33 | _static_inline int64_t | ||
| 34 | coord_h48(cube_fast_t c, uint32_t *cocsepdata, uint8_t h) | ||
| 35 | { | ||
| 36 | cube_fast_t d; | ||
| 37 | int64_t cocsep, coclass, esep, eo, esize, ret; | ||
| 38 | uint32_t data; | ||
| 39 | uint8_t ttrep; | ||
| 40 | |||
| 41 | DBG_ASSERT(h <= 11, -1, "coord_h48: h must be between 0 and 11\n"); | ||
| 42 | |||
| 43 | cocsep = coord_fast_cocsep(c); | ||
| 44 | data = cocsepdata[cocsep]; | ||
| 45 | coclass = (data & (0xFFFFU << 16U)) >> 16U; | ||
| 46 | ttrep = (data & (0xFFU << 8U)) >> 8U; | ||
| 47 | |||
| 48 | d = transform(c, ttrep); /* TODO: transform only edges */ | ||
| 49 | esep = coord_fast_esep(d); | ||
| 50 | eo = coord_fast_eo(d); | ||
| 51 | |||
| 52 | esize = (_12c4 * _8c4) << h; | ||
| 53 | ret = (coclass * esize) + (esep << h) + (eo >> (11-h)); | ||
| 54 | |||
| 55 | return ret; | ||
| 56 | } | ||
| 57 | |||
| 58 | /* | ||
| 59 | Each element of the cocsep table is a uint32_t used as follows: | ||
| 60 | - Lowest 8-bit block: pruning value | ||
| 61 | - Second-lower 8-bit block: "ttrep" (transformation to representative) | ||
| 62 | - Top 16-bit block: symcoord value | ||
| 63 | After the data as described above, more auxiliary information is appended: | ||
| 64 | - A uint32_t representing the number of symmetry classes | ||
| 65 | - A uint32_t representing the highest value of the pruning table | ||
| 66 | - One uint32_t for each "line" of the pruning table, representing the number | ||
| 67 | of positions having that pruning value. | ||
| 68 | */ | ||
| 69 | _static size_t | ||
| 70 | gendata_cocsep(void *buf) | ||
| 71 | { | ||
| 72 | size_t tablesize = _3p7 << 7U; | ||
| 73 | size_t visitedsize = (tablesize + 7U) / 8U; | ||
| 74 | size_t infosize = 12; | ||
| 75 | |||
| 76 | cube_fast_t solved; | ||
| 77 | uint32_t *buf32, *info, cc; | ||
| 78 | uint16_t n; | ||
| 79 | uint8_t i, j, visited[visitedsize]; | ||
| 80 | |||
| 81 | buf32 = (uint32_t *)buf; | ||
| 82 | info = buf32 + tablesize; | ||
| 83 | memset(buf32, 0xFFU, 4*tablesize); | ||
| 84 | memset(info, 0, 4*infosize); | ||
| 85 | |||
| 86 | solved = cubetofast(solvedcube()); | ||
| 87 | for (i = 0, n = 0, cc = 0; i < 10; i++) { | ||
| 88 | memset(visited, 0, visitedsize); | ||
| 89 | DBG_LOG("cocsep: generating depth %" PRIu8 "\n", i); | ||
| 90 | cc = gendata_cocsep_dfs(solved, 0, i, &n, buf32, visited); | ||
| 91 | info[i+2] = cc; | ||
| 92 | DBG_LOG("found %" PRIu32 "\n", cc); | ||
| 93 | } | ||
| 94 | |||
| 95 | info[0] = (uint32_t)n; | ||
| 96 | info[1] = 9U; /* Known max pruning value */ | ||
| 97 | DBG_ASSERT(n == COCSEP_CLASSES, 0, | ||
| 98 | "cocsep: computed %" PRIu16 " symmetry classes, " | ||
| 99 | "expected %" PRIu16 "\n", n, COCSEP_CLASSES); | ||
| 100 | |||
| 101 | DBG_LOG("cocsep data computed\n"); | ||
| 102 | DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]); | ||
| 103 | DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[1]); | ||
| 104 | DBG_LOG("Pruning value distribution:\n"); | ||
| 105 | for (j = 0; j < 10; j++) | ||
| 106 | DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+2]); | ||
| 107 | |||
| 108 | return 4*(tablesize + infosize); | ||
| 109 | } | ||
| 110 | |||
| 111 | _static uint32_t | ||
| 112 | gendata_cocsep_dfs( | ||
| 113 | cube_fast_t c, | ||
| 114 | uint8_t depth, | ||
| 115 | uint8_t maxdepth, | ||
| 116 | uint16_t *n, | ||
| 117 | uint32_t *buf32, | ||
| 118 | uint8_t *visited | ||
| 119 | ) | ||
| 120 | { | ||
| 121 | uint8_t m, t, tinv, olddepth; | ||
| 122 | uint32_t cc; | ||
| 123 | int64_t i; | ||
| 124 | cube_fast_t d; | ||
| 125 | |||
| 126 | i = coord_fast_cocsep(c); | ||
| 127 | olddepth = (uint8_t)(buf32[i] & 0xFFU); | ||
| 128 | if (olddepth < depth || get_visited(visited, i)) | ||
| 129 | return 0; | ||
| 130 | set_visited(visited, i); | ||
| 131 | |||
| 132 | if (depth == maxdepth) { | ||
| 133 | if ((buf32[i] & 0xFFU) != 0xFFU) | ||
| 134 | return 0; | ||
| 135 | |||
| 136 | for (t = 0, cc = 0; t < 48; t++) { | ||
| 137 | d = transform(c, t); | ||
| 138 | i = coord_fast_cocsep(d); | ||
| 139 | set_visited(visited, i); | ||
| 140 | tinv = inverse_trans(t); | ||
| 141 | cc += (buf32[i] & 0xFFU) == 0xFFU; | ||
| 142 | buf32[i] = (*n << 16U) | (tinv << 8U) | depth; | ||
| 143 | } | ||
| 144 | (*n)++; | ||
| 145 | |||
| 146 | return cc; | ||
| 147 | } | ||
| 148 | |||
| 149 | for (m = 0, cc = 0; m < 18; m++) { | ||
| 150 | d = move(c, m); | ||
| 151 | cc += gendata_cocsep_dfs(d, depth+1, maxdepth, n, buf32, visited); | ||
| 152 | } | ||
| 153 | |||
| 154 | return cc; | ||
| 155 | } | ||
| 156 | |||
| 157 | /* | ||
| 158 | TODO description | ||
| 159 | generating fixed table with h=0, k=4 | ||
| 160 | */ | ||
| 161 | _static size_t | ||
| 162 | gendata_esep(const void *cocsepdata, void *buf) | ||
| 163 | { | ||
| 164 | size_t tablesize = (COCSEP_CLASSES * _12c4 * _8c4) / 2U; | ||
| 165 | size_t visitedsize = (tablesize * 2U + 7U) / 8U; | ||
| 166 | size_t infosize = 25; /* TODO unknown yet */ | ||
| 167 | |||
| 168 | uint32_t *buf32, *info, cc; | ||
| 169 | uint8_t moves[20]; | ||
| 170 | dfsarg_gendata_t arg; | ||
| 171 | |||
| 172 | arg.visited = malloc(visitedsize); | ||
| 173 | buf32 = (uint32_t *)buf; | ||
| 174 | info = buf32 + tablesize; | ||
| 175 | memset(buf32, 0xFFU, 4*tablesize); | ||
| 176 | memset(info, 0, 4*infosize); | ||
| 177 | |||
| 178 | arg.cube = cubetofast(solvedcube()); | ||
| 179 | arg.moves = moves; | ||
| 180 | arg.nmoves = 0; | ||
| 181 | arg.cocsepdata = (uint32_t *)cocsepdata; | ||
| 182 | arg.buf32 = buf32; | ||
| 183 | /* TODO loop until no more is done, not until 12! (or hardcode limits)*/ | ||
| 184 | for (arg.depth = 0, cc = 0; arg.depth < 12; arg.depth++) { | ||
| 185 | DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth); | ||
| 186 | memset(arg.visited, 0, visitedsize); | ||
| 187 | cc = gendata_esep_dfs(&arg); | ||
| 188 | info[arg.depth+1] = cc; | ||
| 189 | DBG_LOG("found %" PRIu32 "\n", cc); | ||
| 190 | } | ||
| 191 | free(arg.visited); | ||
| 192 | |||
| 193 | return cc; | ||
| 194 | } | ||
| 195 | |||
| 196 | _static uint32_t | ||
| 197 | gendata_esep_dfs(dfsarg_gendata_t *arg) | ||
| 198 | { | ||
| 199 | uint8_t m, t, olddepth; | ||
| 200 | uint32_t cc; | ||
| 201 | uint64_t i; | ||
| 202 | cube_fast_t d; | ||
| 203 | dfsarg_gendata_t nextarg; | ||
| 204 | |||
| 205 | if (!allowednextmove(arg->moves, arg->nmoves)) | ||
| 206 | return 0; | ||
| 207 | |||
| 208 | if (arg->nmoves > 0) | ||
| 209 | arg->cube = move(arg->cube, arg->moves[arg->nmoves-1]); | ||
| 210 | |||
| 211 | i = coord_h48(arg->cube, arg->cocsepdata, 0U); | ||
| 212 | olddepth = get_esep_pval(arg->buf32, i); | ||
| 213 | |||
| 214 | if (olddepth < arg->nmoves || get_visited(arg->visited, i)) | ||
| 215 | return 0; | ||
| 216 | set_visited(arg->visited, i); | ||
| 217 | |||
| 218 | if (arg->nmoves == arg->depth) { | ||
| 219 | if (olddepth != 15U) | ||
| 220 | return 0; | ||
| 221 | |||
| 222 | for (t = 0, cc = 0; t < 48; t++) { | ||
| 223 | d = transform(arg->cube, t); | ||
| 224 | i = coord_h48(d, arg->cocsepdata, 0U); | ||
| 225 | set_visited(arg->visited, i); | ||
| 226 | cc += get_esep_pval(arg->buf32, i) == 15U; | ||
| 227 | set_esep_pval(arg->buf32, i, arg->depth); | ||
| 228 | } | ||
| 229 | |||
| 230 | return cc; | ||
| 231 | } | ||
| 232 | |||
| 233 | |||
| 234 | nextarg = *arg; | ||
| 235 | nextarg.nmoves = arg->nmoves + 1; | ||
| 236 | for (m = 0, cc = 0; m < 18; m++) { | ||
| 237 | nextarg.cube = arg->cube; | ||
| 238 | nextarg.moves[arg->nmoves] = m; | ||
| 239 | cc += gendata_esep_dfs(&nextarg); | ||
| 240 | } | ||
| 241 | |||
| 242 | return cc; | ||
| 243 | } | ||
| 244 | |||
| 245 | _static_inline bool get_visited(const uint8_t *a, int64_t i) | ||
| 246 | { | ||
| 247 | return a[_visited_ind(i)] & _visited_mask(i); | ||
| 248 | } | ||
| 249 | |||
| 250 | _static_inline void set_visited(uint8_t *a, int64_t i) | ||
| 251 | { | ||
| 252 | a[_visited_ind(i)] |= _visited_mask(i); | ||
| 253 | } | ||
| 254 | |||
| 255 | _static_inline uint8_t | ||
| 256 | get_esep_pval(const uint32_t *buf32, int64_t i) | ||
| 257 | { | ||
| 258 | return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i); | ||
| 259 | } | ||
| 260 | |||
| 261 | _static_inline void | ||
| 262 | set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) | ||
| 263 | { | ||
| 264 | buf32[_esep_ind(i)] = | ||
| 265 | (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i)); | ||
| 266 | } | ||
