1 /**CFile****************************************************************
2
3 FileName [hopOper.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Minimalistic And-Inverter Graph package.]
8
9 Synopsis [AIG operations.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - May 11, 2006.]
16
17 Revision [$Id: hopOper.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "hop.h"
22
23 ABC_NAMESPACE_IMPL_START
24
25
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29
30 // procedure to detect an EXOR gate
Hop_ObjIsExorType(Hop_Obj_t * p0,Hop_Obj_t * p1,Hop_Obj_t ** ppFan0,Hop_Obj_t ** ppFan1)31 static inline int Hop_ObjIsExorType( Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Obj_t ** ppFan0, Hop_Obj_t ** ppFan1 )
32 {
33 if ( !Hop_IsComplement(p0) || !Hop_IsComplement(p1) )
34 return 0;
35 p0 = Hop_Regular(p0);
36 p1 = Hop_Regular(p1);
37 if ( !Hop_ObjIsAnd(p0) || !Hop_ObjIsAnd(p1) )
38 return 0;
39 if ( Hop_ObjFanin0(p0) != Hop_ObjFanin0(p1) || Hop_ObjFanin1(p0) != Hop_ObjFanin1(p1) )
40 return 0;
41 if ( Hop_ObjFaninC0(p0) == Hop_ObjFaninC0(p1) || Hop_ObjFaninC1(p0) == Hop_ObjFaninC1(p1) )
42 return 0;
43 *ppFan0 = Hop_ObjChild0(p0);
44 *ppFan1 = Hop_ObjChild1(p0);
45 return 1;
46 }
47
48 ////////////////////////////////////////////////////////////////////////
49 /// FUNCTION DEFINITIONS ///
50 ////////////////////////////////////////////////////////////////////////
51
52 /**Function*************************************************************
53
54 Synopsis [Returns i-th elementary variable.]
55
56 Description []
57
58 SideEffects []
59
60 SeeAlso []
61
62 ***********************************************************************/
Hop_IthVar(Hop_Man_t * p,int i)63 Hop_Obj_t * Hop_IthVar( Hop_Man_t * p, int i )
64 {
65 int v;
66 for ( v = Hop_ManPiNum(p); v <= i; v++ )
67 Hop_ObjCreatePi( p );
68 assert( i < Vec_PtrSize(p->vPis) );
69 return Hop_ManPi( p, i );
70 }
71
72 /**Function*************************************************************
73
74 Synopsis [Perform one operation.]
75
76 Description [The argument nodes can be complemented.]
77
78 SideEffects []
79
80 SeeAlso []
81
82 ***********************************************************************/
Hop_Oper(Hop_Man_t * p,Hop_Obj_t * p0,Hop_Obj_t * p1,Hop_Type_t Type)83 Hop_Obj_t * Hop_Oper( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Type_t Type )
84 {
85 if ( Type == AIG_AND )
86 return Hop_And( p, p0, p1 );
87 if ( Type == AIG_EXOR )
88 return Hop_Exor( p, p0, p1 );
89 assert( 0 );
90 return NULL;
91 }
92
93 /**Function*************************************************************
94
95 Synopsis [Performs canonicization step.]
96
97 Description [The argument nodes can be complemented.]
98
99 SideEffects []
100
101 SeeAlso []
102
103 ***********************************************************************/
Hop_And(Hop_Man_t * p,Hop_Obj_t * p0,Hop_Obj_t * p1)104 Hop_Obj_t * Hop_And( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
105 {
106 Hop_Obj_t * pGhost, * pResult;
107 // Hop_Obj_t * pFan0, * pFan1;
108 // check trivial cases
109 if ( p0 == p1 )
110 return p0;
111 if ( p0 == Hop_Not(p1) )
112 return Hop_Not(p->pConst1);
113 if ( Hop_Regular(p0) == p->pConst1 )
114 return p0 == p->pConst1 ? p1 : Hop_Not(p->pConst1);
115 if ( Hop_Regular(p1) == p->pConst1 )
116 return p1 == p->pConst1 ? p0 : Hop_Not(p->pConst1);
117 // check if it can be an EXOR gate
118 // if ( Hop_ObjIsExorType( p0, p1, &pFan0, &pFan1 ) )
119 // return Hop_Exor( p, pFan0, pFan1 );
120 // check the table
121 pGhost = Hop_ObjCreateGhost( p, p0, p1, AIG_AND );
122 if ( (pResult = Hop_TableLookup( p, pGhost )) )
123 return pResult;
124 return Hop_ObjCreate( p, pGhost );
125 }
126
127 /**Function*************************************************************
128
129 Synopsis [Performs canonicization step.]
130
131 Description [The argument nodes can be complemented.]
132
133 SideEffects []
134
135 SeeAlso []
136
137 ***********************************************************************/
Hop_Exor(Hop_Man_t * p,Hop_Obj_t * p0,Hop_Obj_t * p1)138 Hop_Obj_t * Hop_Exor( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
139 {
140 /*
141 Hop_Obj_t * pGhost, * pResult;
142 // check trivial cases
143 if ( p0 == p1 )
144 return Hop_Not(p->pConst1);
145 if ( p0 == Hop_Not(p1) )
146 return p->pConst1;
147 if ( Hop_Regular(p0) == p->pConst1 )
148 return Hop_NotCond( p1, p0 == p->pConst1 );
149 if ( Hop_Regular(p1) == p->pConst1 )
150 return Hop_NotCond( p0, p1 == p->pConst1 );
151 // check the table
152 pGhost = Hop_ObjCreateGhost( p, p0, p1, AIG_EXOR );
153 if ( pResult = Hop_TableLookup( p, pGhost ) )
154 return pResult;
155 return Hop_ObjCreate( p, pGhost );
156 */
157 return Hop_Or( p, Hop_And(p, p0, Hop_Not(p1)), Hop_And(p, Hop_Not(p0), p1) );
158 }
159
160 /**Function*************************************************************
161
162 Synopsis [Implements Boolean OR.]
163
164 Description []
165
166 SideEffects []
167
168 SeeAlso []
169
170 ***********************************************************************/
Hop_Or(Hop_Man_t * p,Hop_Obj_t * p0,Hop_Obj_t * p1)171 Hop_Obj_t * Hop_Or( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
172 {
173 return Hop_Not( Hop_And( p, Hop_Not(p0), Hop_Not(p1) ) );
174 }
175
176 /**Function*************************************************************
177
178 Synopsis [Implements ITE operation.]
179
180 Description []
181
182 SideEffects []
183
184 SeeAlso []
185
186 ***********************************************************************/
Hop_Mux(Hop_Man_t * p,Hop_Obj_t * pC,Hop_Obj_t * p1,Hop_Obj_t * p0)187 Hop_Obj_t * Hop_Mux( Hop_Man_t * p, Hop_Obj_t * pC, Hop_Obj_t * p1, Hop_Obj_t * p0 )
188 {
189 /*
190 Hop_Obj_t * pTempA1, * pTempA2, * pTempB1, * pTempB2, * pTemp;
191 int Count0, Count1;
192 // consider trivial cases
193 if ( p0 == Hop_Not(p1) )
194 return Hop_Exor( p, pC, p0 );
195 // other cases can be added
196 // implement the first MUX (F = C * x1 + C' * x0)
197
198 // check for constants here!!!
199
200 pTempA1 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, pC, p1, AIG_AND) );
201 pTempA2 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pC), p0, AIG_AND) );
202 if ( pTempA1 && pTempA2 )
203 {
204 pTemp = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pTempA1), Hop_Not(pTempA2), AIG_AND) );
205 if ( pTemp ) return Hop_Not(pTemp);
206 }
207 Count0 = (pTempA1 != NULL) + (pTempA2 != NULL);
208 // implement the second MUX (F' = C * x1' + C' * x0')
209 pTempB1 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, pC, Hop_Not(p1), AIG_AND) );
210 pTempB2 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pC), Hop_Not(p0), AIG_AND) );
211 if ( pTempB1 && pTempB2 )
212 {
213 pTemp = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pTempB1), Hop_Not(pTempB2), AIG_AND) );
214 if ( pTemp ) return pTemp;
215 }
216 Count1 = (pTempB1 != NULL) + (pTempB2 != NULL);
217 // compare and decide which one to implement
218 if ( Count0 >= Count1 )
219 {
220 pTempA1 = pTempA1? pTempA1 : Hop_And(p, pC, p1);
221 pTempA2 = pTempA2? pTempA2 : Hop_And(p, Hop_Not(pC), p0);
222 return Hop_Or( p, pTempA1, pTempA2 );
223 }
224 pTempB1 = pTempB1? pTempB1 : Hop_And(p, pC, Hop_Not(p1));
225 pTempB2 = pTempB2? pTempB2 : Hop_And(p, Hop_Not(pC), Hop_Not(p0));
226 return Hop_Not( Hop_Or( p, pTempB1, pTempB2 ) );
227 */
228 return Hop_Or( p, Hop_And(p, pC, p1), Hop_And(p, Hop_Not(pC), p0) );
229 }
230
231 /**Function*************************************************************
232
233 Synopsis [Implements ITE operation.]
234
235 Description []
236
237 SideEffects []
238
239 SeeAlso []
240
241 ***********************************************************************/
Hop_Maj(Hop_Man_t * p,Hop_Obj_t * pA,Hop_Obj_t * pB,Hop_Obj_t * pC)242 Hop_Obj_t * Hop_Maj( Hop_Man_t * p, Hop_Obj_t * pA, Hop_Obj_t * pB, Hop_Obj_t * pC )
243 {
244 return Hop_Or( p, Hop_Or(p, Hop_And(p, pA, pB), Hop_And(p, pA, pC)), Hop_And(p, pB, pC) );
245 }
246
247 /**Function*************************************************************
248
249 Synopsis [Constructs the well-balanced tree of gates.]
250
251 Description [Disregards levels and possible logic sharing.]
252
253 SideEffects []
254
255 SeeAlso []
256
257 ***********************************************************************/
Hop_Multi_rec(Hop_Man_t * p,Hop_Obj_t ** ppObjs,int nObjs,Hop_Type_t Type)258 Hop_Obj_t * Hop_Multi_rec( Hop_Man_t * p, Hop_Obj_t ** ppObjs, int nObjs, Hop_Type_t Type )
259 {
260 Hop_Obj_t * pObj1, * pObj2;
261 if ( nObjs == 1 )
262 return ppObjs[0];
263 pObj1 = Hop_Multi_rec( p, ppObjs, nObjs/2, Type );
264 pObj2 = Hop_Multi_rec( p, ppObjs + nObjs/2, nObjs - nObjs/2, Type );
265 return Hop_Oper( p, pObj1, pObj2, Type );
266 }
267
268 /**Function*************************************************************
269
270 Synopsis [Old code.]
271
272 Description []
273
274 SideEffects []
275
276 SeeAlso []
277
278 ***********************************************************************/
Hop_Multi(Hop_Man_t * p,Hop_Obj_t ** pArgs,int nArgs,Hop_Type_t Type)279 Hop_Obj_t * Hop_Multi( Hop_Man_t * p, Hop_Obj_t ** pArgs, int nArgs, Hop_Type_t Type )
280 {
281 assert( Type == AIG_AND || Type == AIG_EXOR );
282 assert( nArgs > 0 );
283 return Hop_Multi_rec( p, pArgs, nArgs, Type );
284 }
285
286 /**Function*************************************************************
287
288 Synopsis [Implements the miter.]
289
290 Description []
291
292 SideEffects []
293
294 SeeAlso []
295
296 ***********************************************************************/
Hop_Miter(Hop_Man_t * p,Vec_Ptr_t * vPairs)297 Hop_Obj_t * Hop_Miter( Hop_Man_t * p, Vec_Ptr_t * vPairs )
298 {
299 int i;
300 assert( vPairs->nSize > 0 );
301 assert( vPairs->nSize % 2 == 0 );
302 // go through the cubes of the node's SOP
303 for ( i = 0; i < vPairs->nSize; i += 2 )
304 vPairs->pArray[i/2] = Hop_Not( Hop_Exor( p, (Hop_Obj_t *)vPairs->pArray[i], (Hop_Obj_t *)vPairs->pArray[i+1] ) );
305 vPairs->nSize = vPairs->nSize/2;
306 return Hop_Not( Hop_Multi_rec( p, (Hop_Obj_t **)vPairs->pArray, vPairs->nSize, AIG_AND ) );
307 }
308
309 /**Function*************************************************************
310
311 Synopsis [Creates AND function with nVars inputs.]
312
313 Description []
314
315 SideEffects []
316
317 SeeAlso []
318
319 ***********************************************************************/
Hop_CreateAnd(Hop_Man_t * p,int nVars)320 Hop_Obj_t * Hop_CreateAnd( Hop_Man_t * p, int nVars )
321 {
322 Hop_Obj_t * pFunc;
323 int i;
324 pFunc = Hop_ManConst1( p );
325 for ( i = 0; i < nVars; i++ )
326 pFunc = Hop_And( p, pFunc, Hop_IthVar(p, i) );
327 return pFunc;
328 }
329
330 /**Function*************************************************************
331
332 Synopsis [Creates AND function with nVars inputs.]
333
334 Description []
335
336 SideEffects []
337
338 SeeAlso []
339
340 ***********************************************************************/
Hop_CreateOr(Hop_Man_t * p,int nVars)341 Hop_Obj_t * Hop_CreateOr( Hop_Man_t * p, int nVars )
342 {
343 Hop_Obj_t * pFunc;
344 int i;
345 pFunc = Hop_ManConst0( p );
346 for ( i = 0; i < nVars; i++ )
347 pFunc = Hop_Or( p, pFunc, Hop_IthVar(p, i) );
348 return pFunc;
349 }
350
351 /**Function*************************************************************
352
353 Synopsis [Creates AND function with nVars inputs.]
354
355 Description []
356
357 SideEffects []
358
359 SeeAlso []
360
361 ***********************************************************************/
Hop_CreateExor(Hop_Man_t * p,int nVars)362 Hop_Obj_t * Hop_CreateExor( Hop_Man_t * p, int nVars )
363 {
364 Hop_Obj_t * pFunc;
365 int i;
366 pFunc = Hop_ManConst0( p );
367 for ( i = 0; i < nVars; i++ )
368 pFunc = Hop_Exor( p, pFunc, Hop_IthVar(p, i) );
369 return pFunc;
370 }
371
372 ////////////////////////////////////////////////////////////////////////
373 /// END OF FILE ///
374 ////////////////////////////////////////////////////////////////////////
375
376
377 ABC_NAMESPACE_IMPL_END
378
379