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