summaryrefslogtreecommitdiffstats
path: root/src/misc/espresso/cvrm.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/espresso/cvrm.c')
-rw-r--r--src/misc/espresso/cvrm.c539
1 files changed, 539 insertions, 0 deletions
diff --git a/src/misc/espresso/cvrm.c b/src/misc/espresso/cvrm.c
new file mode 100644
index 00000000..7d42d6e3
--- /dev/null
+++ b/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;
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-26 15:51:58 +0000