busybox/coreutils/tr.c

/* vi: set sw=4 ts=4: */
/*
 * Mini tr implementation for busybox
 *
 ** Copyright (c) 1987,1997, Prentice Hall   All rights reserved.
 *
 * The name of Prentice Hall may not be used to endorse or promote
 * products derived from this software without specific prior
 * written permission.
 *
 * Copyright (c) Michiel Huisjes
 *
 * This version of tr is adapted from Minix tr and was modified
 * by Erik Andersen <andersen@codepoet.org> to be used in busybox.
 *
 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
 */
/* http://www.opengroup.org/onlinepubs/009695399/utilities/tr.html
 * TODO: graph, print
 */

//kbuild:lib-$(CONFIG_TR) += tr.o

//config:config TR
//config:	bool "tr"
//config:	default y
//config:	help
//config:	  tr is used to squeeze, and/or delete characters from standard
//config:	  input, writing to standard output.
//config:
//config:config FEATURE_TR_CLASSES
//config:	bool "Enable character classes (such as [:upper:])"
//config:	default y
//config:	depends on TR
//config:	help
//config:	  Enable character classes, enabling commands such as:
//config:	  tr [:upper:] [:lower:] to convert input into lowercase.
//config:
//config:config FEATURE_TR_EQUIV
//config:	bool "Enable equivalence classes"
//config:	default y
//config:	depends on TR
//config:	help
//config:	  Enable equivalence classes, which essentially add the enclosed
//config:	  character to the current set. For instance, tr [=a=] xyz would
//config:	  replace all instances of 'a' with 'xyz'. This option is mainly
//config:	  useful for cases when no other way of expressing a character
//config:	  is possible.

#include "libbb.h"

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,
		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[(unsigned char)(string1[i])] = last;
		else
			pvector[(unsigned char)(string1[i])] = last = string2[j++];
	}
}

/* supported constructs:
 *   Ranges,  e.g.,  0-9   ==>  0123456789
 *   Escapes, e.g.,  \a    ==>  Control-G
 *   Character classes, e.g. [:upper:] ==> A...Z
 *   Equiv classess, e.g. [=A=] ==> A   (hmmmmmmm?)
 * not supported:
 *   \ooo-\ooo - octal ranges
 *   [x*N] - repeat char x N times
 *   [x*] - repeat char x until it fills STRING2:
 * # echo qwe123 | /usr/bin/tr 123456789 '[d]'
 * qwe[d]
 * # echo qwe123 | /usr/bin/tr 123456789 '[d*]'
 * qweddd
 */
static unsigned expand(const char *arg, char **buffer_p)
{
	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[pos++] = bb_process_escape_sequence(&arg);
			continue;
		}
		if (arg[1] == '-') { /* "0-9..." */
			ac = arg[2];
			if (ac == '\0') { /* "0-": copy verbatim */
				buffer[pos++] = *arg++; /* copy '0' */
				continue; /* next iter will copy '-' and stop */
			}
			i = (unsigned char) *arg;
			while (i <= ac) /* ok: i is unsigned _int_ */
				buffer[pos++] = i++;
			arg += 3; /* skip 0-9 */
			continue;
		}
		if ((ENABLE_FEATURE_TR_CLASSES || ENABLE_FEATURE_TR_EQUIV)
		 && *arg == '['
		) {
			arg++;
			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;
				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;
				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[pos++] = i;
				}
				if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_upper) {
					for (i = 'A'; i <= 'Z'; i++)
						buffer[pos++] = i;
				}
				if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_lower) {
					for (i = 'a'; i <= 'z'; i++)
						buffer[pos++] = i;
				}
				if (j == CLASS_space || j == CLASS_blank) {
					buffer[pos++] = '\t';
					if (j == CLASS_space) {
						buffer[pos++] = '\n';
						buffer[pos++] = '\v';
						buffer[pos++] = '\f';
						buffer[pos++] = '\r';
					}
					buffer[pos++] = ' ';
				}
				if (j == CLASS_punct || j == CLASS_cntrl) {
					for (i = '\0'; i < ASCII; i++) {
						if ((j == CLASS_punct && isprint_asciionly(i) && !isalnum(i) && !isspace(i))
						 || (j == CLASS_cntrl && iscntrl(i))
						) {
							buffer[pos++] = i;
						}
					}
				}
				if (j == CLASS_xdigit) {
					for (i = 'A'; i <= 'F'; i++) {
						buffer[pos + 6] = i | 0x20;
						buffer[pos++] = i;
					}
					pos += 6;
				}
				continue;
			}
			/* "[xyz...", i=x, arg points to y */
			if (ENABLE_FEATURE_TR_EQUIV && i == '=') { /* [=CHAR=] */
				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:
			 * 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.
			 */
 skip_bracket:
			arg -= 2; /* points to "[" in "[xyz..." */
		}
		buffer[pos++] = *arg++;
	}
	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 len;
	char conv[ASCII];
	unsigned char ch;

	len = 0;
	ch = '\0';
	while (1) {
		if (memchr(buffer, ch, buffer_len) == NULL)
			conv[len++] = ch;
		if (++ch == '\0')
			break;
	}
	memcpy(buffer, conv, len);
	return len;
}

int tr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
int tr_main(int argc UNUSED_PARAM, char **argv)
{
	int i;
	smalluint opts;
	ssize_t read_chars;
	size_t in_index, out_index;
	unsigned last = UCHAR_MAX + 1; /* not equal to any char */
	unsigned char coded, c;
	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	(3 << 0)
#define TR_OPT_delete		(1 << 2)
#define TR_OPT_squeeze_reps	(1 << 3)

	for (i = 0; i < ASCII; i++) {
		vector[i] = i;
		/*invec[i] = outvec[i] = FALSE; - done by xzalloc */
	}

	/* -C/-c difference is that -C complements "characters",
	 * and -c complements "values" (binary bytes I guess).
	 * In POSIX locale, these are the same.
	 */

	opt_complementary = "-1";
	opts = getopt32(argv, "+Ccds"); /* '+': stop at first non-option */
	argv += optind;

	str1_length = expand(*argv++, &str1);
	str2_length = 0;
	if (opts & 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, str2, out_index);
 start_from:
				out_index = 0;
			}
			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);
				break;
			}
			in_index = 0;
		}
		c = str1[in_index++];
		if ((opts & TR_OPT_delete) && invec[c])
			continue;
		coded = vector[c];
		if ((opts & TR_OPT_squeeze_reps) && last == coded
		 && (invec[c] || outvec[coded])
		) {
			continue;
		}
		str2[out_index++] = last = coded;
	}

	return EXIT_SUCCESS;
}
1	niro	532	/* vi: set sw=4 ts=4: */
2			/*
3			* Mini tr implementation for busybox
4			*
5			** Copyright (c) 1987,1997, Prentice Hall All rights reserved.
6			*
7			* The name of Prentice Hall may not be used to endorse or promote
8			* products derived from this software without specific prior
9			* written permission.
10			*
11			* Copyright (c) Michiel Huisjes
12			*
13			* This version of tr is adapted from Minix tr and was modified
14			* by Erik Andersen <andersen@codepoet.org> to be used in busybox.
15			*
16			* Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
17			*/
18	niro	816	/* http://www.opengroup.org/onlinepubs/009695399/utilities/tr.html
19	niro	984	* TODO: graph, print
20	niro	816	*/
21	niro	1123
22			//kbuild:lib-$(CONFIG_TR) += tr.o
23
24			//config:config TR
25			//config: bool "tr"
26			//config: default y
27			//config: help
28			//config: tr is used to squeeze, and/or delete characters from standard
29			//config: input, writing to standard output.
30			//config:
31			//config:config FEATURE_TR_CLASSES
32			//config: bool "Enable character classes (such as [:upper:])"
33			//config: default y
34			//config: depends on TR
35			//config: help
36			//config: Enable character classes, enabling commands such as:
37			//config: tr [:upper:] [:lower:] to convert input into lowercase.
38			//config:
39			//config:config FEATURE_TR_EQUIV
40			//config: bool "Enable equivalence classes"
41			//config: default y
42			//config: depends on TR
43			//config: help
44			//config: Enable equivalence classes, which essentially add the enclosed
45			//config: character to the current set. For instance, tr [=a=] xyz would
46			//config: replace all instances of 'a' with 'xyz'. This option is mainly
47			//config: useful for cases when no other way of expressing a character
48			//config: is possible.
49
50	niro	816	#include "libbb.h"
51	niro	532
52	niro	984	enum {
53			ASCII = 256,
54			/* string buffer needs to be at least as big as the whole "alphabet".
55			* BUFSIZ == ASCII is ok, but we will realloc in expand
56			* even for smallest patterns, let's avoid that by using *2:
57			*/
58			TR_BUFSIZ = (BUFSIZ > ASCII2) ? BUFSIZ : ASCII2,
59			};
60	niro	532
61	niro	816	static void map(char *pvector,
62	niro	984	char *string1, unsigned string1_len,
63			char *string2, unsigned string2_len)
64	niro	532	{
65			char last = '0';
66	niro	984	unsigned i, j;
67	niro	532
68			for (j = 0, i = 0; i < string1_len; i++) {
69			if (string2_len <= j)
70	niro	984	pvector[(unsigned char)(string1[i])] = last;
71	niro	532	else
72	niro	984	pvector[(unsigned char)(string1[i])] = last = string2[j++];
73	niro	532	}
74			}
75
76			/* supported constructs:
77	niro	816	* Ranges, e.g., 0-9 ==> 0123456789
78			* Escapes, e.g., \a ==> Control-G
79			* Character classes, e.g. [:upper:] ==> A...Z
80			* Equiv classess, e.g. [=A=] ==> A (hmmmmmmm?)
81	niro	984	* not supported:
82			* \ooo-\ooo - octal ranges
83			* [x*N] - repeat char x N times
84			* [x*] - repeat char x until it fills STRING2:
85			* # echo qwe123 \| /usr/bin/tr 123456789 '[d]'
86			* qwe[d]
87			* # echo qwe123 \| /usr/bin/tr 123456789 '[d*]'
88			* qweddd
89	niro	532	*/
90	niro	984	static unsigned expand(const char arg, char *buffer_p)
91	niro	532	{
92	niro	984	char buffer = buffer_p;
93			unsigned pos = 0;
94			unsigned size = TR_BUFSIZ;
95	niro	816	unsigned i; /* can't be unsigned char: must be able to hold 256 */
96			unsigned char ac;
97	niro	532
98			while (*arg) {
99	niro	984	if (pos + ASCII > size) {
100			size += ASCII;
101			*buffer_p = buffer = xrealloc(buffer, size);
102			}
103	niro	532	if (*arg == '\\') {
104			arg++;
105	niro	984	buffer[pos++] = bb_process_escape_sequence(&arg);
106	niro	816	continue;
107			}
108			if (arg[1] == '-') { /* "0-9..." */
109			ac = arg[2];
110			if (ac == '\0') { /* "0-": copy verbatim */
111	niro	984	buffer[pos++] = arg++; / copy '0' */
112	niro	816	continue; /* next iter will copy '-' and stop */
113	niro	532	}
114	niro	984	i = (unsigned char) *arg;
115	niro	816	while (i <= ac) /* ok: i is unsigned _int_ */
116	niro	984	buffer[pos++] = i++;
117	niro	816	arg += 3; /* skip 0-9 */
118			continue;
119			}
120	niro	984	if ((ENABLE_FEATURE_TR_CLASSES \|\| ENABLE_FEATURE_TR_EQUIV)
121			&& *arg == '['
122			) {
123	niro	532	arg++;
124	niro	984	i = (unsigned char) *arg++;
125			/* "[xyz...". i=x, arg points to y */
126			if (ENABLE_FEATURE_TR_CLASSES && i == ':') { /* [:class:] */
127	niro	816	#define CLO ":]\0"
128			static const char classes[] ALIGN1 =
129			"alpha"CLO "alnum"CLO "digit"CLO
130			"lower"CLO "upper"CLO "space"CLO
131	niro	984	"blank"CLO "punct"CLO "cntrl"CLO
132			"xdigit"CLO;
133			enum {
134			CLASS_invalid = 0, /* we increment the retval */
135			CLASS_alpha = 1,
136			CLASS_alnum = 2,
137			CLASS_digit = 3,
138			CLASS_lower = 4,
139			CLASS_upper = 5,
140			CLASS_space = 6,
141			CLASS_blank = 7,
142			CLASS_punct = 8,
143			CLASS_cntrl = 9,
144			CLASS_xdigit = 10,
145			//CLASS_graph = 11,
146			//CLASS_print = 12,
147			};
148	niro	816	smalluint j;
149	niro	984	char *tmp;
150
151			/* xdigit needs 8, not 7 */
152			i = 7 + (arg[0] == 'x');
153			tmp = xstrndup(arg, i);
154			j = index_in_strings(classes, tmp) + 1;
155			free(tmp);
156
157			if (j == CLASS_invalid)
158			goto skip_bracket;
159
160			arg += i;
161			if (j == CLASS_alnum \|\| j == CLASS_digit \|\| j == CLASS_xdigit) {
162	niro	532	for (i = '0'; i <= '9'; i++)
163	niro	984	buffer[pos++] = i;
164	niro	816	}
165			if (j == CLASS_alpha \|\| j == CLASS_alnum \|\| j == CLASS_upper) {
166	niro	532	for (i = 'A'; i <= 'Z'; i++)
167	niro	984	buffer[pos++] = i;
168	niro	532	}
169	niro	816	if (j == CLASS_alpha \|\| j == CLASS_alnum \|\| j == CLASS_lower) {
170	niro	532	for (i = 'a'; i <= 'z'; i++)
171	niro	984	buffer[pos++] = i;
172	niro	532	}
173	niro	816	if (j == CLASS_space \|\| j == CLASS_blank) {
174	niro	984	buffer[pos++] = '\t';
175	niro	816	if (j == CLASS_space) {
176	niro	984	buffer[pos++] = '\n';
177			buffer[pos++] = '\v';
178			buffer[pos++] = '\f';
179			buffer[pos++] = '\r';
180	niro	816	}
181	niro	984	buffer[pos++] = ' ';
182	niro	532	}
183	niro	816	if (j == CLASS_punct \|\| j == CLASS_cntrl) {
184	niro	984	for (i = '\0'; i < ASCII; i++) {
185			if ((j == CLASS_punct && isprint_asciionly(i) && !isalnum(i) && !isspace(i))
186			\|\| (j == CLASS_cntrl && iscntrl(i))
187			) {
188			buffer[pos++] = i;
189			}
190			}
191	niro	532	}
192	niro	984	if (j == CLASS_xdigit) {
193			for (i = 'A'; i <= 'F'; i++) {
194			buffer[pos + 6] = i \| 0x20;
195			buffer[pos++] = i;
196			}
197			pos += 6;
198	niro	532	}
199	niro	984	continue;
200	niro	532	}
201	niro	816	/* "[xyz...", i=x, arg points to y */
202			if (ENABLE_FEATURE_TR_EQUIV && i == '=') { /* [=CHAR=] */
203	niro	984	buffer[pos++] = arg; / copy CHAR */
204			if (!arg[0] \|\| arg[1] != '=' \|\| arg[2] != ']')
205	niro	816	bb_show_usage();
206			arg += 3; /* skip CHAR=] */
207	niro	532	continue;
208			}
209	niro	984	/* The rest of "[xyz..." cases is treated as normal
210			* string, "[" has no special meaning here:
211			* tr "[a-z]" "[A-Z]" can be written as tr "a-z" "A-Z",
212			* also try tr "[a-z]" "_A-Z+" and you'll see that
213			* [] is not special here.
214			*/
215			skip_bracket:
216			arg -= 2; /* points to "[" in "[xyz..." */
217	niro	816	}
218	niro	984	buffer[pos++] = *arg++;
219	niro	532	}
220	niro	984	return pos;
221	niro	532	}
222
223	niro	984	/* NB: buffer is guaranteed to be at least TR_BUFSIZE
224			* (which is >= ASCII) big.
225			*/
226	niro	532	static int complement(char *buffer, int buffer_len)
227			{
228	niro	984	int len;
229			char conv[ASCII];
230			unsigned char ch;
231	niro	532
232	niro	984	len = 0;
233			ch = '\0';
234			while (1) {
235			if (memchr(buffer, ch, buffer_len) == NULL)
236			conv[len++] = ch;
237			if (++ch == '\0')
238			break;
239	niro	532	}
240	niro	984	memcpy(buffer, conv, len);
241			return len;
242	niro	532	}
243
244	niro	816	int tr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
245			int tr_main(int argc UNUSED_PARAM, char **argv)
246	niro	532	{
247			int i;
248	niro	984	smalluint opts;
249			ssize_t read_chars;
250			size_t in_index, out_index;
251	niro	816	unsigned last = UCHAR_MAX + 1; /* not equal to any char */
252			unsigned char coded, c;
253	niro	984	char *str1 = xmalloc(TR_BUFSIZ);
254			char *str2 = xmalloc(TR_BUFSIZ);
255			int str2_length;
256			int str1_length;
257			char vector = xzalloc(ASCII 3);
258			char *invec = vector + ASCII;
259			char outvec = vector + ASCII 2;
260	niro	532
261	niro	984	#define TR_OPT_complement (3 << 0)
262			#define TR_OPT_delete (1 << 2)
263			#define TR_OPT_squeeze_reps (1 << 3)
264	niro	532
265	niro	984	for (i = 0; i < ASCII; i++) {
266	niro	532	vector[i] = i;
267	niro	816	/invec[i] = outvec[i] = FALSE; - done by xzalloc /
268	niro	532	}
269
270	niro	984	/* -C/-c difference is that -C complements "characters",
271			* and -c complements "values" (binary bytes I guess).
272			* In POSIX locale, these are the same.
273			*/
274
275			opt_complementary = "-1";
276			opts = getopt32(argv, "+Ccds"); /* '+': stop at first non-option */
277			argv += optind;
278
279			str1_length = expand(*argv++, &str1);
280			str2_length = 0;
281			if (opts & TR_OPT_complement)
282			str1_length = complement(str1, str1_length);
283			if (*argv) {
284			if (argv[0][0] == '\0')
285			bb_error_msg_and_die("STRING2 cannot be empty");
286			str2_length = expand(*argv, &str2);
287			map(vector, str1, str1_length,
288			str2, str2_length);
289	niro	532	}
290	niro	984	for (i = 0; i < str1_length; i++)
291			invec[(unsigned char)(str1[i])] = TRUE;
292			for (i = 0; i < str2_length; i++)
293			outvec[(unsigned char)(str2[i])] = TRUE;
294	niro	816
295	niro	984	goto start_from;
296
297			/* In this loop, str1 space is reused as input buffer,
298			* str2 - as output one. */
299	niro	816	for (;;) {
300			/* If we're out of input, flush output and read more input. */
301			if ((ssize_t)in_index == read_chars) {
302			if (out_index) {
303	niro	984	xwrite(STDOUT_FILENO, str2, out_index);
304			start_from:
305	niro	816	out_index = 0;
306			}
307	niro	984	read_chars = safe_read(STDIN_FILENO, str1, TR_BUFSIZ);
308	niro	816	if (read_chars <= 0) {
309			if (read_chars < 0)
310			bb_perror_msg_and_die(bb_msg_read_error);
311	niro	984	break;
312	niro	816	}
313			in_index = 0;
314			}
315	niro	984	c = str1[in_index++];
316			if ((opts & TR_OPT_delete) && invec[c])
317			continue;
318	niro	816	coded = vector[c];
319	niro	984	if ((opts & TR_OPT_squeeze_reps) && last == coded
320			&& (invec[c] \|\| outvec[coded])
321			) {
322	niro	816	continue;
323	niro	984	}
324			str2[out_index++] = last = coded;
325	niro	816	}
326	niro	984
327	niro	816	return EXIT_SUCCESS;
328	niro	532	}