Variable length data packet with adjustable length indicator

The invention relates to a method of encoding and decoding a data stream in which data type information combines with data packet length and identifier information to reduce the required length of the data stream while providing the added functionality of allowing for type checking at the receiving computer.

FIELD OF THE INVENTION
 The present invention relates to a method, especially operable on pervasive
 devices eg. communications enabled Personal Digital Assistant, mobile
 phone, remote field sensors/monitor or other mobile devices, for encoding
 data for minimal length byte streams for transmission over slow/costly
 networks.
 BACKGROUND OF THE INVENTION
 In traditional client/server computing environments, data items along with
 their identifiers are transmitted within data streams between computers in
 respective data packets in one of two ways:
 data items are given a fixed length within a data packet according to the
 maximum required length of a data item. A receiving computer can search
 for specific data items by searching for their identifiers in the data
 stream by jumping the known length of a data packet to the identifier in
 the next data packet; or
 data items are allocated a length sufficient to store the data, and this
 length variable is stored in another location with a data packet. The
 receiving computer needs to read the length variable to determine how far
 to jump to the next identifier location in the data stream.
 Clearly, the first method while computationally more simple will require
 excess bandwidth to transfer redundant information. The second method
 while computationally more complex requires less bandwidth. Even with the
 second method, the length variable must be allocated a length sufficiently
 long enough to define the length of the longest data item. This is turn
 can be wasteful if data types can vary between long strings or simple
 integers. Neither method takes into account that identifier lengths can
 also vary and using a fixed field length for the identifier again requires
 excess bandwidth.
 The present invention defines a simple compact "free format" layout for
 data items sent over a network, keeping the number of bytes used to a
 minimum, independent of compression techniques.
 DISCLOSURE OF THE INVENTION
 Accordingly, the present invention provides a method as claimed in claim 1.
 It will be seen that the method according to the invention produces a data
 stream in which data type information combines with data packet length and
 identifier information to reduce the required length of the data stream
 while providing the added functionality of allowing for type checking at
 the receiving computer.

DESCRIPTION OF THE PREFERRED EMBODIMENTS.
 In the preferred embodiment, a Data item along with its identifier is
 encoded and transmitted in a data packet within a data stream. The data
 packet is encoded according to the layout of FIG. 2. Where:
 Length defines a variable number of bytes within the data packet following
 the length field. The length field varies typically between 1 and 4 bytes
 in length. The length field is encoded in the following manner:
 The first byte has its first (most significant) two bits reserved and they
 are used as the length of the length field i.e.
 00=1 byte used for length (6 bits=0-63)
 01=2 bytes used for length (14 bits=64-16,383)
 10=3 bytes used for length (22 bits=16,384-4,194,303)
 11=4 bytes used for length (30 bits=4,194,304-1,073,741,823)
 The remainder of the first byte in combination with the contents of up to
 the next three bytes give the remaining length of the data packet--i.e.
 the combined length of the identifier, fence and data item.
 It should be noted that 3 or more reserved bits could be used, but this is
 generally unnecessary as even an (8 byte-3 bit) Length field would
 represent an extremely long Data item, i.e. 61 bits for a length.
 Identifier is a variable length string of bytes (in the preferred
 embodiment, each byte value must be less than 0.times.E0). Typically an
 Identifier would be an ASCII string for which a restriction to byte values
 less than 0.times.E0 would not cause a problem. The end of the identifier
 field is detected by a receiving computer when a byte with a value greater
 than or equal to 0.times.E0 is encountered as this is the beginning of the
 Fence field.
 Fence is a special byte delimiting the boundary between the identifier and
 the optional Data item. This byte is used to contain the data type of the
 Data item. An example of a partial coding scheme for Fence is shown in
 Table 1. The remaining codes above E9 and F9 could be used for types such
 as reals.
 Thus, it can be seen that the single Fence byte
 performs 3 distinct functions:
 Delimiting the Identifier
 Defining the data type; and
 In some cases, defining that the data is:
 null rather than no data in a Data item;
 a positive or negative integer, with no Data bytes sent, for integer values
 0 cr --1; and
 boolean true or false with no Data bytes sent.
 An example byte stream encoded according to the method of the invention is
 shown in FIG. 3. In the first field 10, the first two bits of the first
 byte are b00 indicating a length field one byte long. The remaining bits
 add up to 8 indicating that 8 bytes are to follow the length field. The
 next two bytes 0.times.53 and 0.times.49 correspond to an identifier field
 having an ASCII value of "51". This is followed by a fence field
 indicating an 8 byte integer data type with leading 00's suppressed is to
 follow. In this data packet, it can be seen that the first three bytes of
 the integer Data item are suppressed.
 The second and third data packets 12 and 14 respectively include a 1 byte
 length field indicating a remaining field length of 3 bytes. Because the
 identifier field in both cases is two bytes long, a receiver would expect
 that the data item will not contain any data. In the packets 12 and 14
 respectively this is confirmed because the fence bytes indicates a byte
 type with null value and a 4 byte integer type of value -1 follows. So it
 can be seen that in both cases the fence field enables typed data to be
 transmitted in one byte.
 The ability to specify null data items rather than data items with no
 content provides an important distinction particularly when a string is
 transmitted. Because if the fence byte were 0.times.E1 rather than
 0.times.F1, it would indicate a string with no contents rather than a null
 string. As seen above, it also allows integer bytes of value -1 to be
 transmitted only by indicating their data type.
 In the fourth packet 16 a two byte field length is required as indicated by
 the first two bits of the byte 0.times.46. The following 0.times.02 byte
 then forms the most significant portion of the length value with the
 reserved bits being removed from the least significant portion to indicate
 b0000 0010 00 0110 bytes follow. The fence byte indicates a string data
 type follows. A receiving computer knows that the length of the Data item
 is the length value for the packet less the two bytes of the identifier
 field plus the fence byte.
 Using this data structure, savings in the byte stream are achieved by:
 using a variable length field (1 to 4 bytes) where only the required length
 bytes are sent;
 using a variable length Identifier field where only the required bytes are
 sent; and
 suppressing leading 0.times.00s and 0.times.FF's of integer values in the
 output stream again sending only the required bytes;
 with these three variable lengths being indicated within only one length
 field.
 It should also be seen that because all the Data items are typed, not only
 can they be type checked at the receiving end, Null Data items can be
 transmitted simply by indicating their data type. this enables the
 presence of the even null data items to be checked at the receiving end.
 Furthermore in the preferred embodiment, actual boolean values are
 transmitted simply by indicating their data type as either 0.times.E4 or
 0.times.F4.
 It will be seen that the order of the data packets within the data stream
 is not significant as the stream can be searched to find a matching
 Identifier. Such a search is fast as the Length field can be used to skip
 to the next packet to try to match the Identifier.
 Further savings can be achieved by compressing the data. Compressors can
 usually be helped by performing an XOR of one packet with a previous
 packet in the byte stream producing repeated bytes of 0.times.00. Because
 of the variable length of the packets produced according to the invention,
 however, and because the order of the packets may change, a simple XOR
 would not produce many zeros in the byte stream. An intelligent XOR,
 however, that worked on a packet by packet basis could produce repeated
 0.times.00 bytes thus assisting the compressor.
 TABLE #1
 Code Comments
 0xE0 Data is un-typed
 0xF0 null (no Data item) - un-typed
 0xE1 Data is ASCII
 0xF1 null (no Data item) - ASCII type
 0xE2 Data is Unicode
 0xF2 null (no Data item) - Unicode type
 0xE3 byte(s)
 0xF3 null (no Data item) - byte type
 0xE4 boolean (false) - (no Data item)
 0xF4 boolean (true) - (no Data item)
 0xE5 short (2 byte integer) 0x00 byte(s) suppressed
 0xF5 negative value short (2 byte integer) 0xFF byte(s)
 0xE6 int (4 byte integer) 0x00 byte(s) suppressed
 0xF6 negative value int (4 byte integer) 0xFF byte(s)
 0xE7 long (8 byte integer) 0x00 byte(s) suppressed
 0xF7 negative value long (8 byte integer) 0xFF byte(s)
 0xE8 Data is an object
 0xF8 null (no Data item) - object type