mpmDsd.c File Reference

#include "mpmInt.h"
#include "misc/extra/extra.h"

Go to the source code of this file.

Functions
Vec_Wrd_t *	Mpm_ManGetTruthWithCnf (int Limit)
	FUNCTION DEFINITIONS ///. More...
void	Mpm_ManPrintDsdStats (Mpm_Man_t *p)
Hsh_IntMan_t *	Mpm_ManBuildHashTable (Vec_Int_t **pvConfgRes)
void	Mpm_ManPrintPerm (unsigned s)
void	Mpm_ManPrecomputePerms (Mpm_Man_t *p)
word	Mpm_CutTruthFromDsd (Mpm_Man_t *pMan, Mpm_Cut_t *pCut, int iClass)
int	Mpm_CutCheckDsd6 (Mpm_Man_t *p, word t)
int	Mpm_CutComputeDsd6 (Mpm_Man_t *p, Mpm_Cut_t *pCut, Mpm_Cut_t *pCut0, Mpm_Cut_t *pCut1, Mpm_Cut_t *pCutC, int fCompl0, int fCompl1, int fComplC, int Type)

Variables
static ABC_NAMESPACE_IMPL_START Mpm_Dsd_t	s_DsdClass6 [595]
	DECLARATIONS ///. More...

Function Documentation

int Mpm_CutCheckDsd6	(	Mpm_Man_t *	p,
		word	t
	)

Function*************************************************************

Synopsis [Checks hash table for DSD class.]

Description []

SideEffects []

SeeAlso []

Definition at line 905 of file mpmDsd.c.

{
    int fCompl, Entry, Config;
    if ( (fCompl = (t & 1)) )
        t = ~t;
    Entry = *Hsh_IntManLookup( p->pHash, (unsigned *)&t );
    if ( Entry == -1 )
        return -1;
    Config = Vec_IntEntry( p->vConfgRes, Entry );
    if ( fCompl )
        Config ^= (1 << 16);
    return Config;
}

int Mpm_CutComputeDsd6	(	Mpm_Man_t *	p,
		Mpm_Cut_t *	pCut,
		Mpm_Cut_t *	pCut0,
		Mpm_Cut_t *	pCut1,
		Mpm_Cut_t *	pCutC,
		int	fCompl0,
		int	fCompl1,
		int	fComplC,
		int	Type
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 930 of file mpmDsd.c.

{
    int fVerbose = 0;
    int i, Config, iClass, fCompl;
    int pLeavesNew[6] = { -1, -1, -1, -1, -1, -1 };
    word t = 0;
    if ( pCutC == NULL )
    {
        word t0, t1;
        int iClass0  = Abc_Lit2Var(pCut0->iFunc);
        int iClass1  = Abc_Lit2Var(pCut1->iFunc);
        word Truth0  = p->pDsd6[iClass0].uTruth;
        int Perm1    = Vec_IntEntry( p->vMap2Perm, p->uPermMask[1] );
        word Truth1p = Vec_WrdEntry( p->vPerm6, iClass1 * 720 + Perm1 );
        if ( p->uComplMask[1] )
        {
            for ( i = 0; i < 6; i++ )
                if ( (p->uComplMask[1] >> i) & 1 )
                    Truth1p = Abc_Tt6Flip( Truth1p, i );            
        }
        t0 = (fCompl0 ^ pCut0->fCompl ^ Abc_LitIsCompl(pCut0->iFunc)) ? ~Truth0  : Truth0;
        t1 = (fCompl1 ^ pCut1->fCompl ^ Abc_LitIsCompl(pCut1->iFunc)) ? ~Truth1p : Truth1p;
        if ( Type == 1 )
            t = t0 & t1;
        else if ( Type == 2 )
            t = t0 ^ t1;
        else assert( 0 );

if ( fVerbose )
{
Mpm_ManPrintPerm( p->uPermMask[1] );               printf( "\n" );
Kit_DsdPrintFromTruth( (unsigned *)&Truth0, 6 );   printf( "\n" );
Kit_DsdPrintFromTruth( (unsigned *)&Truth1p, 6 );  printf( "\n" );
Kit_DsdPrintFromTruth( (unsigned *)&t, 6 );        printf( "\n" );
}
    }
    else
    {
        word t0, t1, tC;
        int iClass0  = Abc_Lit2Var(pCut0->iFunc);
        int iClass1  = Abc_Lit2Var(pCut1->iFunc);
        int iClassC  = Abc_Lit2Var(pCutC->iFunc);
        word Truth0  = p->pDsd6[iClass0].uTruth;
        int Perm1    = Vec_IntEntry( p->vMap2Perm, p->uPermMask[1] );
        int PermC    = Vec_IntEntry( p->vMap2Perm, p->uPermMask[2] );
        word Truth1p = Vec_WrdEntry( p->vPerm6, iClass1 * 720 + Perm1 );
        word TruthCp = Vec_WrdEntry( p->vPerm6, iClassC * 720 + PermC );
        if ( p->uComplMask[1] )
        {
            for ( i = 0; i < 6; i++ )
                if ( (p->uComplMask[1] >> i) & 1 )
                    Truth1p = Abc_Tt6Flip( Truth1p, i );            
        }
        if ( p->uComplMask[2] )
        {
            for ( i = 0; i < 6; i++ )
                if ( (p->uComplMask[2] >> i) & 1 )
                    TruthCp = Abc_Tt6Flip( TruthCp, i );            
        }
        t0 = (fCompl0 ^ pCut0->fCompl ^ Abc_LitIsCompl(pCut0->iFunc)) ? ~Truth0  : Truth0;
        t1 = (fCompl1 ^ pCut1->fCompl ^ Abc_LitIsCompl(pCut1->iFunc)) ? ~Truth1p : Truth1p;
        tC = (fComplC ^ pCutC->fCompl ^ Abc_LitIsCompl(pCutC->iFunc)) ? ~TruthCp : TruthCp;
        t = (tC & t1) | (~tC & t0);
    }

    // find configuration
    Config = Mpm_CutCheckDsd6( p, t );
    if ( Config == -1 )
    {
        p->nNonDsd++;
        return 0;
    }

    // get the class
    iClass = Config >> 17;
    fCompl = (Config >> 16) & 1;
    Config &= 0xFFFF;

    // check if the gate exists
    if ( p->pPars->fMap4Gates )
    {
        if ( Vec_IntSize(Vec_WecEntry(p->vNpnConfigs, iClass)) == 0 )
        {
            p->nNoMatch++;
            return 0;
        }
    }

    // set the function
    pCut->iFunc = Abc_Var2Lit( iClass, fCompl );

if ( fVerbose )
{
Mpm_CutPrint( pCut0 );
Mpm_CutPrint( pCut1 );
Mpm_CutPrint( pCut );
}

    // update cut
    assert( (Config >> 6) < 720 );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        pLeavesNew[(int)(p->Perm6[Config >> 6][i])] = Abc_LitNotCond( pCut->pLeaves[i], (Config >> i) & 1 );
    pCut->nLeaves = p->pDsd6[iClass].nVars;
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        assert( pLeavesNew[i] != -1 );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        pCut->pLeaves[i] = pLeavesNew[i];
    p->nCountDsd[iClass]++;
    p->nSmallSupp += (int)(pCut->nLeaves < 2);

if ( fVerbose )
{
printf( "Computed " );
Mpm_CutPrint( pCut );
printf( "\n" );
}
    return 1;
}

word Mpm_CutTruthFromDsd	(	Mpm_Man_t *	pMan,
		Mpm_Cut_t *	pCut,
		int	iClass
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 883 of file mpmDsd.c.

{
    int i;
    word uTruth = pMan->pDsd6[iClass].uTruth;
    assert( pMan->pDsd6[iClass].nVars == (int)pCut->nLeaves );
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        if ( Abc_LitIsCompl(pCut->pLeaves[i]) )
            uTruth = Abc_Tt6Flip( uTruth, i ); 
    return uTruth;
}

Hsh_IntMan_t* Mpm_ManBuildHashTable

(

Vec_Int_t **

pvConfgRes

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 699 of file mpmDsd.c.

{
    FILE * pFile;
    char * pFileName = "dsdfuncs6.dat";
    int RetValue, size = Extra_FileSize( pFileName ) / 12;  // 2866420
    Vec_Wrd_t * vTruthRes = Vec_WrdAlloc( size );
    Vec_Int_t * vConfgRes = Vec_IntAlloc( size );
    Hsh_IntMan_t * pHash;

    pFile = fopen( pFileName, "rb" );
    RetValue = fread( Vec_WrdArray(vTruthRes), sizeof(word), size, pFile );
    RetValue = fread( Vec_IntArray(vConfgRes), sizeof(int), size, pFile );
    vTruthRes->nSize = size;
    vConfgRes->nSize = size;
    // create hash table
    pHash = Hsh_WrdManHashArrayStart( vTruthRes, 1 );
    // cleanup
    if ( pvConfgRes )
        *pvConfgRes = vConfgRes;
    else
        Vec_IntFree( vConfgRes );
    Vec_WrdFree( vTruthRes );
//    Hsh_IntManStop( pHash );
    return pHash;
}

Vec_Wrd_t* Mpm_ManGetTruthWithCnf

(

int

Limit

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 644 of file mpmDsd.c.

{
    Vec_Wrd_t * vRes = Vec_WrdAlloc( 1000 );
    int i;
    for ( i = 0; i < 595; i++ )
        if ( s_DsdClass6[i].nClauses <= Limit )
            Vec_WrdPush( vRes, s_DsdClass6[i].uTruth );
    return vRes;
}

void Mpm_ManPrecomputePerms

(

Mpm_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 755 of file mpmDsd.c.

{
    int nVars = 6;
    // 0(1:1) 1(2:1) 2(4:2) 3(10:6) 4(33:23) 5(131:98) 6(595:464)
    int nClasses[7] = { 1, 2, 4, 10, 33, 131, 595 };
    int nPerms = Extra_Factorial( nVars );
//    int nSwaps = (1 << nVars);
    int * pComp, * pPerm;
    int i, k, x, One, OneCopy, Num;
    Vec_Int_t * vVars;
    abctime clk = Abc_Clock();
    assert( p->pDsd6 == NULL );
    p->pDsd6 = s_DsdClass6;
    // precompute schedules
    pComp = Extra_GreyCodeSchedule( nVars );
    pPerm = Extra_PermSchedule( nVars );
    // map numbers into perms
    p->vMap2Perm = Vec_IntStartFull( (1<<(3*nVars)) );
    // store permutations
    One = 0;
    for ( x = 0; x < nVars; x++ )
    {
        p->Perm6[0][x] = (char)x;
        One |= (x << (3*x));
    }
//    Vec_IntWriteEntry( p->vMap2Perm, One, 0 );
    OneCopy = One;
    for ( k = 0; k < nPerms; k++ )
    {
        if ( k > 0 )
        for ( x = 0; x < nVars; x++ )
            p->Perm6[k][x] = p->Perm6[k-1][x];
        ABC_SWAP( char, p->Perm6[k][pPerm[k]], p->Perm6[k][pPerm[k]+1] );

        Num = ( (One >> (3*(pPerm[k]  ))) ^ (One >> (3*(pPerm[k]+1))) ) & 7;
        One ^=  (Num << (3*(pPerm[k]  )));
        One ^=  (Num << (3*(pPerm[k]+1)));

        Vec_IntWriteEntry( p->vMap2Perm, One, k );
        
//        Mpm_ManPrintPerm( One );
//        for ( x = 0; x < nVars; x++ )
//            printf( "%d ", p->Perm6[k][x] );
//        printf( "\n" );
    }
    assert( OneCopy == One );
    // fill in the gaps
    vVars = Vec_IntAlloc( 6 );
    Vec_IntForEachEntry( p->vMap2Perm, Num, i )
    {
        // mark used variables
        int Count = 0;
        One = i;
        Vec_IntFill( vVars, 6, 0 );
        for ( k = 0; k < nVars; k++ )
        {
            int iVar = ((One >> (3*k)) & 7);
            if ( iVar >= nVars && iVar < 7 )
                break;
            if ( iVar != 7 )
            {
                if ( Vec_IntEntry( vVars, iVar ) == 1 )
                    break;
                Vec_IntWriteEntry( vVars, iVar, 1 );
                Count++;
            }
        }
        // skip ones with dups and complete
        if ( k < nVars || Count == nVars )
            continue;
        // find unused variables
        for ( x = k = 0; k < 6; k++ )
            if ( Vec_IntEntry(vVars, k) == 0 )
                Vec_IntWriteEntry( vVars, x++, k );
        Vec_IntShrink( vVars, x );
        // fill in used variables
        x = 0;
        for ( k = 0; k < nVars; k++ )
        {
            int iVar = ((One >> (3*k)) & 7);
            if ( iVar == 7 )
                One ^= ((Vec_IntEntry(vVars, x++) ^ 7) << (3*k));
        }
        assert( x == Vec_IntSize(vVars) );
        // save this one
        assert( Vec_IntEntry( p->vMap2Perm, One ) != -1 );
        Vec_IntWriteEntry( p->vMap2Perm, i, Vec_IntEntry(p->vMap2Perm, One) );
/*
        // mapping
        Mpm_ManPrintPerm( i );
        printf( "->  " );
        Mpm_ManPrintPerm( One );
        printf( "\n" );
*/
    }
    Vec_IntFree( vVars );

    // store permuted truth tables
    assert( p->vPerm6 == NULL );
    p->vPerm6 = Vec_WrdAlloc( nPerms * 595 );
    for ( i = 0; i < nClasses[nVars]; i++ )
    {
        word uTruth = s_DsdClass6[i].uTruth;
        for ( k = 0; k < nPerms; k++ )
        {
            uTruth = Abc_Tt6SwapAdjacent( uTruth, pPerm[k] );
            Vec_WrdPush( p->vPerm6, uTruth );
        }
        assert( uTruth == s_DsdClass6[i].uTruth );
    }
    ABC_FREE( pPerm );
    ABC_FREE( pComp );
    // build hash table
    p->pHash = Mpm_ManBuildHashTable( &p->vConfgRes );
    Abc_PrintTime( 1, "Setting up DSD information", Abc_Clock() - clk );
}

void Mpm_ManPrintDsdStats

(

Mpm_Man_t *

p

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 665 of file mpmDsd.c.

{
    int i, Absent = 0;
    for ( i = 0; i < 595; i++ )
    {
        if ( p->nCountDsd[i] == 0 )
        {
            Absent++;
            continue;
        }
        if ( p->pPars->fVeryVerbose )
        {
            printf( "%5d  :  ", i );
            printf( "%-20s   ", p->pDsd6[i].pStr );
            printf( "%8d ",     p->nCountDsd[i] );
            printf( "\n" );
        }
    }
    printf( "Unused classes = %d (%.2f %%).  ",  Absent, 100.0 * Absent / 595 );
    printf( "Non-DSD cuts = %d (%.2f %%).  ",   p->nNonDsd, 100.0 * p->nNonDsd / p->nCutsMergedAll );
    printf( "No-match cuts = %d (%.2f %%).\n",  p->nNoMatch, 100.0 * p->nNoMatch / p->nCutsMergedAll );
}

void Mpm_ManPrintPerm

(

unsigned

s

)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 736 of file mpmDsd.c.

{
    int i;
    for ( i = 0; i < 6; i++ )
        printf( "%d ", (s >> (3*i)) & 7 );
    printf( "  " );
}

Variable Documentation

ABC_NAMESPACE_IMPL_START Mpm_Dsd_t s_DsdClass6[595]

static

DECLARATIONS ///.

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

FileName [mpmDsd.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Configurable technology mapper.]

Synopsis [DSD manipulation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 1, 2013.]

Revision [

Id:

mpmDsd.c,v 1.00 2013/06/01 00:00:00 alanmi Exp

]

Definition at line 30 of file mpmDsd.c.