1 /**CFile****************************************************************
2
3 FileName [cutNode.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [K-feasible cut computation package.]
8
9 Synopsis [Procedures to compute cuts for a node.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: cutNode.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "cutInt.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 [Allocates the cut.]
37
38 Description []
39
40 SideEffects []
41
42 SeeAlso []
43
44 ***********************************************************************/
Cut_CutAlloc(Cut_Man_t * p)45 Cut_Cut_t * Cut_CutAlloc( Cut_Man_t * p )
46 {
47 Cut_Cut_t * pCut;
48 // cut allocation
49 pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts );
50 memset( pCut, 0, sizeof(Cut_Cut_t) );
51 pCut->nVarsMax = p->pParams->nVarsMax;
52 pCut->fSimul = p->fSimul;
53 // statistics
54 p->nCutsAlloc++;
55 p->nCutsCur++;
56 if ( p->nCutsPeak < p->nCutsAlloc - p->nCutsDealloc )
57 p->nCutsPeak = p->nCutsAlloc - p->nCutsDealloc;
58 return pCut;
59 }
60
61 /**Function*************************************************************
62
63 Synopsis [Recybles the cut.]
64
65 Description []
66
67 SideEffects []
68
69 SeeAlso []
70
71 ***********************************************************************/
Cut_CutRecycle(Cut_Man_t * p,Cut_Cut_t * pCut)72 void Cut_CutRecycle( Cut_Man_t * p, Cut_Cut_t * pCut )
73 {
74 p->nCutsDealloc++;
75 p->nCutsCur--;
76 if ( pCut->nLeaves == 1 )
77 p->nCutsTriv--;
78 Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut );
79 }
80
81 /**Function*************************************************************
82
83 Synopsis [Compares two cuts.]
84
85 Description []
86
87 SideEffects []
88
89 SeeAlso []
90
91 ***********************************************************************/
Cut_CutCompare(Cut_Cut_t * pCut1,Cut_Cut_t * pCut2)92 int Cut_CutCompare( Cut_Cut_t * pCut1, Cut_Cut_t * pCut2 )
93 {
94 int i;
95 if ( pCut1->nLeaves < pCut2->nLeaves )
96 return -1;
97 if ( pCut1->nLeaves > pCut2->nLeaves )
98 return 1;
99 for ( i = 0; i < (int)pCut1->nLeaves; i++ )
100 {
101 if ( pCut1->pLeaves[i] < pCut2->pLeaves[i] )
102 return -1;
103 if ( pCut1->pLeaves[i] > pCut2->pLeaves[i] )
104 return 1;
105 }
106 return 0;
107 }
108
109 /**Function*************************************************************
110
111 Synopsis [Duplicates the list.]
112
113 Description []
114
115 SideEffects []
116
117 SeeAlso []
118
119 ***********************************************************************/
Cut_CutDupList(Cut_Man_t * p,Cut_Cut_t * pList)120 Cut_Cut_t * Cut_CutDupList( Cut_Man_t * p, Cut_Cut_t * pList )
121 {
122 Cut_Cut_t * pHead = NULL, ** ppTail = &pHead;
123 Cut_Cut_t * pTemp, * pCopy;
124 if ( pList == NULL )
125 return NULL;
126 Cut_ListForEachCut( pList, pTemp )
127 {
128 pCopy = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts );
129 memcpy( pCopy, pTemp, (size_t)p->EntrySize );
130 *ppTail = pCopy;
131 ppTail = &pCopy->pNext;
132 }
133 *ppTail = NULL;
134 return pHead;
135 }
136
137 /**Function*************************************************************
138
139 Synopsis [Recycles the list.]
140
141 Description []
142
143 SideEffects []
144
145 SeeAlso []
146
147 ***********************************************************************/
Cut_CutRecycleList(Cut_Man_t * p,Cut_Cut_t * pList)148 void Cut_CutRecycleList( Cut_Man_t * p, Cut_Cut_t * pList )
149 {
150 Cut_Cut_t * pCut, * pCut2;
151 Cut_ListForEachCutSafe( pList, pCut, pCut2 )
152 Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut );
153 }
154
155 /**Function*************************************************************
156
157 Synopsis [Counts the number of cuts in the list.]
158
159 Description []
160
161 SideEffects []
162
163 SeeAlso []
164
165 ***********************************************************************/
Cut_CutCountList(Cut_Cut_t * pList)166 int Cut_CutCountList( Cut_Cut_t * pList )
167 {
168 int Counter = 0;
169 Cut_ListForEachCut( pList, pList )
170 Counter++;
171 return Counter;
172 }
173
174 /**Function*************************************************************
175
176 Synopsis [Merges two NULL-terminated linked lists.]
177
178 Description []
179
180 SideEffects []
181
182 SeeAlso []
183
184 ***********************************************************************/
Cut_CutMergeLists(Cut_Cut_t * pList1,Cut_Cut_t * pList2)185 Cut_Cut_t * Cut_CutMergeLists( Cut_Cut_t * pList1, Cut_Cut_t * pList2 )
186 {
187 Cut_Cut_t * pList = NULL, ** ppTail = &pList;
188 Cut_Cut_t * pCut;
189 while ( pList1 && pList2 )
190 {
191 if ( Cut_CutCompare(pList1, pList2) < 0 )
192 {
193 pCut = pList1;
194 pList1 = pList1->pNext;
195 }
196 else
197 {
198 pCut = pList2;
199 pList2 = pList2->pNext;
200 }
201 *ppTail = pCut;
202 ppTail = &pCut->pNext;
203 }
204 *ppTail = pList1? pList1: pList2;
205 return pList;
206 }
207
208 /**Function*************************************************************
209
210 Synopsis [Sets the number of the cuts in the list.]
211
212 Description []
213
214 SideEffects []
215
216 SeeAlso []
217
218 ***********************************************************************/
Cut_CutNumberList(Cut_Cut_t * pList)219 void Cut_CutNumberList( Cut_Cut_t * pList )
220 {
221 Cut_Cut_t * pCut;
222 int i = 0;
223 Cut_ListForEachCut( pList, pCut )
224 pCut->Num0 = i++;
225 }
226
227 /**Function*************************************************************
228
229 Synopsis [Creates the trivial cut.]
230
231 Description []
232
233 SideEffects []
234
235 SeeAlso []
236
237 ***********************************************************************/
Cut_CutCreateTriv(Cut_Man_t * p,int Node)238 Cut_Cut_t * Cut_CutCreateTriv( Cut_Man_t * p, int Node )
239 {
240 Cut_Cut_t * pCut;
241 if ( p->pParams->fSeq )
242 Node <<= CUT_SHIFT;
243 pCut = Cut_CutAlloc( p );
244 pCut->nLeaves = 1;
245 pCut->pLeaves[0] = Node;
246 pCut->uSign = Cut_NodeSign( Node );
247 if ( p->pParams->fTruth )
248 {
249 /*
250 if ( pCut->nVarsMax == 4 )
251 Cut_CutWriteTruth( pCut, p->uTruthVars[0] );
252 else
253 Extra_BitCopy( pCut->nLeaves, p->uTruths[0], (uint8*)Cut_CutReadTruth(pCut) );
254 */
255 unsigned * pTruth = Cut_CutReadTruth(pCut);
256 int i;
257 for ( i = 0; i < p->nTruthWords; i++ )
258 pTruth[i] = 0xAAAAAAAA;
259 }
260 p->nCutsTriv++;
261 return pCut;
262 }
263
264
265 /**Function*************************************************************
266
267 Synopsis [Print the cut.]
268
269 Description []
270
271 SideEffects []
272
273 SeeAlso []
274
275 ***********************************************************************/
Cut_CutPrint(Cut_Cut_t * pCut,int fSeq)276 void Cut_CutPrint( Cut_Cut_t * pCut, int fSeq )
277 {
278 int i;
279 assert( pCut->nLeaves > 0 );
280 printf( "%d : {", pCut->nLeaves );
281 for ( i = 0; i < (int)pCut->nLeaves; i++ )
282 {
283 if ( fSeq )
284 {
285 printf( " %d", pCut->pLeaves[i] >> CUT_SHIFT );
286 if ( pCut->pLeaves[i] & CUT_MASK )
287 printf( "(%d)", pCut->pLeaves[i] & CUT_MASK );
288 }
289 else
290 printf( " %d", pCut->pLeaves[i] );
291 }
292 printf( " }" );
293 // printf( "\nSign = " );
294 // Extra_PrintBinary( stdout, &pCut->uSign, 32 );
295 }
296
297 /**Function*************************************************************
298
299 Synopsis [Print the cut.]
300
301 Description []
302
303 SideEffects []
304
305 SeeAlso []
306
307 ***********************************************************************/
Cut_CutPrintList(Cut_Cut_t * pList,int fSeq)308 void Cut_CutPrintList( Cut_Cut_t * pList, int fSeq )
309 {
310 Cut_Cut_t * pCut;
311 for ( pCut = pList; pCut; pCut = pCut->pNext )
312 Cut_CutPrint( pCut, fSeq ), printf( "\n" );
313 }
314
315 /**Function*************************************************************
316
317 Synopsis [Consider dropping cuts if they are useless by now.]
318
319 Description []
320
321 SideEffects []
322
323 SeeAlso []
324
325 ***********************************************************************/
Cut_CutPrintMerge(Cut_Cut_t * pCut,Cut_Cut_t * pCut0,Cut_Cut_t * pCut1)326 void Cut_CutPrintMerge( Cut_Cut_t * pCut, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
327 {
328 printf( "\n" );
329 printf( "%d : %5d %5d %5d %5d %5d\n",
330 pCut0->nLeaves,
331 pCut0->nLeaves > 0 ? pCut0->pLeaves[0] : -1,
332 pCut0->nLeaves > 1 ? pCut0->pLeaves[1] : -1,
333 pCut0->nLeaves > 2 ? pCut0->pLeaves[2] : -1,
334 pCut0->nLeaves > 3 ? pCut0->pLeaves[3] : -1,
335 pCut0->nLeaves > 4 ? pCut0->pLeaves[4] : -1
336 );
337 printf( "%d : %5d %5d %5d %5d %5d\n",
338 pCut1->nLeaves,
339 pCut1->nLeaves > 0 ? pCut1->pLeaves[0] : -1,
340 pCut1->nLeaves > 1 ? pCut1->pLeaves[1] : -1,
341 pCut1->nLeaves > 2 ? pCut1->pLeaves[2] : -1,
342 pCut1->nLeaves > 3 ? pCut1->pLeaves[3] : -1,
343 pCut1->nLeaves > 4 ? pCut1->pLeaves[4] : -1
344 );
345 if ( pCut == NULL )
346 printf( "Cannot merge\n" );
347 else
348 printf( "%d : %5d %5d %5d %5d %5d\n",
349 pCut->nLeaves,
350 pCut->nLeaves > 0 ? pCut->pLeaves[0] : -1,
351 pCut->nLeaves > 1 ? pCut->pLeaves[1] : -1,
352 pCut->nLeaves > 2 ? pCut->pLeaves[2] : -1,
353 pCut->nLeaves > 3 ? pCut->pLeaves[3] : -1,
354 pCut->nLeaves > 4 ? pCut->pLeaves[4] : -1
355 );
356 }
357
358 ////////////////////////////////////////////////////////////////////////
359 /// END OF FILE ///
360 ////////////////////////////////////////////////////////////////////////
361
362
363 ABC_NAMESPACE_IMPL_END
364
365