usr.bin/col/col.c

   1 /*-
   2  * Copyright (c) 1990, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Michael Rendell of the Memorial University of Newfoundland.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  * @(#) Copyright (c) 1990, 1993, 1994 The Regents of the University of California.  All rights reserved.
  37  * @(#)col.c    8.5 (Berkeley) 5/4/95
  38  * $FreeBSD: src/usr.bin/col/col.c,v 1.6.6.4 2001/08/02 01:27:12 obrien Exp $
  39  * $DragonFly: src/usr.bin/col/col.c,v 1.2 2003/06/17 04:29:25 dillon Exp $
  40  */
  41
  42 #include <ctype.h>
  43 #include <err.h>
  44 #include <string.h>
  45 #include <stdio.h>
  46 #include <stdlib.h>
  47 #include <unistd.h>
  48 #include <locale.h>
  49
  50 #define BS      '\b'            /* backspace */
  51 #define TAB     '\t'            /* tab */
  52 #define SPACE   ' '             /* space */
  53 #define NL      '\n'            /* newline */
  54 #define CR      '\r'            /* carriage return */
  55 #define ESC     '\033'          /* escape */
  56 #define SI      '\017'          /* shift in to normal character set */
  57 #define SO      '\016'          /* shift out to alternate character set */
  58 #define VT      '\013'          /* vertical tab (aka reverse line feed) */
  59 #define RLF     '\007'          /* ESC-07 reverse line feed */
  60 #define RHLF    '\010'          /* ESC-010 reverse half-line feed */
  61 #define FHLF    '\011'          /* ESC-011 forward half-line feed */
  62
  63 /* build up at least this many lines before flushing them out */
  64 #define BUFFER_MARGIN           32
  65
  66 typedef char CSET;
  67
  68 typedef struct char_str {
  69 #define CS_NORMAL       1
  70 #define CS_ALTERNATE    2
  71         short           c_column;       /* column character is in */
  72         CSET            c_set;          /* character set (currently only 2) */
  73         char            c_char;         /* character in question */
  74 } CHAR;
  75
  76 typedef struct line_str LINE;
  77 struct line_str {
  78         CHAR    *l_line;                /* characters on the line */
  79         LINE    *l_prev;                /* previous line */
  80         LINE    *l_next;                /* next line */
  81         int     l_lsize;                /* allocated sizeof l_line */
  82         int     l_line_len;             /* strlen(l_line) */
  83         int     l_needs_sort;           /* set if chars went in out of order */
  84         int     l_max_col;              /* max column in the line */
  85 };
  86
  87 LINE   *alloc_line __P((void));
  88 void    dowarn __P((int));
  89 void    flush_line __P((LINE *));
  90 void    flush_lines __P((int));
  91 void    flush_blanks __P((void));
  92 void    free_line __P((LINE *));
  93 int     main __P((int, char **));
  94 void    usage __P((void));
  95
  96 CSET    last_set;               /* char_set of last char printed */
  97 LINE   *lines;
  98 int     compress_spaces;        /* if doing space -> tab conversion */
  99 int     fine;                   /* if `fine' resolution (half lines) */
 100 int     max_bufd_lines;         /* max # lines to keep in memory */
 101 int     nblank_lines;           /* # blanks after last flushed line */
 102 int     no_backspaces;          /* if not to output any backspaces */
 103 int     pass_unknown_seqs;      /* pass unknown control sequences */
 104
 105 #define PUTC(ch) \
 106         do {                                    \
 107                 if (putchar(ch) == EOF)         \
 108                         errx(1, "write error"); \
 109         } while (0)
 110
 111 int
 112 main(argc, argv)
 113         int argc;
 114         char **argv;
 115 {
 116         int ch;
 117         CHAR *c;
 118         CSET cur_set;                   /* current character set */
 119         LINE *l;                        /* current line */
 120         int extra_lines;                /* # of lines above first line */
 121         int cur_col;                    /* current column */
 122         int cur_line;                   /* line number of current position */
 123         int max_line;                   /* max value of cur_line */
 124         int this_line;                  /* line l points to */
 125         int nflushd_lines;              /* number of lines that were flushed */
 126         int adjust, opt, warned;
 127
 128         (void)setlocale(LC_CTYPE, "");
 129
 130         max_bufd_lines = 128;
 131         compress_spaces = 1;            /* compress spaces into tabs */
 132         while ((opt = getopt(argc, argv, "bfhl:px")) != -1)
 133                 switch (opt) {
 134                 case 'b':               /* do not output backspaces */
 135                         no_backspaces = 1;
 136                         break;
 137                 case 'f':               /* allow half forward line feeds */
 138                         fine = 1;
 139                         break;
 140                 case 'h':               /* compress spaces into tabs */
 141                         compress_spaces = 1;
 142                         break;
 143                 case 'l':               /* buffered line count */
 144                         if ((max_bufd_lines = atoi(optarg)) <= 0)
 145                                 errx(1, "bad -l argument %s", optarg);
 146                         break;
 147                 case 'p':               /* pass unknown control sequences */
 148                         pass_unknown_seqs = 1;
 149                         break;
 150                 case 'x':               /* do not compress spaces into tabs */
 151                         compress_spaces = 0;
 152                         break;
 153                 case '?':
 154                 default:
 155                         usage();
 156                 }
 157
 158         if (optind != argc)
 159                 usage();
 160
 161         /* this value is in half lines */
 162         max_bufd_lines *= 2;
 163
 164         adjust = cur_col = extra_lines = warned = 0;
 165         cur_line = max_line = nflushd_lines = this_line = 0;
 166         cur_set = last_set = CS_NORMAL;
 167         lines = l = alloc_line();
 168
 169         while ((ch = getchar()) != EOF) {
 170                 if (!isgraph(ch)) {
 171                         switch (ch) {
 172                         case BS:                /* can't go back further */
 173                                 if (cur_col == 0)
 174                                         continue;
 175                                 --cur_col;
 176                                 continue;
 177                         case CR:
 178                                 cur_col = 0;
 179                                 continue;
 180                         case ESC:               /* just ignore EOF */
 181                                 switch(getchar()) {
 182                                 case RLF:
 183                                         cur_line -= 2;
 184                                         break;
 185                                 case RHLF:
 186                                         cur_line--;
 187                                         break;
 188                                 case FHLF:
 189                                         cur_line++;
 190                                         if (cur_line > max_line)
 191                                                 max_line = cur_line;
 192                                 }
 193                                 continue;
 194                         case NL:
 195                                 cur_line += 2;
 196                                 if (cur_line > max_line)
 197                                         max_line = cur_line;
 198                                 cur_col = 0;
 199                                 continue;
 200                         case SPACE:
 201                                 ++cur_col;
 202                                 continue;
 203                         case SI:
 204                                 cur_set = CS_NORMAL;
 205                                 continue;
 206                         case SO:
 207                                 cur_set = CS_ALTERNATE;
 208                                 continue;
 209                         case TAB:               /* adjust column */
 210                                 cur_col |= 7;
 211                                 ++cur_col;
 212                                 continue;
 213                         case VT:
 214                                 cur_line -= 2;
 215                                 continue;
 216                         }
 217                         if (!pass_unknown_seqs)
 218                                 continue;
 219                 }
 220
 221                 /* Must stuff ch in a line - are we at the right one? */
 222                 if (cur_line != this_line - adjust) {
 223                         LINE *lnew;
 224                         int nmove;
 225
 226                         adjust = 0;
 227                         nmove = cur_line - this_line;
 228                         if (!fine) {
 229                                 /* round up to next line */
 230                                 if (cur_line & 1) {
 231                                         adjust = 1;
 232                                         nmove++;
 233                                 }
 234                         }
 235                         if (nmove < 0) {
 236                                 for (; nmove < 0 && l->l_prev; nmove++)
 237                                         l = l->l_prev;
 238                                 if (nmove) {
 239                                         if (nflushd_lines == 0) {
 240                                                 /*
 241                                                  * Allow backup past first
 242                                                  * line if nothing has been
 243                                                  * flushed yet.
 244                                                  */
 245                                                 for (; nmove < 0; nmove++) {
 246                                                         lnew = alloc_line();
 247                                                         l->l_prev = lnew;
 248                                                         lnew->l_next = l;
 249                                                         l = lines = lnew;
 250                                                         extra_lines++;
 251                                                 }
 252                                         } else {
 253                                                 if (!warned++)
 254                                                         dowarn(cur_line);
 255                                                 cur_line -= nmove;
 256                                         }
 257                                 }
 258                         } else {
 259                                 /* may need to allocate here */
 260                                 for (; nmove > 0 && l->l_next; nmove--)
 261                                         l = l->l_next;
 262                                 for (; nmove > 0; nmove--) {
 263                                         lnew = alloc_line();
 264                                         lnew->l_prev = l;
 265                                         l->l_next = lnew;
 266                                         l = lnew;
 267                                 }
 268                         }
 269                         this_line = cur_line + adjust;
 270                         nmove = this_line - nflushd_lines;
 271                         if (nmove >= max_bufd_lines + BUFFER_MARGIN) {
 272                                 nflushd_lines += nmove - max_bufd_lines;
 273                                 flush_lines(nmove - max_bufd_lines);
 274                         }
 275                 }
 276                 /* grow line's buffer? */
 277                 if (l->l_line_len + 1 >= l->l_lsize) {
 278                         int need;
 279
 280                         need = l->l_lsize ? l->l_lsize * 2 : 90;
 281                         if ((l->l_line = realloc(l->l_line,
 282                             (unsigned)need * sizeof(CHAR))) == NULL)
 283                                 err(1, (char *)NULL);
 284                         l->l_lsize = need;
 285                 }
 286                 c = &l->l_line[l->l_line_len++];
 287                 c->c_char = ch;
 288                 c->c_set = cur_set;
 289                 c->c_column = cur_col;
 290                 /*
 291                  * If things are put in out of order, they will need sorting
 292                  * when it is flushed.
 293                  */
 294                 if (cur_col < l->l_max_col)
 295                         l->l_needs_sort = 1;
 296                 else
 297                         l->l_max_col = cur_col;
 298                 cur_col++;
 299         }
 300         if (max_line == 0)
 301                 exit(0);        /* no lines, so just exit */
 302
 303         /* goto the last line that had a character on it */
 304         for (; l->l_next; l = l->l_next)
 305                 this_line++;
 306         flush_lines(this_line - nflushd_lines + extra_lines + 1);
 307
 308         /* make sure we leave things in a sane state */
 309         if (last_set != CS_NORMAL)
 310                 PUTC('\017');
 311
 312         /* flush out the last few blank lines */
 313         nblank_lines = max_line - this_line;
 314         if (max_line & 1)
 315                 nblank_lines++;
 316         else if (!nblank_lines)
 317                 /* missing a \n on the last line? */
 318                 nblank_lines = 2;
 319         flush_blanks();
 320         exit(0);
 321 }
 322
 323 void
 324 flush_lines(nflush)
 325         int nflush;
 326 {
 327         LINE *l;
 328
 329         while (--nflush >= 0) {
 330                 l = lines;
 331                 lines = l->l_next;
 332                 if (l->l_line) {
 333                         flush_blanks();
 334                         flush_line(l);
 335                 }
 336                 nblank_lines++;
 337                 if (l->l_line)
 338                         (void)free(l->l_line);
 339                 free_line(l);
 340         }
 341         if (lines)
 342                 lines->l_prev = NULL;
 343 }
 344
 345 /*
 346  * Print a number of newline/half newlines.  If fine flag is set, nblank_lines
 347  * is the number of half line feeds, otherwise it is the number of whole line
 348  * feeds.
 349  */
 350 void
 351 flush_blanks()
 352 {
 353         int half, i, nb;
 354
 355         half = 0;
 356         nb = nblank_lines;
 357         if (nb & 1) {
 358                 if (fine)
 359                         half = 1;
 360                 else
 361                         nb++;
 362         }
 363         nb /= 2;
 364         for (i = nb; --i >= 0;)
 365                 PUTC('\n');
 366         if (half) {
 367                 PUTC('\033');
 368                 PUTC('9');
 369                 if (!nb)
 370                         PUTC('\r');
 371         }
 372         nblank_lines = 0;
 373 }
 374
 375 /*
 376  * Write a line to stdout taking care of space to tab conversion (-h flag)
 377  * and character set shifts.
 378  */
 379 void
 380 flush_line(l)
 381         LINE *l;
 382 {
 383         CHAR *c, *endc;
 384         int nchars, last_col, this_col;
 385
 386         last_col = 0;
 387         nchars = l->l_line_len;
 388
 389         if (l->l_needs_sort) {
 390                 static CHAR *sorted;
 391                 static int count_size, *count, i, save, sorted_size, tot;
 392
 393                 /*
 394                  * Do an O(n) sort on l->l_line by column being careful to
 395                  * preserve the order of characters in the same column.
 396                  */
 397                 if (l->l_lsize > sorted_size) {
 398                         sorted_size = l->l_lsize;
 399                         if ((sorted = realloc(sorted,
 400                             (unsigned)sizeof(CHAR) * sorted_size)) == NULL)
 401                                 err(1, (char *)NULL);
 402                 }
 403                 if (l->l_max_col >= count_size) {
 404                         count_size = l->l_max_col + 1;
 405                         if ((count = realloc(count,
 406                             (unsigned)sizeof(int) * count_size)) == NULL)
 407                                 err(1, (char *)NULL);
 408                 }
 409                 memset(count, 0, sizeof(int) * l->l_max_col + 1);
 410                 for (i = nchars, c = l->l_line; --i >= 0; c++)
 411                         count[c->c_column]++;
 412
 413                 /*
 414                  * calculate running total (shifted down by 1) to use as
 415                  * indices into new line.
 416                  */
 417                 for (tot = 0, i = 0; i <= l->l_max_col; i++) {
 418                         save = count[i];
 419                         count[i] = tot;
 420                         tot += save;
 421                 }
 422
 423                 for (i = nchars, c = l->l_line; --i >= 0; c++)
 424                         sorted[count[c->c_column]++] = *c;
 425                 c = sorted;
 426         } else
 427                 c = l->l_line;
 428         while (nchars > 0) {
 429                 this_col = c->c_column;
 430                 endc = c;
 431                 do {
 432                         ++endc;
 433                 } while (--nchars > 0 && this_col == endc->c_column);
 434
 435                 /* if -b only print last character */
 436                 if (no_backspaces)
 437                         c = endc - 1;
 438
 439                 if (this_col > last_col) {
 440                         int nspace = this_col - last_col;
 441
 442                         if (compress_spaces && nspace > 1) {
 443                                 while (1) {
 444                                         int tab_col, tab_size;;
 445
 446                                         tab_col = (last_col + 8) & ~7;
 447                                         if (tab_col > this_col)
 448                                                 break;
 449                                         tab_size = tab_col - last_col;
 450                                         if (tab_size == 1)
 451                                                 PUTC(' ');
 452                                         else
 453                                                 PUTC('\t');
 454                                         nspace -= tab_size;
 455                                         last_col = tab_col;
 456                                 }
 457                         }
 458                         while (--nspace >= 0)
 459                                 PUTC(' ');
 460                         last_col = this_col;
 461                 }
 462                 last_col++;
 463
 464                 for (;;) {
 465                         if (c->c_set != last_set) {
 466                                 switch (c->c_set) {
 467                                 case CS_NORMAL:
 468                                         PUTC('\017');
 469                                         break;
 470                                 case CS_ALTERNATE:
 471                                         PUTC('\016');
 472                                 }
 473                                 last_set = c->c_set;
 474                         }
 475                         PUTC(c->c_char);
 476                         if (++c >= endc)
 477                                 break;
 478                         PUTC('\b');
 479                 }
 480         }
 481 }
 482
 483 #define NALLOC 64
 484
 485 static LINE *line_freelist;
 486
 487 LINE *
 488 alloc_line()
 489 {
 490         LINE *l;
 491         int i;
 492
 493         if (!line_freelist) {
 494                 if ((l = realloc(NULL, sizeof(LINE) * NALLOC)) == NULL)
 495                         err(1, (char *)NULL);
 496                 line_freelist = l;
 497                 for (i = 1; i < NALLOC; i++, l++)
 498                         l->l_next = l + 1;
 499                 l->l_next = NULL;
 500         }
 501         l = line_freelist;
 502         line_freelist = l->l_next;
 503
 504         memset(l, 0, sizeof(LINE));
 505         return (l);
 506 }
 507
 508 void
 509 free_line(l)
 510         LINE *l;
 511 {
 512
 513         l->l_next = line_freelist;
 514         line_freelist = l;
 515 }
 516
 517 void
 518 usage()
 519 {
 520
 521         (void)fprintf(stderr, "usage: col [-bfhpx] [-l nline]\n");
 522         exit(1);
 523 }
 524
 525 void
 526 dowarn(line)
 527         int line;
 528 {
 529
 530         warnx("warning: can't back up %s",
 531                 line < 0 ? "past first line" : "-- line already flushed");
 532 }