ifDec66.c File Reference

#include "if.h"
#include "bool/kit/kit.h"
#include "misc/vec/vecMem.h"

Include dependency graph for ifDec66.c:

Go to the source code of this file.

Classes
struct	If_Grp_t_
struct	If_Hte_t_

Macros
#define	CLU_VAR_MAX   11
#define	CLU_MEM_MAX   1000
#define	CLU_UNUSED   0xff

Functions
unsigned int	If_CluPrimeCudd2 (unsigned int p)
int	If_CluHashFindMedian2 (If_Man_t *p, int t)
int	If_CluHashKey2 (word *pTruth, int nWords, int Size)
unsigned *	If_CluHashLookup2 (If_Man_t *p, word *pTruth, int t)
int	If_CluCheckXX (If_Man_t *p, word *pTruth0, int lutSize, int nVars, int fHashing)
int	If_CluCheckXXExt (void *pMan, word *pTruth, int nVars, int nLutLeaf, int nLutRoot, char *pLut0, char *pLut1, word *pFunc0, word *pFunc1)
int	If_CutPerformCheckXX (If_Man_t *p, unsigned *pTruth0, int nVars, int nLeaves, char *pStr)

Macro Definition Documentation

CLU_MEM_MAX

#define CLU_MEM_MAX   1000

Definition at line 28 of file ifDec66.c.

CLU_UNUSED

#define CLU_UNUSED   0xff

Definition at line 29 of file ifDec66.c.

CLU_VAR_MAX

#define CLU_VAR_MAX   11

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

FileName [ifDec66.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [FPGA mapping based on priority cuts.]

Synopsis [Fast checking procedures.]

Author [Alessandro Tempia Calvino]

Affiliation [EPFL]

Date [Ver. 1.0. Started - Feb 8, 2024.]

Revision [

Id

ifDec66.c,v 1.00 2008/02/08 00:00:00 tempia Exp

]

Definition at line 27 of file ifDec66.c.

Function Documentation

If_CluCheckXX()

int If_CluCheckXX	(	If_Man_t *	p,
		word *	pTruth0,
		int	lutSize,
		int	nVars,
		int	fHashing )

Definition at line 276 of file ifDec66.c.

{
    If_Grp_t G1 = {0};
    unsigned * pHashed = NULL;
 
    if ( p && fHashing )
    {
        pHashed = If_CluHashLookup2( p, pTruth0, 0 );
        if ( pHashed && *pHashed != CLU_UNUSED )
            If_CluUns2Grp2( *pHashed, &G1 );
    }
 
    /* new entry */
    if ( G1.nVars == 0 )
    {
        G1.nVars = acdXX_evaluate( pTruth0, lutSize, nVars );
    }
 
    if ( pHashed )
        *pHashed = If_CluGrp2Uns2( &G1 );
 
    return G1.nVars;
}

Here is the call graph for this function:

Here is the caller graph for this function:

If_CluCheckXXExt()

int If_CluCheckXXExt	(	void *	pMan,
		word *	pTruth,
		int	nVars,
		int	nLutLeaf,
		int	nLutRoot,
		char *	pLut0,
		char *	pLut1,
		word *	pFunc0,
		word *	pFunc1 )

Definition at line 301 of file ifDec66.c.

{
    (void)pMan;
    assert( nLutLeaf == nLutRoot );
    unsigned char result[32];
    int i;
 
    if ( acdXX_decompose( pTruth, nLutRoot, nVars, result ) )
    {
        /* decomposition failed */
        return 0;
    }
 
    /* copy LUT bound set */
    unsigned char * pResult = result + 2;
    int Lut1Size = (int) (*pResult++);
    pLut1[0] = Lut1Size;
    pLut1[1] = 0; /* not used */
    for (i = 0; i < Lut1Size; ++i)
    {
        pLut1[2+i] = *pResult++;
    }
    int func_num_bytes = ( Lut1Size <= 3 ) ? 1 : ( 1 << ( Lut1Size - 3 ) );
    *pFunc1 = 0;
    for (i = 0; i < func_num_bytes; ++i)
    {
        *pFunc1 |= ( ( (word) *pResult++ ) & 0xFF ) << 8*i;
    }
 
    /* copy LUT composition */
    int Lut0Size = (int) (*pResult++);
    pLut0[0] = Lut0Size;
    pLut0[1] = 0; /* not used */
    for (i = 0; i < Lut0Size; ++i)
    {
        pLut0[2+i] = *pResult++;
    }
    func_num_bytes = ( Lut0Size <= 3 ) ? 1 : ( 1 << ( Lut0Size - 3 ) );
    *pFunc0 = 0;
    for (i = 0; i < func_num_bytes; ++i)
    {
        *pFunc0 |= ( ( (word) *pResult++ ) & 0xFF ) << 8*i;
    }
 
    *pFunc1 = If_CluAdjust2( *pFunc1, Lut1Size );
    *pFunc0 = If_CluAdjust2( *pFunc0, Lut0Size );
 
    return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

If_CluHashFindMedian2()

int If_CluHashFindMedian2	(	If_Man_t *	p,
		int	t )

Definition at line 128 of file ifDec66.c.

{
    If_Hte_t * pEntry;
    Vec_Int_t * vCounters;
    int i, Max = 0, Total = 0, Half = 0;
    vCounters = Vec_IntStart( 1000 );
    for ( i = 0; i < p->nTableSize[t]; i++ )
    {
        for ( pEntry = ((If_Hte_t **)p->pHashTable[t])[i]; pEntry; pEntry = pEntry->pNext )
        {
            if ( Max < (int)pEntry->Counter )
            {
                Max = pEntry->Counter;
                Vec_IntSetEntry( vCounters, pEntry->Counter, 0 );
            }
            Vec_IntAddToEntry( vCounters, pEntry->Counter, 1 );
            Total++;
        }
    }
    for ( i = Max; i > 0; i-- )
    {
        Half += Vec_IntEntry( vCounters, i );
        if ( Half > Total/2 )
            break;
    }
/*
    printf( "total = %d  ", Total );
    printf( "half = %d  ", Half );
    printf( "i = %d  ", i );
    printf( "Max = %d.\n", Max );
*/
    Vec_IntFree( vCounters );
    return Abc_MaxInt( i, 1 );
}

Here is the caller graph for this function:

If_CluHashKey2()

int If_CluHashKey2	(	word *	pTruth,
		int	nWords,
		int	Size )

Definition at line 163 of file ifDec66.c.

{
    static unsigned BigPrimes[8] = {12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741};
    unsigned Value = 0;
    int i;
    if ( nWords < 4 )
    {
        unsigned char * s = (unsigned char *)pTruth;
        for ( i = 0; i < 8 * nWords; i++ )
            Value ^= BigPrimes[i % 7] * s[i];
    }
    else
    {
        unsigned * s = (unsigned *)pTruth;
        for ( i = 0; i < 2 * nWords; i++ )
            Value ^= BigPrimes[i % 7] * s[i];
    }
    return Value % Size;
}

Here is the caller graph for this function:

If_CluHashLookup2()

unsigned * If_CluHashLookup2	(	If_Man_t *	p,
		word *	pTruth,
		int	t )

Definition at line 183 of file ifDec66.c.

{
    If_Hte_t * pEntry, * pPrev;
    int nWords, HashKey;
    if ( p == NULL )
        return NULL;
    nWords = If_CluWordNum2(p->pPars->nLutSize);
    if ( p->pMemEntries == NULL )
        p->pMemEntries = Mem_FixedStart( sizeof(If_Hte_t) + sizeof(word) * (If_CluWordNum2(p->pPars->nLutSize) - 1) );
    if ( p->pHashTable[t] == NULL )
    {
        // decide how large should be the table
        int nEntriesMax1 = 4 * If_CluPrimeCudd2( Vec_PtrSize(p->vObjs) * p->pPars->nCutsMax );
        int nEntriesMax2 = (int)(((double)CLU_MEM_MAX * (1 << 20)) / If_CluWordNum2(p->pPars->nLutSize) / 8);
//        int nEntriesMax2 = 10000;
        // create table
        p->nTableSize[t] = If_CluPrimeCudd2( Abc_MinInt(nEntriesMax1, nEntriesMax2)/2 );
        p->pHashTable[t] = ABC_CALLOC( void *, p->nTableSize[t] );
    }
    // check if this entry exists
    HashKey = If_CluHashKey2( pTruth, nWords, p->nTableSize[t] );
    for ( pEntry = ((If_Hte_t **)p->pHashTable[t])[HashKey]; pEntry; pEntry = pEntry->pNext )
        if ( memcmp(pEntry->pTruth, pTruth, sizeof(word) * nWords) == 0 )
        {
            pEntry->Counter++;
            return &pEntry->Group;
        }
    // resize the hash table
    if ( p->nTableEntries[t] >= 2 * p->nTableSize[t] )
    {
        // collect useful entries
        If_Hte_t * pPrev;
        Vec_Ptr_t * vUseful = Vec_PtrAlloc( p->nTableEntries[t] );
        int i, Median = If_CluHashFindMedian2( p, t );
        for ( i = 0; i < p->nTableSize[t]; i++ )
        {
            for ( pEntry = ((If_Hte_t **)p->pHashTable[t])[i]; pEntry; )
            {
                if ( (int)pEntry->Counter > Median )
                {
                    Vec_PtrPush( vUseful, pEntry );
                    pEntry = pEntry->pNext;
                }
                else
                {
                    pPrev = pEntry->pNext;
                    Mem_FixedEntryRecycle( p->pMemEntries, (char *)pEntry );
                    pEntry = pPrev;
                }
            }
        }
        // add useful entries
        memset( p->pHashTable[t], 0, sizeof(void *) * p->nTableSize[t] );
        Vec_PtrForEachEntry( If_Hte_t *, vUseful, pEntry, i )
        {
            HashKey = If_CluHashKey2( pEntry->pTruth, nWords, p->nTableSize[t] );
            pPrev = ((If_Hte_t **)p->pHashTable[t])[HashKey];
            if ( pPrev == NULL || pEntry->Counter >= pPrev->Counter )
            {
                pEntry->pNext = pPrev;
                ((If_Hte_t **)p->pHashTable[t])[HashKey] = pEntry;
            }
            else
            {
                while ( pPrev->pNext && pEntry->Counter < pPrev->pNext->Counter )
                    pPrev = pPrev->pNext;
                pEntry->pNext = pPrev->pNext;
                pPrev->pNext = pEntry;
            }
        }
        p->nTableEntries[t] = Vec_PtrSize( vUseful );
        Vec_PtrFree( vUseful );
    }
    // create entry
    p->nTableEntries[t]++;
    pEntry = (If_Hte_t *)Mem_FixedEntryFetch( p->pMemEntries );
    memcpy( pEntry->pTruth, pTruth, sizeof(word) * nWords );
    pEntry->Group = CLU_UNUSED;
    pEntry->Counter = 1;
    // insert at the beginning
//    pEntry->pNext = ((If_Hte_t **)p->pHashTable[t])[HashKey];
//    ((If_Hte_t **)p->pHashTable[t])[HashKey] = pEntry;
    // insert at the end
    pEntry->pNext = NULL;
    for ( pPrev = ((If_Hte_t **)p->pHashTable[t])[HashKey]; pPrev && pPrev->pNext; pPrev = pPrev->pNext );
    if ( pPrev == NULL )
        ((If_Hte_t **)p->pHashTable[t])[HashKey] = pEntry;
    else
        pPrev->pNext = pEntry;
    return &pEntry->Group;
}

Here is the call graph for this function:

Here is the caller graph for this function:

If_CluPrimeCudd2()

unsigned int If_CluPrimeCudd2

(

unsigned int

p

)

Definition at line 76 of file ifDec66.c.

{
    int i,pn;
 
    p--;
    do {
        p++;
        if (p&1) {
        pn = 1;
        i = 3;
        while ((unsigned) (i * i) <= p) {
        if (p % i == 0) {
            pn = 0;
            break;
        }
        i += 2;
        }
    } else {
        pn = 0;
    }
    } while (!pn);
    return(p);
 
} /* end of Cudd_Prime */

Here is the caller graph for this function:

If_CutPerformCheckXX()

int If_CutPerformCheckXX	(	If_Man_t *	p,
		unsigned *	pTruth0,
		int	nVars,
		int	nLeaves,
		char *	pStr )

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

Synopsis [Performs ACD into 66 cascade.]

Description []

SideEffects []

SeeAlso []

Definition at line 363 of file ifDec66.c.

{
    unsigned pTruth[IF_MAX_FUNC_LUTSIZE > 5 ? 1 << (IF_MAX_FUNC_LUTSIZE - 5) : 1];
    int Length;
    // stretch the truth table
    memcpy( pTruth, pTruth0, sizeof(word) * Abc_TtWordNum(nVars) );
    Abc_TtStretch6( (word *)pTruth, nLeaves, p->pPars->nLutSize );
 
    // if cutmin is disabled, minimize the function
    if ( !p->pPars->fCutMin )
        nLeaves = Abc_TtMinBase( (word *)pTruth, NULL, nLeaves, nVars );
 
    // quit if parameters are wrong
    Length = strlen(pStr);
    if ( Length != 2 )
    {
        printf( "Wrong LUT struct (%s)\n", pStr );
        return 0;
    }
 
    int lutSize = pStr[0] - '0';
    if ( lutSize < 3 || lutSize > 6 )
    {
        printf( "The LUT size (%d) should belong to {3,4,5,6}.\n", lutSize );
        return 0;
    }
 
    if ( nLeaves >= 2 * lutSize  )
    {
        printf( "The cut size (%d) is too large for the LUT structure %s.\n", nLeaves, pStr );
        return 0;
    }
 
    // consider trivial case
    if ( nLeaves <= lutSize )
        return 1;
 
    return If_CluCheckXX(p, (word*)pTruth, lutSize, nVars, 1);
}

Here is the call graph for this function: