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, 0 insertions, 483 deletions
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;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-28 11:13:36 +0000