/* vsprintf with automatic memory allocation.

   Copyright (C) 1999, 2002-2019 Free Software Foundation, Inc.

   This program 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, or (at your option)

   any later version.

   This program 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 this program; if not, see <https://www.gnu.org/licenses/>.  */

/* This file can be parametrized with the following macros:

     VASNPRINTF         The name of the function being defined.

     FCHAR_T            The element type of the format string.

     DCHAR_T            The element type of the destination (result) string.

     FCHAR_T_ONLY_ASCII Set to 1 to enable verification that all characters

                        in the format string are ASCII. MUST be set if

                        FCHAR_T and DCHAR_T are not the same type.

     DIRECTIVE          Structure denoting a format directive.

                        Depends on FCHAR_T.

     DIRECTIVES         Structure denoting the set of format directives of a

                        format string.  Depends on FCHAR_T.

     PRINTF_PARSE       Function that parses a format string.

                        Depends on FCHAR_T.

     DCHAR_CPY          memcpy like function for DCHAR_T[] arrays.

     DCHAR_SET          memset like function for DCHAR_T[] arrays.

     DCHAR_MBSNLEN      mbsnlen like function for DCHAR_T[] arrays.

     SNPRINTF           The system's snprintf (or similar) function.

                        This may be either snprintf or swprintf.

     TCHAR_T            The element type of the argument and result string

                        of the said SNPRINTF function.  This may be either

                        char or wchar_t.  The code exploits that

                        sizeof (TCHAR_T) | sizeof (DCHAR_T) and

                        alignof (TCHAR_T) <= alignof (DCHAR_T).

     DCHAR_IS_TCHAR     Set to 1 if DCHAR_T and TCHAR_T are the same type.

     DCHAR_CONV_FROM_ENCODING A function to convert from char[] to DCHAR[].

     DCHAR_IS_UINT8_T   Set to 1 if DCHAR_T is uint8_t.

     DCHAR_IS_UINT16_T  Set to 1 if DCHAR_T is uint16_t.

     DCHAR_IS_UINT32_T  Set to 1 if DCHAR_T is uint32_t.  */

#ifndef _WIN32

/* Tell glibc's <stdio.h> to provide a prototype for snprintf().

   This must come before <config.h> because <config.h> may include

   <features.h>, and once <features.h> has been included, it's too late.  */

#ifndef _GNU_SOURCE

# define _GNU_SOURCE    1

#endif

#endif

#ifndef VASNPRINTF

# include <config.h>

#endif

#include "glib/galloca.h"

#include "g-gnulib.h"

/* Specification.  */

#ifndef VASNPRINTF

# if WIDE_CHAR_VERSION

#  include "vasnwprintf.h"

# else

#  include "vasnprintf.h"

# endif

#endif

#include <locale.h>     /* localeconv() */

#include <stdio.h>      /* snprintf(), sprintf() */

#include <stdlib.h>     /* abort(), malloc(), realloc(), free() */

#include <string.h>     /* memcpy(), strlen() */

#include <errno.h>      /* errno */

#include <limits.h>     /* CHAR_BIT */

#include <float.h>      /* DBL_MAX_EXP, LDBL_MAX_EXP */

#if HAVE_NL_LANGINFO

# include <langinfo.h>

#endif

#ifndef VASNPRINTF

# if WIDE_CHAR_VERSION

#  include "wprintf-parse.h"

# else

#  include "printf-parse.h"

# endif

#endif

/* Checked size_t computations.  */

#include "xsize.h"

#include "verify.h"

#if (NEED_PRINTF_DOUBLE || NEED_PRINTF_LONG_DOUBLE) && !defined IN_LIBINTL

# include <gnulib_math.h>

# include "float+.h"

#endif

#if (NEED_PRINTF_DOUBLE || NEED_PRINTF_INFINITE_DOUBLE) && !defined IN_LIBINTL

# include <gnulib_math.h>

# include "isnand-nolibm.h"

#endif

#if (NEED_PRINTF_LONG_DOUBLE || NEED_PRINTF_INFINITE_LONG_DOUBLE) && !defined IN_LIBINTL

# include <gnulib_math.h>

# include "isnanl-nolibm.h"

# include "fpucw.h"

#endif

#if (NEED_PRINTF_DIRECTIVE_A || NEED_PRINTF_DOUBLE) && !defined IN_LIBINTL

# include <gnulib_math.h>

# include "isnand-nolibm.h"

# include "printf-frexp.h"

#endif

#if (NEED_PRINTF_DIRECTIVE_A || NEED_PRINTF_LONG_DOUBLE) && !defined IN_LIBINTL

# include <gnulib_math.h>

# include "isnanl-nolibm.h"

# include "printf-frexpl.h"

# include "fpucw.h"

#endif

#ifndef FALLTHROUGH

# if __GNUC__ < 7

#  define FALLTHROUGH ((void) 0)

# else

#  define FALLTHROUGH __attribute__ ((__fallthrough__))

# endif

#endif

/* Default parameters.  */

#ifndef VASNPRINTF

# if WIDE_CHAR_VERSION

#  define VASNPRINTF vasnwprintf

#  define FCHAR_T wchar_t

#  define DCHAR_T wchar_t

#  define TCHAR_T wchar_t

#  define DCHAR_IS_TCHAR 1

#  define DIRECTIVE wchar_t_directive

#  define DIRECTIVES wchar_t_directives

#  define PRINTF_PARSE wprintf_parse

#  define DCHAR_CPY wmemcpy

#  define DCHAR_SET wmemset

# else

#  define VASNPRINTF vasnprintf

#  define FCHAR_T char

#  define DCHAR_T char

#  define TCHAR_T char

#  define DCHAR_IS_TCHAR 1

#  define DIRECTIVE char_directive

#  define DIRECTIVES char_directives

#  define PRINTF_PARSE printf_parse

#  define DCHAR_CPY memcpy

#  define DCHAR_SET memset

# endif

#endif

#if WIDE_CHAR_VERSION

  /* TCHAR_T is wchar_t.  */

# define USE_SNPRINTF 1

# if HAVE_DECL__SNWPRINTF

   /* On Windows, the function swprintf() has a different signature than

      on Unix; we use the function _snwprintf() or - on mingw - snwprintf()

      instead.  The mingw function snwprintf() has fewer bugs than the

      MSVCRT function _snwprintf(), so prefer that.  */

#  if defined __MINGW32__

#   define SNPRINTF snwprintf

#  else

#   define SNPRINTF _snwprintf

#   define USE_MSVC__SNPRINTF 1

#  endif

# else

   /* Unix.  */

#  define SNPRINTF swprintf

# endif

#else

  /* TCHAR_T is char.  */

  /* Use snprintf if it exists under the name 'snprintf' or '_snprintf'.

     But don't use it on BeOS, since BeOS snprintf produces no output if the

     size argument is >= 0x3000000.

     Also don't use it on Linux libc5, since there snprintf with size = 1

     writes any output without bounds, like sprintf.  */

# if (HAVE_DECL__SNPRINTF || HAVE_SNPRINTF) && !defined __BEOS__ && !(__GNU_LIBRARY__ == 1)

#  define USE_SNPRINTF 1

# else

#  define USE_SNPRINTF 0

# endif

# if HAVE_DECL__SNPRINTF

   /* Windows.  The mingw function snprintf() has fewer bugs than the MSVCRT

      function _snprintf(), so prefer that.  */

#  if defined __MINGW32__

#   define SNPRINTF snprintf

    /* Here we need to call the native snprintf, not rpl_snprintf.  */

#   undef snprintf

#  else

    /* MSVC versions < 14 did not have snprintf, only _snprintf.  */

#   define SNPRINTF _snprintf

#   define USE_MSVC__SNPRINTF 1

#  endif

# else

   /* Unix.  */

#  define SNPRINTF snprintf

   /* Here we need to call the native snprintf, not rpl_snprintf.  */

#  undef snprintf

# endif

#endif

/* Here we need to call the native sprintf, not rpl_sprintf.  */

#undef sprintf

/* GCC >= 4.0 with -Wall emits unjustified "... may be used uninitialized"

   warnings in this file.  Use -Dlint to suppress them.  */

#if defined GCC_LINT || defined lint

# define IF_LINT(Code) Code

#else

# define IF_LINT(Code) /* empty */

#endif

/* Avoid some warnings from "gcc -Wshadow".

   This file doesn't use the exp() and remainder() functions.  */

#undef exp

#define exp expo

#undef remainder

#define remainder rem

#if (!USE_SNPRINTF || !HAVE_SNPRINTF_RETVAL_C99 || USE_MSVC__SNPRINTF) && !WIDE_CHAR_VERSION

# if (HAVE_STRNLEN && !defined _AIX)

#  define local_strnlen strnlen

# else

#  ifndef local_strnlen_defined

#   define local_strnlen_defined 1

static size_t

local_strnlen (const char *string, size_t maxlen)

{

  const char *end = memchr (string, '\0', maxlen);

  return end ? (size_t) (end - string) : maxlen;

}

#  endif

# endif

#endif

#if (((!USE_SNPRINTF || !HAVE_SNPRINTF_RETVAL_C99 || USE_MSVC__SNPRINTF) && WIDE_CHAR_VERSION) || ((!USE_SNPRINTF || !HAVE_SNPRINTF_RETVAL_C99 || USE_MSVC__SNPRINTF || (NEED_PRINTF_DIRECTIVE_LS && !defined IN_LIBINTL)) && !WIDE_CHAR_VERSION && DCHAR_IS_TCHAR)) && HAVE_WCHAR_T

# if HAVE_WCSLEN

#  define local_wcslen wcslen

# else

   /* Solaris 2.5.1 has wcslen() in a separate library libw.so. To avoid

      a dependency towards this library, here is a local substitute.

      Define this substitute only once, even if this file is included

      twice in the same compilation unit.  */

#  ifndef local_wcslen_defined

#   define local_wcslen_defined 1

static size_t

local_wcslen (const wchar_t *s)

{

  const wchar_t *ptr;

  for (ptr = s; *ptr != (wchar_t) 0; ptr++)

    ;

  return ptr - s;

}

#  endif

# endif

#endif

#if (!USE_SNPRINTF || !HAVE_SNPRINTF_RETVAL_C99 || USE_MSVC__SNPRINTF) && HAVE_WCHAR_T && WIDE_CHAR_VERSION

# if HAVE_WCSNLEN

#  define local_wcsnlen wcsnlen

# else

#  ifndef local_wcsnlen_defined

#   define local_wcsnlen_defined 1

static size_t

local_wcsnlen (const wchar_t *s, size_t maxlen)

{

  const wchar_t *ptr;

  for (ptr = s; maxlen > 0 && *ptr != (wchar_t) 0; ptr++, maxlen--)

    ;

  return ptr - s;

}

#  endif

# endif

#endif

#if (NEED_PRINTF_DIRECTIVE_A || NEED_PRINTF_LONG_DOUBLE || NEED_PRINTF_INFINITE_LONG_DOUBLE || NEED_PRINTF_DOUBLE || NEED_PRINTF_INFINITE_DOUBLE) && !defined IN_LIBINTL

/* Determine the decimal-point character according to the current locale.  */

# ifndef decimal_point_char_defined

#  define decimal_point_char_defined 1

static char

decimal_point_char (void)

{

  const char *point;

  /* Determine it in a multithread-safe way.  We know nl_langinfo is

     multithread-safe on glibc systems and Mac OS X systems, but is not required

     to be multithread-safe by POSIX.  sprintf(), however, is multithread-safe.

     localeconv() is rarely multithread-safe.  */

#  if HAVE_NL_LANGINFO && (__GLIBC__ || defined __UCLIBC__ || (defined __APPLE__ && defined __MACH__))

  point = nl_langinfo (RADIXCHAR);

#  elif 1

  char pointbuf[5];

  sprintf (pointbuf, "%#.0f", 1.0);

  point = &pointbuf[1];

#  else

  point = localeconv () -> decimal_point;

#  endif

  /* The decimal point is always a single byte: either '.' or ','.  */

  return (point[0] != '\0' ? point[0] : '.');

}

# endif

#endif

#if NEED_PRINTF_INFINITE_DOUBLE && !NEED_PRINTF_DOUBLE && !defined IN_LIBINTL

/* Equivalent to !isfinite(x) || x == 0, but does not require libm.  */

static int

is_infinite_or_zero (double x)

{

  return isnand (x) || x + x == x;

}

#endif

#if NEED_PRINTF_INFINITE_LONG_DOUBLE && !NEED_PRINTF_LONG_DOUBLE && !defined IN_LIBINTL

/* Equivalent to !isfinite(x) || x == 0, but does not require libm.  */

static int

is_infinite_or_zerol (long double x)

{

  return isnanl (x) || x + x == x;

}

#endif

#if (NEED_PRINTF_LONG_DOUBLE || NEED_PRINTF_DOUBLE) && !defined IN_LIBINTL

/* Converting 'long double' to decimal without rare rounding bugs requires

   real bignums.  We use the naming conventions of GNU gmp, but vastly simpler

   (and slower) algorithms.  */

typedef unsigned int mp_limb_t;

# define GMP_LIMB_BITS 32

verify (sizeof (mp_limb_t) * CHAR_BIT == GMP_LIMB_BITS);

typedef unsigned long long mp_twolimb_t;

# define GMP_TWOLIMB_BITS 64

verify (sizeof (mp_twolimb_t) * CHAR_BIT == GMP_TWOLIMB_BITS);

/* Representation of a bignum >= 0.  */

typedef struct

{

  size_t nlimbs;

  mp_limb_t *limbs; /* Bits in little-endian order, allocated with malloc().  */

} mpn_t;

/* Compute the product of two bignums >= 0.

   Return the allocated memory in case of success, NULL in case of memory

   allocation failure.  */

static void *

multiply (mpn_t src1, mpn_t src2, mpn_t *dest)

{

  const mp_limb_t *p1;

  const mp_limb_t *p2;

  size_t len1;

  size_t len2;

  if (src1.nlimbs <= src2.nlimbs)

    {

      len1 = src1.nlimbs;

      p1 = src1.limbs;

      len2 = src2.nlimbs;

      p2 = src2.limbs;

    }

  else

    {

      len1 = src2.nlimbs;

      p1 = src2.limbs;

      len2 = src1.nlimbs;

      p2 = src1.limbs;

    }

  /* Now 0 <= len1 <= len2.  */

  if (len1 == 0)

    {

      /* src1 or src2 is zero.  */

      dest->nlimbs = 0;

      dest->limbs = (mp_limb_t *) malloc (1);

    }

  else

    {

      /* Here 1 <= len1 <= len2.  */

      size_t dlen;

      mp_limb_t *dp;

      size_t k, i, j;

      dlen = len1 + len2;

      dp = (mp_limb_t *) malloc (dlen * sizeof (mp_limb_t));

      if (dp == NULL)

        return NULL;

      for (k = len2; k > 0; )

        dp[--k] = 0;

      for (i = 0; i < len1; i++)

        {

          mp_limb_t digit1 = p1[i];

          mp_twolimb_t carry = 0;

          for (j = 0; j < len2; j++)

            {

              mp_limb_t digit2 = p2[j];

              carry += (mp_twolimb_t) digit1 * (mp_twolimb_t) digit2;

              carry += dp[i + j];

              dp[i + j] = (mp_limb_t) carry;

              carry = carry >> GMP_LIMB_BITS;

            }

          dp[i + len2] = (mp_limb_t) carry;

        }

      /* Normalise.  */

      while (dlen > 0 && dp[dlen - 1] == 0)

        dlen--;

      dest->nlimbs = dlen;

      dest->limbs = dp;

    }

  return dest->limbs;

}

/* Compute the quotient of a bignum a >= 0 and a bignum b > 0.

   a is written as  a = q * b + r  with 0 <= r < b.  q is the quotient, r

   the remainder.

   Finally, round-to-even is performed: If r > b/2 or if r = b/2 and q is odd,

   q is incremented.

   Return the allocated memory in case of success, NULL in case of memory

   allocation failure.  */

static void *

divide (mpn_t a, mpn_t b, mpn_t *q)

{

  /* Algorithm:

     First normalise a and b: a=[a[m-1],...,a[0]], b=[b[n-1],...,b[0]]

     with m>=0 and n>0 (in base beta = 2^GMP_LIMB_BITS).

     If m<n, then q:=0 and r:=a.

     If m>=n=1, perform a single-precision division:

       r:=0, j:=m,

       while j>0 do

         {Here (q[m-1]*beta^(m-1)+...+q[j]*beta^j) * b[0] + r*beta^j =

               = a[m-1]*beta^(m-1)+...+a[j]*beta^j und 0<=r<b[0]<beta}

         j:=j-1, r:=r*beta+a[j], q[j]:=floor(r/b[0]), r:=r-b[0]*q[j].

       Normalise [q[m-1],...,q[0]], yields q.

     If m>=n>1, perform a multiple-precision division:

       We have a/b < beta^(m-n+1).

       s:=intDsize-1-(highest bit in b[n-1]), 0<=s<intDsize.

       Shift a and b left by s bits, copying them. r:=a.

       r=[r[m],...,r[0]], b=[b[n-1],...,b[0]] with b[n-1]>=beta/2.

       For j=m-n,...,0: {Here 0 <= r < b*beta^(j+1).}

         Compute q* :

           q* := floor((r[j+n]*beta+r[j+n-1])/b[n-1]).

           In case of overflow (q* >= beta) set q* := beta-1.

           Compute c2 := ((r[j+n]*beta+r[j+n-1]) - q* * b[n-1])*beta + r[j+n-2]

           and c3 := b[n-2] * q*.

           {We have 0 <= c2 < 2*beta^2, even 0 <= c2 < beta^2 if no overflow

            occurred.  Furthermore 0 <= c3 < beta^2.

            If there was overflow and

            r[j+n]*beta+r[j+n-1] - q* * b[n-1] >= beta, i.e. c2 >= beta^2,

            the next test can be skipped.}

           While c3 > c2, {Here 0 <= c2 < c3 < beta^2}

             Put q* := q* - 1, c2 := c2 + b[n-1]*beta, c3 := c3 - b[n-2].

           If q* > 0:

             Put r := r - b * q* * beta^j. In detail:

               [r[n+j],...,r[j]] := [r[n+j],...,r[j]] - q* * [b[n-1],...,b[0]].

               hence: u:=0, for i:=0 to n-1 do

                              u := u + q* * b[i],

                              r[j+i]:=r[j+i]-(u mod beta) (+ beta, if carry),

                              u:=u div beta (+ 1, if carry in subtraction)

                      r[n+j]:=r[n+j]-u.

               {Since always u = (q* * [b[i-1],...,b[0]] div beta^i) + 1

                               < q* + 1 <= beta,

                the carry u does not overflow.}

             If a negative carry occurs, put q* := q* - 1

               and [r[n+j],...,r[j]] := [r[n+j],...,r[j]] + [0,b[n-1],...,b[0]].

         Set q[j] := q*.

       Normalise [q[m-n],..,q[0]]; this yields the quotient q.

       Shift [r[n-1],...,r[0]] right by s bits and normalise; this yields the

       rest r.

       The room for q[j] can be allocated at the memory location of r[n+j].

     Finally, round-to-even:

       Shift r left by 1 bit.

       If r > b or if r = b and q[0] is odd, q := q+1.

   */

  const mp_limb_t *a_ptr = a.limbs;

  size_t a_len = a.nlimbs;

  const mp_limb_t *b_ptr = b.limbs;

  size_t b_len = b.nlimbs;

  mp_limb_t *roomptr;

  mp_limb_t *tmp_roomptr = NULL;

  mp_limb_t *q_ptr;

  size_t q_len;

  mp_limb_t *r_ptr;

  size_t r_len;

  /* Allocate room for a_len+2 digits.

     (Need a_len+1 digits for the real division and 1 more digit for the

     final rounding of q.)  */

  roomptr = (mp_limb_t *) malloc ((a_len + 2) * sizeof (mp_limb_t));

  if (roomptr == NULL)

    return NULL;

  /* Normalise a.  */

  while (a_len > 0 && a_ptr[a_len - 1] == 0)

    a_len--;

  /* Normalise b.  */

  for (;;)

    {

      if (b_len == 0)

        /* Division by zero.  */

        abort ();

      if (b_ptr[b_len - 1] == 0)

        b_len--;

      else

        break;

    }

  /* Here m = a_len >= 0 and n = b_len > 0.  */

  if (a_len < b_len)

    {

      /* m<n: trivial case.  q=0, r := copy of a.  */

      r_ptr = roomptr;

      r_len = a_len;

      memcpy (r_ptr, a_ptr, a_len * sizeof (mp_limb_t));

      q_ptr = roomptr + a_len;

      q_len = 0;

    }

  else if (b_len == 1)

    {

      /* n=1: single precision division.

         beta^(m-1) <= a < beta^m  ==>  beta^(m-2) <= a/b < beta^m  */

      r_ptr = roomptr;

      q_ptr = roomptr + 1;

      {

        mp_limb_t den = b_ptr[0];

        mp_limb_t remainder = 0;

        const mp_limb_t *sourceptr = a_ptr + a_len;

        mp_limb_t *destptr = q_ptr + a_len;

        size_t count;

        for (count = a_len; count > 0; count--)

          {

            mp_twolimb_t num =

              ((mp_twolimb_t) remainder << GMP_LIMB_BITS) | *--sourceptr;

            *--destptr = num / den;

            remainder = num % den;

          }

        /* Normalise and store r.  */

        if (remainder > 0)

          {

            r_ptr[0] = remainder;

            r_len = 1;

          }

        else

          r_len = 0;

        /* Normalise q.  */

        q_len = a_len;

        if (q_ptr[q_len - 1] == 0)

          q_len--;

      }

    }

  else

    {

      /* n>1: multiple precision division.

         beta^(m-1) <= a < beta^m, beta^(n-1) <= b < beta^n  ==>

         beta^(m-n-1) <= a/b < beta^(m-n+1).  */

      /* Determine s.  */

      size_t s;

      {

        mp_limb_t msd = b_ptr[b_len - 1]; /* = b[n-1], > 0 */

        /* Determine s = GMP_LIMB_BITS - integer_length (msd).

           Code copied from gnulib's integer_length.c.  */

# if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)

        s = __builtin_clz (msd);

# else

#  if defined DBL_EXPBIT0_WORD && defined DBL_EXPBIT0_BIT

        if (GMP_LIMB_BITS <= DBL_MANT_BIT)

          {

            /* Use 'double' operations.

               Assumes an IEEE 754 'double' implementation.  */

#   define DBL_EXP_MASK ((DBL_MAX_EXP - DBL_MIN_EXP) | 7)

#   define DBL_EXP_BIAS (DBL_EXP_MASK / 2 - 1)

#   define NWORDS \

     ((sizeof (double) + sizeof (unsigned int) - 1) / sizeof (unsigned int))

            union { double value; unsigned int word[NWORDS]; } m;

            /* Use a single integer to floating-point conversion.  */

            m.value = msd;

            s = GMP_LIMB_BITS

                - (((m.word[DBL_EXPBIT0_WORD] >> DBL_EXPBIT0_BIT) & DBL_EXP_MASK)

                   - DBL_EXP_BIAS);

          }

        else

#   undef NWORDS

#  endif

          {

            s = 31;

            if (msd >= 0x10000)

              {

                msd = msd >> 16;

                s -= 16;

              }

            if (msd >= 0x100)

              {

                msd = msd >> 8;

                s -= 8;

              }

            if (msd >= 0x10)

              {

                msd = msd >> 4;

                s -= 4;

              }

            if (msd >= 0x4)

              {

                msd = msd >> 2;

                s -= 2;

              }

            if (msd >= 0x2)

              {

                msd = msd >> 1;

                s -= 1;

              }

          }

# endif

      }

      /* 0 <= s < GMP_LIMB_BITS.

         Copy b, shifting it left by s bits.  */

      if (s > 0)

        {

          tmp_roomptr = (mp_limb_t *) malloc (b_len * sizeof (mp_limb_t));

          if (tmp_roomptr == NULL)

            {

              free (roomptr);

              return NULL;

            }

          {

            const mp_limb_t *sourceptr = b_ptr;

            mp_limb_t *destptr = tmp_roomptr;

            mp_twolimb_t accu = 0;

            size_t count;

            for (count = b_len; count > 0; count--)

              {

                accu += (mp_twolimb_t) *sourceptr++ << s;

                *destptr++ = (mp_limb_t) accu;

                accu = accu >> GMP_LIMB_BITS;

              }

            /* accu must be zero, since that was how s was determined.  */

            if (accu != 0)

              abort ();

          }

          b_ptr = tmp_roomptr;

        }

      /* Copy a, shifting it left by s bits, yields r.

         Memory layout:

         At the beginning: r = roomptr[0..a_len],

         at the end: r = roomptr[0..b_len-1], q = roomptr[b_len..a_len]  */

      r_ptr = roomptr;

      if (s == 0)

        {

          memcpy (r_ptr, a_ptr, a_len * sizeof (mp_limb_t));

          r_ptr[a_len] = 0;

        }

      else

        {

          const mp_limb_t *sourceptr = a_ptr;

          mp_limb_t *destptr = r_ptr;

          mp_twolimb_t accu = 0;

          size_t count;

          for (count = a_len; count > 0; count--)

            {

              accu += (mp_twolimb_t) *sourceptr++ << s;

              *destptr++ = (mp_limb_t) accu;

              accu = accu >> GMP_LIMB_BITS;

            }

          *destptr++ = (mp_limb_t) accu;

        }

      q_ptr = roomptr + b_len;

      q_len = a_len - b_len + 1; /* q will have m-n+1 limbs */

      {

        size_t j = a_len - b_len; /* m-n */

        mp_limb_t b_msd = b_ptr[b_len - 1]; /* b[n-1] */

        mp_limb_t b_2msd = b_ptr[b_len - 2]; /* b[n-2] */

        mp_twolimb_t b_msdd = /* b[n-1]*beta+b[n-2] */

          ((mp_twolimb_t) b_msd << GMP_LIMB_BITS) | b_2msd;

        /* Division loop, traversed m-n+1 times.

           j counts down, b is unchanged, beta/2 <= b[n-1] < beta.  */

        for (;;)

          {

            mp_limb_t q_star;

            mp_limb_t c1;

            if (r_ptr[j + b_len] < b_msd) /* r[j+n] < b[n-1] ? */

              {

                /* Divide r[j+n]*beta+r[j+n-1] by b[n-1], no overflow.  */

                mp_twolimb_t num =

                  ((mp_twolimb_t) r_ptr[j + b_len] << GMP_LIMB_BITS)

                  | r_ptr[j + b_len - 1];

                q_star = num / b_msd;

                c1 = num % b_msd;

              }

            else

              {

                /* Overflow, hence r[j+n]*beta+r[j+n-1] >= beta*b[n-1].  */

                q_star = (mp_limb_t)~(mp_limb_t)0; /* q* = beta-1 */

                /* Test whether r[j+n]*beta+r[j+n-1] - (beta-1)*b[n-1] >= beta

                   <==> r[j+n]*beta+r[j+n-1] + b[n-1] >= beta*b[n-1]+beta

                   <==> b[n-1] < floor((r[j+n]*beta+r[j+n-1]+b[n-1])/beta)

                        {<= beta !}.

                   If yes, jump directly to the subtraction loop.

                   (Otherwise, r[j+n]*beta+r[j+n-1] - (beta-1)*b[n-1] < beta

                    <==> floor((r[j+n]*beta+r[j+n-1]+b[n-1])/beta) = b[n-1] ) */

                if (r_ptr[j + b_len] > b_msd

                    || (c1 = r_ptr[j + b_len - 1] + b_msd) < b_msd)

                  /* r[j+n] >= b[n-1]+1 or

                     r[j+n] = b[n-1] and the addition r[j+n-1]+b[n-1] gives a

                     carry.  */

                  goto subtract;

              }

            /* q_star = q*,

               c1 = (r[j+n]*beta+r[j+n-1]) - q* * b[n-1] (>=0, <beta).  */

            {

              mp_twolimb_t c2 = /* c1*beta+r[j+n-2] */

                ((mp_twolimb_t) c1 << GMP_LIMB_BITS) | r_ptr[j + b_len - 2];

              mp_twolimb_t c3 = /* b[n-2] * q* */

                (mp_twolimb_t) b_2msd * (mp_twolimb_t) q_star;

              /* While c2 < c3, increase c2 and decrease c3.

                 Consider c3-c2.  While it is > 0, decrease it by

                 b[n-1]*beta+b[n-2].  Because of b[n-1]*beta+b[n-2] >= beta^2/2

                 this can happen only twice.  */

              if (c3 > c2)

                {

                  q_star = q_star - 1; /* q* := q* - 1 */

                  if (c3 - c2 > b_msdd)

                    q_star = q_star - 1; /* q* := q* - 1 */

                }

            }

            if (q_star > 0)

              subtract:

              {

                /* Subtract r := r - b * q* * beta^j.  */

                mp_limb_t cr;

                {

                  const mp_limb_t *sourceptr = b_ptr;

                  mp_limb_t *destptr = r_ptr + j;

                  mp_twolimb_t carry = 0;

                  size_t count;

                  for (count = b_len; count > 0; count--)

                    {

                      /* Here 0 <= carry <= q*.  */

                      carry =

                        carry

                        + (mp_twolimb_t) q_star * (mp_twolimb_t) *sourceptr++

                        + (mp_limb_t) ~(*destptr);

                      /* Here 0 <= carry <= beta*q* + beta-1.  */

                      *destptr++ = ~(mp_limb_t) carry;

                      carry = carry >> GMP_LIMB_BITS; /* <= q* */

                    }

                  cr = (mp_limb_t) carry;

                }

                /* Subtract cr from r_ptr[j + b_len], then forget about

                   r_ptr[j + b_len].  */

                if (cr > r_ptr[j + b_len])

                  {

                    /* Subtraction gave a carry.  */

                    q_star = q_star - 1; /* q* := q* - 1 */

                    /* Add b back.  */

                    {

                      const mp_limb_t *sourceptr = b_ptr;

                      mp_limb_t *destptr = r_ptr + j;

                      mp_limb_t carry = 0;

                      size_t count;

                      for (count = b_len; count > 0; count--)

                        {

                          mp_limb_t source1 = *sourceptr++;

                          mp_limb_t source2 = *destptr;

                          *destptr++ = source1 + source2 + carry;

                          carry =

                            (carry

                             ? source1 >= (mp_limb_t) ~source2

                             : source1 > (mp_limb_t) ~source2);

                        }

                    }

                    /* Forget about the carry and about r[j+n].  */

                  }

              }

            /* q* is determined.  Store it as q[j].  */

            q_ptr[j] = q_star;

            if (j == 0)

              break;

            j--;

          }

      }

      r_len = b_len;

      /* Normalise q.  */

      if (q_ptr[q_len - 1] == 0)

        q_len--;

# if 0 /* Not needed here, since we need r only to compare it with b/2, and

          b is shifted left by s bits.  */

      /* Shift r right by s bits.  */

      if (s > 0)

        {

          mp_limb_t ptr = r_ptr + r_len;

          mp_twolimb_t accu = 0;

          size_t count;

          for (count = r_len; count > 0; count--)

            {

              accu = (mp_twolimb_t) (mp_limb_t) accu << GMP_LIMB_BITS;

              accu += (mp_twolimb_t) *--ptr << (GMP_LIMB_BITS - s);

              *ptr = (mp_limb_t) (accu >> GMP_LIMB_BITS);

            }

        }

# endif

      /* Normalise r.  */

      while (r_len > 0 && r_ptr[r_len - 1] == 0)

        r_len--;

    }

  /* Compare r << 1 with b.  */

  if (r_len > b_len)

    goto increment_q;

  {

    size_t i;

    for (i = b_len;;)

      {

        mp_limb_t r_i =

          (i <= r_len && i > 0 ? r_ptr[i - 1] >> (GMP_LIMB_BITS - 1) : 0)

          | (i < r_len ? r_ptr[i] << 1 : 0);

        mp_limb_t b_i = (i < b_len ? b_ptr[i] : 0);

        if (r_i > b_i)

          goto increment_q;

        if (r_i < b_i)

          goto keep_q;

        if (i == 0)

          break;

        i--;

      }

  }

  if (q_len > 0 && ((q_ptr[0] & 1) != 0))

    /* q is odd.  */

    increment_q:

    {

      size_t i;

      for (i = 0; i < q_len; i++)

        if (++(q_ptr[i]) != 0)

          goto keep_q;

      q_ptr[q_len++] = 1;

    }

  keep_q:

  if (tmp_roomptr != NULL)

    free (tmp_roomptr);

  q->limbs = q_ptr;

  q->nlimbs = q_len;

  return roomptr;

}

/* Convert a bignum a >= 0, multiplied with 10^extra_zeroes, to decimal

   representation.

   Destroys the contents of a.

   Return the allocated memory - containing the decimal digits in low-to-high

   order, terminated with a NUL character - in case of success, NULL in case

   of memory allocation failure.  */

static char *

convert_to_decimal (mpn_t a, size_t extra_zeroes)

{

  mp_limb_t *a_ptr = a.limbs;

  size_t a_len = a.nlimbs;

  /* 0.03345 is slightly larger than log(2)/(9*log(10)).  */

  size_t c_len = 9 * ((size_t)(a_len * (GMP_LIMB_BITS * 0.03345f)) + 1);

  /* We need extra_zeroes bytes for zeroes, followed by c_len bytes for the

     digits of a, followed by 1 byte for the terminating NUL.  */

  char *c_ptr = (char *) malloc (xsum (xsum (extra_zeroes, c_len), 1));

  if (c_ptr != NULL)

    {

      char *d_ptr = c_ptr;

      for (; extra_zeroes > 0; extra_zeroes--)

        *d_ptr++ = '0';

      while (a_len > 0)

        {

          /* Divide a by 10^9, in-place.  */

          mp_limb_t remainder = 0;

          mp_limb_t *ptr = a_ptr + a_len;

          size_t count;

          for (count = a_len; count > 0; count--)

            {

              mp_twolimb_t num =

                ((mp_twolimb_t) remainder << GMP_LIMB_BITS) | *--ptr;

              *ptr = num / 1000000000;

              remainder = num % 1000000000;

            }

          /* Store the remainder as 9 decimal digits.  */

          for (count = 9; count > 0; count--)

            {

              *d_ptr++ = '0' + (remainder % 10);

              remainder = remainder / 10;

            }

          /* Normalize a.  */

          if (a_ptr[a_len - 1] == 0)

            a_len--;

        }

      /* Remove leading zeroes.  */

      while (d_ptr > c_ptr && d_ptr[-1] == '0')

        d_ptr--;

      /* But keep at least one zero.  */

      if (d_ptr == c_ptr)

        *d_ptr++ = '0';

      /* Terminate the string.  */

      *d_ptr = '\0';

    }

  return c_ptr;

}

# if NEED_PRINTF_LONG_DOUBLE

/* Assuming x is finite and >= 0:

   write x as x = 2^e * m, where m is a bignum.

   Return the allocated memory in case of success, NULL in case of memory

   allocation failure.  */

static void *

decode_long_double (long double x, int *ep, mpn_t *mp)

{

  mpn_t m;

  int exp;

  long double y;

  size_t i;

  /* Allocate memory for result.  */

  m.nlimbs = (LDBL_MANT_BIT + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS;

  m.limbs = (mp_limb_t *) malloc (m.nlimbs * sizeof (mp_limb_t));

  if (m.limbs == NULL)

    return NULL;

  /* Split into exponential part and mantissa.  */

  y = frexpl (x, &exp);

  if (!(y >= 0.0L && y < 1.0L))

    abort ();

  /* x = 2^exp * y = 2^(exp - LDBL_MANT_BIT) * (y * 2^LDBL_MANT_BIT), and the

     latter is an integer.  */

  /* Convert the mantissa (y * 2^LDBL_MANT_BIT) to a sequence of limbs.

     I'm not sure whether it's safe to cast a 'long double' value between

     2^31 and 2^32 to 'unsigned int', therefore play safe and cast only

     'long double' values between 0 and 2^16 (to 'unsigned int' or 'int',

     doesn't matter).  */

#  if (LDBL_MANT_BIT % GMP_LIMB_BITS) != 0

#   if (LDBL_MANT_BIT % GMP_LIMB_BITS) > GMP_LIMB_BITS / 2

    {

      mp_limb_t hi, lo;

      y *= (mp_limb_t) 1 << (LDBL_MANT_BIT % (GMP_LIMB_BITS / 2));

      hi = (int) y;

      y -= hi;

      if (!(y >= 0.0L && y < 1.0L))

        abort ();

      y *= (mp_limb_t) 1 << (GMP_LIMB_BITS / 2);

      lo = (int) y;

      y -= lo;

      if (!(y >= 0.0L && y < 1.0L))

        abort ();

      m.limbs[LDBL_MANT_BIT / GMP_LIMB_BITS] = (hi << (GMP_LIMB_BITS / 2)) | lo;

    }

#   else

    {

      mp_limb_t d;

      y *= (mp_limb_t) 1 << (LDBL_MANT_BIT % GMP_LIMB_BITS);

      d = (int) y;

      y -= d;

      if (!(y >= 0.0L && y < 1.0L))

        abort ();

      m.limbs[LDBL_MANT_BIT / GMP_LIMB_BITS] = d;

    }

#   endif

#  endif

  for (i = LDBL_MANT_BIT / GMP_LIMB_BITS; i > 0; )

    {

      mp_limb_t hi, lo;

      y *= (mp_limb_t) 1 << (GMP_LIMB_BITS / 2);

      hi = (int) y;

      y -= hi;

      if (!(y >= 0.0L && y < 1.0L))

        abort ();

      y *= (mp_limb_t) 1 << (GMP_LIMB_BITS / 2);

      lo = (int) y;

      y -= lo;

      if (!(y >= 0.0L && y < 1.0L))

        abort ();

      m.limbs[--i] = (hi << (GMP_LIMB_BITS / 2)) | lo;

    }

#  if 0 /* On FreeBSD 6.1/x86, 'long double' numbers sometimes have excess

           precision.  */

  if (!(y == 0.0L))

    abort ();

#  endif

  /* Normalise.  */

  while (m.nlimbs > 0 && m.limbs[m.nlimbs - 1] == 0)

    m.nlimbs--;

  *mp = m;

  *ep = exp - LDBL_MANT_BIT;

  return m.limbs;

}

# endif

# if NEED_PRINTF_DOUBLE

/* Assuming x is finite and >= 0:

   write x as x = 2^e * m, where m is a bignum.

   Return the allocated memory in case of success, NULL in case of memory

   allocation failure.  */

static void *

decode_double (double x, int *ep, mpn_t *mp)

{

  mpn_t m;

  int exp;

  double y;

  size_t i;

  /* Allocate memory for result.  */

  m.nlimbs = (DBL_MANT_BIT + GMP_LIMB_BITS - 1) / GMP_LIMB_BITS;

  m.limbs = (mp_limb_t *) malloc (m.nlimbs * sizeof (mp_limb_t));

  if (m.limbs == NULL)

    return NULL;

  /* Split into exponential part and mantissa.  */

  y = frexp (x, &exp);

  if (!(y >= 0.0 && y < 1.0))

    abort ();

  /* x = 2^exp * y = 2^(exp - DBL_MANT_BIT) * (y * 2^DBL_MANT_BIT), and the

     latter is an integer.  */

  /* Convert the mantissa (y * 2^DBL_MANT_BIT) to a sequence of limbs.

     I'm not sure whether it's safe to cast a 'double' value between

     2^31 and 2^32 to 'unsigned int', therefore play safe and cast only

     'double' values between 0 and 2^16 (to 'unsigned int' or 'int',

     doesn't matter).  */

#  if (DBL_MANT_BIT % GMP_LIMB_BITS) != 0

#   if (DBL_MANT_BIT % GMP_LIMB_BITS) > GMP_LIMB_BITS / 2

    {

      mp_limb_t hi, lo;

      y *= (mp_limb_t) 1 << (DBL_MANT_BIT % (GMP_LIMB_BITS / 2));

      hi = (int) y;

      y -= hi;

      if (!(y >= 0.0 && y < 1.0))

        abort ();

      y *= (mp_limb_t) 1 << (GMP_LIMB_BITS / 2);

      lo = (int) y;

      y -= lo;

      if (!(y >= 0.0 && y < 1.0))

        abort ();

      m.limbs[DBL_MANT_BIT / GMP_LIMB_BITS] = (hi << (GMP_LIMB_BITS / 2)) | lo;

    }

#   else

    {

      mp_limb_t d;

      y *= (mp_limb_t) 1 << (DBL_MANT_BIT % GMP_LIMB_BITS);

      d = (int) y;

      y -= d;

      if (!(y >= 0.0 && y < 1.0))

        abort ();

      m.limbs[DBL_MANT_BIT / GMP_LIMB_BITS] = d;

    }

#   endif

#  endif

  for (i = DBL_MANT_BIT / GMP_LIMB_BITS; i > 0; )

    {