1/* Calculate what line insertion or deletion to do, and do it, 2 Copyright (C) 1985, 1986, 1990, 1993, 1994, 2001, 2002, 2003, 2004, 3 2005, 2006, 2007 Free Software Foundation, Inc. 4 5This file is part of GNU Emacs. 6 7GNU Emacs is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GNU Emacs is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GNU Emacs; see the file COPYING. If not, write to 19the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22 23#include <config.h> 24#include <stdio.h> 25#include <string.h> 26#include "termchar.h" 27#include "lisp.h" 28#include "dispextern.h" 29#include "keyboard.h" 30#include "frame.h" 31#include "window.h" 32 33/* All costs measured in characters. 34 So no cost can exceed the area of a frame, measured in characters. 35 Let's hope this is never more than 1000000 characters. */ 36 37#define INFINITY 1000000 38 39struct matrix_elt 40 { 41 /* Cost of outputting through this line 42 if no insert/delete is done just above it. */ 43 int writecost; 44 /* Cost of outputting through this line 45 if an insert is done just above it. */ 46 int insertcost; 47 /* Cost of outputting through this line 48 if a delete is done just above it. */ 49 int deletecost; 50 /* Number of inserts so far in this run of inserts, 51 for the cost in insertcost. */ 52 unsigned char insertcount; 53 /* Number of deletes so far in this run of deletes, 54 for the cost in deletecost. */ 55 unsigned char deletecount; 56 /* Number of writes so far since the last insert 57 or delete for the cost in writecost. */ 58 unsigned char writecount; 59 }; 60 61static void do_direct_scrolling P_ ((struct glyph_matrix *, 62 struct matrix_elt *, 63 int, int)); 64static void do_scrolling P_ ((struct glyph_matrix *, 65 struct matrix_elt *, 66 int, int)); 67 68 69/* Determine, in matrix[i,j], the cost of updating the first j old 70 lines into the first i new lines using the general scrolling method. 71 This involves using insert or delete somewhere if i != j. 72 For each matrix elements, three kinds of costs are recorded: 73 the smallest cost that ends with an insert, the smallest 74 cost that ends with a delete, and the smallest cost that 75 ends with neither one. These are kept separate because 76 on some terminals the cost of doing an insert varies 77 depending on whether one was just done, etc. */ 78 79/* draw_cost[VPOS] is the cost of outputting new line at VPOS. 80 old_hash[VPOS] is the hash code of the old line at VPOS. 81 new_hash[VPOS] is the hash code of the new line at VPOS. 82 Note that these are not true frame vpos's, but relative 83 to the place at which the first mismatch between old and 84 new contents appears. */ 85 86static void 87calculate_scrolling (frame, matrix, window_size, lines_below, 88 draw_cost, old_hash, new_hash, 89 free_at_end) 90 FRAME_PTR frame; 91 /* matrix is of size window_size + 1 on each side. */ 92 struct matrix_elt *matrix; 93 int window_size, lines_below; 94 int *draw_cost; 95 int *old_hash; 96 int *new_hash; 97 int free_at_end; 98{ 99 register int i, j; 100 int frame_lines = FRAME_LINES (frame); 101 register struct matrix_elt *p, *p1; 102 register int cost, cost1; 103 104 int lines_moved = window_size + (scroll_region_ok ? 0 : lines_below); 105 /* first_insert_cost[I] is the cost of doing the first insert-line 106 at the i'th line of the lines we are considering, 107 where I is origin 1 (as it is below). */ 108 int *first_insert_cost 109 = &FRAME_INSERT_COST (frame)[frame_lines - 1 - lines_moved]; 110 int *first_delete_cost 111 = &FRAME_DELETE_COST (frame)[frame_lines - 1 - lines_moved]; 112 int *next_insert_cost 113 = &FRAME_INSERTN_COST (frame)[frame_lines - 1 - lines_moved]; 114 int *next_delete_cost 115 = &FRAME_DELETEN_COST (frame)[frame_lines - 1 - lines_moved]; 116 117 /* Discourage long scrolls on fast lines. 118 Don't scroll nearly a full frame height unless it saves 119 at least 1/4 second. */ 120 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame)); 121 122 if (baud_rate <= 0) 123 extra_cost = 1; 124 125 /* initialize the top left corner of the matrix */ 126 matrix->writecost = 0; 127 matrix->insertcost = INFINITY; 128 matrix->deletecost = INFINITY; 129 matrix->insertcount = 0; 130 matrix->deletecount = 0; 131 132 /* initialize the left edge of the matrix */ 133 cost = first_insert_cost[1] - next_insert_cost[1]; 134 for (i = 1; i <= window_size; i++) 135 { 136 p = matrix + i * (window_size + 1); 137 cost += draw_cost[i] + next_insert_cost[i] + extra_cost; 138 p->insertcost = cost; 139 p->writecost = INFINITY; 140 p->deletecost = INFINITY; 141 p->insertcount = i; 142 p->deletecount = 0; 143 } 144 145 /* initialize the top edge of the matrix */ 146 cost = first_delete_cost[1] - next_delete_cost[1]; 147 for (j = 1; j <= window_size; j++) 148 { 149 cost += next_delete_cost[j]; 150 matrix[j].deletecost = cost; 151 matrix[j].writecost = INFINITY; 152 matrix[j].insertcost = INFINITY; 153 matrix[j].deletecount = j; 154 matrix[j].insertcount = 0; 155 } 156 157 /* `i' represents the vpos among new frame contents. 158 `j' represents the vpos among the old frame contents. */ 159 p = matrix + window_size + 2; /* matrix [1, 1] */ 160 for (i = 1; i <= window_size; i++, p++) 161 for (j = 1; j <= window_size; j++, p++) 162 { 163 /* p contains the address of matrix [i, j] */ 164 165 /* First calculate the cost assuming we do 166 not insert or delete above this line. 167 That is, if we update through line i-1 168 based on old lines through j-1, 169 and then just change old line j to new line i. */ 170 p1 = p - window_size - 2; /* matrix [i-1, j-1] */ 171 cost = p1->writecost; 172 if (cost > p1->insertcost) 173 cost = p1->insertcost; 174 if (cost > p1->deletecost) 175 cost = p1->deletecost; 176 if (old_hash[j] != new_hash[i]) 177 cost += draw_cost[i]; 178 p->writecost = cost; 179 180 /* Calculate the cost if we do an insert-line 181 before outputting this line. 182 That is, we update through line i-1 183 based on old lines through j, 184 do an insert-line on line i, 185 and then output line i from scratch, 186 leaving old lines starting from j for reuse below. */ 187 p1 = p - window_size - 1; /* matrix [i-1, j] */ 188 /* No need to think about doing a delete followed 189 immediately by an insert. It cannot be as good 190 as not doing either of them. */ 191 if (free_at_end == i) 192 { 193 cost = p1->writecost; 194 cost1 = p1->insertcost; 195 } 196 else 197 { 198 cost = p1->writecost + first_insert_cost[i]; 199 if ((int) p1->insertcount > i) 200 abort (); 201 cost1 = p1->insertcost + next_insert_cost[i - p1->insertcount]; 202 } 203 p->insertcost = min (cost, cost1) + draw_cost[i] + extra_cost; 204 p->insertcount = (cost < cost1) ? 1 : p1->insertcount + 1; 205 if ((int) p->insertcount > i) 206 abort (); 207 208 /* Calculate the cost if we do a delete line after 209 outputting this line. 210 That is, we update through line i 211 based on old lines through j-1, 212 and throw away old line j. */ 213 p1 = p - 1; /* matrix [i, j-1] */ 214 /* No need to think about doing an insert followed 215 immediately by a delete. */ 216 if (free_at_end == i) 217 { 218 cost = p1->writecost; 219 cost1 = p1->deletecost; 220 } 221 else 222 { 223 cost = p1->writecost + first_delete_cost[i]; 224 cost1 = p1->deletecost + next_delete_cost[i]; 225 } 226 p->deletecost = min (cost, cost1); 227 p->deletecount = (cost < cost1) ? 1 : p1->deletecount + 1; 228 } 229} 230 231 232 233/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX 234 according to the costs in MATRIX, using the general scrolling 235 method that is used if the terminal does not support the setting of 236 scroll windows (scroll_region_ok == 0). 237 238 WINDOW_SIZE is the number of lines being considered for scrolling 239 and UNCHANGED_AT_TOP is the vpos of the first line being 240 considered. These two arguments can specify any contiguous range 241 of lines. */ 242 243static void 244do_scrolling (current_matrix, matrix, window_size, unchanged_at_top) 245 struct glyph_matrix *current_matrix; 246 struct matrix_elt *matrix; 247 int window_size; 248 int unchanged_at_top; 249{ 250 struct matrix_elt *p; 251 int i, j, k; 252 253 /* Set to 1 if we have set a terminal window with 254 set_terminal_window. */ 255 int terminal_window_p = 0; 256 257 /* A queue for line insertions to be done. */ 258 struct queue { int count, pos; }; 259 struct queue *queue_start 260 = (struct queue *) alloca (current_matrix->nrows * sizeof (struct queue)); 261 struct queue *queue = queue_start; 262 263 char *retained_p = (char *) alloca (window_size * sizeof (char)); 264 int *copy_from = (int *) alloca (window_size * sizeof (int)); 265 266 /* Zero means line is empty. */ 267 bzero (retained_p, window_size * sizeof (char)); 268 for (k = 0; k < window_size; ++k) 269 copy_from[k] = -1; 270 271#define CHECK_BOUNDS \ 272 do \ 273 { \ 274 int k; \ 275 for (k = 0; k < window_size; ++k) \ 276 xassert (copy_from[k] == -1 \ 277 || (copy_from[k] >= 0 && copy_from[k] < window_size)); \ 278 } \ 279 while (0); 280 281 /* When j is advanced, this corresponds to deleted lines. 282 When i is advanced, this corresponds to inserted lines. */ 283 i = j = window_size; 284 while (i > 0 || j > 0) 285 { 286 p = matrix + i * (window_size + 1) + j; 287 288 if (p->insertcost < p->writecost && p->insertcost < p->deletecost) 289 { 290 /* Insert should be done at vpos i-1, plus maybe some before. 291 Queue the screen operation to be performed. */ 292 queue->count = p->insertcount; 293 queue->pos = i + unchanged_at_top - p->insertcount; 294 ++queue; 295 296 /* By incrementing I, we leave room in the result rows 297 for the empty rows opened up. */ 298 i -= p->insertcount; 299 } 300 else if (p->deletecost < p->writecost) 301 { 302 /* Old line at vpos j-1, and maybe some before it, should be 303 deleted. By decrementing J, we skip some lines in the 304 temp_rows which is equivalent to omitting these lines in 305 the result rows, thus deleting them. */ 306 j -= p->deletecount; 307 308 /* Set the terminal window, if not done already. */ 309 if (! terminal_window_p) 310 { 311 set_terminal_window (window_size + unchanged_at_top); 312 terminal_window_p = 1; 313 } 314 315 /* Delete lines on the terminal. */ 316 ins_del_lines (j + unchanged_at_top, - p->deletecount); 317 } 318 else 319 { 320 /* Best thing done here is no insert or delete, i.e. a write. */ 321 --i, --j; 322 xassert (i >= 0 && i < window_size); 323 xassert (j >= 0 && j < window_size); 324 copy_from[i] = j; 325 retained_p[j] = 1; 326 327#if GLYPH_DEBUG 328 CHECK_BOUNDS; 329#endif 330 } 331 } 332 333 /* Now do all insertions queued above. */ 334 if (queue > queue_start) 335 { 336 int next = -1; 337 338 /* Set the terminal window if not yet done. */ 339 if (!terminal_window_p) 340 { 341 set_terminal_window (window_size + unchanged_at_top); 342 terminal_window_p = 1; 343 } 344 345 do 346 { 347 --queue; 348 349 /* Do the deletion on the terminal. */ 350 ins_del_lines (queue->pos, queue->count); 351 352 /* All lines in the range deleted become empty in the glyph 353 matrix. Assign to them glyph rows that are not retained. 354 K is the starting position of the deleted range relative 355 to the window we are working in. */ 356 k = queue->pos - unchanged_at_top; 357 for (j = 0; j < queue->count; ++j) 358 { 359 /* Find the next row not retained. */ 360 while (retained_p[++next]) 361 ; 362 363 /* Record that this row is to be used for the empty 364 glyph row j. */ 365 copy_from[k + j] = next; 366 } 367 } 368 while (queue > queue_start); 369 370 } 371 372 for (k = 0; k < window_size; ++k) 373 xassert (copy_from[k] >= 0 && copy_from[k] < window_size); 374 375 /* Perform the row swizzling. */ 376 mirrored_line_dance (current_matrix, unchanged_at_top, window_size, 377 copy_from, retained_p); 378 379 /* Some sanity checks if GLYPH_DEBUG != 0. */ 380 CHECK_MATRIX (current_matrix); 381 382 if (terminal_window_p) 383 set_terminal_window (0); 384} 385 386 387/* Determine, in matrix[i,j], the cost of updating the first j 388 old lines into the first i new lines using the direct 389 scrolling method. When the old line and the new line have 390 different hash codes, the calculated cost of updating old 391 line j into new line i includes the cost of outputting new 392 line i, and if i != j, the cost of outputting the old line j 393 is also included, as a penalty for moving the line and then 394 erasing it. In addition, the cost of updating a sequence of 395 lines with constant i - j includes the cost of scrolling the 396 old lines into their new positions, unless i == j. Scrolling 397 is achieved by setting the screen window to avoid affecting 398 other lines below, and inserting or deleting lines at the top 399 of the scrolled region. The cost of scrolling a sequence of 400 lines includes the fixed cost of specifying a scroll region, 401 plus a variable cost which can depend upon the number of lines 402 involved and the distance by which they are scrolled, and an 403 extra cost to discourage long scrolls. 404 405 As reflected in the matrix, an insert or delete does not 406 correspond directly to the insertion or deletion which is 407 used in scrolling lines. An insert means that the value of i 408 has increased without a corresponding increase in the value 409 of j. A delete means that the value of j has increased 410 without a corresponding increase in the value of i. A write 411 means that i and j are both increased by the same amount, and 412 that the old lines will be moved to their new positions. 413 414 An insert following a delete is allowed only if i > j. 415 A delete following an insert is allowed only if i < j. 416 These restrictions ensure that the new lines in an insert 417 will always be blank as an effect of the neighboring writes. 418 Thus the calculated cost of an insert is simply the cost of 419 outputting the new line contents. The direct cost of a 420 delete is zero. Inserts and deletes indirectly affect the 421 total cost through their influence on subsequent writes. */ 422 423/* The vectors draw_cost, old_hash, and new_hash have the same 424 meanings here as in calculate_scrolling, and old_draw_cost 425 is the equivalent of draw_cost for the old line contents */ 426 427static void 428calculate_direct_scrolling (frame, matrix, window_size, lines_below, 429 draw_cost, old_draw_cost, old_hash, new_hash, 430 free_at_end) 431 FRAME_PTR frame; 432 /* matrix is of size window_size + 1 on each side. */ 433 struct matrix_elt *matrix; 434 int window_size, lines_below; 435 int *draw_cost; 436 int *old_draw_cost; 437 int *old_hash; 438 int *new_hash; 439 int free_at_end; 440{ 441 register int i, j; 442 int frame_lines = FRAME_LINES (frame); 443 register struct matrix_elt *p, *p1; 444 register int cost, cost1, delta; 445 446 /* first_insert_cost[-I] is the cost of doing the first insert-line 447 at a position I lines above the bottom line in the scroll window. */ 448 int *first_insert_cost 449 = &FRAME_INSERT_COST (frame)[frame_lines - 1]; 450 int *first_delete_cost 451 = &FRAME_DELETE_COST (frame)[frame_lines - 1]; 452 int *next_insert_cost 453 = &FRAME_INSERTN_COST (frame)[frame_lines - 1]; 454 int *next_delete_cost 455 = &FRAME_DELETEN_COST (frame)[frame_lines - 1]; 456 457 int scroll_overhead; 458 459 /* Discourage long scrolls on fast lines. 460 Don't scroll nearly a full frame height unless it saves 461 at least 1/4 second. */ 462 int extra_cost = baud_rate / (10 * 4 * FRAME_LINES (frame)); 463 464 if (baud_rate <= 0) 465 extra_cost = 1; 466 467 /* Overhead of setting the scroll window, plus the extra cost 468 cost of scrolling by a distance of one. The extra cost is 469 added once for consistency with the cost vectors */ 470 scroll_overhead = scroll_region_cost + extra_cost; 471 472 /* initialize the top left corner of the matrix */ 473 matrix->writecost = 0; 474 matrix->insertcost = INFINITY; 475 matrix->deletecost = INFINITY; 476 matrix->writecount = 0; 477 matrix->insertcount = 0; 478 matrix->deletecount = 0; 479 480 /* initialize the left edge of the matrix */ 481 cost = 0; 482 for (i = 1; i <= window_size; i++) 483 { 484 p = matrix + i * (window_size + 1); 485 cost += draw_cost[i]; 486 p->insertcost = cost; 487 p->writecost = INFINITY; 488 p->deletecost = INFINITY; 489 p->insertcount = i; 490 p->writecount = 0; 491 p->deletecount = 0; 492 } 493 494 /* initialize the top edge of the matrix */ 495 for (j = 1; j <= window_size; j++) 496 { 497 matrix[j].deletecost = 0; 498 matrix[j].writecost = INFINITY; 499 matrix[j].insertcost = INFINITY; 500 matrix[j].deletecount = j; 501 matrix[j].writecount = 0; 502 matrix[j].insertcount = 0; 503 } 504 505 /* `i' represents the vpos among new frame contents. 506 `j' represents the vpos among the old frame contents. */ 507 p = matrix + window_size + 2; /* matrix [1, 1] */ 508 509 for (i = 1; i <= window_size; i++, p++) 510 for (j = 1; j <= window_size; j++, p++) 511 { 512 /* p contains the address of matrix [i, j] */ 513 514 /* First calculate the cost assuming we do 515 not insert or delete above this line. 516 That is, if we update through line i-1 517 based on old lines through j-1, 518 and then just change old line j to new line i. 519 520 Depending on which choice gives the lower cost, 521 this usually involves either scrolling a single line 522 or extending a sequence of scrolled lines, but 523 when i == j, no scrolling is required. */ 524 p1 = p - window_size - 2; /* matrix [i-1, j-1] */ 525 cost = p1->insertcost; 526 if (cost > p1->deletecost) 527 cost = p1->deletecost; 528 cost1 = p1->writecost; 529 if (i == j) 530 { 531 if (cost > cost1) 532 { 533 cost = cost1; 534 p->writecount = p1->writecount + 1; 535 } 536 else 537 p->writecount = 1; 538 if (old_hash[j] != new_hash[i]) 539 { 540 cost += draw_cost[i]; 541 } 542 } 543 else 544 { 545 if (i > j) 546 { 547 delta = i - j; 548 549 /* The cost added here for scrolling the first line by 550 a distance N includes the overhead of setting the 551 scroll window, the cost of inserting N lines at a 552 position N lines above the bottom line of the window, 553 and an extra cost which is proportional to N. */ 554 cost += scroll_overhead + first_insert_cost[-delta] + 555 (delta-1) * (next_insert_cost[-delta] + extra_cost); 556 557 /* In the most general case, the insertion overhead and 558 the multiply factor can grow linearly as the distance 559 from the bottom of the window increases. The incremental 560 cost of scrolling an additional line depends upon the 561 rate of change of these two parameters. Each of these 562 growth rates can be determined by a simple difference. 563 To reduce the cumulative effects of rounding error, we 564 vary the position at which the difference is computed. */ 565 cost1 += first_insert_cost[-j] - first_insert_cost[1-j] + 566 (delta-1) * (next_insert_cost[-j] - next_insert_cost[1-j]); 567 } 568 else 569 { 570 delta = j - i; 571 cost += scroll_overhead + first_delete_cost[-delta] + 572 (delta-1) * (next_delete_cost[-delta] + extra_cost); 573 cost1 += first_delete_cost[-i] - first_delete_cost[1-i] + 574 (delta-1) * ( next_delete_cost[-i] - next_delete_cost[1-i]); 575 } 576 if (cost1 < cost) 577 { 578 cost = cost1; 579 p->writecount = p1->writecount + 1; 580 } 581 else 582 p->writecount = 1; 583 if (old_hash[j] != new_hash[i]) 584 { 585 cost += draw_cost[i] + old_draw_cost[j]; 586 } 587 } 588 p->writecost = cost; 589 590 /* Calculate the cost if we do an insert-line 591 before outputting this line. 592 That is, we update through line i-1 593 based on old lines through j, 594 do an insert-line on line i, 595 and then output line i from scratch, 596 leaving old lines starting from j for reuse below. */ 597 p1 = p - window_size - 1; /* matrix [i-1, j] */ 598 cost = p1->writecost; 599 /* If i > j, an insert is allowed after a delete. */ 600 if (i > j && p1->deletecost < cost) 601 cost = p1->deletecost; 602 if (p1->insertcost <= cost) 603 { 604 cost = p1->insertcost; 605 p->insertcount = p1->insertcount + 1; 606 } 607 else 608 p->insertcount = 1; 609 cost += draw_cost[i]; 610 p->insertcost = cost; 611 612 /* Calculate the cost if we do a delete line after 613 outputting this line. 614 That is, we update through line i 615 based on old lines through j-1, 616 and throw away old line j. */ 617 p1 = p - 1; /* matrix [i, j-1] */ 618 cost = p1->writecost; 619 /* If i < j, a delete is allowed after an insert. */ 620 if (i < j && p1->insertcost < cost) 621 cost = p1->insertcost; 622 cost1 = p1->deletecost; 623 if (p1->deletecost <= cost) 624 { 625 cost = p1->deletecost; 626 p->deletecount = p1->deletecount + 1; 627 } 628 else 629 p->deletecount = 1; 630 p->deletecost = cost; 631 } 632} 633 634 635 636/* Perform insert-lines and delete-lines operations on CURRENT_MATRIX 637 according to the costs in MATRIX, using the direct scrolling method 638 which is used when the terminal supports setting a scroll window 639 (scroll_region_ok). 640 641 WINDOW_SIZE is the number of lines being considered for scrolling 642 and UNCHANGED_AT_TOP is the vpos of the first line being 643 considered. These two arguments can specify any contiguous range 644 of lines. 645 646 In the direct scrolling method, a new scroll window is selected 647 before each insertion or deletion, so that groups of lines can be 648 scrolled directly to their final vertical positions. This method 649 is described in more detail in calculate_direct_scrolling, where 650 the cost matrix for this approach is constructed. */ 651 652static void 653do_direct_scrolling (current_matrix, cost_matrix, window_size, 654 unchanged_at_top) 655 struct glyph_matrix *current_matrix; 656 struct matrix_elt *cost_matrix; 657 int window_size; 658 int unchanged_at_top; 659{ 660 struct matrix_elt *p; 661 int i, j; 662 663 /* A queue of deletions and insertions to be performed. */ 664 struct alt_queue { int count, pos, window; }; 665 struct alt_queue *queue_start = (struct alt_queue *) 666 alloca (window_size * sizeof *queue_start); 667 struct alt_queue *queue = queue_start; 668 669 /* Set to 1 if a terminal window has been set with 670 set_terminal_window: */ 671 int terminal_window_p = 0; 672 673 /* A nonzero value of write_follows indicates that a write has been 674 selected, allowing either an insert or a delete to be selected 675 next. When write_follows is zero, a delete cannot be selected 676 unless j < i, and an insert cannot be selected unless i < j. 677 This corresponds to a similar restriction (with the ordering 678 reversed) in calculate_direct_scrolling, which is intended to 679 ensure that lines marked as inserted will be blank. */ 680 int write_follows_p = 1; 681 682 /* For each row in the new matrix what row of the old matrix it is. */ 683 int *copy_from = (int *) alloca (window_size * sizeof (int)); 684 685 /* Non-zero for each row in the new matrix that is retained from the 686 old matrix. Lines not retained are empty. */ 687 char *retained_p = (char *) alloca (window_size * sizeof (char)); 688 689 bzero (retained_p, window_size * sizeof (char)); 690 691 /* Perform some sanity checks when GLYPH_DEBUG is on. */ 692 CHECK_MATRIX (current_matrix); 693 694 /* We are working on the line range UNCHANGED_AT_TOP ... 695 UNCHANGED_AT_TOP + WINDOW_SIZE (not including) in CURRENT_MATRIX. 696 We step through lines in this range from the end to the start. I 697 is an index into new lines, j an index into old lines. The cost 698 matrix determines what to do for ranges of indices. 699 700 If i is decremented without also decrementing j, this corresponds 701 to inserting empty lines in the result. If j is decremented 702 without also decrementing i, this corresponds to omitting these 703 lines in the new rows, i.e. rows are deleted. */ 704 i = j = window_size; 705 706 while (i > 0 || j > 0) 707 { 708 p = cost_matrix + i * (window_size + 1) + j; 709 710 if (p->insertcost < p->writecost 711 && p->insertcost < p->deletecost 712 && (write_follows_p || i < j)) 713 { 714 /* Insert is cheaper than deleting or writing lines. Leave 715 a hole in the result display that will be filled with 716 empty lines when the queue is emptied. */ 717 queue->count = 0; 718 queue->window = i; 719 queue->pos = i - p->insertcount; 720 ++queue; 721 722 i -= p->insertcount; 723 write_follows_p = 0; 724 } 725 else if (p->deletecost < p->writecost 726 && (write_follows_p || i > j)) 727 { 728 /* Deleting lines is cheaper. By decrementing J, omit 729 deletecount lines from the original. */ 730 write_follows_p = 0; 731 j -= p->deletecount; 732 } 733 else 734 { 735 /* One or more lines should be written. In the direct 736 scrolling method we do this by scrolling the lines to the 737 place they belong. */ 738 int n_to_write = p->writecount; 739 write_follows_p = 1; 740 xassert (n_to_write > 0); 741 742 if (i > j) 743 { 744 /* Immediately insert lines */ 745 set_terminal_window (i + unchanged_at_top); 746 terminal_window_p = 1; 747 ins_del_lines (j - n_to_write + unchanged_at_top, i - j); 748 } 749 else if (i < j) 750 { 751 /* Queue the deletion of a group of lines */ 752 queue->pos = i - n_to_write + unchanged_at_top; 753 queue->window = j + unchanged_at_top; 754 queue->count = i - j; 755 ++queue; 756 } 757 758 while (n_to_write > 0) 759 { 760 --i, --j, --n_to_write; 761 copy_from[i] = j; 762 retained_p[j] = 1; 763 } 764 } 765 } 766 767 /* Do queued operations. */ 768 if (queue > queue_start) 769 { 770 int next = -1; 771 772 do 773 { 774 --queue; 775 if (queue->count) 776 { 777 set_terminal_window (queue->window); 778 terminal_window_p = 1; 779 ins_del_lines (queue->pos, queue->count); 780 } 781 else 782 { 783 for (j = queue->window - 1; j >= queue->pos; --j) 784 { 785 while (retained_p[++next]) 786 ; 787 copy_from[j] = next; 788 } 789 } 790 } 791 while (queue > queue_start); 792 } 793 794 /* Now, for each row I in the range of rows we are working on, 795 copy_from[i] gives the original line to copy to I, and 796 retained_p[copy_from[i]] is zero if line I in the new display is 797 empty. */ 798 mirrored_line_dance (current_matrix, unchanged_at_top, window_size, 799 copy_from, retained_p); 800 801 if (terminal_window_p) 802 set_terminal_window (0); 803} 804 805 806 807void 808scrolling_1 (frame, window_size, unchanged_at_top, unchanged_at_bottom, 809 draw_cost, old_draw_cost, old_hash, new_hash, free_at_end) 810 FRAME_PTR frame; 811 int window_size, unchanged_at_top, unchanged_at_bottom; 812 int *draw_cost; 813 int *old_draw_cost; 814 int *old_hash; 815 int *new_hash; 816 int free_at_end; 817{ 818 struct matrix_elt *matrix; 819 matrix = ((struct matrix_elt *) 820 alloca ((window_size + 1) * (window_size + 1) * sizeof *matrix)); 821 822 if (scroll_region_ok) 823 { 824 calculate_direct_scrolling (frame, matrix, window_size, 825 unchanged_at_bottom, 826 draw_cost, old_draw_cost, 827 old_hash, new_hash, free_at_end); 828 do_direct_scrolling (frame->current_matrix, 829 matrix, window_size, unchanged_at_top); 830 } 831 else 832 { 833 calculate_scrolling (frame, matrix, window_size, unchanged_at_bottom, 834 draw_cost, old_hash, new_hash, 835 free_at_end); 836 do_scrolling (frame->current_matrix, matrix, window_size, 837 unchanged_at_top); 838 } 839} 840 841 842 843/* Return number of lines in common between current and desired frame 844 contents described to us only as vectors of hash codes OLDHASH and 845 NEWHASH. Consider only vpos range START to END (not including 846 END). Ignore short lines on the assumption that avoiding redrawing 847 such a line will have little weight. */ 848 849int 850scrolling_max_lines_saved (start, end, oldhash, newhash, cost) 851 int start, end; 852 int *oldhash, *newhash, *cost; 853{ 854 struct { int hash; int count; } lines[01000]; 855 register int i, h; 856 register int matchcount = 0; 857 int avg_length = 0; 858 int threshold; 859 860 /* Compute a threshold which is 1/4 of average length of these lines. */ 861 862 for (i = start; i < end; i++) 863 avg_length += cost[i]; 864 865 avg_length /= end - start; 866 threshold = avg_length / 4; 867 868 bzero (lines, sizeof lines); 869 870 /* Put new lines' hash codes in hash table. Ignore lines shorter 871 than the threshold. Thus, if the lines that are in common are 872 mainly the ones that are short, they won't count. */ 873 for (i = start; i < end; i++) 874 { 875 if (cost[i] > threshold) 876 { 877 h = newhash[i] & 0777; 878 lines[h].hash = newhash[i]; 879 lines[h].count++; 880 } 881 } 882 883 /* Look up old line hash codes in the hash table. Count number of 884 matches between old lines and new. */ 885 for (i = start; i < end; i++) 886 { 887 h = oldhash[i] & 0777; 888 if (oldhash[i] == lines[h].hash) 889 { 890 matchcount++; 891 if (--lines[h].count == 0) 892 lines[h].hash = 0; 893 } 894 } 895 896 return matchcount; 897} 898 899/* Return a measure of the cost of moving the lines starting with vpos 900 FROM, up to but not including vpos TO, down by AMOUNT lines (AMOUNT 901 may be negative). These are the same arguments that might be given 902 to scroll_frame_lines to perform this scrolling. */ 903 904int 905scroll_cost (frame, from, to, amount) 906 FRAME_PTR frame; 907 int from, to, amount; 908{ 909 /* Compute how many lines, at bottom of frame, 910 will not be involved in actual motion. */ 911 int limit = to; 912 int offset; 913 int height = FRAME_LINES (frame); 914 915 if (amount == 0) 916 return 0; 917 918 if (! scroll_region_ok) 919 limit = height; 920 else if (amount > 0) 921 limit += amount; 922 923 if (amount < 0) 924 { 925 int temp = to; 926 to = from + amount; 927 from = temp + amount; 928 amount = - amount; 929 } 930 931 offset = height - limit; 932 933 return 934 (FRAME_INSERT_COST (frame)[offset + from] 935 + (amount - 1) * FRAME_INSERTN_COST (frame)[offset + from] 936 + FRAME_DELETE_COST (frame)[offset + to] 937 + (amount - 1) * FRAME_DELETEN_COST (frame)[offset + to]); 938} 939 940/* Calculate the line insertion/deletion 941 overhead and multiply factor values */ 942 943static void 944line_ins_del (frame, ov1, pf1, ovn, pfn, ov, mf) 945 FRAME_PTR frame; 946 int ov1, ovn; 947 int pf1, pfn; 948 register int *ov, *mf; 949{ 950 register int i; 951 register int frame_lines = FRAME_LINES (frame); 952 register int insert_overhead = ov1 * 10; 953 register int next_insert_cost = ovn * 10; 954 955 for (i = frame_lines-1; i >= 0; i--) 956 { 957 mf[i] = next_insert_cost / 10; 958 next_insert_cost += pfn; 959 ov[i] = (insert_overhead + next_insert_cost) / 10; 960 insert_overhead += pf1; 961 } 962} 963 964static void 965ins_del_costs (frame, 966 one_line_string, multi_string, 967 setup_string, cleanup_string, 968 costvec, ncostvec, coefficient) 969 FRAME_PTR frame; 970 char *one_line_string, *multi_string; 971 char *setup_string, *cleanup_string; 972 int *costvec, *ncostvec; 973 int coefficient; 974{ 975 if (multi_string) 976 line_ins_del (frame, 977 string_cost (multi_string) * coefficient, 978 per_line_cost (multi_string) * coefficient, 979 0, 0, costvec, ncostvec); 980 else if (one_line_string) 981 line_ins_del (frame, 982 string_cost (setup_string) + string_cost (cleanup_string), 0, 983 string_cost (one_line_string), 984 per_line_cost (one_line_string), 985 costvec, ncostvec); 986 else 987 line_ins_del (frame, 988 9999, 0, 9999, 0, 989 costvec, ncostvec); 990} 991 992/* Calculate the insert and delete line costs. 993 Note that this is done even when running with a window system 994 because we want to know how long scrolling takes (and avoid it). 995 This must be redone whenever the frame height changes. 996 997 We keep the ID costs in a precomputed array based on the position 998 at which the I or D is performed. Also, there are two kinds of ID 999 costs: the "once-only" and the "repeated". This is to handle both 1000 those terminals that are able to insert N lines at a time (once- 1001 only) and those that must repeatedly insert one line. 1002 1003 The cost to insert N lines at line L is 1004 [tt.t_ILov + (frame_lines + 1 - L) * tt.t_ILpf] + 1005 N * [tt.t_ILnov + (frame_lines + 1 - L) * tt.t_ILnpf] 1006 1007 ILov represents the basic insert line overhead. ILpf is the padding 1008 required to allow the terminal time to move a line: insertion at line 1009 L changes (frame_lines + 1 - L) lines. 1010 1011 The first bracketed expression above is the overhead; the second is 1012 the multiply factor. Both are dependent only on the position at 1013 which the insert is performed. We store the overhead in 1014 FRAME_INSERT_COST (frame) and the multiply factor in 1015 FRAME_INSERTN_COST (frame). Note however that any insertion 1016 must include at least one multiply factor. Rather than compute this 1017 as FRAME_INSERT_COST (frame)[line]+FRAME_INSERTN_COST (frame)[line], 1018 we add FRAME_INSERTN_COST (frame) into FRAME_INSERT_COST (frame). 1019 This is reasonable because of the particular algorithm used in calcM. 1020 1021 Deletion is essentially the same as insertion. 1022 */ 1023 1024void 1025do_line_insertion_deletion_costs (frame, 1026 ins_line_string, multi_ins_string, 1027 del_line_string, multi_del_string, 1028 setup_string, cleanup_string, coefficient) 1029 FRAME_PTR frame; 1030 char *ins_line_string, *multi_ins_string; 1031 char *del_line_string, *multi_del_string; 1032 char *setup_string, *cleanup_string; 1033 int coefficient; 1034{ 1035 if (FRAME_INSERT_COST (frame) != 0) 1036 { 1037 FRAME_INSERT_COST (frame) = 1038 (int *) xrealloc (FRAME_INSERT_COST (frame), 1039 FRAME_LINES (frame) * sizeof (int)); 1040 FRAME_DELETEN_COST (frame) = 1041 (int *) xrealloc (FRAME_DELETEN_COST (frame), 1042 FRAME_LINES (frame) * sizeof (int)); 1043 FRAME_INSERTN_COST (frame) = 1044 (int *) xrealloc (FRAME_INSERTN_COST (frame), 1045 FRAME_LINES (frame) * sizeof (int)); 1046 FRAME_DELETE_COST (frame) = 1047 (int *) xrealloc (FRAME_DELETE_COST (frame), 1048 FRAME_LINES (frame) * sizeof (int)); 1049 } 1050 else 1051 { 1052 FRAME_INSERT_COST (frame) = 1053 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); 1054 FRAME_DELETEN_COST (frame) = 1055 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); 1056 FRAME_INSERTN_COST (frame) = 1057 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); 1058 FRAME_DELETE_COST (frame) = 1059 (int *) xmalloc (FRAME_LINES (frame) * sizeof (int)); 1060 } 1061 1062 ins_del_costs (frame, 1063 ins_line_string, multi_ins_string, 1064 setup_string, cleanup_string, 1065 FRAME_INSERT_COST (frame), FRAME_INSERTN_COST (frame), 1066 coefficient); 1067 ins_del_costs (frame, 1068 del_line_string, multi_del_string, 1069 setup_string, cleanup_string, 1070 FRAME_DELETE_COST (frame), FRAME_DELETEN_COST (frame), 1071 coefficient); 1072} 1073 1074/* arch-tag: cdb7149c-48e7-4793-a948-2786c8e45485 1075 (do not change this comment) */ 1076