| /* | |
| 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; | |
| } |