| /* |
| module: cvrm.c |
| Purpose: miscellaneous cover manipulation |
| a) verify two covers are equal, check consistency of a cover |
| b) unravel a multiple-valued cover into minterms |
| c) sort covers |
| */ |
| |
| #include "espresso.h" |
| |
| |
| static void cb_unravel(c, start, end, startbase, B1) |
| IN register pcube c; |
| IN int start, end; |
| IN pcube startbase; |
| INOUT pcover B1; |
| { |
| pcube base = cube.temp[0], p, last; |
| int expansion, place, skip, var, size, offset; |
| register int i, j, k, n; |
| |
| /* Determine how many cubes it will blow up into, and create a mask |
| for those parts that have only a single coordinate |
| */ |
| expansion = 1; |
| (void) set_copy(base, startbase); |
| for(var = start; var <= end; var++) { |
| if ((size = set_dist(c, cube.var_mask[var])) < 2) { |
| (void) set_or(base, base, cube.var_mask[var]); |
| } else { |
| expansion *= size; |
| } |
| } |
| (void) set_and(base, c, base); |
| |
| /* Add the unravelled sets starting at the last element of B1 */ |
| offset = B1->count; |
| B1->count += expansion; |
| foreach_remaining_set(B1, last, GETSET(B1, offset-1), p) { |
| INLINEset_copy(p, base); |
| } |
| |
| place = expansion; |
| for(var = start; var <= end; var++) { |
| if ((size = set_dist(c, cube.var_mask[var])) > 1) { |
| skip = place; |
| place = place / size; |
| n = 0; |
| for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) { |
| if (is_in_set(c, i)) { |
| for(j = n; j < expansion; j += skip) { |
| for(k = 0; k < place; k++) { |
| p = GETSET(B1, j+k+offset); |
| (void) set_insert(p, i); |
| } |
| } |
| n += place; |
| } |
| } |
| } |
| } |
| } |
| |
| |
| pcover unravel_range(B, start, end) |
| IN pcover B; |
| IN int start, end; |
| { |
| pcover B1; |
| int var, total_size, expansion, size; |
| register pcube p, last, startbase = cube.temp[1]; |
| |
| /* Create the starting base for those variables not being unravelled */ |
| (void) set_copy(startbase, cube.emptyset); |
| for(var = 0; var < start; var++) |
| (void) set_or(startbase, startbase, cube.var_mask[var]); |
| for(var = end+1; var < cube.num_vars; var++) |
| (void) set_or(startbase, startbase, cube.var_mask[var]); |
| |
| /* Determine how many cubes it will blow up into */ |
| total_size = 0; |
| foreach_set(B, last, p) { |
| expansion = 1; |
| for(var = start; var <= end; var++) |
| if ((size = set_dist(p, cube.var_mask[var])) >= 2) |
| if ((expansion *= size) > 1000000) |
| fatal("unreasonable expansion in unravel"); |
| total_size += expansion; |
| } |
| |
| /* We can now allocate a cover of exactly the correct size */ |
| B1 = new_cover(total_size); |
| foreach_set(B, last, p) { |
| cb_unravel(p, start, end, startbase, B1); |
| } |
| free_cover(B); |
| return B1; |
| } |
| |
| |
| pcover unravel(B, start) |
| IN pcover B; |
| IN int start; |
| { |
| return unravel_range(B, start, cube.num_vars-1); |
| } |
| |
| /* lex_sort -- sort cubes in a standard lexical fashion */ |
| pcover lex_sort(T) |
| pcover T; |
| { |
| pcover T1 = sf_unlist(sf_sort(T, lex_order), T->count, T->sf_size); |
| free_cover(T); |
| return T1; |
| } |
| |
| |
| /* size_sort -- sort cubes by their size */ |
| pcover size_sort(T) |
| pcover T; |
| { |
| pcover T1 = sf_unlist(sf_sort(T, descend), T->count, T->sf_size); |
| free_cover(T); |
| return T1; |
| } |
| |
| |
| /* mini_sort -- sort cubes according to the heuristics of mini */ |
| pcover mini_sort(F, compare) |
| pcover F; |
| int (*compare)(); |
| { |
| register int *count, cnt, n = cube.size, i; |
| register pcube p, last; |
| pcover F_sorted; |
| pcube *F1; |
| |
| /* Perform a column sum over the set family */ |
| count = sf_count(F); |
| |
| /* weight is "inner product of the cube and the column sums" */ |
| foreach_set(F, last, p) { |
| cnt = 0; |
| for(i = 0; i < n; i++) |
| if (is_in_set(p, i)) |
| cnt += count[i]; |
| PUTSIZE(p, cnt); |
| } |
| FREE(count); |
| |
| /* use qsort to sort the array */ |
| qsort((char *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare); |
| F_sorted = sf_unlist(F1, F->count, F->sf_size); |
| free_cover(F); |
| |
| return F_sorted; |
| } |
| |
| |
| /* sort_reduce -- Espresso strategy for ordering the cubes before reduction */ |
| pcover sort_reduce(T) |
| IN pcover T; |
| { |
| register pcube p, last, largest = NULL; |
| register int bestsize = -1, size, n = cube.num_vars; |
| pcover T_sorted; |
| pcube *T1; |
| |
| if (T->count == 0) |
| return T; |
| |
| /* find largest cube */ |
| foreach_set(T, last, p) |
| if ((size = set_ord(p)) > bestsize) |
| largest = p, bestsize = size; |
| |
| foreach_set(T, last, p) |
| PUTSIZE(p, ((n - cdist(largest,p)) << 7) + MIN(set_ord(p),127)); |
| |
| qsort((char *) (T1 = sf_list(T)), T->count, sizeof(pcube), descend); |
| T_sorted = sf_unlist(T1, T->count, T->sf_size); |
| free_cover(T); |
| |
| return T_sorted; |
| } |
| |
| pcover random_order(F) |
| register pcover F; |
| { |
| pset temp; |
| register int i, k; |
| #ifdef RANDOM |
| long random(); |
| #endif |
| |
| temp = set_new(F->sf_size); |
| for(i = F->count - 1; i > 0; i--) { |
| /* Choose a random number between 0 and i */ |
| #ifdef RANDOM |
| k = random() % i; |
| #else |
| /* this is not meant to be really used; just provides an easy |
| "out" if random() and srandom() aren't around |
| */ |
| k = (i*23 + 997) % i; |
| #endif |
| /* swap sets i and k */ |
| set_copy(temp, GETSET(F, k)); |
| set_copy(GETSET(F, k), GETSET(F, i)); |
| set_copy(GETSET(F, i), temp); |
| } |
| set_free(temp); |
| return F; |
| } |
| |
| /* |
| * cubelist_partition -- take a cubelist T and see if it has any components; |
| * if so, return cubelist's of the two partitions A and B; the return value |
| * is the size of the partition; if not, A and B |
| * are undefined and the return value is 0 |
| */ |
| int cubelist_partition(T, A, B, comp_debug) |
| pcube *T; /* a list of cubes */ |
| pcube **A, **B; /* cubelist of partition and remainder */ |
| unsigned int comp_debug; |
| { |
| register pcube *T1, p, seed, cof; |
| pcube *A1, *B1; |
| bool change; |
| int count, numcube; |
| |
| numcube = CUBELISTSIZE(T); |
| |
| /* Mark all cubes -- covered cubes belong to the partition */ |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| RESET(p, COVERED); |
| } |
| |
| /* |
| * Extract a partition from the cubelist T; start with the first cube as a |
| * seed, and then pull in all cubes which share a variable with the seed; |
| * iterate until no new cubes are brought into the partition. |
| */ |
| seed = set_save(T[2]); |
| cof = T[0]; |
| SET(T[2], COVERED); |
| count = 1; |
| |
| do { |
| change = FALSE; |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) { |
| INLINEset_and(seed, seed, p); |
| SET(p, COVERED); |
| change = TRUE; |
| count++; |
| } |
| |
| } |
| } while (change); |
| |
| set_free(seed); |
| |
| if (comp_debug) { |
| printf("COMPONENT_REDUCTION: split into %d %d\n", |
| count, numcube - count); |
| } |
| |
| if (count != numcube) { |
| /* Allocate and setup the cubelist's for the two partitions */ |
| *A = A1 = ALLOC(pcube, numcube+3); |
| *B = B1 = ALLOC(pcube, numcube+3); |
| (*A)[0] = set_save(T[0]); |
| (*B)[0] = set_save(T[0]); |
| A1 = *A + 2; |
| B1 = *B + 2; |
| |
| /* Loop over the cubes in T and distribute to A and B */ |
| for(T1 = T+2; (p = *T1++) != NULL; ) { |
| if (TESTP(p, COVERED)) { |
| *A1++ = p; |
| } else { |
| *B1++ = p; |
| } |
| } |
| |
| /* Stuff needed at the end of the cubelist's */ |
| *A1++ = NULL; |
| (*A)[1] = (pcube) A1; |
| *B1++ = NULL; |
| (*B)[1] = (pcube) B1; |
| } |
| |
| return numcube - count; |
| } |
| |
| /* |
| * quick cofactor against a single output function |
| */ |
| pcover cof_output(T, i) |
| pcover T; |
| register int i; |
| { |
| pcover T1; |
| register pcube p, last, pdest, mask; |
| |
| mask = cube.var_mask[cube.output]; |
| T1 = new_cover(T->count); |
| foreach_set(T, last, p) { |
| if (is_in_set(p, i)) { |
| pdest = GETSET(T1, T1->count++); |
| INLINEset_or(pdest, p, mask); |
| RESET(pdest, PRIME); |
| } |
| } |
| return T1; |
| } |
| |
| |
| /* |
| * quick intersection against a single output function |
| */ |
| pcover uncof_output(T, i) |
| pcover T; |
| int i; |
| { |
| register pcube p, last, mask; |
| |
| if (T == NULL) { |
| return T; |
| } |
| |
| mask = cube.var_mask[cube.output]; |
| foreach_set(T, last, p) { |
| INLINEset_diff(p, p, mask); |
| set_insert(p, i); |
| } |
| return T; |
| } |
| |
| |
| /* |
| * A generic routine to perform an operation for each output function |
| * |
| * func() is called with a PLA for each output function (with the output |
| * part effectively removed). |
| * func1() is called after reforming the equivalent output function |
| * |
| * Each function returns TRUE if process is to continue |
| */ |
| foreach_output_function(PLA, func, func1) |
| pPLA PLA; |
| int (*func)(); |
| int (*func1)(); |
| { |
| pPLA PLA1; |
| int i; |
| |
| /* Loop for each output function */ |
| for(i = 0; i < cube.part_size[cube.output]; i++) { |
| |
| /* cofactor on the output part */ |
| PLA1 = new_PLA(); |
| PLA1->F = cof_output(PLA->F, i + cube.first_part[cube.output]); |
| PLA1->R = cof_output(PLA->R, i + cube.first_part[cube.output]); |
| PLA1->D = cof_output(PLA->D, i + cube.first_part[cube.output]); |
| |
| /* Call a routine to do something with the cover */ |
| if ((*func)(PLA1, i) == 0) { |
| free_PLA(PLA1); |
| return 0; |
| } |
| |
| /* intersect with the particular output part again */ |
| PLA1->F = uncof_output(PLA1->F, i + cube.first_part[cube.output]); |
| PLA1->R = uncof_output(PLA1->R, i + cube.first_part[cube.output]); |
| PLA1->D = uncof_output(PLA1->D, i + cube.first_part[cube.output]); |
| |
| /* Call a routine to do something with the final result */ |
| if ((*func1)(PLA1, i) == 0) { |
| free_PLA(PLA1); |
| return 0; |
| } |
| |
| /* Cleanup for next go-around */ |
| free_PLA(PLA1); |
| |
| |
| } |
| } |
| |
| static pcover Fmin; |
| static pcube phase; |
| |
| /* |
| * minimize each output function individually |
| */ |
| void so_espresso(PLA, strategy) |
| pPLA PLA; |
| int strategy; |
| { |
| Fmin = new_cover(PLA->F->count); |
| if (strategy == 0) { |
| foreach_output_function(PLA, so_do_espresso, so_save); |
| } else { |
| foreach_output_function(PLA, so_do_exact, so_save); |
| } |
| sf_free(PLA->F); |
| PLA->F = Fmin; |
| } |
| |
| |
| /* |
| * minimize each output function, choose function or complement based on the |
| * one with the fewer number of terms |
| */ |
| void so_both_espresso(PLA, strategy) |
| pPLA PLA; |
| int strategy; |
| { |
| phase = set_save(cube.fullset); |
| Fmin = new_cover(PLA->F->count); |
| if (strategy == 0) { |
| foreach_output_function(PLA, so_both_do_espresso, so_both_save); |
| } else { |
| foreach_output_function(PLA, so_both_do_exact, so_both_save); |
| } |
| sf_free(PLA->F); |
| PLA->F = Fmin; |
| PLA->phase = phase; |
| } |
| |
| |
| int so_do_espresso(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| char word[32]; |
| |
| /* minimize the single-output function (on-set) */ |
| skip_make_sparse = 1; |
| (void) sprintf(word, "ESPRESSO-POS(%d)", i); |
| EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F); |
| return 1; |
| } |
| |
| |
| int so_do_exact(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| char word[32]; |
| |
| /* minimize the single-output function (on-set) */ |
| skip_make_sparse = 1; |
| (void) sprintf(word, "EXACT-POS(%d)", i); |
| EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F); |
| return 1; |
| } |
| |
| |
| /*ARGSUSED*/ |
| int so_save(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| Fmin = sf_append(Fmin, PLA->F); /* disposes of PLA->F */ |
| PLA->F = NULL; |
| return 1; |
| } |
| |
| |
| int so_both_do_espresso(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| char word[32]; |
| |
| /* minimize the single-output function (on-set) */ |
| (void) sprintf(word, "ESPRESSO-POS(%d)", i); |
| skip_make_sparse = 1; |
| EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F); |
| |
| /* minimize the single-output function (off-set) */ |
| (void) sprintf(word, "ESPRESSO-NEG(%d)", i); |
| skip_make_sparse = 1; |
| EXEC_S(PLA->R = espresso(PLA->R, PLA->D, PLA->F), word, PLA->R); |
| |
| return 1; |
| } |
| |
| |
| int so_both_do_exact(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| char word[32]; |
| |
| /* minimize the single-output function (on-set) */ |
| (void) sprintf(word, "EXACT-POS(%d)", i); |
| skip_make_sparse = 1; |
| EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F); |
| |
| /* minimize the single-output function (off-set) */ |
| (void) sprintf(word, "EXACT-NEG(%d)", i); |
| skip_make_sparse = 1; |
| EXEC_S(PLA->R = minimize_exact(PLA->R, PLA->D, PLA->F, 1), word, PLA->R); |
| |
| return 1; |
| } |
| |
| |
| int so_both_save(PLA, i) |
| pPLA PLA; |
| int i; |
| { |
| if (PLA->F->count > PLA->R->count) { |
| sf_free(PLA->F); |
| PLA->F = PLA->R; |
| PLA->R = NULL; |
| i += cube.first_part[cube.output]; |
| set_remove(phase, i); |
| } else { |
| sf_free(PLA->R); |
| PLA->R = NULL; |
| } |
| Fmin = sf_append(Fmin, PLA->F); |
| PLA->F = NULL; |
| return 1; |
| } |