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 lookupvar (math_state->lookupvar)
 123 #define setvar    (math_state->setvar   )
 124 //#define endofname (math_state->endofname)
 125
 126 typedef unsigned char operator;
 127
 128 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
 129  * precedence, and 3 high bits are an ID unique across operators of that
 130  * precedence. The ID portion is so that multiple operators can have the
 131  * same precedence, ensuring that the leftmost one is evaluated first.
 132  * Consider * and /
 133  */
 134 #define tok_decl(prec,id)       (((id)<<5) | (prec))
 135 #define PREC(op)                ((op) & 0x1F)
 136
 137 #define TOK_LPAREN              tok_decl(0,0)
 138
 139 #define TOK_COMMA               tok_decl(1,0)
 140
 141 /* All assignments are right associative and have the same precedence,
 142  * but there are 11 of them, which doesn't fit into 3 bits for unique id.
 143  * Abusing another precedence level:
 144  */
 145 #define TOK_ASSIGN              tok_decl(2,0)
 146 #define TOK_AND_ASSIGN          tok_decl(2,1)
 147 #define TOK_OR_ASSIGN           tok_decl(2,2)
 148 #define TOK_XOR_ASSIGN          tok_decl(2,3)
 149 #define TOK_PLUS_ASSIGN         tok_decl(2,4)
 150 #define TOK_MINUS_ASSIGN        tok_decl(2,5)
 151 #define TOK_LSHIFT_ASSIGN       tok_decl(2,6)
 152 #define TOK_RSHIFT_ASSIGN       tok_decl(2,7)
 153
 154 #define TOK_MUL_ASSIGN          tok_decl(3,0)
 155 #define TOK_DIV_ASSIGN          tok_decl(3,1)
 156 #define TOK_REM_ASSIGN          tok_decl(3,2)
 157
 158 #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
 159
 160 /* ternary conditional operator is right associative too */
 161 #define TOK_CONDITIONAL         tok_decl(4,0)
 162 #define TOK_CONDITIONAL_SEP     tok_decl(4,1)
 163
 164 #define TOK_OR                  tok_decl(5,0)
 165
 166 #define TOK_AND                 tok_decl(6,0)
 167
 168 #define TOK_BOR                 tok_decl(7,0)
 169
 170 #define TOK_BXOR                tok_decl(8,0)
 171
 172 #define TOK_BAND                tok_decl(9,0)
 173
 174 #define TOK_EQ                  tok_decl(10,0)
 175 #define TOK_NE                  tok_decl(10,1)
 176
 177 #define TOK_LT                  tok_decl(11,0)
 178 #define TOK_GT                  tok_decl(11,1)
 179 #define TOK_GE                  tok_decl(11,2)
 180 #define TOK_LE                  tok_decl(11,3)
 181
 182 #define TOK_LSHIFT              tok_decl(12,0)
 183 #define TOK_RSHIFT              tok_decl(12,1)
 184
 185 #define TOK_ADD                 tok_decl(13,0)
 186 #define TOK_SUB                 tok_decl(13,1)
 187
 188 #define TOK_MUL                 tok_decl(14,0)
 189 #define TOK_DIV                 tok_decl(14,1)
 190 #define TOK_REM                 tok_decl(14,2)
 191
 192 /* exponent is right associative */
 193 #define TOK_EXPONENT            tok_decl(15,1)
 194
 195 /* unary operators */
 196 #define UNARYPREC               16
 197 #define TOK_BNOT                tok_decl(UNARYPREC,0)
 198 #define TOK_NOT                 tok_decl(UNARYPREC,1)
 199
 200 #define TOK_UMINUS              tok_decl(UNARYPREC+1,0)
 201 #define TOK_UPLUS               tok_decl(UNARYPREC+1,1)
 202
 203 #define PREC_PRE                (UNARYPREC+2)
 204
 205 #define TOK_PRE_INC             tok_decl(PREC_PRE, 0)
 206 #define TOK_PRE_DEC             tok_decl(PREC_PRE, 1)
 207
 208 #define PREC_POST               (UNARYPREC+3)
 209
 210 #define TOK_POST_INC            tok_decl(PREC_POST, 0)
 211 #define TOK_POST_DEC            tok_decl(PREC_POST, 1)
 212
 213 #define SPEC_PREC               (UNARYPREC+4)
 214
 215 #define TOK_NUM                 tok_decl(SPEC_PREC, 0)
 216 #define TOK_RPAREN              tok_decl(SPEC_PREC, 1)
 217
 218 static int
 219 tok_have_assign(operator op)
 220 {
 221         operator prec = PREC(op);
 222
 223         fix_assignment_prec(prec);
 224         return (prec == PREC(TOK_ASSIGN) ||
 225                         prec == PREC_PRE || prec == PREC_POST);
 226 }
 227
 228 static int
 229 is_right_associative(operator prec)
 230 {
 231         return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT)
 232                 || prec == PREC(TOK_CONDITIONAL));
 233 }
 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 remembered_name {
 245         struct remembered_name *next;
 246         const char *var;
 247 } remembered_name;
 248
 249
 250 static arith_t FAST_FUNC
 251 evaluate_string(arith_state_t *math_state, const char *expr);
 252
 253 static int
 254 arith_lookup_val(arith_state_t *math_state, v_n_t *t)
 255 {
 256         if (t->var) {
 257                 const char *p = lookupvar(t->var);
 258                 if (p) {
 259                         remembered_name *cur;
 260                         remembered_name cur_save;
 261
 262                         /* did we already see this name?
 263                          * testcase: a=b; b=a; echo $((a))
 264                          */
 265                         for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
 266                                 if (strcmp(cur->var, t->var) == 0) {
 267                                         /* Yes. Expression recursion loop detected */
 268                                         return -5;
 269                                 }
 270                         }
 271
 272                         /* push current var name */
 273                         cur = math_state->list_of_recursed_names;
 274                         cur_save.var = t->var;
 275                         cur_save.next = cur;
 276                         math_state->list_of_recursed_names = &cur_save;
 277
 278                         /* recursively evaluate p as expression */
 279                         t->val = evaluate_string(math_state, p);
 280
 281                         /* pop current var name */
 282                         math_state->list_of_recursed_names = cur;
 283
 284                         return math_state->errcode;
 285                 }
 286                 /* treat undefined var as 0 */
 287                 t->val = 0;
 288         }
 289         return 0;
 290 }
 291
 292 /* "Applying" a token means performing it on the top elements on the integer
 293  * stack. For an unary operator it will only change the top element, but a
 294  * binary operator will pop two arguments and push the result */
 295 static NOINLINE int
 296 arith_apply(arith_state_t *math_state, operator op, v_n_t *numstack, v_n_t **numstackptr)
 297 {
 298 #define NUMPTR (*numstackptr)
 299
 300         v_n_t *numptr_m1;
 301         arith_t numptr_val, rez;
 302         int err;
 303
 304         /* There is no operator that can work without arguments */
 305         if (NUMPTR == numstack)
 306                 goto err;
 307         numptr_m1 = NUMPTR - 1;
 308
 309         /* Check operand is var with noninteger value */
 310         err = arith_lookup_val(math_state, numptr_m1);
 311         if (err)
 312                 return err;
 313
 314         rez = numptr_m1->val;
 315         if (op == TOK_UMINUS)
 316                 rez *= -1;
 317         else if (op == TOK_NOT)
 318                 rez = !rez;
 319         else if (op == TOK_BNOT)
 320                 rez = ~rez;
 321         else if (op == TOK_POST_INC || op == TOK_PRE_INC)
 322                 rez++;
 323         else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
 324                 rez--;
 325         else if (op != TOK_UPLUS) {
 326                 /* Binary operators */
 327
 328                 /* check and binary operators need two arguments */
 329                 if (numptr_m1 == numstack) goto err;
 330
 331                 /* ... and they pop one */
 332                 --NUMPTR;
 333                 numptr_val = rez;
 334                 if (op == TOK_CONDITIONAL) {
 335                         if (!numptr_m1->contidional_second_val_initialized) {
 336                                 /* protect $((expr1 ? expr2)) without ": expr" */
 337                                 goto err;
 338                         }
 339                         rez = numptr_m1->contidional_second_val;
 340                 } else if (numptr_m1->contidional_second_val_initialized) {
 341                         /* protect $((expr1 : expr2)) without "expr ? " */
 342                         goto err;
 343                 }
 344                 numptr_m1 = NUMPTR - 1;
 345                 if (op != TOK_ASSIGN) {
 346                         /* check operand is var with noninteger value for not '=' */
 347                         err = arith_lookup_val(math_state, numptr_m1);
 348                         if (err)
 349                                 return err;
 350                 }
 351                 if (op == TOK_CONDITIONAL) {
 352                         numptr_m1->contidional_second_val = rez;
 353                 }
 354                 rez = numptr_m1->val;
 355                 if (op == TOK_BOR || op == TOK_OR_ASSIGN)
 356                         rez |= numptr_val;
 357                 else if (op == TOK_OR)
 358                         rez = numptr_val || rez;
 359                 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
 360                         rez &= numptr_val;
 361                 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
 362                         rez ^= numptr_val;
 363                 else if (op == TOK_AND)
 364                         rez = rez && numptr_val;
 365                 else if (op == TOK_EQ)
 366                         rez = (rez == numptr_val);
 367                 else if (op == TOK_NE)
 368                         rez = (rez != numptr_val);
 369                 else if (op == TOK_GE)
 370                         rez = (rez >= numptr_val);
 371                 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
 372                         rez >>= numptr_val;
 373                 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
 374                         rez <<= numptr_val;
 375                 else if (op == TOK_GT)
 376                         rez = (rez > numptr_val);
 377                 else if (op == TOK_LT)
 378                         rez = (rez < numptr_val);
 379                 else if (op == TOK_LE)
 380                         rez = (rez <= numptr_val);
 381                 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
 382                         rez *= numptr_val;
 383                 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
 384                         rez += numptr_val;
 385                 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
 386                         rez -= numptr_val;
 387                 else if (op == TOK_ASSIGN || op == TOK_COMMA)
 388                         rez = numptr_val;
 389                 else if (op == TOK_CONDITIONAL_SEP) {
 390                         if (numptr_m1 == numstack) {
 391                                 /* protect $((expr : expr)) without "expr ? " */
 392                                 goto err;
 393                         }
 394                         numptr_m1->contidional_second_val_initialized = op;
 395                         numptr_m1->contidional_second_val = numptr_val;
 396                 } else if (op == TOK_CONDITIONAL) {
 397                         rez = rez ?
 398                                 numptr_val : numptr_m1->contidional_second_val;
 399                 } else if (op == TOK_EXPONENT) {
 400                         arith_t c;
 401                         if (numptr_val < 0)
 402                                 return -3;      /* exponent less than 0 */
 403                         c = 1;
 404                         while (--numptr_val >= 0)
 405                             c *= rez;
 406                         rez = c;
 407                 } else if (numptr_val==0)          /* zero divisor check */
 408                         return -2;
 409                 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
 410                         rez /= numptr_val;
 411                 else if (op == TOK_REM || op == TOK_REM_ASSIGN)
 412                         rez %= numptr_val;
 413         }
 414         if (tok_have_assign(op)) {
 415                 char buf[sizeof(arith_t)*3 + 2];
 416
 417                 if (numptr_m1->var == NULL) {
 418                         /* Hmm, 1=2 ? */
 419                         goto err;
 420                 }
 421                 /* save to shell variable */
 422                 sprintf(buf, arith_t_fmt, rez);
 423                 setvar(numptr_m1->var, buf);
 424                 /* after saving, make previous value for v++ or v-- */
 425                 if (op == TOK_POST_INC)
 426                         rez--;
 427                 else if (op == TOK_POST_DEC)
 428                         rez++;
 429         }
 430         numptr_m1->val = rez;
 431         /* erase var name, it is just a number now */
 432         numptr_m1->var = NULL;
 433         return 0;
 434  err:
 435         return -1;
 436 #undef NUMPTR
 437 }
 438
 439 /* longest must be first */
 440 static const char op_tokens[] ALIGN1 = {
 441         '<','<','=',0, TOK_LSHIFT_ASSIGN,
 442         '>','>','=',0, TOK_RSHIFT_ASSIGN,
 443         '<','<',    0, TOK_LSHIFT,
 444         '>','>',    0, TOK_RSHIFT,
 445         '|','|',    0, TOK_OR,
 446         '&','&',    0, TOK_AND,
 447         '!','=',    0, TOK_NE,
 448         '<','=',    0, TOK_LE,
 449         '>','=',    0, TOK_GE,
 450         '=','=',    0, TOK_EQ,
 451         '|','=',    0, TOK_OR_ASSIGN,
 452         '&','=',    0, TOK_AND_ASSIGN,
 453         '*','=',    0, TOK_MUL_ASSIGN,
 454         '/','=',    0, TOK_DIV_ASSIGN,
 455         '%','=',    0, TOK_REM_ASSIGN,
 456         '+','=',    0, TOK_PLUS_ASSIGN,
 457         '-','=',    0, TOK_MINUS_ASSIGN,
 458         '-','-',    0, TOK_POST_DEC,
 459         '^','=',    0, TOK_XOR_ASSIGN,
 460         '+','+',    0, TOK_POST_INC,
 461         '*','*',    0, TOK_EXPONENT,
 462         '!',        0, TOK_NOT,
 463         '<',        0, TOK_LT,
 464         '>',        0, TOK_GT,
 465         '=',        0, TOK_ASSIGN,
 466         '|',        0, TOK_BOR,
 467         '&',        0, TOK_BAND,
 468         '*',        0, TOK_MUL,
 469         '/',        0, TOK_DIV,
 470         '%',        0, TOK_REM,
 471         '+',        0, TOK_ADD,
 472         '-',        0, TOK_SUB,
 473         '^',        0, TOK_BXOR,
 474         /* uniq */
 475         '~',        0, TOK_BNOT,
 476         ',',        0, TOK_COMMA,
 477         '?',        0, TOK_CONDITIONAL,
 478         ':',        0, TOK_CONDITIONAL_SEP,
 479         ')',        0, TOK_RPAREN,
 480         '(',        0, TOK_LPAREN,
 481         0
 482 };
 483 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
 484
 485 const char* FAST_FUNC
 486 endofname(const char *name)
 487 {
 488         if (!is_name(*name))
 489                 return name;
 490         while (*++name) {
 491                 if (!is_in_name(*name))
 492                         break;
 493         }
 494         return name;
 495 }
 496
 497 static arith_t FAST_FUNC
 498 evaluate_string(arith_state_t *math_state, const char *expr)
 499 {
 500         operator lasttok;
 501         int errcode;
 502         const char *start_expr = expr = skip_whitespace(expr);
 503         unsigned expr_len = strlen(expr) + 2;
 504         /* Stack of integers */
 505         /* The proof that there can be no more than strlen(startbuf)/2+1 integers
 506          * in any given correct or incorrect expression is left as an exercise to
 507          * the reader. */
 508         v_n_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
 509         v_n_t *numstackptr = numstack;
 510         /* Stack of operator tokens */
 511         operator *const stack = alloca(expr_len * sizeof(stack[0]));
 512         operator *stackptr = stack;
 513
 514         *stackptr++ = lasttok = TOK_LPAREN;     /* start off with a left paren */
 515         errcode = 0;
 516
 517         while (1) {
 518                 const char *p;
 519                 operator op;
 520                 operator prec;
 521                 char arithval;
 522
 523                 expr = skip_whitespace(expr);
 524                 arithval = *expr;
 525                 if (arithval == '\0') {
 526                         if (expr == start_expr) {
 527                                 /* Null expression. */
 528                                 numstack->val = 0;
 529                                 goto ret;
 530                         }
 531
 532                         /* This is only reached after all tokens have been extracted from the
 533                          * input stream. If there are still tokens on the operator stack, they
 534                          * are to be applied in order. At the end, there should be a final
 535                          * result on the integer stack */
 536
 537                         if (expr != ptr_to_rparen + 1) {
 538                                 /* If we haven't done so already,
 539                                  * append a closing right paren
 540                                  * and let the loop process it */
 541                                 expr = ptr_to_rparen;
 542                                 continue;
 543                         }
 544                         /* At this point, we're done with the expression */
 545                         if (numstackptr != numstack + 1) {
 546                                 /* ...but if there isn't, it's bad */
 547                                 goto err;
 548                         }
 549                         if (numstack->var) {
 550                                 /* expression is $((var)) only, lookup now */
 551                                 errcode = arith_lookup_val(math_state, numstack);
 552                         }
 553                         goto ret;
 554                 }
 555
 556                 p = endofname(expr);
 557                 if (p != expr) {
 558                         /* Name */
 559                         size_t var_name_size = (p-expr) + 1;  /* +1 for NUL */
 560                         numstackptr->var = alloca(var_name_size);
 561                         safe_strncpy(numstackptr->var, expr, var_name_size);
 562                         expr = p;
 563  num:
 564                         numstackptr->contidional_second_val_initialized = 0;
 565                         numstackptr++;
 566                         lasttok = TOK_NUM;
 567                         continue;
 568                 }
 569
 570                 if (isdigit(arithval)) {
 571                         /* Number */
 572                         numstackptr->var = NULL;
 573                         errno = 0;
 574                         numstackptr->val = strto_arith_t(expr, (char**) &expr, 0);
 575                         if (errno)
 576                                 numstackptr->val = 0; /* bash compat */
 577                         goto num;
 578                 }
 579
 580                 /* Should be an operator */
 581                 p = op_tokens;
 582                 while (1) {
 583                         const char *e = expr;
 584                         /* Compare expr to current op_tokens[] element */
 585                         while (*p && *e == *p)
 586                                 p++, e++;
 587                         if (*p == '\0') { /* match: operator is found */
 588                                 expr = e;
 589                                 break;
 590                         }
 591                         /* Go to next element of op_tokens[] */
 592                         while (*p)
 593                                 p++;
 594                         p += 2; /* skip NUL and TOK_foo bytes */
 595                         if (*p == '\0') /* no next element, operator not found */
 596                                 goto err;
 597                 }
 598                 op = p[1]; /* fetch TOK_foo value */
 599                 /* NB: expr now points past the operator */
 600
 601                 /* post grammar: a++ reduce to num */
 602                 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
 603                         lasttok = TOK_NUM;
 604
 605                 /* Plus and minus are binary (not unary) _only_ if the last
 606                  * token was a number, or a right paren (which pretends to be
 607                  * a number, since it evaluates to one). Think about it.
 608                  * It makes sense. */
 609                 if (lasttok != TOK_NUM) {
 610                         switch (op) {
 611                         case TOK_ADD:
 612                                 op = TOK_UPLUS;
 613                                 break;
 614                         case TOK_SUB:
 615                                 op = TOK_UMINUS;
 616                                 break;
 617                         case TOK_POST_INC:
 618                                 op = TOK_PRE_INC;
 619                                 break;
 620                         case TOK_POST_DEC:
 621                                 op = TOK_PRE_DEC;
 622                                 break;
 623                         }
 624                 }
 625                 /* We don't want an unary operator to cause recursive descent on the
 626                  * stack, because there can be many in a row and it could cause an
 627                  * operator to be evaluated before its argument is pushed onto the
 628                  * integer stack.
 629                  * But for binary operators, "apply" everything on the operator
 630                  * stack until we find an operator with a lesser priority than the
 631                  * one we have just extracted.
 632                  * Left paren is given the lowest priority so it will never be
 633                  * "applied" in this way.
 634                  * if associativity is right and priority eq, applied also skip
 635                  */
 636                 prec = PREC(op);
 637                 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
 638                         /* not left paren or unary */
 639                         if (lasttok != TOK_NUM) {
 640                                 /* binary op must be preceded by a num */
 641                                 goto err;
 642                         }
 643                         while (stackptr != stack) {
 644                                 operator prev_op = *--stackptr;
 645                                 if (op == TOK_RPAREN) {
 646                                         /* The algorithm employed here is simple: while we don't
 647                                          * hit an open paren nor the bottom of the stack, pop
 648                                          * tokens and apply them */
 649                                         if (prev_op == TOK_LPAREN) {
 650                                                 /* Any operator directly after a
 651                                                  * close paren should consider itself binary */
 652                                                 lasttok = TOK_NUM;
 653                                                 goto next;
 654                                         }
 655                                 } else {
 656                                         operator prev_prec = PREC(prev_op);
 657                                         fix_assignment_prec(prec);
 658                                         fix_assignment_prec(prev_prec);
 659                                         if (prev_prec < prec
 660                                          || (prev_prec == prec && is_right_associative(prec))
 661                                         ) {
 662                                                 stackptr++;
 663                                                 break;
 664                                         }
 665                                 }
 666                                 errcode = arith_apply(math_state, prev_op, numstack, &numstackptr);
 667                                 if (errcode)
 668                                         goto ret;
 669                         }
 670                         if (op == TOK_RPAREN) {
 671                                 goto err;
 672                         }
 673                 }
 674
 675                 /* Push this operator to the stack and remember it. */
 676                 *stackptr++ = lasttok = op;
 677  next: ;
 678         } /* while (1) */
 679
 680  err:
 681         numstack->val = errcode = -1;
 682  ret:
 683         math_state->errcode = errcode;
 684         return numstack->val;
 685 }
 686
 687 arith_t FAST_FUNC
 688 arith(arith_state_t *math_state, const char *expr)
 689 {
 690         math_state->list_of_recursed_names = NULL;
 691         return evaluate_string(math_state, expr);
 692 }
 693
 694 /*
 695  * Copyright (c) 1989, 1991, 1993, 1994
 696  *      The Regents of the University of California.  All rights reserved.
 697  *
 698  * This code is derived from software contributed to Berkeley by
 699  * Kenneth Almquist.
 700  *
 701  * Redistribution and use in source and binary forms, with or without
 702  * modification, are permitted provided that the following conditions
 703  * are met:
 704  * 1. Redistributions of source code must retain the above copyright
 705  *    notice, this list of conditions and the following disclaimer.
 706  * 2. Redistributions in binary form must reproduce the above copyright
 707  *    notice, this list of conditions and the following disclaimer in the
 708  *    documentation and/or other materials provided with the distribution.
 709  * 3. Neither the name of the University nor the names of its contributors
 710  *    may be used to endorse or promote products derived from this software
 711  *    without specific prior written permission.
 712  *
 713  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 714  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 715  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 716  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 717  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 718  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 719  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 720  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 721  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 722  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 723  * SUCH DAMAGE.
 724  */