/*********************************************************************
NAME
prime_implicants_by_recursive_partitioning
PURPOSE
Allocate some working vectors and call the recursive prime
implicants function to generate the prime implicants of
a boolean function. In fact this function is only an entry
for the recursive process performed by the recursive function
that will be called.
SYNOPSIS
struct node *prime_implicants_by_recursive_partitioning(list)
struct node *list;
DESCRIPTION
We allocate a vector that contains all the input variables. Each
time we partition the function along one input variable, we place
this variable at the end of the vector and decrement the number of
input of the partitioned function such that this input variable
is no longer available to the partitioned function. So this function
initializes the recursive process by allocating a vector containing
all the input variables before calling the recursive function to
generate the prime implicants.
COORDINATES
McGill University Electrical Engineering VLSI lab MONTREAL CANADA
14 juillet 1984
AUTHOR
Michel DAGENAIS
***********************************************************************/
#include "cubes.h"
#include <malloc.h>
struct node
*common_list, /* list when converting a tree in a list */
*dont_care_list, /* list to put the dont care cover */
**point_to_merge, /* pointer to node to merge */
*node_to_merge; /* node that we currently try to merge */
struct binary
*common_binary; /* branch to merge with */
int
*nb0_at_input, /* number of cubes with 0 for each input */
*nb1_at_input, /* number of cubes with 1 for each input */
*nbx_at_input, /* number of cubes with x for each input */
*unused_input, /* input var not taken by partitions */
nbinput; /* number of input var not taken for partition*/
struct node
*prime_implicants_by_recursive_partitioning(list)
struct node *list;
{
struct branch branch; /* branch sent to the recursive function */
struct node
*temp_node, /* node in the list */
**prev_list; /* pointer to node in the list */
/* We first screen the list to see if any node has an output part
composed exclusively of 0; in such a case, this node is removed
from the list. */
prev_list = &list;
for(; (temp_node = *prev_list) != NULL ;)
{ if(empty_output(temp_node->cube))
{ *prev_list = temp_node->next_node;
free_node(temp_node);
}
else prev_list = &(temp_node->next_node);
}
/* we first allocate integer vectors to contain the list of input var,
and for each passible code (0, 1 or x) a working vector used in
the input var selection for partitioning. */
unused_input = (int *)calloc((unsigned)input_number,sizeof(int));
nb0_at_input = (int *)calloc((unsigned)input_number,sizeof(int));
nb1_at_input = (int *)calloc((unsigned)input_number,sizeof(int));
nbx_at_input = (int *)calloc((unsigned)input_number,sizeof(int));
if(unused_input == NULL || nb0_at_input == NULL || nb1_at_input == NULL ||
nbx_at_input == NULL) fatal_system_error("unable to alloc vector for inputs");
/* we initialize unused_input with the list of input var which is
0 to (input_number - 1) when we start here with the unpartitioned
function. nbinput is initialized to input_number the number of input
variables available in the vector unused input before we start the
partitioning. */
for(nbinput = 0 ; nbinput < input_number ; nbinput++)
{ unused_input[nbinput] = nbinput;
}
dont_care_list = NULL;
/* we now call the recursive function that will return the list of prime
implicants of the function described by the list of disjoint cubes sent */
branch.status = LEAF;
branch._.leaf = list;
recursive_prime_implicants(&branch,1);
/* the nodes in the dont care cover were kept in a different list, we will
return them in the same list as the prime implicants. */
list = merge_node_lists(dont_care_list,branch._.leaf);
/* we now simply free the vectors allocated, the job is done */
flush_binary();
free((char *)unused_input);
free((char *)nb0_at_input);
free((char *)nb1_at_input);
free((char *)nbx_at_input);
return(list);
}
/**********************************************************************
NAME
recursive_prime_implicants
PURPOSE
Generate the list of prime implicants of a boolean function from
a list of disjoint cubes. These prime implicants will be linked
together in a covering graph.
SYNOPSIS
recursive_prime_implicants(branch,return_a_list)
struct branch *branch;
int return_a_list;
DESCRIPTION
This function generates the prime implicants using a recursive
partitioning up to unate functions. The partitions are then merged
together and the new implicants formed are checked for absorbtion.
Each partition is performed on an input variable, all the cubes
with a 0 go on one side, all the cubes with a 1 on the other and
the cubes with a x go on both sides. We then make both sides prime
and we finally merge both together along the partitioning variable.
The parameter return_a_list tells that the 0 side of the tree should
be returned in a list instead of a subtree.
COORDINATES
McGill University Electrical Engineering VLSI lab MONTREAL CANADA
13 july 1984
AUTHOR
Michel DAGENAIS
************************************************************************/
recursive_prime_implicants(branch,return_a_list)
struct branch *branch;
int return_a_list;
{
int
current_code, /* code for the node at current_input */
current_input; /* input variable selected */
struct node
*temp_node, /* temp node to place in the list 1 or 0 */
*start_list1, /* list of nodes with 1 in current input */
*start_list0, /* list of nodes with a 0 in current input */
*next_node, /* next node in the list to partition */
*list; /* list of nodes received */
struct binary
*temp_binary; /* new node for this partition */
/* we select the input for which we will partition. A negative value tells
that only one cube is left in the list and that no partitioning is needed
any more; in this case the only cube in this partition is necessarily prime
and the function terminates here. */
current_input = select_input(&(branch->_.leaf));
if(current_input < 0) return;
list = branch->_.leaf;
/* we need to partition; the input is already selected, all the cubes with
a 0 for this input will be put in start_list0, all the cubes with a 1
in start_list1. The cubes with a x for this input will be splitted in
two cube, one with a 0 to put in start_list 0 and one with a 1 to put
in start_list1. */
define_current_var(current_input);
start_list0 = NULL;
start_list1 = NULL;
for(temp_node = list ; temp_node != NULL ; temp_node = next_node)
{ next_node = temp_node->next_node;
current_code = extract_current_var(temp_node->cube);
switch(current_code)
{ case _1_ :
/* we have a 1 for the selected input place the cube in start_list1 */
temp_node->next_node = start_list1;
start_list1 = temp_node;
break;
case _0_ :
/* we have a 0 for the selected input place the cube in start_list0 */
temp_node->next_node = start_list0;
start_list0 = temp_node;
break;
case _X_ :
/* we have a x split the cube and place it in both lists */
temp_node->next_node = start_list0;
start_list0 = temp_node;
temp_node = copy_and_alloc_node(temp_node->cube);
temp_node->next_node = start_list1;
start_list1 = temp_node;
/* place respectively 0 and 1 in the splitted cubes for current_input*/
set_current_var(start_list0->cube,mask10);
set_current_var(start_list1->cube,mask01);
break;
}
}
/* for each partition we generate the prime implicants by calling the
recursive function. */
temp_binary = alloc_binary();
temp_binary->var = current_input;
temp_binary->is0.status = LEAF;
temp_binary->is0._.leaf = start_list0;
temp_binary->is1.status = LEAF;
temp_binary->is1._.leaf = start_list1;
if(return_a_list) recursive_prime_implicants(&(temp_binary->is0),1);
else recursive_prime_implicants(&(temp_binary->is0),0);
recursive_prime_implicants(&(temp_binary->is1),0);
nbinput++;
define_current_var(current_input);
/* we have two lists of cubes prime in their respective partition, when we will
put the list together they will still be prime except maybe for the input
var along which they were partition. For this reason, we will try the star
product between each cube of a partition with each cube of the other
partition. The new cubes formed may absorb the cubes used for their formation
and the new cubes must also be checked for absorbtion with the other new
cubes. */
common_binary = temp_binary;
scan_node_to_merge(&(temp_binary->is0));
/* if we have to return a list, we simply merge the subtrees in one list */
if(return_a_list)
{ common_list = merge_node_lists(temp_binary->isx,temp_binary->is0._.leaf);
put_in_common_list(&(temp_binary->is1));
free_binary(temp_binary);
branch->_.leaf = common_list;
if(VERBOSIS)
{ sprintf(error_buffer,"leftmost subtree merged at level %d (%d)",
input_number - nbinput,nb_alloc_nodes - 1);
send_user_message(error_buffer);
}
return;
}
/* both subtrees are empty, we can then simply return a list and release the
binary structure that holds the subtrees. */
if(temp_binary->is0.status == 0 && temp_binary->is1.status == 0)
{ branch->status = LEAF;
branch->_.leaf = temp_binary->isx;
free_binary(temp_binary);
}
else
{ branch->status = SUBTREE;
branch->_.subtree = temp_binary;
}
if(VERY_VERBOSIS)
{ sprintf(error_buffer,"subtree merged at level %d (%d)",
input_number - nbinput,nb_alloc_nodes - 1);
send_user_message(error_buffer);
}
}
/**********************************************************************
NAME
scan_node_to_merge
PURPOSE
Find all the nodes in a branch and try to merge them with the rest
of the nodes that are in the other side of the common branch.
SYNOPSIS
scan_node_to_merge(branch)
struct branch *branch;
DESCRIPTION
When we start the merging at a binary node, we scan to merge all the
nodes in the 0 branch and we try to merge them with the nodes in the
1 branch. The 1 branch for this purpose can be accessed from the common
binary. When the branch points to a leaf, we take all the nodes in the
leaf; when it points to a subtree, we take all the nodes in the isx
list and scan recursively the 0 and 1 branches.
COORDINATES
McGill University Electrical Engineering VLSI lab MONTREAL CANADA
8 august 1984
AUTHOR
Michel DAGENAIS
************************************************************************/
scan_node_to_merge(branch)
struct branch *branch;
{
struct binary *temp_binary; /* temp pointer to a subtree */
int status;
status = branch->status;
if(status == 0) return;
if(status & SUBTREE)
{ temp_binary = branch->_.subtree;
scan_node_to_merge(&(temp_binary->is0));
scan_node_to_merge(&(temp_binary->is1));
point_to_merge = &(temp_binary->isx);
}
else point_to_merge = &(branch->_.leaf);
/* all the nodes in the list to merge will be star produc with all the other
nodes in the 1 branch of the common_binary. When no merge covers the node
to merge we take the next node in the list. If the node is covered, the
point_to_merge is already updated to point to the next node */
for(; (node_to_merge = *point_to_merge) != NULL ;)
{ if(merge_with_rest(&(common_binary->is1)) == 0)
point_to_merge = &(node_to_merge->next_node);
}
/* We look if this branch of the tree is not empty in which case we cut
it to help restrict the search further on. */
if(status & SUBTREE)
{ if(temp_binary->is0.status == 0 && temp_binary->is1.status == 0)
{ if(temp_binary->isx == NULL) branch->status = 0;
else
{ branch->status = LEAF;
branch->_.leaf = temp_binary->isx;
}
free_binary(temp_binary);
}
}
else if(branch->_.leaf == NULL) branch->status = 0;
}
/***********************************************************************
NAME
merge_with_rest
PURPOSE
We scan the specified branch to find some nodes that might merge
with the node_to_merge. The candidates are merged and placed in the
graph.
SYNOPSIS
int merge_with_rest(branch)
struct branch *branch;
DESCRIPTION
If the branch points to a leaf, we try to merge the nodes in it with
the current node to merge. If it points to a subtree, we try to merge
the nodes in the isx list and recursively merge with the 0 and 1
branches. When a merge is successfull, the new node is placed in the
graph and we check that it is not absorbed by the nodes already in
the common_binary in the isx list where the new nodes merged are put.
When the node to merge is absorbed, we remove it from the list to
merge, update the pointer to merge and return 1; when the node to merge
is absorbed we know that no other merge will give a bigger cube and
it is why we stop the merging for that node. Otherwise, we return 0.
COORDINATES
McGill University Electrical Engineering VLSI lab MONTREAL CANADA
8 august 1984
AUTHOR
Michel DAGENAIS
************************************************************************/
int merge_with_rest(branch)
struct branch *branch;
{
struct node
*temp_node, /* temp pointer in the list to merge */
**point_temp_node, /* pointer to temp_node */
*temp_nodex, /* temp pointer in the list to absorb */
**point_to_nodex, /* pointer to temp_nodex */
*new_node; /* pointer to the result of the merge and link*/
struct binary *temp_binary; /* pointer to the subtree of branch */
int
status, /* temp storage for the branch status */
code; /* value of the var for the node to merge */
status = branch->status;
if(status == 0) return(0);
if(status & SUBTREE)
{ temp_binary = branch->_.subtree;
point_temp_node = &(temp_binary->isx);
}
else point_temp_node = &(branch->_.leaf);
/* we will try to merge the node with all the nodes in the list */
for(; (temp_node = *point_temp_node) != NULL ;)
{
#ifdef DEBUG
foutput_cube(stdout,node_to_merge->cube);
foutput_cube(stdout,temp_node->cube);
printf("Above two cubes to merge");
#endif
if(star_product(node_to_merge->cube,temp_node->cube,spare_node->cube))
{ new_node = merge_and_link(point_to_merge,point_temp_node,spare_node);
#ifdef DEBUG
printf(", merge successfull gives:\n");
foutput_cube(stdout,new_node->cube);
#endif
/* a merge occured, we will see if the new node is absorbed by nodes already
merged and put in the listx of the common binary. */
point_to_nodex = &(common_binary->isx);
for(; (temp_nodex = *point_to_nodex) != NULL ;)
{ code = absorb(new_node->cube,temp_nodex->cube);
#ifdef DEBUG
printf("Absorbtion code: %d \n",code);
#endif
switch(code)
{ case 0 :
absorb_and_unlink(temp_nodex,&new_node);
break;
case 1 :
absorb_and_unlink(new_node,point_to_nodex);
break;
case 2 :
absorb_and_unlink(temp_nodex,&new_node);
break;
}
if(new_node == NULL) break;
/* if the node in the listx was not absorbed, we update the point_to_nodex */
if(temp_nodex == *point_to_nodex)
point_to_nodex = &(temp_nodex->next_node);
}
/* the new node was not absorbed, it will be put in the listx. */
if(new_node != NULL)
{ new_node->next_node = common_binary->isx;
common_binary->isx = new_node;
}
/* the node to merge was absorbed, it is the best possible merge and we stop */
if(*point_to_merge != node_to_merge) return(1);
}
if(temp_node == *point_temp_node)point_temp_node = &(temp_node->next_node);
}
/* We will now merge recursively with the subtrees of this branch. If the
node to merge has a 0 for the variable of this binary it can only merge
with the subtree 0 and the same if it has 1 with the subtree 1; this way
important savings on useless attempt to star product, are achieved. */
if(status & SUBTREE)
{ code = extract_var(node_to_merge->cube,temp_binary->var);
switch (code)
{ case _0_ :
if(merge_with_rest(&(temp_binary->is0))) return(1);
break;
case _1_ :
if(merge_with_rest(&(temp_binary->is1))) return(1);
break;
case _X_ :
if(merge_with_rest(&(temp_binary->is0))) return(1);
if(merge_with_rest(&(temp_binary->is1))) return(1);
break;
}
/* all the merging are done, we will now look if this branch is not empty
in which case we will cut it from the tree. */
if(temp_binary->is0.status == 0 && temp_binary->is1.status == 0)
{ if(temp_binary->isx == NULL) branch->status = 0;
else
{ branch->status = LEAF;
branch->_.leaf = temp_binary->isx;
}
free_binary(temp_binary);
}
}
else if(branch->_.leaf == NULL) branch->status = 0;
return(0);
}
��������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������