From e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Sep 2007 08:01:00 -0700 Subject: Version abc70930 --- src/misc/espresso/cofactor.c | 382 ------------------------------------------- 1 file changed, 382 deletions(-) delete mode 100644 src/misc/espresso/cofactor.c (limited to 'src/misc/espresso/cofactor.c') diff --git a/src/misc/espresso/cofactor.c b/src/misc/espresso/cofactor.c deleted file mode 100644 index b851a639..00000000 --- a/src/misc/espresso/cofactor.c +++ /dev/null @@ -1,382 +0,0 @@ -/* - * Revision Control Information - * - * $Source$ - * $Author$ - * $Revision$ - * $Date$ - * - */ -#include "espresso.h" - -/* - The cofactor of a cover against a cube "c" is a cover formed by the - cofactor of each cube in the cover against c. The cofactor of two - cubes is null if they are distance 1 or more apart. If they are - distance zero apart, the cofactor is the restriction of the cube - to the minterms of c. - - The cube list contains the following information: - - T[0] = pointer to a cube identifying the variables that have - been cofactored against - T[1] = pointer to just beyond the sentinel (i.e., T[n] in this case) - T[2] - . - . = pointers to cubes - . - T[n-2] - T[n-1] = NULL pointer (sentinel) - - - Cofactoring involves repeated application of "cdist0" to check if a - cube of the cover intersects the cofactored cube. This can be - slow, especially for the recursive descent of the espresso - routines. Therefore, a special cofactor routine "scofactor" is - provided which assumes the cofactor is only in a single variable. -*/ - - -/* cofactor -- compute the cofactor of a cover with respect to a cube */ -pcube *cofactor(T, c) -IN pcube *T; -IN register pcube c; -{ - pcube temp = cube.temp[0], *Tc_save, *Tc, *T1; - register pcube p; - int listlen; - - listlen = CUBELISTSIZE(T) + 5; - - /* Allocate a new list of cube pointers (max size is previous size) */ - Tc_save = Tc = ALLOC(pcube, listlen); - - /* pass on which variables have been cofactored against */ - *Tc++ = set_or(new_cube(), T[0], set_diff(temp, cube.fullset, c)); - Tc++; - - /* Loop for each cube in the list, determine suitability, and save */ - for(T1 = T+2; (p = *T1++) != NULL; ) { - if (p != c) { - -#ifdef NO_INLINE - if (! cdist0(p, c)) goto false; -#else - {register int w,last;register unsigned int x;if((last=cube.inword)!=-1) - {x=p[last]&c[last];if(~(x|x>>1)&cube.inmask)goto false;for(w=1;w>1)&DISJOINT)goto false;}}}{register int w,var,last; - register pcube mask;for(var=cube.num_binary_vars;var= 0; i--) - count[i] = 0; - } - - /* Count the number of zeros in each column */ - { register int i, *cnt; - register unsigned int val; - register pcube p, cof = T[0], full = cube.fullset; - for(T1 = T+2; (p = *T1++) != NULL; ) - for(i = LOOP(p); i > 0; i--) - if (val = full[i] & ~ (p[i] | cof[i])) { - cnt = count + ((i-1) << LOGBPI); -#if BPI == 32 - if (val & 0xFF000000) { - if (val & 0x80000000) cnt[31]++; - if (val & 0x40000000) cnt[30]++; - if (val & 0x20000000) cnt[29]++; - if (val & 0x10000000) cnt[28]++; - if (val & 0x08000000) cnt[27]++; - if (val & 0x04000000) cnt[26]++; - if (val & 0x02000000) cnt[25]++; - if (val & 0x01000000) cnt[24]++; - } - if (val & 0x00FF0000) { - if (val & 0x00800000) cnt[23]++; - if (val & 0x00400000) cnt[22]++; - if (val & 0x00200000) cnt[21]++; - if (val & 0x00100000) cnt[20]++; - if (val & 0x00080000) cnt[19]++; - if (val & 0x00040000) cnt[18]++; - if (val & 0x00020000) cnt[17]++; - if (val & 0x00010000) cnt[16]++; - } -#endif - if (val & 0xFF00) { - if (val & 0x8000) cnt[15]++; - if (val & 0x4000) cnt[14]++; - if (val & 0x2000) cnt[13]++; - if (val & 0x1000) cnt[12]++; - if (val & 0x0800) cnt[11]++; - if (val & 0x0400) cnt[10]++; - if (val & 0x0200) cnt[ 9]++; - if (val & 0x0100) cnt[ 8]++; - } - if (val & 0x00FF) { - if (val & 0x0080) cnt[ 7]++; - if (val & 0x0040) cnt[ 6]++; - if (val & 0x0020) cnt[ 5]++; - if (val & 0x0010) cnt[ 4]++; - if (val & 0x0008) cnt[ 3]++; - if (val & 0x0004) cnt[ 2]++; - if (val & 0x0002) cnt[ 1]++; - if (val & 0x0001) cnt[ 0]++; - } - } - } - - /* - * Perform counts for each variable: - * cdata.var_zeros[var] = number of zeros in the variable - * cdata.parts_active[var] = number of active parts for each variable - * cdata.vars_active = number of variables which are active - * cdata.vars_unate = number of variables which are active and unate - * - * best -- the variable which is best for splitting based on: - * mostactive -- most # active parts in any variable - * mostzero -- most # zeros in any variable - * mostbalanced -- minimum over the maximum # zeros / part / variable - */ - - { register int var, i, lastbit, active, maxactive; - int best = -1, mostactive = 0, mostzero = 0, mostbalanced = 32000; - cdata.vars_unate = cdata.vars_active = 0; - - for(var = 0; var < cube.num_vars; var++) { - if (var < cube.num_binary_vars) { /* special hack for binary vars */ - i = count[var*2]; - lastbit = count[var*2 + 1]; - active = (i > 0) + (lastbit > 0); - cdata.var_zeros[var] = i + lastbit; - maxactive = MAX(i, lastbit); - } else { - maxactive = active = cdata.var_zeros[var] = 0; - lastbit = cube.last_part[var]; - for(i = cube.first_part[var]; i <= lastbit; i++) { - cdata.var_zeros[var] += count[i]; - active += (count[i] > 0); - if (active > maxactive) maxactive = active; - } - } - - /* first priority is to maximize the number of active parts */ - /* for binary case, this will usually select the output first */ - if (active > mostactive) - best = var, mostactive = active, mostzero = cdata.var_zeros[best], - mostbalanced = maxactive; - else if (active == mostactive) - /* secondary condition is to maximize the number zeros */ - /* for binary variables, this is the same as minimum # of 2's */ - if (cdata.var_zeros[var] > mostzero) - best = var, mostzero = cdata.var_zeros[best], - mostbalanced = maxactive; - else if (cdata.var_zeros[var] == mostzero) - /* third condition is to pick a balanced variable */ - /* for binary vars, this means roughly equal # 0's and 1's */ - if (maxactive < mostbalanced) - best = var, mostbalanced = maxactive; - - cdata.parts_active[var] = active; - cdata.is_unate[var] = (active == 1); - cdata.vars_active += (active > 0); - cdata.vars_unate += (active == 1); - } - cdata.best = best; - } -} - -int binate_split_select(T, cleft, cright, debug_flag) -IN pcube *T; -IN register pcube cleft, cright; -IN int debug_flag; -{ - int best = cdata.best; - register int i, lastbit = cube.last_part[best], halfbit = 0; - register pcube cof=T[0]; - - /* Create the cubes to cofactor against */ - (void) set_diff(cleft, cube.fullset, cube.var_mask[best]); - (void) set_diff(cright, cube.fullset, cube.var_mask[best]); - for(i = cube.first_part[best]; i <= lastbit; i++) - if (! is_in_set(cof,i)) - halfbit++; - for(i = cube.first_part[best], halfbit = halfbit/2; halfbit > 0; i++) - if (! is_in_set(cof,i)) - halfbit--, set_insert(cleft, i); - for(; i <= lastbit; i++) - if (! is_in_set(cof,i)) - set_insert(cright, i); - - if (debug & debug_flag) { - (void) printf("BINATE_SPLIT_SELECT: split against %d\n", best); - if (verbose_debug) - (void) printf("cl=%s\ncr=%s\n", pc1(cleft), pc2(cright)); - } - return best; -} - - -pcube *cube1list(A) -pcover A; -{ - register pcube last, p, *plist, *list; - - list = plist = ALLOC(pcube, A->count + 3); - *plist++ = new_cube(); - plist++; - foreach_set(A, last, p) { - *plist++ = p; - } - *plist++ = NULL; /* sentinel */ - list[1] = (pcube) plist; - return list; -} - - -pcube *cube2list(A, B) -pcover A, B; -{ - register pcube last, p, *plist, *list; - - list = plist = ALLOC(pcube, A->count + B->count + 3); - *plist++ = new_cube(); - plist++; - foreach_set(A, last, p) { - *plist++ = p; - } - foreach_set(B, last, p) { - *plist++ = p; - } - *plist++ = NULL; - list[1] = (pcube) plist; - return list; -} - - -pcube *cube3list(A, B, C) -pcover A, B, C; -{ - register pcube last, p, *plist, *list; - - plist = ALLOC(pcube, A->count + B->count + C->count + 3); - list = plist; - *plist++ = new_cube(); - plist++; - foreach_set(A, last, p) { - *plist++ = p; - } - foreach_set(B, last, p) { - *plist++ = p; - } - foreach_set(C, last, p) { - *plist++ = p; - } - *plist++ = NULL; - list[1] = (pcube) plist; - return list; -} - - -pcover cubeunlist(A1) -pcube *A1; -{ - register int i; - register pcube p, pdest, cof = A1[0]; - register pcover A; - - A = new_cover(CUBELISTSIZE(A1)); - for(i = 2; (p = A1[i]) != NULL; i++) { - pdest = GETSET(A, i-2); - INLINEset_or(pdest, p, cof); - } - A->count = CUBELISTSIZE(A1); - return A; -} - -simplify_cubelist(T) -pcube *T; -{ - register pcube *Tdest; - register int i, ncubes; - - (void) set_copy(cube.temp[0], T[0]); /* retrieve cofactor */ - - ncubes = CUBELISTSIZE(T); - qsort((char *) (T+2), ncubes, sizeof(pset), (int (*)()) d1_order); - - Tdest = T+2; - /* *Tdest++ = T[2]; */ - for(i = 3; i < ncubes; i++) { - if (d1_order(&T[i-1], &T[i]) != 0) { - *Tdest++ = T[i]; - } - } - - *Tdest++ = NULL; /* sentinel */ - Tdest[1] = (pcube) Tdest; /* save pointer to last */ -} -- cgit v1.2.3