/**CFile****************************************************************
FileName [cutMerge.c]
SystemName [ABC: Logic synthesis and verification system.]
PackageName [K-feasible cut computation package.]
Synopsis [Procedure to merge two cuts.]
Author [Alan Mishchenko]
Affiliation [UC Berkeley]
Date [Ver. 1.0. Started - June 20, 2005.]
Revision [$Id: cutMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
***********************************************************************/
#include "cutInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Merges two cuts.]
Description [This procedure works.]
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}};
Cut_Cut_t * pRes;
int * pRow;
int nLeaves0, nLeaves1, Limit;
int i, k, Count, nNodes;
assert( pCut0->nLeaves >= pCut1->nLeaves );
// the case of the largest cut sizes
Limit = p->pParams->nVarsMax;
nLeaves0 = pCut0->nLeaves;
nLeaves1 = pCut1->nLeaves;
if ( nLeaves0 == Limit && nLeaves1 == Limit )
{
for ( i = 0; i < nLeaves0; i++ )
if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
return NULL;
pRes = Cut_CutAlloc( p );
for ( i = 0; i < nLeaves0; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = nLeaves0;
return pRes;
}
// the case when one of the cuts is the largest
if ( nLeaves0 == Limit )
{
for ( i = 0; i < nLeaves1; i++ )
{
for ( k = nLeaves0 - 1; k >= 0; k-- )
if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
break;
if ( k == -1 ) // did not find
return NULL;
}
pRes = Cut_CutAlloc( p );
for ( i = 0; i < nLeaves0; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = nLeaves0;
return pRes;
}
// other cases
nNodes = nLeaves0;
for ( i = 0; i < nLeaves1; i++ )
{
for ( k = nLeaves0 - 1; k >= 0; k-- )
{
if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] )
continue;
if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] )
{
pRow = M[k+1];
if ( pRow[0] == 0 )
pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
else if ( pRow[1] == 0 )
pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
else if ( pRow[2] == 0 )
pRow[2] = pCut1->pLeaves[i];
else
assert( 0 );
if ( ++nNodes > Limit )
{
for ( i = 0; i <= nLeaves0; i++ )
M[i][0] = 0;
return NULL;
}
}
break;
}
if ( k == -1 )
{
pRow = M[0];
if ( pRow[0] == 0 )
pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
else if ( pRow[1] == 0 )
pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
else if ( pRow[2] == 0 )
pRow[2] = pCut1->pLeaves[i];
else
assert( 0 );
if ( ++nNodes > Limit )
{
for ( i = 0; i <= nLeaves0; i++ )
M[i][0] = 0;
return NULL;
}
continue;
}
}
pRes = Cut_CutAlloc( p );
for ( Count = 0, i = 0; i <= nLeaves0; i++ )
{
if ( i > 0 )
pRes->pLeaves[Count++] = pCut0->pLeaves[i-1];
pRow = M[i];
if ( pRow[0] )
{
pRes->pLeaves[Count++] = pRow[0];
if ( pRow[1] )
{
pRes->pLeaves[Count++] = pRow[1];
if ( pRow[2] )
pRes->pLeaves[Count++] = pRow[2];
}
pRow[0] = 0;
}
}
assert( Count == nNodes );
pRes->nLeaves = nNodes;
return pRes;
}
/**Function*************************************************************
Synopsis [Merges two cuts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
Cut_Cut_t * pRes;
int * pLeaves;
int Limit, nLeaves0, nLeaves1;
int i, k, c;
assert( pCut0->nLeaves >= pCut1->nLeaves );
// consider two cuts
nLeaves0 = pCut0->nLeaves;
nLeaves1 = pCut1->nLeaves;
// the case of the largest cut sizes
Limit = p->pParams->nVarsMax;
if ( nLeaves0 == Limit && nLeaves1 == Limit )
{
for ( i = 0; i < nLeaves0; i++ )
if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
return NULL;
pRes = Cut_CutAlloc( p );
for ( i = 0; i < nLeaves0; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = pCut0->nLeaves;
return pRes;
}
// the case when one of the cuts is the largest
if ( nLeaves0 == Limit )
{
for ( i = 0; i < nLeaves1; i++ )
{
for ( k = nLeaves0 - 1; k >= 0; k-- )
if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
break;
if ( k == -1 ) // did not find
return NULL;
}
pRes = Cut_CutAlloc( p );
for ( i = 0; i < nLeaves0; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = pCut0->nLeaves;
return pRes;
}
// prepare the cut
if ( p->pReady == NULL )
p->pReady = Cut_CutAlloc( p );
pLeaves = p->pReady->pLeaves;
// compare two cuts with different numbers
i = k = 0;
for ( c = 0; c < Limit; c++ )
{
if ( k == nLeaves1 )
{
if ( i == nLeaves0 )
{
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
pLeaves[c] = pCut0->pLeaves[i++];
continue;
}
if ( i == nLeaves0 )
{
if ( k == nLeaves1 )
{
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
pLeaves[c] = pCut1->pLeaves[k++];
continue;
}
if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
{
pLeaves[c] = pCut0->pLeaves[i++];
continue;
}
if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
{
pLeaves[c] = pCut1->pLeaves[k++];
continue;
}
pLeaves[c] = pCut0->pLeaves[i++];
k++;
}
if ( i < nLeaves0 || k < nLeaves1 )
return NULL;
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
/**Function*************************************************************
Synopsis [Merges two cuts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Cut_t * Cut_CutMergeTwo3( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
Cut_Cut_t * pRes;
int * pLeaves;
int Limit, nLeaves0, nLeaves1;
int i, k, c;
assert( pCut0->nLeaves >= pCut1->nLeaves );
// prepare the cut
if ( p->pReady == NULL )
p->pReady = Cut_CutAlloc( p );
pLeaves = p->pReady->pLeaves;
// consider two cuts
Limit = p->pParams->nVarsMax;
nLeaves0 = pCut0->nLeaves;
nLeaves1 = pCut1->nLeaves;
if ( nLeaves0 == Limit )
{ // the case when one of the cuts is the largest
if ( nLeaves1 == Limit )
{ // the case when both cuts are the largest
for ( i = 0; i < nLeaves0; i++ )
{
pLeaves[i] = pCut0->pLeaves[i];
if ( pLeaves[i] != pCut1->pLeaves[i] )
return NULL;
}
}
else
{
for ( i = k = 0; i < nLeaves0; i++ )
{
pLeaves[i] = pCut0->pLeaves[i];
if ( k == (int)nLeaves1 )
continue;
if ( pLeaves[i] < pCut1->pLeaves[k] )
continue;
if ( pLeaves[i] == pCut1->pLeaves[k++] )
continue;
return NULL;
}
if ( k < nLeaves1 )
return NULL;
}
p->pReady->nLeaves = nLeaves0;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
// compare two cuts with different numbers
i = k = 0;
for ( c = 0; c < Limit; c++ )
{
if ( k == nLeaves1 )
{
if ( i == nLeaves0 )
{
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
pLeaves[c] = pCut0->pLeaves[i++];
continue;
}
if ( i == nLeaves0 )
{
if ( k == nLeaves1 )
{
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
pLeaves[c] = pCut1->pLeaves[k++];
continue;
}
if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
{
pLeaves[c] = pCut0->pLeaves[i++];
continue;
}
if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
{
pLeaves[c] = pCut1->pLeaves[k++];
continue;
}
pLeaves[c] = pCut0->pLeaves[i++];
k++;
}
if ( i < nLeaves0 || k < nLeaves1 )
return NULL;
p->pReady->nLeaves = c;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
/**Function*************************************************************
Synopsis [Merges two cuts.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Cut_t * Cut_CutMergeTwo4( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
Cut_Cut_t * pRes;
int * pLeaves;
int i, k, min, NodeTemp, Limit, nTotal;
assert( pCut0->nLeaves >= pCut1->nLeaves );
// prepare the cut
if ( p->pReady == NULL )
p->pReady = Cut_CutAlloc( p );
pLeaves = p->pReady->pLeaves;
// consider two cuts
Limit = p->pParams->nVarsMax;
if ( pCut0->nLeaves == (unsigned)Limit )
{ // the case when one of the cuts is the largest
if ( pCut1->nLeaves == (unsigned)Limit )
{ // the case when both cuts are the largest
for ( i = 0; i < (int)pCut0->nLeaves; i++ )
{
pLeaves[i] = pCut0->pLeaves[i];
if ( pLeaves[i] != pCut1->pLeaves[i] )
return NULL;
}
}
else
{
for ( i = k = 0; i < (int)pCut0->nLeaves; i++ )
{
pLeaves[i] = pCut0->pLeaves[i];
if ( k == (int)pCut1->nLeaves )
continue;
if ( pLeaves[i] < pCut1->pLeaves[k] )
continue;
if ( pLeaves[i] == pCut1->pLeaves[k++] )
continue;
return NULL;
}
if ( k < (int)pCut1->nLeaves )
return NULL;
}
p->pReady->nLeaves = pCut0->nLeaves;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
// count the number of unique entries in pCut1
nTotal = pCut0->nLeaves;
for ( i = 0; i < (int)pCut1->nLeaves; i++ )
{
// try to find this entry among the leaves of pCut0
for ( k = 0; k < (int)pCut0->nLeaves; k++ )
if ( pCut1->pLeaves[i] == pCut0->pLeaves[k] )
break;
if ( k < (int)pCut0->nLeaves ) // found
continue;
// we found a new entry to add
if ( nTotal == Limit )
return NULL;
pLeaves[nTotal++] = pCut1->pLeaves[i];
}
// we know that the feasible cut exists
// add the starting entries
for ( k = 0; k < (int)pCut0->nLeaves; k++ )
pLeaves[k] = pCut0->pLeaves[k];
// selection-sort the entries
for ( i = 0; i < nTotal - 1; i++ )
{
min = i;
for ( k = i+1; k < nTotal; k++ )
if ( pLeaves[k] < pLeaves[min] )
min = k;
NodeTemp = pLeaves[i];
pLeaves[i] = pLeaves[min];
pLeaves[min] = NodeTemp;
}
p->pReady->nLeaves = nTotal;
pRes = p->pReady; p->pReady = NULL;
return pRes;
}
/**Function*************************************************************
Synopsis [Merges two cuts.]
Description [This procedure works.]
SideEffects []
SeeAlso []
***********************************************************************/
Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}};
Cut_Cut_t * pRes;
int * pRow;
unsigned uSign0, uSign1;
int i, k, nNodes, Count;
unsigned Limit = p->pParams->nVarsMax;
assert( pCut0->nLeaves >= pCut1->nLeaves );
// the case of the largest cut sizes
if ( pCut0->nLeaves == Limit && pCut1->nLeaves == Limit )
{
for ( i = 0; i < (int)pCut0->nLeaves; i++ )
if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] )
return NULL;
pRes = Cut_CutAlloc( p );
for ( i = 0; i < (int)pCut0->nLeaves; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = pCut0->nLeaves;
return pRes;
}
// the case when one of the cuts is the largest
if ( pCut0->nLeaves == Limit )
{
if ( !p->pParams->fTruth )
{
for ( i = 0; i < (int)pCut1->nLeaves; i++ )
{
for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
break;
if ( k == -1 ) // did not find
return NULL;
}
pRes = Cut_CutAlloc( p );
}
else
{
uSign1 = 0;
for ( i = 0; i < (int)pCut1->nLeaves; i++ )
{
for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] )
{
uSign1 |= (1 << i);
break;
}
if ( k == -1 ) // did not find
return NULL;
}
pRes = Cut_CutAlloc( p );
pRes->Num1 = uSign1;
}
for ( i = 0; i < (int)pCut0->nLeaves; i++ )
pRes->pLeaves[i] = pCut0->pLeaves[i];
pRes->nLeaves = pCut0->nLeaves;
return pRes;
}
// other cases
nNodes = pCut0->nLeaves;
for ( i = 0; i < (int)pCut1->nLeaves; i++ )
{
for ( k = pCut0->nLeaves - 1; k >= 0; k-- )
{
if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] )
continue;
if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] )
{
pRow = M[k+1];
if ( pRow[0] == 0 )
pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
else if ( pRow[1] == 0 )
pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
else if ( pRow[2] == 0 )
pRow[2] = pCut1->pLeaves[i];
else
assert( 0 );
if ( ++nNodes > (int)Limit )
{
for ( i = 0; i <= (int)pCut0->nLeaves; i++ )
M[i][0] = 0;
return NULL;
}
}
break;
}
if ( k == -1 )
{
pRow = M[0];
if ( pRow[0] == 0 )
pRow[0] = pCut1->pLeaves[i], pRow[1] = 0;
else if ( pRow[1] == 0 )
pRow[1] = pCut1->pLeaves[i], pRow[2] = 0;
else if ( pRow[2] == 0 )
pRow[2] = pCut1->pLeaves[i];
else
assert( 0 );
if ( ++nNodes > (int)Limit )
{
for ( i = 0; i <= (int)pCut0->nLeaves; i++ )
M[i][0] = 0;
return NULL;
}
continue;
}
}
pRes = Cut_CutAlloc( p );
if ( !p->pParams->fTruth )
{
for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ )
{
if ( i > 0 )
pRes->pLeaves[Count++] = pCut0->pLeaves[i-1];
pRow = M[i];
if ( pRow[0] )
{
pRes->pLeaves[Count++] = pRow[0];
if ( pRow[1] )
{
pRes->pLeaves[Count++] = pRow[1];
if ( pRow[2] )
pRes->pLeaves[Count++] = pRow[2];
}
pRow[0] = 0;
}
}
assert( Count == nNodes );
pRes->nLeaves = nNodes;
/*
// make sure that the cut is correct
{
for ( i = 1; i < (int)pRes->nLeaves; i++ )
if ( pRes->pLeaves[i-1] >= pRes->pLeaves[i] )
{
int v = 0;
}
}
*/
return pRes;
}
uSign0 = uSign1 = 0;
for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ )
{
if ( i > 0 )
{
uSign0 |= (1 << Count);
pRes->pLeaves[Count++] = pCut1->pLeaves[i-1];
}
pRow = M[i];
if ( pRow[0] )
{
uSign1 |= (1 << Count);
pRes->pLeaves[Count++] = pRow[0];
if ( pRow[1] )
{
uSign1 |= (1 << Count);
pRes->pLeaves[Count++] = pRow[1];
if ( pRow[2] )
{
uSign1 |= (1 << Count);
pRes->pLeaves[Count++] = pRow[2];
}
}
pRow[0] = 0;
}
}
assert( Count == nNodes );
pRes->nLeaves = nNodes;
pRes->Num1 = uSign1;
pRes->Num0 = uSign0;
return pRes;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END