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