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 */