| /* | |
| 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; | |
| } |