expr: fix comparisons 'a < b' where we were overflowing a-b

(not to mention that we used int, not arith_t). closes bug 2744.
Also, shrink a bit and add testsuite entry

function                                             old     new   delta
nextarg                                               75      84      +9
tostring                                              38      35      -3
toarith                                               89      86      -3
str_value                                             35      32      -3
eval6                                                555     552      -3
int_value                                             29      23      -6
eval4                                                128     120      -8
eval3                                                112     104      -8
eval2                                                512     417     -95
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 1/8 up/down: 9/-129)           Total: -120 bytes

2 files changed, 100 insertions, 87 deletions

diff --git a/coreutils/expr.c b/coreutils/expr.c
index 959f5200c..2f9c5c1e3 100644
--- a/coreutils/expr.c
+++ b/coreutils/expr.c
@@ -28,13 +28,6 @@
 #include "libbb.h"
 #include "xregex.h"
 
-/* The kinds of value we can have.  */
-enum valtype {
-	integer,
-	string
-};
-typedef enum valtype TYPE;
-
 #if ENABLE_EXPR_MATH_SUPPORT_64
 typedef int64_t arith_t;
 
@@ -51,10 +44,16 @@ typedef long arith_t;
 
 /* TODO: use bb_strtol[l]? It's easier to check for errors... */
 
+/* The kinds of value we can have.  */
+enum {
+	INTEGER,
+	STRING
+};
+
 /* A value is.... */
 struct valinfo {
-	TYPE type;			/* Which kind. */
-	union {				/* The value itself. */
+	smallint type;                  /* Which kind. */
+	union {                         /* The value itself. */
 		arith_t i;
 		char *s;
 	} u;
@@ -77,8 +76,9 @@ static VALUE *int_value(arith_t i)
 {
 	VALUE *v;
 
-	v = xmalloc(sizeof(VALUE));
-	v->type = integer;
+	v = xzalloc(sizeof(VALUE));
+	if (INTEGER) /* otherwise xzaaloc did it already */
+		v->type = INTEGER;
 	v->u.i = i;
 	return v;
 }
@@ -89,46 +89,47 @@ static VALUE *str_value(const char *s)
 {
 	VALUE *v;
 
-	v = xmalloc(sizeof(VALUE));
-	v->type = string;
+	v = xzalloc(sizeof(VALUE));
+	if (STRING) /* otherwise xzaaloc did it already */
+		v->type = STRING;
 	v->u.s = xstrdup(s);
 	return v;
 }
 
 /* Free VALUE V, including structure components.  */
 
-static void freev(VALUE * v)
+static void freev(VALUE *v)
 {
-	if (v->type == string)
+	if (v->type == STRING)
 		free(v->u.s);
 	free(v);
 }
 
 /* Return nonzero if V is a null-string or zero-number.  */
 
-static int null(VALUE * v)
+static int null(VALUE *v)
 {
-	if (v->type == integer)
+	if (v->type == INTEGER)
 		return v->u.i == 0;
-	/* string: */
+	/* STRING: */
 	return v->u.s[0] == '\0' || LONE_CHAR(v->u.s, '0');
 }
 
-/* Coerce V to a string value (can't fail).  */
+/* Coerce V to a STRING value (can't fail).  */
 
-static void tostring(VALUE * v)
+static void tostring(VALUE *v)
 {
-	if (v->type == integer) {
+	if (v->type == INTEGER) {
 		v->u.s = xasprintf("%" PF_REZ "d", PF_REZ_TYPE v->u.i);
-		v->type = string;
+		v->type = STRING;
 	}
 }
 
-/* Coerce V to an integer value.  Return 1 on success, 0 on failure.  */
+/* Coerce V to an INTEGER value.  Return 1 on success, 0 on failure.  */
 
-static bool toarith(VALUE * v)
+static bool toarith(VALUE *v)
 {
-	if (v->type == string) {
+	if (v->type == STRING) {
 		arith_t i;
 		char *e;
 
@@ -139,50 +140,54 @@ static bool toarith(VALUE * v)
 			return 0;
 		free(v->u.s);
 		v->u.i = i;
-		v->type = integer;
+		v->type = INTEGER;
 	}
 	return 1;
 }
 
-/* Return nonzero if the next token matches STR exactly.
+/* Return str[0]+str[1] if the next token matches STR exactly.
    STR must not be NULL.  */
 
-static bool nextarg(const char *str)
+static int nextarg(const char *str)
 {
-	if (*G.args == NULL)
+	if (*G.args == NULL || strcmp(*G.args, str) != 0)
 		return 0;
-	return strcmp(*G.args, str) == 0;
+	return (unsigned char)str[0] + (unsigned char)str[1];
 }
 
 /* The comparison operator handling functions.  */
 
-static int cmp_common(VALUE * l, VALUE * r, int op)
+static int cmp_common(VALUE *l, VALUE *r, int op)
 {
-	int cmpval;
+	arith_t ll, rr;
 
-	if (l->type == string || r->type == string) {
+	ll = l->u.i;
+	rr = r->u.i;
+	if (l->type == STRING || r->type == STRING) {
 		tostring(l);
 		tostring(r);
-		cmpval = strcmp(l->u.s, r->u.s);
-	} else
-		cmpval = l->u.i - r->u.i;
+		ll = strcmp(l->u.s, r->u.s);
+		rr = 0;
+	}
+	/* calculating ll - rr and checking the result is prone to overflows.
+	 * We'll do it differently: */
 	if (op == '<')
-		return cmpval < 0;
-	if (op == ('L' + 'E'))
-		return cmpval <= 0;
-	if (op == '=')
-		return cmpval == 0;
-	if (op == '!')
-		return cmpval != 0;
+		return ll < rr;
+	if (op == ('<' + '='))
+		return ll <= rr;
+	if (op == '=' || (op == '=' + '='))
+		return ll == rr;
+	if (op == '!' + '=')
+		return ll != rr;
 	if (op == '>')
-		return cmpval > 0;
+		return ll > rr;
 	/* >= */
-	return cmpval >= 0;
+	return ll >= rr;
 }
 
 /* The arithmetic operator handling functions.  */
 
-static arith_t arithmetic_common(VALUE * l, VALUE * r, int op)
+static arith_t arithmetic_common(VALUE *l, VALUE *r, int op)
 {
 	arith_t li, ri;
 
@@ -190,25 +195,24 @@ static arith_t arithmetic_common(VALUE * l, VALUE * r, int op)
 		bb_error_msg_and_die("non-numeric argument");
 	li = l->u.i;
 	ri = r->u.i;
-	if ((op == '/' || op == '%') && ri == 0)
-		bb_error_msg_and_die("division by zero");
 	if (op == '+')
 		return li + ri;
-	else if (op == '-')
+	if (op == '-')
 		return li - ri;
-	else if (op == '*')
+	if (op == '*')
 		return li * ri;
-	else if (op == '/')
+	if (ri == 0)
+		bb_error_msg_and_die("division by zero");
+	if (op == '/')
 		return li / ri;
-	else
-		return li % ri;
+	return li % ri;
 }
 
 /* Do the : operator.
    SV is the VALUE for the lhs (the string),
    PV is the VALUE for the rhs (the pattern).  */
 
-static VALUE *docolon(VALUE * sv, VALUE * pv)
+static VALUE *docolon(VALUE *sv, VALUE *pv)
 {
 	VALUE *v;
 	regex_t re_buffer;
@@ -230,14 +234,16 @@ of a basic regular expression is not portable; it is being ignored", pv->u.s);
 
 	/* expr uses an anchored pattern match, so check that there was a
 	 * match and that the match starts at offset 0. */
-	if (regexec(&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH &&
-		re_regs[0].rm_so == 0) {
+	if (regexec(&re_buffer, sv->u.s, NMATCH, re_regs, 0) != REG_NOMATCH
+	 && re_regs[0].rm_so == 0
+	) {
 		/* Were \(...\) used? */
 		if (re_buffer.re_nsub > 0) {
 			sv->u.s[re_regs[1].rm_eo] = '\0';
 			v = str_value(sv->u.s + re_regs[1].rm_so);
-		} else
+		} else {
 			v = int_value(re_regs[0].rm_eo);
+		}
 	} else {
 		/* Match failed -- return the right kind of null.  */
 		if (re_buffer.re_nsub > 0)
@@ -327,7 +333,7 @@ static VALUE *eval6(void)
 			v = str_value("");
 		else {
 			v = xmalloc(sizeof(VALUE));
-			v->type = string;
+			v->type = STRING;
 			v->u.s = xstrndup(l->u.s + i1->u.i - 1, i2->u.i);
 		}
 		freev(l);
@@ -367,14 +373,11 @@ static VALUE *eval4(void)
 
 	l = eval5();
 	while (1) {
-		if (nextarg("*"))
-			op = '*';
-		else if (nextarg("/"))
-			op = '/';
-		else if (nextarg("%"))
-			op = '%';
-		else
-			return l;
+		op = nextarg("*");
+		if (!op) { op = nextarg("/");
+		 if (!op) { op = nextarg("%");
+		  if (!op) return l;
+		}}
 		G.args++;
 		r = eval5();
 		val = arithmetic_common(l, r, op);
@@ -394,12 +397,11 @@ static VALUE *eval3(void)
 
 	l = eval4();
 	while (1) {
-		if (nextarg("+"))
-			op = '+';
-		else if (nextarg("-"))
-			op = '-';
-		else
-			return l;
+		op = nextarg("+");
+		if (!op) {
+			op = nextarg("-");
+			if (!op) return l;
+		}
 		G.args++;
 		r = eval4();
 		val = arithmetic_common(l, r, op);
@@ -419,20 +421,15 @@ static VALUE *eval2(void)
 
 	l = eval3();
 	while (1) {
-		if (nextarg("<"))
-			op = '<';
-		else if (nextarg("<="))
-			op = 'L' + 'E';
-		else if (nextarg("=") || nextarg("=="))
-			op = '=';
-		else if (nextarg("!="))
-			op = '!';
-		else if (nextarg(">="))
-			op = 'G' + 'E';
-		else if (nextarg(">"))
-			op = '>';
-		else
-			return l;
+		op = nextarg("<");
+		if (!op) { op = nextarg("<=");
+		 if (!op) { op = nextarg("=");
+		  if (!op) { op = nextarg("==");
+		   if (!op) { op = nextarg("!=");
+		    if (!op) { op = nextarg(">=");
+		     if (!op) { op = nextarg(">");
+		      if (!op) return l;
+		}}}}}}
 		G.args++;
 		r = eval3();
 		toarith(l);
@@ -498,7 +495,7 @@ int expr_main(int argc, char **argv)
 	if (*G.args)
 		bb_error_msg_and_die("syntax error");
 
-	if (v->type == integer)
+	if (v->type == INTEGER)
 		printf("%" PF_REZ "d\n", PF_REZ_TYPE v->u.i);
 	else
 		puts(v->u.s);
diff --git a/testsuite/expr/expr-big b/testsuite/expr/expr-big
new file mode 100644
index 000000000..23dbbb3c8
--- /dev/null
+++ b/testsuite/expr/expr-big
@@ -0,0 +1,16 @@
+# busybox expr
+
+# 3*1000*1000*1000 overflows 32-bit signed int
+res=`busybox expr 0 '<' 3000000000`
+[ x"$res" = x1 ] || exit 1
+
+# 9223372036854775807 = 2^31-1
+res=`busybox expr 0 '<' 9223372036854775807`
+[ x"$res" = x1 ] || exit 1
+# coreutils fails this one!
+res=`busybox expr -9223372036854775800 '<' 9223372036854775807`
+[ x"$res" = x1 ] || exit 1
+
+# This one works only by chance
+# res=`busybox expr 0 '<' 9223372036854775808`
+# [ x"$res" = x1 ] || exit 1