1 /*
2 * Number-to-string and string-to-number conversions.
3 *
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.
9 *
10 * See: doc/number-conversion.rst.
11 */
12
13 #include "duk_internal.h"
14
15 #define DUK__IEEE_DOUBLE_EXP_BIAS 1023
16 #define DUK__IEEE_DOUBLE_EXP_MIN (-1022) /* biased exp == 0 -> denormal, exp -1022 */
17
18 #define DUK__DIGITCHAR(x) duk_lc_digits[(x)]
19
20 /*
21 * Tables generated with util/gennumdigits.py.
22 *
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.
27 *
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
32 * bounded.
33 */
34
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 */
40 };
41
42 typedef struct {
43 duk_int16_t upper;
44 duk_int16_t lower;
45 } duk__exp_limits;
46
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 },
57 };
58
59 /*
60 * Limited functionality bigint implementation.
61 *
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.
66 *
67 * Argument order is "assignment order", i.e. target first, then arguments:
68 * x <- y * z --> duk__bi_mul(x, y, z);
69 */
70
71 /* This upper value has been experimentally determined; debug build will check
72 * bigint size with assertions.
73 */
74 #define DUK__BI_MAX_PARTS 37 /* 37x32 = 1184 bits */
75
76 #if defined(DUK_USE_DEBUG_LEVEL) && (DUK_USE_DEBUG_LEVEL >= 2)
77 #define DUK__BI_PRINT(name,x) duk__bi_print((name),(x))
78 #else
79 #define DUK__BI_PRINT(name,x)
80 #endif
81
82 /* Current size is about 152 bytes. */
83 typedef struct {
84 duk_small_int_t n;
85 duk_uint32_t v[DUK__BI_MAX_PARTS]; /* low to high */
86 } duk__bigint;
87
88 #if defined(DUK_USE_DEBUG_LEVEL) && (DUK_USE_DEBUG_LEVEL >= 2)
duk__bi_print(const char * name,duk__bigint * x)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];
92 char *p = buf;
93 duk_small_int_t i;
94
95 /* No NUL term checks in this debug code. */
96 p += DUK_SPRINTF(p, "%p n=%ld", (void *) x, (long) x->n);
97 if (x->n == 0) {
98 p += DUK_SPRINTF(p, " 0");
99 }
100 for (i = x->n - 1; i >= 0; i--) {
101 p += DUK_SPRINTF(p, " %08lx", (unsigned long) x->v[i]);
102 }
103
104 DUK_DDD(DUK_DDDPRINT("%s: %s", (const char *) name, (const char *) buf));
105 }
106 #endif
107
108 #if defined(DUK_USE_ASSERTIONS)
duk__bi_is_valid(duk__bigint * x)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 */ );
113 }
114 #endif
115
duk__bi_normalize(duk__bigint * x)116 DUK_LOCAL void duk__bi_normalize(duk__bigint *x) {
117 duk_small_int_t i;
118
119 for (i = x->n - 1; i >= 0; i--) {
120 if (x->v[i] != 0) {
121 break;
122 }
123 }
124
125 /* Note: if 'x' is zero, x->n becomes 0 here */
126 x->n = i + 1;
127 DUK_ASSERT(duk__bi_is_valid(x));
128 }
129
130 /* x <- y */
duk__bi_copy(duk__bigint * x,duk__bigint * y)131 DUK_LOCAL void duk__bi_copy(duk__bigint *x, duk__bigint *y) {
132 duk_small_int_t n;
133
134 n = y->n;
135 x->n = n;
136 /* No need to special case n == 0. */
137 duk_memcpy((void *) x->v, (const void *) y->v, (size_t) (sizeof(duk_uint32_t) * (size_t) n));
138 }
139
duk__bi_set_small(duk__bigint * x,duk_uint32_t v)140 DUK_LOCAL void duk__bi_set_small(duk__bigint *x, duk_uint32_t v) {
141 if (v == 0U) {
142 x->n = 0;
143 } else {
144 x->n = 1;
145 x->v[0] = v;
146 }
147 DUK_ASSERT(duk__bi_is_valid(x));
148 }
149
150 /* Return value: <0 <=> x < y
151 * 0 <=> x == y
152 * >0 <=> x > y
153 */
duk__bi_compare(duk__bigint * x,duk__bigint * y)154 DUK_LOCAL int duk__bi_compare(duk__bigint *x, duk__bigint *y) {
155 duk_small_int_t i, nx, ny;
156 duk_uint32_t tx, ty;
157
158 DUK_ASSERT(duk__bi_is_valid(x));
159 DUK_ASSERT(duk__bi_is_valid(y));
160
161 nx = x->n;
162 ny = y->n;
163 if (nx > ny) {
164 goto ret_gt;
165 }
166 if (nx < ny) {
167 goto ret_lt;
168 }
169 for (i = nx - 1; i >= 0; i--) {
170 tx = x->v[i];
171 ty = y->v[i];
172
173 if (tx > ty) {
174 goto ret_gt;
175 }
176 if (tx < ty) {
177 goto ret_lt;
178 }
179 }
180
181 return 0;
182
183 ret_gt:
184 return 1;
185
186 ret_lt:
187 return -1;
188 }
189
190 /* x <- y + z */
191 #if defined(DUK_USE_64BIT_OPS)
duk__bi_add(duk__bigint * x,duk__bigint * y,duk__bigint * z)192 DUK_LOCAL void duk__bi_add(duk__bigint *x, duk__bigint *y, duk__bigint *z) {
193 duk_uint64_t tmp;
194 duk_small_int_t i, ny, nz;
195
196 DUK_ASSERT(duk__bi_is_valid(y));
197 DUK_ASSERT(duk__bi_is_valid(z));
198
199 if (z->n > y->n) {
200 duk__bigint *t;
201 t = y; y = z; z = t;
202 }
203 DUK_ASSERT(y->n >= z->n);
204
205 ny = y->n; nz = z->n;
206 tmp = 0U;
207 for (i = 0; i < ny; i++) {
208 DUK_ASSERT(i < DUK__BI_MAX_PARTS);
209 tmp += y->v[i];
210 if (i < nz) {
211 tmp += z->v[i];
212 }
213 x->v[i] = (duk_uint32_t) (tmp & 0xffffffffUL);
214 tmp = tmp >> 32;
215 }
216 if (tmp != 0U) {
217 DUK_ASSERT(i < DUK__BI_MAX_PARTS);
218 x->v[i++] = (duk_uint32_t) tmp;
219 }
220 x->n = i;
221 DUK_ASSERT(x->n <= DUK__BI_MAX_PARTS);
222
223 /* no need to normalize */
224 DUK_ASSERT(duk__bi_is_valid(x));
225 }
226 #else /* DUK_USE_64BIT_OPS */
duk__bi_add(duk__bigint * x,duk__bigint * y,duk__bigint * z)227 DUK_LOCAL void duk__bi_add(duk__bigint *x, duk__bigint *y, duk__bigint *z) {
228 duk_uint32_t carry, tmp1, tmp2;
229 duk_small_int_t i, ny, nz;
230
231 DUK_ASSERT(duk__bi_is_valid(y));
232 DUK_ASSERT(duk__bi_is_valid(z));
233
234 if (z->n > y->n) {
235 duk__bigint *t;
236 t = y; y = z; z = t;
237 }
238 DUK_ASSERT(y->n >= z->n);
239
240 ny = y->n; nz = z->n;
241 carry = 0U;
242 for (i = 0; i < ny; i++) {
243 /* Carry is detected based on wrapping which relies on exact 32-bit
244 * types.
245 */
246 DUK_ASSERT(i < DUK__BI_MAX_PARTS);
247 tmp1 = y->v[i];
248 tmp2 = tmp1;
249 if (i < nz) {
250 tmp2 += z->v[i];
251 }
252
253 /* Careful with carry condition:
254 * - If carry not added: 0x12345678 + 0 + 0xffffffff = 0x12345677 (< 0x12345678)
255 * - If carry added: 0x12345678 + 1 + 0xffffffff = 0x12345678 (== 0x12345678)
256 */
257 if (carry) {
258 tmp2++;
259 carry = (tmp2 <= tmp1 ? 1U : 0U);
260 } else {
261 carry = (tmp2 < tmp1 ? 1U : 0U);
262 }
263
264 x->v[i] = tmp2;
265 }
266 if (carry) {
267 DUK_ASSERT(i < DUK__BI_MAX_PARTS);
268 DUK_ASSERT(carry == 1U);
269 x->v[i++] = carry;
270 }
271 x->n = i;
272 DUK_ASSERT(x->n <= DUK__BI_MAX_PARTS);
273
274 /* no need to normalize */
275 DUK_ASSERT(duk__bi_is_valid(x));
276 }
277 #endif /* DUK_USE_64BIT_OPS */
278
279 /* x <- y + z */
duk__bi_add_small(duk__bigint * x,duk__bigint * y,duk_uint32_t z)280 DUK_LOCAL void duk__bi_add_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) {
281 duk__bigint tmp;
282
283 DUK_ASSERT(duk__bi_is_valid(y));
284
285 /* XXX: this could be optimized; there is only one call site now though */
286 duk__bi_set_small(&tmp, z);
287 duk__bi_add(x, y, &tmp);
288
289 DUK_ASSERT(duk__bi_is_valid(x));
290 }
291
292 #if 0 /* unused */
293 /* x <- x + y, use t as temp */
294 DUK_LOCAL void duk__bi_add_copy(duk__bigint *x, duk__bigint *y, duk__bigint *t) {
295 duk__bi_add(t, x, y);
296 duk__bi_copy(x, t);
297 }
298 #endif
299
300 /* x <- y - z, require x >= y => z >= 0, i.e. y >= z */
301 #if defined(DUK_USE_64BIT_OPS)
duk__bi_sub(duk__bigint * x,duk__bigint * y,duk__bigint * z)302 DUK_LOCAL void duk__bi_sub(duk__bigint *x, duk__bigint *y, duk__bigint *z) {
303 duk_small_int_t i, ny, nz;
304 duk_uint32_t ty, tz;
305 duk_int64_t tmp;
306
307 DUK_ASSERT(duk__bi_is_valid(y));
308 DUK_ASSERT(duk__bi_is_valid(z));
309 DUK_ASSERT(duk__bi_compare(y, z) >= 0);
310 DUK_ASSERT(y->n >= z->n);
311
312 ny = y->n; nz = z->n;
313 tmp = 0;
314 for (i = 0; i < ny; i++) {
315 ty = y->v[i];
316 if (i < nz) {
317 tz = z->v[i];
318 } else {
319 tz = 0;
320 }
321 tmp = (duk_int64_t) ty - (duk_int64_t) tz + tmp;
322 x->v[i] = (duk_uint32_t) ((duk_uint64_t) tmp & 0xffffffffUL);
323 tmp = tmp >> 32; /* 0 or -1 */
324 }
325 DUK_ASSERT(tmp == 0);
326
327 x->n = i;
328 duk__bi_normalize(x); /* need to normalize, may even cancel to 0 */
329 DUK_ASSERT(duk__bi_is_valid(x));
330 }
331 #else
duk__bi_sub(duk__bigint * x,duk__bigint * y,duk__bigint * z)332 DUK_LOCAL void duk__bi_sub(duk__bigint *x, duk__bigint *y, duk__bigint *z) {
333 duk_small_int_t i, ny, nz;
334 duk_uint32_t tmp1, tmp2, borrow;
335
336 DUK_ASSERT(duk__bi_is_valid(y));
337 DUK_ASSERT(duk__bi_is_valid(z));
338 DUK_ASSERT(duk__bi_compare(y, z) >= 0);
339 DUK_ASSERT(y->n >= z->n);
340
341 ny = y->n; nz = z->n;
342 borrow = 0U;
343 for (i = 0; i < ny; i++) {
344 /* Borrow is detected based on wrapping which relies on exact 32-bit
345 * types.
346 */
347 tmp1 = y->v[i];
348 tmp2 = tmp1;
349 if (i < nz) {
350 tmp2 -= z->v[i];
351 }
352
353 /* Careful with borrow condition:
354 * - If borrow not subtracted: 0x12345678 - 0 - 0xffffffff = 0x12345679 (> 0x12345678)
355 * - If borrow subtracted: 0x12345678 - 1 - 0xffffffff = 0x12345678 (== 0x12345678)
356 */
357 if (borrow) {
358 tmp2--;
359 borrow = (tmp2 >= tmp1 ? 1U : 0U);
360 } else {
361 borrow = (tmp2 > tmp1 ? 1U : 0U);
362 }
363
364 x->v[i] = tmp2;
365 }
366 DUK_ASSERT(borrow == 0U);
367
368 x->n = i;
369 duk__bi_normalize(x); /* need to normalize, may even cancel to 0 */
370 DUK_ASSERT(duk__bi_is_valid(x));
371 }
372 #endif
373
374 #if 0 /* unused */
375 /* x <- y - z */
376 DUK_LOCAL void duk__bi_sub_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) {
377 duk__bigint tmp;
378
379 DUK_ASSERT(duk__bi_is_valid(y));
380
381 /* XXX: this could be optimized */
382 duk__bi_set_small(&tmp, z);
383 duk__bi_sub(x, y, &tmp);
384
385 DUK_ASSERT(duk__bi_is_valid(x));
386 }
387 #endif
388
389 /* x <- x - y, use t as temp */
duk__bi_sub_copy(duk__bigint * x,duk__bigint * y,duk__bigint * t)390 DUK_LOCAL void duk__bi_sub_copy(duk__bigint *x, duk__bigint *y, duk__bigint *t) {
391 duk__bi_sub(t, x, y);
392 duk__bi_copy(x, t);
393 }
394
395 /* x <- y * z */
duk__bi_mul(duk__bigint * x,duk__bigint * y,duk__bigint * z)396 DUK_LOCAL void duk__bi_mul(duk__bigint *x, duk__bigint *y, duk__bigint *z) {
397 duk_small_int_t i, j, nx, nz;
398
399 DUK_ASSERT(duk__bi_is_valid(y));
400 DUK_ASSERT(duk__bi_is_valid(z));
401
402 nx = y->n + z->n; /* max possible */
403 DUK_ASSERT(nx <= DUK__BI_MAX_PARTS);
404
405 if (nx == 0) {
406 /* Both inputs are zero; cases where only one is zero can go
407 * through main algorithm.
408 */
409 x->n = 0;
410 return;
411 }
412
413 duk_memzero((void *) x->v, (size_t) (sizeof(duk_uint32_t) * (size_t) nx));
414 x->n = nx;
415
416 nz = z->n;
417 for (i = 0; i < y->n; i++) {
418 #if defined(DUK_USE_64BIT_OPS)
419 duk_uint64_t tmp = 0U;
420 for (j = 0; j < nz; j++) {
421 tmp += (duk_uint64_t) y->v[i] * (duk_uint64_t) z->v[j] + x->v[i+j];
422 x->v[i+j] = (duk_uint32_t) (tmp & 0xffffffffUL);
423 tmp = tmp >> 32;
424 }
425 if (tmp > 0) {
426 DUK_ASSERT(i + j < nx);
427 DUK_ASSERT(i + j < DUK__BI_MAX_PARTS);
428 DUK_ASSERT(x->v[i+j] == 0U);
429 x->v[i+j] = (duk_uint32_t) tmp;
430 }
431 #else
432 /*
433 * Multiply + add + carry for 32-bit components using only 16x16->32
434 * multiplies and carry detection based on unsigned overflow.
435 *
436 * 1st mult, 32-bit: (A*2^16 + B)
437 * 2nd mult, 32-bit: (C*2^16 + D)
438 * 3rd add, 32-bit: E
439 * 4th add, 32-bit: F
440 *
441 * (AC*2^16 + B) * (C*2^16 + D) + E + F
442 * = AC*2^32 + AD*2^16 + BC*2^16 + BD + E + F
443 * = AC*2^32 + (AD + BC)*2^16 + (BD + E + F)
444 * = AC*2^32 + AD*2^16 + BC*2^16 + (BD + E + F)
445 */
446 duk_uint32_t a, b, c, d, e, f;
447 duk_uint32_t r, s, t;
448
449 a = y->v[i]; b = a & 0xffffUL; a = a >> 16;
450
451 f = 0;
452 for (j = 0; j < nz; j++) {
453 c = z->v[j]; d = c & 0xffffUL; c = c >> 16;
454 e = x->v[i+j];
455
456 /* build result as: (r << 32) + s: start with (BD + E + F) */
457 r = 0;
458 s = b * d;
459
460 /* add E */
461 t = s + e;
462 if (t < s) { r++; } /* carry */
463 s = t;
464
465 /* add F */
466 t = s + f;
467 if (t < s) { r++; } /* carry */
468 s = t;
469
470 /* add BC*2^16 */
471 t = b * c;
472 r += (t >> 16);
473 t = s + ((t & 0xffffUL) << 16);
474 if (t < s) { r++; } /* carry */
475 s = t;
476
477 /* add AD*2^16 */
478 t = a * d;
479 r += (t >> 16);
480 t = s + ((t & 0xffffUL) << 16);
481 if (t < s) { r++; } /* carry */
482 s = t;
483
484 /* add AC*2^32 */
485 t = a * c;
486 r += t;
487
488 DUK_DDD(DUK_DDDPRINT("ab=%08lx cd=%08lx ef=%08lx -> rs=%08lx %08lx",
489 (unsigned long) y->v[i], (unsigned long) z->v[j],
490 (unsigned long) x->v[i+j], (unsigned long) r,
491 (unsigned long) s));
492
493 x->v[i+j] = s;
494 f = r;
495 }
496 if (f > 0U) {
497 DUK_ASSERT(i + j < nx);
498 DUK_ASSERT(i + j < DUK__BI_MAX_PARTS);
499 DUK_ASSERT(x->v[i+j] == 0U);
500 x->v[i+j] = (duk_uint32_t) f;
501 }
502 #endif /* DUK_USE_64BIT_OPS */
503 }
504
505 duk__bi_normalize(x);
506 DUK_ASSERT(duk__bi_is_valid(x));
507 }
508
509 /* x <- y * z */
duk__bi_mul_small(duk__bigint * x,duk__bigint * y,duk_uint32_t z)510 DUK_LOCAL void duk__bi_mul_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) {
511 duk__bigint tmp;
512
513 DUK_ASSERT(duk__bi_is_valid(y));
514
515 /* XXX: this could be optimized */
516 duk__bi_set_small(&tmp, z);
517 duk__bi_mul(x, y, &tmp);
518
519 DUK_ASSERT(duk__bi_is_valid(x));
520 }
521
522 /* x <- x * y, use t as temp */
duk__bi_mul_copy(duk__bigint * x,duk__bigint * y,duk__bigint * t)523 DUK_LOCAL void duk__bi_mul_copy(duk__bigint *x, duk__bigint *y, duk__bigint *t) {
524 duk__bi_mul(t, x, y);
525 duk__bi_copy(x, t);
526 }
527
528 /* x <- x * y, use t as temp */
duk__bi_mul_small_copy(duk__bigint * x,duk_uint32_t y,duk__bigint * t)529 DUK_LOCAL void duk__bi_mul_small_copy(duk__bigint *x, duk_uint32_t y, duk__bigint *t) {
530 duk__bi_mul_small(t, x, y);
531 duk__bi_copy(x, t);
532 }
533
duk__bi_is_even(duk__bigint * x)534 DUK_LOCAL int duk__bi_is_even(duk__bigint *x) {
535 DUK_ASSERT(duk__bi_is_valid(x));
536 return (x->n == 0) || ((x->v[0] & 0x01) == 0);
537 }
538
duk__bi_is_zero(duk__bigint * x)539 DUK_LOCAL int duk__bi_is_zero(duk__bigint *x) {
540 DUK_ASSERT(duk__bi_is_valid(x));
541 return (x->n == 0); /* this is the case for normalized numbers */
542 }
543
544 /* Bigint is 2^52. Used to detect normalized IEEE double mantissa values
545 * which are at the lowest edge (next floating point value downwards has
546 * a different exponent). The lowest mantissa has the form:
547 *
548 * 1000........000 (52 zeroes; only "hidden bit" is set)
549 */
duk__bi_is_2to52(duk__bigint * x)550 DUK_LOCAL duk_small_int_t duk__bi_is_2to52(duk__bigint *x) {
551 DUK_ASSERT(duk__bi_is_valid(x));
552 return (duk_small_int_t)
553 (x->n == 2) && (x->v[0] == 0U) && (x->v[1] == (1U << (52-32)));
554 }
555
556 /* x <- (1<<y) */
duk__bi_twoexp(duk__bigint * x,duk_small_int_t y)557 DUK_LOCAL void duk__bi_twoexp(duk__bigint *x, duk_small_int_t y) {
558 duk_small_int_t n, r;
559
560 n = (y / 32) + 1;
561 DUK_ASSERT(n > 0);
562 r = y % 32;
563 duk_memzero((void *) x->v, sizeof(duk_uint32_t) * (size_t) n);
564 x->n = n;
565 x->v[n - 1] = (((duk_uint32_t) 1) << r);
566 }
567
568 /* x <- b^y; use t1 and t2 as temps */
duk__bi_exp_small(duk__bigint * x,duk_small_int_t b,duk_small_int_t y,duk__bigint * t1,duk__bigint * t2)569 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) {
570 /* Fast path the binary case */
571
572 DUK_ASSERT(x != t1 && x != t2 && t1 != t2); /* distinct bignums, easy mistake to make */
573 DUK_ASSERT(b >= 0);
574 DUK_ASSERT(y >= 0);
575
576 if (b == 2) {
577 duk__bi_twoexp(x, y);
578 return;
579 }
580
581 /* http://en.wikipedia.org/wiki/Exponentiation_by_squaring */
582
583 DUK_DDD(DUK_DDDPRINT("exp_small: b=%ld, y=%ld", (long) b, (long) y));
584
585 duk__bi_set_small(x, 1);
586 duk__bi_set_small(t1, (duk_uint32_t) b);
587 for (;;) {
588 /* Loop structure ensures that we don't compute t1^2 unnecessarily
589 * on the final round, as that might create a bignum exceeding the
590 * current DUK__BI_MAX_PARTS limit.
591 */
592 if (y & 0x01) {
593 duk__bi_mul_copy(x, t1, t2);
594 }
595 y = y >> 1;
596 if (y == 0) {
597 break;
598 }
599 duk__bi_mul_copy(t1, t1, t2);
600 }
601
602 DUK__BI_PRINT("exp_small result", x);
603 }
604
605 /*
606 * A Dragon4 number-to-string variant, based on:
607 *
608 * Guy L. Steele Jr., Jon L. White: "How to Print Floating-Point Numbers
609 * Accurately"
610 *
611 * Robert G. Burger, R. Kent Dybvig: "Printing Floating-Point Numbers
612 * Quickly and Accurately"
613 *
614 * The current algorithm is based on Figure 1 of the Burger-Dybvig paper,
615 * i.e. the base implementation without logarithm estimation speedups
616 * (these would increase code footprint considerably). Fixed-format output
617 * does not follow the suggestions in the paper; instead, we generate an
618 * extra digit and round-with-carry.
619 *
620 * The same algorithm is used for number parsing (with b=10 and B=2)
621 * by generating one extra digit and doing rounding manually.
622 *
623 * See doc/number-conversion.rst for limitations.
624 */
625
626 /* Maximum number of digits generated. */
627 #define DUK__MAX_OUTPUT_DIGITS 1040 /* (Number.MAX_VALUE).toString(2).length == 1024, + slack */
628
629 /* Maximum number of characters in formatted value. */
630 #define DUK__MAX_FORMATTED_LENGTH 1040 /* (-Number.MAX_VALUE).toString(2).length == 1025, + slack */
631
632 /* Number and (minimum) size of bigints in the nc_ctx structure. */
633 #define DUK__NUMCONV_CTX_NUM_BIGINTS 7
634 #define DUK__NUMCONV_CTX_BIGINTS_SIZE (sizeof(duk__bigint) * DUK__NUMCONV_CTX_NUM_BIGINTS)
635
636 typedef struct {
637 /* Currently about 7*152 = 1064 bytes. The space for these
638 * duk__bigints is used also as a temporary buffer for generating
639 * the final string. This is a bit awkard; a union would be
640 * more correct.
641 */
642 duk__bigint f, r, s, mp, mm, t1, t2;
643
644 duk_small_int_t is_s2n; /* if 1, doing a string-to-number; else doing a number-to-string */
645 duk_small_int_t is_fixed; /* if 1, doing a fixed format output (not free format) */
646 duk_small_int_t req_digits; /* requested number of output digits; 0 = free-format */
647 duk_small_int_t abs_pos; /* digit position is absolute, not relative */
648 duk_small_int_t e; /* exponent for 'f' */
649 duk_small_int_t b; /* input radix */
650 duk_small_int_t B; /* output radix */
651 duk_small_int_t k; /* see algorithm */
652 duk_small_int_t low_ok; /* see algorithm */
653 duk_small_int_t high_ok; /* see algorithm */
654 duk_small_int_t unequal_gaps; /* m+ != m- (very rarely) */
655
656 /* Buffer used for generated digits, values are in the range [0,B-1]. */
657 duk_uint8_t digits[DUK__MAX_OUTPUT_DIGITS];
658 duk_small_int_t count; /* digit count */
659 } duk__numconv_stringify_ctx;
660
661 /* Note: computes with 'idx' in assertions, so caller beware.
662 * 'idx' is preincremented, i.e. '1' on first call, because it
663 * is more convenient for the caller.
664 */
665 #define DUK__DRAGON4_OUTPUT_PREINC(nc_ctx,preinc_idx,x) do { \
666 DUK_ASSERT((preinc_idx) - 1 >= 0); \
667 DUK_ASSERT((preinc_idx) - 1 < DUK__MAX_OUTPUT_DIGITS); \
668 ((nc_ctx)->digits[(preinc_idx) - 1]) = (duk_uint8_t) (x); \
669 } while (0)
670
duk__dragon4_format_uint32(duk_uint8_t * buf,duk_uint32_t x,duk_small_int_t radix)671 DUK_LOCAL duk_size_t duk__dragon4_format_uint32(duk_uint8_t *buf, duk_uint32_t x, duk_small_int_t radix) {
672 duk_uint8_t *p;
673 duk_size_t len;
674 duk_small_int_t dig;
675 duk_uint32_t t;
676
677 DUK_ASSERT(buf != NULL);
678 DUK_ASSERT(radix >= 2 && radix <= 36);
679
680 /* A 32-bit unsigned integer formats to at most 32 digits (the
681 * worst case happens with radix == 2). Output the digits backwards,
682 * and use a memmove() to get them in the right place.
683 */
684
685 p = buf + 32;
686 for (;;) {
687 t = x / (duk_uint32_t) radix;
688 dig = (duk_small_int_t) (x - t * (duk_uint32_t) radix);
689 x = t;
690
691 DUK_ASSERT(dig >= 0 && dig < 36);
692 *(--p) = DUK__DIGITCHAR(dig);
693
694 if (x == 0) {
695 break;
696 }
697 }
698 len = (duk_size_t) ((buf + 32) - p);
699
700 duk_memmove((void *) buf, (const void *) p, (size_t) len);
701
702 return len;
703 }
704
duk__dragon4_prepare(duk__numconv_stringify_ctx * nc_ctx)705 DUK_LOCAL void duk__dragon4_prepare(duk__numconv_stringify_ctx *nc_ctx) {
706 duk_small_int_t lowest_mantissa;
707
708 #if 1
709 /* Assume IEEE round-to-even, so that shorter encoding can be used
710 * when round-to-even would produce correct result. By removing
711 * this check (and having low_ok == high_ok == 0) the results would
712 * still be accurate but in some cases longer than necessary.
713 */
714 if (duk__bi_is_even(&nc_ctx->f)) {
715 DUK_DDD(DUK_DDDPRINT("f is even"));
716 nc_ctx->low_ok = 1;
717 nc_ctx->high_ok = 1;
718 } else {
719 DUK_DDD(DUK_DDDPRINT("f is odd"));
720 nc_ctx->low_ok = 0;
721 nc_ctx->high_ok = 0;
722 }
723 #else
724 /* Note: not honoring round-to-even should work but now generates incorrect
725 * results. For instance, 1e23 serializes to "a000...", i.e. the first digit
726 * equals the radix (10). Scaling stops one step too early in this case.
727 * Don't know why this is the case, but since this code path is unused, it
728 * doesn't matter.
729 */
730 nc_ctx->low_ok = 0;
731 nc_ctx->high_ok = 0;
732 #endif
733
734 /* For string-to-number, pretend we never have the lowest mantissa as there
735 * is no natural "precision" for inputs. Having lowest_mantissa == 0, we'll
736 * fall into the base cases for both e >= 0 and e < 0.
737 */
738 if (nc_ctx->is_s2n) {
739 lowest_mantissa = 0;
740 } else {
741 lowest_mantissa = duk__bi_is_2to52(&nc_ctx->f);
742 }
743
744 nc_ctx->unequal_gaps = 0;
745 if (nc_ctx->e >= 0) {
746 /* exponent non-negative (and thus not minimum exponent) */
747
748 if (lowest_mantissa) {
749 /* (>= e 0) AND (= f (expt b (- p 1)))
750 *
751 * be <- (expt b e) == b^e
752 * be1 <- (* be b) == (expt b (+ e 1)) == b^(e+1)
753 * r <- (* f be1 2) == 2 * f * b^(e+1) [if b==2 -> f * b^(e+2)]
754 * s <- (* b 2) [if b==2 -> 4]
755 * m+ <- be1 == b^(e+1)
756 * m- <- be == b^e
757 * k <- 0
758 * B <- B
759 * low_ok <- round
760 * high_ok <- round
761 */
762
763 DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); "
764 "lowest mantissa value for this exponent -> "
765 "unequal gaps"));
766
767 duk__bi_exp_small(&nc_ctx->mm, nc_ctx->b, nc_ctx->e, &nc_ctx->t1, &nc_ctx->t2); /* mm <- b^e */
768 duk__bi_mul_small(&nc_ctx->mp, &nc_ctx->mm, (duk_uint32_t) nc_ctx->b); /* mp <- b^(e+1) */
769 duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->f, 2);
770 duk__bi_mul(&nc_ctx->r, &nc_ctx->t1, &nc_ctx->mp); /* r <- (2 * f) * b^(e+1) */
771 duk__bi_set_small(&nc_ctx->s, (duk_uint32_t) (nc_ctx->b * 2)); /* s <- 2 * b */
772 nc_ctx->unequal_gaps = 1;
773 } else {
774 /* (>= e 0) AND (not (= f (expt b (- p 1))))
775 *
776 * be <- (expt b e) == b^e
777 * r <- (* f be 2) == 2 * f * b^e [if b==2 -> f * b^(e+1)]
778 * s <- 2
779 * m+ <- be == b^e
780 * m- <- be == b^e
781 * k <- 0
782 * B <- B
783 * low_ok <- round
784 * high_ok <- round
785 */
786
787 DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); "
788 "not lowest mantissa for this exponent -> "
789 "equal gaps"));
790
791 duk__bi_exp_small(&nc_ctx->mm, nc_ctx->b, nc_ctx->e, &nc_ctx->t1, &nc_ctx->t2); /* mm <- b^e */
792 duk__bi_copy(&nc_ctx->mp, &nc_ctx->mm); /* mp <- b^e */
793 duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->f, 2);
794 duk__bi_mul(&nc_ctx->r, &nc_ctx->t1, &nc_ctx->mp); /* r <- (2 * f) * b^e */
795 duk__bi_set_small(&nc_ctx->s, 2); /* s <- 2 */
796 }
797 } else {
798 /* When doing string-to-number, lowest_mantissa is always 0 so
799 * the exponent check, while incorrect, won't matter.
800 */
801 if (nc_ctx->e > DUK__IEEE_DOUBLE_EXP_MIN /*not minimum exponent*/ &&
802 lowest_mantissa /* lowest mantissa for this exponent*/) {
803 /* r <- (* f b 2) [if b==2 -> (* f 4)]
804 * s <- (* (expt b (- 1 e)) 2) == b^(1-e) * 2 [if b==2 -> b^(2-e)]
805 * m+ <- b == 2
806 * m- <- 1
807 * k <- 0
808 * B <- B
809 * low_ok <- round
810 * high_ok <- round
811 */
812
813 DUK_DDD(DUK_DDDPRINT("negative exponent; not minimum exponent and "
814 "lowest mantissa for this exponent -> "
815 "unequal gaps"));
816
817 duk__bi_mul_small(&nc_ctx->r, &nc_ctx->f, (duk_uint32_t) (nc_ctx->b * 2)); /* r <- (2 * b) * f */
818 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 */
819 duk__bi_mul_small(&nc_ctx->s, &nc_ctx->t1, 2); /* s <- b^(1-e) * 2 */
820 duk__bi_set_small(&nc_ctx->mp, 2);
821 duk__bi_set_small(&nc_ctx->mm, 1);
822 nc_ctx->unequal_gaps = 1;
823 } else {
824 /* r <- (* f 2)
825 * s <- (* (expt b (- e)) 2) == b^(-e) * 2 [if b==2 -> b^(1-e)]
826 * m+ <- 1
827 * m- <- 1
828 * k <- 0
829 * B <- B
830 * low_ok <- round
831 * high_ok <- round
832 */
833
834 DUK_DDD(DUK_DDDPRINT("negative exponent; minimum exponent or not "
835 "lowest mantissa for this exponent -> "
836 "equal gaps"));
837
838 duk__bi_mul_small(&nc_ctx->r, &nc_ctx->f, 2); /* r <- 2 * f */
839 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 */
840 duk__bi_mul_small(&nc_ctx->s, &nc_ctx->t1, 2); /* s <- b^(-e) * 2 */
841 duk__bi_set_small(&nc_ctx->mp, 1);
842 duk__bi_set_small(&nc_ctx->mm, 1);
843 }
844 }
845 }
846
duk__dragon4_scale(duk__numconv_stringify_ctx * nc_ctx)847 DUK_LOCAL void duk__dragon4_scale(duk__numconv_stringify_ctx *nc_ctx) {
848 duk_small_int_t k = 0;
849
850 /* This is essentially the 'scale' algorithm, with recursion removed.
851 * Note that 'k' is either correct immediately, or will move in one
852 * direction in the loop. There's no need to do the low/high checks
853 * on every round (like the Scheme algorithm does).
854 *
855 * The scheme algorithm finds 'k' and updates 's' simultaneously,
856 * while the logical algorithm finds 'k' with 's' having its initial
857 * value, after which 's' is updated separately (see the Burger-Dybvig
858 * paper, Section 3.1, steps 2 and 3).
859 *
860 * The case where m+ == m- (almost always) is optimized for, because
861 * it reduces the bigint operations considerably and almost always
862 * applies. The scale loop only needs to work with m+, so this works.
863 */
864
865 /* XXX: this algorithm could be optimized quite a lot by using e.g.
866 * a logarithm based estimator for 'k' and performing B^n multiplication
867 * using a lookup table or using some bit-representation based exp
868 * algorithm. Currently we just loop, with significant performance
869 * impact for very large and very small numbers.
870 */
871
872 DUK_DDD(DUK_DDDPRINT("scale: B=%ld, low_ok=%ld, high_ok=%ld",
873 (long) nc_ctx->B, (long) nc_ctx->low_ok, (long) nc_ctx->high_ok));
874 DUK__BI_PRINT("r(init)", &nc_ctx->r);
875 DUK__BI_PRINT("s(init)", &nc_ctx->s);
876 DUK__BI_PRINT("mp(init)", &nc_ctx->mp);
877 DUK__BI_PRINT("mm(init)", &nc_ctx->mm);
878
879 for (;;) {
880 DUK_DDD(DUK_DDDPRINT("scale loop (inc k), k=%ld", (long) k));
881 DUK__BI_PRINT("r", &nc_ctx->r);
882 DUK__BI_PRINT("s", &nc_ctx->s);
883 DUK__BI_PRINT("m+", &nc_ctx->mp);
884 DUK__BI_PRINT("m-", &nc_ctx->mm);
885
886 duk__bi_add(&nc_ctx->t1, &nc_ctx->r, &nc_ctx->mp); /* t1 = (+ r m+) */
887 if (duk__bi_compare(&nc_ctx->t1, &nc_ctx->s) >= (nc_ctx->high_ok ? 0 : 1)) {
888 DUK_DDD(DUK_DDDPRINT("k is too low"));
889 /* r <- r
890 * s <- (* s B)
891 * m+ <- m+
892 * m- <- m-
893 * k <- (+ k 1)
894 */
895
896 duk__bi_mul_small_copy(&nc_ctx->s, (duk_uint32_t) nc_ctx->B, &nc_ctx->t1);
897 k++;
898 } else {
899 break;
900 }
901 }
902
903 /* k > 0 -> k was too low, and cannot be too high */
904 if (k > 0) {
905 goto skip_dec_k;
906 }
907
908 for (;;) {
909 DUK_DDD(DUK_DDDPRINT("scale loop (dec k), k=%ld", (long) k));
910 DUK__BI_PRINT("r", &nc_ctx->r);
911 DUK__BI_PRINT("s", &nc_ctx->s);
912 DUK__BI_PRINT("m+", &nc_ctx->mp);
913 DUK__BI_PRINT("m-", &nc_ctx->mm);
914
915 duk__bi_add(&nc_ctx->t1, &nc_ctx->r, &nc_ctx->mp); /* t1 = (+ r m+) */
916 duk__bi_mul_small(&nc_ctx->t2, &nc_ctx->t1, (duk_uint32_t) nc_ctx->B); /* t2 = (* (+ r m+) B) */
917 if (duk__bi_compare(&nc_ctx->t2, &nc_ctx->s) <= (nc_ctx->high_ok ? -1 : 0)) {
918 DUK_DDD(DUK_DDDPRINT("k is too high"));
919 /* r <- (* r B)
920 * s <- s
921 * m+ <- (* m+ B)
922 * m- <- (* m- B)
923 * k <- (- k 1)
924 */
925 duk__bi_mul_small_copy(&nc_ctx->r, (duk_uint32_t) nc_ctx->B, &nc_ctx->t1);
926 duk__bi_mul_small_copy(&nc_ctx->mp, (duk_uint32_t) nc_ctx->B, &nc_ctx->t1);
927 if (nc_ctx->unequal_gaps) {
928 DUK_DDD(DUK_DDDPRINT("m+ != m- -> need to update m- too"));
929 duk__bi_mul_small_copy(&nc_ctx->mm, (duk_uint32_t) nc_ctx->B, &nc_ctx->t1);
930 }
931 k--;
932 } else {
933 break;
934 }
935 }
936
937 skip_dec_k:
938
939 if (!nc_ctx->unequal_gaps) {
940 DUK_DDD(DUK_DDDPRINT("equal gaps, copy m- from m+"));
941 duk__bi_copy(&nc_ctx->mm, &nc_ctx->mp); /* mm <- mp */
942 }
943 nc_ctx->k = k;
944
945 DUK_DDD(DUK_DDDPRINT("final k: %ld", (long) k));
946 DUK__BI_PRINT("r(final)", &nc_ctx->r);
947 DUK__BI_PRINT("s(final)", &nc_ctx->s);
948 DUK__BI_PRINT("mp(final)", &nc_ctx->mp);
949 DUK__BI_PRINT("mm(final)", &nc_ctx->mm);
950 }
951
duk__dragon4_generate(duk__numconv_stringify_ctx * nc_ctx)952 DUK_LOCAL void duk__dragon4_generate(duk__numconv_stringify_ctx *nc_ctx) {
953 duk_small_int_t tc1, tc2; /* terminating conditions */
954 duk_small_int_t d; /* current digit */
955 duk_small_int_t count = 0; /* digit count */
956
957 /*
958 * Digit generation loop.
959 *
960 * Different termination conditions:
961 *
962 * 1. Free format output. Terminate when shortest accurate
963 * representation found.
964 *
965 * 2. Fixed format output, with specific number of digits.
966 * Ignore termination conditions, terminate when digits
967 * generated. Caller requests an extra digit and rounds.
968 *
969 * 3. Fixed format output, with a specific absolute cut-off
970 * position (e.g. 10 digits after decimal point). Note
971 * that we always generate at least one digit, even if
972 * the digit is below the cut-off point already.
973 */
974
975 for (;;) {
976 DUK_DDD(DUK_DDDPRINT("generate loop, count=%ld, k=%ld, B=%ld, low_ok=%ld, high_ok=%ld",
977 (long) count, (long) nc_ctx->k, (long) nc_ctx->B,
978 (long) nc_ctx->low_ok, (long) nc_ctx->high_ok));
979 DUK__BI_PRINT("r", &nc_ctx->r);
980 DUK__BI_PRINT("s", &nc_ctx->s);
981 DUK__BI_PRINT("m+", &nc_ctx->mp);
982 DUK__BI_PRINT("m-", &nc_ctx->mm);
983
984 /* (quotient-remainder (* r B) s) using a dummy subtraction loop */
985 duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->r, (duk_uint32_t) nc_ctx->B); /* t1 <- (* r B) */
986 d = 0;
987 for (;;) {
988 if (duk__bi_compare(&nc_ctx->t1, &nc_ctx->s) < 0) {
989 break;
990 }
991 duk__bi_sub_copy(&nc_ctx->t1, &nc_ctx->s, &nc_ctx->t2); /* t1 <- t1 - s */
992 d++;
993 }
994 duk__bi_copy(&nc_ctx->r, &nc_ctx->t1); /* r <- (remainder (* r B) s) */
995 /* d <- (quotient (* r B) s) (in range 0...B-1) */
996 DUK_DDD(DUK_DDDPRINT("-> d(quot)=%ld", (long) d));
997 DUK__BI_PRINT("r(rem)", &nc_ctx->r);
998
999 duk__bi_mul_small_copy(&nc_ctx->mp, (duk_uint32_t) nc_ctx->B, &nc_ctx->t2); /* m+ <- (* m+ B) */
1000 duk__bi_mul_small_copy(&nc_ctx->mm, (duk_uint32_t) nc_ctx->B, &nc_ctx->t2); /* m- <- (* m- B) */
1001 DUK__BI_PRINT("mp(upd)", &nc_ctx->mp);
1002 DUK__BI_PRINT("mm(upd)", &nc_ctx->mm);
1003
1004 /* Terminating conditions. For fixed width output, we just ignore the
1005 * terminating conditions (and pretend that tc1 == tc2 == false). The
1006 * the current shortcut for fixed-format output is to generate a few
1007 * extra digits and use rounding (with carry) to finish the output.
1008 */
1009
1010 if (nc_ctx->is_fixed == 0) {
1011 /* free-form */
1012 tc1 = (duk__bi_compare(&nc_ctx->r, &nc_ctx->mm) <= (nc_ctx->low_ok ? 0 : -1));
1013
1014 duk__bi_add(&nc_ctx->t1, &nc_ctx->r, &nc_ctx->mp); /* t1 <- (+ r m+) */
1015 tc2 = (duk__bi_compare(&nc_ctx->t1, &nc_ctx->s) >= (nc_ctx->high_ok ? 0 : 1));
1016
1017 DUK_DDD(DUK_DDDPRINT("tc1=%ld, tc2=%ld", (long) tc1, (long) tc2));
1018 } else {
1019 /* fixed-format */
1020 tc1 = 0;
1021 tc2 = 0;
1022 }
1023
1024 /* Count is incremented before DUK__DRAGON4_OUTPUT_PREINC() call
1025 * on purpose, which is taken into account by the macro.
1026 */
1027 count++;
1028
1029 if (tc1) {
1030 if (tc2) {
1031 /* tc1 = true, tc2 = true */
1032 duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->r, 2);
1033 if (duk__bi_compare(&nc_ctx->t1, &nc_ctx->s) < 0) { /* (< (* r 2) s) */
1034 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=true, 2r > s: output d --> %ld (k=%ld)",
1035 (long) d, (long) nc_ctx->k));
1036 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx, count, d);
1037 } else {
1038 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=true, 2r <= s: output d+1 --> %ld (k=%ld)",
1039 (long) (d + 1), (long) nc_ctx->k));
1040 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx, count, d + 1);
1041 }
1042 break;
1043 } else {
1044 /* tc1 = true, tc2 = false */
1045 DUK_DDD(DUK_DDDPRINT("tc1=true, tc2=false: output d --> %ld (k=%ld)",
1046 (long) d, (long) nc_ctx->k));
1047 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx, count, d);
1048 break;
1049 }
1050 } else {
1051 if (tc2) {
1052 /* tc1 = false, tc2 = true */
1053 DUK_DDD(DUK_DDDPRINT("tc1=false, tc2=true: output d+1 --> %ld (k=%ld)",
1054 (long) (d + 1), (long) nc_ctx->k));
1055 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx, count, d + 1);
1056 break;
1057 } else {
1058 /* tc1 = false, tc2 = false */
1059 DUK_DDD(DUK_DDDPRINT("tc1=false, tc2=false: output d --> %ld (k=%ld)",
1060 (long) d, (long) nc_ctx->k));
1061 DUK__DRAGON4_OUTPUT_PREINC(nc_ctx, count, d);
1062
1063 /* r <- r (updated above: r <- (remainder (* r B) s)
1064 * s <- s
1065 * m+ <- m+ (updated above: m+ <- (* m+ B)
1066 * m- <- m- (updated above: m- <- (* m- B)
1067 * B, low_ok, high_ok are fixed
1068 */
1069
1070 /* fall through and continue for-loop */
1071 }
1072 }
1073
1074 /* fixed-format termination conditions */
1075 if (nc_ctx->is_fixed) {
1076 if (nc_ctx->abs_pos) {
1077 int pos = nc_ctx->k - count + 1; /* count is already incremented, take into account */
1078 DUK_DDD(DUK_DDDPRINT("fixed format, absolute: abs pos=%ld, k=%ld, count=%ld, req=%ld",
1079 (long) pos, (long) nc_ctx->k, (long) count, (long) nc_ctx->req_digits));
1080 if (pos <= nc_ctx->req_digits) {
1081 DUK_DDD(DUK_DDDPRINT("digit position reached req_digits, end generate loop"));
1082 break;
1083 }
1084 } else {
1085 DUK_DDD(DUK_DDDPRINT("fixed format, relative: k=%ld, count=%ld, req=%ld",
1086 (long) nc_ctx->k, (long) count, (long) nc_ctx->req_digits));
1087 if (count >= nc_ctx->req_digits) {
1088 DUK_DDD(DUK_DDDPRINT("digit count reached req_digits, end generate loop"));
1089 break;
1090 }
1091 }
1092 }
1093 } /* for */
1094
1095 nc_ctx->count = count;
1096
1097 DUK_DDD(DUK_DDDPRINT("generate finished"));
1098
1099 #if defined(DUK_USE_DEBUG_LEVEL) && (DUK_USE_DEBUG_LEVEL >= 2)
1100 {
1101 duk_uint8_t buf[2048];
1102 duk_small_int_t i, t;
1103 duk_memzero(buf, sizeof(buf));
1104 for (i = 0; i < nc_ctx->count; i++) {
1105 t = nc_ctx->digits[i];
1106 if (t < 0 || t > 36) {
1107 buf[i] = (duk_uint8_t) '?';
1108 } else {
1109 buf[i] = (duk_uint8_t) DUK__DIGITCHAR(t);
1110 }
1111 }
1112 DUK_DDD(DUK_DDDPRINT("-> generated digits; k=%ld, digits='%s'",
1113 (long) nc_ctx->k, (const char *) buf));
1114 }
1115 #endif
1116 }
1117
1118 /* Round up digits to a given position. If position is out-of-bounds,
1119 * does nothing. If carry propagates over the first digit, a '1' is
1120 * prepended to digits and 'k' will be updated. Return value indicates
1121 * whether carry propagated over the first digit.
1122 *
1123 * Note that nc_ctx->count is NOT updated based on the rounding position
1124 * (it is updated only if carry overflows over the first digit and an
1125 * extra digit is prepended).
1126 */
duk__dragon4_fixed_format_round(duk__numconv_stringify_ctx * nc_ctx,duk_small_int_t round_idx)1127 DUK_LOCAL duk_small_int_t duk__dragon4_fixed_format_round(duk__numconv_stringify_ctx *nc_ctx, duk_small_int_t round_idx) {
1128 duk_small_int_t t;
1129 duk_uint8_t *p;
1130 duk_uint8_t roundup_limit;
1131 duk_small_int_t ret = 0;
1132
1133 /*
1134 * round_idx points to the digit which is considered for rounding; the
1135 * digit to its left is the final digit of the rounded value. If round_idx
1136 * is zero, rounding will be performed; the result will either be an empty
1137 * rounded value or if carry happens a '1' digit is generated.
1138 */
1139
1140 if (round_idx >= nc_ctx->count) {
1141 DUK_DDD(DUK_DDDPRINT("round_idx out of bounds (%ld >= %ld (count)) -> no rounding",
1142 (long) round_idx, (long) nc_ctx->count));
1143 return 0;
1144 } else if (round_idx < 0) {
1145 DUK_DDD(DUK_DDDPRINT("round_idx out of bounds (%ld < 0) -> no rounding",
1146 (long) round_idx));
1147 return 0;
1148 }
1149
1150 /*
1151 * Round-up limit.
1152 *
1153 * For even values, divides evenly, e.g. 10 -> roundup_limit=5.
1154 *
1155 * For odd values, rounds up, e.g. 3 -> roundup_limit=2.
1156 * If radix is 3, 0/3 -> down, 1/3 -> down, 2/3 -> up.
1157 */
1158 roundup_limit = (duk_uint8_t) ((nc_ctx->B + 1) / 2);
1159
1160 p = &nc_ctx->digits[round_idx];
1161 if (*p >= roundup_limit) {
1162 DUK_DDD(DUK_DDDPRINT("fixed-format rounding carry required"));
1163 /* carry */
1164 for (;;) {
1165 *p = 0;
1166 if (p == &nc_ctx->digits[0]) {
1167 DUK_DDD(DUK_DDDPRINT("carry propagated to first digit -> special case handling"));
1168 duk_memmove((void *) (&nc_ctx->digits[1]),
1169 (const void *) (&nc_ctx->digits[0]),
1170 (size_t) (sizeof(char) * (size_t) nc_ctx->count));
1171 nc_ctx->digits[0] = 1; /* don't increase 'count' */
1172 nc_ctx->k++; /* position of highest digit changed */
1173 nc_ctx->count++; /* number of digits changed */
1174 ret = 1;
1175 break;
1176 }
1177
1178 DUK_DDD(DUK_DDDPRINT("fixed-format rounding carry: B=%ld, roundup_limit=%ld, p=%p, digits=%p",
1179 (long) nc_ctx->B, (long) roundup_limit, (void *) p, (void *) nc_ctx->digits));
1180 p--;
1181 t = *p;
1182 DUK_DDD(DUK_DDDPRINT("digit before carry: %ld", (long) t));
1183 if (++t < nc_ctx->B) {
1184 DUK_DDD(DUK_DDDPRINT("rounding carry terminated"));
1185 *p = (duk_uint8_t) t;
1186 break;
1187 }
1188
1189 DUK_DDD(DUK_DDDPRINT("wraps, carry to next digit"));
1190 }
1191 }
1192
1193 return ret;
1194 }
1195
1196 #define DUK__NO_EXP (65536) /* arbitrary marker, outside valid exp range */
1197
duk__dragon4_convert_and_push(duk__numconv_stringify_ctx * nc_ctx,duk_hthread * thr,duk_small_int_t radix,duk_small_int_t digits,duk_small_uint_t flags,duk_small_int_t neg)1198 DUK_LOCAL void duk__dragon4_convert_and_push(duk__numconv_stringify_ctx *nc_ctx,
1199 duk_hthread *thr,
1200 duk_small_int_t radix,
1201 duk_small_int_t digits,
1202 duk_small_uint_t flags,
1203 duk_small_int_t neg) {
1204 duk_small_int_t k;
1205 duk_small_int_t pos, pos_end;
1206 duk_small_int_t expt;
1207 duk_small_int_t dig;
1208 duk_uint8_t *q;
1209 duk_uint8_t *buf;
1210
1211 /*
1212 * The string conversion here incorporates all the necessary ECMAScript
1213 * semantics without attempting to be generic. nc_ctx->digits contains
1214 * nc_ctx->count digits (>= 1), with the topmost digit's 'position'
1215 * indicated by nc_ctx->k as follows:
1216 *
1217 * digits="123" count=3 k=0 --> 0.123
1218 * digits="123" count=3 k=1 --> 1.23
1219 * digits="123" count=3 k=5 --> 12300
1220 * digits="123" count=3 k=-1 --> 0.0123
1221 *
1222 * Note that the identifier names used for format selection are different
1223 * in Burger-Dybvig paper and ECMAScript specification (quite confusingly
1224 * so, because e.g. 'k' has a totally different meaning in each). See
1225 * documentation for discussion.
1226 *
1227 * ECMAScript doesn't specify any specific behavior for format selection
1228 * (e.g. when to use exponent notation) for non-base-10 numbers.
1229 *
1230 * The bigint space in the context is reused for string output, as there
1231 * is more than enough space for that (>1kB at the moment), and we avoid
1232 * allocating even more stack.
1233 */
1234
1235 DUK_ASSERT(DUK__NUMCONV_CTX_BIGINTS_SIZE >= DUK__MAX_FORMATTED_LENGTH);
1236 DUK_ASSERT(nc_ctx->count >= 1);
1237
1238 k = nc_ctx->k;
1239 buf = (duk_uint8_t *) &nc_ctx->f; /* XXX: union would be more correct */
1240 q = buf;
1241
1242 /* Exponent handling: if exponent format is used, record exponent value and
1243 * fake k such that one leading digit is generated (e.g. digits=123 -> "1.23").
1244 *
1245 * toFixed() prevents exponent use; otherwise apply a set of criteria to
1246 * match the other API calls (toString(), toPrecision, etc).
1247 */
1248
1249 expt = DUK__NO_EXP;
1250 if (!nc_ctx->abs_pos /* toFixed() */) {
1251 if ((flags & DUK_N2S_FLAG_FORCE_EXP) || /* exponential notation forced */
1252 ((flags & DUK_N2S_FLAG_NO_ZERO_PAD) && /* fixed precision and zero padding would be required */
1253 (k - digits >= 1)) || /* (e.g. k=3, digits=2 -> "12X") */
1254 ((k > 21 || k <= -6) && (radix == 10))) { /* toString() conditions */
1255 DUK_DDD(DUK_DDDPRINT("use exponential notation: k=%ld -> expt=%ld",
1256 (long) k, (long) (k - 1)));
1257 expt = k - 1; /* e.g. 12.3 -> digits="123" k=2 -> 1.23e1 */
1258 k = 1; /* generate mantissa with a single leading whole number digit */
1259 }
1260 }
1261
1262 if (neg) {
1263 *q++ = '-';
1264 }
1265
1266 /* Start position (inclusive) and end position (exclusive) */
1267 pos = (k >= 1 ? k : 1);
1268 if (nc_ctx->is_fixed) {
1269 if (nc_ctx->abs_pos) {
1270 /* toFixed() */
1271 pos_end = -digits;
1272 } else {
1273 pos_end = k - digits;
1274 }
1275 } else {
1276 pos_end = k - nc_ctx->count;
1277 }
1278 if (pos_end > 0) {
1279 pos_end = 0;
1280 }
1281
1282 DUK_DDD(DUK_DDDPRINT("expt=%ld, k=%ld, count=%ld, pos=%ld, pos_end=%ld, is_fixed=%ld, "
1283 "digits=%ld, abs_pos=%ld",
1284 (long) expt, (long) k, (long) nc_ctx->count, (long) pos, (long) pos_end,
1285 (long) nc_ctx->is_fixed, (long) digits, (long) nc_ctx->abs_pos));
1286
1287 /* Digit generation */
1288 while (pos > pos_end) {
1289 DUK_DDD(DUK_DDDPRINT("digit generation: pos=%ld, pos_end=%ld",
1290 (long) pos, (long) pos_end));
1291 if (pos == 0) {
1292 *q++ = (duk_uint8_t) '.';
1293 }
1294 if (pos > k) {
1295 *q++ = (duk_uint8_t) '0';
1296 } else if (pos <= k - nc_ctx->count) {
1297 *q++ = (duk_uint8_t) '0';
1298 } else {
1299 dig = nc_ctx->digits[k - pos];
1300 DUK_ASSERT(dig >= 0 && dig < nc_ctx->B);
1301 *q++ = (duk_uint8_t) DUK__DIGITCHAR(dig);
1302 }
1303
1304 pos--;
1305 }
1306 DUK_ASSERT(pos <= 1);
1307
1308 /* Exponent */
1309 if (expt != DUK__NO_EXP) {
1310 /*
1311 * Exponent notation for non-base-10 numbers isn't specified in ECMAScript
1312 * specification, as it never explicitly turns up: non-decimal numbers can
1313 * only be formatted with Number.prototype.toString([radix]) and for that,
1314 * behavior is not explicitly specified.
1315 *
1316 * Logical choices include formatting the exponent as decimal (e.g. binary
1317 * 100000 as 1e+5) or in current radix (e.g. binary 100000 as 1e+101).
1318 * The Dragon4 algorithm (in the original paper) prints the exponent value
1319 * in the target radix B. However, for radix values 15 and above, the
1320 * exponent separator 'e' is no longer easily parseable. Consider, for
1321 * instance, the number "1.faecee+1c".
1322 */
1323
1324 duk_size_t len;
1325 char expt_sign;
1326
1327 *q++ = 'e';
1328 if (expt >= 0) {
1329 expt_sign = '+';
1330 } else {
1331 expt_sign = '-';
1332 expt = -expt;
1333 }
1334 *q++ = (duk_uint8_t) expt_sign;
1335 len = duk__dragon4_format_uint32(q, (duk_uint32_t) expt, radix);
1336 q += len;
1337 }
1338
1339 duk_push_lstring(thr, (const char *) buf, (size_t) (q - buf));
1340 }
1341
1342 /*
1343 * Conversion helpers
1344 */
1345
duk__dragon4_double_to_ctx(duk__numconv_stringify_ctx * nc_ctx,duk_double_t x)1346 DUK_LOCAL void duk__dragon4_double_to_ctx(duk__numconv_stringify_ctx *nc_ctx, duk_double_t x) {
1347 duk_double_union u;
1348 duk_uint32_t tmp;
1349 duk_small_int_t expt;
1350
1351 /*
1352 * seeeeeee eeeeffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff
1353 * A B C D E F G H
1354 *
1355 * s sign bit
1356 * eee... exponent field
1357 * fff... fraction
1358 *
1359 * ieee value = 1.ffff... * 2^(e - 1023) (normal)
1360 * = 0.ffff... * 2^(-1022) (denormal)
1361 *
1362 * algorithm v = f * b^e
1363 */
1364
1365 DUK_DBLUNION_SET_DOUBLE(&u, x);
1366
1367 nc_ctx->f.n = 2;
1368
1369 tmp = DUK_DBLUNION_GET_LOW32(&u);
1370 nc_ctx->f.v[0] = tmp;
1371 tmp = DUK_DBLUNION_GET_HIGH32(&u);
1372 nc_ctx->f.v[1] = tmp & 0x000fffffUL;
1373 expt = (duk_small_int_t) ((tmp >> 20) & 0x07ffUL);
1374
1375 if (expt == 0) {
1376 /* denormal */
1377 expt = DUK__IEEE_DOUBLE_EXP_MIN - 52;
1378 duk__bi_normalize(&nc_ctx->f);
1379 } else {
1380 /* normal: implicit leading 1-bit */
1381 nc_ctx->f.v[1] |= 0x00100000UL;
1382 expt = expt - DUK__IEEE_DOUBLE_EXP_BIAS - 52;
1383 DUK_ASSERT(duk__bi_is_valid(&nc_ctx->f)); /* true, because v[1] has at least one bit set */
1384 }
1385
1386 DUK_ASSERT(duk__bi_is_valid(&nc_ctx->f));
1387
1388 nc_ctx->e = expt;
1389 }
1390
duk__dragon4_ctx_to_double(duk__numconv_stringify_ctx * nc_ctx,duk_double_t * x)1391 DUK_LOCAL void duk__dragon4_ctx_to_double(duk__numconv_stringify_ctx *nc_ctx, duk_double_t *x) {
1392 duk_double_union u;
1393 duk_small_int_t expt;
1394 duk_small_int_t i;
1395 duk_small_int_t bitstart;
1396 duk_small_int_t bitround;
1397 duk_small_int_t bitidx;
1398 duk_small_int_t skip_round;
1399 duk_uint32_t t, v;
1400
1401 DUK_ASSERT(nc_ctx->count == 53 + 1);
1402
1403 /* Sometimes this assert is not true right now; it will be true after
1404 * rounding. See: test-bug-numconv-mantissa-assert.js.
1405 */
1406 DUK_ASSERT_DISABLE(nc_ctx->digits[0] == 1); /* zero handled by caller */
1407
1408 /* Should not be required because the code below always sets both high
1409 * and low parts, but at least gcc-4.4.5 fails to deduce this correctly
1410 * (perhaps because the low part is set (seemingly) conditionally in a
1411 * loop), so this is here to avoid the bogus warning.
1412 */
1413 duk_memzero((void *) &u, sizeof(u));
1414
1415 /*
1416 * Figure out how generated digits match up with the mantissa,
1417 * and then perform rounding. If mantissa overflows, need to
1418 * recompute the exponent (it is bumped and may overflow to
1419 * infinity).
1420 *
1421 * For normal numbers the leading '1' is hidden and ignored,
1422 * and the last bit is used for rounding:
1423 *
1424 * rounding pt
1425 * <--------52------->|
1426 * 1 x x x x ... x x x x|y ==> x x x x ... x x x x
1427 *
1428 * For denormals, the leading '1' is included in the number,
1429 * and the rounding point is different:
1430 *
1431 * rounding pt
1432 * <--52 or less--->|
1433 * 1 x x x x ... x x|x x y ==> 0 0 ... 1 x x ... x x
1434 *
1435 * The largest denormals will have a mantissa beginning with
1436 * a '1' (the explicit leading bit); smaller denormals will
1437 * have leading zero bits.
1438 *
1439 * If the exponent would become too high, the result becomes
1440 * Infinity. If the exponent is so small that the entire
1441 * mantissa becomes zero, the result becomes zero.
1442 *
1443 * Note: the Dragon4 'k' is off-by-one with respect to the IEEE
1444 * exponent. For instance, k==0 indicates that the leading '1'
1445 * digit is at the first binary fraction position (0.1xxx...);
1446 * the corresponding IEEE exponent would be -1.
1447 */
1448
1449 skip_round = 0;
1450
1451 recheck_exp:
1452
1453 expt = nc_ctx->k - 1; /* IEEE exp without bias */
1454 if (expt > 1023) {
1455 /* Infinity */
1456 bitstart = -255; /* needed for inf: causes mantissa to become zero,
1457 * and rounding to be skipped.
1458 */
1459 expt = 2047;
1460 } else if (expt >= -1022) {
1461 /* normal */
1462 bitstart = 1; /* skip leading digit */
1463 expt += DUK__IEEE_DOUBLE_EXP_BIAS;
1464 DUK_ASSERT(expt >= 1 && expt <= 2046);
1465 } else {
1466 /* denormal or zero */
1467 bitstart = 1023 + expt; /* expt==-1023 -> bitstart=0 (leading 1);
1468 * expt==-1024 -> bitstart=-1 (one left of leading 1), etc
1469 */
1470 expt = 0;
1471 }
1472 bitround = bitstart + 52;
1473
1474 DUK_DDD(DUK_DDDPRINT("ieee expt=%ld, bitstart=%ld, bitround=%ld",
1475 (long) expt, (long) bitstart, (long) bitround));
1476
1477 if (!skip_round) {
1478 if (duk__dragon4_fixed_format_round(nc_ctx, bitround)) {
1479 /* Corner case: see test-numconv-parse-mant-carry.js. We could
1480 * just bump the exponent and update bitstart, but it's more robust
1481 * to recompute (but avoid rounding twice).
1482 */
1483 DUK_DDD(DUK_DDDPRINT("rounding caused exponent to be bumped, recheck exponent"));
1484 skip_round = 1;
1485 goto recheck_exp;
1486 }
1487 }
1488
1489 /*
1490 * Create mantissa
1491 */
1492
1493 t = 0;
1494 for (i = 0; i < 52; i++) {
1495 bitidx = bitstart + 52 - 1 - i;
1496 if (bitidx >= nc_ctx->count) {
1497 v = 0;
1498 } else if (bitidx < 0) {
1499 v = 0;
1500 } else {
1501 v = nc_ctx->digits[bitidx];
1502 }
1503 DUK_ASSERT(v == 0 || v == 1);
1504 t += v << (i % 32);
1505 if (i == 31) {
1506 /* low 32 bits is complete */
1507 DUK_DBLUNION_SET_LOW32(&u, t);
1508 t = 0;
1509 }
1510 }
1511 /* t has high mantissa */
1512
1513 DUK_DDD(DUK_DDDPRINT("mantissa is complete: %08lx %08lx",
1514 (unsigned long) t,
1515 (unsigned long) DUK_DBLUNION_GET_LOW32(&u)));
1516
1517 DUK_ASSERT(expt >= 0 && expt <= 0x7ffL);
1518 t += ((duk_uint32_t) expt) << 20;
1519 #if 0 /* caller handles sign change */
1520 if (negative) {
1521 t |= 0x80000000U;
1522 }
1523 #endif
1524 DUK_DBLUNION_SET_HIGH32(&u, t);
1525
1526 DUK_DDD(DUK_DDDPRINT("number is complete: %08lx %08lx",
1527 (unsigned long) DUK_DBLUNION_GET_HIGH32(&u),
1528 (unsigned long) DUK_DBLUNION_GET_LOW32(&u)));
1529
1530 *x = DUK_DBLUNION_GET_DOUBLE(&u);
1531 }
1532
1533 /*
1534 * Exposed number-to-string API
1535 *
1536 * Input: [ number ]
1537 * Output: [ string ]
1538 */
1539
duk__numconv_stringify_raw(duk_hthread * thr,duk_small_int_t radix,duk_small_int_t digits,duk_small_uint_t flags)1540 DUK_LOCAL DUK_NOINLINE void duk__numconv_stringify_raw(duk_hthread *thr, duk_small_int_t radix, duk_small_int_t digits, duk_small_uint_t flags) {
1541 duk_double_t x;
1542 duk_small_int_t c;
1543 duk_small_int_t neg;
1544 duk_uint32_t uval;
1545 duk__numconv_stringify_ctx nc_ctx_alloc; /* large context; around 2kB now */
1546 duk__numconv_stringify_ctx *nc_ctx = &nc_ctx_alloc;
1547
1548 x = (duk_double_t) duk_require_number(thr, -1);
1549 duk_pop(thr);
1550
1551 /*
1552 * Handle special cases (NaN, infinity, zero).
1553 */
1554
1555 c = (duk_small_int_t) DUK_FPCLASSIFY(x);
1556 if (DUK_SIGNBIT((double) x)) {
1557 x = -x;
1558 neg = 1;
1559 } else {
1560 neg = 0;
1561 }
1562
1563 /* NaN sign bit is platform specific with unpacked, un-normalized NaNs */
1564 DUK_ASSERT(c == DUK_FP_NAN || DUK_SIGNBIT((double) x) == 0);
1565
1566 if (c == DUK_FP_NAN) {
1567 duk_push_hstring_stridx(thr, DUK_STRIDX_NAN);
1568 return;
1569 } else if (c == DUK_FP_INFINITE) {
1570 if (neg) {
1571 /* -Infinity */
1572 duk_push_hstring_stridx(thr, DUK_STRIDX_MINUS_INFINITY);
1573 } else {
1574 /* Infinity */
1575 duk_push_hstring_stridx(thr, DUK_STRIDX_INFINITY);
1576 }
1577 return;
1578 } else if (c == DUK_FP_ZERO) {
1579 /* We can't shortcut zero here if it goes through special formatting
1580 * (such as forced exponential notation).
1581 */
1582 ;
1583 }
1584
1585 /*
1586 * Handle integers in 32-bit range (that is, [-(2**32-1),2**32-1])
1587 * specially, as they're very likely for embedded programs. This
1588 * is now done for all radix values. We must be careful not to use
1589 * the fast path when special formatting (e.g. forced exponential)
1590 * is in force.
1591 *
1592 * XXX: could save space by supporting radix 10 only and using
1593 * sprintf "%lu" for the fast path and for exponent formatting.
1594 */
1595
1596 uval = duk_double_to_uint32_t(x);
1597 if (duk_double_equals((double) uval, x) && /* integer number in range */
1598 flags == 0) { /* no special formatting */
1599 /* use bigint area as a temp */
1600 duk_uint8_t *buf = (duk_uint8_t *) (&nc_ctx->f);
1601 duk_uint8_t *p = buf;
1602
1603 DUK_ASSERT(DUK__NUMCONV_CTX_BIGINTS_SIZE >= 32 + 1); /* max size: radix=2 + sign */
1604 if (neg && uval != 0) {
1605 /* no negative sign for zero */
1606 *p++ = (duk_uint8_t) '-';
1607 }
1608 p += duk__dragon4_format_uint32(p, uval, radix);
1609 duk_push_lstring(thr, (const char *) buf, (duk_size_t) (p - buf));
1610 return;
1611 }
1612
1613 /*
1614 * Dragon4 setup.
1615 *
1616 * Convert double from IEEE representation for conversion;
1617 * normal finite values have an implicit leading 1-bit. The
1618 * slow path algorithm doesn't handle zero, so zero is special
1619 * cased here but still creates a valid nc_ctx, and goes
1620 * through normal formatting in case special formatting has
1621 * been requested (e.g. forced exponential format: 0 -> "0e+0").
1622 */
1623
1624 /* Would be nice to bulk clear the allocation, but the context
1625 * is 1-2 kilobytes and nothing should rely on it being zeroed.
1626 */
1627 #if 0
1628 duk_memzero((void *) nc_ctx, sizeof(*nc_ctx)); /* slow init, do only for slow path cases */
1629 #endif
1630
1631 nc_ctx->is_s2n = 0;
1632 nc_ctx->b = 2;
1633 nc_ctx->B = radix;
1634 nc_ctx->abs_pos = 0;
1635 if (flags & DUK_N2S_FLAG_FIXED_FORMAT) {
1636 nc_ctx->is_fixed = 1;
1637 if (flags & DUK_N2S_FLAG_FRACTION_DIGITS) {
1638 /* absolute req_digits; e.g. digits = 1 -> last digit is 0,
1639 * but add an extra digit for rounding.
1640 */
1641 nc_ctx->abs_pos = 1;
1642 nc_ctx->req_digits = (-digits + 1) - 1;
1643 } else {
1644 nc_ctx->req_digits = digits + 1;
1645 }
1646 } else {
1647 nc_ctx->is_fixed = 0;
1648 nc_ctx->req_digits = 0;
1649 }
1650
1651 if (c == DUK_FP_ZERO) {
1652 /* Zero special case: fake requested number of zero digits; ensure
1653 * no sign bit is printed. Relative and absolute fixed format
1654 * require separate handling.
1655 */
1656 duk_small_int_t count;
1657 if (nc_ctx->is_fixed) {
1658 if (nc_ctx->abs_pos) {
1659 count = digits + 2; /* lead zero + 'digits' fractions + 1 for rounding */
1660 } else {
1661 count = digits + 1; /* + 1 for rounding */
1662 }
1663 } else {
1664 count = 1;
1665 }
1666 DUK_DDD(DUK_DDDPRINT("count=%ld", (long) count));
1667 DUK_ASSERT(count >= 1);
1668 duk_memzero((void *) nc_ctx->digits, (size_t) count);
1669 nc_ctx->count = count;
1670 nc_ctx->k = 1; /* 0.000... */
1671 neg = 0;
1672 goto zero_skip;
1673 }
1674
1675 duk__dragon4_double_to_ctx(nc_ctx, x); /* -> sets 'f' and 'e' */
1676 DUK__BI_PRINT("f", &nc_ctx->f);
1677 DUK_DDD(DUK_DDDPRINT("e=%ld", (long) nc_ctx->e));
1678
1679 /*
1680 * Dragon4 slow path digit generation.
1681 */
1682
1683 duk__dragon4_prepare(nc_ctx); /* setup many variables in nc_ctx */
1684
1685 DUK_DDD(DUK_DDDPRINT("after prepare:"));
1686 DUK__BI_PRINT("r", &nc_ctx->r);
1687 DUK__BI_PRINT("s", &nc_ctx->s);
1688 DUK__BI_PRINT("mp", &nc_ctx->mp);
1689 DUK__BI_PRINT("mm", &nc_ctx->mm);
1690
1691 duk__dragon4_scale(nc_ctx);
1692
1693 DUK_DDD(DUK_DDDPRINT("after scale; k=%ld", (long) nc_ctx->k));
1694 DUK__BI_PRINT("r", &nc_ctx->r);
1695 DUK__BI_PRINT("s", &nc_ctx->s);
1696 DUK__BI_PRINT("mp", &nc_ctx->mp);
1697 DUK__BI_PRINT("mm", &nc_ctx->mm);
1698
1699 duk__dragon4_generate(nc_ctx);
1700
1701 /*
1702 * Convert and push final string.
1703 */
1704
1705 zero_skip:
1706
1707 if (flags & DUK_N2S_FLAG_FIXED_FORMAT) {
1708 /* Perform fixed-format rounding. */
1709 duk_small_int_t roundpos;
1710 if (flags & DUK_N2S_FLAG_FRACTION_DIGITS) {
1711 /* 'roundpos' is relative to nc_ctx->k and increases to the right
1712 * (opposite of how 'k' changes).
1713 */
1714 roundpos = -digits; /* absolute position for digit considered for rounding */
1715 roundpos = nc_ctx->k - roundpos;
1716 } else {
1717 roundpos = digits;
1718 }
1719 DUK_DDD(DUK_DDDPRINT("rounding: k=%ld, count=%ld, digits=%ld, roundpos=%ld",
1720 (long) nc_ctx->k, (long) nc_ctx->count, (long) digits, (long) roundpos));
1721 (void) duk__dragon4_fixed_format_round(nc_ctx, roundpos);
1722
1723 /* Note: 'count' is currently not adjusted by rounding (i.e. the
1724 * digits are not "chopped off". That shouldn't matter because
1725 * the digit position (absolute or relative) is passed on to the
1726 * convert-and-push function.
1727 */
1728 }
1729
1730 duk__dragon4_convert_and_push(nc_ctx, thr, radix, digits, flags, neg);
1731 }
1732
duk_numconv_stringify(duk_hthread * thr,duk_small_int_t radix,duk_small_int_t digits,duk_small_uint_t flags)1733 DUK_INTERNAL void duk_numconv_stringify(duk_hthread *thr, duk_small_int_t radix, duk_small_int_t digits, duk_small_uint_t flags) {
1734 duk_native_stack_check(thr);
1735 duk__numconv_stringify_raw(thr, radix, digits, flags);
1736 }
1737
1738 /*
1739 * Exposed string-to-number API
1740 *
1741 * Input: [ string ]
1742 * Output: [ number ]
1743 *
1744 * If number parsing fails, a NaN is pushed as the result. If number parsing
1745 * fails due to an internal error, an InternalError is thrown.
1746 */
1747
duk__numconv_parse_raw(duk_hthread * thr,duk_small_int_t radix,duk_small_uint_t flags)1748 DUK_LOCAL DUK_NOINLINE void duk__numconv_parse_raw(duk_hthread *thr, duk_small_int_t radix, duk_small_uint_t flags) {
1749 duk__numconv_stringify_ctx nc_ctx_alloc; /* large context; around 2kB now */
1750 duk__numconv_stringify_ctx *nc_ctx = &nc_ctx_alloc;
1751 duk_double_t res;
1752 duk_hstring *h_str;
1753 duk_int_t expt;
1754 duk_bool_t expt_neg;
1755 duk_small_int_t expt_adj;
1756 duk_small_int_t neg;
1757 duk_small_int_t dig;
1758 duk_small_int_t dig_whole;
1759 duk_small_int_t dig_lzero;
1760 duk_small_int_t dig_frac;
1761 duk_small_int_t dig_expt;
1762 duk_small_int_t dig_prec;
1763 const duk__exp_limits *explim;
1764 const duk_uint8_t *p;
1765 duk_small_int_t ch;
1766
1767 DUK_DDD(DUK_DDDPRINT("parse number: %!T, radix=%ld, flags=0x%08lx",
1768 (duk_tval *) duk_get_tval(thr, -1),
1769 (long) radix, (unsigned long) flags));
1770
1771 DUK_ASSERT(radix >= 2 && radix <= 36);
1772 DUK_ASSERT(radix - 2 < (duk_small_int_t) sizeof(duk__str2num_digits_for_radix));
1773
1774 /*
1775 * Preliminaries: trim, sign, Infinity check
1776 *
1777 * We rely on the interned string having a NUL terminator, which will
1778 * cause a parse failure wherever it is encountered. As a result, we
1779 * don't need separate pointer checks.
1780 *
1781 * There is no special parsing for 'NaN' in the specification although
1782 * 'Infinity' (with an optional sign) is allowed in some contexts.
1783 * Some contexts allow plus/minus sign, while others only allow the
1784 * minus sign (like JSON.parse()).
1785 *
1786 * Automatic hex number detection (leading '0x' or '0X') and octal
1787 * number detection (leading '0' followed by at least one octal digit)
1788 * is done here too.
1789 *
1790 * Symbols are not explicitly rejected here (that's up to the caller).
1791 * If a symbol were passed here, it should ultimately safely fail
1792 * parsing due to a syntax error.
1793 */
1794
1795 if (flags & DUK_S2N_FLAG_TRIM_WHITE) {
1796 /* Leading / trailing whitespace is sometimes accepted and
1797 * sometimes not. After white space trimming, all valid input
1798 * characters are pure ASCII.
1799 */
1800 duk_trim(thr, -1);
1801 }
1802 h_str = duk_require_hstring(thr, -1);
1803 DUK_ASSERT(h_str != NULL);
1804 p = (const duk_uint8_t *) DUK_HSTRING_GET_DATA(h_str);
1805
1806 neg = 0;
1807 ch = *p;
1808 if (ch == (duk_small_int_t) '+') {
1809 if ((flags & DUK_S2N_FLAG_ALLOW_PLUS) == 0) {
1810 DUK_DDD(DUK_DDDPRINT("parse failed: leading plus sign not allowed"));
1811 goto parse_fail;
1812 }
1813 p++;
1814 } else if (ch == (duk_small_int_t) '-') {
1815 if ((flags & DUK_S2N_FLAG_ALLOW_MINUS) == 0) {
1816 DUK_DDD(DUK_DDDPRINT("parse failed: leading minus sign not allowed"));
1817 goto parse_fail;
1818 }
1819 p++;
1820 neg = 1;
1821 }
1822
1823 if ((flags & DUK_S2N_FLAG_ALLOW_INF) && DUK_STRNCMP((const char *) p, "Infinity", 8) == 0) {
1824 /* Don't check for Infinity unless the context allows it.
1825 * 'Infinity' is a valid integer literal in e.g. base-36:
1826 *
1827 * parseInt('Infinity', 36)
1828 * 1461559270678
1829 */
1830
1831 if ((flags & DUK_S2N_FLAG_ALLOW_GARBAGE) == 0 && p[8] != DUK_ASC_NUL) {
1832 DUK_DDD(DUK_DDDPRINT("parse failed: trailing garbage after matching 'Infinity' not allowed"));
1833 goto parse_fail;
1834 } else {
1835 res = DUK_DOUBLE_INFINITY;
1836 goto negcheck_and_ret;
1837 }
1838 }
1839 ch = *p;
1840 if (ch == (duk_small_int_t) '0') {
1841 duk_small_int_t detect_radix = 0;
1842 ch = DUK_LOWERCASE_CHAR_ASCII(p[1]); /* 'x' or 'X' -> 'x' */
1843 if ((flags & DUK_S2N_FLAG_ALLOW_AUTO_HEX_INT) && ch == DUK_ASC_LC_X) {
1844 DUK_DDD(DUK_DDDPRINT("detected 0x/0X hex prefix, changing radix and preventing fractions and exponent"));
1845 detect_radix = 16;
1846 #if 0
1847 } else if ((flags & DUK_S2N_FLAG_ALLOW_AUTO_LEGACY_OCT_INT) &&
1848 (ch >= (duk_small_int_t) '0' && ch <= (duk_small_int_t) '9')) {
1849 DUK_DDD(DUK_DDDPRINT("detected 0n oct prefix, changing radix and preventing fractions and exponent"));
1850 detect_radix = 8;
1851
1852 /* NOTE: if this legacy octal case is added back, it has
1853 * different flags and 'p' advance so this needs to be
1854 * reworked.
1855 */
1856 flags |= DUK_S2N_FLAG_ALLOW_EMPTY_AS_ZERO; /* interpret e.g. '09' as '0', not NaN */
1857 p += 1;
1858 #endif
1859 } else if ((flags & DUK_S2N_FLAG_ALLOW_AUTO_OCT_INT) && ch == DUK_ASC_LC_O) {
1860 DUK_DDD(DUK_DDDPRINT("detected 0o oct prefix, changing radix and preventing fractions and exponent"));
1861 detect_radix = 8;
1862 } else if ((flags & DUK_S2N_FLAG_ALLOW_AUTO_BIN_INT) && ch == DUK_ASC_LC_B) {
1863 DUK_DDD(DUK_DDDPRINT("detected 0b bin prefix, changing radix and preventing fractions and exponent"));
1864 detect_radix = 2;
1865 }
1866 if (detect_radix > 0) {
1867 radix = detect_radix;
1868 /* Clear empty as zero flag: interpret e.g. '0x' and '0xg' as a NaN (= parse error) */
1869 flags &= ~(DUK_S2N_FLAG_ALLOW_EXP | DUK_S2N_FLAG_ALLOW_EMPTY_FRAC |
1870 DUK_S2N_FLAG_ALLOW_FRAC | DUK_S2N_FLAG_ALLOW_NAKED_FRAC |
1871 DUK_S2N_FLAG_ALLOW_EMPTY_AS_ZERO);
1872 flags |= DUK_S2N_FLAG_ALLOW_LEADING_ZERO; /* allow e.g. '0x0009' and '0b00010001' */
1873 p += 2;
1874 }
1875 }
1876
1877 /*
1878 * Scan number and setup for Dragon4.
1879 *
1880 * The fast path case is detected during setup: an integer which
1881 * can be converted without rounding, no net exponent. The fast
1882 * path could be implemented as a separate scan, but may not really
1883 * be worth it: the multiplications for building 'f' are not
1884 * expensive when 'f' is small.
1885 *
1886 * The significand ('f') must contain enough bits of (apparent)
1887 * accuracy, so that Dragon4 will generate enough binary output digits.
1888 * For decimal numbers, this means generating a 20-digit significand,
1889 * which should yield enough practical accuracy to parse IEEE doubles.
1890 * In fact, the ECMAScript specification explicitly allows an
1891 * implementation to treat digits beyond 20 as zeroes (and even
1892 * to round the 20th digit upwards). For non-decimal numbers, the
1893 * appropriate number of digits has been precomputed for comparable
1894 * accuracy.
1895 *
1896 * Digit counts:
1897 *
1898 * [ dig_lzero ]
1899 * |
1900 * .+-..---[ dig_prec ]----.
1901 * | || |
1902 * 0000123.456789012345678901234567890e+123456
1903 * | | | | | |
1904 * `--+--' `------[ dig_frac ]-------' `-+--'
1905 * | |
1906 * [ dig_whole ] [ dig_expt ]
1907 *
1908 * dig_frac and dig_expt are -1 if not present
1909 * dig_lzero is only computed for whole number part
1910 *
1911 * Parsing state
1912 *
1913 * Parsing whole part dig_frac < 0 AND dig_expt < 0
1914 * Parsing fraction part dig_frac >= 0 AND dig_expt < 0
1915 * Parsing exponent part dig_expt >= 0 (dig_frac may be < 0 or >= 0)
1916 *
1917 * Note: in case we hit an implementation limit (like exponent range),
1918 * we should throw an error, NOT return NaN or Infinity. Even with
1919 * very large exponent (or significand) values the final result may be
1920 * finite, so NaN/Infinity would be incorrect.
1921 */
1922
1923 duk__bi_set_small(&nc_ctx->f, 0);
1924 dig_prec = 0;
1925 dig_lzero = 0;
1926 dig_whole = 0;
1927 dig_frac = -1;
1928 dig_expt = -1;
1929 expt = 0;
1930 expt_adj = 0; /* essentially tracks digit position of lowest 'f' digit */
1931 expt_neg = 0;
1932 for (;;) {
1933 ch = *p++;
1934
1935 DUK_DDD(DUK_DDDPRINT("parse digits: p=%p, ch='%c' (%ld), expt=%ld, expt_adj=%ld, "
1936 "dig_whole=%ld, dig_frac=%ld, dig_expt=%ld, dig_lzero=%ld, dig_prec=%ld",
1937 (const void *) p, (int) ((ch >= 0x20 && ch <= 0x7e) ? ch : '?'), (long) ch,
1938 (long) expt, (long) expt_adj, (long) dig_whole, (long) dig_frac,
1939 (long) dig_expt, (long) dig_lzero, (long) dig_prec));
1940 DUK__BI_PRINT("f", &nc_ctx->f);
1941
1942 /* Most common cases first. */
1943 if (ch >= (duk_small_int_t) '0' && ch <= (duk_small_int_t) '9') {
1944 dig = (duk_small_int_t) ch - '0' + 0;
1945 } else if (ch == (duk_small_int_t) '.') {
1946 /* A leading digit is not required in some cases, e.g. accept ".123".
1947 * In other cases (JSON.parse()) a leading digit is required. This
1948 * is checked for after the loop.
1949 */
1950 if (dig_frac >= 0 || dig_expt >= 0) {
1951 if (flags & DUK_S2N_FLAG_ALLOW_GARBAGE) {
1952 DUK_DDD(DUK_DDDPRINT("garbage termination (invalid period)"));
1953 break;
1954 } else {
1955 DUK_DDD(DUK_DDDPRINT("parse failed: period not allowed"));
1956 goto parse_fail;
1957 }
1958 }
1959
1960 if ((flags & DUK_S2N_FLAG_ALLOW_FRAC) == 0) {
1961 /* Some contexts don't allow fractions at all; this can't be a
1962 * post-check because the state ('f' and expt) would be incorrect.
1963 */
1964 if (flags & DUK_S2N_FLAG_ALLOW_GARBAGE) {
1965 DUK_DDD(DUK_DDDPRINT("garbage termination (invalid first period)"));
1966 break;
1967 } else {
1968 DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed"));
1969 }
1970 }
1971
1972 DUK_DDD(DUK_DDDPRINT("start fraction part"));
1973 dig_frac = 0;
1974 continue;
1975 } else if (ch == (duk_small_int_t) 0) {
1976 DUK_DDD(DUK_DDDPRINT("NUL termination"));
1977 break;
1978 } else if ((flags & DUK_S2N_FLAG_ALLOW_EXP) &&
1979 dig_expt < 0 && (ch == (duk_small_int_t) 'e' || ch == (duk_small_int_t) 'E')) {
1980 /* Note: we don't parse back exponent notation for anything else
1981 * than radix 10, so this is not an ambiguous check (e.g. hex
1982 * exponent values may have 'e' either as a significand digit
1983 * or as an exponent separator).
1984 *
1985 * If the exponent separator occurs twice, 'e' will be interpreted
1986 * as a digit (= 14) and will be rejected as an invalid decimal
1987 * digit.
1988 */
1989
1990 DUK_DDD(DUK_DDDPRINT("start exponent part"));
1991
1992 /* Exponent without a sign or with a +/- sign is accepted
1993 * by all call sites (even JSON.parse()).
1994 */
1995 ch = *p;
1996 if (ch == (duk_small_int_t) '-') {
1997 expt_neg = 1;
1998 p++;
1999 } else if (ch == (duk_small_int_t) '+') {
2000 p++;
2001 }
2002 dig_expt = 0;
2003 continue;
2004 } else if (ch >= (duk_small_int_t) 'a' && ch <= (duk_small_int_t) 'z') {
2005 dig = (duk_small_int_t) (ch - (duk_small_int_t) 'a' + 0x0a);
2006 } else if (ch >= (duk_small_int_t) 'A' && ch <= (duk_small_int_t) 'Z') {
2007 dig = (duk_small_int_t) (ch - (duk_small_int_t) 'A' + 0x0a);
2008 } else {
2009 dig = 255; /* triggers garbage digit check below */
2010 }
2011 DUK_ASSERT((dig >= 0 && dig <= 35) || dig == 255);
2012
2013 if (dig >= radix) {
2014 if (flags & DUK_S2N_FLAG_ALLOW_GARBAGE) {
2015 DUK_DDD(DUK_DDDPRINT("garbage termination"));
2016 break;
2017 } else {
2018 DUK_DDD(DUK_DDDPRINT("parse failed: trailing garbage or invalid digit"));
2019 goto parse_fail;
2020 }
2021 }
2022
2023 if (dig_expt < 0) {
2024 /* whole or fraction digit */
2025
2026 if (dig_prec < duk__str2num_digits_for_radix[radix - 2]) {
2027 /* significant from precision perspective */
2028
2029 duk_small_int_t f_zero = duk__bi_is_zero(&nc_ctx->f);
2030 if (f_zero && dig == 0) {
2031 /* Leading zero is not counted towards precision digits; not
2032 * in the integer part, nor in the fraction part.
2033 */
2034 if (dig_frac < 0) {
2035 dig_lzero++;
2036 }
2037 } else {
2038 /* XXX: join these ops (multiply-accumulate), but only if
2039 * code footprint decreases.
2040 */
2041 duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->f, (duk_uint32_t) radix);
2042 duk__bi_add_small(&nc_ctx->f, &nc_ctx->t1, (duk_uint32_t) dig);
2043 dig_prec++;
2044 }
2045 } else {
2046 /* Ignore digits beyond a radix-specific limit, but note them
2047 * in expt_adj.
2048 */
2049 expt_adj++;
2050 }
2051
2052 if (dig_frac >= 0) {
2053 dig_frac++;
2054 expt_adj--;
2055 } else {
2056 dig_whole++;
2057 }
2058 } else {
2059 /* exponent digit */
2060
2061 DUK_ASSERT(radix == 10);
2062 expt = expt * radix + dig;
2063 if (expt > DUK_S2N_MAX_EXPONENT) {
2064 /* Impose a reasonable exponent limit, so that exp
2065 * doesn't need to get tracked using a bigint.
2066 */
2067 DUK_DDD(DUK_DDDPRINT("parse failed: exponent too large"));
2068 goto parse_explimit_error;
2069 }
2070 dig_expt++;
2071 }
2072 }
2073
2074 /* Leading zero. */
2075
2076 if (dig_lzero > 0 && dig_whole > 1) {
2077 if ((flags & DUK_S2N_FLAG_ALLOW_LEADING_ZERO) == 0) {
2078 DUK_DDD(DUK_DDDPRINT("parse failed: leading zeroes not allowed in integer part"));
2079 goto parse_fail;
2080 }
2081 }
2082
2083 /* Validity checks for various fraction formats ("0.1", ".1", "1.", "."). */
2084
2085 if (dig_whole == 0) {
2086 if (dig_frac == 0) {
2087 /* "." is not accepted in any format */
2088 DUK_DDD(DUK_DDDPRINT("parse failed: plain period without leading or trailing digits"));
2089 goto parse_fail;
2090 } else if (dig_frac > 0) {
2091 /* ".123" */
2092 if ((flags & DUK_S2N_FLAG_ALLOW_NAKED_FRAC) == 0) {
2093 DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed without "
2094 "leading integer digit(s)"));
2095 goto parse_fail;
2096 }
2097 } else {
2098 /* Empty ("") is allowed in some formats (e.g. Number(''), as zero,
2099 * but it must not have a leading +/- sign (GH-2019). Note that
2100 * for Number(), h_str is already trimmed so we can check for zero
2101 * length and still get Number(' + ') == NaN.
2102 */
2103 if ((flags & DUK_S2N_FLAG_ALLOW_EMPTY_AS_ZERO) == 0) {
2104 DUK_DDD(DUK_DDDPRINT("parse failed: empty string not allowed (as zero)"));
2105 goto parse_fail;
2106 } else if (DUK_HSTRING_GET_BYTELEN(h_str) != 0) {
2107 DUK_DDD(DUK_DDDPRINT("parse failed: no digits, but not empty (had a +/- sign)"));
2108 goto parse_fail;
2109 }
2110 }
2111 } else {
2112 if (dig_frac == 0) {
2113 /* "123." is allowed in some formats */
2114 if ((flags & DUK_S2N_FLAG_ALLOW_EMPTY_FRAC) == 0) {
2115 DUK_DDD(DUK_DDDPRINT("parse failed: empty fractions"));
2116 goto parse_fail;
2117 }
2118 } else if (dig_frac > 0) {
2119 /* "123.456" */
2120 ;
2121 } else {
2122 /* "123" */
2123 ;
2124 }
2125 }
2126
2127 /* Exponent without digits (e.g. "1e" or "1e+"). If trailing garbage is
2128 * allowed, ignore exponent part as garbage (= parse as "1", i.e. exp 0).
2129 */
2130
2131 if (dig_expt == 0) {
2132 if ((flags & DUK_S2N_FLAG_ALLOW_GARBAGE) == 0) {
2133 DUK_DDD(DUK_DDDPRINT("parse failed: empty exponent"));
2134 goto parse_fail;
2135 }
2136 DUK_ASSERT(expt == 0);
2137 }
2138
2139 if (expt_neg) {
2140 expt = -expt;
2141 }
2142 DUK_DDD(DUK_DDDPRINT("expt=%ld, expt_adj=%ld, net exponent -> %ld",
2143 (long) expt, (long) expt_adj, (long) (expt + expt_adj)));
2144 expt += expt_adj;
2145
2146 /* Fast path check. */
2147
2148 if (nc_ctx->f.n <= 1 && /* 32-bit value */
2149 expt == 0 /* no net exponent */) {
2150 /* Fast path is triggered for no exponent and also for balanced exponent
2151 * and fraction parts, e.g. for "1.23e2" == "123". Remember to respect
2152 * zero sign.
2153 */
2154
2155 /* XXX: could accept numbers larger than 32 bits, e.g. up to 53 bits? */
2156 DUK_DDD(DUK_DDDPRINT("fast path number parse"));
2157 if (nc_ctx->f.n == 1) {
2158 res = (double) nc_ctx->f.v[0];
2159 } else {
2160 res = 0.0;
2161 }
2162 goto negcheck_and_ret;
2163 }
2164
2165 /* Significand ('f') padding. */
2166
2167 while (dig_prec < duk__str2num_digits_for_radix[radix - 2]) {
2168 /* Pad significand with "virtual" zero digits so that Dragon4 will
2169 * have enough (apparent) precision to work with.
2170 */
2171 DUK_DDD(DUK_DDDPRINT("dig_prec=%ld, pad significand with zero", (long) dig_prec));
2172 duk__bi_mul_small_copy(&nc_ctx->f, (duk_uint32_t) radix, &nc_ctx->t1);
2173 DUK__BI_PRINT("f", &nc_ctx->f);
2174 expt--;
2175 dig_prec++;
2176 }
2177
2178 DUK_DDD(DUK_DDDPRINT("final exponent: %ld", (long) expt));
2179
2180 /* Detect zero special case. */
2181
2182 if (nc_ctx->f.n == 0) {
2183 /* This may happen even after the fast path check, if exponent is
2184 * not balanced (e.g. "0e1"). Remember to respect zero sign.
2185 */
2186 DUK_DDD(DUK_DDDPRINT("significand is zero"));
2187 res = 0.0;
2188 goto negcheck_and_ret;
2189 }
2190
2191
2192 /* Quick reject of too large or too small exponents. This check
2193 * would be incorrect for zero (e.g. "0e1000" is zero, not Infinity)
2194 * so zero check must be above.
2195 */
2196
2197 explim = &duk__str2num_exp_limits[radix - 2];
2198 if (expt > explim->upper) {
2199 DUK_DDD(DUK_DDDPRINT("exponent too large -> infinite"));
2200 res = (duk_double_t) DUK_DOUBLE_INFINITY;
2201 goto negcheck_and_ret;
2202 } else if (expt < explim->lower) {
2203 DUK_DDD(DUK_DDDPRINT("exponent too small -> zero"));
2204 res = (duk_double_t) 0.0;
2205 goto negcheck_and_ret;
2206 }
2207
2208 nc_ctx->is_s2n = 1;
2209 nc_ctx->e = expt;
2210 nc_ctx->b = radix;
2211 nc_ctx->B = 2;
2212 nc_ctx->is_fixed = 1;
2213 nc_ctx->abs_pos = 0;
2214 nc_ctx->req_digits = 53 + 1;
2215
2216 DUK__BI_PRINT("f", &nc_ctx->f);
2217 DUK_DDD(DUK_DDDPRINT("e=%ld", (long) nc_ctx->e));
2218
2219 /*
2220 * Dragon4 slow path (binary) digit generation.
2221 * An extra digit is generated for rounding.
2222 */
2223
2224 duk__dragon4_prepare(nc_ctx); /* setup many variables in nc_ctx */
2225
2226 DUK_DDD(DUK_DDDPRINT("after prepare:"));
2227 DUK__BI_PRINT("r", &nc_ctx->r);
2228 DUK__BI_PRINT("s", &nc_ctx->s);
2229 DUK__BI_PRINT("mp", &nc_ctx->mp);
2230 DUK__BI_PRINT("mm", &nc_ctx->mm);
2231
2232 duk__dragon4_scale(nc_ctx);
2233
2234 DUK_DDD(DUK_DDDPRINT("after scale; k=%ld", (long) nc_ctx->k));
2235 DUK__BI_PRINT("r", &nc_ctx->r);
2236 DUK__BI_PRINT("s", &nc_ctx->s);
2237 DUK__BI_PRINT("mp", &nc_ctx->mp);
2238 DUK__BI_PRINT("mm", &nc_ctx->mm);
2239
2240 duk__dragon4_generate(nc_ctx);
2241
2242 DUK_ASSERT(nc_ctx->count == 53 + 1);
2243
2244 /*
2245 * Convert binary digits into an IEEE double. Need to handle
2246 * denormals and rounding correctly.
2247 *
2248 * Some call sites currently assume the result is always a
2249 * non-fastint double. If this is changed, check all call
2250 * sites.
2251 */
2252
2253 duk__dragon4_ctx_to_double(nc_ctx, &res);
2254 goto negcheck_and_ret;
2255
2256 negcheck_and_ret:
2257 if (neg) {
2258 res = -res;
2259 }
2260 duk_pop(thr);
2261 duk_push_number(thr, (double) res);
2262 DUK_DDD(DUK_DDDPRINT("result: %!T", (duk_tval *) duk_get_tval(thr, -1)));
2263 return;
2264
2265 parse_fail:
2266 DUK_DDD(DUK_DDDPRINT("parse failed"));
2267 duk_pop(thr);
2268 duk_push_nan(thr);
2269 return;
2270
2271 parse_explimit_error:
2272 DUK_DDD(DUK_DDDPRINT("parse failed, internal error, can't return a value"));
2273 DUK_ERROR_RANGE(thr, "exponent too large");
2274 DUK_WO_NORETURN(return;);
2275 }
2276
duk_numconv_parse(duk_hthread * thr,duk_small_int_t radix,duk_small_uint_t flags)2277 DUK_INTERNAL void duk_numconv_parse(duk_hthread *thr, duk_small_int_t radix, duk_small_uint_t flags) {
2278 duk_native_stack_check(thr);
2279 duk__numconv_parse_raw(thr, radix, flags);
2280 }
2281