tr: fix overflow in expand and complement, fix stop after [:class:],

 fix order of [:xdigit:], make tr require one param at least.

function                                             old     new   delta
expand                                              1743    1849    +106
tr_main                                              463     518     +55
complement                                            72      75      +3
------------------------------------------------------------------------------
(add/remove: 0/0 grow/shrink: 3/0 up/down: 164/0)             Total: 164 bytes

1 files changed, 131 insertions, 104 deletions

diff --git a/coreutils/tr.c b/coreutils/tr.c
index cd31b8550..bf6fa2996 100644
--- a/coreutils/tr.c
+++ b/coreutils/tr.c
@@ -16,24 +16,31 @@
  * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
  */
 /* http://www.opengroup.org/onlinepubs/009695399/utilities/tr.html
- * TODO: xdigit, graph, print
+ * TODO: graph, print
  */
 #include "libbb.h"
 
-#define ASCII 0377
+enum {
+	ASCII = 256,
+	/* string buffer needs to be at least as big as the whole "alphabet".
+	 * BUFSIZ == ASCII is ok, but we will realloc in expand
+	 * even for smallest patterns, let's avoid that by using *2:
+	 */
+	TR_BUFSIZ = (BUFSIZ > ASCII*2) ? BUFSIZ : ASCII*2,
+};
 
 static void map(char *pvector,
-		unsigned char *string1, unsigned string1_len,
-		unsigned char *string2, unsigned string2_len)
+		char *string1, unsigned string1_len,
+		char *string2, unsigned string2_len)
 {
 	char last = '0';
 	unsigned i, j;
 
 	for (j = 0, i = 0; i < string1_len; i++) {
 		if (string2_len <= j)
-			pvector[string1[i]] = last;
+			pvector[(unsigned char)(string1[i])] = last;
 		else
-			pvector[string1[i]] = last = string2[j++];
+			pvector[(unsigned char)(string1[i])] = last = string2[j++];
 	}
 }
 
@@ -43,139 +50,155 @@ static void map(char *pvector,
  *   Character classes, e.g. [:upper:] ==> A...Z
  *   Equiv classess, e.g. [=A=] ==> A   (hmmmmmmm?)
  */
-static unsigned expand(const char *arg, char *buffer)
+static unsigned expand(const char *arg, char **buffer_p)
 {
-	char *buffer_start = buffer;
+	char *buffer = *buffer_p;
+	unsigned pos = 0;
+	unsigned size = TR_BUFSIZ;
 	unsigned i; /* can't be unsigned char: must be able to hold 256 */
 	unsigned char ac;
 
 	while (*arg) {
+		if (pos + ASCII > size) {
+			size += ASCII;
+			*buffer_p = buffer = xrealloc(buffer, size);
+		}
 		if (*arg == '\\') {
 			arg++;
-			*buffer++ = bb_process_escape_sequence(&arg);
+			buffer[pos++] = bb_process_escape_sequence(&arg);
 			continue;
 		}
 		if (arg[1] == '-') { /* "0-9..." */
 			ac = arg[2];
 			if (ac == '\0') { /* "0-": copy verbatim */
-				*buffer++ = *arg++; /* copy '0' */
+				buffer[pos++] = *arg++; /* copy '0' */
 				continue; /* next iter will copy '-' and stop */
 			}
-			i = *arg;
+			i = (unsigned char) *arg;
 			while (i <= ac) /* ok: i is unsigned _int_ */
-				*buffer++ = i++;
+				buffer[pos++] = i++;
 			arg += 3; /* skip 0-9 */
 			continue;
 		}
-		if (*arg == '[') { /* "[xyz..." */
+		if ((ENABLE_FEATURE_TR_CLASSES || ENABLE_FEATURE_TR_EQUIV)
+		 && *arg == '['
+		) {
 			arg++;
-			i = *arg++;
-			/* "[xyz...", i=x, arg points to y */
-			if (ENABLE_FEATURE_TR_CLASSES && i == ':') {
+			i = (unsigned char) *arg++;
+			/* "[xyz...". i=x, arg points to y */
+			if (ENABLE_FEATURE_TR_CLASSES && i == ':') { /* [:class:] */
 #define CLO ":]\0"
 				static const char classes[] ALIGN1 =
 					"alpha"CLO "alnum"CLO "digit"CLO
 					"lower"CLO "upper"CLO "space"CLO
 					"blank"CLO "punct"CLO "cntrl"CLO
 					"xdigit"CLO;
-#define CLASS_invalid 0 /* we increment the retval */
-#define CLASS_alpha 1
-#define CLASS_alnum 2
-#define CLASS_digit 3
-#define CLASS_lower 4
-#define CLASS_upper 5
-#define CLASS_space 6
-#define CLASS_blank 7
-#define CLASS_punct 8
-#define CLASS_cntrl 9
-#define CLASS_xdigit 10
-//#define CLASS_graph 11
-//#define CLASS_print 12
+				enum {
+					CLASS_invalid = 0, /* we increment the retval */
+					CLASS_alpha = 1,
+					CLASS_alnum = 2,
+					CLASS_digit = 3,
+					CLASS_lower = 4,
+					CLASS_upper = 5,
+					CLASS_space = 6,
+					CLASS_blank = 7,
+					CLASS_punct = 8,
+					CLASS_cntrl = 9,
+					CLASS_xdigit = 10,
+					//CLASS_graph = 11,
+					//CLASS_print = 12,
+				};
 				smalluint j;
-				{
-					/* xdigit needs 8, not 7 */
-					char *tmp = xstrndup(arg, 7 + (arg[0]=='x'));
-					j = index_in_strings(classes, tmp) + 1;
-					free(tmp);
-				}
+				char *tmp;
+
+				/* xdigit needs 8, not 7 */
+				i = 7 + (arg[0] == 'x');
+				tmp = xstrndup(arg, i);
+				j = index_in_strings(classes, tmp) + 1;
+				free(tmp);
+
+				if (j == CLASS_invalid)
+					goto skip_bracket;
+
+				arg += i;
 				if (j == CLASS_alnum || j == CLASS_digit || j == CLASS_xdigit) {
 					for (i = '0'; i <= '9'; i++)
-						*buffer++ = i;
+						buffer[pos++] = i;
 				}
 				if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_upper) {
 					for (i = 'A'; i <= 'Z'; i++)
-						*buffer++ = i;
+						buffer[pos++] = i;
 				}
 				if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_lower) {
 					for (i = 'a'; i <= 'z'; i++)
-						*buffer++ = i;
+						buffer[pos++] = i;
 				}
 				if (j == CLASS_space || j == CLASS_blank) {
-					*buffer++ = '\t';
+					buffer[pos++] = '\t';
 					if (j == CLASS_space) {
-						*buffer++ = '\n';
-						*buffer++ = '\v';
-						*buffer++ = '\f';
-						*buffer++ = '\r';
+						buffer[pos++] = '\n';
+						buffer[pos++] = '\v';
+						buffer[pos++] = '\f';
+						buffer[pos++] = '\r';
 					}
-					*buffer++ = ' ';
+					buffer[pos++] = ' ';
 				}
 				if (j == CLASS_punct || j == CLASS_cntrl) {
-					for (i = '\0'; i <= ASCII; i++)
+					for (i = '\0'; i < ASCII; i++) {
 						if ((j == CLASS_punct && isprint(i) && !isalnum(i) && !isspace(i))
-						 || (j == CLASS_cntrl && iscntrl(i)))
-							*buffer++ = i;
+						 || (j == CLASS_cntrl && iscntrl(i))
+						) {
+							buffer[pos++] = i;
+						}
+					}
 				}
 				if (j == CLASS_xdigit) {
 					for (i = 'A'; i <= 'F'; i++) {
-						*buffer++ = i;
-						*buffer++ = i | 0x20;
+						buffer[pos + 6] = i | 0x20;
+						buffer[pos++] = i;
 					}
+					pos += 6;
 				}
-				if (j == CLASS_invalid) {
-					*buffer++ = '[';
-					*buffer++ = ':';
-					continue;
-				}
-				break;
+				continue;
 			}
 			/* "[xyz...", i=x, arg points to y */
 			if (ENABLE_FEATURE_TR_EQUIV && i == '=') { /* [=CHAR=] */
-				*buffer++ = *arg; /* copy CHAR */
-				if (!*arg || arg[1] != '=' || arg[2] != ']')
+				buffer[pos++] = *arg; /* copy CHAR */
+				if (!arg[0] || arg[1] != '=' || arg[2] != ']')
 					bb_show_usage();
 				arg += 3;	/* skip CHAR=] */
 				continue;
 			}
-			/* The rest of [xyz... cases is treated as normal
-			 * string, '[' has no special meaning here:
+			/* The rest of "[xyz..." cases is treated as normal
+			 * string, "[" has no special meaning here:
 			 * tr "[a-z]" "[A-Z]" can be written as tr "a-z" "A-Z",
 			 * also try tr "[a-z]" "_A-Z+" and you'll see that
 			 * [] is not special here.
 			 */
-			*buffer++ = '[';
-			arg--; /* points to x */
-			continue;
+ skip_bracket:
+			arg -= 2; /* points to "[" in "[xyz..." */
 		}
-		*buffer++ = *arg++;
+		buffer[pos++] = *arg++;
 	}
-	return (buffer - buffer_start);
+	return pos;
 }
 
+/* NB: buffer is guaranteed to be at least TR_BUFSIZE
+ * (which is >= ASCII) big.
+ */
 static int complement(char *buffer, int buffer_len)
 {
-	int ch, j, len;
-	char conv[ASCII + 2];
+	int len;
+	char conv[ASCII];
+	unsigned char ch;
 
 	len = 0;
-	for (ch = '\0'; ch <= ASCII; ch++) {
-		for (j = 0; j < buffer_len; j++)
-			if (buffer[j] == ch)
-				goto next_ch;
-		/* Didn't find it */
-		conv[len++] = (char) ch;
- next_ch:
-		continue;
+	ch = '\0';
+	while (1) {
+		if (memchr(buffer, ch, buffer_len) == NULL)
+			conv[len++] = ch;
+		if (++ch == '\0')
+			break;
 	}
 	memcpy(buffer, conv, len);
 	return len;
@@ -190,54 +213,56 @@ int tr_main(int argc UNUSED_PARAM, char **argv)
 	size_t in_index, out_index;
 	unsigned last = UCHAR_MAX + 1; /* not equal to any char */
 	unsigned char coded, c;
-	unsigned char *output = xmalloc(BUFSIZ);
-	char *vector = xzalloc((ASCII+1) * 3);
-	char *invec  = vector + (ASCII+1);
-	char *outvec = vector + (ASCII+1) * 2;
+	char *str1 = xmalloc(TR_BUFSIZ);
+	char *str2 = xmalloc(TR_BUFSIZ);
+	int str2_length;
+	int str1_length;
+	char *vector = xzalloc(ASCII * 3);
+	char *invec  = vector + ASCII;
+	char *outvec = vector + ASCII * 2;
 
 #define TR_OPT_complement	(1 << 0)
 #define TR_OPT_delete		(1 << 1)
 #define TR_OPT_squeeze_reps	(1 << 2)
 
-	flags = getopt32(argv, "+cds"); /* '+': stop at first non-option */
-	argv += optind;
-
-	for (i = 0; i <= ASCII; i++) {
+	for (i = 0; i < ASCII; i++) {
 		vector[i] = i;
 		/*invec[i] = outvec[i] = FALSE; - done by xzalloc */
 	}
 
-#define tr_buf bb_common_bufsiz1
-	if (*argv != NULL) {
-		int output_length = 0;
-		int input_length;
+	opt_complementary = "-1";
+	flags = getopt32(argv, "+cds"); /* '+': stop at first non-option */
+	argv += optind;
 
-		input_length = expand(*argv++, tr_buf);
-		if (flags & TR_OPT_complement)
-			input_length = complement(tr_buf, input_length);
-		if (*argv) {
-			if (argv[0][0] == '\0')
-				bb_error_msg_and_die("STRING2 cannot be empty");
-			output_length = expand(*argv, (char *)output);
-			map(vector, (unsigned char *)tr_buf, input_length, output, output_length);
-		}
-		for (i = 0; i < input_length; i++)
-			invec[(unsigned char)tr_buf[i]] = TRUE;
-		for (i = 0; i < output_length; i++)
-			outvec[output[i]] = TRUE;
+	str1_length = expand(*argv++, &str1);
+	str2_length = 0;
+	if (flags & TR_OPT_complement)
+		str1_length = complement(str1, str1_length);
+	if (*argv) {
+		if (argv[0][0] == '\0')
+			bb_error_msg_and_die("STRING2 cannot be empty");
+		str2_length = expand(*argv, &str2);
+		map(vector, str1, str1_length,
+				str2, str2_length);
 	}
+	for (i = 0; i < str1_length; i++)
+		invec[(unsigned char)(str1[i])] = TRUE;
+	for (i = 0; i < str2_length; i++)
+		outvec[(unsigned char)(str2[i])] = TRUE;
 
 	goto start_from;
 
+	/* In this loop, str1 space is reused as input buffer,
+	 * str2 - as output one. */
 	for (;;) {
 		/* If we're out of input, flush output and read more input. */
 		if ((ssize_t)in_index == read_chars) {
 			if (out_index) {
-				xwrite(STDOUT_FILENO, (char *)output, out_index);
+				xwrite(STDOUT_FILENO, str2, out_index);
  start_from:
 				out_index = 0;
 			}
-			read_chars = safe_read(STDIN_FILENO, tr_buf, BUFSIZ);
+			read_chars = safe_read(STDIN_FILENO, str1, TR_BUFSIZ);
 			if (read_chars <= 0) {
 				if (read_chars < 0)
 					bb_perror_msg_and_die(bb_msg_read_error);
@@ -245,14 +270,16 @@ int tr_main(int argc UNUSED_PARAM, char **argv)
 			}
 			in_index = 0;
 		}
-		c = tr_buf[in_index++];
+		c = str1[in_index++];
 		if ((flags & TR_OPT_delete) && invec[c])
 			continue;
 		coded = vector[c];
 		if ((flags & TR_OPT_squeeze_reps) && last == coded
-		 && (invec[c] || outvec[coded]))
+		 && (invec[c] || outvec[coded])
+		) {
 			continue;
-		output[out_index++] = last = coded;
+		}
+		str2[out_index++] = last = coded;
 	}
 
 	return EXIT_SUCCESS;