File: lzip.info,  Node: Stream format,  Next: Trailing data,  Prev: File format,  Up: Top

7 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.