src/misc/espresso/reduce.c

Go to the documentation of this file.

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

---