src/scroll.c

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