summaryrefslogtreecommitdiffstats
path: root/src/aig/saig/saigIsoFast.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/aig/saig/saigIsoFast.c')
-rw-r--r--src/aig/saig/saigIsoFast.c352
1 files changed, 352 insertions, 0 deletions
diff --git a/src/aig/saig/saigIsoFast.c b/src/aig/saig/saigIsoFast.c
new file mode 100644
index 00000000..6556b90f
--- /dev/null
+++ b/src/aig/saig/saigIsoFast.c
@@ -0,0 +1,352 @@
+/**CFile****************************************************************
+
+ FileName [aigIsoFast.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [AIG package.]
+
+ Synopsis [Graph isomorphism package.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - April 28, 2007.]
+
+ Revision [$Id: aigIsoFast.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "saig.h"
+
+ABC_NAMESPACE_IMPL_START
+
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+#define AIG_ISO_NUM 16
+
+typedef struct Iso_Dat_t_ Iso_Dat_t;
+struct Iso_Dat_t_
+{
+ unsigned nFiNeg : 3;
+ unsigned nFoNeg : 2;
+ unsigned nFoPos : 2;
+ unsigned Fi0Lev : 3;
+ unsigned Fi1Lev : 3;
+ unsigned Level : 3;
+ unsigned fVisit : 16;
+};
+
+typedef struct Iso_Dat2_t_ Iso_Dat2_t;
+struct Iso_Dat2_t_
+{
+ unsigned Data : 16;
+};
+
+typedef struct Iso_Sto_t_ Iso_Sto_t;
+struct Iso_Sto_t_
+{
+ Aig_Man_t * pAig; // user's AIG manager
+ int nObjs; // number of objects
+ Iso_Dat_t * pData; // data for each object
+ Vec_Int_t * vVisited; // visited nodes
+ Vec_Ptr_t * vRoots; // root nodes
+ Vec_Int_t * vPlaces; // places in the counter lists
+ int * pCounters; // counters
+};
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Iso_Sto_t * Iso_StoStart( Aig_Man_t * pAig )
+{
+ Iso_Sto_t * p;
+ p = ABC_CALLOC( Iso_Sto_t, 1 );
+ p->pAig = pAig;
+ p->nObjs = Aig_ManObjNumMax( pAig );
+ p->pData = ABC_CALLOC( Iso_Dat_t, p->nObjs );
+ p->vVisited = Vec_IntStart( 1000 );
+ p->vPlaces = Vec_IntStart( 1000 );
+ p->vRoots = Vec_PtrStart( 1000 );
+ p->pCounters = ABC_CALLOC( int, (1 << AIG_ISO_NUM) );
+ return p;
+}
+void Iso_StoStop( Iso_Sto_t * p )
+{
+ Vec_IntFree( p->vPlaces );
+ Vec_IntFree( p->vVisited );
+ Vec_PtrFree( p->vRoots );
+ ABC_FREE( p->pCounters );
+ ABC_FREE( p->pData );
+ ABC_FREE( p );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collect statistics about one node.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Iso_StoCollectInfo_rec( Aig_Man_t * p, Aig_Obj_t * pObj, int fCompl, Vec_Int_t * vVisited, Iso_Dat_t * pData, Vec_Ptr_t * vRoots )
+{
+ Iso_Dat_t * pThis = pData + Aig_ObjId(pObj);
+ assert( Aig_ObjIsPi(pObj) || Aig_ObjIsNode(pObj) );
+ if ( pThis->fVisit )
+ {
+ if ( fCompl )
+ pThis->nFoNeg++;
+ else
+ pThis->nFoPos++;
+ return;
+ }
+ assert( *((int *)pThis) == 0 );
+ pThis->fVisit = 1;
+ if ( fCompl )
+ pThis->nFoNeg++;
+ else
+ pThis->nFoPos++;
+ pThis->Level = pObj->Level;
+ pThis->nFiNeg = Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
+ if ( Aig_ObjIsNode(pObj) )
+ {
+ if ( Aig_ObjFaninC0(pObj) < Aig_ObjFaninC1(pObj) || (Aig_ObjFaninC0(pObj) == Aig_ObjFaninC1(pObj) && Aig_ObjFanin0(pObj)->Level < Aig_ObjFanin1(pObj)->Level) )
+ {
+ pThis->Fi0Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
+ pThis->Fi1Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
+ }
+ else
+ {
+ pThis->Fi0Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
+ pThis->Fi1Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
+ }
+ Iso_StoCollectInfo_rec( p, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), vVisited, pData, vRoots );
+ Iso_StoCollectInfo_rec( p, Aig_ObjFanin1(pObj), Aig_ObjFaninC1(pObj), vVisited, pData, vRoots );
+ }
+ else if ( Saig_ObjIsLo(p, pObj) )
+ {
+ pThis->Fi0Lev = 1;
+ pThis->Fi1Lev = 0;
+ Vec_PtrPush( vRoots, Saig_ObjLoToLi(p, pObj) );
+ }
+ else if ( Saig_ObjIsPi(p, pObj) )
+ {
+ pThis->Fi0Lev = 0;
+ pThis->Fi1Lev = 0;
+ }
+ else
+ assert( 0 );
+ assert( pThis->nFoNeg + pThis->nFoPos );
+ Vec_IntPush( vVisited, Aig_ObjId(pObj) );
+}
+
+//static int time_Trav = 0;
+
+/**Function*************************************************************
+
+ Synopsis [Collect statistics about one output.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Int_t * Iso_StoCollectInfo( Iso_Sto_t * p, Aig_Obj_t * pPo )
+{
+ int fVerboseShow = 0;
+ Vec_Int_t * vInfo;
+ Iso_Dat2_t * pData2 = (Iso_Dat2_t *)p->pData;
+ Aig_Man_t * pAig = p->pAig;
+ Aig_Obj_t * pObj;
+ int i, Value, Entry, * pPerm;
+ int clk = clock();
+
+ assert( Aig_ObjIsPo(pPo) );
+
+ // collect initial POs
+ Vec_IntClear( p->vVisited );
+ Vec_PtrClear( p->vRoots );
+ Vec_PtrPush( p->vRoots, pPo );
+
+ // mark internal nodes
+ Vec_PtrForEachEntry( Aig_Obj_t *, p->vRoots, pObj, i )
+ if ( !Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) )
+ Iso_StoCollectInfo_rec( pAig, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), p->vVisited, p->pData, p->vRoots );
+// time_Trav += clock() - clk;
+
+ // count how many times each data entry appears
+ Vec_IntClear( p->vPlaces );
+ Vec_IntForEachEntry( p->vVisited, Entry, i )
+ {
+ Value = pData2[Entry].Data;
+// assert( Value > 0 );
+ if ( p->pCounters[Value]++ == 0 )
+ Vec_IntPush( p->vPlaces, Value );
+// pData2[Entry].Data = 0;
+ *((int *)(p->pData + Entry)) = 0;
+ }
+
+ // collect non-trivial counters
+ Vec_IntClear( p->vVisited );
+ Vec_IntForEachEntry( p->vPlaces, Entry, i )
+ {
+ assert( p->pCounters[Entry] );
+ Vec_IntPush( p->vVisited, p->pCounters[Entry] );
+ p->pCounters[Entry] = 0;
+ }
+// printf( "%d ", Vec_IntSize(p->vVisited) );
+
+ // sort the costs in the increasing order
+ pPerm = Abc_SortCost( Vec_IntArray(p->vVisited), Vec_IntSize(p->vVisited) );
+ assert( Vec_IntEntry(p->vVisited, pPerm[0]) <= Vec_IntEntry(p->vVisited, pPerm[Vec_IntSize(p->vVisited)-1]) );
+
+ // create information
+ vInfo = Vec_IntAlloc( Vec_IntSize(p->vVisited) );
+ for ( i = Vec_IntSize(p->vVisited)-1; i >= 0; i-- )
+ {
+ Entry = Vec_IntEntry( p->vVisited, pPerm[i] );
+ Entry = (Entry << AIG_ISO_NUM) | Vec_IntEntry( p->vPlaces, pPerm[i] );
+ Vec_IntPush( vInfo, Entry );
+ }
+ ABC_FREE( pPerm );
+
+ // show the final result
+ if ( fVerboseShow )
+ Vec_IntForEachEntry( vInfo, Entry, i )
+ {
+ Iso_Dat2_t Data = { Entry & 0xFFFF };
+ Iso_Dat_t * pData = (Iso_Dat_t *)&Data;
+
+ printf( "%6d : ", i );
+ printf( "Freq =%6d ", Entry >> 16 );
+
+ printf( "FiNeg =%3d ", pData->nFiNeg );
+ printf( "FoNeg =%3d ", pData->nFoNeg );
+ printf( "FoPos =%3d ", pData->nFoPos );
+ printf( "Fi0L =%3d ", pData->Fi0Lev );
+ printf( "Fi1L =%3d ", pData->Fi1Lev );
+ printf( "Lev =%3d ", pData->Level );
+ printf( "\n" );
+ }
+ return vInfo;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Takes multi-output sequential AIG.]
+
+ Description [Returns candidate equivalence classes of POs.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Iso_StoCompareVecInt( Vec_Int_t ** p1, Vec_Int_t ** p2 )
+{
+ return Vec_IntCompareVec( *p1, *p2 );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Takes multi-output sequential AIG.]
+
+ Description [Returns candidate equivalence classes of POs.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Vec_t * Saig_IsoDetectFast( Aig_Man_t * pAig )
+{
+ Iso_Sto_t * pMan;
+ Aig_Obj_t * pObj;
+ Vec_Ptr_t * vClasses, * vInfos;
+ Vec_Int_t * vInfo, * vPrev, * vLevel;
+ int i, Number, nUnique = 0, clk = clock();
+
+ // collect infos and remember their number
+ pMan = Iso_StoStart( pAig );
+ vInfos = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
+ Saig_ManForEachPo( pAig, pObj, i )
+ {
+ vInfo = Iso_StoCollectInfo(pMan, pObj);
+ Vec_IntPush( vInfo, i );
+ Vec_PtrPush( vInfos, vInfo );
+ }
+ Iso_StoStop( pMan );
+ Abc_PrintTime( 1, "Info computation time", clock() - clk );
+
+ // sort the infos
+ clk = clock();
+ Vec_PtrSort( vInfos, (int (*)(void))Iso_StoCompareVecInt );
+
+ // create classes
+ clk = clock();
+ vClasses = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
+ // start the first class
+ Vec_PtrPush( vClasses, (vLevel = Vec_IntAlloc(4)) );
+ vPrev = (Vec_Int_t *)Vec_PtrEntry( vInfos, 0 );
+ Vec_IntPush( vLevel, Vec_IntPop(vPrev) );
+ // consider other classes
+ Vec_PtrForEachEntryStart( Vec_Int_t *, vInfos, vInfo, i, 1 )
+ {
+ Number = Vec_IntPop( vInfo );
+ if ( Vec_IntCompareVec(vPrev, vInfo) )
+ Vec_PtrPush( vClasses, Vec_IntAlloc(4) );
+ vLevel = (Vec_Int_t *)Vec_PtrEntryLast( vClasses );
+ Vec_IntPush( vLevel, Number );
+ vPrev = vInfo;
+ }
+ Vec_VecFree( (Vec_Vec_t *)vInfos );
+ Abc_PrintTime( 1, "Sorting time", clock() - clk );
+// Abc_PrintTime( 1, "Traversal time", time_Trav );
+
+ // report the results
+// Vec_VecPrintInt( (Vec_Vec_t *)vClasses );
+ printf( "Devided %d outputs into %d cand equiv classes.\n", Saig_ManPoNum(pAig), Vec_PtrSize(vClasses) );
+
+ Vec_PtrForEachEntry( Vec_Int_t *, vClasses, vLevel, i )
+ if ( Vec_IntSize(vLevel) > 1 )
+ printf( "%d ", Vec_IntSize(vLevel) );
+ else
+ nUnique++;
+ printf( " Unique = %d\n", nUnique );
+
+// return (Vec_Vec_t *)vClasses;
+ Vec_VecFree( (Vec_Vec_t *)vClasses );
+ return NULL;
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-05 16:30:37 +0000