third_party/freetype/src/base/ftcalc.c

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