Adding bit-blasting of sqrt using non-restoring algorithm (Parhami, 2nd ed, p. 452)

3 files changed, 40 insertions, 3 deletions

diff --git a/src/base/wlc/wlc.h b/src/base/wlc/wlc.h
index 5dbf190c..27ce427a 100644
--- a/src/base/wlc/wlc.h
+++ b/src/base/wlc/wlc.h
@@ -214,6 +214,7 @@ struct Wlc_BstPar_t_
     int                    fAddOutputs;
     int                    fMulti;
     int                    fBooth;
+    int                    fNonRest;
     int                    fCla;
     int                    fNoCleanup;
     int                    fCreateMiter;
diff --git a/src/base/wlc/wlcBlast.c b/src/base/wlc/wlcBlast.c
index 1676d6d6..6eb5a5c4 100644
--- a/src/base/wlc/wlcBlast.c
+++ b/src/base/wlc/wlcBlast.c
@@ -773,6 +773,35 @@ void Wlc_BlastSqrt( Gia_Man_t * pNew, int * pNum, int nNum, Vec_Int_t * vTmp, Ve
     }
     Vec_IntReverseOrder( vRes );
 }
+void Wlc_BlastSqrtNR( Gia_Man_t * pNew, int * pNum, int nNum, Vec_Int_t * vTmp, Vec_Int_t * vRes )
+{
+    int * pSqr, * pRem, * pIn1;
+    int i, k, Carry = 1;
+    assert( nNum % 2 == 0 );
+    Vec_IntFill( vRes, nNum/2, 0 );
+    Vec_IntFill( vTmp, 2*nNum, 0 );
+    pSqr = Vec_IntArray( vRes );
+    pRem = Vec_IntArray( vTmp );
+    pIn1 = pRem + nNum;
+    for ( i = 0; i < nNum/2; i++ )
+    {
+        int SqrPrev = Carry;
+        assert( pIn1[0] == 0 );
+        for ( k = 1; k < i; k++ )
+            pIn1[k] = 0;
+        for ( k = i; k < 2*i; k++ )
+            pIn1[k] = pSqr[k-i];
+        pIn1[k++] = Abc_LitNot(Carry);
+        pIn1[k++] = 1;
+        assert( k == 2*i+2 );
+        pRem[2*i+0] = pNum[nNum-2*i-1];
+        pRem[2*i+1] = pNum[nNum-2*i-2];
+        for ( k = 2*i+1; k >= 0; k-- )
+            Wlc_BlastFullAdder( pNew, Gia_ManHashXor(pNew, SqrPrev, pIn1[k]), pRem[k], Carry, &Carry, &pRem[k] );
+        pSqr[i] = Carry;
+    }
+    Vec_IntReverseOrder( vRes );
+}
 void Wlc_IntInsert( Vec_Int_t * vProd, Vec_Int_t * vLevel, int Node, int Level )
 {
     int i;
@@ -1794,7 +1823,10 @@ Gia_Man_t * Wlc_NtkBitBlast( Wlc_Ntk_t * p, Wlc_BstPar_t * pParIn )
         {
             int * pArg0 = Wlc_VecLoadFanins( vTemp0, pFans0, nRange0, nRange0 + (nRange0 & 1), 0 );
             nRange0 += (nRange0 & 1);
-            Wlc_BlastSqrt( pNew, pArg0, nRange0, vTemp2, vRes );
+            if ( pPar->fNonRest )
+                Wlc_BlastSqrtNR( pNew, pArg0, nRange0, vTemp2, vRes );
+            else
+                Wlc_BlastSqrt( pNew, pArg0, nRange0, vTemp2, vRes );
             if ( nRange > Vec_IntSize(vRes) )
                 Vec_IntFillExtra( vRes, nRange, 0 );
             else
diff --git a/src/base/wlc/wlcCom.c b/src/base/wlc/wlcCom.c
index ac7f111d..58c5d2ac 100644
--- a/src/base/wlc/wlcCom.c
+++ b/src/base/wlc/wlcCom.c
@@ -1037,7 +1037,7 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
     Wlc_BstParDefault( pPar );
     pPar->nOutputRange = 2;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "ORAMcombadestnizvh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "ORAMcombqadestnizvh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -1097,6 +1097,9 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
         case 'b':
             pPar->fBooth ^= 1;
             break;
+        case 'q':
+            pPar->fNonRest ^= 1;
+            break;
         case 'a':
             pPar->fCla ^= 1;
             break;
@@ -1195,7 +1198,7 @@ int Abc_CommandBlast( Abc_Frame_t * pAbc, int argc, char ** argv )
     Abc_FrameUpdateGia( pAbc, pNew );
     return 0;
 usage:
-    Abc_Print( -2, "usage: %%blast [-ORAM num] [-combadestnizvh]\n" );
+    Abc_Print( -2, "usage: %%blast [-ORAM num] [-combqadestnizvh]\n" );
     Abc_Print( -2, "\t         performs bit-blasting of the word-level design\n" );
     Abc_Print( -2, "\t-O num : zero-based index of the first word-level PO to bit-blast [default = %d]\n", pPar->iOutput );
     Abc_Print( -2, "\t-R num : the total number of word-level POs to bit-blast [default = %d]\n",          pPar->nOutputRange );
@@ -1205,6 +1208,7 @@ usage:
     Abc_Print( -2, "\t-o     : toggle using additional POs on the word-level boundaries [default = %s]\n", pPar->fAddOutputs? "yes": "no" );
     Abc_Print( -2, "\t-m     : toggle creating boxes for all multipliers in the design [default = %s]\n",  pPar->fMulti? "yes": "no" );
     Abc_Print( -2, "\t-b     : toggle generating radix-4 Booth multipliers [default = %s]\n",              pPar->fBooth? "yes": "no" );
+    Abc_Print( -2, "\t-q     : toggle generating non-restoring square root [default = %s]\n",              pPar->fNonRest? "yes": "no" );
     Abc_Print( -2, "\t-a     : toggle generating carry-look-ahead adder [default = %s]\n",                 pPar->fCla? "yes": "no" );
     Abc_Print( -2, "\t-d     : toggle creating dual-output multi-output miter [default = %s]\n",           pPar->fCreateMiter? "yes": "no" );
     Abc_Print( -2, "\t-e     : toggle creating miter with output word bits combined [default = %s]\n",     pPar->fCreateWordMiter? "yes": "no" );