1 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
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:
11 The above copyright notice and this permission notice shall be
12 included in all copies or substantial portions of the Software.
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.
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. */
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
37 /* To use the routine, call it with an expression string and error return
41 * Aug 24, 2001 Manuel Novoa III
43 * Reduced the generated code size by about 30% (i386) and fixed several bugs.
45 * 1) In arith_apply():
46 * a) Cached values of *numptr and &(numptr[-1]).
47 * b) Removed redundant test for zero denominator.
50 * a) Eliminated redundant code for processing operator tokens by moving
51 * to a table-based implementation. Also folded handling of parens
53 * b) Combined all 3 loops which called arith_apply to reduce generated
54 * code size at the cost of speed.
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).
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
69 * Aug 26, 2001 Manuel Novoa III
71 * Return 0 for null expressions. Pointed out by vodz.
73 * Merge in Aaron's comments previously posted to the busybox list,
74 * modified slightly to take account of my changes to the code.
76 * TODO: May want to allow access to variables in the arith code.
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
92 * Use "#if 1" below for Aaron's original test for whitespace.
93 * Use "#if 0" for ctype's isspace().
97 #define isspace(arithval) \
98 (arithval == ' ' || arithval == '\n' || arithval == '\t')
101 typedef char operator;
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 /. */
109 #define tok_decl(prec,id) (((id)<<5)|(prec))
110 #define PREC(op) ((op)&0x1F)
112 #define TOK_LPAREN tok_decl(0,0)
114 #define TOK_OR tok_decl(1,0)
116 #define TOK_AND tok_decl(2,0)
118 #define TOK_BOR tok_decl(3,0)
120 #define TOK_BXOR tok_decl(4,0)
122 #define TOK_BAND tok_decl(5,0)
124 #define TOK_EQ tok_decl(6,0)
125 #define TOK_NE tok_decl(6,1)
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)
132 #define TOK_LSHIFT tok_decl(8,0)
133 #define TOK_RSHIFT tok_decl(8,1)
135 #define TOK_ADD tok_decl(9,0)
136 #define TOK_SUB tok_decl(9,1)
138 #define TOK_MUL tok_decl(10,0)
139 #define TOK_DIV tok_decl(10,1)
140 #define TOK_REM tok_decl(10,2)
142 /* For now all unary operators have the same precedence, and that's used to
143 * identify them as unary operators */
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)
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 */
154 #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr)
155 #define NUMPTR (*numstackptr)
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)
165 if (NUMPTR == numstack) goto err; /* There is no operator that can work
167 NUMPTR_M1 = NUMPTR - 1;
168 if (op == TOK_UMINUS)
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
178 numptr_val = *--NUMPTR; /* ... and they pop one */
179 NUMPTR_M1 = NUMPTR - 1;
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 */
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! */
223 static const char endexpression[] = ")";
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,
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
238 #define NUM_PAIR_EQUAL 3
239 #define NUM_PAIR_SAME 6
241 extern long arith (const char *expr, int *errcode)
243 register char arithval; /* Current character under analysis */
244 operator lasttok, op;
247 const char *p = endexpression;
249 size_t datasizes = strlen(expr) + 2;
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
255 long *numstack = alloca(((datasizes)/2)*sizeof(long)),
256 *numstackptr = numstack;
257 /* Stack of operator tokens */
258 operator *stack = alloca((datasizes) * sizeof(operator)),
262 *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */
265 if ((arithval = *expr) == 0) {
266 if (p == endexpression) { /* Null expression. */
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 */
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. */
280 /* At this point, we're done with the expression. */
281 if (numstackptr != numstack+1) {/* ... but if there isn't, it's bad */
283 return (*errcode = -1);
288 /* Continue processing the expression. */
289 if (isspace(arithval)) {
290 goto prologue; /* Skip whitespace */
292 if ((unsigned)arithval-'0' <= 9) /* isdigit */ {
293 *numstackptr++ = strtol(expr, (char **) &expr, 10);
298 if ((p = strchr(op_char, arithval)) == NULL) {
302 for ( p=op_char ; *p != arithval ; p++ ) {
308 p = op_token + (int)(p - op_char);
310 if ((p >= op_token + NUM_PAIR_EQUAL) || (*expr != '=')) {
312 if ((p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL)
313 || (*expr != arithval) || (arithval == '!')) {
315 if (arithval == '=') { /* single = */
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.
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 */
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
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 */
342 if ((prec > 0) && (prec != UNARYPREC)) { /* not left paren or unary */
343 if (lasttok != TOK_NUM) { /* binary op must be preceded by a num */
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) {
353 lasttok = TOK_NUM; /* Any operator directly after a */
354 /* close paren should consider itself binary */
357 } else if (PREC(stackptr[-1]) < prec) {
360 *errcode = ARITH_APPLY(*--stackptr);
361 if(*errcode) return *errcode;
363 if (op == TOK_RPAREN) {
368 /* Push this operator to the stack and remember it. */
369 *stackptr++ = lasttok = op;