ncurses 4.1
[ncurses.git] / ncurses / hardscroll.c
1
2 /***************************************************************************
3 *                            COPYRIGHT NOTICE                              *
4 ****************************************************************************
5 *                ncurses is copyright (C) 1992-1995                        *
6 *                          Zeyd M. Ben-Halim                               *
7 *                          zmbenhal@netcom.com                             *
8 *                          Eric S. Raymond                                 *
9 *                          esr@snark.thyrsus.com                           *
10 *                                                                          *
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.                *
17 *                                                                          *
18 *        ncurses comes AS IS with no warranty, implied or expressed.       *
19 *                                                                          *
20 ***************************************************************************/
21
22
23 /******************************************************************************
24
25 NAME
26    hardscroll.c -- hardware-scrolling optimization for ncurses
27
28 SYNOPSIS
29    void _nc_scroll_optimize(void)
30
31 DESCRIPTION
32                         OVERVIEW
33
34 This algorithm for computes optimum hardware scrolling to transform an
35 old screen (curscr) into a new screen (newscr) via vertical line moves.
36
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.
43
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.
47
48                         LINE-MOVE COMPUTATION
49
50 Now, to a discussion of the line-move computation.
51
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.
56
57 Assume that the real screen starts with lines 0..23.  Now, we have
58 the following possible line-oriented operations on the screen:
59
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.
63
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.
67
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.
71
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.
75
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.
78
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.
82
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
87 transformations.
88
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.
92
93                         THE ALGORITHM
94
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).
97
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.
104
105 Here is pseudo-code for the remainder of the algorithm:
106
107   repeat
108 1:    first = 0;
109 2:    no_hunk_moved = TRUE;
110
111       # on each pass, try to find a movable hunk
112 3:    while (first < screen_depth)
113
114           # scan for start of hunk
115 4:        while (oldnum field of first == -1)
116               first++
117
118           # if we have no hunk, quit this pass
119 5:        if (first >= screen_depth)
120               break;
121
122           # we found a hunk
123 6:        last = (end of longest continues oldnum range starting here)
124
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)
127
128           # figure the hunk's displacement
129 9:        disp = first - (first virtual line's oldnum field)
130
131           # does the hunk want to move?
132 10:       if (disp != 0)
133               # is the hunk movable without destroying info?
134 11:           if (real [ofirst+disp, olast+disp] are all in range or DISCARDED)
135 12:               if (disp > 0)
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
142
143           # done trying to move this hunk
144 17:       first = last + 1;
145        end while
146     until
147 18:    no_hunk_moved;    # quit when a complete pass finds no movable hunks
148
149 HOW TO TEST THIS:
150
151 Use the following production:
152
153 hardscroll: hardscroll.c
154         $(CC) -g -DSCROLLDEBUG hardscroll.c -o hardscroll
155
156 Then just type scramble vectors and watch.  The following test loads are
157 a representative sample of cases:
158
159 -----------------------------  CUT HERE ------------------------------------
160 # No lines moved
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
162 #
163 # A scroll up
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
165 #
166 # A scroll down
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
168 #
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
171 #
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
174 #
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 ------------------------------------
178
179 AUTHOR
180     Eric S. Raymond <esr@snark.thyrsus.com>, November 1994
181
182 *****************************************************************************/
183
184 #include <curses.priv.h>
185
186 MODULE_ID("$Id: hardscroll.c,v 1.17 1997/02/15 22:33:12 tom Exp $")
187
188 #if defined(TRACE) || defined(SCROLLDEBUG)
189 void _nc_linedump(void);
190 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
191
192 /* if only this number of lines is carried over, nuke the screen and redraw */
193 #define CLEAR_THRESHOLD         3
194
195 #if defined(SCROLLDEBUG) || defined(HASHDEBUG)
196 #define LINES   24
197 int oldnums[LINES], reallines[LINES];
198 #define OLDNUM(n)       oldnums[n]
199 #define REAL(m)         reallines[m]
200 #undef T
201 #define T(x)            (void) printf x ; (void) putchar('\n');
202 #else
203 #include <curses.h>
204 #define OLDNUM(n)       newscr->_line[n].oldindex
205 #define REAL(m)         curscr->_line[m].oldindex
206 #ifndef _NEWINDEX
207 #define _NEWINDEX       -1
208 #endif /* _NEWINDEX */
209 #endif /* defined(SCROLLDEBUG) || defined(HASHDEBUG) */
210
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? */
213 {
214     int         n;
215
216     for (n = top + disp; n <= bottom + disp; n++)
217         if (REAL(n) != _NEWINDEX && !(REAL(n) <= bottom && REAL(n) >= top))
218             return(FALSE);
219
220     return(TRUE);
221 }
222
223 void _nc_scroll_optimize(void)
224 /* scroll optimization to transform curscr to newscr */
225 {
226     bool no_hunk_moved;         /* no hunk moved on this pass? */
227     int n, new_lines;
228 #if defined(TRACE) || defined(SCROLLDEBUG)
229     int pass = 0;
230 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
231
232     TR(TRACE_ICALLS, ("_nc_scroll_optimize() begins"));
233
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)
243         {
244             REAL(n) = _NEWINDEX;
245             new_lines++;
246         }
247
248     /*
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.
260      */
261     if (LINES - new_lines <= CLEAR_THRESHOLD)
262     {
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) */
267         return;
268     }
269
270 #ifdef TRACE
271     TR(TRACE_UPDATE | TRACE_MOVE, ("After real line marking:"));
272     if (_nc_tracing & (TRACE_UPDATE | TRACE_MOVE))
273         _nc_linedump();
274 #endif /* TRACE */
275
276     /* time to shuffle lines to do scroll optimization */
277     do {
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 */
283
284         TR(TRACE_UPDATE | TRACE_MOVE, ("Pass %d:", pass++));
285
286         first = 0;              /* start scan at top line */
287         no_hunk_moved = TRUE;
288
289         while (first < LINES)
290         {
291             /* find the beginning of a hunk */
292             while (first < LINES && OLDNUM(first) == _NEWINDEX)
293                 first++;
294             if (first >= LINES)
295                 break;
296
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)
300                     break;
301
302             /* find the corresponding range on the old screen */
303             ofirst = OLDNUM(first);
304             olast = OLDNUM(last);
305
306             /* compute the hunk's displacement */
307             disp = first - OLDNUM(first);
308
309             TR(TRACE_UPDATE | TRACE_MOVE, ("found hunk: first = %2d, last = %2d, ofirst = %2d, olast = %2d, disp = %2d",
310                            first, last, ofirst, olast, disp));
311
312             /* OK, time to try to move the hunk? */
313             if (disp != 0)
314                 if (all_discarded(ofirst, olast, disp))
315                 {
316                     int m;
317
318                     if (disp > 0)
319                         olast += disp;
320                     else /* (disp < 0) */
321                         ofirst += disp;
322
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)
326                         break;
327                     _nc_scroll_window(curscr, -disp, ofirst, olast);
328 #endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
329
330                     for (m = ofirst; m <= olast; m++)
331                     {
332                         REAL(m) = _NEWINDEX;
333 #if !defined(SCROLLDEBUG) && !defined(HASHDEBUG)
334                         /*
335                          * This will tell the second stage of the optimizer
336                          * that every line in the hunk on the real screen has
337                          * been changed.
338                          */
339                         curscr->_line[m].firstchar = 0;
340                         curscr->_line[m].lastchar = curscr->_maxx;
341 #endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */
342                     }
343                     for (m = first; m <= last; m++)
344                         OLDNUM(m) = _NEWINDEX;
345
346                     no_hunk_moved = FALSE;
347                 }
348
349             /* OK, done with this hunk */
350             first = last + 1;
351         }
352     } while
353         (!no_hunk_moved);
354 }
355
356 #if defined(TRACE) || defined(SCROLLDEBUG)
357 void _nc_linedump(void)
358 /* dump the state of the real and virtual oldnum fields */
359 {
360     int n;
361     char        buf[BUFSIZ];
362
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));
367
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));
372 }
373 #endif /* defined(TRACE) || defined(SCROLLDEBUG) */
374
375 #ifdef SCROLLDEBUG
376
377 int
378 main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED)
379 {
380     char        line[BUFSIZ], *st;
381
382     _nc_tracing = TRACE_MOVE;
383     for (;;)
384     {
385         int     n;
386
387         for (n = 0; n < LINES; n++)
388         {
389             reallines[n] = n;
390             oldnums[n] = _NEWINDEX;
391         }
392
393         /* grab the test vector */
394         if (fgets(line, sizeof(line), stdin) == (char *)NULL)
395             exit(EXIT_SUCCESS);
396
397         /* parse it */
398         n = 0;
399         if (line[0] == '#')
400         {
401             (void) fputs(line, stderr);
402             continue;
403         }
404         st = strtok(line, " ");
405         do {
406             oldnums[n++] = atoi(st);
407         } while
408             ((st = strtok((char *)NULL, " ")) != 0);
409
410         /* display it */
411         (void) fputs("Initial input:\n", stderr);
412         _nc_linedump();
413
414         _nc_scroll_optimize();
415     }
416 }
417
418 #endif /* SCROLLDEBUG */
419
420 /* hardscroll.c ends here */