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 is_assign_op(operator op)
 217 {
 218         operator prec = PREC(op);
 219         fix_assignment_prec(prec);
 220         return prec == PREC(TOK_ASSIGN)
 221         || prec == PREC_PRE
 222         || prec == PREC_POST;
 223 }
 224
 225 static int
 226 is_right_associative(operator prec)
 227 {
 228         return prec == PREC(TOK_ASSIGN)
 229         || prec == PREC(TOK_EXPONENT)
 230         || prec == PREC(TOK_CONDITIONAL);
 231 }
 232
 233
 234 typedef struct {
 235         arith_t val;
 236         /* We acquire second_val only when "expr1 : expr2" part
 237          * of ternary ?: op is evaluated.
 238          * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
 239          * ':' produces a new value which has two parts, val and second_val;
 240          * then '?' selects one of them based on its left side.
 241          */
 242         arith_t second_val;
 243         char second_val_present;
 244         /* If NULL then it's just a number, else it's a named variable */
 245         char *var;
 246 } var_or_num_t;
 247
 248 typedef struct remembered_name {
 249         struct remembered_name *next;
 250         const char *var;
 251 } remembered_name;
 252
 253
 254 static arith_t FAST_FUNC
 255 evaluate_string(arith_state_t *math_state, const char *expr);
 256
 257 static const char*
 258 arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
 259 {
 260         if (t->var) {
 261                 const char *p = lookupvar(t->var);
 262                 if (p) {
 263                         remembered_name *cur;
 264                         remembered_name cur_save;
 265
 266                         /* did we already see this name?
 267                          * testcase: a=b; b=a; echo $((a))
 268                          */
 269                         for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
 270                                 if (strcmp(cur->var, t->var) == 0) {
 271                                         /* Yes */
 272                                         return "expression recursion loop detected";
 273                                 }
 274                         }
 275
 276                         /* push current var name */
 277                         cur = math_state->list_of_recursed_names;
 278                         cur_save.var = t->var;
 279                         cur_save.next = cur;
 280                         math_state->list_of_recursed_names = &cur_save;
 281
 282                         /* recursively evaluate p as expression */
 283                         t->val = evaluate_string(math_state, p);
 284
 285                         /* pop current var name */
 286                         math_state->list_of_recursed_names = cur;
 287
 288                         return math_state->errmsg;
 289                 }
 290                 /* treat undefined var as 0 */
 291                 t->val = 0;
 292         }
 293         return 0;
 294 }
 295
 296 /* "Applying" a token means performing it on the top elements on the integer
 297  * stack. For an unary operator it will only change the top element, but a
 298  * binary operator will pop two arguments and push the result */
 299 static NOINLINE const char*
 300 arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
 301 {
 302 #define NUMPTR (*numstackptr)
 303
 304         var_or_num_t *top_of_stack;
 305         arith_t rez;
 306         const char *err;
 307
 308         /* There is no operator that can work without arguments */
 309         if (NUMPTR == numstack)
 310                 goto err;
 311
 312         top_of_stack = NUMPTR - 1;
 313
 314         /* Resolve name to value, if needed */
 315         err = arith_lookup_val(math_state, top_of_stack);
 316         if (err)
 317                 return err;
 318
 319         rez = top_of_stack->val;
 320         if (op == TOK_UMINUS)
 321                 rez = -rez;
 322         else if (op == TOK_NOT)
 323                 rez = !rez;
 324         else if (op == TOK_BNOT)
 325                 rez = ~rez;
 326         else if (op == TOK_POST_INC || op == TOK_PRE_INC)
 327                 rez++;
 328         else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
 329                 rez--;
 330         else if (op != TOK_UPLUS) {
 331                 /* Binary operators */
 332                 arith_t right_side_val;
 333                 char bad_second_val;
 334
 335                 /* Binary operators need two arguments */
 336                 if (top_of_stack == numstack)
 337                         goto err;
 338                 /* ...and they pop one */
 339                 NUMPTR = top_of_stack; /* this decrements NUMPTR */
 340
 341                 bad_second_val = top_of_stack->second_val_present;
 342                 if (op == TOK_CONDITIONAL) { /* ? operation */
 343                         /* Make next if (...) protect against
 344                          * $((expr1 ? expr2)) - that is, missing ": expr" */
 345                         bad_second_val = !bad_second_val;
 346                 }
 347                 if (bad_second_val) {
 348                         /* Protect against $((expr <not_?_op> expr1 : expr2)) */
 349                         return "malformed ?: operator";
 350                 }
 351
 352                 top_of_stack--; /* now points to left side */
 353
 354                 if (op != TOK_ASSIGN) {
 355                         /* Resolve left side value (unless the op is '=') */
 356                         err = arith_lookup_val(math_state, top_of_stack);
 357                         if (err)
 358                                 return err;
 359                 }
 360
 361                 right_side_val = rez;
 362                 rez = top_of_stack->val;
 363                 if (op == TOK_CONDITIONAL) /* ? operation */
 364                         rez = (rez ? right_side_val : top_of_stack[1].second_val);
 365                 else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
 366                         if (top_of_stack == numstack) {
 367                                 /* Protect against $((expr : expr)) */
 368                                 return "malformed ?: operator";
 369                         }
 370                         top_of_stack->second_val_present = op;
 371                         top_of_stack->second_val = right_side_val;
 372                 }
 373                 else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
 374                         rez |= right_side_val;
 375                 else if (op == TOK_OR)
 376                         rez = right_side_val || rez;
 377                 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
 378                         rez &= right_side_val;
 379                 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
 380                         rez ^= right_side_val;
 381                 else if (op == TOK_AND)
 382                         rez = rez && right_side_val;
 383                 else if (op == TOK_EQ)
 384                         rez = (rez == right_side_val);
 385                 else if (op == TOK_NE)
 386                         rez = (rez != right_side_val);
 387                 else if (op == TOK_GE)
 388                         rez = (rez >= right_side_val);
 389                 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
 390                         rez >>= right_side_val;
 391                 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
 392                         rez <<= right_side_val;
 393                 else if (op == TOK_GT)
 394                         rez = (rez > right_side_val);
 395                 else if (op == TOK_LT)
 396                         rez = (rez < right_side_val);
 397                 else if (op == TOK_LE)
 398                         rez = (rez <= right_side_val);
 399                 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
 400                         rez *= right_side_val;
 401                 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
 402                         rez += right_side_val;
 403                 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
 404                         rez -= right_side_val;
 405                 else if (op == TOK_ASSIGN || op == TOK_COMMA)
 406                         rez = right_side_val;
 407                 else if (op == TOK_EXPONENT) {
 408                         arith_t c;
 409                         if (right_side_val < 0)
 410                                 return "exponent less than 0";
 411                         c = 1;
 412                         while (--right_side_val >= 0)
 413                                 c *= rez;
 414                         rez = c;
 415                 }
 416                 else if (right_side_val == 0)
 417                         return "divide by zero";
 418                 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
 419                       || op == TOK_REM || op == TOK_REM_ASSIGN) {
 420                         /*
 421                          * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))'
 422                          *
 423                          * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1
 424                          * and thus is not representable.
 425                          * Some CPUs segfault trying such op.
 426                          * Others overflow MAX_POSITIVE_INT+1 to
 427                          * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000).
 428                          * Make sure to at least not SEGV here:
 429                          */
 430                         if (right_side_val == -1
 431                          && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */
 432                         ) {
 433                                 right_side_val = 1;
 434                         }
 435                         if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
 436                                 rez /= right_side_val;
 437                         else {
 438                                 rez %= right_side_val;
 439                         }
 440                 }
 441         }
 442
 443         if (is_assign_op(op)) {
 444                 char buf[sizeof(arith_t)*3 + 2];
 445
 446                 if (top_of_stack->var == NULL) {
 447                         /* Hmm, 1=2 ? */
 448 //TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8
 449                         goto err;
 450                 }
 451                 /* Save to shell variable */
 452                 sprintf(buf, ARITH_FMT, rez);
 453                 setvar(top_of_stack->var, buf);
 454                 /* After saving, make previous value for v++ or v-- */
 455                 if (op == TOK_POST_INC)
 456                         rez--;
 457                 else if (op == TOK_POST_DEC)
 458                         rez++;
 459         }
 460
 461         top_of_stack->val = rez;
 462         /* Erase var name, it is just a number now */
 463         top_of_stack->var = NULL;
 464         return NULL;
 465  err:
 466         return "arithmetic syntax error";
 467 #undef NUMPTR
 468 }
 469
 470 /* longest must be first */
 471 static const char op_tokens[] ALIGN1 = {
 472         '<','<','=',0, TOK_LSHIFT_ASSIGN,
 473         '>','>','=',0, TOK_RSHIFT_ASSIGN,
 474         '<','<',    0, TOK_LSHIFT,
 475         '>','>',    0, TOK_RSHIFT,
 476         '|','|',    0, TOK_OR,
 477         '&','&',    0, TOK_AND,
 478         '!','=',    0, TOK_NE,
 479         '<','=',    0, TOK_LE,
 480         '>','=',    0, TOK_GE,
 481         '=','=',    0, TOK_EQ,
 482         '|','=',    0, TOK_OR_ASSIGN,
 483         '&','=',    0, TOK_AND_ASSIGN,
 484         '*','=',    0, TOK_MUL_ASSIGN,
 485         '/','=',    0, TOK_DIV_ASSIGN,
 486         '%','=',    0, TOK_REM_ASSIGN,
 487         '+','=',    0, TOK_PLUS_ASSIGN,
 488         '-','=',    0, TOK_MINUS_ASSIGN,
 489         '-','-',    0, TOK_POST_DEC,
 490         '^','=',    0, TOK_XOR_ASSIGN,
 491         '+','+',    0, TOK_POST_INC,
 492         '*','*',    0, TOK_EXPONENT,
 493         '!',        0, TOK_NOT,
 494         '<',        0, TOK_LT,
 495         '>',        0, TOK_GT,
 496         '=',        0, TOK_ASSIGN,
 497         '|',        0, TOK_BOR,
 498         '&',        0, TOK_BAND,
 499         '*',        0, TOK_MUL,
 500         '/',        0, TOK_DIV,
 501         '%',        0, TOK_REM,
 502         '+',        0, TOK_ADD,
 503         '-',        0, TOK_SUB,
 504         '^',        0, TOK_BXOR,
 505         /* uniq */
 506         '~',        0, TOK_BNOT,
 507         ',',        0, TOK_COMMA,
 508         '?',        0, TOK_CONDITIONAL,
 509         ':',        0, TOK_CONDITIONAL_SEP,
 510         ')',        0, TOK_RPAREN,
 511         '(',        0, TOK_LPAREN,
 512         0
 513 };
 514 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
 515
 516 #if ENABLE_FEATURE_SH_MATH_BASE
 517 static arith_t strto_arith_t(const char *nptr, char **endptr)
 518 {
 519         unsigned base;
 520         arith_t n;
 521
 522 # if ENABLE_FEATURE_SH_MATH_64
 523         n = strtoull(nptr, endptr, 0);
 524 # else
 525         n = strtoul(nptr, endptr, 0);
 526 # endif
 527         if (**endptr != '#'
 528          || (*nptr < '1' || *nptr > '9')
 529          || (n < 2 || n > 64)
 530         ) {
 531                 return n;
 532         }
 533
 534         /* It's "N#nnnn" or "NN#nnnn" syntax, NN can't start with 0,
 535          * NN is in 2..64 range.
 536          */
 537         base = (unsigned)n;
 538         n = 0;
 539         nptr = *endptr + 1;
 540         /* bash allows "N#" (empty "nnnn" part) */
 541         while (isdigit(*nptr)) {
 542                 /* bash does not check for overflows */
 543                 n = n * base + (*nptr++ - '0');
 544         }
 545         *endptr = (char*)nptr;
 546         return n;
 547 }
 548 #else /* !ENABLE_FEATURE_SH_MATH_BASE */
 549 # if ENABLE_FEATURE_SH_MATH_64
 550 #  define strto_arith_t(nptr, endptr) strtoull(nptr, endptr, 0)
 551 # else
 552 #  define strto_arith_t(nptr, endptr) strtoul(nptr, endptr, 0)
 553 # endif
 554 #endif
 555
 556 static arith_t FAST_FUNC
 557 evaluate_string(arith_state_t *math_state, const char *expr)
 558 {
 559         operator lasttok;
 560         const char *errmsg;
 561         const char *start_expr = expr = skip_whitespace(expr);
 562         unsigned expr_len = strlen(expr) + 2;
 563         /* Stack of integers */
 564         /* The proof that there can be no more than strlen(startbuf)/2+1
 565          * integers in any given correct or incorrect expression
 566          * is left as an exercise to the reader. */
 567         var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
 568         var_or_num_t *numstackptr = numstack;
 569         /* Stack of operator tokens */
 570         operator *const stack = alloca(expr_len * sizeof(stack[0]));
 571         operator *stackptr = stack;
 572
 573         /* Start with a left paren */
 574         *stackptr++ = lasttok = TOK_LPAREN;
 575         errmsg = NULL;
 576
 577         while (1) {
 578                 const char *p;
 579                 operator op;
 580                 operator prec;
 581                 char arithval;
 582
 583                 expr = skip_whitespace(expr);
 584                 arithval = *expr;
 585                 if (arithval == '\0') {
 586                         if (expr == start_expr) {
 587                                 /* Null expression */
 588                                 numstack->val = 0;
 589                                 goto ret;
 590                         }
 591
 592                         /* This is only reached after all tokens have been extracted from the
 593                          * input stream. If there are still tokens on the operator stack, they
 594                          * are to be applied in order. At the end, there should be a final
 595                          * result on the integer stack */
 596
 597                         if (expr != ptr_to_rparen + 1) {
 598                                 /* If we haven't done so already,
 599                                  * append a closing right paren
 600                                  * and let the loop process it */
 601                                 expr = ptr_to_rparen;
 602                                 continue;
 603                         }
 604                         /* At this point, we're done with the expression */
 605                         if (numstackptr != numstack + 1) {
 606                                 /* ...but if there isn't, it's bad */
 607                                 goto err;
 608                         }
 609                         if (numstack->var) {
 610                                 /* expression is $((var)) only, lookup now */
 611                                 errmsg = arith_lookup_val(math_state, numstack);
 612                         }
 613                         goto ret;
 614                 }
 615
 616                 p = endofname(expr);
 617                 if (p != expr) {
 618                         /* Name */
 619                         size_t var_name_size = (p-expr) + 1;  /* +1 for NUL */
 620                         numstackptr->var = alloca(var_name_size);
 621                         safe_strncpy(numstackptr->var, expr, var_name_size);
 622                         expr = p;
 623  num:
 624                         numstackptr->second_val_present = 0;
 625                         numstackptr++;
 626                         lasttok = TOK_NUM;
 627                         continue;
 628                 }
 629
 630                 if (isdigit(arithval)) {
 631                         /* Number */
 632                         numstackptr->var = NULL;
 633                         errno = 0;
 634                         numstackptr->val = strto_arith_t(expr, (char**) &expr);
 635                         if (errno)
 636                                 numstackptr->val = 0; /* bash compat */
 637                         goto num;
 638                 }
 639
 640                 /* Should be an operator */
 641
 642                 /* Special case: NUM-- and NUM++ are not recognized if NUM
 643                  * is a literal number, not a variable. IOW:
 644                  * "a+++v" is a++ + v.
 645                  * "7+++v" is 7 + ++v, not 7++ + v.
 646                  */
 647                 if (lasttok == TOK_NUM && !numstackptr[-1].var /* number literal */
 648                  && (expr[0] == '+' || expr[0] == '-')
 649                  && (expr[1] == expr[0])
 650                 ) {
 651                         //bb_error_msg("special %c%c", expr[0], expr[0]);
 652                         op = (expr[0] == '+' ? TOK_ADD : TOK_SUB);
 653                         expr += 1;
 654                         goto tok_found1;
 655                 }
 656
 657                 p = op_tokens;
 658                 while (1) {
 659                         /* Compare expr to current op_tokens[] element */
 660                         const char *e = expr;
 661                         while (1) {
 662                                 if (*p == '\0') {
 663                                         /* Match: operator is found */
 664                                         expr = e;
 665                                         goto tok_found;
 666                                 }
 667                                 if (*p != *e)
 668                                         break;
 669                                 p++;
 670                                 e++;
 671                         }
 672                         /* No match, go to next element of op_tokens[] */
 673                         while (*p)
 674                                 p++;
 675                         p += 2; /* skip NUL and TOK_foo bytes */
 676                         if (*p == '\0') {
 677                                 /* No next element, operator not found */
 678                                 //math_state->syntax_error_at = expr;
 679                                 goto err;
 680                         }
 681                 }
 682  tok_found:
 683                 op = p[1]; /* fetch TOK_foo value */
 684  tok_found1:
 685                 /* NB: expr now points past the operator */
 686
 687                 /* post grammar: a++ reduce to num */
 688                 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
 689                         lasttok = TOK_NUM;
 690
 691                 /* Plus and minus are binary (not unary) _only_ if the last
 692                  * token was a number, or a right paren (which pretends to be
 693                  * a number, since it evaluates to one). Think about it.
 694                  * It makes sense. */
 695                 if (lasttok != TOK_NUM) {
 696                         switch (op) {
 697                         case TOK_ADD:
 698                                 op = TOK_UPLUS;
 699                                 break;
 700                         case TOK_SUB:
 701                                 op = TOK_UMINUS;
 702                                 break;
 703                         case TOK_POST_INC:
 704                                 op = TOK_PRE_INC;
 705                                 break;
 706                         case TOK_POST_DEC:
 707                                 op = TOK_PRE_DEC;
 708                                 break;
 709                         }
 710                 }
 711                 /* We don't want an unary operator to cause recursive descent on the
 712                  * stack, because there can be many in a row and it could cause an
 713                  * operator to be evaluated before its argument is pushed onto the
 714                  * integer stack.
 715                  * But for binary operators, "apply" everything on the operator
 716                  * stack until we find an operator with a lesser priority than the
 717                  * one we have just extracted. If op is right-associative,
 718                  * then stop "applying" on the equal priority too.
 719                  * Left paren is given the lowest priority so it will never be
 720                  * "applied" in this way.
 721                  */
 722                 prec = PREC(op);
 723                 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
 724                         /* not left paren or unary */
 725                         if (lasttok != TOK_NUM) {
 726                                 /* binary op must be preceded by a num */
 727                                 goto err;
 728                         }
 729                         while (stackptr != stack) {
 730                                 operator prev_op = *--stackptr;
 731                                 if (op == TOK_RPAREN) {
 732                                         /* The algorithm employed here is simple: while we don't
 733                                          * hit an open paren nor the bottom of the stack, pop
 734                                          * tokens and apply them */
 735                                         if (prev_op == TOK_LPAREN) {
 736                                                 /* Any operator directly after a
 737                                                  * close paren should consider itself binary */
 738                                                 lasttok = TOK_NUM;
 739                                                 goto next;
 740                                         }
 741                                 } else {
 742                                         operator prev_prec = PREC(prev_op);
 743                                         fix_assignment_prec(prec);
 744                                         fix_assignment_prec(prev_prec);
 745                                         if (prev_prec < prec
 746                                          || (prev_prec == prec && is_right_associative(prec))
 747                                         ) {
 748                                                 stackptr++;
 749                                                 break;
 750                                         }
 751                                 }
 752                                 errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
 753                                 if (errmsg)
 754                                         goto err_with_custom_msg;
 755                         }
 756                         if (op == TOK_RPAREN)
 757                                 goto err;
 758                 }
 759
 760                 /* Push this operator to the stack and remember it */
 761                 *stackptr++ = lasttok = op;
 762  next: ;
 763         } /* while (1) */
 764
 765  err:
 766         errmsg = "arithmetic syntax error";
 767  err_with_custom_msg:
 768         numstack->val = -1;
 769  ret:
 770         math_state->errmsg = errmsg;
 771         return numstack->val;
 772 }
 773
 774 arith_t FAST_FUNC
 775 arith(arith_state_t *math_state, const char *expr)
 776 {
 777         math_state->errmsg = NULL;
 778         math_state->list_of_recursed_names = NULL;
 779         return evaluate_string(math_state, expr);
 780 }
 781
 782 /*
 783  * Copyright (c) 1989, 1991, 1993, 1994
 784  *      The Regents of the University of California.  All rights reserved.
 785  *
 786  * This code is derived from software contributed to Berkeley by
 787  * Kenneth Almquist.
 788  *
 789  * Redistribution and use in source and binary forms, with or without
 790  * modification, are permitted provided that the following conditions
 791  * are met:
 792  * 1. Redistributions of source code must retain the above copyright
 793  *    notice, this list of conditions and the following disclaimer.
 794  * 2. Redistributions in binary form must reproduce the above copyright
 795  *    notice, this list of conditions and the following disclaimer in the
 796  *    documentation and/or other materials provided with the distribution.
 797  * 3. Neither the name of the University nor the names of its contributors
 798  *    may be used to endorse or promote products derived from this software
 799  *    without specific prior written permission.
 800  *
 801  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND
 802  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 803  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 804  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 805  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 806  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 807  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 808  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 809  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 810  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 811  * SUCH DAMAGE.
 812  */