| /**CFile**************************************************************** |
| |
| FileName [mioSop.c] |
| |
| PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] |
| |
| Synopsis [Derives SOP from Boolean expression.] |
| |
| Author [MVSIS Group] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - September 8, 2003.] |
| |
| Revision [$Id: mioSop.c,v 1.4 2004/06/28 14:20:25 alanmi Exp $] |
| |
| ***********************************************************************/ |
| |
| #include "mioInt.h" |
| #include "exp.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| static inline unsigned Mio_CubeVar0( int v ) { return (1<< (v<<1) ); } |
| static inline unsigned Mio_CubeVar1( int v ) { return (1<<((v<<1)+1)); } |
| static inline int Mio_CubeHasVar0( unsigned x, int v ) { return (x & Mio_CubeVar0(v)) > 0; } |
| static inline int Mio_CubeHasVar1( unsigned x, int v ) { return (x & Mio_CubeVar1(v)) > 0; } |
| static inline int Mio_CubeEmpty( unsigned x ) { return (x & (x>>1) & 0x55555555) != 0; } |
| static inline unsigned Mio_CubeAnd( unsigned x, unsigned y ) { return x | y; } |
| static inline int Mio_CubeContains( unsigned x, unsigned y ) { return (x | y) == y; } // x contains y |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Push while performing SCC.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Mio_SopPushSCC( Vec_Int_t * p, unsigned c ) |
| { |
| unsigned Entry; |
| int i, k = 0; |
| Vec_IntForEachEntry( p, Entry, i ) |
| { |
| if ( Mio_CubeContains( Entry, c ) ) // Entry contains c |
| { |
| assert( i == k ); |
| return; |
| } |
| if ( Mio_CubeContains( c, Entry ) ) // c contains Entry |
| continue; |
| Vec_IntWriteEntry( p, k++, Entry ); |
| } |
| Vec_IntShrink( p, k ); |
| Vec_IntPush( p, c ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Make the OR of two covers.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopCoverOr( Vec_Int_t * p, Vec_Int_t * q ) |
| { |
| Vec_Int_t * r; |
| unsigned Entry; |
| int i; |
| r = Vec_IntAlloc( Vec_IntSize(p) + Vec_IntSize(q) ); |
| Vec_IntForEachEntry( p, Entry, i ) |
| Vec_IntPush( r, Entry ); |
| Vec_IntForEachEntry( q, Entry, i ) |
| Mio_SopPushSCC( r, Entry ); |
| return r; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Make the AND of two covers.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopCoverAnd( Vec_Int_t * p, Vec_Int_t * q ) |
| { |
| Vec_Int_t * r; |
| unsigned EntryP, EntryQ; |
| int i, k; |
| r = Vec_IntAlloc( Vec_IntSize(p) * Vec_IntSize(q) ); |
| Vec_IntForEachEntry( p, EntryP, i ) |
| Vec_IntForEachEntry( q, EntryQ, k ) |
| if ( !Mio_CubeEmpty( Mio_CubeAnd(EntryP, EntryQ) ) ) |
| Mio_SopPushSCC( r, Mio_CubeAnd(EntryP, EntryQ) ); |
| return r; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create negative literal.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopVar0( int i ) |
| { |
| Vec_Int_t * vSop; |
| vSop = Vec_IntAlloc( 1 ); |
| Vec_IntPush( vSop, Mio_CubeVar0(i) ); |
| return vSop; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create positive literal.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopVar1( int i ) |
| { |
| Vec_Int_t * vSop; |
| vSop = Vec_IntAlloc( 1 ); |
| Vec_IntPush( vSop, Mio_CubeVar1(i) ); |
| return vSop; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create constant 0 literal.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopConst0() |
| { |
| Vec_Int_t * vSop; |
| vSop = Vec_IntAlloc( 1 ); |
| return vSop; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Create constant 1 literal.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Vec_Int_t * Mio_SopConst1() |
| { |
| Vec_Int_t * vSop; |
| vSop = Vec_IntAlloc( 1 ); |
| Vec_IntPush( vSop, 0 ); |
| return vSop; |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives SOP representation as the char string.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| char * Mio_SopDeriveFromArray( Vec_Int_t * vSop, int nVars, Vec_Str_t * vStr, int fPolarity ) |
| { |
| unsigned Entry; |
| int i, k; |
| Vec_StrClear( vStr ); |
| if ( Vec_IntSize(vSop) == 0 ) |
| { |
| Vec_StrPush( vStr, ' ' ); |
| Vec_StrPush( vStr, (char)('1'-fPolarity) ); |
| Vec_StrPush( vStr, '\n' ); |
| Vec_StrPush( vStr, '\0' ); |
| return Vec_StrArray( vStr ); |
| } |
| if ( Vec_IntSize(vSop) == 1 && Vec_IntEntry(vSop, 0) == 0 ) |
| { |
| Vec_StrPush( vStr, ' ' ); |
| Vec_StrPush( vStr, (char)('0'+fPolarity) ); |
| Vec_StrPush( vStr, '\n' ); |
| Vec_StrPush( vStr, '\0' ); |
| return Vec_StrArray( vStr ); |
| } |
| // create cubes |
| Vec_IntForEachEntry( vSop, Entry, i ) |
| { |
| for ( k = 0; k < nVars; k++ ) |
| { |
| if ( Mio_CubeHasVar0( Entry, k ) ) |
| Vec_StrPush( vStr, '0' ); |
| else if ( Mio_CubeHasVar1( Entry, k ) ) |
| Vec_StrPush( vStr, '1' ); |
| else |
| Vec_StrPush( vStr, '-' ); |
| } |
| Vec_StrPush( vStr, ' ' ); |
| Vec_StrPush( vStr, (char)('0'+fPolarity) ); |
| Vec_StrPush( vStr, '\n' ); |
| } |
| Vec_StrPush( vStr, '\0' ); |
| return Vec_StrArray( vStr ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [Derives SOP representation.] |
| |
| Description [The SOP is guaranteed to be SCC-free but not minimal.] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| char * Mio_LibDeriveSop( int nVars, Vec_Int_t * vExpr, Vec_Str_t * vStr ) |
| { |
| Vec_Int_t * vSop; |
| Vec_Ptr_t * vSops0, * vSops1, * vTemp; |
| int i, Index0, Index1, fCompl0, fCompl1; |
| Vec_StrClear( vStr ); |
| if ( Exp_IsConst0(vExpr) ) |
| { |
| Vec_StrPrintStr( vStr, " 0\n" ); |
| Vec_StrPush( vStr, '\0' ); |
| return Vec_StrArray( vStr ); |
| } |
| if ( Exp_IsConst1(vExpr) ) |
| { |
| Vec_StrPrintStr( vStr, " 1\n" ); |
| Vec_StrPush( vStr, '\0' ); |
| return Vec_StrArray( vStr ); |
| } |
| if ( Exp_IsLit(vExpr) ) |
| { |
| for ( i = 0; i < nVars; i++ ) |
| Vec_StrPush( vStr, '-' ); |
| Vec_StrPrintStr( vStr, " 1\n" ); |
| Vec_StrPush( vStr, '\0' ); |
| assert( (Vec_IntEntry(vExpr,0) >> 1) < nVars ); |
| Vec_StrWriteEntry( vStr, Vec_IntEntry(vExpr,0) >> 1, (char)('1' - (Vec_IntEntry(vExpr,0) & 1)) ); |
| return Vec_StrArray( vStr ); |
| } |
| vSops0 = Vec_PtrAlloc( nVars + Exp_NodeNum(vExpr) ); |
| vSops1 = Vec_PtrAlloc( nVars + Exp_NodeNum(vExpr) ); |
| for ( i = 0; i < nVars; i++ ) |
| { |
| Vec_PtrPush( vSops0, Mio_SopVar0(i) ); |
| Vec_PtrPush( vSops1, Mio_SopVar1(i) ); |
| } |
| for ( i = 0; i < Exp_NodeNum(vExpr); i++ ) |
| { |
| Index0 = Vec_IntEntry( vExpr, 2*i+0 ) >> 1; |
| Index1 = Vec_IntEntry( vExpr, 2*i+1 ) >> 1; |
| fCompl0 = Vec_IntEntry( vExpr, 2*i+0 ) & 1; |
| fCompl1 = Vec_IntEntry( vExpr, 2*i+1 ) & 1; |
| // positive polarity |
| vSop = Mio_SopCoverAnd( fCompl0 ? (Vec_Int_t *)Vec_PtrEntry(vSops0, Index0) : (Vec_Int_t *)Vec_PtrEntry(vSops1, Index0), |
| fCompl1 ? (Vec_Int_t *)Vec_PtrEntry(vSops0, Index1) : (Vec_Int_t *)Vec_PtrEntry(vSops1, Index1) ); |
| Vec_PtrPush( vSops1, vSop ); |
| // negative polarity |
| vSop = Mio_SopCoverOr( fCompl0 ? (Vec_Int_t *)Vec_PtrEntry(vSops1, Index0) : (Vec_Int_t *)Vec_PtrEntry(vSops0, Index0), |
| fCompl1 ? (Vec_Int_t *)Vec_PtrEntry(vSops1, Index1) : (Vec_Int_t *)Vec_PtrEntry(vSops0, Index1) ); |
| Vec_PtrPush( vSops0, vSop ); |
| } |
| // complement |
| if ( Vec_IntEntryLast(vExpr) & 1 ) |
| { |
| vTemp = vSops0; |
| vSops0 = vSops1; |
| vSops1 = vTemp; |
| } |
| // select the best polarity |
| if ( Vec_IntSize( (Vec_Int_t *)Vec_PtrEntryLast(vSops0) ) < Vec_IntSize( (Vec_Int_t *)Vec_PtrEntryLast(vSops1) ) ) |
| vSop = (Vec_Int_t *)Vec_PtrEntryLast(vSops0); |
| else |
| vSop = (Vec_Int_t *)Vec_PtrEntryLast(vSops1); |
| // convert positive polarity into SOP |
| Mio_SopDeriveFromArray( vSop, nVars, vStr, (vSop == Vec_PtrEntryLast(vSops1)) ); |
| Vec_VecFree( (Vec_Vec_t *)vSops0 ); |
| Vec_VecFree( (Vec_Vec_t *)vSops1 ); |
| return Vec_StrArray( vStr ); |
| } |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
