gcc/cppexp.c

   1 /* Parse C expressions for cpplib.
   2    Copyright (C) 1987, 1992, 1994, 1995, 1997, 1998, 1999, 2000, 2001,
   3    2002 Free Software Foundation.
   4    Contributed by Per Bothner, 1994.
   5
   6 This program is free software; you can redistribute it and/or modify it
   7 under the terms of the GNU General Public License as published by the
   8 Free Software Foundation; either version 2, or (at your option) any
   9 later version.
  10
  11 This program is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with this program; if not, write to the Free Software
  18 Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 #include "config.h"
  22 #include "system.h"
  23 #include "cpplib.h"
  24 #include "cpphash.h"
  25
  26 #define PART_PRECISION (sizeof (cpp_num_part) * CHAR_BIT)
  27 #define HALF_MASK (~(cpp_num_part) 0 >> (PART_PRECISION / 2))
  28 #define LOW_PART(num_part) (num_part & HALF_MASK)
  29 #define HIGH_PART(num_part) (num_part >> (PART_PRECISION / 2))
  30
  31 struct op
  32 {
  33   cpp_num value;                /* The value logically "right" of op.  */
  34   enum cpp_ttype op;
  35 };
  36
  37 /* Some simple utility routines on double integers.  */
  38 #define num_zerop(num) ((num.low | num.high) == 0)
  39 #define num_eq(num1, num2) (num1.low == num2.low && num1.high == num2.high)
  40 static bool num_positive PARAMS ((cpp_num, size_t));
  41 static bool num_greater_eq PARAMS ((cpp_num, cpp_num, size_t));
  42 static cpp_num num_trim PARAMS ((cpp_num, size_t));
  43 static cpp_num num_part_mul PARAMS ((cpp_num_part, cpp_num_part));
  44
  45 static cpp_num num_unary_op PARAMS ((cpp_reader *, cpp_num, enum cpp_ttype));
  46 static cpp_num num_binary_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
  47                                       enum cpp_ttype));
  48 static cpp_num num_negate PARAMS ((cpp_num, size_t));
  49 static cpp_num num_bitwise_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
  50                                        enum cpp_ttype));
  51 static cpp_num num_inequality_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
  52                                           enum cpp_ttype));
  53 static cpp_num num_equality_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
  54                                         enum cpp_ttype));
  55 static cpp_num num_mul PARAMS ((cpp_reader *, cpp_num, cpp_num));
  56 static cpp_num num_div_op PARAMS ((cpp_reader *, cpp_num, cpp_num,
  57                                    enum cpp_ttype));
  58 static cpp_num num_lshift PARAMS ((cpp_num, size_t, size_t));
  59 static cpp_num num_rshift PARAMS ((cpp_num, size_t, size_t));
  60
  61 static cpp_num append_digit PARAMS ((cpp_num, int, int, size_t));
  62 static cpp_num parse_defined PARAMS ((cpp_reader *));
  63 static cpp_num eval_token PARAMS ((cpp_reader *, const cpp_token *));
  64 static struct op *reduce PARAMS ((cpp_reader *, struct op *, enum cpp_ttype));
  65 static unsigned int interpret_float_suffix PARAMS ((const uchar *, size_t));
  66 static unsigned int interpret_int_suffix PARAMS ((const uchar *, size_t));
  67
  68 /* Token type abuse to create unary plus and minus operators.  */
  69 #define CPP_UPLUS (CPP_LAST_CPP_OP + 1)
  70 #define CPP_UMINUS (CPP_LAST_CPP_OP + 2)
  71
  72 /* With -O2, gcc appears to produce nice code, moving the error
  73    message load and subsequent jump completely out of the main path.  */
  74 #define SYNTAX_ERROR(msgid) \
  75   do { cpp_error (pfile, DL_ERROR, msgid); goto syntax_error; } while(0)
  76 #define SYNTAX_ERROR2(msgid, arg) \
  77   do { cpp_error (pfile, DL_ERROR, msgid, arg); goto syntax_error; } while(0)
  78
  79 /* Subroutine of cpp_classify_number.  S points to a float suffix of
  80    length LEN, possibly zero.  Returns 0 for an invalid suffix, or a
  81    flag vector describing the suffix.  */
  82 static unsigned int
  83 interpret_float_suffix (s, len)
  84      const uchar *s;
  85      size_t len;
  86 {
  87   size_t f = 0, l = 0, i = 0;
  88
  89   while (len--)
  90     switch (s[len])
  91       {
  92       case 'f': case 'F': f++; break;
  93       case 'l': case 'L': l++; break;
  94       case 'i': case 'I':
  95       case 'j': case 'J': i++; break;
  96       default:
  97         return 0;
  98       }
  99
 100   if (f + l > 1 || i > 1)
 101     return 0;
 102
 103   return ((i ? CPP_N_IMAGINARY : 0)
 104           | (f ? CPP_N_SMALL :
 105              l ? CPP_N_LARGE : CPP_N_MEDIUM));
 106 }
 107
 108 /* Subroutine of cpp_classify_number.  S points to an integer suffix
 109    of length LEN, possibly zero. Returns 0 for an invalid suffix, or a
 110    flag vector describing the suffix.  */
 111 static unsigned int
 112 interpret_int_suffix (s, len)
 113      const uchar *s;
 114      size_t len;
 115 {
 116   size_t u, l, i;
 117
 118   u = l = i = 0;
 119
 120   while (len--)
 121     switch (s[len])
 122       {
 123       case 'u': case 'U':       u++; break;
 124       case 'i': case 'I':
 125       case 'j': case 'J':       i++; break;
 126       case 'l': case 'L':       l++;
 127         /* If there are two Ls, they must be adjacent and the same case.  */
 128         if (l == 2 && s[len] != s[len + 1])
 129           return 0;
 130         break;
 131       default:
 132         return 0;
 133       }
 134
 135   if (l > 2 || u > 1 || i > 1)
 136     return 0;
 137
 138   return ((i ? CPP_N_IMAGINARY : 0)
 139           | (u ? CPP_N_UNSIGNED : 0)
 140           | ((l == 0) ? CPP_N_SMALL
 141              : (l == 1) ? CPP_N_MEDIUM : CPP_N_LARGE));
 142 }
 143
 144 /* Categorize numeric constants according to their field (integer,
 145    floating point, or invalid), radix (decimal, octal, hexadecimal),
 146    and type suffixes.  */
 147 unsigned int
 148 cpp_classify_number (pfile, token)
 149      cpp_reader *pfile;
 150      const cpp_token *token;
 151 {
 152   const uchar *str = token->val.str.text;
 153   const uchar *limit;
 154   unsigned int max_digit, result, radix;
 155   enum {NOT_FLOAT = 0, AFTER_POINT, AFTER_EXPON} float_flag;
 156
 157   /* If the lexer has done its job, length one can only be a single
 158      digit.  Fast-path this very common case.  */
 159   if (token->val.str.len == 1)
 160     return CPP_N_INTEGER | CPP_N_SMALL | CPP_N_DECIMAL;
 161
 162   limit = str + token->val.str.len;
 163   float_flag = NOT_FLOAT;
 164   max_digit = 0;
 165   radix = 10;
 166
 167   /* First, interpret the radix.  */
 168   if (*str == '0')
 169     {
 170       radix = 8;
 171       str++;
 172
 173       /* Require at least one hex digit to classify it as hex.  */
 174       if ((*str == 'x' || *str == 'X') && ISXDIGIT (str[1]))
 175         {
 176           radix = 16;
 177           str++;
 178         }
 179     }
 180
 181   /* Now scan for a well-formed integer or float.  */
 182   for (;;)
 183     {
 184       unsigned int c = *str++;
 185
 186       if (ISDIGIT (c) || (ISXDIGIT (c) && radix == 16))
 187         {
 188           c = hex_value (c);
 189           if (c > max_digit)
 190             max_digit = c;
 191         }
 192       else if (c == '.')
 193         {
 194           if (float_flag == NOT_FLOAT)
 195             float_flag = AFTER_POINT;
 196           else
 197             SYNTAX_ERROR ("too many decimal points in number");
 198         }
 199       else if ((radix <= 10 && (c == 'e' || c == 'E'))
 200                || (radix == 16 && (c == 'p' || c == 'P')))
 201         {
 202           float_flag = AFTER_EXPON;
 203           break;
 204         }
 205       else
 206         {
 207           /* Start of suffix.  */
 208           str--;
 209           break;
 210         }
 211     }
 212
 213   if (float_flag != NOT_FLOAT && radix == 8)
 214     radix = 10;
 215
 216   if (max_digit >= radix)
 217     SYNTAX_ERROR2 ("invalid digit \"%c\" in octal constant", '0' + max_digit);
 218
 219   if (float_flag != NOT_FLOAT)
 220     {
 221       if (radix == 16 && CPP_PEDANTIC (pfile) && !CPP_OPTION (pfile, c99))
 222         cpp_error (pfile, DL_PEDWARN,
 223                    "use of C99 hexadecimal floating constant");
 224
 225       if (float_flag == AFTER_EXPON)
 226         {
 227           if (*str == '+' || *str == '-')
 228             str++;
 229
 230           /* Exponent is decimal, even if string is a hex float.  */
 231           if (!ISDIGIT (*str))
 232             SYNTAX_ERROR ("exponent has no digits");
 233
 234           do
 235             str++;
 236           while (ISDIGIT (*str));
 237         }
 238       else if (radix == 16)
 239         SYNTAX_ERROR ("hexadecimal floating constants require an exponent");
 240
 241       result = interpret_float_suffix (str, limit - str);
 242       if (result == 0)
 243         {
 244           cpp_error (pfile, DL_ERROR,
 245                      "invalid suffix \"%.*s\" on floating constant",
 246                      (int) (limit - str), str);
 247           return CPP_N_INVALID;
 248         }
 249
 250       /* Traditional C didn't accept any floating suffixes.  */
 251       if (limit != str
 252           && CPP_WTRADITIONAL (pfile)
 253           && ! cpp_sys_macro_p (pfile))
 254         cpp_error (pfile, DL_WARNING,
 255                    "traditional C rejects the \"%.*s\" suffix",
 256                    (int) (limit - str), str);
 257
 258       result |= CPP_N_FLOATING;
 259     }
 260   else
 261     {
 262       result = interpret_int_suffix (str, limit - str);
 263       if (result == 0)
 264         {
 265           cpp_error (pfile, DL_ERROR,
 266                      "invalid suffix \"%.*s\" on integer constant",
 267                      (int) (limit - str), str);
 268           return CPP_N_INVALID;
 269         }
 270
 271       /* Traditional C only accepted the 'L' suffix.  */
 272       if (result != CPP_N_SMALL && result != CPP_N_MEDIUM
 273           && CPP_WTRADITIONAL (pfile)
 274           && ! cpp_sys_macro_p (pfile))
 275         cpp_error (pfile, DL_WARNING,
 276                    "traditional C rejects the \"%.*s\" suffix",
 277                    (int) (limit - str), str);
 278
 279       if ((result & CPP_N_WIDTH) == CPP_N_LARGE
 280           && ! CPP_OPTION (pfile, c99)
 281           && CPP_OPTION (pfile, warn_long_long))
 282         cpp_error (pfile, DL_PEDWARN, "use of C99 long long integer constant");
 283
 284       result |= CPP_N_INTEGER;
 285     }
 286
 287   if ((result & CPP_N_IMAGINARY) && CPP_PEDANTIC (pfile))
 288     cpp_error (pfile, DL_PEDWARN, "imaginary constants are a GCC extension");
 289
 290   if (radix == 10)
 291     result |= CPP_N_DECIMAL;
 292   else if (radix == 16)
 293     result |= CPP_N_HEX;
 294   else
 295     result |= CPP_N_OCTAL;
 296
 297   return result;
 298
 299  syntax_error:
 300   return CPP_N_INVALID;
 301 }
 302
 303 /* cpp_interpret_integer converts an integer constant into a cpp_num,
 304    of precision options->precision.
 305
 306    We do not provide any interface for decimal->float conversion,
 307    because the preprocessor doesn't need it and the floating point
 308    handling in GCC proper is too ugly to speak of.  */
 309 cpp_num
 310 cpp_interpret_integer (pfile, token, type)
 311      cpp_reader *pfile;
 312      const cpp_token *token;
 313      unsigned int type;
 314 {
 315   const uchar *p, *end;
 316   cpp_num result;
 317
 318   result.low = 0;
 319   result.high = 0;
 320   result.unsignedp = !!(type & CPP_N_UNSIGNED);
 321   result.overflow = false;
 322
 323   p = token->val.str.text;
 324   end = p + token->val.str.len;
 325
 326   /* Common case of a single digit.  */
 327   if (token->val.str.len == 1)
 328     result.low = p[0] - '0';
 329   else
 330     {
 331       cpp_num_part max;
 332       size_t precision = CPP_OPTION (pfile, precision);
 333       unsigned int base = 10, c = 0;
 334       bool overflow = false;
 335
 336       if ((type & CPP_N_RADIX) == CPP_N_OCTAL)
 337         {
 338           base = 8;
 339           p++;
 340         }
 341       else if ((type & CPP_N_RADIX) == CPP_N_HEX)
 342         {
 343           base = 16;
 344           p += 2;
 345         }
 346
 347       /* We can add a digit to numbers strictly less than this without
 348          needing the precision and slowness of double integers.  */
 349       max = ~(cpp_num_part) 0;
 350       if (precision < PART_PRECISION)
 351         max >>= PART_PRECISION - precision;
 352       max = (max - base + 1) / base + 1;
 353
 354       for (; p < end; p++)
 355         {
 356           c = *p;
 357
 358           if (ISDIGIT (c) || (base == 16 && ISXDIGIT (c)))
 359             c = hex_value (c);
 360           else
 361             break;
 362
 363           /* Strict inequality for when max is set to zero.  */
 364           if (result.low < max)
 365             result.low = result.low * base + c;
 366           else
 367             {
 368               result = append_digit (result, c, base, precision);
 369               overflow |= result.overflow;
 370               max = 0;
 371             }
 372         }
 373
 374       if (overflow)
 375         cpp_error (pfile, DL_PEDWARN,
 376                    "integer constant is too large for its type");
 377       /* If too big to be signed, consider it unsigned.  Only warn for
 378          decimal numbers.  Traditional numbers were always signed (but
 379          we still honour an explicit U suffix); but we only have
 380          traditional semantics in directives.  */
 381       else if (!result.unsignedp
 382                && !(CPP_OPTION (pfile, traditional)
 383                     && pfile->state.in_directive)
 384                && !num_positive (result, precision))
 385         {
 386           if (base == 10)
 387             cpp_error (pfile, DL_WARNING,
 388                        "integer constant is so large that it is unsigned");
 389           result.unsignedp = true;
 390         }
 391     }
 392
 393   return result;
 394 }
 395
 396 /* Append DIGIT to NUM, a number of PRECISION bits being read in base
 397    BASE.  */
 398 static cpp_num
 399 append_digit (num, digit, base, precision)
 400      cpp_num num;
 401      int digit, base;
 402      size_t precision;
 403 {
 404   cpp_num result;
 405   unsigned int shift = 3 + (base == 16);
 406   bool overflow;
 407   cpp_num_part add_high, add_low;
 408
 409   /* Multiply by 8 or 16.  Catching this overflow here means we don't
 410      need to worry about add_high overflowing.  */
 411   overflow = !!(num.high >> (PART_PRECISION - shift));
 412   result.high = num.high << shift;
 413   result.low = num.low << shift;
 414   result.high |= num.low >> (PART_PRECISION - shift);
 415
 416   if (base == 10)
 417     {
 418       add_low = num.low << 1;
 419       add_high = (num.high << 1) + (num.low >> (PART_PRECISION - 1));
 420     }
 421   else
 422     add_high = add_low = 0;
 423
 424   if (add_low + digit < add_low)
 425     add_high++;
 426   add_low += digit;
 427
 428   if (result.low + add_low < result.low)
 429     add_high++;
 430   if (result.high + add_high < result.high)
 431     overflow = true;
 432
 433   result.low += add_low;
 434   result.high += add_high;
 435
 436   /* The above code catches overflow of a cpp_num type.  This catches
 437      overflow of the (possibly shorter) target precision.  */
 438   num.low = result.low;
 439   num.high = result.high;
 440   result = num_trim (result, precision);
 441   if (!num_eq (result, num))
 442     overflow = true;
 443
 444   result.unsignedp = num.unsignedp;
 445   result.overflow = overflow;
 446   return result;
 447 }
 448
 449 /* Handle meeting "defined" in a preprocessor expression.  */
 450 static cpp_num
 451 parse_defined (pfile)
 452      cpp_reader *pfile;
 453 {
 454   cpp_num result;
 455   int paren = 0;
 456   cpp_hashnode *node = 0;
 457   const cpp_token *token;
 458   cpp_context *initial_context = pfile->context;
 459
 460   /* Don't expand macros.  */
 461   pfile->state.prevent_expansion++;
 462
 463   token = cpp_get_token (pfile);
 464   if (token->type == CPP_OPEN_PAREN)
 465     {
 466       paren = 1;
 467       token = cpp_get_token (pfile);
 468     }
 469
 470   if (token->type == CPP_NAME)
 471     {
 472       node = token->val.node;
 473       if (paren && cpp_get_token (pfile)->type != CPP_CLOSE_PAREN)
 474         {
 475           cpp_error (pfile, DL_ERROR, "missing ')' after \"defined\"");
 476           node = 0;
 477         }
 478     }
 479   else
 480     {
 481       cpp_error (pfile, DL_ERROR,
 482                  "operator \"defined\" requires an identifier");
 483       if (token->flags & NAMED_OP)
 484         {
 485           cpp_token op;
 486
 487           op.flags = 0;
 488           op.type = token->type;
 489           cpp_error (pfile, DL_ERROR,
 490                      "(\"%s\" is an alternative token for \"%s\" in C++)",
 491                      cpp_token_as_text (pfile, token),
 492                      cpp_token_as_text (pfile, &op));
 493         }
 494     }
 495
 496   if (node)
 497     {
 498       if (pfile->context != initial_context)
 499         cpp_error (pfile, DL_WARNING,
 500                    "this use of \"defined\" may not be portable");
 501
 502       /* A possible controlling macro of the form #if !defined ().
 503          _cpp_parse_expr checks there was no other junk on the line.  */
 504       pfile->mi_ind_cmacro = node;
 505     }
 506
 507   pfile->state.prevent_expansion--;
 508
 509   result.unsignedp = false;
 510   result.high = 0;
 511   result.overflow = false;
 512   result.low = node && node->type == NT_MACRO;
 513   return result;
 514 }
 515
 516 /* Convert a token into a CPP_NUMBER (an interpreted preprocessing
 517    number or character constant, or the result of the "defined" or "#"
 518    operators).  */
 519 static cpp_num
 520 eval_token (pfile, token)
 521      cpp_reader *pfile;
 522      const cpp_token *token;
 523 {
 524   cpp_num result;
 525   unsigned int temp;
 526   int unsignedp = 0;
 527
 528   switch (token->type)
 529     {
 530     case CPP_NUMBER:
 531       temp = cpp_classify_number (pfile, token);
 532       switch (temp & CPP_N_CATEGORY)
 533         {
 534         case CPP_N_FLOATING:
 535           cpp_error (pfile, DL_ERROR,
 536                      "floating constant in preprocessor expression");
 537           break;
 538         case CPP_N_INTEGER:
 539           if (!(temp & CPP_N_IMAGINARY))
 540             return cpp_interpret_integer (pfile, token, temp);
 541           cpp_error (pfile, DL_ERROR,
 542                      "imaginary number in preprocessor expression");
 543           break;
 544
 545         case CPP_N_INVALID:
 546           /* Error already issued.  */
 547           break;
 548         }
 549       result.high = result.low = 0;
 550       break;
 551
 552     case CPP_WCHAR:
 553     case CPP_CHAR:
 554       {
 555         cppchar_t cc = cpp_interpret_charconst (pfile, token,
 556                                                 &temp, &unsignedp);
 557
 558         result.high = 0;
 559         result.low = cc;
 560         /* Sign-extend the result if necessary.  */
 561         if (!unsignedp && (cppchar_signed_t) cc < 0)
 562           {
 563             if (PART_PRECISION > BITS_PER_CPPCHAR_T)
 564               result.low |= ~(~(cpp_num_part) 0
 565                               >> (PART_PRECISION - BITS_PER_CPPCHAR_T));
 566             result.high = ~(cpp_num_part) 0;
 567             result = num_trim (result, CPP_OPTION (pfile, precision));
 568           }
 569       }
 570       break;
 571
 572     case CPP_NAME:
 573       if (token->val.node == pfile->spec_nodes.n_defined)
 574         return parse_defined (pfile);
 575       else if (CPP_OPTION (pfile, cplusplus)
 576                && (token->val.node == pfile->spec_nodes.n_true
 577                    || token->val.node == pfile->spec_nodes.n_false))
 578         {
 579           result.high = 0;
 580           result.low = (token->val.node == pfile->spec_nodes.n_true);
 581
 582           /* Warn about use of true or false in #if when pedantic
 583              and stdbool.h has not been included.  */
 584           if (CPP_PEDANTIC (pfile)
 585               && ! cpp_defined (pfile, DSC("__bool_true_false_are_defined")))
 586             cpp_error (pfile, DL_PEDWARN,
 587                        "ISO C++ does not permit \"%s\" in #if",
 588                        NODE_NAME (token->val.node));
 589         }
 590       else
 591         {
 592           result.high = 0;
 593           result.low = 0;
 594           if (CPP_OPTION (pfile, warn_undef) && !pfile->state.skip_eval)
 595             cpp_error (pfile, DL_WARNING, "\"%s\" is not defined",
 596                        NODE_NAME (token->val.node));
 597         }
 598       break;
 599
 600     default: /* CPP_HASH */
 601       _cpp_test_assertion (pfile, &temp);
 602       result.high = 0;
 603       result.low = temp;
 604     }
 605
 606   result.unsignedp = !!unsignedp;
 607   result.overflow = false;
 608   return result;
 609 }
 610 \f
 611 /* Operator precedence and flags table.
 612
 613 After an operator is returned from the lexer, if it has priority less
 614 than the operator on the top of the stack, we reduce the stack by one
 615 operator and repeat the test.  Since equal priorities do not reduce,
 616 this is naturally right-associative.
 617
 618 We handle left-associative operators by decrementing the priority of
 619 just-lexed operators by one, but retaining the priority of operators
 620 already on the stack.
 621
 622 The remaining cases are '(' and ')'.  We handle '(' by skipping the
 623 reduction phase completely.  ')' is given lower priority than
 624 everything else, including '(', effectively forcing a reduction of the
 625 parenthesised expression.  If there is a matching '(', the routine
 626 reduce() exits immediately.  If the normal exit route sees a ')', then
 627 there cannot have been a matching '(' and an error message is output.
 628
 629 The parser assumes all shifted operators require a left operand unless
 630 the flag NO_L_OPERAND is set.  These semantics are automatic; any
 631 extra semantics need to be handled with operator-specific code.  */
 632
 633 /* Flags.  ALWAYS_EVAL is for operators that should be evaluated even
 634    if skip_eval is true; perhaps they are invalid and require a
 635    diagnostic, or they might modify skip_eval.  */
 636 #define NO_L_OPERAND    (1 << 0)
 637 #define LEFT_ASSOC      (1 << 1)
 638 #define ALWAYS_EVAL     (1 << 2)
 639
 640 /* Operator to priority map.  Must be in the same order as the first
 641    N entries of enum cpp_ttype.  */
 642 static const struct operator
 643 {
 644   uchar prio;
 645   uchar flags;
 646 } optab[] =
 647 {
 648   /* EQ */              {0, 0}, /* Shouldn't happen.  */
 649   /* NOT */             {16, NO_L_OPERAND},
 650   /* GREATER */         {12, LEFT_ASSOC},
 651   /* LESS */            {12, LEFT_ASSOC},
 652   /* PLUS */            {14, LEFT_ASSOC},
 653   /* MINUS */           {14, LEFT_ASSOC},
 654   /* MULT */            {15, LEFT_ASSOC},
 655   /* DIV */             {15, LEFT_ASSOC},
 656   /* MOD */             {15, LEFT_ASSOC},
 657   /* AND */             {9, LEFT_ASSOC},
 658   /* OR */              {7, LEFT_ASSOC},
 659   /* XOR */             {8, LEFT_ASSOC},
 660   /* RSHIFT */          {13, LEFT_ASSOC},
 661   /* LSHIFT */          {13, LEFT_ASSOC},
 662
 663   /* MIN */             {10, LEFT_ASSOC},
 664   /* MAX */             {10, LEFT_ASSOC},
 665
 666   /* COMPL */           {16, NO_L_OPERAND},
 667   /* AND_AND */         {6, LEFT_ASSOC | ALWAYS_EVAL},
 668   /* OR_OR */           {5, LEFT_ASSOC | ALWAYS_EVAL},
 669   /* QUERY */           {3, ALWAYS_EVAL},
 670   /* COLON */           {4, LEFT_ASSOC | ALWAYS_EVAL},
 671   /* COMMA */           {2, LEFT_ASSOC},
 672   /* OPEN_PAREN */      {1, NO_L_OPERAND | ALWAYS_EVAL},
 673   /* CLOSE_PAREN */     {0, 0},
 674   /* EOF */             {0, 0},
 675   /* EQ_EQ */           {11, LEFT_ASSOC},
 676   /* NOT_EQ */          {11, LEFT_ASSOC},
 677   /* GREATER_EQ */      {12, LEFT_ASSOC},
 678   /* LESS_EQ */         {12, LEFT_ASSOC},
 679   /* UPLUS */           {16, NO_L_OPERAND},
 680   /* UMINUS */          {16, NO_L_OPERAND}
 681 };
 682
 683 /* Parse and evaluate a C expression, reading from PFILE.
 684    Returns the truth value of the expression.
 685
 686    The implementation is an operator precedence parser, i.e. a
 687    bottom-up parser, using a stack for not-yet-reduced tokens.
 688
 689    The stack base is op_stack, and the current stack pointer is 'top'.
 690    There is a stack element for each operator (only), and the most
 691    recently pushed operator is 'top->op'.  An operand (value) is
 692    stored in the 'value' field of the stack element of the operator
 693    that precedes it.  */
 694 bool
 695 _cpp_parse_expr (pfile)
 696      cpp_reader *pfile;
 697 {
 698   struct op *top = pfile->op_stack;
 699   const cpp_token *token = NULL, *prev_token;
 700   unsigned int lex_count;
 701   bool saw_leading_not, want_value = true;
 702
 703   pfile->state.skip_eval = 0;
 704
 705   /* Set up detection of #if ! defined().  */
 706   pfile->mi_ind_cmacro = 0;
 707   saw_leading_not = false;
 708   lex_count = 0;
 709
 710   /* Lowest priority operator prevents further reductions.  */
 711   top->op = CPP_EOF;
 712
 713   for (;;)
 714     {
 715       struct op op;
 716
 717       prev_token = token;
 718       token = cpp_get_token (pfile);
 719       lex_count++;
 720       op.op = token->type;
 721
 722       switch (op.op)
 723         {
 724           /* These tokens convert into values.  */
 725         case CPP_NUMBER:
 726         case CPP_CHAR:
 727         case CPP_WCHAR:
 728         case CPP_NAME:
 729         case CPP_HASH:
 730           if (!want_value)
 731             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
 732                            cpp_token_as_text (pfile, token));
 733           want_value = false;
 734           top->value = eval_token (pfile, token);
 735           continue;
 736
 737         case CPP_NOT:
 738           saw_leading_not = lex_count == 1;
 739           break;
 740         case CPP_PLUS:
 741           if (want_value)
 742             op.op = CPP_UPLUS;
 743           break;
 744         case CPP_MINUS:
 745           if (want_value)
 746             op.op = CPP_UMINUS;
 747           break;
 748         case CPP_OTHER:
 749           if (ISGRAPH (token->val.c))
 750             SYNTAX_ERROR2 ("invalid character '%c' in #if", token->val.c);
 751           else
 752             SYNTAX_ERROR2 ("invalid character '\\%03o' in #if", token->val.c);
 753
 754         default:
 755           if ((int) op.op <= (int) CPP_EQ || (int) op.op >= (int) CPP_PLUS_EQ)
 756             SYNTAX_ERROR2 ("token \"%s\" is not valid in preprocessor expressions",
 757                            cpp_token_as_text (pfile, token));
 758           break;
 759         }
 760
 761       /* Check we have a value or operator as appropriate.  */
 762       if (optab[op.op].flags & NO_L_OPERAND)
 763         {
 764           if (!want_value)
 765             SYNTAX_ERROR2 ("missing binary operator before token \"%s\"",
 766                            cpp_token_as_text (pfile, token));
 767         }
 768       else if (want_value)
 769         {
 770           /* Ordering here is subtle and intended to favour the
 771              missing parenthesis diagnostics over alternatives.  */
 772           if (op.op == CPP_CLOSE_PAREN)
 773             {
 774               if (top->op == CPP_OPEN_PAREN)
 775                 SYNTAX_ERROR ("void expression between '(' and ')'");
 776             }
 777           else if (top->op == CPP_EOF)
 778             SYNTAX_ERROR ("#if with no expression");
 779           if (top->op != CPP_EOF && top->op != CPP_OPEN_PAREN)
 780             SYNTAX_ERROR2 ("operator '%s' has no right operand",
 781                            cpp_token_as_text (pfile, prev_token));
 782         }
 783
 784       top = reduce (pfile, top, op.op);
 785       if (!top)
 786         goto syntax_error;
 787
 788       if (op.op == CPP_EOF)
 789         break;
 790
 791       switch (op.op)
 792         {
 793         case CPP_CLOSE_PAREN:
 794           continue;
 795         case CPP_OR_OR:
 796           if (!num_zerop (top->value))
 797             pfile->state.skip_eval++;
 798           break;
 799         case CPP_AND_AND:
 800         case CPP_QUERY:
 801           if (num_zerop (top->value))
 802             pfile->state.skip_eval++;
 803           break;
 804         case CPP_COLON:
 805           if (top->op != CPP_QUERY)
 806             SYNTAX_ERROR (" ':' without preceding '?'");
 807           if (!num_zerop (top[-1].value)) /* Was '?' condition true?  */
 808             pfile->state.skip_eval++;
 809           else
 810             pfile->state.skip_eval--;
 811         default:
 812           break;
 813         }
 814
 815       want_value = true;
 816
 817       /* Check for and handle stack overflow.  */
 818       if (++top == pfile->op_limit)
 819         top = _cpp_expand_op_stack (pfile);
 820
 821       top->op = op.op;
 822     }
 823
 824   /* The controlling macro expression is only valid if we called lex 3
 825      times: <!> <defined expression> and <EOF>.  push_conditional ()
 826      checks that we are at top-of-file.  */
 827   if (pfile->mi_ind_cmacro && !(saw_leading_not && lex_count == 3))
 828     pfile->mi_ind_cmacro = 0;
 829
 830   if (top != pfile->op_stack)
 831     {
 832       cpp_error (pfile, DL_ICE, "unbalanced stack in #if");
 833     syntax_error:
 834       return false;  /* Return false on syntax error.  */
 835     }
 836
 837   return !num_zerop (top->value);
 838 }
 839
 840 /* Reduce the operator / value stack if possible, in preparation for
 841    pushing operator OP.  Returns NULL on error, otherwise the top of
 842    the stack.  */
 843 static struct op *
 844 reduce (pfile, top, op)
 845      cpp_reader *pfile;
 846      struct op *top;
 847      enum cpp_ttype op;
 848 {
 849   unsigned int prio;
 850
 851   if (top->op <= CPP_EQ || top->op > CPP_LAST_CPP_OP + 2)
 852     {
 853     bad_op:
 854       cpp_error (pfile, DL_ICE, "impossible operator '%u'", top->op);
 855       return 0;
 856     }
 857
 858   if (op == CPP_OPEN_PAREN)
 859     return top;
 860
 861   /* Decrement the priority of left-associative operators to force a
 862      reduction with operators of otherwise equal priority.  */
 863   prio = optab[op].prio - ((optab[op].flags & LEFT_ASSOC) != 0);
 864   while (prio < optab[top->op].prio)
 865     {
 866       if (!pfile->state.skip_eval || optab[top->op].flags & ALWAYS_EVAL)
 867         switch (top->op)
 868           {
 869           case CPP_UPLUS:
 870           case CPP_UMINUS:
 871           case CPP_NOT:
 872           case CPP_COMPL:
 873             top[-1].value = num_unary_op (pfile, top->value, top->op);
 874             break;
 875
 876           case CPP_PLUS:
 877           case CPP_MINUS:
 878           case CPP_RSHIFT:
 879           case CPP_LSHIFT:
 880           case CPP_MIN:
 881           case CPP_MAX:
 882           case CPP_COMMA:
 883             top[-1].value = num_binary_op (pfile, top[-1].value,
 884                                            top->value, top->op);
 885             break;
 886
 887           case CPP_GREATER:
 888           case CPP_LESS:
 889           case CPP_GREATER_EQ:
 890           case CPP_LESS_EQ:
 891             top[-1].value
 892               = num_inequality_op (pfile, top[-1].value, top->value, top->op);
 893             break;
 894
 895           case CPP_EQ_EQ:
 896           case CPP_NOT_EQ:
 897             top[-1].value
 898               = num_equality_op (pfile, top[-1].value, top->value, top->op);
 899             break;
 900
 901           case CPP_AND:
 902           case CPP_OR:
 903           case CPP_XOR:
 904             top[-1].value
 905               = num_bitwise_op (pfile, top[-1].value, top->value, top->op);
 906             break;
 907
 908           case CPP_MULT:
 909             top[-1].value = num_mul (pfile, top[-1].value, top->value);
 910             break;
 911
 912           case CPP_DIV:
 913           case CPP_MOD:
 914             top[-1].value = num_div_op (pfile, top[-1].value,
 915                                         top->value, top->op);
 916             break;
 917
 918           case CPP_OR_OR:
 919             top--;
 920             if (!num_zerop (top->value))
 921               pfile->state.skip_eval--;
 922             top->value.low = (!num_zerop (top->value)
 923                               || !num_zerop (top[1].value));
 924             top->value.high = 0;
 925             top->value.unsignedp = false;
 926             top->value.overflow = false;
 927             continue;
 928
 929           case CPP_AND_AND:
 930             top--;
 931             if (num_zerop (top->value))
 932               pfile->state.skip_eval--;
 933             top->value.low = (!num_zerop (top->value)
 934                               && !num_zerop (top[1].value));
 935             top->value.high = 0;
 936             top->value.unsignedp = false;
 937             top->value.overflow = false;
 938             continue;
 939
 940           case CPP_OPEN_PAREN:
 941             if (op != CPP_CLOSE_PAREN)
 942               {
 943                 cpp_error (pfile, DL_ERROR, "missing ')' in expression");
 944                 return 0;
 945               }
 946             top--;
 947             top->value = top[1].value;
 948             return top;
 949
 950           case CPP_COLON:
 951             top -= 2;
 952             if (!num_zerop (top->value))
 953               {
 954                 pfile->state.skip_eval--;
 955                 top->value = top[1].value;
 956               }
 957             else
 958               top->value = top[2].value;
 959             top->value.unsignedp = (top[1].value.unsignedp
 960                                     || top[2].value.unsignedp);
 961             continue;
 962
 963           case CPP_QUERY:
 964             cpp_error (pfile, DL_ERROR, "'?' without following ':'");
 965             return 0;
 966
 967           default:
 968             goto bad_op;
 969           }
 970
 971       top--;
 972       if (top->value.overflow && !pfile->state.skip_eval)
 973         cpp_error (pfile, DL_PEDWARN,
 974                    "integer overflow in preprocessor expression");
 975     }
 976
 977   if (op == CPP_CLOSE_PAREN)
 978     {
 979       cpp_error (pfile, DL_ERROR, "missing '(' in expression");
 980       return 0;
 981     }
 982
 983   return top;
 984 }
 985
 986 /* Returns the position of the old top of stack after expansion.  */
 987 struct op *
 988 _cpp_expand_op_stack (pfile)
 989      cpp_reader *pfile;
 990 {
 991   size_t old_size = (size_t) (pfile->op_limit - pfile->op_stack);
 992   size_t new_size = old_size * 2 + 20;
 993
 994   pfile->op_stack = (struct op *) xrealloc (pfile->op_stack,
 995                                             new_size * sizeof (struct op));
 996   pfile->op_limit = pfile->op_stack + new_size;
 997
 998   return pfile->op_stack + old_size;
 999 }
1000
1001 /* Clears the unused high order bits of the number pointed to by PNUM.  */
1002 static cpp_num
1003 num_trim (num, precision)
1004      cpp_num num;
1005      size_t precision;
1006 {
1007   if (precision > PART_PRECISION)
1008     {
1009       precision -= PART_PRECISION;
1010       if (precision < PART_PRECISION)
1011         num.high &= ((cpp_num_part) 1 << precision) - 1;
1012     }
1013   else
1014     {
1015       if (precision < PART_PRECISION)
1016         num.low &= ((cpp_num_part) 1 << precision) - 1;
1017       num.high = 0;
1018     }
1019
1020   return num;
1021 }
1022
1023 /* True iff A (presumed signed) >= 0.  */
1024 static bool
1025 num_positive (num, precision)
1026      cpp_num num;
1027      size_t precision;
1028 {
1029   if (precision > PART_PRECISION)
1030     {
1031       precision -= PART_PRECISION;
1032       return (num.high & (cpp_num_part) 1 << (precision - 1)) == 0;
1033     }
1034
1035   return (num.low & (cpp_num_part) 1 << (precision - 1)) == 0;
1036 }
1037
1038 /* Sign extend a number, with PRECISION significant bits and all
1039    others assumed clear, to fill out a cpp_num structure.  */
1040 cpp_num
1041 cpp_num_sign_extend (num, precision)
1042      cpp_num num;
1043      size_t precision;
1044 {
1045   if (!num.unsignedp)
1046     {
1047       if (precision > PART_PRECISION)
1048         {
1049           precision -= PART_PRECISION;
1050           if (precision < PART_PRECISION
1051               && (num.high & (cpp_num_part) 1 << (precision - 1)))
1052             num.high |= ~(~(cpp_num_part) 0 >> (PART_PRECISION - precision));
1053         }
1054       else if (num.low & (cpp_num_part) 1 << (precision - 1))
1055         {
1056           if (precision < PART_PRECISION)
1057             num.low |= ~(~(cpp_num_part) 0 >> (PART_PRECISION - precision));
1058           num.high = ~(cpp_num_part) 0;
1059         }
1060     }
1061
1062   return num;
1063 }
1064
1065 /* Returns the negative of NUM.  */
1066 static cpp_num
1067 num_negate (num, precision)
1068      cpp_num num;
1069      size_t precision;
1070 {
1071   cpp_num copy;
1072
1073   copy = num;
1074   num.high = ~num.high;
1075   num.low = ~num.low;
1076   if (++num.low == 0)
1077     num.high++;
1078   num = num_trim (num, precision);
1079   num.overflow = (!num.unsignedp && num_eq (num, copy) && !num_zerop (num));
1080
1081   return num;
1082 }
1083
1084 /* Returns true if A >= B.  */
1085 static bool
1086 num_greater_eq (pa, pb, precision)
1087      cpp_num pa, pb;
1088      size_t precision;
1089 {
1090   bool unsignedp;
1091
1092   unsignedp = pa.unsignedp || pb.unsignedp;
1093
1094   if (!unsignedp)
1095     {
1096       /* Both numbers have signed type.  If they are of different
1097        sign, the answer is the sign of A.  */
1098       unsignedp = num_positive (pa, precision);
1099
1100       if (unsignedp != num_positive (pb, precision))
1101         return unsignedp;
1102
1103       /* Otherwise we can do an unsigned comparison.  */
1104     }
1105
1106   return (pa.high > pb.high) || (pa.high == pb.high && pa.low >= pb.low);
1107 }
1108
1109 /* Returns LHS OP RHS, where OP is a bit-wise operation.  */
1110 static cpp_num
1111 num_bitwise_op (pfile, lhs, rhs, op)
1112      cpp_reader *pfile ATTRIBUTE_UNUSED;
1113      cpp_num lhs, rhs;
1114      enum cpp_ttype op;
1115 {
1116   lhs.overflow = false;
1117   lhs.unsignedp = lhs.unsignedp || rhs.unsignedp;
1118
1119   /* As excess precision is zeroed, there is no need to num_trim () as
1120      these operations cannot introduce a set bit there.  */
1121   if (op == CPP_AND)
1122     {
1123       lhs.low &= rhs.low;
1124       lhs.high &= rhs.high;
1125     }
1126   else if (op == CPP_OR)
1127     {
1128       lhs.low |= rhs.low;
1129       lhs.high |= rhs.high;
1130     }
1131   else
1132     {
1133       lhs.low ^= rhs.low;
1134       lhs.high ^= rhs.high;
1135     }
1136
1137   return lhs;
1138 }
1139
1140 /* Returns LHS OP RHS, where OP is an inequality.  */
1141 static cpp_num
1142 num_inequality_op (pfile, lhs, rhs, op)
1143      cpp_reader *pfile;
1144      cpp_num lhs, rhs;
1145      enum cpp_ttype op;
1146 {
1147   bool gte = num_greater_eq (lhs, rhs, CPP_OPTION (pfile, precision));
1148
1149   if (op == CPP_GREATER_EQ)
1150     lhs.low = gte;
1151   else if (op == CPP_LESS)
1152     lhs.low = !gte;
1153   else if (op == CPP_GREATER)
1154     lhs.low = gte && !num_eq (lhs, rhs);
1155   else /* CPP_LESS_EQ.  */
1156     lhs.low = !gte || num_eq (lhs, rhs);
1157
1158   lhs.high = 0;
1159   lhs.overflow = false;
1160   lhs.unsignedp = false;
1161   return lhs;
1162 }
1163
1164 /* Returns LHS OP RHS, where OP is == or !=.  */
1165 static cpp_num
1166 num_equality_op (pfile, lhs, rhs, op)
1167      cpp_reader *pfile ATTRIBUTE_UNUSED;
1168      cpp_num lhs, rhs;
1169      enum cpp_ttype op;
1170 {
1171   /* Work around a 3.0.4 bug; see PR 6950.  */
1172   bool eq = num_eq (lhs, rhs);
1173   if (op == CPP_NOT_EQ)
1174     eq = !eq;
1175   lhs.low = eq;
1176   lhs.high = 0;
1177   lhs.overflow = false;
1178   lhs.unsignedp = false;
1179   return lhs;
1180 }
1181
1182 /* Shift NUM, of width PRECISION, right by N bits.  */
1183 static cpp_num
1184 num_rshift (num, precision, n)
1185      cpp_num num;
1186      size_t precision, n;
1187 {
1188   cpp_num_part sign_mask;
1189
1190   if (num.unsignedp || num_positive (num, precision))
1191     sign_mask = 0;
1192   else
1193     sign_mask = ~(cpp_num_part) 0;
1194
1195   if (n >= precision)
1196     num.high = num.low = sign_mask;
1197   else
1198     {
1199       /* Sign-extend.  */
1200       if (precision < PART_PRECISION)
1201         num.high = sign_mask, num.low |= sign_mask << precision;
1202       else if (precision < 2 * PART_PRECISION)
1203         num.high |= sign_mask << (precision - PART_PRECISION);
1204
1205       if (n >= PART_PRECISION)
1206         {
1207           n -= PART_PRECISION;
1208           num.low = num.high;
1209           num.high = sign_mask;
1210         }
1211
1212       if (n)
1213         {
1214           num.low = (num.low >> n) | (num.high << (PART_PRECISION - n));
1215           num.high = (num.high >> n) | (sign_mask << (PART_PRECISION - n));
1216         }
1217     }
1218
1219   num = num_trim (num, precision);
1220   num.overflow = false;
1221   return num;
1222 }
1223
1224 /* Shift NUM, of width PRECISION, left by N bits.  */
1225 static cpp_num
1226 num_lshift (num, precision, n)
1227      cpp_num num;
1228      size_t precision, n;
1229 {
1230   if (n >= precision)
1231     {
1232       num.overflow = !num.unsignedp && !num_zerop (num);
1233       num.high = num.low = 0;
1234     }
1235   else
1236     {
1237       cpp_num orig, maybe_orig;
1238       size_t m = n;
1239
1240       orig = num;
1241       if (m >= PART_PRECISION)
1242         {
1243           m -= PART_PRECISION;
1244           num.high = num.low;
1245           num.low = 0;
1246         }
1247       if (m)
1248         {
1249           num.high = (num.high << m) | (num.low >> (PART_PRECISION - m));
1250           num.low <<= m;
1251         }
1252       num = num_trim (num, precision);
1253
1254       if (num.unsignedp)
1255         num.overflow = false;
1256       else
1257         {
1258           maybe_orig = num_rshift (num, precision, n);
1259           num.overflow = !num_eq (orig, maybe_orig);
1260         }
1261     }
1262
1263   return num;
1264 }
1265
1266 /* The four unary operators: +, -, ! and ~.  */
1267 static cpp_num
1268 num_unary_op (pfile, num, op)
1269      cpp_reader *pfile;
1270      cpp_num num;
1271      enum cpp_ttype op;
1272 {
1273   switch (op)
1274     {
1275     case CPP_UPLUS:
1276       if (CPP_WTRADITIONAL (pfile))
1277         cpp_error (pfile, DL_WARNING,
1278                    "traditional C rejects the unary plus operator");
1279       num.overflow = false;
1280       break;
1281
1282     case CPP_UMINUS:
1283       num = num_negate (num, CPP_OPTION (pfile, precision));
1284       break;
1285
1286     case CPP_COMPL:
1287       num.high = ~num.high;
1288       num.low = ~num.low;
1289       num = num_trim (num, CPP_OPTION (pfile, precision));
1290       num.overflow = false;
1291       break;
1292
1293     default: /* case CPP_NOT: */
1294       num.low = num_zerop (num);
1295       num.high = 0;
1296       num.overflow = false;
1297       num.unsignedp = false;
1298       break;
1299     }
1300
1301   return num;
1302 }
1303
1304 /* The various binary operators.  */
1305 static cpp_num
1306 num_binary_op (pfile, lhs, rhs, op)
1307      cpp_reader *pfile;
1308      cpp_num lhs, rhs;
1309      enum cpp_ttype op;
1310 {
1311   cpp_num result;
1312   size_t precision = CPP_OPTION (pfile, precision);
1313   bool gte;
1314   size_t n;
1315
1316   switch (op)
1317     {
1318       /* Shifts.  */
1319     case CPP_LSHIFT:
1320     case CPP_RSHIFT:
1321       if (!rhs.unsignedp && !num_positive (rhs, precision))
1322         {
1323           /* A negative shift is a positive shift the other way.  */
1324           if (op == CPP_LSHIFT)
1325             op = CPP_RSHIFT;
1326           else
1327             op = CPP_LSHIFT;
1328           rhs = num_negate (rhs, precision);
1329         }
1330       if (rhs.high)
1331         n = ~0;                 /* Maximal.  */
1332       else
1333         n = rhs.low;
1334       if (op == CPP_LSHIFT)
1335         lhs = num_lshift (lhs, precision, n);
1336       else
1337         lhs = num_rshift (lhs, precision, n);
1338       break;
1339
1340       /* Min / Max.  */
1341     case CPP_MIN:
1342     case CPP_MAX:
1343       {
1344         bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1345
1346         gte = num_greater_eq (lhs, rhs, precision);
1347         if (op == CPP_MIN)
1348           gte = !gte;
1349         if (!gte)
1350           lhs = rhs;
1351         lhs.unsignedp = unsignedp;
1352       }
1353       break;
1354
1355       /* Arithmetic.  */
1356     case CPP_MINUS:
1357       rhs = num_negate (rhs, precision);
1358     case CPP_PLUS:
1359       result.low = lhs.low + rhs.low;
1360       result.high = lhs.high + rhs.high;
1361       if (result.low < lhs.low)
1362         result.high++;
1363
1364       result = num_trim (result, precision);
1365       result.unsignedp = lhs.unsignedp || rhs.unsignedp;
1366       if (result.unsignedp)
1367         result.overflow = false;
1368       else
1369         {
1370           bool lhsp = num_positive (lhs, precision);
1371           result.overflow = (lhsp == num_positive (rhs, precision)
1372                              && lhsp != num_positive (result, precision));
1373         }
1374       return result;
1375
1376       /* Comma.  */
1377     default: /* case CPP_COMMA: */
1378       if (CPP_PEDANTIC (pfile))
1379         cpp_error (pfile, DL_PEDWARN,
1380                    "comma operator in operand of #if");
1381       lhs = rhs;
1382       break;
1383     }
1384
1385   return lhs;
1386 }
1387
1388 /* Multiplies two unsigned cpp_num_parts to give a cpp_num.  This
1389    cannot overflow.  */
1390 static cpp_num
1391 num_part_mul (lhs, rhs)
1392      cpp_num_part lhs, rhs;
1393 {
1394   cpp_num result;
1395   cpp_num_part middle[2], temp;
1396
1397   result.low = LOW_PART (lhs) * LOW_PART (rhs);
1398   result.high = HIGH_PART (lhs) * HIGH_PART (rhs);
1399
1400   middle[0] = LOW_PART (lhs) * HIGH_PART (rhs);
1401   middle[1] = HIGH_PART (lhs) * LOW_PART (rhs);
1402
1403   temp = result.low;
1404   result.low += LOW_PART (middle[0]) << (PART_PRECISION / 2);
1405   if (result.low < temp)
1406     result.high++;
1407
1408   temp = result.low;
1409   result.low += LOW_PART (middle[1]) << (PART_PRECISION / 2);
1410   if (result.low < temp)
1411     result.high++;
1412
1413   result.high += HIGH_PART (middle[0]);
1414   result.high += HIGH_PART (middle[1]);
1415
1416   return result;
1417 }
1418
1419 /* Multiply two preprocessing numbers.  */
1420 static cpp_num
1421 num_mul (pfile, lhs, rhs)
1422      cpp_reader *pfile;
1423      cpp_num lhs, rhs;
1424 {
1425   cpp_num result, temp;
1426   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1427   bool overflow, negate = false;
1428   size_t precision = CPP_OPTION (pfile, precision);
1429
1430   /* Prepare for unsigned multiplication.  */
1431   if (!unsignedp)
1432     {
1433       if (!num_positive (lhs, precision))
1434         negate = !negate, lhs = num_negate (lhs, precision);
1435       if (!num_positive (rhs, precision))
1436         negate = !negate, rhs = num_negate (rhs, precision);
1437     }
1438
1439   overflow = lhs.high && rhs.high;
1440   result = num_part_mul (lhs.low, rhs.low);
1441
1442   temp = num_part_mul (lhs.high, rhs.low);
1443   result.high += temp.low;
1444   if (temp.high)
1445     overflow = true;
1446
1447   temp = num_part_mul (lhs.low, rhs.high);
1448   result.high += temp.low;
1449   if (temp.high)
1450     overflow = true;
1451
1452   temp.low = result.low, temp.high = result.high;
1453   result = num_trim (result, precision);
1454   if (!num_eq (result, temp))
1455     overflow = true;
1456
1457   if (negate)
1458     result = num_negate (result, precision);
1459
1460   if (unsignedp)
1461     result.overflow = false;
1462   else
1463     result.overflow = overflow || (num_positive (result, precision) ^ !negate
1464                                    && !num_zerop (result));
1465   result.unsignedp = unsignedp;
1466
1467   return result;
1468 }
1469
1470 /* Divide two preprocessing numbers, returning the answer or the
1471    remainder depending upon OP.  */
1472 static cpp_num
1473 num_div_op (pfile, lhs, rhs, op)
1474      cpp_reader *pfile;
1475      cpp_num lhs, rhs;
1476      enum cpp_ttype op;
1477 {
1478   cpp_num result, sub;
1479   cpp_num_part mask;
1480   bool unsignedp = lhs.unsignedp || rhs.unsignedp;
1481   bool negate = false, lhs_neg = false;
1482   size_t i, precision = CPP_OPTION (pfile, precision);
1483
1484   /* Prepare for unsigned division.  */
1485   if (!unsignedp)
1486     {
1487       if (!num_positive (lhs, precision))
1488         negate = !negate, lhs_neg = true, lhs = num_negate (lhs, precision);
1489       if (!num_positive (rhs, precision))
1490         negate = !negate, rhs = num_negate (rhs, precision);
1491     }
1492
1493   /* Find the high bit.  */
1494   if (rhs.high)
1495     {
1496       i = precision - 1;
1497       mask = (cpp_num_part) 1 << (i - PART_PRECISION);
1498       for (; ; i--, mask >>= 1)
1499         if (rhs.high & mask)
1500           break;
1501     }
1502   else if (rhs.low)
1503     {
1504       if (precision > PART_PRECISION)
1505         i = precision - PART_PRECISION - 1;
1506       else
1507         i = precision - 1;
1508       mask = (cpp_num_part) 1 << i;
1509       for (; ; i--, mask >>= 1)
1510         if (rhs.low & mask)
1511           break;
1512     }
1513   else
1514     {
1515       cpp_error (pfile, DL_ERROR, "division by zero in #if");
1516       return lhs;
1517     }
1518
1519   /* First non-zero bit of RHS is bit I.  Do naive division by
1520      shifting the RHS fully left, and subtracting from LHS if LHS is
1521      at least as big, and then repeating but with one less shift.
1522      This is not very efficient, but is easy to understand.  */
1523
1524   rhs.unsignedp = true;
1525   lhs.unsignedp = true;
1526   i = precision - i - 1;
1527   sub = num_lshift (rhs, precision, i);
1528
1529   result.high = result.low = 0;
1530   for (;;)
1531     {
1532       if (num_greater_eq (lhs, sub, precision))
1533         {
1534           lhs = num_binary_op (pfile, lhs, sub, CPP_MINUS);
1535           if (i >= PART_PRECISION)
1536             result.high |= (cpp_num_part) 1 << (i - PART_PRECISION);
1537           else
1538             result.low |= (cpp_num_part) 1 << i;
1539         }
1540       if (i-- == 0)
1541         break;
1542       sub.low = (sub.low >> 1) | (sub.high << (PART_PRECISION - 1));
1543       sub.high >>= 1;
1544     }
1545
1546   /* We divide so that the remainder has the sign of the LHS.  */
1547   if (op == CPP_DIV)
1548     {
1549       result.unsignedp = unsignedp;
1550       if (unsignedp)
1551         result.overflow = false;
1552       else
1553         {
1554           if (negate)
1555             result = num_negate (result, precision);
1556           result.overflow = num_positive (result, precision) ^ !negate;
1557         }
1558
1559       return result;
1560     }
1561
1562   /* CPP_MOD.  */
1563   lhs.unsignedp = unsignedp;
1564   lhs.overflow = false;
1565   if (lhs_neg)
1566     lhs = num_negate (lhs, precision);
1567
1568   return lhs;
1569 }