From d51f798956a9f9fbdd1fc4eeecc483e511b1c3d3 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 3 May 2020 10:32:30 -0700 Subject: Experimental resubstitution. --- src/misc/util/utilTruth.h | 146 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 146 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index e0ee1720..425ec27d 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -365,6 +365,141 @@ static inline int Abc_TtIntersect( word * pIn1, word * pIn2, int nWords, int fCo } return 0; } +static inline int Abc_TtIntersectOne( word * pOut, int fComp, word * pIn, int fComp0, int nWords ) +{ + int w; + if ( fComp0 ) + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn[w] & pOut[w] ) + return 1; + } + } + else + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( pIn[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( pIn[w] & pOut[w] ) + return 1; + } + } + return 0; +} +static inline int Abc_TtIntersectTwo( word * pOut, int fComp, word * pIn0, int fComp0, word * pIn1, int fComp1, int nWords ) +{ + int w; + if ( fComp0 && fComp1 ) + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn0[w] & ~pIn1[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn0[w] & ~pIn1[w] & pOut[w] ) + return 1; + } + } + else if ( fComp0 ) + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn0[w] & pIn1[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn0[w] & pIn1[w] & pOut[w] ) + return 1; + } + } + else if ( fComp1 ) + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( pIn0[w] & ~pIn1[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( pIn0[w] & ~pIn1[w] & pOut[w] ) + return 1; + } + } + else + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( pIn0[w] & pIn1[w] & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( pIn0[w] & pIn1[w] & pOut[w] ) + return 1; + } + } + return 0; +} +static inline int Abc_TtIntersectXor( word * pOut, int fComp, word * pIn0, word * pIn1, int fComp01, int nWords ) +{ + int w; + if ( fComp01 ) + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( ~(pIn0[w] ^ pIn1[w]) & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( ~(pIn0[w] ^ pIn1[w]) & pOut[w] ) + return 1; + } + } + else + { + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( (pIn0[w] ^ pIn1[w]) & ~pOut[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( (pIn0[w] ^ pIn1[w]) & pOut[w] ) + return 1; + } + } + return 0; +} static inline int Abc_TtEqual( word * pIn1, word * pIn2, int nWords ) { int w; @@ -1869,6 +2004,17 @@ static inline int Abc_TtCountOnesVecXor( word * x, word * y, int nWords ) Count += Abc_TtCountOnes( x[w] ^ y[w] ); return Count; } +static inline int Abc_TtCountOnesVecXorMask( word * x, word * y, int fCompl, word * pMask, int nWords ) +{ + int w, Count = 0; + if ( fCompl ) + for ( w = 0; w < nWords; w++ ) + Count += Abc_TtCountOnes( pMask[w] & (x[w] ^ ~y[w]) ); + else + for ( w = 0; w < nWords; w++ ) + Count += Abc_TtCountOnes( pMask[w] & (x[w] ^ y[w]) ); + return Count; +} static inline int Abc_TtAndXorSum( word * pOut, word * pIn1, word * pIn2, int nWords ) { int w, Count = 0; -- cgit v1.2.3 From d0efef2fe958ca093b06ad4be739ffdcb44c4d28 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Wed, 30 Dec 2020 11:24:35 -0800 Subject: Experiments with simulation. --- src/misc/util/utilTruth.h | 12 ++++++++++++ 1 file changed, 12 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 425ec27d..6cef332b 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -216,6 +216,12 @@ static inline void Abc_TtMask( word * pTruth, int nWords, int nBits ) SeeAlso [] ***********************************************************************/ +static inline void Abc_TtVec( word * pOut, int nWords, word Entry ) +{ + int w; + for ( w = 0; w < nWords; w++ ) + pOut[w] = Entry; +} static inline void Abc_TtConst( word * pOut, int nWords, int fConst1 ) { int w; @@ -316,6 +322,12 @@ static inline void Abc_TtOrXor( word * pOut, word * pIn1, word * pIn2, int nWord for ( w = 0; w < nWords; w++ ) pOut[w] |= pIn1[w] ^ pIn2[w]; } +static inline void Abc_TtOrAnd( word * pOut, word * pIn1, word * pIn2, int nWords ) +{ + int w; + for ( w = 0; w < nWords; w++ ) + pOut[w] |= pIn1[w] & pIn2[w]; +} static inline void Abc_TtXor( word * pOut, word * pIn1, word * pIn2, int nWords, int fCompl ) { int w; -- cgit v1.2.3 From b4f099c511f66dfe6624ac26194abb90e9615cfd Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 19 Jun 2021 19:26:41 -0700 Subject: Experiments with LUT mapping for small functions. --- src/misc/util/utilTruth.h | 49 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 6cef332b..112ec8b4 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -35,6 +35,22 @@ ABC_NAMESPACE_HEADER_START /// BASIC TYPES /// //////////////////////////////////////////////////////////////////////// +static unsigned s_Truths5[6] = { + 0xAAAAAAAA, + 0xCCCCCCCC, + 0xF0F0F0F0, + 0xFF00FF00, + 0xFFFF0000 +}; + +static unsigned s_Truths5Neg[6] = { + 0x55555555, + 0x33333333, + 0x0F0F0F0F, + 0x00FF00FF, + 0x0000FFFF +}; + static word s_Truths6[6] = { ABC_CONST(0xAAAAAAAAAAAAAAAA), ABC_CONST(0xCCCCCCCCCCCCCCCC), @@ -262,6 +278,12 @@ static inline void Abc_TtCopy( word * pOut, word * pIn, int nWords, int fCompl ) for ( w = 0; w < nWords; w++ ) pOut[w] = pIn[w]; } +static inline word * Abc_TtDup( word * pIn, int nWords, int fCompl ) +{ + word * pOut = ABC_ALLOC( word, nWords ); + Abc_TtCopy( pOut, pIn, nWords, fCompl ); + return pOut; +} static inline void Abc_TtAnd( word * pOut, word * pIn1, word * pIn2, int nWords, int fCompl ) { int w; @@ -819,6 +841,33 @@ static inline void Abc_TtElemInit2( word * pTtElems, int nVars ) } } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Abc_Tt5HasVar( unsigned t, int iVar ) +{ + return ((t << (1<= 0 && iVar < 5 ); + return (t &s_Truths5Neg[iVar]) | ((t &s_Truths5Neg[iVar]) << (1<= 0 && iVar < 5 ); + return (t & s_Truths5[iVar]) | ((t & s_Truths5[iVar]) >> (1< Date: Sun, 1 Aug 2021 12:13:27 -0700 Subject: Experiments with LUT mapping for small functions. --- src/misc/util/utilTruth.h | 67 +++++++++++++++++++++++++++++------------------ 1 file changed, 42 insertions(+), 25 deletions(-) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 112ec8b4..01a2a369 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -1663,31 +1663,6 @@ static inline void Abc_TtFlip( word * pTruth, int nWords, int iVar ) } } -/**Function************************************************************* - - Synopsis [] - - Description [] - - SideEffects [] - - SeeAlso [] - -***********************************************************************/ -static inline word Abc_Tt6Permute_rec( word t, int * pPerm, int nVars ) -{ - word uRes0, uRes1; int Var; - if ( t == 0 ) return 0; - if ( ~t == 0 ) return ~(word)0; - for ( Var = nVars-1; Var >= 0; Var-- ) - if ( Abc_Tt6HasVar( t, Var ) ) - break; - assert( Var >= 0 ); - uRes0 = Abc_Tt6Permute_rec( Abc_Tt6Cofactor0(t, Var), pPerm, Var ); - uRes1 = Abc_Tt6Permute_rec( Abc_Tt6Cofactor1(t, Var), pPerm, Var ); - return (uRes0 & s_Truths6Neg[pPerm[Var]]) | (uRes1 & s_Truths6[pPerm[Var]]); -} - /**Function************************************************************* Synopsis [] @@ -1803,6 +1778,48 @@ static inline word Abc_Tt6RemoveVar( word t, int iVar ) return t; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Abc_Tt6Permute_rec( word t, int * pPerm, int nVars ) +{ + word uRes0, uRes1; int Var; + if ( t == 0 ) return 0; + if ( ~t == 0 ) return ~(word)0; + for ( Var = nVars-1; Var >= 0; Var-- ) + if ( Abc_Tt6HasVar( t, Var ) ) + break; + assert( Var >= 0 ); + uRes0 = Abc_Tt6Permute_rec( Abc_Tt6Cofactor0(t, Var), pPerm, Var ); + uRes1 = Abc_Tt6Permute_rec( Abc_Tt6Cofactor1(t, Var), pPerm, Var ); + return (uRes0 & s_Truths6Neg[pPerm[Var]]) | (uRes1 & s_Truths6[pPerm[Var]]); +} +static inline void Abc_TtPermute( word * p, int * pPerm, int nVars ) +{ + int v, nWords = Abc_TtWordNum(nVars), Perm[16]; + assert( nVars <= 16 ); + for ( v = 0; v < nVars; v++ ) + Perm[v] = pPerm[v]; + for ( v = nVars-1; v >= 0; v-- ) + { + while ( v != Perm[v] ) + { + int vCur = Perm[v]; + Abc_TtSwapVars( p, nVars, v, vCur ); + Perm[v] = Perm[vCur]; + Perm[vCur]= vCur; + } + } +} + /**Function************************************************************* Synopsis [Support minimization.] -- cgit v1.2.3 From 03bb1e49bfcc148faaa4981bb3d758514adfeb4d Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 1 Aug 2021 12:14:38 -0700 Subject: Experiments with LUT mapping for small functions. --- src/misc/util/utilTruth.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 01a2a369..4c4b1422 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -1804,7 +1804,7 @@ static inline word Abc_Tt6Permute_rec( word t, int * pPerm, int nVars ) } static inline void Abc_TtPermute( word * p, int * pPerm, int nVars ) { - int v, nWords = Abc_TtWordNum(nVars), Perm[16]; + int v, Perm[16]; assert( nVars <= 16 ); for ( v = 0; v < nVars; v++ ) Perm[v] = pPerm[v]; -- cgit v1.2.3 From 5f8d4e72d1d99539d100ca5c190c56c5901976e6 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 2 Aug 2021 16:46:56 -0700 Subject: Experiments with LUT mapping for small functions. --- src/misc/util/utilTruth.h | 56 ++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 55 insertions(+), 1 deletion(-) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 4c4b1422..7f3a7dd1 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -399,7 +399,23 @@ static inline int Abc_TtIntersect( word * pIn1, word * pIn2, int nWords, int fCo } return 0; } -static inline int Abc_TtIntersectOne( word * pOut, int fComp, word * pIn, int fComp0, int nWords ) +static inline int Abc_TtIntersectCare( word * pIn1, word * pIn2, word * pCare, int nWords, int fCompl ) +{ + int w; + if ( fCompl ) + { + for ( w = 0; w < nWords; w++ ) + if ( ~pIn1[w] & pIn2[w] & pCare[w] ) + return 1; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( pIn1[w] & pIn2[w] & pCare[w] ) + return 1; + } + return 0; +}static inline int Abc_TtIntersectOne( word * pOut, int fComp, word * pIn, int fComp0, int nWords ) { int w; if ( fComp0 ) @@ -542,6 +558,23 @@ static inline int Abc_TtEqual( word * pIn1, word * pIn2, int nWords ) return 0; return 1; } +static inline int Abc_TtEqualCare( word * pIn1, word * pIn2, word * pCare, int fComp, int nWords ) +{ + int w; + if ( fComp ) + { + for ( w = 0; w < nWords; w++ ) + if ( (~pIn1[w] ^ pIn2[w]) & pCare[w] ) + return 0; + } + else + { + for ( w = 0; w < nWords; w++ ) + if ( (pIn1[w] ^ pIn2[w]) & pCare[w] ) + return 0; + } + return 1; +} static inline int Abc_TtOpposite( word * pIn1, word * pIn2, int nWords ) { int w; @@ -1803,6 +1836,25 @@ static inline word Abc_Tt6Permute_rec( word t, int * pPerm, int nVars ) return (uRes0 & s_Truths6Neg[pPerm[Var]]) | (uRes1 & s_Truths6[pPerm[Var]]); } static inline void Abc_TtPermute( word * p, int * pPerm, int nVars ) +{ + int v, UnPerm[16], Perm[16]; + assert( nVars <= 16 ); + for ( v = 0; v < nVars; v++ ) + UnPerm[v] = Perm[v] = v; + for ( v = nVars-1; v >= 0; v-- ) + { + int Lev = UnPerm[pPerm[v]]; + if ( v == Lev ) + continue; + Abc_TtSwapVars( p, nVars, v, Lev ); + ABC_SWAP( int, Perm[v], Perm[Lev] ); + UnPerm[Perm[Lev]] = Lev; + UnPerm[Perm[v]] = v; + } + for ( v = 0; v < nVars; v++ ) + assert( Perm[v] == pPerm[v] ); +} +static inline void Abc_TtUnpermute( word * p, int * pPerm, int nVars ) { int v, Perm[16]; assert( nVars <= 16 ); @@ -1818,6 +1870,8 @@ static inline void Abc_TtPermute( word * p, int * pPerm, int nVars ) Perm[vCur]= vCur; } } + for ( v = 0; v < nVars; v++ ) + assert( Perm[v] == v ); } /**Function************************************************************* -- cgit v1.2.3 From a718318740a3a50f6058b3d64330dbe8ca1e6303 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 2 Sep 2021 22:54:19 -0700 Subject: Various changes. --- src/misc/util/abc_global.h | 2 ++ src/misc/util/utilTruth.h | 6 ++++++ 2 files changed, 8 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index d7c5bea7..34bd5057 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -288,6 +288,8 @@ static inline int Abc_Base2Log( unsigned n ) { int r; if ( n < static inline int Abc_Base10Log( unsigned n ) { int r; if ( n < 2 ) return (int)n; for ( r = 0, n--; n; n /= 10, r++ ) {}; return r; } static inline int Abc_Base16Log( unsigned n ) { int r; if ( n < 2 ) return (int)n; for ( r = 0, n--; n; n /= 16, r++ ) {}; return r; } static inline char * Abc_UtilStrsav( char * s ) { return s ? strcpy(ABC_ALLOC(char, strlen(s)+1), s) : NULL; } +static inline char * Abc_UtilStrsavTwo( char * s, char * a ){ char * r; if (!a) return Abc_UtilStrsav(s); r = ABC_ALLOC(char, strlen(s)+strlen(a)+1); sprintf(r, "%s%s", s, a ); return r; } +static inline char * Abc_UtilStrsavNum( char * s, int n ) { char * r; if (!s) return NULL; r = ABC_ALLOC(char, strlen(s)+12+1); sprintf(r, "%s%d", s, n ); return r; } static inline int Abc_BitByteNum( int nBits ) { return (nBits>>3) + ((nBits&7) > 0); } static inline int Abc_BitWordNum( int nBits ) { return (nBits>>5) + ((nBits&31) > 0); } static inline int Abc_Bit6WordNum( int nBits ) { return (nBits>>6) + ((nBits&63) > 0); } diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 7f3a7dd1..6a98c40f 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -344,6 +344,12 @@ static inline void Abc_TtOrXor( word * pOut, word * pIn1, word * pIn2, int nWord for ( w = 0; w < nWords; w++ ) pOut[w] |= pIn1[w] ^ pIn2[w]; } +static inline void Abc_TtAndXor( word * pOut, word * pIn1, word * pIn2, int nWords ) +{ + int w; + for ( w = 0; w < nWords; w++ ) + pOut[w] &= pIn1[w] ^ pIn2[w]; +} static inline void Abc_TtOrAnd( word * pOut, word * pIn1, word * pIn2, int nWords ) { int w; -- cgit v1.2.3 From 6ca31c475f7ae1605be34a0629559db2beef49d1 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 16 Sep 2021 21:51:10 -0700 Subject: Improving MiniAIG and name manager. --- src/misc/util/utilNam.c | 39 +++++++++++++++++++++++++++++++++++++++ src/misc/util/utilNam.h | 2 ++ 2 files changed, 41 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/utilNam.c b/src/misc/util/utilNam.c index 30a68c63..b1d2702c 100644 --- a/src/misc/util/utilNam.c +++ b/src/misc/util/utilNam.c @@ -142,6 +142,45 @@ void Abc_NamPrint( Abc_Nam_t * p, char * pFileName ) fclose(pFile); } +/**Function************************************************************* + + Synopsis [Writes into a file and reads from a file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_NamSave( Abc_Nam_t * p, char * pFileName ) +{ + FILE * pFile = fopen( pFileName, "wb" ); int h, i; + if ( pFile == NULL ) { printf( "Count node open input file %s\n", pFileName ); return; } + Vec_IntForEachEntryStart( &p->vInt2Handle, h, i, 1 ) + fprintf( pFile, "%s\n", Abc_NamHandleToStr(p, h) ); + fclose(pFile); +} +Abc_Nam_t * Abc_NamLoad( char * pFileName ) +{ + Abc_Nam_t * p; + int fFound, NameId, nLineSize = 1 << 20; + char * pBuffer = ABC_ALLOC( char, nLineSize+1 ); + FILE * pFile = fopen( pFileName, "rb" ); + if ( pFile == NULL ) { printf( "Count node open output file %s\n", pFileName ); return NULL; } + p = Abc_NamStart( 1000, 20 ); + while ( fgets( pBuffer, nLineSize, pFile ) != NULL ) + { + pBuffer[strlen(pBuffer)-1] = 0; + NameId = Abc_NamStrFindOrAdd( p, pBuffer, &fFound ); + assert( !fFound ); + } + assert( NameId+1 == Abc_NamObjNumMax(p) ); + fclose( pFile ); + ABC_FREE( pBuffer ); + return p; +} + /**Function************************************************************* Synopsis [References the manager.] diff --git a/src/misc/util/utilNam.h b/src/misc/util/utilNam.h index 8e054fc1..cf2d27e7 100644 --- a/src/misc/util/utilNam.h +++ b/src/misc/util/utilNam.h @@ -53,6 +53,8 @@ typedef struct Abc_Nam_t_ Abc_Nam_t; extern Abc_Nam_t * Abc_NamStart( int nObjs, int nAveSize ); extern void Abc_NamStop( Abc_Nam_t * p ); extern void Abc_NamPrint( Abc_Nam_t * p, char * pFileName ); +extern void Abc_NamSave( Abc_Nam_t * p, char * pFileName ); +extern Abc_Nam_t * Abc_NamLoad( char * pFileName ); extern Abc_Nam_t * Abc_NamRef( Abc_Nam_t * p ); extern void Abc_NamDeref( Abc_Nam_t * p ); extern int Abc_NamObjNumMax( Abc_Nam_t * p ); -- cgit v1.2.3 From e2f15482175a06a9aa9056a3a54b2bb05de2721a Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Tue, 21 Sep 2021 10:00:46 -0700 Subject: Various changes. --- src/misc/util/abc_global.h | 1 + src/misc/util/utilNam.c | 2 +- src/misc/util/utilSort.c | 101 +++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 103 insertions(+), 1 deletion(-) (limited to 'src/misc/util') diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index 34bd5057..f6076399 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -515,6 +515,7 @@ static inline void Abc_ReverseOrder( int * pA, int nA ) // sorting extern void Abc_MergeSort( int * pInput, int nSize ); extern int * Abc_MergeSortCost( int * pCosts, int nSize ); +extern void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ); extern void Abc_QuickSort1( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort2( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort3( word * pData, int nSize, int fDecrease ); diff --git a/src/misc/util/utilNam.c b/src/misc/util/utilNam.c index b1d2702c..f6539f03 100644 --- a/src/misc/util/utilNam.c +++ b/src/misc/util/utilNam.c @@ -164,7 +164,7 @@ void Abc_NamSave( Abc_Nam_t * p, char * pFileName ) Abc_Nam_t * Abc_NamLoad( char * pFileName ) { Abc_Nam_t * p; - int fFound, NameId, nLineSize = 1 << 20; + int fFound, NameId = -1, nLineSize = 1 << 20; char * pBuffer = ABC_ALLOC( char, nLineSize+1 ); FILE * pFile = fopen( pFileName, "rb" ); if ( pFile == NULL ) { printf( "Count node open output file %s\n", pFileName ); return NULL; } diff --git a/src/misc/util/utilSort.c b/src/misc/util/utilSort.c index 31890503..679017ed 100644 --- a/src/misc/util/utilSort.c +++ b/src/misc/util/utilSort.c @@ -137,6 +137,107 @@ void Abc_MergeSort( int * pInput, int nSize ) } +/**Function************************************************************* + + Synopsis [Merging two lists of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortMergeCost2( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost ) +{ + int nEntries = (p1End - p1Beg) + (p2End - p2Beg); + int * pOutBeg = pOut; + while ( p1Beg < p1End && p2Beg < p2End ) + { + if ( pCost[*p1Beg] == pCost[*p2Beg] ) + *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; + else if ( pCost[*p1Beg] < pCost[*p2Beg] ) + *pOut++ = *p1Beg++; + else // if ( pCost[*p1Beg] > pCost[*p2Beg] ) + *pOut++ = *p2Beg++; + } + while ( p1Beg < p1End ) + *pOut++ = *p1Beg++; + while ( p2Beg < p2End ) + *pOut++ = *p2Beg++; + assert( pOut - pOutBeg == nEntries ); +} + +/**Function************************************************************* + + Synopsis [Recursive sorting.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortCost2_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost ) +{ + int nSize = pInEnd - pInBeg; + assert( nSize > 0 ); + if ( nSize == 1 ) + return; + if ( nSize == 2 ) + { + if ( pCost[pInBeg[0]] > pCost[pInBeg[1]] ) + { + pInBeg[0] ^= pInBeg[1]; + pInBeg[1] ^= pInBeg[0]; + pInBeg[0] ^= pInBeg[1]; + } + } + else if ( nSize < 8 ) + { + int temp, i, j, best_i; + for ( i = 0; i < nSize-1; i++ ) + { + best_i = i; + for ( j = i+1; j < nSize; j++ ) + if ( pCost[pInBeg[j]] < pCost[pInBeg[best_i]] ) + best_i = j; + temp = pInBeg[i]; + pInBeg[i] = pInBeg[best_i]; + pInBeg[best_i] = temp; + } + } + else + { + Abc_SortCost2_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost ); + Abc_SortCost2_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost ); + Abc_SortMergeCost2( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost ); + memcpy( pInBeg, pOutBeg, sizeof(int) * nSize ); + } +} + +/**Function************************************************************* + + Synopsis [Returns the sorted array of integers.] + + Description [This procedure is about 10% faster than qsort().] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ) +{ + int * pOutput; + if ( nSize < 2 ) + return; + pOutput = (int *) malloc( sizeof(int) * nSize ); + Abc_SortCost2_rec( pInput, pInput + nSize, pOutput, pCost ); + free( pOutput ); +} + /**Function************************************************************* -- cgit v1.2.3 From 2ce1ce8bed69623de58d9394e22a3a8812096561 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 26 Sep 2021 11:12:17 -0700 Subject: Various changes. --- src/misc/util/abc_global.h | 1 + src/misc/util/utilSort.c | 103 +++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 104 insertions(+) (limited to 'src/misc/util') diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index f6076399..5ba614c7 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -516,6 +516,7 @@ static inline void Abc_ReverseOrder( int * pA, int nA ) extern void Abc_MergeSort( int * pInput, int nSize ); extern int * Abc_MergeSortCost( int * pCosts, int nSize ); extern void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ); +extern void Abc_MergeSortCost2Reverse( int * pInput, int nSize, int * pCost ); extern void Abc_QuickSort1( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort2( word * pData, int nSize, int fDecrease ); extern void Abc_QuickSort3( word * pData, int nSize, int fDecrease ); diff --git a/src/misc/util/utilSort.c b/src/misc/util/utilSort.c index 679017ed..a748caf9 100644 --- a/src/misc/util/utilSort.c +++ b/src/misc/util/utilSort.c @@ -239,6 +239,109 @@ void Abc_MergeSortCost2( int * pInput, int nSize, int * pCost ) } +/**Function************************************************************* + + Synopsis [Merging two lists of entries.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortMergeCost2Reverse( int * p1Beg, int * p1End, int * p2Beg, int * p2End, int * pOut, int * pCost ) +{ + int nEntries = (p1End - p1Beg) + (p2End - p2Beg); + int * pOutBeg = pOut; + while ( p1Beg < p1End && p2Beg < p2End ) + { + if ( pCost[*p1Beg] == pCost[*p2Beg] ) + *pOut++ = *p1Beg++, *pOut++ = *p2Beg++; + else if ( pCost[*p1Beg] > pCost[*p2Beg] ) + *pOut++ = *p1Beg++; + else // if ( pCost[*p1Beg] < pCost[*p2Beg] ) + *pOut++ = *p2Beg++; + } + while ( p1Beg < p1End ) + *pOut++ = *p1Beg++; + while ( p2Beg < p2End ) + *pOut++ = *p2Beg++; + assert( pOut - pOutBeg == nEntries ); +} + +/**Function************************************************************* + + Synopsis [Recursive sorting.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_SortCost2Reverse_rec( int * pInBeg, int * pInEnd, int * pOutBeg, int * pCost ) +{ + int nSize = pInEnd - pInBeg; + assert( nSize > 0 ); + if ( nSize == 1 ) + return; + if ( nSize == 2 ) + { + if ( pCost[pInBeg[0]] < pCost[pInBeg[1]] ) + { + pInBeg[0] ^= pInBeg[1]; + pInBeg[1] ^= pInBeg[0]; + pInBeg[0] ^= pInBeg[1]; + } + } + else if ( nSize < 8 ) + { + int temp, i, j, best_i; + for ( i = 0; i < nSize-1; i++ ) + { + best_i = i; + for ( j = i+1; j < nSize; j++ ) + if ( pCost[pInBeg[j]] > pCost[pInBeg[best_i]] ) + best_i = j; + temp = pInBeg[i]; + pInBeg[i] = pInBeg[best_i]; + pInBeg[best_i] = temp; + } + } + else + { + Abc_SortCost2Reverse_rec( pInBeg, pInBeg + nSize/2, pOutBeg, pCost ); + Abc_SortCost2Reverse_rec( pInBeg + nSize/2, pInEnd, pOutBeg + nSize/2, pCost ); + Abc_SortMergeCost2Reverse( pInBeg, pInBeg + nSize/2, pInBeg + nSize/2, pInEnd, pOutBeg, pCost ); + memcpy( pInBeg, pOutBeg, sizeof(int) * nSize ); + } +} + +/**Function************************************************************* + + Synopsis [Returns the sorted array of integers.] + + Description [This procedure is about 10% faster than qsort().] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_MergeSortCost2Reverse( int * pInput, int nSize, int * pCost ) +{ + int * pOutput; + if ( nSize < 2 ) + return; + pOutput = (int *) malloc( sizeof(int) * nSize ); + Abc_SortCost2Reverse_rec( pInput, pInput + nSize, pOutput, pCost ); + free( pOutput ); +} + + + /**Function************************************************************* Synopsis [Merging two lists of entries.] -- cgit v1.2.3 From a8b5da820df6c008fd02f514a8c93a48ecfe3620 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 26 Sep 2021 11:58:42 -0700 Subject: Other compiler changes. --- src/misc/util/abc_global.h | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'src/misc/util') diff --git a/src/misc/util/abc_global.h b/src/misc/util/abc_global.h index 5ba614c7..d1a9b4d3 100644 --- a/src/misc/util/abc_global.h +++ b/src/misc/util/abc_global.h @@ -329,7 +329,12 @@ static inline int Abc_Lit2Att4( int Lit ) { assert(Lit >= 0) typedef ABC_INT64_T abctime; static inline abctime Abc_Clock() { -#if (defined(LIN) || defined(LIN64)) && !(__APPLE__ & __MACH__) && !defined(__MINGW32__) +#if defined(__APPLE__) && defined(__MACH__) + #define APPLE_MACH (__APPLE__ & __MACH__) +#else + #define APPLE_MACH 0 +#endif +#if (defined(LIN) || defined(LIN64)) && !APPLE_MACH && !defined(__MINGW32__) struct timespec ts; if ( clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts) < 0 ) return (abctime)-1; -- cgit v1.2.3 From 674bcbee379b9dcef418ddb62655ee0d3d59f96c Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 30 Sep 2021 18:02:33 -0700 Subject: Various changes. --- src/misc/util/utilTruth.h | 48 +++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 44 insertions(+), 4 deletions(-) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index 6a98c40f..dbc0e5a0 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -356,6 +356,12 @@ static inline void Abc_TtOrAnd( word * pOut, word * pIn1, word * pIn2, int nWord for ( w = 0; w < nWords; w++ ) pOut[w] |= pIn1[w] & pIn2[w]; } +static inline void Abc_TtSharpOr( word * pOut, word * pIn1, word * pIn2, int nWords ) +{ + int w; + for ( w = 0; w < nWords; w++ ) + pOut[w] = (pOut[w] & ~pIn1[w]) | pIn2[w]; +} static inline void Abc_TtXor( word * pOut, word * pIn1, word * pIn2, int nWords, int fCompl ) { int w; @@ -2104,18 +2110,25 @@ static inline int Abc_TtCountOnesVec( word * x, int nWords ) { int w, Count = 0; for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( x[w] ); + if ( x[w] ) + Count += Abc_TtCountOnes( x[w] ); return Count; } static inline int Abc_TtCountOnesVecMask( word * x, word * pMask, int nWords, int fCompl ) { int w, Count = 0; if ( fCompl ) + { for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & ~x[w] ); + if ( pMask[w] & ~x[w] ) + Count += Abc_TtCountOnes( pMask[w] & ~x[w] ); + } else + { for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & x[w] ); + if ( pMask[w] & x[w] ) + Count += Abc_TtCountOnes( pMask[w] & x[w] ); + } return Count; } static inline int Abc_TtCountOnesVecMask2( word * x0, word * x1, int fComp0, int fComp1, word * pMask, int nWords ) @@ -2139,7 +2152,8 @@ static inline int Abc_TtCountOnesVecXor( word * x, word * y, int nWords ) { int w, Count = 0; for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( x[w] ^ y[w] ); + if ( x[w] ^ y[w] ) + Count += Abc_TtCountOnes( x[w] ^ y[w] ); return Count; } static inline int Abc_TtCountOnesVecXorMask( word * x, word * y, int fCompl, word * pMask, int nWords ) @@ -2163,6 +2177,16 @@ static inline int Abc_TtAndXorSum( word * pOut, word * pIn1, word * pIn2, int nW } return Count; } +static inline void Abc_TtIsfPrint( word * pOff, word * pOn, int nWords ) +{ + int nTotal = 64*nWords; + int nOffset = Abc_TtCountOnesVec(pOff, nWords); + int nOnset = Abc_TtCountOnesVec(pOn, nWords); + int nDcset = nTotal - nOffset - nOnset; + printf( "OFF =%6d (%6.2f %%) ", nOffset, 100.0*nOffset/nTotal ); + printf( "ON =%6d (%6.2f %%) ", nOnset, 100.0*nOnset/nTotal ); + printf( "DC =%6d (%6.2f %%)", nDcset, 100.0*nDcset/nTotal ); +} /**Function************************************************************* @@ -2263,6 +2287,22 @@ static inline int Abc_TtFindLastDiffBit2( word * pIn1, word * pIn2, int nWords ) return 64*w + Abc_Tt6LastBit(pIn1[w] ^ pIn2[w]); return -1; } +static inline int Abc_TtFindFirstAndBit2( word * pIn1, word * pIn2, int nWords ) +{ + int w; + for ( w = 0; w < nWords; w++ ) + if ( pIn1[w] & pIn2[w] ) + return 64*w + Abc_Tt6FirstBit(pIn1[w] & pIn2[w]); + return -1; +} +static inline int Abc_TtFindLastAndBit2( word * pIn1, word * pIn2, int nWords ) +{ + int w; + for ( w = nWords - 1; w >= 0; w-- ) + if ( pIn1[w] & pIn2[w] ) + return 64*w + Abc_Tt6LastBit(pIn1[w] & pIn2[w]); + return -1; +} static inline int Abc_TtFindFirstZero( word * pIn, int nVars ) { int w, nWords = Abc_TtWordNum(nVars); -- cgit v1.2.3 From d4f073bad759874161e2de5952ef7d466bc3eb07 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 22 Oct 2021 00:00:01 -0700 Subject: Various changes. --- src/misc/util/utilTruth.h | 30 +++++++++++++++--------------- 1 file changed, 15 insertions(+), 15 deletions(-) (limited to 'src/misc/util') diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h index dbc0e5a0..d9efa55f 100644 --- a/src/misc/util/utilTruth.h +++ b/src/misc/util/utilTruth.h @@ -2106,12 +2106,15 @@ static inline int Abc_TtCountOnes( word x ) x = x + (x >> 32); return (int)(x & 0xFF); } +static inline int Abc_TtCountOnes2( word x ) +{ + return x ? Abc_TtCountOnes(x) : 0; +} static inline int Abc_TtCountOnesVec( word * x, int nWords ) { int w, Count = 0; for ( w = 0; w < nWords; w++ ) - if ( x[w] ) - Count += Abc_TtCountOnes( x[w] ); + Count += Abc_TtCountOnes2( x[w] ); return Count; } static inline int Abc_TtCountOnesVecMask( word * x, word * pMask, int nWords, int fCompl ) @@ -2120,14 +2123,12 @@ static inline int Abc_TtCountOnesVecMask( word * x, word * pMask, int nWords, in if ( fCompl ) { for ( w = 0; w < nWords; w++ ) - if ( pMask[w] & ~x[w] ) - Count += Abc_TtCountOnes( pMask[w] & ~x[w] ); + Count += Abc_TtCountOnes2( pMask[w] & ~x[w] ); } else { for ( w = 0; w < nWords; w++ ) - if ( pMask[w] & x[w] ) - Count += Abc_TtCountOnes( pMask[w] & x[w] ); + Count += Abc_TtCountOnes2( pMask[w] & x[w] ); } return Count; } @@ -2136,24 +2137,23 @@ static inline int Abc_TtCountOnesVecMask2( word * x0, word * x1, int fComp0, int int w, Count = 0; if ( !fComp0 && !fComp1 ) for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & x0[w] & x1[w] ); + Count += Abc_TtCountOnes2( pMask[w] & x0[w] & x1[w] ); else if ( fComp0 && !fComp1 ) for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & ~x0[w] & x1[w] ); + Count += Abc_TtCountOnes2( pMask[w] & ~x0[w] & x1[w] ); else if ( !fComp0 && fComp1 ) for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & x0[w] & ~x1[w] ); + Count += Abc_TtCountOnes2( pMask[w] & x0[w] & ~x1[w] ); else for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & ~x0[w] & ~x1[w] ); + Count += Abc_TtCountOnes2( pMask[w] & ~x0[w] & ~x1[w] ); return Count; } static inline int Abc_TtCountOnesVecXor( word * x, word * y, int nWords ) { int w, Count = 0; for ( w = 0; w < nWords; w++ ) - if ( x[w] ^ y[w] ) - Count += Abc_TtCountOnes( x[w] ^ y[w] ); + Count += Abc_TtCountOnes2( x[w] ^ y[w] ); return Count; } static inline int Abc_TtCountOnesVecXorMask( word * x, word * y, int fCompl, word * pMask, int nWords ) @@ -2161,10 +2161,10 @@ static inline int Abc_TtCountOnesVecXorMask( word * x, word * y, int fCompl, wor int w, Count = 0; if ( fCompl ) for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & (x[w] ^ ~y[w]) ); + Count += Abc_TtCountOnes2( pMask[w] & (x[w] ^ ~y[w]) ); else for ( w = 0; w < nWords; w++ ) - Count += Abc_TtCountOnes( pMask[w] & (x[w] ^ y[w]) ); + Count += Abc_TtCountOnes2( pMask[w] & (x[w] ^ y[w]) ); return Count; } static inline int Abc_TtAndXorSum( word * pOut, word * pIn1, word * pIn2, int nWords ) @@ -2173,7 +2173,7 @@ static inline int Abc_TtAndXorSum( word * pOut, word * pIn1, word * pIn2, int nW for ( w = 0; w < nWords; w++ ) { pOut[w] &= pIn1[w] ^ pIn2[w]; - Count += Abc_TtCountOnes( pOut[w] ); + Count += Abc_TtCountOnes2( pOut[w] ); } return Count; } -- cgit v1.2.3