1 /**CFile****************************************************************
2 
3   FileName    [aigIsoFast.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [AIG package.]
8 
9   Synopsis    [Graph isomorphism package.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - April 28, 2007.]
16 
17   Revision    [$Id: aigIsoFast.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "saig.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 ///                        DECLARATIONS                              ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 #define AIG_ISO_NUM 16
31 
32 typedef struct Iso_Dat_t_ Iso_Dat_t;
33 struct Iso_Dat_t_
34 {
35     unsigned      nFiNeg    :  3;
36     unsigned      nFoNeg    :  2;
37     unsigned      nFoPos    :  2;
38     unsigned      Fi0Lev    :  3;
39     unsigned      Fi1Lev    :  3;
40     unsigned      Level     :  3;
41     unsigned      fVisit    : 16;
42 };
43 
44 typedef struct Iso_Dat2_t_ Iso_Dat2_t;
45 struct Iso_Dat2_t_
46 {
47     unsigned      Data      : 16;
48 };
49 
50 typedef struct Iso_Sto_t_ Iso_Sto_t;
51 struct Iso_Sto_t_
52 {
53     Aig_Man_t *   pAig;       // user's AIG manager
54     int           nObjs;      // number of objects
55     Iso_Dat_t *   pData;      // data for each object
56     Vec_Int_t *   vVisited;   // visited nodes
57     Vec_Ptr_t *   vRoots;     // root nodes
58     Vec_Int_t *   vPlaces;    // places in the counter lists
59     int *         pCounters;  // counters
60 };
61 
62 ////////////////////////////////////////////////////////////////////////
63 ///                     FUNCTION DEFINITIONS                         ///
64 ////////////////////////////////////////////////////////////////////////
65 
66 /**Function*************************************************************
67 
68   Synopsis    []
69 
70   Description []
71 
72   SideEffects []
73 
74   SeeAlso     []
75 
76 ***********************************************************************/
Iso_StoStart(Aig_Man_t * pAig)77 Iso_Sto_t * Iso_StoStart( Aig_Man_t * pAig )
78 {
79     Iso_Sto_t * p;
80     p = ABC_CALLOC( Iso_Sto_t, 1 );
81     p->pAig      = pAig;
82     p->nObjs     = Aig_ManObjNumMax( pAig );
83     p->pData     = ABC_CALLOC( Iso_Dat_t, p->nObjs );
84     p->vVisited  = Vec_IntStart( 1000 );
85     p->vPlaces   = Vec_IntStart( 1000 );
86     p->vRoots    = Vec_PtrStart( 1000 );
87     p->pCounters = ABC_CALLOC( int, (1 << AIG_ISO_NUM) );
88     return p;
89 }
Iso_StoStop(Iso_Sto_t * p)90 void Iso_StoStop( Iso_Sto_t * p )
91 {
92     Vec_IntFree( p->vPlaces );
93     Vec_IntFree( p->vVisited );
94     Vec_PtrFree( p->vRoots );
95     ABC_FREE( p->pCounters );
96     ABC_FREE( p->pData );
97     ABC_FREE( p );
98 }
99 
100 /**Function*************************************************************
101 
102   Synopsis    [Collect statistics about one node.]
103 
104   Description []
105 
106   SideEffects []
107 
108   SeeAlso     []
109 
110 ***********************************************************************/
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)111 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 )
112 {
113     Iso_Dat_t * pThis = pData + Aig_ObjId(pObj);
114     assert( Aig_ObjIsCi(pObj) || Aig_ObjIsNode(pObj) );
115     if ( pThis->fVisit )
116     {
117         if ( fCompl )
118             pThis->nFoNeg++;
119         else
120             pThis->nFoPos++;
121         return;
122     }
123     assert( *((int *)pThis) == 0 );
124     pThis->fVisit = 1;
125     if ( fCompl )
126         pThis->nFoNeg++;
127     else
128         pThis->nFoPos++;
129     pThis->Level = pObj->Level;
130     pThis->nFiNeg = Aig_ObjFaninC0(pObj) + Aig_ObjFaninC1(pObj);
131     if ( Aig_ObjIsNode(pObj) )
132     {
133         if ( Aig_ObjFaninC0(pObj) < Aig_ObjFaninC1(pObj) || (Aig_ObjFaninC0(pObj) == Aig_ObjFaninC1(pObj) && Aig_ObjFanin0(pObj)->Level < Aig_ObjFanin1(pObj)->Level) )
134         {
135             pThis->Fi0Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
136             pThis->Fi1Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
137         }
138         else
139         {
140             pThis->Fi0Lev = pObj->Level - Aig_ObjFanin1(pObj)->Level;
141             pThis->Fi1Lev = pObj->Level - Aig_ObjFanin0(pObj)->Level;
142         }
143         Iso_StoCollectInfo_rec( p, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), vVisited, pData, vRoots );
144         Iso_StoCollectInfo_rec( p, Aig_ObjFanin1(pObj), Aig_ObjFaninC1(pObj), vVisited, pData, vRoots );
145     }
146     else if ( Saig_ObjIsLo(p, pObj) )
147     {
148         pThis->Fi0Lev = 1;
149         pThis->Fi1Lev = 0;
150         Vec_PtrPush( vRoots, Saig_ObjLoToLi(p, pObj) );
151     }
152     else if ( Saig_ObjIsPi(p, pObj) )
153     {
154         pThis->Fi0Lev = 0;
155         pThis->Fi1Lev = 0;
156     }
157     else
158         assert( 0 );
159     assert( pThis->nFoNeg + pThis->nFoPos );
160     Vec_IntPush( vVisited, Aig_ObjId(pObj) );
161 }
162 
163 //static abctime time_Trav = 0;
164 
165 /**Function*************************************************************
166 
167   Synopsis    [Collect statistics about one output.]
168 
169   Description []
170 
171   SideEffects []
172 
173   SeeAlso     []
174 
175 ***********************************************************************/
Iso_StoCollectInfo(Iso_Sto_t * p,Aig_Obj_t * pPo)176 Vec_Int_t * Iso_StoCollectInfo( Iso_Sto_t * p, Aig_Obj_t * pPo )
177 {
178     int fVerboseShow = 0;
179     Vec_Int_t * vInfo;
180     Iso_Dat2_t * pData2 = (Iso_Dat2_t *)p->pData;
181     Aig_Man_t * pAig = p->pAig;
182     Aig_Obj_t * pObj;
183     int i, Value, Entry, * pPerm;
184 //    abctime clk = Abc_Clock();
185 
186     assert( Aig_ObjIsCo(pPo) );
187 
188     // collect initial POs
189     Vec_IntClear( p->vVisited );
190     Vec_PtrClear( p->vRoots );
191     Vec_PtrPush( p->vRoots, pPo );
192 
193     // mark internal nodes
194     Vec_PtrForEachEntry( Aig_Obj_t *, p->vRoots, pObj, i )
195         if ( !Aig_ObjIsConst1(Aig_ObjFanin0(pObj)) )
196             Iso_StoCollectInfo_rec( pAig, Aig_ObjFanin0(pObj), Aig_ObjFaninC0(pObj), p->vVisited, p->pData, p->vRoots );
197 //    time_Trav += Abc_Clock() - clk;
198 
199     // count how many times each data entry appears
200     Vec_IntClear( p->vPlaces );
201     Vec_IntForEachEntry( p->vVisited, Entry, i )
202     {
203         Value = pData2[Entry].Data;
204 //        assert( Value > 0 );
205         if ( p->pCounters[Value]++ == 0 )
206             Vec_IntPush( p->vPlaces, Value );
207 //        pData2[Entry].Data = 0;
208         *((int *)(p->pData + Entry)) = 0;
209     }
210 
211     // collect non-trivial counters
212     Vec_IntClear( p->vVisited );
213     Vec_IntForEachEntry( p->vPlaces, Entry, i )
214     {
215         assert( p->pCounters[Entry] );
216         Vec_IntPush( p->vVisited, p->pCounters[Entry] );
217         p->pCounters[Entry] = 0;
218     }
219 //    printf( "%d ", Vec_IntSize(p->vVisited) );
220 
221     // sort the costs in the increasing order
222     pPerm = Abc_MergeSortCost( Vec_IntArray(p->vVisited), Vec_IntSize(p->vVisited) );
223     assert( Vec_IntEntry(p->vVisited, pPerm[0]) <= Vec_IntEntry(p->vVisited, pPerm[Vec_IntSize(p->vVisited)-1]) );
224 
225     // create information
226     vInfo = Vec_IntAlloc( Vec_IntSize(p->vVisited) );
227     for ( i = Vec_IntSize(p->vVisited)-1; i >= 0; i-- )
228     {
229         Entry = Vec_IntEntry( p->vVisited, pPerm[i] );
230         Entry = (Entry << AIG_ISO_NUM) | Vec_IntEntry( p->vPlaces, pPerm[i] );
231         Vec_IntPush( vInfo, Entry );
232     }
233     ABC_FREE( pPerm );
234 
235     // show the final result
236     if ( fVerboseShow )
237     Vec_IntForEachEntry( vInfo, Entry, i )
238     {
239         Iso_Dat2_t Data = { Entry & 0xFFFF };
240         Iso_Dat_t * pData = (Iso_Dat_t *)&Data;
241 
242         printf( "%6d : ", i );
243         printf( "Freq =%6d ", Entry >> 16 );
244 
245         printf( "FiNeg =%3d ", pData->nFiNeg );
246         printf( "FoNeg =%3d ", pData->nFoNeg );
247         printf( "FoPos =%3d ", pData->nFoPos );
248         printf( "Fi0L  =%3d ", pData->Fi0Lev );
249         printf( "Fi1L  =%3d ", pData->Fi1Lev );
250         printf( "Lev   =%3d ", pData->Level  );
251         printf( "\n" );
252     }
253     return vInfo;
254 }
255 
256 /**Function*************************************************************
257 
258   Synopsis    [Takes multi-output sequential AIG.]
259 
260   Description [Returns candidate equivalence classes of POs.]
261 
262   SideEffects []
263 
264   SeeAlso     []
265 
266 ***********************************************************************/
Iso_StoCompareVecInt(Vec_Int_t ** p1,Vec_Int_t ** p2)267 int Iso_StoCompareVecInt( Vec_Int_t ** p1, Vec_Int_t ** p2 )
268 {
269     return Vec_IntCompareVec( *p1, *p2 );
270 }
271 
272 /**Function*************************************************************
273 
274   Synopsis    [Takes multi-output sequential AIG.]
275 
276   Description [Returns candidate equivalence classes of POs.]
277 
278   SideEffects []
279 
280   SeeAlso     []
281 
282 ***********************************************************************/
Saig_IsoDetectFast(Aig_Man_t * pAig)283 Vec_Vec_t * Saig_IsoDetectFast( Aig_Man_t * pAig )
284 {
285     Iso_Sto_t * pMan;
286     Aig_Obj_t * pObj;
287     Vec_Ptr_t * vClasses, * vInfos;
288     Vec_Int_t * vInfo, * vPrev, * vLevel;
289     int i, Number, nUnique = 0;
290     abctime clk = Abc_Clock();
291 
292     // collect infos and remember their number
293     pMan = Iso_StoStart( pAig );
294     vInfos = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
295     Saig_ManForEachPo( pAig, pObj, i )
296     {
297         vInfo = Iso_StoCollectInfo(pMan, pObj);
298         Vec_IntPush( vInfo, i );
299         Vec_PtrPush( vInfos, vInfo );
300     }
301     Iso_StoStop( pMan );
302     Abc_PrintTime( 1, "Info computation time", Abc_Clock() - clk );
303 
304     // sort the infos
305     clk = Abc_Clock();
306     Vec_PtrSort( vInfos, (int (*)(void))Iso_StoCompareVecInt );
307 
308     // create classes
309     clk = Abc_Clock();
310     vClasses = Vec_PtrAlloc( Saig_ManPoNum(pAig) );
311     // start the first class
312     Vec_PtrPush( vClasses, (vLevel = Vec_IntAlloc(4)) );
313     vPrev = (Vec_Int_t *)Vec_PtrEntry( vInfos, 0 );
314     Vec_IntPush( vLevel, Vec_IntPop(vPrev) );
315     // consider other classes
316     Vec_PtrForEachEntryStart( Vec_Int_t *, vInfos, vInfo, i, 1 )
317     {
318         Number = Vec_IntPop( vInfo );
319         if ( Vec_IntCompareVec(vPrev, vInfo) )
320             Vec_PtrPush( vClasses, Vec_IntAlloc(4) );
321         vLevel = (Vec_Int_t *)Vec_PtrEntryLast( vClasses );
322         Vec_IntPush( vLevel, Number );
323         vPrev = vInfo;
324     }
325     Vec_VecFree( (Vec_Vec_t *)vInfos );
326     Abc_PrintTime( 1, "Sorting time", Abc_Clock() - clk );
327 //    Abc_PrintTime( 1, "Traversal time", time_Trav );
328 
329     // report the results
330 //    Vec_VecPrintInt( (Vec_Vec_t *)vClasses );
331     printf( "Devided %d outputs into %d cand equiv classes.\n", Saig_ManPoNum(pAig), Vec_PtrSize(vClasses) );
332 
333     Vec_PtrForEachEntry( Vec_Int_t *, vClasses, vLevel, i )
334         if ( Vec_IntSize(vLevel) > 1 )
335             printf( "%d ", Vec_IntSize(vLevel) );
336         else
337             nUnique++;
338     printf( " Unique = %d\n", nUnique );
339 
340 //    return (Vec_Vec_t *)vClasses;
341     Vec_VecFree( (Vec_Vec_t *)vClasses );
342     return NULL;
343 }
344 
345 
346 
347 ////////////////////////////////////////////////////////////////////////
348 ///                       END OF FILE                                ///
349 ////////////////////////////////////////////////////////////////////////
350 
351 
352 ABC_NAMESPACE_IMPL_END
353 
354