#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "misc/vec/vec.h"
#include "misc/vec/vecHsh.h"
#include "bool/kit/kit.h"
#include "misc/extra/extra.h"

Include dependency graph for extraUtilPrime.c:

Classes
struct	Tab_Man_t_

struct	Tab_Ent_t_

Macros
#define	ABC_PRIME_MASK 0xFF

#define	TAB_UNUSED 0xFFFF

#define	Tab_ManForEachCube(p, pCube, c)

#define	Tab_ManForEachCubeReverse(p, pCube, c)

Typedefs
typedef struct Tab_Ent_t_	Tab_Ent_t

Functions
ABC_NAMESPACE_IMPL_START void	Abc_GenCountDump (Vec_Int_t vPrimes, int nVars, char pFileName)
	DECLARATIONS ///.

void	Abc_GenCountHits1 (Vec_Bit_t vMap, Vec_Int_t vPrimes, int nVars)

Vec_Int_t *	Abc_GenPrimes (int nVars)

void	Abc_GenPrimesTest ()

Tab_Man_t *	Tab_ManAlloc (int nVars, int nCubes)

void	Tab_ManFree (Tab_Man_t *p)

void	Tab_ManStart (Tab_Man_t p, Vec_Int_t vCubes)

int	Tab_ManCubeFree (int pCube1, int pCube2, Vec_Int_t *vCubeFree)

int	Tab_ManCheckEqual2 (int pCube1, int pCube2, int Var1, int Var2)

int	Tab_ManCheckEqual (int pCube1, int pCube2, int Var1, int Var2)

int	Tab_ManCountItems (Tab_Man_t p, int Dist2, Vec_Int_t *pvStarts)

Vec_Int_t *	Tab_ManCollectDist1 (Tab_Man_t *p, int Dist2)

void	Tab_DecomposeTest ()

Macro Definition Documentation

◆ ABC_PRIME_MASK

#define ABC_PRIME_MASK 0xFF

Definition at line 128 of file extraUtilPrime.c.

◆ Tab_ManForEachCube

#define Tab_ManForEachCube	(	p,
		pCube,
		c )

Value:

for ( c = 0; c < p->nCubes && (pCube = Tab_ManCube(p, c)); c++ ) \

if ( pCube[0] == -1 ) {} else

p

Cube * p

Definition exorList.c:222

Definition at line 280 of file extraUtilPrime.c.

#define Tab_ManForEachCube( p, pCube, c )                                  \
    for ( c = 0; c < p->nCubes && (pCube = Tab_ManCube(p, c)); c++ )       \
        if ( pCube[0] == -1 ) {} else 

◆ Tab_ManForEachCubeReverse

#define Tab_ManForEachCubeReverse	(	p,
		pCube,
		c )

Value:

for ( c = p->nCubes - 1; c >= 0 && (pCube = Tab_ManCube(p, c)); c-- ) \

if ( pCube[0] == -1 ) {} else

Definition at line 284 of file extraUtilPrime.c.

#define Tab_ManForEachCubeReverse( p, pCube, c )                           \
    for ( c = p->nCubes - 1; c >= 0 && (pCube = Tab_ManCube(p, c)); c-- )  \
        if ( pCube[0] == -1 ) {} else 

◆ TAB_UNUSED

#define TAB_UNUSED 0xFFFF

Definition at line 167 of file extraUtilPrime.c.

Typedef Documentation

◆ Tab_Ent_t

typedef struct Tab_Ent_t_ Tab_Ent_t

Definition at line 170 of file extraUtilPrime.c.

Function Documentation

◆ Abc_GenCountDump()

ABC_NAMESPACE_IMPL_START void Abc_GenCountDump	(	Vec_Int_t *	vPrimes,
		int	nVars,
		char *	pFileName )

DECLARATIONS ///.

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

FileName [extraUtilPrime.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [extra]

Synopsis [Function enumeration.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id: extraUtilPrime.c,v 1.0 2003/02/01 00:00:00 alanmi Exp

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 51 of file extraUtilPrime.c.

{
    FILE * pFile;
    int i, k, Prime;
    pFile = fopen( pFileName, "wb" );
    fprintf( pFile, "# %d prime numbers up to 2^%d generated by ABC on %s\n", Vec_IntSize(vPrimes), nVars, Extra_TimeStamp() );
    fprintf( pFile, ".i %d\n", nVars );
    fprintf( pFile, ".o %d\n", 1 );
    fprintf( pFile, ".p %d\n", Vec_IntSize(vPrimes) );
    Vec_IntForEachEntry( vPrimes, Prime, i )
        for ( k = nVars-1; k >= 0; k-- )
            fprintf( pFile, "%d%s", (Prime >> k)&1, k ? "" : " 1\n" );
    fprintf( pFile, ".e\n\n" );
    fclose( pFile );
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_GenCountHits1()

void Abc_GenCountHits1	(	Vec_Bit_t *	vMap,
		Vec_Int_t *	vPrimes,
		int	nVars )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 78 of file extraUtilPrime.c.

{
    abctime clk = Abc_Clock();
    int i, k, Prime, Count = 0;
    Vec_IntForEachEntry( vPrimes, Prime, i )
    {
        for ( k = 0; k < nVars; k++ )
            if ( !Vec_BitEntry(vMap, Prime ^ (1<<k)) )
            {
                //printf( "%3d : %2d %2d     flipped bit %d\n", Count, Prime, Prime ^ (1<<k), k );
                Count++;
            }
    }
    printf( "Dist1 pairs = %d. ", Count/2 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}

Here is the caller graph for this function:

◆ Abc_GenPrimes()

Vec_Int_t * Abc_GenPrimes ( int nVars )

Definition at line 94 of file extraUtilPrime.c.

{
    int i, n, nBits = ( 1 << nVars );
    Vec_Bit_t * vMap = Vec_BitStart( nBits );
    Vec_Int_t * vPrimes = Vec_IntAlloc( 1000 );
    Vec_BitWriteEntry(vMap, 0, 1);
    Vec_BitWriteEntry(vMap, 1, 1);
    for ( n = 2; n < nBits; n++ )
        if ( !Vec_BitEntry(vMap, n) )
            for ( i = 2*n; i < nBits; i += n )
                Vec_BitWriteEntry(vMap, i, 1);
    for ( n = 2; n < nBits; n++ )
        if ( !Vec_BitEntry(vMap, n) )
            Vec_IntPush( vPrimes, n );
    printf( "Primes up to 2^%d = %d\n", nVars, Vec_IntSize(vPrimes) );
    Abc_GenCountHits1( vMap, vPrimes, nVars );
    Vec_BitFree( vMap );
    return vPrimes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Abc_GenPrimesTest()

void Abc_GenPrimesTest ( )

Definition at line 113 of file extraUtilPrime.c.

{
    // 54,400,028 primes up to 2^30 can be computed in 22 sec
    int nVars = 18;
    Vec_Int_t * vPrimes = Abc_GenPrimes( nVars );
    Abc_GenCountDump( vPrimes, nVars, "primes18.pla" );
    //Vec_IntPrint( vPrimes );
    printf( "Primes up to 2^%d = %d\n", nVars, Vec_IntSize(vPrimes) );
 
    Vec_IntFree( vPrimes );
}

Here is the call graph for this function:

◆ Tab_DecomposeTest()

void Tab_DecomposeTest ( )

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

Synopsis [Table decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 578 of file extraUtilPrime.c.

{
    int nVars = 20;// no more than 13
    abctime clk = Abc_Clock();
    Vec_Int_t * vPairs;
    Vec_Int_t * vPrimes = Abc_GenPrimes( nVars );
    Tab_Man_t * p = Tab_ManAlloc( nVars, Vec_IntSize(vPrimes) );
    Tab_ManStart( p, vPrimes );
    printf( "Created %d cubes dependent on %d variables.\n", p->nCubes, p->nVars );
    vPairs = Tab_ManCollectDist1( p, 0 );
    printf( "Collected %d pairs.\n", Vec_IntSize(vPairs)/2 );
    Vec_IntFree( vPairs );
    Tab_ManFree( p );
    Vec_IntFree( vPrimes );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}

Here is the call graph for this function:

◆ Tab_ManAlloc()

Tab_Man_t * Tab_ManAlloc	(	int	nVars,
		int	nCubes )

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

Synopsis [Manager manipulation.]

Description []

SideEffects []

SeeAlso []

Definition at line 300 of file extraUtilPrime.c.

{
    Tab_Man_t * p = ABC_CALLOC( Tab_Man_t, 1 );
    p->nVars   = nVars;
    p->nCubes  = nCubes;
    p->Degree  = Abc_Base2Log((p->nVars + 1) * p->nCubes + 1) + 3;
    p->Mask    = (1 << p->Degree) - 1;
    //p->nEnts   = 1;
    p->pCubes  = ABC_CALLOC( int, p->nCubes * (p->nVars + 1) );
    p->pValues = ABC_CALLOC( word, p->nCubes );
//    p->pTable  = ABC_CALLOC( Tab_Ent_t, (p->Mask + 1) );
    printf( "Allocated %.2f MB for cube structure.\n", 4.0 * p->nCubes * (p->nVars + 2) / (1 << 20) );
    return p;
}

Here is the caller graph for this function:

◆ Tab_ManCheckEqual()

int Tab_ManCheckEqual	(	int *	pCube1,
		int *	pCube2,
		int	Var1,
		int	Var2 )

Definition at line 397 of file extraUtilPrime.c.

{
    int Cube1[32], Cube2[32];
    int i, k, nVars1, nVars2;
    assert( pCube1[0] <= 32 );
    assert( pCube2[0] <= 32 );
    for ( i = 1, k = 0; i <= pCube1[0]; i++ )
        if ( i != Var1 )
            Cube1[k++] = pCube1[i];
    nVars1 = k;
    for ( i = 1, k = 0; i <= pCube2[0]; i++ )
        if ( i != Var2 )
            Cube2[k++] = pCube2[i];
    nVars2 = k;
    if ( nVars1 != nVars2 )
        return 0;
    for ( i = 0; i < nVars1; i++ )
        if ( Cube1[i] != Cube2[i] )
            return 0;
    return 1;
}

Here is the caller graph for this function:

◆ Tab_ManCheckEqual2()

int Tab_ManCheckEqual2	(	int *	pCube1,
		int *	pCube2,
		int	Var1,
		int	Var2 )

Definition at line 382 of file extraUtilPrime.c.

{
    int i1, i2;
    for ( i1 = i2 = 1; ; i1++, i2++ )
    {
        if ( i1 == Var1 )  i1++;
        if ( i2 == Var2 )  i2++;
        if ( i1 > pCube1[0] || i2 > pCube2[0] )
            return 0;
        if ( pCube1[i1] != pCube2[i2] )
            return 0;
        if ( i1 == pCube1[0] && i2 == pCube2[0] )
            return 1;
    }
}

◆ Tab_ManCollectDist1()

Vec_Int_t * Tab_ManCollectDist1	(	Tab_Man_t *	p,
		int	Dist2 )

Definition at line 446 of file extraUtilPrime.c.

{
    Vec_Int_t * vStarts = NULL;                           // starting mark for each cube
    int nItems = Tab_ManCountItems( p, Dist2, &vStarts ); // item count
    int nBits  = Abc_Base2Log( nItems ) + 6;              // hash table size  
    Vec_Bit_t * vPres = Vec_BitStart( 1 << nBits );       // hash table
    Vec_Bit_t * vMarks = Vec_BitStart( nItems );          // collisions 
    Vec_Int_t * vUseful = Vec_IntAlloc( 1000 );           // useful pairs
    Vec_Int_t * vBin = Vec_IntAlloc( 100 );
    Vec_Int_t * vCubeFree = Vec_IntAlloc( 100 );
    word Value; unsigned Mask = (1 << nBits) - 1;
    int * pCube, c, a, b, nMarks = 0, nUseful, Entry1, Entry2;
    // iterate forward
    Tab_ManForEachCube( p, pCube, c )
    {
        // cube
        if ( Vec_BitAddEntry(vPres, (int)p->pValues[c] & Mask) )
            Vec_BitWriteEntry( vMarks, nMarks, 1 );
        nMarks++;
        // dist1
        for ( a = 1; a <= pCube[0]; a++, nMarks++ )
            if ( Vec_BitAddEntry(vPres, (int)(p->pValues[c] - Tab_ManValue(p, pCube[a])) & Mask) )
                Vec_BitWriteEntry( vMarks, nMarks, 1 );
        // dist2
        if ( Dist2 )
        for ( a = 1; a <= pCube[0]; a++ )
        {
            Value = p->pValues[c] - Tab_ManValue(p, pCube[a]);
            for ( b = a + 1; b <= pCube[0]; b++, nMarks++ )
                if ( Vec_BitAddEntry(vPres, (int)(Value - Tab_ManValue(p, pCube[b])) & Mask) )
                    Vec_BitWriteEntry( vMarks, nMarks, 1 );
        }
    }
    assert( nMarks == nItems );
    Vec_BitReset( vPres );
    // iterate backward
    nMarks--;
    Tab_ManForEachCubeReverse( p, pCube, c )
    {
        Value = p->pValues[c];
        // dist2
        if ( Dist2 )
        for ( a = pCube[0]; a >= 1; a-- )
        {
            Value = p->pValues[c] - Tab_ManValue(p, pCube[a]);
            for ( b = pCube[0]; b >= a + 1; b--, nMarks-- )
                if ( Vec_BitAddEntry(vPres, (int)(Value - Tab_ManValue(p, pCube[b])) & Mask) )
                    Vec_BitWriteEntry( vMarks, nMarks, 1 );
        }
        // dist1
        for ( a = pCube[0]; a >= 1; a--, nMarks-- )
            if ( Vec_BitAddEntry(vPres, (int)(p->pValues[c] - Tab_ManValue(p, pCube[a])) & Mask) )
                Vec_BitWriteEntry( vMarks, nMarks, 1 );
        // cube
        if ( Vec_BitAddEntry(vPres, (int)p->pValues[c] & Mask) )
            Vec_BitWriteEntry( vMarks, nMarks, 1 );
        nMarks--;
    }
    nMarks++;
    assert( nMarks == 0 );
    Vec_BitFree( vPres );
    // count useful
    nUseful = Vec_BitCount( vMarks );
printf( "Items = %d. Bits = %d.   Useful = %d.   \n", nItems, nBits, nUseful );
 
    // add to the hash table
    p->nTable = Abc_PrimeCudd(nUseful);
    p->pTable = ABC_FALLOC( Tab_Ent_t, p->nTable );
printf( "Table %d\n", p->nTable );
    Tab_ManForEachCube( p, pCube, c )
    {
        // cube
        if ( Vec_BitEntry(vMarks, nMarks++) )
            Tab_ManHashAdd( p, (int)(p->pValues[c] % p->nTable), c, TAB_UNUSED, TAB_UNUSED );
        // dist1
        for ( a = 1; a <= pCube[0]; a++, nMarks++ )
            if ( Vec_BitEntry(vMarks, nMarks) )
                Tab_ManHashAdd( p, (int)((p->pValues[c] - Tab_ManValue(p, pCube[a])) % p->nTable), c, a-1, TAB_UNUSED );
        // dist2
        if ( Dist2 )
        for ( a = 1; a <= pCube[0]; a++ )
        {
            Value = p->pValues[c] - Tab_ManValue(p, pCube[a]);
            for ( b = a + 1; b <= pCube[0]; b++, nMarks++ )
                if ( Vec_BitEntry(vMarks, nMarks) )
                    Tab_ManHashAdd( p, (int)((Value - Tab_ManValue(p, pCube[b])) % p->nTable), c, a-1, b-1 );
        }
    }
    assert( nMarks == nItems );
    // collect entries
    for ( c = 0; c < p->nTable; c++ )
    {
        Tab_ManHashCollectBin( p, c, vBin );
        //printf( "%d ", Vec_IntSize(vBin) );
        //if ( c > 100 )
        //    break;
        Vec_IntForEachEntry( vBin, Entry1, a )
        Vec_IntForEachEntryStart( vBin, Entry2, b, a + 1 )
        {
            Tab_Ent_t * pEntA = Tab_ManEnt( p, Entry1 );
            Tab_Ent_t * pEntB = Tab_ManEnt( p, Entry2 );
            int * pCubeA = Tab_ManCube( p, pEntA->Cube );
            int * pCubeB = Tab_ManCube( p, pEntB->Cube );
//            int Base = Tab_ManCubeFree( pCubeA, pCubeB, vCubeFree );
//            if ( Vec_IntSize(vCubeFree) == 2 )
            if ( Tab_ManCheckEqual(pCubeA, pCubeB, pEntA->VarA+1, pEntB->VarA+1) )
            {
                Vec_IntPushTwo( vUseful, pEntA->Cube, pEntB->Cube );
            }
        }
 
    }
    //printf( "\n" );
 
    ABC_FREE( p->pTable );
    Vec_IntFree( vCubeFree );
    Vec_IntFree( vBin );
    Vec_BitFree( vMarks );
    return vUseful;
}

Here is the call graph for this function:

Here is the caller graph for this function:

◆ Tab_ManCountItems()

int Tab_ManCountItems	(	Tab_Man_t *	p,
		int	Dist2,
		Vec_Int_t **	pvStarts )

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

Synopsis [Collecting distance-1 pairs.]

Description []

SideEffects []

SeeAlso []

Definition at line 430 of file extraUtilPrime.c.

{
    Vec_Int_t * vStarts = Vec_IntAlloc( p->nCubes );
    int * pCube, c, Count = 0;
    Tab_ManForEachCube( p, pCube, c )
    {
        Vec_IntPush( vStarts, Count );
        Count += 1 + pCube[0];
        if ( Dist2 )
            Count += pCube[0] * pCube[0] / 2;
    }
    assert( Vec_IntSize(vStarts) == p->nCubes );
    if ( pvStarts )
        *pvStarts = vStarts;
    return Count;
}

Here is the caller graph for this function:

◆ Tab_ManCubeFree()

int Tab_ManCubeFree	(	int *	pCube1,
		int *	pCube2,
		Vec_Int_t *	vCubeFree )

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

Synopsis [Find a cube-free divisor of the two cubes.]

Description []

SideEffects []

SeeAlso []

Definition at line 348 of file extraUtilPrime.c.

{
    int * pBeg1 = pCube1 + 1;  // skip variable ID
    int * pBeg2 = pCube2 + 1;  // skip variable ID
    int * pEnd1 = pBeg1 + pCube1[0];
    int * pEnd2 = pBeg2 + pCube2[0];
    int Counter = 0, fAttr0 = 0, fAttr1 = 1;
    Vec_IntClear( vCubeFree );
    while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
    {
        if ( *pBeg1 == *pBeg2 )
            pBeg1++, pBeg2++, Counter++;
        else if ( *pBeg1 < *pBeg2 )
            Vec_IntPush( vCubeFree, Abc_Var2Lit(*pBeg1++, fAttr0) );
        else  
        {
            if ( Vec_IntSize(vCubeFree) == 0 )
                fAttr0 = 1, fAttr1 = 0;
            Vec_IntPush( vCubeFree, Abc_Var2Lit(*pBeg2++, fAttr1) );
        }
    }
    while ( pBeg1 < pEnd1 )
        Vec_IntPush( vCubeFree, Abc_Var2Lit(*pBeg1++, fAttr0) );
    while ( pBeg2 < pEnd2 )
        Vec_IntPush( vCubeFree, Abc_Var2Lit(*pBeg2++, fAttr1) );
    if ( Vec_IntSize(vCubeFree) == 0 )
        printf( "The SOP has duplicated cubes.\n" );
    else if ( Vec_IntSize(vCubeFree) == 1 )
        printf( "The SOP has contained cubes.\n" );
//    else if ( Vec_IntSize(vCubeFree) == 2 && Abc_Lit2Var(Abc_Lit2Var(Vec_IntEntry(vCubeFree, 0))) == Abc_Lit2Var(Abc_Lit2Var(Vec_IntEntry(vCubeFree, 1))) )
//        printf( "The SOP has distance-1 cubes or it is not a prime cover.  Please make sure the result verifies.\n" );
    assert( !Abc_LitIsCompl(Vec_IntEntry(vCubeFree, 0)) );
    return Counter;
}

◆ Tab_ManFree()

void Tab_ManFree ( Tab_Man_t * p )

Definition at line 314 of file extraUtilPrime.c.

{
    ABC_FREE( p->pCubes );
    ABC_FREE( p->pValues );
    ABC_FREE( p->pTable );
    ABC_FREE( p );
}

Here is the caller graph for this function:

◆ Tab_ManStart()

void Tab_ManStart	(	Tab_Man_t *	p,
		Vec_Int_t *	vCubes )

Definition at line 321 of file extraUtilPrime.c.

{
    int * pCube, Cube, c, v;
    p->nLits = 0;
    Tab_ManForEachCube( p, pCube, c )
    {
        Cube = Vec_IntEntry( vCubes, c );
        pCube[0] = p->nVars;
        for ( v = 0; v < p->nVars; v++ )
            pCube[v+1] = Abc_Var2Lit( v, !((Cube >> v) & 1) );
        p->pValues[c] = Tab_ManHashValue( p, pCube );
        p->nLits += pCube[0];
    }
}

Here is the caller graph for this function:

Classes

Macros

Typedefs

Functions

Macro Definition Documentation

◆ ABC_PRIME_MASK

◆ Tab_ManForEachCube

◆ Tab_ManForEachCubeReverse

◆ TAB_UNUSED

Typedef Documentation

◆ Tab_Ent_t

Function Documentation

◆ Abc_GenCountDump()

◆ Abc_GenCountHits1()

◆ Abc_GenPrimes()

◆ Abc_GenPrimesTest()

◆ Tab_DecomposeTest()

◆ Tab_ManAlloc()

◆ Tab_ManCheckEqual()

◆ Tab_ManCheckEqual2()

◆ Tab_ManCollectDist1()

◆ Tab_ManCountItems()

◆ Tab_ManCubeFree()

◆ Tab_ManFree()

◆ Tab_ManStart()