X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;ds=sidebyside;f=shell%2Fmath.c;h=e7565ebf2980a6f9f249977e6a34541582ceab89;hb=8a475def9e3e21f780ebcf07dd607b26ceb00ea8;hp=555559a26ced9a20b34ed481ca495e302198eb9f;hpb=06d44d7dfb709bfe02e74d187cceb8591bbda3b4;p=oweals%2Fbusybox.git

diff --git a/shell/math.c b/shell/math.c
index 555559a26..e7565ebf2 100644
--- a/shell/math.c
+++ b/shell/math.c
@@ -1,5 +1,5 @@
 /*
- * arithmetic code ripped out of ash shell for code sharing
+ * Arithmetic code ripped out of ash shell for code sharing.
  *
  * This code is derived from software contributed to Berkeley by
  * Kenneth Almquist.
@@ -26,26 +26,26 @@
  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  */
 /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
-
-   Permission is hereby granted, free of charge, to any person obtaining
-   a copy of this software and associated documentation files (the
-   "Software"), to deal in the Software without restriction, including
-   without limitation the rights to use, copy, modify, merge, publish,
-   distribute, sublicense, and/or sell copies of the Software, and to
-   permit persons to whom the Software is furnished to do so, subject to
-   the following conditions:
-
-   The above copyright notice and this permission notice shall be
-   included in all copies or substantial portions of the Software.
-
-   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
-   MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
-   IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
-   CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
-   TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
-   SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-*/
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+ */
 
 /* This is my infix parser/evaluator. It is optimized for size, intended
  * as a replacement for yacc-based parsers. However, it may well be faster
@@ -60,9 +60,6 @@
  * this is based (this code differs in that it applies operators immediately
  * to the stack instead of adding them to a queue to end up with an
  * expression).
- *
- * To use the routine, call it with an expression string and error return
- * pointer
  */
 
 /*
@@ -157,7 +154,7 @@ typedef unsigned char operator;
 
 #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
 
-/* ternary conditional operator is right associative too */
+/* Ternary conditional operator is right associative too */
 #define TOK_CONDITIONAL         tok_decl(4,0)
 #define TOK_CONDITIONAL_SEP     tok_decl(4,1)
 
@@ -189,10 +186,10 @@ typedef unsigned char operator;
 #define TOK_DIV                 tok_decl(14,1)
 #define TOK_REM                 tok_decl(14,2)
 
-/* exponent is right associative */
+/* Exponent is right associative */
 #define TOK_EXPONENT            tok_decl(15,1)
 
-/* unary operators */
+/* Unary operators */
 #define UNARYPREC               16
 #define TOK_BNOT                tok_decl(UNARYPREC,0)
 #define TOK_NOT                 tok_decl(UNARYPREC,1)
@@ -216,67 +213,81 @@ typedef unsigned char operator;
 #define TOK_RPAREN              tok_decl(SPEC_PREC, 1)
 
 static int
-tok_have_assign(operator op)
+is_assign_op(operator op)
 {
 	operator prec = PREC(op);
-
 	fix_assignment_prec(prec);
-	return (prec == PREC(TOK_ASSIGN) ||
-			prec == PREC_PRE || prec == PREC_POST);
+	return prec == PREC(TOK_ASSIGN)
+	|| prec == PREC_PRE
+	|| prec == PREC_POST;
 }
 
 static int
 is_right_associative(operator prec)
 {
-	return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT)
-	        || prec == PREC(TOK_CONDITIONAL));
+	return prec == PREC(TOK_ASSIGN)
+	|| prec == PREC(TOK_EXPONENT)
+	|| prec == PREC(TOK_CONDITIONAL);
 }
 
+
 typedef struct {
 	arith_t val;
-	arith_t contidional_second_val;
-	char contidional_second_val_initialized;
-	char *var;      /* if NULL then is regular number,
-			   else is variable name */
-} v_n_t;
-
-typedef struct chk_var_recursive_looped_t {
+	/* We acquire second_val only when "expr1 : expr2" part
+	 * of ternary ?: op is evaluated.
+	 * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
+	 * ':' produces a new value which has two parts, val and second_val;
+	 * then '?' selects one of them based on its left side.
+	 */
+	arith_t second_val;
+	char second_val_present;
+	/* If NULL then it's just a number, else it's a named variable */
+	char *var;
+} var_or_num_t;
+
+typedef struct remembered_name {
+	struct remembered_name *next;
 	const char *var;
-	struct chk_var_recursive_looped_t *next;
-} chk_var_recursive_looped_t;
+} remembered_name;
 
-static chk_var_recursive_looped_t *prev_chk_var_recursive;
 
-static int
-arith_lookup_val(arith_state_t *math_state, v_n_t *t)
+static arith_t FAST_FUNC
+evaluate_string(arith_state_t *math_state, const char *expr);
+
+static const char*
+arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
 {
 	if (t->var) {
 		const char *p = lookupvar(t->var);
-
 		if (p) {
-			chk_var_recursive_looped_t *cur;
-			chk_var_recursive_looped_t cur_save;
-
-			/* recursively try p as expression */
+			remembered_name *cur;
+			remembered_name cur_save;
 
-			for (cur = prev_chk_var_recursive; cur; cur = cur->next) {
+			/* did we already see this name?
+			 * testcase: a=b; b=a; echo $((a))
+			 */
+			for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
 				if (strcmp(cur->var, t->var) == 0) {
-					/* expression recursion loop detected */
-					return -5;
+					/* Yes */
+					return "expression recursion loop detected";
 				}
 			}
-			/* save current var name */
-			cur = prev_chk_var_recursive;
+
+			/* push current var name */
+			cur = math_state->list_of_recursed_names;
 			cur_save.var = t->var;
 			cur_save.next = cur;
-			prev_chk_var_recursive = &cur_save;
+			math_state->list_of_recursed_names = &cur_save;
+
+			/* recursively evaluate p as expression */
+			t->val = evaluate_string(math_state, p);
+
+			/* pop current var name */
+			math_state->list_of_recursed_names = cur;
 
-			t->val = arith(math_state, p);
-			/* restore previous ptr after recursion */
-			prev_chk_var_recursive = cur;
-			return math_state->errcode;
+			return math_state->errmsg;
 		}
-		/* allow undefined var as 0 */
+		/* treat undefined var as 0 */
 		t->val = 0;
 	}
 	return 0;
@@ -285,28 +296,29 @@ arith_lookup_val(arith_state_t *math_state, v_n_t *t)
 /* "Applying" a token means performing it on the top elements on the integer
  * stack. For an unary operator it will only change the top element, but a
  * binary operator will pop two arguments and push the result */
-static NOINLINE int
-arith_apply(arith_state_t *math_state, operator op, v_n_t *numstack, v_n_t **numstackptr)
+static NOINLINE const char*
+arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
 {
 #define NUMPTR (*numstackptr)
 
-	v_n_t *numptr_m1;
-	arith_t numptr_val, rez;
-	int err;
+	var_or_num_t *top_of_stack;
+	arith_t rez;
+	const char *err;
 
 	/* There is no operator that can work without arguments */
 	if (NUMPTR == numstack)
 		goto err;
-	numptr_m1 = NUMPTR - 1;
 
-	/* Check operand is var with noninteger value */
-	err = arith_lookup_val(math_state, numptr_m1);
+	top_of_stack = NUMPTR - 1;
+
+	/* Resolve name to value, if needed */
+	err = arith_lookup_val(math_state, top_of_stack);
 	if (err)
 		return err;
 
-	rez = numptr_m1->val;
+	rez = top_of_stack->val;
 	if (op == TOK_UMINUS)
-		rez *= -1;
+		rez = -rez;
 	else if (op == TOK_NOT)
 		rez = !rez;
 	else if (op == TOK_BNOT)
@@ -317,115 +329,141 @@ arith_apply(arith_state_t *math_state, operator op, v_n_t *numstack, v_n_t **num
 		rez--;
 	else if (op != TOK_UPLUS) {
 		/* Binary operators */
+		arith_t right_side_val;
+		char bad_second_val;
 
-		/* check and binary operators need two arguments */
-		if (numptr_m1 == numstack) goto err;
-
-		/* ... and they pop one */
-		--NUMPTR;
-		numptr_val = rez;
-		if (op == TOK_CONDITIONAL) {
-			if (!numptr_m1->contidional_second_val_initialized) {
-				/* protect $((expr1 ? expr2)) without ": expr" */
-				goto err;
-			}
-			rez = numptr_m1->contidional_second_val;
-		} else if (numptr_m1->contidional_second_val_initialized) {
-			/* protect $((expr1 : expr2)) without "expr ? " */
+		/* Binary operators need two arguments */
+		if (top_of_stack == numstack)
 			goto err;
+		/* ...and they pop one */
+		NUMPTR = top_of_stack; /* this decrements NUMPTR */
+
+		bad_second_val = top_of_stack->second_val_present;
+		if (op == TOK_CONDITIONAL) { /* ? operation */
+			/* Make next if (...) protect against
+			 * $((expr1 ? expr2)) - that is, missing ": expr" */
+			bad_second_val = !bad_second_val;
+		}
+		if (bad_second_val) {
+			/* Protect against $((expr <not_?_op> expr1 : expr2)) */
+			return "malformed ?: operator";
 		}
-		numptr_m1 = NUMPTR - 1;
+
+		top_of_stack--; /* now points to left side */
+
 		if (op != TOK_ASSIGN) {
-			/* check operand is var with noninteger value for not '=' */
-			err = arith_lookup_val(math_state, numptr_m1);
+			/* Resolve left side value (unless the op is '=') */
+			err = arith_lookup_val(math_state, top_of_stack);
 			if (err)
 				return err;
 		}
-		if (op == TOK_CONDITIONAL) {
-			numptr_m1->contidional_second_val = rez;
+
+		right_side_val = rez;
+		rez = top_of_stack->val;
+		if (op == TOK_CONDITIONAL) /* ? operation */
+			rez = (rez ? right_side_val : top_of_stack[1].second_val);
+		else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
+			if (top_of_stack == numstack) {
+				/* Protect against $((expr : expr)) */
+				return "malformed ?: operator";
+			}
+			top_of_stack->second_val_present = op;
+			top_of_stack->second_val = right_side_val;
 		}
-		rez = numptr_m1->val;
-		if (op == TOK_BOR || op == TOK_OR_ASSIGN)
-			rez |= numptr_val;
+		else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
+			rez |= right_side_val;
 		else if (op == TOK_OR)
-			rez = numptr_val || rez;
+			rez = right_side_val || rez;
 		else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
-			rez &= numptr_val;
+			rez &= right_side_val;
 		else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
-			rez ^= numptr_val;
+			rez ^= right_side_val;
 		else if (op == TOK_AND)
-			rez = rez && numptr_val;
+			rez = rez && right_side_val;
 		else if (op == TOK_EQ)
-			rez = (rez == numptr_val);
+			rez = (rez == right_side_val);
 		else if (op == TOK_NE)
-			rez = (rez != numptr_val);
+			rez = (rez != right_side_val);
 		else if (op == TOK_GE)
-			rez = (rez >= numptr_val);
+			rez = (rez >= right_side_val);
 		else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
-			rez >>= numptr_val;
+			rez >>= right_side_val;
 		else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
-			rez <<= numptr_val;
+			rez <<= right_side_val;
 		else if (op == TOK_GT)
-			rez = (rez > numptr_val);
+			rez = (rez > right_side_val);
 		else if (op == TOK_LT)
-			rez = (rez < numptr_val);
+			rez = (rez < right_side_val);
 		else if (op == TOK_LE)
-			rez = (rez <= numptr_val);
+			rez = (rez <= right_side_val);
 		else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
-			rez *= numptr_val;
+			rez *= right_side_val;
 		else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
-			rez += numptr_val;
+			rez += right_side_val;
 		else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
-			rez -= numptr_val;
+			rez -= right_side_val;
 		else if (op == TOK_ASSIGN || op == TOK_COMMA)
-			rez = numptr_val;
-		else if (op == TOK_CONDITIONAL_SEP) {
-			if (numptr_m1 == numstack) {
-				/* protect $((expr : expr)) without "expr ? " */
-				goto err;
-			}
-			numptr_m1->contidional_second_val_initialized = op;
-			numptr_m1->contidional_second_val = numptr_val;
-		} else if (op == TOK_CONDITIONAL) {
-			rez = rez ?
-				numptr_val : numptr_m1->contidional_second_val;
-		} else if (op == TOK_EXPONENT) {
+			rez = right_side_val;
+		else if (op == TOK_EXPONENT) {
 			arith_t c;
-			if (numptr_val < 0)
-				return -3;      /* exponent less than 0 */
+			if (right_side_val < 0)
+				return "exponent less than 0";
 			c = 1;
-			while (--numptr_val >= 0)
-			    c *= rez;
+			while (--right_side_val >= 0)
+				c *= rez;
 			rez = c;
-		} else if (numptr_val==0)          /* zero divisor check */
-			return -2;
-		else if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
-			rez /= numptr_val;
-		else if (op == TOK_REM || op == TOK_REM_ASSIGN)
-			rez %= numptr_val;
+		}
+		else if (right_side_val == 0)
+			return "divide by zero";
+		else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
+		      || op == TOK_REM || op == TOK_REM_ASSIGN) {
+			/*
+			 * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))'
+			 *
+			 * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1
+			 * and thus is not representable.
+			 * Some CPUs segfault trying such op.
+			 * Others overfolw MAX_POSITIVE_INT+1 to
+			 * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000).
+			 * Make sure to at least not SEGV here:
+			 */
+			if (right_side_val == -1
+			 && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */
+			) {
+				right_side_val = 1;
+			}
+			if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
+				rez /= right_side_val;
+			else {
+				rez %= right_side_val;
+			}
+		}
 	}
-	if (tok_have_assign(op)) {
+
+	if (is_assign_op(op)) {
 		char buf[sizeof(arith_t)*3 + 2];
 
-		if (numptr_m1->var == NULL) {
+		if (top_of_stack->var == NULL) {
 			/* Hmm, 1=2 ? */
+//TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8
 			goto err;
 		}
-		/* save to shell variable */
-		sprintf(buf, arith_t_fmt, rez);
-		setvar(numptr_m1->var, buf);
-		/* after saving, make previous value for v++ or v-- */
+		/* Save to shell variable */
+		sprintf(buf, ARITH_FMT, rez);
+		setvar(top_of_stack->var, buf);
+		/* After saving, make previous value for v++ or v-- */
 		if (op == TOK_POST_INC)
 			rez--;
 		else if (op == TOK_POST_DEC)
 			rez++;
 	}
-	numptr_m1->val = rez;
-	/* erase var name, it is just a number now */
-	numptr_m1->var = NULL;
-	return 0;
+
+	top_of_stack->val = rez;
+	/* Erase var name, it is just a number now */
+	top_of_stack->var = NULL;
+	return NULL;
  err:
-	return -1;
+	return "arithmetic syntax error";
 #undef NUMPTR
 }
 
@@ -475,37 +513,26 @@ static const char op_tokens[] ALIGN1 = {
 };
 #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
 
-const char* FAST_FUNC
-endofname(const char *name)
-{
-	if (!is_name(*name))
-		return name;
-	while (*++name) {
-		if (!is_in_name(*name))
-			break;
-	}
-	return name;
-}
-
-arith_t
-arith(arith_state_t *math_state, const char *expr)
+static arith_t FAST_FUNC
+evaluate_string(arith_state_t *math_state, const char *expr)
 {
 	operator lasttok;
-	int errcode;
+	const char *errmsg;
 	const char *start_expr = expr = skip_whitespace(expr);
 	unsigned expr_len = strlen(expr) + 2;
 	/* Stack of integers */
-	/* The proof that there can be no more than strlen(startbuf)/2+1 integers
-	 * in any given correct or incorrect expression is left as an exercise to
-	 * the reader. */
-	v_n_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
-	v_n_t *numstackptr = numstack;
+	/* The proof that there can be no more than strlen(startbuf)/2+1
+	 * integers in any given correct or incorrect expression
+	 * is left as an exercise to the reader. */
+	var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
+	var_or_num_t *numstackptr = numstack;
 	/* Stack of operator tokens */
 	operator *const stack = alloca(expr_len * sizeof(stack[0]));
 	operator *stackptr = stack;
 
-	*stackptr++ = lasttok = TOK_LPAREN;     /* start off with a left paren */
-	errcode = 0;
+	/* Start with a left paren */
+	*stackptr++ = lasttok = TOK_LPAREN;
+	errmsg = NULL;
 
 	while (1) {
 		const char *p;
@@ -517,7 +544,7 @@ arith(arith_state_t *math_state, const char *expr)
 		arithval = *expr;
 		if (arithval == '\0') {
 			if (expr == start_expr) {
-				/* Null expression. */
+				/* Null expression */
 				numstack->val = 0;
 				goto ret;
 			}
@@ -541,7 +568,7 @@ arith(arith_state_t *math_state, const char *expr)
 			}
 			if (numstack->var) {
 				/* expression is $((var)) only, lookup now */
-				errcode = arith_lookup_val(math_state, numstack);
+				errmsg = arith_lookup_val(math_state, numstack);
 			}
 			goto ret;
 		}
@@ -554,7 +581,7 @@ arith(arith_state_t *math_state, const char *expr)
 			safe_strncpy(numstackptr->var, expr, var_name_size);
 			expr = p;
  num:
-			numstackptr->contidional_second_val_initialized = 0;
+			numstackptr->second_val_present = 0;
 			numstackptr++;
 			lasttok = TOK_NUM;
 			continue;
@@ -573,21 +600,32 @@ arith(arith_state_t *math_state, const char *expr)
 		/* Should be an operator */
 		p = op_tokens;
 		while (1) {
-			const char *e = expr;
+// TODO: bash allows 7+++v, treats it as 7 + ++v
+// we treat it as 7++ + v and reject
 			/* Compare expr to current op_tokens[] element */
-			while (*p && *e == *p)
-				p++, e++;
-			if (*p == '\0') { /* match: operator is found */
-				expr = e;
-				break;
+			const char *e = expr;
+			while (1) {
+				if (*p == '\0') {
+					/* Match: operator is found */
+					expr = e;
+					goto tok_found;
+				}
+				if (*p != *e)
+					break;
+				p++;
+				e++;
 			}
-			/* Go to next element of op_tokens[] */
+			/* No match, go to next element of op_tokens[] */
 			while (*p)
 				p++;
 			p += 2; /* skip NUL and TOK_foo bytes */
-			if (*p == '\0') /* no next element, operator not found */
+			if (*p == '\0') {
+				/* No next element, operator not found */
+				//math_state->syntax_error_at = expr;
 				goto err;
+			}
 		}
+ tok_found:
 		op = p[1]; /* fetch TOK_foo value */
 		/* NB: expr now points past the operator */
 
@@ -621,10 +659,10 @@ arith(arith_state_t *math_state, const char *expr)
 		 * integer stack.
 		 * But for binary operators, "apply" everything on the operator
 		 * stack until we find an operator with a lesser priority than the
-		 * one we have just extracted.
+		 * one we have just extracted. If op is right-associative,
+		 * then stop "applying" on the equal priority too.
 		 * Left paren is given the lowest priority so it will never be
 		 * "applied" in this way.
-		 * if associativity is right and priority eq, applied also skip
 		 */
 		prec = PREC(op);
 		if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
@@ -656,27 +694,36 @@ arith(arith_state_t *math_state, const char *expr)
 						break;
 					}
 				}
-				errcode = arith_apply(math_state, prev_op, numstack, &numstackptr);
-				if (errcode)
-					goto ret;
+				errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
+				if (errmsg)
+					goto err_with_custom_msg;
 			}
-			if (op == TOK_RPAREN) {
+			if (op == TOK_RPAREN)
 				goto err;
-			}
 		}
 
-		/* Push this operator to the stack and remember it. */
+		/* Push this operator to the stack and remember it */
 		*stackptr++ = lasttok = op;
  next: ;
 	} /* while (1) */
 
  err:
-	numstack->val = errcode = -1;
+	errmsg = "arithmetic syntax error";
+ err_with_custom_msg:
+	numstack->val = -1;
  ret:
-	math_state->errcode = errcode;
+	math_state->errmsg = errmsg;
 	return numstack->val;
 }
 
+arith_t FAST_FUNC
+arith(arith_state_t *math_state, const char *expr)
+{
+	math_state->errmsg = NULL;
+	math_state->list_of_recursed_names = NULL;
+	return evaluate_string(math_state, expr);
+}
+
 /*
  * Copyright (c) 1989, 1991, 1993, 1994
  *      The Regents of the University of California.  All rights reserved.