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