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 /* documentation is in fttrigon.h */ 455 456 FT_EXPORT_DEF( void ) 457 FT_Vector_From_Polar( FT_Vector* vec, 458 FT_Fixed length, 459 FT_Angle angle ) 460 { 461 vec->x = length; 462 vec->y = 0; 463 464 FT_Vector_Rotate( vec, angle ); 465 } 466 467 468 /* documentation is in fttrigon.h */ 469 470 FT_EXPORT_DEF( FT_Angle ) 471 FT_Angle_Diff( FT_Angle angle1, 472 FT_Angle angle2 ) 473 { 474 FT_Angle delta = angle2 - angle1; 475 476 delta %= FT_ANGLE_2PI; 477 478 if ( delta > FT_ANGLE_PI ) 479 delta -= FT_ANGLE_2PI; 480 481 return delta; 482 } 483 484 485 /* END */ 486