git.ozlabs.org Git - ccan/blob - 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