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