apdf/freetype2/base/fttrigon.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  fttrigon.c                                                             */
   4 /*                                                                         */
   5 /*    FreeType trigonometric functions (body).                             */
   6 /*                                                                         */
   7 /*  Copyright 2001 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_TRIGONOMETRY_H
  21
  22
  23   /* the following is 0.2715717684432231 * 2^30 */
  24 #define FT_TRIG_COSCALE  0x11616E8EUL
  25
  26   /* this table was generated for FT_PI = 180L << 16, i.e. degrees */
  27 #define FT_TRIG_MAX_ITERS  23
  28
  29   static const FT_Fixed
  30   ft_trig_arctan_table[24] =
  31   {
  32     4157273L, 2949120L, 1740967L, 919879L, 466945L, 234379L, 117304L,
  33     58666L, 29335L, 14668L, 7334L, 3667L, 1833L, 917L, 458L, 229L, 115L,
  34     57L, 29L, 14L, 7L, 4L, 2L, 1L
  35   };
  36
  37   /* the Cordic shrink factor, multiplied by 2^32 */
  38 #define FT_TRIG_SCALE    1166391785UL  /* 0x4585BA38UL */
  39
  40
  41 #ifdef FT_CONFIG_HAS_INT64
  42
  43   /* multiply a given value by the CORDIC shrink factor */
  44   static FT_Fixed
  45   ft_trig_downscale( FT_Fixed  val )
  46   {
  47     FT_Fixed  s;
  48     FT_Int64  v;
  49
  50
  51     s   = val;
  52     val = ( val >= 0 ) ? val : -val;
  53
  54     v   = ( val * (FT_Int64)FT_TRIG_SCALE ) + 0x100000000UL;
  55     val = (FT_Fixed)( v >> 32 );
  56
  57     return ( s >= 0 ) ? val : -val;
  58   }
  59
  60 #else /* !FT_CONFIG_HAS_INT64 */
  61
  62   /* multiply a given value by the CORDIC shrink factor */
  63   static FT_Fixed
  64   ft_trig_downscale( FT_Fixed  val )
  65   {
  66     FT_Fixed   s;
  67     FT_UInt32  v1, v2, k1, k2, hi, lo1, lo2, lo3;
  68
  69
  70     s   = val;
  71     val = ( val >= 0 ) ? val : -val;
  72
  73     v1 = (FT_UInt32)val >> 16;
  74     v2 = (FT_UInt32)val & 0xFFFF;
  75
  76     k1 = FT_TRIG_SCALE >> 16;       /* constant */
  77     k2 = FT_TRIG_SCALE & 0xFFFF;    /* constant */
  78
  79     hi   = k1 * v1;
  80     lo1  = k1 * v2 + k2 * v1;       /* can't overflow */
  81
  82     lo2  = ( k2 * v2 ) >> 16;
  83     lo3  = ( lo1 >= lo2 ) ? lo1 : lo2;
  84     lo1 += lo2;
  85
  86     hi  += lo1 >> 16;
  87     if ( lo1 < lo3 )
  88       hi += 0x10000UL;
  89
  90     val  = (FT_Fixed)hi;
  91
  92     return ( s >= 0 ) ? val : -val;
  93   }
  94
  95 #endif /* !FT_CONFIG_HAS_INT64 */
  96
  97
  98   static FT_Int
  99   ft_trig_prenorm( FT_Vector*  vec )
 100   {
 101     FT_Fixed  x, y, z;
 102     FT_Int    shift;
 103
 104
 105     x = vec->x;
 106     y = vec->y;
 107
 108     z     = ( ( x >= 0 ) ? x : - x ) | ( (y >= 0) ? y : -y );
 109     shift = 0;
 110
 111     if ( z < ( 1L << 27 ) )
 112     {
 113       do
 114       {
 115         shift++;
 116         z <<= 1;
 117       } while ( z < ( 1L << 27 ) );
 118
 119       vec->x = x << shift;
 120       vec->y = y << shift;
 121     }
 122     else if ( z > ( 1L << 28 ) )
 123     {
 124       do
 125       {
 126         shift++;
 127         z >>= 1;
 128       } while ( z > ( 1L << 28 ) );
 129
 130       vec->x = x >> shift;
 131       vec->y = y >> shift;
 132       shift  = -shift;
 133     }
 134     return shift;
 135   }
 136
 137
 138   static void
 139   ft_trig_pseudo_rotate( FT_Vector*  vec,
 140                          FT_Angle    theta )
 141   {
 142     FT_Int           i;
 143     FT_Fixed         x, y, xtemp;
 144     const FT_Fixed  *arctanptr;
 145
 146
 147     x = vec->x;
 148     y = vec->y;
 149
 150     /* Get angle between -90 and 90 degrees */
 151     while ( theta <= -FT_ANGLE_PI2 )
 152     {
 153       x = -x;
 154       y = -y;
 155       theta += FT_ANGLE_PI;
 156     }
 157
 158     while ( theta > FT_ANGLE_PI2 )
 159     {
 160       x = -x;
 161       y = -y;
 162       theta -= FT_ANGLE_PI;
 163     }
 164
 165     /* Initial pseudorotation, with left shift */
 166     arctanptr = ft_trig_arctan_table;
 167
 168     if ( theta < 0 )
 169     {
 170       xtemp  = x + ( y << 1 );
 171       y      = y - ( x << 1 );
 172       x      = xtemp;
 173       theta += *arctanptr++;
 174     }
 175     else
 176     {
 177       xtemp  = x - ( y << 1 );
 178       y      = y + ( x << 1 );
 179       x      = xtemp;
 180       theta -= *arctanptr++;
 181     }
 182
 183     /* Subsequent pseudorotations, with right shifts */
 184     i = 0;
 185     do
 186     {
 187       if ( theta < 0 )
 188       {
 189         xtemp  = x + ( y >> i );
 190         y      = y - ( x >> i );
 191         x      = xtemp;
 192         theta += *arctanptr++;
 193       }
 194       else
 195       {
 196         xtemp  = x - ( y >> i );
 197         y      = y + ( x >> i );
 198         x      = xtemp;
 199         theta -= *arctanptr++;
 200       }
 201     } while ( ++i < FT_TRIG_MAX_ITERS );
 202
 203     vec->x = x;
 204     vec->y = y;
 205   }
 206
 207
 208   static void
 209   ft_trig_pseudo_polarize( FT_Vector*  vec )
 210   {
 211     FT_Fixed         theta;
 212     FT_Fixed         yi, i;
 213     FT_Fixed         x, y;
 214     const FT_Fixed  *arctanptr;
 215
 216
 217     x = vec->x;
 218     y = vec->y;
 219
 220     /* Get the vector into the right half plane */
 221     theta = 0;
 222     if ( x < 0 )
 223     {
 224       x = -x;
 225       y = -y;
 226       theta = 2 * FT_ANGLE_PI2;
 227     }
 228
 229     if ( y > 0 )
 230       theta = - theta;
 231
 232     arctanptr = ft_trig_arctan_table;
 233
 234     if ( y < 0 )
 235     {
 236       /* Rotate positive */
 237       yi     = y + ( x << 1 );
 238       x      = x - ( y << 1 );
 239       y      = yi;
 240       theta -= *arctanptr++;  /* Subtract angle */
 241     }
 242     else
 243     {
 244       /* Rotate negative */
 245       yi     = y - ( x << 1 );
 246       x      = x + ( y << 1 );
 247       y      = yi;
 248       theta += *arctanptr++;  /* Add angle */
 249     }
 250
 251     i = 0;
 252     do
 253     {
 254       if ( y < 0 )
 255       {
 256         /* Rotate positive */
 257         yi     = y + ( x >> i );
 258         x      = x - ( y >> i );
 259         y      = yi;
 260         theta -= *arctanptr++;
 261       }
 262       else
 263       {
 264         /* Rotate negative */
 265         yi     = y - ( x >> i );
 266         x      = x + ( y >> i );
 267         y      = yi;
 268         theta += *arctanptr++;
 269       }
 270     } while ( ++i < FT_TRIG_MAX_ITERS );
 271
 272     /* round theta */
 273     if ( theta >= 0 )
 274       theta = ( theta + 16 ) & -32;
 275     else
 276       theta = - (( -theta + 16 ) & -32);
 277
 278     vec->x = x;
 279     vec->y = theta;
 280   }
 281
 282
 283   /* documentation is in fttrigon.h */
 284
 285   FT_EXPORT_DEF( FT_Fixed )
 286   FT_Cos( FT_Angle  angle )
 287   {
 288     FT_Vector  v;
 289
 290
 291     v.x = FT_TRIG_COSCALE >> 2;
 292     v.y = 0;
 293     ft_trig_pseudo_rotate( &v, angle );
 294
 295     return v.x / ( 1 << 12 );
 296   }
 297
 298
 299   /* documentation is in fttrigon.h */
 300
 301   FT_EXPORT_DEF( FT_Fixed )
 302   FT_Sin( FT_Angle  angle )
 303   {
 304     return FT_Cos( FT_ANGLE_PI2 - angle );
 305   }
 306
 307
 308   /* documentation is in fttrigon.h */
 309
 310   FT_EXPORT_DEF( FT_Fixed )
 311   FT_Tan( FT_Angle  angle )
 312   {
 313     FT_Vector  v;
 314
 315
 316     v.x = FT_TRIG_COSCALE >> 2;
 317     v.y = 0;
 318     ft_trig_pseudo_rotate( &v, angle );
 319
 320     return FT_DivFix( v.y, v.x );
 321   }
 322
 323
 324   /* documentation is in fttrigon.h */
 325
 326   FT_EXPORT_DEF( FT_Angle )
 327   FT_Atan2( FT_Fixed  dx,
 328             FT_Fixed  dy )
 329   {
 330     FT_Vector  v;
 331
 332
 333     if ( dx == 0 && dy == 0 )
 334       return 0;
 335
 336     v.x = dx;
 337     v.y = dy;
 338     ft_trig_prenorm( &v );
 339     ft_trig_pseudo_polarize( &v );
 340
 341     return v.y;
 342   }
 343
 344
 345   /* documentation is in fttrigon.h */
 346
 347   FT_EXPORT_DEF( void )
 348   FT_Vector_Unit( FT_Vector*  vec,
 349                   FT_Angle    angle )
 350   {
 351     vec->x = FT_TRIG_COSCALE >> 2;
 352     vec->y = 0;
 353     ft_trig_pseudo_rotate( vec, angle );
 354     vec->x >>= 12;
 355     vec->y >>= 12;
 356   }
 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         vec->x = v.x >> shift;
 382         vec->y = v.y >> shift;
 383       }
 384       else
 385       {
 386         shift  = -shift;
 387         vec->x = v.x << shift;
 388         vec->y = v.y << shift;
 389       }
 390     }
 391   }
 392
 393
 394   /* documentation is in fttrigon.h */
 395
 396   FT_EXPORT_DEF( FT_Fixed )
 397   FT_Vector_Length( FT_Vector*  vec )
 398   {
 399     FT_Int     shift;
 400     FT_Vector  v;
 401
 402
 403     v = *vec;
 404
 405     /* handle trivial cases */
 406     if ( v.x == 0 )
 407     {
 408       return ( v.y >= 0 ) ? v.y : -v.y;
 409     }
 410     else if ( v.y == 0 )
 411     {
 412       return ( v.x >= 0 ) ? v.x : -v.x;
 413     }
 414
 415     /* general case */
 416     shift = ft_trig_prenorm( &v );
 417     ft_trig_pseudo_polarize( &v );
 418
 419     v.x = ft_trig_downscale( v.x );
 420
 421     if ( shift > 0 )
 422       return ( v.x + ( 1 << ( shift - 1 ) ) ) >> shift;
 423
 424     return v.x << -shift;
 425   }
 426
 427
 428   /* documentation is in fttrigon.h */
 429
 430   FT_EXPORT_DEF( void )
 431   FT_Vector_Polarize( FT_Vector*  vec,
 432                       FT_Fixed   *length,
 433                       FT_Angle   *angle )
 434   {
 435     FT_Int     shift;
 436     FT_Vector  v;
 437
 438
 439     v = *vec;
 440
 441     if ( v.x == 0 && v.y == 0 )
 442       return;
 443
 444     shift = ft_trig_prenorm( &v );
 445     ft_trig_pseudo_polarize( &v );
 446
 447     v.x = ft_trig_downscale( v.x );
 448
 449     *length = ( shift >= 0 ) ? ( v.x >> shift ) : ( v.x << -shift );
 450     *angle  = v.y;
 451   }
 452
 453
 454 /* END */