misc/libfreetype/src/base/fttrigon.c
changeset 5172 88f2e05288ba
equal deleted inserted replaced
5171:f9283dc4860d 5172:88f2e05288ba
       
     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 */