Commit b4ac30b0edf57e9ea3e12d0e4279f16b5ba121ee
2013-01-02T22:21:37
[base] Reduce trigonometric algorithms. After we get within 45 degrees by means of true 90-degree rotations, we can remove initial 45-degree CORDIC iteration and start from atan(1/2) pseudorotation, reducing expansion factor thereby. * src/base/fttrigon.c (FT_TRIG_SCALE, FT_TRIG_COSCALE): Update macros. (ft_trig_pseudo_rotate, ft_trig_pseudo_polarize): Update. * src/tools/cordic.py: Bring up to date with trigonometric core. * docs/CHANGES: Old typo.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183
diff --git a/ChangeLog b/ChangeLog
index ee029b7..cd0cca4 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,19 @@
-2012-12-21 Alexei Podtelezhnikov <apodtele@gmail.com>
+2013-01-02 Alexei Podtelezhnikov <apodtele@gmail.com>
+
+ [base] Reduce trigonometric algorithms.
+
+ After we get within 45 degrees by means of true 90-degree rotations,
+ we can remove initial 45-degree CORDIC iteration and start from
+ atan(1/2) pseudorotation, reducing expansion factor thereby.
+
+ * src/base/fttrigon.c (FT_TRIG_SCALE, FT_TRIG_COSCALE): Update macros.
+ (ft_trig_pseudo_rotate, ft_trig_pseudo_polarize): Update.
+
+ * src/tools/cordic.py: Bring up to date with trigonometric core.
+
+ * docs/CHANGES: Old typo.
+
+2013-01-02 Alexei Podtelezhnikov <apodtele@gmail.com>
* src/pshinter/pshalgo.h: Remove unused code.
diff --git a/docs/CHANGES b/docs/CHANGES
index 18ec194..5de81f5 100644
--- a/docs/CHANGES
+++ b/docs/CHANGES
@@ -2486,7 +2486,7 @@ CHANGES BETWEEN 2.0.3 and 2.0.2
number. see <freetype/fterrors.h> for details.
- A new public header file has been introduced, named
- FT_TRIGONOMETRY_H (include/freetype/fttrig.h), providing
+ FT_TRIGONOMETRY_H (include/freetype/fttrigon.h), providing
trigonometric functions to compute sines, cosines, arctangents,
etc. with 16.16 fixed precision. The implementation is based on
the CORDIC algorithm and is very fast while being sufficiently
diff --git a/src/base/fttrigon.c b/src/base/fttrigon.c
index 5239538..4bcc7ab 100644
--- a/src/base/fttrigon.c
+++ b/src/base/fttrigon.c
@@ -4,7 +4,7 @@
/* */
/* FreeType trigonometric functions (body). */
/* */
-/* Copyright 2001-2005, 2012 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, */
@@ -26,20 +26,20 @@
#endif
- /* the Cordic shrink factor 0.607252935008887 * 2^32 */
-#define FT_TRIG_SCALE 0x9B74EDA8UL
+ /* the Cordic shrink factor 0.858785336480436 * 2^32 */
+#define FT_TRIG_SCALE 0xDBD95B16UL
- /* the following is 0.607252935008887 * 2^30 */
-#define FT_TRIG_COSCALE 0x26DD3B6AUL
+ /* the following is 0.858785336480436 * 2^30 */
+#define FT_TRIG_COSCALE 0x36F656C6UL
/* 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[23] =
+ ft_trig_arctan_table[] =
{
- 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
};
@@ -199,25 +199,27 @@
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;
}
arctanptr = ft_trig_arctan_table;
/* Pseudorotations, with right shifts */
- i = 0;
+ i = 1;
do
{
if ( theta < 0 )
@@ -253,22 +255,42 @@
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;
+ }
+ }
+ else
+ {
+ if ( y < -x )
+ {
+ theta = -FT_ANGLE_PI2;
+ xtemp = -y;
+ y = x;
+ x = xtemp;
+ }
+ else
+ {
+ theta = 0;
+ }
}
-
- if ( y > 0 )
- theta = - theta;
arctanptr = ft_trig_arctan_table;
/* Pseudorotations, with right shifts */
- i = 0;
+ i = 1;
do
{
if ( y > 0 )
diff --git a/src/tools/cordic.py b/src/tools/cordic.py
index 44bdc20..6742c90 100644
--- a/src/tools/cordic.py
+++ b/src/tools/cordic.py
@@ -10,7 +10,7 @@ comma = ""
print ""
print "table of arctan( 1/2^n ) for PI = " + repr(units/65536.0) + " units"
-for n in range(0,32):
+for n in range(1,32):
x = 0.5**n # tangent value