source: trunk/poppler/freetype-2.1.10/src/base/fttrigon.c @ 2

Last change on this file since 2 was 2, checked in by Eugene Romanenko, 15 years ago

First import

File size: 10.2 KB
Line 
1/***************************************************************************/
2/*                                                                         */
3/*  fttrigon.c                                                             */
4/*                                                                         */
5/*    FreeType trigonometric functions (body).                             */
6/*                                                                         */
7/*  Copyright 2001, 2002, 2003, 2004 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_TRIG_SCALE >> 16;       /* constant */
78    k2 = 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 += 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 ( z < ( 1L << 27 ) )
113    {
114      do
115      {
116        shift++;
117        z <<= 1;
118      } while ( z < ( 1L << 27 ) );
119
120      vec->x = x << shift;
121      vec->y = y << shift;
122    }
123    else if ( z > ( 1L << 28 ) )
124    {
125      do
126      {
127        shift++;
128        z >>= 1;
129      } while ( z > ( 1L << 28 ) );
130
131      vec->x = x >> shift;
132      vec->y = y >> shift;
133      shift  = -shift;
134    }
135    return shift;
136  }
137
138
139  static void
140  ft_trig_pseudo_rotate( FT_Vector*  vec,
141                         FT_Angle    theta )
142  {
143    FT_Int           i;
144    FT_Fixed         x, y, xtemp;
145    const FT_Fixed  *arctanptr;
146
147
148    x = vec->x;
149    y = vec->y;
150
151    /* Get angle between -90 and 90 degrees */
152    while ( theta <= -FT_ANGLE_PI2 )
153    {
154      x = -x;
155      y = -y;
156      theta += FT_ANGLE_PI;
157    }
158
159    while ( theta > FT_ANGLE_PI2 )
160    {
161      x = -x;
162      y = -y;
163      theta -= FT_ANGLE_PI;
164    }
165
166    /* Initial pseudorotation, with left shift */
167    arctanptr = ft_trig_arctan_table;
168
169    if ( theta < 0 )
170    {
171      xtemp  = x + ( y << 1 );
172      y      = y - ( x << 1 );
173      x      = xtemp;
174      theta += *arctanptr++;
175    }
176    else
177    {
178      xtemp  = x - ( y << 1 );
179      y      = y + ( x << 1 );
180      x      = xtemp;
181      theta -= *arctanptr++;
182    }
183
184    /* Subsequent pseudorotations, with right shifts */
185    i = 0;
186    do
187    {
188      if ( theta < 0 )
189      {
190        xtemp  = x + ( y >> i );
191        y      = y - ( x >> i );
192        x      = xtemp;
193        theta += *arctanptr++;
194      }
195      else
196      {
197        xtemp  = x - ( y >> i );
198        y      = y + ( x >> i );
199        x      = xtemp;
200        theta -= *arctanptr++;
201      }
202    } while ( ++i < FT_TRIG_MAX_ITERS );
203
204    vec->x = x;
205    vec->y = y;
206  }
207
208
209  static void
210  ft_trig_pseudo_polarize( FT_Vector*  vec )
211  {
212    FT_Fixed         theta;
213    FT_Fixed         yi, i;
214    FT_Fixed         x, y;
215    const FT_Fixed  *arctanptr;
216
217
218    x = vec->x;
219    y = vec->y;
220
221    /* Get the vector into the right half plane */
222    theta = 0;
223    if ( x < 0 )
224    {
225      x = -x;
226      y = -y;
227      theta = 2 * FT_ANGLE_PI2;
228    }
229
230    if ( y > 0 )
231      theta = - theta;
232
233    arctanptr = ft_trig_arctan_table;
234
235    if ( y < 0 )
236    {
237      /* Rotate positive */
238      yi     = y + ( x << 1 );
239      x      = x - ( y << 1 );
240      y      = yi;
241      theta -= *arctanptr++;  /* Subtract angle */
242    }
243    else
244    {
245      /* Rotate negative */
246      yi     = y - ( x << 1 );
247      x      = x + ( y << 1 );
248      y      = yi;
249      theta += *arctanptr++;  /* Add angle */
250    }
251
252    i = 0;
253    do
254    {
255      if ( y < 0 )
256      {
257        /* Rotate positive */
258        yi     = y + ( x >> i );
259        x      = x - ( y >> i );
260        y      = yi;
261        theta -= *arctanptr++;
262      }
263      else
264      {
265        /* Rotate negative */
266        yi     = y - ( x >> i );
267        x      = x + ( y >> i );
268        y      = yi;
269        theta += *arctanptr++;
270      }
271    } while ( ++i < FT_TRIG_MAX_ITERS );
272
273    /* round theta */
274    if ( theta >= 0 )
275      theta = FT_PAD_ROUND( theta, 32 );
276    else
277      theta = -FT_PAD_ROUND( -theta, 32 );
278
279    vec->x = x;
280    vec->y = theta;
281  }
282
283
284  /* documentation is in fttrigon.h */
285
286  FT_EXPORT_DEF( FT_Fixed )
287  FT_Cos( FT_Angle  angle )
288  {
289    FT_Vector  v;
290
291
292    v.x = FT_TRIG_COSCALE >> 2;
293    v.y = 0;
294    ft_trig_pseudo_rotate( &v, angle );
295
296    return v.x / ( 1 << 12 );
297  }
298
299
300  /* documentation is in fttrigon.h */
301
302  FT_EXPORT_DEF( FT_Fixed )
303  FT_Sin( FT_Angle  angle )
304  {
305    return FT_Cos( FT_ANGLE_PI2 - angle );
306  }
307
308
309  /* documentation is in fttrigon.h */
310
311  FT_EXPORT_DEF( FT_Fixed )
312  FT_Tan( FT_Angle  angle )
313  {
314    FT_Vector  v;
315
316
317    v.x = FT_TRIG_COSCALE >> 2;
318    v.y = 0;
319    ft_trig_pseudo_rotate( &v, angle );
320
321    return FT_DivFix( v.y, v.x );
322  }
323
324
325  /* documentation is in fttrigon.h */
326
327  FT_EXPORT_DEF( FT_Angle )
328  FT_Atan2( FT_Fixed  dx,
329            FT_Fixed  dy )
330  {
331    FT_Vector  v;
332
333
334    if ( dx == 0 && dy == 0 )
335      return 0;
336
337    v.x = dx;
338    v.y = dy;
339    ft_trig_prenorm( &v );
340    ft_trig_pseudo_polarize( &v );
341
342    return v.y;
343  }
344
345
346  /* documentation is in fttrigon.h */
347
348  FT_EXPORT_DEF( void )
349  FT_Vector_Unit( FT_Vector*  vec,
350                  FT_Angle    angle )
351  {
352    vec->x = FT_TRIG_COSCALE >> 2;
353    vec->y = 0;
354    ft_trig_pseudo_rotate( vec, angle );
355    vec->x >>= 12;
356    vec->y >>= 12;
357  }
358
359
360  /* these macros return 0 for positive numbers,
361     and -1 for negative ones */
362#define FT_SIGN_LONG( x )   ( (x) >> ( FT_SIZEOF_LONG * 8 - 1 ) )
363#define FT_SIGN_INT( x )    ( (x) >> ( FT_SIZEOF_INT * 8 - 1 ) )
364#define FT_SIGN_INT32( x )  ( (x) >> 31 )
365#define FT_SIGN_INT16( x )  ( (x) >> 15 )
366
367
368  /* documentation is in fttrigon.h */
369
370  FT_EXPORT_DEF( void )
371  FT_Vector_Rotate( FT_Vector*  vec,
372                    FT_Angle    angle )
373  {
374    FT_Int     shift;
375    FT_Vector  v;
376
377
378    v.x   = vec->x;
379    v.y   = vec->y;
380
381    if ( angle && ( v.x != 0 || v.y != 0 ) )
382    {
383      shift = ft_trig_prenorm( &v );
384      ft_trig_pseudo_rotate( &v, angle );
385      v.x = ft_trig_downscale( v.x );
386      v.y = ft_trig_downscale( v.y );
387
388      if ( shift > 0 )
389      {
390        FT_Int32  half = 1L << ( shift - 1 );
391
392
393        vec->x = ( v.x + half + FT_SIGN_LONG( v.x ) ) >> shift;
394        vec->y = ( v.y + half + FT_SIGN_LONG( v.y ) ) >> shift;
395      }
396      else
397      {
398        shift  = -shift;
399        vec->x = v.x << shift;
400        vec->y = v.y << shift;
401      }
402    }
403  }
404
405
406  /* documentation is in fttrigon.h */
407
408  FT_EXPORT_DEF( FT_Fixed )
409  FT_Vector_Length( FT_Vector*  vec )
410  {
411    FT_Int     shift;
412    FT_Vector  v;
413
414
415    v = *vec;
416
417    /* handle trivial cases */
418    if ( v.x == 0 )
419    {
420      return ( v.y >= 0 ) ? v.y : -v.y;
421    }
422    else if ( v.y == 0 )
423    {
424      return ( v.x >= 0 ) ? v.x : -v.x;
425    }
426
427    /* general case */
428    shift = ft_trig_prenorm( &v );
429    ft_trig_pseudo_polarize( &v );
430
431    v.x = ft_trig_downscale( v.x );
432
433    if ( shift > 0 )
434      return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift;
435
436    return v.x << -shift;
437  }
438
439
440  /* documentation is in fttrigon.h */
441
442  FT_EXPORT_DEF( void )
443  FT_Vector_Polarize( FT_Vector*  vec,
444                      FT_Fixed   *length,
445                      FT_Angle   *angle )
446  {
447    FT_Int     shift;
448    FT_Vector  v;
449
450
451    v = *vec;
452
453    if ( v.x == 0 && v.y == 0 )
454      return;
455
456    shift = ft_trig_prenorm( &v );
457    ft_trig_pseudo_polarize( &v );
458
459    v.x = ft_trig_downscale( v.x );
460
461    *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
462    *angle  = v.y;
463  }
464
465
466  /* documentation is in fttrigon.h */
467
468  FT_EXPORT_DEF( void )
469  FT_Vector_From_Polar( FT_Vector*  vec,
470                        FT_Fixed    length,
471                        FT_Angle    angle )
472  {
473    vec->x = length;
474    vec->y = 0;
475
476    FT_Vector_Rotate( vec, angle );
477  }
478
479
480  /* documentation is in fttrigon.h */
481
482  FT_EXPORT_DEF( FT_Angle )
483  FT_Angle_Diff( FT_Angle  angle1,
484                 FT_Angle  angle2 )
485  {
486    FT_Angle  delta = angle2 - angle1;
487
488
489    delta %= FT_ANGLE_2PI;
490    if ( delta < 0 )
491      delta += FT_ANGLE_2PI;
492
493    if ( delta > FT_ANGLE_PI )
494      delta -= FT_ANGLE_2PI;
495
496    return delta;
497  }
498
499
500/* END */
Note: See TracBrowser for help on using the repository browser.