150276Speter/**************************************************************************** 2184989Srafan * Copyright (c) 1998-2007,2008 Free Software Foundation, Inc. * 350276Speter * * 450276Speter * Permission is hereby granted, free of charge, to any person obtaining a * 550276Speter * copy of this software and associated documentation files (the * 650276Speter * "Software"), to deal in the Software without restriction, including * 750276Speter * without limitation the rights to use, copy, modify, merge, publish, * 850276Speter * distribute, distribute with modifications, sublicense, and/or sell * 950276Speter * copies of the Software, and to permit persons to whom the Software is * 1050276Speter * furnished to do so, subject to the following conditions: * 1150276Speter * * 1250276Speter * The above copyright notice and this permission notice shall be included * 1350276Speter * in all copies or substantial portions of the Software. * 1450276Speter * * 1550276Speter * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS * 1650276Speter * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF * 1750276Speter * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. * 1850276Speter * IN NO EVENT SHALL THE ABOVE COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, * 1950276Speter * DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR * 2050276Speter * OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR * 2150276Speter * THE USE OR OTHER DEALINGS IN THE SOFTWARE. * 2250276Speter * * 2350276Speter * Except as contained in this notice, the name(s) of the above copyright * 2450276Speter * holders shall not be used in advertising or otherwise to promote the * 2550276Speter * sale, use or other dealings in this Software without prior written * 2650276Speter * authorization. * 2750276Speter ****************************************************************************/ 2850276Speter 2950276Speter/**************************************************************************** 3050276Speter * Author: Zeyd M. Ben-Halim <zmbenhal@netcom.com> 1992,1995 * 3150276Speter * and: Eric S. Raymond <esr@snark.thyrsus.com> * 32184989Srafan * and: Thomas E. Dickey 1996-on * 33184989Srafan * and: Alexander V Lukyanov 1997-1998 * 3450276Speter ****************************************************************************/ 3550276Speter 3650276Speter/****************************************************************************** 3750276Speter 3850276SpeterNAME 3950276Speter hardscroll.c -- hardware-scrolling optimization for ncurses 4050276Speter 4150276SpeterSYNOPSIS 4250276Speter void _nc_scroll_optimize(void) 4350276Speter 4450276SpeterDESCRIPTION 4550276Speter OVERVIEW 4650276Speter 4750276SpeterThis algorithm for computes optimum hardware scrolling to transform an 4850276Speterold screen (curscr) into a new screen (newscr) via vertical line moves. 4950276Speter 5050276SpeterBecause the screen has a `grain' (there are insert/delete/scroll line 5150276Speteroperations but no insert/delete/scroll column operations), it is efficient 5250276Speterbreak the update algorithm into two pieces: a first stage that does only line 5350276Spetermoves, optimizing the end product of user-invoked insertions, deletions, and 5450276Speterscrolls; and a second phase (corresponding to the present doupdate code in 5550276Speterncurses) that does only line transformations. 5650276Speter 5750276SpeterThe common case we want hardware scrolling for is to handle line insertions 5850276Speterand deletions in screen-oriented text-editors. This two-stage approach will 5950276Speteraccomplish that at a low computation and code-size cost. 6050276Speter 6150276Speter LINE-MOVE COMPUTATION 6250276Speter 6350276SpeterNow, to a discussion of the line-move computation. 6450276Speter 6550276SpeterFor expository purposes, consider the screen lines to be represented by 6650276Speterintegers 0..23 (with the understanding that the value of 23 may vary). 6750276SpeterLet a new line introduced by insertion, scrolling, or at the bottom of 6850276Speterthe screen following a line delete be given the index -1. 6950276Speter 7050276SpeterAssume that the real screen starts with lines 0..23. Now, we have 7150276Speterthe following possible line-oriented operations on the screen: 7250276Speter 7350276SpeterInsertion: inserts a line at a given screen row, forcing all lines below 7450276Speterto scroll forward. The last screen line is lost. For example, an insertion 7550276Speterat line 5 would produce: 0..4 -1 5..23. 7650276Speter 7750276SpeterDeletion: deletes a line at a given screen row, forcing all lines below 7850276Speterto scroll forward. The last screen line is made new. For example, a deletion 7950276Speterat line 7 would produce: 0..6 8..23 -1. 8050276Speter 8150276SpeterScroll up: move a range of lines up 1. The bottom line of the range 8250276Speterbecomes new. For example, scrolling up the region from 9 to 14 will 8350276Speterproduce 0..8 10..14 -1 15..23. 8450276Speter 8550276SpeterScroll down: move a range of lines down 1. The top line of the range 8650276Speterbecomes new. For example, scrolling down the region from 12 to 16 will produce 8750276Speter0..11 -1 12..15 17..23. 8850276Speter 8950276SpeterNow, an obvious property of all these operations is that they preserve the 9050276Speterorder of old lines, though not their position in the sequence. 9150276Speter 9250276SpeterThe key trick of this algorithm is that the original line indices described 9350276Speterabove are actually maintained as _line[].oldindex fields in the window 9450276Speterstructure, and stick to each line through scroll and insert/delete operations. 9550276Speter 9650276SpeterThus, it is possible at update time to look at the oldnum fields and compute 9750276Speteran optimal set of il/dl/scroll operations that will take the real screen 9850276Speterlines to the virtual screen lines. Once these vertical moves have been done, 9950276Speterwe can hand off to the second stage of the update algorithm, which does line 10050276Spetertransformations. 10150276Speter 10250276SpeterNote that the move computation does not need to have the full generality 10350276Speterof a diff algorithm (which it superficially resembles) because lines cannot 10450276Speterbe moved out of order. 10550276Speter 10650276Speter THE ALGORITHM 10750276Speter 10850276SpeterThe scrolling is done in two passes. The first pass is from top to bottom 10950276Speterscroling hunks UP. The second one is from bottom to top scrolling hunks DOWN. 11050276SpeterObviously enough, no lines to be scrolled will be destroyed. (lav) 11150276Speter 11250276SpeterHOW TO TEST THIS: 11350276Speter 11450276SpeterUse the following production: 11550276Speter 11650276Speterhardscroll: hardscroll.c 11750276Speter $(CC) -g -DSCROLLDEBUG hardscroll.c -o hardscroll 11850276Speter 11950276SpeterThen just type scramble vectors and watch. The following test loads are 12050276Spetera representative sample of cases: 12150276Speter 12250276Speter----------------------------- CUT HERE ------------------------------------ 12350276Speter# No lines moved 12450276Speter 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 12550276Speter# 12650276Speter# A scroll up 12750276Speter 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 -1 12850276Speter# 12950276Speter# A scroll down 13050276Speter-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 13150276Speter# 13250276Speter# An insertion (after line 12) 13350276Speter 0 1 2 3 4 5 6 7 8 9 10 11 12 -1 13 14 15 16 17 18 19 20 21 22 13450276Speter# 13550276Speter# A simple deletion (line 10) 13650276Speter 0 1 2 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 21 22 23 -1 13750276Speter# 13850276Speter# A more complex case 13950276Speter-1 -1 -1 -1 -1 3 4 5 6 7 -1 -1 8 9 10 11 12 13 14 15 16 17 -1 -1 14050276Speter----------------------------- CUT HERE ------------------------------------ 14150276Speter 14250276SpeterAUTHOR 14350276Speter Eric S. Raymond <esr@snark.thyrsus.com>, November 1994 14450276Speter New algorithm by Alexander V. Lukyanov <lav@yars.free.net>, Aug 1997 14550276Speter 14650276Speter*****************************************************************************/ 14750276Speter 14850276Speter#include <curses.priv.h> 14950276Speter 150184989SrafanMODULE_ID("$Id: hardscroll.c,v 1.42 2008/08/03 23:49:30 tom Exp $") 15150276Speter 15250276Speter#if defined(SCROLLDEBUG) || defined(HASHDEBUG) 15350276Speter 15450276Speter# undef screen_lines 15550276Speter# define screen_lines MAXLINES 15676726SpeterNCURSES_EXPORT_VAR(int) 15776726Speteroldnums[MAXLINES]; 15850276Speter# define OLDNUM(n) oldnums[n] 15950276Speter# define _tracef printf 16050276Speter# undef TR 16150276Speter# define TR(n, a) if (_nc_tracing & (n)) { _tracef a ; putchar('\n'); } 16250276Speter 163174993Srafanextern NCURSES_EXPORT_VAR(unsigned) _nc_tracing; 164174993Srafan 16550276Speter#else /* no debug */ 16650276Speter 16750276Speter/* OLDNUM(n) indicates which line will be shifted to the position n. 16850276Speter if OLDNUM(n) == _NEWINDEX, then the line n in new, not shifted from 16950276Speter somewhere. */ 17076726SpeterNCURSES_EXPORT_VAR(int *) 171174993Srafan_nc_oldnums = 0; /* obsolete: keep for ABI compat */ 17276726Speter 17350276Speter# if USE_HASHMAP 174174993Srafan# define oldnums SP->_oldnum_list 17550276Speter# define OLDNUM(n) oldnums[n] 17676726Speter# else /* !USE_HASHMAP */ 17750276Speter# define OLDNUM(n) newscr->_line[n].oldindex 17876726Speter# endif /* !USE_HASHMAP */ 17950276Speter 180174993Srafan#define OLDNUM_SIZE SP->_oldnum_size 181174993Srafan 18250276Speter#endif /* defined(SCROLLDEBUG) || defined(HASHDEBUG) */ 18350276Speter 18476726SpeterNCURSES_EXPORT(void) 18576726Speter_nc_scroll_optimize(void) 18650276Speter/* scroll optimization to transform curscr to newscr */ 18750276Speter{ 18850276Speter int i; 18950276Speter int start, end, shift; 19050276Speter 191174993Srafan TR(TRACE_ICALLS, (T_CALLED("_nc_scroll_optimize"))); 19250276Speter 19350276Speter#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG) 19450276Speter#if USE_HASHMAP 19550276Speter /* get enough storage */ 196174993Srafan if (OLDNUM_SIZE < screen_lines) { 19750276Speter int *new_oldnums = typeRealloc(int, screen_lines, oldnums); 19850276Speter if (!new_oldnums) 19950276Speter return; 20050276Speter oldnums = new_oldnums; 201174993Srafan OLDNUM_SIZE = screen_lines; 20250276Speter } 20350276Speter /* calculate the indices */ 20450276Speter _nc_hash_map(); 20550276Speter#endif 20650276Speter#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */ 20750276Speter 20850276Speter#ifdef TRACE 209174993Srafan if (USE_TRACEF(TRACE_UPDATE | TRACE_MOVE)) { 21050276Speter _nc_linedump(); 211174993Srafan _nc_unlock_global(tracef); 212174993Srafan } 21350276Speter#endif /* TRACE */ 21450276Speter 21550276Speter /* pass 1 - from top to bottom scrolling up */ 21676726Speter for (i = 0; i < screen_lines;) { 21750276Speter while (i < screen_lines && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) <= i)) 21850276Speter i++; 21950276Speter if (i >= screen_lines) 22050276Speter break; 22150276Speter 22276726Speter shift = OLDNUM(i) - i; /* shift > 0 */ 22350276Speter start = i; 22450276Speter 22550276Speter i++; 22676726Speter while (i < screen_lines && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i 22776726Speter == shift) 22850276Speter i++; 22976726Speter end = i - 1 + shift; 23050276Speter 23150276Speter TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift)); 23250276Speter#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG) 23376726Speter if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) { 23450276Speter TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll")); 23550276Speter continue; 23650276Speter } 23750276Speter#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */ 23850276Speter } 23950276Speter 24050276Speter /* pass 2 - from bottom to top scrolling down */ 24176726Speter for (i = screen_lines - 1; i >= 0;) { 24250276Speter while (i >= 0 && (OLDNUM(i) == _NEWINDEX || OLDNUM(i) >= i)) 24350276Speter i--; 24450276Speter if (i < 0) 24550276Speter break; 24650276Speter 24776726Speter shift = OLDNUM(i) - i; /* shift < 0 */ 24850276Speter end = i; 24950276Speter 25050276Speter i--; 25150276Speter while (i >= 0 && OLDNUM(i) != _NEWINDEX && OLDNUM(i) - i == shift) 25250276Speter i--; 25376726Speter start = i + 1 - (-shift); 25450276Speter 25550276Speter TR(TRACE_UPDATE | TRACE_MOVE, ("scroll [%d, %d] by %d", start, end, shift)); 25650276Speter#if !defined(SCROLLDEBUG) && !defined(HASHDEBUG) 25776726Speter if (_nc_scrolln(shift, start, end, screen_lines - 1) == ERR) { 25850276Speter TR(TRACE_UPDATE | TRACE_MOVE, ("unable to scroll")); 25950276Speter continue; 26050276Speter } 26150276Speter#endif /* !defined(SCROLLDEBUG) && !defined(HASHDEBUG) */ 26250276Speter } 263174993Srafan TR(TRACE_ICALLS, (T_RETURN(""))); 26450276Speter} 26550276Speter 26650276Speter#if defined(TRACE) || defined(SCROLLDEBUG) || defined(HASHDEBUG) 26776726SpeterNCURSES_EXPORT(void) 26876726Speter_nc_linedump(void) 26950276Speter/* dump the state of the real and virtual oldnum fields */ 27050276Speter{ 27176726Speter int n; 272174993Srafan char *buf = 0; 27376726Speter size_t want = (screen_lines + 1) * 4; 27450276Speter 275184989Srafan if ((buf = typeMalloc(char, want)) != 0) { 27650276Speter 277184989Srafan (void) strcpy(buf, "virt"); 278184989Srafan for (n = 0; n < screen_lines; n++) 279184989Srafan (void) sprintf(buf + strlen(buf), " %02d", OLDNUM(n)); 280184989Srafan TR(TRACE_UPDATE | TRACE_MOVE, (buf)); 281184989Srafan free(buf); 282184989Srafan } 28350276Speter} 28450276Speter#endif /* defined(TRACE) || defined(SCROLLDEBUG) */ 28550276Speter 28650276Speter#ifdef SCROLLDEBUG 28750276Speter 28850276Speterint 28976726Spetermain(int argc GCC_UNUSED, char *argv[]GCC_UNUSED) 29050276Speter{ 29176726Speter char line[BUFSIZ], *st; 29250276Speter 29350276Speter#ifdef TRACE 29450276Speter _nc_tracing = TRACE_MOVE; 29550276Speter#endif 29676726Speter for (;;) { 29776726Speter int n; 29850276Speter 29950276Speter for (n = 0; n < screen_lines; n++) 30050276Speter oldnums[n] = _NEWINDEX; 30150276Speter 30250276Speter /* grab the test vector */ 30376726Speter if (fgets(line, sizeof(line), stdin) == (char *) NULL) 30450276Speter exit(EXIT_SUCCESS); 30550276Speter 30650276Speter /* parse it */ 30750276Speter n = 0; 30876726Speter if (line[0] == '#') { 30950276Speter (void) fputs(line, stderr); 31050276Speter continue; 31150276Speter } 31250276Speter st = strtok(line, " "); 31350276Speter do { 31450276Speter oldnums[n++] = atoi(st); 31550276Speter } while 31676726Speter ((st = strtok((char *) NULL, " ")) != 0); 31750276Speter 31850276Speter /* display it */ 31950276Speter (void) fputs("Initial input:\n", stderr); 32050276Speter _nc_linedump(); 32150276Speter 32250276Speter _nc_scroll_optimize(); 32350276Speter } 32450276Speter} 32550276Speter 32650276Speter#endif /* SCROLLDEBUG */ 32750276Speter 32850276Speter/* hardscroll.c ends here */ 329