exor.h File Reference

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
#include "misc/vec/vec.h"
#include "misc/vec/vecWec.h"

Include dependency graph for exor.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	cinfo_tag
struct	cube

Typedefs
typedef struct cinfo_tag	cinfo
typedef unsigned int	drow
typedef unsigned char	byte
typedef struct cube	Cube

Enumerations
enum	{   BPI = 32 , BPIMASK = 31 , LOGBPI = 5 , MAXVARS = 1000 ,   ADDITIONAL_CUBES = 33 , CUBE_PAIR_FACTOR = 20 , DIFFERENT = 0x55555555 }
	MACRO DEFINITIONS ///. More...
enum	type { MULTI_OUTPUT = 1 , SINGLE_NODE , MULTI_NODE }
	CUBE COVER and CUBE typedefs ///. More...
enum	varvalue { VAR_NEG = 1 , VAR_POS , VAR_ABS }
	VARVALUE and CUBEDIST enum typedefs ///. More...
enum	cubedist { DIST2 , DIST3 , DIST4 }

Functions
void	PrepareBitSetModule ()
	FUNCTION DEFINITIONS ///.
int	WriteResultIntoFile (char *pFileName)
int	IterativelyApplyExorLink2 (char fDistEnable)
	FUNCTIONS OF THIS MODULE ///.
int	IterativelyApplyExorLink3 (char fDistEnable)
int	IterativelyApplyExorLink4 (char fDistEnable)
int	AllocateCubeSets (int nVarsIn, int nVarsOut)
	CUBE SET MANIPULATION PROCEDURES ///.
void	DelocateCubeSets ()
int	AllocateQueques (int nPlaces)
void	DelocateQueques ()
int	AllocateCover (int nCubes, int nWordsIn, int nWordsOut)
	CUBE COVER MEMORY MANAGEMENT //.
void	DelocateCover ()
void	AddToFreeCubes (Cube *pC)
	FREE CUBE LIST MANIPULATION FUNCTIONS ///.
Cube *	GetFreeCube ()
void	InsertVarsWithoutClearing (Cube *pC, int *pVars, int nVarsIn, int *pVarValues, int Output)
int	CheckForCloseCubes (Cube *p, int fAddCube)
int	FindDiffVars (int *pDiffVars, Cube *pC1, Cube *pC2)
int	ComputeQCost (Vec_Int_t *vCube)
int	ComputeQCostBits (Cube *p)
int	CountLiterals ()
	FUNCTION DECLARATIONS ///.
int	CountQCost ()

Variables
unsigned char	BitCount []

Typedef Documentation

byte

typedef unsigned char byte

Definition at line 121 of file exor.h.

cinfo

typedef struct cinfo_tag cinfo

Cube

typedef struct cube Cube

drow

typedef unsigned int drow

Definition at line 120 of file exor.h.

Enumeration Type Documentation

anonymous enum

anonymous enum

MACRO DEFINITIONS ///.

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

FileName [exor.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Exclusive sum-of-product minimization.]

Synopsis [Internal declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

exor.h,v 1.0 2005/06/20 00:00:00 alanmi Exp

]

                                                            ///
              Interface of EXORCISM - 4                     ///
        An Exclusive Sum-of-Product Minimizer               ///
         Alan Mishchenko  <alanmi@ee.pdx.edu>               ///
                                                            ///

                                                            ///
                   Main Module                              ///
                                                            ///

Ver. 1.0. Started - July 15, 2000. Last update - July 20, 2000 /// Ver. 1.4. Started - Aug 10, 2000. Last update - Aug 10, 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/ ///

Enumerator
BPI
BPIMASK
LOGBPI
MAXVARS
ADDITIONAL_CUBES
CUBE_PAIR_FACTOR
DIFFERENT

Definition at line 57 of file exor.h.

     {
  // the number of bits per integer
  BPI = 32,
  BPIMASK = 31,
  LOGBPI = 5,
 
  // the maximum number of input variables
  MAXVARS = 1000,
 
  // the number of cubes that are allocated additionally
  ADDITIONAL_CUBES = 33,
 
  // the factor showing how many cube pairs will be allocated
  CUBE_PAIR_FACTOR = 20,
  // the following number of cube pairs are allocated:
  // nCubesAlloc/CUBE_PAIR_FACTOR
 
  DIFFERENT = 0x55555555,
};

cubedist

enum cubedist

Enumerator
DIST2
DIST3
DIST4

Definition at line 181 of file exor.h.

{ DIST2, DIST3, DIST4 } cubedist;

type

enum type

CUBE COVER and CUBE typedefs ///.

Enumerator
MULTI_OUTPUT
SINGLE_NODE
MULTI_NODE

Definition at line 90 of file exor.h.

{ MULTI_OUTPUT = 1, SINGLE_NODE, MULTI_NODE  } type;

varvalue

enum varvalue

VARVALUE and CUBEDIST enum typedefs ///.

Enumerator
VAR_NEG
VAR_POS
VAR_ABS

Definition at line 178 of file exor.h.

{ VAR_NEG = 1, VAR_POS, VAR_ABS  } varvalue;

Function Documentation

AddToFreeCubes()

void AddToFreeCubes ( Cube * pC )

extern

FREE CUBE LIST MANIPULATION FUNCTIONS ///.

Definition at line 157 of file exorCubes.c.

{
    assert( p );
    assert( p->Prev == NULL ); // the cube should not be in use
    assert( p->Next == NULL );
    assert( p->ID );
 
    p->Next = s_CubesFree;
    s_CubesFree = p;
 
    // set the ID of the cube to 0, 
    // so that cube pair garbage collection could recognize it as different
    p->ID = 0;
 
    g_CoverInfo.nCubesFree++;
}

Here is the caller graph for this function:

AllocateCover()

int AllocateCover ( int nCubes, int nWordsIn, int nWordsOut )

extern

CUBE COVER MEMORY MANAGEMENT //.

CUBE COVER MEMORY MANAGEMENT //.

Definition at line 90 of file exorCubes.c.

{
    int OneCubeSize;
    int OneInputSetSize;
    Cube ** pp;
    int TotalSize;
    int i, k;
 
    // determine the size of one cube WITH storage for bits
    OneCubeSize = sizeof(Cube) + (nWordsIn+nWordsOut)*sizeof(unsigned);
    // determine what is the amount of storage for the input part of the cube 
    OneInputSetSize = nWordsIn*sizeof(unsigned);
 
    // allocate memory for the array of pointers
    pp = (Cube **)ABC_ALLOC( Cube *, nCubes );
    if ( pp == NULL )
        return 0;
 
    // determine the size of the total cube cover
    TotalSize = nCubes*OneCubeSize;
    // allocate and clear memory for the cover in one large piece
    pp[0] = (Cube *)ABC_ALLOC( char, TotalSize );
    if ( pp[0] == NULL )
        return 0;
    memset( pp[0], 0, (size_t)TotalSize );
 
    // assign pointers to cubes and bit strings inside this piece
    pp[0]->pCubeDataIn  = (unsigned*)(pp[0] + 1);
    pp[0]->pCubeDataOut = (unsigned*)((char*)pp[0]->pCubeDataIn + OneInputSetSize);
    for ( i = 1; i < nCubes; i++ )
    {
        pp[i] = (Cube *)((char*)pp[i-1] + OneCubeSize);
        pp[i]->pCubeDataIn = (unsigned*)(pp[i] + 1);
        pp[i]->pCubeDataOut = (unsigned*)((char*)pp[i]->pCubeDataIn + OneInputSetSize);
    }
 
    // connect the cubes into the list using Next pointers
    for ( k = 0; k < nCubes-1; k++ )
        pp[k]->Next = pp[k+1];
    // the last pointer is already set to NULL
 
    // assign the head of the free list
    s_CubesFree = pp[0];
    // set the counters of the used and free cubes
    g_CoverInfo.nCubesInUse = 0;
    g_CoverInfo.nCubesFree = nCubes;
 
    // save the pointer to the allocated memory
    s_pCoverMemory = pp;
 
    assert ( g_CoverInfo.nCubesInUse + g_CoverInfo.nCubesFree == g_CoverInfo.nCubesAlloc );
 
    return nCubes*sizeof(Cube *) + TotalSize;
}

Here is the call graph for this function:

Here is the caller graph for this function:

AllocateCubeSets()

int AllocateCubeSets ( int nVarsIn, int nVarsOut )

extern

CUBE SET MANIPULATION PROCEDURES ///.

Memory Allocation/Delocation ///

Definition at line 792 of file exorList.c.

{
    s_List = NULL;
 
    // clean other data
    s_fDistEnable2 = 1;
    s_fDistEnable3 = 0;
    s_fDistEnable4 = 0;
    memset( s_CubeGroup, 0, sizeof(void *) * 5 );
    memset( s_fInserted, 0, sizeof(int) * 5 );
    s_fDecreaseLiterals = 0;
    s_cEnquequed = 0;
    s_cAttempts = 0;
    s_cReshapes = 0;
    s_nCubesBefore = 0;
    s_Gain = 0;
    s_GainTotal = 0;
    s_GroupCounter = 0;
    s_GroupBest = 0;
    s_pC1 = s_pC2 = NULL;
 
    return 4;
}

Here is the call graph for this function:

Here is the caller graph for this function:

AllocateQueques()

int AllocateQueques ( int nPlaces )

extern

Definition at line 1112 of file exorList.c.

{
    int i;
    s_nPosAlloc  = nPlaces;
 
    for ( i = 0; i < 3; i++ )
    {
        // clean data
        memset( &s_Que[i], 0, sizeof(que) );
 
        s_Que[i].pC1 = (Cube**) ABC_ALLOC( Cube*, nPlaces );
        s_Que[i].pC2 = (Cube**) ABC_ALLOC( Cube*, nPlaces );
        s_Que[i].ID1 = (byte*) ABC_ALLOC( byte, nPlaces );
        s_Que[i].ID2 = (byte*) ABC_ALLOC( byte, nPlaces );
 
        if ( s_Que[i].pC1==NULL || s_Que[i].pC2==NULL || s_Que[i].ID1==NULL || s_Que[i].ID2==NULL )
            return 0;
 
        s_nPosMax[i] = 0;
        s_Que[i].fEmpty = 1;
    }
 
    return nPlaces * (sizeof(Cube*) + sizeof(Cube*) + 2*sizeof(byte) );
}

Here is the call graph for this function:

Here is the caller graph for this function:

CheckForCloseCubes()

int CheckForCloseCubes ( Cube * p, int fAddCube )

extern

Definition at line 643 of file exorList.c.

{
    // start the new range
    NewRangeReset();
 
    for ( s_q = s_List; s_q; s_q = s_q->Next )
    {
        s_Distance = GetDistancePlus( p, s_q );
        if ( s_Distance > 4 )
        {
        }
        else if ( s_Distance == 4 )
        {
            if ( s_fDistEnable4 ) 
                NewRangeInsertCubePair( DIST4, p, s_q );
        }
        else if ( s_Distance == 3 )
        {
            if ( s_fDistEnable3 ) 
                NewRangeInsertCubePair( DIST3, p, s_q );
        }
        else if ( s_Distance == 2 )
        { 
            if ( s_fDistEnable2 ) 
                NewRangeInsertCubePair( DIST2, p, s_q );
        }
        else if ( s_Distance == 1 )
        {   // extract the cube from the data structure

            // store the changes
            s_ChangeStore.fInput = (s_DiffVarNum != -1);
            s_ChangeStore.p      = p;
            s_ChangeStore.PrevQa = s_q->a;
            s_ChangeStore.PrevPa = p->a;
            s_ChangeStore.PrevQq = s_q->q;
            s_ChangeStore.PrevPq = p->q;
            s_ChangeStore.PrevPz = p->z;
            s_ChangeStore.Var    = s_DiffVarNum;
            s_ChangeStore.Value  = s_DiffVarValueQ;
            s_ChangeStore.PrevID = s_q->ID;
 
            CubeExtract( s_q );
            // perform the EXOR of the two cubes and write the result into p
 
            // it is important that the resultant cube is written into p!!!
 
            if ( s_DiffVarNum == -1 )
            {
                int i;
                // exor the output part
                p->z = 0;
                for ( i = 0; i < g_CoverInfo.nWordsOut; i++ )
                {
                    p->pCubeDataOut[i] ^= s_q->pCubeDataOut[i];
                    p->z += BIT_COUNT(p->pCubeDataOut[i]);
                }
            }
            else
            {
                // the cube has already been updated by GetDistancePlus()
 
                // modify the parameters of the number of literals in the new cube
//              p->a += s_UpdateLiterals[ s_DiffVarValueP ][ s_DiffVarValueQ ];
                if ( s_DiffVarValueP_old == VAR_NEG || s_DiffVarValueP_old == VAR_POS )
                    p->a--;
                if ( s_DiffVarValueP_new == VAR_NEG || s_DiffVarValueP_new == VAR_POS )
                    p->a++;
                p->q = ComputeQCostBits(p);
            }
 
            // move q to the free cube list
            AddToFreeCubes( s_q );
 
            // make sure that nobody with use the pairs created so far
//          NewRangeReset();
            // call the function again for the new cube
            return 1 + CheckForCloseCubes( p, 1 );
        }
        else // if ( Distance == 0 )
        {   // extract the second cube from the data structure and add them both to the free list
            AddToFreeCubes( p );
            AddToFreeCubes( CubeExtract( s_q ) );
 
            // make sure that nobody with use the pairs created so far
            NewRangeReset();
            return 2;
        }
    }
    
    // add the cube to the data structure if needed
    if ( fAddCube )
        CubeInsert( p );
 
    // add temporarily stored new range of cube pairs to the queque
    NewRangeAdd();
 
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeQCost()

int ComputeQCost ( Vec_Int_t * vCube )

extern

Definition at line 132 of file exor.c.

{
    int i, Entry, nLitsN = 0;
    Vec_IntForEachEntry( vCube, Entry, i )
        nLitsN += Abc_LitIsCompl(Entry);
    return GetQCost( Vec_IntSize(vCube), nLitsN );
}

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeQCostBits()

int ComputeQCostBits ( Cube * p )

extern

Definition at line 139 of file exor.c.

{
    extern varvalue GetVar( Cube* pC, int Var );
    int v, nLits = 0, nLitsN = 0;
    for ( v = 0; v < g_CoverInfo.nVarsIn; v++ )
    {
        int Value = GetVar( p, v );
        if ( Value == VAR_NEG )
            nLitsN++;
        else if ( Value == VAR_POS )
            nLits++;
    }
    nLits += nLitsN;
    return GetQCost( nLits, nLitsN );
}

Here is the call graph for this function:

Here is the caller graph for this function:

CountLiterals()

int CountLiterals ( )

extern

FUNCTION DECLARATIONS ///.

Definition at line 77 of file exorUtil.c.

{
    Cube* p;
    int LitCounter = 0;
    for ( p = IterCubeSetStart( ); p; p = IterCubeSetNext() )
        LitCounter += p->a;
    return LitCounter;
}

Here is the call graph for this function:

Here is the caller graph for this function:

CountQCost()

int CountQCost ( )

extern

Definition at line 119 of file exorUtil.c.

{
    Cube* p;
    int QCost = 0;
    int QCostControl = 0;
    for ( p = IterCubeSetStart( ); p; p = IterCubeSetNext() )
    {
        QCostControl += p->q;
        QCost += ComputeQCostBits( p );
    }
//    if ( QCostControl != QCost )
//        printf( "Warning! The recorded number of literals (%d) differs from the actual number (%d)\n", QCostControl, QCost );
    return QCost;
}

Here is the call graph for this function:

Here is the caller graph for this function:

DelocateCover()

void DelocateCover ( )

extern

Definition at line 147 of file exorCubes.c.

{
    ABC_FREE( s_pCoverMemory[0] );
    ABC_FREE( s_pCoverMemory );
}

Here is the caller graph for this function:

DelocateCubeSets()

void DelocateCubeSets ( )

extern

Definition at line 816 of file exorList.c.

{
}

Here is the caller graph for this function:

DelocateQueques()

void DelocateQueques ( )

extern

Definition at line 1139 of file exorList.c.

{
    int i;
    for ( i = 0; i < 3; i++ )
    {
        ABC_FREE( s_Que[i].pC1 );
        ABC_FREE( s_Que[i].pC2 );
        ABC_FREE( s_Que[i].ID1 );
        ABC_FREE( s_Que[i].ID2 );
    }
}

Here is the caller graph for this function:

FindDiffVars()

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

extern

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:

GetFreeCube()

Cube * GetFreeCube ( )

extern

Definition at line 174 of file exorCubes.c.

{
    Cube * p;
    assert( s_CubesFree );
    p = s_CubesFree;
    s_CubesFree = s_CubesFree->Next;
    p->Next = NULL;
    g_CoverInfo.nCubesFree--;
    return p;
}

Here is the caller graph for this function:

InsertVarsWithoutClearing()

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

extern

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:

IterativelyApplyExorLink2()

int IterativelyApplyExorLink2 ( char fDistEnable )

extern

FUNCTIONS OF THIS MODULE ///.

Definition at line 277 of file exorList.c.

{
    int z;
 
    // this var is specific to ExorLink-2
    s_Dist = (cubedist)0;
 
    // enable pair accumulation
    s_fDistEnable2 = fDistEnable & 1;
    s_fDistEnable3 = fDistEnable & 2;
    s_fDistEnable4 = fDistEnable & 4;
 
    // initialize counters
    s_cEnquequed = GetQuequeStats( s_Dist );
    s_cAttempts  = 0;
    s_cReshapes  = 0;
 
    // remember the number of cubes before minimization
    s_nCubesBefore = g_CoverInfo.nCubesInUse;
 
    for ( z = IteratorCubePairStart( s_Dist, &s_pC1, &s_pC2 ); z; z = IteratorCubePairNext() )
    {
        s_cAttempts++;
        // start ExorLink of the given Distance
        if ( ExorLinkCubeIteratorStart( s_CubeGroup, s_pC1, s_pC2, s_Dist ) )
        {
            // extract old cubes from storage (to prevent EXORing with their derivitives)
            CubeExtract( s_pC1 );
            CubeExtract( s_pC2 );
 
            // mark the current position in the cube pair queques
            MarkSet();
 
            // check the first group (generated by ExorLinkCubeIteratorStart())
            if ( CheckForCloseCubes( s_CubeGroup[0], 0 ) ) 
            {  // the first cube leads to improvement - it is already inserted
                CheckForCloseCubes( s_CubeGroup[1], 1 ); // insert the second cube
                goto SUCCESS;
            }
            if ( CheckForCloseCubes( s_CubeGroup[1], 0 ) ) 
            {  // the second cube leads to improvement - it is already inserted
                CheckForCloseCubes( s_CubeGroup[0], 1 ); // insert the first cube
//              CheckAndInsert( s_CubeGroup[0] );
                goto SUCCESS;
            }
            // the first group does not lead to improvement
 
            // rewind to the previously marked position in the cube pair queques
            MarkRewind();
 
            // generate the second group
            ExorLinkCubeIteratorNext( s_CubeGroup );
 
            // check the second group
            if ( CheckForCloseCubes( s_CubeGroup[0], 0 ) ) 
            { // the first cube leads to improvement - it is already inserted
                CheckForCloseCubes( s_CubeGroup[1], 1 ); // insert the second cube
                goto SUCCESS;
            }
            if ( CheckForCloseCubes( s_CubeGroup[1], 0 ) ) 
            { // the second cube leads to improvement - it is already inserted
                CheckForCloseCubes( s_CubeGroup[0], 1 ); // insert the first cube
//              CheckAndInsert( s_CubeGroup[0] );
                goto SUCCESS;
            }
            // the second group does not lead to improvement
 
            // decide whether to accept the second group, depending on literals
            if ( s_fDecreaseLiterals )
            {
                if ( g_CoverInfo.fUseQCost ? 
                     s_CubeGroup[0]->q + s_CubeGroup[1]->q >= s_pC1->q + s_pC2->q :
                     s_CubeGroup[0]->a + s_CubeGroup[1]->a >= s_pC1->a + s_pC2->a ) 
                // the group increases literals
                { // do not take the last group
                            
                    // rewind to the previously marked position in the cube pair queques
                    MarkRewind();
 
                    // return the old cubes back to storage
                    CubeInsert( s_pC1 );
                    CubeInsert( s_pC2 );
                    // clean the results of generating ExorLinked cubes
                    ExorLinkCubeIteratorCleanUp( 0 );
                    continue;
                }
            }
 
            // take the last group
            // there is no need to test these cubes again,
            // because they have been tested and did not yield any improvement
            CubeInsert( s_CubeGroup[0] );
            CubeInsert( s_CubeGroup[1] );
//          CheckForCloseCubes( s_CubeGroup[0], 1 ); 
//          CheckForCloseCubes( s_CubeGroup[1], 1 ); 
 
SUCCESS:
            // clean the results of generating ExorLinked cubes
            ExorLinkCubeIteratorCleanUp( 1 ); // take the last group
            // free old cubes
            AddToFreeCubes( s_pC1 );
            AddToFreeCubes( s_pC2 );
            // increate the counter
            s_cReshapes++;
        }
    }
    // print the report
    if ( g_CoverInfo.Verbosity == 2 )
    {
    printf( "ExLink-%d", 2 );
    printf( ": Que= %5d", s_cEnquequed );
    printf( "  Att= %4d", s_cAttempts );
    printf( "  Resh= %4d", s_cReshapes );
    printf( "  NoResh= %4d", s_cAttempts - s_cReshapes );
    printf( "  Cubes= %3d", g_CoverInfo.nCubesInUse );
    printf( "  (%d)", s_nCubesBefore - g_CoverInfo.nCubesInUse );
    printf( "  Lits= %5d", CountLiterals() );
    printf( "  QCost = %6d", CountQCost() );
    printf( "\n" );
    }
 
    // return the number of cubes gained in the process
    return s_nCubesBefore - g_CoverInfo.nCubesInUse;
}

Here is the call graph for this function:

Here is the caller graph for this function:

IterativelyApplyExorLink3()

int IterativelyApplyExorLink3 ( char fDistEnable )

extern

Definition at line 405 of file exorList.c.

{
    int z, c, d;
    // this var is specific to ExorLink-3
    s_Dist = (cubedist)1;
 
    // enable pair accumulation
    s_fDistEnable2 = fDistEnable & 1;
    s_fDistEnable3 = fDistEnable & 2;
    s_fDistEnable4 = fDistEnable & 4;
 
    // initialize counters
    s_cEnquequed = GetQuequeStats( s_Dist );
    s_cAttempts  = 0;
    s_cReshapes  = 0;
 
    // remember the number of cubes before minimization
    s_nCubesBefore = g_CoverInfo.nCubesInUse;
 
    for ( z = IteratorCubePairStart( s_Dist, &s_pC1, &s_pC2 ); z; z = IteratorCubePairNext() )
    {
        s_cAttempts++;
        // start ExorLink of the given Distance
        if ( ExorLinkCubeIteratorStart( s_CubeGroup, s_pC1, s_pC2, s_Dist ) )
        {
            // extract old cubes from storage (to prevent EXORing with their derivitives)
            CubeExtract( s_pC1 );
            CubeExtract( s_pC2 );
 
            // mark the current position in the cube pair queques
            MarkSet();
 
            // check cube groups one by one
            s_GroupCounter = 0;
            do  
            {   // check the cubes of this group one by one
                for ( c = 0; c < 3; c++ )
                if ( !s_CubeGroup[c]->fMark ) // this cube has not yet been checked
                {
                    s_Gain = CheckForCloseCubes( s_CubeGroup[c], 0 ); // do not insert the cube, by default
                    if ( s_Gain ) 
                    { // this cube leads to improvement or reshaping - it is already inserted
 
                        // decide whether to accept this group based on literal count
                        if ( s_fDecreaseLiterals && s_Gain == 1 )
                        if ( g_CoverInfo.fUseQCost ?
                             s_CubeGroup[0]->q + s_CubeGroup[1]->q + s_CubeGroup[2]->q > s_pC1->q + s_pC2->q + s_ChangeStore.PrevQq :
                             s_CubeGroup[0]->a + s_CubeGroup[1]->a + s_CubeGroup[2]->a > s_pC1->a + s_pC2->a + s_ChangeStore.PrevQa 
                           ) // the group increases literals
                        { // do not take this group
                            // remember the group
                            s_GroupBest = s_GroupCounter;
                            // undo changes to be able to continue checking other groups
                            UndoRecentChanges();
                            break;
                        }
 
                        // take this group
                        for ( d = 0; d < 3; d++ ) // insert other cubes
                            if ( d != c )
                            {
                                CheckForCloseCubes( s_CubeGroup[d], 1 ); 
//                              if ( s_CubeGroup[d]->fMark )
//                                  CheckAndInsert( s_CubeGroup[d] );
//                                  CheckOnlyOneCube( s_CubeGroup[d] );
//                                  CheckForCloseCubes( s_CubeGroup[d], 1 ); 
//                              else
//                                  CheckForCloseCubes( s_CubeGroup[d], 1 ); 
                            }
 
                        // clean the results of generating ExorLinked cubes
                        ExorLinkCubeIteratorCleanUp( 1 ); // take the last group
                        // free old cubes
                        AddToFreeCubes( s_pC1 );
                        AddToFreeCubes( s_pC2 );
                        // update the counter
                        s_cReshapes++;
                        goto END_OF_LOOP;
                    }
                    else // mark the cube as checked
                        s_CubeGroup[c]->fMark = 1;
                }
                // the group is not taken - find the new group
                s_GroupCounter++;
                                        
                // rewind to the previously marked position in the cube pair queques
                MarkRewind();
            } 
            while ( ExorLinkCubeIteratorNext( s_CubeGroup ) );
            // none of the groups leads to improvement
 
            // return the old cubes back to storage
            CubeInsert( s_pC1 );
            CubeInsert( s_pC2 );
            // clean the results of generating ExorLinked cubes
            ExorLinkCubeIteratorCleanUp( 0 );
        }
END_OF_LOOP: {}
    }
 
    // print the report
    if ( g_CoverInfo.Verbosity == 2 )
    {
    printf( "ExLink-%d", 3 );
    printf( ": Que= %5d", s_cEnquequed );
    printf( "  Att= %4d", s_cAttempts );
    printf( "  Resh= %4d", s_cReshapes );
    printf( "  NoResh= %4d", s_cAttempts - s_cReshapes );
    printf( "  Cubes= %3d", g_CoverInfo.nCubesInUse );
    printf( "  (%d)", s_nCubesBefore - g_CoverInfo.nCubesInUse );
    printf( "  Lits= %5d", CountLiterals() );
    printf( "  QCost = %6d", CountQCost() );
    printf( "\n" );
    }
 
    // return the number of cubes gained in the process
    return s_nCubesBefore - g_CoverInfo.nCubesInUse;
}

Here is the call graph for this function:

Here is the caller graph for this function:

IterativelyApplyExorLink4()

int IterativelyApplyExorLink4 ( char fDistEnable )

extern

Definition at line 524 of file exorList.c.

{
    int z, c;
    // this var is specific to ExorLink-4
    s_Dist = (cubedist)2;
 
    // enable pair accumulation
    s_fDistEnable2 = fDistEnable & 1;
    s_fDistEnable3 = fDistEnable & 2;
    s_fDistEnable4 = fDistEnable & 4;
 
    // initialize counters
    s_cEnquequed = GetQuequeStats( s_Dist );
    s_cAttempts  = 0;
    s_cReshapes  = 0;
 
    // remember the number of cubes before minimization
    s_nCubesBefore = g_CoverInfo.nCubesInUse;
 
    for ( z = IteratorCubePairStart( s_Dist, &s_pC1, &s_pC2 ); z; z = IteratorCubePairNext() )
    {
        s_cAttempts++;
        // start ExorLink of the given Distance
        if ( ExorLinkCubeIteratorStart( s_CubeGroup, s_pC1, s_pC2, s_Dist ) )
        {
            // extract old cubes from storage (to prevent EXORing with their derivitives)
            CubeExtract( s_pC1 );
            CubeExtract( s_pC2 );
 
            // mark the current position in the cube pair queques
            MarkSet();
 
            // check cube groups one by one
            do  
            {   // check the cubes of this group one by one
                s_GainTotal = 0;
                for ( c = 0; c < 4; c++ )
                if ( !s_CubeGroup[c]->fMark ) // this cube has not yet been checked
                {
                    s_Gain = CheckForCloseCubes( s_CubeGroup[c], 0 ); // do not insert the cube, by default
                    // if the cube leads to gain, it is already inserted
                    s_fInserted[c] = (int)(s_Gain>0);
                    // increment the total gain
                    s_GainTotal += s_Gain;
                }
                else
                    s_fInserted[c] = 0; // the cube has already been checked - it is not inserted
 
                if ( s_GainTotal == 0 ) // the group does not lead to any gain
                { // mark the cubes
                    for ( c = 0; c < 4; c++ )
                        s_CubeGroup[c]->fMark = 1;
                }
                else if ( s_GainTotal == 1 ) // the group does not lead to substantial gain, too
                { 
                    // undo changes to be able to continue checking groups
                    UndoRecentChanges();
                    // mark those cubes that were not inserted
                    for ( c = 0; c < 4; c++ )
                        s_CubeGroup[c]->fMark = !s_fInserted[c];
                }
                else // if ( s_GainTotal > 1 ) // the group reshapes or improves
                { // accept the group
                    for ( c = 0; c < 4; c++ ) // insert other cubes
                        if ( !s_fInserted[c] )
                            CheckForCloseCubes( s_CubeGroup[c], 1 ); 
//                          CheckAndInsert( s_CubeGroup[c] );
                    // clean the results of generating ExorLinked cubes
                    ExorLinkCubeIteratorCleanUp( 1 ); // take the last group
                    // free old cubes
                    AddToFreeCubes( s_pC1 );
                    AddToFreeCubes( s_pC2 );
                    // update the counter
                    s_cReshapes++;
                    goto END_OF_LOOP;
                }
                                        
                // rewind to the previously marked position in the cube pair queques
                MarkRewind();
            } 
            while ( ExorLinkCubeIteratorNext( s_CubeGroup ) );
            // none of the groups leads to improvement
 
            // return the old cubes back to storage
            CubeInsert( s_pC1 );
            CubeInsert( s_pC2 );
            // clean the results of generating ExorLinked cubes
            ExorLinkCubeIteratorCleanUp( 0 );
        }
END_OF_LOOP: {}
    }
 
    // print the report
    if ( g_CoverInfo.Verbosity == 2 )
    {
    printf( "ExLink-%d", 4 );
    printf( ": Que= %5d", s_cEnquequed );
    printf( "  Att= %4d", s_cAttempts );
    printf( "  Resh= %4d", s_cReshapes );
    printf( "  NoResh= %4d", s_cAttempts - s_cReshapes );
    printf( "  Cubes= %3d", g_CoverInfo.nCubesInUse );
    printf( "  (%d)", s_nCubesBefore - g_CoverInfo.nCubesInUse );
    printf( "  Lits= %5d", CountLiterals() );
    printf( "  QCost = %6d", CountQCost() );
    printf( "\n" );
    }
 
    // return the number of cubes gained in the process
    return s_nCubesBefore - g_CoverInfo.nCubesInUse;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PrepareBitSetModule()

void PrepareBitSetModule ( )

extern

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:

WriteResultIntoFile()

int WriteResultIntoFile ( char * pFileName )

extern

Definition at line 182 of file exorUtil.c.

{
    FILE * pFile;
    time_t ltime;
    char * TimeStr;
 
    pFile = fopen( pFileName, "w" );
    if ( pFile == NULL )
    {
        fprintf( stderr, "\n\nCannot open the output file\n" );
        return 1;
    }
 
    // get current time
    time( &ltime );
    TimeStr = asctime( localtime( &ltime ) );
    // get the number of literals
    g_CoverInfo.nLiteralsAfter = CountLiteralsCheck();
    g_CoverInfo.QCostAfter = CountQCost();
    fprintf( pFile, "# EXORCISM-4 output for command line arguments: " );
    fprintf( pFile, "\"-Q %d -V %d\"\n", g_CoverInfo.Quality, g_CoverInfo.Verbosity );
    fprintf( pFile, "# Minimization performed %s", TimeStr );
    fprintf( pFile, "# Initial statistics: " );
    fprintf( pFile, "Cubes = %d  Literals = %d  QCost = %d\n", g_CoverInfo.nCubesBefore, g_CoverInfo.nLiteralsBefore, g_CoverInfo.QCostBefore );
    fprintf( pFile, "# Final   statistics: " );
    fprintf( pFile, "Cubes = %d  Literals = %d  QCost = %d\n", g_CoverInfo.nCubesInUse, g_CoverInfo.nLiteralsAfter, g_CoverInfo.QCostAfter );
    fprintf( pFile, "# File reading and reordering time = %.2f sec\n", TICKS_TO_SECONDS(g_CoverInfo.TimeRead) );
    fprintf( pFile, "# Starting cover generation time   = %.2f sec\n", TICKS_TO_SECONDS(g_CoverInfo.TimeStart) );
    fprintf( pFile, "# Pure ESOP minimization time      = %.2f sec\n", TICKS_TO_SECONDS(g_CoverInfo.TimeMin) );
    fprintf( pFile, ".i %d\n", g_CoverInfo.nVarsIn );
    fprintf( pFile, ".o %d\n", g_CoverInfo.nVarsOut );
    fprintf( pFile, ".p %d\n", g_CoverInfo.nCubesInUse );
    fprintf( pFile, ".type esop\n" );
    WriteTableIntoFile( pFile );
    fprintf( pFile, ".e\n" );
    fclose( pFile );
    return 0;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

BitCount

unsigned char BitCount[]

extern

Definition at line 138 of file exorBits.c.