Moving set packet processor suitable for resource-constrained devices6751675Abstract A method for data communication includes receiving a data packet that includes at least one contiguous data item, defining a window that initially includes the beginning of the data items, determining whether the window includes a part of a split data item and processing the contiguous data items when there are no split data items. The method also includes processing all data items occurring before a split data item when a split data item is found, storing the first part of a split data item, moving the window to include both parts of the split data item, appending the stored first part to the second part to create an appended packet and processing the appended packet. An apparatus for data communication includes at least one memory having program instructions and at least one processor configured to use the program instructions to receive a data packet that includes at least one contiguous data item, define a window that initially includes the beginning of the data items, determine whether the window includes a part of a split data item and process the contiguous data items when there are no split data items. The processor is also configured to process all data items occurring before a split data item when a split data item is found, store the first part of a split data item, move the window to include both parts of the split data item, append the stored first part to the second part and process the result. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
TABLE 1
##STR1##
If the data shown in Table 2 were encapsulated in an APDU 135 represented by Table 1 while preserving the relative order of the data, there would be insufficient room for the second sixteen-bit integer, resulting in a "data split" problem. This data split problem is typically handled by processing the data on the terminal side to guarantee the data will not be split. This processing on the terminal side may include by way of example, changing the size of the APDU 135 to prevent a data split, or reordering the data within APDUs before sending them to a Java Card.TM. technology enabled device 120. Each of these solutions has disadvantages. Changing the size of the APDU 135 and reordering the data within the APDU 135 requires complex negotiation between the terminal and the card. The terminal must transform the data and provide the card with enough information to reconstruct the data. The card must receive the information from the terminal, reconstruct the data and provide a response to the terminal. Making the terminal and card applications data-dependent as such increases processing overhead. This data dependency also increases memory overhead, both in terms of program size and the amount of RAM required to store buffered data. Putting intelligence on the terminal side also raises security concerns. Knowing whether a data split problem exists requires that the terminal know the size of each data item being sent. This size information is related to the data type. This information is not available if the data is encrypted. Thus, the terminal must decrypt encrypted data before it interprets the data to determine the size of each data unit. Once the data is decrypted, the terminal has access to private information. In some applications, only the card is meant to interpret the data, not the terminal. Accordingly, a need exists in the prior art for a method and apparatus for data communications between a terminal device and a smart card that requires relatively little processing and memory overhead on terminal and smart card applications. A further need exists for such a method and apparatus that is relatively secure. SUMMARY OF THE INVENTION A method for data communication includes receiving a data packet that includes at least one contiguous data item, defining a window that initially includes the beginning of the data items, determining whether the window includes a part of a split data item and processing the contiguous data items when there are no split data items. The method also includes processing all data items occurring before a split data item when a split data item is found, storing the first part of a split data item, moving the window to include both parts of the split data item, appending the stored first part to the second part to create an appended packet and processing the appended packet. An apparatus for data communication includes at least one memory having program instructions and at least one processor configured to use the program instructions to receive a data packet that includes at least one contiguous data item, define a window that initially includes the beginning of the data items, determine whether the window includes a part of a split data item and process the contiguous data items when there are no split data items. The processor is also configured to process all data items occurring before a split data item when a split data item is found, store the first part of a split data item, move the window to include both parts of the split data item, append the stored first part to the second part and process the result. BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram that illustrates typical apparatus for installing applications on a Java Card.TM. technology enabled device. FIG. 2 is a flow diagram that illustrates a method for data communications in accordance with one embodiment of the present invention. FIG. 3 is a flow diagram that illustrates a method for appending split data values in accordance with one embodiment of the present invention. FIG. 4 is a flow diagram that illustrates a method for moving a window in accordance with one embodiment of the present invention. FIG. 5 is a block diagram that illustrates applying the invention to a 32-byte data packet and a four-byte window. DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS Those of ordinary skill in the art will realize that the following description of the present invention is illustrative only. Other embodiments of the invention will readily suggest themselves to such skilled persons having the benefit of this disclosure. This invention relates to computer systems. More particularly, the present invention relates to moving set data communications. The invention further relates to machine readable media on which are stored (1) the layout parameters of the present invention and/or (2) program instructions for using the present invention in performing operations on a computer. Such media includes by way of example magnetic tape, magnetic disks, optically readable media such as CD ROMs and semiconductor memory such as PCMCIA cards. The medium may also take the form of a portable item such as a small disk, diskette or cassette. The medium may also take the form of a larger or immobile item such as a hard disk drive or a computer RAM. Resource-constrained devices are generally considered to be those that are relatively restricted in memory and/or computing power or speed, as compared to typical desktop computers and the like. Although the particular implementation discussed below is described in reference to a smart card, the invention can be used with other resource-constrained devices including, but not limited to, cellular telephones, boundary scan devices, field programmable devices, personal digital assistants (PDAs) and pagers, as well as other miniature or small footprint devices. The invention can also be used on non-resource-constrained devices. For the purpose of this disclosure, the term "processor" may be used to refer to a physical computer or a virtual machine. Also, data processing refers to that processing required to install an application on a resource-constrained device such as a Java Card.TM. technology enabled device 120. According to the present invention, physically segmented data is treated conceptually as a contiguous data stream. Data is processed within a conceptual sliding window, also called a moving set. If there are no data splits, data processing occurs as usual. If a data split is detected, the window is moved towards the source of the conceptual data stream to see the rest of the data, including the other part of the split data. This process continues until all the data is consumed. Turning now to FIG. 2, a flow diagram that illustrates moving data set communications in accordance with one embodiment of the present invention is presented. At reference numeral 150, a data packet is received. At reference numeral 155, the start of the window is set to the start of the data packet. At reference numeral 160, a determination is made regarding whether a data value is split. If a data value has not been split, the data is processed as usual at reference numeral 165. At reference numeral 170, the window is moved a number of bytes equivalent to the window size. If a data value has been split, the data up to the split data value is processed as usual at reference numeral 165. At reference numeral 170, the portion of the split data value that is present is saved. At reference numeral 175, the window is moved to include the rest of the split data. At reference numeral 180, the saved portion of the split data is appended to the rest of the split data from the newly positioned window. At reference numeral 165, the appended data is processed as usual. Turning now to FIG. 3, a flow diagram that illustrates appending data in accordance with one embodiment of the present invention is presented. At reference numeral 200, the stored data is retrieved. At reference numeral 205, the stored data is concatenated with the new data obtained when the window was moved to include the rest of the split data at reference numeral 175 of FIG. 2. At reference numeral 210, the concatenated data is processed. At reference numeral 215, the window is moved past the concatenated data. Turning now to FIG. 4, a flow diagram that illustrates moving a window in accordance with one embodiment of the present invention is presented. At reference numeral 230, a determination is made regarding whether the window is large enough to accommodate the move without discarding unprocessed data. If the window is not large enough, the window size is increased at reference numeral 235. If the window is large enough, a determination is made regarding whether the end of the input stream has been reached at reference numeral 240. If the end of the input stream has been reached, at least one data packet is read at reference numeral 245. If the end of the input stream has not been reached, the window is positioned at reference numeral 250. To aid in an understanding of the present invention, the invention will be applied to a specific example illustrated in FIG. 5. FIG. 5 illustrates the invention using a 32-byte data packet buffer 270 and a four-byte window 275. All except two data items in the data packet are two-byte integers. A byte is represented by reference numeral 280 and the first two bytes of a four-byte integer are represented by reference numeral 285. At reference numeral 150 of FIG. 2, the first data packet is received. At reference numeral 155, the window 275 is set to the start of the data packet 270. At reference numeral 160, a determination is made regarding whether a data value in the window 275 is split. Since the end if the window 275 coincides with the end of a two-byte integer 290, there is no data split. At reference numeral 165, data values 290 and 295 are processed as usual. At reference numeral 170, the window 275 is moved. At reference numeral 230 of FIG. 4, the window is determined to be large enough to move four bytes because the window can hold that number of bytes. At reference numeral 240, a check is made to determine whether the end of the input stream has been reached. Since only four bytes of the 32-byte data packet have been processed thus far, the end of the data stream has not been reached. At reference numeral 250, the window is moved four bytes towards the source of the input stream. The repositioned window is indicated by reference numeral 300. Window 300 includes one byte 305, one two-byte integer 310 and one byte of another two-byte integer 315. At reference numeral 160 of FIG. 2, a determination is made regarding whether a data value has been split. Since the window includes only one byte of a two-byte integer 315, a data value has been split. At reference numeral 165, the data values occurring before the split are processed. Thus, byte 305 and two-byte integer 310 are processed. At reference numeral 170, the one byte of two-byte integer 315 is saved. At reference numeral 175, the window is moved to include the rest of the split data. The repositioned window is represented by reference numeral 330. Window 330 contains both bytes of the split two-byte integer 315. Windows 335 through 355 each contain two two-byte integers and are processed in the same manner as window 275. Window 360 includes only one half of a four-byte integer 365. The two bytes 365 are stored at reference numeral 170 of FIG. 2. At reference numeral 175, the window is moved to include the rest of the data. Since the end of the input stream has been reached, another data packet is read at reference numeral 245 of FIG. 4. Since the window size is less than the size of the 32-byte data packet data in this example, only one data packet is read. At reference numeral 200 of FIG. 3, the stored data is retrieved. At reference numeral 205, the stored data is concatenated with the other data in the window 360 that was just read from a new data packet. At reference numeral 210, the concatenated data is processed. At reference numeral 215, the window is moved past the concatenated data. One of ordinary skill in the art will also recognize that number of data splits encountered by using the present invention varies inversely with the window size. The effect of reducing data splits by increasing the window size must be weighed against the increased memory requirements of a larger window. According to one embodiment of the present invention, the number of bytes allocated to store split data values is selected based upon the computer architecture of the card device. A typical 16-bit processor has a two-byte integer base type. Most 16-bit processor instructions expect 16-bit operands. Thus, most data values encountered in a data packet will be two bytes or less. If a two-byte data value is split, one byte will be within the window, and the other one byte will be outside the window. Accordingly, a one-byte buffer will be enough for most situations. Likewise, a typical 32-bit processor has a four-byte integer base type. If a four-byte integer is split, the amount of data in the window could be from one to three of the four bytes. Thus, a three-byte buffer will suffice for most situations. More generally then, for an n-base processor, where n is the number of bits, the number of bytes allocated for a storage buffer is (n/8)-1. According to another embodiment of the present invention, the header portion of a data packet is used to store split data values. For example, an APDU contains a five-byte header. An APDU contains either a command or a response. The format for a typical command APDU is shown in Table 3.
TABLE 3
##STR3##
In Table 3, CLA is the Instruction class, INS is the instruction, P1 and P2 are the instruction parameters, L.sub.c is the byte length of the data field of the instruction, Data is the to data field of the instruction and L.sub.c is the maximum number of bytes expected in the data field of the response. Each item in the header is one byte in size. Accordingly, the maximum data field size is 256 bytes. APDUs are described in detail in ISO Standard 7816-4:1995, Section 5.3. Typically, the five APDU header bytes CLA, INS, P1, P2 and L.sub.c are examined upon receipt of the APDU to determine how to interpret the data portion of the APDU. Once the information has been extracted from the header bytes, the memory locations of the header bytes are not used during subsequent processing of the APDU data portion. According to this embodiment of the present invention, the APDU header bytes are reused as a storage location for split data values, thus avoiding the allocation of additional memory. The illustration of the present invention using a specific window size and a specific data packet size is not intended to be limiting in any way. Those of ordinary skill in the art will recognize that the invention is applicable to various data packet formats and window sizes. Also, although the present invention has been illustrated with respect to Java Card.TM. technology, those of ordinary skill in the art will recognize that the invention is applicable to many other platforms. These platforms include by way of example, K virtual machine (KVM) technology. KVM technology is described in "The K Virtual Machine (KVM)--A White Paper", Jun. 8, 1999, Sun Microsystems, Inc. The present invention may be implemented in software or firmware, as well as in programmable gate array devices, Application Specific Integrated Circuits (ASICs), and other hardware. Thus, a novel method for moving set data communication has been described. While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art having the benefit of this disclosure that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.
|
Same subclass Same class Consider this |
||||||||||