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