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