From 8eef7f8326e715ea4e9e84f46487cf4657601c25 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 20 Feb 2006 08:01:00 -0800 Subject: Version abc60220 --- src/misc/espresso/setc.c | 483 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 483 insertions(+) create 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 new file mode 100644 index 00000000..a6112ebc --- /dev/null +++ b/src/misc/espresso/setc.c @@ -0,0 +1,483 @@ +/* + * 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