abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
amapUniq.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [amapUniq.c]
4 
5  SystemName [ABC: Logic synthesis and verification system.]
6 
7  PackageName [Technology mapper for standard cells.]
8 
9  Synopsis [Checks if the structural node already exists.]
10 
11  Author [Alan Mishchenko]
12 
13  Affiliation [UC Berkeley]
14 
15  Date [Ver. 1.0. Started - June 20, 2005.]
16 
17  Revision [$Id: amapUniq.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18 
19 ***********************************************************************/
20 
21 #include "amapInt.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 [Checks if the entry exists and returns value.]
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
45 static inline int Vec_IntCheckWithMask( Vec_Int_t * p, int Entry )
46 {
47  int i;
48  for ( i = 0; i < p->nSize; i++ )
49  if ( (0xffff & p->pArray[i]) == (0xffff & Entry) )
50  return p->pArray[i] >> 16;
51  return -1;
52 }
53 
54 /**Function*************************************************************
55 
56  Synopsis [Pushes entry in the natural order.]
57 
58  Description []
59 
60  SideEffects []
61 
62  SeeAlso []
63 
64 ***********************************************************************/
65 static inline void Vec_IntPushOrderWithMask( Vec_Int_t * p, int Entry )
66 {
67  int i;
68  if ( p->nSize == p->nCap )
69  Vec_IntGrow( p, 2 * p->nCap );
70  p->nSize++;
71  for ( i = p->nSize-2; i >= 0; i-- )
72  if ( (0xffff & p->pArray[i]) > (0xffff & Entry) )
73  p->pArray[i+1] = p->pArray[i];
74  else
75  break;
76  p->pArray[i+1] = Entry;
77 }
78 
79 /**Function*************************************************************
80 
81  Synopsis []
82 
83  Description []
84 
85  SideEffects []
86 
87  SeeAlso []
88 
89 ***********************************************************************/
90 int Amap_LibFindNode( Amap_Lib_t * pLib, int iFan0, int iFan1, int fXor )
91 {
92  if ( fXor )
93  return Vec_IntCheckWithMask( (Vec_Int_t *)Vec_PtrEntry(pLib->vRulesX, iFan0), iFan1 );
94  else
95  return Vec_IntCheckWithMask( (Vec_Int_t *)Vec_PtrEntry(pLib->vRules, iFan0), iFan1 );
96 }
97 
98 /**Function*************************************************************
99 
100  Synopsis [Checks if the three-argument rule exist.]
101 
102  Description []
103 
104  SideEffects []
105 
106  SeeAlso []
107 
108 ***********************************************************************/
109 int Amap_LibFindMux( Amap_Lib_t * p, int iFan0, int iFan1, int iFan2 )
110 {
111  int x;
112  for ( x = 0; x < Vec_IntSize(p->vRules3); x += 4 )
113  {
114  if ( Vec_IntEntry(p->vRules3, x) == iFan0 &&
115  Vec_IntEntry(p->vRules3, x+1) == iFan1 &&
116  Vec_IntEntry(p->vRules3, x+2) == iFan2 )
117  {
118  return Vec_IntEntry(p->vRules3, x+3);
119  }
120  }
121  return -1;
122 }
123 
124 /**Function*************************************************************
125 
126  Synopsis [Creates a new node.]
127 
128  Description []
129 
130  SideEffects []
131 
132  SeeAlso []
133 
134 ***********************************************************************/
135 Amap_Nod_t * Amap_LibCreateObj( Amap_Lib_t * p )
136 {
137  Amap_Nod_t * pNode;
138  if ( p->nNodes == p->nNodesAlloc )
139  {
140  p->pNodes = ABC_REALLOC( Amap_Nod_t, p->pNodes, 2*p->nNodesAlloc );
141  p->nNodesAlloc *= 2;
142  }
143  pNode = Amap_LibNod( p, p->nNodes );
144  memset( pNode, 0, sizeof(Amap_Nod_t) );
145  pNode->Id = p->nNodes++;
146  Vec_PtrPush( p->vRules, Vec_IntAlloc(8) );
147  Vec_PtrPush( p->vRules, Vec_IntAlloc(8) );
148  Vec_PtrPush( p->vRulesX, Vec_IntAlloc(8) );
149  Vec_PtrPush( p->vRulesX, Vec_IntAlloc(8) );
150  return pNode;
151 }
152 
153 /**Function*************************************************************
154 
155  Synopsis [Creates a new node.]
156 
157  Description []
158 
159  SideEffects []
160 
161  SeeAlso []
162 
163 ***********************************************************************/
164 int Amap_LibCreateVar( Amap_Lib_t * p )
165 {
166  Amap_Nod_t * pNode;
167  // start the manager
168  assert( p->pNodes == NULL );
169  p->nNodesAlloc = 256;
170  p->pNodes = ABC_ALLOC( Amap_Nod_t, p->nNodesAlloc );
171  // create the first node
172  pNode = Amap_LibCreateObj( p );
173  p->pNodes->Type = AMAP_OBJ_PI;
174  p->pNodes->nSuppSize = 1;
175  return 0;
176 }
177 
178 /**Function*************************************************************
179 
180  Synopsis [Creates a new node.]
181 
182  Description []
183 
184  SideEffects []
185 
186  SeeAlso []
187 
188 ***********************************************************************/
189 int Amap_LibCreateNode( Amap_Lib_t * p, int iFan0, int iFan1, int fXor )
190 {
191  Amap_Nod_t * pNode;
192  int iFan;
193  if ( iFan0 < iFan1 )
194  {
195  iFan = iFan0;
196  iFan0 = iFan1;
197  iFan1 = iFan;
198  }
199  pNode = Amap_LibCreateObj( p );
200  pNode->Type = fXor? AMAP_OBJ_XOR : AMAP_OBJ_AND;
201  pNode->nSuppSize = p->pNodes[Abc_Lit2Var(iFan0)].nSuppSize + p->pNodes[Abc_Lit2Var(iFan1)].nSuppSize;
202  pNode->iFan0 = iFan0;
203  pNode->iFan1 = iFan1;
204 if ( p->fVerbose )
205 printf( "Creating node %5d %c : iFan0 = %5d%c iFan1 = %5d%c\n",
206 pNode->Id, (fXor?'x':' '),
207 Abc_Lit2Var(iFan0), (Abc_LitIsCompl(iFan0)?'-':'+'),
208 Abc_Lit2Var(iFan1), (Abc_LitIsCompl(iFan1)?'-':'+') );
209 
210  if ( fXor )
211  {
212  if ( iFan0 == iFan1 )
213  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRulesX, iFan0), (pNode->Id << 16) | iFan1 );
214  else
215  {
216  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRulesX, iFan0), (pNode->Id << 16) | iFan1 );
217  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRulesX, iFan1), (pNode->Id << 16) | iFan0 );
218  }
219  }
220  else
221  {
222  if ( iFan0 == iFan1 )
223  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRules, iFan0), (pNode->Id << 16) | iFan1 );
224  else
225  {
226  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRules, iFan0), (pNode->Id << 16) | iFan1 );
227  Vec_IntPushOrderWithMask( (Vec_Int_t *)Vec_PtrEntry(p->vRules, iFan1), (pNode->Id << 16) | iFan0 );
228  }
229  }
230  return pNode->Id;
231 }
232 
233 /**Function*************************************************************
234 
235  Synopsis [Creates a new node.]
236 
237  Description []
238 
239  SideEffects []
240 
241  SeeAlso []
242 
243 ***********************************************************************/
244 int Amap_LibCreateMux( Amap_Lib_t * p, int iFan0, int iFan1, int iFan2 )
245 {
246  Amap_Nod_t * pNode;
247  pNode = Amap_LibCreateObj( p );
248  pNode->Type = AMAP_OBJ_MUX;
249  pNode->nSuppSize = p->pNodes[Abc_Lit2Var(iFan0)].nSuppSize + p->pNodes[Abc_Lit2Var(iFan1)].nSuppSize + p->pNodes[Abc_Lit2Var(iFan2)].nSuppSize;
250  pNode->iFan0 = iFan0;
251  pNode->iFan1 = iFan1;
252  pNode->iFan2 = iFan2;
253 if ( p->fVerbose )
254 printf( "Creating node %5d %c : iFan0 = %5d%c iFan1 = %5d%c iFan2 = %5d%c\n",
255 pNode->Id, 'm',
256 Abc_Lit2Var(iFan0), (Abc_LitIsCompl(iFan0)?'-':'+'),
257 Abc_Lit2Var(iFan1), (Abc_LitIsCompl(iFan1)?'-':'+'),
258 Abc_Lit2Var(iFan2), (Abc_LitIsCompl(iFan2)?'-':'+') );
259 
260  Vec_IntPush( p->vRules3, iFan0 );
261  Vec_IntPush( p->vRules3, iFan1 );
262  Vec_IntPush( p->vRules3, iFan2 );
263  Vec_IntPush( p->vRules3, pNode->Id );
264  return pNode->Id;
265 }
266 
267 /**Function*************************************************************
268 
269  Synopsis [Allocates triangular lookup table.]
270 
271  Description []
272 
273  SideEffects []
274 
275  SeeAlso []
276 
277 ***********************************************************************/
278 int ** Amap_LibLookupTableAlloc( Vec_Ptr_t * vVec, int fVerbose )
279 {
280  Vec_Int_t * vOne;
281  int ** pRes, * pBuffer;
282  int i, k, nTotal, nSize, nEntries, Value;
283  // count the total size
284  nEntries = nSize = Vec_PtrSize( vVec );
285  Vec_PtrForEachEntry( Vec_Int_t *, vVec, vOne, i )
286  nEntries += Vec_IntSize(vOne);
287  pBuffer = ABC_ALLOC( int, nSize * sizeof(void *) + nEntries );
288  pRes = (int **)pBuffer;
289  pRes[0] = pBuffer + nSize * sizeof(void *);
290  nTotal = 0;
291  Vec_PtrForEachEntry( Vec_Int_t *, vVec, vOne, i )
292  {
293  pRes[i] = pRes[0] + nTotal;
294  nTotal += Vec_IntSize(vOne) + 1;
295  if ( fVerbose )
296  printf( "%d : ", i );
297  Vec_IntForEachEntry( vOne, Value, k )
298  {
299  pRes[i][k] = Value;
300  if ( fVerbose )
301  printf( "%d(%d) ", Value&0xffff, Value>>16 );
302  }
303  if ( fVerbose )
304  printf( "\n" );
305  pRes[i][k] = 0;
306  }
307  assert( nTotal == nEntries );
308  return pRes;
309 }
310 
311 ////////////////////////////////////////////////////////////////////////
312 /// END OF FILE ///
313 ////////////////////////////////////////////////////////////////////////
314 
315 
316 ABC_NAMESPACE_IMPL_END
317 
memset
char * memset()
Amap_LibFindNode
int Amap_LibFindNode(Amap_Lib_t *pLib, int iFan0, int iFan1, int fXor)
Definition: amapUniq.c:90
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Amap_Nod_t_::iFan0
short iFan0
Definition: amapInt.h:177
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Amap_Nod_t_::iFan2
short iFan2
Definition: amapInt.h:179
Vec_PtrSize
static int Vec_PtrSize(Vec_Ptr_t *p)
Definition: vecPtr.h:295
Vec_IntGrow
static void Vec_IntGrow(Vec_Int_t *p, int nCapMin)
Definition: bblif.c:336
Abc_LitIsCompl
static int Abc_LitIsCompl(int Lit)
Definition: abc_global.h:265
Amap_Nod_t_::Type
unsigned Type
Definition: amapInt.h:176
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Amap_Nod_t_::nSuppSize
unsigned nSuppSize
Definition: amapInt.h:175
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Amap_LibCreateObj
Amap_Nod_t * Amap_LibCreateObj(Amap_Lib_t *p)
Definition: amapUniq.c:135
Amap_LibFindMux
int Amap_LibFindMux(Amap_Lib_t *p, int iFan0, int iFan1, int iFan2)
Definition: amapUniq.c:109
Vec_IntPushOrderWithMask
static void Vec_IntPushOrderWithMask(Vec_Int_t *p, int Entry)
Definition: amapUniq.c:65
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
Amap_LibCreateMux
int Amap_LibCreateMux(Amap_Lib_t *p, int iFan0, int iFan1, int iFan2)
Definition: amapUniq.c:244
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Amap_Lib_t
typedefABC_NAMESPACE_HEADER_START struct Amap_Lib_t_ Amap_Lib_t
INCLUDES ///.
Definition: amap.h:42
Amap_LibCreateVar
int Amap_LibCreateVar(Amap_Lib_t *p)
Definition: amapUniq.c:164
Amap_Nod_t_
Definition: amapInt.h:172
Abc_Lit2Var
static int Abc_Lit2Var(int Lit)
Definition: abc_global.h:264
Amap_Nod_t_::Id
unsigned Id
Definition: amapInt.h:174
Amap_Nod_t_::iFan1
short iFan1
Definition: amapInt.h:178
Amap_LibLookupTableAlloc
int ** Amap_LibLookupTableAlloc(Vec_Ptr_t *vVec, int fVerbose)
Definition: amapUniq.c:278
assert
#define assert(ex)
Definition: util_old.h:213
Vec_IntCheckWithMask
static ABC_NAMESPACE_IMPL_START int Vec_IntCheckWithMask(Vec_Int_t *p, int Entry)
DECLARATIONS ///.
Definition: amapUniq.c:45
Amap_LibNod
static Amap_Nod_t * Amap_LibNod(Amap_Lib_t *p, int i)
Definition: amapInt.h:264
Vec_PtrForEachEntry
#define Vec_PtrForEachEntry(Type, vVec, pEntry, i)
MACRO DEFINITIONS ///.
Definition: vecPtr.h:55
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Amap_LibCreateNode
int Amap_LibCreateNode(Amap_Lib_t *p, int iFan0, int iFan1, int fXor)
Definition: amapUniq.c:189
nTotal
int nTotal
DECLARATIONS ///.
Definition: cutTruth.c:37