4.3BSD - /usr/src/new/emacs/src/scroll.c

   1: /* Calculate what ins/del line to do, and do it, for Emacs redisplay.
   2:    Copyright (C) 1985 Richard M. Stallman.
   3: 
   4: This file is part of GNU Emacs.
   5: 
   6: GNU Emacs is distributed in the hope that it will be useful,
   7: but WITHOUT ANY WARRANTY.  No author or distributor
   8: accepts responsibility to anyone for the consequences of using it
   9: or for whether it serves any particular purpose or works at all,
  10: unless he says so in writing.  Refer to the GNU Emacs General Public
  11: License for full details.
  12: 
  13: Everyone is granted permission to copy, modify and redistribute
  14: GNU Emacs, but only under the conditions described in the
  15: GNU Emacs General Public License.   A copy of this license is
  16: supposed to have been given to you along with GNU Emacs so you
  17: can know your rights and responsibilities.  It should be in a
  18: file named COPYING.  Among other things, the copyright notice
  19: and this notice must be preserved on all copies.  */
  20: 
  21: 
  22: #include "config.h"
  23: #include "termchar.h"
  24: #include "dispextern.h"
  25: 
  26: #define max(a, b) ((a) > (b) ? (a) : (b))
  27: #define min(a, b) ((a) < (b) ? (a) : (b))
  28: 
  29: /* All costs measured in characters.  Therefore, no cost
  30:    can exceed MScreenLength * MScreenWidth (or so).
  31:    That is about 10000, which fits in a short.  */
  32: 
  33: #define INFINITY 15000
  34: 
  35: struct matrix_elt
  36:   {
  37:     /* Cost of outputting through this line
  38:        if no insert/delete is done just above it.  */
  39:     short writecost;
  40:     /* Cost of outputting through this line
  41:        if an insert is done just above it.  */
  42:     short insertcost;
  43:     /* Cost of outputting through this line
  44:        if a delete is done just above it.  */
  45:     short deletecost;
  46:     /* Number of inserts so far in this run of inserts,
  47:        for the cost in insertcost.  */
  48:     char insertcount;
  49:     /* Number of deletes so far in this run of deletes,
  50:        for the cost in deletecost.  */
  51:     char deletecount;
  52:   };
  53: 
  54: /* See CalcIDCosts for on the arrays below */
  55: int ILcost[MScreenLength];/* ov(n) + 1*mf(n) */
  56: int DLcost[MScreenLength];/* ov(n) + 1*mf(n) */
  57: int ILncost[MScreenLength];/* mf(n) */
  58: int DLncost[MScreenLength];/* mf(n) */
  59: 
  60: scrolling_1 (window_size, unchanged_at_top, unchanged_at_bottom,
  61:          draw_cost, old_hash, new_hash, free_at_end)
  62:      int window_size, unchanged_at_top, unchanged_at_bottom;
  63:      int *draw_cost;
  64:      int *old_hash;
  65:      int *new_hash;
  66:      int free_at_end;
  67: {
  68:   struct matrix_elt *matrix;
  69:   matrix = ((struct matrix_elt *)
  70:         alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix));
  71: 
  72:   calculate_scrolling (matrix, window_size, unchanged_at_bottom,
  73:                draw_cost, old_hash, new_hash,
  74:                free_at_end);
  75:   do_scrolling (matrix, window_size, unchanged_at_top);
  76: }
  77: 
  78: /* Determine, in matrix[i,j], the cost of updating the first j old lines
  79:    into the first i new lines.
  80:    This involves using insert or delete somewhere if i != j.
  81:    For each matrix elements, three kinds of costs are recorded:
  82:    the smallest cost that ends with an insert, the smallest
  83:    cost that ends with a delete, and the smallest cost that
  84:    ends with neither one.  These are kept separate because
  85:    on some terminals the cost of doing an insert varies
  86:    depending on whether one was just done, etc.  */
  87: 
  88: /* draw_cost[VPOS] is the cost of outputting new line at VPOS.
  89:    old_hash[VPOS] is the hash code of the old line at VPOS.
  90:    new_hash[VPOS] is the hash code of the new line at VPOS.
  91:    Note that these are not true screen vpos's, but relative
  92:    to the place at which the first mismatch between old and
  93:    new contents appears.  */
  94: 
  95: calculate_scrolling (matrix, window_size, lines_below,
  96:              draw_cost, old_hash, new_hash,
  97:              free_at_end)
  98:      /* matrix is of size window_size + 1 on each side.  */
  99:      struct matrix_elt *matrix;
 100:      int window_size;
 101:      int *draw_cost;
 102:      int *old_hash;
 103:      int *new_hash;
 104:      int free_at_end;
 105: {
 106:   register int i, j;
 107:   register struct matrix_elt *p, *p1;
 108:   register int cost, cost1;
 109: 
 110:   int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below);
 111:   int *first_insert_cost = &ILcost[screen_height - lines_moved];
 112:   int *first_delete_cost = &DLcost[screen_height - lines_moved];
 113:   int *next_insert_cost = &ILncost[screen_height - lines_moved];
 114:   int *next_delete_cost = &DLncost[screen_height - lines_moved];
 115: 
 116:   /* initialize the top left corner of the matrix */
 117:   matrix->writecost = 0;
 118:   matrix->insertcost = INFINITY;
 119:   matrix->deletecost = INFINITY;
 120:   matrix->insertcount = 0;
 121:   matrix->deletecount = 0;
 122: 
 123:   /* initialize the left edge of the matrix */
 124:   cost = first_insert_cost[1] - next_insert_cost[1];
 125:   for (i = 1; i <= window_size; i++)
 126:     {
 127:       p = matrix + i * (window_size + 1);
 128:       cost += draw_cost[i] + next_insert_cost[i];
 129:       p->insertcost = cost;
 130:       p->writecost = INFINITY;
 131:       p->deletecost = INFINITY;
 132:       p->insertcount = i;
 133:       p->deletecount = 0;
 134:     }
 135: 
 136:   /* initialize the top edge of the matrix */
 137:   cost = first_delete_cost[1] - next_delete_cost[1];
 138:   for (j = 1; j <= window_size; j++)
 139:     {
 140:       cost += next_delete_cost[j];
 141:       matrix[j].deletecost = cost;
 142:       matrix[j].writecost = INFINITY;
 143:       matrix[j].insertcost = INFINITY;
 144:       matrix[j].deletecount = j;
 145:       matrix[j].insertcount = j;
 146:     }
 147: 
 148:   /* `i' represents the vpos among new screen contents.
 149:      `j' represents the vpos among the old screen contents.  */
 150:   p = matrix + window_size + 2; /* matrix [1, 1] */
 151:   for (i = 1; i <= window_size; i++, p++)
 152:     for (j = 1; j <= window_size; j++, p++)
 153:       {
 154:     /* p contains the address of matrix [i, j] */
 155: 
 156:     /* First calculate the cost assuming we do
 157: 	   not insert or delete above this line.
 158: 	   That is, if we update through line i-1
 159: 	   based on old lines through j-1,
 160: 	   and then just change old line j to new line i.  */
 161:     p1 = p - window_size - 2; /* matrix [i-1, j-1] */
 162:     cost = p1->writecost;
 163:     if (cost > p1->insertcost)
 164:       cost = p1->insertcost;
 165:     if (cost > p1->deletecost)
 166:       cost = p1->deletecost;
 167:     if (old_hash[j] != new_hash[i])
 168:       cost += draw_cost[i];
 169:     p->writecost = cost;
 170: 
 171:     /* Calculate the cost if we do an insert-line
 172: 	   before outputting this line.
 173: 	   That is, we update through line i-1
 174: 	   based on old lines through j,
 175: 	   do an insert-line on line i,
 176: 	   and then output line i from scratch,
 177: 	   leaving old lines starting from j for reuse below.  */
 178:     p1 = p - window_size - 1; /* matrix [i-1, j] */
 179:     /* No need to think about doing a delete followed
 180: 	   immediately by an insert.  It cannot be as good
 181: 	   as not doing either of them.  */
 182:     if (free_at_end == i)
 183:       {
 184:         cost = p1->writecost;
 185:         cost1 = p1->insertcost;
 186:       }
 187:     else
 188:       {
 189:         cost = p1->writecost + first_insert_cost[i];
 190:         cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount];
 191:       }
 192:     p->insertcost = min (cost, cost1) + draw_cost[i];
 193:     p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1;
 194: 
 195:     /* Calculate the cost if we do a delete line after
 196: 	   outputting this line.
 197: 	   That is, we update through line i
 198: 	   based on old lines through j-1,
 199: 	   and throw away old line j.  */
 200:     p1 = p - 1;     /* matrix [i, j-1] */
 201:     /* No need to think about doing an insert followed
 202: 	   immediately by a delete.  */
 203:     if (free_at_end == i)
 204:       {
 205:         cost = p1->writecost;
 206:         cost1 = p1->deletecost;
 207:       }
 208:     else
 209:       {
 210:         cost = p1->writecost + first_delete_cost[i];
 211:         cost1 = p1->deletecost + next_delete_cost[i];
 212:       }
 213:     p->deletecost = min (cost, cost1);
 214:     p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1;
 215:       }
 216: }
 217: 
 218: /* Perform insert-lines and delete-lines operations
 219:  according to the costs in the matrix.
 220:  Updates the contents of PhysScreen to record what was done. */
 221: 
 222: do_scrolling (matrix, window_size, unchanged_at_top)
 223:      struct matrix_elt *matrix;
 224:      int window_size;
 225:      int unchanged_at_top;
 226: {
 227:   register struct matrix_elt *p;
 228:   register int i, j;
 229:   struct { int count, pos; } queue[MScreenLength];
 230:   int offset = unchanged_at_top;
 231:   int qi = 0;
 232:   int window = 0;
 233:   register int tem;
 234:   extern struct display_line *PhysScreen[MScreenLength + 1];
 235:   extern struct display_line *OPhysScreen[MScreenLength + 1];
 236: 
 237: /* First do all deletions of lines; queue up insertions.
 238:   Also move lines to correct slots in PhysScreen */
 239: 
 240:   i = j = window_size;
 241: 
 242:   while (i > 0 || j > 0)
 243:     {
 244:       p = matrix + i * (window_size + 1) + j;
 245:       tem = p->insertcost;
 246:       if (tem < p->writecost && tem < p->deletecost)
 247:     {
 248:       /* Insert should be done at vpos i-1, plus maybe some before */
 249:       queue[qi].count = p->insertcount;
 250:       i -= p->insertcount;
 251:       queue[qi++].pos = i + unchanged_at_top;
 252:     }
 253:       else if (p->deletecost < p->writecost)
 254:     {
 255:       /* Old line at vpos j-1, and maybe some before it,
 256: 	     should be deleted */
 257:       j -= p->deletecount;
 258:       if (!window)
 259:         {
 260:           set_terminal_window (window_size + unchanged_at_top);
 261:           window = 1;
 262:         }
 263:       ins_del_lines (j + unchanged_at_top, - p->deletecount);
 264:     }
 265:       else
 266:     {
 267:       /* Best thing done here is no insert or delete */
 268:       /* Old line at vpos j-1 ends up at vpos i-1 */
 269:       PhysScreen[i + offset] = OPhysScreen[j + offset];
 270:       i--;
 271:       j--;
 272:     }
 273:     }
 274: 
 275:   if (!window && qi)
 276:     {
 277:       set_terminal_window (window_size + unchanged_at_top);
 278:       window = 1;
 279:     }
 280: 
 281:   /* Now do all insertions */
 282: 
 283:   for (i = qi - 1; i >= 0; i--)
 284:     {
 285:       ins_del_lines (queue[i].pos, queue[i].count);
 286:       /* mark the inserted lines as clear */
 287:       tem = queue[i].pos;
 288:       for (j = tem + queue[i].count; j > tem; j--)
 289:     PhysScreen[j] = 0;
 290:     }
 291: 
 292:   if (window)
 293:     set_terminal_window (0);
 294: }
 295: 
 296: /* Return number of lines in common between PhysScreen and DesiredScreen,
 297:    considering only vpos range START to END (not including END).
 298:    Ignores short lines (length < 20) on the assumption that
 299:    avoiding redrawing such a line will have little weight.  */
 300: 
 301: int
 302: scrolling_max_lines_saved (start, end, oldhash, newhash, cost)
 303:      int start, end;
 304:      int *oldhash, *newhash, *cost;
 305: {
 306:   struct { int hash; int count; } lines[01000];
 307:   register int i, h;
 308:   register int matchcount = 0;
 309: 
 310:   bzero (lines, sizeof lines);
 311: 
 312:   /* Put new lines' hash codes in hash table.  */
 313:   for (i = start; i < end; i++)
 314:     {
 315:       if (cost[i] > 20)
 316:     {
 317:       h = newhash[i] & 0777;
 318:       lines[h].hash = newhash[i];
 319:       lines[h].count++;
 320:     }
 321:     }
 322: 
 323:   /* Look up old line hash codes in the hash table.
 324:      Count number of matches between old lines and new.  */
 325: 
 326:   for (i = start; i < end; i++)
 327:     {
 328:       h = oldhash[i] & 0777;
 329:       if (oldhash[i] == lines[h].hash)
 330:     {
 331:       matchcount++;
 332:       if (--lines[h].count == 0)
 333:         lines[h].hash = 0;
 334:     }
 335:     }
 336: 
 337:   return matchcount;
 338: }
 339: 
 340: /* Calculate the insert and delete line costs.
 341: 
 342:    We keep the ID costs in a precomputed array based on the position
 343:    at which the I or D is performed.  Also, there are two kinds of ID
 344:    costs: the "once-only" and the "repeated".  This is to handle both
 345:    those terminals that are able to insert N lines at a time (once-
 346:    only) and those that must repeatedly insert one line.
 347: 
 348:    The cost to insert N lines at line L is
 349:    	    [tt.t_ILov  + (screen_height + 1 - L) * tt.t_ILpf] +
 350: 	N * [tt.t_ILnov + (screen_height + 1 - L) * tt.t_ILnpf]
 351: 
 352:    ILov represents the basic insert line overhead.  ILpf is the padding
 353:    required to allow the terminal time to move a line: insertion at line
 354:    L changes (screen_height + 1 - L) lines.
 355: 
 356:    The first bracketed expression above is the overhead; the second is
 357:    the multiply factor.  Both are dependent only on the position at
 358:    which the insert is performed.  We store the overhead in ILcost and
 359:    the multiply factor in ILncost.  Note however that any insertion
 360:    must include at least one multiply factor.  Rather than compute this
 361:    as ILcost[line]+ILncost[line], we add ILncost into ILcost.  This is
 362:    reasonable because of the particular algorithm used in calcM.
 363: 
 364:    Deletion is essentially the same as insertion.
 365:  */
 366: 
 367: CalcIDCosts (ins_line_string, multi_ins_string,
 368:          del_line_string, multi_del_string,
 369:          setup_string, cleanup_string)
 370:      char *ins_line_string, *multi_ins_string;
 371:      char *del_line_string, *multi_del_string;
 372:      char *setup_string, *cleanup_string;
 373: {
 374:   /* Discourage long scrolls slightly on fast lines.
 375:      This says that scrolling nearly the full length of the screen
 376:      is not worth it if reprinting takes less than 1/4 second.  */
 377:   int extra = baud_rate / (10 * 4 * screen_height);
 378: 
 379:   CalcIDCosts1 (ins_line_string, multi_ins_string,
 380:         setup_string, cleanup_string,
 381:         ILcost, ILncost, extra);
 382:   CalcIDCosts1 (del_line_string, multi_del_string,
 383:         setup_string, cleanup_string,
 384:         DLcost, DLncost, 0);
 385: }
 386: 
 387: CalcIDCosts1 (one_line_string, multi_string,
 388:           setup_string, cleanup_string,
 389:           costvec, ncostvec, extra)
 390:      char *one_line_string, *multi_string;
 391:      char *setup_string, *cleanup_string;
 392:      int *costvec, *ncostvec;
 393:      int extra;
 394: {
 395:   if (multi_string)
 396:     CalcLID (string_cost (multi_string),
 397:          per_line_cost (multi_string),
 398:          extra, 0, costvec, ncostvec);
 399:   else if (one_line_string)
 400:     CalcLID (string_cost (setup_string) + string_cost (cleanup_string), 0,
 401:          string_cost (one_line_string) + extra,
 402:          per_line_cost (one_line_string),
 403:          costvec, ncostvec);
 404:   else
 405:     CalcLID (9999, 0, 9999, 0,
 406:          costvec, ncostvec);
 407: }
 408: 
 409: /* Calculate the line ID overhead and multiply factor values */
 410: CalcLID (ov1, pf1, ovn, pfn, ov, mf)
 411:      int ov1, ovn;
 412:      int pf1, pfn;
 413:      register int *ov, *mf;
 414: {
 415:   register int i;
 416:   register int insert_overhead = ov1 * 10 + screen_height * pf1;
 417:   register int next_insert_cost = ovn * 10 + screen_height * pfn;
 418: 
 419:   for (i = screen_height - 1; i > 0; i--)
 420:     {
 421:       *mf++ = next_insert_cost / 10;
 422:       next_insert_cost -= pfn;
 423:       *ov++ = (insert_overhead + next_insert_cost) / 10;
 424:       insert_overhead -= pf1;
 425:     }
 426: }

Defined functions

Defined variables

Defined struct's

Defined macros