/*******************************************************************
 *
 *  ttcalc.c
 *
 *    Arithmetic Computations (body).
 *
 *  Copyright 1996, 1997 by
 *  David Turner, Robert Wilhelm, and Werner Lemberg.
 *
 *  This file is part of the FreeType project, and may only be used
 *  modified and distributed under the terms of the FreeType project
 *  license, LICENSE.TXT.  By continuing to use, modify, or distribute 
 *  this file you indicate that you have read the license and
 *  understand and accept it fully.
 *
 ******************************************************************/

#include "ttcalc.h"
#include "tterror.h"
#include "tttables.h"


/* support for 1-complement arithmetic has been totally dropped in this */
/* release. You can still write your own code if you need it..          */

  static const long  Roots[63] =
  {
       1,    1,    2,     3,     4,     5,     8,    11,
      16,   22,   32,    45,    64,    90,   128,   181,
     256,  362,  512,   724,  1024,  1448,  2048,  2896,
    4096, 5892, 8192, 11585, 16384, 23170, 32768, 46340,

      65536,   92681,  131072,   185363,   262144,   370727,
     524288,  741455, 1048576,  1482910,  2097152,  2965820,
    4194304, 5931641, 8388608, 11863283, 16777216, 23726566,

      33554432,   47453132,   67108864,   94906265,
     134217728,  189812531,  268435456,  379625062,
     536870912,  759250125, 1073741824, 1518500250,
    2147483647
  };


#ifdef LONG64

  Int32  MulDiv( Int32  a, Int32  b, Int32  c )
  {
    Int32  s;

    s  = a; a = ABS(a);
    s ^= b; b = ABS(b);
    s ^= c; c = ABS(c);

    a = (Int64)a * b / c;
    return ((s < 0) ? -a : a);
  }


  Int32  MulDiv_Round( Int32  a, Int32  b, Int32  c )
  {
    int  s;

    s  = a; a = ABS(a);
    s ^= b; b = ABS(b);
    s ^= c; c = ABS(c);

    a = ((Int64)a * b + c/2) / c;
    return ((s < 0) ? -a : a);
  }


  Int  Order64( Int64  z )
  {
    int  j = 0;
    while ( z )
    {
      z = (unsigned INT64)z >> 1;
      j++;
    }
    return j - 1;
  }


  Int32  Sqrt64( Int64  l )
  {
    Int64  r, s;

    if ( l <= 0 ) return 0;
    if ( l == 1 ) return 1;

    r = Roots[Order64( l )];

    do
    {
      s = r;
      r = ( r + l/r ) >> 1;
    }
    while ( r > s || r*r > l );

    return r;
  }

#else /* LONG64 */

  Int32  MulDiv( Int32  a, Int32  b, Int32  c )
  {
    Int64  temp;
    Int32  s;

    s  = a; a = ABS(a);
    s ^= b; b = ABS(b);
    s ^= c; c = ABS(c);

    MulTo64( a, b, &temp );
    a = Div64by32( &temp, c );

    return ((s < 0) ? -a : a);
  }


  Int32  MulDiv_Round( Int32  a, Int32  b, Int32  c )
  {
    Int64  temp, temp2;
    Int32  s;

    s  = a; a = ABS(a);
    s ^= b; b = ABS(b);
    s ^= c; c = ABS(c);

    MulTo64( a, b, &temp );
    temp2.hi = (Int32)(c >> 31);
    temp2.lo = (Word32)(c / 2);
    Add64( &temp, &temp2, &temp );
    a = Div64by32( &temp, c );

    return ((s < 0) ? -a : a);
  }


  void  Neg64( Int64*  x )
  {
    /* Remember that -(0x80000000) == 0x80000000 with 2-complement! */
    /* We take care of that here.                                   */

    x->hi ^= 0xFFFFFFFF;
    x->lo ^= 0xFFFFFFFF;
    x->lo++;

    if ( !x->lo )
    {
      x->hi++;
      if ( (Int32)x->hi == 0x80000000 )  /* Check -MaxInt32 - 1 */
      {
        x->lo--;
        x->hi--;  /* We return 0x7FFFFFFF! */
      }
    }
  }


  void  Add64( Int64*  x, Int64*  y, Int64*  z )
  {
    register Word32  lo, hi;

    hi = x->hi + y->hi;
    lo = x->lo + y->lo;

    if ( y->lo )
      if ( (Word32)x->lo >= (Word32)(-y->lo) ) hi++;

    z->lo = lo;
    z->hi = hi;
  }


  void  Sub64( Int64*  x, Int64*  y, Int64*  z )
  {
    register Word32  lo, hi;

    hi = x->hi - y->hi;
    lo = x->lo - y->lo;

    if ( x->lo < y->lo ) hi--;

    z->lo = lo;
    z->hi = hi;
  }


  void  MulTo64( Int32  x, Int32  y, Int64*  z )
  {
    Int32   s;
    Word32  lo1, hi1, lo2, hi2, lo, hi, i1, i2;

    s  = x; x = ABS(x);
    s ^= y; y = ABS(y);

    lo1 = x & 0x0000FFFF;  hi1 = x >> 16;
    lo2 = y & 0x0000FFFF;  hi2 = y >> 16;

    lo = lo1*lo2;
    i1 = lo1*hi2;
    i2 = lo2*hi1;
    hi = hi1*hi2;

    /* Check carry overflow of i1 + i2 */

    if ( i2 )
    {
      if ( i1 >= (Word32)-i2 ) hi += 1 << 16;
      i1 += i2;
    }

    i2 = i1 >> 16;
    i1 = i1 << 16;

    /* Check carry overflow of i1 + lo */
    if ( i1 )
    {
      if ( lo >= (Word32)-i1 ) hi++;
      lo += i1;
    }

    hi += i2;

    z->lo = lo;
    z->hi = hi;

    if (s < 0) Neg64( z );
  }


  Int32  Div64by32( Int64*  x, Int32  y )
  {
    Int32   s;
    Word32  q, r, i, lo;

    s  = x->hi; if (s<0) Neg64(x);
    s ^= y;     y = ABS(y);

    /* Shortcut */
    if ( x->hi == 0 )
    {
      q = x->lo / y;
      return ((s<0) ? -q : q);
    }

    r  = x->hi;
    lo = x->lo;

    if ( r >= (Word32)y )   /* we know y is to be treated as unsigned here */
      return ( (s<0) ? 0x80000001 : 0x7FFFFFFF );
                            /* Return Max/Min Int32 if divide overflow */
                            /* This includes division by zero!         */
    q = 0;
    for ( i = 0; i < 32; i++ )
    {
      r <<= 1;
      q <<= 1;
      r  |= lo >> 31;

      if ( r >= y )
      {
        r -= y;
        q |= 1;
      }
      lo <<= 1;
    }

    return ( (s<0) ? -q : q );
  }


  Int  Order64( Int64*  z )
  {
    Word32  i;
    int     j;

    if ( z->hi )
    {
      i = z->hi;
      j = 32;
    }
    else
    {
      i = z->lo;
      j = 0;
    }

    while ( i > 0 )
    {
      i >>= 1;
      j++;
    }
    return j-1;
  }


  Int32  Sqrt64( Int64*  l )
  {
    Int64  l2;
    Int32  r, s;

    if ( (Int32)l->hi < 0          ||
        (l->hi == 0 && l->lo == 0) )  return 0;

    s = Order64( l );
    if ( s == 0 ) return 1;

    r = Roots[s];
    do
    {
      s = r;
      r = ( r + Div64by32(l,r) ) >> 1;
      MulTo64( r, r,   &l2 );
      Sub64  ( l, &l2, &l2 );
    }
    while ( r > s || (Int32)l2.hi < 0 );

    return r;
  }

#endif /* LONG64 */

#if 0  /* unused by the rest of the library */

  Int  Order32( Int32  z )
  {
    int j;

    j = 0;
    while ( z )
    {
      z = (Word32)z >> 1;
      j++;
    }
    return j - 1;
  }


  Int32  Sqrt32( Int32  l )
  {
    Int32  r, s;

    if ( l <= 0 ) return 0;
    if ( l == 1 ) return 1;

    r = Roots[Order32( l )];
    do
    {
      s = r;
      r = ( r + l/r ) >> 1;
    }
    while ( r > s || r*r > l );
    return r;
  }

#endif

/* END */
