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