libbb/arith.c

   1 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
   2
   3    Permission is hereby granted, free of charge, to any person obtaining
   4    a copy of this software and associated documentation files (the
   5    "Software"), to deal in the Software without restriction, including
   6    without limitation the rights to use, copy, modify, merge, publish,
   7    distribute, sublicense, and/or sell copies of the Software, and to
   8    permit persons to whom the Software is furnished to do so, subject to
   9    the following conditions:
  10
  11    The above copyright notice and this permission notice shall be
  12    included in all copies or substantial portions of the Software.
  13
  14    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  15    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  16    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  17    IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  18    CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  19    TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  20    SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21 */
  22
  23 /* This is my infix parser/evaluator. It is optimized for size, intended
  24  * as a replacement for yacc-based parsers. However, it may well be faster
  25  * than a comparable parser writen in yacc. The supported operators are
  26  * listed in #defines below. Parens, order of operations, and error handling
  27  * are supported. This code is threadsafe. The exact expression format should
  28  * be that which POSIX specifies for shells. */
  29
  30 /* The code uses a simple two-stack algorithm. See
  31  * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
  32  * for a detailed explaination of the infix-to-postfix algorithm on which
  33  * this is based (this code differs in that it applies operators immediately
  34  * to the stack instead of adding them to a queue to end up with an
  35  * expression). */
  36
  37 /* To use the routine, call it with an expression string and error return
  38  * pointer */
  39
  40 /*
  41  * Aug 24, 2001              Manuel Novoa III
  42  *
  43  * Reduced the generated code size by about 30% (i386) and fixed several bugs.
  44  *
  45  * 1) In arith_apply():
  46  *    a) Cached values of *numptr and &(numptr[-1]).
  47  *    b) Removed redundant test for zero denominator.
  48  *
  49  * 2) In arith():
  50  *    a) Eliminated redundant code for processing operator tokens by moving
  51  *       to a table-based implementation.  Also folded handling of parens
  52  *       into the table.
  53  *    b) Combined all 3 loops which called arith_apply to reduce generated
  54  *       code size at the cost of speed.
  55  *
  56  * 3) The following expressions were treated as valid by the original code:
  57  *       1()  ,    0!  ,    1 ( *3 )   .
  58  *    These bugs have been fixed by internally enclosing the expression in
  59  *    parens and then checking that all binary ops and right parens are
  60  *    preceded by a valid expression (NUM_TOKEN).
  61  *
  62  * Note: It may be desireable to replace Aaron's test for whitespace with
  63  * ctype's isspace() if it is used by another busybox applet or if additional
  64  * whitespace chars should be considered.  Look below the "#include"s for a
  65  * precompiler test.
  66  */
  67
  68 /*
  69  * Aug 26, 2001              Manuel Novoa III
  70  *
  71  * Return 0 for null expressions.  Pointed out by vodz.
  72  *
  73  * Merge in Aaron's comments previously posted to the busybox list,
  74  * modified slightly to take account of my changes to the code.
  75  *
  76  * TODO: May want to allow access to variables in the arith code.
  77  *       This would:
  78  *       1) allow us to evaluate $A as 0 if A isn't set (although this
  79  *          would require changes to ash.c too).
  80  *       2) allow us to write expressions as $(( A + 2 )).
  81  *       This could be done using a callback function passed to the
  82  *       arith() function of by requiring such a function with fixed
  83  *       name as an extern.
  84  */
  85
  86 #include <stdlib.h>
  87 #include <string.h>
  88 #include <ctype.h>
  89 #include "libbb.h"
  90
  91 /*
  92  * Use "#if 1" below for Aaron's original test for whitespace.
  93  * Use "#if 0" for ctype's isspace().
  94  * */
  95 #if 1
  96 #undef isspace
  97 #define isspace(arithval) \
  98         (arithval == ' ' || arithval == '\n' || arithval == '\t')
  99 #endif
 100
 101 typedef char operator;
 102
 103 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
 104  * precedence, and high 3 are an ID unique accross operators of that
 105  * precedence. The ID portion is so that multiple operators can have the
 106  * same precedence, ensuring that the leftmost one is evaluated first.
 107  * Consider * and /. */
 108
 109 #define tok_decl(prec,id) (((id)<<5)|(prec))
 110 #define PREC(op) ((op)&0x1F)
 111
 112 #define TOK_LPAREN tok_decl(0,0)
 113
 114 #define TOK_OR tok_decl(1,0)
 115
 116 #define TOK_AND tok_decl(2,0)
 117
 118 #define TOK_BOR tok_decl(3,0)
 119
 120 #define TOK_BXOR tok_decl(4,0)
 121
 122 #define TOK_BAND tok_decl(5,0)
 123
 124 #define TOK_EQ tok_decl(6,0)
 125 #define TOK_NE tok_decl(6,1)
 126
 127 #define TOK_LT tok_decl(7,0)
 128 #define TOK_GT tok_decl(7,1)
 129 #define TOK_GE tok_decl(7,2)
 130 #define TOK_LE tok_decl(7,3)
 131
 132 #define TOK_LSHIFT tok_decl(8,0)
 133 #define TOK_RSHIFT tok_decl(8,1)
 134
 135 #define TOK_ADD tok_decl(9,0)
 136 #define TOK_SUB tok_decl(9,1)
 137
 138 #define TOK_MUL tok_decl(10,0)
 139 #define TOK_DIV tok_decl(10,1)
 140 #define TOK_REM tok_decl(10,2)
 141
 142 /* For now all unary operators have the same precedence, and that's used to
 143  * identify them as unary operators */
 144 #define UNARYPREC 14
 145 #define TOK_BNOT tok_decl(UNARYPREC,0)
 146 #define TOK_NOT tok_decl(UNARYPREC,1)
 147 #define TOK_UMINUS tok_decl(UNARYPREC,2)
 148 #define TOK_UPLUS tok_decl(UNARYPREC,3)
 149
 150 #define TOK_NUM tok_decl(15,0)
 151 #define TOK_RPAREN tok_decl(15,1)
 152 #define TOK_ERROR  tok_decl(15,2)       /* just a place-holder really */
 153
 154 #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr)
 155 #define NUMPTR (*numstackptr)
 156
 157 /* "applying" a token means performing it on the top elements on the integer
 158  * stack. For a unary operator it will only change the top element, but a
 159  * binary operator will pop two arguments and push a result */
 160 static short arith_apply(operator    op, long *numstack, long **numstackptr)
 161 {
 162         long numptr_val;
 163         long *NUMPTR_M1;
 164
 165         if (NUMPTR == numstack) goto err; /* There is no operator that can work
 166                                                                                  without arguments */
 167         NUMPTR_M1 = NUMPTR - 1;
 168         if (op == TOK_UMINUS)
 169                 *NUMPTR_M1 *= -1;
 170         else if (op == TOK_NOT)
 171                 *NUMPTR_M1 = !(*NUMPTR_M1);
 172         else if (op == TOK_BNOT)
 173                 *NUMPTR_M1 = ~(*NUMPTR_M1);
 174         else if (op != TOK_UPLUS) {
 175                 /* Binary operators */
 176         if (NUMPTR_M1 == numstack) goto err; /* ... and binary operators need two
 177                                                                                    arguments */
 178         numptr_val = *--NUMPTR;         /* ... and they pop one */
 179                 NUMPTR_M1 = NUMPTR - 1;
 180         if (op == TOK_BOR)
 181                         *NUMPTR_M1 |= numptr_val;
 182         else if (op == TOK_OR)
 183                         *NUMPTR_M1 = numptr_val || *NUMPTR_M1;
 184         else if (op == TOK_BAND)
 185                         *NUMPTR_M1 &= numptr_val;
 186         else if (op == TOK_AND)
 187                         *NUMPTR_M1 = *NUMPTR_M1 && numptr_val;
 188         else if (op == TOK_EQ)
 189                         *NUMPTR_M1 = (*NUMPTR_M1 == numptr_val);
 190         else if (op == TOK_NE)
 191                         *NUMPTR_M1 = (*NUMPTR_M1 != numptr_val);
 192         else if (op == TOK_GE)
 193                         *NUMPTR_M1 = (*NUMPTR_M1 >= numptr_val);
 194         else if (op == TOK_RSHIFT)
 195                         *NUMPTR_M1 >>= numptr_val;
 196         else if (op == TOK_LSHIFT)
 197                         *NUMPTR_M1 <<= numptr_val;
 198         else if (op == TOK_GT)
 199                         *NUMPTR_M1 = (*NUMPTR_M1 > numptr_val);
 200         else if (op == TOK_LT)
 201                         *NUMPTR_M1 = (*NUMPTR_M1 < numptr_val);
 202         else if (op == TOK_LE)
 203                         *NUMPTR_M1 = (*NUMPTR_M1 <= numptr_val);
 204         else if (op == TOK_MUL)
 205                         *NUMPTR_M1 *= numptr_val;
 206         else if (op == TOK_ADD)
 207                         *NUMPTR_M1 += numptr_val;
 208         else if (op == TOK_SUB)
 209                         *NUMPTR_M1 -= numptr_val;
 210         else if(numptr_val==0)          /* zero divisor check */
 211                         return -2;
 212         else if (op == TOK_DIV)
 213                         *NUMPTR_M1 /= numptr_val;
 214         else if (op == TOK_REM)
 215                         *NUMPTR_M1 %= numptr_val;
 216                 /* WARNING!!!  WARNING!!!  WARNING!!! */
 217                 /* Any new operators should be added BEFORE the zero divisor check! */
 218         }
 219         return 0;
 220 err: return(-1);
 221 }
 222
 223 static const char endexpression[] = ")";
 224
 225 /* + and - (in that order) must be last */
 226 static const char op_char[] = "!<>=|&*/%~()+-";
 227 static const char op_token[] = {
 228         /* paired with equal */
 229         TOK_NE, TOK_LE, TOK_GE,
 230         /* paired with self -- note: ! is special-cased below*/
 231         TOK_ERROR, TOK_LSHIFT, TOK_RSHIFT, TOK_EQ, TOK_OR, TOK_AND,
 232         /* singles */
 233         TOK_NOT, TOK_LT, TOK_GT, TOK_ERROR, TOK_BOR, TOK_BAND,
 234         TOK_MUL, TOK_DIV, TOK_REM, TOK_BNOT, TOK_LPAREN, TOK_RPAREN,
 235         TOK_ADD, TOK_SUB, TOK_UPLUS, TOK_UMINUS
 236 };
 237
 238 #define NUM_PAIR_EQUAL  3
 239 #define NUM_PAIR_SAME   6
 240
 241 extern long arith (const char *expr, int *errcode)
 242 {
 243         register char arithval; /* Current character under analysis */
 244         operator    lasttok, op;
 245         unsigned char prec;
 246
 247         const char *p = endexpression;
 248
 249         size_t datasizes = strlen(expr) + 2;
 250
 251         /* Stack of integers */
 252         /* The proof that there can be no more than strlen(startbuf)/2+1 integers
 253          * in any given correct or incorrect expression is left as an excersize to
 254          * the reader. */
 255         long *numstack = alloca(((datasizes)/2)*sizeof(long)),
 256                 *numstackptr = numstack;
 257         /* Stack of operator tokens */
 258         operator *stack = alloca((datasizes) * sizeof(operator)),
 259                 *stackptr = stack;
 260
 261         *numstack = 0;
 262         *stackptr++ = lasttok = TOK_LPAREN;     /* start off with a left paren */
 263
 264   loop:
 265         if ((arithval = *expr) == 0) {
 266                 if (p == endexpression) { /* Null expression. */
 267                         *errcode = 0;
 268                         return *numstack;
 269                 }
 270
 271                 /* This is only reached after all tokens have been extracted from the
 272                  * input stream. If there are still tokens on the operator stack, they
 273                  * are to be applied in order. At the end, there should be a final
 274                  * result on the integer stack */
 275
 276                 if (expr != endexpression + 1) {        /* If we haven't done so already, */
 277                         expr = endexpression;   /* append a closing right paren */
 278                         goto loop;      /* and let the loop process it. */
 279                 }
 280                 /* At this point, we're done with the expression. */
 281                 if (numstackptr != numstack+1) {/* ... but if there isn't, it's bad */
 282                   err:
 283                         return (*errcode = -1);
 284                         /* NOTREACHED */
 285                 }
 286                 return *numstack;
 287         } else {
 288                 /* Continue processing the expression.  */
 289                 if (isspace(arithval)) {
 290                         goto prologue;          /* Skip whitespace */
 291                 }
 292                 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
 293                         *numstackptr++ = strtol(expr, (char **) &expr, 10);
 294                         lasttok = TOK_NUM;
 295                         goto loop;
 296                 }
 297 #if 1
 298                 if ((p = strchr(op_char, arithval)) == NULL) {
 299                         goto err;
 300                 }
 301 #else
 302             for ( p=op_char ; *p != arithval ; p++ ) {
 303                         if (!*p) {
 304                                 goto err;
 305                         }
 306                 }
 307 #endif
 308                 p = op_token + (int)(p - op_char);
 309                 ++expr;
 310                 if ((p >= op_token + NUM_PAIR_EQUAL) || (*expr != '=')) {
 311                         p += NUM_PAIR_EQUAL;
 312                         if ((p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL)
 313                                 || (*expr != arithval) || (arithval == '!')) {
 314                                 --expr;
 315                                 if (arithval == '=') { /* single = */
 316                                         goto err;
 317                                 }
 318                                 p += NUM_PAIR_SAME;
 319                                 /* Plus and minus are binary (not unary) _only_ if the last
 320                                  * token was as number, or a right paren (which pretends to be
 321                                  * a number, since it evaluates to one). Think about it.
 322                                  * It makes sense. */
 323                                 if ((lasttok != TOK_NUM)
 324                                         && (p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL
 325                                                 + sizeof(op_char) - 2)) {
 326                                         p += 2; /* Unary plus or minus */
 327                                 }
 328                         }
 329                 }
 330                 op = *p;
 331
 332                 /* We don't want a unary operator to cause recursive descent on the
 333                  * stack, because there can be many in a row and it could cause an
 334                  * operator to be evaluated before its argument is pushed onto the
 335                  * integer stack. */
 336                 /* But for binary operators, "apply" everything on the operator
 337                  * stack until we find an operator with a lesser priority than the
 338                  * one we have just extracted. */
 339                 /* Left paren is given the lowest priority so it will never be
 340                  * "applied" in this way */
 341                 prec = PREC(op);
 342                 if ((prec > 0) && (prec != UNARYPREC)) { /* not left paren or unary */
 343                         if (lasttok != TOK_NUM) { /* binary op must be preceded by a num */
 344                                 goto err;
 345                         }
 346                         while (stackptr != stack) {
 347                                 if (op == TOK_RPAREN) {
 348                                         /* The algorithm employed here is simple: while we don't
 349                                          * hit an open paren nor the bottom of the stack, pop
 350                                          * tokens and apply them */
 351                                         if (stackptr[-1] == TOK_LPAREN) {
 352                                                 --stackptr;
 353                                                 lasttok = TOK_NUM; /* Any operator directly after a */
 354                                                 /* close paren should consider itself binary */
 355                                                 goto prologue;
 356                                         }
 357                                 } else if (PREC(stackptr[-1]) < prec) {
 358                                         break;
 359                                 }
 360                                 *errcode = ARITH_APPLY(*--stackptr);
 361                                 if(*errcode) return *errcode;
 362                         }
 363                         if (op == TOK_RPAREN) {
 364                                 goto err;
 365                         }
 366                 }
 367
 368                 /* Push this operator to the stack and remember it. */
 369                 *stackptr++ = lasttok = op;
 370
 371           prologue:
 372                 ++expr;
 373                 goto loop;
 374         }
 375 }