abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
fxuReduce.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [fxuReduce.c]
4 
5  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
6 
7  Synopsis [Procedures to reduce the number of considered cube pairs.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 1.0. Started - February 1, 2003.]
14 
15  Revision [$Id: fxuReduce.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "base/abc/abc.h"
20 #include "fxuInt.h"
21 #include "fxu.h"
22 
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 static int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] );
31 
32 ////////////////////////////////////////////////////////////////////////
33 /// FUNCTION DEFINITIONS ///
34 ////////////////////////////////////////////////////////////////////////
35 
36 /**Function*************************************************************
37 
38  Synopsis [Precomputes the pairs to use for creating two-cube divisors.]
39 
40  Description [This procedure takes the matrix with variables and cubes
41  allocated (p), the original covers of the nodes (i-sets) and their number
42  (ppCovers,nCovers). The maximum number of pairs to compute and the total
43  number of pairs in existence. This procedure adds to the storage of
44  divisors exactly the given number of pairs (nPairsMax) while taking
45  first those pairs that have the smallest number of literals in their
46  cube-free form.]
47 
48  SideEffects []
49 
50  SeeAlso []
51 
52 ***********************************************************************/
53 int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax )
54 {
55  unsigned char * pnLitsDiff; // storage for the counters of diff literals
56  int * pnPairCounters; // the counters of pairs for each number of diff literals
57  Fxu_Cube * pCubeFirst, * pCubeLast;
58  Fxu_Cube * pCube1, * pCube2;
59  Fxu_Var * pVar;
60  int nCubes, nBitsMax, nSum;
61  int CutOffNum = -1, CutOffQuant = -1; // Suppress "might be used uninitialized"
62  int iPair, iQuant, k, c;
63 // abctime clk = Abc_Clock();
64  char * pSopCover;
65  int nFanins;
66 
67  assert( nPairsMax < nPairsTotal );
68 
69  // allocate storage for counter of diffs
70  pnLitsDiff = ABC_FALLOC( unsigned char, nPairsTotal );
71  // go through the covers and precompute the distances between the pairs
72  iPair = 0;
73  nBitsMax = -1;
74  for ( c = 0; c < vCovers->nSize; c++ )
75  if ( (pSopCover = (char *)vCovers->pArray[c]) )
76  {
77  nFanins = Abc_SopGetVarNum(pSopCover);
78  // precompute the differences
79  Fxu_CountPairDiffs( pSopCover, pnLitsDiff + iPair );
80  // update the counter
81  nCubes = Abc_SopGetCubeNum( pSopCover );
82  iPair += nCubes * (nCubes - 1) / 2;
83  if ( nBitsMax < nFanins )
84  nBitsMax = nFanins;
85  }
86  assert( iPair == nPairsTotal );
87 
88  // allocate storage for counters of cube pairs by difference
89  pnPairCounters = ABC_FALLOC( int, 2 * nBitsMax );
90  memset( pnPairCounters, 0, sizeof(int) * 2 * nBitsMax );
91  // count the number of different pairs
92  for ( k = 0; k < nPairsTotal; k++ )
93  pnPairCounters[ pnLitsDiff[k] ]++;
94  // determine what pairs to take starting from the lower
95  // so that there would be exactly pPairsMax pairs
96  if ( pnPairCounters[0] != 0 )
97  {
98  ABC_FREE( pnLitsDiff );
99  ABC_FREE( pnPairCounters );
100  printf( "The SOPs of the nodes contain duplicated cubes. Run \"bdd; sop\" before \"fx\".\n" );
101  return 0;
102  }
103  if ( pnPairCounters[1] != 0 )
104  {
105  ABC_FREE( pnLitsDiff );
106  ABC_FREE( pnPairCounters );
107  printf( "The SOPs of the nodes are not SCC-free. Run \"bdd; sop\" before \"fx\".\n" );
108  return 0;
109  }
110  assert( pnPairCounters[0] == 0 ); // otherwise, covers are not dup-free
111  assert( pnPairCounters[1] == 0 ); // otherwise, covers are not SCC-free
112  nSum = 0;
113  for ( k = 0; k < 2 * nBitsMax; k++ )
114  {
115  nSum += pnPairCounters[k];
116  if ( nSum >= nPairsMax )
117  {
118  CutOffNum = k;
119  CutOffQuant = pnPairCounters[k] - (nSum - nPairsMax);
120  break;
121  }
122  }
123  ABC_FREE( pnPairCounters );
124 
125  // set to 0 all the pairs above the cut-off number and quantity
126  iQuant = 0;
127  iPair = 0;
128  for ( k = 0; k < nPairsTotal; k++ )
129  if ( pnLitsDiff[k] > CutOffNum )
130  pnLitsDiff[k] = 0;
131  else if ( pnLitsDiff[k] == CutOffNum )
132  {
133  if ( iQuant++ >= CutOffQuant )
134  pnLitsDiff[k] = 0;
135  else
136  iPair++;
137  }
138  else
139  iPair++;
140  assert( iPair == nPairsMax );
141 
142  // collect the corresponding pairs and add the divisors
143  iPair = 0;
144  for ( c = 0; c < vCovers->nSize; c++ )
145  if ( (pSopCover = (char *)vCovers->pArray[c]) )
146  {
147  // get the var
148  pVar = p->ppVars[2*c+1];
149  // get the first cube
150  pCubeFirst = pVar->pFirst;
151  // get the last cube
152  pCubeLast = pCubeFirst;
153  for ( k = 0; k < pVar->nCubes; k++ )
154  pCubeLast = pCubeLast->pNext;
155  assert( pCubeLast == NULL || pCubeLast->pVar != pVar );
156 
157  // go through the cube pairs
158  for ( pCube1 = pCubeFirst; pCube1 != pCubeLast; pCube1 = pCube1->pNext )
159  for ( pCube2 = pCube1->pNext; pCube2 != pCubeLast; pCube2 = pCube2->pNext )
160  if ( pnLitsDiff[iPair++] )
161  { // create the divisors for this pair
162  Fxu_MatrixAddDivisor( p, pCube1, pCube2 );
163  }
164  }
165  assert( iPair == nPairsTotal );
166  ABC_FREE( pnLitsDiff );
167 //ABC_PRT( "Preprocess", Abc_Clock() - clk );
168  return 1;
169 }
170 
171 
172 /**Function*************************************************************
173 
174  Synopsis [Counts the differences in each cube pair in the cover.]
175 
176  Description [Takes the cover (pCover) and the array where the
177  diff counters go (pDiffs). The array pDiffs should have as many
178  entries as there are different pairs of cubes in the cover: n(n-1)/2.
179  Fills out the array pDiffs with the following info: For each cube
180  pair, included in the array is the number of literals in both cubes
181  after they are made cube free.]
182 
183  SideEffects []
184 
185  SeeAlso []
186 
187 ***********************************************************************/
188 int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] )
189 {
190  char * pCube1, * pCube2;
191  int nOnes, nCubePairs, nFanins, v;
192  nCubePairs = 0;
193  nFanins = Abc_SopGetVarNum(pCover);
194  Abc_SopForEachCube( pCover, nFanins, pCube1 )
195  Abc_SopForEachCube( pCube1, nFanins, pCube2 )
196  {
197  if ( pCube1 == pCube2 )
198  continue;
199  nOnes = 0;
200  for ( v = 0; v < nFanins; v++ )
201  nOnes += (pCube1[v] != pCube2[v]);
202  pDiffs[nCubePairs++] = nOnes;
203  }
204  return 1;
205 }
206 
207 ////////////////////////////////////////////////////////////////////////
208 /// END OF FILE ///
209 ////////////////////////////////////////////////////////////////////////
210 
211 
213 
char * memset()
int nCubes
Definition: fxuInt.h:216
Definition: fxuInt.h:213
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
static Llb_Mgr_t * p
Definition: llb3Image.c:950
void Fxu_MatrixAddDivisor(Fxu_Matrix *p, Fxu_Cube *pCube1, Fxu_Cube *pCube2)
Definition: fxuMatrix.c:301
#define Abc_SopForEachCube(pSop, nFanins, pCube)
Definition: abc.h:531
ABC_DLL int Abc_SopGetCubeNum(char *pSop)
Definition: abcSop.c:489
int Fxu_PreprocessCubePairs(Fxu_Matrix *p, Vec_Ptr_t *vCovers, int nPairsTotal, int nPairsMax)
FUNCTION DEFINITIONS ///.
Definition: fxuReduce.c:53
Fxu_Var * pVar
Definition: fxuInt.h:205
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Fxu_Cube * pFirst
Definition: fxuInt.h:217
Fxu_Cube * pNext
Definition: fxuInt.h:208
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
#define ABC_FREE(obj)
Definition: abc_global.h:232
ABC_DLL int Abc_SopGetVarNum(char *pSop)
Definition: abcSop.c:536
#define assert(ex)
Definition: util_old.h:213
typedefABC_NAMESPACE_HEADER_START struct FxuMatrix Fxu_Matrix
INCLUDES ///.
Definition: fxuInt.h:63
static ABC_NAMESPACE_IMPL_START int Fxu_CountPairDiffs(char *pCover, unsigned char pDiffs[])
DECLARATIONS ///.
Definition: fxuReduce.c:188
#define ABC_FALLOC(type, num)
Definition: abc_global.h:231