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