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_X_P (frame))
 258     {
 259       bcopy (current_frame->top_left_x, temp_frame->top_left_x,
 260              current_frame->height * sizeof (short));
 261       bcopy (current_frame->top_left_y, temp_frame->top_left_y,
 262              current_frame->height * sizeof (short));
 263       bcopy (current_frame->pix_width, temp_frame->pix_width,
 264              current_frame->height * sizeof (short));
 265       bcopy (current_frame->pix_height, temp_frame->pix_height,
 266              current_frame->height * sizeof (short));
 267       bcopy (current_frame->max_ascent, temp_frame->max_ascent,
 268              current_frame->height * sizeof (short));
 269     }
 270 #endif
 271
 272   i = j = window_size;
 273
 274   while (i > 0 || j > 0)
 275     {
 276       p = matrix + i * (window_size + 1) + j;
 277       tem = p->insertcost;
 278       if (tem < p->writecost && tem < p->deletecost)
 279         {
 280           /* Insert should be done at vpos i-1, plus maybe some before */
 281           queue[qi].count = p->insertcount;
 282           i -= p->insertcount;
 283           queue[qi++].pos = i + unchanged_at_top;
 284         }
 285       else if (p->deletecost < p->writecost)
 286         {
 287           /* Old line at vpos j-1, and maybe some before it,
 288              should be deleted */
 289           j -= p->deletecount;
 290           if (!window)
 291             {
 292               set_terminal_window (window_size + unchanged_at_top);
 293               window = 1;
 294             }
 295           ins_del_lines (j + unchanged_at_top, - p->deletecount);
 296         }
 297       else
 298         {
 299           /* Best thing done here is no insert or delete */
 300           /* Old line at vpos j-1 ends up at vpos i-1 */
 301           current_frame->glyphs[i + offset - 1]
 302             = temp_frame->glyphs[j + offset - 1];
 303           current_frame->used[i + offset - 1]
 304             = temp_frame->used[j + offset - 1];
 305           current_frame->highlight[i + offset - 1]
 306             = temp_frame->highlight[j + offset - 1];
 307
 308           temp_frame->enable[j + offset - 1] = 1;
 309           i--;
 310           j--;
 311         }
 312     }
 313
 314   if (!window && qi)
 315     {
 316       set_terminal_window (window_size + unchanged_at_top);
 317       window = 1;
 318     }
 319
 320   /* Now do all insertions */
 321
 322   next = unchanged_at_top;
 323   for (i = qi - 1; i >= 0; i--)
 324     {
 325       ins_del_lines (queue[i].pos, queue[i].count);
 326
 327       /* Mark the inserted lines as clear,
 328          and put into them the line-contents strings
 329          that were discarded during the deletions.
 330          Those are the ones for which temp_frame->enable was not set.  */
 331       tem = queue[i].pos;
 332       for (j = tem + queue[i].count - 1; j >= tem; j--)
 333         {
 334           current_frame->enable[j] = 0;
 335           while (temp_frame->enable[next])
 336             next++;
 337           current_frame->glyphs[j] = temp_frame->glyphs[next++];
 338         }
 339     }
 340
 341   if (window)
 342     set_terminal_window (0);
 343 }
 344 \f
 345 void
 346 scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom,
 347              draw_cost, old_hash, new_hash, free_at_end)
 348      FRAME_PTR frame;
 349      int window_size, unchanged_at_top, unchanged_at_bottom;
 350      int *draw_cost;
 351      int *old_hash;
 352      int *new_hash;
 353      int free_at_end;
 354 {
 355   struct matrix_elt *matrix;
 356   matrix = ((struct matrix_elt *)
 357             alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
 358
 359   calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom,
 360                        draw_cost, old_hash, new_hash,
 361                        free_at_end);
 362   do_scrolling (frame, matrix, window_size, unchanged_at_top);
 363 }
 364 \f
 365 /* Return number of lines in common between current and desired frame contents
 366    described to us only as vectors of hash codes OLDHASH and NEWHASH.
 367    Consider only vpos range START to END (not including END).
 368    Ignore short lines on the assumption that
 369    avoiding redrawing such a line will have little weight.  */
 370
 371 int
 372 scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
 373      int start, end;
 374      int *oldhash, *newhash, *cost;
 375 {
 376   struct { int hash; int count; } lines[01000];
 377   register int i, h;
 378   register int matchcount = 0;
 379   int avg_length = 0;
 380   int threshold;
 381
 382   /* Compute a threshold which is 1/4 of average length of these lines.  */
 383
 384   for (i = start; i < end; i++)
 385     avg_length += cost[i];
 386
 387   avg_length /= end - start;
 388   threshold = avg_length / 4;
 389
 390   bzero (lines, sizeof lines);
 391
 392   /* Put new lines' hash codes in hash table.
 393      Ignore lines shorter than the threshold.
 394      Thus, if the lines that are in common
 395      are mainly the ones that are short,
 396      they won't count.  */
 397   for (i = start; i < end; i++)
 398     {
 399       if (cost[i] > threshold)
 400         {
 401           h = newhash[i] & 0777;
 402           lines[h].hash = newhash[i];
 403           lines[h].count++;
 404         }
 405     }
 406
 407   /* Look up old line hash codes in the hash table.
 408      Count number of matches between old lines and new.  */
 409
 410   for (i = start; i < end; i++)
 411     {
 412       h = oldhash[i] & 0777;
 413       if (oldhash[i] == lines[h].hash)
 414         {
 415           matchcount++;
 416           if (--lines[h].count == 0)
 417             lines[h].hash = 0;
 418         }
 419     }
 420
 421   return matchcount;
 422 }
 423 \f
 424 /* Return a measure of the cost of moving the lines
 425    starting with vpos FROM, up to but not including vpos TO,
 426    down by AMOUNT lines (AMOUNT may be negative).
 427    These are the same arguments that might be given to
 428    scroll_frame_lines to perform this scrolling.  */
 429
 430 scroll_cost (frame, from, to, amount)
 431      FRAME_PTR frame;
 432      int from, to, amount;
 433 {
 434   /* Compute how many lines, at bottom of frame,
 435      will not be involved in actual motion.  */
 436   int limit = to;
 437   int offset;
 438   int height = FRAME_HEIGHT (frame);
 439
 440   if (amount == 0)
 441     return 0;
 442
 443   if (! scroll_region_ok)
 444     limit = height;
 445   else if (amount > 0)
 446     limit += amount;
 447
 448   if (amount < 0)
 449     {
 450       int temp = to;
 451       to = from + amount;
 452       from = temp + amount;
 453       amount = - amount;
 454     }
 455
 456   offset = height - limit;
 457
 458   return
 459     (FRAME_INSERT_COST (frame)[offset + from]
 460      + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from]
 461      + FRAME_DELETEN_COST (frame)[offset + to]
 462      + (amount - 1) * FRAME_DELETE_COST (frame)[offset + to]);
 463 }
 464 \f
 465 /* Calculate the line insertion/deletion
 466    overhead and multiply factor values */
 467
 468 static void
 469 line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf)
 470      FRAME_PTR frame;
 471      int ov1, ovn;
 472      int pf1, pfn;
 473      register int *ov, *mf;
 474 {
 475   register int i;
 476   register int frame_height = FRAME_HEIGHT (frame);
 477   register int insert_overhead = ov1 * 10;
 478   register int next_insert_cost = ovn * 10;
 479
 480   for (i = frame_height-1; i >= 0; i--)
 481     {
 482       mf[i] = next_insert_cost / 10;
 483       next_insert_cost += pfn;
 484       ov[i] = (insert_overhead + next_insert_cost) / 10;
 485       insert_overhead += pf1;
 486     }
 487 }
 488
 489 static void
 490 ins_del_costs (frame,
 491                one_line_string, multi_string,
 492                setup_string, cleanup_string,
 493                costvec, ncostvec, coefficient)
 494      FRAME_PTR frame;
 495      char *one_line_string, *multi_string;
 496      char *setup_string, *cleanup_string;
 497      int *costvec, *ncostvec;
 498      int coefficient;
 499 {
 500   if (multi_string)
 501     line_ins_del (frame,
 502                   string_cost (multi_string) * coefficient,
 503                   per_line_cost (multi_string) * coefficient,
 504                   0, 0, costvec, ncostvec);
 505   else if (one_line_string)
 506     line_ins_del (frame,
 507                   string_cost (setup_string) + string_cost (cleanup_string), 0,
 508                   string_cost (one_line_string),
 509                   per_line_cost (one_line_string),
 510                   costvec, ncostvec);
 511   else
 512     line_ins_del (frame,
 513                   9999, 0, 9999, 0,
 514                   costvec, ncostvec);
 515 }
 516
 517 /* Calculate the insert and delete line costs.
 518    Note that this is done even when running with a window system
 519    because we want to know how long scrolling takes (and avoid it).
 520    This must be redone whenever the frame height changes.
 521
 522    We keep the ID costs in a precomputed array based on the position
 523    at which the I or D is performed.  Also, there are two kinds of ID
 524    costs: the "once-only" and the "repeated".  This is to handle both
 525    those terminals that are able to insert N lines at a time (once-
 526    only) and those that must repeatedly insert one line.
 527
 528    The cost to insert N lines at line L is
 529             [tt.t_ILov  + (frame_height + 1 - L) * tt.t_ILpf] +
 530         N * [tt.t_ILnov + (frame_height + 1 - L) * tt.t_ILnpf]
 531
 532    ILov represents the basic insert line overhead.  ILpf is the padding
 533    required to allow the terminal time to move a line: insertion at line
 534    L changes (frame_height + 1 - L) lines.
 535
 536    The first bracketed expression above is the overhead; the second is
 537    the multiply factor.  Both are dependent only on the position at
 538    which the insert is performed.  We store the overhead in
 539    FRAME_INSERT_COST (frame) and the multiply factor in
 540    FRAME_INSERTN_COST (frame).  Note however that any insertion
 541    must include at least one multiply factor.  Rather than compute this
 542    as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line],
 543    we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame).
 544    This is reasonable because of the particular algorithm used in calcM.
 545
 546    Deletion is essentially the same as insertion.
 547  */
 548
 549 do_line_insertion_deletion_costs (frame,
 550                                   ins_line_string, multi_ins_string,
 551                                   del_line_string, multi_del_string,
 552                                   setup_string, cleanup_string, coefficient)
 553      FRAME_PTR frame;
 554      char *ins_line_string, *multi_ins_string;
 555      char *del_line_string, *multi_del_string;
 556      char *setup_string, *cleanup_string;
 557      int coefficient;
 558 {
 559   if (FRAME_INSERT_COST (frame) != 0)
 560     {
 561       FRAME_INSERT_COST (frame) =
 562         (int *) xrealloc (FRAME_INSERT_COST (frame),
 563                           FRAME_HEIGHT (frame) * sizeof (int));
 564       FRAME_DELETEN_COST (frame) =
 565         (int *) xrealloc (FRAME_DELETEN_COST (frame),
 566                           FRAME_HEIGHT (frame) * sizeof (int));
 567       FRAME_INSERTN_COST (frame) =
 568         (int *) xrealloc (FRAME_INSERTN_COST (frame),
 569                           FRAME_HEIGHT (frame) * sizeof (int));
 570       FRAME_DELETE_COST (frame) =
 571         (int *) xrealloc (FRAME_DELETE_COST (frame),
 572                           FRAME_HEIGHT (frame) * sizeof (int));
 573     }
 574   else
 575     {
 576       FRAME_INSERT_COST (frame) =
 577         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 578       FRAME_DELETEN_COST (frame) =
 579         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 580       FRAME_INSERTN_COST (frame) =
 581         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 582       FRAME_DELETE_COST (frame) =
 583         (int *) xmalloc (FRAME_HEIGHT (frame) * sizeof (int));
 584     }
 585
 586   ins_del_costs (frame,
 587                  ins_line_string, multi_ins_string,
 588                  setup_string, cleanup_string,
 589                  FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame),
 590                  coefficient);
 591   ins_del_costs (frame,
 592                  del_line_string, multi_del_string,
 593                  setup_string, cleanup_string,
 594                  FRAME_DELETEN_COST (frame), FRAME_DELETE_COST (frame),
 595                  coefficient);
 596 }