/* $OpenBSD: display.c,v 1.48 2017/07/06 19:27:37 schwarze Exp $ */
/* This file is in the public domain. */
/*
* The functions in this file handle redisplay. The
* redisplay system knows almost nothing about the editing
* process; the editing functions do, however, set some
* hints to eliminate a lot of the grinding. There is more
* that can be done; the "vtputc" interface is a real
* pig.
*/
#include <sys/queue.h>
#include <ctype.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <term.h>
#include "def.h"
#include "kbd.h"
/*
* A video structure always holds
* an array of characters whose length is equal to
* the longest line possible. v_text is allocated
* dynamically to fit the screen width.
*/
struct video {
short v_hash; /* Hash code, for compares. */
short v_flag; /* Flag word. */
short v_color; /* Color of the line. */
int v_cost; /* Cost of display. */
char *v_text; /* The actual characters. */
};
#define VFCHG 0x0001 /* Changed. */
#define VFHBAD 0x0002 /* Hash and cost are bad. */
#define VFEXT 0x0004 /* extended line (beond ncol) */
/*
* SCORE structures hold the optimal
* trace trajectory, and the cost of redisplay, when
* the dynamic programming redisplay code is used.
*/
struct score {
int s_itrace; /* "i" index for track back. */
int s_jtrace; /* "j" index for trace back. */
int s_cost; /* Display cost. */
};
void vtmove(int, int);
void vtputc(int);
void vtpute(int);
int vtputs(const char *);
void vteeol(void);
void updext(int, int);
void modeline(struct mgwin *, int);
void setscores(int, int);
void traceback(int, int, int, int);
void ucopy(struct video *, struct video *);
void uline(int, struct video *, struct video *);
void hash(struct video *);
int sgarbf = TRUE; /* TRUE if screen is garbage. */
int vtrow = HUGE; /* Virtual cursor row. */
int vtcol = HUGE; /* Virtual cursor column. */
int tthue = CNONE; /* Current color. */
int ttrow = HUGE; /* Physical cursor row. */
int ttcol = HUGE; /* Physical cursor column. */
int tttop = HUGE; /* Top of scroll region. */
int ttbot = HUGE; /* Bottom of scroll region. */
int lbound = 0; /* leftmost bound of the current */
/* line being displayed */
struct video **vscreen; /* Edge vector, virtual. */
struct video **pscreen; /* Edge vector, physical. */
struct video *video; /* Actual screen data. */
struct video blanks; /* Blank line image. */
/*
* This matrix is written as an array because
* we do funny things in the "setscores" routine, which
* is very compute intensive, to make the subscripts go away.
* It would be "SCORE score[NROW][NROW]" in old speak.
* Look at "setscores" to understand what is up.
*/
struct score *score; /* [NROW * NROW] */
static int linenos = TRUE;
static int colnos = FALSE;
/* Is macro recording enabled? */
extern int macrodef;
/* Is working directory global? */
extern int globalwd;
/*
* Since we don't have variables (we probably should) these are command
* processors for changing the values of mode flags.
*/
/* ARGSUSED */
int
linenotoggle(int f, int n)
{
if (f & FFARG)
linenos = n > 0;
else
linenos = !linenos;
sgarbf = TRUE;
return (TRUE);
}
/* ARGSUSED */
int
colnotoggle(int f, int n)
{
if (f & FFARG)
colnos = n > 0;
else
colnos = !colnos;
sgarbf = TRUE;
return (TRUE);
}
/*
* Reinit the display data structures, this is called when the terminal
* size changes.
*/
int
vtresize(int force, int newrow, int newcol)
{
int i;
int rowchanged, colchanged;
static int first_run = 1;
struct video *vp;
if (newrow < 1 || newcol < 1)
return (FALSE);
rowchanged = (newrow != nrow);
colchanged = (newcol != ncol);
#define TRYREALLOC(a, n) do { \
void *tmp; \
if ((tmp = realloc((a), (n))) == NULL) { \
panic("out of memory in display code"); \
} \
(a) = tmp; \
} while (0)
#define TRYREALLOCARRAY(a, n, m) do { \
void *tmp; \
if ((tmp = reallocarray((a), (n), (m))) == NULL) {\
panic("out of memory in display code"); \
} \
(a) = tmp; \
} while (0)
/* No update needed */
if (!first_run && !force && !rowchanged && !colchanged)
return (TRUE);
if (first_run)
memset(&blanks, 0, sizeof(blanks));
if (rowchanged || first_run) {
int vidstart;
/*
* This is not pretty.
*/
if (nrow == 0)
vidstart = 0;
else
vidstart = 2 * (nrow - 1);
/*
* We're shrinking, free some internal data.
*/
if (newrow < nrow) {
for (i = 2 * (newrow - 1); i < 2 * (nrow - 1); i++) {
free(video[i].v_text);
video[i].v_text = NULL;
}
}
TRYREALLOCARRAY(score, newrow, newrow * sizeof(struct score));
TRYREALLOCARRAY(vscreen, (newrow - 1), sizeof(struct video *));
TRYREALLOCARRAY(pscreen, (newrow - 1), sizeof(struct video *));
TRYREALLOCARRAY(video, (newrow - 1), 2 * sizeof(struct video));
/*
* Zero-out the entries we just allocated.
*/
for (i = vidstart; i < 2 * (newrow - 1); i++)
memset(&video[i], 0, sizeof(struct video));
/*
* Reinitialize vscreen and pscreen arrays completely.
*/
vp = &video[0];
for (i = 0; i < newrow - 1; ++i) {
vscreen[i] = vp;
++vp;
pscreen[i] = vp;
++vp;
}
}
if (rowchanged || colchanged || first_run) {
for (i = 0; i < 2 * (newrow - 1); i++)
TRYREALLOC(video[i].v_text, newcol);
TRYREALLOC(blanks.v_text, newcol);
}
nrow = newrow;
ncol = newcol;
if (ttrow > nrow)
ttrow = nrow;
if (ttcol > ncol)
ttcol = ncol;
first_run = 0;
return (TRUE);
}
#undef TRYREALLOC
#undef TRYREALLOCARRAY
/*
* Initialize the data structures used
* by the display code. The edge vectors used
* to access the screens are set up. The operating
* system's terminal I/O channel is set up. Fill the
* "blanks" array with ASCII blanks. The rest is done
* at compile time. The original window is marked
* as needing full update, and the physical screen
* is marked as garbage, so all the right stuff happens
* on the first call to redisplay.
*/
void
vtinit(void)
{
int i;
ttopen();
ttinit();
/*
* ttinit called ttresize(), which called vtresize(), so our data
* structures are setup correctly.
*/
blanks.v_color = CTEXT;
for (i = 0; i < ncol; ++i)
blanks.v_text[i] = ' ';
}
/*
* Tidy up the virtual display system
* in anticipation of a return back to the host
* operating system. Right now all we do is position
* the cursor to the last line, erase the line, and
* close the terminal channel.
*/
void
vttidy(void)
{
ttcolor(CTEXT);
ttnowindow(); /* No scroll window. */
ttmove(nrow - 1, 0); /* Echo line. */
tteeol();
tttidy();
ttflush();
ttclose();
}
/*
* Move the virtual cursor to an origin
* 0 spot on the virtual display screen. I could
* store the column as a character pointer to the spot
* on the line, which would make "vtputc" a little bit
* more efficient. No checking for errors.
*/
void
vtmove(int row, int col)
{
vtrow = row;
vtcol = col;
}
/*
* Write a character to the virtual display,
* dealing with long lines and the display of unprintable
* things like control characters. Also expand tabs every 8
* columns. This code only puts printing characters into
* the virtual display image. Special care must be taken when
* expanding tabs. On a screen whose width is not a multiple
* of 8, it is possible for the virtual cursor to hit the
* right margin before the next tab stop is reached. This
* makes the tab code loop if you are not careful.
* Three guesses how we found this.
*/
void
vtputc(int c)
{
struct video *vp;
c &= 0xff;
vp = vscreen[vtrow];
if (vtcol >= ncol)
vp->v_text[ncol - 1] = '$';
else if (c == '\t'
#ifdef NOTAB
&& !(curbp->b_flag & BFNOTAB)
#endif
) {
do {
vtputc(' ');
} while (vtcol < ncol && (vtcol & 0x07) != 0);
} else if (ISCTRL(c)) {
vtputc('^');
vtputc(CCHR(c));
} else if (isprint(c))
vp->v_text[vtcol++] = c;
else {
char bf[5];
snprintf(bf, sizeof(bf), "\\%o", c);
vtputs(bf);
}
}
/*
* Put a character to the virtual screen in an extended line. If we are not
* yet on left edge, don't print it yet. Check for overflow on the right
* margin.
*/
void
vtpute(int c)
{
struct video *vp;
c &= 0xff;
vp = vscreen[vtrow];
if (vtcol >= ncol)
vp->v_text[ncol - 1] = '$';
else if (c == '\t'
#ifdef NOTAB
&& !(curbp->b_flag & BFNOTAB)
#endif
) {
do {
vtpute(' ');
} while (((vtcol + lbound) & 0x07) != 0 && vtcol < ncol);
} else if (ISCTRL(c) != FALSE) {
vtpute('^');
vtpute(CCHR(c));
} else if (isprint(c)) {
if (vtcol >= 0)
vp->v_text[vtcol] = c;
++vtcol;
} else {
char bf[5], *cp;
snprintf(bf, sizeof(bf), "\\%o", c);
for (cp = bf; *cp != '\0'; cp++)
vtpute(*cp);
}
}
/*
* Erase from the end of the software cursor to the end of the line on which
* the software cursor is located. The display routines will decide if a
* hardware erase to end of line command should be used to display this.
*/
void
vteeol(void)
{
struct video *vp;
vp = vscreen[vtrow];
while (vtcol < ncol)
vp->v_text[vtcol++] = ' ';
}
/*
* Make sure that the display is
* right. This is a three part process. First,
* scan through all of the windows looking for dirty
* ones. Check the framing, and refresh the screen.
* Second, make sure that "currow" and "curcol" are
* correct for the current window. Third, make the
* virtual and physical screens the same.
*/
void
update(int modelinecolor)
{
struct line *lp;
struct mgwin *wp;
struct video *vp1;
struct video *vp2;
int c, i, j;
int hflag;
int currow, curcol;
int offs, size;
if (charswaiting())
return;
if (sgarbf) { /* must update everything */
wp = wheadp;
while (wp != NULL) {
wp->w_rflag |= WFMODE | WFFULL;
wp = wp->w_wndp;
}
}
if (linenos || colnos) {
wp = wheadp;
while (wp != NULL) {
wp->w_rflag |= WFMODE;
wp = wp->w_wndp;
}
}
hflag = FALSE; /* Not hard. */
for (wp = wheadp; wp != NULL; wp = wp->w_wndp) {
/*
* Nothing to be done.
*/
if (wp->w_rflag == 0)
continue;
if ((wp->w_rflag & WFFRAME) == 0) {
lp = wp->w_linep;
for (i = 0; i < wp->w_ntrows; ++i) {
if (lp == wp->w_dotp)
goto out;
if (lp == wp->w_bufp->b_headp)
break;
lp = lforw(lp);
}
}
/*
* Put the middle-line in place.
*/
i = wp->w_frame;
if (i > 0) {
--i;
if (i >= wp->w_ntrows)
i = wp->w_ntrows - 1;
} else if (i < 0) {
i += wp->w_ntrows;
if (i < 0)
i = 0;
} else
i = wp->w_ntrows / 2; /* current center, no change */
/*
* Find the line.
*/
lp = wp->w_dotp;
while (i != 0 && lback(lp) != wp->w_bufp->b_headp) {
--i;
lp = lback(lp);
}
wp->w_linep = lp;
wp->w_rflag |= WFFULL; /* Force full. */
out:
lp = wp->w_linep; /* Try reduced update. */
i = wp->w_toprow;
if ((wp->w_rflag & ~WFMODE) == WFEDIT) {
while (lp != wp->w_dotp) {
++i;
lp = lforw(lp);
}
vscreen[i]->v_color = CTEXT;
vscreen[i]->v_flag |= (VFCHG | VFHBAD);
vtmove(i, 0);
for (j = 0; j < llength(lp); ++j)
vtputc(lgetc(lp, j));
vteeol();
} else if ((wp->w_rflag & (WFEDIT | WFFULL)) != 0) {
hflag = TRUE;
while (i < wp->w_toprow + wp->w_ntrows) {
vscreen[i]->v_color = CTEXT;
vscreen[i]->v_flag |= (VFCHG | VFHBAD);
vtmove(i, 0);
if (lp != wp->w_bufp->b_headp) {
for (j = 0; j < llength(lp); ++j)
vtputc(lgetc(lp, j));
lp = lforw(lp);
}
vteeol();
++i;
}
}
if ((wp->w_rflag & WFMODE) != 0)
modeline(wp, modelinecolor);
wp->w_rflag = 0;
wp->w_frame = 0;
}
lp = curwp->w_linep; /* Cursor location. */
currow = curwp->w_toprow;
while (lp != curwp->w_dotp) {
++currow;
lp = lforw(lp);
}
curcol = 0;
i = 0;
while (i < curwp->w_doto) {
c = lgetc(lp, i++);
if (c == '\t'
#ifdef NOTAB
&& !(curbp->b_flag & BFNOTAB)
#endif
) {
curcol |= 0x07;
curcol++;
} else if (ISCTRL(c) != FALSE)
curcol += 2;
else if (isprint(c))
curcol++;
else {
char bf[5];
snprintf(bf, sizeof(bf), "\\%o", c);
curcol += strlen(bf);
}
}
if (curcol >= ncol - 1) { /* extended line. */
/* flag we are extended and changed */
vscreen[currow]->v_flag |= VFEXT | VFCHG;
updext(currow, curcol); /* and output extended line */
} else
lbound = 0; /* not extended line */
/*
* Make sure no lines need to be de-extended because the cursor is no
* longer on them.
*/
wp = wheadp;
while (wp != NULL) {
lp = wp->w_linep;
i = wp->w_toprow;
while (i < wp->w_toprow + wp->w_ntrows) {
if (vscreen[i]->v_flag & VFEXT) {
/* always flag extended lines as changed */
vscreen[i]->v_flag |= VFCHG;
if ((wp != curwp) || (lp != wp->w_dotp) ||
(curcol < ncol - 1)) {
vtmove(i, 0);
for (j = 0; j < llength(lp); ++j)
vtputc(lgetc(lp, j));
vteeol();
/* this line no longer is extended */
vscreen[i]->v_flag &= ~VFEXT;
}
}
lp = lforw(lp);
++i;
}
/* if garbaged then fix up mode lines */
if (sgarbf != FALSE)
vscreen[i]->v_flag |= VFCHG;
/* and onward to the next window */
wp = wp->w_wndp;
}
if (sgarbf != FALSE) { /* Screen is garbage. */
sgarbf = FALSE; /* Erase-page clears. */
epresf = FALSE; /* The message area. */
tttop = HUGE; /* Forget where you set. */
ttbot = HUGE; /* scroll region. */
tthue = CNONE; /* Color unknown. */
ttmove(0, 0);
tteeop();
for (i = 0; i < nrow - 1; ++i) {
uline(i, vscreen[i], &blanks);
ucopy(vscreen[i], pscreen[i]);
}
ttmove(currow, curcol - lbound);
ttflush();
return;
}
if (hflag != FALSE) { /* Hard update? */
for (i = 0; i < nrow - 1; ++i) {/* Compute hash data. */
hash(vscreen[i]);
hash(pscreen[i]);
}
offs = 0; /* Get top match. */
while (offs != nrow - 1) {
vp1 = vscreen[offs];
vp2 = pscreen[offs];
if (vp1->v_color != vp2->v_color
|| vp1->v_hash != vp2->v_hash)
break;
uline(offs, vp1, vp2);
ucopy(vp1, vp2);
++offs;
}
if (offs == nrow - 1) { /* Might get it all. */
ttmove(currow, curcol - lbound);
ttflush();
return;
}
size = nrow - 1; /* Get bottom match. */
while (size != offs) {
vp1 = vscreen[size - 1];
vp2 = pscreen[size - 1];
if (vp1->v_color != vp2->v_color
|| vp1->v_hash != vp2->v_hash)
break;
uline(size - 1, vp1, vp2);
ucopy(vp1, vp2);
--size;
}
if ((size -= offs) == 0) /* Get screen size. */
panic("Illegal screen size in update");
setscores(offs, size); /* Do hard update. */
traceback(offs, size, size, size);
for (i = 0; i < size; ++i)
ucopy(vscreen[offs + i], pscreen[offs + i]);
ttmove(currow, curcol - lbound);
ttflush();
return;
}
for (i = 0; i < nrow - 1; ++i) { /* Easy update. */
vp1 = vscreen[i];
vp2 = pscreen[i];
if ((vp1->v_flag & VFCHG) != 0) {
uline(i, vp1, vp2);
ucopy(vp1, vp2);
}
}
ttmove(currow, curcol - lbound);
ttflush();
}
/*
* Update a saved copy of a line,
* kept in a video structure. The "vvp" is
* the one in the "vscreen". The "pvp" is the one
* in the "pscreen". This is called to make the
* virtual and physical screens the same when
* display has done an update.
*/
void
ucopy(struct video *vvp, struct video *pvp)
{
vvp->v_flag &= ~VFCHG; /* Changes done. */
pvp->v_flag = vvp->v_flag; /* Update model. */
pvp->v_hash = vvp->v_hash;
pvp->v_cost = vvp->v_cost;
pvp->v_color = vvp->v_color;
bcopy(vvp->v_text, pvp->v_text, ncol);
}
/*
* updext: update the extended line which the cursor is currently on at a
* column greater than the terminal width. The line will be scrolled right or
* left to let the user see where the cursor is.
*/
void
updext(int currow, int curcol)
{
struct line *lp; /* pointer to current line */
int j; /* index into line */
if (ncol < 2)
return;
/*
* calculate what column the left bound should be
* (force cursor into middle half of screen)
*/
lbound = curcol - (curcol % (ncol >> 1)) - (ncol >> 2);
/*
* scan through the line outputing characters to the virtual screen
* once we reach the left edge
*/
vtmove(currow, -lbound); /* start scanning offscreen */
lp = curwp->w_dotp; /* line to output */
for (j = 0; j < llength(lp); ++j) /* until the end-of-line */
vtpute(lgetc(lp, j));
vteeol(); /* truncate the virtual line */
vscreen[currow]->v_text[0] = '$'; /* and put a '$' in column 1 */
}
/*
* Update a single line. This routine only
* uses basic functionality (no insert and delete character,
* but erase to end of line). The "vvp" points at the video
* structure for the line on the virtual screen, and the "pvp"
* is the same for the physical screen. Avoid erase to end of
* line when updating CMODE color lines, because of the way that
* reverse video works on most terminals.
*/
void
uline(int row, struct video *vvp, struct video *pvp)
{
char *cp1;
char *cp2;
char *cp3;
char *cp4;
char *cp5;
int nbflag;
if (vvp->v_color != pvp->v_color) { /* Wrong color, do a */
ttmove(row, 0); /* full redraw. */
#ifdef STANDOUT_GLITCH
if (pvp->v_color != CTEXT && magic_cookie_glitch >= 0)
tteeol();
#endif
ttcolor(vvp->v_color);
#ifdef STANDOUT_GLITCH
cp1 = &vvp->v_text[magic_cookie_glitch > 0 ? magic_cookie_glitch : 0];
/*
* The odd code for magic_cookie_glitch==0 is to avoid
* putting the invisible glitch character on the next line.
* (Hazeltine executive 80 model 30)
*/
cp2 = &vvp->v_text[ncol - (magic_cookie_glitch >= 0 ?
(magic_cookie_glitch != 0 ? magic_cookie_glitch : 1) : 0)];
#else
cp1 = &vvp->v_text[0];
cp2 = &vvp->v_text[ncol];
#endif
while (cp1 != cp2) {
ttputc(*cp1++);
++ttcol;
}
ttcolor(CTEXT);
return;
}
cp1 = &vvp->v_text[0]; /* Compute left match. */
cp2 = &pvp->v_text[0];
while (cp1 != &vvp->v_text[ncol] && cp1[0] == cp2[0]) {
++cp1;
++cp2;
}
if (cp1 == &vvp->v_text[ncol]) /* All equal. */
return;
nbflag = FALSE;
cp3 = &vvp->v_text[ncol]; /* Compute right match. */
cp4 = &pvp->v_text[ncol];
while (cp3[-1] == cp4[-1]) {
--cp3;
--cp4;
if (cp3[0] != ' ') /* Note non-blanks in */
nbflag = TRUE; /* the right match. */
}
cp5 = cp3; /* Is erase good? */
if (nbflag == FALSE && vvp->v_color == CTEXT) {
while (cp5 != cp1 && cp5[-1] == ' ')
--cp5;
/* Alcyon hack */
if ((int) (cp3 - cp5) <= tceeol)
cp5 = cp3;
}
/* Alcyon hack */
ttmove(row, (int) (cp1 - &vvp->v_text[0]));
#ifdef STANDOUT_GLITCH
if (vvp->v_color != CTEXT && magic_cookie_glitch > 0) {
if (cp1 < &vvp->v_text[magic_cookie_glitch])
cp1 = &vvp->v_text[magic_cookie_glitch];
if (cp5 > &vvp->v_text[ncol - magic_cookie_glitch])
cp5 = &vvp->v_text[ncol - magic_cookie_glitch];
} else if (magic_cookie_glitch < 0)
#endif
ttcolor(vvp->v_color);
while (cp1 != cp5) {
ttputc(*cp1++);
++ttcol;
}
if (cp5 != cp3) /* Do erase. */
tteeol();
}
/*
* Redisplay the mode line for the window pointed to by the "wp".
* This is the only routine that has any idea of how the mode line is
* formatted. You can change the modeline format by hacking at this
* routine. Called by "update" any time there is a dirty window. Note
* that if STANDOUT_GLITCH is defined, first and last magic_cookie_glitch
* characters may never be seen.
*/
void
modeline(struct mgwin *wp, int modelinecolor)
{
int n, md;
struct buffer *bp;
char sl[21]; /* Overkill. Space for 2^64 in base 10. */
int len;
n = wp->w_toprow + wp->w_ntrows; /* Location. */
vscreen[n]->v_color = modelinecolor; /* Mode line color. */
vscreen[n]->v_flag |= (VFCHG | VFHBAD); /* Recompute, display. */
vtmove(n, 0); /* Seek to right line. */
bp = wp->w_bufp;
vtputc('-');
vtputc('-');
if ((bp->b_flag & BFREADONLY) != 0) {
vtputc('%');
if ((bp->b_flag & BFCHG) != 0)
vtputc('*');
else
vtputc('%');
} else if ((bp->b_flag & BFCHG) != 0) { /* "*" if changed. */
vtputc('*');
vtputc('*');
} else {
vtputc('-');
vtputc('-');
}
vtputc('-');
n = 5;
n += vtputs("Mg: ");
if (bp->b_bname[0] != '\0')
n += vtputs(&(bp->b_bname[0]));
while (n < 42) { /* Pad out with blanks. */
vtputc(' ');
++n;
}
vtputc('(');
++n;
for (md = 0; ; ) {
n += vtputs(bp->b_modes[md]->p_name);
if (++md > bp->b_nmodes)
break;
vtputc('-');
++n;
}
/* XXX These should eventually move to a real mode */
if (macrodef == TRUE)
n += vtputs("-def");
if (globalwd == TRUE)
n += vtputs("-gwd");
vtputc(')');
++n;
if (linenos && colnos)
len = snprintf(sl, sizeof(sl), "--L%d--C%d", wp->w_dotline,
getcolpos(wp));
else if (linenos)
len = snprintf(sl, sizeof(sl), "--L%d", wp->w_dotline);
else if (colnos)
len = snprintf(sl, sizeof(sl), "--C%d", getcolpos(wp));
if ((linenos || colnos) && len < sizeof(sl) && len != -1)
n += vtputs(sl);
while (n < ncol) { /* Pad out. */
vtputc('-');
++n;
}
}
/*
* Output a string to the mode line, report how long it was.
*/
int
vtputs(const char *s)
{
int n = 0;
while (*s != '\0') {
vtputc(*s++);
++n;
}
return (n);
}
/*
* Compute the hash code for the line pointed to by the "vp".
* Recompute it if necessary. Also set the approximate redisplay
* cost. The validity of the hash code is marked by a flag bit.
* The cost understand the advantages of erase to end of line.
* Tuned for the VAX by Bob McNamara; better than it used to be on
* just about any machine.
*/
void
hash(struct video *vp)
{
int i, n;
char *s;
if ((vp->v_flag & VFHBAD) != 0) { /* Hash bad. */
s = &vp->v_text[ncol - 1];
for (i = ncol; i != 0; --i, --s)
if (*s != ' ')
break;
n = ncol - i; /* Erase cheaper? */
if (n > tceeol)
n = tceeol;
vp->v_cost = i + n; /* Bytes + blanks. */
for (n = 0; i != 0; --i, --s)
n = (n << 5) + n + *s;
vp->v_hash = n; /* Hash code. */
vp->v_flag &= ~VFHBAD; /* Flag as all done. */
}
}
/*
* Compute the Insert-Delete
* cost matrix. The dynamic programming algorithm
* described by James Gosling is used. This code assumes
* that the line above the echo line is the last line involved
* in the scroll region. This is easy to arrange on the VT100
* because of the scrolling region. The "offs" is the origin 0
* offset of the first row in the virtual/physical screen that
* is being updated; the "size" is the length of the chunk of
* screen being updated. For a full screen update, use offs=0
* and size=nrow-1.
*
* Older versions of this code implemented the score matrix by
* a two dimensional array of SCORE nodes. This put all kinds of
* multiply instructions in the code! This version is written to
* use a linear array and pointers, and contains no multiplication
* at all. The code has been carefully looked at on the VAX, with
* only marginal checking on other machines for efficiency. In
* fact, this has been tuned twice! Bob McNamara tuned it even
* more for the VAX, which is a big issue for him because of
* the 66 line X displays.
*
* On some machines, replacing the "for (i=1; i<=size; ++i)" with
* i = 1; do { } while (++i <=size)" will make the code quite a
* bit better; but it looks ugly.
*/
void
setscores(int offs, int size)
{
struct score *sp;
struct score *sp1;
struct video **vp, **pp;
struct video **vbase, **pbase;
int tempcost;
int bestcost;
int j, i;
vbase = &vscreen[offs - 1]; /* By hand CSE's. */
pbase = &pscreen[offs - 1];
score[0].s_itrace = 0; /* [0, 0] */
score[0].s_jtrace = 0;
score[0].s_cost = 0;
sp = &score[1]; /* Row 0, inserts. */
tempcost = 0;
vp = &vbase[1];
for (j = 1; j <= size; ++j) {
sp->s_itrace = 0;
sp->s_jtrace = j - 1;
tempcost += tcinsl;
tempcost += (*vp)->v_cost;
sp->s_cost = tempcost;
++vp;
++sp;
}
sp = &score[nrow]; /* Column 0, deletes. */
tempcost = 0;
for (i = 1; i <= size; ++i) {
sp->s_itrace = i - 1;
sp->s_jtrace = 0;
tempcost += tcdell;
sp->s_cost = tempcost;
sp += nrow;
}
sp1 = &score[nrow + 1]; /* [1, 1]. */
pp = &pbase[1];
for (i = 1; i <= size; ++i) {
sp = sp1;
vp = &vbase[1];
for (j = 1; j <= size; ++j) {
sp->s_itrace = i - 1;
sp->s_jtrace = j;
bestcost = (sp - nrow)->s_cost;
if (j != size) /* Cd(A[i])=0 @ Dis. */
bestcost += tcdell;
tempcost = (sp - 1)->s_cost;
tempcost += (*vp)->v_cost;
if (i != size) /* Ci(B[j])=0 @ Dsj. */
tempcost += tcinsl;
if (tempcost < bestcost) {
sp->s_itrace = i;
sp->s_jtrace = j - 1;
bestcost = tempcost;
}
tempcost = (sp - nrow - 1)->s_cost;
if ((*pp)->v_color != (*vp)->v_color
|| (*pp)->v_hash != (*vp)->v_hash)
tempcost += (*vp)->v_cost;
if (tempcost < bestcost) {
sp->s_itrace = i - 1;
sp->s_jtrace = j - 1;
bestcost = tempcost;
}
sp->s_cost = bestcost;
++sp; /* Next column. */
++vp;
}
++pp;
sp1 += nrow; /* Next row. */
}
}
/*
* Trace back through the dynamic programming cost
* matrix, and update the screen using an optimal sequence
* of redraws, insert lines, and delete lines. The "offs" is
* the origin 0 offset of the chunk of the screen we are about to
* update. The "i" and "j" are always started in the lower right
* corner of the matrix, and imply the size of the screen.
* A full screen traceback is called with offs=0 and i=j=nrow-1.
* There is some do-it-yourself double subscripting here,
* which is acceptable because this routine is much less compute
* intensive then the code that builds the score matrix!
*/
void
traceback(int offs, int size, int i, int j)
{
int itrace, jtrace;
int k;
int ninsl, ndraw, ndell;
if (i == 0 && j == 0) /* End of update. */
return;
itrace = score[(nrow * i) + j].s_itrace;
jtrace = score[(nrow * i) + j].s_jtrace;
if (itrace == i) { /* [i, j-1] */
ninsl = 0; /* Collect inserts. */
if (i != size)
ninsl = 1;
ndraw = 1;
while (itrace != 0 || jtrace != 0) {
if (score[(nrow * itrace) + jtrace].s_itrace != itrace)
break;
jtrace = score[(nrow * itrace) + jtrace].s_jtrace;
if (i != size)
++ninsl;
++ndraw;
}
traceback(offs, size, itrace, jtrace);
if (ninsl != 0) {
ttcolor(CTEXT);
ttinsl(offs + j - ninsl, offs + size - 1, ninsl);
}
do { /* B[j], A[j] blank. */
k = offs + j - ndraw;
uline(k, vscreen[k], &blanks);
} while (--ndraw);
return;
}
if (jtrace == j) { /* [i-1, j] */
ndell = 0; /* Collect deletes. */
if (j != size)
ndell = 1;
while (itrace != 0 || jtrace != 0) {
if (score[(nrow * itrace) + jtrace].s_jtrace != jtrace)
break;
itrace = score[(nrow * itrace) + jtrace].s_itrace;
if (j != size)
++ndell;
}
if (ndell != 0) {
ttcolor(CTEXT);
ttdell(offs + i - ndell, offs + size - 1, ndell);
}
traceback(offs, size, itrace, jtrace);
return;
}
traceback(offs, size, itrace, jtrace);
k = offs + j - 1;
uline(k, vscreen[k], pscreen[offs + i - 1]);
}