diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2007-10-01 08:01:00 -0700 |
commit | 4812c90424dfc40d26725244723887a2d16ddfd9 (patch) | |
tree | b32ace96e7e2d84d586e09ba605463b6f49c3271 /src/misc/espresso/unate.c | |
parent | e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 (diff) | |
download | abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.gz abc-4812c90424dfc40d26725244723887a2d16ddfd9.tar.bz2 abc-4812c90424dfc40d26725244723887a2d16ddfd9.zip |
Version abc71001
Diffstat (limited to 'src/misc/espresso/unate.c')
-rw-r--r-- | src/misc/espresso/unate.c | 441 |
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; +} |