src/base/abci/abcMeasure.c File Reference

#include "abc.h"
#include "kit.h"
Include dependency graph for abcMeasure.c:

Go to the source code of this file.

Functions

void Abc_NtkPrintMeasures (unsigned *pTruth, int nVars)
void Abc_Ntk4VarObjPrint_rec (Abc_Obj_t *pObj)
unsigned Abc_Ntk4VarObj (Vec_Ptr_t *vNodes)
void Abc_Ntk4VarTable (Abc_Ntk_t *pNtk)
int Abc_NtkPrintOneDecompCheckCofList (unsigned *uCofs, int nCofs)
int Abc_NtkPrintOneDecompCheck (unsigned *uCofs, int nCofs, unsigned uMask)
void Abc_NtkPrintOneDecomp_rec (unsigned *uCofs, int nCofs, int nVars, unsigned uMask, int *pBestSize, unsigned *puBestMask)
void Abc_NtkPrintOneDecomp (unsigned *pTruth, int nVars)
void Abc_NtkPrintOneDec (unsigned *pTruth, int nVars)

Function Documentation

unsigned Abc_Ntk4VarObj ( Vec_Ptr_t *  vNodes  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 141 of file abcMeasure.c.

00142 {
00143     Abc_Obj_t * pObj;
00144     unsigned uTruth0, uTruth1;
00145     int i;
00146     Vec_PtrForEachEntry( vNodes, pObj, i )
00147     {
00148         uTruth0 = (unsigned)(Abc_ObjFanin0(pObj)->pCopy);
00149         uTruth1 = (unsigned)(Abc_ObjFanin1(pObj)->pCopy);
00150         if ( Abc_ObjFaninC0(pObj) )
00151             uTruth0 = ~uTruth0;
00152         if ( Abc_ObjFaninC1(pObj) )
00153             uTruth1 = ~uTruth1;
00154         pObj->pCopy = (void *)(uTruth0 & uTruth1);
00155     }
00156     return uTruth0 & uTruth1;
00157 }

void Abc_Ntk4VarObjPrint_rec ( Abc_Obj_t *  pObj  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file abcMeasure.c.

00108 {
00109     if ( pObj == Abc_AigConst1(pObj->pNtk) )
00110     {
00111         printf( "1" );
00112         return;
00113     }
00114     if ( Abc_ObjIsPi(pObj) )
00115     {
00116         printf( "%c", pObj->Id - 1 + 'a' );
00117         return;
00118     }
00119 
00120     printf( "(" );
00121     Abc_Ntk4VarObjPrint_rec( Abc_ObjFanin0(pObj) );
00122     if ( Abc_ObjFaninC0(pObj) )
00123         printf( "\'" );
00124     Abc_Ntk4VarObjPrint_rec( Abc_ObjFanin1(pObj) );
00125     if ( Abc_ObjFaninC1(pObj) )
00126         printf( "\'" );
00127     printf( ")" );
00128 }

void Abc_Ntk4VarTable ( Abc_Ntk_t *  pNtk  ) 

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 170 of file abcMeasure.c.

00171 {
00172     static unsigned u4VarTruths[4] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00 };
00173     static unsigned u4VarTts[222] = {
00174         0x0000, 0x0001, 0x0003, 0x0006, 0x0007, 0x000f, 0x0016, 0x0017, 0x0018, 0x0019, 
00175         0x001b, 0x001e, 0x001f, 0x003c, 0x003d, 0x003f, 0x0069, 0x006b, 0x006f, 0x007e, 
00176         0x007f, 0x00ff, 0x0116, 0x0117, 0x0118, 0x0119, 0x011a, 0x011b, 0x011e, 0x011f, 
00177         0x012c, 0x012d, 0x012f, 0x013c, 0x013d, 0x013e, 0x013f, 0x0168, 0x0169, 0x016a, 
00178         0x016b, 0x016e, 0x016f, 0x017e, 0x017f, 0x0180, 0x0181, 0x0182, 0x0183, 0x0186, 
00179         0x0187, 0x0189, 0x018b, 0x018f, 0x0196, 0x0197, 0x0198, 0x0199, 0x019a, 0x019b, 
00180         0x019e, 0x019f, 0x01a8, 0x01a9, 0x01aa, 0x01ab, 0x01ac, 0x01ad, 0x01ae, 0x01af, 
00181         0x01bc, 0x01bd, 0x01be, 0x01bf, 0x01e8, 0x01e9, 0x01ea, 0x01eb, 0x01ee, 0x01ef, 
00182         0x01fe, 0x033c, 0x033d, 0x033f, 0x0356, 0x0357, 0x0358, 0x0359, 0x035a, 0x035b, 
00183         0x035e, 0x035f, 0x0368, 0x0369, 0x036a, 0x036b, 0x036c, 0x036d, 0x036e, 0x036f, 
00184         0x037c, 0x037d, 0x037e, 0x03c0, 0x03c1, 0x03c3, 0x03c5, 0x03c6, 0x03c7, 0x03cf, 
00185         0x03d4, 0x03d5, 0x03d6, 0x03d7, 0x03d8, 0x03d9, 0x03db, 0x03dc, 0x03dd, 0x03de, 
00186         0x03fc, 0x0660, 0x0661, 0x0662, 0x0663, 0x0666, 0x0667, 0x0669, 0x066b, 0x066f, 
00187         0x0672, 0x0673, 0x0676, 0x0678, 0x0679, 0x067a, 0x067b, 0x067e, 0x0690, 0x0691, 
00188         0x0693, 0x0696, 0x0697, 0x069f, 0x06b0, 0x06b1, 0x06b2, 0x06b3, 0x06b4, 0x06b5, 
00189         0x06b6, 0x06b7, 0x06b9, 0x06bd, 0x06f0, 0x06f1, 0x06f2, 0x06f6, 0x06f9, 0x0776, 
00190         0x0778, 0x0779, 0x077a, 0x077e, 0x07b0, 0x07b1, 0x07b4, 0x07b5, 0x07b6, 0x07bc, 
00191         0x07e0, 0x07e1, 0x07e2, 0x07e3, 0x07e6, 0x07e9, 0x07f0, 0x07f1, 0x07f2, 0x07f8, 
00192         0x0ff0, 0x1668, 0x1669, 0x166a, 0x166b, 0x166e, 0x167e, 0x1681, 0x1683, 0x1686, 
00193         0x1687, 0x1689, 0x168b, 0x168e, 0x1696, 0x1697, 0x1698, 0x1699, 0x169a, 0x169b, 
00194         0x169e, 0x16a9, 0x16ac, 0x16ad, 0x16bc, 0x16e9, 0x177e, 0x178e, 0x1796, 0x1798, 
00195         0x179a, 0x17ac, 0x17e8, 0x18e7, 0x19e1, 0x19e3, 0x19e6, 0x1bd8, 0x1be4, 0x1ee1, 
00196         0x3cc3, 0x6996
00197     };
00198     int Counters[222] = {0};
00199     Vec_Ptr_t * vNodes;
00200     Abc_Obj_t * pObj;
00201     unsigned uTruth;
00202     int i, k, Count = 0;
00203 
00204     unsigned short * puCanons = NULL;
00205     unsigned char * puMap = NULL;
00206     Extra_Truth4VarNPN( &puCanons, NULL, NULL, &puMap );
00207 
00208     // set elementary truth tables
00209     assert( Abc_NtkPiNum(pNtk) == 4 );
00210     Abc_AigConst1(pNtk)->pCopy = (void *)0xFFFFFFFF;
00211     Abc_NtkForEachPi( pNtk, pObj, i )
00212         pObj->pCopy = (void *)u4VarTruths[i];
00213 
00214     // create truth tables
00215     Abc_NtkForEachPo( pNtk, pObj, i )
00216     {
00217         vNodes = Abc_NtkDfsNodes( pNtk, &pObj, 1 );
00218         if ( Vec_PtrSize(vNodes) == 0 )
00219             uTruth = (unsigned)Abc_ObjFanin0(pObj)->pCopy;
00220         else
00221             uTruth = Abc_Ntk4VarObj( vNodes );
00222 
00223         if ( (uTruth & 0xFFFF) < (~uTruth & 0xFFFF) )
00224             uTruth = uTruth & 0xFFFF;
00225         else
00226             uTruth = ~uTruth & 0xFFFF;
00227 
00228         for ( k = 0; k < 222; k++ )
00229             if ( u4VarTts[k] == uTruth )
00230                 break;
00231         if ( k == 222 )
00232             continue;
00233 /*
00234 //        if ( uTruth == 1725 )
00235         if ( k == 96 )
00236         {
00237             printf( "%d : ", Vec_PtrSize(vNodes) );
00238             Abc_Ntk4VarObjPrint_rec( Abc_ObjFanin0(pObj) );
00239             printf( "\n" );
00240         }
00241 */
00242         Counters[k]++;
00243 
00244 //        Counters[ puMap[uTruth & 0xFFFF] ]++;
00245         Vec_PtrFree( vNodes );
00246     }
00247     free( puCanons );
00248     free( puMap );
00249 
00250     Count = 0;
00251     for ( k = 0; k < 222; k++ )
00252     {
00253         printf( "%d/%x/%d ", k, u4VarTts[k], Counters[k] );
00254         Count += Counters[k];
00255     }
00256     printf( " Total = %d\n", Count );
00257 }

void Abc_NtkPrintMeasures ( unsigned *  pTruth,
int  nVars 
)

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

FileName [abc_.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

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

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 43 of file abcMeasure.c.

00044 {
00045     unsigned uCofs[10][32];
00046     int i, k, nOnes;
00047 
00048     // total pairs
00049     nOnes =  Kit_TruthCountOnes( uCofs[0], nVars );
00050     printf( "Total = %d.\n", nOnes * ((1 << nVars) - nOnes) );
00051 
00052     // print measures for individual variables
00053     for ( i = 0; i < nVars; i++ )
00054     {
00055         Kit_TruthUniqueNew( uCofs[0], pTruth, nVars, i );
00056         nOnes = Kit_TruthCountOnes( uCofs[0], nVars );
00057         printf( "%7d ", nOnes );
00058     }
00059     printf( "\n" );
00060 
00061     // consider pairs
00062     for ( i = 0; i < nVars; i++ )
00063     for ( k = 0; k < nVars; k++ )
00064     {
00065         if ( i == k )
00066         {
00067             printf( "        " );
00068             continue;
00069         }
00070         Kit_TruthCofactor0New( uCofs[0], pTruth, nVars, i );
00071         Kit_TruthCofactor1New( uCofs[1], pTruth, nVars, i );
00072 
00073         Kit_TruthCofactor0New( uCofs[2], uCofs[0], nVars, k ); // 00
00074         Kit_TruthCofactor1New( uCofs[3], uCofs[0], nVars, k ); // 01
00075         Kit_TruthCofactor0New( uCofs[4], uCofs[1], nVars, k ); // 10
00076         Kit_TruthCofactor1New( uCofs[5], uCofs[1], nVars, k ); // 11
00077 
00078         Kit_TruthAndPhase( uCofs[6], uCofs[2], uCofs[5], nVars, 0, 1 ); // 00  & 11'
00079         Kit_TruthAndPhase( uCofs[7], uCofs[2], uCofs[5], nVars, 1, 0 ); // 00' & 11
00080         Kit_TruthAndPhase( uCofs[8], uCofs[3], uCofs[4], nVars, 0, 1 ); // 01  & 10'
00081         Kit_TruthAndPhase( uCofs[9], uCofs[3], uCofs[4], nVars, 1, 0 ); // 01' & 10
00082 
00083         nOnes = Kit_TruthCountOnes( uCofs[6], nVars ) + 
00084                 Kit_TruthCountOnes( uCofs[7], nVars ) + 
00085                 Kit_TruthCountOnes( uCofs[8], nVars ) + 
00086                 Kit_TruthCountOnes( uCofs[9], nVars );
00087 
00088         printf( "%7d ", nOnes );
00089         if ( k == nVars - 1 )
00090             printf( "\n" );
00091     }
00092     printf( "\n" );
00093 }

void Abc_NtkPrintOneDec ( unsigned *  pTruth,
int  nVars 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 427 of file abcMeasure.c.

00428 {
00429     unsigned uCof[(1<<11)], * pOut = uCof, * pIn = pTruth, * pTemp;
00430     int nDiffs[16];
00431     int Order[16];
00432     int i, fChange, Temp, Counter;
00433 
00434     // find the ordering
00435     for ( i = 0; i < nVars; i++ )
00436     {
00437         Kit_TruthUniqueNew( uCof, pTruth, nVars, i );
00438         nDiffs[i] = Kit_TruthCountOnes( uCof, nVars );
00439         Order[i] = i;
00440     }
00441 
00442     // permute truth table to least active variable first
00443     Counter = 0;
00444     do {
00445         fChange = 0;
00446         for ( i = 0; i < nVars-1; i++ )
00447         {
00448             if ( nDiffs[i] <= nDiffs[i+1] )
00449                 continue;
00450             fChange = 1;
00451             Counter++;
00452 
00453             Temp = nDiffs[i];
00454             nDiffs[i] = nDiffs[i+1];
00455             nDiffs[i+1] = Temp;
00456 
00457             Temp = Order[i];
00458             Order[i] = Order[i+1];
00459             Order[i+1] = Temp;
00460 
00461             Extra_TruthSwapAdjacentVars( pOut, pIn, nVars, i );
00462             pTemp = pIn; pIn = pOut; pOut = pTemp;
00463         }
00464     } while ( fChange );
00465 
00466     // swap if it was moved an even number of times
00467     if ( Counter & 1 )
00468         Extra_TruthCopy( pOut, pIn, nVars );
00469 
00470     // call the decomposition
00471     Abc_NtkPrintOneDecomp( pTruth, nVars );
00472 }

void Abc_NtkPrintOneDecomp ( unsigned *  pTruth,
int  nVars 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 385 of file abcMeasure.c.

00386 {
00387     int BoundSet = 6;
00388     unsigned uCofs[64], uMask, uBestMask = 0;
00389     int i, nCofs, nMints, nMintShift, BestSize = 1;
00390 
00391     assert( nVars >  BoundSet );
00392     assert( nVars <= BoundSet + 5 ); // at most 5 variable cofactors
00393 
00394     // collect the cofactors
00395     nCofs = (1 << BoundSet);
00396     nMints = (1 << (nVars-BoundSet));
00397     nMintShift = 0;
00398     uMask = Kit_CubeMask( nMints );
00399     for ( i = 0; i < nCofs; i++ )
00400     {
00401         uCofs[i] = (pTruth[nMintShift/32] >> (nMintShift % 32)) & uMask;
00402         nMintShift += nMints;
00403     }
00404 
00405     // try removing variables
00406     for ( i = 0; i < BoundSet; i++ )
00407         Abc_NtkPrintOneDecomp_rec( uCofs, nCofs, nVars, (1 << i), &BestSize, &uBestMask );
00408 
00409     printf( "Best size = %d  ", BestSize );
00410     printf( "Best mask = " );
00411     Extra_PrintBinary( stdout, &uBestMask, nVars );
00412     printf( "\n" );
00413 }

void Abc_NtkPrintOneDecomp_rec ( unsigned *  uCofs,
int  nCofs,
int  nVars,
unsigned  uMask,
int *  pBestSize,
unsigned *  puBestMask 
)

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 345 of file abcMeasure.c.

00346 {
00347     unsigned uMaskNew;
00348     int v, last, Counter = 0;
00349     // find the last variable in the mask
00350     for ( v = 0; v < nVars; v++ )
00351         if ( uMask & (1<<v) )
00352         {
00353             last = v;
00354             Counter++;
00355         }
00356     if ( Counter > 3 )
00357         return;
00358     // try adding one variable after the last
00359     for ( v = last + 1; v < nVars; v++ )
00360     {
00361         uMaskNew = uMask | (1 << v);
00362         if ( !Abc_NtkPrintOneDecompCheck( uCofs, nCofs, uMaskNew ) )
00363             continue;
00364         if ( *pBestSize < Counter + 1 )
00365         {
00366             *pBestSize = Counter + 1;
00367             *puBestMask = uMaskNew;
00368         }
00369         // try other masks
00370         Abc_NtkPrintOneDecomp_rec( uCofs, nCofs, nVars, uMaskNew, pBestSize, puBestMask );
00371     }
00372 }

int Abc_NtkPrintOneDecompCheck ( unsigned *  uCofs,
int  nCofs,
unsigned  uMask 
)

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

Synopsis [Checks all cofactors with the given mask.]

Description []

SideEffects []

SeeAlso []

Definition at line 304 of file abcMeasure.c.

00305 {
00306     unsigned pCofs[32][32];
00307     int nCofNums[32] = {0};
00308     int uMasks[32];
00309     int nGroups = 0;
00310     int i, k;
00311     for ( i = 0; i < nCofs; i++ )
00312     {
00313         // find group of this cof
00314         for ( k = 0; k < nGroups; k++ )
00315             if ( (int)(i & uMask) == uMasks[k] )
00316                 break;
00317         if ( k == nGroups )
00318         {
00319             uMasks[k] = (i & uMask);
00320             nGroups++;
00321         }
00322         // save cof in the group
00323         pCofs[k][ nCofNums[k]++ ] = uCofs[i];
00324         assert( nCofNums[k] <= 32 );
00325         assert( nGroups <= 32 );
00326     }
00327     // check the groups
00328     for ( i = 0; i < nGroups; i++ )
00329         if ( !Abc_NtkPrintOneDecompCheckCofList(pCofs[i], nCofNums[i]) )
00330             return 0;
00331     return 1;
00332 }

int Abc_NtkPrintOneDecompCheckCofList ( unsigned *  uCofs,
int  nCofs 
)

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

Synopsis [Returns 1 if there are no more than 2 unique cofactors.]

Description []

SideEffects []

SeeAlso []

Definition at line 273 of file abcMeasure.c.

00274 {
00275     int i, Ind = -1;
00276     assert( nCofs > 2 );
00277     for ( i = 1; i < nCofs; i++ )
00278     {
00279         if ( uCofs[i] == uCofs[0] )
00280             continue;
00281         if ( Ind == -1 )
00282         {
00283             Ind = i;
00284             continue;
00285         }
00286         if ( uCofs[i] == uCofs[Ind] )
00287             continue;
00288         return 0;
00289     }
00290     return 1;
00291 }

Generated on Tue Jan 5 12:18:38 2010 for abc70930 by  doxygen 1.6.1