Version abc80130_2

1 files changed, 441 insertions, 0 deletions

diff --git a/src/misc/espresso/unate.c b/src/misc/espresso/unate.c
new file mode 100644
index 00000000..bd71207f
--- /dev/null
+++ b/src/misc/espresso/unate.c
@@ -0,0 +1,441 @@
+/*
+ * Revision Control Information
+ *
+ * $Source$
+ * $Author$
+ * $Revision$
+ * $Date$
+ *
+ */
+/*
+ *  unate.c -- routines for dealing with unate functions
+ */
+
+#include "espresso.h"
+
+static pset_family abs_covered();
+static pset_family abs_covered_many();
+static int abs_select_restricted();
+
+pcover map_cover_to_unate(T)
+pcube *T;
+{
+    register unsigned int word_test, word_set, bit_test, bit_set;
+    register pcube p, pA;
+    pset_family A;
+    pcube *T1;
+    int ncol, i;
+
+    A = sf_new(CUBELISTSIZE(T), cdata.vars_unate);
+    A->count = CUBELISTSIZE(T);
+    foreachi_set(A, i, p) {
+    (void) set_clear(p, A->sf_size);
+    }
+    ncol = 0;
+
+    for(i = 0; i < cube.size; i++) {
+    if (cdata.part_zeros[i] > 0) {
+        assert(ncol <= cdata.vars_unate);
+
+        /* Copy a column from T to A */
+        word_test = WHICH_WORD(i);
+        bit_test = 1 << WHICH_BIT(i);
+        word_set = WHICH_WORD(ncol);
+        bit_set = 1 << WHICH_BIT(ncol);
+
+        pA = A->data;
+        for(T1 = T+2; (p = *T1++) != 0; ) {
+        if ((p[word_test] & bit_test) == 0) {
+            pA[word_set] |= bit_set;
+        }
+        pA += A->wsize;
+        }
+
+        ncol++;
+    }
+    }
+
+    return A;
+}
+
+pcover map_unate_to_cover(A)
+pset_family A;
+{
+    register int i, ncol, lp;
+    register pcube p, pB;
+    int var, nunate, *unate;
+    pcube last;
+    pset_family B;
+
+    B = sf_new(A->count, cube.size);
+    B->count = A->count;
+
+    /* Find the unate variables */
+    unate = ALLOC(int, cube.num_vars);
+    nunate = 0;
+    for(var = 0; var < cube.num_vars; var++) {
+    if (cdata.is_unate[var]) {
+        unate[nunate++] = var;
+    }
+    }
+
+    /* Loop for each set of A */
+    pB = B->data;
+    foreach_set(A, last, p) {
+
+    /* Initialize this set of B */
+    INLINEset_fill(pB, cube.size);
+
+    /* Now loop for the unate variables; if the part is in A,
+     * then this variable of B should be a single 1 in the unate
+     * part.
+     */
+    for(ncol = 0; ncol < nunate; ncol++) {
+        if (is_in_set(p, ncol)) {
+        lp = cube.last_part[unate[ncol]];
+        for(i = cube.first_part[unate[ncol]]; i <= lp; i++) {
+            if (cdata.part_zeros[i] == 0) {
+            set_remove(pB, i);
+            }
+        }
+        }
+    }
+    pB += B->wsize;
+    }
+
+    FREE(unate);
+    return B;
+}
+
+/*
+ *  unate_compl
+ */
+
+pset_family unate_compl(A)
+pset_family A;
+{
+    register pset p, last;
+
+    /* Make sure A is single-cube containment minimal */
+/*    A = sf_rev_contain(A);*/
+
+    foreach_set(A, last, p) {
+    PUTSIZE(p, set_ord(p));
+    }
+
+    /* Recursively find the complement */
+    A = unate_complement(A);
+
+    /* Now, we can guarantee a minimal result by containing the result */
+    A = sf_rev_contain(A);
+    return A;
+}
+
+
+/*
+ *  Assume SIZE(p) records the size of each set
+ */
+pset_family unate_complement(A)
+pset_family A;            /* disposes of A */
+{
+    pset_family Abar;
+    register pset p, p1, restrict;
+    register int i;
+    int max_i, min_set_ord, j;
+
+    /* Check for no sets in the matrix -- complement is the universe */
+    if (A->count == 0) {
+    sf_free(A);
+    Abar = sf_new(1, A->sf_size);
+    (void) set_clear(GETSET(Abar, Abar->count++), A->sf_size);
+
+    /* Check for a single set in the maxtrix -- compute de Morgan complement */
+    } else if (A->count == 1) {
+    p = A->data;
+    Abar = sf_new(A->sf_size, A->sf_size);
+    for(i = 0; i < A->sf_size; i++) {
+        if (is_in_set(p, i)) {
+        p1 = set_clear(GETSET(Abar, Abar->count++), A->sf_size);
+        set_insert(p1, i);
+        }
+    }
+    sf_free(A);
+
+    } else {
+
+    /* Select splitting variable as the variable which belongs to a set
+     * of the smallest size, and which has greatest column count
+     */
+    restrict = set_new(A->sf_size);
+    min_set_ord = A->sf_size + 1;
+    foreachi_set(A, i, p) {
+        if (SIZE(p) < min_set_ord) {
+        set_copy(restrict, p);
+        min_set_ord = SIZE(p);
+        } else if (SIZE(p) == min_set_ord) {
+        set_or(restrict, restrict, p);
+        }
+    }
+
+    /* Check for no data (shouldn't happen ?) */
+    if (min_set_ord == 0) {
+        A->count = 0;
+        Abar = A;
+
+    /* Check for "essential" columns */
+    } else if (min_set_ord == 1) {
+        Abar = unate_complement(abs_covered_many(A, restrict));
+        sf_free(A);
+        foreachi_set(Abar, i, p) {
+        set_or(p, p, restrict);
+        }
+
+    /* else, recur as usual */
+    } else {
+        max_i = abs_select_restricted(A, restrict);
+
+        /* Select those rows of A which are not covered by max_i,
+         * recursively find all minimal covers of these rows, and
+         * then add back in max_i
+         */
+        Abar = unate_complement(abs_covered(A, max_i));
+        foreachi_set(Abar, i, p) {
+        set_insert(p, max_i);
+        }
+
+        /* Now recur on A with all zero's on column max_i */
+        foreachi_set(A, i, p) {
+        if (is_in_set(p, max_i)) {
+            set_remove(p, max_i);
+            j = SIZE(p) - 1;
+            PUTSIZE(p, j);
+        }
+        }
+
+        Abar = sf_append(Abar, unate_complement(A));
+    }
+    set_free(restrict);
+    }
+
+    return Abar;
+}
+
+pset_family exact_minimum_cover(T)
+IN pset_family T;
+{
+    register pset p, last, p1;
+    register int i, n;
+    int lev, lvl;
+    pset nlast;
+    pset_family temp;
+    long start = ptime();
+    struct {
+    pset_family sf;
+    int level;
+    } stack[32];                /* 32 suffices for 2 ** 32 cubes ! */
+
+    if (T->count <= 0)
+    return sf_new(1, T->sf_size);
+    for(n = T->count, lev = 0; n != 0; n >>= 1, lev++)   ;
+
+    /* A simple heuristic ordering */
+    T = lex_sort(sf_save(T));
+
+    /* Push a full set on the stack to get things started */
+    n = 1;
+    stack[0].sf = sf_new(1, T->sf_size);
+    stack[0].level = lev;
+    set_fill(GETSET(stack[0].sf, stack[0].sf->count++), T->sf_size);
+
+    nlast = GETSET(T, T->count - 1);
+    foreach_set(T, last, p) {
+
+    /* "unstack" the set into a family */
+    temp = sf_new(set_ord(p), T->sf_size);
+    for(i = 0; i < T->sf_size; i++)
+        if (is_in_set(p, i)) {
+        p1 = set_fill(GETSET(temp, temp->count++), T->sf_size);
+        set_remove(p1, i);
+        }
+    stack[n].sf = temp;
+    stack[n++].level = lev;
+
+    /* Pop the stack and perform (leveled) intersections */
+    while (n > 1 && (stack[n-1].level==stack[n-2].level || p == nlast)) {
+        temp = unate_intersect(stack[n-1].sf, stack[n-2].sf, FALSE);
+        lvl = MIN(stack[n-1].level, stack[n-2].level) - 1;
+        if (debug & MINCOV && lvl < 10) {
+        printf("# EXACT_MINCOV[%d]: %4d = %4d x %4d, time = %s\n",
+            lvl, temp->count, stack[n-1].sf->count,
+            stack[n-2].sf->count, print_time(ptime() - start));
+        (void) fflush(stdout);
+        }
+        sf_free(stack[n-2].sf);
+        sf_free(stack[n-1].sf);
+        stack[n-2].sf = temp;
+        stack[n-2].level = lvl;
+        n--;
+    }
+    }
+
+    temp = stack[0].sf;
+    p1 = set_fill(set_new(T->sf_size), T->sf_size);
+    foreach_set(temp, last, p)
+    INLINEset_diff(p, p1, p);
+    set_free(p1);
+    if (debug & MINCOV1) {
+    printf("MINCOV: family of all minimal coverings is\n");
+    sf_print(temp);
+    }
+    sf_free(T);         /* this is the copy of T we made ... */
+    return temp;
+}
+
+/*
+ *  unate_intersect -- intersect two unate covers
+ *
+ *  If largest_only is TRUE, then only the largest cube(s) are returned
+ */
+
+#define MAGIC 500               /* save 500 cubes before containment */
+
+pset_family unate_intersect(A, B, largest_only)
+pset_family A, B;
+bool largest_only;
+{
+    register pset pi, pj, lasti, lastj, pt;
+    pset_family T, Tsave;
+    bool save;
+    int maxord, ord;
+
+    /* How large should each temporary result cover be ? */
+    T = sf_new(MAGIC, A->sf_size);
+    Tsave = NULL;
+    maxord = 0;
+    pt = T->data;
+
+    /* Form pairwise intersection of each set of A with each cube of B */
+    foreach_set(A, lasti, pi) {
+
+    foreach_set(B, lastj, pj) {
+
+        save = set_andp(pt, pi, pj);
+
+        /* Check if we want the largest only */
+        if (save && largest_only) {
+        if ((ord = set_ord(pt)) > maxord) {
+            /* discard Tsave and T */
+            if (Tsave != NULL) {
+            sf_free(Tsave);
+            Tsave = NULL;
+            }
+            pt = T->data;
+            T->count = 0;
+            /* Re-create pt (which was just thrown away) */
+            (void) set_and(pt, pi, pj);
+            maxord = ord;
+        } else if (ord < maxord) {
+            save = FALSE;
+        }
+        }
+
+        if (save) {
+        if (++T->count >= T->capacity) {
+            T = sf_contain(T);
+            Tsave = (Tsave == NULL) ? T : sf_union(Tsave, T);
+            T = sf_new(MAGIC, A->sf_size);
+            pt = T->data;
+        } else {
+            pt += T->wsize;
+        }
+        }
+    }
+    }
+
+
+    /* Contain the final result and merge it into Tsave */
+    T = sf_contain(T);
+    Tsave = (Tsave == NULL) ? T : sf_union(Tsave, T);
+
+    return Tsave;
+}
+
+/*
+ *  abs_covered -- after selecting a new column for the selected set,
+ *  create a new matrix which is only those rows which are still uncovered
+ */
+static pset_family
+abs_covered(A, pick)
+pset_family A;
+register int pick;
+{
+    register pset last, p, pdest;
+    register pset_family Aprime;
+
+    Aprime = sf_new(A->count, A->sf_size);
+    pdest = Aprime->data;
+    foreach_set(A, last, p)
+    if (! is_in_set(p, pick)) {
+        INLINEset_copy(pdest, p);
+        Aprime->count++;
+        pdest += Aprime->wsize;
+    }
+    return Aprime;
+}
+
+
+/*
+ *  abs_covered_many -- after selecting many columns for ther selected set,
+ *  create a new matrix which is only those rows which are still uncovered
+ */
+static pset_family
+abs_covered_many(A, pick_set)
+pset_family A;
+register pset pick_set;
+{
+    register pset last, p, pdest;
+    register pset_family Aprime;
+
+    Aprime = sf_new(A->count, A->sf_size);
+    pdest = Aprime->data;
+    foreach_set(A, last, p)
+    if (setp_disjoint(p, pick_set)) {
+        INLINEset_copy(pdest, p);
+        Aprime->count++;
+        pdest += Aprime->wsize;
+    }
+    return Aprime;
+}
+
+
+/*
+ *  abs_select_restricted -- select the column of maximum column count which
+ *  also belongs to the set "restrict"; weight each column of a set as
+ *  1 / (set_ord(p) - 1).
+ */
+static int
+abs_select_restricted(A, restrict)
+pset_family A;
+pset restrict;
+{
+    register int i, best_var, best_count, *count;
+
+    /* Sum the elements in these columns */
+    count = sf_count_restricted(A, restrict);
+
+    /* Find which variable has maximum weight */
+    best_var = -1;
+    best_count = 0;
+    for(i = 0; i < A->sf_size; i++) {
+    if (count[i] > best_count) {
+        best_var = i;
+        best_count = count[i];
+    }
+    }
+    FREE(count);
+
+    if (best_var == -1)
+    fatal("abs_select_restricted: should not have best_var == -1");
+
+    return best_var;
+}