1 /* $OpenBSD: lib_mvcur.c,v 1.3 1999/06/27 08:14:21 millert Exp $ */ 2 3 /**************************************************************************** 4 * Copyright (c) 1998 Free Software Foundation, Inc. * 5 * * 6 * Permission is hereby granted, free of charge, to any person obtaining a * 7 * copy of this software and associated documentation files (the * 8 * "Software"), to deal in the Software without restriction, including * 9 * without limitation the rights to use, copy, modify, merge, publish, * 10 * distribute, distribute with modifications, sublicense, and/or sell * 11 * copies of the Software, and to permit persons to whom the Software is * 12 * furnished to do so, subject to the following conditions: * 13 * * 14 * The above copyright notice and this permission notice shall be included * 15 * in all copies or substantial portions of the Software. * 16 * * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 18 * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 19 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 20 * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 21 * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 22 * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 23 * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 24 * * 25 * Except as contained in this notice, the name(s) of the above copyright * 26 * holders shall not be used in advertising or otherwise to promote the * 27 * sale, use or other dealings in this Software without prior written * 28 * authorization. * 29 ****************************************************************************/ 30 31 /**************************************************************************** 32 * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 33 * and: Eric S. Raymond <esr@snark.thyrsus.com> * 34 ****************************************************************************/ 35 36 37 /* 38 ** lib_mvcur.c 39 ** 40 ** The routines for moving the physical cursor and scrolling: 41 ** 42 ** void _nc_mvcur_init(void) 43 ** 44 ** void _nc_mvcur_resume(void) 45 ** 46 ** int mvcur(int old_y, int old_x, int new_y, int new_x) 47 ** 48 ** void _nc_mvcur_wrap(void) 49 ** 50 ** Comparisons with older movement optimizers: 51 ** SVr3 curses mvcur() can't use cursor_to_ll or auto_left_margin. 52 ** 4.4BSD curses can't use cuu/cud/cuf/cub/hpa/vpa/tab/cbt for local 53 ** motions. It doesn't use tactics based on auto_left_margin. Weirdly 54 ** enough, it doesn't use its own hardware-scrolling routine to scroll up 55 ** destination lines for out-of-bounds addresses! 56 ** old ncurses optimizer: less accurate cost computations (in fact, 57 ** it was broken and had to be commented out!). 58 ** 59 ** Compile with -DMAIN to build an interactive tester/timer for the movement 60 ** optimizer. You can use it to investigate the optimizer's behavior. 61 ** You can also use it for tuning the formulas used to determine whether 62 ** or not full optimization is attempted. 63 ** 64 ** This code has a nasty tendency to find bugs in terminfo entries, because it 65 ** exercises the non-cup movement capabilities heavily. If you think you've 66 ** found a bug, try deleting subsets of the following capabilities (arranged 67 ** in decreasing order of suspiciousness): it, tab, cbt, hpa, vpa, cuu, cud, 68 ** cuf, cub, cuu1, cud1, cuf1, cub1. It may be that one or more are wrong. 69 ** 70 ** Note: you should expect this code to look like a resource hog in a profile. 71 ** That's because it does a lot of I/O, through the tputs() calls. The I/O 72 ** cost swamps the computation overhead (and as machines get faster, this 73 ** will become even more true). Comments in the test exerciser at the end 74 ** go into detail about tuning and how you can gauge the optimizer's 75 ** effectiveness. 76 **/ 77 78 /**************************************************************************** 79 * 80 * Constants and macros for optimizer tuning. 81 * 82 ****************************************************************************/ 83 84 /* 85 * The average overhead of a full optimization computation in character 86 * transmission times. If it's too high, the algorithm will be a bit 87 * over-biased toward using cup rather than local motions; if it's too 88 * low, the algorithm may spend more time than is strictly optimal 89 * looking for non-cup motions. Profile the optimizer using the `t' 90 * command of the exerciser (see below), and round to the nearest integer. 91 * 92 * Yes, I (esr) thought about computing expected overhead dynamically, say 93 * by derivation from a running average of optimizer times. But the 94 * whole point of this optimization is to *decrease* the frequency of 95 * system calls. :-) 96 */ 97 #define COMPUTE_OVERHEAD 1 /* I use a 90MHz Pentium @ 9.6Kbps */ 98 99 /* 100 * LONG_DIST is the distance we consider to be just as costly to move over as a 101 * cup sequence is to emit. In other words, it's the length of a cup sequence 102 * adjusted for average computation overhead. The magic number is the length 103 * of "\033[yy;xxH", the typical cup sequence these days. 104 */ 105 #define LONG_DIST (8 - COMPUTE_OVERHEAD) 106 107 /* 108 * Tell whether a motion is optimizable by local motions. Needs to be cheap to 109 * compute. In general, all the fast moves go to either the right or left edge 110 * of the screen. So any motion to a location that is (a) further away than 111 * LONG_DIST and (b) further inward from the right or left edge than LONG_DIST, 112 * we'll consider nonlocal. 113 */ 114 #define NOT_LOCAL(fy, fx, ty, tx) ((tx > LONG_DIST) && (tx < screen_lines - 1 - LONG_DIST) && (abs(ty-fy) + abs(tx-fx) > LONG_DIST)) 115 116 /**************************************************************************** 117 * 118 * External interfaces 119 * 120 ****************************************************************************/ 121 122 /* 123 * For this code to work OK, the following components must live in the 124 * screen structure: 125 * 126 * int _char_padding; // cost of character put 127 * int _cr_cost; // cost of (carriage_return) 128 * int _cup_cost; // cost of (cursor_address) 129 * int _home_cost; // cost of (cursor_home) 130 * int _ll_cost; // cost of (cursor_to_ll) 131 *#if USE_HARD_TABS 132 * int _ht_cost; // cost of (tab) 133 * int _cbt_cost; // cost of (back_tab) 134 *#endif USE_HARD_TABS 135 * int _cub1_cost; // cost of (cursor_left) 136 * int _cuf1_cost; // cost of (cursor_right) 137 * int _cud1_cost; // cost of (cursor_down) 138 * int _cuu1_cost; // cost of (cursor_up) 139 * int _cub_cost; // cost of (parm_cursor_left) 140 * int _cuf_cost; // cost of (parm_cursor_right) 141 * int _cud_cost; // cost of (parm_cursor_down) 142 * int _cuu_cost; // cost of (parm_cursor_up) 143 * int _hpa_cost; // cost of (column_address) 144 * int _vpa_cost; // cost of (row_address) 145 * int _ech_cost; // cost of (erase_chars) 146 * int _rep_cost; // cost of (repeat_char) 147 * 148 * The USE_HARD_TABS switch controls whether it is reliable to use tab/backtabs 149 * for local motions. On many systems, it's not, due to uncertainties about 150 * tab delays and whether or not tabs will be expanded in raw mode. If you 151 * have parm_right_cursor, tab motions don't win you a lot anyhow. 152 */ 153 154 #include <curses.priv.h> 155 #include <term.h> 156 #include <ctype.h> 157 158 MODULE_ID("$From: lib_mvcur.c,v 1.57 1999/06/26 22:16:04 tom Exp $") 159 160 #define STRLEN(s) (s != 0) ? strlen(s) : 0 161 162 #define CURRENT_ATTR SP->_current_attr /* current phys attribute */ 163 #define CURRENT_ROW SP->_cursrow /* phys cursor row */ 164 #define CURRENT_COLUMN SP->_curscol /* phys cursor column */ 165 #define REAL_ATTR SP->_current_attr /* phys current attribute */ 166 #define WANT_CHAR(y, x) SP->_newscr->_line[y].text[x] /* desired state */ 167 #define BAUDRATE cur_term->_baudrate /* bits per second */ 168 169 #if defined(MAIN) || defined(NCURSES_TEST) 170 #include <sys/time.h> 171 172 static bool profiling = FALSE; 173 static float diff; 174 #endif /* MAIN */ 175 176 #define OPT_SIZE 512 177 178 static int normalized_cost(const char *const cap, int affcnt); 179 180 #if !HAVE_STRSTR 181 char * _nc_strstr(const char *haystack, const char *needle) 182 { 183 size_t len1 = strlen(haystack); 184 size_t len2 = strlen(needle); 185 char *result = 0; 186 187 while ((len1 != 0) && (len1-- >= len2)) { 188 if (!strncmp(haystack, needle, len2)) { 189 result = haystack; 190 break; 191 } 192 haystack++; 193 } 194 return result; 195 } 196 #endif 197 198 /**************************************************************************** 199 * 200 * Initialization/wrapup (including cost pre-computation) 201 * 202 ****************************************************************************/ 203 204 #ifdef TRACE 205 static int 206 trace_cost_of(const char *capname, const char *cap, int affcnt) 207 { 208 int result = _nc_msec_cost(cap,affcnt); 209 TR(TRACE_CHARPUT|TRACE_MOVE, ("CostOf %s %d", capname, result)); 210 return result; 211 } 212 #define CostOf(cap,affcnt) trace_cost_of(#cap,cap,affcnt); 213 214 static int 215 trace_normalized_cost(const char *capname, const char *cap, int affcnt) 216 { 217 int result = normalized_cost(cap,affcnt); 218 TR(TRACE_CHARPUT|TRACE_MOVE, ("NormalizedCost %s %d", capname, result)); 219 return result; 220 } 221 #define NormalizedCost(cap,affcnt) trace_normalized_cost(#cap,cap,affcnt); 222 223 #else 224 225 #define CostOf(cap,affcnt) _nc_msec_cost(cap,affcnt); 226 #define NormalizedCost(cap,affcnt) normalized_cost(cap,affcnt); 227 228 #endif 229 230 int _nc_msec_cost(const char *const cap, int affcnt) 231 /* compute the cost of a given operation */ 232 { 233 if (cap == 0) 234 return(INFINITY); 235 else 236 { 237 const char *cp; 238 float cum_cost = 0; 239 240 for (cp = cap; *cp; cp++) 241 { 242 /* extract padding, either mandatory or required */ 243 if (cp[0] == '$' && cp[1] == '<' && strchr(cp, '>')) 244 { 245 float number = 0; 246 247 for (cp += 2; *cp != '>'; cp++) 248 { 249 if (isdigit(*cp)) 250 number = number * 10 + (*cp - '0'); 251 else if (*cp == '.') 252 number += (*++cp - 10) / 10.0; 253 else if (*cp == '*') 254 number *= affcnt; 255 } 256 257 cum_cost += number * 10; 258 } 259 else 260 cum_cost += SP->_char_padding; 261 } 262 263 return((int)cum_cost); 264 } 265 } 266 267 static int normalized_cost(const char *const cap, int affcnt) 268 /* compute the effective character-count for an operation (round up) */ 269 { 270 int cost = _nc_msec_cost(cap, affcnt); 271 if (cost != INFINITY) 272 cost = (cost + SP->_char_padding - 1) / SP->_char_padding; 273 return cost; 274 } 275 276 static void reset_scroll_region(void) 277 /* Set the scroll-region to a known state (the default) */ 278 { 279 if (change_scroll_region) 280 { 281 TPUTS_TRACE("change_scroll_region"); 282 putp(tparm(change_scroll_region, 0, screen_lines - 1)); 283 } 284 } 285 286 void _nc_mvcur_resume(void) 287 /* what to do at initialization time and after each shellout */ 288 { 289 /* initialize screen for cursor access */ 290 if (enter_ca_mode) 291 { 292 TPUTS_TRACE("enter_ca_mode"); 293 putp(enter_ca_mode); 294 } 295 296 /* 297 * Doing this here rather than in _nc_mvcur_wrap() ensures that 298 * ncurses programs will see a reset scroll region even if a 299 * program that messed with it died ungracefully. 300 * 301 * This also undoes the effects of terminal init strings that assume 302 * they know the screen size. This is useful when you're running 303 * a vt100 emulation through xterm. 304 */ 305 reset_scroll_region(); 306 SP->_cursrow = SP->_curscol = -1; 307 308 /* restore cursor shape */ 309 if (SP->_cursor != -1) 310 { 311 int cursor = SP->_cursor; 312 SP->_cursor = -1; 313 curs_set (cursor); 314 } 315 } 316 317 void _nc_mvcur_init(void) 318 /* initialize the cost structure */ 319 { 320 /* 321 * 9 = 7 bits + 1 parity + 1 stop. 322 */ 323 SP->_char_padding = (9 * 1000 * 10) / (BAUDRATE > 0 ? BAUDRATE : 9600); 324 if (SP->_char_padding <= 0) 325 SP->_char_padding = 1; /* must be nonzero */ 326 TR(TRACE_CHARPUT|TRACE_MOVE, ("char_padding %d msecs", SP->_char_padding)); 327 328 /* non-parameterized local-motion strings */ 329 SP->_cr_cost = CostOf(carriage_return, 0); 330 SP->_home_cost = CostOf(cursor_home, 0); 331 SP->_ll_cost = CostOf(cursor_to_ll, 0); 332 #if USE_HARD_TABS 333 SP->_ht_cost = CostOf(tab, 0); 334 SP->_cbt_cost = CostOf(back_tab, 0); 335 #endif /* USE_HARD_TABS */ 336 SP->_cub1_cost = CostOf(cursor_left, 0); 337 SP->_cuf1_cost = CostOf(cursor_right, 0); 338 SP->_cud1_cost = CostOf(cursor_down, 0); 339 SP->_cuu1_cost = CostOf(cursor_up, 0); 340 341 SP->_smir_cost = CostOf(enter_insert_mode, 0); 342 SP->_rmir_cost = CostOf(exit_insert_mode, 0); 343 SP->_ip_cost = 0; 344 if (insert_padding) { 345 SP->_ip_cost = CostOf(insert_padding, 0); 346 } 347 348 /* 349 * Assumption: if the terminal has memory_relative addressing, the 350 * initialization strings or smcup will set single-page mode so we 351 * can treat it like absolute screen addressing. This seems to be true 352 * for all cursor_mem_address terminal types in the terminfo database. 353 */ 354 SP->_address_cursor = cursor_address ? cursor_address : cursor_mem_address; 355 356 /* 357 * Parametrized local-motion strings. This static cost computation 358 * depends on the following assumptions: 359 * 360 * (1) They never have * padding. In the entire master terminfo database 361 * as of March 1995, only the obsolete Zenith Z-100 pc violates this. 362 * (Proportional padding is found mainly in insert, delete and scroll 363 * capabilities). 364 * 365 * (2) The average case of cup has two two-digit parameters. Strictly, 366 * the average case for a 24 * 80 screen has ((10*10*(1 + 1)) + 367 * (14*10*(1 + 2)) + (10*70*(2 + 1)) + (14*70*4)) / (24*80) = 3.458 368 * digits of parameters. On a 25x80 screen the average is 3.6197. 369 * On larger screens the value gets much closer to 4. 370 * 371 * (3) The average case of cub/cuf/hpa/ech/rep has 2 digits of parameters 372 * (strictly, (((10 * 1) + (70 * 2)) / 80) = 1.8750). 373 * 374 * (4) The average case of cud/cuu/vpa has 2 digits of parameters 375 * (strictly, (((10 * 1) + (14 * 2)) / 24) = 1.5833). 376 * 377 * All these averages depend on the assumption that all parameter values 378 * are equally probable. 379 */ 380 SP->_cup_cost = CostOf(tparm(SP->_address_cursor, 23, 23), 1); 381 SP->_cub_cost = CostOf(tparm(parm_left_cursor, 23), 1); 382 SP->_cuf_cost = CostOf(tparm(parm_right_cursor, 23), 1); 383 SP->_cud_cost = CostOf(tparm(parm_down_cursor, 23), 1); 384 SP->_cuu_cost = CostOf(tparm(parm_up_cursor, 23), 1); 385 SP->_hpa_cost = CostOf(tparm(column_address, 23), 1); 386 SP->_vpa_cost = CostOf(tparm(row_address, 23), 1); 387 388 /* non-parameterized screen-update strings */ 389 SP->_ed_cost = NormalizedCost(clr_eos, 1); 390 SP->_el_cost = NormalizedCost(clr_eol, 1); 391 SP->_el1_cost = NormalizedCost(clr_bol, 1); 392 SP->_dch1_cost = NormalizedCost(delete_character, 1); 393 SP->_ich1_cost = NormalizedCost(insert_character, 1); 394 395 /* parameterized screen-update strings */ 396 SP->_dch_cost = NormalizedCost(tparm(parm_dch, 23), 1); 397 SP->_ich_cost = NormalizedCost(tparm(parm_ich, 23), 1); 398 SP->_ech_cost = NormalizedCost(tparm(erase_chars, 23), 1); 399 SP->_rep_cost = NormalizedCost(tparm(repeat_char, ' ', 23), 1); 400 401 SP->_cup_ch_cost = NormalizedCost(tparm(SP->_address_cursor, 23, 23), 1); 402 SP->_hpa_ch_cost = NormalizedCost(tparm(column_address, 23), 1); 403 404 /* pre-compute some capability lengths */ 405 SP->_carriage_return_length = STRLEN(carriage_return); 406 SP->_cursor_home_length = STRLEN(cursor_home); 407 SP->_cursor_to_ll_length = STRLEN(cursor_to_ll); 408 409 /* 410 * If save_cursor is used within enter_ca_mode, we should not use it for 411 * scrolling optimization, since the corresponding restore_cursor is not 412 * nested on the various terminals (vt100, xterm, etc.) which use this 413 * feature. 414 */ 415 if (save_cursor != 0 416 && enter_ca_mode != 0 417 && strstr(enter_ca_mode, save_cursor) != 0) { 418 T(("...suppressed sc/rc capability due to conflict with smcup/rmcup")); 419 save_cursor = 0; 420 restore_cursor = 0; 421 } 422 423 /* 424 * A different, possibly better way to arrange this would be to set 425 * SP->_endwin = TRUE at window initialization time and let this be 426 * called by doupdate's return-from-shellout code. 427 */ 428 _nc_mvcur_resume(); 429 } 430 431 void _nc_mvcur_wrap(void) 432 /* wrap up cursor-addressing mode */ 433 { 434 /* leave cursor at screen bottom */ 435 mvcur(-1, -1, screen_lines - 1, 0); 436 437 /* set cursor to normal mode */ 438 if (SP->_cursor != -1) 439 curs_set(1); 440 441 if (exit_ca_mode) 442 { 443 TPUTS_TRACE("exit_ca_mode"); 444 putp(exit_ca_mode); 445 } 446 /* 447 * Reset terminal's tab counter. There's a long-time bug that 448 * if you exit a "curses" program such as vi or more, tab 449 * forward, and then backspace, the cursor doesn't go to the 450 * right place. The problem is that the kernel counts the 451 * escape sequences that reset things as column positions. 452 * Utter a \r to reset this invisibly. 453 */ 454 _nc_outch('\r'); 455 } 456 457 /**************************************************************************** 458 * 459 * Optimized cursor movement 460 * 461 ****************************************************************************/ 462 463 /* 464 * Perform repeated-append, returning cost 465 */ 466 static inline int 467 repeated_append (int total, int num, int repeat, char *dst, const char *src) 468 { 469 register size_t src_len = strlen(src); 470 register size_t dst_len = STRLEN(dst); 471 472 if ((dst_len + repeat * src_len) < OPT_SIZE-1) { 473 total += (num * repeat); 474 if (dst) { 475 dst += dst_len; 476 while (repeat-- > 0) { 477 (void) strcpy(dst, src); 478 dst += src_len; 479 } 480 } 481 } else { 482 total = INFINITY; 483 } 484 return total; 485 } 486 487 #ifndef NO_OPTIMIZE 488 #define NEXTTAB(fr) (fr + init_tabs - (fr % init_tabs)) 489 490 /* 491 * Assume back_tab (CBT) does not wrap backwards at the left margin, return 492 * a negative value at that point to simplify the loop. 493 */ 494 #define LASTTAB(fr) ((fr > 0) ? ((fr - 1) / init_tabs) * init_tabs : -1) 495 496 /* Note: we'd like to inline this for speed, but GNU C barfs on the attempt. */ 497 498 static int 499 relative_move(char *result, int from_y,int from_x,int to_y,int to_x, bool ovw) 500 /* move via local motions (cuu/cuu1/cud/cud1/cub1/cub/cuf1/cuf/vpa/hpa) */ 501 { 502 int n, vcost = 0, hcost = 0; 503 504 if (result) 505 result[0] = '\0'; 506 507 if (to_y != from_y) 508 { 509 vcost = INFINITY; 510 511 if (row_address) 512 { 513 if (result) 514 (void) strcpy(result, tparm(row_address, to_y)); 515 vcost = SP->_vpa_cost; 516 } 517 518 if (to_y > from_y) 519 { 520 n = (to_y - from_y); 521 522 if (parm_down_cursor && SP->_cud_cost < vcost) 523 { 524 if (result) 525 (void) strcpy(result, tparm(parm_down_cursor, n)); 526 vcost = SP->_cud_cost; 527 } 528 529 if (cursor_down && (n * SP->_cud1_cost < vcost)) 530 { 531 if (result) 532 result[0] = '\0'; 533 vcost = repeated_append(0, SP->_cud1_cost, n, result, cursor_down); 534 } 535 } 536 else /* (to_y < from_y) */ 537 { 538 n = (from_y - to_y); 539 540 if (parm_up_cursor && SP->_cup_cost < vcost) 541 { 542 if (result) 543 (void) strcpy(result, tparm(parm_up_cursor, n)); 544 vcost = SP->_cup_cost; 545 } 546 547 if (cursor_up && (n * SP->_cuu1_cost < vcost)) 548 { 549 if (result) 550 result[0] = '\0'; 551 vcost = repeated_append(0, SP->_cuu1_cost, n, result, cursor_up); 552 } 553 } 554 555 if (vcost == INFINITY) 556 return(INFINITY); 557 } 558 559 if (result) 560 result += strlen(result); 561 562 if (to_x != from_x) 563 { 564 char str[OPT_SIZE]; 565 566 hcost = INFINITY; 567 568 if (column_address) 569 { 570 if (result) 571 (void) strcpy(result, tparm(column_address, to_x)); 572 hcost = SP->_hpa_cost; 573 } 574 575 if (to_x > from_x) 576 { 577 n = to_x - from_x; 578 579 if (parm_right_cursor && SP->_cuf_cost < hcost) 580 { 581 if (result) 582 (void) strcpy(result, tparm(parm_right_cursor, n)); 583 hcost = SP->_cuf_cost; 584 } 585 586 if (cursor_right) 587 { 588 int lhcost = 0; 589 590 str[0] = '\0'; 591 592 #if USE_HARD_TABS 593 /* use hard tabs, if we have them, to do as much as possible */ 594 if (init_tabs > 0 && tab) 595 { 596 int nxt, fr; 597 598 for (fr = from_x; (nxt = NEXTTAB(fr)) <= to_x; fr = nxt) 599 { 600 lhcost = repeated_append(lhcost, SP->_ht_cost, 1, str, tab); 601 if (lhcost == INFINITY) 602 break; 603 } 604 605 n = to_x - fr; 606 from_x = fr; 607 } 608 #endif /* USE_HARD_TABS */ 609 610 #if defined(REAL_ATTR) && defined(WANT_CHAR) 611 #ifdef BSD_TPUTS 612 /* 613 * If we're allowing BSD-style padding in tputs, don't generate 614 * a string with a leading digit. Otherwise, that will be 615 * interpreted as a padding value rather than sent to the 616 * screen. 617 */ 618 if (ovw 619 && n > 0 620 && vcost == 0 621 && str[0] == '\0' 622 && isdigit(TextOf(WANT_CHAR(to_y, from_x)))) 623 ovw = FALSE; 624 #endif 625 /* 626 * If we have no attribute changes, overwrite is cheaper. 627 * Note: must suppress this by passing in ovw = FALSE whenever 628 * WANT_CHAR would return invalid data. In particular, this 629 * is true between the time a hardware scroll has been done 630 * and the time the structure WANT_CHAR would access has been 631 * updated. 632 */ 633 if (ovw) 634 { 635 int i; 636 637 for (i = 0; i < n; i++) 638 if ((WANT_CHAR(to_y, from_x + i) & A_ATTRIBUTES) != CURRENT_ATTR) 639 { 640 ovw = FALSE; 641 break; 642 } 643 } 644 if (ovw) 645 { 646 char *sp; 647 int i; 648 649 sp = str + strlen(str); 650 651 for (i = 0; i < n; i++) 652 *sp++ = WANT_CHAR(to_y, from_x + i); 653 *sp = '\0'; 654 lhcost += n * SP->_char_padding; 655 } 656 else 657 #endif /* defined(REAL_ATTR) && defined(WANT_CHAR) */ 658 { 659 lhcost = repeated_append(lhcost, SP->_cuf1_cost, n, str, cursor_right); 660 } 661 662 if (lhcost < hcost) 663 { 664 if (result) 665 (void) strcpy(result, str); 666 hcost = lhcost; 667 } 668 } 669 } 670 else /* (to_x < from_x) */ 671 { 672 n = from_x - to_x; 673 674 if (parm_left_cursor && SP->_cub_cost < hcost) 675 { 676 if (result) 677 (void) strcpy(result, tparm(parm_left_cursor, n)); 678 hcost = SP->_cub_cost; 679 } 680 681 if (cursor_left) 682 { 683 int lhcost = 0; 684 685 str[0] = '\0'; 686 687 #if USE_HARD_TABS 688 if (init_tabs > 0 && back_tab) 689 { 690 int nxt, fr; 691 692 for (fr = from_x; (nxt = LASTTAB(fr)) >= to_x; fr = nxt) 693 { 694 lhcost = repeated_append(lhcost, SP->_cbt_cost, 1, str, back_tab); 695 if (lhcost == INFINITY) 696 break; 697 } 698 699 n = fr - to_x; 700 } 701 #endif /* USE_HARD_TABS */ 702 703 lhcost = repeated_append(lhcost, SP->_cub1_cost, n, str, cursor_left); 704 705 if (lhcost < hcost) 706 { 707 if (result) 708 (void) strcpy(result, str); 709 hcost = lhcost; 710 } 711 } 712 } 713 714 if (hcost == INFINITY) 715 return(INFINITY); 716 } 717 718 return(vcost + hcost); 719 } 720 #endif /* !NO_OPTIMIZE */ 721 722 /* 723 * With the machinery set up above, it's conceivable that 724 * onscreen_mvcur could be modified into a recursive function that does 725 * an alpha-beta search of motion space, as though it were a chess 726 * move tree, with the weight function being boolean and the search 727 * depth equated to length of string. However, this would jack up the 728 * computation cost a lot, especially on terminals without a cup 729 * capability constraining the search tree depth. So we settle for 730 * the simpler method below. 731 */ 732 733 static inline int 734 onscreen_mvcur(int yold,int xold,int ynew,int xnew, bool ovw) 735 /* onscreen move from (yold, xold) to (ynew, xnew) */ 736 { 737 char use[OPT_SIZE], *sp; 738 int tactic = 0, newcost, usecost = INFINITY; 739 740 #if defined(MAIN) || defined(NCURSES_TEST) 741 struct timeval before, after; 742 743 gettimeofday(&before, NULL); 744 #endif /* MAIN */ 745 746 /* tactic #0: use direct cursor addressing */ 747 sp = tparm(SP->_address_cursor, ynew, xnew); 748 if (sp) 749 { 750 tactic = 0; 751 (void) strcpy(use, sp); 752 usecost = SP->_cup_cost; 753 754 #if defined(TRACE) || defined(NCURSES_TEST) 755 if (!(_nc_optimize_enable & OPTIMIZE_MVCUR)) 756 goto nonlocal; 757 #endif /* TRACE */ 758 759 /* 760 * We may be able to tell in advance that the full optimization 761 * will probably not be worth its overhead. Also, don't try to 762 * use local movement if the current attribute is anything but 763 * A_NORMAL...there are just too many ways this can screw up 764 * (like, say, local-movement \n getting mapped to some obscure 765 * character because A_ALTCHARSET is on). 766 */ 767 if (yold == -1 || xold == -1 || NOT_LOCAL(yold, xold, ynew, xnew)) 768 { 769 #if defined(MAIN) || defined(NCURSES_TEST) 770 if (!profiling) 771 { 772 (void) fputs("nonlocal\n", stderr); 773 goto nonlocal; /* always run the optimizer if profiling */ 774 } 775 #else 776 goto nonlocal; 777 #endif /* MAIN */ 778 } 779 } 780 781 #ifndef NO_OPTIMIZE 782 /* tactic #1: use local movement */ 783 if (yold != -1 && xold != -1 784 && ((newcost=relative_move(NULL, yold, xold, ynew, xnew, ovw))!=INFINITY) 785 && newcost < usecost) 786 { 787 tactic = 1; 788 usecost = newcost; 789 } 790 791 /* tactic #2: use carriage-return + local movement */ 792 if (yold != -1 && carriage_return 793 && ((newcost=relative_move(NULL, yold,0,ynew,xnew, ovw)) != INFINITY) 794 && SP->_cr_cost + newcost < usecost) 795 { 796 tactic = 2; 797 usecost = SP->_cr_cost + newcost; 798 } 799 800 /* tactic #3: use home-cursor + local movement */ 801 if (cursor_home 802 && ((newcost=relative_move(NULL, 0, 0, ynew, xnew, ovw)) != INFINITY) 803 && SP->_home_cost + newcost < usecost) 804 { 805 tactic = 3; 806 usecost = SP->_home_cost + newcost; 807 } 808 809 /* tactic #4: use home-down + local movement */ 810 if (cursor_to_ll 811 && ((newcost=relative_move(NULL, screen_lines-1, 0, ynew, xnew, ovw)) != INFINITY) 812 && SP->_ll_cost + newcost < usecost) 813 { 814 tactic = 4; 815 usecost = SP->_ll_cost + newcost; 816 } 817 818 /* 819 * tactic #5: use left margin for wrap to right-hand side, 820 * unless strange wrap behavior indicated by xenl might hose us. 821 */ 822 if (auto_left_margin && !eat_newline_glitch 823 && yold > 0 && cursor_left 824 && ((newcost=relative_move(NULL, yold-1, screen_columns-1, ynew, xnew, ovw)) != INFINITY) 825 && SP->_cr_cost + SP->_cub1_cost + newcost + newcost < usecost) 826 { 827 tactic = 5; 828 usecost = SP->_cr_cost + SP->_cub1_cost + newcost; 829 } 830 831 /* 832 * These cases are ordered by estimated relative frequency. 833 */ 834 if (tactic) 835 { 836 if (tactic == 1) 837 (void) relative_move(use, yold, xold, ynew, xnew, ovw); 838 else if (tactic == 2) 839 { 840 (void) strcpy(use, carriage_return); 841 (void) relative_move(use + SP->_carriage_return_length, 842 yold,0,ynew,xnew, ovw); 843 } 844 else if (tactic == 3) 845 { 846 (void) strcpy(use, cursor_home); 847 (void) relative_move(use + SP->_cursor_home_length, 848 0, 0, ynew, xnew, ovw); 849 } 850 else if (tactic == 4) 851 { 852 (void) strcpy(use, cursor_to_ll); 853 (void) relative_move(use + SP->_cursor_to_ll_length, 854 screen_lines-1, 0, ynew, xnew, ovw); 855 } 856 else /* if (tactic == 5) */ 857 { 858 use[0] = '\0'; 859 if (xold > 0) 860 (void) strcat(use, carriage_return); 861 (void) strcat(use, cursor_left); 862 (void) relative_move(use + strlen(use), 863 yold-1, screen_columns-1, ynew, xnew, ovw); 864 } 865 } 866 #endif /* !NO_OPTIMIZE */ 867 868 #if defined(MAIN) || defined(NCURSES_TEST) 869 gettimeofday(&after, NULL); 870 diff = after.tv_usec - before.tv_usec 871 + (after.tv_sec - before.tv_sec) * 1000000; 872 if (!profiling) 873 (void) fprintf(stderr, "onscreen: %d msec, %f 28.8Kbps char-equivalents\n", 874 (int)diff, diff/288); 875 #endif /* MAIN */ 876 877 nonlocal: 878 if (usecost != INFINITY) 879 { 880 TPUTS_TRACE("mvcur"); 881 tputs(use, 1, _nc_outch); 882 return(OK); 883 } 884 else 885 return(ERR); 886 } 887 888 int mvcur(int yold, int xold, int ynew, int xnew) 889 /* optimized cursor move from (yold, xold) to (ynew, xnew) */ 890 { 891 TR(TRACE_MOVE, ("mvcur(%d,%d,%d,%d) called", yold, xold, ynew, xnew)); 892 893 if (yold == ynew && xold == xnew) 894 return(OK); 895 896 /* 897 * Most work here is rounding for terminal boundaries getting the 898 * column position implied by wraparound or the lack thereof and 899 * rolling up the screen to get ynew on the screen. 900 */ 901 902 if (xnew >= screen_columns) 903 { 904 ynew += xnew / screen_columns; 905 xnew %= screen_columns; 906 } 907 if (xold >= screen_columns) 908 { 909 int l; 910 911 l = (xold + 1) / screen_columns; 912 yold += l; 913 if (yold >= screen_lines) 914 l -= (yold - screen_lines - 1); 915 916 while (l > 0) { 917 if (newline) 918 { 919 TPUTS_TRACE("newline"); 920 tputs(newline, 0, _nc_outch); 921 } 922 else 923 putchar('\n'); 924 l--; 925 if (xold > 0) 926 { 927 if (carriage_return) 928 { 929 TPUTS_TRACE("carriage_return"); 930 tputs(carriage_return, 0, _nc_outch); 931 } 932 else 933 putchar('\r'); 934 xold = 0; 935 } 936 } 937 } 938 939 if (yold > screen_lines - 1) 940 yold = screen_lines - 1; 941 if (ynew > screen_lines - 1) 942 ynew = screen_lines - 1; 943 944 /* destination location is on screen now */ 945 return(onscreen_mvcur(yold, xold, ynew, xnew, TRUE)); 946 } 947 948 #if defined(TRACE) || defined(NCURSES_TEST) 949 int _nc_optimize_enable = OPTIMIZE_ALL; 950 #endif 951 952 #if defined(MAIN) || defined(NCURSES_TEST) 953 /**************************************************************************** 954 * 955 * Movement optimizer test code 956 * 957 ****************************************************************************/ 958 959 #include <tic.h> 960 #include <dump_entry.h> 961 962 const char *_nc_progname = "mvcur"; 963 964 static unsigned long xmits; 965 966 int tputs(const char *string, int affcnt GCC_UNUSED, int (*outc)(int) GCC_UNUSED) 967 /* stub tputs() that dumps sequences in a visible form */ 968 { 969 if (profiling) 970 xmits += strlen(string); 971 else 972 (void) fputs(_nc_visbuf(string), stdout); 973 return(OK); 974 } 975 976 int putp(const char *string) 977 { 978 return(tputs(string, 1, _nc_outch)); 979 } 980 981 int _nc_outch(int ch) 982 { 983 putc(ch, stdout); 984 return OK; 985 } 986 987 static char tname[MAX_ALIAS]; 988 989 static void load_term(void) 990 { 991 (void) setupterm(tname, STDOUT_FILENO, NULL); 992 } 993 994 static int roll(int n) 995 { 996 int i, j; 997 998 i = (RAND_MAX / n) * n; 999 while ((j = rand()) >= i) 1000 continue; 1001 return (j % n); 1002 } 1003 1004 int main(int argc GCC_UNUSED, char *argv[] GCC_UNUSED) 1005 { 1006 (void) strcpy(tname, termname()); 1007 load_term(); 1008 _nc_setupscreen(lines, columns, stdout); 1009 baudrate(); 1010 1011 _nc_mvcur_init(); 1012 NC_BUFFERED(FALSE); 1013 1014 (void) puts("The mvcur tester. Type ? for help"); 1015 1016 fputs("smcup:", stdout); 1017 putchar('\n'); 1018 1019 for (;;) 1020 { 1021 int fy, fx, ty, tx, n, i; 1022 char buf[BUFSIZ], capname[BUFSIZ]; 1023 1024 (void) fputs("> ", stdout); 1025 (void) fgets(buf, sizeof(buf), stdin); 1026 1027 if (buf[0] == '?') 1028 { 1029 (void) puts("? -- display this help message"); 1030 (void) puts("fy fx ty tx -- (4 numbers) display (fy,fx)->(ty,tx) move"); 1031 (void) puts("s[croll] n t b m -- display scrolling sequence"); 1032 (void) printf("r[eload] -- reload terminal info for %s\n", termname()); 1033 (void) puts("l[oad] <term> -- load terminal info for type <term>"); 1034 (void) puts("d[elete] <cap> -- delete named capability"); 1035 (void) puts("i[nspect] -- display terminal capabilities"); 1036 (void) puts("c[ost] -- dump cursor-optimization cost table"); 1037 (void) puts("o[optimize] -- toggle movement optimization"); 1038 (void) puts("t[orture] <num> -- torture-test with <num> random moves"); 1039 (void) puts("q[uit] -- quit the program"); 1040 } 1041 else if (sscanf(buf, "%d %d %d %d", &fy, &fx, &ty, &tx) == 4) 1042 { 1043 struct timeval before, after; 1044 1045 putchar('"'); 1046 1047 gettimeofday(&before, NULL); 1048 mvcur(fy, fx, ty, tx); 1049 gettimeofday(&after, NULL); 1050 1051 printf("\" (%ld msec)\n", 1052 (long)(after.tv_usec - before.tv_usec + (after.tv_sec - before.tv_sec) * 1000000)); 1053 } 1054 else if (sscanf(buf, "s %d %d %d %d", &fy, &fx, &ty, &tx) == 4) 1055 { 1056 struct timeval before, after; 1057 1058 putchar('"'); 1059 1060 gettimeofday(&before, NULL); 1061 _nc_scrolln(fy, fx, ty, tx); 1062 gettimeofday(&after, NULL); 1063 1064 printf("\" (%ld msec)\n", 1065 (long)(after.tv_usec - before.tv_usec + (after.tv_sec - before.tv_sec) * 1000000)); 1066 } 1067 else if (buf[0] == 'r') 1068 { 1069 (void) strcpy(tname, termname()); 1070 load_term(); 1071 } 1072 else if (sscanf(buf, "l %s", tname) == 1) 1073 { 1074 load_term(); 1075 } 1076 else if (sscanf(buf, "d %s", capname) == 1) 1077 { 1078 struct name_table_entry const *np = _nc_find_entry(capname, 1079 _nc_info_hash_table); 1080 1081 if (np == NULL) 1082 (void) printf("No such capability as \"%s\"\n", capname); 1083 else 1084 { 1085 switch(np->nte_type) 1086 { 1087 case BOOLEAN: 1088 cur_term->type.Booleans[np->nte_index] = FALSE; 1089 (void) printf("Boolean capability `%s' (%d) turned off.\n", 1090 np->nte_name, np->nte_index); 1091 break; 1092 1093 case NUMBER: 1094 cur_term->type.Numbers[np->nte_index] = -1; 1095 (void) printf("Number capability `%s' (%d) set to -1.\n", 1096 np->nte_name, np->nte_index); 1097 break; 1098 1099 case STRING: 1100 cur_term->type.Strings[np->nte_index] = (char *)NULL; 1101 (void) printf("String capability `%s' (%d) deleted.\n", 1102 np->nte_name, np->nte_index); 1103 break; 1104 } 1105 } 1106 } 1107 else if (buf[0] == 'i') 1108 { 1109 dump_init((char *)NULL, F_TERMINFO, S_TERMINFO, 70, 0, FALSE); 1110 dump_entry(&cur_term->type, FALSE, TRUE, 0); 1111 putchar('\n'); 1112 } 1113 else if (buf[0] == 'o') 1114 { 1115 if (_nc_optimize_enable & OPTIMIZE_MVCUR) 1116 { 1117 _nc_optimize_enable &=~ OPTIMIZE_MVCUR; 1118 (void) puts("Optimization is now off."); 1119 } 1120 else 1121 { 1122 _nc_optimize_enable |= OPTIMIZE_MVCUR; 1123 (void) puts("Optimization is now on."); 1124 } 1125 } 1126 /* 1127 * You can use the `t' test to profile and tune the movement 1128 * optimizer. Use iteration values in three digits or more. 1129 * At above 5000 iterations the profile timing averages are stable 1130 * to within a millisecond or three. 1131 * 1132 * The `overhead' field of the report will help you pick a 1133 * COMPUTE_OVERHEAD figure appropriate for your processor and 1134 * expected line speed. The `total estimated time' is 1135 * computation time plus a character-transmission time 1136 * estimate computed from the number of transmits and the baud 1137 * rate. 1138 * 1139 * Use this together with the `o' command to get a read on the 1140 * optimizer's effectiveness. Compare the total estimated times 1141 * for `t' runs of the same length in both optimized and un-optimized 1142 * modes. As long as the optimized times are less, the optimizer 1143 * is winning. 1144 */ 1145 else if (sscanf(buf, "t %d", &n) == 1) 1146 { 1147 float cumtime = 0, perchar; 1148 int speeds[] = {2400, 9600, 14400, 19200, 28800, 38400, 0}; 1149 1150 srand((unsigned)(getpid() + time((time_t *)0))); 1151 profiling = TRUE; 1152 xmits = 0; 1153 for (i = 0; i < n; i++) 1154 { 1155 /* 1156 * This does a move test between two random locations, 1157 * Random moves probably short-change the optimizer, 1158 * which will work better on the short moves probably 1159 * typical of doupdate()'s usage pattern. Still, 1160 * until we have better data... 1161 */ 1162 #ifdef FIND_COREDUMP 1163 int from_y = roll(lines); 1164 int to_y = roll(lines); 1165 int from_x = roll(columns); 1166 int to_x = roll(columns); 1167 1168 printf("(%d,%d) -> (%d,%d)\n", from_y, from_x, to_y, to_x); 1169 mvcur(from_y, from_x, to_y, to_x); 1170 #else 1171 mvcur(roll(lines), roll(columns), roll(lines), roll(columns)); 1172 #endif /* FIND_COREDUMP */ 1173 if (diff) 1174 cumtime += diff; 1175 } 1176 profiling = FALSE; 1177 1178 /* 1179 * Average milliseconds per character optimization time. 1180 * This is the key figure to watch when tuning the optimizer. 1181 */ 1182 perchar = cumtime / n; 1183 1184 (void) printf("%d moves (%ld chars) in %d msec, %f msec each:\n", 1185 n, xmits, (int)cumtime, perchar); 1186 1187 for (i = 0; speeds[i]; i++) 1188 { 1189 /* 1190 * Total estimated time for the moves, computation and 1191 * transmission both. Transmission time is an estimate 1192 * assuming 9 bits/char, 8 bits + 1 stop bit. 1193 */ 1194 float totalest = cumtime + xmits * 9 * 1e6 / speeds[i]; 1195 1196 /* 1197 * Per-character optimization overhead in character transmits 1198 * at the current speed. Round this to the nearest integer 1199 * to figure COMPUTE_OVERHEAD for the speed. 1200 */ 1201 float overhead = speeds[i] * perchar / 1e6; 1202 1203 (void) printf("%6d bps: %3.2f char-xmits overhead; total estimated time %15.2f\n", 1204 speeds[i], overhead, totalest); 1205 } 1206 } 1207 else if (buf[0] == 'c') 1208 { 1209 (void) printf("char padding: %d\n", SP->_char_padding); 1210 (void) printf("cr cost: %d\n", SP->_cr_cost); 1211 (void) printf("cup cost: %d\n", SP->_cup_cost); 1212 (void) printf("home cost: %d\n", SP->_home_cost); 1213 (void) printf("ll cost: %d\n", SP->_ll_cost); 1214 #if USE_HARD_TABS 1215 (void) printf("ht cost: %d\n", SP->_ht_cost); 1216 (void) printf("cbt cost: %d\n", SP->_cbt_cost); 1217 #endif /* USE_HARD_TABS */ 1218 (void) printf("cub1 cost: %d\n", SP->_cub1_cost); 1219 (void) printf("cuf1 cost: %d\n", SP->_cuf1_cost); 1220 (void) printf("cud1 cost: %d\n", SP->_cud1_cost); 1221 (void) printf("cuu1 cost: %d\n", SP->_cuu1_cost); 1222 (void) printf("cub cost: %d\n", SP->_cub_cost); 1223 (void) printf("cuf cost: %d\n", SP->_cuf_cost); 1224 (void) printf("cud cost: %d\n", SP->_cud_cost); 1225 (void) printf("cuu cost: %d\n", SP->_cuu_cost); 1226 (void) printf("hpa cost: %d\n", SP->_hpa_cost); 1227 (void) printf("vpa cost: %d\n", SP->_vpa_cost); 1228 } 1229 else if (buf[0] == 'x' || buf[0] == 'q') 1230 break; 1231 else 1232 (void) puts("Invalid command."); 1233 } 1234 1235 (void) fputs("rmcup:", stdout); 1236 _nc_mvcur_wrap(); 1237 putchar('\n'); 1238 1239 return(0); 1240 } 1241 1242 #endif /* MAIN */ 1243 1244 /* lib_mvcur.c ends here */ 1245