1 /***************************************************************************/ |
|
2 /* */ |
|
3 /* fttrigon.c */ |
|
4 /* */ |
|
5 /* FreeType trigonometric functions (body). */ |
|
6 /* */ |
|
7 /* Copyright 2001, 2002, 2003, 2004, 2005 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 #include <ft2build.h> |
|
20 #include FT_INTERNAL_OBJECTS_H |
|
21 #include FT_TRIGONOMETRY_H |
|
22 |
|
23 |
|
24 /* the following is 0.2715717684432231 * 2^30 */ |
|
25 #define FT_TRIG_COSCALE 0x11616E8EUL |
|
26 |
|
27 /* this table was generated for FT_PI = 180L << 16, i.e. degrees */ |
|
28 #define FT_TRIG_MAX_ITERS 23 |
|
29 |
|
30 static const FT_Fixed |
|
31 ft_trig_arctan_table[24] = |
|
32 { |
|
33 4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L, |
|
34 58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L, |
|
35 57L, 29L, 14L, 7L, 4L, 2L, 1L |
|
36 }; |
|
37 |
|
38 /* the Cordic shrink factor, multiplied by 2^32 */ |
|
39 #define FT_TRIG_SCALE 1166391785UL /* 0x4585BA38UL */ |
|
40 |
|
41 |
|
42 #ifdef FT_CONFIG_HAS_INT64 |
|
43 |
|
44 /* multiply a given value by the CORDIC shrink factor */ |
|
45 static FT_Fixed |
|
46 ft_trig_downscale( FT_Fixed val ) |
|
47 { |
|
48 FT_Fixed s; |
|
49 FT_Int64 v; |
|
50 |
|
51 |
|
52 s = val; |
|
53 val = ( val >= 0 ) ? val : -val; |
|
54 |
|
55 v = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL; |
|
56 val = (FT_Fixed)( v >> 32 ); |
|
57 |
|
58 return ( s >= 0 ) ? val : -val; |
|
59 } |
|
60 |
|
61 #else /* !FT_CONFIG_HAS_INT64 */ |
|
62 |
|
63 /* multiply a given value by the CORDIC shrink factor */ |
|
64 static FT_Fixed |
|
65 ft_trig_downscale( FT_Fixed val ) |
|
66 { |
|
67 FT_Fixed s; |
|
68 FT_UInt32 v1, v2, k1, k2, hi, lo1, lo2, lo3; |
|
69 |
|
70 |
|
71 s = val; |
|
72 val = ( val >= 0 ) ? val : -val; |
|
73 |
|
74 v1 = (FT_UInt32)val >> 16; |
|
75 v2 = (FT_UInt32)(val & 0xFFFFL); |
|
76 |
|
77 k1 = (FT_UInt32)FT_TRIG_SCALE >> 16; /* constant */ |
|
78 k2 = (FT_UInt32)(FT_TRIG_SCALE & 0xFFFFL); /* constant */ |
|
79 |
|
80 hi = k1 * v1; |
|
81 lo1 = k1 * v2 + k2 * v1; /* can't overflow */ |
|
82 |
|
83 lo2 = ( k2 * v2 ) >> 16; |
|
84 lo3 = ( lo1 >= lo2 ) ? lo1 : lo2; |
|
85 lo1 += lo2; |
|
86 |
|
87 hi += lo1 >> 16; |
|
88 if ( lo1 < lo3 ) |
|
89 hi += (FT_UInt32)0x10000UL; |
|
90 |
|
91 val = (FT_Fixed)hi; |
|
92 |
|
93 return ( s >= 0 ) ? val : -val; |
|
94 } |
|
95 |
|
96 #endif /* !FT_CONFIG_HAS_INT64 */ |
|
97 |
|
98 |
|
99 static FT_Int |
|
100 ft_trig_prenorm( FT_Vector* vec ) |
|
101 { |
|
102 FT_Fixed x, y, z; |
|
103 FT_Int shift; |
|
104 |
|
105 |
|
106 x = vec->x; |
|
107 y = vec->y; |
|
108 |
|
109 z = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y ); |
|
110 shift = 0; |
|
111 |
|
112 #if 1 |
|
113 /* determine msb bit index in `shift' */ |
|
114 if ( z >= ( 1L << 16 ) ) |
|
115 { |
|
116 z >>= 16; |
|
117 shift += 16; |
|
118 } |
|
119 if ( z >= ( 1L << 8 ) ) |
|
120 { |
|
121 z >>= 8; |
|
122 shift += 8; |
|
123 } |
|
124 if ( z >= ( 1L << 4 ) ) |
|
125 { |
|
126 z >>= 4; |
|
127 shift += 4; |
|
128 } |
|
129 if ( z >= ( 1L << 2 ) ) |
|
130 { |
|
131 z >>= 2; |
|
132 shift += 2; |
|
133 } |
|
134 if ( z >= ( 1L << 1 ) ) |
|
135 { |
|
136 z >>= 1; |
|
137 shift += 1; |
|
138 } |
|
139 |
|
140 if ( shift <= 27 ) |
|
141 { |
|
142 shift = 27 - shift; |
|
143 vec->x = x << shift; |
|
144 vec->y = y << shift; |
|
145 } |
|
146 else |
|
147 { |
|
148 shift -= 27; |
|
149 vec->x = x >> shift; |
|
150 vec->y = y >> shift; |
|
151 shift = -shift; |
|
152 } |
|
153 |
|
154 #else /* 0 */ |
|
155 |
|
156 if ( z < ( 1L << 27 ) ) |
|
157 { |
|
158 do |
|
159 { |
|
160 shift++; |
|
161 z <<= 1; |
|
162 } while ( z < ( 1L << 27 ) ); |
|
163 vec->x = x << shift; |
|
164 vec->y = y << shift; |
|
165 } |
|
166 else if ( z > ( 1L << 28 ) ) |
|
167 { |
|
168 do |
|
169 { |
|
170 shift++; |
|
171 z >>= 1; |
|
172 } while ( z > ( 1L << 28 ) ); |
|
173 |
|
174 vec->x = x >> shift; |
|
175 vec->y = y >> shift; |
|
176 shift = -shift; |
|
177 } |
|
178 |
|
179 #endif /* 0 */ |
|
180 |
|
181 return shift; |
|
182 } |
|
183 |
|
184 |
|
185 static void |
|
186 ft_trig_pseudo_rotate( FT_Vector* vec, |
|
187 FT_Angle theta ) |
|
188 { |
|
189 FT_Int i; |
|
190 FT_Fixed x, y, xtemp; |
|
191 const FT_Fixed *arctanptr; |
|
192 |
|
193 |
|
194 x = vec->x; |
|
195 y = vec->y; |
|
196 |
|
197 /* Get angle between -90 and 90 degrees */ |
|
198 while ( theta <= -FT_ANGLE_PI2 ) |
|
199 { |
|
200 x = -x; |
|
201 y = -y; |
|
202 theta += FT_ANGLE_PI; |
|
203 } |
|
204 |
|
205 while ( theta > FT_ANGLE_PI2 ) |
|
206 { |
|
207 x = -x; |
|
208 y = -y; |
|
209 theta -= FT_ANGLE_PI; |
|
210 } |
|
211 |
|
212 /* Initial pseudorotation, with left shift */ |
|
213 arctanptr = ft_trig_arctan_table; |
|
214 |
|
215 if ( theta < 0 ) |
|
216 { |
|
217 xtemp = x + ( y << 1 ); |
|
218 y = y - ( x << 1 ); |
|
219 x = xtemp; |
|
220 theta += *arctanptr++; |
|
221 } |
|
222 else |
|
223 { |
|
224 xtemp = x - ( y << 1 ); |
|
225 y = y + ( x << 1 ); |
|
226 x = xtemp; |
|
227 theta -= *arctanptr++; |
|
228 } |
|
229 |
|
230 /* Subsequent pseudorotations, with right shifts */ |
|
231 i = 0; |
|
232 do |
|
233 { |
|
234 if ( theta < 0 ) |
|
235 { |
|
236 xtemp = x + ( y >> i ); |
|
237 y = y - ( x >> i ); |
|
238 x = xtemp; |
|
239 theta += *arctanptr++; |
|
240 } |
|
241 else |
|
242 { |
|
243 xtemp = x - ( y >> i ); |
|
244 y = y + ( x >> i ); |
|
245 x = xtemp; |
|
246 theta -= *arctanptr++; |
|
247 } |
|
248 } while ( ++i < FT_TRIG_MAX_ITERS ); |
|
249 |
|
250 vec->x = x; |
|
251 vec->y = y; |
|
252 } |
|
253 |
|
254 |
|
255 static void |
|
256 ft_trig_pseudo_polarize( FT_Vector* vec ) |
|
257 { |
|
258 FT_Fixed theta; |
|
259 FT_Fixed yi, i; |
|
260 FT_Fixed x, y; |
|
261 const FT_Fixed *arctanptr; |
|
262 |
|
263 |
|
264 x = vec->x; |
|
265 y = vec->y; |
|
266 |
|
267 /* Get the vector into the right half plane */ |
|
268 theta = 0; |
|
269 if ( x < 0 ) |
|
270 { |
|
271 x = -x; |
|
272 y = -y; |
|
273 theta = 2 * FT_ANGLE_PI2; |
|
274 } |
|
275 |
|
276 if ( y > 0 ) |
|
277 theta = - theta; |
|
278 |
|
279 arctanptr = ft_trig_arctan_table; |
|
280 |
|
281 if ( y < 0 ) |
|
282 { |
|
283 /* Rotate positive */ |
|
284 yi = y + ( x << 1 ); |
|
285 x = x - ( y << 1 ); |
|
286 y = yi; |
|
287 theta -= *arctanptr++; /* Subtract angle */ |
|
288 } |
|
289 else |
|
290 { |
|
291 /* Rotate negative */ |
|
292 yi = y - ( x << 1 ); |
|
293 x = x + ( y << 1 ); |
|
294 y = yi; |
|
295 theta += *arctanptr++; /* Add angle */ |
|
296 } |
|
297 |
|
298 i = 0; |
|
299 do |
|
300 { |
|
301 if ( y < 0 ) |
|
302 { |
|
303 /* Rotate positive */ |
|
304 yi = y + ( x >> i ); |
|
305 x = x - ( y >> i ); |
|
306 y = yi; |
|
307 theta -= *arctanptr++; |
|
308 } |
|
309 else |
|
310 { |
|
311 /* Rotate negative */ |
|
312 yi = y - ( x >> i ); |
|
313 x = x + ( y >> i ); |
|
314 y = yi; |
|
315 theta += *arctanptr++; |
|
316 } |
|
317 } while ( ++i < FT_TRIG_MAX_ITERS ); |
|
318 |
|
319 /* round theta */ |
|
320 if ( theta >= 0 ) |
|
321 theta = FT_PAD_ROUND( theta, 32 ); |
|
322 else |
|
323 theta = -FT_PAD_ROUND( -theta, 32 ); |
|
324 |
|
325 vec->x = x; |
|
326 vec->y = theta; |
|
327 } |
|
328 |
|
329 |
|
330 /* documentation is in fttrigon.h */ |
|
331 |
|
332 FT_EXPORT_DEF( FT_Fixed ) |
|
333 FT_Cos( FT_Angle angle ) |
|
334 { |
|
335 FT_Vector v; |
|
336 |
|
337 |
|
338 v.x = FT_TRIG_COSCALE >> 2; |
|
339 v.y = 0; |
|
340 ft_trig_pseudo_rotate( &v, angle ); |
|
341 |
|
342 return v.x / ( 1 << 12 ); |
|
343 } |
|
344 |
|
345 |
|
346 /* documentation is in fttrigon.h */ |
|
347 |
|
348 FT_EXPORT_DEF( FT_Fixed ) |
|
349 FT_Sin( FT_Angle angle ) |
|
350 { |
|
351 return FT_Cos( FT_ANGLE_PI2 - angle ); |
|
352 } |
|
353 |
|
354 |
|
355 /* documentation is in fttrigon.h */ |
|
356 |
|
357 FT_EXPORT_DEF( FT_Fixed ) |
|
358 FT_Tan( FT_Angle angle ) |
|
359 { |
|
360 FT_Vector v; |
|
361 |
|
362 |
|
363 v.x = FT_TRIG_COSCALE >> 2; |
|
364 v.y = 0; |
|
365 ft_trig_pseudo_rotate( &v, angle ); |
|
366 |
|
367 return FT_DivFix( v.y, v.x ); |
|
368 } |
|
369 |
|
370 |
|
371 /* documentation is in fttrigon.h */ |
|
372 |
|
373 FT_EXPORT_DEF( FT_Angle ) |
|
374 FT_Atan2( FT_Fixed dx, |
|
375 FT_Fixed dy ) |
|
376 { |
|
377 FT_Vector v; |
|
378 |
|
379 |
|
380 if ( dx == 0 && dy == 0 ) |
|
381 return 0; |
|
382 |
|
383 v.x = dx; |
|
384 v.y = dy; |
|
385 ft_trig_prenorm( &v ); |
|
386 ft_trig_pseudo_polarize( &v ); |
|
387 |
|
388 return v.y; |
|
389 } |
|
390 |
|
391 |
|
392 /* documentation is in fttrigon.h */ |
|
393 |
|
394 FT_EXPORT_DEF( void ) |
|
395 FT_Vector_Unit( FT_Vector* vec, |
|
396 FT_Angle angle ) |
|
397 { |
|
398 vec->x = FT_TRIG_COSCALE >> 2; |
|
399 vec->y = 0; |
|
400 ft_trig_pseudo_rotate( vec, angle ); |
|
401 vec->x >>= 12; |
|
402 vec->y >>= 12; |
|
403 } |
|
404 |
|
405 |
|
406 /* these macros return 0 for positive numbers, |
|
407 and -1 for negative ones */ |
|
408 #define FT_SIGN_LONG( x ) ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) ) |
|
409 #define FT_SIGN_INT( x ) ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) ) |
|
410 #define FT_SIGN_INT32( x ) ( (x) >> 31 ) |
|
411 #define FT_SIGN_INT16( x ) ( (x) >> 15 ) |
|
412 |
|
413 |
|
414 /* documentation is in fttrigon.h */ |
|
415 |
|
416 FT_EXPORT_DEF( void ) |
|
417 FT_Vector_Rotate( FT_Vector* vec, |
|
418 FT_Angle angle ) |
|
419 { |
|
420 FT_Int shift; |
|
421 FT_Vector v; |
|
422 |
|
423 |
|
424 v.x = vec->x; |
|
425 v.y = vec->y; |
|
426 |
|
427 if ( angle && ( v.x != 0 || v.y != 0 ) ) |
|
428 { |
|
429 shift = ft_trig_prenorm( &v ); |
|
430 ft_trig_pseudo_rotate( &v, angle ); |
|
431 v.x = ft_trig_downscale( v.x ); |
|
432 v.y = ft_trig_downscale( v.y ); |
|
433 |
|
434 if ( shift > 0 ) |
|
435 { |
|
436 FT_Int32 half = (FT_Int32)1L << ( shift - 1 ); |
|
437 |
|
438 |
|
439 vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift; |
|
440 vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift; |
|
441 } |
|
442 else |
|
443 { |
|
444 shift = -shift; |
|
445 vec->x = v.x << shift; |
|
446 vec->y = v.y << shift; |
|
447 } |
|
448 } |
|
449 } |
|
450 |
|
451 |
|
452 /* documentation is in fttrigon.h */ |
|
453 |
|
454 FT_EXPORT_DEF( FT_Fixed ) |
|
455 FT_Vector_Length( FT_Vector* vec ) |
|
456 { |
|
457 FT_Int shift; |
|
458 FT_Vector v; |
|
459 |
|
460 |
|
461 v = *vec; |
|
462 |
|
463 /* handle trivial cases */ |
|
464 if ( v.x == 0 ) |
|
465 { |
|
466 return ( v.y >= 0 ) ? v.y : -v.y; |
|
467 } |
|
468 else if ( v.y == 0 ) |
|
469 { |
|
470 return ( v.x >= 0 ) ? v.x : -v.x; |
|
471 } |
|
472 |
|
473 /* general case */ |
|
474 shift = ft_trig_prenorm( &v ); |
|
475 ft_trig_pseudo_polarize( &v ); |
|
476 |
|
477 v.x = ft_trig_downscale( v.x ); |
|
478 |
|
479 if ( shift > 0 ) |
|
480 return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift; |
|
481 |
|
482 return v.x << -shift; |
|
483 } |
|
484 |
|
485 |
|
486 /* documentation is in fttrigon.h */ |
|
487 |
|
488 FT_EXPORT_DEF( void ) |
|
489 FT_Vector_Polarize( FT_Vector* vec, |
|
490 FT_Fixed *length, |
|
491 FT_Angle *angle ) |
|
492 { |
|
493 FT_Int shift; |
|
494 FT_Vector v; |
|
495 |
|
496 |
|
497 v = *vec; |
|
498 |
|
499 if ( v.x == 0 && v.y == 0 ) |
|
500 return; |
|
501 |
|
502 shift = ft_trig_prenorm( &v ); |
|
503 ft_trig_pseudo_polarize( &v ); |
|
504 |
|
505 v.x = ft_trig_downscale( v.x ); |
|
506 |
|
507 *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift ); |
|
508 *angle = v.y; |
|
509 } |
|
510 |
|
511 |
|
512 /* documentation is in fttrigon.h */ |
|
513 |
|
514 FT_EXPORT_DEF( void ) |
|
515 FT_Vector_From_Polar( FT_Vector* vec, |
|
516 FT_Fixed length, |
|
517 FT_Angle angle ) |
|
518 { |
|
519 vec->x = length; |
|
520 vec->y = 0; |
|
521 |
|
522 FT_Vector_Rotate( vec, angle ); |
|
523 } |
|
524 |
|
525 |
|
526 /* documentation is in fttrigon.h */ |
|
527 |
|
528 FT_EXPORT_DEF( FT_Angle ) |
|
529 FT_Angle_Diff( FT_Angle angle1, |
|
530 FT_Angle angle2 ) |
|
531 { |
|
532 FT_Angle delta = angle2 - angle1; |
|
533 |
|
534 |
|
535 delta %= FT_ANGLE_2PI; |
|
536 if ( delta < 0 ) |
|
537 delta += FT_ANGLE_2PI; |
|
538 |
|
539 if ( delta > FT_ANGLE_PI ) |
|
540 delta -= FT_ANGLE_2PI; |
|
541 |
|
542 return delta; |
|
543 } |
|
544 |
|
545 |
|
546 /* END */ |
|