src/base/fttrigon.c

   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 */