fttrigon.c File Reference

#include <ft2build.h>

Include dependency graph for fttrigon.c:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	FT_TRIG_SCALE   0xDBD95B16UL
#define	FT_TRIG_SAFE_MSB   29
#define	FT_TRIG_MAX_ITERS   23
#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 )

Functions
static FT_Fixed	ft_trig_downscale (FT_Fixed val)
static FT_Int	ft_trig_prenorm (FT_Vector *vec)
static void	ft_trig_pseudo_rotate (FT_Vector *vec, FT_Angle theta)
static void	ft_trig_pseudo_polarize (FT_Vector *vec)
	FT_Cos (FT_Angle angle)
	FT_Sin (FT_Angle angle)
	FT_Tan (FT_Angle angle)
	FT_Atan2 (FT_Fixed dx, FT_Fixed dy)
	FT_Vector_Unit (FT_Vector *vec, FT_Angle angle)
	FT_Vector_Rotate (FT_Vector *vec, FT_Angle angle)
	FT_Vector_Length (FT_Vector *vec)
	FT_Vector_Polarize (FT_Vector *vec, FT_Fixed *length, FT_Angle *angle)
	FT_Vector_From_Polar (FT_Vector *vec, FT_Fixed length, FT_Angle angle)
	FT_Angle_Diff (FT_Angle angle1, FT_Angle angle2)

Variables
static const FT_Angle	ft_trig_arctan_table []

Macro Definition Documentation

FT_SIGN_INT

#define FT_SIGN_INT

(

x

)

( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )

Definition at line 378 of file fttrigon.c.

FT_SIGN_INT16

#define FT_SIGN_INT16

(

x

)

( (x) >> 15 )

Definition at line 380 of file fttrigon.c.

FT_SIGN_INT32

#define FT_SIGN_INT32

(

x

)

( (x) >> 31 )

Definition at line 379 of file fttrigon.c.

FT_SIGN_LONG

#define FT_SIGN_LONG

(

x

)

( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )

Definition at line 377 of file fttrigon.c.

FT_TRIG_MAX_ITERS

#define FT_TRIG_MAX_ITERS   23

Definition at line 46 of file fttrigon.c.

FT_TRIG_SAFE_MSB

#define FT_TRIG_SAFE_MSB   29

Definition at line 43 of file fttrigon.c.

FT_TRIG_SCALE

#define FT_TRIG_SCALE   0xDBD95B16UL

Definition at line 39 of file fttrigon.c.

Function Documentation

FT_Angle_Diff()

FT_Angle_Diff	(	FT_Angle	angle1,
		FT_Angle	angle2
	)

Definition at line 510 of file fttrigon.c.

  {
    FT_Angle  delta = angle2 - angle1;
 
 
    while ( delta <= -FT_ANGLE_PI )
      delta += FT_ANGLE_2PI;
 
    while ( delta > FT_ANGLE_PI )
      delta -= FT_ANGLE_2PI;
 
    return delta;
  }

Referenced by ft_angle_mean(), ft_conic_is_small_enough(), ft_cubic_is_small_enough(), ft_stroker_arcto(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), FT_Stroker_EndSubPath(), ft_stroker_inside(), ft_stroker_outside(), and ft_stroker_process_corner().

FT_Atan2()

FT_Atan2	(	FT_Fixed	dx,
		FT_Fixed	dy
	)

Definition at line 340 of file fttrigon.c.

  {
    FT_Vector  v;
 
 
    if ( dx == 0 && dy == 0 )
      return 0;
 
    v.x = dx;
    v.y = dy;
    ft_trig_prenorm( &v );
    ft_trig_pseudo_polarize( &v );
 
    return v.y;
  }

Referenced by ft_conic_is_small_enough(), ft_cubic_is_small_enough(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), FT_Stroker_LineTo(), and test_atan2().

FT_Cos()

FT_Cos

(

FT_Angle

angle

)

Definition at line 298 of file fttrigon.c.

  {
    FT_Vector  v;
 
 
    FT_Vector_Unit( &v, angle );
 
    return v.x;
  }

Referenced by ft_stroke_border_arcto(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), ft_stroker_inside(), ft_stroker_outside(), and test_cos().

FT_Sin()

FT_Sin

(

FT_Angle

angle

)

Definition at line 312 of file fttrigon.c.

  {
    FT_Vector  v;
 
 
    FT_Vector_Unit( &v, angle );
 
    return v.y;
  }

Referenced by ft_stroke_border_arcto(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), ft_stroker_outside(), and test_sin().

FT_Tan()

FT_Tan

(

FT_Angle

angle

)

Definition at line 326 of file fttrigon.c.

  {
    FT_Vector  v;
 
 
    FT_Vector_Unit( &v, angle );
 
    return FT_DivFix( v.y, v.x );
  }

Referenced by ft_stroker_inside(), and test_tan().

ft_trig_downscale()

static FT_Fixed ft_trig_downscale ( FT_Fixed  val )

static

Definition at line 84 of file fttrigon.c.

  {
    FT_Int     s = 1;
    FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
 
 
    if ( val < 0 )
    {
       val = -val;
       s = -1;
    }
 
    lo1 = (FT_UInt32)val & 0x0000FFFFU;
    hi1 = (FT_UInt32)val >> 16;
    lo2 = FT_TRIG_SCALE & 0x0000FFFFU;
    hi2 = FT_TRIG_SCALE >> 16;
 
    lo = lo1 * lo2;
    i1 = lo1 * hi2;
    i2 = lo2 * hi1;
    hi = hi1 * hi2;
 
    /* Check carry overflow of i1 + i2 */
    i1 += i2;
    hi += (FT_UInt32)( i1 < i2 ) << 16;
 
    hi += i1 >> 16;
    i1  = i1 << 16;
 
    /* Check carry overflow of i1 + lo */
    lo += i1;
    hi += ( lo < i1 );
 
    /* 0x40000000 comes from regression analysis between true */
    /* and CORDIC hypotenuse, so it minimizes the error       */
 
    /* Check carry overflow of lo + 0x40000000 */
    lo += 0x40000000UL;
    hi += ( lo < 0x40000000UL );
 
    val = (FT_Fixed)hi;
 
    return s < 0 ? -val : val;
  }

Referenced by FT_Vector_Length(), FT_Vector_Polarize(), and FT_Vector_Rotate().

ft_trig_prenorm()

static FT_Int ft_trig_prenorm ( FT_Vector *  vec )

static

Definition at line 134 of file fttrigon.c.

  {
    FT_Pos  x, y;
    FT_Int  shift;
 
 
    x = vec->x;
    y = vec->y;
 
    shift = FT_MSB( (FT_UInt32)( FT_ABS( x ) | FT_ABS( y ) ) );
 
    if ( shift <= FT_TRIG_SAFE_MSB )
    {
      shift  = FT_TRIG_SAFE_MSB - shift;
      vec->x = (FT_Pos)( (FT_ULong)x << shift );
      vec->y = (FT_Pos)( (FT_ULong)y << shift );
    }
    else
    {
      shift -= FT_TRIG_SAFE_MSB;
      vec->x = x >> shift;
      vec->y = y >> shift;
      shift  = -shift;
    }
 
    return shift;
  }

Referenced by FT_Atan2(), FT_Vector_Length(), FT_Vector_Polarize(), and FT_Vector_Rotate().

ft_trig_pseudo_polarize()

static void ft_trig_pseudo_polarize ( FT_Vector *  vec )

static

Definition at line 219 of file fttrigon.c.

  {
    FT_Angle         theta;
    FT_Int           i;
    FT_Fixed         x, y, xtemp, b;
    const FT_Angle  *arctanptr;
 
 
    x = vec->x;
    y = vec->y;
 
    /* Get the vector into [-PI/4,PI/4] sector */
    if ( y > x )
    {
      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;
      }
    }
    else
    {
      if ( y < -x )
      {
        theta = -FT_ANGLE_PI2;
        xtemp = -y;
        y     =  x;
        x     =  xtemp;
      }
      else
      {
        theta = 0;
      }
    }
 
    arctanptr = ft_trig_arctan_table;
 
    /* Pseudorotations, with right shifts */
    for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
    {
      if ( y > 0 )
      {
        xtemp  = x + ( ( y + b ) >> i );
        y      = y - ( ( x + b ) >> i );
        x      = xtemp;
        theta += *arctanptr++;
      }
      else
      {
        xtemp  = x - ( ( y + b ) >> i );
        y      = y + ( ( x + b ) >> i );
        x      = xtemp;
        theta -= *arctanptr++;
      }
    }
 
    /* round theta to acknowledge its error that mostly comes */
    /* from accumulated rounding errors in the arctan table   */
    if ( theta >= 0 )
      theta = FT_PAD_ROUND( theta, 16 );
    else
      theta = -FT_PAD_ROUND( -theta, 16 );
 
    vec->x = x;
    vec->y = theta;
  }

Referenced by FT_Atan2(), FT_Vector_Length(), and FT_Vector_Polarize().

ft_trig_pseudo_rotate()

static void ft_trig_pseudo_rotate ( FT_Vector *  vec, FT_Angle  theta  )

static

Definition at line 164 of file fttrigon.c.

  {
    FT_Int           i;
    FT_Fixed         x, y, xtemp, b;
    const FT_Angle  *arctanptr;
 
 
    x = vec->x;
    y = vec->y;
 
    /* Rotate inside [-PI/4,PI/4] sector */
    while ( theta < -FT_ANGLE_PI4 )
    {
      xtemp  =  y;
      y      = -x;
      x      =  xtemp;
      theta +=  FT_ANGLE_PI2;
    }
 
    while ( theta > FT_ANGLE_PI4 )
    {
      xtemp  = -y;
      y      =  x;
      x      =  xtemp;
      theta -=  FT_ANGLE_PI2;
    }
 
    arctanptr = ft_trig_arctan_table;
 
    /* Pseudorotations, with right shifts */
    for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
    {
      if ( theta < 0 )
      {
        xtemp  = x + ( ( y + b ) >> i );
        y      = y - ( ( x + b ) >> i );
        x      = xtemp;
        theta += *arctanptr++;
      }
      else
      {
        xtemp  = x - ( ( y + b ) >> i );
        y      = y + ( ( x + b ) >> i );
        x      = xtemp;
        theta -= *arctanptr++;
      }
    }
 
    vec->x = x;
    vec->y = y;
  }

Referenced by FT_Vector_Rotate(), and FT_Vector_Unit().

FT_Vector_From_Polar()

FT_Vector_From_Polar	(	FT_Vector *	vec,
		FT_Fixed	length,
		FT_Angle	angle
	)

Definition at line 493 of file fttrigon.c.

  {
    if ( !vec )
      return;
 
    vec->x = length;
    vec->y = 0;
 
    FT_Vector_Rotate( vec, angle );
  }

Referenced by ft_stroke_border_arcto(), ft_stroker_cap(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), ft_stroker_inside(), FT_Stroker_LineTo(), ft_stroker_outside(), and ft_stroker_subpath_start().

FT_Vector_Length()

FT_Vector_Length

(

FT_Vector *

vec

)

Definition at line 426 of file fttrigon.c.

  {
    FT_Int     shift;
    FT_Vector  v;
 
 
    if ( !vec )
      return 0;
 
    v = *vec;
 
    /* handle trivial cases */
    if ( v.x == 0 )
    {
      return FT_ABS( v.y );
    }
    else if ( v.y == 0 )
    {
      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 + ( 1L << ( shift - 1 ) ) ) >> shift;
 
    return (FT_Fixed)( (FT_UInt32)v.x << -shift );
  }

Referenced by FT_Hypot(), FT_Stroker_ConicTo(), FT_Stroker_CubicTo(), FT_Stroker_LineTo(), and test_length().

FT_Vector_Polarize()

FT_Vector_Polarize	(	FT_Vector *	vec,
		FT_Fixed *	length,
		FT_Angle *	angle
	)

Definition at line 463 of file fttrigon.c.

  {
    FT_Int     shift;
    FT_Vector  v;
 
 
    if ( !vec || !length || !angle )
      return;
 
    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 )
                         : (FT_Fixed)( (FT_UInt32)v.x << -shift );
    *angle  = v.y;
  }

FT_Vector_Rotate()

FT_Vector_Rotate	(	FT_Vector *	vec,
		FT_Angle	angle
	)

Definition at line 386 of file fttrigon.c.

  {
    FT_Int     shift;
    FT_Vector  v;
 
 
    if ( !vec || !angle )
      return;
 
    v = *vec;
 
    if ( v.x == 0 && v.y == 0 )
      return;
 
    shift = ft_trig_prenorm( &v );
    ft_trig_pseudo_rotate( &v, angle );
    v.x = ft_trig_downscale( v.x );
    v.y = ft_trig_downscale( v.y );
 
    if ( shift > 0 )
    {
      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 = (FT_Pos)( (FT_ULong)v.x << shift );
      vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
    }
  }

Referenced by FT_Vector_From_Polar(), and test_rotate().

FT_Vector_Unit()

FT_Vector_Unit	(	FT_Vector *	vec,
		FT_Angle	angle
	)

Definition at line 361 of file fttrigon.c.

  {
    if ( !vec )
      return;
 
    vec->x = FT_TRIG_SCALE >> 8;
    vec->y = 0;
    ft_trig_pseudo_rotate( vec, angle );
    vec->x = ( vec->x + 0x80L ) >> 8;
    vec->y = ( vec->y + 0x80L ) >> 8;
  }

Referenced by FT_Cos(), FT_Sin(), FT_Tan(), IntEscapeMatrix(), and test_unit().

Variable Documentation

ft_trig_arctan_table

const FT_Angle ft_trig_arctan_table[]

static

Initial value:

=
  {
    1740967L, 919879L, 466945L, 234379L, 117304L, 58666L, 29335L,
    14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
    57L, 29L, 14L, 7L, 4L, 2L, 1L
  }

Definition at line 49 of file fttrigon.c.

Referenced by ft_trig_pseudo_polarize(), and ft_trig_pseudo_rotate().