src/misc/espresso/essen.c

Go to the documentation of this file.

/*
 * Revision Control Information
 *
 * $Source$
 * $Author$
 * $Revision$
 * $Date$
 *
 */
/*
    module: essen.c
    purpose: Find essential primes in a multiple-valued function
*/

#include "espresso.h"

/*
    essential -- return a cover consisting of the cubes of F which are
    essential prime implicants (with respect to F u D); Further, remove
    these cubes from the ON-set F, and add them to the OFF-set D.

    Sometimes EXPAND can determine that a cube is not an essential prime.
    If so, it will set the "NONESSEN" flag in the cube.

    We count on IRREDUNDANT to have set the flag RELESSEN to indicate
    that a prime was relatively essential (i.e., covers some minterm
    not contained in any other prime in the current cover), or to have
    reset the flag to indicate that a prime was relatively redundant
    (i.e., all minterms covered by other primes in the current cover).
    Of course, after executing irredundant, all of the primes in the
    cover are relatively essential, but we can mark the primes which
    were redundant at the start of irredundant and avoid an extra check
    on these primes for essentiality.
*/

pcover essential(Fp, Dp)
IN pcover *Fp, *Dp;
{
    register pcube last, p;
    pcover E, F = *Fp, D = *Dp;

    /* set all cubes in F active */
    (void) sf_active(F);

    /* Might as well start out with some cubes in E */
    E = new_cover(10);

    foreach_set(F, last, p) {
        /* don't test a prime which EXPAND says is nonessential */
        if (! TESTP(p, NONESSEN)) {
            /* only test a prime which was relatively essential */
            if (TESTP(p, RELESSEN)) {
                /* Check essentiality */
                if (essen_cube(F, D, p)) {
                    if (debug & ESSEN)
                        printf("ESSENTIAL: %s\n", pc1(p));
                    E = sf_addset(E, p);
                    RESET(p, ACTIVE);
                    F->active_count--;
                }
            }
        }
    }

    *Fp = sf_inactive(F);               /* delete the inactive cubes from F */
    *Dp = sf_join(D, E);                /* add the essentials to D */
    sf_free(D);
    return E;
}

/*
    essen_cube -- check if a single cube is essential or not

    The prime c is essential iff

        consensus((F u D) # c, c) u D

    does not contain c.
*/
bool essen_cube(F, D, c)
IN pcover F, D;
IN pcube c;
{
    pcover H, FD;
    pcube *H1;
    bool essen;

    /* Append F and D together, and take the sharp-consensus with c */
    FD = sf_join(F, D);
    H = cb_consensus(FD, c);
    free_cover(FD);

    /* Add the don't care set, and see if this covers c */
    H1 = cube2list(H, D);
    essen = ! cube_is_covered(H1, c);
    free_cubelist(H1);

    free_cover(H);
    return essen;
}


/*
 *  cb_consensus -- compute consensus(T # c, c)
 */
pcover cb_consensus(T, c)
register pcover T;
register pcube c;
{
    register pcube temp, last, p;
    register pcover R;

    R = new_cover(T->count*2);
    temp = new_cube();
    foreach_set(T, last, p) {
        if (p != c) {
            switch (cdist01(p, c)) {
                case 0:
                    /* distance-0 needs special care */
                    R = cb_consensus_dist0(R, p, c);
                    break;

                case 1:
                    /* distance-1 is easy because no sharping required */
                    consensus(temp, p, c);
                    R = sf_addset(R, temp);
                    break;
            }
        }
    }
    set_free(temp);
    return R;
}


/*
 *  form the sharp-consensus for p and c when they intersect
 *  What we are forming is consensus(p # c, c).
 */
pcover cb_consensus_dist0(R, p, c)
pcover R;
register pcube p, c;
{
    int var;
    bool got_one;
    register pcube temp, mask;
    register pcube p_diff_c=cube.temp[0], p_and_c=cube.temp[1];

    /* If c contains p, then this gives us no information for essential test */
    if (setp_implies(p, c)) {
        return R;
    }

    /* For the multiple-valued variables */
    temp = new_cube();
    got_one = FALSE;
    INLINEset_diff(p_diff_c, p, c);
    INLINEset_and(p_and_c, p, c);

    for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
        /* Check if c(var) is contained in p(var) -- if so, no news */
        mask = cube.var_mask[var];
        if (! setp_disjoint(p_diff_c, mask)) {
            INLINEset_merge(temp, c, p_and_c, mask);
            R = sf_addset(R, temp);
            got_one = TRUE;
        }
    }

    /* if no cube so far, add one for the intersection */
    if (! got_one && cube.num_binary_vars > 0) {
        /* Add a single cube for the intersection of p and c */
        INLINEset_and(temp, p, c);
        R = sf_addset(R, temp);
    }

    set_free(temp);
    return R;
}

---