1 /**CFile****************************************************************
2
3 FileName [mapperCanon.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: mapperCanon.c,v 1.2 2005/01/23 06:59:42 alanmi Exp $]
16
17 ***********************************************************************/
18
19 #include "mapperInt.h"
20
21 ABC_NAMESPACE_IMPL_START
22
23
24 ////////////////////////////////////////////////////////////////////////
25 /// DECLARATIONS ///
26 ////////////////////////////////////////////////////////////////////////
27
28 static unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase );
29 static void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] );
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Computes the N-canonical form of the Boolean function.]
38
39 Description [The N-canonical form is defined as the truth table with
40 the minimum integer value. This function exhaustively enumerates
41 through the complete set of 2^N phase assignments.]
42
43 SideEffects []
44
45 SeeAlso []
46
47 ***********************************************************************/
Map_CanonComputeSlow(unsigned uTruths[][2],int nVarsMax,int nVarsReal,unsigned uTruth[],unsigned char * puPhases,unsigned uTruthRes[])48 int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
49 {
50 unsigned uTruthPerm[2];
51 int nMints, nPhases, m;
52
53 nPhases = 0;
54 nMints = (1 << nVarsReal);
55 if ( nVarsMax < 6 )
56 {
57 uTruthRes[0] = MAP_MASK(32);
58 for ( m = 0; m < nMints; m++ )
59 {
60 uTruthPerm[0] = Map_CanonComputePhase( uTruths, nVarsMax, uTruth[0], m );
61 if ( uTruthRes[0] > uTruthPerm[0] )
62 {
63 uTruthRes[0] = uTruthPerm[0];
64 nPhases = 0;
65 puPhases[nPhases++] = (unsigned char)m;
66 }
67 else if ( uTruthRes[0] == uTruthPerm[0] )
68 {
69 if ( nPhases < 4 ) // the max number of phases in Map_Super_t
70 puPhases[nPhases++] = (unsigned char)m;
71 }
72 }
73 uTruthRes[1] = uTruthRes[0];
74 }
75 else
76 {
77 uTruthRes[0] = MAP_MASK(32);
78 uTruthRes[1] = MAP_MASK(32);
79 for ( m = 0; m < nMints; m++ )
80 {
81 Map_CanonComputePhase6( uTruths, nVarsMax, uTruth, m, uTruthPerm );
82 if ( uTruthRes[1] > uTruthPerm[1] || (uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] > uTruthPerm[0]) )
83 {
84 uTruthRes[0] = uTruthPerm[0];
85 uTruthRes[1] = uTruthPerm[1];
86 nPhases = 0;
87 puPhases[nPhases++] = (unsigned char)m;
88 }
89 else if ( uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] == uTruthPerm[0] )
90 {
91 if ( nPhases < 4 ) // the max number of phases in Map_Super_t
92 puPhases[nPhases++] = (unsigned char)m;
93 }
94 }
95 }
96 assert( nPhases > 0 );
97 // printf( "%d ", nPhases );
98 return nPhases;
99 }
100
101 /**Function*************************************************************
102
103 Synopsis [Performs phase transformation for one function of less than 6 variables.]
104
105 Description []
106
107 SideEffects []
108
109 SeeAlso []
110
111 ***********************************************************************/
Map_CanonComputePhase(unsigned uTruths[][2],int nVars,unsigned uTruth,unsigned uPhase)112 unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase )
113 {
114 int v, Shift;
115 for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
116 if ( uPhase & Shift )
117 uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift));
118 return uTruth;
119 }
120
121 /**Function*************************************************************
122
123 Synopsis [Performs phase transformation for one function of 6 variables.]
124
125 Description []
126
127 SideEffects []
128
129 SeeAlso []
130
131 ***********************************************************************/
Map_CanonComputePhase6(unsigned uTruths[][2],int nVars,unsigned uTruth[],unsigned uPhase,unsigned uTruthRes[])132 void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] )
133 {
134 unsigned uTemp;
135 int v, Shift;
136
137 // initialize the result
138 uTruthRes[0] = uTruth[0];
139 uTruthRes[1] = uTruth[1];
140 if ( uPhase == 0 )
141 return;
142 // compute the phase
143 for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
144 if ( uPhase & Shift )
145 {
146 if ( Shift < 32 )
147 {
148 uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift));
149 uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift));
150 }
151 else
152 {
153 uTemp = uTruthRes[0];
154 uTruthRes[0] = uTruthRes[1];
155 uTruthRes[1] = uTemp;
156 }
157 }
158 }
159
160 /**Function*************************************************************
161
162 Synopsis [Computes the N-canonical form of the Boolean function.]
163
164 Description [The N-canonical form is defined as the truth table with
165 the minimum integer value. This function exhaustively enumerates
166 through the complete set of 2^N phase assignments.]
167
168 SideEffects []
169
170 SeeAlso []
171
172 ***********************************************************************/
Map_CanonComputeFast(Map_Man_t * p,int nVarsMax,int nVarsReal,unsigned uTruth[],unsigned char * puPhases,unsigned uTruthRes[])173 int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
174 {
175 unsigned uTruth0, uTruth1;
176 unsigned uCanon0, uCanon1, uCanonBest;
177 unsigned uPhaseBest = 16; // Suppress "might be used uninitialized" (asserts require < 16)
178 int i, Limit;
179
180 if ( nVarsMax == 6 )
181 return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
182
183 if ( nVarsReal < 5 )
184 {
185 // return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
186
187 uTruth0 = uTruth[0] & 0xFFFF;
188 assert( p->pCounters[uTruth0] > 0 );
189 uTruthRes[0] = (p->uCanons[uTruth0] << 16) | p->uCanons[uTruth0];
190 uTruthRes[1] = uTruthRes[0];
191 puPhases[0] = p->uPhases[uTruth0][0];
192 return 1;
193 }
194
195 assert( nVarsMax == 5 );
196 assert( nVarsReal == 5 );
197 uTruth0 = uTruth[0] & 0xFFFF;
198 uTruth1 = (uTruth[0] >> 16);
199 if ( uTruth1 == 0 )
200 {
201 uTruthRes[0] = p->uCanons[uTruth0];
202 uTruthRes[1] = uTruthRes[0];
203 Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
204 for ( i = 0; i < Limit; i++ )
205 puPhases[i] = p->uPhases[uTruth0][i];
206 return Limit;
207 }
208 else if ( uTruth0 == 0 )
209 {
210 uTruthRes[0] = p->uCanons[uTruth1];
211 uTruthRes[1] = uTruthRes[0];
212 Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
213 for ( i = 0; i < Limit; i++ )
214 {
215 puPhases[i] = p->uPhases[uTruth1][i];
216 puPhases[i] |= (1 << 4);
217 }
218 return Limit;
219 }
220 uCanon0 = p->uCanons[uTruth0];
221 uCanon1 = p->uCanons[uTruth1];
222 if ( uCanon0 >= uCanon1 ) // using nCanon1 as the main one
223 {
224 assert( p->pCounters[uTruth1] > 0 );
225 uCanonBest = 0xFFFFFFFF;
226 for ( i = 0; i < p->pCounters[uTruth1]; i++ )
227 {
228 uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 );
229 if ( uCanonBest > uCanon0 )
230 {
231 uCanonBest = uCanon0;
232 uPhaseBest = p->uPhases[uTruth1][i];
233 assert( uPhaseBest < 16 );
234 }
235 }
236 uTruthRes[0] = (uCanon1 << 16) | uCanonBest;
237 uTruthRes[1] = uTruthRes[0];
238 puPhases[0] = uPhaseBest;
239 return 1;
240 }
241 else if ( uCanon0 < uCanon1 )
242 {
243 assert( p->pCounters[uTruth0] > 0 );
244 uCanonBest = 0xFFFFFFFF;
245 for ( i = 0; i < p->pCounters[uTruth0]; i++ )
246 {
247 uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 );
248 if ( uCanonBest > uCanon1 )
249 {
250 uCanonBest = uCanon1;
251 uPhaseBest = p->uPhases[uTruth0][i];
252 assert( uPhaseBest < 16 );
253 }
254 }
255 uTruthRes[0] = (uCanon0 << 16) | uCanonBest;
256 uTruthRes[1] = uTruthRes[0];
257 puPhases[0] = uPhaseBest | (1 << 4);
258 return 1;
259 }
260 else
261 {
262 assert( 0 );
263 return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
264 }
265 }
266
267
268
269
270
271 ////////////////////////////////////////////////////////////////////////
272 /// END OF FILE ///
273 ////////////////////////////////////////////////////////////////////////
274
275
276 ABC_NAMESPACE_IMPL_END
277
278