1 /* $OpenBSD: display.c,v 1.6 2001/05/24 03:05:22 mickey Exp $ */ 2 3 /* 4 * The functions in this file handle redisplay. The 5 * redisplay system knows almost nothing about the editing 6 * process; the editing functions do, however, set some 7 * hints to eliminate a lot of the grinding. There is more 8 * that can be done; the "vtputc" interface is a real 9 * pig. Two conditional compilation flags; the GOSLING 10 * flag enables dynamic programming redisplay, using the 11 * algorithm published by Jim Gosling in SIGOA. The MEMMAP 12 * changes things around for memory mapped video. With 13 * both off, the terminal is a VT52. 14 */ 15 #include "def.h" 16 #include "kbd.h" 17 18 /* 19 * You can change these back to the types 20 * implied by the name if you get tight for space. If you 21 * make both of them "int" you get better code on the VAX. 22 * They do nothing if this is not Gosling redisplay, except 23 * for change the size of a structure that isn't used. 24 * A bit of a cheat. 25 */ 26 /* These defines really belong in sysdef.h */ 27 #ifndef XCHAR 28 #define XCHAR int 29 #define XSHORT int 30 #endif 31 32 #ifdef STANDOUT_GLITCH 33 #include <term.h> 34 #endif 35 36 /* 37 * A video structure always holds 38 * an array of characters whose length is equal to 39 * the longest line possible. Only some of this is 40 * used if "ncol" isn't the same as "NCOL". 41 */ 42 typedef struct { 43 short v_hash; /* Hash code, for compares. */ 44 short v_flag; /* Flag word. */ 45 short v_color; /* Color of the line. */ 46 XSHORT v_cost; /* Cost of display. */ 47 char v_text[NCOL]; /* The actual characters. */ 48 } VIDEO; 49 50 #define VFCHG 0x0001 /* Changed. */ 51 #define VFHBAD 0x0002 /* Hash and cost are bad. */ 52 #define VFEXT 0x0004 /* extended line (beond ncol) */ 53 54 /* 55 * SCORE structures hold the optimal 56 * trace trajectory, and the cost of redisplay, when 57 * the dynamic programming redisplay code is used. 58 * If no fancy redisplay, this isn't used. The trace index 59 * fields can be "char", and the score a "short", but 60 * this makes the code worse on the VAX. 61 */ 62 typedef struct { 63 XCHAR s_itrace; /* "i" index for track back. */ 64 XCHAR s_jtrace; /* "j" index for trace back. */ 65 XSHORT s_cost; /* Display cost. */ 66 } SCORE; 67 68 69 void vtmove __P((int, int)); 70 void vtputc __P((int)); 71 void vtpute __P((int)); 72 int vtputs __P((char *)); 73 void vteeol __P((void)); 74 void updext __P((int, int)); 75 void modeline __P((MGWIN *)); 76 void setscores __P((int, int)); 77 void traceback __P((int, int, int, int)); 78 void ucopy __P((VIDEO *, VIDEO *)); 79 void uline __P((int, VIDEO *, VIDEO *)); 80 void hash __P((VIDEO *)); 81 82 83 int sgarbf = TRUE; /* TRUE if screen is garbage. */ 84 int vtrow = 0; /* Virtual cursor row. */ 85 int vtcol = 0; /* Virtual cursor column. */ 86 int tthue = CNONE; /* Current color. */ 87 int ttrow = HUGE; /* Physical cursor row. */ 88 int ttcol = HUGE; /* Physical cursor column. */ 89 int tttop = HUGE; /* Top of scroll region. */ 90 int ttbot = HUGE; /* Bottom of scroll region. */ 91 int lbound = 0; /* leftmost bound of the current line */ 92 /* being displayed */ 93 94 VIDEO *vscreen[NROW - 1]; /* Edge vector, virtual. */ 95 VIDEO *pscreen[NROW - 1]; /* Edge vector, physical. */ 96 VIDEO video[2 * (NROW - 1)]; /* Actual screen data. */ 97 VIDEO blanks; /* Blank line image. */ 98 99 #ifdef GOSLING 100 /* 101 * This matrix is written as an array because 102 * we do funny things in the "setscores" routine, which 103 * is very compute intensive, to make the subscripts go away. 104 * It would be "SCORE score[NROW][NROW]" in old speak. 105 * Look at "setscores" to understand what is up. 106 */ 107 SCORE score[NROW * NROW]; 108 #endif 109 110 /* 111 * Initialize the data structures used 112 * by the display code. The edge vectors used 113 * to access the screens are set up. The operating 114 * system's terminal I/O channel is set up. Fill the 115 * "blanks" array with ASCII blanks. The rest is done 116 * at compile time. The original window is marked 117 * as needing full update, and the physical screen 118 * is marked as garbage, so all the right stuff happens 119 * on the first call to redisplay. 120 */ 121 void 122 vtinit() 123 { 124 VIDEO *vp; 125 int i; 126 127 ttopen(); 128 ttinit(); 129 vp = &video[0]; 130 for (i = 0; i < NROW - 1; ++i) { 131 vscreen[i] = vp; 132 ++vp; 133 pscreen[i] = vp; 134 ++vp; 135 } 136 blanks.v_color = CTEXT; 137 for (i = 0; i < NCOL; ++i) 138 blanks.v_text[i] = ' '; 139 } 140 141 /* 142 * Tidy up the virtual display system 143 * in anticipation of a return back to the host 144 * operating system. Right now all we do is position 145 * the cursor to the last line, erase the line, and 146 * close the terminal channel. 147 */ 148 void 149 vttidy() 150 { 151 152 ttcolor(CTEXT); 153 ttnowindow(); /* No scroll window. */ 154 ttmove(nrow - 1, 0); /* Echo line. */ 155 tteeol(); 156 tttidy(); 157 ttflush(); 158 ttclose(); 159 } 160 161 /* 162 * Move the virtual cursor to an origin 163 * 0 spot on the virtual display screen. I could 164 * store the column as a character pointer to the spot 165 * on the line, which would make "vtputc" a little bit 166 * more efficient. No checking for errors. 167 */ 168 void 169 vtmove(row, col) 170 int row, col; 171 { 172 173 vtrow = row; 174 vtcol = col; 175 } 176 177 /* 178 * Write a character to the virtual display, 179 * dealing with long lines and the display of unprintable 180 * things like control characters. Also expand tabs every 8 181 * columns. This code only puts printing characters into 182 * the virtual display image. Special care must be taken when 183 * expanding tabs. On a screen whose width is not a multiple 184 * of 8, it is possible for the virtual cursor to hit the 185 * right margin before the next tab stop is reached. This 186 * makes the tab code loop if you are not careful. 187 * Three guesses how we found this. 188 */ 189 void 190 vtputc(c) 191 int c; 192 { 193 VIDEO *vp; 194 195 vp = vscreen[vtrow]; 196 if (vtcol >= ncol) 197 vp->v_text[ncol - 1] = '$'; 198 else if (c == '\t' 199 #ifdef NOTAB 200 && !(curbp->b_flag & BFNOTAB) 201 #endif 202 ) { 203 do { 204 vtputc(' '); 205 } while (vtcol < ncol && (vtcol & 0x07) != 0); 206 } else if (ISCTRL(c)) { 207 vtputc('^'); 208 vtputc(CCHR(c)); 209 } else 210 vp->v_text[vtcol++] = c; 211 } 212 213 /* 214 * Put a character to the virtual screen in an extended line. If we are not 215 * yet on left edge, don't print it yet. Check for overflow on the right 216 * margin. 217 */ 218 void 219 vtpute(c) 220 int c; 221 { 222 VIDEO *vp; 223 224 vp = vscreen[vtrow]; 225 226 if (vtcol >= ncol) 227 vp->v_text[ncol - 1] = '$'; 228 else if (c == '\t' 229 #ifdef NOTAB 230 && !(curbp->b_flag & BFNOTAB) 231 #endif 232 ) { 233 do { 234 vtpute(' '); 235 } 236 while (((vtcol + lbound) & 0x07) != 0 && vtcol < ncol); 237 } else if (ISCTRL(c) != FALSE) { 238 vtpute('^'); 239 vtpute(CCHR(c)); 240 } else { 241 if (vtcol >= 0) 242 vp->v_text[vtcol] = c; 243 ++vtcol; 244 } 245 } 246 247 /* 248 * Erase from the end of the software cursor to the end of the line on which 249 * the software cursor is located. The display routines will decide if a 250 * hardware erase to end of line command should be used to display this. 251 */ 252 void 253 vteeol() 254 { 255 VIDEO *vp; 256 257 vp = vscreen[vtrow]; 258 while (vtcol < ncol) 259 vp->v_text[vtcol++] = ' '; 260 } 261 262 /* 263 * Make sure that the display is 264 * right. This is a three part process. First, 265 * scan through all of the windows looking for dirty 266 * ones. Check the framing, and refresh the screen. 267 * Second, make sure that "currow" and "curcol" are 268 * correct for the current window. Third, make the 269 * virtual and physical screens the same. 270 */ 271 void 272 update() 273 { 274 LINE *lp; 275 MGWIN *wp; 276 VIDEO *vp1; 277 VIDEO *vp2; 278 int i, j; 279 int c; 280 int hflag; 281 int currow; 282 int curcol; 283 int offs; 284 int size; 285 286 if (typeahead()) 287 return; 288 if (sgarbf) { /* must update everything */ 289 wp = wheadp; 290 while (wp != NULL) { 291 wp->w_flag |= WFMODE | WFHARD; 292 wp = wp->w_wndp; 293 } 294 } 295 hflag = FALSE; /* Not hard. */ 296 wp = wheadp; 297 while (wp != NULL) { 298 if (wp->w_flag != 0) { /* Need update. */ 299 if ((wp->w_flag & WFFORCE) == 0) { 300 lp = wp->w_linep; 301 for (i = 0; i < wp->w_ntrows; ++i) { 302 if (lp == wp->w_dotp) 303 goto out; 304 if (lp == wp->w_bufp->b_linep) 305 break; 306 lp = lforw(lp); 307 } 308 } 309 i = wp->w_force; /* Reframe this one. */ 310 if (i > 0) { 311 --i; 312 if (i >= wp->w_ntrows) 313 i = wp->w_ntrows - 1; 314 } else if (i < 0) { 315 i += wp->w_ntrows; 316 if (i < 0) 317 i = 0; 318 } else 319 i = wp->w_ntrows / 2; 320 lp = wp->w_dotp; 321 while (i != 0 && lback(lp) != wp->w_bufp->b_linep) { 322 --i; 323 lp = lback(lp); 324 } 325 wp->w_linep = lp; 326 wp->w_flag |= WFHARD; /* Force full. */ 327 out: 328 lp = wp->w_linep; /* Try reduced update. */ 329 i = wp->w_toprow; 330 if ((wp->w_flag & ~WFMODE) == WFEDIT) { 331 while (lp != wp->w_dotp) { 332 ++i; 333 lp = lforw(lp); 334 } 335 vscreen[i]->v_color = CTEXT; 336 vscreen[i]->v_flag |= (VFCHG | VFHBAD); 337 vtmove(i, 0); 338 for (j = 0; j < llength(lp); ++j) 339 vtputc(lgetc(lp, j)); 340 vteeol(); 341 } else if ((wp->w_flag & (WFEDIT | WFHARD)) != 0) { 342 hflag = TRUE; 343 while (i < wp->w_toprow + wp->w_ntrows) { 344 vscreen[i]->v_color = CTEXT; 345 vscreen[i]->v_flag |= (VFCHG | VFHBAD); 346 vtmove(i, 0); 347 if (lp != wp->w_bufp->b_linep) { 348 for (j = 0; j < llength(lp); ++j) 349 vtputc(lgetc(lp, j)); 350 lp = lforw(lp); 351 } 352 vteeol(); 353 ++i; 354 } 355 } 356 if ((wp->w_flag & WFMODE) != 0) 357 modeline(wp); 358 wp->w_flag = 0; 359 wp->w_force = 0; 360 } 361 wp = wp->w_wndp; 362 } 363 lp = curwp->w_linep; /* Cursor location. */ 364 currow = curwp->w_toprow; 365 while (lp != curwp->w_dotp) { 366 ++currow; 367 lp = lforw(lp); 368 } 369 curcol = 0; 370 i = 0; 371 while (i < curwp->w_doto) { 372 c = lgetc(lp, i++); 373 if (c == '\t' 374 #ifdef NOTAB 375 && !(curbp->b_flag & BFNOTAB) 376 #endif 377 ) 378 curcol |= 0x07; 379 else if (ISCTRL(c) != FALSE) 380 ++curcol; 381 ++curcol; 382 } 383 if (curcol >= ncol - 1) { /* extended line. */ 384 /* flag we are extended and changed */ 385 vscreen[currow]->v_flag |= VFEXT | VFCHG; 386 updext(currow, curcol); /* and output extended line */ 387 } else 388 lbound = 0; /* not extended line */ 389 390 /* 391 * make sure no lines need to be de-extended because the cursor is no 392 * longer on them 393 */ 394 wp = wheadp; 395 while (wp != NULL) { 396 lp = wp->w_linep; 397 i = wp->w_toprow; 398 while (i < wp->w_toprow + wp->w_ntrows) { 399 if (vscreen[i]->v_flag & VFEXT) { 400 /* always flag extended lines as changed */ 401 vscreen[i]->v_flag |= VFCHG; 402 if ((wp != curwp) || (lp != wp->w_dotp) || 403 (curcol < ncol - 1)) { 404 vtmove(i, 0); 405 for (j = 0; j < llength(lp); ++j) 406 vtputc(lgetc(lp, j)); 407 vteeol(); 408 /* this line no longer is extended */ 409 vscreen[i]->v_flag &= ~VFEXT; 410 } 411 } 412 lp = lforw(lp); 413 ++i; 414 } 415 /* if garbaged then fix up mode lines */ 416 if (sgarbf != FALSE) 417 vscreen[i]->v_flag |= VFCHG; 418 /* and onward to the next window */ 419 wp = wp->w_wndp; 420 } 421 422 if (sgarbf != FALSE) { /* Screen is garbage. */ 423 sgarbf = FALSE; /* Erase-page clears */ 424 epresf = FALSE; /* the message area. */ 425 tttop = HUGE; /* Forget where you set */ 426 ttbot = HUGE; /* scroll region. */ 427 tthue = CNONE; /* Color unknown. */ 428 ttmove(0, 0); 429 tteeop(); 430 for (i = 0; i < nrow - 1; ++i) { 431 uline(i, vscreen[i], &blanks); 432 ucopy(vscreen[i], pscreen[i]); 433 } 434 ttmove(currow, curcol - lbound); 435 ttflush(); 436 return; 437 } 438 #ifdef GOSLING 439 if (hflag != FALSE) { /* Hard update? */ 440 for (i = 0; i < nrow - 1; ++i) {/* Compute hash data. */ 441 hash(vscreen[i]); 442 hash(pscreen[i]); 443 } 444 offs = 0; /* Get top match. */ 445 while (offs != nrow - 1) { 446 vp1 = vscreen[offs]; 447 vp2 = pscreen[offs]; 448 if (vp1->v_color != vp2->v_color 449 || vp1->v_hash != vp2->v_hash) 450 break; 451 uline(offs, vp1, vp2); 452 ucopy(vp1, vp2); 453 ++offs; 454 } 455 if (offs == nrow - 1) { /* Might get it all. */ 456 ttmove(currow, curcol - lbound); 457 ttflush(); 458 return; 459 } 460 size = nrow - 1; /* Get bottom match. */ 461 while (size != offs) { 462 vp1 = vscreen[size - 1]; 463 vp2 = pscreen[size - 1]; 464 if (vp1->v_color != vp2->v_color 465 || vp1->v_hash != vp2->v_hash) 466 break; 467 uline(size - 1, vp1, vp2); 468 ucopy(vp1, vp2); 469 --size; 470 } 471 if ((size -= offs) == 0) /* Get screen size. */ 472 panic("Illegal screen size in update"); 473 setscores(offs, size); /* Do hard update. */ 474 traceback(offs, size, size, size); 475 for (i = 0; i < size; ++i) 476 ucopy(vscreen[offs + i], pscreen[offs + i]); 477 ttmove(currow, curcol - lbound); 478 ttflush(); 479 return; 480 } 481 #endif 482 for (i = 0; i < nrow - 1; ++i) { /* Easy update. */ 483 vp1 = vscreen[i]; 484 vp2 = pscreen[i]; 485 if ((vp1->v_flag & VFCHG) != 0) { 486 uline(i, vp1, vp2); 487 ucopy(vp1, vp2); 488 } 489 } 490 ttmove(currow, curcol - lbound); 491 ttflush(); 492 } 493 494 /* 495 * Update a saved copy of a line, 496 * kept in a VIDEO structure. The "vvp" is 497 * the one in the "vscreen". The "pvp" is the one 498 * in the "pscreen". This is called to make the 499 * virtual and physical screens the same when 500 * display has done an update. 501 */ 502 void 503 ucopy(vvp, pvp) 504 VIDEO *vvp; 505 VIDEO *pvp; 506 { 507 508 vvp->v_flag &= ~VFCHG; /* Changes done. */ 509 pvp->v_flag = vvp->v_flag; /* Update model. */ 510 pvp->v_hash = vvp->v_hash; 511 pvp->v_cost = vvp->v_cost; 512 pvp->v_color = vvp->v_color; 513 bcopy(vvp->v_text, pvp->v_text, ncol); 514 } 515 516 /* 517 * updext: update the extended line which the cursor is currently on at a 518 * column greater than the terminal width. The line will be scrolled right or 519 * left to let the user see where the cursor is 520 */ 521 void 522 updext(currow, curcol) 523 int currow, curcol; 524 { 525 LINE *lp; /* pointer to current line */ 526 int j; /* index into line */ 527 528 /* 529 * calculate what column the left bound should be 530 * (force cursor into middle half of screen) 531 */ 532 lbound = curcol - (curcol % (ncol >> 1)) - (ncol >> 2); 533 /* 534 * scan through the line outputing characters to the virtual screen 535 * once we reach the left edge 536 */ 537 vtmove(currow, -lbound); /* start scanning offscreen */ 538 lp = curwp->w_dotp; /* line to output */ 539 for (j = 0; j < llength(lp); ++j) /* until the end-of-line */ 540 vtpute(lgetc(lp, j)); 541 vteeol(); /* truncate the virtual line */ 542 vscreen[currow]->v_text[0] = '$'; /* and put a '$' in column 1 */ 543 } 544 545 /* 546 * Update a single line. This routine only 547 * uses basic functionality (no insert and delete character, 548 * but erase to end of line). The "vvp" points at the VIDEO 549 * structure for the line on the virtual screen, and the "pvp" 550 * is the same for the physical screen. Avoid erase to end of 551 * line when updating CMODE color lines, because of the way that 552 * reverse video works on most terminals. 553 */ 554 void 555 uline(row, vvp, pvp) 556 int row; 557 VIDEO *vvp; 558 VIDEO *pvp; 559 { 560 #ifdef MEMMAP 561 putline(row + 1, 1, &vvp->v_text[0]); 562 #else 563 char *cp1; 564 char *cp2; 565 char *cp3; 566 char *cp4; 567 char *cp5; 568 int nbflag; 569 570 if (vvp->v_color != pvp->v_color) { /* Wrong color, do a */ 571 ttmove(row, 0); /* full redraw. */ 572 #ifdef STANDOUT_GLITCH 573 if (pvp->v_color != CTEXT && magic_cookie_glitch >= 0) 574 tteeol(); 575 #endif 576 ttcolor(vvp->v_color); 577 #ifdef STANDOUT_GLITCH 578 cp1 = &vvp->v_text[magic_cookie_glitch > 0 ? magic_cookie_glitch : 0]; 579 /* 580 * the odd code for magic_cookie_glitch==0 is to avoid 581 * putting the invisable glitch character on the next line. 582 * (Hazeltine executive 80 model 30) 583 */ 584 cp2 = &vvp->v_text[ncol - (magic_cookie_glitch >= 0 ? (magic_cookie_glitch != 0 ? magic_cookie_glitch : 1) : 0)]; 585 #else 586 cp1 = &vvp->v_text[0]; 587 cp2 = &vvp->v_text[ncol]; 588 #endif 589 while (cp1 != cp2) { 590 ttputc(*cp1++); 591 ++ttcol; 592 } 593 #ifndef MOVE_STANDOUT 594 ttcolor(CTEXT); 595 #endif 596 return; 597 } 598 cp1 = &vvp->v_text[0]; /* Compute left match. */ 599 cp2 = &pvp->v_text[0]; 600 while (cp1 != &vvp->v_text[ncol] && cp1[0] == cp2[0]) { 601 ++cp1; 602 ++cp2; 603 } 604 if (cp1 == &vvp->v_text[ncol]) /* All equal. */ 605 return; 606 nbflag = FALSE; 607 cp3 = &vvp->v_text[ncol]; /* Compute right match. */ 608 cp4 = &pvp->v_text[ncol]; 609 while (cp3[-1] == cp4[-1]) { 610 --cp3; 611 --cp4; 612 if (cp3[0] != ' ') /* Note non-blanks in */ 613 nbflag = TRUE; /* the right match. */ 614 } 615 cp5 = cp3; /* Is erase good? */ 616 if (nbflag == FALSE && vvp->v_color == CTEXT) { 617 while (cp5 != cp1 && cp5[-1] == ' ') 618 --cp5; 619 /* Alcyon hack */ 620 if ((int) (cp3 - cp5) <= tceeol) 621 cp5 = cp3; 622 } 623 /* Alcyon hack */ 624 ttmove(row, (int) (cp1 - &vvp->v_text[0])); 625 #ifdef STANDOUT_GLITCH 626 if (vvp->v_color != CTEXT && magic_cookie_glitch > 0) { 627 if (cp1 < &vvp->v_text[magic_cookie_glitch]) 628 cp1 = &vvp->v_text[magic_cookie_glitch]; 629 if (cp5 > &vvp->v_text[ncol - magic_cookie_glitch]) 630 cp5 = &vvp->v_text[ncol - magic_cookie_glitch]; 631 } else if (magic_cookie_glitch < 0) 632 #endif 633 ttcolor(vvp->v_color); 634 while (cp1 != cp5) { 635 ttputc(*cp1++); 636 ++ttcol; 637 } 638 if (cp5 != cp3) /* Do erase. */ 639 tteeol(); 640 #endif 641 } 642 643 /* 644 * Redisplay the mode line for the window pointed to by the "wp". 645 * This is the only routine that has any idea of how the modeline is 646 * formatted. You can change the modeline format by hacking at this 647 * routine. Called by "update" any time there is a dirty window. Note 648 * that if STANDOUT_GLITCH is defined, first and last magic_cookie_glitch 649 * characters may never be seen. 650 */ 651 void 652 modeline(wp) 653 MGWIN *wp; 654 { 655 int n; 656 BUFFER *bp; 657 int mode; 658 659 n = wp->w_toprow + wp->w_ntrows; /* Location. */ 660 vscreen[n]->v_color = CMODE; /* Mode line color. */ 661 vscreen[n]->v_flag |= (VFCHG | VFHBAD); /* Recompute, display. */ 662 vtmove(n, 0); /* Seek to right line. */ 663 bp = wp->w_bufp; 664 vtputc('-'); 665 vtputc('-'); 666 if ((bp->b_flag & BFCHG) != 0) { /* "*" if changed. */ 667 vtputc('*'); 668 vtputc('*'); 669 } else { 670 vtputc('-'); 671 vtputc('-'); 672 } 673 vtputc('-'); 674 n = 5; 675 n += vtputs("Mg: "); 676 if (bp->b_bname[0] != '\0') 677 n += vtputs(&(bp->b_bname[0])); 678 while (n < 42) { /* Pad out with blanks */ 679 vtputc(' '); 680 ++n; 681 } 682 vtputc('('); 683 ++n; 684 for (mode = 0;;) { 685 n += vtputs(bp->b_modes[mode]->p_name); 686 if (++mode > bp->b_nmodes) 687 break; 688 vtputc('-'); 689 ++n; 690 } 691 vtputc(')'); 692 ++n; 693 while (n < ncol) { /* Pad out. */ 694 vtputc('-'); 695 ++n; 696 } 697 } 698 /* 699 * output a string to the mode line, report how long it was. 700 */ 701 int 702 vtputs(s) 703 char *s; 704 { 705 int n = 0; 706 707 while (*s != '\0') { 708 vtputc(*s++); 709 ++n; 710 } 711 return n; 712 } 713 714 #ifdef GOSLING 715 /* 716 * Compute the hash code for the line pointed to by the "vp". 717 * Recompute it if necessary. Also set the approximate redisplay 718 * cost. The validity of the hash code is marked by a flag bit. 719 * The cost understand the advantages of erase to end of line. 720 * Tuned for the VAX by Bob McNamara; better than it used to be on 721 * just about any machine. 722 */ 723 void 724 hash(vp) 725 VIDEO *vp; 726 { 727 int i; 728 int n; 729 char *s; 730 731 if ((vp->v_flag & VFHBAD) != 0) { /* Hash bad. */ 732 s = &vp->v_text[ncol - 1]; 733 for (i = ncol; i != 0; --i, --s) 734 if (*s != ' ') 735 break; 736 n = ncol - i; /* Erase cheaper? */ 737 if (n > tceeol) 738 n = tceeol; 739 vp->v_cost = i + n; /* Bytes + blanks. */ 740 for (n = 0; i != 0; --i, --s) 741 n = (n << 5) + n + *s; 742 vp->v_hash = n; /* Hash code. */ 743 vp->v_flag &= ~VFHBAD; /* Flag as all done. */ 744 } 745 } 746 747 /* 748 * Compute the Insert-Delete 749 * cost matrix. The dynamic programming algorithm 750 * described by James Gosling is used. This code assumes 751 * that the line above the echo line is the last line involved 752 * in the scroll region. This is easy to arrange on the VT100 753 * because of the scrolling region. The "offs" is the origin 0 754 * offset of the first row in the virtual/physical screen that 755 * is being updated; the "size" is the length of the chunk of 756 * screen being updated. For a full screen update, use offs=0 757 * and size=nrow-1. 758 * 759 * Older versions of this code implemented the score matrix by 760 * a two dimensional array of SCORE nodes. This put all kinds of 761 * multiply instructions in the code! This version is written to 762 * use a linear array and pointers, and contains no multiplication 763 * at all. The code has been carefully looked at on the VAX, with 764 * only marginal checking on other machines for efficiency. In 765 * fact, this has been tuned twice! Bob McNamara tuned it even 766 * more for the VAX, which is a big issue for him because of 767 * the 66 line X displays. 768 * 769 * On some machines, replacing the "for (i=1; i<=size; ++i)" with 770 * i = 1; do { } while (++i <=size)" will make the code quite a 771 * bit better; but it looks ugly. 772 */ 773 void 774 setscores(offs, size) 775 int offs; 776 int size; 777 { 778 SCORE *sp; 779 SCORE *sp1; 780 int tempcost; 781 int bestcost; 782 int j, i; 783 VIDEO **vp, **pp; 784 VIDEO **vbase, **pbase; 785 786 vbase = &vscreen[offs - 1]; /* By hand CSE's. */ 787 pbase = &pscreen[offs - 1]; 788 score[0].s_itrace = 0; /* [0, 0] */ 789 score[0].s_jtrace = 0; 790 score[0].s_cost = 0; 791 sp = &score[1]; /* Row 0, inserts. */ 792 tempcost = 0; 793 vp = &vbase[1]; 794 for (j = 1; j <= size; ++j) { 795 sp->s_itrace = 0; 796 sp->s_jtrace = j - 1; 797 tempcost += tcinsl; 798 tempcost += (*vp)->v_cost; 799 sp->s_cost = tempcost; 800 ++vp; 801 ++sp; 802 } 803 sp = &score[NROW]; /* Column 0, deletes. */ 804 tempcost = 0; 805 for (i = 1; i <= size; ++i) { 806 sp->s_itrace = i - 1; 807 sp->s_jtrace = 0; 808 tempcost += tcdell; 809 sp->s_cost = tempcost; 810 sp += NROW; 811 } 812 sp1 = &score[NROW + 1]; /* [1, 1]. */ 813 pp = &pbase[1]; 814 for (i = 1; i <= size; ++i) { 815 sp = sp1; 816 vp = &vbase[1]; 817 for (j = 1; j <= size; ++j) { 818 sp->s_itrace = i - 1; 819 sp->s_jtrace = j; 820 bestcost = (sp - NROW)->s_cost; 821 if (j != size) /* Cd(A[i])=0 @ Dis. */ 822 bestcost += tcdell; 823 tempcost = (sp - 1)->s_cost; 824 tempcost += (*vp)->v_cost; 825 if (i != size) /* Ci(B[j])=0 @ Dsj. */ 826 tempcost += tcinsl; 827 if (tempcost < bestcost) { 828 sp->s_itrace = i; 829 sp->s_jtrace = j - 1; 830 bestcost = tempcost; 831 } 832 tempcost = (sp - NROW - 1)->s_cost; 833 if ((*pp)->v_color != (*vp)->v_color 834 || (*pp)->v_hash != (*vp)->v_hash) 835 tempcost += (*vp)->v_cost; 836 if (tempcost < bestcost) { 837 sp->s_itrace = i - 1; 838 sp->s_jtrace = j - 1; 839 bestcost = tempcost; 840 } 841 sp->s_cost = bestcost; 842 ++sp; /* Next column. */ 843 ++vp; 844 } 845 ++pp; 846 sp1 += NROW; /* Next row. */ 847 } 848 } 849 850 /* 851 * Trace back through the dynamic programming cost 852 * matrix, and update the screen using an optimal sequence 853 * of redraws, insert lines, and delete lines. The "offs" is 854 * the origin 0 offset of the chunk of the screen we are about to 855 * update. The "i" and "j" are always started in the lower right 856 * corner of the matrix, and imply the size of the screen. 857 * A full screen traceback is called with offs=0 and i=j=nrow-1. 858 * There is some do-it-yourself double subscripting here, 859 * which is acceptable because this routine is much less compute 860 * intensive then the code that builds the score matrix! 861 */ 862 void 863 traceback(offs, size, i, j) 864 int offs; 865 int size; 866 int i; 867 int j; 868 { 869 int itrace; 870 int jtrace; 871 int k; 872 int ninsl; 873 int ndraw; 874 int ndell; 875 876 if (i == 0 && j == 0) /* End of update. */ 877 return; 878 itrace = score[(NROW * i) + j].s_itrace; 879 jtrace = score[(NROW * i) + j].s_jtrace; 880 if (itrace == i) { /* [i, j-1] */ 881 ninsl = 0; /* Collect inserts. */ 882 if (i != size) 883 ninsl = 1; 884 ndraw = 1; 885 while (itrace != 0 || jtrace != 0) { 886 if (score[(NROW * itrace) + jtrace].s_itrace != itrace) 887 break; 888 jtrace = score[(NROW * itrace) + jtrace].s_jtrace; 889 if (i != size) 890 ++ninsl; 891 ++ndraw; 892 } 893 traceback(offs, size, itrace, jtrace); 894 if (ninsl != 0) { 895 ttcolor(CTEXT); 896 ttinsl(offs + j - ninsl, offs + size - 1, ninsl); 897 } 898 do { /* B[j], A[j] blank. */ 899 k = offs + j - ndraw; 900 uline(k, vscreen[k], &blanks); 901 } while (--ndraw); 902 return; 903 } 904 if (jtrace == j) { /* [i-1, j] */ 905 ndell = 0; /* Collect deletes. */ 906 if (j != size) 907 ndell = 1; 908 while (itrace != 0 || jtrace != 0) { 909 if (score[(NROW * itrace) + jtrace].s_jtrace != jtrace) 910 break; 911 itrace = score[(NROW * itrace) + jtrace].s_itrace; 912 if (j != size) 913 ++ndell; 914 } 915 if (ndell != 0) { 916 ttcolor(CTEXT); 917 ttdell(offs + i - ndell, offs + size - 1, ndell); 918 } 919 traceback(offs, size, itrace, jtrace); 920 return; 921 } 922 traceback(offs, size, itrace, jtrace); 923 k = offs + j - 1; 924 uline(k, vscreen[k], pscreen[offs + i - 1]); 925 } 926 #endif 927