summaryrefslogtreecommitdiffstats
path: root/src/misc/espresso/setc.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/espresso/setc.c')
-rw-r--r--src/misc/espresso/setc.c483
1 files changed, 483 insertions, 0 deletions
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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-28 11:12:15 +0000