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                 if(*NUMPTR==0)
 124                         return -2;
 125                 NUMPTR[-1] /= *NUMPTR;
 126                 }
 127         else if (op == TOK_REM) {
 128                 if(*NUMPTR==0)
 129                         return -2;
 130                 NUMPTR[-1] %= *NUMPTR;
 131                 }
 132         else if (op == TOK_ADD)
 133                 NUMPTR[-1] += *NUMPTR;
 134         else if (op == TOK_SUB)
 135                 NUMPTR[-1] -= *NUMPTR;
 136         }
 137         return 0;
 138 err: return(-1);
 139 }
 140
 141 extern long arith (const char *startbuf, int *errcode)
 142 {
 143         register char arithval;
 144         const char *expr = startbuf;
 145
 146         operator lasttok = TOK_MUL, op;
 147         size_t datasizes = strlen(startbuf);
 148         unsigned char prec;
 149
 150         long *numstack, *numstackptr;
 151         operator *stack = alloca(datasizes * sizeof(operator)), *stackptr = stack;
 152
 153         *errcode = 0;
 154         numstack = alloca((datasizes/2+1)*sizeof(long)), numstackptr = numstack;
 155
 156         while ((arithval = *expr)) {
 157                 if (arithval == ' ' || arithval == '\n' || arithval == '\t')
 158                         goto prologue;
 159                 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
 160                         *numstackptr++ = strtol(expr, (char **) &expr, 10);
 161                         lasttok = TOK_NUM;
 162                         continue;
 163                 } if (arithval == '(') {
 164                         *stackptr++ = TOK_LPAREN;
 165                         lasttok = TOK_LPAREN;
 166                         goto prologue;
 167                 } if (arithval == ')') {
 168                         lasttok = TOK_NUM;
 169                         while (stackptr != stack) {
 170                                 op = *--stackptr;
 171                                 if (op == TOK_LPAREN)
 172                                         goto prologue;
 173                                 *errcode = ARITH_APPLY(op);
 174                                 if(*errcode) return *errcode;
 175                         }
 176                         goto err; /* Mismatched parens */
 177                 } if (arithval == '|') {
 178                         if (*++expr == '|')
 179                                 op = TOK_OR;
 180                         else {
 181                                 --expr;
 182                                 op = TOK_BOR;
 183                         }
 184                 } else if (arithval == '&') {
 185                         if (*++expr == '&')
 186                                 op = TOK_AND;
 187                         else {
 188                                 --expr;
 189                                 op = TOK_BAND;
 190                         }
 191                 } else if (arithval == '=') {
 192                         if (*++expr != '=') goto err; /* Unknown token */
 193                         op = TOK_EQ;
 194                 } else if (arithval == '!') {
 195                         if (*++expr == '=')
 196                                 op = TOK_NE;
 197                         else {
 198                                 --expr;
 199                                 op = TOK_NOT;
 200                         }
 201                 } else if (arithval == '>') {
 202                         switch (*++expr) {
 203                                 case '=':
 204                                         op = TOK_GE;
 205                                         break;
 206                                 case '>':
 207                                         op = TOK_RSHIFT;
 208                                         break;
 209                                 default:
 210                                         --expr;
 211                                         op = TOK_GT;
 212                         }
 213                 } else if (arithval == '<') {
 214                         switch (*++expr) {
 215                                 case '=':
 216                                         op = TOK_LE;
 217                                         break;
 218                                 case '<':
 219                                         op = TOK_LSHIFT;
 220                                         break;
 221                                 default:
 222                                         --expr;
 223                                         op = TOK_LT;
 224                         }
 225                 } else if (arithval == '*')
 226                         op = TOK_MUL;
 227                 else if (arithval == '/')
 228                         op = TOK_DIV;
 229                 else if (arithval == '%')
 230                         op = TOK_REM;
 231                 else if (arithval == '+') {
 232                         if (lasttok != TOK_NUM) goto prologue; /* Unary plus */
 233                         op = TOK_ADD;
 234                 } else if (arithval == '-')
 235                         op = (lasttok == TOK_NUM) ? TOK_SUB : TOK_UMINUS;
 236                 else if (arithval == '~')
 237                         op = TOK_BNOT;
 238                 else goto err; /* Unknown token */
 239
 240                 prec = PREC(op);
 241                 if (prec != UNARYPREC)
 242                         while (stackptr != stack && PREC(stackptr[-1]) >= prec) {
 243                                 *errcode = ARITH_APPLY(*--stackptr);
 244                                 if(*errcode) return *errcode;
 245                         }
 246                 *stackptr++ = op;
 247                 lasttok = op;
 248 prologue: ++expr;
 249         } /* yay */
 250
 251         while (stackptr != stack) {
 252                 *errcode = ARITH_APPLY(*--stackptr);
 253                 if(*errcode) return *errcode;
 254         }
 255         if (numstackptr != numstack+1) {
 256 err:
 257             *errcode = -1;
 258             return -1;
 259          /* NOTREACHED */
 260         }
 261
 262         return *numstack;
 263 }