1 /**CFile****************************************************************
2
3 FileName [exorLink.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Exclusive sum-of-product minimization.]
8
9 Synopsis [Cube iterators.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: exorLink.c,v 1.0 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 ////////////////////////////////////////////////////////////////////////
22 /// ///
23 /// Implementation of EXORCISM - 4 ///
24 /// An Exclusive Sum-of-Product Minimizer ///
25 /// ///
26 /// Alan Mishchenko <alanmi@ee.pdx.edu> ///
27 /// ///
28 ////////////////////////////////////////////////////////////////////////
29 /// ///
30 /// Generation of ExorLinked Cubes ///
31 /// ///
32 /// Ver. 1.0. Started - July 26, 2000. Last update - July 29, 2000 ///
33 /// Ver. 1.4. Started - Aug 10, 2000. Last update - Aug 12, 2000 ///
34 /// ///
35 ////////////////////////////////////////////////////////////////////////
36 /// This software was tested with the BDD package "CUDD", v.2.3.0 ///
37 /// by Fabio Somenzi ///
38 /// http://vlsi.colorado.edu/~fabio/ ///
39 ////////////////////////////////////////////////////////////////////////
40
41 #include "exor.h"
42
43 ABC_NAMESPACE_IMPL_START
44
45 ////////////////////////////////////////////////////////////////////////
46 /// MACRO DEFINITIONS ///
47 ////////////////////////////////////////////////////////////////////////
48
49 #define LARGE_NUM 1000000
50
51 ////////////////////////////////////////////////////////////////////////
52 /// EXTERNAL FUNCTION DECLARATIONS ///
53 ////////////////////////////////////////////////////////////////////////
54
55 ////////////////////////////////////////////////////////////////////////
56 /// FUNCTIONS OF THIS MODULE ///
57 ////////////////////////////////////////////////////////////////////////
58
59 int ExorLinkCubeIteratorStart( Cube** pGroup, Cube* pC1, Cube* pC2, cubedist Dist );
60 // this function starts the Exor-Link iterator, which iterates
61 // through the cube groups starting from the group with min literals
62 // returns 1 on success, returns 0 if the cubes have wrong distance
63
64 int ExorLinkCubeIteratorNext( Cube** pGroup );
65 // give the next group in the decreasing order of sum of literals
66 // returns 1 on success, returns 0 if there are no more groups
67
68 int ExorLinkCubeIteratorPick( Cube** pGroup, int g );
69 // gives the group #g in the order in which the groups were given
70 // during iteration
71 // returns 1 on success, returns 0 if something g is too large
72
73 void ExorLinkCubeIteratorCleanUp( int fTakeLastGroup );
74 // removes the cubes from the store back into the list of free cubes
75 // if fTakeLastGroup is 0, removes all cubes
76 // if fTakeLastGroup is 1, does not store the last group
77
78 ////////////////////////////////////////////////////////////////////////
79 /// EXTERNAL VARIABLES ///
80 ////////////////////////////////////////////////////////////////////////
81
82 // information about the cube cover before
83 extern cinfo g_CoverInfo;
84 // new IDs are assigned only when it is known that the cubes are useful
85 // this is done in ExorLinkCubeIteratorCleanUp();
86
87 // the head of the list of free cubes
88 extern Cube* g_CubesFree;
89
90 extern byte BitCount[];
91
92 ////////////////////////////////////////////////////////////////////////
93 /// EXORLINK INFO ///
94 ////////////////////////////////////////////////////////////////////////
95
96 const int s_ELMax = 4;
97
98 // ExorLink-2: there are 4 cubes, 2 literals each, combined into 2 groups
99 // ExorLink-3: there are 12 cubes, 3 literals each, combined into 6 groups
100 // ExorLink-4: there are 32 cubes, 4 literals each, combined into 24 groups
101 // ExorLink-5: there are 80 cubes, 5 literals each, combined into 120 groups
102 // Exorlink-n: there are n*2^(n-1) cubes, n literals each, combined into n! groups
103 const int s_ELnCubes[4] = { 4, 12, 32, 80 };
104 const int s_ELnGroups[4] = { 2, 6, 24, 120 };
105
106 // value sets of cubes X{a0}Y{b0}Z{c0}U{d0} and X{a1}Y{b1}Z{c1}U{d1}
107 // used to represent the ExorLink cube generation rules
108 enum { vs0, vs1, vsX };
109 // vs0 = 0, // the value set of the first cube
110 // vs1 = 1, // the value set of the second cube
111 // vsX = 2 // EXOR of the value sets of the first and second cubes
112
113 // representation of ExorLinked cubes
114 static int s_ELCubeRules[3][32][4] = {
115 { // ExorLink-2 Cube Generating Rules
116 // | 0 | 1 | - sections
117 // |-------|
118 {vsX,vs0}, // cube 0 | | |
119 {vsX,vs1}, // cube 1 | | 0 |
120 {vs0,vsX}, // cube 2 | | |
121 {vs1,vsX} // cube 3 | 0 | |
122 },
123 { // ExorLink-3 Cube Generating Rules
124 // | 0 | 1 | 2 | - sections
125 // |-----------|
126 {vsX,vs0,vs0}, // cube 0 | | | |
127 {vsX,vs0,vs1}, // cube 1 | | | 0 |
128 {vsX,vs1,vs0}, // cube 2 | | 0 | |
129 {vsX,vs1,vs1}, // cube 3 | | 1 | 1 |
130
131 {vs0,vsX,vs0}, // cube 4 | | | |
132 {vs0,vsX,vs1}, // cube 5 | | | 2 |
133 {vs1,vsX,vs0}, // cube 6 | 0 | | |
134 {vs1,vsX,vs1}, // cube 7 | 1 | | 3 |
135
136 {vs0,vs0,vsX}, // cube 8 | | | |
137 {vs0,vs1,vsX}, // cube 9 | | 2 | |
138 {vs1,vs0,vsX}, // cube 10 | 2 | | |
139 {vs1,vs1,vsX} // cube 11 | 3 | 3 | |
140 },
141 { // ExorLink-4 Rules Generating Rules
142 // | 0 | 1 | 2 | 4 | - sections
143 // |---------------|
144 {vsX,vs0,vs0,vs0}, // cube 0 | | | | |
145 {vsX,vs0,vs0,vs1}, // cube 1 | | | | 0 |
146 {vsX,vs0,vs1,vs0}, // cube 2 | | | 0 | |
147 {vsX,vs0,vs1,vs1}, // cube 3 | | | 1 | 1 |
148 {vsX,vs1,vs0,vs0}, // cube 4 | | 0 | | |
149 {vsX,vs1,vs0,vs1}, // cube 5 | | 1 | | 2 |
150 {vsX,vs1,vs1,vs0}, // cube 6 | | 2 | 2 | |
151 {vsX,vs1,vs1,vs1}, // cube 7 | | 3 | 3 | 3 |
152
153 {vs0,vsX,vs0,vs0}, // cube 8 | | | | |
154 {vs0,vsX,vs0,vs1}, // cube 9 | | | | 4 |
155 {vs0,vsX,vs1,vs0}, // cube 10 | | | 4 | |
156 {vs0,vsX,vs1,vs1}, // cube 11 | | | 5 | 5 |
157 {vs1,vsX,vs0,vs0}, // cube 12 | 0 | | | |
158 {vs1,vsX,vs0,vs1}, // cube 13 | 1 | | | 6 |
159 {vs1,vsX,vs1,vs0}, // cube 14 | 2 | | 6 | |
160 {vs1,vsX,vs1,vs1}, // cube 15 | 3 | | 7 | 7 |
161
162 {vs0,vs0,vsX,vs0}, // cube 16 | | | | |
163 {vs0,vs0,vsX,vs1}, // cube 17 | | | | 8 |
164 {vs0,vs1,vsX,vs0}, // cube 18 | | 4 | | |
165 {vs0,vs1,vsX,vs1}, // cube 19 | | 5 | | 9 |
166 {vs1,vs0,vsX,vs0}, // cube 20 | 4 | | | |
167 {vs1,vs0,vsX,vs1}, // cube 21 | 5 | | | 10|
168 {vs1,vs1,vsX,vs0}, // cube 22 | 6 | 6 | | |
169 {vs1,vs1,vsX,vs1}, // cube 23 | 7 | 7 | | 11|
170
171 {vs0,vs0,vs0,vsX}, // cube 24 | | | | |
172 {vs0,vs0,vs1,vsX}, // cube 25 | | | 8 | |
173 {vs0,vs1,vs0,vsX}, // cube 26 | | 8 | | |
174 {vs0,vs1,vs1,vsX}, // cube 27 | | 9 | 9 | |
175 {vs1,vs0,vs0,vsX}, // cube 28 | 8 | | | |
176 {vs1,vs0,vs1,vsX}, // cube 29 | 9 | | 10| |
177 {vs1,vs1,vs0,vsX}, // cube 30 | 10| 10| | |
178 {vs1,vs1,vs1,vsX} // cube 31 | 11| 11| 11| |
179 }
180 };
181
182 // these cubes are combined into groups
183 static int s_ELGroupRules[3][24][4] = {
184 { // ExorLink-2 Group Forming Rules
185 {0,3}, // group 0 - section 0
186 {2,1} // group 1 - section 1
187 },
188 { // ExorLink-3 Group Forming Rules
189 {0,6,11}, // group 0 - section 0
190 {0,7,10}, // group 1
191 {4,2,11}, // group 2 - section 1
192 {4,3,9}, // group 3
193 {8,1,7}, // group 4 - section 2
194 {8,3,5} // group 5
195 },
196 { // ExorLink-4 Group Forming Rules
197 // section 0: (0-12)(1-13)(2-14)(3-15)(4-20)(5-21)(6-22)(7-23)(8-28)(9-29)(10-30)(11-31)
198 {0,12,22,31}, // group 0 // {0,6,11}, // group 0 - section 0
199 {0,12,23,30}, // group 1 // {0,7,10}, // group 1
200 {0,20,14,31}, // group 2 // {4,2,11}, // group 2
201 {0,20,15,29}, // group 3 // {4,3,9}, // group 3
202 {0,28,13,23}, // group 4 // {8,1,7}, // group 4
203 {0,28,15,21}, // group 5 // {8,3,5} // group 5
204 // section 1: (0-4)(1-5)(2-6)(3-7)(4-18)(5-19)(6-22)(7-23)(8-26)(9-27)(10-30)(11-31)
205 {8,4,22,31}, // group 6
206 {8,4,23,30}, // group 7
207 {8,18,6,31}, // group 8
208 {8,18,7,27}, // group 9
209 {8,26,5,23}, // group 10
210 {8,26,7,19}, // group 11
211 // section 2: (0-2)(1-3)(2-6)(3-7)(4-10)(5-11)(6-14)(7-15)(8-25)(9-27)(10-29)(11-31)
212 {16,2,14,31}, // group 12
213 {16,2,15,29}, // group 13
214 {16,10,6,31}, // group 14
215 {16,10,7,27}, // group 15
216 {16,25,3,15}, // group 16
217 {16,25,7,11}, // group 17
218 // section 3: (0-1)(1-3)(2-5)(3-7)(4-9)(5-11)(6-13)(7-15)(8-17)(9-19)(10-21)(11-23)
219 {24,1,13,23}, // group 18
220 {24,1,15,21}, // group 19
221 {24,9, 5,23}, // group 20
222 {24,9, 7,19}, // group 21
223 {24,17,3,15}, // group 22
224 {24,17,7,11} // group 23
225 }
226 };
227
228 // it is assumed that if literals in the first cube, second cube
229 // and their EXOR are 0 or 1 (as opposed to -), they are written
230 // into a mask, which is used to count the number of literals in
231 // the cube groups cubes
232 //
233 // below is the set of masks selecting literals belonging
234 // to the given cube of the group
235
236 static drow s_CubeLitMasks[3][32] = {
237 { // ExorLink-2 Literal Counting Masks
238 // v3 v2 v1 v0
239 // -xBA -xBA -xBA -xBA
240 // -------------------
241 0x14, // cube 0 <0000 0000 0001 0100> {vsX,vs0}
242 0x24, // cube 1 <0000 0000 0010 0100> {vsX,vs1}
243 0x41, // cube 2 <0000 0000 0100 0001> {vs0,vsX}
244 0x42, // cube 3 <0000 0000 0100 0010> {vs1,vsX}
245 },
246 { // ExorLink-3 Literal Counting Masks
247 0x114, // cube 0 <0000 0001 0001 0100> {vsX,vs0,vs0}
248 0x214, // cube 1 <0000 0010 0001 0100> {vsX,vs0,vs1}
249 0x124, // cube 2 <0000 0001 0010 0100> {vsX,vs1,vs0}
250 0x224, // cube 3 <0000 0010 0010 0100> {vsX,vs1,vs1}
251 0x141, // cube 4 <0000 0001 0100 0001> {vs0,vsX,vs0}
252 0x241, // cube 5 <0000 0010 0100 0001> {vs0,vsX,vs1}
253 0x142, // cube 6 <0000 0001 0100 0010> {vs1,vsX,vs0}
254 0x242, // cube 7 <0000 0010 0100 0010> {vs1,vsX,vs1}
255 0x411, // cube 8 <0000 0100 0001 0001> {vs0,vs0,vsX}
256 0x421, // cube 9 <0000 0100 0010 0001> {vs0,vs1,vsX}
257 0x412, // cube 10 <0000 0100 0001 0010> {vs1,vs0,vsX}
258 0x422, // cube 11 <0000 0100 0010 0010> {vs1,vs1,vsX}
259 },
260 { // ExorLink-4 Literal Counting Masks
261 0x1114, // cube 0 <0001 0001 0001 0100> {vsX,vs0,vs0,vs0}
262 0x2114, // cube 1 <0010 0001 0001 0100> {vsX,vs0,vs0,vs1}
263 0x1214, // cube 2 <0001 0010 0001 0100> {vsX,vs0,vs1,vs0}
264 0x2214, // cube 3 <0010 0010 0001 0100> {vsX,vs0,vs1,vs1}
265 0x1124, // cube 4 <0001 0001 0010 0100> {vsX,vs1,vs0,vs0}
266 0x2124, // cube 5 <0010 0001 0010 0100> {vsX,vs1,vs0,vs1}
267 0x1224, // cube 6 <0001 0010 0010 0100> {vsX,vs1,vs1,vs0}
268 0x2224, // cube 7 <0010 0010 0010 0100> {vsX,vs1,vs1,vs1}
269 0x1141, // cube 8 <0001 0001 0100 0001> {vs0,vsX,vs0,vs0}
270 0x2141, // cube 9 <0010 0001 0100 0001> {vs0,vsX,vs0,vs1}
271 0x1241, // cube 10 <0001 0010 0100 0001> {vs0,vsX,vs1,vs0}
272 0x2241, // cube 11 <0010 0010 0100 0001> {vs0,vsX,vs1,vs1}
273 0x1142, // cube 12 <0001 0001 0100 0010> {vs1,vsX,vs0,vs0}
274 0x2142, // cube 13 <0010 0001 0100 0010> {vs1,vsX,vs0,vs1}
275 0x1242, // cube 14 <0001 0010 0100 0010> {vs1,vsX,vs1,vs0}
276 0x2242, // cube 15 <0010 0010 0100 0010> {vs1,vsX,vs1,vs1}
277 0x1411, // cube 16 <0001 0100 0001 0001> {vs0,vs0,vsX,vs0}
278 0x2411, // cube 17 <0010 0100 0001 0001> {vs0,vs0,vsX,vs1}
279 0x1421, // cube 18 <0001 0100 0010 0001> {vs0,vs1,vsX,vs0}
280 0x2421, // cube 19 <0010 0100 0010 0001> {vs0,vs1,vsX,vs1}
281 0x1412, // cube 20 <0001 0100 0001 0010> {vs1,vs0,vsX,vs0}
282 0x2412, // cube 21 <0010 0100 0001 0010> {vs1,vs0,vsX,vs1}
283 0x1422, // cube 22 <0001 0100 0010 0010> {vs1,vs1,vsX,vs0}
284 0x2422, // cube 23 <0010 0100 0010 0010> {vs1,vs1,vsX,vs1}
285 0x4111, // cube 24 <0100 0001 0001 0001> {vs0,vs0,vs0,vsX}
286 0x4211, // cube 25 <0100 0010 0001 0001> {vs0,vs0,vs1,vsX}
287 0x4121, // cube 26 <0100 0001 0010 0001> {vs0,vs1,vs0,vsX}
288 0x4221, // cube 27 <0100 0010 0010 0001> {vs0,vs1,vs1,vsX}
289 0x4112, // cube 28 <0100 0001 0001 0010> {vs1,vs0,vs0,vsX}
290 0x4212, // cube 29 <0100 0010 0001 0010> {vs1,vs0,vs1,vsX}
291 0x4122, // cube 30 <0100 0001 0010 0010> {vs1,vs1,vs0,vsX}
292 0x4222, // cube 31 <0100 0010 0010 0010> {vs1,vs1,vs1,vsX}
293 }
294 };
295
296 static drow s_BitMasks[32] =
297 {
298 0x00000001,0x00000002,0x00000004,0x00000008,
299 0x00000010,0x00000020,0x00000040,0x00000080,
300 0x00000100,0x00000200,0x00000400,0x00000800,
301 0x00001000,0x00002000,0x00004000,0x00008000,
302 0x00010000,0x00020000,0x00040000,0x00080000,
303 0x00100000,0x00200000,0x00400000,0x00800000,
304 0x01000000,0x02000000,0x04000000,0x08000000,
305 0x10000000,0x20000000,0x40000000,0x80000000
306 };
307
308 ////////////////////////////////////////////////////////////////////////
309 /// STATIC VARIABLES ///
310 ////////////////////////////////////////////////////////////////////////
311
312 // this flag is TRUE as long as the storage is allocated
313 static int fWorking;
314
315 // set these flags to have minimum literal groups generated first
316 static int fMinLitGroupsFirst[4] = { 0 /*dist2*/, 0 /*dist3*/, 0 /*dist4*/};
317
318 static int nDist;
319 static int nCubes;
320 static int nCubesInGroup;
321 static int nGroups;
322 static Cube *pCA, *pCB;
323
324 // storage for variable numbers that are different in the cubes
325 static int DiffVars[5];
326 static int* pDiffVars;
327 static int nDifferentVars;
328
329 // storage for the bits and words of different input variables
330 static int nDiffVarsIn;
331 static int DiffVarWords[5];
332 static int DiffVarBits[5];
333
334 // literal mask used to count the number of literals in the cubes
335 static drow MaskLiterals;
336 // the base for counting literals
337 static int StartingLiterals;
338 // the number of literals in each cube
339 static int CubeLiterals[32];
340 static int BitShift;
341 static int DiffVarValues[4][3];
342 static int Value;
343
344 // the sorted array of groups in the increasing order of costs
345 static int GroupCosts[32];
346 static int GroupCostBest;
347 static int GroupCostBestNum;
348
349 static int CubeNum;
350 static int NewZ;
351 static drow Temp;
352
353 // the cubes currently created
354 static Cube* ELCubes[32];
355
356 // the bit string with 1's corresponding to cubes in ELCubes[]
357 // that constitute the last group
358 static drow LastGroup;
359
360 static int GroupOrder[24];
361 static drow VisitedGroups;
362 static int nVisitedGroups;
363
364 //int RemainderBits = (nVars*2)%(sizeof(drow)*8);
365 //int TotalWords = (nVars*2)/(sizeof(drow)*8) + (RemainderBits > 0);
366 static drow DammyBitData[(MAXVARS*2)/(sizeof(drow)*8)+(MAXVARS*2)%(sizeof(drow)*8)];
367
368 ////////////////////////////////////////////////////////////////////////
369 /// FUNCTION DEFINTIONS ///
370 ////////////////////////////////////////////////////////////////////////
371
372 // IDEA! if we already used a cube to count distances and it did not improve
373 // there is no need to try it again with other group
374 // (this idea works only for ExorLink-2 and -3)
375
ExorLinkCubeIteratorStart(Cube ** pGroup,Cube * pC1,Cube * pC2,cubedist Dist)376 int ExorLinkCubeIteratorStart( Cube** pGroup, Cube* pC1, Cube* pC2, cubedist Dist )
377 // this function starts the Exor-Link iterator, which iterates
378 // through the cube groups starting from the group with min literals
379 // returns 1 on success, returns 0 if the cubes have wrong distance
380 {
381 int i, c;
382
383 // check that everything is okey
384 assert( pC1 != NULL );
385 assert( pC2 != NULL );
386 assert( !fWorking );
387
388 nDist = Dist;
389 nCubes = Dist + 2;
390 nCubesInGroup = s_ELnCubes[nDist];
391 nGroups = s_ELnGroups[Dist];
392 pCA = pC1;
393 pCB = pC2;
394 // find what variables are different in these two cubes
395 // FindDiffVars returns DiffVars[0] < 0, if the output is different
396 nDifferentVars = FindDiffVars( DiffVars, pCA, pCB );
397 if ( nCubes != nDifferentVars )
398 {
399 // cout << "ExorLinkCubeIterator(): Distance mismatch";
400 // cout << " nCubes = " << nCubes << " nDiffVars = " << nDifferentVars << endl;
401 fWorking = 0;
402 return 0;
403 }
404
405 // copy the input variable cube data into DammyBitData[]
406 for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
407 DammyBitData[i] = pCA->pCubeDataIn[i];
408
409 // find the number of different input variables
410 nDiffVarsIn = ( DiffVars[0] >= 0 )? nCubes: nCubes-1;
411 // assign the pointer to the place where the number of diff input vars is stored
412 pDiffVars = ( DiffVars[0] >= 0 )? DiffVars: DiffVars+1;
413 // find the bit offsets and remove different variables
414 for ( i = 0; i < nDiffVarsIn; i++ )
415 {
416 DiffVarWords[i] = ((2*pDiffVars[i]) >> LOGBPI) ;
417 DiffVarBits[i] = ((2*pDiffVars[i]) & BPIMASK);
418 // clear this position
419 DammyBitData[ DiffVarWords[i] ] &= ~( 3 << DiffVarBits[i] );
420 }
421
422 // extract the values from the cubes and create the mask of literals
423 MaskLiterals = 0;
424 // initialize the base for literal counts
425 StartingLiterals = pCA->a;
426 for ( i = 0, BitShift = 0; i < nDiffVarsIn; i++, BitShift++ )
427 {
428 DiffVarValues[i][0] = ( pCA->pCubeDataIn[DiffVarWords[i]] >> DiffVarBits[i] ) & 3;
429 if ( DiffVarValues[i][0] != VAR_ABS )
430 {
431 MaskLiterals |= ( 1 << BitShift );
432 // update the base for literal counts
433 StartingLiterals--;
434 }
435 BitShift++;
436
437 DiffVarValues[i][1] = ( pCB->pCubeDataIn[DiffVarWords[i]] >> DiffVarBits[i] ) & 3;
438 if ( DiffVarValues[i][1] != VAR_ABS )
439 MaskLiterals |= ( 1 << BitShift );
440 BitShift++;
441
442 DiffVarValues[i][2] = DiffVarValues[i][0] ^ DiffVarValues[i][1];
443 if ( DiffVarValues[i][2] != VAR_ABS )
444 MaskLiterals |= ( 1 << BitShift );
445 BitShift++;
446 }
447
448 // count the number of additional literals in each cube of the group
449 for ( i = 0; i < nCubesInGroup; i++ )
450 CubeLiterals[i] = BitCount[ MaskLiterals & s_CubeLitMasks[Dist][i] ];
451
452 // compute the costs of all groups
453 for ( i = 0; i < nGroups; i++ )
454 // go over all cubes in the group
455 for ( GroupCosts[i] = 0, c = 0; c < nCubes; c++ )
456 GroupCosts[i] += CubeLiterals[ s_ELGroupRules[Dist][i][c] ];
457
458 // find the best cost group
459 if ( fMinLitGroupsFirst[Dist] )
460 { // find the minimum cost group
461 GroupCostBest = LARGE_NUM;
462 for ( i = 0; i < nGroups; i++ )
463 if ( GroupCostBest > GroupCosts[i] )
464 {
465 GroupCostBest = GroupCosts[i];
466 GroupCostBestNum = i;
467 }
468 }
469 else
470 { // find the maximum cost group
471 GroupCostBest = -1;
472 for ( i = 0; i < nGroups; i++ )
473 if ( GroupCostBest < GroupCosts[i] )
474 {
475 GroupCostBest = GroupCosts[i];
476 GroupCostBestNum = i;
477 }
478 }
479
480 // create the cubes with min number of literals needed for the group
481 LastGroup = 0;
482 for ( c = 0; c < nCubes; c++ )
483 {
484 CubeNum = s_ELGroupRules[Dist][GroupCostBestNum][c];
485 LastGroup |= s_BitMasks[CubeNum];
486
487 // bring a cube from the free cube list
488 ELCubes[CubeNum] = GetFreeCube();
489
490 // copy the input bit data into the cube
491 for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
492 ELCubes[CubeNum]->pCubeDataIn[i] = DammyBitData[i];
493
494 // copy the output bit data into the cube
495 NewZ = 0;
496 if ( DiffVars[0] >= 0 ) // the output is not involved in ExorLink
497 {
498 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
499 ELCubes[CubeNum]->pCubeDataOut[i] = pCA->pCubeDataOut[i];
500 NewZ = pCA->z;
501 }
502 else // the output is involved
503 { // determine where the output information comes from
504 Value = s_ELCubeRules[Dist][CubeNum][nDiffVarsIn];
505 if ( Value == vs0 )
506 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
507 {
508 Temp = pCA->pCubeDataOut[i];
509 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
510 NewZ += BIT_COUNT(Temp);
511 }
512 else if ( Value == vs1 )
513 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
514 {
515 Temp = pCB->pCubeDataOut[i];
516 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
517 NewZ += BIT_COUNT(Temp);
518 }
519 else if ( Value == vsX )
520 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
521 {
522 Temp = pCA->pCubeDataOut[i] ^ pCB->pCubeDataOut[i];
523 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
524 NewZ += BIT_COUNT(Temp);
525 }
526 }
527
528 // set the variables that should be there
529 for ( i = 0; i < nDiffVarsIn; i++ )
530 {
531 Value = DiffVarValues[i][ s_ELCubeRules[Dist][CubeNum][i] ];
532 ELCubes[CubeNum]->pCubeDataIn[ DiffVarWords[i] ] |= ( Value << DiffVarBits[i] );
533 }
534
535 // set the number of literals
536 ELCubes[CubeNum]->a = StartingLiterals + CubeLiterals[CubeNum];
537 ELCubes[CubeNum]->z = NewZ;
538 ELCubes[CubeNum]->q = ComputeQCostBits( ELCubes[CubeNum] );
539
540 // assign the ID
541 ELCubes[CubeNum]->ID = g_CoverInfo.cIDs++;
542 // skip through zero-ID
543 if ( g_CoverInfo.cIDs == 256 )
544 g_CoverInfo.cIDs = 1;
545
546 // prepare the return array
547 pGroup[c] = ELCubes[CubeNum];
548 }
549
550 // mark this group as visited
551 VisitedGroups |= s_BitMasks[ GroupCostBestNum ];
552 // set the first visited group number
553 GroupOrder[0] = GroupCostBestNum;
554 // increment the counter of visited groups
555 nVisitedGroups = 1;
556 fWorking = 1;
557 return 1;
558 }
559
ExorLinkCubeIteratorNext(Cube ** pGroup)560 int ExorLinkCubeIteratorNext( Cube** pGroup )
561 // give the next group in the decreasing order of sum of literals
562 // returns 1 on success, returns 0 if there are no more groups
563 {
564 int i, c;
565
566 // check that everything is okey
567 assert( fWorking );
568
569 if ( nVisitedGroups == nGroups )
570 // we have iterated through all groups
571 return 0;
572
573 // find the min/max cost group
574 if ( fMinLitGroupsFirst[nDist] )
575 // if ( nCubes == 4 )
576 { // find the minimum cost
577 // go through all groups
578 GroupCostBest = LARGE_NUM;
579 for ( i = 0; i < nGroups; i++ )
580 if ( !(VisitedGroups & s_BitMasks[i]) && GroupCostBest > GroupCosts[i] )
581 {
582 GroupCostBest = GroupCosts[i];
583 GroupCostBestNum = i;
584 }
585 assert( GroupCostBest != LARGE_NUM );
586 }
587 else
588 { // find the maximum cost
589 // go through all groups
590 GroupCostBest = -1;
591 for ( i = 0; i < nGroups; i++ )
592 if ( !(VisitedGroups & s_BitMasks[i]) && GroupCostBest < GroupCosts[i] )
593 {
594 GroupCostBest = GroupCosts[i];
595 GroupCostBestNum = i;
596 }
597 assert( GroupCostBest != -1 );
598 }
599
600 // create the cubes needed for the group, if they are not created already
601 LastGroup = 0;
602 for ( c = 0; c < nCubes; c++ )
603 {
604 CubeNum = s_ELGroupRules[nDist][GroupCostBestNum][c];
605 LastGroup |= s_BitMasks[CubeNum];
606
607 if ( ELCubes[CubeNum] == NULL ) // this cube does not exist
608 {
609 // bring a cube from the free cube list
610 ELCubes[CubeNum] = GetFreeCube();
611
612 // copy the input bit data into the cube
613 for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
614 ELCubes[CubeNum]->pCubeDataIn[i] = DammyBitData[i];
615
616 // copy the output bit data into the cube
617 NewZ = 0;
618 if ( DiffVars[0] >= 0 ) // the output is not involved in ExorLink
619 {
620 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
621 ELCubes[CubeNum]->pCubeDataOut[i] = pCA->pCubeDataOut[i];
622 NewZ = pCA->z;
623 }
624 else // the output is involved
625 { // determine where the output information comes from
626 Value = s_ELCubeRules[nDist][CubeNum][nDiffVarsIn];
627 if ( Value == vs0 )
628 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
629 {
630 Temp = pCA->pCubeDataOut[i];
631 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
632 NewZ += BIT_COUNT(Temp);
633 }
634 else if ( Value == vs1 )
635 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
636 {
637 Temp = pCB->pCubeDataOut[i];
638 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
639 NewZ += BIT_COUNT(Temp);
640 }
641 else if ( Value == vsX )
642 for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
643 {
644 Temp = pCA->pCubeDataOut[i] ^ pCB->pCubeDataOut[i];
645 ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
646 NewZ += BIT_COUNT(Temp);
647 }
648 }
649
650 // set the variables that should be there
651 for ( i = 0; i < nDiffVarsIn; i++ )
652 {
653 Value = DiffVarValues[i][ s_ELCubeRules[nDist][CubeNum][i] ];
654 ELCubes[CubeNum]->pCubeDataIn[ DiffVarWords[i] ] |= ( Value << DiffVarBits[i] );
655 }
656
657 // set the number of literals and output ones
658 ELCubes[CubeNum]->a = StartingLiterals + CubeLiterals[CubeNum];
659 ELCubes[CubeNum]->z = NewZ;
660 ELCubes[CubeNum]->q = ComputeQCostBits( ELCubes[CubeNum] );
661 assert( NewZ != 255 );
662
663 // assign the ID
664 ELCubes[CubeNum]->ID = g_CoverInfo.cIDs++;
665 // skip through zero-ID
666 if ( g_CoverInfo.cIDs == 256 )
667 g_CoverInfo.cIDs = 1;
668
669 }
670 // prepare the return array
671 pGroup[c] = ELCubes[CubeNum];
672 }
673
674 // mark this group as visited
675 VisitedGroups |= s_BitMasks[ GroupCostBestNum ];
676 // set the next visited group number and
677 // increment the counter of visited groups
678 GroupOrder[ nVisitedGroups++ ] = GroupCostBestNum;
679 return 1;
680 }
681
ExorLinkCubeIteratorPick(Cube ** pGroup,int g)682 int ExorLinkCubeIteratorPick( Cube** pGroup, int g )
683 // gives the group #g in the order in which the groups were given
684 // during iteration
685 // returns 1 on success, returns 0 if something is wrong (g is too large)
686 {
687 int GroupNum, c;
688
689 assert( fWorking );
690 assert( g >= 0 && g < nGroups );
691 assert( VisitedGroups & s_BitMasks[g] );
692
693 GroupNum = GroupOrder[g];
694 // form the group
695 LastGroup = 0;
696 for ( c = 0; c < nCubes; c++ )
697 {
698 CubeNum = s_ELGroupRules[nDist][GroupNum][c];
699
700 // remember this group as the last one
701 LastGroup |= s_BitMasks[CubeNum];
702
703 assert( ELCubes[CubeNum] != NULL ); // this cube should exist
704 // prepare the return array
705 pGroup[c] = ELCubes[CubeNum];
706 }
707 return 1;
708 }
709
ExorLinkCubeIteratorCleanUp(int fTakeLastGroup)710 void ExorLinkCubeIteratorCleanUp( int fTakeLastGroup )
711 // removes the cubes from the store back into the list of free cubes
712 // if fTakeLastGroup is 0, removes all cubes
713 // if fTakeLastGroup is 1, does not store the last group
714 {
715 int c;
716 assert( fWorking );
717
718 // put cubes back
719 // set the cube pointers to zero
720 if ( fTakeLastGroup == 0 )
721 for ( c = 0; c < nCubesInGroup; c++ )
722 {
723 ELCubes[c]->fMark = 0;
724 AddToFreeCubes( ELCubes[c] );
725 ELCubes[c] = NULL;
726 }
727 else
728 for ( c = 0; c < nCubesInGroup; c++ )
729 if ( ELCubes[c] )
730 {
731 ELCubes[c]->fMark = 0;
732 if ( (LastGroup & s_BitMasks[c]) == 0 ) // does not belong to the last group
733 AddToFreeCubes( ELCubes[c] );
734 ELCubes[c] = NULL;
735 }
736
737 // set the cube groups to zero
738 VisitedGroups = 0;
739 // shut down the iterator
740 fWorking = 0;
741 }
742
743
744 ///////////////////////////////////////////////////////////////////
745 //////////// End of File /////////////////
746 ///////////////////////////////////////////////////////////////////
747
748
749 ABC_NAMESPACE_IMPL_END
750