Updates to arithmetic verification.

8 files changed, 88 insertions, 55 deletions

diff --git a/abclib.dsp b/abclib.dsp
index f2dbc1b3..7d1c1551 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -5355,6 +5355,10 @@ SOURCE=.\src\proof\acec\acecCore.c
 # End Source File
 # Begin Source File
 
+SOURCE=.\src\proof\acec\acecCover.c
+# End Source File
+# Begin Source File
+
 SOURCE=.\src\proof\acec\acecFadds.c
 # End Source File
 # Begin Source File
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 4dc50ed2..31f3a275 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -40126,7 +40126,7 @@ usage:
 int Abc_CommandAbc9Polyn( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
     Vec_Int_t * vOrder = NULL;
-    int c, fSimple = 0, fSigned = 0, fVerbose = 0, fVeryVerbose = 0;
+    int c, fSimple = 1, fSigned = 0, fVerbose = 0, fVeryVerbose = 0;
     Extra_UtilGetoptReset();
     while ( ( c = Extra_UtilGetopt( argc, argv, "asvwh" ) ) != EOF )
     {
diff --git a/src/base/wlc/wlc.h b/src/base/wlc/wlc.h
index 5791731e..bb5c4bfe 100644
--- a/src/base/wlc/wlc.h
+++ b/src/base/wlc/wlc.h
@@ -259,7 +259,7 @@ extern Vec_Int_t *    Wlc_NtkFindUifableMultiplierPairs( Wlc_Ntk_t * p );
 extern Wlc_Ntk_t *    Wlc_NtkAbstractNodes( Wlc_Ntk_t * pNtk, Vec_Int_t * vNodes );
 extern Wlc_Ntk_t *    Wlc_NtkUifNodePairs( Wlc_Ntk_t * pNtk, Vec_Int_t * vPairs );
 /*=== wlcBlast.c ========================================================*/
-extern Gia_Man_t *    Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nRange, int fGiaSimple, int fAddOutputs );
+extern Gia_Man_t *    Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nRange, int fGiaSimple, int fAddOutputs, int fBooth );
 /*=== wlcCom.c ========================================================*/
 extern void           Wlc_SetNtk( Abc_Frame_t * pAbc, Wlc_Ntk_t * pNtk );
 /*=== wlcNtk.c ========================================================*/
diff --git a/src/base/wlc/wlcBlast.c b/src/base/wlc/wlcBlast.c
index 97b32144..c86c7cf0 100644
--- a/src/base/wlc/wlcBlast.c
+++ b/src/base/wlc/wlcBlast.c
@@ -635,7 +635,7 @@ void Wlc_IntInsert( Vec_Int_t * vProd, Vec_Int_t * vLevel, int Node, int Level )
     Vec_IntInsert( vProd,  i + 1, Node  );
     Vec_IntInsert( vLevel, i + 1, Level );
 }
-void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vLevels, Vec_Int_t * vRes, int nSizeMax )
+void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vLevels, Vec_Int_t * vRes )
 {
     Vec_Int_t * vLevel, * vProd;
     int i, NodeS, NodeC, LevelS, LevelC, Node1, Node2, Node3, Level1, Level2, Level3;
@@ -691,7 +691,9 @@ void Wlc_BlastReduceMatrix( Gia_Man_t * pNew, Vec_Wec_t * vProds, Vec_Wec_t * vL
         Vec_IntPush( vRes,   Vec_IntEntry(vProd, 0) );
         Vec_IntPush( vLevel, Vec_IntEntry(vProd, 1) );
     }
-    Wlc_BlastAdder( pNew, Vec_IntArray(vRes), Vec_IntArray(vLevel), nSizeMax );
+    Vec_IntPush( vRes,   0 );
+    Vec_IntPush( vLevel, 0 );
+    Wlc_BlastAdder( pNew, Vec_IntArray(vRes), Vec_IntArray(vLevel), Vec_IntSize(vRes) );
 }
 void Wlc_BlastMultiplier3( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int nArgB, Vec_Int_t * vRes )
 {
@@ -705,7 +707,7 @@ void Wlc_BlastMultiplier3( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA
             Vec_WecPush( vLevels, i+k, 0 );
         }
 
-    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, nArgA + nArgB );
+    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes );
 
     Vec_WecFree( vProds );
     Vec_WecFree( vLevels );
@@ -730,15 +732,15 @@ void Wlc_BlastSquare( Gia_Man_t * pNew, int * pNum, int nNum, Vec_Int_t * vTmp,
             }
         }
 
-    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, 2*nNum );
+    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes );
 
     Vec_WecFree( vProds );
     Vec_WecFree( vLevels );
 }
 void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int nArgB, Vec_Int_t * vRes, int fSigned )
 {
-    Vec_Wec_t * vProds  = Vec_WecStart( nArgA + nArgB );
-    Vec_Wec_t * vLevels = Vec_WecStart( nArgA + nArgB );
+    Vec_Wec_t * vProds  = Vec_WecStart( nArgA + nArgB + 3 );
+    Vec_Wec_t * vLevels = Vec_WecStart( nArgA + nArgB + 3 );
     int FillA = fSigned ? pArgA[nArgA-1] : 0;
     int FillB = fSigned ? pArgB[nArgB-1] : 0;
     int i, k, Sign;
@@ -769,6 +771,8 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int
             
             pp = Gia_ManHashXor( pNew, Part, Neg );
 
+            if ( pp == 0 )
+                continue;
             Vec_WecPush( vProds,  k+i, pp );
             Vec_WecPush( vLevels, k+i, 0 );
         }
@@ -799,9 +803,9 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int
         Vec_WecPush( vProds,  k, Neg );
         Vec_WecPush( vLevels, k, 0 );
     }
-//    Vec_WecPrint( vProds, 0 );
+    //Vec_WecPrint( vProds, 0 );
 
-    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes, nArgA + nArgB );
+    Wlc_BlastReduceMatrix( pNew, vProds, vLevels, vRes );
 
     Vec_WecFree( vProds );
     Vec_WecFree( vLevels );
@@ -820,7 +824,7 @@ void Wlc_BlastBooth( Gia_Man_t * pNew, int * pArgA, int * pArgB, int nArgA, int
   SeeAlso     []
 
 ***********************************************************************/
-Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nOutputRange, int fGiaSimple, int fAddOutputs )
+Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, int nOutputRange, int fGiaSimple, int fAddOutputs, int fBooth )
 {
     int fVerbose = 0;
     int fUseOldMultiplierBlasting = 0;
@@ -1229,10 +1233,12 @@ Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Vec_Int_t * vBoxIds, int iOutput, in
                 int * pArg1 = Wlc_VecLoadFanins( vTemp1, pFans1, nRange1, nRangeMax, fSigned );
                 if ( Wlc_NtkCountConstBits(pArg0, nRangeMax) < Wlc_NtkCountConstBits(pArg1, nRangeMax) )
                     ABC_SWAP( int *, pArg0, pArg1 );
-                Wlc_BlastMultiplier( pNew, pArg0, pArg1, nRangeMax, nRangeMax, vTemp2, vRes, fSigned );
-                //Wlc_BlastBooth( pNew, pArg0, pArg1, nRange0, nRange1, vRes, fSigned );
+                if ( fBooth )
+                    Wlc_BlastBooth( pNew, pArg0, pArg1, nRange0, nRange1, vRes, fSigned );
+                else
+                    Wlc_BlastMultiplier( pNew, pArg0, pArg1, nRangeMax, nRangeMax, vTemp2, vRes, fSigned );
                 //Wlc_BlastMultiplier3( pNew, pArg0, pArg1, nRange0, nRange1, vRes );
-                if ( nRange > nRangeMax + nRangeMax )
+                if ( nRange > Vec_IntSize(vRes) )
                     Vec_IntFillExtra( vRes, nRange, fSigned ? Vec_IntEntryLast(vRes) : 0 );
                 else
                     Vec_IntShrink( vRes, nRange );
diff --git a/src/base/wlc/wlcCom.c b/src/base/wlc/wlcCom.c
index 5237f11d..2c504127 100644
--- a/src/base/wlc/wlcCom.c
+++ b/src/base/wlc/wlcCom.c
@@ -338,9 +338,9 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
     Wlc_Ntk_t * pNtk = Wlc_AbcGetNtk(pAbc);
     Vec_Int_t * vBoxIds = NULL;
     Gia_Man_t * pNew = NULL;
-    int c, iOutput = -1, nOutputRange = 2, fGiaSimple = 0, fAddOutputs = 0, fMulti = 0, fVerbose  = 0;
+    int c, iOutput = -1, nOutputRange = 2, fGiaSimple = 0, fAddOutputs = 0, fMulti = 0, fBooth = 0, fVerbose  = 0;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "ORcomvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "ORcombvh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -375,6 +375,9 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'm':
             fMulti ^= 1;
             break;
+        case 'b':
+            fBooth ^= 1;
+            break;
         case 'v':
             fVerbose ^= 1;
             break;
@@ -401,7 +404,7 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
         return 0;
     }
     // transform
-    pNew = Wlc_NtkBitBlast( pNtk, vBoxIds, iOutput, nOutputRange, fGiaSimple, fAddOutputs );
+    pNew = Wlc_NtkBitBlast( pNtk, vBoxIds, iOutput, nOutputRange, fGiaSimple, fAddOutputs, fBooth );
     Vec_IntFreeP( &vBoxIds );
     if ( pNew == NULL )
     {
@@ -411,13 +414,14 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
     Abc_FrameUpdateGia( pAbc, pNew );
     return 0;
 usage:
-    Abc_Print( -2, "usage: %%blast [-OR num] [-comvh]\n" );
+    Abc_Print( -2, "usage: %%blast [-OR num] [-combvh]\n" );
     Abc_Print( -2, "\t         performs bit-blasting of the word-level design\n" );
     Abc_Print( -2, "\t-O num : zero-based index of the first word-level PO to bit-blast [default = %d]\n", iOutput );
     Abc_Print( -2, "\t-R num : the total number of word-level POs to bit-blast [default = %d]\n", nOutputRange );
     Abc_Print( -2, "\t-c     : toggle using AIG w/o const propagation and strashing [default = %s]\n", fGiaSimple? "yes": "no" );
     Abc_Print( -2, "\t-o     : toggle using additional POs on the word-level boundaries [default = %s]\n", fAddOutputs? "yes": "no" );
     Abc_Print( -2, "\t-m     : toggle creating boxes for all multipliers in the design [default = %s]\n", fMulti? "yes": "no" );
+    Abc_Print( -2, "\t-b     : toggle generating radix-4 Booth multipliers [default = %s]\n", fBooth? "yes": "no" );
     Abc_Print( -2, "\t-v     : toggle printing verbose information [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h     : print the command usage\n");
     return 1;
diff --git a/src/base/wlc/wlcReadVer.c b/src/base/wlc/wlcReadVer.c
index 3ff5cc6f..08dc8e98 100644
--- a/src/base/wlc/wlcReadVer.c
+++ b/src/base/wlc/wlcReadVer.c
@@ -1291,7 +1291,7 @@ void Io_ReadWordTest( char * pFileName )
         return;
     Wlc_WriteVer( pNtk, "test.v", 0, 0 );
 
-    pNew = Wlc_NtkBitBlast( pNtk, NULL, -1, 0, 0, 0 );
+    pNew = Wlc_NtkBitBlast( pNtk, NULL, -1, 0, 0, 0, 0 );
     Gia_AigerWrite( pNew, "test.aig", 0, 0 );
     Gia_ManStop( pNew );
 
diff --git a/src/base/wlc/wlcSim.c b/src/base/wlc/wlcSim.c
index 5fd83ca7..20ac8c61 100644
--- a/src/base/wlc/wlcSim.c
+++ b/src/base/wlc/wlcSim.c
@@ -129,7 +129,7 @@ Vec_Ptr_t * Wlc_NtkSimulate( Wlc_Ntk_t * p, Vec_Int_t * vNodes, int nWords, int
 {
     Gia_Obj_t * pObj; 
     Vec_Ptr_t * vOne, * vRes;
-    Gia_Man_t * pGia = Wlc_NtkBitBlast( p, NULL, -1, 0, 0, 0 );
+    Gia_Man_t * pGia = Wlc_NtkBitBlast( p, NULL, -1, 0, 0, 0, 0 );
     Wlc_Obj_t * pWlcObj;
     int f, i, k, w, nBits, Counter = 0;
     // allocate simulation info for one timeframe
diff --git a/src/proof/acec/acecPolyn.c b/src/proof/acec/acecPolyn.c
index be601405..042e0c59 100644
--- a/src/proof/acec/acecPolyn.c
+++ b/src/proof/acec/acecPolyn.c
@@ -64,26 +64,6 @@ struct Pln_Man_t_
 
 /**Function*************************************************************
 
-  Synopsis    []
-
-  Description []
-               
-  SideEffects []
-
-  SeeAlso     []
-
-***********************************************************************/
-Vec_Int_t * Pln_ManSimpleOrder( Gia_Man_t * p )
-{
-    Vec_Int_t * vOrder; int Id;
-    vOrder = Vec_IntStart( Gia_ManObjNum(p) );
-    Gia_ManForEachAndId( p, Id )
-        Vec_IntWriteEntry( vOrder, Id, Id );
-    return vOrder;
-}
-
-/**Function*************************************************************
-
   Synopsis    [Computation manager.]
 
   Description []
@@ -108,7 +88,7 @@ Pln_Man_t * Pln_ManAlloc( Gia_Man_t * pGia, Vec_Int_t * vOrder )
     p->vTempM[1] = Vec_IntAlloc( 100 );
     p->vTempM[2] = Vec_IntAlloc( 100 );
     p->vTempM[3] = Vec_IntAlloc( 100 );
-    p->vOrder    = vOrder ? vOrder : Vec_IntStartNatural( Gia_ManObjNum(pGia) );
+    p->vOrder    = vOrder ? Vec_IntDup(vOrder) : Vec_IntStartNatural( Gia_ManObjNum(pGia) );
     assert( Vec_IntSize(p->vOrder) == Gia_ManObjNum(pGia) );
     Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) );
     // add 0-constant and 1-monomial
@@ -131,36 +111,52 @@ void Pln_ManStop( Pln_Man_t * p )
     Vec_IntFree( p->vTempM[1] );
     Vec_IntFree( p->vTempM[2] );
     Vec_IntFree( p->vTempM[3] );
-    //Vec_IntFree( p->vOrder );
+    Vec_IntFree( p->vOrder );
     ABC_FREE( p );
 }
+int Pln_ManCompare3( int * pData0, int * pData1 )
+{
+    if ( pData0[0] < pData1[0] ) return -1;
+    if ( pData0[0] > pData1[0] ) return  1;
+    if ( pData0[1] < pData1[1] ) return -1;
+    if ( pData0[1] > pData1[1] ) return  1;
+    return 0;
+}
 void Pln_ManPrintFinal( Pln_Man_t * p, int fVerbose, int fVeryVerbose )
 {
     Vec_Int_t * vArray;
-    int k, Entry, iMono, iConst, Count = 0;
+    int i, k, Entry, iMono, iConst;
+    // collect triples
+    Vec_Int_t * vPairs = Vec_IntAlloc( 100 );
     Vec_IntForEachEntry( p->vCoefs, iConst, iMono )
     {
         if ( iConst == 0 ) 
             continue;
-
-        Count++;
-
-        if ( !fVerbose )
-            continue;
-
-        if ( Count > 25 )
+        vArray = Hsh_VecReadEntry( p->pHashC, iConst );
+        Vec_IntPush( vPairs, Vec_IntEntry(vArray, 0) );
+        vArray = Hsh_VecReadEntry( p->pHashM, iMono );
+        Vec_IntPush( vPairs, Vec_IntSize(vArray) ? Vec_IntEntry(vArray, 0) : 0 );
+        Vec_IntPushTwo( vPairs, iConst, iMono );
+    }
+    // sort triples
+    qsort( Vec_IntArray(vPairs), Vec_IntSize(vPairs)/4, 16, (int (*)(const void *, const void *))Pln_ManCompare3 );
+    // print
+    if ( fVerbose )
+    Vec_IntForEachEntryDouble( vPairs, iConst, iMono, i )
+    {
+        if ( i % 4 == 0 )
             continue;
-
+        printf( "%-6d : ", i/4 );
         vArray = Hsh_VecReadEntry( p->pHashC, iConst );
         Vec_IntForEachEntry( vArray, Entry, k )
             printf( "%s%d", Entry < 0 ? "-" : "+", (1 << (Abc_AbsInt(Entry)-1)) );
-
         vArray = Hsh_VecReadEntry( p->pHashM, iMono );
         Vec_IntForEachEntry( vArray, Entry, k )
             printf( " * %d", Entry );
         printf( "\n" );
     }
-    printf( "HashC = %d. HashM = %d.  Total = %d. Used = %d.\n", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Count );
+    printf( "HashC = %d. HashM = %d.  Total = %d. Used = %d.  ", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Vec_IntSize(vPairs)/4 );
+    Vec_IntFree( vPairs );
 }
 
 /**Function*************************************************************
@@ -400,7 +396,7 @@ void Gia_PolynBuild( Gia_Man_t * pGia, Vec_Int_t * vOrder, int fSigned, int fVer
             else
                 Vec_BitSetEntry( vPres, LevCur, 1 );
 
-            if ( fVerbose )
+            if ( fVeryVerbose )
                 printf( "Line%5d   Iter%10d : Obj =%6d.  Order =%6d.  HashC =%6d. HashM =%10d.  Total =%10d. Used =%10d.\n", 
                     Line++, Iter, LevCur, Vec_IntEntry(p->vOrder, LevCur), Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, p->nUsed );
         }
@@ -409,14 +405,37 @@ void Gia_PolynBuild( Gia_Man_t * pGia, Vec_Int_t * vOrder, int fSigned, int fVer
         Gia_PolynBuildOne( p, iMono );
         //clk2 += Abc_Clock() - temp;
     }
-    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
     //Abc_PrintTime( 1, "Time2", clk2 );
     Pln_ManPrintFinal( p, fVerbose, fVeryVerbose );
+    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
     Pln_ManStop( p );
     Vec_BitFree( vPres );
 }
 
 
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Gia_PolynBuild2( Gia_Man_t * pGia, int fSigned, int fVerbose, int fVeryVerbose )
+{
+    Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 );    // hash table for constants
+    Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 );    // hash table for monomials
+    Vec_Wec_t * vLit2Mono = Vec_WecStart( Gia_ManObjNum(pGia) * 2 );
+
+    Hsh_VecManStop( pHashC );
+    Hsh_VecManStop( pHashM );
+}
+
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////