summaryrefslogtreecommitdiffstats
path: root/src/misc/extra
diff options
context:
space:
mode:
Diffstat (limited to 'src/misc/extra')
-rw-r--r--src/misc/extra/extra.h69
-rw-r--r--src/misc/extra/extraBddAuto.c1558
-rw-r--r--src/misc/extra/extraBddMisc.c77
-rw-r--r--src/misc/extra/extraBddUnate.c641
-rw-r--r--src/misc/extra/extraUtilCanon.c24
-rw-r--r--src/misc/extra/extraUtilReader.c15
-rw-r--r--src/misc/extra/module.make3
7 files changed, 2375 insertions, 12 deletions
diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h
index bb776ab7..0d0c93a8 100644
--- a/src/misc/extra/extra.h
+++ b/src/misc/extra/extra.h
@@ -106,7 +106,35 @@ typedef unsigned long long uint64;
/* Various Utilities */
/*===========================================================================*/
+/*=== extraBddAuto.c ========================================================*/
+
+extern DdNode * Extra_bddSpaceFromFunctionFast( DdManager * dd, DdNode * bFunc );
+extern DdNode * Extra_bddSpaceFromFunction( DdManager * dd, DdNode * bF, DdNode * bG );
+extern DdNode * extraBddSpaceFromFunction( DdManager * dd, DdNode * bF, DdNode * bG );
+extern DdNode * Extra_bddSpaceFromFunctionPos( DdManager * dd, DdNode * bFunc );
+extern DdNode * extraBddSpaceFromFunctionPos( DdManager * dd, DdNode * bFunc );
+extern DdNode * Extra_bddSpaceFromFunctionNeg( DdManager * dd, DdNode * bFunc );
+extern DdNode * extraBddSpaceFromFunctionNeg( DdManager * dd, DdNode * bFunc );
+
+extern DdNode * Extra_bddSpaceCanonVars( DdManager * dd, DdNode * bSpace );
+extern DdNode * extraBddSpaceCanonVars( DdManager * dd, DdNode * bSpace );
+
+extern DdNode * Extra_bddSpaceEquations( DdManager * dd, DdNode * bSpace );
+extern DdNode * Extra_bddSpaceEquationsNeg( DdManager * dd, DdNode * bSpace );
+extern DdNode * extraBddSpaceEquationsNeg( DdManager * dd, DdNode * bSpace );
+extern DdNode * Extra_bddSpaceEquationsPos( DdManager * dd, DdNode * bSpace );
+extern DdNode * extraBddSpaceEquationsPos( DdManager * dd, DdNode * bSpace );
+
+extern DdNode * Extra_bddSpaceFromMatrixPos( DdManager * dd, DdNode * zA );
+extern DdNode * extraBddSpaceFromMatrixPos( DdManager * dd, DdNode * zA );
+extern DdNode * Extra_bddSpaceFromMatrixNeg( DdManager * dd, DdNode * zA );
+extern DdNode * extraBddSpaceFromMatrixNeg( DdManager * dd, DdNode * zA );
+
+extern DdNode * Extra_bddSpaceReduce( DdManager * dd, DdNode * bFunc, DdNode * bCanonVars );
+extern DdNode ** Extra_bddSpaceExorGates( DdManager * dd, DdNode * bFuncRed, DdNode * zEquations );
+
/*=== extraBddMisc.c ========================================================*/
+
extern DdNode * Extra_TransferPermute( DdManager * ddSource, DdManager * ddDestination, DdNode * f, int * Permute );
extern DdNode * Extra_TransferLevelByLevel( DdManager * ddSource, DdManager * ddDestination, DdNode * f );
extern DdNode * Extra_bddRemapUp( DdManager * dd, DdNode * bF );
@@ -126,6 +154,7 @@ extern DdNode * Extra_bddFindOneCube( DdManager * dd, DdNode * bF );
extern DdNode * Extra_bddGetOneCube( DdManager * dd, DdNode * bFunc );
extern DdNode * Extra_bddComputeRangeCube( DdManager * dd, int iStart, int iStop );
extern DdNode * Extra_bddBitsToCube( DdManager * dd, int Code, int CodeWidth, DdNode ** pbVars, int fMsbFirst );
+extern DdNode * Extra_bddSupportNegativeCube( DdManager * dd, DdNode * f );
/*=== extraBddKmap.c ================================================================*/
@@ -185,6 +214,46 @@ extern DdNode * extraZddTuplesFromBdd( DdManager * dd, DdNode * bVarsK, DdNo
extern DdNode * Extra_zddSelectOneSubset( DdManager * dd, DdNode * zS );
extern DdNode * extraZddSelectOneSubset( DdManager * dd, DdNode * zS );
+/*=== extraBddUnate.c =================================================================*/
+
+typedef struct Extra_UnateVar_t_ Extra_UnateVar_t;
+struct Extra_UnateVar_t_ {
+ unsigned iVar : 30; // index of the variable
+ unsigned Pos : 1; // 1 if positive unate
+ unsigned Neg : 1; // 1 if negative unate
+};
+
+typedef struct Extra_UnateInfo_t_ Extra_UnateInfo_t;
+struct Extra_UnateInfo_t_ {
+ int nVars; // the number of variables in the support
+ int nVarsMax; // the number of variables in the DD manager
+ int nUnate; // the number of unate variables
+ Extra_UnateVar_t * pVars; // the array of variables present in the support
+};
+
+/* allocates the data structure */
+extern Extra_UnateInfo_t * Extra_UnateInfoAllocate( int nVars );
+/* deallocates the data structure */
+extern void Extra_UnateInfoDissolve( Extra_UnateInfo_t * );
+/* print the contents the data structure */
+extern void Extra_UnateInfoPrint( Extra_UnateInfo_t * );
+/* converts the ZDD into the Extra_SymmInfo_t structure */
+extern Extra_UnateInfo_t * Extra_UnateInfoCreateFromZdd( DdManager * dd, DdNode * zUnate, DdNode * bVars );
+/* naive check of unateness of one variable */
+extern int Extra_bddCheckUnateNaive( DdManager * dd, DdNode * bF, int iVar );
+
+/* computes the unateness information for the function */
+extern Extra_UnateInfo_t * Extra_UnateComputeFast( DdManager * dd, DdNode * bFunc );
+extern Extra_UnateInfo_t * Extra_UnateComputeSlow( DdManager * dd, DdNode * bFunc );
+
+/* computes the classical symmetry information as a ZDD */
+extern DdNode * Extra_zddUnateInfoCompute( DdManager * dd, DdNode * bF, DdNode * bVars );
+extern DdNode * extraZddUnateInfoCompute( DdManager * dd, DdNode * bF, DdNode * bVars );
+
+/* converts a set of variables into a set of singleton subsets */
+extern DdNode * Extra_zddGetSingletonsBoth( DdManager * dd, DdNode * bVars );
+extern DdNode * extraZddGetSingletonsBoth( DdManager * dd, DdNode * bVars );
+
/*=== extraUtilBitMatrix.c ================================================================*/
typedef struct Extra_BitMat_t_ Extra_BitMat_t;
diff --git a/src/misc/extra/extraBddAuto.c b/src/misc/extra/extraBddAuto.c
new file mode 100644
index 00000000..21a969ba
--- /dev/null
+++ b/src/misc/extra/extraBddAuto.c
@@ -0,0 +1,1558 @@
+/**CFile****************************************************************
+
+ FileName [extraBddAuto.c]
+
+ PackageName [extra]
+
+ Synopsis [Computation of autosymmetries.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 2.0. Started - September 1, 2003.]
+
+ Revision [$Id: extraBddAuto.c,v 1.0 2003/05/21 18:03:50 alanmi Exp $]
+
+***********************************************************************/
+
+#include "extra.h"
+
+/*---------------------------------------------------------------------------*/
+/* Constant declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Stucture declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Type declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Variable declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Macro declarations */
+/*---------------------------------------------------------------------------*/
+
+
+/**AutomaticStart*************************************************************/
+
+/*---------------------------------------------------------------------------*/
+/* Static function prototypes */
+/*---------------------------------------------------------------------------*/
+
+/**AutomaticEnd***************************************************************/
+
+
+/*
+ LinearSpace(f) = Space(f,f)
+
+ Space(f,g)
+ {
+ if ( f = const )
+ {
+ if ( f = g ) return 1;
+ else return 0;
+ }
+ if ( g = const ) return 0;
+ return x' * Space(fx',gx') * Space(fx,gx) + x * Space(fx',gx) * Space(fx,gx');
+ }
+
+ Equations(s) = Pos(s) + Neg(s);
+
+ Pos(s)
+ {
+ if ( s = 0 ) return 1;
+ if ( s = 1 ) return 0;
+ if ( sx'= 0 ) return Pos(sx) + x;
+ if ( sx = 0 ) return Pos(sx');
+ return 1 * [Pos(sx') & Pos(sx)] + x * [Pos(sx') & Neg(sx)];
+ }
+
+ Neg(s)
+ {
+ if ( s = 0 ) return 1;
+ if ( s = 1 ) return 0;
+ if ( sx'= 0 ) return Neg(sx);
+ if ( sx = 0 ) return Neg(sx') + x;
+ return 1 * [Neg(sx') & Neg(sx)] + x * [Neg(sx') & Pos(sx)];
+ }
+
+
+ SpaceP(A)
+ {
+ if ( A = 0 ) return 1;
+ if ( A = 1 ) return 1;
+ return x' * SpaceP(Ax') * SpaceP(Ax) + x * SpaceP(Ax') * SpaceN(Ax);
+ }
+
+ SpaceN(A)
+ {
+ if ( A = 0 ) return 1;
+ if ( A = 1 ) return 0;
+ return x' * SpaceN(Ax') * SpaceN(Ax) + x * SpaceN(Ax') * SpaceP(Ax);
+ }
+
+
+ LinInd(A)
+ {
+ if ( A = const ) return 1;
+ if ( !LinInd(Ax') ) return 0;
+ if ( !LinInd(Ax) ) return 0;
+ if ( LinSumOdd(Ax') & LinSumEven(Ax) != 0 ) return 0;
+ if ( LinSumEven(Ax') & LinSumEven(Ax) != 0 ) return 0;
+ return 1;
+ }
+
+ LinSumOdd(A)
+ {
+ if ( A = 0 ) return 0; // Odd0 ---e-- Odd1
+ if ( A = 1 ) return 1; // \ o
+ Odd0 = LinSumOdd(Ax'); // x is absent // \
+ Even0 = LinSumEven(Ax'); // x is absent // / o
+ Odd1 = LinSumOdd(Ax); // x is present // Even0 ---e-- Even1
+ Even1 = LinSumEven(Ax); // x is absent
+ return 1 * [Odd0 + ExorP(Odd0, Even1)] + x * [Odd1 + ExorP(Odd1, Even0)];
+ }
+
+ LinSumEven(A)
+ {
+ if ( A = 0 ) return 0;
+ if ( A = 1 ) return 0;
+ Odd0 = LinSumOdd(Ax'); // x is absent
+ Even0 = LinSumEven(Ax'); // x is absent
+ Odd1 = LinSumOdd(Ax); // x is present
+ Even1 = LinSumEven(Ax); // x is absent
+ return 1 * [Even0 + Even1 + ExorP(Even0, Even1)] + x * [ExorP(Odd0, Odd1)];
+ }
+
+*/
+
+/*---------------------------------------------------------------------------*/
+/* Definition of exported functions */
+/*---------------------------------------------------------------------------*/
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromFunctionFast( DdManager * dd, DdNode * bFunc )
+{
+ int * pSupport;
+ int * pPermute;
+ int * pPermuteBack;
+ DdNode ** pCompose;
+ DdNode * bCube, * bTemp;
+ DdNode * bSpace, * bFunc1, * bFunc2, * bSpaceShift;
+ int nSupp, Counter;
+ int i, lev;
+
+ // get the support
+ pSupport = ALLOC( int, ddMax(dd->size,dd->sizeZ) );
+ Extra_SupportArray( dd, bFunc, pSupport );
+ nSupp = 0;
+ for ( i = 0; i < dd->size; i++ )
+ if ( pSupport[i] )
+ nSupp++;
+
+ // make sure the manager has enough variables
+ if ( 2*nSupp > dd->size )
+ {
+ printf( "Cannot derive linear space, because DD manager does not have enough variables.\n" );
+ fflush( stdout );
+ free( pSupport );
+ return NULL;
+ }
+
+ // create the permutation arrays
+ pPermute = ALLOC( int, dd->size );
+ pPermuteBack = ALLOC( int, dd->size );
+ pCompose = ALLOC( DdNode *, dd->size );
+ for ( i = 0; i < dd->size; i++ )
+ {
+ pPermute[i] = i;
+ pPermuteBack[i] = i;
+ pCompose[i] = dd->vars[i]; Cudd_Ref( pCompose[i] );
+ }
+
+ // remap the function in such a way that the variables are interleaved
+ Counter = 0;
+ bCube = b1; Cudd_Ref( bCube );
+ for ( lev = 0; lev < dd->size; lev++ )
+ if ( pSupport[ dd->invperm[lev] ] )
+ { // var "dd->invperm[lev]" on level "lev" should go to level 2*Counter;
+ pPermute[ dd->invperm[lev] ] = dd->invperm[2*Counter];
+ // var from level 2*Counter+1 should go back to the place of this var
+ pPermuteBack[ dd->invperm[2*Counter+1] ] = dd->invperm[lev];
+ // the permutation should be defined in such a way that variable
+ // on level 2*Counter is replaced by an EXOR of itself and var on the next level
+ Cudd_Deref( pCompose[ dd->invperm[2*Counter] ] );
+ pCompose[ dd->invperm[2*Counter] ] =
+ Cudd_bddXor( dd, dd->vars[ dd->invperm[2*Counter] ], dd->vars[ dd->invperm[2*Counter+1] ] );
+ Cudd_Ref( pCompose[ dd->invperm[2*Counter] ] );
+ // add this variable to the cube
+ bCube = Cudd_bddAnd( dd, bTemp = bCube, dd->vars[ dd->invperm[2*Counter] ] ); Cudd_Ref( bCube );
+ Cudd_RecursiveDeref( dd, bTemp );
+ // increment the counter
+ Counter ++;
+ }
+
+ // permute the functions
+ bFunc1 = Cudd_bddPermute( dd, bFunc, pPermute ); Cudd_Ref( bFunc1 );
+ // compose to gate the function depending on both vars
+ bFunc2 = Cudd_bddVectorCompose( dd, bFunc1, pCompose ); Cudd_Ref( bFunc2 );
+ // gate the vector space
+ // L(a) = ForAll x [ F(x) = F(x+a) ] = Not( Exist x [ F(x) (+) F(x+a) ] )
+ bSpaceShift = Cudd_bddXorExistAbstract( dd, bFunc1, bFunc2, bCube ); Cudd_Ref( bSpaceShift );
+ bSpaceShift = Cudd_Not( bSpaceShift );
+ // permute the space back into the original mapping
+ bSpace = Cudd_bddPermute( dd, bSpaceShift, pPermuteBack ); Cudd_Ref( bSpace );
+ Cudd_RecursiveDeref( dd, bFunc1 );
+ Cudd_RecursiveDeref( dd, bFunc2 );
+ Cudd_RecursiveDeref( dd, bSpaceShift );
+ Cudd_RecursiveDeref( dd, bCube );
+
+ for ( i = 0; i < dd->size; i++ )
+ Cudd_RecursiveDeref( dd, pCompose[i] );
+ free( pPermute );
+ free( pPermuteBack );
+ free( pCompose );
+ free( pSupport );
+
+ Cudd_Deref( bSpace );
+ return bSpace;
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromFunction( DdManager * dd, DdNode * bF, DdNode * bG )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceFromFunction( dd, bF, bG );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromFunctionPos( DdManager * dd, DdNode * bFunc )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceFromFunctionPos( dd, bFunc );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromFunctionNeg( DdManager * dd, DdNode * bFunc )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceFromFunctionNeg( dd, bFunc );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceCanonVars( DdManager * dd, DdNode * bSpace )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceCanonVars( dd, bSpace );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceReduce( DdManager * dd, DdNode * bFunc, DdNode * bCanonVars )
+{
+ DdNode * bNegCube;
+ DdNode * bResult;
+ bNegCube = Extra_bddSupportNegativeCube( dd, bCanonVars ); Cudd_Ref( bNegCube );
+ bResult = Cudd_Cofactor( dd, bFunc, bNegCube ); Cudd_Ref( bResult );
+ Cudd_RecursiveDeref( dd, bNegCube );
+ Cudd_Deref( bResult );
+ return bResult;
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceEquations( DdManager * dd, DdNode * bSpace )
+{
+ DdNode * zRes;
+ DdNode * zEquPos;
+ DdNode * zEquNeg;
+ zEquPos = Extra_bddSpaceEquationsPos( dd, bSpace ); Cudd_Ref( zEquPos );
+ zEquNeg = Extra_bddSpaceEquationsNeg( dd, bSpace ); Cudd_Ref( zEquNeg );
+ zRes = Cudd_zddUnion( dd, zEquPos, zEquNeg ); Cudd_Ref( zRes );
+ Cudd_RecursiveDerefZdd( dd, zEquPos );
+ Cudd_RecursiveDerefZdd( dd, zEquNeg );
+ Cudd_Deref( zRes );
+ return zRes;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceEquationsPos( DdManager * dd, DdNode * bSpace )
+{
+ DdNode * zRes;
+ do {
+ dd->reordered = 0;
+ zRes = extraBddSpaceEquationsPos( dd, bSpace );
+ } while (dd->reordered == 1);
+ return zRes;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceEquationsNeg( DdManager * dd, DdNode * bSpace )
+{
+ DdNode * zRes;
+ do {
+ dd->reordered = 0;
+ zRes = extraBddSpaceEquationsNeg( dd, bSpace );
+ } while (dd->reordered == 1);
+ return zRes;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromMatrixPos( DdManager * dd, DdNode * zA )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceFromMatrixPos( dd, zA );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * Extra_bddSpaceFromMatrixNeg( DdManager * dd, DdNode * zA )
+{
+ DdNode * bRes;
+ do {
+ dd->reordered = 0;
+ bRes = extraBddSpaceFromMatrixNeg( dd, zA );
+ } while (dd->reordered == 1);
+ return bRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Counts the number of literals in one combination.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Extra_zddLitCountComb( DdManager * dd, DdNode * zComb )
+{
+ int Counter;
+ if ( zComb == z0 )
+ return 0;
+ Counter = 0;
+ for ( ; zComb != z1; zComb = cuddT(zComb) )
+ Counter++;
+ return Counter;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description [Returns the array of ZDDs with the number equal to the number of
+ vars in the DD manager. If the given var is non-canonical, this array contains
+ the referenced ZDD representing literals in the corresponding EXOR equation.]
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode ** Extra_bddSpaceExorGates( DdManager * dd, DdNode * bFuncRed, DdNode * zEquations )
+{
+ DdNode ** pzRes;
+ int * pVarsNonCan;
+ DdNode * zEquRem;
+ int iVarNonCan;
+ DdNode * zExor, * zTemp;
+
+ // get the set of non-canonical variables
+ pVarsNonCan = ALLOC( int, ddMax(dd->size,dd->sizeZ) );
+ Extra_SupportArray( dd, bFuncRed, pVarsNonCan );
+
+ // allocate storage for the EXOR sets
+ pzRes = ALLOC( DdNode *, dd->size );
+ memset( pzRes, 0, sizeof(DdNode *) * dd->size );
+
+ // go through all the equations
+ zEquRem = zEquations; Cudd_Ref( zEquRem );
+ while ( zEquRem != z0 )
+ {
+ // extract one product
+ zExor = Extra_zddSelectOneSubset( dd, zEquRem ); Cudd_Ref( zExor );
+ // remove it from the set
+ zEquRem = Cudd_zddDiff( dd, zTemp = zEquRem, zExor ); Cudd_Ref( zEquRem );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+
+ // locate the non-canonical variable
+ iVarNonCan = -1;
+ for ( zTemp = zExor; zTemp != z1; zTemp = cuddT(zTemp) )
+ {
+ if ( pVarsNonCan[zTemp->index/2] == 1 )
+ {
+ assert( iVarNonCan == -1 );
+ iVarNonCan = zTemp->index/2;
+ }
+ }
+ assert( iVarNonCan != -1 );
+
+ if ( Extra_zddLitCountComb( dd, zExor ) > 1 )
+ pzRes[ iVarNonCan ] = zExor; // takes ref
+ else
+ Cudd_RecursiveDerefZdd( dd, zExor );
+ }
+ Cudd_RecursiveDerefZdd( dd, zEquRem );
+
+ free( pVarsNonCan );
+ return pzRes;
+}
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of internal functions */
+/*---------------------------------------------------------------------------*/
+
+/**Function********************************************************************
+
+ Synopsis [Performs the recursive steps of Extra_bddSpaceFromFunction.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+DdNode * extraBddSpaceFromFunction( DdManager * dd, DdNode * bF, DdNode * bG )
+{
+ DdNode * bRes;
+ DdNode * bFR, * bGR;
+
+ bFR = Cudd_Regular( bF );
+ bGR = Cudd_Regular( bG );
+ if ( cuddIsConstant(bFR) )
+ {
+ if ( bF == bG )
+ return b1;
+ else
+ return b0;
+ }
+ if ( cuddIsConstant(bGR) )
+ return b0;
+ // both bFunc and bCore are not constants
+
+ // the operation is commutative - normalize the problem
+ if ( (unsigned)bF > (unsigned)bG )
+ return extraBddSpaceFromFunction(dd, bG, bF);
+
+
+ if ( bRes = cuddCacheLookup2(dd, extraBddSpaceFromFunction, bF, bG) )
+ return bRes;
+ else
+ {
+ DdNode * bF0, * bF1;
+ DdNode * bG0, * bG1;
+ DdNode * bTemp1, * bTemp2;
+ DdNode * bRes0, * bRes1;
+ int LevelF, LevelG;
+ int index;
+
+ LevelF = dd->perm[bFR->index];
+ LevelG = dd->perm[bGR->index];
+ if ( LevelF <= LevelG )
+ {
+ index = dd->invperm[LevelF];
+ if ( bFR != bF )
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+ }
+ else
+ {
+ index = dd->invperm[LevelG];
+ bF0 = bF1 = bF;
+ }
+
+ if ( LevelG <= LevelF )
+ {
+ if ( bGR != bG )
+ {
+ bG0 = Cudd_Not( cuddE(bGR) );
+ bG1 = Cudd_Not( cuddT(bGR) );
+ }
+ else
+ {
+ bG0 = cuddE(bGR);
+ bG1 = cuddT(bGR);
+ }
+ }
+ else
+ bG0 = bG1 = bG;
+
+ bTemp1 = extraBddSpaceFromFunction( dd, bF0, bG0 );
+ if ( bTemp1 == NULL )
+ return NULL;
+ cuddRef( bTemp1 );
+
+ bTemp2 = extraBddSpaceFromFunction( dd, bF1, bG1 );
+ if ( bTemp2 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ return NULL;
+ }
+ cuddRef( bTemp2 );
+
+
+ bRes0 = cuddBddAndRecur( dd, bTemp1, bTemp2 );
+ if ( bRes0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ Cudd_RecursiveDeref( dd, bTemp2 );
+ return NULL;
+ }
+ cuddRef( bRes0 );
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ Cudd_RecursiveDeref( dd, bTemp2 );
+
+
+ bTemp1 = extraBddSpaceFromFunction( dd, bF0, bG1 );
+ if ( bTemp1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ return NULL;
+ }
+ cuddRef( bTemp1 );
+
+ bTemp2 = extraBddSpaceFromFunction( dd, bF1, bG0 );
+ if ( bTemp2 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ return NULL;
+ }
+ cuddRef( bTemp2 );
+
+ bRes1 = cuddBddAndRecur( dd, bTemp1, bTemp2 );
+ if ( bRes1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ Cudd_RecursiveDeref( dd, bTemp2 );
+ return NULL;
+ }
+ cuddRef( bRes1 );
+ Cudd_RecursiveDeref( dd, bTemp1 );
+ Cudd_RecursiveDeref( dd, bTemp2 );
+
+
+
+ // consider the case when Res0 and Res1 are the same node
+ if ( bRes0 == bRes1 )
+ bRes = bRes1;
+ // consider the case when Res1 is complemented
+ else if ( Cudd_IsComplement(bRes1) )
+ {
+ bRes = cuddUniqueInter(dd, index, Cudd_Not(bRes1), Cudd_Not(bRes0));
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ bRes = Cudd_Not(bRes);
+ }
+ else
+ {
+ bRes = cuddUniqueInter( dd, index, bRes1, bRes0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ }
+ cuddDeref( bRes0 );
+ cuddDeref( bRes1 );
+
+ // insert the result into cache
+ cuddCacheInsert2(dd, extraBddSpaceFromFunction, bF, bG, bRes);
+ return bRes;
+ }
+} /* end of extraBddSpaceFromFunction */
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceFromFunctionPos().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceFromFunctionPos( DdManager * dd, DdNode * bF )
+{
+ DdNode * bRes, * bFR;
+ statLine( dd );
+
+ bFR = Cudd_Regular(bF);
+ if ( cuddIsConstant(bFR) )
+ return b1;
+
+ if ( bRes = cuddCacheLookup1(dd, extraBddSpaceFromFunctionPos, bF) )
+ return bRes;
+ else
+ {
+ DdNode * bF0, * bF1;
+ DdNode * bPos0, * bPos1;
+ DdNode * bNeg0, * bNeg1;
+ DdNode * bRes0, * bRes1;
+
+ if ( bFR != bF ) // bF is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+
+ bPos0 = extraBddSpaceFromFunctionPos( dd, bF0 );
+ if ( bPos0 == NULL )
+ return NULL;
+ cuddRef( bPos0 );
+
+ bPos1 = extraBddSpaceFromFunctionPos( dd, bF1 );
+ if ( bPos1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bPos0 );
+ return NULL;
+ }
+ cuddRef( bPos1 );
+
+ bRes0 = cuddBddAndRecur( dd, bPos0, bPos1 );
+ if ( bRes0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bPos0 );
+ Cudd_RecursiveDeref( dd, bPos1 );
+ return NULL;
+ }
+ cuddRef( bRes0 );
+ Cudd_RecursiveDeref( dd, bPos0 );
+ Cudd_RecursiveDeref( dd, bPos1 );
+
+
+ bNeg0 = extraBddSpaceFromFunctionNeg( dd, bF0 );
+ if ( bNeg0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ return NULL;
+ }
+ cuddRef( bNeg0 );
+
+ bNeg1 = extraBddSpaceFromFunctionNeg( dd, bF1 );
+ if ( bNeg1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ return NULL;
+ }
+ cuddRef( bNeg1 );
+
+ bRes1 = cuddBddAndRecur( dd, bNeg0, bNeg1 );
+ if ( bRes1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ Cudd_RecursiveDeref( dd, bNeg1 );
+ return NULL;
+ }
+ cuddRef( bRes1 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ Cudd_RecursiveDeref( dd, bNeg1 );
+
+
+ // consider the case when Res0 and Res1 are the same node
+ if ( bRes0 == bRes1 )
+ bRes = bRes1;
+ // consider the case when Res1 is complemented
+ else if ( Cudd_IsComplement(bRes1) )
+ {
+ bRes = cuddUniqueInter( dd, bFR->index, Cudd_Not(bRes1), Cudd_Not(bRes0) );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ bRes = Cudd_Not(bRes);
+ }
+ else
+ {
+ bRes = cuddUniqueInter( dd, bFR->index, bRes1, bRes0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ }
+ cuddDeref( bRes0 );
+ cuddDeref( bRes1 );
+
+ cuddCacheInsert1( dd, extraBddSpaceFromFunctionPos, bF, bRes );
+ return bRes;
+ }
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceFromFunctionPos().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceFromFunctionNeg( DdManager * dd, DdNode * bF )
+{
+ DdNode * bRes, * bFR;
+ statLine( dd );
+
+ bFR = Cudd_Regular(bF);
+ if ( cuddIsConstant(bFR) )
+ return b0;
+
+ if ( bRes = cuddCacheLookup1(dd, extraBddSpaceFromFunctionNeg, bF) )
+ return bRes;
+ else
+ {
+ DdNode * bF0, * bF1;
+ DdNode * bPos0, * bPos1;
+ DdNode * bNeg0, * bNeg1;
+ DdNode * bRes0, * bRes1;
+
+ if ( bFR != bF ) // bF is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+
+ bPos0 = extraBddSpaceFromFunctionNeg( dd, bF0 );
+ if ( bPos0 == NULL )
+ return NULL;
+ cuddRef( bPos0 );
+
+ bPos1 = extraBddSpaceFromFunctionNeg( dd, bF1 );
+ if ( bPos1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bPos0 );
+ return NULL;
+ }
+ cuddRef( bPos1 );
+
+ bRes0 = cuddBddAndRecur( dd, bPos0, bPos1 );
+ if ( bRes0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bPos0 );
+ Cudd_RecursiveDeref( dd, bPos1 );
+ return NULL;
+ }
+ cuddRef( bRes0 );
+ Cudd_RecursiveDeref( dd, bPos0 );
+ Cudd_RecursiveDeref( dd, bPos1 );
+
+
+ bNeg0 = extraBddSpaceFromFunctionPos( dd, bF0 );
+ if ( bNeg0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ return NULL;
+ }
+ cuddRef( bNeg0 );
+
+ bNeg1 = extraBddSpaceFromFunctionPos( dd, bF1 );
+ if ( bNeg1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ return NULL;
+ }
+ cuddRef( bNeg1 );
+
+ bRes1 = cuddBddAndRecur( dd, bNeg0, bNeg1 );
+ if ( bRes1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ Cudd_RecursiveDeref( dd, bNeg1 );
+ return NULL;
+ }
+ cuddRef( bRes1 );
+ Cudd_RecursiveDeref( dd, bNeg0 );
+ Cudd_RecursiveDeref( dd, bNeg1 );
+
+
+ // consider the case when Res0 and Res1 are the same node
+ if ( bRes0 == bRes1 )
+ bRes = bRes1;
+ // consider the case when Res1 is complemented
+ else if ( Cudd_IsComplement(bRes1) )
+ {
+ bRes = cuddUniqueInter( dd, bFR->index, Cudd_Not(bRes1), Cudd_Not(bRes0) );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ bRes = Cudd_Not(bRes);
+ }
+ else
+ {
+ bRes = cuddUniqueInter( dd, bFR->index, bRes1, bRes0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ }
+ cuddDeref( bRes0 );
+ cuddDeref( bRes1 );
+
+ cuddCacheInsert1( dd, extraBddSpaceFromFunctionNeg, bF, bRes );
+ return bRes;
+ }
+}
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceCanonVars().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceCanonVars( DdManager * dd, DdNode * bF )
+{
+ DdNode * bRes, * bFR;
+ statLine( dd );
+
+ bFR = Cudd_Regular(bF);
+ if ( cuddIsConstant(bFR) )
+ return bF;
+
+ if ( bRes = cuddCacheLookup1(dd, extraBddSpaceCanonVars, bF) )
+ return bRes;
+ else
+ {
+ DdNode * bF0, * bF1;
+ DdNode * bRes, * bRes0;
+
+ if ( bFR != bF ) // bF is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+ if ( bF0 == b0 )
+ {
+ bRes = extraBddSpaceCanonVars( dd, bF1 );
+ if ( bRes == NULL )
+ return NULL;
+ }
+ else if ( bF1 == b0 )
+ {
+ bRes = extraBddSpaceCanonVars( dd, bF0 );
+ if ( bRes == NULL )
+ return NULL;
+ }
+ else
+ {
+ bRes0 = extraBddSpaceCanonVars( dd, bF0 );
+ if ( bRes0 == NULL )
+ return NULL;
+ cuddRef( bRes0 );
+
+ bRes = cuddUniqueInter( dd, bFR->index, bRes0, b0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref( dd,bRes0 );
+ return NULL;
+ }
+ cuddDeref( bRes0 );
+ }
+
+ cuddCacheInsert1( dd, extraBddSpaceCanonVars, bF, bRes );
+ return bRes;
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceEquationsPos().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceEquationsPos( DdManager * dd, DdNode * bF )
+{
+ DdNode * zRes;
+ statLine( dd );
+
+ if ( bF == b0 )
+ return z1;
+ if ( bF == b1 )
+ return z0;
+
+ if ( zRes = cuddCacheLookup1Zdd(dd, extraBddSpaceEquationsPos, bF) )
+ return zRes;
+ else
+ {
+ DdNode * bFR, * bF0, * bF1;
+ DdNode * zPos0, * zPos1, * zNeg1;
+ DdNode * zRes, * zRes0, * zRes1;
+
+ bFR = Cudd_Regular(bF);
+ if ( bFR != bF ) // bF is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+ if ( bF0 == b0 )
+ {
+ zRes1 = extraBddSpaceEquationsPos( dd, bF1 );
+ if ( zRes1 == NULL )
+ return NULL;
+ cuddRef( zRes1 );
+
+ // add the current element to the set
+ zRes = cuddZddGetNode( dd, 2*bFR->index, z1, zRes1 );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes1);
+ return NULL;
+ }
+ cuddDeref( zRes1 );
+ }
+ else if ( bF1 == b0 )
+ {
+ zRes = extraBddSpaceEquationsPos( dd, bF0 );
+ if ( zRes == NULL )
+ return NULL;
+ }
+ else
+ {
+ zPos0 = extraBddSpaceEquationsPos( dd, bF0 );
+ if ( zPos0 == NULL )
+ return NULL;
+ cuddRef( zPos0 );
+
+ zPos1 = extraBddSpaceEquationsPos( dd, bF1 );
+ if ( zPos1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ return NULL;
+ }
+ cuddRef( zPos1 );
+
+ zNeg1 = extraBddSpaceEquationsNeg( dd, bF1 );
+ if ( zNeg1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zNeg1 );
+
+
+ zRes0 = cuddZddIntersect( dd, zPos0, zPos1 );
+ if ( zRes0 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zRes0 );
+
+ zRes1 = cuddZddIntersect( dd, zPos0, zNeg1 );
+ if ( zRes1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes0);
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zRes1 );
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ // only zRes0 and zRes1 are refed at this point
+
+ zRes = cuddZddGetNode( dd, 2*bFR->index, zRes1, zRes0 );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes0);
+ Cudd_RecursiveDerefZdd(dd, zRes1);
+ return NULL;
+ }
+ cuddDeref( zRes0 );
+ cuddDeref( zRes1 );
+ }
+
+ cuddCacheInsert1( dd, extraBddSpaceEquationsPos, bF, zRes );
+ return zRes;
+ }
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceEquationsNev().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceEquationsNeg( DdManager * dd, DdNode * bF )
+{
+ DdNode * zRes;
+ statLine( dd );
+
+ if ( bF == b0 )
+ return z1;
+ if ( bF == b1 )
+ return z0;
+
+ if ( zRes = cuddCacheLookup1Zdd(dd, extraBddSpaceEquationsNeg, bF) )
+ return zRes;
+ else
+ {
+ DdNode * bFR, * bF0, * bF1;
+ DdNode * zPos0, * zPos1, * zNeg1;
+ DdNode * zRes, * zRes0, * zRes1;
+
+ bFR = Cudd_Regular(bF);
+ if ( bFR != bF ) // bF is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+ if ( bF0 == b0 )
+ {
+ zRes = extraBddSpaceEquationsNeg( dd, bF1 );
+ if ( zRes == NULL )
+ return NULL;
+ }
+ else if ( bF1 == b0 )
+ {
+ zRes0 = extraBddSpaceEquationsNeg( dd, bF0 );
+ if ( zRes0 == NULL )
+ return NULL;
+ cuddRef( zRes0 );
+
+ // add the current element to the set
+ zRes = cuddZddGetNode( dd, 2*bFR->index, z1, zRes0 );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes0);
+ return NULL;
+ }
+ cuddDeref( zRes0 );
+ }
+ else
+ {
+ zPos0 = extraBddSpaceEquationsNeg( dd, bF0 );
+ if ( zPos0 == NULL )
+ return NULL;
+ cuddRef( zPos0 );
+
+ zPos1 = extraBddSpaceEquationsNeg( dd, bF1 );
+ if ( zPos1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ return NULL;
+ }
+ cuddRef( zPos1 );
+
+ zNeg1 = extraBddSpaceEquationsPos( dd, bF1 );
+ if ( zNeg1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zNeg1 );
+
+
+ zRes0 = cuddZddIntersect( dd, zPos0, zPos1 );
+ if ( zRes0 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zRes0 );
+
+ zRes1 = cuddZddIntersect( dd, zPos0, zNeg1 );
+ if ( zRes1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes0);
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ return NULL;
+ }
+ cuddRef( zRes1 );
+ Cudd_RecursiveDerefZdd(dd, zNeg1);
+ Cudd_RecursiveDerefZdd(dd, zPos0);
+ Cudd_RecursiveDerefZdd(dd, zPos1);
+ // only zRes0 and zRes1 are refed at this point
+
+ zRes = cuddZddGetNode( dd, 2*bFR->index, zRes1, zRes0 );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd(dd, zRes0);
+ Cudd_RecursiveDerefZdd(dd, zRes1);
+ return NULL;
+ }
+ cuddDeref( zRes0 );
+ cuddDeref( zRes1 );
+ }
+
+ cuddCacheInsert1( dd, extraBddSpaceEquationsNeg, bF, zRes );
+ return zRes;
+ }
+}
+
+
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceFromFunctionPos().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceFromMatrixPos( DdManager * dd, DdNode * zA )
+{
+ DdNode * bRes;
+ statLine( dd );
+
+ if ( zA == z0 )
+ return b1;
+ if ( zA == z1 )
+ return b1;
+
+ if ( bRes = cuddCacheLookup1(dd, extraBddSpaceFromMatrixPos, zA) )
+ return bRes;
+ else
+ {
+ DdNode * bP0, * bP1;
+ DdNode * bN0, * bN1;
+ DdNode * bRes0, * bRes1;
+
+ bP0 = extraBddSpaceFromMatrixPos( dd, cuddE(zA) );
+ if ( bP0 == NULL )
+ return NULL;
+ cuddRef( bP0 );
+
+ bP1 = extraBddSpaceFromMatrixPos( dd, cuddT(zA) );
+ if ( bP1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bP0 );
+ return NULL;
+ }
+ cuddRef( bP1 );
+
+ bRes0 = cuddBddAndRecur( dd, bP0, bP1 );
+ if ( bRes0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bP0 );
+ Cudd_RecursiveDeref( dd, bP1 );
+ return NULL;
+ }
+ cuddRef( bRes0 );
+ Cudd_RecursiveDeref( dd, bP0 );
+ Cudd_RecursiveDeref( dd, bP1 );
+
+
+ bN0 = extraBddSpaceFromMatrixPos( dd, cuddE(zA) );
+ if ( bN0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ return NULL;
+ }
+ cuddRef( bN0 );
+
+ bN1 = extraBddSpaceFromMatrixNeg( dd, cuddT(zA) );
+ if ( bN1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ return NULL;
+ }
+ cuddRef( bN1 );
+
+ bRes1 = cuddBddAndRecur( dd, bN0, bN1 );
+ if ( bRes1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ Cudd_RecursiveDeref( dd, bN1 );
+ return NULL;
+ }
+ cuddRef( bRes1 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ Cudd_RecursiveDeref( dd, bN1 );
+
+
+ // consider the case when Res0 and Res1 are the same node
+ if ( bRes0 == bRes1 )
+ bRes = bRes1;
+ // consider the case when Res1 is complemented
+ else if ( Cudd_IsComplement(bRes1) )
+ {
+ bRes = cuddUniqueInter( dd, zA->index/2, Cudd_Not(bRes1), Cudd_Not(bRes0) );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ bRes = Cudd_Not(bRes);
+ }
+ else
+ {
+ bRes = cuddUniqueInter( dd, zA->index/2, bRes1, bRes0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ }
+ cuddDeref( bRes0 );
+ cuddDeref( bRes1 );
+
+ cuddCacheInsert1( dd, extraBddSpaceFromMatrixPos, zA, bRes );
+ return bRes;
+ }
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Performs the recursive step of Extra_bddSpaceFromFunctionPos().]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+DdNode * extraBddSpaceFromMatrixNeg( DdManager * dd, DdNode * zA )
+{
+ DdNode * bRes;
+ statLine( dd );
+
+ if ( zA == z0 )
+ return b1;
+ if ( zA == z1 )
+ return b0;
+
+ if ( bRes = cuddCacheLookup1(dd, extraBddSpaceFromMatrixNeg, zA) )
+ return bRes;
+ else
+ {
+ DdNode * bP0, * bP1;
+ DdNode * bN0, * bN1;
+ DdNode * bRes0, * bRes1;
+
+ bP0 = extraBddSpaceFromMatrixNeg( dd, cuddE(zA) );
+ if ( bP0 == NULL )
+ return NULL;
+ cuddRef( bP0 );
+
+ bP1 = extraBddSpaceFromMatrixNeg( dd, cuddT(zA) );
+ if ( bP1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bP0 );
+ return NULL;
+ }
+ cuddRef( bP1 );
+
+ bRes0 = cuddBddAndRecur( dd, bP0, bP1 );
+ if ( bRes0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bP0 );
+ Cudd_RecursiveDeref( dd, bP1 );
+ return NULL;
+ }
+ cuddRef( bRes0 );
+ Cudd_RecursiveDeref( dd, bP0 );
+ Cudd_RecursiveDeref( dd, bP1 );
+
+
+ bN0 = extraBddSpaceFromMatrixNeg( dd, cuddE(zA) );
+ if ( bN0 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ return NULL;
+ }
+ cuddRef( bN0 );
+
+ bN1 = extraBddSpaceFromMatrixPos( dd, cuddT(zA) );
+ if ( bN1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ return NULL;
+ }
+ cuddRef( bN1 );
+
+ bRes1 = cuddBddAndRecur( dd, bN0, bN1 );
+ if ( bRes1 == NULL )
+ {
+ Cudd_RecursiveDeref( dd, bRes0 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ Cudd_RecursiveDeref( dd, bN1 );
+ return NULL;
+ }
+ cuddRef( bRes1 );
+ Cudd_RecursiveDeref( dd, bN0 );
+ Cudd_RecursiveDeref( dd, bN1 );
+
+
+ // consider the case when Res0 and Res1 are the same node
+ if ( bRes0 == bRes1 )
+ bRes = bRes1;
+ // consider the case when Res1 is complemented
+ else if ( Cudd_IsComplement(bRes1) )
+ {
+ bRes = cuddUniqueInter( dd, zA->index/2, Cudd_Not(bRes1), Cudd_Not(bRes0) );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ bRes = Cudd_Not(bRes);
+ }
+ else
+ {
+ bRes = cuddUniqueInter( dd, zA->index/2, bRes1, bRes0 );
+ if ( bRes == NULL )
+ {
+ Cudd_RecursiveDeref(dd,bRes0);
+ Cudd_RecursiveDeref(dd,bRes1);
+ return NULL;
+ }
+ }
+ cuddDeref( bRes0 );
+ cuddDeref( bRes1 );
+
+ cuddCacheInsert1( dd, extraBddSpaceFromMatrixNeg, zA, bRes );
+ return bRes;
+ }
+}
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of static functions */
+/*---------------------------------------------------------------------------*/
+
diff --git a/src/misc/extra/extraBddMisc.c b/src/misc/extra/extraBddMisc.c
index 932ed525..7d806ec7 100644
--- a/src/misc/extra/extraBddMisc.c
+++ b/src/misc/extra/extraBddMisc.c
@@ -719,6 +719,83 @@ DdNode * Extra_bddBitsToCube( DdManager * dd, int Code, int CodeWidth, DdNode **
return bResult;
} /* end of Extra_bddBitsToCube */
+/**Function********************************************************************
+
+ Synopsis [Finds the support as a negative polarity cube.]
+
+ Description [Finds the variables on which a DD depends. Returns a BDD
+ consisting of the product of the variables in the negative polarity
+ if successful; NULL otherwise.]
+
+ SideEffects [None]
+
+ SeeAlso [Cudd_VectorSupport Cudd_Support]
+
+******************************************************************************/
+DdNode * Extra_bddSupportNegativeCube( DdManager * dd, DdNode * f )
+{
+ int *support;
+ DdNode *res, *tmp, *var;
+ int i, j;
+ int size;
+
+ /* Allocate and initialize support array for ddSupportStep. */
+ size = ddMax( dd->size, dd->sizeZ );
+ support = ALLOC( int, size );
+ if ( support == NULL )
+ {
+ dd->errorCode = CUDD_MEMORY_OUT;
+ return ( NULL );
+ }
+ for ( i = 0; i < size; i++ )
+ {
+ support[i] = 0;
+ }
+
+ /* Compute support and clean up markers. */
+ ddSupportStep( Cudd_Regular( f ), support );
+ ddClearFlag( Cudd_Regular( f ) );
+
+ /* Transform support from array to cube. */
+ do
+ {
+ dd->reordered = 0;
+ res = DD_ONE( dd );
+ cuddRef( res );
+ for ( j = size - 1; j >= 0; j-- )
+ { /* for each level bottom-up */
+ i = ( j >= dd->size ) ? j : dd->invperm[j];
+ if ( support[i] == 1 )
+ {
+ var = cuddUniqueInter( dd, i, dd->one, Cudd_Not( dd->one ) );
+ //////////////////////////////////////////////////////////////////
+ var = Cudd_Not(var);
+ //////////////////////////////////////////////////////////////////
+ cuddRef( var );
+ tmp = cuddBddAndRecur( dd, res, var );
+ if ( tmp == NULL )
+ {
+ Cudd_RecursiveDeref( dd, res );
+ Cudd_RecursiveDeref( dd, var );
+ res = NULL;
+ break;
+ }
+ cuddRef( tmp );
+ Cudd_RecursiveDeref( dd, res );
+ Cudd_RecursiveDeref( dd, var );
+ res = tmp;
+ }
+ }
+ }
+ while ( dd->reordered == 1 );
+
+ FREE( support );
+ if ( res != NULL )
+ cuddDeref( res );
+ return ( res );
+
+} /* end of Extra_SupportNeg */
+
/*---------------------------------------------------------------------------*/
/* Definition of internal functions */
/*---------------------------------------------------------------------------*/
diff --git a/src/misc/extra/extraBddUnate.c b/src/misc/extra/extraBddUnate.c
new file mode 100644
index 00000000..b0297c77
--- /dev/null
+++ b/src/misc/extra/extraBddUnate.c
@@ -0,0 +1,641 @@
+/**CFile****************************************************************
+
+ FileName [extraBddUnate.c]
+
+ PackageName [extra]
+
+ Synopsis [Efficient methods to compute the information about
+ unate variables using an algorithm that is conceptually similar to
+ the algorithm for two-variable symmetry computation presented in:
+ A. Mishchenko. Fast Computation of Symmetries in Boolean Functions.
+ Transactions on CAD, Nov. 2003.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 2.0. Started - September 1, 2003.]
+
+ Revision [$Id: extraBddUnate.c,v 1.0 2003/09/01 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "extra.h"
+
+/*---------------------------------------------------------------------------*/
+/* Constant declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Stucture declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Type declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Variable declarations */
+/*---------------------------------------------------------------------------*/
+
+/*---------------------------------------------------------------------------*/
+/* Macro declarations */
+/*---------------------------------------------------------------------------*/
+
+/**AutomaticStart*************************************************************/
+
+/*---------------------------------------------------------------------------*/
+/* Static function prototypes */
+/*---------------------------------------------------------------------------*/
+
+/**AutomaticEnd***************************************************************/
+
+/*---------------------------------------------------------------------------*/
+/* Definition of exported functions */
+/*---------------------------------------------------------------------------*/
+
+
+/**Function********************************************************************
+
+ Synopsis [Computes the classical symmetry information for the function.]
+
+ Description [Returns the symmetry information in the form of Extra_UnateInfo_t structure.]
+
+ SideEffects [If the ZDD variables are not derived from BDD variables with
+ multiplicity 2, this function may derive them in a wrong way.]
+
+ SeeAlso []
+
+******************************************************************************/
+Extra_UnateInfo_t * Extra_UnateComputeFast(
+ DdManager * dd, /* the manager */
+ DdNode * bFunc) /* the function whose symmetries are computed */
+{
+ DdNode * bSupp;
+ DdNode * zRes;
+ Extra_UnateInfo_t * p;
+
+ bSupp = Cudd_Support( dd, bFunc ); Cudd_Ref( bSupp );
+ zRes = Extra_zddUnateInfoCompute( dd, bFunc, bSupp ); Cudd_Ref( zRes );
+
+ p = Extra_UnateInfoCreateFromZdd( dd, zRes, bSupp );
+
+ Cudd_RecursiveDeref( dd, bSupp );
+ Cudd_RecursiveDerefZdd( dd, zRes );
+
+ return p;
+
+} /* end of Extra_UnateInfoCompute */
+
+
+/**Function********************************************************************
+
+ Synopsis [Computes the classical symmetry information as a ZDD.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+DdNode * Extra_zddUnateInfoCompute(
+ DdManager * dd, /* the DD manager */
+ DdNode * bF,
+ DdNode * bVars)
+{
+ DdNode * res;
+ do {
+ dd->reordered = 0;
+ res = extraZddUnateInfoCompute( dd, bF, bVars );
+ } while (dd->reordered == 1);
+ return(res);
+
+} /* end of Extra_zddUnateInfoCompute */
+
+
+/**Function********************************************************************
+
+ Synopsis [Converts a set of variables into a set of singleton subsets.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+DdNode * Extra_zddGetSingletonsBoth(
+ DdManager * dd, /* the DD manager */
+ DdNode * bVars) /* the set of variables */
+{
+ DdNode * res;
+ do {
+ dd->reordered = 0;
+ res = extraZddGetSingletonsBoth( dd, bVars );
+ } while (dd->reordered == 1);
+ return(res);
+
+} /* end of Extra_zddGetSingletonsBoth */
+
+/**Function********************************************************************
+
+ Synopsis [Allocates unateness information structure.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+Extra_UnateInfo_t * Extra_UnateInfoAllocate( int nVars )
+{
+ Extra_UnateInfo_t * p;
+ // allocate and clean the storage for unateness info
+ p = ALLOC( Extra_UnateInfo_t, 1 );
+ memset( p, 0, sizeof(Extra_UnateInfo_t) );
+ p->nVars = nVars;
+ p->pVars = ALLOC( Extra_UnateVar_t, nVars );
+ memset( p->pVars, 0, nVars * sizeof(Extra_UnateVar_t) );
+ return p;
+} /* end of Extra_UnateInfoAllocate */
+
+/**Function********************************************************************
+
+ Synopsis [Deallocates symmetry information structure.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+void Extra_UnateInfoDissolve( Extra_UnateInfo_t * p )
+{
+ free( p->pVars );
+ free( p );
+} /* end of Extra_UnateInfoDissolve */
+
+/**Function********************************************************************
+
+ Synopsis [Allocates symmetry information structure.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+void Extra_UnateInfoPrint( Extra_UnateInfo_t * p )
+{
+ char * pBuffer;
+ int i;
+ pBuffer = ALLOC( char, p->nVarsMax+1 );
+ memset( pBuffer, ' ', p->nVarsMax );
+ pBuffer[p->nVarsMax] = 0;
+ for ( i = 0; i < p->nVars; i++ )
+ if ( p->pVars[i].Neg )
+ pBuffer[ p->pVars[i].iVar ] = 'n';
+ else if ( p->pVars[i].Pos )
+ pBuffer[ p->pVars[i].iVar ] = 'p';
+ else
+ pBuffer[ p->pVars[i].iVar ] = '.';
+ printf( "%s\n", pBuffer );
+ free( pBuffer );
+} /* end of Extra_UnateInfoPrint */
+
+
+/**Function********************************************************************
+
+ Synopsis [Creates the symmetry information structure from ZDD.]
+
+ Description [ZDD representation of symmetries is the set of cubes, each
+ of which has two variables in the positive polarity. These variables correspond
+ to the symmetric variable pair.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+Extra_UnateInfo_t * Extra_UnateInfoCreateFromZdd( DdManager * dd, DdNode * zPairs, DdNode * bSupp )
+{
+ Extra_UnateInfo_t * p;
+ DdNode * bTemp, * zSet, * zCube, * zTemp;
+ int * pMapVars2Nums;
+ int i, nSuppSize;
+
+ nSuppSize = Extra_bddSuppSize( dd, bSupp );
+
+ // allocate and clean the storage for symmetry info
+ p = Extra_UnateInfoAllocate( nSuppSize );
+
+ // allocate the storage for the temporary map
+ pMapVars2Nums = ALLOC( int, dd->size );
+ memset( pMapVars2Nums, 0, dd->size * sizeof(int) );
+
+ // assign the variables
+ p->nVarsMax = dd->size;
+ for ( i = 0, bTemp = bSupp; bTemp != b1; bTemp = cuddT(bTemp), i++ )
+ {
+ p->pVars[i].iVar = bTemp->index;
+ pMapVars2Nums[bTemp->index] = i;
+ }
+
+ // write the symmetry info into the structure
+ zSet = zPairs; Cudd_Ref( zSet );
+// Cudd_zddPrintCover( dd, zPairs ); printf( "\n" );
+ while ( zSet != z0 )
+ {
+ // get the next cube
+ zCube = Extra_zddSelectOneSubset( dd, zSet ); Cudd_Ref( zCube );
+
+ // add this var to the data structure
+ assert( cuddT(zCube) == z1 && cuddE(zCube) == z0 );
+ if ( zCube->index & 1 ) // neg
+ p->pVars[ pMapVars2Nums[zCube->index/2] ].Neg = 1;
+ else
+ p->pVars[ pMapVars2Nums[zCube->index/2] ].Pos = 1;
+ // count the unate vars
+ p->nUnate++;
+
+ // update the cuver and deref the cube
+ zSet = Cudd_zddDiff( dd, zTemp = zSet, zCube ); Cudd_Ref( zSet );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zCube );
+
+ } // for each cube
+ Cudd_RecursiveDerefZdd( dd, zSet );
+ FREE( pMapVars2Nums );
+ return p;
+
+} /* end of Extra_UnateInfoCreateFromZdd */
+
+
+
+/**Function********************************************************************
+
+ Synopsis [Computes the classical unateness information for the function.]
+
+ Description [Uses the naive way of comparing cofactors.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+Extra_UnateInfo_t * Extra_UnateComputeSlow( DdManager * dd, DdNode * bFunc )
+{
+ int nSuppSize;
+ DdNode * bSupp, * bTemp;
+ Extra_UnateInfo_t * p;
+ int i, Res;
+
+ // compute the support
+ bSupp = Cudd_Support( dd, bFunc ); Cudd_Ref( bSupp );
+ nSuppSize = Extra_bddSuppSize( dd, bSupp );
+//printf( "Support = %d. ", nSuppSize );
+//Extra_bddPrint( dd, bSupp );
+//printf( "%d ", nSuppSize );
+
+ // allocate the storage for symmetry info
+ p = Extra_UnateInfoAllocate( nSuppSize );
+
+ // assign the variables
+ p->nVarsMax = dd->size;
+ for ( i = 0, bTemp = bSupp; bTemp != b1; bTemp = cuddT(bTemp), i++ )
+ {
+ Res = Extra_bddCheckUnateNaive( dd, bFunc, bTemp->index );
+ p->pVars[i].iVar = bTemp->index;
+ if ( Res == -1 )
+ p->pVars[i].Neg = 1;
+ else if ( Res == 1 )
+ p->pVars[i].Pos = 1;
+ p->nUnate += (Res != 0);
+ }
+ Cudd_RecursiveDeref( dd, bSupp );
+ return p;
+
+} /* end of Extra_UnateComputeSlow */
+
+/**Function********************************************************************
+
+ Synopsis [Checks if the two variables are symmetric.]
+
+ Description [Returns 0 if vars are not unate. Return -1/+1 if the var is neg/pos unate.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+int Extra_bddCheckUnateNaive(
+ DdManager * dd, /* the DD manager */
+ DdNode * bF,
+ int iVar)
+{
+ DdNode * bCof0, * bCof1;
+ int Res;
+
+ assert( iVar < dd->size );
+
+ bCof0 = Cudd_Cofactor( dd, bF, Cudd_Not(Cudd_bddIthVar(dd,iVar)) ); Cudd_Ref( bCof0 );
+ bCof1 = Cudd_Cofactor( dd, bF, Cudd_bddIthVar(dd,iVar) ); Cudd_Ref( bCof1 );
+
+ if ( Cudd_bddLeq( dd, bCof0, bCof1 ) )
+ Res = 1;
+ else if ( Cudd_bddLeq( dd, bCof1, bCof0 ) )
+ Res =-1;
+ else
+ Res = 0;
+
+ Cudd_RecursiveDeref( dd, bCof0 );
+ Cudd_RecursiveDeref( dd, bCof1 );
+ return Res;
+} /* end of Extra_bddCheckUnateNaive */
+
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of internal functions */
+/*---------------------------------------------------------------------------*/
+
+/**Function********************************************************************
+
+ Synopsis [Performs a recursive step of Extra_UnateInfoCompute.]
+
+ Description [Returns the set of symmetric variable pairs represented as a set
+ of two-literal ZDD cubes. Both variables always appear in the positive polarity
+ in the cubes. This function works without building new BDD nodes. Some relatively
+ small number of ZDD nodes may be built to ensure proper bookkeeping of the
+ symmetry information.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+DdNode *
+extraZddUnateInfoCompute(
+ DdManager * dd, /* the manager */
+ DdNode * bFunc, /* the function whose symmetries are computed */
+ DdNode * bVars ) /* the set of variables on which this function depends */
+{
+ DdNode * zRes;
+ DdNode * bFR = Cudd_Regular(bFunc);
+
+ if ( cuddIsConstant(bFR) )
+ {
+ if ( cuddIsConstant(bVars) )
+ return z0;
+ return extraZddGetSingletonsBoth( dd, bVars );
+ }
+ assert( bVars != b1 );
+
+ if ( zRes = cuddCacheLookup2Zdd(dd, extraZddUnateInfoCompute, bFunc, bVars) )
+ return zRes;
+ else
+ {
+ DdNode * zRes0, * zRes1;
+ DdNode * zTemp, * zPlus;
+ DdNode * bF0, * bF1;
+ DdNode * bVarsNew;
+ int nVarsExtra;
+ int LevelF;
+ int AddVar;
+
+ // every variable in bF should be also in bVars, therefore LevelF cannot be above LevelV
+ // if LevelF is below LevelV, scroll through the vars in bVars to the same level as F
+ // count how many extra vars are there in bVars
+ nVarsExtra = 0;
+ LevelF = dd->perm[bFR->index];
+ for ( bVarsNew = bVars; LevelF > dd->perm[bVarsNew->index]; bVarsNew = cuddT(bVarsNew) )
+ nVarsExtra++;
+ // the indexes (level) of variables should be synchronized now
+ assert( bFR->index == bVarsNew->index );
+
+ // cofactor the function
+ if ( bFR != bFunc ) // bFunc is complemented
+ {
+ bF0 = Cudd_Not( cuddE(bFR) );
+ bF1 = Cudd_Not( cuddT(bFR) );
+ }
+ else
+ {
+ bF0 = cuddE(bFR);
+ bF1 = cuddT(bFR);
+ }
+
+ // solve subproblems
+ zRes0 = extraZddUnateInfoCompute( dd, bF0, cuddT(bVarsNew) );
+ if ( zRes0 == NULL )
+ return NULL;
+ cuddRef( zRes0 );
+
+ // if there is no symmetries in the negative cofactor
+ // there is no need to test the positive cofactor
+ if ( zRes0 == z0 )
+ zRes = zRes0; // zRes takes reference
+ else
+ {
+ zRes1 = extraZddUnateInfoCompute( dd, bF1, cuddT(bVarsNew) );
+ if ( zRes1 == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes0 );
+ return NULL;
+ }
+ cuddRef( zRes1 );
+
+ // only those variables are pair-wise symmetric
+ // that are pair-wise symmetric in both cofactors
+ // therefore, intersect the solutions
+ zRes = cuddZddIntersect( dd, zRes0, zRes1 );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes0 );
+ Cudd_RecursiveDerefZdd( dd, zRes1 );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zRes0 );
+ Cudd_RecursiveDerefZdd( dd, zRes1 );
+ }
+
+ // consider the current top-most variable
+ AddVar = -1;
+ if ( Cudd_bddLeq( dd, bF0, bF1 ) ) // pos
+ AddVar = 0;
+ else if ( Cudd_bddLeq( dd, bF1, bF0 ) ) // neg
+ AddVar = 1;
+ if ( AddVar >= 0 )
+ {
+ // create the singleton
+ zPlus = cuddZddGetNode( dd, 2*bFR->index + AddVar, z1, z0 );
+ if ( zPlus == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes );
+ return NULL;
+ }
+ cuddRef( zPlus );
+
+ // add these to the result
+ zRes = cuddZddUnion( dd, zTemp = zRes, zPlus );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ }
+ // only zRes is referenced at this point
+
+ // if we skipped some variables, these variables cannot be symmetric with
+ // any variables that are currently in the support of bF, but they can be
+ // symmetric with the variables that are in bVars but not in the support of bF
+ for ( bVarsNew = bVars; LevelF > dd->perm[bVarsNew->index]; bVarsNew = cuddT(bVarsNew) )
+ {
+ // create the negative singleton
+ zPlus = cuddZddGetNode( dd, 2*bVarsNew->index+1, z1, z0 );
+ if ( zPlus == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes );
+ return NULL;
+ }
+ cuddRef( zPlus );
+
+ // add these to the result
+ zRes = cuddZddUnion( dd, zTemp = zRes, zPlus );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+
+
+ // create the positive singleton
+ zPlus = cuddZddGetNode( dd, 2*bVarsNew->index, z1, z0 );
+ if ( zPlus == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes );
+ return NULL;
+ }
+ cuddRef( zPlus );
+
+ // add these to the result
+ zRes = cuddZddUnion( dd, zTemp = zRes, zPlus );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ }
+ cuddDeref( zRes );
+
+ /* insert the result into cache */
+ cuddCacheInsert2(dd, extraZddUnateInfoCompute, bFunc, bVars, zRes);
+ return zRes;
+ }
+} /* end of extraZddUnateInfoCompute */
+
+
+/**Function********************************************************************
+
+ Synopsis [Performs a recursive step of Extra_zddGetSingletons.]
+
+ Description [Returns the set of ZDD singletons, containing those pos/neg
+ polarity ZDD variables that correspond to the BDD variables in bVars.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+DdNode * extraZddGetSingletonsBoth(
+ DdManager * dd, /* the DD manager */
+ DdNode * bVars) /* the set of variables */
+{
+ DdNode * zRes;
+
+ if ( bVars == b1 )
+ return z1;
+
+ if ( zRes = cuddCacheLookup1Zdd(dd, extraZddGetSingletonsBoth, bVars) )
+ return zRes;
+ else
+ {
+ DdNode * zTemp, * zPlus;
+
+ // solve subproblem
+ zRes = extraZddGetSingletonsBoth( dd, cuddT(bVars) );
+ if ( zRes == NULL )
+ return NULL;
+ cuddRef( zRes );
+
+
+ // create the negative singleton
+ zPlus = cuddZddGetNode( dd, 2*bVars->index+1, z1, z0 );
+ if ( zPlus == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes );
+ return NULL;
+ }
+ cuddRef( zPlus );
+
+ // add these to the result
+ zRes = cuddZddUnion( dd, zTemp = zRes, zPlus );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+
+
+ // create the positive singleton
+ zPlus = cuddZddGetNode( dd, 2*bVars->index, z1, z0 );
+ if ( zPlus == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zRes );
+ return NULL;
+ }
+ cuddRef( zPlus );
+
+ // add these to the result
+ zRes = cuddZddUnion( dd, zTemp = zRes, zPlus );
+ if ( zRes == NULL )
+ {
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+ return NULL;
+ }
+ cuddRef( zRes );
+ Cudd_RecursiveDerefZdd( dd, zTemp );
+ Cudd_RecursiveDerefZdd( dd, zPlus );
+
+ cuddDeref( zRes );
+ cuddCacheInsert1( dd, extraZddGetSingletonsBoth, bVars, zRes );
+ return zRes;
+ }
+} /* end of extraZddGetSingletonsBoth */
+
+
+/*---------------------------------------------------------------------------*/
+/* Definition of static Functions */
+/*---------------------------------------------------------------------------*/
diff --git a/src/misc/extra/extraUtilCanon.c b/src/misc/extra/extraUtilCanon.c
index 9d4e5b5d..fcc7d84d 100644
--- a/src/misc/extra/extraUtilCanon.c
+++ b/src/misc/extra/extraUtilCanon.c
@@ -99,7 +99,8 @@ int Extra_TruthCanonFastN( int nVarsMax, int nVarsReal, unsigned * pt, unsigned
Description []
- SideEffects []
+ SideEffects [This procedure has a bug, which shows on Solaris.
+ Most likely has something to do with the casts, i.g *((unsigned *)pt0)]
SeeAlso []
@@ -129,21 +130,22 @@ int Extra_TruthCanonN_rec( int nVars, unsigned char * pt, unsigned ** pptRes, ch
pt0 = pt;
pt1 = pt + (1 << nVarsN) / 8;
// 5-var truth tables for this call
- uInit0 = *((unsigned *)pt0);
- uInit1 = *((unsigned *)pt1);
+// uInit0 = *((unsigned *)pt0);
+// uInit1 = *((unsigned *)pt1);
if ( nVarsN == 3 )
{
- uInit0 &= 0xFF;
- uInit1 &= 0xFF;
- uInit0 = (uInit0 << 24) | (uInit0 << 16) | (uInit0 << 8) | uInit0;
- uInit1 = (uInit1 << 24) | (uInit1 << 16) | (uInit1 << 8) | uInit1;
+ uInit0 = (pt0[0] << 24) | (pt0[0] << 16) | (pt0[0] << 8) | pt0[0];
+ uInit1 = (pt1[0] << 24) | (pt1[0] << 16) | (pt1[0] << 8) | pt1[0];
}
else if ( nVarsN == 4 )
{
- uInit0 &= 0xFFFF;
- uInit1 &= 0xFFFF;
- uInit0 = (uInit0 << 16) | uInit0;
- uInit1 = (uInit1 << 16) | uInit1;
+ uInit0 = (pt0[1] << 24) | (pt0[0] << 16) | (pt0[1] << 8) | pt0[0];
+ uInit1 = (pt1[1] << 24) | (pt1[0] << 16) | (pt1[1] << 8) | pt1[0];
+ }
+ else
+ {
+ uInit0 = (pt0[3] << 24) | (pt0[2] << 16) | (pt0[1] << 8) | pt0[0];
+ uInit1 = (pt1[3] << 24) | (pt1[2] << 16) | (pt1[1] << 8) | pt1[0];
}
// storage for truth tables and phases
diff --git a/src/misc/extra/extraUtilReader.c b/src/misc/extra/extraUtilReader.c
index 016f01e3..6e16b399 100644
--- a/src/misc/extra/extraUtilReader.c
+++ b/src/misc/extra/extraUtilReader.c
@@ -262,6 +262,9 @@ void * Extra_FileReaderGetTokens_int( Extra_FileReader_t * p )
// check if the new data should to be loaded
if ( p->pBufferCur > p->pBufferStop )
Extra_FileReaderReload( p );
+
+// printf( "%d\n", p->pBufferEnd - p->pBufferCur );
+
// process the string starting from the current position
for ( pChar = p->pBufferCur; pChar < p->pBufferEnd; pChar++ )
{
@@ -270,6 +273,10 @@ void * Extra_FileReaderGetTokens_int( Extra_FileReader_t * p )
p->nLineCounter++;
// switch depending on the character
MapValue = p->pCharMap[*pChar];
+
+// printf( "Char value = %d. Map value = %d.\n", *pChar, MapValue );
+
+
switch ( MapValue )
{
case EXTRA_CHAR_COMMENT:
@@ -326,6 +333,14 @@ void * Extra_FileReaderGetTokens_int( Extra_FileReader_t * p )
return p->vTokens;
}
printf( "Extra_FileReader failed to parse the file \"%s\".\n", p->pFileName );
+/*
+ {
+ int i;
+ for ( i = 0; i < p->vTokens->nSize; i++ )
+ printf( "%s ", p->vTokens->pArray[i] );
+ printf( "\n" );
+ }
+*/
return NULL;
}
diff --git a/src/misc/extra/module.make b/src/misc/extra/module.make
index 42a0d84f..8e7b1772 100644
--- a/src/misc/extra/module.make
+++ b/src/misc/extra/module.make
@@ -1,4 +1,5 @@
-SRC += src/misc/extra/extraBddKmap.c \
+SRC += src/misc/extra/extraBddAuto.c \
+ src/misc/extra/extraBddKmap.c \
src/misc/extra/extraBddMisc.c \
src/misc/extra/extraBddSymm.c \
src/misc/extra/extraUtilBitMatrix.c \
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-07 11:45:38 +0000