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 (c) 1995-1999 by Sun Microsystems, Inc.
24  * All rights reserved.
25  */
26 
27 #pragma ident	"%Z%%M%	%I%	%E% SMI"
28 
29 /* LINTLIBRARY */
30 
31 /*
32  * doupdate.c
33  *
34  * XCurses Library
35  *
36  * Copyright 1990, 1995 by Mortice Kern Systems Inc.  All rights reserved.
37  *
38  */
39 
40 #ifdef M_RCSID
41 #ifndef lint
42 static char const rcsID[] =
43 "$Header: /team/ps/sun_xcurses/archive/local_changes/xcurses/src/lib/"
44 "libxcurses/src/libc/xcurses/rcs/doupdate.c 1.22 1998/06/04 12:13:38 "
45 "cbates Exp $";
46 #endif
47 #endif
48 
49 #include <sys/isa_defs.h>
50 #include <private.h>
51 #include <string.h>
52 #include <signal.h>
53 
54 #undef SIGTSTP
55 
56 /*
57  * This value is the ideal length for the cursor addressing sequence
58  * being four bytes long, ie. "<escape><cursor addressing code><row><col>".
59  * eg. VT52 - "\EYrc" or ADM3A - "\E=rc"
60  */
61 #define	JUMP_SIZE	4
62 
63 /*
64  * This value is the ideal length for the clear-to-eol sequence
65  * being two bytes long, ie "<escape><clear eol code>".
66  */
67 #define	CEOL_SIZE	2
68 
69 #define	GOTO(r, c)	((void) __m_mvcur(curscr->_cury, curscr->_curx,\
70 	r, c, __m_outc), curscr->_cury = r, curscr->_curx = c)
71 
72 typedef struct cost_op {
73 	short	cost;
74 	short	op;
75 } lcost;
76 
77 typedef void (*t_action)(int, int);
78 
79 
80 #define	LC(i, j) 	(lc[(i) * (LINES + 1) + (j)])
81 
82 static lcost *lc = NULL;
83 #if defined(_LP64)
84 static unsigned int	*nhash = NULL;
85 #else
86 static unsigned long	*nhash = NULL;
87 #endif
88 static t_action *del = NULL;
89 static t_action *ins_rep = NULL;
90 
91 static WINDOW	*newscr;
92 
93 static void erase_bottom(int, int);
94 static void clear_bottom(int);
95 static void complex(void);
96 static int cost(int, int);
97 static void lines_delete(int, int);
98 static void lines_insert(int, int);
99 static void lines_replace(int, int);
100 static void script(int, int);
101 static int scroll_up(int);
102 static void simple(void);
103 static void text_replace(int);
104 #if 0
105 static int scroll_dn(int);
106 #endif
107 
108 
109 /*
110  * Wrapper that streams Curses output.
111  *
112  * All escape sequences going to the screen come through here.
113  * All ordinary characters go to the screen via the putc in doupdate.c
114  */
115 int
__m_outc(int ch)116 __m_outc(int ch)
117 {
118 	return (putc(ch, __m_screen->_of));
119 }
120 
121 /*
122  * Allocate or grow doupdate() structures.
123  */
124 int
__m_doupdate_init(void)125 __m_doupdate_init(void)
126 {
127 	void	*new;
128 	static short	nlines = 0;
129 
130 	if (lines <= 0)
131 		return (-1);
132 
133 	if (lines <= nlines)
134 		return (0);
135 
136 	new = malloc((lines + 1) * (lines + 1) * sizeof (*lc));
137 	if (new == NULL)
138 		return (-1);
139 	if (lc != NULL)
140 		free(lc);
141 	lc = (lcost *) new;
142 
143 	new = malloc((lines + lines) * sizeof (*del));
144 	if (new == NULL)
145 		return (-1);
146 	if (del != NULL)
147 		free(del);
148 	del = (t_action *) new;
149 	ins_rep = del + lines;
150 
151 	new = malloc(lines * sizeof (*nhash));
152 	if (new == NULL)
153 		return (-1);
154 	if (nhash != NULL)
155 		free(nhash);
156 #if defined(_LP64)
157 	nhash = (unsigned int *) new;
158 #else
159 	nhash = (unsigned long *) new;
160 #endif
161 
162 	nlines = lines;
163 
164 	return (0);
165 }
166 
167 static void
erase_bottom(int start,int end)168 erase_bottom(int start, int end)
169 {
170 	int i;
171 
172 	for (i = start; i < end; ++i) {
173 		(void) __m_cc_erase(curscr, i, 0, i, curscr->_maxx - 1);
174 		__m_cc_hash(curscr, __m_screen->_hash, i);
175 	}
176 }
177 
178 /*
179  *  Clear from the start of the current row to bottom of screen.
180  */
181 static void
clear_bottom(int y)182 clear_bottom(int y)
183 {
184 	/* Restore default color pair before doing area clears. */
185 	if (back_color_erase)
186 		(void) vid_puts(WA_NORMAL, 0, (void *) 0, __m_outc);
187 
188 	if (y == 0 && clear_screen != NULL) {
189 		(void) TPUTS(clear_screen, 1, __m_outc);
190 	} else {
191 		(void) __m_mvcur(-1, -1, y, 0, __m_outc);
192 		if (clr_eos != NULL) {
193 			(void) TPUTS(clr_eos, 1, __m_outc);
194 		} else if (clr_eol != NULL) {
195 			for (;;) {
196 				(void) TPUTS(clr_eol, 1, __m_outc);
197 				if (LINES <= y)
198 					break;
199 				(void) __m_mvcur(y, 0, y + 1, 0, __m_outc);
200 				++y;
201 			}
202 		}
203 	}
204 
205 	curscr->_cury = y;
206 	curscr->_curx = 0;
207 }
208 
209 
210 
211 /*
212  * Rewrite of text_replace() implementation by C. Bates of MKS
213  *
214  * This code creates a list of 'regions' for each test line which
215  * is to be replaced. Each region describes a portion of the line.
216  * Logic is performed on the list of regions, then the regions
217  * are used to generate output.
218  */
219 typedef	struct LineRegion {
220 	int	col;	/* Starting column of region */
221 	int	size;	/* Size of region */
222 	/* 0: Difference Region, 1: Common Region, 2: Delete Region */
223 	int	type;
224 } LineRegion;
225 #define	REGION_DIFFERENT	0
226 #define	REGION_COMMON		1
227 #define	REGION_DELETE		2
228 
229 #define	DELETE_SEARCH_LIMIT	4
230 #define	DELETE_THRESHOLD	10
231 
232 static LineRegion	regions[1024];
233 int	nRegions = 0;
234 
235 /*
236  * Return the first column of the completely blank End-of-line
237  */
238 static int
_find_blank_tail(int row)239 _find_blank_tail(int row)
240 {
241 	cchar_t	*nptr;
242 	int	tail = COLS;
243 
244 	if (!clr_eol)
245 		return (COLS);
246 	/*
247 	 * Find start of blank tail region.
248 	 */
249 	nptr = &newscr->_line[row][COLS];
250 	for (; 0 < tail; --tail) {
251 		if (!__m_cc_compare(--nptr, &newscr->_bg, 1))
252 			break;
253 	}
254 	return (tail);
255 }
256 
257 /*
258  * Send all the characters in the region to the terminal
259  */
260 static void
_writeRegion(int row,LineRegion region)261 _writeRegion(int row, LineRegion region)
262 {
263 	short	npair;
264 	attr_t	nattr;
265 	int	i;
266 	cchar_t	*optr = &curscr->_line[row][region.col];
267 	cchar_t	*nptr = &newscr->_line[row][region.col];
268 
269 	for (i = 0; i < region.size; i++, nptr++, optr++) {
270 		nattr = nptr->_at;
271 		npair = nptr->_co;
272 
273 		/*
274 		 * Change attribute state.
275 		 */
276 		if ((ATTR_STATE != nattr) || (optr->_at != nattr) ||
277 			(cur_term->_co != npair)) {
278 			(void) vid_puts(nattr, npair, NULL, __m_outc);
279 		}
280 		/*
281 		 * Don't display internal characters.
282 		 */
283 		if (nptr->_f)
284 			(void) __m_cc_write(nptr);
285 
286 		/*
287 		 * Update copy of screen image.
288 		 */
289 		*optr = *nptr;
290 		curscr->_curx = region.col + i + 1;
291 	}
292 }
293 
294 /*
295  * Delete some characters from the terminal for this region
296  */
297 static void
_deleteRegion(int row,LineRegion region)298 _deleteRegion(int row, LineRegion region)
299 {
300 	int	i;
301 	cchar_t	*optr = &curscr->_line[row][region.col];
302 
303 	if ((region.size <= 1) || !parm_dch) {
304 		for (i = 0; i < region.size; i++)
305 			(void) TPUTS(delete_character, 1, __m_outc);
306 	} else {
307 		(void) TPUTS(tparm(parm_dch, (long)region.size,
308 			0, 0, 0, 0, 0, 0, 0, 0), region.size, __m_outc);
309 	}
310 	for (i = region.col; i < COLS - region.size; i++) {
311 		/*
312 		 * Delete the chars in the image of the real screen
313 		 */
314 		*optr = *(optr + region.size);
315 		optr++;
316 	}
317 }
318 
319 /*
320  * Use clr_eol control if possible
321  */
322 static void
_clearToEOL(int row,int tail)323 _clearToEOL(int row, int tail)
324 {
325 	if (tail < COLS) {
326 		GOTO(row, tail);
327 		/*
328 		 * Restore default color pair before area clear.
329 		 */
330 		if (back_color_erase)
331 			(void) vid_puts(WA_NORMAL, 0, NULL, __m_outc);
332 
333 		(void) TPUTS(clr_eol, 1, __m_outc);
334 		(void) __m_cc_erase(curscr, row, tail, row, COLS - 1);
335 	}
336 }
337 
338 /*
339  * Delete leading common region
340  */
341 static void
_normalizeRegions1(void)342 _normalizeRegions1(void)
343 {
344 	int	iRegion;
345 
346 	/*
347 	 * Delete leading common region
348 	 */
349 	if (regions[0].type == REGION_COMMON) {
350 		nRegions--;
351 		for (iRegion = 0; iRegion < nRegions; iRegion++) {
352 			regions[iRegion] = regions[iRegion + 1];
353 		}
354 	}
355 }
356 
357 /*
358  * Give each region a size, then delete all trailing common regions
359  */
360 static void
_normalizeRegions2(void)361 _normalizeRegions2(void)
362 {
363 	int	iRegion;
364 
365 	for (iRegion = 0; iRegion < nRegions - 1; iRegion++) {
366 		regions[iRegion].size = regions[iRegion + 1].col -
367 			regions[iRegion].col;
368 	}
369 	regions[nRegions - 1].size = COLS - regions[nRegions - 1].col;
370 
371 	/*
372 	 * Delete trailing common regions
373 	 */
374 	while (regions[nRegions - 1].type == REGION_COMMON)
375 		nRegions--;
376 }
377 
378 /*
379  * Tiny common regions are merged into adjacent difference regions
380  */
381 static void
_mergeTinyRegions(void)382 _mergeTinyRegions(void)
383 {
384 	int	from;
385 	int	to;
386 	for (from = 1, to = 1; from < nRegions; ) {
387 		if ((regions[from].type == REGION_COMMON) &&
388 			(regions[from].size < JUMP_SIZE)) {
389 			/*
390 			 * Merge out tiny common regions
391 			 */
392 			regions[to - 1].size += regions[from].size;
393 			/*
394 			 * Now join adjacent non-common regions
395 			 */
396 			if (++from < nRegions)
397 				regions[to - 1].size += regions[from++].size;
398 		} else {
399 			regions[to++] = regions[from++];
400 		}
401 	}
402 	nRegions = to;
403 }
404 
405 /*
406  * Create the initial list of regions for this row
407  */
408 static int
_findRegions(int row)409 _findRegions(int row)
410 {
411 	int	cmp;
412 	int	old_cmp;
413 	int	col;
414 	int	bestDeleteCount;
415 	cchar_t	*nptr = &newscr->_line[row][0];
416 	cchar_t	*optr = &curscr->_line[row][0];
417 
418 	col = 0;
419 	nRegions = 0;
420 	bestDeleteCount = 0;
421 	if ((__m_screen->_flags & S_INS_DEL_CHAR) &&
422 		(parm_dch || delete_character)) {
423 		int	bestFit = 0;
424 		int	deletePoint;
425 		int	deleteCount;
426 		int	matches;
427 
428 		/*
429 		 * Skip to first difference
430 		 */
431 		for (col = 0; col < COLS; col++) {
432 			if (!__m_cc_compare(&optr[col], &nptr[col], 1))
433 				break;
434 		}
435 		deletePoint = col;
436 		for (deleteCount = 1; deleteCount < DELETE_SEARCH_LIMIT;
437 			deleteCount++) {
438 			matches = 0;
439 			for (col = deletePoint; col < COLS - deleteCount;
440 				col++) {
441 				if (__m_cc_compare(&optr[col + deleteCount],
442 					&nptr[col], 1))
443 					matches++;
444 				else
445 					break;
446 			}
447 			if (matches > bestFit) {
448 				bestFit = matches;
449 				bestDeleteCount = deleteCount;
450 			}
451 		}
452 		if (bestFit > DELETE_THRESHOLD) {
453 			regions[nRegions].type = REGION_DELETE;
454 			regions[nRegions].col = deletePoint;
455 			regions[nRegions].size = bestDeleteCount;
456 			nRegions++;
457 			col = deletePoint + bestDeleteCount;
458 		} else {
459 			col = 0;
460 			nRegions = 0;
461 			/* Forget trying to use character delete */
462 			bestDeleteCount = 0;
463 		}
464 	}
465 	for (old_cmp = -1; col + bestDeleteCount < COLS; col++) {
466 		cmp = __m_cc_compare(&optr[col + bestDeleteCount],
467 			&nptr[col], 1);
468 		if (cmp != old_cmp) {
469 			regions[nRegions].type = cmp ? REGION_COMMON :
470 				REGION_DIFFERENT;
471 			regions[nRegions].col = col;
472 			regions[nRegions].size = 0;	/* Determine later */
473 			nRegions++;
474 			old_cmp = cmp;
475 		}
476 	}
477 	if (bestDeleteCount) {
478 		/*
479 		 * Force update of end-of-line if delete is to be used
480 		 */
481 		regions[nRegions].type = REGION_DIFFERENT;
482 		regions[nRegions].col = col;
483 		regions[nRegions].size = 0;	/* Determine later */
484 		nRegions++;
485 	}
486 	_normalizeRegions1();
487 	if (nRegions == 0)
488 		return (0);		/* No difference regions */
489 
490 	_normalizeRegions2();
491 	return (1);
492 }
493 
494 /*
495  * Determine if Clr-EOL optimization can be used, and
496  * adjust regions accordingly
497  */
498 static int
_ceolAdjustRegions(int row)499 _ceolAdjustRegions(int row)
500 {
501 	int	iRegion;
502 	int	blankEolStart = _find_blank_tail(row);
503 
504 	for (iRegion = 0; iRegion < nRegions; iRegion++) {
505 		switch (regions[iRegion].type) {
506 		case REGION_DIFFERENT:
507 			if (regions[iRegion].col >= blankEolStart) {
508 				/*
509 				 * Delete this and all following regions
510 				 */
511 				nRegions = iRegion;
512 				return (blankEolStart);
513 			}
514 			if (regions[iRegion].col + regions[iRegion].size >
515 				blankEolStart) {
516 				/*
517 				 * Truncate this region to end
518 				 * where blank EOL starts
519 				 */
520 				regions[iRegion].size = blankEolStart -
521 					regions[iRegion].col;
522 				/*
523 				 * Delete all following regions
524 				 */
525 				nRegions = iRegion + 1;
526 				return (blankEolStart);
527 			}
528 			break;
529 		case REGION_COMMON:
530 			break;
531 		case REGION_DELETE:		/* Scrap the whole thing */
532 			return (COLS);
533 		}
534 	}
535 	return (COLS);	/* Couldn't use Clear EOL optimization */
536 }
537 
538 /*
539  * Generate output, based on region list
540  */
541 static void
_updateRegions(int row)542 _updateRegions(int row)
543 {
544 	int	ceolStart;
545 	int	iRegion;
546 
547 	ceolStart = _ceolAdjustRegions(row);
548 
549 	/*
550 	 * regions are guaranteed to start with a non-common region.
551 	 * tiny common regions have also been merged into
552 	 * bracketting common-regions.
553 	 */
554 	if (nRegions) {
555 		for (iRegion = 0; iRegion < nRegions; iRegion++) {
556 			switch (regions[iRegion].type) {
557 			case REGION_COMMON:
558 				break;
559 			case REGION_DELETE:
560 				/*
561 				 * Start of non-common region
562 				 */
563 				GOTO(row, regions[iRegion].col);
564 				_deleteRegion(row, regions[iRegion]);
565 				break;
566 			case REGION_DIFFERENT:
567 				/*
568 				 * Star of non-common region
569 				 */
570 				GOTO(row, regions[iRegion].col);
571 				_writeRegion(row, regions[iRegion]);
572 				break;
573 			}
574 		}
575 	}
576 	if (ceolStart != COLS) {
577 		_clearToEOL(row, ceolStart);
578 	}
579 }
580 
581 /*
582  * The new text_replace algorithm, which uses regions
583  */
584 static void
text_replace(int row)585 text_replace(int row)
586 {
587 	if (!_findRegions(row))
588 		return;
589 	_mergeTinyRegions();
590 	_updateRegions(row);
591 
592 	/*
593 	 * Line wrapping checks.
594 	 */
595 	if (COLS <= curscr->_curx) {
596 		--curscr->_curx;
597 		if (auto_right_margin && (row < LINES - 1)) {
598 			if (eat_newline_glitch) {
599 				(void) __m_outc('\r');
600 				(void) __m_outc('\n');
601 			}
602 			++curscr->_cury;
603 			curscr->_curx = 0;
604 		}
605 	}
606 }
607 
608 /*
609  * Replace a block of lines.
610  * Only ever used for complex().
611  */
612 static void
lines_replace(int from,int to_1)613 lines_replace(int from, int to_1)
614 {
615 	for (; from < to_1; ++from)
616 		text_replace(from);
617 }
618 
619 /*
620  * Delete a block of lines.
621  * Only ever used for complex().
622  */
623 static void
lines_delete(int from,int to_1)624 lines_delete(int from, int to_1)
625 {
626 	int count = to_1 - from;
627 
628 	if (LINES <= to_1) {
629 		erase_bottom(from, LINES);
630 		clear_bottom(from);
631 	} else {
632 		GOTO(from, 0);
633 		(void) winsdelln(curscr, -count);
634 
635 		if (parm_delete_line != NULL) {
636 			/*
637 			 * Assume that the sequence to delete more than one
638 			 * line is faster than repeated single delete_lines.
639 			 */
640 			(void) TPUTS(tparm(parm_delete_line, (long)count,
641 				0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc);
642 		} else if (delete_line != NULL) {
643 			while (from++ < to_1)
644 				(void) TPUTS(delete_line, 1, __m_outc);
645 		} else  {
646 			/* Error -- what to do. */
647 			return;
648 		}
649 	}
650 }
651 
652 /*
653  * Insert a block of lines.
654  * Only ever used for complex().
655  *
656  * We must assume that insert_line and parm_insert_line reset the
657  * cursor column to zero.  Therefore it is text_replace() responsiblity
658  * to move the cursor to the correct column to begin the update.
659  */
660 static void
lines_insert(int from,int to_1)661 lines_insert(int from, int to_1)
662 {
663 	int	row;
664 	int	count = to_1 - from;
665 
666 	/*
667 	 * Position the cursor and insert a block of lines into the screen
668 	 * image now, insert lines into the physical screen, then draw the
669 	 * new screen lines.
670 	 */
671 	GOTO(from, 0);
672 	(void) winsdelln(curscr, count);
673 
674 	if (parm_insert_line != NULL) {
675 		/*
676 		 * Assume that the sequence to insert more than one line is
677 		 * faster than repeated single insert_lines.
678 		 */
679 		(void) TPUTS(tparm(parm_insert_line, (long)count,
680 			0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc);
681 	} else if (insert_line != NULL) {
682 		/*
683 		 * For the single line insert we use to iterate moving
684 		 * the cursor, inserting, and then drawing a line.  That
685 		 * would appear to be slow but visually appealing.  However,
686 		 * people on slow terminals want speed and those on fast
687 		 * terminal won't see it.
688 		 */
689 		for (row = from; row < to_1; ++row)
690 			(void) TPUTS(insert_line, 1, __m_outc);
691 	} else {
692 		/* Error -- what to do. */
693 		return;
694 	}
695 
696 	for (row = from; row < to_1; ++row)
697 		text_replace(row);
698 }
699 
700 static int
scroll_up(int n)701 scroll_up(int n)
702 {
703 	int	count = n;
704 	int	start, finish, to;
705 
706 	if (scroll_forward != NULL) {
707 		GOTO(LINES-1, 0);
708 		while (0 < n--)
709 			(void) TPUTS(scroll_forward, 1, __m_outc);
710 	} else if (parm_delete_line != NULL && 1 < n) {
711 		GOTO(0, 0);
712 		(void) TPUTS(tparm(parm_delete_line, (long)n,
713 			0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc);
714 	} else if (delete_line != NULL) {
715 		GOTO(0, 0);
716 		while (0 < n--)
717 			(void) TPUTS(delete_line, 1, __m_outc);
718 	} else {
719 		return (0);
720 	}
721 
722 	/* Scroll recorded image. */
723 	start = 0;
724 	finish = count-1;
725 	to = lines;
726 
727 	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
728 	(void) __m_ptr_move((void **) curscr->_line,
729 		curscr->_maxy, start, finish, to);
730 
731 	simple();
732 
733 	return (1);
734 }
735 
736 #if 0
737 static int
738 scroll_dn(int n)
739 {
740 	int	count = n;
741 	int	start, finish, to;
742 
743 	if (LINES < n)
744 		return (0);
745 
746 	if (scroll_reverse != NULL) {
747 		GOTO(0, 0);
748 		while (0 < n--)
749 			(void) TPUTS(scroll_reverse, 1, __m_outc);
750 	} else if (parm_insert_line != NULL && 1 < n) {
751 		GOTO(0, 0);
752 		(void) TPUTS(tparm(parm_insert_line, (long)n,
753 			0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc);
754 	} else if (insert_line != NULL) {
755 		GOTO(0, 0);
756 		while (0 < n--)
757 			(void) TPUTS(insert_line, 1, __m_outc);
758 	} else {
759 		return (0);
760 	}
761 
762 	/* Scroll recorded image. */
763 	start = lines - count;
764 	finish = lines - 1;
765 	to = 0;
766 
767 	(void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1);
768 	(void) __m_ptr_move((void **) curscr->_line,
769 		curscr->_maxy, start, finish, to);
770 
771 	simple();
772 
773 	return (1);
774 }
775 #endif
776 
777 /*
778  * Dynamic programming algorithm for the string edit problem.
779  *
780  * This is a modified Gosling cost algorithm that takes into account
781  * null/move operations.
782  *
783  * Costs for move, delete, replace, and insert are 0, 1, 2, and 3
784  * repectively.
785  */
786 #define	MOVE_COST	0
787 #define	REPLACE_COST	10
788 #define	INSERT_COST	12
789 #define	DELETE_COST	1
790 
791 static int
cost(int fr,int lr)792 cost(int fr, int lr)
793 {
794 	lcost	*lcp;
795 	int	or, nr, cc;
796 #if defined(_LP64)
797 	unsigned int	*ohash = __m_screen->_hash;
798 #else
799 	unsigned long	*ohash = __m_screen->_hash;
800 #endif
801 
802 	/*
803 	 * Prepare initial row and column of cost matrix.
804 	 *
805 	 *	0 3 6 9 ...
806 	 *	1
807 	 *	2
808 	 *	3
809 	 *	:
810 	 */
811 	LC(fr, fr).cost = MOVE_COST;
812 	for (cc = 1, ++lr, nr = fr+1; nr <= lr; ++nr, ++cc) {
813 		/* Top row is 3, 6, 9, ... */
814 		LC(fr, nr).cost = cc * INSERT_COST;
815 		LC(fr, nr).op = 'i';
816 
817 		/* Left column is 1, 2, 3, ... */
818 		LC(nr, fr).cost = cc * DELETE_COST;
819 		LC(nr, fr).op = 'd';
820 	}
821 
822 	for (--lr, or = fr; or <= lr; ++or) {
823 		for (nr = fr; nr <= lr; ++nr) {
824 			lcp = &LC(or + 1, nr + 1);
825 
826 			/* Assume move op. */
827 			lcp->cost = LC(or, nr).cost;
828 			lcp->op = 'm';
829 
830 			if (ohash[or] != nhash[nr]) {
831 				/* Lines are different, assume replace op. */
832 				lcp->cost += REPLACE_COST;
833 				lcp->op = 'r';
834 			}
835 
836 			/* Compare insert op. */
837 			if ((cc = LC(or + 1, nr).cost + INSERT_COST) <
838 				lcp->cost) {
839 				lcp->cost = cc;
840 				lcp->op = 'i';
841 			}
842 
843 			/* Compare delete op. */
844 			if ((cc = LC(or, nr + 1).cost + DELETE_COST) <
845 				lcp->cost) {
846 				lcp->cost = cc;
847 				lcp->op = 'd';
848 			}
849 		}
850 	}
851 
852 	return (LC(lr + 1, lr + 1).cost);
853 }
854 
855 /*
856  * Build edit script.
857  *
858  * Normally this would be a recursve routine doing the deletes, inserts,
859  * and replaces on individual lines. Instead we build the script so that
860  * we can later do the operations on a block basis.  For terminals with
861  * parm_delete or parm_insert strings this will be better in terms of the
862  * number of characters sent to delete and insert a block of lines.
863  *
864  * Also we can optimize the script so that tail inserts become replaces.
865  * This saves unnecessary inserts operations when the tail can just be
866  * overwritten.
867  */
868 static void
script(int fr,int lr)869 script(int fr, int lr)
870 {
871 	int	i, j;
872 	cchar_t	*cp;
873 
874 	i = j = lr + 1;
875 
876 	(void) memset(del, 0, sizeof (*del) * LINES);
877 	(void) memset(ins_rep, 0, sizeof (*ins_rep) * LINES);
878 
879 	do {
880 		/*
881 		 * We don't have to bounds check i or j becuase row fr and
882 		 * column fr of lc have been preset in order to guarantee the
883 		 * correct motion.
884 		 */
885 		switch (LC(i, j).op) {
886 		case 'i':
887 			--j;
888 			ins_rep[j] = lines_insert;
889 			break;
890 		case 'd':
891 			--i;
892 			del[i] = lines_delete;
893 			break;
894 		case 'm':
895 			--i;
896 			--j;
897 			break;
898 		case 'r':
899 			--i;
900 			--j;
901 			ins_rep[j] = lines_replace;
902 			break;
903 		}
904 	} while (fr < i || fr < j);
905 
906 	/* Optimize Tail Inserts */
907 	for (i = LINES-1; 0 <= i && ins_rep[i] == lines_insert; --i) {
908 		/* Make each character in the screen line image invalid. */
909 		for (cp = curscr->_line[i], j = 0; j < COLS; ++j, ++cp)
910 			cp->_n = -1;
911 		ins_rep[i] = lines_replace;
912 	}
913 }
914 
915 /*
916  * Complex update algorithm using insert/delete line operations.
917  *
918  * References:
919  * [MyM86]	E.W. Myers & W. Miller, Row Replacement Algorithms for
920  *		Screen Editors, TR 86-19, Dept. Computer Science, U. of Arizona
921  * [MyM87]	E.W. Myers & W. Miller, A Simple Row Replacement Method,
922  *		TR 86-28, Dept. Computer Science, U. of Arizona
923  * [Mil87]	W. Miller, A Software Tools Sampler, Prentice-Hall, 1987
924  * [Gos81]	James Gosling, A redisplay algorithm, Proceedings of the
925  *		ACM Symposium on Text Manipulation, SIGPLAN Notices,
926  *		16(6) June 1981, pg 123-129
927  *
928  * All the above were reviewed and experimented with.  Due to the nature of
929  * Curses' having to handling overlapping WINDOWs, the only suitable
930  * algorithum is [Gos81].  The others are better suited to editor type
931  * applications that have one window being the entire terminal screen.
932  *
933  */
934 static void
complex(void)935 complex(void)
936 {
937 	int	fr = -1;
938 	int	i, j, lr;
939 	t_action	func;
940 
941 	/* Find block of lines to change */
942 	for (i = 0; i < LINES; ++i) {
943 		if (newscr->_first[i] < newscr->_last[i]) {
944 			/* Compute new hash. */
945 			__m_cc_hash(newscr, nhash, i);
946 			if (fr == -1)
947 				fr = i;
948 			lr = i;
949 		} else {
950 			/* Line not dirty so hash same as before. */
951 			nhash[i] = __m_screen->_hash[i];
952 		}
953 	}
954 
955 	if (fr != -1) {
956 		/* Gosling */
957 		(void) cost(fr, lr);
958 		script(fr, lr);
959 
960 		/* Do deletes first in reverse order. */
961 		for (j = lr; fr <= j; --j) {
962 			if (del[j] != (t_action) 0) {
963 				for (i = j-1; fr <= i; --i)
964 					if (del[i] == (t_action) 0)
965 						break;
966 
967 				lines_delete(i+1, j+1);
968 				j = i;
969 			}
970 		}
971 
972 		/* Do insert/replace in forward order. */
973 		for (i = fr; i <= lr; ++i) {
974 			if ((func = ins_rep[i]) != (t_action) 0) {
975 				/* Find size of block */
976 				for (j = i; j <= lr && ins_rep[j] == func; ++j)
977 					;
978 				(*func)(i, j);
979 				i = j - 1;
980 			}
981 		}
982 		/*
983 		 * _line[], which contains pointers to screen lines,
984 		 * may be shuffled.
985 		 */
986 		for (i = fr; i <= lr; ++i) {
987 			/* Save new hash for next update. */
988 			__m_screen->_hash[i] = nhash[i];
989 
990 			/* Mark line as untouched. */
991 			newscr->_first[i] = newscr->_maxx;
992 			newscr->_last[i] = -1;
993 		}
994 	}
995 }
996 
997 /*
998  * Simple screen update algorithm
999  *
1000  * We perform a simple incremental update of the terminal screen.
1001  * Only the segment of a line that was touched is replaced on the
1002  * line.
1003  */
1004 static void
simple(void)1005 simple(void)
1006 {
1007 	int row;
1008 
1009 	for (row = 0; row < newscr->_maxy; ++row) {
1010 		if (newscr->_first[row] < newscr->_last[row]) {
1011 			text_replace(row);
1012 
1013 			/* Mark line as untouched. */
1014 			newscr->_first[row] = newscr->_maxx;
1015 			newscr->_last[row] = -1;
1016 			__m_cc_hash(curscr, __m_screen->_hash, row);
1017 		}
1018 	}
1019 
1020 	newscr->_flags &= ~W_REDRAW_WINDOW;
1021 }
1022 
1023 void
wtouchln_hard(WINDOW * w,int y,int n)1024 wtouchln_hard(WINDOW *w, int y, int n)
1025 {
1026 	int	last;
1027 
1028 	last = w->_maxx;
1029 
1030 	for (; (y < w->_maxy) && (0 < n); ++y, --n) {
1031 		/*
1032 		 * Force compare in doupdate to fail.
1033 		 * Touch should be unconditional
1034 		 */
1035 (void) memset(&__m_screen->_curscr->_line[w->_begy + y][w->_begx],
1036 	0xff, last * sizeof (cchar_t));
1037 	}
1038 }
1039 /*
1040  * Send all changes made to _newscr to the physical terminal.
1041  *
1042  * If idlok() is set TRUE then doupdate will try and use hardware insert
1043  * and delete line sequences in an effort to optimize output.  idlok()
1044  * should really only be used in applications that want a proper scrolling
1045  * effect.
1046  *
1047  * Added scroll heuristic to handle special case where a full size window
1048  * with full size scroll region, will scroll the window and replace dirty
1049  * lines instead of performing usual cost/script operations.
1050  */
1051 int
doupdate(void)1052 doupdate(void)
1053 {
1054 #ifdef SIGTSTP
1055 	int (*oldsig)(int) = signal(SIGTSTP, SIG_IGN);
1056 #endif
1057 
1058 	if (pollTypeahead()) {
1059 		return (OK);
1060 	}
1061 	newscr = __m_screen->_newscr;
1062 
1063 	if (__m_screen->_flags & S_ENDWIN) {
1064 		/* Return from temporary escape done with endwin(). */
1065 		__m_screen->_flags &= ~S_ENDWIN;
1066 
1067 		(void) reset_prog_mode();
1068 		if (enter_ca_mode != NULL)
1069 			(void) TPUTS(enter_ca_mode, 1, __m_outc);
1070 		if (keypad_xmit != NULL)
1071 			(void) TPUTS(keypad_xmit, 1, __m_outc);
1072 		if (ena_acs != NULL)
1073 			(void) TPUTS(ena_acs, 1, __m_outc);
1074 
1075 		/* Force redraw of screen. */
1076 		newscr->_flags |= W_CLEAR_WINDOW;
1077 	}
1078 	/*
1079 	 * When redrawwing a window, we not only assume that line
1080 	 * noise may have lost characters, but line noise may have
1081 	 * generated bogus characters on the screen outside the
1082 	 * the window in question, in which case redraw the entire
1083 	 * screen to be sure.
1084 	 */
1085 	if ((newscr->_flags & (W_CLEAR_WINDOW | W_REDRAW_WINDOW)) ||
1086 		(curscr->_flags & W_CLEAR_WINDOW)) {
1087 		erase_bottom(0, newscr->_maxy);
1088 		clear_bottom(0);
1089 		(void) wtouchln(newscr, 0, newscr->_maxy, 1);
1090 		newscr->_flags &= ~W_CLEAR_WINDOW;
1091 		curscr->_flags &= ~W_CLEAR_WINDOW;
1092 	}
1093 
1094 	/*
1095 	 * Scrolling heuristic should only be used if lines being
1096 	 * scrolled are clean because scrolling overrides updates
1097 	 *
1098 	 * Right now, the following code should always turn off
1099 	 * scrolling, because the internal scroll touches the
1100 	 * scrolled lines. This thing requires a lot more care
1101 	 * than I have right now...
1102 	 */
1103 	if (newscr->_scroll) {
1104 		int	y;
1105 		for (y = 0; y < newscr->_maxy; ++y) {
1106 			if (0 <= newscr->_last[y]) {
1107 				newscr->_scroll = 0;
1108 			}
1109 		}
1110 		newscr->_scroll = 0;	/* Just fudge it for now ... */
1111 	}
1112 	if (newscr->_flags & W_REDRAW_WINDOW) {
1113 		simple();
1114 	} else {
1115 		if (newscr->_scroll == 0) {
1116 			if (__m_screen->_flags & S_INS_DEL_LINE) {
1117 				complex();
1118 			} else {
1119 				simple();
1120 			}
1121 		} else {
1122 			if (!scroll_up(newscr->_scroll)) {
1123 				if (__m_screen->_flags & S_INS_DEL_LINE) {
1124 					complex();
1125 				} else {
1126 					simple();
1127 				}
1128 			}
1129 		}
1130 	}
1131 
1132 	if (!(newscr->_flags & W_LEAVE_CURSOR))	{
1133 		GOTO(newscr->_cury, newscr->_curx);
1134 	}
1135 
1136 	if (!(curscr->_flags & W_FLUSH)) {
1137 		(void) fflush(__m_screen->_of);
1138 	}
1139 
1140 	newscr->_scroll = curscr->_scroll = 0;
1141 
1142 	/* Send labels to terminal that supports them. */
1143 	__m_slk_doupdate();
1144 #ifdef SIGTSTP
1145 	signal(SIGTSTP, oldsig);
1146 #endif
1147 
1148 	return (OK);
1149 }
1150 
1151 /*
1152  * If true, the implementation may use hardware insert and delete,
1153  * character features of the terminal.  The window parameter
1154  * is ignored.
1155  */
1156 /* ARGSUSED */
1157 void
idcok(WINDOW * w,bool bf)1158 idcok(WINDOW *w, bool bf)
1159 {
1160 	__m_screen->_flags &= ~S_INS_DEL_CHAR;
1161 	if (bf)
1162 		__m_screen->_flags |= S_INS_DEL_CHAR;
1163 }
1164 
1165 /*
1166  * If true, the implementation may use hardware insert, delete,
1167  * and scroll line features of the terminal.  The window parameter
1168  * is ignored.
1169  */
1170 /* ARGSUSED */
1171 int
idlok(WINDOW * w,bool bf)1172 idlok(WINDOW *w, bool bf)
1173 {
1174 	__m_screen->_flags &= ~S_INS_DEL_LINE;
1175 	if (bf && has_il())
1176 		__m_screen->_flags |= S_INS_DEL_LINE;
1177 
1178 	return (OK);
1179 }
1180 
1181 /*
1182  * Use the POSIX 32-bit CRC function to compute a hash value
1183  * for the window line.
1184  */
1185 void
1186 #if defined(_LP64)
__m_cc_hash(WINDOW * w,unsigned int * array,int y)1187 __m_cc_hash(WINDOW *w, unsigned int *array, int y)
1188 #else
1189 __m_cc_hash(WINDOW *w, unsigned long *array, int y)
1190 #endif
1191 {
1192 	array[y] = 0;
1193 	m_crcposix(&array[y], (unsigned char *) w->_line[y],
1194 		(size_t)(w->_maxx * sizeof (**w->_line)));
1195 }
1196