summaryrefslogtreecommitdiff
path: root/missing/dtoa.c
diff options
context:
space:
mode:
Diffstat (limited to 'missing/dtoa.c')
-rw-r--r--missing/dtoa.c334
1 files changed, 213 insertions, 121 deletions
diff --git a/missing/dtoa.c b/missing/dtoa.c
index cbee13ee81..ba8cd46ebd 100644
--- a/missing/dtoa.c
+++ b/missing/dtoa.c
@@ -98,17 +98,6 @@
* if memory is available and otherwise does something you deem
* appropriate. If MALLOC is undefined, malloc will be invoked
* directly -- and assumed always to succeed.
- * #define Omit_Private_Memory to omit logic (added Jan. 1998) for making
- * memory allocations from a private pool of memory when possible.
- * When used, the private pool is PRIVATE_MEM bytes long: 2304 bytes,
- * unless #defined to be a different length. This default length
- * suffices to get rid of MALLOC calls except for unusual cases,
- * such as decimal-to-binary conversion of a very long string of
- * digits. The longest string dtoa can return is about 751 bytes
- * long. For conversions by strtod of strings of 800 digits and
- * all dtoa conversions in single-threaded executions with 8-byte
- * pointers, PRIVATE_MEM >= 7400 appears to suffice; with 4-byte
- * pointers, PRIVATE_MEM >= 7112 appears adequate.
* #define INFNAN_CHECK on IEEE systems to cause strtod to check for
* Infinity and NaN (case insensitively). On some systems (e.g.,
* some HP systems), it may be necessary to #define NAN_WORD0
@@ -183,15 +172,22 @@
#undef Long
#undef ULong
-#if SIZEOF_INT == 4
+#include <assert.h>
+#include <limits.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#if (INT_MAX >> 30) && !(INT_MAX >> 31)
#define Long int
#define ULong unsigned int
-#elif SIZEOF_LONG == 4
+#elif (LONG_MAX >> 30) && !(LONG_MAX >> 31)
#define Long long int
#define ULong unsigned long int
+#else
+#error No 32bit integer
#endif
-#if HAVE_LONG_LONG
+#if defined(HAVE_LONG_LONG) && (HAVE_LONG_LONG)
#define Llong LONG_LONG
#else
#define NO_LONG_LONG
@@ -202,6 +198,11 @@
#define Bug(x) {fprintf(stderr, "%s\n", (x)); exit(EXIT_FAILURE);}
#endif
+#ifndef ISDIGIT
+#include <ctype.h>
+#define ISDIGIT(c) isdigit(c)
+#endif
+#include <errno.h>
#include <stdlib.h>
#include <string.h>
@@ -209,23 +210,41 @@
#include <locale.h>
#endif
+#if defined(HAVE_STDCKDINT_H) || !defined(__has_include)
+#elif __has_include(<stdckdint.h>)
+# define HAVE_STDCKDINT_H 1
+#endif
+#ifdef HAVE_STDCKDINT_H
+# include <stdckdint.h>
+#endif
+
+#if !defined(ckd_add)
+static inline int /* bool */
+ckd_add(int *result, int x, int y)
+{
+ if (x < 0) {
+ if (y < INT_MIN - x) return 1;
+ }
+ else if (x > 0) {
+ if (y > INT_MAX - x) return 1;
+ }
+ *result = x + y;
+ return 0;
+}
+#endif
+
#ifdef MALLOC
extern void *MALLOC(size_t);
#else
-#define MALLOC xmalloc
+#define MALLOC malloc
#endif
#ifdef FREE
extern void FREE(void*);
#else
-#define FREE xfree
-#endif
-
-#ifndef Omit_Private_Memory
-#ifndef PRIVATE_MEM
-#define PRIVATE_MEM 2304
+#define FREE free
#endif
-#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
-static double private_mem[PRIVATE_mem], *pmem_next = private_mem;
+#ifndef NO_SANITIZE
+#define NO_SANITIZE(x, y) y
#endif
#undef IEEE_Arith
@@ -280,7 +299,7 @@ extern "C" {
#endif
#ifndef hexdigit
-static const char hexdigits[] = "0123456789abcdef0123456789ABCDEF";
+static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF";
#endif
#if defined(IEEE_LITTLE_ENDIAN) + defined(IEEE_BIG_ENDIAN) + defined(VAX) + defined(IBM) != 1
@@ -489,6 +508,19 @@ extern double rnd_prod(double, double), rnd_quot(double, double);
#define FREE_DTOA_LOCK(n) /*unused right now*/
#endif
+#ifndef ATOMIC_PTR_CAS
+#define ATOMIC_PTR_CAS(var, old, new) ((var) = (new), (void *)(old))
+#endif
+#ifndef LIKELY
+#define LIKELY(x) (x)
+#endif
+#ifndef UNLIKELY
+#define UNLIKELY(x) (x)
+#endif
+#ifndef ASSUME
+#define ASSUME(x) (void)(x)
+#endif
+
#define Kmax 15
struct Bigint {
@@ -499,57 +531,29 @@ struct Bigint {
typedef struct Bigint Bigint;
-static Bigint *freelist[Kmax+1];
-
static Bigint *
Balloc(int k)
{
int x;
Bigint *rv;
-#ifndef Omit_Private_Memory
- size_t len;
-#endif
- ACQUIRE_DTOA_LOCK(0);
- if (k <= Kmax && (rv = freelist[k]) != 0) {
- freelist[k] = rv->next;
- }
- else {
- x = 1 << k;
-#ifdef Omit_Private_Memory
- rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
-#else
- len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
- /sizeof(double);
- if (k <= Kmax && pmem_next - private_mem + len <= PRIVATE_mem) {
- rv = (Bigint*)pmem_next;
- pmem_next += len;
- }
- else
- rv = (Bigint*)MALLOC(len*sizeof(double));
-#endif
- rv->k = k;
- rv->maxwds = x;
- }
- FREE_DTOA_LOCK(0);
+ x = 1 << k;
+ rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
+ if (!rv) return NULL;
+ rv->k = k;
+ rv->maxwds = x;
rv->sign = rv->wds = 0;
return rv;
}
static void
-Bfree(Bigint *v)
+Bclear(Bigint **vp)
{
- if (v) {
- if (v->k > Kmax) {
- FREE(v);
- return;
- }
- ACQUIRE_DTOA_LOCK(0);
- v->next = freelist[v->k];
- freelist[v->k] = v;
- FREE_DTOA_LOCK(0);
- }
+ Bigint *v = *vp;
+ *vp = NULL;
+ if (v) FREE(v);
}
+#define Bfree(v) Bclear(&(v))
#define Bcopy(x,y) memcpy((char *)&(x)->sign, (char *)&(y)->sign, \
(y)->wds*sizeof(Long) + 2*sizeof(int))
@@ -595,6 +599,10 @@ multadd(Bigint *b, int m, int a) /* multiply by m and add a */
if (carry) {
if (wds >= b->maxwds) {
b1 = Balloc(b->k+1);
+ if (!b1) {
+ Bfree(b);
+ return NULL;
+ }
Bcopy(b1, b);
Bfree(b);
b = b1;
@@ -616,10 +624,12 @@ s2b(const char *s, int nd0, int nd, ULong y9)
for (k = 0, y = 1; x > y; y <<= 1, k++) ;
#ifdef Pack_32
b = Balloc(k);
+ if (!b) return NULL;
b->x[0] = y9;
b->wds = 1;
#else
b = Balloc(k+1);
+ if (!b) return NULL;
b->x[0] = y9 & 0xffff;
b->wds = (b->x[1] = y9 >> 16) ? 2 : 1;
#endif
@@ -629,13 +639,16 @@ s2b(const char *s, int nd0, int nd, ULong y9)
s += 9;
do {
b = multadd(b, 10, *s++ - '0');
+ if (!b) return NULL;
} while (++i < nd0);
s++;
}
else
s += 10;
- for (; i < nd; i++)
+ for (; i < nd; i++) {
b = multadd(b, 10, *s++ - '0');
+ if (!b) return NULL;
+ }
return b;
}
@@ -717,11 +730,14 @@ i2b(int i)
Bigint *b;
b = Balloc(1);
+ if (!b) return NULL;
b->x[0] = i;
b->wds = 1;
return b;
}
+#define Bzero_p(b) (!(b)->x[0] && (b)->wds <= 1)
+
static Bigint *
mult(Bigint *a, Bigint *b)
{
@@ -738,6 +754,14 @@ mult(Bigint *a, Bigint *b)
#endif
#endif
+ if (Bzero_p(a) || Bzero_p(b)) {
+ c = Balloc(0);
+ if (!c) return NULL;
+ c->wds = 1;
+ c->x[0] = 0;
+ return c;
+ }
+
if (a->wds < b->wds) {
c = a;
a = b;
@@ -750,6 +774,7 @@ mult(Bigint *a, Bigint *b)
if (wc > a->maxwds)
k++;
c = Balloc(k);
+ if (!c) return NULL;
for (x = c->x, xa = x + wc; x < xa; x++)
*x = 0;
xa = a->x;
@@ -830,48 +855,46 @@ pow5mult(Bigint *b, int k)
{
Bigint *b1, *p5, *p51;
int i;
- static int p05[3] = { 5, 25, 125 };
+ static const int p05[3] = { 5, 25, 125 };
- if ((i = k & 3) != 0)
+ if ((i = k & 3) != 0) {
b = multadd(b, p05[i-1], 0);
+ if (!b) return NULL;
+ }
+
+#define b_cache(var, addr, new_expr) \
+ if ((var = addr) != 0) {} else { \
+ Bigint *tmp = 0; \
+ ACQUIRE_DTOA_LOCK(1); \
+ if (!(var = addr) && (var = (new_expr)) != 0) { \
+ var->next = 0; \
+ tmp = ATOMIC_PTR_CAS(addr, NULL, var); \
+ } \
+ FREE_DTOA_LOCK(1); \
+ if (UNLIKELY(tmp)) { \
+ Bfree(var); \
+ var = tmp; \
+ } \
+ else if (!var) { \
+ Bfree(b); \
+ return NULL; \
+ } \
+ }
if (!(k >>= 2))
return b;
- if (!(p5 = p5s)) {
- /* first time */
-#ifdef MULTIPLE_THREADS
- ACQUIRE_DTOA_LOCK(1);
- if (!(p5 = p5s)) {
- p5 = p5s = i2b(625);
- p5->next = 0;
- }
- FREE_DTOA_LOCK(1);
-#else
- p5 = p5s = i2b(625);
- p5->next = 0;
-#endif
- }
+ /* first time */
+ b_cache(p5, p5s, i2b(625));
for (;;) {
if (k & 1) {
b1 = mult(b, p5);
Bfree(b);
b = b1;
+ if (!b) return NULL;
}
if (!(k >>= 1))
break;
- if (!(p51 = p5->next)) {
-#ifdef MULTIPLE_THREADS
- ACQUIRE_DTOA_LOCK(1);
- if (!(p51 = p5->next)) {
- p51 = p5->next = mult(p5,p5);
- p51->next = 0;
- }
- FREE_DTOA_LOCK(1);
-#else
- p51 = p5->next = mult(p5,p5);
- p51->next = 0;
-#endif
- }
+ b_cache(p51, p5->next, mult(p5, p5));
p5 = p51;
}
return b;
@@ -884,6 +907,8 @@ lshift(Bigint *b, int k)
Bigint *b1;
ULong *x, *x1, *xe, z;
+ if (!k || Bzero_p(b)) return b;
+
#ifdef Pack_32
n = k >> 5;
#else
@@ -894,6 +919,10 @@ lshift(Bigint *b, int k)
for (i = b->maxwds; n1 > i; i <<= 1)
k1++;
b1 = Balloc(k1);
+ if (!b1) {
+ Bfree(b);
+ return NULL;
+ }
x1 = b1->x;
for (i = 0; i < n; i++)
*x1++ = 0;
@@ -979,6 +1008,7 @@ diff(Bigint *a, Bigint *b)
i = cmp(a,b);
if (!i) {
c = Balloc(0);
+ if (!c) return NULL;
c->wds = 1;
c->x[0] = 0;
return c;
@@ -992,6 +1022,7 @@ diff(Bigint *a, Bigint *b)
else
i = 0;
c = Balloc(a->k);
+ if (!c) return NULL;
c->sign = i;
wa = a->wds;
xa = a->x;
@@ -1177,6 +1208,7 @@ d2b(double d_, int *e, int *bits)
#else
b = Balloc(2);
#endif
+ if (!b) return NULL;
x = b->x;
z = d0 & Frac_mask;
@@ -1497,9 +1529,10 @@ break2:
aadj = 1.0;
nd0 = -4;
- if (!*++s || !(s1 = strchr(hexdigit, *s))) goto ret0;
+ if (!*++s || (!(s1 = strchr(hexdigit, *s)) && *s != '.')) goto ret0;
if (*s == '0') {
while (*++s == '0');
+ if (!*s) goto ret;
s1 = strchr(hexdigit, *s);
}
if (s1 != NULL) {
@@ -1510,9 +1543,7 @@ break2:
} while (*++s && (s1 = strchr(hexdigit, *s)));
}
- if (*s == '.') {
- dsign = 1;
- if (!*++s || !(s1 = strchr(hexdigit, *s))) goto ret0;
+ if ((*s == '.') && *++s && (s1 = strchr(hexdigit, *s))) {
if (nd0 < 0) {
while (*s == '0') {
s++;
@@ -1522,14 +1553,11 @@ break2:
for (; *s && (s1 = strchr(hexdigit, *s)); ++s) {
adj += aadj * ((s1 - hexdigit) & 15);
if ((aadj /= 16) == 0.0) {
- while (strchr(hexdigit, *++s));
+ while (*++s && strchr(hexdigit, *s));
break;
}
}
}
- else {
- dsign = 0;
- }
if (*s == 'P' || *s == 'p') {
dsign = 0x2C - *++s; /* +: 2B, -: 2D */
@@ -1552,9 +1580,6 @@ break2:
} while ('0' <= c && c <= '9');
nd0 += nd * dsign;
}
- else {
- if (dsign) goto ret0;
- }
dval(rv) = ldexp(adj, nd0);
goto ret;
}
@@ -1591,9 +1616,9 @@ break2:
}
#endif
if (c == '.') {
- if (!ISDIGIT(s[1]))
- goto dig_done;
c = *++s;
+ if (!ISDIGIT(c))
+ goto dig_done;
if (!nd) {
for (; c == '0'; c = *++s)
nz++;
@@ -1934,12 +1959,16 @@ undfl:
/* Put digits into bd: true value = bd * 10^e */
bd0 = s2b(s0, nd0, nd, y);
+ if (!bd0) goto ret;
for (;;) {
bd = Balloc(bd0->k);
+ if (!bd) goto retfree;
Bcopy(bd, bd0);
bb = d2b(dval(rv), &bbe, &bbbits); /* rv = bb * 2^bbe */
+ if (!bb) goto retfree;
bs = i2b(1);
+ if (!bs) goto retfree;
if (e >= 0) {
bb2 = bb5 = 0;
@@ -1996,19 +2025,30 @@ undfl:
}
if (bb5 > 0) {
bs = pow5mult(bs, bb5);
+ if (!bs) goto retfree;
bb1 = mult(bs, bb);
Bfree(bb);
bb = bb1;
+ if (!bb) goto retfree;
}
- if (bb2 > 0)
+ if (bb2 > 0) {
bb = lshift(bb, bb2);
- if (bd5 > 0)
+ if (!bb) goto retfree;
+ }
+ if (bd5 > 0) {
bd = pow5mult(bd, bd5);
- if (bd2 > 0)
+ if (!bd) goto retfree;
+ }
+ if (bd2 > 0) {
bd = lshift(bd, bd2);
- if (bs2 > 0)
+ if (!bd) goto retfree;
+ }
+ if (bs2 > 0) {
bs = lshift(bs, bs2);
+ if (!bs) goto retfree;
+ }
delta = diff(bb, bd);
+ if (!delta) goto retfree;
dsign = delta->sign;
delta->sign = 0;
i = cmp(delta, bs);
@@ -2041,6 +2081,7 @@ undfl:
#endif
{
delta = lshift(delta,Log2P);
+ if (!delta) goto nomem;
if (cmp(delta, bs) <= 0)
adj = -0.5;
}
@@ -2130,6 +2171,7 @@ apply_adj:
break;
}
delta = lshift(delta,Log2P);
+ if (!delta) goto retfree;
if (cmp(delta, bs) > 0)
goto drop_down;
break;
@@ -2520,10 +2562,10 @@ static char *dtoa_result;
static char *
rv_alloc(int i)
{
- return dtoa_result = xmalloc(i);
+ return dtoa_result = MALLOC(i);
}
#else
-#define rv_alloc(i) xmalloc(i)
+#define rv_alloc(i) MALLOC(i)
#endif
static char *
@@ -2532,6 +2574,7 @@ nrv_alloc(const char *s, char **rve, size_t n)
char *rv, *t;
t = rv = rv_alloc(n);
+ if (!rv) return NULL;
while ((*t = *s++) != 0) t++;
if (rve)
*rve = t;
@@ -2550,7 +2593,7 @@ nrv_alloc(const char *s, char **rve, size_t n)
static void
freedtoa(char *s)
{
- xfree(s);
+ FREE(s);
}
#endif
@@ -2704,6 +2747,7 @@ dtoa(double d_, int mode, int ndigits, int *decpt, int *sign, char **rve)
#endif
b = d2b(dval(d), &be, &bbits);
+ if (!b) return NULL;
#ifdef Sudden_Underflow
i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1));
#else
@@ -2823,13 +2867,20 @@ dtoa(double d_, int mode, int ndigits, int *decpt, int *sign, char **rve)
leftright = 0;
/* no break */
case 5:
- i = ndigits + k + 1;
+ if (ckd_add(&i, ndigits, k + 1)) { /* k + 1 should be safe */
+ Bfree(b);
+ return NULL;
+ }
ilim = i;
ilim1 = i - 1;
if (i <= 0)
i = 1;
}
s = s0 = rv_alloc(i+1);
+ if (!s) {
+ Bfree(b);
+ return NULL;
+ }
#ifdef Honor_FLT_ROUNDS
if (mode > 1 && rounding != 1)
@@ -3010,6 +3061,7 @@ bump_up:
b2 += i;
s2 += i;
mhi = i2b(1);
+ if (!mhi) goto nomem;
}
if (m2 > 0 && s2 > 0) {
i = m2 < s2 ? m2 : s2;
@@ -3021,19 +3073,28 @@ bump_up:
if (leftright) {
if (m5 > 0) {
mhi = pow5mult(mhi, m5);
+ if (!mhi) goto nomem;
b1 = mult(mhi, b);
Bfree(b);
b = b1;
+ if (!b) goto nomem;
}
- if ((j = b5 - m5) != 0)
+ if ((j = b5 - m5) != 0) {
b = pow5mult(b, j);
+ if (!b) goto nomem;
+ }
}
- else
+ else {
b = pow5mult(b, b5);
+ if (!b) goto nomem;
+ }
}
S = i2b(1);
- if (s5 > 0)
+ if (!S) goto nomem;
+ if (s5 > 0) {
S = pow5mult(S, s5);
+ if (!S) goto nomem;
+ }
/* Check for special case that d is a normalized power of 2. */
@@ -3081,16 +3142,23 @@ bump_up:
m2 += i;
s2 += i;
}
- if (b2 > 0)
+ if (b2 > 0) {
b = lshift(b, b2);
- if (s2 > 0)
+ if (!b) goto nomem;
+ }
+ if (s2 > 0) {
S = lshift(S, s2);
+ if (!S) goto nomem;
+ }
if (k_check) {
if (cmp(b,S) < 0) {
k--;
b = multadd(b, 10, 0); /* we botched the k estimate */
- if (leftright)
+ if (!b) goto nomem;
+ if (leftright) {
mhi = multadd(mhi, 10, 0);
+ if (!mhi) goto nomem;
+ }
ilim = ilim1;
}
}
@@ -3107,8 +3175,10 @@ one_digit:
goto ret;
}
if (leftright) {
- if (m2 > 0)
+ if (m2 > 0) {
mhi = lshift(mhi, m2);
+ if (!mhi) goto nomem;
+ }
/* Compute mlo -- check for special case
* that d is a normalized power of 2.
@@ -3117,8 +3187,10 @@ one_digit:
mlo = mhi;
if (spec_case) {
mhi = Balloc(mhi->k);
+ if (!mhi) goto nomem;
Bcopy(mhi, mlo);
mhi = lshift(mhi, Log2P);
+ if (!mhi) goto nomem;
}
for (i = 1;;i++) {
@@ -3128,6 +3200,7 @@ one_digit:
*/
j = cmp(b, mlo);
delta = diff(S, mhi);
+ if (!delta) goto nomem;
j1 = delta->sign ? 1 : cmp(b, delta);
Bfree(delta);
#ifndef ROUND_BIASED
@@ -3168,6 +3241,7 @@ one_digit:
#endif /*Honor_FLT_ROUNDS*/
if (j1 > 0) {
b = lshift(b, 1);
+ if (!b) goto nomem;
j1 = cmp(b, S);
if ((j1 > 0 || (j1 == 0 && (dig & 1))) && dig++ == '9')
goto round_9_up;
@@ -3196,11 +3270,16 @@ keep_dig:
if (i == ilim)
break;
b = multadd(b, 10, 0);
- if (mlo == mhi)
+ if (!b) goto nomem;
+ if (mlo == mhi) {
mlo = mhi = multadd(mhi, 10, 0);
+ if (!mlo) goto nomem;
+ }
else {
mlo = multadd(mlo, 10, 0);
+ if (!mlo) goto nomem;
mhi = multadd(mhi, 10, 0);
+ if (!mhi) goto nomem;
}
}
}
@@ -3216,6 +3295,7 @@ keep_dig:
if (i >= ilim)
break;
b = multadd(b, 10, 0);
+ if (!b) goto nomem;
}
/* Round off last digit */
@@ -3227,6 +3307,7 @@ keep_dig:
}
#endif
b = lshift(b, 1);
+ if (!b) goto nomem;
j = cmp(b, S);
if (j > 0 || (j == 0 && (dig & 1))) {
roundoff:
@@ -3268,6 +3349,16 @@ ret1:
if (rve)
*rve = s;
return s0;
+ nomem:
+ if (S) Bfree(S);
+ if (mhi) {
+ if (mlo && mlo != mhi)
+ Bfree(mlo);
+ Bfree(mhi);
+ }
+ if (b) Bfree(b);
+ FREE(s0);
+ return NULL;
}
/*-
@@ -3376,6 +3467,7 @@ hdtoa(double d, const char *xdigs, int ndigits, int *decpt, int *sign, char **rv
*/
bufsize = (ndigits > 0) ? ndigits : SIGFIGS;
s0 = rv_alloc(bufsize+1);
+ if (!s0) return NULL;
/* Round to the desired number of digits. */
if (SIGFIGS > ndigits && ndigits > 0) {
generated by cgit v1.2.3 (git 2.25.1) at 2026-06-04 05:15:54 +0000