[freetype2] master 7a81b63: Optimize Bézier bisections.

[Alexei Podtelezhnikov]

branch: master
commit 7a81b63abc2b3da0d7f0950f69377d2b3f54b0fb
Author: Alexei Podtelezhnikov <address@hidden>
Commit: Alexei Podtelezhnikov <address@hidden>

    Optimize Bézier bisections.
    
    * src/raster/ftraster.c (Split_Conic, Split_Cubic): Use shifts and
    refactor.
    * src/smooth/ftgrays.c (gray_split_conic, gray_split_cubic): Ditto.
    * src/base/ftstroke.c (ft_conic_split, ft_cubic_split): Ditto.
    * src/base/ftbbox.c (cubic_peak): Use shifts.
---
 ChangeLog             | 10 +++++++++
 src/base/ftbbox.c     | 12 +++++------
 src/base/ftstroke.c   | 56 ++++++++++++++++++++++++++++-----------------------
 src/raster/ftraster.c | 56 ++++++++++++++++++++++++++++-----------------------
 src/smooth/ftgrays.c  | 56 ++++++++++++++++++++++++++++-----------------------
 5 files changed, 109 insertions(+), 81 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 7919b5f..cae7fab 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,13 @@
+2019-04-25  Alexei Podtelezhnikov  <address@hidden>
+
+       Optimize Bézier bisections.
+
+       * src/raster/ftraster.c (Split_Conic, Split_Cubic): Use shifts and
+       refactor.
+       * src/smooth/ftgrays.c (gray_split_conic, gray_split_cubic): Ditto.
+       * src/base/ftstroke.c (ft_conic_split, ft_cubic_split): Ditto.
+       * src/base/ftbbox.c (cubic_peak): Use shifts.
+
 2019-04-23  Werner Lemberg  <address@hidden>
 
        * src/sfnt/ttcmap.c (tt_cmap12_next): Remove dead code.
diff --git a/src/base/ftbbox.c b/src/base/ftbbox.c
index 0b04fde..a0b2c46 100644
--- a/src/base/ftbbox.c
+++ b/src/base/ftbbox.c
@@ -319,9 +319,9 @@
         q2 = q2 + q1;
         q4 = q4 + q3;
         q3 = q3 + q2;
-        q4 = ( q4 + q3 ) / 8;
-        q3 = q3 / 4;
-        q2 = q2 / 2;
+        q4 = ( q4 + q3 ) >> 3;
+        q3 = q3 >> 2;
+        q2 = q2 >> 1;
       }
       else                     /* second half */
       {
@@ -330,9 +330,9 @@
         q3 = q3 + q4;
         q1 = q1 + q2;
         q2 = q2 + q3;
-        q1 = ( q1 + q2 ) / 8;
-        q2 = q2 / 4;
-        q3 = q3 / 2;
+        q1 = ( q1 + q2 ) >> 3;
+        q2 = q2 >> 2;
+        q3 = q3 >> 1;
       }
 
       /* check whether either end reached the maximum */
diff --git a/src/base/ftstroke.c b/src/base/ftstroke.c
index 826062c..1b2c0f6 100644
--- a/src/base/ftstroke.c
+++ b/src/base/ftstroke.c
@@ -86,16 +86,18 @@
 
 
     base[4].x = base[2].x;
-    b = base[1].x;
-    a = base[3].x = ( base[2].x + b ) / 2;
-    b = base[1].x = ( base[0].x + b ) / 2;
-    base[2].x = ( a + b ) / 2;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    base[3].x = b >> 1;
+    base[2].x = ( a + b ) >> 2;
+    base[1].x = a >> 1;
 
     base[4].y = base[2].y;
-    b = base[1].y;
-    a = base[3].y = ( base[2].y + b ) / 2;
-    b = base[1].y = ( base[0].y + b ) / 2;
-    base[2].y = ( a + b ) / 2;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    base[3].y = b >> 1;
+    base[2].y = ( a + b ) >> 2;
+    base[1].y = a >> 1;
   }
 
 
@@ -153,28 +155,32 @@
   static void
   ft_cubic_split( FT_Vector*  base )
   {
-    FT_Pos  a, b, c, d;
+    FT_Pos  a, b, c;
 
 
     base[6].x = base[3].x;
-    c = base[1].x;
-    d = base[2].x;
-    base[1].x = a = ( base[0].x + c ) / 2;
-    base[5].x = b = ( base[3].x + d ) / 2;
-    c = ( c + d ) / 2;
-    base[2].x = a = ( a + c ) / 2;
-    base[4].x = b = ( b + c ) / 2;
-    base[3].x = ( a + b ) / 2;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    c = base[2].x + base[3].x;
+    base[5].x = c >> 1;
+    c += b;
+    base[4].x = c >> 2;
+    base[1].x = a >> 1;
+    a += b;
+    base[2].x = a >> 2;
+    base[3].x = ( a + c ) >> 3;
 
     base[6].y = base[3].y;
-    c = base[1].y;
-    d = base[2].y;
-    base[1].y = a = ( base[0].y + c ) / 2;
-    base[5].y = b = ( base[3].y + d ) / 2;
-    c = ( c + d ) / 2;
-    base[2].y = a = ( a + c ) / 2;
-    base[4].y = b = ( b + c ) / 2;
-    base[3].y = ( a + b ) / 2;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    c = base[2].y + base[3].y;
+    base[5].y = c >> 1;
+    c += b;
+    base[4].y = c >> 2;
+    base[1].y = a >> 1;
+    a += b;
+    base[2].y = a >> 2;
+    base[3].y = ( a + c ) >> 3;
   }
 
 
diff --git a/src/raster/ftraster.c b/src/raster/ftraster.c
index 798a72d..2859113 100644
--- a/src/raster/ftraster.c
+++ b/src/raster/ftraster.c
@@ -914,16 +914,18 @@
 
 
     base[4].x = base[2].x;
-    b = base[1].x;
-    a = base[3].x = ( base[2].x + b ) / 2;
-    b = base[1].x = ( base[0].x + b ) / 2;
-    base[2].x = ( a + b ) / 2;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    base[3].x = b >> 1;
+    base[2].x = ( a + b ) >> 2;
+    base[1].x = a >> 1;
 
     base[4].y = base[2].y;
-    b = base[1].y;
-    a = base[3].y = ( base[2].y + b ) / 2;
-    b = base[1].y = ( base[0].y + b ) / 2;
-    base[2].y = ( a + b ) / 2;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    base[3].y = b >> 1;
+    base[2].y = ( a + b ) >> 2;
+    base[1].y = a >> 1;
 
     /* hand optimized.  gcc doesn't seem to be too good at common      */
     /* expression substitution and instruction scheduling ;-)          */
@@ -947,28 +949,32 @@
   static void
   Split_Cubic( TPoint*  base )
   {
-    Long  a, b, c, d;
+    Long  a, b, c;
 
 
     base[6].x = base[3].x;
-    c = base[1].x;
-    d = base[2].x;
-    base[1].x = a = ( base[0].x + c + 1 ) >> 1;
-    base[5].x = b = ( base[3].x + d + 1 ) >> 1;
-    c = ( c + d + 1 ) >> 1;
-    base[2].x = a = ( a + c + 1 ) >> 1;
-    base[4].x = b = ( b + c + 1 ) >> 1;
-    base[3].x = ( a + b + 1 ) >> 1;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    c = base[2].x + base[3].x;
+    base[5].x = c >> 1;
+    c += b;
+    base[4].x = c >> 2;
+    base[1].x = a >> 1;
+    a += b;
+    base[2].x = a >> 2;
+    base[3].x = ( a + c ) >> 3;
 
     base[6].y = base[3].y;
-    c = base[1].y;
-    d = base[2].y;
-    base[1].y = a = ( base[0].y + c + 1 ) >> 1;
-    base[5].y = b = ( base[3].y + d + 1 ) >> 1;
-    c = ( c + d + 1 ) >> 1;
-    base[2].y = a = ( a + c + 1 ) >> 1;
-    base[4].y = b = ( b + c + 1 ) >> 1;
-    base[3].y = ( a + b + 1 ) >> 1;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    c = base[2].y + base[3].y;
+    base[5].y = c >> 1;
+    c += b;
+    base[4].y = c >> 2;
+    base[1].y = a >> 1;
+    a += b;
+    base[2].y = a >> 2;
+    base[3].y = ( a + c ) >> 3;
   }
 
 
diff --git a/src/smooth/ftgrays.c b/src/smooth/ftgrays.c
index 20c6a34..82cd445 100644
--- a/src/smooth/ftgrays.c
+++ b/src/smooth/ftgrays.c
@@ -979,16 +979,18 @@ typedef ptrdiff_t  FT_PtrDist;
 
 
     base[4].x = base[2].x;
-    b = base[1].x;
-    a = base[3].x = ( base[2].x + b ) / 2;
-    b = base[1].x = ( base[0].x + b ) / 2;
-    base[2].x = ( a + b ) / 2;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    base[3].x = b >> 1;
+    base[2].x = ( a + b ) >> 2;
+    base[1].x = a >> 1;
 
     base[4].y = base[2].y;
-    b = base[1].y;
-    a = base[3].y = ( base[2].y + b ) / 2;
-    b = base[1].y = ( base[0].y + b ) / 2;
-    base[2].y = ( a + b ) / 2;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    base[3].y = b >> 1;
+    base[2].y = ( a + b ) >> 2;
+    base[1].y = a >> 1;
   }
 
 
@@ -1060,28 +1062,32 @@ typedef ptrdiff_t  FT_PtrDist;
   static void
   gray_split_cubic( FT_Vector*  base )
   {
-    TPos  a, b, c, d;
+    TPos  a, b, c;
 
 
     base[6].x = base[3].x;
-    c = base[1].x;
-    d = base[2].x;
-    base[1].x = a = ( base[0].x + c ) / 2;
-    base[5].x = b = ( base[3].x + d ) / 2;
-    c = ( c + d ) / 2;
-    base[2].x = a = ( a + c ) / 2;
-    base[4].x = b = ( b + c ) / 2;
-    base[3].x = ( a + b ) / 2;
+    a = base[0].x + base[1].x;
+    b = base[1].x + base[2].x;
+    c = base[2].x + base[3].x;
+    base[5].x = c >> 1;
+    c += b;
+    base[4].x = c >> 2;
+    base[1].x = a >> 1;
+    a += b;
+    base[2].x = a >> 2;
+    base[3].x = ( a + c ) >> 3;
 
     base[6].y = base[3].y;
-    c = base[1].y;
-    d = base[2].y;
-    base[1].y = a = ( base[0].y + c ) / 2;
-    base[5].y = b = ( base[3].y + d ) / 2;
-    c = ( c + d ) / 2;
-    base[2].y = a = ( a + c ) / 2;
-    base[4].y = b = ( b + c ) / 2;
-    base[3].y = ( a + b ) / 2;
+    a = base[0].y + base[1].y;
+    b = base[1].y + base[2].y;
+    c = base[2].y + base[3].y;
+    base[5].y = c >> 1;
+    c += b;
+    base[4].y = c >> 2;
+    base[1].y = a >> 1;
+    a += b;
+    base[2].y = a >> 2;
+    base[3].y = ( a + c ) >> 3;
   }