1/*
2** String scanning.
3** Copyright (C) 2005-2021 Mike Pall. See Copyright Notice in luajit.h
4*/
5
6#include <math.h>
7
8#define lj_strscan_c
9#define LUA_CORE
10
11#include "lj_obj.h"
12#include "lj_char.h"
13#include "lj_strscan.h"
14
15/* -- Scanning numbers ---------------------------------------------------- */
16
17/*
18** Rationale for the builtin string to number conversion library:
19**
20** It removes a dependency on libc's strtod(), which is a true portability
21** nightmare. Mainly due to the plethora of supported OS and toolchain
22** combinations. Sadly, the various implementations
23** a) are often buggy, incomplete (no hex floats) and/or imprecise,
24** b) sometimes crash or hang on certain inputs,
25** c) return non-standard NaNs that need to be filtered out, and
26** d) fail if the locale-specific decimal separator is not a dot,
27** which can only be fixed with atrocious workarounds.
28**
29** Also, most of the strtod() implementations are hopelessly bloated,
30** which is not just an I-cache hog, but a problem for static linkage
31** on embedded systems, too.
32**
33** OTOH the builtin conversion function is very compact. Even though it
34** does a lot more, like parsing long longs, octal or imaginary numbers
35** and returning the result in different formats:
36** a) It needs less than 3 KB (!) of machine code (on x64 with -Os),
37** b) it doesn't perform any dynamic allocation and,
38** c) it needs only around 600 bytes of stack space.
39**
40** The builtin function is faster than strtod() for typical inputs, e.g.
41** "123", "1.5" or "1e6". Arguably, it's slower for very large exponents,
42** which are not very common (this could be fixed, if needed).
43**
44** And most importantly, the builtin function is equally precise on all
45** platforms. It correctly converts and rounds any input to a double.
46** If this is not the case, please send a bug report -- but PLEASE verify
47** that the implementation you're comparing to is not the culprit!
48**
49** The implementation quickly pre-scans the entire string first and
50** handles simple integers on-the-fly. Otherwise, it dispatches to the
51** base-specific parser. Hex and octal is straightforward.
52**
53** Decimal to binary conversion uses a fixed-length circular buffer in
54** base 100. Some simple cases are handled directly. For other cases, the
55** number in the buffer is up-scaled or down-scaled until the integer part
56** is in the proper range. Then the integer part is rounded and converted
57** to a double which is finally rescaled to the result. Denormals need
58** special treatment to prevent incorrect 'double rounding'.
59*/
60
61/* Definitions for circular decimal digit buffer (base 100 = 2 digits/byte). */
62#define STRSCAN_DIG 1024
63#define STRSCAN_MAXDIG 800 /* 772 + extra are sufficient. */
64#define STRSCAN_DDIG (STRSCAN_DIG/2)
65#define STRSCAN_DMASK (STRSCAN_DDIG-1)
66
67/* Helpers for circular buffer. */
68#define DNEXT(a) (((a)+1) & STRSCAN_DMASK)
69#define DPREV(a) (((a)-1) & STRSCAN_DMASK)
70#define DLEN(lo, hi) ((int32_t)(((lo)-(hi)) & STRSCAN_DMASK))
71
72#define casecmp(c, k) (((c) | 0x20) == k)
73
74/* Final conversion to double. */
75static void strscan_double(uint64_t x, TValue *o, int32_t ex2, int32_t neg)
76{
77 double n;
78
79 /* Avoid double rounding for denormals. */
80 if (LJ_UNLIKELY(ex2 <= -1075 && x != 0)) {
81 /* NYI: all of this generates way too much code on 32 bit CPUs. */
82#if (defined(__GNUC__) || defined(__clang__)) && LJ_64
83 int32_t b = (int32_t)(__builtin_clzll(x)^63);
84#else
85 int32_t b = (x>>32) ? 32+(int32_t)lj_fls((uint32_t)(x>>32)) :
86 (int32_t)lj_fls((uint32_t)x);
87#endif
88 if ((int32_t)b + ex2 <= -1023 && (int32_t)b + ex2 >= -1075) {
89 uint64_t rb = (uint64_t)1 << (-1075-ex2);
90 if ((x & rb) && ((x & (rb+rb+rb-1)))) x += rb+rb;
91 x = (x & ~(rb+rb-1));
92 }
93 }
94
95 /* Convert to double using a signed int64_t conversion, then rescale. */
96 lj_assertX((int64_t)x >= 0, "bad double conversion");
97 n = (double)(int64_t)x;
98 if (neg) n = -n;
99 if (ex2) n = ldexp(n, ex2);
100 o->n = n;
101}
102
103/* Parse hexadecimal number. */
104static StrScanFmt strscan_hex(const uint8_t *p, TValue *o,
105 StrScanFmt fmt, uint32_t opt,
106 int32_t ex2, int32_t neg, uint32_t dig)
107{
108 uint64_t x = 0;
109 uint32_t i;
110
111 /* Scan hex digits. */
112 for (i = dig > 16 ? 16 : dig ; i; i--, p++) {
113 uint32_t d = (*p != '.' ? *p : *++p); if (d > '9') d += 9;
114 x = (x << 4) + (d & 15);
115 }
116
117 /* Summarize rounding-effect of excess digits. */
118 for (i = 16; i < dig; i++, p++)
119 x |= ((*p != '.' ? *p : *++p) != '0'), ex2 += 4;
120
121 /* Format-specific handling. */
122 switch (fmt) {
123 case STRSCAN_INT:
124 if (!(opt & STRSCAN_OPT_TONUM) && x < 0x80000000u+neg) {
125 o->i = neg ? -(int32_t)x : (int32_t)x;
126 return STRSCAN_INT; /* Fast path for 32 bit integers. */
127 }
128 if (!(opt & STRSCAN_OPT_C)) { fmt = STRSCAN_NUM; break; }
129 /* fallthrough */
130 case STRSCAN_U32:
131 if (dig > 8) return STRSCAN_ERROR;
132 o->i = neg ? -(int32_t)x : (int32_t)x;
133 return STRSCAN_U32;
134 case STRSCAN_I64:
135 case STRSCAN_U64:
136 if (dig > 16) return STRSCAN_ERROR;
137 o->u64 = neg ? (uint64_t)-(int64_t)x : x;
138 return fmt;
139 default:
140 break;
141 }
142
143 /* Reduce range, then convert to double. */
144 if ((x & U64x(c0000000,0000000))) { x = (x >> 2) | (x & 3); ex2 += 2; }
145 strscan_double(x, o, ex2, neg);
146 return fmt;
147}
148
149/* Parse octal number. */
150static StrScanFmt strscan_oct(const uint8_t *p, TValue *o,
151 StrScanFmt fmt, int32_t neg, uint32_t dig)
152{
153 uint64_t x = 0;
154
155 /* Scan octal digits. */
156 if (dig > 22 || (dig == 22 && *p > '1')) return STRSCAN_ERROR;
157 while (dig-- > 0) {
158 if (!(*p >= '0' && *p <= '7')) return STRSCAN_ERROR;
159 x = (x << 3) + (*p++ & 7);
160 }
161
162 /* Format-specific handling. */
163 switch (fmt) {
164 case STRSCAN_INT:
165 if (x >= 0x80000000u+neg) fmt = STRSCAN_U32;
166 /* fallthrough */
167 case STRSCAN_U32:
168 if ((x >> 32)) return STRSCAN_ERROR;
169 o->i = neg ? -(int32_t)x : (int32_t)x;
170 break;
171 default:
172 case STRSCAN_I64:
173 case STRSCAN_U64:
174 o->u64 = neg ? (uint64_t)-(int64_t)x : x;
175 break;
176 }
177 return fmt;
178}
179
180/* Parse decimal number. */
181static StrScanFmt strscan_dec(const uint8_t *p, TValue *o,
182 StrScanFmt fmt, uint32_t opt,
183 int32_t ex10, int32_t neg, uint32_t dig)
184{
185 uint8_t xi[STRSCAN_DDIG], *xip = xi;
186
187 if (dig) {
188 uint32_t i = dig;
189 if (i > STRSCAN_MAXDIG) {
190 ex10 += (int32_t)(i - STRSCAN_MAXDIG);
191 i = STRSCAN_MAXDIG;
192 }
193 /* Scan unaligned leading digit. */
194 if (((ex10^i) & 1))
195 *xip++ = ((*p != '.' ? *p : *++p) & 15), i--, p++;
196 /* Scan aligned double-digits. */
197 for ( ; i > 1; i -= 2) {
198 uint32_t d = 10 * ((*p != '.' ? *p : *++p) & 15); p++;
199 *xip++ = d + ((*p != '.' ? *p : *++p) & 15); p++;
200 }
201 /* Scan and realign trailing digit. */
202 if (i) *xip++ = 10 * ((*p != '.' ? *p : *++p) & 15), ex10--, dig++, p++;
203
204 /* Summarize rounding-effect of excess digits. */
205 if (dig > STRSCAN_MAXDIG) {
206 do {
207 if ((*p != '.' ? *p : *++p) != '0') { xip[-1] |= 1; break; }
208 p++;
209 } while (--dig > STRSCAN_MAXDIG);
210 dig = STRSCAN_MAXDIG;
211 } else { /* Simplify exponent. */
212 while (ex10 > 0 && dig <= 18) *xip++ = 0, ex10 -= 2, dig += 2;
213 }
214 } else { /* Only got zeros. */
215 ex10 = 0;
216 xi[0] = 0;
217 }
218
219 /* Fast path for numbers in integer format (but handles e.g. 1e6, too). */
220 if (dig <= 20 && ex10 == 0) {
221 uint8_t *xis;
222 uint64_t x = xi[0];
223 double n;
224 for (xis = xi+1; xis < xip; xis++) x = x * 100 + *xis;
225 if (!(dig == 20 && (xi[0] > 18 || (int64_t)x >= 0))) { /* No overflow? */
226 /* Format-specific handling. */
227 switch (fmt) {
228 case STRSCAN_INT:
229 if (!(opt & STRSCAN_OPT_TONUM) && x < 0x80000000u+neg) {
230 o->i = neg ? -(int32_t)x : (int32_t)x;
231 return STRSCAN_INT; /* Fast path for 32 bit integers. */
232 }
233 if (!(opt & STRSCAN_OPT_C)) { fmt = STRSCAN_NUM; goto plainnumber; }
234 /* fallthrough */
235 case STRSCAN_U32:
236 if ((x >> 32) != 0) return STRSCAN_ERROR;
237 o->i = neg ? -(int32_t)x : (int32_t)x;
238 return STRSCAN_U32;
239 case STRSCAN_I64:
240 case STRSCAN_U64:
241 o->u64 = neg ? (uint64_t)-(int64_t)x : x;
242 return fmt;
243 default:
244 plainnumber: /* Fast path for plain numbers < 2^63. */
245 if ((int64_t)x < 0) break;
246 n = (double)(int64_t)x;
247 if (neg) n = -n;
248 o->n = n;
249 return fmt;
250 }
251 }
252 }
253
254 /* Slow non-integer path. */
255 if (fmt == STRSCAN_INT) {
256 if ((opt & STRSCAN_OPT_C)) return STRSCAN_ERROR;
257 fmt = STRSCAN_NUM;
258 } else if (fmt > STRSCAN_INT) {
259 return STRSCAN_ERROR;
260 }
261 {
262 uint32_t hi = 0, lo = (uint32_t)(xip-xi);
263 int32_t ex2 = 0, idig = (int32_t)lo + (ex10 >> 1);
264
265 lj_assertX(lo > 0 && (ex10 & 1) == 0, "bad lo %d ex10 %d", lo, ex10);
266
267 /* Handle simple overflow/underflow. */
268 if (idig > 310/2) { if (neg) setminfV(o); else setpinfV(o); return fmt; }
269 else if (idig < -326/2) { o->n = neg ? -0.0 : 0.0; return fmt; }
270
271 /* Scale up until we have at least 17 or 18 integer part digits. */
272 while (idig < 9 && idig < DLEN(lo, hi)) {
273 uint32_t i, cy = 0;
274 ex2 -= 6;
275 for (i = DPREV(lo); ; i = DPREV(i)) {
276 uint32_t d = (xi[i] << 6) + cy;
277 cy = (((d >> 2) * 5243) >> 17); d = d - cy * 100; /* Div/mod 100. */
278 xi[i] = (uint8_t)d;
279 if (i == hi) break;
280 if (d == 0 && i == DPREV(lo)) lo = i;
281 }
282 if (cy) {
283 hi = DPREV(hi);
284 if (xi[DPREV(lo)] == 0) lo = DPREV(lo);
285 else if (hi == lo) { lo = DPREV(lo); xi[DPREV(lo)] |= xi[lo]; }
286 xi[hi] = (uint8_t)cy; idig++;
287 }
288 }
289
290 /* Scale down until no more than 17 or 18 integer part digits remain. */
291 while (idig > 9) {
292 uint32_t i = hi, cy = 0;
293 ex2 += 6;
294 do {
295 cy += xi[i];
296 xi[i] = (cy >> 6);
297 cy = 100 * (cy & 0x3f);
298 if (xi[i] == 0 && i == hi) hi = DNEXT(hi), idig--;
299 i = DNEXT(i);
300 } while (i != lo);
301 while (cy) {
302 if (hi == lo) { xi[DPREV(lo)] |= 1; break; }
303 xi[lo] = (cy >> 6); lo = DNEXT(lo);
304 cy = 100 * (cy & 0x3f);
305 }
306 }
307
308 /* Collect integer part digits and convert to rescaled double. */
309 {
310 uint64_t x = xi[hi];
311 uint32_t i;
312 for (i = DNEXT(hi); --idig > 0 && i != lo; i = DNEXT(i))
313 x = x * 100 + xi[i];
314 if (i == lo) {
315 while (--idig >= 0) x = x * 100;
316 } else { /* Gather round bit from remaining digits. */
317 x <<= 1; ex2--;
318 do {
319 if (xi[i]) { x |= 1; break; }
320 i = DNEXT(i);
321 } while (i != lo);
322 }
323 strscan_double(x, o, ex2, neg);
324 }
325 }
326 return fmt;
327}
328
329/* Parse binary number. */
330static StrScanFmt strscan_bin(const uint8_t *p, TValue *o,
331 StrScanFmt fmt, uint32_t opt,
332 int32_t ex2, int32_t neg, uint32_t dig)
333{
334 uint64_t x = 0;
335 uint32_t i;
336
337 if (ex2 || dig > 64) return STRSCAN_ERROR;
338
339 /* Scan binary digits. */
340 for (i = dig; i; i--, p++) {
341 if ((*p & ~1) != '0') return STRSCAN_ERROR;
342 x = (x << 1) | (*p & 1);
343 }
344
345 /* Format-specific handling. */
346 switch (fmt) {
347 case STRSCAN_INT:
348 if (!(opt & STRSCAN_OPT_TONUM) && x < 0x80000000u+neg) {
349 o->i = neg ? -(int32_t)x : (int32_t)x;
350 return STRSCAN_INT; /* Fast path for 32 bit integers. */
351 }
352 if (!(opt & STRSCAN_OPT_C)) { fmt = STRSCAN_NUM; break; }
353 /* fallthrough */
354 case STRSCAN_U32:
355 if (dig > 32) return STRSCAN_ERROR;
356 o->i = neg ? -(int32_t)x : (int32_t)x;
357 return STRSCAN_U32;
358 case STRSCAN_I64:
359 case STRSCAN_U64:
360 o->u64 = neg ? (uint64_t)-(int64_t)x : x;
361 return fmt;
362 default:
363 break;
364 }
365
366 /* Reduce range, then convert to double. */
367 if ((x & U64x(c0000000,0000000))) { x = (x >> 2) | (x & 3); ex2 += 2; }
368 strscan_double(x, o, ex2, neg);
369 return fmt;
370}
371
372/* Scan string containing a number. Returns format. Returns value in o. */
373StrScanFmt lj_strscan_scan(const uint8_t *p, MSize len, TValue *o,
374 uint32_t opt)
375{
376 int32_t neg = 0;
377 const uint8_t *pe = p + len;
378
379 /* Remove leading space, parse sign and non-numbers. */
380 if (LJ_UNLIKELY(!lj_char_isdigit(*p))) {
381 while (lj_char_isspace(*p)) p++;
382 if (*p == '+' || *p == '-') neg = (*p++ == '-');
383 if (LJ_UNLIKELY(*p >= 'A')) { /* Parse "inf", "infinity" or "nan". */
384 TValue tmp;
385 setnanV(&tmp);
386 if (casecmp(p[0],'i') && casecmp(p[1],'n') && casecmp(p[2],'f')) {
387 if (neg) setminfV(&tmp); else setpinfV(&tmp);
388 p += 3;
389 if (casecmp(p[0],'i') && casecmp(p[1],'n') && casecmp(p[2],'i') &&
390 casecmp(p[3],'t') && casecmp(p[4],'y')) p += 5;
391 } else if (casecmp(p[0],'n') && casecmp(p[1],'a') && casecmp(p[2],'n')) {
392 p += 3;
393 }
394 while (lj_char_isspace(*p)) p++;
395 if (*p || p < pe) return STRSCAN_ERROR;
396 o->u64 = tmp.u64;
397 return STRSCAN_NUM;
398 }
399 }
400
401 /* Parse regular number. */
402 {
403 StrScanFmt fmt = STRSCAN_INT;
404 int cmask = LJ_CHAR_DIGIT;
405 int base = (opt & STRSCAN_OPT_C) && *p == '0' ? 0 : 10;
406 const uint8_t *sp, *dp = NULL;
407 uint32_t dig = 0, hasdig = 0, x = 0;
408 int32_t ex = 0;
409
410 /* Determine base and skip leading zeros. */
411 if (LJ_UNLIKELY(*p <= '0')) {
412 if (*p == '0') {
413 if (casecmp(p[1], 'x'))
414 base = 16, cmask = LJ_CHAR_XDIGIT, p += 2;
415 else if (casecmp(p[1], 'b'))
416 base = 2, cmask = LJ_CHAR_DIGIT, p += 2;
417 }
418 for ( ; ; p++) {
419 if (*p == '0') {
420 hasdig = 1;
421 } else if (*p == '.') {
422 if (dp) return STRSCAN_ERROR;
423 dp = p;
424 } else {
425 break;
426 }
427 }
428 }
429
430 /* Preliminary digit and decimal point scan. */
431 for (sp = p; ; p++) {
432 if (LJ_LIKELY(lj_char_isa(*p, cmask))) {
433 x = x * 10 + (*p & 15); /* For fast path below. */
434 dig++;
435 } else if (*p == '.') {
436 if (dp) return STRSCAN_ERROR;
437 dp = p;
438 } else {
439 break;
440 }
441 }
442 if (!(hasdig | dig)) return STRSCAN_ERROR;
443
444 /* Handle decimal point. */
445 if (dp) {
446 if (base == 2) return STRSCAN_ERROR;
447 fmt = STRSCAN_NUM;
448 if (dig) {
449 ex = (int32_t)(dp-(p-1)); dp = p-1;
450 while (ex < 0 && *dp-- == '0') ex++, dig--; /* Skip trailing zeros. */
451 if (base == 16) ex *= 4;
452 }
453 }
454
455 /* Parse exponent. */
456 if (base >= 10 && casecmp(*p, (uint32_t)(base == 16 ? 'p' : 'e'))) {
457 uint32_t xx;
458 int negx = 0;
459 fmt = STRSCAN_NUM; p++;
460 if (*p == '+' || *p == '-') negx = (*p++ == '-');
461 if (!lj_char_isdigit(*p)) return STRSCAN_ERROR;
462 xx = (*p++ & 15);
463 while (lj_char_isdigit(*p)) {
464 if (xx < 65536) xx = xx * 10 + (*p & 15);
465 p++;
466 }
467 ex += negx ? -(int32_t)xx : (int32_t)xx;
468 }
469
470 /* Parse suffix. */
471 if (*p) {
472 /* I (IMAG), U (U32), LL (I64), ULL/LLU (U64), L (long), UL/LU (ulong). */
473 /* NYI: f (float). Not needed until cp_number() handles non-integers. */
474 if (casecmp(*p, 'i')) {
475 if (!(opt & STRSCAN_OPT_IMAG)) return STRSCAN_ERROR;
476 p++; fmt = STRSCAN_IMAG;
477 } else if (fmt == STRSCAN_INT) {
478 if (casecmp(*p, 'u')) p++, fmt = STRSCAN_U32;
479 if (casecmp(*p, 'l')) {
480 p++;
481 if (casecmp(*p, 'l')) p++, fmt += STRSCAN_I64 - STRSCAN_INT;
482 else if (!(opt & STRSCAN_OPT_C)) return STRSCAN_ERROR;
483 else if (sizeof(long) == 8) fmt += STRSCAN_I64 - STRSCAN_INT;
484 }
485 if (casecmp(*p, 'u') && (fmt == STRSCAN_INT || fmt == STRSCAN_I64))
486 p++, fmt += STRSCAN_U32 - STRSCAN_INT;
487 if ((fmt == STRSCAN_U32 && !(opt & STRSCAN_OPT_C)) ||
488 (fmt >= STRSCAN_I64 && !(opt & STRSCAN_OPT_LL)))
489 return STRSCAN_ERROR;
490 }
491 while (lj_char_isspace(*p)) p++;
492 if (*p) return STRSCAN_ERROR;
493 }
494 if (p < pe) return STRSCAN_ERROR;
495
496 /* Fast path for decimal 32 bit integers. */
497 if (fmt == STRSCAN_INT && base == 10 &&
498 (dig < 10 || (dig == 10 && *sp <= '2' && x < 0x80000000u+neg))) {
499 if ((opt & STRSCAN_OPT_TONUM)) {
500 o->n = neg ? -(double)x : (double)x;
501 return STRSCAN_NUM;
502 } else {
503 o->i = neg ? -(int32_t)x : (int32_t)x;
504 return STRSCAN_INT;
505 }
506 }
507
508 /* Dispatch to base-specific parser. */
509 if (base == 0 && !(fmt == STRSCAN_NUM || fmt == STRSCAN_IMAG))
510 return strscan_oct(sp, o, fmt, neg, dig);
511 if (base == 16)
512 fmt = strscan_hex(sp, o, fmt, opt, ex, neg, dig);
513 else if (base == 2)
514 fmt = strscan_bin(sp, o, fmt, opt, ex, neg, dig);
515 else
516 fmt = strscan_dec(sp, o, fmt, opt, ex, neg, dig);
517
518 /* Try to convert number to integer, if requested. */
519 if (fmt == STRSCAN_NUM && (opt & STRSCAN_OPT_TOINT)) {
520 double n = o->n;
521 int32_t i = lj_num2int(n);
522 if (n == (lua_Number)i) { o->i = i; return STRSCAN_INT; }
523 }
524 return fmt;
525 }
526}
527
528int LJ_FASTCALL lj_strscan_num(GCstr *str, TValue *o)
529{
530 StrScanFmt fmt = lj_strscan_scan((const uint8_t *)strdata(str), str->len, o,
531 STRSCAN_OPT_TONUM);
532 lj_assertX(fmt == STRSCAN_ERROR || fmt == STRSCAN_NUM, "bad scan format");
533 return (fmt != STRSCAN_ERROR);
534}
535
536#if LJ_DUALNUM
537int LJ_FASTCALL lj_strscan_number(GCstr *str, TValue *o)
538{
539 StrScanFmt fmt = lj_strscan_scan((const uint8_t *)strdata(str), str->len, o,
540 STRSCAN_OPT_TOINT);
541 lj_assertX(fmt == STRSCAN_ERROR || fmt == STRSCAN_NUM || fmt == STRSCAN_INT,
542 "bad scan format");
543 if (fmt == STRSCAN_INT) setitype(o, LJ_TISNUM);
544 return (fmt != STRSCAN_ERROR);
545}
546#endif
547
548#undef DNEXT
549#undef DPREV
550#undef DLEN
551
552