The file is good-known_size-without_eopm.lzma from the xz project’s test
files (0BSD licence): 31 bytes that decompress to Hello, a new line,
World! and a new line. Drop it, or any .lzma file, on the
explorer and press Show beside its LZMA data to see the same table for your own file.
The numbers below were printed by this site’s decoder and the data was checked against
xz -d.
The bytes
5D properties: lc 3, lp 0, pb 2
00 10 00 00 dictionary size 0x1000 = 4,096 bytes
0D 00 00 00 00 00 00 00 uncompressed size 13
00 range coder: the first byte is always 0
24 19 49 98 the first Code: 0x24194998
6F 05 15 27 27 0D 76 78 the rest of the range-coded data (18 bytes in all
D0 29 1D 20 00 after the header, with the five above)There is no end marker, because the size is known: the decoder stops after 13 bytes
and, as the specification asks, finds Code equal to 0.
The first bit by hand
The decoder starts with Range = 0xFFFFFFFF and Code = 0x24194998. The first
decision is IsMatch[state 0][posState 0], a probability of 1,024 out of 2,048.
bound = (0xFFFFFFFF >> 11) × 1024 = 0x1FFFFF × 0x400 = 0x7FFFFC00.
Code is below it, so the bit is 0 (a literal), Range becomes
0x7FFFFC00 and the probability rises to 1,056. Eight more bits, each from the
literal tree chosen by the context (the previous byte is 0 and the position is 0), give
0x48, “H”.
The symbols
Range and Code are the registers before the symbol; the input offsets are in the file.
| # | Output at | Symbol | State | Range | Code | Input bytes |
|---|---|---|---|---|---|---|
| 0 | 0 | literal H | 0 → 0 | FFFFFFFF | 24194998 | 0x12 to 0x13 |
| 1 | 1 | literal e | 0 → 0 | 80000000 | 194D986F | 0x13 to 0x14 |
| 2 | 2 | literal l | 0 → 0 | 40000000 | 0D986F05 | 0x14 to 0x15 |
| 3 | 3 | short rep: one byte from 1 back (l) | 0 → 9 | 20000000 | 186F0515 | none new |
| 4 | 4 | literal after a match o, coded against the byte at rep0 | 9 → 6 | 02000000 | 006F0515 | 0x15 to 0x16 |
| 5 | 5 | literal line feed | 6 → 3 | 01000000 | 00051527 | 0x16 to 0x18 |
| 6 | 6 | literal W | 3 → 0 | 7FE00000 | 1667270D | 0x18 to 0x19 |
| 7 to 12 | 7 to 12 | literals o r l d ! and a line feed | 0 → 0 | see the explorer | 0x19 to 0x1F | |
Three things to see. A literal after a literal leaves the state at 0 (symbols 0 to 2). The short rep at symbol 3 is the cheapest way to say “the same byte again”: it needs no length and no distance, and it sets the state to 9. The literal after it (symbol 4, state 9, which is 7 or more) is coded against the byte one back, “l”: while the bits of “o” agree with the bits of “l” the decoder uses the probabilities for matched literals, and as soon as they differ (0x6F is 01101111 and 0x6C is 01101100: the first six bits agree and the seventh differs) it falls back to the ordinary tree. Then the state counts down 9, 6, 3, 0 through the literals that follow.
Each symbol used 0 to 2 input bytes. The decoder reads a byte only when Range
drops below 224, so a symbol that does not move Range far reads nothing, and the
bytes a symbol “used” are those it pulled in, not the ones that hold its bits: a range coder spreads one
symbol’s information over neighbouring bytes. That is why the explorer links a symbol to the bytes it
read, and links an output byte back to them, rather than claiming an exact byte for each.
Reading a trace
- Type: literal, literal after a match, match (a new distance), rep0 to rep3 (a remembered distance), short rep (one byte from rep0) or end marker.
- State before and after: 0 to 6 follow a literal, 7 to 11 follow a match or rep (the states table).
- rep0 rep1 rep2 rep3 after the symbol, as distances (1 is the byte before).
- Copies from: the output position a match reads, and the symbol that made the byte there.
- Range, Code: the range decoder registers before the symbol; re-running the range decoder from them reproduces the symbol.