[freetype2] sqrt_fixed 95b0fe2a6 1/2: [base] Reintroduce `FT_SqrtFixed`.

[Werner Lemberg]

branch: sqrt_fixed
commit 95b0fe2a6dff256b4e0670e7ee6c72dc51aac968
Author: Alexei Podtelezhnikov <apodtele@gmail.com>
Commit: Alexei Podtelezhnikov <apodtele@gmail.com>

    [base] Reintroduce `FT_SqrtFixed`.
    
    The general square root calculations are not necessary in FreeType.
    For vector normalization or length, FreeType uses special functions.
    It is, however, required in the legacy CFF specifications.
    
    * src/base/ftcalc.c (FT_SqrtFixed): New function that uses either
    Babylonian or bit-wise algorithm, whichever is faster for the given
    situation.
    * include/freetype/internal/ftcalc.h (FT_SqrtFixed): Declare it.
---
 include/freetype/internal/ftcalc.h |  7 ++--
 src/base/ftcalc.c                  | 71 ++++++++++++++++++++++++++++----------
 2 files changed, 54 insertions(+), 24 deletions(-)

diff --git a/include/freetype/internal/ftcalc.h 
b/include/freetype/internal/ftcalc.h
index fa5e4050f..b987ccb20 100644
--- a/include/freetype/internal/ftcalc.h
+++ b/include/freetype/internal/ftcalc.h
@@ -489,8 +489,6 @@ FT_BEGIN_HEADER
             FT_Fixed  y );
 
 
-#if 0
-
   /**************************************************************************
    *
    * @function:
@@ -507,13 +505,12 @@ FT_BEGIN_HEADER
    *   The result of 'sqrt(x)'.
    *
    * @note:
-   *   This function is not very fast.
+   *   This function is slow and should be avoided.  Consider `FT_Hypot` or
+   *   `FT_Vector_NormLen' instead.
    */
   FT_BASE( FT_UInt32 )
   FT_SqrtFixed( FT_UInt32  x );
 
-#endif /* 0 */
-
 
 #define INT_TO_F26DOT6( x )    ( (FT_Long)(x) * 64  )    /* << 6  */
 #define INT_TO_F2DOT14( x )    ( (FT_Long)(x) * 16384 )  /* << 14 */
diff --git a/src/base/ftcalc.c b/src/base/ftcalc.c
index 0b915992a..a5bd61491 100644
--- a/src/base/ftcalc.c
+++ b/src/base/ftcalc.c
@@ -913,38 +913,71 @@
   }
 
 
-#if 0
-
   /* documentation is in ftcalc.h */
 
-  /* Algorithm and code by Christophe Meessen (1993) */ 
-  /* with overflow fixed.                            */
   FT_BASE_DEF( FT_UInt32 )
   FT_SqrtFixed( FT_UInt32  v )
   {
-    FT_UInt32  r = v >> 1;
-    FT_UInt32  q = ( v & 1 ) << 15;
-    FT_UInt32  b = 0x20000000;
-    FT_UInt32  t;
+    if ( v == 0 )
+      return 0;
 
+#ifndef FT_INT64
 
-    do
+    /* Algorithm by Christophe Meessen (1993) with overflow fixed and    */
+    /* rounding added.  Any unsigned fixed 16.16 argument is acceptable. */
+    /* However, this algorithm is slower than the Babylonian method with */
+    /* a good initial guess. We only use it for large 32-bit values when */
+    /* 64-bit computations are not desirable.                            */
+    else if ( v > 0x10000U )
     {
-      t = q + b;
-      if ( r >= t )
+      FT_UInt32  r = v >> 1;
+      FT_UInt32  q = ( v & 1 ) << 15;
+      FT_UInt32  b = 0x20000000;
+      FT_UInt32  t;
+
+
+      do
       {
-        r -= t;
-        q  = t + b;  /* equivalent to q += 2*b */
+        t = q + b;
+        if ( r >= t )
+        {
+          r -= t;
+          q  = t + b;  /* equivalent to q += 2*b */
+        }
+        r <<= 1;
+        b >>= 1;
       }
-      r <<= 1;
-      b >>= 1;
+      while ( b > 0x10 );  /* exactly 25 cycles */
+
+      return ( q + 0x40 ) >> 7;
     }
-    while ( b > 0x20 );
+    else
+    {
+      FT_UInt32  r = ( v << 16 ) - 1;
 
-    return q >> 7;
-  }
+#else /* FT_INT64 */
 
-#endif /* 0 */
+    else
+    {
+      FT_UInt64  r = ( (FT_UInt64)v << 16 ) - 1;
+
+#endif /* FT_INT64 */
+
+      FT_UInt32  q = 1 << ( ( 17 + FT_MSB( v ) ) >> 1 );
+      FT_UInt32  t;
+
+
+      /* Babylonian method with rounded-up division */
+      do
+      {
+        t = q;
+        q = ( t + (FT_UInt32)( r / t ) + 1 ) >> 1;
+      }
+      while ( q != t );  /* less than 6 cycles */
+
+      return q;
+    }
+  }
 
 
   /* documentation is in ftcalc.h */