xref: /titanic_41/usr/src/lib/libxcurses/src/libc/xcurses/doupdate.c (revision 16222dda8ab79e59a26e1a5f6c4f627c0c53508a)
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
39 static 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 
74 typedef struct cost_op {
75 	short cost;
76 	short op;
77 } lcost;
78 
79 typedef void (*t_action)(int, int);
80 
81 static jmp_buf breakout;
82 
83 #define LC(i,j) 	(lc[(i) * (LINES + 1) + (j)])
84 
85 static lcost *lc = (lcost *) 0;
86 static unsigned long *nhash = (unsigned long *) 0;
87 static t_action *del = (t_action *) 0;
88 static t_action *ins_rep = (t_action *) 0;
89 
90 static WINDOW *newscr;
91 
92 STATIC void erase_bottom(int);
93 STATIC void clear_bottom(int);
94 STATIC void complex(void);
95 STATIC int cost(int, int);
96 STATIC void lines_delete(int, int);
97 STATIC void lines_insert(int, int);
98 STATIC void lines_replace(int, int);
99 STATIC void script(int, int);
100 STATIC int scroll_dn(int);
101 STATIC int scroll_up(int);
102 STATIC void simple(void);
103 STATIC void text_replace(int);
104 STATIC 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  */
112 int
__m_outc(ch)113 __m_outc(ch)
114 int ch;
115 {
116         return putc(ch, __m_screen->_of);
117 }
118 
119 /*
120  * Allocate or grow doupdate() structures.
121  */
122 int
__m_doupdate_init()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 
161 STATIC void
erase_bottom(y)162 erase_bottom(y)
163 int 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  */
176 STATIC void
clear_bottom(y)177 clear_bottom(y)
178 int 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  */
229 STATIC void
text_replace(row)230 text_replace(row)
231 int 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--)) {
322 write_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 	}
393 done:
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  */
452 STATIC void
lines_replace(from,to_1)453 lines_replace(from, to_1)
454 int 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  */
464 STATIC void
lines_delete(from,to_1)465 lines_delete(from, to_1)
466 int 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  */
504 STATIC void
lines_insert(from,to_1)505 lines_insert(from, to_1)
506 int 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 
545 STATIC int
scroll_up(n)546 scroll_up(n)
547 int 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 
587 STATIC int
scroll_dn(n)588 scroll_dn(n)
589 int 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
633 STATIC int
is_same_line(old,new,count)634 is_same_line(old, new, count)
635 cchar_t *old, *new;
636 int 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  */
655 STATIC int
cost(fr,lr)656 cost(fr, lr)
657 int 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  */
737 STATIC void
script(fr,lr)738 script(fr, lr)
739 int 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  */
803 STATIC void
complex()804 complex()
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 		}
851 record:
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  */
873 STATIC void
simple()874 simple()
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  */
906 int
doupdate()907 doupdate()
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  */
1025 void
idcok(WINDOW * w,bool bf)1026 idcok(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  */
1044 int
idlok(WINDOW * w,bool bf)1045 idlok(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  */
1062 void
__m_cc_hash(w,array,y)1063 __m_cc_hash(w, array, y)
1064 WINDOW *w;
1065 unsigned long *array;
1066 int 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