thirdparty/freetype-2.3.12/src/base/ftcalc.c

   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 )
  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 )
  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 )
  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 )
 111   FT_Sqrt32( FT_Int32  x )
 112   {
 113     FT_UInt32  val, root, newroot, mask;
 114
 115
 116     root = 0;
 117     mask = (FT_UInt32)0x40000000UL;
 118     val  = (FT_UInt32)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 )
 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 )
 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 )
 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 )
 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
 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
 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
 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 )
 358   FT_MulDiv( FT_Long  a,
 359              FT_Long  b,
 360              FT_Long  c )
 361   {
 362     long  s;
 363
 364
 365     /* XXX: this function does not allow 64-bit arguments */
 366     if ( a == 0 || b == c )
 367       return a;
 368
 369     s  = a; a = FT_ABS( a );
 370     s ^= b; b = FT_ABS( b );
 371     s ^= c; c = FT_ABS( c );
 372
 373     if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
 374       a = ( a * b + ( c >> 1 ) ) / c;
 375
 376     else if ( c > 0 )
 377     {
 378       FT_Int64  temp, temp2;
 379
 380
 381       ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp );
 382
 383       temp2.hi = 0;
 384       temp2.lo = (FT_UInt32)(c >> 1);
 385       FT_Add64( &temp, &temp2, &temp );
 386       a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c );
 387     }
 388     else
 389       a = 0x7FFFFFFFL;
 390
 391     return ( s < 0 ? -a : a );
 392   }
 393
 394
 395 #ifdef TT_USE_BYTECODE_INTERPRETER
 396
 397   FT_BASE_DEF( FT_Long )
 398   FT_MulDiv_No_Round( FT_Long  a,
 399                       FT_Long  b,
 400                       FT_Long  c )
 401   {
 402     long  s;
 403
 404
 405     if ( a == 0 || b == c )
 406       return a;
 407
 408     s  = a; a = FT_ABS( a );
 409     s ^= b; b = FT_ABS( b );
 410     s ^= c; c = FT_ABS( c );
 411
 412     if ( a <= 46340L && b <= 46340L && c > 0 )
 413       a = a * b / c;
 414
 415     else if ( c > 0 )
 416     {
 417       FT_Int64  temp;
 418
 419
 420       ft_multo64( (FT_Int32)a, (FT_Int32)b, &temp );
 421       a = ft_div64by32( temp.hi, temp.lo, (FT_Int32)c );
 422     }
 423     else
 424       a = 0x7FFFFFFFL;
 425
 426     return ( s < 0 ? -a : a );
 427   }
 428
 429 #endif /* TT_USE_BYTECODE_INTERPRETER */
 430
 431
 432   /* documentation is in freetype.h */
 433
 434   FT_EXPORT_DEF( FT_Long )
 435   FT_MulFix( FT_Long  a,
 436              FT_Long  b )
 437   {
 438 #ifdef FT_MULFIX_ASSEMBLER
 439
 440     return FT_MULFIX_ASSEMBLER( a, b );
 441
 442 #elif 0
 443
 444     /*
 445      *  This code is nonportable.  See comment below.
 446      *
 447      *  However, on a platform where right-shift of a signed quantity fills
 448      *  the leftmost bits by copying the sign bit, it might be faster.
 449      */
 450
 451     FT_Long   sa, sb;
 452     FT_ULong  ua, ub;
 453
 454
 455     if ( a == 0 || b == 0x10000L )
 456       return a;
 457
 458     /*
 459      *  This is a clever way of converting a signed number `a' into its
 460      *  absolute value (stored back into `a') and its sign.  The sign is
 461      *  stored in `sa'; 0 means `a' was positive or zero, and -1 means `a'
 462      *  was negative.  (Similarly for `b' and `sb').
 463      *
 464      *  Unfortunately, it doesn't work (at least not portably).
 465      *
 466      *  It makes the assumption that right-shift on a negative signed value
 467      *  fills the leftmost bits by copying the sign bit.  This is wrong.
 468      *  According to K&R 2nd ed, section `A7.8 Shift Operators' on page 206,
 469      *  the result of right-shift of a negative signed value is
 470      *  implementation-defined.  At least one implementation fills the
 471      *  leftmost bits with 0s (i.e., it is exactly the same as an unsigned
 472      *  right shift).  This means that when `a' is negative, `sa' ends up
 473      *  with the value 1 rather than -1.  After that, everything else goes
 474      *  wrong.
 475      */
 476     sa = ( a >> ( sizeof ( a ) * 8 - 1 ) );
 477     a  = ( a ^ sa ) - sa;
 478     sb = ( b >> ( sizeof ( b ) * 8 - 1 ) );
 479     b  = ( b ^ sb ) - sb;
 480
 481     ua = (FT_ULong)a;
 482     ub = (FT_ULong)b;
 483
 484     if ( ua <= 2048 && ub <= 1048576L )
 485       ua = ( ua * ub + 0x8000U ) >> 16;
 486     else
 487     {
 488       FT_ULong  al = ua & 0xFFFFU;
 489
 490
 491       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
 492            ( ( al * ( ub & 0xFFFFU ) + 0x8000U ) >> 16 );
 493     }
 494
 495     sa ^= sb,
 496     ua  = (FT_ULong)(( ua ^ sa ) - sa);
 497
 498     return (FT_Long)ua;
 499
 500 #else /* 0 */
 501
 502     FT_Long   s;
 503     FT_ULong  ua, ub;
 504
 505
 506     if ( a == 0 || b == 0x10000L )
 507       return a;
 508
 509     s  = a; a = FT_ABS( a );
 510     s ^= b; b = FT_ABS( b );
 511
 512     ua = (FT_ULong)a;
 513     ub = (FT_ULong)b;
 514
 515     if ( ua <= 2048 && ub <= 1048576L )
 516       ua = ( ua * ub + 0x8000UL ) >> 16;
 517     else
 518     {
 519       FT_ULong  al = ua & 0xFFFFUL;
 520
 521
 522       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
 523            ( ( al * ( ub & 0xFFFFUL ) + 0x8000UL ) >> 16 );
 524     }
 525
 526     return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
 527
 528 #endif /* 0 */
 529
 530   }
 531
 532
 533   /* documentation is in freetype.h */
 534
 535   FT_EXPORT_DEF( FT_Long )
 536   FT_DivFix( FT_Long  a,
 537              FT_Long  b )
 538   {
 539     FT_Int32   s;
 540     FT_UInt32  q;
 541
 542
 543     /* XXX: this function does not allow 64-bit arguments */
 544     s  = (FT_Int32)a; a = FT_ABS( a );
 545     s ^= (FT_Int32)b; b = FT_ABS( b );
 546
 547     if ( b == 0 )
 548     {
 549       /* check for division by 0 */
 550       q = (FT_UInt32)0x7FFFFFFFL;
 551     }
 552     else if ( ( a >> 16 ) == 0 )
 553     {
 554       /* compute result directly */
 555       q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
 556     }
 557     else
 558     {
 559       /* we need more bits; we have to do it by hand */
 560       FT_Int64  temp, temp2;
 561
 562       temp.hi  = (FT_Int32) (a >> 16);
 563       temp.lo  = (FT_UInt32)(a << 16);
 564       temp2.hi = 0;
 565       temp2.lo = (FT_UInt32)( b >> 1 );
 566       FT_Add64( &temp, &temp2, &temp );
 567       q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b );
 568     }
 569
 570     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 571   }
 572
 573
 574 #if 0
 575
 576   /* documentation is in ftcalc.h */
 577
 578   FT_EXPORT_DEF( void )
 579   FT_MulTo64( FT_Int32   x,
 580               FT_Int32   y,
 581               FT_Int64  *z )
 582   {
 583     FT_Int32  s;
 584
 585
 586     s  = x; x = FT_ABS( x );
 587     s ^= y; y = FT_ABS( y );
 588
 589     ft_multo64( x, y, z );
 590
 591     if ( s < 0 )
 592     {
 593       z->lo = (FT_UInt32)-(FT_Int32)z->lo;
 594       z->hi = ~z->hi + !( z->lo );
 595     }
 596   }
 597
 598
 599   /* apparently, the second version of this code is not compiled correctly */
 600   /* on Mac machines with the MPW C compiler..  tsk, tsk, tsk...           */
 601
 602 #if 1
 603
 604   FT_EXPORT_DEF( FT_Int32 )
 605   FT_Div64by32( FT_Int64*  x,
 606                 FT_Int32   y )
 607   {
 608     FT_Int32   s;
 609     FT_UInt32  q, r, i, lo;
 610
 611
 612     s  = x->hi;
 613     if ( s < 0 )
 614     {
 615       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 616       x->hi = ~x->hi + !x->lo;
 617     }
 618     s ^= y;  y = FT_ABS( y );
 619
 620     /* Shortcut */
 621     if ( x->hi == 0 )
 622     {
 623       if ( y > 0 )
 624         q = x->lo / y;
 625       else
 626         q = 0x7FFFFFFFL;
 627
 628       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 629     }
 630
 631     r  = x->hi;
 632     lo = x->lo;
 633
 634     if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
 635       return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
 636                              /* Return Max/Min Int32 if division overflow. */
 637                              /* This includes division by zero!            */
 638     q = 0;
 639     for ( i = 0; i < 32; i++ )
 640     {
 641       r <<= 1;
 642       q <<= 1;
 643       r  |= lo >> 31;
 644
 645       if ( r >= (FT_UInt32)y )
 646       {
 647         r -= y;
 648         q |= 1;
 649       }
 650       lo <<= 1;
 651     }
 652
 653     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 654   }
 655
 656 #else /* 0 */
 657
 658   FT_EXPORT_DEF( FT_Int32 )
 659   FT_Div64by32( FT_Int64*  x,
 660                 FT_Int32   y )
 661   {
 662     FT_Int32   s;
 663     FT_UInt32  q;
 664
 665
 666     s  = x->hi;
 667     if ( s < 0 )
 668     {
 669       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 670       x->hi = ~x->hi + !x->lo;
 671     }
 672     s ^= y;  y = FT_ABS( y );
 673
 674     /* Shortcut */
 675     if ( x->hi == 0 )
 676     {
 677       if ( y > 0 )
 678         q = ( x->lo + ( y >> 1 ) ) / y;
 679       else
 680         q = 0x7FFFFFFFL;
 681
 682       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 683     }
 684
 685     q = ft_div64by32( x->hi, x->lo, y );
 686
 687     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 688   }
 689
 690 #endif /* 0 */
 691
 692 #endif /* 0 */
 693
 694
 695 #endif /* FT_LONG64 */
 696
 697
 698   /* documentation is in ftglyph.h */
 699
 700   FT_EXPORT_DEF( void )
 701   FT_Matrix_Multiply( const FT_Matrix*  a,
 702                       FT_Matrix        *b )
 703   {
 704     FT_Fixed  xx, xy, yx, yy;
 705
 706
 707     if ( !a || !b )
 708       return;
 709
 710     xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx );
 711     xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy );
 712     yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx );
 713     yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy );
 714
 715     b->xx = xx;  b->xy = xy;
 716     b->yx = yx;  b->yy = yy;
 717   }
 718
 719
 720   /* documentation is in ftglyph.h */
 721
 722   FT_EXPORT_DEF( FT_Error )
 723   FT_Matrix_Invert( FT_Matrix*  matrix )
 724   {
 725     FT_Pos  delta, xx, yy;
 726
 727
 728     if ( !matrix )
 729       return FT_Err_Invalid_Argument;
 730
 731     /* compute discriminant */
 732     delta = FT_MulFix( matrix->xx, matrix->yy ) -
 733             FT_MulFix( matrix->xy, matrix->yx );
 734
 735     if ( !delta )
 736       return FT_Err_Invalid_Argument;  /* matrix can't be inverted */
 737
 738     matrix->xy = - FT_DivFix( matrix->xy, delta );
 739     matrix->yx = - FT_DivFix( matrix->yx, delta );
 740
 741     xx = matrix->xx;
 742     yy = matrix->yy;
 743
 744     matrix->xx = FT_DivFix( yy, delta );
 745     matrix->yy = FT_DivFix( xx, delta );
 746
 747     return FT_Err_Ok;
 748   }
 749
 750
 751   /* documentation is in ftcalc.h */
 752
 753   FT_BASE_DEF( void )
 754   FT_Matrix_Multiply_Scaled( const FT_Matrix*  a,
 755                              FT_Matrix        *b,
 756                              FT_Long           scaling )
 757   {
 758     FT_Fixed  xx, xy, yx, yy;
 759
 760     FT_Long   val = 0x10000L * scaling;
 761
 762
 763     if ( !a || !b )
 764       return;
 765
 766     xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val );
 767     xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val );
 768     yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val );
 769     yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val );
 770
 771     b->xx = xx;  b->xy = xy;
 772     b->yx = yx;  b->yy = yy;
 773   }
 774
 775
 776   /* documentation is in ftcalc.h */
 777
 778   FT_BASE_DEF( void )
 779   FT_Vector_Transform_Scaled( FT_Vector*        vector,
 780                               const FT_Matrix*  matrix,
 781                               FT_Long           scaling )
 782   {
 783     FT_Pos   xz, yz;
 784
 785     FT_Long  val = 0x10000L * scaling;
 786
 787
 788     if ( !vector || !matrix )
 789       return;
 790
 791     xz = FT_MulDiv( vector->x, matrix->xx, val ) +
 792          FT_MulDiv( vector->y, matrix->xy, val );
 793
 794     yz = FT_MulDiv( vector->x, matrix->yx, val ) +
 795          FT_MulDiv( vector->y, matrix->yy, val );
 796
 797     vector->x = xz;
 798     vector->y = yz;
 799   }
 800
 801
 802   /* documentation is in ftcalc.h */
 803
 804   FT_BASE_DEF( FT_Int32 )
 805   FT_SqrtFixed( FT_Int32  x )
 806   {
 807     FT_UInt32  root, rem_hi, rem_lo, test_div;
 808     FT_Int     count;
 809
 810
 811     root = 0;
 812
 813     if ( x > 0 )
 814     {
 815       rem_hi = 0;
 816       rem_lo = x;
 817       count  = 24;
 818       do
 819       {
 820         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
 821         rem_lo <<= 2;
 822         root   <<= 1;
 823         test_div = ( root << 1 ) + 1;
 824
 825         if ( rem_hi >= test_div )
 826         {
 827           rem_hi -= test_div;
 828           root   += 1;
 829         }
 830       } while ( --count );
 831     }
 832
 833     return (FT_Int32)root;
 834   }
 835
 836
 837   /* documentation is in ftcalc.h */
 838
 839   FT_BASE_DEF( FT_Int )
 840   ft_corner_orientation( FT_Pos  in_x,
 841                          FT_Pos  in_y,
 842                          FT_Pos  out_x,
 843                          FT_Pos  out_y )
 844   {
 845     FT_Long  result; /* avoid overflow on 16-bit system */
 846
 847
 848     /* deal with the trivial cases quickly */
 849     if ( in_y == 0 )
 850     {
 851       if ( in_x >= 0 )
 852         result = out_y;
 853       else
 854         result = -out_y;
 855     }
 856     else if ( in_x == 0 )
 857     {
 858       if ( in_y >= 0 )
 859         result = -out_x;
 860       else
 861         result = out_x;
 862     }
 863     else if ( out_y == 0 )
 864     {
 865       if ( out_x >= 0 )
 866         result = in_y;
 867       else
 868         result = -in_y;
 869     }
 870     else if ( out_x == 0 )
 871     {
 872       if ( out_y >= 0 )
 873         result = -in_x;
 874       else
 875         result =  in_x;
 876     }
 877     else /* general case */
 878     {
 879 #ifdef FT_LONG64
 880
 881       FT_Int64  delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
 882
 883
 884       if ( delta == 0 )
 885         result = 0;
 886       else
 887         result = 1 - 2 * ( delta < 0 );
 888
 889 #else
 890
 891       FT_Int64  z1, z2;
 892
 893
 894       /* XXX: this function does not allow 64-bit arguments */
 895       ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 );
 896       ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 );
 897
 898       if ( z1.hi > z2.hi )
 899         result = +1;
 900       else if ( z1.hi < z2.hi )
 901         result = -1;
 902       else if ( z1.lo > z2.lo )
 903         result = +1;
 904       else if ( z1.lo < z2.lo )
 905         result = -1;
 906       else
 907         result = 0;
 908
 909 #endif
 910     }
 911
 912     /* XXX: only the sign of return value, +1/0/-1 must be used */
 913     return (FT_Int)result;
 914   }
 915
 916
 917   /* documentation is in ftcalc.h */
 918
 919   FT_BASE_DEF( FT_Int )
 920   ft_corner_is_flat( FT_Pos  in_x,
 921                      FT_Pos  in_y,
 922                      FT_Pos  out_x,
 923                      FT_Pos  out_y )
 924   {
 925     FT_Pos  ax = in_x;
 926     FT_Pos  ay = in_y;
 927
 928     FT_Pos  d_in, d_out, d_corner;
 929
 930
 931     if ( ax < 0 )
 932       ax = -ax;
 933     if ( ay < 0 )
 934       ay = -ay;
 935     d_in = ax + ay;
 936
 937     ax = out_x;
 938     if ( ax < 0 )
 939       ax = -ax;
 940     ay = out_y;
 941     if ( ay < 0 )
 942       ay = -ay;
 943     d_out = ax + ay;
 944
 945     ax = out_x + in_x;
 946     if ( ax < 0 )
 947       ax = -ax;
 948     ay = out_y + in_y;
 949     if ( ay < 0 )
 950       ay = -ay;
 951     d_corner = ax + ay;
 952
 953     return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
 954   }
 955
 956
 957 /* END */