File: lzip.info, Node: Stream format, Next:Trailing data, Prev:File format, Up:Top7 Format of the LZMA stream in lzip files ***************************************** The LZMA algorithm has three parameters, called "special LZMA properties", to adjust it for some kinds of binary data. These parameters are: 'literal_context_bits' (with a default value of 3), 'literal_pos_state_bits' (with a default value of 0), and 'pos_state_bits' (with a default value of 2). As a general purpose compressor, lzip only uses the default values for these parameters. In particular 'literal_pos_state_bits' has been optimized away and does not even appear in the code. Lzip finishes the LZMA stream with an "End Of Stream" (EOS) marker (the distance-length pair 0xFFFFFFFFU, 2), which in conjunction with the 'member size' field in the member trailer allows the checking of stream integrity. The EOS marker is the only LZMA marker allowed in lzip files. The LZMA stream in lzip files always has these two features (default properties and EOS marker) and is referred to in this document as LZMA-302eos. This simplified and marker-terminated form of the LZMA stream format has been chosen to maximize interoperability and safety. The second stage of LZMA is a range encoder that uses a different probability model for each type of symbol: distances, lengths, literal bytes, etc. Range encoding conceptually encodes all the symbols of the message into one number. Unlike Huffman coding, which assigns to each symbol a bit-pattern and concatenates all the bit-patterns together, range encoding can compress one symbol to less than one bit. Therefore the compressed data produced by a range encoder can't be split in pieces that could be described individually. It seems that the only way of describing the LZMA-302eos stream is to describe the algorithm that decodes it. And given the many details about the range decoder that need to be described accurately, the source code of a real decompressor seems the only appropriate reference to use. What follows is a description of the decoding algorithm for LZMA-302eos streams using as reference the source code of "lzd", an educational decompressor for lzip files, included in appendix A. *Note Reference source code::. Lzd is written in C++11 and can be downloaded from the lzip download directory. 7.1 What is coded ================= The LZMA stream includes literals, matches, and repeated matches (matches reusing a recently used distance). There are 7 different coding sequences: Bit sequence Name Description ----------------------------------------------------------------------------- 0 + byte literal literal byte 1 + 0 + len + dis match distance-length pair 1 + 1 + 0 + 0 shortrep 1 byte match at latest used distance 1 + 1 + 0 + 1 + len rep0 len bytes match at latest used distance 1 + 1 + 1 + 0 + len rep1 len bytes match at second latest used distance 1 + 1 + 1 + 1 + 0 + len rep2 len bytes match at third latest used distance 1 + 1 + 1 + 1 + 1 + len rep3 len bytes match at fourth latest used distance In the following tables, multibit sequences are coded in normal order, from most significant bit (MSB) to least significant bit (LSB), except where noted otherwise. Lengths (the 'len' in the table above) are coded as follows: Bit sequence Description ---------------------------------------------------------------------------- 0 + 3 bits lengths from 2 to 9 1 + 0 + 3 bits lengths from 10 to 17 1 + 1 + 8 bits lengths from 18 to 273 The coding of distances is a little more complicated, so I'll begin by explaining a simpler version of the encoding. Imagine you need to encode a number from 0 to 2^32 - 1, and you want to do it in a way that produces shorter codes for the smaller numbers. You may first encode the position of the most significant bit that is set to 1, which you may find by making a bit scan from the left (from the MSB). A position of 0 means that the number is 0 (no bit is set), 1 means the LSB is the first bit set (the number is 1), and 32 means the MSB is set (i.e., the number is >= 0x80000000). Then, if the position is >= 2, you encode the remaining position - 1 bits. Let's call these bits "direct bits" because they are coded directly by value instead of indirectly by position. The inconvenient of this simple method is that it needs 6 bits to encode the position, but it just uses 33 of the 64 possible values, wasting almost half of the codes. The intelligent trick of LZMA is that it encodes in what it calls a "slot" the position of the most significant bit set, along with the value of the next bit, using the same 6 bits that would take to encode the position alone. This seems to need 66 slots (twice the number of positions), but for positions 0 and 1 there is no next bit, so the number of slots needed is 64 (0 to 63). The 6 bits representing this "slot number" are then context-coded. If the distance is >= 4, the remaining bits are encoded as follows. 'direct_bits' is the amount of remaining bits (from 1 to 30) needed to form a complete distance, and is calculated as (slot >> 1) - 1. If a distance needs 6 or more direct_bits, the last 4 bits are encoded separately. The last piece (all the direct_bits for distances 4 to 127 (slots 4 to 13), or the last 4 bits for distances >= 128 (slot >= 14)) is context-coded in reverse order (from LSB to MSB). For distances >= 128, the 'direct_bits - 4' part is encoded with fixed 0.5 probability. Bit sequence Description ---------------------------------------------------------------------------- slot distances from 0 to 3 slot + direct_bits distances from 4 to 127 slot + (direct_bits - 4) + 4 bits distances from 128 to 2^32 - 1 7.2 The coding contexts ======================= These contexts ('Bit_model' in the source), are integers or arrays of integers representing the probability of the corresponding bit being 0. The indices used in these arrays are: 'state' A state machine ('State' in the source) with 12 states (0 to 11), coding the latest 2 to 4 types of sequences processed. The initial state is 0. 'pos_state' Value of the 2 least significant bits of the current position in the decoded data. 'literal_state' Value of the 3 most significant bits of the latest byte decoded. 'len_state' Coded value of the current match length (length - 2), with a maximum of 3. The resulting value is in the range 0 to 3. The types of previous sequences corresponding to each state are shown in the following table. '!literal' is any sequence except a literal byte. 'rep' is any one of 'rep0', 'rep1', 'rep2', or 'rep3'. The last type in each line is the most recent. State Types of previous sequences ------------------------------------------------------ 0 literal, literal, literal 1 match, literal, literal 2 rep or (!literal, shortrep), literal, literal 3 literal, shortrep, literal, literal 4 match, literal 5 rep or (!literal, shortrep), literal 6 literal, shortrep, literal 7 literal, match 8 literal, rep 9 literal, shortrep 10 !literal, match 11 !literal, (rep or shortrep) The contexts for decoding the type of coding sequence are: Name Indices Used when ---------------------------------------------------------------------------- bm_match state, pos_state sequence start bm_rep state after sequence 1 bm_rep0 state after sequence 11 bm_rep1 state after sequence 111 bm_rep2 state after sequence 1111 bm_len state, pos_state after sequence 110 The contexts for decoding distances are: Name Indices Used when ---------------------------------------------------------------------------- bm_dis_slot len_state, bit tree distance start bm_dis reverse bit tree after slots 4 to 13 bm_align reverse bit tree for distances >= 128, after fixed probability bits There are two separate sets of contexts for lengths ('Len_model' in the source). One for normal matches, the other for repeated matches. The contexts in each Len_model are (see 'decode_len' in the source): Name Indices Used when --------------------------------------------------------------------------- choice1 none length start choice2 none after sequence 1 bm_low pos_state, bit tree after sequence 0 bm_mid pos_state, bit tree after sequence 10 bm_high bit tree after sequence 11 The context array 'bm_literal' is special. In principle it acts as a normal bit tree context, the one selected by 'literal_state'. But if the previous decoded byte was not a literal, two other bit tree contexts are used depending on the value of each bit in 'match_byte' (the byte at the latest used distance), until a bit is decoded that is different from its corresponding bit in 'match_byte'. After the first difference is found, the rest of the byte is decoded using the normal bit tree context. (See 'decode_matched' in the source). 7.3 The range decoder ===================== The LZMA stream is consumed one byte at a time by the range decoder. (See 'normalize' in the source). Every byte consumed produces a variable number of decoded bits, depending on how well these bits agree with their context. (See 'decode_bit' in the source). The range decoder state consists of two unsigned 32-bit variables: 'range' (representing the most significant part of the range size not yet decoded) and 'code' (representing the current point within 'range'). 'range' is initialized to 2^32 - 1, and 'code' is initialized to 0. The range encoder produces a first 0 byte that must be ignored by the range decoder. (See the 'Range_decoder' constructor in the source). 7.4 Decoding and checking the LZMA stream ========================================= After decoding the member header and obtaining the dictionary size, the range decoder is initialized and then the LZMA decoder enters a loop (see 'decode_member' in the source) where it invokes the range decoder with the appropriate contexts to decode the different coding sequences (matches, repeated matches, and literal bytes), until the "End Of Stream" marker is decoded. Once the "End Of Stream" marker has been decoded, the decompressor reads and decodes the member trailer, and checks that the three integrity factors stored there (CRC, data size, and member size) match those computed from the data.