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