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