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