#include "cubes.h"

/****************************************************************************

NAME
	star_product

PURPOSE
	This function generates the biggest cube that can be created
	from two adjacent cubes. The variable for which adjacency is
	checked is predefined as the current_var.

SYNOPSIS
	int star_product(cube1,cube2,result_cube)
	long int *cube1,*cube2,*result_cube;

DESCRIPTION
	The two cubes are used to form the biggest possible cube out of them.
	If they are not adjacent for the current_var or if their output 
        are disjoint, no cube can be formed and the value 0 is returned.
	Otherwise 1 is returned.

COORDINATES
	McGill University Electrical Engineering VLSI Lab MONTREAL CANADA
	19 june 1984

AUTHOR
	Michel DAGENAIS

************************************************************************/

int star_product(cube1,cube2,result_cube)

long int *cube1,*cube2,*result_cube;
{
  long int
	result,		/* word containing the intersection */
	*end_input,	/* pointer to the word after the last word of input */
	*end_output,	/* pointer to the word after the last word of cube */
	*merged_word,	/* pointer to the word in which is the current var */
	intersect_mask; /* mask that contains 10 for intersecting var and 00 */
			/* for non-intersecting var */

  int common_output;

  merged_word = cube1 + current_word_index;
  end_input = cube1 + input_length;
  end_output = cube1 + total_length;

#ifdef DEBUG
  printf("cube1 %lx merged_word %lx current_mask11 %lx current_mask10 %lx\n",
         cube1,merged_word,current_mask11,current_mask10);
#endif

  for(; cube1 < end_input ; cube1++)

/*	we put the intersection in result_word		*/

   { result = *cube1 & *cube2;

/*	we check if the intersection is null on one variable	*/

     intersect_mask = ((result << 1) | result) & mask10;
     if(intersect_mask != mask10)

/*	the null intersection should be only on the current_var which means
	that the two cubes are adjacent along that variable.
	If the null part is for another variable, 0 is returned and no merging
	is possible along that variable. If the merging can be performed, that
	part becomes an x.					*/

      { if((intersect_mask | current_mask10) != mask10)return(0);
	if(cube1 != merged_word) return(0);
        result |= current_mask11;
      }
     *result_cube = result;
     cube2++;
     result_cube++;
   }

/* the input of the new cube is formed, we must now check if its output is
   empty, and if not compute it */

  common_output = 0;
  for(; cube1 < end_output ; cube1++)
   { *result_cube = *cube1 & *cube2;
     if(*result_cube != 0L) common_output = 1;
     cube2++;
     result_cube++;
   }
  if(common_output) return(1);
  else return(0);
}

/****************************************************************************

NAME
	covers, covers_input, absorb, covers_list

PURPOSE
	This function tells you if a cube covers completely another one.

SYNOPSIS
	int covers(cube1,cube2)
	long int *cube1,*cube2;

        int covers_input(cube1,cube2)
	long int *cube1, *cube2;

	int absorb(cube1,cube2)
	long int *cube1,*cube2;

	int covers_list(cube,list)
	long int *cube;
	struct cube_list *list;

DESCRIPTION

    -covers returns 1 if cube1 covers cube2 and 0 otherwise.

    -covers_input returns 1 if the input of cube1 covers the input of cube2. 

    -absorb returns -1 if nobody covers nobody, 0 if cube1 and cube2 are equal,
	1 if cube1 covers cube2 and 2 if cube2 covers cube1.

    -covers_list returns 1 if cube covers all the cube in the list and 0 
	otherwise.

COORDINATES
	McGill University Electrical Engineering VLSI Lab MONTREAL CANADA
	19 june 1984

AUTHOR
	Michel DAGENAIS

************************************************************************/

int covers(cube1,cube2)

long int *cube1,*cube2;
{
  long int *end_of_cube; /* pointer to the word after the last of cube*/

  end_of_cube = cube1 + total_length;

  for(; cube1 < end_of_cube ; cube1++)
   { if((*cube1 & *cube2) != *cube2 ) return(0);
     cube2++;
   }
  return(1);
 }

/**********************************************************************/

#ifdef DEBUG

int covers_input(cube1,cube2)

long int *cube1,*cube2;
{
  long int *end_of_input; /* pointer to the word after the last of cube*/

  end_of_input = cube1 + input_length;

  for(; cube1 < end_of_input ; cube1++)
   { if((*cube1 & *cube2) != *cube2 ) return(0);
     cube2++;
   }
  return(1);
 }

#endif

/***********************************************************************/

int absorb(cube1,cube2)

long int *cube1,*cube2;
{
  long int 
	*end_of_cube,	/* pointer to the word after the last of cube */
	and_cubes;	/* intersection of the two cubes */

  int 
	cube1_covers,	/* logic variable tells if 1 covers 2 up to now */
	cube2_covers;	/* logic variable tells if 2 covers 1 up to now */

  end_of_cube = cube1 + total_length;

  cube1_covers = 1;
  cube2_covers = 1;

  for(; cube1 < end_of_cube ; cube1++)
   { and_cubes = *cube1 & *cube2;
     if(and_cubes != *cube1)
      { if(cube1_covers == 0) return(-1);
        else cube2_covers = 0;
      }
     if(and_cubes != *cube2)
      { if(cube2_covers == 0) return(-1);
        else cube1_covers = 0;
      }
     cube2++;
   }
  if(cube1_covers)
   { if(cube2_covers) return(0);	/* both cubes are equal */
     else return(1);	/* cube 1 covers cube 2 */
   }
  else return(2);	/* cube 2 covers cube 1 */
}

/********************************************************************/

int covers_list(cube,list)

long int *cube;
struct cube_list *list;
{
  for(; list != NULL ; list = list->next_cube)
   { if(covers(cube,list->cube) == 0) return(0);
   }
  return(1);
}

/****************************************************************************

NAME
	intersect, intersect_list

PURPOSE
	These functions check if two cubes do intersect.

SYNOPSIS
	int intersect(cube1,cube2)
	long int *cube1,*cube2;

	int intersect_list(cube,list)
	struct cube_list *list;
	long int *cube;

DESCRIPTION

    -intersect returns 1 if cube1 and cube2 do intersect and 0 otherwise.

    -intersect_list returns 1 if cube1 intersects with any cube in list and 0
	otherwise.

COORDINATES
	McGill University Electrical Engineering VLSI Lab MONTREAL CANADA
	19 june 1984

AUTHOR
	Michel DAGENAIS

************************************************************************/

int intersect(cube1,cube2)

long int *cube1,*cube2;
{
  long int 
	*end_of_input,		/* pointer to word after input of cube */
	*end_of_output,		/* pointer to word after output of cube */
	result;			/* intersection of the cubes */

  end_of_input = cube1 + input_length;
  end_of_output = cube1 + total_length;

  for(; cube1 < end_of_input ; cube1++)
   { result = *cube1 & *cube2;

/*	we want to detect if the intersection is null for any variable */

     if((((result << 1) | result ) & mask10) != mask10) return(0);
     cube2++;
   }
  for(; cube1 < end_of_output ; cube1++)
   { if((*cube1 & *cube2) != 0L) return(1);
     cube2++;
   }
  return(0);
}

/*************************************************************************/

int intersect_list(cube,list)

long int *cube;
struct cube_list *list;
{
  for(; list != NULL ; list = list->next_cube)
   { if(intersect(cube,list->cube)) return(1);
   }
  return(0);
}

/****************************************************************************

NAME
	disjoint_sharp

PURPOSE
	This function takes a list of disjoint cubes and sharp from it
	another cube. The list is updated to contain the result.

SYNOPSIS
	int disjoint_sharp(list,cube)
	long int *cube;
	struct cube_list **list;

DESCRIPTION
	the function takes each cube in the list, see if the other cube
	intersect with it. If so a new list is computed such that it is
	disjoint from the cube but the union of the cube and the new
	list has the same coverage as with the old list and the cube. It is the 
	disjoint sharp operation as defined by Hong and Opstako for
	their MINI program. The implementation is different however.
	The function returns 1 when the list is empty after the sharp.
	Otherwise the function returns 0.

COORDINATES
	McGill University Electrical Engineering VLSI Lab MONTREAL CANADA
	19 june 1984

AUTHOR
	Michel DAGENAIS

************************************************************************/

int disjoint_sharp(list,cube)

long int *cube;
struct cube_list **list;
{
  struct cube_list 
	*present_cube_list,	/*pointer to the cube_list element considered*/
	**previous_cube,	/*pointer to the next_cube element of previous*/
				/* cube, useful when we want to delete an */
				/* element in the list */
	*temp_pointer;		/* temporary pointer when a cube is splitted */

  long int 
	*end_input,		/* pointer to end of input of a cube */
	*end_output,		/* pointer to end of output of a cube */
	*present_cube,		/* pointer to the cube considered */
	*sharping_cube,		/* pointer to the cube we sharp from the list*/
	result,			/* contains the intersection of two cubes */
	mask_var;		/* mask one variable in a long int */

  previous_cube = list;

  end_input = cube + input_length;
  end_output = cube + total_length;

  for(; (present_cube_list = *previous_cube) != NULL ;)
   { present_cube = present_cube_list->cube;
   
/* If the two cubes do not intersect we simply go to the next cube in the
   list since there is nothing to sharp here.				*/

     if(intersect(cube,present_cube) == 0)
      { previous_cube = &(present_cube_list->next_cube);
	continue;
      }

     for(sharping_cube = cube ; sharping_cube < end_input ; sharping_cube++)

/*	we compute the intersection of the two cubes and see for which 
	variables it is smaller than the cube from which we want to remove the
	intersection 							*/

      { result = (*sharping_cube & *present_cube) ^ *present_cube;
        if(result != NULL)

/*	the intersection does not cover all the cube we will have to split it
	for all the variables for which we have X in the cube in the list and
	not X for the sharping cube					*/

         { for(mask_var = 3 ; mask_var != NULL ; mask_var = mask_var << 2)

            { if(result & mask_var)

/*	We split the cube in two by allocating a new cube and giving the value
	1 to a cube and 0 to the other for the input variable of the cube 
	which was x. One cube will be disjoint from the sharping cube and
	skipped in the list while the other will intersect and is smaller
	such that by repetitive splitting, we will end with a cube completely
	covered by the sharping cube; for this last cube the output common 
	with the sharping cube will be reset to 0 as a result of the sharp
	operation.							*/

               { temp_pointer = present_cube_list->next_cube;
                 present_cube_list->next_cube =
		 copy_and_alloc_cube_list(present_cube_list->cube);

	         *present_cube = ~(mask_var & *sharping_cube) & *present_cube;

		 present_cube = (present_cube - present_cube_list->cube)
					+ (present_cube_list->next_cube)->cube;

		 previous_cube = &(present_cube_list->next_cube);
		 present_cube_list = present_cube_list->next_cube;
		 present_cube_list->next_cube = temp_pointer;
                 *present_cube = ((~mask_var) | *sharping_cube) & *present_cube;
	       }
	    }
	 }
	present_cube++;
      }

/*	If all the output bits are reset to 0 as result of the sharp
	operation, the last cube becomes empty and is removed from the list.
	After we go to process the next cube in the list		*/

     result = NULL;
     for(; sharping_cube < end_output;)
      { *present_cube = *present_cube & (~ *sharping_cube);
        if(*present_cube) result = 1;
        sharping_cube++;
        present_cube++;
      }
     if(result == NULL)
      { temp_pointer = present_cube_list->next_cube;
        free_cube_list(present_cube_list);
        present_cube_list = temp_pointer;
	*previous_cube = temp_pointer;
      }
     else
      { previous_cube = &(present_cube_list->next_cube);
      }
   }
  if(*list == NULL) return(1);
  return(0);
}

b