expand.c File Reference

#include "espresso.h"

Go to the source code of this file.

Macros
#define	NEW

Functions
ABC_NAMESPACE_IMPL_START pcover	expand (INOUT pcover F, IN pcover R, IN bool nonsparse)
void	expand1 (pcover BB, pcover CC, pcube RAISE, pcube FREESET, pcube OVEREXPANDED_CUBE, pcube SUPER_CUBE, pcube INIT_LOWER, int *num_covered, pcube c)
void	essen_parts (pcover BB, pcover CC, pcube RAISE, pcube FREESET)
void	essen_raising (pcover BB, pcube RAISE, pcube FREESET)
void	elim_lowering (pcover BB, pcover CC, pcube RAISE, pcube FREESET)
int	most_frequent (pcover CC, pcube FREESET)
void	setup_BB_CC (pcover BB, pcover CC)
void	select_feasible (pcover BB, pcover CC, pcube RAISE, pcube FREESET, pcube SUPER_CUBE, int *num_covered)
bool	feasibly_covered (pcover BB, pcube c, pcube RAISE, pcube new_lower)
void	mincov (pcover BB, pcube RAISE, pcube FREESET)
pcover	find_all_primes (pcover BB, pcube RAISE, pcube FREESET)
pcover	all_primes (pcover F, pcover R)

Macro Definition Documentation

#define NEW

Function Documentation

pcover all_primes	(	pcover	F,
		pcover	R
	)

Definition at line 669 of file expand.c.

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

void elim_lowering	(	pcover	BB,
		pcover	CC,
		pcube	RAISE,
		pcube	FREESET
	)

Definition at line 288 of file expand.c.

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

void essen_parts	(	pcover	BB,
		pcover	CC,
		pcube	RAISE,
		pcube	FREESET
	)

Definition at line 210 of file expand.c.

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

void essen_raising	(	pcover	BB,
		pcube	RAISE,
		pcube	FREESET
	)

Definition at line 259 of file expand.c.

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

ABC_NAMESPACE_IMPL_START pcover expand	(	INOUT pcover	F,
		IN pcover	R,
		IN bool	nonsparse
	)

Definition at line 53 of file expand.c.

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

void expand1	(	pcover	BB,
		pcover	CC,
		pcube	RAISE,
		pcube	FREESET,
		pcube	OVEREXPANDED_CUBE,
		pcube	SUPER_CUBE,
		pcube	INIT_LOWER,
		int *	num_covered,
		pcube	c
	)

Definition at line 135 of file expand.c.

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

bool feasibly_covered	(	pcover	BB,
		pcube	c,
		pcube	RAISE,
		pcube	new_lower
	)

Definition at line 521 of file expand.c.

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

pcover find_all_primes	(	pcover	BB,
		pcube	RAISE,
		pcube	FREESET
	)

Definition at line 634 of file expand.c.

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

void mincov	(	pcover	BB,
		pcube	RAISE,
		pcube	FREESET
	)

Definition at line 560 of file expand.c.

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

int most_frequent	(	pcover	CC,
		pcube	FREESET
	)

Definition at line 338 of file expand.c.

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

void select_feasible	(	pcover	BB,
		pcover	CC,
		pcube	RAISE,
		pcube	FREESET,
		pcube	SUPER_CUBE,
		int *	num_covered
	)

Definition at line 404 of file expand.c.

{
    register pcube p, last;
    register pcube bestfeas = NULL; // Suppress "might be used uninitialized"
    register pcube *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 */
}

void setup_BB_CC	(	pcover	BB,
		pcover	CC
	)

Definition at line 375 of file expand.c.

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