exorLink.c File Reference

#include "exor.h"

Include dependency graph for exorLink.c:

Go to the source code of this file.

Macros
#define	LARGE_NUM   1000000
	MACRO DEFINITIONS ///.

Enumerations
enum	{ vs0 , vs1 , vsX }

Functions
int	ExorLinkCubeIteratorStart (Cube **pGroup, Cube *pC1, Cube *pC2, cubedist Dist)
	EXTERNAL FUNCTION DECLARATIONS ///.
int	ExorLinkCubeIteratorNext (Cube **pGroup)
int	ExorLinkCubeIteratorPick (Cube **pGroup, int g)
void	ExorLinkCubeIteratorCleanUp (int fTakeLastGroup)

Variables
cinfo	g_CoverInfo
	EXTERNAL VARIABLES ///.
Cube *	g_CubesFree
byte	BitCount []
const int	s_ELMax = 4
	EXORLINK INFO ///.
const int	s_ELnCubes [4] = { 4, 12, 32, 80 }
const int	s_ELnGroups [4] = { 2, 6, 24, 120 }

Macro Definition Documentation

LARGE_NUM

#define LARGE_NUM   1000000

MACRO DEFINITIONS ///.

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/ ///

Definition at line 49 of file exorLink.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
vs0
vs1
vsX

Definition at line 108 of file exorLink.c.

{ vs0, vs1, vsX };

Function Documentation

ExorLinkCubeIteratorCleanUp()

void ExorLinkCubeIteratorCleanUp

(

int

fTakeLastGroup

)

Definition at line 710 of file exorLink.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ExorLinkCubeIteratorNext()

int ExorLinkCubeIteratorNext

(

Cube **

pGroup

)

Definition at line 560 of file exorLink.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ExorLinkCubeIteratorPick()

int ExorLinkCubeIteratorPick	(	Cube **	pGroup,
		int	g )

Definition at line 682 of file exorLink.c.

{
    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;
}

ExorLinkCubeIteratorStart()

int ExorLinkCubeIteratorStart	(	Cube **	pGroup,
		Cube *	pC1,
		Cube *	pC2,
		cubedist	Dist )

EXTERNAL FUNCTION DECLARATIONS ///.

ExorLink Functions.

FUNCTION DEFINTIONS ///.

FUNCTIONS OF THIS MODULE ///

Definition at line 376 of file exorLink.c.

{
    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;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

BitCount

byte BitCount[]

extern

Definition at line 138 of file exorBits.c.

g_CoverInfo

cinfo g_CoverInfo

extern

EXTERNAL VARIABLES ///.

EXTERNAL VARIABLES ///.

EXTERNAL FUNCTIONS ///.

MACRO DEFINITIONS ///.

CFile****************************************************************

FileName [exor.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Exclusive sum-of-product minimization.]

Synopsis [Main procedure.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

exor.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>               ///
                                                            ///

                                                            ///
                   Main Module                              ///
          ESOP Minimization Task Coordinator                ///
                                                            ///
    1) interprets command line                              ///  
    2) calls the approapriate reading procedure             ///
    3) calls the minimization module                        ///
                                                            ///

Ver. 1.0. Started - July 18, 2000. Last update - July 20, 2000 /// Ver. 1.1. Started - July 24, 2000. Last update - July 29, 2000 /// Ver. 1.4. Started - Aug 10, 2000. Last update - Aug 26, 2000 /// Ver. 1.6. Started - Sep 11, 2000. Last update - Sep 15, 2000 /// Ver. 1.7. Started - Sep 20, 2000. Last update - Sep 23, 2000 /// ///

This software was tested with the BDD package "CUDD", v.2.3.0 /// by Fabio Somenzi /// http://vlsi.colorado.edu/~fabio/ ///

Definition at line 58 of file exor.c.

g_CubesFree

Cube* g_CubesFree

extern

s_ELMax

const int s_ELMax = 4

EXORLINK INFO ///.

Definition at line 96 of file exorLink.c.

s_ELnCubes

const int s_ELnCubes[4] = { 4, 12, 32, 80 }

Definition at line 103 of file exorLink.c.

{ 4, 12, 32, 80 };

s_ELnGroups

const int s_ELnGroups[4] = { 2, 6, 24, 120 }

Definition at line 104 of file exorLink.c.

{ 2,  6, 24, 120 };