abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
mapperTruth.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [mapperTruth.c]
4 
5  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
6 
7  Synopsis [Generic technology mapping engine.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 2.0. Started - June 1, 2004.]
14 
15  Revision [$Id: mapperTruth.c,v 1.8 2005/01/23 06:59:45 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "mapperInt.h"
20 
22 
23 
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27 
28 static void Map_TruthsCut( Map_Man_t * pMan, Map_Cut_t * pCut );
29 extern void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] );
30 static void Map_CutsCollect_rec( Map_Cut_t * pCut, Map_NodeVec_t * vVisited );
31 
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35 
36 /**Function*************************************************************
37 
38  Synopsis [Derives truth tables for each cut.]
39 
40  Description []
41 
42  SideEffects []
43 
44  SeeAlso []
45 
46 ***********************************************************************/
48 {
49  ProgressBar * pProgress;
50  Map_Node_t * pNode;
51  Map_Cut_t * pCut;
52  int nNodes, i;
53  // compute the cuts for the POs
54  nNodes = pMan->vMapObjs->nSize;
55  pProgress = Extra_ProgressBarStart( stdout, nNodes );
56  for ( i = 0; i < nNodes; i++ )
57  {
58  pNode = pMan->vMapObjs->pArray[i];
59  if ( !Map_NodeIsAnd( pNode ) )
60  continue;
61  assert( pNode->pCuts );
62  assert( pNode->pCuts->nLeaves == 1 );
63 
64  // match the simple cut
65  pNode->pCuts->M[0].uPhase = 0;
66  pNode->pCuts->M[0].pSupers = pMan->pSuperLib->pSuperInv;
67  pNode->pCuts->M[0].uPhaseBest = 0;
68  pNode->pCuts->M[0].pSuperBest = pMan->pSuperLib->pSuperInv;
69 
70  pNode->pCuts->M[1].uPhase = 0;
71  pNode->pCuts->M[1].pSupers = pMan->pSuperLib->pSuperInv;
72  pNode->pCuts->M[1].uPhaseBest = 1;
73  pNode->pCuts->M[1].pSuperBest = pMan->pSuperLib->pSuperInv;
74 
75  // match the rest of the cuts
76  for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
77  Map_TruthsCut( pMan, pCut );
78  Extra_ProgressBarUpdate( pProgress, i, "Tables ..." );
79  }
80  Extra_ProgressBarStop( pProgress );
81 }
82 
83 /**Function*************************************************************
84 
85  Synopsis [Derives the truth table for one cut.]
86 
87  Description []
88 
89  SideEffects []
90 
91  SeeAlso []
92 
93 ***********************************************************************/
95 {
96 // unsigned uCanon1, uCanon2;
97  unsigned uTruth[2], uCanon[2];
98  unsigned char uPhases[16];
99  unsigned * uCanon2;
100  char * pPhases2;
101  int fUseFast = 1;
102  int fUseSlow = 0;
103  int fUseRec = 0; // this does not work for Solaris
104 
105  extern int Map_CanonCompute( int nVarsMax, int nVarsReal, unsigned * pt, unsigned ** pptRes, char ** ppfRes );
106 
107  // generally speaking, 1-input cut can be matched into a wire!
108  if ( pCut->nLeaves == 1 )
109  return;
110 /*
111  if ( p->nVarsMax == 5 )
112  {
113  uTruth[0] = pCut->uTruth;
114  uTruth[1] = pCut->uTruth;
115  }
116  else
117 */
118  Map_TruthsCutOne( p, pCut, uTruth );
119 
120 
121  // compute the canonical form for the positive phase
122  if ( fUseFast )
123  Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
124  else if ( fUseSlow )
125  Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
126  else if ( fUseRec )
127  {
128 // Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
129  Extra_TruthCanonFastN( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
130 /*
131  if ( uCanon[0] != uCanon2[0] || uPhases[0] != pPhases2[0] )
132  {
133  int k = 0;
134  Map_CanonCompute( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
135  }
136 */
137  uCanon[0] = uCanon2[0];
138  uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0];
139  uPhases[0] = pPhases2[0];
140  }
141  else
142  Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
143  pCut->M[1].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon );
144  pCut->M[1].uPhase = uPhases[0];
145  p->nCanons++;
146 
147 //uCanon1 = uCanon[0] & 0xFFFF;
148 
149  // compute the canonical form for the negative phase
150  uTruth[0] = ~uTruth[0];
151  uTruth[1] = ~uTruth[1];
152  if ( fUseFast )
153  Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
154  else if ( fUseSlow )
155  Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
156  else if ( fUseRec )
157  {
158 // Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
159  Extra_TruthCanonFastN( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
160 /*
161  if ( uCanon[0] != uCanon2[0] || uPhases[0] != pPhases2[0] )
162  {
163  int k = 0;
164  Map_CanonCompute( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
165  }
166 */
167  uCanon[0] = uCanon2[0];
168  uCanon[1] = (p->nVarsMax == 6)? uCanon2[1] : uCanon2[0];
169  uPhases[0] = pPhases2[0];
170  }
171  else
172  Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
173  pCut->M[0].pSupers = Map_SuperTableLookupC( p->pSuperLib, uCanon );
174  pCut->M[0].uPhase = uPhases[0];
175  p->nCanons++;
176 
177 //uCanon2 = uCanon[0] & 0xFFFF;
178 //assert( p->nVarsMax == 4 );
179 //Rwt_Man4ExploreCount( uCanon1 < uCanon2 ? uCanon1 : uCanon2 );
180 
181  // restore the truth table
182  uTruth[0] = ~uTruth[0];
183  uTruth[1] = ~uTruth[1];
184 }
185 
186 /**Function*************************************************************
187 
188  Synopsis [Computes the truth table of one cut.]
189 
190  Description []
191 
192  SideEffects []
193 
194  SeeAlso []
195 
196 ***********************************************************************/
197 void Map_TruthsCutOne( Map_Man_t * p, Map_Cut_t * pCut, unsigned uTruth[] )
198 {
199  unsigned uTruth1[2], uTruth2[2];
200  Map_Cut_t * pTemp = NULL; // Suppress "might be used uninitialized"
201  int i;
202  // mark the cut leaves
203  for ( i = 0; i < pCut->nLeaves; i++ )
204  {
205  pTemp = pCut->ppLeaves[i]->pCuts;
206  pTemp->fMark = 1;
207  pTemp->M[0].uPhaseBest = p->uTruths[i][0];
208  pTemp->M[1].uPhaseBest = p->uTruths[i][1];
209  }
210  assert( pCut->fMark == 0 );
211 
212  // collect the cuts in the cut cone
213  p->vVisited->nSize = 0;
214  Map_CutsCollect_rec( pCut, p->vVisited );
215  assert( p->vVisited->nSize > 0 );
216  pCut->nVolume = p->vVisited->nSize;
217 
218  // compute the tables and unmark
219  for ( i = 0; i < pCut->nLeaves; i++ )
220  {
221  pTemp = pCut->ppLeaves[i]->pCuts;
222  pTemp->fMark = 0;
223  }
224  for ( i = 0; i < p->vVisited->nSize; i++ )
225  {
226  // get the cut
227  pTemp = (Map_Cut_t *)p->vVisited->pArray[i];
228  pTemp->fMark = 0;
229  // get truth table of the first branch
230  if ( Map_CutIsComplement(pTemp->pOne) )
231  {
232  uTruth1[0] = ~Map_CutRegular(pTemp->pOne)->M[0].uPhaseBest;
233  uTruth1[1] = ~Map_CutRegular(pTemp->pOne)->M[1].uPhaseBest;
234  }
235  else
236  {
237  uTruth1[0] = Map_CutRegular(pTemp->pOne)->M[0].uPhaseBest;
238  uTruth1[1] = Map_CutRegular(pTemp->pOne)->M[1].uPhaseBest;
239  }
240  // get truth table of the second branch
241  if ( Map_CutIsComplement(pTemp->pTwo) )
242  {
243  uTruth2[0] = ~Map_CutRegular(pTemp->pTwo)->M[0].uPhaseBest;
244  uTruth2[1] = ~Map_CutRegular(pTemp->pTwo)->M[1].uPhaseBest;
245  }
246  else
247  {
248  uTruth2[0] = Map_CutRegular(pTemp->pTwo)->M[0].uPhaseBest;
249  uTruth2[1] = Map_CutRegular(pTemp->pTwo)->M[1].uPhaseBest;
250  }
251  // get the truth table of the output
252  if ( !pTemp->Phase )
253  {
254  pTemp->M[0].uPhaseBest = uTruth1[0] & uTruth2[0];
255  pTemp->M[1].uPhaseBest = uTruth1[1] & uTruth2[1];
256  }
257  else
258  {
259  pTemp->M[0].uPhaseBest = ~(uTruth1[0] & uTruth2[0]);
260  pTemp->M[1].uPhaseBest = ~(uTruth1[1] & uTruth2[1]);
261  }
262  }
263  uTruth[0] = pTemp->M[0].uPhaseBest;
264  uTruth[1] = pTemp->M[1].uPhaseBest;
265 }
266 
267 /**Function*************************************************************
268 
269  Synopsis [Recursively collect the cuts.]
270 
271  Description []
272 
273  SideEffects []
274 
275  SeeAlso []
276 
277 ***********************************************************************/
278 void Map_CutsCollect_rec( Map_Cut_t * pCut, Map_NodeVec_t * vVisited )
279 {
280  if ( pCut->fMark )
281  return;
282  Map_CutsCollect_rec( Map_CutRegular(pCut->pOne), vVisited );
283  Map_CutsCollect_rec( Map_CutRegular(pCut->pTwo), vVisited );
284  assert( pCut->fMark == 0 );
285  pCut->fMark = 1;
286  Map_NodeVecPush( vVisited, (Map_Node_t *)pCut );
287 }
288 
289 /*
290  {
291  unsigned * uCanon2;
292  char * pPhases2;
293 
294  Map_CanonComputeSlow( p->uTruths, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
295  Map_CanonCompute( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
296  if ( uCanon2[0] != uCanon[0] )
297  {
298  int v = 0;
299  Map_CanonCompute( p->nVarsMax, pCut->nLeaves, uTruth, &uCanon2, &pPhases2 );
300  Map_CanonComputeFast( p, p->nVarsMax, pCut->nLeaves, uTruth, uPhases, uCanon );
301  }
302 // else
303 // {
304 // printf( "Correct.\n" );
305 // }
306  }
307 */
308 
309 ////////////////////////////////////////////////////////////////////////
310 /// END OF FILE ///
311 ////////////////////////////////////////////////////////////////////////
312 
313 
315 
int Map_NodeIsAnd(Map_Node_t *p)
Definition: mapperCreate.c:115
int Extra_TruthCanonFastN(int nVarsMax, int nVarsReal, unsigned *pt, unsigned **pptRes, char **ppfRes)
static Llb_Mgr_t * p
Definition: llb3Image.c:950
unsigned uPhaseBest
Definition: mapperInt.h:252
static ABC_NAMESPACE_IMPL_START void Map_TruthsCut(Map_Man_t *pMan, Map_Cut_t *pCut)
DECLARATIONS ///.
Definition: mapperTruth.c:94
static void Map_CutsCollect_rec(Map_Cut_t *pCut, Map_NodeVec_t *vVisited)
Definition: mapperTruth.c:278
Map_Cut_t * pNext
Definition: mapperInt.h:262
Map_Super_t * pSupers
Definition: mapperInt.h:249
Map_Super_t * pSuperBest
Definition: mapperInt.h:253
#define Map_CutIsComplement(p)
Definition: mapperInt.h:67
void Map_MappingTruths(Map_Man_t *pMan)
FUNCTION DEFINITIONS ///.
Definition: mapperTruth.c:47
DECLARATIONS ///.
Map_Super_t * Map_SuperTableLookupC(Map_SuperLib_t *pLib, unsigned uTruth[])
Definition: mapperTable.c:183
Map_Cut_t * pCuts
Definition: mapperInt.h:240
Map_Cut_t * pOne
Definition: mapperInt.h:263
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
if(last==0)
Definition: sparse_int.h:34
void Extra_ProgressBarStop(ProgressBar *p)
Map_Cut_t * pTwo
Definition: mapperInt.h:264
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
#define Map_CutRegular(p)
Definition: mapperInt.h:68
typedefABC_NAMESPACE_HEADER_START struct Map_ManStruct_t_ Map_Man_t
INCLUDES ///.
Definition: mapper.h:40
int Map_CanonComputeSlow(unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char *puPhases, unsigned uTruthRes[])
FUNCTION DEFINITIONS ///.
Definition: mapperCanon.c:48
void Map_TruthsCutOne(Map_Man_t *p, Map_Cut_t *pCut, unsigned uTruth[])
Definition: mapperTruth.c:197
ProgressBar * Extra_ProgressBarStart(FILE *pFile, int nItemsTotal)
FUNCTION DEFINITIONS ///.
#define assert(ex)
Definition: util_old.h:213
static void Extra_ProgressBarUpdate(ProgressBar *p, int nItemsCur, char *pString)
Definition: extra.h:243
void Map_NodeVecPush(Map_NodeVec_t *p, Map_Node_t *Entry)
Definition: mapperVec.c:190
Map_Match_t M[2]
Definition: mapperInt.h:271
Map_Node_t * ppLeaves[6]
Definition: mapperInt.h:265
int Map_CanonComputeFast(Map_Man_t *p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char *puPhases, unsigned uTruthRes[])
Definition: mapperCanon.c:173