2 * Number-to-string and string-to-number conversions.
4 * Slow path number-to-string and string-to-number conversion is based on
5 * a Dragon4 variant, with fast paths for small integers. Big integer
6 * arithmetic is needed for guaranteeing that the conversion is correct
7 * and uses a minimum number of digits. The big number arithmetic has a
8 * fixed maximum size and does not require dynamic allocations.
10 * See: doc/number-conversion.rst.
13 #include "duk_internal.h"
15 #define DUK__IEEE_DOUBLE_EXP_BIAS 1023
16 #define DUK__IEEE_DOUBLE_EXP_MIN (-1022) /* biased exp == 0 -> denormal, exp -1022 */
18 #define DUK__DIGITCHAR(x) duk_lc_digits[(x)]
21 * Tables generated with src/gennumdigits.py.
23 * duk__str2num_digits_for_radix indicates, for each radix, how many input
24 * digits should be considered significant for string-to-number conversion.
25 * The input is also padded to this many digits to give the Dragon4
26 * conversion enough (apparent) precision to work with.
28 * duk__str2num_exp_limits indicates, for each radix, the radix-specific
29 * minimum/maximum exponent values (for a Dragon4 integer mantissa)
30 * below and above which the number is guaranteed to underflow to zero
31 * or overflow to Infinity. This allows parsing to keep bigint values
35 DUK_LOCAL
const duk_uint8_t duk__str2num_digits_for_radix
[] = {
36 69, 44, 35, 30, 27, 25, 23, 22, 20, 20, /* 2 to 11 */
37 20, 19, 19, 18, 18, 17, 17, 17, 16, 16, /* 12 to 21 */
38 16, 16, 16, 15, 15, 15, 15, 15, 15, 14, /* 22 to 31 */
39 14, 14, 14, 14, 14 /* 31 to 36 */
47 DUK_LOCAL
const duk__exp_limits duk__str2num_exp_limits
[] = {
48 { 957, -1147 }, { 605, -725 }, { 479, -575 }, { 414, -496 },
49 { 372, -446 }, { 342, -411 }, { 321, -384 }, { 304, -364 },
50 { 291, -346 }, { 279, -334 }, { 268, -323 }, { 260, -312 },
51 { 252, -304 }, { 247, -296 }, { 240, -289 }, { 236, -283 },
52 { 231, -278 }, { 227, -273 }, { 223, -267 }, { 220, -263 },
53 { 216, -260 }, { 213, -256 }, { 210, -253 }, { 208, -249 },
54 { 205, -246 }, { 203, -244 }, { 201, -241 }, { 198, -239 },
55 { 196, -237 }, { 195, -234 }, { 193, -232 }, { 191, -230 },
56 { 190, -228 }, { 188, -226 }, { 187, -225 },
60 * Limited functionality bigint implementation.
62 * Restricted to non-negative numbers with less than 32 * DUK__BI_MAX_PARTS bits,
63 * with the caller responsible for ensuring this is never exceeded. No memory
64 * allocation (except stack) is needed for bigint computation. Operations
65 * have been tailored for number conversion needs.
67 * Argument order is "assignment order", i.e. target first, then arguments:
68 * x <- y * z --> duk__bi_mul(x, y, z);
71 /* This upper value has been experimentally determined; debug build will check
72 * bigint size with assertions.
74 #define DUK__BI_MAX_PARTS 37 /* 37x32 = 1184 bits */
76 #ifdef DUK_USE_DDDPRINT
77 #define DUK__BI_PRINT(name,x) duk__bi_print((name),(x))
79 #define DUK__BI_PRINT(name,x)
82 /* Current size is about 152 bytes. */
85 duk_uint32_t v
[DUK__BI_MAX_PARTS
]; /* low to high */
88 #ifdef DUK_USE_DDDPRINT
89 DUK_LOCAL
void duk__bi_print(const char *name
, duk__bigint
*x
) {
90 /* Overestimate required size; debug code so not critical to be tight. */
91 char buf
[DUK__BI_MAX_PARTS
* 9 + 64];
95 /* No NUL term checks in this debug code. */
96 p
+= DUK_SPRINTF(p
, "%p n=%ld", (void *) x
, (long) x
->n
);
98 p
+= DUK_SPRINTF(p
, " 0");
100 for (i
= x
->n
- 1; i
>= 0; i
--) {
101 p
+= DUK_SPRINTF(p
, " %08lx", (unsigned long) x
->v
[i
]);
104 DUK_DDD(DUK_DDDPRINT("%s: %s", (const char *) name
, (const char *) buf
));
108 #ifdef DUK_USE_ASSERTIONS
109 DUK_LOCAL duk_small_int_t
duk__bi_is_valid(duk__bigint
*x
) {
110 return (duk_small_int_t
)
111 ( ((x
->n
>= 0) && (x
->n
<= DUK__BI_MAX_PARTS
)) /* is valid size */ &&
112 ((x
->n
== 0) || (x
->v
[x
->n
- 1] != 0)) /* is normalized */ );
116 DUK_LOCAL
void duk__bi_normalize(duk__bigint
*x
) {
119 for (i
= x
->n
- 1; i
>= 0; i
--) {
125 /* Note: if 'x' is zero, x->n becomes 0 here */
127 DUK_ASSERT(duk__bi_is_valid(x
));
131 DUK_LOCAL
void duk__bi_copy(duk__bigint
*x
, duk__bigint
*y
) {
139 DUK_MEMCPY((void *) x
->v
, (void *) y
->v
, (size_t) (sizeof(duk_uint32_t
) * n
));
142 DUK_LOCAL
void duk__bi_set_small(duk__bigint
*x
, duk_uint32_t v
) {
149 DUK_ASSERT(duk__bi_is_valid(x
));
152 /* Return value: <0 <=> x < y
156 DUK_LOCAL
int duk__bi_compare(duk__bigint
*x
, duk__bigint
*y
) {
157 duk_small_int_t i
, nx
, ny
;
160 DUK_ASSERT(duk__bi_is_valid(x
));
161 DUK_ASSERT(duk__bi_is_valid(y
));
171 for (i
= nx
- 1; i
>= 0; i
--) {
193 #ifdef DUK_USE_64BIT_OPS
194 DUK_LOCAL
void duk__bi_add(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*z
) {
196 duk_small_int_t i
, ny
, nz
;
198 DUK_ASSERT(duk__bi_is_valid(y
));
199 DUK_ASSERT(duk__bi_is_valid(z
));
205 DUK_ASSERT(y
->n
>= z
->n
);
207 ny
= y
->n
; nz
= z
->n
;
209 for (i
= 0; i
< ny
; i
++) {
210 DUK_ASSERT(i
< DUK__BI_MAX_PARTS
);
215 x
->v
[i
] = (duk_uint32_t
) (tmp
& 0xffffffffUL
);
219 DUK_ASSERT(i
< DUK__BI_MAX_PARTS
);
220 x
->v
[i
++] = (duk_uint32_t
) tmp
;
223 DUK_ASSERT(x
->n
<= DUK__BI_MAX_PARTS
);
225 /* no need to normalize */
226 DUK_ASSERT(duk__bi_is_valid(x
));
228 #else /* DUK_USE_64BIT_OPS */
229 DUK_LOCAL
void duk__bi_add(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*z
) {
230 duk_uint32_t carry
, tmp1
, tmp2
;
231 duk_small_int_t i
, ny
, nz
;
233 DUK_ASSERT(duk__bi_is_valid(y
));
234 DUK_ASSERT(duk__bi_is_valid(z
));
240 DUK_ASSERT(y
->n
>= z
->n
);
242 ny
= y
->n
; nz
= z
->n
;
244 for (i
= 0; i
< ny
; i
++) {
245 /* Carry is detected based on wrapping which relies on exact 32-bit
248 DUK_ASSERT(i
< DUK__BI_MAX_PARTS
);
255 /* Careful with carry condition:
256 * - If carry not added: 0x12345678 + 0 + 0xffffffff = 0x12345677 (< 0x12345678)
257 * - If carry added: 0x12345678 + 1 + 0xffffffff = 0x12345678 (== 0x12345678)
261 carry
= (tmp2
<= tmp1
? 1U : 0U);
263 carry
= (tmp2
< tmp1
? 1U : 0U);
269 DUK_ASSERT(i
< DUK__BI_MAX_PARTS
);
270 DUK_ASSERT(carry
== 1U);
274 DUK_ASSERT(x
->n
<= DUK__BI_MAX_PARTS
);
276 /* no need to normalize */
277 DUK_ASSERT(duk__bi_is_valid(x
));
279 #endif /* DUK_USE_64BIT_OPS */
282 DUK_LOCAL
void duk__bi_add_small(duk__bigint
*x
, duk__bigint
*y
, duk_uint32_t z
) {
285 DUK_ASSERT(duk__bi_is_valid(y
));
287 /* XXX: this could be optimized; there is only one call site now though */
288 duk__bi_set_small(&tmp
, z
);
289 duk__bi_add(x
, y
, &tmp
);
291 DUK_ASSERT(duk__bi_is_valid(x
));
295 /* x <- x + y, use t as temp */
296 DUK_LOCAL
void duk__bi_add_copy(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*t
) {
297 duk__bi_add(t
, x
, y
);
302 /* x <- y - z, require x >= y => z >= 0, i.e. y >= z */
303 #ifdef DUK_USE_64BIT_OPS
304 DUK_LOCAL
void duk__bi_sub(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*z
) {
305 duk_small_int_t i
, ny
, nz
;
309 DUK_ASSERT(duk__bi_is_valid(y
));
310 DUK_ASSERT(duk__bi_is_valid(z
));
311 DUK_ASSERT(duk__bi_compare(y
, z
) >= 0);
312 DUK_ASSERT(y
->n
>= z
->n
);
314 ny
= y
->n
; nz
= z
->n
;
316 for (i
= 0; i
< ny
; i
++) {
323 tmp
= (duk_int64_t
) ty
- (duk_int64_t
) tz
+ tmp
;
324 x
->v
[i
] = (duk_uint32_t
) (tmp
& 0xffffffffUL
);
325 tmp
= tmp
>> 32; /* 0 or -1 */
327 DUK_ASSERT(tmp
== 0);
330 duk__bi_normalize(x
); /* need to normalize, may even cancel to 0 */
331 DUK_ASSERT(duk__bi_is_valid(x
));
334 DUK_LOCAL
void duk__bi_sub(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*z
) {
335 duk_small_int_t i
, ny
, nz
;
336 duk_uint32_t tmp1
, tmp2
, borrow
;
338 DUK_ASSERT(duk__bi_is_valid(y
));
339 DUK_ASSERT(duk__bi_is_valid(z
));
340 DUK_ASSERT(duk__bi_compare(y
, z
) >= 0);
341 DUK_ASSERT(y
->n
>= z
->n
);
343 ny
= y
->n
; nz
= z
->n
;
345 for (i
= 0; i
< ny
; i
++) {
346 /* Borrow is detected based on wrapping which relies on exact 32-bit
355 /* Careful with borrow condition:
356 * - If borrow not subtracted: 0x12345678 - 0 - 0xffffffff = 0x12345679 (> 0x12345678)
357 * - If borrow subtracted: 0x12345678 - 1 - 0xffffffff = 0x12345678 (== 0x12345678)
361 borrow
= (tmp2
>= tmp1
? 1U : 0U);
363 borrow
= (tmp2
> tmp1
? 1U : 0U);
368 DUK_ASSERT(borrow
== 0U);
371 duk__bi_normalize(x
); /* need to normalize, may even cancel to 0 */
372 DUK_ASSERT(duk__bi_is_valid(x
));
378 DUK_LOCAL
void duk__bi_sub_small(duk__bigint
*x
, duk__bigint
*y
, duk_uint32_t z
) {
381 DUK_ASSERT(duk__bi_is_valid(y
));
383 /* XXX: this could be optimized */
384 duk__bi_set_small(&tmp
, z
);
385 duk__bi_sub(x
, y
, &tmp
);
387 DUK_ASSERT(duk__bi_is_valid(x
));
391 /* x <- x - y, use t as temp */
392 DUK_LOCAL
void duk__bi_sub_copy(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*t
) {
393 duk__bi_sub(t
, x
, y
);
398 DUK_LOCAL
void duk__bi_mul(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*z
) {
399 duk_small_int_t i
, j
, nx
, nz
;
401 DUK_ASSERT(duk__bi_is_valid(y
));
402 DUK_ASSERT(duk__bi_is_valid(z
));
404 nx
= y
->n
+ z
->n
; /* max possible */
405 DUK_ASSERT(nx
<= DUK__BI_MAX_PARTS
);
408 /* Both inputs are zero; cases where only one is zero can go
409 * through main algorithm.
415 DUK_MEMZERO((void *) x
->v
, (size_t) (sizeof(duk_uint32_t
) * nx
));
419 for (i
= 0; i
< y
->n
; i
++) {
420 #ifdef DUK_USE_64BIT_OPS
421 duk_uint64_t tmp
= 0U;
422 for (j
= 0; j
< nz
; j
++) {
423 tmp
+= (duk_uint64_t
) y
->v
[i
] * (duk_uint64_t
) z
->v
[j
] + x
->v
[i
+j
];
424 x
->v
[i
+j
] = (duk_uint32_t
) (tmp
& 0xffffffffUL
);
428 DUK_ASSERT(i
+ j
< nx
);
429 DUK_ASSERT(i
+ j
< DUK__BI_MAX_PARTS
);
430 DUK_ASSERT(x
->v
[i
+j
] == 0U);
431 x
->v
[i
+j
] = (duk_uint32_t
) tmp
;
435 * Multiply + add + carry for 32-bit components using only 16x16->32
436 * multiplies and carry detection based on unsigned overflow.
438 * 1st mult, 32-bit: (A*2^16 + B)
439 * 2nd mult, 32-bit: (C*2^16 + D)
443 * (AC*2^16 + B) * (C*2^16 + D) + E + F
444 * = AC*2^32 + AD*2^16 + BC*2^16 + BD + E + F
445 * = AC*2^32 + (AD + BC)*2^16 + (BD + E + F)
446 * = AC*2^32 + AD*2^16 + BC*2^16 + (BD + E + F)
448 duk_uint32_t a
, b
, c
, d
, e
, f
;
449 duk_uint32_t r
, s
, t
;
451 a
= y
->v
[i
]; b
= a
& 0xffffUL
; a
= a
>> 16;
454 for (j
= 0; j
< nz
; j
++) {
455 c
= z
->v
[j
]; d
= c
& 0xffffUL
; c
= c
>> 16;
458 /* build result as: (r << 32) + s: start with (BD + E + F) */
464 if (t
< s
) { r
++; } /* carry */
469 if (t
< s
) { r
++; } /* carry */
475 t
= s
+ ((t
& 0xffffUL
) << 16);
476 if (t
< s
) { r
++; } /* carry */
482 t
= s
+ ((t
& 0xffffUL
) << 16);
483 if (t
< s
) { r
++; } /* carry */
490 DUK_DDD(DUK_DDDPRINT("ab=%08lx cd=%08lx ef=%08lx -> rs=%08lx %08lx",
491 (unsigned long) y
->v
[i
], (unsigned long) z
->v
[j
],
492 (unsigned long) x
->v
[i
+j
], (unsigned long) r
,
499 DUK_ASSERT(i
+ j
< nx
);
500 DUK_ASSERT(i
+ j
< DUK__BI_MAX_PARTS
);
501 DUK_ASSERT(x
->v
[i
+j
] == 0U);
502 x
->v
[i
+j
] = (duk_uint32_t
) f
;
504 #endif /* DUK_USE_64BIT_OPS */
507 duk__bi_normalize(x
);
508 DUK_ASSERT(duk__bi_is_valid(x
));
512 DUK_LOCAL
void duk__bi_mul_small(duk__bigint
*x
, duk__bigint
*y
, duk_uint32_t z
) {
515 DUK_ASSERT(duk__bi_is_valid(y
));
517 /* XXX: this could be optimized */
518 duk__bi_set_small(&tmp
, z
);
519 duk__bi_mul(x
, y
, &tmp
);
521 DUK_ASSERT(duk__bi_is_valid(x
));
524 /* x <- x * y, use t as temp */
525 DUK_LOCAL
void duk__bi_mul_copy(duk__bigint
*x
, duk__bigint
*y
, duk__bigint
*t
) {
526 duk__bi_mul(t
, x
, y
);
530 /* x <- x * y, use t as temp */
531 DUK_LOCAL
void duk__bi_mul_small_copy(duk__bigint
*x
, duk_uint32_t y
, duk__bigint
*t
) {
532 duk__bi_mul_small(t
, x
, y
);
536 DUK_LOCAL
int duk__bi_is_even(duk__bigint
*x
) {
537 DUK_ASSERT(duk__bi_is_valid(x
));
538 return (x
->n
== 0) || ((x
->v
[0] & 0x01) == 0);
541 DUK_LOCAL
int duk__bi_is_zero(duk__bigint
*x
) {
542 DUK_ASSERT(duk__bi_is_valid(x
));
543 return (x
->n
== 0); /* this is the case for normalized numbers */
546 /* Bigint is 2^52. Used to detect normalized IEEE double mantissa values
547 * which are at the lowest edge (next floating point value downwards has
548 * a different exponent). The lowest mantissa has the form:
550 * 1000........000 (52 zeroes; only "hidden bit" is set)
552 DUK_LOCAL duk_small_int_t
duk__bi_is_2to52(duk__bigint
*x
) {
553 DUK_ASSERT(duk__bi_is_valid(x
));
554 return (duk_small_int_t
)
555 (x
->n
== 2) && (x
->v
[0] == 0U) && (x
->v
[1] == (1U << (52-32)));
559 DUK_LOCAL
void duk__bi_twoexp(duk__bigint
*x
, duk_small_int_t y
) {
560 duk_small_int_t n
, r
;
565 DUK_MEMZERO((void *) x
->v
, sizeof(duk_uint32_t
) * n
);
567 x
->v
[n
- 1] = (((duk_uint32_t
) 1) << r
);
570 /* x <- b^y; use t1 and t2 as temps */
571 DUK_LOCAL
void duk__bi_exp_small(duk__bigint
*x
, duk_small_int_t b
, duk_small_int_t y
, duk__bigint
*t1
, duk__bigint
*t2
) {
572 /* Fast path the binary case */
574 DUK_ASSERT(x
!= t1
&& x
!= t2
&& t1
!= t2
); /* distinct bignums, easy mistake to make */
579 duk__bi_twoexp(x
, y
);
583 /* http://en.wikipedia.org/wiki/Exponentiation_by_squaring */
585 DUK_DDD(DUK_DDDPRINT("exp_small: b=%ld, y=%ld", (long) b
, (long) y
));
587 duk__bi_set_small(x
, 1);
588 duk__bi_set_small(t1
, b
);
590 /* Loop structure ensures that we don't compute t1^2 unnecessarily
591 * on the final round, as that might create a bignum exceeding the
592 * current DUK__BI_MAX_PARTS limit.
595 duk__bi_mul_copy(x
, t1
, t2
);
601 duk__bi_mul_copy(t1
, t1
, t2
);
604 DUK__BI_PRINT("exp_small result", x
);
608 * A Dragon4 number-to-string variant, based on:
610 * Guy L. Steele Jr., Jon L. White: "How to Print Floating-Point Numbers
613 * Robert G. Burger, R. Kent Dybvig: "Printing Floating-Point Numbers
614 * Quickly and Accurately"
616 * The current algorithm is based on Figure 1 of the Burger-Dybvig paper,
617 * i.e. the base implementation without logarithm estimation speedups
618 * (these would increase code footprint considerably). Fixed-format output
619 * does not follow the suggestions in the paper; instead, we generate an
620 * extra digit and round-with-carry.
622 * The same algorithm is used for number parsing (with b=10 and B=2)
623 * by generating one extra digit and doing rounding manually.
625 * See doc/number-conversion.rst for limitations.
628 /* Maximum number of digits generated. */
629 #define DUK__MAX_OUTPUT_DIGITS 1040 /* (Number.MAX_VALUE).toString(2).length == 1024, + spare */
631 /* Maximum number of characters in formatted value. */
632 #define DUK__MAX_FORMATTED_LENGTH 1040 /* (-Number.MAX_VALUE).toString(2).length == 1025, + spare */
634 /* Number and (minimum) size of bigints in the nc_ctx structure. */
635 #define DUK__NUMCONV_CTX_NUM_BIGINTS 7
636 #define DUK__NUMCONV_CTX_BIGINTS_SIZE (sizeof(duk__bigint) * DUK__NUMCONV_CTX_NUM_BIGINTS)
639 /* Currently about 7*152 = 1064 bytes. The space for these
640 * duk__bigints is used also as a temporary buffer for generating
641 * the final string. This is a bit awkard; a union would be
644 duk__bigint f
, r
, s
, mp
, mm
, t1
, t2
;
646 duk_small_int_t is_s2n
; /* if 1, doing a string-to-number; else doing a number-to-string */
647 duk_small_int_t is_fixed
; /* if 1, doing a fixed format output (not free format) */
648 duk_small_int_t req_digits
; /* requested number of output digits; 0 = free-format */
649 duk_small_int_t abs_pos
; /* digit position is absolute, not relative */
650 duk_small_int_t e
; /* exponent for 'f' */
651 duk_small_int_t b
; /* input radix */
652 duk_small_int_t B
; /* output radix */
653 duk_small_int_t k
; /* see algorithm */
654 duk_small_int_t low_ok
; /* see algorithm */
655 duk_small_int_t high_ok
; /* see algorithm */
656 duk_small_int_t unequal_gaps
; /* m+ != m- (very rarely) */
658 /* Buffer used for generated digits, values are in the range [0,B-1]. */
659 duk_uint8_t digits
[DUK__MAX_OUTPUT_DIGITS
];
660 duk_small_int_t count
; /* digit count */
661 } duk__numconv_stringify_ctx
;
663 /* Note: computes with 'idx' in assertions, so caller beware.
664 * 'idx' is preincremented, i.e. '1' on first call, because it
665 * is more convenient for the caller.
667 #define DUK__DRAGON4_OUTPUT_PREINC(nc_ctx,preinc_idx,x) do { \
668 DUK_ASSERT((preinc_idx) - 1 >= 0); \
669 DUK_ASSERT((preinc_idx) - 1 < DUK__MAX_OUTPUT_DIGITS); \
670 ((nc_ctx)->digits[(preinc_idx) - 1]) = (duk_uint8_t) (x); \
673 DUK_LOCAL duk_size_t
duk__dragon4_format_uint32(duk_uint8_t
*buf
, duk_uint32_t x
, duk_small_int_t radix
) {
679 DUK_ASSERT(radix
>= 2 && radix
<= 36);
681 /* A 32-bit unsigned integer formats to at most 32 digits (the
682 * worst case happens with radix == 2). Output the digits backwards,
683 * and use a memmove() to get them in the right place.
692 DUK_ASSERT(dig
>= 0 && dig
< 36);
693 *(--p
) = DUK__DIGITCHAR(dig
);
699 len
= (duk_size_t
) ((buf
+ 32) - p
);
701 DUK_MEMMOVE((void *) buf
, (void *) p
, (size_t) len
);
706 DUK_LOCAL
void duk__dragon4_prepare(duk__numconv_stringify_ctx
*nc_ctx
) {
707 duk_small_int_t lowest_mantissa
;
710 /* Assume IEEE round-to-even, so that shorter encoding can be used
711 * when round-to-even would produce correct result. By removing
712 * this check (and having low_ok == high_ok == 0) the results would
713 * still be accurate but in some cases longer than necessary.
715 if (duk__bi_is_even(&nc_ctx
->f
)) {
716 DUK_DDD(DUK_DDDPRINT("f is even"));
720 DUK_DDD(DUK_DDDPRINT("f is odd"));
725 /* Note: not honoring round-to-even should work but now generates incorrect
726 * results. For instance, 1e23 serializes to "a000...", i.e. the first digit
727 * equals the radix (10). Scaling stops one step too early in this case.
728 * Don't know why this is the case, but since this code path is unused, it
735 /* For string-to-number, pretend we never have the lowest mantissa as there
736 * is no natural "precision" for inputs. Having lowest_mantissa == 0, we'll
737 * fall into the base cases for both e >= 0 and e < 0.
739 if (nc_ctx
->is_s2n
) {
742 lowest_mantissa
= duk__bi_is_2to52(&nc_ctx
->f
);
745 nc_ctx
->unequal_gaps
= 0;
746 if (nc_ctx
->e
>= 0) {
747 /* exponent non-negative (and thus not minimum exponent) */
749 if (lowest_mantissa
) {
750 /* (>= e 0) AND (= f (expt b (- p 1)))
752 * be <- (expt b e) == b^e
753 * be1 <- (* be b) == (expt b (+ e 1)) == b^(e+1)
754 * r <- (* f be1 2) == 2 * f * b^(e+1) [if b==2 -> f * b^(e+2)]
755 * s <- (* b 2) [if b==2 -> 4]
756 * m+ <- be1 == b^(e+1)
764 DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); "
765 "lowest mantissa value for this exponent -> "
768 duk__bi_exp_small(&nc_ctx
->mm
, nc_ctx
->b
, nc_ctx
->e
, &nc_ctx
->t1
, &nc_ctx
->t2
); /* mm <- b^e */
769 duk__bi_mul_small(&nc_ctx
->mp
, &nc_ctx
->mm
, nc_ctx
->b
); /* mp <- b^(e+1) */
770 duk__bi_mul_small(&nc_ctx
->t1
, &nc_ctx
->f
, 2);
771 duk__bi_mul(&nc_ctx
->r
, &nc_ctx
->t1
, &nc_ctx
->mp
); /* r <- (2 * f) * b^(e+1) */
772 duk__bi_set_small(&nc_ctx
->s
, nc_ctx
->b
* 2); /* s <- 2 * b */
773 nc_ctx
->unequal_gaps
= 1;
775 /* (>= e 0) AND (not (= f (expt b (- p 1))))
777 * be <- (expt b e) == b^e
778 * r <- (* f be 2) == 2 * f * b^e [if b==2 -> f * b^(e+1)]
788 DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); "
789 "not lowest mantissa for this exponent -> "
792 duk__bi_exp_small(&nc_ctx
->mm
, nc_ctx
->b
, nc_ctx
->e
, &nc_ctx
->t1
, &nc_ctx
->t2
); /* mm <- b^e */
793 duk__bi_copy(&nc_ctx
->mp
, &nc_ctx
->mm
); /* mp <- b^e */
794 duk__bi_mul_small(&nc_ctx
->t1
, &nc_ctx
->f
, 2);
795 duk__bi_mul(&nc_ctx
->r
, &nc_ctx
->t1
, &nc_ctx
->mp
); /* r <- (2 * f) * b^e */
796 duk__bi_set_small(&nc_ctx
->s
, 2); /* s <- 2 */
799 /* When doing string-to-number, lowest_mantissa is always 0 so
800 * the exponent check, while incorrect, won't matter.
802 if (nc_ctx
->e
> DUK__IEEE_DOUBLE_EXP_MIN
/*not minimum exponent*/ &&
803 lowest_mantissa
/* lowest mantissa for this exponent*/) {
804 /* r <- (* f b 2) [if b==2 -> (* f 4)]
805 * s <- (* (expt b (- 1 e)) 2) == b^(1-e) * 2 [if b==2 -> b^(2-e)]
814 DUK_DDD(DUK_DDDPRINT("negative exponent; not minimum exponent and "
815 "lowest mantissa for this exponent -> "
818 duk__bi_mul_small(&nc_ctx
->r
, &nc_ctx
->f
, nc_ctx
->b
* 2); /* r <- (2 * b) * f */
819 duk__bi_exp_small(&nc_ctx
->t1
, nc_ctx
->b
, 1 - nc_ctx
->e
, &nc_ctx
->s
, &nc_ctx
->t2
); /* NB: use 's' as temp on purpose */
820 duk__bi_mul_small(&nc_ctx
->s
, &nc_ctx
->t1
, 2); /* s <- b^(1-e) * 2 */
821 duk__bi_set_small(&nc_ctx
->mp
, 2);
822 duk__bi_set_small(&nc_ctx
->mm
, 1);
823 nc_ctx
->unequal_gaps
= 1;
826 * s <- (* (expt b (- e)) 2) == b^(-e) * 2 [if b==2 -> b^(1-e)]
835 DUK_DDD(DUK_DDDPRINT("negative exponent; minimum exponent or not "
836 "lowest mantissa for this exponent -> "
839 duk__bi_mul_small(&nc_ctx
->r
, &nc_ctx
->f
, 2); /* r <- 2 * f */
840 duk__bi_exp_small(&nc_ctx
->t1
, nc_ctx
->b
, -nc_ctx
->e
, &nc_ctx
->s
, &nc_ctx
->t2
); /* NB: use 's' as temp on purpose */
841 duk__bi_mul_small(&nc_ctx
->s
, &nc_ctx
->t1
, 2); /* s <- b^(-e) * 2 */
842 duk__bi_set_small(&nc_ctx
->mp
, 1);
843 duk__bi_set_small(&nc_ctx
->mm
, 1);
848 DUK_LOCAL
void duk__dragon4_scale(duk__numconv_stringify_ctx
*nc_ctx
) {
849 duk_small_int_t k
= 0;
851 /* This is essentially the 'scale' algorithm, with recursion removed.
852 * Note that 'k' is either correct immediately, or will move in one
853 * direction in the loop. There's no need to do the low/high checks
854 * on every round (like the Scheme algorithm does).
856 * The scheme algorithm finds 'k' and updates 's' simultaneously,
857 * while the logical algorithm finds 'k' with 's' having its initial
858 * value, after which 's' is updated separately (see the Burger-Dybvig
859 * paper, Section 3.1, steps 2 and 3).
861 * The case where m+ == m- (almost always) is optimized for, because
862 * it reduces the bigint operations considerably and almost always
863 * applies. The scale loop only needs to work with m+, so this works.
866 /* XXX: this algorithm could be optimized quite a lot by using e.g.
867 * a logarithm based estimator for 'k' and performing B^n multiplication
868 * using a lookup table or using some bit-representation based exp
869 * algorithm. Currently we just loop, with significant performance
870 * impact for very large and very small numbers.
873 DUK_DDD(DUK_DDDPRINT("scale: B=%ld, low_ok=%ld, high_ok=%ld",
874 (long) nc_ctx
->B
, (long) nc_ctx
->low_ok
, (long) nc_ctx
->high_ok
));
875 DUK__BI_PRINT("r(init)", &nc_ctx
->r
);
876 DUK__BI_PRINT("s(init)", &nc_ctx
->s
);
877 DUK__BI_PRINT("mp(init)", &nc_ctx
->mp
);
878 DUK__BI_PRINT("mm(init)", &nc_ctx
->mm
);
881 DUK_DDD(DUK_DDDPRINT("scale loop (inc k), k=%ld", (long) k
));
882 DUK__BI_PRINT("r", &nc_ctx
->r
);
883 DUK__BI_PRINT("s", &nc_ctx
->s
);
884 DUK__BI_PRINT("m+", &nc_ctx
->mp
);
885 DUK__BI_PRINT("m-", &nc_ctx
->mm
);
887 duk__bi_add(&nc_ctx
->t1
, &nc_ctx
->r
, &nc_ctx
->mp
); /* t1 = (+ r m+) */
888 if (duk__bi_compare(&nc_ctx
->t1
, &nc_ctx
->s
) >= (nc_ctx
->high_ok
? 0 : 1)) {
889 DUK_DDD(DUK_DDDPRINT("k is too low"));
897 duk__bi_mul_small_copy(&nc_ctx
->s
, nc_ctx
->B
, &nc_ctx
->t1
);
904 /* k > 0 -> k was too low, and cannot be too high */
910 DUK_DDD(DUK_DDDPRINT("scale loop (dec k), k=%ld", (long) k
));
911 DUK__BI_PRINT("r", &nc_ctx
->r
);
912 DUK__BI_PRINT("s", &nc_ctx
->s
);
913 DUK__BI_PRINT("m+", &nc_ctx
->mp
);
914 DUK__BI_PRINT("m-", &nc_ctx
->mm
);
916 duk__bi_add(&nc_ctx
->t1
, &nc_ctx
->r
, &nc_ctx
->mp
); /* t1 = (+ r m+) */
917 duk__bi_mul_small(&nc_ctx
->t2
, &nc_ctx
->t1
, nc_ctx
->B
); /* t2 = (* (+ r m+) B) */
918 if (duk__bi_compare(&nc_ctx
->t2
, &nc_ctx
->s
) <= (nc_ctx
->high_ok
? -1 : 0)) {
919 DUK_DDD(DUK_DDDPRINT("k is too high"));
926 duk__bi_mul_small_copy(&nc_ctx
->r
, nc_ctx
->B
, &nc_ctx
->t1
);
927 duk__bi_mul_small_copy(&nc_ctx
->mp
, nc_ctx
->B
, &nc_ctx
->t1
);
928 if (nc_ctx
->unequal_gaps
) {
929 DUK_DDD(DUK_DDDPRINT("m+ != m- -> need to update m- too"));
930 duk__bi_mul_small_copy(&nc_ctx
->mm
, nc_ctx
->B
, &nc_ctx
->t1
);
940 if (!nc_ctx
->unequal_gaps
) {
941 DUK_DDD(DUK_DDDPRINT("equal gaps, copy m- from m+"));
942 duk__bi_copy(&nc_ctx
->mm
, &nc_ctx
->mp
); /* mm <- mp */
946 DUK_DDD(DUK_DDDPRINT("final k: %ld", (long) k
));
947 DUK__BI_PRINT("r(final)", &nc_ctx
->r
);
948 DUK__BI_PRINT("s(final)", &nc_ctx
->s
);
949 DUK__BI_PRINT("mp(final)", &nc_ctx
->mp
);
950 DUK__BI_PRINT("mm(final)", &nc_ctx
->mm
);
953 DUK_LOCAL
void duk__dragon4_generate(duk__numconv_stringify_ctx
*nc_ctx
) {
954 duk_small_int_t tc1
, tc2
; /* terminating conditions */
955 duk_small_int_t d
; /* current digit */
956 duk_small_int_t count
= 0; /* digit count */
959 * Digit generation loop.
961 * Different termination conditions:
963 * 1. Free format output. Terminate when shortest accurate
964 * representation found.
966 * 2. Fixed format output, with specific number of digits.
967 * Ignore termination conditions, terminate when digits
968 * generated. Caller requests an extra digit and rounds.
970 * 3. Fixed format output, with a specific absolute cut-off
971 * position (e.g. 10 digits after decimal point). Note
972 * that we always generate at least one digit, even if
973 * the digit is below the cut-off point already.
977 DUK_DDD(DUK_DDDPRINT("generate loop, count=%ld, k=%ld, B=%ld, low_ok=%ld, high_ok=%ld",
978 (long) count
, (long) nc_ctx
->k
, (long) nc_ctx
->B
,
979 (long) nc_ctx
->low_ok
, (long) nc_ctx
->high_ok
));
980 DUK__BI_PRINT("r", &nc_ctx
->r
);
981 DUK__BI_PRINT("s", &nc_ctx
->s
);
982 DUK__BI_PRINT("m+", &nc_ctx
->mp
);
983 DUK__BI_PRINT("m-", &nc_ctx
->mm
);
985 /* (quotient-remainder (* r B) s) using a dummy subtraction loop */
986 duk__bi_mul_small(&nc_ctx
->t1
, &nc_ctx
->r
, nc_ctx
->B
); /* t1 <- (* r B) */
989 if (duk__bi_compare(&nc_ctx
->t1
, &nc_ctx
->s
) < 0) {
992 duk__bi_sub_copy(&nc_ctx
->t1
, &nc_ctx
->s
, &nc_ctx
->t2
); /* t1 <- t1 - s */
995 duk__bi_copy(&nc_ctx
->r
, &nc_ctx
->t1
); /* r <- (remainder (* r B) s) */
996 /* d <- (quotient (* r B) s) (in range 0...B-1) */
997 DUK_DDD(DUK_DDDPRINT("-> d(quot)=%ld", (long) d
));
998 DUK__BI_PRINT("r(rem)", &nc_ctx
->r
);
1000 duk__bi_mul_small_copy(&nc_ctx
->mp
, nc_ctx
->B
, &nc_ctx
->t2
); /* m+ <- (* m+ B) */
1001 duk__bi_mul_small_copy(&nc_ctx
->mm
, nc_ctx
->B
, &nc_ctx
->t2
); /* m- <- (* m- B) */
1002 DUK__BI_PRINT("mp(upd)", &nc_ctx
->mp
);
1003 DUK__BI_PRINT("mm(upd)", &nc_ctx
->mm
);
1005 /* Terminating conditions. For fixed width output, we just ignore the
1006 * terminating conditions (and pretend that tc1 == tc2 == false). The
1007 * the current shortcut for fixed-format output is to generate a few
1008 * extra digits and use rounding (with carry) to finish the output.
1011 if (nc_ctx
->is_fixed
== 0) {
1013 tc1
= (duk__bi_compare(&nc_ctx
->r
, &nc_ctx
->mm
) <= (nc_ctx
->low_ok
? 0 : -1));
1015 duk__bi_add(&nc_ctx
->t1
, &nc_ctx
->r
, &nc_ctx
->mp
); /* t1 <- (+ r m+) */
1016 tc2
= (duk__bi_compare(&nc_ctx
->t1
, &nc_ctx
->s
) >= (nc_ctx
->high_ok
? 0 : 1));
1018 DUK_DDD(DUK_DDDPRINT("tc1=%ld, tc2=%ld", (long) tc1
, (long) tc2
));
1025 /* Count is incremented before DUK__DRAGON4_OUTPUT_PREINC() call
1026 * on purpose, which is taken into account by the macro.
1032 /* tc1 = true, tc2 = true */
1033 duk__bi_mul_small(&nc_ctx
->t1
, &nc_ctx
->r
, 2);
1034 if (duk__bi_compare(&nc_ctx
->t1
, &nc_ctx
->s
) < 0) { /* (< (* r 2) s) */
1035 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=true, 2r > s: output d --> %ld (k=%ld)",
1036 (long) d
, (long) nc_ctx
->k
));
1037 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx
, count
, d
);
1039 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=true, 2r <= s: output d+1 --> %ld (k=%ld)",
1040 (long) (d
+ 1), (long) nc_ctx
->k
));
1041 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx
, count
, d
+ 1);
1045 /* tc1 = true, tc2 = false */
1046 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=false: output d --> %ld (k=%ld)",
1047 (long) d
, (long) nc_ctx
->k
));
1048 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx
, count
, d
);
1053 /* tc1 = false, tc2 = true */
1054 DUK_DDD(DUK_DDDPRINT("tc1=false, tc2=true: output d+1 --> %ld (k=%ld)",
1055 (long) (d
+ 1), (long) nc_ctx
->k
));
1056 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx
, count
, d
+ 1);
1059 /* tc1 = false, tc2 = false */
1060 DUK_DDD(DUK_DDDPRINT("tc1=false, tc2=false: output d --> %ld (k=%ld)",
1061 (long) d
, (long) nc_ctx
->k
));
1062 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx
, count
, d
);
1064 /* r <- r (updated above: r <- (remainder (* r B) s)
1066 * m+ <- m+ (updated above: m+ <- (* m+ B)
1067 * m- <- m- (updated above: m- <- (* m- B)
1068 * B, low_ok, high_ok are fixed
1071 /* fall through and continue for-loop */
1075 /* fixed-format termination conditions */
1076 if (nc_ctx
->is_fixed
) {
1077 if (nc_ctx
->abs_pos
) {
1078 int pos
= nc_ctx
->k
- count
+ 1; /* count is already incremented, take into account */
1079 DUK_DDD(DUK_DDDPRINT("fixed format, absolute: abs pos=%ld, k=%ld, count=%ld, req=%ld",
1080 (long) pos
, (long) nc_ctx
->k
, (long) count
, (long) nc_ctx
->req_digits
));
1081 if (pos
<= nc_ctx
->req_digits
) {
1082 DUK_DDD(DUK_DDDPRINT("digit position reached req_digits, end generate loop"));
1086 DUK_DDD(DUK_DDDPRINT("fixed format, relative: k=%ld, count=%ld, req=%ld",
1087 (long) nc_ctx
->k
, (long) count
, (long) nc_ctx
->req_digits
));
1088 if (count
>= nc_ctx
->req_digits
) {
1089 DUK_DDD(DUK_DDDPRINT("digit count reached req_digits, end generate loop"));
1096 nc_ctx
->count
= count
;
1098 DUK_DDD(DUK_DDDPRINT("generate finished"));
1100 #ifdef DUK_USE_DDDPRINT
1102 duk_uint8_t buf
[2048];
1103 duk_small_int_t i
, t
;
1104 DUK_MEMZERO(buf
, sizeof(buf
));
1105 for (i
= 0; i
< nc_ctx
->count
; i
++) {
1106 t
= nc_ctx
->digits
[i
];
1107 if (t
< 0 || t
> 36) {
1108 buf
[i
] = (duk_uint8_t
) '?';
1110 buf
[i
] = (duk_uint8_t
) DUK__DIGITCHAR(t
);
1113 DUK_DDD(DUK_DDDPRINT("-> generated digits; k=%ld, digits='%s'",
1114 (long) nc_ctx
->k
, (const char *) buf
));
1119 /* Round up digits to a given position. If position is out-of-bounds,
1120 * does nothing. If carry propagates over the first digit, a '1' is
1121 * prepended to digits and 'k' will be updated. Return value indicates
1122 * whether carry propagated over the first digit.
1124 * Note that nc_ctx->count is NOT updated based on the rounding position
1125 * (it is updated only if carry overflows over the first digit and an
1126 * extra digit is prepended).
1128 DUK_LOCAL duk_small_int_t
duk__dragon4_fixed_format_round(duk__numconv_stringify_ctx
*nc_ctx
, duk_small_int_t round_idx
) {
1131 duk_uint8_t roundup_limit
;
1132 duk_small_int_t ret
= 0;
1135 * round_idx points to the digit which is considered for rounding; the
1136 * digit to its left is the final digit of the rounded value. If round_idx
1137 * is zero, rounding will be performed; the result will either be an empty
1138 * rounded value or if carry happens a '1' digit is generated.
1141 if (round_idx
>= nc_ctx
->count
) {
1142 DUK_DDD(DUK_DDDPRINT("round_idx out of bounds (%ld >= %ld (count)) -> no rounding",
1143 (long) round_idx
, (long) nc_ctx
->count
));
1145 } else if (round_idx
< 0) {
1146 DUK_DDD(DUK_DDDPRINT("round_idx out of bounds (%ld < 0) -> no rounding",
1154 * For even values, divides evenly, e.g. 10 -> roundup_limit=5.
1156 * For odd values, rounds up, e.g. 3 -> roundup_limit=2.
1157 * If radix is 3, 0/3 -> down, 1/3 -> down, 2/3 -> up.
1159 roundup_limit
= (duk_uint8_t
) ((nc_ctx
->B
+ 1) / 2);
1161 p
= &nc_ctx
->digits
[round_idx
];
1162 if (*p
>= roundup_limit
) {
1163 DUK_DDD(DUK_DDDPRINT("fixed-format rounding carry required"));
1167 if (p
== &nc_ctx
->digits
[0]) {
1168 DUK_DDD(DUK_DDDPRINT("carry propagated to first digit -> special case handling"));
1169 DUK_MEMMOVE((void *) (&nc_ctx
->digits
[1]),
1170 (void *) (&nc_ctx
->digits
[0]),
1171 (size_t) (sizeof(char) * nc_ctx
->count
));
1172 nc_ctx
->digits
[0] = 1; /* don't increase 'count' */
1173 nc_ctx
->k
++; /* position of highest digit changed */
1174 nc_ctx
->count
++; /* number of digits changed */
1179 DUK_DDD(DUK_DDDPRINT("fixed-format rounding carry: B=%ld, roundup_limit=%ld, p=%p, digits=%p",
1180 (long) nc_ctx
->B
, (long) roundup_limit
, (void *) p
, (void *) nc_ctx
->digits
));
1183 DUK_DDD(DUK_DDDPRINT("digit before carry: %ld", (long) t
));
1184 if (++t
< nc_ctx
->B
) {
1185 DUK_DDD(DUK_DDDPRINT("rounding carry terminated"));
1190 DUK_DDD(DUK_DDDPRINT("wraps, carry to next digit"));
1197 #define DUK__NO_EXP (65536) /* arbitrary marker, outside valid exp range */
1199 DUK_LOCAL
void duk__dragon4_convert_and_push(duk__numconv_stringify_ctx
*nc_ctx
,
1201 duk_small_int_t radix
,
1202 duk_small_int_t digits
,
1203 duk_small_uint_t flags
,
1204 duk_small_int_t neg
) {
1206 duk_small_int_t pos
, pos_end
;
1207 duk_small_int_t expt
;
1208 duk_small_int_t dig
;
1213 * The string conversion here incorporates all the necessary Ecmascript
1214 * semantics without attempting to be generic. nc_ctx->digits contains
1215 * nc_ctx->count digits (>= 1), with the topmost digit's 'position'
1216 * indicated by nc_ctx->k as follows:
1218 * digits="123" count=3 k=0 --> 0.123
1219 * digits="123" count=3 k=1 --> 1.23
1220 * digits="123" count=3 k=5 --> 12300
1221 * digits="123" count=3 k=-1 --> 0.0123
1223 * Note that the identifier names used for format selection are different
1224 * in Burger-Dybvig paper and Ecmascript specification (quite confusingly
1225 * so, because e.g. 'k' has a totally different meaning in each). See
1226 * documentation for discussion.
1228 * Ecmascript doesn't specify any specific behavior for format selection
1229 * (e.g. when to use exponent notation) for non-base-10 numbers.
1231 * The bigint space in the context is reused for string output, as there
1232 * is more than enough space for that (>1kB at the moment), and we avoid
1233 * allocating even more stack.
1236 DUK_ASSERT(DUK__NUMCONV_CTX_BIGINTS_SIZE
>= DUK__MAX_FORMATTED_LENGTH
);
1237 DUK_ASSERT(nc_ctx
->count
>= 1);
1240 buf
= (duk_uint8_t
*) &nc_ctx
->f
; /* XXX: union would be more correct */
1243 /* Exponent handling: if exponent format is used, record exponent value and
1244 * fake k such that one leading digit is generated (e.g. digits=123 -> "1.23").
1246 * toFixed() prevents exponent use; otherwise apply a set of criteria to
1247 * match the other API calls (toString(), toPrecision, etc).
1251 if (!nc_ctx
->abs_pos
/* toFixed() */) {
1252 if ((flags
& DUK_N2S_FLAG_FORCE_EXP
) || /* exponential notation forced */
1253 ((flags
& DUK_N2S_FLAG_NO_ZERO_PAD
) && /* fixed precision and zero padding would be required */
1254 (k
- digits
>= 1)) || /* (e.g. k=3, digits=2 -> "12X") */
1255 ((k
> 21 || k
<= -6) && (radix
== 10))) { /* toString() conditions */
1256 DUK_DDD(DUK_DDDPRINT("use exponential notation: k=%ld -> expt=%ld",
1257 (long) k
, (long) (k
- 1)));
1258 expt
= k
- 1; /* e.g. 12.3 -> digits="123" k=2 -> 1.23e1 */
1259 k
= 1; /* generate mantissa with a single leading whole number digit */
1267 /* Start position (inclusive) and end position (exclusive) */
1268 pos
= (k
>= 1 ? k
: 1);
1269 if (nc_ctx
->is_fixed
) {
1270 if (nc_ctx
->abs_pos
) {
1274 pos_end
= k
- digits
;
1277 pos_end
= k
- nc_ctx
->count
;
1283 DUK_DDD(DUK_DDDPRINT("expt=%ld, k=%ld, count=%ld, pos=%ld, pos_end=%ld, is_fixed=%ld, "
1284 "digits=%ld, abs_pos=%ld",
1285 (long) expt
, (long) k
, (long) nc_ctx
->count
, (long) pos
, (long) pos_end
,
1286 (long) nc_ctx
->is_fixed
, (long) digits
, (long) nc_ctx
->abs_pos
));
1288 /* Digit generation */
1289 while (pos
> pos_end
) {
1290 DUK_DDD(DUK_DDDPRINT("digit generation: pos=%ld, pos_end=%ld",
1291 (long) pos
, (long) pos_end
));
1293 *q
++ = (duk_uint8_t
) '.';
1296 *q
++ = (duk_uint8_t
) '0';
1297 } else if (pos
<= k
- nc_ctx
->count
) {
1298 *q
++ = (duk_uint8_t
) '0';
1300 dig
= nc_ctx
->digits
[k
- pos
];
1301 DUK_ASSERT(dig
>= 0 && dig
< nc_ctx
->B
);
1302 *q
++ = (duk_uint8_t
) DUK__DIGITCHAR(dig
);
1307 DUK_ASSERT(pos
<= 1);
1310 if (expt
!= DUK__NO_EXP
) {
1312 * Exponent notation for non-base-10 numbers isn't specified in Ecmascript
1313 * specification, as it never explicitly turns up: non-decimal numbers can
1314 * only be formatted with Number.prototype.toString([radix]) and for that,
1315 * behavior is not explicitly specified.
1317 * Logical choices include formatting the exponent as decimal (e.g. binary
1318 * 100000 as 1e+5) or in current radix (e.g. binary 100000 as 1e+101).
1319 * The Dragon4 algorithm (in the original paper) prints the exponent value
1320 * in the target radix B. However, for radix values 15 and above, the
1321 * exponent separator 'e' is no longer easily parseable. Consider, for
1322 * instance, the number "1.faecee+1c".
1335 *q
++ = (duk_uint8_t
) expt_sign
;
1336 len
= duk__dragon4_format_uint32(q
, (duk_uint32_t
) expt
, radix
);
1340 duk_push_lstring(ctx
, (const char *) buf
, (size_t) (q
- buf
));
1344 * Conversion helpers
1347 DUK_LOCAL
void duk__dragon4_double_to_ctx(duk__numconv_stringify_ctx
*nc_ctx
, duk_double_t x
) {
1350 duk_small_int_t expt
;
1353 * seeeeeee eeeeffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
1357 * eee... exponent field
1360 * ieee value = 1.ffff... * 2^(e - 1023) (normal)
1361 * = 0.ffff... * 2^(-1022) (denormal)
1363 * algorithm v = f * b^e
1366 DUK_DBLUNION_SET_DOUBLE(&u
, x
);
1370 tmp
= DUK_DBLUNION_GET_LOW32(&u
);
1371 nc_ctx
->f
.v
[0] = tmp
;
1372 tmp
= DUK_DBLUNION_GET_HIGH32(&u
);
1373 nc_ctx
->f
.v
[1] = tmp
& 0x000fffffUL
;
1374 expt
= (duk_small_int_t
) ((tmp
>> 20) & 0x07ffUL
);
1378 expt
= DUK__IEEE_DOUBLE_EXP_MIN
- 52;
1379 duk__bi_normalize(&nc_ctx
->f
);
1381 /* normal: implicit leading 1-bit */
1382 nc_ctx
->f
.v
[1] |= 0x00100000UL
;
1383 expt
= expt
- DUK__IEEE_DOUBLE_EXP_BIAS
- 52;
1384 DUK_ASSERT(duk__bi_is_valid(&nc_ctx
->f
)); /* true, because v[1] has at least one bit set */
1387 DUK_ASSERT(duk__bi_is_valid(&nc_ctx
->f
));
1392 DUK_LOCAL
void duk__dragon4_ctx_to_double(duk__numconv_stringify_ctx
*nc_ctx
, duk_double_t
*x
) {
1394 duk_small_int_t expt
;
1396 duk_small_int_t bitstart
;
1397 duk_small_int_t bitround
;
1398 duk_small_int_t bitidx
;
1399 duk_small_int_t skip_round
;
1402 DUK_ASSERT(nc_ctx
->count
== 53 + 1);
1404 /* Sometimes this assert is not true right now; it will be true after
1405 * rounding. See: test-bug-numconv-mantissa-assert.js.
1407 DUK_ASSERT_DISABLE(nc_ctx
->digits
[0] == 1); /* zero handled by caller */
1409 /* Should not be required because the code below always sets both high
1410 * and low parts, but at least gcc-4.4.5 fails to deduce this correctly
1411 * (perhaps because the low part is set (seemingly) conditionally in a
1412 * loop), so this is here to avoid the bogus warning.
1414 DUK_MEMZERO((void *) &u
, sizeof(u
));
1417 * Figure out how generated digits match up with the mantissa,
1418 * and then perform rounding. If mantissa overflows, need to
1419 * recompute the exponent (it is bumped and may overflow to
1422 * For normal numbers the leading '1' is hidden and ignored,
1423 * and the last bit is used for rounding:
1426 * <--------52------->|
1427 * 1 x x x x ... x x x x|y ==> x x x x ... x x x x
1429 * For denormals, the leading '1' is included in the number,
1430 * and the rounding point is different:
1433 * <--52 or less--->|
1434 * 1 x x x x ... x x|x x y ==> 0 0 ... 1 x x ... x x
1436 * The largest denormals will have a mantissa beginning with
1437 * a '1' (the explicit leading bit); smaller denormals will
1438 * have leading zero bits.
1440 * If the exponent would become too high, the result becomes
1441 * Infinity. If the exponent is so small that the entire
1442 * mantissa becomes zero, the result becomes zero.
1444 * Note: the Dragon4 'k' is off-by-one with respect to the IEEE
1445 * exponent. For instance, k==0 indicates that the leading '1'
1446 * digit is at the first binary fraction position (0.1xxx...);
1447 * the corresponding IEEE exponent would be -1.
1454 expt
= nc_ctx
->k
- 1; /* IEEE exp without bias */
1457 bitstart
= -255; /* needed for inf: causes mantissa to become zero,
1458 * and rounding to be skipped.
1461 } else if (expt
>= -1022) {
1463 bitstart
= 1; /* skip leading digit */
1464 expt
+= DUK__IEEE_DOUBLE_EXP_BIAS
;
1465 DUK_ASSERT(expt
>= 1 && expt
<= 2046);
1467 /* denormal or zero */
1468 bitstart
= 1023 + expt
; /* expt==-1023 -> bitstart=0 (leading 1);
1469 * expt==-1024 -> bitstart=-1 (one left of leading 1), etc
1473 bitround
= bitstart
+ 52;
1475 DUK_DDD(DUK_DDDPRINT("ieee expt=%ld, bitstart=%ld, bitround=%ld",
1476 (long) expt
, (long) bitstart
, (long) bitround
));
1479 if (duk__dragon4_fixed_format_round(nc_ctx
, bitround
)) {
1480 /* Corner case: see test-numconv-parse-mant-carry.js. We could
1481 * just bump the exponent and update bitstart, but it's more robust
1482 * to recompute (but avoid rounding twice).
1484 DUK_DDD(DUK_DDDPRINT("rounding caused exponent to be bumped, recheck exponent"));
1495 for (i
= 0; i
< 52; i
++) {
1496 bitidx
= bitstart
+ 52 - 1 - i
;
1497 if (bitidx
>= nc_ctx
->count
) {
1499 } else if (bitidx
< 0) {
1502 v
= nc_ctx
->digits
[bitidx
];
1504 DUK_ASSERT(v
== 0 || v
== 1);
1507 /* low 32 bits is complete */
1508 DUK_DBLUNION_SET_LOW32(&u
, t
);
1512 /* t has high mantissa */
1514 DUK_DDD(DUK_DDDPRINT("mantissa is complete: %08lx %08lx",
1516 (unsigned long) DUK_DBLUNION_GET_LOW32(&u
)));
1518 DUK_ASSERT(expt
>= 0 && expt
<= 0x7ffL
);
1520 #if 0 /* caller handles sign change */
1525 DUK_DBLUNION_SET_HIGH32(&u
, t
);
1527 DUK_DDD(DUK_DDDPRINT("number is complete: %08lx %08lx",
1528 (unsigned long) DUK_DBLUNION_GET_HIGH32(&u
),
1529 (unsigned long) DUK_DBLUNION_GET_LOW32(&u
)));
1531 *x
= DUK_DBLUNION_GET_DOUBLE(&u
);
1535 * Exposed number-to-string API
1538 * Output: [ string ]
1541 DUK_INTERNAL
void duk_numconv_stringify(duk_context
*ctx
, duk_small_int_t radix
, duk_small_int_t digits
, duk_small_uint_t flags
) {
1544 duk_small_int_t neg
;
1546 duk__numconv_stringify_ctx nc_ctx_alloc
; /* large context; around 2kB now */
1547 duk__numconv_stringify_ctx
*nc_ctx
= &nc_ctx_alloc
;
1549 x
= (duk_double_t
) duk_require_number(ctx
, -1);
1553 * Handle special cases (NaN, infinity, zero).
1556 c
= (duk_small_int_t
) DUK_FPCLASSIFY(x
);
1557 if (DUK_SIGNBIT((double) x
)) {
1564 /* NaN sign bit is platform specific with unpacked, un-normalized NaNs */
1565 DUK_ASSERT(c
== DUK_FP_NAN
|| DUK_SIGNBIT((double) x
) == 0);
1567 if (c
== DUK_FP_NAN
) {
1568 duk_push_hstring_stridx(ctx
, DUK_STRIDX_NAN
);
1570 } else if (c
== DUK_FP_INFINITE
) {
1573 duk_push_hstring_stridx(ctx
, DUK_STRIDX_MINUS_INFINITY
);
1576 duk_push_hstring_stridx(ctx
, DUK_STRIDX_INFINITY
);
1579 } else if (c
== DUK_FP_ZERO
) {
1580 /* We can't shortcut zero here if it goes through special formatting
1581 * (such as forced exponential notation).
1587 * Handle integers in 32-bit range (that is, [-(2**32-1),2**32-1])
1588 * specially, as they're very likely for embedded programs. This
1589 * is now done for all radix values. We must be careful not to use
1590 * the fast path when special formatting (e.g. forced exponential)
1593 * XXX: could save space by supporting radix 10 only and using
1594 * sprintf "%lu" for the fast path and for exponent formatting.
1597 uval
= (unsigned int) x
;
1598 if (((double) uval
) == x
&& /* integer number in range */
1599 flags
== 0) { /* no special formatting */
1600 /* use bigint area as a temp */
1601 duk_uint8_t
*buf
= (duk_uint8_t
*) (&nc_ctx
->f
);
1602 duk_uint8_t
*p
= buf
;
1604 DUK_ASSERT(DUK__NUMCONV_CTX_BIGINTS_SIZE
>= 32 + 1); /* max size: radix=2 + sign */
1605 if (neg
&& uval
!= 0) {
1606 /* no negative sign for zero */
1607 *p
++ = (duk_uint8_t
) '-';
1609 p
+= duk__dragon4_format_uint32(p
, uval
, radix
);
1610 duk_push_lstring(ctx
, (const char *) buf
, (duk_size_t
) (p
- buf
));
1617 * Convert double from IEEE representation for conversion;
1618 * normal finite values have an implicit leading 1-bit. The
1619 * slow path algorithm doesn't handle zero, so zero is special
1620 * cased here but still creates a valid nc_ctx, and goes
1621 * through normal formatting in case special formatting has
1622 * been requested (e.g. forced exponential format: 0 -> "0e+0").
1625 /* Would be nice to bulk clear the allocation, but the context
1626 * is 1-2 kilobytes and nothing should rely on it being zeroed.
1629 DUK_MEMZERO((void *) nc_ctx
, sizeof(*nc_ctx
)); /* slow init, do only for slow path cases */
1635 nc_ctx
->abs_pos
= 0;
1636 if (flags
& DUK_N2S_FLAG_FIXED_FORMAT
) {
1637 nc_ctx
->is_fixed
= 1;
1638 if (flags
& DUK_N2S_FLAG_FRACTION_DIGITS
) {
1639 /* absolute req_digits; e.g. digits = 1 -> last digit is 0,
1640 * but add an extra digit for rounding.
1642 nc_ctx
->abs_pos
= 1;
1643 nc_ctx
->req_digits
= (-digits
+ 1) - 1;
1645 nc_ctx
->req_digits
= digits
+ 1;
1648 nc_ctx
->is_fixed
= 0;
1649 nc_ctx
->req_digits
= 0;
1652 if (c
== DUK_FP_ZERO
) {
1653 /* Zero special case: fake requested number of zero digits; ensure
1654 * no sign bit is printed. Relative and absolute fixed format
1655 * require separate handling.
1657 duk_small_int_t count
;
1658 if (nc_ctx
->is_fixed
) {
1659 if (nc_ctx
->abs_pos
) {
1660 count
= digits
+ 2; /* lead zero + 'digits' fractions + 1 for rounding */
1662 count
= digits
+ 1; /* + 1 for rounding */
1667 DUK_DDD(DUK_DDDPRINT("count=%ld", (long) count
));
1668 DUK_ASSERT(count
>= 1);
1669 DUK_MEMZERO((void *) nc_ctx
->digits
, count
);
1670 nc_ctx
->count
= count
;
1671 nc_ctx
->k
= 1; /* 0.000... */
1676 duk__dragon4_double_to_ctx(nc_ctx
, x
); /* -> sets 'f' and 'e' */
1677 DUK__BI_PRINT("f", &nc_ctx
->f
);
1678 DUK_DDD(DUK_DDDPRINT("e=%ld", (long) nc_ctx
->e
));
1681 * Dragon4 slow path digit generation.
1684 duk__dragon4_prepare(nc_ctx
); /* setup many variables in nc_ctx */
1686 DUK_DDD(DUK_DDDPRINT("after prepare:"));
1687 DUK__BI_PRINT("r", &nc_ctx
->r
);
1688 DUK__BI_PRINT("s", &nc_ctx
->s
);
1689 DUK__BI_PRINT("mp", &nc_ctx
->mp
);
1690 DUK__BI_PRINT("mm", &nc_ctx
->mm
);
1692 duk__dragon4_scale(nc_ctx
);
1694 DUK_DDD(DUK_DDDPRINT("after scale; k=%ld", (long) nc_ctx
->k
));
1695 DUK__BI_PRINT("r", &nc_ctx
->r
);
1696 DUK__BI_PRINT("s", &nc_ctx
->s
);
1697 DUK__BI_PRINT("mp", &nc_ctx
->mp
);
1698 DUK__BI_PRINT("mm", &nc_ctx
->mm
);
1700 duk__dragon4_generate(nc_ctx
);
1703 * Convert and push final string.
1708 if (flags
& DUK_N2S_FLAG_FIXED_FORMAT
) {
1709 /* Perform fixed-format rounding. */
1710 duk_small_int_t roundpos
;
1711 if (flags
& DUK_N2S_FLAG_FRACTION_DIGITS
) {
1712 /* 'roundpos' is relative to nc_ctx->k and increases to the right
1713 * (opposite of how 'k' changes).
1715 roundpos
= -digits
; /* absolute position for digit considered for rounding */
1716 roundpos
= nc_ctx
->k
- roundpos
;
1720 DUK_DDD(DUK_DDDPRINT("rounding: k=%ld, count=%ld, digits=%ld, roundpos=%ld",
1721 (long) nc_ctx
->k
, (long) nc_ctx
->count
, (long) digits
, (long) roundpos
));
1722 (void) duk__dragon4_fixed_format_round(nc_ctx
, roundpos
);
1724 /* Note: 'count' is currently not adjusted by rounding (i.e. the
1725 * digits are not "chopped off". That shouldn't matter because
1726 * the digit position (absolute or relative) is passed on to the
1727 * convert-and-push function.
1731 duk__dragon4_convert_and_push(nc_ctx
, ctx
, radix
, digits
, flags
, neg
);
1735 * Exposed string-to-number API
1738 * Output: [ number ]
1740 * If number parsing fails, a NaN is pushed as the result. If number parsing
1741 * fails due to an internal error, an InternalError is thrown.
1744 DUK_INTERNAL
void duk_numconv_parse(duk_context
*ctx
, duk_small_int_t radix
, duk_small_uint_t flags
) {
1745 duk_hthread
*thr
= (duk_hthread
*) ctx
;
1746 duk__numconv_stringify_ctx nc_ctx_alloc
; /* large context; around 2kB now */
1747 duk__numconv_stringify_ctx
*nc_ctx
= &nc_ctx_alloc
;
1750 duk_small_int_t expt
;
1751 duk_small_int_t expt_neg
;
1752 duk_small_int_t expt_adj
;
1753 duk_small_int_t neg
;
1754 duk_small_int_t dig
;
1755 duk_small_int_t dig_whole
;
1756 duk_small_int_t dig_lzero
;
1757 duk_small_int_t dig_frac
;
1758 duk_small_int_t dig_expt
;
1759 duk_small_int_t dig_prec
;
1760 const duk__exp_limits
*explim
;
1761 const duk_uint8_t
*p
;
1764 /* This seems to waste a lot of stack frame entries, but good compilers
1765 * will compute these as needed below. Some of these initial flags are
1766 * also modified in the code below, so they can't all be removed.
1768 duk_small_int_t trim_white
= (flags
& DUK_S2N_FLAG_TRIM_WHITE
);
1769 duk_small_int_t allow_expt
= (flags
& DUK_S2N_FLAG_ALLOW_EXP
);
1770 duk_small_int_t allow_garbage
= (flags
& DUK_S2N_FLAG_ALLOW_GARBAGE
);
1771 duk_small_int_t allow_plus
= (flags
& DUK_S2N_FLAG_ALLOW_PLUS
);
1772 duk_small_int_t allow_minus
= (flags
& DUK_S2N_FLAG_ALLOW_MINUS
);
1773 duk_small_int_t allow_infinity
= (flags
& DUK_S2N_FLAG_ALLOW_INF
);
1774 duk_small_int_t allow_frac
= (flags
& DUK_S2N_FLAG_ALLOW_FRAC
);
1775 duk_small_int_t allow_naked_frac
= (flags
& DUK_S2N_FLAG_ALLOW_NAKED_FRAC
);
1776 duk_small_int_t allow_empty_frac
= (flags
& DUK_S2N_FLAG_ALLOW_EMPTY_FRAC
);
1777 duk_small_int_t allow_empty
= (flags
& DUK_S2N_FLAG_ALLOW_EMPTY_AS_ZERO
);
1778 duk_small_int_t allow_leading_zero
= (flags
& DUK_S2N_FLAG_ALLOW_LEADING_ZERO
);
1779 duk_small_int_t allow_auto_hex_int
= (flags
& DUK_S2N_FLAG_ALLOW_AUTO_HEX_INT
);
1780 duk_small_int_t allow_auto_oct_int
= (flags
& DUK_S2N_FLAG_ALLOW_AUTO_OCT_INT
);
1782 DUK_DDD(DUK_DDDPRINT("parse number: %!T, radix=%ld, flags=0x%08lx",
1783 (duk_tval
*) duk_get_tval(ctx
, -1),
1784 (long) radix
, (unsigned long) flags
));
1786 DUK_ASSERT(radix
>= 2 && radix
<= 36);
1787 DUK_ASSERT(radix
- 2 < (duk_small_int_t
) sizeof(duk__str2num_digits_for_radix
));
1790 * Preliminaries: trim, sign, Infinity check
1792 * We rely on the interned string having a NUL terminator, which will
1793 * cause a parse failure wherever it is encountered. As a result, we
1794 * don't need separate pointer checks.
1796 * There is no special parsing for 'NaN' in the specification although
1797 * 'Infinity' (with an optional sign) is allowed in some contexts.
1798 * Some contexts allow plus/minus sign, while others only allow the
1799 * minus sign (like JSON.parse()).
1801 * Automatic hex number detection (leading '0x' or '0X') and octal
1802 * number detection (leading '0' followed by at least one octal digit)
1807 /* Leading / trailing whitespace is sometimes accepted and
1808 * sometimes not. After white space trimming, all valid input
1809 * characters are pure ASCII.
1813 h_str
= duk_require_hstring(ctx
, -1);
1814 DUK_ASSERT(h_str
!= NULL
);
1815 p
= (const duk_uint8_t
*) DUK_HSTRING_GET_DATA(h_str
);
1819 if (ch
== (duk_small_int_t
) '+') {
1821 DUK_DDD(DUK_DDDPRINT("parse failed: leading plus sign not allowed"));
1825 } else if (ch
== (duk_small_int_t
) '-') {
1827 DUK_DDD(DUK_DDDPRINT("parse failed: leading minus sign not allowed"));
1835 if (allow_infinity
&& ch
== (duk_small_int_t
) 'I') {
1836 /* Don't check for Infinity unless the context allows it.
1837 * 'Infinity' is a valid integer literal in e.g. base-36:
1839 * parseInt('Infinity', 36)
1843 const duk_uint8_t
*q
;
1845 /* borrow literal Infinity from builtin string */
1846 q
= (const duk_uint8_t
*) DUK_HSTRING_GET_DATA(DUK_HTHREAD_STRING_INFINITY(thr
));
1847 if (DUK_STRNCMP((const char *) p
, (const char *) q
, 8) == 0) {
1848 if (!allow_garbage
&& (p
[8] != (duk_uint8_t
) 0)) {
1849 DUK_DDD(DUK_DDDPRINT("parse failed: trailing garbage after matching 'Infinity' not allowed"));
1852 res
= DUK_DOUBLE_INFINITY
;
1853 goto negcheck_and_ret
;
1857 if (ch
== (duk_small_int_t
) '0') {
1858 duk_small_int_t detect_radix
= 0;
1860 if (allow_auto_hex_int
&& (ch
== (duk_small_int_t
) 'x' || ch
== (duk_small_int_t
) 'X')) {
1861 DUK_DDD(DUK_DDDPRINT("detected 0x/0X hex prefix, changing radix and preventing fractions and exponent"));
1863 allow_empty
= 0; /* interpret e.g. '0x' and '0xg' as a NaN (= parse error) */
1865 } else if (allow_auto_oct_int
&& (ch
>= (duk_small_int_t
) '0' && ch
<= (duk_small_int_t
) '9')) {
1866 DUK_DDD(DUK_DDDPRINT("detected 0n oct prefix, changing radix and preventing fractions and exponent"));
1868 allow_empty
= 1; /* interpret e.g. '09' as '0', not NaN */
1871 if (detect_radix
> 0) {
1872 radix
= detect_radix
;
1875 allow_naked_frac
= 0;
1876 allow_empty_frac
= 0;
1877 allow_leading_zero
= 1; /* allow e.g. '0x0009' and '00077' */
1882 * Scan number and setup for Dragon4.
1884 * The fast path case is detected during setup: an integer which
1885 * can be converted without rounding, no net exponent. The fast
1886 * path could be implemented as a separate scan, but may not really
1887 * be worth it: the multiplications for building 'f' are not
1888 * expensive when 'f' is small.
1890 * The significand ('f') must contain enough bits of (apparent)
1891 * accuracy, so that Dragon4 will generate enough binary output digits.
1892 * For decimal numbers, this means generating a 20-digit significand,
1893 * which should yield enough practical accuracy to parse IEEE doubles.
1894 * In fact, the Ecmascript specification explicitly allows an
1895 * implementation to treat digits beyond 20 as zeroes (and even
1896 * to round the 20th digit upwards). For non-decimal numbers, the
1897 * appropriate number of digits has been precomputed for comparable
1904 * .+-..---[ dig_prec ]----.
1906 * 0000123.456789012345678901234567890e+123456
1908 * `--+--' `------[ dig_frac ]-------' `-+--'
1910 * [ dig_whole ] [ dig_expt ]
1912 * dig_frac and dig_expt are -1 if not present
1913 * dig_lzero is only computed for whole number part
1917 * Parsing whole part dig_frac < 0 AND dig_expt < 0
1918 * Parsing fraction part dig_frac >= 0 AND dig_expt < 0
1919 * Parsing exponent part dig_expt >= 0 (dig_frac may be < 0 or >= 0)
1921 * Note: in case we hit an implementation limit (like exponent range),
1922 * we should throw an error, NOT return NaN or Infinity. Even with
1923 * very large exponent (or significand) values the final result may be
1924 * finite, so NaN/Infinity would be incorrect.
1927 duk__bi_set_small(&nc_ctx
->f
, 0);
1934 expt_adj
= 0; /* essentially tracks digit position of lowest 'f' digit */
1939 DUK_DDD(DUK_DDDPRINT("parse digits: p=%p, ch='%c' (%ld), expt=%ld, expt_adj=%ld, "
1940 "dig_whole=%ld, dig_frac=%ld, dig_expt=%ld, dig_lzero=%ld, dig_prec=%ld",
1941 (void *) p
, (int) ((ch
>= 0x20 && ch
<= 0x7e) ? ch
: '?'), (long) ch
,
1942 (long) expt
, (long) expt_adj
, (long) dig_whole
, (long) dig_frac
,
1943 (long) dig_expt
, (long) dig_lzero
, (long) dig_prec
));
1944 DUK__BI_PRINT("f", &nc_ctx
->f
);
1946 /* Most common cases first. */
1947 if (ch
>= (duk_small_int_t
) '0' && ch
<= (duk_small_int_t
) '9') {
1948 dig
= (int) ch
- '0' + 0;
1949 } else if (ch
== (duk_small_int_t
) '.') {
1950 /* A leading digit is not required in some cases, e.g. accept ".123".
1951 * In other cases (JSON.parse()) a leading digit is required. This
1952 * is checked for after the loop.
1954 if (dig_frac
>= 0 || dig_expt
>= 0) {
1955 if (allow_garbage
) {
1956 DUK_DDD(DUK_DDDPRINT("garbage termination (invalid period)"));
1959 DUK_DDD(DUK_DDDPRINT("parse failed: period not allowed"));
1965 /* Some contexts don't allow fractions at all; this can't be a
1966 * post-check because the state ('f' and expt) would be incorrect.
1968 if (allow_garbage
) {
1969 DUK_DDD(DUK_DDDPRINT("garbage termination (invalid first period)"));
1972 DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed"));
1976 DUK_DDD(DUK_DDDPRINT("start fraction part"));
1979 } else if (ch
== (duk_small_int_t
) 0) {
1980 DUK_DDD(DUK_DDDPRINT("NUL termination"));
1982 } else if (allow_expt
&& dig_expt
< 0 && (ch
== (duk_small_int_t
) 'e' || ch
== (duk_small_int_t
) 'E')) {
1983 /* Note: we don't parse back exponent notation for anything else
1984 * than radix 10, so this is not an ambiguous check (e.g. hex
1985 * exponent values may have 'e' either as a significand digit
1986 * or as an exponent separator).
1988 * If the exponent separator occurs twice, 'e' will be interpreted
1989 * as a digit (= 14) and will be rejected as an invalid decimal
1993 DUK_DDD(DUK_DDDPRINT("start exponent part"));
1995 /* Exponent without a sign or with a +/- sign is accepted
1996 * by all call sites (even JSON.parse()).
1999 if (ch
== (duk_small_int_t
) '-') {
2002 } else if (ch
== (duk_small_int_t
) '+') {
2007 } else if (ch
>= (duk_small_int_t
) 'a' && ch
<= (duk_small_int_t
) 'z') {
2008 dig
= (duk_small_int_t
) (ch
- (duk_small_int_t
) 'a' + 0x0a);
2009 } else if (ch
>= (duk_small_int_t
) 'A' && ch
<= (duk_small_int_t
) 'Z') {
2010 dig
= (duk_small_int_t
) (ch
- (duk_small_int_t
) 'A' + 0x0a);
2012 dig
= 255; /* triggers garbage digit check below */
2014 DUK_ASSERT((dig
>= 0 && dig
<= 35) || dig
== 255);
2017 if (allow_garbage
) {
2018 DUK_DDD(DUK_DDDPRINT("garbage termination"));
2021 DUK_DDD(DUK_DDDPRINT("parse failed: trailing garbage or invalid digit"));
2027 /* whole or fraction digit */
2029 if (dig_prec
< duk__str2num_digits_for_radix
[radix
- 2]) {
2030 /* significant from precision perspective */
2032 duk_small_int_t f_zero
= duk__bi_is_zero(&nc_ctx
->f
);
2033 if (f_zero
&& dig
== 0) {
2034 /* Leading zero is not counted towards precision digits; not
2035 * in the integer part, nor in the fraction part.
2041 /* XXX: join these ops (multiply-accumulate), but only if
2042 * code footprint decreases.
2044 duk__bi_mul_small(&nc_ctx
->t1
, &nc_ctx
->f
, radix
);
2045 duk__bi_add_small(&nc_ctx
->f
, &nc_ctx
->t1
, dig
);
2049 /* Ignore digits beyond a radix-specific limit, but note them
2055 if (dig_frac
>= 0) {
2062 /* exponent digit */
2064 expt
= expt
* radix
+ dig
;
2065 if (expt
> DUK_S2N_MAX_EXPONENT
) {
2066 /* impose a reasonable exponent limit, so that exp
2067 * doesn't need to get tracked using a bigint.
2069 DUK_DDD(DUK_DDDPRINT("parse failed: exponent too large"));
2070 goto parse_int_error
;
2078 if (dig_lzero
> 0 && dig_whole
> 1) {
2079 if (!allow_leading_zero
) {
2080 DUK_DDD(DUK_DDDPRINT("parse failed: leading zeroes not allowed in integer part"));
2085 /* Validity checks for various fraction formats ("0.1", ".1", "1.", "."). */
2087 if (dig_whole
== 0) {
2088 if (dig_frac
== 0) {
2089 /* "." is not accepted in any format */
2090 DUK_DDD(DUK_DDDPRINT("parse failed: plain period without leading or trailing digits"));
2092 } else if (dig_frac
> 0) {
2094 if (!allow_naked_frac
) {
2095 DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed without "
2096 "leading integer digit(s)"));
2100 /* empty ("") is allowed in some formats (e.g. Number(''), as zero */
2102 DUK_DDD(DUK_DDDPRINT("parse failed: empty string not allowed (as zero)"));
2107 if (dig_frac
== 0) {
2108 /* "123." is allowed in some formats */
2109 if (!allow_empty_frac
) {
2110 DUK_DDD(DUK_DDDPRINT("parse failed: empty fractions"));
2113 } else if (dig_frac
> 0) {
2122 /* Exponent without digits (e.g. "1e" or "1e+"). If trailing garbage is
2123 * allowed, ignore exponent part as garbage (= parse as "1", i.e. exp 0).
2126 if (dig_expt
== 0) {
2127 if (!allow_garbage
) {
2128 DUK_DDD(DUK_DDDPRINT("parse failed: empty exponent"));
2131 DUK_ASSERT(expt
== 0);
2137 DUK_DDD(DUK_DDDPRINT("expt=%ld, expt_adj=%ld, net exponent -> %ld",
2138 (long) expt
, (long) expt_adj
, (long) (expt
+ expt_adj
)));
2141 /* Fast path check. */
2143 if (nc_ctx
->f
.n
<= 1 && /* 32-bit value */
2144 expt
== 0 /* no net exponent */) {
2145 /* Fast path is triggered for no exponent and also for balanced exponent
2146 * and fraction parts, e.g. for "1.23e2" == "123". Remember to respect
2150 /* XXX: could accept numbers larger than 32 bits, e.g. up to 53 bits? */
2151 DUK_DDD(DUK_DDDPRINT("fast path number parse"));
2152 if (nc_ctx
->f
.n
== 1) {
2153 res
= (double) nc_ctx
->f
.v
[0];
2157 goto negcheck_and_ret
;
2160 /* Significand ('f') padding. */
2162 while (dig_prec
< duk__str2num_digits_for_radix
[radix
- 2]) {
2163 /* Pad significand with "virtual" zero digits so that Dragon4 will
2164 * have enough (apparent) precision to work with.
2166 DUK_DDD(DUK_DDDPRINT("dig_prec=%ld, pad significand with zero", (long) dig_prec
));
2167 duk__bi_mul_small_copy(&nc_ctx
->f
, radix
, &nc_ctx
->t1
);
2168 DUK__BI_PRINT("f", &nc_ctx
->f
);
2173 DUK_DDD(DUK_DDDPRINT("final exponent: %ld", (long) expt
));
2175 /* Detect zero special case. */
2177 if (nc_ctx
->f
.n
== 0) {
2178 /* This may happen even after the fast path check, if exponent is
2179 * not balanced (e.g. "0e1"). Remember to respect zero sign.
2181 DUK_DDD(DUK_DDDPRINT("significand is zero"));
2183 goto negcheck_and_ret
;
2187 /* Quick reject of too large or too small exponents. This check
2188 * would be incorrect for zero (e.g. "0e1000" is zero, not Infinity)
2189 * so zero check must be above.
2192 explim
= &duk__str2num_exp_limits
[radix
- 2];
2193 if (expt
> explim
->upper
) {
2194 DUK_DDD(DUK_DDDPRINT("exponent too large -> infinite"));
2195 res
= (duk_double_t
) DUK_DOUBLE_INFINITY
;
2196 goto negcheck_and_ret
;
2197 } else if (expt
< explim
->lower
) {
2198 DUK_DDD(DUK_DDDPRINT("exponent too small -> zero"));
2199 res
= (duk_double_t
) 0.0;
2200 goto negcheck_and_ret
;
2207 nc_ctx
->is_fixed
= 1;
2208 nc_ctx
->abs_pos
= 0;
2209 nc_ctx
->req_digits
= 53 + 1;
2211 DUK__BI_PRINT("f", &nc_ctx
->f
);
2212 DUK_DDD(DUK_DDDPRINT("e=%ld", (long) nc_ctx
->e
));
2215 * Dragon4 slow path (binary) digit generation.
2216 * An extra digit is generated for rounding.
2219 duk__dragon4_prepare(nc_ctx
); /* setup many variables in nc_ctx */
2221 DUK_DDD(DUK_DDDPRINT("after prepare:"));
2222 DUK__BI_PRINT("r", &nc_ctx
->r
);
2223 DUK__BI_PRINT("s", &nc_ctx
->s
);
2224 DUK__BI_PRINT("mp", &nc_ctx
->mp
);
2225 DUK__BI_PRINT("mm", &nc_ctx
->mm
);
2227 duk__dragon4_scale(nc_ctx
);
2229 DUK_DDD(DUK_DDDPRINT("after scale; k=%ld", (long) nc_ctx
->k
));
2230 DUK__BI_PRINT("r", &nc_ctx
->r
);
2231 DUK__BI_PRINT("s", &nc_ctx
->s
);
2232 DUK__BI_PRINT("mp", &nc_ctx
->mp
);
2233 DUK__BI_PRINT("mm", &nc_ctx
->mm
);
2235 duk__dragon4_generate(nc_ctx
);
2237 DUK_ASSERT(nc_ctx
->count
== 53 + 1);
2240 * Convert binary digits into an IEEE double. Need to handle
2241 * denormals and rounding correctly.
2244 duk__dragon4_ctx_to_double(nc_ctx
, &res
);
2245 goto negcheck_and_ret
;
2252 duk_push_number(ctx
, (double) res
);
2253 DUK_DDD(DUK_DDDPRINT("result: %!T", (duk_tval
*) duk_get_tval(ctx
, -1)));
2257 DUK_DDD(DUK_DDDPRINT("parse failed"));
2263 DUK_DDD(DUK_DDDPRINT("parse failed, internal error, can't return a value"));
2264 DUK_ERROR(thr
, DUK_ERR_INTERNAL_ERROR
, "number parse error");