Index: src/base/fttrigon.c |
diff --git a/src/base/fttrigon.c b/src/base/fttrigon.c |
index fdf433ab866aa73dd89fbaa47c6c2cd98e0206f0..4ffdcb77f1bfa619d5b9e70a9b896e01610711a3 100644 |
--- a/src/base/fttrigon.c |
+++ b/src/base/fttrigon.c |
@@ -4,7 +4,7 @@ |
/* */ |
/* 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, */ |
@@ -15,31 +15,46 @@ |
/* */ |
/***************************************************************************/ |
+ /*************************************************************************/ |
+ /* */ |
+ /* 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 |
@@ -50,7 +65,7 @@ |
s = val; |
- val = ( val >= 0 ) ? val : -val; |
+ val = FT_ABS( val ); |
v = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL; |
val = (FT_Fixed)( v >> 32 ); |
@@ -58,7 +73,7 @@ |
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 |
@@ -69,19 +84,19 @@ |
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; |
@@ -93,91 +108,35 @@ |
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 ) ) |
- { |
- z >>= 16; |
- shift += 16; |
- } |
- if ( z >= ( 1L << 8 ) ) |
- { |
- z >>= 8; |
- shift += 8; |
- } |
- if ( z >= ( 1L << 4 ) ) |
- { |
- z >>= 4; |
- shift += 4; |
- } |
- if ( z >= ( 1L << 2 ) ) |
+ if ( shift <= FT_TRIG_SAFE_MSB ) |
{ |
- 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; |
- 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 ) ); |
- |
+ shift -= FT_TRIG_SAFE_MSB; |
vec->x = x >> shift; |
vec->y = y >> shift; |
shift = -shift; |
} |
-#endif /* 0 */ |
- |
return shift; |
} |
@@ -187,65 +146,50 @@ |
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; |
@@ -255,66 +199,67 @@ |
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 > 0 ) |
- theta = - theta; |
- |
- arctanptr = ft_trig_arctan_table; |
- |
- if ( y < 0 ) |
- { |
- /* Rotate positive */ |
- yi = y + ( x << 1 ); |
- x = x - ( y << 1 ); |
- y = yi; |
- theta -= *arctanptr++; /* Subtract angle */ |
+ 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 |
{ |
- /* Rotate negative */ |
- yi = y - ( x << 1 ); |
- x = x + ( y << 1 ); |
- y = yi; |
- theta += *arctanptr++; /* Add angle */ |
+ if ( y < -x ) |
+ { |
+ theta = -FT_ANGLE_PI2; |
+ xtemp = -y; |
+ y = x; |
+ x = xtemp; |
+ } |
+ else |
+ { |
+ theta = 0; |
+ } |
} |
- i = 0; |
- do |
+ 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 ) |
+ 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 ) |
@@ -335,11 +280,11 @@ |
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; |
} |
@@ -360,7 +305,7 @@ |
FT_Vector v; |
- v.x = FT_TRIG_COSCALE >> 2; |
+ v.x = FT_TRIG_SCALE >> 8; |
v.y = 0; |
ft_trig_pseudo_rotate( &v, angle ); |
@@ -395,11 +340,11 @@ |
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; |
} |
@@ -442,8 +387,8 @@ |
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 ); |
} |
} |
} |
@@ -463,11 +408,11 @@ |
/* 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 */ |
@@ -479,7 +424,7 @@ |
if ( shift > 0 ) |
return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift; |
- return v.x << -shift; |
+ return (FT_Fixed)( (FT_UInt32)v.x << -shift ); |
} |
@@ -504,7 +449,8 @@ |
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; |
} |