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