The present invention is in the field of data compression in data communications and in particular is an improved method of compressing particular types of data transmitted between a host computer and one or more remotely located command driven terminals.
These terminal devices are configured to provide bidirectional communication with a host computer to which they are connected, either directly, or via intervening modem/telephone line combinations or other links. In particular, communications are effected by writing into and reading from the contents of the addressable screen buffer.
Like most CRT terminals with memory, the screen buffer includes addressable locations for character contents and attribute data, which controls certain aspects of the visual presentation of data at associated screen locations, such as highlighted video, reverse video, blinking, etc.
The original 3270 terminals had their origin many hardware generations ago. A simple command language for controlling the writing of data into the screen buffers was created and is part of the operating systems with which these devices are normally used. In particular, the command set includes commands to erase the buffer before writing, erase the buffer and set the alternate screen size before writing, and to write without a preceding erase. The data to be written can contain buffer control orders which include Set Buffer Address (SBA), i.e., to position to a particular address in the screen buffer at which the data orders will be place.
It should therefore be understood that the contents of the screen buffer can be modified by either erasing the entire contents with an erase command followed by order to write to all locations at which the user wants data displayed, or alternatively a write command may be sent with orders to simply overwrite portions of the screen buffer leaving other portions unchanged. Both techniques are commonly used in application programs written to run on machines connected to such terminals.
Normally, only modified fields are transmitted back from the terminal device, i.e., fields in which the terminal operator added, changed, or deleted characters. These altered fields are transmitted back to the host computer preceded by the screen buffer address which the field begins. Some applications need the field data to be transmitted whether it has been modified or not. This is accomplished by having the application set the Modified Data Tag (MDT) in the attribute in the Start Field order. Those familiar with the 3270 family of terminals know that the Modified Data Tag for these particular devices is the lowest order bit in the attribute character of the Start Field order. The terminal controller sets this bit when the data is modified by the terminal operator and, as noted above, the application can also set it in order to cause the terminal controller to return the contents of the field irrespective of actions at the terminal.
Data representing the contents of fields with set Modified Data Tags are returned upon the operation of one of a plurality of interrupt keys, the most common of which is the carriage return or ENTER key. In this way, bidirectional communications are effected based on location in the screen buffer, and thus, the location of data on the screen itself.
As the sophistication of computer systems has increased and user's desire for larger terminals with greater data display capabilities have increased, larger terminals have been introduced into the 3270 family. These devices have larger screen buffers in order to accommodate more screen data and to provide a greater variety of display attributes.
The size of the screen buffers generally varies from 480 display positions on a 3270 Model 1 to 9,920 positions on a 3290 display station, one of the more sophisticated terminals of this particular family.
As large computer systems, such as airline reservation computers and the like have become more common, there are an increasing number of remotely located terminals connected to the computers via telephone links. As the size of the screen buffers is increased, it will be appreciated that significant amounts of time are required to transmit large blocks of data from a host computer running a particular application to a remote terminal device. For example, if a 9600 bit per second modem is used on a voice grade telephone line, it takes a period on the order of 25 to 30 seconds to transmit the entire contents of a 3290 screen buffer from the host to the terminal. Transmission of high volumes of data between a host computer and a terminal has the doubly undesirable effect of increasing costs for running the system by using a large amount of telephone line capacity as well as increasing the delay that users experience in interactive operations with the host.
For example, some schemes for data compression over links between a host computer and a command driven terminal maintain an indication of which particular fields on the terminal are modified by a command string sent by an application program and will transmit only instructions to overwrite the modified fields. Any redundant commands that write unchanged data to other fields are stripped out. Depending on the application that is running on the host and its activity with respect to redefining fields, this can be a useful to approach to reducing the overall amount of data transmitted from host to terminal. This is particularly true if the programmer of the application was inattentive to opportunities to avoid the transmission of redundant data for unchanged fields. Indeed, one of the main reasons that the need and market exists for data compressors of this type is the fact that there are many large computer installations with relatively old applications running where less than optimum techniques were employed by the programmers in writing the code that transmits output to remote terminals.
Additionally, modem programming languages and application generators typically insulate the programmer from the hardware requirements. In some cases, it is not possible for the programmer to direct efficient use of the terminal display in the chosen language. Also, many languages support the use of multiple terminal types independent of the application program logic. Only after the type of terminal is established in a session with the host are the true physical limitations of the display buffer known. In these cases, efficient use of the terminal buffer and telecommunications lines may not be enforced by the programmer but must be driven by the terminal processor or a compression program such as the invention described in this specification.
While transmitting only modified fields can be effective, if the fields are long and only minor modifications have been made, there is still a significant amount of redundant data transmitted.
U.S. Pat. No. 4,750,137 issued Jun. 7, 1988 to Harper et al. shows another method of compressing data that is transmitted to command driven terminals. The method disclosed in Harper creates two buffers sized identically to the terminal buffer for each terminal currently connected to the host system. One of these buffers is used to maintain a present state image of the buffer contents. In other words, this is a locally maintained duplication of what should be the contents of the screen buffer at a particular remote terminal.
These two buffers are then compared on a byte-by-byte basis, using an exclusive OR function, to determine the address locations in each buffer that contain different data. If the data is the same, the exclusive OR function will be false. If the data is different, the exclusive OR function for that particular byte location will be true and the compressor program knows that information concerning the state of this buffer location should be transmitted to the remote terminal. The program then assembles, in the terminal command language, a set of commands to write new data to the changed locations detected by the exclusive ORing process. Once this is accomplished, the modified screen image buffer becomes the present screen image buffer and the process is repeated the next time a command to write data to the screen is received from the host application.
The data compression program disclosed in Harper et al. '137 has the advantage of effectively minimizing the amount of data transmitted from the host application to the VTAMs. However, the price paid for this minimization is significant increases in both memory and CPU time overhead at the host in order to implement the compressor. For each session with a terminal having an address buffer of a given size that the host application can service at any given time, a portion of the host's memory that is more than twice the size of the terminal's buffer must be allocated. Additional memory beyond the buffer size containing order and attribute information must also be used. Furthermore, upon each burst of command strings from the host intended for a particular terminal, a number of exclusive OR operations equal to the size of the screen buffer must be made before each transmission of data is made to a remote terminal. For a numerical example, if a large host system is configured to handle 100 remote sessions supporting 3290 type terminals simultaneously, host memory on the order of 6 megabytes must be allocated just to support the data compression buffers. Also, while the Harper compression algorithm effectively minimizes transmitted data, it scans and compares a memory location corresponding to each screen buffer location, irrespective of how small the transmitted string received from the host happens to be. In other words, it is efficient with respect to data transmitted to the remote terminal, but inefficient with respect to the overhead required to service the algorithm locally at the host.
The process shown in the Harper et al. patent is algorithmically relatively simple but requires a great deal of CPU time and a significant amount of memory. To implement a single pass merger and analysis as is used in the present invention, conventional programming techniques require either the setting of a large number of flag variables to indicate present aspects of the relationship between the current state of the buffer indicated by the command string representation and the processing of the new commands.
Therefore, there is a need in the art of supporting data communications between command driven terminals and host computer systems for an improved method of compressing data transmitted to such terminals that, like the method disclosed in the Harper et al. '137 patent, effectively minimizes the length of the string transmitted to the remote terminal, but which also provides an advantage of significantly reducing both memory and computation time overhead at the host that is required to service the compression function.
Whenever a set of command strings is received from the application running on the host, this set of command strings is stored in a buffer and sorted in ascending buffer address order. Subsequently, the method employs the step of sequentially analyzing and merging both the newly received set of command strings and the existing command string representation of the present contents of the buffer.
In the preferred form of the present invention, three command strings are generated as a result of this analysis and merger. These strings are also referred to as the output objects of the preferred embodiment. The first is a write command string (WRT). This string is a sequence of commands, in the terminal command language combined with appropriate data, that would cause all new data to be written to the screen, but does not duplicate any redundant write commands that would simply overwrite screen buffer locations with the same data that they already contain. In other words, in generating the write command sequence, the analysis detects commands in the new set from the application that simply rewrite redundant data in to particular buffer address locations, and eliminates these commands, or the redundant portion of the data for the commands, from the resultant write command string.
The third result of the analysis is to generate an expected state command string (ESC). The expected state command string is a string of commands, likewise in the terminal command language with appropriate data, that would write the new state of the screen buffer entirely, following transmission of an erase command.
Note that the visual presentation presented to the user at the terminal following an erase command is the same for the erase/write command string and the new expected state command string. However, the difference is that the erase/write command string contains only information that is necessary to visibly cause the identical screen to present itself to the user as would result from sending the entire new expected state string. The erase/write command string contains no modified data tag (MDT) settings, no trailing protected blanks and no dark protected data, as these are not necessary for the visual screen presentation. The application expects these constructs to be present in the terminal's screen buffer so the expected state command string contains information representative of all of the transmitted orders and data.
Once this is completed, the length of the write command string and the erase/write command string are compared and the shorter of the two is transmitted with the appropriate command, i.e., write, erase/write, or erase/write/alternate. This is because the transmission of either string will provide the same end result with respect to the visible images on the screen at the remote terminal being serviced. Irrespective of which string is sent, the above described expected state command string representation becomes the new command string representation for the current contents and is maintained in memory at the host for servicing this particular terminal until the next set of command strings is received from the host application.
Since the length of the command string representation for a screen buffer may vary considerably, both during execution of an application and from application to application, the preferred form of the present invention employs dynamic buffer allocation when supporting multiple simultaneous sessions. First, it should be noted that rarely will an application generate a command string representation of the current contents of a buffer that occupies a number of bytes that approximates the buffer size. This can only occur when a very complex screen is presented to the user having a large number of relatively short fields. Indeed, it will be intuitively apparent that a screen for which the length of the command string representation approached the length of the buffer would be one that would present an extremely cluttered appearance to the user. Therefore, good human interface practices in writing applications to run on the host drive host software in a direction that leads to small command string representation sizes as compared to the size of the screen buffer. Additionally, since there is no need to replicate large fixed size blocks of data as buffers, as is the case with the compression algorithm shown in the Harper et al. '137 patent, it is relatively easy and efficient to dynamically allocate available memory space for different sized buffers, depending on the recent history of the size of command string representations, that are used with particular sessions.
One argument is a call to a label for a procedure to be performed while in the state identified by the state label. The second parameter is a call to a particular one of a plurality of tests that are performed on current conditions of program variables, or on the output from the procedure called by the previous argument. Next, N parameters are state labels for other states to which the state machine should branch on the N conditions that results from the test.
Thus, N of the parameters for each execution of the basic procedure are other state labels. Each state label is a valid label in the language being used to implement the machine.
One aspect of the best mode of the state machine implementation aspect of the present invention is that the procedure label is either a macro label or a call to a subroutine in the language that is used to encode the state machine. Therefore, shorter procedures are inline macros that are compiled directly by the compiler or assembler used to generate code to implement the machine. When procedure labels correspond to subroutines, the assembler will insert a call to the subroutine at the point where these procedure labels appear. Therefore, very compact code for implementing the state machine and executing the underlying process can be generated by a judicious choice of inline macros that are directly assembled or compiled into machine language statements when a macro label is encountered in the state machine representation, and longer procedures are identified by a label that references a subroutine call. The ability to directly compile short macros of code leads to a faster operating program that does not employ CPU overhead by placing parameters on a stack that is required when making a subroutine call. When complex procedures are called, subroutines are used as they are more appropriate in such circumstances.
Another way of viewing this aspect of the present invention is that construction of a state machine that implements an Niary tree can be directly implemented from a graphical representation of the tree where the state names for the nodes are the labels, and a single standard procedure calls another procedure and a test that identifies the branches of the tree.
It is an object of the present invention to provide an improved method of compressing data provided to command driven terminals that effectively minimizes the amount of CPU time required to accomplish compression, the amount of data actually transmitted over a physical link to a remotely connected terminal, as well as significantly reducing the size of the memory that the host computer employing the method must allocate to buffers for implementing the compression function.
In particular, the reduction in the amount of transmitted data is comparable to that achieved by prior art methods having the highest compression ratios, but the CPU overhead for accomplishing this compression ratio is dramatically reduced by the single pass analysis and merger employed the present invention.
It is a further object of the present invention to provide an improved method of compression that will sort an incoming set of command strings from a host application and then, in a single pass, compare and merge that set of command strings with a command string representation of the current contents of a terminal's screen buffer.
It is still a further object of the present invention to provide such an improved method that will generate a new expected state command string representation as a result of the one pass analysis and both a write command and an erase/write representation of the differences between the current and new states of the buffer.
It is yet a further object of the present invention to provide an improved method of compressing data transmitted to command driven terminals that will send minimum length bursts of data to remote terminals yet, in practical applications, reduces the amount of buffer memory required at the host to about 30 percent of that required for the buffer duplication and exclusive ORing methods of the prior art.
That the present invention meets these objects, and overcomes the drawbacks of the prior art cited hereinabove, will be appreciated from the detailed description of the present invention hereinbelow.
