Branch data Line data Source code
1 : : /*
2 : : * This file is part of the MicroPython project, http://micropython.org/
3 : : *
4 : : * The MIT License (MIT)
5 : : *
6 : : * Copyright (c) 2013, 2014 Damien P. George
7 : : *
8 : : * Permission is hereby granted, free of charge, to any person obtaining a copy
9 : : * of this software and associated documentation files (the "Software"), to deal
10 : : * in the Software without restriction, including without limitation the rights
11 : : * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12 : : * copies of the Software, and to permit persons to whom the Software is
13 : : * furnished to do so, subject to the following conditions:
14 : : *
15 : : * The above copyright notice and this permission notice shall be included in
16 : : * all copies or substantial portions of the Software.
17 : : *
18 : : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19 : : * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20 : : * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21 : : * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22 : : * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23 : : * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
24 : : * THE SOFTWARE.
25 : : */
26 : :
27 : : #include <stdbool.h>
28 : : #include <stdlib.h>
29 : :
30 : : #include "py/runtime.h"
31 : : #include "py/parsenumbase.h"
32 : : #include "py/parsenum.h"
33 : : #include "py/smallint.h"
34 : :
35 : : #if MICROPY_PY_BUILTINS_FLOAT
36 : : #include <math.h>
37 : : #endif
38 : :
39 : 134 : static NORETURN void raise_exc(mp_obj_t exc, mp_lexer_t *lex) {
40 : : // if lex!=NULL then the parser called us and we need to convert the
41 : : // exception's type from ValueError to SyntaxError and add traceback info
42 [ + + ]: 134 : if (lex != NULL) {
43 : 16 : ((mp_obj_base_t *)MP_OBJ_TO_PTR(exc))->type = &mp_type_SyntaxError;
44 : 16 : mp_obj_exception_add_traceback(exc, lex->source_name, lex->tok_line, MP_QSTRnull);
45 : : }
46 : 134 : nlr_raise(exc);
47 : : }
48 : :
49 : 31355 : mp_obj_t mp_parse_num_integer(const char *restrict str_, size_t len, int base, mp_lexer_t *lex) {
50 : 31355 : const byte *restrict str = (const byte *)str_;
51 : 31355 : const byte *restrict top = str + len;
52 : 31355 : bool neg = false;
53 : 31355 : mp_obj_t ret_val;
54 : :
55 : : // check radix base
56 [ + - + + ]: 31355 : if ((base != 0 && base < 2) || base > 36) {
57 : : // this won't be reached if lex!=NULL
58 : 4 : mp_raise_ValueError(MP_ERROR_TEXT("int() arg 2 must be >= 2 and <= 36"));
59 : : }
60 : :
61 : : // skip leading space
62 [ + + + + ]: 31471 : for (; str < top && unichar_isspace(*str); str++) {
63 : 120 : }
64 : :
65 : : // parse optional sign
66 [ + + ]: 31360 : if (str < top) {
67 [ + + ]: 31348 : if (*str == '+') {
68 : 12 : str++;
69 [ + + ]: 31336 : } else if (*str == '-') {
70 : 296 : str++;
71 : 296 : neg = true;
72 : : }
73 : : }
74 : :
75 : : // parse optional base prefix
76 : 31360 : str += mp_parse_num_base((const char *)str, top - str, &base);
77 : :
78 : : // string should be an integer number
79 : 31360 : mp_int_t int_val = 0;
80 : 31360 : const byte *restrict str_val_start = str;
81 [ + + ]: 95775 : for (; str < top; str++) {
82 : : // get next digit as a value
83 : 65502 : mp_uint_t dig = *str;
84 [ + + ]: 65502 : if ('0' <= dig && dig <= '9') {
85 : : dig -= '0';
86 [ + + ]: 2378 : } else if (dig == '_') {
87 : 16 : continue;
88 : : } else {
89 : 2362 : dig |= 0x20; // make digit lower-case
90 [ + + ]: 2362 : if ('a' <= dig && dig <= 'z') {
91 : 2280 : dig -= 'a' - 10;
92 : : } else {
93 : : // unknown character
94 : : break;
95 : : }
96 : : }
97 [ + + ]: 65404 : if (dig >= (mp_uint_t)base) {
98 : : break;
99 : : }
100 : :
101 : : // add next digi and check for overflow
102 [ + + ]: 65356 : if (mp_small_int_mul_overflow(int_val, base)) {
103 : 943 : goto overflow;
104 : : }
105 : 64413 : int_val = int_val * base + dig;
106 [ + + ]: 64413 : if (!MP_SMALL_INT_FITS(int_val)) {
107 : 14 : goto overflow;
108 : : }
109 : : }
110 : :
111 : : // negate value if needed
112 [ + + ]: 30403 : if (neg) {
113 : 142 : int_val = -int_val;
114 : : }
115 : :
116 : : // create the small int
117 : 30403 : ret_val = MP_OBJ_NEW_SMALL_INT(int_val);
118 : :
119 : 31360 : have_ret_val:
120 : : // check we parsed something
121 [ + + ]: 31360 : if (str == str_val_start) {
122 : 54 : goto value_error;
123 : : }
124 : :
125 : : // skip trailing space
126 [ + + + + ]: 31438 : for (; str < top && unichar_isspace(*str); str++) {
127 : 132 : }
128 : :
129 : : // check we reached the end of the string
130 [ + + ]: 31306 : if (str != top) {
131 : 48 : goto value_error;
132 : : }
133 : :
134 : : // return the object
135 : 31258 : return ret_val;
136 : :
137 : 957 : overflow:
138 : : // reparse using long int
139 : : {
140 : 957 : const char *s2 = (const char *)str_val_start;
141 : 957 : ret_val = mp_obj_new_int_from_str_len(&s2, top - str_val_start, neg, base);
142 : 957 : str = (const byte *)s2;
143 : 957 : goto have_ret_val;
144 : : }
145 : :
146 : 102 : value_error:
147 : : {
148 : : #if MICROPY_ERROR_REPORTING <= MICROPY_ERROR_REPORTING_TERSE
149 : : mp_obj_t exc = mp_obj_new_exception_msg(&mp_type_ValueError,
150 : : MP_ERROR_TEXT("invalid syntax for integer"));
151 : : raise_exc(exc, lex);
152 : : #elif MICROPY_ERROR_REPORTING == MICROPY_ERROR_REPORTING_NORMAL
153 : : mp_obj_t exc = mp_obj_new_exception_msg_varg(&mp_type_ValueError,
154 : : MP_ERROR_TEXT("invalid syntax for integer with base %d"), base == 1 ? 0 : base);
155 : : raise_exc(exc, lex);
156 : : #else
157 : 102 : vstr_t vstr;
158 : 102 : mp_print_t print;
159 : 102 : vstr_init_print(&vstr, 50, &print);
160 [ + + ]: 192 : mp_printf(&print, "invalid syntax for integer with base %d: ", base == 1 ? 0 : base);
161 : 102 : mp_str_print_quoted(&print, str_val_start, top - str_val_start, true);
162 : 102 : mp_obj_t exc = mp_obj_new_exception_arg1(&mp_type_ValueError,
163 : : mp_obj_new_str_from_utf8_vstr(&vstr));
164 : 102 : raise_exc(exc, lex);
165 : : #endif
166 : : }
167 : : }
168 : :
169 : : enum {
170 : : REAL_IMAG_STATE_START = 0,
171 : : REAL_IMAG_STATE_HAVE_REAL = 1,
172 : : REAL_IMAG_STATE_HAVE_IMAG = 2,
173 : : };
174 : :
175 : : typedef enum {
176 : : PARSE_DEC_IN_INTG,
177 : : PARSE_DEC_IN_FRAC,
178 : : PARSE_DEC_IN_EXP,
179 : : } parse_dec_in_t;
180 : :
181 : : #if MICROPY_PY_BUILTINS_FLOAT
182 : : // MANTISSA_MAX is used to retain precision while not overflowing mantissa
183 : : // SMALL_NORMAL_VAL is the smallest power of 10 that is still a normal float
184 : : // EXACT_POWER_OF_10 is the largest value of x so that 10^x can be stored exactly in a float
185 : : // Note: EXACT_POWER_OF_10 is at least floor(log_5(2^mantissa_length)). Indeed, 10^n = 2^n * 5^n
186 : : // so we only have to store the 5^n part in the mantissa (the 2^n part will go into the float's
187 : : // exponent).
188 : : #if MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_FLOAT
189 : : #define MANTISSA_MAX 0x19999998U
190 : : #define SMALL_NORMAL_VAL (1e-37F)
191 : : #define SMALL_NORMAL_EXP (-37)
192 : : #define EXACT_POWER_OF_10 (9)
193 : : #elif MICROPY_FLOAT_IMPL == MICROPY_FLOAT_IMPL_DOUBLE
194 : : #define MANTISSA_MAX 0x1999999999999998ULL
195 : : #define SMALL_NORMAL_VAL (1e-307)
196 : : #define SMALL_NORMAL_EXP (-307)
197 : : #define EXACT_POWER_OF_10 (22)
198 : : #endif
199 : :
200 : : // Break out inner digit accumulation routine to ease trailing zero deferral.
201 : 45896 : static mp_float_uint_t accept_digit(mp_float_uint_t p_mantissa, unsigned int dig, int *p_exp_extra, int in) {
202 : : // Core routine to ingest an additional digit.
203 [ + + ]: 45896 : if (p_mantissa < MANTISSA_MAX) {
204 : : // dec_val won't overflow so keep accumulating
205 [ + + ]: 45884 : if (in == PARSE_DEC_IN_FRAC) {
206 : 23625 : --(*p_exp_extra);
207 : : }
208 : 45884 : return 10u * p_mantissa + dig;
209 : : } else {
210 : : // dec_val might overflow and we anyway can't represent more digits
211 : : // of precision, so ignore the digit and just adjust the exponent
212 [ + - ]: 12 : if (in == PARSE_DEC_IN_INTG) {
213 : 12 : ++(*p_exp_extra);
214 : : }
215 : 12 : return p_mantissa;
216 : : }
217 : : }
218 : : #endif // MICROPY_PY_BUILTINS_FLOAT
219 : :
220 : : #if MICROPY_PY_BUILTINS_COMPLEX
221 : 23788 : mp_obj_t mp_parse_num_decimal(const char *str, size_t len, bool allow_imag, bool force_complex, mp_lexer_t *lex)
222 : : #else
223 : : mp_obj_t mp_parse_num_float(const char *str, size_t len, bool allow_imag, mp_lexer_t *lex)
224 : : #endif
225 : : {
226 : : #if MICROPY_PY_BUILTINS_FLOAT
227 : :
228 : 23788 : const char *top = str + len;
229 : 23788 : mp_float_t dec_val = 0;
230 : 23788 : bool dec_neg = false;
231 : :
232 : : #if MICROPY_PY_BUILTINS_COMPLEX
233 : 23788 : unsigned int real_imag_state = REAL_IMAG_STATE_START;
234 : 23788 : mp_float_t dec_real = 0;
235 : 52 : parse_start:
236 : : #endif
237 : :
238 : : // skip leading space
239 [ + + + + ]: 23840 : for (; str < top && unichar_isspace(*str); str++) {
240 : 8 : }
241 : :
242 : : // parse optional sign
243 [ + + ]: 23832 : if (str < top) {
244 [ + + ]: 23828 : if (*str == '+') {
245 : 36 : str++;
246 [ + + ]: 23792 : } else if (*str == '-') {
247 : 112 : str++;
248 : 112 : dec_neg = true;
249 : : }
250 : : }
251 : :
252 : 23832 : const char *str_val_start = str;
253 : :
254 : : // determine what the string is
255 [ + + + + ]: 23832 : if (str < top && (str[0] | 0x20) == 'i') {
256 : : // string starts with 'i', should be 'inf' or 'infinity' (case insensitive)
257 [ + - + - : 1049 : if (str + 2 < top && (str[1] | 0x20) == 'n' && (str[2] | 0x20) == 'f') {
+ - ]
258 : : // inf
259 : 1049 : str += 3;
260 : 1049 : dec_val = (mp_float_t)INFINITY;
261 [ + + + - : 1049 : if (str + 4 < top && (str[0] | 0x20) == 'i' && (str[1] | 0x20) == 'n' && (str[2] | 0x20) == 'i' && (str[3] | 0x20) == 't' && (str[4] | 0x20) == 'y') {
+ - + - +
- + - ]
262 : : // infinity
263 : 8 : str += 5;
264 : : }
265 : : }
266 [ + + + + ]: 22783 : } else if (str < top && (str[0] | 0x20) == 'n') {
267 : : // string starts with 'n', should be 'nan' (case insensitive)
268 [ + - + - : 116 : if (str + 2 < top && (str[1] | 0x20) == 'a' && (str[2] | 0x20) == 'n') {
+ - ]
269 : : // NaN
270 : 116 : str += 3;
271 : 116 : dec_val = MICROPY_FLOAT_C_FUN(nan)("");
272 : : }
273 : : } else {
274 : : // string should be a decimal number
275 : 22667 : parse_dec_in_t in = PARSE_DEC_IN_INTG;
276 : 22667 : bool exp_neg = false;
277 : 22667 : mp_float_uint_t mantissa = 0;
278 : 22667 : int exp_val = 0;
279 : 22667 : int exp_extra = 0;
280 : 22667 : int trailing_zeros_intg = 0, trailing_zeros_frac = 0;
281 [ + + ]: 452974 : while (str < top) {
282 : 430563 : unsigned int dig = *str++;
283 [ + + ]: 430563 : if ('0' <= dig && dig <= '9') {
284 : 400546 : dig -= '0';
285 [ + + ]: 400546 : if (in == PARSE_DEC_IN_EXP) {
286 : : // don't overflow exp_val when adding next digit, instead just truncate
287 : : // it and the resulting float will still be correct, either inf or 0.0
288 : : // (use INT_MAX/2 to allow adding exp_extra at the end without overflow)
289 [ + + ]: 31173 : if (exp_val < (INT_MAX / 2 - 9) / 10) {
290 : 31077 : exp_val = 10 * exp_val + dig;
291 : : }
292 : : } else {
293 [ + + ]: 369373 : if (dig == 0 || mantissa >= MANTISSA_MAX) {
294 : : // Defer treatment of zeros in fractional part. If nothing comes afterwards, ignore them.
295 : : // Also, once we reach MANTISSA_MAX, treat every additional digit as a trailing zero.
296 [ + + ]: 342529 : if (in == PARSE_DEC_IN_INTG) {
297 : 35064 : ++trailing_zeros_intg;
298 : : } else {
299 : 307465 : ++trailing_zeros_frac;
300 : : }
301 : : } else {
302 : : // Time to un-defer any trailing zeros. Intg zeros first.
303 [ + + ]: 28682 : while (trailing_zeros_intg) {
304 : 1838 : mantissa = accept_digit(mantissa, 0, &exp_extra, PARSE_DEC_IN_INTG);
305 : 1838 : --trailing_zeros_intg;
306 : : }
307 [ + + ]: 44058 : while (trailing_zeros_frac) {
308 : 17214 : mantissa = accept_digit(mantissa, 0, &exp_extra, PARSE_DEC_IN_FRAC);
309 : 17214 : --trailing_zeros_frac;
310 : : }
311 : 26844 : mantissa = accept_digit(mantissa, dig, &exp_extra, in);
312 : : }
313 : : }
314 [ + + ]: 30017 : } else if (in == PARSE_DEC_IN_INTG && dig == '.') {
315 : : in = PARSE_DEC_IN_FRAC;
316 [ + + + + ]: 15327 : } else if (in != PARSE_DEC_IN_EXP && ((dig | 0x20) == 'e')) {
317 : 15055 : in = PARSE_DEC_IN_EXP;
318 [ + - ]: 15055 : if (str < top) {
319 [ + + ]: 15055 : if (str[0] == '+') {
320 : 7276 : str++;
321 [ + + ]: 7779 : } else if (str[0] == '-') {
322 : 6298 : str++;
323 : 6298 : exp_neg = true;
324 : : }
325 : : }
326 [ + + ]: 15055 : if (str == top) {
327 : 4 : goto value_error;
328 : : }
329 [ + + ]: 272 : } else if (dig == '_') {
330 : 20 : continue;
331 : : } else {
332 : : // unknown character
333 : : str--;
334 : : break;
335 : : }
336 : : }
337 : :
338 : : // work out the exponent
339 [ + + ]: 22663 : if (exp_neg) {
340 : 6298 : exp_val = -exp_val;
341 : : }
342 : :
343 : : // apply the exponent, making sure it's not a subnormal value
344 : 22663 : exp_val += exp_extra + trailing_zeros_intg;
345 : 22663 : dec_val = (mp_float_t)mantissa;
346 [ + + ]: 22663 : if (exp_val < SMALL_NORMAL_EXP) {
347 : 8 : exp_val -= SMALL_NORMAL_EXP;
348 : 8 : dec_val *= SMALL_NORMAL_VAL;
349 : : }
350 : :
351 : : // At this point, we need to multiply the mantissa by its base 10 exponent. If possible,
352 : : // we would rather manipulate numbers that have an exact representation in IEEE754. It
353 : : // turns out small positive powers of 10 do, whereas small negative powers of 10 don't.
354 : : // So in that case, we'll yield a division of exact values rather than a multiplication
355 : : // of slightly erroneous values.
356 [ + + ]: 22663 : if (exp_val < 0 && exp_val >= -EXACT_POWER_OF_10) {
357 : 3759 : dec_val /= MICROPY_FLOAT_C_FUN(pow)(10, -exp_val);
358 : : } else {
359 : 18904 : dec_val *= MICROPY_FLOAT_C_FUN(pow)(10, exp_val);
360 : : }
361 : : }
362 : :
363 [ + + + + ]: 23828 : if (allow_imag && str < top && (*str | 0x20) == 'j') {
364 : : #if MICROPY_PY_BUILTINS_COMPLEX
365 [ + + ]: 208 : if (str == str_val_start) {
366 : : // Convert "j" to "1j".
367 : 12 : dec_val = 1;
368 : : }
369 : 208 : ++str;
370 : 208 : real_imag_state |= REAL_IMAG_STATE_HAVE_IMAG;
371 : : #else
372 : : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("complex values not supported")), lex);
373 : : #endif
374 : : }
375 : :
376 : : // negate value if needed
377 [ + + ]: 23828 : if (dec_neg) {
378 : 112 : dec_val = -dec_val;
379 : : }
380 : :
381 : : // check we parsed something
382 [ + + ]: 23828 : if (str == str_val_start) {
383 : 8 : goto value_error;
384 : : }
385 : :
386 : : // skip trailing space
387 [ + + + + ]: 23832 : for (; str < top && unichar_isspace(*str); str++) {
388 : 12 : }
389 : :
390 : : // check we reached the end of the string
391 [ + + ]: 23820 : if (str != top) {
392 : : #if MICROPY_PY_BUILTINS_COMPLEX
393 [ + + ]: 60 : if (force_complex && real_imag_state == REAL_IMAG_STATE_START) {
394 : : // If we've only seen a real so far, keep parsing for the imaginary part.
395 : 44 : dec_real = dec_val;
396 : 44 : dec_val = 0;
397 : 44 : real_imag_state |= REAL_IMAG_STATE_HAVE_REAL;
398 : 44 : goto parse_start;
399 : : }
400 : : #endif
401 : 16 : goto value_error;
402 : : }
403 : :
404 : : #if MICROPY_PY_BUILTINS_COMPLEX
405 [ + + ]: 23760 : if (real_imag_state == REAL_IMAG_STATE_HAVE_REAL) {
406 : : // We're on the second part, but didn't get the expected imaginary number.
407 : 4 : goto value_error;
408 : : }
409 : : #endif
410 : :
411 : : // return the object
412 : :
413 : : #if MICROPY_PY_BUILTINS_COMPLEX
414 [ + + ]: 23756 : if (real_imag_state != REAL_IMAG_STATE_START) {
415 : 200 : return mp_obj_new_complex(dec_real, dec_val);
416 [ + + ]: 23556 : } else if (force_complex) {
417 : 8 : return mp_obj_new_complex(dec_val, 0);
418 : : }
419 : : #endif
420 : :
421 : 23548 : return mp_obj_new_float(dec_val);
422 : :
423 : 32 : value_error:
424 : 32 : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("invalid syntax for number")), lex);
425 : :
426 : : #else
427 : : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("decimal numbers not supported")), lex);
428 : : #endif
429 : : }
|
