/**CFile****************************************************************
FileName [mapperCanon.c]
PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
Synopsis [Generic technology mapping engine.]
Author [MVSIS Group]
Affiliation [UC Berkeley]
Date [Ver. 2.0. Started - June 1, 2004.]
Revision [$Id: mapperCanon.c,v 1.2 2005/01/23 06:59:42 alanmi Exp $]
***********************************************************************/
#include "mapperInt.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase );
static void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] );
////////////////////////////////////////////////////////////////////////
/// FUNCTION DEFINITIONS ///
////////////////////////////////////////////////////////////////////////
/**Function*************************************************************
Synopsis [Computes the N-canonical form of the Boolean function.]
Description [The N-canonical form is defined as the truth table with
the minimum integer value. This function exhaustively enumerates
through the complete set of 2^N phase assignments.]
SideEffects []
SeeAlso []
***********************************************************************/
int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
{
unsigned uTruthPerm[2];
int nMints, nPhases, m;
nPhases = 0;
nMints = (1 << nVarsReal);
if ( nVarsMax < 6 )
{
uTruthRes[0] = MAP_MASK(32);
for ( m = 0; m < nMints; m++ )
{
uTruthPerm[0] = Map_CanonComputePhase( uTruths, nVarsMax, uTruth[0], m );
if ( uTruthRes[0] > uTruthPerm[0] )
{
uTruthRes[0] = uTruthPerm[0];
nPhases = 0;
puPhases[nPhases++] = (unsigned char)m;
}
else if ( uTruthRes[0] == uTruthPerm[0] )
{
if ( nPhases < 4 ) // the max number of phases in Map_Super_t
puPhases[nPhases++] = (unsigned char)m;
}
}
uTruthRes[1] = uTruthRes[0];
}
else
{
uTruthRes[0] = MAP_MASK(32);
uTruthRes[1] = MAP_MASK(32);
for ( m = 0; m < nMints; m++ )
{
Map_CanonComputePhase6( uTruths, nVarsMax, uTruth, m, uTruthPerm );
if ( uTruthRes[1] > uTruthPerm[1] || (uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] > uTruthPerm[0]) )
{
uTruthRes[0] = uTruthPerm[0];
uTruthRes[1] = uTruthPerm[1];
nPhases = 0;
puPhases[nPhases++] = (unsigned char)m;
}
else if ( uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] == uTruthPerm[0] )
{
if ( nPhases < 4 ) // the max number of phases in Map_Super_t
puPhases[nPhases++] = (unsigned char)m;
}
}
}
assert( nPhases > 0 );
// printf( "%d ", nPhases );
return nPhases;
}
/**Function*************************************************************
Synopsis [Performs phase transformation for one function of less than 6 variables.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase )
{
int v, Shift;
for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
if ( uPhase & Shift )
uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift));
return uTruth;
}
/**Function*************************************************************
Synopsis [Performs phase transformation for one function of 6 variables.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] )
{
unsigned uTemp;
int v, Shift;
// initialize the result
uTruthRes[0] = uTruth[0];
uTruthRes[1] = uTruth[1];
if ( uPhase == 0 )
return;
// compute the phase
for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
if ( uPhase & Shift )
{
if ( Shift < 32 )
{
uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift));
uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift));
}
else
{
uTemp = uTruthRes[0];
uTruthRes[0] = uTruthRes[1];
uTruthRes[1] = uTemp;
}
}
}
/**Function*************************************************************
Synopsis [Computes the N-canonical form of the Boolean function.]
Description [The N-canonical form is defined as the truth table with
the minimum integer value. This function exhaustively enumerates
through the complete set of 2^N phase assignments.]
SideEffects []
SeeAlso []
***********************************************************************/
int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
{
unsigned uTruth0, uTruth1;
unsigned uCanon0, uCanon1, uCanonBest;
unsigned uPhaseBest = 16; // Suppress "might be used uninitialized" (asserts require < 16)
int i, Limit;
if ( nVarsMax == 6 )
return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
if ( nVarsReal < 5 )
{
// return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
uTruth0 = uTruth[0] & 0xFFFF;
assert( p->pCounters[uTruth0] > 0 );
uTruthRes[0] = (p->uCanons[uTruth0] << 16) | p->uCanons[uTruth0];
uTruthRes[1] = uTruthRes[0];
puPhases[0] = p->uPhases[uTruth0][0];
return 1;
}
assert( nVarsMax == 5 );
assert( nVarsReal == 5 );
uTruth0 = uTruth[0] & 0xFFFF;
uTruth1 = (uTruth[0] >> 16);
if ( uTruth1 == 0 )
{
uTruthRes[0] = p->uCanons[uTruth0];
uTruthRes[1] = uTruthRes[0];
Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
for ( i = 0; i < Limit; i++ )
puPhases[i] = p->uPhases[uTruth0][i];
return Limit;
}
else if ( uTruth0 == 0 )
{
uTruthRes[0] = p->uCanons[uTruth1];
uTruthRes[1] = uTruthRes[0];
Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
for ( i = 0; i < Limit; i++ )
{
puPhases[i] = p->uPhases[uTruth1][i];
puPhases[i] |= (1 << 4);
}
return Limit;
}
uCanon0 = p->uCanons[uTruth0];
uCanon1 = p->uCanons[uTruth1];
if ( uCanon0 >= uCanon1 ) // using nCanon1 as the main one
{
assert( p->pCounters[uTruth1] > 0 );
uCanonBest = 0xFFFFFFFF;
for ( i = 0; i < p->pCounters[uTruth1]; i++ )
{
uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 );
if ( uCanonBest > uCanon0 )
{
uCanonBest = uCanon0;
uPhaseBest = p->uPhases[uTruth1][i];
assert( uPhaseBest < 16 );
}
}
uTruthRes[0] = (uCanon1 << 16) | uCanonBest;
uTruthRes[1] = uTruthRes[0];
puPhases[0] = uPhaseBest;
return 1;
}
else if ( uCanon0 < uCanon1 )
{
assert( p->pCounters[uTruth0] > 0 );
uCanonBest = 0xFFFFFFFF;
for ( i = 0; i < p->pCounters[uTruth0]; i++ )
{
uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 );
if ( uCanonBest > uCanon1 )
{
uCanonBest = uCanon1;
uPhaseBest = p->uPhases[uTruth0][i];
assert( uPhaseBest < 16 );
}
}
uTruthRes[0] = (uCanon0 << 16) | uCanonBest;
uTruthRes[1] = uTruthRes[0];
puPhases[0] = uPhaseBest | (1 << 4);
return 1;
}
else
{
assert( 0 );
return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
}
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END