lib/freetype/src/base/ftcalc.c

   1 /***************************************************************************/
   2 /*                                                                         */
   3 /*  ftcalc.c                                                               */
   4 /*                                                                         */
   5 /*    Arithmetic computations (body).                                      */
   6 /*                                                                         */
   7 /*  Copyright 1996-2001, 2002 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
  43 #ifdef FT_LONG64
  44
  45   typedef FT_INT64  FT_Int64;
  46
  47 #else
  48
  49   typedef struct  FT_Int64_
  50   {
  51     FT_UInt32  lo;
  52     FT_UInt32  hi;
  53
  54   } FT_Int64;
  55
  56 #endif /* FT_LONG64 */
  57
  58
  59   /*************************************************************************/
  60   /*                                                                       */
  61   /* The macro FT_COMPONENT is used in trace mode.  It is an implicit      */
  62   /* parameter of the FT_TRACE() and FT_ERROR() macros, used to print/log  */
  63   /* messages during execution.                                            */
  64   /*                                                                       */
  65 #undef  FT_COMPONENT
  66 #define FT_COMPONENT  trace_calc
  67
  68
  69   /* The following three functions are available regardless of whether */
  70   /* FT_LONG64 is defined.                                             */
  71
  72   /* documentation is in freetype.h */
  73
  74   FT_EXPORT_DEF( FT_Fixed )
  75   FT_RoundFix( FT_Fixed  a )
  76   {
  77     return ( a >= 0 ) ?   ( a + 0x8000L ) & -0x10000L
  78                       : -((-a + 0x8000L ) & -0x10000L );
  79   }
  80
  81
  82   /* documentation is in freetype.h */
  83
  84   FT_EXPORT_DEF( FT_Fixed )
  85   FT_CeilFix( FT_Fixed  a )
  86   {
  87     return ( a >= 0 ) ?   ( a + 0xFFFFL ) & -0x10000L
  88                       : -((-a + 0xFFFFL ) & -0x10000L );
  89   }
  90
  91
  92   /* documentation is in freetype.h */
  93
  94   FT_EXPORT_DEF( FT_Fixed )
  95   FT_FloorFix( FT_Fixed  a )
  96   {
  97     return ( a >= 0 ) ?   a & -0x10000L
  98                       : -((-a) & -0x10000L );
  99   }
 100
 101
 102   /* documentation is in ftcalc.h */
 103
 104   FT_EXPORT_DEF( FT_Int32 )
 105   FT_Sqrt32( FT_Int32  x )
 106   {
 107     FT_ULong  val, root, newroot, mask;
 108
 109
 110     root = 0;
 111     mask = 0x40000000L;
 112     val  = (FT_ULong)x;
 113
 114     do
 115     {
 116       newroot = root + mask;
 117       if ( newroot <= val )
 118       {
 119         val -= newroot;
 120         root = newroot + mask;
 121       }
 122
 123       root >>= 1;
 124       mask >>= 2;
 125
 126     } while ( mask != 0 );
 127
 128     return root;
 129   }
 130
 131
 132 #ifdef FT_LONG64
 133
 134
 135   /* documentation is in freetype.h */
 136
 137   FT_EXPORT_DEF( FT_Long )
 138   FT_MulDiv( FT_Long  a,
 139              FT_Long  b,
 140              FT_Long  c )
 141   {
 142     FT_Int   s;
 143     FT_Long  d;
 144
 145
 146     s = 1;
 147     if ( a < 0 ) { a = -a; s = -1; }
 148     if ( b < 0 ) { b = -b; s = -s; }
 149     if ( c < 0 ) { c = -c; s = -s; }
 150
 151     d = (FT_Long)( c > 0 ? ( (FT_Int64)a * b + ( c >> 1 ) ) / c
 152                          : 0x7FFFFFFFL );
 153
 154     return ( s > 0 ) ? d : -d;
 155   }
 156
 157
 158   /* documentation is in freetype.h */
 159
 160   FT_EXPORT_DEF( FT_Long )
 161   FT_MulFix( FT_Long  a,
 162              FT_Long  b )
 163   {
 164     FT_Int   s = 1;
 165     FT_Long  c;
 166
 167
 168     if ( a < 0 ) { a = -a; s = -1; }
 169     if ( b < 0 ) { b = -b; s = -s; }
 170
 171     c = (FT_Long)( ( (FT_Int64)a * b + 0x8000 ) >> 16 );
 172     return ( s > 0 ) ? c : -c ;
 173   }
 174
 175
 176   /* documentation is in freetype.h */
 177
 178   FT_EXPORT_DEF( FT_Long )
 179   FT_DivFix( FT_Long  a,
 180              FT_Long  b )
 181   {
 182     FT_Int32   s;
 183     FT_UInt32  q;
 184
 185     s = 1;
 186     if ( a < 0 ) { a = -a; s = -1; }
 187     if ( b < 0 ) { b = -b; s = -s; }
 188
 189     if ( b == 0 )
 190       /* check for division by 0 */
 191       q = 0x7FFFFFFFL;
 192     else
 193       /* compute result directly */
 194       q = (FT_UInt32)( ( ( (FT_Int64)a << 16 ) + ( b >> 1 ) ) / b );
 195
 196     return ( s < 0 ? -(FT_Long)q : (FT_Long)q );
 197   }
 198
 199
 200 #else /* FT_LONG64 */
 201
 202
 203   static void
 204   ft_multo64( FT_UInt32  x,
 205               FT_UInt32  y,
 206               FT_Int64  *z )
 207   {
 208     FT_UInt32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
 209
 210
 211     lo1 = x & 0x0000FFFFU;  hi1 = x >> 16;
 212     lo2 = y & 0x0000FFFFU;  hi2 = y >> 16;
 213
 214     lo = lo1 * lo2;
 215     i1 = lo1 * hi2;
 216     i2 = lo2 * hi1;
 217     hi = hi1 * hi2;
 218
 219     /* Check carry overflow of i1 + i2 */
 220     i1 += i2;
 221     hi += (FT_UInt32)( i1 < i2 ) << 16;
 222
 223     hi += i1 >> 16;
 224     i1  = i1 << 16;
 225
 226     /* Check carry overflow of i1 + lo */
 227     lo += i1;
 228     hi += ( lo < i1 );
 229
 230     z->lo = lo;
 231     z->hi = hi;
 232   }
 233
 234
 235   static FT_UInt32
 236   ft_div64by32( FT_UInt32  hi,
 237                 FT_UInt32  lo,
 238                 FT_UInt32  y )
 239   {
 240     FT_UInt32  r, q;
 241     FT_Int     i;
 242
 243
 244     q = 0;
 245     r = hi;
 246
 247     if ( r >= y )
 248       return (FT_UInt32)0x7FFFFFFFL;
 249
 250     i = 32;
 251     do
 252     {
 253       r <<= 1;
 254       q <<= 1;
 255       r  |= lo >> 31;
 256
 257       if ( r >= (FT_UInt32)y )
 258       {
 259         r -= y;
 260         q |= 1;
 261       }
 262       lo <<= 1;
 263     } while ( --i );
 264
 265     return q;
 266   }
 267
 268
 269   /* documentation is in ftcalc.h */
 270
 271   FT_EXPORT_DEF( void )
 272   FT_Add64( FT_Int64*  x,
 273             FT_Int64*  y,
 274             FT_Int64  *z )
 275   {
 276     register FT_UInt32  lo, hi, max;
 277
 278
 279     max = x->lo > y->lo ? x->lo : y->lo;
 280     lo  = x->lo + y->lo;
 281     hi  = x->hi + y->hi + ( lo < max );
 282
 283     z->lo = lo;
 284     z->hi = hi;
 285   }
 286
 287
 288   /* documentation is in freetype.h */
 289
 290   FT_EXPORT_DEF( FT_Long )
 291   FT_MulDiv( FT_Long  a,
 292              FT_Long  b,
 293              FT_Long  c )
 294   {
 295     long  s;
 296
 297
 298     if ( a == 0 || b == c )
 299       return a;
 300
 301     s  = a; a = ABS( a );
 302     s ^= b; b = ABS( b );
 303     s ^= c; c = ABS( c );
 304
 305     if ( a <= 46340L && b <= 46340L && c <= 176095L && c > 0 )
 306     {
 307       a = ( a * b + ( c >> 1 ) ) / c;
 308     }
 309     else if ( c > 0 )
 310     {
 311       FT_Int64  temp, temp2;
 312
 313
 314       ft_multo64( a, b, &temp );
 315
 316       temp2.hi = 0;
 317       temp2.lo = (FT_UInt32)(c >> 1);
 318       FT_Add64( &temp, &temp2, &temp );
 319       a = ft_div64by32( temp.hi, temp.lo, c );
 320     }
 321     else
 322       a = 0x7FFFFFFFL;
 323
 324     return ( s < 0 ? -a : a );
 325   }
 326
 327
 328   /* documentation is in freetype.h */
 329
 330   FT_EXPORT_DEF( FT_Long )
 331   FT_MulFix( FT_Long  a,
 332              FT_Long  b )
 333   {
 334     FT_Long   s;
 335     FT_ULong  ua, ub;
 336
 337
 338     if ( a == 0 || b == 0x10000L )
 339       return a;
 340
 341     s  = a; a = ABS(a);
 342     s ^= b; b = ABS(b);
 343
 344     ua = (FT_ULong)a;
 345     ub = (FT_ULong)b;
 346
 347     if ( ua <= 2048 && ub <= 1048576L )
 348     {
 349       ua = ( ua * ub + 0x8000 ) >> 16;
 350     }
 351     else
 352     {
 353       FT_ULong  al = ua & 0xFFFF;
 354
 355
 356       ua = ( ua >> 16 ) * ub +  al * ( ub >> 16 ) +
 357            ( ( al * ( ub & 0xFFFF ) + 0x8000 ) >> 16 );
 358     }
 359
 360     return ( s < 0 ? -(FT_Long)ua : (FT_Long)ua );
 361   }
 362
 363
 364   /* documentation is in freetype.h */
 365
 366   FT_EXPORT_DEF( FT_Long )
 367   FT_DivFix( FT_Long  a,
 368              FT_Long  b )
 369   {
 370     FT_Int32   s;
 371     FT_UInt32  q;
 372
 373
 374     s  = a; a = ABS(a);
 375     s ^= b; b = ABS(b);
 376
 377     if ( b == 0 )
 378     {
 379       /* check for division by 0 */
 380       q = 0x7FFFFFFFL;
 381     }
 382     else if ( ( a >> 16 ) == 0 )
 383     {
 384       /* compute result directly */
 385       q = (FT_UInt32)( (a << 16) + (b >> 1) ) / (FT_UInt32)b;
 386     }
 387     else
 388     {
 389       /* we need more bits; we have to do it by hand */
 390       FT_Int64  temp, temp2;
 391
 392       temp.hi  = (FT_Int32) (a >> 16);
 393       temp.lo  = (FT_UInt32)(a << 16);
 394       temp2.hi = 0;
 395       temp2.lo = (FT_UInt32)( b >> 1 );
 396       FT_Add64( &temp, &temp2, &temp );
 397       q = ft_div64by32( temp.hi, temp.lo, b );
 398     }
 399
 400     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 401   }
 402
 403
 404   /* documentation is in ftcalc.h */
 405
 406   FT_EXPORT_DEF( void )
 407   FT_MulTo64( FT_Int32   x,
 408               FT_Int32   y,
 409               FT_Int64  *z )
 410   {
 411     FT_Int32  s;
 412
 413
 414     s  = x; x = ABS( x );
 415     s ^= y; y = ABS( y );
 416
 417     ft_multo64( x, y, z );
 418
 419     if ( s < 0 )
 420     {
 421       z->lo = (FT_UInt32)-(FT_Int32)z->lo;
 422       z->hi = ~z->hi + !( z->lo );
 423     }
 424   }
 425
 426
 427   /* documentation is in ftcalc.h */
 428
 429   /* apparently, the second version of this code is not compiled correctly */
 430   /* on Mac machines with the MPW C compiler..  tsss, tsss, tss...         */
 431
 432 #if 1
 433
 434   FT_EXPORT_DEF( FT_Int32 )
 435   FT_Div64by32( FT_Int64*  x,
 436                 FT_Int32   y )
 437   {
 438     FT_Int32   s;
 439     FT_UInt32  q, r, i, lo;
 440
 441
 442     s  = x->hi;
 443     if ( s < 0 )
 444     {
 445       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 446       x->hi = ~x->hi + !x->lo;
 447     }
 448     s ^= y;  y = ABS( y );
 449
 450     /* Shortcut */
 451     if ( x->hi == 0 )
 452     {
 453       if ( y > 0 )
 454         q = x->lo / y;
 455       else
 456         q = 0x7FFFFFFFL;
 457
 458       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 459     }
 460
 461     r  = x->hi;
 462     lo = x->lo;
 463
 464     if ( r >= (FT_UInt32)y ) /* we know y is to be treated as unsigned here */
 465       return ( s < 0 ? 0x80000001UL : 0x7FFFFFFFUL );
 466                              /* Return Max/Min Int32 if division overflow. */
 467                              /* This includes division by zero! */
 468     q = 0;
 469     for ( i = 0; i < 32; i++ )
 470     {
 471       r <<= 1;
 472       q <<= 1;
 473       r  |= lo >> 31;
 474
 475       if ( r >= (FT_UInt32)y )
 476       {
 477         r -= y;
 478         q |= 1;
 479       }
 480       lo <<= 1;
 481     }
 482
 483     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 484   }
 485
 486 #else /* 0 */
 487
 488   FT_EXPORT_DEF( FT_Int32 )
 489   FT_Div64by32( FT_Int64*  x,
 490                 FT_Int32   y )
 491   {
 492     FT_Int32   s;
 493     FT_UInt32  q;
 494
 495
 496     s  = x->hi;
 497     if ( s < 0 )
 498     {
 499       x->lo = (FT_UInt32)-(FT_Int32)x->lo;
 500       x->hi = ~x->hi + !x->lo;
 501     }
 502     s ^= y;  y = ABS( y );
 503
 504     /* Shortcut */
 505     if ( x->hi == 0 )
 506     {
 507       if ( y > 0 )
 508         q = ( x->lo + ( y >> 1 ) ) / y;
 509       else
 510         q = 0x7FFFFFFFL;
 511
 512       return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 513     }
 514
 515     q = ft_div64by32( x->hi, x->lo, y );
 516
 517     return ( s < 0 ? -(FT_Int32)q : (FT_Int32)q );
 518   }
 519
 520 #endif /* 0 */
 521
 522
 523 #endif /* FT_LONG64 */
 524
 525
 526   /* a not-so-fast but working 16.16 fixed point square root function */
 527
 528   FT_EXPORT_DEF( FT_Int32 )
 529   FT_SqrtFixed( FT_Int32  x )
 530   {
 531     FT_UInt32  root, rem_hi, rem_lo, test_div;
 532     FT_Int     count;
 533
 534
 535     root = 0;
 536
 537     if ( x > 0 )
 538     {
 539       rem_hi = 0;
 540       rem_lo = x;
 541       count  = 24;
 542       do
 543       {
 544         rem_hi   = ( rem_hi << 2 ) | ( rem_lo >> 30 );
 545         rem_lo <<= 2;
 546         root   <<= 1;
 547         test_div = ( root << 1 ) + 1;
 548
 549         if ( rem_hi >= test_div )
 550         {
 551           rem_hi -= test_div;
 552           root   += 1;
 553         }
 554       } while ( --count );
 555     }
 556
 557     return (FT_Int32)root;
 558   }
 559
 560
 561 /* END */