9 files changed, 210 insertions, 45 deletions

diff --git a/TODO.txt b/TODO.txt
index 00b85c0..a52945f 100644
--- a/TODO.txt
+++ b/TODO.txt
@@ -1,18 +1,19 @@
 Bug in esep table generation
-  - add pre-computation of h48 coordinates at distance <=7?
-    - unit tests (but how do I test? just leave it there to check regressions)
-  - Add long-running test for h0k4 (maybe as a tool?)
   - compute all tables for h<11
-    - compute visited up to a fixed depth (7? 8?)
+    x compute visited up to a fixed depth 8
     - compute additional step (if needed) to fill <=base
-    - brute-force the last 2 steps (only 18 moves + 18*15 move pairs)
+    - brute-force the last 2 steps (only 18 moves + 18*15 move pairs, + sim)
     - compare with known h0 results (from long-running test)
   - compute table for h=11
-    - is is worth pre-computing stuff?
     - can it be unified to the other computation, or is it much better
       to do it ad hoc?
+  - Add long-running test for h0k4 (maybe as a tool?)
+    - tests for other sizes?
   - optimize
     - use cached values for invcoord_esep? check if it is faster
+    - Unify and improve performance of finding nasty sim
+      (right now we don't even use selfsim)
+    - parallelize with pthread
 
 (OLD:
   - Fails for UFRUFU, try command
diff --git a/src/cube_transform_with_switch.h b/src/cube_transform_with_switch.h
index 45e1d64..18c1c8c 100644
--- a/src/cube_transform_with_switch.h
+++ b/src/cube_transform_with_switch.h
@@ -118,7 +118,7 @@ transform_edges(cube_t c, uint8_t t)
         case _trans_BLm:
                 return _trans_edges_mirrored(BLm, c);
         default:
-                LOG("transform error, unknown transformation\n");
+                LOG("transform error, unknown transformation %" PRIu8 "\n", t);
                 return zero;
         }
 }
@@ -224,7 +224,7 @@ transform_corners(cube_t c, uint8_t t)
         case _trans_BLm:
                 return _trans_corners_mirrored(BLm, c);
         default:
-                LOG("transform error, unknown transformation\n");
+                LOG("transform error, unknown transformation %" PRIu8 "\n", t);
                 return zero;
         }
 }
@@ -330,7 +330,7 @@ transform(cube_t c, uint8_t t)
         case _trans_BLm:
                 return _trans_mirrored(BLm, c);
         default:
-                LOG("transform error, unknown transformation\n");
+                LOG("transform error, unknown transformation %" PRIu8 "\n", t);
                 return zero;
         }
 }
diff --git a/src/solve_h48.h b/src/solve_h48.h
index c7cc91c..ad77156 100644
--- a/src/solve_h48.h
+++ b/src/solve_h48.h
@@ -30,7 +30,7 @@
 typedef struct {
         uint64_t n;
         uint64_t capacity;
-        uint64_t mod;
+        uint64_t randomizer;
         uint64_t *table;
 } h48map_t;
 
@@ -112,7 +112,8 @@ _static_inline void set_esep_pval(uint32_t *, int64_t, uint8_t);
 
 _static size_t gendata_cocsep(void *, uint64_t *, cube_t *);
 _static uint32_t gendata_cocsep_dfs(dfsarg_cocsep_t *);
-_static int64_t gen_h48map_short(uint8_t, const uint32_t *, h48map_t *);
+_static uint64_t gen_h48short(
+    uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *);
 _static size_t gendata_h48h0k4(void *, uint8_t);
 _static int64_t gendata_h48h0k4_bfs(bfsarg_esep_t *);
 _static int64_t gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *);
@@ -123,16 +124,17 @@ _static_inline int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
 _static_inline int8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint32_t *);
 _static_inline bool solve_h48_stop(dfsarg_solveh48_t *);
 _static int64_t solve_h48_dfs(dfsarg_solveh48_t *);
-_static int64_t solve_h48(cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
+_static int64_t solve_h48(
+    cube_t, int8_t, int8_t, int8_t, uint8_t, const void *, char *);
 
 _static int64_t solve_h48stats_dfs(dfsarg_solveh48stats_t *);
 _static int64_t solve_h48stats(cube_t, int8_t, const void *, char [static 12]);
 
 _static void
-h48map_create(h48map_t *map, uint64_t capacity, uint64_t mod)
+h48map_create(h48map_t *map, uint64_t capacity, uint64_t randomizer)
 {
         map->capacity = capacity;
-        map->mod = mod;
+        map->randomizer = randomizer;
 
         map->table = malloc(map->capacity * sizeof(int64_t));
         h48map_clear(map);
@@ -156,7 +158,7 @@ h48map_lookup(h48map_t *map, uint64_t x)
 {
         uint64_t hash, i;
 
-        hash = ((x % map->capacity) * map->mod) % map->capacity;
+        hash = ((x % map->capacity) * map->randomizer) % map->capacity;
         for (i = hash;
              map->table[i] != MAP_UNSET && (map->table[i] & MAP_KEYMASK) != x;
              i = (i+1) % map->capacity
@@ -384,32 +386,55 @@ gendata_cocsep_dfs(dfsarg_cocsep_t *arg)
         return cc;
 }
 
-_static int64_t
-gen_h48map_short(uint8_t n, const uint32_t *cocsepdata, h48map_t *map)
-{
-/*
-        uint8_t i, j, m;
-        int64_t coord;
-        cube_t cube, d;
+_static uint64_t
+gen_h48short(
+        uint8_t n,
+        const uint32_t *cocsepdata,
+        const cube_t *crep,
+        const uint64_t *selfsim,
+        h48map_t *map
+) {
+        uint8_t i, m, t;
+        int64_t coord, cc;
+        uint64_t j, oldn, sim;
+        kvpair_t kv;
+        cube_t cube, d, e;
 
         cube = solvedcube();
         coord = coord_h48(cube, cocsepdata, 11);
+        h48map_insertmin(map, coord, 0);
+        oldn = 0;
+        LOG("Short h48: generating depth 0\nfound %" PRIu8 "\n", map->n-oldn);
         for (i = 0; i < n; i++) {
-                for (j = 0; (coord = h48map_next(map, &j)) != -1; ) {
-                        cube = invcoord_h48(coord, cocsepdata, 11);
+                LOG("Short h48: generating depth %" PRIu8 "\n", i+1);
+                j = 0;
+                oldn = map->n;
+                for (kv = h48map_nextkvpair(map, &j);
+                     j != map->capacity;
+                     kv = h48map_nextkvpair(map, &j)
+                ) {
+                        if (kv.val != i)
+                                continue;
+                        cube = invcoord_h48(kv.key, crep, 11);
                         for (m = 0; m < 18; m++) {
                                 d = move(cube, m);
-TODO
+                                coord = coord_h48(d, cocsepdata, 11);
+                                h48map_insertmin(map, coord, i+1);
+                                cc = coord / H48_ESIZE(11);
+                                sim = selfsim[cc] >> UINT64_C(1);
+                                for (t = 1; t < 48 && sim; t++) {
+                                /* TODO: optimize by using transform_edges,
+                                   corner coordinate is kept */
+                                        e = transform(d, t);
+                                        coord = coord_h48(e, cocsepdata, 11);
+                                        h48map_insertmin(map, coord, i+1);
+                                }
                         }
                 }
+                LOG("found %" PRIu8 "\n", map->n-oldn);
         }
-*/
-}
 
-_static int64_t
-gen_h48set_short_dfs(dfsarg_genh48set_t *arg)
-{
-        /* TODO */
+        return map->n;
 }
 
 /*
@@ -511,7 +536,7 @@ gendata_h48h0k4_bfs_fromdone(bfsarg_esep_t *arg)
                         cc += x != arg->depth;
                         cocsep_coord = j / H48_ESIZE(0);
                         sim = arg->selfsim[cocsep_coord] >> UINT64_C(1);
-                        for (t = 1; t < 48 && sim; t++, sim >>= UINT64_C(1)) {
+                        for (t = 1; t < 48 && sim; t++) {
                                 /* TODO: use only selfsim */
                                 transd = transform(moved, t);
                                 k = coord_h48(transd, arg->cocsepdata, 0);
@@ -553,7 +578,7 @@ neighbor_found:
                 cc++;
                 cocsep_coord = i / H48_ESIZE(0);
                 sim = arg->selfsim[cocsep_coord] >> 1;
-                for (t = 1; t < 48 && sim; t++, sim >>= 1) {
+                for (t = 1; t < 48 && sim; t++) {
                         /* TODO: use only selfsim */
                         transd = transform(cube, t);
                         j = coord_h48(transd, arg->cocsepdata, 0);
diff --git a/test/112_h48map/h48map_tests.c b/test/112_h48map/h48map_tests.c
index ce8f657..d70bc3a 100644
--- a/test/112_h48map/h48map_tests.c
+++ b/test/112_h48map/h48map_tests.c
@@ -1,11 +1,12 @@
 #include "../test.h"
 
 #define MAP_KEYSHIFT          UINT64_C(40)
+#define MAXPOS 1000
 
 typedef struct {
         uint64_t n;
         uint64_t capacity;
-        uint64_t mod;
+        uint64_t randomizer;
         uint64_t *table;
 } h48map_t;
 
@@ -15,9 +16,7 @@ typedef struct {
 } kvpair_t;
 
 void h48map_create(h48map_t *, uint64_t, uint64_t);
-void h48map_clear(h48map_t *);
 void h48map_destroy(h48map_t *);
-uint64_t h48map_lookup(h48map_t *, uint64_t);
 void h48map_insertmin(h48map_t *, uint64_t, uint64_t);
 uint64_t h48map_value(h48map_t *, uint64_t);
 kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
@@ -40,28 +39,26 @@ uint64_t readl(void) {
 
 void run(void) {
         h48map_t map;
-        uint64_t n, i, j, capacity, mod, x, y, v;
-        kvpair_t kv, *a, *b;
+        uint64_t n, i, j, capacity, randomizer, x, y, v;
+        kvpair_t kv, a[MAXPOS], b[MAXPOS];
 
         capacity = readl();
-        mod = readl();
+        randomizer = readl();
         n = readl();
 
-        a = malloc(n * sizeof(kvpair_t));
-        b = malloc(n * sizeof(kvpair_t));
         for (i = 0; i < n; i++) {
                 x = readl();
                 y = readl();
                 a[i] = (kvpair_t) { .key = x, .val = y };
         }
 
-        h48map_create(&map, capacity, mod);
+        h48map_create(&map, capacity, randomizer);
         for (i = 0; i < n; i++)
                 h48map_insertmin(&map, a[i].key, a[i].val);
 
         i = 0;
         for (kv = h48map_nextkvpair(&map, &i), j = 0;
-             i != map.capacity;
+             i != map.capacity && j < MAXPOS;
              kv = h48map_nextkvpair(&map, &i)
         ) {
                 b[j++] = kv;
@@ -83,6 +80,4 @@ void run(void) {
         }
 
         h48map_destroy(&map);
-        free(a);
-        free(b);
 }
diff --git a/test/113_gen_h48short/00_depth_1.in b/test/113_gen_h48short/00_depth_1.in
new file mode 100644
index 0000000..c86f15b
--- /dev/null
+++ b/test/113_gen_h48short/00_depth_1.in
@@ -0,0 +1,28 @@
+73
+157
+1
+
+For longer test:
+
+20000003
+20000023
+8
+
+Short h48: generating depth 0
+found 1
+Short h48: generating depth 1
+found 1
+Short h48: generating depth 2
+found 4
+Short h48: generating depth 3
+found 34
+Short h48: generating depth 4
+found 333
+Short h48: generating depth 5
+found 3815
+Short h48: generating depth 6
+found 45382
+Short h48: generating depth 7
+found 548562
+Short h48: generating depth 8
+found 6839723
diff --git a/test/113_gen_h48short/00_depth_1.out b/test/113_gen_h48short/00_depth_1.out
new file mode 100644
index 0000000..b0dba31
--- /dev/null
+++ b/test/113_gen_h48short/00_depth_1.out
@@ -0,0 +1,3 @@
+2
+0 0
+71075840 1
diff --git a/test/113_gen_h48short/01_depth_3.in b/test/113_gen_h48short/01_depth_3.in
new file mode 100644
index 0000000..920e70a
--- /dev/null
+++ b/test/113_gen_h48short/01_depth_3.in
@@ -0,0 +1,3 @@
+73
+157
+3
diff --git a/test/113_gen_h48short/01_depth_3.out b/test/113_gen_h48short/01_depth_3.out
new file mode 100644
index 0000000..dbce376
--- /dev/null
+++ b/test/113_gen_h48short/01_depth_3.out
@@ -0,0 +1,40 @@
+40
+0 0
+70981632 3
+71075840 1
+71086080 3
+142067712 2
+218789888 3
+218884096 2
+283879424 2
+283899904 3
+283953152 3
+283973632 2
+360548808 3
+360835072 3
+473668032 3
+473956352 3
+499869696 3
+500011008 3
+598679552 3
+599109185 3
+662171648 3
+662601226 3
+724818316 3
+725106688 3
+790513664 3
+790607872 3
+904991108 3
+926726144 3
+928729088 3
+1009662340 3
+1088755203 3
+1171758595 3
+1206452224 3
+1206480896 3
+1277360128 3
+1277454336 3
+1403695492 3
+1403697540 3
+1403736452 3
+1403738500 3
diff --git a/test/113_gen_h48short/gen_h48short.c b/test/113_gen_h48short/gen_h48short.c
new file mode 100644
index 0000000..399ef1e
--- /dev/null
+++ b/test/113_gen_h48short/gen_h48short.c
@@ -0,0 +1,70 @@
+#include "../test.h"
+
+#define COCSEP_CLASSES 3393
+#define MAXPOS 200
+
+typedef struct {
+        uint64_t n;
+        uint64_t capacity;
+        uint64_t randomizer;
+        uint64_t *table;
+} h48map_t;
+
+typedef struct {
+        uint64_t key;
+        uint64_t val;
+} kvpair_t;
+
+void h48map_create(h48map_t *, uint64_t, uint64_t);
+void h48map_destroy(h48map_t *);
+kvpair_t h48map_nextkvpair(h48map_t *, uint64_t *);
+size_t gendata_cocsep(void *, uint64_t *, cube_t *);
+uint64_t gen_h48short(
+    uint8_t, const uint32_t *, const cube_t *, const uint64_t *, h48map_t *);
+
+char str[STRLENMAX];
+
+int compare(const void *x, const void *y) {
+        uint64_t a = ((kvpair_t *)x)->key;
+        uint64_t b = ((kvpair_t *)y)->key;
+
+        if (a > b) return 1;
+        if (a == b) return 0;
+        return -1;
+}
+
+uint64_t readl(void) {
+        fgets(str, STRLENMAX, stdin);
+        return atoll(str);
+}
+
+void run(void) {
+        uint32_t cocsepdata[300000];
+        h48map_t map;
+        uint64_t n, i, j, capacity, randomizer, selfsim[COCSEP_CLASSES];
+        kvpair_t kv, b[MAXPOS];
+        cube_t crep[COCSEP_CLASSES];
+
+        capacity = readl();
+        randomizer = readl();
+        n = readl();
+
+        h48map_create(&map, capacity, randomizer);
+        gendata_cocsep(cocsepdata, selfsim, crep);
+        gen_h48short(n, cocsepdata, crep, selfsim, &map);
+
+        i = 0;
+        for (kv = h48map_nextkvpair(&map, &i), j = 0;
+             i != map.capacity && j < MAXPOS;
+             kv = h48map_nextkvpair(&map, &i)
+        ) {
+                b[j++] = kv;
+        }
+        qsort(b, j, sizeof(kvpair_t), compare);
+
+        printf("%" PRIu64 "\n", map.n);
+        for (i = 0; i < j; i++)
+                printf("%" PRIu64 " %" PRIu64 "\n", b[i].key, b[i].val);
+
+        h48map_destroy(&map);
+}