LCOV - code coverage report
Current view: | top level - Python - dtoa.c (source / functions) |  |  | Hit | Total | Coverage
Test: | CPython 3.12 LCOV report [commit 5e6661bce9] |  | Lines: | 964 | 1292 | 74.6 %
Date: | 2023-03-20 08:15:36 |  | Functions: | 28 | 28 | 100.0 %
|  |  | Branches: | 559 | 916 | 61.0 %

               Branch data     Line data    Source code
           1                 :            : /****************************************************************
           2                 :            :  *
           3                 :            :  * The author of this software is David M. Gay.
           4                 :            :  *
           5                 :            :  * Copyright (c) 1991, 2000, 2001 by Lucent Technologies.
           6                 :            :  *
           7                 :            :  * Permission to use, copy, modify, and distribute this software for any
           8                 :            :  * purpose without fee is hereby granted, provided that this entire notice
           9                 :            :  * is included in all copies of any software which is or includes a copy
          10                 :            :  * or modification of this software and in all copies of the supporting
          11                 :            :  * documentation for such software.
          12                 :            :  *
          13                 :            :  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
          14                 :            :  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
          15                 :            :  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
          16                 :            :  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
          17                 :            :  *
          18                 :            :  ***************************************************************/
          19                 :            :
          20                 :            : /****************************************************************
          21                 :            :  * This is dtoa.c by David M. Gay, downloaded from
          22                 :            :  * http://www.netlib.org/fp/dtoa.c on April 15, 2009 and modified for
          23                 :            :  * inclusion into the Python core by Mark E. T. Dickinson and Eric V. Smith.
          24                 :            :  *
          25                 :            :  * Please remember to check http://www.netlib.org/fp regularly (and especially
          26                 :            :  * before any Python release) for bugfixes and updates.
          27                 :            :  *
          28                 :            :  * The major modifications from Gay's original code are as follows:
          29                 :            :  *
          30                 :            :  *  0. The original code has been specialized to Python's needs by removing
          31                 :            :  *     many of the #ifdef'd sections.  In particular, code to support VAX and
          32                 :            :  *     IBM floating-point formats, hex NaNs, hex floats, locale-aware
          33                 :            :  *     treatment of the decimal point, and setting of the inexact flag have
          34                 :            :  *     been removed.
          35                 :            :  *
          36                 :            :  *  1. We use PyMem_Malloc and PyMem_Free in place of malloc and free.
          37                 :            :  *
          38                 :            :  *  2. The public functions strtod, dtoa and freedtoa all now have
          39                 :            :  *     a _Py_dg_ prefix.
          40                 :            :  *
          41                 :            :  *  3. Instead of assuming that PyMem_Malloc always succeeds, we thread
          42                 :            :  *     PyMem_Malloc failures through the code.  The functions
          43                 :            :  *
          44                 :            :  *       Balloc, multadd, s2b, i2b, mult, pow5mult, lshift, diff, d2b
          45                 :            :  *
          46                 :            :  *     of return type *Bigint all return NULL to indicate a malloc failure.
          47                 :            :  *     Similarly, rv_alloc and nrv_alloc (return type char *) return NULL on
          48                 :            :  *     failure.  bigcomp now has return type int (it used to be void) and
          49                 :            :  *     returns -1 on failure and 0 otherwise.  _Py_dg_dtoa returns NULL
          50                 :            :  *     on failure.  _Py_dg_strtod indicates failure due to malloc failure
          51                 :            :  *     by returning -1.0, setting errno=ENOMEM and *se to s00.
          52                 :            :  *
          53                 :            :  *  4. The static variable dtoa_result has been removed.  Callers of
          54                 :            :  *     _Py_dg_dtoa are expected to call _Py_dg_freedtoa to free
          55                 :            :  *     the memory allocated by _Py_dg_dtoa.
          56                 :            :  *
          57                 :            :  *  5. The code has been reformatted to better fit with Python's
          58                 :            :  *     C style guide (PEP 7).
          59                 :            :  *
          60                 :            :  *  6. A bug in the memory allocation has been fixed: to avoid FREEing memory
          61                 :            :  *     that hasn't been MALLOC'ed, private_mem should only be used when k <=
          62                 :            :  *     Kmax.
          63                 :            :  *
          64                 :            :  *  7. _Py_dg_strtod has been modified so that it doesn't accept strings with
          65                 :            :  *     leading whitespace.
          66                 :            :  *
          67                 :            :  *  8. A corner case where _Py_dg_dtoa didn't strip trailing zeros has been
          68                 :            :  *     fixed. (bugs.python.org/issue40780)
          69                 :            :  *
          70                 :            :  ***************************************************************/
          71                 :            :
          72                 :            : /* Please send bug reports for the original dtoa.c code to David M. Gay (dmg
          73                 :            :  * at acm dot org, with " at " changed at "@" and " dot " changed to ".").
          74                 :            :  * Please report bugs for this modified version using the Python issue tracker
          75                 :            :  * (http://bugs.python.org). */
          76                 :            :
          77                 :            : /* On a machine with IEEE extended-precision registers, it is
          78                 :            :  * necessary to specify double-precision (53-bit) rounding precision
          79                 :            :  * before invoking strtod or dtoa.  If the machine uses (the equivalent
          80                 :            :  * of) Intel 80x87 arithmetic, the call
          81                 :            :  *      _control87(PC_53, MCW_PC);
          82                 :            :  * does this with many compilers.  Whether this or another call is
          83                 :            :  * appropriate depends on the compiler; for this to work, it may be
          84                 :            :  * necessary to #include "float.h" or another system-dependent header
          85                 :            :  * file.
          86                 :            :  */
          87                 :            :
          88                 :            : /* strtod for IEEE-, VAX-, and IBM-arithmetic machines.
          89                 :            :  *
          90                 :            :  * This strtod returns a nearest machine number to the input decimal
          91                 :            :  * string (or sets errno to ERANGE).  With IEEE arithmetic, ties are
          92                 :            :  * broken by the IEEE round-even rule.  Otherwise ties are broken by
          93                 :            :  * biased rounding (add half and chop).
          94                 :            :  *
          95                 :            :  * Inspired loosely by William D. Clinger's paper "How to Read Floating
          96                 :            :  * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
          97                 :            :  *
          98                 :            :  * Modifications:
          99                 :            :  *
         100                 :            :  *      1. We only require IEEE, IBM, or VAX double-precision
         101                 :            :  *              arithmetic (not IEEE double-extended).
         102                 :            :  *      2. We get by with floating-point arithmetic in a case that
         103                 :            :  *              Clinger missed -- when we're computing d * 10^n
         104                 :            :  *              for a small integer d and the integer n is not too
         105                 :            :  *              much larger than 22 (the maximum integer k for which
         106                 :            :  *              we can represent 10^k exactly), we may be able to
         107                 :            :  *              compute (d*10^k) * 10^(e-k) with just one roundoff.
         108                 :            :  *      3. Rather than a bit-at-a-time adjustment of the binary
         109                 :            :  *              result in the hard case, we use floating-point
         110                 :            :  *              arithmetic to determine the adjustment to within
         111                 :            :  *              one bit; only in really hard cases do we need to
         112                 :            :  *              compute a second residual.
         113                 :            :  *      4. Because of 3., we don't need a large table of powers of 10
         114                 :            :  *              for ten-to-e (just some small tables, e.g. of 10^k
         115                 :            :  *              for 0 <= k <= 22).
         116                 :            :  */
         117                 :            :
         118                 :            : /* Linking of Python's #defines to Gay's #defines starts here. */
         119                 :            :
         120                 :            : #include "Python.h"
         121                 :            : #include "pycore_dtoa.h"          // _PY_SHORT_FLOAT_REPR
         122                 :            : #include "pycore_pystate.h"       // _PyInterpreterState_GET()
         123                 :            : #include <stdlib.h>               // exit()
         124                 :            :
         125                 :            : /* if _PY_SHORT_FLOAT_REPR == 0, then don't even try to compile
         126                 :            :    the following code */
         127                 :            : #if _PY_SHORT_FLOAT_REPR == 1
         128                 :            :
         129                 :            : #include "float.h"
         130                 :            :
         131                 :            : #define MALLOC PyMem_Malloc
         132                 :            : #define FREE PyMem_Free
         133                 :            :
         134                 :            : /* This code should also work for ARM mixed-endian format on little-endian
         135                 :            :    machines, where doubles have byte order 45670123 (in increasing address
         136                 :            :    order, 0 being the least significant byte). */
         137                 :            : #ifdef DOUBLE_IS_LITTLE_ENDIAN_IEEE754
         138                 :            : #  define IEEE_8087
         139                 :            : #endif
         140                 :            : #if defined(DOUBLE_IS_BIG_ENDIAN_IEEE754) ||  \
         141                 :            :   defined(DOUBLE_IS_ARM_MIXED_ENDIAN_IEEE754)
         142                 :            : #  define IEEE_MC68k
         143                 :            : #endif
         144                 :            : #if defined(IEEE_8087) + defined(IEEE_MC68k) != 1
         145                 :            : #error "Exactly one of IEEE_8087 or IEEE_MC68k should be defined."
         146                 :            : #endif
         147                 :            :
         148                 :            : /* The code below assumes that the endianness of integers matches the
         149                 :            :    endianness of the two 32-bit words of a double.  Check this. */
         150                 :            : #if defined(WORDS_BIGENDIAN) && (defined(DOUBLE_IS_LITTLE_ENDIAN_IEEE754) || \
         151                 :            :                                  defined(DOUBLE_IS_ARM_MIXED_ENDIAN_IEEE754))
         152                 :            : #error "doubles and ints have incompatible endianness"
         153                 :            : #endif
         154                 :            :
         155                 :            : #if !defined(WORDS_BIGENDIAN) && defined(DOUBLE_IS_BIG_ENDIAN_IEEE754)
         156                 :            : #error "doubles and ints have incompatible endianness"
         157                 :            : #endif
         158                 :            :
         159                 :            :
         160                 :            : // ULong is defined in pycore_dtoa.h.
         161                 :            : typedef int32_t Long;
         162                 :            : typedef uint64_t ULLong;
         163                 :            :
         164                 :            : #undef DEBUG
         165                 :            : #ifdef Py_DEBUG
         166                 :            : #define DEBUG
         167                 :            : #endif
         168                 :            :
         169                 :            : /* End Python #define linking */
         170                 :            :
         171                 :            : #ifdef DEBUG
         172                 :            : #define Bug(x) {fprintf(stderr, "%s\n", x); exit(1);}
         173                 :            : #endif
         174                 :            :
         175                 :            : #ifdef __cplusplus
         176                 :            : extern "C" {
         177                 :            : #endif
         178                 :            :
         179                 :            : typedef union { double d; ULong L[2]; } U;
         180                 :            :
         181                 :            : #ifdef IEEE_8087
         182                 :            : #define word0(x) (x)->L[1]
         183                 :            : #define word1(x) (x)->L[0]
         184                 :            : #else
         185                 :            : #define word0(x) (x)->L[0]
         186                 :            : #define word1(x) (x)->L[1]
         187                 :            : #endif
         188                 :            : #define dval(x) (x)->d
         189                 :            :
         190                 :            : #ifndef STRTOD_DIGLIM
         191                 :            : #define STRTOD_DIGLIM 40
         192                 :            : #endif
         193                 :            :
         194                 :            : /* maximum permitted exponent value for strtod; exponents larger than
         195                 :            :    MAX_ABS_EXP in absolute value get truncated to +-MAX_ABS_EXP.  MAX_ABS_EXP
         196                 :            :    should fit into an int. */
         197                 :            : #ifndef MAX_ABS_EXP
         198                 :            : #define MAX_ABS_EXP 1100000000U
         199                 :            : #endif
         200                 :            : /* Bound on length of pieces of input strings in _Py_dg_strtod; specifically,
         201                 :            :    this is used to bound the total number of digits ignoring leading zeros and
         202                 :            :    the number of digits that follow the decimal point.  Ideally, MAX_DIGITS
         203                 :            :    should satisfy MAX_DIGITS + 400 < MAX_ABS_EXP; that ensures that the
         204                 :            :    exponent clipping in _Py_dg_strtod can't affect the value of the output. */
         205                 :            : #ifndef MAX_DIGITS
         206                 :            : #define MAX_DIGITS 1000000000U
         207                 :            : #endif
         208                 :            :
         209                 :            : /* Guard against trying to use the above values on unusual platforms with ints
         210                 :            :  * of width less than 32 bits. */
         211                 :            : #if MAX_ABS_EXP > INT_MAX
         212                 :            : #error "MAX_ABS_EXP should fit in an int"
         213                 :            : #endif
         214                 :            : #if MAX_DIGITS > INT_MAX
         215                 :            : #error "MAX_DIGITS should fit in an int"
         216                 :            : #endif
         217                 :            :
         218                 :            : /* The following definition of Storeinc is appropriate for MIPS processors.
         219                 :            :  * An alternative that might be better on some machines is
         220                 :            :  * #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff)
         221                 :            :  */
         222                 :            : #if defined(IEEE_8087)
         223                 :            : #define Storeinc(a,b,c) (((unsigned short *)a)[1] = (unsigned short)b,  \
         224                 :            :                          ((unsigned short *)a)[0] = (unsigned short)c, a++)
         225                 :            : #else
         226                 :            : #define Storeinc(a,b,c) (((unsigned short *)a)[0] = (unsigned short)b,  \
         227                 :            :                          ((unsigned short *)a)[1] = (unsigned short)c, a++)
         228                 :            : #endif
         229                 :            :
         230                 :            : /* #define P DBL_MANT_DIG */
         231                 :            : /* Ten_pmax = floor(P*log(2)/log(5)) */
         232                 :            : /* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */
         233                 :            : /* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
         234                 :            : /* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */
         235                 :            :
         236                 :            : #define Exp_shift  20
         237                 :            : #define Exp_shift1 20
         238                 :            : #define Exp_msk1    0x100000
         239                 :            : #define Exp_msk11   0x100000
         240                 :            : #define Exp_mask  0x7ff00000
         241                 :            : #define P 53
         242                 :            : #define Nbits 53
         243                 :            : #define Bias 1023
         244                 :            : #define Emax 1023
         245                 :            : #define Emin (-1022)
         246                 :            : #define Etiny (-1074)  /* smallest denormal is 2**Etiny */
         247                 :            : #define Exp_1  0x3ff00000
         248                 :            : #define Exp_11 0x3ff00000
         249                 :            : #define Ebits 11
         250                 :            : #define Frac_mask  0xfffff
         251                 :            : #define Frac_mask1 0xfffff
         252                 :            : #define Ten_pmax 22
         253                 :            : #define Bletch 0x10
         254                 :            : #define Bndry_mask  0xfffff
         255                 :            : #define Bndry_mask1 0xfffff
         256                 :            : #define Sign_bit 0x80000000
         257                 :            : #define Log2P 1
         258                 :            : #define Tiny0 0
         259                 :            : #define Tiny1 1
         260                 :            : #define Quick_max 14
         261                 :            : #define Int_max 14
         262                 :            :
         263                 :            : #ifndef Flt_Rounds
         264                 :            : #ifdef FLT_ROUNDS
         265                 :            : #define Flt_Rounds FLT_ROUNDS
         266                 :            : #else
         267                 :            : #define Flt_Rounds 1
         268                 :            : #endif
         269                 :            : #endif /*Flt_Rounds*/
         270                 :            :
         271                 :            : #define Rounding Flt_Rounds
         272                 :            :
         273                 :            : #define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1))
         274                 :            : #define Big1 0xffffffff
         275                 :            :
         276                 :            : /* Standard NaN used by _Py_dg_stdnan. */
         277                 :            :
         278                 :            : #define NAN_WORD0 0x7ff80000
         279                 :            : #define NAN_WORD1 0
         280                 :            :
         281                 :            : /* Bits of the representation of positive infinity. */
         282                 :            :
         283                 :            : #define POSINF_WORD0 0x7ff00000
         284                 :            : #define POSINF_WORD1 0
         285                 :            :
         286                 :            : /* struct BCinfo is used to pass information from _Py_dg_strtod to bigcomp */
         287                 :            :
         288                 :            : typedef struct BCinfo BCinfo;
         289                 :            : struct
         290                 :            : BCinfo {
         291                 :            :     int e0, nd, nd0, scale;
         292                 :            : };
         293                 :            :
         294                 :            : #define FFFFFFFF 0xffffffffUL
         295                 :            :
         296                 :            : /* struct Bigint is used to represent arbitrary-precision integers.  These
         297                 :            :    integers are stored in sign-magnitude format, with the magnitude stored as
         298                 :            :    an array of base 2**32 digits.  Bigints are always normalized: if x is a
         299                 :            :    Bigint then x->wds >= 1, and either x->wds == 1 or x[wds-1] is nonzero.
         300                 :            :
         301                 :            :    The Bigint fields are as follows:
         302                 :            :
         303                 :            :      - next is a header used by Balloc and Bfree to keep track of lists
         304                 :            :          of freed Bigints;  it's also used for the linked list of
         305                 :            :          powers of 5 of the form 5**2**i used by pow5mult.
         306                 :            :      - k indicates which pool this Bigint was allocated from
         307                 :            :      - maxwds is the maximum number of words space was allocated for
         308                 :            :        (usually maxwds == 2**k)
         309                 :            :      - sign is 1 for negative Bigints, 0 for positive.  The sign is unused
         310                 :            :        (ignored on inputs, set to 0 on outputs) in almost all operations
         311                 :            :        involving Bigints: a notable exception is the diff function, which
         312                 :            :        ignores signs on inputs but sets the sign of the output correctly.
         313                 :            :      - wds is the actual number of significant words
         314                 :            :      - x contains the vector of words (digits) for this Bigint, from least
         315                 :            :        significant (x[0]) to most significant (x[wds-1]).
         316                 :            : */
         317                 :            :
         318                 :            : // struct Bigint is defined in pycore_dtoa.h.
         319                 :            : typedef struct Bigint Bigint;
         320                 :            :
         321                 :            : #ifndef Py_USING_MEMORY_DEBUGGER
         322                 :            :
         323                 :            : /* Memory management: memory is allocated from, and returned to, Kmax+1 pools
         324                 :            :    of memory, where pool k (0 <= k <= Kmax) is for Bigints b with b->maxwds ==
         325                 :            :    1 << k.  These pools are maintained as linked lists, with freelist[k]
         326                 :            :    pointing to the head of the list for pool k.
         327                 :            :
         328                 :            :    On allocation, if there's no free slot in the appropriate pool, MALLOC is
         329                 :            :    called to get more memory.  This memory is not returned to the system until
         330                 :            :    Python quits.  There's also a private memory pool that's allocated from
         331                 :            :    in preference to using MALLOC.
         332                 :            :
         333                 :            :    For Bigints with more than (1 << Kmax) digits (which implies at least 1233
         334                 :            :    decimal digits), memory is directly allocated using MALLOC, and freed using
         335                 :            :    FREE.
         336                 :            :
         337                 :            :    XXX: it would be easy to bypass this memory-management system and
         338                 :            :    translate each call to Balloc into a call to PyMem_Malloc, and each
         339                 :            :    Bfree to PyMem_Free.  Investigate whether this has any significant
         340                 :            :    performance on impact. */
         341                 :            :
         342                 :            : #define freelist interp->dtoa.freelist
         343                 :            : #define private_mem interp->dtoa.preallocated
         344                 :            : #define pmem_next interp->dtoa.preallocated_next
         345                 :            :
         346                 :            : /* Allocate space for a Bigint with up to 1<<k digits */
         347                 :            :
         348                 :            : static Bigint *
         349                 :      43884 : Balloc(int k)
         350                 :            : {
         351                 :            :     int x;
         352                 :            :     Bigint *rv;
         353                 :            :     unsigned int len;
         354                 :      43884 :     PyInterpreterState *interp = _PyInterpreterState_GET();
         355                 :            :
         356   [ +  -  +  + ]:      43884 :     if (k <= Bigint_Kmax && (rv = freelist[k]))
         357                 :      43850 :         freelist[k] = rv->next;
         358                 :            :     else {
         359                 :         34 :         x = 1 << k;
         360                 :         34 :         len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
         361                 :         34 :             /sizeof(double);
         362         [ +  - ]:         34 :         if (k <= Bigint_Kmax &&
         363         [ +  + ]:         34 :             pmem_next - private_mem + len <= (Py_ssize_t)Bigint_PREALLOC_SIZE
         364                 :            :         ) {
         365                 :         31 :             rv = (Bigint*)pmem_next;
         366                 :         31 :             pmem_next += len;
         367                 :            :         }
         368                 :            :         else {
         369                 :          3 :             rv = (Bigint*)MALLOC(len*sizeof(double));
         370         [ -  + ]:          3 :             if (rv == NULL)
         371                 :          0 :                 return NULL;
         372                 :            :         }
         373                 :         34 :         rv->k = k;
         374                 :         34 :         rv->maxwds = x;
         375                 :            :     }
         376                 :      43884 :     rv->sign = rv->wds = 0;
         377                 :      43884 :     return rv;
         378                 :            : }
         379                 :            :
         380                 :            : /* Free a Bigint allocated with Balloc */
         381                 :            :
         382                 :            : static void
         383                 :      80392 : Bfree(Bigint *v)
         384                 :            : {
         385         [ +  + ]:      80392 :     if (v) {
         386         [ -  + ]:      43877 :         if (v->k > Bigint_Kmax)
         387                 :          0 :             FREE((void*)v);
         388                 :            :         else {
         389                 :      43877 :             PyInterpreterState *interp = _PyInterpreterState_GET();
         390                 :      43877 :             v->next = freelist[v->k];
         391                 :      43877 :             freelist[v->k] = v;
         392                 :            :         }
         393                 :            :     }
         394                 :      80392 : }
         395                 :            :
         396                 :            : #undef pmem_next
         397                 :            : #undef private_mem
         398                 :            : #undef freelist
         399                 :            :
         400                 :            : #else
         401                 :            :
         402                 :            : /* Alternative versions of Balloc and Bfree that use PyMem_Malloc and
         403                 :            :    PyMem_Free directly in place of the custom memory allocation scheme above.
         404                 :            :    These are provided for the benefit of memory debugging tools like
         405                 :            :    Valgrind. */
         406                 :            :
         407                 :            : /* Allocate space for a Bigint with up to 1<<k digits */
         408                 :            :
         409                 :            : static Bigint *
         410                 :            : Balloc(int k)
         411                 :            : {
         412                 :            :     int x;
         413                 :            :     Bigint *rv;
         414                 :            :     unsigned int len;
         415                 :            :
         416                 :            :     x = 1 << k;
         417                 :            :     len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
         418                 :            :         /sizeof(double);
         419                 :            :
         420                 :            :     rv = (Bigint*)MALLOC(len*sizeof(double));
         421                 :            :     if (rv == NULL)
         422                 :            :         return NULL;
         423                 :            :
         424                 :            :     rv->k = k;
         425                 :            :     rv->maxwds = x;
         426                 :            :     rv->sign = rv->wds = 0;
         427                 :            :     return rv;
         428                 :            : }
         429                 :            :
         430                 :            : /* Free a Bigint allocated with Balloc */
         431                 :            :
         432                 :            : static void
         433                 :            : Bfree(Bigint *v)
         434                 :            : {
         435                 :            :     if (v) {
         436                 :            :         FREE((void*)v);
         437                 :            :     }
         438                 :            : }
         439                 :            :
         440                 :            : #endif /* Py_USING_MEMORY_DEBUGGER */
         441                 :            :
         442                 :            : #define Bcopy(x,y) memcpy((char *)&x->sign, (char *)&y->sign,   \
         443                 :            :                           y->wds*sizeof(Long) + 2*sizeof(int))
         444                 :            :
         445                 :            : /* Multiply a Bigint b by m and add a.  Either modifies b in place and returns
         446                 :            :    a pointer to the modified b, or Bfrees b and returns a pointer to a copy.
         447                 :            :    On failure, return NULL.  In this case, b will have been already freed. */
         448                 :            :
         449                 :            : static Bigint *
         450                 :      34286 : multadd(Bigint *b, int m, int a)       /* multiply by m and add a */
         451                 :            : {
         452                 :            :     int i, wds;
         453                 :            :     ULong *x;
         454                 :            :     ULLong carry, y;
         455                 :            :     Bigint *b1;
         456                 :            :
         457                 :      34286 :     wds = b->wds;
         458                 :      34286 :     x = b->x;
         459                 :      34286 :     i = 0;
         460                 :      34286 :     carry = a;
         461                 :            :     do {
         462                 :      60645 :         y = *x * (ULLong)m + carry;
         463                 :      60645 :         carry = y >> 32;
         464                 :      60645 :         *x++ = (ULong)(y & FFFFFFFF);
         465                 :            :     }
         466         [ +  + ]:      60645 :     while(++i < wds);
         467         [ +  + ]:      34286 :     if (carry) {
         468         [ +  + ]:       3966 :         if (wds >= b->maxwds) {
         469                 :          2 :             b1 = Balloc(b->k+1);
         470         [ -  + ]:          2 :             if (b1 == NULL){
         471                 :          0 :                 Bfree(b);
         472                 :          0 :                 return NULL;
         473                 :            :             }
         474                 :          2 :             Bcopy(b1, b);
         475                 :          2 :             Bfree(b);
         476                 :          2 :             b = b1;
         477                 :            :         }
         478                 :       3966 :         b->x[wds++] = (ULong)carry;
         479                 :       3966 :         b->wds = wds;
         480                 :            :     }
         481                 :      34286 :     return b;
         482                 :            : }
         483                 :            :
         484                 :            : /* convert a string s containing nd decimal digits (possibly containing a
         485                 :            :    decimal separator at position nd0, which is ignored) to a Bigint.  This
         486                 :            :    function carries on where the parsing code in _Py_dg_strtod leaves off: on
         487                 :            :    entry, y9 contains the result of converting the first 9 digits.  Returns
         488                 :            :    NULL on failure. */
         489                 :            :
         490                 :            : static Bigint *
         491                 :       4172 : s2b(const char *s, int nd0, int nd, ULong y9)
         492                 :            : {
         493                 :            :     Bigint *b;
         494                 :            :     int i, k;
         495                 :            :     Long x, y;
         496                 :            :
         497                 :       4172 :     x = (nd + 8) / 9;
         498         [ +  + ]:       8175 :     for(k = 0, y = 1; x > y; y <<= 1, k++) ;
         499                 :       4172 :     b = Balloc(k);
         500         [ -  + ]:       4172 :     if (b == NULL)
         501                 :          0 :         return NULL;
         502                 :       4172 :     b->x[0] = y9;
         503                 :       4172 :     b->wds = 1;
         504                 :            :
         505         [ +  + ]:       4172 :     if (nd <= 9)
         506                 :        284 :       return b;
         507                 :            :
         508                 :       3888 :     s += 9;
         509         [ +  + ]:      12319 :     for (i = 9; i < nd0; i++) {
         510                 :       8431 :         b = multadd(b, 10, *s++ - '0');
         511         [ -  + ]:       8431 :         if (b == NULL)
         512                 :          0 :             return NULL;
         513                 :            :     }
         514                 :       3888 :     s++;
         515         [ +  + ]:      26642 :     for(; i < nd; i++) {
         516                 :      22754 :         b = multadd(b, 10, *s++ - '0');
         517         [ -  + ]:      22754 :         if (b == NULL)
         518                 :          0 :             return NULL;
         519                 :            :     }
         520                 :       3888 :     return b;
         521                 :            : }
         522                 :            :
         523                 :            : /* count leading 0 bits in the 32-bit integer x. */
         524                 :            :
         525                 :            : static int
         526                 :       5809 : hi0bits(ULong x)
         527                 :            : {
         528                 :       5809 :     int k = 0;
         529                 :            :
         530         [ +  + ]:       5809 :     if (!(x & 0xffff0000)) {
         531                 :       4956 :         k = 16;
         532                 :       4956 :         x <<= 16;
         533                 :            :     }
         534         [ +  + ]:       5809 :     if (!(x & 0xff000000)) {
         535                 :       4053 :         k += 8;
         536                 :       4053 :         x <<= 8;
         537                 :            :     }
         538         [ +  + ]:       5809 :     if (!(x & 0xf0000000)) {
         539                 :       2005 :         k += 4;
         540                 :       2005 :         x <<= 4;
         541                 :            :     }
         542         [ +  + ]:       5809 :     if (!(x & 0xc0000000)) {
         543                 :       3178 :         k += 2;
         544                 :       3178 :         x <<= 2;
         545                 :            :     }
         546         [ +  + ]:       5809 :     if (!(x & 0x80000000)) {
         547                 :       2277 :         k++;
         548         [ -  + ]:       2277 :         if (!(x & 0x40000000))
         549                 :          0 :             return 32;
         550                 :            :     }
         551                 :       5809 :     return k;
         552                 :            : }
         553                 :            :
         554                 :            : /* count trailing 0 bits in the 32-bit integer y, and shift y right by that
         555                 :            :    number of bits. */
         556                 :            :
         557                 :            : static int
         558                 :         58 : lo0bits(ULong *y)
         559                 :            : {
         560                 :            :     int k;
         561                 :         58 :     ULong x = *y;
         562                 :            :
         563         [ +  + ]:         58 :     if (x & 7) {
         564         [ +  + ]:         28 :         if (x & 1)
         565                 :         19 :             return 0;
         566         [ +  + ]:          9 :         if (x & 2) {
         567                 :          6 :             *y = x >> 1;
         568                 :          6 :             return 1;
         569                 :            :         }
         570                 :          3 :         *y = x >> 2;
         571                 :          3 :         return 2;
         572                 :            :     }
         573                 :         30 :     k = 0;
         574         [ +  + ]:         30 :     if (!(x & 0xffff)) {
         575                 :         23 :         k = 16;
         576                 :         23 :         x >>= 16;
         577                 :            :     }
         578         [ +  + ]:         30 :     if (!(x & 0xff)) {
         579                 :          2 :         k += 8;
         580                 :          2 :         x >>= 8;
         581                 :            :     }
         582         [ +  + ]:         30 :     if (!(x & 0xf)) {
         583                 :         26 :         k += 4;
         584                 :         26 :         x >>= 4;
         585                 :            :     }
         586         [ +  + ]:         30 :     if (!(x & 0x3)) {
         587                 :          5 :         k += 2;
         588                 :          5 :         x >>= 2;
         589                 :            :     }
         590         [ +  + ]:         30 :     if (!(x & 1)) {
         591                 :          5 :         k++;
         592                 :          5 :         x >>= 1;
         593         [ -  + ]:          5 :         if (!x)
         594                 :          0 :             return 32;
         595                 :            :     }
         596                 :         30 :     *y = x;
         597                 :         30 :     return k;
         598                 :            : }
         599                 :            :
         600                 :            : /* convert a small nonnegative integer to a Bigint */
         601                 :            :
         602                 :            : static Bigint *
         603                 :       4592 : i2b(int i)
         604                 :            : {
         605                 :            :     Bigint *b;
         606                 :            :
         607                 :       4592 :     b = Balloc(1);
         608         [ -  + ]:       4592 :     if (b == NULL)
         609                 :          0 :         return NULL;
         610                 :       4592 :     b->x[0] = i;
         611                 :       4592 :     b->wds = 1;
         612                 :       4592 :     return b;
         613                 :            : }
         614                 :            :
         615                 :            : /* multiply two Bigints.  Returns a new Bigint, or NULL on failure.  Ignores
         616                 :            :    the signs of a and b. */
         617                 :            :
         618                 :            : static Bigint *
         619                 :      12098 : mult(Bigint *a, Bigint *b)
         620                 :            : {
         621                 :            :     Bigint *c;
         622                 :            :     int k, wa, wb, wc;
         623                 :            :     ULong *x, *xa, *xae, *xb, *xbe, *xc, *xc0;
         624                 :            :     ULong y;
         625                 :            :     ULLong carry, z;
         626                 :            :
         627   [ -  +  -  -  :      12098 :     if ((!a->x[0] && a->wds == 1) || (!b->x[0] && b->wds == 1)) {
                 +  +  -  + ]
         628                 :          0 :         c = Balloc(0);
         629         [ #  # ]:          0 :         if (c == NULL)
         630                 :          0 :             return NULL;
         631                 :          0 :         c->wds = 1;
         632                 :          0 :         c->x[0] = 0;
         633                 :          0 :         return c;
         634                 :            :     }
         635                 :            :
         636         [ +  + ]:      12098 :     if (a->wds < b->wds) {
         637                 :       5539 :         c = a;
         638                 :       5539 :         a = b;
         639                 :       5539 :         b = c;
         640                 :            :     }
         641                 :      12098 :     k = a->k;
         642                 :      12098 :     wa = a->wds;
         643                 :      12098 :     wb = b->wds;
         644                 :      12098 :     wc = wa + wb;
         645         [ +  + ]:      12098 :     if (wc > a->maxwds)
         646                 :       4588 :         k++;
         647                 :      12098 :     c = Balloc(k);
         648         [ -  + ]:      12098 :     if (c == NULL)
         649                 :          0 :         return NULL;
         650         [ +  + ]:      94426 :     for(x = c->x, xa = x + wc; x < xa; x++)
         651                 :      82328 :         *x = 0;
         652                 :      12098 :     xa = a->x;
         653                 :      12098 :     xae = xa + wa;
         654                 :      12098 :     xb = b->x;
         655                 :      12098 :     xbe = xb + wb;
         656                 :      12098 :     xc0 = c->x;
         657         [ +  + ]:      33674 :     for(; xb < xbe; xc0++) {
         658         [ +  + ]:      21576 :         if ((y = *xb++)) {
         659                 :      21498 :             x = xa;
         660                 :      21498 :             xc = xc0;
         661                 :      21498 :             carry = 0;
         662                 :            :             do {
         663                 :     169465 :                 z = *x++ * (ULLong)y + *xc + carry;
         664                 :     169465 :                 carry = z >> 32;
         665                 :     169465 :                 *xc++ = (ULong)(z & FFFFFFFF);
         666                 :            :             }
         667         [ +  + ]:     169465 :             while(x < xae);
         668                 :      21498 :             *xc = (ULong)carry;
         669                 :            :         }
         670                 :            :     }
         671   [ +  -  +  + ]:      21484 :     for(xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ;
         672                 :      12098 :     c->wds = wc;
         673                 :      12098 :     return c;
         674                 :            : }
         675                 :            :
         676                 :            : #ifndef Py_USING_MEMORY_DEBUGGER
         677                 :            :
         678                 :            : /* multiply the Bigint b by 5**k.  Returns a pointer to the result, or NULL on
         679                 :            :    failure; if the returned pointer is distinct from b then the original
         680                 :            :    Bigint b will have been Bfree'd.   Ignores the sign of b. */
         681                 :            :
         682                 :            : static Bigint *
         683                 :       4537 : pow5mult(Bigint *b, int k)
         684                 :            : {
         685                 :            :     Bigint *b1, *p5, *p51;
         686                 :            :     int i;
         687                 :            :     static const int p05[3] = { 5, 25, 125 };
         688                 :            :
         689         [ +  + ]:       4537 :     if ((i = k & 3)) {
         690                 :       2482 :         b = multadd(b, p05[i-1], 0);
         691         [ -  + ]:       2482 :         if (b == NULL)
         692                 :          0 :             return NULL;
         693                 :            :     }
         694                 :            :
         695         [ +  + ]:       4537 :     if (!(k >>= 2))
         696                 :         13 :         return b;
         697                 :       4524 :     PyInterpreterState *interp = _PyInterpreterState_GET();
         698                 :       4524 :     p5 = interp->dtoa.p5s;
         699         [ +  + ]:       4524 :     if (!p5) {
         700                 :            :         /* first time */
         701                 :          1 :         p5 = i2b(625);
         702         [ -  + ]:          1 :         if (p5 == NULL) {
         703                 :          0 :             Bfree(b);
         704                 :          0 :             return NULL;
         705                 :            :         }
         706                 :          1 :         interp->dtoa.p5s = p5;
         707                 :          1 :         p5->next = 0;
         708                 :            :     }
         709                 :            :     for(;;) {
         710         [ +  + ]:      17825 :         if (k & 1) {
         711                 :       8007 :             b1 = mult(b, p5);
         712                 :       8007 :             Bfree(b);
         713                 :       8007 :             b = b1;
         714         [ -  + ]:       8007 :             if (b == NULL)
         715                 :          0 :                 return NULL;
         716                 :            :         }
         717         [ +  + ]:      17825 :         if (!(k >>= 1))
         718                 :       4524 :             break;
         719                 :      13301 :         p51 = p5->next;
         720         [ +  + ]:      13301 :         if (!p51) {
         721                 :          6 :             p51 = mult(p5,p5);
         722         [ -  + ]:          6 :             if (p51 == NULL) {
         723                 :          0 :                 Bfree(b);
         724                 :          0 :                 return NULL;
         725                 :            :             }
         726                 :          6 :             p51->next = 0;
         727                 :          6 :             p5->next = p51;
         728                 :            :         }
         729                 :      13301 :         p5 = p51;
         730                 :            :     }
         731                 :       4524 :     return b;
         732                 :            : }
         733                 :            :
         734                 :            : #else
         735                 :            :
         736                 :            : /* Version of pow5mult that doesn't cache powers of 5. Provided for
         737                 :            :    the benefit of memory debugging tools like Valgrind. */
         738                 :            :
         739                 :            : static Bigint *
         740                 :            : pow5mult(Bigint *b, int k)
         741                 :            : {
         742                 :            :     Bigint *b1, *p5, *p51;
         743                 :            :     int i;
         744                 :            :     static const int p05[3] = { 5, 25, 125 };
         745                 :            :
         746                 :            :     if ((i = k & 3)) {
         747                 :            :         b = multadd(b, p05[i-1], 0);
         748                 :            :         if (b == NULL)
         749                 :            :             return NULL;
         750                 :            :     }
         751                 :            :
         752                 :            :     if (!(k >>= 2))
         753                 :            :         return b;
         754                 :            :     p5 = i2b(625);
         755                 :            :     if (p5 == NULL) {
         756                 :            :         Bfree(b);
         757                 :            :         return NULL;
         758                 :            :     }
         759                 :            :
         760                 :            :     for(;;) {
         761                 :            :         if (k & 1) {
         762                 :            :             b1 = mult(b, p5);
         763                 :            :             Bfree(b);
         764                 :            :             b = b1;
         765                 :            :             if (b == NULL) {
         766                 :            :                 Bfree(p5);
         767                 :            :                 return NULL;
         768                 :            :             }
         769                 :            :         }
         770                 :            :         if (!(k >>= 1))
         771                 :            :             break;
         772                 :            :         p51 = mult(p5, p5);
         773                 :            :         Bfree(p5);
         774                 :            :         p5 = p51;
         775                 :            :         if (p5 == NULL) {
         776                 :            :             Bfree(b);
         777                 :            :             return NULL;
         778                 :            :         }
         779                 :            :     }
         780                 :            :     Bfree(p5);
         781                 :            :     return b;
         782                 :            : }
         783                 :            :
         784                 :            : #endif /* Py_USING_MEMORY_DEBUGGER */
         785                 :            :
         786                 :            : /* shift a Bigint b left by k bits.  Return a pointer to the shifted result,
         787                 :            :    or NULL on failure.  If the returned pointer is distinct from b then the
         788                 :            :    original b will have been Bfree'd.   Ignores the sign of b. */
         789                 :            :
         790                 :            : static Bigint *
         791                 :       9191 : lshift(Bigint *b, int k)
         792                 :            : {
         793                 :            :     int i, k1, n, n1;
         794                 :            :     Bigint *b1;
         795                 :            :     ULong *x, *x1, *xe, z;
         796                 :            :
         797   [ +  -  +  +  :       9191 :     if (!k || (!b->x[0] && b->wds == 1))
                       -  + ]
         798                 :          0 :         return b;
         799                 :            :
         800                 :       9191 :     n = k >> 5;
         801                 :       9191 :     k1 = b->k;
         802                 :       9191 :     n1 = n + b->wds + 1;
         803         [ +  + ]:      19519 :     for(i = b->maxwds; n1 > i; i <<= 1)
         804                 :      10328 :         k1++;
         805                 :       9191 :     b1 = Balloc(k1);
         806         [ -  + ]:       9191 :     if (b1 == NULL) {
         807                 :          0 :         Bfree(b);
         808                 :          0 :         return NULL;
         809                 :            :     }
         810                 :       9191 :     x1 = b1->x;
         811         [ +  + ]:      44562 :     for(i = 0; i < n; i++)
         812                 :      35371 :         *x1++ = 0;
         813                 :       9191 :     x = b->x;
         814                 :       9191 :     xe = x + b->wds;
         815         [ +  + ]:       9191 :     if (k &= 0x1f) {
         816                 :       9118 :         k1 = 32 - k;
         817                 :       9118 :         z = 0;
         818                 :            :         do {
         819                 :      39607 :             *x1++ = *x << k | z;
         820                 :      39607 :             z = *x++ >> k1;
         821                 :            :         }
         822         [ +  + ]:      39607 :         while(x < xe);
         823         [ +  + ]:       9118 :         if ((*x1 = z))
         824                 :       1318 :             ++n1;
         825                 :            :     }
         826                 :            :     else do
         827                 :        144 :              *x1++ = *x++;
         828         [ +  + ]:        144 :         while(x < xe);
         829                 :       9191 :     b1->wds = n1 - 1;
         830                 :       9191 :     Bfree(b);
         831                 :       9191 :     return b1;
         832                 :            : }
         833                 :            :
         834                 :            : /* Do a three-way compare of a and b, returning -1 if a < b, 0 if a == b and
         835                 :            :    1 if a > b.  Ignores signs of a and b. */
         836                 :            :
         837                 :            : static int
         838                 :      10003 : cmp(Bigint *a, Bigint *b)
         839                 :            : {
         840                 :            :     ULong *xa, *xa0, *xb, *xb0;
         841                 :            :     int i, j;
         842                 :            :
         843                 :      10003 :     i = a->wds;
         844                 :      10003 :     j = b->wds;
         845                 :            : #ifdef DEBUG
         846                 :            :     if (i > 1 && !a->x[i-1])
         847                 :            :         Bug("cmp called with a->x[a->wds-1] == 0");
         848                 :            :     if (j > 1 && !b->x[j-1])
         849                 :            :         Bug("cmp called with b->x[b->wds-1] == 0");
         850                 :            : #endif
         851         [ +  + ]:      10003 :     if (i -= j)
         852                 :        620 :         return i;
         853                 :       9383 :     xa0 = a->x;
         854                 :       9383 :     xa = xa0 + j;
         855                 :       9383 :     xb0 = b->x;
         856                 :       9383 :     xb = xb0 + j;
         857                 :            :     for(;;) {
         858         [ +  + ]:      14938 :         if (*--xa != *--xb)
         859         [ +  + ]:       9372 :             return *xa < *xb ? -1 : 1;
         860         [ +  + ]:       5566 :         if (xa <= xa0)
         861                 :         11 :             break;
         862                 :            :     }
         863                 :         11 :     return 0;
         864                 :            : }
         865                 :            :
         866                 :            : /* Take the difference of Bigints a and b, returning a new Bigint.  Returns
         867                 :            :    NULL on failure.  The signs of a and b are ignored, but the sign of the
         868                 :            :    result is set appropriately. */
         869                 :            :
         870                 :            : static Bigint *
         871                 :       4632 : diff(Bigint *a, Bigint *b)
         872                 :            : {
         873                 :            :     Bigint *c;
         874                 :            :     int i, wa, wb;
         875                 :            :     ULong *xa, *xae, *xb, *xbe, *xc;
         876                 :            :     ULLong borrow, y;
         877                 :            :
         878                 :       4632 :     i = cmp(a,b);
         879         [ +  + ]:       4632 :     if (!i) {
         880                 :         11 :         c = Balloc(0);
         881         [ -  + ]:         11 :         if (c == NULL)
         882                 :          0 :             return NULL;
         883                 :         11 :         c->wds = 1;
         884                 :         11 :         c->x[0] = 0;
         885                 :         11 :         return c;
         886                 :            :     }
         887         [ +  + ]:       4621 :     if (i < 0) {
         888                 :       3477 :         c = a;
         889                 :       3477 :         a = b;
         890                 :       3477 :         b = c;
         891                 :       3477 :         i = 1;
         892                 :            :     }
         893                 :            :     else
         894                 :       1144 :         i = 0;
         895                 :       4621 :     c = Balloc(a->k);
         896         [ -  + ]:       4621 :     if (c == NULL)
         897                 :          0 :         return NULL;
         898                 :       4621 :     c->sign = i;
         899                 :       4621 :     wa = a->wds;
         900                 :       4621 :     xa = a->x;
         901                 :       4621 :     xae = xa + wa;
         902                 :       4621 :     wb = b->wds;
         903                 :       4621 :     xb = b->x;
         904                 :       4621 :     xbe = xb + wb;
         905                 :       4621 :     xc = c->x;
         906                 :       4621 :     borrow = 0;
         907                 :            :     do {
         908                 :      38672 :         y = (ULLong)*xa++ - *xb++ - borrow;
         909                 :      38672 :         borrow = y >> 32 & (ULong)1;
         910                 :      38672 :         *xc++ = (ULong)(y & FFFFFFFF);
         911                 :            :     }
         912         [ +  + ]:      38672 :     while(xb < xbe);
         913         [ +  + ]:       4721 :     while(xa < xae) {
         914                 :        100 :         y = *xa++ - borrow;
         915                 :        100 :         borrow = y >> 32 & (ULong)1;
         916                 :        100 :         *xc++ = (ULong)(y & FFFFFFFF);
         917                 :            :     }
         918         [ +  + ]:      10345 :     while(!*--xc)
         919                 :       5724 :         wa--;
         920                 :       4621 :     c->wds = wa;
         921                 :       4621 :     return c;
         922                 :            : }
         923                 :            :
         924                 :            : /* Given a positive normal double x, return the difference between x and the
         925                 :            :    next double up.  Doesn't give correct results for subnormals. */
         926                 :            :
         927                 :            : static double
         928                 :       2879 : ulp(U *x)
         929                 :            : {
         930                 :            :     Long L;
         931                 :            :     U u;
         932                 :            :
         933                 :       2879 :     L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1;
         934                 :       2879 :     word0(&u) = L;
         935                 :       2879 :     word1(&u) = 0;
         936                 :       2879 :     return dval(&u);
         937                 :            : }
         938                 :            :
         939                 :            : /* Convert a Bigint to a double plus an exponent */
         940                 :            :
         941                 :            : static double
         942                 :       5750 : b2d(Bigint *a, int *e)
         943                 :            : {
         944                 :            :     ULong *xa, *xa0, w, y, z;
         945                 :            :     int k;
         946                 :            :     U d;
         947                 :            :
         948                 :       5750 :     xa0 = a->x;
         949                 :       5750 :     xa = xa0 + a->wds;
         950                 :       5750 :     y = *--xa;
         951                 :            : #ifdef DEBUG
         952                 :            :     if (!y) Bug("zero y in b2d");
         953                 :            : #endif
         954                 :       5750 :     k = hi0bits(y);
         955                 :       5750 :     *e = 32 - k;
         956         [ +  + ]:       5750 :     if (k < Ebits) {
         957                 :        527 :         word0(&d) = Exp_1 | y >> (Ebits - k);
         958         [ +  + ]:        527 :         w = xa > xa0 ? *--xa : 0;
         959                 :        527 :         word1(&d) = y << ((32-Ebits) + k) | w >> (Ebits - k);
         960                 :        527 :         goto ret_d;
         961                 :            :     }
         962         [ +  + ]:       5223 :     z = xa > xa0 ? *--xa : 0;
         963         [ +  + ]:       5223 :     if (k -= Ebits) {
         964                 :       5170 :         word0(&d) = Exp_1 | y << k | z >> (32 - k);
         965         [ +  + ]:       5170 :         y = xa > xa0 ? *--xa : 0;
         966                 :       5170 :         word1(&d) = z << k | y >> (32 - k);
         967                 :            :     }
         968                 :            :     else {
         969                 :         53 :         word0(&d) = Exp_1 | y;
         970                 :         53 :         word1(&d) = z;
         971                 :            :     }
         972                 :       5750 :   ret_d:
         973                 :       5750 :     return dval(&d);
         974                 :            : }
         975                 :            :
         976                 :            : /* Convert a scaled double to a Bigint plus an exponent.  Similar to d2b,
         977                 :            :    except that it accepts the scale parameter used in _Py_dg_strtod (which
         978                 :            :    should be either 0 or 2*P), and the normalization for the return value is
         979                 :            :    different (see below).  On input, d should be finite and nonnegative, and d
         980                 :            :    / 2**scale should be exactly representable as an IEEE 754 double.
         981                 :            :
         982                 :            :    Returns a Bigint b and an integer e such that
         983                 :            :
         984                 :            :      dval(d) / 2**scale = b * 2**e.
         985                 :            :
         986                 :            :    Unlike d2b, b is not necessarily odd: b and e are normalized so
         987                 :            :    that either 2**(P-1) <= b < 2**P and e >= Etiny, or b < 2**P
         988                 :            :    and e == Etiny.  This applies equally to an input of 0.0: in that
         989                 :            :    case the return values are b = 0 and e = Etiny.
         990                 :            :
         991                 :            :    The above normalization ensures that for all possible inputs d,
         992                 :            :    2**e gives ulp(d/2**scale).
         993                 :            :
         994                 :            :    Returns NULL on failure.
         995                 :            : */
         996                 :            :
         997                 :            : static Bigint *
         998                 :       4525 : sd2b(U *d, int scale, int *e)
         999                 :            : {
        1000                 :            :     Bigint *b;
        1001                 :            :
        1002                 :       4525 :     b = Balloc(1);
        1003         [ -  + ]:       4525 :     if (b == NULL)
        1004                 :          0 :         return NULL;
        1005                 :            :
        1006                 :            :     /* First construct b and e assuming that scale == 0. */
        1007                 :       4525 :     b->wds = 2;
        1008                 :       4525 :     b->x[0] = word1(d);
        1009                 :       4525 :     b->x[1] = word0(d) & Frac_mask;
        1010                 :       4525 :     *e = Etiny - 1 + (int)((word0(d) & Exp_mask) >> Exp_shift);
        1011         [ -  + ]:       4525 :     if (*e < Etiny)
        1012                 :          0 :         *e = Etiny;
        1013                 :            :     else
        1014                 :       4525 :         b->x[1] |= Exp_msk1;
        1015                 :            :
        1016                 :            :     /* Now adjust for scale, provided that b != 0. */
        1017   [ +  +  +  +  :       4525 :     if (scale && (b->x[0] || b->x[1])) {
                       +  - ]
        1018                 :        704 :         *e -= scale;
        1019         [ +  + ]:        704 :         if (*e < Etiny) {
        1020                 :        519 :             scale = Etiny - *e;
        1021                 :        519 :             *e = Etiny;
        1022                 :            :             /* We can't shift more than P-1 bits without shifting out a 1. */
        1023                 :            :             assert(0 < scale && scale <= P - 1);
        1024         [ +  + ]:        519 :             if (scale >= 32) {
        1025                 :            :                 /* The bits shifted out should all be zero. */
        1026                 :            :                 assert(b->x[0] == 0);
        1027                 :        267 :                 b->x[0] = b->x[1];
        1028                 :        267 :                 b->x[1] = 0;
        1029                 :        267 :                 scale -= 32;
        1030                 :            :             }
        1031         [ +  + ]:        519 :             if (scale) {
        1032                 :            :                 /* The bits shifted out should all be zero. */
        1033                 :            :                 assert(b->x[0] << (32 - scale) == 0);
        1034                 :        511 :                 b->x[0] = (b->x[0] >> scale) | (b->x[1] << (32 - scale));
        1035                 :        511 :                 b->x[1] >>= scale;
        1036                 :            :             }
        1037                 :            :         }
        1038                 :            :     }
        1039                 :            :     /* Ensure b is normalized. */
        1040         [ +  + ]:       4525 :     if (!b->x[1])
        1041                 :        325 :         b->wds = 1;
        1042                 :            :
        1043                 :       4525 :     return b;
        1044                 :            : }
        1045                 :            :
        1046                 :            : /* Convert a double to a Bigint plus an exponent.  Return NULL on failure.
        1047                 :            :
        1048                 :            :    Given a finite nonzero double d, return an odd Bigint b and exponent *e
        1049                 :            :    such that fabs(d) = b * 2**e.  On return, *bbits gives the number of
        1050                 :            :    significant bits of b; that is, 2**(*bbits-1) <= b < 2**(*bbits).
        1051                 :            :
        1052                 :            :    If d is zero, then b == 0, *e == -1010, *bbits = 0.
        1053                 :            :  */
        1054                 :            :
        1055                 :            : static Bigint *
        1056                 :         58 : d2b(U *d, int *e, int *bits)
        1057                 :            : {
        1058                 :            :     Bigint *b;
        1059                 :            :     int de, k;
        1060                 :            :     ULong *x, y, z;
        1061                 :            :     int i;
        1062                 :            :
        1063                 :         58 :     b = Balloc(1);
        1064         [ -  + ]:         58 :     if (b == NULL)
        1065                 :          0 :         return NULL;
        1066                 :         58 :     x = b->x;
        1067                 :            :
        1068                 :         58 :     z = word0(d) & Frac_mask;
        1069                 :         58 :     word0(d) &= 0x7fffffff;   /* clear sign bit, which we ignore */
        1070         [ +  - ]:         58 :     if ((de = (int)(word0(d) >> Exp_shift)))
        1071                 :         58 :         z |= Exp_msk1;
        1072         [ +  + ]:         58 :     if ((y = word1(d))) {
        1073         [ +  + ]:         34 :         if ((k = lo0bits(&y))) {
        1074                 :         15 :             x[0] = y | z << (32 - k);
        1075                 :         15 :             z >>= k;
        1076                 :            :         }
        1077                 :            :         else
        1078                 :         19 :             x[0] = y;
        1079                 :         34 :         i =
        1080         [ +  + ]:         34 :             b->wds = (x[1] = z) ? 2 : 1;
        1081                 :            :     }
        1082                 :            :     else {
        1083                 :         24 :         k = lo0bits(&z);
        1084                 :         24 :         x[0] = z;
        1085                 :         24 :         i =
        1086                 :         24 :             b->wds = 1;
        1087                 :         24 :         k += 32;
        1088                 :            :     }
        1089         [ +  - ]:         58 :     if (de) {
        1090                 :         58 :         *e = de - Bias - (P-1) + k;
        1091                 :         58 :         *bits = P - k;
        1092                 :            :     }
        1093                 :            :     else {
        1094                 :          0 :         *e = de - Bias - (P-1) + 1 + k;
        1095                 :          0 :         *bits = 32*i - hi0bits(x[i-1]);
        1096                 :            :     }
        1097                 :         58 :     return b;
        1098                 :            : }
        1099                 :            :
        1100                 :            : /* Compute the ratio of two Bigints, as a double.  The result may have an
        1101                 :            :    error of up to 2.5 ulps. */
        1102                 :            :
        1103                 :            : static double
        1104                 :       2875 : ratio(Bigint *a, Bigint *b)
        1105                 :            : {
        1106                 :            :     U da, db;
        1107                 :            :     int k, ka, kb;
        1108                 :            :
        1109                 :       2875 :     dval(&da) = b2d(a, &ka);
        1110                 :       2875 :     dval(&db) = b2d(b, &kb);
        1111                 :       2875 :     k = ka - kb + 32*(a->wds - b->wds);
        1112         [ +  + ]:       2875 :     if (k > 0)
        1113                 :       2745 :         word0(&da) += k*Exp_msk1;
        1114                 :            :     else {
        1115                 :        130 :         k = -k;
        1116                 :        130 :         word0(&db) += k*Exp_msk1;
        1117                 :            :     }
        1118                 :       2875 :     return dval(&da) / dval(&db);
        1119                 :            : }
        1120                 :            :
        1121                 :            : static const double
        1122                 :            : tens[] = {
        1123                 :            :     1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
        1124                 :            :     1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
        1125                 :            :     1e20, 1e21, 1e22
        1126                 :            : };
        1127                 :            :
        1128                 :            : static const double
        1129                 :            : bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 };
        1130                 :            : static const double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128,
        1131                 :            :                                    9007199254740992.*9007199254740992.e-256
        1132                 :            :                                    /* = 2^106 * 1e-256 */
        1133                 :            : };
        1134                 :            : /* The factor of 2^53 in tinytens[4] helps us avoid setting the underflow */
        1135                 :            : /* flag unnecessarily.  It leads to a song and dance at the end of strtod. */
        1136                 :            : #define Scale_Bit 0x10
        1137                 :            : #define n_bigtens 5
        1138                 :            :
        1139                 :            : #define ULbits 32
        1140                 :            : #define kshift 5
        1141                 :            : #define kmask 31
        1142                 :            :
        1143                 :            :
        1144                 :            : static int
        1145                 :         59 : dshift(Bigint *b, int p2)
        1146                 :            : {
        1147                 :         59 :     int rv = hi0bits(b->x[b->wds-1]) - 4;
        1148         [ +  + ]:         59 :     if (p2 > 0)
        1149                 :         53 :         rv -= p2;
        1150                 :         59 :     return rv & kmask;
        1151                 :            : }
        1152                 :            :
        1153                 :            : /* special case of Bigint division.  The quotient is always in the range 0 <=
        1154                 :            :    quotient < 10, and on entry the divisor S is normalized so that its top 4
        1155                 :            :    bits (28--31) are zero and bit 27 is set. */
        1156                 :            :
        1157                 :            : static int
        1158                 :        545 : quorem(Bigint *b, Bigint *S)
        1159                 :            : {
        1160                 :            :     int n;
        1161                 :            :     ULong *bx, *bxe, q, *sx, *sxe;
        1162                 :            :     ULLong borrow, carry, y, ys;
        1163                 :            :
        1164                 :        545 :     n = S->wds;
        1165                 :            : #ifdef DEBUG
        1166                 :            :     /*debug*/ if (b->wds > n)
        1167                 :            :         /*debug*/       Bug("oversize b in quorem");
        1168                 :            : #endif
        1169         [ +  + ]:        545 :     if (b->wds < n)
        1170                 :          6 :         return 0;
        1171                 :        539 :     sx = S->x;
        1172                 :        539 :     sxe = sx + --n;
        1173                 :        539 :     bx = b->x;
        1174                 :        539 :     bxe = bx + n;
        1175                 :        539 :     q = *bxe / (*sxe + 1);      /* ensure q <= true quotient */
        1176                 :            : #ifdef DEBUG
        1177                 :            :     /*debug*/ if (q > 9)
        1178                 :            :         /*debug*/       Bug("oversized quotient in quorem");
        1179                 :            : #endif
        1180         [ +  + ]:        539 :     if (q) {
        1181                 :        459 :         borrow = 0;
        1182                 :        459 :         carry = 0;
        1183                 :            :         do {
        1184                 :       1306 :             ys = *sx++ * (ULLong)q + carry;
        1185                 :       1306 :             carry = ys >> 32;
        1186                 :       1306 :             y = *bx - (ys & FFFFFFFF) - borrow;
        1187                 :       1306 :             borrow = y >> 32 & (ULong)1;
        1188                 :       1306 :             *bx++ = (ULong)(y & FFFFFFFF);
        1189                 :            :         }
        1190         [ +  + ]:       1306 :         while(sx <= sxe);
        1191         [ -  + ]:        459 :         if (!*bxe) {
        1192                 :          0 :             bx = b->x;
        1193   [ #  #  #  # ]:          0 :             while(--bxe > bx && !*bxe)
        1194                 :          0 :                 --n;
        1195                 :          0 :             b->wds = n;
        1196                 :            :         }
        1197                 :            :     }
        1198         [ +  + ]:        539 :     if (cmp(b, S) >= 0) {
        1199                 :         21 :         q++;
        1200                 :         21 :         borrow = 0;
        1201                 :         21 :         carry = 0;
        1202                 :         21 :         bx = b->x;
        1203                 :         21 :         sx = S->x;
        1204                 :            :         do {
        1205                 :        200 :             ys = *sx++ + carry;
        1206                 :        200 :             carry = ys >> 32;
        1207                 :        200 :             y = *bx - (ys & FFFFFFFF) - borrow;
        1208                 :        200 :             borrow = y >> 32 & (ULong)1;
        1209                 :        200 :             *bx++ = (ULong)(y & FFFFFFFF);
        1210                 :            :         }
        1211         [ +  + ]:        200 :         while(sx <= sxe);
        1212                 :         21 :         bx = b->x;
        1213                 :         21 :         bxe = bx + n;
        1214         [ +  + ]:         21 :         if (!*bxe) {
        1215   [ +  +  -  + ]:         17 :             while(--bxe > bx && !*bxe)
        1216                 :          0 :                 --n;
        1217                 :         17 :             b->wds = n;
        1218                 :            :         }
        1219                 :            :     }
        1220                 :        539 :     return q;
        1221                 :            : }
        1222                 :            :
        1223                 :            : /* sulp(x) is a version of ulp(x) that takes bc.scale into account.
        1224                 :            :
        1225                 :            :    Assuming that x is finite and nonnegative (positive zero is fine
        1226                 :            :    here) and x / 2^bc.scale is exactly representable as a double,
        1227                 :            :    sulp(x) is equivalent to 2^bc.scale * ulp(x / 2^bc.scale). */
        1228                 :            :
        1229                 :            : static double
        1230                 :          4 : sulp(U *x, BCinfo *bc)
        1231                 :            : {
        1232                 :            :     U u;
        1233                 :            :
        1234   [ -  +  -  - ]:          4 :     if (bc->scale && 2*P + 1 > (int)((word0(x) & Exp_mask) >> Exp_shift)) {
        1235                 :            :         /* rv/2^bc->scale is subnormal */
        1236                 :          0 :         word0(&u) = (P+2)*Exp_msk1;
        1237                 :          0 :         word1(&u) = 0;
        1238                 :          0 :         return u.d;
        1239                 :            :     }
        1240                 :            :     else {
        1241                 :            :         assert(word0(x) || word1(x)); /* x != 0.0 */
        1242                 :          4 :         return ulp(x);
        1243                 :            :     }
        1244                 :            : }
        1245                 :            :
        1246                 :            : /* The bigcomp function handles some hard cases for strtod, for inputs
        1247                 :            :    with more than STRTOD_DIGLIM digits.  It's called once an initial
        1248                 :            :    estimate for the double corresponding to the input string has
        1249                 :            :    already been obtained by the code in _Py_dg_strtod.
        1250                 :            :
        1251                 :            :    The bigcomp function is only called after _Py_dg_strtod has found a
        1252                 :            :    double value rv such that either rv or rv + 1ulp represents the
        1253                 :            :    correctly rounded value corresponding to the original string.  It
        1254                 :            :    determines which of these two values is the correct one by
        1255                 :            :    computing the decimal digits of rv + 0.5ulp and comparing them with
        1256                 :            :    the corresponding digits of s0.
        1257                 :            :
        1258                 :            :    In the following, write dv for the absolute value of the number represented
        1259                 :            :    by the input string.
        1260                 :            :
        1261                 :            :    Inputs:
        1262                 :            :
        1263                 :            :      s0 points to the first significant digit of the input string.
        1264                 :            :
        1265                 :            :      rv is a (possibly scaled) estimate for the closest double value to the
        1266                 :            :         value represented by the original input to _Py_dg_strtod.  If
        1267                 :            :         bc->scale is nonzero, then rv/2^(bc->scale) is the approximation to
        1268                 :            :         the input value.
        1269                 :            :
        1270                 :            :      bc is a struct containing information gathered during the parsing and
        1271                 :            :         estimation steps of _Py_dg_strtod.  Description of fields follows:
        1272                 :            :
        1273                 :            :         bc->e0 gives the exponent of the input value, such that dv = (integer
        1274                 :            :            given by the bd->nd digits of s0) * 10**e0
        1275                 :            :
        1276                 :            :         bc->nd gives the total number of significant digits of s0.  It will
        1277                 :            :            be at least 1.
        1278                 :            :
        1279                 :            :         bc->nd0 gives the number of significant digits of s0 before the
        1280                 :            :            decimal separator.  If there's no decimal separator, bc->nd0 ==
        1281                 :            :            bc->nd.
        1282                 :            :
        1283                 :            :         bc->scale is the value used to scale rv to avoid doing arithmetic with
        1284                 :            :            subnormal values.  It's either 0 or 2*P (=106).
        1285                 :            :
        1286                 :            :    Outputs:
        1287                 :            :
        1288                 :            :      On successful exit, rv/2^(bc->scale) is the closest double to dv.
        1289                 :            :
        1290                 :            :      Returns 0 on success, -1 on failure (e.g., due to a failed malloc call). */
        1291                 :            :
        1292                 :            : static int
        1293                 :         23 : bigcomp(U *rv, const char *s0, BCinfo *bc)
        1294                 :            : {
        1295                 :            :     Bigint *b, *d;
        1296                 :            :     int b2, d2, dd, i, nd, nd0, odd, p2, p5;
        1297                 :            :
        1298                 :         23 :     nd = bc->nd;
        1299                 :         23 :     nd0 = bc->nd0;
        1300                 :         23 :     p5 = nd + bc->e0;
        1301                 :         23 :     b = sd2b(rv, bc->scale, &p2);
        1302         [ -  + ]:         23 :     if (b == NULL)
        1303                 :          0 :         return -1;
        1304                 :            :
        1305                 :            :     /* record whether the lsb of rv/2^(bc->scale) is odd:  in the exact halfway
        1306                 :            :        case, this is used for round to even. */
        1307                 :         23 :     odd = b->x[0] & 1;
        1308                 :            :
        1309                 :            :     /* left shift b by 1 bit and or a 1 into the least significant bit;
        1310                 :            :        this gives us b * 2**p2 = rv/2^(bc->scale) + 0.5 ulp. */
        1311                 :         23 :     b = lshift(b, 1);
        1312         [ -  + ]:         23 :     if (b == NULL)
        1313                 :          0 :         return -1;
        1314                 :         23 :     b->x[0] |= 1;
        1315                 :         23 :     p2--;
        1316                 :            :
        1317                 :         23 :     p2 -= p5;
        1318                 :         23 :     d = i2b(1);
        1319         [ -  + ]:         23 :     if (d == NULL) {
        1320                 :          0 :         Bfree(b);
        1321                 :          0 :         return -1;
        1322                 :            :     }
        1323                 :            :     /* Arrange for convenient computation of quotients:
        1324                 :            :      * shift left if necessary so divisor has 4 leading 0 bits.
        1325                 :            :      */
        1326         [ +  - ]:         23 :     if (p5 > 0) {
        1327                 :         23 :         d = pow5mult(d, p5);
        1328         [ -  + ]:         23 :         if (d == NULL) {
        1329                 :          0 :             Bfree(b);
        1330                 :          0 :             return -1;
        1331                 :            :         }
        1332                 :            :     }
        1333         [ #  # ]:          0 :     else if (p5 < 0) {
        1334                 :          0 :         b = pow5mult(b, -p5);
        1335         [ #  # ]:          0 :         if (b == NULL) {
        1336                 :          0 :             Bfree(d);
        1337                 :          0 :             return -1;
        1338                 :            :         }
        1339                 :            :     }
        1340         [ -  + ]:         23 :     if (p2 > 0) {
        1341                 :          0 :         b2 = p2;
        1342                 :          0 :         d2 = 0;
        1343                 :            :     }
        1344                 :            :     else {
        1345                 :         23 :         b2 = 0;
        1346                 :         23 :         d2 = -p2;
        1347                 :            :     }
        1348                 :         23 :     i = dshift(d, d2);
        1349         [ +  - ]:         23 :     if ((b2 += i) > 0) {
        1350                 :         23 :         b = lshift(b, b2);
        1351         [ -  + ]:         23 :         if (b == NULL) {
        1352                 :          0 :             Bfree(d);
        1353                 :          0 :             return -1;
        1354                 :            :         }
        1355                 :            :     }
        1356         [ +  - ]:         23 :     if ((d2 += i) > 0) {
        1357                 :         23 :         d = lshift(d, d2);
        1358         [ -  + ]:         23 :         if (d == NULL) {
        1359                 :          0 :             Bfree(b);
        1360                 :          0 :             return -1;
        1361                 :            :         }
        1362                 :            :     }
        1363                 :            :
        1364                 :            :     /* Compare s0 with b/d: set dd to -1, 0, or 1 according as s0 < b/d, s0 ==
        1365                 :            :      * b/d, or s0 > b/d.  Here the digits of s0 are thought of as representing
        1366                 :            :      * a number in the range [0.1, 1). */
        1367         [ -  + ]:         23 :     if (cmp(b, d) >= 0)
        1368                 :            :         /* b/d >= 1 */
        1369                 :          0 :         dd = -1;
        1370                 :            :     else {
        1371                 :         23 :         i = 0;
        1372                 :            :         for(;;) {
        1373                 :        415 :             b = multadd(b, 10, 0);
        1374         [ -  + ]:        415 :             if (b == NULL) {
        1375                 :          0 :                 Bfree(d);
        1376                 :          0 :                 return -1;
        1377                 :            :             }
        1378         [ +  + ]:        415 :             dd = s0[i < nd0 ? i : i+1] - '0' - quorem(b, d);
        1379                 :        415 :             i++;
        1380                 :            :
        1381         [ +  + ]:        415 :             if (dd)
        1382                 :         23 :                 break;
        1383   [ -  +  -  - ]:        392 :             if (!b->x[0] && b->wds == 1) {
        1384                 :            :                 /* b/d == 0 */
        1385                 :          0 :                 dd = i < nd;
        1386                 :          0 :                 break;
        1387                 :            :             }
        1388         [ -  + ]:        392 :             if (!(i < nd)) {
        1389                 :            :                 /* b/d != 0, but digits of s0 exhausted */
        1390                 :          0 :                 dd = -1;
        1391                 :          0 :                 break;
        1392                 :            :             }
        1393                 :            :         }
        1394                 :            :     }
        1395                 :         23 :     Bfree(b);
        1396                 :         23 :     Bfree(d);
        1397   [ +  +  -  +  :         23 :     if (dd > 0 || (dd == 0 && odd))
                       -  - ]
        1398                 :          4 :         dval(rv) += sulp(rv, bc);
        1399                 :         23 :     return 0;
        1400                 :            : }
        1401                 :            :
        1402                 :            : /* Return a 'standard' NaN value.
        1403                 :            :
        1404                 :            :    There are exactly two quiet NaNs that don't arise by 'quieting' signaling
        1405                 :            :    NaNs (see IEEE 754-2008, section 6.2.1).  If sign == 0, return the one whose
        1406                 :            :    sign bit is cleared.  Otherwise, return the one whose sign bit is set.
        1407                 :            : */
        1408                 :            :
        1409                 :            : double
        1410                 :        812 : _Py_dg_stdnan(int sign)
        1411                 :            : {
        1412                 :            :     U rv;
        1413                 :        812 :     word0(&rv) = NAN_WORD0;
        1414                 :        812 :     word1(&rv) = NAN_WORD1;
        1415         [ +  + ]:        812 :     if (sign)
        1416                 :          1 :         word0(&rv) |= Sign_bit;
        1417                 :        812 :     return dval(&rv);
        1418                 :            : }
        1419                 :            :
        1420                 :            : /* Return positive or negative infinity, according to the given sign (0 for
        1421                 :            :  * positive infinity, 1 for negative infinity). */
        1422                 :            :
        1423                 :            : double
        1424                 :       1234 : _Py_dg_infinity(int sign)
        1425                 :            : {
        1426                 :            :     U rv;
        1427                 :       1234 :     word0(&rv) = POSINF_WORD0;
        1428                 :       1234 :     word1(&rv) = POSINF_WORD1;
        1429         [ +  + ]:       1234 :     return sign ? -dval(&rv) : dval(&rv);
        1430                 :            : }
        1431                 :            :
        1432                 :            : double
        1433                 :      11475 : _Py_dg_strtod(const char *s00, char **se)
        1434                 :            : {
        1435                 :            :     int bb2, bb5, bbe, bd2, bd5, bs2, c, dsign, e, e1, error;
        1436                 :            :     int esign, i, j, k, lz, nd, nd0, odd, sign;
        1437                 :            :     const char *s, *s0, *s1;
        1438                 :            :     double aadj, aadj1;
        1439                 :            :     U aadj2, adj, rv, rv0;
        1440                 :            :     ULong y, z, abs_exp;
        1441                 :            :     Long L;
        1442                 :            :     BCinfo bc;
        1443                 :      11475 :     Bigint *bb = NULL, *bd = NULL, *bd0 = NULL, *bs = NULL, *delta = NULL;
        1444                 :            :     size_t ndigits, fraclen;
        1445                 :            :     double result;
        1446                 :            :
        1447                 :      11475 :     dval(&rv) = 0.;
        1448                 :            :
        1449                 :            :     /* Start parsing. */
        1450                 :      11475 :     c = *(s = s00);
        1451                 :            :
        1452                 :            :     /* Parse optional sign, if present. */
        1453                 :      11475 :     sign = 0;
        1454      [ +  -  + ]:      11475 :     switch (c) {
        1455                 :       3659 :     case '-':
        1456                 :       3659 :         sign = 1;
        1457                 :            :         /* fall through */
        1458                 :       3659 :     case '+':
        1459                 :       3659 :         c = *++s;
        1460                 :            :     }
        1461                 :            :
        1462                 :            :     /* Skip leading zeros: lz is true iff there were leading zeros. */
        1463                 :      11475 :     s1 = s;
        1464         [ +  + ]:      15555 :     while (c == '0')
        1465                 :       4080 :         c = *++s;
        1466                 :      11475 :     lz = s != s1;
        1467                 :            :
        1468                 :            :     /* Point s0 at the first nonzero digit (if any).  fraclen will be the
        1469                 :            :        number of digits between the decimal point and the end of the
        1470                 :            :        digit string.  ndigits will be the total number of digits ignoring
        1471                 :            :        leading zeros. */
        1472                 :      11475 :     s0 = s1 = s;
        1473   [ +  +  +  + ]:      19815 :     while ('0' <= c && c <= '9')
        1474                 :       8340 :         c = *++s;
        1475                 :      11475 :     ndigits = s - s1;
        1476                 :      11475 :     fraclen = 0;
        1477                 :            :
        1478                 :            :     /* Parse decimal point and following digits. */
        1479         [ +  + ]:      11475 :     if (c == '.') {
        1480                 :       8991 :         c = *++s;
        1481         [ +  + ]:       8991 :         if (!ndigits) {
        1482                 :       4078 :             s1 = s;
        1483         [ +  + ]:       7161 :             while (c == '0')
        1484                 :       3083 :                 c = *++s;
        1485   [ +  +  +  + ]:       4078 :             lz = lz || s != s1;
        1486                 :       4078 :             fraclen += (s - s1);
        1487                 :       4078 :             s0 = s;
        1488                 :            :         }
        1489                 :       8991 :         s1 = s;
        1490   [ +  +  +  + ]:      87983 :         while ('0' <= c && c <= '9')
        1491                 :      78992 :             c = *++s;
        1492                 :       8991 :         ndigits += s - s1;
        1493                 :       8991 :         fraclen += s - s1;
        1494                 :            :     }
        1495                 :            :
        1496                 :            :     /* Now lz is true if and only if there were leading zero digits, and
        1497                 :            :        ndigits gives the total number of digits ignoring leading zeros.  A
        1498                 :            :        valid input must have at least one digit. */
        1499   [ +  +  +  + ]:      11475 :     if (!ndigits && !lz) {
        1500         [ +  - ]:       2019 :         if (se)
        1501                 :       2019 :             *se = (char *)s00;
        1502                 :       2019 :         goto parse_error;
        1503                 :            :     }
        1504                 :            :
        1505                 :            :     /* Range check ndigits and fraclen to make sure that they, and values
        1506                 :            :        computed with them, can safely fit in an int. */
        1507   [ +  -  -  + ]:       9456 :     if (ndigits > MAX_DIGITS || fraclen > MAX_DIGITS) {
        1508         [ #  # ]:          0 :         if (se)
        1509                 :          0 :             *se = (char *)s00;
        1510                 :          0 :         goto parse_error;
        1511                 :            :     }
        1512                 :       9456 :     nd = (int)ndigits;
        1513                 :       9456 :     nd0 = (int)ndigits - (int)fraclen;
        1514                 :            :
        1515                 :            :     /* Parse exponent. */
        1516                 :       9456 :     e = 0;
        1517   [ +  +  +  + ]:       9456 :     if (c == 'e' || c == 'E') {
        1518                 :       1399 :         s00 = s;
        1519                 :       1399 :         c = *++s;
        1520                 :            :
        1521                 :            :         /* Exponent sign. */
        1522                 :       1399 :         esign = 0;
        1523      [ +  +  + ]:       1399 :         switch (c) {
        1524                 :        926 :         case '-':
        1525                 :        926 :             esign = 1;
        1526                 :            :             /* fall through */
        1527                 :       1296 :         case '+':
        1528                 :       1296 :             c = *++s;
        1529                 :            :         }
        1530                 :            :
        1531                 :            :         /* Skip zeros.  lz is true iff there are leading zeros. */
        1532                 :       1399 :         s1 = s;
        1533         [ +  + ]:       1470 :         while (c == '0')
        1534                 :         71 :             c = *++s;
        1535                 :       1399 :         lz = s != s1;
        1536                 :            :
        1537                 :            :         /* Get absolute value of the exponent. */
        1538                 :       1399 :         s1 = s;
        1539                 :       1399 :         abs_exp = 0;
        1540   [ +  +  +  - ]:       4987 :         while ('0' <= c && c <= '9') {
        1541                 :       3588 :             abs_exp = 10*abs_exp + (c - '0');
        1542                 :       3588 :             c = *++s;
        1543                 :            :         }
        1544                 :            :
        1545                 :            :         /* abs_exp will be correct modulo 2**32.  But 10**9 < 2**32, so if
        1546                 :            :            there are at most 9 significant exponent digits then overflow is
        1547                 :            :            impossible. */
        1548   [ +  -  -  + ]:       1399 :         if (s - s1 > 9 || abs_exp > MAX_ABS_EXP)
        1549                 :          0 :             e = (int)MAX_ABS_EXP;
        1550                 :            :         else
        1551                 :       1399 :             e = (int)abs_exp;
        1552         [ +  + ]:       1399 :         if (esign)
        1553                 :        926 :             e = -e;
        1554                 :            :
        1555                 :            :         /* A valid exponent must have at least one digit. */
        1556   [ -  +  -  - ]:       1399 :         if (s == s1 && !lz)
        1557                 :          0 :             s = s00;
        1558                 :            :     }
        1559                 :            :
        1560                 :            :     /* Adjust exponent to take into account position of the point. */
        1561                 :       9456 :     e -= nd - nd0;
        1562         [ +  + ]:       9456 :     if (nd0 <= 0)
        1563                 :       4084 :         nd0 = nd;
        1564                 :            :
        1565                 :            :     /* Finished parsing.  Set se to indicate how far we parsed */
        1566         [ +  + ]:       9456 :     if (se)
        1567                 :       9450 :         *se = (char *)s;
        1568                 :            :
        1569                 :            :     /* If all digits were zero, exit with return value +-0.0.  Otherwise,
        1570                 :            :        strip trailing zeros: scan back until we hit a nonzero digit. */
        1571         [ +  + ]:       9456 :     if (!nd)
        1572                 :       2784 :         goto ret;
        1573         [ +  - ]:       8699 :     for (i = nd; i > 0; ) {
        1574                 :       8699 :         --i;
        1575   [ +  +  +  + ]:       8699 :         if (s0[i < nd0 ? i : i+1] != '0') {
        1576                 :       6672 :             ++i;
        1577                 :       6672 :             break;
        1578                 :            :         }
        1579                 :            :     }
        1580                 :       6672 :     e += nd - i;
        1581                 :       6672 :     nd = i;
        1582         [ +  + ]:       6672 :     if (nd0 > nd)
        1583                 :        165 :         nd0 = nd;
        1584                 :            :
        1585                 :            :     /* Summary of parsing results.  After parsing, and dealing with zero
        1586                 :            :      * inputs, we have values s0, nd0, nd, e, sign, where:
        1587                 :            :      *
        1588                 :            :      *  - s0 points to the first significant digit of the input string
        1589                 :            :      *
        1590                 :            :      *  - nd is the total number of significant digits (here, and
        1591                 :            :      *    below, 'significant digits' means the set of digits of the
        1592                 :            :      *    significand of the input that remain after ignoring leading
        1593                 :            :      *    and trailing zeros).
        1594                 :            :      *
        1595                 :            :      *  - nd0 indicates the position of the decimal point, if present; it
        1596                 :            :      *    satisfies 1 <= nd0 <= nd.  The nd significant digits are in
        1597                 :            :      *    s0[0:nd0] and s0[nd0+1:nd+1] using the usual Python half-open slice
        1598                 :            :      *    notation.  (If nd0 < nd, then s0[nd0] contains a '.'  character; if
        1599                 :            :      *    nd0 == nd, then s0[nd0] could be any non-digit character.)
        1600                 :            :      *
        1601                 :            :      *  - e is the adjusted exponent: the absolute value of the number
        1602                 :            :      *    represented by the original input string is n * 10**e, where
        1603                 :            :      *    n is the integer represented by the concatenation of
        1604                 :            :      *    s0[0:nd0] and s0[nd0+1:nd+1]
        1605                 :            :      *
        1606                 :            :      *  - sign gives the sign of the input:  1 for negative, 0 for positive
        1607                 :            :      *
        1608                 :            :      *  - the first and last significant digits are nonzero
        1609                 :            :      */
        1610                 :            :
        1611                 :            :     /* put first DBL_DIG+1 digits into integer y and z.
        1612                 :            :      *
        1613                 :            :      *  - y contains the value represented by the first min(9, nd)
        1614                 :            :      *    significant digits
        1615                 :            :      *
        1616                 :            :      *  - if nd > 9, z contains the value represented by significant digits
        1617                 :            :      *    with indices in [9, min(16, nd)).  So y * 10**(min(16, nd) - 9) + z
        1618                 :            :      *    gives the value represented by the first min(16, nd) sig. digits.
        1619                 :            :      */
        1620                 :            :
        1621                 :       6672 :     bc.e0 = e1 = e;
        1622                 :       6672 :     y = z = 0;
        1623         [ +  + ]:      73535 :     for (i = 0; i < nd; i++) {
        1624         [ +  + ]:      70465 :         if (i < 9)
        1625         [ +  + ]:      39477 :             y = 10*y + s0[i < nd0 ? i : i+1] - '0';
        1626         [ +  + ]:      30988 :         else if (i < DBL_DIG+1)
        1627         [ +  + ]:      27386 :             z = 10*z + s0[i < nd0 ? i : i+1] - '0';
        1628                 :            :         else
        1629                 :       3602 :             break;
        1630                 :            :     }
        1631                 :            :
        1632                 :       6672 :     k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
        1633                 :       6672 :     dval(&rv) = y;
        1634         [ +  + ]:       6672 :     if (k > 9) {
        1635                 :       3925 :         dval(&rv) = tens[k - 9] * dval(&rv) + z;
        1636                 :            :     }
        1637         [ +  + ]:       6672 :     if (nd <= DBL_DIG
        1638                 :            :         && Flt_Rounds == 1
        1639                 :            :         ) {
        1640         [ +  + ]:       2795 :         if (!e)
        1641                 :       1236 :             goto ret;
        1642         [ +  + ]:       1559 :         if (e > 0) {
        1643         [ +  + ]:        271 :             if (e <= Ten_pmax) {
        1644                 :        202 :                 dval(&rv) *= tens[e];
        1645                 :        202 :                 goto ret;
        1646                 :            :             }
        1647                 :         69 :             i = DBL_DIG - nd;
        1648         [ +  + ]:         69 :             if (e <= Ten_pmax + i) {
        1649                 :            :                 /* A fancier test would sometimes let us do
        1650                 :            :                  * this for larger i values.
        1651                 :            :                  */
        1652                 :          3 :                 e -= i;
        1653                 :          3 :                 dval(&rv) *= tens[i];
        1654                 :          3 :                 dval(&rv) *= tens[e];
        1655                 :          3 :                 goto ret;
        1656                 :            :             }
        1657                 :            :         }
        1658         [ +  + ]:       1288 :         else if (e >= -Ten_pmax) {
        1659                 :       1055 :             dval(&rv) /= tens[-e];
        1660                 :       1055 :             goto ret;
        1661                 :            :         }
        1662                 :            :     }
        1663                 :       4176 :     e1 += nd - k;
        1664                 :            :
        1665                 :       4176 :     bc.scale = 0;
        1666                 :            :
        1667                 :            :     /* Get starting approximation = rv * 10**e1 */
        1668                 :            :
        1669         [ +  + ]:       4176 :     if (e1 > 0) {
        1670         [ +  + ]:        430 :         if ((i = e1 & 15))
        1671                 :        423 :             dval(&rv) *= tens[i];
        1672         [ +  + ]:        430 :         if (e1 &= ~15) {
        1673         [ +  + ]:        414 :             if (e1 > DBL_MAX_10_EXP)
        1674                 :          4 :                 goto ovfl;
        1675                 :        410 :             e1 >>= 4;
        1676         [ +  + ]:       1874 :             for(j = 0; e1 > 1; j++, e1 >>= 1)
        1677         [ +  + ]:       1464 :                 if (e1 & 1)
        1678                 :        395 :                     dval(&rv) *= bigtens[j];
        1679                 :            :             /* The last multiplication could overflow. */
        1680                 :        410 :             word0(&rv) -= P*Exp_msk1;
        1681                 :        410 :             dval(&rv) *= bigtens[j];
        1682         [ -  + ]:        410 :             if ((z = word0(&rv) & Exp_mask)
        1683                 :            :                 > Exp_msk1*(DBL_MAX_EXP+Bias-P))
        1684                 :          0 :                 goto ovfl;
        1685         [ -  + ]:        410 :             if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) {
        1686                 :            :                 /* set to largest number */
        1687                 :            :                 /* (Can't trust DBL_MAX) */
        1688                 :          0 :                 word0(&rv) = Big0;
        1689                 :          0 :                 word1(&rv) = Big1;
        1690                 :            :             }
        1691                 :            :             else
        1692                 :        410 :                 word0(&rv) += P*Exp_msk1;
        1693                 :            :         }
        1694                 :            :     }
        1695         [ +  + ]:       3746 :     else if (e1 < 0) {
        1696                 :            :         /* The input decimal value lies in [10**e1, 10**(e1+16)).
        1697                 :            :
        1698                 :            :            If e1 <= -512, underflow immediately.
        1699                 :            :            If e1 <= -256, set bc.scale to 2*P.
        1700                 :            :
        1701                 :            :            So for input value < 1e-256, bc.scale is always set;
        1702                 :            :            for input value >= 1e-240, bc.scale is never set.
        1703                 :            :            For input values in [1e-256, 1e-240), bc.scale may or may
        1704                 :            :            not be set. */
        1705                 :            :
        1706                 :       3731 :         e1 = -e1;
        1707         [ +  + ]:       3731 :         if ((i = e1 & 15))
        1708                 :       2870 :             dval(&rv) /= tens[i];
        1709         [ +  + ]:       3731 :         if (e1 >>= 4) {
        1710         [ -  + ]:       1829 :             if (e1 >= 1 << n_bigtens)
        1711                 :          0 :                 goto undfl;
        1712         [ +  + ]:       1829 :             if (e1 & Scale_Bit)
        1713                 :        412 :                 bc.scale = 2*P;
        1714         [ +  + ]:       5865 :             for(j = 0; e1 > 0; j++, e1 >>= 1)
        1715         [ +  + ]:       4036 :                 if (e1 & 1)
        1716                 :       2604 :                     dval(&rv) *= tinytens[j];
        1717         [ +  + ]:       1829 :             if (bc.scale && (j = 2*P + 1 - ((word0(&rv) & Exp_mask)
        1718         [ +  + ]:        412 :                                             >> Exp_shift)) > 0) {
        1719                 :            :                 /* scaled rv is denormal; clear j low bits */
        1720         [ +  + ]:        304 :                 if (j >= 32) {
        1721                 :        161 :                     word1(&rv) = 0;
        1722         [ +  + ]:        161 :                     if (j >= 53)
        1723                 :          6 :                         word0(&rv) = (P+2)*Exp_msk1;
        1724                 :            :                     else
        1725                 :        155 :                         word0(&rv) &= 0xffffffff << (j-32);
        1726                 :            :                 }
        1727                 :            :                 else
        1728                 :        143 :                     word1(&rv) &= 0xffffffff << j;
        1729                 :            :             }
        1730         [ -  + ]:       1829 :             if (!dval(&rv))
        1731                 :          0 :                 goto undfl;
        1732                 :            :         }
        1733                 :            :     }
        1734                 :            :
        1735                 :            :     /* Now the hard part -- adjusting rv to the correct value.*/
        1736                 :            :
        1737                 :            :     /* Put digits into bd: true value = bd * 10^e */
        1738                 :            :
        1739                 :       4172 :     bc.nd = nd;
        1740                 :       4172 :     bc.nd0 = nd0;       /* Only needed if nd > STRTOD_DIGLIM, but done here */
        1741                 :            :                         /* to silence an erroneous warning about bc.nd0 */
        1742                 :            :                         /* possibly not being initialized. */
        1743         [ +  + ]:       4172 :     if (nd > STRTOD_DIGLIM) {
        1744                 :            :         /* ASSERT(STRTOD_DIGLIM >= 18); 18 == one more than the */
        1745                 :            :         /* minimum number of decimal digits to distinguish double values */
        1746                 :            :         /* in IEEE arithmetic. */
        1747                 :            :
        1748                 :            :         /* Truncate input to 18 significant digits, then discard any trailing
        1749                 :            :            zeros on the result by updating nd, nd0, e and y suitably. (There's
        1750                 :            :            no need to update z; it's not reused beyond this point.) */
        1751         [ +  - ]:         34 :         for (i = 18; i > 0; ) {
        1752                 :            :             /* scan back until we hit a nonzero digit.  significant digit 'i'
        1753                 :            :             is s0[i] if i < nd0, s0[i+1] if i >= nd0. */
        1754                 :         34 :             --i;
        1755   [ -  +  +  + ]:         34 :             if (s0[i < nd0 ? i : i+1] != '0') {
        1756                 :         30 :                 ++i;
        1757                 :         30 :                 break;
        1758                 :            :             }
        1759                 :            :         }
        1760                 :         30 :         e += nd - i;
        1761                 :         30 :         nd = i;
        1762         [ -  + ]:         30 :         if (nd0 > nd)
        1763                 :          0 :             nd0 = nd;
        1764         [ -  + ]:         30 :         if (nd < 9) { /* must recompute y */
        1765                 :          0 :             y = 0;
        1766         [ #  # ]:          0 :             for(i = 0; i < nd0; ++i)
        1767                 :          0 :                 y = 10*y + s0[i] - '0';
        1768         [ #  # ]:          0 :             for(; i < nd; ++i)
        1769                 :          0 :                 y = 10*y + s0[i+1] - '0';
        1770                 :            :         }
        1771                 :            :     }
        1772                 :       4172 :     bd0 = s2b(s0, nd0, nd, y);
        1773         [ -  + ]:       4172 :     if (bd0 == NULL)
        1774                 :          0 :         goto failed_malloc;
        1775                 :            :
        1776                 :            :     /* Notation for the comments below.  Write:
        1777                 :            :
        1778                 :            :          - dv for the absolute value of the number represented by the original
        1779                 :            :            decimal input string.
        1780                 :            :
        1781                 :            :          - if we've truncated dv, write tdv for the truncated value.
        1782                 :            :            Otherwise, set tdv == dv.
        1783                 :            :
        1784                 :            :          - srv for the quantity rv/2^bc.scale; so srv is the current binary
        1785                 :            :            approximation to tdv (and dv).  It should be exactly representable
        1786                 :            :            in an IEEE 754 double.
        1787                 :            :     */
        1788                 :            :
        1789                 :            :     for(;;) {
        1790                 :            :
        1791                 :            :         /* This is the main correction loop for _Py_dg_strtod.
        1792                 :            :
        1793                 :            :            We've got a decimal value tdv, and a floating-point approximation
        1794                 :            :            srv=rv/2^bc.scale to tdv.  The aim is to determine whether srv is
        1795                 :            :            close enough (i.e., within 0.5 ulps) to tdv, and to compute a new
        1796                 :            :            approximation if not.
        1797                 :            :
        1798                 :            :            To determine whether srv is close enough to tdv, compute integers
        1799                 :            :            bd, bb and bs proportional to tdv, srv and 0.5 ulp(srv)
        1800                 :            :            respectively, and then use integer arithmetic to determine whether
        1801                 :            :            |tdv - srv| is less than, equal to, or greater than 0.5 ulp(srv).
        1802                 :            :         */
        1803                 :            :
        1804                 :       4502 :         bd = Balloc(bd0->k);
        1805         [ -  + ]:       4502 :         if (bd == NULL) {
        1806                 :          0 :             goto failed_malloc;
        1807                 :            :         }
        1808                 :       4502 :         Bcopy(bd, bd0);
        1809                 :       4502 :         bb = sd2b(&rv, bc.scale, &bbe);   /* srv = bb * 2^bbe */
        1810         [ -  + ]:       4502 :         if (bb == NULL) {
        1811                 :          0 :             goto failed_malloc;
        1812                 :            :         }
        1813                 :            :         /* Record whether lsb of bb is odd, in case we need this
        1814                 :            :            for the round-to-even step later. */
        1815                 :       4502 :         odd = bb->x[0] & 1;
        1816                 :            :
        1817                 :            :         /* tdv = bd * 10**e;  srv = bb * 2**bbe */
        1818                 :       4502 :         bs = i2b(1);
        1819         [ -  + ]:       4502 :         if (bs == NULL) {
        1820                 :          0 :             goto failed_malloc;
        1821                 :            :         }
        1822                 :            :
        1823         [ +  + ]:       4502 :         if (e >= 0) {
        1824                 :        434 :             bb2 = bb5 = 0;
        1825                 :        434 :             bd2 = bd5 = e;
        1826                 :            :         }
        1827                 :            :         else {
        1828                 :       4068 :             bb2 = bb5 = -e;
        1829                 :       4068 :             bd2 = bd5 = 0;
        1830                 :            :         }
        1831         [ +  + ]:       4502 :         if (bbe >= 0)
        1832                 :        434 :             bb2 += bbe;
        1833                 :            :         else
        1834                 :       4068 :             bd2 -= bbe;
        1835                 :       4502 :         bs2 = bb2;
        1836                 :       4502 :         bb2++;
        1837                 :       4502 :         bd2++;
        1838                 :            :
        1839                 :            :         /* At this stage bd5 - bb5 == e == bd2 - bb2 + bbe, bb2 - bs2 == 1,
        1840                 :            :            and bs == 1, so:
        1841                 :            :
        1842                 :            :               tdv == bd * 10**e = bd * 2**(bbe - bb2 + bd2) * 5**(bd5 - bb5)
        1843                 :            :               srv == bb * 2**bbe = bb * 2**(bbe - bb2 + bb2)
        1844                 :            :               0.5 ulp(srv) == 2**(bbe-1) = bs * 2**(bbe - bb2 + bs2)
        1845                 :            :
        1846                 :            :            It follows that:
        1847                 :            :
        1848                 :            :               M * tdv = bd * 2**bd2 * 5**bd5
        1849                 :            :               M * srv = bb * 2**bb2 * 5**bb5
        1850                 :            :               M * 0.5 ulp(srv) = bs * 2**bs2 * 5**bb5
        1851                 :            :
        1852                 :            :            for some constant M.  (Actually, M == 2**(bb2 - bbe) * 5**bb5, but
        1853                 :            :            this fact is not needed below.)
        1854                 :            :         */
        1855                 :            :
        1856                 :            :         /* Remove factor of 2**i, where i = min(bb2, bd2, bs2). */
        1857                 :       4502 :         i = bb2 < bd2 ? bb2 : bd2;
        1858         [ +  + ]:       4502 :         if (i > bs2)
        1859                 :       4073 :             i = bs2;
        1860         [ +  + ]:       4502 :         if (i > 0) {
        1861                 :       4496 :             bb2 -= i;
        1862                 :       4496 :             bd2 -= i;
        1863                 :       4496 :             bs2 -= i;
        1864                 :            :         }
        1865                 :            :
        1866                 :            :         /* Scale bb, bd, bs by the appropriate powers of 2 and 5. */
        1867         [ +  + ]:       4502 :         if (bb5 > 0) {
        1868                 :       4068 :             bs = pow5mult(bs, bb5);
        1869         [ -  + ]:       4068 :             if (bs == NULL) {
        1870                 :          0 :                 goto failed_malloc;
        1871                 :            :             }
        1872                 :       4068 :             Bigint *bb1 = mult(bs, bb);
        1873                 :       4068 :             Bfree(bb);
        1874                 :       4068 :             bb = bb1;
        1875         [ -  + ]:       4068 :             if (bb == NULL) {
        1876                 :          0 :                 goto failed_malloc;
        1877                 :            :             }
        1878                 :            :         }
        1879         [ +  - ]:       4502 :         if (bb2 > 0) {
        1880                 :       4502 :             bb = lshift(bb, bb2);
        1881         [ -  + ]:       4502 :             if (bb == NULL) {
        1882                 :          0 :                 goto failed_malloc;
        1883                 :            :             }
        1884                 :            :         }
        1885         [ +  + ]:       4502 :         if (bd5 > 0) {
        1886                 :        417 :             bd = pow5mult(bd, bd5);
        1887         [ -  + ]:        417 :             if (bd == NULL) {
        1888                 :          0 :                 goto failed_malloc;
        1889                 :            :             }
        1890                 :            :         }
        1891         [ +  + ]:       4502 :         if (bd2 > 0) {
        1892                 :       4073 :             bd = lshift(bd, bd2);
        1893         [ -  + ]:       4073 :             if (bd == NULL) {
        1894                 :          0 :                 goto failed_malloc;
        1895                 :            :             }
        1896                 :            :         }
        1897         [ +  + ]:       4502 :         if (bs2 > 0) {
        1898                 :        426 :             bs = lshift(bs, bs2);
        1899         [ -  + ]:        426 :             if (bs == NULL) {
        1900                 :          0 :                 goto failed_malloc;
        1901                 :            :             }
        1902                 :            :         }
        1903                 :            :
        1904                 :            :         /* Now bd, bb and bs are scaled versions of tdv, srv and 0.5 ulp(srv),
        1905                 :            :            respectively.  Compute the difference |tdv - srv|, and compare
        1906                 :            :            with 0.5 ulp(srv). */
        1907                 :            :
        1908                 :       4502 :         delta = diff(bb, bd);
        1909         [ -  + ]:       4502 :         if (delta == NULL) {
        1910                 :          0 :             goto failed_malloc;
        1911                 :            :         }
        1912                 :       4502 :         dsign = delta->sign;
        1913                 :       4502 :         delta->sign = 0;
        1914                 :       4502 :         i = cmp(delta, bs);
        1915   [ +  +  +  + ]:       4502 :         if (bc.nd > nd && i <= 0) {
        1916         [ +  + ]:         30 :             if (dsign)
        1917                 :         23 :                 break;  /* Must use bigcomp(). */
        1918                 :            :
        1919                 :            :             /* Here rv overestimates the truncated decimal value by at most
        1920                 :            :                0.5 ulp(rv).  Hence rv either overestimates the true decimal
        1921                 :            :                value by <= 0.5 ulp(rv), or underestimates it by some small
        1922                 :            :                amount (< 0.1 ulp(rv)); either way, rv is within 0.5 ulps of
        1923                 :            :                the true decimal value, so it's possible to exit.
        1924                 :            :
        1925                 :            :                Exception: if scaled rv is a normal exact power of 2, but not
        1926                 :            :                DBL_MIN, then rv - 0.5 ulp(rv) takes us all the way down to the
        1927                 :            :                next double, so the correctly rounded result is either rv - 0.5
        1928                 :            :                ulp(rv) or rv; in this case, use bigcomp to distinguish. */
        1929                 :            :
        1930   [ -  +  -  - ]:          7 :             if (!word1(&rv) && !(word0(&rv) & Bndry_mask)) {
        1931                 :            :                 /* rv can't be 0, since it's an overestimate for some
        1932                 :            :                    nonzero value.  So rv is a normal power of 2. */
        1933                 :          0 :                 j = (int)(word0(&rv) & Exp_mask) >> Exp_shift;
        1934                 :            :                 /* rv / 2^bc.scale = 2^(j - 1023 - bc.scale); use bigcomp if
        1935                 :            :                    rv / 2^bc.scale >= 2^-1021. */
        1936         [ #  # ]:          0 :                 if (j - bc.scale >= 2) {
        1937                 :          0 :                     dval(&rv) -= 0.5 * sulp(&rv, &bc);
        1938                 :          0 :                     break; /* Use bigcomp. */
        1939                 :            :                 }
        1940                 :            :             }
        1941                 :            :
        1942                 :            :             {
        1943                 :          7 :                 bc.nd = nd;
        1944                 :          7 :                 i = -1; /* Discarded digits make delta smaller. */
        1945                 :            :             }
        1946                 :            :         }
        1947                 :            :
        1948         [ +  + ]:       4479 :         if (i < 0) {
        1949                 :            :             /* Error is less than half an ulp -- check for
        1950                 :            :              * special case of mantissa a power of two.
        1951                 :            :              */
        1952   [ +  +  +  +  :       1604 :             if (dsign || word1(&rv) || word0(&rv) & Bndry_mask
                       +  + ]
        1953         [ +  + ]:         36 :                 || (word0(&rv) & Exp_mask) <= (2*P+1)*Exp_msk1
        1954                 :            :                 ) {
        1955                 :            :                 break;
        1956                 :            :             }
        1957   [ +  +  +  + ]:         28 :             if (!delta->x[0] && delta->wds <= 1) {
        1958                 :            :                 /* exact result */
        1959                 :          9 :                 break;
        1960                 :            :             }
        1961                 :         19 :             delta = lshift(delta,Log2P);
        1962         [ -  + ]:         19 :             if (delta == NULL) {
        1963                 :          0 :                 goto failed_malloc;
        1964                 :            :             }
        1965         [ +  + ]:         19 :             if (cmp(delta, bs) > 0)
        1966                 :          2 :                 goto drop_down;
        1967                 :         17 :             break;
        1968                 :            :         }
        1969         [ -  + ]:       2875 :         if (i == 0) {
        1970                 :            :             /* exactly half-way between */
        1971         [ #  # ]:          0 :             if (dsign) {
        1972         [ #  # ]:          0 :                 if ((word0(&rv) & Bndry_mask1) == Bndry_mask1
        1973         [ #  # ]:          0 :                     &&  word1(&rv) == (
        1974                 :          0 :                         (bc.scale &&
        1975         [ #  # ]:          0 :                          (y = word0(&rv) & Exp_mask) <= 2*P*Exp_msk1) ?
        1976         [ #  # ]:          0 :                         (0xffffffff & (0xffffffff << (2*P+1-(y>>Exp_shift)))) :
        1977                 :            :                         0xffffffff)) {
        1978                 :            :                     /*boundary case -- increment exponent*/
        1979                 :          0 :                     word0(&rv) = (word0(&rv) & Exp_mask)
        1980                 :          0 :                         + Exp_msk1
        1981                 :            :                         ;
        1982                 :          0 :                     word1(&rv) = 0;
        1983                 :            :                     /* dsign = 0; */
        1984                 :          0 :                     break;
        1985                 :            :                 }
        1986                 :            :             }
        1987   [ #  #  #  # ]:          0 :             else if (!(word0(&rv) & Bndry_mask) && !word1(&rv)) {
        1988                 :          0 :               drop_down:
        1989                 :            :                 /* boundary case -- decrement exponent */
        1990         [ -  + ]:          2 :                 if (bc.scale) {
        1991                 :          0 :                     L = word0(&rv) & Exp_mask;
        1992         [ #  # ]:          0 :                     if (L <= (2*P+1)*Exp_msk1) {
        1993         [ #  # ]:          0 :                         if (L > (P+2)*Exp_msk1)
        1994                 :            :                             /* round even ==> */
        1995                 :            :                             /* accept rv */
        1996                 :          0 :                             break;
        1997                 :            :                         /* rv = smallest denormal */
        1998         [ #  # ]:          0 :                         if (bc.nd > nd)
        1999                 :          0 :                             break;
        2000                 :          0 :                         goto undfl;
        2001                 :            :                     }
        2002                 :            :                 }
        2003                 :          2 :                 L = (word0(&rv) & Exp_mask) - Exp_msk1;
        2004                 :          2 :                 word0(&rv) = L | Bndry_mask1;
        2005                 :          2 :                 word1(&rv) = 0xffffffff;
        2006                 :          2 :                 break;
        2007                 :            :             }
        2008         [ #  # ]:          0 :             if (!odd)
        2009                 :          0 :                 break;
        2010         [ #  # ]:          0 :             if (dsign)
        2011                 :          0 :                 dval(&rv) += sulp(&rv, &bc);
        2012                 :            :             else {
        2013                 :          0 :                 dval(&rv) -= sulp(&rv, &bc);
        2014         [ #  # ]:          0 :                 if (!dval(&rv)) {
        2015         [ #  # ]:          0 :                     if (bc.nd >nd)
        2016                 :          0 :                         break;
        2017                 :          0 :                     goto undfl;
        2018                 :            :                 }
        2019                 :            :             }
        2020                 :            :             /* dsign = 1 - dsign; */
        2021                 :          0 :             break;
        2022                 :            :         }
        2023         [ +  + ]:       2875 :         if ((aadj = ratio(delta, bs)) <= 2.) {
        2024         [ +  + ]:        913 :             if (dsign)
        2025                 :        738 :                 aadj = aadj1 = 1.;
        2026   [ -  +  -  - ]:        175 :             else if (word1(&rv) || word0(&rv) & Bndry_mask) {
        2027   [ -  +  -  - ]:        175 :                 if (word1(&rv) == Tiny1 && !word0(&rv)) {
        2028         [ #  # ]:          0 :                     if (bc.nd >nd)
        2029                 :          0 :                         break;
        2030                 :          0 :                     goto undfl;
        2031                 :            :                 }
        2032                 :        175 :                 aadj = 1.;
        2033                 :        175 :                 aadj1 = -1.;
        2034                 :            :             }
        2035                 :            :             else {
        2036                 :            :                 /* special case -- power of FLT_RADIX to be */
        2037                 :            :                 /* rounded down... */
        2038                 :            :
        2039         [ #  # ]:          0 :                 if (aadj < 2./FLT_RADIX)
        2040                 :          0 :                     aadj = 1./FLT_RADIX;
        2041                 :            :                 else
        2042                 :          0 :                     aadj *= 0.5;
        2043                 :          0 :                 aadj1 = -aadj;
        2044                 :            :             }
        2045                 :            :         }
        2046                 :            :         else {
        2047                 :       1962 :             aadj *= 0.5;
        2048         [ +  + ]:       1962 :             aadj1 = dsign ? aadj : -aadj;
        2049                 :            :             if (Flt_Rounds == 0)
        2050                 :            :                 aadj1 += 0.5;
        2051                 :            :         }
        2052                 :       2875 :         y = word0(&rv) & Exp_mask;
        2053                 :            :
        2054                 :            :         /* Check for overflow */
        2055                 :            :
        2056         [ +  + ]:       2875 :         if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) {
        2057                 :        125 :             dval(&rv0) = dval(&rv);
        2058                 :        125 :             word0(&rv) -= P*Exp_msk1;
        2059                 :        125 :             adj.d = aadj1 * ulp(&rv);
        2060                 :        125 :             dval(&rv) += adj.d;
        2061         [ -  + ]:        125 :             if ((word0(&rv) & Exp_mask) >=
        2062                 :            :                 Exp_msk1*(DBL_MAX_EXP+Bias-P)) {
        2063   [ #  #  #  # ]:          0 :                 if (word0(&rv0) == Big0 && word1(&rv0) == Big1) {
        2064                 :          0 :                     goto ovfl;
        2065                 :            :                 }
        2066                 :          0 :                 word0(&rv) = Big0;
        2067                 :          0 :                 word1(&rv) = Big1;
        2068                 :          0 :                 goto cont;
        2069                 :            :             }
        2070                 :            :             else
        2071                 :        125 :                 word0(&rv) += P*Exp_msk1;
        2072                 :            :         }
        2073                 :            :         else {
        2074   [ +  +  +  + ]:       2750 :             if (bc.scale && y <= 2*P*Exp_msk1) {
        2075         [ +  - ]:        217 :                 if (aadj <= 0x7fffffff) {
        2076         [ -  + ]:        217 :                     if ((z = (ULong)aadj) <= 0)
        2077                 :          0 :                         z = 1;
        2078                 :        217 :                     aadj = z;
        2079         [ -  + ]:        217 :                     aadj1 = dsign ? aadj : -aadj;
        2080                 :            :                 }
        2081                 :        217 :                 dval(&aadj2) = aadj1;
        2082                 :        217 :                 word0(&aadj2) += (2*P+1)*Exp_msk1 - y;
        2083                 :        217 :                 aadj1 = dval(&aadj2);
        2084                 :            :             }
        2085                 :       2750 :             adj.d = aadj1 * ulp(&rv);
        2086                 :       2750 :             dval(&rv) += adj.d;
        2087                 :            :         }
        2088                 :       2875 :         z = word0(&rv) & Exp_mask;
        2089         [ +  + ]:       2875 :         if (bc.nd == nd) {
        2090         [ +  + ]:       2853 :             if (!bc.scale)
        2091         [ +  + ]:       2561 :                 if (y == z) {
        2092                 :            :                     /* Can we stop now? */
        2093                 :       2545 :                     L = (Long)aadj;
        2094                 :       2545 :                     aadj -= L;
        2095                 :            :                     /* The tolerances below are conservative. */
        2096   [ +  +  -  +  :       2545 :                     if (dsign || word1(&rv) || word0(&rv) & Bndry_mask) {
                       -  - ]
        2097   [ +  +  -  + ]:       2545 :                         if (aadj < .4999999 || aadj > .5000001)
        2098                 :            :                             break;
        2099                 :            :                     }
        2100         [ #  # ]:          0 :                     else if (aadj < .4999999/FLT_RADIX)
        2101                 :          0 :                         break;
        2102                 :            :                 }
        2103                 :            :         }
        2104                 :        330 :       cont:
        2105                 :        330 :         Bfree(bb); bb = NULL;
        2106                 :        330 :         Bfree(bd); bd = NULL;
        2107                 :        330 :         Bfree(bs); bs = NULL;
        2108                 :        330 :         Bfree(delta); delta = NULL;
        2109                 :            :     }
        2110         [ +  + ]:       4172 :     if (bc.nd > nd) {
        2111                 :         23 :         error = bigcomp(&rv, s0, &bc);
        2112         [ -  + ]:         23 :         if (error)
        2113                 :          0 :             goto failed_malloc;
        2114                 :            :     }
        2115                 :            :
        2116         [ +  + ]:       4172 :     if (bc.scale) {
        2117                 :        412 :         word0(&rv0) = Exp_1 - 2*P*Exp_msk1;
        2118                 :        412 :         word1(&rv0) = 0;
        2119                 :        412 :         dval(&rv) *= dval(&rv0);
        2120                 :            :     }
        2121                 :            :
        2122                 :       3760 :   ret:
        2123         [ +  + ]:       9452 :     result = sign ? -dval(&rv) : dval(&rv);
        2124                 :       9452 :     goto done;
        2125                 :            :
        2126                 :       2019 :   parse_error:
        2127                 :       2019 :     result = 0.0;
        2128                 :       2019 :     goto done;
        2129                 :            :
        2130                 :          0 :   failed_malloc:
        2131                 :          0 :     errno = ENOMEM;
        2132                 :          0 :     result = -1.0;
        2133                 :          0 :     goto done;
        2134                 :            :
        2135                 :          0 :   undfl:
        2136         [ #  # ]:          0 :     result = sign ? -0.0 : 0.0;
        2137                 :          0 :     goto done;
        2138                 :            :
        2139                 :          4 :   ovfl:
        2140                 :          4 :     errno = ERANGE;
        2141                 :            :     /* Can't trust HUGE_VAL */
        2142                 :          4 :     word0(&rv) = Exp_mask;
        2143                 :          4 :     word1(&rv) = 0;
        2144         [ -  + ]:          4 :     result = sign ? -dval(&rv) : dval(&rv);
        2145                 :          4 :     goto done;
        2146                 :            :
        2147                 :      11475 :   done:
        2148                 :      11475 :     Bfree(bb);
        2149                 :      11475 :     Bfree(bd);
        2150                 :      11475 :     Bfree(bs);
        2151                 :      11475 :     Bfree(bd0);
        2152                 :      11475 :     Bfree(delta);
        2153                 :      11475 :     return result;
        2154                 :            :
        2155                 :            : }
        2156                 :            :
        2157                 :            : static char *
        2158                 :        112 : rv_alloc(int i)
        2159                 :            : {
        2160                 :            :     int j, k, *r;
        2161                 :            :
        2162                 :        112 :     j = sizeof(ULong);
        2163                 :        112 :     for(k = 0;
        2164         [ -  + ]:        112 :         sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= (unsigned)i;
        2165                 :          0 :         j <<= 1)
        2166                 :          0 :         k++;
        2167                 :        112 :     r = (int*)Balloc(k);
        2168         [ -  + ]:        112 :     if (r == NULL)
        2169                 :          0 :         return NULL;
        2170                 :        112 :     *r = k;
        2171                 :        112 :     return (char *)(r+1);
        2172                 :            : }
        2173                 :            :
        2174                 :            : static char *
        2175                 :         54 : nrv_alloc(const char *s, char **rve, int n)
        2176                 :            : {
        2177                 :            :     char *rv, *t;
        2178                 :            :
        2179                 :         54 :     rv = rv_alloc(n);
        2180         [ -  + ]:         54 :     if (rv == NULL)
        2181                 :          0 :         return NULL;
        2182                 :         54 :     t = rv;
        2183         [ +  + ]:        313 :     while((*t = *s++)) t++;
        2184         [ +  - ]:         54 :     if (rve)
        2185                 :         54 :         *rve = t;
        2186                 :         54 :     return rv;
        2187                 :            : }
        2188                 :            :
        2189                 :            : /* freedtoa(s) must be used to free values s returned by dtoa
        2190                 :            :  * when MULTIPLE_THREADS is #defined.  It should be used in all cases,
        2191                 :            :  * but for consistency with earlier versions of dtoa, it is optional
        2192                 :            :  * when MULTIPLE_THREADS is not defined.
        2193                 :            :  */
        2194                 :            :
        2195                 :            : void
        2196                 :        112 : _Py_dg_freedtoa(char *s)
        2197                 :            : {
        2198                 :        112 :     Bigint *b = (Bigint *)((int *)s - 1);
        2199                 :        112 :     b->maxwds = 1 << (b->k = *(int*)b);
        2200                 :        112 :     Bfree(b);
        2201                 :        112 : }
        2202                 :            :
        2203                 :            : /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
        2204                 :            :  *
        2205                 :            :  * Inspired by "How to Print Floating-Point Numbers Accurately" by
        2206                 :            :  * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126].
        2207                 :            :  *
        2208                 :            :  * Modifications:
        2209                 :            :  *      1. Rather than iterating, we use a simple numeric overestimate
        2210                 :            :  *         to determine k = floor(log10(d)).  We scale relevant
        2211                 :            :  *         quantities using O(log2(k)) rather than O(k) multiplications.
        2212                 :            :  *      2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
        2213                 :            :  *         try to generate digits strictly left to right.  Instead, we
        2214                 :            :  *         compute with fewer bits and propagate the carry if necessary
        2215                 :            :  *         when rounding the final digit up.  This is often faster.
        2216                 :            :  *      3. Under the assumption that input will be rounded nearest,
        2217                 :            :  *         mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
        2218                 :            :  *         That is, we allow equality in stopping tests when the
        2219                 :            :  *         round-nearest rule will give the same floating-point value
        2220                 :            :  *         as would satisfaction of the stopping test with strict
        2221                 :            :  *         inequality.
        2222                 :            :  *      4. We remove common factors of powers of 2 from relevant
        2223                 :            :  *         quantities.
        2224                 :            :  *      5. When converting floating-point integers less than 1e16,
        2225                 :            :  *         we use floating-point arithmetic rather than resorting
        2226                 :            :  *         to multiple-precision integers.
        2227                 :            :  *      6. When asked to produce fewer than 15 digits, we first try
        2228                 :            :  *         to get by with floating-point arithmetic; we resort to
        2229                 :            :  *         multiple-precision integer arithmetic only if we cannot
        2230                 :            :  *         guarantee that the floating-point calculation has given
        2231                 :            :  *         the correctly rounded result.  For k requested digits and
        2232                 :            :  *         "uniformly" distributed input, the probability is
        2233                 :            :  *         something like 10^(k-15) that we must resort to the Long
        2234                 :            :  *         calculation.
        2235                 :            :  */
        2236                 :            :
        2237                 :            : /* Additional notes (METD): (1) returns NULL on failure.  (2) to avoid memory
        2238                 :            :    leakage, a successful call to _Py_dg_dtoa should always be matched by a
        2239                 :            :    call to _Py_dg_freedtoa. */
        2240                 :            :
        2241                 :            : char *
        2242                 :        112 : _Py_dg_dtoa(double dd, int mode, int ndigits,
        2243                 :            :             int *decpt, int *sign, char **rve)
        2244                 :            : {
        2245                 :            :     /*  Arguments ndigits, decpt, sign are similar to those
        2246                 :            :         of ecvt and fcvt; trailing zeros are suppressed from
        2247                 :            :         the returned string.  If not null, *rve is set to point
        2248                 :            :         to the end of the return value.  If d is +-Infinity or NaN,
        2249                 :            :         then *decpt is set to 9999.
        2250                 :            :
        2251                 :            :         mode:
        2252                 :            :         0 ==> shortest string that yields d when read in
        2253                 :            :         and rounded to nearest.
        2254                 :            :         1 ==> like 0, but with Steele & White stopping rule;
        2255                 :            :         e.g. with IEEE P754 arithmetic , mode 0 gives
        2256                 :            :         1e23 whereas mode 1 gives 9.999999999999999e22.
        2257                 :            :         2 ==> max(1,ndigits) significant digits.  This gives a
        2258                 :            :         return value similar to that of ecvt, except
        2259                 :            :         that trailing zeros are suppressed.
        2260                 :            :         3 ==> through ndigits past the decimal point.  This
        2261                 :            :         gives a return value similar to that from fcvt,
        2262                 :            :         except that trailing zeros are suppressed, and
        2263                 :            :         ndigits can be negative.
        2264                 :            :         4,5 ==> similar to 2 and 3, respectively, but (in
        2265                 :            :         round-nearest mode) with the tests of mode 0 to
        2266                 :            :         possibly return a shorter string that rounds to d.
        2267                 :            :         With IEEE arithmetic and compilation with
        2268                 :            :         -DHonor_FLT_ROUNDS, modes 4 and 5 behave the same
        2269                 :            :         as modes 2 and 3 when FLT_ROUNDS != 1.
        2270                 :            :         6-9 ==> Debugging modes similar to mode - 4:  don't try
        2271                 :            :         fast floating-point estimate (if applicable).
        2272                 :            :
        2273                 :            :         Values of mode other than 0-9 are treated as mode 0.
        2274                 :            :
        2275                 :            :         Sufficient space is allocated to the return value
        2276                 :            :         to hold the suppressed trailing zeros.
        2277                 :            :     */
        2278                 :            :
        2279                 :            :     int bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1,
        2280                 :            :         j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
        2281                 :            :         spec_case, try_quick;
        2282                 :            :     Long L;
        2283                 :            :     int denorm;
        2284                 :            :     ULong x;
        2285                 :            :     Bigint *b, *b1, *delta, *mlo, *mhi, *S;
        2286                 :            :     U d2, eps, u;
        2287                 :            :     double ds;
        2288                 :            :     char *s, *s0;
        2289                 :            :
        2290                 :            :     /* set pointers to NULL, to silence gcc compiler warnings and make
        2291                 :            :        cleanup easier on error */
        2292                 :        112 :     mlo = mhi = S = 0;
        2293                 :        112 :     s0 = 0;
        2294                 :            :
        2295                 :        112 :     u.d = dd;
        2296         [ +  + ]:        112 :     if (word0(&u) & Sign_bit) {
        2297                 :            :         /* set sign for everything, including 0's and NaNs */
        2298                 :         22 :         *sign = 1;
        2299                 :         22 :         word0(&u) &= ~Sign_bit; /* clear sign bit */
        2300                 :            :     }
        2301                 :            :     else
        2302                 :         90 :         *sign = 0;
        2303                 :            :
        2304                 :            :     /* quick return for Infinities, NaNs and zeros */
        2305         [ +  + ]:        112 :     if ((word0(&u) & Exp_mask) == Exp_mask)
        2306                 :            :     {
        2307                 :            :         /* Infinity or NaN */
        2308                 :         45 :         *decpt = 9999;
        2309   [ +  -  +  + ]:         45 :         if (!word1(&u) && !(word0(&u) & 0xfffff))
        2310                 :         23 :             return nrv_alloc("Infinity", rve, 8);
        2311                 :         22 :         return nrv_alloc("NaN", rve, 3);
        2312                 :            :     }
        2313         [ +  + ]:         67 :     if (!dval(&u)) {
        2314                 :          9 :         *decpt = 1;
        2315                 :          9 :         return nrv_alloc("0", rve, 1);
        2316                 :            :     }
        2317                 :            :
        2318                 :            :     /* compute k = floor(log10(d)).  The computation may leave k
        2319                 :            :        one too large, but should never leave k too small. */
        2320                 :         58 :     b = d2b(&u, &be, &bbits);
        2321         [ -  + ]:         58 :     if (b == NULL)
        2322                 :          0 :         goto failed_malloc;
        2323         [ +  - ]:         58 :     if ((i = (int)(word0(&u) >> Exp_shift1 & (Exp_mask>>Exp_shift1)))) {
        2324                 :         58 :         dval(&d2) = dval(&u);
        2325                 :         58 :         word0(&d2) &= Frac_mask1;
        2326                 :         58 :         word0(&d2) |= Exp_11;
        2327                 :            :
        2328                 :            :         /* log(x)       ~=~ log(1.5) + (x-1.5)/1.5
        2329                 :            :          * log10(x)      =  log(x) / log(10)
        2330                 :            :          *              ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
        2331                 :            :          * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2)
        2332                 :            :          *
        2333                 :            :          * This suggests computing an approximation k to log10(d) by
        2334                 :            :          *
        2335                 :            :          * k = (i - Bias)*0.301029995663981
        2336                 :            :          *      + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
        2337                 :            :          *
        2338                 :            :          * We want k to be too large rather than too small.
        2339                 :            :          * The error in the first-order Taylor series approximation
        2340                 :            :          * is in our favor, so we just round up the constant enough
        2341                 :            :          * to compensate for any error in the multiplication of
        2342                 :            :          * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
        2343                 :            :          * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
        2344                 :            :          * adding 1e-13 to the constant term more than suffices.
        2345                 :            :          * Hence we adjust the constant term to 0.1760912590558.
        2346                 :            :          * (We could get a more accurate k by invoking log10,
        2347                 :            :          *  but this is probably not worthwhile.)
        2348                 :            :          */
        2349                 :            :
        2350                 :         58 :         i -= Bias;
        2351                 :         58 :         denorm = 0;
        2352                 :            :     }
        2353                 :            :     else {
        2354                 :            :         /* d is denormalized */
        2355                 :            :
        2356                 :          0 :         i = bbits + be + (Bias + (P-1) - 1);
        2357                 :          0 :         x = i > 32  ? word0(&u) << (64 - i) | word1(&u) >> (i - 32)
        2358         [ #  # ]:          0 :             : word1(&u) << (32 - i);
        2359                 :          0 :         dval(&d2) = x;
        2360                 :          0 :         word0(&d2) -= 31*Exp_msk1; /* adjust exponent */
        2361                 :          0 :         i -= (Bias + (P-1) - 1) + 1;
        2362                 :          0 :         denorm = 1;
        2363                 :            :     }
        2364                 :         58 :     ds = (dval(&d2)-1.5)*0.289529654602168 + 0.1760912590558 +
        2365                 :         58 :         i*0.301029995663981;
        2366                 :         58 :     k = (int)ds;
        2367   [ +  +  +  - ]:         58 :     if (ds < 0. && ds != k)
        2368                 :         22 :         k--;    /* want k = floor(ds) */
        2369                 :         58 :     k_check = 1;
        2370   [ +  +  +  + ]:         58 :     if (k >= 0 && k <= Ten_pmax) {
        2371         [ +  + ]:         30 :         if (dval(&u) < tens[k])
        2372                 :          1 :             k--;
        2373                 :         30 :         k_check = 0;
        2374                 :            :     }
        2375                 :         58 :     j = bbits - i - 1;
        2376         [ +  + ]:         58 :     if (j >= 0) {
        2377                 :         48 :         b2 = 0;
        2378                 :         48 :         s2 = j;
        2379                 :            :     }
        2380                 :            :     else {
        2381                 :         10 :         b2 = -j;
        2382                 :         10 :         s2 = 0;
        2383                 :            :     }
        2384         [ +  + ]:         58 :     if (k >= 0) {
        2385                 :         35 :         b5 = 0;
        2386                 :         35 :         s5 = k;
        2387                 :         35 :         s2 += k;
        2388                 :            :     }
        2389                 :            :     else {
        2390                 :         23 :         b2 -= k;
        2391                 :         23 :         b5 = -k;
        2392                 :         23 :         s5 = 0;
        2393                 :            :     }
        2394   [ +  -  -  + ]:         58 :     if (mode < 0 || mode > 9)
        2395                 :          0 :         mode = 0;
        2396                 :            :
        2397                 :         58 :     try_quick = 1;
        2398                 :            :
        2399         [ -  + ]:         58 :     if (mode > 5) {
        2400                 :          0 :         mode -= 4;
        2401                 :          0 :         try_quick = 0;
        2402                 :            :     }
        2403                 :         58 :     leftright = 1;
        2404                 :         58 :     ilim = ilim1 = -1;  /* Values for cases 0 and 1; done here to */
        2405                 :            :     /* silence erroneous "gcc -Wall" warning. */
        2406   [ +  -  -  +  :         58 :     switch(mode) {
                       -  - ]
        2407                 :         50 :     case 0:
        2408                 :            :     case 1:
        2409                 :         50 :         i = 18;
        2410                 :         50 :         ndigits = 0;
        2411                 :         50 :         break;
        2412                 :          0 :     case 2:
        2413                 :          0 :         leftright = 0;
        2414                 :            :         /* fall through */
        2415                 :          0 :     case 4:
        2416         [ #  # ]:          0 :         if (ndigits <= 0)
        2417                 :          0 :             ndigits = 1;
        2418                 :          0 :         ilim = ilim1 = i = ndigits;
        2419                 :          0 :         break;
        2420                 :          8 :     case 3:
        2421                 :          8 :         leftright = 0;
        2422                 :            :         /* fall through */
        2423                 :          8 :     case 5:
        2424                 :          8 :         i = ndigits + k + 1;
        2425                 :          8 :         ilim = i;
        2426                 :          8 :         ilim1 = i - 1;
        2427         [ +  + ]:          8 :         if (i <= 0)
        2428                 :          6 :             i = 1;
        2429                 :            :     }
        2430                 :         58 :     s0 = rv_alloc(i);
        2431         [ -  + ]:         58 :     if (s0 == NULL)
        2432                 :          0 :         goto failed_malloc;
        2433                 :         58 :     s = s0;
        2434                 :            :
        2435                 :            :
        2436   [ +  +  +  -  :         58 :     if (ilim >= 0 && ilim <= Quick_max && try_quick) {
                       +  - ]
        2437                 :            :
        2438                 :            :         /* Try to get by with floating-point arithmetic. */
        2439                 :            :
        2440                 :          2 :         i = 0;
        2441                 :          2 :         dval(&d2) = dval(&u);
        2442                 :          2 :         k0 = k;
        2443                 :          2 :         ilim0 = ilim;
        2444                 :          2 :         ieps = 2; /* conservative */
        2445         [ -  + ]:          2 :         if (k > 0) {
        2446                 :          0 :             ds = tens[k&0xf];
        2447                 :          0 :             j = k >> 4;
        2448         [ #  # ]:          0 :             if (j & Bletch) {
        2449                 :            :                 /* prevent overflows */
        2450                 :          0 :                 j &= Bletch - 1;
        2451                 :          0 :                 dval(&u) /= bigtens[n_bigtens-1];
        2452                 :          0 :                 ieps++;
        2453                 :            :             }
        2454         [ #  # ]:          0 :             for(; j; j >>= 1, i++)
        2455         [ #  # ]:          0 :                 if (j & 1) {
        2456                 :          0 :                     ieps++;
        2457                 :          0 :                     ds *= bigtens[i];
        2458                 :            :                 }
        2459                 :          0 :             dval(&u) /= ds;
        2460                 :            :         }
        2461         [ -  + ]:          2 :         else if ((j1 = -k)) {
        2462                 :          0 :             dval(&u) *= tens[j1 & 0xf];
        2463         [ #  # ]:          0 :             for(j = j1 >> 4; j; j >>= 1, i++)
        2464         [ #  # ]:          0 :                 if (j & 1) {
        2465                 :          0 :                     ieps++;
        2466                 :          0 :                     dval(&u) *= bigtens[i];
        2467                 :            :                 }
        2468                 :            :         }
        2469   [ -  +  -  -  :          2 :         if (k_check && dval(&u) < 1. && ilim > 0) {
                       -  - ]
        2470         [ #  # ]:          0 :             if (ilim1 <= 0)
        2471                 :          0 :                 goto fast_failed;
        2472                 :          0 :             ilim = ilim1;
        2473                 :          0 :             k--;
        2474                 :          0 :             dval(&u) *= 10.;
        2475                 :          0 :             ieps++;
        2476                 :            :         }
        2477                 :          2 :         dval(&eps) = ieps*dval(&u) + 7.;
        2478                 :          2 :         word0(&eps) -= (P-1)*Exp_msk1;
        2479         [ -  + ]:          2 :         if (ilim == 0) {
        2480                 :          0 :             S = mhi = 0;
        2481                 :          0 :             dval(&u) -= 5.;
        2482         [ #  # ]:          0 :             if (dval(&u) > dval(&eps))
        2483                 :          0 :                 goto one_digit;
        2484         [ #  # ]:          0 :             if (dval(&u) < -dval(&eps))
        2485                 :          0 :                 goto no_digits;
        2486                 :          0 :             goto fast_failed;
        2487                 :            :         }
        2488         [ -  + ]:          2 :         if (leftright) {
        2489                 :            :             /* Use Steele & White method of only
        2490                 :            :              * generating digits needed.
        2491                 :            :              */
        2492                 :          0 :             dval(&eps) = 0.5/tens[ilim-1] - dval(&eps);
        2493                 :          0 :             for(i = 0;;) {
        2494                 :          0 :                 L = (Long)dval(&u);
        2495                 :          0 :                 dval(&u) -= L;
        2496                 :          0 :                 *s++ = '0' + (int)L;
        2497         [ #  # ]:          0 :                 if (dval(&u) < dval(&eps))
        2498                 :          0 :                     goto ret1;
        2499         [ #  # ]:          0 :                 if (1. - dval(&u) < dval(&eps))
        2500                 :          0 :                     goto bump_up;
        2501         [ #  # ]:          0 :                 if (++i >= ilim)
        2502                 :          0 :                     break;
        2503                 :          0 :                 dval(&eps) *= 10.;
        2504                 :          0 :                 dval(&u) *= 10.;
        2505                 :            :             }
        2506                 :            :         }
        2507                 :            :         else {
        2508                 :            :             /* Generate ilim digits, then fix them up. */
        2509                 :          2 :             dval(&eps) *= tens[ilim-1];
        2510                 :          6 :             for(i = 1;; i++, dval(&u) *= 10.) {
        2511                 :          6 :                 L = (Long)(dval(&u));
        2512         [ -  + ]:          6 :                 if (!(dval(&u) -= L))
        2513                 :          0 :                     ilim = i;
        2514                 :          6 :                 *s++ = '0' + (int)L;
        2515         [ +  + ]:          6 :                 if (i == ilim) {
        2516         [ -  + ]:          2 :                     if (dval(&u) > 0.5 + dval(&eps))
        2517                 :          0 :                         goto bump_up;
        2518         [ +  - ]:          2 :                     else if (dval(&u) < 0.5 - dval(&eps)) {
        2519         [ -  + ]:          2 :                         while(*--s == '0');
        2520                 :          2 :                         s++;
        2521                 :          2 :                         goto ret1;
        2522                 :            :                     }
        2523                 :          0 :                     break;
        2524                 :            :                 }
        2525                 :            :             }
        2526                 :            :         }
        2527                 :          0 :       fast_failed:
        2528                 :          0 :         s = s0;
        2529                 :          0 :         dval(&u) = dval(&d2);
        2530                 :          0 :         k = k0;
        2531                 :          0 :         ilim = ilim0;
        2532                 :            :     }
        2533                 :            :
        2534                 :            :     /* Do we have a "small" integer? */
        2535                 :            :
        2536   [ +  +  +  + ]:         56 :     if (be >= 0 && k <= Int_max) {
        2537                 :            :         /* Yes. */
        2538                 :         20 :         ds = tens[k];
        2539   [ -  +  -  - ]:         20 :         if (ndigits < 0 && ilim <= 0) {
        2540                 :          0 :             S = mhi = 0;
        2541   [ #  #  #  # ]:          0 :             if (ilim < 0 || dval(&u) <= 5*ds)
        2542                 :          0 :                 goto no_digits;
        2543                 :          0 :             goto one_digit;
        2544                 :            :         }
        2545                 :         40 :         for(i = 1;; i++, dval(&u) *= 10.) {
        2546                 :         40 :             L = (Long)(dval(&u) / ds);
        2547                 :         40 :             dval(&u) -= L*ds;
        2548                 :         40 :             *s++ = '0' + (int)L;
        2549         [ +  + ]:         40 :             if (!dval(&u)) {
        2550                 :         20 :                 break;
        2551                 :            :             }
        2552         [ -  + ]:         20 :             if (i == ilim) {
        2553                 :          0 :                 dval(&u) += dval(&u);
        2554   [ #  #  #  #  :          0 :                 if (dval(&u) > ds || (dval(&u) == ds && L & 1)) {
                       #  # ]
        2555                 :          0 :                   bump_up:
        2556         [ #  # ]:          0 :                     while(*--s == '9')
        2557         [ #  # ]:          0 :                         if (s == s0) {
        2558                 :          0 :                             k++;
        2559                 :          0 :                             *s = '0';
        2560                 :          0 :                             break;
        2561                 :            :                         }
        2562                 :          0 :                     ++*s++;
        2563                 :            :                 }
        2564                 :            :                 else {
        2565                 :            :                     /* Strip trailing zeros. This branch was missing from the
        2566                 :            :                        original dtoa.c, leading to surplus trailing zeros in
        2567                 :            :                        some cases. See bugs.python.org/issue40780. */
        2568   [ #  #  #  # ]:          0 :                     while (s > s0 && s[-1] == '0') {
        2569                 :          0 :                         --s;
        2570                 :            :                     }
        2571                 :            :                 }
        2572                 :          0 :                 break;
        2573                 :            :             }
        2574                 :            :         }
        2575                 :         20 :         goto ret1;
        2576                 :            :     }
        2577                 :            :
        2578                 :         36 :     m2 = b2;
        2579                 :         36 :     m5 = b5;
        2580         [ +  + ]:         36 :     if (leftright) {
        2581                 :         30 :         i =
        2582         [ -  + ]:         30 :             denorm ? be + (Bias + (P-1) - 1 + 1) :
        2583                 :         30 :             1 + P - bbits;
        2584                 :         30 :         b2 += i;
        2585                 :         30 :         s2 += i;
        2586                 :         30 :         mhi = i2b(1);
        2587         [ -  + ]:         30 :         if (mhi == NULL)
        2588                 :          0 :             goto failed_malloc;
        2589                 :            :     }
        2590   [ +  +  +  - ]:         36 :     if (m2 > 0 && s2 > 0) {
        2591                 :         29 :         i = m2 < s2 ? m2 : s2;
        2592                 :         29 :         b2 -= i;
        2593                 :         29 :         m2 -= i;
        2594                 :         29 :         s2 -= i;
        2595                 :            :     }
        2596         [ +  + ]:         36 :     if (b5 > 0) {
        2597         [ +  + ]:         23 :         if (leftright) {
        2598         [ +  - ]:         17 :             if (m5 > 0) {
        2599                 :         17 :                 mhi = pow5mult(mhi, m5);
        2600         [ -  + ]:         17 :                 if (mhi == NULL)
        2601                 :          0 :                     goto failed_malloc;
        2602                 :         17 :                 b1 = mult(mhi, b);
        2603                 :         17 :                 Bfree(b);
        2604                 :         17 :                 b = b1;
        2605         [ -  + ]:         17 :                 if (b == NULL)
        2606                 :          0 :                     goto failed_malloc;
        2607                 :            :             }
        2608         [ -  + ]:         17 :             if ((j = b5 - m5)) {
        2609                 :          0 :                 b = pow5mult(b, j);
        2610         [ #  # ]:          0 :                 if (b == NULL)
        2611                 :          0 :                     goto failed_malloc;
        2612                 :            :             }
        2613                 :            :         }
        2614                 :            :         else {
        2615                 :          6 :             b = pow5mult(b, b5);
        2616         [ -  + ]:          6 :             if (b == NULL)
        2617                 :          0 :                 goto failed_malloc;
        2618                 :            :         }
        2619                 :            :     }
        2620                 :         36 :     S = i2b(1);
        2621         [ -  + ]:         36 :     if (S == NULL)
        2622                 :          0 :         goto failed_malloc;
        2623         [ +  + ]:         36 :     if (s5 > 0) {
        2624                 :          6 :         S = pow5mult(S, s5);
        2625         [ -  + ]:          6 :         if (S == NULL)
        2626                 :          0 :             goto failed_malloc;
        2627                 :            :     }
        2628                 :            :
        2629                 :            :     /* Check for special case that d is a normalized power of 2. */
        2630                 :            :
        2631                 :         36 :     spec_case = 0;
        2632   [ +  +  -  + ]:         36 :     if ((mode < 2 || leftright)
        2633                 :            :         ) {
        2634   [ -  +  -  - ]:         30 :         if (!word1(&u) && !(word0(&u) & Bndry_mask)
        2635         [ #  # ]:          0 :             && word0(&u) & (Exp_mask & ~Exp_msk1)
        2636                 :            :             ) {
        2637                 :            :             /* The special case */
        2638                 :          0 :             b2 += Log2P;
        2639                 :          0 :             s2 += Log2P;
        2640                 :          0 :             spec_case = 1;
        2641                 :            :         }
        2642                 :            :     }
        2643                 :            :
        2644                 :            :     /* Arrange for convenient computation of quotients:
        2645                 :            :      * shift left if necessary so divisor has 4 leading 0 bits.
        2646                 :            :      *
        2647                 :            :      * Perhaps we should just compute leading 28 bits of S once
        2648                 :            :      * and for all and pass them and a shift to quorem, so it
        2649                 :            :      * can do shifts and ors to compute the numerator for q.
        2650                 :            :      */
        2651                 :            : #define iInc 28
        2652                 :         36 :     i = dshift(S, s2);
        2653                 :         36 :     b2 += i;
        2654                 :         36 :     m2 += i;
        2655                 :         36 :     s2 += i;
        2656         [ +  - ]:         36 :     if (b2 > 0) {
        2657                 :         36 :         b = lshift(b, b2);
        2658         [ -  + ]:         36 :         if (b == NULL)
        2659                 :          0 :             goto failed_malloc;
        2660                 :            :     }
        2661         [ +  - ]:         36 :     if (s2 > 0) {
        2662                 :         36 :         S = lshift(S, s2);
        2663         [ -  + ]:         36 :         if (S == NULL)
        2664                 :          0 :             goto failed_malloc;
        2665                 :            :     }
        2666         [ +  + ]:         36 :     if (k_check) {
        2667         [ +  + ]:         28 :         if (cmp(b,S) < 0) {
        2668                 :          2 :             k--;
        2669                 :          2 :             b = multadd(b, 10, 0);      /* we botched the k estimate */
        2670         [ -  + ]:          2 :             if (b == NULL)
        2671                 :          0 :                 goto failed_malloc;
        2672         [ +  - ]:          2 :             if (leftright) {
        2673                 :          2 :                 mhi = multadd(mhi, 10, 0);
        2674         [ -  + ]:          2 :                 if (mhi == NULL)
        2675                 :          0 :                     goto failed_malloc;
        2676                 :            :             }
        2677                 :          2 :             ilim = ilim1;
        2678                 :            :         }
        2679                 :            :     }
        2680   [ +  -  +  +  :         36 :     if (ilim <= 0 && (mode == 3 || mode == 5)) {
                       -  + ]
        2681         [ +  - ]:          6 :         if (ilim < 0) {
        2682                 :            :             /* no digits, fcvt style */
        2683                 :          6 :           no_digits:
        2684                 :          6 :             k = -1 - ndigits;
        2685                 :          6 :             goto ret;
        2686                 :            :         }
        2687                 :            :         else {
        2688                 :          0 :             S = multadd(S, 5, 0);
        2689         [ #  # ]:          0 :             if (S == NULL)
        2690                 :          0 :                 goto failed_malloc;
        2691         [ #  # ]:          0 :             if (cmp(b, S) <= 0)
        2692                 :          0 :                 goto no_digits;
        2693                 :            :         }
        2694                 :          0 :       one_digit:
        2695                 :          0 :         *s++ = '1';
        2696                 :          0 :         k++;
        2697                 :          0 :         goto ret;
        2698                 :            :     }
        2699         [ +  - ]:         30 :     if (leftright) {
        2700         [ +  - ]:         30 :         if (m2 > 0) {
        2701                 :         30 :             mhi = lshift(mhi, m2);
        2702         [ -  + ]:         30 :             if (mhi == NULL)
        2703                 :          0 :                 goto failed_malloc;
        2704                 :            :         }
        2705                 :            :
        2706                 :            :         /* Compute mlo -- check for special case
        2707                 :            :          * that d is a normalized power of 2.
        2708                 :            :          */
        2709                 :            :
        2710                 :         30 :         mlo = mhi;
        2711         [ -  + ]:         30 :         if (spec_case) {
        2712                 :          0 :             mhi = Balloc(mhi->k);
        2713         [ #  # ]:          0 :             if (mhi == NULL)
        2714                 :          0 :                 goto failed_malloc;
        2715                 :          0 :             Bcopy(mhi, mlo);
        2716                 :          0 :             mhi = lshift(mhi, Log2P);
        2717         [ #  # ]:          0 :             if (mhi == NULL)
        2718                 :          0 :                 goto failed_malloc;
        2719                 :            :         }
        2720                 :            :
        2721                 :        130 :         for(i = 1;;i++) {
        2722                 :        130 :             dig = quorem(b,S) + '0';
        2723                 :            :             /* Do we yet have the shortest decimal string
        2724                 :            :              * that will round to d?
        2725                 :            :              */
        2726                 :        130 :             j = cmp(b, mlo);
        2727                 :        130 :             delta = diff(S, mhi);
        2728         [ -  + ]:        130 :             if (delta == NULL)
        2729                 :          0 :                 goto failed_malloc;
        2730         [ +  - ]:        130 :             j1 = delta->sign ? 1 : cmp(b, delta);
        2731                 :        130 :             Bfree(delta);
        2732   [ -  +  -  -  :        130 :             if (j1 == 0 && mode != 1 && !(word1(&u) & 1)
                       -  - ]
        2733                 :            :                 ) {
        2734         [ #  # ]:          0 :                 if (dig == '9')
        2735                 :          0 :                     goto round_9_up;
        2736         [ #  # ]:          0 :                 if (j > 0)
        2737                 :          0 :                     dig++;
        2738                 :          0 :                 *s++ = dig;
        2739                 :          0 :                 goto ret;
        2740                 :            :             }
        2741   [ +  +  -  +  :        130 :             if (j < 0 || (j == 0 && mode != 1
                       -  - ]
        2742         [ #  # ]:          0 :                           && !(word1(&u) & 1)
        2743                 :            :                     )) {
        2744   [ +  +  -  + ]:         22 :                 if (!b->x[0] && b->wds <= 1) {
        2745                 :          0 :                     goto accept_dig;
        2746                 :            :                 }
        2747         [ -  + ]:         22 :                 if (j1 > 0) {
        2748                 :          0 :                     b = lshift(b, 1);
        2749         [ #  # ]:          0 :                     if (b == NULL)
        2750                 :          0 :                         goto failed_malloc;
        2751                 :          0 :                     j1 = cmp(b, S);
        2752   [ #  #  #  #  :          0 :                     if ((j1 > 0 || (j1 == 0 && dig & 1))
                       #  # ]
        2753         [ #  # ]:          0 :                         && dig++ == '9')
        2754                 :          0 :                         goto round_9_up;
        2755                 :            :                 }
        2756                 :         22 :               accept_dig:
        2757                 :         22 :                 *s++ = dig;
        2758                 :         22 :                 goto ret;
        2759                 :            :             }
        2760         [ +  + ]:        108 :             if (j1 > 0) {
        2761         [ +  + ]:          8 :                 if (dig == '9') { /* possible if i == 1 */
        2762                 :          1 :                   round_9_up:
        2763                 :          1 :                     *s++ = '9';
        2764                 :          1 :                     goto roundoff;
        2765                 :            :                 }
        2766                 :          7 :                 *s++ = dig + 1;
        2767                 :          7 :                 goto ret;
        2768                 :            :             }
        2769                 :        100 :             *s++ = dig;
        2770         [ -  + ]:        100 :             if (i == ilim)
        2771                 :          0 :                 break;
        2772                 :        100 :             b = multadd(b, 10, 0);
        2773         [ -  + ]:        100 :             if (b == NULL)
        2774                 :          0 :                 goto failed_malloc;
        2775         [ +  - ]:        100 :             if (mlo == mhi) {
        2776                 :        100 :                 mlo = mhi = multadd(mhi, 10, 0);
        2777         [ -  + ]:        100 :                 if (mlo == NULL)
        2778                 :          0 :                     goto failed_malloc;
        2779                 :            :             }
        2780                 :            :             else {
        2781                 :          0 :                 mlo = multadd(mlo, 10, 0);
        2782         [ #  # ]:          0 :                 if (mlo == NULL)
        2783                 :          0 :                     goto failed_malloc;
        2784                 :          0 :                 mhi = multadd(mhi, 10, 0);
        2785         [ #  # ]:          0 :                 if (mhi == NULL)
        2786                 :          0 :                     goto failed_malloc;
        2787                 :            :             }
        2788                 :            :         }
        2789                 :            :     }
        2790                 :            :     else
        2791                 :          0 :         for(i = 1;; i++) {
        2792                 :          0 :             *s++ = dig = quorem(b,S) + '0';
        2793   [ #  #  #  # ]:          0 :             if (!b->x[0] && b->wds <= 1) {
        2794                 :          0 :                 goto ret;
        2795                 :            :             }
        2796         [ #  # ]:          0 :             if (i >= ilim)
        2797                 :          0 :                 break;
        2798                 :          0 :             b = multadd(b, 10, 0);
        2799         [ #  # ]:          0 :             if (b == NULL)
        2800                 :          0 :                 goto failed_malloc;
        2801                 :            :         }
        2802                 :            :
        2803                 :            :     /* Round off last digit */
        2804                 :            :
        2805                 :          0 :     b = lshift(b, 1);
        2806         [ #  # ]:          0 :     if (b == NULL)
        2807                 :          0 :         goto failed_malloc;
        2808                 :          0 :     j = cmp(b, S);
        2809   [ #  #  #  #  :          0 :     if (j > 0 || (j == 0 && dig & 1)) {
                       #  # ]
        2810                 :          0 :       roundoff:
        2811         [ +  - ]:          1 :         while(*--s == '9')
        2812         [ +  - ]:          1 :             if (s == s0) {
        2813                 :          1 :                 k++;
        2814                 :          1 :                 *s++ = '1';
        2815                 :          1 :                 goto ret;
        2816                 :            :             }
        2817                 :          0 :         ++*s++;
        2818                 :            :     }
        2819                 :            :     else {
        2820         [ #  # ]:          0 :         while(*--s == '0');
        2821                 :          0 :         s++;
        2822                 :            :     }
        2823                 :         36 :   ret:
        2824                 :         36 :     Bfree(S);
        2825         [ +  + ]:         36 :     if (mhi) {
        2826   [ +  -  -  + ]:         30 :         if (mlo && mlo != mhi)
        2827                 :          0 :             Bfree(mlo);
        2828                 :         30 :         Bfree(mhi);
        2829                 :            :     }
        2830                 :          6 :   ret1:
        2831                 :         58 :     Bfree(b);
        2832                 :         58 :     *s = 0;
        2833                 :         58 :     *decpt = k + 1;
        2834         [ +  - ]:         58 :     if (rve)
        2835                 :         58 :         *rve = s;
        2836                 :         58 :     return s0;
        2837                 :          0 :   failed_malloc:
        2838         [ #  # ]:          0 :     if (S)
        2839                 :          0 :         Bfree(S);
        2840   [ #  #  #  # ]:          0 :     if (mlo && mlo != mhi)
        2841                 :          0 :         Bfree(mlo);
        2842         [ #  # ]:          0 :     if (mhi)
        2843                 :          0 :         Bfree(mhi);
        2844         [ #  # ]:          0 :     if (b)
        2845                 :          0 :         Bfree(b);
        2846         [ #  # ]:          0 :     if (s0)
        2847                 :          0 :         _Py_dg_freedtoa(s0);
        2848                 :          0 :     return NULL;
        2849                 :            : }
        2850                 :            : #ifdef __cplusplus
        2851                 :            : }
        2852                 :            : #endif
        2853                 :            :
        2854                 :            : #endif  // _PY_SHORT_FLOAT_REPR == 1

Generated by: LCOV version 1.14