OLD | NEW |
| (Empty) |
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 "../../include/ft2build.h" | |
33 #include "../../include/freetype/internal/ftobjs.h" | |
34 #include "../../include/freetype/internal/ftcalc.h" | |
35 #include "../../include/freetype/fttrigon.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 */ | |
OLD | NEW |