Made gate library package Mio independent of CUDD.

1 files changed, 333 insertions, 0 deletions

diff --git a/src/map/mio/mioSop.c b/src/map/mio/mioSop.c
new file mode 100644
index 00000000..46122121
--- /dev/null
+++ b/src/map/mio/mioSop.c
@@ -0,0 +1,333 @@
+/**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
+