libraries/freetype-2.0.5/ftcalc.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftcalc.c                                                               */
   4 /*                                                                         */
   5 /*    Arithmetic computations (body).                                      */
   6 /*                                                                         */
   7 /*  Copyright 1996-2001 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_INTERNAL_CALC_H
  37 #include FT_INTERNAL_DEBUG_H
  38 #include FT_INTERNAL_OBJECTS_H
  39
  40
  41 /* we need to define a 64-bits data type here */
  42 #ifndef FT_CONFIG_OPTION_OLD_CALCS
  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 #endif /* !FT_CONFIG_OPTION_OLD_CALCS */
  60
  61
  62   /*************************************************************************/
  63   /*                                                                       */
  64   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
  65   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
  66   /* messages during execution.                                            */
  67   /*                                                                       */
  68 #undef  FT_COMPONENT
  69 #define FT_COMPONENT  trace_calc
  70
  71
  72   /* The following three functions are available regardless of whether */
  73   /* FT_LONG64 or FT_CONFIG_OPTION_OLD_CALCS is defined.               */
  74
  75   /* documentation is in freetype.h */
  76
  77   FT_EXPORT_DEF( FT_Fixed )
  78   FT_RoundFix( FT_Fixed  a )
  79   {
  80     return ( a >= 0 ) ?   ( a + 0x8000L ) & -0x10000L
  81                       : -((-a + 0x8000L ) & -0x10000L );
  82   }
  83
  84
  85   /* documentation is in freetype.h */
  86
  87   FT_EXPORT_DEF( FT_Fixed )
  88   FT_CeilFix( FT_Fixed  a )
  89   {
  90     return ( a >= 0 ) ?   ( a + 0xFFFFL ) & -0x10000L
  91                       : -((-a + 0xFFFFL ) & -0x10000L );
  92   }
  93
  94
  95   /* documentation is in freetype.h */
  96
  97   FT_EXPORT_DEF( FT_Fixed )
  98   FT_FloorFix( FT_Fixed  a )
  99   {
 100     return ( a >= 0 ) ?   a & -0x10000L
 101                       : -((-a) & -0x10000L );
 102   }
 103
 104
 105 #ifdef FT_CONFIG_OPTION_OLD_CALCS
 106
 107   static const FT_Long  ft_square_roots[63] =
 108   {
 109        1L,    1L,    2L,     3L,     4L,     5L,     8L,    11L,
 110       16L,   22L,   32L,    45L,    64L,    90L,   128L,   181L,
 111      256L,  362L,  512L,   724L,  1024L,  1448L,  2048L,  2896L,
 112     4096L, 5892L, 8192L, 11585L, 16384L, 23170L, 32768L, 46340L,
 113
 114       65536L,   92681L,  131072L,   185363L,   262144L,   370727L,
 115      524288L,  741455L, 1048576L,  1482910L,  2097152L,  2965820L,
 116     4194304L, 5931641L, 8388608L, 11863283L, 16777216L, 23726566L,
 117
 118       33554432L,   47453132L,   67108864L,   94906265L,
 119      134217728L,  189812531L,  268435456L,  379625062L,
 120      536870912L,  759250125L, 1073741824L, 1518500250L,
 121     2147483647L
 122   };
 123
 124 #else
 125
 126   /* documentation is in ftcalc.h */
 127
 128   FT_EXPORT_DEF( FT_Int32 )
 129   FT_Sqrt32( FT_Int32  x )
 130   {
 131     FT_ULong  val, root, newroot, mask;
 132
 133
 134     root = 0;
 135     mask = 0x40000000L;
 136     val  = (FT_ULong)x;
 137
 138     do
 139     {
 140       newroot = root + mask;
 141       if ( newroot <= val )
 142       {
 143         val -= newroot;
 144         root = newroot + mask;
 145       }
 146
 147       root >>= 1;
 148       mask >>= 2;
 149
 150     } while ( mask != 0 );
 151
 152     return root;
 153   }
 154
 155 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
 156
 157
 158 #ifdef FT_LONG64
 159
 160   /* documentation is in freetype.h */
 161
 162   FT_EXPORT_DEF( FT_Long )
 163   FT_MulDiv( FT_Long  a,
 164              FT_Long  b,
 165              FT_Long  c )
 166   {
 167     FT_Int   s;
 168     FT_Long  d;
 169
 170
 171     s = 1;
 172     if ( a < 0 ) { a = -a; s = -1; }
 173     if ( b < 0 ) { b = -b; s = -s; }
 174     if ( c < 0 ) { c = -c; s = -s; }
 175
 176     d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
 177                          : 0x7FFFFFFFL );
 178
 179     return ( s > 0 ) ? d : -d;
 180   }
 181
 182
 183   /* documentation is in freetype.h */
 184
 185   FT_EXPORT_DEF( FT_Long )
 186   FT_MulFix( FT_Long  a,
 187              FT_Long  b )
 188   {
 189     FT_Int   s = 1;
 190     FT_Long  c;
 191
 192
 193     if ( a < 0 ) { a = -a; s = -1; }
 194     if ( b < 0 ) { b = -b; s = -s; }
 195
 196     c = (FT_Long)( ( (FT_Int64)a * b + 0x8000 ) >> 16 );
 197     return ( s > 0 ) ? c : -c ;
 198   }
 199
 200
 201   /* documentation is in freetype.h */
 202
 203   FT_EXPORT_DEF( FT_Long )
 204   FT_DivFix( FT_Long  a,
 205              FT_Long  b )
 206   {
 207     FT_Int32   s;
 208     FT_UInt32  q;
 209
 210     s = 1;
 211     if ( a < 0 ) { a = -a; s = -1; }
 212     if ( b < 0 ) { b = -b; s = -s; }
 213
 214     if ( b == 0 )
 215       /* check for division by 0 */
 216       q = 0x7FFFFFFFL;
 217     else
 218       /* compute result directly */
 219       q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
 220
 221     return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
 222   }
 223
 224
 225 #ifdef FT_CONFIG_OPTION_OLD_CALCS
 226
 227   /* a helper function for FT_Sqrt64() */
 228
 229   static int
 230   ft_order64( FT_Int64  z )
 231   {
 232     int  j = 0;
 233
 234
 235     while ( z )
 236     {
 237       z = (unsigned FT_INT64)z >> 1;
 238       j++;
 239     }
 240     return j - 1;
 241   }
 242
 243
 244   /* documentation is in ftcalc.h */
 245
 246   FT_EXPORT_DEF( FT_Int32 )
 247   FT_Sqrt64( FT_Int64  l )
 248   {
 249     FT_Int64  r, s;
 250
 251
 252     if ( l <= 0 ) return 0;
 253     if ( l == 1 ) return 1;
 254
 255     r = ft_square_roots[ft_order64( l )];
 256
 257     do
 258     {
 259       s = r;
 260       r = ( r + l / r ) >> 1;
 261
 262     } while ( r > s || r * r > l );
 263
 264     return (FT_Int32)r;
 265   }
 266
 267 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
 268
 269
 270 #else /* FT_LONG64 */
 271
 272
 273   static void
 274   ft_multo64( FT_UInt32  x,
 275               FT_UInt32  y,
 276               FT_Int64  *z )
 277   {
 278     FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
 279
 280
 281     lo1 = x & 0x0000FFFFU;  hi1 = x >> 16;
 282     lo2 = y & 0x0000FFFFU;  hi2 = y >> 16;
 283
 284     lo = lo1 * lo2;
 285     i1 = lo1 * hi2;
 286     i2 = lo2 * hi1;
 287     hi = hi1 * hi2;
 288
 289     /* Check carry overflow of i1 + i2 */
 290     i1 += i2;
 291     hi += (FT_UInt32)( i1 < i2 ) << 16;
 292
 293     hi += i1 >> 16;
 294     i1  = i1 << 16;
 295
 296     /* Check carry overflow of i1 + lo */
 297     lo += i1;
 298     hi += ( lo < i1 );
 299
 300     z->lo = lo;
 301     z->hi = hi;
 302   }
 303
 304
 305   static FT_UInt32
 306   ft_div64by32( FT_UInt32  hi,
 307                 FT_UInt32  lo,
 308                 FT_UInt32  y )
 309   {
 310     FT_UInt32  r, q;
 311     FT_Int     i;
 312
 313
 314     q = 0;
 315     r = hi;
 316
 317     if ( r >= y )
 318       return (FT_UInt32)0x7FFFFFFFL;
 319
 320     i = 32;
 321     do
 322     {
 323       r <<= 1;
 324       q <<= 1;
 325       r  |= lo >> 31;
 326
 327       if ( r >= (FT_UInt32)y )
 328       {
 329         r -= y;
 330         q |= 1;
 331       }
 332       lo <<= 1;
 333     } while ( --i );
 334
 335     return q;
 336   }
 337
 338
 339   /* documentation is in ftcalc.h */
 340
 341   FT_EXPORT_DEF( void )
 342   FT_Add64( FT_Int64*  x,
 343             FT_Int64*  y,
 344             FT_Int64  *z )
 345   {
 346     register FT_UInt32  lo, hi, max;
 347
 348
 349     max = x->lo > y->lo ? x->lo : y->lo;
 350     lo  = x->lo + y->lo;
 351     hi  = x->hi + y->hi + ( lo < max );
 352
 353     z->lo = lo;
 354     z->hi = hi;
 355   }
 356
 357
 358   /* documentation is in freetype.h */
 359
 360   FT_EXPORT_DEF( FT_Long )
 361   FT_MulDiv( FT_Long  a,
 362              FT_Long  b,
 363              FT_Long  c )
 364   {
 365     long  s;
 366
 367
 368     if ( a == 0 || b == c )
 369       return a;
 370
 371     s  = a; a = ABS( a );
 372     s ^= b; b = ABS( b );
 373     s ^= c; c = ABS( c );
 374
 375     if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
 376     {
 377       a = ( a * b + ( c >> 1 ) ) / c;
 378     }
 379     else if ( c > 0 )
 380     {
 381       FT_Int64  temp, temp2;
 382
 383
 384       ft_multo64( a, b, &temp );
 385
 386       temp2.hi = 0;
 387       temp2.lo = (FT_UInt32)(c >> 1);
 388       FT_Add64( &temp, &temp2, &temp );
 389       a = ft_div64by32( temp.hi, temp.lo, c );
 390     }
 391     else
 392       a = 0x7FFFFFFFL;
 393
 394     return ( s < 0 ? -a : a );
 395   }
 396
 397
 398   /* documentation is in freetype.h */
 399
 400   FT_EXPORT_DEF( FT_Long )
 401   FT_MulFix( FT_Long  a,
 402              FT_Long  b )
 403   {
 404     FT_Long   s;
 405     FT_ULong  ua, ub;
 406
 407
 408     if ( a == 0 || b == 0x10000L )
 409       return a;
 410
 411     s  = a; a = ABS(a);
 412     s ^= b; b = ABS(b);
 413
 414     ua = (FT_ULong)a;
 415     ub = (FT_ULong)b;
 416
 417     if ( ua <= 2048 && ub <= 1048576L )
 418     {
 419       ua = ( ua * ub + 0x8000 ) >> 16;
 420     }
 421     else
 422     {
 423       FT_ULong  al = ua & 0xFFFF;
 424
 425
 426       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
 427            ( ( al * ( ub & 0xFFFF ) + 0x8000 ) >> 16 );
 428     }
 429
 430     return ( s < 0 ? -(FT_Long)ua : ua );
 431   }
 432
 433
 434   /* documentation is in freetype.h */
 435
 436   FT_EXPORT_DEF( FT_Long )
 437   FT_DivFix( FT_Long  a,
 438              FT_Long  b )
 439   {
 440     FT_Int32   s;
 441     FT_UInt32  q;
 442
 443
 444     s  = a; a = ABS(a);
 445     s ^= b; b = ABS(b);
 446
 447     if ( b == 0 )
 448     {
 449       /* check for division by 0 */
 450       q = 0x7FFFFFFFL;
 451     }
 452     else if ( ( a >> 16 ) == 0 )
 453     {
 454       /* compute result directly */
 455       q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
 456     }
 457     else
 458     {
 459       /* we need more bits; we have to do it by hand */
 460       FT_Int64  temp, temp2;
 461
 462       temp.hi  = (FT_Int32) (a >> 16);
 463       temp.lo  = (FT_UInt32)(a << 16);
 464       temp2.hi = 0;
 465       temp2.lo = (FT_UInt32)( b >> 1 );
 466       FT_Add64( &temp, &temp2, &temp );
 467       q = ft_div64by32( temp.hi, temp.lo, b );
 468     }
 469
 470     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 471   }
 472
 473
 474   /* documentation is in ftcalc.h */
 475
 476   FT_EXPORT_DEF( void )
 477   FT_MulTo64( FT_Int32   x,
 478               FT_Int32   y,
 479               FT_Int64  *z )
 480   {
 481     FT_Int32  s;
 482
 483
 484     s  = x; x = ABS( x );
 485     s ^= y; y = ABS( y );
 486
 487     ft_multo64( x, y, z );
 488
 489     if ( s < 0 )
 490     {
 491       z->lo = (FT_UInt32)-(FT_Int32)z->lo;
 492       z->hi = ~z->hi + !( z->lo );
 493     }
 494   }
 495
 496
 497   /* documentation is in ftcalc.h */
 498
 499   FT_EXPORT_DEF( FT_Int32 )
 500   FT_Div64by32( FT_Int64*  x,
 501                 FT_Int32   y )
 502   {
 503     FT_Int32   s;
 504     FT_UInt32  q;
 505
 506
 507     s  = x->hi;
 508     if ( s < 0 )
 509     {
 510       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 511       x->hi = ~x->hi + !( x->lo );
 512     }
 513     s ^= y;  y = ABS( y );
 514
 515     /* Shortcut */
 516     if ( x->hi == 0 )
 517     {
 518       if ( y > 0 )
 519         q = ( x->lo + ( y >> 1 ) ) / y;
 520       else
 521         q = 0x7FFFFFFFL;
 522
 523       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 524     }
 525
 526     q = ft_div64by32( x->hi, x->lo, y );
 527
 528     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 529   }
 530
 531
 532 #ifdef FT_CONFIG_OPTION_OLD_CALCS
 533
 534
 535   /* two helper functions for FT_Sqrt64() */
 536
 537   static void
 538   FT_Sub64( FT_Int64*  x,
 539             FT_Int64*  y,
 540             FT_Int64*  z )
 541   {
 542     register FT_UInt32  lo, hi;
 543
 544
 545     lo = x->lo - y->lo;
 546     hi = x->hi - y->hi - ( (FT_Int32)lo < 0 );
 547
 548     z->lo = lo;
 549     z->hi = hi;
 550   }
 551
 552
 553   static int
 554   ft_order64( FT_Int64*  z )
 555   {
 556     FT_UInt32  i;
 557     int        j;
 558
 559
 560     i = z->lo;
 561     j = 0;
 562     if ( z->hi )
 563     {
 564       i = z->hi;
 565       j = 32;
 566     }
 567
 568     while ( i > 0 )
 569     {
 570       i >>= 1;
 571       j++;
 572     }
 573     return j - 1;
 574   }
 575
 576
 577   /* documentation is in ftcalc.h */
 578
 579   FT_EXPORT_DEF( FT_Int32 )
 580   FT_Sqrt64( FT_Int64*  l )
 581   {
 582     FT_Int64  l2;
 583     FT_Int32  r, s;
 584
 585
 586     if ( (FT_Int32)l->hi < 0          ||
 587          ( l->hi == 0 && l->lo == 0 ) )
 588       return 0;
 589
 590     s = ft_order64( l );
 591     if ( s == 0 )
 592       return 1;
 593
 594     r = ft_square_roots[s];
 595     do
 596     {
 597       s = r;
 598       r = ( r + FT_Div64by32( l, r ) ) >> 1;
 599       FT_MulTo64( r, r,   &l2 );
 600       FT_Sub64  ( l, &l2, &l2 );
 601
 602     } while ( r > s || (FT_Int32)l2.hi < 0 );
 603
 604     return r;
 605   }
 606
 607
 608 #endif /* FT_CONFIG_OPTION_OLD_CALCS */
 609
 610
 611 #endif /* FT_LONG64 */
 612
 613
 614   /* a not-so-fast but working 16.16 fixed point square root function */
 615
 616   FT_EXPORT_DEF( FT_Int32 )
 617   FT_SqrtFixed( FT_Int32  x )
 618   {
 619     FT_UInt32  root, rem_hi, rem_lo, test_div;
 620     FT_Int     count;
 621
 622
 623     root = 0;
 624
 625     if ( x > 0 )
 626     {
 627       rem_hi = 0;
 628       rem_lo = x;
 629       count  = 24;
 630       do
 631       {
 632         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
 633         rem_lo <<= 2;
 634         root   <<= 1;
 635         test_div = ( root << 1 ) + 1;
 636
 637         if ( rem_hi >= test_div )
 638         {
 639           rem_hi -= test_div;
 640           root   += 1;
 641         }
 642       } while ( --count );
 643     }
 644
 645     return (FT_Int32)root;
 646   }
 647
 648
 649 /* END */