From 4d30a1e4f1edecff86d5066ce4653a370e59e5e1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Jan 2008 08:01:00 -0800 Subject: Version abc80130 --- src/misc/espresso/setc.c | 483 ----------------------------------------------- 1 file changed, 483 deletions(-) delete mode 100644 src/misc/espresso/setc.c (limited to 'src/misc/espresso/setc.c') diff --git a/src/misc/espresso/setc.c b/src/misc/espresso/setc.c deleted file mode 100644 index a6112ebc..00000000 --- a/src/misc/espresso/setc.c +++ /dev/null @@ -1,483 +0,0 @@ -/* - * 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; -} -- cgit v1.2.3