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