dauArray.c File Reference

#include "dauInt.h"

Go to the source code of this file.

Data Structures
struct	Dau_Dsd_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_	Dau_Dsd_t
	DECLARATIONS ///. More...

Functions
static void	Dau_DsdClean (Dau_Dsd_t *p)
int	Dau_DsdCountAnd (Dau_Dsd_t *p)
	FUNCTION DEFINITIONS ///. More...
int	Dau_DsdConstruct (char *pDsd, Dau_Dsd_t *pStore)
void	Dau_DsdPrint (Dau_Dsd_t *p)
void	Dau_DsdDepth (Dau_Dsd_t *p)
void	Dau_DsdRemoveUseless (Dau_Dsd_t *p)
void	Dau_DsdTest22 ()

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_ Dau_Dsd_t

DECLARATIONS ///.

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

FileName [dauArray.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [DAG-aware unmapping.]

Synopsis [Array representation of DSD.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

dauArray.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 29 of file dauArray.c.

Function Documentation

static void Dau_DsdClean ( Dau_Dsd_t *  p )

inlinestatic

Definition at line 42 of file dauArray.c.

{ *((int *)p) = 0; }

int Dau_DsdConstruct	(	char *	pDsd,
		Dau_Dsd_t *	pStore
	)

Definition at line 76 of file dauArray.c.

{
    Dau_Dsd_t * pLevel[DAU_MAX_VAR];
    Dau_Dsd_t * q = pStore;
    int d = -1, fCompl = 0;
    if ( Dau_DsdIsConst(pDsd) )
    {
        Dau_DsdClean( q );
        q->Type   = DAU_DSD_CONST0;
        q->fCompl = Dau_DsdIsConst1(pDsd);
        return 1;
    }
    for ( --q; *pDsd; pDsd++ )
    {
        if ( *pDsd == '!' )
        {
            fCompl ^= 1;
            continue;
        }
        if ( *pDsd == ')' || *pDsd == ']' || *pDsd == '>' || *pDsd == '}' )
        {
            assert( fCompl == 0 );
            if ( --d >= 0 )
            {
                pLevel[d]->nFans++;
                if ( pLevel[d]->Data > pLevel[d+1]->Data )
                    pLevel[d]->Data = pLevel[d+1]->Data;
            }
            continue;
        }
        Dau_DsdClean( ++q );
        q->Data = 31;
        q->fCompl = fCompl;
        fCompl = 0;
        if ( *pDsd >= 'a' && *pDsd <= 'z' )
        {
            q->Type   = DAU_DSD_VAR;
            q->iVar   = *pDsd - 'a';
            q->Depth  = d + 1;
            if ( d >= 0 )
            {
                pLevel[d]->nFans++;
                if ( pLevel[d]->Data > q->iVar )
                    pLevel[d]->Data = q->iVar;
            }
            continue;
        }
        if ( *pDsd == '(' )
            q->Type = DAU_DSD_AND;
        else if ( *pDsd == '[' )
            q->Type = DAU_DSD_XOR;
        else if ( *pDsd == '<' )
            q->Type = DAU_DSD_MUX;
        else if ( *pDsd == '{' )
            q->Type = DAU_DSD_PRIME;
        else assert( 0 );
        pLevel[++d] = q;
        q->Depth = d;
    }
    assert( d == -1 );
    Dau_DsdClean( ++q );
    return q - pStore;
}

int Dau_DsdCountAnd

(

Dau_Dsd_t *

p

)

FUNCTION DEFINITIONS ///.

Definition at line 48 of file dauArray.c.

{
    int Count, Costs[7] = {0, 0, 0, 1, 3, 3, 3};
    for ( Count = 0; p->Type; p++ )
        Count += Costs[p->Type];
    return Count;
}

void Dau_DsdDepth

(

Dau_Dsd_t *

p

)

Definition at line 175 of file dauArray.c.

{
    int d, pVisits[DAU_MAX_VAR];
    if ( p->Type == DAU_DSD_CONST0 )
        return;
    pVisits[0] = 1;
    for ( d = 0; p->Type; p++ )
    {
        p->Depth = d;
        if ( p->Type == DAU_DSD_VAR )
            while ( d > 0 && --pVisits[d] == 0 )
                d--;
        else
            pVisits[++d] = p->nFans;
    }
    assert( d == 0 );
}

void Dau_DsdPrint

(

Dau_Dsd_t *

p

)

Definition at line 140 of file dauArray.c.

{
    char OpenType[7]  = {0, 0, 0, '(', '[', '<', '{'};
    char CloseType[7] = {0, 0, 0, ')', ']', '>', '}'};
    char pTypes[DAU_MAX_VAR];
    int d, pVisits[DAU_MAX_VAR];
    if ( p->Type == DAU_DSD_CONST0 )
    {
        printf( "%d\n", p->fCompl );
        return;
    }
    pVisits[0] = 1;
    for ( d = 0; p->Type; p++ )
    {
        if ( p->fCompl )
            printf( "!" );
        if ( p->Type == DAU_DSD_VAR )
        {
            printf( "%c", 'a' + p->iVar );
            while ( d > 0 && --pVisits[d] == 0 )
                printf( "%c", pTypes[d--] );
        }
        else
        {
            pVisits[++d] = p->nFans;
            printf( "%c", OpenType[p->Type] );
            printf( "%c", 'a' + p->Data );
            printf( "%d", p->Depth );
            pTypes[d]  = CloseType[p->Type];
        }
    }
    assert( d == 0 );
    printf( "\n" );
}

void Dau_DsdRemoveUseless

(

Dau_Dsd_t *

p

)

Definition at line 193 of file dauArray.c.

{
    Dau_Dsd_t * q = p, * pLevel[DAU_MAX_VAR];
    int d, fChange = 0, pVisits[DAU_MAX_VAR];
    if ( p->Type == DAU_DSD_CONST0 )
        return;
    pVisits[0] = 1;
    for ( d = 0; p->Type; p++ )
    {
        p->Depth = d;
        if ( p->Type == DAU_DSD_VAR )
            while ( d > 0 && --pVisits[d] == 0 )
                d--;
        else
        {
            if ( d > 0 && (pLevel[d-1]->Type == DAU_DSD_XOR && p->Type == DAU_DSD_XOR ||
                           pLevel[d-1]->Type == DAU_DSD_AND && p->Type == DAU_DSD_AND && !p->fCompl) )
            {
                pLevel[d-1]->nFans += p->nFans - 1;
                pVisits[d] += p->nFans - 1;
                p->fUnused = 1;
                fChange = 1;
            }
            else
            {
                pLevel[d++] = p;
                pVisits[d] = p->nFans;
            }
        }
    }
    assert( d == 0 );
    // compact
    if ( fChange )
    {
        for ( p = q; p->Type; p++ )
            if ( !p->fUnused )
                *q++ = *p;
        Dau_DsdClean( q );
    }
}

void Dau_DsdTest22

(

)

Definition at line 234 of file dauArray.c.

{
    Dau_Dsd_t pStore[2 * DAU_MAX_VAR];
//    char * pDsd = "[(ab)c(f!(he))]";
//    char * pDsd = "[(abd)cf(f!{she})]";
    char * pDsd = "[(abd)[cf](f(sg(he)))]";
//    char * pDsd = "[(ab)[cf]]";
    int i, nSize = Dau_DsdConstruct( pDsd, pStore );
//    Dau_DsdDepth( pStore );
    Dau_DsdPrint( pStore );

    Dau_DsdRemoveUseless( pStore );

    Dau_DsdPrint( pStore );
    i = 0;
}