1 /* $OpenBSD: col.c,v 1.10 2007/05/01 01:26:19 jdixon Exp $ */ 2 /* $NetBSD: col.c,v 1.7 1995/09/02 05:48:50 jtc Exp $ */ 3 4 /*- 5 * Copyright (c) 1990, 1993, 1994 6 * The Regents of the University of California. All rights reserved. 7 * 8 * This code is derived from software contributed to Berkeley by 9 * Michael Rendell of the Memorial University of Newfoundland. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 2. Redistributions in binary form must reproduce the above copyright 17 * notice, this list of conditions and the following disclaimer in the 18 * documentation and/or other materials provided with the distribution. 19 * 3. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36 #ifndef lint 37 static char copyright[] = 38 "@(#) Copyright (c) 1990, 1993, 1994\n\ 39 The Regents of the University of California. All rights reserved.\n"; 40 #endif /* not lint */ 41 42 #ifndef lint 43 #if 0 44 static char sccsid[] = "@(#)col.c 8.5 (Berkeley) 5/4/95"; 45 #endif 46 static char rcsid[] = "$OpenBSD: col.c,v 1.10 2007/05/01 01:26:19 jdixon Exp $"; 47 #endif /* not lint */ 48 49 #include <ctype.h> 50 #include <err.h> 51 #include <string.h> 52 #include <stdio.h> 53 #include <stdlib.h> 54 #include <unistd.h> 55 #include <limits.h> 56 57 #define BS '\b' /* backspace */ 58 #define TAB '\t' /* tab */ 59 #define SPACE ' ' /* space */ 60 #define NL '\n' /* newline */ 61 #define CR '\r' /* carriage return */ 62 #define ESC '\033' /* escape */ 63 #define SI '\017' /* shift in to normal character set */ 64 #define SO '\016' /* shift out to alternate character set */ 65 #define VT '\013' /* vertical tab (aka reverse line feed) */ 66 #define RLF '\007' /* ESC-07 reverse line feed */ 67 #define RHLF '\010' /* ESC-010 reverse half-line feed */ 68 #define FHLF '\011' /* ESC-011 forward half-line feed */ 69 70 /* build up at least this many lines before flushing them out */ 71 #define BUFFER_MARGIN 32 72 73 typedef char CSET; 74 75 typedef struct char_str { 76 #define CS_NORMAL 1 77 #define CS_ALTERNATE 2 78 short c_column; /* column character is in */ 79 CSET c_set; /* character set (currently only 2) */ 80 char c_char; /* character in question */ 81 } CHAR; 82 83 typedef struct line_str LINE; 84 struct line_str { 85 CHAR *l_line; /* characters on the line */ 86 LINE *l_prev; /* previous line */ 87 LINE *l_next; /* next line */ 88 int l_lsize; /* allocated sizeof l_line */ 89 int l_line_len; /* strlen(l_line) */ 90 int l_needs_sort; /* set if chars went in out of order */ 91 int l_max_col; /* max column in the line */ 92 }; 93 94 LINE *alloc_line(void); 95 void dowarn(int); 96 void flush_line(LINE *); 97 void flush_lines(int); 98 void flush_blanks(void); 99 void free_line(LINE *); 100 void usage(void); 101 void *xmalloc(void *, size_t); 102 103 CSET last_set; /* char_set of last char printed */ 104 LINE *lines; 105 int compress_spaces; /* if doing space -> tab conversion */ 106 int fine; /* if `fine' resolution (half lines) */ 107 int max_bufd_lines; /* max # lines to keep in memory */ 108 int nblank_lines; /* # blanks after last flushed line */ 109 int no_backspaces; /* if not to output any backspaces */ 110 111 #define PUTC(ch) \ 112 if (putchar(ch) == EOF) \ 113 err(1, "stdout"); 114 115 int 116 main(int argc, char *argv[]) 117 { 118 int ch; 119 CHAR *c; 120 CSET cur_set; /* current character set */ 121 LINE *l; /* current line */ 122 int extra_lines; /* # of lines above first line */ 123 int cur_col; /* current column */ 124 int cur_line; /* line number of current position */ 125 int max_line; /* max value of cur_line */ 126 int this_line; /* line l points to */ 127 int nflushd_lines; /* number of lines that were flushed */ 128 int adjust, opt, warned; 129 const char *errstr; 130 131 max_bufd_lines = 128; 132 compress_spaces = 1; /* compress spaces into tabs */ 133 while ((opt = getopt(argc, argv, "bfhl:x")) != -1) 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 max_bufd_lines = strtonum(optarg, 1, INT_MAX, &errstr); 146 if (errstr != NULL) 147 errx(1, "bad -l argument, %s: %s", errstr, 148 optarg); 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 continue; 218 } 219 220 /* Must stuff ch in a line - are we at the right one? */ 221 if (cur_line != this_line - adjust) { 222 LINE *lnew; 223 int nmove; 224 225 adjust = 0; 226 nmove = cur_line - this_line; 227 if (!fine) { 228 /* round up to next line */ 229 if (cur_line & 1) { 230 adjust = 1; 231 nmove++; 232 } 233 } 234 if (nmove < 0) { 235 for (; nmove < 0 && l->l_prev; nmove++) 236 l = l->l_prev; 237 if (nmove) { 238 if (nflushd_lines == 0) { 239 /* 240 * Allow backup past first 241 * line if nothing has been 242 * flushed yet. 243 */ 244 for (; nmove < 0; nmove++) { 245 lnew = alloc_line(); 246 l->l_prev = lnew; 247 lnew->l_next = l; 248 l = lines = lnew; 249 extra_lines++; 250 } 251 } else { 252 if (!warned++) 253 dowarn(cur_line); 254 cur_line -= nmove; 255 } 256 } 257 } else { 258 /* may need to allocate here */ 259 for (; nmove > 0 && l->l_next; nmove--) 260 l = l->l_next; 261 for (; nmove > 0; nmove--) { 262 lnew = alloc_line(); 263 lnew->l_prev = l; 264 l->l_next = lnew; 265 l = lnew; 266 } 267 } 268 this_line = cur_line + adjust; 269 nmove = this_line - nflushd_lines; 270 if (nmove >= max_bufd_lines + BUFFER_MARGIN) { 271 nflushd_lines += nmove - max_bufd_lines; 272 flush_lines(nmove - max_bufd_lines); 273 } 274 } 275 /* grow line's buffer? */ 276 if (l->l_line_len + 1 >= l->l_lsize) { 277 int need; 278 279 need = l->l_lsize ? l->l_lsize * 2 : 90; 280 l->l_line = (CHAR *)xmalloc((void *) l->l_line, 281 (unsigned) need * sizeof(CHAR)); 282 l->l_lsize = need; 283 } 284 c = &l->l_line[l->l_line_len++]; 285 c->c_char = ch; 286 c->c_set = cur_set; 287 c->c_column = cur_col; 288 /* 289 * If things are put in out of order, they will need sorting 290 * when it is flushed. 291 */ 292 if (cur_col < l->l_max_col) 293 l->l_needs_sort = 1; 294 else 295 l->l_max_col = cur_col; 296 cur_col++; 297 } 298 if (max_line == 0) 299 exit(0); /* no lines, so just exit */ 300 301 /* goto the last line that had a character on it */ 302 for (; l->l_next; l = l->l_next) 303 this_line++; 304 flush_lines(this_line - nflushd_lines + extra_lines + 1); 305 306 /* make sure we leave things in a sane state */ 307 if (last_set != CS_NORMAL) 308 PUTC('\017'); 309 310 /* flush out the last few blank lines */ 311 nblank_lines = max_line - this_line; 312 if (max_line & 1) 313 nblank_lines++; 314 else if (!nblank_lines) 315 /* missing a \n on the last line? */ 316 nblank_lines = 2; 317 flush_blanks(); 318 exit(0); 319 } 320 321 void 322 flush_lines(int nflush) 323 { 324 LINE *l; 325 326 while (--nflush >= 0) { 327 l = lines; 328 lines = l->l_next; 329 if (l->l_line) { 330 flush_blanks(); 331 flush_line(l); 332 } 333 nblank_lines++; 334 if (l->l_line) 335 (void)free((void *)l->l_line); 336 free_line(l); 337 } 338 if (lines) 339 lines->l_prev = NULL; 340 } 341 342 /* 343 * Print a number of newline/half newlines. If fine flag is set, nblank_lines 344 * is the number of half line feeds, otherwise it is the number of whole line 345 * feeds. 346 */ 347 void 348 flush_blanks(void) 349 { 350 int half, i, nb; 351 352 half = 0; 353 nb = nblank_lines; 354 if (nb & 1) { 355 if (fine) 356 half = 1; 357 else 358 nb++; 359 } 360 nb /= 2; 361 for (i = nb; --i >= 0;) 362 PUTC('\n'); 363 if (half) { 364 PUTC('\033'); 365 PUTC('9'); 366 if (!nb) 367 PUTC('\r'); 368 } 369 nblank_lines = 0; 370 } 371 372 /* 373 * Write a line to stdout taking care of space to tab conversion (-h flag) 374 * and character set shifts. 375 */ 376 void 377 flush_line(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 int ntabs; 438 439 ntabs = ((last_col % 8) + nspace) / 8; 440 if (ntabs) { 441 nspace -= (ntabs * 8) - (last_col % 8); 442 while (--ntabs >= 0) 443 PUTC('\t'); 444 } 445 } 446 while (--nspace >= 0) 447 PUTC(' '); 448 last_col = this_col; 449 } 450 last_col++; 451 452 for (;;) { 453 if (c->c_set != last_set) { 454 switch (c->c_set) { 455 case CS_NORMAL: 456 PUTC('\017'); 457 break; 458 case CS_ALTERNATE: 459 PUTC('\016'); 460 } 461 last_set = c->c_set; 462 } 463 PUTC(c->c_char); 464 if (++c >= endc) 465 break; 466 PUTC('\b'); 467 } 468 } 469 } 470 471 #define NALLOC 64 472 473 static LINE *line_freelist; 474 475 LINE * 476 alloc_line(void) 477 { 478 LINE *l; 479 int i; 480 481 if (!line_freelist) { 482 l = (LINE *)xmalloc(NULL, sizeof(LINE) * NALLOC); 483 line_freelist = l; 484 for (i = 1; i < NALLOC; i++, l++) 485 l->l_next = l + 1; 486 l->l_next = NULL; 487 } 488 l = line_freelist; 489 line_freelist = l->l_next; 490 491 memset(l, 0, sizeof(LINE)); 492 return (l); 493 } 494 495 void 496 free_line(LINE *l) 497 { 498 499 l->l_next = line_freelist; 500 line_freelist = l; 501 } 502 503 void * 504 xmalloc(void *p, size_t size) 505 { 506 507 if (!(p = (void *)realloc(p, size))) 508 err(1, "realloc failed"); 509 return (p); 510 } 511 512 void 513 usage(void) 514 { 515 (void)fprintf(stderr, "usage: col [-bfhx] [-l num]\n"); 516 exit(1); 517 } 518 519 void 520 dowarn(int line) 521 { 522 523 warnx("warning: can't back up %s", 524 line < 0 ? "past first line" : "-- line already flushed"); 525 } 526