1 /***************************************************************************/ 2 /* */ 3 /* ftcalc.c */ 4 /* */ 5 /* Arithmetic computations (body). */ 6 /* */ 7 /* Copyright 1996-2015 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 /* Support for 1-complement arithmetic has been totally dropped in this */ 21 /* release. You can still write your own code if you need it. */ 22 /* */ 23 /*************************************************************************/ 24 25 /*************************************************************************/ 26 /* */ 27 /* Implementing basic computation routines. */ 28 /* */ 29 /* FT_MulDiv(), FT_MulFix(), FT_DivFix(), FT_RoundFix(), FT_CeilFix(), */ 30 /* and FT_FloorFix() are declared in freetype.h. */ 31 /* */ 32 /*************************************************************************/ 33 34 35 #include <ft2build.h> 36 #include FT_GLYPH_H 37 #include FT_TRIGONOMETRY_H 38 #include FT_INTERNAL_CALC_H 39 #include FT_INTERNAL_DEBUG_H 40 #include FT_INTERNAL_OBJECTS_H 41 42 43 #ifdef FT_MULFIX_ASSEMBLER 44 #undef FT_MulFix 45 #endif 46 47 /* we need to emulate a 64-bit data type if a real one isn't available */ 48 49 #ifndef FT_LONG64 50 51 typedef struct FT_Int64_ 52 { 53 FT_UInt32 lo; 54 FT_UInt32 hi; 55 56 } FT_Int64; 57 58 #endif /* !FT_LONG64 */ 59 60 61 /*************************************************************************/ 62 /* */ 63 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ 64 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ 65 /* messages during execution. */ 66 /* */ 67 #undef FT_COMPONENT 68 #define FT_COMPONENT trace_calc 69 70 71 /* transfer sign leaving a positive number */ 72 #define FT_MOVE_SIGN( x, s ) \ 73 FT_BEGIN_STMNT \ 74 if ( x < 0 ) \ 75 { \ 76 x = -x; \ 77 s = -s; \ 78 } \ 79 FT_END_STMNT 80 81 /* The following three functions are available regardless of whether */ 82 /* FT_LONG64 is defined. */ 83 84 /* documentation is in freetype.h */ 85 86 FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix(FT_Fixed a)87 FT_RoundFix( FT_Fixed a ) 88 { 89 return a >= 0 ? ( a + 0x8000L ) & ~0xFFFFL 90 : -((-a + 0x8000L ) & ~0xFFFFL ); 91 } 92 93 94 /* documentation is in freetype.h */ 95 96 FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix(FT_Fixed a)97 FT_CeilFix( FT_Fixed a ) 98 { 99 return a >= 0 ? ( a + 0xFFFFL ) & ~0xFFFFL 100 : -((-a + 0xFFFFL ) & ~0xFFFFL ); 101 } 102 103 104 /* documentation is in freetype.h */ 105 106 FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix(FT_Fixed a)107 FT_FloorFix( FT_Fixed a ) 108 { 109 return a >= 0 ? a & ~0xFFFFL 110 : -((-a) & ~0xFFFFL ); 111 } 112 113 #ifndef FT_MSB 114 115 FT_BASE_DEF ( FT_Int ) FT_MSB(FT_UInt32 z)116 FT_MSB( FT_UInt32 z ) 117 { 118 FT_Int shift = 0; 119 120 121 /* determine msb bit index in `shift' */ 122 if ( z & 0xFFFF0000UL ) 123 { 124 z >>= 16; 125 shift += 16; 126 } 127 if ( z & 0x0000FF00UL ) 128 { 129 z >>= 8; 130 shift += 8; 131 } 132 if ( z & 0x000000F0UL ) 133 { 134 z >>= 4; 135 shift += 4; 136 } 137 if ( z & 0x0000000CUL ) 138 { 139 z >>= 2; 140 shift += 2; 141 } 142 if ( z & 0x00000002UL ) 143 { 144 /* z >>= 1; */ 145 shift += 1; 146 } 147 148 return shift; 149 } 150 151 #endif /* !FT_MSB */ 152 153 154 /* documentation is in ftcalc.h */ 155 156 FT_BASE_DEF( FT_Fixed ) FT_Hypot(FT_Fixed x,FT_Fixed y)157 FT_Hypot( FT_Fixed x, 158 FT_Fixed y ) 159 { 160 FT_Vector v; 161 162 163 v.x = x; 164 v.y = y; 165 166 return FT_Vector_Length( &v ); 167 } 168 169 170 #ifdef FT_LONG64 171 172 173 /* documentation is in freetype.h */ 174 175 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a_,FT_Long b_,FT_Long c_)176 FT_MulDiv( FT_Long a_, 177 FT_Long b_, 178 FT_Long c_ ) 179 { 180 FT_Int s = 1; 181 FT_UInt64 a, b, c, d; 182 FT_Long d_; 183 184 185 FT_MOVE_SIGN( a_, s ); 186 FT_MOVE_SIGN( b_, s ); 187 FT_MOVE_SIGN( c_, s ); 188 189 a = (FT_UInt64)a_; 190 b = (FT_UInt64)b_; 191 c = (FT_UInt64)c_; 192 193 d = c > 0 ? ( a * b + ( c >> 1 ) ) / c 194 : 0x7FFFFFFFUL; 195 196 d_ = (FT_Long)d; 197 198 return s < 0 ? -d_ : d_; 199 } 200 201 202 /* documentation is in ftcalc.h */ 203 204 FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round(FT_Long a_,FT_Long b_,FT_Long c_)205 FT_MulDiv_No_Round( FT_Long a_, 206 FT_Long b_, 207 FT_Long c_ ) 208 { 209 FT_Int s = 1; 210 FT_UInt64 a, b, c, d; 211 FT_Long d_; 212 213 214 FT_MOVE_SIGN( a_, s ); 215 FT_MOVE_SIGN( b_, s ); 216 FT_MOVE_SIGN( c_, s ); 217 218 a = (FT_UInt64)a_; 219 b = (FT_UInt64)b_; 220 c = (FT_UInt64)c_; 221 222 d = c > 0 ? a * b / c 223 : 0x7FFFFFFFUL; 224 225 d_ = (FT_Long)d; 226 227 return s < 0 ? -d_ : d_; 228 } 229 230 231 /* documentation is in freetype.h */ 232 233 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a_,FT_Long b_)234 FT_MulFix( FT_Long a_, 235 FT_Long b_ ) 236 { 237 #ifdef FT_MULFIX_ASSEMBLER 238 239 return FT_MULFIX_ASSEMBLER( a_, b_ ); 240 241 #else 242 243 FT_Int s = 1; 244 FT_UInt64 a, b, c; 245 FT_Long c_; 246 247 248 FT_MOVE_SIGN( a_, s ); 249 FT_MOVE_SIGN( b_, s ); 250 251 a = (FT_UInt64)a_; 252 b = (FT_UInt64)b_; 253 254 c = ( a * b + 0x8000UL ) >> 16; 255 256 c_ = (FT_Long)c; 257 258 return s < 0 ? -c_ : c_; 259 260 #endif /* FT_MULFIX_ASSEMBLER */ 261 } 262 263 264 /* documentation is in freetype.h */ 265 266 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a_,FT_Long b_)267 FT_DivFix( FT_Long a_, 268 FT_Long b_ ) 269 { 270 FT_Int s = 1; 271 FT_UInt64 a, b, q; 272 FT_Long q_; 273 274 275 FT_MOVE_SIGN( a_, s ); 276 FT_MOVE_SIGN( b_, s ); 277 278 a = (FT_UInt64)a_; 279 b = (FT_UInt64)b_; 280 281 q = b > 0 ? ( ( a << 16 ) + ( b >> 1 ) ) / b 282 : 0x7FFFFFFFUL; 283 284 q_ = (FT_Long)q; 285 286 return s < 0 ? -q_ : q_; 287 } 288 289 290 #else /* !FT_LONG64 */ 291 292 293 static void ft_multo64(FT_UInt32 x,FT_UInt32 y,FT_Int64 * z)294 ft_multo64( FT_UInt32 x, 295 FT_UInt32 y, 296 FT_Int64 *z ) 297 { 298 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; 299 300 301 lo1 = x & 0x0000FFFFU; hi1 = x >> 16; 302 lo2 = y & 0x0000FFFFU; hi2 = y >> 16; 303 304 lo = lo1 * lo2; 305 i1 = lo1 * hi2; 306 i2 = lo2 * hi1; 307 hi = hi1 * hi2; 308 309 /* Check carry overflow of i1 + i2 */ 310 i1 += i2; 311 hi += (FT_UInt32)( i1 < i2 ) << 16; 312 313 hi += i1 >> 16; 314 i1 = i1 << 16; 315 316 /* Check carry overflow of i1 + lo */ 317 lo += i1; 318 hi += ( lo < i1 ); 319 320 z->lo = lo; 321 z->hi = hi; 322 } 323 324 325 static FT_UInt32 ft_div64by32(FT_UInt32 hi,FT_UInt32 lo,FT_UInt32 y)326 ft_div64by32( FT_UInt32 hi, 327 FT_UInt32 lo, 328 FT_UInt32 y ) 329 { 330 FT_UInt32 r, q; 331 FT_Int i; 332 333 334 if ( hi >= y ) 335 return (FT_UInt32)0x7FFFFFFFL; 336 337 /* We shift as many bits as we can into the high register, perform */ 338 /* 32-bit division with modulo there, then work through the remaining */ 339 /* bits with long division. This optimization is especially noticeable */ 340 /* for smaller dividends that barely use the high register. */ 341 342 i = 31 - FT_MSB( hi ); 343 r = ( hi << i ) | ( lo >> ( 32 - i ) ); lo <<= i; /* left 64-bit shift */ 344 q = r / y; 345 r -= q * y; /* remainder */ 346 347 i = 32 - i; /* bits remaining in low register */ 348 do 349 { 350 q <<= 1; 351 r = ( r << 1 ) | ( lo >> 31 ); lo <<= 1; 352 353 if ( r >= y ) 354 { 355 r -= y; 356 q |= 1; 357 } 358 } while ( --i ); 359 360 return q; 361 } 362 363 364 static void FT_Add64(FT_Int64 * x,FT_Int64 * y,FT_Int64 * z)365 FT_Add64( FT_Int64* x, 366 FT_Int64* y, 367 FT_Int64 *z ) 368 { 369 FT_UInt32 lo, hi; 370 371 372 lo = x->lo + y->lo; 373 hi = x->hi + y->hi + ( lo < x->lo ); 374 375 z->lo = lo; 376 z->hi = hi; 377 } 378 379 380 /* The FT_MulDiv function has been optimized thanks to ideas from */ 381 /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */ 382 /* a rather common case when everything fits within 32-bits. */ 383 /* */ 384 /* We compute 'a*b+c/2', then divide it by 'c' (all positive values). */ 385 /* */ 386 /* The product of two positive numbers never exceeds the square of */ 387 /* its mean values. Therefore, we always avoid the overflow by */ 388 /* imposing */ 389 /* */ 390 /* (a + b) / 2 <= sqrt(X - c/2) , */ 391 /* */ 392 /* where X = 2^32 - 1, the maximum unsigned 32-bit value, and using */ 393 /* unsigned arithmetic. Now we replace `sqrt' with a linear function */ 394 /* that is smaller or equal for all values of c in the interval */ 395 /* [0;X/2]; it should be equal to sqrt(X) and sqrt(3X/4) at the */ 396 /* endpoints. Substituting the linear solution and explicit numbers */ 397 /* we get */ 398 /* */ 399 /* a + b <= 131071.99 - c / 122291.84 . */ 400 /* */ 401 /* In practice, we should use a faster and even stronger inequality */ 402 /* */ 403 /* a + b <= 131071 - (c >> 16) */ 404 /* */ 405 /* or, alternatively, */ 406 /* */ 407 /* a + b <= 129894 - (c >> 17) . */ 408 /* */ 409 /* FT_MulFix, on the other hand, is optimized for a small value of */ 410 /* the first argument, when the second argument can be much larger. */ 411 /* This can be achieved by scaling the second argument and the limit */ 412 /* in the above inequalities. For example, */ 413 /* */ 414 /* a + (b >> 8) <= (131071 >> 4) */ 415 /* */ 416 /* covers the practical range of use. The actual test below is a bit */ 417 /* tighter to avoid the border case overflows. */ 418 /* */ 419 /* In the case of FT_DivFix, the exact overflow check */ 420 /* */ 421 /* a << 16 <= X - c/2 */ 422 /* */ 423 /* is scaled down by 2^16 and we use */ 424 /* */ 425 /* a <= 65535 - (c >> 17) . */ 426 427 /* documentation is in freetype.h */ 428 429 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a_,FT_Long b_,FT_Long c_)430 FT_MulDiv( FT_Long a_, 431 FT_Long b_, 432 FT_Long c_ ) 433 { 434 FT_Int s = 1; 435 FT_UInt32 a, b, c; 436 437 438 /* XXX: this function does not allow 64-bit arguments */ 439 440 if ( a_ == 0 || b_ == c_ ) 441 return a_; 442 443 FT_MOVE_SIGN( a_, s ); 444 FT_MOVE_SIGN( b_, s ); 445 FT_MOVE_SIGN( c_, s ); 446 447 a = (FT_UInt32)a_; 448 b = (FT_UInt32)b_; 449 c = (FT_UInt32)c_; 450 451 if ( c == 0 ) 452 a = 0x7FFFFFFFUL; 453 454 else if ( a + b <= 129894UL - ( c >> 17 ) ) 455 a = ( a * b + ( c >> 1 ) ) / c; 456 457 else 458 { 459 FT_Int64 temp, temp2; 460 461 462 ft_multo64( a, b, &temp ); 463 464 temp2.hi = 0; 465 temp2.lo = c >> 1; 466 467 FT_Add64( &temp, &temp2, &temp ); 468 469 /* last attempt to ditch long division */ 470 a = temp.hi == 0 ? temp.lo / c 471 : ft_div64by32( temp.hi, temp.lo, c ); 472 } 473 474 a_ = (FT_Long)a; 475 476 return s < 0 ? -a_ : a_; 477 } 478 479 480 FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round(FT_Long a_,FT_Long b_,FT_Long c_)481 FT_MulDiv_No_Round( FT_Long a_, 482 FT_Long b_, 483 FT_Long c_ ) 484 { 485 FT_Int s = 1; 486 FT_UInt32 a, b, c; 487 488 489 /* XXX: this function does not allow 64-bit arguments */ 490 491 if ( a_ == 0 || b_ == c_ ) 492 return a_; 493 494 FT_MOVE_SIGN( a_, s ); 495 FT_MOVE_SIGN( b_, s ); 496 FT_MOVE_SIGN( c_, s ); 497 498 a = (FT_UInt32)a_; 499 b = (FT_UInt32)b_; 500 c = (FT_UInt32)c_; 501 502 if ( c == 0 ) 503 a = 0x7FFFFFFFUL; 504 505 else if ( a + b <= 131071UL ) 506 a = a * b / c; 507 508 else 509 { 510 FT_Int64 temp; 511 512 513 ft_multo64( a, b, &temp ); 514 515 /* last attempt to ditch long division */ 516 a = temp.hi == 0 ? temp.lo / c 517 : ft_div64by32( temp.hi, temp.lo, c ); 518 } 519 520 a_ = (FT_Long)a; 521 522 return s < 0 ? -a_ : a_; 523 } 524 525 526 /* documentation is in freetype.h */ 527 528 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a_,FT_Long b_)529 FT_MulFix( FT_Long a_, 530 FT_Long b_ ) 531 { 532 #ifdef FT_MULFIX_ASSEMBLER 533 534 return FT_MULFIX_ASSEMBLER( a_, b_ ); 535 536 #elif 0 537 538 /* 539 * This code is nonportable. See comment below. 540 * 541 * However, on a platform where right-shift of a signed quantity fills 542 * the leftmost bits by copying the sign bit, it might be faster. 543 */ 544 545 FT_Long sa, sb; 546 FT_UInt32 a, b; 547 548 549 if ( a_ == 0 || b_ == 0x10000L ) 550 return a_; 551 552 /* 553 * This is a clever way of converting a signed number `a' into its 554 * absolute value (stored back into `a') and its sign. The sign is 555 * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a' 556 * was negative. (Similarly for `b' and `sb'). 557 * 558 * Unfortunately, it doesn't work (at least not portably). 559 * 560 * It makes the assumption that right-shift on a negative signed value 561 * fills the leftmost bits by copying the sign bit. This is wrong. 562 * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206, 563 * the result of right-shift of a negative signed value is 564 * implementation-defined. At least one implementation fills the 565 * leftmost bits with 0s (i.e., it is exactly the same as an unsigned 566 * right shift). This means that when `a' is negative, `sa' ends up 567 * with the value 1 rather than -1. After that, everything else goes 568 * wrong. 569 */ 570 sa = ( a_ >> ( sizeof ( a_ ) * 8 - 1 ) ); 571 a = ( a_ ^ sa ) - sa; 572 sb = ( b_ >> ( sizeof ( b_ ) * 8 - 1 ) ); 573 b = ( b_ ^ sb ) - sb; 574 575 a = (FT_UInt32)a_; 576 b = (FT_UInt32)b_; 577 578 if ( a + ( b >> 8 ) <= 8190UL ) 579 a = ( a * b + 0x8000U ) >> 16; 580 else 581 { 582 FT_UInt32 al = a & 0xFFFFUL; 583 584 585 a = ( a >> 16 ) * b + al * ( b >> 16 ) + 586 ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); 587 } 588 589 sa ^= sb; 590 a = ( a ^ sa ) - sa; 591 592 return (FT_Long)a; 593 594 #else /* 0 */ 595 596 FT_Int s = 1; 597 FT_UInt32 a, b; 598 599 600 /* XXX: this function does not allow 64-bit arguments */ 601 602 if ( a_ == 0 || b_ == 0x10000L ) 603 return a_; 604 605 FT_MOVE_SIGN( a_, s ); 606 FT_MOVE_SIGN( b_, s ); 607 608 a = (FT_UInt32)a_; 609 b = (FT_UInt32)b_; 610 611 if ( a + ( b >> 8 ) <= 8190UL ) 612 a = ( a * b + 0x8000UL ) >> 16; 613 else 614 { 615 FT_UInt32 al = a & 0xFFFFUL; 616 617 618 a = ( a >> 16 ) * b + al * ( b >> 16 ) + 619 ( ( al * ( b & 0xFFFFUL ) + 0x8000UL ) >> 16 ); 620 } 621 622 a_ = (FT_Long)a; 623 624 return s < 0 ? -a_ : a_; 625 626 #endif /* 0 */ 627 628 } 629 630 631 /* documentation is in freetype.h */ 632 633 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a_,FT_Long b_)634 FT_DivFix( FT_Long a_, 635 FT_Long b_ ) 636 { 637 FT_Int s = 1; 638 FT_UInt32 a, b, q; 639 FT_Long q_; 640 641 642 /* XXX: this function does not allow 64-bit arguments */ 643 644 FT_MOVE_SIGN( a_, s ); 645 FT_MOVE_SIGN( b_, s ); 646 647 a = (FT_UInt32)a_; 648 b = (FT_UInt32)b_; 649 650 if ( b == 0 ) 651 { 652 /* check for division by 0 */ 653 q = 0x7FFFFFFFUL; 654 } 655 else if ( a <= 65535UL - ( b >> 17 ) ) 656 { 657 /* compute result directly */ 658 q = ( ( a << 16 ) + ( b >> 1 ) ) / b; 659 } 660 else 661 { 662 /* we need more bits; we have to do it by hand */ 663 FT_Int64 temp, temp2; 664 665 666 temp.hi = a >> 16; 667 temp.lo = a << 16; 668 temp2.hi = 0; 669 temp2.lo = b >> 1; 670 671 FT_Add64( &temp, &temp2, &temp ); 672 q = ft_div64by32( temp.hi, temp.lo, b ); 673 } 674 675 q_ = (FT_Long)q; 676 677 return s < 0 ? -q_ : q_; 678 } 679 680 681 #endif /* !FT_LONG64 */ 682 683 684 /* documentation is in ftglyph.h */ 685 686 FT_EXPORT_DEF( void ) FT_Matrix_Multiply(const FT_Matrix * a,FT_Matrix * b)687 FT_Matrix_Multiply( const FT_Matrix* a, 688 FT_Matrix *b ) 689 { 690 FT_Fixed xx, xy, yx, yy; 691 692 693 if ( !a || !b ) 694 return; 695 696 xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx ); 697 xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy ); 698 yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx ); 699 yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy ); 700 701 b->xx = xx; b->xy = xy; 702 b->yx = yx; b->yy = yy; 703 } 704 705 706 /* documentation is in ftglyph.h */ 707 708 FT_EXPORT_DEF( FT_Error ) FT_Matrix_Invert(FT_Matrix * matrix)709 FT_Matrix_Invert( FT_Matrix* matrix ) 710 { 711 FT_Pos delta, xx, yy; 712 713 714 if ( !matrix ) 715 return FT_THROW( Invalid_Argument ); 716 717 /* compute discriminant */ 718 delta = FT_MulFix( matrix->xx, matrix->yy ) - 719 FT_MulFix( matrix->xy, matrix->yx ); 720 721 if ( !delta ) 722 return FT_THROW( Invalid_Argument ); /* matrix can't be inverted */ 723 724 matrix->xy = - FT_DivFix( matrix->xy, delta ); 725 matrix->yx = - FT_DivFix( matrix->yx, delta ); 726 727 xx = matrix->xx; 728 yy = matrix->yy; 729 730 matrix->xx = FT_DivFix( yy, delta ); 731 matrix->yy = FT_DivFix( xx, delta ); 732 733 return FT_Err_Ok; 734 } 735 736 737 /* documentation is in ftcalc.h */ 738 739 FT_BASE_DEF( void ) FT_Matrix_Multiply_Scaled(const FT_Matrix * a,FT_Matrix * b,FT_Long scaling)740 FT_Matrix_Multiply_Scaled( const FT_Matrix* a, 741 FT_Matrix *b, 742 FT_Long scaling ) 743 { 744 FT_Fixed xx, xy, yx, yy; 745 746 FT_Long val = 0x10000L * scaling; 747 748 749 if ( !a || !b ) 750 return; 751 752 xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val ); 753 xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val ); 754 yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val ); 755 yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val ); 756 757 b->xx = xx; b->xy = xy; 758 b->yx = yx; b->yy = yy; 759 } 760 761 762 /* documentation is in ftcalc.h */ 763 764 FT_BASE_DEF( void ) FT_Vector_Transform_Scaled(FT_Vector * vector,const FT_Matrix * matrix,FT_Long scaling)765 FT_Vector_Transform_Scaled( FT_Vector* vector, 766 const FT_Matrix* matrix, 767 FT_Long scaling ) 768 { 769 FT_Pos xz, yz; 770 771 FT_Long val = 0x10000L * scaling; 772 773 774 if ( !vector || !matrix ) 775 return; 776 777 xz = FT_MulDiv( vector->x, matrix->xx, val ) + 778 FT_MulDiv( vector->y, matrix->xy, val ); 779 780 yz = FT_MulDiv( vector->x, matrix->yx, val ) + 781 FT_MulDiv( vector->y, matrix->yy, val ); 782 783 vector->x = xz; 784 vector->y = yz; 785 } 786 787 788 #if 0 789 790 /* documentation is in ftcalc.h */ 791 792 FT_BASE_DEF( FT_Int32 ) 793 FT_SqrtFixed( FT_Int32 x ) 794 { 795 FT_UInt32 root, rem_hi, rem_lo, test_div; 796 FT_Int count; 797 798 799 root = 0; 800 801 if ( x > 0 ) 802 { 803 rem_hi = 0; 804 rem_lo = (FT_UInt32)x; 805 count = 24; 806 do 807 { 808 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 ); 809 rem_lo <<= 2; 810 root <<= 1; 811 test_div = ( root << 1 ) + 1; 812 813 if ( rem_hi >= test_div ) 814 { 815 rem_hi -= test_div; 816 root += 1; 817 } 818 } while ( --count ); 819 } 820 821 return (FT_Int32)root; 822 } 823 824 #endif /* 0 */ 825 826 827 /* documentation is in ftcalc.h */ 828 829 FT_BASE_DEF( FT_Int ) ft_corner_orientation(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)830 ft_corner_orientation( FT_Pos in_x, 831 FT_Pos in_y, 832 FT_Pos out_x, 833 FT_Pos out_y ) 834 { 835 FT_Long result; /* avoid overflow on 16-bit system */ 836 837 838 /* deal with the trivial cases quickly */ 839 if ( in_y == 0 ) 840 { 841 if ( in_x >= 0 ) 842 result = out_y; 843 else 844 result = -out_y; 845 } 846 else if ( in_x == 0 ) 847 { 848 if ( in_y >= 0 ) 849 result = -out_x; 850 else 851 result = out_x; 852 } 853 else if ( out_y == 0 ) 854 { 855 if ( out_x >= 0 ) 856 result = in_y; 857 else 858 result = -in_y; 859 } 860 else if ( out_x == 0 ) 861 { 862 if ( out_y >= 0 ) 863 result = -in_x; 864 else 865 result = in_x; 866 } 867 else /* general case */ 868 { 869 #ifdef FT_LONG64 870 871 FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x; 872 873 874 if ( delta == 0 ) 875 result = 0; 876 else 877 result = 1 - 2 * ( delta < 0 ); 878 879 #else 880 881 FT_Int64 z1, z2; 882 883 884 /* XXX: this function does not allow 64-bit arguments */ 885 ft_multo64( (FT_UInt32)in_x, (FT_UInt32)out_y, &z1 ); 886 ft_multo64( (FT_UInt32)in_y, (FT_UInt32)out_x, &z2 ); 887 888 if ( z1.hi > z2.hi ) 889 result = +1; 890 else if ( z1.hi < z2.hi ) 891 result = -1; 892 else if ( z1.lo > z2.lo ) 893 result = +1; 894 else if ( z1.lo < z2.lo ) 895 result = -1; 896 else 897 result = 0; 898 899 #endif 900 } 901 902 /* XXX: only the sign of return value, +1/0/-1 must be used */ 903 return (FT_Int)result; 904 } 905 906 907 /* documentation is in ftcalc.h */ 908 909 FT_BASE_DEF( FT_Int ) ft_corner_is_flat(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)910 ft_corner_is_flat( FT_Pos in_x, 911 FT_Pos in_y, 912 FT_Pos out_x, 913 FT_Pos out_y ) 914 { 915 FT_Pos ax = in_x + out_x; 916 FT_Pos ay = in_y + out_y; 917 918 FT_Pos d_in, d_out, d_hypot; 919 920 921 /* The idea of this function is to compare the length of the */ 922 /* hypotenuse with the `in' and `out' length. The `corner' */ 923 /* represented by `in' and `out' is flat if the hypotenuse's */ 924 /* length isn't too large. */ 925 /* */ 926 /* This approach has the advantage that the angle between */ 927 /* `in' and `out' is not checked. In case one of the two */ 928 /* vectors is `dominant', this is, much larger than the */ 929 /* other vector, we thus always have a flat corner. */ 930 /* */ 931 /* hypotenuse */ 932 /* x---------------------------x */ 933 /* \ / */ 934 /* \ / */ 935 /* in \ / out */ 936 /* \ / */ 937 /* o */ 938 /* Point */ 939 940 d_in = FT_HYPOT( in_x, in_y ); 941 d_out = FT_HYPOT( out_x, out_y ); 942 d_hypot = FT_HYPOT( ax, ay ); 943 944 /* now do a simple length comparison: */ 945 /* */ 946 /* d_in + d_out < 17/16 d_hypot */ 947 948 return ( d_in + d_out - d_hypot ) < ( d_hypot >> 4 ); 949 } 950 951 952 /* END */ 953