2 /***************************************************************************
4 ****************************************************************************
5 * ncurses is copyright (C) 1992-1995 *
7 * zmbenhal@netcom.com *
9 * esr@snark.thyrsus.com *
11 * Permission is hereby granted to reproduce and distribute ncurses *
12 * by any means and for any fee, whether alone or as part of a *
13 * larger distribution, in source or in binary form, PROVIDED *
14 * this notice is included with any such distribution, and is not *
15 * removed from any of its header files. Mention of ncurses in any *
16 * applications linked with it is highly appreciated. *
18 * ncurses comes AS IS with no warranty, implied or expressed. *
20 ***************************************************************************/
23 /******************************************************************************
26 hardscroll.c -- hardware-scrolling optimization for ncurses
29 void _nc_scroll_optimize(void)
34 This algorithm for computes optimum hardware scrolling to transform an
35 old screen (curscr) into a new screen (newscr) via vertical line moves.
37 Because the screen has a `grain' (there are insert/delete/scroll line
38 operations but no insert/delete/scroll column operations), it is efficient
39 break the update algorithm into two pieces: a first stage that does only line
40 moves, optimizing the end product of user-invoked insertions, deletions, and
41 scrolls; and a second phase (corresponding to the present doupdate code in
42 ncurses) that does only line transformations.
44 The common case we want hardware scrolling for is to handle line insertions
45 and deletions in screen-oriented text-editors. This two-stage approach will
46 accomplish that at a low computation and code-size cost.
50 Now, to a discussion of the line-move computation.
52 For expository purposes, consider the screen lines to be represented by
53 integers 0..23 (with the understanding that the value of 23 may vary).
54 Let a new line introduced by insertion, scrolling, or at the bottom of
55 the screen following a line delete be given the index -1.
57 Assume that the real screen starts with lines 0..23. Now, we have
58 the following possible line-oriented operations on the screen:
60 Insertion: inserts a line at a given screen row, forcing all lines below
61 to scroll forward. The last screen line is lost. For example, an insertion
62 at line 5 would produce: 0..4 -1 5..23.
64 Deletion: deletes a line at a given screen row, forcing all lines below
65 to scroll forward. The last screen line is made new. For example, a deletion
66 at line 7 would produce: 0..6 8..23 -1.
68 Scroll up: move a range of lines up 1. The bottom line of the range
69 becomes new. For example, scrolling up the region from 9 to 14 will
70 produce 0..8 10..14 -1 15..23.
72 Scroll down: move a range of lines down 1. The top line of the range
73 becomes new. For example, scrolling down the region from 12 to 16 will produce
74 0..11 -1 12..15 17..23.
76 Now, an obvious property of all these operations is that they preserve the
77 order of old lines, though not their position in the sequence.
79 The key trick of this algorithm is that the original line indices described
80 above are actually maintained as _line[].oldindex fields in the window
81 structure, and stick to each line through scroll and insert/delete operations.
83 Thus, it is possible at update time to look at the oldnum fields and compute
84 an optimal set of il/dl/scroll operations that will take the real screen
85 lines to the virtual screen lines. Once these vertical moves have been done,
86 we can hand off to the second stage of the update algorithm, which does line
89 Note that the move computation does not need to have the full generality
90 of a diff algorithm (which it superficially resembles) because lines cannot
91 be moved out of order.
95 First, mark each line on the real screen that is *not* carried over to the
96 virtual screen discarded (that is, with a -1 oldnum index).
98 Second, optionally run through each virtual line with a non -1 oldnum. If the
99 line is sufficiently changed, mark it -1 (we don't want to move it). The exact
100 test for "sufficiently changed" is not relevant to the control flow of this
101 algorithm. Cases the test should detect are those in which rewriting
102 the line from whatever might be on the real screen would be cheaper than the
103 move. Blank lines on a terminal with clear-to-eol probably meet this test.
105 Here is pseudo-code for the remainder of the algorithm:
109 2: no_hunk_moved = TRUE;
111 # on each pass, try to find a movable hunk
112 3: while (first < screen_depth)
114 # scan for start of hunk
115 4: while (oldnum field of first == -1)
118 # if we have no hunk, quit this pass
119 5: if (first >= screen_depth)
123 6: last = (end of longest continues oldnum range starting here)
125 7: ofirst = (first line's oldnum, where it was on real screen)
126 8: olast = (last line's oldnum, where it was on real screen)
128 # figure the hunk's displacement
129 9: disp = first - (first virtual line's oldnum field)
131 # does the hunk want to move?
133 # is the hunk movable without destroying info?
134 11: if (real [ofirst+disp, olast+disp] are all in range or DISCARDED)
136 13: scroll real [ofirst, olast+disp] down by disp
137 (mark [ofirst, olast+disp] DISCARDED)
138 14: else if (disp < 0)
139 15: scroll real [ofirst+disp, olast] up by disp
140 (mark [ofirst+disp, olast] DISCARDED)
141 16: no_hunk_moved = FALSE
143 # done trying to move this hunk
144 17: first = last + 1;
147 18: no_hunk_moved; # quit when a complete pass finds no movable hunks
151 Use the following production:
153 hardscroll: hardscroll.c
154 $(CC) -g -DSCROLLDEBUG hardscroll.c -o hardscroll
156 Then just type scramble vectors and watch. The following test loads are
157 a representative sample of cases:
159 ----------------------------- CUT HERE ------------------------------------
161 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
164 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 -1
167 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
169 # An insertion (after line 12)
170 0 1 2 3 4 5 6 7 8 9 10 11 12 -1 13 14 15 16 17 18 19 20 21 22
172 # A simple deletion (line 10)
173 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 -1
175 # A more complex case
176 -1 -1 -1 -1 -1 3 4 5 6 7 -1 -1 8 9 10 11 12 13 14 15 16 17 -1 -1
177 ----------------------------- CUT HERE ------------------------------------
180 Eric S. Raymond <esr@snark.thyrsus.com>, November 1994
182 *****************************************************************************/
184 #include <curses.priv.h>
186 MODULE_ID("$Id: hardscroll.c,v 1.17 1997/02/15 22:33:12 tom Exp $")
188 #if defined(TRACE) || defined(SCROLLDEBUG)
189 void _nc_linedump(void);
190 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
192 /* if only this number of lines is carried over, nuke the screen and redraw */
193 #define CLEAR_THRESHOLD 3
195 #if defined(SCROLLDEBUG) || defined(HASHDEBUG)
197 int oldnums[LINES], reallines[LINES];
198 #define OLDNUM(n) oldnums[n]
199 #define REAL(m) reallines[m]
201 #define T(x) (void) printf x ; (void) putchar('\n');
204 #define OLDNUM(n) newscr->_line[n].oldindex
205 #define REAL(m) curscr->_line[m].oldindex
208 #endif /* _NEWINDEX */
209 #endif /* defined(SCROLLDEBUG) || defined(HASHDEBUG) */
211 static bool all_discarded(int const top, int const bottom, int const disp)
212 /* has the given range of real lines been marked discarded? */
216 for (n = top + disp; n <= bottom + disp; n++)
217 if (REAL(n) != _NEWINDEX && !(REAL(n) <= bottom && REAL(n) >= top))
223 void _nc_scroll_optimize(void)
224 /* scroll optimization to transform curscr to newscr */
226 bool no_hunk_moved; /* no hunk moved on this pass? */
228 #if defined(TRACE) || defined(SCROLLDEBUG)
230 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
232 TR(TRACE_ICALLS, ("_nc_scroll_optimize() begins"));
234 /* mark any line not carried over with _NEWINDEX */
235 for (n = 0; n < LINES; n++)
236 REAL(n) += (MAXLINES + 1);
237 for (n = 0; n < LINES; n++)
238 if (OLDNUM(n) != _NEWINDEX
239 && REAL(OLDNUM(n)) >= MAXLINES)
240 REAL(OLDNUM(n)) -= (MAXLINES + 1);
241 for (n = new_lines = 0; n < LINES; n++)
242 if (REAL(n) > MAXLINES)
249 * ^F in vi (which scrolls forward by LINES-2 in the file) exposes
250 * a weakness in this design. Ideally, vertical motion
251 * optimization should cost its actions and then force a
252 * ClrUpdate() and complete redraw if that would be faster than
253 * the scroll. Unfortunately, this would be a serious pain to
254 * arrange; hence, this hack. If there are few enough lines
255 * carried over, don't bother with the scrolling, we just nuke the
256 * screen and redraw the whole thing. Keith Bostic argues that
257 * this will be a win on strictly visual grounds even if the
258 * resulting update is theoretically sub-optimal. Experience
259 * with vi says he's probably right.
261 if (LINES - new_lines <= CLEAR_THRESHOLD)
263 T(("too few lines carried over, nuking screen"));
264 #if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
265 clearok(stdscr, TRUE);
266 #endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
271 TR(TRACE_UPDATE | TRACE_MOVE, ("After real line marking:"));
272 if (_nc_tracing & (TRACE_UPDATE | TRACE_MOVE))
276 /* time to shuffle lines to do scroll optimization */
278 int first; /* first line of current hunk */
279 int last; /* last line of current hunk */
280 int ofirst; /* oldnum index of first line */
281 int olast; /* oldnum index of last line */
282 int disp; /* hunk displacement */
284 TR(TRACE_UPDATE | TRACE_MOVE, ("Pass %d:", pass++));
286 first = 0; /* start scan at top line */
287 no_hunk_moved = TRUE;
289 while (first < LINES)
291 /* find the beginning of a hunk */
292 while (first < LINES && OLDNUM(first) == _NEWINDEX)
297 /* find the end of the hunk */
298 for (last = first; last < LINES; last++)
299 if (last == LINES - 1 || OLDNUM(last + 1) != OLDNUM(last) + 1)
302 /* find the corresponding range on the old screen */
303 ofirst = OLDNUM(first);
304 olast = OLDNUM(last);
306 /* compute the hunk's displacement */
307 disp = first - OLDNUM(first);
309 TR(TRACE_UPDATE | TRACE_MOVE, ("found hunk: first = %2d, last = %2d, ofirst = %2d, olast = %2d, disp = %2d",
310 first, last, ofirst, olast, disp));
312 /* OK, time to try to move the hunk? */
314 if (all_discarded(ofirst, olast, disp))
320 else /* (disp < 0) */
323 TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", ofirst, olast, -disp));
324 #if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
325 if (_nc_mvcur_scrolln(-disp, ofirst, olast, LINES - 1) == ERR)
327 _nc_scroll_window(curscr, -disp, ofirst, olast);
328 #endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
330 for (m = ofirst; m <= olast; m++)
333 #if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
335 * This will tell the second stage of the optimizer
336 * that every line in the hunk on the real screen has
339 curscr->_line[m].firstchar = 0;
340 curscr->_line[m].lastchar = curscr->_maxx;
341 #endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
343 for (m = first; m <= last; m++)
344 OLDNUM(m) = _NEWINDEX;
346 no_hunk_moved = FALSE;
349 /* OK, done with this hunk */
356 #if defined(TRACE) || defined(SCROLLDEBUG)
357 void _nc_linedump(void)
358 /* dump the state of the real and virtual oldnum fields */
363 (void) strcpy(buf, "real");
364 for (n = 0; n < LINES; n++)
365 (void) sprintf(buf + strlen(buf), " %02d", REAL(n));
366 TR(TRACE_UPDATE | TRACE_MOVE, (buf));
368 (void) strcpy(buf, "virt");
369 for (n = 0; n < LINES; n++)
370 (void) sprintf(buf + strlen(buf), " %02d", OLDNUM(n));
371 TR(TRACE_UPDATE | TRACE_MOVE, (buf));
373 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
378 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
380 char line[BUFSIZ], *st;
382 _nc_tracing = TRACE_MOVE;
387 for (n = 0; n < LINES; n++)
390 oldnums[n] = _NEWINDEX;
393 /* grab the test vector */
394 if (fgets(line, sizeof(line), stdin) == (char *)NULL)
401 (void) fputs(line, stderr);
404 st = strtok(line, " ");
406 oldnums[n++] = atoi(st);
408 ((st = strtok((char *)NULL, " ")) != 0);
411 (void) fputs("Initial input:\n", stderr);
414 _nc_scroll_optimize();
418 #endif /* SCROLLDEBUG */
420 /* hardscroll.c ends here */