]>
git.saurik.com Git - apple/libc.git/blob - gdtoa/FreeBSD/gdtoa-gdtoa.c
1 /****************************************************************
3 The author of this software is David M. Gay.
5 Copyright (C) 1998, 1999 by Lucent Technologies
8 Permission to use, copy, modify, and distribute this software and
9 its documentation for any purpose and without fee is hereby
10 granted, provided that the above copyright notice appear in all
11 copies and that both that the copyright notice and this
12 permission notice and warranty disclaimer appear in supporting
13 documentation, and that the name of Lucent or any of its entities
14 not be used in advertising or publicity pertaining to
15 distribution of the software without specific, written prior
18 LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
19 INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
20 IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
21 SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
22 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
23 IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
24 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
27 ****************************************************************/
29 /* Please send bug reports to
31 Bell Laboratories, Room 2C-463
33 Murray Hill, NJ 07974-0636
42 bitstob(bits
, nbits
, bbits
) ULong
*bits
; int nbits
; int *bbits
;
44 bitstob(ULong
*bits
, int nbits
, int *bbits
)
62 be
= bits
+ ((nbits
- 1) >> kshift
);
65 *x
++ = *bits
& ALL_ON
;
67 *x
++ = (*bits
>> 16) & ALL_ON
;
69 } while(++bits
<= be
);
78 *bbits
= i
*ULbits
+ 32 - hi0bits(b
->x
[i
]);
83 /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
85 * Inspired by "How to Print Floating-Point Numbers Accurately" by
86 * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101].
89 * 1. Rather than iterating, we use a simple numeric overestimate
90 * to determine k = floor(log10(d)). We scale relevant
91 * quantities using O(log2(k)) rather than O(k) multiplications.
92 * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
93 * try to generate digits strictly left to right. Instead, we
94 * compute with fewer bits and propagate the carry if necessary
95 * when rounding the final digit up. This is often faster.
96 * 3. Under the assumption that input will be rounded nearest,
97 * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
98 * That is, we allow equality in stopping tests when the
99 * round-nearest rule will give the same floating-point value
100 * as would satisfaction of the stopping test with strict
102 * 4. We remove common factors of powers of 2 from relevant
104 * 5. When converting floating-point integers less than 1e16,
105 * we use floating-point arithmetic rather than resorting
106 * to multiple-precision integers.
107 * 6. When asked to produce fewer than 15 digits, we first try
108 * to get by with floating-point arithmetic; we resort to
109 * multiple-precision integer arithmetic only if we cannot
110 * guarantee that the floating-point calculation has given
111 * the correctly rounded result. For k requested digits and
112 * "uniformly" distributed input, the probability is
113 * something like 10^(k-15) that we must resort to the Long
120 (fpi
, be
, bits
, kindp
, mode
, ndigits
, decpt
, rve
)
121 FPI
*fpi
; int be
; ULong
*bits
;
122 int *kindp
, mode
, ndigits
, *decpt
; char **rve
;
124 (FPI
*fpi
, int be
, ULong
*bits
, int *kindp
, int mode
, int ndigits
, int *decpt
, char **rve
)
127 /* Arguments ndigits and decpt are similar to the second and third
128 arguments of ecvt and fcvt; trailing zeros are suppressed from
129 the returned string. If not null, *rve is set to point
130 to the end of the return value. If d is +-Infinity or NaN,
131 then *decpt is set to 9999.
134 0 ==> shortest string that yields d when read in
135 and rounded to nearest.
136 1 ==> like 0, but with Steele & White stopping rule;
137 e.g. with IEEE P754 arithmetic , mode 0 gives
138 1e23 whereas mode 1 gives 9.999999999999999e22.
139 2 ==> max(1,ndigits) significant digits. This gives a
140 return value similar to that of ecvt, except
141 that trailing zeros are suppressed.
142 3 ==> through ndigits past the decimal point. This
143 gives a return value similar to that from fcvt,
144 except that trailing zeros are suppressed, and
145 ndigits can be negative.
146 4-9 should give the same return values as 2-3, i.e.,
147 4 <= mode <= 9 ==> same return as mode
148 2 + (mode & 1). These modes are mainly for
149 debugging; often they run slower but sometimes
150 faster than modes 2-3.
151 4,5,8,9 ==> left-to-right digit generation.
152 6-9 ==> don't try fast floating-point estimate
155 Values of mode other than 0-9 are treated as mode 0.
157 Sufficient space is allocated to the return value
158 to hold the suppressed trailing zeros.
161 int bbits
, b2
, b5
, be0
, dig
, i
, ieps
, ilim
, ilim0
, ilim1
, inex
;
162 int j
, j1
, k
, k0
, k_check
, kind
, leftright
, m2
, m5
, nbits
;
163 int rdir
, s2
, s5
, spec_case
, try_quick
;
165 Bigint
*b
, *b1
, *delta
, *mlo
, *mhi
, *mhi1
, *S
;
166 double d
, d2
, ds
, eps
;
169 #ifndef MULTIPLE_THREADS
171 freedtoa(dtoa_result
);
176 kind
= *kindp
&= ~STRTOG_Inexact
;
177 switch(kind
& STRTOG_Retmask
) {
181 case STRTOG_Denormal
:
183 case STRTOG_Infinite
:
185 return nrv_alloc("Infinity", rve
, 8);
188 return nrv_alloc("NaN", rve
, 3);
192 b
= bitstob(bits
, nbits
= fpi
->nbits
, &bbits
);
194 if ( (i
= trailz(b
)) !=0) {
203 return nrv_alloc("0", rve
, 1);
206 dval(d
) = b2d(b
, &i
);
208 word0(d
) &= Frac_mask1
;
211 if ( (j
= 11 - hi0bits(word0(d
) & Frac_mask
)) !=0)
215 /* log(x) ~=~ log(1.5) + (x-1.5)/1.5
216 * log10(x) = log(x) / log(10)
217 * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
218 * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2)
220 * This suggests computing an approximation k to log10(d) by
222 * k = (i - Bias)*0.301029995663981
223 * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
225 * We want k to be too large rather than too small.
226 * The error in the first-order Taylor series approximation
227 * is in our favor, so we just round up the constant enough
228 * to compensate for any error in the multiplication of
229 * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
230 * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
231 * adding 1e-13 to the constant term more than suffices.
232 * Hence we adjust the constant term to 0.1760912590558.
233 * (We could get a more accurate k by invoking log10,
234 * but this is probably not worthwhile.)
240 ds
= (dval(d
)-1.5)*0.289529654602168 + 0.1760912590558 + i
*0.301029995663981;
242 /* correct assumption about exponent range */
249 if (ds
< 0. && ds
!= k
)
250 k
--; /* want k = floor(ds) */
254 if ( (j1
= j
& 3) !=0)
256 word0(d
) += j
<< Exp_shift
- 2 & Exp_mask
;
258 word0(d
) += (be
+ bbits
- 1) << Exp_shift
;
260 if (k
>= 0 && k
<= Ten_pmax
) {
261 if (dval(d
) < tens
[k
])
284 if (mode
< 0 || mode
> 9)
296 i
= (int)(nbits
* .30103) + 3;
305 ilim
= ilim1
= i
= ndigits
;
317 s
= s0
= rv_alloc(i
);
319 if ( (rdir
= fpi
->rounding
- 1) !=0) {
322 if (kind
& STRTOG_Neg
)
326 /* Now rdir = 0 ==> round near, 1 ==> round up, 2 ==> round down. */
328 if (ilim
>= 0 && ilim
<= Quick_max
&& try_quick
&& !rdir
329 #ifndef IMPRECISE_INEXACT
334 /* Try to get by with floating-point arithmetic. */
339 if ( (j
= 11 - hi0bits(word0(d
) & Frac_mask
)) !=0)
344 ieps
= 2; /* conservative */
349 /* prevent overflows */
351 dval(d
) /= bigtens
[n_bigtens
-1];
354 for(; j
; j
>>= 1, i
++)
362 if ( (j1
= -k
) !=0) {
363 dval(d
) *= tens
[j1
& 0xf];
364 for(j
= j1
>> 4; j
; j
>>= 1, i
++)
367 dval(d
) *= bigtens
[i
];
371 if (k_check
&& dval(d
) < 1. && ilim
> 0) {
379 dval(eps
) = ieps
*dval(d
) + 7.;
380 word0(eps
) -= (P
-1)*Exp_msk1
;
384 if (dval(d
) > dval(eps
))
386 if (dval(d
) < -dval(eps
))
392 /* Use Steele & White method of only
393 * generating digits needed.
395 dval(eps
) = ds
*0.5/tens
[ilim
-1] - dval(eps
);
397 L
= (Long
)(dval(d
)/ds
);
400 if (dval(d
) < dval(eps
)) {
402 inex
= STRTOG_Inexlo
;
405 if (ds
- dval(d
) < dval(eps
))
415 /* Generate ilim digits, then fix them up. */
416 dval(eps
) *= tens
[ilim
-1];
417 for(i
= 1;; i
++, dval(d
) *= 10.) {
418 if ( (L
= (Long
)(dval(d
)/ds
)) !=0)
423 if (dval(d
) > ds
+ dval(eps
))
425 else if (dval(d
) < ds
- dval(eps
)) {
429 inex
= STRTOG_Inexlo
;
445 /* Do we have a "small" integer? */
447 if (be
>= 0 && k
<= Int_max
) {
450 if (ndigits
< 0 && ilim
<= 0) {
452 if (ilim
< 0 || dval(d
) <= 5*ds
)
456 for(i
= 1;; i
++, dval(d
) *= 10.) {
459 #ifdef Check_FLT_ROUNDS
460 /* If FLT_ROUNDS == 2, L will usually be high by 1 */
473 inex
= STRTOG_Inexlo
;
477 if (dval(d
) > ds
|| dval(d
) == ds
&& L
& 1) {
479 inex
= STRTOG_Inexhi
;
489 inex
= STRTOG_Inexlo
;
502 if (be
- i
++ < fpi
->emin
)
504 i
= be
- fpi
->emin
+ 1;
515 if ((i
= ilim
) < 0) {
524 if (m2
> 0 && s2
> 0) {
525 i
= m2
< s2
? m2
: s2
;
533 mhi
= pow5mult(mhi
, m5
);
538 if ( (j
= b5
- m5
) !=0)
548 /* Check for special case that d is a normalized power of 2. */
552 if (bbits
== 1 && be0
> fpi
->emin
+ 1) {
553 /* The special case */
560 /* Arrange for convenient computation of quotients:
561 * shift left if necessary so divisor has 4 leading 0 bits.
563 * Perhaps we should just compute leading 28 bits of S once
564 * and for all and pass them and a shift to quorem, so it
565 * can do shifts and ors to compute the numerator for q.
568 if ( (i
= ((s5
? 32 - hi0bits(S
->x
[S
->wds
-1]) : 1) + s2
) & 0x1f) !=0)
571 if ( (i
= ((s5
? 32 - hi0bits(S
->x
[S
->wds
-1]) : 1) + s2
) & 0xf) !=0)
593 b
= multadd(b
, 10, 0); /* we botched the k estimate */
595 mhi
= multadd(mhi
, 10, 0);
599 if (ilim
<= 0 && mode
> 2) {
600 if (ilim
< 0 || cmp(b
,S
= multadd(S
,5,0)) <= 0) {
601 /* no digits, fcvt style */
604 inex
= STRTOG_Inexlo
;
608 inex
= STRTOG_Inexhi
;
615 mhi
= lshift(mhi
, m2
);
617 /* Compute mlo -- check for special case
618 * that d is a normalized power of 2.
623 mhi
= Balloc(mhi
->k
);
625 mhi
= lshift(mhi
, 1);
629 dig
= quorem(b
,S
) + '0';
630 /* Do we yet have the shortest decimal string
631 * that will round to d?
634 delta
= diff(S
, mhi
);
635 j1
= delta
->sign
? 1 : cmp(b
, delta
);
638 if (j1
== 0 && !mode
&& !(bits
[0] & 1) && !rdir
) {
642 if (b
->wds
> 1 || b
->x
[0])
643 inex
= STRTOG_Inexlo
;
647 inex
= STRTOG_Inexhi
;
653 if (j
< 0 || j
== 0 && !mode
658 if (rdir
&& (b
->wds
> 1 || b
->x
[0])) {
660 inex
= STRTOG_Inexlo
;
663 while (cmp(S
,mhi
) > 0) {
665 mhi1
= multadd(mhi
, 10, 0);
669 b
= multadd(b
, 10, 0);
670 dig
= quorem(b
,S
) + '0';
674 inex
= STRTOG_Inexhi
;
680 if ((j1
> 0 || j1
== 0 && dig
& 1)
683 inex
= STRTOG_Inexhi
;
685 if (b
->wds
> 1 || b
->x
[0])
686 inex
= STRTOG_Inexlo
;
691 if (j1
> 0 && rdir
!= 2) {
692 if (dig
== '9') { /* possible if i == 1 */
695 inex
= STRTOG_Inexhi
;
698 inex
= STRTOG_Inexhi
;
705 b
= multadd(b
, 10, 0);
707 mlo
= mhi
= multadd(mhi
, 10, 0);
709 mlo
= multadd(mlo
, 10, 0);
710 mhi
= multadd(mhi
, 10, 0);
716 *s
++ = dig
= quorem(b
,S
) + '0';
719 b
= multadd(b
, 10, 0);
722 /* Round off last digit */
725 if (rdir
== 2 || b
->wds
<= 1 && !b
->x
[0])
731 if (j
> 0 || j
== 0 && dig
& 1) {
733 inex
= STRTOG_Inexhi
;
744 if (b
->wds
> 1 || b
->x
[0])
745 inex
= STRTOG_Inexlo
;
752 if (mlo
&& mlo
!= mhi
)