src/misc/espresso/setc.c

Go to the documentation of this file.

/*
 * Revision Control Information
 *
 * $Source$
 * $Author$
 * $Revision$
 * $Date$
 *
 */
/*
    setc.c -- massive bit-hacking for performing special "cube"-type
    operations on a set

    The basic trick used for binary valued variables is the following:

    If a[w] and b[w] contain a full word of binary variables, then:

     1) to get the full word of their intersection, we use

            x = a[w] & b[w];


     2) to see if the intersection is null in any variables, we examine

            x = ~(x | x >> 1) & DISJOINT;

        this will have a single 1 in each binary variable for which
        the intersection is null.  In particular, if this is zero,
        then there are no disjoint variables; or, if this is nonzero,
        then there is at least one disjoint variable.  A "count_ones"
        over x will tell in how many variables they have an null
        intersection.


     3) to get a mask which selects the disjoint variables, we use

            (x | x << 1)

        this provides a selector which can be used to see where
        they have an null intersection


    cdist       return distance between two cubes
    cdist0      return true if two cubes are distance 0 apart
    cdist01     return distance, or 2 if distance exceeds 1
    consensus   compute consensus of two cubes distance 1 apart
    force_lower expand hack (for now), related to consensus
*/

#include "espresso.h"

/* see if the cube has a full row of 1's (with respect to cof) */
bool full_row(p, cof)
IN register pcube p, cof;
{
    register int i = LOOP(p);
    do if ((p[i] | cof[i]) != cube.fullset[i]) return FALSE; while (--i > 0);
    return TRUE;
}

/*
    cdist0 -- return TRUE if a and b are distance 0 apart
*/

bool cdist0(a, b)
register pcube a, b;
{
 {  /* Check binary variables */
    register int w, last; register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last] & b[last];
        if (~(x | x >> 1) & cube.inmask)
            return FALSE;               /* disjoint in some variable */

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w] & b[w];
            if (~(x | x >> 1) & DISJOINT)
                return FALSE;           /* disjoint in some variable */
        }
    }
 }

 {  /* Check the multiple-valued variables */
    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 (a[w] & b[w] & mask[w])
                goto nextvar;
        return FALSE;           /* disjoint in this variable */
    nextvar: ;
    }
 }
    return TRUE;
}

/*
    cdist01 -- return the "distance" between two cubes (defined as the
    number of null variables in their intersection).  If the distance
    exceeds 1, the value 2 is returned.
*/

int cdist01(a, b)
register pset a, b;
{
    int dist = 0;

 {  /* Check binary variables */
    register int w, last; register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last] & b[last];
        if (x = ~ (x | x >> 1) & cube.inmask)
            if ((dist = count_ones(x)) > 1)
                return 2;

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w] & b[w];
            if (x = ~ (x | x >> 1) & DISJOINT)
                if (dist == 1 || (dist += count_ones(x)) > 1)
                    return 2;
        }
    }
 }

 {  /* Check the multiple-valued variables */
    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 (a[w] & b[w] & mask[w])
                goto nextvar;
        if (++dist > 1)
            return 2;
    nextvar: ;
    }
 }
    return dist;
}

/*
    cdist -- return the "distance" between two cubes (defined as the
    number of null variables in their intersection).
*/

int cdist(a, b)
register pset a, b;
{
    int dist = 0;

 {  /* Check binary variables */
    register int w, last; register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last] & b[last];
        if (x = ~ (x | x >> 1) & cube.inmask)
            dist = count_ones(x);

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w] & b[w];
            if (x = ~ (x | x >> 1) & DISJOINT)
                dist += count_ones(x);
        }
    }
 }

 {  /* Check the multiple-valued variables */
    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 (a[w] & b[w] & mask[w])
                goto nextvar;
        dist++;
    nextvar: ;
    }
 }
    return dist;
}

/*
    force_lower -- Determine which variables of a do not intersect b.
*/

pset force_lower(xlower, a, b)
INOUT pset xlower;
IN register pset a, b;
{

 {  /* Check binary variables (if any) */
    register int w, last; register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last] & b[last];
        if (x = ~(x | x >> 1) & cube.inmask)
            xlower[last] |= (x | (x << 1)) & a[last];

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w] & b[w];
            if (x = ~(x | x >> 1) & DISJOINT)
                xlower[w] |= (x | (x << 1)) & a[w];
        }
    }
 }

 {  /* Check the multiple-valued variables */
    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 (a[w] & b[w] & mask[w])
                goto nextvar;
        for(w = cube.first_word[var]; w <= last; w++)
            xlower[w] |= a[w] & mask[w];
    nextvar: ;
    }
 }
    return xlower;
}

/*
    consensus -- multiple-valued consensus

    Although this looks very messy, the idea is to compute for r the
    "and" of the cubes a and b for each variable, unless the "and" is
    null in a variable, in which case the "or" of a and b is computed
    for this variable.

    Because we don't check how many variables are null in the
    intersection of a and b, the returned value for r really only
    represents the consensus when a and b are distance 1 apart.
*/

void consensus(r, a, b)
INOUT pcube r;
IN register pcube a, b;
{
    INLINEset_clear(r, cube.size);

 {  /* Check binary variables (if any) */
    register int w, last; register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        r[last] = x = a[last] & b[last];
        if (x = ~(x | x >> 1) & cube.inmask)
            r[last] |= (x | (x << 1)) & (a[last] | b[last]);

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            r[w] = x = a[w] & b[w];
            if (x = ~(x | x >> 1) & DISJOINT)
                r[w] |= (x | (x << 1)) & (a[w] | b[w]);
        }
    }
 }


 {  /* Check the multiple-valued variables */
    bool empty; int var; unsigned int x;
    register int w, 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];
        empty = TRUE;
        for(w = cube.first_word[var]; w <= last; w++)
            if (x = a[w] & b[w] & mask[w])
                empty = FALSE, r[w] |= x;
        if (empty)
            for(w = cube.first_word[var]; w <= last; w++)
                r[w] |= mask[w] & (a[w] | b[w]);
    }
 }
}

/*
    cactive -- return the index of the single active variable in
    the cube, or return -1 if there are none or more than 2.
*/

int cactive(a)
register pcube a;
{
    int active = -1, dist = 0, bit_index();

 {  /* Check binary variables */
    register int w, last;
    register unsigned int x;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last];
        if (x = ~ (x & x >> 1) & cube.inmask) {
            if ((dist = count_ones(x)) > 1)
                return -1;              /* more than 2 active variables */
            active = (last-1)*(BPI/2) + bit_index(x) / 2;
        }

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w];
            if (x = ~ (x & x >> 1) & DISJOINT) {
                if ((dist += count_ones(x)) > 1)
                    return -1;          /* more than 2 active variables */
                active = (w-1)*(BPI/2) + bit_index(x) / 2;
            }
        }
    }
 }

 {  /* Check the multiple-valued variables */
    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 (mask[w] & ~ a[w]) {
                if (++dist > 1)
                    return -1;
                active = var;
                break;
            }
    }
 }
 return active;
}

/*
    ccommon -- return TRUE if a and b are share "active" variables
    active variables include variables that are empty;
*/

bool ccommon(a, b, cof)
register pcube a, b, cof;
{
 {  /* Check binary variables */
    int last;
    register int w;
    register unsigned int x, y;
    if ((last = cube.inword) != -1) {

        /* Check the partial word of binary variables */
        x = a[last] | cof[last];
        y = b[last] | cof[last];
        if (~(x & x>>1) & ~(y & y>>1) & cube.inmask)
            return TRUE;

        /* Check the full words of binary variables */
        for(w = 1; w < last; w++) {
            x = a[w] | cof[w];
            y = b[w] | cof[w];
            if (~(x & x>>1) & ~(y & y>>1) & DISJOINT)
                return TRUE;
        }
    }
 }

 {  /* Check the multiple-valued variables */
    int var;
    register int w, 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];
        /* Check for some part missing from a */
        for(w = cube.first_word[var]; w <= last; w++)
            if (mask[w] & ~a[w] & ~cof[w]) {

                /* If so, check for some part missing from b */
                for(w = cube.first_word[var]; w <= last; w++)
                    if (mask[w] & ~b[w] & ~cof[w])
                        return TRUE;            /* both active */
                break;
            }
    }
 }
    return FALSE;
}

/*
    These routines compare two sets (cubes) for the qsort() routine and
    return:

        -1 if set a is to precede set b
         0 if set a and set b are equal
         1 if set a is to follow set b

    Usually the SIZE field of the set is assumed to contain the size
    of the set (which will save recomputing the set size during the
    sort).  For distance-1 merging, the global variable cube.temp[0] is
    a mask which mask's-out the merging variable.
*/

/* descend -- comparison for descending sort on set size */
int descend(a, b)
pset *a, *b;
{
    register pset a1 = *a, b1 = *b;
    if (SIZE(a1) > SIZE(b1)) return -1;
    else if (SIZE(a1) < SIZE(b1)) return 1;
    else {
        register int i = LOOP(a1);
        do
            if (a1[i] > b1[i]) return -1; else if (a1[i] < b1[i]) return 1;
        while (--i > 0);
    }
    return 0;
}

/* ascend -- comparison for ascending sort on set size */
int ascend(a, b)
pset *a, *b;
{
    register pset a1 = *a, b1 = *b;
    if (SIZE(a1) > SIZE(b1)) return 1;
    else if (SIZE(a1) < SIZE(b1)) return -1;
    else {
        register int i = LOOP(a1);
        do
            if (a1[i] > b1[i]) return 1; else if (a1[i] < b1[i]) return -1;
        while (--i > 0);
    }
    return 0;
}


/* lex_order -- comparison for "lexical" ordering of cubes */
int lex_order(a, b)
pset *a, *b;
{
    register pset a1 = *a, b1 = *b;
    register int i = LOOP(a1);
    do
        if (a1[i] > b1[i]) return -1; else if (a1[i] < b1[i]) return 1;
    while (--i > 0);
    return 0;
}


/* d1_order -- comparison for distance-1 merge routine */
int d1_order(a, b)
pset *a, *b;
{
    register pset a1 = *a, b1 = *b, c1 = cube.temp[0];
    register int i = LOOP(a1);
    register unsigned int x1, x2;
    do
        if ((x1 = a1[i] | c1[i]) > (x2 = b1[i] | c1[i])) return -1;
        else if (x1 < x2) return 1;
    while (--i > 0);
    return 0;
}


/* desc1 -- comparison (without indirection) for descending sort */
/* also has effect of handling NULL pointers,and a NULL pointer has smallest
order */
int desc1(a, b)
register pset a, b;
{
    if (a == (pset) NULL)
        return (b == (pset) NULL) ? 0 : 1;
    else if (b == (pset) NULL)
        return -1;
    if (SIZE(a) > SIZE(b)) return -1;
    else if (SIZE(a) < SIZE(b)) return 1;
    else {
        register int i = LOOP(a);
        do
            if (a[i] > b[i]) return -1; else if (a[i] < b[i]) return 1;
        while (--i > 0);
    }
    return 0;
}

---