ReactOS 0.4.15-dev-7674-gc0b4db1
fttrigon.c
Go to the documentation of this file.
1/***************************************************************************/
2/* */
3/* fttrigon.c */
4/* */
5/* FreeType trigonometric functions (body). */
6/* */
7/* Copyright 2001-2018 by */
8/* David Turner, Robert Wilhelm, and Werner Lemberg. */
9/* */
10/* This file is part of the FreeType project, and may only be used, */
11/* modified, and distributed under the terms of the FreeType project */
12/* license, LICENSE.TXT. By continuing to use, modify, or distribute */
13/* this file you indicate that you have read the license and */
14/* understand and accept it fully. */
15/* */
16/***************************************************************************/
17
18 /*************************************************************************/
19 /* */
20 /* This is a fixed-point CORDIC implementation of trigonometric */
21 /* functions as well as transformations between Cartesian and polar */
22 /* coordinates. The angles are represented as 16.16 fixed-point values */
23 /* in degrees, i.e., the angular resolution is 2^-16 degrees. Note that */
24 /* only vectors longer than 2^16*180/pi (or at least 22 bits) on a */
25 /* discrete Cartesian grid can have the same or better angular */
26 /* resolution. Therefore, to maintain this precision, some functions */
27 /* require an interim upscaling of the vectors, whereas others operate */
28 /* with 24-bit long vectors directly. */
29 /* */
30 /*************************************************************************/
31
32#include <ft2build.h>
33#include FT_INTERNAL_OBJECTS_H
34#include FT_INTERNAL_CALC_H
35#include FT_TRIGONOMETRY_H
36
37
38 /* the Cordic shrink factor 0.858785336480436 * 2^32 */
39#define FT_TRIG_SCALE 0xDBD95B16UL
40
41 /* the highest bit in overflow-safe vector components, */
42 /* MSB of 0.858785336480436 * sqrt(0.5) * 2^30 */
43#define FT_TRIG_SAFE_MSB 29
44
45 /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
46#define FT_TRIG_MAX_ITERS 23
47
48 static const FT_Angle
50 {
51 1740967L, 919879L, 466945L, 234379L, 117304L, 58666L, 29335L,
52 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
53 57L, 29L, 14L, 7L, 4L, 2L, 1L
54 };
55
56
57#ifdef FT_LONG64
58
59 /* multiply a given value by the CORDIC shrink factor */
60 static FT_Fixed
62 {
63 FT_Int s = 1;
64
65
66 if ( val < 0 )
67 {
68 val = -val;
69 s = -1;
70 }
71
72 /* 0x40000000 comes from regression analysis between true */
73 /* and CORDIC hypotenuse, so it minimizes the error */
74 val = (FT_Fixed)(
75 ( (FT_UInt64)val * FT_TRIG_SCALE + 0x40000000UL ) >> 32 );
76
77 return s < 0 ? -val : val;
78 }
79
80#else /* !FT_LONG64 */
81
82 /* multiply a given value by the CORDIC shrink factor */
83 static FT_Fixed
85 {
86 FT_Int s = 1;
87 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2;
88
89
90 if ( val < 0 )
91 {
92 val = -val;
93 s = -1;
94 }
95
96 lo1 = (FT_UInt32)val & 0x0000FFFFU;
97 hi1 = (FT_UInt32)val >> 16;
98 lo2 = FT_TRIG_SCALE & 0x0000FFFFU;
99 hi2 = FT_TRIG_SCALE >> 16;
100
101 lo = lo1 * lo2;
102 i1 = lo1 * hi2;
103 i2 = lo2 * hi1;
104 hi = hi1 * hi2;
105
106 /* Check carry overflow of i1 + i2 */
107 i1 += i2;
108 hi += (FT_UInt32)( i1 < i2 ) << 16;
109
110 hi += i1 >> 16;
111 i1 = i1 << 16;
112
113 /* Check carry overflow of i1 + lo */
114 lo += i1;
115 hi += ( lo < i1 );
116
117 /* 0x40000000 comes from regression analysis between true */
118 /* and CORDIC hypotenuse, so it minimizes the error */
119
120 /* Check carry overflow of lo + 0x40000000 */
121 lo += 0x40000000UL;
122 hi += ( lo < 0x40000000UL );
123
124 val = (FT_Fixed)hi;
125
126 return s < 0 ? -val : val;
127 }
128
129#endif /* !FT_LONG64 */
130
131
132 /* undefined and never called for zero vector */
133 static FT_Int
135 {
136 FT_Pos x, y;
138
139
140 x = vec->x;
141 y = vec->y;
142
143 shift = FT_MSB( (FT_UInt32)( FT_ABS( x ) | FT_ABS( y ) ) );
144
145 if ( shift <= FT_TRIG_SAFE_MSB )
146 {
148 vec->x = (FT_Pos)( (FT_ULong)x << shift );
149 vec->y = (FT_Pos)( (FT_ULong)y << shift );
150 }
151 else
152 {
154 vec->x = x >> shift;
155 vec->y = y >> shift;
156 shift = -shift;
157 }
158
159 return shift;
160 }
161
162
163 static void
165 FT_Angle theta )
166 {
167 FT_Int i;
168 FT_Fixed x, y, xtemp, b;
169 const FT_Angle *arctanptr;
170
171
172 x = vec->x;
173 y = vec->y;
174
175 /* Rotate inside [-PI/4,PI/4] sector */
176 while ( theta < -FT_ANGLE_PI4 )
177 {
178 xtemp = y;
179 y = -x;
180 x = xtemp;
181 theta += FT_ANGLE_PI2;
182 }
183
184 while ( theta > FT_ANGLE_PI4 )
185 {
186 xtemp = -y;
187 y = x;
188 x = xtemp;
189 theta -= FT_ANGLE_PI2;
190 }
191
192 arctanptr = ft_trig_arctan_table;
193
194 /* Pseudorotations, with right shifts */
195 for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
196 {
197 if ( theta < 0 )
198 {
199 xtemp = x + ( ( y + b ) >> i );
200 y = y - ( ( x + b ) >> i );
201 x = xtemp;
202 theta += *arctanptr++;
203 }
204 else
205 {
206 xtemp = x - ( ( y + b ) >> i );
207 y = y + ( ( x + b ) >> i );
208 x = xtemp;
209 theta -= *arctanptr++;
210 }
211 }
212
213 vec->x = x;
214 vec->y = y;
215 }
216
217
218 static void
220 {
221 FT_Angle theta;
222 FT_Int i;
223 FT_Fixed x, y, xtemp, b;
224 const FT_Angle *arctanptr;
225
226
227 x = vec->x;
228 y = vec->y;
229
230 /* Get the vector into [-PI/4,PI/4] sector */
231 if ( y > x )
232 {
233 if ( y > -x )
234 {
235 theta = FT_ANGLE_PI2;
236 xtemp = y;
237 y = -x;
238 x = xtemp;
239 }
240 else
241 {
242 theta = y > 0 ? FT_ANGLE_PI : -FT_ANGLE_PI;
243 x = -x;
244 y = -y;
245 }
246 }
247 else
248 {
249 if ( y < -x )
250 {
251 theta = -FT_ANGLE_PI2;
252 xtemp = -y;
253 y = x;
254 x = xtemp;
255 }
256 else
257 {
258 theta = 0;
259 }
260 }
261
262 arctanptr = ft_trig_arctan_table;
263
264 /* Pseudorotations, with right shifts */
265 for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ )
266 {
267 if ( y > 0 )
268 {
269 xtemp = x + ( ( y + b ) >> i );
270 y = y - ( ( x + b ) >> i );
271 x = xtemp;
272 theta += *arctanptr++;
273 }
274 else
275 {
276 xtemp = x - ( ( y + b ) >> i );
277 y = y + ( ( x + b ) >> i );
278 x = xtemp;
279 theta -= *arctanptr++;
280 }
281 }
282
283 /* round theta to acknowledge its error that mostly comes */
284 /* from accumulated rounding errors in the arctan table */
285 if ( theta >= 0 )
286 theta = FT_PAD_ROUND( theta, 16 );
287 else
288 theta = -FT_PAD_ROUND( -theta, 16 );
289
290 vec->x = x;
291 vec->y = theta;
292 }
293
294
295 /* documentation is in fttrigon.h */
296
299 {
300 FT_Vector v;
301
302
304
305 return v.x;
306 }
307
308
309 /* documentation is in fttrigon.h */
310
313 {
314 FT_Vector v;
315
316
318
319 return v.y;
320 }
321
322
323 /* documentation is in fttrigon.h */
324
327 {
328 FT_Vector v;
329
330
332
333 return FT_DivFix( v.y, v.x );
334 }
335
336
337 /* documentation is in fttrigon.h */
338
341 FT_Fixed dy )
342 {
343 FT_Vector v;
344
345
346 if ( dx == 0 && dy == 0 )
347 return 0;
348
349 v.x = dx;
350 v.y = dy;
351 ft_trig_prenorm( &v );
353
354 return v.y;
355 }
356
357
358 /* documentation is in fttrigon.h */
359
360 FT_EXPORT_DEF( void )
363 {
364 if ( !vec )
365 return;
366
367 vec->x = FT_TRIG_SCALE >> 8;
368 vec->y = 0;
370 vec->x = ( vec->x + 0x80L ) >> 8;
371 vec->y = ( vec->y + 0x80L ) >> 8;
372 }
373
374
375 /* these macros return 0 for positive numbers,
376 and -1 for negative ones */
377#define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
378#define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
379#define FT_SIGN_INT32( x ) ( (x) >> 31 )
380#define FT_SIGN_INT16( x ) ( (x) >> 15 )
381
382
383 /* documentation is in fttrigon.h */
384
385 FT_EXPORT_DEF( void )
388 {
390 FT_Vector v;
391
392
393 if ( !vec || !angle )
394 return;
395
396 v = *vec;
397
398 if ( v.x == 0 && v.y == 0 )
399 return;
400
401 shift = ft_trig_prenorm( &v );
403 v.x = ft_trig_downscale( v.x );
404 v.y = ft_trig_downscale( v.y );
405
406 if ( shift > 0 )
407 {
408 FT_Int32 half = (FT_Int32)1L << ( shift - 1 );
409
410
411 vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
412 vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
413 }
414 else
415 {
416 shift = -shift;
417 vec->x = (FT_Pos)( (FT_ULong)v.x << shift );
418 vec->y = (FT_Pos)( (FT_ULong)v.y << shift );
419 }
420 }
421
422
423 /* documentation is in fttrigon.h */
424
427 {
429 FT_Vector v;
430
431
432 if ( !vec )
433 return 0;
434
435 v = *vec;
436
437 /* handle trivial cases */
438 if ( v.x == 0 )
439 {
440 return FT_ABS( v.y );
441 }
442 else if ( v.y == 0 )
443 {
444 return FT_ABS( v.x );
445 }
446
447 /* general case */
448 shift = ft_trig_prenorm( &v );
450
451 v.x = ft_trig_downscale( v.x );
452
453 if ( shift > 0 )
454 return ( v.x + ( 1L << ( shift - 1 ) ) ) >> shift;
455
456 return (FT_Fixed)( (FT_UInt32)v.x << -shift );
457 }
458
459
460 /* documentation is in fttrigon.h */
461
462 FT_EXPORT_DEF( void )
465 FT_Angle *angle )
466 {
468 FT_Vector v;
469
470
471 if ( !vec || !length || !angle )
472 return;
473
474 v = *vec;
475
476 if ( v.x == 0 && v.y == 0 )
477 return;
478
479 shift = ft_trig_prenorm( &v );
481
482 v.x = ft_trig_downscale( v.x );
483
484 *length = shift >= 0 ? ( v.x >> shift )
485 : (FT_Fixed)( (FT_UInt32)v.x << -shift );
486 *angle = v.y;
487 }
488
489
490 /* documentation is in fttrigon.h */
491
492 FT_EXPORT_DEF( void )
496 {
497 if ( !vec )
498 return;
499
500 vec->x = length;
501 vec->y = 0;
502
504 }
505
506
507 /* documentation is in fttrigon.h */
508
511 FT_Angle angle2 )
512 {
513 FT_Angle delta = angle2 - angle1;
514
515
516 while ( delta <= -FT_ANGLE_PI )
517 delta += FT_ANGLE_2PI;
518
519 while ( delta > FT_ANGLE_PI )
520 delta -= FT_ANGLE_2PI;
521
522 return delta;
523 }
524
525
526/* END */
FT_DivFix(FT_Long a, FT_Long b)
Definition: ftcalc.c:608
FT_Vector * vec
Definition: ftbbox.c:448
FT_MSB(FT_UInt32 z)
Definition: ftcalc.c:114
#define FT_EXPORT_DEF(x)
Definition: ftconfig.h:483
FT_BEGIN_HEADER typedef signed long FT_Pos
Definition: ftimage.h:58
#define FT_ABS(a)
Definition: ftobjs.h:74
#define FT_PAD_ROUND(x, n)
Definition: ftobjs.h:89
FT_Vector_From_Polar(FT_Vector *vec, FT_Fixed length, FT_Angle angle)
Definition: fttrigon.c:493
FT_Vector_Polarize(FT_Vector *vec, FT_Fixed *length, FT_Angle *angle)
Definition: fttrigon.c:463
static const FT_Angle ft_trig_arctan_table[]
Definition: fttrigon.c:49
static FT_Fixed ft_trig_downscale(FT_Fixed val)
Definition: fttrigon.c:84
FT_Vector_Length(FT_Vector *vec)
Definition: fttrigon.c:426
FT_Vector_Unit(FT_Vector *vec, FT_Angle angle)
Definition: fttrigon.c:361
static void ft_trig_pseudo_rotate(FT_Vector *vec, FT_Angle theta)
Definition: fttrigon.c:164
FT_Tan(FT_Angle angle)
Definition: fttrigon.c:326
FT_Angle_Diff(FT_Angle angle1, FT_Angle angle2)
Definition: fttrigon.c:510
#define FT_TRIG_SAFE_MSB
Definition: fttrigon.c:43
#define FT_TRIG_SCALE
Definition: fttrigon.c:39
FT_Sin(FT_Angle angle)
Definition: fttrigon.c:312
static void ft_trig_pseudo_polarize(FT_Vector *vec)
Definition: fttrigon.c:219
#define FT_SIGN_LONG(x)
Definition: fttrigon.c:377
FT_Atan2(FT_Fixed dx, FT_Fixed dy)
Definition: fttrigon.c:340
FT_Cos(FT_Angle angle)
Definition: fttrigon.c:298
FT_Vector_Rotate(FT_Vector *vec, FT_Angle angle)
Definition: fttrigon.c:386
#define FT_TRIG_MAX_ITERS
Definition: fttrigon.c:46
static FT_Int ft_trig_prenorm(FT_Vector *vec)
Definition: fttrigon.c:134
FT_BEGIN_HEADER typedef FT_Fixed FT_Angle
Definition: fttrigon.h:52
#define FT_ANGLE_PI4
Definition: fttrigon.h:100
#define FT_ANGLE_PI
Definition: fttrigon.h:64
#define FT_ANGLE_2PI
Definition: fttrigon.h:76
#define FT_ANGLE_PI2
Definition: fttrigon.h:88
unsigned long FT_ULong
Definition: fttypes.h:253
signed long FT_Fixed
Definition: fttypes.h:288
signed int FT_Int
Definition: fttypes.h:220
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
const GLdouble * v
Definition: gl.h:2040
GLdouble s
Definition: gl.h:2039
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLboolean GLboolean GLboolean b
Definition: glext.h:6204
GLuint GLsizei GLsizei * length
Definition: glext.h:6040
GLfloat angle
Definition: glext.h:10853
GLuint GLfloat * val
Definition: glext.h:7180
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
#define b
Definition: ke_i.h:79
GLint dy
Definition: linetemp.h:97
GLint dx
Definition: linetemp.h:97
#define shift
Definition: input.c:1755
FT_Pos x
Definition: ftimage.h:76
FT_Pos y
Definition: ftimage.h:77