| /**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 |
| |
