1 /**CFile****************************************************************
2 
3   FileName    [acecNorm.c]
4 
5   SystemName  [ABC: Logic synthesis and verification system.]
6 
7   PackageName [CEC for arithmetic circuits.]
8 
9   Synopsis    [Adder tree normalization.]
10 
11   Author      [Alan Mishchenko]
12 
13   Affiliation [UC Berkeley]
14 
15   Date        [Ver. 1.0. Started - June 20, 2005.]
16 
17   Revision    [$Id: acecNorm.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "acecInt.h"
22 
23 ABC_NAMESPACE_IMPL_START
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 ///                        DECLARATIONS                              ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 ////////////////////////////////////////////////////////////////////////
31 ///                     FUNCTION DEFINITIONS                         ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36   Synopsis    []
37 
38   Description []
39 
40   SideEffects []
41 
42   SeeAlso     []
43 
44 ***********************************************************************/
Acec_InsertHadd(Gia_Man_t * pNew,int In[2],int Out[2])45 void Acec_InsertHadd( Gia_Man_t * pNew, int In[2], int Out[2] )
46 {
47     int And, Or;
48     Out[1] = Gia_ManAppendAnd2( pNew, In[0], In[1] );
49     And    = Gia_ManAppendAnd2( pNew, Abc_LitNot(In[0]), Abc_LitNot(In[1]) );
50     Or     = Gia_ManAppendOr2( pNew, Out[1], And );
51     Out[0] = Abc_LitNot( Or );
52 }
Acec_InsertFadd(Gia_Man_t * pNew,int In[3],int Out[2])53 void Acec_InsertFadd( Gia_Man_t * pNew, int In[3], int Out[2] )
54 {
55     int In2[2], Out1[2], Out2[2];
56     Acec_InsertHadd( pNew, In, Out1 );
57     In2[0] = Out1[0];
58     In2[1] = In[2];
59     Acec_InsertHadd( pNew, In2, Out2 );
60     Out[0] = Out2[0];
61     Out[1] = Gia_ManAppendOr2( pNew, Out1[1], Out2[1] );
62 }
Acec_InsertTree(Gia_Man_t * pNew,Vec_Wec_t * vLeafMap)63 Vec_Int_t * Acec_InsertTree( Gia_Man_t * pNew, Vec_Wec_t * vLeafMap )
64 {
65     Vec_Int_t * vRootRanks = Vec_IntAlloc( Vec_WecSize(vLeafMap) + 5 );
66     Vec_Int_t * vLevel;
67     int i, In[3], Out[2];
68     Vec_WecForEachLevel( vLeafMap, vLevel, i )
69     {
70         if ( Vec_IntSize(vLevel) == 0 )
71         {
72             Vec_IntPush( vRootRanks, 0 );
73             continue;
74         }
75         while ( Vec_IntSize(vLevel) > 1 )
76         {
77             if ( Vec_IntSize(vLevel) == 2 )
78                 Vec_IntPush( vLevel, 0 );
79             //In[2] = Vec_IntPop( vLevel );
80             //In[1] = Vec_IntPop( vLevel );
81             //In[0] = Vec_IntPop( vLevel );
82 
83             In[0] = Vec_IntEntry( vLevel, 0 );
84             Vec_IntDrop( vLevel, 0 );
85 
86             In[1] = Vec_IntEntry( vLevel, 0 );
87             Vec_IntDrop( vLevel, 0 );
88 
89             In[2] = Vec_IntEntry( vLevel, 0 );
90             Vec_IntDrop( vLevel, 0 );
91 
92             Acec_InsertFadd( pNew, In, Out );
93             Vec_IntPush( vLevel, Out[0] );
94             if ( i+1 < Vec_WecSize(vLeafMap) )
95                 vLevel = Vec_WecEntry(vLeafMap, i+1);
96             else
97                 vLevel = Vec_WecPushLevel(vLeafMap);
98             Vec_IntPush( vLevel, Out[1] );
99             vLevel = Vec_WecEntry(vLeafMap, i);
100         }
101         assert( Vec_IntSize(vLevel) == 1 );
102         Vec_IntPush( vRootRanks, Vec_IntEntry(vLevel, 0) );
103     }
104     return vRootRanks;
105 }
106 
107 /**Function*************************************************************
108 
109   Synopsis    []
110 
111   Description []
112 
113   SideEffects []
114 
115   SeeAlso     []
116 
117 ***********************************************************************/
Acec_InsertBox_rec(Gia_Man_t * pNew,Gia_Man_t * p,Gia_Obj_t * pObj)118 int Acec_InsertBox_rec( Gia_Man_t * pNew, Gia_Man_t * p, Gia_Obj_t * pObj )
119 {
120     if ( ~pObj->Value )
121         return pObj->Value;
122     assert( Gia_ObjIsAnd(pObj) );
123     Acec_InsertBox_rec( pNew, p, Gia_ObjFanin0(pObj) );
124     Acec_InsertBox_rec( pNew, p, Gia_ObjFanin1(pObj) );
125     return (pObj->Value = Gia_ManAppendAnd2( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) ));
126 }
Acec_BuildTree(Gia_Man_t * pNew,Gia_Man_t * p,Vec_Wec_t * vLeafLits,Vec_Int_t * vRootLits)127 Vec_Int_t * Acec_BuildTree( Gia_Man_t * pNew, Gia_Man_t * p, Vec_Wec_t * vLeafLits, Vec_Int_t * vRootLits )
128 {
129     Vec_Wec_t * vLeafMap = Vec_WecStart( Vec_WecSize(vLeafLits) );
130     Vec_Int_t * vLevel, * vRootRanks;
131     int i, k, iLit, iLitNew;
132     // add roo literals
133     if ( vRootLits )
134         Vec_IntForEachEntry( vRootLits, iLit, i )
135         {
136             if ( i < Vec_WecSize(vLeafMap) )
137                 vLevel = Vec_WecEntry(vLeafMap, i);
138             else
139                 vLevel = Vec_WecPushLevel(vLeafMap);
140             Vec_IntPush( vLevel, iLit );
141         }
142     // add other literals
143     Vec_WecForEachLevel( vLeafLits, vLevel, i )
144         Vec_IntForEachEntry( vLevel, iLit, k )
145         {
146             Gia_Obj_t * pObj = Gia_ManObj( p, Abc_Lit2Var(iLit) );
147             iLitNew = Acec_InsertBox_rec( pNew, p, pObj );
148             iLitNew = Abc_LitNotCond( iLitNew, Abc_LitIsCompl(iLit) );
149             Vec_WecPush( vLeafMap, i, iLitNew );
150         }
151     // construct map of root literals
152     vRootRanks = Acec_InsertTree( pNew, vLeafMap );
153     Vec_WecFree( vLeafMap );
154     return vRootRanks;
155 }
Acec_InsertBox(Acec_Box_t * pBox,int fAll)156 Gia_Man_t * Acec_InsertBox( Acec_Box_t * pBox, int fAll )
157 {
158     Gia_Man_t * p = pBox->pGia;
159     Gia_Man_t * pNew;
160     Gia_Obj_t * pObj;
161     Vec_Int_t * vRootRanks, * vLevel, * vTemp;
162     int i, k, iLit, iLitNew;
163     pNew = Gia_ManStart( Gia_ManObjNum(p) );
164     pNew->pName = Abc_UtilStrsav( p->pName );
165     pNew->pSpec = Abc_UtilStrsav( p->pSpec );
166     Gia_ManFillValue(p);
167     Gia_ManConst0(p)->Value = 0;
168     Gia_ManForEachCi( p, pObj, i )
169         pObj->Value = Gia_ManAppendCi( pNew );
170     // implement tree
171     if ( fAll )
172         vRootRanks = Acec_BuildTree( pNew, p, pBox->vLeafLits, NULL );
173     else
174     {
175         assert( pBox->vShared != NULL );
176         assert( pBox->vUnique != NULL );
177         vRootRanks = Acec_BuildTree( pNew, p, pBox->vShared, NULL );
178         vRootRanks = Acec_BuildTree( pNew, p, pBox->vUnique, vTemp = vRootRanks );
179         Vec_IntFree( vTemp );
180     }
181     // update polarity of literals
182     Vec_WecForEachLevel( pBox->vRootLits, vLevel, i )
183         Vec_IntForEachEntry( vLevel, iLit, k )
184         {
185             pObj = Gia_ManObj( p, Abc_Lit2Var(iLit) );
186             iLitNew = k ? 0 : Vec_IntEntry( vRootRanks, i );
187             pObj->Value = Abc_LitNotCond( iLitNew, Abc_LitIsCompl(iLit) );
188         }
189     Vec_IntFree( vRootRanks );
190     // construct the outputs
191     Gia_ManForEachCo( p, pObj, i )
192         Acec_InsertBox_rec( pNew, p, Gia_ObjFanin0(pObj) );
193     Gia_ManForEachCo( p, pObj, i )
194         pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
195     Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
196     return pNew;
197 }
198 
199 /**Function*************************************************************
200 
201   Synopsis    []
202 
203   Description []
204 
205   SideEffects []
206 
207   SeeAlso     []
208 
209 ***********************************************************************/
Acec_Normalize(Gia_Man_t * pGia,int fBooth,int fVerbose)210 Gia_Man_t * Acec_Normalize( Gia_Man_t * pGia, int fBooth, int fVerbose )
211 {
212     Vec_Bit_t * vIgnore = fBooth ? Acec_BoothFindPPG( pGia ) : NULL;
213     Acec_Box_t * pBox = Acec_DeriveBox( pGia, vIgnore, 0, 0, fVerbose );
214     Gia_Man_t * pNew  = Acec_InsertBox( pBox, 1 );
215     Acec_BoxFreeP( &pBox );
216     Vec_BitFreeP( &vIgnore );
217     return pNew;
218 }
219 
220 ////////////////////////////////////////////////////////////////////////
221 ///                       END OF FILE                                ///
222 ////////////////////////////////////////////////////////////////////////
223 
224 
225 ABC_NAMESPACE_IMPL_END
226 
227