/* mpfr_sqrt -- square root of a floating-point number

Copyright 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.

This file is part of the MPFR Library.

The MPFR Library is free software; you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation; either version 2.1 of the License, or (at your
option) any later version.

The MPFR Library is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
License for more details.

You should have received a copy of the GNU Lesser General Public License
along with the MPFR Library; see the file COPYING.LIB.  If not, write to
the Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
MA 02110-1301, USA. */

#include "mpfr-impl.h"

int
mpfr_sqrt (mpfr_ptr r, mpfr_srcptr u, mp_rnd_t rnd_mode)
{
  mp_size_t rsize; /* number of limbs of r */
  mp_size_t rrsize;
  mp_size_t usize; /* number of limbs of u */
  mp_size_t tsize; /* number of limbs of the sqrtrem remainder */
  mp_size_t k;
  mp_size_t l;
  mp_ptr rp;
  mp_ptr up;
  mp_ptr sp;
  mp_ptr tp;
  mp_limb_t sticky0; /* truncated part of input */
  mp_limb_t sticky1; /* truncated part of rp[0] */
  mp_limb_t sticky;
  int odd_exp;
  int sh; /* number of extra bits in rp[0] */
  int inexact; /* return ternary flag */
  mp_exp_t expr;
  MPFR_TMP_DECL(marker);

  if (MPFR_UNLIKELY(MPFR_IS_SINGULAR(u)))
    {
      if (MPFR_IS_NAN(u))
        {
          MPFR_SET_NAN(r);
          MPFR_RET_NAN;
        }
      else if (MPFR_IS_ZERO(u))
        {
          /* 0+ or 0- */
          MPFR_SET_SAME_SIGN(r, u);
          MPFR_SET_ZERO(r);
          MPFR_RET(0); /* zero is exact */
        }
      else
        {
          MPFR_ASSERTD(MPFR_IS_INF(u));
          /* sqrt(-Inf) = NAN */
          if (MPFR_IS_NEG(u))
            {
              MPFR_SET_NAN(r);
              MPFR_RET_NAN;
            }
          MPFR_SET_POS(r);
          MPFR_SET_INF(r);
          MPFR_RET(0);
        }
    }
  if (MPFR_UNLIKELY(MPFR_IS_NEG(u)))
    {
      MPFR_SET_NAN(r);
      MPFR_RET_NAN;
    }
  MPFR_CLEAR_FLAGS(r);
  MPFR_SET_POS(r);

  rsize = MPFR_LIMB_SIZE(r); /* number of limbs of r */
  rrsize = rsize + rsize;
  usize = MPFR_LIMB_SIZE(u); /* number of limbs of u */
  rp = MPFR_MANT(r);
  up = MPFR_MANT(u);
  sticky0 = MPFR_LIMB_ZERO; /* truncated part of input */
  sticky1 = MPFR_LIMB_ZERO; /* truncated part of rp[0] */
  odd_exp = (unsigned int) MPFR_GET_EXP (u) & 1;
  inexact = -1; /* return ternary flag */

  MPFR_TMP_MARK (marker);
  sp = (mp_limb_t *) MPFR_TMP_ALLOC (rrsize * sizeof (mp_limb_t));

  /* copy the most significant limbs of u to {sp, rrsize} */
  if (MPFR_LIKELY(usize <= rrsize)) /* in case r and u have the same precision,
                                       we have indeed rrsize = 2 * usize */
    {
      k = rrsize - usize;
      if (MPFR_LIKELY(k))
        MPN_ZERO (sp, k);
      if (odd_exp)
        {
          if (MPFR_LIKELY(k))
            sp[k - 1] = mpn_rshift (sp + k, up, usize, 1);
          else
            sticky0 = mpn_rshift (sp, up, usize, 1);
        }
      else
        MPN_COPY (sp + rrsize - usize, up, usize);
    }
  else /* usize > rrsize: truncate the input */
    {
      k = usize - rrsize;
      if (odd_exp)
        sticky0 = mpn_rshift (sp, up + k, rrsize, 1);
      else
        MPN_COPY (sp, up + k, rrsize);
      l = k;
      while (sticky0 == MPFR_LIMB_ZERO && l != 0)
        sticky0 = up[--l];
    }

  /* sticky0 is non-zero iff the truncated part of the input is non-zero */

  tsize = mpn_sqrtrem (rp, tp = sp, sp, rrsize);

  l = tsize;
  sticky = sticky0;
  while (sticky == MPFR_LIMB_ZERO && l != 0)
    sticky = tp[--l];

  /* truncated low bits of rp[0] */
  MPFR_UNSIGNED_MINUS_MODULO(sh,MPFR_PREC(r));
  sticky1 = rp[0] & MPFR_LIMB_MASK(sh);
  rp[0] -= sticky1;

  sticky = sticky || sticky1;

  expr = (MPFR_GET_EXP(u) + odd_exp) / 2;  /* exact */

  if (rnd_mode == GMP_RNDZ || rnd_mode == GMP_RNDD || sticky == MPFR_LIMB_ZERO)
    {
      inexact = (sticky == MPFR_LIMB_ZERO) ? 0 : -1;
      goto truncate;
    }
  else if (rnd_mode == GMP_RNDN)
    {
      /* if sh>0, the round bit is bit (sh-1) of sticky1
                  and the sticky bit is formed by the low sh-1 bits from
                  sticky1, together with {tp, tsize} and sticky0. */
      if (sh)
        {
          if (sticky1 & (MPFR_LIMB_ONE << (sh - 1)))
            { /* round bit is set */
              if (sticky1 == (MPFR_LIMB_ONE << (sh - 1)) && tsize == 0
                  && sticky0 == 0)
                goto even_rule;
              else
                goto add_one_ulp;
            }
          else /* round bit is zero */
            goto truncate; /* with the default inexact=-1 */
        }
      else
        {
          /* if sh=0, we have to compare {tp, tsize} with {rp, rsize}:
                if {tp, tsize} < {rp, rsize}: truncate
                if {tp, tsize} > {rp, rsize}: round up
                if {tp, tsize} = {rp, rsize}: compare the truncated part of the
                                              input to 1/4
                   if < 1/4: truncate
                   if > 1/4: round up
                   if = 1/4: even rounding rule
             Set inexact = -1 if truncate
                 inexact = 1 if add one ulp
                 inexact = 0 if even rounding rule
          */
          if (tsize < rsize)
            inexact = -1;
          else if (tsize > rsize) /* FIXME: may happen? */
            inexact = 1;
          else /* tsize = rsize */
            {
              int cmp;

              cmp = mpn_cmp (tp, rp, rsize);
              if (cmp > 0)
                inexact = 1;
              else if (cmp < 0 || sticky0 == MPFR_LIMB_ZERO)
                inexact = -1;
              /* now tricky case {tp, tsize} = {rp, rsize} */
              /* in case usize <= rrsize, the only case where sticky0 <> 0
                 is when the exponent of u is odd and usize = rrsize (k=0),
                 but in that case the truncated part is exactly 1/2, thus
                 we have to round up.
                 If the exponent of u is odd, and up[k] is odd, the truncated
                 part is >= 1/2, so we round up too. */
              else if (usize <= rrsize || (odd_exp && (up[k] & MPFR_LIMB_ONE)))
                inexact = 1;
              else
                {
                  /* now usize > rrsize:
                     (a) if the exponent of u is even, the 1/4 bit is the
                     2nd most significant bit of up[k-1];
                     (b) if the exponent of u is odd, the 1/4 bit is the
                     1st most significant bit of up[k-1]; */
                  sticky1 = MPFR_LIMB_ONE << (BITS_PER_MP_LIMB - 2 + odd_exp);
                  if (up[k - 1] < sticky1)
                    inexact = -1;
                  else if (up[k - 1] > sticky1)
                    inexact = 1;
                  else
                    {
                      /* up[k - 1] == sticky1: consider low k-1 limbs */
                      while (--k > 0 && up[k - 1] == MPFR_LIMB_ZERO)
                        ;
                      inexact = (k != 0);
                    }
                } /* end of case {tp, tsize} = {rp, rsize} */
            } /* end of case tsize = rsize */
          if (inexact == -1)
            goto truncate;
          else if (inexact == 1)
            goto add_one_ulp;
          /* else go through even_rule */
        }
    }
  else /* rnd_mode=GMP_RDNU, necessarily sticky <> 0, thus add 1 ulp */
    goto add_one_ulp;

 even_rule: /* has to set inexact */
  inexact = (rp[0] & (MPFR_LIMB_ONE << sh)) ? 1 : -1;
  if (inexact == -1)
    goto truncate;
  /* else go through add_one_ulp */

 add_one_ulp:
  inexact = 1; /* always here */
  if (mpn_add_1 (rp, rp, rsize, MPFR_LIMB_ONE << sh))
    {
      expr ++;
      rp[rsize - 1] = MPFR_LIMB_HIGHBIT;
    }

 truncate: /* inexact = 0 or -1 */

  MPFR_SET_EXP(r, expr);

  MPFR_TMP_FREE(marker);

  return inexact;
}