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