Adding option 'gen -b' to generate signed Booth multipliers.

2 files changed, 286 insertions, 6 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 43ef2ec7..8af2a172 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -12406,6 +12406,7 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
     int fSorter;
     int fMesh;
     int fMulti;
+    int fBooth;
     int fFpga;
     int fOneHot;
     int fRandom;
@@ -12416,6 +12417,7 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
     extern void Abc_GenSorter( char * pFileName, int nVars );
     extern void Abc_GenMesh( char * pFileName, int nVars );
     extern void Abc_GenMulti( char * pFileName, int nVars );
+    extern void Abc_GenBooth( char * pFileName, int nVars );
     extern void Abc_GenFpga( char * pFileName, int nLutSize, int nLuts, int nVars );
     extern void Abc_GenOneHot( char * pFileName, int nVars );
     extern void Abc_GenRandom( char * pFileName, int nPis );
@@ -12429,12 +12431,13 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
     fSorter = 0;
     fMesh = 0;
     fMulti = 0;
+    fBooth = 0;
     fFpga = 0;
     fOneHot = 0;
     fRandom = 0;
     fVerbose = 0;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "NAKLabsemftrvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "NAKLatsembfnrvh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -12485,7 +12488,7 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'a':
             fAdder ^= 1;
             break;
-        case 'b':
+        case 't':
             fAdderTree ^= 1;
             break;
         case 's':
@@ -12497,10 +12500,13 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'm':
             fMulti ^= 1;
             break;
+        case 'b':
+            fBooth ^= 1;
+            break;
         case 'f':
             fFpga ^= 1;
             break;
-        case 't':
+        case 'n':
             fOneHot ^= 1;
             break;
         case 'r':
@@ -12535,6 +12541,8 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
         Abc_GenMesh( FileName, nVars );
     else if ( fMulti )
         Abc_GenMulti( FileName, nVars );
+    else if ( fBooth )
+        Abc_GenBooth( FileName, nVars );
     else if ( fFpga )
         Abc_GenFpga( FileName, nLutSize, nLuts, nVars );
 //        Abc_GenFpga( FileName, 2, 2, 3 );
@@ -12562,19 +12570,20 @@ int Abc_CommandGen( Abc_Frame_t * pAbc, int argc, char ** argv )
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: gen [-NAKL num] [-asemftrvh] <file>\n" );
+    Abc_Print( -2, "usage: gen [-NAKL num] [-atsembfnrvh] <file>\n" );
     Abc_Print( -2, "\t         generates simple circuits\n" );
     Abc_Print( -2, "\t-N num : the number of variables [default = %d]\n", nVars );
     Abc_Print( -2, "\t-A num : the number of agruments (for adder tree) [default = %d]\n", nArgs );
     Abc_Print( -2, "\t-K num : the LUT size (to be used with switch -f) [default = %d]\n", nLutSize );
     Abc_Print( -2, "\t-L num : the LUT count (to be used with switch -f) [default = %d]\n", nLuts );
     Abc_Print( -2, "\t-a     : generate ripple-carry adder [default = %s]\n", fAdder? "yes": "no" );
-    Abc_Print( -2, "\t-b     : generate an adder tree [default = %s]\n", fAdderTree? "yes": "no" );
+    Abc_Print( -2, "\t-t     : generate an adder tree [default = %s]\n", fAdderTree? "yes": "no" );
     Abc_Print( -2, "\t-s     : generate a sorter [default = %s]\n", fSorter? "yes": "no" );
     Abc_Print( -2, "\t-e     : generate a mesh [default = %s]\n", fMesh? "yes": "no" );
     Abc_Print( -2, "\t-m     : generate a multiplier [default = %s]\n", fMulti? "yes": "no" );
+    Abc_Print( -2, "\t-b     : generate a signed Booth multiplier [default = %s]\n", fBooth? "yes": "no" );
     Abc_Print( -2, "\t-f     : generate a LUT FPGA structure [default = %s]\n", fFpga? "yes": "no" );
-    Abc_Print( -2, "\t-t     : generate one-hotness conditions [default = %s]\n", fOneHot? "yes": "no" );
+    Abc_Print( -2, "\t-n     : generate one-hotness conditions [default = %s]\n", fOneHot? "yes": "no" );
     Abc_Print( -2, "\t-r     : generate random single-output function [default = %s]\n", fRandom? "yes": "no" );
     Abc_Print( -2, "\t-v     : prints verbose information [default = %s]\n", fVerbose? "yes": "no" );
     Abc_Print( -2, "\t-h     : print the command usage\n");
diff --git a/src/base/abci/abcGen.c b/src/base/abci/abcGen.c
index e90040ab..5d1c02ce 100644
--- a/src/base/abci/abcGen.c
+++ b/src/base/abci/abcGen.c
@@ -19,6 +19,7 @@
 ***********************************************************************/
 
 #include "base/abc/abc.h"
+#include "aig/miniaig/miniaig.h"
 
 ABC_NAMESPACE_IMPL_START
 
@@ -870,6 +871,276 @@ void Abc_GenAdderTree( char * pFileName, int nArgs, int nBits )
     fclose( pFile );
 }
 
+
+/**Function*************************************************************
+
+  Synopsis    [Generating signed Booth multiplier.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Abc_GenSignedBoothPP( Gia_Man_t * p, int a, int b, int c, int d, int e )
+{
+/*
+    abc>  lutexact -I 5 -N 7 -g F335ACC0
+
+    05 = 4'b0110( d e )
+    06 = 4'b0110( c d )
+    07 = 4'b0100( a 06 )
+    08 = 4'b1000( b 06 )
+    09 = 4'b0100( 05 07 )
+    10 = 4'b0110( 08 09 )
+    11 = 4'b0110( d 10 )
+*/
+    int n05 = Gia_ManHashXor( p, d,   e   );
+    int n06 = Gia_ManHashXor( p, c,   d   );
+    int n07 = Gia_ManHashAnd( p, a,   Abc_LitNot(n06) );
+    int n08 = Gia_ManHashAnd( p, b,   n06 );
+    int n09 = Gia_ManHashAnd( p, n05, Abc_LitNot(n07) );
+    int n10 = Gia_ManHashXor( p, n08, n09 );
+    int n11 = Gia_ManHashXor( p, d,   n10 );
+    return n11;
+}
+Gia_Man_t * Abc_GenSignedBoothPPTest( int nArgA, int nArgB )
+{
+    Gia_Man_t * pNew; int i, iLit;
+    pNew = Gia_ManStart( 1000 );
+    pNew->pName = Abc_UtilStrsav( "booth" );
+    for ( i = 0; i < 5; i++ )
+         Gia_ManAppendCi(pNew);
+    iLit = Abc_GenSignedBoothPP( pNew, 2, 4, 6, 8, 10 );
+    Gia_ManAppendCo(pNew, iLit);
+    return pNew;
+}
+
+/*
+// parametrized implementation of signed Booth multiplier
+module booth #(
+     parameter N = 4      // bit-width of input a 
+    ,parameter M = 4      // bit-width of input b
+)(
+     input  [N-1:0]   a    // input data
+    ,input  [M-1:0]   b    // input data
+    ,output [N+M-1:0] z    // output data
+);
+
+    localparam TT = 32'hF335ACC0;
+    localparam W  = N+M+1;
+    localparam L  =  (M+1)/2;
+
+    wire [W-1:0] data1[L:0];
+    wire [W-1:0] data2[L:0];
+
+    assign data2[0] = data1[0];
+    assign z = data2[L][N+M-1:0];
+
+    wire [N+1:0] a2 = {a[N-1], a, 1'b0};
+    wire [M+1:0] b2 = {b[M-1], b, 1'b0};
+
+    genvar j;
+    generate
+        for ( j = 0; j < W; j = j + 1 ) begin : J
+            assign data1[0][j] = (j%2 == 0 && j/2 < L) ? b2[j+2] : 1'b0;
+        end
+    endgenerate
+
+    genvar k, i0, i1, i2;
+    generate
+        for ( k = 0; k < 2*L; k = k + 2 ) begin : K
+
+            for ( i0 = 0; i0 < k; i0 = i0 + 1 ) begin : I0
+                assign data1[k/2+1][i0] = 1'b0;
+            end
+
+            for ( i1 = 0; i1 <= N;  i1 = i1 + 1 ) begin : I1
+                wire [4:0] in = {b2[k+2], b2[k+1], b2[k], a2[i1+1], a2[i1]};
+                assign data1[k/2+1][k+i1] = (k > 0 && i1 == N) ? ~TT[in] : TT[in];
+            end
+
+            assign data1[k/2+1][k+N+1]  = k > 0 ? 1'b1 : data1[k/2+1][k+N];
+            for ( i2 = k+N+2; i2 < W; i2 = i2 + 1 ) begin : I2
+                assign data1[k/2+1][i2] = (k > 0 || i2 > k+N+2)? 1'b0 : ~data1[k/2+1][k+N];
+            end
+
+            assign data2[k/2+1] = data2[k/2] + data1[k/2+1];
+
+        end
+    endgenerate
+
+endmodule
+*/
+
+Gia_Man_t * Abc_GenSignedBooth( int nArgN, int nArgM )
+{
+    int nWidth = nArgN + nArgM + 1;
+    int Length = (nArgM + 1) / 2;
+    int i, k, iLit;
+
+    Vec_Int_t * vPPs  = Vec_IntAlloc( nWidth * (Length + 1) );
+    Vec_Int_t * vArgN = Vec_IntAlloc( nArgN + 2 );
+    Vec_Int_t * vArgM = Vec_IntAlloc( nArgM + 2 );
+    int * pArgN = Vec_IntArray( vArgN );
+    int * pArgM = Vec_IntArray( vArgM );
+
+    Gia_Man_t * pTemp, * pNew; 
+    pNew = Gia_ManStart( 1000 );
+    pNew->pName = Abc_UtilStrsav( "booth" );
+
+    Vec_IntPush( vArgN, 0 );
+    for ( i = 0; i < nArgN; i++ )
+        Vec_IntPush( vArgN, Gia_ManAppendCi(pNew) );
+    Vec_IntPush( vArgN, Vec_IntEntryLast(vArgN) );
+
+    Vec_IntPush( vArgM, 0 );
+    for ( i = 0; i < nArgM; i++ )
+        Vec_IntPush( vArgM, Gia_ManAppendCi(pNew) );
+    Vec_IntPush( vArgM, Vec_IntEntryLast(vArgM) );
+
+    for ( i = 0; i < nWidth; i++ )
+        Vec_IntPush( vPPs, (i%2 == 0 && i/2 < Length) ? pArgM[i+2] : 0 );
+
+    Gia_ManHashAlloc( pNew );
+    for ( k = 0; k < 2*Length; k += 2 )
+    {
+        for ( i = 0; i < k; i++ )
+            Vec_IntPush( vPPs, 0 );
+        for ( i = 0; i <= nArgN; i++ )
+        {
+            iLit = Abc_GenSignedBoothPP( pNew, pArgN[i], pArgN[i+1], pArgM[k], pArgM[k+1], pArgM[k+2] );
+            Vec_IntPush( vPPs, Abc_LitNotCond( iLit, k > 0 && i == nArgN ) );
+        }
+        iLit = Vec_IntEntryLast(vPPs);
+        Vec_IntPush( vPPs, k > 0 ? 1 : iLit );
+        for ( i = k+nArgN+2; i < nWidth; i++ )
+            Vec_IntPush( vPPs, (k > 0 || i > k+nArgN+2) ? 0 : Abc_LitNot(iLit) );
+    }
+    Gia_ManHashStop( pNew );
+
+    for ( k = 0; k <= Length; k++ )
+        for ( i = 0; i < nArgN+nArgM; i++ )
+            Gia_ManAppendCo( pNew, Vec_IntEntry(vPPs, k*(nArgN+nArgM+1) + i) );
+    Vec_IntFree( vPPs );
+    Vec_IntFree( vArgN );
+    Vec_IntFree( vArgM );
+
+    pNew = Gia_ManCleanup( pTemp = pNew );
+    Gia_ManStop( pTemp );
+    return pNew;
+}
+Mini_Aig_t * Abc_GenSignedBoothMini( int nArgN, int nArgM )
+{
+    extern Mini_Aig_t * Gia_ManToMiniAig( Gia_Man_t * pGia );
+    Gia_Man_t * pGia = Abc_GenSignedBooth( nArgN, nArgM );
+    Mini_Aig_t * pMini = Gia_ManToMiniAig( pGia );
+    Gia_ManStop( pGia );
+    return pMini;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    []
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Abc_WriteBoothPartialProducts( FILE * pFile, int nVars )
+{
+    Mini_Aig_t * p = Abc_GenSignedBoothMini( nVars, nVars );
+    int i, nNodes = Mini_AigNodeNum(p);
+    int nDigits   = Abc_Base10Log( nVars );
+    int nDigits2  = Abc_Base10Log( 2*nVars );
+    int nDigits3  = Abc_Base10Log( nNodes );
+    int nOut = 0;
+    fprintf( pFile, ".names pp%0*d\n", nDigits3, 0 );
+    for ( i = 1; i < nNodes; i++ )
+    {
+        if ( Mini_AigNodeIsPi( p, i ) )
+        {
+            if ( i > 0 && i <= nVars )
+                fprintf( pFile, ".names a%0*d pp%0*d\n1 1\n", nDigits, i-1,       nDigits3, i );
+            else if ( i > nVars && i <= 2*nVars )
+                fprintf( pFile, ".names b%0*d pp%0*d\n1 1\n", nDigits, i-1-nVars, nDigits3, i );
+            else assert( 0 );
+        }
+        else if ( Mini_AigNodeIsPo( p, i ) )
+        {
+            int Lit = Mini_AigNodeFanin0( p, i );
+            fprintf( pFile, ".names pp%0*d y%0*d_%0*d\n%d 1\n", nDigits3, Abc_Lit2Var(Lit), nDigits, nOut/(2*nVars), nDigits2, nOut%(2*nVars), !Abc_LitIsCompl(Lit) );
+            nOut++;
+        }
+        else if ( Mini_AigNodeIsAnd( p, i ) )
+        {
+            int Lit0 = Mini_AigNodeFanin0( p, i );
+            int Lit1 = Mini_AigNodeFanin1( p, i );
+            fprintf( pFile, ".names pp%0*d pp%0*d pp%0*d\n%d%d 1\n", 
+                nDigits3, Abc_Lit2Var(Lit0), nDigits3, Abc_Lit2Var(Lit1), nDigits3, i, !Abc_LitIsCompl(Lit0), !Abc_LitIsCompl(Lit1) );
+        }
+        else assert( 0 );
+    }
+    Mini_AigStop( p );
+}
+void Abc_WriteBooth( FILE * pFile, int nVars )
+{
+    int i, k, nDigits = Abc_Base10Log( nVars ), nDigits2 = Abc_Base10Log( 2*nVars );
+    int Length = 1+(nVars + 1)/2;
+
+    assert( nVars > 0 );
+    fprintf( pFile, ".model Multi%d\n", nVars );
+
+    fprintf( pFile, ".inputs" );
+    for ( i = 0; i < nVars; i++ )
+        fprintf( pFile, " a%0*d", nDigits, i );
+    for ( i = 0; i < nVars; i++ )
+        fprintf( pFile, " b%0*d", nDigits, i );
+    fprintf( pFile, "\n" );
+
+    fprintf( pFile, ".outputs" );
+    for ( i = 0; i < 2*nVars; i++ )
+        fprintf( pFile, " m%0*d", nDigits2, i );
+    fprintf( pFile, "\n" );
+
+    Abc_WriteBoothPartialProducts( pFile, nVars );
+
+    for ( i = 0; i < 2*nVars; i++ )
+        fprintf( pFile, ".names x%0*d_%0*d\n", nDigits, 0, nDigits2, i );
+    for ( k = 0; k < Length; k++ )
+    {
+        fprintf( pFile, ".subckt ADD%d", 2*nVars );
+        for ( i = 0; i < 2*nVars; i++ )
+            fprintf( pFile, " a%0*d=x%0*d_%0*d", nDigits2, i, nDigits, k, nDigits2, i );
+        for ( i = 0; i < 2*nVars; i++ )
+            fprintf( pFile, " b%0*d=y%0*d_%0*d", nDigits2, i, nDigits, k, nDigits2, i );
+        for ( i = 0; i <= 2*nVars; i++ )
+            fprintf( pFile, " s%0*d=x%0*d_%0*d", nDigits2, i, nDigits, k+1, nDigits2, i );
+        fprintf( pFile, "\n" );
+    }
+    for ( i = 0; i < 2 * nVars; i++ )
+        fprintf( pFile, ".names x%0*d_%0*d m%0*d\n1 1\n", nDigits, k, nDigits2, i, nDigits2, i );
+    fprintf( pFile, ".end\n" ); 
+    fprintf( pFile, "\n" );
+    Abc_WriteAdder( pFile, 2*nVars );
+}
+void Abc_GenBooth( char * pFileName, int nVars )
+{
+    FILE * pFile;
+    assert( nVars > 0 );
+    pFile = fopen( pFileName, "w" );
+    fprintf( pFile, "# %d-bit signed Booth multiplier generated by ABC on %s\n", nVars, Extra_TimeStamp() );
+    Abc_WriteBooth( pFile, nVars );
+    fclose( pFile );
+}
+
+
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////