aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/gendata_full.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48/gendata_full.h')
-rw-r--r--src/solvers/h48/gendata_full.h329
1 files changed, 329 insertions, 0 deletions
diff --git a/src/solvers/h48/gendata_full.h b/src/solvers/h48/gendata_full.h
new file mode 100644
index 0000000..be234d9
--- /dev/null
+++ b/src/solvers/h48/gendata_full.h
@@ -0,0 +1,329 @@
1#define ESEP_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4)
2#define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h))
3#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k)))
4
5#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8))
6#define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8)))
7#define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i))
8
9#define MAXLEN 20
10
11/*
12TODO: This loop over similar h48 coordinates can be improved by only
13transforming edges, but we need to compose transformations (i.e. conjugate
14_t by _ttrep).
15*/
16#define _foreach_h48sim(_cube, _cocsepdata, _selfsim, _h, _action) \
17 int64_t _cocsep = coord_cocsep(_cube); \
18 uint8_t _ttrep = TTREP(_cocsepdata[_cocsep]); \
19 uint8_t _inverse_ttrep = inverse_trans(_ttrep); \
20 int64_t _coclass = COCLASS(_cocsepdata[_cocsep]); \
21 cube_t _rep = transform(_cube, _ttrep); \
22 uint64_t _sim = _selfsim[_coclass]; \
23 for (uint8_t _t = 0; _t < 48 && _sim; _t++, _sim >>= 1) { \
24 if (!(_sim & 1)) continue; \
25 _cube = transform(_rep, _t); \
26 _cube = transform(_cube, _inverse_ttrep); \
27 _action \
28 }
29
30typedef struct {
31 uint8_t h;
32 uint8_t k;
33 uint8_t maxdepth;
34 void * buf;
35} gendata_h48_arg_t;
36
37typedef struct {
38 uint8_t maxdepth;
39 const uint32_t *cocsepdata;
40 const cube_t *crep;
41 const uint64_t *selfsim;
42 h48map_t *map;
43} gendata_h48short_arg_t;
44
45typedef struct {
46 uint8_t depth;
47 uint32_t *cocsepdata;
48 uint32_t *buf32;
49 uint64_t *selfsim;
50 int64_t done;
51 cube_t *crep;
52} bfsarg_esep_t;
53
54_static_inline uint8_t get_esep_pval(const uint32_t *, int64_t);
55_static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
56
57_static uint64_t gen_h48short(gendata_h48short_arg_t *);
58_static size_t gendata_h48(gendata_h48_arg_t *);
59_static size_t gendata_h48h0k4(void *, uint8_t);
60_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
61_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
62_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
63_static size_t gendata_h48k2(void *, uint8_t, uint8_t);
64
65_static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
66
67_static uint64_t
68gen_h48short(gendata_h48short_arg_t *arg)
69{
70 uint8_t i, m;
71 int64_t coord;
72 uint64_t j, oldn;
73 kvpair_t kv;
74 cube_t cube, d;
75
76 cube = solvedcube();
77 coord = coord_h48(cube, arg->cocsepdata, 11);
78 h48map_insertmin(arg->map, coord, 0);
79 oldn = 0;
80 LOG("Short h48: depth 0\nfound %" PRIu8 "\n", arg->map->n-oldn);
81 for (i = 0; i < arg->maxdepth; i++) {
82 LOG("Short h48: depth %" PRIu8 "\n", i+1);
83 j = 0;
84 oldn = arg->map->n;
85 for (kv = h48map_nextkvpair(arg->map, &j);
86 j != arg->map->capacity;
87 kv = h48map_nextkvpair(arg->map, &j)
88 ) {
89 if (kv.val != i)
90 continue;
91 cube = invcoord_h48(kv.key, arg->crep, 11);
92 for (m = 0; m < 18; m++) {
93 d = move(cube, m);
94 _foreach_h48sim(
95 d, arg->cocsepdata, arg->selfsim, 11,
96 coord = coord_h48(d, arg->cocsepdata, 11);
97 h48map_insertmin(arg->map, coord, i+1);
98 )
99 }
100 }
101 LOG("found %" PRIu8 "\n", arg->map->n-oldn);
102 }
103
104 return arg->map->n;
105}
106
107/* Generic function that dispatches to the data generators */
108_static size_t
109gendata_h48(gendata_h48_arg_t *arg)
110{
111 if (arg->h == 0 && arg->k == 4) {
112 return gendata_h48h0k4(arg->buf, arg->maxdepth);
113 } else if (arg->k == 2) {
114 return gendata_h48k2(arg->buf, arg->h, arg->maxdepth);
115 }
116
117 LOG("Cannot generate data for h = %" PRIu8 " and k = %" PRIu8
118 " (not implemented yet)\n", arg->h, arg->k);
119}
120
121/*
122TODO description
123generating fixed table with h=0, k=4
124*/
125_static size_t
126gendata_h48h0k4(void *buf, uint8_t maxdepth)
127{
128 uint32_t j, *buf32, *info, *cocsepdata;
129 bfsarg_esep_t arg;
130 int64_t sc, cc, esep_max;
131 uint64_t selfsim[COCSEP_CLASSES];
132 cube_t crep[COCSEP_CLASSES];
133 size_t cocsepsize, infosize;
134
135 if (buf == NULL)
136 goto gendata_h48h0k4_return_size;
137
138 /* TODO: move info at start of tables (all tables!) */
139 cocsepsize = gendata_cocsep(buf, selfsim, crep);
140 infosize = 88;
141
142 esep_max = (int64_t)ESEP_MAX(0);
143 cocsepdata = (uint32_t *)buf;
144 buf32 = cocsepdata + cocsepsize / 4;
145 info = buf32 + (ESEP_TABLESIZE(0, 4) / sizeof(uint32_t));
146 memset(buf32, 0xFF, ESEP_TABLESIZE(0, 4));
147
148 sc = coord_h48(solved, cocsepdata, 0);
149 set_esep_pval(buf32, sc, 0);
150 info[1] = 1;
151 arg = (bfsarg_esep_t) {
152 .cocsepdata = cocsepdata,
153 .buf32 = buf32,
154 .selfsim = selfsim,
155 .crep = crep
156 };
157 for (
158 arg.done = 1, arg.depth = 1, cc = 0;
159 arg.done < esep_max && arg.depth <= maxdepth;
160 arg.depth++
161 ) {
162 LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
163 cc = gendata_h48h0k4_bfs(&arg);
164 arg.done += cc;
165 info[arg.depth+1] = cc;
166 LOG("found %" PRId64 "\n", cc);
167 }
168
169 info[0] = arg.depth-1;
170
171 LOG("h48 pruning table computed\n");
172 LOG("Maximum pruning value: %" PRIu32 "\n", info[0]);
173 LOG("Pruning value distribution:\n");
174 for (j = 0; j <= info[0]; j++)
175 LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]);
176
177gendata_h48h0k4_return_size:
178 return cocsepsize + ESEP_TABLESIZE(0, 4) + infosize;
179}
180
181_static int64_t
182gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
183{
184 const uint8_t breakpoint = 10; /* Hand-picked optimal */
185
186 if (arg->depth < breakpoint)
187 return gendata_h48h0k4_bfs_fromdone(arg);
188 else
189 return gendata_h48h0k4_bfs_fromnew(arg);
190}
191
192_static int64_t
193gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
194{
195 uint8_t c, m, x;
196 uint32_t cc;
197 int64_t i, j, k;
198 cube_t cube, moved;
199
200 for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) {
201 c = get_esep_pval(arg->buf32, i);
202 if (c != arg->depth - 1)
203 continue;
204 cube = invcoord_h48(i, arg->crep, 0);
205 for (m = 0; m < 18; m++) {
206 moved = move(cube, m);
207 j = coord_h48(moved, arg->cocsepdata, 0);
208 if (get_esep_pval(arg->buf32, j) <= arg->depth)
209 continue;
210 _foreach_h48sim(moved, arg->cocsepdata, arg->selfsim, 0,
211 k = coord_h48(moved, arg->cocsepdata, 0);
212 x = get_esep_pval(arg->buf32, k);
213 set_esep_pval(arg->buf32, k, arg->depth);
214 cc += x != arg->depth;
215 )
216 }
217 }
218
219 return cc;
220}
221
222_static int64_t
223gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg)
224{
225 uint8_t c, m, x;
226 uint32_t cc;
227 int64_t i, j;
228 cube_t cube, moved;
229
230 for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) {
231 c = get_esep_pval(arg->buf32, i);
232 if (c != 0xF)
233 continue;
234 cube = invcoord_h48(i, arg->crep, 0);
235 for (m = 0; m < 18; m++) {
236 moved = move(cube, m);
237 j = coord_h48(moved, arg->cocsepdata, 0);
238 x = get_esep_pval(arg->buf32, j);
239 if (x >= arg->depth)
240 continue;
241 _foreach_h48sim(cube, arg->cocsepdata, arg->selfsim, 0,
242 j = coord_h48(cube, arg->cocsepdata, 0);
243 x = get_esep_pval(arg->buf32, j);
244 set_esep_pval(arg->buf32, j, arg->depth);
245 cc += x == 0xF;
246 )
247 break; /* Enough to find one, skip the rest */
248 }
249 }
250
251 return cc;
252}
253
254_static size_t
255gendata_h48k2(void *buf, uint8_t h, uint8_t maxdepth)
256{
257 static uint64_t capacity = 10000019; /* First prime after 1e8 */
258 static uint64_t randomizer = 10000079; /* Second prime after 1e8 */
259 static uint8_t base[] = {
260 [0] = 8,
261 [1] = 8,
262 [2] = 8,
263 [3] = 8,
264 [4] = 9,
265 [5] = 9,
266 [6] = 9,
267 [7] = 9,
268 [8] = 10,
269 [9] = 10,
270 [10] = 10,
271 [11] = 10
272 };
273
274 uint64_t nshort;
275 uint32_t *buf32, *info, *cocsepdata;
276 h48map_t depth8cubes;
277 gendata_h48short_arg_t shortarg;
278 uint64_t selfsim[COCSEP_CLASSES];
279 cube_t crep[COCSEP_CLASSES];
280 size_t cocsepsize, infosize;
281
282 DBG_ASSERT(base[h] == 8, 0, "Only implemented for h <= 3 (base 8)\n");
283
284 if (buf == NULL)
285 goto gendata_h48k2_return_size;
286
287 cocsepdata = (uint32_t *)buf;
288 cocsepsize = gendata_cocsep(buf, selfsim, crep);
289 infosize = 88;
290
291 h48map_create(&depth8cubes, capacity, randomizer);
292 shortarg = (gendata_h48short_arg_t) {
293 .maxdepth = 8,
294 .cocsepdata = cocsepdata,
295 .crep = crep,
296 .selfsim = selfsim,
297 .map = &depth8cubes
298 };
299
300 nshort = gen_h48short(&shortarg);
301 LOG("%" PRIu64 "\n", nshort);
302
303 h48map_destroy(&depth8cubes);
304
305gendata_h48k2_return_size:
306 return cocsepsize + ESEP_TABLESIZE(h, 2) + infosize;
307}
308
309_static_inline uint8_t
310get_esep_pval(const uint32_t *buf32, int64_t i)
311{
312 return (buf32[ESEP_IND(i)] & ESEP_MASK(i)) >> ESEP_SHIFT(i);
313}
314
315_static_inline void
316set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
317{
318 buf32[ESEP_IND(i)] =
319 (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i));
320}
321
322_static_inline int8_t
323get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint32_t *h48data)
324{
325 int64_t coord;
326
327 coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
328 return get_esep_pval(h48data, coord);
329}

Generated with cgit - Back to sebastiano.tronto.net