Version abc70930

1 files changed, 0 insertions, 258 deletions

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