aboutsummaryrefslogtreecommitdiff
path: root/src/solve_h48.h
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-05-27 12:04:53 +0200
committerSebastiano Tronto <sebastiano@tronto.net>2024-05-27 12:04:53 +0200
commit49b9c4a516f72e03d53277075f4580e2df8f0e63 (patch)
treedea68649391d14d63a96e742b450c59681ac4305 /src/solve_h48.h
parentfde8dfa9df8df1e3d42a9a8840836e33817cd498 (diff)
downloadnissy-core-49b9c4a516f72e03d53277075f4580e2df8f0e63.tar.gz
nissy-core-49b9c4a516f72e03d53277075f4580e2df8f0e63.zip
Some type fixes and some cleanup
Diffstat (limited to 'src/solve_h48.h')
-rw-r--r--src/solve_h48.h114
1 files changed, 65 insertions, 49 deletions
diff --git a/src/solve_h48.h b/src/solve_h48.h
index ecb0863..abf7a86 100644
--- a/src/solve_h48.h
+++ b/src/solve_h48.h
@@ -1,18 +1,23 @@
1#define COCSEP_CLASSES 3393U 1#define COCSEP_CLASSES ((size_t)3393)
2#define COCSEP_TABLESIZE (_3p7 << 7ULL) 2#define COCSEP_TABLESIZE ((size_t)_3p7 << (size_t)7)
3#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + 7ULL) / 8ULL) 3#define COCSEP_VISITEDSIZE ((COCSEP_TABLESIZE + (size_t)7) / (size_t)8)
4#define COCSEP_FULLSIZE (4*(COCSEP_TABLESIZE + 12)) 4#define COCSEP_FULLSIZE ((size_t)4 * (COCSEP_TABLESIZE + (size_t)12))
5 5
6#define ESEP_MAX(h) ((COCSEP_CLASSES * _12c4 * _8c4) << (h)) 6#define ESEP_NOEO (COCSEP_CLASSES * (size_t)_12c4 * (size_t)_8c4)
7#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / (8U / (k))) 7#define ESEP_MAX(h) (ESEP_NOEO << (size_t)(h))
8#define ESEP_TABLESIZE(h, k) (ESEP_MAX((h)) / ((size_t)8 / (size_t)(k)))
8 9
9#define H48_ESIZE(h) ((_12c4 * _8c4) << (h)) 10#define COCLASS_MASK (UINT32_C(0xFFFF) << UINT32_C(16))
11#define COCLASS(x) (((x) & COCLASS_MASK) >> UINT32_C(16))
12#define TTREP_MASK (UINT32_C(0xFF) << UINT32_C(8))
13#define TTREP(x) (((x) & TTREP_MASK) >> UINT32_C(8))
14#define H48_ESIZE(h) ((_12c4 * _8c4) << (int64_t)(h))
10 15
11#define _esep_ind(i) (i / 8ULL) 16#define ESEP_IND(i) ((uint32_t)(i) / UINT32_C(8))
12#define _esep_shift(i) (4ULL * (i % 8ULL)) 17#define ESEP_SHIFT(i) (UINT32_C(4) * ((uint32_t)(i) % UINT32_C(8)))
13#define _esep_mask(i) (((1ULL << 4ULL) - 1ULL) << _esep_shift(i)) 18#define ESEP_MASK(i) ((_bit_u32(4) - (uint32_t)(1)) << ESEP_SHIFT(i))
14#define _visited_ind(i) (i / 8ULL) 19#define VISITED_IND(i) ((uint32_t)(i) / UINT32_C(8))
15#define _visited_mask(i) (1ULL << (i % 8ULL)) 20#define VISITED_MASK(i) (UINT32_C(1) << ((uint32_t)(i) % UINT32_C(8)))
16 21
17typedef struct { 22typedef struct {
18 cube_fast_t cube; 23 cube_fast_t cube;
@@ -59,8 +64,8 @@ coord_h48(cube_fast_t c, const uint32_t *cocsepdata, uint8_t h)
59 64
60 cocsep = coord_fast_cocsep(c); 65 cocsep = coord_fast_cocsep(c);
61 data = cocsepdata[cocsep]; 66 data = cocsepdata[cocsep];
62 coclass = (data & (0xFFFFU << 16U)) >> 16U; 67 coclass = (int64_t)COCLASS(data);
63 ttrep = (data & (0xFFU << 8U)) >> 8U; 68 ttrep = (int64_t)TTREP(data);
64 69
65 return coord_h48_edges(c, coclass, ttrep, h); 70 return coord_h48_edges(c, coclass, ttrep, h);
66} 71}
@@ -69,13 +74,14 @@ _static_inline int64_t
69coord_h48_edges(cube_fast_t c, int64_t coclass, uint8_t t, uint8_t h) 74coord_h48_edges(cube_fast_t c, int64_t coclass, uint8_t t, uint8_t h)
70{ 75{
71 cube_fast_t d; 76 cube_fast_t d;
72 int64_t esep, eo; 77 int64_t esep, eo, edges;
73 78
74 d = transform_edges(c, t); 79 d = transform_edges(c, t);
75 esep = coord_fast_esep(d); 80 esep = coord_fast_esep(d);
76 eo = coord_fast_eo(d); 81 eo = coord_fast_eo(d);
82 edges = (esep << (int64_t)h) + (eo >> (11 - (int64_t)h));
77 83
78 return (coclass * H48_ESIZE(h)) + (esep << h) + (eo >> (11-h)); 84 return coclass * H48_ESIZE(h) + edges;
79} 85}
80 86
81/* 87/*
@@ -85,15 +91,17 @@ returned cube is a transformed cube of one that gives the correct value.
85*/ 91*/
86_static_inline cube_fast_t 92_static_inline cube_fast_t
87invcoord_h48(int64_t i, const cube_fast_t *crep, uint8_t h) { 93invcoord_h48(int64_t i, const cube_fast_t *crep, uint8_t h) {
88 cube_fast_t ret; int64_t coclass, ee, esep, eo; 94 cube_fast_t ret;
95 int64_t hh, coclass, ee, esep, eo;
89 96
90 DBG_ASSERT(h <= 11, cubetofast(zero), 97 DBG_ASSERT(h <= 11, cubetofast(zero),
91 "invcoord_h48: h must be between 0 and 11\n"); 98 "invcoord_h48: h must be between 0 and 11\n");
92 99
100 hh = (int64_t)h;
93 coclass = i / H48_ESIZE(h); 101 coclass = i / H48_ESIZE(h);
94 ee = i % H48_ESIZE(h); 102 ee = i % H48_ESIZE(h);
95 esep = ee >> h; 103 esep = ee >> hh;
96 eo = (ee & ((1<<h)-1)) << (11-h); 104 eo = (ee & ((1 << hh) - 1)) << (11 - hh);
97 105
98 ret = invcoord_fast_esep(esep); 106 ret = invcoord_fast_esep(esep);
99 copy_corners_fast(&ret, crep[coclass]); 107 copy_corners_fast(&ret, crep[coclass]);
@@ -123,7 +131,7 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep)
123 131
124 buf32 = (uint32_t *)buf; 132 buf32 = (uint32_t *)buf;
125 info = buf32 + COCSEP_TABLESIZE; 133 info = buf32 + COCSEP_TABLESIZE;
126 memset(buf32, 0xFFU, sizeof(uint32_t) * COCSEP_TABLESIZE); 134 memset(buf32, 0xFF, sizeof(uint32_t) * COCSEP_TABLESIZE);
127 memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES); 135 memset(selfsim, 0, sizeof(uint64_t) * COCSEP_CLASSES);
128 136
129 arg = (dfsarg_cocsep_t) { 137 arg = (dfsarg_cocsep_t) {
@@ -145,10 +153,10 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep)
145 } 153 }
146 154
147 info[0] = (uint32_t)n; 155 info[0] = (uint32_t)n;
148 info[1] = 9U; /* Known max pruning value */ 156 info[1] = 9; /* Known max pruning value */
149 DBG_ASSERT(n == COCSEP_CLASSES, 0, 157 DBG_ASSERT(n == COCSEP_CLASSES, 0,
150 "cocsep: computed %" PRIu16 " symmetry classes, " 158 "cocsep: computed %" PRIu16 " symmetry classes, "
151 "expected %" PRIu16 "\n", n, COCSEP_CLASSES); 159 "expected %zu\n", n, COCSEP_CLASSES);
152 160
153 DBG_LOG("cocsep data computed\n"); 161 DBG_LOG("cocsep data computed\n");
154 DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]); 162 DBG_LOG("Symmetry classes: %" PRIu32 "\n", info[0]);
@@ -163,33 +171,37 @@ gendata_cocsep(void *buf, uint64_t *selfsim, cube_fast_t *rep)
163_static uint32_t 171_static uint32_t
164gendata_cocsep_dfs(dfsarg_cocsep_t *arg) 172gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
165{ 173{
166 uint8_t m, tinv, olddepth; 174 uint8_t m, tinv;
167 uint32_t cc; 175 uint32_t cc, class, ttrep, depth, olddepth;
168 uint64_t t, is; 176 uint64_t t, is;
169 int64_t i, ii; 177 int64_t i, j;
170 cube_fast_t d; 178 cube_fast_t d;
171 dfsarg_cocsep_t nextarg; 179 dfsarg_cocsep_t nextarg;
172 180
173 i = coord_fast_cocsep(arg->cube); 181 i = coord_fast_cocsep(arg->cube);
174 olddepth = (uint8_t)(arg->buf32[i] & 0xFFU); 182 olddepth = (uint8_t)(arg->buf32[i] & 0xFF);
175 if (olddepth < arg->depth || get_visited(arg->visited, i)) 183 if (olddepth < arg->depth || get_visited(arg->visited, i))
176 return 0; 184 return 0;
177 set_visited(arg->visited, i); 185 set_visited(arg->visited, i);
178 186
179 if (arg->depth == arg->maxdepth) { 187 if (arg->depth == arg->maxdepth) {
180 if ((arg->buf32[i] & 0xFFU) != 0xFFU) 188 if ((arg->buf32[i] & 0xFF) != 0xFF)
181 return 0; 189 return 0;
182 190
183 for (t = 0, cc = 0; t < 48; t++) { 191 for (t = 0, cc = 0; t < 48; t++) {
184 d = transform_corners(arg->cube, t); 192 d = transform_corners(arg->cube, t);
185 ii = coord_fast_cocsep(d); 193 j = coord_fast_cocsep(d);
186 is = (i == ii); 194 is = (i == j);
187 arg->selfsim[*arg->n] |= is << t; 195 arg->selfsim[*arg->n] |= is << t;
188 set_visited(arg->visited, ii); 196 set_visited(arg->visited, j);
189 tinv = inverse_trans(t); 197 tinv = inverse_trans(t);
190 cc += (arg->buf32[ii] & 0xFFU) == 0xFFU; 198 olddepth = (uint8_t)(arg->buf32[j] & 0xFF);
191 arg->buf32[ii] = 199 cc += olddepth == 0xFF;
192 (*arg->n << 16U) | (tinv << 8U) | arg->depth; 200
201 class = (uint32_t)(*arg->n) << 16;
202 ttrep = (uint32_t)tinv << 8;
203 depth = (uint32_t)arg->depth;
204 arg->buf32[j] = class | ttrep | depth;
193 } 205 }
194 arg->rep[*arg->n] = arg->cube; 206 arg->rep[*arg->n] = arg->cube;
195 (*arg->n)++; 207 (*arg->n)++;
@@ -217,16 +229,17 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
217 const int k = 4; /* TODO: other cases? */ 229 const int k = 4; /* TODO: other cases? */
218 uint32_t j, *buf32, *info, *cocsepdata; 230 uint32_t j, *buf32, *info, *cocsepdata;
219 bfsarg_esep_t arg; 231 bfsarg_esep_t arg;
220 int64_t sc, cc, tot; 232 int64_t sc, cc, tot, esep_max;
221 uint64_t selfsim[COCSEP_CLASSES]; 233 uint64_t selfsim[COCSEP_CLASSES];
222 cube_fast_t crep[COCSEP_CLASSES]; 234 cube_fast_t crep[COCSEP_CLASSES];
223 size_t cocsepsize; 235 size_t cocsepsize, infosize;
224 236
237 esep_max = (int64_t)ESEP_MAX(h);
225 cocsepsize = gendata_cocsep(buf, selfsim, crep); 238 cocsepsize = gendata_cocsep(buf, selfsim, crep);
226 cocsepdata = (uint32_t *)buf; 239 cocsepdata = (uint32_t *)buf;
227 buf32 = cocsepdata + cocsepsize/4; 240 buf32 = cocsepdata + cocsepsize / 4;
228 info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t)); 241 info = buf32 + (ESEP_TABLESIZE(h, k) / sizeof(uint32_t));
229 memset(buf32, 0xFFU, ESEP_TABLESIZE(h, k)); 242 memset(buf32, 0xFF, ESEP_TABLESIZE(h, k));
230 243
231 sc = coord_h48(cubetofast(solved), cocsepdata, h); 244 sc = coord_h48(cubetofast(solved), cocsepdata, h);
232 set_esep_pval(buf32, sc, 0); 245 set_esep_pval(buf32, sc, 0);
@@ -240,7 +253,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
240 }; 253 };
241 for ( 254 for (
242 tot = 1, arg.depth = 1, cc = 0; 255 tot = 1, arg.depth = 1, cc = 0;
243 tot < ESEP_MAX(h) && arg.depth <= maxdepth; 256 tot < esep_max && arg.depth <= maxdepth;
244 arg.depth++ 257 arg.depth++
245 ) { 258 ) {
246 DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth); 259 DBG_LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
@@ -251,6 +264,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
251 } 264 }
252 265
253 info[0] = arg.depth-1; 266 info[0] = arg.depth-1;
267 infosize = 4 * (size_t)(info[0] + 2);
254 268
255 DBG_LOG("h48 pruning table computed\n"); 269 DBG_LOG("h48 pruning table computed\n");
256 DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[0]); 270 DBG_LOG("Maximum pruning value: %" PRIu32 "\n", info[0]);
@@ -258,7 +272,7 @@ gendata_h48(void *buf, uint8_t h, uint8_t maxdepth)
258 for (j = 0; j <= info[0]; j++) 272 for (j = 0; j <= info[0]; j++)
259 DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]); 273 DBG_LOG("%" PRIu8 ":\t%" PRIu32 "\n", j, info[j+1]);
260 274
261 return COCSEP_FULLSIZE + ESEP_TABLESIZE(h, k) + 4*(info[0]+2); 275 return cocsepsize + ESEP_TABLESIZE(h, k) + infosize;
262} 276}
263 277
264_static uint64_t 278_static uint64_t
@@ -266,10 +280,12 @@ gendata_esep_bfs(bfsarg_esep_t *arg)
266{ 280{
267 uint8_t c, m, x; 281 uint8_t c, m, x;
268 uint32_t cc; 282 uint32_t cc;
269 uint64_t i, j, k, t, cocsep_coord, sim; 283 int64_t i, j, k, t, cocsep_coord, sim, esep_max;
270 cube_fast_t cube, moved, transd; 284 cube_fast_t cube, moved, transd;
271 285
272 for (i = 0, cc = 0; i < ESEP_MAX(arg->h); i++) { 286 esep_max = (uint64_t)ESEP_MAX(arg->h);
287
288 for (i = 0, cc = 0; i < esep_max; i++) {
273 c = get_esep_pval(arg->buf32, i); 289 c = get_esep_pval(arg->buf32, i);
274 if (c != arg->depth - 1) 290 if (c != arg->depth - 1)
275 continue; 291 continue;
@@ -288,9 +304,9 @@ gendata_esep_bfs(bfsarg_esep_t *arg)
288 set_esep_pval(arg->buf32, j, arg->depth); 304 set_esep_pval(arg->buf32, j, arg->depth);
289 cc += x != arg->depth; 305 cc += x != arg->depth;
290 cocsep_coord = j / H48_ESIZE(arg->h); 306 cocsep_coord = j / H48_ESIZE(arg->h);
291 sim = arg->selfsim[cocsep_coord] >> 1ULL; 307 sim = arg->selfsim[cocsep_coord] >> 1;
292 for (t = 1; t < 48 && sim; t++, sim >>= 1ULL) { 308 for (t = 1; t < 48 && sim; t++, sim >>= 1) {
293 if (!(sim & 1ULL)) 309 if (!(sim & 1))
294 continue; 310 continue;
295 transd = transform(moved, t); 311 transd = transform(moved, t);
296 k = coord_h48(transd, arg->cocsepdata, arg->h); 312 k = coord_h48(transd, arg->cocsepdata, arg->h);
@@ -308,23 +324,23 @@ gendata_esep_bfs(bfsarg_esep_t *arg)
308 324
309_static_inline bool get_visited(const uint8_t *a, int64_t i) 325_static_inline bool get_visited(const uint8_t *a, int64_t i)
310{ 326{
311 return a[_visited_ind(i)] & _visited_mask(i); 327 return a[VISITED_IND(i)] & VISITED_MASK(i);
312} 328}
313 329
314_static_inline void set_visited(uint8_t *a, int64_t i) 330_static_inline void set_visited(uint8_t *a, int64_t i)
315{ 331{
316 a[_visited_ind(i)] |= _visited_mask(i); 332 a[VISITED_IND(i)] |= VISITED_MASK(i);
317} 333}
318 334
319_static_inline uint8_t 335_static_inline uint8_t
320get_esep_pval(const uint32_t *buf32, int64_t i) 336get_esep_pval(const uint32_t *buf32, int64_t i)
321{ 337{
322 return (buf32[_esep_ind(i)] & _esep_mask(i)) >> _esep_shift(i); 338 return (buf32[ESEP_IND(i)] & ESEP_MASK(i)) >> ESEP_SHIFT(i);
323} 339}
324 340
325_static_inline void 341_static_inline void
326set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val) 342set_esep_pval(uint32_t *buf32, int64_t i, uint8_t val)
327{ 343{
328 buf32[_esep_ind(i)] = 344 buf32[ESEP_IND(i)] =
329 (buf32[_esep_ind(i)] & (~_esep_mask(i))) | (val << _esep_shift(i)); 345 (buf32[ESEP_IND(i)] & (~ESEP_MASK(i))) | (val << ESEP_SHIFT(i));
330} 346}

Generated with cgit - Back to sebastiano.tronto.net