"Fossies" - the Fresh Open Source Software Archive

Member "heaplayers-351/benchmarks/espresso/cvrm.c" (19 Sep 2003, 12126 Bytes) of package /linux/misc/old/heaplayers_3_5_1.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "cvrm.c" see the Fossies "Dox" file reference documentation.

    1 /*
    2     module: cvrm.c
    3     Purpose: miscellaneous cover manipulation
    4     a) verify two covers are equal, check consistency of a cover
    5     b) unravel a multiple-valued cover into minterms
    6     c) sort covers
    7 */
    8 
    9 #include "espresso.h"
   10 
   11 
   12 static void cb_unravel(c, start, end, startbase, B1)
   13 IN register pcube c;
   14 IN int start, end;
   15 IN pcube startbase;
   16 INOUT pcover B1;
   17 {
   18     pcube base = cube.temp[0], p, last;
   19     int expansion, place, skip, var, size, offset;
   20     register int i, j, k, n;
   21 
   22     /* Determine how many cubes it will blow up into, and create a mask
   23     for those parts that have only a single coordinate
   24     */
   25     expansion = 1;
   26     (void) set_copy(base, startbase);
   27     for(var = start; var <= end; var++) {
   28     if ((size = set_dist(c, cube.var_mask[var])) < 2) {
   29         (void) set_or(base, base, cube.var_mask[var]);
   30     } else {
   31         expansion *= size;
   32     }
   33     }
   34     (void) set_and(base, c, base);
   35 
   36     /* Add the unravelled sets starting at the last element of B1 */
   37     offset = B1->count;
   38     B1->count += expansion;
   39     foreach_remaining_set(B1, last, GETSET(B1, offset-1), p) {
   40     INLINEset_copy(p, base);
   41     }
   42 
   43     place = expansion;
   44     for(var = start; var <= end; var++) {
   45     if ((size = set_dist(c, cube.var_mask[var])) > 1) {
   46         skip = place;
   47         place = place / size;
   48         n = 0;
   49         for(i = cube.first_part[var]; i <= cube.last_part[var]; i++) {
   50         if (is_in_set(c, i)) {
   51             for(j = n; j < expansion; j += skip) {
   52             for(k = 0; k < place; k++) {
   53                 p = GETSET(B1, j+k+offset);
   54                 (void) set_insert(p, i);
   55             }
   56             }
   57             n += place;
   58         }
   59         }
   60     }
   61     }
   62 }
   63 
   64 
   65 pcover unravel_range(B, start, end)
   66 IN pcover B;
   67 IN int start, end;
   68 {
   69     pcover B1;
   70     int var, total_size, expansion, size;
   71     register pcube p, last, startbase = cube.temp[1];
   72 
   73     /* Create the starting base for those variables not being unravelled */
   74     (void) set_copy(startbase, cube.emptyset);
   75     for(var = 0; var < start; var++)
   76     (void) set_or(startbase, startbase, cube.var_mask[var]);
   77     for(var = end+1; var < cube.num_vars; var++)
   78     (void) set_or(startbase, startbase, cube.var_mask[var]);
   79 
   80     /* Determine how many cubes it will blow up into */
   81     total_size = 0;
   82     foreach_set(B, last, p) {
   83     expansion = 1;
   84     for(var = start; var <= end; var++)
   85         if ((size = set_dist(p, cube.var_mask[var])) >= 2)
   86         if ((expansion *= size) > 1000000)
   87             fatal("unreasonable expansion in unravel");
   88     total_size += expansion;
   89     }
   90 
   91     /* We can now allocate a cover of exactly the correct size */
   92     B1 = new_cover(total_size);
   93     foreach_set(B, last, p) {
   94     cb_unravel(p, start, end, startbase, B1);
   95     }
   96     free_cover(B);
   97     return B1;
   98 }
   99 
  100 
  101 pcover unravel(B, start)
  102 IN pcover B;
  103 IN int start;
  104 {
  105     return unravel_range(B, start, cube.num_vars-1);
  106 }
  107 
  108 /* lex_sort -- sort cubes in a standard lexical fashion */
  109 pcover lex_sort(T)
  110 pcover T;
  111 {
  112     pcover T1 = sf_unlist(sf_sort(T, lex_order), T->count, T->sf_size);
  113     free_cover(T);
  114     return T1;
  115 }
  116 
  117 
  118 /* size_sort -- sort cubes by their size */
  119 pcover size_sort(T)
  120 pcover T;
  121 {
  122     pcover T1 = sf_unlist(sf_sort(T, descend), T->count, T->sf_size);
  123     free_cover(T);
  124     return T1;
  125 }
  126 
  127 
  128 /*  mini_sort -- sort cubes according to the heuristics of mini */
  129 pcover mini_sort(F, compare)
  130 pcover F;
  131 int (*compare)();
  132 {
  133     register int *count, cnt, n = cube.size, i;
  134     register pcube p, last;
  135     pcover F_sorted;
  136     pcube *F1;
  137 
  138     /* Perform a column sum over the set family */
  139     count = sf_count(F);
  140 
  141     /* weight is "inner product of the cube and the column sums" */
  142     foreach_set(F, last, p) {
  143     cnt = 0;
  144     for(i = 0; i < n; i++)
  145         if (is_in_set(p, i))
  146         cnt += count[i];
  147     PUTSIZE(p, cnt);
  148     }
  149     FREE(count);
  150 
  151     /* use qsort to sort the array */
  152     qsort((char *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare);
  153     F_sorted = sf_unlist(F1, F->count, F->sf_size);
  154     free_cover(F);
  155 
  156     return F_sorted;
  157 }
  158 
  159 
  160 /* sort_reduce -- Espresso strategy for ordering the cubes before reduction */
  161 pcover sort_reduce(T)
  162 IN pcover T;
  163 {
  164     register pcube p, last, largest = NULL;
  165     register int bestsize = -1, size, n = cube.num_vars;
  166     pcover T_sorted;
  167     pcube *T1;
  168 
  169     if (T->count == 0)
  170     return T;
  171 
  172     /* find largest cube */
  173     foreach_set(T, last, p)
  174     if ((size = set_ord(p)) > bestsize)
  175         largest = p, bestsize = size;
  176 
  177     foreach_set(T, last, p)
  178     PUTSIZE(p, ((n - cdist(largest,p)) << 7) + MIN(set_ord(p),127));
  179 
  180     qsort((char *) (T1 = sf_list(T)), T->count, sizeof(pcube), descend);
  181     T_sorted = sf_unlist(T1, T->count, T->sf_size);
  182     free_cover(T);
  183 
  184     return T_sorted;
  185 }
  186 
  187 pcover random_order(F)
  188 register pcover F;
  189 {
  190     pset temp;
  191     register int i, k;
  192 #ifdef RANDOM
  193     long random();
  194 #endif
  195 
  196     temp = set_new(F->sf_size);
  197     for(i = F->count - 1; i > 0; i--) {
  198     /* Choose a random number between 0 and i */
  199 #ifdef RANDOM
  200     k = random() % i;
  201 #else
  202     /* this is not meant to be really used; just provides an easy
  203        "out" if random() and srandom() aren't around
  204     */
  205     k = (i*23 + 997) % i;
  206 #endif
  207     /* swap sets i and k */
  208     set_copy(temp, GETSET(F, k));
  209     set_copy(GETSET(F, k), GETSET(F, i));
  210     set_copy(GETSET(F, i), temp);
  211     }
  212     set_free(temp);
  213     return F;
  214 }
  215 
  216 /*
  217  *  cubelist_partition -- take a cubelist T and see if it has any components;
  218  *  if so, return cubelist's of the two partitions A and B; the return value
  219  *  is the size of the partition; if not, A and B
  220  *  are undefined and the return value is 0
  221  */
  222 int cubelist_partition(T, A, B, comp_debug)
  223 pcube *T;           /* a list of cubes */
  224 pcube **A, **B;         /* cubelist of partition and remainder */
  225 unsigned int comp_debug;
  226 {
  227     register pcube *T1, p, seed, cof;
  228     pcube *A1, *B1;
  229     bool change;
  230     int count, numcube;
  231 
  232     numcube = CUBELISTSIZE(T);
  233 
  234     /* Mark all cubes -- covered cubes belong to the partition */
  235     for(T1 = T+2; (p = *T1++) != NULL; ) {
  236     RESET(p, COVERED);
  237     }
  238 
  239     /*
  240      *  Extract a partition from the cubelist T; start with the first cube as a
  241      *  seed, and then pull in all cubes which share a variable with the seed;
  242      *  iterate until no new cubes are brought into the partition.
  243      */
  244     seed = set_save(T[2]);
  245     cof = T[0];
  246     SET(T[2], COVERED);
  247     count = 1;
  248 
  249     do {
  250     change = FALSE;
  251     for(T1 = T+2; (p = *T1++) != NULL; ) {
  252         if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) {
  253         INLINEset_and(seed, seed, p);
  254         SET(p, COVERED);
  255         change = TRUE;
  256         count++;
  257         }
  258     
  259     }
  260     } while (change);
  261 
  262     set_free(seed);
  263 
  264     if (comp_debug) {
  265     printf("COMPONENT_REDUCTION: split into %d %d\n",
  266         count, numcube - count);
  267     }
  268 
  269     if (count != numcube) {
  270     /* Allocate and setup the cubelist's for the two partitions */
  271     *A = A1 = ALLOC(pcube, numcube+3);
  272     *B = B1 = ALLOC(pcube, numcube+3);
  273     (*A)[0] = set_save(T[0]);
  274     (*B)[0] = set_save(T[0]);
  275     A1 = *A + 2;
  276     B1 = *B + 2;
  277 
  278     /* Loop over the cubes in T and distribute to A and B */
  279     for(T1 = T+2; (p = *T1++) != NULL; ) {
  280         if (TESTP(p, COVERED)) {
  281         *A1++ = p;
  282         } else {
  283         *B1++ = p;
  284         }
  285     }
  286 
  287     /* Stuff needed at the end of the cubelist's */
  288     *A1++ = NULL;
  289     (*A)[1] = (pcube) A1;
  290     *B1++ = NULL;
  291     (*B)[1] = (pcube) B1;
  292     }
  293 
  294     return numcube - count;
  295 }
  296 
  297 /*
  298  *  quick cofactor against a single output function
  299  */
  300 pcover cof_output(T, i)
  301 pcover T;
  302 register int i;
  303 {
  304     pcover T1;
  305     register pcube p, last, pdest, mask;
  306 
  307     mask = cube.var_mask[cube.output];
  308     T1 = new_cover(T->count);
  309     foreach_set(T, last, p) {
  310     if (is_in_set(p, i)) {
  311         pdest = GETSET(T1, T1->count++);
  312         INLINEset_or(pdest, p, mask);
  313         RESET(pdest, PRIME);
  314     }
  315     }
  316     return T1;
  317 }
  318 
  319 
  320 /*
  321  *  quick intersection against a single output function
  322  */
  323 pcover uncof_output(T, i)
  324 pcover T;
  325 int i;
  326 {
  327     register pcube p, last, mask;
  328 
  329     if (T == NULL) {
  330     return T;
  331     }
  332 
  333     mask = cube.var_mask[cube.output];
  334     foreach_set(T, last, p) {
  335     INLINEset_diff(p, p, mask);
  336     set_insert(p, i);
  337     }
  338     return T;
  339 }
  340 
  341 
  342 /*
  343  *  A generic routine to perform an operation for each output function
  344  *
  345  *  func() is called with a PLA for each output function (with the output
  346  *  part effectively removed).
  347  *  func1() is called after reforming the equivalent output function
  348  *
  349  *  Each function returns TRUE if process is to continue
  350  */
  351 foreach_output_function(PLA, func, func1)
  352 pPLA PLA;
  353 int (*func)();
  354 int (*func1)();
  355 {
  356     pPLA PLA1;
  357     int i;
  358 
  359     /* Loop for each output function */
  360     for(i = 0; i < cube.part_size[cube.output]; i++) {
  361 
  362     /* cofactor on the output part */
  363     PLA1 = new_PLA();
  364     PLA1->F = cof_output(PLA->F, i + cube.first_part[cube.output]);
  365     PLA1->R = cof_output(PLA->R, i + cube.first_part[cube.output]);
  366     PLA1->D = cof_output(PLA->D, i + cube.first_part[cube.output]);
  367 
  368     /* Call a routine to do something with the cover */
  369     if ((*func)(PLA1, i) == 0) {
  370         free_PLA(PLA1);
  371         return;
  372     }
  373 
  374     /* intersect with the particular output part again */
  375     PLA1->F = uncof_output(PLA1->F, i + cube.first_part[cube.output]);
  376     PLA1->R = uncof_output(PLA1->R, i + cube.first_part[cube.output]);
  377     PLA1->D = uncof_output(PLA1->D, i + cube.first_part[cube.output]);
  378 
  379     /* Call a routine to do something with the final result */
  380     if ((*func1)(PLA1, i) == 0) {
  381         free_PLA(PLA1);
  382         return;
  383     }
  384 
  385     /* Cleanup for next go-around */
  386     free_PLA(PLA1);
  387     
  388 
  389     }
  390 }
  391 
  392 static pcover Fmin;
  393 static pcube phase;
  394 
  395 /*
  396  *  minimize each output function individually
  397  */
  398 void so_espresso(PLA, strategy)
  399 pPLA PLA;
  400 int strategy;
  401 {
  402     Fmin = new_cover(PLA->F->count);
  403     if (strategy == 0) {
  404     foreach_output_function(PLA, so_do_espresso, so_save);
  405     } else {
  406     foreach_output_function(PLA, so_do_exact, so_save);
  407     }
  408     sf_free(PLA->F);
  409     PLA->F = Fmin;
  410 }
  411 
  412 
  413 /*
  414  *  minimize each output function, choose function or complement based on the
  415  *  one with the fewer number of terms
  416  */
  417 void so_both_espresso(PLA, strategy)
  418 pPLA PLA;
  419 int strategy;
  420 {
  421     phase = set_save(cube.fullset);
  422     Fmin = new_cover(PLA->F->count);
  423     if (strategy == 0) {
  424     foreach_output_function(PLA, so_both_do_espresso, so_both_save);
  425     } else {
  426     foreach_output_function(PLA, so_both_do_exact, so_both_save);
  427     }
  428     sf_free(PLA->F);
  429     PLA->F = Fmin;
  430     PLA->phase = phase;
  431 }
  432 
  433 
  434 int so_do_espresso(PLA, i)
  435 pPLA PLA;
  436 int i;
  437 {
  438     char word[32];
  439 
  440     /* minimize the single-output function (on-set) */
  441     skip_make_sparse = 1;
  442     (void) sprintf(word, "ESPRESSO-POS(%d)", i);
  443     EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
  444     return 1;
  445 }
  446 
  447 
  448 int so_do_exact(PLA, i)
  449 pPLA PLA;
  450 int i;
  451 {
  452     char word[32];
  453 
  454     /* minimize the single-output function (on-set) */
  455     skip_make_sparse = 1;
  456     (void) sprintf(word, "EXACT-POS(%d)", i);
  457     EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
  458     return 1;
  459 }
  460 
  461 
  462 /*ARGSUSED*/
  463 int so_save(PLA, i)
  464 pPLA PLA;
  465 int i;
  466 {
  467     Fmin = sf_append(Fmin, PLA->F); /* disposes of PLA->F */
  468     PLA->F = NULL;
  469     return 1;
  470 }
  471 
  472 
  473 int so_both_do_espresso(PLA, i)
  474 pPLA PLA;
  475 int i;
  476 {
  477     char word[32];
  478 
  479     /* minimize the single-output function (on-set) */
  480     (void) sprintf(word, "ESPRESSO-POS(%d)", i);
  481     skip_make_sparse = 1;
  482     EXEC_S(PLA->F = espresso(PLA->F, PLA->D, PLA->R), word, PLA->F);
  483 
  484     /* minimize the single-output function (off-set) */
  485     (void) sprintf(word, "ESPRESSO-NEG(%d)", i);
  486     skip_make_sparse = 1;
  487     EXEC_S(PLA->R = espresso(PLA->R, PLA->D, PLA->F), word, PLA->R);
  488 
  489     return 1;
  490 }
  491 
  492 
  493 int so_both_do_exact(PLA, i)
  494 pPLA PLA;
  495 int i;
  496 {
  497     char word[32];
  498 
  499     /* minimize the single-output function (on-set) */
  500     (void) sprintf(word, "EXACT-POS(%d)", i);
  501     skip_make_sparse = 1;
  502     EXEC_S(PLA->F = minimize_exact(PLA->F, PLA->D, PLA->R, 1), word, PLA->F);
  503 
  504     /* minimize the single-output function (off-set) */
  505     (void) sprintf(word, "EXACT-NEG(%d)", i);
  506     skip_make_sparse = 1;
  507     EXEC_S(PLA->R = minimize_exact(PLA->R, PLA->D, PLA->F, 1), word, PLA->R);
  508 
  509     return 1;
  510 }
  511 
  512 
  513 int so_both_save(PLA, i)
  514 pPLA PLA;
  515 int i;
  516 {
  517     if (PLA->F->count > PLA->R->count) {
  518     sf_free(PLA->F);
  519     PLA->F = PLA->R;
  520     PLA->R = NULL;
  521     i += cube.first_part[cube.output];
  522     set_remove(phase, i);
  523     } else {
  524     sf_free(PLA->R);
  525     PLA->R = NULL;
  526     }
  527     Fmin = sf_append(Fmin, PLA->F);
  528     PLA->F = NULL;
  529     return 1;
  530 }