1/*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License").  You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22/*
23 * Copyright 2015 Gary Mills
24 * Copyright (c) 1995, by Sun Microsystems, Inc.
25 * All rights reserved.
26 */
27
28/*
29 * doupdate.c
30 *
31 * XCurses Library
32 *
33 * Copyright 1990, 1995 by Mortice Kern Systems Inc.  All rights reserved.
34 *
35 */
36
37#ifdef M_RCSID
38#ifndef lint
39static char const rcsID[] = "$Header: /rd/src/libc/xcurses/rcs/doupdate.c 1.9 1995/07/26 17:45:06 ant Exp $";
40#endif
41#endif
42
43#include <private.h>
44#include <string.h>
45#include <setjmp.h>
46#include <signal.h>
47
48#undef SIGTSTP
49
50/*
51 * Disable typeahead trapping because it slow down updated dramatically
52 * on MPE/iX.
53 */
54#ifdef MPE_STUB
55#undef M_CURSES_TYPEAHEAD
56#endif
57
58/*
59 * This value is the ideal length for the cursor addressing sequence
60 * being four bytes long, ie. "<escape><cursor addressing code><row><col>".
61 * eg. VT52 - "\EYrc" or ADM3A - "\E=rc"
62 */
63#define JUMP_SIZE	4
64
65/*
66 * This value is the ideal length for the clear-to-eol sequence
67 * being two bytes long, ie "<escape><clear eol code>".
68 */
69#define CEOL_SIZE	2
70
71#define GOTO(r,c)	(__m_mvcur(curscr->_cury, curscr->_curx,r,c,__m_outc),\
72			curscr->_cury = r, curscr->_curx = c)
73
74typedef struct cost_op {
75	short cost;
76	short op;
77} lcost;
78
79typedef void (*t_action)(int, int);
80
81static jmp_buf breakout;
82
83#define LC(i,j) 	(lc[(i) * (LINES + 1) + (j)])
84
85static lcost *lc = (lcost *) 0;
86static unsigned long *nhash = (unsigned long *) 0;
87static t_action *del = (t_action *) 0;
88static t_action *ins_rep = (t_action *) 0;
89
90static WINDOW *newscr;
91
92STATIC void erase_bottom(int);
93STATIC void clear_bottom(int);
94STATIC void complex(void);
95STATIC int cost(int, int);
96STATIC void lines_delete(int, int);
97STATIC void lines_insert(int, int);
98STATIC void lines_replace(int, int);
99STATIC void script(int, int);
100STATIC int scroll_dn(int);
101STATIC int scroll_up(int);
102STATIC void simple(void);
103STATIC void text_replace(int);
104STATIC void block_over(int, int, int);
105
106/*f
107 * Wrapper that streams Curses output.
108 *
109 * All escape sequences going to the screen come through here.
110 * All ordinary characters go to the screen via the putc in doupdate.c
111 */
112int
113__m_outc(ch)
114int ch;
115{
116        return putc(ch, __m_screen->_of);
117}
118
119/*
120 * Allocate or grow doupdate() structures.
121 */
122int
123__m_doupdate_init()
124{
125	void *new;
126	static short nlines = 0;
127
128	if (lines <= 0)
129		return -1;
130
131	if (lines <= nlines)
132		return 0;
133
134	new = m_malloc((lines+1) * (lines+1) * sizeof *lc);
135	if (new == (void *) 0)
136		return -1;
137	if (lc != (lcost *) 0)
138		free(lc);
139	lc = (lcost *) new;
140
141	new = m_malloc((lines + lines) * sizeof *del);
142	if (new == (void *) 0)
143		return -1;
144	if (del != (t_action *) 0)
145		free(del);
146	del = (t_action *) new;
147	ins_rep = del + lines;
148
149	new = m_malloc(lines * sizeof *nhash);
150	if (new == (void *) 0)
151		return -1;
152	if (nhash != (unsigned long *) 0)
153		free(nhash);
154	nhash = (unsigned long *) new;
155
156	nlines = lines;
157
158	return 0;
159}
160
161STATIC void
162erase_bottom(y)
163int y;
164{
165	int i;
166
167	for (i = y; i < LINES; ++i) {
168		(void) __m_cc_erase(curscr, i, 0, i, curscr->_maxx-1);
169		__m_cc_hash(curscr, __m_screen->_hash, i);
170	}
171}
172
173/*f
174 *  Clear from the start of the current row to bottom of screen.
175 */
176STATIC void
177clear_bottom(y)
178int y;
179{
180	erase_bottom(y);
181
182	/* Restore default color pair before doing area clears. */
183	if (back_color_erase)
184		(void) vid_puts(WA_NORMAL, 0, (void *) 0, __m_outc);
185
186	if (y == 0 && clear_screen != (char *) 0) {
187		(void) tputs(clear_screen, 1, __m_outc);
188	} else {
189		(void) __m_mvcur(-1, -1, y, 0, __m_outc);
190		if (clr_eos != (char *) 0) {
191			(void) tputs(clr_eos, 1, __m_outc);
192		} else if (clr_eol != (char *) 0) {
193			for (;;) {
194				(void) tputs(clr_eol, 1, __m_outc);
195				if (LINES <= y)
196					break;
197				(void) __m_mvcur(y, 0, y+1, 0, __m_outc);
198				++y;
199			}
200		}
201	}
202
203	curscr->_cury = y;
204	curscr->_curx = 0;
205}
206
207/*f
208 * Replace a line of text.
209 *
210 * The principal scheme is to overwrite the region of a line between
211 * the first and last differing characters.  A clear-eol is used to
212 * optimise an update region that consist largely of blanks.  This can
213 * happen fairly often in the case of scrolled lines or full redraws.
214 *
215 * Miller's line redraw algorithm, used in the 'S' editor [Mil87],
216 * should be re-investigated to see if it is simple and fast enough for
217 * our needs, and if it can be adapted to handle the ceol_standout_glitch
218 * (HP 2392A terminals) and multibyte character sequences.
219 *
220 * Very early versions of this code applied a Gosling algorithm column
221 * wise in addition to the row-wise used in complex().  It was removed
222 * in favour of both computation and transmission speed.  The assumption
223 * being that overwrites of a line region occured far more frequently
224 * than the need to insert/delete several isolated characters.
225 *
226 * References:
227 * [Mil87]	W. Miller, A Software Tools Sampler, Prentice-Hall, 1987
228 */
229STATIC void
230text_replace(row)
231int row;
232{
233	short npair;
234	attr_t cookie, nattr;
235	cchar_t *optr, *nptr;
236	int col, last, tail, jump, count;
237
238#ifdef M_CURSES_TYPEAHEAD
239	/* Before replacing a line of text, check for type-ahead. */
240	if (__m_screen->_flags & S_ISATTY) {
241		unsigned char cc;
242
243		if (read(__m_screen->_kfd, &cc, sizeof cc) == sizeof cc) {
244			(void) ungetch(cc);
245			longjmp(breakout, 1);
246		}
247	}
248#endif /* M_CURSES_TYPEAHEAD */
249
250	col = newscr->_first[row];
251	if (col < 0)
252		col = 0;
253
254	last = newscr->_last[row];
255	if (COLS < last)
256		last = COLS;
257
258	if (clr_eol != (char *) 0) {
259		/* Find start of blank tail region. */
260		nptr = &newscr->_line[row][COLS];
261		for (tail = COLS; 0 < tail; --tail) {
262			if (!__m_cc_compare(--nptr, &newscr->_bg, 1))
263				break;
264		}
265
266		/* Only consider clear-to-end-of-line optimization if the
267		 * blank tail falls within the end of the dirty region by
268		 * more than ideal length of clear-to-end-of-line sequence.
269		 * Else disable the check by forcing tail to be at the
270		 * end-of-line.
271		 */
272		if (last < tail + CEOL_SIZE)
273			tail = COLS;
274	}
275
276	optr = &curscr->_line[row][col];
277	nptr = &newscr->_line[row][col];
278
279	for (jump = -1; col < last; ) {
280		/* Skip common regions. */
281		for (count = 0; __m_cc_compare(optr, nptr, 1); ++count) {
282			/* Advance before possible goto. */
283			++optr;
284			++nptr;
285
286			if (last <= ++col)
287				goto done;
288		}
289
290                /* Move the cursor by redrawing characters or using
291                 * cursor motion commands.  The first time that we
292                 * address this row, jump equals -1, so that the cursor
293                 * will be forced to the correct screen line.  Once
294                 * there, we should be able to track the cursor motion
295                 * along the line and jump only when the cost of redrawing
296		 * to column N is more expensive than a jump to column N.
297                 */
298                if (jump < count) {
299			/* First time addressing this row or cost of
300			 * jumping cheaper than redrawing.
301			 */
302                        jump = JUMP_SIZE;
303                        GOTO(row, col);
304			count = 0;
305
306			/* If attributes at start of field are different
307			 * force an attribute cookie to be dropped.
308			 */
309			if (ceol_standout_glitch
310			&& (optr->_at != nptr->_at || optr->_co != nptr->_co))
311				ATTR_STATE |= WA_COOKIE;
312                } else {
313                        /* Redraw to move short distance. */
314			optr -= count;
315			nptr -= count;
316			col -= count;
317		}
318
319		/* Write difference region. */
320		while (col < last
321		&& (!__m_cc_compare(optr, nptr, 1) || 0 < count--)) {
322write_loop:
323			/* Check for clear-to-end-of-line optimization. */
324			if (clr_eol != (char *) 0 && tail <= col) {
325				/* For HP terminals, only clear-to-end-of-line
326				 * once the attributes have been turned off.
327				 * Other terminals, we can proceed normally.
328				 */
329				if (!ceol_standout_glitch
330				|| ATTR_STATE == WA_NORMAL) {
331					curscr->_curx = col;
332					goto done;
333				}
334			}
335
336			++col;
337
338			/* Make sure we don't scroll the screen by writing
339			 * to the bottom right corner.
340			 */
341			if (COLS <= col && LINES-1 <= row
342			&& auto_right_margin && !eat_newline_glitch) {
343				/*** TODO
344				 *** Insert character/auto_right_margin
345				 *** hacks for writting into the last
346				 *** column of the last line so as not
347				 *** to scroll.
348				 ***/
349				curscr->_curx = col;
350				goto done;
351			}
352
353			/* Remember any existing attribute cookie. */
354			cookie = optr->_at & WA_COOKIE;
355
356			nattr = nptr->_at;
357			npair = nptr->_co;
358
359			/* Change attribute state.  On HP terminals we also
360			 * have to check for attribute cookies that may need
361			 * to be changed.
362			 */
363			if (ATTR_STATE != nattr
364			|| optr->_at != nattr || optr->_co != npair) {
365				(void) vid_puts(
366					nattr, npair, (void *) 0, __m_outc
367				);
368
369				/* Remember new or existing cookie. */
370				cookie = WA_COOKIE;
371			}
372
373			/* Don't display internal characters. */
374			if (nptr->_f)
375				(void) __m_cc_write(nptr);
376
377			/* Update copy of screen image. */
378			*optr++ = *nptr++;
379			optr->_at |= cookie;
380		}
381
382		curscr->_curx = col;
383
384		/* Check the attributes at the end of the field with
385		 * those of start of the next common region.  If they
386		 * differ, force another iteration of the write-loop
387		 * that will change the attribute state.
388		 */
389		if (ceol_standout_glitch && col < COLS
390		&& ATTR_STATE != (optr->_at & ~WA_COOKIE))
391			goto write_loop;
392	}
393done:
394	/* Before leaving this line, check if we have to turn off
395	 * attributes and record a cookie.
396	 */
397	if (!move_standout_mode && ATTR_STATE != WA_NORMAL) {
398		/* ceol_standout_glitch, which affects HP terminals,
399		 * drops hidden cookies on the screen where ever the
400		 * cursor is, so disabling attributes before a cursor
401		 * motion operation could disturb existing highlights.
402		 */
403		if (ceol_standout_glitch)
404			/* Attributes on an HP terminal do not cross lines. */
405			ATTR_STATE = A_NORMAL;
406		else
407			(void) vid_puts(WA_NORMAL, 0, (void *) 0, __m_outc);
408	}
409
410	/* Re-check for clear to end-of-line optimization. */
411	if (clr_eol != (char *) 0 && tail <= col && col < last) {
412		/* Is the tail of the current screen image non-blank? */
413		for (tail = col; tail < COLS; ++tail, ++optr)
414			if (!__m_cc_compare(optr, &newscr->_bg, 1))
415				break;
416
417		/* If tail didn't reach the right margin of
418		 * the current screen image, then we will
419		 * make it look like the new image with a
420		 * clear to end-of-line.
421		 */
422		if (tail < COLS) {
423			/* Restore default color pair before area clear. */
424			if (back_color_erase)
425				(void) vid_puts(
426					WA_NORMAL, 0, (void *) 0, __m_outc
427				);
428
429			(void) tputs(clr_eol, 1, __m_outc);
430			__m_cc_erase(curscr, row, tail, row, COLS-1);
431		}
432	}
433
434	/* Line wrapping checks. */
435	if (COLS <= curscr->_curx) {
436		--curscr->_curx;
437		if (auto_right_margin && row < LINES-1) {
438			if (eat_newline_glitch) {
439				__m_outc('\r');
440				__m_outc('\n');
441			}
442			++curscr->_cury;
443			curscr->_curx = 0;
444		}
445	}
446}
447
448/*f
449 * Replace a block of lines.
450 * Only ever used for complex().
451 */
452STATIC void
453lines_replace(from, to_1)
454int from, to_1;
455{
456	for (; from < to_1; ++from)
457		text_replace(from);
458}
459
460/*f
461 * Delete a block of lines.
462 * Only ever used for complex().
463 */
464STATIC void
465lines_delete(from, to_1)
466int from, to_1;
467{
468	int count = to_1 - from;
469
470	if (LINES <= to_1) {
471		clear_bottom(from);
472	} else {
473		GOTO(from, 0);
474		(void) winsdelln(curscr, -count);
475
476		if (parm_delete_line != (char *) 0) {
477			/* Assume that the sequence to delete more than one
478			 * line is faster than repeated single delete_lines.
479			 */
480			(void) tputs(
481				tparm(
482					parm_delete_line, (long) count,
483					0, 0, 0, 0, 0, 0, 0, 0
484				), count, __m_outc
485			);
486		} else if (delete_line != (char *) 0) {
487			while (from++ < to_1)
488				(void) tputs(delete_line, 1, __m_outc);
489		} else  {
490			/* Error -- what to do. */
491			return;
492		}
493	}
494}
495
496/*f
497 * Insert a block of lines.
498 * Only ever used for complex().
499 *
500 * We must assume that insert_line and parm_insert_line reset the
501 * cursor column to zero.  Therefore it is text_replace() responsiblity
502 * to move the cursor to the correct column to begin the update.
503 */
504STATIC void
505lines_insert(from, to_1)
506int from, to_1;
507{
508	int row, count = to_1 - from;
509
510	/* Position the cursor and insert a block of lines into the screen
511	 * image now, insert lines into the physical screen, then draw the
512	 * new screen lines.
513	 */
514	GOTO(from, 0);
515	(void) winsdelln(curscr, count);
516
517	if (parm_insert_line != (char *) 0) {
518		/* Assume that the sequence to insert more than one line is
519		 * faster than repeated single insert_lines.
520		 */
521		(void) tputs(
522			tparm(
523				parm_insert_line, (long) count,
524				0, 0, 0, 0, 0, 0, 0, 0
525			), count, __m_outc
526		);
527	} else if (insert_line != (char *) 0) {
528		/* For the single line insert we use to iterate moving
529		 * the cursor, inserting, and then drawing a line.  That
530		 * would appear to be slow but visually appealing.  However,
531		 * people on slow terminals want speed and those on fast
532		 * terminal won't see it.
533		 */
534		for (row = from; row < to_1; ++row)
535			(void) tputs(insert_line, 1, __m_outc);
536	} else {
537		/* Error -- what to do. */
538		return;
539	}
540
541	for (row = from; row < to_1; ++row)
542		text_replace(row);
543}
544
545STATIC int
546scroll_up(n)
547int n;
548{
549	int count = n;
550	int start, finish, to, row;
551
552	if (scroll_forward != (char *) 0) {
553		GOTO(LINES-1, 0);
554		while (0 < n--)
555			(void) tputs(scroll_forward, 1, __m_outc);
556	} else if (parm_delete_line != (char *) 0 && 1 < n) {
557		GOTO(0, 0);
558		(void) tputs(
559			tparm(
560				parm_delete_line, (long) n,
561				0, 0, 0, 0, 0, 0, 0, 0
562			), n, __m_outc
563		);
564	} else if (delete_line != (char *) 0) {
565		GOTO(0, 0);
566		while (0 < n--)
567			(void) tputs(delete_line, 1, __m_outc);
568	} else {
569		return 0;
570	}
571
572	/* Scroll recorded image. */
573	start = 0;
574	finish = count-1;
575	to = lines;
576
577	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
578	(void) __m_ptr_move(
579		(void **) curscr->_line, curscr->_maxy, start, finish, to
580	);
581
582	simple();
583
584	return 1;
585}
586
587STATIC int
588scroll_dn(n)
589int n;
590{
591	int count = n;
592	int start, finish, to, row;
593
594	if (LINES < n)
595		return 0;
596
597	if (scroll_reverse != (char *) 0) {
598		GOTO(0, 0);
599		while (0 < n--)
600			(void) tputs(scroll_reverse, 1, __m_outc);
601	} else if (parm_insert_line != (char *) 0 && 1 < n) {
602		GOTO(0, 0);
603		(void) tputs(
604			tparm(
605				parm_insert_line, (long) n,
606				0, 0, 0, 0, 0, 0, 0, 0
607			), n, __m_outc
608		);
609	} else if (insert_line != (char *) 0) {
610		GOTO(0, 0);
611		while (0 < n--)
612			(void) tputs(insert_line, 1, __m_outc);
613	} else {
614		return 0;
615	}
616
617	/* Scroll recorded image. */
618	start = lines - count;
619	finish = lines - 1;
620	to = 0;
621
622	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
623	(void) __m_ptr_move(
624		(void **) curscr->_line, curscr->_maxy, start, finish, to
625	);
626
627	simple();
628
629	return 1;
630}
631
632#ifdef NEVER
633STATIC int
634is_same_line(old, new, count)
635cchar_t *old, *new;
636int count;
637{
638	while (0 < count--)
639		if (!__m_cc_compare(old, new, 1))
640			return 0;
641
642	return 1;
643}
644#endif /* NEVER */
645
646/*f
647 * Dynamic programming algorithm for the string edit problem.
648 *
649 * This is a modified Gosling cost algorithm that takes into account
650 * null/move operations.
651 *
652 * Costs for move, delete, replace, and insert are 0, 1, 2, and 3
653 * repectively.
654 */
655STATIC int
656cost(fr, lr)
657int fr, lr;
658{
659	register lcost *lcp;
660	register int or, nr, cc;
661	register unsigned long *ohash = __m_screen->_hash;
662	cchar_t **oline = curscr->_line;
663	cchar_t **nline = newscr->_line;
664	int linesz = COLS * sizeof **oline;
665
666	/* Prepare initial row and column of cost matrix.
667	 *
668	 *	0 3 6 9 ...
669	 *	1
670	 *	2
671	 *	3
672	 *	:
673	 */
674	LC(fr,fr).cost = 0;
675	for (cc = 1, ++lr, nr = fr+1; nr <= lr; ++nr, ++cc) {
676		/* Top row is 3, 6, 9, ... */
677		LC(fr,nr).cost = cc * 3;
678		LC(fr,nr).op = 'i';
679
680		/* Left column is 1, 2, 3, ... */
681		LC(nr,fr).cost = cc;
682		LC(nr,fr).op = 'd';
683	}
684
685	for (--lr, or = fr; or <= lr; ++or) {
686		for (nr = fr; nr <= lr; ++nr) {
687			lcp = &LC(or+1,nr+1);
688
689			/* Assume move op. */
690			lcp->cost = LC(or,nr).cost;
691			lcp->op = 'm';
692
693			if (ohash[or] != nhash[nr]
694#ifdef NEVER
695/* Should no longer require this code.  Using the POSIX 32-bit CRC to
696 * generate a hash value should be sufficient now, since text_replace()
697 * will compare the contents of a line and output only the dirty regions.
698 */
699			|| !is_same_line(oline[or], nline[nr], linesz)
700#endif
701			) {
702				/* Lines are different, assume replace op. */
703				lcp->cost += 2;
704				lcp->op = 'r';
705			}
706
707			/* Compare insert op. */
708			if ((cc = LC(or+1,nr).cost + 3) < lcp->cost) {
709				lcp->cost = cc;
710				lcp->op = 'i';
711			}
712
713			/* Compare delete op. */
714			if ((cc = LC(or,nr+1).cost + 1) < lcp->cost) {
715				lcp->cost = cc;
716				lcp->op = 'd';
717			}
718		}
719	}
720
721	return LC(lr+1,lr+1).cost;
722}
723
724/*f
725 * Build edit script.
726 *
727 * Normally this would be a recursve routine doing the deletes, inserts,
728 * and replaces on individual lines. Instead we build the script so that
729 * we can later do the operations on a block basis.  For terminals with
730 * parm_delete or parm_insert strings this will be better in terms of the
731 * number of characters sent to delete and insert a block of lines.
732 *
733 * Also we can optimize the script so that tail inserts become replaces.
734 * This saves unnecessary inserts operations when the tail can just be
735 * overwritten.
736 */
737STATIC void
738script(fr, lr)
739int fr, lr;
740{
741	int i, j;
742	cchar_t *cp;
743
744	i = j = lr + 1;
745
746	memset(del, 0, sizeof *del * LINES);
747	memset(ins_rep, 0, sizeof *ins_rep * LINES);
748
749	do {
750		/* We don't have to bounds check i or j becuase row fr and
751		 * column fr of lc have been preset in order to guarantee the
752		 * correct motion.
753		 */
754		switch (LC(i,j).op) {
755		case 'i':
756			--j;
757			ins_rep[j] = lines_insert;
758			break;
759		case 'd':
760			--i;
761			del[i] = lines_delete;
762			break;
763		case 'm':
764			--i;
765			--j;
766			break;
767		case 'r':
768			--i;
769			--j;
770			ins_rep[j] = lines_replace;
771			break;
772		}
773	} while (fr < i || fr < j);
774
775	/* Optimize Tail Inserts */
776	for (i = LINES-1; 0 <= i && ins_rep[i] == lines_insert; --i) {
777		/* Make each character in the screen line image invalid. */
778		for (cp = curscr->_line[i], j = 0; j < COLS; ++j, ++cp)
779			cp->_n = -1;
780		ins_rep[i] = lines_replace;
781	}
782}
783
784/*f
785 * Complex update algorithm using insert/delete line operations.
786 *
787 * References:
788 * [MyM86]	E.W. Myers & W. Miller, Row Replacement Algorithms for
789 *		Screen Editors, TR 86-19, Dept. Computer Science, U. of Arizona
790 * [MyM87]	E.W. Myers & W. Miller, A Simple Row Replacement Method,
791 *		TR 86-28, Dept. Computer Science, U. of Arizona
792 * [Mil87]	W. Miller, A Software Tools Sampler, Prentice-Hall, 1987
793 * [Gos81]	James Gosling, A redisplay algorithm, Proceedings of the
794 *		ACM Symposium on Text Manipulation, SIGPLAN Notices,
795 *		16(6) June 1981, pg 123-129
796 *
797 * All the above were reviewed and experimented with.  Due to the nature of
798 * Curses' having to handling overlapping WINDOWs, the only suitable
799 * algorithum is [Gos81].  The others are better suited to editor type
800 * applications that have one window being the entire terminal screen.
801 *
802 */
803STATIC void
804complex()
805{
806	int fr = -1;
807	int i, j, lr;
808	t_action func;
809
810	/* Find block of lines to change */
811	for (i = 0; i < LINES; ++i) {
812		if (newscr->_first[i] < newscr->_last[i]) {
813			/* Compute new hash. */
814			__m_cc_hash(newscr, nhash, i);
815			if (fr == -1)
816				fr = i;
817			lr = i;
818		} else {
819			/* Line not dirty so hash same as before. */
820			nhash[i] = __m_screen->_hash[i];
821		}
822	}
823
824	if (fr != -1) {
825		/* Gosling */
826		cost(fr, lr);
827		script(fr, lr);
828
829		/* Do deletes first in reverse order. */
830		for (j = lr; fr <= j; --j) {
831			if (del[j] != (t_action) 0) {
832				for (i = j-1; fr <= i; --i)
833					if (del[i] == (t_action) 0)
834						break;
835
836				lines_delete(i+1, j+1);
837				j = i;
838			}
839		}
840
841		/* Do insert/replace in forward order. */
842		for (i = fr; i <= lr; ++i) {
843			if ((func = ins_rep[i]) != (t_action) 0) {
844				/* Find size of block */
845				for (j = i; j <= lr && ins_rep[j] == func; ++j)
846					;
847				(*func)(i, j);
848				i = j-1;
849			}
850		}
851record:
852		/* _line[], which contains pointers to screen lines,
853		 * may be shuffled.
854		 */
855		for (i = fr; i <= lr; ++i) {
856			/* Save new hash for next update. */
857			__m_screen->_hash[i] = nhash[i];
858
859			/* Mark line as untouched. */
860			newscr->_first[i] = newscr->_maxx;
861			newscr->_last[i] = -1;
862		}
863	}
864}
865
866/*f
867 * Simple screen update algorithm
868 *
869 * We perform a simple incremental update of the terminal screen.
870 * Only the segment of a line that was touched is replaced on the
871 * line.
872 */
873STATIC void
874simple()
875{
876	int row;
877
878	for (row = 0; row < LINES; ++row) {
879		if (newscr->_first[row] < newscr->_last[row]) {
880			text_replace(row);
881
882			/* Mark line as untouched. */
883			newscr->_first[row] = newscr->_maxx;
884			newscr->_last[row] = -1;
885
886			if (__m_screen->_flags & S_INS_DEL_LINE)
887				__m_cc_hash(newscr, nhash, row);
888		}
889	}
890
891	newscr->_flags &= ~W_REDRAW_WINDOW;
892}
893
894/*f
895 * Send all changes made to _newscr to the physical terminal.
896 *
897 * If idlok() is set TRUE then doupdate will try and use hardware insert
898 * and delete line sequences in an effort to optimize output.  idlok()
899 * should really only be used in applications that want a proper scrolling
900 * effect.
901 *
902 * Added scroll heuristic to handle special case where a full size window
903 * with full size scroll region, will scroll the window and replace dirty
904 * lines instead of performing usual cost/script operations.
905 */
906int
907doupdate()
908{
909#ifdef SIGTSTP
910	int (*oldsig)(int) = signal(SIGTSTP, SIG_IGN);
911#endif
912
913#ifdef M_CURSES_TYPEAHEAD
914	unsigned char cc;
915	volatile int min, time, icanon;
916
917	if (__m_screen->_flags & S_ISATTY) {
918		/* Set up non-blocking input for typeahead trapping. */
919		min = cur_term->_prog.c_cc[VMIN];
920		time = cur_term->_prog.c_cc[VTIME];
921		icanon = cur_term->_prog.c_lflag & ICANON;
922
923		cur_term->_prog.c_cc[VMIN] = 0;
924		cur_term->_prog.c_cc[VTIME] = 0;
925		cur_term->_prog.c_lflag &= ~ICANON;
926
927		(void) tcsetattr(__m_screen->_kfd, TCSANOW, &cur_term->_prog);
928	}
929#endif /* M_CURSES_TYPEAHEAD */
930
931#ifdef M_CURSES_TRACE
932	__m_trace(
933		"doupdate(void) using %s algorithm.",
934		(__m_screen->_flags & S_INS_DEL_LINE) ? "complex" : "simple"
935	);
936#endif
937
938	newscr = __m_screen->_newscr;
939
940	if (__m_screen->_flags & S_ENDWIN) {
941		/* Return from temporary escape done with endwin(). */
942		__m_screen->_flags &= ~S_ENDWIN;
943
944		(void) reset_prog_mode();
945		if (enter_ca_mode != (char *) 0)
946			(void) tputs(enter_ca_mode, 1, __m_outc);
947		if (keypad_xmit != (char *) 0)
948			(void) tputs(keypad_xmit, 1, __m_outc);
949		if (ena_acs != (char *) 0)
950			(void) tputs(ena_acs, 1, __m_outc);
951
952		/* Force redraw of screen. */
953		newscr->_flags |= W_CLEAR_WINDOW;
954	}
955
956#ifdef M_CURSES_TYPEAHEAD
957	if (setjmp(breakout) == 0) {
958		if ((__m_screen->_flags & S_ISATTY)
959		&& read(__m_screen->_kfd, &cc, sizeof cc) == sizeof cc) {
960			(void) ungetch(cc);
961			longjmp(breakout, 1);
962		}
963#endif /* M_CURSES_TYPEAHEAD */
964
965		/* When redrawwing a window, we not only assume that line
966		 * noise may have lost characters, but line noise may have
967		 * generated bogus characters on the screen outside the
968		 * the window in question, in which case redraw the entire
969		 * screen to be sure.
970		 */
971		if (newscr->_flags & (W_CLEAR_WINDOW | W_REDRAW_WINDOW)) {
972			clear_bottom(0);
973			newscr->_flags &= ~W_CLEAR_WINDOW;
974			(void) wtouchln(newscr, 0, newscr->_maxy, 1);
975		}
976
977		if (newscr->_flags & W_REDRAW_WINDOW)
978			simple();
979#if 0		/* This first expression, of undefined section, is useless
980		 * since newscr->_scroll is unsigned and never LT zero.
981		 */
982		else if (newscr->_scroll < 0 && scroll_dn(-newscr->_scroll))
983#else
984		else if (scroll_dn(-newscr->_scroll))
985#endif
986			;
987		else if (0 < newscr->_scroll && scroll_up(newscr->_scroll))
988			;
989		else if (__m_screen->_flags & S_INS_DEL_LINE)
990			complex();
991		else
992			simple();
993
994		if (!(newscr->_flags & W_LEAVE_CURSOR))
995			GOTO(newscr->_cury, newscr->_curx);
996
997		if (!(curscr->_flags & W_FLUSH))
998			(void) fflush(__m_screen->_of);
999#ifdef M_CURSES_TYPEAHEAD
1000	}
1001
1002	if (__m_screen->_flags & S_ISATTY) {
1003		/* Restore previous input mode. */
1004		cur_term->_prog.c_cc[VMIN] = min;
1005		cur_term->_prog.c_cc[VTIME] = time;
1006		cur_term->_prog.c_lflag |= icanon;
1007
1008		(void) tcsetattr(__m_screen->_kfd,TCSANOW,&cur_term->_prog);
1009	}
1010#endif /* M_CURSES_TYPEAHEAD */
1011
1012	newscr->_scroll = curscr->_scroll = 0;
1013#ifdef SIGTSTP
1014	signal(SIGTSTP, oldsig);
1015#endif
1016
1017	return __m_return_code("doupdate", OK);
1018}
1019
1020/*
1021 * If true, the implementation may use hardware insert and delete,
1022 * character features of the terminal.  The window parameter
1023 * is ignored.
1024 */
1025void
1026idcok(WINDOW *w, bool bf)
1027{
1028#ifdef M_CURSES_TRACE
1029	__m_trace("idcok(%p, %d)", w, bf);
1030#endif
1031
1032	__m_screen->_flags &= ~S_INS_DEL_CHAR;
1033	if (bf)
1034		__m_screen->_flags |= S_INS_DEL_CHAR;
1035
1036	__m_return_void("idcok");
1037}
1038
1039/*
1040 * If true, the implementation may use hardware insert, delete,
1041 * and scroll line features of the terminal.  The window parameter
1042 * is ignored.
1043 */
1044int
1045idlok(WINDOW *w, bool bf)
1046{
1047#ifdef M_CURSES_TRACE
1048	__m_trace("idlok(%p, %d)", w, bf);
1049#endif
1050
1051	__m_screen->_flags &= ~S_INS_DEL_LINE;
1052	if (bf && has_il())
1053		__m_screen->_flags |= S_INS_DEL_LINE;
1054
1055	return __m_return_code("idlok", OK);
1056}
1057
1058/*
1059 * Use the POSIX 32-bit CRC function to compute a hash value
1060 * for the window line.
1061 */
1062void
1063__m_cc_hash(w, array, y)
1064WINDOW *w;
1065unsigned long *array;
1066int y;
1067{
1068	array[y] = 0;
1069	m_crcposix(
1070		&array[y], (unsigned char *) w->_line[y],
1071		(size_t) (w->_maxx * sizeof **w->_line)
1072	);
1073}
1074
1075
1076