1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 /* 23 * Copyright (c) 1995-1999 by Sun Microsystems, Inc. 24 * All rights reserved. 25 */ 26 27 /* LINTLIBRARY */ 28 29 /* 30 * doupdate.c 31 * 32 * XCurses Library 33 * 34 * Copyright 1990, 1995 by Mortice Kern Systems Inc. All rights reserved. 35 * 36 */ 37 38 #ifdef M_RCSID 39 #ifndef lint 40 static char const rcsID[] = 41 "$Header: /team/ps/sun_xcurses/archive/local_changes/xcurses/src/lib/" 42 "libxcurses/src/libc/xcurses/rcs/doupdate.c 1.22 1998/06/04 12:13:38 " 43 "cbates Exp $"; 44 #endif 45 #endif 46 47 #include <sys/isa_defs.h> 48 #include <private.h> 49 #include <string.h> 50 #include <signal.h> 51 52 #undef SIGTSTP 53 54 /* 55 * This value is the ideal length for the cursor addressing sequence 56 * being four bytes long, ie. "<escape><cursor addressing code><row><col>". 57 * eg. VT52 - "\EYrc" or ADM3A - "\E=rc" 58 */ 59 #define JUMP_SIZE 4 60 61 /* 62 * This value is the ideal length for the clear-to-eol sequence 63 * being two bytes long, ie "<escape><clear eol code>". 64 */ 65 #define CEOL_SIZE 2 66 67 #define GOTO(r, c) ((void) __m_mvcur(curscr->_cury, curscr->_curx,\ 68 r, c, __m_outc), curscr->_cury = r, curscr->_curx = c) 69 70 typedef struct cost_op { 71 short cost; 72 short op; 73 } lcost; 74 75 typedef void (*t_action)(int, int); 76 77 78 #define LC(i, j) (lc[(i) * (LINES + 1) + (j)]) 79 80 static lcost *lc = NULL; 81 #if defined(_LP64) 82 static unsigned int *nhash = NULL; 83 #else 84 static unsigned long *nhash = NULL; 85 #endif 86 static t_action *del = NULL; 87 static t_action *ins_rep = NULL; 88 89 static WINDOW *newscr; 90 91 static void erase_bottom(int, int); 92 static void clear_bottom(int); 93 static void complex(void); 94 static int cost(int, int); 95 static void lines_delete(int, int); 96 static void lines_insert(int, int); 97 static void lines_replace(int, int); 98 static void script(int, int); 99 static int scroll_up(int); 100 static void simple(void); 101 static void text_replace(int); 102 #if 0 103 static int scroll_dn(int); 104 #endif 105 106 107 /* 108 * Wrapper that streams Curses output. 109 * 110 * All escape sequences going to the screen come through here. 111 * All ordinary characters go to the screen via the putc in doupdate.c 112 */ 113 int 114 __m_outc(int ch) 115 { 116 return (putc(ch, __m_screen->_of)); 117 } 118 119 /* 120 * Allocate or grow doupdate() structures. 121 */ 122 int 123 __m_doupdate_init(void) 124 { 125 void *new; 126 static short nlines = 0; 127 128 if (lines <= 0) 129 return (-1); 130 131 if (lines <= nlines) 132 return (0); 133 134 new = malloc((lines + 1) * (lines + 1) * sizeof (*lc)); 135 if (new == NULL) 136 return (-1); 137 if (lc != NULL) 138 free(lc); 139 lc = (lcost *) new; 140 141 new = malloc((lines + lines) * sizeof (*del)); 142 if (new == NULL) 143 return (-1); 144 if (del != NULL) 145 free(del); 146 del = (t_action *) new; 147 ins_rep = del + lines; 148 149 new = malloc(lines * sizeof (*nhash)); 150 if (new == NULL) 151 return (-1); 152 if (nhash != NULL) 153 free(nhash); 154 #if defined(_LP64) 155 nhash = (unsigned int *) new; 156 #else 157 nhash = (unsigned long *) new; 158 #endif 159 160 nlines = lines; 161 162 return (0); 163 } 164 165 static void 166 erase_bottom(int start, int end) 167 { 168 int i; 169 170 for (i = start; i < end; ++i) { 171 (void) __m_cc_erase(curscr, i, 0, i, curscr->_maxx - 1); 172 __m_cc_hash(curscr, __m_screen->_hash, i); 173 } 174 } 175 176 /* 177 * Clear from the start of the current row to bottom of screen. 178 */ 179 static void 180 clear_bottom(int y) 181 { 182 /* Restore default color pair before doing area clears. */ 183 if (back_color_erase) 184 (void) vid_puts(WA_NORMAL, 0, (void *) 0, __m_outc); 185 186 if (y == 0 && clear_screen != NULL) { 187 (void) TPUTS(clear_screen, 1, __m_outc); 188 } else { 189 (void) __m_mvcur(-1, -1, y, 0, __m_outc); 190 if (clr_eos != NULL) { 191 (void) TPUTS(clr_eos, 1, __m_outc); 192 } else if (clr_eol != NULL) { 193 for (;;) { 194 (void) TPUTS(clr_eol, 1, __m_outc); 195 if (LINES <= y) 196 break; 197 (void) __m_mvcur(y, 0, y + 1, 0, __m_outc); 198 ++y; 199 } 200 } 201 } 202 203 curscr->_cury = y; 204 curscr->_curx = 0; 205 } 206 207 208 209 /* 210 * Rewrite of text_replace() implementation by C. Bates of MKS 211 * 212 * This code creates a list of 'regions' for each test line which 213 * is to be replaced. Each region describes a portion of the line. 214 * Logic is performed on the list of regions, then the regions 215 * are used to generate output. 216 */ 217 typedef struct LineRegion { 218 int col; /* Starting column of region */ 219 int size; /* Size of region */ 220 /* 0: Difference Region, 1: Common Region, 2: Delete Region */ 221 int type; 222 } LineRegion; 223 #define REGION_DIFFERENT 0 224 #define REGION_COMMON 1 225 #define REGION_DELETE 2 226 227 #define DELETE_SEARCH_LIMIT 4 228 #define DELETE_THRESHOLD 10 229 230 static LineRegion regions[1024]; 231 int nRegions = 0; 232 233 /* 234 * Return the first column of the completely blank End-of-line 235 */ 236 static int 237 _find_blank_tail(int row) 238 { 239 cchar_t *nptr; 240 int tail = COLS; 241 242 if (!clr_eol) 243 return (COLS); 244 /* 245 * Find start of blank tail region. 246 */ 247 nptr = &newscr->_line[row][COLS]; 248 for (; 0 < tail; --tail) { 249 if (!__m_cc_compare(--nptr, &newscr->_bg, 1)) 250 break; 251 } 252 return (tail); 253 } 254 255 /* 256 * Send all the characters in the region to the terminal 257 */ 258 static void 259 _writeRegion(int row, LineRegion region) 260 { 261 short npair; 262 attr_t nattr; 263 int i; 264 cchar_t *optr = &curscr->_line[row][region.col]; 265 cchar_t *nptr = &newscr->_line[row][region.col]; 266 267 for (i = 0; i < region.size; i++, nptr++, optr++) { 268 nattr = nptr->_at; 269 npair = nptr->_co; 270 271 /* 272 * Change attribute state. 273 */ 274 if ((ATTR_STATE != nattr) || (optr->_at != nattr) || 275 (cur_term->_co != npair)) { 276 (void) vid_puts(nattr, npair, NULL, __m_outc); 277 } 278 /* 279 * Don't display internal characters. 280 */ 281 if (nptr->_f) 282 (void) __m_cc_write(nptr); 283 284 /* 285 * Update copy of screen image. 286 */ 287 *optr = *nptr; 288 curscr->_curx = region.col + i + 1; 289 } 290 } 291 292 /* 293 * Delete some characters from the terminal for this region 294 */ 295 static void 296 _deleteRegion(int row, LineRegion region) 297 { 298 int i; 299 cchar_t *optr = &curscr->_line[row][region.col]; 300 301 if ((region.size <= 1) || !parm_dch) { 302 for (i = 0; i < region.size; i++) 303 (void) TPUTS(delete_character, 1, __m_outc); 304 } else { 305 (void) TPUTS(tparm(parm_dch, (long)region.size, 306 0, 0, 0, 0, 0, 0, 0, 0), region.size, __m_outc); 307 } 308 for (i = region.col; i < COLS - region.size; i++) { 309 /* 310 * Delete the chars in the image of the real screen 311 */ 312 *optr = *(optr + region.size); 313 optr++; 314 } 315 } 316 317 /* 318 * Use clr_eol control if possible 319 */ 320 static void 321 _clearToEOL(int row, int tail) 322 { 323 if (tail < COLS) { 324 GOTO(row, tail); 325 /* 326 * Restore default color pair before area clear. 327 */ 328 if (back_color_erase) 329 (void) vid_puts(WA_NORMAL, 0, NULL, __m_outc); 330 331 (void) TPUTS(clr_eol, 1, __m_outc); 332 (void) __m_cc_erase(curscr, row, tail, row, COLS - 1); 333 } 334 } 335 336 /* 337 * Delete leading common region 338 */ 339 static void 340 _normalizeRegions1(void) 341 { 342 int iRegion; 343 344 /* 345 * Delete leading common region 346 */ 347 if (regions[0].type == REGION_COMMON) { 348 nRegions--; 349 for (iRegion = 0; iRegion < nRegions; iRegion++) { 350 regions[iRegion] = regions[iRegion + 1]; 351 } 352 } 353 } 354 355 /* 356 * Give each region a size, then delete all trailing common regions 357 */ 358 static void 359 _normalizeRegions2(void) 360 { 361 int iRegion; 362 363 for (iRegion = 0; iRegion < nRegions - 1; iRegion++) { 364 regions[iRegion].size = regions[iRegion + 1].col - 365 regions[iRegion].col; 366 } 367 regions[nRegions - 1].size = COLS - regions[nRegions - 1].col; 368 369 /* 370 * Delete trailing common regions 371 */ 372 while (regions[nRegions - 1].type == REGION_COMMON) 373 nRegions--; 374 } 375 376 /* 377 * Tiny common regions are merged into adjacent difference regions 378 */ 379 static void 380 _mergeTinyRegions(void) 381 { 382 int from; 383 int to; 384 for (from = 1, to = 1; from < nRegions; ) { 385 if ((regions[from].type == REGION_COMMON) && 386 (regions[from].size < JUMP_SIZE)) { 387 /* 388 * Merge out tiny common regions 389 */ 390 regions[to - 1].size += regions[from].size; 391 /* 392 * Now join adjacent non-common regions 393 */ 394 if (++from < nRegions) 395 regions[to - 1].size += regions[from++].size; 396 } else { 397 regions[to++] = regions[from++]; 398 } 399 } 400 nRegions = to; 401 } 402 403 /* 404 * Create the initial list of regions for this row 405 */ 406 static int 407 _findRegions(int row) 408 { 409 int cmp; 410 int old_cmp; 411 int col; 412 int bestDeleteCount; 413 cchar_t *nptr = &newscr->_line[row][0]; 414 cchar_t *optr = &curscr->_line[row][0]; 415 416 col = 0; 417 nRegions = 0; 418 bestDeleteCount = 0; 419 if ((__m_screen->_flags & S_INS_DEL_CHAR) && 420 (parm_dch || delete_character)) { 421 int bestFit = 0; 422 int deletePoint; 423 int deleteCount; 424 int matches; 425 426 /* 427 * Skip to first difference 428 */ 429 for (col = 0; col < COLS; col++) { 430 if (!__m_cc_compare(&optr[col], &nptr[col], 1)) 431 break; 432 } 433 deletePoint = col; 434 for (deleteCount = 1; deleteCount < DELETE_SEARCH_LIMIT; 435 deleteCount++) { 436 matches = 0; 437 for (col = deletePoint; col < COLS - deleteCount; 438 col++) { 439 if (__m_cc_compare(&optr[col + deleteCount], 440 &nptr[col], 1)) 441 matches++; 442 else 443 break; 444 } 445 if (matches > bestFit) { 446 bestFit = matches; 447 bestDeleteCount = deleteCount; 448 } 449 } 450 if (bestFit > DELETE_THRESHOLD) { 451 regions[nRegions].type = REGION_DELETE; 452 regions[nRegions].col = deletePoint; 453 regions[nRegions].size = bestDeleteCount; 454 nRegions++; 455 col = deletePoint + bestDeleteCount; 456 } else { 457 col = 0; 458 nRegions = 0; 459 /* Forget trying to use character delete */ 460 bestDeleteCount = 0; 461 } 462 } 463 for (old_cmp = -1; col + bestDeleteCount < COLS; col++) { 464 cmp = __m_cc_compare(&optr[col + bestDeleteCount], 465 &nptr[col], 1); 466 if (cmp != old_cmp) { 467 regions[nRegions].type = cmp ? REGION_COMMON : 468 REGION_DIFFERENT; 469 regions[nRegions].col = col; 470 regions[nRegions].size = 0; /* Determine later */ 471 nRegions++; 472 old_cmp = cmp; 473 } 474 } 475 if (bestDeleteCount) { 476 /* 477 * Force update of end-of-line if delete is to be used 478 */ 479 regions[nRegions].type = REGION_DIFFERENT; 480 regions[nRegions].col = col; 481 regions[nRegions].size = 0; /* Determine later */ 482 nRegions++; 483 } 484 _normalizeRegions1(); 485 if (nRegions == 0) 486 return (0); /* No difference regions */ 487 488 _normalizeRegions2(); 489 return (1); 490 } 491 492 /* 493 * Determine if Clr-EOL optimization can be used, and 494 * adjust regions accordingly 495 */ 496 static int 497 _ceolAdjustRegions(int row) 498 { 499 int iRegion; 500 int blankEolStart = _find_blank_tail(row); 501 502 for (iRegion = 0; iRegion < nRegions; iRegion++) { 503 switch (regions[iRegion].type) { 504 case REGION_DIFFERENT: 505 if (regions[iRegion].col >= blankEolStart) { 506 /* 507 * Delete this and all following regions 508 */ 509 nRegions = iRegion; 510 return (blankEolStart); 511 } 512 if (regions[iRegion].col + regions[iRegion].size > 513 blankEolStart) { 514 /* 515 * Truncate this region to end 516 * where blank EOL starts 517 */ 518 regions[iRegion].size = blankEolStart - 519 regions[iRegion].col; 520 /* 521 * Delete all following regions 522 */ 523 nRegions = iRegion + 1; 524 return (blankEolStart); 525 } 526 break; 527 case REGION_COMMON: 528 break; 529 case REGION_DELETE: /* Scrap the whole thing */ 530 return (COLS); 531 } 532 } 533 return (COLS); /* Couldn't use Clear EOL optimization */ 534 } 535 536 /* 537 * Generate output, based on region list 538 */ 539 static void 540 _updateRegions(int row) 541 { 542 int ceolStart; 543 int iRegion; 544 545 ceolStart = _ceolAdjustRegions(row); 546 547 /* 548 * regions are guaranteed to start with a non-common region. 549 * tiny common regions have also been merged into 550 * bracketting common-regions. 551 */ 552 if (nRegions) { 553 for (iRegion = 0; iRegion < nRegions; iRegion++) { 554 switch (regions[iRegion].type) { 555 case REGION_COMMON: 556 break; 557 case REGION_DELETE: 558 /* 559 * Start of non-common region 560 */ 561 GOTO(row, regions[iRegion].col); 562 _deleteRegion(row, regions[iRegion]); 563 break; 564 case REGION_DIFFERENT: 565 /* 566 * Star of non-common region 567 */ 568 GOTO(row, regions[iRegion].col); 569 _writeRegion(row, regions[iRegion]); 570 break; 571 } 572 } 573 } 574 if (ceolStart != COLS) { 575 _clearToEOL(row, ceolStart); 576 } 577 } 578 579 /* 580 * The new text_replace algorithm, which uses regions 581 */ 582 static void 583 text_replace(int row) 584 { 585 if (!_findRegions(row)) 586 return; 587 _mergeTinyRegions(); 588 _updateRegions(row); 589 590 /* 591 * Line wrapping checks. 592 */ 593 if (COLS <= curscr->_curx) { 594 --curscr->_curx; 595 if (auto_right_margin && (row < LINES - 1)) { 596 if (eat_newline_glitch) { 597 (void) __m_outc('\r'); 598 (void) __m_outc('\n'); 599 } 600 ++curscr->_cury; 601 curscr->_curx = 0; 602 } 603 } 604 } 605 606 /* 607 * Replace a block of lines. 608 * Only ever used for complex(). 609 */ 610 static void 611 lines_replace(int from, int to_1) 612 { 613 for (; from < to_1; ++from) 614 text_replace(from); 615 } 616 617 /* 618 * Delete a block of lines. 619 * Only ever used for complex(). 620 */ 621 static void 622 lines_delete(int from, int to_1) 623 { 624 int count = to_1 - from; 625 626 if (LINES <= to_1) { 627 erase_bottom(from, LINES); 628 clear_bottom(from); 629 } else { 630 GOTO(from, 0); 631 (void) winsdelln(curscr, -count); 632 633 if (parm_delete_line != NULL) { 634 /* 635 * Assume that the sequence to delete more than one 636 * line is faster than repeated single delete_lines. 637 */ 638 (void) TPUTS(tparm(parm_delete_line, (long)count, 639 0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc); 640 } else if (delete_line != NULL) { 641 while (from++ < to_1) 642 (void) TPUTS(delete_line, 1, __m_outc); 643 } else { 644 /* Error -- what to do. */ 645 return; 646 } 647 } 648 } 649 650 /* 651 * Insert a block of lines. 652 * Only ever used for complex(). 653 * 654 * We must assume that insert_line and parm_insert_line reset the 655 * cursor column to zero. Therefore it is text_replace() responsiblity 656 * to move the cursor to the correct column to begin the update. 657 */ 658 static void 659 lines_insert(int from, int to_1) 660 { 661 int row; 662 int count = to_1 - from; 663 664 /* 665 * Position the cursor and insert a block of lines into the screen 666 * image now, insert lines into the physical screen, then draw the 667 * new screen lines. 668 */ 669 GOTO(from, 0); 670 (void) winsdelln(curscr, count); 671 672 if (parm_insert_line != NULL) { 673 /* 674 * Assume that the sequence to insert more than one line is 675 * faster than repeated single insert_lines. 676 */ 677 (void) TPUTS(tparm(parm_insert_line, (long)count, 678 0, 0, 0, 0, 0, 0, 0, 0), count, __m_outc); 679 } else if (insert_line != NULL) { 680 /* 681 * For the single line insert we use to iterate moving 682 * the cursor, inserting, and then drawing a line. That 683 * would appear to be slow but visually appealing. However, 684 * people on slow terminals want speed and those on fast 685 * terminal won't see it. 686 */ 687 for (row = from; row < to_1; ++row) 688 (void) TPUTS(insert_line, 1, __m_outc); 689 } else { 690 /* Error -- what to do. */ 691 return; 692 } 693 694 for (row = from; row < to_1; ++row) 695 text_replace(row); 696 } 697 698 static int 699 scroll_up(int n) 700 { 701 int count = n; 702 int start, finish, to; 703 704 if (scroll_forward != NULL) { 705 GOTO(LINES-1, 0); 706 while (0 < n--) 707 (void) TPUTS(scroll_forward, 1, __m_outc); 708 } else if (parm_delete_line != NULL && 1 < n) { 709 GOTO(0, 0); 710 (void) TPUTS(tparm(parm_delete_line, (long)n, 711 0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc); 712 } else if (delete_line != NULL) { 713 GOTO(0, 0); 714 while (0 < n--) 715 (void) TPUTS(delete_line, 1, __m_outc); 716 } else { 717 return (0); 718 } 719 720 /* Scroll recorded image. */ 721 start = 0; 722 finish = count-1; 723 to = lines; 724 725 (void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1); 726 (void) __m_ptr_move((void **) curscr->_line, 727 curscr->_maxy, start, finish, to); 728 729 simple(); 730 731 return (1); 732 } 733 734 #if 0 735 static int 736 scroll_dn(int n) 737 { 738 int count = n; 739 int start, finish, to; 740 741 if (LINES < n) 742 return (0); 743 744 if (scroll_reverse != NULL) { 745 GOTO(0, 0); 746 while (0 < n--) 747 (void) TPUTS(scroll_reverse, 1, __m_outc); 748 } else if (parm_insert_line != NULL && 1 < n) { 749 GOTO(0, 0); 750 (void) TPUTS(tparm(parm_insert_line, (long)n, 751 0, 0, 0, 0, 0, 0, 0, 0), n, __m_outc); 752 } else if (insert_line != NULL) { 753 GOTO(0, 0); 754 while (0 < n--) 755 (void) TPUTS(insert_line, 1, __m_outc); 756 } else { 757 return (0); 758 } 759 760 /* Scroll recorded image. */ 761 start = lines - count; 762 finish = lines - 1; 763 to = 0; 764 765 (void) __m_cc_erase(curscr, start, 0, finish, curscr->_maxx-1); 766 (void) __m_ptr_move((void **) curscr->_line, 767 curscr->_maxy, start, finish, to); 768 769 simple(); 770 771 return (1); 772 } 773 #endif 774 775 /* 776 * Dynamic programming algorithm for the string edit problem. 777 * 778 * This is a modified Gosling cost algorithm that takes into account 779 * null/move operations. 780 * 781 * Costs for move, delete, replace, and insert are 0, 1, 2, and 3 782 * repectively. 783 */ 784 #define MOVE_COST 0 785 #define REPLACE_COST 10 786 #define INSERT_COST 12 787 #define DELETE_COST 1 788 789 static int 790 cost(int fr, int lr) 791 { 792 lcost *lcp; 793 int or, nr, cc; 794 #if defined(_LP64) 795 unsigned int *ohash = __m_screen->_hash; 796 #else 797 unsigned long *ohash = __m_screen->_hash; 798 #endif 799 800 /* 801 * Prepare initial row and column of cost matrix. 802 * 803 * 0 3 6 9 ... 804 * 1 805 * 2 806 * 3 807 * : 808 */ 809 LC(fr, fr).cost = MOVE_COST; 810 for (cc = 1, ++lr, nr = fr+1; nr <= lr; ++nr, ++cc) { 811 /* Top row is 3, 6, 9, ... */ 812 LC(fr, nr).cost = cc * INSERT_COST; 813 LC(fr, nr).op = 'i'; 814 815 /* Left column is 1, 2, 3, ... */ 816 LC(nr, fr).cost = cc * DELETE_COST; 817 LC(nr, fr).op = 'd'; 818 } 819 820 for (--lr, or = fr; or <= lr; ++or) { 821 for (nr = fr; nr <= lr; ++nr) { 822 lcp = &LC(or + 1, nr + 1); 823 824 /* Assume move op. */ 825 lcp->cost = LC(or, nr).cost; 826 lcp->op = 'm'; 827 828 if (ohash[or] != nhash[nr]) { 829 /* Lines are different, assume replace op. */ 830 lcp->cost += REPLACE_COST; 831 lcp->op = 'r'; 832 } 833 834 /* Compare insert op. */ 835 if ((cc = LC(or + 1, nr).cost + INSERT_COST) < 836 lcp->cost) { 837 lcp->cost = cc; 838 lcp->op = 'i'; 839 } 840 841 /* Compare delete op. */ 842 if ((cc = LC(or, nr + 1).cost + DELETE_COST) < 843 lcp->cost) { 844 lcp->cost = cc; 845 lcp->op = 'd'; 846 } 847 } 848 } 849 850 return (LC(lr + 1, lr + 1).cost); 851 } 852 853 /* 854 * Build edit script. 855 * 856 * Normally this would be a recursve routine doing the deletes, inserts, 857 * and replaces on individual lines. Instead we build the script so that 858 * we can later do the operations on a block basis. For terminals with 859 * parm_delete or parm_insert strings this will be better in terms of the 860 * number of characters sent to delete and insert a block of lines. 861 * 862 * Also we can optimize the script so that tail inserts become replaces. 863 * This saves unnecessary inserts operations when the tail can just be 864 * overwritten. 865 */ 866 static void 867 script(int fr, int lr) 868 { 869 int i, j; 870 cchar_t *cp; 871 872 i = j = lr + 1; 873 874 (void) memset(del, 0, sizeof (*del) * LINES); 875 (void) memset(ins_rep, 0, sizeof (*ins_rep) * LINES); 876 877 do { 878 /* 879 * We don't have to bounds check i or j becuase row fr and 880 * column fr of lc have been preset in order to guarantee the 881 * correct motion. 882 */ 883 switch (LC(i, j).op) { 884 case 'i': 885 --j; 886 ins_rep[j] = lines_insert; 887 break; 888 case 'd': 889 --i; 890 del[i] = lines_delete; 891 break; 892 case 'm': 893 --i; 894 --j; 895 break; 896 case 'r': 897 --i; 898 --j; 899 ins_rep[j] = lines_replace; 900 break; 901 } 902 } while (fr < i || fr < j); 903 904 /* Optimize Tail Inserts */ 905 for (i = LINES-1; 0 <= i && ins_rep[i] == lines_insert; --i) { 906 /* Make each character in the screen line image invalid. */ 907 for (cp = curscr->_line[i], j = 0; j < COLS; ++j, ++cp) 908 cp->_n = -1; 909 ins_rep[i] = lines_replace; 910 } 911 } 912 913 /* 914 * Complex update algorithm using insert/delete line operations. 915 * 916 * References: 917 * [MyM86] E.W. Myers & W. Miller, Row Replacement Algorithms for 918 * Screen Editors, TR 86-19, Dept. Computer Science, U. of Arizona 919 * [MyM87] E.W. Myers & W. Miller, A Simple Row Replacement Method, 920 * TR 86-28, Dept. Computer Science, U. of Arizona 921 * [Mil87] W. Miller, A Software Tools Sampler, Prentice-Hall, 1987 922 * [Gos81] James Gosling, A redisplay algorithm, Proceedings of the 923 * ACM Symposium on Text Manipulation, SIGPLAN Notices, 924 * 16(6) June 1981, pg 123-129 925 * 926 * All the above were reviewed and experimented with. Due to the nature of 927 * Curses' having to handling overlapping WINDOWs, the only suitable 928 * algorithum is [Gos81]. The others are better suited to editor type 929 * applications that have one window being the entire terminal screen. 930 * 931 */ 932 static void 933 complex(void) 934 { 935 int fr = -1; 936 int i, j, lr; 937 t_action func; 938 939 /* Find block of lines to change */ 940 for (i = 0; i < LINES; ++i) { 941 if (newscr->_first[i] < newscr->_last[i]) { 942 /* Compute new hash. */ 943 __m_cc_hash(newscr, nhash, i); 944 if (fr == -1) 945 fr = i; 946 lr = i; 947 } else { 948 /* Line not dirty so hash same as before. */ 949 nhash[i] = __m_screen->_hash[i]; 950 } 951 } 952 953 if (fr != -1) { 954 /* Gosling */ 955 (void) cost(fr, lr); 956 script(fr, lr); 957 958 /* Do deletes first in reverse order. */ 959 for (j = lr; fr <= j; --j) { 960 if (del[j] != (t_action) 0) { 961 for (i = j-1; fr <= i; --i) 962 if (del[i] == (t_action) 0) 963 break; 964 965 lines_delete(i+1, j+1); 966 j = i; 967 } 968 } 969 970 /* Do insert/replace in forward order. */ 971 for (i = fr; i <= lr; ++i) { 972 if ((func = ins_rep[i]) != (t_action) 0) { 973 /* Find size of block */ 974 for (j = i; j <= lr && ins_rep[j] == func; ++j) 975 ; 976 (*func)(i, j); 977 i = j - 1; 978 } 979 } 980 /* 981 * _line[], which contains pointers to screen lines, 982 * may be shuffled. 983 */ 984 for (i = fr; i <= lr; ++i) { 985 /* Save new hash for next update. */ 986 __m_screen->_hash[i] = nhash[i]; 987 988 /* Mark line as untouched. */ 989 newscr->_first[i] = newscr->_maxx; 990 newscr->_last[i] = -1; 991 } 992 } 993 } 994 995 /* 996 * Simple screen update algorithm 997 * 998 * We perform a simple incremental update of the terminal screen. 999 * Only the segment of a line that was touched is replaced on the 1000 * line. 1001 */ 1002 static void 1003 simple(void) 1004 { 1005 int row; 1006 1007 for (row = 0; row < newscr->_maxy; ++row) { 1008 if (newscr->_first[row] < newscr->_last[row]) { 1009 text_replace(row); 1010 1011 /* Mark line as untouched. */ 1012 newscr->_first[row] = newscr->_maxx; 1013 newscr->_last[row] = -1; 1014 __m_cc_hash(curscr, __m_screen->_hash, row); 1015 } 1016 } 1017 1018 newscr->_flags &= ~W_REDRAW_WINDOW; 1019 } 1020 1021 void 1022 wtouchln_hard(WINDOW *w, int y, int n) 1023 { 1024 int last; 1025 1026 last = w->_maxx; 1027 1028 for (; (y < w->_maxy) && (0 < n); ++y, --n) { 1029 /* 1030 * Force compare in doupdate to fail. 1031 * Touch should be unconditional 1032 */ 1033 (void) memset(&__m_screen->_curscr->_line[w->_begy + y][w->_begx], 1034 0xff, last * sizeof (cchar_t)); 1035 } 1036 } 1037 /* 1038 * Send all changes made to _newscr to the physical terminal. 1039 * 1040 * If idlok() is set TRUE then doupdate will try and use hardware insert 1041 * and delete line sequences in an effort to optimize output. idlok() 1042 * should really only be used in applications that want a proper scrolling 1043 * effect. 1044 * 1045 * Added scroll heuristic to handle special case where a full size window 1046 * with full size scroll region, will scroll the window and replace dirty 1047 * lines instead of performing usual cost/script operations. 1048 */ 1049 int 1050 doupdate(void) 1051 { 1052 #ifdef SIGTSTP 1053 int (*oldsig)(int) = signal(SIGTSTP, SIG_IGN); 1054 #endif 1055 1056 if (pollTypeahead()) { 1057 return (OK); 1058 } 1059 newscr = __m_screen->_newscr; 1060 1061 if (__m_screen->_flags & S_ENDWIN) { 1062 /* Return from temporary escape done with endwin(). */ 1063 __m_screen->_flags &= ~S_ENDWIN; 1064 1065 (void) reset_prog_mode(); 1066 if (enter_ca_mode != NULL) 1067 (void) TPUTS(enter_ca_mode, 1, __m_outc); 1068 if (keypad_xmit != NULL) 1069 (void) TPUTS(keypad_xmit, 1, __m_outc); 1070 if (ena_acs != NULL) 1071 (void) TPUTS(ena_acs, 1, __m_outc); 1072 1073 /* Force redraw of screen. */ 1074 newscr->_flags |= W_CLEAR_WINDOW; 1075 } 1076 /* 1077 * When redrawwing a window, we not only assume that line 1078 * noise may have lost characters, but line noise may have 1079 * generated bogus characters on the screen outside the 1080 * the window in question, in which case redraw the entire 1081 * screen to be sure. 1082 */ 1083 if ((newscr->_flags & (W_CLEAR_WINDOW | W_REDRAW_WINDOW)) || 1084 (curscr->_flags & W_CLEAR_WINDOW)) { 1085 erase_bottom(0, newscr->_maxy); 1086 clear_bottom(0); 1087 (void) wtouchln(newscr, 0, newscr->_maxy, 1); 1088 newscr->_flags &= ~W_CLEAR_WINDOW; 1089 curscr->_flags &= ~W_CLEAR_WINDOW; 1090 } 1091 1092 /* 1093 * Scrolling heuristic should only be used if lines being 1094 * scrolled are clean because scrolling overrides updates 1095 * 1096 * Right now, the following code should always turn off 1097 * scrolling, because the internal scroll touches the 1098 * scrolled lines. This thing requires a lot more care 1099 * than I have right now... 1100 */ 1101 if (newscr->_scroll) { 1102 int y; 1103 for (y = 0; y < newscr->_maxy; ++y) { 1104 if (0 <= newscr->_last[y]) { 1105 newscr->_scroll = 0; 1106 } 1107 } 1108 newscr->_scroll = 0; /* Just fudge it for now ... */ 1109 } 1110 if (newscr->_flags & W_REDRAW_WINDOW) { 1111 simple(); 1112 } else { 1113 if (newscr->_scroll == 0) { 1114 if (__m_screen->_flags & S_INS_DEL_LINE) { 1115 complex(); 1116 } else { 1117 simple(); 1118 } 1119 } else { 1120 if (!scroll_up(newscr->_scroll)) { 1121 if (__m_screen->_flags & S_INS_DEL_LINE) { 1122 complex(); 1123 } else { 1124 simple(); 1125 } 1126 } 1127 } 1128 } 1129 1130 if (!(newscr->_flags & W_LEAVE_CURSOR)) { 1131 GOTO(newscr->_cury, newscr->_curx); 1132 } 1133 1134 if (!(curscr->_flags & W_FLUSH)) { 1135 (void) fflush(__m_screen->_of); 1136 } 1137 1138 newscr->_scroll = curscr->_scroll = 0; 1139 1140 /* Send labels to terminal that supports them. */ 1141 __m_slk_doupdate(); 1142 #ifdef SIGTSTP 1143 signal(SIGTSTP, oldsig); 1144 #endif 1145 1146 return (OK); 1147 } 1148 1149 /* 1150 * If true, the implementation may use hardware insert and delete, 1151 * character features of the terminal. The window parameter 1152 * is ignored. 1153 */ 1154 /* ARGSUSED */ 1155 void 1156 idcok(WINDOW *w, bool bf) 1157 { 1158 __m_screen->_flags &= ~S_INS_DEL_CHAR; 1159 if (bf) 1160 __m_screen->_flags |= S_INS_DEL_CHAR; 1161 } 1162 1163 /* 1164 * If true, the implementation may use hardware insert, delete, 1165 * and scroll line features of the terminal. The window parameter 1166 * is ignored. 1167 */ 1168 /* ARGSUSED */ 1169 int 1170 idlok(WINDOW *w, bool bf) 1171 { 1172 __m_screen->_flags &= ~S_INS_DEL_LINE; 1173 if (bf && has_il()) 1174 __m_screen->_flags |= S_INS_DEL_LINE; 1175 1176 return (OK); 1177 } 1178 1179 /* 1180 * Use the POSIX 32-bit CRC function to compute a hash value 1181 * for the window line. 1182 */ 1183 void 1184 #if defined(_LP64) 1185 __m_cc_hash(WINDOW *w, unsigned int *array, int y) 1186 #else 1187 __m_cc_hash(WINDOW *w, unsigned long *array, int y) 1188 #endif 1189 { 1190 array[y] = 0; 1191 m_crcposix(&array[y], (unsigned char *) w->_line[y], 1192 (size_t)(w->_maxx * sizeof (**w->_line))); 1193 } 1194