home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: SysTools / SysTools.zip / ft-beta.zip / freetype / lib / ttcalc.c < prev    next >
C/C++ Source or Header  |  1997-10-06  |  7KB  |  396 lines
  1. /*******************************************************************
  2.  *
  3.  *  ttcalc.c
  4.  *
  5.  *    Arithmetic Computations (body).
  6.  *
  7.  *  Copyright 1996, 1997 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. #include "ttcalc.h"
  19. #include "tterror.h"
  20. #include "tttables.h"
  21.  
  22. #define SIGN_BIT  (Int32)0x80000000
  23.  
  24. /* The following macro is used to test the sign of a 2's complement */
  25. /* value during computations                                        */
  26.  
  27. #ifndef ONE_COMPLEMENT
  28. #define TEST_NEG( x )  ((Int32)(x) < 0)
  29. #else
  30. #define TEST_NEG( x )  ((x) & SIGN_BIT)
  31. #endif
  32.  
  33.   static const long Roots[63] =
  34.   {
  35.        1,    1,    2,     3,     4,     5,     8,    11,
  36.       16,   22,   32,    45,    64,    90,   128,   181,
  37.      256,  362,  512,   724,  1024,  1448,  2048,  2896,
  38.     4096, 5892, 8192, 11585, 16384, 23170, 32768, 46340,
  39.  
  40.       65536,   92681,  131072,   185363,   262144,   370727,
  41.      524288,  741455, 1048576,  1482910,  2097152,  2965820,
  42.     4194304, 5931641, 8388608, 11863283, 16777216, 23726566,
  43.  
  44.        33554432,   47453132,   67108864,   94906265,
  45.       134217728,  189812531,  268435456,  379625062,
  46.       536870912,  759250125, 1073741824, 1518500250,
  47.      2147483647
  48.   };
  49.  
  50.  
  51. #ifdef LONG64
  52.  
  53.   Int32  MulDiv( Int32  a, Int32  b, Int32  c )
  54.   {
  55.     int  s = 0;
  56.  
  57.     if ( a < 0 ) { a = -a; s ^= 1; }
  58.     if ( b < 0 ) { b = -b; s ^= 1; }
  59.     if ( c < 0 ) { c = -c; s ^= 1; }
  60.  
  61.     a = (Int64)a * b / c;
  62.     if ( s ) a = -a;
  63.     return a;
  64.   }
  65.  
  66.  
  67.   Int32  MulDiv_Round( Int32  a, Int32  b, Int32  c )
  68.   {
  69.     int  s = 0;
  70.  
  71.     if ( a < 0 ) { a = -a; s ^= 1; }
  72.     if ( b < 0 ) { b = -b; s ^= 1; }
  73.     if ( c < 0 ) { c = -c; s ^= 1; }
  74.  
  75.     a = ((Int64)a * b + c/2) / c;
  76.     if ( s ) a = -a;
  77.     return a;
  78.   }
  79.  
  80.  
  81.   Int  Order64( Int64  z )
  82.   {
  83.     int  j;
  84.  
  85.     j = 0;
  86.     while ( z )
  87.     {
  88.       z = (unsigned INT64)z >> 1;
  89.       j++;
  90.     }
  91.  
  92.     return j - 1;
  93.   }
  94.  
  95.  
  96.   Int32  Sqrt64( Int64  l )
  97.   {
  98.     Int64  r, s;
  99.  
  100.     if ( l <= 0 ) return 0;
  101.     if ( l == 1 ) return 1;
  102.  
  103.     r = Roots[Order64( l )];
  104.  
  105.     do
  106.     {
  107.       s = r;
  108.       r = ( r + l/r ) >> 1;
  109.     }
  110.     while ( r > s || r*r > l );
  111.  
  112.     return r;
  113.   }
  114.  
  115. #else /* LONG64 */
  116.  
  117.   Int32  MulDiv( Int32  a, Int32  b, Int32  c )
  118.   {
  119.     Int64  temp;
  120.     int    s;
  121.  
  122.     s = 0; 
  123.     if ( a < 0 ) { a = -a; s ^= 1; }
  124.     if ( b < 0 ) { b = -b; s ^= 1; }
  125.     if ( c < 0 ) { c = -c; s ^= 1; }
  126.  
  127.     MulTo64( a, b, &temp );
  128.     a = Div64by32( &temp, c );
  129.  
  130.     if ( s ) a = -a;
  131.     return a;
  132.   }
  133.  
  134.  
  135.   Int32  MulDiv_Round( Int32  a, Int32  b, Int32  c )
  136.   {
  137.     Int64  temp, temp2;
  138.     int    s;
  139.  
  140.     s = 0; 
  141.     if ( a < 0 ) { a = -a; s ^= 1; }
  142.     if ( b < 0 ) { b = -b; s ^= 1; }
  143.     if ( c < 0 ) { c = -c; s ^= 1; }
  144.  
  145.     MulTo64( a, b, &temp );
  146.     temp2.hi = (Int32)(c >> 31);
  147.     temp2.lo = (Word32)(c / 2);
  148.     Add64( &temp, &temp2, &temp );
  149.  
  150.     a = Div64by32( &temp, c );
  151.     if ( s ) a = -a;
  152.     return a;
  153.   }
  154.  
  155.  
  156.   void  Neg64( Int64*  x )
  157.   {
  158.     /* Remember that -(0x80000000) == 0x80000000 with 2-complement! */
  159.     /* We take care of that here.                                   */
  160.  
  161.     x->hi ^= 0xFFFFFFFF;
  162.     x->lo ^= 0xFFFFFFFF;
  163.     x->lo++;
  164.     if ( !x->lo )
  165.     {
  166.       x->hi++;
  167.       if ( (Int32)x->hi == SIGN_BIT )  /* Check -MaxInt32-1 */
  168.       {
  169.         x->lo--;
  170.         x->hi--;  /* We return 0x7FFFFFFF !! */
  171.       }
  172.     }
  173.   }
  174.  
  175.  
  176.   void  Add64( Int64*  x, Int64*  y, Int64*  z )
  177.   {
  178.     register Word32  lo, hi;
  179.  
  180.     hi = x->hi + y->hi;
  181.     lo = x->lo + y->lo;
  182.  
  183.     if ( y->lo )
  184.       if ( (Word32)x->lo >= (Word32)(-y->lo) ) hi++;
  185.  
  186.     z->lo = lo;
  187.     z->hi = hi;
  188.   }
  189.  
  190.  
  191.   void  Sub64( Int64*  x, Int64*  y, Int64*  z )
  192.   {
  193.     register Word32  lo, hi;
  194.  
  195.     hi = x->hi - y->hi;
  196.     lo = x->lo - y->lo;
  197.  
  198.     if ( x->lo < y->lo ) hi--;
  199.  
  200.     z->lo = lo;
  201.     z->hi = hi;
  202.   }
  203.  
  204.  
  205.   void  MulTo64( Int32  x, Int32  y, Int64*  z )
  206.   {
  207.     Int32   s1, s2;
  208.     Word32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;
  209.  
  210.     s1 = x & SIGN_BIT;
  211.     s2 = y & SIGN_BIT;
  212.  
  213.     if (s1) x = -x;
  214.     if (s2) y = -y;
  215.  
  216.     lo1 = x & 0x0000FFFF;  hi1 = x >> 16;
  217.     lo2 = y & 0x0000FFFF;  hi2 = y >> 16;
  218.  
  219.     lo = lo1*lo2;
  220.     i1 = lo1*hi2;
  221.     i2 = lo2*hi1;
  222.     hi = hi1*hi2;
  223.  
  224.     /* Check carry overflow of i1+i2 */
  225.  
  226.     if ( i2 )
  227.     {
  228.       if ( i1 >= (Word32)-i2 ) hi += 1 << 16;
  229.       i1 += i2;
  230.     }
  231.  
  232.     i2 = i1 >> 16;
  233.     i1 = i1 << 16;
  234.  
  235.     /* Check carry overflow of i1+lo */
  236.     if ( i1 )
  237.     {
  238.       if ( lo >= (Word32)-i1 ) hi++;
  239.       lo += i1;
  240.     }
  241.  
  242.     hi += i2;
  243.  
  244.     z->lo = lo;
  245.     z->hi = hi;
  246.  
  247.     if ( s1 ^ s2 ) Neg64( z );
  248.   }
  249.  
  250.  
  251.   Int32  Div64by32( Int64*  x, Int32  y )
  252.   {
  253.     Word32  s1, s2, q, r, i, lo;
  254.  
  255.     s1 = x->hi & SIGN_BIT;
  256.     s2 = y     & SIGN_BIT;
  257.  
  258.     if ( s1 ) Neg64( x );
  259.  
  260.     if ( s2 ) y = -y;
  261.  
  262.     s1 = s1 ^ s2;
  263.     if ( s1 )
  264.       s2 = 0x80000001;  /* MinInt32 */    /* Overflow result */
  265.     else                                  /* in s2           */
  266.       s2 = 0x7FFFFFFF;  /* MaxInt32 */
  267.  
  268.     /* Shortcut */
  269.  
  270.     if ( x->hi == 0 )
  271.     {
  272.       q = x->lo / y;
  273.       if (s1) q = -q;
  274.       return q;
  275.     }
  276.  
  277.     r  = x->hi;
  278.     lo = x->lo;
  279.  
  280.     if ( r >= (Word32)y )   /* we know y is to be treated as unsigned here */
  281.       return s2;            /* Return Max/Min Int32 if divide overflow */
  282.                             /* This includes division by zero !!       */
  283.     q = 0;
  284.  
  285.     for ( i = 0; i < 32; i++ )
  286.     {
  287.       r <<= 1;
  288.       q <<= 1;
  289.       r  |= lo >> 31;
  290.  
  291.       if ( !TEST_NEG( r - y ) )
  292.       {
  293.         r  = r - y;
  294.         q |= 1;
  295.       }
  296.       lo <<= 1;
  297.     }
  298.  
  299.     if ( s1 ) q = -q;
  300.  
  301.     return q;
  302.   }
  303.  
  304.  
  305.  
  306.   Int  Order64( Int64*  z )
  307.   {
  308.     Word32  i;
  309.     int     j;
  310.  
  311.     if ( z->hi )
  312.     {
  313.       i = z->hi;
  314.       j = 32;
  315.     }
  316.     else
  317.     {
  318.       i = z->lo;
  319.       j = 0;
  320.     }
  321.  
  322.     while ( i > 0 )
  323.     {
  324.       i >>= 1;
  325.       j++;
  326.     }
  327.  
  328.     return j - 1;
  329.   }
  330.  
  331.  
  332.  
  333.   Int32  Sqrt64( Int64*  l )
  334.   {
  335.     Int64  l2;
  336.     Int32  r, s, u;
  337.  
  338.     if ( TEST_NEG( l->hi ) ) return 0;
  339.  
  340.     if ( l->hi == 0 && l->lo == 0 ) return 0;
  341.  
  342.     s = Order64( l );
  343.     if ( s == 0 ) return 1;
  344.  
  345.     r = Roots[s];
  346.  
  347.     do
  348.     {
  349.       s = r;
  350.       u = Div64by32( l, r );
  351.       r = ( r + u ) >> 1;
  352.       MulTo64( r, r,   &l2 );
  353.       Sub64  ( l, &l2, &l2 );
  354.     }
  355.     while ( r > s || TEST_NEG( l2.hi ) );
  356.  
  357.     return r;
  358.   }
  359.  
  360. #endif
  361.  
  362.   Int  Order32( Int32  z )
  363.   {
  364.     int j;
  365.  
  366.     j = 0;
  367.     while ( z )
  368.     {
  369.       z = (Word32)z >> 1;
  370.       j++;
  371.     }
  372.  
  373.     return j - 1;
  374.   }
  375.  
  376.  
  377.   Int32  Sqrt32( Int32  l )
  378.   {
  379.     Int32  r, s;
  380.  
  381.     if ( l <= 0 ) return 0;
  382.     if ( l == 1 ) return 1;
  383.  
  384.     r = Roots[Order32( l )];
  385.  
  386.     do
  387.     {
  388.       s = r;
  389.       r = ( r + l/r ) >> 1;
  390.     }
  391.     while ( r > s || r*r > l );
  392.  
  393.     return r;
  394.   }
  395.  
  396.