shell/math.c

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