(scrolling_1): When scroll_region_ok is set, use a

new scrolling method which scrolls groups of lines directly
to their final vertical positions.
(struct matrix_elt): New field writecount.
(calculate_direct_scrolling): New function.
(do_direct_scrolling): New function.

1 files changed, 451 insertions, 9 deletions

diff --git a/src/scroll.c b/src/scroll.c
index 639f0f12628..75de9ebba89 100644
--- a/src/scroll.c
+++ b/src/scroll.c
@@ -52,11 +52,14 @@ struct matrix_elt
     /* Number of deletes so far in this run of deletes,
        for the cost in deletecost.  */
     unsigned char deletecount;
+    /* Number of writes so far since the last insert
+       or delete for the cost in writecost. */
+    unsigned char writecount;
   };
 
 
-/* Determine, in matrix[i,j], the cost of updating the first j old lines
-   into the first i new lines.
+/* Determine, in matrix[i,j], the cost of updating the first j old
+   lines into the first i new lines using the general scrolling method.
    This involves using insert or delete somewhere if i != j.
    For each matrix elements, three kinds of costs are recorded:
    the smallest cost that ends with an insert, the smallest
@@ -217,8 +220,8 @@ calculate_scrolling (frame, matrix, window_size, lines_below,
       }
 }
 
-/* Perform insert-lines and delete-lines operations on FRAME
-   according to the costs in MATRIX.
+/* Perform insert-lines and delete-lines operations on FRAME according
+   to the costs in MATRIX, using the general scrolling method.
    Update the frame's current_glyphs info to record what was done.
 
    WINDOW_SIZE is the number of lines being considered for scrolling
@@ -361,12 +364,440 @@ do_scrolling (frame, matrix, window_size, unchanged_at_top)
     set_terminal_window (0);
 }
 
+/* Determine, in matrix[i,j], the cost of updating the first j
+   old lines into the first i new lines using the direct
+   scrolling method.  When the old line and the new line have
+   different hash codes, the calculated cost of updating old
+   line j into new line i includes the cost of outputting new
+   line i, and if i != j, the cost of outputting the old line j
+   is also included, as a penalty for moving the line and then
+   erasing it.  In addition, the cost of updating a sequence of
+   lines with constant i - j includes the cost of scrolling the
+   old lines into their new positions, unless i == j.  Scrolling
+   is achieved by setting the screen window to avoid affecting
+   other lines below, and inserting or deleting lines at the top
+   of the scrolled region.  The cost of scrolling a sequence of
+   lines includes the fixed cost of specifying a scroll region,
+   plus a variable cost which can depend upon the number of lines
+   involved and the distance by which they are scrolled, and an
+   extra cost to discourage long scrolls.
+
+   As reflected in the matrix, an insert or delete does not
+   correspond directly to the insertion or deletion which is
+   used in scrolling lines.  An insert means that the value of i
+   has increased without a corresponding increase in the value
+   of j.  A delete means that the value of j has increased
+   without a corresponding increase in the value of i.  A write
+   means that i and j are both increased by the same amount, and
+   that the old lines will be moved to their new positions.
+
+   An insert following a delete is allowed only if i > j.
+   A delete following an insert is allowed only if i < j.
+   These restrictions ensure that the new lines in an insert
+   will always be blank as an effect of the neighboring writes.
+   Thus the calculated cost of an insert is simply the cost of
+   outputting the new line contents.  The direct cost of a
+   delete is zero.  Inserts and deletes indirectly affect the
+   total cost through their influence on subsequent writes. */
+
+/* The vectors draw_cost, old_hash, and new_hash have the same
+   meanings here as in calculate_scrolling, and old_draw_cost
+   is the equivalent of draw_cost for the old line contents */
+
+static void
+calculate_direct_scrolling (frame, matrix, window_size, lines_below,
+			    draw_cost, old_draw_cost, old_hash, new_hash,
+			    free_at_end)
+     FRAME_PTR frame;
+     /* matrix is of size window_size + 1 on each side.  */
+     struct matrix_elt *matrix;
+     int window_size;
+     int *draw_cost;
+     int *old_draw_cost;
+     int *old_hash;
+     int *new_hash;
+     int free_at_end;
+{
+  register int i, j;
+  int frame_height = FRAME_HEIGHT (frame);
+  register struct matrix_elt *p, *p1;
+  register int cost, cost1, delta;
+
+  /* first_insert_cost[-I] is the cost of doing the first insert-line
+     at a position I lines above the bottom line in the scroll window. */
+  int *first_insert_cost
+    = &FRAME_INSERT_COST (frame)[frame_height - 1];
+  int *first_delete_cost
+    = &FRAME_DELETE_COST (frame)[frame_height - 1];
+  int *next_insert_cost
+    = &FRAME_INSERTN_COST (frame)[frame_height - 1];
+  int *next_delete_cost
+    = &FRAME_DELETEN_COST (frame)[frame_height - 1];
+
+  int scroll_overhead;
+
+  /* Discourage long scrolls on fast lines.
+     Don't scroll nearly a full frame height unless it saves
+     at least 1/4 second.  */
+  int extra_cost = baud_rate / (10 * 4 * FRAME_HEIGHT (frame));
+
+  if (baud_rate <= 0)
+    extra_cost = 1;
+
+  /* Overhead of setting the scroll window, plus the extra cost
+     cost of scrolling by a distance of one.  The extra cost is
+     added once for consistency with the cost vectors */
+  scroll_overhead = scroll_region_cost + extra_cost;
+
+  /* initialize the top left corner of the matrix */
+  matrix->writecost = 0;
+  matrix->insertcost = INFINITY;
+  matrix->deletecost = INFINITY;
+  matrix->writecount = 0;
+  matrix->insertcount = 0;
+  matrix->deletecount = 0;
+
+  /* initialize the left edge of the matrix */
+  cost = 0;
+  for (i = 1; i <= window_size; i++)
+    {
+      p = matrix + i * (window_size + 1);
+      cost += draw_cost[i];
+      p->insertcost = cost;
+      p->writecost = INFINITY;
+      p->deletecost = INFINITY;
+      p->insertcount = i;
+      p->writecount = 0;
+      p->deletecount = 0;
+    }
+
+  /* initialize the top edge of the matrix */
+  for (j = 1; j <= window_size; j++)
+    {
+      matrix[j].deletecost = 0;
+      matrix[j].writecost = INFINITY;
+      matrix[j].insertcost = INFINITY;
+      matrix[j].deletecount = j;
+      matrix[j].writecount = 0;
+      matrix[j].insertcount = 0;
+    }
+
+  /* `i' represents the vpos among new frame contents.
+     `j' represents the vpos among the old frame contents.  */
+  p = matrix + window_size + 2;	/* matrix [1, 1] */
+
+  for (i = 1; i <= window_size; i++, p++)
+    for (j = 1; j <= window_size; j++, p++)
+      {
+	/* p contains the address of matrix [i, j] */
+
+	/* First calculate the cost assuming we do
+	   not insert or delete above this line.
+	   That is, if we update through line i-1
+	   based on old lines through j-1,
+	   and then just change old line j to new line i.
+
+	   Depending on which choice gives the lower cost,
+	   this usually involves either scrolling a single line
+	   or extending a sequence of scrolled lines, but
+	   when i == j, no scrolling is required. */
+	p1 = p - window_size - 2; /* matrix [i-1, j-1] */
+	cost = p1->insertcost;
+	if (cost > p1->deletecost)
+	  cost = p1->deletecost;
+	cost1 = p1->writecost;
+	if (i == j)
+	  {
+	    if (cost > cost1)
+	      {
+		cost = cost1;
+		p->writecount = p1->writecount + 1;
+	      }
+	    else
+	      p->writecount = 1;
+	    if (old_hash[j] != new_hash[i])
+	      {
+		cost += draw_cost[i];
+	      }
+	  }
+	else
+	  {
+	    if (i > j)
+	      {
+		delta = i - j;
+
+		/* The cost added here for scrolling the first line by
+		   a distance N includes the overhead of setting the
+		   scroll window, the cost of inserting N lines at a
+		   position N lines above the bottom line of the window,
+		   and an extra cost which is proportional to N. */
+		cost += scroll_overhead + first_insert_cost[-delta] +
+		  (delta-1) * (next_insert_cost[-delta] + extra_cost);
+
+		/* In the most general case, the insertion overhead and
+		   the multiply factor can grow linearly as the distance
+		   from the bottom of the window increases.  The incremental
+		   cost of scrolling an additional line depends upon the
+		   rate of change of these two parameters.  Each of these
+		   growth rates can be determined by a simple difference.
+		   To reduce the cumulative effects of rounding error, we
+		   vary the position at which the difference is computed. */
+		cost1 += first_insert_cost[-j] - first_insert_cost[1-j] +
+		  (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]); 
+	      }
+	    else
+	      {
+		delta = j - i;
+		cost += scroll_overhead + first_delete_cost[-delta] +
+		  (delta-1) * (next_delete_cost[-delta] + extra_cost);
+		cost1 += first_delete_cost[-i] - first_delete_cost[1-i] +
+		  (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]); 
+	      }
+	    if (cost1 < cost)
+	      {
+		cost = cost1;
+		p->writecount = p1->writecount + 1;
+	      }
+	    else
+	      p->writecount = 1;
+	    if (old_hash[j] != new_hash[i])
+	      {
+		cost += draw_cost[i] + old_draw_cost[j];
+	      }
+	  }
+	p->writecost = cost;
+
+	/* Calculate the cost if we do an insert-line
+	   before outputting this line.
+	   That is, we update through line i-1
+	   based on old lines through j,
+	   do an insert-line on line i,
+	   and then output line i from scratch,
+	   leaving old lines starting from j for reuse below.  */
+	p1 = p - window_size - 1; /* matrix [i-1, j] */
+	cost = p1->writecost;
+	/* If i > j, an insert is allowed after a delete. */
+	if (i > j && p1->deletecost < cost)
+	  cost = p1->deletecost;
+	if (p1->insertcost <= cost)
+	  {
+	    cost = p1->insertcost;
+	    p->insertcount = p1->insertcount + 1;
+	  }
+	else
+	  p->insertcount = 1;
+	cost += draw_cost[i];
+	p->insertcost = cost;
+
+	/* Calculate the cost if we do a delete line after
+	   outputting this line.
+	   That is, we update through line i
+	   based on old lines through j-1,
+	   and throw away old line j.  */
+	p1 = p - 1;		/* matrix [i, j-1] */
+	cost = p1->writecost;
+	/* If i < j, a delete is allowed after an insert. */
+	if (i < j && p1->insertcost < cost)
+	  cost = p1->insertcost;
+	cost1 = p1->deletecost;
+	if (p1->deletecost <= cost)
+	  {
+	    cost = p1->deletecost;
+	    p->deletecount = p1->deletecount + 1;
+	  }
+	else
+	  p->deletecount = 1;
+	p->deletecost = cost;
+      }
+}
+
+/* Perform insert-lines and delete-lines operations on FRAME according
+   to the costs in MATRIX, using the direct scrolling method.
+   Update the frame's current_glyphs info to record what was done.
+
+   WINDOW_SIZE is the number of lines being considered for scrolling
+   and UNCHANGED_AT_TOP is the vpos of the first line being considered.
+   These two arguments can specify any contiguous range of lines.
+ 
+   We also shuffle the charstarts vectors for the lines
+   along with the glyphs; but the results are not quite right,
+   since we cannot offset them for changes in amount of text
+   in this line or that line.  Luckily it doesn't matter,
+   since update_frame and update_line will copy in the proper
+   new charstarts vectors from the frame's desired_glyphs.
+
+   In the direct scrolling method, a new scroll window is selected
+   before each insertion or deletion, so that groups of lines can be
+   scrolled directly to their final vertical positions.  This method
+   is described in more detail in calculate_direct_scrolling,
+   where the cost matrix for this approach is constructed. */
+
+static void
+do_direct_scrolling (frame, matrix, window_size, unchanged_at_top)
+     FRAME_PTR frame;
+     struct matrix_elt *matrix;
+     int window_size;
+     int unchanged_at_top;
+{
+  register struct matrix_elt *p;
+  register int i, j;
+  register struct frame_glyphs *current_frame;
+  /* temp_frame->enable[i] means line i has been moved to current_frame.  */
+  register struct frame_glyphs *temp_frame;
+  struct alt_queue { int count, pos, window; } *queue;
+  int offset = unchanged_at_top;
+  int qi = 0;
+  int window = 0;
+  register int tem;
+  int next;
+
+  /* A nonzero value of write_follows indicates that a write has been
+     selected, allowing either an insert or a delete to be selected next.
+     When write_follows is zero, a delete cannot be selected unless j < i,
+     and an insert cannot be selected unless i < j.  This corresponds to
+     a similar restriction (with the ordering reversed) in
+     calculate_direct_scrolling, which is intended to ensure that lines
+     marked as inserted will be blank. */
+  int write_follows = 1;
+
+  queue = (struct alt_queue *) alloca (FRAME_HEIGHT (frame)
+				       * sizeof (struct alt_queue));
+
+  current_frame = FRAME_CURRENT_GLYPHS (frame);
+  temp_frame = FRAME_TEMP_GLYPHS (frame);
+
+  bcopy (current_frame->glyphs, temp_frame->glyphs,
+	 current_frame->height * sizeof (GLYPH *));
+  bcopy (current_frame->charstarts, temp_frame->charstarts,
+	 current_frame->height * sizeof (GLYPH *));
+  bcopy (current_frame->used, temp_frame->used,
+	 current_frame->height * sizeof (int));
+  bcopy (current_frame->highlight, temp_frame->highlight,
+	 current_frame->height * sizeof (char));
+  bzero (temp_frame->enable, temp_frame->height * sizeof (char));
+  bcopy (current_frame->bufp, temp_frame->bufp,
+	 current_frame->height * sizeof (int));
+
+#ifdef HAVE_X_WINDOWS
+  if (FRAME_X_P (frame))
+    {
+      bcopy (current_frame->top_left_x, temp_frame->top_left_x,
+	     current_frame->height * sizeof (short));
+      bcopy (current_frame->top_left_y, temp_frame->top_left_y,
+	     current_frame->height * sizeof (short));
+      bcopy (current_frame->pix_width, temp_frame->pix_width,
+	     current_frame->height * sizeof (short));
+      bcopy (current_frame->pix_height, temp_frame->pix_height,
+	     current_frame->height * sizeof (short));
+      bcopy (current_frame->max_ascent, temp_frame->max_ascent,
+	     current_frame->height * sizeof (short));
+    }
+#endif
+
+  i = j = window_size;
+
+  while (i > 0 || j > 0)
+    {
+      p = matrix + i * (window_size + 1) + j;
+      tem = p->insertcost;
+      if (tem < p->writecost && tem < p->deletecost
+	  && (write_follows || i < j))
+	{
+	  /* Insert should be done at vpos i-1, plus maybe some before.
+	     Setting count to 0 in the queue marks this as an insert. */
+	  write_follows = 0;
+	  queue[qi].window = i + unchanged_at_top;
+	  queue[qi].count = 0;
+	  i -= p->insertcount;
+	  queue[qi++].pos = i + unchanged_at_top;
+	}
+      else if (p->deletecost < p->writecost && (write_follows || i > j))
+	{
+	  /* Delete should be done at vpos j-1, plus maybe some before. */
+	  write_follows = 0;
+	  j -= p->deletecount;
+	}
+      else
+	{
+	  /* One or more lines should be retained. */
+	  write_follows = 1;
+	  tem = p->writecount;
+	  if (i > j)
+	    {
+	      /* Immediately scroll a group of lines downward */
+	      set_terminal_window (i + unchanged_at_top);
+	      window = 1;
+	      ins_del_lines (j - tem + unchanged_at_top, i - j);
+	    }
+	  else if (i < j)
+	    {
+	      /* Queue the upward scrolling of a group of lines */
+	      queue[qi].pos = i - tem + unchanged_at_top;
+	      queue[qi].window = j + unchanged_at_top;
+	      queue[qi++].count = i - j;
+	    }
+
+	  /* Now copy the line-contents strings */
+	  while (tem > 0)
+	    {
+	      i--;
+	      j--;
+	      tem--;
+	      current_frame->glyphs[i + offset]
+		= temp_frame->glyphs[j + offset];
+	      current_frame->charstarts[i + offset]
+		= temp_frame->charstarts[j + offset];
+	      current_frame->used[i + offset]
+		= temp_frame->used[j + offset];
+	      current_frame->highlight[i + offset]
+		= temp_frame->highlight[j + offset];
+
+	      temp_frame->enable[j + offset] = 1;
+	    }
+	}
+    }
+
+  /* Now do all the upward scrolling, and copy the line-contents
+     strings for the blank lines of the recorded inserts. */
+
+  next = unchanged_at_top;
+  for (i = qi - 1; i >= 0; i--)
+    {
+      if (queue[i].count)
+	{
+	  set_terminal_window (queue[i].window);
+	  window = 1;
+	  ins_del_lines (queue[i].pos, queue[i].count);
+	}
+      else
+	{
+	  /* Mark the inserted lines as clear,
+	     and put into them the line-contents strings
+	     that were discarded during the deletions.
+	     Those are the ones for which temp_frame->enable was not set. */
+	  tem = queue[i].pos;
+	  for (j = queue[i].window - 1; j >= tem; j--)
+	    {
+	      current_frame->enable[j] = 0;
+	      while (temp_frame->enable[next])
+		next++;
+	      current_frame->glyphs[j] = temp_frame->glyphs[next];
+	      current_frame->charstarts[j] = temp_frame->charstarts[next++];
+	    }
+	}
+    }
+
+  if (window)
+    set_terminal_window (0);
+}
+
 void
 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
-	     draw_cost, old_hash, new_hash, free_at_end)
+	     draw_cost, old_draw_cost, old_hash, new_hash, free_at_end)
      FRAME_PTR frame;
      int window_size, unchanged_at_top, unchanged_at_bottom;
      int *draw_cost;
+     int *old_draw_cost;
      int *old_hash;
      int *new_hash;
      int free_at_end;
@@ -375,10 +806,21 @@ scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
   matrix = ((struct matrix_elt *)
 	    alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
 
-  calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
-		       draw_cost, old_hash, new_hash,
-		       free_at_end);
-  do_scrolling (frame, matrix, window_size, unchanged_at_top);
+  if (scroll_region_ok)
+    {
+      calculate_direct_scrolling (frame, matrix, window_size,
+				  unchanged_at_bottom,
+				  draw_cost, old_draw_cost, 
+				  old_hash, new_hash, free_at_end);
+      do_direct_scrolling (frame, matrix, window_size, unchanged_at_top);
+    }
+  else
+    {
+      calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
+			   draw_cost, old_hash, new_hash,
+			   free_at_end);
+      do_scrolling (frame, matrix, window_size, unchanged_at_top);
+    }
 }
 
 /* Return number of lines in common between current and desired frame contents