1 /***************************************************************************/ 2 /* */ 3 /* ftcalc.c */ 4 /* */ 5 /* Arithmetic computations (body). */ 6 /* */ 7 /* Copyright 1996-2006, 2008, 2012-2014 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 #ifndef FT_CONFIG_OPTION_NO_ASSEMBLER 44 /* Provide assembler fragments for performance-critical functions. */ 45 /* These must be defined `static __inline__' with GCC. */ 46 47 #if defined( __CC_ARM ) || defined( __ARMCC__ ) /* RVCT */ 48 49 #define FT_MULFIX_ASSEMBLER FT_MulFix_arm 50 51 /* documentation is in freetype.h */ 52 53 static __inline FT_Int32 FT_MulFix_arm(FT_Int32 a,FT_Int32 b)54 FT_MulFix_arm( FT_Int32 a, 55 FT_Int32 b ) 56 { 57 register FT_Int32 t, t2; 58 59 60 __asm 61 { 62 smull t2, t, b, a /* (lo=t2,hi=t) = a*b */ 63 mov a, t, asr #31 /* a = (hi >> 31) */ 64 add a, a, #0x8000 /* a += 0x8000 */ 65 adds t2, t2, a /* t2 += a */ 66 adc t, t, #0 /* t += carry */ 67 mov a, t2, lsr #16 /* a = t2 >> 16 */ 68 orr a, a, t, lsl #16 /* a |= t << 16 */ 69 } 70 return a; 71 } 72 73 #endif /* __CC_ARM || __ARMCC__ */ 74 75 76 #ifdef __GNUC__ 77 78 #if defined( __arm__ ) && \ 79 ( !defined( __thumb__ ) || defined( __thumb2__ ) ) && \ 80 !( defined( __CC_ARM ) || defined( __ARMCC__ ) ) 81 82 #define FT_MULFIX_ASSEMBLER FT_MulFix_arm 83 84 /* documentation is in freetype.h */ 85 86 static __inline__ FT_Int32 FT_MulFix_arm(FT_Int32 a,FT_Int32 b)87 FT_MulFix_arm( FT_Int32 a, 88 FT_Int32 b ) 89 { 90 register FT_Int32 t, t2; 91 92 93 __asm__ __volatile__ ( 94 "smull %1, %2, %4, %3\n\t" /* (lo=%1,hi=%2) = a*b */ 95 "mov %0, %2, asr #31\n\t" /* %0 = (hi >> 31) */ 96 #if defined( __clang__ ) && defined( __thumb2__ ) 97 "add.w %0, %0, #0x8000\n\t" /* %0 += 0x8000 */ 98 #else 99 "add %0, %0, #0x8000\n\t" /* %0 += 0x8000 */ 100 #endif 101 "adds %1, %1, %0\n\t" /* %1 += %0 */ 102 "adc %2, %2, #0\n\t" /* %2 += carry */ 103 "mov %0, %1, lsr #16\n\t" /* %0 = %1 >> 16 */ 104 "orr %0, %0, %2, lsl #16\n\t" /* %0 |= %2 << 16 */ 105 : "=r"(a), "=&r"(t2), "=&r"(t) 106 : "r"(a), "r"(b) 107 : "cc" ); 108 return a; 109 } 110 111 #endif /* __arm__ && */ 112 /* ( __thumb2__ || !__thumb__ ) && */ 113 /* !( __CC_ARM || __ARMCC__ ) */ 114 115 116 #if defined( __i386__ ) 117 118 #define FT_MULFIX_ASSEMBLER FT_MulFix_i386 119 120 /* documentation is in freetype.h */ 121 122 static __inline__ FT_Int32 FT_MulFix_i386(FT_Int32 a,FT_Int32 b)123 FT_MulFix_i386( FT_Int32 a, 124 FT_Int32 b ) 125 { 126 register FT_Int32 result; 127 128 129 __asm__ __volatile__ ( 130 "imul %%edx\n" 131 "movl %%edx, %%ecx\n" 132 "sarl $31, %%ecx\n" 133 "addl $0x8000, %%ecx\n" 134 "addl %%ecx, %%eax\n" 135 "adcl $0, %%edx\n" 136 "shrl $16, %%eax\n" 137 "shll $16, %%edx\n" 138 "addl %%edx, %%eax\n" 139 : "=a"(result), "=d"(b) 140 : "a"(a), "d"(b) 141 : "%ecx", "cc" ); 142 return result; 143 } 144 145 #endif /* i386 */ 146 147 #endif /* __GNUC__ */ 148 149 150 #ifdef _MSC_VER /* Visual C++ */ 151 152 #ifdef _M_IX86 153 154 #define FT_MULFIX_ASSEMBLER FT_MulFix_i386 155 156 /* documentation is in freetype.h */ 157 158 static __inline FT_Int32 FT_MulFix_i386(FT_Int32 a,FT_Int32 b)159 FT_MulFix_i386( FT_Int32 a, 160 FT_Int32 b ) 161 { 162 register FT_Int32 result; 163 164 __asm 165 { 166 mov eax, a 167 mov edx, b 168 imul edx 169 mov ecx, edx 170 sar ecx, 31 171 add ecx, 8000h 172 add eax, ecx 173 adc edx, 0 174 shr eax, 16 175 shl edx, 16 176 add eax, edx 177 mov result, eax 178 } 179 return result; 180 } 181 182 #endif /* _M_IX86 */ 183 184 #endif /* _MSC_VER */ 185 186 187 #if defined( __GNUC__ ) && defined( __x86_64__ ) 188 189 #define FT_MULFIX_ASSEMBLER FT_MulFix_x86_64 190 191 static __inline__ FT_Int32 FT_MulFix_x86_64(FT_Int32 a,FT_Int32 b)192 FT_MulFix_x86_64( FT_Int32 a, 193 FT_Int32 b ) 194 { 195 /* Temporarily disable the warning that C90 doesn't support */ 196 /* `long long'. */ 197 #if ( __GNUC__ > 4 ) || ( ( __GNUC__ == 4 ) && ( __GNUC_MINOR__ >= 6 ) ) 198 #pragma GCC diagnostic push 199 #pragma GCC diagnostic ignored "-Wlong-long" 200 #endif 201 202 #if 1 203 /* Technically not an assembly fragment, but GCC does a really good */ 204 /* job at inlining it and generating good machine code for it. */ 205 long long ret, tmp; 206 207 208 ret = (long long)a * b; 209 tmp = ret >> 63; 210 ret += 0x8000 + tmp; 211 212 return (FT_Int32)( ret >> 16 ); 213 #else 214 215 /* For some reason, GCC 4.6 on Ubuntu 12.04 generates invalid machine */ 216 /* code from the lines below. The main issue is that `wide_a' is not */ 217 /* properly initialized by sign-extending `a'. Instead, the generated */ 218 /* machine code assumes that the register that contains `a' on input */ 219 /* can be used directly as a 64-bit value, which is wrong most of the */ 220 /* time. */ 221 long long wide_a = (long long)a; 222 long long wide_b = (long long)b; 223 long long result; 224 225 226 __asm__ __volatile__ ( 227 "imul %2, %1\n" 228 "mov %1, %0\n" 229 "sar $63, %0\n" 230 "lea 0x8000(%1, %0), %0\n" 231 "sar $16, %0\n" 232 : "=&r"(result), "=&r"(wide_a) 233 : "r"(wide_b) 234 : "cc" ); 235 236 return (FT_Int32)result; 237 #endif 238 239 #if ( __GNUC__ > 4 ) || ( ( __GNUC__ == 4 ) && ( __GNUC_MINOR__ >= 6 ) ) 240 #pragma GCC diagnostic pop 241 #endif 242 } 243 244 #endif /* __GNUC__ && __x86_64__ */ 245 246 #if defined( __GNUC__ ) 247 #if ( __GNUC__ > 3 ) || ( ( __GNUC__ == 3 ) && ( __GNUC_MINOR__ >= 4 ) ) 248 249 #if FT_SIZEOF_INT == 4 250 251 #define FT_MSB_BUILTIN( x ) ( 31 - __builtin_clz( x ) ) 252 253 #elif FT_SIZEOF_LONG == 4 254 255 #define FT_MSB_BUILTIN( x ) ( 31 - __builtin_clzl( x ) ) 256 257 #endif 258 259 #endif 260 #endif /* __GNUC__ */ 261 262 #endif /* !FT_CONFIG_OPTION_NO_ASSEMBLER */ 263 264 265 #ifdef FT_CONFIG_OPTION_INLINE_MULFIX 266 #ifdef FT_MULFIX_ASSEMBLER 267 #define FT_MULFIX_INLINED FT_MULFIX_ASSEMBLER 268 #endif 269 #endif 270 271 #ifdef FT_MULFIX_INLINED 272 #undef FT_MulFix 273 #endif 274 275 /* we need to emulate a 64-bit data type if a real one isn't available */ 276 277 #ifndef FT_LONG64 278 279 typedef struct FT_Int64_ 280 { 281 FT_UInt32 lo; 282 FT_UInt32 hi; 283 284 } FT_Int64; 285 286 #endif /* !FT_LONG64 */ 287 288 289 /*************************************************************************/ 290 /* */ 291 /* The macro FT_COMPONENT is used in trace mode. It is an implicit */ 292 /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log */ 293 /* messages during execution. */ 294 /* */ 295 #undef FT_COMPONENT 296 #define FT_COMPONENT trace_calc 297 298 299 /* The following three functions are available regardless of whether */ 300 /* FT_LONG64 is defined. */ 301 302 /* documentation is in freetype.h */ 303 304 FT_EXPORT_DEF( FT_Fixed ) FT_RoundFix(FT_Fixed a)305 FT_RoundFix( FT_Fixed a ) 306 { 307 return ( a >= 0 ) ? ( a + 0x8000L ) & ~0xFFFFL 308 : -((-a + 0x8000L ) & ~0xFFFFL ); 309 } 310 311 312 /* documentation is in freetype.h */ 313 314 FT_EXPORT_DEF( FT_Fixed ) FT_CeilFix(FT_Fixed a)315 FT_CeilFix( FT_Fixed a ) 316 { 317 return ( a >= 0 ) ? ( a + 0xFFFFL ) & ~0xFFFFL 318 : -((-a + 0xFFFFL ) & ~0xFFFFL ); 319 } 320 321 322 /* documentation is in freetype.h */ 323 324 FT_EXPORT_DEF( FT_Fixed ) FT_FloorFix(FT_Fixed a)325 FT_FloorFix( FT_Fixed a ) 326 { 327 return ( a >= 0 ) ? a & ~0xFFFFL 328 : -((-a) & ~0xFFFFL ); 329 } 330 331 332 FT_BASE_DEF ( FT_Int ) FT_MSB(FT_UInt32 z)333 FT_MSB( FT_UInt32 z ) 334 { 335 #ifdef FT_MSB_BUILTIN 336 337 return FT_MSB_BUILTIN( z ); 338 339 #else 340 341 FT_Int shift = 0; 342 343 /* determine msb bit index in `shift' */ 344 if ( z >= ( 1L << 16 ) ) 345 { 346 z >>= 16; 347 shift += 16; 348 } 349 if ( z >= ( 1L << 8 ) ) 350 { 351 z >>= 8; 352 shift += 8; 353 } 354 if ( z >= ( 1L << 4 ) ) 355 { 356 z >>= 4; 357 shift += 4; 358 } 359 if ( z >= ( 1L << 2 ) ) 360 { 361 z >>= 2; 362 shift += 2; 363 } 364 if ( z >= ( 1L << 1 ) ) 365 { 366 /* z >>= 1; */ 367 shift += 1; 368 } 369 370 return shift; 371 372 #endif /* FT_MSB_BUILTIN */ 373 } 374 375 376 /* documentation is in ftcalc.h */ 377 378 FT_BASE_DEF( FT_Fixed ) FT_Hypot(FT_Fixed x,FT_Fixed y)379 FT_Hypot( FT_Fixed x, 380 FT_Fixed y ) 381 { 382 FT_Vector v; 383 384 385 v.x = x; 386 v.y = y; 387 388 return FT_Vector_Length( &v ); 389 } 390 391 392 #ifdef FT_LONG64 393 394 395 /* documentation is in freetype.h */ 396 397 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)398 FT_MulDiv( FT_Long a, 399 FT_Long b, 400 FT_Long c ) 401 { 402 FT_Int s; 403 FT_Long d; 404 405 406 s = 1; 407 if ( a < 0 ) { a = -a; s = -1; } 408 if ( b < 0 ) { b = -b; s = -s; } 409 if ( c < 0 ) { c = -c; s = -s; } 410 411 d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c 412 : 0x7FFFFFFFL ); 413 414 return ( s > 0 ) ? d : -d; 415 } 416 417 418 /* documentation is in ftcalc.h */ 419 420 FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round(FT_Long a,FT_Long b,FT_Long c)421 FT_MulDiv_No_Round( FT_Long a, 422 FT_Long b, 423 FT_Long c ) 424 { 425 FT_Int s; 426 FT_Long d; 427 428 429 s = 1; 430 if ( a < 0 ) { a = -a; s = -1; } 431 if ( b < 0 ) { b = -b; s = -s; } 432 if ( c < 0 ) { c = -c; s = -s; } 433 434 d = (FT_Long)( c > 0 ? (FT_Int64)a * b / c 435 : 0x7FFFFFFFL ); 436 437 return ( s > 0 ) ? d : -d; 438 } 439 440 441 /* documentation is in freetype.h */ 442 443 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a,FT_Long b)444 FT_MulFix( FT_Long a, 445 FT_Long b ) 446 { 447 #ifdef FT_MULFIX_ASSEMBLER 448 449 return FT_MULFIX_ASSEMBLER( a, b ); 450 451 #else 452 453 FT_Int s = 1; 454 FT_Long c; 455 456 457 if ( a < 0 ) 458 { 459 a = -a; 460 s = -1; 461 } 462 463 if ( b < 0 ) 464 { 465 b = -b; 466 s = -s; 467 } 468 469 c = (FT_Long)( ( (FT_Int64)a * b + 0x8000L ) >> 16 ); 470 471 return ( s > 0 ) ? c : -c; 472 473 #endif /* FT_MULFIX_ASSEMBLER */ 474 } 475 476 477 /* documentation is in freetype.h */ 478 479 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a,FT_Long b)480 FT_DivFix( FT_Long a, 481 FT_Long b ) 482 { 483 FT_Int32 s; 484 FT_UInt32 q; 485 486 487 s = 1; 488 if ( a < 0 ) 489 { 490 a = -a; 491 s = -1; 492 } 493 if ( b < 0 ) 494 { 495 b = -b; 496 s = -s; 497 } 498 499 if ( b == 0 ) 500 /* check for division by 0 */ 501 q = 0x7FFFFFFFL; 502 else 503 /* compute result directly */ 504 q = (FT_UInt32)( ( ( (FT_UInt64)a << 16 ) + ( b >> 1 ) ) / b ); 505 506 return ( s < 0 ? -(FT_Long)q : (FT_Long)q ); 507 } 508 509 510 #else /* !FT_LONG64 */ 511 512 513 static void ft_multo64(FT_UInt32 x,FT_UInt32 y,FT_Int64 * z)514 ft_multo64( FT_UInt32 x, 515 FT_UInt32 y, 516 FT_Int64 *z ) 517 { 518 FT_UInt32 lo1, hi1, lo2, hi2, lo, hi, i1, i2; 519 520 521 lo1 = x & 0x0000FFFFU; hi1 = x >> 16; 522 lo2 = y & 0x0000FFFFU; hi2 = y >> 16; 523 524 lo = lo1 * lo2; 525 i1 = lo1 * hi2; 526 i2 = lo2 * hi1; 527 hi = hi1 * hi2; 528 529 /* Check carry overflow of i1 + i2 */ 530 i1 += i2; 531 hi += (FT_UInt32)( i1 < i2 ) << 16; 532 533 hi += i1 >> 16; 534 i1 = i1 << 16; 535 536 /* Check carry overflow of i1 + lo */ 537 lo += i1; 538 hi += ( lo < i1 ); 539 540 z->lo = lo; 541 z->hi = hi; 542 } 543 544 545 static FT_UInt32 ft_div64by32(FT_UInt32 hi,FT_UInt32 lo,FT_UInt32 y)546 ft_div64by32( FT_UInt32 hi, 547 FT_UInt32 lo, 548 FT_UInt32 y ) 549 { 550 FT_UInt32 r, q; 551 FT_Int i; 552 553 554 q = 0; 555 r = hi; 556 557 if ( r >= y ) 558 return (FT_UInt32)0x7FFFFFFFL; 559 560 i = 32; 561 do 562 { 563 r <<= 1; 564 q <<= 1; 565 r |= lo >> 31; 566 567 if ( r >= y ) 568 { 569 r -= y; 570 q |= 1; 571 } 572 lo <<= 1; 573 } while ( --i ); 574 575 return q; 576 } 577 578 579 static void FT_Add64(FT_Int64 * x,FT_Int64 * y,FT_Int64 * z)580 FT_Add64( FT_Int64* x, 581 FT_Int64* y, 582 FT_Int64 *z ) 583 { 584 register FT_UInt32 lo, hi; 585 586 587 lo = x->lo + y->lo; 588 hi = x->hi + y->hi + ( lo < x->lo ); 589 590 z->lo = lo; 591 z->hi = hi; 592 } 593 594 595 /* documentation is in freetype.h */ 596 597 /* The FT_MulDiv function has been optimized thanks to ideas from */ 598 /* Graham Asher and Alexei Podtelezhnikov. The trick is to optimize */ 599 /* a rather common case when everything fits within 32-bits. */ 600 /* */ 601 /* We compute 'a*b+c/2', then divide it by 'c'. (positive values) */ 602 /* */ 603 /* The product of two positive numbers never exceeds the square of */ 604 /* their mean. Therefore, we always avoid the overflow by imposing */ 605 /* */ 606 /* ( a + b ) / 2 <= sqrt( X - c/2 ) */ 607 /* */ 608 /* where X = 2^31 - 1. Now we replace sqrt with a linear function */ 609 /* that is smaller or equal in the entire range of c from 0 to X; */ 610 /* it should be equal to sqrt(X) and sqrt(X/2) at the range termini. */ 611 /* Substituting the linear solution and explicit numbers we get */ 612 /* */ 613 /* a + b <= 92681.9 - c / 79108.95 */ 614 /* */ 615 /* In practice we use a faster and even stronger inequality */ 616 /* */ 617 /* a + b <= 92681 - (c >> 16) */ 618 /* */ 619 620 FT_EXPORT_DEF( FT_Long ) FT_MulDiv(FT_Long a,FT_Long b,FT_Long c)621 FT_MulDiv( FT_Long a, 622 FT_Long b, 623 FT_Long c ) 624 { 625 long s; 626 627 628 /* XXX: this function does not allow 64-bit arguments */ 629 if ( a == 0 || b == c ) 630 return a; 631 632 s = a; a = FT_ABS( a ); 633 s ^= b; b = FT_ABS( b ); 634 s ^= c; c = FT_ABS( c ); 635 636 if ( (FT_ULong)a + (FT_ULong)b <= 92681UL - ( c >> 16 ) && c > 0 ) 637 a = ( a * b + ( c >> 1 ) ) / c; 638 639 else if ( (FT_Int32)c > 0 ) 640 { 641 FT_Int64 temp, temp2; 642 643 644 ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); 645 646 temp2.hi = 0; 647 temp2.lo = (FT_UInt32)(c >> 1); 648 FT_Add64( &temp, &temp2, &temp ); 649 a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); 650 } 651 else 652 a = 0x7FFFFFFFL; 653 654 return ( s < 0 ? -a : a ); 655 } 656 657 658 FT_BASE_DEF( FT_Long ) FT_MulDiv_No_Round(FT_Long a,FT_Long b,FT_Long c)659 FT_MulDiv_No_Round( FT_Long a, 660 FT_Long b, 661 FT_Long c ) 662 { 663 long s; 664 665 666 if ( a == 0 || b == c ) 667 return a; 668 669 s = a; a = FT_ABS( a ); 670 s ^= b; b = FT_ABS( b ); 671 s ^= c; c = FT_ABS( c ); 672 673 if ( (FT_ULong)a + (FT_ULong)b <= 92681UL && c > 0 ) 674 a = a * b / c; 675 676 else if ( (FT_Int32)c > 0 ) 677 { 678 FT_Int64 temp; 679 680 681 ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp ); 682 a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c ); 683 } 684 else 685 a = 0x7FFFFFFFL; 686 687 return ( s < 0 ? -a : a ); 688 } 689 690 691 /* documentation is in freetype.h */ 692 693 FT_EXPORT_DEF( FT_Long ) FT_MulFix(FT_Long a,FT_Long b)694 FT_MulFix( FT_Long a, 695 FT_Long b ) 696 { 697 #ifdef FT_MULFIX_ASSEMBLER 698 699 return FT_MULFIX_ASSEMBLER( a, b ); 700 701 #elif 0 702 703 /* 704 * This code is nonportable. See comment below. 705 * 706 * However, on a platform where right-shift of a signed quantity fills 707 * the leftmost bits by copying the sign bit, it might be faster. 708 */ 709 710 FT_Long sa, sb; 711 FT_ULong ua, ub; 712 713 714 if ( a == 0 || b == 0x10000L ) 715 return a; 716 717 /* 718 * This is a clever way of converting a signed number `a' into its 719 * absolute value (stored back into `a') and its sign. The sign is 720 * stored in `sa'; 0 means `a' was positive or zero, and -1 means `a' 721 * was negative. (Similarly for `b' and `sb'). 722 * 723 * Unfortunately, it doesn't work (at least not portably). 724 * 725 * It makes the assumption that right-shift on a negative signed value 726 * fills the leftmost bits by copying the sign bit. This is wrong. 727 * According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206, 728 * the result of right-shift of a negative signed value is 729 * implementation-defined. At least one implementation fills the 730 * leftmost bits with 0s (i.e., it is exactly the same as an unsigned 731 * right shift). This means that when `a' is negative, `sa' ends up 732 * with the value 1 rather than -1. After that, everything else goes 733 * wrong. 734 */ 735 sa = ( a >> ( sizeof ( a ) * 8 - 1 ) ); 736 a = ( a ^ sa ) - sa; 737 sb = ( b >> ( sizeof ( b ) * 8 - 1 ) ); 738 b = ( b ^ sb ) - sb; 739 740 ua = (FT_ULong)a; 741 ub = (FT_ULong)b; 742 743 if ( ua <= 2048 && ub <= 1048576L ) 744 ua = ( ua * ub + 0x8000U ) >> 16; 745 else 746 { 747 FT_ULong al = ua & 0xFFFFU; 748 749 750 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + 751 ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 ); 752 } 753 754 sa ^= sb, 755 ua = (FT_ULong)(( ua ^ sa ) - sa); 756 757 return (FT_Long)ua; 758 759 #else /* 0 */ 760 761 FT_Long s; 762 FT_ULong ua, ub; 763 764 765 if ( a == 0 || b == 0x10000L ) 766 return a; 767 768 s = a; a = FT_ABS( a ); 769 s ^= b; b = FT_ABS( b ); 770 771 ua = (FT_ULong)a; 772 ub = (FT_ULong)b; 773 774 if ( ua <= 2048 && ub <= 1048576L ) 775 ua = ( ua * ub + 0x8000UL ) >> 16; 776 else 777 { 778 FT_ULong al = ua & 0xFFFFUL; 779 780 781 ua = ( ua >> 16 ) * ub + al * ( ub >> 16 ) + 782 ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 ); 783 } 784 785 return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua ); 786 787 #endif /* 0 */ 788 789 } 790 791 792 /* documentation is in freetype.h */ 793 794 FT_EXPORT_DEF( FT_Long ) FT_DivFix(FT_Long a,FT_Long b)795 FT_DivFix( FT_Long a, 796 FT_Long b ) 797 { 798 FT_Int32 s; 799 FT_UInt32 q; 800 801 802 /* XXX: this function does not allow 64-bit arguments */ 803 s = (FT_Int32)a; a = FT_ABS( a ); 804 s ^= (FT_Int32)b; b = FT_ABS( b ); 805 806 if ( (FT_UInt32)b == 0 ) 807 { 808 /* check for division by 0 */ 809 q = (FT_UInt32)0x7FFFFFFFL; 810 } 811 else if ( ( a >> 16 ) == 0 ) 812 { 813 /* compute result directly */ 814 q = (FT_UInt32)( ( (FT_ULong)a << 16 ) + ( b >> 1 ) ) / (FT_UInt32)b; 815 } 816 else 817 { 818 /* we need more bits; we have to do it by hand */ 819 FT_Int64 temp, temp2; 820 821 822 temp.hi = (FT_Int32)( a >> 16 ); 823 temp.lo = (FT_UInt32)a << 16; 824 temp2.hi = 0; 825 temp2.lo = (FT_UInt32)( b >> 1 ); 826 FT_Add64( &temp, &temp2, &temp ); 827 q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b ); 828 } 829 830 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 831 } 832 833 834 #if 0 835 836 /* documentation is in ftcalc.h */ 837 838 FT_EXPORT_DEF( void ) 839 FT_MulTo64( FT_Int32 x, 840 FT_Int32 y, 841 FT_Int64 *z ) 842 { 843 FT_Int32 s; 844 845 846 s = x; x = FT_ABS( x ); 847 s ^= y; y = FT_ABS( y ); 848 849 ft_multo64( x, y, z ); 850 851 if ( s < 0 ) 852 { 853 z->lo = (FT_UInt32)-(FT_Int32)z->lo; 854 z->hi = ~z->hi + !( z->lo ); 855 } 856 } 857 858 859 /* apparently, the second version of this code is not compiled correctly */ 860 /* on Mac machines with the MPW C compiler.. tsk, tsk, tsk... */ 861 862 #if 1 863 864 FT_EXPORT_DEF( FT_Int32 ) 865 FT_Div64by32( FT_Int64* x, 866 FT_Int32 y ) 867 { 868 FT_Int32 s; 869 FT_UInt32 q, r, i, lo; 870 871 872 s = x->hi; 873 if ( s < 0 ) 874 { 875 x->lo = (FT_UInt32)-(FT_Int32)x->lo; 876 x->hi = ~x->hi + !x->lo; 877 } 878 s ^= y; y = FT_ABS( y ); 879 880 /* Shortcut */ 881 if ( x->hi == 0 ) 882 { 883 if ( y > 0 ) 884 q = x->lo / y; 885 else 886 q = 0x7FFFFFFFL; 887 888 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 889 } 890 891 r = x->hi; 892 lo = x->lo; 893 894 if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */ 895 return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL ); 896 /* Return Max/Min Int32 if division overflow. */ 897 /* This includes division by zero! */ 898 q = 0; 899 for ( i = 0; i < 32; i++ ) 900 { 901 r <<= 1; 902 q <<= 1; 903 r |= lo >> 31; 904 905 if ( r >= (FT_UInt32)y ) 906 { 907 r -= y; 908 q |= 1; 909 } 910 lo <<= 1; 911 } 912 913 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 914 } 915 916 #else /* 0 */ 917 918 FT_EXPORT_DEF( FT_Int32 ) 919 FT_Div64by32( FT_Int64* x, 920 FT_Int32 y ) 921 { 922 FT_Int32 s; 923 FT_UInt32 q; 924 925 926 s = x->hi; 927 if ( s < 0 ) 928 { 929 x->lo = (FT_UInt32)-(FT_Int32)x->lo; 930 x->hi = ~x->hi + !x->lo; 931 } 932 s ^= y; y = FT_ABS( y ); 933 934 /* Shortcut */ 935 if ( x->hi == 0 ) 936 { 937 if ( y > 0 ) 938 q = ( x->lo + ( y >> 1 ) ) / y; 939 else 940 q = 0x7FFFFFFFL; 941 942 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 943 } 944 945 q = ft_div64by32( x->hi, x->lo, y ); 946 947 return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q ); 948 } 949 950 #endif /* 0 */ 951 952 #endif /* 0 */ 953 954 955 #endif /* FT_LONG64 */ 956 957 958 /* documentation is in ftglyph.h */ 959 960 FT_EXPORT_DEF( void ) FT_Matrix_Multiply(const FT_Matrix * a,FT_Matrix * b)961 FT_Matrix_Multiply( const FT_Matrix* a, 962 FT_Matrix *b ) 963 { 964 FT_Fixed xx, xy, yx, yy; 965 966 967 if ( !a || !b ) 968 return; 969 970 xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx ); 971 xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy ); 972 yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx ); 973 yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy ); 974 975 b->xx = xx; b->xy = xy; 976 b->yx = yx; b->yy = yy; 977 } 978 979 980 /* documentation is in ftglyph.h */ 981 982 FT_EXPORT_DEF( FT_Error ) FT_Matrix_Invert(FT_Matrix * matrix)983 FT_Matrix_Invert( FT_Matrix* matrix ) 984 { 985 FT_Pos delta, xx, yy; 986 987 988 if ( !matrix ) 989 return FT_THROW( Invalid_Argument ); 990 991 /* compute discriminant */ 992 delta = FT_MulFix( matrix->xx, matrix->yy ) - 993 FT_MulFix( matrix->xy, matrix->yx ); 994 995 if ( !delta ) 996 return FT_THROW( Invalid_Argument ); /* matrix can't be inverted */ 997 998 matrix->xy = - FT_DivFix( matrix->xy, delta ); 999 matrix->yx = - FT_DivFix( matrix->yx, delta ); 1000 1001 xx = matrix->xx; 1002 yy = matrix->yy; 1003 1004 matrix->xx = FT_DivFix( yy, delta ); 1005 matrix->yy = FT_DivFix( xx, delta ); 1006 1007 return FT_Err_Ok; 1008 } 1009 1010 1011 /* documentation is in ftcalc.h */ 1012 1013 FT_BASE_DEF( void ) FT_Matrix_Multiply_Scaled(const FT_Matrix * a,FT_Matrix * b,FT_Long scaling)1014 FT_Matrix_Multiply_Scaled( const FT_Matrix* a, 1015 FT_Matrix *b, 1016 FT_Long scaling ) 1017 { 1018 FT_Fixed xx, xy, yx, yy; 1019 1020 FT_Long val = 0x10000L * scaling; 1021 1022 1023 if ( !a || !b ) 1024 return; 1025 1026 xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val ); 1027 xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val ); 1028 yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val ); 1029 yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val ); 1030 1031 b->xx = xx; b->xy = xy; 1032 b->yx = yx; b->yy = yy; 1033 } 1034 1035 1036 /* documentation is in ftcalc.h */ 1037 1038 FT_BASE_DEF( void ) FT_Vector_Transform_Scaled(FT_Vector * vector,const FT_Matrix * matrix,FT_Long scaling)1039 FT_Vector_Transform_Scaled( FT_Vector* vector, 1040 const FT_Matrix* matrix, 1041 FT_Long scaling ) 1042 { 1043 FT_Pos xz, yz; 1044 1045 FT_Long val = 0x10000L * scaling; 1046 1047 1048 if ( !vector || !matrix ) 1049 return; 1050 1051 xz = FT_MulDiv( vector->x, matrix->xx, val ) + 1052 FT_MulDiv( vector->y, matrix->xy, val ); 1053 1054 yz = FT_MulDiv( vector->x, matrix->yx, val ) + 1055 FT_MulDiv( vector->y, matrix->yy, val ); 1056 1057 vector->x = xz; 1058 vector->y = yz; 1059 } 1060 1061 1062 #if 0 1063 1064 /* documentation is in ftcalc.h */ 1065 1066 FT_BASE_DEF( FT_Int32 ) 1067 FT_SqrtFixed( FT_Int32 x ) 1068 { 1069 FT_UInt32 root, rem_hi, rem_lo, test_div; 1070 FT_Int count; 1071 1072 1073 root = 0; 1074 1075 if ( x > 0 ) 1076 { 1077 rem_hi = 0; 1078 rem_lo = x; 1079 count = 24; 1080 do 1081 { 1082 rem_hi = ( rem_hi << 2 ) | ( rem_lo >> 30 ); 1083 rem_lo <<= 2; 1084 root <<= 1; 1085 test_div = ( root << 1 ) + 1; 1086 1087 if ( rem_hi >= test_div ) 1088 { 1089 rem_hi -= test_div; 1090 root += 1; 1091 } 1092 } while ( --count ); 1093 } 1094 1095 return (FT_Int32)root; 1096 } 1097 1098 #endif /* 0 */ 1099 1100 1101 /* documentation is in ftcalc.h */ 1102 1103 FT_BASE_DEF( FT_Int ) ft_corner_orientation(FT_Pos in_x,FT_Pos in_y,FT_Pos out_x,FT_Pos out_y)1104 ft_corner_orientation( FT_Pos in_x, 1105 FT_Pos in_y, 1106 FT_Pos out_x, 1107 FT_Pos out_y ) 1108 { 1109 FT_Long result; /* avoid overflow on 16-bit system */ 1110 1111 1112 /* deal with the trivial cases quickly */ 1113 if ( in_y == 0 ) 1114 { 1115 if ( in_x >= 0 ) 1116 result = out_y; 1117 else 1118 result = -out_y; 1119 } 1120 else if ( in_x == 0 ) 1121 { 1122 if ( in_y >= 0 ) 1123 result = -out_x; 1124 else 1125 result = out_x; 1126 } 1127 else if ( out_y == 0 ) 1128 { 1129 if ( out_x >= 0 ) 1130 result = in_y; 1131 else 1132 result = -in_y; 1133 } 1134 else if ( out_x == 0 ) 1135 { 1136 if ( out_y >= 0 ) 1137 result = -in_x; 1138 else 1139 result = in_x; 1140 } 1141 else /* general case */ 1142 { 1143 #ifdef FT_LONG64 1144 1145 FT_Int64 delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x; 1146 1147 1148 if ( delta == 0 ) 1149 result = 0; 1150 else 1151 result = 1 - 2 * ( delta < 0 ); 1152 1153 #else 1154 1155 FT_Int64 z1, z2; 1156 1157 1158 /* XXX: this function does not allow 64-bit arguments */ 1159 ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 ); 1160 ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 ); 1161 1162 if ( z1.hi > z2.hi ) 1163 result = +1; 1164 else if ( z1.hi < z2.hi ) 1165 result = -1; 1166 else if ( z1.lo > z2.lo ) 1167 result = +1; 1168 else if ( z1.lo < z2.lo ) 1169 result = -1; 1170 else 1171 result = 0; 1172 1173 #endif 1174 } 1175 1176 /* XXX: only the sign of return value, +1/0/-1 must be used */ 1177 return (FT_Int)result; 1178 } 1179 1180 1181 /* documentation is in ftcalc.h */ 1182 1183 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)1184 ft_corner_is_flat( FT_Pos in_x, 1185 FT_Pos in_y, 1186 FT_Pos out_x, 1187 FT_Pos out_y ) 1188 { 1189 FT_Pos ax = in_x; 1190 FT_Pos ay = in_y; 1191 1192 FT_Pos d_in, d_out, d_corner; 1193 1194 1195 /* We approximate the Euclidean metric (sqrt(x^2 + y^2)) with */ 1196 /* the Taxicab metric (|x| + |y|), which can be computed much */ 1197 /* faster. If one of the two vectors is much longer than the */ 1198 /* other one, the direction of the shorter vector doesn't */ 1199 /* influence the result any more. */ 1200 /* */ 1201 /* corner */ 1202 /* x---------------------------x */ 1203 /* \ / */ 1204 /* \ / */ 1205 /* in \ / out */ 1206 /* \ / */ 1207 /* o */ 1208 /* Point */ 1209 /* */ 1210 1211 if ( ax < 0 ) 1212 ax = -ax; 1213 if ( ay < 0 ) 1214 ay = -ay; 1215 d_in = ax + ay; /* d_in = || in || */ 1216 1217 ax = out_x; 1218 if ( ax < 0 ) 1219 ax = -ax; 1220 ay = out_y; 1221 if ( ay < 0 ) 1222 ay = -ay; 1223 d_out = ax + ay; /* d_out = || out || */ 1224 1225 ax = out_x + in_x; 1226 if ( ax < 0 ) 1227 ax = -ax; 1228 ay = out_y + in_y; 1229 if ( ay < 0 ) 1230 ay = -ay; 1231 d_corner = ax + ay; /* d_corner = || in + out || */ 1232 1233 /* now do a simple length comparison: */ 1234 /* */ 1235 /* d_in + d_out < 17/16 d_corner */ 1236 1237 return ( d_in + d_out - d_corner ) < ( d_corner >> 4 ); 1238 } 1239 1240 1241 /* END */ 1242