abcBridge-0.10.0.0: abc-build/src/proof/live/combination.c

#include <stdio.h>
#include "base/main/main.h"
#include "aig/aig/aig.h"
#include "aig/saig/saig.h"
#include <string.h>
#include "base/main/mainInt.h"
#include "proof/pdr/pdr.h"
#include <time.h>

ABC_NAMESPACE_IMPL_START

long countCombination(long n, long k)
{
	assert( n >= k );
	if( n == k ) return 1;
	if( k == 1 ) return n;
	return countCombination( n-1, k-1 ) + countCombination( n-1, k );
}	

void listCombination(int n, int t)
{
	Vec_Int_t *vC;
	int i, j, combCounter = 0;

	//Initialization
	vC = Vec_IntAlloc(t+3);
	for(i=-1; i<t; i++)
		Vec_IntPush( vC, i );
	Vec_IntPush( vC, n );
	Vec_IntPush( vC, 0 );

	while(1)
	{
		//visit combination
		printf("Comb-%3d : ", ++combCounter);
		for( i=t; i>0; i--)
			printf("vC[%d] = %d ", i, Vec_IntEntry(vC, i));
		printf("\n");

		j = 1;
		while( Vec_IntEntry( vC, j ) + 1 == Vec_IntEntry( vC, j+1 ) )
		{
			//printf("\nGochon = %d, %d\n", Vec_IntEntry( vC, j ) + 1, Vec_IntEntry( vC, j+1 ));
			Vec_IntWriteEntry( vC, j, j-1 );
			j = j + 1;
		}
		if( j > t ) break;
		Vec_IntWriteEntry( vC, j, Vec_IntEntry( vC, j ) + 1 );
	}
	
	Vec_IntFree(vC);	
}

int generateCombinatorialStabil( Aig_Man_t *pAigNew, Aig_Man_t *pAigOld, 
				Vec_Int_t *vCandidateMonotoneSignals_,
				Vec_Ptr_t *vDisj_nCk_,
				int combN, int combK )
{
	Aig_Obj_t *pObjMonoCand, *pObj;
	int targetPoIndex;

	//Knuth's Data Strcuture
	int totalCombination_KNUTH = 0;
	Vec_Int_t *vC_KNUTH;
	int i_KNUTH, j_KNUTH;

	//Knuth's Data Structure Initialization
	vC_KNUTH = Vec_IntAlloc(combK+3);
	for(i_KNUTH=-1; i_KNUTH<combK; i_KNUTH++)
		Vec_IntPush( vC_KNUTH, i_KNUTH );
	Vec_IntPush( vC_KNUTH, combN );
	Vec_IntPush( vC_KNUTH, 0 );

	while(1)
	{
		totalCombination_KNUTH++;
		pObjMonoCand = Aig_Not(Aig_ManConst1(pAigNew));
		for( i_KNUTH=combK; i_KNUTH>0; i_KNUTH--)
		{
			targetPoIndex = Vec_IntEntry( vCandidateMonotoneSignals_, Vec_IntEntry(vC_KNUTH, i_KNUTH));
			pObj = Aig_ObjChild0Copy(Aig_ManCo( pAigOld, targetPoIndex ));
			pObjMonoCand = Aig_Or( pAigNew, pObj, pObjMonoCand );
		}
		Vec_PtrPush(vDisj_nCk_, pObjMonoCand );

		j_KNUTH = 1;
		while( Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 == Vec_IntEntry( vC_KNUTH, j_KNUTH+1 ) )
		{
			Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, j_KNUTH-1 );
			j_KNUTH = j_KNUTH + 1;
		}
		if( j_KNUTH > combK ) break;
		Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 );
	}

	Vec_IntFree(vC_KNUTH);

	return totalCombination_KNUTH;
}

int generateCombinatorialStabilExhaust( Aig_Man_t *pAigNew, Aig_Man_t *pAigOld, 
				Vec_Ptr_t *vDisj_nCk_,
				int combN, int combK )
{
	Aig_Obj_t *pObjMonoCand, *pObj;
	int targetPoIndex;

	//Knuth's Data Strcuture
	int totalCombination_KNUTH = 0;
	Vec_Int_t *vC_KNUTH;
	int i_KNUTH, j_KNUTH;

	//Knuth's Data Structure Initialization
	vC_KNUTH = Vec_IntAlloc(combK+3);
	for(i_KNUTH=-1; i_KNUTH<combK; i_KNUTH++)
		Vec_IntPush( vC_KNUTH, i_KNUTH );
	Vec_IntPush( vC_KNUTH, combN );
	Vec_IntPush( vC_KNUTH, 0 );

	while(1)
	{
		totalCombination_KNUTH++;
		pObjMonoCand = Aig_Not(Aig_ManConst1(pAigNew));
		for( i_KNUTH=combK; i_KNUTH>0; i_KNUTH--)
		{
			//targetPoIndex = Vec_IntEntry( vCandidateMonotoneSignals_, Vec_IntEntry(vC_KNUTH, i_KNUTH));
			targetPoIndex = Vec_IntEntry(vC_KNUTH, i_KNUTH);
			pObj = (Aig_Obj_t *)(Aig_ManLo( pAigOld, targetPoIndex )->pData);
			pObjMonoCand = Aig_Or( pAigNew, pObj, pObjMonoCand );
		}
		Vec_PtrPush(vDisj_nCk_, pObjMonoCand );

		j_KNUTH = 1;
		while( Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 == Vec_IntEntry( vC_KNUTH, j_KNUTH+1 ) )
		{
			Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, j_KNUTH-1 );
			j_KNUTH = j_KNUTH + 1;
		}
		if( j_KNUTH > combK ) break;
		Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 );
	}

	Vec_IntFree(vC_KNUTH);

	return totalCombination_KNUTH;
}

Aig_Man_t *generateDisjunctiveTester( Abc_Ntk_t *pNtk, Aig_Man_t *pAig, int combN, int combK )
{
	//AIG creation related data structure
	Aig_Man_t *pNewAig;
	int piCopied = 0, loCopied = 0, loCreated = 0, liCopied = 0, liCreated = 0, poCopied = 0;
	//int i, iElem, nRegCount, hintSingalBeginningMarker, hintSingalEndMarker;
	int i, nRegCount, hintSingalBeginningMarker, hintSingalEndMarker;
	int combN_internal, combK_internal; //, targetPoIndex;
	long longI, lCombinationCount;
	//Aig_Obj_t *pObj, *pObjMonoCand, *pObjLO_nCk, *pObjDisj_nCk;
	Aig_Obj_t *pObj, *pObjLO_nCk, *pObjDisj_nCk;
	Vec_Ptr_t *vLO_nCk, *vPODriver_nCk, *vDisj_nCk;
	Vec_Int_t *vCandidateMonotoneSignals;

	extern Vec_Int_t *findHintOutputs(Abc_Ntk_t *pNtk);
	
	//Knuth's Data Strcuture
	//Vec_Int_t *vC_KNUTH;
	//int i_KNUTH, j_KNUTH, combCounter_KNUTH = 0;

	//Collecting target HINT signals
	vCandidateMonotoneSignals = findHintOutputs(pNtk);
	if( vCandidateMonotoneSignals == NULL )
	{
		printf("\nTraget Signal Set is Empty: Duplicating given AIG\n");
		combN_internal = 0;
	}
	else
	{
		//Vec_IntForEachEntry( vCandidateMonotoneSignals, iElem, i )
		//	printf("Po[%d] = %s\n", iElem, Abc_ObjName( Abc_NtkPo(pNtk, iElem) ) );
		hintSingalBeginningMarker = Vec_IntEntry( vCandidateMonotoneSignals, 0 );
		hintSingalEndMarker = Vec_IntEntry( vCandidateMonotoneSignals, Vec_IntSize(vCandidateMonotoneSignals) - 1 );
		combN_internal = hintSingalEndMarker - hintSingalBeginningMarker + 1;
	}

	//combK_internal = combK;

	//Knuth's Data Structure Initialization
	//vC_KNUTH = Vec_IntAlloc(combK_internal+3);
	//for(i_KNUTH=-1; i_KNUTH<combK_internal; i_KNUTH++)
	//	Vec_IntPush( vC_KNUTH, i_KNUTH );
	//Vec_IntPush( vC_KNUTH, combN_internal );
	//Vec_IntPush( vC_KNUTH, 0 );

	//Standard AIG duplication begins
	//Standard AIG Manager Creation
	pNewAig = Aig_ManStart( Aig_ManObjNumMax(pAig) );
	pNewAig->pName = (char *)malloc( strlen( pAig->pName ) + strlen("_nCk") + 1 );
	sprintf(pNewAig->pName, "%s_%s", pAig->pName, "nCk");
    	pNewAig->pSpec = NULL;

	//Standard Mapping of Constant Nodes
	pObj = Aig_ManConst1( pAig );
    	pObj->pData = Aig_ManConst1( pNewAig );

	//Standard AIG PI duplication
	Saig_ManForEachPi( pAig, pObj, i )
	{
		piCopied++;
		pObj->pData = Aig_ObjCreateCi(pNewAig);
	}

	//Standard AIG LO duplication
	Saig_ManForEachLo( pAig, pObj, i )
    	{
		loCopied++;
		pObj->pData = Aig_ObjCreateCi(pNewAig);
    	}

	//nCk LO creation
	lCombinationCount = 0;
	for(combK_internal=1; combK_internal<=combK; combK_internal++)
		lCombinationCount += countCombination( combN_internal, combK_internal );
	assert( lCombinationCount > 0 );
	vLO_nCk = Vec_PtrAlloc(lCombinationCount);
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		loCreated++;
		pObj = Aig_ObjCreateCi(pNewAig);
		Vec_PtrPush( vLO_nCk, pObj );
	}

	//Standard Node duplication
	Aig_ManForEachNode( pAig, pObj, i )
	{
		pObj->pData = Aig_And( pNewAig, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
	}
	
	//nCk specific logic creation (i.e. nCk number of OR gates)
	vDisj_nCk = Vec_PtrAlloc(lCombinationCount);

	

	//while(1)
	//{
	//	//visit combination
	//	//printf("Comb-%3d : ", ++combCounter_KNUTH);
	//	pObjMonoCand = Aig_Not(Aig_ManConst1(pNewAig));
	//	for( i_KNUTH=combK_internal; i_KNUTH>0; i_KNUTH--)
	//	{
	//		//printf("vC[%d] = %d ", i_KNUTH, Vec_IntEntry(vC_KNUTH, i_KNUTH));
	//		targetPoIndex = Vec_IntEntry( vCandidateMonotoneSignals, Vec_IntEntry(vC_KNUTH, i_KNUTH));
	//		pObj = Aig_ObjChild0Copy(Aig_ManCo( pAig, targetPoIndex ));
	//		pObjMonoCand = Aig_Or( pNewAig, pObj, pObjMonoCand );
	//	}
	//	Vec_PtrPush(vDisj_nCk, pObjMonoCand );
	//	//printf("\n");

	//	j_KNUTH = 1;
	//	while( Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 == Vec_IntEntry( vC_KNUTH, j_KNUTH+1 ) )
	//	{
	//		Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, j_KNUTH-1 );
	//		j_KNUTH = j_KNUTH + 1;
	//	}
	//	if( j_KNUTH > combK_internal ) break;
	//	Vec_IntWriteEntry( vC_KNUTH, j_KNUTH, Vec_IntEntry( vC_KNUTH, j_KNUTH ) + 1 );
	//}
	for( combK_internal=1; combK_internal<=combK; combK_internal++ )
		generateCombinatorialStabil( pNewAig, pAig, vCandidateMonotoneSignals,
				vDisj_nCk, combN_internal, combK_internal );


	//creation of implication logic
	vPODriver_nCk = Vec_PtrAlloc(lCombinationCount);
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		pObjLO_nCk = (Aig_Obj_t *)(Vec_PtrEntry( vLO_nCk, longI ));
		pObjDisj_nCk = (Aig_Obj_t *)(Vec_PtrEntry( vDisj_nCk, longI ));

		pObj = Aig_Or( pNewAig, Aig_Not(pObjDisj_nCk), pObjLO_nCk);
		Vec_PtrPush(vPODriver_nCk, pObj);
	}
	
	//Standard PO duplication
	Saig_ManForEachPo( pAig, pObj, i )
	{
		poCopied++;
		pObj->pData = Aig_ObjCreateCo( pNewAig, Aig_ObjChild0Copy(pObj) ); 
	}

	//nCk specific PO creation
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		Aig_ObjCreateCo( pNewAig, (Aig_Obj_t *)(Vec_PtrEntry( vPODriver_nCk, longI )) );
	}

	//Standard LI duplication
	Saig_ManForEachLi( pAig, pObj, i )
	{
		liCopied++;
		Aig_ObjCreateCo( pNewAig, Aig_ObjChild0Copy(pObj) );
	}

	//nCk specific LI creation
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		liCreated++;
		Aig_ObjCreateCo( pNewAig, (Aig_Obj_t *)(Vec_PtrEntry( vPODriver_nCk, longI )) );
	}

	//clean-up, book-keeping
	assert( liCopied + liCreated == loCopied + loCreated );	
	nRegCount = loCopied + loCreated;

	Aig_ManSetRegNum( pNewAig, nRegCount );
	Aig_ManCleanup( pNewAig );
	assert( Aig_ManCheck( pNewAig ) );
	
	//Vec_IntFree(vC_KNUTH);	
	return pNewAig;
}

Aig_Man_t *generateGeneralDisjunctiveTester( Abc_Ntk_t *pNtk, Aig_Man_t *pAig, int combK )
{
	//AIG creation related data structure
	Aig_Man_t *pNewAig;
	int piCopied = 0, loCopied = 0, loCreated = 0, liCopied = 0, liCreated = 0, poCopied = 0;
	//int i, iElem, nRegCount, hintSingalBeginningMarker, hintSingalEndMarker;
	int i, nRegCount;
	int combN_internal, combK_internal; //, targetPoIndex;
	long longI, lCombinationCount;
	//Aig_Obj_t *pObj, *pObjMonoCand, *pObjLO_nCk, *pObjDisj_nCk;
	Aig_Obj_t *pObj, *pObjLO_nCk, *pObjDisj_nCk;
	Vec_Ptr_t *vLO_nCk, *vPODriver_nCk, *vDisj_nCk;

	extern Vec_Int_t *findHintOutputs(Abc_Ntk_t *pNtk);
	
	//Knuth's Data Strcuture
	//Vec_Int_t *vC_KNUTH;
	//int i_KNUTH, j_KNUTH, combCounter_KNUTH = 0;

	//Collecting target HINT signals
	//vCandidateMonotoneSignals = findHintOutputs(pNtk);
	//if( vCandidateMonotoneSignals == NULL )
	//{
	//	printf("\nTraget Signal Set is Empty: Duplicating given AIG\n");
	//	combN_internal = 0;
	//}
	//else
	//{
		//Vec_IntForEachEntry( vCandidateMonotoneSignals, iElem, i )
		//	printf("Po[%d] = %s\n", iElem, Abc_ObjName( Abc_NtkPo(pNtk, iElem) ) );
	//	hintSingalBeginningMarker = Vec_IntEntry( vCandidateMonotoneSignals, 0 );
	//	hintSingalEndMarker = Vec_IntEntry( vCandidateMonotoneSignals, Vec_IntSize(vCandidateMonotoneSignals) - 1 );
	//	combN_internal = hintSingalEndMarker - hintSingalBeginningMarker + 1;
	//}

	combN_internal = Aig_ManRegNum(pAig);

	pNewAig = Aig_ManStart( Aig_ManObjNumMax(pAig) );
	pNewAig->pName = (char *)malloc( strlen( pAig->pName ) + strlen("_nCk") + 1 );
	sprintf(pNewAig->pName, "%s_%s", pAig->pName, "nCk");
    	pNewAig->pSpec = NULL;

	//Standard Mapping of Constant Nodes
	pObj = Aig_ManConst1( pAig );
    	pObj->pData = Aig_ManConst1( pNewAig );

	//Standard AIG PI duplication
	Saig_ManForEachPi( pAig, pObj, i )
	{
		piCopied++;
		pObj->pData = Aig_ObjCreateCi(pNewAig);
	}

	//Standard AIG LO duplication
	Saig_ManForEachLo( pAig, pObj, i )
    	{
		loCopied++;
		pObj->pData = Aig_ObjCreateCi(pNewAig);
    	}

	//nCk LO creation
	lCombinationCount = 0;
	for(combK_internal=1; combK_internal<=combK; combK_internal++)
		lCombinationCount += countCombination( combN_internal, combK_internal );
	assert( lCombinationCount > 0 );
	vLO_nCk = Vec_PtrAlloc(lCombinationCount);
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		loCreated++;
		pObj = Aig_ObjCreateCi(pNewAig);
		Vec_PtrPush( vLO_nCk, pObj );
	}

	//Standard Node duplication
	Aig_ManForEachNode( pAig, pObj, i )
	{
		pObj->pData = Aig_And( pNewAig, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
	}
	
	//nCk specific logic creation (i.e. nCk number of OR gates)
	vDisj_nCk = Vec_PtrAlloc(lCombinationCount);

	for( combK_internal=1; combK_internal<=combK; combK_internal++ )
	{
		generateCombinatorialStabilExhaust( pNewAig, pAig,
				vDisj_nCk, combN_internal, combK_internal );
	}


	//creation of implication logic
	vPODriver_nCk = Vec_PtrAlloc(lCombinationCount);
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		pObjLO_nCk = (Aig_Obj_t *)(Vec_PtrEntry( vLO_nCk, longI ));
		pObjDisj_nCk = (Aig_Obj_t *)(Vec_PtrEntry( vDisj_nCk, longI ));

		pObj = Aig_Or( pNewAig, Aig_Not(pObjDisj_nCk), pObjLO_nCk);
		Vec_PtrPush(vPODriver_nCk, pObj);
	}
	
	//Standard PO duplication
	Saig_ManForEachPo( pAig, pObj, i )
	{
		poCopied++;
		pObj->pData = Aig_ObjCreateCo( pNewAig, Aig_ObjChild0Copy(pObj) ); 
	}

	//nCk specific PO creation
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		Aig_ObjCreateCo( pNewAig, (Aig_Obj_t *)(Vec_PtrEntry( vPODriver_nCk, longI )) );
	}

	//Standard LI duplication
	Saig_ManForEachLi( pAig, pObj, i )
	{
		liCopied++;
		Aig_ObjCreateCo( pNewAig, Aig_ObjChild0Copy(pObj) );
	}

	//nCk specific LI creation
	for( longI = 0; longI < lCombinationCount; longI++ )
	{
		liCreated++;
		Aig_ObjCreateCo( pNewAig, (Aig_Obj_t *)(Vec_PtrEntry( vPODriver_nCk, longI )) );
	}

	//clean-up, book-keeping
	assert( liCopied + liCreated == loCopied + loCreated );	
	nRegCount = loCopied + loCreated;

	Aig_ManSetRegNum( pNewAig, nRegCount );
	Aig_ManCleanup( pNewAig );
	assert( Aig_ManCheck( pNewAig ) );
	
	Vec_PtrFree(vLO_nCk);
	Vec_PtrFree(vPODriver_nCk);
	Vec_PtrFree(vDisj_nCk);
	//Vec_IntFree(vC_KNUTH);	
	return pNewAig;
}

ABC_NAMESPACE_IMPL_END