Use -O not -O3: reduces ccan/tdb test time from 24 to 18 seconds.
[ccan] / ccan / ccan_tokenizer / read_cnumber.c
1
2 //for strtold
3 #define _ISOC99_SOURCE
4 #include <stdlib.h>
5 #undef _ISOC99_SOURCE
6
7 #include "ccan_tokenizer.h"
8
9 #ifndef ULLONG_MAX
10 #define ULLONG_MAX 18446744073709551615ULL
11 #endif
12
13 static const char *skipnum(const char *s, const char *e, readui_base base) {
14         for (;s<e;s++) {
15                 unsigned int c = (unsigned char)*s;
16                 
17                 if (cdigit(c)) {
18                         if ( c-'0' >= (base & 0xFF) &&
19                             !(base & READUI_ALLOWHIGHERDIGITS) )
20                                 break;
21                 } else if (c>='A' && c<='Z') {
22                         if (!(base & READUI_ALLOWCAPLETTERS))
23                                 break;
24                         if ( c-'A'+10 >= (base & 0xFF) &&
25                             !(base & READUI_ALLOWHIGHERDIGITS))
26                                 break;
27                 } else if (c>='a' && c<='z') {
28                         if (!(base & READUI_ALLOWLCASELETTERS))
29                                 break;
30                         if ( c-'a'+10 >= (base & 0xFF) &&
31                             !(base & READUI_ALLOWHIGHERDIGITS))
32                                 break;
33                 } else
34                         break;
35         }
36         
37         return s;
38 }
39
40 static uint64_t readui_valid(const char *s, const char *e, readui_base base) {
41         uint64_t ret = 0;
42         uint64_t multiplier = 1;
43         uint64_t digit_value;
44         
45         //64-bit multiplication with overflow checking
46         #define multiply(dest, src) do { \
47                 uint32_t a0 = (uint64_t)(dest) & 0xFFFFFFFF; \
48                 uint32_t a1 = (uint64_t)(dest) >> 32; \
49                 uint32_t b0 = (uint64_t)(src) & 0xFFFFFFFF; \
50                 uint32_t b1 = (uint64_t)(src) >> 32; \
51                 uint64_t a, b; \
52                 \
53                 if (a1 && b1) \
54                         goto overflowed; \
55                 a = (uint64_t)a1*b0 + (uint64_t)a0*b1; \
56                 if (a > 0xFFFFFFFF) \
57                         goto overflowed; \
58                 a <<= 32; \
59                 b = (uint64_t)a0*b0; \
60                 \
61                 if (a+b < a) \
62                         goto overflowed; \
63                 (dest) = a+b; \
64         } while(0)
65         
66         if (s >= e || ((base&0xFF) < 1)) {
67                 errno = EINVAL;
68                 return 0;
69         }
70         
71         while (s<e && *s=='0') s++;
72         
73         if (e > s) {
74                 for (;;) {
75                         char c = *--e;
76                         
77                         //this series of if statements takes advantage of the fact that 'a'>'A'>'0'
78                         if (c >= 'a')
79                                 c -= 'a'-10;
80                         else if (c >= 'A')
81                                 c -= 'A'-10;
82                         else
83                                 c -= '0';
84                         digit_value = c;
85                         
86                         //TODO:  Write/find a testcase where temp *= multiplier does overflow
87                         multiply(digit_value, multiplier);
88                         
89                         if (ret+digit_value < ret)
90                                 goto overflowed;
91                         ret += digit_value;
92                         
93                         if (e <= s)
94                                 break;
95                         
96                         multiply(multiplier, base & 0xFF);
97                 }
98         }
99         errno = 0;
100         return ret;
101         
102 overflowed:
103         errno = ERANGE;
104         return ULLONG_MAX;
105         
106         #undef multiply
107 }
108
109 uint64_t readui(const char **sp, const char *e, readui_base base) {
110         const char *s = *sp;
111         
112         while (s<e && cwhite(*s)) s++;
113         e = skipnum(s, e, base);
114         
115         *sp = e;
116         return readui_valid(s, e, base);
117 }
118
119
120 #define MESSAGE_PATH "tokenize/read_cnumber/"
121
122 struct scan_number {
123 /*
124  * Each of the pointers points to the first character of a given component.
125  * Consider 0x50.1p+1f .  It would be broken down into:
126  */
127         const char *prefix;   // 0x
128         const char *digits;   // 50.1
129         const char *exponent; // p+1
130         const char *suffix;   // f
131         const char *end;
132         size_t dots_found;    // 1
133 };
134
135 /*
136  * Scans past all the characters in a number token, fills the struct, and
137  * returns one of TOK_INTEGER or TOK_FLOATING to indicate the type.
138  *
139  * First character must be [0-9 '.']
140  */
141 static enum token_type scan_number(struct scan_number *sn,
142                                         const char *s, const char *e) {
143         enum token_type type;
144         
145         sn->dots_found = 0;
146         
147         sn->prefix = s;
148         sn->digits = s;
149         if (s+3<=e && s[0]=='0') {
150                 if (s[1]=='X' || s[1]=='x') {
151                 //hexadecimal
152                         s += 2;
153                         sn->digits = s;
154                         for (;s<e;s++) {
155                                 if (*s == '.')
156                                         sn->dots_found++;
157                                 else if (!chex(*s))
158                                         break;
159                         }
160                         goto done_scanning_digits;
161                 } else if (s[1]=='B' || s[1]=='b') {
162                 //binary
163                         s += 2;
164                         if (*s!='0' && *s!='1')
165                                 s -= 2;
166                         sn->digits = s;
167                 }
168         }
169         
170         //binary, decimal, or octal
171         for (;s<e;s++) {
172                 if (*s == '.')
173                         sn->dots_found++;
174                 else if (!cdigit(*s))
175                         break;
176         }
177
178 done_scanning_digits:
179         
180         sn->exponent = s;
181         if (s<e && (
182                 (sn->prefix==sn->digits && (*s=='E' || *s=='e')) ||
183                 (sn->prefix < sn->digits && (*s=='P' || *s=='p'))
184         )) {
185                 s++;
186                 if (s<e && (*s=='+' || *s=='-'))
187                         s++;
188                 while (s<e && cdigit(*s)) s++;
189         }
190         
191         sn->suffix = s;
192         while (s<e && (cdigit(*s) || cletter(*s) ||
193                 *s=='.' || *s=='_' || *s=='$')) s++;
194         
195         sn->end = s;
196         
197         //Now we're done scanning, but now we want to know what type this is
198         type = TOK_INTEGER;
199         if (sn->dots_found)
200                 type = TOK_FLOATING;
201         if (sn->exponent < sn->suffix)
202                 type = TOK_FLOATING;
203         
204         //if this is an octal, make the leading 0 a prefix
205         if (type==TOK_INTEGER && sn->prefix==sn->digits &&
206                         sn->digits < s && sn->digits[0]=='0')
207                 sn->digits++;
208         
209         return type;
210 }
211
212 static enum tok_suffix read_number_suffix(const char *s, const char *e,
213                         enum token_type type, tok_message_queue *mq) {
214         const char *orig_s = s;
215         enum tok_suffix sfx = 0;
216         
217         //read the suffix in pieces
218         while (s<e) {
219                 enum tok_suffix sfx_prev = sfx;
220                 char c = *s++;
221                 if (c>='a' && c<='z')
222                         c -= 'a'-'A';
223                 
224                 if (c=='L') {
225                         if (s<e && (*s=='L' || *s=='l')) {
226                                 s++;
227                                 sfx |= TOK_LL;
228                                 
229                                 //TOK_L and TOK_LL are mutually exclusive
230                                 if (sfx & TOK_L)
231                                         goto invalid;
232                         } else {
233                                 sfx |= TOK_L;
234                         }
235                 }
236                 else if (c=='U')
237                         sfx |= TOK_U;
238                 else if (c=='F')
239                         sfx |= TOK_F;
240                 else if (c=='I')
241                         sfx |= TOK_I;
242                 else
243                         goto invalid;
244                 
245                 if (sfx == sfx_prev)
246                         goto invalid; //suffix piece was repeated
247         }
248         
249         //make sure the suffix is appropriate for this number type
250         if (type==TOK_INTEGER && (sfx & TOK_F)) {
251                 tok_msg_error(suffix_float_only, orig_s,
252                 "Suffix only valid for floating point numbers");
253                 sfx = TOK_NOSUFFIX;
254         }
255         if (type==TOK_FLOATING && (sfx & (TOK_U | TOK_LL))) {
256                 tok_msg_error(suffix_integer_only, orig_s,
257                 "Suffix only valid for integers");
258                 sfx = TOK_NOSUFFIX;
259         }
260         
261         return sfx;
262         
263 invalid:
264         if (type==TOK_INTEGER)
265                 tok_msg_error(integer_suffix_invalid, orig_s,
266                                 "Integer suffix invalid");
267         else
268                 tok_msg_error(floating_suffix_invalid, orig_s,
269                                 "Floating point suffix invalid");
270         return TOK_NOSUFFIX;
271 }
272
273 static void read_integer(struct tok_integer *out, const struct scan_number *sn,
274                         tok_message_queue *mq) {
275         /*
276         Assertions about an integer's struct scan_number:
277                 prefix is empty or [0 0B 0b 0X 0x]
278                 sn->digits is not empty (i.e. sn->digits < sn->exponent)
279                         *unless* the prefix is "0"
280                 has no exponent
281                 suffix is [0-9 A-Z a-z '.']*
282                 dots_found == 0
283         */
284         readui_base base = READUI_DEC;
285         const char *tokstart = sn->prefix;
286         const char *s = sn->digits, *e = sn->exponent;
287         
288         if (sn->prefix+1 < sn->digits) {
289                 if (sn->prefix[1]=='X' || sn->prefix[1]=='x')
290                         base = READUI_HEX;
291                 else
292                         base = READUI_OCT;
293         } else if (sn->prefix < sn->digits) {
294                 base = READUI_OCT;
295         }
296         
297         if (s>=e && base==READUI_OCT) {
298                 //octal contains no digits
299                 out->v = 0;
300                 out->base = 8;
301                 goto suffix;
302         }
303         
304         out->v = readui(&s, sn->exponent, base);
305         out->base = base & 0xFF;
306         
307         if (s != e || errno == EINVAL) {
308                 tok_msg_error(integer_invalid_digits, tokstart,
309                         "Integer constant contains invalid digits");
310         } else if (errno) {
311                 if (errno == ERANGE) {
312                         tok_msg_error(integer_out_of_range, tokstart,
313                                 "Integer constant out of range");
314                 } else {
315                         tok_msg_bug(readui_unknown, tokstart,
316                                 "Unknown error returned by readui");
317                 }
318         }
319         
320 suffix:
321         out->suffix =
322                 read_number_suffix(sn->suffix, sn->end, TOK_INTEGER, mq);
323         
324         return;
325 }
326
327 static void read_floating(struct tok_floating *out, const struct scan_number *sn,
328                         tok_message_queue *mq) {
329         /*
330         Assertions about a float's struct scan_number:
331                 prefix is empty or [0B 0b 0X 0x] (note: no octal prefix 0)
332                 sn->digits not empty, ever
333                 exponent may or may not exist
334                 If exponent exists, it is valid and formatted as:
335                         ( [E P e p] ['+' '-']*0..1 [0-9]* )
336                 An exponent starts with E if this is decimal, P if it is hex/binary
337                 suffix is [0-9 A-Z a-z '.']*
338                 dots_found can be anything
339         */
340         const char *tokstart = sn->prefix;
341         const char *s = sn->prefix, *e = sn->suffix;
342         char borrow = *sn->end;
343         //long double strtold(const char *nptr, char **endptr);
344         
345         out->v = 0.0;
346         out->suffix = TOK_NOSUFFIX;
347         
348         if (sn->prefix < sn->digits) {
349                 if (sn->prefix[1]=='B' || sn->prefix[1]=='b') {
350                         tok_msg_error(binary_float, tokstart,
351                                 "Binary floating point constants not allowed");
352                         return;
353                 }
354                 if (sn->exponent >= sn->suffix) {
355                         tok_msg_error(hex_float_no_exponent, tokstart,
356                                 "Hex floating point constant missing exponent");
357                         return;
358                 }
359         }
360         
361         
362         /* Stick a null terminator at the end of the input so strtold
363          * won't read beyond the given input.
364          *
365          * This is thread-safe because the input is from
366          * token_list.txt, which was generated in the
367          * tokenize function which is still running.
368          */
369         *(char*)sn->end = 0;
370         errno = 0;
371         out->v = strtold(s, (char**)&s);
372         //don't forget to set it back
373         *(char*)sn->end = borrow;
374         
375         if (errno) {
376                 //for some reason, strtold may errno to EDOM to indicate underrun
377                 //open test/run.c and search "floating_out_of_range" for more details
378                 if (errno == ERANGE || errno == EDOM) {
379                         tok_msg_error(floating_out_of_range, tokstart,
380                                 "Floating point constant out of range");
381                 } else {
382                         tok_msg_bug(strtold_unknown, tokstart,
383                                 "Unknown error returned by strtold");
384                 }
385         }
386         
387         if (s != e) {
388                 tok_msg_error(floating_invalid_digits, tokstart,
389                         "Floating point constant contains invalid digits");
390         }
391         
392         out->suffix =
393                 read_number_suffix(sn->suffix, sn->end, TOK_FLOATING, mq);
394 }
395
396 char *read_cnumber(struct token *tok, const char *s, const char *e, tok_message_queue *mq) {
397         struct scan_number sn;
398         
399         tok->type = scan_number(&sn, s, e);
400         if (tok->type == TOK_INTEGER)
401                 read_integer(&tok->integer, &sn, mq);
402         else
403                 read_floating(&tok->floating, &sn, mq);
404         
405         return (char*)sn.end;
406 }
407
408 #undef MESSAGE_PATH