2 * arithmetic code ripped out of ash shell for code sharing
4 * Copyright (c) 1989, 1991, 1993, 1994
5 * The Regents of the University of California. All rights reserved.
7 * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
8 * was re-ported from NetBSD and debianized.
10 * This code is derived from software contributed to Berkeley by
13 * Licensed under the GPL v2 or later, see the file LICENSE in this tarball.
15 * Original BSD copyright notice is retained at the end of this file.
18 * rewrite arith.y to micro stack based cryptic algorithm by
19 * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
21 * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support
24 * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be
25 * used in busybox and size optimizations,
26 * rewrote arith (see notes to this), added locale support,
27 * rewrote dynamic variables.
32 #define a_e_h_t arith_eval_hooks_t
33 #define lookupvar (math_hooks->lookupvar)
34 #define setvar (math_hooks->setvar)
35 #define endofname (math_hooks->endofname)
37 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
39 Permission is hereby granted, free of charge, to any person obtaining
40 a copy of this software and associated documentation files (the
41 "Software"), to deal in the Software without restriction, including
42 without limitation the rights to use, copy, modify, merge, publish,
43 distribute, sublicense, and/or sell copies of the Software, and to
44 permit persons to whom the Software is furnished to do so, subject to
45 the following conditions:
47 The above copyright notice and this permission notice shall be
48 included in all copies or substantial portions of the Software.
50 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
51 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
52 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
53 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
54 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
55 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
56 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
59 /* This is my infix parser/evaluator. It is optimized for size, intended
60 * as a replacement for yacc-based parsers. However, it may well be faster
61 * than a comparable parser written in yacc. The supported operators are
62 * listed in #defines below. Parens, order of operations, and error handling
63 * are supported. This code is thread safe. The exact expression format should
64 * be that which POSIX specifies for shells. */
66 /* The code uses a simple two-stack algorithm. See
67 * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
68 * for a detailed explanation of the infix-to-postfix algorithm on which
69 * this is based (this code differs in that it applies operators immediately
70 * to the stack instead of adding them to a queue to end up with an
73 /* To use the routine, call it with an expression string and error return
77 * Aug 24, 2001 Manuel Novoa III
79 * Reduced the generated code size by about 30% (i386) and fixed several bugs.
81 * 1) In arith_apply():
82 * a) Cached values of *numptr and &(numptr[-1]).
83 * b) Removed redundant test for zero denominator.
86 * a) Eliminated redundant code for processing operator tokens by moving
87 * to a table-based implementation. Also folded handling of parens
89 * b) Combined all 3 loops which called arith_apply to reduce generated
90 * code size at the cost of speed.
92 * 3) The following expressions were treated as valid by the original code:
93 * 1() , 0! , 1 ( *3 ) .
94 * These bugs have been fixed by internally enclosing the expression in
95 * parens and then checking that all binary ops and right parens are
96 * preceded by a valid expression (NUM_TOKEN).
98 * Note: It may be desirable to replace Aaron's test for whitespace with
99 * ctype's isspace() if it is used by another busybox applet or if additional
100 * whitespace chars should be considered. Look below the "#include"s for a
105 * Aug 26, 2001 Manuel Novoa III
107 * Return 0 for null expressions. Pointed out by Vladimir Oleynik.
109 * Merge in Aaron's comments previously posted to the busybox list,
110 * modified slightly to take account of my changes to the code.
115 * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru>
117 * - allow access to variable,
118 * used recursive find value indirection (c=2*2; a="c"; $((a+=2)) produce 6)
119 * - realize assign syntax (VAR=expr, +=, *= etc)
120 * - realize exponentiation (** operator)
121 * - realize comma separated - expr, expr
122 * - realise ++expr --expr expr++ expr--
123 * - realise expr ? expr : expr (but, second expr calculate always)
124 * - allow hexadecimal and octal numbers
125 * - was restored loses XOR operator
126 * - remove one goto label, added three ;-)
127 * - protect $((num num)) as true zero expr (Manuel`s error)
128 * - always use special isspace(), see comment from bash ;-)
131 #define arith_isspace(arithval) \
132 (arithval == ' ' || arithval == '\n' || arithval == '\t')
134 typedef unsigned char operator;
136 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
137 * precedence, and 3 high bits are an ID unique across operators of that
138 * precedence. The ID portion is so that multiple operators can have the
139 * same precedence, ensuring that the leftmost one is evaluated first.
140 * Consider * and /. */
142 #define tok_decl(prec,id) (((id)<<5)|(prec))
143 #define PREC(op) ((op) & 0x1F)
145 #define TOK_LPAREN tok_decl(0,0)
147 #define TOK_COMMA tok_decl(1,0)
149 #define TOK_ASSIGN tok_decl(2,0)
150 #define TOK_AND_ASSIGN tok_decl(2,1)
151 #define TOK_OR_ASSIGN tok_decl(2,2)
152 #define TOK_XOR_ASSIGN tok_decl(2,3)
153 #define TOK_PLUS_ASSIGN tok_decl(2,4)
154 #define TOK_MINUS_ASSIGN tok_decl(2,5)
155 #define TOK_LSHIFT_ASSIGN tok_decl(2,6)
156 #define TOK_RSHIFT_ASSIGN tok_decl(2,7)
158 #define TOK_MUL_ASSIGN tok_decl(3,0)
159 #define TOK_DIV_ASSIGN tok_decl(3,1)
160 #define TOK_REM_ASSIGN tok_decl(3,2)
162 /* all assign is right associativity and precedence eq, but (7+3)<<5 > 256 */
163 #define convert_prec_is_assing(prec) do { if (prec == 3) prec = 2; } while (0)
165 /* conditional is right associativity too */
166 #define TOK_CONDITIONAL tok_decl(4,0)
167 #define TOK_CONDITIONAL_SEP tok_decl(4,1)
169 #define TOK_OR tok_decl(5,0)
171 #define TOK_AND tok_decl(6,0)
173 #define TOK_BOR tok_decl(7,0)
175 #define TOK_BXOR tok_decl(8,0)
177 #define TOK_BAND tok_decl(9,0)
179 #define TOK_EQ tok_decl(10,0)
180 #define TOK_NE tok_decl(10,1)
182 #define TOK_LT tok_decl(11,0)
183 #define TOK_GT tok_decl(11,1)
184 #define TOK_GE tok_decl(11,2)
185 #define TOK_LE tok_decl(11,3)
187 #define TOK_LSHIFT tok_decl(12,0)
188 #define TOK_RSHIFT tok_decl(12,1)
190 #define TOK_ADD tok_decl(13,0)
191 #define TOK_SUB tok_decl(13,1)
193 #define TOK_MUL tok_decl(14,0)
194 #define TOK_DIV tok_decl(14,1)
195 #define TOK_REM tok_decl(14,2)
197 /* exponent is right associativity */
198 #define TOK_EXPONENT tok_decl(15,1)
200 /* For now unary operators. */
202 #define TOK_BNOT tok_decl(UNARYPREC,0)
203 #define TOK_NOT tok_decl(UNARYPREC,1)
205 #define TOK_UMINUS tok_decl(UNARYPREC+1,0)
206 #define TOK_UPLUS tok_decl(UNARYPREC+1,1)
208 #define PREC_PRE (UNARYPREC+2)
210 #define TOK_PRE_INC tok_decl(PREC_PRE, 0)
211 #define TOK_PRE_DEC tok_decl(PREC_PRE, 1)
213 #define PREC_POST (UNARYPREC+3)
215 #define TOK_POST_INC tok_decl(PREC_POST, 0)
216 #define TOK_POST_DEC tok_decl(PREC_POST, 1)
218 #define SPEC_PREC (UNARYPREC+4)
220 #define TOK_NUM tok_decl(SPEC_PREC, 0)
221 #define TOK_RPAREN tok_decl(SPEC_PREC, 1)
223 #define NUMPTR (*numstackptr)
226 tok_have_assign(operator op)
228 operator prec = PREC(op);
230 convert_prec_is_assing(prec);
231 return (prec == PREC(TOK_ASSIGN) ||
232 prec == PREC_PRE || prec == PREC_POST);
236 is_right_associativity(operator prec)
238 return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT)
239 || prec == PREC(TOK_CONDITIONAL));
244 arith_t contidional_second_val;
245 char contidional_second_val_initialized;
246 char *var; /* if NULL then is regular number,
247 else is variable name */
250 typedef struct chk_var_recursive_looped_t {
252 struct chk_var_recursive_looped_t *next;
253 } chk_var_recursive_looped_t;
255 static chk_var_recursive_looped_t *prev_chk_var_recursive;
258 arith_lookup_val(v_n_t *t, a_e_h_t *math_hooks)
261 const char *p = lookupvar(t->var);
266 /* recursive try as expression */
267 chk_var_recursive_looped_t *cur;
268 chk_var_recursive_looped_t cur_save;
270 for (cur = prev_chk_var_recursive; cur; cur = cur->next) {
271 if (strcmp(cur->var, t->var) == 0) {
272 /* expression recursion loop detected */
276 /* save current lookuped var name */
277 cur = prev_chk_var_recursive;
278 cur_save.var = t->var;
280 prev_chk_var_recursive = &cur_save;
282 t->val = arith (p, &errcode, math_hooks);
283 /* restore previous ptr after recursiving */
284 prev_chk_var_recursive = cur;
287 /* allow undefined var as 0 */
293 /* "applying" a token means performing it on the top elements on the integer
294 * stack. For a unary operator it will only change the top element, but a
295 * binary operator will pop two arguments and push a result */
297 arith_apply(operator op, v_n_t *numstack, v_n_t **numstackptr, a_e_h_t *math_hooks)
300 arith_t numptr_val, rez;
301 int ret_arith_lookup_val;
303 /* There is no operator that can work without arguments */
304 if (NUMPTR == numstack) goto err;
305 numptr_m1 = NUMPTR - 1;
307 /* check operand is var with noninteger value */
308 ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks);
309 if (ret_arith_lookup_val)
310 return ret_arith_lookup_val;
312 rez = numptr_m1->val;
313 if (op == TOK_UMINUS)
315 else if (op == TOK_NOT)
317 else if (op == TOK_BNOT)
319 else if (op == TOK_POST_INC || op == TOK_PRE_INC)
321 else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
323 else if (op != TOK_UPLUS) {
324 /* Binary operators */
326 /* check and binary operators need two arguments */
327 if (numptr_m1 == numstack) goto err;
329 /* ... and they pop one */
332 if (op == TOK_CONDITIONAL) {
333 if (!numptr_m1->contidional_second_val_initialized) {
334 /* protect $((expr1 ? expr2)) without ": expr" */
337 rez = numptr_m1->contidional_second_val;
338 } else if (numptr_m1->contidional_second_val_initialized) {
339 /* protect $((expr1 : expr2)) without "expr ? " */
342 numptr_m1 = NUMPTR - 1;
343 if (op != TOK_ASSIGN) {
344 /* check operand is var with noninteger value for not '=' */
345 ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks);
346 if (ret_arith_lookup_val)
347 return ret_arith_lookup_val;
349 if (op == TOK_CONDITIONAL) {
350 numptr_m1->contidional_second_val = rez;
352 rez = numptr_m1->val;
353 if (op == TOK_BOR || op == TOK_OR_ASSIGN)
355 else if (op == TOK_OR)
356 rez = numptr_val || rez;
357 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
359 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
361 else if (op == TOK_AND)
362 rez = rez && numptr_val;
363 else if (op == TOK_EQ)
364 rez = (rez == numptr_val);
365 else if (op == TOK_NE)
366 rez = (rez != numptr_val);
367 else if (op == TOK_GE)
368 rez = (rez >= numptr_val);
369 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
371 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
373 else if (op == TOK_GT)
374 rez = (rez > numptr_val);
375 else if (op == TOK_LT)
376 rez = (rez < numptr_val);
377 else if (op == TOK_LE)
378 rez = (rez <= numptr_val);
379 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
381 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
383 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
385 else if (op == TOK_ASSIGN || op == TOK_COMMA)
387 else if (op == TOK_CONDITIONAL_SEP) {
388 if (numptr_m1 == numstack) {
389 /* protect $((expr : expr)) without "expr ? " */
392 numptr_m1->contidional_second_val_initialized = op;
393 numptr_m1->contidional_second_val = numptr_val;
394 } else if (op == TOK_CONDITIONAL) {
396 numptr_val : numptr_m1->contidional_second_val;
397 } else if (op == TOK_EXPONENT) {
399 return -3; /* exponent less than 0 */
408 } else if (numptr_val==0) /* zero divisor check */
410 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
412 else if (op == TOK_REM || op == TOK_REM_ASSIGN)
415 if (tok_have_assign(op)) {
416 char buf[sizeof(arith_t)*3 + 2];
418 if (numptr_m1->var == NULL) {
422 /* save to shell variable */
423 sprintf(buf, arith_t_fmt, rez);
424 setvar(numptr_m1->var, buf, 0);
425 /* after saving, make previous value for v++ or v-- */
426 if (op == TOK_POST_INC)
428 else if (op == TOK_POST_DEC)
431 numptr_m1->val = rez;
432 /* protect geting var value, is number now */
433 numptr_m1->var = NULL;
439 /* longest must be first */
440 static const char op_tokens[] ALIGN1 = {
441 '<','<','=',0, TOK_LSHIFT_ASSIGN,
442 '>','>','=',0, TOK_RSHIFT_ASSIGN,
443 '<','<', 0, TOK_LSHIFT,
444 '>','>', 0, TOK_RSHIFT,
451 '|','=', 0, TOK_OR_ASSIGN,
452 '&','=', 0, TOK_AND_ASSIGN,
453 '*','=', 0, TOK_MUL_ASSIGN,
454 '/','=', 0, TOK_DIV_ASSIGN,
455 '%','=', 0, TOK_REM_ASSIGN,
456 '+','=', 0, TOK_PLUS_ASSIGN,
457 '-','=', 0, TOK_MINUS_ASSIGN,
458 '-','-', 0, TOK_POST_DEC,
459 '^','=', 0, TOK_XOR_ASSIGN,
460 '+','+', 0, TOK_POST_INC,
461 '*','*', 0, TOK_EXPONENT,
477 '?', 0, TOK_CONDITIONAL,
478 ':', 0, TOK_CONDITIONAL_SEP,
484 #define endexpression (&op_tokens[sizeof(op_tokens)-7])
487 arith(const char *expr, int *perrcode, a_e_h_t *math_hooks)
489 char arithval; /* Current character under analysis */
490 operator lasttok, op;
492 operator *stack, *stackptr;
493 const char *p = endexpression;
495 v_n_t *numstack, *numstackptr;
496 unsigned datasizes = strlen(expr) + 2;
498 /* Stack of integers */
499 /* The proof that there can be no more than strlen(startbuf)/2+1 integers
500 * in any given correct or incorrect expression is left as an exercise to
502 numstackptr = numstack = alloca((datasizes / 2) * sizeof(numstack[0]));
503 /* Stack of operator tokens */
504 stackptr = stack = alloca(datasizes * sizeof(stack[0]));
506 *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */
507 *perrcode = errcode = 0;
512 if (p == endexpression) {
513 /* Null expression. */
517 /* This is only reached after all tokens have been extracted from the
518 * input stream. If there are still tokens on the operator stack, they
519 * are to be applied in order. At the end, there should be a final
520 * result on the integer stack */
522 if (expr != endexpression + 1) {
523 /* If we haven't done so already, */
524 /* append a closing right paren */
525 expr = endexpression;
526 /* and let the loop process it. */
529 /* At this point, we're done with the expression. */
530 if (numstackptr != numstack+1) {
531 /* ... but if there isn't, it's bad */
537 /* expression is $((var)) only, lookup now */
538 errcode = arith_lookup_val(numstack, math_hooks);
542 return numstack->val;
545 /* Continue processing the expression. */
546 if (arith_isspace(arithval)) {
547 /* Skip whitespace */
552 size_t var_name_size = (p-expr) + 1; /* trailing zero */
554 numstackptr->var = alloca(var_name_size);
555 safe_strncpy(numstackptr->var, expr, var_name_size);
558 numstackptr->contidional_second_val_initialized = 0;
563 if (isdigit(arithval)) {
564 numstackptr->var = NULL;
566 /* call strtoul[l]: */
567 numstackptr->val = strto_arith_t(expr, (char **) &expr, 0);
569 numstackptr->val = 0; /* bash compat */
572 for (p = op_tokens; ; p++) {
576 /* strange operator not found */
579 for (o = expr; *p && *o == *p; p++)
586 /* skip tail uncompared token */
589 /* skip zero delim */
594 /* post grammar: a++ reduce to num */
595 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
598 /* Plus and minus are binary (not unary) _only_ if the last
599 * token was a number, or a right paren (which pretends to be
600 * a number, since it evaluates to one). Think about it.
602 if (lasttok != TOK_NUM) {
618 /* We don't want an unary operator to cause recursive descent on the
619 * stack, because there can be many in a row and it could cause an
620 * operator to be evaluated before its argument is pushed onto the
622 /* But for binary operators, "apply" everything on the operator
623 * stack until we find an operator with a lesser priority than the
624 * one we have just extracted. */
625 /* Left paren is given the lowest priority so it will never be
626 * "applied" in this way.
627 * if associativity is right and priority eq, applied also skip
630 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
631 /* not left paren or unary */
632 if (lasttok != TOK_NUM) {
633 /* binary op must be preceded by a num */
636 while (stackptr != stack) {
637 if (op == TOK_RPAREN) {
638 /* The algorithm employed here is simple: while we don't
639 * hit an open paren nor the bottom of the stack, pop
640 * tokens and apply them */
641 if (stackptr[-1] == TOK_LPAREN) {
643 /* Any operator directly after a */
645 /* close paren should consider itself binary */
649 operator prev_prec = PREC(stackptr[-1]);
651 convert_prec_is_assing(prec);
652 convert_prec_is_assing(prev_prec);
653 if (prev_prec < prec)
655 /* check right assoc */
656 if (prev_prec == prec && is_right_associativity(prec))
659 errcode = arith_apply(*--stackptr, numstack, &numstackptr, math_hooks);
660 if (errcode) goto ret;
662 if (op == TOK_RPAREN) {
667 /* Push this operator to the stack and remember it. */
668 *stackptr++ = lasttok = op;
675 * Copyright (c) 1989, 1991, 1993, 1994
676 * The Regents of the University of California. All rights reserved.
678 * This code is derived from software contributed to Berkeley by
681 * Redistribution and use in source and binary forms, with or without
682 * modification, are permitted provided that the following conditions
684 * 1. Redistributions of source code must retain the above copyright
685 * notice, this list of conditions and the following disclaimer.
686 * 2. Redistributions in binary form must reproduce the above copyright
687 * notice, this list of conditions and the following disclaimer in the
688 * documentation and/or other materials provided with the distribution.
689 * 3. Neither the name of the University nor the names of its contributors
690 * may be used to endorse or promote products derived from this software
691 * without specific prior written permission.
693 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
694 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
695 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
696 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
697 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
698 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
699 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
700 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
701 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
702 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF