info lzip

5.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, multi-bit sequences are coded in normal order, from MSB to 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. LZMA divides the interval between any two powers of 2 into 2 halves, named slots. As possible distances range from 0 to (2^32 - 1), there are 64 slots (0 to 63). The slot number is context-coded in 6 bits. ‘direct_bits’ are the remaining bits (from 0 to 30) needed to form a complete distance, and are calculated as (slot >> 1) - 1. If a distance needs 6 or more direct_bits, the last 4 bits are coded separately. The last piece (direct_bits for distances 4 to 127 or the last 4 bits for distances >= 128) is context-coded in reverse order (from LSB to MSB). For distances >= 128, the ‘direct_bits - 4’ part is coded 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

This document was generated on October 10, 2013 using texi2html 5.0.