exorLink.c

/**CFile****************************************************************

  FileName    [exorLink.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Exclusive sum-of-product minimization.]

  Synopsis    [Cube iterators.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: exorLink.c,v 1.0 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

////////////////////////////////////////////////////////////////////////
///                                                                  ///
///                  Implementation of EXORCISM - 4                  ///
///              An Exclusive Sum-of-Product Minimizer               ///
///                                                                  ///
///               Alan Mishchenko  <alanmi@ee.pdx.edu>               ///
///                                                                  ///
////////////////////////////////////////////////////////////////////////
///                                                                  ///
///                 Generation of ExorLinked Cubes                   ///
///                                                                  ///
///  Ver. 1.0. Started - July 26, 2000. Last update - July 29, 2000  ///
///  Ver. 1.4. Started -  Aug 10, 2000. Last update -  Aug 12, 2000  ///
///                                                                  ///
////////////////////////////////////////////////////////////////////////
///   This software was tested with the BDD package "CUDD", v.2.3.0  ///
///                          by Fabio Somenzi                        ///
///                  http://vlsi.colorado.edu/~fabio/                ///
////////////////////////////////////////////////////////////////////////

#include "exor.h"

ABC_NAMESPACE_IMPL_START

////////////////////////////////////////////////////////////////////////
///                       MACRO DEFINITIONS                          ///
////////////////////////////////////////////////////////////////////////

#define LARGE_NUM 1000000

////////////////////////////////////////////////////////////////////////
///                 EXTERNAL FUNCTION DECLARATIONS                   ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                    FUNCTIONS OF THIS MODULE                      ///
////////////////////////////////////////////////////////////////////////

int ExorLinkCubeIteratorStart( Cube** pGroup, Cube* pC1, Cube* pC2, cubedist Dist );
// this function starts the Exor-Link iterator, which iterates
// through the cube groups starting from the group with min literals
// returns 1 on success, returns 0 if the cubes have wrong distance

int ExorLinkCubeIteratorNext( Cube** pGroup );
// give the next group in the decreasing order of sum of literals
// returns 1 on success, returns 0 if there are no more groups

int ExorLinkCubeIteratorPick( Cube** pGroup, int g );
// gives the group #g in the order in which the groups were given
// during iteration
// returns 1 on success, returns 0 if something g is too large

void ExorLinkCubeIteratorCleanUp( int fTakeLastGroup );
// removes the cubes from the store back into the list of free cubes
// if fTakeLastGroup is 0, removes all cubes
// if fTakeLastGroup is 1, does not store the last group

////////////////////////////////////////////////////////////////////////
///                       EXTERNAL VARIABLES                         ///
////////////////////////////////////////////////////////////////////////

// information about the cube cover before
extern cinfo g_CoverInfo;
// new IDs are assigned only when it is known that the cubes are useful
// this is done in ExorLinkCubeIteratorCleanUp();

// the head of the list of free cubes
extern Cube* g_CubesFree;

extern byte BitCount[];

////////////////////////////////////////////////////////////////////////
///                         EXORLINK INFO                            ///
////////////////////////////////////////////////////////////////////////

const int s_ELMax = 4;

// ExorLink-2: there are 4 cubes,  2 literals each, combined into 2 groups
// ExorLink-3: there are 12 cubes, 3 literals each, combined into 6 groups
// ExorLink-4: there are 32 cubes, 4 literals each, combined into 24 groups
// ExorLink-5: there are 80 cubes, 5 literals each, combined into 120 groups
// Exorlink-n: there are n*2^(n-1) cubes, n literals each, combined into n! groups
const int s_ELnCubes[4]  = { 4, 12, 32, 80 };
const int s_ELnGroups[4] = { 2,  6, 24, 120 };

// value sets of cubes X{a0}Y{b0}Z{c0}U{d0} and X{a1}Y{b1}Z{c1}U{d1}
// used to represent the ExorLink cube generation rules
enum { vs0, vs1, vsX };
// vs0 = 0, // the value set of the first cube 
// vs1 = 1, // the value set of the second cube
// vsX = 2  // EXOR of the value sets of the first and second cubes

// representation of ExorLinked cubes
static int s_ELCubeRules[3][32][4]  = {
{ // ExorLink-2 Cube Generating Rules
                       // | 0 | 1 | - sections
                       // |-------|
    {vsX,vs0}, // cube 0  |   |   |
    {vsX,vs1}, // cube 1  |   | 0 |
    {vs0,vsX}, // cube 2  |   |   |
    {vs1,vsX}  // cube 3  | 0 |   |
},
{ // ExorLink-3 Cube Generating Rules
                            // | 0 | 1 | 2 | - sections
                            // |-----------|
    {vsX,vs0,vs0}, // cube 0   |   |   |   |
    {vsX,vs0,vs1}, // cube 1   |   |   | 0 |
    {vsX,vs1,vs0}, // cube 2   |   | 0 |   |
    {vsX,vs1,vs1}, // cube 3   |   | 1 | 1 |

    {vs0,vsX,vs0}, // cube 4   |   |   |   |
    {vs0,vsX,vs1}, // cube 5   |   |   | 2 |
    {vs1,vsX,vs0}, // cube 6   | 0 |   |   |
    {vs1,vsX,vs1}, // cube 7   | 1 |   | 3 |

    {vs0,vs0,vsX}, // cube 8   |   |   |   |
    {vs0,vs1,vsX}, // cube 9   |   | 2 |   |
    {vs1,vs0,vsX}, // cube 10  | 2 |   |   |
    {vs1,vs1,vsX}  // cube 11  | 3 | 3 |   |
},
{ // ExorLink-4 Rules Generating Rules
                                // | 0 | 1 | 2 | 4 | - sections
                                // |---------------|
    {vsX,vs0,vs0,vs0}, // cube 0   |   |   |   |   |
    {vsX,vs0,vs0,vs1}, // cube 1   |   |   |   | 0 |
    {vsX,vs0,vs1,vs0}, // cube 2   |   |   | 0 |   |
    {vsX,vs0,vs1,vs1}, // cube 3   |   |   | 1 | 1 |
    {vsX,vs1,vs0,vs0}, // cube 4   |   | 0 |   |   |
    {vsX,vs1,vs0,vs1}, // cube 5   |   | 1 |   | 2 |
    {vsX,vs1,vs1,vs0}, // cube 6   |   | 2 | 2 |   |
    {vsX,vs1,vs1,vs1}, // cube 7   |   | 3 | 3 | 3 |

    {vs0,vsX,vs0,vs0}, // cube 8   |   |   |   |   |
    {vs0,vsX,vs0,vs1}, // cube 9   |   |   |   | 4 |
    {vs0,vsX,vs1,vs0}, // cube 10  |   |   | 4 |   |
    {vs0,vsX,vs1,vs1}, // cube 11  |   |   | 5 | 5 |
    {vs1,vsX,vs0,vs0}, // cube 12  | 0 |   |   |   |
    {vs1,vsX,vs0,vs1}, // cube 13  | 1 |   |   | 6 |
    {vs1,vsX,vs1,vs0}, // cube 14  | 2 |   | 6 |   |
    {vs1,vsX,vs1,vs1}, // cube 15  | 3 |   | 7 | 7 |

    {vs0,vs0,vsX,vs0}, // cube 16  |   |   |   |   |
    {vs0,vs0,vsX,vs1}, // cube 17  |   |   |   | 8 |
    {vs0,vs1,vsX,vs0}, // cube 18  |   | 4 |   |   |
    {vs0,vs1,vsX,vs1}, // cube 19  |   | 5 |   | 9 |
    {vs1,vs0,vsX,vs0}, // cube 20  | 4 |   |   |   |
    {vs1,vs0,vsX,vs1}, // cube 21  | 5 |   |   | 10|
    {vs1,vs1,vsX,vs0}, // cube 22  | 6 | 6 |   |   |
    {vs1,vs1,vsX,vs1}, // cube 23  | 7 | 7 |   | 11|

    {vs0,vs0,vs0,vsX}, // cube 24  |   |   |   |   |
    {vs0,vs0,vs1,vsX}, // cube 25  |   |   | 8 |   |
    {vs0,vs1,vs0,vsX}, // cube 26  |   | 8 |   |   |
    {vs0,vs1,vs1,vsX}, // cube 27  |   | 9 | 9 |   |
    {vs1,vs0,vs0,vsX}, // cube 28  | 8 |   |   |   |
    {vs1,vs0,vs1,vsX}, // cube 29  | 9 |   | 10|   |
    {vs1,vs1,vs0,vsX}, // cube 30  | 10| 10|   |   |
    {vs1,vs1,vs1,vsX}  // cube 31  | 11| 11| 11|   |
}
};

// these cubes are combined into groups
static int s_ELGroupRules[3][24][4] = { 
{ // ExorLink-2 Group Forming Rules
    {0,3},  // group 0 - section 0
    {2,1}   // group 1 - section 1
},
{ // ExorLink-3 Group Forming Rules
    {0,6,11}, // group 0 - section 0 
    {0,7,10}, // group 1
    {4,2,11}, // group 2 - section 1 
    {4,3,9},  // group 3
    {8,1,7},  // group 4 - section 2 
    {8,3,5}   // group 5
},
{ // ExorLink-4 Group Forming Rules 
// 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)
    {0,12,22,31},  // group 0       // {0,6,11}, // group 0  - section 0
    {0,12,23,30},  // group 1       // {0,7,10}, // group 1
    {0,20,14,31},  // group 2       // {4,2,11}, // group 2
    {0,20,15,29},  // group 3       // {4,3,9},  // group 3
    {0,28,13,23},  // group 4       // {8,1,7},  // group 4
    {0,28,15,21},  // group 5       // {8,3,5}   // group 5
// 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)
    {8,4,22,31},   // group 6
    {8,4,23,30},   // group 7
    {8,18,6,31},   // group 8
    {8,18,7,27},   // group 9
    {8,26,5,23},   // group 10
    {8,26,7,19},   // group 11
// 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)
    {16,2,14,31},  // group 12
    {16,2,15,29},  // group 13
    {16,10,6,31},  // group 14
    {16,10,7,27},  // group 15
    {16,25,3,15},  // group 16
    {16,25,7,11},  // group 17
// 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)
    {24,1,13,23},  // group 18
    {24,1,15,21},  // group 19
    {24,9, 5,23},  // group 20
    {24,9, 7,19},  // group 21
    {24,17,3,15},  // group 22
    {24,17,7,11}   // group 23
}
};

// it is assumed that if literals in the first cube, second cube 
// and their EXOR are 0 or 1 (as opposed to -), they are written
// into a mask, which is used to count the number of literals in 
// the cube groups cubes
//
// below is the set of masks selecting literals belonging
// to the given cube of the group

static drow s_CubeLitMasks[3][32] = { 
{  // ExorLink-2 Literal Counting Masks
//                      v3   v2   v1   v0
//                     -xBA -xBA -xBA -xBA  
//                     -------------------
    0x14,  // cube 0  <0000 0000 0001 0100> {vsX,vs0}
    0x24,  // cube 1  <0000 0000 0010 0100> {vsX,vs1}
    0x41,  // cube 2  <0000 0000 0100 0001> {vs0,vsX}
    0x42,  // cube 3  <0000 0000 0100 0010> {vs1,vsX}
},
{  // ExorLink-3 Literal Counting Masks
    0x114, // cube 0  <0000 0001 0001 0100> {vsX,vs0,vs0}
    0x214, // cube 1  <0000 0010 0001 0100> {vsX,vs0,vs1}
    0x124, // cube 2  <0000 0001 0010 0100> {vsX,vs1,vs0}
    0x224, // cube 3  <0000 0010 0010 0100> {vsX,vs1,vs1}
    0x141, // cube 4  <0000 0001 0100 0001> {vs0,vsX,vs0}
    0x241, // cube 5  <0000 0010 0100 0001> {vs0,vsX,vs1}
    0x142, // cube 6  <0000 0001 0100 0010> {vs1,vsX,vs0}
    0x242, // cube 7  <0000 0010 0100 0010> {vs1,vsX,vs1}
    0x411, // cube 8  <0000 0100 0001 0001> {vs0,vs0,vsX}
    0x421, // cube 9  <0000 0100 0010 0001> {vs0,vs1,vsX}
    0x412, // cube 10 <0000 0100 0001 0010> {vs1,vs0,vsX}
    0x422, // cube 11 <0000 0100 0010 0010> {vs1,vs1,vsX}
},
{  // ExorLink-4 Literal Counting Masks
    0x1114, // cube 0   <0001 0001 0001 0100> {vsX,vs0,vs0,vs0}
    0x2114, // cube 1   <0010 0001 0001 0100> {vsX,vs0,vs0,vs1}
    0x1214, // cube 2   <0001 0010 0001 0100> {vsX,vs0,vs1,vs0}
    0x2214, // cube 3   <0010 0010 0001 0100> {vsX,vs0,vs1,vs1}
    0x1124, // cube 4   <0001 0001 0010 0100> {vsX,vs1,vs0,vs0}
    0x2124, // cube 5   <0010 0001 0010 0100> {vsX,vs1,vs0,vs1}
    0x1224, // cube 6   <0001 0010 0010 0100> {vsX,vs1,vs1,vs0}
    0x2224, // cube 7   <0010 0010 0010 0100> {vsX,vs1,vs1,vs1}
    0x1141, // cube 8   <0001 0001 0100 0001> {vs0,vsX,vs0,vs0}
    0x2141, // cube 9   <0010 0001 0100 0001> {vs0,vsX,vs0,vs1}
    0x1241, // cube 10  <0001 0010 0100 0001> {vs0,vsX,vs1,vs0}
    0x2241, // cube 11  <0010 0010 0100 0001> {vs0,vsX,vs1,vs1}
    0x1142, // cube 12  <0001 0001 0100 0010> {vs1,vsX,vs0,vs0}
    0x2142, // cube 13  <0010 0001 0100 0010> {vs1,vsX,vs0,vs1}
    0x1242, // cube 14  <0001 0010 0100 0010> {vs1,vsX,vs1,vs0}
    0x2242, // cube 15  <0010 0010 0100 0010> {vs1,vsX,vs1,vs1}
    0x1411, // cube 16  <0001 0100 0001 0001> {vs0,vs0,vsX,vs0}
    0x2411, // cube 17  <0010 0100 0001 0001> {vs0,vs0,vsX,vs1}
    0x1421, // cube 18  <0001 0100 0010 0001> {vs0,vs1,vsX,vs0}
    0x2421, // cube 19  <0010 0100 0010 0001> {vs0,vs1,vsX,vs1}
    0x1412, // cube 20  <0001 0100 0001 0010> {vs1,vs0,vsX,vs0}
    0x2412, // cube 21  <0010 0100 0001 0010> {vs1,vs0,vsX,vs1}
    0x1422, // cube 22  <0001 0100 0010 0010> {vs1,vs1,vsX,vs0}
    0x2422, // cube 23  <0010 0100 0010 0010> {vs1,vs1,vsX,vs1}
    0x4111, // cube 24  <0100 0001 0001 0001> {vs0,vs0,vs0,vsX}
    0x4211, // cube 25  <0100 0010 0001 0001> {vs0,vs0,vs1,vsX}
    0x4121, // cube 26  <0100 0001 0010 0001> {vs0,vs1,vs0,vsX}
    0x4221, // cube 27  <0100 0010 0010 0001> {vs0,vs1,vs1,vsX}
    0x4112, // cube 28  <0100 0001 0001 0010> {vs1,vs0,vs0,vsX}
    0x4212, // cube 29  <0100 0010 0001 0010> {vs1,vs0,vs1,vsX}
    0x4122, // cube 30  <0100 0001 0010 0010> {vs1,vs1,vs0,vsX}
    0x4222, // cube 31  <0100 0010 0010 0010> {vs1,vs1,vs1,vsX}
}
};

static drow s_BitMasks[32] = 
{
    0x00000001,0x00000002,0x00000004,0x00000008,
    0x00000010,0x00000020,0x00000040,0x00000080,
    0x00000100,0x00000200,0x00000400,0x00000800,
    0x00001000,0x00002000,0x00004000,0x00008000,
    0x00010000,0x00020000,0x00040000,0x00080000,
    0x00100000,0x00200000,0x00400000,0x00800000,
    0x01000000,0x02000000,0x04000000,0x08000000,
    0x10000000,0x20000000,0x40000000,0x80000000
};

////////////////////////////////////////////////////////////////////////
///                        STATIC VARIABLES                          ///
////////////////////////////////////////////////////////////////////////

// this flag is TRUE as long as the storage is allocated
static int fWorking;

// set these flags to have minimum literal groups generated first
static int fMinLitGroupsFirst[4] = { 0 /*dist2*/, 0 /*dist3*/, 0 /*dist4*/};

static int nDist;
static int nCubes;
static int nCubesInGroup;
static int nGroups;
static Cube *pCA, *pCB;

// storage for variable numbers that are different in the cubes
static int DiffVars[5];
static int* pDiffVars;
static int nDifferentVars;

// storage for the bits and words of different input variables
static int nDiffVarsIn;
static int DiffVarWords[5];
static int DiffVarBits[5];

// literal mask used to count the number of literals in the cubes
static drow MaskLiterals;
// the base for counting literals
static int StartingLiterals;
// the number of literals in each cube
static int CubeLiterals[32];
static int BitShift;
static int DiffVarValues[4][3];
static int Value;

// the sorted array of groups in the increasing order of costs
static int GroupCosts[32];
static int GroupCostBest;
static int GroupCostBestNum;

static int CubeNum;
static int NewZ;
static drow Temp;

// the cubes currently created
static Cube* ELCubes[32];

// the bit string with 1's corresponding to cubes in ELCubes[] 
// that constitute the last group
static drow LastGroup;

static int  GroupOrder[24];
static drow VisitedGroups;
static int  nVisitedGroups;

//int RemainderBits = (nVars*2)%(sizeof(drow)*8);
//int TotalWords    = (nVars*2)/(sizeof(drow)*8) + (RemainderBits > 0);
static drow DammyBitData[(MAXVARS*2)/(sizeof(drow)*8)+(MAXVARS*2)%(sizeof(drow)*8)];

////////////////////////////////////////////////////////////////////////
///                       FUNCTION DEFINTIONS                        ///
////////////////////////////////////////////////////////////////////////

// IDEA! if we already used a cube to count distances and it did not improve
// there is no need to try it again with other group
// (this idea works only for ExorLink-2 and -3)

int ExorLinkCubeIteratorStart( Cube** pGroup, Cube* pC1, Cube* pC2, cubedist Dist )
// this function starts the Exor-Link iterator, which iterates
// through the cube groups starting from the group with min literals
// returns 1 on success, returns 0 if the cubes have wrong distance
{
    int i, c;

    // check that everything is okey
    assert( pC1 != NULL );
    assert( pC2 != NULL );
    assert( !fWorking );

    nDist = Dist;
    nCubes = Dist + 2;
    nCubesInGroup = s_ELnCubes[nDist];
    nGroups = s_ELnGroups[Dist];
    pCA = pC1;
    pCB = pC2;
    // find what variables are different in these two cubes
    // FindDiffVars returns DiffVars[0] < 0, if the output is different
    nDifferentVars = FindDiffVars( DiffVars, pCA, pCB );
    if ( nCubes != nDifferentVars )
    {
//      cout << "ExorLinkCubeIterator(): Distance mismatch";
//      cout << " nCubes = " << nCubes << " nDiffVars = " << nDifferentVars << endl;
        fWorking = 0;
        return 0;
    }

    // copy the input variable cube data into DammyBitData[]
    for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
        DammyBitData[i] = pCA->pCubeDataIn[i];

    // find the number of different input variables
    nDiffVarsIn = ( DiffVars[0] >= 0 )? nCubes: nCubes-1;
    // assign the pointer to the place where the number of diff input vars is stored
    pDiffVars   = ( DiffVars[0] >= 0 )? DiffVars: DiffVars+1;
    // find the bit offsets and remove different variables
    for ( i = 0; i < nDiffVarsIn; i++ )
    {
        DiffVarWords[i] = ((2*pDiffVars[i]) >> LOGBPI) ;
        DiffVarBits[i]  = ((2*pDiffVars[i]) & BPIMASK);
        // clear this position
        DammyBitData[ DiffVarWords[i] ] &= ~( 3 << DiffVarBits[i] );
    }

    // extract the values from the cubes and create the mask of literals
    MaskLiterals = 0;
    // initialize the base for literal counts
    StartingLiterals = pCA->a;
    for ( i = 0, BitShift = 0; i < nDiffVarsIn; i++, BitShift++ )
    {
        DiffVarValues[i][0] = ( pCA->pCubeDataIn[DiffVarWords[i]] >> DiffVarBits[i] ) & 3;
        if ( DiffVarValues[i][0] != VAR_ABS )
        {
            MaskLiterals |= ( 1 << BitShift );
            // update the base for literal counts
            StartingLiterals--;
        }
        BitShift++;

        DiffVarValues[i][1] = ( pCB->pCubeDataIn[DiffVarWords[i]] >> DiffVarBits[i] ) & 3;
        if ( DiffVarValues[i][1] != VAR_ABS )
            MaskLiterals |= ( 1 << BitShift );
        BitShift++;

        DiffVarValues[i][2] = DiffVarValues[i][0] ^ DiffVarValues[i][1];
        if ( DiffVarValues[i][2] != VAR_ABS )
            MaskLiterals |= ( 1 << BitShift );
        BitShift++;
    }

    // count the number of additional literals in each cube of the group
    for ( i = 0; i < nCubesInGroup; i++ )
        CubeLiterals[i] = BitCount[ MaskLiterals & s_CubeLitMasks[Dist][i] ];

    // compute the costs of all groups
    for ( i = 0; i < nGroups; i++ )
        // go over all cubes in the group
        for ( GroupCosts[i] = 0, c = 0; c < nCubes; c++ )
            GroupCosts[i] += CubeLiterals[ s_ELGroupRules[Dist][i][c] ];

    // find the best cost group
    if ( fMinLitGroupsFirst[Dist] ) 
    { // find the minimum cost group
        GroupCostBest = LARGE_NUM;
        for ( i = 0; i < nGroups; i++ )
            if ( GroupCostBest > GroupCosts[i] )
            {
                GroupCostBest = GroupCosts[i];
                GroupCostBestNum = i;
            }
    }
    else 
    { // find the maximum cost group
        GroupCostBest = -1;
        for ( i = 0; i < nGroups; i++ )
            if ( GroupCostBest < GroupCosts[i] )
            {
                GroupCostBest = GroupCosts[i];
                GroupCostBestNum = i;
            }
    }

    // create the cubes with min number of literals needed for the group
    LastGroup = 0;
    for ( c = 0; c < nCubes; c++ )
    {
        CubeNum = s_ELGroupRules[Dist][GroupCostBestNum][c];
        LastGroup |= s_BitMasks[CubeNum];

        // bring a cube from the free cube list
        ELCubes[CubeNum] = GetFreeCube();

        // copy the input bit data into the cube 
        for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
            ELCubes[CubeNum]->pCubeDataIn[i] = DammyBitData[i];

        // copy the output bit data into the cube
        NewZ = 0;
        if ( DiffVars[0] >= 0 ) // the output is not involved in ExorLink
        {
            for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                ELCubes[CubeNum]->pCubeDataOut[i] = pCA->pCubeDataOut[i];
            NewZ = pCA->z;
        }
        else // the output is involved
        { // determine where the output information comes from
            Value = s_ELCubeRules[Dist][CubeNum][nDiffVarsIn];
            if ( Value == vs0 )
                for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                {
                    Temp = pCA->pCubeDataOut[i];
                    ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                    NewZ += BIT_COUNT(Temp);
                }
            else if ( Value == vs1 )
                for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                {
                    Temp = pCB->pCubeDataOut[i];
                    ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                    NewZ += BIT_COUNT(Temp);
                }
            else if ( Value == vsX )
                for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                {
                    Temp = pCA->pCubeDataOut[i] ^ pCB->pCubeDataOut[i];
                    ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                    NewZ += BIT_COUNT(Temp);
                }
        }

        // set the variables that should be there
        for ( i = 0; i < nDiffVarsIn; i++ )
        {
            Value = DiffVarValues[i][ s_ELCubeRules[Dist][CubeNum][i] ];
            ELCubes[CubeNum]->pCubeDataIn[ DiffVarWords[i] ] |= ( Value << DiffVarBits[i] );
        }

        // set the number of literals
        ELCubes[CubeNum]->a = StartingLiterals + CubeLiterals[CubeNum];
        ELCubes[CubeNum]->z = NewZ;
        ELCubes[CubeNum]->q = ComputeQCostBits( ELCubes[CubeNum] );

        // assign the ID
        ELCubes[CubeNum]->ID = g_CoverInfo.cIDs++;
        // skip through zero-ID
        if ( g_CoverInfo.cIDs == 256 )
            g_CoverInfo.cIDs = 1;

        // prepare the return array
        pGroup[c] = ELCubes[CubeNum];
    }

    // mark this group as visited 
    VisitedGroups |= s_BitMasks[ GroupCostBestNum ];
    // set the first visited group number
    GroupOrder[0] = GroupCostBestNum;
    // increment the counter of visited groups
    nVisitedGroups = 1;
    fWorking = 1;
    return 1;
}

int ExorLinkCubeIteratorNext( Cube** pGroup )
// give the next group in the decreasing order of sum of literals
// returns 1 on success, returns 0 if there are no more groups
{
    int i, c;

    // check that everything is okey
    assert( fWorking );

    if ( nVisitedGroups == nGroups ) 
    // we have iterated through all groups
        return 0;

    // find the min/max cost group
    if ( fMinLitGroupsFirst[nDist] ) 
//  if ( nCubes == 4 ) 
    { // find the minimum cost
        // go through all groups
        GroupCostBest = LARGE_NUM;
        for ( i = 0; i < nGroups; i++ )
            if ( !(VisitedGroups & s_BitMasks[i]) && GroupCostBest > GroupCosts[i] )
            {
                GroupCostBest = GroupCosts[i];
                GroupCostBestNum = i;
            }
        assert( GroupCostBest != LARGE_NUM );
    }
    else 
    { // find the maximum cost
        // go through all groups
        GroupCostBest = -1;
        for ( i = 0; i < nGroups; i++ )
            if ( !(VisitedGroups & s_BitMasks[i]) && GroupCostBest < GroupCosts[i] )
            {
                GroupCostBest = GroupCosts[i];
                GroupCostBestNum = i;
            }
        assert( GroupCostBest != -1 );
    }

    // create the cubes needed for the group, if they are not created already
    LastGroup = 0;
    for ( c = 0; c < nCubes; c++ )
    {
        CubeNum = s_ELGroupRules[nDist][GroupCostBestNum][c];
        LastGroup |= s_BitMasks[CubeNum];

        if ( ELCubes[CubeNum] == NULL ) // this cube does not exist
        {
            // bring a cube from the free cube list
            ELCubes[CubeNum] = GetFreeCube();

            // copy the input bit data into the cube 
            for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
                ELCubes[CubeNum]->pCubeDataIn[i] = DammyBitData[i];

            // copy the output bit data into the cube
            NewZ = 0;
            if ( DiffVars[0] >= 0 ) // the output is not involved in ExorLink
            {
                for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                    ELCubes[CubeNum]->pCubeDataOut[i] = pCA->pCubeDataOut[i];
                NewZ = pCA->z;
            }
            else // the output is involved
            { // determine where the output information comes from
                Value = s_ELCubeRules[nDist][CubeNum][nDiffVarsIn];
                if ( Value == vs0 )
                    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                    {
                        Temp = pCA->pCubeDataOut[i];
                        ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                        NewZ += BIT_COUNT(Temp);
                    }
                else if ( Value == vs1 )
                    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                    {
                        Temp = pCB->pCubeDataOut[i];
                        ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                        NewZ += BIT_COUNT(Temp);
                    }
                else if ( Value == vsX )
                    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                    {
                        Temp = pCA->pCubeDataOut[i] ^ pCB->pCubeDataOut[i];
                        ELCubes[CubeNum]->pCubeDataOut[i] = Temp;
                        NewZ += BIT_COUNT(Temp);
                    }
            }

            // set the variables that should be there
            for ( i = 0; i < nDiffVarsIn; i++ )
            {
                Value = DiffVarValues[i][ s_ELCubeRules[nDist][CubeNum][i] ];
                ELCubes[CubeNum]->pCubeDataIn[ DiffVarWords[i] ] |= ( Value << DiffVarBits[i] );
            }

            // set the number of literals and output ones
            ELCubes[CubeNum]->a = StartingLiterals + CubeLiterals[CubeNum];
            ELCubes[CubeNum]->z = NewZ;
            ELCubes[CubeNum]->q = ComputeQCostBits( ELCubes[CubeNum] );
            assert( NewZ != 255 );

            // assign the ID
            ELCubes[CubeNum]->ID = g_CoverInfo.cIDs++;
            // skip through zero-ID
            if ( g_CoverInfo.cIDs == 256 )
                g_CoverInfo.cIDs = 1;

        }
        // prepare the return array
        pGroup[c] = ELCubes[CubeNum];
    }

    // mark this group as visited 
    VisitedGroups |= s_BitMasks[ GroupCostBestNum ];
    // set the next visited group number and
    // increment the counter of visited groups
    GroupOrder[ nVisitedGroups++ ] = GroupCostBestNum;
    return 1;
}

int ExorLinkCubeIteratorPick( Cube** pGroup, int g )
// gives the group #g in the order in which the groups were given
// during iteration
// returns 1 on success, returns 0 if something is wrong (g is too large)
{
    int GroupNum, c;

    assert( fWorking );
    assert( g >= 0 && g < nGroups );
    assert( VisitedGroups & s_BitMasks[g] );

    GroupNum = GroupOrder[g];
    // form the group
    LastGroup = 0;
    for ( c = 0; c < nCubes; c++ )
    {
        CubeNum = s_ELGroupRules[nDist][GroupNum][c];

        // remember this group as the last one
        LastGroup |= s_BitMasks[CubeNum];

        assert( ELCubes[CubeNum] != NULL ); // this cube should exist
        // prepare the return array
        pGroup[c] = ELCubes[CubeNum];
    }
    return 1;
}

void ExorLinkCubeIteratorCleanUp( int fTakeLastGroup )
// removes the cubes from the store back into the list of free cubes
// if fTakeLastGroup is 0, removes all cubes
// if fTakeLastGroup is 1, does not store the last group
{
    int c;
    assert( fWorking );

    // put cubes back
    // set the cube pointers to zero
    if ( fTakeLastGroup == 0 )
        for ( c = 0; c < nCubesInGroup; c++ )
        {
            ELCubes[c]->fMark = 0;
            AddToFreeCubes( ELCubes[c] );
            ELCubes[c] = NULL;
        }
    else
        for ( c = 0; c < nCubesInGroup; c++ )
        if ( ELCubes[c] )
        {
            ELCubes[c]->fMark = 0;
            if ( (LastGroup & s_BitMasks[c]) == 0 ) // does not belong to the last group
                AddToFreeCubes( ELCubes[c] );
            ELCubes[c] = NULL;
        }

    // set the cube groups to zero
    VisitedGroups = 0;
    // shut down the iterator
    fWorking = 0;
}

    
///////////////////////////////////////////////////////////////////
////////////              End of File             /////////////////
///////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END