coreutils/tr.c

   1 /* 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 /* http://www.opengroup.org/onlinepubs/009695399/utilities/tr.html
  19  * TODO: graph, print
  20  */
  21 #include "libbb.h"
  22
  23 enum {
  24         ASCII = 256,
  25         /* string buffer needs to be at least as big as the whole "alphabet".
  26          * BUFSIZ == ASCII is ok, but we will realloc in expand
  27          * even for smallest patterns, let's avoid that by using *2:
  28          */
  29         TR_BUFSIZ = (BUFSIZ > ASCII*2) ? BUFSIZ : ASCII*2,
  30 };
  31
  32 static void map(char *pvector,
  33                 char *string1, unsigned string1_len,
  34                 char *string2, unsigned string2_len)
  35 {
  36         char last = '0';
  37         unsigned i, j;
  38
  39         for (j = 0, i = 0; i < string1_len; i++) {
  40                 if (string2_len <= j)
  41                         pvector[(unsigned char)(string1[i])] = last;
  42                 else
  43                         pvector[(unsigned char)(string1[i])] = last = string2[j++];
  44         }
  45 }
  46
  47 /* supported constructs:
  48  *   Ranges,  e.g.,  0-9   ==>  0123456789
  49  *   Escapes, e.g.,  \a    ==>  Control-G
  50  *   Character classes, e.g. [:upper:] ==> A...Z
  51  *   Equiv classess, e.g. [=A=] ==> A   (hmmmmmmm?)
  52  */
  53 static unsigned expand(const char *arg, char **buffer_p)
  54 {
  55         char *buffer = *buffer_p;
  56         unsigned pos = 0;
  57         unsigned size = TR_BUFSIZ;
  58         unsigned i; /* can't be unsigned char: must be able to hold 256 */
  59         unsigned char ac;
  60
  61         while (*arg) {
  62                 if (pos + ASCII > size) {
  63                         size += ASCII;
  64                         *buffer_p = buffer = xrealloc(buffer, size);
  65                 }
  66                 if (*arg == '\\') {
  67                         arg++;
  68                         buffer[pos++] = bb_process_escape_sequence(&arg);
  69                         continue;
  70                 }
  71                 if (arg[1] == '-') { /* "0-9..." */
  72                         ac = arg[2];
  73                         if (ac == '\0') { /* "0-": copy verbatim */
  74                                 buffer[pos++] = *arg++; /* copy '0' */
  75                                 continue; /* next iter will copy '-' and stop */
  76                         }
  77                         i = (unsigned char) *arg;
  78                         while (i <= ac) /* ok: i is unsigned _int_ */
  79                                 buffer[pos++] = i++;
  80                         arg += 3; /* skip 0-9 */
  81                         continue;
  82                 }
  83                 if ((ENABLE_FEATURE_TR_CLASSES || ENABLE_FEATURE_TR_EQUIV)
  84                  && *arg == '['
  85                 ) {
  86                         arg++;
  87                         i = (unsigned char) *arg++;
  88                         /* "[xyz...". i=x, arg points to y */
  89                         if (ENABLE_FEATURE_TR_CLASSES && i == ':') { /* [:class:] */
  90 #define CLO ":]\0"
  91                                 static const char classes[] ALIGN1 =
  92                                         "alpha"CLO "alnum"CLO "digit"CLO
  93                                         "lower"CLO "upper"CLO "space"CLO
  94                                         "blank"CLO "punct"CLO "cntrl"CLO
  95                                         "xdigit"CLO;
  96                                 enum {
  97                                         CLASS_invalid = 0, /* we increment the retval */
  98                                         CLASS_alpha = 1,
  99                                         CLASS_alnum = 2,
 100                                         CLASS_digit = 3,
 101                                         CLASS_lower = 4,
 102                                         CLASS_upper = 5,
 103                                         CLASS_space = 6,
 104                                         CLASS_blank = 7,
 105                                         CLASS_punct = 8,
 106                                         CLASS_cntrl = 9,
 107                                         CLASS_xdigit = 10,
 108                                         //CLASS_graph = 11,
 109                                         //CLASS_print = 12,
 110                                 };
 111                                 smalluint j;
 112                                 char *tmp;
 113
 114                                 /* xdigit needs 8, not 7 */
 115                                 i = 7 + (arg[0] == 'x');
 116                                 tmp = xstrndup(arg, i);
 117                                 j = index_in_strings(classes, tmp) + 1;
 118                                 free(tmp);
 119
 120                                 if (j == CLASS_invalid)
 121                                         goto skip_bracket;
 122
 123                                 arg += i;
 124                                 if (j == CLASS_alnum || j == CLASS_digit || j == CLASS_xdigit) {
 125                                         for (i = '0'; i <= '9'; i++)
 126                                                 buffer[pos++] = i;
 127                                 }
 128                                 if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_upper) {
 129                                         for (i = 'A'; i <= 'Z'; i++)
 130                                                 buffer[pos++] = i;
 131                                 }
 132                                 if (j == CLASS_alpha || j == CLASS_alnum || j == CLASS_lower) {
 133                                         for (i = 'a'; i <= 'z'; i++)
 134                                                 buffer[pos++] = i;
 135                                 }
 136                                 if (j == CLASS_space || j == CLASS_blank) {
 137                                         buffer[pos++] = '\t';
 138                                         if (j == CLASS_space) {
 139                                                 buffer[pos++] = '\n';
 140                                                 buffer[pos++] = '\v';
 141                                                 buffer[pos++] = '\f';
 142                                                 buffer[pos++] = '\r';
 143                                         }
 144                                         buffer[pos++] = ' ';
 145                                 }
 146                                 if (j == CLASS_punct || j == CLASS_cntrl) {
 147                                         for (i = '\0'; i < ASCII; i++) {
 148                                                 if ((j == CLASS_punct && isprint(i) && !isalnum(i) && !isspace(i))
 149                                                  || (j == CLASS_cntrl && iscntrl(i))
 150                                                 ) {
 151                                                         buffer[pos++] = i;
 152                                                 }
 153                                         }
 154                                 }
 155                                 if (j == CLASS_xdigit) {
 156                                         for (i = 'A'; i <= 'F'; i++) {
 157                                                 buffer[pos + 6] = i | 0x20;
 158                                                 buffer[pos++] = i;
 159                                         }
 160                                         pos += 6;
 161                                 }
 162                                 continue;
 163                         }
 164                         /* "[xyz...", i=x, arg points to y */
 165                         if (ENABLE_FEATURE_TR_EQUIV && i == '=') { /* [=CHAR=] */
 166                                 buffer[pos++] = *arg; /* copy CHAR */
 167                                 if (!arg[0] || arg[1] != '=' || arg[2] != ']')
 168                                         bb_show_usage();
 169                                 arg += 3;       /* skip CHAR=] */
 170                                 continue;
 171                         }
 172                         /* The rest of "[xyz..." cases is treated as normal
 173                          * string, "[" has no special meaning here:
 174                          * tr "[a-z]" "[A-Z]" can be written as tr "a-z" "A-Z",
 175                          * also try tr "[a-z]" "_A-Z+" and you'll see that
 176                          * [] is not special here.
 177                          */
 178  skip_bracket:
 179                         arg -= 2; /* points to "[" in "[xyz..." */
 180                 }
 181                 buffer[pos++] = *arg++;
 182         }
 183         return pos;
 184 }
 185
 186 /* NB: buffer is guaranteed to be at least TR_BUFSIZE
 187  * (which is >= ASCII) big.
 188  */
 189 static int complement(char *buffer, int buffer_len)
 190 {
 191         int len;
 192         char conv[ASCII];
 193         unsigned char ch;
 194
 195         len = 0;
 196         ch = '\0';
 197         while (1) {
 198                 if (memchr(buffer, ch, buffer_len) == NULL)
 199                         conv[len++] = ch;
 200                 if (++ch == '\0')
 201                         break;
 202         }
 203         memcpy(buffer, conv, len);
 204         return len;
 205 }
 206
 207 int tr_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
 208 int tr_main(int argc UNUSED_PARAM, char **argv)
 209 {
 210         int i;
 211         smalluint flags;
 212         ssize_t read_chars;
 213         size_t in_index, out_index;
 214         unsigned last = UCHAR_MAX + 1; /* not equal to any char */
 215         unsigned char coded, c;
 216         char *str1 = xmalloc(TR_BUFSIZ);
 217         char *str2 = xmalloc(TR_BUFSIZ);
 218         int str2_length;
 219         int str1_length;
 220         char *vector = xzalloc(ASCII * 3);
 221         char *invec  = vector + ASCII;
 222         char *outvec = vector + ASCII * 2;
 223
 224 #define TR_OPT_complement       (1 << 0)
 225 #define TR_OPT_delete           (1 << 1)
 226 #define TR_OPT_squeeze_reps     (1 << 2)
 227
 228         for (i = 0; i < ASCII; i++) {
 229                 vector[i] = i;
 230                 /*invec[i] = outvec[i] = FALSE; - done by xzalloc */
 231         }
 232
 233         opt_complementary = "-1";
 234         flags = getopt32(argv, "+cds"); /* '+': stop at first non-option */
 235         argv += optind;
 236
 237         str1_length = expand(*argv++, &str1);
 238         str2_length = 0;
 239         if (flags & TR_OPT_complement)
 240                 str1_length = complement(str1, str1_length);
 241         if (*argv) {
 242                 if (argv[0][0] == '\0')
 243                         bb_error_msg_and_die("STRING2 cannot be empty");
 244                 str2_length = expand(*argv, &str2);
 245                 map(vector, str1, str1_length,
 246                                 str2, str2_length);
 247         }
 248         for (i = 0; i < str1_length; i++)
 249                 invec[(unsigned char)(str1[i])] = TRUE;
 250         for (i = 0; i < str2_length; i++)
 251                 outvec[(unsigned char)(str2[i])] = TRUE;
 252
 253         goto start_from;
 254
 255         /* In this loop, str1 space is reused as input buffer,
 256          * str2 - as output one. */
 257         for (;;) {
 258                 /* If we're out of input, flush output and read more input. */
 259                 if ((ssize_t)in_index == read_chars) {
 260                         if (out_index) {
 261                                 xwrite(STDOUT_FILENO, str2, out_index);
 262  start_from:
 263                                 out_index = 0;
 264                         }
 265                         read_chars = safe_read(STDIN_FILENO, str1, TR_BUFSIZ);
 266                         if (read_chars <= 0) {
 267                                 if (read_chars < 0)
 268                                         bb_perror_msg_and_die(bb_msg_read_error);
 269                                 break;
 270                         }
 271                         in_index = 0;
 272                 }
 273                 c = str1[in_index++];
 274                 if ((flags & TR_OPT_delete) && invec[c])
 275                         continue;
 276                 coded = vector[c];
 277                 if ((flags & TR_OPT_squeeze_reps) && last == coded
 278                  && (invec[c] || outvec[coded])
 279                 ) {
 280                         continue;
 281                 }
 282                 str2[out_index++] = last = coded;
 283         }
 284
 285         return EXIT_SUCCESS;
 286 }