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