Merge remote-tracking branch 'upstream/master'

Merge upstream

3 files changed, 150 insertions, 32 deletions

diff --git a/src/solvers/h48/gendata_cocsep.h b/src/solvers/h48/gendata_cocsep.h
index 2189145..262793b 100644
--- a/src/solvers/h48/gendata_cocsep.h
+++ b/src/solvers/h48/gendata_cocsep.h
@@ -25,6 +25,7 @@ STATIC_INLINE void set_visited(uint8_t *, int64_t);
 
 STATIC size_t gendata_cocsep(void *, uint64_t *, cube_t *);
 STATIC uint32_t gendata_cocsep_dfs(cocsep_dfs_arg_t *);
+STATIC void getdistribution_cocsep(const uint32_t *, uint64_t [static 21]);
 
 STATIC_INLINE int8_t get_h48_cdata(cube_t, uint32_t *, uint32_t *);
 
@@ -157,6 +158,17 @@ gendata_cocsep_dfs(cocsep_dfs_arg_t *arg)
         return cc;
 }
 
+STATIC void
+getdistribution_cocsep(const uint32_t *table, uint64_t distr[static 21])
+{
+        size_t i;
+
+        memset(distr, 0, 21 * sizeof(uint64_t));
+
+        for (i = 0; i < COCSEP_TABLESIZE; i++)
+                distr[CBOUND(table[i])]++;
+}
+
 STATIC_INLINE bool
 get_visited(const uint8_t *a, int64_t i)
 {
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h
index 3445570..75b7abf 100644
--- a/src/solvers/h48/gendata_h48.h
+++ b/src/solvers/h48/gendata_h48.h
@@ -103,14 +103,19 @@ STATIC_INLINE bool gendata_h48k2_dfs_stop(cube_t, int8_t, h48k2_dfs_arg_t *);
 STATIC size_t gendata_h48k2_realcoord(gendata_h48_arg_t *);
 STATIC void gendata_h48k2_dfs(h48k2_dfs_arg_t *arg);
 STATIC void * gendata_h48k2_runthread(void *);
-STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t *, uint8_t);
+STATIC tableinfo_t makeinfo_h48k2(gendata_h48_arg_t *);
+STATIC void getdistribution_h48(const uint8_t *,
+    uint64_t [static INFO_DISTRIBUTION_LEN], uint8_t, uint8_t);
 
 STATIC uint32_t *get_cocsepdata_ptr(const void *);
 STATIC uint8_t *get_h48data_ptr(const void *);
 
 STATIC_INLINE uint8_t get_h48_pval(const uint8_t *, int64_t, uint8_t);
 STATIC_INLINE void set_h48_pval(uint8_t *, int64_t, uint8_t, uint8_t);
-STATIC_INLINE uint8_t get_h48_bound(cube_t, uint32_t, uint8_t, uint8_t, uint8_t *);
+STATIC_INLINE uint8_t get_h48_bound(
+    cube_t, uint32_t, uint8_t, uint8_t, uint8_t *);
+
+size_t gendata_h48_derive(uint8_t, const void *, void *);
 
 STATIC uint64_t
 gendata_h48short(gendata_h48short_arg_t *arg)
@@ -387,7 +392,7 @@ gendata_h48k2(gendata_h48_arg_t *arg)
                 [11] = 10
         };
 
-        uint8_t t, selectedbase, *table;
+        uint8_t t, *table;
         int64_t j;
         uint64_t i, ii, inext, count;
         h48map_t shortcubes;
@@ -414,8 +419,9 @@ gendata_h48k2(gendata_h48_arg_t *arg)
         };
         gendata_h48short(&shortarg);
 
-        selectedbase = arg->base < 20 ? arg->base : base[arg->h];
-        arg->info = makeinfo_h48k2(arg, selectedbase);
+        if (arg->base >= 20)
+                arg->base = base[arg->h];
+        arg->info = makeinfo_h48k2(arg);
 
         inext = count = 0;
         pthread_mutex_init(&shortcubes_mutex, NULL);
@@ -425,7 +431,7 @@ gendata_h48k2(gendata_h48_arg_t *arg)
                 dfsarg[i] = (h48k2_dfs_arg_t){
                         .h = arg->h,
                         .k = arg->k,
-                        .base = selectedbase,
+                        .base = arg->base,
                         .shortdepth = shortdepth,
                         .cocsepdata = arg->cocsepdata,
                         .table = table,
@@ -603,14 +609,17 @@ STATIC_INLINE bool
 gendata_h48k2_dfs_stop(cube_t cube, int8_t depth, h48k2_dfs_arg_t *arg)
 {
         uint64_t val;
-        int64_t coord;
+        int64_t coord, mutex;
         int8_t oldval;
 
         if (arg->h == 0 || arg->h == 11) {
                 /* We are in the "real coordinate" case, we can stop
                    if this coordinate has already been visited */
                 coord = coord_h48(cube, arg->cocsepdata, arg->h);
+                mutex = H48_INDEX(coord, arg->k) % CHUNKS;
+                pthread_mutex_lock(arg->table_mutex[mutex]);
                 oldval = get_h48_pval(arg->table, coord, arg->k);
+                pthread_mutex_unlock(arg->table_mutex[mutex]);
                 return oldval <= depth;
         } else {
                 /* With 0 < k < 11 we do not have a "real coordinate".
@@ -637,7 +646,7 @@ gendata_h48k2_realcoord_runthread(void *arg)
 }
 
 STATIC tableinfo_t
-makeinfo_h48k2(gendata_h48_arg_t *arg, uint8_t base)
+makeinfo_h48k2(gendata_h48_arg_t *arg)
 {
         tableinfo_t info;
 
@@ -651,7 +660,7 @@ makeinfo_h48k2(gendata_h48_arg_t *arg, uint8_t base)
                 .classes = 0,
                 .h48h = arg->h,
                 .bits = 2,
-                .base = base,
+                .base = arg->base,
                 .maxvalue = 3,
                 .next = 0,
         };
@@ -662,6 +671,25 @@ makeinfo_h48k2(gendata_h48_arg_t *arg, uint8_t base)
         return info;
 }
 
+STATIC void
+getdistribution_h48(
+        const uint8_t *table,
+        uint64_t distr[static INFO_DISTRIBUTION_LEN],
+        uint8_t h,
+        uint8_t k
+) {
+        uint8_t val;
+        int64_t i, h48max;
+
+        memset(distr, 0, INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+
+        h48max = H48_COORDMAX(h);
+        for (i = 0; i < h48max; i++) {
+                val = get_h48_pval(table, i, k);
+                distr[val]++;
+        }
+}
+
 STATIC uint32_t *
 get_cocsepdata_ptr(const void *data)
 {
@@ -695,3 +723,77 @@ get_h48_bound(cube_t cube, uint32_t cdata, uint8_t h, uint8_t k, uint8_t *table)
         coord = coord_h48_edges(cube, COCLASS(cdata), TTREP(cdata), h);
         return get_h48_pval(table, coord, k);
 }
+
+size_t
+gendata_h48_derive(uint8_t h, const void *fulltable, void *buf)
+{
+        size_t cocsepsize, h48size;
+        uint8_t val_full, val_derive, *h48full, *h48derive;
+        int64_t i, j, h48max;
+        gendata_h48_arg_t arg;
+        tableinfo_t cocsepinfo, fulltableinfo;
+
+        /* Initializing values in case of error */
+        /* TODO cleanup this */
+        fulltableinfo.bits = 2;
+        fulltableinfo.base = 8;
+
+        readtableinfo_n(fulltable, 2, &fulltableinfo);
+        arg.h = h;
+        arg.k = fulltableinfo.bits;
+        arg.maxdepth = 20;
+        arg.buf = buf;
+        arg.cocsepdata = (uint32_t *)((char *)buf + INFOSIZE);
+        arg.base = fulltableinfo.base;
+        arg.info = makeinfo_h48k2(&arg);
+
+        /* Technically this step is redundant, except that we
+           need selfsim and crep */
+        cocsepsize = gendata_cocsep(buf, arg.selfsim, arg.crep);
+        arg.h48buf = (uint8_t *)buf + cocsepsize;
+        h48size = H48_TABLESIZE(h, arg.k) + INFOSIZE;
+
+        if (buf == NULL)
+                goto gendata_h48_derive_return_size;
+
+        if (!readtableinfo(buf, &cocsepinfo)) {
+                LOG("gendata_h48: could not read info for cocsep table\n");
+                goto gendata_h48_derive_error;
+        }
+
+        cocsepinfo.next = cocsepsize;
+        if (!writetableinfo(&cocsepinfo, buf)) {
+                LOG("gendata_h48_derive: could not write info for cocsep table"
+                    " with updated 'next' value\n");
+                goto gendata_h48_derive_error;
+        }
+
+        h48full = (uint8_t *)fulltable + cocsepsize + INFOSIZE;
+        h48derive = (uint8_t *)arg.h48buf + INFOSIZE;
+        memset(h48derive, 0xFF, H48_TABLESIZE(h, arg.k));
+        memset(arg.info.distribution, 0,
+            INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+
+        h48max = H48_COORDMAX(fulltableinfo.h48h);
+        for (i = 0; i < h48max; i++) {
+                if (i % INT64_C(1000000000) == 0 && i > 0)
+                        LOG("Processing %" PRId64 "th coordinate\n", i);
+                j = i >> (int64_t)(fulltableinfo.h48h - h);
+                val_full = get_h48_pval(h48full, i, arg.k);
+                val_derive = get_h48_pval(h48derive, j, arg.k);
+                set_h48_pval(h48derive, j, arg.k, MIN(val_full, val_derive));
+        }
+
+        getdistribution_h48(h48derive, arg.info.distribution, h, arg.k);
+
+        if (!writetableinfo(&arg.info, arg.h48buf)) {
+                LOG("gendata_h48_derive: could not write info for table\n");
+                goto gendata_h48_derive_error;
+        }
+
+gendata_h48_derive_return_size:
+        return cocsepsize + h48size;
+
+gendata_h48_derive_error:
+        return 0;
+}
diff --git a/src/solvers/tables.h b/src/solvers/tables.h
index bad3b2c..a668988 100644
--- a/src/solvers/tables.h
+++ b/src/solvers/tables.h
@@ -7,34 +7,34 @@
 #define TABLETYPE_PRUNING        0
 #define TABLETYPE_SPECIAL        1
 
-#define INFO_OFFSET_SOLVER       0
-#define INFO_OFFSET_TYPE         INFO_SOLVER_STRLEN
+#define INFO_OFFSET_DISTRIBUTION 0
+#define INFO_OFFSET_TYPE         (INFO_DISTRIBUTION_LEN * sizeof(uint64_t))
 #define INFO_OFFSET_INFOSIZE     (INFO_OFFSET_TYPE + sizeof(uint64_t))
 #define INFO_OFFSET_FULLSIZE     (INFO_OFFSET_INFOSIZE + sizeof(uint64_t))
 #define INFO_OFFSET_HASH         (INFO_OFFSET_FULLSIZE + sizeof(uint64_t))
 #define INFO_OFFSET_ENTRIES      (INFO_OFFSET_HASH + sizeof(uint64_t))
 #define INFO_OFFSET_CLASSES      (INFO_OFFSET_ENTRIES + sizeof(uint64_t))
-#define INFO_OFFSET_H48H         (INFO_OFFSET_CLASSES + sizeof(uint64_t))
+#define INFO_OFFSET_NEXT         (INFO_OFFSET_CLASSES + sizeof(uint64_t))
+#define INFO_OFFSET_SOLVER       (INFO_OFFSET_NEXT + sizeof(uint64_t))
+#define INFO_OFFSET_H48H         (INFO_OFFSET_SOLVER + INFO_SOLVER_STRLEN)
 #define INFO_OFFSET_BITS         (INFO_OFFSET_H48H + sizeof(uint8_t))
 #define INFO_OFFSET_BASE         (INFO_OFFSET_BITS + sizeof(uint8_t))
 #define INFO_OFFSET_MAXVALUE     (INFO_OFFSET_BASE + sizeof(uint8_t))
-#define INFO_OFFSET_NEXT         (INFO_OFFSET_MAXVALUE + sizeof(uint8_t))
-#define INFO_OFFSET_DISTRIBUTION (INFO_OFFSET_NEXT + sizeof(uint64_t))
 
 typedef struct {
-        char solver[INFO_SOLVER_STRLEN];
+        uint64_t distribution[INFO_DISTRIBUTION_LEN];
         uint64_t type;
         uint64_t infosize;
         uint64_t fullsize;
         uint64_t hash;
         uint64_t entries;
         uint64_t classes; /* Used only by cocsepdata, for now */
+        uint64_t next;
+        char solver[INFO_SOLVER_STRLEN];
         uint8_t h48h; /* Specific to H48 tables */
         uint8_t bits;
         uint8_t base;
         uint8_t maxvalue;
-        uint64_t next;
-        uint64_t distribution[INFO_DISTRIBUTION_LEN];
 } tableinfo_t;
 
 STATIC bool readtableinfo(const void *, tableinfo_t *);
@@ -54,21 +54,24 @@ readtableinfo(const void *buf, tableinfo_t *info)
                 return false;
         }
 
-        memcpy(info->solver, OFFSET(buf, INFO_OFFSET_SOLVER),
-            INFO_SOLVER_STRLEN);
+        memcpy(info->distribution, OFFSET(buf, INFO_OFFSET_DISTRIBUTION),
+            INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+
         info->type = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_TYPE);
         info->infosize = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_INFOSIZE);
         info->fullsize = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_FULLSIZE);
         info->hash = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_HASH);
         info->entries = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_ENTRIES);
         info->classes = *(const uint64_t *)OFFSET(buf, INFO_OFFSET_CLASSES);
+        info->next = *(const uint64_t* )OFFSET(buf, INFO_OFFSET_NEXT);
+
+        memcpy(info->solver, OFFSET(buf, INFO_OFFSET_SOLVER),
+            INFO_SOLVER_STRLEN);
+
         info->h48h = *OFFSET(buf, INFO_OFFSET_H48H);
         info->bits = *OFFSET(buf, INFO_OFFSET_BITS);
         info->base = *OFFSET(buf, INFO_OFFSET_BASE);
         info->maxvalue = *OFFSET(buf, INFO_OFFSET_MAXVALUE);
-        info->next = *(const uint64_t* )OFFSET(buf, INFO_OFFSET_NEXT);
-        memcpy(info->distribution, OFFSET(buf, INFO_OFFSET_DISTRIBUTION),
-            INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
 
         return true;
 }
@@ -98,6 +101,17 @@ writetableinfo(const tableinfo_t *info, void *buf)
                 return false;
         }
 
+        memcpy(OFFSET(buf, INFO_OFFSET_DISTRIBUTION), info->distribution,
+            INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
+
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_TYPE) = info->type;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_INFOSIZE) = info->infosize;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_FULLSIZE) = info->fullsize;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_HASH) = info->hash;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_ENTRIES) = info->entries;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_CLASSES) = info->classes;
+        *(uint64_t *)OFFSET(buf, INFO_OFFSET_NEXT) = info->next;
+
         memcpy(OFFSET(buf, INFO_OFFSET_SOLVER), info->solver,
             INFO_SOLVER_STRLEN);
 
@@ -106,20 +120,10 @@ writetableinfo(const tableinfo_t *info, void *buf)
                 if (*OFFSET(buf, i) == 0)
                         *OFFSET(buf, i) = 0;
 
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_TYPE) = info->type;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_INFOSIZE) = info->infosize;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_FULLSIZE) = info->fullsize;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_HASH) = info->hash;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_ENTRIES) = info->entries;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_CLASSES) = info->classes;
         *OFFSET(buf, INFO_OFFSET_H48H) = info->h48h;
         *OFFSET(buf, INFO_OFFSET_BITS) = info->bits;
         *OFFSET(buf, INFO_OFFSET_BASE) = info->base;
         *OFFSET(buf, INFO_OFFSET_MAXVALUE) = info->maxvalue;
-        *(uint64_t *)OFFSET(buf, INFO_OFFSET_NEXT) = info->next;
-
-        memcpy(OFFSET(buf, INFO_OFFSET_DISTRIBUTION), info->distribution,
-            INFO_DISTRIBUTION_LEN * sizeof(uint64_t));
 
         return true;
 }