src/misc/espresso/expand.c

Go to the documentation of this file.

/*
 * Revision Control Information
 *
 * $Source$
 * $Author$
 * $Revision$
 * $Date$
 *
 */
/*
    module: expand.c
    purpose: Perform the Espresso-II Expansion Step

    The idea is to take each nonprime cube of the on-set and expand it
    into a prime implicant such that we can cover as many other cubes
    of the on-set.  If no cube of the on-set can be covered, then we
    expand each cube into a large prime implicant by transforming the
    problem into a minimum covering problem which is solved by the
    heuristics of minimum_cover.

    These routines revolve around having a representation of the
    OFF-set.  (In contrast to the Espresso-II manuscript, we do NOT
    require an "unwrapped" version of the OFF-set).

    Some conventions on variable names:

        SUPER_CUBE is the supercube of all cubes which can be covered
        by an expansion of the cube being expanded

        OVEREXPANDED_CUBE is the cube which would result from expanding
        all parts which can expand individually of the cube being expanded

        RAISE is the current expansion of the current cube

        FREESET is the set of parts which haven't been raised or lowered yet.

        INIT_LOWER is a set of parts to be removed from the free parts before
        starting the expansion
*/

#include "espresso.h"

/*
    expand -- expand each nonprime cube of F into a prime implicant

    If nonsparse is true, only the non-sparse variables will be expanded;
    this is done by forcing all of the sparse variables out of the free set.
*/

pcover expand(F, R, nonsparse)
INOUT pcover F;
IN pcover R;
IN bool nonsparse;              /* expand non-sparse variables only */
{
    register pcube last, p;
    pcube RAISE, FREESET, INIT_LOWER, SUPER_CUBE, OVEREXPANDED_CUBE;
    int var, num_covered;
    bool change;

    /* Order the cubes according to "chewing-away from the edges" of mini */
    if (use_random_order)
        F = random_order(F);
    else
        F = mini_sort(F, ascend);

    /* Allocate memory for variables needed by expand1() */
    RAISE = new_cube();
    FREESET = new_cube();
    INIT_LOWER = new_cube();
    SUPER_CUBE = new_cube();
    OVEREXPANDED_CUBE = new_cube();

    /* Setup the initial lowering set (differs only for nonsparse) */
    if (nonsparse)
        for(var = 0; var < cube.num_vars; var++)
            if (cube.sparse[var])
                (void) set_or(INIT_LOWER, INIT_LOWER, cube.var_mask[var]);

    /* Mark all cubes as not covered, and maybe essential */
    foreach_set(F, last, p) {
        RESET(p, COVERED);
        RESET(p, NONESSEN);
    }

    /* Try to expand each nonprime and noncovered cube */
    foreach_set(F, last, p) {
        /* do not expand if PRIME or if covered by previous expansion */
        if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) {

            /* expand the cube p, result is RAISE */
            expand1(R, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
                INIT_LOWER, &num_covered, p);
            if (debug & EXPAND)
                printf("EXPAND: %s (covered %d)\n", pc1(p), num_covered);
            (void) set_copy(p, RAISE);
            SET(p, PRIME);
            RESET(p, COVERED);          /* not really necessary */

            /* See if we generated an inessential prime */
            if (num_covered == 0 && ! setp_equal(p, OVEREXPANDED_CUBE)) {
                SET(p, NONESSEN);
            }
        }
    }

    /* Delete any cubes of F which became covered during the expansion */
    F->active_count = 0;
    change = FALSE;
    foreach_set(F, last, p) {
        if (TESTP(p, COVERED)) {
            RESET(p, ACTIVE);
            change = TRUE;
        } else {
            SET(p, ACTIVE);
            F->active_count++;
        }
    }
    if (change)
        F = sf_inactive(F);

    free_cube(RAISE);
    free_cube(FREESET);
    free_cube(INIT_LOWER);
    free_cube(SUPER_CUBE);
    free_cube(OVEREXPANDED_CUBE);
    return F;
}

/*
    expand1 -- Expand a single cube against the OFF-set
*/
void expand1(BB, CC, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
                INIT_LOWER, num_covered, c)
pcover BB;                      /* Blocking matrix (OFF-set) */
pcover CC;                      /* Covering matrix (ON-set) */
pcube RAISE;                    /* The current parts which have been raised */
pcube FREESET;                  /* The current parts which are free */
pcube OVEREXPANDED_CUBE;        /* Overexpanded cube of c */
pcube SUPER_CUBE;               /* Supercube of all cubes of CC we cover */
pcube INIT_LOWER;               /* Parts to initially remove from FREESET */
int *num_covered;               /* Number of cubes of CC which are covered */
pcube c;                        /* The cube to be expanded */
{
    int bestindex;

    if (debug & EXPAND1)
        printf("\nEXPAND1:    \t%s\n", pc1(c));

    /* initialize BB and CC */
    SET(c, PRIME);              /* don't try to cover ourself */
    setup_BB_CC(BB, CC);

    /* initialize count of # cubes covered, and the supercube of them */
    *num_covered = 0;
    (void) set_copy(SUPER_CUBE, c);

    /* Initialize the lowering, raising and unassigned sets */
    (void) set_copy(RAISE, c);
    (void) set_diff(FREESET, cube.fullset, RAISE);

    /* If some parts are forced into lowering set, remove them */
    if (! setp_empty(INIT_LOWER)) {
        (void) set_diff(FREESET, FREESET, INIT_LOWER);
        elim_lowering(BB, CC, RAISE, FREESET);
    }

    /* Determine what can be raised, and return the over-expanded cube */
    essen_parts(BB, CC, RAISE, FREESET);
    (void) set_or(OVEREXPANDED_CUBE, RAISE, FREESET);

    /* While there are still cubes which can be covered, cover them ! */
    if (CC->active_count > 0) {
        select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered);
    }

    /* While there are still cubes covered by the overexpanded cube ... */
    while (CC->active_count > 0) {
        bestindex = most_frequent(CC, FREESET);
        set_insert(RAISE, bestindex);
        set_remove(FREESET, bestindex);
        essen_parts(BB, CC, RAISE, FREESET);
    }

    /* Finally, when all else fails, choose the largest possible prime */
    /* We will loop only if we decide unravelling OFF-set is too expensive */
    while (BB->active_count > 0) {
        mincov(BB, RAISE, FREESET);
    }

    /* Raise any remaining free coordinates */
    (void) set_or(RAISE, RAISE, FREESET);
}

/*
    essen_parts -- determine which parts are forced into the lowering
    set to insure that the cube be orthognal to the OFF-set.

    If any cube of the OFF-set is distance 1 from the raising cube,
    then we must lower all parts of the conflicting variable.  (If the
    cube is distance 0, we detect this error here.)

    If there are essentially lowered parts, we can remove from consideration
    any cubes of the OFF-set which are more than distance 1 from the
    overexpanded cube of RAISE.
*/

void essen_parts(BB, CC, RAISE, FREESET)
pcover BB, CC;
pcube RAISE, FREESET;
{
    register pcube p, r = RAISE;
    pcube lastp, xlower = cube.temp[0];
    int dist;

    (void) set_copy(xlower, cube.emptyset);

    foreach_active_set(BB, lastp, p) {
#ifdef NO_INLINE
        if ((dist = cdist01(p, r)) > 1) goto exit_if;
#else
 {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1)
{x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto
exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||(
dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube
mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[
var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[
w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}}
#endif
        if (dist == 0) {
            fatal("ON-set and OFF-set are not orthogonal");
        } else {
            (void) force_lower(xlower, p, r);
            BB->active_count--;
            RESET(p, ACTIVE);
        }
exit_if: ;
    }

    if (! setp_empty(xlower)) {
        (void) set_diff(FREESET, FREESET, xlower);/* remove from free set */
        elim_lowering(BB, CC, RAISE, FREESET);
    }

    if (debug & EXPAND1)
        printf("ESSEN_PARTS:\tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
}

/*
    essen_raising -- determine which parts may always be added to
    the raising set without restricting further expansions

    General rule: if some part is not blocked by any cube of BB, then
    this part can always be raised.
*/

void essen_raising(BB, RAISE, FREESET)
register pcover BB;
pcube RAISE, FREESET;
{
    register pcube last, p, xraise = cube.temp[0];

    /* Form union of all cubes of BB, and then take complement wrt FREESET */
    (void) set_copy(xraise, cube.emptyset);
    foreach_active_set(BB, last, p)
        INLINEset_or(xraise, xraise, p);
    (void) set_diff(xraise, FREESET, xraise);

    (void) set_or(RAISE, RAISE, xraise);         /* add to raising set */
    (void) set_diff(FREESET, FREESET, xraise);       /* remove from free set */

    if (debug & EXPAND1)
        printf("ESSEN_RAISING:\tRAISE=%s FREESET=%s\n",
            pc1(RAISE), pc2(FREESET));
}

/*
    elim_lowering -- after removing parts from FREESET, we can reduce the
    size of both BB and CC.

    We mark as inactive any cube of BB which does not intersect the
    overexpanded cube (i.e., RAISE + FREESET).  Likewise, we remove
    from CC any cube which is not covered by the overexpanded cube.
*/

void elim_lowering(BB, CC, RAISE, FREESET)
pcover BB, CC;
pcube RAISE, FREESET;
{
    register pcube p, r = set_or(cube.temp[0], RAISE, FREESET);
    pcube last;

    /*
     *  Remove sets of BB which are orthogonal to future expansions
     */
    foreach_active_set(BB, last, p) {
#ifdef NO_INLINE
        if (! cdist0(p, r))
#else
 {register int w,lastw;register unsigned int x;if((lastw=cube.inword)!=-1){x=p[
lastw]&r[lastw];if(~(x|x>>1)&cube.inmask)goto false;for(w=1;w<lastw;w++){x=p[w]
&r[w];if(~(x|x>>1)&DISJOINT)goto false;}}}{register int w,var,lastw;register
pcube mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.
var_mask[var];lastw=cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++)
if(p[w]&r[w]&mask[w])goto nextvar;goto false;nextvar:;}}continue;false:
#endif
            BB->active_count--, RESET(p, ACTIVE);
    }


    /*
     *  Remove sets of CC which cannot be covered by future expansions
     */
    if (CC != (pcover) NULL) {
        foreach_active_set(CC, last, p) {
#ifdef NO_INLINE
            if (! setp_implies(p, r))
#else
            INLINEsetp_implies(p, r, /* when false => */ goto false1);
            /* when true => go to end of loop */ continue;
            false1:
#endif
                CC->active_count--, RESET(p, ACTIVE);
        }
    }
}

/*
    most_frequent -- When all else fails, select a reasonable part to raise
    The active cubes of CC are the cubes which are covered by the
    overexpanded cube of the original cube (however, we know that none
    of them can actually be covered by a feasible expansion of the
    original cube).  We resort to the MINI strategy of selecting to
    raise the part which will cover the same part in the most cubes of CC.
*/
int most_frequent(CC, FREESET)
pcover CC;
pcube FREESET;
{
    register int i, best_part, best_count, *count;
    register pset p, last;

    /* Count occurences of each variable */
    count = ALLOC(int, cube.size);
    for(i = 0; i < cube.size; i++)
        count[i] = 0;
    if (CC != (pcover) NULL)
        foreach_active_set(CC, last, p)
            set_adjcnt(p, count, 1);

    /* Now find which free part occurs most often */
    best_count = best_part = -1;
    for(i = 0; i < cube.size; i++)
        if (is_in_set(FREESET,i) && count[i] > best_count) {
            best_part = i;
            best_count = count[i];
        }
    FREE(count);

    if (debug & EXPAND1)
        printf("MOST_FREQUENT:\tbest=%d FREESET=%s\n", best_part, pc2(FREESET));
    return best_part;
}

/*
    setup_BB_CC -- set up the blocking and covering set families;

    Note that the blocking family is merely the set of cubes of R, and
    that CC is the set of cubes of F which might possibly be covered
    (i.e., nonprime cubes, and cubes not already covered)
*/

void setup_BB_CC(BB, CC)
register pcover BB, CC;
{
    register pcube p, last;

    /* Create the block and cover set families */
    BB->active_count = BB->count;
    foreach_set(BB, last, p)
        SET(p, ACTIVE);

    if (CC != (pcover) NULL) {
        CC->active_count = CC->count;
        foreach_set(CC, last, p)
            if (TESTP(p, COVERED) || TESTP(p, PRIME))
                CC->active_count--, RESET(p, ACTIVE);
            else
                SET(p, ACTIVE);
    }
}

/*
    select_feasible -- Determine if there are cubes which can be covered,
    and if so, raise those parts necessary to cover as many as possible.

    We really don't check to maximize the number that can be covered;
    instead, we check, for each fcc, how many other fcc remain fcc
    after expanding to cover the fcc.  (Essentially one-level lookahead).
*/

void select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered)
pcover BB, CC;
pcube RAISE, FREESET, SUPER_CUBE;
int *num_covered;
{
    register pcube p, last, bestfeas, *feas;
    register int i, j;
    pcube *feas_new_lower;
    int bestcount, bestsize, count, size, numfeas, lastfeas;
    pcover new_lower;

    /*  Start out with all cubes covered by the over-expanded cube as
     *  the "possibly" feasibly-covered cubes (pfcc)
     */
    feas = ALLOC(pcube, CC->active_count);
    numfeas = 0;
    foreach_active_set(CC, last, p)
        feas[numfeas++] = p;

    /* Setup extra cubes to record parts forced low after a covering */
    feas_new_lower = ALLOC(pcube, CC->active_count);
    new_lower = new_cover(numfeas);
    for(i = 0; i < numfeas; i++)
        feas_new_lower[i] = GETSET(new_lower, i);


loop:
    /* Find the essentially raised parts -- this might cover some cubes
       for us, without having to find out if they are fcc or not
    */
    essen_raising(BB, RAISE, FREESET);

    /* Now check all "possibly" feasibly covered cubes to check feasibility */
    lastfeas = numfeas;
    numfeas = 0;
    for(i = 0; i < lastfeas; i++) {
        p = feas[i];

        /* Check active because essen_parts might have removed it */
        if (TESTP(p, ACTIVE)) {

            /*  See if the cube is already covered by RAISE --
             *  this can happen because of essen_raising() or because of
             *  the previous "loop"
             */
            if (setp_implies(p, RAISE)) {
                (*num_covered) += 1;
                (void) set_or(SUPER_CUBE, SUPER_CUBE, p);
                CC->active_count--;
                RESET(p, ACTIVE);
                SET(p, COVERED);
            /* otherwise, test if it is feasibly covered */
            } else if (feasibly_covered(BB,p,RAISE,feas_new_lower[numfeas])) {
                feas[numfeas] = p;                      /* save the fcc */
                numfeas++;
            }
        }
    }
    if (debug & EXPAND1)
        printf("SELECT_FEASIBLE: started with %d pfcc, ended with %d fcc\n",
            lastfeas, numfeas);

    /* Exit here if there are no feasibly covered cubes */
    if (numfeas == 0) {
        FREE(feas);
        FREE(feas_new_lower);
        free_cover(new_lower);
        return;
    }

    /* Now find which is the best feasibly covered cube */
    bestcount = 0;
    bestsize = 9999;
    for(i = 0; i < numfeas; i++) {
        size = set_dist(feas[i], FREESET);      /* # of newly raised parts */
        count = 0;      /* # of other cubes which remain fcc after raising */

#define NEW
#ifdef NEW
        for(j = 0; j < numfeas; j++)
            if (setp_disjoint(feas_new_lower[i], feas[j]))
                count++;
#else
        for(j = 0; j < numfeas; j++)
            if (setp_implies(feas[j], feas[i]))
                count++;
#endif
        if (count > bestcount) {
            bestcount = count;
            bestfeas = feas[i];
            bestsize = size;
        } else if (count == bestcount && size < bestsize) {
            bestfeas = feas[i];
            bestsize = size;
        }
    }

    /* Add the necessary parts to the raising set */
    (void) set_or(RAISE, RAISE, bestfeas);
    (void) set_diff(FREESET, FREESET, RAISE);
    if (debug & EXPAND1)
        printf("FEASIBLE:  \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
    essen_parts(BB, CC, RAISE, FREESET);
    goto loop;
/* NOTREACHED */
}

/*
    feasibly_covered -- determine if the cube c is feasibly covered
    (i.e., if it is possible to raise all of the necessary variables
    while still insuring orthogonality with R).  Also, if c is feasibly
    covered, then compute the new set of parts which are forced into
    the lowering set.
*/

bool feasibly_covered(BB, c, RAISE, new_lower)
pcover BB;
pcube c, RAISE, new_lower;
{
    register pcube p, r = set_or(cube.temp[0], RAISE, c);
    int dist;
    pcube lastp;

    set_copy(new_lower, cube.emptyset);
    foreach_active_set(BB, lastp, p) {
#ifdef NO_INLINE
        if ((dist = cdist01(p, r)) > 1) goto exit_if;
#else
 {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1)
{x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto
exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||(
dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube
mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[
var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[
w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}}
#endif
        if (dist == 0)
            return FALSE;
        else
            (void) force_lower(new_lower, p, r);
    exit_if: ;
    }
    return TRUE;
}

/*
    mincov -- transform the problem of expanding a cube to a maximally-
    large prime implicant into the problem of selecting a minimum
    cardinality cover over a family of sets.

    When we get to this point, we must unravel the remaining off-set.
    This may be painful.
*/

void mincov(BB, RAISE, FREESET)
pcover BB;
pcube RAISE, FREESET;
{
    int expansion, nset, var, dist;
    pset_family B;
    register pcube xraise=cube.temp[0], xlower, p, last, plower;

#ifdef RANDOM_MINCOV
#if defined(_POSIX_SOURCE) || defined(__SVR4)
    dist = rand() % set_ord(FREESET);
#else
    dist = random() % set_ord(FREESET);
#endif
    for(var = 0; var < cube.size && dist >= 0; var++) {
        if (is_in_set(FREESET, var)) {
            dist--;
        }
    }

    set_insert(RAISE, var);
    set_remove(FREESET, var);
    (void) essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET);
#else

    /* Create B which are those cubes which we must avoid intersecting */
    B = new_cover(BB->active_count);
    foreach_active_set(BB, last, p) {
        plower = set_copy(GETSET(B, B->count++), cube.emptyset);
        (void) force_lower(plower, p, RAISE);
    }

    /* Determine how many sets it will blow up into after the unravel */
    nset = 0;
    foreach_set(B, last, p) {
        expansion = 1;
        for(var = cube.num_binary_vars; var < cube.num_vars; var++) {
            if ((dist=set_dist(p, cube.var_mask[var])) > 1) {
                expansion *= dist;
                if (expansion > 500) goto heuristic_mincov;
            }
        }
        nset += expansion;
        if (nset > 500) goto heuristic_mincov;
    }

    B = unravel(B, cube.num_binary_vars);
    xlower = do_sm_minimum_cover(B);

    /* Add any remaining free parts to the raising set */
    (void) set_or(RAISE, RAISE, set_diff(xraise, FREESET, xlower));
    (void) set_copy(FREESET, cube.emptyset);    /* free set is empty */
    BB->active_count = 0;                       /* BB satisfied */
    if (debug & EXPAND1) {
        printf("MINCOV:    \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET));
    }
    sf_free(B);
    set_free(xlower);
    return;

heuristic_mincov:
    sf_free(B);
    /* most_frequent will pick first free part */
    set_insert(RAISE, most_frequent(/*CC*/ (pcover) NULL, FREESET));
    (void) set_diff(FREESET, FREESET, RAISE);
    essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET);
    return;
#endif
}

/*
    find_all_primes -- find all of the primes which cover the
    currently reduced BB
*/
pcover find_all_primes(BB, RAISE, FREESET)
pcover BB;
register pcube RAISE, FREESET;
{
    register pset last, p, plower;
    pset_family B, B1;

    if (BB->active_count == 0) {
        B1 = new_cover(1);
        p = GETSET(B1, B1->count++);
        (void) set_copy(p, RAISE);
        SET(p, PRIME);
    } else {
        B = new_cover(BB->active_count);
        foreach_active_set(BB, last, p) {
            plower = set_copy(GETSET(B, B->count++), cube.emptyset);
            (void) force_lower(plower, p, RAISE);
        }
        B = sf_rev_contain(unravel(B, cube.num_binary_vars));
        B1 = exact_minimum_cover(B);
        foreach_set(B1, last, p) {
            INLINEset_diff(p, FREESET, p);
            INLINEset_or(p, p, RAISE);
            SET(p, PRIME);
        }
        free_cover(B);
    }
    return B1;
}

/*
    all_primes -- foreach cube in F, generate all of the primes
    which cover the cube.
*/

pcover all_primes(F, R)
pcover F, R;
{
    register pcube last, p, RAISE, FREESET;
    pcover Fall_primes, B1;

    FREESET = new_cube();
    RAISE = new_cube();
    Fall_primes = new_cover(F->count);

    foreach_set(F, last, p) {
        if (TESTP(p, PRIME)) {
            Fall_primes = sf_addset(Fall_primes, p);
        } else {
            /* Setup for call to essential parts */
            (void) set_copy(RAISE, p);
            (void) set_diff(FREESET, cube.fullset, RAISE);
            setup_BB_CC(R, /* CC */ (pcover) NULL);
            essen_parts(R, /* CC */ (pcover) NULL, RAISE, FREESET);

            /* Find all of the primes, and add them to the prime set */
            B1 = find_all_primes(R, RAISE, FREESET);
            Fall_primes = sf_append(Fall_primes, B1);
        }
    }

    set_free(RAISE);
    set_free(FREESET);
    return Fall_primes;
}

---