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