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