shell/math.c

   1 /*
   2  * arithmetic code ripped out of ash shell for code sharing
   3  *
   4  * This code is derived from software contributed to Berkeley by
   5  * Kenneth Almquist.
   6  *
   7  * Original BSD copyright notice is retained at the end of this file.
   8  *
   9  * Copyright (c) 1989, 1991, 1993, 1994
  10  *      The Regents of the University of California.  All rights reserved.
  11  *
  12  * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
  13  * was re-ported from NetBSD and debianized.
  14  *
  15  * rewrite arith.y to micro stack based cryptic algorithm by
  16  * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  17  *
  18  * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support
  19  * dynamic variables.
  20  *
  21  * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be
  22  * used in busybox and size optimizations,
  23  * rewrote arith (see notes to this), added locale support,
  24  * rewrote dynamic variables.
  25  *
  26  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  27  */
  28 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  29
  30    Permission is hereby granted, free of charge, to any person obtaining
  31    a copy of this software and associated documentation files (the
  32    "Software"), to deal in the Software without restriction, including
  33    without limitation the rights to use, copy, modify, merge, publish,
  34    distribute, sublicense, and/or sell copies of the Software, and to
  35    permit persons to whom the Software is furnished to do so, subject to
  36    the following conditions:
  37
  38    The above copyright notice and this permission notice shall be
  39    included in all copies or substantial portions of the Software.
  40
  41    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  42    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  43    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  44    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  45    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  46    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  47    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  48 */
  49
  50 /* This is my infix parser/evaluator. It is optimized for size, intended
  51  * as a replacement for yacc-based parsers. However, it may well be faster
  52  * than a comparable parser written in yacc. The supported operators are
  53  * listed in #defines below. Parens, order of operations, and error handling
  54  * are supported. This code is thread safe. The exact expression format should
  55  * be that which POSIX specifies for shells.
  56  *
  57  * The code uses a simple two-stack algorithm. See
  58  * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
  59  * for a detailed explanation of the infix-to-postfix algorithm on which
  60  * this is based (this code differs in that it applies operators immediately
  61  * to the stack instead of adding them to a queue to end up with an
  62  * expression).
  63  *
  64  * To use the routine, call it with an expression string and error return
  65  * pointer
  66  */
  67
  68 /*
  69  * Aug 24, 2001              Manuel Novoa III
  70  *
  71  * Reduced the generated code size by about 30% (i386) and fixed several bugs.
  72  *
  73  * 1) In arith_apply():
  74  *    a) Cached values of *numptr and &(numptr[-1]).
  75  *    b) Removed redundant test for zero denominator.
  76  *
  77  * 2) In arith():
  78  *    a) Eliminated redundant code for processing operator tokens by moving
  79  *       to a table-based implementation.  Also folded handling of parens
  80  *       into the table.
  81  *    b) Combined all 3 loops which called arith_apply to reduce generated
  82  *       code size at the cost of speed.
  83  *
  84  * 3) The following expressions were treated as valid by the original code:
  85  *       1()  ,    0!  ,    1 ( *3 )   .
  86  *    These bugs have been fixed by internally enclosing the expression in
  87  *    parens and then checking that all binary ops and right parens are
  88  *    preceded by a valid expression (NUM_TOKEN).
  89  *
  90  * Note: It may be desirable to replace Aaron's test for whitespace with
  91  * ctype's isspace() if it is used by another busybox applet or if additional
  92  * whitespace chars should be considered.  Look below the "#include"s for a
  93  * precompiler test.
  94  */
  95 /*
  96  * Aug 26, 2001              Manuel Novoa III
  97  *
  98  * Return 0 for null expressions.  Pointed out by Vladimir Oleynik.
  99  *
 100  * Merge in Aaron's comments previously posted to the busybox list,
 101  * modified slightly to take account of my changes to the code.
 102  *
 103  */
 104 /*
 105  *  (C) 2003 Vladimir Oleynik <dzo@simtreas.ru>
 106  *
 107  * - allow access to variable,
 108  *   use recursive value indirection: c="2*2"; a="c"; echo $((a+=2)) produce 6
 109  * - implement assign syntax (VAR=expr, +=, *= etc)
 110  * - implement exponentiation (** operator)
 111  * - implement comma separated - expr, expr
 112  * - implement ++expr --expr expr++ expr--
 113  * - implement expr ? expr : expr (but second expr is always calculated)
 114  * - allow hexadecimal and octal numbers
 115  * - restore lost XOR operator
 116  * - protect $((num num)) as true zero expr (Manuel's error)
 117  * - always use special isspace(), see comment from bash ;-)
 118  */
 119 #include "libbb.h"
 120 #include "math.h"
 121
 122 #define a_e_h_t   arith_eval_hooks_t
 123 #define lookupvar (math_hooks->lookupvar)
 124 #define setvar    (math_hooks->setvar   )
 125 //#define endofname (math_hooks->endofname)
 126
 127 typedef unsigned char operator;
 128
 129 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
 130  * precedence, and 3 high bits are an ID unique across operators of that
 131  * precedence. The ID portion is so that multiple operators can have the
 132  * same precedence, ensuring that the leftmost one is evaluated first.
 133  * Consider * and /
 134  */
 135 #define tok_decl(prec,id)       (((id)<<5) | (prec))
 136 #define PREC(op)                ((op) & 0x1F)
 137
 138 #define TOK_LPAREN              tok_decl(0,0)
 139
 140 #define TOK_COMMA               tok_decl(1,0)
 141
 142 /* All assignments are right associative and have the same precedence,
 143  * but there are 11 of them, which doesn't fit into 3 bits for unique id.
 144  * Abusing another precedence level:
 145  */
 146 #define TOK_ASSIGN              tok_decl(2,0)
 147 #define TOK_AND_ASSIGN          tok_decl(2,1)
 148 #define TOK_OR_ASSIGN           tok_decl(2,2)
 149 #define TOK_XOR_ASSIGN          tok_decl(2,3)
 150 #define TOK_PLUS_ASSIGN         tok_decl(2,4)
 151 #define TOK_MINUS_ASSIGN        tok_decl(2,5)
 152 #define TOK_LSHIFT_ASSIGN       tok_decl(2,6)
 153 #define TOK_RSHIFT_ASSIGN       tok_decl(2,7)
 154
 155 #define TOK_MUL_ASSIGN          tok_decl(3,0)
 156 #define TOK_DIV_ASSIGN          tok_decl(3,1)
 157 #define TOK_REM_ASSIGN          tok_decl(3,2)
 158
 159 #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
 160
 161 /* ternary conditional operator is right associative too */
 162 #define TOK_CONDITIONAL         tok_decl(4,0)
 163 #define TOK_CONDITIONAL_SEP     tok_decl(4,1)
 164
 165 #define TOK_OR                  tok_decl(5,0)
 166
 167 #define TOK_AND                 tok_decl(6,0)
 168
 169 #define TOK_BOR                 tok_decl(7,0)
 170
 171 #define TOK_BXOR                tok_decl(8,0)
 172
 173 #define TOK_BAND                tok_decl(9,0)
 174
 175 #define TOK_EQ                  tok_decl(10,0)
 176 #define TOK_NE                  tok_decl(10,1)
 177
 178 #define TOK_LT                  tok_decl(11,0)
 179 #define TOK_GT                  tok_decl(11,1)
 180 #define TOK_GE                  tok_decl(11,2)
 181 #define TOK_LE                  tok_decl(11,3)
 182
 183 #define TOK_LSHIFT              tok_decl(12,0)
 184 #define TOK_RSHIFT              tok_decl(12,1)
 185
 186 #define TOK_ADD                 tok_decl(13,0)
 187 #define TOK_SUB                 tok_decl(13,1)
 188
 189 #define TOK_MUL                 tok_decl(14,0)
 190 #define TOK_DIV                 tok_decl(14,1)
 191 #define TOK_REM                 tok_decl(14,2)
 192
 193 /* exponent is right associative */
 194 #define TOK_EXPONENT            tok_decl(15,1)
 195
 196 /* unary operators */
 197 #define UNARYPREC               16
 198 #define TOK_BNOT                tok_decl(UNARYPREC,0)
 199 #define TOK_NOT                 tok_decl(UNARYPREC,1)
 200
 201 #define TOK_UMINUS              tok_decl(UNARYPREC+1,0)
 202 #define TOK_UPLUS               tok_decl(UNARYPREC+1,1)
 203
 204 #define PREC_PRE                (UNARYPREC+2)
 205
 206 #define TOK_PRE_INC             tok_decl(PREC_PRE, 0)
 207 #define TOK_PRE_DEC             tok_decl(PREC_PRE, 1)
 208
 209 #define PREC_POST               (UNARYPREC+3)
 210
 211 #define TOK_POST_INC            tok_decl(PREC_POST, 0)
 212 #define TOK_POST_DEC            tok_decl(PREC_POST, 1)
 213
 214 #define SPEC_PREC               (UNARYPREC+4)
 215
 216 #define TOK_NUM                 tok_decl(SPEC_PREC, 0)
 217 #define TOK_RPAREN              tok_decl(SPEC_PREC, 1)
 218
 219 static int
 220 tok_have_assign(operator op)
 221 {
 222         operator prec = PREC(op);
 223
 224         fix_assignment_prec(prec);
 225         return (prec == PREC(TOK_ASSIGN) ||
 226                         prec == PREC_PRE || prec == PREC_POST);
 227 }
 228
 229 static int
 230 is_right_associative(operator prec)
 231 {
 232         return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT)
 233                 || prec == PREC(TOK_CONDITIONAL));
 234 }
 235
 236 typedef struct {
 237         arith_t val;
 238         arith_t contidional_second_val;
 239         char contidional_second_val_initialized;
 240         char *var;      /* if NULL then is regular number,
 241                            else is variable name */
 242 } v_n_t;
 243
 244 typedef struct chk_var_recursive_looped_t {
 245         const char *var;
 246         struct chk_var_recursive_looped_t *next;
 247 } chk_var_recursive_looped_t;
 248
 249 static chk_var_recursive_looped_t *prev_chk_var_recursive;
 250
 251 static int
 252 arith_lookup_val(v_n_t *t, a_e_h_t *math_hooks)
 253 {
 254         if (t->var) {
 255                 const char *p = lookupvar(t->var);
 256
 257                 if (p) {
 258                         int errcode;
 259                         chk_var_recursive_looped_t *cur;
 260                         chk_var_recursive_looped_t cur_save;
 261
 262                         /* recursively try p as expression */
 263
 264                         for (cur = prev_chk_var_recursive; cur; cur = cur->next) {
 265                                 if (strcmp(cur->var, t->var) == 0) {
 266                                         /* expression recursion loop detected */
 267                                         return -5;
 268                                 }
 269                         }
 270                         /* save current var name */
 271                         cur = prev_chk_var_recursive;
 272                         cur_save.var = t->var;
 273                         cur_save.next = cur;
 274                         prev_chk_var_recursive = &cur_save;
 275
 276                         t->val = arith(p, &errcode, math_hooks);
 277                         /* restore previous ptr after recursion */
 278                         prev_chk_var_recursive = cur;
 279                         return errcode;
 280                 }
 281                 /* allow undefined var as 0 */
 282                 t->val = 0;
 283         }
 284         return 0;
 285 }
 286
 287 /* "Applying" a token means performing it on the top elements on the integer
 288  * stack. For an unary operator it will only change the top element, but a
 289  * binary operator will pop two arguments and push the result */
 290 static NOINLINE int
 291 arith_apply(operator op, v_n_t *numstack, v_n_t **numstackptr, a_e_h_t *math_hooks)
 292 {
 293 #define NUMPTR (*numstackptr)
 294
 295         v_n_t *numptr_m1;
 296         arith_t numptr_val, rez;
 297         int ret_arith_lookup_val;
 298
 299         /* There is no operator that can work without arguments */
 300         if (NUMPTR == numstack)
 301                 goto err;
 302         numptr_m1 = NUMPTR - 1;
 303
 304         /* Check operand is var with noninteger value */
 305         ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks);
 306         if (ret_arith_lookup_val)
 307                 return ret_arith_lookup_val;
 308
 309         rez = numptr_m1->val;
 310         if (op == TOK_UMINUS)
 311                 rez *= -1;
 312         else if (op == TOK_NOT)
 313                 rez = !rez;
 314         else if (op == TOK_BNOT)
 315                 rez = ~rez;
 316         else if (op == TOK_POST_INC || op == TOK_PRE_INC)
 317                 rez++;
 318         else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
 319                 rez--;
 320         else if (op != TOK_UPLUS) {
 321                 /* Binary operators */
 322
 323                 /* check and binary operators need two arguments */
 324                 if (numptr_m1 == numstack) goto err;
 325
 326                 /* ... and they pop one */
 327                 --NUMPTR;
 328                 numptr_val = rez;
 329                 if (op == TOK_CONDITIONAL) {
 330                         if (!numptr_m1->contidional_second_val_initialized) {
 331                                 /* protect $((expr1 ? expr2)) without ": expr" */
 332                                 goto err;
 333                         }
 334                         rez = numptr_m1->contidional_second_val;
 335                 } else if (numptr_m1->contidional_second_val_initialized) {
 336                         /* protect $((expr1 : expr2)) without "expr ? " */
 337                         goto err;
 338                 }
 339                 numptr_m1 = NUMPTR - 1;
 340                 if (op != TOK_ASSIGN) {
 341                         /* check operand is var with noninteger value for not '=' */
 342                         ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks);
 343                         if (ret_arith_lookup_val)
 344                                 return ret_arith_lookup_val;
 345                 }
 346                 if (op == TOK_CONDITIONAL) {
 347                         numptr_m1->contidional_second_val = rez;
 348                 }
 349                 rez = numptr_m1->val;
 350                 if (op == TOK_BOR || op == TOK_OR_ASSIGN)
 351                         rez |= numptr_val;
 352                 else if (op == TOK_OR)
 353                         rez = numptr_val || rez;
 354                 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
 355                         rez &= numptr_val;
 356                 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
 357                         rez ^= numptr_val;
 358                 else if (op == TOK_AND)
 359                         rez = rez && numptr_val;
 360                 else if (op == TOK_EQ)
 361                         rez = (rez == numptr_val);
 362                 else if (op == TOK_NE)
 363                         rez = (rez != numptr_val);
 364                 else if (op == TOK_GE)
 365                         rez = (rez >= numptr_val);
 366                 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
 367                         rez >>= numptr_val;
 368                 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
 369                         rez <<= numptr_val;
 370                 else if (op == TOK_GT)
 371                         rez = (rez > numptr_val);
 372                 else if (op == TOK_LT)
 373                         rez = (rez < numptr_val);
 374                 else if (op == TOK_LE)
 375                         rez = (rez <= numptr_val);
 376                 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
 377                         rez *= numptr_val;
 378                 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
 379                         rez += numptr_val;
 380                 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
 381                         rez -= numptr_val;
 382                 else if (op == TOK_ASSIGN || op == TOK_COMMA)
 383                         rez = numptr_val;
 384                 else if (op == TOK_CONDITIONAL_SEP) {
 385                         if (numptr_m1 == numstack) {
 386                                 /* protect $((expr : expr)) without "expr ? " */
 387                                 goto err;
 388                         }
 389                         numptr_m1->contidional_second_val_initialized = op;
 390                         numptr_m1->contidional_second_val = numptr_val;
 391                 } else if (op == TOK_CONDITIONAL) {
 392                         rez = rez ?
 393                                 numptr_val : numptr_m1->contidional_second_val;
 394                 } else if (op == TOK_EXPONENT) {
 395                         arith_t c;
 396                         if (numptr_val < 0)
 397                                 return -3;      /* exponent less than 0 */
 398                         c = 1;
 399                         while (--numptr_val >= 0)
 400                             c *= rez;
 401                         rez = c;
 402                 } else if (numptr_val==0)          /* zero divisor check */
 403                         return -2;
 404                 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
 405                         rez /= numptr_val;
 406                 else if (op == TOK_REM || op == TOK_REM_ASSIGN)
 407                         rez %= numptr_val;
 408         }
 409         if (tok_have_assign(op)) {
 410                 char buf[sizeof(arith_t)*3 + 2];
 411
 412                 if (numptr_m1->var == NULL) {
 413                         /* Hmm, 1=2 ? */
 414                         goto err;
 415                 }
 416                 /* save to shell variable */
 417                 sprintf(buf, arith_t_fmt, rez);
 418                 setvar(numptr_m1->var, buf);
 419                 /* after saving, make previous value for v++ or v-- */
 420                 if (op == TOK_POST_INC)
 421                         rez--;
 422                 else if (op == TOK_POST_DEC)
 423                         rez++;
 424         }
 425         numptr_m1->val = rez;
 426         /* erase var name, it is just a number now */
 427         numptr_m1->var = NULL;
 428         return 0;
 429  err:
 430         return -1;
 431 #undef NUMPTR
 432 }
 433
 434 /* longest must be first */
 435 static const char op_tokens[] ALIGN1 = {
 436         '<','<','=',0, TOK_LSHIFT_ASSIGN,
 437         '>','>','=',0, TOK_RSHIFT_ASSIGN,
 438         '<','<',    0, TOK_LSHIFT,
 439         '>','>',    0, TOK_RSHIFT,
 440         '|','|',    0, TOK_OR,
 441         '&','&',    0, TOK_AND,
 442         '!','=',    0, TOK_NE,
 443         '<','=',    0, TOK_LE,
 444         '>','=',    0, TOK_GE,
 445         '=','=',    0, TOK_EQ,
 446         '|','=',    0, TOK_OR_ASSIGN,
 447         '&','=',    0, TOK_AND_ASSIGN,
 448         '*','=',    0, TOK_MUL_ASSIGN,
 449         '/','=',    0, TOK_DIV_ASSIGN,
 450         '%','=',    0, TOK_REM_ASSIGN,
 451         '+','=',    0, TOK_PLUS_ASSIGN,
 452         '-','=',    0, TOK_MINUS_ASSIGN,
 453         '-','-',    0, TOK_POST_DEC,
 454         '^','=',    0, TOK_XOR_ASSIGN,
 455         '+','+',    0, TOK_POST_INC,
 456         '*','*',    0, TOK_EXPONENT,
 457         '!',        0, TOK_NOT,
 458         '<',        0, TOK_LT,
 459         '>',        0, TOK_GT,
 460         '=',        0, TOK_ASSIGN,
 461         '|',        0, TOK_BOR,
 462         '&',        0, TOK_BAND,
 463         '*',        0, TOK_MUL,
 464         '/',        0, TOK_DIV,
 465         '%',        0, TOK_REM,
 466         '+',        0, TOK_ADD,
 467         '-',        0, TOK_SUB,
 468         '^',        0, TOK_BXOR,
 469         /* uniq */
 470         '~',        0, TOK_BNOT,
 471         ',',        0, TOK_COMMA,
 472         '?',        0, TOK_CONDITIONAL,
 473         ':',        0, TOK_CONDITIONAL_SEP,
 474         ')',        0, TOK_RPAREN,
 475         '(',        0, TOK_LPAREN,
 476         0
 477 };
 478 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
 479
 480 const char* FAST_FUNC
 481 endofname(const char *name)
 482 {
 483         if (!is_name(*name))
 484                 return name;
 485         while (*++name) {
 486                 if (!is_in_name(*name))
 487                         break;
 488         }
 489         return name;
 490 }
 491
 492 arith_t
 493 arith(const char *expr, int *perrcode, a_e_h_t *math_hooks)
 494 {
 495         operator lasttok;
 496         int errcode;
 497         const char *start_expr = expr = skip_whitespace(expr);
 498         unsigned expr_len = strlen(expr) + 2;
 499         /* Stack of integers */
 500         /* The proof that there can be no more than strlen(startbuf)/2+1 integers
 501          * in any given correct or incorrect expression is left as an exercise to
 502          * the reader. */
 503         v_n_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
 504         v_n_t *numstackptr = numstack;
 505         /* Stack of operator tokens */
 506         operator *const stack = alloca(expr_len * sizeof(stack[0]));
 507         operator *stackptr = stack;
 508
 509         *stackptr++ = lasttok = TOK_LPAREN;     /* start off with a left paren */
 510         errcode = 0;
 511
 512         while (1) {
 513                 const char *p;
 514                 operator op;
 515                 operator prec;
 516                 char arithval;
 517
 518                 expr = skip_whitespace(expr);
 519                 arithval = *expr;
 520                 if (arithval == '\0') {
 521                         if (expr == start_expr) {
 522                                 /* Null expression. */
 523                                 numstack->val = 0;
 524                                 goto ret;
 525                         }
 526
 527                         /* This is only reached after all tokens have been extracted from the
 528                          * input stream. If there are still tokens on the operator stack, they
 529                          * are to be applied in order. At the end, there should be a final
 530                          * result on the integer stack */
 531
 532                         if (expr != ptr_to_rparen + 1) {
 533                                 /* If we haven't done so already,
 534                                  * append a closing right paren
 535                                  * and let the loop process it */
 536                                 expr = ptr_to_rparen;
 537                                 continue;
 538                         }
 539                         /* At this point, we're done with the expression */
 540                         if (numstackptr != numstack + 1) {
 541                                 /* ...but if there isn't, it's bad */
 542                                 goto err;
 543                         }
 544                         if (numstack->var) {
 545                                 /* expression is $((var)) only, lookup now */
 546                                 errcode = arith_lookup_val(numstack, math_hooks);
 547                         }
 548                         goto ret;
 549                 }
 550
 551                 p = endofname(expr);
 552                 if (p != expr) {
 553                         /* Name */
 554                         size_t var_name_size = (p-expr) + 1;  /* +1 for NUL */
 555                         numstackptr->var = alloca(var_name_size);
 556                         safe_strncpy(numstackptr->var, expr, var_name_size);
 557                         expr = p;
 558  num:
 559                         numstackptr->contidional_second_val_initialized = 0;
 560                         numstackptr++;
 561                         lasttok = TOK_NUM;
 562                         continue;
 563                 }
 564
 565                 if (isdigit(arithval)) {
 566                         /* Number */
 567                         numstackptr->var = NULL;
 568                         errno = 0;
 569                         numstackptr->val = strto_arith_t(expr, (char**) &expr, 0);
 570                         if (errno)
 571                                 numstackptr->val = 0; /* bash compat */
 572                         goto num;
 573                 }
 574
 575                 /* Should be an operator */
 576                 p = op_tokens;
 577                 while (1) {
 578                         const char *e = expr;
 579                         /* Compare expr to current op_tokens[] element */
 580                         while (*p && *e == *p)
 581                                 p++, e++;
 582                         if (*p == '\0') { /* match: operator is found */
 583                                 expr = e;
 584                                 break;
 585                         }
 586                         /* Go to next element of op_tokens[] */
 587                         while (*p)
 588                                 p++;
 589                         p += 2; /* skip NUL and TOK_foo bytes */
 590                         if (*p == '\0') /* no next element, operator not found */
 591                                 goto err;
 592                 }
 593                 op = p[1]; /* fetch TOK_foo value */
 594                 /* NB: expr now points past the operator */
 595
 596                 /* post grammar: a++ reduce to num */
 597                 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
 598                         lasttok = TOK_NUM;
 599
 600                 /* Plus and minus are binary (not unary) _only_ if the last
 601                  * token was a number, or a right paren (which pretends to be
 602                  * a number, since it evaluates to one). Think about it.
 603                  * It makes sense. */
 604                 if (lasttok != TOK_NUM) {
 605                         switch (op) {
 606                         case TOK_ADD:
 607                                 op = TOK_UPLUS;
 608                                 break;
 609                         case TOK_SUB:
 610                                 op = TOK_UMINUS;
 611                                 break;
 612                         case TOK_POST_INC:
 613                                 op = TOK_PRE_INC;
 614                                 break;
 615                         case TOK_POST_DEC:
 616                                 op = TOK_PRE_DEC;
 617                                 break;
 618                         }
 619                 }
 620                 /* We don't want an unary operator to cause recursive descent on the
 621                  * stack, because there can be many in a row and it could cause an
 622                  * operator to be evaluated before its argument is pushed onto the
 623                  * integer stack.
 624                  * But for binary operators, "apply" everything on the operator
 625                  * stack until we find an operator with a lesser priority than the
 626                  * one we have just extracted.
 627                  * Left paren is given the lowest priority so it will never be
 628                  * "applied" in this way.
 629                  * if associativity is right and priority eq, applied also skip
 630                  */
 631                 prec = PREC(op);
 632                 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
 633                         /* not left paren or unary */
 634                         if (lasttok != TOK_NUM) {
 635                                 /* binary op must be preceded by a num */
 636                                 goto err;
 637                         }
 638                         while (stackptr != stack) {
 639                                 operator prev_op = *--stackptr;
 640                                 if (op == TOK_RPAREN) {
 641                                         /* The algorithm employed here is simple: while we don't
 642                                          * hit an open paren nor the bottom of the stack, pop
 643                                          * tokens and apply them */
 644                                         if (prev_op == TOK_LPAREN) {
 645                                                 /* Any operator directly after a
 646                                                  * close paren should consider itself binary */
 647                                                 lasttok = TOK_NUM;
 648                                                 goto next;
 649                                         }
 650                                 } else {
 651                                         operator prev_prec = PREC(prev_op);
 652                                         fix_assignment_prec(prec);
 653                                         fix_assignment_prec(prev_prec);
 654                                         if (prev_prec < prec
 655                                          || (prev_prec == prec && is_right_associative(prec))
 656                                         ) {
 657                                                 stackptr++;
 658                                                 break;
 659                                         }
 660                                 }
 661                                 errcode = arith_apply(prev_op, numstack, &numstackptr, math_hooks);
 662                                 if (errcode)
 663                                         goto ret;
 664                         }
 665                         if (op == TOK_RPAREN) {
 666                                 goto err;
 667                         }
 668                 }
 669
 670                 /* Push this operator to the stack and remember it. */
 671                 *stackptr++ = lasttok = op;
 672  next: ;
 673         } /* while (1) */
 674
 675  err:
 676         numstack->val = errcode = -1;
 677  ret:
 678         *perrcode = errcode;
 679         return numstack->val;
 680 }
 681
 682 /*
 683  * Copyright (c) 1989, 1991, 1993, 1994
 684  *      The Regents of the University of California.  All rights reserved.
 685  *
 686  * This code is derived from software contributed to Berkeley by
 687  * Kenneth Almquist.
 688  *
 689  * Redistribution and use in source and binary forms, with or without
 690  * modification, are permitted provided that the following conditions
 691  * are met:
 692  * 1. Redistributions of source code must retain the above copyright
 693  *    notice, this list of conditions and the following disclaimer.
 694  * 2. Redistributions in binary form must reproduce the above copyright
 695  *    notice, this list of conditions and the following disclaimer in the
 696  *    documentation and/or other materials provided with the distribution.
 697  * 3. Neither the name of the University nor the names of its contributors
 698  *    may be used to endorse or promote products derived from this software
 699  *    without specific prior written permission.
 700  *
 701  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 702  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 703  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 704  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 705  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 706  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 707  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 708  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 709  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 710  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 711  * SUCH DAMAGE.
 712  */