src/scroll.c

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