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. */
  28
  29 /* To use the routine, call it with an expression string. It returns an
  30  * integer result. You will also need to define an "error" function
  31  * that takes printf arguments and _does not return_, or modify the code
  32  * to use another error mechanism. */
  33
  34 #include <stdlib.h>
  35 #include <string.h>
  36 #include "libbb.h"
  37
  38 typedef char operator;
  39
  40 #define tok_decl(prec,id) (((id)<<5)|(prec))
  41 #define PREC(op) ((op)&0x1F)
  42
  43 #define TOK_LPAREN tok_decl(0,0)
  44
  45 #define TOK_OR tok_decl(1,0)
  46
  47 #define TOK_AND tok_decl(2,0)
  48
  49 #define TOK_BOR tok_decl(3,0)
  50
  51 #define TOK_BXOR tok_decl(4,0)
  52
  53 #define TOK_BAND tok_decl(5,0)
  54
  55 #define TOK_EQ tok_decl(6,0)
  56 #define TOK_NE tok_decl(6,1)
  57
  58 #define TOK_LT tok_decl(7,0)
  59 #define TOK_GT tok_decl(7,1)
  60 #define TOK_GE tok_decl(7,2)
  61 #define TOK_LE tok_decl(7,3)
  62
  63 #define TOK_LSHIFT tok_decl(8,0)
  64 #define TOK_RSHIFT tok_decl(8,1)
  65
  66 #define TOK_ADD tok_decl(9,0)
  67 #define TOK_SUB tok_decl(9,1)
  68
  69 #define TOK_MUL tok_decl(10,0)
  70 #define TOK_DIV tok_decl(10,1)
  71 #define TOK_REM tok_decl(10,2)
  72
  73 #define UNARYPREC 14
  74 #define TOK_BNOT tok_decl(UNARYPREC,0)
  75 #define TOK_NOT tok_decl(UNARYPREC,1)
  76 #define TOK_UMINUS tok_decl(UNARYPREC,2)
  77
  78 #define TOK_NUM tok_decl(15,0)
  79
  80 #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr)
  81 #define NUMPTR (*numstackptr)
  82 static short arith_apply(operator op, long *numstack, long **numstackptr)
  83 {
  84         if (NUMPTR == numstack) goto err;
  85         if (op == TOK_UMINUS)
  86                 NUMPTR[-1] *= -1;
  87         else if (op == TOK_NOT)
  88                 NUMPTR[-1] = !(NUMPTR[-1]);
  89         else if (op == TOK_BNOT)
  90                 NUMPTR[-1] = ~(NUMPTR[-1]);
  91
  92         /* Binary operators */
  93         else {
  94         if (NUMPTR-1 == numstack) goto err;
  95         --NUMPTR;
  96         if (op == TOK_BOR)
  97                 NUMPTR[-1] |= *NUMPTR;
  98         else if (op == TOK_OR)
  99                 NUMPTR[-1] = *NUMPTR || NUMPTR[-1];
 100         else if (op == TOK_BAND)
 101                 NUMPTR[-1] &= *NUMPTR;
 102         else if (op == TOK_AND)
 103                 NUMPTR[-1] = NUMPTR[-1] && *NUMPTR;
 104         else if (op == TOK_EQ)
 105                 NUMPTR[-1] = (NUMPTR[-1] == *NUMPTR);
 106         else if (op == TOK_NE)
 107                 NUMPTR[-1] = (NUMPTR[-1] != *NUMPTR);
 108         else if (op == TOK_GE)
 109                 NUMPTR[-1] = (NUMPTR[-1] >= *NUMPTR);
 110         else if (op == TOK_RSHIFT)
 111                 NUMPTR[-1] >>= *NUMPTR;
 112         else if (op == TOK_LSHIFT)
 113                 NUMPTR[-1] <<= *NUMPTR;
 114         else if (op == TOK_GT)
 115                 NUMPTR[-1] = (NUMPTR[-1] > *NUMPTR);
 116         else if (op == TOK_LT)
 117                 NUMPTR[-1] = (NUMPTR[-1] < *NUMPTR);
 118         else if (op == TOK_LE)
 119                 NUMPTR[-1] = (NUMPTR[-1] <= *NUMPTR);
 120         else if (op == TOK_MUL)
 121                 NUMPTR[-1] *= *NUMPTR;
 122         else if (op == TOK_DIV)
 123                 NUMPTR[-1] /= *NUMPTR;
 124         else if (op == TOK_REM)
 125                 NUMPTR[-1] %= *NUMPTR;
 126         else if (op == TOK_ADD)
 127                 NUMPTR[-1] += *NUMPTR;
 128         else if (op == TOK_SUB)
 129                 NUMPTR[-1] -= *NUMPTR;
 130         }
 131         return 0;
 132 err: return(1);
 133 }
 134
 135 extern long arith (const char *startbuf)
 136 {
 137         register char arithval;
 138         const char *expr = startbuf;
 139
 140         operator lasttok = TOK_MUL, op;
 141         size_t datasizes = strlen(startbuf);
 142         unsigned char prec;
 143
 144         long *numstack, *numstackptr;
 145
 146         operator *stack = alloca(datasizes * sizeof(operator)), *stackptr = stack;
 147         numstack = alloca((datasizes/2+1)*sizeof(long)), numstackptr = numstack;
 148
 149         while ((arithval = *expr)) {
 150                 if (arithval == ' ' || arithval == '\n' || arithval == '\t')
 151                         goto prologue;
 152                 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
 153                         *numstackptr++ = strtol(expr, (char **) &expr, 10);
 154                         lasttok = TOK_NUM;
 155                         continue;
 156                 } if (arithval == '(') {
 157                         *stackptr++ = TOK_LPAREN;
 158                         lasttok = TOK_LPAREN;
 159                         goto prologue;
 160                 } if (arithval == ')') {
 161                         lasttok = TOK_NUM;
 162                         while (stackptr != stack) {
 163                                 op = *--stackptr;
 164                                 if (op == TOK_LPAREN)
 165                                         goto prologue;
 166                                 if(ARITH_APPLY(op)) goto err;
 167                         }
 168                         goto err; /* Mismatched parens */
 169                 } if (arithval == '|') {
 170                         if (*++expr == '|')
 171                                 op = TOK_OR;
 172                         else {
 173                                 --expr;
 174                                 op = TOK_BOR;
 175                         }
 176                 } else if (arithval == '&') {
 177                         if (*++expr == '&')
 178                                 op = TOK_AND;
 179                         else {
 180                                 --expr;
 181                                 op = TOK_BAND;
 182                         }
 183                 } else if (arithval == '=') {
 184                         if (*++expr != '=') goto err; /* Unknown token */
 185                         op = TOK_EQ;
 186                 } else if (arithval == '!') {
 187                         if (*++expr == '=')
 188                                 op = TOK_NE;
 189                         else {
 190                                 --expr;
 191                                 op = TOK_NOT;
 192                         }
 193                 } else if (arithval == '>') {
 194                         switch (*++expr) {
 195                                 case '=':
 196                                         op = TOK_GE;
 197                                         break;
 198                                 case '>':
 199                                         op = TOK_RSHIFT;
 200                                         break;
 201                                 default:
 202                                         --expr;
 203                                         op = TOK_GT;
 204                         }
 205                 } else if (arithval == '<') {
 206                         switch (*++expr) {
 207                                 case '=':
 208                                         op = TOK_LE;
 209                                         break;
 210                                 case '<':
 211                                         op = TOK_LSHIFT;
 212                                         break;
 213                                 default:
 214                                         --expr;
 215                                         op = TOK_LT;
 216                         }
 217                 } else if (arithval == '*')
 218                         op = TOK_MUL;
 219                 else if (arithval == '/')
 220                         op = TOK_DIV;
 221                 else if (arithval == '%')
 222                         op = TOK_REM;
 223                 else if (arithval == '+') {
 224                         if (lasttok != TOK_NUM) goto prologue; /* Unary plus */
 225                         op = TOK_ADD;
 226                 } else if (arithval == '-')
 227                         op = (lasttok == TOK_NUM) ? TOK_SUB : TOK_UMINUS;
 228                 else if (arithval == '~')
 229                         op = TOK_BNOT;
 230                 else goto err; /* Unknown token */
 231
 232                 prec = PREC(op);
 233                 if (prec != UNARYPREC)
 234                         while (stackptr != stack && PREC(stackptr[-1]) >= prec)
 235                                 if(ARITH_APPLY(*--stackptr)) goto err;
 236                 *stackptr++ = op;
 237                 lasttok = op;
 238 prologue: ++expr;
 239         } /* yay */
 240
 241         while (stackptr != stack)
 242                 if(ARITH_APPLY(*--stackptr)) goto err;
 243         if (numstackptr != numstack+1) {
 244 err:
 245             return -1;
 246          /* NOTREACHED */
 247         }
 248
 249         return *numstack;
 250 }