abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
mioSop.c File Reference
#include "mioInt.h"
#include "exp.h"

Go to the source code of this file.

Functions

static
ABC_NAMESPACE_IMPL_START
unsigned 		Mio_CubeVar0 (int v)
 DECLARATIONS ///. More...
 
static unsigned Mio_CubeVar1 (int v)
 
static int Mio_CubeHasVar0 (unsigned x, int v)
 
static int Mio_CubeHasVar1 (unsigned x, int v)
 
static int Mio_CubeEmpty (unsigned x)
 
static unsigned Mio_CubeAnd (unsigned x, unsigned y)
 
static int Mio_CubeContains (unsigned x, unsigned y)
 
void Mio_SopPushSCC (Vec_Int_t *p, unsigned c)
 FUNCTION DEFINITIONS ///. More...
 
Vec_Int_t * Mio_SopCoverOr (Vec_Int_t *p, Vec_Int_t *q)
 
Vec_Int_t * Mio_SopCoverAnd (Vec_Int_t *p, Vec_Int_t *q)
 
Vec_Int_t * Mio_SopVar0 (int i)
 
Vec_Int_t * Mio_SopVar1 (int i)
 
Vec_Int_t * Mio_SopConst0 ()
 
Vec_Int_t * Mio_SopConst1 ()
 
char * Mio_SopDeriveFromArray (Vec_Int_t *vSop, int nVars, Vec_Str_t *vStr, int fPolarity)
 
char * Mio_LibDeriveSop (int nVars, Vec_Int_t *vExpr, Vec_Str_t *vStr)
 

Function Documentation

static unsigned Mio_CubeAnd ( unsigned  x,
unsigned  y 
)
inlinestatic

Definition at line 34 of file mioSop.c.

34 { return x | y; }
static int Mio_CubeContains ( unsigned  x,
unsigned  y 
)
inlinestatic

Definition at line 35 of file mioSop.c.

35 { return (x | y) == y; } // x contains y
static int Mio_CubeEmpty ( unsigned  x)
inlinestatic

Definition at line 33 of file mioSop.c.

33 { return (x & (x>>1) & 0x55555555) != 0; }
static int Mio_CubeHasVar0 ( unsigned  x,
int  v 
)
inlinestatic

Definition at line 31 of file mioSop.c.

31 { return (x & Mio_CubeVar0(v)) > 0; }
Mio_CubeVar0
static ABC_NAMESPACE_IMPL_START unsigned Mio_CubeVar0(int v)
DECLARATIONS ///.
Definition: mioSop.c:29
static int Mio_CubeHasVar1 ( unsigned  x,
int  v 
)
inlinestatic

Definition at line 32 of file mioSop.c.

32 { return (x & Mio_CubeVar1(v)) > 0; }
Mio_CubeVar1
static unsigned Mio_CubeVar1(int v)
Definition: mioSop.c:30
static ABC_NAMESPACE_IMPL_START unsigned Mio_CubeVar0 ( int  v)
inlinestatic

DECLARATIONS ///.

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

FileName [mioSop.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Derives SOP from Boolean expression.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - September 8, 2003.]

Revision [

Id:
mioSop.c,v 1.4 2004/06/28 14:20:25 alanmi Exp

]

Definition at line 29 of file mioSop.c.

29 { return (1<< (v<<1) ); }
static unsigned Mio_CubeVar1 ( int  v)
inlinestatic

Definition at line 30 of file mioSop.c.

30 { return (1<<((v<<1)+1)); }
char* Mio_LibDeriveSop ( int  nVars,
Vec_Int_t *  vExpr,
Vec_Str_t *  vStr 
)

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

Synopsis [Derives SOP representation.]

Description [The SOP is guaranteed to be SCC-free but not minimal.]

SideEffects []

SeeAlso []

Definition at line 257 of file mioSop.c.

258 {
259  Vec_Int_t * vSop;
260  Vec_Ptr_t * vSops0, * vSops1, * vTemp;
261  int i, Index0, Index1, fCompl0, fCompl1;
262  Vec_StrClear( vStr );
263  if ( Exp_IsConst0(vExpr) )
264  {
265  Vec_StrPrintStr( vStr, " 0\n" );
266  Vec_StrPush( vStr, '\0' );
267  return Vec_StrArray( vStr );
268  }
269  if ( Exp_IsConst1(vExpr) )
270  {
271  Vec_StrPrintStr( vStr, " 1\n" );
272  Vec_StrPush( vStr, '\0' );
273  return Vec_StrArray( vStr );
274  }
275  if ( Exp_IsLit(vExpr) )
276  {
277  for ( i = 0; i < nVars; i++ )
278  Vec_StrPush( vStr, '-' );
279  Vec_StrPrintStr( vStr, " 1\n" );
280  Vec_StrPush( vStr, '\0' );
281  assert( (Vec_IntEntry(vExpr,0) >> 1) < nVars );
282  Vec_StrWriteEntry( vStr, Vec_IntEntry(vExpr,0) >> 1, (char)('1' - (Vec_IntEntry(vExpr,0) & 1)) );
283  return Vec_StrArray( vStr );
284  }
285  vSops0 = Vec_PtrAlloc( nVars + Exp_NodeNum(vExpr) );
286  vSops1 = Vec_PtrAlloc( nVars + Exp_NodeNum(vExpr) );
287  for ( i = 0; i < nVars; i++ )
288  {
289  Vec_PtrPush( vSops0, Mio_SopVar0(i) );
290  Vec_PtrPush( vSops1, Mio_SopVar1(i) );
291  }
292  for ( i = 0; i < Exp_NodeNum(vExpr); i++ )
293  {
294  Index0 = Vec_IntEntry( vExpr, 2*i+0 ) >> 1;
295  Index1 = Vec_IntEntry( vExpr, 2*i+1 ) >> 1;
296  fCompl0 = Vec_IntEntry( vExpr, 2*i+0 ) & 1;
297  fCompl1 = Vec_IntEntry( vExpr, 2*i+1 ) & 1;
298  // positive polarity
299  vSop = Mio_SopCoverAnd( fCompl0 ? (Vec_Int_t *)Vec_PtrEntry(vSops0, Index0) : (Vec_Int_t *)Vec_PtrEntry(vSops1, Index0),
300  fCompl1 ? (Vec_Int_t *)Vec_PtrEntry(vSops0, Index1) : (Vec_Int_t *)Vec_PtrEntry(vSops1, Index1) );
301  Vec_PtrPush( vSops1, vSop );
302  // negative polarity
303  vSop = Mio_SopCoverOr( fCompl0 ? (Vec_Int_t *)Vec_PtrEntry(vSops1, Index0) : (Vec_Int_t *)Vec_PtrEntry(vSops0, Index0),
304  fCompl1 ? (Vec_Int_t *)Vec_PtrEntry(vSops1, Index1) : (Vec_Int_t *)Vec_PtrEntry(vSops0, Index1) );
305  Vec_PtrPush( vSops0, vSop );
306  }
307  // complement
308  if ( Vec_IntEntryLast(vExpr) & 1 )
309  {
310  vTemp = vSops0;
311  vSops0 = vSops1;
312  vSops1 = vTemp;
313  }
314  // select the best polarity
315  if ( Vec_IntSize( (Vec_Int_t *)Vec_PtrEntryLast(vSops0) ) < Vec_IntSize( (Vec_Int_t *)Vec_PtrEntryLast(vSops1) ) )
316  vSop = (Vec_Int_t *)Vec_PtrEntryLast(vSops0);
317  else
318  vSop = (Vec_Int_t *)Vec_PtrEntryLast(vSops1);
319  // convert positive polarity into SOP
320  Mio_SopDeriveFromArray( vSop, nVars, vStr, (vSop == Vec_PtrEntryLast(vSops1)) );
321  Vec_VecFree( (Vec_Vec_t *)vSops0 );
322  Vec_VecFree( (Vec_Vec_t *)vSops1 );
323  return Vec_StrArray( vStr );
324 }
Vec_Ptr_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Ptr_t_ Vec_Ptr_t
INCLUDES ///.
Definition: vecPtr.h:42
Exp_IsConst0
static int Exp_IsConst0(Vec_Int_t *p)
Definition: exp.h:64
Vec_Vec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Vec_t_ Vec_Vec_t
INCLUDES ///.
Definition: vecVec.h:42
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_StrArray
static char * Vec_StrArray(Vec_Str_t *p)
Definition: vecStr.h:272
Vec_StrClear
static void Vec_StrClear(Vec_Str_t *p)
Definition: vecStr.h:519
Vec_PtrPush
static void Vec_PtrPush(Vec_Ptr_t *p, void *Entry)
Definition: vecPtr.h:606
Vec_StrPush
static void Vec_StrPush(Vec_Str_t *p, char Entry)
Definition: vecStr.h:535
Vec_VecFree
static void Vec_VecFree(Vec_Vec_t *p)
Definition: vecVec.h:347
Mio_SopVar0
Vec_Int_t * Mio_SopVar0(int i)
Definition: mioSop.c:130
Vec_StrWriteEntry
static void Vec_StrWriteEntry(Vec_Str_t *p, int i, char Entry)
Definition: vecStr.h:370
Vec_PtrEntryLast
static void * Vec_PtrEntryLast(Vec_Ptr_t *p)
Definition: vecPtr.h:413
Mio_SopDeriveFromArray
char * Mio_SopDeriveFromArray(Vec_Int_t *vSop, int nVars, Vec_Str_t *vStr, int fPolarity)
Definition: mioSop.c:205
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Mio_SopCoverOr
Vec_Int_t * Mio_SopCoverOr(Vec_Int_t *p, Vec_Int_t *q)
Definition: mioSop.c:82
Exp_NodeNum
static int Exp_NodeNum(Vec_Int_t *p)
Definition: exp.h:89
Vec_PtrEntry
static void * Vec_PtrEntry(Vec_Ptr_t *p, int i)
Definition: vecPtr.h:362
Vec_IntEntryLast
static int Vec_IntEntryLast(Vec_Int_t *p)
Definition: bblif.c:319
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Exp_IsLit
static int Exp_IsLit(Vec_Int_t *p)
Definition: exp.h:85
Vec_PtrAlloc
static Vec_Ptr_t * Vec_PtrAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: vecPtr.h:83
Mio_SopCoverAnd
Vec_Int_t * Mio_SopCoverAnd(Vec_Int_t *p, Vec_Int_t *q)
Definition: mioSop.c:106
Exp_IsConst1
static int Exp_IsConst1(Vec_Int_t *p)
Definition: exp.h:68
assert
#define assert(ex)
Definition: util_old.h:213
Vec_StrPrintStr
static void Vec_StrPrintStr(Vec_Str_t *p, const char *pStr)
Definition: vecStr.h:627
Mio_SopVar1
Vec_Int_t * Mio_SopVar1(int i)
Definition: mioSop.c:149
Vec_Int_t* Mio_SopConst0 ( )

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

Synopsis [Create constant 0 literal.]

Description []

SideEffects []

SeeAlso []

Definition at line 168 of file mioSop.c.

169 {
170  Vec_Int_t * vSop;
171  vSop = Vec_IntAlloc( 1 );
172  return vSop;
173 }
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_Int_t* Mio_SopConst1 ( )

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

Synopsis [Create constant 1 literal.]

Description []

SideEffects []

SeeAlso []

Definition at line 186 of file mioSop.c.

187 {
188  Vec_Int_t * vSop;
189  vSop = Vec_IntAlloc( 1 );
190  Vec_IntPush( vSop, 0 );
191  return vSop;
192 }
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Vec_Int_t* Mio_SopCoverAnd ( Vec_Int_t *  p,
Vec_Int_t *  q 
)

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

Synopsis [Make the AND of two covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 106 of file mioSop.c.

107 {
108  Vec_Int_t * r;
109  unsigned EntryP, EntryQ;
110  int i, k;
111  r = Vec_IntAlloc( Vec_IntSize(p) * Vec_IntSize(q) );
112  Vec_IntForEachEntry( p, EntryP, i )
113  Vec_IntForEachEntry( q, EntryQ, k )
114  if ( !Mio_CubeEmpty( Mio_CubeAnd(EntryP, EntryQ) ) )
115  Mio_SopPushSCC( r, Mio_CubeAnd(EntryP, EntryQ) );
116  return r;
117 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
if
if(last==0)
Definition: sparse_int.h:34
Mio_SopPushSCC
void Mio_SopPushSCC(Vec_Int_t *p, unsigned c)
FUNCTION DEFINITIONS ///.
Definition: mioSop.c:52
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Mio_CubeEmpty
static int Mio_CubeEmpty(unsigned x)
Definition: mioSop.c:33
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Mio_CubeAnd
static unsigned Mio_CubeAnd(unsigned x, unsigned y)
Definition: mioSop.c:34
Vec_Int_t* Mio_SopCoverOr ( Vec_Int_t *  p,
Vec_Int_t *  q 
)

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

Synopsis [Make the OR of two covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 82 of file mioSop.c.

83 {
84  Vec_Int_t * r;
85  unsigned Entry;
86  int i;
87  r = Vec_IntAlloc( Vec_IntSize(p) + Vec_IntSize(q) );
88  Vec_IntForEachEntry( p, Entry, i )
89  Vec_IntPush( r, Entry );
90  Vec_IntForEachEntry( q, Entry, i )
91  Mio_SopPushSCC( r, Entry );
92  return r;
93 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Mio_SopPushSCC
void Mio_SopPushSCC(Vec_Int_t *p, unsigned c)
FUNCTION DEFINITIONS ///.
Definition: mioSop.c:52
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
char* Mio_SopDeriveFromArray ( Vec_Int_t *  vSop,
int  nVars,
Vec_Str_t *  vStr,
int  fPolarity 
)

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

Synopsis [Derives SOP representation as the char string.]

Description []

SideEffects []

SeeAlso []

Definition at line 205 of file mioSop.c.

206 {
207  unsigned Entry;
208  int i, k;
209  Vec_StrClear( vStr );
210  if ( Vec_IntSize(vSop) == 0 )
211  {
212  Vec_StrPush( vStr, ' ' );
213  Vec_StrPush( vStr, (char)('1'-fPolarity) );
214  Vec_StrPush( vStr, '\n' );
215  Vec_StrPush( vStr, '\0' );
216  return Vec_StrArray( vStr );
217  }
218  if ( Vec_IntSize(vSop) == 1 && Vec_IntEntry(vSop, 0) == 0 )
219  {
220  Vec_StrPush( vStr, ' ' );
221  Vec_StrPush( vStr, (char)('0'+fPolarity) );
222  Vec_StrPush( vStr, '\n' );
223  Vec_StrPush( vStr, '\0' );
224  return Vec_StrArray( vStr );
225  }
226  // create cubes
227  Vec_IntForEachEntry( vSop, Entry, i )
228  {
229  for ( k = 0; k < nVars; k++ )
230  {
231  if ( Mio_CubeHasVar0( Entry, k ) )
232  Vec_StrPush( vStr, '0' );
233  else if ( Mio_CubeHasVar1( Entry, k ) )
234  Vec_StrPush( vStr, '1' );
235  else
236  Vec_StrPush( vStr, '-' );
237  }
238  Vec_StrPush( vStr, ' ' );
239  Vec_StrPush( vStr, (char)('0'+fPolarity) );
240  Vec_StrPush( vStr, '\n' );
241  }
242  Vec_StrPush( vStr, '\0' );
243  return Vec_StrArray( vStr );
244 }
Vec_StrArray
static char * Vec_StrArray(Vec_Str_t *p)
Definition: vecStr.h:272
Vec_StrClear
static void Vec_StrClear(Vec_Str_t *p)
Definition: vecStr.h:519
Mio_CubeHasVar1
static int Mio_CubeHasVar1(unsigned x, int v)
Definition: mioSop.c:32
Vec_StrPush
static void Vec_StrPush(Vec_Str_t *p, char Entry)
Definition: vecStr.h:535
Vec_IntEntry
static int Vec_IntEntry(Vec_Int_t *p, int i)
Definition: bblif.c:268
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Mio_CubeHasVar0
static int Mio_CubeHasVar0(unsigned x, int v)
Definition: mioSop.c:31
void Mio_SopPushSCC ( Vec_Int_t *  p,
unsigned  c 
)

FUNCTION DEFINITIONS ///.

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

Synopsis [Push while performing SCC.]

Description []

SideEffects []

SeeAlso []

Definition at line 52 of file mioSop.c.

53 {
54  unsigned Entry;
55  int i, k = 0;
56  Vec_IntForEachEntry( p, Entry, i )
57  {
58  if ( Mio_CubeContains( Entry, c ) ) // Entry contains c
59  {
60  assert( i == k );
61  return;
62  }
63  if ( Mio_CubeContains( c, Entry ) ) // c contains Entry
64  continue;
65  Vec_IntWriteEntry( p, k++, Entry );
66  }
67  Vec_IntShrink( p, k );
68  Vec_IntPush( p, c );
69 }
Mio_CubeContains
static int Mio_CubeContains(unsigned x, unsigned y)
Definition: mioSop.c:35
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
Vec_IntWriteEntry
static void Vec_IntWriteEntry(Vec_Int_t *p, int i, int Entry)
Definition: bblif.c:285
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Vec_IntShrink
static void Vec_IntShrink(Vec_Int_t *p, int nSizeNew)
Definition: bblif.c:435
assert
#define assert(ex)
Definition: util_old.h:213
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition: vecInt.h:54
Vec_Int_t* Mio_SopVar0 ( int  i)

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

Synopsis [Create negative literal.]

Description []

SideEffects []

SeeAlso []

Definition at line 130 of file mioSop.c.

131 {
132  Vec_Int_t * vSop;
133  vSop = Vec_IntAlloc( 1 );
134  Vec_IntPush( vSop, Mio_CubeVar0(i) );
135  return vSop;
136 }
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Mio_CubeVar0
static ABC_NAMESPACE_IMPL_START unsigned Mio_CubeVar0(int v)
DECLARATIONS ///.
Definition: mioSop.c:29
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468
Vec_Int_t* Mio_SopVar1 ( int  i)

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

Synopsis [Create positive literal.]

Description []

SideEffects []

SeeAlso []

Definition at line 149 of file mioSop.c.

150 {
151  Vec_Int_t * vSop;
152  vSop = Vec_IntAlloc( 1 );
153  Vec_IntPush( vSop, Mio_CubeVar1(i) );
154  return vSop;
155 }
Mio_CubeVar1
static unsigned Mio_CubeVar1(int v)
Definition: mioSop.c:30
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition: bblif.c:37
Vec_IntAlloc
static Vec_Int_t * Vec_IntAlloc(int nCap)
FUNCTION DEFINITIONS ///.
Definition: bblif.c:149
Vec_IntPush
static void Vec_IntPush(Vec_Int_t *p, int Entry)
Definition: bblif.c:468