| /* | |
| module: reduce.c | |
| purpose: Perform the Espresso-II reduction step | |
| Reduction is a technique used to explore larger regions of the | |
| optimization space. We replace each cube of F with a smaller | |
| cube while still maintaining a cover of the same logic function. | |
| */ | |
| #include "espresso.h" | |
| static bool toggle = TRUE; | |
| /* | |
| reduce -- replace each cube in F with its reduction | |
| The reduction of a cube is the smallest cube contained in the cube | |
| which can replace the cube in the original cover without changing | |
| the cover. This is equivalent to the super cube of all of the | |
| essential points in the cube. This can be computed directly. | |
| The problem is that the order in which the cubes are reduced can | |
| greatly affect the final result. We alternate between two ordering | |
| strategies: | |
| (1) Order the cubes in ascending order of distance from the | |
| largest cube breaking ties by ordering cubes of equal distance | |
| in descending order of size (sort_reduce) | |
| (2) Order the cubes in descending order of the inner-product of | |
| the cube and the column sums (mini_sort) | |
| The real workhorse of this section is the routine SCCC which is | |
| used to find the Smallest Cube Containing the Complement of a cover. | |
| Reduction as proposed by Espresso-II takes a cube and computes its | |
| maximal reduction as the intersection between the cube and the | |
| smallest cube containing the complement of (F u D - {c}) cofactored | |
| against c. | |
| As usual, the unate-recursive paradigm is used to compute SCCC. | |
| The SCCC of a unate cover is trivial to compute, and thus we perform | |
| Shannon Cofactor expansion attempting to drive the cover to be unate | |
| as fast as possible. | |
| */ | |
| pcover reduce(F, D) | |
| INOUT pcover F; | |
| IN pcover D; | |
| { | |
| register pcube last, p, cunder, *FD; | |
| /* Order the cubes */ | |
| if (use_random_order) | |
| F = random_order(F); | |
| else { | |
| F = toggle ? sort_reduce(F) : mini_sort(F, descend); | |
| toggle = ! toggle; | |
| } | |
| /* Try to reduce each cube */ | |
| FD = cube2list(F, D); | |
| foreach_set(F, last, p) { | |
| cunder = reduce_cube(FD, p); /* reduce the cube */ | |
| if (setp_equal(cunder, p)) { /* see if it actually did */ | |
| SET(p, ACTIVE); /* cube remains active */ | |
| SET(p, PRIME); /* cube remains prime ? */ | |
| } else { | |
| if (debug & REDUCE) { | |
| printf("REDUCE: %s to %s %s\n", | |
| pc1(p), pc2(cunder), print_time(ptime())); | |
| } | |
| set_copy(p, cunder); /* save reduced version */ | |
| RESET(p, PRIME); /* cube is no longer prime */ | |
| if (setp_empty(cunder)) | |
| RESET(p, ACTIVE); /* if null, kill the cube */ | |
| else | |
| SET(p, ACTIVE); /* cube is active */ | |
| } | |
| free_cube(cunder); | |
| } | |
| free_cubelist(FD); | |
| /* Delete any cubes of F which reduced to the empty cube */ | |
| return sf_inactive(F); | |
| } | |
| /* reduce_cube -- find the maximal reduction of a cube */ | |
| pcube reduce_cube(FD, p) | |
| IN pcube *FD, p; | |
| { | |
| pcube cunder; | |
| cunder = sccc(cofactor(FD, p)); | |
| return set_and(cunder, cunder, p); | |
| } | |
| /* sccc -- find Smallest Cube Containing the Complement of a cover */ | |
| pcube sccc(T) | |
| INOUT pcube *T; /* T will be disposed of */ | |
| { | |
| pcube r; | |
| register pcube cl, cr; | |
| register int best; | |
| static int sccc_level = 0; | |
| if (debug & REDUCE1) { | |
| debug_print(T, "SCCC", sccc_level++); | |
| } | |
| if (sccc_special_cases(T, &r) == MAYBE) { | |
| cl = new_cube(); | |
| cr = new_cube(); | |
| best = binate_split_select(T, cl, cr, REDUCE1); | |
| r = sccc_merge(sccc(scofactor(T, cl, best)), | |
| sccc(scofactor(T, cr, best)), cl, cr); | |
| free_cubelist(T); | |
| } | |
| if (debug & REDUCE1) | |
| printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r)); | |
| return r; | |
| } | |
| pcube sccc_merge(left, right, cl, cr) | |
| INOUT register pcube left, right; /* will be disposed of ... */ | |
| INOUT register pcube cl, cr; /* will be disposed of ... */ | |
| { | |
| INLINEset_and(left, left, cl); | |
| INLINEset_and(right, right, cr); | |
| INLINEset_or(left, left, right); | |
| free_cube(right); | |
| free_cube(cl); | |
| free_cube(cr); | |
| return left; | |
| } | |
| /* | |
| sccc_cube -- find the smallest cube containing the complement of a cube | |
| By DeMorgan's law and the fact that the smallest cube containing a | |
| cover is the "or" of the positional cubes, it is simple to see that | |
| the SCCC is the universe if the cube has more than two active | |
| variables. If there is only a single active variable, then the | |
| SCCC is merely the bitwise complement of the cube in that | |
| variable. A last special case is no active variables, in which | |
| case the SCCC is empty. | |
| This is "anded" with the incoming cube result. | |
| */ | |
| pcube sccc_cube(result, p) | |
| register pcube result, p; | |
| { | |
| register pcube temp=cube.temp[0], mask; | |
| int var; | |
| if ((var = cactive(p)) >= 0) { | |
| mask = cube.var_mask[var]; | |
| INLINEset_xor(temp, p, mask); | |
| INLINEset_and(result, result, temp); | |
| } | |
| return result; | |
| } | |
| /* | |
| * sccc_special_cases -- check the special cases for sccc | |
| */ | |
| bool sccc_special_cases(T, result) | |
| INOUT pcube *T; /* will be disposed if answer is determined */ | |
| OUT pcube *result; /* returned only if answer determined */ | |
| { | |
| register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0]; | |
| pcube *A, *B; | |
| /* empty cover => complement is universe => SCCC is universe */ | |
| if (T[2] == NULL) { | |
| *result = set_save(cube.fullset); | |
| free_cubelist(T); | |
| return TRUE; | |
| } | |
| /* row of 1's => complement is empty => SCCC is empty */ | |
| for(T1 = T+2; (p = *T1++) != NULL; ) { | |
| if (full_row(p, cof)) { | |
| *result = new_cube(); | |
| free_cubelist(T); | |
| return TRUE; | |
| } | |
| } | |
| /* Collect column counts, determine unate variables, etc. */ | |
| massive_count(T); | |
| /* If cover is unate (or single cube), apply simple rules to find SCCCU */ | |
| if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) { | |
| *result = set_save(cube.fullset); | |
| for(T1 = T+2; (p = *T1++) != NULL; ) { | |
| (void) sccc_cube(*result, set_or(temp, p, cof)); | |
| } | |
| free_cubelist(T); | |
| return TRUE; | |
| } | |
| /* Check for column of 0's (which can be easily factored( */ | |
| ceil = set_save(cof); | |
| for(T1 = T+2; (p = *T1++) != NULL; ) { | |
| INLINEset_or(ceil, ceil, p); | |
| } | |
| if (! setp_equal(ceil, cube.fullset)) { | |
| *result = sccc_cube(set_save(cube.fullset), ceil); | |
| if (setp_equal(*result, cube.fullset)) { | |
| free_cube(ceil); | |
| } else { | |
| *result = sccc_merge(sccc(cofactor(T,ceil)), | |
| set_save(cube.fullset), ceil, *result); | |
| } | |
| free_cubelist(T); | |
| return TRUE; | |
| } | |
| free_cube(ceil); | |
| /* Single active column at this point => tautology => SCCC is empty */ | |
| if (cdata.vars_active == 1) { | |
| *result = new_cube(); | |
| free_cubelist(T); | |
| return TRUE; | |
| } | |
| /* Check for components */ | |
| if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) { | |
| if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) { | |
| return MAYBE; | |
| } else { | |
| free_cubelist(T); | |
| *result = sccc(A); | |
| ceil = sccc(B); | |
| (void) set_and(*result, *result, ceil); | |
| set_free(ceil); | |
| return TRUE; | |
| } | |
| } | |
| /* Not much we can do about it */ | |
| return MAYBE; | |
| } |