Several updates to FXCH including:

- Cube Grouping
- New sub-cube hash table

1 files changed, 125 insertions, 1 deletions

diff --git a/src/opt/fxch/Fxch.c b/src/opt/fxch/Fxch.c
index 6c3983ef..02b3aa66 100644
--- a/src/opt/fxch/Fxch.c
+++ b/src/opt/fxch/Fxch.c
@@ -15,7 +15,6 @@
   Revision    []
 
 ***********************************************************************/
-
 #include "Fxch.h"
 
 ABC_NAMESPACE_IMPL_START
@@ -26,6 +25,125 @@ ABC_NAMESPACE_IMPL_START
 
 /**Function*************************************************************
 
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxch_CubesGruping(Fxch_Man_t* pFxchMan)
+{
+    Vec_Int_t* vCube;
+    int iCube;
+
+    /* Identify the number of Outputs and create the translation table */
+    pFxchMan->vTranslation = Vec_IntAlloc( 32 );
+    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
+    {
+        int Id = Vec_IntEntry( vCube, 0 );
+        int iTranslation = Vec_IntFind( pFxchMan->vTranslation, Id );
+
+        if ( iTranslation == -1 )
+            Vec_IntPush( pFxchMan->vTranslation, Id );
+    }
+    int nOutputs = Vec_IntSize( pFxchMan->vTranslation );
+
+    /* Size of the OutputID in number o ints */
+    int SizeOutputID = ( nOutputs >> 5 ) + ( ( nOutputs & 31 ) > 0 );
+
+    /* Initialize needed structures */
+    pFxchMan->vOutputID = Vec_IntAlloc( 4096 );
+    pFxchMan->pTempOutputID = ABC_CALLOC( int, SizeOutputID );
+    pFxchMan->nSizeOutputID = SizeOutputID;
+
+    Hsh_VecMan_t* pCubeHash =  Hsh_VecManStart( 1024 );
+
+    /* Identify equal cubes */
+    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
+    {
+        int Id = Vec_IntEntry( vCube, 0 );
+        int iTranslation = Vec_IntFind( pFxchMan->vTranslation, Id );
+        Vec_IntWriteEntry( vCube, 0, 0 ); // Clear ID, Outputs will be identified by it later
+
+        int iCubeNoID = Hsh_VecManAdd( pCubeHash, vCube );
+        int Temp = ( 1 << ( iTranslation & 31 ) );
+        if ( iCubeNoID == Vec_IntSize( pFxchMan->vOutputID ) / SizeOutputID )
+        {
+            for ( int i = 0; i < SizeOutputID; i++ )
+                pFxchMan->pTempOutputID[i] = 0;
+
+            pFxchMan->pTempOutputID[ iTranslation >> 5 ] = Temp;
+            Vec_IntPushArray( pFxchMan->vOutputID, pFxchMan->pTempOutputID, SizeOutputID ); 
+        }
+        else
+        {
+            Vec_IntClear( vCube );
+            int* pEntry = Vec_IntEntryP( pFxchMan->vOutputID, ( iCubeNoID * SizeOutputID ) + ( iTranslation >> 5 ) );
+            *pEntry |= Temp;
+        }
+    }
+
+    Hsh_VecManStop( pCubeHash );
+    Vec_WecRemoveEmpty( pFxchMan->vCubes );
+}
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Fxch_CubesUnGruping(Fxch_Man_t* pFxchMan)
+{
+    int iCube;
+    int i, j;
+    Vec_Int_t* vCube;
+    Vec_Int_t* vNewCube;
+
+    assert( Vec_WecSize( pFxchMan->vCubes ) == ( Vec_IntSize( pFxchMan->vOutputID ) / pFxchMan->nSizeOutputID ) );
+    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
+    {
+        if ( Vec_IntSize( vCube ) == 0 || Vec_IntEntry( vCube, 0 ) != 0 )
+            continue;
+
+        int* pOutputID = Vec_IntEntryP( pFxchMan->vOutputID, iCube * pFxchMan->nSizeOutputID );
+        int nOnes = 0;
+
+        for ( i = 0; i < pFxchMan->nSizeOutputID; i++ )
+            nOnes += Fxch_CountOnes( (unsigned int) pOutputID[i] );
+
+        for ( i = 0; i < pFxchMan->nSizeOutputID && nOnes; i++ )
+            for ( j = 0; j < 32 && nOnes; j++ )
+                if ( pOutputID[i] & ( 1 << j ) )
+                {
+                    if ( nOnes == 1 )
+                        Vec_IntWriteEntry( vCube, 0, Vec_IntEntry( pFxchMan->vTranslation, ( i << 5 ) | j ) );
+                    else
+                    {
+                        vNewCube = Vec_WecPushLevel( pFxchMan->vCubes );
+                        Vec_IntAppend( vNewCube, vCube );
+                        Vec_IntWriteEntry( vNewCube, 0, Vec_IntEntry( pFxchMan->vTranslation, (i << 5 ) | j ) );
+                    }
+                    nOnes -= 1;
+                }
+    }
+
+    Vec_IntFree( pFxchMan->vTranslation );
+    Vec_IntFree( pFxchMan->vOutputID );
+    ABC_FREE( pFxchMan->pTempOutputID );
+    return;
+}
+
+/**Function*************************************************************
+
   Synopsis    [ Performs fast extract with cube hashing on a set
                 of covers. ]
 
@@ -47,6 +165,7 @@ int Fxch_FastExtract( Vec_Wec_t* vCubes,
     int i;
 
     TempTime = Abc_Clock();
+    Fxch_CubesGruping( pFxchMan );
     Fxch_ManMapLiteralsIntoCubes( pFxchMan, ObjIdMax );
     Fxch_ManGenerateLitHashKeys( pFxchMan );
     Fxch_ManComputeLevel( pFxchMan );
@@ -61,6 +180,7 @@ int Fxch_FastExtract( Vec_Wec_t* vCubes,
         Fxch_ManPrintStats( pFxchMan );
 
     TempTime = Abc_Clock();
+    
     for ( i = 0; (!nMaxDivExt || i < nMaxDivExt) && Vec_QueTopPriority( pFxchMan->vDivPrio ) > 0.0; i++ )
     {
         int iDiv = Vec_QuePop( pFxchMan->vDivPrio );
@@ -70,6 +190,7 @@ int Fxch_FastExtract( Vec_Wec_t* vCubes,
 
         Fxch_ManUpdate( pFxchMan, iDiv );
     }
+   
     pFxchMan->timeExt = Abc_Clock() - TempTime;
 
     if ( fVerbose )
@@ -80,9 +201,12 @@ int Fxch_FastExtract( Vec_Wec_t* vCubes,
         Abc_PrintTime( 1, "[FXCH]    +-> Extr", pFxchMan->timeExt );
     }
 
+    Fxch_CubesUnGruping( pFxchMan );
     Fxch_ManSCHashTablesFree( pFxchMan );
     Fxch_ManFree( pFxchMan );
+
     Vec_WecRemoveEmpty( vCubes );
+    Vec_WecSortByFirstInt( vCubes, 0 );
 
     return 1;
 }