/*
* 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"
ABC_NAMESPACE_IMPL_START
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;
}
ABC_NAMESPACE_IMPL_END