src/scroll.c

   1 /* Calculate what line insertion or deletion to do, and do it,
   2    Copyright (C) 1985, 1986, 1990, 1993 Free Software Foundation, Inc.
   3
   4 This file is part of GNU Emacs.
   5
   6 GNU Emacs is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU Emacs is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU Emacs; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19
  20
  21 #include <config.h>
  22 #include "termchar.h"
  23 #include "lisp.h"
  24 #include "dispextern.h"
  25 #include "frame.h"
  26
  27 extern struct display_line **ophys_lines;
  28
  29 #define max(a, b) ((a) > (b) ? (a) : (b))
  30 #define min(a, b) ((a) < (b) ? (a) : (b))
  31
  32 /* All costs measured in characters.
  33    So no cost can exceed the area of a frame, measured in characters.
  34    Let's hope this is never more than 15000 characters.  */
  35
  36 #define INFINITY 15000
  37
  38 struct matrix_elt
  39   {
  40     /* Cost of outputting through this line
  41        if no insert/delete is done just above it.  */
  42     short writecost;
  43     /* Cost of outputting through this line
  44        if an insert is done just above it.  */
  45     short insertcost;
  46     /* Cost of outputting through this line
  47        if a delete is done just above it.  */
  48     short deletecost;
  49     /* Number of inserts so far in this run of inserts,
  50        for the cost in insertcost.  */
  51     char insertcount;
  52     /* Number of deletes so far in this run of deletes,
  53        for the cost in deletecost.  */
  54     char deletecount;
  55   };
  56
  57 \f
  58 /* Determine, in matrix[i,j], the cost of updating the first j old lines
  59    into the first i new lines.
  60    This involves using insert or delete somewhere if i != j.
  61    For each matrix elements, three kinds of costs are recorded:
  62    the smallest cost that ends with an insert, the smallest
  63    cost that ends with a delete, and the smallest cost that
  64    ends with neither one.  These are kept separate because
  65    on some terminals the cost of doing an insert varies
  66    depending on whether one was just done, etc.  */
  67
  68 /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
  69    old_hash[VPOS] is the hash code of the old line at VPOS.
  70    new_hash[VPOS] is the hash code of the new line at VPOS.
  71    Note that these are not true frame vpos's, but relative
  72    to the place at which the first mismatch between old and
  73    new contents appears.  */
  74
  75 static void
  76 calculate_scrolling (frame, matrix, window_size, lines_below,
  77                      draw_cost, old_hash, new_hash,
  78                      free_at_end)
  79      FRAME_PTR frame;
  80      /* matrix is of size window_size + 1 on each side.  */
  81      struct matrix_elt *matrix;
  82      int window_size;
  83      int *draw_cost;
  84      int *old_hash;
  85      int *new_hash;
  86      int free_at_end;
  87 {
  88   register int i, j;
  89   int frame_height = FRAME_HEIGHT (frame);
  90   register struct matrix_elt *p, *p1;
  91   register int cost, cost1;
  92
  93   int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
  94   /* first_insert_cost[I] is the cost of doing the first insert-line
  95      at the I'th line of the lines we are considering,
  96      where I is origin 1 (as it is below).  */
  97   int *first_insert_cost
  98     = &FRAME_INSERT_COST (frame)[frame_height - 1 - lines_moved];
  99   int *first_delete_cost
 100     = &FRAME_DELETE_COST (frame)[frame_height - 1 - lines_moved];
 101   int *next_insert_cost
 102     = &FRAME_INSERTN_COST (frame)[frame_height - 1 - lines_moved];
 103   int *next_delete_cost
 104     = &FRAME_DELETEN_COST (frame)[frame_height - 1 - lines_moved];
 105
 106   /* Discourage long scrolls on fast lines.
 107      Don't scroll nearly a full frame height unless it saves
 108      at least 1/4 second.  */
 109   int extra_cost = baud_rate / (10 * 4 * FRAME_HEIGHT (frame));
 110
 111   if (baud_rate <= 0)
 112     extra_cost = 1;
 113
 114   /* initialize the top left corner of the matrix */
 115   matrix->writecost = 0;
 116   matrix->insertcost = INFINITY;
 117   matrix->deletecost = INFINITY;
 118   matrix->insertcount = 0;
 119   matrix->deletecount = 0;
 120
 121   /* initialize the left edge of the matrix */
 122   cost = first_insert_cost[1] - next_insert_cost[1];
 123   for (i = 1; i <= window_size; i++)
 124     {
 125       p = matrix + i * (window_size + 1);
 126       cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
 127       p->insertcost = cost;
 128       p->writecost = INFINITY;
 129       p->deletecost = INFINITY;
 130       p->insertcount = i;
 131       p->deletecount = 0;
 132     }
 133
 134   /* initialize the top edge of the matrix */
 135   cost = first_delete_cost[1] - next_delete_cost[1];
 136   for (j = 1; j <= window_size; j++)
 137     {
 138       cost += next_delete_cost[j];
 139       matrix[j].deletecost = cost;
 140       matrix[j].writecost = INFINITY;
 141       matrix[j].insertcost = INFINITY;
 142       matrix[j].deletecount = j;
 143       matrix[j].insertcount = 0;
 144     }
 145
 146   /* `i' represents the vpos among new frame contents.
 147      `j' represents the vpos among the old frame contents.  */
 148   p = matrix + window_size + 2; /* matrix [1, 1] */
 149   for (i = 1; i <= window_size; i++, p++)
 150     for (j = 1; j <= window_size; j++, p++)
 151       {
 152         /* p contains the address of matrix [i, j] */
 153
 154         /* First calculate the cost assuming we do
 155            not insert or delete above this line.
 156            That is, if we update through line i-1
 157            based on old lines through j-1,
 158            and then just change old line j to new line i.  */
 159         p1 = p - window_size - 2; /* matrix [i-1, j-1] */
 160         cost = p1->writecost;
 161         if (cost > p1->insertcost)
 162           cost = p1->insertcost;
 163         if (cost > p1->deletecost)
 164           cost = p1->deletecost;
 165         if (old_hash[j] != new_hash[i])
 166           cost += draw_cost[i];
 167         p->writecost = cost;
 168
 169         /* Calculate the cost if we do an insert-line
 170            before outputting this line.
 171            That is, we update through line i-1
 172            based on old lines through j,
 173            do an insert-line on line i,
 174            and then output line i from scratch,
 175            leaving old lines starting from j for reuse below.  */
 176         p1 = p - window_size - 1; /* matrix [i-1, j] */
 177         /* No need to think about doing a delete followed
 178            immediately by an insert.  It cannot be as good
 179            as not doing either of them.  */
 180         if (free_at_end == i)
 181           {
 182             cost = p1->writecost;
 183             cost1 = p1->insertcost;
 184           }
 185         else
 186           {
 187             cost = p1->writecost + first_insert_cost[i];
 188             if (p1->insertcount > i)
 189               abort ();
 190             cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
 191           }
 192         p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
 193         p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
 194         if (p->insertcount > i)
 195           abort ();
 196
 197         /* Calculate the cost if we do a delete line after
 198            outputting this line.
 199            That is, we update through line i
 200            based on old lines through j-1,
 201            and throw away old line j.  */
 202         p1 = p - 1;             /* matrix [i, j-1] */
 203         /* No need to think about doing an insert followed
 204            immediately by a delete.  */
 205         if (free_at_end == i)
 206           {
 207             cost = p1->writecost;
 208             cost1 = p1->deletecost;
 209           }
 210         else
 211           {
 212             cost = p1->writecost + first_delete_cost[i];
 213             cost1 = p1->deletecost + next_delete_cost[i];
 214           }
 215         p->deletecost = min (cost, cost1);
 216         p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
 217       }
 218 }
 219 \f
 220 /* Perform insert-lines and delete-lines operations
 221  according to the costs in the matrix.
 222  Updates the contents of the frame to record what was done. */
 223
 224 static void
 225 do_scrolling (frame, matrix, window_size, unchanged_at_top)
 226      FRAME_PTR frame;
 227      struct matrix_elt *matrix;
 228      int window_size;
 229      int unchanged_at_top;
 230 {
 231   register struct matrix_elt *p;
 232   register int i, j;
 233   register struct frame_glyphs *current_frame;
 234   /* temp_frame->enable[i] means line i has been moved to current_frame.  */
 235   register struct frame_glyphs *temp_frame;
 236   struct queue { int count, pos; } *queue;
 237   int offset = unchanged_at_top;
 238   int qi = 0;
 239   int window = 0;
 240   register int tem;
 241   int next;
 242
 243   queue = (struct queue *) alloca (FRAME_HEIGHT (frame)
 244                                    * sizeof (struct queue));
 245
 246   current_frame = FRAME_CURRENT_GLYPHS (frame);
 247   temp_frame = FRAME_TEMP_GLYPHS (frame);
 248
 249   bcopy (current_frame->glyphs, temp_frame->glyphs,
 250          current_frame->height * sizeof (GLYPH *));
 251   bcopy (current_frame->used, temp_frame->used,
 252          current_frame->height * sizeof (int));
 253   bcopy (current_frame->highlight, temp_frame->highlight,
 254          current_frame->height * sizeof (char));
 255   bzero (temp_frame->enable, temp_frame->height * sizeof (char));
 256   bcopy (current_frame->bufp, temp_frame->bufp,
 257          current_frame->height * sizeof (int));
 258
 259 #ifdef HAVE_X_WINDOWS
 260   if (FRAME_X_P (frame))
 261     {
 262       bcopy (current_frame->top_left_x, temp_frame->top_left_x,
 263              current_frame->height * sizeof (short));
 264       bcopy (current_frame->top_left_y, temp_frame->top_left_y,
 265              current_frame->height * sizeof (short));
 266       bcopy (current_frame->pix_width, temp_frame->pix_width,
 267              current_frame->height * sizeof (short));
 268       bcopy (current_frame->pix_height, temp_frame->pix_height,
 269              current_frame->height * sizeof (short));
 270       bcopy (current_frame->max_ascent, temp_frame->max_ascent,
 271              current_frame->height * sizeof (short));
 272     }
 273 #endif
 274
 275   i = j = window_size;
 276
 277   while (i > 0 || j > 0)
 278     {
 279       p = matrix + i * (window_size + 1) + j;
 280       tem = p->insertcost;
 281       if (tem < p->writecost && tem < p->deletecost)
 282         {
 283           /* Insert should be done at vpos i-1, plus maybe some before */
 284           queue[qi].count = p->insertcount;
 285           i -= p->insertcount;
 286           queue[qi++].pos = i + unchanged_at_top;
 287         }
 288       else if (p->deletecost < p->writecost)
 289         {
 290           /* Old line at vpos j-1, and maybe some before it,
 291              should be deleted */
 292           j -= p->deletecount;
 293           if (!window)
 294             {
 295               set_terminal_window (window_size + unchanged_at_top);
 296               window = 1;
 297             }
 298           ins_del_lines (j + unchanged_at_top, - p->deletecount);
 299         }
 300       else
 301         {
 302           /* Best thing done here is no insert or delete */
 303           /* Old line at vpos j-1 ends up at vpos i-1 */
 304           current_frame->glyphs[i + offset - 1]
 305             = temp_frame->glyphs[j + offset - 1];
 306           current_frame->used[i + offset - 1]
 307             = temp_frame->used[j + offset - 1];
 308           current_frame->highlight[i + offset - 1]
 309             = temp_frame->highlight[j + offset - 1];
 310
 311           temp_frame->enable[j + offset - 1] = 1;
 312           i--;
 313           j--;
 314         }
 315     }
 316
 317   if (!window && qi)
 318     {
 319       set_terminal_window (window_size + unchanged_at_top);
 320       window = 1;
 321     }
 322
 323   /* Now do all insertions */
 324
 325   next = unchanged_at_top;
 326   for (i = qi - 1; i >= 0; i--)
 327     {
 328       ins_del_lines (queue[i].pos, queue[i].count);
 329
 330       /* Mark the inserted lines as clear,
 331          and put into them the line-contents strings
 332          that were discarded during the deletions.
 333          Those are the ones for which temp_frame->enable was not set.  */
 334       tem = queue[i].pos;
 335       for (j = tem + queue[i].count - 1; j >= tem; j--)
 336         {
 337           current_frame->enable[j] = 0;
 338           while (temp_frame->enable[next])
 339             next++;
 340           current_frame->glyphs[j] = temp_frame->glyphs[next++];
 341         }
 342     }
 343
 344   if (window)
 345     set_terminal_window (0);
 346 }
 347 \f
 348 void
 349 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
 350              draw_cost, old_hash, new_hash, free_at_end)
 351      FRAME_PTR frame;
 352      int window_size, unchanged_at_top, unchanged_at_bottom;
 353      int *draw_cost;
 354      int *old_hash;
 355      int *new_hash;
 356      int free_at_end;
 357 {
 358   struct matrix_elt *matrix;
 359   matrix = ((struct matrix_elt *)
 360             alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
 361
 362   calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
 363                        draw_cost, old_hash, new_hash,
 364                        free_at_end);
 365   do_scrolling (frame, matrix, window_size, unchanged_at_top);
 366 }
 367 \f
 368 /* Return number of lines in common between current and desired frame contents
 369    described to us only as vectors of hash codes OLDHASH and NEWHASH.
 370    Consider only vpos range START to END (not including END).
 371    Ignore short lines on the assumption that
 372    avoiding redrawing such a line will have little weight.  */
 373
 374 int
 375 scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
 376      int start, end;
 377      int *oldhash, *newhash, *cost;
 378 {
 379   struct { int hash; int count; } lines[01000];
 380   register int i, h;
 381   register int matchcount = 0;
 382   int avg_length = 0;
 383   int threshold;
 384
 385   /* Compute a threshold which is 1/4 of average length of these lines.  */
 386
 387   for (i = start; i < end; i++)
 388     avg_length += cost[i];
 389
 390   avg_length /= end - start;
 391   threshold = avg_length / 4;
 392
 393   bzero (lines, sizeof lines);
 394
 395   /* Put new lines' hash codes in hash table.
 396      Ignore lines shorter than the threshold.
 397      Thus, if the lines that are in common
 398      are mainly the ones that are short,
 399      they won't count.  */
 400   for (i = start; i < end; i++)
 401     {
 402       if (cost[i] > threshold)
 403         {
 404           h = newhash[i] & 0777;
 405           lines[h].hash = newhash[i];
 406           lines[h].count++;
 407         }
 408     }
 409
 410   /* Look up old line hash codes in the hash table.
 411      Count number of matches between old lines and new.  */
 412
 413   for (i = start; i < end; i++)
 414     {
 415       h = oldhash[i] & 0777;
 416       if (oldhash[i] == lines[h].hash)
 417         {
 418           matchcount++;
 419           if (--lines[h].count == 0)
 420             lines[h].hash = 0;
 421         }
 422     }
 423
 424   return matchcount;
 425 }
 426 \f
 427 /* Return a measure of the cost of moving the lines
 428    starting with vpos FROM, up to but not including vpos TO,
 429    down by AMOUNT lines (AMOUNT may be negative).
 430    These are the same arguments that might be given to
 431    scroll_frame_lines to perform this scrolling.  */
 432
 433 scroll_cost (frame, from, to, amount)
 434      FRAME_PTR frame;
 435      int from, to, amount;
 436 {
 437   /* Compute how many lines, at bottom of frame,
 438      will not be involved in actual motion.  */
 439   int limit = to;
 440   int offset;
 441   int height = FRAME_HEIGHT (frame);
 442
 443   if (amount == 0)
 444     return 0;
 445
 446   if (! scroll_region_ok)
 447     limit = height;
 448   else if (amount > 0)
 449     limit += amount;
 450
 451   if (amount < 0)
 452     {
 453       int temp = to;
 454       to = from + amount;
 455       from = temp + amount;
 456       amount = - amount;
 457     }
 458
 459   offset = height - limit;
 460
 461   return
 462     (FRAME_INSERT_COST (frame)[offset + from]
 463      + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
 464      + FRAME_DELETEN_COST (frame)[offset + to]
 465      + (amount - 1) * FRAME_DELETE_COST (frame)[offset + to]);
 466 }
 467 \f
 468 /* Calculate the line insertion/deletion
 469    overhead and multiply factor values */
 470
 471 static void
 472 line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
 473      FRAME_PTR frame;
 474      int ov1, ovn;
 475      int pf1, pfn;
 476      register int *ov, *mf;
 477 {
 478   register int i;
 479   register int frame_height = FRAME_HEIGHT (frame);
 480   register int insert_overhead = ov1 * 10;
 481   register int next_insert_cost = ovn * 10;
 482
 483   for (i = frame_height-1; i >= 0; i--)
 484     {
 485       mf[i] = next_insert_cost / 10;
 486       next_insert_cost += pfn;
 487       ov[i] = (insert_overhead + next_insert_cost) / 10;
 488       insert_overhead += pf1;
 489     }
 490 }
 491
 492 static void
 493 ins_del_costs (frame,
 494                one_line_string, multi_string,
 495                setup_string, cleanup_string,
 496                costvec, ncostvec, coefficient)
 497      FRAME_PTR frame;
 498      char *one_line_string, *multi_string;
 499      char *setup_string, *cleanup_string;
 500      int *costvec, *ncostvec;
 501      int coefficient;
 502 {
 503   if (multi_string)
 504     line_ins_del (frame,
 505                   string_cost (multi_string) * coefficient,
 506                   per_line_cost (multi_string) * coefficient,
 507                   0, 0, costvec, ncostvec);
 508   else if (one_line_string)
 509     line_ins_del (frame,
 510                   string_cost (setup_string) + string_cost (cleanup_string), 0,
 511                   string_cost (one_line_string),
 512                   per_line_cost (one_line_string),
 513                   costvec, ncostvec);
 514   else
 515     line_ins_del (frame,
 516                   9999, 0, 9999, 0,
 517                   costvec, ncostvec);
 518 }
 519
 520 /* Calculate the insert and delete line costs.
 521    Note that this is done even when running with a window system
 522    because we want to know how long scrolling takes (and avoid it).
 523    This must be redone whenever the frame height changes.
 524
 525    We keep the ID costs in a precomputed array based on the position
 526    at which the I or D is performed.  Also, there are two kinds of ID
 527    costs: the "once-only" and the "repeated".  This is to handle both
 528    those terminals that are able to insert N lines at a time (once-
 529    only) and those that must repeatedly insert one line.
 530
 531    The cost to insert N lines at line L is
 532             [tt.t_ILov  + (frame_height + 1 - L) * tt.t_ILpf] +
 533         N * [tt.t_ILnov + (frame_height + 1 - L) * tt.t_ILnpf]
 534
 535    ILov represents the basic insert line overhead.  ILpf is the padding
 536    required to allow the terminal time to move a line: insertion at line
 537    L changes (frame_height + 1 - L) lines.
 538
 539    The first bracketed expression above is the overhead; the second is
 540    the multiply factor.  Both are dependent only on the position at
 541    which the insert is performed.  We store the overhead in
 542    FRAME_INSERT_COST (frame) and the multiply factor in
 543    FRAME_INSERTN_COST (frame).  Note however that any insertion
 544    must include at least one multiply factor.  Rather than compute this
 545    as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
 546    we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
 547    This is reasonable because of the particular algorithm used in calcM.
 548
 549    Deletion is essentially the same as insertion.
 550  */
 551
 552 do_line_insertion_deletion_costs (frame,
 553                                   ins_line_string, multi_ins_string,
 554                                   del_line_string, multi_del_string,
 555                                   setup_string, cleanup_string, coefficient)
 556      FRAME_PTR frame;
 557      char *ins_line_string, *multi_ins_string;
 558      char *del_line_string, *multi_del_string;
 559      char *setup_string, *cleanup_string;
 560      int coefficient;
 561 {
 562   if (FRAME_INSERT_COST (frame) != 0)
 563     {
 564       FRAME_INSERT_COST (frame) =
 565         (int *) xrealloc (FRAME_INSERT_COST (frame),
 566                           FRAME_HEIGHT (frame) * sizeof (int));
 567       FRAME_DELETEN_COST (frame) =
 568         (int *) xrealloc (FRAME_DELETEN_COST (frame),
 569                           FRAME_HEIGHT (frame) * sizeof (int));
 570       FRAME_INSERTN_COST (frame) =
 571         (int *) xrealloc (FRAME_INSERTN_COST (frame),
 572                           FRAME_HEIGHT (frame) * sizeof (int));
 573       FRAME_DELETE_COST (frame) =
 574         (int *) xrealloc (FRAME_DELETE_COST (frame),
 575                           FRAME_HEIGHT (frame) * sizeof (int));
 576     }
 577   else
 578     {
 579       FRAME_INSERT_COST (frame) =
 580         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 581       FRAME_DELETEN_COST (frame) =
 582         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 583       FRAME_INSERTN_COST (frame) =
 584         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 585       FRAME_DELETE_COST (frame) =
 586         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 587     }
 588
 589   ins_del_costs (frame,
 590                  ins_line_string, multi_ins_string,
 591                  setup_string, cleanup_string,
 592                  FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
 593                  coefficient);
 594   ins_del_costs (frame,
 595                  del_line_string, multi_del_string,
 596                  setup_string, cleanup_string,
 597                  FRAME_DELETEN_COST (frame), FRAME_DELETE_COST (frame),
 598                  coefficient);
 599 }