aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48')
-rw-r--r--src/solvers/h48/checkdata.h192
-rw-r--r--src/solvers/h48/gendata_h48.h121
-rw-r--r--src/solvers/h48/gendata_types_macros.h19
-rw-r--r--src/solvers/h48/solve.h20
-rw-r--r--src/solvers/h48/utils.h38
5 files changed, 156 insertions, 234 deletions
diff --git a/src/solvers/h48/checkdata.h b/src/solvers/h48/checkdata.h
index 04afd48..7aa18aa 100644
--- a/src/solvers/h48/checkdata.h
+++ b/src/solvers/h48/checkdata.h
@@ -18,155 +18,113 @@ uint64_t expected_cocsep[21] = {
18struct { 18struct {
19 uint8_t max; 19 uint8_t max;
20 uint64_t table[21]; 20 uint64_t table[21];
21} expected_h48[12][9] = { 21} expected_h48[12] = {
22 [0] = { 22 [0] = {
23 [2] = { 23 .max = 3,
24 .max = 3, 24 .table = {
25 .table = { 25 [0] = 5473562,
26 [0] = 5473562, 26 [1] = 34776317,
27 [1] = 34776317, 27 [2] = 68566704,
28 [2] = 68566704, 28 [3] = 8750867,
29 [3] = 8750867,
30 },
31 },
32 [4] = {
33 .max = 12,
34 .table = {
35 [0] = 1,
36 [1] = 1,
37 [2] = 4,
38 [3] = 34,
39 [4] = 331,
40 [5] = 3612,
41 [6] = 41605,
42 [7] = 474128,
43 [8] = 4953846,
44 [9] = 34776317,
45 [10] = 68566704,
46 [11] = 8749194,
47 [12] = 1673,
48 },
49 }, 29 },
50 }, 30 },
51 [1] = { 31 [1] = {
52 [2] = { 32 .max = 3,
53 .max = 3, 33 .table = {
54 .table = { 34 [0] = 6012079,
55 [0] = 6012079, 35 [1] = 45822302,
56 [1] = 45822302, 36 [2] = 142018732,
57 [2] = 142018732, 37 [3] = 41281787,
58 [3] = 41281787,
59 },
60 }, 38 },
61 }, 39 },
62 [2] = { 40 [2] = {
63 [2] = { 41 .max = 3,
64 .max = 3, 42 .table = {
65 .table = { 43 [0] = 6391286,
66 [0] = 6391286, 44 [1] = 55494785,
67 [1] = 55494785, 45 [2] = 252389935,
68 [2] = 252389935, 46 [3] = 155993794,
69 [3] = 155993794,
70 },
71 }, 47 },
72 }, 48 },
73 [3] = { 49 [3] = {
74 [2] = { 50 .max = 3,
75 .max = 3, 51 .table = {
76 .table = { 52 [0] = 6686828,
77 [0] = 6686828, 53 [1] = 63867852,
78 [1] = 63867852, 54 [2] = 392789689,
79 [2] = 392789689, 55 [3] = 477195231,
80 [3] = 477195231,
81 },
82 }, 56 },
83 }, 57 },
84 [4] = { 58 [4] = {
85 [2] = { 59 .max = 3,
86 .max = 3, 60 .table = {
87 .table = { 61 [0] = 77147213,
88 [0] = 77147213, 62 [1] = 543379415,
89 [1] = 543379415, 63 [2] = 1139570251,
90 [2] = 1139570251, 64 [3] = 120982321,
91 [3] = 120982321,
92 },
93 }, 65 },
94 }, 66 },
95 [5] = { 67 [5] = {
96 [2] = { 68 .max = 3,
97 .max = 3, 69 .table = {
98 .table = { 70 [0] = 82471284,
99 [0] = 82471284, 71 [1] = 687850732,
100 [1] = 687850732, 72 [2] = 2345840746,
101 [2] = 2345840746, 73 [3] = 645995638,
102 [3] = 645995638,
103 },
104 }, 74 },
105 }, 75 },
106 [6] = { 76 [6] = {
107 [2] = { 77 .max = 3,
108 .max = 3, 78 .table = {
109 .table = { 79 [0] = 85941099,
110 [0] = 85941099, 80 [1] = 804752968,
111 [1] = 804752968, 81 [2] = 4077248182,
112 [2] = 4077248182, 82 [3] = 2556374551,
113 [3] = 2556374551,
114 },
115 }, 83 },
116 }, 84 },
117 [7] = { 85 [7] = {
118 [2] = { 86 .max = 3,
119 .max = 3, 87 .table = {
120 .table = { 88 [0] = 88529761,
121 [0] = 88529761, 89 [1] = 897323475,
122 [1] = 897323475, 90 [2] = 6126260791,
123 [2] = 6126260791, 91 [3] = 7936519573,
124 [3] = 7936519573,
125 },
126 }, 92 },
127 }, 93 },
128 [8] = { 94 [8] = {
129 [2] = { 95 .max = 3,
130 .max = 3, 96 .table = {
131 .table = { 97 [0] = 1051579940,
132 [0] = 1051579940, 98 [1] = 8136021316,
133 [1] = 8136021316, 99 [2] = 19024479822,
134 [2] = 19024479822, 100 [3] = 1885186122,
135 [3] = 1885186122,
136 },
137 }, 101 },
138 }, 102 },
139 [9] = { 103 [9] = {
140 [2] = { 104 .max = 3,
141 .max = 3, 105 .table = {
142 .table = { 106 [0] = 1102038189,
143 [0] = 1102038189, 107 [1] = 9888265242,
144 [1] = 9888265242, 108 [2] = 38299375805,
145 [2] = 38299375805, 109 [3] = 10904855164,
146 [3] = 10904855164,
147 },
148 }, 110 },
149 }, 111 },
150 [10] = { 112 [10] = {
151 [2] = { 113 .max = 3,
152 .max = 3, 114 .table = {
153 .table = { 115 [0] = 1133240039,
154 [0] = 1133240039, 116 [1] = 11196285614,
155 [1] = 11196285614, 117 [2] = 64164702961,
156 [2] = 64164702961, 118 [3] = 43894840186,
157 [3] = 43894840186,
158 },
159 }, 119 },
160 }, 120 },
161 [11] = { 121 [11] = {
162 [2] = { 122 .max = 3,
163 .max = 3, 123 .table = {
164 .table = { 124 [0] = 1150763161,
165 [0] = 1150763161, 125 [1] = 12045845660,
166 [1] = 12045845660, 126 [2] = 91163433330,
167 [2] = 91163433330, 127 [3] = 136418095449,
168 [3] = 136418095449,
169 },
170 }, 128 },
171 }, 129 },
172}; 130};
@@ -210,8 +168,8 @@ checkdata_h48(
210 continue; 168 continue;
211 } 169 }
212 170
213 ed = expected_h48[info.h48h][info.bits].table; 171 ed = expected_h48[info.h48h].table;
214 em = expected_h48[info.h48h][info.bits].max; 172 em = expected_h48[info.h48h].max;
215 173
216 LOG("[checkdata] Checking distribution for '%s' from " 174 LOG("[checkdata] Checking distribution for '%s' from "
217 "table preamble\n", info.solver); 175 "table preamble\n", info.solver);
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index e8bb7b2..68111c8 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -2,24 +2,22 @@ STATIC long long gendata_h48_dispatch(
2 const char *, unsigned long long, unsigned char *); 2 const char *, unsigned long long, unsigned char *);
3STATIC uint64_t gendata_h48short(gendata_h48short_arg_t [static 1]); 3STATIC uint64_t gendata_h48short(gendata_h48short_arg_t [static 1]);
4STATIC int64_t gendata_h48(gendata_h48_arg_t [static 1]); 4STATIC int64_t gendata_h48(gendata_h48_arg_t [static 1]);
5STATIC void gendata_h48k2(gendata_h48_arg_t [static 1]); 5STATIC void gendata_h48_maintable(gendata_h48_arg_t [static 1]);
6STATIC void *gendata_h48k2_runthread(void *); 6STATIC void *gendata_h48_runthread(void *);
7 7
8STATIC_INLINE void gendata_h48_mark(gendata_h48_mark_t [static 1]); 8STATIC_INLINE void gendata_h48_mark(gendata_h48_mark_t [static 1]);
9STATIC_INLINE bool gendata_h48k2_dfs_stop( 9STATIC_INLINE bool gendata_h48_dfs_stop(
10 cube_t, int8_t, h48k2_dfs_arg_t [static 1]); 10 cube_t, int8_t, h48_dfs_arg_t [static 1]);
11STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t [static 1]); 11STATIC void gendata_h48_dfs(h48_dfs_arg_t [static 1]);
12STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t [static 1]); 12STATIC tableinfo_t makeinfo_h48(gendata_h48_arg_t [static 1]);
13 13
14STATIC const uint32_t *get_cocsepdata_constptr(const unsigned char *); 14STATIC const uint32_t *get_cocsepdata_constptr(const unsigned char *);
15STATIC const unsigned char *get_h48data_constptr(const unsigned char *); 15STATIC const unsigned char *get_h48data_constptr(const unsigned char *);
16 16
17STATIC_INLINE uint8_t get_h48_pval(const unsigned char *, uint64_t, uint8_t); 17STATIC_INLINE uint8_t get_h48_pval(const unsigned char *, uint64_t);
18STATIC_INLINE void set_h48_pval(unsigned char *, uint64_t, uint8_t, uint8_t); 18STATIC_INLINE void set_h48_pval(unsigned char *, uint64_t, uint8_t);
19STATIC_INLINE uint8_t get_h48_pvalmin( 19STATIC_INLINE uint8_t get_h48_pvalmin(const unsigned char *, uint64_t);
20 const unsigned char *, uint64_t, uint8_t); 20STATIC_INLINE void set_h48_pvalmin(unsigned char *, uint64_t, uint8_t);
21STATIC_INLINE void set_h48_pvalmin(
22 unsigned char *, uint64_t, uint8_t, uint8_t);
23 21
24STATIC long long 22STATIC long long
25gendata_h48_dispatch( 23gendata_h48_dispatch(
@@ -31,7 +29,7 @@ gendata_h48_dispatch(
31 long long err; 29 long long err;
32 gendata_h48_arg_t arg; 30 gendata_h48_arg_t arg;
33 31
34 err = parse_h48_hk(solver, &arg.h, &arg.k); 32 err = parse_h48h(solver, &arg.h);
35 if (err != NISSY_OK) 33 if (err != NISSY_OK)
36 return err; 34 return err;
37 35
@@ -85,7 +83,7 @@ gendata_h48(gendata_h48_arg_t arg[static 1])
85 tableinfo_t cocsepinfo, h48info; 83 tableinfo_t cocsepinfo, h48info;
86 84
87 cocsepsize = COCSEP_FULLSIZE; 85 cocsepsize = COCSEP_FULLSIZE;
88 h48size = INFOSIZE + H48_TABLESIZE(arg->h, arg->k); 86 h48size = INFOSIZE + H48_TABLESIZE(arg->h);
89 eoesepsize = EOESEP_FULLSIZE; 87 eoesepsize = EOESEP_FULLSIZE;
90 88
91 size = cocsepsize + h48size + eoesepsize; 89 size = cocsepsize + h48size + eoesepsize;
@@ -106,11 +104,8 @@ gendata_h48(gendata_h48_arg_t arg[static 1])
106 arg->cocsepdata = (uint32_t *)cocsepdata_offset; 104 arg->cocsepdata = (uint32_t *)cocsepdata_offset;
107 arg->h48buf = (wrapthread_atomic unsigned char*)arg->buf + cocsepsize; 105 arg->h48buf = (wrapthread_atomic unsigned char*)arg->buf + cocsepsize;
108 106
109/* TODO this can probably be removed now? */ 107 /* Compute the main H48 table with two bits per entry */
110 arg->base = 99; 108 gendata_h48_maintable(arg);
111/* */
112
113 gendata_h48k2(arg);
114 109
115 r = readtableinfo(arg->buf_size, arg->buf, &cocsepinfo); 110 r = readtableinfo(arg->buf_size, arg->buf, &cocsepinfo);
116 if (r != NISSY_OK) { 111 if (r != NISSY_OK) {
@@ -152,10 +147,10 @@ gendata_h48(gendata_h48_arg_t arg[static 1])
152} 147}
153 148
154STATIC void 149STATIC void
155gendata_h48k2(gendata_h48_arg_t arg[static 1]) 150gendata_h48_maintable(gendata_h48_arg_t arg[static 1])
156{ 151{
157 /* 152 /*
158 * A good base value for the k=2 tables have few positions with value 153 * A good base value for the h48 tables have few positions with value
159 * 0, because those are treated as lower bound 0 and require a second 154 * 0, because those are treated as lower bound 0 and require a second
160 * lookup in another table, and at the same time not too many positions 155 * lookup in another table, and at the same time not too many positions
161 * with value 3, because some of those are under-estimates. 156 * with value 3, because some of those are under-estimates.
@@ -208,13 +203,13 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
208 uint64_t i, ii, inext, bufsize, done, nshort, velocity; 203 uint64_t i, ii, inext, bufsize, done, nshort, velocity;
209 h48map_t shortcubes; 204 h48map_t shortcubes;
210 gendata_h48short_arg_t shortarg; 205 gendata_h48short_arg_t shortarg;
211 h48k2_dfs_arg_t dfsarg[THREADS]; 206 h48_dfs_arg_t dfsarg[THREADS];
212 wrapthread_define_var_thread_t(thread[THREADS]); 207 wrapthread_define_var_thread_t(thread[THREADS]);
213 wrapthread_define_var_mutex_t(shortcubes_mutex); 208 wrapthread_define_var_mutex_t(shortcubes_mutex);
214 wrapthread_define_var_mutex_t(table_mutex[CHUNKS]); 209 wrapthread_define_var_mutex_t(table_mutex[CHUNKS]);
215 210
216 table = (unsigned char *)arg->h48buf + INFOSIZE; 211 table = (unsigned char *)arg->h48buf + INFOSIZE;
217 memset(table, 0xFF, H48_TABLESIZE(arg->h, arg->k)); 212 memset(table, 0xFF, H48_TABLESIZE(arg->h));
218 213
219 LOG("[H48 gendata] Computing depth <=%" PRIu8 "\n", shortdepth) 214 LOG("[H48 gendata] Computing depth <=%" PRIu8 "\n", shortdepth)
220 h48map_create(&shortcubes, capacity, randomizer); 215 h48map_create(&shortcubes, capacity, randomizer);
@@ -229,9 +224,8 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
229 nshort = shortarg.map->n; 224 nshort = shortarg.map->n;
230 LOG("[H48 gendata] Computed %" PRIu64 " positions\n", nshort); 225 LOG("[H48 gendata] Computed %" PRIu64 " positions\n", nshort);
231 226
232 if (arg->base >= 20) 227 arg->base = base[arg->h];
233 arg->base = base[arg->h]; 228 arg->info = makeinfo_h48(arg);
234 arg->info = makeinfo_h48k2(arg);
235 229
236 inext = 0; 230 inext = 0;
237 count = 0; 231 count = 0;
@@ -239,9 +233,8 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
239 for (i = 0; i < CHUNKS; i++) 233 for (i = 0; i < CHUNKS; i++)
240 wrapthread_mutex_init(&table_mutex[i], NULL); 234 wrapthread_mutex_init(&table_mutex[i], NULL);
241 for (i = 0; i < THREADS; i++) { 235 for (i = 0; i < THREADS; i++) {
242 dfsarg[i] = (h48k2_dfs_arg_t){ 236 dfsarg[i] = (h48_dfs_arg_t){
243 .h = arg->h, 237 .h = arg->h,
244 .k = arg->k,
245 .base = arg->base, 238 .base = arg->base,
246 .shortdepth = shortdepth, 239 .shortdepth = shortdepth,
247 .cocsepdata = arg->cocsepdata, 240 .cocsepdata = arg->cocsepdata,
@@ -257,12 +250,13 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
257 dfsarg[i].table_mutex[ii] = &table_mutex[ii]; 250 dfsarg[i].table_mutex[ii] = &table_mutex[ii];
258 251
259 wrapthread_create( 252 wrapthread_create(
260 &thread[i], NULL, gendata_h48k2_runthread, &dfsarg[i]); 253 &thread[i], NULL, gendata_h48_runthread, &dfsarg[i]);
261 } 254 }
262 255
263 if (NISSY_CANSLEEP) { 256 if (NISSY_CANSLEEP) {
264 /* Log the progress periodically */ 257 /* Log the progress periodically */
265 LOG("Processing 'short cubes'. This will take a while.\n"); 258 LOG("[H48 gendata] Processing 'short cubes'. "
259 "This will take a while.\n");
266 260
267 /* Estimate velocity by checking how much is done after 1s */ 261 /* Estimate velocity by checking how much is done after 1s */
268 msleep(1000); 262 msleep(1000);
@@ -277,8 +271,8 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
277 wrapthread_mutex_lock(&shortcubes_mutex); 271 wrapthread_mutex_lock(&shortcubes_mutex);
278 done = count; 272 done = count;
279 wrapthread_mutex_unlock(&shortcubes_mutex); 273 wrapthread_mutex_unlock(&shortcubes_mutex);
280 LOG("Processed %" PRIu64 " / %" PRIu64 " cubes\n", 274 LOG("[H48 gendata] Processed %" PRIu64 " / %" PRIu64
281 (done / 1000) * 1000, nshort); 275 " cubes\n", (done / 1000) * 1000, nshort);
282 } 276 }
283 } else { 277 } else {
284 LOG("Status updates won't be available because the sleep() " 278 LOG("Status updates won't be available because the sleep() "
@@ -297,14 +291,14 @@ gendata_h48k2(gendata_h48_arg_t arg[static 1])
297} 291}
298 292
299STATIC void * 293STATIC void *
300gendata_h48k2_runthread(void *arg) 294gendata_h48_runthread(void *arg)
301{ 295{
302 uint64_t coord, coordext, coordmin; 296 uint64_t coord, coordext, coordmin;
303 kvpair_t kv; 297 kvpair_t kv;
304 h48k2_dfs_arg_t *dfsarg; 298 h48_dfs_arg_t *dfsarg;
305 wrapthread_define_if_threads(uint64_t, mutex); 299 wrapthread_define_if_threads(uint64_t, mutex);
306 300
307 dfsarg = (h48k2_dfs_arg_t *)arg; 301 dfsarg = (h48_dfs_arg_t *)arg;
308 302
309 while (true) { 303 while (true) {
310 wrapthread_mutex_lock(dfsarg->shortcubes_mutex); 304 wrapthread_mutex_lock(dfsarg->shortcubes_mutex);
@@ -324,12 +318,12 @@ gendata_h48k2_runthread(void *arg)
324 318
325 mutex = H48_LINE(coord) % CHUNKS; 319 mutex = H48_LINE(coord) % CHUNKS;
326 wrapthread_mutex_lock(dfsarg->table_mutex[mutex]); 320 wrapthread_mutex_lock(dfsarg->table_mutex[mutex]);
327 set_h48_pval(dfsarg->table, coordext, dfsarg->k, 0); 321 set_h48_pval(dfsarg->table, coordext, 0);
328 set_h48_pvalmin(dfsarg->table, coordmin, dfsarg->k, kv.val); 322 set_h48_pvalmin(dfsarg->table, coordmin, kv.val);
329 wrapthread_mutex_unlock(dfsarg->table_mutex[mutex]); 323 wrapthread_mutex_unlock(dfsarg->table_mutex[mutex]);
330 } else { 324 } else {
331 dfsarg->cube = invcoord_h48(kv.key, dfsarg->crep, 11); 325 dfsarg->cube = invcoord_h48(kv.key, dfsarg->crep, 11);
332 gendata_h48k2_dfs(dfsarg); 326 gendata_h48_dfs(dfsarg);
333 } 327 }
334 } 328 }
335 329
@@ -337,7 +331,7 @@ gendata_h48k2_runthread(void *arg)
337} 331}
338 332
339STATIC void 333STATIC void
340gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1]) 334gendata_h48_dfs(h48_dfs_arg_t arg[static 1])
341{ 335{
342 int8_t d; 336 int8_t d;
343 uint8_t m[4]; 337 uint8_t m[4];
@@ -346,7 +340,6 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1])
346 340
347 markarg = (gendata_h48_mark_t) { 341 markarg = (gendata_h48_mark_t) {
348 .h = arg->h, 342 .h = arg->h,
349 .k = arg->k,
350 .base = arg->base, 343 .base = arg->base,
351 .cocsepdata = arg->cocsepdata, 344 .cocsepdata = arg->cocsepdata,
352 .selfsim = arg->selfsim, 345 .selfsim = arg->selfsim,
@@ -365,7 +358,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1])
365 for (m[0] = 0; m[0] < 18; m[0]++) { 358 for (m[0] = 0; m[0] < 18; m[0]++) {
366 markarg.depth = d+1; 359 markarg.depth = d+1;
367 cube[0] = move(arg->cube, m[0]); 360 cube[0] = move(arg->cube, m[0]);
368 if (gendata_h48k2_dfs_stop(cube[0], d+1, arg)) 361 if (gendata_h48_dfs_stop(cube[0], d+1, arg))
369 continue; 362 continue;
370 markarg.cube = cube[0]; 363 markarg.cube = cube[0];
371 gendata_h48_mark(&markarg); 364 gendata_h48_mark(&markarg);
@@ -378,7 +371,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1])
378 continue; 371 continue;
379 } 372 }
380 cube[1] = move(cube[0], m[1]); 373 cube[1] = move(cube[0], m[1]);
381 if (gendata_h48k2_dfs_stop(cube[1], d+2, arg)) 374 if (gendata_h48_dfs_stop(cube[1], d+2, arg))
382 continue; 375 continue;
383 markarg.cube = cube[1]; 376 markarg.cube = cube[1];
384 gendata_h48_mark(&markarg); 377 gendata_h48_mark(&markarg);
@@ -393,7 +386,7 @@ gendata_h48k2_dfs(h48k2_dfs_arg_t arg[static 1])
393 continue; 386 continue;
394 } 387 }
395 cube[2] = move(cube[1], m[2]); 388 cube[2] = move(cube[1], m[2]);
396 if (gendata_h48k2_dfs_stop(cube[2], d+3, arg)) 389 if (gendata_h48_dfs_stop(cube[2], d+3, arg))
397 continue; 390 continue;
398 markarg.cube = cube[2]; 391 markarg.cube = cube[2];
399 gendata_h48_mark(&markarg); 392 gendata_h48_mark(&markarg);
@@ -430,18 +423,18 @@ gendata_h48_mark(gendata_h48_mark_t arg[static 1])
430 423
431 mutex = H48_LINE(coord) % CHUNKS; 424 mutex = H48_LINE(coord) % CHUNKS;
432 wrapthread_mutex_lock(arg->table_mutex[mutex]); 425 wrapthread_mutex_lock(arg->table_mutex[mutex]);
433 oldval = get_h48_pval(arg->table, coordext, arg->k); 426 oldval = get_h48_pval(arg->table, coordext);
434 newval = (uint8_t)MAX(arg->depth, 0); 427 newval = (uint8_t)MAX(arg->depth, 0);
435 v = MIN(newval, oldval); 428 v = MIN(newval, oldval);
436 set_h48_pval(arg->table, coordext, arg->k, v); 429 set_h48_pval(arg->table, coordext, v);
437 v = arg->depth + arg->base; 430 v = arg->depth + arg->base;
438 set_h48_pvalmin(arg->table, coordmin, arg->k, v); 431 set_h48_pvalmin(arg->table, coordmin, v);
439 wrapthread_mutex_unlock(arg->table_mutex[mutex]); 432 wrapthread_mutex_unlock(arg->table_mutex[mutex]);
440 ) 433 )
441} 434}
442 435
443STATIC_INLINE bool 436STATIC_INLINE bool
444gendata_h48k2_dfs_stop(cube_t cube, int8_t d, h48k2_dfs_arg_t arg[static 1]) 437gendata_h48_dfs_stop(cube_t cube, int8_t d, h48_dfs_arg_t arg[static 1])
445{ 438{
446 uint64_t val; 439 uint64_t val;
447 uint64_t coord, coordext; 440 uint64_t coord, coordext;
@@ -455,11 +448,11 @@ gendata_h48k2_dfs_stop(cube_t cube, int8_t d, h48k2_dfs_arg_t arg[static 1])
455 coordext = H48_LINE_EXT(coord); 448 coordext = H48_LINE_EXT(coord);
456 mutex = H48_LINE(coord) % CHUNKS; 449 mutex = H48_LINE(coord) % CHUNKS;
457 wrapthread_mutex_lock(arg->table_mutex[mutex]); 450 wrapthread_mutex_lock(arg->table_mutex[mutex]);
458 oldval = get_h48_pval(arg->table, coordext, arg->k); 451 oldval = get_h48_pval(arg->table, coordext);
459 wrapthread_mutex_unlock(arg->table_mutex[mutex]); 452 wrapthread_mutex_unlock(arg->table_mutex[mutex]);
460 return oldval <= d; 453 return oldval <= d;
461 } else { 454 } else {
462 /* With 0 < k < 11 we do not have a "real coordinate". 455 /* With 0 < h < 11 we do not have a "real coordinate".
463 The best we can do is checking if we backtracked to 456 The best we can do is checking if we backtracked to
464 one of the "short cubes". */ 457 one of the "short cubes". */
465 coord = coord_h48(cube, arg->cocsepdata, 11); 458 coord = coord_h48(cube, arg->cocsepdata, 11);
@@ -469,15 +462,15 @@ gendata_h48k2_dfs_stop(cube_t cube, int8_t d, h48k2_dfs_arg_t arg[static 1])
469} 462}
470 463
471STATIC tableinfo_t 464STATIC tableinfo_t
472makeinfo_h48k2(gendata_h48_arg_t arg[static 1]) 465makeinfo_h48(gendata_h48_arg_t arg[static 1])
473{ 466{
474 tableinfo_t info; 467 tableinfo_t info;
475 468
476 info = (tableinfo_t) { 469 info = (tableinfo_t) {
477 .solver = "h48 solver h = , k = 2", 470 .solver = "h48 solver h = ",
478 .type = TABLETYPE_PRUNING, 471 .type = TABLETYPE_PRUNING,
479 .infosize = INFOSIZE, 472 .infosize = INFOSIZE,
480 .fullsize = H48_TABLESIZE(arg->h, 2) + INFOSIZE, 473 .fullsize = H48_TABLESIZE(arg->h) + INFOSIZE,
481 .hash = 0, 474 .hash = 0,
482 .entries = H48_COORDMAX(arg->h) + 2 * H48_LINES(arg->h), 475 .entries = H48_COORDMAX(arg->h) + 2 * H48_LINES(arg->h),
483 .classes = 0, 476 .classes = 0,
@@ -507,31 +500,31 @@ get_h48data_constptr(const unsigned char *data)
507} 500}
508 501
509STATIC_INLINE uint8_t 502STATIC_INLINE uint8_t
510get_h48_pval(const unsigned char *table, uint64_t i, uint8_t k) 503get_h48_pval(const unsigned char *table, uint64_t i)
511{ 504{
512 return (table[H48_INDEX(i, k)] & H48_MASK(i, k)) >> H48_SHIFT(i, k); 505 return (table[H48_INDEX(i)] & H48_MASK(i)) >> H48_SHIFT(i);
513} 506}
514 507
515STATIC_INLINE uint8_t 508STATIC_INLINE uint8_t
516get_h48_pvalmin(const unsigned char *table, uint64_t i, uint8_t k) 509get_h48_pvalmin(const unsigned char *table, uint64_t i)
517{ 510{
518 return (get_h48_pval(table, i, k) << UINT8_C(2)) + 511 return (get_h48_pval(table, i) << UINT8_C(2)) +
519 get_h48_pval(table, i+UINT64_C(1), k); 512 get_h48_pval(table, i+UINT64_C(1));
520} 513}
521 514
522STATIC_INLINE void 515STATIC_INLINE void
523set_h48_pval(unsigned char *table, uint64_t i, uint8_t k, uint8_t val) 516set_h48_pval(unsigned char *table, uint64_t i, uint8_t val)
524{ 517{
525 table[H48_INDEX(i, k)] = (table[H48_INDEX(i, k)] & (~H48_MASK(i, k))) 518 table[H48_INDEX(i)] = (table[H48_INDEX(i)] & (~H48_MASK(i)))
526 | (val << H48_SHIFT(i, k)); 519 | (val << H48_SHIFT(i));
527} 520}
528 521
529STATIC_INLINE void 522STATIC_INLINE void
530set_h48_pvalmin(unsigned char *table, uint64_t i, uint8_t k, uint8_t val) 523set_h48_pvalmin(unsigned char *table, uint64_t i, uint8_t val)
531{ 524{
532 uint8_t v; 525 uint8_t v;
533 526
534 v = MIN(val, get_h48_pvalmin(table, i, k)); 527 v = MIN(val, get_h48_pvalmin(table, i));
535 set_h48_pval(table, i, k, v >> UINT8_C(2)); 528 set_h48_pval(table, i, v >> UINT8_C(2));
536 set_h48_pval(table, i+UINT64_C(1), k, v % UINT8_C(4)); 529 set_h48_pval(table, i+UINT64_C(1), v % UINT8_C(4));
537} 530}
diff --git a/src/solvers/h48/gendata_types_macros.h b/src/solvers/h48/gendata_types_macros.h
index 16f0be3..9bce2c9 100644
--- a/src/solvers/h48/gendata_types_macros.h
+++ b/src/solvers/h48/gendata_types_macros.h
@@ -20,13 +20,10 @@
20 20
21#define H48_COORDMAX_NOEO (COCSEP_CLASSES * ESEP_MAX) 21#define H48_COORDMAX_NOEO (COCSEP_CLASSES * ESEP_MAX)
22#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (uint64_t)(h)) 22#define H48_COORDMAX(h) (H48_COORDMAX_NOEO << (uint64_t)(h))
23#define H48_DIV(k) ((size_t)8 / (size_t)(k))
24#define H48_TABLESIZE_K4(h) DIV_ROUND_UP((size_t)H48_COORDMAX(h), H48_DIV(4))
25 23
26#define H48_COEFF(k) (UINT64_C(8) / (uint64_t)(k)) 24#define H48_INDEX(i) ((i) / UINT64_C(4))
27#define H48_INDEX(i, k) ((i) / H48_COEFF(k)) 25#define H48_SHIFT(i) (UINT8_C(2) * (uint8_t)((i) % UINT64_C(4)))
28#define H48_SHIFT(i, k) ((uint8_t)(k) * (uint8_t)((i) % H48_COEFF(k))) 26#define H48_MASK(i) (UINT8_C(3) << H48_SHIFT(i))
29#define H48_MASK(i, k) ((UINT8_BIT(k) - UINT8_C(1)) << H48_SHIFT(i, k))
30 27
31#define H48_LINE_BITS UINT64_C(512) 28#define H48_LINE_BITS UINT64_C(512)
32#define H48_LINE_BYTES (H48_LINE_BITS >> UINT64_C(3)) 29#define H48_LINE_BYTES (H48_LINE_BITS >> UINT64_C(3))
@@ -37,10 +34,7 @@
37#define H48_LINE_MIN(i) \ 34#define H48_LINE_MIN(i) \
38 ((H48_LINE(i) + UINT64_C(1)) * H48_LINE_ALLCOORDS - UINT64_C(2)) 35 ((H48_LINE(i) + UINT64_C(1)) * H48_LINE_ALLCOORDS - UINT64_C(2))
39#define H48_LINES(h) DIV_ROUND_UP(H48_COORDMAX(h), H48_LINE_COORDS) 36#define H48_LINES(h) DIV_ROUND_UP(H48_COORDMAX(h), H48_LINE_COORDS)
40#define H48_TABLESIZE_K2(h) ((size_t)(H48_LINE_BYTES * H48_LINES(h))) 37#define H48_TABLESIZE(h) ((size_t)(H48_LINE_BYTES * H48_LINES(h)))
41
42#define H48_TABLESIZE(h, k) \
43 ((k) == 4 ? H48_TABLESIZE_K4(h) : H48_TABLESIZE_K2(h))
44 38
45#define CHUNKS 2000 39#define CHUNKS 2000
46 40
@@ -76,7 +70,6 @@ typedef struct {
76 70
77typedef struct { 71typedef struct {
78 uint8_t h; 72 uint8_t h;
79 uint8_t k;
80 uint8_t base; 73 uint8_t base;
81 uint8_t maxdepth; 74 uint8_t maxdepth;
82 tableinfo_t info; 75 tableinfo_t info;
@@ -99,7 +92,6 @@ typedef struct {
99typedef struct { 92typedef struct {
100 cube_t cube; 93 cube_t cube;
101 uint8_t h; 94 uint8_t h;
102 uint8_t k;
103 uint8_t base; 95 uint8_t base;
104 uint8_t shortdepth; 96 uint8_t shortdepth;
105 uint32_t *cocsepdata; 97 uint32_t *cocsepdata;
@@ -111,13 +103,12 @@ typedef struct {
111 wrapthread_define_struct_mutex_t(*table_mutex[CHUNKS]); 103 wrapthread_define_struct_mutex_t(*table_mutex[CHUNKS]);
112 uint64_t *next; 104 uint64_t *next;
113 wrapthread_atomic uint64_t *count; 105 wrapthread_atomic uint64_t *count;
114} h48k2_dfs_arg_t; 106} h48_dfs_arg_t;
115 107
116typedef struct { 108typedef struct {
117 cube_t cube; 109 cube_t cube;
118 int8_t depth; 110 int8_t depth;
119 uint8_t h; 111 uint8_t h;
120 uint8_t k;
121 uint8_t base; 112 uint8_t base;
122 uint32_t *cocsepdata; 113 uint32_t *cocsepdata;
123 uint64_t *selfsim; 114 uint64_t *selfsim;
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h
index 047d13e..8ac596d 100644
--- a/src/solvers/h48/solve.h
+++ b/src/solvers/h48/solve.h
@@ -30,7 +30,6 @@ typedef struct {
30 bool use_lb_normal; 30 bool use_lb_normal;
31 bool use_lb_inverse; 31 bool use_lb_inverse;
32 uint8_t h; 32 uint8_t h;
33 uint8_t k;
34 uint8_t base; 33 uint8_t base;
35 const uint32_t *cocsepdata; 34 const uint32_t *cocsepdata;
36 const unsigned char *h48data; 35 const unsigned char *h48data;
@@ -93,10 +92,10 @@ STATIC long long solve_h48_dispatch(
93 void *poll_status_data 92 void *poll_status_data
94) 93)
95{ 94{
96 uint8_t h, k; 95 uint8_t h;
97 long long err; 96 long long err;
98 97
99 err = parse_h48_hk(solver, &h, &k); 98 err = parse_h48h(solver, &h);
100 if (err != NISSY_OK) 99 if (err != NISSY_OK)
101 return err; 100 return err;
102 101
@@ -142,15 +141,14 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1])
142 coord = coord_h48_edges( 141 coord = coord_h48_edges(
143 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); 142 arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h);
144 coordext = H48_LINE_EXT(coord); 143 coordext = H48_LINE_EXT(coord);
145 arg->lb_inverse = get_h48_pval(arg->h48data, coordext, arg->k); 144 arg->lb_inverse = get_h48_pval(arg->h48data, coordext);
146 arg->table_lookups++; 145 arg->table_lookups++;
147 146
148 if (arg->k == 2 && arg->lb_inverse == 0) { 147 if (arg->lb_inverse == 0) {
149 arg->table_fallbacks++; 148 arg->table_fallbacks++;
150 149
151 coordmin = H48_LINE_MIN(coord); 150 coordmin = H48_LINE_MIN(coord);
152 pval_min = get_h48_pvalmin( 151 pval_min = get_h48_pvalmin(arg->h48data, coordmin);
153 arg->h48data, coordmin, arg->k);
154 pval_eoesep = get_eoesep_pval_cube( 152 pval_eoesep = get_eoesep_pval_cube(
155 arg->h48data_fallback_eoesep, arg->inverse); 153 arg->h48data_fallback_eoesep, arg->inverse);
156 arg->lb_inverse = MAX(pval_min, pval_eoesep); 154 arg->lb_inverse = MAX(pval_min, pval_eoesep);
@@ -172,15 +170,14 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1])
172 coord = coord_h48_edges( 170 coord = coord_h48_edges(
173 arg->cube, COCLASS(data), TTREP(data), arg->h); 171 arg->cube, COCLASS(data), TTREP(data), arg->h);
174 coordext = H48_LINE_EXT(coord); 172 coordext = H48_LINE_EXT(coord);
175 arg->lb_normal = get_h48_pval(arg->h48data, coordext, arg->k); 173 arg->lb_normal = get_h48_pval(arg->h48data, coordext);
176 arg->table_lookups++; 174 arg->table_lookups++;
177 175
178 if (arg->k == 2 && arg->lb_normal == 0) { 176 if (arg->lb_normal == 0) {
179 arg->table_fallbacks++; 177 arg->table_fallbacks++;
180 178
181 coordmin = H48_LINE_MIN(coord); 179 coordmin = H48_LINE_MIN(coord);
182 pval_min = get_h48_pval( 180 pval_min = get_h48_pval(arg->h48data, coordmin);
183 arg->h48data, coordmin, arg->k);
184 pval_eoesep = get_eoesep_pval_cube( 181 pval_eoesep = get_eoesep_pval_cube(
185 arg->h48data_fallback_eoesep, arg->cube); 182 arg->h48data_fallback_eoesep, arg->cube);
186 arg->lb_normal = MAX(pval_min, pval_eoesep); 183 arg->lb_normal = MAX(pval_min, pval_eoesep);
@@ -515,7 +512,6 @@ solve_h48(
515 .start_cube = oc.cube, 512 .start_cube = oc.cube,
516 .cube = oc.cube, 513 .cube = oc.cube,
517 .h = info.h48h, 514 .h = info.h48h,
518 .k = info.bits,
519 .base = info.base, 515 .base = info.base,
520 .cocsepdata = cocsepdata, 516 .cocsepdata = cocsepdata,
521 .h48data = h48data, 517 .h48data = h48data,
diff --git a/src/solvers/h48/utils.h b/src/solvers/h48/utils.h
index 17f1c94..682eb1d 100644
--- a/src/solvers/h48/utils.h
+++ b/src/solvers/h48/utils.h
@@ -4,22 +4,21 @@
4#define H48_HMAX UINT8_C(7) 4#define H48_HMAX UINT8_C(7)
5#endif 5#endif
6 6
7long long parse_h48_hk( 7long long parse_h48h(const char *, uint8_t [static 1]);
8 const char *, uint8_t [static 1], uint8_t [static 1]);
9STATIC long long dataid_h48(const char *, char [static NISSY_SIZE_DATAID]); 8STATIC long long dataid_h48(const char *, char [static NISSY_SIZE_DATAID]);
10 9
11long long 10long long
12parse_h48_hk(const char *buf, uint8_t h[static 1], uint8_t k[static 1]) 11parse_h48h(const char *buf, uint8_t h[static 1])
13{ 12{
14 char format_error_msg[100]; 13 char format_error_msg[100];
15 sprintf(format_error_msg, "[H48] Error parsing H48 solver: must be in " 14 sprintf(format_error_msg, "[H48] Error parsing H48 solver: must be in "
16 "'h48h*k*' format, but got '%s'\n", buf); 15 "'h48h*' format, but got '%s'\n", buf);
17 16
18 buf += 3; 17 buf += 3;
19 18
20 if (*buf != 'h') { 19 if (*buf != 'h') {
21 LOG(format_error_msg); 20 LOG(format_error_msg);
22 goto parse_h48_hk_error; 21 goto parse_h48h_error;
23 } 22 }
24 buf++; 23 buf++;
25 24
@@ -27,48 +26,33 @@ parse_h48_hk(const char *buf, uint8_t h[static 1], uint8_t k[static 1])
27 if (*h > H48_HMAX) { 26 if (*h > H48_HMAX) {
28 LOG("[H48] Invalid value %" PRIu8 " for parameter h (must be " 27 LOG("[H48] Invalid value %" PRIu8 " for parameter h (must be "
29 "at most %" PRIu8 ")\n", *h, H48_HMAX); 28 "at most %" PRIu8 ")\n", *h, H48_HMAX);
30 goto parse_h48_hk_error; 29 goto parse_h48h_error;
31 } 30 }
32 31
33 for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++) { 32 for ( ; *buf >= 0 + '0' && *buf <= 9 + '0'; buf++) {
34 if (*buf == 0) { 33 if (*buf == 0) {
35 LOG(format_error_msg); 34 LOG(format_error_msg);
36 goto parse_h48_hk_error; 35 goto parse_h48h_error;
37 } 36 }
38 } 37 }
39 38
40 if (*buf != 'k') {
41 LOG(format_error_msg);
42 goto parse_h48_hk_error;
43 }
44 buf++;
45
46 *k = atoi(buf);
47 if (!(*k == 2 || (*k == 4 && *h == 0))) {
48 LOG("[H48] Invalid combinations of values h=%" PRIu8 " and k=%"
49 PRIu8 " for parameters h and k\n", *h, *k);
50 goto parse_h48_hk_error;
51 }
52
53 return NISSY_OK; 39 return NISSY_OK;
54 40
55parse_h48_hk_error: 41parse_h48h_error:
56 *h = 0; 42 *h = 0;
57 *k = 0;
58 return NISSY_ERROR_INVALID_SOLVER; 43 return NISSY_ERROR_INVALID_SOLVER;
59} 44}
60 45
61STATIC long long 46STATIC long long
62dataid_h48(const char *hk, char buf[static NISSY_SIZE_DATAID]) 47dataid_h48(const char *str, char buf[static NISSY_SIZE_DATAID])
63{ 48{
64 uint8_t h, k; 49 uint8_t h;
65 long long err; 50 long long err;
66 51
67 err = parse_h48_hk(hk, &h, &k); 52 err = parse_h48h(str, &h);
68 if (err < 0) 53 if (err < 0)
69 return err; 54 return err;
70 55
71 sprintf(buf, "h48h%" PRIu8 "k%" PRIu8 "%s", h, k, 56 sprintf(buf, "h48h%" PRIu8, h);
72 k == 2 ? "i" : "");
73 return NISSY_OK; 57 return NISSY_OK;
74} 58}

Generated with cgit - Back to sebastiano.tronto.net