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