abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
ifDec75.c File Reference
#include "if.h"
#include "misc/extra/extra.h"
#include "bool/kit/kit.h"
#include "opt/dau/dau.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START int Dau_DsdCheckDecExist_rec (char *pStr, char **p, int *pMatches, int *pnSupp)
 DECLARATIONS ///. More...
 
int Dau_DsdCheckDecExist (char *pDsd)
 
int Dau_DsdCheckDecAndExist_rec (char *pStr, char **p, int *pMatches, int *pnSupp)
 
int Dau_DsdCheckDecAndExist (char *pDsd)
 
int If_CutPerformCheck75__ (If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
 
int If_CutPerformCheck75 (If_Man_t *p, unsigned *pTruth0, int nVars, int nLeaves, char *pStr)
 

Function Documentation

int Dau_DsdCheckDecAndExist ( char *  pDsd)

Definition at line 185 of file ifDec75.c.

186 {
187  int nSupp = 0;
188  if ( pDsd[1] == 0 )
189  return 1;
190  return Dau_DsdCheckDecAndExist_rec( pDsd, &pDsd, Dau_DsdComputeMatches(pDsd), &nSupp );
191 }
Dau_DsdComputeMatches
int * Dau_DsdComputeMatches(char *p)
Definition: dauDsd.c:80
Dau_DsdCheckDecAndExist_rec
int Dau_DsdCheckDecAndExist_rec(char *pStr, char **p, int *pMatches, int *pnSupp)
Definition: ifDec75.c:123
int Dau_DsdCheckDecAndExist_rec ( char *  pStr,
char **  p,
int *  pMatches,
int *  pnSupp 
)

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

Synopsis [Finds all boundsets for which AND-decomposition exists.]

Description []

SideEffects []

SeeAlso []

Definition at line 123 of file ifDec75.c.

124 {
125  if ( **p == '!' )
126  (*p)++;
127  while ( (**p >= 'A' && **p <= 'F') || (**p >= '0' && **p <= '9') )
128  (*p)++;
129  if ( **p >= 'a' && **p <= 'z' ) // var
130  {
131  (*pnSupp)++;
132  return 0;
133  }
134  if ( **p == '(' ) // and
135  {
136  unsigned Mask = 0;
137  int m, i, pSupps[8] = {0}, nParts = 0, nSimple = 0, nMints;
138  char * q = pStr + pMatches[ *p - pStr ];
139  assert( *q == **p + 1 + (**p != '(') );
140  for ( (*p)++; *p < q; (*p)++ )
141  {
142  Mask |= Dau_DsdCheckDecAndExist_rec( pStr, p, pMatches, &pSupps[nParts] );
143  nSimple += (pSupps[nParts] == 1);
144  *pnSupp += pSupps[nParts++];
145  }
146  assert( *p == q );
147  assert( nParts > 1 );
148  if ( nSimple > 0 )
149  {
150  nMints = (1 << nParts);
151  for ( m = 1; m < nMints; m++ )
152  {
153  int Sum = 0;
154  for ( i = 0; i < nParts; i++ )
155  if ( pSupps[i] > 1 && ((m >> i) & 1) )
156  Sum += pSupps[i];
157  assert( Sum <= 8 );
158  if ( Sum >= 2 )
159  for ( i = 0; i < nSimple; i++ )
160  Mask |= (1 << (Sum + i));
161  }
162  for ( i = 2; i < nSimple; i++ )
163  Mask |= (1 << i);
164  }
165  return Mask;
166  }
167  if ( **p == '<' || **p == '{' || **p == '[' ) // mux/xor/nondec
168  {
169  int uSupp;
170  unsigned Mask = 0;
171  char * q = pStr + pMatches[ *p - pStr ];
172  assert( *q == **p + 1 + (**p != '(') );
173  for ( (*p)++; *p < q; (*p)++ )
174  {
175  uSupp = 0;
176  Mask |= Dau_DsdCheckDecAndExist_rec( pStr, p, pMatches, &uSupp );
177  *pnSupp += uSupp;
178  }
179  assert( *p == q );
180  return Mask;
181  }
182  assert( 0 );
183  return 0;
184 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
pSupps
static int * pSupps
Definition: abcUtil.c:2053
Dau_DsdCheckDecAndExist_rec
int Dau_DsdCheckDecAndExist_rec(char *pStr, char **p, int *pMatches, int *pnSupp)
Definition: ifDec75.c:123
assert
#define assert(ex)
Definition: util_old.h:213
int Dau_DsdCheckDecExist ( char *  pDsd)

Definition at line 104 of file ifDec75.c.

105 {
106  int nSupp = 0;
107  if ( pDsd[1] == 0 )
108  return 0;
109  return Dau_DsdCheckDecExist_rec( pDsd, &pDsd, Dau_DsdComputeMatches(pDsd), &nSupp );
110 }
Dau_DsdComputeMatches
int * Dau_DsdComputeMatches(char *p)
Definition: dauDsd.c:80
Dau_DsdCheckDecExist_rec
ABC_NAMESPACE_IMPL_START int Dau_DsdCheckDecExist_rec(char *pStr, char **p, int *pMatches, int *pnSupp)
DECLARATIONS ///.
Definition: ifDec75.c:48
ABC_NAMESPACE_IMPL_START int Dau_DsdCheckDecExist_rec ( char *  pStr,
char **  p,
int *  pMatches,
int *  pnSupp 
)

DECLARATIONS ///.

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

FileName [ifDec75.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [FPGA mapping based on priority cuts.]

Synopsis [Performs additional check.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - November 21, 2006.]

Revision [

Id:
ifDec75.c,v 1.00 2006/11/21 00:00:00 alanmi Exp

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Finds all boundsets for which decomposition exists.]

Description []

SideEffects []

SeeAlso []

Definition at line 48 of file ifDec75.c.

49 {
50  if ( **p == '!' )
51  (*p)++;
52  while ( (**p >= 'A' && **p <= 'F') || (**p >= '0' && **p <= '9') )
53  (*p)++;
54  if ( **p >= 'a' && **p <= 'z' ) // var
55  {
56  (*pnSupp)++;
57  return 0;
58  }
59  if ( **p == '(' || **p == '[' ) // and/xor
60  {
61  unsigned Mask = 0;
62  int m, pSupps[8] = {0}, nParts = 0, nMints;
63  char * q = pStr + pMatches[ *p - pStr ];
64  assert( *q == **p + 1 + (**p != '(') );
65  for ( (*p)++; *p < q; (*p)++ )
66  {
67  Mask |= Dau_DsdCheckDecExist_rec( pStr, p, pMatches, &pSupps[nParts] );
68  *pnSupp += pSupps[nParts++];
69  }
70  assert( *p == q );
71  assert( nParts > 1 );
72  nMints = (1 << nParts);
73  for ( m = 1; m < nMints; m++ )
74  {
75  int i, Sum = 0;
76  for ( i = 0; i < nParts; i++ )
77  if ( (m >> i) & 1 )
78  Sum += pSupps[i];
79  assert( Sum > 0 && Sum <= 8 );
80  if ( Sum >= 2 )
81  Mask |= (1 << Sum);
82  }
83  return Mask;
84  }
85  if ( **p == '<' || **p == '{' ) // mux
86  {
87  int uSupp;
88  unsigned Mask = 0;
89  char * q = pStr + pMatches[ *p - pStr ];
90  assert( *q == **p + 1 + (**p != '(') );
91  for ( (*p)++; *p < q; (*p)++ )
92  {
93  uSupp = 0;
94  Mask |= Dau_DsdCheckDecExist_rec( pStr, p, pMatches, &uSupp );
95  *pnSupp += uSupp;
96  }
97  assert( *p == q );
98  Mask |= (1 << *pnSupp);
99  return Mask;
100  }
101  assert( 0 );
102  return 0;
103 }
p
static Llb_Mgr_t * p
Definition: llb3Image.c:950
pSupps
static int * pSupps
Definition: abcUtil.c:2053
Dau_DsdCheckDecExist_rec
ABC_NAMESPACE_IMPL_START int Dau_DsdCheckDecExist_rec(char *pStr, char **p, int *pMatches, int *pnSupp)
DECLARATIONS ///.
Definition: ifDec75.c:48
assert
#define assert(ex)
Definition: util_old.h:213
int If_CutPerformCheck75 ( If_Man_t *  p,
unsigned *  pTruth0,
int  nVars,
int  nLeaves,
char *  pStr 
)

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

Synopsis [Performs additional check.]

Description []

SideEffects []

SeeAlso []

Definition at line 303 of file ifDec75.c.

304 {
305  word * pTruthW = (word *)pTruth0;
306  word pTruth[4] = { pTruthW[0], pTruthW[1], pTruthW[2], pTruthW[3] };
307  assert( nLeaves <= 8 );
308  if ( !p->pPars->fCutMin )
309  Abc_TtMinimumBase( pTruth, NULL, nLeaves, &nLeaves );
310  if ( nLeaves < 6 )
311  return 1;
312 // if ( nLeaves < 8 && If_CutPerformCheck07( p, (unsigned *)pTruth, nVars, nLeaves, "44" ) )
313  if ( nLeaves < 8 && If_CutPerformCheck16( p, (unsigned *)pTruth, nVars, nLeaves, "44" ) )
314  return 1;
315  // this is faster but not compatible with -z
316  if ( !p->pPars->fDeriveLuts && p->pPars->fEnableCheck75 && nLeaves == 8 )
317  {
318 // char pDsdStr[1000] = "(!(abd)!(c!([fe][gh])))";
319  char pDsdStr[1000];
320  int nSizeNonDec = Dau_DsdDecompose( (word *)pTruth, nLeaves, 0, 0, pDsdStr );
321  if ( nSizeNonDec >= 5 )
322  return 0;
323  if ( Dau_DsdCheckDecAndExist(pDsdStr) & 0x10 ) // bit 4
324  return 1;
325  return 0;
326  }
327  if ( If_CutPerformCheck45( p, (unsigned *)pTruth, nVars, nLeaves, pStr ) )
328  return 1;
329  if ( If_CutPerformCheck54( p, (unsigned *)pTruth, nVars, nLeaves, pStr ) )
330  return 1;
331  return 0;
332 }
Abc_TtMinimumBase
static int Abc_TtMinimumBase(word *t, int *pSupp, int nVarsAll, int *pnVars)
Definition: utilTruth.h:1314
If_Par_t_::fDeriveLuts
int fDeriveLuts
Definition: if.h:138
Dau_DsdDecompose
int Dau_DsdDecompose(word *pTruth, int nVarsInit, int fSplitPrime, int fWriteTruth, char *pRes)
Definition: dauDsd.c:1912
Dau_DsdCheckDecAndExist
int Dau_DsdCheckDecAndExist(char *pDsd)
Definition: ifDec75.c:185
If_CutPerformCheck54
int If_CutPerformCheck54(If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
Definition: ifDec16.c:1886
If_Par_t_::fEnableCheck75
int fEnableCheck75
Definition: if.h:131
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
If_Man_t_::pPars
If_Par_t * pPars
Definition: if.h:184
If_Par_t_::fCutMin
int fCutMin
Definition: if.h:120
assert
#define assert(ex)
Definition: util_old.h:213
If_CutPerformCheck16
int If_CutPerformCheck16(If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
Definition: ifDec16.c:2216
If_CutPerformCheck45
int If_CutPerformCheck45(If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
Definition: ifDec16.c:1865
int If_CutPerformCheck75__ ( If_Man_t *  p,
unsigned *  pTruth,
int  nVars,
int  nLeaves,
char *  pStr 
)

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

Synopsis [Performs additional check.]

Description []

SideEffects []

SeeAlso []

Definition at line 204 of file ifDec75.c.

205 {
206  char pDsdStr[1000];
207  int nSizeNonDec, nDecExists, nDecAndExists;
208  static int Counter = 0;
209  Counter++;
210  if ( nLeaves < 6 )
211  return 1;
212  assert( nLeaves <= 8 );
213  if ( nLeaves < 8 && If_CutPerformCheck16( p, pTruth, nVars, nLeaves, "44" ) )
214  return 1;
215  // check decomposability
216  nSizeNonDec = Dau_DsdDecompose( (word *)pTruth, nLeaves, 0, 0, pDsdStr );
217 // printf( "Vars = %d %s", nLeaves, pDsdStr ); printf( "\n" );
218 // Extra_PrintBinary( stdout, &nDecExists, 8 ); printf( "\n" );
219 // Extra_PrintBinary( stdout, &nDecAndExists, 8 ); printf( "\n" );
220  if ( nLeaves == 8 )
221  {
222  if ( nSizeNonDec >= 5 )
223  return 0;
224  nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr );
225  if ( nDecAndExists & 0x10 ) // bit 4
226  return 1;
227  else
228  return 0;
229  }
230  if ( nLeaves == 7 )
231  {
232  extern void If_Dec7MinimumBase( word uTruth[2], int * pSupp, int nVarsAll, int * pnVars );
233  word * pT = (word *)pTruth;
234  word pCof0[2], pCof1[2];
235  int v, nVarsMin;
236  if ( nSizeNonDec < 5 )
237  {
238  nDecExists = Dau_DsdCheckDecExist( pDsdStr );
239  if ( nDecExists & 0x10 ) // bit 4
240  return 1;
241  nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr );
242  if ( nDecAndExists & 0x18 ) // bit 4, 3
243  return 1;
244  }
245  // check cofactors
246  for ( v = 0; v < 7; v++ )
247  {
248  pCof0[0] = pCof1[0] = pT[0];
249  pCof0[1] = pCof1[1] = pT[1];
250  Abc_TtCofactor0( pCof0, 2, v );
251  Abc_TtCofactor1( pCof1, 2, v );
252  if ( Abc_TtSupportSize(pCof0, 7) < 4 )
253  {
254  If_Dec7MinimumBase( pCof1, NULL, 7, &nVarsMin );
255  nSizeNonDec = Dau_DsdDecompose( pCof1, nVarsMin, 0, 0, pDsdStr );
256  if ( nSizeNonDec >= 5 )
257  continue;
258  nDecExists = Dau_DsdCheckDecExist( pDsdStr );
259  if ( nDecExists & 0x18 ) // bit 4, 3
260  return 1;
261  }
262  else if ( Abc_TtSupportSize(pCof1, 7) < 4 )
263  {
264  If_Dec7MinimumBase( pCof0, NULL, 7, &nVarsMin );
265  nSizeNonDec = Dau_DsdDecompose( pCof0, nVarsMin, 0, 0, pDsdStr );
266  if ( nSizeNonDec >= 5 )
267  continue;
268  nDecExists = Dau_DsdCheckDecExist( pDsdStr );
269  if ( nDecExists & 0x18 ) // bit 4, 3
270  return 1;
271  }
272  }
273  return 0;
274  }
275  if ( nLeaves == 6 )
276  {
277  if ( nSizeNonDec < 5 )
278  {
279  nDecExists = Dau_DsdCheckDecExist( pDsdStr );
280  if ( nDecExists & 0x18 ) // bit 4, 3
281  return 1;
282  nDecAndExists = Dau_DsdCheckDecAndExist( pDsdStr );
283  if ( nDecAndExists & 0x1C ) // bit 4, 3, 2
284  return 1;
285  }
286  return If_CutPerformCheck07( p, pTruth, nVars, nLeaves, pStr );
287  }
288  assert( 0 );
289  return 0;
290 }
Dau_DsdDecompose
int Dau_DsdDecompose(word *pTruth, int nVarsInit, int fSplitPrime, int fWriteTruth, char *pRes)
Definition: dauDsd.c:1912
Dau_DsdCheckDecAndExist
int Dau_DsdCheckDecAndExist(char *pDsd)
Definition: ifDec75.c:185
If_CutPerformCheck07
int If_CutPerformCheck07(If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
Definition: ifDec07.c:1071
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Counter
static int Counter
Definition: extraBddMisc.c:1877
Abc_TtCofactor0
static void Abc_TtCofactor0(word *pTruth, int nWords, int iVar)
Definition: utilTruth.h:425
Abc_TtCofactor1
static void Abc_TtCofactor1(word *pTruth, int nWords, int iVar)
Definition: utilTruth.h:444
Abc_TtSupportSize
static int Abc_TtSupportSize(word *t, int nVars)
Definition: utilTruth.h:986
assert
#define assert(ex)
Definition: util_old.h:213
Dau_DsdCheckDecExist
int Dau_DsdCheckDecExist(char *pDsd)
Definition: ifDec75.c:104
If_Dec7MinimumBase
void If_Dec7MinimumBase(word uTruth[2], int *pSupp, int nVarsAll, int *pnVars)
Definition: ifDec07.c:544
If_CutPerformCheck16
int If_CutPerformCheck16(If_Man_t *p, unsigned *pTruth, int nVars, int nLeaves, char *pStr)
Definition: ifDec16.c:2216