From e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Sep 2007 08:01:00 -0700 Subject: Version abc70930 --- src/misc/espresso/reduce.c | 258 --------------------------------------------- 1 file changed, 258 deletions(-) delete mode 100644 src/misc/espresso/reduce.c (limited to 'src/misc/espresso/reduce.c') diff --git a/src/misc/espresso/reduce.c b/src/misc/espresso/reduce.c deleted file mode 100644 index 00e4507f..00000000 --- a/src/misc/espresso/reduce.c +++ /dev/null @@ -1,258 +0,0 @@ -/* - * Revision Control Information - * - * $Source$ - * $Author$ - * $Revision$ - * $Date$ - * - */ -/* - module: reduce.c - purpose: Perform the Espresso-II reduction step - - Reduction is a technique used to explore larger regions of the - optimization space. We replace each cube of F with a smaller - cube while still maintaining a cover of the same logic function. -*/ - -#include "espresso.h" - -static bool toggle = TRUE; - - -/* - reduce -- replace each cube in F with its reduction - - The reduction of a cube is the smallest cube contained in the cube - which can replace the cube in the original cover without changing - the cover. This is equivalent to the super cube of all of the - essential points in the cube. This can be computed directly. - - The problem is that the order in which the cubes are reduced can - greatly affect the final result. We alternate between two ordering - strategies: - - (1) Order the cubes in ascending order of distance from the - largest cube breaking ties by ordering cubes of equal distance - in descending order of size (sort_reduce) - - (2) Order the cubes in descending order of the inner-product of - the cube and the column sums (mini_sort) - - The real workhorse of this section is the routine SCCC which is - used to find the Smallest Cube Containing the Complement of a cover. - Reduction as proposed by Espresso-II takes a cube and computes its - maximal reduction as the intersection between the cube and the - smallest cube containing the complement of (F u D - {c}) cofactored - against c. - - As usual, the unate-recursive paradigm is used to compute SCCC. - The SCCC of a unate cover is trivial to compute, and thus we perform - Shannon Cofactor expansion attempting to drive the cover to be unate - as fast as possible. -*/ - -pcover reduce(F, D) -INOUT pcover F; -IN pcover D; -{ - register pcube last, p, cunder, *FD; - - /* Order the cubes */ - if (use_random_order) - F = random_order(F); - else { - F = toggle ? sort_reduce(F) : mini_sort(F, descend); - toggle = ! toggle; - } - - /* Try to reduce each cube */ - FD = cube2list(F, D); - foreach_set(F, last, p) { - cunder = reduce_cube(FD, p); /* reduce the cube */ - if (setp_equal(cunder, p)) { /* see if it actually did */ - SET(p, ACTIVE); /* cube remains active */ - SET(p, PRIME); /* cube remains prime ? */ - } else { - if (debug & REDUCE) { - printf("REDUCE: %s to %s %s\n", - pc1(p), pc2(cunder), print_time(ptime())); - } - set_copy(p, cunder); /* save reduced version */ - RESET(p, PRIME); /* cube is no longer prime */ - if (setp_empty(cunder)) - RESET(p, ACTIVE); /* if null, kill the cube */ - else - SET(p, ACTIVE); /* cube is active */ - } - free_cube(cunder); - } - free_cubelist(FD); - - /* Delete any cubes of F which reduced to the empty cube */ - return sf_inactive(F); -} - -/* reduce_cube -- find the maximal reduction of a cube */ -pcube reduce_cube(FD, p) -IN pcube *FD, p; -{ - pcube cunder; - - cunder = sccc(cofactor(FD, p)); - return set_and(cunder, cunder, p); -} - - -/* sccc -- find Smallest Cube Containing the Complement of a cover */ -pcube sccc(T) -INOUT pcube *T; /* T will be disposed of */ -{ - pcube r; - register pcube cl, cr; - register int best; - static int sccc_level = 0; - - if (debug & REDUCE1) { - debug_print(T, "SCCC", sccc_level++); - } - - if (sccc_special_cases(T, &r) == MAYBE) { - cl = new_cube(); - cr = new_cube(); - best = binate_split_select(T, cl, cr, REDUCE1); - r = sccc_merge(sccc(scofactor(T, cl, best)), - sccc(scofactor(T, cr, best)), cl, cr); - free_cubelist(T); - } - - if (debug & REDUCE1) - printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r)); - return r; -} - - -pcube sccc_merge(left, right, cl, cr) -INOUT register pcube left, right; /* will be disposed of ... */ -INOUT register pcube cl, cr; /* will be disposed of ... */ -{ - INLINEset_and(left, left, cl); - INLINEset_and(right, right, cr); - INLINEset_or(left, left, right); - free_cube(right); - free_cube(cl); - free_cube(cr); - return left; -} - - -/* - sccc_cube -- find the smallest cube containing the complement of a cube - - By DeMorgan's law and the fact that the smallest cube containing a - cover is the "or" of the positional cubes, it is simple to see that - the SCCC is the universe if the cube has more than two active - variables. If there is only a single active variable, then the - SCCC is merely the bitwise complement of the cube in that - variable. A last special case is no active variables, in which - case the SCCC is empty. - - This is "anded" with the incoming cube result. -*/ -pcube sccc_cube(result, p) -register pcube result, p; -{ - register pcube temp=cube.temp[0], mask; - int var; - - if ((var = cactive(p)) >= 0) { - mask = cube.var_mask[var]; - INLINEset_xor(temp, p, mask); - INLINEset_and(result, result, temp); - } - return result; -} - -/* - * sccc_special_cases -- check the special cases for sccc - */ - -bool sccc_special_cases(T, result) -INOUT pcube *T; /* will be disposed if answer is determined */ -OUT pcube *result; /* returned only if answer determined */ -{ - register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0]; - pcube *A, *B; - - /* empty cover => complement is universe => SCCC is universe */ - if (T[2] == NULL) { - *result = set_save(cube.fullset); - free_cubelist(T); - return TRUE; - } - - /* row of 1's => complement is empty => SCCC is empty */ - for(T1 = T+2; (p = *T1++) != NULL; ) { - if (full_row(p, cof)) { - *result = new_cube(); - free_cubelist(T); - return TRUE; - } - } - - /* Collect column counts, determine unate variables, etc. */ - massive_count(T); - - /* If cover is unate (or single cube), apply simple rules to find SCCCU */ - if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) { - *result = set_save(cube.fullset); - for(T1 = T+2; (p = *T1++) != NULL; ) { - (void) sccc_cube(*result, set_or(temp, p, cof)); - } - free_cubelist(T); - return TRUE; - } - - /* Check for column of 0's (which can be easily factored( */ - ceil = set_save(cof); - for(T1 = T+2; (p = *T1++) != NULL; ) { - INLINEset_or(ceil, ceil, p); - } - if (! setp_equal(ceil, cube.fullset)) { - *result = sccc_cube(set_save(cube.fullset), ceil); - if (setp_equal(*result, cube.fullset)) { - free_cube(ceil); - } else { - *result = sccc_merge(sccc(cofactor(T,ceil)), - set_save(cube.fullset), ceil, *result); - } - free_cubelist(T); - return TRUE; - } - free_cube(ceil); - - /* Single active column at this point => tautology => SCCC is empty */ - if (cdata.vars_active == 1) { - *result = new_cube(); - free_cubelist(T); - return TRUE; - } - - /* Check for components */ - if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) { - if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) { - return MAYBE; - } else { - free_cubelist(T); - *result = sccc(A); - ceil = sccc(B); - (void) set_and(*result, *result, ceil); - set_free(ceil); - return TRUE; - } - } - - /* Not much we can do about it */ - return MAYBE; -} -- cgit v1.2.3