Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
4349 | Serge | 1 | /***************************************************************************/ |
2 | /* */ |
||
3 | /* fttrigon.c */ |
||
4 | /* */ |
||
5 | /* FreeType trigonometric functions (body). */ |
||
6 | /* */ |
||
7 | /* Copyright 2001-2005, 2012-2013 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 |
||
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_Fixed |
||
49 | ft_trig_arctan_table[] = |
||
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 |
||
61 | ft_trig_downscale( FT_Fixed val ) |
||
62 | { |
||
63 | FT_Fixed s; |
||
64 | FT_Int64 v; |
||
65 | |||
66 | |||
67 | s = val; |
||
68 | val = FT_ABS( val ); |
||
69 | |||
70 | v = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL; |
||
71 | val = (FT_Fixed)( v >> 32 ); |
||
72 | |||
73 | return ( s >= 0 ) ? val : -val; |
||
74 | } |
||
75 | |||
76 | #else /* !FT_LONG64 */ |
||
77 | |||
78 | /* multiply a given value by the CORDIC shrink factor */ |
||
79 | static FT_Fixed |
||
80 | ft_trig_downscale( FT_Fixed val ) |
||
81 | { |
||
82 | FT_Fixed s; |
||
83 | FT_UInt32 v1, v2, k1, k2, hi, lo1, lo2, lo3; |
||
84 | |||
85 | |||
86 | s = val; |
||
87 | val = FT_ABS( val ); |
||
88 | |||
89 | v1 = (FT_UInt32)val >> 16; |
||
90 | v2 = (FT_UInt32)( val & 0xFFFFL ); |
||
91 | |||
92 | k1 = (FT_UInt32)FT_TRIG_SCALE >> 16; /* constant */ |
||
93 | k2 = (FT_UInt32)( FT_TRIG_SCALE & 0xFFFFL ); /* constant */ |
||
94 | |||
95 | hi = k1 * v1; |
||
96 | lo1 = k1 * v2 + k2 * v1; /* can't overflow */ |
||
97 | |||
98 | lo2 = ( k2 * v2 ) >> 16; |
||
99 | lo3 = FT_MAX( lo1, lo2 ); |
||
100 | lo1 += lo2; |
||
101 | |||
102 | hi += lo1 >> 16; |
||
103 | if ( lo1 < lo3 ) |
||
104 | hi += (FT_UInt32)0x10000UL; |
||
105 | |||
106 | val = (FT_Fixed)hi; |
||
107 | |||
108 | return ( s >= 0 ) ? val : -val; |
||
109 | } |
||
110 | |||
111 | #endif /* !FT_LONG64 */ |
||
112 | |||
113 | |||
114 | static FT_Int |
||
115 | ft_trig_prenorm( FT_Vector* vec ) |
||
116 | { |
||
117 | FT_Pos x, y; |
||
118 | FT_Int shift; |
||
119 | |||
120 | |||
121 | x = vec->x; |
||
122 | y = vec->y; |
||
123 | |||
124 | shift = FT_MSB( FT_ABS( x ) | FT_ABS( y ) ); |
||
125 | |||
126 | if ( shift <= FT_TRIG_SAFE_MSB ) |
||
127 | { |
||
128 | shift = FT_TRIG_SAFE_MSB - shift; |
||
129 | vec->x = (FT_Pos)( (FT_ULong)x << shift ); |
||
130 | vec->y = (FT_Pos)( (FT_ULong)y << shift ); |
||
131 | } |
||
132 | else |
||
133 | { |
||
134 | shift -= FT_TRIG_SAFE_MSB; |
||
135 | vec->x = x >> shift; |
||
136 | vec->y = y >> shift; |
||
137 | shift = -shift; |
||
138 | } |
||
139 | |||
140 | return shift; |
||
141 | } |
||
142 | |||
143 | |||
144 | static void |
||
145 | ft_trig_pseudo_rotate( FT_Vector* vec, |
||
146 | FT_Angle theta ) |
||
147 | { |
||
148 | FT_Int i; |
||
149 | FT_Fixed x, y, xtemp, b; |
||
150 | const FT_Fixed *arctanptr; |
||
151 | |||
152 | |||
153 | x = vec->x; |
||
154 | y = vec->y; |
||
155 | |||
156 | /* Rotate inside [-PI/4,PI/4] sector */ |
||
157 | while ( theta < -FT_ANGLE_PI4 ) |
||
158 | { |
||
159 | xtemp = y; |
||
160 | y = -x; |
||
161 | x = xtemp; |
||
162 | theta += FT_ANGLE_PI2; |
||
163 | } |
||
164 | |||
165 | while ( theta > FT_ANGLE_PI4 ) |
||
166 | { |
||
167 | xtemp = -y; |
||
168 | y = x; |
||
169 | x = xtemp; |
||
170 | theta -= FT_ANGLE_PI2; |
||
171 | } |
||
172 | |||
173 | arctanptr = ft_trig_arctan_table; |
||
174 | |||
175 | /* Pseudorotations, with right shifts */ |
||
176 | for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ ) |
||
177 | { |
||
178 | if ( theta < 0 ) |
||
179 | { |
||
180 | xtemp = x + ( ( y + b ) >> i ); |
||
181 | y = y - ( ( x + b ) >> i ); |
||
182 | x = xtemp; |
||
183 | theta += *arctanptr++; |
||
184 | } |
||
185 | else |
||
186 | { |
||
187 | xtemp = x - ( ( y + b ) >> i ); |
||
188 | y = y + ( ( x + b ) >> i ); |
||
189 | x = xtemp; |
||
190 | theta -= *arctanptr++; |
||
191 | } |
||
192 | } |
||
193 | |||
194 | vec->x = x; |
||
195 | vec->y = y; |
||
196 | } |
||
197 | |||
198 | |||
199 | static void |
||
200 | ft_trig_pseudo_polarize( FT_Vector* vec ) |
||
201 | { |
||
202 | FT_Angle theta; |
||
203 | FT_Int i; |
||
204 | FT_Fixed x, y, xtemp, b; |
||
205 | const FT_Fixed *arctanptr; |
||
206 | |||
207 | |||
208 | x = vec->x; |
||
209 | y = vec->y; |
||
210 | |||
211 | /* Get the vector into [-PI/4,PI/4] sector */ |
||
212 | if ( y > x ) |
||
213 | { |
||
214 | if ( y > -x ) |
||
215 | { |
||
216 | theta = FT_ANGLE_PI2; |
||
217 | xtemp = y; |
||
218 | y = -x; |
||
219 | x = xtemp; |
||
220 | } |
||
221 | else |
||
222 | { |
||
223 | theta = y > 0 ? FT_ANGLE_PI : -FT_ANGLE_PI; |
||
224 | x = -x; |
||
225 | y = -y; |
||
226 | } |
||
227 | } |
||
228 | else |
||
229 | { |
||
230 | if ( y < -x ) |
||
231 | { |
||
232 | theta = -FT_ANGLE_PI2; |
||
233 | xtemp = -y; |
||
234 | y = x; |
||
235 | x = xtemp; |
||
236 | } |
||
237 | else |
||
238 | { |
||
239 | theta = 0; |
||
240 | } |
||
241 | } |
||
242 | |||
243 | arctanptr = ft_trig_arctan_table; |
||
244 | |||
245 | /* Pseudorotations, with right shifts */ |
||
246 | for ( i = 1, b = 1; i < FT_TRIG_MAX_ITERS; b <<= 1, i++ ) |
||
247 | { |
||
248 | if ( y > 0 ) |
||
249 | { |
||
250 | xtemp = x + ( ( y + b ) >> i ); |
||
251 | y = y - ( ( x + b ) >> i ); |
||
252 | x = xtemp; |
||
253 | theta += *arctanptr++; |
||
254 | } |
||
255 | else |
||
256 | { |
||
257 | xtemp = x - ( ( y + b ) >> i ); |
||
258 | y = y + ( ( x + b ) >> i ); |
||
259 | x = xtemp; |
||
260 | theta -= *arctanptr++; |
||
261 | } |
||
262 | } |
||
263 | |||
264 | /* round theta */ |
||
265 | if ( theta >= 0 ) |
||
266 | theta = FT_PAD_ROUND( theta, 32 ); |
||
267 | else |
||
268 | theta = -FT_PAD_ROUND( -theta, 32 ); |
||
269 | |||
270 | vec->x = x; |
||
271 | vec->y = theta; |
||
272 | } |
||
273 | |||
274 | |||
275 | /* documentation is in fttrigon.h */ |
||
276 | |||
277 | FT_EXPORT_DEF( FT_Fixed ) |
||
278 | FT_Cos( FT_Angle angle ) |
||
279 | { |
||
280 | FT_Vector v; |
||
281 | |||
282 | |||
283 | v.x = FT_TRIG_SCALE >> 8; |
||
284 | v.y = 0; |
||
285 | ft_trig_pseudo_rotate( &v, angle ); |
||
286 | |||
287 | return ( v.x + 0x80L ) >> 8; |
||
288 | } |
||
289 | |||
290 | |||
291 | /* documentation is in fttrigon.h */ |
||
292 | |||
293 | FT_EXPORT_DEF( FT_Fixed ) |
||
294 | FT_Sin( FT_Angle angle ) |
||
295 | { |
||
296 | return FT_Cos( FT_ANGLE_PI2 - angle ); |
||
297 | } |
||
298 | |||
299 | |||
300 | /* documentation is in fttrigon.h */ |
||
301 | |||
302 | FT_EXPORT_DEF( FT_Fixed ) |
||
303 | FT_Tan( FT_Angle angle ) |
||
304 | { |
||
305 | FT_Vector v; |
||
306 | |||
307 | |||
308 | v.x = FT_TRIG_SCALE >> 8; |
||
309 | v.y = 0; |
||
310 | ft_trig_pseudo_rotate( &v, angle ); |
||
311 | |||
312 | return FT_DivFix( v.y, v.x ); |
||
313 | } |
||
314 | |||
315 | |||
316 | /* documentation is in fttrigon.h */ |
||
317 | |||
318 | FT_EXPORT_DEF( FT_Angle ) |
||
319 | FT_Atan2( FT_Fixed dx, |
||
320 | FT_Fixed dy ) |
||
321 | { |
||
322 | FT_Vector v; |
||
323 | |||
324 | |||
325 | if ( dx == 0 && dy == 0 ) |
||
326 | return 0; |
||
327 | |||
328 | v.x = dx; |
||
329 | v.y = dy; |
||
330 | ft_trig_prenorm( &v ); |
||
331 | ft_trig_pseudo_polarize( &v ); |
||
332 | |||
333 | return v.y; |
||
334 | } |
||
335 | |||
336 | |||
337 | /* documentation is in fttrigon.h */ |
||
338 | |||
339 | FT_EXPORT_DEF( void ) |
||
340 | FT_Vector_Unit( FT_Vector* vec, |
||
341 | FT_Angle angle ) |
||
342 | { |
||
343 | vec->x = FT_TRIG_SCALE >> 8; |
||
344 | vec->y = 0; |
||
345 | ft_trig_pseudo_rotate( vec, angle ); |
||
346 | vec->x = ( vec->x + 0x80L ) >> 8; |
||
347 | vec->y = ( vec->y + 0x80L ) >> 8; |
||
348 | } |
||
349 | |||
350 | |||
351 | /* these macros return 0 for positive numbers, |
||
352 | and -1 for negative ones */ |
||
353 | #define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) ) |
||
354 | #define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) ) |
||
355 | #define FT_SIGN_INT32( x ) ( (x) >> 31 ) |
||
356 | #define FT_SIGN_INT16( x ) ( (x) >> 15 ) |
||
357 | |||
358 | |||
359 | /* documentation is in fttrigon.h */ |
||
360 | |||
361 | FT_EXPORT_DEF( void ) |
||
362 | FT_Vector_Rotate( FT_Vector* vec, |
||
363 | FT_Angle angle ) |
||
364 | { |
||
365 | FT_Int shift; |
||
366 | FT_Vector v; |
||
367 | |||
368 | |||
369 | v.x = vec->x; |
||
370 | v.y = vec->y; |
||
371 | |||
372 | if ( angle && ( v.x != 0 || v.y != 0 ) ) |
||
373 | { |
||
374 | shift = ft_trig_prenorm( &v ); |
||
375 | ft_trig_pseudo_rotate( &v, angle ); |
||
376 | v.x = ft_trig_downscale( v.x ); |
||
377 | v.y = ft_trig_downscale( v.y ); |
||
378 | |||
379 | if ( shift > 0 ) |
||
380 | { |
||
381 | FT_Int32 half = (FT_Int32)1L << ( shift - 1 ); |
||
382 | |||
383 | |||
384 | vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift; |
||
385 | vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift; |
||
386 | } |
||
387 | else |
||
388 | { |
||
389 | shift = -shift; |
||
390 | vec->x = (FT_Pos)( (FT_ULong)v.x << shift ); |
||
391 | vec->y = (FT_Pos)( (FT_ULong)v.y << shift ); |
||
392 | } |
||
393 | } |
||
394 | } |
||
395 | |||
396 | |||
397 | /* documentation is in fttrigon.h */ |
||
398 | |||
399 | FT_EXPORT_DEF( FT_Fixed ) |
||
400 | FT_Vector_Length( FT_Vector* vec ) |
||
401 | { |
||
402 | FT_Int shift; |
||
403 | FT_Vector v; |
||
404 | |||
405 | |||
406 | v = *vec; |
||
407 | |||
408 | /* handle trivial cases */ |
||
409 | if ( v.x == 0 ) |
||
410 | { |
||
411 | return FT_ABS( v.y ); |
||
412 | } |
||
413 | else if ( v.y == 0 ) |
||
414 | { |
||
415 | return FT_ABS( v.x ); |
||
416 | } |
||
417 | |||
418 | /* general case */ |
||
419 | shift = ft_trig_prenorm( &v ); |
||
420 | ft_trig_pseudo_polarize( &v ); |
||
421 | |||
422 | v.x = ft_trig_downscale( v.x ); |
||
423 | |||
424 | if ( shift > 0 ) |
||
425 | return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift; |
||
426 | |||
427 | return (FT_Fixed)( (FT_UInt32)v.x << -shift ); |
||
428 | } |
||
429 | |||
430 | |||
431 | /* documentation is in fttrigon.h */ |
||
432 | |||
433 | FT_EXPORT_DEF( void ) |
||
434 | FT_Vector_Polarize( FT_Vector* vec, |
||
435 | FT_Fixed *length, |
||
436 | FT_Angle *angle ) |
||
437 | { |
||
438 | FT_Int shift; |
||
439 | FT_Vector v; |
||
440 | |||
441 | |||
442 | v = *vec; |
||
443 | |||
444 | if ( v.x == 0 && v.y == 0 ) |
||
445 | return; |
||
446 | |||
447 | shift = ft_trig_prenorm( &v ); |
||
448 | ft_trig_pseudo_polarize( &v ); |
||
449 | |||
450 | v.x = ft_trig_downscale( v.x ); |
||
451 | |||
452 | *length = ( shift >= 0 ) ? ( v.x >> shift ) |
||
453 | : (FT_Fixed)( (FT_UInt32)v.x << -shift ); |
||
454 | *angle = v.y; |
||
455 | } |
||
456 | |||
457 | |||
458 | /* documentation is in fttrigon.h */ |
||
459 | |||
460 | FT_EXPORT_DEF( void ) |
||
461 | FT_Vector_From_Polar( FT_Vector* vec, |
||
462 | FT_Fixed length, |
||
463 | FT_Angle angle ) |
||
464 | { |
||
465 | vec->x = length; |
||
466 | vec->y = 0; |
||
467 | |||
468 | FT_Vector_Rotate( vec, angle ); |
||
469 | } |
||
470 | |||
471 | |||
472 | /* documentation is in fttrigon.h */ |
||
473 | |||
474 | FT_EXPORT_DEF( FT_Angle ) |
||
475 | FT_Angle_Diff( FT_Angle angle1, |
||
476 | FT_Angle angle2 ) |
||
477 | { |
||
478 | FT_Angle delta = angle2 - angle1; |
||
479 | |||
480 | |||
481 | delta %= FT_ANGLE_2PI; |
||
482 | if ( delta < 0 ) |
||
483 | delta += FT_ANGLE_2PI; |
||
484 | |||
485 | if ( delta > FT_ANGLE_PI ) |
||
486 | delta -= FT_ANGLE_2PI; |
||
487 | |||
488 | return delta; |
||
489 | } |
||
490 | |||
491 | |||
492 | /* END */>><>><>><>><>><>><>=><=>>>>=><=>>>><>><>=>>><> |