exorBits.c File Reference

#include "exor.h"

Include dependency graph for exorBits.c:

Go to the source code of this file.

Macros
#define	FULL16BITS   0x10000
#define	MARKNUMBER   200

Functions
int	GetDistance (Cube *pC1, Cube *pC2)
	FUNCTIONS OF THIS MODULE ///.
int	GetDistancePlus (Cube *pC1, Cube *pC2)
int	FindDiffVars (int *pDiffVars, Cube *pC1, Cube *pC2)
void	InsertVars (Cube *pC, int *pVars, int nVarsIn, int *pVarValues)
varvalue	GetVar (Cube *pC, int Var)
	INLINE FUNCTION DEFINITIONS ///.
void	ExorVar (Cube *pC, int Var, varvalue Val)
void	PrepareBitSetModule ()
	FUNCTION DEFINITIONS ///.
void	InsertVarsWithoutClearing (Cube *pC, int *pVars, int nVarsIn, int *pVarValues, int Output)

Variables
ABC_NAMESPACE_IMPL_START cinfo	g_CoverInfo
	MACRO DEFINITIONS ///.
unsigned char	BitCount [FULL16BITS]
int	s_DiffVarNum
int	s_DiffVarValueP_old
int	s_DiffVarValueP_new
int	s_DiffVarValueQ

Macro Definition Documentation

FULL16BITS

#define FULL16BITS   0x10000

Definition at line 134 of file exorBits.c.

MARKNUMBER

#define MARKNUMBER   200

Definition at line 135 of file exorBits.c.

Function Documentation

ExorVar()

void ExorVar	(	Cube *	pC,
		int	Var,
		varvalue	Val )

Definition at line 197 of file exorBits.c.

{
    int Bit = (Var<<1);
    pC->pCubeDataIn[VarWord(Bit)] ^= ( Val << VarBit(Bit) );
}

Here is the caller graph for this function:

FindDiffVars()

int FindDiffVars	(	int *	pDiffVars,
		Cube *	pC1,
		Cube *	pC2 )

Definition at line 304 of file exorBits.c.

{
    int i, v;
    DiffVarCounter = 0;
    // check whether the output parts of the cubes are different
 
    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
        if ( pC1->pCubeDataOut[i] != pC2->pCubeDataOut[i] )
        { // they are different
            pDiffVars[0] = -1;
            DiffVarCounter = 1;
            break;
        }
 
    for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
    {
 
        Temp1 = pC1->pCubeDataIn[i] ^ pC2->pCubeDataIn[i];
        Temp2 = (Temp1|(Temp1>>1)) & DIFFERENT;
 
        // check the first part of this word
        Temp = Temp2 & 0xffff;
        cVars = BitCount[ Temp ];
        if ( cVars )
        {
            if ( cVars < 5 )
                for ( v = 0; v < cVars; v++ )
                {
                    assert( BitGroupNumbers[Temp] != MARKNUMBER );
                    pDiffVars[ DiffVarCounter++ ] = i*16 + GroupLiterals[ BitGroupNumbers[Temp] ][v];
                }
            else
                return 5;
        }
        if ( DiffVarCounter > 4 )
            return 5;
 
        // check the second part of this word
        Temp = Temp2 >> 16;
        cVars = BitCount[ Temp ];
        if ( cVars )
        {
            if ( cVars < 5 )
                for ( v = 0; v < cVars; v++ )
                {
                    assert( BitGroupNumbers[Temp] != MARKNUMBER );
                    pDiffVars[ DiffVarCounter++ ] = i*16 + 8 + GroupLiterals[ BitGroupNumbers[Temp] ][v];
                }
            else
                return 5;
        }
        if ( DiffVarCounter > 4 )
            return 5;
    }
    return DiffVarCounter;
}

Here is the caller graph for this function:

GetDistance()

int GetDistance	(	Cube *	pC1,
		Cube *	pC2 )

FUNCTIONS OF THIS MODULE ///.

EXTERNAL FUNCTIONS ///.

Definition at line 214 of file exorBits.c.

{
    int i;
    DiffVarCounter = 0;
 
    for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
    {
        Temp1 = pC1->pCubeDataIn[i] ^ pC2->pCubeDataIn[i];
        Temp2 = (Temp1|(Temp1>>1)) & DIFFERENT;
 
        // count how many bits are one in this var difference
        DiffVarCounter  += BIT_COUNT(Temp2);
        if ( DiffVarCounter > 4 )
            return 5;
    }
    // check whether the output parts are different
    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
        if ( pC1->pCubeDataOut[i] ^ pC2->pCubeDataOut[i] )
        {
            DiffVarCounter++;
            break;
        }
    return DiffVarCounter;
}

GetDistancePlus()

int GetDistancePlus	(	Cube *	pC1,
		Cube *	pC2 )

Definition at line 246 of file exorBits.c.

{
    int i;
 
    DiffVarCounter = 0;
    LastNonZeroWordNum = -1;
    for ( i = 0; i < g_CoverInfo.nWordsIn; i++ )
    {
        Temp1 = pC1->pCubeDataIn[i] ^ pC2->pCubeDataIn[i];
        Temp2 = (Temp1|(Temp1>>1)) & DIFFERENT;
 
        // save the value of var difference, in case 
        // the distance is one and we need to return the var number
        if ( Temp2 )
        {
            LastNonZeroWordNum = i;
            LastNonZeroWord = Temp2;
        }
 
        // count how many bits are one in this var difference
        DiffVarCounter  += BIT_COUNT(Temp2);
        if ( DiffVarCounter > 4 )
            return 5;
    }
    // check whether the output parts are different
    for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
        if ( pC1->pCubeDataOut[i] ^ pC2->pCubeDataOut[i] )
        {
            DiffVarCounter++;
            break;
        }
 
    if ( DiffVarCounter == 1 )
    {
        if ( LastNonZeroWordNum == -1 ) // the output is the only different variable
            s_DiffVarNum = -1;
        else
        {
            Temp = (LastNonZeroWord>>2);
            for ( i = 0; Temp; Temp>>=2, i++ );
            s_DiffVarNum = LastNonZeroWordNum*BPI/2 + i;
 
            // save the old var value
            s_DiffVarValueP_old = GetVar( pC1, s_DiffVarNum );
            s_DiffVarValueQ = GetVar( pC2, s_DiffVarNum );
 
            // EXOR this value with the corresponding value in p cube           
            ExorVar( pC1, s_DiffVarNum, (varvalue)s_DiffVarValueQ );
 
            s_DiffVarValueP_new = GetVar( pC1, s_DiffVarNum );
        }
    }
 
    return DiffVarCounter;
}

Here is the call graph for this function:

Here is the caller graph for this function:

GetVar()

varvalue GetVar	(	Cube *	pC,
		int	Var )

INLINE FUNCTION DEFINITIONS ///.

Definition at line 188 of file exorBits.c.

{
    int Bit = (Var<<1);
    int Value = ((pC->pCubeDataIn[VarWord(Bit)] >> VarBit(Bit)) & 3);
    assert( Value == VAR_NEG || Value == VAR_POS || Value == VAR_ABS );
    return (varvalue)Value;
}

Here is the caller graph for this function:

InsertVars()

void InsertVars	(	Cube *	pC,
		int *	pVars,
		int	nVarsIn,
		int *	pVarValues )

Definition at line 365 of file exorBits.c.

{
    int GlobalBit;
    int LocalWord;
    int LocalBit;
    int i;
    assert( nVarsIn > 0 && nVarsIn <= g_CoverInfo.nVarsIn );
    for ( i = 0; i < nVarsIn; i++ )
    {
        assert( pVars[i] >= 0 && pVars[i] < g_CoverInfo.nVarsIn );
        assert( pVarValues[i] == VAR_NEG || pVarValues[i] == VAR_POS || pVarValues[i] == VAR_ABS );
        GlobalBit = (pVars[i]<<1);
        LocalWord = VarWord(GlobalBit);
        LocalBit  = VarBit(GlobalBit);
 
        // correct this variables
        pC->pCubeDataIn[LocalWord] = ((pC->pCubeDataIn[LocalWord]&(~(3<<LocalBit)))|(pVarValues[i]<<LocalBit));
    }
}

InsertVarsWithoutClearing()

void InsertVarsWithoutClearing	(	Cube *	pC,
		int *	pVars,
		int	nVarsIn,
		int *	pVarValues,
		int	Output )

Definition at line 388 of file exorBits.c.

{
    int GlobalBit;
    int LocalWord;
    int LocalBit;
    int i;
    assert( nVarsIn > 0 && nVarsIn <= g_CoverInfo.nVarsIn );
    for ( i = 0; i < nVarsIn; i++ )
    {
        assert( pVars[i] >= 0 && pVars[i] < g_CoverInfo.nVarsIn );
        assert( pVarValues[i] == VAR_NEG || pVarValues[i] == VAR_POS || pVarValues[i] == VAR_ABS );
        GlobalBit = (pVars[i]<<1);
        LocalWord = VarWord(GlobalBit);
        LocalBit  = VarBit(GlobalBit);
 
        // correct this variables
        pC->pCubeDataIn[LocalWord] |= ( pVarValues[i] << LocalBit );
    }
    // insert the output bit
    pC->pCubeDataOut[VarWord(Output)] |= ( 1 << VarBit(Output) );
}

Here is the caller graph for this function:

PrepareBitSetModule()

void PrepareBitSetModule

(

)

FUNCTION DEFINITIONS ///.

Definition at line 144 of file exorBits.c.

{   
    // prepare bit count
    int i, k;
    int nLimit;
    
    nLimit = FULL16BITS;
    for ( i = 0; i < nLimit; i++ )
    {
        BitCount[i] = __builtin_popcount( i & 0xffff );
        BitGroupNumbers[i] = MARKNUMBER;
    }
    // prepare bit groups
    for ( k = 0; k < 163; k++ )
        BitGroupNumbers[ SparseNumbers[k] ] = k;
/*
    // verify bit groups
    int n = 4368;
    char Buff[100];
    cout << "The number is " << n << endl;
    cout << "The binary is " << itoa(n,Buff,2) << endl;
    cout << "BitGroupNumbers[n] is " << (int)BitGroupNumbers[n] << endl;
    cout << "The group literals are ";
    for ( int g = 0; g < 4; g++ )
        cout << " " << (int)GroupLiterals[BitGroupNumbers[n]][g];
*/
}

Here is the caller graph for this function:

Variable Documentation

BitCount

unsigned char BitCount[FULL16BITS]

Definition at line 138 of file exorBits.c.

g_CoverInfo

ABC_NAMESPACE_IMPL_START cinfo g_CoverInfo

extern

MACRO DEFINITIONS ///.

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

FileName [exorBits.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Exclusive sum-of-product minimization.]

Synopsis [Bit-level procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

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

                                                            ///
        EXOR-Oriented Bit String Manipulation               ///
                                                            ///

Ver. 1.0. Started - July 18, 2000. Last update - July 20, 2000 /// Ver. 1.4. Started - Aug 10, 2000. Last update - Aug 10, 2000 /// ///

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

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.

s_DiffVarNum

int s_DiffVarNum

extern

Definition at line 638 of file exorList.c.

s_DiffVarValueP_new

int s_DiffVarValueP_new

extern

Definition at line 640 of file exorList.c.

s_DiffVarValueP_old

int s_DiffVarValueP_old

extern

Definition at line 639 of file exorList.c.

s_DiffVarValueQ

int s_DiffVarValueQ

extern

Definition at line 641 of file exorList.c.