.LZMA File Format – LZMA coding

Range decoder

• Start: Range = FFFFFFFF; read 5 bytes into Code. The first byte must be 0, and Code equal to Range marks the stream as corrupted; in an undamaged stream Code is always less than Range.
• Normalise: whenever Range falls below 2²⁴, shift Range and Code left 8 bits and read the next byte into Code.
• Probability bits: each probability is an 11-bit number (out of 2,048) that the next bit is 0, starting at 1,024. bound = (Range >> 11) × prob. If Code < bound the bit is 0: Range = bound, prob += (2048 − prob) >> 5. Otherwise it is 1: Range −= bound, Code −= bound, prob −= prob >> 5.
• Direct bits, with probability one half: Range >>= 1; the bit is 1 if Code ≥ Range, which is then subtracted.
• A bit tree of n bits decodes a number from the top bit down, using 2ⁿ probabilities indexed by the bits read so far; a reverse bit tree reads the low bit first.

Packets

The decoder keeps the position pos, the state (0 to 11), the previous byte and four repeat distances rep0 to rep3. posState = pos & ((1 << pb) − 1). Each packet starts with decision bits:

The bits come from these probability arrays: IsMatch[state][posState], IsRep[state], IsRepG0[state], IsRep0Long[state][posState], IsRepG1[state] and IsRepG2[state]. A repeat moves the distance it used to rep0 and shifts the others down; a MATCH pushes its new distance in as rep0 and drops rep3.

States

The state remembers the kinds of the last few packets. States 0 to 6 follow a literal; 7 to 11 follow a match or repeat.

Literals

There are 0x300 << (lc + lp) literal probabilities, 0x300 for each context. The context is ((pos & ((1 << lp) − 1)) << lc) + (prevByte >> (8 − lc)). In states below 7 the byte is an 8-bit tree. From state 7 up (just after a match) it is a “matched literal”: the byte at distance rep0 is used as a guide, and while its bits agree with the bits decoded, a separate set of probabilities chosen by the guide bit is used. (The specification’s prose says “state > 7”, but its decoder code tests state >= 7.)

Lengths

MATCH and LONGREP use two length decoders of the same shape, one each. Lengths run from 2 to 273:

Distances

1. lenState = min(len − 2, 3). Decode a 6-bit tree from PosSlot[lenState]: the distance slot, 0 to 63.
2. Slots 0 to 3 are the distance itself.
3. Otherwise numDirectBits = (slot >> 1) − 1 and the distance starts as (2 | (slot & 1)) << numDirectBits.
4. Slots 4 to 13: the low numDirectBits bits are a reverse bit tree in the SpecPos probabilities.
5. Slots 14 to 63: numDirectBits − 4 direct bits, then the low 4 bits as a reverse 4-bit tree in the Align probabilities.

The decoded value is the distance minus 1. A value of FFFFFFFF is the end marker. Otherwise it must be smaller than the data decoded so far and the dictionary size.

Constants