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 distributor8: accepts responsibility to anyone for the consequences of using it9: 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 Public11: License for full details.12:13: Everyone is granted permission to copy, modify and redistribute14: GNU Emacs, but only under the conditions described in the15: GNU Emacs General Public License. A copy of this license is16: supposed to have been given to you along with GNU Emacs so you17: can know your rights and responsibilities. It should be in a18: file named COPYING. Among other things, the copyright notice19: 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 cost30: can exceed MScreenLength * MScreenWidth (or so).31: That is about 10000, which fits in a short. */32:33: #define INFINITY 1500034:35: struct matrix_elt36: {37: /* Cost of outputting through this line38: if no insert/delete is done just above it. */39: short writecost;40: /* Cost of outputting through this line41: if an insert is done just above it. */42: short insertcost;43: /* Cost of outputting through this line44: 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 lines79: 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 smallest83: cost that ends with a delete, and the smallest cost that84: ends with neither one. These are kept separate because85: on some terminals the cost of doing an insert varies86: 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 relative92: to the place at which the first mismatch between old and93: 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 do157: not insert or delete above this line.158: That is, if we update through line i-1159: 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-line172: before outputting this line.173: That is, we update through line i-1174: 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 followed180: immediately by an insert. It cannot be as good181: as not doing either of them. */182: if (free_at_end == i)183: {184: cost = p1->writecost;185: cost1 = p1->insertcost;186: }187: else188: {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 after196: outputting this line.197: That is, we update through line i198: 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 followed202: immediately by a delete. */203: if (free_at_end == i)204: {205: cost = p1->writecost;206: cost1 = p1->deletecost;207: }208: else209: {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 operations219: 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: else266: {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 that299: avoiding redrawing such a line will have little weight. */300:301: int302: 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 position343: at which the I or D is performed. Also, there are two kinds of ID344: costs: the "once-only" and the "repeated". This is to handle both345: 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 is349: [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 padding353: required to allow the terminal time to move a line: insertion at line354: L changes (screen_height + 1 - L) lines.355:356: The first bracketed expression above is the overhead; the second is357: the multiply factor. Both are dependent only on the position at358: which the insert is performed. We store the overhead in ILcost and359: the multiply factor in ILncost. Note however that any insertion360: must include at least one multiply factor. Rather than compute this361: as ILcost[line]+ILncost[line], we add ILncost into ILcost. This is362: 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 screen376: 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: else405: 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: }

scrolling_max_lines_saved
defined in line 301; used 1 times

- in /usr/src/new/emacs/src/dispnew.c line 703