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 : 122 : 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 [ + + ]: 122 : if (lex != NULL) {
43 : 12 : ((mp_obj_base_t *)MP_OBJ_TO_PTR(exc))->type = &mp_type_SyntaxError;
44 : 12 : mp_obj_exception_add_traceback(exc, lex->source_name, lex->tok_line, MP_QSTRnull);
45 : : }
46 : 122 : nlr_raise(exc);
47 : : }
48 : :
49 : 30551 : mp_obj_t mp_parse_num_integer(const char *restrict str_, size_t len, int base, mp_lexer_t *lex) {
50 : 30551 : const byte *restrict str = (const byte *)str_;
51 : 30551 : const byte *restrict top = str + len;
52 : 30551 : bool neg = false;
53 : 30551 : mp_obj_t ret_val;
54 : :
55 : : // check radix base
56 [ + - + + ]: 30551 : 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 [ + + + + ]: 30655 : for (; str < top && unichar_isspace(*str); str++) {
63 : 108 : }
64 : :
65 : : // parse optional sign
66 [ + + ]: 30568 : if (str < top) {
67 [ + + ]: 30556 : if (*str == '+') {
68 : 12 : str++;
69 [ + + ]: 30544 : } else if (*str == '-') {
70 : 296 : str++;
71 : 296 : neg = true;
72 : : }
73 : : }
74 : :
75 : : // parse optional base prefix
76 : 30568 : str += mp_parse_num_base((const char *)str, top - str, &base);
77 : :
78 : : // string should be an integer number
79 : 30568 : mp_int_t int_val = 0;
80 : 30568 : const byte *restrict str_val_start = str;
81 [ + + ]: 93767 : for (; str < top; str++) {
82 : : // get next digit as a value
83 : 64228 : mp_uint_t dig = *str;
84 [ + + ]: 64228 : if ('0' <= dig && dig <= '9') {
85 : : dig -= '0';
86 [ + + ]: 2326 : } else if (dig == '_') {
87 : 16 : continue;
88 : : } else {
89 : 2310 : dig |= 0x20; // make digit lower-case
90 [ + + ]: 2310 : if ('a' <= dig && dig <= 'z') {
91 : 2276 : dig -= 'a' - 10;
92 : : } else {
93 : : // unknown character
94 : : break;
95 : : }
96 : : }
97 [ + + ]: 64178 : if (dig >= (mp_uint_t)base) {
98 : : break;
99 : : }
100 : :
101 : : // add next digi and check for overflow
102 [ + + ]: 64142 : if (mp_small_int_mul_overflow(int_val, base)) {
103 : 943 : goto overflow;
104 : : }
105 : 63197 : int_val = int_val * base + dig;
106 [ + + ]: 63197 : if (!MP_SMALL_INT_FITS(int_val)) {
107 : 14 : goto overflow;
108 : : }
109 : : }
110 : :
111 : : // negate value if needed
112 [ + + ]: 29609 : if (neg) {
113 : 142 : int_val = -int_val;
114 : : }
115 : :
116 : : // create the small int
117 : 29609 : ret_val = MP_OBJ_NEW_SMALL_INT(int_val);
118 : :
119 : 30566 : have_ret_val:
120 : : // check we parsed something
121 [ + + ]: 30566 : if (str == str_val_start) {
122 : 54 : goto value_error;
123 : : }
124 : :
125 : : // skip trailing space
126 [ + + + + ]: 30588 : for (; str < top && unichar_isspace(*str); str++) {
127 : 76 : }
128 : :
129 : : // check we reached the end of the string
130 [ + + ]: 30513 : if (str != top) {
131 : 36 : goto value_error;
132 : : }
133 : :
134 : : // return the object
135 : 30477 : 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 : 90 : 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);
155 : : raise_exc(exc, lex);
156 : : #else
157 : 90 : vstr_t vstr;
158 : 90 : mp_print_t print;
159 : 90 : vstr_init_print(&vstr, 50, &print);
160 : 90 : mp_printf(&print, "invalid syntax for integer with base %d: ", base);
161 : 90 : mp_str_print_quoted(&print, str_val_start, top - str_val_start, true);
162 : 90 : mp_obj_t exc = mp_obj_new_exception_arg1(&mp_type_ValueError,
163 : : mp_obj_new_str_from_utf8_vstr(&vstr));
164 : 90 : 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 : : // DEC_VAL_MAX only needs to be rough and is used to retain precision while not overflowing
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 DEC_VAL_MAX 1e20F
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 DEC_VAL_MAX 1e200
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 : 53628 : static void accept_digit(mp_float_t *p_dec_val, int dig, int *p_exp_extra, int in) {
202 : : // Core routine to ingest an additional digit.
203 [ + + ]: 53628 : if (*p_dec_val < DEC_VAL_MAX) {
204 : : // dec_val won't overflow so keep accumulating
205 : 53626 : *p_dec_val = 10 * *p_dec_val + dig;
206 [ + + ]: 53626 : if (in == PARSE_DEC_IN_FRAC) {
207 : 27047 : --(*p_exp_extra);
208 : : }
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 [ - + ]: 2 : if (in == PARSE_DEC_IN_INTG) {
213 : 0 : ++(*p_exp_extra);
214 : : }
215 : : }
216 : 53628 : }
217 : : #endif // MICROPY_PY_BUILTINS_FLOAT
218 : :
219 : : #if MICROPY_PY_BUILTINS_COMPLEX
220 : 23784 : mp_obj_t mp_parse_num_decimal(const char *str, size_t len, bool allow_imag, bool force_complex, mp_lexer_t *lex)
221 : : #else
222 : : mp_obj_t mp_parse_num_float(const char *str, size_t len, bool allow_imag, mp_lexer_t *lex)
223 : : #endif
224 : : {
225 : : #if MICROPY_PY_BUILTINS_FLOAT
226 : :
227 : 23784 : const char *top = str + len;
228 : 23784 : mp_float_t dec_val = 0;
229 : 23784 : bool dec_neg = false;
230 : :
231 : : #if MICROPY_PY_BUILTINS_COMPLEX
232 : 23784 : unsigned int real_imag_state = REAL_IMAG_STATE_START;
233 : 23784 : mp_float_t dec_real = 0;
234 : 52 : parse_start:
235 : : #endif
236 : :
237 : : // skip leading space
238 [ + + + + ]: 23836 : for (; str < top && unichar_isspace(*str); str++) {
239 : 8 : }
240 : :
241 : : // parse optional sign
242 [ + + ]: 23828 : if (str < top) {
243 [ + + ]: 23824 : if (*str == '+') {
244 : 36 : str++;
245 [ + + ]: 23788 : } else if (*str == '-') {
246 : 112 : str++;
247 : 112 : dec_neg = true;
248 : : }
249 : : }
250 : :
251 : 23828 : const char *str_val_start = str;
252 : :
253 : : // determine what the string is
254 [ + + + + ]: 23828 : if (str < top && (str[0] | 0x20) == 'i') {
255 : : // string starts with 'i', should be 'inf' or 'infinity' (case insensitive)
256 [ + - + - : 1049 : if (str + 2 < top && (str[1] | 0x20) == 'n' && (str[2] | 0x20) == 'f') {
+ - ]
257 : : // inf
258 : 1049 : str += 3;
259 : 1049 : dec_val = (mp_float_t)INFINITY;
260 [ + + + - : 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') {
+ - + - +
- + - ]
261 : : // infinity
262 : 8 : str += 5;
263 : : }
264 : : }
265 [ + + + + ]: 22779 : } else if (str < top && (str[0] | 0x20) == 'n') {
266 : : // string starts with 'n', should be 'nan' (case insensitive)
267 [ + - + - : 116 : if (str + 2 < top && (str[1] | 0x20) == 'a' && (str[2] | 0x20) == 'n') {
+ - ]
268 : : // NaN
269 : 116 : str += 3;
270 : 116 : dec_val = MICROPY_FLOAT_C_FUN(nan)("");
271 : : }
272 : : } else {
273 : : // string should be a decimal number
274 : 22663 : parse_dec_in_t in = PARSE_DEC_IN_INTG;
275 : 22663 : bool exp_neg = false;
276 : 22663 : int exp_val = 0;
277 : 22663 : int exp_extra = 0;
278 : 22663 : int trailing_zeros_intg = 0, trailing_zeros_frac = 0;
279 [ + + ]: 452876 : while (str < top) {
280 : 430469 : unsigned int dig = *str++;
281 [ + + ]: 430469 : if ('0' <= dig && dig <= '9') {
282 : 400452 : dig -= '0';
283 [ + + ]: 400452 : if (in == PARSE_DEC_IN_EXP) {
284 : : // don't overflow exp_val when adding next digit, instead just truncate
285 : : // it and the resulting float will still be correct, either inf or 0.0
286 : : // (use INT_MAX/2 to allow adding exp_extra at the end without overflow)
287 [ + + ]: 31173 : if (exp_val < (INT_MAX / 2 - 9) / 10) {
288 : 31077 : exp_val = 10 * exp_val + dig;
289 : : }
290 : : } else {
291 [ + + + + ]: 369279 : if (dig == 0 || dec_val >= DEC_VAL_MAX) {
292 : : // Defer treatment of zeros in fractional part. If nothing comes afterwards, ignore them.
293 : : // Also, once we reach DEC_VAL_MAX, treat every additional digit as a trailing zero.
294 [ + + ]: 334723 : if (in == PARSE_DEC_IN_INTG) {
295 : 30608 : ++trailing_zeros_intg;
296 : : } else {
297 : 304115 : ++trailing_zeros_frac;
298 : : }
299 : : } else {
300 : : // Time to un-defer any trailing zeros. Intg zeros first.
301 [ + + ]: 36338 : while (trailing_zeros_intg) {
302 : 1782 : accept_digit(&dec_val, 0, &exp_extra, PARSE_DEC_IN_INTG);
303 : 1782 : --trailing_zeros_intg;
304 : : }
305 [ + + ]: 51846 : while (trailing_zeros_frac) {
306 : 17290 : accept_digit(&dec_val, 0, &exp_extra, PARSE_DEC_IN_FRAC);
307 : 17290 : --trailing_zeros_frac;
308 : : }
309 : 34556 : accept_digit(&dec_val, dig, &exp_extra, in);
310 : : }
311 : : }
312 [ + + ]: 30017 : } else if (in == PARSE_DEC_IN_INTG && dig == '.') {
313 : : in = PARSE_DEC_IN_FRAC;
314 [ + + + + ]: 15327 : } else if (in != PARSE_DEC_IN_EXP && ((dig | 0x20) == 'e')) {
315 : 15055 : in = PARSE_DEC_IN_EXP;
316 [ + - ]: 15055 : if (str < top) {
317 [ + + ]: 15055 : if (str[0] == '+') {
318 : 7276 : str++;
319 [ + + ]: 7779 : } else if (str[0] == '-') {
320 : 6298 : str++;
321 : 6298 : exp_neg = true;
322 : : }
323 : : }
324 [ + + ]: 15055 : if (str == top) {
325 : 4 : goto value_error;
326 : : }
327 [ + + ]: 272 : } else if (dig == '_') {
328 : 20 : continue;
329 : : } else {
330 : : // unknown character
331 : : str--;
332 : : break;
333 : : }
334 : : }
335 : :
336 : : // work out the exponent
337 [ + + ]: 22659 : if (exp_neg) {
338 : 6298 : exp_val = -exp_val;
339 : : }
340 : :
341 : : // apply the exponent, making sure it's not a subnormal value
342 : 22659 : exp_val += exp_extra + trailing_zeros_intg;
343 [ + + ]: 22659 : if (exp_val < SMALL_NORMAL_EXP) {
344 : 8 : exp_val -= SMALL_NORMAL_EXP;
345 : 8 : dec_val *= SMALL_NORMAL_VAL;
346 : : }
347 : :
348 : : // At this point, we need to multiply the mantissa by its base 10 exponent. If possible,
349 : : // we would rather manipulate numbers that have an exact representation in IEEE754. It
350 : : // turns out small positive powers of 10 do, whereas small negative powers of 10 don't.
351 : : // So in that case, we'll yield a division of exact values rather than a multiplication
352 : : // of slightly erroneous values.
353 [ + + ]: 22659 : if (exp_val < 0 && exp_val >= -EXACT_POWER_OF_10) {
354 : 3741 : dec_val /= MICROPY_FLOAT_C_FUN(pow)(10, -exp_val);
355 : : } else {
356 : 18918 : dec_val *= MICROPY_FLOAT_C_FUN(pow)(10, exp_val);
357 : : }
358 : : }
359 : :
360 [ + + + + ]: 23824 : if (allow_imag && str < top && (*str | 0x20) == 'j') {
361 : : #if MICROPY_PY_BUILTINS_COMPLEX
362 [ + + ]: 208 : if (str == str_val_start) {
363 : : // Convert "j" to "1j".
364 : 12 : dec_val = 1;
365 : : }
366 : 208 : ++str;
367 : 208 : real_imag_state |= REAL_IMAG_STATE_HAVE_IMAG;
368 : : #else
369 : : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("complex values not supported")), lex);
370 : : #endif
371 : : }
372 : :
373 : : // negate value if needed
374 [ + + ]: 23824 : if (dec_neg) {
375 : 112 : dec_val = -dec_val;
376 : : }
377 : :
378 : : // check we parsed something
379 [ + + ]: 23824 : if (str == str_val_start) {
380 : 8 : goto value_error;
381 : : }
382 : :
383 : : // skip trailing space
384 [ + + + + ]: 23828 : for (; str < top && unichar_isspace(*str); str++) {
385 : 12 : }
386 : :
387 : : // check we reached the end of the string
388 [ + + ]: 23816 : if (str != top) {
389 : : #if MICROPY_PY_BUILTINS_COMPLEX
390 [ + + ]: 60 : if (force_complex && real_imag_state == REAL_IMAG_STATE_START) {
391 : : // If we've only seen a real so far, keep parsing for the imaginary part.
392 : 44 : dec_real = dec_val;
393 : 44 : dec_val = 0;
394 : 44 : real_imag_state |= REAL_IMAG_STATE_HAVE_REAL;
395 : 44 : goto parse_start;
396 : : }
397 : : #endif
398 : 16 : goto value_error;
399 : : }
400 : :
401 : : #if MICROPY_PY_BUILTINS_COMPLEX
402 [ + + ]: 23756 : if (real_imag_state == REAL_IMAG_STATE_HAVE_REAL) {
403 : : // We're on the second part, but didn't get the expected imaginary number.
404 : 4 : goto value_error;
405 : : }
406 : : #endif
407 : :
408 : : // return the object
409 : :
410 : : #if MICROPY_PY_BUILTINS_COMPLEX
411 [ + + ]: 23752 : if (real_imag_state != REAL_IMAG_STATE_START) {
412 : 200 : return mp_obj_new_complex(dec_real, dec_val);
413 [ + + ]: 23552 : } else if (force_complex) {
414 : 8 : return mp_obj_new_complex(dec_val, 0);
415 : : }
416 : : #endif
417 : :
418 : 23544 : return mp_obj_new_float(dec_val);
419 : :
420 : 32 : value_error:
421 : 32 : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("invalid syntax for number")), lex);
422 : :
423 : : #else
424 : : raise_exc(mp_obj_new_exception_msg(&mp_type_ValueError, MP_ERROR_TEXT("decimal numbers not supported")), lex);
425 : : #endif
426 : : }
|
