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