1 /*
2 * Arithmetic code ripped out of ash shell for code sharing.
3 *
4 * This code is derived from software contributed to Berkeley by
5 * Kenneth Almquist.
6 *
7 * Original BSD copyright notice is retained at the end of this file.
8 *
9 * Copyright (c) 1989, 1991, 1993, 1994
10 * The Regents of the University of California. All rights reserved.
11 *
12 * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
13 * was re-ported from NetBSD and debianized.
14 *
15 * rewrite arith.y to micro stack based cryptic algorithm by
16 * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
17 *
18 * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support
19 * dynamic variables.
20 *
21 * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be
22 * used in busybox and size optimizations,
23 * rewrote arith (see notes to this), added locale support,
24 * rewrote dynamic variables.
25 *
26 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
27 */
28 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
29 *
30 * Permission is hereby granted, free of charge, to any person obtaining
31 * a copy of this software and associated documentation files (the
32 * "Software"), to deal in the Software without restriction, including
33 * without limitation the rights to use, copy, modify, merge, publish,
34 * distribute, sublicense, and/or sell copies of the Software, and to
35 * permit persons to whom the Software is furnished to do so, subject to
36 * the following conditions:
37 *
38 * The above copyright notice and this permission notice shall be
39 * included in all copies or substantial portions of the Software.
40 *
41 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
42 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
43 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
44 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
45 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
46 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
47 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
48 */
49
50 /* This is my infix parser/evaluator. It is optimized for size, intended
51 * as a replacement for yacc-based parsers. However, it may well be faster
52 * than a comparable parser written in yacc. The supported operators are
53 * listed in #defines below. Parens, order of operations, and error handling
54 * are supported. This code is thread safe. The exact expression format should
55 * be that which POSIX specifies for shells.
56 *
57 * The code uses a simple two-stack algorithm. See
58 * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
59 * for a detailed explanation of the infix-to-postfix algorithm on which
60 * this is based (this code differs in that it applies operators immediately
61 * to the stack instead of adding them to a queue to end up with an
62 * expression).
63 */
64
65 /*
66 * Aug 24, 2001 Manuel Novoa III
67 *
68 * Reduced the generated code size by about 30% (i386) and fixed several bugs.
69 *
70 * 1) In arith_apply():
71 * a) Cached values of *numptr and &(numptr[-1]).
72 * b) Removed redundant test for zero denominator.
73 *
74 * 2) In arith():
75 * a) Eliminated redundant code for processing operator tokens by moving
76 * to a table-based implementation. Also folded handling of parens
77 * into the table.
78 * b) Combined all 3 loops which called arith_apply to reduce generated
79 * code size at the cost of speed.
80 *
81 * 3) The following expressions were treated as valid by the original code:
82 * 1() , 0! , 1 ( *3 ) .
83 * These bugs have been fixed by internally enclosing the expression in
84 * parens and then checking that all binary ops and right parens are
85 * preceded by a valid expression (NUM_TOKEN).
86 *
87 * Note: It may be desirable to replace Aaron's test for whitespace with
88 * ctype's isspace() if it is used by another busybox applet or if additional
89 * whitespace chars should be considered. Look below the "#include"s for a
90 * precompiler test.
91 */
92 /*
93 * Aug 26, 2001 Manuel Novoa III
94 *
95 * Return 0 for null expressions. Pointed out by Vladimir Oleynik.
96 *
97 * Merge in Aaron's comments previously posted to the busybox list,
98 * modified slightly to take account of my changes to the code.
99 *
100 */
101 /*
102 * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru>
103 *
104 * - allow access to variable,
105 * use recursive value indirection: c="2*2"; a="c"; echo $((a+=2)) produce 6
106 * - implement assign syntax (VAR=expr, +=, *= etc)
107 * - implement exponentiation (** operator)
108 * - implement comma separated - expr, expr
109 * - implement ++expr --expr expr++ expr--
110 * - implement expr ? expr : expr (but second expr is always calculated)
111 * - allow hexadecimal and octal numbers
112 * - restore lost XOR operator
113 * - protect $((num num)) as true zero expr (Manuel's error)
114 * - always use special isspace(), see comment from bash ;-)
115 */
116 #include "libbb.h"
117 #include "math.h"
118
119 typedef unsigned char operator;
120
121 /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
122 * precedence, and 3 high bits are an ID unique across operators of that
123 * precedence. The ID portion is so that multiple operators can have the
124 * same precedence, ensuring that the leftmost one is evaluated first.
125 * Consider * and /
126 */
127 #define tok_decl(prec,id) (((id)<<5) | (prec))
128 #define PREC(op) ((op) & 0x1F)
129
130 #define TOK_LPAREN tok_decl(0,0)
131
132 #define TOK_COMMA tok_decl(1,0)
133
134 /* All assignments are right associative and have the same precedence,
135 * but there are 11 of them, which doesn't fit into 3 bits for unique id.
136 * Abusing another precedence level:
137 */
138 #define TOK_ASSIGN tok_decl(2,0)
139 #define TOK_AND_ASSIGN tok_decl(2,1)
140 #define TOK_OR_ASSIGN tok_decl(2,2)
141 #define TOK_XOR_ASSIGN tok_decl(2,3)
142 #define TOK_PLUS_ASSIGN tok_decl(2,4)
143 #define TOK_MINUS_ASSIGN tok_decl(2,5)
144 #define TOK_LSHIFT_ASSIGN tok_decl(2,6)
145 #define TOK_RSHIFT_ASSIGN tok_decl(2,7)
146
147 #define TOK_MUL_ASSIGN tok_decl(3,0)
148 #define TOK_DIV_ASSIGN tok_decl(3,1)
149 #define TOK_REM_ASSIGN tok_decl(3,2)
150
151 #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
152
153 /* Ternary conditional operator is right associative too */
154 #define TOK_CONDITIONAL tok_decl(4,0)
155 #define TOK_CONDITIONAL_SEP tok_decl(4,1)
156
157 #define TOK_OR tok_decl(5,0)
158
159 #define TOK_AND tok_decl(6,0)
160
161 #define TOK_BOR tok_decl(7,0)
162
163 #define TOK_BXOR tok_decl(8,0)
164
165 #define TOK_BAND tok_decl(9,0)
166
167 #define TOK_EQ tok_decl(10,0)
168 #define TOK_NE tok_decl(10,1)
169
170 #define TOK_LT tok_decl(11,0)
171 #define TOK_GT tok_decl(11,1)
172 #define TOK_GE tok_decl(11,2)
173 #define TOK_LE tok_decl(11,3)
174
175 #define TOK_LSHIFT tok_decl(12,0)
176 #define TOK_RSHIFT tok_decl(12,1)
177
178 #define TOK_ADD tok_decl(13,0)
179 #define TOK_SUB tok_decl(13,1)
180
181 #define TOK_MUL tok_decl(14,0)
182 #define TOK_DIV tok_decl(14,1)
183 #define TOK_REM tok_decl(14,2)
184
185 /* Exponent is right associative */
186 #define TOK_EXPONENT tok_decl(15,1)
187
188 /* Unary operators */
189 #define UNARYPREC 16
190 #define TOK_BNOT tok_decl(UNARYPREC,0)
191 #define TOK_NOT tok_decl(UNARYPREC,1)
192
193 #define TOK_UMINUS tok_decl(UNARYPREC+1,0)
194 #define TOK_UPLUS tok_decl(UNARYPREC+1,1)
195
196 #define PREC_PRE (UNARYPREC+2)
197
198 #define TOK_PRE_INC tok_decl(PREC_PRE, 0)
199 #define TOK_PRE_DEC tok_decl(PREC_PRE, 1)
200
201 #define PREC_POST (UNARYPREC+3)
202
203 #define TOK_POST_INC tok_decl(PREC_POST, 0)
204 #define TOK_POST_DEC tok_decl(PREC_POST, 1)
205
206 #define SPEC_PREC (UNARYPREC+4)
207
208 #define TOK_NUM tok_decl(SPEC_PREC, 0)
209 #define TOK_RPAREN tok_decl(SPEC_PREC, 1)
210
211 static int
is_assign_op(operator op)212 is_assign_op(operator op)
213 {
214 operator prec = PREC(op);
215 fix_assignment_prec(prec);
216 return prec == PREC(TOK_ASSIGN)
217 || prec == PREC_PRE
218 || prec == PREC_POST;
219 }
220
221 static int
is_right_associative(operator prec)222 is_right_associative(operator prec)
223 {
224 return prec == PREC(TOK_ASSIGN)
225 || prec == PREC(TOK_EXPONENT)
226 || prec == PREC(TOK_CONDITIONAL);
227 }
228
229
230 typedef struct {
231 arith_t val;
232 /* We acquire second_val only when "expr1 : expr2" part
233 * of ternary ?: op is evaluated.
234 * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
235 * ':' produces a new value which has two parts, val and second_val;
236 * then '?' selects one of them based on its left side.
237 */
238 arith_t second_val;
239 char second_val_present;
240 /* If NULL then it's just a number, else it's a named variable */
241 char *var;
242 } var_or_num_t;
243
244 typedef struct remembered_name {
245 struct remembered_name *next;
246 const char *var;
247 } remembered_name;
248
249
250 static arith_t
251 evaluate_string(arith_state_t *math_state, const char *expr);
252
253 static const char*
arith_lookup_val(arith_state_t * math_state,var_or_num_t * t)254 arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
255 {
256 if (t->var) {
257 const char *p = math_state->lookupvar(t->var);
258 if (p) {
259 remembered_name *cur;
260 remembered_name cur_save;
261
262 /* did we already see this name?
263 * testcase: a=b; b=a; echo $((a))
264 */
265 for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
266 if (strcmp(cur->var, t->var) == 0) {
267 /* Yes */
268 return "expression recursion loop detected";
269 }
270 }
271
272 /* push current var name */
273 cur = math_state->list_of_recursed_names;
274 cur_save.var = t->var;
275 cur_save.next = cur;
276 math_state->list_of_recursed_names = &cur_save;
277
278 /* recursively evaluate p as expression */
279 t->val = evaluate_string(math_state, p);
280
281 /* pop current var name */
282 math_state->list_of_recursed_names = cur;
283
284 return math_state->errmsg;
285 }
286 /* treat undefined var as 0 */
287 t->val = 0;
288 }
289 return 0;
290 }
291
292 /* "Applying" a token means performing it on the top elements on the integer
293 * stack. For an unary operator it will only change the top element, but a
294 * binary operator will pop two arguments and push the result */
295 static NOINLINE const char*
arith_apply(arith_state_t * math_state,operator op,var_or_num_t * numstack,var_or_num_t ** numstackptr)296 arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
297 {
298 #define NUMPTR (*numstackptr)
299
300 var_or_num_t *top_of_stack;
301 arith_t rez;
302 const char *err;
303
304 /* There is no operator that can work without arguments */
305 if (NUMPTR == numstack)
306 goto err;
307
308 top_of_stack = NUMPTR - 1;
309
310 /* Resolve name to value, if needed */
311 err = arith_lookup_val(math_state, top_of_stack);
312 if (err)
313 return err;
314
315 rez = top_of_stack->val;
316 if (op == TOK_UMINUS)
317 rez = -rez;
318 else if (op == TOK_NOT)
319 rez = !rez;
320 else if (op == TOK_BNOT)
321 rez = ~rez;
322 else if (op == TOK_POST_INC || op == TOK_PRE_INC)
323 rez++;
324 else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
325 rez--;
326 else if (op != TOK_UPLUS) {
327 /* Binary operators */
328 arith_t right_side_val;
329 char bad_second_val;
330
331 /* Binary operators need two arguments */
332 if (top_of_stack == numstack)
333 goto err;
334 /* ...and they pop one */
335 NUMPTR = top_of_stack; /* this decrements NUMPTR */
336
337 bad_second_val = top_of_stack->second_val_present;
338 if (op == TOK_CONDITIONAL) { /* ? operation */
339 /* Make next if (...) protect against
340 * $((expr1 ? expr2)) - that is, missing ": expr" */
341 bad_second_val = !bad_second_val;
342 }
343 if (bad_second_val) {
344 /* Protect against $((expr <not_?_op> expr1 : expr2)) */
345 return "malformed ?: operator";
346 }
347
348 top_of_stack--; /* now points to left side */
349
350 if (op != TOK_ASSIGN) {
351 /* Resolve left side value (unless the op is '=') */
352 err = arith_lookup_val(math_state, top_of_stack);
353 if (err)
354 return err;
355 }
356
357 right_side_val = rez;
358 rez = top_of_stack->val;
359 if (op == TOK_CONDITIONAL) /* ? operation */
360 rez = (rez ? right_side_val : top_of_stack[1].second_val);
361 else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
362 if (top_of_stack == numstack) {
363 /* Protect against $((expr : expr)) */
364 return "malformed ?: operator";
365 }
366 top_of_stack->second_val_present = op;
367 top_of_stack->second_val = right_side_val;
368 }
369 else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
370 rez |= right_side_val;
371 else if (op == TOK_OR)
372 rez = right_side_val || rez;
373 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
374 rez &= right_side_val;
375 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
376 rez ^= right_side_val;
377 else if (op == TOK_AND)
378 rez = rez && right_side_val;
379 else if (op == TOK_EQ)
380 rez = (rez == right_side_val);
381 else if (op == TOK_NE)
382 rez = (rez != right_side_val);
383 else if (op == TOK_GE)
384 rez = (rez >= right_side_val);
385 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
386 rez >>= right_side_val;
387 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
388 rez <<= right_side_val;
389 else if (op == TOK_GT)
390 rez = (rez > right_side_val);
391 else if (op == TOK_LT)
392 rez = (rez < right_side_val);
393 else if (op == TOK_LE)
394 rez = (rez <= right_side_val);
395 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
396 rez *= right_side_val;
397 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
398 rez += right_side_val;
399 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
400 rez -= right_side_val;
401 else if (op == TOK_ASSIGN || op == TOK_COMMA)
402 rez = right_side_val;
403 else if (op == TOK_EXPONENT) {
404 arith_t c;
405 if (right_side_val < 0)
406 return "exponent less than 0";
407 c = 1;
408 while (--right_side_val >= 0)
409 c *= rez;
410 rez = c;
411 }
412 else if (right_side_val == 0)
413 return "divide by zero";
414 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
415 || op == TOK_REM || op == TOK_REM_ASSIGN) {
416 /*
417 * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))'
418 *
419 * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1
420 * and thus is not representable.
421 * Some CPUs segfault trying such op.
422 * Others overflow MAX_POSITIVE_INT+1 to
423 * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000).
424 * Make sure to at least not SEGV here:
425 */
426 if (right_side_val == -1
427 && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */
428 ) {
429 right_side_val = 1;
430 }
431 if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
432 rez /= right_side_val;
433 else {
434 rez %= right_side_val;
435 }
436 }
437 }
438
439 if (is_assign_op(op)) {
440 char buf[sizeof(arith_t)*3 + 2];
441
442 if (top_of_stack->var == NULL) {
443 /* Hmm, 1=2 ? */
444 goto err;
445 }
446 /* Save to shell variable */
447 sprintf(buf, ARITH_FMT, rez);
448 math_state->setvar(top_of_stack->var, buf);
449 /* After saving, make previous value for v++ or v-- */
450 if (op == TOK_POST_INC)
451 rez--;
452 if (op == TOK_POST_DEC)
453 rez++;
454 }
455
456 top_of_stack->val = rez;
457 /* Erase var name, it is just a number now */
458 top_of_stack->var = NULL;
459 return NULL;
460 err:
461 return "arithmetic syntax error";
462 #undef NUMPTR
463 }
464
465 /* longest must be first */
466 static const char op_tokens[] ALIGN1 = {
467 '<','<','=',0, TOK_LSHIFT_ASSIGN,
468 '>','>','=',0, TOK_RSHIFT_ASSIGN,
469 '<','<', 0, TOK_LSHIFT,
470 '>','>', 0, TOK_RSHIFT,
471 '|','|', 0, TOK_OR,
472 '&','&', 0, TOK_AND,
473 '!','=', 0, TOK_NE,
474 '<','=', 0, TOK_LE,
475 '>','=', 0, TOK_GE,
476 '=','=', 0, TOK_EQ,
477 '|','=', 0, TOK_OR_ASSIGN,
478 '&','=', 0, TOK_AND_ASSIGN,
479 '*','=', 0, TOK_MUL_ASSIGN,
480 '/','=', 0, TOK_DIV_ASSIGN,
481 '%','=', 0, TOK_REM_ASSIGN,
482 '+','=', 0, TOK_PLUS_ASSIGN,
483 '-','=', 0, TOK_MINUS_ASSIGN,
484 '-','-', 0, TOK_POST_DEC,
485 '^','=', 0, TOK_XOR_ASSIGN,
486 '+','+', 0, TOK_POST_INC,
487 '*','*', 0, TOK_EXPONENT,
488 '!', 0, TOK_NOT,
489 '<', 0, TOK_LT,
490 '>', 0, TOK_GT,
491 '=', 0, TOK_ASSIGN,
492 '|', 0, TOK_BOR,
493 '&', 0, TOK_BAND,
494 '*', 0, TOK_MUL,
495 '/', 0, TOK_DIV,
496 '%', 0, TOK_REM,
497 '+', 0, TOK_ADD,
498 '-', 0, TOK_SUB,
499 '^', 0, TOK_BXOR,
500 /* uniq */
501 '~', 0, TOK_BNOT,
502 ',', 0, TOK_COMMA,
503 '?', 0, TOK_CONDITIONAL,
504 ':', 0, TOK_CONDITIONAL_SEP,
505 ')', 0, TOK_RPAREN,
506 '(', 0, TOK_LPAREN,
507 0
508 };
509 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
510
511 #if ENABLE_FEATURE_SH_MATH_BASE
strto_arith_t(const char * nptr,char ** endptr)512 static arith_t strto_arith_t(const char *nptr, char **endptr)
513 {
514 unsigned base;
515 arith_t n;
516
517 # if ENABLE_FEATURE_SH_MATH_64
518 n = strtoull(nptr, endptr, 0);
519 # else
520 n = strtoul(nptr, endptr, 0);
521 # endif
522 if (**endptr != '#'
523 || (*nptr < '1' || *nptr > '9')
524 || (n < 2 || n > 64)
525 ) {
526 return n;
527 }
528
529 /* It's "N#nnnn" or "NN#nnnn" syntax, NN can't start with 0,
530 * NN is in 2..64 range.
531 */
532 base = (unsigned)n;
533 n = 0;
534 nptr = *endptr + 1;
535 for (;;) {
536 unsigned digit = (unsigned)*nptr - '0';
537 if (digit >= 10 /* not 0..9 */
538 && digit <= 'z' - '0' /* needed to reject e.g. $((64#~)) */
539 ) {
540 /* in bases up to 36, case does not matter for a-z */
541 digit = (unsigned)(*nptr | 0x20) - ('a' - 10);
542 if (base > 36 && *nptr <= '_') {
543 /* otherwise, A-Z,@,_ are 36-61,62,63 */
544 if (*nptr == '_')
545 digit = 63;
546 else if (*nptr == '@')
547 digit = 62;
548 else if (digit < 36) /* A-Z */
549 digit += 36 - 10;
550 else
551 break; /* error: one of [\]^ */
552 }
553 //bb_error_msg("ch:'%c'%d digit:%u", *nptr, *nptr, digit);
554 //if (digit < 10) - example where we need this?
555 // break;
556 }
557 if (digit >= base)
558 break;
559 /* bash does not check for overflows */
560 n = n * base + digit;
561 nptr++;
562 }
563 /* Note: we do not set errno on bad chars, we just set a pointer
564 * to the first invalid char. For example, this allows
565 * "N#" (empty "nnnn" part): 64#+1 is a valid expression,
566 * it means 64# + 1, whereas 64#~... is not, since ~ is not a valid
567 * operator.
568 */
569 *endptr = (char*)nptr;
570 return n;
571 }
572 #else /* !ENABLE_FEATURE_SH_MATH_BASE */
573 # if ENABLE_FEATURE_SH_MATH_64
574 # define strto_arith_t(nptr, endptr) strtoull(nptr, endptr, 0)
575 # else
576 # define strto_arith_t(nptr, endptr) strtoul(nptr, endptr, 0)
577 # endif
578 #endif
579
580 static arith_t
evaluate_string(arith_state_t * math_state,const char * expr)581 evaluate_string(arith_state_t *math_state, const char *expr)
582 {
583 operator lasttok;
584 const char *errmsg;
585 const char *start_expr = expr = skip_whitespace(expr);
586 unsigned expr_len = strlen(expr) + 2;
587 /* Stack of integers */
588 /* The proof that there can be no more than strlen(startbuf)/2+1
589 * integers in any given correct or incorrect expression
590 * is left as an exercise to the reader. */
591 var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
592 var_or_num_t *numstackptr = numstack;
593 /* Stack of operator tokens */
594 operator *const stack = alloca(expr_len * sizeof(stack[0]));
595 operator *stackptr = stack;
596
597 /* Start with a left paren */
598 *stackptr++ = lasttok = TOK_LPAREN;
599 errmsg = NULL;
600
601 while (1) {
602 const char *p;
603 operator op;
604 operator prec;
605
606 expr = skip_whitespace(expr);
607 if (*expr == '\0') {
608 if (expr == start_expr) {
609 /* Null expression */
610 numstack->val = 0;
611 goto ret;
612 }
613
614 /* This is only reached after all tokens have been extracted from the
615 * input stream. If there are still tokens on the operator stack, they
616 * are to be applied in order. At the end, there should be a final
617 * result on the integer stack */
618
619 if (expr != ptr_to_rparen + 1) {
620 /* If we haven't done so already,
621 * append a closing right paren
622 * and let the loop process it */
623 expr = ptr_to_rparen;
624 //bb_error_msg("expr=')'");
625 continue;
626 }
627 /* At this point, we're done with the expression */
628 if (numstackptr != numstack + 1) {
629 /* ...but if there isn't, it's bad */
630 goto err;
631 }
632 goto ret;
633 }
634
635 p = endofname(expr);
636 if (p != expr) {
637 /* Name */
638 size_t var_name_size = (p - expr) + 1; /* +1 for NUL */
639 numstackptr->var = alloca(var_name_size);
640 safe_strncpy(numstackptr->var, expr, var_name_size);
641 //bb_error_msg("var:'%s'", numstackptr->var);
642 expr = p;
643 num:
644 numstackptr->second_val_present = 0;
645 numstackptr++;
646 lasttok = TOK_NUM;
647 continue;
648 }
649
650 if (isdigit(*expr)) {
651 /* Number */
652 numstackptr->var = NULL;
653 errno = 0;
654 numstackptr->val = strto_arith_t(expr, (char**) &expr);
655 //bb_error_msg("val:%lld", numstackptr->val);
656 if (errno)
657 numstackptr->val = 0; /* bash compat */
658 goto num;
659 }
660
661 /* Should be an operator */
662
663 /* Special case: XYZ--, XYZ++, --XYZ, ++XYZ are recognized
664 * only if XYZ is a variable name, not a number or EXPR. IOW:
665 * "a+++v" is a++ + v.
666 * "(a)+++7" is ( a ) + + + 7.
667 * "7+++v" is 7 + ++v, not 7++ + v.
668 * "--7" is - - 7, not --7.
669 * "++++a" is + + ++a, not ++ ++a.
670 */
671 if ((expr[0] == '+' || expr[0] == '-')
672 && (expr[1] == expr[0])
673 ) {
674 if (numstackptr == numstack || !numstackptr[-1].var) { /* not a VAR++ */
675 char next = skip_whitespace(expr + 2)[0];
676 if (!(isalpha(next) || next == '_')) { /* not a ++VAR */
677 //bb_error_msg("special %c%c", expr[0], expr[0]);
678 op = (expr[0] == '+' ? TOK_ADD : TOK_SUB);
679 expr++;
680 goto tok_found1;
681 }
682 }
683 }
684
685 p = op_tokens;
686 while (1) {
687 /* Compare expr to current op_tokens[] element */
688 const char *e = expr;
689 while (1) {
690 if (*p == '\0') {
691 /* Match: operator is found */
692 expr = e;
693 goto tok_found;
694 }
695 if (*p != *e)
696 break;
697 p++;
698 e++;
699 }
700 /* No match, go to next element of op_tokens[] */
701 while (*p)
702 p++;
703 p += 2; /* skip NUL and TOK_foo bytes */
704 if (*p == '\0') {
705 /* No next element, operator not found */
706 //math_state->syntax_error_at = expr;
707 goto err;
708 }
709 }
710 tok_found:
711 op = p[1]; /* fetch TOK_foo value */
712 tok_found1:
713 /* NB: expr now points past the operator */
714
715 /* post grammar: a++ reduce to num */
716 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
717 lasttok = TOK_NUM;
718
719 /* Plus and minus are binary (not unary) _only_ if the last
720 * token was a number, or a right paren (which pretends to be
721 * a number, since it evaluates to one). Think about it.
722 * It makes sense. */
723 if (lasttok != TOK_NUM) {
724 switch (op) {
725 case TOK_ADD:
726 op = TOK_UPLUS;
727 break;
728 case TOK_SUB:
729 op = TOK_UMINUS;
730 break;
731 case TOK_POST_INC:
732 op = TOK_PRE_INC;
733 break;
734 case TOK_POST_DEC:
735 op = TOK_PRE_DEC;
736 break;
737 }
738 }
739 /* We don't want an unary operator to cause recursive descent on the
740 * stack, because there can be many in a row and it could cause an
741 * operator to be evaluated before its argument is pushed onto the
742 * integer stack.
743 * But for binary operators, "apply" everything on the operator
744 * stack until we find an operator with a lesser priority than the
745 * one we have just extracted. If op is right-associative,
746 * then stop "applying" on the equal priority too.
747 * Left paren is given the lowest priority so it will never be
748 * "applied" in this way.
749 */
750 prec = PREC(op);
751 //bb_error_msg("prec:%02x", prec);
752 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
753 /* not left paren or unary */
754 if (lasttok != TOK_NUM) {
755 /* binary op must be preceded by a num */
756 goto err;
757 }
758 /* The algorithm employed here is simple: while we don't
759 * hit an open paren nor the bottom of the stack, pop
760 * tokens and apply them */
761 while (stackptr != stack) {
762 operator prev_op = *--stackptr;
763 if (op == TOK_RPAREN) {
764 //bb_error_msg("op == TOK_RPAREN");
765 if (prev_op == TOK_LPAREN) {
766 //bb_error_msg("prev_op == TOK_LPAREN");
767 //bb_error_msg(" %p %p numstackptr[-1].var:'%s'", numstack, numstackptr-1, numstackptr[-1].var);
768 if (numstackptr[-1].var) {
769 /* Expression is (var), lookup now */
770 errmsg = arith_lookup_val(math_state, &numstackptr[-1]);
771 if (errmsg)
772 goto err_with_custom_msg;
773 /* Erase var name: (var) is just a number, for example, (var) = 1 is not valid */
774 numstackptr[-1].var = NULL;
775 }
776 /* Any operator directly after a
777 * close paren should consider itself binary */
778 lasttok = TOK_NUM;
779 goto next;
780 }
781 //bb_error_msg("prev_op != TOK_LPAREN");
782 } else {
783 operator prev_prec = PREC(prev_op);
784 //bb_error_msg("op != TOK_RPAREN");
785 fix_assignment_prec(prec);
786 fix_assignment_prec(prev_prec);
787 if (prev_prec < prec
788 || (prev_prec == prec && is_right_associative(prec))
789 ) {
790 stackptr++;
791 break;
792 }
793 }
794 //bb_error_msg("arith_apply(prev_op:%02x)", prev_op);
795 errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
796 if (errmsg)
797 goto err_with_custom_msg;
798 }
799 if (op == TOK_RPAREN)
800 goto err;
801 }
802
803 /* Push this operator to the stack and remember it */
804 //bb_error_msg("push op:%02x", op);
805 *stackptr++ = lasttok = op;
806 next: ;
807 } /* while (1) */
808
809 err:
810 errmsg = "arithmetic syntax error";
811 err_with_custom_msg:
812 numstack->val = -1;
813 ret:
814 math_state->errmsg = errmsg;
815 return numstack->val;
816 }
817
818 arith_t FAST_FUNC
arith(arith_state_t * math_state,const char * expr)819 arith(arith_state_t *math_state, const char *expr)
820 {
821 math_state->errmsg = NULL;
822 math_state->list_of_recursed_names = NULL;
823 return evaluate_string(math_state, expr);
824 }
825
826 /*
827 * Copyright (c) 1989, 1991, 1993, 1994
828 * The Regents of the University of California. All rights reserved.
829 *
830 * This code is derived from software contributed to Berkeley by
831 * Kenneth Almquist.
832 *
833 * Redistribution and use in source and binary forms, with or without
834 * modification, are permitted provided that the following conditions
835 * are met:
836 * 1. Redistributions of source code must retain the above copyright
837 * notice, this list of conditions and the following disclaimer.
838 * 2. Redistributions in binary form must reproduce the above copyright
839 * notice, this list of conditions and the following disclaimer in the
840 * documentation and/or other materials provided with the distribution.
841 * 3. Neither the name of the University nor the names of its contributors
842 * may be used to endorse or promote products derived from this software
843 * without specific prior written permission.
844 *
845 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND
846 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
847 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
848 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
849 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
850 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
851 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
852 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
853 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
854 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
855 * SUCH DAMAGE.
856 */
857