Update freetype to latest version of ASOP.

src/base/fttrigon.c

 /***************************************************************************/
 /*                                                                         */
 /*  fttrigon.c                                                             */
 /*                                                                         */
 /*    FreeType trigonometric functions (body).                             */
 /*                                                                         */
-/*  Copyright 2001, 2002, 2003, 2004, 2005 by                              */
+/*  Copyright 2001-2005, 2012-2013 by                                      */
 /*  David Turner, Robert Wilhelm, and Werner Lemberg.                      */
 /*                                                                         */
 /*  This file is part of the FreeType project, and may only be used,       */
 /*  modified, and distributed under the terms of the FreeType project      */
 /*  license, LICENSE.TXT.  By continuing to use, modify, or distribute     */
 /*  this file you indicate that you have read the license and              */
 /*  understand and accept it fully.                                        */
 /*                                                                         */
 /***************************************************************************/
 
+  /*************************************************************************/
+  /*                                                                       */
+  /* This is a fixed-point CORDIC implementation of trigonometric          */
+  /* functions as well as transformations between Cartesian and polar      */
+  /* coordinates.  The angles are represented as 16.16 fixed-point values  */
+  /* in degrees, i.e., the angular resolution is 2^-16 degrees.  Note that */
+  /* only vectors longer than 2^16*180/pi (or at least 22 bits) on a       */
+  /* discrete Cartesian grid can have the same or better angular           */
+  /* resolution.  Therefore, to maintain this precision, some functions    */
+  /* require an interim upscaling of the vectors, whereas others operate   */
+  /* with 24-bit long vectors directly.                                    */
+  /*                                                                       */
+  /*************************************************************************/
 
 #include <ft2build.h>
 #include FT_INTERNAL_OBJECTS_H
+#include FT_INTERNAL_CALC_H
 #include FT_TRIGONOMETRY_H
 
 
-  /* the following is 0.2715717684432231 * 2^30 */
-#define FT_TRIG_COSCALE  0x11616E8EUL
+  /* the Cordic shrink factor 0.858785336480436 * 2^32 */
+#define FT_TRIG_SCALE      0xDBD95B16UL
+
+  /* the highest bit in overflow-safe vector components, */
+  /* MSB of 0.858785336480436 * sqrt(0.5) * 2^30         */
+#define FT_TRIG_SAFE_MSB   29
 
   /* 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[] =
   {
-    4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L,
-    58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
+    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    1166391785UL  /* 0x4585BA38UL */
 
-
-#ifdef FT_CONFIG_HAS_INT64
+#ifdef FT_LONG64
 
   /* multiply a given value by the CORDIC shrink factor */
   static FT_Fixed
   ft_trig_downscale( FT_Fixed  val )
   {
     FT_Fixed  s;
     FT_Int64  v;
 
 
     s   = val;
-    val = ( val >= 0 ) ? val : -val;
+    val = FT_ABS( val );
 
     v   = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL;
     val = (FT_Fixed)( v >> 32 );
 
     return ( s >= 0 ) ? val : -val;
   }
 
-#else /* !FT_CONFIG_HAS_INT64 */
+#else /* !FT_LONG64 */
 
   /* multiply a given value by the CORDIC shrink factor */
   static FT_Fixed
   ft_trig_downscale( FT_Fixed  val )
   {
     FT_Fixed   s;
     FT_UInt32  v1, v2, k1, k2, hi, lo1, lo2, lo3;
 
 
     s   = val;
-    val = ( val >= 0 ) ? val : -val;
+    val = FT_ABS( val );
 
     v1 = (FT_UInt32)val >> 16;
-    v2 = (FT_UInt32)(val & 0xFFFFL);
+    v2 = (FT_UInt32)( val & 0xFFFFL );
 
-    k1 = (FT_UInt32)FT_TRIG_SCALE >> 16;       /* constant */
-    k2 = (FT_UInt32)(FT_TRIG_SCALE & 0xFFFFL);   /* constant */
+    k1 = (FT_UInt32)FT_TRIG_SCALE >> 16;           /* constant */
+    k2 = (FT_UInt32)( FT_TRIG_SCALE & 0xFFFFL );   /* constant */
 
     hi   = k1 * v1;
     lo1  = k1 * v2 + k2 * v1;       /* can't overflow */
 
     lo2  = ( k2 * v2 ) >> 16;
-    lo3  = ( lo1 >= lo2 ) ? lo1 : lo2;
+    lo3  = FT_MAX( lo1, lo2 );
     lo1 += lo2;
 
     hi  += lo1 >> 16;
     if ( lo1 < lo3 )
       hi += (FT_UInt32)0x10000UL;
 
     val  = (FT_Fixed)hi;
 
     return ( s >= 0 ) ? val : -val;
   }
 
-#endif /* !FT_CONFIG_HAS_INT64 */
+#endif /* !FT_LONG64 */
 
 
   static FT_Int
   ft_trig_prenorm( FT_Vector*  vec )
   {
-    FT_Fixed  x, y, z;
-    FT_Int    shift;
+    FT_Pos  x, y;
+    FT_Int  shift;
 
 
     x = vec->x;
     y = vec->y;
 
-    z     = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
-    shift = 0;
+    shift = FT_MSB( FT_ABS( x ) | FT_ABS( y ) );
 
-#if 1
-    /* determine msb bit index in `shift' */
-    if ( z >= ( 1L << 16 ) )
+    if ( shift <= FT_TRIG_SAFE_MSB )
     {
-      z     >>= 16;
-      shift  += 16;
-    }
-    if ( z >= ( 1L << 8 ) )
-    {
-      z     >>= 8;
-      shift  += 8;
-    }
-    if ( z >= ( 1L << 4 ) )
-    {
-      z     >>= 4;
-      shift  += 4;
-    }
-    if ( z >= ( 1L << 2 ) )
-    {
-      z     >>= 2;
-      shift  += 2;
-    }
-    if ( z >= ( 1L << 1 ) )
-    {
-      z    >>= 1;
-      shift += 1;
-    }
-
-    if ( shift <= 27 )
-    {
-      shift  = 27 - shift;
-      vec->x = x << shift;
-      vec->y = y << shift;
+      shift  = FT_TRIG_SAFE_MSB - shift;
+      vec->x = (FT_Pos)( (FT_ULong)x << shift );
+      vec->y = (FT_Pos)( (FT_ULong)y << shift );
     }
     else
     {
-      shift -= 27;
+      shift -= FT_TRIG_SAFE_MSB;
       vec->x = x >> shift;
       vec->y = y >> shift;
       shift  = -shift;
     }
 
-#else /* 0 */
-
-    if ( z < ( 1L << 27 ) )
-    {
-      do
-      {
-        shift++;
-        z <<= 1;
-      } while ( z < ( 1L << 27 ) );
-      vec->x = x << shift;
-      vec->y = y << shift;
-    }
-    else if ( z > ( 1L << 28 ) )
-    {
-      do
-      {
-        shift++;
-        z >>= 1;
-      } while ( z > ( 1L << 28 ) );
-
-      vec->x = x >> shift;
-      vec->y = y >> shift;
-      shift  = -shift;
-    }
-
-#endif /* 0 */
-
     return shift;
   }
 
 
   static void
   ft_trig_pseudo_rotate( FT_Vector*  vec,
                          FT_Angle    theta )
   {
     FT_Int           i;
-    FT_Fixed         x, y, xtemp;
+    FT_Fixed         x, y, xtemp, b;
     const FT_Fixed  *arctanptr;
 
 
     x = vec->x;
     y = vec->y;
 
-    /* Get angle between -90 and 90 degrees */
-    while ( theta <= -FT_ANGLE_PI2 )
+    /* Rotate inside [-PI/4,PI/4] sector */
+    while ( theta < -FT_ANGLE_PI4 )
     {
-      x = -x;
-      y = -y;
-      theta += FT_ANGLE_PI;
+      xtemp  =  y;
+      y      = -x;
+      x      =  xtemp;
+      theta +=  FT_ANGLE_PI2;
     }
 
-    while ( theta > FT_ANGLE_PI2 )
+    while ( theta > FT_ANGLE_PI4 )
     {
-      x = -x;
-      y = -y;
-      theta -= FT_ANGLE_PI;
+      xtemp  = -y;
+      y      =  x;
+      x      =  xtemp;
+      theta -=  FT_ANGLE_PI2;
     }
 
-    /* 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 */
-    i = 0;
-    do
+    /* Pseudorotations, with right shifts */
+    for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
     {
       if ( theta < 0 )
       {
-        xtemp  = x + ( y >> i );
-        y      = y - ( x >> i );
+        xtemp  = x + ( ( y + b ) >> i );
+        y      = y - ( ( x + b ) >> i );
         x      = xtemp;
         theta += *arctanptr++;
       }
       else
       {
-        xtemp  = x - ( y >> i );
-        y      = y + ( x >> i );
+        xtemp  = x - ( ( y + b ) >> i );
+        y      = y + ( ( x + b ) >> i );
         x      = xtemp;
         theta -= *arctanptr++;
       }
-    } while ( ++i < FT_TRIG_MAX_ITERS );
+    }
 
     vec->x = x;
     vec->y = y;
   }
 
 
   static void
   ft_trig_pseudo_polarize( FT_Vector*  vec )
   {
-    FT_Fixed         theta;
-    FT_Fixed         yi, i;
-    FT_Fixed         x, y;
+    FT_Angle         theta;
+    FT_Int           i;
+    FT_Fixed         x, y, xtemp, b;
     const FT_Fixed  *arctanptr;
 
 
     x = vec->x;
     y = vec->y;
 
-    /* Get the vector into the right half plane */
-    theta = 0;
-    if ( x < 0 )
+    /* Get the vector into [-PI/4,PI/4] sector */
+    if ( y > x )
     {
-      x = -x;
-      y = -y;
-      theta = 2 * FT_ANGLE_PI2;
+      if ( y > -x )
+      {
+        theta =  FT_ANGLE_PI2;
+        xtemp =  y;
+        y     = -x;
+        x     =  xtemp;
+      }
+      else
+      {
+        theta =  y > 0 ? FT_ANGLE_PI : -FT_ANGLE_PI;
+        x     = -x;
+        y     = -y;
+      }
     }
-
-    if ( y > 0 )
-      theta = - theta;
+    else
+    {
+      if ( y < -x )
+      {
+        theta = -FT_ANGLE_PI2;
+        xtemp = -y;
+        y     =  x;
+        x     =  xtemp;
+      }
+      else
+      {
+        theta = 0;
+      }
+    }
 
     arctanptr = ft_trig_arctan_table;
 
-    if ( y < 0 )
+    /* Pseudorotations, with right shifts */
+    for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
     {
-      /* Rotate positive */
-      yi     = y + ( x << 1 );
-      x      = x - ( y << 1 );
-      y      = yi;
-      theta -= *arctanptr++;  /* Subtract angle */
-    }
-    else
-    {
-      /* Rotate negative */
-      yi     = y - ( x << 1 );
-      x      = x + ( y << 1 );
-      y      = yi;
-      theta += *arctanptr++;  /* Add angle */
-    }
-
-    i = 0;
-    do
-    {
-      if ( y < 0 )
+      if ( y > 0 )
       {
-        /* Rotate positive */
-        yi     = y + ( x >> i );
-        x      = x - ( y >> i );
-        y      = yi;
-        theta -= *arctanptr++;
+        xtemp  = x + ( ( y + b ) >> i );
+        y      = y - ( ( x + b ) >> i );
+        x      = xtemp;
+        theta += *arctanptr++;
       }
       else
       {
-        /* Rotate negative */
-        yi     = y - ( x >> i );
-        x      = x + ( y >> i );
-        y      = yi;
-        theta += *arctanptr++;
+        xtemp  = x - ( ( y + b ) >> i );
+        y      = y + ( ( x + b ) >> i );
+        x      = xtemp;
+        theta -= *arctanptr++;
       }
-    } while ( ++i < FT_TRIG_MAX_ITERS );
+    }
 
     /* round theta */
     if ( theta >= 0 )
       theta = FT_PAD_ROUND( theta, 32 );
     else
       theta = -FT_PAD_ROUND( -theta, 32 );
 
     vec->x = x;
     vec->y = theta;
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( FT_Fixed )
   FT_Cos( FT_Angle  angle )
   {
     FT_Vector  v;
 
 
-    v.x = FT_TRIG_COSCALE >> 2;
+    v.x = FT_TRIG_SCALE >> 8;
     v.y = 0;
     ft_trig_pseudo_rotate( &v, angle );
 
-    return v.x / ( 1 << 12 );
+    return ( v.x + 0x80L ) >> 8;
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( FT_Fixed )
   FT_Sin( FT_Angle  angle )
   {
     return FT_Cos( FT_ANGLE_PI2 - angle );
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( FT_Fixed )
   FT_Tan( FT_Angle  angle )
   {
     FT_Vector  v;
 
 
-    v.x = FT_TRIG_COSCALE >> 2;
+    v.x = FT_TRIG_SCALE >> 8;
     v.y = 0;
     ft_trig_pseudo_rotate( &v, angle );
 
     return FT_DivFix( v.y, v.x );
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( FT_Angle )
@@ skipping 14 matching lines @@
     return v.y;
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( void )
   FT_Vector_Unit( FT_Vector*  vec,
                   FT_Angle    angle )
   {
-    vec->x = FT_TRIG_COSCALE >> 2;
+    vec->x = FT_TRIG_SCALE >> 8;
     vec->y = 0;
     ft_trig_pseudo_rotate( vec, angle );
-    vec->x >>= 12;
-    vec->y >>= 12;
+    vec->x = ( vec->x + 0x80L ) >> 8;
+    vec->y = ( vec->y + 0x80L ) >> 8;
   }
 
 
   /* these macros return 0 for positive numbers,
      and -1 for negative ones */
 #define FT_SIGN_LONG( x )   ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
 #define FT_SIGN_INT( x )    ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
 #define FT_SIGN_INT32( x )  ( (x) >> 31 )
 #define FT_SIGN_INT16( x )  ( (x) >> 15 )
 
@@ skipping 22 matching lines @@
       {
         FT_Int32  half = (FT_Int32)1L << ( shift - 1 );
 
 
         vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
         vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
       }
       else
       {
         shift  = -shift;
-        vec->x = v.x << shift;
-        vec->y = v.y << shift;
+        vec->x = (FT_Pos)( (FT_ULong)v.x << shift );
+        vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
       }
     }
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( FT_Fixed )
   FT_Vector_Length( FT_Vector*  vec )
   {
     FT_Int     shift;
     FT_Vector  v;
 
 
     v = *vec;
 
     /* handle trivial cases */
     if ( v.x == 0 )
     {
-      return ( v.y >= 0 ) ? v.y : -v.y;
+      return FT_ABS( v.y );
     }
     else if ( v.y == 0 )
     {
-      return ( v.x >= 0 ) ? v.x : -v.x;
+      return FT_ABS( v.x );
     }
 
     /* general case */
     shift = ft_trig_prenorm( &v );
     ft_trig_pseudo_polarize( &v );
 
     v.x = ft_trig_downscale( v.x );
 
     if ( shift > 0 )
       return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift;
 
-    return v.x << -shift;
+    return (FT_Fixed)( (FT_UInt32)v.x << -shift );
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( void )
   FT_Vector_Polarize( FT_Vector*  vec,
                       FT_Fixed   *length,
                       FT_Angle   *angle )
   {
     FT_Int     shift;
     FT_Vector  v;
 
 
     v = *vec;
 
     if ( v.x == 0 && v.y == 0 )
       return;
 
     shift = ft_trig_prenorm( &v );
     ft_trig_pseudo_polarize( &v );
 
     v.x = ft_trig_downscale( v.x );
 
-    *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
+    *length = ( shift >= 0 ) ?                      ( v.x >>  shift )
+                             : (FT_Fixed)( (FT_UInt32)v.x << -shift );
     *angle  = v.y;
   }
 
 
   /* documentation is in fttrigon.h */
 
   FT_EXPORT_DEF( void )
   FT_Vector_From_Polar( FT_Vector*  vec,
                         FT_Fixed    length,
                         FT_Angle    angle )
@@ skipping 19 matching lines @@
       delta += FT_ANGLE_2PI;
 
     if ( delta > FT_ANGLE_PI )
       delta -= FT_ANGLE_2PI;
 
     return delta;
   }
 
 
 /* END */