extension/SDL2_ttf-2.0.14/external/freetype-2.4.12/src/base/fttrigon.c

   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 <ft2build.h>
  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 */