]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
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 src/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 | #ifdef DUK_USE_DDDPRINT | |
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 | #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]; | |
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 | #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 */ ); | |
113 | } | |
114 | #endif | |
115 | ||
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 */ | |
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 | if (n == 0) { | |
137 | return; | |
138 | } | |
139 | DUK_MEMCPY((void *) x->v, (const void *) y->v, (size_t) (sizeof(duk_uint32_t) * n)); | |
140 | } | |
141 | ||
142 | DUK_LOCAL void duk__bi_set_small(duk__bigint *x, duk_uint32_t v) { | |
143 | if (v == 0U) { | |
144 | x->n = 0; | |
145 | } else { | |
146 | x->n = 1; | |
147 | x->v[0] = v; | |
148 | } | |
149 | DUK_ASSERT(duk__bi_is_valid(x)); | |
150 | } | |
151 | ||
152 | /* Return value: <0 <=> x < y | |
153 | * 0 <=> x == y | |
154 | * >0 <=> x > y | |
155 | */ | |
156 | DUK_LOCAL int duk__bi_compare(duk__bigint *x, duk__bigint *y) { | |
157 | duk_small_int_t i, nx, ny; | |
158 | duk_uint32_t tx, ty; | |
159 | ||
160 | DUK_ASSERT(duk__bi_is_valid(x)); | |
161 | DUK_ASSERT(duk__bi_is_valid(y)); | |
162 | ||
163 | nx = x->n; | |
164 | ny = y->n; | |
165 | if (nx > ny) { | |
166 | goto ret_gt; | |
167 | } | |
168 | if (nx < ny) { | |
169 | goto ret_lt; | |
170 | } | |
171 | for (i = nx - 1; i >= 0; i--) { | |
172 | tx = x->v[i]; | |
173 | ty = y->v[i]; | |
174 | ||
175 | if (tx > ty) { | |
176 | goto ret_gt; | |
177 | } | |
178 | if (tx < ty) { | |
179 | goto ret_lt; | |
180 | } | |
181 | } | |
182 | ||
183 | return 0; | |
184 | ||
185 | ret_gt: | |
186 | return 1; | |
187 | ||
188 | ret_lt: | |
189 | return -1; | |
190 | } | |
191 | ||
192 | /* x <- y + z */ | |
193 | #ifdef DUK_USE_64BIT_OPS | |
194 | DUK_LOCAL void duk__bi_add(duk__bigint *x, duk__bigint *y, duk__bigint *z) { | |
195 | duk_uint64_t tmp; | |
196 | duk_small_int_t i, ny, nz; | |
197 | ||
198 | DUK_ASSERT(duk__bi_is_valid(y)); | |
199 | DUK_ASSERT(duk__bi_is_valid(z)); | |
200 | ||
201 | if (z->n > y->n) { | |
202 | duk__bigint *t; | |
203 | t = y; y = z; z = t; | |
204 | } | |
205 | DUK_ASSERT(y->n >= z->n); | |
206 | ||
207 | ny = y->n; nz = z->n; | |
208 | tmp = 0U; | |
209 | for (i = 0; i < ny; i++) { | |
210 | DUK_ASSERT(i < DUK__BI_MAX_PARTS); | |
211 | tmp += y->v[i]; | |
212 | if (i < nz) { | |
213 | tmp += z->v[i]; | |
214 | } | |
215 | x->v[i] = (duk_uint32_t) (tmp & 0xffffffffUL); | |
216 | tmp = tmp >> 32; | |
217 | } | |
218 | if (tmp != 0U) { | |
219 | DUK_ASSERT(i < DUK__BI_MAX_PARTS); | |
220 | x->v[i++] = (duk_uint32_t) tmp; | |
221 | } | |
222 | x->n = i; | |
223 | DUK_ASSERT(x->n <= DUK__BI_MAX_PARTS); | |
224 | ||
225 | /* no need to normalize */ | |
226 | DUK_ASSERT(duk__bi_is_valid(x)); | |
227 | } | |
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; | |
232 | ||
233 | DUK_ASSERT(duk__bi_is_valid(y)); | |
234 | DUK_ASSERT(duk__bi_is_valid(z)); | |
235 | ||
236 | if (z->n > y->n) { | |
237 | duk__bigint *t; | |
238 | t = y; y = z; z = t; | |
239 | } | |
240 | DUK_ASSERT(y->n >= z->n); | |
241 | ||
242 | ny = y->n; nz = z->n; | |
243 | carry = 0U; | |
244 | for (i = 0; i < ny; i++) { | |
245 | /* Carry is detected based on wrapping which relies on exact 32-bit | |
246 | * types. | |
247 | */ | |
248 | DUK_ASSERT(i < DUK__BI_MAX_PARTS); | |
249 | tmp1 = y->v[i]; | |
250 | tmp2 = tmp1; | |
251 | if (i < nz) { | |
252 | tmp2 += z->v[i]; | |
253 | } | |
254 | ||
255 | /* Careful with carry condition: | |
256 | * - If carry not added: 0x12345678 + 0 + 0xffffffff = 0x12345677 (< 0x12345678) | |
257 | * - If carry added: 0x12345678 + 1 + 0xffffffff = 0x12345678 (== 0x12345678) | |
258 | */ | |
259 | if (carry) { | |
260 | tmp2++; | |
261 | carry = (tmp2 <= tmp1 ? 1U : 0U); | |
262 | } else { | |
263 | carry = (tmp2 < tmp1 ? 1U : 0U); | |
264 | } | |
265 | ||
266 | x->v[i] = tmp2; | |
267 | } | |
268 | if (carry) { | |
269 | DUK_ASSERT(i < DUK__BI_MAX_PARTS); | |
270 | DUK_ASSERT(carry == 1U); | |
271 | x->v[i++] = carry; | |
272 | } | |
273 | x->n = i; | |
274 | DUK_ASSERT(x->n <= DUK__BI_MAX_PARTS); | |
275 | ||
276 | /* no need to normalize */ | |
277 | DUK_ASSERT(duk__bi_is_valid(x)); | |
278 | } | |
279 | #endif /* DUK_USE_64BIT_OPS */ | |
280 | ||
281 | /* x <- y + z */ | |
282 | DUK_LOCAL void duk__bi_add_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) { | |
283 | duk__bigint tmp; | |
284 | ||
285 | DUK_ASSERT(duk__bi_is_valid(y)); | |
286 | ||
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); | |
290 | ||
291 | DUK_ASSERT(duk__bi_is_valid(x)); | |
292 | } | |
293 | ||
294 | #if 0 /* unused */ | |
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); | |
298 | duk__bi_copy(x, t); | |
299 | } | |
300 | #endif | |
301 | ||
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; | |
306 | duk_uint32_t ty, tz; | |
307 | duk_int64_t tmp; | |
308 | ||
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); | |
313 | ||
314 | ny = y->n; nz = z->n; | |
315 | tmp = 0; | |
316 | for (i = 0; i < ny; i++) { | |
317 | ty = y->v[i]; | |
318 | if (i < nz) { | |
319 | tz = z->v[i]; | |
320 | } else { | |
321 | tz = 0; | |
322 | } | |
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 */ | |
326 | } | |
327 | DUK_ASSERT(tmp == 0); | |
328 | ||
329 | x->n = i; | |
330 | duk__bi_normalize(x); /* need to normalize, may even cancel to 0 */ | |
331 | DUK_ASSERT(duk__bi_is_valid(x)); | |
332 | } | |
333 | #else | |
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; | |
337 | ||
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); | |
342 | ||
343 | ny = y->n; nz = z->n; | |
344 | borrow = 0U; | |
345 | for (i = 0; i < ny; i++) { | |
346 | /* Borrow is detected based on wrapping which relies on exact 32-bit | |
347 | * types. | |
348 | */ | |
349 | tmp1 = y->v[i]; | |
350 | tmp2 = tmp1; | |
351 | if (i < nz) { | |
352 | tmp2 -= z->v[i]; | |
353 | } | |
354 | ||
355 | /* Careful with borrow condition: | |
356 | * - If borrow not subtracted: 0x12345678 - 0 - 0xffffffff = 0x12345679 (> 0x12345678) | |
357 | * - If borrow subtracted: 0x12345678 - 1 - 0xffffffff = 0x12345678 (== 0x12345678) | |
358 | */ | |
359 | if (borrow) { | |
360 | tmp2--; | |
361 | borrow = (tmp2 >= tmp1 ? 1U : 0U); | |
362 | } else { | |
363 | borrow = (tmp2 > tmp1 ? 1U : 0U); | |
364 | } | |
365 | ||
366 | x->v[i] = tmp2; | |
367 | } | |
368 | DUK_ASSERT(borrow == 0U); | |
369 | ||
370 | x->n = i; | |
371 | duk__bi_normalize(x); /* need to normalize, may even cancel to 0 */ | |
372 | DUK_ASSERT(duk__bi_is_valid(x)); | |
373 | } | |
374 | #endif | |
375 | ||
376 | #if 0 /* unused */ | |
377 | /* x <- y - z */ | |
378 | DUK_LOCAL void duk__bi_sub_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) { | |
379 | duk__bigint tmp; | |
380 | ||
381 | DUK_ASSERT(duk__bi_is_valid(y)); | |
382 | ||
383 | /* XXX: this could be optimized */ | |
384 | duk__bi_set_small(&tmp, z); | |
385 | duk__bi_sub(x, y, &tmp); | |
386 | ||
387 | DUK_ASSERT(duk__bi_is_valid(x)); | |
388 | } | |
389 | #endif | |
390 | ||
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); | |
394 | duk__bi_copy(x, t); | |
395 | } | |
396 | ||
397 | /* x <- y * z */ | |
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; | |
400 | ||
401 | DUK_ASSERT(duk__bi_is_valid(y)); | |
402 | DUK_ASSERT(duk__bi_is_valid(z)); | |
403 | ||
404 | nx = y->n + z->n; /* max possible */ | |
405 | DUK_ASSERT(nx <= DUK__BI_MAX_PARTS); | |
406 | ||
407 | if (nx == 0) { | |
408 | /* Both inputs are zero; cases where only one is zero can go | |
409 | * through main algorithm. | |
410 | */ | |
411 | x->n = 0; | |
412 | return; | |
413 | } | |
414 | ||
415 | DUK_MEMZERO((void *) x->v, (size_t) (sizeof(duk_uint32_t) * nx)); | |
416 | x->n = nx; | |
417 | ||
418 | nz = z->n; | |
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); | |
425 | tmp = tmp >> 32; | |
426 | } | |
427 | if (tmp > 0) { | |
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; | |
432 | } | |
433 | #else | |
434 | /* | |
435 | * Multiply + add + carry for 32-bit components using only 16x16->32 | |
436 | * multiplies and carry detection based on unsigned overflow. | |
437 | * | |
438 | * 1st mult, 32-bit: (A*2^16 + B) | |
439 | * 2nd mult, 32-bit: (C*2^16 + D) | |
440 | * 3rd add, 32-bit: E | |
441 | * 4th add, 32-bit: F | |
442 | * | |
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) | |
447 | */ | |
448 | duk_uint32_t a, b, c, d, e, f; | |
449 | duk_uint32_t r, s, t; | |
450 | ||
451 | a = y->v[i]; b = a & 0xffffUL; a = a >> 16; | |
452 | ||
453 | f = 0; | |
454 | for (j = 0; j < nz; j++) { | |
455 | c = z->v[j]; d = c & 0xffffUL; c = c >> 16; | |
456 | e = x->v[i+j]; | |
457 | ||
458 | /* build result as: (r << 32) + s: start with (BD + E + F) */ | |
459 | r = 0; | |
460 | s = b * d; | |
461 | ||
462 | /* add E */ | |
463 | t = s + e; | |
464 | if (t < s) { r++; } /* carry */ | |
465 | s = t; | |
466 | ||
467 | /* add F */ | |
468 | t = s + f; | |
469 | if (t < s) { r++; } /* carry */ | |
470 | s = t; | |
471 | ||
472 | /* add BC*2^16 */ | |
473 | t = b * c; | |
474 | r += (t >> 16); | |
475 | t = s + ((t & 0xffffUL) << 16); | |
476 | if (t < s) { r++; } /* carry */ | |
477 | s = t; | |
478 | ||
479 | /* add AD*2^16 */ | |
480 | t = a * d; | |
481 | r += (t >> 16); | |
482 | t = s + ((t & 0xffffUL) << 16); | |
483 | if (t < s) { r++; } /* carry */ | |
484 | s = t; | |
485 | ||
486 | /* add AC*2^32 */ | |
487 | t = a * c; | |
488 | r += t; | |
489 | ||
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, | |
493 | (unsigned long) s)); | |
494 | ||
495 | x->v[i+j] = s; | |
496 | f = r; | |
497 | } | |
498 | if (f > 0U) { | |
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; | |
503 | } | |
504 | #endif /* DUK_USE_64BIT_OPS */ | |
505 | } | |
506 | ||
507 | duk__bi_normalize(x); | |
508 | DUK_ASSERT(duk__bi_is_valid(x)); | |
509 | } | |
510 | ||
511 | /* x <- y * z */ | |
512 | DUK_LOCAL void duk__bi_mul_small(duk__bigint *x, duk__bigint *y, duk_uint32_t z) { | |
513 | duk__bigint tmp; | |
514 | ||
515 | DUK_ASSERT(duk__bi_is_valid(y)); | |
516 | ||
517 | /* XXX: this could be optimized */ | |
518 | duk__bi_set_small(&tmp, z); | |
519 | duk__bi_mul(x, y, &tmp); | |
520 | ||
521 | DUK_ASSERT(duk__bi_is_valid(x)); | |
522 | } | |
523 | ||
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); | |
527 | duk__bi_copy(x, t); | |
528 | } | |
529 | ||
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); | |
533 | duk__bi_copy(x, t); | |
534 | } | |
535 | ||
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); | |
539 | } | |
540 | ||
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 */ | |
544 | } | |
545 | ||
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: | |
549 | * | |
550 | * 1000........000 (52 zeroes; only "hidden bit" is set) | |
551 | */ | |
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))); | |
556 | } | |
557 | ||
558 | /* x <- (1<<y) */ | |
559 | DUK_LOCAL void duk__bi_twoexp(duk__bigint *x, duk_small_int_t y) { | |
560 | duk_small_int_t n, r; | |
561 | ||
562 | n = (y / 32) + 1; | |
563 | DUK_ASSERT(n > 0); | |
564 | r = y % 32; | |
565 | DUK_MEMZERO((void *) x->v, sizeof(duk_uint32_t) * n); | |
566 | x->n = n; | |
567 | x->v[n - 1] = (((duk_uint32_t) 1) << r); | |
568 | } | |
569 | ||
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 */ | |
573 | ||
574 | DUK_ASSERT(x != t1 && x != t2 && t1 != t2); /* distinct bignums, easy mistake to make */ | |
575 | DUK_ASSERT(b >= 0); | |
576 | DUK_ASSERT(y >= 0); | |
577 | ||
578 | if (b == 2) { | |
579 | duk__bi_twoexp(x, y); | |
580 | return; | |
581 | } | |
582 | ||
583 | /* http://en.wikipedia.org/wiki/Exponentiation_by_squaring */ | |
584 | ||
585 | DUK_DDD(DUK_DDDPRINT("exp_small: b=%ld, y=%ld", (long) b, (long) y)); | |
586 | ||
587 | duk__bi_set_small(x, 1); | |
588 | duk__bi_set_small(t1, b); | |
589 | for (;;) { | |
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. | |
593 | */ | |
594 | if (y & 0x01) { | |
595 | duk__bi_mul_copy(x, t1, t2); | |
596 | } | |
597 | y = y >> 1; | |
598 | if (y == 0) { | |
599 | break; | |
600 | } | |
601 | duk__bi_mul_copy(t1, t1, t2); | |
602 | } | |
603 | ||
604 | DUK__BI_PRINT("exp_small result", x); | |
605 | } | |
606 | ||
607 | /* | |
608 | * A Dragon4 number-to-string variant, based on: | |
609 | * | |
610 | * Guy L. Steele Jr., Jon L. White: "How to Print Floating-Point Numbers | |
611 | * Accurately" | |
612 | * | |
613 | * Robert G. Burger, R. Kent Dybvig: "Printing Floating-Point Numbers | |
614 | * Quickly and Accurately" | |
615 | * | |
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. | |
621 | * | |
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. | |
624 | * | |
625 | * See doc/number-conversion.rst for limitations. | |
626 | */ | |
627 | ||
628 | /* Maximum number of digits generated. */ | |
629 | #define DUK__MAX_OUTPUT_DIGITS 1040 /* (Number.MAX_VALUE).toString(2).length == 1024, + spare */ | |
630 | ||
631 | /* Maximum number of characters in formatted value. */ | |
632 | #define DUK__MAX_FORMATTED_LENGTH 1040 /* (-Number.MAX_VALUE).toString(2).length == 1025, + spare */ | |
633 | ||
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) | |
637 | ||
638 | typedef struct { | |
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 | |
642 | * more correct. | |
643 | */ | |
644 | duk__bigint f, r, s, mp, mm, t1, t2; | |
645 | ||
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) */ | |
657 | ||
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; | |
662 | ||
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. | |
666 | */ | |
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); \ | |
671 | } while (0) | |
672 | ||
673 | DUK_LOCAL duk_size_t duk__dragon4_format_uint32(duk_uint8_t *buf, duk_uint32_t x, duk_small_int_t radix) { | |
674 | duk_uint8_t *p; | |
675 | duk_size_t len; | |
676 | duk_small_int_t dig; | |
677 | duk_small_int_t t; | |
678 | ||
679 | DUK_ASSERT(radix >= 2 && radix <= 36); | |
680 | ||
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. | |
684 | */ | |
685 | ||
686 | p = buf + 32; | |
687 | for (;;) { | |
688 | t = x / radix; | |
689 | dig = x - t * radix; | |
690 | x = t; | |
691 | ||
692 | DUK_ASSERT(dig >= 0 && dig < 36); | |
693 | *(--p) = DUK__DIGITCHAR(dig); | |
694 | ||
695 | if (x == 0) { | |
696 | break; | |
697 | } | |
698 | } | |
699 | len = (duk_size_t) ((buf + 32) - p); | |
700 | ||
701 | DUK_MEMMOVE((void *) buf, (const void *) p, (size_t) len); | |
702 | ||
703 | return len; | |
704 | } | |
705 | ||
706 | DUK_LOCAL void duk__dragon4_prepare(duk__numconv_stringify_ctx *nc_ctx) { | |
707 | duk_small_int_t lowest_mantissa; | |
708 | ||
709 | #if 1 | |
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. | |
714 | */ | |
715 | if (duk__bi_is_even(&nc_ctx->f)) { | |
716 | DUK_DDD(DUK_DDDPRINT("f is even")); | |
717 | nc_ctx->low_ok = 1; | |
718 | nc_ctx->high_ok = 1; | |
719 | } else { | |
720 | DUK_DDD(DUK_DDDPRINT("f is odd")); | |
721 | nc_ctx->low_ok = 0; | |
722 | nc_ctx->high_ok = 0; | |
723 | } | |
724 | #else | |
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 | |
729 | * doesn't matter. | |
730 | */ | |
731 | nc_ctx->low_ok = 0; | |
732 | nc_ctx->high_ok = 0; | |
733 | #endif | |
734 | ||
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. | |
738 | */ | |
739 | if (nc_ctx->is_s2n) { | |
740 | lowest_mantissa = 0; | |
741 | } else { | |
742 | lowest_mantissa = duk__bi_is_2to52(&nc_ctx->f); | |
743 | } | |
744 | ||
745 | nc_ctx->unequal_gaps = 0; | |
746 | if (nc_ctx->e >= 0) { | |
747 | /* exponent non-negative (and thus not minimum exponent) */ | |
748 | ||
749 | if (lowest_mantissa) { | |
750 | /* (>= e 0) AND (= f (expt b (- p 1))) | |
751 | * | |
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) | |
757 | * m- <- be == b^e | |
758 | * k <- 0 | |
759 | * B <- B | |
760 | * low_ok <- round | |
761 | * high_ok <- round | |
762 | */ | |
763 | ||
764 | DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); " | |
765 | "lowest mantissa value for this exponent -> " | |
766 | "unequal gaps")); | |
767 | ||
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; | |
774 | } else { | |
775 | /* (>= e 0) AND (not (= f (expt b (- p 1)))) | |
776 | * | |
777 | * be <- (expt b e) == b^e | |
778 | * r <- (* f be 2) == 2 * f * b^e [if b==2 -> f * b^(e+1)] | |
779 | * s <- 2 | |
780 | * m+ <- be == b^e | |
781 | * m- <- be == b^e | |
782 | * k <- 0 | |
783 | * B <- B | |
784 | * low_ok <- round | |
785 | * high_ok <- round | |
786 | */ | |
787 | ||
788 | DUK_DDD(DUK_DDDPRINT("non-negative exponent (not smallest exponent); " | |
789 | "not lowest mantissa for this exponent -> " | |
790 | "equal gaps")); | |
791 | ||
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 */ | |
797 | } | |
798 | } else { | |
799 | /* When doing string-to-number, lowest_mantissa is always 0 so | |
800 | * the exponent check, while incorrect, won't matter. | |
801 | */ | |
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)] | |
806 | * m+ <- b == 2 | |
807 | * m- <- 1 | |
808 | * k <- 0 | |
809 | * B <- B | |
810 | * low_ok <- round | |
811 | * high_ok <- round | |
812 | */ | |
813 | ||
814 | DUK_DDD(DUK_DDDPRINT("negative exponent; not minimum exponent and " | |
815 | "lowest mantissa for this exponent -> " | |
816 | "unequal gaps")); | |
817 | ||
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; | |
824 | } else { | |
825 | /* r <- (* f 2) | |
826 | * s <- (* (expt b (- e)) 2) == b^(-e) * 2 [if b==2 -> b^(1-e)] | |
827 | * m+ <- 1 | |
828 | * m- <- 1 | |
829 | * k <- 0 | |
830 | * B <- B | |
831 | * low_ok <- round | |
832 | * high_ok <- round | |
833 | */ | |
834 | ||
835 | DUK_DDD(DUK_DDDPRINT("negative exponent; minimum exponent or not " | |
836 | "lowest mantissa for this exponent -> " | |
837 | "equal gaps")); | |
838 | ||
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); | |
844 | } | |
845 | } | |
846 | } | |
847 | ||
848 | DUK_LOCAL void duk__dragon4_scale(duk__numconv_stringify_ctx *nc_ctx) { | |
849 | duk_small_int_t k = 0; | |
850 | ||
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). | |
855 | * | |
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). | |
860 | * | |
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. | |
864 | */ | |
865 | ||
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. | |
871 | */ | |
872 | ||
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); | |
879 | ||
880 | for (;;) { | |
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); | |
886 | ||
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")); | |
890 | /* r <- r | |
891 | * s <- (* s B) | |
892 | * m+ <- m+ | |
893 | * m- <- m- | |
894 | * k <- (+ k 1) | |
895 | */ | |
896 | ||
897 | duk__bi_mul_small_copy(&nc_ctx->s, nc_ctx->B, &nc_ctx->t1); | |
898 | k++; | |
899 | } else { | |
900 | break; | |
901 | } | |
902 | } | |
903 | ||
904 | /* k > 0 -> k was too low, and cannot be too high */ | |
905 | if (k > 0) { | |
906 | goto skip_dec_k; | |
907 | } | |
908 | ||
909 | for (;;) { | |
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); | |
915 | ||
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")); | |
920 | /* r <- (* r B) | |
921 | * s <- s | |
922 | * m+ <- (* m+ B) | |
923 | * m- <- (* m- B) | |
924 | * k <- (- k 1) | |
925 | */ | |
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); | |
931 | } | |
932 | k--; | |
933 | } else { | |
934 | break; | |
935 | } | |
936 | } | |
937 | ||
938 | skip_dec_k: | |
939 | ||
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 */ | |
943 | } | |
944 | nc_ctx->k = k; | |
945 | ||
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); | |
951 | } | |
952 | ||
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 */ | |
957 | ||
958 | /* | |
959 | * Digit generation loop. | |
960 | * | |
961 | * Different termination conditions: | |
962 | * | |
963 | * 1. Free format output. Terminate when shortest accurate | |
964 | * representation found. | |
965 | * | |
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. | |
969 | * | |
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. | |
974 | */ | |
975 | ||
976 | for (;;) { | |
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); | |
984 | ||
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) */ | |
987 | d = 0; | |
988 | for (;;) { | |
989 | if (duk__bi_compare(&nc_ctx->t1, &nc_ctx->s) < 0) { | |
990 | break; | |
991 | } | |
992 | duk__bi_sub_copy(&nc_ctx->t1, &nc_ctx->s, &nc_ctx->t2); /* t1 <- t1 - s */ | |
993 | d++; | |
994 | } | |
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); | |
999 | ||
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); | |
1004 | ||
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. | |
1009 | */ | |
1010 | ||
1011 | if (nc_ctx->is_fixed == 0) { | |
1012 | /* free-form */ | |
1013 | tc1 = (duk__bi_compare(&nc_ctx->r, &nc_ctx->mm) <= (nc_ctx->low_ok ? 0 : -1)); | |
1014 | ||
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)); | |
1017 | ||
1018 | DUK_DDD(DUK_DDDPRINT("tc1=%ld, tc2=%ld", (long) tc1, (long) tc2)); | |
1019 | } else { | |
1020 | /* fixed-format */ | |
1021 | tc1 = 0; | |
1022 | tc2 = 0; | |
1023 | } | |
1024 | ||
1025 | /* Count is incremented before DUK__DRAGON4_OUTPUT_PREINC() call | |
1026 | * on purpose, which is taken into account by the macro. | |
1027 | */ | |
1028 | count++; | |
1029 | ||
1030 | if (tc1) { | |
1031 | if (tc2) { | |
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); | |
1038 | } else { | |
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); | |
1042 | } | |
1043 | break; | |
1044 | } else { | |
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); | |
1049 | break; | |
1050 | } | |
1051 | } else { | |
1052 | if (tc2) { | |
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); | |
1057 | break; | |
1058 | } else { | |
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); | |
1063 | ||
1064 | /* r <- r (updated above: r <- (remainder (* r B) s) | |
1065 | * s <- 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 | |
1069 | */ | |
1070 | ||
1071 | /* fall through and continue for-loop */ | |
1072 | } | |
1073 | } | |
1074 | ||
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")); | |
1083 | break; | |
1084 | } | |
1085 | } else { | |
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")); | |
1090 | break; | |
1091 | } | |
1092 | } | |
1093 | } | |
1094 | } /* for */ | |
1095 | ||
1096 | nc_ctx->count = count; | |
1097 | ||
1098 | DUK_DDD(DUK_DDDPRINT("generate finished")); | |
1099 | ||
1100 | #ifdef DUK_USE_DDDPRINT | |
1101 | { | |
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) '?'; | |
1109 | } else { | |
1110 | buf[i] = (duk_uint8_t) DUK__DIGITCHAR(t); | |
1111 | } | |
1112 | } | |
1113 | DUK_DDD(DUK_DDDPRINT("-> generated digits; k=%ld, digits='%s'", | |
1114 | (long) nc_ctx->k, (const char *) buf)); | |
1115 | } | |
1116 | #endif | |
1117 | } | |
1118 | ||
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. | |
1123 | * | |
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). | |
1127 | */ | |
1128 | DUK_LOCAL duk_small_int_t duk__dragon4_fixed_format_round(duk__numconv_stringify_ctx *nc_ctx, duk_small_int_t round_idx) { | |
1129 | duk_small_int_t t; | |
1130 | duk_uint8_t *p; | |
1131 | duk_uint8_t roundup_limit; | |
1132 | duk_small_int_t ret = 0; | |
1133 | ||
1134 | /* | |
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. | |
1139 | */ | |
1140 | ||
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)); | |
1144 | return 0; | |
1145 | } else if (round_idx < 0) { | |
1146 | DUK_DDD(DUK_DDDPRINT("round_idx out of bounds (%ld < 0) -> no rounding", | |
1147 | (long) round_idx)); | |
1148 | return 0; | |
1149 | } | |
1150 | ||
1151 | /* | |
1152 | * Round-up limit. | |
1153 | * | |
1154 | * For even values, divides evenly, e.g. 10 -> roundup_limit=5. | |
1155 | * | |
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. | |
1158 | */ | |
1159 | roundup_limit = (duk_uint8_t) ((nc_ctx->B + 1) / 2); | |
1160 | ||
1161 | p = &nc_ctx->digits[round_idx]; | |
1162 | if (*p >= roundup_limit) { | |
1163 | DUK_DDD(DUK_DDDPRINT("fixed-format rounding carry required")); | |
1164 | /* carry */ | |
1165 | for (;;) { | |
1166 | *p = 0; | |
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 | (const 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 */ | |
1175 | ret = 1; | |
1176 | break; | |
1177 | } | |
1178 | ||
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)); | |
1181 | p--; | |
1182 | t = *p; | |
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")); | |
1186 | *p = (duk_uint8_t) t; | |
1187 | break; | |
1188 | } | |
1189 | ||
1190 | DUK_DDD(DUK_DDDPRINT("wraps, carry to next digit")); | |
1191 | } | |
1192 | } | |
1193 | ||
1194 | return ret; | |
1195 | } | |
1196 | ||
1197 | #define DUK__NO_EXP (65536) /* arbitrary marker, outside valid exp range */ | |
1198 | ||
1199 | DUK_LOCAL void duk__dragon4_convert_and_push(duk__numconv_stringify_ctx *nc_ctx, | |
1200 | duk_context *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) { | |
1205 | duk_small_int_t k; | |
1206 | duk_small_int_t pos, pos_end; | |
1207 | duk_small_int_t expt; | |
1208 | duk_small_int_t dig; | |
1209 | duk_uint8_t *q; | |
1210 | duk_uint8_t *buf; | |
1211 | ||
1212 | /* | |
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: | |
1217 | * | |
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 | |
1222 | * | |
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. | |
1227 | * | |
1228 | * Ecmascript doesn't specify any specific behavior for format selection | |
1229 | * (e.g. when to use exponent notation) for non-base-10 numbers. | |
1230 | * | |
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. | |
1234 | */ | |
1235 | ||
1236 | DUK_ASSERT(DUK__NUMCONV_CTX_BIGINTS_SIZE >= DUK__MAX_FORMATTED_LENGTH); | |
1237 | DUK_ASSERT(nc_ctx->count >= 1); | |
1238 | ||
1239 | k = nc_ctx->k; | |
1240 | buf = (duk_uint8_t *) &nc_ctx->f; /* XXX: union would be more correct */ | |
1241 | q = buf; | |
1242 | ||
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"). | |
1245 | * | |
1246 | * toFixed() prevents exponent use; otherwise apply a set of criteria to | |
1247 | * match the other API calls (toString(), toPrecision, etc). | |
1248 | */ | |
1249 | ||
1250 | expt = DUK__NO_EXP; | |
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 */ | |
1260 | } | |
1261 | } | |
1262 | ||
1263 | if (neg) { | |
1264 | *q++ = '-'; | |
1265 | } | |
1266 | ||
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) { | |
1271 | /* toFixed() */ | |
1272 | pos_end = -digits; | |
1273 | } else { | |
1274 | pos_end = k - digits; | |
1275 | } | |
1276 | } else { | |
1277 | pos_end = k - nc_ctx->count; | |
1278 | } | |
1279 | if (pos_end > 0) { | |
1280 | pos_end = 0; | |
1281 | } | |
1282 | ||
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)); | |
1287 | ||
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)); | |
1292 | if (pos == 0) { | |
1293 | *q++ = (duk_uint8_t) '.'; | |
1294 | } | |
1295 | if (pos > k) { | |
1296 | *q++ = (duk_uint8_t) '0'; | |
1297 | } else if (pos <= k - nc_ctx->count) { | |
1298 | *q++ = (duk_uint8_t) '0'; | |
1299 | } else { | |
1300 | dig = nc_ctx->digits[k - pos]; | |
1301 | DUK_ASSERT(dig >= 0 && dig < nc_ctx->B); | |
1302 | *q++ = (duk_uint8_t) DUK__DIGITCHAR(dig); | |
1303 | } | |
1304 | ||
1305 | pos--; | |
1306 | } | |
1307 | DUK_ASSERT(pos <= 1); | |
1308 | ||
1309 | /* Exponent */ | |
1310 | if (expt != DUK__NO_EXP) { | |
1311 | /* | |
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. | |
1316 | * | |
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". | |
1323 | */ | |
1324 | ||
1325 | duk_size_t len; | |
1326 | char expt_sign; | |
1327 | ||
1328 | *q++ = 'e'; | |
1329 | if (expt >= 0) { | |
1330 | expt_sign = '+'; | |
1331 | } else { | |
1332 | expt_sign = '-'; | |
1333 | expt = -expt; | |
1334 | } | |
1335 | *q++ = (duk_uint8_t) expt_sign; | |
1336 | len = duk__dragon4_format_uint32(q, (duk_uint32_t) expt, radix); | |
1337 | q += len; | |
1338 | } | |
1339 | ||
1340 | duk_push_lstring(ctx, (const char *) buf, (size_t) (q - buf)); | |
1341 | } | |
1342 | ||
1343 | /* | |
1344 | * Conversion helpers | |
1345 | */ | |
1346 | ||
1347 | DUK_LOCAL void duk__dragon4_double_to_ctx(duk__numconv_stringify_ctx *nc_ctx, duk_double_t x) { | |
1348 | duk_double_union u; | |
1349 | duk_uint32_t tmp; | |
1350 | duk_small_int_t expt; | |
1351 | ||
1352 | /* | |
1353 | * seeeeeee eeeeffff ffffffff ffffffff ffffffff ffffffff ffffffff ffffffff | |
1354 | * A B C D E F G H | |
1355 | * | |
1356 | * s sign bit | |
1357 | * eee... exponent field | |
1358 | * fff... fraction | |
1359 | * | |
1360 | * ieee value = 1.ffff... * 2^(e - 1023) (normal) | |
1361 | * = 0.ffff... * 2^(-1022) (denormal) | |
1362 | * | |
1363 | * algorithm v = f * b^e | |
1364 | */ | |
1365 | ||
1366 | DUK_DBLUNION_SET_DOUBLE(&u, x); | |
1367 | ||
1368 | nc_ctx->f.n = 2; | |
1369 | ||
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); | |
1375 | ||
1376 | if (expt == 0) { | |
1377 | /* denormal */ | |
1378 | expt = DUK__IEEE_DOUBLE_EXP_MIN - 52; | |
1379 | duk__bi_normalize(&nc_ctx->f); | |
1380 | } else { | |
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 */ | |
1385 | } | |
1386 | ||
1387 | DUK_ASSERT(duk__bi_is_valid(&nc_ctx->f)); | |
1388 | ||
1389 | nc_ctx->e = expt; | |
1390 | } | |
1391 | ||
1392 | DUK_LOCAL void duk__dragon4_ctx_to_double(duk__numconv_stringify_ctx *nc_ctx, duk_double_t *x) { | |
1393 | duk_double_union u; | |
1394 | duk_small_int_t expt; | |
1395 | duk_small_int_t i; | |
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; | |
1400 | duk_uint32_t t, v; | |
1401 | ||
1402 | DUK_ASSERT(nc_ctx->count == 53 + 1); | |
1403 | ||
1404 | /* Sometimes this assert is not true right now; it will be true after | |
1405 | * rounding. See: test-bug-numconv-mantissa-assert.js. | |
1406 | */ | |
1407 | DUK_ASSERT_DISABLE(nc_ctx->digits[0] == 1); /* zero handled by caller */ | |
1408 | ||
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. | |
1413 | */ | |
1414 | DUK_MEMZERO((void *) &u, sizeof(u)); | |
1415 | ||
1416 | /* | |
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 | |
1420 | * infinity). | |
1421 | * | |
1422 | * For normal numbers the leading '1' is hidden and ignored, | |
1423 | * and the last bit is used for rounding: | |
1424 | * | |
1425 | * rounding pt | |
1426 | * <--------52------->| | |
1427 | * 1 x x x x ... x x x x|y ==> x x x x ... x x x x | |
1428 | * | |
1429 | * For denormals, the leading '1' is included in the number, | |
1430 | * and the rounding point is different: | |
1431 | * | |
1432 | * rounding pt | |
1433 | * <--52 or less--->| | |
1434 | * 1 x x x x ... x x|x x y ==> 0 0 ... 1 x x ... x x | |
1435 | * | |
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. | |
1439 | * | |
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. | |
1443 | * | |
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. | |
1448 | */ | |
1449 | ||
1450 | skip_round = 0; | |
1451 | ||
1452 | recheck_exp: | |
1453 | ||
1454 | expt = nc_ctx->k - 1; /* IEEE exp without bias */ | |
1455 | if (expt > 1023) { | |
1456 | /* Infinity */ | |
1457 | bitstart = -255; /* needed for inf: causes mantissa to become zero, | |
1458 | * and rounding to be skipped. | |
1459 | */ | |
1460 | expt = 2047; | |
1461 | } else if (expt >= -1022) { | |
1462 | /* normal */ | |
1463 | bitstart = 1; /* skip leading digit */ | |
1464 | expt += DUK__IEEE_DOUBLE_EXP_BIAS; | |
1465 | DUK_ASSERT(expt >= 1 && expt <= 2046); | |
1466 | } else { | |
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 | |
1470 | */ | |
1471 | expt = 0; | |
1472 | } | |
1473 | bitround = bitstart + 52; | |
1474 | ||
1475 | DUK_DDD(DUK_DDDPRINT("ieee expt=%ld, bitstart=%ld, bitround=%ld", | |
1476 | (long) expt, (long) bitstart, (long) bitround)); | |
1477 | ||
1478 | if (!skip_round) { | |
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). | |
1483 | */ | |
1484 | DUK_DDD(DUK_DDDPRINT("rounding caused exponent to be bumped, recheck exponent")); | |
1485 | skip_round = 1; | |
1486 | goto recheck_exp; | |
1487 | } | |
1488 | } | |
1489 | ||
1490 | /* | |
1491 | * Create mantissa | |
1492 | */ | |
1493 | ||
1494 | t = 0; | |
1495 | for (i = 0; i < 52; i++) { | |
1496 | bitidx = bitstart + 52 - 1 - i; | |
1497 | if (bitidx >= nc_ctx->count) { | |
1498 | v = 0; | |
1499 | } else if (bitidx < 0) { | |
1500 | v = 0; | |
1501 | } else { | |
1502 | v = nc_ctx->digits[bitidx]; | |
1503 | } | |
1504 | DUK_ASSERT(v == 0 || v == 1); | |
1505 | t += v << (i % 32); | |
1506 | if (i == 31) { | |
1507 | /* low 32 bits is complete */ | |
1508 | DUK_DBLUNION_SET_LOW32(&u, t); | |
1509 | t = 0; | |
1510 | } | |
1511 | } | |
1512 | /* t has high mantissa */ | |
1513 | ||
1514 | DUK_DDD(DUK_DDDPRINT("mantissa is complete: %08lx %08lx", | |
1515 | (unsigned long) t, | |
1516 | (unsigned long) DUK_DBLUNION_GET_LOW32(&u))); | |
1517 | ||
1518 | DUK_ASSERT(expt >= 0 && expt <= 0x7ffL); | |
1519 | t += expt << 20; | |
1520 | #if 0 /* caller handles sign change */ | |
1521 | if (negative) { | |
1522 | t |= 0x80000000U; | |
1523 | } | |
1524 | #endif | |
1525 | DUK_DBLUNION_SET_HIGH32(&u, t); | |
1526 | ||
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))); | |
1530 | ||
1531 | *x = DUK_DBLUNION_GET_DOUBLE(&u); | |
1532 | } | |
1533 | ||
1534 | /* | |
1535 | * Exposed number-to-string API | |
1536 | * | |
1537 | * Input: [ number ] | |
1538 | * Output: [ string ] | |
1539 | */ | |
1540 | ||
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) { | |
1542 | duk_double_t x; | |
1543 | duk_small_int_t c; | |
1544 | duk_small_int_t neg; | |
1545 | duk_uint32_t uval; | |
1546 | duk__numconv_stringify_ctx nc_ctx_alloc; /* large context; around 2kB now */ | |
1547 | duk__numconv_stringify_ctx *nc_ctx = &nc_ctx_alloc; | |
1548 | ||
1549 | x = (duk_double_t) duk_require_number(ctx, -1); | |
1550 | duk_pop(ctx); | |
1551 | ||
1552 | /* | |
1553 | * Handle special cases (NaN, infinity, zero). | |
1554 | */ | |
1555 | ||
1556 | c = (duk_small_int_t) DUK_FPCLASSIFY(x); | |
1557 | if (DUK_SIGNBIT((double) x)) { | |
1558 | x = -x; | |
1559 | neg = 1; | |
1560 | } else { | |
1561 | neg = 0; | |
1562 | } | |
1563 | ||
1564 | /* NaN sign bit is platform specific with unpacked, un-normalized NaNs */ | |
1565 | DUK_ASSERT(c == DUK_FP_NAN || DUK_SIGNBIT((double) x) == 0); | |
1566 | ||
1567 | if (c == DUK_FP_NAN) { | |
1568 | duk_push_hstring_stridx(ctx, DUK_STRIDX_NAN); | |
1569 | return; | |
1570 | } else if (c == DUK_FP_INFINITE) { | |
1571 | if (neg) { | |
1572 | /* -Infinity */ | |
1573 | duk_push_hstring_stridx(ctx, DUK_STRIDX_MINUS_INFINITY); | |
1574 | } else { | |
1575 | /* Infinity */ | |
1576 | duk_push_hstring_stridx(ctx, DUK_STRIDX_INFINITY); | |
1577 | } | |
1578 | return; | |
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). | |
1582 | */ | |
1583 | ; | |
1584 | } | |
1585 | ||
1586 | /* | |
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) | |
1591 | * is in force. | |
1592 | * | |
1593 | * XXX: could save space by supporting radix 10 only and using | |
1594 | * sprintf "%lu" for the fast path and for exponent formatting. | |
1595 | */ | |
1596 | ||
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; | |
1603 | ||
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) '-'; | |
1608 | } | |
1609 | p += duk__dragon4_format_uint32(p, uval, radix); | |
1610 | duk_push_lstring(ctx, (const char *) buf, (duk_size_t) (p - buf)); | |
1611 | return; | |
1612 | } | |
1613 | ||
1614 | /* | |
1615 | * Dragon4 setup. | |
1616 | * | |
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"). | |
1623 | */ | |
1624 | ||
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. | |
1627 | */ | |
1628 | #if 0 | |
1629 | DUK_MEMZERO((void *) nc_ctx, sizeof(*nc_ctx)); /* slow init, do only for slow path cases */ | |
1630 | #endif | |
1631 | ||
1632 | nc_ctx->is_s2n = 0; | |
1633 | nc_ctx->b = 2; | |
1634 | nc_ctx->B = radix; | |
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. | |
1641 | */ | |
1642 | nc_ctx->abs_pos = 1; | |
1643 | nc_ctx->req_digits = (-digits + 1) - 1; | |
1644 | } else { | |
1645 | nc_ctx->req_digits = digits + 1; | |
1646 | } | |
1647 | } else { | |
1648 | nc_ctx->is_fixed = 0; | |
1649 | nc_ctx->req_digits = 0; | |
1650 | } | |
1651 | ||
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. | |
1656 | */ | |
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 */ | |
1661 | } else { | |
1662 | count = digits + 1; /* + 1 for rounding */ | |
1663 | } | |
1664 | } else { | |
1665 | count = 1; | |
1666 | } | |
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... */ | |
1672 | neg = 0; | |
1673 | goto zero_skip; | |
1674 | } | |
1675 | ||
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)); | |
1679 | ||
1680 | /* | |
1681 | * Dragon4 slow path digit generation. | |
1682 | */ | |
1683 | ||
1684 | duk__dragon4_prepare(nc_ctx); /* setup many variables in nc_ctx */ | |
1685 | ||
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); | |
1691 | ||
1692 | duk__dragon4_scale(nc_ctx); | |
1693 | ||
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); | |
1699 | ||
1700 | duk__dragon4_generate(nc_ctx); | |
1701 | ||
1702 | /* | |
1703 | * Convert and push final string. | |
1704 | */ | |
1705 | ||
1706 | zero_skip: | |
1707 | ||
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). | |
1714 | */ | |
1715 | roundpos = -digits; /* absolute position for digit considered for rounding */ | |
1716 | roundpos = nc_ctx->k - roundpos; | |
1717 | } else { | |
1718 | roundpos = digits; | |
1719 | } | |
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); | |
1723 | ||
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. | |
1728 | */ | |
1729 | } | |
1730 | ||
1731 | duk__dragon4_convert_and_push(nc_ctx, ctx, radix, digits, flags, neg); | |
1732 | } | |
1733 | ||
1734 | /* | |
1735 | * Exposed string-to-number API | |
1736 | * | |
1737 | * Input: [ string ] | |
1738 | * Output: [ number ] | |
1739 | * | |
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. | |
1742 | */ | |
1743 | ||
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; | |
1748 | duk_double_t res; | |
1749 | duk_hstring *h_str; | |
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; | |
1762 | duk_small_int_t ch; | |
1763 | ||
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. | |
1767 | */ | |
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); | |
1781 | ||
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)); | |
1785 | ||
1786 | DUK_ASSERT(radix >= 2 && radix <= 36); | |
1787 | DUK_ASSERT(radix - 2 < (duk_small_int_t) sizeof(duk__str2num_digits_for_radix)); | |
1788 | ||
1789 | /* | |
1790 | * Preliminaries: trim, sign, Infinity check | |
1791 | * | |
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. | |
1795 | * | |
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()). | |
1800 | * | |
1801 | * Automatic hex number detection (leading '0x' or '0X') and octal | |
1802 | * number detection (leading '0' followed by at least one octal digit) | |
1803 | * is done here too. | |
1804 | */ | |
1805 | ||
1806 | if (trim_white) { | |
1807 | /* Leading / trailing whitespace is sometimes accepted and | |
1808 | * sometimes not. After white space trimming, all valid input | |
1809 | * characters are pure ASCII. | |
1810 | */ | |
1811 | duk_trim(ctx, -1); | |
1812 | } | |
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); | |
1816 | ||
1817 | neg = 0; | |
1818 | ch = *p; | |
1819 | if (ch == (duk_small_int_t) '+') { | |
1820 | if (!allow_plus) { | |
1821 | DUK_DDD(DUK_DDDPRINT("parse failed: leading plus sign not allowed")); | |
1822 | goto parse_fail; | |
1823 | } | |
1824 | p++; | |
1825 | } else if (ch == (duk_small_int_t) '-') { | |
1826 | if (!allow_minus) { | |
1827 | DUK_DDD(DUK_DDDPRINT("parse failed: leading minus sign not allowed")); | |
1828 | goto parse_fail; | |
1829 | } | |
1830 | p++; | |
1831 | neg = 1; | |
1832 | } | |
1833 | ||
1834 | ch = *p; | |
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: | |
1838 | * | |
1839 | * parseInt('Infinity', 36) | |
1840 | * 1461559270678 | |
1841 | */ | |
1842 | ||
1843 | const duk_uint8_t *q; | |
1844 | ||
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")); | |
1850 | goto parse_fail; | |
1851 | } else { | |
1852 | res = DUK_DOUBLE_INFINITY; | |
1853 | goto negcheck_and_ret; | |
1854 | } | |
1855 | } | |
1856 | } | |
1857 | if (ch == (duk_small_int_t) '0') { | |
1858 | duk_small_int_t detect_radix = 0; | |
1859 | ch = p[1]; | |
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")); | |
1862 | detect_radix = 16; | |
1863 | allow_empty = 0; /* interpret e.g. '0x' and '0xg' as a NaN (= parse error) */ | |
1864 | p += 2; | |
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")); | |
1867 | detect_radix = 8; | |
1868 | allow_empty = 1; /* interpret e.g. '09' as '0', not NaN */ | |
1869 | p += 1; | |
1870 | } | |
1871 | if (detect_radix > 0) { | |
1872 | radix = detect_radix; | |
1873 | allow_expt = 0; | |
1874 | allow_frac = 0; | |
1875 | allow_naked_frac = 0; | |
1876 | allow_empty_frac = 0; | |
1877 | allow_leading_zero = 1; /* allow e.g. '0x0009' and '00077' */ | |
1878 | } | |
1879 | } | |
1880 | ||
1881 | /* | |
1882 | * Scan number and setup for Dragon4. | |
1883 | * | |
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. | |
1889 | * | |
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 | |
1898 | * accuracy. | |
1899 | * | |
1900 | * Digit counts: | |
1901 | * | |
1902 | * [ dig_lzero ] | |
1903 | * | | |
1904 | * .+-..---[ dig_prec ]----. | |
1905 | * | || | | |
1906 | * 0000123.456789012345678901234567890e+123456 | |
1907 | * | | | | | | | |
1908 | * `--+--' `------[ dig_frac ]-------' `-+--' | |
1909 | * | | | |
1910 | * [ dig_whole ] [ dig_expt ] | |
1911 | * | |
1912 | * dig_frac and dig_expt are -1 if not present | |
1913 | * dig_lzero is only computed for whole number part | |
1914 | * | |
1915 | * Parsing state | |
1916 | * | |
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) | |
1920 | * | |
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. | |
1925 | */ | |
1926 | ||
1927 | duk__bi_set_small(&nc_ctx->f, 0); | |
1928 | dig_prec = 0; | |
1929 | dig_lzero = 0; | |
1930 | dig_whole = 0; | |
1931 | dig_frac = -1; | |
1932 | dig_expt = -1; | |
1933 | expt = 0; | |
1934 | expt_adj = 0; /* essentially tracks digit position of lowest 'f' digit */ | |
1935 | expt_neg = 0; | |
1936 | for (;;) { | |
1937 | ch = *p++; | |
1938 | ||
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 | (const 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); | |
1945 | ||
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. | |
1953 | */ | |
1954 | if (dig_frac >= 0 || dig_expt >= 0) { | |
1955 | if (allow_garbage) { | |
1956 | DUK_DDD(DUK_DDDPRINT("garbage termination (invalid period)")); | |
1957 | break; | |
1958 | } else { | |
1959 | DUK_DDD(DUK_DDDPRINT("parse failed: period not allowed")); | |
1960 | goto parse_fail; | |
1961 | } | |
1962 | } | |
1963 | ||
1964 | if (!allow_frac) { | |
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. | |
1967 | */ | |
1968 | if (allow_garbage) { | |
1969 | DUK_DDD(DUK_DDDPRINT("garbage termination (invalid first period)")); | |
1970 | break; | |
1971 | } else { | |
1972 | DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed")); | |
1973 | } | |
1974 | } | |
1975 | ||
1976 | DUK_DDD(DUK_DDDPRINT("start fraction part")); | |
1977 | dig_frac = 0; | |
1978 | continue; | |
1979 | } else if (ch == (duk_small_int_t) 0) { | |
1980 | DUK_DDD(DUK_DDDPRINT("NUL termination")); | |
1981 | break; | |
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). | |
1987 | * | |
1988 | * If the exponent separator occurs twice, 'e' will be interpreted | |
1989 | * as a digit (= 14) and will be rejected as an invalid decimal | |
1990 | * digit. | |
1991 | */ | |
1992 | ||
1993 | DUK_DDD(DUK_DDDPRINT("start exponent part")); | |
1994 | ||
1995 | /* Exponent without a sign or with a +/- sign is accepted | |
1996 | * by all call sites (even JSON.parse()). | |
1997 | */ | |
1998 | ch = *p; | |
1999 | if (ch == (duk_small_int_t) '-') { | |
2000 | expt_neg = 1; | |
2001 | p++; | |
2002 | } else if (ch == (duk_small_int_t) '+') { | |
2003 | p++; | |
2004 | } | |
2005 | dig_expt = 0; | |
2006 | continue; | |
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); | |
2011 | } else { | |
2012 | dig = 255; /* triggers garbage digit check below */ | |
2013 | } | |
2014 | DUK_ASSERT((dig >= 0 && dig <= 35) || dig == 255); | |
2015 | ||
2016 | if (dig >= radix) { | |
2017 | if (allow_garbage) { | |
2018 | DUK_DDD(DUK_DDDPRINT("garbage termination")); | |
2019 | break; | |
2020 | } else { | |
2021 | DUK_DDD(DUK_DDDPRINT("parse failed: trailing garbage or invalid digit")); | |
2022 | goto parse_fail; | |
2023 | } | |
2024 | } | |
2025 | ||
2026 | if (dig_expt < 0) { | |
2027 | /* whole or fraction digit */ | |
2028 | ||
2029 | if (dig_prec < duk__str2num_digits_for_radix[radix - 2]) { | |
2030 | /* significant from precision perspective */ | |
2031 | ||
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. | |
2036 | */ | |
2037 | if (dig_frac < 0) { | |
2038 | dig_lzero++; | |
2039 | } | |
2040 | } else { | |
2041 | /* XXX: join these ops (multiply-accumulate), but only if | |
2042 | * code footprint decreases. | |
2043 | */ | |
2044 | duk__bi_mul_small(&nc_ctx->t1, &nc_ctx->f, radix); | |
2045 | duk__bi_add_small(&nc_ctx->f, &nc_ctx->t1, dig); | |
2046 | dig_prec++; | |
2047 | } | |
2048 | } else { | |
2049 | /* Ignore digits beyond a radix-specific limit, but note them | |
2050 | * in expt_adj. | |
2051 | */ | |
2052 | expt_adj++; | |
2053 | } | |
2054 | ||
2055 | if (dig_frac >= 0) { | |
2056 | dig_frac++; | |
2057 | expt_adj--; | |
2058 | } else { | |
2059 | dig_whole++; | |
2060 | } | |
2061 | } else { | |
2062 | /* exponent digit */ | |
2063 | ||
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. | |
2068 | */ | |
2069 | DUK_DDD(DUK_DDDPRINT("parse failed: exponent too large")); | |
2070 | goto parse_explimit_error; | |
2071 | } | |
2072 | dig_expt++; | |
2073 | } | |
2074 | } | |
2075 | ||
2076 | /* Leading zero. */ | |
2077 | ||
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")); | |
2081 | goto parse_fail; | |
2082 | } | |
2083 | } | |
2084 | ||
2085 | /* Validity checks for various fraction formats ("0.1", ".1", "1.", "."). */ | |
2086 | ||
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")); | |
2091 | goto parse_fail; | |
2092 | } else if (dig_frac > 0) { | |
2093 | /* ".123" */ | |
2094 | if (!allow_naked_frac) { | |
2095 | DUK_DDD(DUK_DDDPRINT("parse failed: fraction part not allowed without " | |
2096 | "leading integer digit(s)")); | |
2097 | goto parse_fail; | |
2098 | } | |
2099 | } else { | |
2100 | /* empty ("") is allowed in some formats (e.g. Number(''), as zero */ | |
2101 | if (!allow_empty) { | |
2102 | DUK_DDD(DUK_DDDPRINT("parse failed: empty string not allowed (as zero)")); | |
2103 | goto parse_fail; | |
2104 | } | |
2105 | } | |
2106 | } else { | |
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")); | |
2111 | goto parse_fail; | |
2112 | } | |
2113 | } else if (dig_frac > 0) { | |
2114 | /* "123.456" */ | |
2115 | ; | |
2116 | } else { | |
2117 | /* "123" */ | |
2118 | ; | |
2119 | } | |
2120 | } | |
2121 | ||
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). | |
2124 | */ | |
2125 | ||
2126 | if (dig_expt == 0) { | |
2127 | if (!allow_garbage) { | |
2128 | DUK_DDD(DUK_DDDPRINT("parse failed: empty exponent")); | |
2129 | goto parse_fail; | |
2130 | } | |
2131 | DUK_ASSERT(expt == 0); | |
2132 | } | |
2133 | ||
2134 | if (expt_neg) { | |
2135 | expt = -expt; | |
2136 | } | |
2137 | DUK_DDD(DUK_DDDPRINT("expt=%ld, expt_adj=%ld, net exponent -> %ld", | |
2138 | (long) expt, (long) expt_adj, (long) (expt + expt_adj))); | |
2139 | expt += expt_adj; | |
2140 | ||
2141 | /* Fast path check. */ | |
2142 | ||
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 | |
2147 | * zero sign. | |
2148 | */ | |
2149 | ||
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]; | |
2154 | } else { | |
2155 | res = 0.0; | |
2156 | } | |
2157 | goto negcheck_and_ret; | |
2158 | } | |
2159 | ||
2160 | /* Significand ('f') padding. */ | |
2161 | ||
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. | |
2165 | */ | |
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); | |
2169 | expt--; | |
2170 | dig_prec++; | |
2171 | } | |
2172 | ||
2173 | DUK_DDD(DUK_DDDPRINT("final exponent: %ld", (long) expt)); | |
2174 | ||
2175 | /* Detect zero special case. */ | |
2176 | ||
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. | |
2180 | */ | |
2181 | DUK_DDD(DUK_DDDPRINT("significand is zero")); | |
2182 | res = 0.0; | |
2183 | goto negcheck_and_ret; | |
2184 | } | |
2185 | ||
2186 | ||
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. | |
2190 | */ | |
2191 | ||
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; | |
2201 | } | |
2202 | ||
2203 | nc_ctx->is_s2n = 1; | |
2204 | nc_ctx->e = expt; | |
2205 | nc_ctx->b = radix; | |
2206 | nc_ctx->B = 2; | |
2207 | nc_ctx->is_fixed = 1; | |
2208 | nc_ctx->abs_pos = 0; | |
2209 | nc_ctx->req_digits = 53 + 1; | |
2210 | ||
2211 | DUK__BI_PRINT("f", &nc_ctx->f); | |
2212 | DUK_DDD(DUK_DDDPRINT("e=%ld", (long) nc_ctx->e)); | |
2213 | ||
2214 | /* | |
2215 | * Dragon4 slow path (binary) digit generation. | |
2216 | * An extra digit is generated for rounding. | |
2217 | */ | |
2218 | ||
2219 | duk__dragon4_prepare(nc_ctx); /* setup many variables in nc_ctx */ | |
2220 | ||
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); | |
2226 | ||
2227 | duk__dragon4_scale(nc_ctx); | |
2228 | ||
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); | |
2234 | ||
2235 | duk__dragon4_generate(nc_ctx); | |
2236 | ||
2237 | DUK_ASSERT(nc_ctx->count == 53 + 1); | |
2238 | ||
2239 | /* | |
2240 | * Convert binary digits into an IEEE double. Need to handle | |
2241 | * denormals and rounding correctly. | |
2242 | */ | |
2243 | ||
2244 | duk__dragon4_ctx_to_double(nc_ctx, &res); | |
2245 | goto negcheck_and_ret; | |
2246 | ||
2247 | negcheck_and_ret: | |
2248 | if (neg) { | |
2249 | res = -res; | |
2250 | } | |
2251 | duk_pop(ctx); | |
2252 | duk_push_number(ctx, (double) res); | |
2253 | DUK_DDD(DUK_DDDPRINT("result: %!T", (duk_tval *) duk_get_tval(ctx, -1))); | |
2254 | return; | |
2255 | ||
2256 | parse_fail: | |
2257 | DUK_DDD(DUK_DDDPRINT("parse failed")); | |
2258 | duk_pop(ctx); | |
2259 | duk_push_nan(ctx); | |
2260 | return; | |
2261 | ||
2262 | parse_explimit_error: | |
2263 | DUK_DDD(DUK_DDDPRINT("parse failed, internal error, can't return a value")); | |
2264 | DUK_ERROR_RANGE(thr, "exponent too large"); | |
2265 | return; | |
2266 | } |