abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
extraUtilThresh.c File Reference
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "misc/vec/vec.h"
#include "misc/util/utilTruth.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START void Extra_ThreshPrintChow (int Chow0, int *pChow, int nVars)
 DECLARATIONS ///. More...
 
int Extra_ThreshComputeChow (word *t, int nVars, int *pChow)
 
void Extra_ThreshSortByChow (word *t, int nVars, int *pChow)
 
static int Extra_ThreshWeightedSum (int *pW, int nVars, int m)
 
int Extra_ThreshSelectWeights3 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights4 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights5 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights6 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights7 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights8 (word *t, int nVars, int *pW)
 
int Extra_ThreshSelectWeights (word *t, int nVars, int *pW)
 
int Extra_ThreshCheck (word *t, int nVars, int *pW)
 
void Extra_ThreshCheckTest ()
 

Function Documentation

int Extra_ThreshCheck ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 283 of file extraUtilThresh.c.

284 {
285  int Chow0, Chow[16];
286  if ( !Abc_TtIsUnate(t, nVars) )
287  return 0;
288  Abc_TtMakePosUnate( t, nVars );
289  Chow0 = Extra_ThreshComputeChow( t, nVars, Chow );
290  Extra_ThreshSortByChow( t, nVars, Chow );
291  return Extra_ThreshSelectWeights( t, nVars, pW );
292 }
Extra_ThreshSelectWeights
int Extra_ThreshSelectWeights(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:265
Extra_ThreshSortByChow
void Extra_ThreshSortByChow(word *t, int nVars, int *pChow)
Definition: extraUtilThresh.c:72
Abc_TtMakePosUnate
static void Abc_TtMakePosUnate(word *t, int nVars)
Definition: utilTruth.h:1683
Extra_ThreshComputeChow
int Extra_ThreshComputeChow(word *t, int nVars, int *pChow)
Definition: extraUtilThresh.c:57
Abc_TtIsUnate
static int Abc_TtIsUnate(word *t, int nVars)
Definition: utilTruth.h:1667
void Extra_ThreshCheckTest ( )

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

Synopsis [Checks unateness of a function.]

Description []

SideEffects []

SeeAlso []

Definition at line 305 of file extraUtilThresh.c.

306 {
307  int nVars = 5;
308  int T, Chow0, Chow[16], Weights[16];
309 // word t = s_Truths6[0] & s_Truths6[1] & s_Truths6[2] & s_Truths6[3] & s_Truths6[4];
310 // word t = (s_Truths6[0] & s_Truths6[1]) | (s_Truths6[0] & s_Truths6[2] & s_Truths6[3]) | (s_Truths6[0] & s_Truths6[2] & s_Truths6[4]);
311  word t = (s_Truths6[2] & s_Truths6[1]) | (s_Truths6[2] & s_Truths6[0] & s_Truths6[3]) | (s_Truths6[2] & s_Truths6[0] & ~s_Truths6[4]);
312 // word t = (s_Truths6[0] & s_Truths6[1]) | (s_Truths6[0] & s_Truths6[2] & s_Truths6[3]) | (s_Truths6[0] & s_Truths6[2] & s_Truths6[4]) | (s_Truths6[1] & s_Truths6[2] & s_Truths6[3]);
313 // word t = (s_Truths6[0] & s_Truths6[1]) | (s_Truths6[0] & s_Truths6[2]) | (s_Truths6[0] & s_Truths6[3] & s_Truths6[4] & s_Truths6[5]) |
314 // (s_Truths6[1] & s_Truths6[2] & s_Truths6[3]) | (s_Truths6[1] & s_Truths6[2] & s_Truths6[4]) | (s_Truths6[1] & s_Truths6[2] & s_Truths6[5]);
315  int i;
316  assert( nVars <= 8 );
317  for ( i = 0; i < nVars; i++ )
318  printf( "%d %d %d\n", i, Abc_TtPosVar(&t, nVars, i), Abc_TtNegVar(&t, nVars, i) );
319 // word t = s_Truths6[0] & s_Truths6[1] & s_Truths6[2];
320  Chow0 = Extra_ThreshComputeChow( &t, nVars, Chow );
321  if ( (T = Extra_ThreshCheck(&t, nVars, Weights)) )
322  Extra_ThreshPrintChow( T, Weights, nVars );
323  else
324  printf( "No threshold\n" );
325 }
Extra_ThreshCheck
int Extra_ThreshCheck(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:283
word
unsigned __int64 word
DECLARATIONS ///.
Definition: kitPerm.c:36
Extra_ThreshComputeChow
int Extra_ThreshComputeChow(word *t, int nVars, int *pChow)
Definition: extraUtilThresh.c:57
s_Truths6
static word s_Truths6[6]
Definition: extraUtilEnum.c:430
Abc_TtPosVar
static int Abc_TtPosVar(word *t, int nVars, int iVar)
Definition: utilTruth.h:1617
Extra_ThreshPrintChow
ABC_NAMESPACE_IMPL_START void Extra_ThreshPrintChow(int Chow0, int *pChow, int nVars)
DECLARATIONS ///.
Definition: extraUtilThresh.c:50
Abc_TtNegVar
static int Abc_TtNegVar(word *t, int nVars, int iVar)
Definition: utilTruth.h:1642
assert
#define assert(ex)
Definition: util_old.h:213
int Extra_ThreshComputeChow ( word *  t,
int  nVars,
int *  pChow 
)

Definition at line 57 of file extraUtilThresh.c.

58 {
59  int i, k, Chow0 = 0, nMints = (1 << nVars);
60  memset( pChow, 0, sizeof(int) * nVars );
61  // compute Chow coefs
62  for ( i = 0; i < nMints; i++ )
63  if ( Abc_TtGetBit(t, i) )
64  for ( Chow0++, k = 0; k < nVars; k++ )
65  if ( (i >> k) & 1 )
66  pChow[k]++;
67  // compute modified Chow coefs
68  for ( k = 0; k < nVars; k++ )
69  pChow[k] = 2 * pChow[k] - Chow0;
70  return Chow0 - (1 << (nVars-1));
71 }
memset
char * memset()
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
ABC_NAMESPACE_IMPL_START void Extra_ThreshPrintChow ( int  Chow0,
int *  pChow,
int  nVars 
)

DECLARATIONS ///.

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

FileName [extraUtilThresh.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [extra]

Synopsis [Dealing with threshold functions.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - October 7, 2014.]

Revision [

Id:
extraUtilThresh.c,v 1.0 2014/10/07 00:00:00 alanmi Exp

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

Synopsis [Checks thresholdness of the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 50 of file extraUtilThresh.c.

51 {
52  int i;
53  for ( i = 0; i < nVars; i++ )
54  printf( "%d ", pChow[i] );
55  printf( " %d\n", Chow0 );
56 }
int Extra_ThreshSelectWeights ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 265 of file extraUtilThresh.c.

266 {
267  if ( nVars <= 2 )
268  return (t[0] & 0xF) != 6 && (t[0] & 0xF) != 9;
269  if ( nVars == 3 )
270  return Extra_ThreshSelectWeights3( t, nVars, pW );
271  if ( nVars == 4 )
272  return Extra_ThreshSelectWeights4( t, nVars, pW );
273  if ( nVars == 5 )
274  return Extra_ThreshSelectWeights5( t, nVars, pW );
275  if ( nVars == 6 )
276  return Extra_ThreshSelectWeights6( t, nVars, pW );
277  if ( nVars == 7 )
278  return Extra_ThreshSelectWeights7( t, nVars, pW );
279  if ( nVars == 8 )
280  return Extra_ThreshSelectWeights8( t, nVars, pW );
281  return 0;
282 }
Extra_ThreshSelectWeights7
int Extra_ThreshSelectWeights7(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:206
Extra_ThreshSelectWeights6
int Extra_ThreshSelectWeights6(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:178
Extra_ThreshSelectWeights5
int Extra_ThreshSelectWeights5(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:151
Extra_ThreshSelectWeights8
int Extra_ThreshSelectWeights8(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:235
Extra_ThreshSelectWeights3
int Extra_ThreshSelectWeights3(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:98
Extra_ThreshSelectWeights4
int Extra_ThreshSelectWeights4(word *t, int nVars, int *pW)
Definition: extraUtilThresh.c:125
int Extra_ThreshSelectWeights3 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 98 of file extraUtilThresh.c.

99 {
100  int m, Lmin, Lmax, nMints = (1 << nVars);
101  assert( nVars == 3 );
102  for ( pW[2] = 1; pW[2] <= nVars; pW[2]++ )
103  for ( pW[1] = pW[2]; pW[1] <= nVars; pW[1]++ )
104  for ( pW[0] = pW[1]; pW[0] <= nVars; pW[0]++ )
105  {
106  Lmin = 10000; Lmax = 0;
107  for ( m = 0; m < nMints; m++ )
108  {
109  if ( Abc_TtGetBit(t, m) )
110  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
111  else
112  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
113  if ( Lmax >= Lmin )
114  break;
115 // printf( "%c%d ", Abc_TtGetBit(t, m) ? '+' : '-', Extra_ThreshWeightedSum(pW, nVars, m) );
116  }
117 // printf( " -%d +%d\n", Lmax, Lmin );
118  if ( m < nMints )
119  continue;
120  assert( Lmax < Lmin );
121  return Lmin;
122  }
123  return 0;
124 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
int Extra_ThreshSelectWeights4 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 125 of file extraUtilThresh.c.

126 {
127  int m, Lmin, Lmax, nMints = (1 << nVars);
128  assert( nVars == 4 );
129  for ( pW[3] = 1; pW[3] <= nVars; pW[3]++ )
130  for ( pW[2] = pW[3]; pW[2] <= nVars; pW[2]++ )
131  for ( pW[1] = pW[2]; pW[1] <= nVars; pW[1]++ )
132  for ( pW[0] = pW[1]; pW[0] <= nVars; pW[0]++ )
133  {
134  Lmin = 10000; Lmax = 0;
135  for ( m = 0; m < nMints; m++ )
136  {
137  if ( Abc_TtGetBit(t, m) )
138  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
139  else
140  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
141  if ( Lmax >= Lmin )
142  break;
143  }
144  if ( m < nMints )
145  continue;
146  assert( Lmax < Lmin );
147  return Lmin;
148  }
149  return 0;
150 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
int Extra_ThreshSelectWeights5 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 151 of file extraUtilThresh.c.

152 {
153  int m, Lmin, Lmax, nMints = (1 << nVars), Limit = nVars + 0;
154  assert( nVars == 5 );
155  for ( pW[4] = 1; pW[4] <= Limit; pW[4]++ )
156  for ( pW[3] = pW[4]; pW[3] <= Limit; pW[3]++ )
157  for ( pW[2] = pW[3]; pW[2] <= Limit; pW[2]++ )
158  for ( pW[1] = pW[2]; pW[1] <= Limit; pW[1]++ )
159  for ( pW[0] = pW[1]; pW[0] <= Limit; pW[0]++ )
160  {
161  Lmin = 10000; Lmax = 0;
162  for ( m = 0; m < nMints; m++ )
163  {
164  if ( Abc_TtGetBit(t, m) )
165  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
166  else
167  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
168  if ( Lmax >= Lmin )
169  break;
170  }
171  if ( m < nMints )
172  continue;
173  assert( Lmax < Lmin );
174  return Lmin;
175  }
176  return 0;
177 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
int Extra_ThreshSelectWeights6 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 178 of file extraUtilThresh.c.

179 {
180  int m, Lmin, Lmax, nMints = (1 << nVars), Limit = nVars + 3;
181  assert( nVars == 6 );
182  for ( pW[5] = 1; pW[5] <= Limit; pW[5]++ )
183  for ( pW[4] = pW[5]; pW[4] <= Limit; pW[4]++ )
184  for ( pW[3] = pW[4]; pW[3] <= Limit; pW[3]++ )
185  for ( pW[2] = pW[3]; pW[2] <= Limit; pW[2]++ )
186  for ( pW[1] = pW[2]; pW[1] <= Limit; pW[1]++ )
187  for ( pW[0] = pW[1]; pW[0] <= Limit; pW[0]++ )
188  {
189  Lmin = 10000; Lmax = 0;
190  for ( m = 0; m < nMints; m++ )
191  {
192  if ( Abc_TtGetBit(t, m) )
193  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
194  else
195  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
196  if ( Lmax >= Lmin )
197  break;
198  }
199  if ( m < nMints )
200  continue;
201  assert( Lmax < Lmin );
202  return Lmin;
203  }
204  return 0;
205 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
int Extra_ThreshSelectWeights7 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 206 of file extraUtilThresh.c.

207 {
208  int m, Lmin, Lmax, nMints = (1 << nVars), Limit = nVars + 6;
209  assert( nVars == 7 );
210  for ( pW[6] = 1; pW[6] <= Limit; pW[6]++ )
211  for ( pW[5] = pW[6]; pW[5] <= Limit; pW[5]++ )
212  for ( pW[4] = pW[5]; pW[4] <= Limit; pW[4]++ )
213  for ( pW[3] = pW[4]; pW[3] <= Limit; pW[3]++ )
214  for ( pW[2] = pW[3]; pW[2] <= Limit; pW[2]++ )
215  for ( pW[1] = pW[2]; pW[1] <= Limit; pW[1]++ )
216  for ( pW[0] = pW[1]; pW[0] <= Limit; pW[0]++ )
217  {
218  Lmin = 10000; Lmax = 0;
219  for ( m = 0; m < nMints; m++ )
220  {
221  if ( Abc_TtGetBit(t, m) )
222  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
223  else
224  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
225  if ( Lmax >= Lmin )
226  break;
227  }
228  if ( m < nMints )
229  continue;
230  assert( Lmax < Lmin );
231  return Lmin;
232  }
233  return 0;
234 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
int Extra_ThreshSelectWeights8 ( word *  t,
int  nVars,
int *  pW 
)

Definition at line 235 of file extraUtilThresh.c.

236 {
237  int m, Lmin, Lmax, nMints = (1 << nVars), Limit = nVars + 1; // <<-- incomplete detection to save runtime!
238  assert( nVars == 8 );
239  for ( pW[7] = 1; pW[7] <= Limit; pW[7]++ )
240  for ( pW[6] = pW[7]; pW[6] <= Limit; pW[6]++ )
241  for ( pW[5] = pW[6]; pW[5] <= Limit; pW[5]++ )
242  for ( pW[4] = pW[5]; pW[4] <= Limit; pW[4]++ )
243  for ( pW[3] = pW[4]; pW[3] <= Limit; pW[3]++ )
244  for ( pW[2] = pW[3]; pW[2] <= Limit; pW[2]++ )
245  for ( pW[1] = pW[2]; pW[1] <= Limit; pW[1]++ )
246  for ( pW[0] = pW[1]; pW[0] <= Limit; pW[0]++ )
247  {
248  Lmin = 10000; Lmax = 0;
249  for ( m = 0; m < nMints; m++ )
250  {
251  if ( Abc_TtGetBit(t, m) )
252  Lmin = Abc_MinInt( Lmin, Extra_ThreshWeightedSum(pW, nVars, m) );
253  else
254  Lmax = Abc_MaxInt( Lmax, Extra_ThreshWeightedSum(pW, nVars, m) );
255  if ( Lmax >= Lmin )
256  break;
257  }
258  if ( m < nMints )
259  continue;
260  assert( Lmax < Lmin );
261  return Lmin;
262  }
263  return 0;
264 }
Abc_TtGetBit
static int Abc_TtGetBit(word *p, int i)
MACRO DEFINITIONS ///.
Definition: utilTruth.h:149
Abc_MaxInt
static int Abc_MaxInt(int a, int b)
Definition: abc_global.h:238
Abc_MinInt
static int Abc_MinInt(int a, int b)
Definition: abc_global.h:239
assert
#define assert(ex)
Definition: util_old.h:213
Extra_ThreshWeightedSum
static int Extra_ThreshWeightedSum(int *pW, int nVars, int m)
Definition: extraUtilThresh.c:90
void Extra_ThreshSortByChow ( word *  t,
int  nVars,
int *  pChow 
)

Definition at line 72 of file extraUtilThresh.c.

73 {
74  int i, nWords = Abc_TtWordNum(nVars);
75  while ( 1 )
76  {
77  int fChange = 0;
78  for ( i = 0; i < nVars - 1; i++ )
79  {
80  if ( pChow[i] >= pChow[i+1] )
81  continue;
82  ABC_SWAP( int, pChow[i], pChow[i+1] );
83  Abc_TtSwapAdjacent( t, nWords, i );
84  fChange = 1;
85  }
86  if ( !fChange )
87  return;
88  }
89 }
nWords
int nWords
Definition: abcNpn.c:127
ABC_SWAP
#define ABC_SWAP(Type, a, b)
Definition: abc_global.h:218
Abc_TtWordNum
static int Abc_TtWordNum(int nVars)
Definition: utilTruth.h:169
Abc_TtSwapAdjacent
static void Abc_TtSwapAdjacent(word *pTruth, int nWords, int iVar)
Definition: utilTruth.h:1190
static int Extra_ThreshWeightedSum ( int *  pW,
int  nVars,
int  m 
)
inlinestatic

Definition at line 90 of file extraUtilThresh.c.

91 {
92  int i, Cost = 0;
93  for ( i = 0; i < nVars; i++ )
94  if ( (m >> i) & 1 )
95  Cost += pW[i];
96  return Cost;
97 }