solver_nxopt31.c (6029B)
1 #include "solver_nxopt31.h" 2 3 /* TODO: make generic for nxopt solvers */ 4 5 static void apply_move_fst(void *, void *, Move); 6 static void * prepare_cube_fst(void *, Cube *); 7 static bool move_check_stop_nxopt31(void *, DfsArg *, Threader *); 8 static bool is_solved_fst(void *, void *); 9 static void * alloc_cubedata_fst(void *); 10 static void copy_cubedata_fst(void *, void *, void *); 11 static void free_cubedata_fst(void *, void *); 12 static void invert_cubedata_fst(void *, void *); 13 static uint64_t index_nxopt31(uint16_t, uint16_t, uint16_t, uint16_t, Trans); 14 static int update(PruneData*, uint16_t *, uint16_t *, 15 uint16_t *, uint16_t, Move, Trans); 16 17 static uint16_t cpudsep_table[FACTORIAL8]; 18 19 Solver solver_nxopt31 = { 20 .moveset = &moveset_HTM, 21 .move_check_stop = move_check_stop_nxopt31, 22 .validate_solution = NULL, 23 .niss_makes_sense = NULL, 24 .param = NULL, 25 .alloc_cubedata = alloc_cubedata_fst, 26 .copy_cubedata = copy_cubedata_fst, 27 .free_cubedata = free_cubedata_fst, 28 .invert_cube = invert_cubedata_fst, 29 .is_solved = is_solved_fst, 30 .apply_move = apply_move_fst, 31 .prepare_cube = prepare_cube_fst, 32 }; 33 34 /* TODO: this is a bit weird because of realloc, 35 but we want to refactor this in any case */ 36 static void 37 apply_move_fst(void *param, void *cubedata, Move m) 38 { 39 FstCube *fst = (FstCube *)cubedata; 40 41 FstCube *moved = malloc(sizeof(FstCube)); 42 *moved = fst_move(m, *fst); 43 44 free(fst); 45 cubedata = moved; 46 } 47 48 static void 49 init_cpudsep_table() 50 { 51 static bool generated = false; 52 uint64_t i; 53 Cube c; 54 55 if (generated) 56 return; 57 58 gen_coord(&coord_coud_cpudsep); 59 for (i = 0; i < FACTORIAL8; i++) { 60 index_to_perm(i, 8, c.cp); 61 cpudsep_table[i] = index_coord(&coord_cpudsep, &c, NULL); 62 } 63 64 generated = true; 65 } 66 67 /* TODO: ugly */ 68 void 69 prepare_solver_nxopt31() 70 { 71 init_fst(); 72 gen_coord(&coord_eposepe); 73 gen_coord(&coord_eofbepos_sym16); 74 gen_coord(&coord_coud); 75 gen_coord(&coord_cp); 76 77 /* TODO: prepare also table cp pruning and 78 internal table for cpudsep from cp */ 79 /* TODO: also check if ptables are already generated? */ 80 81 init_cpudsep_table(); 82 83 PruneData *pd = malloc(sizeof(PruneData)); 84 pd->moveset = &moveset_HTM; 85 init_moveset(&moveset_HTM); 86 pd->coord = &coord_nxopt31; 87 gen_coord(&coord_nxopt31); 88 pd->compact = true; 89 solver_nxopt31.param = genptable(pd, 4); /* TODO: threads */ 90 } 91 92 static void * 93 prepare_cube_fst(void *param, Cube *cube) 94 { 95 FstCube *fst = malloc(sizeof(FstCube)); 96 97 *fst = cube_to_fst(cube); 98 99 return fst; 100 } 101 102 static bool 103 is_solved_fst(void *param, void *cubedata) 104 { 105 return fst_is_solved(*(FstCube *)cubedata); 106 } 107 108 static void * 109 alloc_cubedata_fst(void *param) 110 { 111 return malloc(sizeof(FstCube)); 112 } 113 114 static void 115 copy_cubedata_fst(void *param, void *src, void *dst) 116 { 117 memcpy(dst, src, sizeof(FstCube)); 118 } 119 120 static void 121 free_cubedata_fst(void *param, void *cubedata) 122 { 123 free(cubedata); 124 } 125 126 /* TODO: again, weird reallocation */ 127 static void 128 invert_cubedata_fst(void *param, void *cubedata) 129 { 130 FstCube *inv = malloc(sizeof(FstCube)); 131 132 *inv = fst_inverse(*(FstCube *)cubedata); 133 free(cubedata); 134 135 cubedata = inv; 136 } 137 138 static uint64_t 139 index_nxopt31(uint16_t eofb, uint16_t eposepe, uint16_t coud, uint16_t cp, Trans t) 140 { 141 uint64_t eofbepos = (eposepe / FACTORIAL4) * POW2TO11 + eofb; 142 uint64_t eofbepos_sym16 = coord_eofbepos_sym16.symclass[eofbepos]; 143 Trans ttr = coord_eofbepos_sym16.transtorep[eofbepos]; 144 if (t != uf) 145 cp = trans_coord(&coord_cp, t, cp); 146 uint64_t sep = cpudsep_table[cp]; 147 uint64_t coud_cpudsep = coud * BINOM8ON4 + sep; 148 uint64_t cc = trans_coord(&coord_coud_cpudsep, ttr, coud_cpudsep); 149 uint64_t ind = eofbepos_sym16 * POW3TO7 * BINOM8ON4 + cc; 150 151 return ind; 152 } 153 154 static int 155 update(PruneData *pd, uint16_t *eofb, uint16_t *eposepe, 156 uint16_t *coud, uint16_t cp, Move m, Trans t) 157 { 158 uint64_t ind; 159 160 /* TODO fix 161 *eofb = coord_eofb.mtable[m][*eofb]; 162 *eposepe = coord_eposepe.mtable[m][*eposepe]; 163 *coud = coord_coud.mtable[m][*coud]; 164 */ 165 166 ind = index_nxopt31(*eofb, *eposepe, *coud, cp, t); 167 168 return ptableval(pd, ind); 169 } 170 171 static bool 172 move_check_stop_nxopt31(void *param, DfsArg *arg, Threader *threader) 173 { 174 /* TODO: implement nxopt trick, i.e. inverse probing + switching */ 175 /* this means making the cube data structure more complex, 176 because we need to memorize the values from last probing 177 not hard, but it means we can't delegate everything to 178 a cube structure (unless we change FstCube to also include 179 tmhe probing values, but it does not make much sense) */ 180 181 uint64_t ind; 182 PruneData *pd = (PruneData *)param; 183 FstCube *fst = (FstCube *)arg->cubedata; 184 185 int l = arg->current_alg->len; 186 int target = arg->d - l; 187 188 Move m = l > 0 ? arg->current_alg->move[l-1] : NULLMOVE; 189 /*fst->uf_cp = coord_cp.mtable[m][fst->uf_cp];*/ 190 fst_move(m, *fst); 191 192 int nuf = update(pd, &fst->uf_eofb, &fst->uf_eposepe, &fst->uf_coud, 193 fst->uf_cp, m, uf); 194 if (nuf > target) 195 return true; 196 int nfr = update(pd, &fst->fr_eofb, &fst->fr_eposepe, &fst->fr_coud, 197 fst->uf_cp, m, fr); 198 if (nfr > target) 199 return true; 200 int nrd = update(pd, &fst->rd_eofb, &fst->rd_eposepe, &fst->rd_coud, 201 fst->uf_cp, m, rd); 202 if (nrd > target) 203 return true; 204 205 if (nuf == nfr && nuf == nrd && nuf == target) 206 return true; 207 208 FstCube inv = fst_inverse(*fst); 209 210 ind = index_nxopt31(inv.uf_eofb, inv.uf_eposepe, inv.uf_coud, inv.uf_cp, uf); 211 int iuf = ptableval(pd, ind); 212 if (iuf > target) 213 return true; 214 ind = index_nxopt31(inv.fr_eofb, inv.fr_eposepe, inv.fr_coud, inv.uf_cp, fr); 215 int ifr = ptableval(pd, ind); 216 if (ifr > target) 217 return true; 218 ind = index_nxopt31(inv.rd_eofb, inv.rd_eposepe, inv.rd_coud, inv.uf_cp, rd); 219 int ird = ptableval(pd, ind); 220 if (ird > target) 221 return true; 222 223 if (iuf == ifr && iuf == ird && iuf == target) 224 return true; 225 226 fst->uf_cp = coord_cp.mtable[m][fst->uf_cp]; 227 228 /* TODO: check also pd_corners */ 229 return false; 230 }