Back to Patent's Contents

U. S. Patent 5,598,564 - Jan 28, 1997

SINGLE PASS METHOD OF COMPRESSING DATA TRANSMITTED TO COMMAND DRIVEN TERMINAL

In particular, the inventor of the present invention has defined three new characters for hexadecimal values that are not defined as characters in the 3270 character set, namely, hexadecimal values 01, 02, and 03. These characters, and their use are defined in the following Table 2.

Note that all of this subject deals with areas of the screen that are blank to the user. These may correspond to buffer addresses that contain either spaces or nulls, but both of these appear as blanks to the screen viewer. However, those skilled in the art know that the 3270 terminal responds differently when, for example, inserting data into a field, depending on whether the addresses that generate blank portions of the field on the screen are filled with nulls or spaces. Thus, them are many situations in which proper operation of the application requires the application have knowledge of whether nulls or blanks are actually in certain fields of the buffer.

In Table 2, the column labeled "On Screen After WRT" indicates what characters are actually in the screen buffer that are represented by the pseudo-character in the CSR shown in the table. These characters are on the screen only as results of WRT objects being transmitted to the buffer. When the erase/write string is transmitted to the buffer, all pseudo-characters in the CSR correspond to nulls that are physically loaded into the screen buffer.

This method of maintaining a record of the differences between what actually appears in a terminal screen buffer and what an application thinks it has written to the screen buffer is also used sending appropriate responses back to the application over the path of communication links 30, 37, 36, 32, 31, and 27 as shown in Fig. 2B. Recall that the method of the preferred embodiment strips all modified data tags set by an application and maintains a record of these in the command string representation. When the MDTs have been set by the application for a field that includes pseudo-characters, the preferred embodiment inserts the actual character from the right hand column shown in Table 2 when returning data to the application.

For example, assume that the first application output shown in Table 3 had been sent by the application to a particular field in a screen buffer and further assume that the modified data tag for that field had been set by the application. Upon the receipt of data back from the terminal indicating that one of the terminal interrupt keys had been depressed, the preferred embodiment would note the setting of the modified data tag in the attribute bit for that field, as represented in the command string representation maintained by the program.

28

Noting that, in the example, five missing space characters appear in this field, the program implementing the preferred embodiment inserts five space characters and returns these to the application. Therefore, the modified data tags have never been physically transmitted to the terminal buffer. Likewise, the five spaces originally output by the application (first line, Table 3) were not transmitted outbound, and were not retransmitted inbound over the data link connecting the host and the terminal buffer under consideration.

This portion of the disclosure shows additional details of what the inventor believes to be the best mode of the data compression method invention described herein as well as disclosing an underlying more general invention of a novel method of representing and implementing an algorithmic state machine. The balance of this specification describes this particular implementation for two bodies of code previously described and shown in Fig. 4. From the disclosure of this particular implementation, similar implementations for the remaining blocks of code shown in Fig. 4 may be created by those skilled in the art.

In particular, the novel state machine implementation for what is indicated as the state 0 tests in Fig. 4 are shown as well as the implementation of the state 100 state submachine.

The method of representing and implementing a state machine described herein is as follows. It is preferable, although not necessary, to create a conventional state tree diagram such as those shown in Figures 6 and 7. Then, a state table such as those shown in Tables 4 and 5 is created. Consider for a moment the state diagram of Fig. 6 and its corresponding state table shown in the following Table 4.

The terminology used in the this description and the notation on the drawings will be described in connection with this figure and table. On Fig. 6, the states are represented by the numbered circular nodes. Circular terminating nodes with a left pointing arrowheads thereon represent branches to other states. Thus, they are used for a convenient notation of some state transitions. The path extending from each state node contains the name of a procedure and the name of a test. If one or the other is missing, it simply means that no procedure or test is required when the machine is in that particular state.

The procedure causes a particular thing to be done by the computer implementing the state machine and the test tests for certain conditions that determine the next state to which the machine moves. Therefore, in thinking of the conventional model of an algorithmic state machine, the results of the call of the particular procedure at any state, and the results of the test, may be thought of as the input to the state machine such that the next state is a function of the present state and the inputs, as is true for all algorithmic state machines. Unlike conventional state machines in which there can be a relatively large number of inputs, this state machine may be thought of as selecting only a very small set of inputs by its selection of the procedure and test that is performed at each state.

It should be noted that the use of a state variable implementation of the compressor of the preferred embodiment avoids a complicated system of flags and registers that would need to be used if more conventional programming techniques were employed. This is because there are a relatively large number of variables that describe the current condition of the one pass analysis and merger routine performed by the present invention. Consider that the program must keep track of two pointers, i.e., one for the current command string and one for the command string representation. Under many circumstances, it needs to know the type of order that opened a particular field that contains the data to which the pointer in the string representations is currently pointing. It needs to keep track of which of the output orders (WRT, E/W, and ESC) have commands open, i.e., are currently in the process of building a command. There are other variables that will need to be tracked by flags and registers in a more conventional setting.

30

Using a state implementation, the present state subsumes the information that would otherwise require a complicated set of variables.

As may be seen from inspection of Fig. 6, the state machine implementation employed in the preferred embodiment is a terinary tree as, for example, shown by the three paths that may be taken from state 4 to state 6, state 300, or state 400. While most exit paths from states are binary in this particular implementation, the overall structure of the state machine is tienary and one of the possible outputs is either an impossible condition, or simply duplicates one of the other conditions, such as when the machine moves to a first new state if a particular variable is less than another, and to a second new state if the particular variable is greater than or equal to the other. This structure was chosen by the inventor because the conditional branch instructions for the processor upon which the preferred embodiment was implemented provided a terinary (three state) output indicative of whether one of the tested variables was less than, equal to, or greater than the other. However, the methodology described herein is equally applicable to construction of a binary tree or an N-ary tree where N is an integer greater than one. Furthermore, a terniary state diagram can be implemented with a processor that only has two output states for conditional branching instructions simply by executing two sequential conditional branch instructions.

On Fig. 6, dashed lines are shown to state 10 from the branching node to state 400 from state 4 and to state 200 from state 7. These indicate that after exit of the 400 and 200 submachines, respectively, the state machine returns to state 10, as indicated in Fig. 4. Similarly, a dashed line shows an ultimate branch to state 2 after the branch to the submachine for state 300 is taken from state 4.

The heart of the state machine representation and implementation method of this invention may be appreciated from viewing Fig. 6 in conjunction with Table 4, which is a representation of same. The point is that the state table of Table 4 is also the source code for implementing the machine.

31

Table 4 is the actual source code employed in the implementation of the preferred embodiment for the state 0 submachine illustrated in Fig. 6, which forms a part of the best mode of implementing the method of data compression described hereinabove. The only modifications that have been made are that a space has been inserted between the word "state" and the state number on the labels on the left hand side of the table, and a space has similarly been inserted between the word "test" and the test numbers shown at each state in order to enhance readability of the table.

The machine operates as follows. In the representation and implementation shown in Table 4, each state variable in the left hand column is a valid label in the assembly language used to generate the object code that implements the state machine. Thus, the state numbers in the left hand column represent both the state variables shown on Fig. 6 and are labels to which the assembly language program can branch. At each labeled statement, the identical routine, referred to as "STATETAB" is called. STATETAB is a relatively short procedure that takes five arguments: a procedure identified by a label, a test procedure identified by a label, and three alternative branching labels that are either a state number label or all zeros. Thus, each branch to one of the state number labels always calls the same routine, i.e., STATETAB.

STATETAB first executes the procedure called out as its first argument and then executes the test called. When this is completed, the results of the test control branching to one of the three state labels that form the last three arguments of the STATETAB procedure. For entries in the state table for which there is a set of eight zeros in one of the state label arguments, it should be understood that this is a test condition that cannot occur. Thus, it is convenient to generate an error upon an attempt to branch to one of these. However, it is not expected that this should ever be encountered. Similarly, if a set of zeros appears as an argument in the procedure position or the test position, it indicates that no procedure or test, respectively, is to be executed while in this particular state. This is all that STATETAB does, repetitively call a procedure and test identified in its argument list, and then cause program control to branch to one of the three state labels that appear as the last three arguments in its argument list.

The procedures and test themselves take variable arguments that can be passed depending on the particular state in which the machine currently finds itself. For example, procedure 1 sets a source of commands that are being analyzed to the CCS and procedure 2 sets the source of commands to be analyzed to the CSR. Other procedures and tests test for certain conditions in the source input. The particular state in which the machine exists will determine whether the source is set to the CCS or the CSR. However, many procedures and tests that operate on information from the source or, test for conditions of the source, are generic and are equally applicable to testing for conditions in the current command string or the command string representation.

It should be noted from inspection of Tables 4 and 5 (below) that the procedures and tests are called multiple times at different states. Furthermore, these procedures and tests are used in the other state submachines, namely, the state 200 machine 85, the state 300 machine 87, and the state 400 machine 86 shown in Fig. 4.

The preferred embodiment of the present invention was implemented using system 370 assembler language, i.e., IBM S/370 Assembler Language, and those skilled in the art will recognize Tables 4 and 5 as (with the slight modification of the spaces described hereinabove) valid S/370 assembler statements.

32

In order to follow an example, the reader's attention is respectfully directed to Table 4, Fig. 6, and Fig. 4, all of which represent the state 0 tests performed. From this inspection in light of the following discussion, the general methodology will be appreciated. On Fig. 6, the machine starts in state 0. As shown on Fig. 6 at state 0, it executes procedure 1 (PROC1) and performs test 3. This is defined by the first two arguments of the STATETAB procedure at the STATE 000 label shown in Table 4. The state destination arguments of STATE 0 are states 1 and 2. It should be noted that there is a repetition of the state 1 label as two of the arguments in the STATE 0 entry in Table 4. Therefore, from reading the first line of Table 4, it can be determined that, depending on the results of test 3, the program should move to either STATE 1 or STATE 2.

Turning for a moment to Fig. 6, it will be seen that the path between STATE 0 and STATE 2 is labeled "MORE CSR", indicating that TEST 3 has determined that the command string representation has not yet been exhausted and therefore, the machine should move to state 2. If the command string has been exhausted, the machine moves from STATE 0 to STATE 1. Turning for a moment to Fig. 4, it should be understood that state 0 corresponds to conditional test 66 shown thereon. YES branch 76 is identical to the path over to STATE 2 shown on FIG. 6. Continuing with the example, STATE 1 on Fig. 6 corresponds to step 68 on Fig. 4. NO branch 69 from 54 goes to exit point 70 which is the DONE exit from STATE 1 shown on Fig. 6. Similarly, YES branch 67 on Fig. 4 takes the program to the STATE 100 submachine. This corresponds to the "MORE CCS" that branches to STATE 100 as shown in Fig. 6.

Likewise, STATE 4 corresponds to step 79 that has three possible branches therefrom. From inspection of the logical significance of branches 80 through 82 on Fig. 4 and the corresponding branches shown as exit paths from STATE 4 on Fig. 6, the correspondence will be appreciated.

It would belabor the point to provide a verbal description of each node and the paths therefrom on Fig. 6. They are described in state Table 4 and can be understood from the foregoing examples and the following description of the tests and the procedures in Tables 6 and 7.

There are a couple of aspects of this constraint that can be appreciated, for example, in connection with a code on Fig. 7A or 7B. For an N-iary state table, (N being the number of branch to labels that are arguments of the STATETAB function) if a condition is encountered in which the machine needs to test for more than N possible outcomes, this can be accomplished by exiting from a first state to branches for N-1 of the outcomes with the other branch branching to state for which the other outcomes are possible. This may be repeated iteratively until all of the possibilities are tested.

For example, in the state 100 submachine shown in Fig. 7A and 7B, once it has been determined that an order has been encountered at state 113, the machine needs to identify whether it is one of a set of more than three possible orders. Therefore, the three branches from step 113 lead to state 114 which is taken if the order is either an SBA or an EUA, step 115 for a start field order, and step 118 for another type order. Turning for a moment to Fig. 7B, it can be seen that state 118 leads to three possible branches, i.e., to state 121 if it is an IC order, state 122 if it is an RA order, and a branch back to step 103 if it is another type of order. In this way, the machine advances from state 113 to an appropriate state based on detection of whether it has encountered one of five classes of orders. Therefore, the state machine representation implementation method of the present invention involves defining a state table in which the state labels are valid labels for the assembler or compiler that is used to generate executable code implementing the state machine. A single multi-argument function for processing each state is included that takes arguments of at least tests, and preferably procedures, and defines at least one output label for each state. Code for the procedures and tests is written, each of which is identified by a label that is used as an argument in the state table. The single multi-argument function redirects control to one of the destination state labels each time it is run.

34

It should be noted that the code for the STATETAB is generated only one time when the state table is assembled or compiled, but that the resultant computer instructions are executed millions of times per day during the running of a program embodying the present invention. Therefore, the STATETAB expansion of the present invention notices occurrences of the condition when two of the three possible state destinations are the same and tests the different one only and will go to the other if appropriate. Similarly, it detects the condition when one of the outcomes is the next state and does not execute a GO TO if that outcome is appropriate. In other words, it simply lets the program counter take the machine to the next state when the test indicates that it should go to the next state. Also, STATETAB detects when no test is conducted in a particular state and lets the machine simply fall through to the next state after the procedure when the first state is completed.

In the preferred form of the method procedure and test arguments with a single function are expressed as labels that can identify either macros or subroutines, subprograms or procedures. These are selected in a manner to generate the most compact and efficient code upon compilation or assembly.

35

From the foregoing, it will be appreciated that the process of the current invention meets the objects stated hereinabove and overcomes the drawbacks of the prior art previously described. Since the logic of the process only deals with buffer addresses into which data either has already been written or is being written by a new set of commands, it does not waste CPU time and memory testing and comparing values representative of the contents of empty addresses of the screen buffer at the terminal being serviced. By providing both a new expected state string, which may be used to newly write the buffer contents after an erase command, as well as a write command string that will write only the needed new data, it assures that a minimum length command string is all that is physically transmitted over the remote links to the video terminals being serviced. In view of the method disclosed in this specification, other implementations of the present invention will occur to those skilled in the art and therefore the scope of the present invention is to be limited only by the claims below and equivalents thereof.

Back to Patent's Contents