h48

commit a016aa7f78c86c59bab3ae4970f8cc339186bc91
parent d3db14d63a03c4a313e818ba1435433dd18acba4
Author: Sebastiano Tronto <sebastiano@tronto.net>
Date:   Sat, 13 Jul 2024 20:32:59 +0200

Added new bfs attempt, but looks wrong

Diffstat:
M
.gitignore
 | 
2
--
M
TODO.txt
 | 
5
++++-
M
src/solve_h48.h
 | 
89
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------------
M
test/103_gendata_h48_h0/gendata_h48_tests.c
 | 
2
+-

4 files changed, 79 insertions(+), 19 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -1,6 +1,4 @@
 config.mk
-benchmark/results
-benchmark/run
 gen
 debuggen
 perf.data
diff --git a/TODO.txt b/TODO.txt
@@ -1,5 +1,8 @@
 Check stats for all tables using H48stats solver
-  - what now?
+  - try DFS for h0 solver
+    - compare results, the bfs method could be wrong
+    - if faster: remove bfs
+    - if slower: why do I get different results with the new bfs?
 
 Bug in esep table generation
   - Fails for UFRUFU, try command
diff --git a/src/solve_h48.h b/src/solve_h48.h
@@ -46,6 +46,7 @@ typedef struct {
 	uint32_t *cocsepdata;
 	uint32_t *buf32;
 	uint64_t *selfsim;
+	int64_t done;
 	cube_t *crep;
 } bfsarg_esep_t;
 
@@ -88,7 +89,9 @@ _static_inline cube_t invcoord_h48(int64_t, const cube_t *, uint8_t);
 _static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
 _static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
 _static size_t gendata_h48h0k4(void *, uint8_t);
-_static uint64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
+_static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
+_static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
+_static int64_t gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *);
 
 _static_inline bool get_visited(const uint8_t *, int64_t);
 _static_inline void set_visited(uint8_t *, int64_t);
@@ -363,7 +366,7 @@ gendata_h48h0k4(void *buf, uint8_t maxdepth)
 {
 	uint32_t j, *buf32, *info, *cocsepdata;
 	bfsarg_esep_t arg;
-	int64_t sc, cc, tot, esep_max;
+	int64_t sc, cc, esep_max;
 	uint64_t selfsim[COCSEP_CLASSES];
 	cube_t crep[COCSEP_CLASSES];
 	size_t cocsepsize, infosize;
@@ -388,19 +391,19 @@ gendata_h48h0k4(void *buf, uint8_t maxdepth)
 	arg = (bfsarg_esep_t) {
 		.cocsepdata = cocsepdata,
 		.buf32 = buf32,
-		.crep = crep,
-		.selfsim = selfsim
+		.selfsim = selfsim,
+		.crep = crep
 	};
 	for (
-		tot = 1, arg.depth = 1, cc = 0;
-		tot < esep_max && arg.depth <= maxdepth;
+		arg.done = 1, arg.depth = 1, cc = 0;
+		arg.done < esep_max && arg.depth <= maxdepth;
 		arg.depth++
 	) {
 		LOG("esep: generating depth %" PRIu8 "\n", arg.depth);
 		cc = gendata_h48h0k4_bfs(&arg);
-		tot += cc;
+		arg.done += cc;
 		info[arg.depth+1] = cc;
-		LOG("found %" PRIu64 "\n", cc);
+		LOG("found %" PRId64 "\n", cc);
 	}
 
 	info[0] = arg.depth-1;
@@ -415,17 +418,31 @@ gendata_h48h0k4_return_size:
 	return cocsepsize + ESEP_TABLESIZE(0, 4) + infosize;
 }
 
-_static uint64_t
+_static int64_t
 gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
 {
+/*
+TODO: the new method gives a slightly different answer. If the new
+method is correct, then the old bfs method is wrong. Which one is it?   
+Try also DFS and compare results (it could be faster).
+/*
+	if (2 * arg->done < (int64_t)ESEP_MAX(0))
+		return gendata_h48h0k4_bfs_fromdone(arg);
+	else
+		return gendata_h48h0k4_bfs_fromnew(arg);
+*/
+	return gendata_h48h0k4_bfs_fromdone(arg);
+}
+
+_static int64_t
+gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
+{
 	uint8_t c, m, x;
 	uint32_t cc;
-	int64_t i, j, k, t, cocsep_coord, sim, esep_max;
+	int64_t i, j, k, t, cocsep_coord, sim;
 	cube_t cube, moved, transd;
 
-	esep_max = (uint64_t)ESEP_MAX(0);
-
-	for (i = 0, cc = 0; i < esep_max; i++) {
+	for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) {
 		c = get_esep_pval(arg->buf32, i);
 		if (c != arg->depth - 1)
 			continue;
@@ -462,12 +479,54 @@ gendata_h48h0k4_bfs(bfsarg_esep_t *arg)
 	return cc;
 }
 
-_static_inline bool get_visited(const uint8_t *a, int64_t i)
+_static int64_t
+gendata_h48h0k4_bfs_fromnew(bfsarg_esep_t *arg)
+{
+	uint8_t c, m, x;
+	uint32_t cc;
+	int64_t i, j, t, cocsep_coord, sim;
+	cube_t cube, moved, transd;
+
+	for (i = 0, cc = 0; i < (int64_t)ESEP_MAX(0); i++) {
+		c = get_esep_pval(arg->buf32, i);
+		if (c != 0xF)
+			continue;
+		cube = invcoord_h48(i, arg->crep, 0);
+		for (m = 0; m < 18; m++) {
+			moved = move(cube, m);
+			j = coord_h48(moved, arg->cocsepdata, 0);
+			x = get_esep_pval(arg->buf32, j);
+			if (x < arg->depth)
+				goto neighbor_found;
+		}
+		continue;
+neighbor_found:
+		set_esep_pval(arg->buf32, i, arg->depth);
+		cc++;
+		cocsep_coord = i / H48_ESIZE(0);
+		sim = arg->selfsim[cocsep_coord] >> 1;
+		for (t = 1; t < 48 && sim; t++, sim >>= 1) {
+			if (!(sim & 1))
+				continue;
+			transd = transform(cube, t);
+			j = coord_h48(transd, arg->cocsepdata, 0);
+			x = get_esep_pval(arg->buf32, j);
+			set_esep_pval(arg->buf32, j, arg->depth);
+			cc += x == 0xF;
+		}
+	}
+
+	return cc;
+}
+
+_static_inline bool
+get_visited(const uint8_t *a, int64_t i)
 {
 	return a[VISITED_IND(i)] & VISITED_MASK(i);
 }
 
-_static_inline void set_visited(uint8_t *a, int64_t i)
+_static_inline void
+set_visited(uint8_t *a, int64_t i)
 {
 	a[VISITED_IND(i)] |= VISITED_MASK(i);
 }
diff --git a/test/103_gendata_h48_h0/gendata_h48_tests.c b/test/103_gendata_h48_h0/gendata_h48_tests.c
@@ -4,7 +4,7 @@
 #define COCSEPSIZE 1119792
 #define ETABLESIZE ((3393 * 495 * 70) >> 1)
 
-size_t gendata_h48h0k4(void *, uint8_t);
+int64_t gendata_h48h0k4(void *, uint8_t);
 
 void run(void) {
 	char str[STRLENMAX];