[freetype2] master-patch-ea68 97251fd5a: [base] Improve the matrix degeneracy check.

[Werner Lemberg]

branch: master-patch-ea68
commit 97251fd5aa2a90041cf4f397a5e887b8d60ab0c2
Author: Alexei Podtelezhnikov <apodtele@gmail.com>
Commit: Alexei Podtelezhnikov <apodtele@gmail.com>

    [base] Improve the matrix degeneracy check.
    
    Also fixes #1251.
    
    * src/base/ftcalc.c (FT_Matrix_Check): To avoid overflow, scale by shifting.
    * include/freetype/internal/ftcalc.h (FT_Matrix_Check): Update description.
---
 include/freetype/internal/ftcalc.h |  4 +--
 src/base/ftcalc.c                  | 70 +++++++++++++-------------------------
 2 files changed, 26 insertions(+), 48 deletions(-)

diff --git a/include/freetype/internal/ftcalc.h 
b/include/freetype/internal/ftcalc.h
index d1baa392b..d9aea2360 100644
--- a/include/freetype/internal/ftcalc.h
+++ b/include/freetype/internal/ftcalc.h
@@ -332,9 +332,9 @@ FT_BEGIN_HEADER
    * Based on geometric considerations we use the following inequality to
    * identify a degenerate matrix.
    *
-   *   50 * abs(xx*yy - xy*yx) < xx^2 + xy^2 + yx^2 + yy^2
+   *   32 * abs(xx*yy - xy*yx) < xx^2 + xy^2 + yx^2 + yy^2
    *
-   * Value 50 is heuristic.
+   * Value 32 is heuristic.
    */
   FT_BASE( FT_Bool )
   FT_Matrix_Check( const FT_Matrix*  matrix );
diff --git a/src/base/ftcalc.c b/src/base/ftcalc.c
index 442b08ddf..9e87abd09 100644
--- a/src/base/ftcalc.c
+++ b/src/base/ftcalc.c
@@ -749,65 +749,43 @@
   FT_BASE_DEF( FT_Bool )
   FT_Matrix_Check( const FT_Matrix*  matrix )
   {
-    FT_Matrix  m;
-    FT_Fixed   val[4];
-    FT_Fixed   nonzero_minval, maxval;
-    FT_Fixed   temp1, temp2;
-    FT_UInt    i;
+    FT_Fixed  xx, xy, yx, yy;
+    FT_Fixed  val;
+    FT_Int    shift;
+    FT_ULong  temp1, temp2;
 
 
     if ( !matrix )
       return 0;
 
-    val[0] = FT_ABS( matrix->xx );
-    val[1] = FT_ABS( matrix->xy );
-    val[2] = FT_ABS( matrix->yx );
-    val[3] = FT_ABS( matrix->yy );
-
-    /*
-     * To avoid overflow, we ensure that each value is not larger than
-     *
-     *   int(sqrt(2^31 / 4)) = 23170  ;
-     *
-     * we also check that no value becomes zero if we have to scale.
-     */
-
-    maxval         = 0;
-    nonzero_minval = FT_LONG_MAX;
+    xx  = matrix->xx;
+    xy  = matrix->xy;
+    yx  = matrix->yx;
+    yy  = matrix->yy;
+    val = FT_ABS( xx ) | FT_ABS( xy ) | FT_ABS( yx ) | FT_ABS( yy );
 
-    for ( i = 0; i < 4; i++ )
-    {
-      if ( val[i] > maxval )
-        maxval = val[i];
-      if ( val[i] && val[i] < nonzero_minval )
-        nonzero_minval = val[i];
-    }
-
-    /* we only handle 32bit values */
-    if ( maxval > 0x7FFFFFFFL )
+    /* we only handle non-zero 32-bit values */
+    if ( !val || val > 0x7FFFFFFFL )
       return 0;
 
-    if ( maxval > 23170 )
-    {
-      FT_Fixed  scale = FT_DivFix( maxval, 23170 );
-
+    /* Scale matrix to avoid the temp1 overflow, which is */
+    /* more stringent than avoiding the temp2 overflow.   */
 
-      if ( !FT_DivFix( nonzero_minval, scale ) )
-        return 0;    /* value range too large */
+    shift = FT_MSB( val ) - 12;
 
-      m.xx = FT_DivFix( matrix->xx, scale );
-      m.xy = FT_DivFix( matrix->xy, scale );
-      m.yx = FT_DivFix( matrix->yx, scale );
-      m.yy = FT_DivFix( matrix->yy, scale );
+    if ( shift > 0 )
+    {
+      xx >>= shift;
+      xy >>= shift;
+      yx >>= shift;
+      yy >>= shift;
     }
-    else
-      m = *matrix;
 
-    temp1 = FT_ABS( m.xx * m.yy - m.xy * m.yx );
-    temp2 = m.xx * m.xx + m.xy * m.xy + m.yx * m.yx + m.yy * m.yy;
+    temp1 = 32U * (FT_ULong)FT_ABS( xx * yy - xy * yx );
+    temp2 = (FT_ULong)( xx * xx ) + (FT_ULong)( xy * xy ) +
+            (FT_ULong)( yx * yx ) + (FT_ULong)( yy * yy );
 
-    if ( temp1 == 0         ||
-         temp2 / temp1 > 50 )
+    if ( temp1 <= temp2 )
       return 0;
 
     return 1;