1 /**CFile****************************************************************
2
3 FileName [mvcLits.c]
4
5 PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
6
7 Synopsis [Literal counting/updating procedures.]
8
9 Author [MVSIS Group]
10
11 Affiliation [UC Berkeley]
12
13 Date [Ver. 1.0. Started - February 1, 2003.]
14
15 Revision [$Id: mvcLits.c,v 1.4 2003/04/03 06:31:50 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #include "mvc.h"
20
21 ABC_NAMESPACE_IMPL_START
22
23
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27
28 ////////////////////////////////////////////////////////////////////////
29 /// FUNCTION DEFINITIONS ///
30 ////////////////////////////////////////////////////////////////////////
31
32 /**Function*************************************************************
33
34 Synopsis [Find the any literal that occurs more than once.]
35
36 Description []
37
38 SideEffects []
39
40 SeeAlso []
41
42 ***********************************************************************/
Mvc_CoverAnyLiteral(Mvc_Cover_t * pCover,Mvc_Cube_t * pMask)43 int Mvc_CoverAnyLiteral( Mvc_Cover_t * pCover, Mvc_Cube_t * pMask )
44 {
45 Mvc_Cube_t * pCube;
46 int nWord, nBit, i;
47 int nLitsCur;
48 int fUseFirst = 0;
49
50 // go through each literal
51 if ( fUseFirst )
52 {
53 for ( i = 0; i < pCover->nBits; i++ )
54 if ( !pMask || Mvc_CubeBitValue(pMask,i) )
55 {
56 // get the word and bit of this literal
57 nWord = Mvc_CubeWhichWord(i);
58 nBit = Mvc_CubeWhichBit(i);
59 // go through all the cubes
60 nLitsCur = 0;
61 Mvc_CoverForEachCube( pCover, pCube )
62 if ( pCube->pData[nWord] & (1<<nBit) )
63 {
64 nLitsCur++;
65 if ( nLitsCur > 1 )
66 return i;
67 }
68 }
69 }
70 else
71 {
72 for ( i = pCover->nBits - 1; i >=0; i-- )
73 if ( !pMask || Mvc_CubeBitValue(pMask,i) )
74 {
75 // get the word and bit of this literal
76 nWord = Mvc_CubeWhichWord(i);
77 nBit = Mvc_CubeWhichBit(i);
78 // go through all the cubes
79 nLitsCur = 0;
80 Mvc_CoverForEachCube( pCover, pCube )
81 if ( pCube->pData[nWord] & (1<<nBit) )
82 {
83 nLitsCur++;
84 if ( nLitsCur > 1 )
85 return i;
86 }
87 }
88 }
89 return -1;
90 }
91
92 /**Function*************************************************************
93
94 Synopsis [Find the most often occurring literal.]
95
96 Description [Find the most often occurring literal among those
97 that occur more than once.]
98
99 SideEffects []
100
101 SeeAlso []
102
103 ***********************************************************************/
Mvc_CoverBestLiteral(Mvc_Cover_t * pCover,Mvc_Cube_t * pMask)104 int Mvc_CoverBestLiteral( Mvc_Cover_t * pCover, Mvc_Cube_t * pMask )
105 {
106 Mvc_Cube_t * pCube;
107 int nWord, nBit;
108 int i, iMax, nLitsMax, nLitsCur;
109 int fUseFirst = 1;
110
111 // go through each literal
112 iMax = -1;
113 nLitsMax = -1;
114 for ( i = 0; i < pCover->nBits; i++ )
115 if ( !pMask || Mvc_CubeBitValue(pMask,i) )
116 {
117 // get the word and bit of this literal
118 nWord = Mvc_CubeWhichWord(i);
119 nBit = Mvc_CubeWhichBit(i);
120 // go through all the cubes
121 nLitsCur = 0;
122 Mvc_CoverForEachCube( pCover, pCube )
123 if ( pCube->pData[nWord] & (1<<nBit) )
124 nLitsCur++;
125
126 // check if this is the best literal
127 if ( fUseFirst )
128 {
129 if ( nLitsMax < nLitsCur )
130 {
131 nLitsMax = nLitsCur;
132 iMax = i;
133 }
134 }
135 else
136 {
137 if ( nLitsMax <= nLitsCur )
138 {
139 nLitsMax = nLitsCur;
140 iMax = i;
141 }
142 }
143 }
144
145 if ( nLitsMax > 1 )
146 return iMax;
147 return -1;
148 }
149
150 /**Function*************************************************************
151
152 Synopsis [Find the most often occurring literal.]
153
154 Description [Find the most often occurring literal among those
155 that occur more than once.]
156
157 SideEffects []
158
159 SeeAlso []
160
161 ***********************************************************************/
Mvc_CoverWorstLiteral(Mvc_Cover_t * pCover,Mvc_Cube_t * pMask)162 int Mvc_CoverWorstLiteral( Mvc_Cover_t * pCover, Mvc_Cube_t * pMask )
163 {
164 Mvc_Cube_t * pCube;
165 int nWord, nBit;
166 int i, iMin, nLitsMin, nLitsCur;
167 int fUseFirst = 1;
168
169 // go through each literal
170 iMin = -1;
171 nLitsMin = 1000000;
172 for ( i = 0; i < pCover->nBits; i++ )
173 if ( !pMask || Mvc_CubeBitValue(pMask,i) )
174 {
175 // get the word and bit of this literal
176 nWord = Mvc_CubeWhichWord(i);
177 nBit = Mvc_CubeWhichBit(i);
178 // go through all the cubes
179 nLitsCur = 0;
180 Mvc_CoverForEachCube( pCover, pCube )
181 if ( pCube->pData[nWord] & (1<<nBit) )
182 nLitsCur++;
183
184 // skip the literal that does not occur or occurs once
185 if ( nLitsCur < 2 )
186 continue;
187
188 // check if this is the best literal
189 if ( fUseFirst )
190 {
191 if ( nLitsMin > nLitsCur )
192 {
193 nLitsMin = nLitsCur;
194 iMin = i;
195 }
196 }
197 else
198 {
199 if ( nLitsMin >= nLitsCur )
200 {
201 nLitsMin = nLitsCur;
202 iMin = i;
203 }
204 }
205 }
206
207 if ( nLitsMin < 1000000 )
208 return iMin;
209 return -1;
210 }
211
212 /**Function*************************************************************
213
214 Synopsis []
215
216 Description []
217
218 SideEffects []
219
220 SeeAlso []
221
222 ***********************************************************************/
Mvc_CoverBestLiteralCover(Mvc_Cover_t * pCover,Mvc_Cover_t * pSimple)223 Mvc_Cover_t * Mvc_CoverBestLiteralCover( Mvc_Cover_t * pCover, Mvc_Cover_t * pSimple )
224 {
225 Mvc_Cover_t * pCoverNew;
226 Mvc_Cube_t * pCubeNew;
227 Mvc_Cube_t * pCubeS;
228 int iLitBest;
229
230 // create the new cover
231 pCoverNew = Mvc_CoverClone( pCover );
232 // get the new cube
233 pCubeNew = Mvc_CubeAlloc( pCoverNew );
234 // clean the cube
235 Mvc_CubeBitClean( pCubeNew );
236
237 // get the first cube of pSimple
238 assert( Mvc_CoverReadCubeNum(pSimple) == 1 );
239 pCubeS = Mvc_CoverReadCubeHead( pSimple );
240 // find the best literal among those of pCubeS
241 iLitBest = Mvc_CoverBestLiteral( pCover, pCubeS );
242
243 // insert this literal into the cube
244 Mvc_CubeBitInsert( pCubeNew, iLitBest );
245 // add the cube to the cover
246 Mvc_CoverAddCubeTail( pCoverNew, pCubeNew );
247 return pCoverNew;
248 }
249
250 /**Function*************************************************************
251
252 Synopsis []
253
254 Description []
255
256 SideEffects []
257
258 SeeAlso []
259
260 ***********************************************************************/
Mvc_CoverFirstCubeFirstLit(Mvc_Cover_t * pCover)261 int Mvc_CoverFirstCubeFirstLit( Mvc_Cover_t * pCover )
262 {
263 Mvc_Cube_t * pCube;
264 int iBit, Value;
265
266 // get the first cube
267 pCube = Mvc_CoverReadCubeHead( pCover );
268 // get the first literal
269 Mvc_CubeForEachBit( pCover, pCube, iBit, Value )
270 if ( Value )
271 return iBit;
272 return -1;
273 }
274
275 /**Function*************************************************************
276
277 Synopsis [Returns the number of literals in the cover.]
278
279 Description [Allocates storage for literal counters and fills it up
280 using the current information.]
281
282 SideEffects []
283
284 SeeAlso []
285
286 ***********************************************************************/
Mvc_CoverCountLiterals(Mvc_Cover_t * pCover)287 int Mvc_CoverCountLiterals( Mvc_Cover_t * pCover )
288 {
289 Mvc_Cube_t * pCube;
290 int nWord, nBit;
291 int i, CounterTot, CounterCur;
292
293 // allocate/clean the storage for literals
294 // Mvc_CoverAllocateArrayLits( pCover );
295 // memset( pCover->pLits, 0, pCover->nBits * sizeof(int) );
296 // go through each literal
297 CounterTot = 0;
298 for ( i = 0; i < pCover->nBits; i++ )
299 {
300 // get the word and bit of this literal
301 nWord = Mvc_CubeWhichWord(i);
302 nBit = Mvc_CubeWhichBit(i);
303 // go through all the cubes
304 CounterCur = 0;
305 Mvc_CoverForEachCube( pCover, pCube )
306 if ( pCube->pData[nWord] & (1<<nBit) )
307 CounterCur++;
308 CounterTot += CounterCur;
309 }
310 return CounterTot;
311 }
312
313 /**Function*************************************************************
314
315 Synopsis [Returns the number of literals in the cover.]
316
317 Description []
318
319 SideEffects []
320
321 SeeAlso []
322
323 ***********************************************************************/
Mvc_CoverIsOneLiteral(Mvc_Cover_t * pCover)324 int Mvc_CoverIsOneLiteral( Mvc_Cover_t * pCover )
325 {
326 Mvc_Cube_t * pCube;
327 int iBit, Counter, Value;
328 if ( Mvc_CoverReadCubeNum(pCover) != 1 )
329 return 0;
330 pCube = Mvc_CoverReadCubeHead(pCover);
331 // count literals
332 Counter = 0;
333 Mvc_CubeForEachBit( pCover, pCube, iBit, Value )
334 {
335 if ( Value )
336 {
337 if ( Counter++ )
338 return 0;
339 }
340 }
341 return 1;
342 }
343
344 ////////////////////////////////////////////////////////////////////////
345 /// END OF FILE ///
346 ////////////////////////////////////////////////////////////////////////
347
348
349 ABC_NAMESPACE_IMPL_END
350
351