1/****************************************************************************
2 * Copyright (c) 1998,2000 Free Software Foundation, Inc.                   *
3 *                                                                          *
4 * Permission is hereby granted, free of charge, to any person obtaining a  *
5 * copy of this software and associated documentation files (the            *
6 * "Software"), to deal in the Software without restriction, including      *
7 * without limitation the rights to use, copy, modify, merge, publish,      *
8 * distribute, distribute with modifications, sublicense, and/or sell       *
9 * copies of the Software, and to permit persons to whom the Software is    *
10 * furnished to do so, subject to the following conditions:                 *
11 *                                                                          *
12 * The above copyright notice and this permission notice shall be included  *
13 * in all copies or substantial portions of the Software.                   *
14 *                                                                          *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS  *
16 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF               *
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.   *
18 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,   *
19 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR    *
20 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR    *
21 * THE USE OR OTHER DEALINGS IN THE SOFTWARE.                               *
22 *                                                                          *
23 * Except as contained in this notice, the name(s) of the above copyright   *
24 * holders shall not be used in advertising or otherwise to promote the     *
25 * sale, use or other dealings in this Software without prior written       *
26 * authorization.                                                           *
27 ****************************************************************************/
28
29/****************************************************************************
30 *  Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995               *
31 *     and: Eric S. Raymond <esr@snark.thyrsus.com>                         *
32 ****************************************************************************/
33
34/******************************************************************************
35
36NAME
37   hardscroll.c -- hardware-scrolling optimization for ncurses
38
39SYNOPSIS
40   void _nc_scroll_optimize(void)
41
42DESCRIPTION
43			OVERVIEW
44
45This algorithm for computes optimum hardware scrolling to transform an
46old screen (curscr) into a new screen (newscr) via vertical line moves.
47
48Because the screen has a `grain' (there are insert/delete/scroll line
49operations but no insert/delete/scroll column operations), it is efficient
50break the update algorithm into two pieces: a first stage that does only line
51moves, optimizing the end product of user-invoked insertions, deletions, and
52scrolls; and a second phase (corresponding to the present doupdate code in
53ncurses) that does only line transformations.
54
55The common case we want hardware scrolling for is to handle line insertions
56and deletions in screen-oriented text-editors.  This two-stage approach will
57accomplish that at a low computation and code-size cost.
58
59			LINE-MOVE COMPUTATION
60
61Now, to a discussion of the line-move computation.
62
63For expository purposes, consider the screen lines to be represented by
64integers 0..23 (with the understanding that the value of 23 may vary).
65Let a new line introduced by insertion, scrolling, or at the bottom of
66the screen following a line delete be given the index -1.
67
68Assume that the real screen starts with lines 0..23.  Now, we have
69the following possible line-oriented operations on the screen:
70
71Insertion: inserts a line at a given screen row, forcing all lines below
72to scroll forward.  The last screen line is lost.  For example, an insertion
73at line 5 would produce: 0..4 -1 5..23.
74
75Deletion: deletes a line at a given screen row, forcing all lines below
76to scroll forward.  The last screen line is made new.  For example, a deletion
77at line 7 would produce: 0..6 8..23 -1.
78
79Scroll up: move a range of lines up 1.  The bottom line of the range
80becomes new.  For example, scrolling up the region from 9 to 14 will
81produce 0..8 10..14 -1 15..23.
82
83Scroll down: move a range of lines down 1.  The top line of the range
84becomes new.  For example, scrolling down the region from 12 to 16 will produce
850..11 -1 12..15 17..23.
86
87Now, an obvious property of all these operations is that they preserve the
88order of old lines, though not their position in the sequence.
89
90The key trick of this algorithm is that the original line indices described
91above are actually maintained as _line[].oldindex fields in the window
92structure, and stick to each line through scroll and insert/delete operations.
93
94Thus, it is possible at update time to look at the oldnum fields and compute
95an optimal set of il/dl/scroll operations that will take the real screen
96lines to the virtual screen lines.  Once these vertical moves have been done,
97we can hand off to the second stage of the update algorithm, which does line
98transformations.
99
100Note that the move computation does not need to have the full generality
101of a diff algorithm (which it superficially resembles) because lines cannot
102be moved out of order.
103
104			THE ALGORITHM
105
106The scrolling is done in two passes. The first pass is from top to bottom
107scroling hunks UP. The second one is from bottom to top scrolling hunks DOWN.
108Obviously enough, no lines to be scrolled will be destroyed. (lav)
109
110HOW TO TEST THIS:
111
112Use the following production:
113
114hardscroll: hardscroll.c
115	$(CC) -g -DSCROLLDEBUG hardscroll.c -o hardscroll
116
117Then just type scramble vectors and watch.  The following test loads are
118a representative sample of cases:
119
120-----------------------------  CUT HERE ------------------------------------
121# No lines moved
122 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
123#
124# A scroll up
125 1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 -1
126#
127# A scroll down
128-1  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22
129#
130# An insertion (after line 12)
131 0  1  2  3  4  5  6  7  8  9 10 11 12 -1 13 14 15 16 17 18 19 20 21 22
132#
133# A simple deletion (line 10)
134 0  1  2  3  4  5  6  7  8  9  11 12 13 14 15 16 17 18 19 20 21 22 23 -1
135#
136# A more complex case
137-1 -1 -1 -1 -1  3  4  5  6  7  -1 -1  8  9 10 11 12 13 14 15 16 17 -1 -1
138-----------------------------  CUT HERE ------------------------------------
139
140AUTHOR
141    Eric S. Raymond <esr@snark.thyrsus.com>, November 1994
142    New algorithm by Alexander V. Lukyanov <lav@yars.free.net>, Aug 1997
143
144*****************************************************************************/
145
146#include <curses.priv.h>
147
148MODULE_ID("$Id: hardscroll.c,v 1.36 2001/01/14 00:17:28 tom Exp $")
149
150#if defined(SCROLLDEBUG) || defined(HASHDEBUG)
151
152# undef screen_lines
153# define screen_lines MAXLINES
154NCURSES_EXPORT_VAR(int)
155oldnums[MAXLINES];
156# define OLDNUM(n)	oldnums[n]
157# define _tracef	printf
158# undef TR
159# define TR(n, a)	if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); }
160
161#else /* no debug */
162
163/* OLDNUM(n) indicates which line will be shifted to the position n.
164   if OLDNUM(n) == _NEWINDEX, then the line n in new, not shifted from
165   somewhere. */
166NCURSES_EXPORT_VAR(int *)
167_nc_oldnums = 0;
168
169# if USE_HASHMAP
170     static int oldnums_allocated = 0;
171#  define oldnums       _nc_oldnums
172#  define OLDNUM(n)	oldnums[n]
173# else				/* !USE_HASHMAP */
174#  define OLDNUM(n)	newscr->_line[n].oldindex
175# endif				/* !USE_HASHMAP */
176
177#endif /* defined(SCROLLDEBUG) || defined(HASHDEBUG) */
178
179NCURSES_EXPORT(void)
180_nc_scroll_optimize(void)
181/* scroll optimization to transform curscr to newscr */
182{
183    int i;
184    int start, end, shift;
185
186    TR(TRACE_ICALLS, ("_nc_scroll_optimize() begins"));
187
188#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
189#if USE_HASHMAP
190    /* get enough storage */
191    if (oldnums_allocated < screen_lines) {
192	int *new_oldnums = typeRealloc(int, screen_lines, oldnums);
193	if (!new_oldnums)
194	    return;
195	oldnums = new_oldnums;
196	oldnums_allocated = screen_lines;
197    }
198    /* calculate the indices */
199    _nc_hash_map();
200#endif
201#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
202
203#ifdef TRACE
204    if (_nc_tracing & (TRACE_UPDATE | TRACE_MOVE))
205	_nc_linedump();
206#endif /* TRACE */
207
208    /* pass 1 - from top to bottom scrolling up */
209    for (i = 0; i < screen_lines;) {
210	while (i < screen_lines && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) <= i))
211	    i++;
212	if (i >= screen_lines)
213	    break;
214
215	shift = OLDNUM(i) - i;	/* shift > 0 */
216	start = i;
217
218	i++;
219	while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i
220	       == shift)
221	    i++;
222	end = i - 1 + shift;
223
224	TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift));
225#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
226	if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) {
227	    TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll"));
228	    continue;
229	}
230#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
231    }
232
233    /* pass 2 - from bottom to top scrolling down */
234    for (i = screen_lines - 1; i >= 0;) {
235	while (i >= 0 && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) >= i))
236	    i--;
237	if (i < 0)
238	    break;
239
240	shift = OLDNUM(i) - i;	/* shift < 0 */
241	end = i;
242
243	i--;
244	while (i >= 0 && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift)
245	    i--;
246	start = i + 1 - (-shift);
247
248	TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift));
249#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
250	if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) {
251	    TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll"));
252	    continue;
253	}
254#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
255    }
256}
257
258#if defined(TRACE) || defined(SCROLLDEBUG) || defined(HASHDEBUG)
259NCURSES_EXPORT(void)
260_nc_linedump(void)
261/* dump the state of the real and virtual oldnum fields */
262{
263    static size_t have;
264    static char *buf;
265
266    int n;
267    size_t want = (screen_lines + 1) * 4;
268
269    if (have < want)
270	buf = typeMalloc(char, have = want);
271
272    (void) strcpy(buf, "virt");
273    for (n = 0; n < screen_lines; n++)
274	(void) sprintf(buf + strlen(buf), " %02d", OLDNUM(n));
275    TR(TRACE_UPDATE | TRACE_MOVE, (buf));
276#if NO_LEAKS
277    free(buf);
278    have = 0;
279#endif
280}
281#endif /* defined(TRACE) || defined(SCROLLDEBUG) */
282
283#ifdef SCROLLDEBUG
284
285int
286main(int argc GCC_UNUSED, char *argv[]GCC_UNUSED)
287{
288    char line[BUFSIZ], *st;
289
290#ifdef TRACE
291    _nc_tracing = TRACE_MOVE;
292#endif
293    for (;;) {
294	int n;
295
296	for (n = 0; n < screen_lines; n++)
297	    oldnums[n] = _NEWINDEX;
298
299	/* grab the test vector */
300	if (fgets(line, sizeof(line), stdin) == (char *) NULL)
301	    exit(EXIT_SUCCESS);
302
303	/* parse it */
304	n = 0;
305	if (line[0] == '#') {
306	    (void) fputs(line, stderr);
307	    continue;
308	}
309	st = strtok(line, " ");
310	do {
311	    oldnums[n++] = atoi(st);
312	} while
313	    ((st = strtok((char *) NULL, " ")) != 0);
314
315	/* display it */
316	(void) fputs("Initial input:\n", stderr);
317	_nc_linedump();
318
319	_nc_scroll_optimize();
320    }
321}
322
323#endif /* SCROLLDEBUG */
324
325/* hardscroll.c ends here */
326