Content for  TS 23.040  Word version:  18.0.0

LZSS compression uses two tokens to identify either literal strings (byte-sequences) or references to repeated sequences. These tokens (for EMS extended-object compression) are described in this clause of the document. A more general introduction to LZSS compression together with an informative example (based upon the tokens described below) is provided in Annex F (informative). The compressed data stream consists of any combination of literal data blocks and slice descriptor sequences. The format of the compressed data stream is illustrated as follows:

This diagram represents the structure of a compressed byte stream using LZSS. The stream contains a mixture of literal octets from the input buffer and slice descriptors representing the re-occurrence of an octet sequence together with a length and index for the matching octet sequence. The initial octets of a compressed buffer will always be a sequence of literal octets. The structures of the literal data blocks and slice descriptors are given below.

When literal octets are written into the compression buffer (for instance during the initial phases of compression) they are preceded by a literal block identifier. The most significant bit (bit 7) of this block shall be set 1. Bits 6-0 indicate the length of the literal block which follows (up to 127 octets). If no match can be found in an octet sequence of greater that 127 octets then 2 (or more) literal blocks shall be written sequentially.

As can be seen from the above table, the slice descriptor sequence length is two octets, hence only repeating slices of data longer than two octets are extracted. The "slice length" is contained in the descriptor high octet and describes a data slice length of up to 63 octets. The "slice offset index" to the start of the slice is contained in the lower 9 bits and limits the window to 511 octets. The "slice offset index" gives the start position of the source slice measured backwards from the current writing position in the output decoded message data buffer, expressed as a positive number.

The compressed data output stream is constructed by repeating the following process until the end of the input data buffer is reached. The input data buffer is scanned, from the current reading position (minus 1) through to a position 511 bytes back from current reading position (the window) looking for the maximum (but limited to 63 octets) length matching data slice contained that matches the data starting at the current reading position (the look ahead buffer). If no matching data slice, longer than two octets, is found then the input data octet at the current reading position is written to a literal buffer. Both the current reading position in the input data buffer and the current writing position in the output data buffer are incremented by one. If a matching slice is found then a slice descriptor is written to the output data buffer at the current writing position in the output data buffer and the current writing position is incremented by two. The current reading position in the input data buffer is incremented by the length of the newly found matching data slice. If the next read octet results in a matching slice being found then the literal buffer is written out. The literal block header, containing a count of the number of literals in the block, is written out first. (If more than 127 literal octets exist in the literal buffer, then it is split into multiple blocks). The above sequence is repeated until the current reading position reaches the end of the input data buffer. When encoding (compressing), it is the input data buffer, up to the current reading position, that is used to search for already known matching data slices, as this represents, and is equal to, the reconstructed output data buffer of the decoder at the receiving end.

The following sequence is repeated until the end of the input data buffer. The data octet at the current reading position in the input data buffer is tested for either 0 or 1 in bit 7. If the bit is set (bit 7 = 1), then the number of literal octets that follow is determined from the lower 7 bits of the header octet (this one). The literal octet block is written to the output data buffer at the current writing position and both the output data writing position and the input data reading position pointers are incremented by the block size. If the bit is clear (bit 7 = 0), then the "slice length" and "slice offset index" are extracted from the two octet slice descriptor. The data slice is copied from within the output data buffer to the end of the output data buffer, where the start of the source slice is at a position "slice offset index" back from the current output data writing position and the destination start position of the slice is the current output buffer writing position. The input data buffer reading position is incremented by two and the output data writing position is incremented by the "slice length".

In order to assist implementers of the compression algorithm described in this specification, a suite of test vectors and 'help' information are available in electronic format. The test vectors are supplied with this specification. These test vectors provide checks for most of the commonly expected parameter value variants in this specification and may be updated as the need arises. In addition Annex F contains an introduction to LZ-type compression algorithms and also has a brief informative example.