Experiments with arithmetic circuits.

5 files changed, 305 insertions, 4 deletions

diff --git a/abclib.dsp b/abclib.dsp
index 87e8aa91..9f66d089 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -4347,6 +4347,10 @@ SOURCE=.\src\aig\gia\giaPf.c
 # End Source File
 # Begin Source File
 
+SOURCE=.\src\aig\gia\giaPolyn.c
+# End Source File
+# Begin Source File
+
 SOURCE=.\src\aig\gia\giaQbf.c
 # End Source File
 # Begin Source File
diff --git a/src/aig/gia/giaPolyn.c b/src/aig/gia/giaPolyn.c
index 56c9a541..4e8d7378 100644
--- a/src/aig/gia/giaPolyn.c
+++ b/src/aig/gia/giaPolyn.c
@@ -21,6 +21,7 @@
 #include "gia.h"
 #include "misc/vec/vecWec.h"
 #include "misc/vec/vecHsh.h"
+#include "misc/vec/vecQue.h"
 
 ABC_NAMESPACE_IMPL_START
 
@@ -218,6 +219,294 @@ void Gia_PolynTest( Gia_Man_t * pGia )
 }
 
 
+
+
+
+typedef struct Pln_Man_t_ Pln_Man_t;
+struct Pln_Man_t_
+{
+    Gia_Man_t *    pGia;      // AIG manager
+    Hsh_VecMan_t * pHashC;    // hash table for constants
+    Hsh_VecMan_t * pHashM;    // hash table for monomials
+    Vec_Que_t *    vQue;      // queue by largest node
+    Vec_Flt_t *    vCounts;   // largest node
+    Vec_Int_t *    vCoefs;    // coefficients for each monomial
+    Vec_Int_t *    vTempC[2]; // polynomial representation
+    Vec_Int_t *    vTempM[4]; // polynomial representation
+    int            nBuilds;   // builds
+};
+    
+/**Function*************************************************************
+
+  Synopsis    [Computation manager.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Pln_Man_t * Pln_ManAlloc( Gia_Man_t * pGia )
+{
+    Pln_Man_t * p = ABC_CALLOC( Pln_Man_t, 1 );
+    p->pGia      = pGia;
+    p->pHashC    = Hsh_VecManStart( 1000 );
+    p->pHashM    = Hsh_VecManStart( 1000 );
+    p->vQue      = Vec_QueAlloc( 1000 );
+    p->vCounts   = Vec_FltAlloc( 1000 );
+    p->vCoefs    = Vec_IntAlloc( 1000 );
+    p->vTempC[0] = Vec_IntAlloc( 100 );
+    p->vTempC[1] = Vec_IntAlloc( 100 );
+    p->vTempM[0] = Vec_IntAlloc( 100 );
+    p->vTempM[1] = Vec_IntAlloc( 100 );
+    p->vTempM[2] = Vec_IntAlloc( 100 );
+    p->vTempM[3] = Vec_IntAlloc( 100 );
+    Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) );
+    // add 0-constant and 1-monomial
+    Hsh_VecManAdd( p->pHashC, p->vTempC[0] );
+    Hsh_VecManAdd( p->pHashM, p->vTempM[0] );
+    Vec_FltPush( p->vCounts, 0 );
+    Vec_IntPush( p->vCoefs, 0 );
+    return p;
+}
+void Pln_ManStop( Pln_Man_t * p )
+{
+    Hsh_VecManStop( p->pHashC );
+    Hsh_VecManStop( p->pHashM );
+    Vec_QueFree( p->vQue );
+    Vec_FltFree( p->vCounts );
+    Vec_IntFree( p->vCoefs );
+    Vec_IntFree( p->vTempC[0] );
+    Vec_IntFree( p->vTempC[1] );
+    Vec_IntFree( p->vTempM[0] );
+    Vec_IntFree( p->vTempM[1] );
+    Vec_IntFree( p->vTempM[2] );
+    Vec_IntFree( p->vTempM[3] );
+    ABC_FREE( p );
+}
+void Pln_ManPrintFinal( Pln_Man_t * p )
+{
+    Vec_Int_t * vArray;
+    int k, Entry, iMono, iConst, Count = 0;
+    Vec_IntForEachEntry( p->vCoefs, iConst, iMono )
+    {
+        if ( iConst == 0 ) 
+            continue;
+
+        Count++;
+
+        if ( Vec_IntSize(p->vCoefs) > 1000 )
+            continue;
+
+        vArray = Hsh_VecReadEntry( p->pHashC, iConst );
+        Vec_IntForEachEntry( vArray, Entry, k )
+            printf( "%s%s2^%d", k ? " + " : "", Entry < 0 ? "-" : "+", 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 );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline void Gia_PolynMergeConstOne( Vec_Int_t * vConst, int New )
+{
+    int i, Old;
+    assert( New != 0 );
+    Vec_IntForEachEntry( vConst, Old, i )
+    {
+        assert( Old != 0 );
+        if ( Old == New ) // A == B
+        {
+            Vec_IntDrop( vConst, i );
+            Gia_PolynMergeConstOne( vConst, New > 0 ? New + 1 : New - 1 );
+            return;
+        }
+        if ( Abc_AbsInt(Old) == Abc_AbsInt(New) ) // A == -B
+        {
+            Vec_IntDrop( vConst, i );
+            return;
+        }
+        if ( Old + New == 1 || Old + New == -1 )  // sign(A) != sign(B)  &&  abs(abs(A)-abs(B)) == 1 
+        {
+            int Value = Abc_MinInt( Abc_AbsInt(Old), Abc_AbsInt(New) );
+            Vec_IntDrop( vConst, i );
+            Gia_PolynMergeConstOne( vConst, (Old + New == 1) ? Value : -Value );
+            return;
+        }
+    }
+    Vec_IntPushUniqueOrder( vConst, New );
+}
+static inline void Gia_PolynMergeConst( Vec_Int_t * vConst, Pln_Man_t * p, int iConstAdd )
+{
+    int i, New;
+    Vec_Int_t * vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd );
+    Vec_IntForEachEntry( vConstAdd, New, i )
+    {
+        Gia_PolynMergeConstOne( vConst, New );
+        vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd );
+    }
+}
+static inline void Gia_PolynBuildAdd( Pln_Man_t * p, Vec_Int_t * vTempC, Vec_Int_t * vTempM )
+{
+    int iConst, iMono = vTempM ? Hsh_VecManAdd(p->pHashM, vTempM) : 0;
+    p->nBuilds++;
+    if ( iMono == Vec_IntSize(p->vCoefs) ) // new monomial
+    {
+        iConst = Hsh_VecManAdd( p->pHashC, vTempC );
+        Vec_IntPush( p->vCoefs, iConst );
+        Vec_FltPush( p->vCounts, Vec_IntEntryLast(vTempM) );
+        Vec_QuePush( p->vQue, iMono );
+//        Vec_QueUpdate( p->vQue, iMono );
+        return;
+    }
+    // this monomial exists
+    iConst = Vec_IntEntry( p->vCoefs, iMono );
+    if ( iConst )
+        Gia_PolynMergeConst( vTempC, p, iConst );
+    iConst = Hsh_VecManAdd( p->pHashC, vTempC );
+    Vec_IntWriteEntry( p->vCoefs, iMono, iConst );
+}
+void Gia_PolynBuildOne( Pln_Man_t * p, int iMono )
+{
+    Gia_Obj_t * pObj; 
+    Vec_Int_t * vArray, * vConst;
+    int iFan0, iFan1;
+    int k, iConst, iDriver;
+
+    assert( Vec_IntSize(p->vCoefs) == Hsh_VecSize(p->pHashM) );
+    vArray  = Hsh_VecReadEntry( p->pHashM, iMono );
+    iDriver = Vec_IntEntryLast( vArray );
+    pObj    = Gia_ManObj( p->pGia, iDriver );
+    if ( !Gia_ObjIsAnd(pObj) )
+        return;
+
+    iConst = Vec_IntEntry( p->vCoefs, iMono );
+    if ( iConst == 0 )
+        return;
+    Vec_IntWriteEntry( p->vCoefs, iMono, 0 );
+
+    iFan0 = Gia_ObjFaninId0p(p->pGia, pObj);
+    iFan1 = Gia_ObjFaninId1p(p->pGia, pObj);
+    for ( k = 0; k < 4; k++ )
+    {
+        Vec_IntClear( p->vTempM[k] );
+        Vec_IntAppend( p->vTempM[k], vArray );
+        Vec_IntPop( p->vTempM[k] );
+        if ( k == 1 || k == 3 )
+            Vec_IntPushUniqueOrder( p->vTempM[k], iFan0 );    // x
+        if ( k == 2 || k == 3 )
+            Vec_IntPushUniqueOrder( p->vTempM[k], iFan1 );    // y
+    }
+
+    vConst = Hsh_VecReadEntry( p->pHashC, iConst );
+    for ( k = 0; k < 2; k++ )
+        Vec_IntAppendMinus( p->vTempC[k], vConst, k );
+
+    if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) )       //  C * (1 - x) * (1 - y)
+    {
+        Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] );   //  C * 1
+        Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[1] );   // -C * x
+        vConst = Hsh_VecReadEntry( p->pHashC, iConst );
+        for ( k = 0; k < 2; k++ )
+            Vec_IntAppendMinus( p->vTempC[k], vConst, k );
+        Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[2] );   // -C * y 
+        Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] );   //  C * x * y
+    }
+    else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ) //  C * (1 - x) * y
+    {
+        Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[2] );   //  C * y 
+        Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] );   // -C * x * y
+    }
+    else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) //  C * x * (1 - y)
+    {
+        Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[1] );   //  C * x 
+        Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] );   // -C * x * y
+    }
+    else   
+        Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] );   //  C * x * y
+}
+int Gia_PolyFindNext2( Pln_Man_t * p )
+{
+    Gia_Obj_t * pObj; 
+    Vec_Int_t * vArray;
+    int Max = 0, iBest = 0, iConst, iMono, iDriver;
+    Vec_IntForEachEntryStart( p->vCoefs, iConst, iMono, 1 )
+    {
+        if ( iConst == 0 ) 
+            continue;
+        vArray  = Hsh_VecReadEntry( p->pHashM, iMono );
+        iDriver = Vec_IntEntryLast( vArray );
+        pObj    = Gia_ManObj( p->pGia, iDriver );
+        if ( !Gia_ObjIsAnd(pObj) )
+            continue;
+        if ( Max < Vec_IntEntryLast(vArray) )
+        {
+            Max   = Vec_IntEntryLast(vArray);
+            iBest = iMono;
+        }
+    }
+    //Vec_IntPrint( Hsh_VecReadEntry(p->pHashM, iBest) );
+    return iBest;
+}
+int Gia_PolyFindNext( Pln_Man_t * p )
+{
+    int iBest = Vec_QueSize(p->vQue) ?  Vec_QuePop(p->vQue) : 0;
+    //Vec_IntPrint( Hsh_VecReadEntry(p->pHashM, iBest) );
+    return iBest;
+}
+void Gia_PolynBuildTest( Gia_Man_t * pGia )
+{
+    abctime clk = Abc_Clock();//, clk2 = 0;
+    Gia_Obj_t * pObj; 
+    int i, iMono, iDriver;
+    Pln_Man_t * p = Pln_ManAlloc( pGia );
+    Gia_ManForEachCoReverse( pGia, pObj, i )
+    {
+        Vec_IntFill( p->vTempC[0], 1,  i+1 );      //  2^i
+        Vec_IntFill( p->vTempC[1], 1, -i-1 );      // -2^i
+
+        iDriver = Gia_ObjFaninId0p( pGia, pObj );
+        Vec_IntFill( p->vTempM[0], 1, iDriver );   //  Driver
+
+        if ( Gia_ObjFaninC0(pObj) )
+        {
+            Gia_PolynBuildAdd( p, p->vTempC[0], NULL );           //  C
+            Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[0] );   // -C * Driver
+        }
+        else
+            Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] );   //  C * Driver
+    }
+    while ( 1 )
+    {
+        //abctime temp = Abc_Clock();
+        iMono = Gia_PolyFindNext(p);
+        if ( !iMono )
+            break;
+        Gia_PolynBuildOne( p, iMono );
+        //clk2 += Abc_Clock() - temp;
+    }
+    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+    //Abc_PrintTime( 1, "Time2", clk2 );
+    Pln_ManPrintFinal( p );
+    Pln_ManStop( p );
+}
+
+
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/aig/gia/module.make b/src/aig/gia/module.make
index adc21d74..7da2858e 100644
--- a/src/aig/gia/module.make
+++ b/src/aig/gia/module.make
@@ -52,6 +52,7 @@ SRC +=    src/aig/gia/giaAig.c \
     src/aig/gia/giaPack.c \
     src/aig/gia/giaPat.c \
     src/aig/gia/giaPf.c \
+    src/aig/gia/giaPolyn.c \
     src/aig/gia/giaQbf.c \
     src/aig/gia/giaResub.c \
     src/aig/gia/giaRetime.c \
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index ab220ab3..c0052a74 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -1583,10 +1583,10 @@ int Abc_CommandPrintFanio( Abc_Frame_t * pAbc, int argc, char ** argv )
 usage:
     Abc_Print( -2, "usage: print_fanio [-fiscmvh]\n" );
     Abc_Print( -2, "\t        prints the statistics about different objects in the network\n" );
-    Abc_Print( -2, "\t-f    : toggles considering fanins/outputs of all nodes [default = %s]\n", fUseFanio? "yes": "no" );
-    Abc_Print( -2, "\t-i    : toggles considering fanins/outputs of CI/CO [default = %s]\n", fUsePio? "yes": "no" );
-    Abc_Print( -2, "\t-s    : toggles considering input/output supports of CI/CO [default = %s]\n", fUseSupp? "yes": "no" );
-    Abc_Print( -2, "\t-c    : toggles considering input/output cones of CI/CO [default = %s]\n", fUseCone? "yes": "no" );
+    Abc_Print( -2, "\t-f    : toggles considering fanins/fanouts of all nodes [default = %s]\n", fUseFanio? "yes": "no" );
+    Abc_Print( -2, "\t-i    : toggles considering fanins/fanouts of CI/CO [default = %s]\n", fUsePio? "yes": "no" );
+    Abc_Print( -2, "\t-s    : toggles considering TFO/TFI support sizes of CI/CO [default = %s]\n", fUseSupp? "yes": "no" );
+    Abc_Print( -2, "\t-c    : toggles considering TFO/TFI cone sizes of CI/CO [default = %s]\n", fUseCone? "yes": "no" );
     Abc_Print( -2, "\t-m    : toggles printing MFFC sizes instead of fanouts [default = %s]\n", fMffc? "yes": "no" );
     Abc_Print( -2, "\t-v    : toggles verbose way of printing the stats [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h    : print the command usage\n");
diff --git a/src/misc/vec/vecInt.h b/src/misc/vec/vecInt.h
index 3d7c33fc..e0e2ba7f 100644
--- a/src/misc/vec/vecInt.h
+++ b/src/misc/vec/vecInt.h
@@ -1991,6 +1991,13 @@ static inline void Vec_IntAppendSkip( Vec_Int_t * vVec1, Vec_Int_t * vVec2, int
         if ( i != iVar )
             Vec_IntPush( vVec1, Entry );
 }
+static inline void Vec_IntAppendMinus( Vec_Int_t * vVec1, Vec_Int_t * vVec2, int fMinus )
+{
+    int Entry, i;
+    Vec_IntClear( vVec1 );
+    Vec_IntForEachEntry( vVec2, Entry, i )
+        Vec_IntPush( vVec1, fMinus ? -Entry : Entry );
+}
 
 /**Function*************************************************************