From d0e834d1a615f8e0e9d04c2ac97811f63562bd0b Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 6 Aug 2005 08:01:00 -0700 Subject: Version abc50806 --- src/opt/fxu/fxu.c | 260 ++++++++++++++++ src/opt/fxu/fxu.h | 108 +++++++ src/opt/fxu/fxuCreate.c | 425 +++++++++++++++++++++++++ src/opt/fxu/fxuHeapD.c | 445 +++++++++++++++++++++++++++ src/opt/fxu/fxuHeapS.c | 444 +++++++++++++++++++++++++++ src/opt/fxu/fxuInt.h | 541 ++++++++++++++++++++++++++++++++ src/opt/fxu/fxuList.c | 522 +++++++++++++++++++++++++++++++ src/opt/fxu/fxuMatrix.c | 382 +++++++++++++++++++++++ src/opt/fxu/fxuPair.c | 555 +++++++++++++++++++++++++++++++++ src/opt/fxu/fxuPrint.c | 195 ++++++++++++ src/opt/fxu/fxuReduce.c | 194 ++++++++++++ src/opt/fxu/fxuSelect.c | 603 ++++++++++++++++++++++++++++++++++++ src/opt/fxu/fxuSingle.c | 166 ++++++++++ src/opt/fxu/fxuUpdate.c | 802 ++++++++++++++++++++++++++++++++++++++++++++++++ src/opt/fxu/module.make | 12 + 15 files changed, 5654 insertions(+) create mode 100644 src/opt/fxu/fxu.c create mode 100644 src/opt/fxu/fxu.h create mode 100644 src/opt/fxu/fxuCreate.c create mode 100644 src/opt/fxu/fxuHeapD.c create mode 100644 src/opt/fxu/fxuHeapS.c create mode 100644 src/opt/fxu/fxuInt.h create mode 100644 src/opt/fxu/fxuList.c create mode 100644 src/opt/fxu/fxuMatrix.c create mode 100644 src/opt/fxu/fxuPair.c create mode 100644 src/opt/fxu/fxuPrint.c create mode 100644 src/opt/fxu/fxuReduce.c create mode 100644 src/opt/fxu/fxuSelect.c create mode 100644 src/opt/fxu/fxuSingle.c create mode 100644 src/opt/fxu/fxuUpdate.c create mode 100644 src/opt/fxu/module.make (limited to 'src/opt') diff --git a/src/opt/fxu/fxu.c b/src/opt/fxu/fxu.c new file mode 100644 index 00000000..4b95b5a5 --- /dev/null +++ b/src/opt/fxu/fxu.c @@ -0,0 +1,260 @@ +/**CFile**************************************************************** + + FileName [fxu.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [The entrance into the fast extract module.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxu.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" +//#include "mvc.h" +#include "fxu.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +/*===== fxuCreate.c ====================================================*/ +extern Fxu_Matrix * Fxu_CreateMatrix( Fxu_Data_t * pData ); +extern void Fxu_CreateCovers( Fxu_Matrix * p, Fxu_Data_t * pData ); + +static int s_MemoryTotal; +static int s_MemoryPeak; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs fast_extract on a set of covers.] + + Description [All the covers are given in the array p->ppCovers. + The resulting covers are returned in the array p->ppCoversNew. + The number of entries in both cover arrays is equal to the number + of all values in the current nodes plus the max expected number + of extracted nodes (p->nValuesCi + p->nValuesInt + p->nValuesExtMax). + The first p->nValuesCi entries, corresponding to the CI nodes, are NULL. + The next p->nValuesInt entries, corresponding to the int nodes, are covers + from which the divisors are extracted. The last p->nValuesExtMax entries + are reserved for the new covers to be extracted. The number of extracted + covers is returned. This number does not exceed the given number (p->nNodesExt). + Two other things are important for the correct operation of this procedure: + (1) The input covers should be SCC-free. (2) The literal array (pCover->pLits) + is allocated in each cover. The i-th entry in the literal array of a cover + is the number of the cover in the array p->ppCovers, which represents this + literal (variable value) in the given cover.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_FastExtract( Fxu_Data_t * pData ) +{ + Fxu_Matrix * p; + Fxu_Single * pSingle; + Fxu_Double * pDouble; + int Weight1, Weight2, Weight3; + + s_MemoryTotal = 0; + s_MemoryPeak = 0; + + // create the matrix + p = Fxu_CreateMatrix( pData ); + if ( p == NULL ) + return -1; +// if ( pData->fVerbose ) +// printf( "Memory usage after construction: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak ); +//Fxu_MatrixPrint( NULL, p ); + + if ( pData->fOnlyS ) + { + pData->nNodesNew = 0; + do + { + Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle ); + if ( pData->fVerbose ) + printf( "Best single = %3d.\n", Weight1 ); + if ( Weight1 > 0 || Weight1 == 0 && pData->fUse0 ) + Fxu_UpdateSingle( p ); + else + break; + } + while ( ++pData->nNodesNew < pData->nNodesExt ); + } + else if ( pData->fOnlyD ) + { + pData->nNodesNew = 0; + do + { + Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ); + if ( pData->fVerbose ) + printf( "Best double = %3d.\n", Weight2 ); + if ( Weight2 > 0 || Weight2 == 0 && pData->fUse0 ) + Fxu_UpdateDouble( p ); + else + break; + } + while ( ++pData->nNodesNew < pData->nNodesExt ); + } + else if ( !pData->fUseCompl ) + { + pData->nNodesNew = 0; + do + { + Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle ); + Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ); + + if ( pData->fVerbose ) + printf( "Best double = %3d. Best single = %3d.\n", Weight2, Weight1 ); +//Fxu_Select( p, &pSingle, &pDouble ); + + if ( Weight1 >= Weight2 ) + { + if ( Weight1 > 0 || Weight1 == 0 && pData->fUse0 ) + Fxu_UpdateSingle( p ); + else + break; + } + else + { + if ( Weight2 > 0 || Weight2 == 0 && pData->fUse0 ) + Fxu_UpdateDouble( p ); + else + break; + } + } + while ( ++pData->nNodesNew < pData->nNodesExt ); + } + else + { // use the complement + pData->nNodesNew = 0; + do + { + Weight1 = Fxu_HeapSingleReadMaxWeight( p->pHeapSingle ); + Weight2 = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ); + + // select the best single and double + Weight3 = Fxu_Select( p, &pSingle, &pDouble ); + if ( pData->fVerbose ) + printf( "Best double = %3d. Best single = %3d. Best complement = %3d.\n", + Weight2, Weight1, Weight3 ); + + if ( Weight3 > 0 || Weight3 == 0 && pData->fUse0 ) + Fxu_Update( p, pSingle, pDouble ); + else + break; + } + while ( ++pData->nNodesNew < pData->nNodesExt ); + } + + if ( pData->fVerbose ) + printf( "Total single = %3d. Total double = %3d. Total compl = %3d.\n", p->nDivs1, p->nDivs2, p->nDivs3 ); + + // create the new covers + if ( pData->nNodesNew ) + Fxu_CreateCovers( p, pData ); + Fxu_MatrixDelete( p ); +// printf( "Memory usage after delocation: Total = %d. Peak = %d.\n", s_MemoryTotal, s_MemoryPeak ); + if ( pData->nNodesNew == pData->nNodesExt ) + printf( "Warning: The limit on the number of extracted divisors has been reached.\n" ); + return pData->nNodesNew; +} + + +/**Function************************************************************* + + Synopsis [Unmarks the cubes in the ring.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixRingCubesUnmark( Fxu_Matrix * p ) +{ + Fxu_Cube * pCube, * pCube2; + // unmark the cubes + Fxu_MatrixForEachCubeInRingSafe( p, pCube, pCube2 ) + pCube->pOrder = NULL; + Fxu_MatrixRingCubesReset( p ); +} + + +/**Function************************************************************* + + Synopsis [Unmarks the vars in the ring.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixRingVarsUnmark( Fxu_Matrix * p ) +{ + Fxu_Var * pVar, * pVar2; + // unmark the vars + Fxu_MatrixForEachVarInRingSafe( p, pVar, pVar2 ) + pVar->pOrder = NULL; + Fxu_MatrixRingVarsReset( p ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Fxu_MemFetch( Fxu_Matrix * p, int nBytes ) +{ + s_MemoryTotal += nBytes; + if ( s_MemoryPeak < s_MemoryTotal ) + s_MemoryPeak = s_MemoryTotal; +// return malloc( nBytes ); + return Extra_MmFixedEntryFetch( p->pMemMan ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MemRecycle( Fxu_Matrix * p, char * pItem, int nBytes ) +{ + s_MemoryTotal -= nBytes; +// free( pItem ); + Extra_MmFixedEntryRecycle( p->pMemMan, pItem ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxu.h b/src/opt/fxu/fxu.h new file mode 100644 index 00000000..5bc1e75f --- /dev/null +++ b/src/opt/fxu/fxu.h @@ -0,0 +1,108 @@ +/**CFile**************************************************************** + + FileName [fxu.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [External declarations of fast extract for unate covers.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxu.h,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#ifndef __FXU_H__ +#define __FXU_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include "vec.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +#ifndef bool +#define bool int +#endif + +typedef struct FxuDataStruct Fxu_Data_t; + +// structure for the FX input/output data +struct FxuDataStruct +{ + // user specified parameters + bool fOnlyS; // set to 1 to have only single-cube divs + bool fOnlyD; // set to 1 to have only double-cube divs + bool fUse0; // set to 1 to have 0-weight also extracted + bool fUseCompl; // set to 1 to have complement taken into account + bool fVerbose; // set to 1 to have verbose output + int nPairsMax; // the maximum number of cube pairs to consider +/* + // parameters of the network + int fMvNetwork; // the network has some MV nodes + // the information about nodes + int nNodesCi; // the number of CI nodes of the network + int nNodesInt; // the number of internal nodes of the network + int nNodesOld; // the number of CI and int nodes + int nNodesNew; // the number of added nodes + int nNodesExt; // the max number of (binary) nodes to be added by FX + int nNodesAlloc; // the total number of all nodes + int * pNode2Value; // for each node, the number of its first value + // the information about values + int nValuesCi; // the total number of values of CI nodes + int nValuesInt; // the total number of values of int nodes + int nValuesOld; // the number of CI and int values + int nValuesNew; // the number of values added nodes + int nValuesExt; // the total number of values of the added nodes + int nValuesAlloc; // the total number of all values of all nodes + int * pValue2Node; // for each value, the number of its node + // the information about covers + Mvc_Cover_t ** ppCovers; // for each value, the corresponding cover + Mvc_Cover_t ** ppCoversNew; // for each value, the corresponding cover after FX + // the MVC manager + Mvc_Manager_t * pManMvc; +*/ + // statistics + int nNodesOld; // the old number of nodes + int nNodesExt; // the number of divisors to extract + int nNodesNew; // the number of divisors extracted + + // the input information + Vec_Ptr_t * vSops; // the SOPs for each node in the network + Vec_Ptr_t * vFanins; // the fanins of each node in the network + // output information + Vec_Ptr_t * vSopsNew; // the SOPs for each node in the network after extraction + Vec_Ptr_t * vFaninsNew; // the fanins of each node in the network after extraction + // the SOP manager + Extra_MmFlex_t * pManSop; +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*===== fxu.c ==========================================================*/ +extern int Fxu_FastExtract( Fxu_Data_t * pData ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + +#endif + diff --git a/src/opt/fxu/fxuCreate.c b/src/opt/fxu/fxuCreate.c new file mode 100644 index 00000000..04b23fce --- /dev/null +++ b/src/opt/fxu/fxuCreate.c @@ -0,0 +1,425 @@ +/**CFile**************************************************************** + + FileName [fxuCreate.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Create matrix from covers and covers from matrix.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuCreate.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "fxuInt.h" +#include "fxu.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +extern int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax ); + +static void Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube, char * pSopCube, Vec_Fan_t * vFanins, int * pOrder ); +static int Fxu_CreateMatrixLitCompare( int * ptrX, int * ptrY ); +static void Fxu_CreateCoversNode( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode, Fxu_Cube * pCubeFirst, Fxu_Cube * pCubeNext ); +static Fxu_Cube * Fxu_CreateCoversFirstCube( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode ); +static Abc_Fan_t * s_pLits; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Creates the sparse matrix from the array of Sop covers.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Matrix * Fxu_CreateMatrix( Fxu_Data_t * pData ) +{ + Fxu_Matrix * p; + Fxu_Var * pVar; + Fxu_Cube * pCubeFirst, * pCubeNew; + Fxu_Cube * pCube1, * pCube2; + char * pSopCover; + char * pSopCube; + int * pOrder, nBitsMax; + int i, v, c; + int nCubesTotal; + int nPairsTotal; + int nPairsStore; + int nCubes; + int iCube, iPair; + int nFanins; + Vec_Fan_t * vFanins; + + // collect all sorts of statistics + nCubesTotal = 0; + nPairsTotal = 0; + nPairsStore = 0; + nBitsMax = -1; + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + nCubes = Abc_SopGetCubeNum( pSopCover ); + nFanins = Abc_SopGetVarNum( pSopCover ); + assert( nFanins > 1 && nCubes > 0 ); + + nCubesTotal += nCubes; + nPairsTotal += nCubes * (nCubes - 1) / 2; + nPairsStore += nCubes * nCubes; + if ( nBitsMax < nFanins ) + nBitsMax = nFanins; + } + if ( nBitsMax <= 0 ) + { + printf( "The current network does not have SOPs to perform extraction.\n" ); + return NULL; + } + + if ( nPairsStore > 10000000 ) + { + printf( "The problem is too large to be solved by \"fxu\" (%d cubes and %d cube pairs)\n", nCubesTotal, nPairsStore ); + return NULL; + } + + // start the matrix + p = Fxu_MatrixAllocate(); + // create the column labels + p->ppVars = ALLOC( Fxu_Var *, 2 * (pData->nNodesOld + pData->nNodesExt) ); + for ( i = 0; i < 2 * pData->nNodesOld; i++ ) + p->ppVars[i] = Fxu_MatrixAddVar( p ); + + // allocate storage for all cube pairs at once + p->pppPairs = ALLOC( Fxu_Pair **, nCubesTotal + 100 ); + p->ppPairs = ALLOC( Fxu_Pair *, nPairsStore + 100 ); + memset( p->ppPairs, 0, sizeof(Fxu_Pair *) * nPairsStore ); + iCube = 0; + iPair = 0; + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + // get the number of cubes + nCubes = Abc_SopGetCubeNum( pSopCover ); + // get the new var in the matrix + pVar = p->ppVars[2*i+1]; + // assign the pair storage + pVar->nCubes = nCubes; + if ( nCubes > 0 ) + { + pVar->ppPairs = p->pppPairs + iCube; + pVar->ppPairs[0] = p->ppPairs + iPair; + for ( v = 1; v < nCubes; v++ ) + pVar->ppPairs[v] = pVar->ppPairs[v-1] + nCubes; + } + // update + iCube += nCubes; + iPair += nCubes * nCubes; + } + assert( iCube == nCubesTotal ); + assert( iPair == nPairsStore ); + + + // allocate room for the reordered literals + pOrder = ALLOC( int, nBitsMax ); + // create the rows + for ( i = 0; i < pData->nNodesOld; i++ ) + if ( pSopCover = pData->vSops->pArray[i] ) + { + // get the new var in the matrix + pVar = p->ppVars[2*i+1]; + // here we sort the literals of the cover + // in the increasing order of the numbers of the corresponding nodes + // because literals should be added to the matrix in this order + vFanins = pData->vFanins->pArray[i]; + s_pLits = vFanins->pArray; + // start the variable order + nFanins = Abc_SopGetVarNum( pSopCover ); + for ( v = 0; v < nFanins; v++ ) + pOrder[v] = v; + // reorder the fanins + qsort( (void *)pOrder, nFanins, sizeof(int),(int (*)(const void *, const void *))Fxu_CreateMatrixLitCompare); + assert( s_pLits[ pOrder[0] ].iFan < s_pLits[ pOrder[nFanins-1] ].iFan ); + // create the corresponding cubes in the matrix + pCubeFirst = NULL; + c = 0; + Abc_SopForEachCube( pSopCover, nFanins, pSopCube ) + { + // create the cube + pCubeNew = Fxu_MatrixAddCube( p, pVar, c ); + Fxu_CreateMatrixAddCube( p, pCubeNew, pSopCube, vFanins, pOrder ); + if ( pCubeFirst == NULL ) + pCubeFirst = pCubeNew; + pCubeNew->pFirst = pCubeFirst; + c++; + } + // set the first cube of this var + pVar->pFirst = pCubeFirst; + // create the divisors without preprocessing + if ( nPairsTotal <= pData->nPairsMax ) + { + for ( pCube1 = pCubeFirst; pCube1; pCube1 = pCube1->pNext ) + for ( pCube2 = pCube1? pCube1->pNext: NULL; pCube2; pCube2 = pCube2->pNext ) + Fxu_MatrixAddDivisor( p, pCube1, pCube2 ); + } + } + FREE( pOrder ); + + // consider the case when cube pairs should be preprocessed + // before adding them to the set of divisors + if ( nPairsTotal > pData->nPairsMax ) + Fxu_PreprocessCubePairs( p, pData->vSops, nPairsTotal, pData->nPairsMax ); + + // add the var pairs to the heap + Fxu_MatrixComputeSingles( p ); + + // allocate temporary storage for pairs + if ( pData->nPairsMax < 1000 ) + pData->nPairsMax = 1000; + p->pPairsTemp = ALLOC( Fxu_Pair *, pData->nPairsMax * 10 + 100 ); + if ( pData->fVerbose ) + { + double Density; + Density = ((double)p->nEntries) / p->lVars.nItems / p->lCubes.nItems; + fprintf( stdout, "Matrix: [vars x cubes] = [%d x %d] ", + p->lVars.nItems, p->lCubes.nItems ); + fprintf( stdout, "Lits = %d Density = %.5f%%\n", + p->nEntries, Density ); + fprintf( stdout, "1-cube divisors = %6d. ", p->lSingles.nItems ); + fprintf( stdout, "2-cube divisors = %6d. ", p->nDivsTotal ); + fprintf( stdout, "Cube pairs = %6d.", nPairsTotal ); + fprintf( stdout, "\n" ); + } +// Fxu_MatrixPrint( stdout, p ); + return p; +} + +/**Function************************************************************* + + Synopsis [Adds one cube with literals to the matrix.] + + Description [Create the cube and literals in the matrix corresponding + to the given cube in the SOP cover. Co-singleton transform is performed here.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube, char * pSopCube, Vec_Fan_t * vFanins, int * pOrder ) +{ + Fxu_Var * pVar; + int Value, i; + // add literals to the matrix + Abc_CubeForEachVar( pSopCube, Value, i ) + { + Value = pSopCube[pOrder[i]]; + if ( Value == '0' ) + { + pVar = p->ppVars[ 2 * vFanins->pArray[pOrder[i]].iFan + 1 ]; // CST + Fxu_MatrixAddLiteral( p, pCube, pVar ); + } + else if ( Value == '1' ) + { + pVar = p->ppVars[ 2 * vFanins->pArray[pOrder[i]].iFan ]; // CST + Fxu_MatrixAddLiteral( p, pCube, pVar ); + } + } +} + + +/**Function************************************************************* + + Synopsis [Creates the new array of Sop covers from the sparse matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateCovers( Fxu_Matrix * p, Fxu_Data_t * pData ) +{ + Fxu_Cube * pCube, * pCubeFirst, * pCubeNext; + int iNode, n; + char * pSopCover; + + // get the first cube of the first internal node + pCubeFirst = Fxu_CreateCoversFirstCube( p, pData, 0 ); + + // go through the internal nodes + for ( n = 0; n < pData->nNodesOld; n++ ) + if ( pSopCover = pData->vSops->pArray[n] ) + { + // get the number of this node + iNode = n; + // get the next first cube + pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 ); + // check if there any new variables in these cubes + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + if ( pCube->lLits.pTail && pCube->lLits.pTail->iVar >= 2 * pData->nNodesOld ) + break; + if ( pCube != pCubeNext ) + Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext ); + // update the first cube + pCubeFirst = pCubeNext; + } + + // add the covers for the extracted nodes + for ( n = 0; n < pData->nNodesNew; n++ ) + { + // get the number of this node + iNode = pData->nNodesOld + n; + // get the next first cube + pCubeNext = Fxu_CreateCoversFirstCube( p, pData, iNode + 1 ); + // the node should be added + Fxu_CreateCoversNode( p, pData, iNode, pCubeFirst, pCubeNext ); + // update the first cube + pCubeFirst = pCubeNext; + } +} + +/**Function************************************************************* + + Synopsis [Create Sop covers for one node that has changed.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_CreateCoversNode( Fxu_Matrix * p, Fxu_Data_t * pData, int iNode, Fxu_Cube * pCubeFirst, Fxu_Cube * pCubeNext ) +{ + Vec_Int_t * vInputsNew; + char * pSopCover; + char * pSopCube; + Fxu_Var * pVar; + Fxu_Cube * pCube; + Fxu_Lit * pLit; + int iNum, nCubes, v; + int fEmptyCube; + + // collect positive polarity variable in the cubes between pCubeFirst and pCubeNext + Fxu_MatrixRingVarsStart( p ); + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + for ( pLit = pCube->lLits.pHead; pLit; pLit = pLit->pHNext ) + { + pVar = p->ppVars[ 2 * (pLit->pVar->iVar/2) + 1 ]; + if ( pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pVar ); + } + Fxu_MatrixRingVarsStop( p ); + + // collect the variable numbers + vInputsNew = Vec_IntAlloc( 4 ); + Fxu_MatrixForEachVarInRing( p, pVar ) + Vec_IntPush( vInputsNew, pVar->iVar / 2 ); + Fxu_MatrixRingVarsUnmark( p ); + + // sort the vars by their number + Vec_IntSort( vInputsNew, 0 ); + + // mark the vars with their numbers in the sorted array + for ( v = 0; v < vInputsNew->nSize; v++ ) + { + p->ppVars[ 2 * vInputsNew->pArray[v] + 0 ]->lLits.nItems = v; // hack - reuse lLits.nItems + p->ppVars[ 2 * vInputsNew->pArray[v] + 1 ]->lLits.nItems = v; // hack - reuse lLits.nItems + } + + // count the number of cubes + nCubes = 0; + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + if ( pCube->lLits.nItems ) + nCubes++; + + // allocate room for the new cover + pSopCover = Abc_SopStart( pData->pManSop, nCubes, vInputsNew->nSize ); + // set the correct polarity of the cover + if ( iNode < pData->nNodesOld && Abc_SopGetPhase( pData->vSops->pArray[iNode] ) == 0 ) + Abc_SopComplement( pSopCover ); + + // add the cubes + nCubes = 0; + for ( pCube = pCubeFirst; pCube != pCubeNext; pCube = pCube->pNext ) + { + if ( pCube->lLits.nItems == 0 ) + continue; + // get hold of the SOP cube + pSopCube = pSopCover + nCubes * (vInputsNew->nSize + 3); + // insert literals + fEmptyCube = 1; + for ( pLit = pCube->lLits.pHead; pLit; pLit = pLit->pHNext ) + { + iNum = pLit->pVar->lLits.nItems; // hack - reuse lLits.nItems + assert( iNum < vInputsNew->nSize ); + if ( pLit->pVar->iVar / 2 < pData->nNodesOld ) + pSopCube[iNum] = (pLit->pVar->iVar & 1)? '0' : '1'; // reverse CST + else + pSopCube[iNum] = (pLit->pVar->iVar & 1)? '1' : '0'; // no CST + fEmptyCube = 0; + } + assert( !fEmptyCube ); + // count the cube + nCubes++; + } + assert( nCubes == Abc_SopGetCubeNum(pSopCover) ); + + pData->vSopsNew->pArray[iNode] = pSopCover; + pData->vFaninsNew->pArray[iNode] = vInputsNew; +} + + +/**Function************************************************************* + + Synopsis [Adds the var to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Cube * Fxu_CreateCoversFirstCube( Fxu_Matrix * p, Fxu_Data_t * pData, int iVar ) +{ + int v; + for ( v = iVar; v < pData->nNodesOld + pData->nNodesNew; v++ ) + if ( p->ppVars[ 2*v + 1 ]->pFirst ) + return p->ppVars[ 2*v + 1 ]->pFirst; + return NULL; +} + +/**Function************************************************************* + + Synopsis [Compares the vars by their number.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_CreateMatrixLitCompare( int * ptrX, int * ptrY ) +{ + return s_pLits[*ptrX].iFan - s_pLits[*ptrY].iFan; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// diff --git a/src/opt/fxu/fxuHeapD.c b/src/opt/fxu/fxuHeapD.c new file mode 100644 index 00000000..7c123249 --- /dev/null +++ b/src/opt/fxu/fxuHeapD.c @@ -0,0 +1,445 @@ +/**CFile**************************************************************** + + FileName [fxuHeapD.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [The priority queue for double cube divisors.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuHeapD.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define FXU_HEAP_DOUBLE_WEIGHT(pDiv) ((pDiv)->Weight) +#define FXU_HEAP_DOUBLE_CURRENT(p, pDiv) ((p)->pTree[(pDiv)->HNum]) +#define FXU_HEAP_DOUBLE_PARENT_EXISTS(p, pDiv) ((pDiv)->HNum > 1) +#define FXU_HEAP_DOUBLE_CHILD1_EXISTS(p, pDiv) (((pDiv)->HNum << 1) <= p->nItems) +#define FXU_HEAP_DOUBLE_CHILD2_EXISTS(p, pDiv) ((((pDiv)->HNum << 1)+1) <= p->nItems) +#define FXU_HEAP_DOUBLE_PARENT(p, pDiv) ((p)->pTree[(pDiv)->HNum >> 1]) +#define FXU_HEAP_DOUBLE_CHILD1(p, pDiv) ((p)->pTree[(pDiv)->HNum << 1]) +#define FXU_HEAP_DOUBLE_CHILD2(p, pDiv) ((p)->pTree[((pDiv)->HNum << 1)+1]) +#define FXU_HEAP_DOUBLE_ASSERT(p, pDiv) assert( (pDiv)->HNum >= 1 && (pDiv)->HNum <= p->nItemsAlloc ) + +static void Fxu_HeapDoubleResize( Fxu_HeapDouble * p ); +static void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 ); +static void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv ); +static void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_HeapDouble * Fxu_HeapDoubleStart() +{ + Fxu_HeapDouble * p; + p = ALLOC( Fxu_HeapDouble, 1 ); + memset( p, 0, sizeof(Fxu_HeapDouble) ); + p->nItems = 0; + p->nItemsAlloc = 10000; + p->pTree = ALLOC( Fxu_Double *, p->nItemsAlloc + 1 ); + p->pTree[0] = NULL; + return p; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleResize( Fxu_HeapDouble * p ) +{ + p->nItemsAlloc *= 2; + p->pTree = REALLOC( Fxu_Double *, p->pTree, p->nItemsAlloc + 1 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleStop( Fxu_HeapDouble * p ) +{ + free( p->pTree ); + free( p ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p ) +{ + Fxu_Double * pDiv; + int Counter = 1; + int Degree = 1; + + Fxu_HeapDoubleCheck( p ); + fprintf( pFile, "The contents of the heap:\n" ); + fprintf( pFile, "Level %d: ", Degree ); + Fxu_HeapDoubleForEachItem( p, pDiv ) + { + assert( Counter == p->pTree[Counter]->HNum ); + fprintf( pFile, "%2d=%3d ", Counter, FXU_HEAP_DOUBLE_WEIGHT(p->pTree[Counter]) ); + if ( ++Counter == (1 << Degree) ) + { + fprintf( pFile, "\n" ); + Degree++; + fprintf( pFile, "Level %d: ", Degree ); + } + } + fprintf( pFile, "\n" ); + fprintf( pFile, "End of the heap printout.\n" ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleCheck( Fxu_HeapDouble * p ) +{ + Fxu_Double * pDiv; + Fxu_HeapDoubleForEachItem( p, pDiv ) + { + assert( pDiv->HNum == p->i ); + Fxu_HeapDoubleCheckOne( p, pDiv ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ + int Weight1, Weight2; + if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) ) + { + Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv); + Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ); + assert( Weight1 >= Weight2 ); + } + if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) ) + { + Weight1 = FXU_HEAP_DOUBLE_WEIGHT(pDiv); + Weight2 = FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ); + assert( Weight1 >= Weight2 ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ + if ( p->nItems == p->nItemsAlloc ) + Fxu_HeapDoubleResize( p ); + // put the last entry to the last place and move up + p->pTree[++p->nItems] = pDiv; + pDiv->HNum = p->nItems; + // move the last entry up if necessary + Fxu_HeapDoubleMoveUp( p, pDiv ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ +//printf( "Updating divisor %d.\n", pDiv->Num ); + + FXU_HEAP_DOUBLE_ASSERT(p,pDiv); + if ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,pDiv) && + FXU_HEAP_DOUBLE_WEIGHT(pDiv) > FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_PARENT(p,pDiv) ) ) + Fxu_HeapDoubleMoveUp( p, pDiv ); + else if ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,pDiv) && + FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD1(p,pDiv) ) ) + Fxu_HeapDoubleMoveDn( p, pDiv ); + else if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,pDiv) && + FXU_HEAP_DOUBLE_WEIGHT(pDiv) < FXU_HEAP_DOUBLE_WEIGHT( FXU_HEAP_DOUBLE_CHILD2(p,pDiv) ) ) + Fxu_HeapDoubleMoveDn( p, pDiv ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ + FXU_HEAP_DOUBLE_ASSERT(p,pDiv); + // put the last entry to the deleted place + // decrement the number of entries + p->pTree[pDiv->HNum] = p->pTree[p->nItems--]; + p->pTree[pDiv->HNum]->HNum = pDiv->HNum; + // move the top entry down if necessary + Fxu_HeapDoubleUpdate( p, p->pTree[pDiv->HNum] ); + pDiv->HNum = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p ) +{ + if ( p->nItems == 0 ) + return NULL; + return p->pTree[1]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p ) +{ + Fxu_Double * pDiv; + if ( p->nItems == 0 ) + return NULL; + // prepare the return value + pDiv = p->pTree[1]; + pDiv->HNum = 0; + // put the last entry on top + // decrement the number of entries + p->pTree[1] = p->pTree[p->nItems--]; + p->pTree[1]->HNum = 1; + // move the top entry down if necessary + Fxu_HeapDoubleMoveDn( p, p->pTree[1] ); + return pDiv; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p ) +{ + if ( p->nItems == 0 ) + return -1; + else + return FXU_HEAP_DOUBLE_WEIGHT(p->pTree[1]); +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleSwap( Fxu_Double ** pDiv1, Fxu_Double ** pDiv2 ) +{ + Fxu_Double * pDiv; + int Temp; + pDiv = *pDiv1; + *pDiv1 = *pDiv2; + *pDiv2 = pDiv; + Temp = (*pDiv1)->HNum; + (*pDiv1)->HNum = (*pDiv2)->HNum; + (*pDiv2)->HNum = Temp; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleMoveUp( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ + Fxu_Double ** ppDiv, ** ppPar; + ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv); + while ( FXU_HEAP_DOUBLE_PARENT_EXISTS(p,*ppDiv) ) + { + ppPar = &FXU_HEAP_DOUBLE_PARENT(p,*ppDiv); + if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) > FXU_HEAP_DOUBLE_WEIGHT(*ppPar) ) + { + Fxu_HeapDoubleSwap( ppDiv, ppPar ); + ppDiv = ppPar; + } + else + break; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapDoubleMoveDn( Fxu_HeapDouble * p, Fxu_Double * pDiv ) +{ + Fxu_Double ** ppChild1, ** ppChild2, ** ppDiv; + ppDiv = &FXU_HEAP_DOUBLE_CURRENT(p, pDiv); + while ( FXU_HEAP_DOUBLE_CHILD1_EXISTS(p,*ppDiv) ) + { // if Child1 does not exist, Child2 also does not exists + + // get the children + ppChild1 = &FXU_HEAP_DOUBLE_CHILD1(p,*ppDiv); + if ( FXU_HEAP_DOUBLE_CHILD2_EXISTS(p,*ppDiv) ) + { + ppChild2 = &FXU_HEAP_DOUBLE_CHILD2(p,*ppDiv); + + // consider two cases + if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) && + FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) ) + { // Div is larger than both, skip + break; + } + else + { // Div is smaller than one of them, then swap it with larger + if ( FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild2) ) + { + Fxu_HeapDoubleSwap( ppDiv, ppChild1 ); + // update the pointer + ppDiv = ppChild1; + } + else + { + Fxu_HeapDoubleSwap( ppDiv, ppChild2 ); + // update the pointer + ppDiv = ppChild2; + } + } + } + else // Child2 does not exist + { + // consider two cases + if ( FXU_HEAP_DOUBLE_WEIGHT(*ppDiv) >= FXU_HEAP_DOUBLE_WEIGHT(*ppChild1) ) + { // Div is larger than Child1, skip + break; + } + else + { // Div is smaller than Child1, then swap them + Fxu_HeapDoubleSwap( ppDiv, ppChild1 ); + // update the pointer + ppDiv = ppChild1; + } + } + } +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuHeapS.c b/src/opt/fxu/fxuHeapS.c new file mode 100644 index 00000000..dbd66055 --- /dev/null +++ b/src/opt/fxu/fxuHeapS.c @@ -0,0 +1,444 @@ +/**CFile**************************************************************** + + FileName [fxuHeapS.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [The priority queue for variables.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuHeapS.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define FXU_HEAP_SINGLE_WEIGHT(pSingle) ((pSingle)->Weight) +#define FXU_HEAP_SINGLE_CURRENT(p, pSingle) ((p)->pTree[(pSingle)->HNum]) +#define FXU_HEAP_SINGLE_PARENT_EXISTS(p, pSingle) ((pSingle)->HNum > 1) +#define FXU_HEAP_SINGLE_CHILD1_EXISTS(p, pSingle) (((pSingle)->HNum << 1) <= p->nItems) +#define FXU_HEAP_SINGLE_CHILD2_EXISTS(p, pSingle) ((((pSingle)->HNum << 1)+1) <= p->nItems) +#define FXU_HEAP_SINGLE_PARENT(p, pSingle) ((p)->pTree[(pSingle)->HNum >> 1]) +#define FXU_HEAP_SINGLE_CHILD1(p, pSingle) ((p)->pTree[(pSingle)->HNum << 1]) +#define FXU_HEAP_SINGLE_CHILD2(p, pSingle) ((p)->pTree[((pSingle)->HNum << 1)+1]) +#define FXU_HEAP_SINGLE_ASSERT(p, pSingle) assert( (pSingle)->HNum >= 1 && (pSingle)->HNum <= p->nItemsAlloc ) + +static void Fxu_HeapSingleResize( Fxu_HeapSingle * p ); +static void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 ); +static void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle ); +static void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_HeapSingle * Fxu_HeapSingleStart() +{ + Fxu_HeapSingle * p; + p = ALLOC( Fxu_HeapSingle, 1 ); + memset( p, 0, sizeof(Fxu_HeapSingle) ); + p->nItems = 0; + p->nItemsAlloc = 2000; + p->pTree = ALLOC( Fxu_Single *, p->nItemsAlloc + 10 ); + p->pTree[0] = NULL; + return p; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleResize( Fxu_HeapSingle * p ) +{ + p->nItemsAlloc *= 2; + p->pTree = REALLOC( Fxu_Single *, p->pTree, p->nItemsAlloc + 10 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleStop( Fxu_HeapSingle * p ) +{ + int i; + i = 0; + free( p->pTree ); + i = 1; + free( p ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSinglePrint( FILE * pFile, Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + int Counter = 1; + int Degree = 1; + + Fxu_HeapSingleCheck( p ); + fprintf( pFile, "The contents of the heap:\n" ); + fprintf( pFile, "Level %d: ", Degree ); + Fxu_HeapSingleForEachItem( p, pSingle ) + { + assert( Counter == p->pTree[Counter]->HNum ); + fprintf( pFile, "%2d=%3d ", Counter, FXU_HEAP_SINGLE_WEIGHT(p->pTree[Counter]) ); + if ( ++Counter == (1 << Degree) ) + { + fprintf( pFile, "\n" ); + Degree++; + fprintf( pFile, "Level %d: ", Degree ); + } + } + fprintf( pFile, "\n" ); + fprintf( pFile, "End of the heap printout.\n" ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleCheck( Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + Fxu_HeapSingleForEachItem( p, pSingle ) + { + assert( pSingle->HNum == p->i ); + Fxu_HeapSingleCheckOne( p, pSingle ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleCheckOne( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + int Weight1, Weight2; + if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) ) + { + Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle); + Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ); + assert( Weight1 >= Weight2 ); + } + if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) ) + { + Weight1 = FXU_HEAP_SINGLE_WEIGHT(pSingle); + Weight2 = FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ); + assert( Weight1 >= Weight2 ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleInsert( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + if ( p->nItems == p->nItemsAlloc ) + Fxu_HeapSingleResize( p ); + // put the last entry to the last place and move up + p->pTree[++p->nItems] = pSingle; + pSingle->HNum = p->nItems; + // move the last entry up if necessary + Fxu_HeapSingleMoveUp( p, pSingle ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleUpdate( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + FXU_HEAP_SINGLE_ASSERT(p,pSingle); + if ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) > FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_PARENT(p,pSingle) ) ) + Fxu_HeapSingleMoveUp( p, pSingle ); + else if ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD1(p,pSingle) ) ) + Fxu_HeapSingleMoveDn( p, pSingle ); + else if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,pSingle) && + FXU_HEAP_SINGLE_WEIGHT(pSingle) < FXU_HEAP_SINGLE_WEIGHT( FXU_HEAP_SINGLE_CHILD2(p,pSingle) ) ) + Fxu_HeapSingleMoveDn( p, pSingle ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleDelete( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + int Place = pSingle->HNum; + FXU_HEAP_SINGLE_ASSERT(p,pSingle); + // put the last entry to the deleted place + // decrement the number of entries + p->pTree[Place] = p->pTree[p->nItems--]; + p->pTree[Place]->HNum = Place; + // move the top entry down if necessary + Fxu_HeapSingleUpdate( p, p->pTree[Place] ); + pSingle->HNum = 0; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Single * Fxu_HeapSingleReadMax( Fxu_HeapSingle * p ) +{ + if ( p->nItems == 0 ) + return NULL; + return p->pTree[1]; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Single * Fxu_HeapSingleGetMax( Fxu_HeapSingle * p ) +{ + Fxu_Single * pSingle; + if ( p->nItems == 0 ) + return NULL; + // prepare the return value + pSingle = p->pTree[1]; + pSingle->HNum = 0; + // put the last entry on top + // decrement the number of entries + p->pTree[1] = p->pTree[p->nItems--]; + p->pTree[1]->HNum = 1; + // move the top entry down if necessary + Fxu_HeapSingleMoveDn( p, p->pTree[1] ); + return pSingle; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_HeapSingleReadMaxWeight( Fxu_HeapSingle * p ) +{ + if ( p->nItems == 0 ) + return -1; + return FXU_HEAP_SINGLE_WEIGHT(p->pTree[1]); +} + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleSwap( Fxu_Single ** pSingle1, Fxu_Single ** pSingle2 ) +{ + Fxu_Single * pSingle; + int Temp; + pSingle = *pSingle1; + *pSingle1 = *pSingle2; + *pSingle2 = pSingle; + Temp = (*pSingle1)->HNum; + (*pSingle1)->HNum = (*pSingle2)->HNum; + (*pSingle2)->HNum = Temp; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleMoveUp( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + Fxu_Single ** ppSingle, ** ppPar; + ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle); + while ( FXU_HEAP_SINGLE_PARENT_EXISTS(p,*ppSingle) ) + { + ppPar = &FXU_HEAP_SINGLE_PARENT(p,*ppSingle); + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) > FXU_HEAP_SINGLE_WEIGHT(*ppPar) ) + { + Fxu_HeapSingleSwap( ppSingle, ppPar ); + ppSingle = ppPar; + } + else + break; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_HeapSingleMoveDn( Fxu_HeapSingle * p, Fxu_Single * pSingle ) +{ + Fxu_Single ** ppChild1, ** ppChild2, ** ppSingle; + ppSingle = &FXU_HEAP_SINGLE_CURRENT(p, pSingle); + while ( FXU_HEAP_SINGLE_CHILD1_EXISTS(p,*ppSingle) ) + { // if Child1 does not exist, Child2 also does not exists + + // get the children + ppChild1 = &FXU_HEAP_SINGLE_CHILD1(p,*ppSingle); + if ( FXU_HEAP_SINGLE_CHILD2_EXISTS(p,*ppSingle) ) + { + ppChild2 = &FXU_HEAP_SINGLE_CHILD2(p,*ppSingle); + + // consider two cases + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) && + FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) ) + { // Var is larger than both, skip + break; + } + else + { // Var is smaller than one of them, then swap it with larger + if ( FXU_HEAP_SINGLE_WEIGHT(*ppChild1) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild2) ) + { + Fxu_HeapSingleSwap( ppSingle, ppChild1 ); + // update the pointer + ppSingle = ppChild1; + } + else + { + Fxu_HeapSingleSwap( ppSingle, ppChild2 ); + // update the pointer + ppSingle = ppChild2; + } + } + } + else // Child2 does not exist + { + // consider two cases + if ( FXU_HEAP_SINGLE_WEIGHT(*ppSingle) >= FXU_HEAP_SINGLE_WEIGHT(*ppChild1) ) + { // Var is larger than Child1, skip + break; + } + else + { // Var is smaller than Child1, then swap them + Fxu_HeapSingleSwap( ppSingle, ppChild1 ); + // update the pointer + ppSingle = ppChild1; + } + } + } +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// diff --git a/src/opt/fxu/fxuInt.h b/src/opt/fxu/fxuInt.h new file mode 100644 index 00000000..1f5a19b8 --- /dev/null +++ b/src/opt/fxu/fxuInt.h @@ -0,0 +1,541 @@ +/**CFile**************************************************************** + + FileName [fxuInt.h] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Internal declarations of fast extract for unate covers.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuInt.h,v 1.3 2003/04/10 05:42:44 donald Exp $] + +***********************************************************************/ + +#ifndef __FXU_INT_H__ +#define __FXU_INT_H__ + +//////////////////////////////////////////////////////////////////////// +/// INCLUDES /// +//////////////////////////////////////////////////////////////////////// + +#include "util.h" +#include "extra.h" + +//////////////////////////////////////////////////////////////////////// +/// PARAMETERS /// +//////////////////////////////////////////////////////////////////////// + +// uncomment this macro to switch to standard memory management +//#define USE_SYSTEM_MEMORY_MANAGEMENT + +//////////////////////////////////////////////////////////////////////// +/// STRUCTURE DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/* + Here is an informal description of the FX data structure. + (1) The sparse matrix is filled with literals, associated with + cubes (row) and variables (columns). The matrix contains + all the cubes of all the nodes in the network. + (2) A cube is associated with + (a) its literals in the matrix, + (b) the output variable of the node, to which this cube belongs, + (3) A variable is associated with + (a) its literals in the matrix and + (b) the list of cube pairs in the cover, for which it is the output + (4) A cube pair is associated with two cubes and contains the counters + of literals in the base and in the cubes without the base + (5) A double-cube divisor is associated with list of all cube pairs + that produce it and its current weight (which is updated automatically + each time a new pair is added or an old pair is removed). + (6) A single-cube divisor is associated the pair of variables. +*/ + +// sparse matrix +typedef struct FxuMatrix Fxu_Matrix; // the sparse matrix + +// sparse matrix contents: cubes (rows), vars (columns), literals (entries) +typedef struct FxuCube Fxu_Cube; // one cube in the sparse matrix +typedef struct FxuVar Fxu_Var; // one literal in the sparse matrix +typedef struct FxuLit Fxu_Lit; // one entry in the sparse matrix + +// double cube divisors +typedef struct FxuPair Fxu_Pair; // the pair of cubes +typedef struct FxuDouble Fxu_Double; // the double-cube divisor +typedef struct FxuSingle Fxu_Single; // the two-literal single-cube divisor + +// various lists +typedef struct FxuListCube Fxu_ListCube; // the list of cubes +typedef struct FxuListVar Fxu_ListVar; // the list of literals +typedef struct FxuListLit Fxu_ListLit; // the list of entries +typedef struct FxuListPair Fxu_ListPair; // the list of pairs +typedef struct FxuListDouble Fxu_ListDouble; // the list of divisors +typedef struct FxuListSingle Fxu_ListSingle; // the list of single-cube divisors + +// various heaps +typedef struct FxuHeapDouble Fxu_HeapDouble; // the heap of divisors +typedef struct FxuHeapSingle Fxu_HeapSingle; // the heap of variables + + +// various lists + +// the list of cubes in the sparse matrix +struct FxuListCube +{ + Fxu_Cube * pHead; + Fxu_Cube * pTail; + int nItems; +}; + +// the list of literals in the sparse matrix +struct FxuListVar +{ + Fxu_Var * pHead; + Fxu_Var * pTail; + int nItems; +}; + +// the list of entries in the sparse matrix +struct FxuListLit +{ + Fxu_Lit * pHead; + Fxu_Lit * pTail; + int nItems; +}; + +// the list of cube pair in the sparse matrix +struct FxuListPair +{ + Fxu_Pair * pHead; + Fxu_Pair * pTail; + int nItems; +}; + +// the list of divisors in the sparse matrix +struct FxuListDouble +{ + Fxu_Double * pHead; + Fxu_Double * pTail; + int nItems; +}; + +// the list of divisors in the sparse matrix +struct FxuListSingle +{ + Fxu_Single * pHead; + Fxu_Single * pTail; + int nItems; +}; + + +// various heaps + +// the heap of double cube divisors by weight +struct FxuHeapDouble +{ + Fxu_Double ** pTree; + int nItems; + int nItemsAlloc; + int i; +}; + +// the heap of variable by their occurrence in the cubes +struct FxuHeapSingle +{ + Fxu_Single ** pTree; + int nItems; + int nItemsAlloc; + int i; +}; + + + +// sparse matrix +struct FxuMatrix // ~ 30 words +{ + // information about the network +// int fMvNetwork; // set to 1 if the network has MV nodes +// int * pValue2Node; // the mapping of values into nodes + // the cubes + Fxu_ListCube lCubes; // the double linked list of cubes + // the values (binary literals) + Fxu_ListVar lVars; // the double linked list of variables + Fxu_Var ** ppVars; // the array of variables + // the double cube divisors + Fxu_ListDouble * pTable; // the hash table of divisors + int nTableSize; // the hash table size + int nDivs; // the number of divisors in the table + int nDivsTotal; // the number of divisors in the table + Fxu_HeapDouble * pHeapDouble; // the heap of divisors by weight + // the single cube divisors + Fxu_ListSingle lSingles; // the linked list of single cube divisors + Fxu_HeapSingle * pHeapSingle; // the heap of variables by the number of literals in the matrix + // storage for cube pairs + Fxu_Pair *** pppPairs; + Fxu_Pair ** ppPairs; + // temporary storage for cubes + Fxu_Cube * pOrderCubes; + Fxu_Cube ** ppTailCubes; + // temporary storage for variables + Fxu_Var * pOrderVars; + Fxu_Var ** ppTailVars; + // temporary storage for pairs + Fxu_Pair ** pPairsTemp; + int nPairsTemp; +// int nPairsMax; + // statistics + int nEntries; // the total number of entries in the sparse matrix + int nDivs1; // the single cube divisors taken + int nDivs2; // the double cube divisors taken + int nDivs3; // the double cube divisors with complement + // memory manager + Extra_MmFixed_t * pMemMan; // the memory manager for all small sized entries +}; + +// the cube in the sparse matrix +struct FxuCube // 9 words +{ + int iCube; // the number of this cube in the cover + Fxu_Cube * pFirst; // the pointer to the first cube of this cover + Fxu_Var * pVar; // the variable representing the output of the cover + Fxu_ListLit lLits; // the row in the table + Fxu_Cube * pPrev; // the previous cube + Fxu_Cube * pNext; // the next cube + Fxu_Cube * pOrder; // the specialized linked list of cubes +}; + +// the variable in the sparse matrix +struct FxuVar // 10 words +{ + int iVar; // the number of this variable + int nCubes; // the number of cubes assoc with this var + Fxu_Cube * pFirst; // the first cube assoc with this var + Fxu_Pair *** ppPairs; // the pairs of cubes assoc with this var + Fxu_ListLit lLits; // the column in the table + Fxu_Var * pPrev; // the previous variable + Fxu_Var * pNext; // the next variable + Fxu_Var * pOrder; // the specialized linked list of variables +}; + +// the literal entry in the sparse matrix +struct FxuLit // 8 words +{ + int iVar; // the number of this variable + int iCube; // the number of this cube + Fxu_Cube * pCube; // the cube of this literal + Fxu_Var * pVar; // the variable of this literal + Fxu_Lit * pHPrev; // prev lit in the cube + Fxu_Lit * pHNext; // next lit in the cube + Fxu_Lit * pVPrev; // prev lit of the var + Fxu_Lit * pVNext; // next lit of the var +}; + +// the cube pair +struct FxuPair // 10 words +{ + int nLits1; // the number of literals in the two cubes + int nLits2; // the number of literals in the two cubes + int nBase; // the number of literals in the base + Fxu_Double * pDiv; // the divisor of this pair + Fxu_Cube * pCube1; // the first cube of the pair + Fxu_Cube * pCube2; // the second cube of the pair + int iCube1; // the first cube of the pair + int iCube2; // the second cube of the pair + Fxu_Pair * pDPrev; // the previous pair in the divisor + Fxu_Pair * pDNext; // the next pair in the divisor +}; + +// the double cube divisor +struct FxuDouble // 10 words +{ + int Num; // the unique number of this divisor + int HNum; // the heap number of this divisor + int Weight; // the weight of this divisor + unsigned Key; // the hash key of this divisor + Fxu_ListPair lPairs; // the pairs of cubes, which produce this divisor + Fxu_Double * pPrev; // the previous divisor in the table + Fxu_Double * pNext; // the next divisor in the table + Fxu_Double * pOrder; // the specialized linked list of divisors +}; + +// the single cube divisor +struct FxuSingle // 7 words +{ + int Num; // the unique number of this divisor + int HNum; // the heap number of this divisor + int Weight; // the weight of this divisor + Fxu_Var * pVar1; // the first variable of the single-cube divisor + Fxu_Var * pVar2; // the second variable of the single-cube divisor + Fxu_Single * pPrev; // the previous divisor in the list + Fxu_Single * pNext; // the next divisor in the list +}; + +//////////////////////////////////////////////////////////////////////// +/// MACRO DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +// minimum/maximum +#define Fxu_Min( a, b ) ( ((a)<(b))? (a):(b) ) +#define Fxu_Max( a, b ) ( ((a)>(b))? (a):(b) ) + +// selection of the minimum/maximum cube in the pair +#define Fxu_PairMinCube( pPair ) (((pPair)->iCube1 < (pPair)->iCube2)? (pPair)->pCube1: (pPair)->pCube2) +#define Fxu_PairMaxCube( pPair ) (((pPair)->iCube1 > (pPair)->iCube2)? (pPair)->pCube1: (pPair)->pCube2) +#define Fxu_PairMinCubeInt( pPair ) (((pPair)->iCube1 < (pPair)->iCube2)? (pPair)->iCube1: (pPair)->iCube2) +#define Fxu_PairMaxCubeInt( pPair ) (((pPair)->iCube1 > (pPair)->iCube2)? (pPair)->iCube1: (pPair)->iCube2) + +// iterators + +#define Fxu_MatrixForEachCube( Matrix, Cube )\ + for ( Cube = (Matrix)->lCubes.pHead;\ + Cube;\ + Cube = Cube->pNext ) +#define Fxu_MatrixForEachCubeSafe( Matrix, Cube, Cube2 )\ + for ( Cube = (Matrix)->lCubes.pHead, Cube2 = (Cube? Cube->pNext: NULL);\ + Cube;\ + Cube = Cube2, Cube2 = (Cube? Cube->pNext: NULL) ) + +#define Fxu_MatrixForEachVariable( Matrix, Var )\ + for ( Var = (Matrix)->lVars.pHead;\ + Var;\ + Var = Var->pNext ) +#define Fxu_MatrixForEachVariableSafe( Matrix, Var, Var2 )\ + for ( Var = (Matrix)->lVars.pHead, Var2 = (Var? Var->pNext: NULL);\ + Var;\ + Var = Var2, Var2 = (Var? Var->pNext: NULL) ) + +#define Fxu_MatrixForEachSingle( Matrix, Single )\ + for ( Single = (Matrix)->lSingles.pHead;\ + Single;\ + Single = Single->pNext ) +#define Fxu_MatrixForEachSingleSafe( Matrix, Single, Single2 )\ + for ( Single = (Matrix)->lSingles.pHead, Single2 = (Single? Single->pNext: NULL);\ + Single;\ + Single = Single2, Single2 = (Single? Single->pNext: NULL) ) + +#define Fxu_TableForEachDouble( Matrix, Key, Div )\ + for ( Div = (Matrix)->pTable[Key].pHead;\ + Div;\ + Div = Div->pNext ) +#define Fxu_TableForEachDoubleSafe( Matrix, Key, Div, Div2 )\ + for ( Div = (Matrix)->pTable[Key].pHead, Div2 = (Div? Div->pNext: NULL);\ + Div;\ + Div = Div2, Div2 = (Div? Div->pNext: NULL) ) + +#define Fxu_MatrixForEachDouble( Matrix, Div, Index )\ + for ( Index = 0; Index < (Matrix)->nTableSize; Index++ )\ + Fxu_TableForEachDouble( Matrix, Index, Div ) +#define Fxu_MatrixForEachDoubleSafe( Matrix, Div, Div2, Index )\ + for ( Index = 0; Index < (Matrix)->nTableSize; Index++ )\ + Fxu_TableForEachDoubleSafe( Matrix, Index, Div, Div2 ) + + +#define Fxu_CubeForEachLiteral( Cube, Lit )\ + for ( Lit = (Cube)->lLits.pHead;\ + Lit;\ + Lit = Lit->pHNext ) +#define Fxu_CubeForEachLiteralSafe( Cube, Lit, Lit2 )\ + for ( Lit = (Cube)->lLits.pHead, Lit2 = (Lit? Lit->pHNext: NULL);\ + Lit;\ + Lit = Lit2, Lit2 = (Lit? Lit->pHNext: NULL) ) + +#define Fxu_VarForEachLiteral( Var, Lit )\ + for ( Lit = (Var)->lLits.pHead;\ + Lit;\ + Lit = Lit->pVNext ) + +#define Fxu_CubeForEachDivisor( Cube, Div )\ + for ( Div = (Cube)->lDivs.pHead;\ + Div;\ + Div = Div->pCNext ) + +#define Fxu_DoubleForEachPair( Div, Pair )\ + for ( Pair = (Div)->lPairs.pHead;\ + Pair;\ + Pair = Pair->pDNext ) +#define Fxu_DoubleForEachPairSafe( Div, Pair, Pair2 )\ + for ( Pair = (Div)->lPairs.pHead, Pair2 = (Pair? Pair->pDNext: NULL);\ + Pair;\ + Pair = Pair2, Pair2 = (Pair? Pair->pDNext: NULL) ) + + +// iterator through the cube pairs belonging to the given cube +#define Fxu_CubeForEachPair( pCube, pPair, i )\ + for ( i = 0;\ + i < pCube->pVar->nCubes &&\ + (((unsigned)(pPair = pCube->pVar->ppPairs[pCube->iCube][i])) >= 0);\ + i++ )\ + if ( pPair ) + +// iterator through all the items in the heap +#define Fxu_HeapDoubleForEachItem( Heap, Div )\ + for ( Heap->i = 1;\ + Heap->i <= Heap->nItems && (Div = Heap->pTree[Heap->i]);\ + Heap->i++ ) +#define Fxu_HeapSingleForEachItem( Heap, Single )\ + for ( Heap->i = 1;\ + Heap->i <= Heap->nItems && (Single = Heap->pTree[Heap->i]);\ + Heap->i++ ) + +// starting the rings +#define Fxu_MatrixRingCubesStart( Matrix ) (((Matrix)->ppTailCubes = &((Matrix)->pOrderCubes)), ((Matrix)->pOrderCubes = NULL)) +#define Fxu_MatrixRingVarsStart( Matrix ) (((Matrix)->ppTailVars = &((Matrix)->pOrderVars)), ((Matrix)->pOrderVars = NULL)) +// stopping the rings +#define Fxu_MatrixRingCubesStop( Matrix ) +#define Fxu_MatrixRingVarsStop( Matrix ) +// resetting the rings +#define Fxu_MatrixRingCubesReset( Matrix ) (((Matrix)->pOrderCubes = NULL), ((Matrix)->ppTailCubes = NULL)) +#define Fxu_MatrixRingVarsReset( Matrix ) (((Matrix)->pOrderVars = NULL), ((Matrix)->ppTailVars = NULL)) +// adding to the rings +#define Fxu_MatrixRingCubesAdd( Matrix, Cube) ((*((Matrix)->ppTailCubes) = Cube), ((Matrix)->ppTailCubes = &(Cube)->pOrder), ((Cube)->pOrder = (Fxu_Cube *)1)) +#define Fxu_MatrixRingVarsAdd( Matrix, Var ) ((*((Matrix)->ppTailVars ) = Var ), ((Matrix)->ppTailVars = &(Var)->pOrder ), ((Var)->pOrder = (Fxu_Var *)1)) +// iterating through the rings +#define Fxu_MatrixForEachCubeInRing( Matrix, Cube )\ + if ( (Matrix)->pOrderCubes )\ + for ( Cube = (Matrix)->pOrderCubes;\ + Cube != (Fxu_Cube *)1;\ + Cube = Cube->pOrder ) +#define Fxu_MatrixForEachCubeInRingSafe( Matrix, Cube, Cube2 )\ + if ( (Matrix)->pOrderCubes )\ + for ( Cube = (Matrix)->pOrderCubes, Cube2 = ((Cube != (Fxu_Cube *)1)? Cube->pOrder: (Fxu_Cube *)1);\ + Cube != (Fxu_Cube *)1;\ + Cube = Cube2, Cube2 = ((Cube != (Fxu_Cube *)1)? Cube->pOrder: (Fxu_Cube *)1) ) +#define Fxu_MatrixForEachVarInRing( Matrix, Var )\ + if ( (Matrix)->pOrderVars )\ + for ( Var = (Matrix)->pOrderVars;\ + Var != (Fxu_Var *)1;\ + Var = Var->pOrder ) +#define Fxu_MatrixForEachVarInRingSafe( Matrix, Var, Var2 )\ + if ( (Matrix)->pOrderVars )\ + for ( Var = (Matrix)->pOrderVars, Var2 = ((Var != (Fxu_Var *)1)? Var->pOrder: (Fxu_Var *)1);\ + Var != (Fxu_Var *)1;\ + Var = Var2, Var2 = ((Var != (Fxu_Var *)1)? Var->pOrder: (Fxu_Var *)1) ) +// the procedures are related to the above macros +extern void Fxu_MatrixRingCubesUnmark( Fxu_Matrix * p ); +extern void Fxu_MatrixRingVarsUnmark( Fxu_Matrix * p ); + + +// macros working with memory +// MEM_ALLOC: allocate the given number (Size) of items of type (Type) +// MEM_FREE: deallocate the pointer (Pointer) to the given number (Size) of items of type (Type) +#ifdef USE_SYSTEM_MEMORY_MANAGEMENT +#define MEM_ALLOC_FXU( Manager, Type, Size ) ((Type *)malloc( (Size) * sizeof(Type) )) +#define MEM_FREE_FXU( Manager, Type, Size, Pointer ) if ( Pointer ) { free(Pointer); Pointer = NULL; } +#else +#define MEM_ALLOC_FXU( Manager, Type, Size )\ + ((Type *)Fxu_MemFetch( Manager, (Size) * sizeof(Type) )) +#define MEM_FREE_FXU( Manager, Type, Size, Pointer )\ + if ( Pointer ) { Fxu_MemRecycle( Manager, (char *)(Pointer), (Size) * sizeof(Type) ); Pointer = NULL; } +#endif + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/*===== fxu.c ====================================================*/ +extern char * Fxu_MemFetch( Fxu_Matrix * p, int nBytes ); +extern void Fxu_MemRecycle( Fxu_Matrix * p, char * pItem, int nBytes ); +/*===== fxuCreate.c ====================================================*/ +/*===== fxuReduce.c ====================================================*/ +/*===== fxuPrint.c ====================================================*/ +extern void Fxu_MatrixPrint( FILE * pFile, Fxu_Matrix * p ); +extern void Fxu_MatrixPrintDivisorProfile( FILE * pFile, Fxu_Matrix * p ); +/*===== fxuSelect.c ====================================================*/ +extern int Fxu_Select( Fxu_Matrix * p, Fxu_Single ** ppSingle, Fxu_Double ** ppDouble ); +extern int Fxu_SelectSCD( Fxu_Matrix * p, int Weight, Fxu_Var ** ppVar1, Fxu_Var ** ppVar2 ); +/*===== fxuUpdate.c ====================================================*/ +extern void Fxu_Update( Fxu_Matrix * p, Fxu_Single * pSingle, Fxu_Double * pDouble ); +extern void Fxu_UpdateDouble( Fxu_Matrix * p ); +extern void Fxu_UpdateSingle( Fxu_Matrix * p ); +/*===== fxuPair.c ====================================================*/ +extern void Fxu_PairCanonicize( Fxu_Cube ** ppCube1, Fxu_Cube ** ppCube2 ); +extern unsigned Fxu_PairHashKeyArray( Fxu_Matrix * p, int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ); +extern unsigned Fxu_PairHashKey( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, int * pnBase, int * pnLits1, int * pnLits2 ); +extern unsigned Fxu_PairHashKeyMv( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, int * pnBase, int * pnLits1, int * pnLits2 ); +extern int Fxu_PairCompare( Fxu_Pair * pPair1, Fxu_Pair * pPair2 ); +extern void Fxu_PairAllocStorage( Fxu_Var * pVar, int nCubes ); +extern void Fxu_PairFreeStorage( Fxu_Var * pVar ); +extern void Fxu_PairClearStorage( Fxu_Cube * pCube ); +extern Fxu_Pair * Fxu_PairAlloc( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2 ); +extern void Fxu_PairAdd( Fxu_Pair * pPair ); +/*===== fxuSingle.c ====================================================*/ +extern void Fxu_MatrixComputeSingles( Fxu_Matrix * p ); +extern void Fxu_MatrixComputeSinglesOne( Fxu_Matrix * p, Fxu_Var * pVar ); +extern int Fxu_SingleCountCoincidence( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2 ); +/*===== fxuMatrix.c ====================================================*/ +// matrix +extern Fxu_Matrix * Fxu_MatrixAllocate(); +extern void Fxu_MatrixDelete( Fxu_Matrix * p ); +// double-cube divisor +extern void Fxu_MatrixAddDivisor( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2 ); +extern void Fxu_MatrixDelDivisor( Fxu_Matrix * p, Fxu_Double * pDiv ); +// single-cube divisor +extern void Fxu_MatrixAddSingle( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2, int Weight ); +// variable +extern Fxu_Var * Fxu_MatrixAddVar( Fxu_Matrix * p ); +// cube +extern Fxu_Cube * Fxu_MatrixAddCube( Fxu_Matrix * p, Fxu_Var * pVar, int iCube ); +// literal +extern void Fxu_MatrixAddLiteral( Fxu_Matrix * p, Fxu_Cube * pCube, Fxu_Var * pVar ); +extern void Fxu_MatrixDelLiteral( Fxu_Matrix * p, Fxu_Lit * pLit ); +/*===== fxuList.c ====================================================*/ +// matrix -> variable +extern void Fxu_ListMatrixAddVariable( Fxu_Matrix * p, Fxu_Var * pVar ); +extern void Fxu_ListMatrixDelVariable( Fxu_Matrix * p, Fxu_Var * pVar ); +// matrix -> cube +extern void Fxu_ListMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pCube ); +extern void Fxu_ListMatrixDelCube( Fxu_Matrix * p, Fxu_Cube * pCube ); +// matrix -> single +extern void Fxu_ListMatrixAddSingle( Fxu_Matrix * p, Fxu_Single * pSingle ); +extern void Fxu_ListMatrixDelSingle( Fxu_Matrix * p, Fxu_Single * pSingle ); +// table -> divisor +extern void Fxu_ListTableAddDivisor( Fxu_Matrix * p, Fxu_Double * pDiv ); +extern void Fxu_ListTableDelDivisor( Fxu_Matrix * p, Fxu_Double * pDiv ); +// cube -> literal +extern void Fxu_ListCubeAddLiteral( Fxu_Cube * pCube, Fxu_Lit * pLit ); +extern void Fxu_ListCubeDelLiteral( Fxu_Cube * pCube, Fxu_Lit * pLit ); +// var -> literal +extern void Fxu_ListVarAddLiteral( Fxu_Var * pVar, Fxu_Lit * pLit ); +extern void Fxu_ListVarDelLiteral( Fxu_Var * pVar, Fxu_Lit * pLit ); +// divisor -> pair +extern void Fxu_ListDoubleAddPairLast( Fxu_Double * pDiv, Fxu_Pair * pLink ); +extern void Fxu_ListDoubleAddPairFirst( Fxu_Double * pDiv, Fxu_Pair * pLink ); +extern void Fxu_ListDoubleAddPairMiddle( Fxu_Double * pDiv, Fxu_Pair * pSpot, Fxu_Pair * pLink ); +extern void Fxu_ListDoubleDelPair( Fxu_Double * pDiv, Fxu_Pair * pPair ); +/*===== fxuHeapDouble.c ====================================================*/ +extern Fxu_HeapDouble * Fxu_HeapDoubleStart(); +extern void Fxu_HeapDoubleStop( Fxu_HeapDouble * p ); +extern void Fxu_HeapDoublePrint( FILE * pFile, Fxu_HeapDouble * p ); +extern void Fxu_HeapDoubleCheck( Fxu_HeapDouble * p ); +extern void Fxu_HeapDoubleCheckOne( Fxu_HeapDouble * p, Fxu_Double * pDiv ); + +extern void Fxu_HeapDoubleInsert( Fxu_HeapDouble * p, Fxu_Double * pDiv ); +extern void Fxu_HeapDoubleUpdate( Fxu_HeapDouble * p, Fxu_Double * pDiv ); +extern void Fxu_HeapDoubleDelete( Fxu_HeapDouble * p, Fxu_Double * pDiv ); +extern int Fxu_HeapDoubleReadMaxWeight( Fxu_HeapDouble * p ); +extern Fxu_Double * Fxu_HeapDoubleReadMax( Fxu_HeapDouble * p ); +extern Fxu_Double * Fxu_HeapDoubleGetMax( Fxu_HeapDouble * p ); +/*===== fxuHeapSingle.c ====================================================*/ +extern Fxu_HeapSingle * Fxu_HeapSingleStart(); +extern void Fxu_HeapSingleStop( Fxu_HeapSingle * p ); +extern void Fxu_HeapSinglePrint( FILE * pFile, Fxu_HeapSingle * p ); +extern void Fxu_HeapSingleCheck( Fxu_HeapSingle * p ); +extern void Fxu_HeapSingleCheckOne( Fxu_HeapSingle * p, Fxu_Single * pSingle ); + +extern void Fxu_HeapSingleInsert( Fxu_HeapSingle * p, Fxu_Single * pSingle ); +extern void Fxu_HeapSingleUpdate( Fxu_HeapSingle * p, Fxu_Single * pSingle ); +extern void Fxu_HeapSingleDelete( Fxu_HeapSingle * p, Fxu_Single * pSingle ); +extern int Fxu_HeapSingleReadMaxWeight( Fxu_HeapSingle * p ); +extern Fxu_Single * Fxu_HeapSingleReadMax( Fxu_HeapSingle * p ); +extern Fxu_Single * Fxu_HeapSingleGetMax( Fxu_HeapSingle * p ); + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// +#endif + diff --git a/src/opt/fxu/fxuList.c b/src/opt/fxu/fxuList.c new file mode 100644 index 00000000..bb081d80 --- /dev/null +++ b/src/opt/fxu/fxuList.c @@ -0,0 +1,522 @@ +/**CFile**************************************************************** + + FileName [fxuList.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Operations on lists.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuList.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +// matrix -> var + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixAddVariable( Fxu_Matrix * p, Fxu_Var * pLink ) +{ + Fxu_ListVar * pList = &p->lVars; + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pPrev = NULL; + pLink->pNext = NULL; + } + else + { + pLink->pNext = NULL; + pList->pTail->pNext = pLink; + pLink->pPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixDelVariable( Fxu_Matrix * p, Fxu_Var * pLink ) +{ + Fxu_ListVar * pList = &p->lVars; + if ( pList->pHead == pLink ) + pList->pHead = pLink->pNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pPrev; + if ( pLink->pPrev ) + pLink->pPrev->pNext = pLink->pNext; + if ( pLink->pNext ) + pLink->pNext->pPrev = pLink->pPrev; + pList->nItems--; +} + + +// matrix -> cube + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixAddCube( Fxu_Matrix * p, Fxu_Cube * pLink ) +{ + Fxu_ListCube * pList = &p->lCubes; + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pPrev = NULL; + pLink->pNext = NULL; + } + else + { + pLink->pNext = NULL; + pList->pTail->pNext = pLink; + pLink->pPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixDelCube( Fxu_Matrix * p, Fxu_Cube * pLink ) +{ + Fxu_ListCube * pList = &p->lCubes; + if ( pList->pHead == pLink ) + pList->pHead = pLink->pNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pPrev; + if ( pLink->pPrev ) + pLink->pPrev->pNext = pLink->pNext; + if ( pLink->pNext ) + pLink->pNext->pPrev = pLink->pPrev; + pList->nItems--; +} + + +// matrix -> single + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixAddSingle( Fxu_Matrix * p, Fxu_Single * pLink ) +{ + Fxu_ListSingle * pList = &p->lSingles; + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pPrev = NULL; + pLink->pNext = NULL; + } + else + { + pLink->pNext = NULL; + pList->pTail->pNext = pLink; + pLink->pPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListMatrixDelSingle( Fxu_Matrix * p, Fxu_Single * pLink ) +{ + Fxu_ListSingle * pList = &p->lSingles; + if ( pList->pHead == pLink ) + pList->pHead = pLink->pNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pPrev; + if ( pLink->pPrev ) + pLink->pPrev->pNext = pLink->pNext; + if ( pLink->pNext ) + pLink->pNext->pPrev = pLink->pPrev; + pList->nItems--; +} + + +// table -> divisor + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListTableAddDivisor( Fxu_Matrix * p, Fxu_Double * pLink ) +{ + Fxu_ListDouble * pList = &(p->pTable[pLink->Key]); + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pPrev = NULL; + pLink->pNext = NULL; + } + else + { + pLink->pNext = NULL; + pList->pTail->pNext = pLink; + pLink->pPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; + p->nDivs++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListTableDelDivisor( Fxu_Matrix * p, Fxu_Double * pLink ) +{ + Fxu_ListDouble * pList = &(p->pTable[pLink->Key]); + if ( pList->pHead == pLink ) + pList->pHead = pLink->pNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pPrev; + if ( pLink->pPrev ) + pLink->pPrev->pNext = pLink->pNext; + if ( pLink->pNext ) + pLink->pNext->pPrev = pLink->pPrev; + pList->nItems--; + p->nDivs--; +} + + +// cube -> literal + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListCubeAddLiteral( Fxu_Cube * pCube, Fxu_Lit * pLink ) +{ + Fxu_ListLit * pList = &(pCube->lLits); + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pHPrev = NULL; + pLink->pHNext = NULL; + } + else + { + pLink->pHNext = NULL; + pList->pTail->pHNext = pLink; + pLink->pHPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListCubeDelLiteral( Fxu_Cube * pCube, Fxu_Lit * pLink ) +{ + Fxu_ListLit * pList = &(pCube->lLits); + if ( pList->pHead == pLink ) + pList->pHead = pLink->pHNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pHPrev; + if ( pLink->pHPrev ) + pLink->pHPrev->pHNext = pLink->pHNext; + if ( pLink->pHNext ) + pLink->pHNext->pHPrev = pLink->pHPrev; + pList->nItems--; +} + + +// var -> literal + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListVarAddLiteral( Fxu_Var * pVar, Fxu_Lit * pLink ) +{ + Fxu_ListLit * pList = &(pVar->lLits); + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pVPrev = NULL; + pLink->pVNext = NULL; + } + else + { + pLink->pVNext = NULL; + pList->pTail->pVNext = pLink; + pLink->pVPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListVarDelLiteral( Fxu_Var * pVar, Fxu_Lit * pLink ) +{ + Fxu_ListLit * pList = &(pVar->lLits); + if ( pList->pHead == pLink ) + pList->pHead = pLink->pVNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pVPrev; + if ( pLink->pVPrev ) + pLink->pVPrev->pVNext = pLink->pVNext; + if ( pLink->pVNext ) + pLink->pVNext->pVPrev = pLink->pVPrev; + pList->nItems--; +} + + + +// divisor -> pair + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListDoubleAddPairLast( Fxu_Double * pDiv, Fxu_Pair * pLink ) +{ + Fxu_ListPair * pList = &pDiv->lPairs; + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pDPrev = NULL; + pLink->pDNext = NULL; + } + else + { + pLink->pDNext = NULL; + pList->pTail->pDNext = pLink; + pLink->pDPrev = pList->pTail; + pList->pTail = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListDoubleAddPairFirst( Fxu_Double * pDiv, Fxu_Pair * pLink ) +{ + Fxu_ListPair * pList = &pDiv->lPairs; + if ( pList->pHead == NULL ) + { + pList->pHead = pLink; + pList->pTail = pLink; + pLink->pDPrev = NULL; + pLink->pDNext = NULL; + } + else + { + pLink->pDPrev = NULL; + pList->pHead->pDPrev = pLink; + pLink->pDNext = pList->pHead; + pList->pHead = pLink; + } + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [Adds the entry in the middle of the list after the spot.] + + Description [Assumes that spot points to the link, after which the given + link should be added. Spot cannot be NULL or the tail of the list. + Therefore, the head and the tail of the list are not changed.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListDoubleAddPairMiddle( Fxu_Double * pDiv, Fxu_Pair * pSpot, Fxu_Pair * pLink ) +{ + Fxu_ListPair * pList = &pDiv->lPairs; + assert( pSpot ); + assert( pSpot != pList->pTail ); + pLink->pDPrev = pSpot; + pLink->pDNext = pSpot->pDNext; + pLink->pDPrev->pDNext = pLink; + pLink->pDNext->pDPrev = pLink; + pList->nItems++; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListDoubleDelPair( Fxu_Double * pDiv, Fxu_Pair * pLink ) +{ + Fxu_ListPair * pList = &pDiv->lPairs; + if ( pList->pHead == pLink ) + pList->pHead = pLink->pDNext; + if ( pList->pTail == pLink ) + pList->pTail = pLink->pDPrev; + if ( pLink->pDPrev ) + pLink->pDPrev->pDNext = pLink->pDNext; + if ( pLink->pDNext ) + pLink->pDNext->pDPrev = pLink->pDPrev; + pList->nItems--; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_ListDoubleAddPairPlace( Fxu_Double * pDiv, Fxu_Pair * pPair, Fxu_Pair * pPairSpot ) +{ + printf( "Fxu_ListDoubleAddPairPlace() is called!\n" ); +} + + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuMatrix.c b/src/opt/fxu/fxuMatrix.c new file mode 100644 index 00000000..0b732aef --- /dev/null +++ b/src/opt/fxu/fxuMatrix.c @@ -0,0 +1,382 @@ +/**CFile**************************************************************** + + FileName [fxuMatrix.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Procedures to manipulate the sparse matrix.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuMatrix.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +extern unsigned int Cudd_Prime( unsigned int p ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Matrix * Fxu_MatrixAllocate() +{ + Fxu_Matrix * p; + p = ALLOC( Fxu_Matrix, 1 ); + memset( p, 0, sizeof(Fxu_Matrix) ); + p->nTableSize = Cudd_Prime(10000); + p->pTable = ALLOC( Fxu_ListDouble, p->nTableSize ); + memset( p->pTable, 0, sizeof(Fxu_ListDouble) * p->nTableSize ); +#ifndef USE_SYSTEM_MEMORY_MANAGEMENT + { + // get the largest size in bytes for the following structures: + // Fxu_Cube, Fxu_Var, Fxu_Lit, Fxu_Pair, Fxu_Double, Fxu_Single + // (currently, Fxu_Var, Fxu_Pair, Fxu_Double take 10 machine words) + int nSizeMax, nSizeCur; + nSizeMax = -1; + nSizeCur = sizeof(Fxu_Cube); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + nSizeCur = sizeof(Fxu_Var); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + nSizeCur = sizeof(Fxu_Lit); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + nSizeCur = sizeof(Fxu_Pair); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + nSizeCur = sizeof(Fxu_Double); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + nSizeCur = sizeof(Fxu_Single); + if ( nSizeMax < nSizeCur ) + nSizeMax = nSizeCur; + p->pMemMan = Extra_MmFixedStart( nSizeMax ); + } +#endif + p->pHeapDouble = Fxu_HeapDoubleStart(); + p->pHeapSingle = Fxu_HeapSingleStart(); + return p; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixDelete( Fxu_Matrix * p ) +{ + Fxu_HeapDoubleCheck( p->pHeapDouble ); + Fxu_HeapDoubleStop( p->pHeapDouble ); + Fxu_HeapSingleStop( p->pHeapSingle ); + + // delete other things +#ifdef USE_SYSTEM_MEMORY_MANAGEMENT + // this code is not needed when the custom memory manager is used + { + Fxu_Cube * pCube, * pCube2; + Fxu_Var * pVar, * pVar2; + Fxu_Lit * pLit, * pLit2; + Fxu_Double * pDiv, * pDiv2; + Fxu_Single * pSingle, * pSingle2; + Fxu_Pair * pPair, * pPair2; + int i; + // delete the divisors + Fxu_MatrixForEachDoubleSafe( p, pDiv, pDiv2, i ) + { + Fxu_DoubleForEachPairSafe( pDiv, pPair, pPair2 ) + MEM_FREE_FXU( p, Fxu_Pair, 1, pPair ); + MEM_FREE_FXU( p, Fxu_Double, 1, pDiv ); + } + Fxu_MatrixForEachSingleSafe( p, pSingle, pSingle2 ) + MEM_FREE_FXU( p, Fxu_Single, 1, pSingle ); + // delete the entries + Fxu_MatrixForEachCube( p, pCube ) + Fxu_CubeForEachLiteralSafe( pCube, pLit, pLit2 ) + MEM_FREE_FXU( p, Fxu_Lit, 1, pLit ); + // delete the cubes + Fxu_MatrixForEachCubeSafe( p, pCube, pCube2 ) + MEM_FREE_FXU( p, Fxu_Cube, 1, pCube ); + // delete the vars + Fxu_MatrixForEachVariableSafe( p, pVar, pVar2 ) + MEM_FREE_FXU( p, Fxu_Var, 1, pVar ); + } +#else + Extra_MmFixedStop( p->pMemMan, 0 ); +#endif + + FREE( p->pppPairs ); + FREE( p->ppPairs ); + FREE( p->pPairsTemp ); + FREE( p->pTable ); + FREE( p->ppVars ); + FREE( p ); +} + + + +/**Function************************************************************* + + Synopsis [Adds a variable to the matrix.] + + Description [This procedure always adds variables at the end of the matrix. + It assigns the var's node and number. It adds the var to the linked list of + all variables and to the table of all nodes.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Var * Fxu_MatrixAddVar( Fxu_Matrix * p ) +{ + Fxu_Var * pVar; + pVar = MEM_ALLOC_FXU( p, Fxu_Var, 1 ); + memset( pVar, 0, sizeof(Fxu_Var) ); + pVar->iVar = p->lVars.nItems; + p->ppVars[pVar->iVar] = pVar; + Fxu_ListMatrixAddVariable( p, pVar ); + return pVar; +} + +/**Function************************************************************* + + Synopsis [Adds a literal to the matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Cube * Fxu_MatrixAddCube( Fxu_Matrix * p, Fxu_Var * pVar, int iCube ) +{ + Fxu_Cube * pCube; + pCube = MEM_ALLOC_FXU( p, Fxu_Cube, 1 ); + memset( pCube, 0, sizeof(Fxu_Cube) ); + pCube->pVar = pVar; + pCube->iCube = iCube; + Fxu_ListMatrixAddCube( p, pCube ); + return pCube; +} + +/**Function************************************************************* + + Synopsis [Adds a literal to the matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixAddLiteral( Fxu_Matrix * p, Fxu_Cube * pCube, Fxu_Var * pVar ) +{ + Fxu_Lit * pLit; + pLit = MEM_ALLOC_FXU( p, Fxu_Lit, 1 ); + memset( pLit, 0, sizeof(Fxu_Lit) ); + // insert the literal into two linked lists + Fxu_ListCubeAddLiteral( pCube, pLit ); + Fxu_ListVarAddLiteral( pVar, pLit ); + // set the back pointers + pLit->pCube = pCube; + pLit->pVar = pVar; + pLit->iCube = pCube->iCube; + pLit->iVar = pVar->iVar; + // increment the literal counter + p->nEntries++; +} + +/**Function************************************************************* + + Synopsis [Deletes the divisor from the matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixDelDivisor( Fxu_Matrix * p, Fxu_Double * pDiv ) +{ + // delete divisor from the table + Fxu_ListTableDelDivisor( p, pDiv ); + // recycle the divisor + MEM_FREE_FXU( p, Fxu_Double, 1, pDiv ); +} + +/**Function************************************************************* + + Synopsis [Deletes the literal fromthe matrix.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixDelLiteral( Fxu_Matrix * p, Fxu_Lit * pLit ) +{ + // delete the literal + Fxu_ListCubeDelLiteral( pLit->pCube, pLit ); + Fxu_ListVarDelLiteral( pLit->pVar, pLit ); + MEM_FREE_FXU( p, Fxu_Lit, 1, pLit ); + // increment the literal counter + p->nEntries--; +} + + +/**Function************************************************************* + + Synopsis [Creates and adds a single cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixAddSingle( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2, int Weight ) +{ + Fxu_Single * pSingle; + assert( pVar1->iVar < pVar2->iVar ); + pSingle = MEM_ALLOC_FXU( p, Fxu_Single, 1 ); + memset( pSingle, 0, sizeof(Fxu_Single) ); + pSingle->Num = p->lSingles.nItems; + pSingle->Weight = Weight; + pSingle->HNum = 0; + pSingle->pVar1 = pVar1; + pSingle->pVar2 = pVar2; + Fxu_ListMatrixAddSingle( p, pSingle ); + // add to the heap + Fxu_HeapSingleInsert( p->pHeapSingle, pSingle ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixAddDivisor( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2 ) +{ + Fxu_Pair * pPair; + Fxu_Double * pDiv; + int nBase, nLits1, nLits2; + int fFound; + unsigned Key; + + // canonicize the pair + Fxu_PairCanonicize( &pCube1, &pCube2 ); + +/* + // compute the hash key + if ( p->fMvNetwork ) +// if ( 0 ) + { // in case of MV network, if all the values in the cube-free divisor + // belong to the same MV variable, this cube pair is not a divisor + Key = Fxu_PairHashKeyMv( p, pCube1, pCube2, &nBase, &nLits1, &nLits2 ); + if ( Key == 0 ) + return; + } + else +*/ + Key = Fxu_PairHashKey( p, pCube1, pCube2, &nBase, &nLits1, &nLits2 ); + + // create the cube pair + pPair = Fxu_PairAlloc( p, pCube1, pCube2 ); + pPair->nBase = nBase; + pPair->nLits1 = nLits1; + pPair->nLits2 = nLits2; + + // check if the divisor for this pair already exists + fFound = 0; + Key %= p->nTableSize; + Fxu_TableForEachDouble( p, Key, pDiv ) + if ( Fxu_PairCompare( pPair, pDiv->lPairs.pTail ) ) // they are equal + { + fFound = 1; + break; + } + + if ( !fFound ) + { // create the new divisor + pDiv = MEM_ALLOC_FXU( p, Fxu_Double, 1 ); + memset( pDiv, 0, sizeof(Fxu_Double) ); + pDiv->Key = Key; + // set the number of this divisor + pDiv->Num = p->nDivsTotal++; // p->nDivs; + // insert the divisor in the table + Fxu_ListTableAddDivisor( p, pDiv ); + // set the initial cost of the divisor + pDiv->Weight -= pPair->nLits1 + pPair->nLits2; + } + + // link the pair to the cubes + Fxu_PairAdd( pPair ); + // connect the pair and the divisor + pPair->pDiv = pDiv; + Fxu_ListDoubleAddPairLast( pDiv, pPair ); + // update the max number of pairs in a divisor +// if ( p->nPairsMax < pDiv->lPairs.nItems ) +// p->nPairsMax = pDiv->lPairs.nItems; + // update the divisor's weight + pDiv->Weight += pPair->nLits1 + pPair->nLits2 - 1 + pPair->nBase; + if ( fFound ) // update the divisor in the heap + Fxu_HeapDoubleUpdate( p->pHeapDouble, pDiv ); + else // add the new divisor to the heap + Fxu_HeapDoubleInsert( p->pHeapDouble, pDiv ); +} + +/* + { + int piVarsC1[100], piVarsC2[100], nVarsC1, nVarsC2; + Fxu_Double * pDivCur; + Fxu_MatrixGetDoubleVars( p, pDiv, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 ); + pDivCur = Fxu_MatrixFindDouble( p, piVarsC1, piVarsC2, nVarsC1, nVarsC2 ); + assert( pDivCur == pDiv ); + } +*/ + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuPair.c b/src/opt/fxu/fxuPair.c new file mode 100644 index 00000000..be6be5e9 --- /dev/null +++ b/src/opt/fxu/fxuPair.c @@ -0,0 +1,555 @@ +/**CFile**************************************************************** + + FileName [fxuPair.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Operations on cube pairs.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuPair.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define MAX_PRIMES 304 + +static s_Primes[MAX_PRIMES] = +{ + 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, + 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, + 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, + 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, + 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, + 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, + 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, + 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, + 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, + 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, + 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, + 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, + 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, + 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, + 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, + 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, + 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, + 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, + 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, + 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, + 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, + 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, + 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, + 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, + 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, + 1993, 1997, 1999, 2003 +}; + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Find the canonical permutation of two cubes in the pair.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairCanonicize( Fxu_Cube ** ppCube1, Fxu_Cube ** ppCube2 ) +{ + Fxu_Lit * pLit1, * pLit2; + Fxu_Cube * pCubeTemp; + + // walk through the cubes to determine + // the one that has higher first variable + pLit1 = (*ppCube1)->lLits.pHead; + pLit2 = (*ppCube2)->lLits.pHead; + while ( 1 ) + { + if ( pLit1->iVar == pLit2->iVar ) + { + pLit1 = pLit1->pHNext; + pLit2 = pLit2->pHNext; + continue; + } + assert( pLit1 && pLit2 ); // this is true if the covers are SCC-free + if ( pLit1->iVar > pLit2->iVar ) + { // swap the cubes + pCubeTemp = *ppCube1; + *ppCube1 = *ppCube2; + *ppCube2 = pCubeTemp; + } + break; + } +} + +/**Function************************************************************* + + Synopsis [Find the canonical permutation of two cubes in the pair.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairCanonicize2( Fxu_Cube ** ppCube1, Fxu_Cube ** ppCube2 ) +{ + Fxu_Cube * pCubeTemp; + // canonicize the pair by ordering the cubes + if ( (*ppCube1)->iCube > (*ppCube2)->iCube ) + { // swap the cubes + pCubeTemp = *ppCube1; + *ppCube1 = *ppCube2; + *ppCube2 = pCubeTemp; + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Fxu_PairHashKeyArray( Fxu_Matrix * p, int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ) +{ + int Offset1 = 100, Offset2 = 200, i; + unsigned Key; + // compute the hash key + Key = 0; + for ( i = 0; i < nVarsC1; i++ ) + Key ^= s_Primes[Offset1+i] * piVarsC1[i]; + for ( i = 0; i < nVarsC2; i++ ) + Key ^= s_Primes[Offset2+i] * piVarsC2[i]; + return Key; +} + +/**Function************************************************************* + + Synopsis [Computes the hash key of the divisor represented by the pair of cubes.] + + Description [Goes through the variables in both cubes. Skips the identical + ones (this corresponds to making the cubes cube-free). Computes the hash + value of the cubes. Assigns the number of literals in the base and in the + cubes without base.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +unsigned Fxu_PairHashKey( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, + int * pnBase, int * pnLits1, int * pnLits2 ) +{ + int Offset1 = 100, Offset2 = 200; + int nBase, nLits1, nLits2; + Fxu_Lit * pLit1, * pLit2; + unsigned Key; + + // compute the hash key + Key = 0; + nLits1 = 0; + nLits2 = 0; + nBase = 0; + pLit1 = pCube1->lLits.pHead; + pLit2 = pCube2->lLits.pHead; + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->iVar == pLit2->iVar ) + { // ensure cube-free + pLit1 = pLit1->pHNext; + pLit2 = pLit2->pHNext; + // add this literal to the base + nBase++; + } + else if ( pLit1->iVar < pLit2->iVar ) + { + Key ^= s_Primes[Offset1+nLits1] * pLit1->iVar; + pLit1 = pLit1->pHNext; + nLits1++; + } + else + { + Key ^= s_Primes[Offset2+nLits2] * pLit2->iVar; + pLit2 = pLit2->pHNext; + nLits2++; + } + } + else if ( pLit1 && !pLit2 ) + { + Key ^= s_Primes[Offset1+nLits1] * pLit1->iVar; + pLit1 = pLit1->pHNext; + nLits1++; + } + else if ( !pLit1 && pLit2 ) + { + Key ^= s_Primes[Offset2+nLits2] * pLit2->iVar; + pLit2 = pLit2->pHNext; + nLits2++; + } + else + break; + } + *pnBase = nBase; + *pnLits1 = nLits1; + *pnLits2 = nLits2; + return Key; +} + +/**Function************************************************************* + + Synopsis [Compares the two pairs.] + + Description [Returns 1 if the divisors represented by these pairs + are equal.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_PairCompare( Fxu_Pair * pPair1, Fxu_Pair * pPair2 ) +{ + Fxu_Lit * pD1C1, * pD1C2; + Fxu_Lit * pD2C1, * pD2C2; + int TopVar1, TopVar2; + int Code; + + if ( pPair1->nLits1 != pPair2->nLits1 ) + return 0; + if ( pPair1->nLits2 != pPair2->nLits2 ) + return 0; + + pD1C1 = pPair1->pCube1->lLits.pHead; + pD1C2 = pPair1->pCube2->lLits.pHead; + + pD2C1 = pPair2->pCube1->lLits.pHead; + pD2C2 = pPair2->pCube2->lLits.pHead; + + Code = pD1C1? 8: 0; + Code |= pD1C2? 4: 0; + Code |= pD2C1? 2: 0; + Code |= pD2C2? 1: 0; + assert( Code == 15 ); + + while ( 1 ) + { + switch ( Code ) + { + case 0: // -- -- NULL NULL NULL NULL + return 1; + case 1: // -- -1 NULL NULL NULL pD2C2 + return 0; + case 2: // -- 1- NULL NULL pD2C1 NULL + return 0; + case 3: // -- 11 NULL NULL pD2C1 pD2C2 + if ( pD2C1->iVar != pD2C2->iVar ) + return 0; + pD2C1 = pD2C1->pHNext; + pD2C2 = pD2C2->pHNext; + break; + case 4: // -1 -- NULL pD1C2 NULL NULL + return 0; + case 5: // -1 -1 NULL pD1C2 NULL pD2C2 + if ( pD1C2->iVar != pD2C2->iVar ) + return 0; + pD1C2 = pD1C2->pHNext; + pD2C2 = pD2C2->pHNext; + break; + case 6: // -1 1- NULL pD1C2 pD2C1 NULL + return 0; + case 7: // -1 11 NULL pD1C2 pD2C1 pD2C2 + TopVar2 = Fxu_Min( pD2C1->iVar, pD2C2->iVar ); + if ( TopVar2 == pD1C2->iVar ) + { + if ( pD2C1->iVar <= pD2C2->iVar ) + return 0; + pD1C2 = pD1C2->pHNext; + pD2C2 = pD2C2->pHNext; + } + else if ( TopVar2 < pD1C2->iVar ) + { + if ( pD2C1->iVar != pD2C2->iVar ) + return 0; + pD2C1 = pD2C1->pHNext; + pD2C2 = pD2C2->pHNext; + } + else + return 0; + break; + case 8: // 1- -- pD1C1 NULL NULL NULL + return 0; + case 9: // 1- -1 pD1C1 NULL NULL pD2C2 + return 0; + case 10: // 1- 1- pD1C1 NULL pD2C1 NULL + if ( pD1C1->iVar != pD2C1->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD2C1 = pD2C1->pHNext; + break; + case 11: // 1- 11 pD1C1 NULL pD2C1 pD2C2 + TopVar2 = Fxu_Min( pD2C1->iVar, pD2C2->iVar ); + if ( TopVar2 == pD1C1->iVar ) + { + if ( pD2C1->iVar >= pD2C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD2C1 = pD2C1->pHNext; + } + else if ( TopVar2 < pD1C1->iVar ) + { + if ( pD2C1->iVar != pD2C2->iVar ) + return 0; + pD2C1 = pD2C1->pHNext; + pD2C2 = pD2C2->pHNext; + } + else + return 0; + break; + case 12: // 11 -- pD1C1 pD1C2 NULL NULL + if ( pD1C1->iVar != pD1C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD1C2 = pD1C2->pHNext; + break; + case 13: // 11 -1 pD1C1 pD1C2 NULL pD2C2 + TopVar1 = Fxu_Min( pD1C1->iVar, pD1C2->iVar ); + if ( TopVar1 == pD2C2->iVar ) + { + if ( pD1C1->iVar <= pD1C2->iVar ) + return 0; + pD1C2 = pD1C2->pHNext; + pD2C2 = pD2C2->pHNext; + } + else if ( TopVar1 < pD2C2->iVar ) + { + if ( pD1C1->iVar != pD1C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD1C2 = pD1C2->pHNext; + } + else + return 0; + break; + case 14: // 11 1- pD1C1 pD1C2 pD2C1 NULL + TopVar1 = Fxu_Min( pD1C1->iVar, pD1C2->iVar ); + if ( TopVar1 == pD2C1->iVar ) + { + if ( pD1C1->iVar >= pD1C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD2C1 = pD2C1->pHNext; + } + else if ( TopVar1 < pD2C1->iVar ) + { + if ( pD1C1->iVar != pD1C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD1C2 = pD1C2->pHNext; + } + else + return 0; + break; + case 15: // 11 11 pD1C1 pD1C2 pD2C1 pD2C2 + TopVar1 = Fxu_Min( pD1C1->iVar, pD1C2->iVar ); + TopVar2 = Fxu_Min( pD2C1->iVar, pD2C2->iVar ); + if ( TopVar1 == TopVar2 ) + { + if ( pD1C1->iVar == pD1C2->iVar ) + { + if ( pD2C1->iVar != pD2C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD1C2 = pD1C2->pHNext; + pD2C1 = pD2C1->pHNext; + pD2C2 = pD2C2->pHNext; + } + else + { + if ( pD2C1->iVar == pD2C2->iVar ) + return 0; + if ( pD1C1->iVar < pD1C2->iVar ) + { + if ( pD2C1->iVar > pD2C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD2C1 = pD2C1->pHNext; + } + else + { + if ( pD2C1->iVar < pD2C2->iVar ) + return 0; + pD1C2 = pD1C2->pHNext; + pD2C2 = pD2C2->pHNext; + } + } + } + else if ( TopVar1 < TopVar2 ) + { + if ( pD1C1->iVar != pD1C2->iVar ) + return 0; + pD1C1 = pD1C1->pHNext; + pD1C2 = pD1C2->pHNext; + } + else + { + if ( pD2C1->iVar != pD2C2->iVar ) + return 0; + pD2C1 = pD2C1->pHNext; + pD2C2 = pD2C2->pHNext; + } + break; + default: + assert( 0 ); + break; + } + + Code = pD1C1? 8: 0; + Code |= pD1C2? 4: 0; + Code |= pD2C1? 2: 0; + Code |= pD2C2? 1: 0; + } + return 1; +} + + +/**Function************************************************************* + + Synopsis [Allocates the storage for cubes pairs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairAllocStorage( Fxu_Var * pVar, int nCubes ) +{ + int k; +// assert( pVar->nCubes == 0 ); + pVar->nCubes = nCubes; + // allocate memory for all the pairs + pVar->ppPairs = ALLOC( Fxu_Pair **, nCubes ); + pVar->ppPairs[0] = ALLOC( Fxu_Pair *, nCubes * nCubes ); + memset( pVar->ppPairs[0], 0, sizeof(Fxu_Pair *) * nCubes * nCubes ); + for ( k = 1; k < nCubes; k++ ) + pVar->ppPairs[k] = pVar->ppPairs[k-1] + nCubes; +} + +/**Function************************************************************* + + Synopsis [Clears all pairs associated with this cube.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairClearStorage( Fxu_Cube * pCube ) +{ + Fxu_Var * pVar; + int i; + pVar = pCube->pVar; + for ( i = 0; i < pVar->nCubes; i++ ) + { + pVar->ppPairs[pCube->iCube][i] = NULL; + pVar->ppPairs[i][pCube->iCube] = NULL; + } +} + +/**Function************************************************************* + + Synopsis [Clears all pairs associated with this cube.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairFreeStorage( Fxu_Var * pVar ) +{ + if ( pVar->ppPairs ) + { + FREE( pVar->ppPairs[0] ); + FREE( pVar->ppPairs ); + } +} + +/**Function************************************************************* + + Synopsis [Adds the pair to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Pair * Fxu_PairAlloc( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2 ) +{ + Fxu_Pair * pPair; + assert( pCube1->pVar == pCube2->pVar ); + pPair = MEM_ALLOC_FXU( p, Fxu_Pair, 1 ); + memset( pPair, 0, sizeof(Fxu_Pair) ); + pPair->pCube1 = pCube1; + pPair->pCube2 = pCube2; + pPair->iCube1 = pCube1->iCube; + pPair->iCube2 = pCube2->iCube; + return pPair; +} + +/**Function************************************************************* + + Synopsis [Adds the pair to storage.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_PairAdd( Fxu_Pair * pPair ) +{ + Fxu_Var * pVar; + + pVar = pPair->pCube1->pVar; + assert( pVar == pPair->pCube2->pVar ); + + pVar->ppPairs[pPair->iCube1][pPair->iCube2] = pPair; + pVar->ppPairs[pPair->iCube2][pPair->iCube1] = pPair; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuPrint.c b/src/opt/fxu/fxuPrint.c new file mode 100644 index 00000000..2d25c0e9 --- /dev/null +++ b/src/opt/fxu/fxuPrint.c @@ -0,0 +1,195 @@ +/**CFile**************************************************************** + + FileName [fxuPrint.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Various printing procedures.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuPrint.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixPrint( FILE * pFile, Fxu_Matrix * p ) +{ + Fxu_Var * pVar; + Fxu_Cube * pCube; + Fxu_Double * pDiv; + Fxu_Single * pSingle; + Fxu_Lit * pLit; + Fxu_Pair * pPair; + int i, LastNum; + int fStdout; + + fStdout = 1; + if ( pFile == NULL ) + { + pFile = fopen( "matrix.txt", "w" ); + fStdout = 0; + } + + fprintf( pFile, "Matrix has %d vars, %d cubes, %d literals, %d divisors.\n", + p->lVars.nItems, p->lCubes.nItems, p->nEntries, p->nDivs ); + fprintf( pFile, "Divisors selected so far: single = %d, double = %d.\n", + p->nDivs1, p->nDivs2 ); + fprintf( pFile, "\n" ); + + // print the numbers on top of the matrix + for ( i = 0; i < 12; i++ ) + fprintf( pFile, " " ); + Fxu_MatrixForEachVariable( p, pVar ) + fprintf( pFile, "%d", pVar->iVar % 10 ); + fprintf( pFile, "\n" ); + + // print the rows + Fxu_MatrixForEachCube( p, pCube ) + { + fprintf( pFile, "%4d", pCube->iCube ); + fprintf( pFile, " " ); + fprintf( pFile, "%4d", pCube->pVar->iVar ); + fprintf( pFile, " " ); + + // print the literals + LastNum = -1; + Fxu_CubeForEachLiteral( pCube, pLit ) + { + for ( i = LastNum + 1; i < pLit->pVar->iVar; i++ ) + fprintf( pFile, "." ); + fprintf( pFile, "1" ); + LastNum = i; + } + for ( i = LastNum + 1; i < p->lVars.nItems; i++ ) + fprintf( pFile, "." ); + fprintf( pFile, "\n" ); + } + fprintf( pFile, "\n" ); + + // print the double-cube divisors + fprintf( pFile, "The double divisors are:\n" ); + Fxu_MatrixForEachDouble( p, pDiv, i ) + { + fprintf( pFile, "Divisor #%3d (lit=%d,%d) (w=%2d): ", + pDiv->Num, pDiv->lPairs.pHead->nLits1, + pDiv->lPairs.pHead->nLits2, pDiv->Weight ); + Fxu_DoubleForEachPair( pDiv, pPair ) + fprintf( pFile, " <%d, %d> (b=%d)", + pPair->pCube1->iCube, pPair->pCube2->iCube, pPair->nBase ); + fprintf( pFile, "\n" ); + } + fprintf( pFile, "\n" ); + + // print the divisors associated with each cube + fprintf( pFile, "The cubes are:\n" ); + Fxu_MatrixForEachCube( p, pCube ) + { + fprintf( pFile, "Cube #%3d: ", pCube->iCube ); + if ( pCube->pVar->ppPairs ) + Fxu_CubeForEachPair( pCube, pPair, i ) + fprintf( pFile, " <%d %d> (d=%d) (b=%d)", + pPair->iCube1, pPair->iCube2, pPair->pDiv->Num, pPair->nBase ); + fprintf( pFile, "\n" ); + } + fprintf( pFile, "\n" ); + + // print the single-cube divisors + fprintf( pFile, "The single divisors are:\n" ); + Fxu_MatrixForEachSingle( p, pSingle ) + { + fprintf( pFile, "Single-cube divisor #%5d: Var1 = %4d. Var2 = %4d. Weight = %2d\n", + pSingle->Num, pSingle->pVar1->iVar, pSingle->pVar2->iVar, pSingle->Weight ); + } + fprintf( pFile, "\n" ); + +/* + { + int Index; + fprintf( pFile, "Distribution of divisors in the hash table:\n" ); + for ( Index = 0; Index < p->nTableSize; Index++ ) + fprintf( pFile, " %d", p->pTable[Index].nItems ); + fprintf( pFile, "\n" ); + } +*/ + if ( !fStdout ) + fclose( pFile ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixPrintDivisorProfile( FILE * pFile, Fxu_Matrix * p ) +{ + Fxu_Double * pDiv; + int WeightMax; + int * pProfile; + int Counter1; // the number of -1 weight + int CounterL; // the number of less than -1 weight + int i; + + WeightMax = Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ); + pProfile = ALLOC( int, (WeightMax + 1) ); + memset( pProfile, 0, sizeof(int) * (WeightMax + 1) ); + + Counter1 = 0; + CounterL = 0; + Fxu_MatrixForEachDouble( p, pDiv, i ) + { + assert( pDiv->Weight <= WeightMax ); + if ( pDiv->Weight == -1 ) + Counter1++; + else if ( pDiv->Weight < 0 ) + CounterL++; + else + pProfile[ pDiv->Weight ]++; + } + + fprintf( pFile, "The double divisors profile:\n" ); + fprintf( pFile, "Weight < -1 divisors = %6d\n", CounterL ); + fprintf( pFile, "Weight -1 divisors = %6d\n", Counter1 ); + for ( i = 0; i <= WeightMax; i++ ) + if ( pProfile[i] ) + fprintf( pFile, "Weight %3d divisors = %6d\n", i, pProfile[i] ); + fprintf( pFile, "End of divisor profile printout\n" ); + FREE( pProfile ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuReduce.c b/src/opt/fxu/fxuReduce.c new file mode 100644 index 00000000..652d807b --- /dev/null +++ b/src/opt/fxu/fxuReduce.c @@ -0,0 +1,194 @@ +/**CFile**************************************************************** + + FileName [fxuReduce.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Procedures to reduce the number of considered cube pairs.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuReduce.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "abc.h" +#include "fxuInt.h" +#include "fxu.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Precomputes the pairs to use for creating two-cube divisors.] + + Description [This procedure takes the matrix with variables and cubes + allocated (p), the original covers of the nodes (i-sets) and their number + (ppCovers,nCovers). The maximum number of pairs to compute and the total + number of pairs in existence. This procedure adds to the storage of + divisors exactly the given number of pairs (nPairsMax) while taking + first those pairs that have the smallest number of literals in their + cube-free form.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax ) +{ + unsigned char * pnLitsDiff; // storage for the counters of diff literals + int * pnPairCounters; // the counters of pairs for each number of diff literals + Fxu_Cube * pCubeFirst, * pCubeLast; + Fxu_Cube * pCube1, * pCube2; + Fxu_Var * pVar; + int nCubes, nBitsMax, nSum; + int CutOffNum, CutOffQuant; + int iPair, iQuant, k, c; + int clk = clock(); + char * pSopCover; + int nFanins; + + assert( nPairsMax < nPairsTotal ); + + // allocate storage for counter of diffs + pnLitsDiff = ALLOC( unsigned char, nPairsTotal ); + // go through the covers and precompute the distances between the pairs + iPair = 0; + nBitsMax = -1; + for ( c = 0; c < vCovers->nSize; c++ ) + if ( pSopCover = vCovers->pArray[c] ) + { + nFanins = Abc_SopGetVarNum(pSopCover); + // precompute the differences + Fxu_CountPairDiffs( pSopCover, pnLitsDiff + iPair ); + // update the counter + nCubes = Abc_SopGetCubeNum( pSopCover ); + iPair += nCubes * (nCubes - 1) / 2; + if ( nBitsMax < nFanins ) + nBitsMax = nFanins; + } + assert( iPair == nPairsTotal ); + + // allocate storage for counters of cube pairs by difference + pnPairCounters = ALLOC( int, 2 * nBitsMax ); + memset( pnPairCounters, 0, sizeof(int) * 2 * nBitsMax ); + // count the number of different pairs + for ( k = 0; k < nPairsTotal; k++ ) + pnPairCounters[ pnLitsDiff[k] ]++; + // determine what pairs to take starting from the lower + // so that there would be exactly pPairsMax pairs + assert( pnPairCounters[0] == 0 ); // otherwise, covers are not dup-free + assert( pnPairCounters[1] == 0 ); // otherwise, covers are not SCC-free + nSum = 0; + for ( k = 0; k < 2 * nBitsMax; k++ ) + { + nSum += pnPairCounters[k]; + if ( nSum >= nPairsMax ) + { + CutOffNum = k; + CutOffQuant = pnPairCounters[k] - (nSum - nPairsMax); + break; + } + } + FREE( pnPairCounters ); + + // set to 0 all the pairs above the cut-off number and quantity + iQuant = 0; + iPair = 0; + for ( k = 0; k < nPairsTotal; k++ ) + if ( pnLitsDiff[k] > CutOffNum ) + pnLitsDiff[k] = 0; + else if ( pnLitsDiff[k] == CutOffNum ) + { + if ( iQuant++ >= CutOffQuant ) + pnLitsDiff[k] = 0; + else + iPair++; + } + else + iPair++; + assert( iPair == nPairsMax ); + + // collect the corresponding pairs and add the divisors + iPair = 0; + for ( c = 0; c < vCovers->nSize; c++ ) + if ( pSopCover = vCovers->pArray[c] ) + { + // get the var + pVar = p->ppVars[2*c+1]; + // get the first cube + pCubeFirst = pVar->pFirst; + // get the last cube + pCubeLast = pCubeFirst; + for ( k = 0; k < pVar->nCubes; k++ ) + pCubeLast = pCubeLast->pNext; + assert( pCubeLast == NULL || pCubeLast->pVar != pVar ); + + // go through the cube pairs + for ( pCube1 = pCubeFirst; pCube1 != pCubeLast; pCube1 = pCube1->pNext ) + for ( pCube2 = pCube1->pNext; pCube2 != pCubeLast; pCube2 = pCube2->pNext ) + if ( pnLitsDiff[iPair++] ) + { // create the divisors for this pair + Fxu_MatrixAddDivisor( p, pCube1, pCube2 ); + } + } + assert( iPair == nPairsTotal ); + FREE( pnLitsDiff ); +//PRT( "Preprocess", clock() - clk ); + return 1; +} + + +/**Function************************************************************* + + Synopsis [Counts the differences in each cube pair in the cover.] + + Description [Takes the cover (pCover) and the array where the + diff counters go (pDiffs). The array pDiffs should have as many + entries as there are different pairs of cubes in the cover: n(n-1)/2. + Fills out the array pDiffs with the following info: For each cube + pair, included in the array is the number of literals in both cubes + after they are made cube free.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] ) +{ + char * pCube1, * pCube2; + int nOnes, nCubePairs, nFanins, v; + nCubePairs = 0; + nFanins = Abc_SopGetVarNum(pCover); + Abc_SopForEachCube( pCover, nFanins, pCube1 ) + Abc_SopForEachCube( pCube1, nFanins, pCube2 ) + { + if ( pCube1 == pCube2 ) + continue; + nOnes = 0; + for ( v = 0; v < nFanins; v++ ) + nOnes += (pCube1[v] != pCube2[v]); + pDiffs[nCubePairs++] = nOnes; + } + return 1; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuSelect.c b/src/opt/fxu/fxuSelect.c new file mode 100644 index 00000000..b56407a9 --- /dev/null +++ b/src/opt/fxu/fxuSelect.c @@ -0,0 +1,603 @@ +/**CFile**************************************************************** + + FileName [fxuSelect.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Procedures to select the best divisor/complement pair.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuSelect.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define MAX_SIZE_LOOKAHEAD 20 + +static int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar ); + +static Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle ); +static Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble ); +static Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble ); + +Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, + int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ); +void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, + int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 ); + + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Selects the best pair (Single,Double) and returns their weight.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_Select( Fxu_Matrix * p, Fxu_Single ** ppSingle, Fxu_Double ** ppDouble ) +{ + // the top entries + Fxu_Single * pSingles[MAX_SIZE_LOOKAHEAD]; + Fxu_Double * pDoubles[MAX_SIZE_LOOKAHEAD]; + // the complements + Fxu_Double * pSCompl[MAX_SIZE_LOOKAHEAD]; + Fxu_Single * pDComplS[MAX_SIZE_LOOKAHEAD]; + Fxu_Double * pDComplD[MAX_SIZE_LOOKAHEAD]; + Fxu_Pair * pPair; + int nSingles; + int nDoubles; + int i; + int WeightBest; + int WeightCur; + int iNum, fBestS; + + // collect the top entries from the queues + for ( nSingles = 0; nSingles < MAX_SIZE_LOOKAHEAD; nSingles++ ) + { + pSingles[nSingles] = Fxu_HeapSingleGetMax( p->pHeapSingle ); + if ( pSingles[nSingles] == NULL ) + break; + } + // put them back into the queue + for ( i = 0; i < nSingles; i++ ) + if ( pSingles[i] ) + Fxu_HeapSingleInsert( p->pHeapSingle, pSingles[i] ); + + // the same for doubles + // collect the top entries from the queues + for ( nDoubles = 0; nDoubles < MAX_SIZE_LOOKAHEAD; nDoubles++ ) + { + pDoubles[nDoubles] = Fxu_HeapDoubleGetMax( p->pHeapDouble ); + if ( pDoubles[nDoubles] == NULL ) + break; + } + // put them back into the queue + for ( i = 0; i < nDoubles; i++ ) + if ( pDoubles[i] ) + Fxu_HeapDoubleInsert( p->pHeapDouble, pDoubles[i] ); + + // for each single, find the complement double (if any) + for ( i = 0; i < nSingles; i++ ) + if ( pSingles[i] ) + pSCompl[i] = Fxu_MatrixFindComplementSingle( p, pSingles[i] ); + + // for each double, find the complement single or double (if any) + for ( i = 0; i < nDoubles; i++ ) + if ( pDoubles[i] ) + { + pPair = pDoubles[i]->lPairs.pHead; + if ( pPair->nLits1 == 1 && pPair->nLits2 == 1 ) + { + pDComplS[i] = Fxu_MatrixFindComplementDouble2( p, pDoubles[i] ); + pDComplD[i] = NULL; + } +// else if ( pPair->nLits1 == 2 && pPair->nLits2 == 2 ) +// { +// pDComplS[i] = NULL; +// pDComplD[i] = Fxu_MatrixFindComplementDouble4( p, pDoubles[i] ); +// } + else + { + pDComplS[i] = NULL; + pDComplD[i] = NULL; + } + } + + // select the best pair + WeightBest = -1; + for ( i = 0; i < nSingles; i++ ) + { + WeightCur = pSingles[i]->Weight; + if ( pSCompl[i] ) + { + // add the weight of the double + WeightCur += pSCompl[i]->Weight; + // there is no need to implement this double, so... + pPair = pSCompl[i]->lPairs.pHead; + WeightCur += pPair->nLits1 + pPair->nLits2; + } + if ( WeightBest < WeightCur ) + { + WeightBest = WeightCur; + *ppSingle = pSingles[i]; + *ppDouble = pSCompl[i]; + fBestS = 1; + iNum = i; + } + } + for ( i = 0; i < nDoubles; i++ ) + { + WeightCur = pDoubles[i]->Weight; + if ( pDComplS[i] ) + { + // add the weight of the single + WeightCur += pDComplS[i]->Weight; + // there is no need to implement this double, so... + pPair = pDoubles[i]->lPairs.pHead; + WeightCur += pPair->nLits1 + pPair->nLits2; + } + if ( WeightBest < WeightCur ) + { + WeightBest = WeightCur; + *ppSingle = pDComplS[i]; + *ppDouble = pDoubles[i]; + fBestS = 0; + iNum = i; + } + } +/* + // print the statistics + printf( "\n" ); + for ( i = 0; i < nSingles; i++ ) + { + printf( "Single #%d: Weight = %3d. ", i, pSingles[i]->Weight ); + printf( "Compl: " ); + if ( pSCompl[i] == NULL ) + printf( "None." ); + else + printf( "D Weight = %3d Sum = %3d", + pSCompl[i]->Weight, pSCompl[i]->Weight + pSingles[i]->Weight ); + printf( "\n" ); + } + printf( "\n" ); + for ( i = 0; i < nDoubles; i++ ) + { + printf( "Double #%d: Weight = %3d. ", i, pDoubles[i]->Weight ); + printf( "Compl: " ); + if ( pDComplS[i] == NULL && pDComplD[i] == NULL ) + printf( "None." ); + else if ( pDComplS[i] ) + printf( "S Weight = %3d Sum = %3d", + pDComplS[i]->Weight, pDComplS[i]->Weight + pDoubles[i]->Weight ); + else if ( pDComplD[i] ) + printf( "D Weight = %3d Sum = %3d", + pDComplD[i]->Weight, pDComplD[i]->Weight + pDoubles[i]->Weight ); + printf( "\n" ); + } + if ( WeightBest == -1 ) + printf( "Selected NONE\n" ); + else + { + printf( "Selected = %s. ", fBestS? "S": "D" ); + printf( "Number = %d. ", iNum ); + printf( "Weight = %d.\n", WeightBest ); + } + printf( "\n" ); +*/ + return WeightBest; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle ) +{ +// int * pValue2Node = p->pValue2Node; + int iVar1, iVar2; + int iVar1C, iVar2C; + // get the variables of this single div + iVar1 = pSingle->pVar1->iVar; + iVar2 = pSingle->pVar2->iVar; + iVar1C = Fxu_MatrixFindComplement( p, iVar1 ); + iVar2C = Fxu_MatrixFindComplement( p, iVar2 ); + if ( iVar1C == -1 || iVar2C == -1 ) + return NULL; + assert( iVar1C < iVar2C ); + return Fxu_MatrixFindDouble( p, &iVar1C, &iVar2C, 1, 1 ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble ) +{ +// int * pValue2Node = p->pValue2Node; + int piVarsC1[10], piVarsC2[10]; + int nVarsC1, nVarsC2; + int iVar1, iVar2, iVarTemp; + int iVar1C, iVar2C; + Fxu_Single * pSingle; + + // get the variables of this double div + Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 ); + assert( nVarsC1 == 1 ); + assert( nVarsC2 == 1 ); + iVar1 = piVarsC1[0]; + iVar2 = piVarsC2[0]; + assert( iVar1 < iVar2 ); + + iVar1C = Fxu_MatrixFindComplement( p, iVar1 ); + iVar2C = Fxu_MatrixFindComplement( p, iVar2 ); + if ( iVar1C == -1 || iVar2C == -1 ) + return NULL; + + // go through the queque and find this one +// assert( iVar1C < iVar2C ); + if ( iVar1C > iVar2C ) + { + iVarTemp = iVar1C; + iVar1C = iVar2C; + iVar2C = iVarTemp; + } + + Fxu_MatrixForEachSingle( p, pSingle ) + if ( pSingle->pVar1->iVar == iVar1C && pSingle->pVar2->iVar == iVar2C ) + return pSingle; + return NULL; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble ) +{ +// int * pValue2Node = p->pValue2Node; + int piVarsC1[10], piVarsC2[10]; + int nVarsC1, nVarsC2; + int iVar11, iVar12, iVar21, iVar22; + int iVar11C, iVar12C, iVar21C, iVar22C; + int RetValue; + + // get the variables of this double div + Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 ); + assert( nVarsC1 == 2 && nVarsC2 == 2 ); + + iVar11 = piVarsC1[0]; + iVar12 = piVarsC1[1]; + iVar21 = piVarsC2[0]; + iVar22 = piVarsC2[1]; + assert( iVar11 < iVar21 ); + + iVar11C = Fxu_MatrixFindComplement( p, iVar11 ); + iVar12C = Fxu_MatrixFindComplement( p, iVar12 ); + iVar21C = Fxu_MatrixFindComplement( p, iVar21 ); + iVar22C = Fxu_MatrixFindComplement( p, iVar22 ); + if ( iVar11C == -1 || iVar12C == -1 || iVar21C == -1 || iVar22C == -1 ) + return NULL; + if ( iVar11C != iVar21 || iVar12C != iVar22 || + iVar21C != iVar11 || iVar22C != iVar12 ) + return NULL; + + // a'b' + ab => a'b + ab' + // a'b + ab' => a'b' + ab + // swap the second pair in each cube + RetValue = piVarsC1[1]; + piVarsC1[1] = piVarsC2[1]; + piVarsC2[1] = RetValue; + + return Fxu_MatrixFindDouble( p, piVarsC1, piVarsC2, 2, 2 ); +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar ) +{ + return iVar ^ 1; +/* +// int * pValue2Node = p->pValue2Node; + int iVarC; + int iNode; + int Beg, End; + + // get the nodes + iNode = pValue2Node[iVar]; + // get the first node with the same var + for ( Beg = iVar; Beg >= 0; Beg-- ) + if ( pValue2Node[Beg] != iNode ) + { + Beg++; + break; + } + // get the last node with the same var + for ( End = iVar; ; End++ ) + if ( pValue2Node[End] != iNode ) + { + End--; + break; + } + + // if one of the vars is not binary, quit + if ( End - Beg > 1 ) + return -1; + + // get the complements + if ( iVar == Beg ) + iVarC = End; + else if ( iVar == End ) + iVarC = Beg; + else + { + assert( 0 ); + } + return iVarC; +*/ +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, + int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 ) +{ + Fxu_Pair * pPair; + Fxu_Lit * pLit1, * pLit2; + int nLits1, nLits2; + + // get the first pair + pPair = pDouble->lPairs.pHead; + // init the parameters + nLits1 = 0; + nLits2 = 0; + pLit1 = pPair->pCube1->lLits.pHead; + pLit2 = pPair->pCube2->lLits.pHead; + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->iVar == pLit2->iVar ) + { // ensure cube-free + pLit1 = pLit1->pHNext; + pLit2 = pLit2->pHNext; + } + else if ( pLit1->iVar < pLit2->iVar ) + { + piVarsC1[nLits1++] = pLit1->iVar; + pLit1 = pLit1->pHNext; + } + else + { + piVarsC2[nLits2++] = pLit2->iVar; + pLit2 = pLit2->pHNext; + } + } + else if ( pLit1 && !pLit2 ) + { + piVarsC1[nLits1++] = pLit1->iVar; + pLit1 = pLit1->pHNext; + } + else if ( !pLit1 && pLit2 ) + { + piVarsC2[nLits2++] = pLit2->iVar; + pLit2 = pLit2->pHNext; + } + else + break; + } + *pnVarsC1 = nLits1; + *pnVarsC2 = nLits2; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, + int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 ) +{ + int piVarsC1_[100], piVarsC2_[100]; + int nVarsC1_, nVarsC2_, i; + Fxu_Double * pDouble; + Fxu_Pair * pPair; + unsigned Key; + + assert( nVarsC1 > 0 ); + assert( nVarsC2 > 0 ); + assert( piVarsC1[0] < piVarsC2[0] ); + + // get the hash key + Key = Fxu_PairHashKeyArray( p, piVarsC1, piVarsC2, nVarsC1, nVarsC2 ); + + // check if the divisor for this pair already exists + Key %= p->nTableSize; + Fxu_TableForEachDouble( p, Key, pDouble ) + { + pPair = pDouble->lPairs.pHead; + if ( pPair->nLits1 != nVarsC1 ) + continue; + if ( pPair->nLits2 != nVarsC2 ) + continue; + // get the cubes of this divisor + Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1_, piVarsC2_, &nVarsC1_, &nVarsC2_ ); + // compare lits of the first cube + for ( i = 0; i < nVarsC1; i++ ) + if ( piVarsC1[i] != piVarsC1_[i] ) + break; + if ( i != nVarsC1 ) + continue; + // compare lits of the second cube + for ( i = 0; i < nVarsC2; i++ ) + if ( piVarsC2[i] != piVarsC2_[i] ) + break; + if ( i != nVarsC2 ) + continue; + return pDouble; + } + return NULL; +} + + + + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_SelectSCD( Fxu_Matrix * p, int WeightLimit, Fxu_Var ** ppVar1, Fxu_Var ** ppVar2 ) +{ +// int * pValue2Node = p->pValue2Node; + Fxu_Var * pVar1; + Fxu_Var * pVar2, * pVarTemp; + Fxu_Lit * pLitV, * pLitH; + int Coin; + int CounterAll; + int CounterTest; + int WeightCur; + int WeightBest; + + CounterAll = 0; + CounterTest = 0; + + WeightBest = -10; + + // iterate through the columns in the matrix + Fxu_MatrixForEachVariable( p, pVar1 ) + { + // start collecting the affected vars + Fxu_MatrixRingVarsStart( p ); + + // go through all the literals of this variable + for ( pLitV = pVar1->lLits.pHead; pLitV; pLitV = pLitV->pVNext ) + { + // for this literal, go through all the horizontal literals + for ( pLitH = pLitV->pHNext; pLitH; pLitH = pLitH->pHNext ) + { + // get another variable + pVar2 = pLitH->pVar; + CounterAll++; + // skip the var if it is already used + if ( pVar2->pOrder ) + continue; + // skip the var if it belongs to the same node +// if ( pValue2Node[pVar1->iVar] == pValue2Node[pVar2->iVar] ) +// continue; + // collect the var + Fxu_MatrixRingVarsAdd( p, pVar2 ); + } + } + // stop collecting the selected vars + Fxu_MatrixRingVarsStop( p ); + + // iterate through the selected vars + Fxu_MatrixForEachVarInRing( p, pVar2 ) + { + CounterTest++; + + // count the coincidence + Coin = Fxu_SingleCountCoincidence( p, pVar1, pVar2 ); + assert( Coin > 0 ); + + // get the new weight + WeightCur = Coin - 2; + + // compare the weights + if ( WeightBest < WeightCur ) + { + WeightBest = WeightCur; + *ppVar1 = pVar1; + *ppVar2 = pVar2; + } + } + // unmark the vars + Fxu_MatrixForEachVarInRingSafe( p, pVar2, pVarTemp ) + pVar2->pOrder = NULL; + Fxu_MatrixRingVarsReset( p ); + } + +// if ( WeightBest == WeightLimit ) +// return -1; + return WeightBest; +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuSingle.c b/src/opt/fxu/fxuSingle.c new file mode 100644 index 00000000..5af5c341 --- /dev/null +++ b/src/opt/fxu/fxuSingle.c @@ -0,0 +1,166 @@ +/**CFile**************************************************************** + + FileName [fxuSingle.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Procedures to compute the set of single-cube divisors.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuSingle.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Computes and adds all single-cube divisors to storage.] + + Description [This procedure should be called once when the matrix is + already contructed before the process of logic extraction begins..] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixComputeSingles( Fxu_Matrix * p ) +{ + Fxu_Var * pVar; + // iterate through the columns in the matrix + Fxu_MatrixForEachVariable( p, pVar ) + Fxu_MatrixComputeSinglesOne( p, pVar ); +} + +/**Function************************************************************* + + Synopsis [Adds the single-cube divisors associated with a new column.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_MatrixComputeSinglesOne( Fxu_Matrix * p, Fxu_Var * pVar ) +{ +// int * pValue2Node = p->pValue2Node; + Fxu_Lit * pLitV, * pLitH; + Fxu_Var * pVar2; + int Coin; +// int CounterAll; +// int CounterTest; + int WeightCur; + + // start collecting the affected vars + Fxu_MatrixRingVarsStart( p ); + // go through all the literals of this variable + for ( pLitV = pVar->lLits.pHead; pLitV; pLitV = pLitV->pVNext ) + // for this literal, go through all the horizontal literals + for ( pLitH = pLitV->pHPrev; pLitH; pLitH = pLitH->pHPrev ) + { + // get another variable + pVar2 = pLitH->pVar; +// CounterAll++; + // skip the var if it is already used + if ( pVar2->pOrder ) + continue; + // skip the var if it belongs to the same node +// if ( pValue2Node[pVar->iVar] == pValue2Node[pVar2->iVar] ) +// continue; + // collect the var + Fxu_MatrixRingVarsAdd( p, pVar2 ); + } + // stop collecting the selected vars + Fxu_MatrixRingVarsStop( p ); + + // iterate through the selected vars + Fxu_MatrixForEachVarInRing( p, pVar2 ) + { +// CounterTest++; + // count the coincidence + Coin = Fxu_SingleCountCoincidence( p, pVar2, pVar ); + assert( Coin > 0 ); + // get the new weight + WeightCur = Coin - 2; + if ( WeightCur >= 0 ) + Fxu_MatrixAddSingle( p, pVar2, pVar, WeightCur ); + } + + // unmark the vars + Fxu_MatrixRingVarsUnmark( p ); +} + +/**Function************************************************************* + + Synopsis [Computes the coincidence count of two columns.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_SingleCountCoincidence( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2 ) +{ + Fxu_Lit * pLit1, * pLit2; + int Result; + + // compute the coincidence count + Result = 0; + pLit1 = pVar1->lLits.pHead; + pLit2 = pVar2->lLits.pHead; + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->pCube->pVar->iVar == pLit2->pCube->pVar->iVar ) + { // the variables are the same + if ( pLit1->iCube == pLit2->iCube ) + { // the literals are the same + pLit1 = pLit1->pVNext; + pLit2 = pLit2->pVNext; + // add this literal to the coincidence + Result++; + } + else if ( pLit1->iCube < pLit2->iCube ) + pLit1 = pLit1->pVNext; + else + pLit2 = pLit2->pVNext; + } + else if ( pLit1->pCube->pVar->iVar < pLit2->pCube->pVar->iVar ) + pLit1 = pLit1->pVNext; + else + pLit2 = pLit2->pVNext; + } + else if ( pLit1 && !pLit2 ) + pLit1 = pLit1->pVNext; + else if ( !pLit1 && pLit2 ) + pLit2 = pLit2->pVNext; + else + break; + } + return Result; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/fxuUpdate.c b/src/opt/fxu/fxuUpdate.c new file mode 100644 index 00000000..b781e0b1 --- /dev/null +++ b/src/opt/fxu/fxuUpdate.c @@ -0,0 +1,802 @@ +/**CFile**************************************************************** + + FileName [fxuUpdate.c] + + PackageName [MVSIS 2.0: Multi-valued logic synthesis system.] + + Synopsis [Updating the sparse matrix when divisors are accepted.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - February 1, 2003.] + + Revision [$Id: fxuUpdate.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "fxuInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +static void Fxu_UpdateDoublePairs( Fxu_Matrix * p, Fxu_Double * pDouble, Fxu_Var * pVar ); +static void Fxu_UpdateMatrixDoubleCreateCubes( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, Fxu_Double * pDiv ); +static void Fxu_UpdateMatrixDoubleClean( Fxu_Matrix * p, Fxu_Cube * pCubeUse, Fxu_Cube * pCubeRem ); +static void Fxu_UpdateMatrixSingleClean( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2, Fxu_Var * pVarNew ); + +static void Fxu_UpdateCreateNewVars( Fxu_Matrix * p, Fxu_Var ** ppVarC, Fxu_Var ** ppVarD, int nCubes ); +static int Fxu_UpdatePairCompare( Fxu_Pair ** ppP1, Fxu_Pair ** ppP2 ); +static void Fxu_UpdatePairsSort( Fxu_Matrix * p, Fxu_Double * pDouble ); + +static void Fxu_UpdateCleanOldDoubles( Fxu_Matrix * p, Fxu_Double * pDiv, Fxu_Cube * pCube ); +static void Fxu_UpdateAddNewDoubles( Fxu_Matrix * p, Fxu_Cube * pCube ); +static void Fxu_UpdateCleanOldSingles( Fxu_Matrix * p ); +static void Fxu_UpdateAddNewSingles( Fxu_Matrix * p, Fxu_Var * pVar ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Updates the matrix after selecting two divisors.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_Update( Fxu_Matrix * p, Fxu_Single * pSingle, Fxu_Double * pDouble ) +{ + Fxu_Cube * pCube, * pCubeNew; + Fxu_Var * pVarC, * pVarD; + Fxu_Var * pVar1, * pVar2; + + // consider trivial cases + if ( pSingle == NULL ) + { + assert( pDouble->Weight == Fxu_HeapDoubleReadMaxWeight( p->pHeapDouble ) ); + Fxu_UpdateDouble( p ); + return; + } + if ( pDouble == NULL ) + { + assert( pSingle->Weight == Fxu_HeapSingleReadMaxWeight( p->pHeapSingle ) ); + Fxu_UpdateSingle( p ); + return; + } + + // get the variables of the single + pVar1 = pSingle->pVar1; + pVar2 = pSingle->pVar2; + + // remove the best double from the heap + Fxu_HeapDoubleDelete( p->pHeapDouble, pDouble ); + // remove the best divisor from the table + Fxu_ListTableDelDivisor( p, pDouble ); + + // create two new columns (vars) + Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 1 ); + // create one new row (cube) + pCubeNew = Fxu_MatrixAddCube( p, pVarD, 0 ); + pCubeNew->pFirst = pCubeNew; + // set the first cube of the positive var + pVarD->pFirst = pCubeNew; + + // start collecting the affected vars and cubes + Fxu_MatrixRingCubesStart( p ); + Fxu_MatrixRingVarsStart( p ); + // add the vars + Fxu_MatrixRingVarsAdd( p, pVar1 ); + Fxu_MatrixRingVarsAdd( p, pVar2 ); + // remove the literals and collect the affected cubes + // remove the divisors associated with this cube + // add to the affected cube the literal corresponding to the new column + Fxu_UpdateMatrixSingleClean( p, pVar1, pVar2, pVarD ); + // replace each two cubes of the pair by one new cube + // the new cube contains the base and the new literal + Fxu_UpdateDoublePairs( p, pDouble, pVarC ); + // stop collecting the affected vars and cubes + Fxu_MatrixRingCubesStop( p ); + Fxu_MatrixRingVarsStop( p ); + + // add the literals to the new cube + assert( pVar1->iVar < pVar2->iVar ); + assert( Fxu_SingleCountCoincidence( p, pVar1, pVar2 ) == 0 ); + Fxu_MatrixAddLiteral( p, pCubeNew, pVar1 ); + Fxu_MatrixAddLiteral( p, pCubeNew, pVar2 ); + + // create new doubles; we cannot add them in the same loop + // because we first have to create *all* new cubes for each node + Fxu_MatrixForEachCubeInRing( p, pCube ) + Fxu_UpdateAddNewDoubles( p, pCube ); + // update the singles after removing some literals + Fxu_UpdateCleanOldSingles( p ); + + // undo the temporary rings with cubes and vars + Fxu_MatrixRingCubesUnmark( p ); + Fxu_MatrixRingVarsUnmark( p ); + // we should undo the rings before creating new singles + + // create new singles + Fxu_UpdateAddNewSingles( p, pVarC ); + Fxu_UpdateAddNewSingles( p, pVarD ); + + // recycle the divisor + MEM_FREE_FXU( p, Fxu_Double, 1, pDouble ); + p->nDivs3++; +} + +/**Function************************************************************* + + Synopsis [Updates after accepting single cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateSingle( Fxu_Matrix * p ) +{ + Fxu_Single * pSingle; + Fxu_Cube * pCube, * pCubeNew; + Fxu_Var * pVarC, * pVarD; + Fxu_Var * pVar1, * pVar2; + + // read the best divisor from the heap + pSingle = Fxu_HeapSingleReadMax( p->pHeapSingle ); + // get the variables of this single-cube divisor + pVar1 = pSingle->pVar1; + pVar2 = pSingle->pVar2; + + // create two new columns (vars) + Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 1 ); + // create one new row (cube) + pCubeNew = Fxu_MatrixAddCube( p, pVarD, 0 ); + pCubeNew->pFirst = pCubeNew; + // set the first cube + pVarD->pFirst = pCubeNew; + + // start collecting the affected vars and cubes + Fxu_MatrixRingCubesStart( p ); + Fxu_MatrixRingVarsStart( p ); + // add the vars + Fxu_MatrixRingVarsAdd( p, pVar1 ); + Fxu_MatrixRingVarsAdd( p, pVar2 ); + // remove the literals and collect the affected cubes + // remove the divisors associated with this cube + // add to the affected cube the literal corresponding to the new column + Fxu_UpdateMatrixSingleClean( p, pVar1, pVar2, pVarD ); + // stop collecting the affected vars and cubes + Fxu_MatrixRingCubesStop( p ); + Fxu_MatrixRingVarsStop( p ); + + // add the literals to the new cube + assert( pVar1->iVar < pVar2->iVar ); + assert( Fxu_SingleCountCoincidence( p, pVar1, pVar2 ) == 0 ); + Fxu_MatrixAddLiteral( p, pCubeNew, pVar1 ); + Fxu_MatrixAddLiteral( p, pCubeNew, pVar2 ); + + // create new doubles; we cannot add them in the same loop + // because we first have to create *all* new cubes for each node + Fxu_MatrixForEachCubeInRing( p, pCube ) + Fxu_UpdateAddNewDoubles( p, pCube ); + // update the singles after removing some literals + Fxu_UpdateCleanOldSingles( p ); + // we should undo the rings before creating new singles + + // unmark the cubes + Fxu_MatrixRingCubesUnmark( p ); + Fxu_MatrixRingVarsUnmark( p ); + + // create new singles + Fxu_UpdateAddNewSingles( p, pVarC ); + Fxu_UpdateAddNewSingles( p, pVarD ); + p->nDivs1++; +} + +/**Function************************************************************* + + Synopsis [Updates the matrix after accepting a double cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateDouble( Fxu_Matrix * p ) +{ + Fxu_Double * pDiv; + Fxu_Cube * pCube, * pCubeNew1, * pCubeNew2; + Fxu_Var * pVarC, * pVarD; + + // remove the best divisor from the heap + pDiv = Fxu_HeapDoubleGetMax( p->pHeapDouble ); + // remove the best divisor from the table + Fxu_ListTableDelDivisor( p, pDiv ); + + // create two new columns (vars) + Fxu_UpdateCreateNewVars( p, &pVarC, &pVarD, 2 ); + // create two new rows (cubes) + pCubeNew1 = Fxu_MatrixAddCube( p, pVarD, 0 ); + pCubeNew1->pFirst = pCubeNew1; + pCubeNew2 = Fxu_MatrixAddCube( p, pVarD, 1 ); + pCubeNew2->pFirst = pCubeNew1; + // set the first cube + pVarD->pFirst = pCubeNew1; + + // add the literals to the new cubes + Fxu_UpdateMatrixDoubleCreateCubes( p, pCubeNew1, pCubeNew2, pDiv ); + + // start collecting the affected cubes and vars + Fxu_MatrixRingCubesStart( p ); + Fxu_MatrixRingVarsStart( p ); + // replace each two cubes of the pair by one new cube + // the new cube contains the base and the new literal + Fxu_UpdateDoublePairs( p, pDiv, pVarD ); + // stop collecting the affected cubes and vars + Fxu_MatrixRingCubesStop( p ); + Fxu_MatrixRingVarsStop( p ); + + // create new doubles; we cannot add them in the same loop + // because we first have to create *all* new cubes for each node + Fxu_MatrixForEachCubeInRing( p, pCube ) + Fxu_UpdateAddNewDoubles( p, pCube ); + // update the singles after removing some literals + Fxu_UpdateCleanOldSingles( p ); + + // undo the temporary rings with cubes and vars + Fxu_MatrixRingCubesUnmark( p ); + Fxu_MatrixRingVarsUnmark( p ); + // we should undo the rings before creating new singles + + // create new singles + Fxu_UpdateAddNewSingles( p, pVarC ); + Fxu_UpdateAddNewSingles( p, pVarD ); + + // recycle the divisor + MEM_FREE_FXU( p, Fxu_Double, 1, pDiv ); + p->nDivs2++; +} + +/**Function************************************************************* + + Synopsis [Update the pairs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateDoublePairs( Fxu_Matrix * p, Fxu_Double * pDouble, Fxu_Var * pVar ) +{ + Fxu_Pair * pPair; + Fxu_Cube * pCubeUse, * pCubeRem; + int i; + + // collect and sort the pairs + Fxu_UpdatePairsSort( p, pDouble ); + for ( i = 0; i < p->nPairsTemp; i++ ) + { + // get the pair + pPair = p->pPairsTemp[i]; + // out of the two cubes, select the one which comes earlier + pCubeUse = Fxu_PairMinCube( pPair ); + pCubeRem = Fxu_PairMaxCube( pPair ); + // collect the affected cube + assert( pCubeUse->pOrder == NULL ); + Fxu_MatrixRingCubesAdd( p, pCubeUse ); + + // remove some literals from pCubeUse and all literals from pCubeRem + Fxu_UpdateMatrixDoubleClean( p, pCubeUse, pCubeRem ); + // add a literal that depends on the new variable + Fxu_MatrixAddLiteral( p, pCubeUse, pVar ); + // check the literal count + assert( pCubeUse->lLits.nItems == pPair->nBase + 1 ); + assert( pCubeRem->lLits.nItems == 0 ); + + // update the divisors by removing useless pairs + Fxu_UpdateCleanOldDoubles( p, pDouble, pCubeUse ); + Fxu_UpdateCleanOldDoubles( p, pDouble, pCubeRem ); + // remove the pair + MEM_FREE_FXU( p, Fxu_Pair, 1, pPair ); + } + p->nPairsTemp = 0; +} + +/**Function************************************************************* + + Synopsis [Add two cubes corresponding to the given double-cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateMatrixDoubleCreateCubes( Fxu_Matrix * p, Fxu_Cube * pCube1, Fxu_Cube * pCube2, Fxu_Double * pDiv ) +{ + Fxu_Lit * pLit1, * pLit2; + Fxu_Pair * pPair; + int nBase, nLits1, nLits2; + + // fill in the SOP and copy the fanins + nBase = nLits1 = nLits2 = 0; + pPair = pDiv->lPairs.pHead; + pLit1 = pPair->pCube1->lLits.pHead; + pLit2 = pPair->pCube2->lLits.pHead; + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->iVar == pLit2->iVar ) + { // skip the cube free part + pLit1 = pLit1->pHNext; + pLit2 = pLit2->pHNext; + nBase++; + } + else if ( pLit1->iVar < pLit2->iVar ) + { // add literal to the first cube + Fxu_MatrixAddLiteral( p, pCube1, pLit1->pVar ); + // move to the next literal in this cube + pLit1 = pLit1->pHNext; + nLits1++; + } + else + { // add literal to the second cube + Fxu_MatrixAddLiteral( p, pCube2, pLit2->pVar ); + // move to the next literal in this cube + pLit2 = pLit2->pHNext; + nLits2++; + } + } + else if ( pLit1 && !pLit2 ) + { // add literal to the first cube + Fxu_MatrixAddLiteral( p, pCube1, pLit1->pVar ); + // move to the next literal in this cube + pLit1 = pLit1->pHNext; + nLits1++; + } + else if ( !pLit1 && pLit2 ) + { // add literal to the second cube + Fxu_MatrixAddLiteral( p, pCube2, pLit2->pVar ); + // move to the next literal in this cube + pLit2 = pLit2->pHNext; + nLits2++; + } + else + break; + } + assert( pPair->nLits1 == nLits1 ); + assert( pPair->nLits2 == nLits2 ); + assert( pPair->nBase == nBase ); +} + + +/**Function************************************************************* + + Synopsis [Create the node equal to double-cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateMatrixDoubleClean( Fxu_Matrix * p, Fxu_Cube * pCubeUse, Fxu_Cube * pCubeRem ) +{ + Fxu_Lit * pLit1, * bLit1Next; + Fxu_Lit * pLit2, * bLit2Next; + + // initialize the starting literals + pLit1 = pCubeUse->lLits.pHead; + pLit2 = pCubeRem->lLits.pHead; + bLit1Next = pLit1? pLit1->pHNext: NULL; + bLit2Next = pLit2? pLit2->pHNext: NULL; + // go through the pair and remove the literals in the base + // from the first cube and all literals from the second cube + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->iVar == pLit2->iVar ) + { // this literal is present in both cubes - it belongs to the base + // mark the affected var + if ( pLit1->pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pLit1->pVar ); + // leave the base in pCubeUse; delete it from pCubeRem + Fxu_MatrixDelLiteral( p, pLit2 ); + // step to the next literals + pLit1 = bLit1Next; + pLit2 = bLit2Next; + bLit1Next = pLit1? pLit1->pHNext: NULL; + bLit2Next = pLit2? pLit2->pHNext: NULL; + } + else if ( pLit1->iVar < pLit2->iVar ) + { // this literal is present in pCubeUse - remove it + // mark the affected var + if ( pLit1->pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pLit1->pVar ); + // delete this literal + Fxu_MatrixDelLiteral( p, pLit1 ); + // step to the next literals + pLit1 = bLit1Next; + bLit1Next = pLit1? pLit1->pHNext: NULL; + } + else + { // this literal is present in pCubeRem - remove it + // mark the affected var + if ( pLit2->pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pLit2->pVar ); + // delete this literal + Fxu_MatrixDelLiteral( p, pLit2 ); + // step to the next literals + pLit2 = bLit2Next; + bLit2Next = pLit2? pLit2->pHNext: NULL; + } + } + else if ( pLit1 && !pLit2 ) + { // this literal is present in pCubeUse - leave it + // mark the affected var + if ( pLit1->pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pLit1->pVar ); + // delete this literal + Fxu_MatrixDelLiteral( p, pLit1 ); + // step to the next literals + pLit1 = bLit1Next; + bLit1Next = pLit1? pLit1->pHNext: NULL; + } + else if ( !pLit1 && pLit2 ) + { // this literal is present in pCubeRem - remove it + // mark the affected var + if ( pLit2->pVar->pOrder == NULL ) + Fxu_MatrixRingVarsAdd( p, pLit2->pVar ); + // delete this literal + Fxu_MatrixDelLiteral( p, pLit2 ); + // step to the next literals + pLit2 = bLit2Next; + bLit2Next = pLit2? pLit2->pHNext: NULL; + } + else + break; + } +} + +/**Function************************************************************* + + Synopsis [Updates the matrix after selecting a single cube divisor.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateMatrixSingleClean( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2, Fxu_Var * pVarNew ) +{ + Fxu_Lit * pLit1, * bLit1Next; + Fxu_Lit * pLit2, * bLit2Next; + + // initialize the starting literals + pLit1 = pVar1->lLits.pHead; + pLit2 = pVar2->lLits.pHead; + bLit1Next = pLit1? pLit1->pVNext: NULL; + bLit2Next = pLit2? pLit2->pVNext: NULL; + while ( 1 ) + { + if ( pLit1 && pLit2 ) + { + if ( pLit1->pCube->pVar->iVar == pLit2->pCube->pVar->iVar ) + { // these literals coincide + if ( pLit1->iCube == pLit2->iCube ) + { // these literals coincide + + // collect the affected cube + assert( pLit1->pCube->pOrder == NULL ); + Fxu_MatrixRingCubesAdd( p, pLit1->pCube ); + + // add the literal to this cube corresponding to the new column + Fxu_MatrixAddLiteral( p, pLit1->pCube, pVarNew ); + // clean the old cubes + Fxu_UpdateCleanOldDoubles( p, NULL, pLit1->pCube ); + + // remove the literals + Fxu_MatrixDelLiteral( p, pLit1 ); + Fxu_MatrixDelLiteral( p, pLit2 ); + + // go to the next literals + pLit1 = bLit1Next; + pLit2 = bLit2Next; + bLit1Next = pLit1? pLit1->pVNext: NULL; + bLit2Next = pLit2? pLit2->pVNext: NULL; + } + else if ( pLit1->iCube < pLit2->iCube ) + { + pLit1 = bLit1Next; + bLit1Next = pLit1? pLit1->pVNext: NULL; + } + else + { + pLit2 = bLit2Next; + bLit2Next = pLit2? pLit2->pVNext: NULL; + } + } + else if ( pLit1->pCube->pVar->iVar < pLit2->pCube->pVar->iVar ) + { + pLit1 = bLit1Next; + bLit1Next = pLit1? pLit1->pVNext: NULL; + } + else + { + pLit2 = bLit2Next; + bLit2Next = pLit2? pLit2->pVNext: NULL; + } + } + else if ( pLit1 && !pLit2 ) + { + pLit1 = bLit1Next; + bLit1Next = pLit1? pLit1->pVNext: NULL; + } + else if ( !pLit1 && pLit2 ) + { + pLit2 = bLit2Next; + bLit2Next = pLit2? pLit2->pVNext: NULL; + } + else + break; + } +} + +/**Function************************************************************* + + Synopsis [Sort the pairs.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdatePairsSort( Fxu_Matrix * p, Fxu_Double * pDouble ) +{ + Fxu_Pair * pPair; + // order the pairs by the first cube to ensure that + // new literals are added to the matrix from top to bottom + // collect pairs into the array + p->nPairsTemp = 0; + Fxu_DoubleForEachPair( pDouble, pPair ) + p->pPairsTemp[ p->nPairsTemp++ ] = pPair; + if ( p->nPairsTemp > 1 ) + { // sort + qsort( (void *)p->pPairsTemp, p->nPairsTemp, sizeof(Fxu_Pair *), + (int (*)(const void *, const void *)) Fxu_UpdatePairCompare ); + assert( Fxu_UpdatePairCompare( p->pPairsTemp, p->pPairsTemp + p->nPairsTemp - 1 ) < 0 ); + } +} + +/**Function************************************************************* + + Synopsis [Compares the vars by their number.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Fxu_UpdatePairCompare( Fxu_Pair ** ppP1, Fxu_Pair ** ppP2 ) +{ + Fxu_Cube * pC1 = (*ppP1)->pCube1; + Fxu_Cube * pC2 = (*ppP2)->pCube1; + int iP1CubeMin, iP2CubeMin; + if ( pC1->pVar->iVar < pC2->pVar->iVar ) + return -1; + if ( pC1->pVar->iVar > pC2->pVar->iVar ) + return 1; + iP1CubeMin = Fxu_PairMinCubeInt( *ppP1 ); + iP2CubeMin = Fxu_PairMinCubeInt( *ppP2 ); + if ( iP1CubeMin < iP2CubeMin ) + return -1; + if ( iP1CubeMin > iP2CubeMin ) + return 1; + assert( 0 ); + return 0; +} + + +/**Function************************************************************* + + Synopsis [Create new variables.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateCreateNewVars( Fxu_Matrix * p, Fxu_Var ** ppVarC, Fxu_Var ** ppVarD, int nCubes ) +{ + Fxu_Var * pVarC, * pVarD; + + // add a new column for the complement + pVarC = Fxu_MatrixAddVar( p ); + pVarC->nCubes = 0; + // add a new column for the divisor + pVarD = Fxu_MatrixAddVar( p ); + pVarD->nCubes = nCubes; + + // mark this entry in the Value2Node array +// assert( p->pValue2Node[pVarC->iVar] > 0 ); +// p->pValue2Node[pVarD->iVar ] = p->pValue2Node[pVarC->iVar]; +// p->pValue2Node[pVarD->iVar+1] = p->pValue2Node[pVarC->iVar]+1; + + *ppVarC = pVarC; + *ppVarD = pVarD; +} + + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateCleanOldDoubles( Fxu_Matrix * p, Fxu_Double * pDiv, Fxu_Cube * pCube ) +{ + Fxu_Double * pDivCur; + Fxu_Pair * pPair; + int i; + + // if the cube is a recently introduced one + // it does not have pairs allocated + // in this case, there is nothing to update + if ( pCube->pVar->ppPairs == NULL ) + return; + + // go through all the pairs of this cube + Fxu_CubeForEachPair( pCube, pPair, i ) + { + // get the divisor of this pair + pDivCur = pPair->pDiv; + // skip the current divisor + if ( pDivCur == pDiv ) + continue; + // remove this pair + Fxu_ListDoubleDelPair( pDivCur, pPair ); + // the divisor may have become useless by now + if ( pDivCur->lPairs.nItems == 0 ) + { + assert( pDivCur->Weight == pPair->nBase - 1 ); + Fxu_HeapDoubleDelete( p->pHeapDouble, pDivCur ); + Fxu_MatrixDelDivisor( p, pDivCur ); + } + else + { + // update the divisor's weight + pDivCur->Weight -= pPair->nLits1 + pPair->nLits2 - 1 + pPair->nBase; + Fxu_HeapDoubleUpdate( p->pHeapDouble, pDivCur ); + } + MEM_FREE_FXU( p, Fxu_Pair, 1, pPair ); + } + // finally erase all the pair info associated with this cube + Fxu_PairClearStorage( pCube ); +} + +/**Function************************************************************* + + Synopsis [Adds the new divisors that depend on the cube.] + + Description [Go through all the non-empty cubes of this cover + (except the given cube) and, for each of them, add the new divisor + with the given cube.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateAddNewDoubles( Fxu_Matrix * p, Fxu_Cube * pCube ) +{ + Fxu_Cube * pTemp; + assert( pCube->pOrder ); + + // if the cube is a recently introduced one + // it does not have pairs allocated + // in this case, there is nothing to update + if ( pCube->pVar->ppPairs == NULL ) + return; + + for ( pTemp = pCube->pFirst; pTemp->pVar == pCube->pVar; pTemp = pTemp->pNext ) + { + // do not add pairs with the empty cubes + if ( pTemp->lLits.nItems == 0 ) + continue; + // to prevent adding duplicated pairs of the new cubes + // do not add the pair, if the current cube is marked + if ( pTemp->pOrder && pTemp >= pCube ) + continue; + Fxu_MatrixAddDivisor( p, pTemp, pCube ); + } +} + +/**Function************************************************************* + + Synopsis [Removes old single cube divisors.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateCleanOldSingles( Fxu_Matrix * p ) +{ + Fxu_Single * pSingle, * pSingle2; + int WeightNew; + + Fxu_MatrixForEachSingleSafe( p, pSingle, pSingle2 ) + { + // if at least one of the variables is marked, recalculate + if ( pSingle->pVar1->pOrder || pSingle->pVar2->pOrder ) + { + // get the new weight + WeightNew = -2 + Fxu_SingleCountCoincidence( p, pSingle->pVar1, pSingle->pVar2 ); + if ( WeightNew >= 0 ) + { + pSingle->Weight = WeightNew; + Fxu_HeapSingleUpdate( p->pHeapSingle, pSingle ); + } + else + { + Fxu_HeapSingleDelete( p->pHeapSingle, pSingle ); + Fxu_ListMatrixDelSingle( p, pSingle ); + MEM_FREE_FXU( p, Fxu_Single, 1, pSingle ); + } + } + } +} + +/**Function************************************************************* + + Synopsis [Updates the single cube divisors.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Fxu_UpdateAddNewSingles( Fxu_Matrix * p, Fxu_Var * pVar ) +{ + Fxu_MatrixComputeSinglesOne( p, pVar ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + diff --git a/src/opt/fxu/module.make b/src/opt/fxu/module.make new file mode 100644 index 00000000..331712d1 --- /dev/null +++ b/src/opt/fxu/module.make @@ -0,0 +1,12 @@ +SRC += fxu.c \ + fxuCreate.c \ + fxuHeapD.c \ + fxuHeapS.c \ + fxuList.c \ + fxuMatrix.c \ + fxuPair.c \ + fxuPrint.c \ + fxuReduce.c \ + fxuSelect.c \ + fxuSingle.c \ + fxuUpdate.c -- cgit v1.2.3