1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sts=4 et sw=4 tw=99:
3 * This Source Code Form is subject to the terms of the Mozilla Public
4 * License, v. 2.0. If a copy of the MPL was not distributed with this
5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6
7 /*
8 * Portable double to alphanumeric string and back converters.
9 */
10
11 #include "jsdtoa.h"
12
13 #include "jsprf.h"
14 #include "jstypes.h"
15 #include "jsutil.h"
16
17 using namespace js;
18
19 #ifdef IS_LITTLE_ENDIAN
20 #define IEEE_8087
21 #else
22 #define IEEE_MC68k
23 #endif
24
25 #ifndef Long
26 #define Long int32_t
27 #endif
28
29 #ifndef ULong
30 #define ULong uint32_t
31 #endif
32
33 /*
34 #ifndef Llong
35 #define Llong int64_t
36 #endif
37
38 #ifndef ULlong
39 #define ULlong uint64_t
40 #endif
41 */
42
43 /*
44 * MALLOC gets declared external, and that doesn't work for class members, so
45 * wrap.
46 */
dtoa_malloc(size_t size)47 static inline void* dtoa_malloc(size_t size) { return js_malloc(size); }
dtoa_free(void * p)48 static inline void dtoa_free(void* p) { return js_free(p); }
49
50 #define NO_GLOBAL_STATE
51 #define NO_ERRNO
52 #define MALLOC dtoa_malloc
53 #define FREE dtoa_free
54 #include "dtoa.c"
55
56 /* Mapping of JSDToStrMode -> js_dtoa mode */
57 static const uint8_t dtoaModes[] = {
58 0, /* DTOSTR_STANDARD */
59 0, /* DTOSTR_STANDARD_EXPONENTIAL, */
60 3, /* DTOSTR_FIXED, */
61 2, /* DTOSTR_EXPONENTIAL, */
62 2}; /* DTOSTR_PRECISION */
63
64 double
js_strtod_harder(DtoaState * state,const char * s00,char ** se,int * err)65 js_strtod_harder(DtoaState* state, const char* s00, char** se, int* err)
66 {
67 double retval;
68 if (err)
69 *err = 0;
70 retval = _strtod(state, s00, se);
71 return retval;
72 }
73
74 char*
js_dtostr(DtoaState * state,char * buffer,size_t bufferSize,JSDToStrMode mode,int precision,double dinput)75 js_dtostr(DtoaState* state, char* buffer, size_t bufferSize, JSDToStrMode mode, int precision,
76 double dinput)
77 {
78 U d;
79 int decPt; /* Offset of decimal point from first digit */
80 int sign; /* Nonzero if the sign bit was set in d */
81 int nDigits; /* Number of significand digits returned by js_dtoa */
82 char* numBegin; /* Pointer to the digits returned by js_dtoa */
83 char* numEnd = 0; /* Pointer past the digits returned by js_dtoa */
84
85 MOZ_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL
86 ? DTOSTR_STANDARD_BUFFER_SIZE
87 : DTOSTR_VARIABLE_BUFFER_SIZE(precision)));
88
89 /*
90 * Change mode here rather than below because the buffer may not be large
91 * enough to hold a large integer.
92 */
93 if (mode == DTOSTR_FIXED && (dinput >= 1e21 || dinput <= -1e21))
94 mode = DTOSTR_STANDARD;
95
96 dval(d) = dinput;
97 numBegin = dtoa(PASS_STATE d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
98 if (!numBegin) {
99 return nullptr;
100 }
101
102 nDigits = numEnd - numBegin;
103 MOZ_ASSERT((size_t) nDigits <= bufferSize - 2);
104 if ((size_t) nDigits > bufferSize - 2) {
105 return nullptr;
106 }
107
108 js_memcpy(buffer + 2, numBegin, nDigits);
109 freedtoa(PASS_STATE numBegin);
110 numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
111 numEnd = numBegin + nDigits;
112 *numEnd = '\0';
113
114 /* If Infinity, -Infinity, or NaN, return the string regardless of mode. */
115 if (decPt != 9999) {
116 bool exponentialNotation = false;
117 int minNDigits = 0; /* Min number of significant digits required */
118 char* p;
119 char* q;
120
121 switch (mode) {
122 case DTOSTR_STANDARD:
123 if (decPt < -5 || decPt > 21)
124 exponentialNotation = true;
125 else
126 minNDigits = decPt;
127 break;
128
129 case DTOSTR_FIXED:
130 if (precision >= 0)
131 minNDigits = decPt + precision;
132 else
133 minNDigits = decPt;
134 break;
135
136 case DTOSTR_EXPONENTIAL:
137 MOZ_ASSERT(precision > 0);
138 minNDigits = precision;
139 /* Fall through */
140 case DTOSTR_STANDARD_EXPONENTIAL:
141 exponentialNotation = true;
142 break;
143
144 case DTOSTR_PRECISION:
145 MOZ_ASSERT(precision > 0);
146 minNDigits = precision;
147 if (decPt < -5 || decPt > precision)
148 exponentialNotation = true;
149 break;
150 }
151
152 /* If the number has fewer than minNDigits, end-pad it with zeros. */
153 if (nDigits < minNDigits) {
154 p = numBegin + minNDigits;
155 nDigits = minNDigits;
156 do {
157 *numEnd++ = '0';
158 } while (numEnd != p);
159 *numEnd = '\0';
160 }
161
162 if (exponentialNotation) {
163 /* Insert a decimal point if more than one significand digit */
164 if (nDigits != 1) {
165 numBegin--;
166 numBegin[0] = numBegin[1];
167 numBegin[1] = '.';
168 }
169 JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
170 } else if (decPt != nDigits) {
171 /* Some kind of a fraction in fixed notation */
172 MOZ_ASSERT(decPt <= nDigits);
173 if (decPt > 0) {
174 /* dd...dd . dd...dd */
175 p = --numBegin;
176 do {
177 *p = p[1];
178 p++;
179 } while (--decPt);
180 *p = '.';
181 } else {
182 /* 0 . 00...00dd...dd */
183 p = numEnd;
184 numEnd += 1 - decPt;
185 q = numEnd;
186 MOZ_ASSERT(numEnd < buffer + bufferSize);
187 *numEnd = '\0';
188 while (p != numBegin)
189 *--q = *--p;
190 for (p = numBegin + 1; p != q; p++)
191 *p = '0';
192 *numBegin = '.';
193 *--numBegin = '0';
194 }
195 }
196 }
197
198 /* If negative and neither -0.0 nor NaN, output a leading '-'. */
199 if (sign &&
200 !(word0(d) == Sign_bit && word1(d) == 0) &&
201 !((word0(d) & Exp_mask) == Exp_mask &&
202 (word1(d) || (word0(d) & Frac_mask)))) {
203 *--numBegin = '-';
204 }
205 return numBegin;
206 }
207
208
209 /* Let b = floor(b / divisor), and return the remainder. b must be nonnegative.
210 * divisor must be between 1 and 65536.
211 * This function cannot run out of memory. */
212 static uint32_t
divrem(Bigint * b,uint32_t divisor)213 divrem(Bigint* b, uint32_t divisor)
214 {
215 int32_t n = b->wds;
216 uint32_t remainder = 0;
217 ULong* bx;
218 ULong* bp;
219
220 MOZ_ASSERT(divisor > 0 && divisor <= 65536);
221
222 if (!n)
223 return 0; /* b is zero */
224 bx = b->x;
225 bp = bx + n;
226 do {
227 ULong a = *--bp;
228 ULong dividend = remainder << 16 | a >> 16;
229 ULong quotientHi = dividend / divisor;
230 ULong quotientLo;
231
232 remainder = dividend - quotientHi*divisor;
233 MOZ_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
234 dividend = remainder << 16 | (a & 0xFFFF);
235 quotientLo = dividend / divisor;
236 remainder = dividend - quotientLo*divisor;
237 MOZ_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
238 *bp = quotientHi << 16 | quotientLo;
239 } while (bp != bx);
240 /* Decrease the size of the number if its most significant word is now zero. */
241 if (bx[n-1] == 0)
242 b->wds--;
243 return remainder;
244 }
245
246 /* Return floor(b/2^k) and set b to be the remainder. The returned quotient must be less than 2^32. */
quorem2(Bigint * b,int32_t k)247 static uint32_t quorem2(Bigint* b, int32_t k)
248 {
249 ULong mask;
250 ULong result;
251 ULong* bx;
252 ULong* bxe;
253 int32_t w;
254 int32_t n = k >> 5;
255 k &= 0x1F;
256 mask = (1<<k) - 1;
257
258 w = b->wds - n;
259 if (w <= 0)
260 return 0;
261 MOZ_ASSERT(w <= 2);
262 bx = b->x;
263 bxe = bx + n;
264 result = *bxe >> k;
265 *bxe &= mask;
266 if (w == 2) {
267 MOZ_ASSERT(!(bxe[1] & ~mask));
268 if (k)
269 result |= bxe[1] << (32 - k);
270 }
271 n++;
272 while (!*bxe && bxe != bx) {
273 n--;
274 bxe--;
275 }
276 b->wds = n;
277 return result;
278 }
279
280
281 /* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
282 * which occurs when printing -5e-324 in binary. We could compute a better estimate of the size of
283 * the output string and malloc fewer bytes depending on d and base, but why bother? */
284 #define DTOBASESTR_BUFFER_SIZE 1078
285 #define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))
286
287 char*
js_dtobasestr(DtoaState * state,int base,double dinput)288 js_dtobasestr(DtoaState* state, int base, double dinput)
289 {
290 U d;
291 char* buffer; /* The output string */
292 char* p; /* Pointer to current position in the buffer */
293 char* pInt; /* Pointer to the beginning of the integer part of the string */
294 char* q;
295 uint32_t digit;
296 U di; /* d truncated to an integer */
297 U df; /* The fractional part of d */
298
299 MOZ_ASSERT(base >= 2 && base <= 36);
300
301 dval(d) = dinput;
302 buffer = (char*) js_malloc(DTOBASESTR_BUFFER_SIZE);
303 if (!buffer)
304 return nullptr;
305 p = buffer;
306
307 if (dval(d) < 0.0
308 #if defined(XP_WIN)
309 && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
310 #endif
311 ) {
312 *p++ = '-';
313 dval(d) = -dval(d);
314 }
315
316 /* Check for Infinity and NaN */
317 if ((word0(d) & Exp_mask) == Exp_mask) {
318 strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
319 return buffer;
320 }
321
322 /* Output the integer part of d with the digits in reverse order. */
323 pInt = p;
324 dval(di) = floor(dval(d));
325 if (dval(di) <= 4294967295.0) {
326 uint32_t n = (uint32_t)dval(di);
327 if (n)
328 do {
329 uint32_t m = n / base;
330 digit = n - m*base;
331 n = m;
332 MOZ_ASSERT(digit < (uint32_t)base);
333 *p++ = BASEDIGIT(digit);
334 } while (n);
335 else *p++ = '0';
336 } else {
337 int e;
338 int bits; /* Number of significant bits in di; not used. */
339 Bigint* b = d2b(PASS_STATE di, &e, &bits);
340 if (!b)
341 goto nomem1;
342 b = lshift(PASS_STATE b, e);
343 if (!b) {
344 nomem1:
345 Bfree(PASS_STATE b);
346 js_free(buffer);
347 return nullptr;
348 }
349 do {
350 digit = divrem(b, base);
351 MOZ_ASSERT(digit < (uint32_t)base);
352 *p++ = BASEDIGIT(digit);
353 } while (b->wds);
354 Bfree(PASS_STATE b);
355 }
356 /* Reverse the digits of the integer part of d. */
357 q = p-1;
358 while (q > pInt) {
359 char ch = *pInt;
360 *pInt++ = *q;
361 *q-- = ch;
362 }
363
364 dval(df) = dval(d) - dval(di);
365 if (dval(df) != 0.0) {
366 /* We have a fraction. */
367 int e, bbits;
368 int32_t s2, done;
369 Bigint* b = nullptr;
370 Bigint* s = nullptr;
371 Bigint* mlo = nullptr;
372 Bigint* mhi = nullptr;
373
374 *p++ = '.';
375 b = d2b(PASS_STATE df, &e, &bbits);
376 if (!b) {
377 nomem2:
378 Bfree(PASS_STATE b);
379 Bfree(PASS_STATE s);
380 if (mlo != mhi)
381 Bfree(PASS_STATE mlo);
382 Bfree(PASS_STATE mhi);
383 js_free(buffer);
384 return nullptr;
385 }
386 MOZ_ASSERT(e < 0);
387 /* At this point df = b * 2^e. e must be less than zero because 0 < df < 1. */
388
389 s2 = -(int32_t)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
390 #ifndef Sudden_Underflow
391 if (!s2)
392 s2 = -1;
393 #endif
394 s2 += Bias + P;
395 /* 1/2^s2 = (nextDouble(d) - d)/2 */
396 MOZ_ASSERT(-s2 < e);
397 mlo = i2b(PASS_STATE 1);
398 if (!mlo)
399 goto nomem2;
400 mhi = mlo;
401 if (!word1(d) && !(word0(d) & Bndry_mask)
402 #ifndef Sudden_Underflow
403 && word0(d) & (Exp_mask & Exp_mask << 1)
404 #endif
405 ) {
406 /* The special case. Here we want to be within a quarter of the last input
407 significant digit instead of one half of it when the output string's value is less than d. */
408 s2 += Log2P;
409 mhi = i2b(PASS_STATE 1<<Log2P);
410 if (!mhi)
411 goto nomem2;
412 }
413 b = lshift(PASS_STATE b, e + s2);
414 if (!b)
415 goto nomem2;
416 s = i2b(PASS_STATE 1);
417 if (!s)
418 goto nomem2;
419 s = lshift(PASS_STATE s, s2);
420 if (!s)
421 goto nomem2;
422 /* At this point we have the following:
423 * s = 2^s2;
424 * 1 > df = b/2^s2 > 0;
425 * (d - prevDouble(d))/2 = mlo/2^s2;
426 * (nextDouble(d) - d)/2 = mhi/2^s2. */
427
428 done = false;
429 do {
430 int32_t j, j1;
431 Bigint* delta;
432
433 b = multadd(PASS_STATE b, base, 0);
434 if (!b)
435 goto nomem2;
436 digit = quorem2(b, s2);
437 if (mlo == mhi) {
438 mlo = mhi = multadd(PASS_STATE mlo, base, 0);
439 if (!mhi)
440 goto nomem2;
441 }
442 else {
443 mlo = multadd(PASS_STATE mlo, base, 0);
444 if (!mlo)
445 goto nomem2;
446 mhi = multadd(PASS_STATE mhi, base, 0);
447 if (!mhi)
448 goto nomem2;
449 }
450
451 /* Do we yet have the shortest string that will round to d? */
452 j = cmp(b, mlo);
453 /* j is b/2^s2 compared with mlo/2^s2. */
454 delta = diff(PASS_STATE s, mhi);
455 if (!delta)
456 goto nomem2;
457 j1 = delta->sign ? 1 : cmp(b, delta);
458 Bfree(PASS_STATE delta);
459 /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */
460
461 #ifndef ROUND_BIASED
462 if (j1 == 0 && !(word1(d) & 1)) {
463 if (j > 0)
464 digit++;
465 done = true;
466 } else
467 #endif
468 if (j < 0 || (j == 0
469 #ifndef ROUND_BIASED
470 && !(word1(d) & 1)
471 #endif
472 )) {
473 if (j1 > 0) {
474 /* Either dig or dig+1 would work here as the least significant digit.
475 Use whichever would produce an output value closer to d. */
476 b = lshift(PASS_STATE b, 1);
477 if (!b)
478 goto nomem2;
479 j1 = cmp(b, s);
480 if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
481 * such as 3.5 in base 3. */
482 digit++;
483 }
484 done = true;
485 } else if (j1 > 0) {
486 digit++;
487 done = true;
488 }
489 MOZ_ASSERT(digit < (uint32_t)base);
490 *p++ = BASEDIGIT(digit);
491 } while (!done);
492 Bfree(PASS_STATE b);
493 Bfree(PASS_STATE s);
494 if (mlo != mhi)
495 Bfree(PASS_STATE mlo);
496 Bfree(PASS_STATE mhi);
497 }
498 MOZ_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
499 *p = '\0';
500 return buffer;
501 }
502
503 DtoaState*
NewDtoaState()504 js::NewDtoaState()
505 {
506 return newdtoa();
507 }
508
509 void
DestroyDtoaState(DtoaState * state)510 js::DestroyDtoaState(DtoaState* state)
511 {
512 destroydtoa(state);
513 }
514
515 /* Cleanup pollution from dtoa.c */
516 #undef Bias
517