Added command 'sparsify' to derive ISF from CSF.

2 files changed, 212 insertions, 0 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index d21c1887..e7271095 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -103,6 +103,7 @@ static int Abc_CommandSweep                  ( Abc_Frame_t * pAbc, int argc, cha
 static int Abc_CommandFastExtract            ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandEliminate              ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandDisjoint               ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandSparsify               ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandLutpack                ( Abc_Frame_t * pAbc, int argc, char ** argv );
 static int Abc_CommandLutmin                 ( Abc_Frame_t * pAbc, int argc, char ** argv );
 //static int Abc_CommandImfs                   ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -690,6 +691,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
     Cmd_CommandAdd( pAbc, "Synthesis",    "fx",            Abc_CommandFastExtract,      1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "eliminate",     Abc_CommandEliminate,        1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "dsd",           Abc_CommandDisjoint,         1 );
+    Cmd_CommandAdd( pAbc, "Synthesis",    "sparsify",      Abc_CommandSparsify,         1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "lutpack",       Abc_CommandLutpack,          1 );
     Cmd_CommandAdd( pAbc, "Synthesis",    "lutmin",        Abc_CommandLutmin,           1 );
 //    Cmd_CommandAdd( pAbc, "Synthesis",    "imfs",          Abc_CommandImfs,             1 );
@@ -4099,6 +4101,86 @@ usage:
   SeeAlso     []
 
 ***********************************************************************/
+int Abc_CommandSparsify( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+    extern Abc_Ntk_t * Abc_NtkSparsify( Abc_Ntk_t * pNtk, int nPerc, int fVerbose );
+    Abc_Ntk_t * pNtk = Abc_FrameReadNtk(pAbc), * pNtkNew;
+    int nPerc, fVerbose, c;
+    // set defaults
+    nPerc      = 10;
+    fVerbose   =  0;
+    Extra_UtilGetoptReset();
+    while ( ( c = Extra_UtilGetopt( argc, argv, "Nvh" ) ) != EOF )
+    {
+        switch ( c )
+        {
+            case 'N':
+                if ( globalUtilOptind >= argc )
+                {
+                    Abc_Print( -1, "Command line switch \"-N\" should be followed by an integer.\n" );
+                    goto usage;
+                }
+                nPerc = atoi(argv[globalUtilOptind]);
+                globalUtilOptind++;
+                if ( nPerc < 1 || nPerc > 100 )
+                    goto usage;
+                break;
+            case 'v':
+                fVerbose ^= 1;
+                break;
+            case 'h':
+                goto usage;
+                break;
+            default:
+                goto usage;
+        }
+    }
+
+    if ( pNtk == NULL )
+    {
+        Abc_Print( -1, "Empty network.\n" );
+        return 1;
+    }
+    if ( !Abc_NtkIsBddLogic( pNtk ) )
+    {
+        Abc_Print( -1, "This command is only applicable to logic BDD networks (run \"bdd\").\n" );
+        return 1;
+    }
+    if ( Abc_NtkCiNum(pNtk) > 16 )
+    {
+        Abc_Print( -1, "The number of primary inputs is more than 16.\n" );
+        return 1;
+    }
+    pNtkNew = Abc_NtkSparsify( pNtk, nPerc, fVerbose );
+    if ( pNtkNew == NULL )
+    {
+        Abc_Print( -1, "Command has failed.\n" );
+        return 1;
+    }
+    // replace the current network
+    Abc_FrameReplaceCurrentNetwork( pAbc, pNtkNew );
+    return 0;
+
+usage:
+    Abc_Print( -2, "usage: sparsify [-N num] [-vh]\n" );
+    Abc_Print( -2, "\t           creates incompletely-specified function\n" );
+    Abc_Print( -2, "\t-N <num> : the percentage of on-set and off-set minterms (1 <= num <= 100) [default = %d]\n", nPerc );
+    Abc_Print( -2, "\t-v       : prints verbose information [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h       : print the command usage\n");
+    return 1;
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
 int Abc_CommandLutpack( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     Abc_Ntk_t * pNtk = Abc_FrameReadNtk(pAbc);
diff --git a/src/base/abci/abcDsd.c b/src/base/abci/abcDsd.c
index 78b160e0..481639dd 100644
--- a/src/base/abci/abcDsd.c
+++ b/src/base/abci/abcDsd.c
@@ -554,6 +554,136 @@ int Abc_NodeFindMuxVar( DdManager * dd, DdNode * bFunc, int nVars )
 }
 
 
+/**Function********************************************************************
+
+  Synopsis    [Computes the positive polarty cube composed of the first vars in the array.]
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+******************************************************************************/
+DdNode * Extra_bddComputeSum( DdManager * dd, DdNode ** pbCubes, int nCubes )
+{
+    DdNode * bRes, * bTemp;
+    int i;
+    bRes = b0; Cudd_Ref( bRes );
+    for ( i = 0; i < nCubes; i++ )
+    {
+        bRes = Cudd_bddOr( dd, bTemp = bRes, pbCubes[i] );  Cudd_Ref( bRes );
+        Cudd_RecursiveDeref( dd, bTemp );
+    }
+    Cudd_Deref( bRes );
+    return bRes;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Derives network with the given percentage of on-set and off-set minterms.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+DdNode * Abc_NtkSparsifyInternalOne( DdManager * ddNew, DdNode * bFunc, int nFanins, int nPerc )
+{
+    int nSpace = (int)Cudd_CountMinterm( ddNew, bFunc, nFanins );
+    int i, nMints = Abc_MaxInt( 1, (int)(0.01 * nPerc * nSpace) );
+    DdNode ** pbMints = Cudd_bddPickArbitraryMinterms( ddNew, bFunc, ddNew->vars, nFanins, nMints );
+    DdNode * bRes;
+    for ( i = 0; i < nMints; i++ )
+        Cudd_Ref( pbMints[i] );
+    bRes = Extra_bddComputeSum( ddNew, pbMints, nMints ); Cudd_Ref( bRes );
+    for ( i = 0; i < nMints; i++ )
+        Cudd_RecursiveDeref( ddNew, pbMints[i] );
+    Cudd_Deref( bRes );
+    ABC_FREE( pbMints );
+    return bRes;
+}
+Abc_Ntk_t * Abc_NtkSparsifyInternal( Abc_Ntk_t * pNtk, int nPerc, int fVerbose )
+{
+    Abc_Ntk_t * pNtkNew;
+    Abc_Obj_t * pObj, * pDriver, * pFanin;
+    DdNode * bFunc, * bFuncOld;
+    DdManager * ddNew;
+    int i, k, c;
+    // start the new network
+    pNtkNew = Abc_NtkAlloc( ABC_NTK_LOGIC, ABC_FUNC_BDD, 1 );
+    Abc_NtkForEachCi( pNtk, pObj, i )
+        Abc_NtkDupObj( pNtkNew, pObj, 1 );
+    // duplicate the name and the spec
+    pNtkNew->pName = Extra_UtilStrsav(pNtk->pName);
+    pNtkNew->pSpec = Extra_UtilStrsav(pNtk->pSpec);
+    // make sure the new manager has enough inputs
+    ddNew = (DdManager *)pNtkNew->pManFunc;
+    Cudd_bddIthVar( ddNew, Abc_NtkCiNum(pNtk)-1 );
+    // go through the outputs
+    Abc_NtkForEachCo( pNtk, pObj, i )
+    {
+        pDriver = Abc_ObjFanin0( pObj );
+        if ( Abc_ObjIsCi(pDriver) )
+        {
+            Abc_NtkDupObj( pNtkNew, pObj, 0 );
+            Abc_ObjAddFanin( pObj->pCopy, Abc_ObjNotCond(pDriver->pCopy, Abc_ObjFaninC0(pObj)) );
+            Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_on" );
+
+            Abc_NtkDupObj( pNtkNew, pObj, 0 );
+            Abc_ObjAddFanin( pObj->pCopy, Abc_ObjNotCond(pDriver->pCopy, !Abc_ObjFaninC0(pObj)) );
+            Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_off" );
+            continue;
+        }
+        if ( Abc_ObjFaninNum(pDriver) == 0 )
+        {
+            Abc_NtkDupObj( pNtkNew, pObj, 0 );
+            Abc_ObjAddFanin( pObj->pCopy, Abc_ObjFaninC0(pObj) ? Abc_NtkCreateNodeConst0(pNtkNew) : Abc_NtkCreateNodeConst1(pNtkNew) );
+            Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_on" );
+
+            Abc_NtkDupObj( pNtkNew, pObj, 0 );
+            Abc_ObjAddFanin( pObj->pCopy, Abc_ObjFaninC0(pObj) ? Abc_NtkCreateNodeConst1(pNtkNew) : Abc_NtkCreateNodeConst0(pNtkNew) );
+            Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), "_off" );
+            continue;
+        }
+        assert( Abc_ObjFaninNum(pObj) > 0 );
+        // onset/offset
+        for ( c = 0; c < 2; c++ )
+        {
+            Abc_NtkDupObj( pNtkNew, pDriver, 0 );
+            Abc_ObjForEachFanin( pDriver, pFanin, k )
+                Abc_ObjAddFanin( pDriver->pCopy, pFanin->pCopy );
+            bFuncOld = Cudd_NotCond( (DdNode *)pDriver->pCopy->pData, c );
+            bFunc = Abc_NtkSparsifyInternalOne( ddNew, bFuncOld, Abc_ObjFaninNum(pDriver), nPerc );  Cudd_Ref( bFunc );
+            Cudd_RecursiveDeref( ddNew, bFuncOld );
+            pDriver->pCopy->pData = bFunc;
+            Abc_NtkDupObj( pNtkNew, pObj, 0 );
+            Abc_ObjAddFanin( pObj->pCopy, pDriver->pCopy );
+            Abc_ObjAssignName( pObj->pCopy, Abc_ObjName(pObj), c ? "_off" : "_on" );
+        }
+    }
+    Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );
+    return pNtkNew;
+}
+Abc_Ntk_t * Abc_NtkSparsify( Abc_Ntk_t * pNtk, int nPerc, int fVerbose )
+{
+    Abc_Ntk_t * pNtkNew;
+    assert( Abc_NtkIsComb(pNtk) );
+    assert( Abc_NtkIsBddLogic(pNtk) );
+    pNtkNew = Abc_NtkSparsifyInternal( pNtk, nPerc, fVerbose );
+    if ( pNtkNew == NULL )
+        return NULL;
+    if ( !Abc_NtkCheck( pNtkNew ) )
+    {
+        printf( "Abc_NtkSparsify: The network check has failed.\n" );
+        Abc_NtkDelete( pNtkNew );
+        return NULL;
+    }
+    return pNtkNew;
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////