src/base/ftcalc.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftcalc.c                                                               */
   4 /*                                                                         */
   5 /*    Arithmetic computations (body).                                      */
   6 /*                                                                         */
   7 /*  Copyright 1996-2006, 2008, 2012 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 >= 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 ( (FT_Int32)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 ( (FT_Int32)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 ( (FT_UInt32)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
 563       temp.hi  = (FT_Int32) ( a >> 16 );
 564       temp.lo  = (FT_UInt32)( a << 16 );
 565       temp2.hi = 0;
 566       temp2.lo = (FT_UInt32)( b >> 1 );
 567       FT_Add64( &temp, &temp2, &temp );
 568       q = ft_div64by32( temp.hi, temp.lo, (FT_Int32)b );
 569     }
 570
 571     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 572   }
 573
 574
 575 #if 0
 576
 577   /* documentation is in ftcalc.h */
 578
 579   FT_EXPORT_DEF( void )
 580   FT_MulTo64( FT_Int32   x,
 581               FT_Int32   y,
 582               FT_Int64  *z )
 583   {
 584     FT_Int32  s;
 585
 586
 587     s  = x; x = FT_ABS( x );
 588     s ^= y; y = FT_ABS( y );
 589
 590     ft_multo64( x, y, z );
 591
 592     if ( s < 0 )
 593     {
 594       z->lo = (FT_UInt32)-(FT_Int32)z->lo;
 595       z->hi = ~z->hi + !( z->lo );
 596     }
 597   }
 598
 599
 600   /* apparently, the second version of this code is not compiled correctly */
 601   /* on Mac machines with the MPW C compiler..  tsk, tsk, tsk...           */
 602
 603 #if 1
 604
 605   FT_EXPORT_DEF( FT_Int32 )
 606   FT_Div64by32( FT_Int64*  x,
 607                 FT_Int32   y )
 608   {
 609     FT_Int32   s;
 610     FT_UInt32  q, r, i, lo;
 611
 612
 613     s  = x->hi;
 614     if ( s < 0 )
 615     {
 616       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 617       x->hi = ~x->hi + !x->lo;
 618     }
 619     s ^= y;  y = FT_ABS( y );
 620
 621     /* Shortcut */
 622     if ( x->hi == 0 )
 623     {
 624       if ( y > 0 )
 625         q = x->lo / y;
 626       else
 627         q = 0x7FFFFFFFL;
 628
 629       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 630     }
 631
 632     r  = x->hi;
 633     lo = x->lo;
 634
 635     if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
 636       return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
 637                              /* Return Max/Min Int32 if division overflow. */
 638                              /* This includes division by zero!            */
 639     q = 0;
 640     for ( i = 0; i < 32; i++ )
 641     {
 642       r <<= 1;
 643       q <<= 1;
 644       r  |= lo >> 31;
 645
 646       if ( r >= (FT_UInt32)y )
 647       {
 648         r -= y;
 649         q |= 1;
 650       }
 651       lo <<= 1;
 652     }
 653
 654     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 655   }
 656
 657 #else /* 0 */
 658
 659   FT_EXPORT_DEF( FT_Int32 )
 660   FT_Div64by32( FT_Int64*  x,
 661                 FT_Int32   y )
 662   {
 663     FT_Int32   s;
 664     FT_UInt32  q;
 665
 666
 667     s  = x->hi;
 668     if ( s < 0 )
 669     {
 670       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 671       x->hi = ~x->hi + !x->lo;
 672     }
 673     s ^= y;  y = FT_ABS( y );
 674
 675     /* Shortcut */
 676     if ( x->hi == 0 )
 677     {
 678       if ( y > 0 )
 679         q = ( x->lo + ( y >> 1 ) ) / y;
 680       else
 681         q = 0x7FFFFFFFL;
 682
 683       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 684     }
 685
 686     q = ft_div64by32( x->hi, x->lo, y );
 687
 688     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 689   }
 690
 691 #endif /* 0 */
 692
 693 #endif /* 0 */
 694
 695
 696 #endif /* FT_LONG64 */
 697
 698
 699   /* documentation is in ftglyph.h */
 700
 701   FT_EXPORT_DEF( void )
 702   FT_Matrix_Multiply( const FT_Matrix*  a,
 703                       FT_Matrix        *b )
 704   {
 705     FT_Fixed  xx, xy, yx, yy;
 706
 707
 708     if ( !a || !b )
 709       return;
 710
 711     xx = FT_MulFix( a->xx, b->xx ) + FT_MulFix( a->xy, b->yx );
 712     xy = FT_MulFix( a->xx, b->xy ) + FT_MulFix( a->xy, b->yy );
 713     yx = FT_MulFix( a->yx, b->xx ) + FT_MulFix( a->yy, b->yx );
 714     yy = FT_MulFix( a->yx, b->xy ) + FT_MulFix( a->yy, b->yy );
 715
 716     b->xx = xx;  b->xy = xy;
 717     b->yx = yx;  b->yy = yy;
 718   }
 719
 720
 721   /* documentation is in ftglyph.h */
 722
 723   FT_EXPORT_DEF( FT_Error )
 724   FT_Matrix_Invert( FT_Matrix*  matrix )
 725   {
 726     FT_Pos  delta, xx, yy;
 727
 728
 729     if ( !matrix )
 730       return FT_Err_Invalid_Argument;
 731
 732     /* compute discriminant */
 733     delta = FT_MulFix( matrix->xx, matrix->yy ) -
 734             FT_MulFix( matrix->xy, matrix->yx );
 735
 736     if ( !delta )
 737       return FT_Err_Invalid_Argument;  /* matrix can't be inverted */
 738
 739     matrix->xy = - FT_DivFix( matrix->xy, delta );
 740     matrix->yx = - FT_DivFix( matrix->yx, delta );
 741
 742     xx = matrix->xx;
 743     yy = matrix->yy;
 744
 745     matrix->xx = FT_DivFix( yy, delta );
 746     matrix->yy = FT_DivFix( xx, delta );
 747
 748     return FT_Err_Ok;
 749   }
 750
 751
 752   /* documentation is in ftcalc.h */
 753
 754   FT_BASE_DEF( void )
 755   FT_Matrix_Multiply_Scaled( const FT_Matrix*  a,
 756                              FT_Matrix        *b,
 757                              FT_Long           scaling )
 758   {
 759     FT_Fixed  xx, xy, yx, yy;
 760
 761     FT_Long   val = 0x10000L * scaling;
 762
 763
 764     if ( !a || !b )
 765       return;
 766
 767     xx = FT_MulDiv( a->xx, b->xx, val ) + FT_MulDiv( a->xy, b->yx, val );
 768     xy = FT_MulDiv( a->xx, b->xy, val ) + FT_MulDiv( a->xy, b->yy, val );
 769     yx = FT_MulDiv( a->yx, b->xx, val ) + FT_MulDiv( a->yy, b->yx, val );
 770     yy = FT_MulDiv( a->yx, b->xy, val ) + FT_MulDiv( a->yy, b->yy, val );
 771
 772     b->xx = xx;  b->xy = xy;
 773     b->yx = yx;  b->yy = yy;
 774   }
 775
 776
 777   /* documentation is in ftcalc.h */
 778
 779   FT_BASE_DEF( void )
 780   FT_Vector_Transform_Scaled( FT_Vector*        vector,
 781                               const FT_Matrix*  matrix,
 782                               FT_Long           scaling )
 783   {
 784     FT_Pos   xz, yz;
 785
 786     FT_Long  val = 0x10000L * scaling;
 787
 788
 789     if ( !vector || !matrix )
 790       return;
 791
 792     xz = FT_MulDiv( vector->x, matrix->xx, val ) +
 793          FT_MulDiv( vector->y, matrix->xy, val );
 794
 795     yz = FT_MulDiv( vector->x, matrix->yx, val ) +
 796          FT_MulDiv( vector->y, matrix->yy, val );
 797
 798     vector->x = xz;
 799     vector->y = yz;
 800   }
 801
 802
 803   /* documentation is in ftcalc.h */
 804
 805   FT_BASE_DEF( FT_Int32 )
 806   FT_SqrtFixed( FT_Int32  x )
 807   {
 808     FT_UInt32  root, rem_hi, rem_lo, test_div;
 809     FT_Int     count;
 810
 811
 812     root = 0;
 813
 814     if ( x > 0 )
 815     {
 816       rem_hi = 0;
 817       rem_lo = x;
 818       count  = 24;
 819       do
 820       {
 821         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
 822         rem_lo <<= 2;
 823         root   <<= 1;
 824         test_div = ( root << 1 ) + 1;
 825
 826         if ( rem_hi >= test_div )
 827         {
 828           rem_hi -= test_div;
 829           root   += 1;
 830         }
 831       } while ( --count );
 832     }
 833
 834     return (FT_Int32)root;
 835   }
 836
 837
 838   /* documentation is in ftcalc.h */
 839
 840   FT_BASE_DEF( FT_Int )
 841   ft_corner_orientation( FT_Pos  in_x,
 842                          FT_Pos  in_y,
 843                          FT_Pos  out_x,
 844                          FT_Pos  out_y )
 845   {
 846     FT_Long  result; /* avoid overflow on 16-bit system */
 847
 848
 849     /* deal with the trivial cases quickly */
 850     if ( in_y == 0 )
 851     {
 852       if ( in_x >= 0 )
 853         result = out_y;
 854       else
 855         result = -out_y;
 856     }
 857     else if ( in_x == 0 )
 858     {
 859       if ( in_y >= 0 )
 860         result = -out_x;
 861       else
 862         result = out_x;
 863     }
 864     else if ( out_y == 0 )
 865     {
 866       if ( out_x >= 0 )
 867         result = in_y;
 868       else
 869         result = -in_y;
 870     }
 871     else if ( out_x == 0 )
 872     {
 873       if ( out_y >= 0 )
 874         result = -in_x;
 875       else
 876         result =  in_x;
 877     }
 878     else /* general case */
 879     {
 880 #ifdef FT_LONG64
 881
 882       FT_Int64  delta = (FT_Int64)in_x * out_y - (FT_Int64)in_y * out_x;
 883
 884
 885       if ( delta == 0 )
 886         result = 0;
 887       else
 888         result = 1 - 2 * ( delta < 0 );
 889
 890 #else
 891
 892       FT_Int64  z1, z2;
 893
 894
 895       /* XXX: this function does not allow 64-bit arguments */
 896       ft_multo64( (FT_Int32)in_x, (FT_Int32)out_y, &z1 );
 897       ft_multo64( (FT_Int32)in_y, (FT_Int32)out_x, &z2 );
 898
 899       if ( z1.hi > z2.hi )
 900         result = +1;
 901       else if ( z1.hi < z2.hi )
 902         result = -1;
 903       else if ( z1.lo > z2.lo )
 904         result = +1;
 905       else if ( z1.lo < z2.lo )
 906         result = -1;
 907       else
 908         result = 0;
 909
 910 #endif
 911     }
 912
 913     /* XXX: only the sign of return value, +1/0/-1 must be used */
 914     return (FT_Int)result;
 915   }
 916
 917
 918   /* documentation is in ftcalc.h */
 919
 920   FT_BASE_DEF( FT_Int )
 921   ft_corner_is_flat( FT_Pos  in_x,
 922                      FT_Pos  in_y,
 923                      FT_Pos  out_x,
 924                      FT_Pos  out_y )
 925   {
 926     FT_Pos  ax = in_x;
 927     FT_Pos  ay = in_y;
 928
 929     FT_Pos  d_in, d_out, d_corner;
 930
 931
 932     if ( ax < 0 )
 933       ax = -ax;
 934     if ( ay < 0 )
 935       ay = -ay;
 936     d_in = ax + ay;
 937
 938     ax = out_x;
 939     if ( ax < 0 )
 940       ax = -ax;
 941     ay = out_y;
 942     if ( ay < 0 )
 943       ay = -ay;
 944     d_out = ax + ay;
 945
 946     ax = out_x + in_x;
 947     if ( ax < 0 )
 948       ax = -ax;
 949     ay = out_y + in_y;
 950     if ( ay < 0 )
 951       ay = -ay;
 952     d_corner = ax + ay;
 953
 954     return ( d_in + d_out - d_corner ) < ( d_corner >> 4 );
 955   }
 956
 957
 958 /* END */