From e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Sep 2007 08:01:00 -0700 Subject: Version abc70930 --- abc70930/src/misc/espresso/cvrm.c | 539 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 539 insertions(+) create mode 100644 abc70930/src/misc/espresso/cvrm.c (limited to 'abc70930/src/misc/espresso/cvrm.c') diff --git a/abc70930/src/misc/espresso/cvrm.c b/abc70930/src/misc/espresso/cvrm.c new file mode 100644 index 00000000..7d42d6e3 --- /dev/null +++ b/abc70930/src/misc/espresso/cvrm.c @@ -0,0 +1,539 @@ +/* + * Revision Control Information + * + * $Source$ + * $Author$ + * $Revision$ + * $Date$ + * + */ +/* + 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), (int (*)()) 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 */ + (void) set_copy(temp, GETSET(F, k)); + (void) set_copy(GETSET(F, k), GETSET(F, i)); + (void) 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) { + (void) 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; + } + + /* 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; + } + + /* 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; +} -- cgit v1.2.3