dsd.h 6.17 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
/**CFile****************************************************************

  FileName    [dsd.h]

  PackageName [DSD: Disjoint-support decomposition package.]

  Synopsis    [External declarations of the package.
  This fast BDD-based recursive algorithm for simple 
  (single-output) DSD is based on the following papers:
  (1) V. Bertacco and M. Damiani, "Disjunctive decomposition of 
  logic functions," Proc. ICCAD '97, pp. 78-82.
  (2) Y. Matsunaga, "An exact and efficient algorithm for disjunctive 
  decomposition", Proc. SASIMI '98, pp. 44-50.
  The scope of detected decompositions is the same as in the paper:
  T. Sasao and M. Matsuura, "DECOMPOS: An integrated system for 
  functional decomposition," Proc. IWLS '98, pp. 471-477.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 8.0. Started - September 22, 2003.]

  Revision    [$Id: dsd.h,v 1.0 2002/22/09 00:00:00 alanmi Exp $]

***********************************************************************/

28 29
#ifndef ABC__bdd__dsd__dsd_h
#define ABC__bdd__dsd__dsd_h
Alan Mishchenko committed
30

31

Alan Mishchenko committed
32 33 34 35 36 37 38 39
////////////////////////////////////////////////////////////////////////
///                    STRUCTURE DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                         PARAMETERS                               ///
////////////////////////////////////////////////////////////////////////

40 41 42 43


ABC_NAMESPACE_HEADER_START

Alan Mishchenko committed
44

Alan Mishchenko committed
45 46 47 48 49 50 51 52 53 54 55
// types of DSD nodes
enum Dsd_Type_t_ { 
    DSD_NODE_NONE   = 0,
    DSD_NODE_CONST1 = 1,
    DSD_NODE_BUF    = 2,
    DSD_NODE_OR     = 3,
    DSD_NODE_EXOR   = 4,
    DSD_NODE_PRIME  = 5,
};

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
56 57 58 59 60 61 62 63
///                      TYPEDEF DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

typedef struct Dsd_Manager_t_   Dsd_Manager_t;
typedef struct Dsd_Node_t_      Dsd_Node_t;
typedef enum   Dsd_Type_t_      Dsd_Type_t;

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
64
///                       MACRO DEFINITIONS                          ///
Alan Mishchenko committed
65 66 67
////////////////////////////////////////////////////////////////////////

// complementation and testing for pointers for decomposition entries
Alan Mishchenko committed
68 69 70 71
#define Dsd_IsComplement(p)  (((int)((ABC_PTRUINT_T) (p) & 01)))
#define Dsd_Regular(p)       ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) & ~01)) 
#define Dsd_Not(p)           ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ 01)) 
#define Dsd_NotCond(p,c)     ((Dsd_Node_t *)((ABC_PTRUINT_T)(p) ^ (c)))
Alan Mishchenko committed
72 73 74 75 76 77 78 79 80 81 82 83 84

////////////////////////////////////////////////////////////////////////
///                         ITERATORS                                ///
////////////////////////////////////////////////////////////////////////

// iterator through the transitions
#define Dsd_NodeForEachChild( Node, Index, Child )        \
    for ( Index = 0;                                      \
          Index < Dsd_NodeReadDecsNum(Node) &&            \
             ((Child = Dsd_NodeReadDec(Node,Index))>=0);  \
          Index++ )

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
85
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
86 87 88 89 90 91 92 93 94 95 96
////////////////////////////////////////////////////////////////////////

/*=== dsdApi.c =======================================================*/
extern Dsd_Type_t      Dsd_NodeReadType( Dsd_Node_t * p ); 
extern DdNode *        Dsd_NodeReadFunc( Dsd_Node_t * p );
extern DdNode *        Dsd_NodeReadSupp( Dsd_Node_t * p );
extern Dsd_Node_t **   Dsd_NodeReadDecs( Dsd_Node_t * p );
extern Dsd_Node_t *    Dsd_NodeReadDec ( Dsd_Node_t * p, int i );
extern int             Dsd_NodeReadDecsNum( Dsd_Node_t * p );
extern int             Dsd_NodeReadMark( Dsd_Node_t * p );
extern void            Dsd_NodeSetMark( Dsd_Node_t * p, int Mark ); 
Alan Mishchenko committed
97
extern DdManager *     Dsd_ManagerReadDd( Dsd_Manager_t * pMan );
Alan Mishchenko committed
98 99
extern Dsd_Node_t *    Dsd_ManagerReadRoot( Dsd_Manager_t * pMan, int i );
extern Dsd_Node_t *    Dsd_ManagerReadInput( Dsd_Manager_t * pMan, int i );
Alan Mishchenko committed
100
extern Dsd_Node_t *    Dsd_ManagerReadConst1( Dsd_Manager_t * pMan );
Alan Mishchenko committed
101 102 103 104 105
/*=== dsdMan.c =======================================================*/
extern Dsd_Manager_t * Dsd_ManagerStart( DdManager * dd, int nSuppMax, int fVerbose );
extern void            Dsd_ManagerStop( Dsd_Manager_t * dMan );
/*=== dsdProc.c =======================================================*/
extern void            Dsd_Decompose( Dsd_Manager_t * dMan, DdNode ** pbFuncs, int nFuncs );
Alan Mishchenko committed
106
extern Dsd_Node_t *    Dsd_DecomposeOne( Dsd_Manager_t * pDsdMan, DdNode * bFunc );
Alan Mishchenko committed
107 108 109
/*=== dsdTree.c =======================================================*/
extern void            Dsd_TreeNodeGetInfo( Dsd_Manager_t * dMan, int * DepthMax, int * GateSizeMax );
extern void            Dsd_TreeNodeGetInfoOne( Dsd_Node_t * pNode, int * DepthMax, int * GateSizeMax );
Alan Mishchenko committed
110
extern int             Dsd_TreeGetAigCost( Dsd_Node_t * pNode );
Alan Mishchenko committed
111 112 113 114 115 116
extern int             Dsd_TreeCountNonTerminalNodes( Dsd_Manager_t * dMan );
extern int             Dsd_TreeCountNonTerminalNodesOne( Dsd_Node_t * pRoot );
extern int             Dsd_TreeCountPrimeNodes( Dsd_Manager_t * pDsdMan );
extern int             Dsd_TreeCountPrimeNodesOne( Dsd_Node_t * pRoot );
extern int             Dsd_TreeCollectDecomposableVars( Dsd_Manager_t * dMan, int * pVars );
extern Dsd_Node_t **   Dsd_TreeCollectNodesDfs( Dsd_Manager_t * dMan, int * pnNodes );
Alan Mishchenko committed
117
extern Dsd_Node_t **   Dsd_TreeCollectNodesDfsOne( Dsd_Manager_t * pDsdMan, Dsd_Node_t * pNode, int * pnNodes );
Alan Mishchenko committed
118
extern void            Dsd_TreePrint( FILE * pFile, Dsd_Manager_t * dMan, char * pInputNames[], char * pOutputNames[], int fShortNames, int Output );
Alan Mishchenko committed
119
extern void            Dsd_NodePrint( FILE * pFile, Dsd_Node_t * pNode );
Alan Mishchenko committed
120 121 122
/*=== dsdLocal.c =======================================================*/
extern DdNode *        Dsd_TreeGetPrimeFunction( DdManager * dd, Dsd_Node_t * pNode );

123 124 125 126 127


ABC_NAMESPACE_HEADER_END


Alan Mishchenko committed
128 129 130

#endif

Alan Mishchenko committed
131 132 133
////////////////////////////////////////////////////////////////////////
///                           END OF FILE                            ///
////////////////////////////////////////////////////////////////////////