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);
 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+1) * sizeof(operator)),
 259                 *stackptr = stack;
 260
 261         *stackptr++ = lasttok = TOK_LPAREN;     /* start off with a left paren */
 262
 263  loop:
 264         if ((arithval = *expr) == 0) {
 265                 if (p == endexpression) { /* Null expression. */
 266                         return (*errcode = 0);
 267                 }
 268
 269                 /* This is only reached after all tokens have been extracted from the
 270                  * input stream. If there are still tokens on the operator stack, they
 271                  * are to be applied in order. At the end, there should be a final
 272                  * result on the integer stack */
 273
 274                 if (expr != endexpression + 1) { /* If we haven't done so already, */
 275                         expr = endexpression;   /* append a closing right paren */
 276                         goto loop;                              /* and let the loop process it. */
 277                 }
 278                 /* At this point, we're done with the expression. */
 279                 if (numstackptr != numstack+1) {/* ... but if there isn't, it's bad */
 280                 err:
 281                         return (*errcode = -1);
 282                         /* NOTREACHED */
 283                 }
 284                 return *numstack;
 285         } else {
 286                 /* Continue processing the expression.  */
 287                 if (isspace(arithval)) {
 288                         goto prologue;          /* Skip whitespace */
 289                 }
 290                 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
 291                         *numstackptr++ = strtol(expr, (char **) &expr, 10);
 292                         lasttok = TOK_NUM;
 293                         goto loop;
 294                 }
 295 #if 1
 296                 if ((p = strchr(op_char, arithval)) == NULL) {
 297                         goto err;
 298                 }
 299 #else
 300             for ( p=op_char ; *p != arithval ; p++ ) {
 301                         if (!*p) {
 302                                 goto err;
 303                         }
 304                 }
 305 #endif
 306                 p = op_token + (int)(p - op_char);
 307                 ++expr;
 308                 if ((p >= op_token + NUM_PAIR_EQUAL) || (*expr != '=')) {
 309                         p += NUM_PAIR_EQUAL;
 310                         if ((p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL)
 311                                 || (*expr != arithval) || (arithval == '!')) {
 312                                 --expr;
 313                                 if (arithval == '=') { /* single = */
 314                                         goto err;
 315                                 }
 316                                 p += NUM_PAIR_SAME;
 317                                 /* Plus and minus are binary (not unary) _only_ if the last
 318                                  * token was as number, or a right paren (which pretends to be
 319                                  * a number, since it evaluates to one). Think about it.
 320                                  * It makes sense. */
 321                                 if ((lasttok != TOK_NUM)
 322                                         && (p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL
 323                                                 + sizeof(op_char) - 2)) {
 324                                         p += 2; /* Unary plus or minus */
 325                                 }
 326                         }
 327                 }
 328                 op = *p;
 329
 330                 /* We don't want a unary operator to cause recursive descent on the
 331                  * stack, because there can be many in a row and it could cause an
 332                  * operator to be evaluated before its argument is pushed onto the
 333                  * integer stack. */
 334                 /* But for binary operators, "apply" everything on the operator
 335                  * stack until we find an operator with a lesser priority than the
 336                  * one we have just extracted. */
 337                 /* Left paren is given the lowest priority so it will never be
 338                  * "applied" in this way */
 339                 prec = PREC(op);
 340                 if ((prec > 0) && (prec != UNARYPREC)) { /* not left paren or unary */
 341                         if (lasttok != TOK_NUM) { /* binary op must be preceded by a num */
 342                                 goto err;
 343                         }
 344                         while (stackptr != stack) {
 345                                 if (op == TOK_RPAREN) {
 346                                         /* The algorithm employed here is simple: while we don't
 347                                          * hit an open paren nor the bottom of the stack, pop
 348                                          * tokens and apply them */
 349                                         if (stackptr[-1] == TOK_LPAREN) {
 350                                                 --stackptr;
 351                                                 lasttok = TOK_NUM; /* Any operator directly after a */
 352                                                                 /* close paren should consider itself binary */
 353                                                 goto prologue;
 354                                         }
 355                                 } else if (PREC(stackptr[-1]) < prec) {
 356                                         break;
 357                                 }
 358                                 *errcode = ARITH_APPLY(*--stackptr);
 359                                 if(*errcode) return *errcode;
 360                         }
 361                         if (op == TOK_RPAREN) {
 362                                 goto err;
 363                         }
 364                 }
 365
 366                 /* Push this operator to the stack and remember it. */
 367                 *stackptr++ = lasttok = op;
 368
 369         prologue:
 370                 ++expr;
 371                 goto loop;
 372         }
 373 }