src/scroll.c

   1 /* Calculate what line insertion or deletion to do, and do it,
   2    Copyright (C) 1985, 1986, 1990, 1992 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   /* initialize the top left corner of the matrix */
 112   matrix->writecost = 0;
 113   matrix->insertcost = INFINITY;
 114   matrix->deletecost = INFINITY;
 115   matrix->insertcount = 0;
 116   matrix->deletecount = 0;
 117
 118   /* initialize the left edge of the matrix */
 119   cost = first_insert_cost[1] - next_insert_cost[1];
 120   for (i = 1; i <= window_size; i++)
 121     {
 122       p = matrix + i * (window_size + 1);
 123       cost += draw_cost[i] + next_insert_cost[i] + extra_cost;
 124       p->insertcost = cost;
 125       p->writecost = INFINITY;
 126       p->deletecost = INFINITY;
 127       p->insertcount = i;
 128       p->deletecount = 0;
 129     }
 130
 131   /* initialize the top edge of the matrix */
 132   cost = first_delete_cost[1] - next_delete_cost[1];
 133   for (j = 1; j <= window_size; j++)
 134     {
 135       cost += next_delete_cost[j];
 136       matrix[j].deletecost = cost;
 137       matrix[j].writecost = INFINITY;
 138       matrix[j].insertcost = INFINITY;
 139       matrix[j].deletecount = j;
 140       matrix[j].insertcount = 0;
 141     }
 142
 143   /* `i' represents the vpos among new frame contents.
 144      `j' represents the vpos among the old frame contents.  */
 145   p = matrix + window_size + 2; /* matrix [1, 1] */
 146   for (i = 1; i <= window_size; i++, p++)
 147     for (j = 1; j <= window_size; j++, p++)
 148       {
 149         /* p contains the address of matrix [i, j] */
 150
 151         /* First calculate the cost assuming we do
 152            not insert or delete above this line.
 153            That is, if we update through line i-1
 154            based on old lines through j-1,
 155            and then just change old line j to new line i.  */
 156         p1 = p - window_size - 2; /* matrix [i-1, j-1] */
 157         cost = p1->writecost;
 158         if (cost > p1->insertcost)
 159           cost = p1->insertcost;
 160         if (cost > p1->deletecost)
 161           cost = p1->deletecost;
 162         if (old_hash[j] != new_hash[i])
 163           cost += draw_cost[i];
 164         p->writecost = cost;
 165
 166         /* Calculate the cost if we do an insert-line
 167            before outputting this line.
 168            That is, we update through line i-1
 169            based on old lines through j,
 170            do an insert-line on line i,
 171            and then output line i from scratch,
 172            leaving old lines starting from j for reuse below.  */
 173         p1 = p - window_size - 1; /* matrix [i-1, j] */
 174         /* No need to think about doing a delete followed
 175            immediately by an insert.  It cannot be as good
 176            as not doing either of them.  */
 177         if (free_at_end == i)
 178           {
 179             cost = p1->writecost;
 180             cost1 = p1->insertcost;
 181           }
 182         else
 183           {
 184             cost = p1->writecost + first_insert_cost[i];
 185             if (p1->insertcount > i)
 186               abort ();
 187             cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
 188           }
 189         p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost;
 190         p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
 191         if (p->insertcount > i)
 192           abort ();
 193
 194         /* Calculate the cost if we do a delete line after
 195            outputting this line.
 196            That is, we update through line i
 197            based on old lines through j-1,
 198            and throw away old line j.  */
 199         p1 = p - 1;             /* matrix [i, j-1] */
 200         /* No need to think about doing an insert followed
 201            immediately by a delete.  */
 202         if (free_at_end == i)
 203           {
 204             cost = p1->writecost;
 205             cost1 = p1->deletecost;
 206           }
 207         else
 208           {
 209             cost = p1->writecost + first_delete_cost[i];
 210             cost1 = p1->deletecost + next_delete_cost[i];
 211           }
 212         p->deletecost = min (cost, cost1);
 213         p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
 214       }
 215 }
 216 \f
 217 /* Perform insert-lines and delete-lines operations
 218  according to the costs in the matrix.
 219  Updates the contents of the frame to record what was done. */
 220
 221 static void
 222 do_scrolling (frame, matrix, window_size, unchanged_at_top)
 223      FRAME_PTR frame;
 224      struct matrix_elt *matrix;
 225      int window_size;
 226      int unchanged_at_top;
 227 {
 228   register struct matrix_elt *p;
 229   register int i, j;
 230   register struct frame_glyphs *current_frame;
 231   /* temp_frame->enable[i] means line i has been moved to current_frame.  */
 232   register struct frame_glyphs *temp_frame;
 233   struct queue { int count, pos; } *queue;
 234   int offset = unchanged_at_top;
 235   int qi = 0;
 236   int window = 0;
 237   register int tem;
 238   int next;
 239
 240   queue = (struct queue *) alloca (FRAME_HEIGHT (frame)
 241                                    * sizeof (struct queue));
 242
 243   current_frame = FRAME_CURRENT_GLYPHS (frame);
 244   temp_frame = FRAME_TEMP_GLYPHS (frame);
 245
 246   bcopy (current_frame->glyphs, temp_frame->glyphs,
 247          current_frame->height * sizeof (GLYPH *));
 248   bcopy (current_frame->used, temp_frame->used,
 249          current_frame->height * sizeof (int));
 250   bcopy (current_frame->highlight, temp_frame->highlight,
 251          current_frame->height * sizeof (char));
 252   bzero (temp_frame->enable, temp_frame->height * sizeof (char));
 253   bcopy (current_frame->bufp, temp_frame->bufp,
 254          current_frame->height * sizeof (int));
 255
 256 #ifdef HAVE_X_WINDOWS
 257   if (FRAME_IS_X (frame))
 258     {
 259       bcopy (current_frame->nruns, temp_frame->nruns,
 260              current_frame->height * sizeof (int));
 261       bcopy (current_frame->face_list, temp_frame->face_list,
 262              current_frame->height * sizeof (struct run *));
 263       bcopy (current_frame->top_left_x, temp_frame->top_left_x,
 264              current_frame->height * sizeof (short));
 265       bcopy (current_frame->top_left_y, temp_frame->top_left_y,
 266              current_frame->height * sizeof (short));
 267       bcopy (current_frame->pix_width, temp_frame->pix_width,
 268              current_frame->height * sizeof (short));
 269       bcopy (current_frame->pix_height, temp_frame->pix_height,
 270              current_frame->height * sizeof (short));
 271     }
 272 #endif
 273
 274   i = j = window_size;
 275
 276   while (i > 0 || j > 0)
 277     {
 278       p = matrix + i * (window_size + 1) + j;
 279       tem = p->insertcost;
 280       if (tem < p->writecost && tem < p->deletecost)
 281         {
 282           /* Insert should be done at vpos i-1, plus maybe some before */
 283           queue[qi].count = p->insertcount;
 284           i -= p->insertcount;
 285           queue[qi++].pos = i + unchanged_at_top;
 286         }
 287       else if (p->deletecost < p->writecost)
 288         {
 289           /* Old line at vpos j-1, and maybe some before it,
 290              should be deleted */
 291           j -= p->deletecount;
 292           if (!window)
 293             {
 294               set_terminal_window (window_size + unchanged_at_top);
 295               window = 1;
 296             }
 297           ins_del_lines (j + unchanged_at_top, - p->deletecount);
 298         }
 299       else
 300         {
 301           /* Best thing done here is no insert or delete */
 302           /* Old line at vpos j-1 ends up at vpos i-1 */
 303           current_frame->glyphs[i + offset - 1]
 304             = temp_frame->glyphs[j + offset - 1];
 305           current_frame->used[i + offset - 1]
 306             = temp_frame->used[j + offset - 1];
 307           current_frame->highlight[i + offset - 1]
 308             = temp_frame->highlight[j + offset - 1];
 309
 310           temp_frame->enable[j + offset - 1] = 1;
 311           i--;
 312           j--;
 313         }
 314     }
 315
 316   if (!window && qi)
 317     {
 318       set_terminal_window (window_size + unchanged_at_top);
 319       window = 1;
 320     }
 321
 322   /* Now do all insertions */
 323
 324   next = unchanged_at_top;
 325   for (i = qi - 1; i >= 0; i--)
 326     {
 327       ins_del_lines (queue[i].pos, queue[i].count);
 328
 329       /* Mark the inserted lines as clear,
 330          and put into them the line-contents strings
 331          that were discarded during the deletions.
 332          Those are the ones for which temp_frame->enable was not set.  */
 333       tem = queue[i].pos;
 334       for (j = tem + queue[i].count - 1; j >= tem; j--)
 335         {
 336           current_frame->enable[j] = 0;
 337           while (temp_frame->enable[next])
 338             next++;
 339           current_frame->glyphs[j] = temp_frame->glyphs[next++];
 340         }
 341     }
 342
 343   if (window)
 344     set_terminal_window (0);
 345 }
 346 \f
 347 void
 348 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
 349              draw_cost, old_hash, new_hash, free_at_end)
 350      FRAME_PTR frame;
 351      int window_size, unchanged_at_top, unchanged_at_bottom;
 352      int *draw_cost;
 353      int *old_hash;
 354      int *new_hash;
 355      int free_at_end;
 356 {
 357   struct matrix_elt *matrix;
 358   matrix = ((struct matrix_elt *)
 359             alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
 360
 361   calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
 362                        draw_cost, old_hash, new_hash,
 363                        free_at_end);
 364   do_scrolling (frame, matrix, window_size, unchanged_at_top);
 365 }
 366 \f
 367 /* Return number of lines in common between current and desired frame contents
 368    described to us only as vectors of hash codes OLDHASH and NEWHASH.
 369    Consider only vpos range START to END (not including END).
 370    Ignore short lines on the assumption that
 371    avoiding redrawing such a line will have little weight.  */
 372
 373 int
 374 scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
 375      int start, end;
 376      int *oldhash, *newhash, *cost;
 377 {
 378   struct { int hash; int count; } lines[01000];
 379   register int i, h;
 380   register int matchcount = 0;
 381   int avg_length = 0;
 382   int threshold;
 383
 384   /* Compute a threshold which is 1/4 of average length of these lines.  */
 385
 386   for (i = start; i < end; i++)
 387     avg_length += cost[i];
 388
 389   avg_length /= end - start;
 390   threshold = avg_length / 4;
 391
 392   bzero (lines, sizeof lines);
 393
 394   /* Put new lines' hash codes in hash table.
 395      Ignore lines shorter than the threshold.
 396      Thus, if the lines that are in common
 397      are mainly the ones that are short,
 398      they won't count.  */
 399   for (i = start; i < end; i++)
 400     {
 401       if (cost[i] > threshold)
 402         {
 403           h = newhash[i] & 0777;
 404           lines[h].hash = newhash[i];
 405           lines[h].count++;
 406         }
 407     }
 408
 409   /* Look up old line hash codes in the hash table.
 410      Count number of matches between old lines and new.  */
 411
 412   for (i = start; i < end; i++)
 413     {
 414       h = oldhash[i] & 0777;
 415       if (oldhash[i] == lines[h].hash)
 416         {
 417           matchcount++;
 418           if (--lines[h].count == 0)
 419             lines[h].hash = 0;
 420         }
 421     }
 422
 423   return matchcount;
 424 }
 425 \f
 426 /* Return a measure of the cost of moving the lines
 427    starting with vpos FROM, up to but not including vpos TO,
 428    down by AMOUNT lines (AMOUNT may be negative).
 429    These are the same arguments that might be given to
 430    scroll_frame_lines to perform this scrolling.  */
 431
 432 scroll_cost (frame, from, to, amount)
 433      FRAME_PTR frame;
 434      int from, to, amount;
 435 {
 436   /* Compute how many lines, at bottom of frame,
 437      will not be involved in actual motion.  */
 438   int limit = to;
 439   int offset;
 440   int height = FRAME_HEIGHT (frame);
 441
 442   if (amount == 0)
 443     return 0;
 444
 445   if (! scroll_region_ok)
 446     limit = height;
 447   else if (amount > 0)
 448     limit += amount;
 449
 450   if (amount < 0)
 451     {
 452       int temp = to;
 453       to = from + amount;
 454       from = temp + amount;
 455       amount = - amount;
 456     }
 457
 458   offset = height - limit;
 459
 460   return
 461     (FRAME_INSERT_COST (frame)[offset + from]
 462      + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
 463      + FRAME_DELETEN_COST (frame)[offset + to]
 464      + (amount - 1) * FRAME_DELETE_COST (frame)[offset + to]);
 465 }
 466 \f
 467 /* Calculate the line insertion/deletion
 468    overhead and multiply factor values */
 469
 470 static void
 471 line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
 472      FRAME_PTR frame;
 473      int ov1, ovn;
 474      int pf1, pfn;
 475      register int *ov, *mf;
 476 {
 477   register int i;
 478   register int frame_height = FRAME_HEIGHT (frame);
 479   register int insert_overhead = ov1 * 10;
 480   register int next_insert_cost = ovn * 10;
 481
 482   for (i = frame_height-1; i >= 0; i--)
 483     {
 484       mf[i] = next_insert_cost / 10;
 485       next_insert_cost += pfn;
 486       ov[i] = (insert_overhead + next_insert_cost) / 10;
 487       insert_overhead += pf1;
 488     }
 489 }
 490
 491 static void
 492 ins_del_costs (frame,
 493                one_line_string, multi_string,
 494                setup_string, cleanup_string,
 495                costvec, ncostvec, coefficient)
 496      FRAME_PTR frame;
 497      char *one_line_string, *multi_string;
 498      char *setup_string, *cleanup_string;
 499      int *costvec, *ncostvec;
 500      int coefficient;
 501 {
 502   if (multi_string)
 503     line_ins_del (frame,
 504                   string_cost (multi_string) * coefficient,
 505                   per_line_cost (multi_string) * coefficient,
 506                   0, 0, costvec, ncostvec);
 507   else if (one_line_string)
 508     line_ins_del (frame,
 509                   string_cost (setup_string) + string_cost (cleanup_string), 0,
 510                   string_cost (one_line_string),
 511                   per_line_cost (one_line_string),
 512                   costvec, ncostvec);
 513   else
 514     line_ins_del (frame,
 515                   9999, 0, 9999, 0,
 516                   costvec, ncostvec);
 517 }
 518
 519 /* Calculate the insert and delete line costs.
 520    Note that this is done even when running with a window system
 521    because we want to know how long scrolling takes (and avoid it).
 522    This must be redone whenever the frame height changes.
 523
 524    We keep the ID costs in a precomputed array based on the position
 525    at which the I or D is performed.  Also, there are two kinds of ID
 526    costs: the "once-only" and the "repeated".  This is to handle both
 527    those terminals that are able to insert N lines at a time (once-
 528    only) and those that must repeatedly insert one line.
 529
 530    The cost to insert N lines at line L is
 531             [tt.t_ILov  + (frame_height + 1 - L) * tt.t_ILpf] +
 532         N * [tt.t_ILnov + (frame_height + 1 - L) * tt.t_ILnpf]
 533
 534    ILov represents the basic insert line overhead.  ILpf is the padding
 535    required to allow the terminal time to move a line: insertion at line
 536    L changes (frame_height + 1 - L) lines.
 537
 538    The first bracketed expression above is the overhead; the second is
 539    the multiply factor.  Both are dependent only on the position at
 540    which the insert is performed.  We store the overhead in
 541    FRAME_INSERT_COST (frame) and the multiply factor in
 542    FRAME_INSERTN_COST (frame).  Note however that any insertion
 543    must include at least one multiply factor.  Rather than compute this
 544    as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
 545    we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
 546    This is reasonable because of the particular algorithm used in calcM.
 547
 548    Deletion is essentially the same as insertion.
 549  */
 550
 551 do_line_insertion_deletion_costs (frame,
 552                                   ins_line_string, multi_ins_string,
 553                                   del_line_string, multi_del_string,
 554                                   setup_string, cleanup_string, coefficient)
 555      FRAME_PTR frame;
 556      char *ins_line_string, *multi_ins_string;
 557      char *del_line_string, *multi_del_string;
 558      char *setup_string, *cleanup_string;
 559      int coefficient;
 560 {
 561   if (FRAME_INSERT_COST (frame) != 0)
 562     {
 563       FRAME_INSERT_COST (frame) =
 564         (int *) xrealloc (FRAME_INSERT_COST (frame),
 565                           FRAME_HEIGHT (frame) * sizeof (int));
 566       FRAME_DELETEN_COST (frame) =
 567         (int *) xrealloc (FRAME_DELETEN_COST (frame),
 568                           FRAME_HEIGHT (frame) * sizeof (int));
 569       FRAME_INSERTN_COST (frame) =
 570         (int *) xrealloc (FRAME_INSERTN_COST (frame),
 571                           FRAME_HEIGHT (frame) * sizeof (int));
 572       FRAME_DELETE_COST (frame) =
 573         (int *) xrealloc (FRAME_DELETE_COST (frame),
 574                           FRAME_HEIGHT (frame) * sizeof (int));
 575     }
 576   else
 577     {
 578       FRAME_INSERT_COST (frame) =
 579         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 580       FRAME_DELETEN_COST (frame) =
 581         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 582       FRAME_INSERTN_COST (frame) =
 583         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 584       FRAME_DELETE_COST (frame) =
 585         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 586     }
 587
 588   ins_del_costs (frame,
 589                  ins_line_string, multi_ins_string,
 590                  setup_string, cleanup_string,
 591                  FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
 592                  coefficient);
 593   ins_del_costs (frame,
 594                  del_line_string, multi_del_string,
 595                  setup_string, cleanup_string,
 596                  FRAME_DELETEN_COST (frame), FRAME_DELETE_COST (frame),
 597                  coefficient);
 598 }