Commit d7383b7b86bf9d8e37d73d2ac1a7fec54d8f746e

Alexei Podtelezhnikov 2012-12-20T01:03:22

[base] Improve trigonometric core. FreeType used to rely on a 24-step iteration CORDIC algorithm to calculate trigonometric functions and rotate vectors. It turns out that once the vector is in the right half-plane, the initial rotation by 63 degrees is not necessary. The algorithm is perfectly capable to converge to any angle starting from the second 45 degree rotation. This patch removes the first rotation and makes it a 23-step CORDIC algorithm. * src/base/fttrigon.c (FT_TRIG_SCALE, FT_TRIG_COSCALE): Update macro values. (ft_trig_pseudo_rotate, ft_trig_pseudo_polarize): Remove initial rotation.

diff --git a/ChangeLog b/ChangeLog
index 0fa5058..ad867b8 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,20 @@
+2012-12-20  Alexei Podtelezhnikov  <apodtele@gmail.com>
+
+	[base] Improve trigonometric core.
+
+	FreeType used to rely on a 24-step iteration CORDIC algorithm to
+	calculate trigonometric functions and rotate vectors. It turns out
+	that once the vector is in the right half-plane, the initial rotation
+	by 63 degrees is not necessary. The algorithm is perfectly capable
+	to converge to any angle starting from the second 45 degree rotation.
+	This patch removes the first rotation and makes it a 23-step CORDIC
+	algorithm.
+
+	* src/base/fttrigon.c (FT_TRIG_SCALE, FT_TRIG_COSCALE): Update macro
+	values.
+	(ft_trig_pseudo_rotate, ft_trig_pseudo_polarize): Remove initial
+	rotation.
+
 2012-12-19  Werner Lemberg  <wl@gnu.org>
 
 	* src/base/ftobjs.c (ft_property_do): Fix compiler warning.
diff --git a/src/base/fttrigon.c b/src/base/fttrigon.c
index 4aeb565..5239538 100644
--- a/src/base/fttrigon.c
+++ b/src/base/fttrigon.c
@@ -26,23 +26,23 @@
 #endif
 
 
-  /* the following is 0.2715717684432231 * 2^30 */
-#define FT_TRIG_COSCALE  0x11616E8EUL
+  /* the Cordic shrink factor 0.607252935008887 * 2^32 */
+#define FT_TRIG_SCALE    0x9B74EDA8UL
+
+  /* the following is 0.607252935008887 * 2^30 */
+#define FT_TRIG_COSCALE  0x26DD3B6AUL
 
   /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
 #define FT_TRIG_MAX_ITERS  23
 
   static const FT_Fixed
-  ft_trig_arctan_table[24] =
+  ft_trig_arctan_table[23] =
   {
-    4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L,
-    58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
+    2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L, 58666L,
+    29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
     57L, 29L, 14L, 7L, 4L, 2L, 1L
   };
 
-  /* the Cordic shrink factor, multiplied by 2^32 */
-#define FT_TRIG_SCALE    1166391864UL  /* 0x4585BA38UL */
-
 
 #ifdef FT_LONG64
 
@@ -214,25 +214,9 @@
       theta -= FT_ANGLE_PI;
     }
 
-    /* Initial pseudorotation, with left shift */
     arctanptr = ft_trig_arctan_table;
 
-    if ( theta < 0 )
-    {
-      xtemp  = x + ( y << 1 );
-      y      = y - ( x << 1 );
-      x      = xtemp;
-      theta += *arctanptr++;
-    }
-    else
-    {
-      xtemp  = x - ( y << 1 );
-      y      = y + ( x << 1 );
-      x      = xtemp;
-      theta -= *arctanptr++;
-    }
-
-    /* Subsequent pseudorotations, with right shifts */
+    /* Pseudorotations, with right shifts */
     i = 0;
     do
     {
@@ -283,22 +267,7 @@
 
     arctanptr = ft_trig_arctan_table;
 
-    if ( y > 0 )
-    {
-      xtemp  = x + ( y << 1 );
-      y      = y - ( x << 1 );
-      x      = xtemp;
-      theta += *arctanptr++;
-    }
-    else
-    {
-      xtemp  = x - ( y << 1 );
-      y      = y + ( x << 1 );
-      x      = xtemp;
-      theta -= *arctanptr++;
-    }
-
-    /* Subsequent pseudorotations, with right shifts */
+    /* Pseudorotations, with right shifts */
     i = 0;
     do
     {